skip to content

Narrow-Phase Collision

SAT and GJK/EPA run on broad-phase candidate pairs to find separation, penetration depth and contact manifolds. Interviewers ask candidates to sketch SAT or GJK to test geometric reasoning.

on this pageshow

explore

questions

5

In narrow-phase collision, what does a contact test return for two overlapping spheres, and how does a capsule reuse that test?

level: juniorimportance: must knowfreq 55%

answer

  1. more than a yes or no
  2. normal, depth, point
  3. centre-to-centre vector
  4. capsule = segment plus radius

basics

~20 s

A narrow-phase test returns a unit contact normal, a penetration depth and contact points, not just yes or no. Spheres get all three from the centre-to-centre vector; a capsule finds the closest point on its core segment, then reuses the sphere test.

solid answer

~50 s

Narrow phase runs on the pairs the broad phase kept and answers *how* they touch: a unit `normal` (here pointing from A toward B), a penetration `depth`, and contact points a solver can push on. For two spheres take `d = cB - cA`; they overlap when `dot(d, d) < (rA + rB)^2`. Then `dist = length(d)`, `normal = d / dist`, `depth = rA + rB - dist`, and a contact point midway between the two surface points, `cA + normal * (rA - depth / 2)`. A capsule is a segment with a radius, so against a sphere you find the point on the segment closest to the sphere's centre and run the sphere test from there with the capsule's radius. Two capsules use the closest points between their segments; when the segments are parallel and overlap, emit two points so one capsule lying along another does not teeter. Coincident centres need a fallback normal.

code

pseudocode · 14 lines
pseudocode
function sphereSphere(cA, rA, cB, rB):
    d = cB - cA
    radiusSum = rA + rB
    distSq = dot(d, d)
    if distSq >= radiusSum * radiusSum:
        return NO_CONTACT
    dist = sqrt(distSq)
    if dist > EPSILON:
        normal = d / dist
    else:
        normal = (0, 1, 0)          // centres coincide: any fixed unit vector
    depth = radiusSum - dist
    point = cA + normal * (rA - depth / 2)
    return Contact(normal, depth, point)

go deeper

for a junior

Recall the three outputs of a contact, a normal, a depth and points, and be able to compute them for two spheres on a whiteboard.

for a middle

Explain how capsules reduce to spheres through closest points on their core segments, and why the normal convention must be consistent across every pair routine.

for a senior

Spot the degenerate cases in production: coincident centres, parallel capsules that need two points, and tolerances that break when the world's units change.

for a principal

Weigh which shape pairs deserve dedicated closed-form routines and which can fall back to a general convex test, given how often each pair occurs in your game.

