Gilbert–Johnson–Keerthi distance algorithm

<h2 id="overview">Overview</h2>
<p>GJK relies on two functions:
</p>
<ul><li>
  
    
      
        
          S
          u
          p
          p
          o
          r
          t
        
        (
        
          s
          h
          a
          p
          e
        
        ,
        
          
            
              d
              →
            
          
        
        )
      
    
    {\displaystyle \mathrm {Support} (\mathrm {shape} ,{\vec {d}})}
  
, which returns the point on shape which has the highest <a href="/facts/Dot_product/tNz8MLjT">dot product</a> with 
  
    
      
        
          
            
              d
              →
            
          
        
      
    
    {\displaystyle {\vec {d}}}
  
.</li>
<li>
  
    
      
        
          N
          e
          a
          r
          e
          s
          t
          S
          i
          m
          p
          l
          e
          x
        
        (
        s
        )
      
    
    {\displaystyle \mathrm {NearestSimplex} (s)}
  
, which takes a simplex s and returns the simplex on s closest to the origin, and a direction toward the origin normal to the new simplex. If s itself contains the origin, NearestSimplex accepts s and the two shapes are determined to intersect.</li></ul>
<p>The simplices handled by NearestSimplex may each be any simplex sub-space of R<i>n</i>. For example in 3D, they may be a point, a line segment, a triangle, or a <a href="/facts/Tetrahedron/7mkSrl6j">tetrahedron</a>; each defined by 1, 2, 3, or 4 points respectively.
</p>
<h3>Pseudocode</h3>
function GJK_intersection(shape p, shape q, vector initial_axis):
    vector  A = Support(p, initial_axis) − Support(q, −initial_axis)
    simplex s = {A}
    vector  D = −A

loop:
        A = Support(p, D) − Support(q, −D)
        if dot(A, D) < 0:
            reject
        s = s ∪ {A}
        s, D, contains_origin := NearestSimplex(s)
        if contains_origin:
            accept

<h2 id="illustration">Illustration</h2>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Minkowski_Portal_Refinement/sBNlCGYI">Minkowski Portal Refinement</a></li>
<li><a href="/facts/Hyperplane_separation_theorem/9EdtJ3oh">Hyperplane separation theorem</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://graphics.stanford.edu/courses/cs448b-00-winter/papers/gilbert.pdf">"A fast procedure for computing the distance between complex objects in three-dimensional space", Gilbert, Johnson and Keerthi</a> - the initial publication</li>
<li><a href="http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances">"Computing the Distance between Objects", Oxford professor Stephen Cameron's implementation of GJK</a></li>
<li><a href="https://www.youtube.com/watch?v=ajv46BSqcK4">"A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)"</a></li>
<li><a href="https://mollyrocket.com/849">A 52 minute video lecture on implementing Gilbert-Johnson-Keerthi</a></li>
<li><a href="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"</a>, Montanari, Petrinic and Barbieri.</li>
<li><a href="https://arxiv.org/pdf/2205.09663.pdf">"Collision Detection Accelerated: An Optimization Perspective"</a>, 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.</li>
<li><a href="https://computerwebsite.net/writing/gjk">"the Gilbert–Johnson–Keerthi algorithm explained as simply as possible"</a></li></ul>

Gilbert–Johnson–Keerthi distance algorithm open-in-new

Gilbert–Johnson–Keerthi distance algorithm