Marching cubes
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 analogous 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 indices 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.
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.
History
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. Unfortunately they made some mistakes. The minor one was that "case 14" - the 15th, because they started at "case 0" - was actually a symmetric image of case 11, but more importantly their base cases could lead to topological wrong decisions. For example case 11 should fit to a rotated and sign changed version of case 3, but it did not. This led the algorithm to produce non-watertight surfaces.
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. Thus, a corrected table includes their 14 unique cases, plus 14 correct sign-changed cases, so 28 cases in total.
The ambiguities were improved upon in later algorithms such as the 1991 asymptotic decider of Nielson and Hamann[2] which corrected these mistakes.[3][4] Several other analyses of ambiguities and related improvements have been proposed since then; see the 2005 survey of Lopes and Bordlie for instance.[4]
Patent issues
The marching cubes algorithm is claimed by anti-software patent advocates as a prime example in the graphics field of the woes of patenting software. An implementation was patented (United States Patent 4,710,876[5]) despite being a relatively obvious solution to the surface-generation problem, they claim. Another similar algorithm was developed, called marching tetrahedrons, in order to circumvent the patent as well as solve 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 17 years have passed from its issue date (December 1, 1987[5]).
Sources
- ^ William E. Lorensen, Harvey E. Cline: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987
- ^ Nielson, Gregory M.; Hamann, B. (1991). "The asymptotic decider: resolving the ambiguity in marching cubes". Proceeding VIS '91 Proceedings of the 2nd conference on Visualization '91.
- ^ Charles D. Hansen; Chris R. Johnson (2004). Visualization Handbook. Academic Press. p. 9. ISBN 978-0-12-387582-2.
- ^ a b A. Lopes; K. Bordlie (2005). "Interactive approaches to contouring and isosurfaces for geovisualization". In Jason Dykes; Alan M. MacEachren; M. J. Kraak (eds.). Exploring Geovisualization. Elsevier. pp. 352–353. ISBN 978-0-08-044531-1.
- ^ a b Marching Cubes, US Patent Office entry
See also
External links
- Overview and source code by Paul Bourke
- GameDev overview by Matthew Ward of Worcester Polytechnic Institute
- Introductory description with additional graphics
- Some of the early history of Marching Cubes
- Timothy S. Newman and Hong Yia. Marching Cubes survey article.
- How to invent marching cubes?