PSA: Collision Detection is an optimization problem and GJK is Frank-Wolfe

9 months ago

Collision detection is fundamentally a convex optimization problem.
The GJK algorithm is a specific sub-case of the Frank-Wolfe (FW) algorithm.
The connection between GJK and FW was explicitly shown in a 2022 paper.
GJK is widely used in modern game physics engines like PhysX, Bullet, and Chaos.
Frank-Wolfe is a general iterative algorithm for solving convex problems, discovered in 1956.
The optimization perspective of GJK is less emphasized in game programming pedagogy.
The 2022 paper provides an intuitive explanation of GJK using optimization concepts.
GJK maintains an active set that is a simplex, improving accuracy near boundaries.
The paper includes accessible explanations and code examples.
Game developers may not have been aware of the FW derivation of GJK historically.

Hasty Briefsbeta