Octree Traversal

This post describes a Least common ancestor based Octree traversal algorithm.

Some definitions:

Let us define the concept of 'Wall Owner'. A node is said to "own" a wall, if the wall was created while splitting the node for the first time. Formally,

A node has 6 walls surrounding it. Let us call these as "External Walls" of the node.
When we split a node "n" into 8 parts, we create 3 new walls inside this node. These walls are "Internal Walls". The node "n" is said to be the owner of these walls.

Nobody owns the external nodes of the root. ie: Owner is NULL.

For each child node, three of its walls are owned by the parent (the internal walls).
The remaining 3 walls are External walls of the parent. Who owns these walls? We know this info by asking the parent.

When a ray originates in a leaf node of the octree, we can trace it as follows:

Let the ray hit a wall "W". We know who the owner of this wall is.
We find the intersection point of the ray, on wall W, and slightly advance the ray (by a delta increment), so that the frontier of the ray is now just outside the node.
We now ask the Owner of W, to tell us which leaf node contains this point.
[ This is the improvement that least common ancestors gives us. Otherwise, we would have to traverse each time from the root node ]
Now we just say that the ray originates in this new leaf node, and continue the process.

This is like a 3D line drawing algorithm for an octree. Note that it also works for other non-uniform space partition techniques like KD-trees (there, we have only 2 children per node, hence only one internal wall per node)

It increases the space requirement by 6 pointers per node. We can reduce this to 3 pointers per node + 3 bits (to identify what position each child is in its parent: 0 to 7), because the 3 internal walls need not be stored. The parent is trivially the owner of such walls.

Relation to Naive Octree Tracing:
The algorithm described above can be converted to the naive algorithm, by simply setting the root as the wall owner for all walls. This means, every time we move from one leaf to the neighbouring leaf, we need to traverse the octree from the root node all the way down. If the depth of the octree is large, this can be a significant overhead.

What this new algorithm brings to the table, is the promise of reduced octree traversal overhead. When we move from one node at level 10 to another node at level 10, there is a very low chance of traversing all the way from the root node. We may just go from a level 7 or level 8 parent, back down to level 10. In my experiments with max depth = 10, I have observed 10% to 20% speedup using this algorithm (see the table in previous post).

Memory issue:

The first most obvious drawback is that of extra memory usage. For my test scene (empty Cornell room) consisting of 320,000 points, with a setting of maxdepth=10, and maximum points per leaf = 10, 309,623 nodes were created overall. This means that 0.3 million nodes * 6 walls per node * 4 bytes per wall = 7.2 MB of additional memory was used. The total memory requirement of each octree node is currently 100 bytes (a lot of optimization is in order), of which 24 bytes are due to the walls. Thats almost a factor of 25% increase in memory requirement. We can reduce this to around 13% using the optimization of storing only 3 wall pointers (as described above), in which case the 10-20% speed improvement is at the cost of a 13% memory requirement increase, which may be justified. Of course, using only 3 pointers will add to the number of conditional statements and make the solution a little inelegant, but it just may be worth it. Further tests with larger datasets may swing the argument in favour of this new algorithm.

A fly in the algorithm:
In some situations, the algorithm described above skips a few nodes along the traversal path. How can this occur? Here is a diagram explaining the issue:



This image shows a step in traversal of the octree. We hit the wall of a node (green circle denotes point of intersection), and now want to know which node to traverse next.
To do this, we move a little ahead along the ray so that we get a point that is just outside this wall. We then ask the parent of this node, which node contains the point. In this case, the parent of this node says that the point no longer lies inside it, and so returns null. What we should do in this case is ask the root node where this point is. We could also go step by step upwards, asking the parent of the parent and so on, but I figured we would just waste time that way.