Kollisionserkennung (Algorithmische Geometrie)

Kollisionserkennung (Algorithmische Geometrie)

Als Kollisionserkennung oder Kollisionsabfrage (engl. 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 (engl. 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“ (engl. 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 herum liegt. Zudem können räumliche, hierarchische Datenstrukturen (engl. 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“ (engl. 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ßer 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 (engl. 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.


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kollisionserkennung — bezeichnet die Kollisionserkennung im Bereich der algorithmischen Geometrie, siehe Kollisionserkennung (Algorithmische Geometrie); die Kollisionserkennung im Bereich der Kommunikationstechnik, siehe Carrier Sense Multiple Access/Collision… …   Deutsch Wikipedia

  • AABB — Ein dreidimensionaler Körper und die entsprechende Bounding Box (in weiß) Ein Bounding Volume ist in der algorithmischen Geometrie ein einfacher geometrischer Körper, der ein komplexes dreidimensionales Objekt oder einen komplexen Körper… …   Deutsch Wikipedia

  • Bounding Box — Ein dreidimensionaler Körper und die entsprechende Bounding Box (in weiß) Ein Bounding Volume ist in der algorithmischen Geometrie ein einfacher geometrischer Körper, der ein komplexes dreidimensionales Objekt oder einen komplexen Körper… …   Deutsch Wikipedia

  • Hüllkörper — Ein dreidimensionaler Körper und die entsprechende Bounding Box (in weiß) Ein Bounding Volume ist in der algorithmischen Geometrie ein einfacher geometrischer Körper, der ein komplexes dreidimensionales Objekt oder einen komplexen Körper… …   Deutsch Wikipedia

  • K-DOP — Ein dreidimensionaler Körper und die entsprechende Bounding Box (in weiß) Ein Bounding Volume ist in der algorithmischen Geometrie ein einfacher geometrischer Körper, der ein komplexes dreidimensionales Objekt oder einen komplexen Körper… …   Deutsch Wikipedia

  • KDOP — Ein dreidimensionaler Körper und die entsprechende Bounding Box (in weiß) Ein Bounding Volume ist in der algorithmischen Geometrie ein einfacher geometrischer Körper, der ein komplexes dreidimensionales Objekt oder einen komplexen Körper… …   Deutsch Wikipedia

  • Computer-Animation — Eine einfache computergenerierte Animation Computeranimation bezeichnet die computergestützte Erzeugung von Animationen. Sie verwendet die Mittel der Computergrafik und ergänzt sie um zusätzliche Techniken. Manchmal wird zwischen… …   Deutsch Wikipedia

  • Computeranimationsfilm — Eine einfache computergenerierte Animation Computeranimation bezeichnet die computergestützte Erzeugung von Animationen. Sie verwendet die Mittel der Computergrafik und ergänzt sie um zusätzliche Techniken. Manchmal wird zwischen… …   Deutsch Wikipedia

  • Computeranimierter Film — Eine einfache computergenerierte Animation Computeranimation bezeichnet die computergestützte Erzeugung von Animationen. Sie verwendet die Mittel der Computergrafik und ergänzt sie um zusätzliche Techniken. Manchmal wird zwischen… …   Deutsch Wikipedia

  • Render-Pipeline — Eine Computergrafik Pipeline, auch Rendering Pipeline oder einfach Grafikpipeline, ist eine Modellvorstellung in der Computergrafik, die beschreibt, welche Schritte ein Grafiksystem zum Rendern, also zur Darstellung einer 3D Szene auf einem… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”