The
Gilbert–Johnson–Keerthi distance algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
is a method of determining the minimum distance between two
convex setIn 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. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not...
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 functionIn 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
simplexIn 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 with n + 1 vertices, of which the simplex is the convex hull...
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.
Discussion
Ask a question about 'Gilbert-Johnson-Keerthi distance algorithm' Start a new discussion about 'Gilbert-Johnson-Keerthi distance algorithm' Answer questions from other users |
The
Gilbert–Johnson–Keerthi distance algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
is a method of determining the minimum distance between two
convex setIn 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. For example, a solid cube is convex, but anything that is hollow or has a dent in it, for example, a crescent shape, is not...
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 functionIn 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
simplexIn 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 with n + 1 vertices, of which the simplex is the convex hull...
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 detectionIn physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids. Simulating what happens once a collision is detected is sometimes referred to as "collision response"...
, especially in
physics engineA physics engine is a computer program that simulates physics models, using variables such as mass, velocity, friction, and wind resistance. It can simulate and predict effects under different conditions that would approximate what happens in real life or in a fantasy world...
s for video games.
External links