Portal Engines and ObjectObject Collisions
Portalbased engines divide a scene or world into smaller convex polyhedral sections. Convex polyhedra are wellsuited 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 spheresphere 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 raytracing routines. In practice, these methods have manifested as octrees and axisaligned bounding boxes (AABBs). Figure 5 shows an AABB and an object inside it.

Figure 5. An object and its AABB. 
“Axisaligned” 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 axisaligned, 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 fastaction 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 topdown approach whereby we begin with the starting volume and recursively subdivide it. Alternatively, we could use a bottomup 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