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 Geometric Tools for Computer Graphics (GTCG) and Real-Time Collision Detection (RTCD); the former is all-encompassing, the latter more approachable and focused.

Guide to source abbreviations:

Check the intersection testing page of the Journal of Graphics Tools for other relevant articles.

Individual article references follow after the table.

Static Object Intersections

Entries are listed from oldest to newest, so often the last entry is the best. This table covers objects not moving; see the next section for dynamic objects.

  ray plane sphere cylinder cone triangle AABB OBB frustum polyhedron  
ray Gems p.304;
SG;
TGS;
RTCD p.198;
SoftSurfer;
RTR2 p.618;
RTR3 p.781
IRT p.50,88;
SG;
GTCG p.482;
TGS;
RTCD p.175;
SoftSurfer (more)
IRT p.39,91;
Gems p.388;
Held jgt 2(4);
GTweb;
3DG p.16;
GTCG p.501;
TGS;
RTCD p.127,177;
RTR2 p.568;
RTR3 p.738
IRT p.91;
Gems IV p.356;
Held jgt 2(4);
GTweb;
GTCG p.507;
TGS;
RTCD p.194
IRT p.91;
Gems V p.227;
Held jgt 2(4);
GTweb;
GTCG p.512
Möller-Trumbore jgt 2(1);
IRT p.53,102;
Gems IV p.24;
Held jgt 2(4);
GTweb;
3DG p.17;
Möller;
GTCG p.485;
TGS;
RTCD p.153,184;
Lofstedt jgt 10(2);
Chirkov jgt 10(3);
Lagae jgt 10(4);
SoftSurfer;
RTR2 p.578;
RTR3 p.746;
Havel TVCG June 2009
IRT p.65,104;
Gems p.395;
Smits;
3DG p.20;
Terdiman (optimized Woo);
Schroeder;
GTCG p.626;
TGS;
RTCD p.179;
Mahovsky jgt 9(1);
Williams jgt 10(1);
Eisemann jgt 12(4) (code);
RTR2 p.572;
RTR3 p.742
(IRT p.104;
Gems II p.247);
GTweb;
Gomez;
GTCG p.630;
TGS;
RTCD p.179;
RTR2 p.572;
RTR3 p.743
(IRT p.104;
Gems II p.247)
IRT p.104;
Gems II p.247;
GTCG p.493;
Platis jgt 8(4);
RTCD p.198;
SoftSurfer
ray
plane IRT p.50,88;
SG;
GTCG p.482;
TGS;
RTCD p.175;
SoftSurfer (more)
GTweb;
SG;
GTCG p.529;
RTCD p.207
distance of
center to plane
<= radius;
GTweb;
Gomez;
GTCG p.548;
TGS;
RTCD p.160,219
GTweb;
GTCG p.551;
TGS;
GTCG p.563;
RTCD p.164
Check if all
vertices are
on one side;(Möller jgt 2(2));
GTCG p.534;
SoftSurfer
Gems IV p.74;
GTCG p.634;
TGS;
RTCD p.161,222;
RTR2 p.587;
RTR3 p.755
GTweb;
Gomez;
GTCG p.635;
TGS;
RTCD p.161;
RTR2 p.588;
RTR3 p.757
    plane
sphere IRT p.39,91;
Gems p.388;
Held jgt 2(4);
GTweb;
3DG p.16;
GTCG p.501;
TGS;
RTCD p.127,177;
RTR2 p.568;
RTR3 p.738
distance of
center to plane
<= radius;
GTweb;
Gomez;
GTCG p.548;
TGS;
RTCD p.160,219
If radii A+B >=
center/center distance;
Held jgt 2(4);
GTweb;
Gomez;
GPG p.390;
GTCG p.602;
TGS;
RTCD p.88,215,223;
RTR3 p.763
If radii A+B >=
center/axis distance;
Held jgt 2(4);
(GTCG p.602);
TGS;
RTCD p.114
GTweb;
(GTCG p.602)
Held jgt 2(4);
GTweb;
Karabassi jgt 4(1);
TGS;
RTCD p.135,167,226
Gems p.335;
Gomez;
GTCG p.644;
TGS;
RTCD p.130,165,228;
RTR2 p.599;
RTR3 p.763
TGS;
RTCD p.132,166
GTweb;
Assarsson;
GPG p.433;
3DG p.302;
RTR2 p.609;
RTR3 p.774
3DG p.462;
RTCD p.142
sphere
(capped) cylinder IRT p.91;
Gems IV p.356;
Held jgt 2(4);
GTweb;
GTCG p.507;
TGS;
RTCD p.194
GTweb;
GTCG p.551;
TGS;
If radii A+B >=
center/axis distance;
Held jgt 2(4);
(GTCG p.602);
TGS;
RTCD p.114
If radii A+B >=
axis/axis distance;
GTweb;
GTCG p.602,646;
TGS;
RTCD p.114
(GTCG p.602) Held jgt 2(4);
TGS
TGS TGS GPG p.380   (capped) cylinder
(capped) cone IRT p.91;
Gems V p.227;
Held jgt 2(4);
GTweb;
GTCG p.512
GTCG p.563;
RTCD p.164
GTweb;
(GTCG p.602)
(GTCG p.602) (GTCG p.602) Held jgt 2(4);
GTweb;
GTCG p.583
        (capped) cone
