Marching Cubes Algorithm

marching cubes single cell

In a Nutshell

Imagine that you have a 3D space having a color assigned to each point ranging from black to white. Now imagine that you take a reference color, for example grey; and call whatever is lighter than it to be “inside” and whatever darker than it to be “outside”. Now to enforce this separation, you simply create a surface along all the points that are grey, thus effectively separating above & below vertices from each other. You have created a mesh.

In marching cubes, to form a mesh, we divide our space in cells & loop over each cell. We check the color at each point of the cell. If top four vertices have darker color & bottom four have lighter color than grey, we’ll know that our mesh surface (being represented by grey) passes between them. We’ll construct the part of mesh that passes through this cube immediately here; and continue with next cell. By looping over the entire space, we keep constructing parts of mesh, and eventually the whole mesh after we have done.

2D Anology

marching cubes in 2d
red represents our geometry

One of the best ways to understand the algorithm is to imagine it working on a 2D plane. Imagine that you have a grid with all points having some scalar value attached with them. We want an algorithm to wrap/cover all those points who are white. We see one cell at a time.

  1. If all of the 4 vertices are white, ignore the cell (make no geometry).
  2. If bottom-left vertex is white, and all other 3 vertices are black: form a face diagonally.
  3. If 2 vertices are white & other 2 are black, make a line between them.
  4. And so on…

All possible configurations of geometry for one cell can be saved in a table. And when algorithm is making the geometry, it loops over each cell & puts one of the configurations that matches the given condition (whether all are white, whether one is white ad so on).

Creating a scalar field

In case of a procedural terrain, you might be wondering how exactly scalar field (which is the input for marching cubes algorithm) is created? Since for simple demonstration, all we have is perlin noise. We know that perlin noise returns value between (-1, 1) for any given vec3 input.

Scalar field is made when we assign a value (a number) to every point in 3D space. To understand scalar field, think of the whole 3D space be filled with fog. The color of every fog particle can range from white to black (0 to 1). This is a scalar field.

The Algorithm’s Process

Once we have created a scalar field, we now call a function on it that covers (forms a shell around) all the points in 3D space whose associated scalar value is above certain given threshold. In other words, it hides all those vertices whose scaler values are above some given threshold by creating a mesh surface covering the whole volume.

1. In this algorithm, we divide our given space into cells & iterate over each cell.

2. We check scalar values associated with every vertex of this cell & determine which one is “below” the surface (or have scalar value above our given threshold) & which one have value below our given threshold (outside the surface).

3. Those having values above our threshold should be hided from others.

4. For this, we have already defined all the possible geometry configurations for a cube (since we are dividing our space into cubes/cells & working on one at a time).

5. We then generate geometry within our current cell based on one of the configurations that matches with our case (for example, what configuration to apply on this cell when all vertices except one are having values below our threshold).

6. We iterate over entire 3D space (cell by cell (cube by cube); within our defined bound; in case of terrain, this bound is chunk size).

All possible configurations

All possible configurations for geometry within a cube, due to its 8 vertices is 2^8 = 256. But most of them are symmetries & only 15 are unique possible cases.

In practical implementation

For now, this is still a draft & I plan to write about practical implementation here in detail in next update. But this link provides good implementation in HLSL: https://polycoding.net/marching-cubes/part-1/

More reading

Following is a useful link from gpugems that’s worth a read.

  1. https://developer.nvidia.com/gpugems/gpugems3/part-i-geometry/chapter-1-generating-complex-procedural-terrains-using-gpu
  2. https://polycoding.net/marching-cubes/part-1/
Table of Contents