The Gilbert–Johnson–Keerthi distance algorithm, commonly referred to as the GJK algorithm, is a fundamental method in computational geometry used to determine the distance between two convex shapes. Unlike brute-force techniques that compare every vertex of one object against another, GJK leverages the geometric properties of Minkowski Difference to efficiently assess whether two objects intersect. Its primary output is a boolean result indicating collision, but with additional logic, it can compute the minimum separating vector, making it invaluable for physics engines and real-time simulations.
Core Principles and Minkowski Difference
At the heart of the GJK algorithm is the concept of Minkowski Difference. Given two shapes, A and B, the Minkowski Difference is a theoretical construct formed by subtracting every point in B from every point in A. If the origin of this difference space lies inside the resulting shape, it indicates that A and B are intersecting. The genius of GJK is that it never explicitly constructs this potentially infinite shape. Instead, it incrementally builds a simplex—a minimal polytope in N-dimensional space—by querying the support function, which finds the farthest point on a shape in a given direction. This approach allows the algorithm to navigate the high-dimensional geometry using only a handful of points.
The Iterative Search Process
GJK operates as an iterative search, guided by the Simplex method. The process begins with an initial direction, often the vector between the centers of the two shapes. In each iteration, the algorithm queries the support function with the current search direction to obtain a new point. This point is then added to the simplex, which is checked to see if it contains the origin. If the origin is inside, a collision is detected. If not, the algorithm identifies the closest feature of the simplex to the origin and updates the search direction to point toward the origin. This loop continues, adding new points and reducing the search space, until either the origin is enclosed or the simplex reaches its maximum size, signifying no intersection.
Simplex Construction in Two and Three Dimensions
The structure of the simplex is dimension-dependent, evolving as the algorithm progresses. In two dimensions, the simplex progresses through a line segment (two points), then a triangle (three points), and finally a tetrahedron in three dimensions (four points). A triangle in 2D or a tetrahedron in 3D is the critical configuration, as it fully encloses the origin. At each step, the algorithm discards the point on the simplex that is least relevant to the direction toward the origin, ensuring computational efficiency. This dynamic refinement is what allows GJK to navigate complex shapes with remarkable speed.
Performance and Advantages
One of the primary reasons for the widespread adoption of GJK is its computational efficiency. The algorithm typically converges in a small number of iterations, often less than ten, regardless of the complexity of the input shapes. This constant-time performance is crucial for real-time applications like video games and robotic pathfinding, where thousands of collision checks might occur every second. Furthermore, GJK is remarkably versatile, handling spheres, boxes, capsules, and complex mesh models as long as they are convex. Its reliance on simple vector operations—dot products and cross products—makes it hardware-friendly and straightforward to implement across various platforms. Limitations and Complementary Algorithms Despite its strengths, the GJK algorithm has inherent limitations. Its requirement for convex shapes means it cannot directly handle concave objects, necessitating decomposition into convex parts beforehand. Additionally, GJK is a proximity query algorithm at its core; while it can be adapted to return a penetration depth, its native design is for boolean collision detection. This is where algorithms like the Expanding Polytope Algorithm (EPA) come into play. EPA is typically run after GJK to refine the collision normal and calculate the exact depth of penetration required to resolve the collision response physically accurately.
Limitations and Complementary Algorithms
Implementation Considerations and Best Practices
More perspective on Gjk algorithm can make the topic easier to follow by connecting earlier points with a few simple takeaways.
