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.

The Octorial: Part 2

I left off having explained how to build a basic octree, but having mentioned nothing about how to use it. In fact, what I detailed before is effectively useless! The octree can be filled up with objects, and they'll be organized into cells, but there is no way to identify which cell an object occupies (except by iterating through all cells) or to use the octree to reduce the workload during tasks such as collision detection. I'll get to that in time, but first there's an issue that becomes apparent when planning such tasks.

A tempting place to start is, given an object, to determine which cell it occupies and then examine its collection of occupants, but since objects are not single points but rather occupy a certain volume of space, if an object exists near the edge of a cell it may extend out of that cell so that part of it is inside a neighboring cell. Identifying which cell it occupies and then identifying all of that cell's neighbors seems like it would be a solution, but only under a certain circumstance - if there is no way for an object to reach from one cell all the way through another and into the one on the other side (Jan Michael Vincent can't be in two Quadrants at once). If an object can do this, that means that any object could collide with any other, regardless of which cells either of them occupy!

The gray blob shown here is so large that even though it is centered on the large black dot, it reaches out of the cell containing it and into nine other cells.

The situation seems a lot like the earlier situation I described that threatened to send my hypothetical approach back to square one, but not all is lost if the non-zero volumes of objects are considered when building the octree to begin with. When inserting an object into the data structure, one could consider its extents and mark every cell that it touches in addition to the cell it "occupies." Some way to determine whether an object touches a given cell is going to be needed anyway, so that functionality can be assumed to be available and referenced here. Here's a bit more pseudocode corresponding to the additions and changes necessary (anything not shown here is the same as before):

