The GJK Algorithm

A physics engine's inner loop asks one question millions of times a second: are these two shapes touching? A crate resting on a floor, a bullet clipping a wall, a character's foot pressing a ramp — every one is a pair of convex shapes and a yes/no. You could test every edge against every edge, but that scales badly and it treats a box, a sphere and a capsule as three different problems. The Gilbert–Johnson–Keerthi algorithm (GJK, 1988) answers the question with one astonishingly general trick that works for any convex shape, and it usually settles the matter in three or four iterations.

GJK is a cousin of the Separating Axis Theorem: both decide convex overlap, but where SAT enumerates candidate separating axes, GJK plays a slicker game on a single derived shape — the Minkowski difference — and reduces "do A and B overlap?" to "does one shape contain the origin?"

The one idea: overlap becomes "does it contain the origin?"

Take two shapes A and B. Build a brand-new shape by subtracting every point of B from every point of A:

A \ominus B \;=\; \{\, \mathbf{a} - \mathbf{b} \;:\; \mathbf{a} \in A,\; \mathbf{b} \in B \,\}.

This is the Minkowski difference. Now here is the whole insight. The shapes A and B share a point exactly when there is some \mathbf{a} = \mathbf{b} — that is, when \mathbf{a} - \mathbf{b} = \mathbf{0} is one of the points of the difference. So:

We have turned a two-shape question into a one-shape, one-point question. The catch: building the full Minkowski difference is expensive (a polygon with m and one with n vertices give a difference with up to mn vertices). GJK's genius is that it never builds it.

Sampling the difference lazily: the support function

GJK only ever needs to know one thing about a shape: in a given direction, which point sticks out farthest? That is the support function:

S_A(\mathbf{d}) \;=\; \operatorname*{arg\,max}_{\mathbf{p} \in A}\; \mathbf{p} \cdot \mathbf{d}.

For a polygon it is the vertex with the largest dot product against \mathbf{d} (a quick scan). For a sphere of centre \mathbf{c} and radius r it is \mathbf{c} + r\,\hat{\mathbf{d}} in closed form. For a capsule, a cone, a convex hull — each is a tiny formula. The beauty is that the support function of the difference factors into the two shapes' own support functions:

S_{A \ominus B}(\mathbf{d}) \;=\; S_A(\mathbf{d}) \;-\; S_B(-\mathbf{d}).

So to poke the Minkowski difference in direction \mathbf{d} you push A along \mathbf{d}, push B along -\mathbf{d}, and subtract. One support point of the difference costs two cheap support evaluations — and GJK samples only a handful of them. This is why GJK works for any convex shape: give it a support function and it is happy, no special cases for boxes versus spheres.

Seeing the Minkowski difference

Below, triangle A and square B overlap on the left. On the right is their Minkowski difference A \ominus B — a bigger convex polygon. Because the two shapes touch, the difference swallows the origin (the marked dot), which is exactly the collision certificate GJK hunts for. Slide the shapes apart and the whole difference would drift off the origin, leaving a clear gap whose width is the separation distance.

GJK never draws that right-hand polygon. It only ever evaluates a few of its extreme vertices via the support function, assembling just enough of them to prove the origin is trapped inside.

Building a simplex to trap the origin

A simplex is the simplest shape in each dimension: a point, a line segment, a triangle, a tetrahedron. GJK grows a simplex out of Minkowski-difference support points, always trying to enclose the origin. The loop is short:

Each iteration either encloses the origin, proves it can never be enclosed, or drags the simplex measurably closer to it — so GJK terminates fast, typically in a handful of steps regardless of how many vertices the shapes have.

Worked example: two support evaluations that bracket the origin

Let A be the triangle with vertices (4,0),\,(6,0),\,(5,2) and let B be the unit square with vertices (4.5,0.5),\,(5.5,0.5),\,(5.5,1.5),\,(4.5,1.5). They overlap, so the origin should end up bracketed by difference points. Push in \mathbf{d} = (1,0) first.

Support of A along \mathbf{d}=(1,0): largest x is (6,0). Support of B along -\mathbf{d}=(-1,0): smallest x is (4.5,0.5). So the difference point is

\mathbf{p}_1 = S_A(\mathbf{d}) - S_B(-\mathbf{d}) = (6,0) - (4.5,0.5) = (1.5,\,-0.5).

That point sits to the right of the origin. Now flip to \mathbf{d} = (-1,0):

\mathbf{p}_2 = S_A(-\mathbf{d}_{\!}) - S_B(\mathbf{d}_{\!}) = (4,0) - (5.5,1.5) = (-1.5,\,-1.5).

Here S_A(-1,0) is the smallest-x vertex (4,0) and S_B(1,0) is the largest-x vertex (5.5,1.5). Point \mathbf{p}_2 sits to the left of the origin. Two support probes in opposing directions have produced difference points on opposite sides of \mathbf{0} along x — the origin is bracketed, and a third probe (perpendicular, toward the origin) closes a triangle around it: GJK reports intersecting.

Had B been shifted far to the right, both \mathbf{p}_1 and \mathbf{p}_2 would land on the same side of the origin, the test \mathbf{p} \cdot \mathbf{d} < 0 would trip, and GJK would stop with separated — no triangle ever encloses \mathbf{0}.

Plain GJK answers overlap and, when they are apart, the separation distance — but when two solids are already interpenetrating it can't tell you how deeply or in which direction to push. That is the job of EPA, the Expanding Polytope Algorithm, GJK's usual partner. Once GJK reports a hit, it hands EPA the final simplex (which straddles the origin). EPA then repeatedly finds the polytope face nearest the origin and pushes a fresh support point through it, expanding the polytope outward until it hugs the true boundary of the Minkowski difference. The closest face to the origin gives the penetration depth (how far to separate) and the contact normal (which way) — exactly the two numbers the collision response needs to shove the bodies apart and apply an impulse. GJK finds the collision; EPA measures it.

Two traps catch people. First: GJK requires convex shapes. The whole method rests on the Minkowski difference of two convex sets being convex, so the support function reaches every extreme point. Feed it a concave mesh — a star, an L-shaped wall, a teapot — and the support function skips over the dents, so GJK can happily report "no collision" while the shapes clearly overlap inside a concavity. The fix is convex decomposition: break the concave mesh into a set of convex pieces (or wrap it in a convex hull for a coarse test) and run GJK on each piece. Nearly every engine does this offline as a preprocessing step.

Second: plain GJK does not give penetration depth. It returns yes/no plus the separation distance when apart — nothing about how deep an overlap goes. If your collision response needs a push-out vector and a contact normal, you must run EPA afterwards. Reaching for GJK's simplex to guess a normal is a classic bug; that information simply isn't there yet.