碰撞检测作为计算机图形学和游戏开发中的核心技术，其重要性不言而喻。无论是游戏角色之间的交互，还是复杂环境中的物体碰撞判断，碰撞检测都承担着保证物理真实性和交互体验的关键任务。过去，行业内普遍以几何学视角来理解和实现碰撞检测，其中Gilbert–Johnson–Keerthi（GJK）算法被广泛认可为最有效的三维凸多面体碰撞检测算法之一。然而，近几年来，学术界的研究逐渐揭示了碰撞检测本质上是一个凸优化问题，并且GJK算法实际上是Frank-Wolfe算法（FW算法）的一种特例，这一发现为碰撞检测技术开辟了全新的优化路径。Frank-Wolfe算法诞生于1956年，是解决一类凸优化问题的迭代算法，以其结构简单且适用范围广泛而闻名。其核心思想在于通过每一步的线性近似，实现优化路径的不断逼近。
2022年发表的重要论文《Collision Detection Accelerated: An Optimization Perspective》首次明确指出GJK算法与Frank-Wolfe算法的内在联系，提出了利用优化理论改进碰撞检测的可能性，这引发了业界和研究界对传统几何方法的重新思考和优化算法的融合应用。GJK算法自1988年问世以来，就成为了像PhysX、Bullet、Chaos、Jolt和Rubikon等现代游戏物理引擎的基石。其通过迭代构造包含原点的凸包简化多面体碰撞问题，快速判断两个多面体是否相交。传统的GJK实现主要侧重于几何直观，通过支持函数（support functions）在Minkowski差集上搜索最接近原点的点，完成碰撞检测判定。尽管这一几何视角形象生动，但也让算法背后的优化机理常被忽视。实际上，将碰撞检测问题重构为一个寻找最小距离的优化问题非常自然。
具体地说，两个凸集合A和B的距离可以表述为寻找a∈A和b∈B使得距离|a−b|最小，等价变换后为寻找x∈A−B使得x的范数最小的问题。此时，A−B即为两个集合的Minkowski差集。将这个问题纳入凸优化框架，目标函数是距离的平方，梯度则是当前点的两倍。Frank-Wolfe算法的核心步骤，是在当前梯度负方向通过支持函数确定搜索点，然后在当前点和该搜索点之间进行线性组合，更新迭代位置。这与GJK中通过支持函数寻找最快收敛方向，以支持点构建凸包的过程高度吻合。传统的Frank-Wolfe算法中，活跃集（active set）多为简单线段，更新过程仅利用当前迭代点与支持点的线性组合，这导致算法在目标函数值局部较小时容易产生振荡，表现出收敛缓慢。
然而，GJK通过维护一个更丰富的活跃集——即多个支持点的凸包——来实现更高效的投影，进而快速确定原点是否在凸包内。这个丰富的活跃集机制正是GJK区别于经典Frank-Wolfe算法的关键所在，也使得GJK在近似与判定碰撞时表现出卓越性能。此外，通过优化视角重新分析GJK，可以为算法的改进提供启示。例如，传统GJK倾向于舍弃历史活跃集信息，而优化算法的活跃集管理则强调保留有利于加快收敛的点，借助现代凸优化中的fully-corrective策略和投影方法，可以设计出更稳定、更快速的碰撞检测算法。同时，优化算法中的线性子问题求解与支持点搜索深度耦合，优化理论为支持函数的设计和近似方法提供理论支撑，进一步提升实用算法的效率。值得注意的是，虽然游戏开发者历来偏重几何直观教学和实现，诸如Gino van den Bergen、Ericson和Casey Muratori等的图形化讲解深入浅出，但围绕优化理论的讨论却相对匮乏。
这一现象或源于学科背景和应用导向的不同。随着2022年的研究推广，越来越多从业者开始关注GJK的优化算法本质，从而推动跨领域知识融合。结合这些洞察，未来的碰撞检测算法可能更加注重多点活跃集的维护策略，改进支持函数的计算效率，引入更先进的凸优化方法，如加速梯度法和自适应步长策略，为游戏物理引擎带来性能飞跃。总结来说，碰撞检测作为家喻户晓的计算几何问题，其本质是凸优化问题。GJK算法正是Frank-Wolfe算法在该领域的具体体现，通过维护多点活跃集实现高效搜索和投影判定。了解并利用这一深层联系，不仅有助于更易于理解和教学碰撞检测技术，也为算法的改进和性能提升提供了理论支撑和实践方向。
在游戏开发和图形物理模拟日益复杂的今天，拥抱优化理论与传统几何方法相结合的思路，将成为推动行业发展的关键动力。
