Marching cubes is a computer graphics

Computer graphics

Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....

 algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

, published in the 1987 SIGGRAPH

SIGGRAPH

SIGGRAPH is the name of the annual conference on computer graphics convened by the ACM SIGGRAPH organization. The first SIGGRAPH conference was in 1974. The conference is attended by tens of thousands of computer professionals...

 proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface

Isosurface

An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value within a volume of space; in other words, it is a level set of a continuous function whose domain is 3D-space.Isosurfaces are normally displayed using computer graphics, and are...

 from a three-dimensional scalar field

Scalar field

In mathematics and physics, a scalar field associates a scalar value to every point in a space. The scalar may either be a mathematical number, or a physical quantity. Scalar fields are required to be coordinate-independent, meaning that any two observers using the same units will agree on the...

 (sometimes called voxel

Voxel

A voxel is a volume element, representing a value on a regular grid in three dimensional space. This is analogous to a pixel, which represents 2D image data in a bitmap...

s). An analogous two-dimensional method is called the marching squares

Marching squares

Marching squares is a computer graphics algorithm that generates contours for a two-dimensional scalar field...

 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 () 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

Gradient

In vector calculus, the gradient of a scalar field is a vector field that points in the direction of the greatest rate of increase of the scalar field, and whose magnitude is the greatest rate of change....

 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

Linear interpolation

Linear interpolation is a method of curve fitting using linear polynomials. Lerp is an abbreviation for linear interpolation, which can also be used as a verb .-Linear interpolation between two known points:...

 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

Magnetic resonance imaging

Magnetic resonance imaging , nuclear magnetic resonance imaging , or magnetic resonance tomography is a medical imaging technique used in radiology to visualize detailed internal structures...

 scan data images, and special effects or 3-D modelling with what is usually called metaballs

Metaballs

Metaballs are, in computer graphics, organic-looking n-dimensional objects. The technique for rendering metaballs was invented by Jim Blinn in the early 1980s....

 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

General Electric

General Electric Company , or GE, is an American multinational conglomerate corporation incorporated in Schenectady, New York and headquartered in Fairfield, Connecticut, United States...

. 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 didn't. This led to non-watertight surfaces produced by their algorithm.

The problem was that for cases where you have "rippling" signs, you can have at least two correct choices for where the correct contour should pass. It actually doesn't matter which choice you take, but you have to make this choice topologically consistent. Their 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.

Later versions, such as Marching Cubes 33 by Evgeni V. Chernyaev or the Asymptotic Decider

Asymptotic Decider

In Scientific Visualization the Asymptotic Decider is an algorithm developed by Nielson and Hamann in 1991 that creates isosurfaces from a given scalar field...

  corrected these mistakes.

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

Software patent

Software patent does not have a universally accepted definition. One definition suggested by the Foundation for a Free Information Infrastructure is that a software patent is a "patent on any performance of a computer realised by means of a computer program".In 2005, the European Patent Office...

. An implementation was patented (United States Patent 4,710,876) despite being a relatively obvious solution to the surface-generation problem, they claim. Another similar algorithm was developed, called Marching Tetrahedrons

Marching Tetrahedrons

Marching tetrahedrons is an algorithm in the field of computer graphics to render implicit surfaces. It clarifies a minor ambiguity problem of marching cubes with some cube configurations....

, 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).

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.