Fast Voxel Data Structures

Voxels are a promising alternative to conventional rasterisation. If managed right they allow for huge worlds, mass editing and fast ray tracing. I'm going to teach you how to use the best data structures for managing your voxels.

I'm going to go over all the most common voxel data structures, how they work and their advantages and disadvantages. I won't go too in depth into each data structure but rather help you figure out what data structure is best for you. One other thing to note is that the terminology to do with voxel data structures is quite inconsistent within the community, so I'll be using the terminology I see the most.

tldr

Flat Grid

A flat grid is the simplest way to store voxels. It's exactly what it sounds like, a grid of voxels. A basic implementation would look like this:

let voxel_grid = [[[Voxel; X_SIZE]; Y_SIZE]; Z_SIZE];

Usually though it is implemented as a flat array for performance reasons:

let voxel_grid = [Voxel; X_SIZE * Y_SIZE * Z_SIZE];
let voxel = voxel_grid[x + y * X_SIZE + z * X_SIZE * Y_SIZE];

While it is very fast to edit it has some drawbacks. The first is that the memory usage grows very fast (n³) giving an upper limit on how much of your world can be loaded at once. The second is that it is slow to traverse as you have to look up every voxel along the ray.

Grid Hierarchy

A grid hierarchy is quite similar to a flat grid. It's different in that you have multiple flat grids at different resolutions. At the bottom layer you have the same flat grid as before. You then have grids of lower resolution that only contain a single bit per voxel that indicate weather there is a voxel in the grid below. When traversing a grid hierarchy you can use the lower resolution grids to skip over large areas of empty space. This gives a very similar ray traversal to an octree but without any pointers allowing you to do a lookup for every layer at once making it much faster than an octree.

A grid hierarchy is not sparse, so its memory still grows at n³, but it is much faster to traverse. It is also very fast to edit as you only need to set 1 bit per layer, and you can set them all at once making it GPU friendly. Grid hierarchies are so fast to create that I can rebuild the whole hierarchy every frame when using a small world. They also are only slightly bigger than a flat grid so all in all they are a great improvement over a flat grid.

Octree

So what if you want to load more data? Both a flat grid and a grid hierarchy grow at n³, so you will run out of memory quite quickly. The solution is a sparse data structure. The most simple sparse data structure is an octree. An octree is a tree where each node has 8 children. The root node represents a cube containing the whole world. Each child then represents ⅛ of the parent. This continues until you reach a leaf node which represents a single voxel. A simple implementation of an octree would have nodes that look like this:

struct Node {
    children: Option<[Node; 8]>,
    voxel: Option<Voxel>,
}

Each node stores its 8 children until you get to the bottom of the tree where instead of storing its children a node stores the voxel data. But this isn't great for performance. A better implementation is to store the octree in an array. Now each node is represented as a u32 that either stores the index of its 8 children or some voxel data. This makes it a lot easier to edit and allows you to easily send it to GPU.

struct Octree {
    nodes: Vec<u32>,
}

An octree looks like this (represented in 2D):

The advantage of an octree is that it greatly reduces memory usage. As you can see in the picture above, the octree doesn't store the entire top left quadrant of the world as there is nothing there. The disadvantage is that it is much slower to traverse. To access a particular voxel you have to traverse down the tree using the children pointers. But if you want a large world a sparse data structure is a necessity. It is possible to use a hash map for faster access to the nodes, but this uses more memory and is not very GPU friendly.

Sparse Octree

A sparse octree is an octree, but each node doesn't have to have 8 children. Instead of just storing a pointer to all 8 children it stores an index and a child mask. The child mask is a bit mask that indicates weather each of the 8 children exist. The child pointer then points to however many of those children exist.

A sparse octree can use up to an eighth of the memory of a normal octree without losing any performance, so it is a nice improvement.

Brick Map

The implementation of a brick map is a bit out of scope, but you can read the paper here. As a brick map has LOD you can do voxel cone tracing for fast global illumination. It also can be streamed in and out allowing huge worlds to be rendered. But due to the hierarchical nature it is still relatively slow to edit.

SDF

A voxel SDF is a flat data structure where every air voxel stores the distance to the closest solid voxel. This is the fastest data structure for ray tracing allowing the most space to be skipped and only taking 1 lookup per DDA step.

Conclusion

As you can see, there are many voxel data structures for different purposes. I've summarized the results in this table:

The best data structure is usually some combination of datastructures. For example I use a brickmap with a grid hierarchy in alex. You could then have another acceleration structure for doing physics and a different datastrucure for writing to disk.