Efficient Exact Collision Detection between Ellipsoids and Superquadrics via Closed-form Minkowski Sums

摘要

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.