Object/Object Intersection | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This page gives a grid of intersection routines for various popular objects, pointing to resources
in books and on the web. For a unified static and dynamic object intersection and distance library (non-commercial use only, though), see
the TGS collision system. The most comprehensive books on the subject are Guide to source abbreviations: **3DG**-*3D Games: Real-time Rendering and Software Technology*, Alan Watt and Fabio Policarpo, Addison-Wesley, 2001.**GPG**-*Game Programming Gems*, ed. Mark DeLoura, Charles River Media, 2000.**GTCG**-*Geometric Tools for Computer Graphics*, Philip J. Schneider and David H. Eberly, Morgan Kaufmann Publishers, 2002. Good, comprehensive book on this topic.**Gems**- The*Graphics Gems*series. See the book's website for individual book links and code.**IRT**-*An Introduction to Ray Tracing*, ed. Andrew Glassner, Academic Press, 1989.**jgt**-*journal of graphics tools*.**GTweb**- Geometric Tools, Dave Eberly's online computer graphics related software repository. His book*3D Game Engine Design*also covers these, in a readable format, as well as many other object/object intersection tests.**RTCD**-*Real-Time Collision Detection*, by Christer Ericson, Morgan Kaufmann Publishers, 2004.**RTR**-*Real-Time Rendering, Third Edition*, by Tomas Möller, Eric Haines, and Naty Hoffman, A.K. Peters Ltd., 2008.**RTR2**-*Real-Time Rendering, Second Edition*, by Tomas Akenine-Möller and Eric Haines, A.K. Peters Ltd., 2002.**SG**- Simple Geometry library, Steve Baker's vector, matrix, and quaternion manipulation library.**TGS**- Talina Gaming System Collision, Andrew Aye's object/object intersection/distance and sweep/penetration software (non-commercial use only).**TVCG**- IEEE Transactions on Visualization and Computer Graphics.
Journal of Graphics Tools for other relevant articles.
Individual article references follow after the table.
## Static Object IntersectionsEntries are listed from oldest to newest, so often thelast entry is the best. This table covers objects not moving; see the next section for dynamic objects.
References are listed in historical order, so it's usually best to look at the last reference first. References in parentheses indicate algorithms that will work, but are not optimized for the particular primitives. Note that all AABB algorithms can also be used for OBB intersections (simply transform the other primitive to the OBB's space), so we do not list these in the table. ## Dynamic Object IntersectionsThese are intersections in which the objects are moving relative to one another. Linear motion (only) is assumed; there is research on rotational motion collision detection, not covered here. The TGS collision system (non-commercial use only) has many methods in this area, and the bookReal-Time Collision Detection covers the subject in some depth. One principle is that even if both objects are moving, only one has to be considered moving. That is, one object's movement vector can be subtracted from both objects, leaving one object at rest. Another principle is to perform a Minkowski sum of the moving sphere with the other object, then shrink the sphere to a ray. A set of static intersection tests are used in many of these tests, so look in the table above for these. The tests below are categorized as boolean, i.e., whether the objects intersect at all, or location, where the actual intersection location where the two moving objects first hit is formed. (Please let me know if you have simple ways of making a given boolean test into a location test.)
The general principal of intersecting a moving sphere against an object is to simplify thinking about the problem by making the sphere into a line segment between its center's start and end locations, while "adding" this sphere (a Minkowski sum) to the other object.
Many of the non-curved objects which are moving can be treated as forming shafts between the starting and ending locations, and then the shaft can be tested against a ray simply enough, or against another non-curved object by using the polyhedron/polyhedron test in Gems IV p.83. Another approach is to use the Separating Axis Theorem (also see Bobic) to tell if the two objects overlap. However, all of these approaches are just
## Article referencesBobic - Bobic, Nick, "Advanced Collision Detection Techniques," Gamasutra, March 2000.
Gomez - Gomez, Miguel, "Simple Intersection Tests for Games," Gamasutra, October 1999.
Schroeder - Schroeder, Tim, "Collision Detection Using Ray Casting," Game Developer Magazine, pp. 50-57, August 2001. Code is on the web.
## Graphics Gems referencesRay/ray: Ronald Goldman, Intersection of Two Lines in Three-Space, Graphics Gems, p. 304.Ray/sphere: Jeff Hultquist, Intersection of a Ray with a Sphere, Graphics Gems, pp. 388-389.Ray/cylinder: Joseph M. Cychosz and Warren N. Waggenspack, Jr., Intersecting a Ray with a Cylinder, Graphics Gems IV, pp. 356-365, includes code.Ray/polygon: Eric Haines, Point in Polygon Strategies, Graphics Gems IV, pp. 24-46, includes code.Ray/cone: Ching-Kuang Shene, Computing the Intersection of a Line and a Cone, Graphics Gems V, pp. 227-231.Ray/AABB: Andrew Woo, Fast Ray-Box Intersection, Graphics Gems, pp. 395-396, includes code.Ray/polyhedron: Eric Haines, Fast Ray-Convex Polyhedron Intersection, Graphics Gems II, pp. 247-250, includes code.
## AlgorithmsScalar values are lowercase italic:a, n, t. Vectors are lowercase bold: p, v, x. Matrices are uppercase bold: M, T. "X" denotes a cross product, "^2" means "squared", "||x||" means the length of vector x.
The solution is: and
If the lines are parallel, the denominator ||
If the lines do not intersect, |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||