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

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.

• If you are interested in fast raytracing of volumetric data use a VDB data structure which produces shallower trees than octrees (less indirections to get to leaves -- like a B+-Tree) openvdb.org Also nVidia has a similar data stricture GVDB which is optimized for their GPU's :github.com/NVIDIA/gvdb-voxels/blob/master/… – wcochran Jun 12 '19 at 18:13

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.