Gilbert–Johnson–Keerthi distance algorithm: Difference between revisions

Revision as of 13:40, 13 April 2017

Latest revision as of 14:57, 18 June 2024

(30 intermediate revisions by 26 users not shown)

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, withfirst linearpublished complexity<ref>"Theby [[Elmer G. Gilbert-]], Daniel W. Johnson-Keerthi, Distanceand Algorithm"S. PatrickSathiya Lindemann,Keerthi 2009</ref>in 1988. 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 (mathematics)|support function]] to iteratively generate closer [[simplex|simplices]] to the correct answer using the [[Minkowski''configuration sum]]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.

GJK makes use of Johnson's distance sub algorithm, which computes in the general case the point of a tetrahedron closest to the origin, but is known to suffer from numerical robustness problems. In 2017 Montanari, Petrinic, and Barbieri proposed a new sub algorithm based on signed volumes which avoid 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 11 ⟶ 14:

GJK relies on two functions:

* <math>\mathrm{Support}(\mathrm{shape}, \vec{d})</math>, which returns the point on <{{math>|shape</math>}} which has the highest [[dot product]] with <math>\vec{d}</math>.

* <math>\mathrm{NearestSimplex}(s)</math>, which takes a simplex <math>{{mvar|s</math>}} and returns the simplex on <math>{{mvar|s</math>}} closest to the origin, and a direction toward the origin normal to the new simplex. If <math>{{mvar|s</math>}} itself contains the origin, <{{math>|NearestSimplex</math>}} accepts <math>{{mvar|s</math>}} and the two shapes are determined to intersect.

The simplices handled by <{{math>|NearestSimplex</math>}} may each be any simplex sub-space of {{math|'''R'''^''n''}}. For example in 3D, they may be a point, a line segment, a triangle, or a [[tetrahedron]]; each defined by 1, 2, 3, or 4 points respectively.

=== Pseudocode ===

'''function''' GJK_intersection(shape p, shape q, vector initial_axis):

<code>

vector A = Support(p, initial_axis) -− Support(q, -initial_axis−initial_axis)

function GJK_intersection(shape p, shape q, vector initial_axis):

simplex s = {A}

vector A = Support(p, initial_axis) - Support(q, -initial_axis)

vector simplex sD = {A}−A

vector D = -A

'''loop''':

A = Support(p, D) -− Support(q, -D−D)

'''if''' dot(A, D) < 0:

reject

s = s ∪ {A}

s, D, contains_origin := NearestSimplex(s)

'''if''' contains_origin:

accept

</code>

== 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).]]

==See also==

*[[Minkowski Portal Refinement]]

*[[Hyperplane separation theorem]]

==External links==

*[httphttps://ieeexploregraphics.ieeestanford.orgedu/xplcourses/freeabs_allcs448b-00-winter/papers/gilbert.jsp?&arnumber=2083pdf "A fast procedure for computing the distance between complex objects in three-dimensional space", Gilbert, Johnson and Keerthi] - the initial publication

*[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://www.youtube.com/watch?v=ajv46BSqcK4 "A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)"]

*[https://mollyrocket.com/849 A 52 minute video lecture on implementing GilberGilbert-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.

*[https://arxiv.org/pdf/2205.09663.pdf "Collision Detection Accelerated: An Optimization Perspective"], Montaut, Le Lidec, Petrik, Sivic and Carpentier. This research article notably shows how the original GJK algorithm can be accelerated by exploiting Nesterov-type acceleration strategies, contributing to lowering the overall computational complexity of GJK.

*[https://computerwebsite.net/writing/gjk "the Gilbert–Johnson–Keerthi algorithm explained as simply as possible"]

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

[[Category:Geometric algorithms]]

[[Category:Convex geometry]]

[[Category:Applied mathematics]]