GJK

The Gilbert–Johnson–Keerthi (GJK) distance algorithm is a geometric method for detecting collision and measuring the minimum distance between two convex shapes. It is widely used in computational geometry and real-time physics simulation due to its efficiency with convex objects.

The algorithm operates in the Minkowski difference of the two shapes. In each iteration, it selects a search direction and uses the shapes’ support functions to obtain extreme points in opposite directions, adding a new vertex to a simplex in Minkowski space. The current simplex is refined to move toward the origin, with the search direction updated to the closest point on the simplex to the origin. In two or three dimensions, the simplex can be a point, a line segment, a triangle, or a tetrahedron.

If the origin lies inside the current simplex, the two shapes intersect. If not, the algorithm converges to the closest point on the Minkowski difference to the origin; the distance from the origin to this point equals the minimum distance between the shapes. The process repeats until convergence or a maximum number of iterations is reached.

GJK is primarily a collision-detection algorithm, but a distance variant yields the minimum separation. When intersection is detected, a secondary method such as the Expanding Polytope Algorithm (EPA) can be used to compute penetration depth. Practical implementations address degeneracies and redundant points to improve robustness and performance.

Historically, GJK was introduced independently by Gilbert, Johnson, and Keerthi in the 1980s. It remains a foundational technique in many physics engines and robotics libraries for convex shapes due to its generality and efficiency.