Gilbert–Johnson–Keerthi distance algorithm: Difference between revisions

Revision as of 13:34, 24 December 2019

Revision as of 05:25, 8 January 2020

Line 2:

"Enhanced GJK" algorithms use edge information to speed up the algorithm by following edges when looking for the next simplex. This improves performance substantially for polytopes with large numbers of vertices.

GJK makes use of Johnson's distance subalgorithm, which computes in the general case the point of a tetrahedron closest to the origin, but is known to suffer from numerical roboustness problems. In 2017 Montanari, Petrinic, and Barbieri proposed a new subalgorithm based on signed volumes which avoids the multiplication of potentially small quantities and achieved a speedup of 15% to 30%.

GJK algorithms are often used incrementally in simulation systems and video games. In this mode, the final simplex from a previous solution is used as the initial guess in the next iteration, or "frame". If the positions in the new frame are close to those in the old frame, the algorithm will converge in one or two iterations. This yields collision detection systems which operate in near-constant time.

Line 40 ⟶ 42:

*[http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances "Computing the Distance between Objects", Oxford professor Stephen Cameron's implementation of GJK]

*[https://mollyrocket.com/849 A 52 minute video lecture on implementing Gilbert-Johnson-Keerthi]

*[https://ora.ox.ac.uk/objects/uuid:69c743d9-73de-4aff-8e6f-b4dd7c010907/download_file?safe_filename=GJK.PDF&file_format=application%2Fpdf&type_of_work=Journal+article "Improving the GJK algorithm for faster and more reliable distance queries between convex objects"], Montanari, Petrinic and Barbieri.

{{DEFAULTSORT:Gilbert-Johnson-Keerthi distance algorithm}}