Collision Detection between Smooth Convex Bodies via Riemannian Optimization Framework

Abstract

Collision detection is a fundamental problem across various fields such as robotics, physical simulation, and computer graphics. While numerous studies have provided efficient solutions, based on the well-known Gilbert, Johnson, and Keerthi (GJK) algorithm and Expanding Polytope Algorithm (EPA), existing methods utilizing GJK-EPA often struggle with smooth strictly convex shapes like ellipsoids. This paper proposes a novel approach to the collision detection problem converting it to a problem compatible with an unconstrained Riemannian optimization problem. Moreover, we presents a specific method of solving the problem based on twice differentiable support functions and the Riemannian trust region (RTR) method. The method exhibits fast and robust convergence rate, leveraging the well-established theory of Riemannian optimization. The evaluation studies comparing our method to GJK-EPA method are done with pre-defined primitive shapes. Additionally, a test result with several more complex shapes is demonstrated exhibiting the method’s effectiveness and applicability.