💥 Wykrywanie kolizji: od AABB do algorytmu GJK

Architektura dwufazowa

Każdy praktyczny system wykrywania kolizji wykorzystuje architekturę dwufazową. Faza szeroka szybko eliminuje pary obiektów, które na pewno nie mogą się zderzyć, korzystając z konserwatywnych, lecz tanich przybliżeń. Faza wąska wykonuje następnie precyzyjne testy geometryczne na niewielkim zbiorze par-kandydatów, które przetrwały fazę szeroką. Ten podział jest kluczowy: faza szeroka nie może niczego pominąć (brak fałszywych negatywów), ale może mieć fałszywe pozytywy; faza wąska musi być dokładna.

Prostopadłościany otaczające wyrównane do osi (AABB)

Najprostszą bryłą otaczającą jest prostopadłościan wyrównany do osi (Axis-Aligned Bounding Box, AABB): najmniejszy prostopadłościan o bokach równoległych do osi układu współrzędnych, który w całości zawiera obiekt. Dla siatki (mesha) AABB definiują minimalne i maksymalne współrzędne x, y, z spośród wszystkich wierzchołków.

Sprawdzenie przecięcia dwóch AABB to jedno porównanie na oś — sześć porównań łącznie:

bool aabbOverlap(AABB a, AABB b) {
  return a.min.x <= b.max.x && a.max.x >= b.min.x
      && a.min.y <= b.max.y && a.max.y >= b.min.y
      && a.min.z <= b.max.z && a.max.z >= b.min.z;
}

AABB są szybkie w testowaniu i aktualizacji, ale mogą być zbyt „luźne" dla obróconych obiektów — długi, ukośny pręt ma duży AABB, który przecina się z wieloma innymi obiektami. Dla obiektów obracających się prostopadłościany zorientowane (OBB) przylegają ściślej, lecz są droższe w testowaniu i aktualizacji.

Hashowanie przestrzenne dla fazy szerokiej

Hashowanie przestrzenne dzieli przestrzeń na regularną siatkę i hashuje każdą komórkę do płaskiej tablicy. Dla każdego obiektu obliczane jest, które komórki siatki przecina jego AABB, po czym obiekt jest wstawiany do tych komórek. Aby znaleźć kandydatów na kolizję dla obiektu, przeszukuje się te same komórki i zwraca wszystkie inne znalezione tam obiekty.

function cellKey(x, y, cellSize) {
  const cx = Math.floor(x / cellSize);
  const cy = Math.floor(y / cellSize);
  // Duże liczby pierwsze, by zmniejszyć kolizje hashu
  return (cx * 92837111) ^ (cy * 689287499);
}

Dla równomiernie rozłożonych obiektów hashowanie przestrzenne osiąga złożoność O(1) na wyszukanie obiektu. Rozmiar komórki powinien odpowiadać średniemu rozmiarowi obiektu — zbyt małe komórki oznaczają wiele komórek na obiekt; zbyt duże oznaczają wiele obiektów na komórkę. Hashowanie przestrzenne doskonale sprawdza się w symulacjach cząstek i dynamice płynów, gdzie oddziałują ze sobą tysiące cząstek o tym samym rozmiarze.

Hierarchie brył otaczających (BVH)

BVH to drzewo brył otaczających. Węzły liściowe zawierają pojedyncze prymitywy (trójkąty, kształty). Węzły wewnętrzne zawierają AABB otaczające wszystkie swoje dzieci. Aby przetestować obiekt A względem sceny, przechodzi się przez BVH: jeśli AABB obiektu A nie przecina się z AABB węzła, całe poddrzewo jest pomijane; w przeciwnym razie rekurencja schodzi do dzieci. Redukuje to problem o złożoności O(n²) do O(n log n) lub lepszej dla typowych scen.

Budowa BVH wykorzystuje heurystyki podziału. Heurystyka powierzchni (Surface Area Heuristic, SAH) minimalizuje oczekiwaną liczbę testów przecięcia, dzieląc w pozycji minimalizującej SA(left)·N(left) + SA(right)·N(right), gdzie SA to pole powierzchni, a N to liczba trójkątów. Drzewa BVH budowane metodą SAH są stosowane w trasowaniu promieni (Embree, OptiX) oraz w silnikach fizyki gier (Bullet, PhysX). Sceny dynamiczne wymagają przebudowy lub ponownego dopasowania BVH w każdej klatce — nowoczesne buildery BVH na GPU robią to w milisekundy, wykorzystując równoległe podejścia top-down lub sortowanie po kodach Mortona.

Twierdzenie o osi rozdzielającej (SAT)

Dla kształtów wypukłych twierdzenie o osi rozdzielającej (Separating Axis Theorem, SAT) daje dokładny test: dwa wypukłe kształty nie przecinają się wtedy i tylko wtedy, gdy istnieje oś rozdzielająca — kierunek, wzdłuż którego ich rzuty się nie pokrywają. Dla wielokątów/wielościanów wystarczy sprawdzić normalne ścian oraz (w 3D) iloczyny wektorowe krawędzi jako osie kandydackie.

Dla dwóch wypukłych wielokątów o n i m krawędziach SAT wymaga n + m testów osi, każdy o złożoności O(1). Jeśli którakolwiek oś je rozdziela, kształty się nie zderzają. Jeśli wszystkie osie wykazują nakładanie się, kształty się zderzają. Oś o minimalnym nakładaniu daje normalną kolizji i głębokość penetracji potrzebną do reakcji. SAT jest dokładny, szybki i dostarcza bogatych informacji o kontakcie — to preferowany algorytm fazy wąskiej dla wypukłych wielościanów w silnikach takich jak Box2D.

Algorytm GJK

Algorytm Gilberta-Johnsona-Keerthiego (1988) określa, czy dwa wypukłe kształty się przecinają, iteracyjnie obliczając najbliższy punkt różnicy Minkowskiego względem początku układu współrzędnych. Różnica Minkowskiego A ⊖ B = {a − b | a ∈ A, b ∈ B} zawiera początek układu wtedy i tylko wtedy, gdy A i B się przecinają.

GJK wykorzystuje funkcje podparcia: dla kierunku d, support(A, d) = argmax_{a ∈ A} d·a — punkt na A najbardziej oddalony w kierunku d. Dla kształtów wypukłych z analitycznymi funkcjami podparcia (kule, kapsuły, prostopadłościany) ma to złożoność O(1). GJK nigdy jawnie nie oblicza różnicy Minkowskiego; próbkuje ją poprzez wywołania funkcji podparcia i buduje sympleks (punkt, krawędź, trójkąt, czworościan), zbiegający do najbliższego elementu.

GJK jest „rozgrzewany" sympleksem z poprzedniej klatki, co czyni go niezwykle szybkim dla wolno poruszających się obiektów — zwykle zbiega w 2–4 iteracjach. W połączeniu z EPA (Expanding Polytope Algorithm) do obliczania głębokości penetracji, gdy wykryto nakładanie się, GJK+EPA jest standardową fazą wąską dla ogólnych kształtów wypukłych w nowoczesnych silnikach fizyki.