GJK Algorithm (Gilbert-Johnson-Keerthi)

The GJK algorithm does not operate directly on the two shapes. Instead, it transforms the problem by computing the Minkowski difference between them. For shapes A and B, this is defined as A ⊖ B = {a - b | a ∈ A, b ∈ B}. The critical insight is that the two original shapes intersect if and only if the Minkowski difference contains the origin. Furthermore, the distance between the shapes is the distance from the origin to this new set. This abstraction reduces collision and distance queries to a single problem: finding the closest point on a convex set to the origin.

GJK never explicitly constructs the full Minkowski difference, which would be computationally prohibitive. Instead, it queries the shape via a support function. For a given direction vector d, the support function for a convex shape returns the point on that shape's boundary that is farthest in the direction of d. For the Minkowski difference, the support point is easily computed as: s_A⊖B(d) = s_A(d) - s_B(-d), where s_A and s_B are the support functions for the individual shapes. This allows GJK to sample the Minkowski difference on-demand using only the geometry of the original objects.

GJK is an iterative method that builds a sequence of increasingly accurate approximations, called simplices, inside the Minkowski difference. A simplex is the convex hull of a small set of points (e.g., a point, line segment, triangle, or tetrahedron).

• Initialization: The algorithm starts with an arbitrary direction and adds a support point to form the initial simplex.
• Iteration: Each iteration uses the current simplex to find the closest point on it to the origin. The direction from this closest point toward the origin is used to query a new support point.
• Termination: If the new support point is not farther in this direction than the current closest point, the algorithm has converged. If the simplex contains the origin, a collision is detected.

A critical sub-step within each GJK iteration is finding the point on the current simplex closest to the origin. This is efficiently solved using Johnson's distance algorithm. It works by representing the closest point as a convex combination of the simplex vertices and using a series of geometric tests (e.g., Voronoi region checks) to determine which sub-simplex (a face, edge, or vertex) contains the closest point. This subalgorithm is what enables GJK to quickly refine its search direction each iteration without solving a general quadratic program.

GJK is prized for its rapid convergence, typically requiring only a few iterations (often 2-10) for standard convex shapes. This speed is due to:

• Geometric progression: Each iteration moves the simplex closer to the origin.
• Robust termination: The algorithm terminates with a collision if the simplex contains the origin. It terminates with a minimum distance when a new support point fails to advance the simplex closer to the origin than the current closest point, within a numerical tolerance.
• Caching: Support points and directions can be cached between frames for objects with small relative motion, a technique known as warm starting, which drastically reduces iteration count.

While GJK excels at detecting collision and finding distance, it only provides a yes/no answer and a separation vector for non-colliding objects. When shapes are interpenetrating, the Expanding Polytope Algorithm (EPA) is used as a post-processor. EPA takes the final simplex from GJK that contains the origin and expands it outward by iteratively adding support points until it reconstructs the full Minkowski difference near the origin. This allows EPA to calculate the penetration depth—the minimum translation vector required to separate the objects—and the corresponding contact normal. The GJK-EPA pipeline is standard in physics engines for generating full contact manifolds.

In robotics, GJK is critical for collision avoidance and path planning. It enables:

• Configuration Space (C-Space) checking: Determining if a robot's proposed pose intersects with obstacles.
• Grasp planning: Verifying that a robotic gripper's geometry does not collide with non-target objects during manipulation.
• Safe trajectory validation: Ensuring every incremental motion between waypoints is collision-free. Its efficiency allows for real-time re-planning in dynamic environments.

Beyond simple collision yes/no detection, GJK's core output is the minimum distance between two convex sets. This is essential for:

• Separation distance monitoring in safety systems.
• Computing the penetration vector when used with the Expanding Polytope Algorithm (EPA).
• Support function optimization: The algorithm iteratively calls a support function for each shape, which finds the farthest point in a given direction. This makes it highly efficient for complex convex shapes represented by their hulls.

GJK operates on a powerful geometric concept: the Minkowski difference between shapes A and B (A ⊖ B).

• Key Insight: The distance between A and B is the distance from the origin to this Minkowski difference. If the origin is inside A ⊖ B, the shapes intersect.
• Simplex Evolution: The algorithm constructs a simplex (a point, line segment, triangle, or tetrahedron) inside A ⊖ B that iteratively moves closer to the origin.
• Termination: It converges when the simplex contains the origin (collision) or when the distance to the origin is minimized (closest points found).

GJK excels where other methods falter:

