Stone Devlog: The (Surface) Implication

It has been a while since my last post. Truth be told there hasn't been a whole lot of progress in that time. When we last left off, I was investigating methods of extracting a surface from volume data. It offered significant advantages compared to my previous approach of operating directly on a polygonal mesh. Namely, it would be much simpler to implement the knapping system by subtract volumes from each other, then generating a mesh, rather than trying to subtract meshes from each other. However, one of my big requirements is the preservation of sharp features. The edges of our spearheads and whatnot need to be crisp and razor-sharp, not the jagged mess we saw with the Voronoi cell last time. Turns out this is a lot to ask for.

Most of the algorithms we've looked at thus far only generate vertices along the edges of cells in a grid. This means that edges and corners that align to the grid will look fine, everything else ends up beveled. This was observable in my last few posts. Some cubes looked sharp, while others did not.

A cube offset from the grid (left) and aligned (right)

We certainly cannot rely on our objects aligning to a grid, so we need a new approach. Thankfully, there are several algorithms that include sharp feature preservation, such as Dual Contouring, Extended Marching Cubes, and Cubical Marching Squares. Unfortunately, that feature preservation is fairly complicated. In fact. most of the sample implementations I've seen skip out of this portion of the algorithm. There are research papers explaining these algorithms in many, many words, but not much code to be found.

The core idea is to calculate the surface normals at the points where the surface intersects the cell edges, then use those normals to project the surface into the cell in order to create vertices for sharp features. In the case of Dual Contouring, the basic idea is to create planes from those intersection points and their corresponding normals, then find an acceptable point within the space that the planes intersect. And then you have to decide what to do if that intersection point lies outside the cell. Plus, you have to hope that there is only one feature inside the cell, because that's all you're getting. If you want more, you can check out some other other research paper instead. And so on. It's been a headache looking over pros and cons for these algorithms, and I've yet to find a fully functional implementation that I can try out before I commit to one.

Cubical Marching Squares seems to be all the rage in many of the voxel-fanatic circles across the internet. On paper (pardon the pun), it seems to have everything I need and the ideas behind the algorithm are pretty clever. The paper even includes pseudo-code, rather than consisting solely of 10 pages of mathematical jargon. Maybe we'll talk about it soon if I can get something working.