Efficient Exact Collision Detection between Ellipsoids and Superquadrics via Closed-form Minkowski Sums
Efficient Exact Collision Detection between Ellipsoids and Superquadrics via Closed-form Minkowski Sums
复制标题
通过闭式 Minkowski 和进行椭球体和超二次曲面之间的高效精确碰撞检测
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
G. Chirikjian
中科院分区：
文献类型：
--
作者：
Sipu Ruan;Karen L. Poblete;Yingke Li;Qian Lin;Qianli Ma;G. Chirikjian
碰撞检测问题在计算机图形学、机器人运动规划、计算机辅助设计等领域引起了研究者的广泛关注，已经提出并应用了大量的基于凸多面体和包围盒的碰撞检测算法。然而，这些形状的算法严重依赖于网格的复杂性。本文研究了具有简单而精确数学描述的椭球和超二次曲面的碰撞检测问题。这些图元在表示复杂对象方面有广泛的应用，并且具有比网格少得多的参数。该碰撞检测方案的基础依赖于n维欧氏空间中椭球与超二次曲面之间的封闭形式Minkowski和。其基本思想是将椭球体收缩为点，并将每个超二次曲面展开为一个新的等距曲面。推导了二维和三维情况下点与一般凸可微参数曲面的相对位置检测方法，并给出了精确碰撞检测算法。为了比较精确算法和不精确算法，基于主运动学公式（PKF）引入了准确性度量。该算法与现有的著名算法：Gilbert-Johnson-Keerthi（GJK）和代数分离条件（ASC）进行了比较。结果表明，该算法与这些有效的检查器进行竞争。
Collision detection has attracted attention of researchers for decades in the field of computer graphics, robot motion planning, computer aided design, etc. A large number of successful algorithms have been proposed and applied, which make use of convex polytopes and bounding volumes as primitives. However, algorithms for those shapes rely significantly on the complexity of the meshes. This paper deals with collision detection for shapes with simple and exact mathematical descriptions, such as ellipsoids and superquadrics. These primitives have a wide range of applications in representing complex objects and have much fewer parameters than meshes. The foundation of the proposed collision detection scheme relies on the closed-form Minkowski sums between ellipsoids and superquadrics in n-dimensional Euclidean space. The basic idea here is to shrink the ellipsoid into a point and expand each superquadric into a new offset surface with closed-form parametric expression. The solutions for detecting relative positions between a point and a general convex differentiable parametric surface in both 2D and 3D are derived, leading to an algorithm for exact collision detection. To compare between exact and inexact algorithms, an accuracy metric is introduced based on the Principal Kinematic Formula (PKF). The proposed algorithm is then compared with existing wellknown algorithms: Gilbert-Johnson-Keerthi (GJK) and Algebraic Separation Conditions (ASC). The results show that the proposed algorithm performs competitively with these efficient checkers.