Marching Cubes

Marching cubes is a computer graphics algorithm for extracting a polygonal mesh of an isosurface from a 3-D volume. The marching cubes algorithm was published in the 1987 SIGGRAPH proceedings by William Lorensen and Harvey Cline. [1]. A patent for the algorithm was applied for on June 5, 1985. The patent has now expired.

Example of the 15 unique Marching Cube Solutions
Example of the 15 unique Marching Cube Solutions

Basic Theory

As the name suggests, marching cubes only works with cubic-cells (commonly called Voxels). By analyzing each cell individually, you can quickly and easily determine if the eight corner points are "above" or "below" the desired isovalue. Each of these eight values can easily be mapped to a single bit of an 8-bit number, reducing the problem to 255 possible combinations. These 255 combinations can be further reduced, using geometric symmetric, down to 15 unique solutions. Most implementations at this point use a simple lookup table and linear interpolation to determine where to create points along the edges.

Also, vertex normals can be computed using the gradient between the vertices, interpolated along the voxel edges. In most rendering applications, this yields a significant quality increase in the display at a minimal impact to performance (on most modern graphics hardware).

Isosurface extraction remains one of the most common visualization methods in use today. It is also used by several other algorithms such as Metaballs and Part Extraction.

Modifications

Modifications can easily be made to extract it to any 3-D structured grid by performing the marching cubes algorithm in the IJK Coordinate space and interpolating the results back into XYZ space. While this is not technically correct, for most applications the difference is negligible.

Also, since each cell is processed individually, it is easy to convert marching cubes into a "streaming" operation where only two slices of the data are necessary in memory at any given time. This allows marching cubes to work on extremely large data sets, hopefully extracting isosurfaces that are easier to manipulate interactively than the entire data set.

History

This algorithm was originally developed and patented by GE Medical Systems for use in their CT and MRI equipment. Just recently, the patent has expired and GE has decided not to pursue renewal, thereby placing this algorithm in the public domain and making it safe for use.

During its protection by the patent, an alternative was developed called Marching Tetrahedra that performs a very similar operation but on tetrahedral cells rather than voxels. Tetrahedral cells are easily created from almost any cell type, making this a fast and flexible alternative to marching cubes. Because of the added overhead of switching from structured to tetrahedral meshes, however, the algorithm never achieved widespread use. The recent release of marching cubes to the public domain further pushes marching tetrahedra into obscurity.

Also, there are two common versions of marching cubes in use. The original version worked well but yielded triangles in odd winding orders. Since OpenGL uses winding order in the decisions for backface culling, triangles would drop at odd and inopportune times. Another version was published shortly afterwards with a slightly modified lookup table that fixed this issue.

Sources

  1. William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3-D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987 (link)

Back to Visualization Algorithms