## What narrow phase is for A physics step usually finds collisions in two passes. The **broad phase** cheaply shortlists pairs whose bounding volumes overlap; most of those pairs are not actually touching. The **narrow phase** then runs an exact test on each surviving pair, using the real shapes. Its job is not only to say *whether* two shapes overlap but *how*, because the code that resolves the collision afterwards needs geometry to work with. ## The contact a solver needs For one touching pair, a narrow-phase test reports a **contact**, made of: - a **contact normal**: a unit vector giving the direction along which the shapes should be pushed apart. Pick one convention and keep it; in this answer it points from shape A toward shape B. - a **penetration depth**: how far the shapes overlap along that normal, a positive distance. - one or more **contact points**: where in the world the shapes touch, so that a push can create the right turning effect. - optionally, **feature information** saying which faces, edges or vertices touched, which later frames use to recognise the same contact again. A plain overlap flag is what the broad phase already gave you. Without a normal and a depth, nothing downstream knows which way or how far to separate the bodies. ## Sphere versus sphere, step by step Spheres are the simplest case, and every rounded shape builds on it. 1. Compute `d = cB - cA`, the vector between the centres, and `radiusSum = rA + rB`. 2. Reject early when `dot(d, d) >= radiusSum * radiusSum`: the spheres are apart (or just touching). Comparing squared lengths avoids a square root for the common no-contact case. 3. Otherwise take `dist = length(d)`. 4. The normal is `d / dist`, pointing from A toward B. 5. The depth is `radiusSum - dist`. 6. A good contact point is halfway between the two surface points: `cA + normal * (rA - depth / 2)`. **Worked example.** Two spheres of radius 1 sit at `(0, 0, 0)` and `(1.5, 0, 0)`. Then `dist = 1.5`, the normal is `(1, 0, 0)`, the depth is `2 - 1.5 = 0.5`, and the contact point is `(0.75, 0, 0)`, exactly halfway between A's surface at `x = 1` and B's surface at `x = 0.5`. ## Capsules: a segment with a radius A **capsule** is every point within radius `r` of a line segment, its **core segment**. That makes it a "rounded segment", and it reuses the sphere logic: - **Capsule versus sphere**: find the point on the core segment closest to the sphere's centre (a closest-point formula from geometry), place an imaginary sphere of the capsule's radius there, and run the sphere-sphere test. - **Capsule versus capsule**: find the pair of closest points between the two core segments, then treat them as two sphere centres with the two radii. - **Parallel capsules**: when the two segments are parallel and overlap along their length, the closest points are not unique. Returning one arbitrary point lets one capsule pivot on it. Emit two contacts instead, at the two ends of the overlapping interval, so a log lying along another log sits still. - **Capsule versus box or hull**: no simple closed form; the usual route is a general convex test on the core segment, with the radius added afterwards. | Shape pair | How the contact is found | |---|---| | Sphere / sphere | Centre-to-centre vector, radius sum | | Capsule / sphere | Closest point on the core segment, then sphere / sphere | | Capsule / capsule | Closest points between segments; two points if parallel | | Sphere / box | Closest point on the box to the centre, then compare with the radius | ## Edge cases that bite - **Coincident centres**: if `dist` is close to zero, `d / dist` divides by nearly zero. Choose any fixed unit normal, such as the world up axis, and report the full radius sum as depth. - **Exact touching**: decide whether a distance equal to the radius sum counts as a contact and use the same rule in every pair routine; resting objects usually sit with a tiny overlap anyway, because many solvers deliberately leave a little penetration. - **Normal direction**: if one routine returns A-to-B and another B-to-A, the solver pushes bodies into each other. Every pair function must follow the same convention, and swapped pairs must flip the normal. - **Units**: depth is in world units, so a scene built in very small or very large units shifts every tolerance you compare it against. Spheres and capsules matter in interviews because they are the shapes most game characters, limbs and projectiles are built from, and because getting their contact right shows you understand what the rest of the pipeline consumes.

  • How would you generate a contact between a sphere and an oriented box?
    Move the sphere's centre into the box's local frame and clamp it to the half extents to get the closest point on the box. If that point is within the radius, the normal runs from it to the centre and the depth is the radius minus the distance. If the centre is inside the box, push out through the nearest face: that face's axis is the normal and the depth is the radius plus the distance to that face.
  • Why does a capsule lying along a parallel capsule need two contact points?
    Parallel overlapping core segments have a whole interval of closest points. One point in the middle gives the solver a single pivot, so the top capsule can tip about it. Two points at the ends of the overlap interval let pushes at both ends cancel any tipping, so the pair rests still.

  • Narrow phase only needs to say whether the two shapes overlap.
  • Penetration depth is the distance between the two sphere centres.
  • A capsule needs its own formula with nothing in common with spheres.
  • Coincident centres never happen in a game, so no fallback normal is needed.
  • The normal's direction does not matter as long as it is unit length.
open as a page

What does the separating axis theorem say, and which candidate axes must a collision test check for two oriented boxes in 3D?

level: middleimportance: must knowfreq 60%

basics

~20 s

Two convex shapes are disjoint exactly when some axis separates their projections. For two oriented boxes in 3D, testing 15 axes is enough: the 3 face normals of each box and the 9 cross products of one box's edge directions with the other's.

open as a page

A capsule body rests on a convex rock; how do GJK distance with collision margins and EPA together give its penetration depth and normal?

level: seniorimportance: should knowfreq 35%

basics

~20 s

A capsule is a core segment plus a radius: GJK distance measures core to rock, depth is radius plus rock margin minus that distance, and the normal joins the closest points. Only overlapping cores need EPA, which expands GJK's simplex to the boundary.

open as a page

How does GJK decide whether two convex shapes intersect, using the Minkowski difference, support functions and its simplex cases?

level: seniorimportance: should knowfreq 48%

basics

~20 s

GJK tests whether the origin lies inside the Minkowski difference of the two shapes without building it: support points grow a simplex of up to four points toward the origin until it encloses the origin or a new point falls short of it.

open as a page

How do you build a stable box-box contact manifold when two tumbling boxes settle face to face but rock and jitter on one deepest point per frame?

level: seniorimportance: should knowfreq 42%

basics

~20 s

Build several points at once: clip the other box's most anti-parallel face against the side planes of the reference face that won the separating-axis test, keep points below it, reduce to four, and match them across frames by feature ids.

open as a page