Improving the GJK algorithm for faster and more reliable distance queries between convex objects
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2017
|
| _version_ | 1797073572080910336 |
|---|---|
| author | Montanari, M Petrinic, N Barbieri, E |
| author_facet | Montanari, M Petrinic, N Barbieri, E |
| author_sort | Montanari, M |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:24:05Z |
| format | Journal article |
| id | oxford-uuid:69c743d9-73de-4aff-8e6f-b4dd7c010907 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:24:05Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:69c743d9-73de-4aff-8e6f-b4dd7c0109072022-03-26T18:53:10ZImproving the GJK algorithm for faster and more reliable distance queries between convex objectsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:69c743d9-73de-4aff-8e6f-b4dd7c010907Symplectic Elements at OxfordAssociation for Computing Machinery2017Montanari, MPetrinic, NBarbieri, EThis 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. |
| spellingShingle | Montanari, M Petrinic, N Barbieri, E Improving the GJK algorithm for faster and more reliable distance queries between convex objects |
| title | Improving the GJK algorithm for faster and more reliable distance queries between convex objects |
| title_full | Improving the GJK algorithm for faster and more reliable distance queries between convex objects |
| title_fullStr | Improving the GJK algorithm for faster and more reliable distance queries between convex objects |
| title_full_unstemmed | Improving the GJK algorithm for faster and more reliable distance queries between convex objects |
| title_short | Improving the GJK algorithm for faster and more reliable distance queries between convex objects |
| title_sort | improving the gjk algorithm for faster and more reliable distance queries between convex objects |
| work_keys_str_mv | AT montanarim improvingthegjkalgorithmforfasterandmorereliabledistancequeriesbetweenconvexobjects AT petrinicn improvingthegjkalgorithmforfasterandmorereliabledistancequeriesbetweenconvexobjects AT barbierie improvingthegjkalgorithmforfasterandmorereliabledistancequeriesbetweenconvexobjects |