Stone Devlog: Volumetric Voronoi Cell Subtraction

Show and tell time! It occurred to me that the logic behind the original algorithm we used for Voronoi shattering could also be used applied to my new volumetric approach. As a result, I was able to throw together a quick and dirty implementation of Voronoi cell subtraction. Check this out:

A cube with subtracted portion

I only spent the last year or so trying to implement mesh-based subtraction. This took the better part of an hour.

Alright, so how does it work? To recap, our original algorithm took the Voronoi cell and expanded each face into an infinite plane. It then categorized the vertices of the target mesh based on whether they lie on the positive or negative side of the plane, based on that plane's normal. The algorithm also split edges at their intersection with the plane and filled the hole, but that is unimportant for this discussion. What does matter is that by iterating through each face of the cell, the algorithm gathered up the vertices of the mesh that were inside the bounds of the cell.

To find which side of the plane a vertex was on, we found the distance between that vertex and the closest point on the plane. In the algorithm, we only cared if the distance was positive, negative, or zero, but that distance was available if we needed it. That makes it a signed distance function!

In my last post, I mentioned that I could represent simple shapes, such as cubes and spheres, with signed distance functions (SDFs) and combine them with boolean operations. Since I can also represent planes with an SDF, that means I can represent a Voronoi cell (or any concave shape, really) as the intersection of multiple planes. When I sample points from a uniform grid, I can then determine where each point lies in relation to the surface of the cell. I can then extract the surface from the SDF using one of many different algorithms.

Voronoi Cell (Left) and triangulated SDF (Right)

Please excuse the weird, jagged edges. They are a result of the resolution of the sampled space. By cramming more test points into the same space, the quality of the triangulation will improve... at the cost of performance. You may also have noticed (if you look past the jaggedness) that the edges are sort of rounded. That is due to the triangulation algorithm I used. An implementation of Surface Nets, in this case, but many of the algorithms I've looked at recently, including Marching Cubes, have a nasty habit of beveling sharp corners. That's something we will address in the not too distant future.

Anyways, once I was able to represent a Voronoi cell as the product of SDFs, I was able to apply boolean operations between the SDF product and that of other shapes. The result was an inexact and inefficient, yet working implementation of the Voronoi cell subtraction I've been pursuing for so long.

The cube after each Voronoi Cell is subtracted

Once again the corners are not sharp, so the removed shard would not fit perfectly with the core. This is evident in the first image of this post. Even still, this is progress. Each of the above subtractions could be the result of striking that cube and breaking a chunk off. As it stands, I could start implementing the knapping system gameplay, albeit with some serious hangs as each shard is removed. I won't jump the gun like that, but it's nice that we are actually getting somewhere. I'll start ironing everything out, and soon we will start working on something playable.