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

This paper considers fast algorithms for computing the Euclidean distance b etween objects that are modeled by convex polytopes in three-dimensional sp ace. The algorithms, designated by RGJK, are modifications of the Gilbert-J ohnson-Keerthi algorithm that follow the scheme originated by Cameron. Each polytope is represented by its vertices and a list of adjacent vertices fo r each vertex. When the algorithms are appropriately applied to a pair of o bjects 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 obje ct vertices. However, when the objects contain complex vertices or faces, t he time can increase drastically. Reasons for this problem are analyzed and algorithmic fixes for them are given. Other contributions to algorithmic p erformance include a procedure for reducing computational time in the prese nce of collisions. Comprehensive numerical experiments illuminate the depen dence 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 Mirtic h.