Ray / Octree traversal

Since the basic work on my voxel raycaster is finished (Crunching voxels with 3D DDA – generalized Bresenham – in a 3D array), it’s time to start looking at hierarchical structures and the methods of switching between several Levels of Detail, which is the direction my PhD will be heading in.

Most literature seems to point to an Octree as the most suitable structure for a voxel grid. If you store the parts of the grid that are empty as null pointers, you get a Sparse Voxel Octree (SVO), which everyone is raving about at the moment. Most people have seen the Jon Olick (from Id Software) tech demo by now, but it’s interesting to notice that this technique is nothing new – there are papers from the nineties already explaining algorithms to trace rays through sparse octrees, for raytracing purposes. The fact that instead of storing polygons, you’re storing actual fixed-spaced data points now is a detail, for me.

I’ve already figured out that there are two kinds of algorithms for ray-octree intersection: bottom-up, which works from the leaves back upwards, and top-down, which is basicly depth-first search.

I’ve already found Revelles’ algorithm from 2000, called An efficient parametric algorithm for octree traversal, which looks interesting, but is quite old. This is a top-down algorithm. The most popular bottom-up approach seems to be K. Sung, A DDA Octree Traversal Algorithm for Ray Tracing, Eurographics’91, North Holland-Elsevier, ISBN 0444 89096 3, p. 73-85. Problem is that most DDA Octree traversal algorithms expect the octree to be of equal depth, which is what we don’t want – we want those trees sparse.

In the more recent literature about Sparse Voxel Octrees I’ve managed to read through, (most notably Laine’s work on SVO’s), they all seem to be based on some kind of GPU-implemented version of DDA (Amanatides/Woo style).

I’ll be working my way through some basic papers about octree traversal next week and start coding as soon as possible, since that’s obviously the best way to learn how these things work.

Leave a Reply