Contents |
|
![]() |
Figure 8. Separating
axis (intervals A and B don’t overlap). |
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
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
![]() |
Figure 9. Hull of a
curved object. |
Decide for Yourself
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 mailto:%20nickb@cagedent.com.
________________________________________________________