This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
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.
Let's say we have a function.
x2 + y2 = 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 some other arbitrary curve or storing it in the same array with lines, triangles, and all the other contours regardless of their original nature.
Conceptually, contouring is simple. Let's rewrite our function:
F(x, y) = x2 + y2 - 4
Now we cover the plane with a grid. For every two adjacent cells, its shared border becomes a piece of the contour if the function F(x,y) changes sign between these two cell's centers. And that's it. This simple rule is enough for simple contouring.
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 for a circle.
We need something better.
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 a better place for them? We have 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 linear interpolation.
Sign buttons are clickable.
This is not flawless. Since our target function is not necessarily linear, we can't expect linear interpolation to approximate it perfectly well. Ideally, we should have been looking for an actual point where the curve intersects an edge and not an interpolative prediction.
But linear interpolation still works well enough most of the time, and it's super cheap to compute.
Here, you can try it out yourself. Just click and drag anywhere on the canvas.
The ironic drawback of marching cubes is that they don't work very well with real cubes.
It's a red rectangle approximated by marching cubes' blue contour ↑
It gets better with a finer grid, sure, but conceptually this is the weak spot. For this problem, we need something different.
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 dual methods is the idea of duality. The very concept, not the specific algorithm. We will look into this right now.
With marching cubes we did the following:
Conceptually, dual contouring goes like this:
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.
There is a red rectangle under the green one, but it's completely covered ↑
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.
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 conceptually, they are both rather simple. I hope this explanation shows it well.
| Index #mathematics #algorithms #tutorials | ← there's more. |
+ Github & RSS |