Gilbert–Johnson–Keerthi distance algorithm
The Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets. 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.
- Comment
- enThe Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets. 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.
- Depiction
- Has abstract
- enThe Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets. 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. "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 makes use of Johnson's distance sub algorithm, which computes in the general case the point of a tetrahedron closest to the origin, but is known to suffer from numerical robustness problems. In 2017 Montanari, Petrinic, and Barbieri proposed a new sub algorithm based on signed volumes which avoid the multiplication of potentially small quantities and achieved a speedup of 15% to 30%. 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 engines for video games.
- Hypernym
- Method
- Is primary topic of
- Gilbert–Johnson–Keerthi distance algorithm
- Label
- enGilbert–Johnson–Keerthi distance algorithm
- Link from a Wikipage to an external page
- arxiv.org/pdf/2205.09663.pdf
- mollyrocket.com/849
- web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances
- ora.ox.ac.uk/objects/uuid:69c743d9-73de-4aff-8e6f-b4dd7c010907/download_file%3Fsafe_filename=GJK.PDF&file_format=application%2Fpdf&type_of_work=Journal+article
- graphics.stanford.edu/courses/cs448b-00-winter/papers/gilbert.pdf
- www.youtube.com/watch%3Fv=ajv46BSqcK4
- Link from a Wikipage to another Wikipage
- Algorithm
- Category:Applied mathematics
- Category:Convex geometry
- Category:Geometric algorithms
- Collision detection
- Convex set
- File:Two types of collisions and corresponding CSO faces.svg
- Minkowski difference
- Minkowski Portal Refinement
- Physics engine
- Simplex
- Support function
- Tetrahedron
- Video games
- SameAs
- 3kqMW
- m.092s8x
- Q4060668
- Алгоритм Гилберта — Джонсона — Кирти
- Subject
- Category:Applied mathematics
- Category:Convex geometry
- Category:Geometric algorithms
- Thumbnail
- WasDerivedFrom
- Gilbert–Johnson–Keerthi distance algorithm?oldid=1100749934&ns=0
- WikiPageLength
- 4751
- Wikipage page ID
- 30861099
- Wikipage revision ID
- 1100749934
- WikiPageUsesTemplate
- Template:Math
- Template:Mathapplied-stub
- Template:Mvar
- Template:Short description
