Gilbert-Johnson-Keerthi distance algorithm: A fast version for incremental motions

Abstract

An algorithm is presented for computing the Euclidean distance between a pair of objects represented by convex polytopes in three dimensional space. It is a fast version of the well known algorithm by Gilbert, Johnson and Keerthi in which the polytopes are characterized by their vertices. The improvement in speed comes from the inclusion of additional structural information on the objects; for each vertex there is a list of adjacent vertices. No other information or preprocessing of data is needed. Following Cameron, the adjacency structures are used to greatly reduce the number of inner product evaluations needed to compute the polytope support functions used in the original Gilbert, Johnson and Keerthi algorithm. When the algorithm is applied to a pair of objects that move incrementally along smooth paths, it shares the advantage of the incremental distance algorithm introduced by Lin and Canny: under appropriate conditions, the computational time is very small and does not depend significantly on the total number of object vertices. Algorithmic details and performance issues are developed fully. Computational experiments provide quantitative data on the effects of object complexity and the size of incremental object motions.