Contents

The Big Picture Portal Engines and Object-Object Collisions Detecting Collisions Using Heirarchy Trees

Detecting Collisions Using Hierarchy Trees

Now, let’s assume that we have either our OBB or AABB trees. How do we actually perform collision detection? We’ll take two trees and check whether two initial boxes overlap. If they do, they might intersect, and we’ll have to recursively process them further (recursive descent). If, along the descent, we find that the subtrees do not intersect, we can stop and conclude that no intersection has occurred. If we find that the subtrees do intersect, we’ll have to process the tree until we hit its leaf nodes to find out which parts overlap. So, the only thing we have to figure out is how to check whether two boxes overlap. One of the tests that we could perform would be to project the boxes on some axis in space and check whether the intervals overlap. If they don’t, the given axis is called a separating axis (Figure 8).

Figure 8. Separating axis (intervals A and B don’t overlap).

To check quickly for overlap, we’ll use something called the Separating Axis Theorem. This theorem tells us that we have only 15 potential separating axes. If overlap occurs on every single separating axis, the boxes intersect. Thus, it’s very easy to determine whether or not two boxes intersect.

Interestingly, the time gradient problem mentioned earlier could easily be solved by the separating axis technique. Remember that the problem involved determining whether a collision has occurred in between any two given times. If we add velocities to the box projection intervals and they overlap on all 15 axes, then a collision has occurred. We could also use an structure that resembles an AABB tree to separate colliders and collidees and check whether they have a possibility of collision. This calculation can quickly reject the majority of the cases in a scene and will perform in an O(N logN) time that is close to optimal.

Collision Techniques Based on BSP Trees

BSP (Binary Space Partitioning) trees are another type of space subdivision technique that’s been in use for many years in the game industry (Doom was the first commercial game that used BSP trees). Even though BSP trees aren’t as popular today as they have been over the past couple of years, the three most licensed game engines today — Quake II, Unreal, and Lithtech — still use them quite extensively. The beauty and extreme efficiency of BSP trees comes to light when we take a look at collision detection. Not only are BSP trees efficient for geometry culling, we also get very efficient world-object collision almost for free.

The BSP tree traversal is the fundamental technique used with BSPs. Collision detection basically is reduced to this tree traversal, or search. This approach is powerful because it rejects a lot of geometry early, so in the end, we only test the collision detection against a small number of planes. As we’ve seen before, finding a separating plane between two objects is sufficient for determining that those two objects don’t intersect. If a separating plane exists, no collision has occurred. So, we can recursively traverse a world’s tree and check whether separating planes intersect the bounding sphere or bounding box. We can increase the accuracy of this approach by checking for every one of the object’s polygons. The easiest way to perform this check is to test whether all parts of the object are on the same side of the plane. This calculation is extremely simple. We can use the Cartesian plane equation, ax + by + cz + d = 0, to determine the side of the plane upon which the point lies. If the equation is satisfied, then our point lies on the plane. If ax + by + cz + d > 0, then the point is on the positive side the plane. If ax + by + cz + d < 0, then the point is on the negative side the plane.

The only important thing to note is that for a collision not to occur, all of the points of an object (or a bounding box) have to be on either the positive or the negative side of a given plane. If we have points on both the positive and negative side of the plane, a collision has occurred and the plane intersects the given object.

Unfortunately, we have no elegant way of checking whether a collision has occurred in between the two intervals (although the techniques discussed at the beginning of this article still apply). However, I have yet to see another structure that has as many uses as a BSP tree.

Curved Objects and Collision Detection

Now that we’ve seen two approaches to collision detection for polygonal objects, lets see how we can compute the collision of curved objects. Several games will be coming out in 1999 that use curved surfaces quite extensively, so the efficient collision detection of curved surfaces will be very important in the coming year. The collision detection (which involves exact surface evaluation at a given point) of curved surfaces is extremely computationally intensive, so we’ll try to avoid it. We’ve already discussed several methods that we could use in this case, as well. The most obvious approach is to approximate the curved surface with a lowest-tessellation representation and use this polytope for collision detection. An even easier, but less accurate, method is to construct a convex hull out of the control vertices of the curved surface and use it for the collision detection. In any case, curved surface collision approximation is very similar to general polytope collision detection. Figure 9 shows the curved surface and the convex hull formed from the control vertices.

Figure 9. Hull of a curved object.

If we combined both techniques into a sort of hybrid approach, we could first test the collision against the hull and then recursively subdivide the patch to which the hull belongs, thus increasing the accuracy tremendously.

Decide for Yourself

Now that we’ve gone over some of the more advanced collision detection schemes (and some basic ones, too), you should be able to decide what type of system would best suit your own game. The main thing you’ll have to decide is how much accuracy you’re willing to sacrifice for speed, simplicity of implementation (shorter development time), and flexibility.

For Further Info

• H. Samet. Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods. Addison Wesley, 1989.

• For more information about AABBs take a look at J. Arvo and D. Kirk. “A survey of ray tracing acceleration techniques,” An Introduction to Ray Tracing. Academic Press, 1989.

• For a transformation speedup, check out James Arvo’s paper in Andrew S. Glassner, ed. Graphics Gems. Academic Press, 1990.

• S. Gottschalk, M. Lin, and D. Manocha. “OBBTree: A hierarchical Structure for rapid interference detection,” Proc. Siggraph 96. ACM Press, 1996. has contributed a great deal to the discussion of OBBs in terms of accuracy and speed of execution.

• S. Gottschalk. Separating Axis Theorem, TR96-024, UNC Chapel Hill, 1990.

• N. Greene. “Detecting intersection of a rectangular solid and a convex polyhedron,” Graphics Gems IV. Academic Press, 1994. introduces several techniques that speed up the overlap computation of a box and a convex polyhedron.

Nick Bobic is trying not to work 14 hours a day with very little success. Any new collision tips and tricks should be sent to nickb@cagedent.com.

________________________________________________________

[Back to] The Big Picture