Marching cubes: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Head and cerebral structures (hidden) extracted from 150 MRI slices using marching-cubes (about 150,000 triangles)

Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline,[1] for extracting a polygonal mesh of an isosurface from a three-dimensional scalar field (sometimes called voxels). An equivalent two-dimensional method is called the marching squares algorithm.

The algorithm proceeds through the scalar field, taking eight neighbor locations at a time (thus forming an imaginary cube), then determining the polygon(s) needed to represent the part of the isosurface that passes through this cube. The individual polygons are then fused into the desired surface.

This is done by creating an index to a precalculated array of 256 possible polygon configurations (28 = 256) within the cube, by treating each of the 8 scalar values as a bit in an 8-bit integer. If the scalar's value is higher than the iso-value (i.e., it is inside the surface) then the appropriate bit is set to one, while if it is lower (outside), it is set to zero. The final value after all 8 scalars are checked, is the actual index to the polygon configuration array.

Finally each vertex of the generated polygons is placed on the appropriate position along the cube's edge by linearly interpolating the two scalar values that are connected by that edge.

15 unique cube configurations

The precalculated array of 256 cube configurations can be obtained by reflections and symmetrical rotations of 15 unique cases. However, using just 15 unique base cases produces an isosurface that is not water-tight. The base cases that can produce a water-tight isosurface are shown in the Marching Cubes survey article external link below (and in other papers).

The gradient of the scalar field at each grid point is also the normal vector of a hypothetical isosurface passing from that point. Therefore, we may interpolate these normals along the edges of each cube to find the normals of the generated vertices which are essential for shading the resulting mesh with some illumination model.

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.

Patent issues

The Marching Cubes algorithm was the prime example in the graphics field of the woes of patenting software, patented despite being a relatively obvious solution to the surface-generation problem. Another similar algorithm was developed, called marching tetrahedrons, in order to circumvent the patent as well as a minor ambiguity problem of marching cubes with some cube configurations. This patent expired in 2005, and it is now legal for the graphics community to use it without royalties since more than 20 years have passed from its filing date (June 5, 1985[2]).

Sources

1. ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
2. ^ Marching Cubes, US Patent Office entry