Voxels, sparse octrees, virtualization

July 25, 2008

Graphics

approximately 3 minutes to read

Recently, I was blogging about virtual texture mapping, which is a method to solve texture budgeting problems. Back then, John Carmack was also talking about raycasting into sparse voxel octrees, to render an infinite amount of geometric detail. Let’s take a look what this is about, complete with an overview of current research papers on this topic.

Voxels

Voxel based graphics are by no means a new idea. For those of you who remember games like Outcast or Comanche, well, these were voxel-based. Basically, a voxel is a small block, similar to Lego block. A pretty good explanation is available at the Wikipedia.

Usage

Well, voxels alone are not that interesting, because for any reasonably detailed modeled, you would need extremely huge amounts of voxels (if using an uniform grid). So, a hierarchical system is needed, which brings us to octrees. An octree is a very simple spatial data structure, which subdivides each node into 8 equally large subnodes. A sparse octree is an octree where most of the nodes are empty, similar to the sparse matrices that you get when discretizing differential equations. One problem I see is that no DCC tool is built for voxel modeling, so triangle meshes (including their texture) have to be “baked” into a voxel structure. This does have an advantage though, as the geometry and texture information is stored in exactly the same data structure.

For rendering, a sparse octree does have a few advantages, as it is quite easy to handle level-of-detail (just stop at a higher level of the hierarchy), streaming in of data is pretty simple (as it is totally uniform. You just stream in new “block”), and it gives a very high level of geometric detail. Jon Olick – from id Software – is going to give a presentation of their approach at this year’s SIGGRAPH. Basically, they are going to use the voxel structure for all static world geometry and polygons for dynamic objects and characters; however, they are also evaluating doing dynamic characters with voxels (for sources, see the announcement on OMPF and some discussion about it on Beyond3d). There is obviously even some company in Australia working on a voxel based renderer now, called Unlimited Detail, which is not yet public. For information about this, check out this article about their renderer.

Plus, there has been quite some research into this. The following papers seem relevant for this topic (updated as soon as a new one crops up):

An interesting tid-bit is that ATI has been using voxel based rendering for their HD4870 demo. At least, they used technology from a company called LightStage, check out this video at youtube for a look at their stuff.

All in all, pretty impressive stuff. However, there is currently no DCC tool which can work with voxels, meaning each engine that wants to use voxels, has to bring in own tools to convert triangle based geometry to it. There is also little support for this from the API side (DX10 and OpenGL are primary based about rasterizing, they are not designed to support mixing different rendering algorithms). And finally, I’m still not convinced that voxels are the way to go. Tessellation of higher-order primitives, together with displacement mapping, seems at least as promising to me, and it has the advantage of being production proven (just go to the cinema to see the results of it).

Update: Added link to the SIGGRAPH presentation from Jon Olick about voxel rendering.

Update 2: Added link to a paper about perfect hashing.

Update 3: Added an article about the renderer used in the Ruby demo.

Update 4: Add link to the 2010 efficient sparse voxel octree paper & source code.