Market›Gilbert–Johnson–Keerthi distance algorithm
Company Profile

Gilbert–Johnson–Keerthi distance algorithm

The Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets, first published by Elmer G. Gilbert, Daniel W. Johnson, and S. Sathiya Keerthi 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 function to iteratively generate closer simplices to the correct answer using the configuration space obstacle (CSO) of two convex shapes, more commonly known as the Minkowski difference.

Overview
GJK relies on two functions: • \mathrm{Support}(\mathrm{shape}, \vec{d}), which returns the point on which has the highest dot product with \vec{d}. • \mathrm{NearestSimplex}(s), which takes a simplex and returns the simplex on closest to the origin, and a direction toward the origin normal to the new simplex. If itself contains the origin, accepts and the two shapes are determined to intersect. The simplices handled by may each be any simplex sub-space of . 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): 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 == Illustration==
Source: Wikipedia ↗
tickerdossier.comtickerdossier.substack.com