Given a 2D implicit line P · n̂ = d and an arbitrary query point Q, find the closest point Q' on the line.
① Form line M: parallel to L, passing through Q.
Line M: P · n̂ = dm where dm = Q · n̂
② Signed distance from L to Q:
(d - dm) in direction of n̂
③ Displace Q toward L by that distance:
Q' = Q + (d - Q·n̂) · n̂
2
Closest Point: Parametric Ray
Given ray P(t) = P₀ + t·d̂ (d̂ normalized) and point Q:
① v = Q - P₀ (vector from ray origin to Q)
② t = v · d̂ (scalar projection of v onto the ray direction)
③ Q' = P(t) = P₀ + t·d̂
* Not clamped: works for infinite lines
* Clamp t to [0, 1] for bounded rays, or [0, ∞) for semi-infinite rays
The dot product v · d̂ gives the exact displacement distance from P₀ needed, because d̂ is a unit vector. This is one of the most common operations in game code — finding the nearest point on a movement path to some target.
3
Closest Point: Plane
Given plane P · n̂ = d and query point Q — same logic as the 2D line, just one dimension higher:
Q' = Q + (d - Q·n̂) · n̂
4
Closest Point: Circle or Sphere
Given sphere (C, r) and query point Q:
① d = C - Q (vector from Q to center)
② d̂ = d / ‖d‖ (normalized direction toward center)
③ Q' = Q + (‖d‖ - r) · d̂
= Q + (‖d‖ - r) · (d / ‖d‖)
This displaces Q toward the sphere by the amount it exceeds the surface. If Q is already inside, the formula still works and pushes Q to the nearest surface point.
5
Closest Point: AABB
Push each coordinate of Q toward the AABB's bounds if it's outside:
For each axis i ∈ {x, y, z}:
if Qi < min_i → Q'i = min_i
else if Qi > max_i → Q'i = max_i
else → Q'i = Qi (already inside on this axis)
6
Intersection: Two Implicit 2D Lines
Given L₁: a₁x + b₁y = d₁ and L₂: a₂x + b₂y = d₂:
① Looking for (x, y) where both equations hold simultaneously
② Solve using Cramer's Rule:
x = (b₂d₁ - b₁d₂) / (a₁b₂ - a₂b₁)
y = (a₁d₂ - a₂d₁) / (a₁b₂ - a₂b₁)
③ Denominator = a₁b₂ - a₂b₁:
≠ 0 → unique intersection point
= 0 → lines are parallel (no intersection or infinite if numerators also 0)
7
Intersection: Two 3D Rays
Given R₁(t) = P₁ + t₁·d₁ and R₂(t) = P₂ + t₂·d₂ (assumed infinite/unbounded):
① Seek t₁ and t₂ where R₁(t₁) = R₂(t₂)
② Using cross products to isolate each parameter:
t₁ = ((P₂ - P₁) × d₂) · (d₁ × d₂) / ‖d₁ × d₂‖²
t₂ = ((P₂ - P₁) × d₁) · (d₁ × d₂) / ‖d₁ × d₂‖²
③ If d₁ × d₂ ≈ 0: lines are parallel (check ‖d₁ × d₂‖ against epsilon)
④ Check if R₁(t₁) ≈ R₂(t₂): if not, the lines are skew (no intersection)
⑤ If using bounded rays, verify t₁ and t₂ are within valid range
8
Intersection: Ray and Plane
Given ray P(t) = P₀ + t·d̂ and plane P · n = d (n and d need not be unit):
① Substitute ray into plane equation:
(P₀ + t_int·d) · n = d
t_int = (d - P₀·n) / (d̂·n)
② Edge cases:
d̂·n = 0 → ray is parallel to plane (no intersection)
d̂·n < 0 → ray hits the front face of the plane
t_int < 0 → intersection is behind the ray origin
t_int > 1 → outside the ray's length (for bounded rays)
The sign of d̂ · n tells you if the ray is hitting the front or back of the plane. In rendering, this is used to skip intersections with back-facing triangles (backface culling in ray tracing).
9
Intersection: AABB and Plane
Given plane P · n = d (n does not need to be unit) and an AABB:
① Compute P · n for each of the 8 corner points of the AABB
② If all dot products have the same sign → all corners are on the same side → no intersection
③ If signs differ → some corners are on each side → intersection
④ Optimization: test only 2 "extreme" corners (the one most in +n direction
and the one most in -n direction) instead of all 8
10
Intersection: Ray and Circle/Sphere
Given sphere (C, r) and ray P(t) = P₀ + t·d̂ (d̂ is unit):
① e = C - P₀ (vector from ray origin to sphere center)
② a = d̂ · e (scalar projection of e onto ray = closest approach t)
③ Closest point on ray is at t = a. Find f² using Pythagorean theorem:
f² = r² - (e·e - a²) (e·e = ‖e‖², a² = projection length²)
④ If f² < 0 → no intersection (ray misses sphere)
⑤ If f² ≥ 0 → two intersection points at:
t = a ± √f²
t₁ = a - √f² (near intersection — entry point)
t₂ = a + √f² (far intersection — exit point)
For bounded rays: check that t values are within valid range.
Compare f² < 0 before taking the square root — avoids calling sqrt when there's no intersection. Compare ‖e‖² < r² first to handle the "ray starts inside sphere" case.
11
Intersection: Two Circles/Spheres
Two static spheres overlap when the distance between centers is less than the sum of their radii:
This is one of the cheapest possible intersection tests. It's used as the first-pass collision check in many physics broadphase systems — if two spheres don't overlap, no further checks needed.
12
Intersection: AABB and Sphere
① Find the point Q' on the AABB closest to sphere center C
(use the per-axis clamp from the closest-point AABB test)
② Check if squared distance from Q' to C is ≤ r²:
‖Q' - C‖² ≤ r²
13
Intersection: Ray and Triangle
① Compute the plane containing the triangle (using the cross product of two edges)
② Find where the ray intersects that plane (ray-plane test)
③ Convert the intersection point to barycentric coordinates (u, v, w)
④ Verify 0 ≤ u, v, w ≤ 1 and u + v + w = 1
(if any barycentric coordinate is < 0 or > 1, the point is outside the triangle)
Barycentric coordinates are used for much more than containment: they interpolate vertex attributes (UV, normals, vertex colors) across the triangle surface. A UV map lookup in a ray tracer is just barycentric interpolation of the three vertex UV coordinates.
14
Intersection: Two AABBs
Test for overlapping extents on each axis independently. If there is no overlap on any single axis, the AABBs do not intersect (Separating Axis Theorem):
For AABBs A and B, check each axis:
if A.xmin >= B.xmax → no overlap on X → return false
if A.xmax <= B.xmin → no overlap on X → return false
if A.ymin >= B.ymax → no overlap on Y → return false
if A.ymax <= B.ymin → no overlap on Y → return false
if A.zmin >= B.zmax → no overlap on Z → return false
if A.zmax <= B.zmin → no overlap on Z → return false
return true (overlap on all three axes → AABBs intersect)
This is the core of AABB-vs-AABB collision and is used extensively in broadphase systems. It's just 6 comparisons — extremely fast and cache-friendly. The same principle (check for a separating axis) scales to OBBs, which require testing 15 potential separation axes in 3D.
15
Exercises
1. Closest Point on Ray
Find the closest point on ray P(t) = (0,0,0) + t·(1,0,0) to point Q = (3, 4, 0). Also find the distance from Q to the ray.
v = Q - P₀ = (3,4,0). t = v · d̂ = (3,4,0)·(1,0,0) = 3. Q' = (3, 0, 0). Distance = ‖Q - Q'‖ = ‖(0,4,0)‖ = 4.
2. Ray-Plane Intersection
Ray: P(t) = (0,5,0) + t·(0,-1,0). Plane: the XZ plane (y = 0, or n = (0,1,0), d = 0). Find t_int and the intersection point.
A = [Pmin=(0,0,0), Pmax=(4,4,4)] and B = [Pmin=(3,3,3), Pmax=(7,7,7)]. Do they overlap?
X: A.xmax=4 > B.xmin=3 and A.xmin=0 < B.xmax=7 → overlap. Y and Z: same. All three axes overlap → AABBs intersect. Overlap region: [3,3,3] to [4,4,4].
Interview Question
Describe the ray-sphere intersection test step by step. What's the role of the dot product and the Pythagorean theorem?
1. Project the vector from ray origin to sphere center onto the ray direction (dot product) to find the ray's closest approach. 2. Use the Pythagorean theorem to find how far this closest approach point is from the sphere center (the "f²" value). 3. If f² < 0, the ray misses. Otherwise, subtract/add √f² from the approach distance to get entry/exit t values. The dot product finds where to look; Pythagoras finds whether we actually hit.
Interview Question
What is the Separating Axis Theorem and how is it used in collision detection?
SAT states: two convex shapes do not intersect if and only if there exists a separating axis — a direction along which the projections of the two shapes do not overlap. For two AABBs, the three world axes are sufficient to check. For OBBs, you must also check the three axes of each box plus the 9 cross products of their axis pairs (15 total). If any single axis shows a gap, the shapes are separated. First gap found = early exit = fast.
Interview Question
How do you build a collision broadphase for a scene with thousands of objects?
Common approaches: 1) Bounding Volume Hierarchy (BVH) — build a tree of AABBs; a ray only recurses into branches whose AABB it hits. O(log n) per query. 2) Sweep and Prune — sort objects by one axis, use interval overlaps to generate candidate pairs; works well for scenes with coherent motion. 3) Spatial hashing / grid — divide space into cells, only test objects in the same cell. Choose based on scene type: BVH for ray casting, sweep-and-prune for physics with many moving objects.