Kollisionserkennung (algorithmische Geometrie)

Als Kollisionserkennung oder Kollisionsabfrage (englisch Collision Detection) wird in der algorithmischen Geometrie das Erkennen des Berührens oder Überlappens zweier oder mehrerer geometrischer (starrer oder deformierbarer) Objekte im zwei- oder dreidimensionalen Raum verstanden. Einer Kollisionserkennung folgt die Kollisionsantwort oder Kollisionsbehandlung, wodurch eine Reaktion auf die Kollision eingeleitet wird.

Kollisionserkennungsmethoden werden beispielsweise bei der Bildgenerierung von Animationsfilmen, in physikalischen Simulationen, bei Computerspielen, zur Pfadplanung in der Robotik oder bei Haptics eingesetzt. Dabei unterscheidet man Methoden zum exakten und zum approximativen Lösen von Kollisionsantworten.

Kollisionserkennung in der Starrkörpersimulation

Bei der Starrkörpersimulation (englisch Rigid Body Simulation) können verschiedene Algorithmen zur Erkennung einer Kollision verwendet werden, wobei folgende Situationen unterschiedlich behandelt werden:

  • Kollision einfacher geometrischer Körper,
  • Kollision zweier konvexer Polyeder (z. B. durch V-Clip-Algorithmus),
  • Kollision n konvexer Polyeder (z. B. durch I-Collide-Algorithmus),
  • Kollision nicht-konvexer Polyeder (z. B. RAPID),
  • Kollision komplexer geometrischer Körper.

In einzelnen Fällen lohnt es sich, nicht-konvexe Polyeder in konvexe zu zerlegen und dadurch wiederum die Algorithmen zum Finden von Kollisionen zwischen konvexen Polyedern zu verwenden. In Szenarien, in denen sich große Mengen- oder sehr komplexe geometrische Figuren befinden, muss die Kollisionserkennung in zwei Phasen unterteilt werden:

  • In der „weiten Phase“ (englisch Broad Phase) wird überprüft, welche Objekte sich überhaupt überlagern können. Dies geschieht unter Zuhilfenahme von Bounding Volumes, welche die geometrischen Objekte umschließen (z. B. Hitboxen, OBBs, AABBs oder k-DOPs). Wichtig ist, dass ein Bounding Volume eine einfache geometrische Struktur besitzt (z. B. Kugeln, Quader) und möglichst eng um die zu umhüllende komplexe geometrische Figur herumliegt. Zudem können räumliche, hierarchische Datenstrukturen (englisch BV-trees) aus den Bounding Volumes erstellt werden, um möglichst schnell in Bereiche zu gelangen, in denen Kollisionen auftreten können. Sobald zwei Bounding Volumes sich schneiden, wird Phase zwei aktiv.
  • In der „nahen Phase“ (englisch Narrow Phase) werden die komplexen Körper innerhalb der Bounding Volumes auf mögliche Schnittpunkte überprüft. Eine exakte Kollisionserkennung kann sehr hohen Rechenaufwand verursachen, weshalb bei einer großen Anzahl von Objekten auf effiziente approximative Algorithmen zurückgegriffen werden muss. Das Erkennen einer Kollision löst die Kollisionsantwort aus.

Um die benötigte Rechenleistung während der Simulation weiterhin zu reduzieren, kann das Berechnen der Bounding Volumes und das Erstellen der hierarchischen Datenstruktur in eine Vorverarbeitungsphase (englisch Preprocessing) verlegt werden.

Kollisionserkennung bei der Simulation deformierbarer Körper

Die Simulation deformierbarer Körper wird des Öfteren unterteilt in Kollision zwischen zwei disjunkten Körpern und Selbstkollision. Dabei nimmt die Selbstkollision beispielsweise bei der Simulation von Textilien oder Haaren nahezu die Hälfte der Rechenleistung in Anspruch und ist somit sehr rechenintensiv. Bei manchen deformierbaren Körpern kann jedoch keine Selbstkollision vorkommen. Fluide gelten nicht als deformierbare Objekte und müssen bei einer Kollision mit einem starren oder deformierbaren Objekt gesondert betrachtet werden.

Für deformierbare Objekte kann das Verwenden von hierarchischen Datenstrukturen sehr viel Rechenleistung in Anspruch nehmen. Darum werden oft nicht-hierarchische Datenstrukturen verwendet.

Räumliche Dimension

Computersimulation und -animation kann im 2D-Raum oder im 3D-Raum ablaufen. Die meisten Kollisionserkennungsmethoden, die für den dreidimensionalen Raum erstellt wurden, können zwar auch zur Lösung des zweidimensionalen Problems verwendet werden, was aber im Allgemeinen nicht zu einer ebenso effizienten Lösung führen muss.