flipcode - Dirtypunk's Column

Dirtypunk's Column - Issue 05 - AABB Trees - Back To Playing With Blocks
by (19 March 2002)

The Triumphant Return

Boldly, I have decided yet again to try and get one of these column updates done – hopefully without running out of time or even worse, corrupting the floppy that the tutorial resided on (oops).

This week (or year, if you’ve been following the column) is on AABB (axis aligned bounding box) trees, the lovely and efficient bounding volume hierarchy that will bring you back into the realm of happiness… … and maybe let you speed some things up along the way. Not only that, I’ve included some sample code and a demo.

As a note before we start, what is said here is directly relevant for an AABB tree. But much of it applies to other bounding volume hierarchies based on spheres, oriented bounding boxes, cubes, lozenges, capsules, ellipsoids, convex hulls or teapots (although, the last one is not recommended). So, take notes and experiment using different volumes if you think you can get a better result. I chose the axis aligned bounding box, because they are easy to understand as well as fast and many people already have code for dealing with them.

What You Talkin’ ‘Bout?

Well, the AABB tree is just that – a tree of axis aligned bounding boxes. Each parent node box bounds its children (and so on), til we get to the leaves of the tree, which bound… …well what ever geometry you are using (usually triangles, which I’ll use as the example from now on). This leads to some interesting properties.

If a parent isn’t visible, its children aren’t visible (all the way down, including the items in the leaves) and if the parents don’t intersect with something, the children won’t intersect with it. As testing an AABB for collision or frustum intersection is usually fairly quick, we can avoid testing large sections of the tree for a relatively small cost.

If you have used an octree, kd-tree or BSP tree before, all this probably sounds fairly familiar, but that doesn’t mean the AABB tree is redundant. These previously mentioned trees (spatial partitions) all have major disadvantages, such as geometry crossing over bounds (and needing to be clipped) and trying to partition all space (in their bounds). An AABB tree has neither of these problems.

The AABB only ever worries about areas of interest (those with geometry) and doesn’t create empty nodes. It doesn’t worry about overlapping or neighbours. For these reasons, the AABB produces a smaller tree with a very tight fit. This is generally good for collision detection, frustum culling, nearest geometry tests etc.

However, an AABB tree isn’t really useful for sorting geometry. It also doesn’t allow you to always find a node that a given point is in or allow you to easily find neighbouring nodes. For this reason, creating a PVS with an AABB tree or using an AABB tree for occlusion culling is not a very good idea.

Play God And Create A Tree!

The first task at hand is how to actually create a tree… Of course there are multiple ways of doing this. We can make the tree from the bottom up or the top down, depending on what your end goal is. We can use a few different heuristics and ideals to decide what we want.

The goal I choose is simple. I want to create a tree with the smallest bounds possible for a target triangle count, at a reasonable tree depth and reduce the size of nodes that are too large (in terms of volume). Volume tends to be the driving force, because the more volume a node has, the worse it is for performance. This is because the chance of an object touching a node increases with the node’s volume.

For this purpose, I’ll first introduce an interesting error metric – the volume of a box + a unit cube. The unit cube in the metric prevents big boxes that happen to be flat having a zero result and muddling things up.

The actual process of building the tree is easiest to do in a recursive way (as it is often with trees). Per node, we want to first calculate the bounding volume (and store it) and then check the heuristics to see if we want to make children (insert suitably dirty joke here). After, we need to work out what geometry will go to the child nodes and create them. If we aren’t making children, we store the geometry passed to the current node. In this tree, leafs must have geometry in them, so you can (if you want) use that fact to label a leaf or alternatively (as I use) you can denote a leaf by null child pointers.

The heuristic I use is something like this: If the node is at the maximum depth or we have below the minimum amount of triangles, building must stop. If the triangle count is below the target amount we stop building unless the error metric of this node’s box is too large.

For simplicity sake, we’ll choose a tree where each non-leaf node has 2 children. What triangles go to a child node is determined per triangle. This is done by testing what side of the average point of all the triangles in the node the midpoint of the triangle in question is. This test is performed in the longest axis of the node bounding box.

Let’s make some pseudo ugly C++ code


AABB_Tree_Node(list<Triangle> trilist, unsigned int treedepth) {
	
    // Build the node bounding box based from the triangle list	

    if (heuristic passed) {
		
        // Find the longest axii of the node's box
        // Find the average point of all the triangles

	list<Triangle> tribuckets[2];

	for all triangles in trilist {
	    // Put into tribuckets based on midpoint's side of
            // average point in the longest axis 	
	}

        child[0]=new AABB_Tree_Node(tribuckets[0],treedepth+1);
        child[1]=new AABB_Tree_Node(tribuckets[1],treedepth+1);
    
    } else {
	
        child[0]=0; // denotes a leaf
        // Copy trilist and store in this node
    }
}

Let’s Do Something With It!

Two examples I mentioned earlier that an AABB tree could be used to speed up were frustum culling and collision detection. Using the hierarchy, easy early outs can be gained and we can efficiently find areas of interest. Let’s look at an example in greater detail…

Let’s say, we want a simple yes/no test to see if a sphere touches a triangle in a model. We must move down the tree testing against node bounds and continuing til we hit a leaf, where we can test triangles. As an added speed up, depending on the model, we can also make use of the fact we should never have an empty leaf. By testing if the sphere totally encompasses a node, we know a triangle must also be encompassed. Let’s do some more ugly pseudo code.


bool AABB_Tree_Node::TestForCollision(Sphere test_sphere) {

    if (test_sphere encompasses the node box)
        return true;

    if (test_sphere intersects the box) {

        if (this node is not a leaf) {
            if (child[0]->TestForCollision(test_sphere))
                return true;
            if (child[1]->TestForCollision(test_sphere))
                return true;

            return false;
        }
		
        for all the triangles in this node {
            // test for intersection with sphere
            // and return true if intersection found
        }
    }

    return false;
}

Some Further Reading

A paper using AABB trees for collision detection:
http://www.win.tue.nl/~gino/solid/jgt98deform.ps

The advanced collision techniques article at gamasutra has some stuff:
http://www.gamasutra.com/features/20000330/bobic_01.htm

Notes On The Demo/Sample Code

The demo uses unextended OpenGL on windows. It tests for collision with 4 spheres against a triangle model, accelerated using the AABB tree. It shows the collided triangles/aabb tree nodes, in different colours for each sphere.

The sample code is some excerpts from the demo - the geometric primitives (very simple sphere, aabb and triangle classes) and a very simple AABB tree class. The code isn't particularly neat (but it is commented and readable) and it is definitely not optimised, but it should serve to show how such a class can be implemented.

Download the source code + demo package here: aabb_tut.zip (155k)

Fin;

AABB trees are very simple, but can go a long way to speeding up your geometric queries. Next time you want to do something like collision detection? Remember AABB trees, this tutorial and most of all remember my soft hands.

As always, thanks to the guys in #flipcode for being my testing lackeys and proof readers (kisses all round) and Kurt for doing his thang.

Article Series:

Dirtypunk's Column - Issue 01 - Hardware Rendering Optimizations
Dirtypunk's Column - Issue 02 - Line Dualities: Plucker Space And You
Dirtypunk's Column - Issue 03 - Visibility Theory
Dirtypunk's Column - Issue 04 - View Independent Progressive Meshes
Dirtypunk's Column - Issue 05 - AABB Trees - Back To Playing With Blocks