Marching cubes

Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (sometimes called voxels). This paper is one of the most cited papers in the computer graphics field. The applications of this algorithm are mainly concerned with medical visualizations such as CT and MRI scan data images, and special effects or 3-D modelling with what is usually called metaballs or other metasurfaces. An analogous two-dimensional method is called the marching squares algorithm.

The algorithm was developed by William E. Lorensen and Harvey E. Cline as a result of their research for General Electric. At General Electric they worked on a way to efficiently visualize data from CT and MRI devices.

Their first published version exploited rotational and reflective symmetry and also sign changes to build the table with 15 unique cases. However, in meshing the faces, there are possibly ambiguous cases. These ambiguous cases can lead to meshings with holes. Topologically correct isosurfaces can still be constructed with extra effort.

The problem was that for cases with "rippling" signs, there are at least two correct choices for where the correct contour should pass. The actual choice does not matter, but it has to be topologically consistent. The original cases made consistent choices, but the sign change could lead to mistakes. The extended table in shows 33 configurations.

The ambiguities were improved upon in later algorithms such as the 1991 asymptotic decider of Nielson and Hamann which corrected these mistakes. Several other analyses of ambiguities and related improvements have been proposed since then; see the 2005 survey of Lopes and Bordlie for instance.

...
Wikipedia