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.