Gilbert–Johnson–Keerthi (GJK) Algorithm

The GJK algorithm operates on shapes not through their explicit geometry, but via a support function. This function, given a direction vector d, returns the point on the shape that is farthest in that direction. This abstraction allows GJK to work with any convex shape (polyhedra, spheres, cones) as long as a support function is defined, making it highly versatile for complex collision geometries in physics engines.

GJK reduces the problem of finding the distance between two convex sets, A and B, to finding the distance between the origin and their Minkowski difference (A - B). A collision occurs if and only if the origin is inside this Minkowski difference set. The algorithm iteratively builds a simplex (a triangle in 3D, a line in 2D) inside this set, trying to enclose the origin.

The algorithm maintains a simplex—the simplest convex hull of a set of points from the Minkowski difference. Starting with a single point, it iteratively:

• Uses the support function to find a new point in a direction toward the origin.
• Updates the simplex to be the smallest subset that best approximates the origin's vicinity.
• Terminates when the simplex contains the origin (collision) or when the distance to the origin cannot be further reduced (minimum separation found).

A critical subroutine determines the point on the current simplex closest to the origin and identifies which subset of the simplex's vertices is relevant. For a 3D simplex (a tetrahedron), this involves checking which faces, edges, or vertices are closest to the origin. This efficiently reduces the simplex's dimensionality at each step, guiding the next support function query.

GJK terminates under two conditions:

• Collision Detected: The origin is found to be inside the current simplex.
• Minimum Distance Found: The algorithm converges when the new point found by the support function does not move closer to the origin than the closest point on the current simplex. The distance to this closest point is the separation distance. The algorithm typically converges in a very small number of iterations, often <10, even for complex shapes.

When GJK detects a collision (origin inside the Minkowski difference), the Expanding Polytope Algorithm (EPA) is often used as a post-processing step. While GJK finds that shapes intersect, EPA expands the final simplex from GJK into a full polytope surrounding the origin to calculate the penetration depth and the associated contact normal, which are necessary for collision response in physics engines.

The Minkowski Difference is the foundational geometric operation upon which the GJK algorithm is built. For two convex sets A and B, it is defined as A - B = {a - b | a ∈ A, b ∈ B}. The key insight is that the distance between A and B is the distance from the origin to this Minkowski Difference set. Furthermore, collision occurs if and only if the origin is contained within the Minkowski Difference. GJK efficiently iterates towards this origin by examining vertices of the Minkowski Difference without explicitly constructing the entire set.

A Support Function (or support mapping) is a core subroutine used by GJK. For a convex shape and a given direction vector d, the support function returns the point on the shape's boundary that is farthest in that direction (i.e., has the maximum dot product with d).

• For a polygon: the vertex with the highest dot product.
• For a sphere: center + (radius * normalized(d)).
• For a convex hull: a linear-time search over vertices. GJK uses this function on the Minkowski Difference by calculating support_A(d) - support_B(-d), allowing it to sample the combined shape efficiently.

A Simplex is the simplest geometric object of a given dimension in space (e.g., 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. It starts with a single point and iteratively adds a new support point in a direction toward the origin. The algorithm then reduces this simplex to the smallest sub-simplex (closest to the origin) and chooses a new search direction. This process continues until the simplex contains the origin (collision) or the distance cannot be improved (minimum distance found).

The Expanding Polytope Algorithm (EPA) is a companion algorithm often used after GJK detects a collision. While GJK efficiently determines if a collision occurred and provides a separation vector when objects are apart, EPA is used to compute the penetration depth and contact manifold (multiple contact points) when objects are intersecting.

• Process: EPA takes the final simplex from GJK that contains the origin and expands it into a full convex polytope around the origin by iteratively adding support points.
• Output: It returns the closest point on the polytope's boundary to the origin, which corresponds to the minimum translation vector (MTV) needed to separate the shapes.

The Separating Axis Theorem (SAT) is an alternative collision detection algorithm primarily for convex polygons/polyhedra. It states that two convex shapes are disjoint if and only if there exists an axis onto which their projections do not overlap. SAT tests a set of candidate axes derived from face normals and edge cross products.

• Comparison with GJK: SAT is often very efficient for low-vertex-count polygons but can become complex for curved shapes like ellipsoids. GJK is more general, handling any convex shape with a support function, and is often preferred in 3D for its consistent performance and ease of implementation for complex primitives.

A Bounding Volume Hierarchy (BVH) is a critical acceleration structure used in large-scale physics simulations and rendering. It is not a replacement for GJK but works in tandem with it.

• Function: A BVH organizes all objects in the scene into a tree, where each node has a simple bounding volume (e.g., an Axis-Aligned Bounding Box - AABB) that contains all its children.
• Pipeline Integration: In the broadphase collision detection stage, the BVH is traversed to quickly cull pairs of objects whose bounding volumes do not overlap. Only the potentially colliding pairs are passed to the narrowphase, where precise algorithms like GJK are executed. This drastically reduces the number of expensive GJK calls.