Constructing an Octree Datastructure

Lately, I have been working hard on my 3D engine Storm3D. One of the features that I am spending a lot of time on, is developing a generic and efficient octree data structure, that will serve multiple purposes from collision detection to voxel based rendering. Here I will introduce the basic algorithm for building an octree and some of the obstacles that you might face.

What is an octree ?

An octree is a hierarchical data structure in which each internal node has eight children. Octrees are usually used to partition a three dimensional space by recursively subdividing it into eight octants. When an octree is used to partition 3D space each ocrtree (sub)space is bounded by a cube and sometimes a cuboid is used instead, each cube is divided recursively into eight cubes until the algorithm reaches a termination criteria.

Octrees are used to speed up certain operations that are otherwise costly, such as  nearest neighbor search, ray casting or collision detection.

Octrees are usually implemented using a linked technique where each node contains pointers (or references) to each of its eight children. A complete octree will have either 8 children for internal node or no children for a leaf node.

Figure 2: Stanford bunny with 8 level octree as visualized in Storm3D Engine.

Constructing the Octree

There are two basic approaches that you can use for building an octree, the first is to build the octree based on the geometry in the scene, this one is mostly useful when the geometry is static since you usually won’t need to update anything in the tree structure. The other approach is to build an octree to a certain depth insert the geometric entities later into it. This could be more useful when you have dynamic scenes. Figure 2 shows Stanford bunny triangles stored in eight level Octree data structure. Notice how each cube represents a node and are divided based on the distribution of the polygonal data.

A basic OctreeNode could look like this, first need to store a bounding box for each node, you can either store half width and center, or the full boudning box class

struct OctreeNode
{
float halfWidth;
vec3 center;
AxisAlignedBox m_bounds;
std::vector<OctreeEntity*> m_objects; // You can use a (intrusive) linked list instead but I like vector because of its contiguous memory
OctreeNode* m_children[8];
};

A bottom-up approach

The algorithm starts by calculating the bounding box of the whole mesh(es) in the scene. Once you have the bounding box you either calculate the cube that corresponds to it or use the same bounding box for the tree construction, if you want to calculate the cube you only use same center and a length equals to the maximum dimension of the bounding box. The tree is constructed based on the distribution of the geometry, that is every sub-space that encloses a certain number of geometric entities should be split until we reach a certain number of entities in each leaf and/or when we reach certain depth level. Other subspaces that don’t contain any entities should terminate that branch and should stop the subdivision.

You split each box into eight sub-boxes, if the sub box contains any geometric data you continue splitting the box by calling the function recursively. You can terminate the recursion once the box has a certain number geometric entities or the tree reached a certain level. Each condition for terminating the tree construction varties based on the application and should be chosen wisely.

//
// Building an octree, code for educational reasons and not particularly optimized.
//
static OctreeNode* BuildOctreeFromMesh( Mesh* mesh, std::vector& objects, AxisAlignedBox& aabb, int stopDepth)
{ 
// stop if we reached certain depth or certain number of objects
if(stopDepth < 0 || objects.size() < 3) return NULL; // Split to 8 cubes AxisAlignedBox boxes[8]; aabb.SplitToEight( boxes ); // Create a node and attach the objects OctreeNode* node = new OctreeNode;  node->m_bounds = aabb;
node->m_objects = objects; // Warning: copying here best be avoided.

std::vector boxObjects[8]; 
//for each triangle check intersection with 8 boxes
for (int i=0; i < objects.size(); ++i) { Triangle& tri = mesh->GetTriangle(objects[i].triangleIdx);
for (int boxId=0; boxId<8; ++boxId)
{
vec3 center = boxes[boxId].GetCenter();
vec3 halfsize = boxes[boxId].GetHalfSize();
bool overlaps = TriBoxOverlap( center, halfsize, tri.vert );

if ( overlaps )
{
boxObjects[boxId].push_back( objects[i] ); // Potential memory allocation here. Could be optimized 
}
}
}

//Loop through boxes and divide them more.
for (int i=0; i < 8; ++i) { size_t size = boxObjects[i].size(); if ( size ) { node->m_children[i] = BuildOctreeFromMesh(mesh, boxObjects[i], boxes[i], stopDepth-1);
}
}

return node;
}

The most challenging part of building an octree is the intersection test between the geometric entity and the bounding volume/triangle. This can be sometimes fairly simple for objects like points and sphere. But can be more complex for triangles, the best algorithm you can use for a triangle box intersection is based on separating axis theorem and you can find it here.

As a final note allocating the nodes using OctreeNode* node = new OctreeNode; might cause cache misses and significantly decrease the tree performance. I advise you to use memory pools instead in case your tree performance (especially traversal) was less than optimal. Using memory pools will make the memory to be contagious and hence avoiding potential problems that can happen due to memory not fitting in cache.

A top-down approach

The other approach starts by building a complete octree to a certain depth level, then insert objects into it. This might be useful for dynamic scenes but it consumes more memory. You start the insertion by testing intersection with the root node, after determining which child of the node the object intersects, you recursively repeat the operation, until you reach a leaf node. If an object intersects more than one child you either split it between them or copy it for each path, this might be simpler to implement but actually splitting it might be more efficient.

Storing geometric entities

Eventhough I am basically talking about triangles here, an octree data structure can contain multiple types of geometric entities, while I had the option to design my structure to contain multiple types in the same tree, the decision was taken so that the tree could contain either triangle meshes or bounding volumes (only one type a time). The decision is made to make certain optimization for each geometric entities easier. Octrees that contain only triangle meshes are usually used in ray casting or collision detection while other bounding volumes are a better candidate for visibility determination. Even though this is not final and could be changed, I found it easier to work with it this way, especially that certain optimizations can be implemented directly.

Each geometric entity is represented by a “OctreeEntity” and is stored in a vector of octree entities in each octree node. Think of the OctreeEntity as a handle, it does not actually contain the geometric object but rather an index that can be used to lock up the actual triangle/object from a list.

class OctreeEntity
{
// here we store a bounding sphere that could come handy in some intersection tests. but it's optional
vec3 center; // optional
float radius; // optional
unsigned int Idx;
};

Dealing with OctreeEntity instead of directly with a geometric object makes the data structure more generic. This way we are effectively hiding the geometric entity and not hard-coding anything inside the tree code. You might be asking how do we deal with different intersection testing and yet keeping the code generic, this can be simply done by hiding the intersection solver in a template function or a template class. You can even go as far as using templates for storing different geometric properties to implement particular optimizations, in templates terminology these are formally known as traits.

Rendering the octree for debugging in OpenGL 3.2

Rendering the octree can be handy for debugging and sometimes to achieve some cool effects. In Storm3D I have a function that traverses the tree and converts it into a renderable mesh. But before that there are two things you need to keep in mind especially if you are using OpenGL 3.2 where; GL_QUADS are deprecated and vertex buffer objects are the only way to draw things.

First, in order to draw a wireframe box without using two triangles, so the quad can be rendered correctly without the split line, you need to use GL_LINE_STRIP. On the performance side, you need to fill your octree in one VBO (though might not always be optimal), this will make you need to use glRestartIndex, so you can store multiple primitive in a single VBO that use GL_LINE_STRIP without duplicating vertices.

As for the actual conversion mechanism. The idea is to traverse the tree in a breadth/depth first traversal and convert each bounding box into renderable verteces and indices and then add them to the VBO. Once done you can render all your octree with a single draw call.

In this article I covered the basics of octree, in the next article I will cover more advanced topics such as ray casting and collision detection.