Dev Blog #44: Voxelize This
Hey guys. This is Grim from NK here to tell you a little about how the voxel shapes in TUG are represented. This will get a little technical, so bear with me!
Many people try to think about voxels in terms of blocks. Blocks are easy to think about! Blocks can be either solid or air which are stored as 1’s or 0’s in data.
In TUG we have smooth voxel contouring that can represent a variety of shapes. Smooth shapes are hard to represent as blocks. Because there is no good way to tell if a block should be smoothed-over or not. We solve this issue by storing our voxel data as a signed distance field. A signed distance field is a grid of numbers that tells us the distance away from the nearest geometrical surface. A positive value means we are outside of the surface, and a negative value means we are inside the surface. Here’s an example in 2D for a circle:
Red values are negative (inside) and green values are positive (outside).
Each voxel is assigned a field value based on the distance to the center of the circle.
A signed distance field shape representation is convenient when it comes to adding and subtracting geometry from the world. To add another shape, we just have to take the smallest distance-field value from both shapes.
Notice how the field values outside the first circle have been replaced with the smaller field values of the second circle.
Removing geometry is also easy! All we have to do is negate the field values of the circle being removed so the inside (negative) field values become outside (positive) field values, and then take the largest field value. Adding and subtracting any shape is possible as long as a field function for the shape can be defined.
Now you might be wondering how a signed distance field is actually turned into triangles that can be rendered in-game. Remember that a surface sits where the field values change from positive to negative. We start by identifying the edges along voxels where there are sign changes.
After we have identified a surface edge, we have to find where the surface actually sits along the edge. Depending on the field values at the two edge end-points, we can place a point along the edge.
After these edges and points are identified, we use the surface-edge intersections to come up with a single vertex position for each voxel. We calculate a voxel vertex position by averaging together all of the intersection points.
There are more expensive techniques to place interior-voxel points more accurately (like Dual Contouring with QEFs), but we have opted for speed over accuracy.
Now that we have voxel points, we have to figure out how to connect them together into faces. This is done by connecting together points across edges that have sign changes.
You can see that the average points connected together do not perfectly represent the circle, but it is pretty close.
This process extends directly to 3D except that the squares are cubes, and that a cube edge has four voxel neighbors instead of two. Across these edges we connect all 4 voxel neighbor positions together to form two triangles.
I hope you have an idea about how geometry in TUG is represented underneath the hood. I hope you’ve enjoyed my overview!
If you have any questions, feel free to send me a message on twitter @NKGrim.
Don’t forget to check out the latest “In The Works” video on Creative mode rework.