How does a video game know the precise moment a complex, rotating object collides with another? In physics simulations and games, this is a constant, critical question. A simple check for overlapping bounding boxes is fast but imprecise. The GJK algorithm is a brilliantly efficient method for determining if two convex shapes are intersecting, and it does so without needing to know the geometry of the shapes themselves.
🔍 The Discovery
Name of the Technology: Gilbert-Johnson-Keerthi (GJK) Distance Algorithm
Original Creator/Institution: Elmer G. Gilbert, Daniel W. Johnson, and S. Sathiya Keerthi
Year of Origin: 1988
License: A fundamental, public domain algorithm.
The algorithm works on a fascinating principle using a concept called the Minkowski difference. Instead of looking at the two shapes, it imagines a new shape created by subtracting the position of every point in one shape from every point in the other. The problem is then simplified: the two original shapes are colliding if, and only if, this new Minkowski shape contains the origin (the point). GJK is a clever iterative method that builds a small polygon (a simplex) inside this Minkowski difference shape. In each step, it expands the simplex towards the origin. If the simplex ever encloses the origin, the shapes are colliding. If it can build a complete simplex that does not contain the origin, and it can't get any closer, the shapes are not colliding.
🛠️ Ready for Today: Why This Isn't Just Theory
The GJK algorithm is a cornerstone of modern physics engines and robotics. Its speed and ability to work with any convex shape make it the standard for real-time collision detection. It's often paired with a second algorithm (like the Expanding Polytope Algorithm or EPA) that can determine the depth and direction of the collision once GJK finds an intersection.
Status: The algorithm is in the public domain.
Implementations: GJK is a core component of most major physics libraries and game engines.
Physics Engines: Box2D (2D), Bullet Physics (3D), and PhysX (3D) all use GJK as their primary "narrow-phase" collision detection algorithm.
Game Engines: Unity and Unreal Engine use physics engines that have GJK at their core.
Robotics: Used in motion planning and simulation to check for collisions between a robot arm and its environment.
Standalone Libraries: Many libraries in C++, Java, and other languages provide implementations for use in custom physics applications.
💡 Creative Applications (Ideas To Get You Thinking)
The ability to ask "are these two complex things touching?" quickly and efficiently is a superpower for simulation and interactive design.
Idea 1 (A "Virtual Reality" Safety System): In a VR application, the user's hands and head are tracked as complex shapes. The furniture and walls in the real world can also be mapped as shapes. A GJK-based system running in the background could constantly check for collisions between the user and their real-world environment. If a collision is imminent, it could trigger a visual warning in the headset, preventing the user from punching a wall.
Idea 2 (A "Packing Optimization" Tool): A logistics company wants to pack as many items of various shapes as possible into a shipping container. A tool could use GJK to allow a user to drag, drop, and rotate 3D models of the items inside a virtual container. The algorithm would provide instant feedback, turning an item red the moment it intersects with another, helping the user find the most efficient packing arrangement interactively.
Idea 3 (A "Molecular Docking" Simulator): In computational biology, researchers want to see if complex protein molecules can "dock" with each other. While this is a highly complex field, a simplified simulator could model the molecules as convex shapes. A researcher could use GJK to quickly test millions of possible orientations between two molecules to get a first-pass filter of which ones are physically able to connect.
🐰 The Rabbit Hole
Dive Deeper: The "Casey Muratori" YouTube channel has a fantastic video that explains GJK. The video "Implementing GJK" is a great starting point, using clear diagrams to explain Minkowski space and how the simplex search works.
Join The Search
Our mission is to unearth the world's most powerful, overlooked ideas. If you know of a technology that is trapped in a niche, overshadowed by hype, or simply deserves a bigger spotlight, please submit it for a future issue here.
Till next time,