Ray Tracing Resources Page

This page gives a grid of intersection routines for various popular objects, pointing to resources in books and on the web. 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. A book focused in large part on object/object intersection tests is the Game Physics Cookbook (GPC), with code - see its giant grid for what intersections it covers. Quílez has a bunch of shader-based ray/object intersectors, including ones (beyond those listed in the table) for the torus, disk, and capsule.

Guide to source abbreviations:

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;
SoftSurfercode;
RTR4 p.989
IRT p.50,88;
SG;
GTCG p.482;
TgS;
RTCD p.175;
SoftSurfer (more): code;
GPC;
Graphics Codex
IRT p.39,91;
Gems p.388;
Held jgt 2(4);
GTweb;
3DG p.16;
GTCG p.501;
TgS;
RTCD p.127,177;
Graphics Codex;
RTR4 p.955;
GPC;
Shadertoy (demo)
IRT p.91;
Gems IV p.356;
Held jgt 2(4);
GTweb;
GTCG p.507;
TgS;
RTCD p.194;
Shadertoy (demo);
Wikipedia
IRT p.91;
Gems V p.227;
Held jgt 2(4);
GTweb doc;
GTCG p.512
Möller-Trumbore jgt 2(1)code (mirror), paper draft;
IRT p.53,102;
Gems IV p.24;
Held jgt 2(4);
GTweb;
3DG p.17;
Möller (mirror);
GTCG p.485;
TgS;
RTCD p.153,184;
Löfstedt jgt 10(2)codepaper draft
Chirkov jgt 10(3)code;
Lagae jgt 10(4)codepaper draft;
SoftSurfercode;
Havel TVCG June 2009;
Woop JCGT 2(1);
Baldwin JCGT 5(3);
GPC;
Graphics Codex;
RTR4 p.962;
Shadertoy (demo)
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) (code);
Eisemann jgt 12(4) (code);
Shirley 2016;
GPC;
Chatzianastasiou;
Majercik JCGT 7(3);
RTR4 p.959;
Wiche;
Shadertoy (demo)
(IRT p.104;
Gems II p.247);
GTweb;
Gomez;
GTCG p.630;
TgS;
RTCD p.179;
Shadertoy GPC;
RTR4 p.960;
(demo)
(IRT p.104;
Gems II p.247)
IRT p.104;
Gems II p.247;
GTCG p.493;
Platis jgt 8(4);
RTCD p.198;
SoftSurfercode
ray
plane IRT p.50,88;
SG;
GTCG p.482;
TgS;
RTCD p.175;
SoftSurfer (more): code;
GPC;
Graphics Codex
GTweb;
SG;
GTCG p.529;
RTCD p.207;
GPC
distance of
center to plane
<= radius;
GTweb;
Gomez;
GTCG p.548;
TgS;
RTCD p.160,219;
GPC
GTweb;
GTCG p.551;
TgS;
GTweb doc
GTCG p.563;
RTCD p.164
Check if all
vertices are
on one side;(Möller jgt 2(2));
GTCG p.534;
SoftSurfercode;
GPC
Gems IV p.74;
GTCG p.634;
TgS;
RTCD p.161,222;
GPC;
RTR4 p.970
GTweb;
Gomez;
GTCG p.635;
TgS;
RTCD p.161;
GPC;
RTR4 p.972
    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;
