3D Geometric Representations: There is no Silver Bullet

Back in the mid-to-late 1980’s, a debate was raging in the ray tracing community. This was a time when ray tracing was far too slow to be considered useful outside of academic circles, and several intersection-culling data structures (e.g., grids, octrees, k-d trees, bounding volume hierarchies, etc.) were introduced to speed it up. Many experts vigorously voiced their opinions as to which data structure was the best, and the debate raged on. Decades later, some of those data structures survived and found an appropriate place in ray tracing (and some in volume graphics), and they are currently thriving thanks to architectural advances in CPUs and especially in GPUs.

In this decade, another debate in 3D graphics is brewing, this time around the best geometric and rendering representation for real-time 3D visualizations. Traditionally, in 3D graphics systems, we distinguish among modeling primitives such as free-form surfaces (e.g., NURBS, subdivision surfaces, etc.) to represent objects, geometric primitives such as polygonal meshes or voxels for fast object manipulations, and display or rendering primitives such as triangle meshes or point clouds that are used to create images. Many 3D real-time applications treat geometric and rendering representations as one, to avoid performance penalties of conversion between representations, or the overhead of maintaining multiple representations. Thus, we are now less inclined to distinguish between geometric and rendering representations. As well, the tendency is to do a one-time, initial convert of the modeling primitives into the desired geometric and rendering representation, to get started in the real-time 3D application.

For the purpose of this post, we concentrate on geometric and rendering representations included often in 3D real-time applications: polygons, voxels, and point clouds. Each representation has progressed in capabilities such that each can render with rich, dependable, and high-quality results. However, on the web, you may have read polarized opinions such as “polygons are the only representation in any serious 3D software”, or “this is the end for polygons”, when polygons are compared to one of the other representations. Note that by polygons, we mean triangles, quads as well as their associated meshes.

While opinions on either extreme are outrageous, they should make us ponder as to why there are such strong opposite opinions. In this post, an objective review of the three different representations will be offered, including their geometric and rendering advantages and disadvantages, as discussed in the context of standards & adoption, surface characteristics, level of detail, and dynamic modifications. In the end, just as with the ray-tracing debate, we believe each representation discussed has an appropriate and productive place in real-time 3D visualization.

Standards and Adoption

The most significant advantage for polygons is the dominant success, investment, and support that it has had in terms of standards and their wide adoption. Examples of such standards include: OpenGL, OpenGL-ES, WebGL, VRML, X3D, STL, OBJ, etc. As well, most game engines and their SDK are based on polygons. The levels of investment and support for other representations pale in comparison to polygons. This has several important advantages for developers when using polygons: 1) faster development time towards the visualization application; 2) wider deployment set of platforms by developing on those standards (OpenGL, WebGL); 3) easier to convert to accepted polygonal formats (STL, OBJ), including 3D-printing formats.

As a result, if polygons do a good enough job for the needs of the application, this factor alone is a compelling reason to jump right to polygons. This is already evident in most games where polygons are dominant, not only as the geometric and rendering representation, but also as the source of input from modelers such as Studio MAX, Blender, Sketchup, etc. Thus, the opinion of “this is the end for polygons” is nowhere near warranted, and the opinion “polygons are the only representation in any serious 3D software” picks up steam. 

In terms of point clouds, adoption is related to the wide emergence of scanners and computer vision techniques, which both generate point cloud data as output. This implies that with time, point cloud data is growing in quantity, although the density of point cloud data can be so large that feasibility of representation and storage is often in question. Support on standards for point clouds is growing but still pale in comparison to polygons, yet their support is still ahead of voxels, even if they are gaining steam in medical visualizations, games, and simulations.

Surface Characteristic Efficiency

In terms of surface characteristics of each representation, polygons are ideal for planar geometric situations, such as architectural applications. However, referring to the left-hand side of the above image, it takes a lot of little polygons to accurately represent detailed surfaces, which are becoming more common due to the fine details captured from certain scanners. 

