### Marching Cubes

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 28 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 x2 + y2 + z2 - 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.

#### Code

This code is all based off my BaseCode. Specifically you will need the contents of Includes.zip on your include path, Libraries.zip on your library path, and DLLs.zip on your system path. The MarchingCubes.cpp and MarchingCubes.h files handle turning a single cube into triangles, while the IsoSurface class handles processing the input function into cubes and repeatedly calling the Polygonise function in MarchingCubes.h. It is just a demo and lets you toggle between 3 pre-defined functions. If it works you should see the function below, sin(xy + xz + yz) + sin(xy) + sinf(yz) + sinf(xz) - 1 = 0:

As a more interesting sample, the following is an implicit surface that I rendered via marching cubes and used as my desktop image for a while:

MarchingCubes.zip (includes project file)

#### MarchingCubes Code Listing

App.cpp, Web Version
App.h, Web Version
Config.h, Web Version
Controller.cpp, Web Version
Controller.h, Web Version
Engine.cpp, Web Version
Engine.h, Web Version
IsoSurface.cpp, Web Version
IsoSurface.h, Web Version
Main.cpp, Web Version
Main.h, Web Version
MarchingCubes.cpp, Web Version
MarchingCubes.h, Web Version
Assets
NormalColor.ps, Web Version
NormalColor.vs, Web Version

Total lines of code: 1566