The Gilbert-Johnson-Keerthi distance algorithm: a fast version for incremental motions
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 1183-1189
- https://doi.org/10.1109/robot.1997.614298
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 (1988) 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-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 (1991). 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.Keywords
This publication has 4 references indexed in Scilit:
- Efficient collision detection using fast distance-calculation algorithms for convex and non-convex objectsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A fast algorithm for incremental distance calculationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A comparison of two fast algorithms for computing the distance between convex polyhedraIEEE Transactions on Robotics and Automation, 1997
- A fast procedure for computing the distance between complex objects in three-dimensional spaceIEEE Journal on Robotics and Automation, 1988