• Vs. SAT (Separating Axis Theorem): GJK is generally faster for complex convex polyhedra, as SAT performance depends on the number of face/edge axes to test.
• Vs. Spatial Partitioning Alone: While grids or trees excel at broad-phase culling, GJK provides the exact narrow-phase result for convex pairs.
• Limitation: It is designed for convex shapes. For concave objects, they must first be decomposed into convex parts (convex decomposition), and GJK is run on each part pair.

A collision detection algorithm like GJK is only the first step in a physics pipeline. Its outputs feed the constraint solver:

• Output Data: For colliding pairs, GJK (with EPA) provides the penetration depth and contact normal.
• Solver Input: This data formulates non-penetration constraints and, with Coulomb friction models, friction constraints.
• Resolution: The solver (e.g., solving an LCP) computes the impulses or forces to resolve the collision, applying Newton-Euler equations to update body velocities and positions.

The Minkowski difference between two convex sets A and B, denoted A ⊖ B, is the foundational geometric operation used by the GJK algorithm. It is defined as the set of all vector differences between points in A and points in B. The key property is that the distance between A and B is the distance from the origin to this Minkowski difference set. If the sets intersect, the origin is contained within A ⊖ B. GJK efficiently samples this set without computing it explicitly.

• Core Property: Distance(A, B) = Distance(origin, A ⊖ B).
• Collision Test: Intersection occurs if origin ∈ (A ⊖ B).
• Algorithmic Role: GJK iteratively builds a simplex (a triangle in 2D, a tetrahedron in 3D) inside A ⊖ B to test for origin containment.

The Expanding Polytope Algorithm (EPA) is the natural companion to GJK for calculating penetration depth. When GJK detects a collision (origin inside the Minkowski difference), EPA takes over. It starts with the final simplex from GJK that contains the origin and iteratively expands it into a full convex polytope around the origin. By finding the closest face of this polytope to the origin, EPA calculates the minimum translation vector (MTV)—the direction and magnitude needed to separate the two intersecting shapes.

• Primary Function: Computes penetration depth and contact manifold.
• Input: The simplex from GJK where a collision was detected.
• Output: A contact normal and penetration depth for collision response.

A support function (or support mapping) is the critical subroutine used by GJK. For a convex shape and a given direction vector d, the support function returns the point on the shape that is farthest in that direction. Mathematically, S_A(d) = argmax_{v ∈ A} (v · d). GJK's efficiency stems from using this function to sample the Minkowski difference: S_{A⊖B}(d) = S_A(d) - S_B(-d). The algorithm only requires this mapping, not the full geometry.

• Key Feature: Enables GJK to work on any convex shape with a defined support mapping.
• Performance: The cost of GJK is largely the cost of evaluating the support function.
• Examples: For a sphere, it's center + radius * normalize(d). For a convex hull, it's a linear search over vertices.

In the context of GJK, a simplex is the simplest convex shape that can be formed in a given dimension: a point (0-simplex), line segment (1-simplex), triangle (2-simplex), or tetrahedron (3-simplex). GJK is an iterative algorithm that builds and updates a simplex within the Minkowski difference. Each iteration, it uses the support function to add a new point and then reduces the simplex to the smallest sub-simplex that still contains the closest point to the origin. This process converges quickly to the origin for collision or to the closest point for distance.

• Evolution: Starts as a single point, grows, and is reduced each step.
• Termination: The algorithm terminates when the simplex contains the origin (collision) or when the new support point does not move closer to the origin (distance found).

This is the full name of the GJK algorithm, specifically highlighting its primary function as a distance algorithm. While famously used for collision detection (a boolean yes/no test), its core mathematical output is the minimum distance between two convex sets. The collision check is a special case where that distance is zero. The algorithm's elegance lies in its iterative use of support functions and simplex reduction to converge on the closest points of the Minkowski difference to the origin, from which the inter-shape distance is directly derived.

• Original Purpose: Computing Euclidean distance between convex sets.
• Output: Can return the closest points on each shape in addition to the distance.
• Foundation: More general than a simple collision test; collision is a distance query where result ≤ 0.

A convex hull of a set of points is the smallest convex set that contains all the points. The GJK algorithm requires its input shapes to be convex. Many complex collision shapes in physics engines are represented as convex hulls of their vertices. The support function for a convex hull is computed by iterating over its vertices to find the one with the maximum dot product with the search direction. This is a common and efficient representation for polyhedral objects in simulations.

• Prerequisite for GJK: Input geometry must be convex; convex hulls are a standard way to ensure this.
• Support Calculation: Involves a linear scan or, for performance, a precomputed hill-climbing data structure.
• Use Case: Representing arbitrary rigid bodies for collision detection.