Kreation’s Edge

Computing an AABB

For this tutorial we will focus on something simple but integral to collision detection. How to build an AABB (Axis Aligned Bounding Box) and how they are different from OBB (Object Bounding Boxes). When you are done with this tut, you will know how to compute your own AABB (basically you will understand how DirectX helpers like D3DXComputeBoundingBox, etc works). The following code is API indendant so it doesn’t matter whether you’re using Open GL or DirectX.

Example of an AABB. The min/max vertices are highlighted:
An Axis Aligned Bounding Box is normally defined by two vectors: a min and max or you can define an AABB by 1 vector that represents the center of the box and a float in which represents the extents of the box. Most FPS engines represent an AABB by min/max vectors. Min being the least vertex in your box (lower bottom left) and max being the max vertex of the box (upper top right). These two vectors represent the extents of your AABB.

The formula to compute an AABB is simple. Taking a vertex buffer (list of vectors), we simply need to find the min/max regions of the mesh to compute an enclosing volume:

 struct WVector

 {

  float x,y,z;

 }; //Discovers the min/max bound within a list of vectors.

 template<typename T>

 void SetMinMaxBound(T *V, int count, WVector &min, WVector &max)

 {

  min=V[0],max=min;

  for (int i=1;i<count;i++)

  {

  if (V[i].x < min.x)

  min.x = V[i].x;

  if (V[i].y < min.y)

  min.y = V[i].y;

  if (V[i].z < min.z)

  min.z = V[i].z;

if (V[i].x > max.x)

  max.x = V[i].x;

  if (V[i].y > max.y)

  max.y = V[i].y;

  if (V[i].z > max.z)

  max.z = V[i].z;

  }

 }

//example how to call SetMinMaxBound()

 WVector min, max;

 WVector vb[4];

 vb[0] = WVector(3.0f,2.0f,2.0f);

 vb[1] = WVector(1.0f,-2.0f,-2.0f);

 vb[2] = WVector(-6.0f,-12.0f,-22.0f);

 vb[3] = WVector(43.0f,22.0f,32.0f);

//min, max will store the min/max of an AABB

 SetMinMaxBound<WVector>(&vb[0], 4, min, max);

Below is an example of a mesh enclosed by an AABB:
 
   
 

There is also a different type of box, called an OBB. OBBs are a bit harder to compute (requiring knowledge of compute eigen vectors, etc). However, they generate the best enclosing volumes and are a bit easier to rotate. Most FPS engines I have seen such as Unreal and Quake stick with AABBs. Many games for consoles such as Rachet-and-Clank for the PS2, etc use spheres to enclose
 meshes.