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:
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.
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:
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:
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)
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:
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:
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.
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.