Kollisionen und Eigenkollisionen
Nicht nur bei Spielen ist die "Kollisionsabfrage" von Bedeutung. Dort handelt es sich noch um sehr einfache Berührungen meist fester Oberflächen. Und die Reaktionen auf diese "Kollisionen" haben auch nur wenig mit der Realität zu tun.
Die Simulation und realistische Animation von Stoffen, Tüchern und Kleidung verlangt nach komplizierteren Ansätzen, Berührungen zu erkennen und darauf zu reagieren.
Einführung
Nun ist die Realität das eigentliche, bisher unerreichte Ziel der Animation und Simulation mit dem Computer. Um diesem Ziel näher zu kommen, benötigt man Ansätze von mathematischer und physikalischer Natur. In der Vergangenheit, d. h. seit Ende der 80er Jahre, wurden mehrere Ansätze entwickelt, die Oberfläche geeignet darzustellen und "Kollisionen" zu erkennen.
Für das weitere Verständnis sind einige Grundlagen sehr wichtig.
Was sind "Kollisionen"?
"Kollisionen" sind Berührungen von Oberflächen, die in der Regel bestimmte Reaktionen zur Folge haben. Speziell bei Stoffen, Tüchern und Kleidung werden zwei wichtige Arten von Berührungen unterschieden:
- Kollisionen
Kollisionen sind allgemeine Berührungen verschiedener Oberflächen, z. B. zwischen Kleidung und Körper.
- Eigenkollisionen
Berührt sich eine verformbare Oberfläche selbst, z. B. bei Falten, Knittern, spricht man von Eigenkollisionen.
Nun ist festgelegt, von was in diesem Kapitel überhaupt gesprochen wird. Das eigentliche Problem ist aber, wie können diese Kollisionen erkannt werden?
Wie arbeiten die Algorithmen zur Kollisionserkennung?
Bounding Sphere und Bounding Box
Im Verlauf der Entwicklung hat sich eine gewisse Grundanschauung in den Berechnungen der virtuellen Welt durchgesetzt. Bei einer Animation ändern sich die physikalischen Eigenschaften der einzelnen Objekte. Durch diese Veränderungen können sich die Objekte gegenseitig beeinflussen, also kollidieren.
Hier kommen zwei neue Begriffe zum Einsatz:
- Bounding Sphere
Um die Betrachtung und Kontrolle der Objekte zu vereinfachen, werden diese in Kugeln eingeschlossen - sogenannte Bounding Spheres. Schneiden oder berühren sich diese Kugeln nach einer Positionsänderung, wird der Bereich der Kollision durch eine Box umfaßt.
- Bounding Box
Diese Box nennt man Bounding Box. Sie wird dann durch einen rekursiven Algorithmus suksessive in weitere Unterboxen unterteilt. Dabei wird für jedes Objekt überprüft, in welchen Unterboxen es enthalten ist. Durch die weitere, rekursive Aufteilungen wird bestimmt, ob es sich um eine Kollision handelt, und falls ja, wo sie ist.
Mit anderen Worten, die Bounding Spheres sind eine Art Frühwarnsystem für Kollisionen, die durch die Bounding Box genau bestimmt und lokalisiert werden können.
Einführung in das Hierarchie-Prinzip
Oberflächen bestehen bekanntermaßen aus vielen kleinen Polygonen. Je genauer die Oberfläche dargestellt werden soll, desto mehr Polygone werden dafür benötigt.
Für die nötigen Berechnungen einer Animation werden benachbarte Polygone zu neuen Teilflächen, und wiederum diese Teilflächen zu größeren Teilflächen zusammengefaßt, usw. Durch diese Vorgehensweise erreicht man eine hierarchische Vereinfachung der Darstellung der Oberfläche.
In Abbildung 10-6 läßt sich erkennen, daß die Teilflächen von Stufe zu Stufe immer größer werden. Diese Hierarchie hat den Vorteil, daß nun nicht mehr Kollisionen zwischen allen Polygonen abgefragt werden müssen. Berechnungen sind nur zwischen den großen Teilflächen und innerhalb dieser Teilflächen notwendig.
Fazit: die Funktionen zur Erkennung von Kollisionen muß nicht so oft aufgerufen werden und die Rechenzeit wird verkürzt.
Geometrischer Ansatz zur Erkennung von Eigenkollisionen
Das Ziel, die Rechenzeit zu verkürzen, wollen wir im Folgenden noch weiter verfolgen. Die Erfahrung zeigt uns, daß einfache Überlegungen ausreichen, einfache Probleme zu lösen. Nun ist es einem Computer nicht möglich, zwischen einfachen und komplizierten Problemen zu unterscheiden. Man benötigt eine Vorbedingung, die auf einfache Weise für große Bereiche der Oberfläche eine komplizierte Kollisionserkennung ausschließt.
Eigenkollision und Krümmung
Diese beiden Bilder zeigen, daß bei weich und gleichmäßig geformten Oberflächen – Stoffe, Tücher und Kleidung – nur wenig Möglichkeiten einer Eigenkollision existieren.
Eigentlich entstehen Kollisionen nur bei sehr großen Krümmungen oder, wenn durch Knicke verursachte Überlagerungen entstehen.
Der Pseudocode dieser geometrischen Eigenschaft würde lauten:
WENN ein Vektor V existiert, dessen Skalarprodukt mit den Normalvektoren Ni der Oberfläche S stets größer als 0 ist - d. h. die Oberfläche nie parallel zum Vektor V ist (V × N > 0, für alle Punkte auf S)
UND die Projektion der Oberfläche S auf eine Fläche E, die senkrecht zum Vektor V ist, keine Schnitte mit sich selbst besitzt,
DANN existieren keine Eigenkollisionen der Oberfläche S.
Durch diese einfache Prüfung können für große Bereiche einer Oberfläche Eigenkollisionen ausgeschlossen werden. Aber auch auf mögliche Kollisionen benachbarter Bereiche unterschiedlicher Oberflächen kann dieses Kriterium angewendet werden. Die geometrischen Bedingungen sind dieselben, nur daß es zwei Oberflächen S1 und S2 gibt. Es bleibt aber bei nur einem Vektor V und einer Fläche E.
Weitere Betrachtungen der Oberfläche
Nun ist der Einsatz komplexer Algorithmen zur Erkennung von Kollisionen auf bestimmte Oberflächenbereiche begrenzt. Aber es müssen noch weitere Probleme einer Realisierung erfaßt werden.
Die Erfassung und Bewertung benachbarter Teilflächen:
Durch eine Brute Force Erfassung kommt man nur zu dem Schluß, daß jeder Teil einer Oberfläche an andere Teile angrenzt. Zeitverschwendung! Deshalb werden nur die Spitzen der Polygone erfaßt, die eine Teilfläche nach außen abgrenzen - wir erinnern uns an das Hierarchie-Prinzip.
Grenzen zwei Teilflächen aneinander, haben sie mindestens eine dieser Spitzen gemeinsam.
Die Krümmung einer unstetigen Oberfläche:
Wird eine Kurve durch kleine gerade Teilstücke dargestellt, spricht man in der Mathematik von Diskretisierung bzw. Unstetigkeit. Die Darstellung von Oberflächen mit Polygonen ist nichts anderes.
Daher müssen für die Beschreibung der Ausrichtung, und damit auch der Krümmung einer unstetigen Oberfläche die Normalvektoren jedes einzelnen Polygons betrachtet werden.
Zur Vereinfachung verteilen wir die Richtungen im Raum auf 14 Einheitsvektoren (Vi). Diese zeigen vom Mittelpunkt eines Würfels auf die Mittelpunkte der sechs Flächen und auf die acht Eckpunkte.
Für jedes Polygon werden die Vektoren Vi gespeichert, die nicht parallel zum Polygon sind (Vi × Np > 0). Und wieder das Hierarchieprinzip – in den oberen Hierarchieebenen läßt sich die Beschreibung von Ausrichtung und Krümmung der Oberfläche auf einen verbleibenden Vektor V beschränken.
Konsistenz von Ausrichtung und Verformung
Während Animationen muß auf erkannte Kollisionen dementsprechend reagiert werden. Aber durch die Reaktion auf Kollisionen dürfen sich Oberflächen nicht plötzlich doch schneiden. Um dies zu vermeiden, muß auf Kontakte zwischen Oberflächen nach physikalischen und mechanischen Regeln geantwortet werden.
Die bisherigen Ansätze prüften den Abstand der Bereiche von Oberflächen zueinander. Aber dabei wird angenommen, daß es sich stets um die korrekten Seiten der Flächen handelt.
Mit einigen Ausnahmen – geschlossene Oberflächen wie Ball und Haut des Körpers – sind Innen- und Außenseite einer Oberfläche nie automatisch definiert.
Dies wirft die Frage auf, auf welcher Seite einer Fläche, Innen- oder Außenseite, die andere Fläche anzunehmen bzw. was als Innen- oder Außenseite der jeweiligen Fläche definiert ist.
Erfassung der Kollision
Ist eine Kollision im Verlauf einer Animation einmal erkannt, wird sie erfaßt und abhängig von der Position der betroffenen Objekte aktualisiert, ebenso wie die Ausrichtung von Innen-/Außenseiten der Oberflächen.
Auch wenn die Kollision im Augenblick nicht auftritt, so bleibt sie doch für gewisse Zeit erfaßt.
Prüfung und Wiederherstellung der Konsistenz
Zwar gewährleistet die Korrektheit der Ansätze und deren Realisierung, daß sich die Oberflächen nicht schneiden. Aber man sollte trotzdem in der Lage sein, Inkonsistenzen zu korrigieren.
Dafür werden erfaßte Kollisionen bzgl. der betroffenen Bereiche der Oberfläche gruppiert. Daraus wird die statistisch häufigste Ausrichtung der Fläche berechnet. Ensteht tatsächlich einmal eine Inkonsistenz, dann wird die wahrscheinlichste Ausrichtung der Oberfläche gewählt.
Abbildung 10-11 zeigt eine schrittweise Korrektur von Inkonsistenzen, d. h. sich schneidende Oberflächen werden step-by-step aufeinandergelegt. Somit gibt es nur noch Berührungen und keine Schnittpunkte mehr.
Vorteile in der Anwendung
Die besprochenen Ansätze dienen zum Zweck der Optimierung der herkömmlichen Algorithmen. Die Anwendung auf eine Kugeloberfläche zeigt deutlich die Steigerung der Effizienz, da bei einer Kugel keine Eigenkollisionen vorkommen können.
Da in der Hierarchie früh erkannt werden kann, daß keine Kollisionen vorkommen, ist der geometrische Ansatz im Vergleich zu herkömmlichen hiercharchischen Algorithmen deutlich schneller.
Aber diese Algorithmen sollen vor allen Dingen für kollidierende Oberflächen angewendet werden. Aber auch die Anwendung auf eine Oberfläche, die sich durch starke Krümmung berührt, zeigt eine deutliche Geschwindigkeitssteigerung.
Wie die Tabellen zeigen, ist die Geschwindigkeit herkömmlicher Algorithmen von der gesamten Zahl der Polygone abhängig. Die Geschwindigkeit unter Berücksichtigung der geometrischen Eigenschaften hängt dagegen fast nur noch von der Zahl der kollidierende Polygone ab. Das Bild zeigt den Kollisionsbereich hell markiert.
Für die Anwendung im Realfall ist nicht nur die Erkennung der Kollisionen zwischen Kleidung und Körper leicht verbessert. Die Erkennung von Eigenkollisionen war bisher der (Rechen)zeitaufwendigste Teil. Durch die Verbesserungen wird er mit Abstand zum kleinsten Teil.
Abbildung 10-14 zeigt die Bereiche heller, die für eine Kollision in Frage kommen. Der linke Teil zeigt alle Bereiche der Oberflächen hell, d. h. eine Erkennung von Kollisionen muß überall in Betracht gezogen werden. Der mittlere Teil zeigt eine Einschränkung möglicher Körper-Kleidung-Kollisionen auf wenige Bereiche der Oberflächen. Rechts sehen wir, daß für Eigenkollisionen der Kleidung die wenigen Bereiche kaum erkennbar zu markieren sind.
Diese Ansätze sind kein Ersatz für die mathematischen und physikalischen Algorithmen zur Erkennung von und Reaktion auf Kollisionen. Sie schließen nur Kollisionen für große Bereiche der Oberflächen aus und sind daher eine wichtige Ergänzung.