TR-IIS-01-013    pdffile

Geometric Interpretation and Comparisons of Enhancements of GJK Algorithm for Computing Euclidean Distance Between Convex Polyhedra

Jing-Sin Liu*, Yuh-ren Chien, Shen-Po Shiang and Wan-Chi Lee

Institute of Information Science 20, Academia Sinica Nankang, Taipei 115, Taiwan, R.O.C. Email: liu@iis.sinica.edu.tw (*correspondence address)

 The computation of Euclidean distance between two convex polyhedra is an important problem in robotics, computer graphics and real-time animation. An efficient and reliable distance computation procedure for a pair of convex sets is developed by Gilbert, Johnson and Keerthi (GJK) in 1988. GJK¡¦s convex set-theoretic approach is general and suitable for iterative numerical computation, however the GJK algorithm has the drawback of lack geometric intuition, especially in pairwise distance computation of convex polyhedra defined by the convex hull of its vertices in Euclidean 2D and 3D space. This paper investigates the steps of GJK algorithm from a geometric but intuitive point of view. By geometric reasoning, we present an improvement of the Euclidean distance computation algorithm made by GJK.  Some comparative simulations for both the static and tracking cases, in particular, collision-free motion planning of redundant robots, are shown to verify the algorithmic improvement in the process of distance computation. In addition, our work provides a simple and efficient algorithm for finding out the information where the closest point of a convex polyhedron to a reference point is: on the face, the edge, or on one vertex of the polyhedron.

Keywords. Distance computation, convex polyhedron, GJK algorithm, Euclidean distance, minimum distance.