Gilbert–Johnson–Keerthi distance algorithm
Encyclopedia
The Gilbert–Johnson–Keerthi distance algorithm
is a method of determining the minimum distance between two convex set
s. 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
es to the correct answer using the Minkowski sum (CSO) of two convex shapes.
"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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
is a method of determining the minimum distance between two convex set
Convex set
In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...
s. 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
Support (mathematics)
In mathematics, the support of a function is the set of points where the function is not zero, or the closure of that set . This concept is used very widely in mathematical analysis...
to iteratively generate closer simplex
Simplex
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,...
es to the correct answer using the Minkowski sum (CSO) of two convex shapes.
"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
Collision detection
Collision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...
, especially in physics engine
Physics engine
A physics engine is computer software that provides an approximate simulation of certain physical systems, such as rigid body dynamics , soft body dynamics, and fluid dynamics, of use in the domains of computer graphics, video games and film. Their main uses are in video games , in which case the...
s for video games.
Illustration
External links
- "A fast procedure for computing the distance between complex objects in three-dimensional space", Gilbert, Johnson and Keerthi - the initial publication