Improving the GJK algorithm for faster and more reliable distance queries between convex objects

Journal article

This article presents a new version of the Gilbert-Johnson-Keerthi (GJK) algorithm that circumvents the shortcomings introduced by degenerate geometries. The original Johnson algorithm and Backup procedure are replaced by a distance subalgorithm that is faster and accurate to machine precision, thus guiding the GJK algorithm toward a shorter search path in less computing time. Numerical tests demonstrate that this effectively is a more robust procedure. In particular, when the objects are found in contact, the newly proposed subalgorithm runs from 15% to 30% times faster than the original one. The improved performance has a significant impact on various applications, such as real-time simulations and collision avoidance systems. Altogether, the main contributions made to the GJK algorithm are faster convergence rate and reduced computational time. These improvements may be easily added into existing implementations; furthermore, engineering applications that require solutions of distance queries to machine precision can now be tackled using the GJK algorithm.

Authors: Montanari, M; Petrinic, N; Barbieri, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Graphics
• Volume: 36
• Issue: 3
• Article number: 30
• Publication date: 2017-06-15
• Acceptance date: 2017-03-15
• DOI: 10.1145/3083724
• ISSN: 1557-7368
• Keywords: distance measurement; Gilbert-Johnson-Keerthi algorithm; collision detection