Interactive explanation of marching cubes and dual contouring

Marching cubes and dual contouring are mostly known as 3D mesh generating algorithms, but since it's hard to explain 3D things using 2D display, we will concentrate on planar analog. We will do contours.

What is contouring?

Let's say we have a function.

x 2 + y 2 = 4

This function represents a circle. Now let's say we don't want a perfect circle, but its contour, — a set of line segments that represent the circle within some tolerable error.

With the contour, we can do things that would be tricky to do with the circle itself. Like intersecting it with another curve or storing it in the same structure with lines, triangles and all the other contours regardless of their original nature.

Conceptually, contouring is very easy. Let's rewrite our function:

F(x, y) = x 2 + y 2 - 4

Now we cover a plane with a grid. For every two adjacent cells, we can consider their shared border a piece of the contour if the function F(x,y) changes sign between these two cell's centers.

Well, technically it does represent the original curve. And the error is predictable. It never exceeds half of the cell's diagonal. But this contour has way too many corners as for a circle.

We need something better.

Marching cubes

What if we add line segments that go across the cells? We can measure function signs in every corner for each square, and add line segments accordingly. For now, let's connect the sign changing edges from middle to middle.

There are 4 squares, 2 signs; there are only 16 combinations of sign change possible.

Click the +/- buttons to change signs.

Since pairs of signs for each shared edge change synchronously for both cells, the line segments connect automatically into a continuous contour.

It's a little better than before, but it is still far from the shape we want.

What if we don't put our line segments ends in the middle of edges, but try to find the best place for them anywhere on the edges? We can get not only the function's signs but also the values so why don't we exploit that?

One way to find a better place to put line segments ends will be by using the linear interpolation.

Sign buttons are clickable.

It's not the best way possible. Since our target function doesn't have to be linear, we can't expect linear interpolation to work perfectly well. Ideally, we should have been looking for an actual point where the curve intersects an edge.

But interpolation works good enough most of the time, and it's super cheap.

Here, you can try it out yourself. Just click and drag anywhere on the canvas.

The obvious drawback of marching cubes is that they don't work very well with real cubes

It gets better with a finer grid, sure, but conceptually this is the weak spot. We still need something better.

Intermezzo

Marching cubes is not a single algorithm. It's a general approach covering a whole family of algorithms. Some are adaptive. Some are supplemented with sharp feature detection. Some can preserve the topology of non-manifold surfaces. Some work faster than others. Some have better memory consumption.

Just as that, dual contouring is not a single dual method. There are plenty. From primitive surface nets to the most sophisticated adaptive methods. We will not look into them.

I believe, the most important lesson we can take from this is the idea of duality. The very concept, not the specific algorithms. We will look into this right now.

Dual contouring

With marching cubes we did the following:

1. If a function changes its sign in a cube , we add a line segment from edge to edge .
2. The exact ends of each segment are being placed anywhere on the edges to minimize the difference between an isoline and a contour.

Conceptually, dual contouring goes like this:

1. If a function changes its sign on the edge , we add a line segment from cube to cube .
2. The exact ends of each segment are being placed anywhere in the cubes to minimize the difference between an isoline and a contour.

Noticed anything?

Exactly! This is the same algorithm. Only cubes now play as edges and edges as cubes. That's the duality.

And now, since we get to place a segment end anywhere in the cube, we can also choose it to be on the corner.

Here, try it yourself. Click and drag.

Duality is a fascinating concept. The way you get new properties from an algorithm by merely swapping planes and points is in a way a mathematical miracle.

Conclusion

In practice, marching cubes and dual contouring tend to be complicated because we want more than just a contour or a triangle mesh out of them. We want them to work with sharp features, textures, open surfaces, non-manifold models, and all in a reasonable time, too. But they are both rather simple conceptually. I hope this explanation shows it well.