Voxels with Both Round and Square Features
Since last time I have managed to finish the first working version of my Marching Cubes [1] (or MC for short) implementation. As I have said in my previous article, I wanted to have both Minecraft-like [2] cube voxels and MC's round shapes.
Marching Cubes
Look at this illustration:
Left image: A segment of a blocky voxel scene and how an MC cube relates to it.
Right image: Same MC cube with the corresponding geometry inside.
On the left, there is a typical square voxel scenario, visualized with the gray cubes (for reference, see Figure 1). The black and white dots mark the scalar values of the voxel scene, and each scalar value correspond to the center of a cube. They have a binary state, where black means filled, and white means empty.
An MC cube other hand has the scalar values at its corners instead, so with 8 corners, and each having a binary state, there is a total of 256 different configurations, each with a predefined geometry, confined to the boundaries of this cube. This allows to have, instead of uniform cubes, all kinds of round geometry that better follow the shape of the voxel data. (Figure 2)
In the original paper there were 15 unique base cases as shown below, the rest of them can be achieved by rotating, mirroring and inverting them to get the total of 256 configurations.
The 15 Marching Cubes base case as presented in the original paper by Lorensen and Cline. The orange dots mark the filled voxels, and the triangles are the corresponding geometry. (source: Wikipedia)
Now, if you look closely, you can see that the triangle vertices always connect to the middle of one of the edges of the MC cube. So if we number the cube edges – which of there's 12 in total – a triangle can be defined by 3 of these edge indices, like so:
Left image: Regular MC square edge indexing.
Right image: A MC configuration, using this indexing to define two triangles. Indexing can start at any vertex, but the direction has to be consistent (like counter clockwise in my case).
Interpolation
To have actual round shapes, we need to introduce interpolation (Figure 3). Although the scalar values have to be binary to index the MC configuration, a fractional value can be binarized. So let's say the range for values is [0, 1], if the scalar value is less than 0.5 then it's outside the geometry (0), if it's greater or equal than 0.5 then it's inside (1).
When the triangle vertex is placed on an edge, the actual position of this vertex along the edge can be calculated with simple linear interpolation, as demonstrated below:
Scalar values are marked on the image, vertices are placed along each colored edge. One scenario is highlighted where the scalar values are s0 and s1, with the formula to calculate the vertex position along the green edge.
Bring Back the Square Features
With the Marching Cubes algorithm in place we finally have round shapes, but now we had lost the squares. Luckily, the way MC works, with some modification it can also accommodate square features. (Figure 4)
Left image: A segment of a blocky voxel scene and how an MC cube relates to it.
Right image: Same MC cube with the corresponding square geometry inside.
Along with the scalar values that define the geometry we could also store information about it being a round or square voxel. And with that, we can create mixed configurations for the transitions, so take this for example:
Transition from round (left) to square (right). Notice the filled circle and rectangle at the corners, the circle means round features and the rectangle the square features.
Now each corner instead of being binary as in inside or outside the geometry, can also differentiate between square (inside), round (inside) and outside. That means instead of 256 predefined configurations, now we need 6,561!
The triangles related to the square features don't need interpolation, but they need more than just the MC cube's edges. For them, the center of each cube face and the core has also needs to be indexable as a vertex for the triangles, so I extended the previous indexing as shown below:
Left image: Cube face indexing, plus 18 as the core.
Right image: A square MC configuration, using this extended indexing to define two triangles.
Lookup Table
Performance-wise the size of the lookup table for the configurations is irrelevant, that's the whole point of using a lookup table. On the other hand, it has to be constructed at some point. A few base cases has to be hand-made, but the rest can be created automatically from the base ones by mirroring, inverting and rotating them. To put this into numbers, here's how much cases that means:
| Base cases | Total | Automated | |
|---|---|---|---|
| Round | 21 | 254 | 91.7% |
| Square | 20 | 254 | 92.1% |
| Round + Square | 67 | 5,796 | 98.8% |
| Empty | — | 257 | — |
| Total | 108 | 6,561 | 98.4% |
And that sums up to 6,561 individual cases in the look up table. 98.4% automation doesn't sound bad, but still, the mixed configurations took me weeks to set up. The hardest part was dealing with the ambiguous cases, because for some configurations there are more than one solution, and if they are not consistent, holes can appear in the geometry when these blocks are placed next to each other.
The struggle. Every single case had to be thought out, and indexed for each triangle.
Lights, Camera, Action!
To see all this in action, open the gallery below. There's a scene in all 4 possible variations, first with regular blocks, then with binary MC, then MC with interpolation, and finally having both interpolated MC and square features intermixed.
Figure 1, 2, 3 and 4.