PSA: Collision Detection is an optimization problem and GJK is Frank-Wolfe
10 months ago
- #game-physics
- #collision-detection
- #optimization
- 碰撞检测本质上是一个凸优化问题。
- GJK算法是Frank-Wolfe（FW）算法的一个特定子案例。
- 2022年的一篇论文明确展示了GJK与FW之间的联系。
- GJK被广泛应用于现代游戏物理引擎，如PhysX、Bullet和Chaos。
- Frank-Wolfe是一种用于解决凸优化问题的通用迭代算法，于1956年提出。
- 在游戏编程教学中，GJK的优化视角较少被强调。
- 2022年的论文使用优化概念对GJK进行了直观解释。
- GJK维护一个单纯形的活跃集，提高了边界附近的精度。
- 该论文包含易于理解的解释和代码示例。
- 历史上，游戏开发者可能并未意识到GJK的FW推导过程。