Matt's Webcorner

Marching cubes is a simple algorithm for creating a triangle mesh from an implicit function (one of the form f(x, y, z) = 0). It works by iterating ("marching") over a uniform grid of cubes superimposed over a region of the function. If all 8 vertices of the cube are positive, or all 8 vertices are negative, the cube is entirely above or entirely below the surface and no triangles are emitted. Otherwise, the cube straddles the function and some triangles and vertices are generated. Since each vertex can either be positive or negative, there are technically 2⁸ possible configurations, but many of these are equivalent to one another. There are only 15 unique cases, shown here:

We iterative over all cubes, adding triangles to a list, and the final mesh is the union of all these triangles. The smaller we make our cubes, the smaller the mesh triangles will be, making our approximation more closely match the target function. As a simple example, the function x² + y² + z² - 1 = 0 represents the unit sphere. Below is the result of using marching cubes on this function, shown at two possible grid resolutions:

Even more intelligent forms of marching cubes, which adapt their cube resolution to match local surface complexity, produces pretty low quality meshes. As a comparison, in the figure below the right mesh was made with adaptive marching cubes while the left mesh was made with a much more advanced algorithm (see Voronoi-based Variational Reconstruction of Unoriented Point Sets).

Nevertheless marching cubes is useful for its simplicity. Implicit functions occur a lot in computer graphics and other fields, and rendering them is often the most intuitive way to work with them. My CS148 slides on marching cubes can be found here.