triangle (polygon) Möller-Trumbore jgt 2(1);
IRT p.53,102;
Gems IV p.24;
Held jgt 2(4);
GTweb;
3DG p.17;
Möller;
GTCG p.485;
TGS;
RTCD p.153,184;
Lofstedt jgt 10(2);
Chirkov jgt 10(3);
Lagae jgt 10(4);
SoftSurfer;
RTR2 p.578;
RTR3 p.746
Check if all
vertices are
on one side;(Möller jgt 2(2));
GTCG p.534;
SoftSurfer
Held jgt 2(4);
GTweb;
Karabassi jgt 4(1);
TGS;
RTCD p.135,167,226
Held jgt 2(4);
TGS
Held jgt 2(4);
GTweb;
GTCG p.583
Möller jgt 2(2);
Held jgt 2(4);
GTweb;
Möller;
GPG p.393;
GTCG p.539;
TGS;
RTCD p.155,172;
Shen jgt 8(1);
Guigue jgt 8(1);
SoftSurfer;
RTR2 p.590;
RTR3 p.757
Gems III p.236;
Gems V p.375;
TGS;
RTCD p.169;
Möller;
RTR2 p.596;
RTR3 p.760
GTweb;
TGS
homogeneous clipping:
Gems p.84
generalized clipping triangle (polygon)
axis-aligned bounding box IRT p.65,104;
Gems p.395;
Smits;
3DG p.20;
Terdiman (optimized Woo);
Schroeder;
GTCG p.626;
TGS;
RTCD p.179;
Mahovsky jgt 9(1);
Williams jgt 10(1);
Eisemann jgt 12(4);
RTR2 p.572;
RTR3 p.742
Gems IV p.74;
GTCG p.634;
TGS;
RTCD p.161,222;
RTR2 p.587;
RTR3 p.755
Gems p.335;
Gomez;
GTCG p.644;
TGS;
RTCD p.130,165,228;
RTR2 p.599;
RTR3 p.763
TGS   Gems III p.236;
Gems V p.375;
TGS;
RTCD p.169;
Möller;
RTR2 p.596;
RTR3 p.760
A.LO<=B.HI &&
A.HI>=B.LO;
Gomez;
3DG p.445;
GTCG p.637;
TGS;
RTCD p.79,230;
RTR2 p.600;
RTR3 p.765
(Gems V p.378;
GTweb;
Gomez;
GTCG p.639);
TGS;
RTR2 p.602;
RTR3 p.777
(Gems IV p.83);
(Gems V p.378);
(GTweb);
Assarsson;
3DG p. 302;(
GTCG p.624);
RTR2 p.612;
RTR3 p.771
Gems IV p.74;
Gems V p.378
axis-aligned bounding box
oriented bounding box (IRT p.104;
Gems II p.247);
GTweb;
Gomez;
GTCG p.630;
TGS;
RTCD p.179;
RTR2 p.572;
RTR3 p.743
GTweb;
Gomez;
GTCG p.635;
TGS;
RTCD p.161;
RTR2 p.588;
RTR3 p.757
TGS;
RTCD p.132,166
TGS   GTweb;
TGS
(Gems V p.378;
GTweb;
Gomez;
GTCG p.639);
TGS;
RTR2 p.602;
RTR3 p.777
GTweb;
Gomez;
3DG p.449;
GTCG p.639;
TGS;
RTCD p.101;
RTR2 p.602;
RTR3 p.767
GTweb;
Assarsson;
GTCG p.624;
RTR2 p.612;
RTR3 p.777
(Gems IV p.83) oriented bounding box
viewing frustum (IRT p.104;
Gems II p.247)
  GTweb;
Assarsson;
GPG p.433;
3DG p.302;
RTR2 p.609;
RTR3 p.774
GPG p.380   homogeneous clipping:
Gems p.84
(Gems IV p.83);
(Gems V p.378);
(GTweb);
Assarsson;
3DG p. 302;(
GTCG p.624);
RTR2 p.612;
RTR3 p.771
GTweb;
Assarsson;
GTCG p.624;
RTR2 p.612;
RTR3 p.777
(Gems IV p.83) (Gems IV p.83) viewing frustum
convex polyhedron IRT p.104;
Gems II p.247;
GTCG p.493;
Platis jgt 8(4);
RTCD p.198;
SoftSurfer
  3DG p.462;
RTCD p.142
    generalized clipping Gems IV p.74;
