Broad Phase und Narrow Phase der Kollisionserkennung: Kandidaten versus Kontakte

Warum die Kollisionsarbeit aufteilen?

Eine Kollisions-Pipeline hat zwei verschiedene Aufgaben: zuerst herausfinden, welche Shapes überhaupt interagieren könnten, dann bestimmen, was ihre Geometrie tatsächlich ergibt. Werden diese Aufgaben vermischt, entstehen irreführende Debug-Ansichten und falsch platzierte Optimierungen. Eine Überlappung von Bounding Boxes ist ein Anlass zur genaueren Prüfung, aber kein ausreichender Beleg dafür, dass sich zwei Spielobjekte berührt haben.

Der Kandidatenvertrag

Eine Broad Phase verwendet konservative Hüllen (Bounds), damit nicht jedes Shape-Paar getestet werden muss. Der Dynamic Tree von Box2D ordnet achsenparallele Bounds in einer binären Hierarchie an. [1] Narrow-Phase-Routinen arbeiten auf den Shapes selbst und können Contact Manifolds erzeugen, die Kontaktpunkte und eine Normale enthalten. Kollisionsfilterung und der spätere Constraint Solver haben jeweils eigene Zuständigkeiten. [2]

Durchgerechnetes Beispiel

Angenommen, es bewegen sich 100 Kisten. Würde jedes ungeordnete Paar getestet, wären 100 × 99 / 2 = 4950 Paartests nötig. Eine beispielhafte räumliche Abfrage liefere nach der Layer-Filterung 180 Kandidaten, und geometrische Tests finden 24 sich berührende Paare. Diese erfundenen Zahlen erläutern die Stufen der Pipeline; sie sind kein Performance-Ergebnis.

Eine lange, diagonal gedrehte Kiste kann eine grosse achsenparallele Box mit leeren Ecken haben. Eine andere Kiste, die in eine dieser Ecken ragt, sollte die Broad Phase passieren, den Shape-Test aber nicht bestehen. Würde jeder der 180 Kandidaten als Kollision gewertet, entstünden falsche Schadensereignisse. Umgekehrt kann eine Hülle, die ihr Shape nicht vollständig umschliesst, einen echten Kontakt verwerfen, bevor die Narrow Phase ihn zu sehen bekommt.

Praktischer Ablauf

Festlegen, wer die räumlichen Proxys nach Bewegung, Grössenänderung, Aktivierung oder Zerstörung aktualisiert. Stabile Paar-Identitäten verwenden, damit wiederholtes Entdecken eines Paars keine doppelten Gameplay-Ereignisse auslöst. Entscheiden, ob Filter vor der Ausgabe der Kandidaten, vor dem Shape-Test oder an beiden Stellen greifen; Regeln, die sich während des Spiels ändern können, dokumentieren.

Anzahl der Kandidaten, Anzahl der tatsächlichen Kontakte, Aufwand für Baum-Updates und Aufwand für geometrische Tests getrennt messen. In einer Diagnoseszene sowohl das tatsächliche Shape als auch seine Bounds darstellen. Die Szene sollte gedrehte dünne Objekte, dichte Stapel und ein grosses bewegtes Objekt zwischen kleinen enthalten. Verpasste Kontakte prüfen, bevor die Reduktion der Kandidaten feinjustiert wird.

Abwägungen und Grenzen

Grosszügige Bounds können den Pflegeaufwand des räumlichen Index senken, lassen dafür aber mehr Kandidaten durch. Enge Bounds können dieses Verhältnis umkehren. Ein Gitter, ein Baum oder Sweep-and-Prune muss anhand von Objektgrössen, Bewegung und Dichte im vorgesehenen Workload beurteilt werden.

Dichte Szenen können trotzdem viele gültige Paare erzeugen; eine räumliche Struktur kann unvermeidbare Interaktionen nicht verschwinden lassen. Broad-Phase-Überlappung, Narrow-Phase-Kontakt, Reaktion des Solvers und Trefferregeln des Gameplays getrennt beobachtbar halten. Auch Continuous Collision Detection braucht eine zeitbewusste Abfragestrategie; eine statische Überlappung an der Endposition deckt ein Bewegungsintervall nicht ab.

Quellen

[1] Dynamic tree — Erin Catto and Box2D contributors.

[2] Collision — Erin Catto and Box2D contributors.