Collision detection between two convex shapes is an essential feature of any physics engine or robot motion planner. It has often been tackled as a computational geometry problem, with the Gilbert, Johnson and Keerthi (GJK) algorithm being the most common approach today. In this work we leverage the fact that collision detection is fundamentally a convex optimization problem. In particular, we establish that the GJK algorithm is a specific sub-case of the well-established Frank-Wolfe (FW) algorithm in convex optimization. We introduce a new collision detection algorithm by adapting recent works linking Nesterov acceleration and Frank-Wolfe methods. We benchmark the proposed accelerated collision detection method on two datasets composed of strictly convex and non-strictly convex shapes. Our results show that our approach significantly reduces the number of iterations to solve collision detection problems compared to the state-of-the-art GJK algorithm, leading to up to two times faster computation times.
翻译:两种 convex 形状之间的碰撞探测是任何物理学引擎或机器人运动规划师的一个基本特征。 它通常被当作一个计算几何学问题来处理, 吉尔伯特、 约翰逊和凯尔西( GJK) 算法是当今最常见的方法。 在这项工作中,我们利用了以下事实,即碰撞探测基本上是一个 convex 优化问题。 特别是, 我们确定, GJK 算法是精密的 Frank- Wolfe (FW) 算法在 convex 优化中的一种具体的子案例。 我们通过调整最近将Nesterov 加速和 Frank- Wolfe 方法联系起来的工程, 引入了新的碰撞探测算法。 我们把拟议的加速碰撞探测方法以两种数据集作为基准, 由严格的 convex 和 非限制性的 convex 形状组成。 我们的结果表明, 我们的方法大大降低了解决碰撞探测问题所需的迭代数, 与最先进的 GJK 算法相比, 导致速度达2倍。