Algorytm GJK
Metoda rozstrzygania, czy dwie bryły wypukłe się zderzają, polegająca na szukaniu początku układu współrzędnych w ich różnicy Minkowskiego.
Nazwa pochodzi od nazwisk Elmera Gilberta, Daniela Johnsona i Sathiyi Keerthiego, którzy opisali algorytm w 1988 roku. Kluczowa obserwacja: dwa zbiory wypukłe się przecinają dokładnie wtedy, gdy ich różnica Minkowskiego zawiera początek układu. GJK szuka go bez budowania całej różnicy — pyta tylko o punkty podparcia, czyli najdalszy punkt kształtu w zadanym kierunku, i rozbudowuje maleńki sympleks (najwyżej czworościan), który albo otacza początek, albo dowodzi, że jest on nieosiągalny.
Ponieważ wszystko idzie przez funkcje podparcia, ten sam kod obsługuje wielościany, kule, walce i kapsuły — cokolwiek wypukłego. Gdy kształty są rozłączne, GJK podaje odległość; głębokość penetracji po nałożeniu się brył liczy się w parze z EPA. Algorytm jest filarem silników fizyki, takich jak Bullet, i działa w narrow phase.