Fast versions of the Gilbert-Johnson-Keerthi distance algorithm: Additional results and comparisons

Abstract

This paper considers fast algorithms for computing the Euclidean distance between objects that are modeled by convex polytopes in three-dimensional space. The algorithms, designated by RGJK, are modifications of the Gilbert-Johnson-Keerthi algorithm that follow the scheme originated by Cameron. Each polytope is represented by its vertices and a list of adjacent vertices for each vertex. When the algorithms are appropriately applied to a pair of objects that have small incremental motions, they share the advantage of the closest-feature algorithm introduced by Lin and Canny: computational time is very small and does not depend significantly on the total number of object vertices. However, when the objects contain complex vertices or faces, the time can increase drastically. Reasons for this problem are analyzed and algorithmic fixes for them are given. Other contributions to algorithmic performance include a procedure for reducing computational time in the presence of collisions. Comprehensive numerical experiments illuminate the dependence of computational time on algorithmic details, object complexity, and the size of incremental motions. The experiments include direct comparisons of RGJK with the closest-feature algorithms of Lin and Canny and of Mirtich.