GJK-algoritmen
En metod som avgör om två konvexa kroppar krockar genom att leta efter origo i deras Minkowskidifferens.
Uppkallad efter Elmer Gilbert, Daniel Johnson och Sathiya Keerthi, som beskrev den 1988. Nyckelidén är att två konvexa mängder skär varandra exakt när deras Minkowskidifferens innehåller origo. GJK letar efter origo utan att någonsin bygga hela differensen: den begär bara stödpunkter — formens ytterpunkt i en given riktning — och odlar en liten simplex (högst en tetraeder) som antingen omsluter origo eller visar att den är onåbar.
Eftersom allt sker via stödfunktioner fungerar samma kod för polyedrar, sfärer, cylindrar och kapslar — allt konvext. GJK ger avståndet när formerna är isär; för penetrationsdjupet när de redan överlappar kompletteras den med EPA. Algoritmen är en hörnsten i fysikmotorer som Bullet och körs i narrow phase.