Space Warps and Octrees

When you think about voxels, the image you see in your mind is that of the evenly sized stacked boxes:

This arrangement gives equal importance to every point in space. In practice, however, space is not always that interesting. Actually most of it is either empty or entirely solid and thus impossible to see. If all space is not the same, why voxels should be?

If we could have only voxels in regions of interest, then we would save a lot of memory and processing time. There are two different techniques to address this.

The first is Space Warps. In homogeneus space voxels are perfect cubes. Each edge measures exactly the same. What would happen if we could place voxel corners anywhere we like?

While the total number of voxels did not change, they now cover the same space in a different way. Voxels in the center are smaller, voxels to the outside are bigger. Since the topology of the voxel grid did not change, it is guaranteed that the same algorithms that run in a regular grid will still run here. Marching Cubes and Dual Contouring, for instance, remain the same.

The advantage is that for the same processing cost and memory footprint, we now have more detail allocated to the voxels in the center. If we could pinch space around the features we consider interesting, and relax it around empty air or entirely solid regions, we would end up with improved triangle resolution at no cost.

The second technique is Octrees, to be more specific: Sparse Voxel Octrees. Sparse Voxel Octree

As we saw before, for most applications we are only interested in the surface of voxels. That is where things stops being solid and the empty space begins. Octrees are ideal for representing that. 

Above all an octree is a way to divide space. You start with a box, which would encompass everything you want to represent. If you need more detail in the box, let's say a surface is going trough it, you then divide it into eight boxes. Then you look at each of the boxes and you ask the same question again, is there any detail in here. If there is, you break the box into another eight smaller boxes and ask the question for each one of them.

Eventually you will have a lot of small boxes in the regions where there is detail, and a few large boxes that contain only air or solid. 

You can use Quadratic Error Functions (QEF) to simplify boxes even more. If you find that the error of collapsing eight boxes into its parent box is small enough, you can just discard the smaller boxes. 

Each terminal node in the octree, a leaf, can  be considered a voxel. With little modifications, Dual Contouring can be run on those voxels. The main difference is that with a regular grid, Dual Contouring would run on every edge. Now with the Octree, some edges that belong to a larger voxel may also be shared by a smaller voxel. It must be made sure that only the small edges are considered.

The results are quite impressive. Instead of producing a surface that is evenly covered by triangles, you now see that areas of interest have a lot of triangles while flat and less detailed areas only have a few.

So which of these techniques did I choose to implement? It was not simple. I was not entirely happy by some distortions I was seeing in my tests with Space Warps. On the other hand, since I wanted to use OpenCL, I knew it would be cheap to compute many points at once, so a brute force method could end up being faster than using an octree. I was especially concerned about memory coherence if I moved the contouring to an octree.

In my future posts you will see which approach made the cut, and which one did not.