Graphics Codex;
RTR4 p.955;
GPC;
Shadertoy (demo)
distance of
center to plane
<= radius;
GTweb;
Gomez;
GTCG p.548;
TgS;
RTCD p.160,219;
GPC
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;
Ellipsoids: GTweb doc;
GPC;
RTR4 p.976
If radii A+B >=
center/axis distance;
Held jgt 2(4);
(GTCG p.602);
TgS;
RTCD p.114
GTweb;
GTweb doc;
(GTCG p.602);
Hale
Held jgt 2(4);
GTweb;
Karabassi jgt 4(1);
TgS;
RTCD p.135,167,226;
GPC
Gems p.335;
Gomez;
GTCG p.644;
TgS;
RTCD p.130,165,228;
Ellipsoid: GTweb doc;
GPC;
RTR4 p.977
TgS;
RTCD p.132,166
Larsson;
GPC
GTweb;
Assarsson;
GPG p.433;
3DG p.302;
GPC;
RTR4 p.984
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;
Shadertoy (demo);
Wikipedia
GTweb;
GTCG p.551;
TgS;
GTweb doc
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 doc;
GTweb doc;
GTCG p.602,646;
TgS;
RTCD p.114
(GTCG p.602) Held jgt 2(4);
TgS;
GTweb doc
TgS TgS GPG p.380   (capped) cylinder
(capped) cone IRT p.91;
Gems V p.227;
Held jgt 2(4);
GTweb doc;
GTCG p.512
GTCG p.563;
RTCD p.164
GTweb;
GTweb doc;
(GTCG p.602);
Hale
(GTCG p.602) (GTCG p.602) Held jgt 2(4);
GTweb doc;
GTCG p.583
GTWeb doc GTweb doc     (capped) cone
triangle (polygon) Möller-Trumbore jgt 2(1)code (mirror), paper draft;
IRT p.53,102;
Gems IV p.24;
Held jgt 2(4);
GTweb;
3DG p.17;
Möller (mirror);
GTCG p.485;
TgS;
RTCD p.153,184;
Löfstedt jgt 10(2)codepaper draft
Chirkov jgt 10(3)code;
Lagae jgt 10(4)codepaper draft;
SoftSurfercode;
Havel TVCG June 2009;
Woop JCGT 2(1);
Baldwin JCGT 5(3);
GPC;
Graphics Codex;
RTR4 p.962;
Shadertoy (demo)
Check if all
vertices are
on one side;(Möller jgt 2(2));
GTCG p.534;
SoftSurfercode;
GPC
Held jgt 2(4);
GTweb;
Karabassi jgt 4(1);
TgS;
RTCD p.135,167,226;
GPC
Held jgt 2(4);
TgS;
GTweb doc
Held jgt 2(4);
GTweb doc;
GTCG p.583
Möller jgt 2(2);
Held jgt 2(4);
GTweb;
Möller (mirror);
GPG p.393;
GTCG p.539;
TgS;
RTCD p.155,172;
Shen jgt 8(1);
Guigue jgt 8(1)code;
SoftSurfercode;
GTweb doc;
GPC;
RTR4 p.972
Gems III p.236;
Gems V p.375;
TgS;
RTCD p.169;
Möller;
GPC;
RTR4 p.974
GTweb;
GTweb doc
TgS;
GPC
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) (code);
Eisemann jgt 12(4) (code);
Shirley 2016;
GPC;
Chatzianastasiou;
Majercik JCGT 7(3);
RTR4 p.959;
Wiche;
Shadertoy (demo)
Gems IV p.74;
GTCG p.634;
TgS;
RTCD p.161,222;
GPC;
RTR4 p.970
Gems p.335;
Gomez;
GTCG p.644;
TgS;
RTCD p.130,165,228;
Ellipsoid: GTweb doc;
GPC;
RTR4 p.977
TgS GTWeb doc Gems III p.236;
Gems V p.375;
TgS;
RTCD p.169;
Möller;
GPC;
RTR4 p.974
A.LO<=B.HI &&
A.HI>=B.LO;
Gomez;
3DG p.445;
GTCG p.637;
TgS;
RTCD p.79,230;
GPC;
RTR4 p.978
(Gems V p.378;
GTweb;
Gomez;
GTCG p.639);
TgS;
GPC
(Gems IV p.83);
(Gems V p.378);
(GTweb);
Assarsson;
3DG p. 302;(
GTCG p.624);
GPC;
RTR4 p.986
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;
Shadertoy GPC;
RTR4 p.960;
(demo)
GTweb;
Gomez;
GTCG p.635;
TgS;
RTCD p.161;
GPC;
RTR4 p.972
TgS;
RTCD p.132,166
Larsson;
GPC
TgS GTweb doc GTweb;
GTweb doc
TgS;
GPC
(Gems V p.378;
GTweb;
Gomez;
GTCG p.639);
TgS;
GPC
GTweb;
Gomez;
3DG p.449;
GTCG p.639;
TgS;
RTCD p.101;
GTweb doc;
GPC;
RTR4 p.980
GTweb;
GTweb doc;
Assarsson;
GTCG p.624;
GPC
(Gems IV p.83) oriented bounding box
viewing frustum (IRT p.104;
Gems II p.247)
  GTweb;
Assarsson;
GPG p.433;
3DG p.302;
GPC;
RTR4 p.984
GPG p.380   homogeneous clipping:
Gems p.84
(Gems IV p.83);
(Gems V p.378);
(GTweb);
Assarsson;
3DG p. 302;(
GTCG p.624);
GPC;
RTR4 p.986
GTweb;
GTweb doc;
Assarsson;
GTCG p.624;
GPC
(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;
SoftSurfercode
  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 doc;
GTCG p.726;
Ganovelli jgt 7(2);
RTCD p.383,399,410;
Gregorius 2013
convex polyhedron
  ray plane sphere cylinder cone triangle AABB OBB frustum 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. Other relevant presentations can be found on the Essential Math for Games Programmers site. 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 (or Minkowski difference) of the moving sphere with the other object, essentially shrinking the moving 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 Gregorius 2015.
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 RTR4, free Collision Detection chapter.
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).
Ray/Moving Polyhedron: Take the convex hull of each polyhedron and then the convex hull of both of these. Glassner is the earliest reference I know. See Gregorius 2015 for a modern treatment.

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 RTR4, free Collision Detection chapter..
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 and RTR4, free Collision Detection chapter..
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; GTWeb doc; RTR4, free Collision Detection chapter.; Gregorius 2012.
Moving Sphere/AABB: GTWeb has a more detailed document on this topic. (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.

Moving Triangle/Triangle: See GTweb doc and Catto 2013.

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.

Moving OBB/OBB: (location) See GTweb doc.

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. See GTweb doc.

Gregorius 2015 covers computing contact points among spheres, capsules, convex hulls, and meshes.

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.

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.

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 IV, 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.