###
**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 2^{8} 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^{2} + y^{2} + z^{2}
- 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 **