The GJK and EPA Algorithms: How Minkowski Difference and the Simplex Determine Collision

The Separating Axis Theorem (SAT) solves collision by brute force, checking every possible face normal of two objects to find a gap of daylight between them. The Gilbert-Johnson-Keerthi (GJK) algorithm differs in one crucial respect: it completely ignores the faces. Instead of testing dozens of polygons, GJK subtracts one object from the other mathematically to create a single, abstract volume called the Minkowski Difference. If that new volume contains the origin point—the exact center of the universe, coordinate (0,0,0)—the objects are colliding. If it does not, they are not. In the high-stakes environment of a 144-hertz physics simulation, where a game engine has less than seven milliseconds to resolve thousands of overlapping rigid bodies, skipping the polygon-by-polygon check is the difference between a fluid simulation and a frozen frame.[1][3]

The genius of GJK lies in how it navigates this abstract Minkowski space. Generating the entire Minkowski Difference for two complex 3D models would require calculating millions of vertices, instantly bottlenecking the CPU. GJK bypasses this by never actually building the shape. Instead, it uses a "support function"—a mathematical probe that asks, "What is the furthest point in this specific direction?" By firing these probes, GJK builds a "simplex" (a point, line, triangle, or tetrahedron) inside the Minkowski space, actively hunting for the origin.[2][5]

Every time the simplex fails to enclose the origin, GJK discards the useless vertices and fires a new support function toward the origin's location. It is a homing missile for intersection. For typical convex shapes, GJK finds the origin or proves it cannot be reached in just three to four iterations. This drops the algorithmic complexity from a geometric nightmare to a near-constant time operation, allowing modern physics engines to test thousands of objects per frame without dropping below the critical 16.6-millisecond render budget.[3][7]

But knowing two objects are colliding is only half the battle. When a player's car slams into a concrete barrier, the engine does not just need a boolean "true" or "false"—it needs to know exactly how deep the car is buried in the wall and which direction to push it out. This is where GJK hits a hard mathematical wall. Because it stops the exact millisecond it traps the origin inside its simplex, it provides zero information about the depth or angle of the penetration.[4]

Enter the Expanding Polytope Algorithm (EPA). When GJK returns a collision, it hands its final, origin-trapping simplex over to EPA. EPA takes that tetrahedron and begins inflating it like a balloon inside the Minkowski space. It finds the face of the simplex closest to the origin, fires another support function in that direction, and stretches the simplex outward to grab a new vertex on the edge of the Minkowski boundary.[4][6]

EPA repeats this expansion, fracturing its own faces into smaller and smaller triangles, until it hits the absolute edge of the Minkowski Difference. The shortest distance from the origin to that final boundary is the exact penetration depth, and the vector pointing there is the collision normal. It is a computationally heavy, iterative process that can consume significant CPU cycles if the objects are highly curved, but it delivers the pixel-perfect resolution data required to calculate bounce, friction, and resting contact.[2]

The pairing of GJK and EPA creates a ruthless filter for physics engines. GJK acts as the lightweight, high-speed vanguard, rapidly clearing the 99 percent of objects that are not colliding. Only when an intersection is absolutely confirmed does the engine pay the heavy computational tax of spinning up EPA to resolve the physics. This division of labor is why a modern competitive shooter can simulate hundreds of grenades, players, and debris fragments simultaneously without melting the server.[5][7]

The implementation of these algorithms dictates the ceiling of a game's physical complexity. While the foundational reference materials from ACM and dyn4j contain no direct developer quotations, their mathematical proofs establish the hard rules of the virtual world: keep collision hulls convex, keep vertex counts low, and let the simplex do the hunting. Since its adaptation for real-time graphics, detailed extensively in Casey Muratori's landmark 2006 implementation guide, the algorithm has become industry standard. The next frontier lies in parallelizing these support functions across GPU compute shaders, potentially pushing collision checks from the thousands into the millions.[2][3][4]