Monday, November 22, 2010

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.


5 comments:

  1. Oh.. the suspense :)

    Some part of me is hoping that the brute force method wins!

    ReplyDelete
  2. This post was interesting! Thanks! :D

    ReplyDelete
  3. You blog is really interesting, I've read it all.
    But I can't find (or maybe I've just missed it) the following post about this topic. Personally I vote for the sparse octree apporoach, because I think it is really promising. I've listen that it has problems with the marching cubes algorithm (not efficent while accessing neighbour voxels) but that shouldn't be a problem in your case! The main advantages, I've heard it has, are the efficient memory usage and the "easy" LOD calculations, is it right?
    I'll look forward your next post!

    ReplyDelete
  4. @Andrea: I ended up using a sparse voxel octree, but this is only to perform the adaptive isocontouring. The information this generates I store it as polygons.

    ReplyDelete
  5. Yes, after some more deep reading of your blog and of some comments, I've understand that you use the octree and that you use it only for storing the datas. It would be interesting to see the actual definition you use, what informations are in the leaf and so on... Maybe a future post? :)
    Also the Dual Contouring algorithm you have implemented with OpenCL seems really interesting, but I haven't yet grasped the details about it: I need to read some of the articles you have linked. Unfortunatly I know little about rendering tecniques and how the triangle mesh become such beautiful screenshots or videos it's mainly a mistery for me!
    But this is only a small part of the work you have done. The procedural generation that runs before this is amazing too! I'm quite surprised that any of the majors software house hasn't yet sequestered you and locked inside some cellar to take advantage of your work to build their next gen engine! If you will disappear in some near future, I really think that this will be the reason! ;)

    ReplyDelete