Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Gamasutra: The Art & Business of Making Gamesspacer
Advanced Collision Detection Techniques
View All     RSS
July 12, 2020
arrowPress Releases
July 12, 2020
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Advanced Collision Detection Techniques

March 30, 2000 Article Start Previous Page 2 of 3 Next

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.

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).

Figure 3. In a sphere-sphere intersection, the routine may report that collision has occurred when it really hasn’t.

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.

Article Start Previous Page 2 of 3 Next

Related Jobs

Remedy Entertainment
Remedy Entertainment — Espoo, Finland

Programmer (Character Technology team)
Square Enix Co., Ltd.
Square Enix Co., Ltd. — Tokyo, Japan

Experienced Game Developer
Klang Games GmbH
Klang Games GmbH — Berlin, Germany

AI Engineer (f/m/d)
Remedy Entertainment
Remedy Entertainment — Helsinki, Finland

Technical Director

Loading Comments

loader image