Vertices lead to Edges, Edges lead to Faces... Faces lead to Rendering
- Voxel Master Yoda
Introduction
Contouring is the process of converting implicit surfaces, such as volume data or voxels to a polygonal representation. This sort of operation is very useful for rendering blobs, finding the surface of water in a fluid simulation, performing mesh simplification, extracting surfaces from CAT scans, or even creating navigation graphs for AI characters to path plan against as described in Ju, Schaefer and Warren [2], and Schaefer and Warren [5]. Furthermore, if a spatial hierarchy like an octree is used to construct the contours and the hierarchy is retained with links to the tessellate faces, collision detection against the mesh can be done with extreme efficiency. This article traces current progress through a series of papers at Joe Warren's site, chosen because I've enjoyed his papers a great deal over the years.
Figure 1, a navigation mesh formed from the negative volume of a game level [2].
Marching Cubes
Dual contouring traces its lineage through the marching cubes algorithm presented first at Siggraph 87 by Lorensen and Cline [1]. In the simplest version of marching cubes, a volume is grid sampled, and all corners of cubes in the grid are classified as inside, outside, or intersecting the surface. Faces on the cube can then be classified according to the combinations of intersections identified where an edge between corners changes from inside to outside. The classification becomes an index into a table of triangles that are then emitted to generate the final surface. There's one extra twist which is the case of a diagonal stripe across the face; the strip could be either filled or empty - in this case sampling at the center of the face can be used to make the choice, see Figure 2.
Figure 2, classification in marching cubes. The red line is the edge to be checked, and the green indicates the two classification possibilities (from [2]).
Convex Contouring
Convex contouring is described in [2] as a method of improving the performance of marching cubes. One of the specific problems addressed were that marching cubes can generate inconsistent topologies if the choice indicated in Figure 1 is not evaluated correctly. Another issue addressed was that the tables marching cubes uses are hand created, not algorithmically derived from the topology and geometry of the individual polyhedrons. Where marching cubes generates triangles based on face intersections, convex contouring generates polygonal shapes that enclose the convex negative space within each cell.
Although the boundaries of the generated polyhedra are unique for each sign configuration of the sample cube corners, the polygonization is not. Imagine four points, two triangles could be generated with the shared edge spanning either of two pairs of vertices. A decision tree is introduced with possible triangulations at the leaves of the tree. The correct triangulation to pick is the one that results in all triangles facing the negative space within the cell convexly. The table construction process is described in [2], as is the algorithm for deriving a triangulation.
Dual Contouring
Marching Cubes results in a tessellation where vertices lie on the edges of the sampling grid, as does the convex contouring method. Dual contouring was introduced at Siggraph 2002 [4]. The data was represented as a signed octree for a significant reduction in memory requirements. The data was augmented with hermite data for exact intersection points and normals allowing reproduction of sharp edges and corners. Quadratic error functions were stored at each cube in the octree to allow the resultant mesh to be simplified versus an error metric.
Dual contouring methods produce vertices on the surface interior to each cube in the grid, and polygons dual to the edges of the grid. Since vertices are placed in the interior of the cubes and not on the edges of the cubes, there is more freedom as to where the vertex can be placed. This results in a tessellation that with more uniformly sized polygons, doesn't generate the thin slivers introduced by marching cubes when sampling cubes are near the surface, and eliminates the gridding effect of marching cubes. Figure 3 shows a comparison between the results of marching cubes and convex contouring. Various extensions are described in [3] for quickly updating a tessellation and rapidly updates for CSG operations.
Figure 3, marching cubes on the left, dual contouring on the right (from [3]).
Dual Marching Cubes
Finally we come to Dual Marching Cubes by Schaefer and Warren [5]. This method aligns vertices in the tessellation with features of the implicit function. The tessellation itself occurs on a grid that is the dual of the structured sampling grid. The result is that thin features missed, or requiring a lot of subdivision are preserved with a much sparser polygonization than that resulting from a structured grid. The method proceeds by creating an octree describing the volume to be contoured, then a dual grid of the octree is created by linking vertices at the centers of each grid cell to its topological neighbours as shown in Figure 4.
Figure 4. The dual grid constructed on a quadtree (from [5]).
The surface is then extracted using a simple extension of marching cubes to dual grids. Since each cell in the grid is topologically equivalent to a cube, the standard marching cubes tables can be used to generate the surface interior to the cell. Since the underlying representation of the data is an octree, the resulting tessellation is much sparser than Dual Contouring or Marching Cubes. Intriguingly, the results are similar to adaptive Marching Cubes since resolution is added appropriately by the creation of the octree. Figure 5 shows a comparison of Dual Marching Cubes with Marching Cubes and Dual Contouring. Further explanation of the algorithm can be found in this presentation.
Figure5. The rocket in the upper left is the original CSG model; upper right is the mesh extracted by Dual Marching Cubes, Marching Cubes is in the lower left, and Dual Contouring is in the lower right (from [5]).
In Closing
It appears that recent research is more concerned with generation of tetrahedral meshes, so as far as I can tell, this sampling represents the state of the art. An excellent collection of references can be found here.
References
[1] W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. In Computer Graphics (Proceedings of SIGGRAPH 87), volume 21, pages 163–169, Anaheim, California, July 1987. pdf
[2] T. Ju, S. Schaefer, and J. Warren. Convex contouring of volumetric data. The Visual Computer, 19(7–8):513–525, 2003. pdf
[3] S. Schaefer and J. Warren. Dual contouring: The secret sauce. Technical Report 02-408, Department of Computer Science, Rice University, 2002. pdf
[4] T. Ju, SF. Losasso, S. Schaefer, and J. Warren. Dual contouring of hermite data. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press, 339–346. pdf
[5] S. Schaefer and J. Warren, Dual Marching Cubes: Primal Contouring of Dual Grids. pdf