Next-Gen 3D Rendering Technology: Voxel Ray Casting

The Advantages Of Sparse Voxel Octrees

Now let’s look at the advantages of our voxel octree when it comes to rendering. The main advantage of this data structure is that it provides an elegant way of solving the problem of level of detail (LoD) in textures, but also of geometry--all with a single algorithm. That’s because, as we implied in the preceding paragraph, each node of the octree contains color information, and so we can do away with 2D textures as we know them. Or, to be more precise, the octree is both the texture and the geometry.

Consequently, the level of detail problem, which had to be managed in a totally independent way for the geometry and for the textures, now amounts to one single system: managing the level of detail of the octree. And it turns out that this can be done very simply. In a way, the principle is an extension of the mipmapping used for textures. The purpose of mipmapping is to try to conserve texels (texture elements) of the closest possible size to that of a pixel. To do that, several resolutions of the texture are pre-calculated and stored, and the hardware adapts the choice of the mipmap level to the size of the texture on the screen.

Something like this can also be achieved with voxel octrees, with the choice of level of detail made dynamically. As soon as the size of a voxel is less than the size of a pixel, the ray’s traversal of the octree is halted at that level. All that’s needed is to store the average of the information contained in its children in each node and you have a very simple way of managing LoD. This mechanism is perfectly suited to a streaming system, which is a little like the one id Software already uses for its MegaTextures. Only those portions of the octree that are needed are stored in video memory, with another part in main memory to accelerate subsequent accesses. But the great majority of the octree simply remains on the storage medium.

The result is that we have an almost unlimited quantity of geometry (and of textures, as we noted). The octree can be as detailed as we want, and at run time the quantity of memory and the display time remain (relatively) constant. The only limitations are the amount of time the artists can devote to creating the octree and the physical limitations of the storage media in the next generation of computers.

We should say that there are other possible ways of addressing these issues, such as with the use of virtual-texture systems like MegaTextures or sparse virtual textures, which will be built into the major 3D engines (CryEngine 3, idTech 5, etc.) next year. Geometry is a more complicated problem to solve, but several possible solutions are afoot. The simplest of these involves pre-calculating several versions of a mesh at different resolutions and selecting the one that best fits the distance from the mesh to the camera. This basic solution is easy to implement, but a significant amount of visual artifacts are created when moving from one level of detail to another.