使用伪距离和非约束优化算法进行凸物体间的碰撞检测

《IEEE Transactions on Robotics》：Collision Detection Between Convex Objects Using Pseudodistance and Unconstrained Optimization

碰撞检测在工程领域至关重要，本文提出一种基于δ-距离的新方法，将隐式曲面构成的凸物体碰撞检测转化为无约束凸优化问题。通过构建虚拟势场实现高效检测，并验证其在平面、二次、超quadric等不同隐式曲面及运动状态下的有效性。

　　

摘要：

碰撞检测问题在许多科学和工程领域中扮演着重要角色。本文提出了一种用于由隐式曲面片段构成的一般凸物体的碰撞检测方法。我们的方法基于两个关键思想：一是引入了一种新的伪距离概念，称为-距离，这种距离适用于隐式表示的凸物体，并具有所需的凸性和二次可微性；二是利用-距离函数在实空间中构建一个虚拟势场，从而将碰撞检测问题转化为一个无约束凸优化问题。该方法被扩展并应用于检测两个物体在沿线性平移轨迹连续运动时是否发生碰撞，这是连续碰撞检测子问题的一种特殊情况。我们使用C++实现了碰撞检测算法，并进行了大量实验，测试对象包括由平面、二次曲面、超二次曲面、超椭球面和超四次曲面及其片段构成的物体，这些物体处于静止状态或线性平移运动状态。实验结果表明，我们的方法性能良好，计算效率高且适用范围广泛。

引言

碰撞检测是机器人运动规划、计算机辅助几何设计、计算机动画与可视化以及现代科学和工程领域的许多其他领域中的一个基本问题。许多著名研究人员已经对此问题进行了研究，包括Gilbert [1]、[2]、Lin [3]、[4]、Wang [5]、[6]等（参见[7]、[8]、[9]及其中的参考文献）。主要发展了两类快速碰撞检测方法：一类基于离散化，适用于多面体物体[1]、[3]、[10]、[11]、[12]；另一类无需离散化，适用于由隐式或参数化曲面表示的曲线物体[13]、[14]、[15]、[16]、[17]。在本文中，我们研究了曲线物体之间的碰撞检测，并提出了一种通用且新的方法，用于高效检测由隐式曲面片段构成的凸物体之间的碰撞。该方法基于我们为曲线物体引入的-距离概念，以及将碰撞检测问题简化为无约束优化问题的方法。