Stone Devlog: Volumetric Approach

 As my work on cutting Voronoi cells out of a stone's mesh has once again been drawing me dangerously close to 3D boolean operations, I decided to take a step away and try a different approach.

When I was initially figuring out how to implement the grander stone knapping system I had envisioned, I briefly considered a sort of voxel-based approach. The thought was to have a blocky stone mesh made up of cubes, a la something out of Minecraft or Cube World. I didn't really want to make a blocky game, though.

Enter the marching cubes algorithm. I was only vaguely familiar with the algorithm and its 2D analogue, marching squares, primarily for its application with tilesets, terrain, and metaballs. However, I had never actually implemented or used either algorithm myself. As is tradition with this project, I skipped the training wheels and went straight for the more complicated 3D version.

Marching cubes. Neat.

There are plenty of better explanations of the algorithm around the web, so I'll keep this brief. The gist is to take a 3D grid of vertices, form cubes, then create a triangulation within each cube. This is done by interpolating along the edges of the cube using an arbitrary scalar value assigned to each vertex, checked against some threshold. In its simplest form, a vertex can either be "off" or "on", 0 or 1. For the two vertices that form an edge, if the value of one is 1 and the other is 0, the interpolated point that is used in the triangulation is smack dab in the middle of the edge, between the two vertices.

Such depth

Truth be told, there wasn't much that I actually needed to do to implement the algorithm. Great resources already exist that have tables containing all 256 possible configurations, based on which vertices are above and below the threshold. I grabbed one, used the code as a reference, and then all I  needed to do was provide the algorithm with a grid of vertices and their respective values.

Just pretend it's a bit more "rocky"

When that was done, I set up a basic UI that allowed me to click away vertices in the grid by setting their value to 0 and regenerating the triangulation. Funnily enough, this is fairly similar to what I had in mind for the original version of the knapping system, long before my ambitions set me on this wild ride. Currently, the system is more or less binary, with the value of a vertex either being 0 or 1, and the triangulation is subsequently blocky. However, by using a wider range of values and adjusting the threshold, smoother geometry can be formed:

I'm not totally sold on this approach yet, but it definitely shows promise. There are a lot of pros and cons to discuss, as well as my reasoning for not taking this route initially. We'll cover all that next time.