Voxels and point clouds have the advantage and disadvantage of being surface-characteristic agnostic, meaning that there is no bias towards any surface characteristic. This surface-characteristic agnostic behavior becomes an advantage with detailed surfaces as compared to polygons – they are just voxels and points put in the right places. However, the disadvantage is that they treat planar surfaces the same way, which makes them a lot less efficient as compared to polygons – e.g., too many voxels or points to represent a large rectangle. 

Another interesting surface characteristic is the spatial 3D-nature of voxels and point clouds, where 3D geometric differencing can be easily achieved. This capability allows visual comparisons between geometric models at a very granular level – see the right-hand side of above image, where the green dots indicate geometric differences between the left and right tires.

Level of Detail (LOD)

For polygons, the curvature of objects can either kill performance, or run at optimal speeds, depending on the level of detail (LOD), thus impacting on the visual quality of the geometric model (and its rendering quality). The objective is to get the best-looking model while minimizing the polygon count as well as generating smooth transitions between LODs – thus optimizing visual quality and speed. If not achieved, model features will pop in and out over a fly-through, in ugly and unexpected ways. Such popping artifacts are difficult to avoid for polygons because polygons are planar, and reduction of the polygon count can drastically alter the shape of the original objects (i.e., smooth transition between LODs become difficult). There are also popping artifacts due to the terminator problem and elongated triangles, but we will leave those details for a future discussion.

Geometric model simplification occurs automatically when the object is converted into voxel or point cloud formats. Any additional LOD can be generated at any chosen level of resolution. In fact, a CLOD (continuous LOD) implementation can treat a voxel set as a 3D-mipmap, with smooth LOD transitions between each level. LOD in this context is critical due to the massive amount of data that would otherwise need to be processed all the time.

The main caveat to the LOD advantage of voxels and point cloud data is that there is no obvious extrapolation of the geometry beyond that highest level of detail. If there is need to perform extreme zoom that higher than the available LOD, the visual results will not be good.

Dynamic Modifications

There are several types of real-time dynamic modifications to consider in certain applications.

Creating holes: voxels and point clouds are ideal for this task, because a hole is basically the trivial deletion of voxels/points, whereas it means re-tessellation for polygons and possible topological changes. As well, complexity of re-tessellation may result in a lot more polygons – for example, a simple triangle, after introduction of a single hole, will be a mesh of many little triangles. 

Particle-based simulations: if a dynamic modification requires re-computation of an entire region, such as in dynamic terrain simulations or natural phenomena simulations (e.g., using LiDAR data), it is actually simpler to do it in voxels or point clouds, because it means shifting voxels/points around, which can be done in real time, as opposed to expensive re-tessellations for polygons. As well, voxels have an additional advantage in which the uniform data points can allow simulations to discretize their computations represent, and render the data, all in the same step. In fact, many polygonal systems convert to voxels or point clouds when particle-based simulations and fluid simulations are needed. 

Soft body: most soft-body modifications require connected neighboring information, which polygons have, but voxels and point clouds do not have. In fact, if there is a single largest criticism of voxels and point clouds in real-time 3D visualization, this topic would be at the top of the list.

Is There a Silver Bullet?

Based on the above discussion, it is clear that neither polarized comments (“polygons are the only representation in any serious 3D software”, and “this is the end for polygons”) hold water. There are certainly many other factors that determine which representation would be best suited for the needs of your application – this post tries to cover only some high-level capabilities. I am interested in hearing about other interesting high-level capabilities relevant to this debate.

In general, the strong support for standards with polygons continue to play a huge role in adoption (in support of polygons). With technical merits of the other representations, it is important to consider them when evaluating the needs of your application. Thus, there is no silver bullet in term of the best representation. However, until there is increased support for the other representations in standards, the needs of those representations can only be fulfilled by the domain experts.