Sparse Voxel Octrees for Realtime Raytracing!

So I’ve been doing research on sparse voxel octrees off and on for about a year now. The more I look into using them, the more practical they become. After recently generating the first render with my current sparse voxel octree implementation, I’ve gathered a fairly clear understanding of why they’re such a practical approach. That said, I’m going to use this blog post to kind of outline my experiences with the technology.

One of the biggest benefits of this technology is the level of detail that it allows. Because everything is effectively treated as a sparse 3D texture, you get all of the benefits of standard 2D texturing. Like regular textures, they’re very suitable for streaming. They also have implicit level-of-detail through the use of mipmapping. That said, the end result is completely unique 3D texture data everywhere, and the amount of detail you can render in a very short period of time is quite astounding (I’ll post some screenshots/video within the next few months to back up this claim =) ).

Another major benefit comes from the fixed maximum render time. When ray-casting for the primary ray hit, there is a maximum number of steps you need to take in your 3D DDA (3D DDA stands for 3D Digital Differential Analysis and is simply a fast way to traverse through all voxels intersected by a ray in the order that they’re intersected). In my current implementation, for a 90 degree field-of-view, there is a maximum of 3,840 steps required in my 3D DDA. This allows me to guarantee a minimum-case performance! Rasterization certainly can’t guarantee that!

One major drawback of this technology is the lack of research available. NVidia released a great paper called Efficient Sparse Voxel Octrees. Id has also released some research along with a video that demonstrates the tech in action. However, none of the research that I’ve found covers the practical implementation details. That said, I find myself implementing a lot of things that I don’t really know if they’ll work or not, but I suppose that’s just the nature of research.

One thing that I’ve found that really helps me in terms of my mental model, as well as my code, is dividing the sparse voxel octree into two different octrees. For me, I have one sparse octree (a resolution of 1024^3) that represents a high level node partition of my scene. I call this octree the “indirection octree”. At each node in the indirection octree, I have a pointer to a “brick”. A brick is a sparse octree of size 128^3 whose leaves represent a voxel in the 3D texture. While this complicates my tree traversal somewhat, it makes management and streaming *MUCH* easier. It also allows me to implement some interesting high-level optimizations, such as a coarse DDA that I can then use to adjust the LOD sooner, and therefor take far fewer 3D-DDA steps overall.

Overall, I find working with voxels to be extremely fascinating. It’s quite a challenge, but the results are pretty interesting. Given my current results, I definitely think that this technology can utilize low-end PC graphics hardware. I’m also holding out hope that this can run at interactive rates on a high-end desktop CPU. I’ll be sure to post more info when I get it! Watch out for a video in the next few months as well!

Advertisement

~ by ebray99 on July 26, 2010.