Kreation’s Edge

Created: Aug 4, ‘04

Printer Friendly

AABB Trees: Best Axis Algorithm

Hopefully you have read my tutorial on computing AABBs. We will now build on that knowledge and build an AABB Tree. AABB Trees provide accurate collision detection for complex scenes/polygon soups (and it can be used for culling too). This paper focuses on using AABB Trees for collision detection.

Below is an example of a mesh using an AABB Tree:
AABB Trees are hierarchial structures that consist of AABB Nodes. Each AABB Node has it’s own min/max bound and pointer members to left/right AABB Nodes. Below is a definition of an AABB Node:

	struct AABBNode
	{
		WVector min, max;
		AABBNode *left, *right;
		WVector *m_pVerts;	//vertices stored within this node
		unsigned int m_nNumVerts; //num of vertices stored (3->n)
	};

The AABBB Tree is composed of AABBNode primitives. To compute an AABB Tree, we use a heuristic (inputs to the algorithm) that defines the max tree depth and minimum number of vertices we want each node to contain.

	typedef unsigned int udword;  

	//Defines the behavior of the AABB tree
	struct GODZ_API AABBTreeInfo
	{
		//heuristics
		udword max_tree_depth;		//max depth the tree can reach
		//min number of vertices each leaf can store
		udword min_vertices;		  

		//ensures that an AABB is never generated that
		//is over min_vertices. Normally, this algorithm
		//is not required because the best axis
		//algorithm normally produces a perfectly balanced tree.
		bool m_bPrune;
	};

The typical AABB Tree can store any number of vertices at each leaf. The heuristic can be played around with to determine best performance (triangles vs max tree depth). The more triangles you store within each node, the less AABB nodes you’ll end up with. If you store too few vertices, you may end up with a huge AABB Tree consisting of lots of nodes. If you store too many triangles, you might end up with too few AABB Nodes- which may cause you too spend too much time evaluating a collision with triangles. During the building process, we recursively crunch the vertex buffer until we end up with a tree that holds an AABB for triangle(s) within the mesh. An AABB Tree is composed of two different types of tree nodes: parent and leaf nodes. The parent AABB Node simply references left/right siblings. It’s AABB encloses it’s child AABB Nodes but it is only an indicator that a collision may be possible. We recursively descend into the AABB tree until we find child leaf nodes that directly store triangles. Below we define the structure of the AABB Tree:

	struct AABBTree
	{
		AABBNode *root;
	};

AABB Trees are normally computed using the longest axis of the box. From there, we examine each triangle in the vertex buffer and test the center of the face to see if it’s less/greater than the split. If it’s less, then we can place the triangle in the buffer for the left node. If it’s greater than we can place this triangle in the right buffer. So basically we just split the VB (vertex buffer) and generate the right/left AABB node. However, instead of using simply the longest axis of the box, we can instead pick the best axis of the box that will result in the most balanced tree. We find the best axis of a vertex buffer by using the C++ code below:

int AABBNode::FindBestAxis(std::vector<Vertex> &vertexList)
{
	size_t vertexNum=vertexList.size();  

	//divide this box into two boxes - pick a better axis
	int iAxis=0;
	int iAxisResult[3]; //stores how close end result is, the lower the better  

	WVector center = m_box.GetCenter();  

	for (iAxis=0;iAxis<3;iAxis++)
	{
		int left=0,right=0;
		Vertex v[3];
		int count=0;
		for(udword i=0;i<vertexNum;i++)
		{
			v[count]=vertexList[i];
			if (count==2)
			{
				float faceCenter[3];
				faceCenter[0] = (v[0].x + v[1].x + v[2].x) / 3.0f;
				faceCenter[1] = (v[0].y + v[1].y + v[2].y) / 3.0f;
				faceCenter[2] = (v[0].z + v[1].z + v[2].z) / 3.0f;  

				if (faceCenter[iAxis] <= center[iAxis])
				{
					left++;
				}
				else
				{
					right++;
				}  

				count=0;
			}
			else
			count++;
		} // vertices  

		iAxisResult[iAxis] = abs(left-right);
	} //axis  

	int index=0;
	int result=iAxisResult[0];
	for (int i=1;i<3;i++)
	{
		if (iAxisResult[i] < result)
		{
			result = iAxisResult[i];
			index=i;
		}
	}  

	//Log("result: %d\n", iAxisResult[index]);  

	return index;
}

We call the FindBestAxis() during the tree building process. Below is the C++ code to build the AABB Tree. It is recursive, recuring only one simple call to start the process.