Gems V p.378
(Gems IV p.83) (Gems IV p.83) Gems IV p.83;
3DG p.453;(
GTweb;
RTR2 p.563;
RTR3 p.731);
GTCG p.726;
Ganovelli jgt 7(2);
RTCD p.383,399,410
convex polyhedron

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 Intersections

These 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 book Real-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.)

Ray/Moving Sphere: (location) Form a cylinder between the two spheres, intersect the two spheres and cylinder with the ray. See Schroeder for code.
Ray/Moving Triangle: (boolean) If each triangle is entirely on one side of the plane formed by the other triangle, form the polyhedron between the two triangles. The connecting faces are formed by all the combinations of an edge on one triangle and a vertex on the other. Discard any separating planes formed (i.e., use only planes in which both triangles are on the same side of the plane). Shoot the ray against it using ray/polyhedron testing. (Short of splitting the triangles into two parts each and forming volumes amongst these, is there an elegant way to perform this operation when one triangle's plane splits the other triangle?)
Ray/Moving AABB: (boolean) Form a shaft (paper) between the beginning and ending position of the AABB and shoot the ray against it using ray/polyhedron testing. See RTR2, p. 614.
Ray/Moving OBB: (boolean) An inelegant way is to form all combinations of edge/vertex pairs and form planes to bound the OBBs (see Ray/Moving triangle, above). (Is there something more elegant?)

Plane/Moving Sphere: (location) Transform the problem into changing the plane into a thick slab, of thickness equal to the radius of the sphere. Change the sphere's path into a line segment. Perform slab/line segment intersection, i.e., ray/plane intersection for the two sides of the slab. See Gomez; and RTR2, p. 621.
Plane/Moving AABB: (location) If the plane's normal is along one of the primary axes, e.g., it is [0 1 0], [0 0 -1], etc., then turn the problem into slab/line segment intersection, similar to plane/moving sphere above. That is, take the thickness of the AABB and make the plane this thick.

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.
Moving Sphere/Sphere: (location) Add the radius of the moving sphere to the static sphere, and treat the moving sphere as a ray. Use this ray to perform ray/sphere intersection. See Gomez; Schroeder for code (article has bug in derivation, code is fine); and RTR2, p. 622.
Moving Sphere/Triangle: (location) Similar to above, turn the sphere into a ray. The triangle turns into a solid defined by a set of spheres at the vertices, cylinders along the edges, and a slab for the interior of the triangle. See Rouwé's article and code, Schroeder for code (article has bug in derivation, code is fine), and RTR2 p. 624.
Moving Sphere/AABB: (boolean) A conservative test (i.e., no false misses, but can give false hits when there actually is no overlap) is to make the AABB move, so forming a shaft (paper) between the beginning and ending position of the AABB. Test the static sphere with shaft testing. See RTR2, p. 614.

Moving AABB/AABB: (location) See Gomez for a use of the Separating Axis Theorem to solve this problem. (boolean) Form a shaft (paper) between the beginning and ending position of the AABB and compare the static AABB against it with shaft testing. See RTR2, p. 614.

Moving Convex Polyhedra/Convex Polyhedra: (boolean) The GTCG book, p. 615 on, gives pseudocode for using the method of separating axes to solve this problem.

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 boolean tests. Also see RTR p. 322; RTR2, p. 627.

Article references

Bobic - 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 references

Ray/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.

Plane/AABB and AABB/polyhedron: Ned Greene, Detecting Intersection of a Rectangular Solid and a Convex Polyhedron, Graphics Gems IV, pp. 74-82.

Sphere/AABB: Jim Arvo, A Simple Method for Box-Sphere Intersection Testing, Graphics Gems, pp. 247-250, includes code.

Triangle/AABB: Doug Voorhies, Triangle-Cube Intersection, Graphics Gems III, pp. 236-239, includes code.
Triangle/AABB and AABB/polyhedron: Green and Hatch, Fast Polygon-Cube Intersection Testing, Graphics Gems V, pp. 375-379, includes code.
Triangle/frustum: Paul Heckbert, Generic Convex Polygon Scan Conversion and Clipping, Graphics Gems, pp. 84-86, includes code.

Polyhedron/polyhedron: Rich Rabbitz, Fast Collision Detection of Moving Convex Polyhedra, Graphics Gems, pp. 83-109, includes code.

Algorithms

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

Ray/ray: (after Goldman, Graphics Gems; see his article for the derivation) Define each ray by an origin o and a normalized (unit vector) direction d. The two lines are then

L1(t1) = o1 + d1*t1
L2(t2) = o2 + d2*t2

The solution is:
t1 = Determinant{(o2-o1),d2,d1 X d2} / ||d1 X d2||^2

and

t2 = Determinant{(o2-o1),d1,d1 X d2} / ||d1 X d2||^2

If the lines are parallel, the denominator ||d1 X d2||^2 is 0.

If the lines do not intersect, t1 and t2 mark the points of closest approach on each line.