My dissertation is an investigation into voxel games and how different volumetric data structures can be used for optimisation. Voxel terrain has been used to produce unique games such as Minecraft or Teardown . However, storing the topology can be challenging as naive methods like using a 3D array requires a lot of memory and scales up quickly as the amount of topology increases.
This is where the optimisation techniques come in. First I implemented a Sparse Voxel Octree structure. Octrees are a spatial data structure that splits the space into 8 “Octants” these Octants have 8 more Octants, this means that large regions of empty space can be reduced to just one Octant. To search the tree, the query point is compared to the origin of the Octant to find out which side it lies on. However, Octrees have a few drawbacks, searching the tree requires a lot of computation compared to an array look up. They also cannot compress identical regions of space and have to be very ‘tall’ to represent fine details.
Volumetric Dynamic B+ Trees (VDB) do not suffer from these same issues, it uses a lot of very clever techniques to make look up and insertion of topology instant. Firstly, topology is stored as a series of bit masks which allows for bit-wise operations that are much faster than arithmetic operations. The tree also supports different amount of children at each node that means that the tree can remain ‘short’ whilst still being able to store lots of detail. Finally, the structure of the tree means that it can take advantage of the CPUs caches meaning traversing the tree is incredibly fast. I’m glossing over a lot of the cool stuff it does for brevity but if your interested checkout Ken Museths paper.
Here is a quick video I made for my viva presentation that visually explains how this project works: