Represent an octree as a binary tree of thrice the depth?

Question

In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as bit-mask that stores which children are used and a pointer to the first child. The children are stored consecutively then.

I'm interested in ray-tracing of sparse voxel octrees, so finding the first intersecting leaf with a ray is the main operation on the tree.

To simplify current implementations, I wonder whether it would make sense to represent an octree as binary tree that at each node bisects the space exactly in the middle. The depth layers would alternate between the three possible orientations of the cutting plane. So three levels of the binary tree correspond to one level in an conventional octree.

1. YZ-plane (root)
2. XZ-plane
3. XY-plane
4. YZ-plane
5. ...

This is similar to the idea of k-d trees, which are binary trees for space partitioning as well. However, they store cutting planes with the nodes to allow for uneven partitioning.

Is there a difference between the octree and a binary tree of three times the depth, or are they equivalent? If there is, why is the octree used more commonly? I haven't found any reference of someone using the explained binary tree for space partitioning. Maybe I'm just missing the correct term for it though.

Answer 1

They're very similar, as you say. Their asymptotic running time is equivalent; the difference in running time and space usage is at most a small constant.

However, in practice, constants can matter. In practice, the octree might perform better, due to its better memory locality. If the depth of the octree is $d$, the depth of your corresponding binary tree will be $3d$. That means looking up an element requires three times as many pointer indirections in your binary tree. Pointer indirections are expensive because they typically cause a miss in the cache (they cause random access to memory, which is the worst case for memory hierarchies). Consequently, in practice, it's possible that the binary tree implementation might be up to three times slower than the octree, due to the increase in cache misses and the poorer memory locality.

Of course, the only way to know for sure is to implement and measure on some benchmarks. But this is one plausible reason why octrees might be preferable in practice.