All Topics  
Gilbert-Johnson-Keerthi distance algorithm

 

 
   Email Print
   Bookmark   Link
 

 

Gilbert-Johnson-Keerthi distance algorithm
 
 
  Topics Gilbert-Johnson-Keerthi distance algorithm Topic Home

The Gilbert–Johnson–Keerthi distance algorithm
Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
 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 or n-simplex is an n-dimensional analogue of a triangle. Specifically, a simplex is the convex hull of a set of affine transformation Point s in some Euclidean space of dimension n or higher ....
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
Full Discussion Forum



Encyclopedia


The Gilbert–Johnson–Keerthi distance algorithm
Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
 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 or n-simplex is an n-dimensional analogue of a triangle. Specifically, a simplex is the convex hull of a set of affine transformation Point s in some Euclidean space of dimension n or higher ....
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

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given solids....
, especially in physics engine
Physics engine

A physics engine is a computer program that simulates Newtonian physics models, using variables such as mass, velocity, friction and wind resistance....
s for video games.

External links

  • - the initial publication