Stone Devlog: Volume vs Boundary Representation

 Alright, let's talk a bit about how to represent geometric figures.

Up to this point, I've been working with a Boundary Representation (B-rep) in one form or another. A B-rep defines a solid by its surface, the boundary between what's 'inside' and 'outside'. My polyhedron and DCEL structures are both examples of B-reps. They use vertices, edges, and faces to define a shape. Because the shape is a closed web of edges and faces, everything inside is inferred to be solid. This is an easy representation to wrap your head around simply because the data and the visual elements are one and the same. What you see is what you get. However, this is also where the trouble begins for what I'm trying to accomplish.

The main issue with an implicit interior is the fact that the interior is implicit. It doesn't actually exist. Peel away any part of that surface and you'll find the inside is hollow. The onus of maintaining the interior falls on the operations modifying the surface. And, since the operations are directly modifying the data used for rendering, the slightest error in any of those operations leads to errors in the final mesh (e.g. holes, overlapping faces, etc.). Then those slight errors snowball on subsequent operations.

The volumetric representation flips all of this on its head. Instead of the surface being defined and the interior implicit, a volumetric representation (such as with voxels) defines the interior of a shape, while the surface is implicit. The data dictates what's solid, from which a surface is generated. Operations are performed on the data, then the surface has to be regenerated. In theory, bad data may make a wonky mesh, but that mesh should not be invalid. As an added bonus, compared to B-reps, voxel data is a lot easier to manipulate.

A blocky showcase of the different boolean operations on two spheres

In the above picture, I created two spheres, applied boolean operations to the spheres, then created a mesh from the points inside the final shape. From left to right, we have Union (A OR B), Intersection (A AND B), Subtraction (A NOT B), and an inverted Subtraction (B NOT A). In this case, the spheres were created by sampling points from a signed distance function: the distance between the sampled point and the sphere center, minus the sphere radius. This function returns a signed value based on the distance to the surface of the sphere, positive for outside, negative for inside, and 0 for points lying exactly on the surface. The various boolean operations are applied simply by returning the minimum or maximum of the two sphere's functions. For instance, the intersection is simply the maximum of the two functions. The positive (exterior) values for either function end up being returned for almost every sampled point, except for where the shapes overlap and both functions return negative.

When I wrapped up my last post, I had intended to write a pros and cons comparison between B-reps and volume representations. I planned to explain my reasoning for pursuing B-reps initially and what turned me off using voxels. After putting in a bit more research and getting further in one weekend than I had in the past year or so, I decided to take a different direction with this post. Voxels are cool, and I probably should have gone this route from the start. 

EZ-PZ CSG

Above is the product of a sphere subtracted from a cube joined with the intersection of a sphere and a cube. Quite the mouthful, let's just focus on the output. Realistically, I only actually need subtraction for the knapping system, but all the boolean operations essentially come for free with this sort of representation. We'll talk more about implementation details and where to go from here in my next post.