|
The '''Gilbert–Johnson–KeerthiGilbert-Johnson-Keerthi''' distance [[algorithm]]''' is a method of determining the minimum distance between two [[convex set]]s shapes. Unlike many other distance algorithms, it does notdoesn't require that the geometry data be stored in any specific format, but instead relies solely on a [[support (mathematics)|support function]] to iteratively generate closer [[simplex]]espoints to the correct answer using the [[Minkowski sum]] (CSO) of two convex shapes.
The algorithm's stability, speed, and small storage footprint make it popular for realtime [[collision detection]], especially in [[physics enginesimulation]] s for [[video games]]. ▼"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 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 realtime [[collision detection]], especially in [[physics engine]]s for [[video games]].
== Illustration==
[[File:Two types of collisions and corresponding CSO faces.svg|550px|thumb|center|The two types of collision and corresponding CSO face: face-vertex (top) and edge-edge (bottom).]]
==External links==
*[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?&arnumber=2083 "A fast procedure for computing the distance between complex objects in three-dimensional space", Gilbert, Johnson and Keerthi] - the initial publication
*[http://intl.ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=614298 "TheMore Gilbert–Johnson–Keerthi distance algorithm: a fast version for incremental motions", Ong and GilbertInformation]
*[http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances "Computing the Distance between Objects", Oxford professor Stephen Cameron's implementation of GJK]
[[Category:Geometric algorithms]]
[[Category:Convex geometry]]
*[http://code.google.com/p/gjkd/ A 2D implementation of the Gilbert–Johnson–Keerthi (GJK) algorithm, written in the D programming language]
{{Math-stub}}
[[ru:Алгоритм Гилберта — Джонсона — Кёрти]]
| 