Octrees - Code and walkthrough

Octrees are a data structure to represent spartially dividing up a scene. The way they work is to divide up a scene into eight leafs, with each leaf further dividing up if they contained more objects than the set threashold.

You could then use this divided up scene for optimisations. Such as to only process rendering for the objects in the visible octrees, or to only process collisions for the objects in the same octree as the current object.

Here's a video of the octrees in action, notice how when a leaf becomes dense, it breaks down into a further eight leafs.



So let's start.

First we create our octree structure. With each octree will containing a pointer to it's parent tree, it's eight leafs, a set of objects and it's world position.

 enum OctreeLeafs  
{  
leaf_bottom_front_left,  
leaf_bottom_front_right,  
leaf_bottom_back_left,  
leaf_bottom_back_right,  

leaf_top_front_left,  
leaf_top_front_right,  
leaf_top_back_left,  
leaf_top_back_right,  
};  

struct Octree  
{  
Octree *parent;  
Octree **leafs;  
ObjectCollideable *objects[MAX_TREE_OBJECTS];  
uint numberOfObjects;  

float hSize;  
Vector3 min, max;  
};  

We can then create the octree with.

 void OctreeNew(Octree **tree, Octree *parent, const Vector3 position, const float size)  
{  
*tree = malloc( sizeof( Octree ) );  
(*tree)->parent = parent;  
(*tree)->leafs = nil;  
(*tree)->numberOfObjects = 0;  

(*tree)->hSize = size * 0.5f;  
(*tree)->min = position;  
(*tree)->max = position;  
Vector3AddFloat( &(*tree)->min, -(*tree)->hSize );  
Vector3AddFloat( &(*tree)->max, (*tree)->hSize );  
}  

Now we'd need to handle adding an object to the tree, this is done by use of recursive function calls, that drill down into the leaf nodes to add the object to all the leafs it resides in. Once it's found a leaf if we have space for the object we add it into it's object list, if we don't have space we'll need to split the tree down to a further eight leafs and re-attempt adding the object.

 void OctreeAddObject(Octree *tree, ObjectCollideable *collideable)  
{   
// Ensure the object is within the octree's limits  
if( tree->parent == nil )  
{  
UpdateCollisions( collideable );  
Vector3 *objectMin = &collideable->min;  
Vector3 *objectMax = &collideable->max;  
if( objectMax->x < tree->min.x ||   
objectMax->y < tree->min.y ||   
objectMax->z < tree->min.z ||   
objectMin->x > tree->max.x ||   
objectMin->y > tree->max.y ||   
objectMin->z > tree->max.z )  
{  
return;  
}  
}  

// Insert in an approperate leaf node  
if( tree->leafs != nil )  
{  
UpdateCollisions( collideable );  

for( uint i=0; i<8; ++i )  
{  
Octree *leaf = tree->leafs[i];  
if( OctreeIsInLeaf( leaf, &collideable->min, &collideable->max ) )  
{  
OctreeAddObject( leaf, collideable );  
}  
}  
}  

// Unless we don't have any  
else if( tree->numberOfObjects < MAX_TREE_OBJECTS )  
{  
tree->objects[tree->numberOfObjects++] = collideable;  
assert( collideable->numberOfOctrees < MAX_OBJECT_TREES );  
collideable->octrees[collideable->numberOfOctrees++] = tree;  
}  

// If we have too many objects split the octree  
else  
{  
OctreeSplit( tree );  

// Try again  
OctreeAddObject( tree, collideable );  
}  
}  

To check if the object resides in a leaf's space we simply use our min max vectors which we're set in OctreeNew.

 BOOL OctreeIsInLeaf(Octree *leaf, Vector3 *targetMin, Vector3 *targetMax)  
{  
Vector3 *sourceMin = &leaf->min;  
Vector3 *sourceMax = &leaf->max;  

if( sourceMax->y > targetMin->y && sourceMin->y < targetMax->y )  
{  
if( sourceMax->x > targetMin->x && sourceMin->x < targetMax->x )  
{  
if( sourceMax->z > targetMin->z && sourceMin->z < targetMax->z )  
{  
return YES;  
}  
}  
}  

return NO;  
}  

Now comes the fun part, splitting our octree into a further eight octrees.
To do so, we first create the eight leaf nodes from our parent's min max vectors and hSize variables.

 void OctreeSplitTopLeafs(Octree *tree, const uint index, Vector3 position)  
{  
position.y += tree->hSize;  
Octree **leaf = &( tree->leafs[index+4] );  
OctreeNew( leaf, tree, position, tree->hSize );  
}  


