Kollisionsdetektion

Kollisionsdetektion bezeichnet die Bestimmung, ob zwei oder mehr Objekte in einem Raum räumlich miteinander in Kontakt treten, und gegebenenfalls den Zeitpunkt dieses Kontakts. Sie ist zentral in Computerspielen, virtueller Realität, Robotik und Simulationen, wo sie realistische Bewegungen, Stabilität und Sicherheit ermöglicht. Grundsätzlich unterscheidet man zwischen einer Grobprüfung (Broad Phase), die potenzielle Kollisionspaare effizient eingrenzt, und einer Feinkollision (Narrow Phase), in der diese Paare exakt auf Kontakt geprüft werden.

In der Grobprüfung kommen oft einfache Geometrien und räumliche Strukturen zum Einsatz, zum Beispiel Achsen-ausgerichtete Bounding Boxes (AABB), Oriented Bounding Boxes (OBB), Bounding Volume Hierarchien (BVH), Quad-/Octrees oder R-tree-basierte Strukturen. Die Feinkollision verwendet genauere Tests wie die Trennungssatz-Methoden (SAT) für konvexe Polygone, Kreis- oder Kugeltests, Polygon- oder Polyhedra-Schnittprüfungen sowie Tests mit Minkowski-Differenz. Für bewegte Objekte wird häufig zwischen diskreter Kollisionsabfrage (bei festgelegten Zeitschritten) und kontinuierlicher Kollisionsdetektion (CCD) unterschieden, um das Durchschlagen schneller Objekte zu vermeiden. Die kontinuierliche Detektion liefert oft den sogenannten Time of Impact (TOI) und ermöglicht eine genaue Bestimmung des Kontaktzeitpunkts.

Nach der Erkennung folgt meist eine Kollisionsauflösung oder -reaktion, bei der Kontaktpunkte, Normalenvektoren und Eindringtiefe genutzt werden, um die Bewegung zu korrigieren oder Impulse zu setzen. Herausforderungen sind Robustheit, Numerik-Rundungsfehler, Degenerierungen und Leistungsbedarf in komplexen Szenen. Anwendungen reichen von Echtzeit-Computergrafik über robotische Planung bis hin zu physikbasierten Simulationen.