The GJK Collision Algorithm

Every time a video game character lands on a platform, a car crumples in a crash simulation, or a robot arm avoids a wall, a question has to be answered in microseconds: do these two objects overlap?

The naive answer — sample thousands of points and check whether any lie inside both objects — is far too slow for real time. The clever answer, found by Elmer Gilbert, Daniel Johnson, and S. Sathiya Keerthi in 1988, reduces the whole question to a single geometric fact:

Two convex shapes overlap if and only if their Minkowski difference contains the origin.

The GJK algorithm (named for its three inventors) exploits that fact by building a small simplex — a triangle in 2-D, a tetrahedron in 3-D — that tries to enclose the origin inside the Minkowski difference. It converges in a handful of steps, touching at most a few support points per iteration, making it one of the fastest collision tests known.

Like closest-pair or convex-hull algorithms, GJK belongs to the world of computational geometry: problems where the answer is proven to exist and the challenge is finding it as cheaply as possible.

Drag the blue shape toward the orange one. The algorithm runs on every mouse move and reports whether the shapes are Separate or Colliding, colouring the canvas accordingly.

<div class="hint">{{hint}}</div>
<canvas id="c" width="480" height="320"></canvas>
<div id="status" class="status">{{status_separate}}</div>
<div class="btns">
  <button id="reset" type="button">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px; cursor: grab; background: #f6f8fa; max-width: 100%; touch-action: none; }
canvas.dragging { cursor: grabbing; }
.status { font: 700 1.05rem system-ui; margin: .6rem 0 .5rem; padding: .35rem .8rem; display: inline-block; border-radius: 6px; }
.status.sep  { background: #e8f5e9; color: #1b5e20; }
.status.col  { background: #ffebee; color: #b71c1c; }
button { font: 600 14px system-ui; padding: .4rem .9rem; background: #1d3557; color: #fff; border: none; border-radius: 8px; cursor: pointer; }
.btns { margin-top: .3rem; }

// Code not found

The key insight is that GJK never iterates over interior points. It only ever calls the support function — "which vertex of this shape is furthest in direction d?" — and builds a simplex from those extreme vertices in the Minkowski difference. When the simplex can no longer grow toward the origin the test terminates, usually in two or three iterations.

GJK is a solved algorithm — it always terminates with the correct answer for convex shapes. Its performance story is striking:

• Support function calls per iteration: exactly one per shape, so two total. Each call scans the shape's vertices once: $O(n)$ for a polygon with n vertices, $O(1)$ for a circle or capsule with a closed-form support.
• Number of iterations: in practice one to four for well-separated shapes. In the worst case, $O(n)$ iterations are possible for degenerate configurations, but this is rarely seen in games.
• Overall cost: roughly $O(n)$ support-function evaluations per query, and for smooth convex bodies (spheres, capsules) it is effectively $O(1)$.
• Limitation: GJK only works on convex shapes. Non-convex meshes must first be decomposed into convex pieces — a hard preprocessing step — before GJK can be applied to each piece.

The Minkowski difference itself has $O(n \cdot m)$ vertices (n and m are the vertex counts of each shape), but GJK never constructs it explicitly. That implicit treatment is the algorithmic magic: a potentially enormous object is navigated using only its support function, keeping memory and time lean.

Compare this to testing every triangle pair between two meshes: $O(n \cdot m)$ with large constants. GJK is why modern physics engines can handle hundreds of collisions per frame.

GJK is one of the few algorithms that went straight from a research paper to production use in virtually every real-time physics system:

• Game physics engines: Bullet, PhysX, Havok, and Box2D all use GJK (or its extension EPA for penetration depth) at their collision-detection core. Every platform game, racing sim, and fighting game relies on it running thousands of times per frame.
• Robotics motion planning: checking whether a robot link collides with an obstacle is a continuous stream of convex-vs-convex queries. Libraries like FCL (Flexible Collision Library) wrap GJK for this purpose.
• CAD and engineering simulation: interference checking between mechanical parts — does this bolt thread clear the housing? — uses the same convex-decomposition + GJK pipeline.
• Medical simulation: virtual surgery tools that must feel realistic to trainees need haptic-speed (>1 kHz) collision feedback; GJK's low constant makes that feasible.
• Animation and cloth: broad-phase collision detection in cloth and hair simulation uses bounding-volume hierarchies of ellipsoids, with GJK at the leaf level.

The extension EPA (Expanding Polytope Algorithm, by Gino van den Bergen, 2001) builds on GJK to compute the exact penetration depth and contact normal once a collision is confirmed — completing the information needed to resolve the collision with an impulse response.

GJK is a beautiful example of an algorithm that wins by changing the question. Instead of asking "do any points of A lie inside B?", it asks "does the Minkowski difference A⊖B contain the origin?" — and then answers that by building a tiny simplex one support point at a time.

The result is an $O(1)$-to-$O(n)$ algorithm that works in any number of dimensions, handles every convex shape through a single abstraction (the support function), and has remained the industry standard for almost four decades. When your game character lands safely on a ledge, it is this 1988 idea — turned into a handful of dot products and a simplex update — that made it happen.

For shapes beyond convex, the next challenge is convex decomposition: splitting an arbitrary mesh into pieces GJK can handle. That is a harder, open-research problem — a reminder that even elegant solved algorithms leave interesting questions just past their boundary.