class Octree:
    
    List of visitors (objects that do not belong to this Octree but may extend into it)

    Insert(occupant):
        if occupant is non-zero in size (how to determine this varies based on the specific development environment) InsertBox(occupant's axis-aligned bounding box)
        else InsertPoint(occupant's position)
       
        allocate point (3D vector)
       
        InsertPoint(position (3D vector)):
            point = position
            InsertPointRecursive(this Octree)
       
        InsertPointRecursive(current Octree):    same as before
       
        InsertBox(box (axis-aligned bounding box)):
            InsertPoint(box's center point)
            for each cell (Octree) returned by OverlapBox(box):
                add occupant to cell's visitors List

    OverlapBox(axis-aligned bounding box):    returns a List of Octrees
        return all Octrees that the given bounding box touches

In other words, each octree cell will now keep a second list of objects that refers to all objects that extend into its assigned volume even if they are not occupants assigned to it. When a new object is inserted, it will be added to this list for every cell that it intersects. For the time being, this is determined using an axis-aligned bounding box for simplicity, since intersections between axis-aligned bounding boxes are very simple to compute and the octree cells happen to be equivalent to axis-aligned bounding boxes already.

These lists of visitors also need to be addressed when a cell splits. Each of its new children will have to be checked for whether any of the visitors touch it and, if so, have that visitor added to its own list of visitors:

 Split():
    Do the same operations as before
    
    if there are visitors:
        for each child Octree in children:
            for each visitor in visitors:
                if visitor is touching child    add visitor to child.visitors
    optionally clear the list of visitors

This may seem like a lot of redundant data. In a sense it is, insofar as many references to any given object may exist in the octree, but this is part of a tradeoff of memory footprint for performance. By encoding more information about how the objects in the octree are related to its structure, it becomes possible to make more intelligent decisions later on when using the octree, thereby avoiding redundant work and saving valuable time. As of today, modern computers tend to have huge amounts of memory available and relatively little extra time for extraneous computations in situations such as games or other real-time simulations.

Now I did just make a lot of mentions of some way in which, given a bounding box, all of the cells touching it can be found, but not how, specifically, that gets done. Unfortunately I think that will require a third entry in this series, so look forward to that.

The Octorial: Introduction

My predilection for procedural generation and the underpinnings of large game worlds has led me to encounter the concept of an octree time and time again, to the point where I started to feel weird being so familiar with others' implementations without ever having cooked up my own. Naturally I started by looking for tutorials and reference implementations, but with limited success (though I will shout out this video and its sequels which I found fairly illuminating). Thus, true to my nature, now that I've managed to figure out enough of the basics to create something usable, I want to share what I've learned. And so:

≾ HOW TO OCTREE ≿

Octrees are a type of spatial partitioning data structure, i.e. a way to organize objects in game worlds based on their locations so that tasks related to said locations can be done efficiently. An oft-cited example is physics engines: a game world may contain a large number of objects, while the game (or simulation) requires that, like solid objects in real life, objects should avoid overlapping each other (e.g. by bouncing). A tempting naive solution for eliminating overlap is to check each object against each other object in a nested loop, but when there are numerous objects this becomes an enormous task of many thousands or millions of operations. By organizing the references to all of these objects in memory in a clever manner, one can enable the engine to make safe generalizations about them and thereby eliminate most of the work.

To start off, imagine if I ruled that the virtual world is to be treated as four adjoining squares: the Northwest Quadrant, the Northeast Quadrant, the Southwest Quadrant, and the Southeast Quadrant. Whenever some object, say Jan Michael Vincent, comes into existence, I examine where it is (its coordinates on two axes, traditionally X and Y or X and Z) and compare these values to the zero point representing the world origin. I can take the first axis to represent West and East - if the value is negative, then the object is somewhere to the West of the world origin and thus in one of the two Western Quadrants, and if it is positive then it is in one of the Eastern Quadrants. Then, making the same comparison with the second axis, I can determine whether it belongs to the Northern or Southern Quadrants.

Because all objects in the simulation exist somewhere in the simulating machine's memory, there is effectively a master list of all objects in the world. With the decisions I have just made, though, I can instead keep four distinct lists of objects - one for each Quadrant. On its own this organization does nothing, but say I want to add another Jan Michael Vincent, but I don't want there to be two in the same Quadrant. I can simply examine which Quadrant would contain the new one and then examine the objects in the list corresponding to that Quadrant, rather than all objects - if the objects are roughly uniformly distributed, then I've already eliminated 3/4 of the work.

Things like physics engines often need to go a little bit further, though. I could easily put something near the edge of a Quadrant in such a way that it extends slightly into another Quadrant. In order to see if one object overlaps another, then, I'll need to consider this possibility - not only whether this object extends into another Quadrant but whether objects in some other Quadrant are reaching into the one I'm currently examining. The end result is that I'll have to examine not just one specific Quadrant but every Quadrant that touches it, which is, unfortunately, all four Quadrants.

But what if I divide the Quadrants into Quadrants? Each Quadrant that contains some objects could be divided up and contain its own set of four sub-Quadrants with their own lists of objects, for a potential total of sixteen, just like in the hypothetical movie. Then, when a new Jan Michael Vincent appears, I can look at his current sub-Quadrant and every sub-Quadrant it touches, but not every sub-Quadrant in the world. If I'm lucky, I'll be back to eliminating 3/4 of the work again.

The fun part is that these rules can be extended with no limit. I can keep subdividing regions of space into smaller and smaller cells and organizing the data into ever more specific partitions, in so doing making it possible to eliminate ever greater portions of the total work later on. Eventually I'll be able to reach a point at which, even if many objects exist in the world, any one cell may only contain a small number of objects or none at all. If this number is small enough, I need not divide it any further because examining this small number of objects becomes a simple and short task. Visually, this would look a bit like a Piet Mondrian painting, with squares of different sizes nestled together, but the data could also be visualized as a tree, with smaller cells being connected together as branches of the larger cells from which they arose:

In this example, I have randomly distributed some black dots and then organized them with the rule that each square may contain at most one dot. Note that some squares are empty, but only squares containing more than one dot have been divided into smaller squares.

All the references to Quadrants may make it unsurprising that this data structure is known as a quadtree. An octree is the same concept extended into three dimensions - rather than partitioning space into square cells and creating 2^2 or 4 new cells each time one is divided, an octree partitions space into cubic cells and creates 2^3 or 8 cells whenever one is divided. Both quadtrees and octrees have uses for which they are better suited - for instance, a quadtree is useful for dealing with huge tracts of land that need to be loaded at different levels of detail based on how far they are from the viewer.

So far, nothing I've described hasn't been covered one place or another. My goal is to demystify how to get from this theoretical point to an actual usable octree implementation. To start, here's a sort of pseudocode adaptation of what I've discussed:

class Octree:

    List of occupants
    
    capacity (positive integer)
    
    Array (length 8) of Octree children <- Octrees contain references to "child" octrees that occupy regions of space within them
    
    scale (floating point value)
    
    center (3D vector)
    
    Constructor(parent Octree, octant (integer value from 0 to 7)):
        capacity = parent capacity
        center = parent center
        treat octant as three bits, e.g. 000, 101, or 111:
            if first bit (fours place) is 1, add half the parent scale to the center's X coordinate
            if second bit (twos place) is 1, add half the parent scale to the center's Y coordinate
            if third bit (ones place) is 1, add half the parent scale to the center's Z coordinate
            (the center is thus now shifted so that it is halfway to one of the corners of the space occupied by the parent)
        scale = parent scale / 2
    
    Insert(occupant):    <- This is structured in such a way that it is easy to extend later
        allocate point (3D vector)
        point = occupant's position (how to obtain this will vary based on the development environment)
        InsertPointRecursive(this Octree)
    
        InsertPointRecursive(current Octree):    <- This is a recursive function that will repeatedly call itself with deeper and deeper nested Octrees until it finds a suitable stopping point. I implemented it as a local function but if this is not feasible you can instead allocate the occupant and point variables separately
            if current octree has children:
                for each child:
                    if child.Contains(point) InsertPointRecursive(child)
            else:
                add occupant to occupants
                if there are more occupants than capacity    current.Split()
    
    Contains(point (3D vector)): returns a boolean value
        Compute whether point is within a cube with center equal to this octree's center and extents along each axis equal to this octree's scale (i.e. dimensions equal to double the scale). This is typically done by examining each coordinate of the given point, comparing it to the center plus or minus the scale, and returning false if the point does not fall within the appropriate range. If all checks pass, return true.
    
    Split():
        create an array of 8 children
        allocate octant (integer value from 0 to 7) and set it to 0
        while octant is less than 8:
            children[octant] = Constructor(this Octree, octant)
            (create a new child using the Constructor and a reference to this Octree and the current octant value, then add it to the array of children)
        for each occupant:
            octant = 0
            treat octant as three bits:
                if occupant's X coordinate is greater than that of the center, set the first bit to 1, i.e. add 4
                if occupant's Y coordinate is greater than that of the center, set the first bit to 1, i.e. add 2
                if occupant's Z coordinate is greater than that of the center, set the first bit to 1, i.e. add 1
            children[octant].Insert(occupant)
            (use the octant value as an array index to get the child Octree corresponding to the occupant's location and then insert the occupant into that child Octree)
        optionally clear the list of occupants, since all objects should now be referenced by the children

 
As with any pseudocode, the final implementation is bound to vary somewhat, as mine did, depending on choice of language, optimizations, and other decisions.

Since, in the interest of being clear and thorough, I've ended up making this article quite long already, I'll once again split it up and call this the "introduction." Look forward to follow-up entries detailing how I moved forward from here.