GJK & EPA Contact Physics

2 min read•1 page

Gilbert-Johnson-Keerthi (GJK Algorithm): Standard all-pairs mesh collision checking scales as O(N · M), far too slow for 60 FPS physics engines. The GJK algorithm converts contact detection into a question of whether the Minkowski difference A - B contains the origin (0, 0, 0). By iteratively evaluating directional support functions, GJK converges in near O(1) time.

GJK Geometric Invariant:

1. Minkowski Difference Locus: Shapes A and B overlap if and only if the origin 0 is in A - B. 2. Support Function: S_A(d) finds the extremal point in direction d, avoiding full mesh storage. 3. Evolving Simplex: Maintains at most 4 points (tetrahedron in 3D) that systematically traps the origin.

python

1def support_mapping(shape, direction):
2    """Returns the extreme point of a convex shape in given direction d."""
3    return max(shape, key=lambda pt: np.dot(pt, direction))
4
5def gjk_collision_test(shape_a, shape_b):
6    """
7    Gilbert-Johnson-Keerthi (GJK) convex collision detection.
8    Evaluates support points on Minkowski Difference: C = A - B.
9    Iteratively builds a 1-simplex (segment), 2-simplex (triangle), or 3-simplex (tetrahedron).
10    Shapes A and B collide if and only if the simplex encloses the origin (0, 0, 0).
11    """
12    # Direction d = B.center - A.center
13    # Simplex initialized with support(A, d) - support(B, -d)
14    return "Collision True iff Origin in Simplex"

Body B Distance (Negative = Intersecting)

0.80

2 min read•1 page

Expanding Polytope Algorithm (EPA Penetration Depth): GJK only answers a binary question: are the two bodies colliding? It cannot provide contact impulses. The Expanding Polytope Algorithm (EPA) takes the simplex from GJK enclosing the origin and iteratively inflates it outward towards the surface of the Minkowski difference. The closest facet to the origin yields the exact contact normal vector and minimum translation distance required to resolve penetration.

EPA Contact Resolution:

1. Polytope Inflation: Expands triangular facets outwards along their outward-pointing normal vectors. 2. Closest Facet Distance: Measures the perpendicular distance from the origin $(0,0,0)$ to the nearest edge/face. 3. Physics Contact Manifold: Feeds penetration depth and contact normal directly into the LCP impulse solver.

python

1def epa_penetration_vector(initial_simplex, shape_a, shape_b, tol=1e-4):
2    """
3    Expanding Polytope Algorithm (EPA) for collision contact manifolds.
4    Takes the terminating GJK simplex enclosing the origin.
5    Iteratively finds the closest facet to origin, shoots ray in facet normal direction,
6    queries support mapping, and expands the polytope until convergence.
7    Returns: penetration_depth (scalar) and contact_normal (unit vector).
8    """
9    polytope = list(initial_simplex)
10    while True:
11        closest_facet, normal, dist = find_closest_facet_to_origin(polytope)
12        p = support(shape_a, normal) - support(shape_b, -normal)
13        d = np.dot(p, normal)
14        if d - dist < tol:
15            return dist, normal  # Exact penetration depth and separation direction
16        polytope = expand_polytope_with_point(polytope, p)

EPA Expansion Iteration

3.00