Marching Cubes Algorithm

Data Structure for the Algorithm#

The basis of the Marching Cubes Algorithm's functionality is the data structure. The data is represented by a 3D grid of points, where every point has an additional value (e.g a number like the brightness). You can subdivide this grid into many cubes by taking the points as corners.

Now we can take a closer look at the cubes we have created. Every cube has eight edges that hold values. The value can be a grayscale value, or just a weight for each point for instance.

Because every of those eight points contain a certain value, we can define a threshold that separates all points in two groups: the points whose values are above the threshold and those whose value are below it.

With this information, we can create parts of the so-called isosurfaces, which result in the whole object when they are put together. For every point whose value is above the threshold (in this example the points with the blue circles), we draw a triangle at the centers of the adjacent edges.

After repeating this process for every cube we have built the whole mesh, and we can see the resulting figure. The more cubes / points the grid has, the more detailed is the resulting object.

Implementation of the Marching Cubes Algorithm#

After understanding the concept, we can take a look on how to implement this algorithm. The primary challenge for this problem is the determination of the isosurface. Where do we need to draw the triangles?

At first glance, one could think of just looping over each point and if it's over the threshold to draw lines to the centers of the adjacent edges. But this approach does not work for every constellation. If you take a look on the points on the right side of the picture above, you can see one of a few special cases that won't work with this method.

Luckily, there is a much better to solve this problem. For this approach, we try to find all possible Combinations that the box can have. By trying all the 28 possibilities and leaving out the symmetrical mirrored ones, we can find 14 different arrangements (15 with the empty one).

Additionally, we can give each combination a unique number by considering is as a binary number. Every cube has eight corners, so we can represent the combination for a cube as an 8-bit integer value!

This integer value represents the example cube from the previous chapter. In general, we have 256 combinations (from 0 to 255), for which we can store the resulting triangles in a lookup table! This makes the implementation quite easy, because we just have to calculate the integer representation for each cube and draw the triangles that we get from the lookup table. In fact, you don't even need to create the lookup table on your own, this would be a lot of effort. You can find lookup tables for the most programming languages on the internet.

The following Code Snippet shows a simple implementation of the Marching Cubes Algorithm. Nevertheless, to make it as readable as possible, it is more pseudo-code than a full-working example.

class Point:

    def __init__(self, x: int, y: int, value: float):
        self.x = x
        self.y = y
        self.value = value


class Cube:

    def __init__(self, corner_points: List[Point]):
        self.corner_points = corner_points


class Grid3D:

    def __init__(self, cubes: List[Cube]):
        self.cubes = cubes


def integer_representation_for_cube(cube: Cube, threshold: float) -> int:
    integer_value = 0
    for index, point in enumerate(cube.corner_points):
        if point.value > threshold:
            integer_value += 1 << index
    return integer_value


def marching_cubes(grid: Grid3D, threshold: float):
    for cube in grid.cubes:
        integer_representation = integer_representation_for_cube(cube, threshold)
        triangles_to_draw: List[Triangle] = lookup_table[integer_representation]

        for triangle in triangles_to_draw:
            draw_triangle(triangle)  # (not implemented here)

Optimizing the Marching Cubes Algorithm#

Like for nearly every algorithm, you can optimize the Marching Cubes Algorithm.

Firstly, you can improve the accuracy of the triangles by setting the corners not always in the center of the edges. The points can have different distances from the threshold value and not every time the same. Therefore, it may make sense to draw the triangle corners closer or further away from the point. But this means that you need to adjust the lookup table and maybe parameterize it. This will take much more effort to implement it.

Another, more common optimization, is to parallelize the computation of the mesh. This is really easy for the Marching Cubes Algorithm and one reason why it's so popular. All the cubes are completely independent of each other, so we can easily compute the cubes in parallel.

Summary#

To sum up, the Marching Cubes Algorithm is very useful when it comes to modelling objects with a mesh. All you have to do is to change the values of the grid points and run the algorithm to update a mesh. Additionally, the algorithm is easy to implement and can be parallelized efficiently.

I hope the idea of the Marching Cubes Algorithm is clearer and you understood why the algorithm is quite attractive for meshing. However, if there is anything left unclear or you have another question, please leave a comment below and I will try to come back to you or adjust the post.