Ray / Octree traversal: Parametric Algorithm

I’m implementing my current ray-octree intersection algorithm using an adapted version of the Revelles 2000 paper An efficient parametric algorithm for octree traversal, and after some painstaking debugging, I think I found a bug in the paper’s text. which seems to be acknowledged in this 2005 google groups discussion as well.

In table 1 on paper 4, on the discussion of extending the quadtree algorithm to octrees, there’s a table of comparisons needed to select the first node. The selection is implemented using bitwise operators. The error is that for operations concerning the z-axis, the rightmost bit must be altered (0), and not the leftmost (2), since that’s for x-axis operations. Switching 0’s and 2’s results in the right table.

Now there’s three days of my life I will not get back. One could argue that this all depends on the way you arrange your bits, but I suppose it’s universal standard that we read the rightmost bit as the indicator for 1^2 – also, in the rest of the paper, this convention is used.

Anyhow, onwards we go!

Leave a Reply