Marching Cubes

Marching cubes is an algorithm in the field of geometry processing which converts an implicit surface into a triangle mesh. An example is shown in the figure below:

The algorithm is the work by Lorensen and Cline which they presented in the year 1987 [1]. Their application lies in the medical field where scans, produced by medical imaging hardware, serve as an input. These scans are subdivided into slices which are then reconstructed to a 3D model by Marching Cubes. However, this principle can be applied to every implicit function by taking different level sets as "slices".

The Algorithm in a Nutshell

Let us take the implicit sphere example from above and use it in this explanation. The main idea of marching cubes is to subdivide the space into equal sized cubes. For example, one could build a grid with 10 x 10 x 10 cubes around the sphere. Now Marching Cubes has the nifty idea of looking at each cube and determine the surface interesection by looking at the corner. For each corner we can easily determine whether the corner lies inside or outside the surface by plugging the corner coordinates into the implicite surface equation.

For example: Take the point (0, 0, 0) and plug it into the sphere equation above, it will yield 0 = 1 as a result. First of all this means that the point is clearly not on the surface as it violates the equation, but this also means that the point is inside of the surface, because 0 is smaller than 1.

Another example: Take the point (2, 0, 0), we receive 4 = 1. This time the point is outside because 4 is larger than 1.

Marching Cubes now proceeds to take each corner of every cube and performs exactly this check. From this we can infer how the surface is passing through the cube, here some examples:

Since we only have eight corners, this means there are only 2^8 = 256 possible surface intersections which we can precompute. If we now iterate all cubes and estimate the surface passing through them, we can gradually build a mesh from this. Thus the name of the algorithm: It marches from cube to cube.

I have investigated this algorithm in the course "Introduction to Scientific Writing" at university and volunarily programmed a visualization served by the Herkules testing system. This visualization is now shown in the lecture and in the third assignment of the course "Fundamentals of Geometry Processing". It was programmed using the Three.js library and embedded in a Svelte page.

Use Case in a Geometry Pipeline

To close this post, I would like to quickly highlight a use case in a geometry pipeline. Given is a point cloud and for each point we know the vertex normal vector (modern scanners are able to extract this information).

What we can now do is, we can move each point in the cloud a bit forward and bit backward. Thus we can create a notion of inside and outside:

This allows us to create a huge equation system where we have triplets of equations for every point. Now comes the crucial part: The points themselves are described using a radial basis function and on the right hand side we specify a distance:

• 1 for outside
• 0 for every original point
• -1 for inside

The solver will give us a so-called Signed Distance Function which is a function that returns a distance value to the surface for any input point. And this is precisely what gets passed onwards to the Marchign Cubes algorithm that builds a mesh from this.

[1] W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3d surface construction algorithm,” ACM SIGGRAPH Computer Graphics, vol. 21, July 1987.