void OctreeSplit(Octree *tree)  
{  
assert( tree->leafs == nil );  
tree->leafs = malloc( sizeof( Octree ) * 8 );  

// Create our leaf nodes  
uint index = leaf_bottom_front_left;  
Vector3 position = tree->min;  
Vector3AddFloat( &position, tree->hSize * 0.5f );  
Octree **leaf = &( tree->leafs[index] );  
OctreeNew( leaf, tree, position, tree->hSize );  
OctreeSplitTopLeafs( tree, index, position );  

index = leaf_bottom_front_right;  
position.x += tree->hSize;  
leaf = &( tree->leafs[index] );  
OctreeNew( leaf, tree, position, tree->hSize );  
OctreeSplitTopLeafs( tree, index, position );  

index = leaf_bottom_back_right;  
position.z += tree->hSize;  
leaf = &( tree->leafs[index] );  
OctreeNew( leaf, tree, position, tree->hSize );  
OctreeSplitTopLeafs( tree, index, position );  

index = leaf_bottom_back_left;  
position.x -= tree->hSize;  
leaf = &( tree->leafs[index] );  
OctreeNew( leaf, tree, position, tree->hSize );  
OctreeSplitTopLeafs( tree, index, position );  
...  

We then parse through the current leaf's objects, remove them from the object list and re-add them into the appropriate new leafs we've just created.

     // Now we need to sort our objects into our new leafs  
while( tree->numberOfObjects > 0 )  
{  
ObjectCollideable *collideable = tree->objects[0];  
removeFromList( collideable, (void**)tree->objects, &tree->numberOfObjects );  
removeFromList( tree, (void**)collideable->octrees, &collideable->numberOfOctrees );  

UpdateCollisions( collideable );  

for( uint i=0; i<8; ++i )  
{  
Octree *leaf = tree->leafs[i];  
if( OctreeIsInLeaf( leaf, &collideable->min, &collideable->max ) )  
{  
// Place this object in this leaf  
leaf->objects[leaf->numberOfObjects++] = collideable;  
assert( leaf->numberOfObjects <= MAX_TREE_OBJECTS );  
collideable->octrees[collideable->numberOfOctrees++] = leaf;  
assert( collideable->numberOfOctrees < MAX_OBJECT_TREES );  
}  
}  
}  
}  

Now for removing an object from the tree, we simply check through all the leafs the object resides in and one by one remove the object from the trees list. We then set a call to prune the tree, so that if the leafs are no longer needed they'll be deleted.

 void OctreeRemoveObject(ObjectCollideable *collideable)  
{  
while( collideable->numberOfOctrees > 0 )  
{      
Octree *tree = collideable->octrees[0];  
removeFromList( collideable, (void**)tree->objects, &tree->numberOfObjects );  
removeFromList( tree, (void**)collideable->octrees, &collideable->numberOfOctrees );  

if( tree->numberOfObjects == 0 )  
{  
if( gEngine->collideables->pruneTrees <= 0.0f )  
{  
gEngine->collideables->pruneTrees = 1.0f;  
}  
}  
}  
}  

Above I set a timer to 1.0f which would count down elsewhere to call the prune tree function. With the prune tree function recursively calling itself on all it's leafs, and if the set of leafs have no objects in them they get deleted.

 void OctreePruneTree(Octree *tree)  
{  
if( tree->leafs != nil )  
{  
BOOL hasObjects = OctreeHasObjects( tree );  
if( hasObjects == NO )  
{  
OctreeDeleteLeafs( tree );  
}  
else  
{  
for( uint i=0; i<8; ++i )  
{  
OctreePruneTree( tree->leafs[i] );  
}  
}  
}  
}  


BOOL OctreeHasObjects(Octree *tree)  
{  
BOOL hasObjects = tree->numberOfObjects > 0;  

if( tree->leafs != nil )  
{  
for( uint i=0; i<8 && hasObjects == NO; ++i )  
{  
hasObjects |= OctreeHasObjects( tree->leafs[i] );  
}  
}  

return hasObjects;  
}  

Again delete leafs works by recursively calling itself to free all the leafs inside.

 void OctreeDeleteLeafs(Octree *tree)  
{  
// Ensure all our leafs are deleted  
if( tree->leafs != nil )  
{  
for( uint i=0; i<8; ++i )  
{  
if( tree->leafs[i] != nil )  
{  
Octree *leaf = tree->leafs[i];  
OctreeDeleteLeafs( leaf );  
}  
}  

free( tree->leafs );  
tree->leafs = nil;  
}  
}  

That's it! Simply add in all your static objects, then whenever you move an object, just re-add it to the root tree, so it can put itself into the appropriate leafs.