Definition
An octtree is a hierarchical subdivision of space in which:
- each node of the hierarchy corresponds to an AABB;
- leaf nodes store the primitives in the corresponding AABB;
- internal nodes have 4 children (in 2D) or 8 children (in 3D) of identical shape:
- the union of the AABBs of the children is equal to the AABB of the parent;
- the AABBs of the children intersect only at their boundaries.
The hierarchical structure is shown below. Leaf nodes usually contain fewer than some fixed number of primitives.
Note that a primitive is usually stored in many leaf nodes.
Ray Tracing with Octtrees
A ray traverses an octtree depth first and stops at the first primitive intersection that it detects.
We start with the root AABB:
- If the AABB is a leaf, the ray is tested for intersection with all of the leaf's primitives. If intersection is detected, the stack is cleared and the closest intersection is returned.
- If the AABB is not a leaf, we determines which of the AABB's children are intersected by the ray. Those children are pushed onto a stack in order of most distant to least distant.
- As long as the stack has data, the next AABB is popped and we return to the first step. Once the stack has no data, we report that no intersection was found.
In the example below, the outer AABB is an internal node with four children. Three of the children are intersected by the ray. The child labelled 3 is pushed, then the child 2 is pushed, then the child 1 is pushed.
When child 1 is processed, it causes 1.2, then 1.1 to be pushed. When child 2 is processed, is causes 2.1 to be pushed. When child 3 is processed, it causes 3.3, then 3.2, then 3.1 to be pushed.
