Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top