GJK Algorithm

GJK: closest points and overlap via the Minkowski difference

The Lin-Canny example answered "how far apart are two convex polygons?" by walking along their explicit vertex/edge structure. The Gilbert–Johnson–Keerthi (GJK) algorithm [GJK88] answers the very same question — and, unlike that example, also directly detects overlap — using a completely different, more general trick: it never looks at the two shapes directly at all, only at a single derived shape called their Minkowski difference.

The Minkowski difference

For two convex shapes $A$ and $B$, their Minkowski difference is $$A \ominus B = \{\, a - b \;:\; a \in A,\, b \in B \,\}.$$ $A \ominus B$ is itself convex, and it has one crucial property: $A$ and $B$ overlap if and only if the origin lies inside $A \ominus B$ — a point $a-b = 0$ exists exactly when some $a \in A$ equals some $b \in B$. So the original question ("do $A$ and $B$ overlap, and if not, how far apart are they?") turns into "is the origin inside this one convex region, and if not, what is the closest point in it to the origin?" — a single, uniform question, independent of what kind of shapes $A$ and $B$ actually are.

The support function

GJK never constructs $A \ominus B$ explicitly (in general it can have far too many vertices). It only ever asks one kind of question: given a direction $d$, what is the farthest point of a shape in that direction — its support point, $\text{support}_S(d) = \arg\max_{p \in S} (p \cdot d)$? This immediately gives a support function for the difference itself: $$\text{support}_{A \ominus B}(d) = \text{support}_A(d) - \text{support}_B(-d).$$ For a polygon (used here) this is a linear scan over its vertices, but the same interface works for a circle, a capsule, or any other convex primitive with a closed-form support function — which is exactly why GJK generalizes far beyond polygons, unlike an algorithm that needs explicit vertex/edge adjacency.

The algorithm

GJK grows a small simplex (in 2D: a point, then a segment, then a triangle) out of support points, chasing the origin:

1. Pick an arbitrary direction, get one support point of $A \ominus B$, and start the simplex with just that point.
2. Find the point $Q$ on the current simplex closest to the origin. This is the very same kind of Voronoi-region reasoning as in the Lin-Canny example — just applied to the abstract simplex instead of a real polygon boundary — and it discards any simplex point not needed to describe that closest feature (e.g. a triangle collapses to just its closest edge or vertex).
3. If the simplex already encloses the origin, $A$ and $B$ overlap — stop.
4. Otherwise, query a new support point $S$ in the direction from $Q$ toward the origin. If $S$ makes no further progress towards the origin than $Q$ already does, the simplex cannot be improved: stop, $\|Q\|$ is the separation distance.
5. Otherwise add $S$ to the (reduced) simplex and go back to step 2.

The actual closest points on $A$ and on $B$ ("witness points", drawn in the left panel exactly as in the Lin-Canny example) come for free: each simplex point remembers which support points of $A$ and $B$ produced it, and the same interpolation weights that place $Q$ on the simplex place the witness points on $A$ and $B$.

The right panel renders exactly this abstract construction: every support point ever queried (light trail), the current simplex (purple), the origin, and the current closest point with its distance — while the left panel shows the same query back in the original world space.

Properties and how it compares to Lin-Canny

• More general: it only needs a support function, so the same code handles circles, capsules or any convex point set — not just polygons with explicit vertex/edge neighbors.
• Detects overlap natively: the same loop that computes the distance also detects when the origin is enclosed, with no separate case needed — unlike the simplified Lin-Canny example on this site, which assumes the polygons are separated.
• Converges in very few support queries in practice (the "Support queries" counter rarely exceeds single digits here), even though, unlike Lin-Canny, this example restarts the search from scratch on every frame in continuous mode — GJK's speed comes from the simplex construction itself, not primarily from reusing the previous frame's answer (though real implementations often warm-start it too, for an extra constant-factor speedup).
• Only finds overlap, not how much: once the origin is enclosed, GJK alone does not say how deeply the shapes interpenetrate. The natural follow-up, the Expanding Polytope Algorithm (EPA) [vdB01], grows the enclosing simplex outward into a full polytope around the origin to recover the penetration depth and direction; it is not implemented in this example.

Together with the earlier examples, this completes a small progression: sweep and prune cheaply narrows many objects down to a few candidate pairs (broad phase); Lin-Canny and GJK then answer the precise question for one such pair — how far apart are they, or do they already overlap — using two very different mechanisms for the same job.

References

• [GJK88] E. G. Gilbert, D. W. Johnson, S. S. Keerthi. A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space. IEEE Journal of Robotics and Automation, 1988.
• [vdB01] Gino van den Bergen. Proximity Queries and Penetration Depth Computation on 3D Game Objects. Game Developers Conference, 2001.
• [Eri04] Christer Ericson. Real-Time Collision Detection. Morgan Kaufmann, 2004.