Portal Engines and
Object-Object Collisions
Portal-based
engines divide a scene or world into smaller convex polyhedral sections.
Convex polyhedra are well-suited for the graphics pipeline because they
eliminate overdraw. Unfortunately, for the purpose of collision detection,
convex polyhedra present us with some difficulties. In some tests that
I performed recently, an average convex polyhedral section in our engine
had about 400 to 500 polygons. Of course, this number varies with every
engine because each engine builds sections using different geometric
techniques. Polygon counts will also vary with each level and world.
 |
|
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.
|
Using
spheres to approximate objects is computationally inexpensive, but because
most geometry in games is square, we should try to use rectangular boxes
to approximate objects. Developers have long used bounding boxes and
this recursive splitting to speed up various ray-tracing routines. In
practice, these methods have manifested as octrees and axis-aligned
bounding boxes (AABBs). Figure 5 shows an AABB and an object inside
it.
 |
|
Figure
5. An object and its AABB.
|
“Axis-aligned”
refers to the fact that either the box is aligned with the world axes
or each face of the box is perpendicular to one coordinate axis. This
basic piece of information can cut down the number of operations needed
to transform such a box. AABBs are used in many of today’s games; developers
often refer to them as the model’s bounding box. Again, the tradeoff
for speed is precision. Because AABBs always have to be axis-aligned,
we can’t just rotate them when the object rotates — they have to be
recomputed for each frame. Still, this computation isn’t difficult and
doesn’t slow us down much if we know the extents of each character model.
However, we still face precision issues. For example, let’s assume that
we’re spinning a thin, rigid rod in 3D, and we’d like to construct an
AABB for each frame of the animation. As we can see, the box approximates
each frame differently and the precision varies (Figure 6).
 |
|
Figure
6. Successive AABBs for a spinning
rod (as viewed from the side).
|
So,
rather than use AABBs, why can’t we use boxes that are arbitrarily oriented
and minimize the empty space, or error, of the box approximation. This
technique is based on what are called oriented bounding boxes (OBBs)
and has been used for ray tracing and interference detection for quite
some time. This technique is not only more accurate, but also more robust
than the AABB technique, as we shall see. However, OBBs are lot more
difficult to implement, slower, and inappropriate for dynamic or procedural
models (an object that morphs, for instance). It’s important to note
that when we subdivide an object into more and more pieces, or volumes,
we’re actually creating a hierarchical tree of that starting volume.
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
Creating
OBB trees from an arbitrary mesh is probably the most difficult part
of the algorithm, and it has to be tweaked and adjusted to suit the
engine or game type. Figure 7 shows the creation of successive OBBs
from a starting model. As we can see, we have to find the tightest box
(or volume, in the case of 3D) around a given model (or set of vertices).
|
|
|
Figure
7. Recursive build of an OBB and its tree.
|
There
are several ways to precompute OBBs, and they all involve a lot of math.
The basic method is to calculate the mean of the distribution of vertices
as the center of the box and then calculate the covariance matrix. We
then use two of the three eigenvectors of the covariance matrix to align
the box with the geometry. We can also use a convex hull routine to
further speed up and optimize tree creation. You can find the complete
derivation in the Gottschalk, Lin, and Manocha paper cited in the “For
Further Info” section.
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.
________________________________________________________
Detecting
Collisions Using Heirarchy Trees
|
|
|
|
Features
