3D Programming - Weekly : Bounding Boxes

Bounding Box Types

This article gives an overview of oriented bounding boxes, including source code. An oriented box is allowed to rotate freely, unlike a axis-aligned bounding box, which always remains aligned to the x,y, and z axes. Tests with oriented bounding boxes are more complicated, and thus slower, but they're also more accurate. I could also mention that spheres can be used as the least accurate bounding type, but I won't since I put Box Types in the section title =)

Data Structure

To store the box, we need to store a centerpoint, a rotation, and how far the box extends from the centerpoint in the x,y,z directions. I use a 4x4 matrix to store the rotation and centerpoint translation, and a vector for the Extents. I just chose to use a 4x4 matrix for simplicity so I could use the matrix class. An alternative to storing extents and a centerpoint is storing the minimum corner and maximum corner, so I have a set function that converts from this format.

Functions

This class contains the following functions:

IsPointInBox: Tests if a point is in the box.
IsSphereInBox: Tests if any part of a sphere is inside the box. A possible use is to determine which objects a light hits using the light radius and position as its sphere of influence.
BoxOutsidePlane: Tests if a box is completely behind a plane. It could be used in culling, including frustum culling.
IsLineInBox : Tests if a line segment intersects the box. This could be used as an initial quick test for things like line of sight, a selection ray, or a bullet shot.
IsBoxInBox: Tests if any part of another box is inside the box, using the separating axes test. Could be used to test for intersections between two objects. Also you could divide a level into various sector boxes, and use this to test which sectors and object is in.

Code Download

bbox.h( 2KB ), bbox.cpp ( 5KB ) : An oriented bounding box class. The code uses the matrix and vector classes from earlier articles, although a needed function or two might be missing. The code is commented enough to give a general idea of how the class and algorithms used work. (I've updated the BoxOutsidePlane function with a more sensible one.)

External Link

A while after I had first written a bounding box class, I found this article which inspired some code changes. It also goes into much more detail than I did here.