Home | Lehre | Videos | Texte | Vorträge | Software | Person | Impressum, Datenschutzerklärung | Blog
Kollisionserkennung, Physik
-
noch Bump-Mapping vom vergangenen Mal
-
Grundideen von Kollisionserkennung und Physiksimulation
-
Einsatz der Kollisionserkennung: in Spielen nicht durch Wände laufen,
Objekte prallen voneinander ab, Objekte gleiten aneinander (z.B. beim Modellieren),
Kleidung liegt auf dem Körper und wird vom Körper bewegt, Haare
fallen nicht durch den Kopf
-
Die Erkennung (Collision Detection) allein genügt also nicht, es muss
auch eine Reaktion (Collision Response) auf die Kollision passieren.
-
Reaktion oft nach den Gesetzen der Physik: Rigid Body Dynamics für
Kegel, Dose usw., Soft Body Dynamics für Hängebauch, Knetgummi,
Tischdecke usw.
-
physikalische Gesetze auch für den kollisionsfreien Teil der Bewegung
einbauen, z.B. Beschleunigung durch Schwerkraft
-
Demo für Rigid und Soft Body Dynamics mit Cinema 4D und Maya. Soft
Body Dynamics über Tausende künstlicher Federn (springs, nicht
feathers), rechenaufwendig, ungenau, instabil, aber das übliche Verfahren
-
Rechenaufwand der Kollisionserkennung
-
n Objekte können auf n(n-1)/2 Arten paarweise kollidieren, also quadratisch
mit Objektanzahl wachsender Rechenaufwand. Ebenfalls explodiert der Rechenaufwand
mit der Zahl der Polygone pro Objekt. Bei verformbaren Körpern (Taschentuch,
ggf. Autokühler) müssen obendrein noch Selbstkollisionen berücksichtigt
werden.
-
Wie den Rechenaufwand drücken?
-
räumliche Kohärenz benutzen: Objekte, die sich fern sich, können
sich nicht berühren
-
zeitliche Kohärenz benutzen: Objekte, die sich zu einem bestimmten
Zeitpunkt fern sind, sind das etwas später immer noch, je nach Geschwindigkeit
-
räumliche Koherenz meist mit verschiedenen Detailstufen ausgenutzt:
Ermittele in einer Broad Phase durch grobe Rechnung, ob zwei Objekte sich
überhaupt berühren können, sehe dann (und nur dann) in einer
Narrow Phase genauer nach.
-
Broad Phase typischerweise mit Bounding Boxes (an den Weltachsen ausgerichtet:
AABB, axis-aligned bounding box; an den Objektachsen ausgerichtet: OBB,
oriented bounding box) oder mit Kugeln (Bounding Spheres) oder mit BSP-Trees
oder Quadtrees/Octrees
-
Man kann auch mehrere Hierarchiestufen in der Broad Phase hintereinanderschalten:
Ragt die Türklinke in die Bounding Box der Hand? Falls ja, ragt sie
auch in die des Zeigefingers? Falls ja, ragt sie auch in die der Kuppe
des Zeigefingers? usw.
-
simple Tests zur Kollisionserkennung
-
Zwei Kugeln kollidieren, wenn die Entfernung ihrer Mittelpunkte voneinander
kleiner ist als die Summe ihrer Radien.
-
Ein Punkt mit Ortsvektor p
liegt dann und nur dann in einem konvexen Polyeder, wenn für alle
Flächen des Polyeders gilt: Das Skalarprodukt v*n
ist größer als p*n,
wobei n der Normalenvektor
der jeweiligen Fläche und v
der Orstvektor eines beliebigen Vertex der Fläche ist.
-
simple physikalische Antwort für reibungsfreie elastische Rigid-Body-Kollisionen
einer Kugel mit einer Kugel (Radius und Masse ggf. verschieden)
-
Eigendrehung (in 3D sehr komplex!) hier egal, weil Stoß bei Kugeln
immer zentral und weil mangels Reibung kein tangentiales Mitreißen
der Oberfläche
-
Seien mA und mB die Massen der Kugeln, vA1, vB1
ihre Geschwindigkeitsvektoren vor der Kollision, vA2, vB2
ihre Geschwindigkeitsvektoren nachher.
-
Die Geschwindigkeiten können sich mangels Reibung nur in Richtung
der "Kontaktnormalen" n ändern,
nicht quer dazu.
-
Impulserhaltung [engl.: momentum conservation]: Die Summe aller Impulse
= Masse*Geschwindigkeitsvektor über alle Körper muss vor und
nach dem Stoß gleich sein.
-
Folge: Die beiden Kugeln tauschen einen Impuls aus, der in Richtung der
Kontaktnormalen zeigt, sage pn.
Das heißt:
mAvA1 +
pn = mA vA2
mBvB1 -
pn = mB vB2
-
Energieerhaltung: Die Summe 1/2 * Masse * Geschwindigkeitsquadrat über
alle Körper muss vorher und nachher gleich sein (zumindest beim elastischen
Stoß; andernfalls wird Energie für dauerhafte Verformung und
Erwärmung abgezweigt).
-
Löse die obigen Gleichungen für den Impuls nach den Endgeschwindigkeiten
auf, setze das in die Gleichung für die Energieerhaltung ein; das
ergibt eine quadratische Gleichung. Lösungen: p = 0 (d.h. die Kugeln
durchdringen einander wie Geister, was zumindest für Billardkugeln
ungewöhnlich wäre) oder p = 2(vB1
- vA1)*n/(1/mA
+ 1/mB).
-
Aus den beiden Gleichungen für den Impuls kann man nun die Änderung
der Geschwindigkeiten beim Stoß bestimmen.
-
Stoß einer Kugel mit einem massiven Hindernis (z.B. Bande des Billardtisches):
Mache mB unendlich, d.h. 1/mB wird null.
-
Simples Verfahren für zweidimensionales Billard (elastisch, reibungslos,
ohne Drehung) [engl.: billiard]
-
Setze dt als einen kleinen Zeitschritt fest.
-
Lege Anfangspositionen und Anfangsgeschwindigkeitsvektoren für alle
Kugeln fest. Die Kugeln dürfen nicht einander und auch nicht die Bande
berühren.
-
In jedem Zeitschritt tue:
-
Bewege jede Kugel um dt mal ihren Geschwindigkeitsvektor
-
Für jede Kugel:
-
Teste auf Kollision mit Bande.
-
Ändere bei Kollision den Geschwindigkeitvektor.
-
Für alle Paare von Kugeln:
-
Teste auf Kollision.
-
Ändere bei Kollision die Geschwindigkeitvektoren.
-
Komplikationen
-
Schnelle Kugeln fliegen durch einander und durch die Bande, weil die Kollision
"verpasst" wird. Also sicher stellen, dass Geschwindigkeit nicht zu hoch
oder Zeitschritt dynamisch anpassen oder (perfekt, aber schwierig) die
gesamte Flugbahn zwischen den Zeitschritten testen.
-
Bei Kollision überlappen sich die Kugeln bereits. Eigentlich muss
man den Zeitpunkt der exakten Berührung finden. Anderfalls stimmt
die Berechnung nicht ganz und (schlimmer noch) kann es passieren, dass
die Kugeln sich im nächsten Zeitschritt immer noch überlappen.
Da wird die Rechnung dann mit den geänderten Geschwindigkeitsvektoren
durchgeführt, was Unsinn liefert. Abhilfe z.B.: Kugeln nach Kollision
entlang der neuen Flugrichtungen auseinander legen.
-
Gleichzeitige Kollisionen von drei und mehr Körpern werden nicht unbedingt
korrekt behandelt.