The Octorial: Part 3

Having still not turned the octree into something actually useful yet, I'll explain in this entry how to give it the functionality it needs to provide useful information once it has been built. This more or less boils down to querying the octree for objects that intersect a given arbitrary volume. For instance, to resolve collisions, each object can query the octree for objects within its own bounding box (or more precisely, within cells that touch said bounding box) and perform precise collision detection for each of those rather than for every other object in the world.

To start off, first it needs to be possible to determine whether a given cell touches a given bounding box. As I mentioned before, it's a simple task to treat a cell as if it is itself an axis-aligned bounding box: the box is a cube with the same center as the cell and an extent along each axis equal to the scale value that cell has stored. Collisions between two axis-aligned bounding boxes are covered in detail in various other places, so I won't bother reinventing the wheel here.

With the ability to quickly evaluate whether a cell touches a bounding box, extracting cells from an octree that touch said box is roughly a breadth-first search:

1. Start with the root node of the octree - the first cell within which all other cells are contained
2. Create a list of results
   
3. Create a queue of cells and add this root node to that queue
4. Start a loop that repeats as long as there is at least one item in the queue:
• Remove the first cell from the queue and see if it touches the given bounding box
• If it does, and it has children, add all of its children to the queue
• If it touches the box and does not have any children, add it to the list of results
5. When the queue is empty, i.e. all cells have been removed from it, every leaf node (cell with no child cells within it) either did not touch the bounding box or is contained in the results list.

The above in pseudocode form:

Touches(box (axis-aligned bounding box)):    returns a boolean value
    Define an axis-aligned bounding box based on this Octree's center and scale
    Return whether the two bounding boxes overlap (the actual amount of overlap need not be calculated)

OverlapBox(box (axis-aligned bounding box)):    returns a List of Octrees
    allocate result (List of Octrees)
    allocate queue (Queue of Octrees)
    queue.Enqueue(this Octree)
    while queue is not empty:
        allocate current Octree reference
        current = queue.Dequeue()
        if(current.Touches(box)):
            if(current has children):
                for each child Octree in current.children:
                    queue.Enqueue(child Octree)
            else    add current to result
    return result

And here is a visual explanation that hopefully makes some sense:

Despite the seeming complexity and number of steps, this technique can end up taking much less time than the "brute force" approach of examining every object. It can even be done many times in a single frame in a real-time environment:

Due to the orthographic camera projection and view directly down the global Y axis, the octree looks like a quadtree in this animation, but is in fact fully three-dimensional and composed of cubic rather than square cells.

In this animation, a yellow cube passes through an octree containing a cloud of 1000 small objects while querying the octree every frame for which objects it might intersect. Every cell that the cube touches is outlined in red, and lines are drawn linking the cube to each potential obstacle.

Note that it is not only the cube that has the potential to touch multiple cells at once - even despite their small size, the obstacles can intersect multiple cells as well, so it is important to check both the occupants and the visitors of each cell in the results. Above, yellow lines denote objects assigned as occupants and green lines indicate visitors that intersect one or more of the result cells despite not being assigned as occupants of them.

With the ability to search the octree for cells and objects within a specified volume, a variety of tasks become available for optimization using this octree. For instance, in a game about building things (or a procedural generator) it is possible to check for space before inserting an object without having to perform a large number of precise collision checks. An AI could use the octree to find targets within a certain range. A level loading system could use the player's location within the octree (or a quadtree) to load more detailed scenery near the player while using less detailed representations in cells further away. Space Engine and Kerbal Space Program, which I've mentioned several times on this blog, both rely on quadtrees for planetary terrain, and Space Engine uses octrees for organizing and loading procedural stars and galaxies.

Octrees have also been gaining visibility as the basis for Sparse Voxel Octrees, but that's a topic that, while fascinating, I myself have barely begun to grasp, let alone something I've tried to implement to date, so for the time being I'll leave that topic to the experts.

Hopefully this series has demystified some of the details of actually implementing an octree in your own projects, why it could be useful, and how its underlying logic works. I'm eager to hear any feedback on parts I could explain in more depth or may have overlooked.