void AABBNode::BuildTree(vector<Vertex> vertexList, AABBTreeInfo &treeInfo,
udword depth)
{
	int vertexNum=(int)vertexList.size();  

	// Build the node bounding box based from the triangle list
	WBox Box(&vertexList[0], vertexNum);  

	//debug box bounds
	SetBounds(Box);  

	if (depth+1 > treeInfo.curr_max_depth)
		treeInfo.curr_max_depth=depth+1;  

	bool bMakeChildren=false;  

	if (vertexNum > treeInfo.min_vertices
	&& depth<treeInfo.max_tree_depth)
	{
		bMakeChildren=true;
	}  

	if (bMakeChildren)
	{
        // Find the longest axii of the node's box
		//int iAxis=Box.GetLongestAxis();
		int iAxis = FindBestAxis(vertexList);
		//Log("Longest axis: %d\n", iAxis);  

		//Get the Arrays for min, max dimensions
		float *min = &Box.min.x;
		float *max = &Box.max.x;  

		//get center of the box for longest axis
		//float fSplit = ( max[ iAxis ] + min[ iAxis ] ) / 2.f ;
		WVector center = Box.GetCenter();
		//Log("split: %f\n", fSplit);  

		int count=0;
		Vertex v[3];
		vector<Vertex> leftSide;
		vector<Vertex> rightSide;  

		udword leftCount=0,rightCount=0; //debug  

		//Log("verts: %d\n", vertexNum);  

		//btw, things that could go wrong- if the mesh doesn't
		//send over the triangles correctly, then you might see
		//huge boxes that are misaligned (bad leaves).
		//things to check is making sure the vertex buffer is
		//correctly aligned along the adjancey buffers, etc
		for(int i=0;i<vertexNum;i++)
		{
			v[count] = vertexList[i];  

			if (count==2)
			{
				float faceCenter[3];
				faceCenter[0] = (v[0].x + v[1].x + v[2].x) / 3.0f;
				faceCenter[1] = (v[0].y + v[1].y + v[2].y) / 3.0f;
				faceCenter[2] = (v[0].z + v[1].z + v[2].z) / 3.0f;
				//WVector faceCenter(x,y,z);  

				if (faceCenter[iAxis] <= center[iAxis]) //fSplit
				{
					//Store the verts to the left.
					leftSide.push_back(v[0]);
					leftSide.push_back(v[1]);
					leftSide.push_back(v[2]);  

					leftCount++;
				}
				else
				{
					//Store the verts to the right.
					rightSide.push_back(v[0]);
					rightSide.push_back(v[1]);
					rightSide.push_back(v[2]);  

					rightCount++;
				}  

				count=0;
			}
			else
				count++;
		}  

		if (treeInfo.m_bPrune && (leftCount == 0 || rightCount == 0)
			)
		{
			//okay, now it's time to cheat. we couldn't use
			//the best axis to split the
			//box so now we'll resort to brute force hacks....
			leftSide.clear();
			rightSide.clear();  

			int leftMaxIndex = vertexNum / 2; //left side  

			int count=0;
			Vertex v[3];
			for(int i=0;i < vertexNum;i++)
			{
				v[count] = vertexList[i];
				if (count == 2)
				{
					if (i<leftMaxIndex)
					{
						//left node
						leftSide.push_back(v[0]);
						leftSide.push_back(v[1]);
						leftSide.push_back(v[2]);
					}
					else
					{
						rightSide.push_back(v[0]);
						rightSide.push_back(v[1]);
						rightSide.push_back(v[2]);
					}  

					count=0;
				}
				else
					count++;
			}
		}  

		if (leftSide.size() > 0 && rightSide.size() > 0)
		{
			assert(leftSide.size() % 3 == 0);
			assert(rightSide.size() % 3 == 0);  

			//Build child nodes
			if (leftSide.size() > 0)
			{
				treeInfo.left_children++;
				children[0] = new AABBNode(leftSide,
				treeInfo, depth+1);
			}
			if (rightSide.size() > 0)
			{
				treeInfo.right_children++;
				children[1] = new AABBNode(rightSide,
				treeInfo, depth+1);
			}
		}
		else
		{
			//should never happen
			bMakeChildren=false;
		}
	}  

	if (!bMakeChildren)
	{
		//Store the data directly if you want....
	}
}

This is really all it takes to construct an AABB Tree. You will also of course need functions to perform AABB Overlap tests and AABB Sweeps. This is the logic to detect collision using the AABB Tree:

• Test other AABB against the root of the AABB Tree. If it does not overlap then return false. If it does, proceed.
• If the AABB Node is a leaf, then return true. If not, proceed.
• Call the left AABB Node and recursively check it’s child nodes to see if any or
  leaves and if one of them collides with the AABB Node.
• If no collisions have been detected then check the right AABB Node. If it or
  one of it’s nodes is a leaf node and it overlaps the AABB then return true.

Below is C++ code of an AABB Node performing an AABB Sweep (you might want to read up on Sweep Volumes).

bool AABBNode::AABBSweepHit(CollisionPrimitive *A, const WVector &oldLocation,

const WVector &newLocation, CollisionResult &result)
{
//if the box is impact by the moving primitive
if (CollisionPrimitive::AABBSweepHit(A, oldLocation, newLocation, result))
{
if (IsLeaf())
{
//test all the triangles within the this node.
//Verify a collision exists.
}

//Go through children since this is not a leaf
AABBNode *left = GetLeftChild();
AABBNode *right = GetRightChild();

if (left != NULL && left->AABBSweepHit(A, oldLocation,
newLocation, result))
{
return true;
}

if (right != NULL && right->AABBSweepHit(A, oldLocation,
newLocation, result))
{
return true;
}
}

return false;
}
 

AABB Trees, Where are they getting used?
Many games uses different forms of bounding volume hierarchies. I talked with a guy that worked on Ratchet and Clank, which I hear used Sphere Volume Trees (which is the same as AABB Trees just that pills are used instead of boxes). The Unreal Engine uses an AABB Tree variant for static meshes. Static meshes- despite their name, can actually be moved around the level- so all of the child nodes get transformed along with the entity.

References:
3D Game Engine Design by David Eberly