Kollisionserkennung (Computergrafik)
aus Wikipedia, der freien Enzyklopädie
Als Kollisionserkennung oder Kollisionsabfrage wird in der Computergrafik das Erkennen des Berührens oder Durchdringens zweier oder mehrerer graphischer (starrer oder deformierbarer) Objekte verstanden.
[Bearbeiten] 3D-Computergrafik
In der 3D-Computergrafik können diese Objekte geometrische Figuren sein oder daraus zusammengesetzte Objekte, wie z. B. dreidimensionale polygonale Modelle, die auch als Drahtgittermodelle visualisiert werden können. Bei der Kollisionserkennung zwischen impliziten Oberflächen geht es darum, Schnittpunkte/-kurven zwischen zwei Oberflächen zu bestimmen, die nur indirekt, beispielsweise durch eine Punktwolke (eine Menge von Punkten im Raum), gegeben sind.
In der ersten Phase der Kollisionserkennung wird versucht, alle Paare von Objekten auszuschließen, die nicht kollidieren können. Räumliche und zeitliche Kohärenzen können genutzt werden, um diese Erkennung zu beschleunigen.
In der zweiten Phase wird unter Zuhilfenahme sogenannter Bounding Volumes (beispielhaft ist hier die Hitbox) grundlegend festgestellt, ob eine Kollision zweier Objekte möglich ist.
In der dritten Phase werden die Kollisionen zwischen in Frage kommenden Objektpaaren exakt bestimmt. Räumliche, hierarchische Datenstrukturen, wie beispielsweise AABB-trees, OBB-trees oder k-DOP-trees werden genutzt, um möglichst schnell in Bereiche zu leiten, in denen Kollisionen auftreten. Auf den entsprechenden (kleineren) Teilmengen von geometrischen Figuren kann ein exakter Schnitttest mit einer der nachfolgenden Methoden durchgeführt werden:
- Schnittpunkt(e) von Strahl und Kugel
- Schnittpunkt von Strahl und Ebene
- Schnittpunkt von Strahl und Dreieck
- Schnittlinie zweier Ebenen
- Schnittlinie zweier Dreiecke
Für deformierbare Objekte und die Erkennung von Selbstkollisionen scheinen bisher nicht-hierarchische Datenstrukturen vielversprechender zu sein.
Da die Kollisionserkennung in vielen VR-Anwendungen einen zentralen Flaschenhals darstellt, gibt es auch approximative Algorithmen (ähnlich wie bei der Kollisionsbehandlung) zur zeitkritischen Kollisionserkennung, um eine physikalisch plausible, aber nicht absolut physikalisch korrekte Erkennung durchzuführen. Am Ende der zur Verfügung stehenden Zeit soll eine möglichst gute und genaue Aussage zur Kollision gemacht werden, die aber in wenigen Fällen auch falsch sein darf. Neben VR-Simulationen sind vor allem 3D-Spiele ein mögliches Einsatzgebiet für diese Art der Kollisionserkennung.
[Bearbeiten] 2D-Computergrafik
In der 2D-Computergrafik bezeichnet Kollisionserkennung die Fähigkeit eines Programms, zu erkennen, ob sich grafische Objekte (Sprites) treffen bzw. berühren. Dies geschieht meist mit hilfe einer Bounding Box, ein minimaler Kasten, der das zu prüfende Objekt beinhaltet. Diese Technik wird gewählt, da sie einfacher ist als das detaillierte Objekt auf Überschneidung bzw. Durchdringung zu prüfen. Die Kollisionsabfrage ist grundsätzlicher Bestandteil von Spielen fast aller Genres mit grafischer Darstellung.
