Gilbert–Johnson–Keerthi distance algorithm: Difference between revisions

Revision as of 14:59, 26 January 2023

Revision as of 02:21, 12 February 2023

Line 1:

{{Short description|Method of determining minimum distance between two convex sets}}

The '''Gilbert–Johnson–Keerthi distance [[algorithm]]''' is a method of determining the minimum distance between two [[convex set]]s, first published by [[Elmer G. Gilbert]], Daniel W. Johnson, and S. Sathiya Keerthi in 1998. Unlike many other distance algorithms, it does not require that the geometry data be stored in any specific format, but instead relies solely on a [[support function]] to iteratively generate closer [[simplex|simplices]] to the correct answer using the ''configuration space obstacle'' (CSO) of two convex shapes, more commonly known as the [[Minkowski difference]].

"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.

Line 8:

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.

The algorithm's stability, speed, and small storage footprint make it popular for Realtimerealtime [[collision detection]], especially in [[physics engine]]s for [[video games]].

== Overview ==