In an interesting historically-tinted blog post, Nick Porcino looks at various methods of contouring in graphics rendering, starting off with the marching cubes algorithm first introduced during Siggraph '87. The method essentially divides a volume into cubes and replaces the cubes with corresponding polygons to approximate the original shape.

After quickly recapping that original principle, Porcino moves onto evolutions of that algorithm: convex contouring ("Where marching cubes generates triangles based on face intersections, convex contouring generates polygonal shapes that enclose the convex negative space within each cell"), dual contouring ("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"), and dual marching cubes.

Dual marching cubes was introduced in 2004. As Porcino describes:

"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.

"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."

Porcino includes visual aids that demonstrate how the dual marching cubes algorithm manages to represent geometry better than the other sampling methods, even with a lower polygon count.

Despite the cube-centric tack of the post, Porcino notes that progress is being made using tetrahedral meshes, and points to the website for Jonathan Shewchuk's UC Berkeley computer science course as a useful resource to that end.