Contents |
|
![]() |
Figure 3. In a sphere-sphere intersection, the routine may report that collision has occurred when it really hasn’t. |
Determining whether an object’s polygons penetrate the world
polygons can be computationally expensive. One of the most primitive ways
of doing collision detection is to approximate each object or a part of
the object with a sphere, and then check whether spheres intersect each
other. This method is widely used even today because it’s computationally
inexpensive. We merely check whether the distance between the centers of
two spheres is less than the sum of the two radii (which indicates that a
collision has occurred). Even better, if we calculate whether the distance
squared is less than the sum of the radii squared, then we eliminate that
nasty square root in our distance calculation. However, while the
calculations are simple, the results are extremely imprecise (Figure
3).
But what if we use this imprecise method as simply a first step.
We represent a whole character as one big sphere, and then check whether
that sphere intersects with any other object in the scene. If we detect a
collision and would like to increase the precision, we can subdivide the
big sphere into a set of smaller spheres and check each one for collision
(Figure 4). We continue to subdivide and check until we are satisfied with
the approximation. This basic idea of hierarchy and subdivision is what
we’ll try to perfect to suit our needs.
![]() |
Figure 4. Sphere
subdivision. |
![]() |
Figure 5. An
object and its AABB. |
![]() |
Figure 6. Successive
AABBs for a spinning rod (as viewed from the side). |
Our choice between AABBs and OBBs should be based upon the level
of accuracy that we need. For a fast-action 3D shooter, we’re probably
better off implementing AABB collision detection — we can spare a little
accuracy for the ease of implementation and speed. The source code that
accompanies this article is available from the Game Developer web site. It
should get you started with AABBs, as well as providing some examples of
source code from several collision detection packages that also implement
OBBs. Now that we have a basic idea of how everything works, let’s look at
the details of the implementation.
Building Trees
![]() |
Figure 7. Recursive
build of an OBB and its
tree. |
Building AABB trees is much easier because we don’t have to find
the minimum bounding volume and its axis. We just have to decide where to
split the model and we get the box construction for free (because it’s a
box parallel with the coordinate axes and it contains all of the vertices
from one side of the separating plane).
So, now that we have all of the boxes, we have to construct a
tree. We could use a top-down approach whereby we begin with the starting
volume and recursively subdivide it. Alternatively, we could use a
bottom-up approach, merging smaller volumes to get the largest volume. To
subdivide the largest volume into smaller ones, we should follow several
suggested rules. We split the volume along the longest axis of the box
with a plane (a plane orthogonal to one of its axes) and then partition
the polygons based upon which side of the partitioning axis they fall
(Figure 7). If we can’t subdivide along the longest axis, we subdivide
along the second longest. We continue until we can’t split the volume any
more, and we’re left with a triangle or a planar polygon. Depending on how
much accuracy we really need (for instance, do we really need to detect
when a single triangle is collided?), we can stop subdividing based on
some arbitrary rule that we propose (the depth of a tree, the number of
triangles in a volume, and so on).
As you can see, the building phase is quite complex and involves a
considerable amount of computation. You definitely can’t build your trees
during the run time — they must be computed ahead of time. Precomputing
trees eliminates the possibility of changing geometry during the run time.
Another drawback is that OBBs require a large amount of matrix
computations. We have to position them in space, and each subtree has to
be multiplied by a matrix.
________________________________________________________