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.