Embed Size (px)
Citation preview
1
KOLLISIONSERKENNUNG
Simulation und 3D-ProggrammierungDozent Prof. Dr. M. ThallerReferentin Nadya Steinert
2
Rückblick: Umgebungskugel und Umgebungsquader
Umgebungskugel ist durch ihren Radius definiert, Mittelpunkt ist identisch mit dem des Modells.
Umgebungsquader ist durch den minimalen und den maximalen Vektor definiert.
Minimaler Vektor ist die linke hintere untere Ecke des Quaders.
Maximaler Vektor ist die rechte obere vordere Ecke. Umgebungskugel und Umgebungsquader schließen
ein Modell vollständig ein.
3
Das Prinzip der Kollisionserkennung
Warum wird es mit Kugeln und Quadern gerechnet?
Damit ist es leichter zu rechnen als mit den Dreiecken des Modells.
Die Modelle liegen innerhalb der Kugeln und Quadern, also wenn z.B. eine Linie die Hülle trifft, dann wird automatisch auch das Modell getroffen.
So werden die komplizierten Berechnungen mit den Dreiecken gespart, wenn das nicht der Fall ist.
4
Kugel - Kugel
Um die Kollision zwischen zwei Objekte zu bestimmen , wird es zuerst geprüft, ob sich deren Umgebungskugeln schneiden.
Bei Kugelkollision kann genauso vorgegangen werden, wie bei der Kollision zweier Kreise.
Es gibt vier Möglichkeiten:
5
Kugel - Kugel
A) Keine Kollision; d > r1 + r2
B) Berührung; d = r1 + r2
C) Schnitt; d < r1 + r2
D) Einschließung; d <= r1 - r2
6
Kugel - Kugel
Wenn die Distanz d zwischen den beiden Kreisen kleiner oder gleich der summe der Radien ist, kollidieren die Kreise an mindestens einer Stelle.
Bei dreidimensionalen Kugeln gilt das gleiche, nur bei der Berechnung von d geht es um Vektorlengenberechnung.
Für die Funktion tbSphereHitsSphere brauchen wir einen Vektor(Mittelpunkt) und eine Flieskommazahl(Radius).
7
Kugel - Kugel
Die Funktion
tbSphereHitsSphere
8
Linie - Kugel
Wenn ein Torpedo, als ein Punkt betrachtet wird, und es soll eine Kugel treffen, können wir die alte Position des Torpedos mit der neuen verbinden. So haben wir Linie und Kugel. Wir brauchen Gleichungen für die Kugel und für die Linie.
9
Die Kugelgleichung
(x – xM)² + (y – yM)² + (z – zM)² = r² Im dreidimensionalen Raum werden die Punkte durch Vektoren ersetzt.Wenn die Entfernung des Punktes zum Mittelpunk gleich dem Radius ist, dann liegt der Punkt auf der Kugel.Zum ersten mal wird ein Vektor quadriert.Der Vektor wird mit Hilfe des Punktproduktes mit sich selbst multipliziert.So hat man das Quadrat der Vektorlänge.
10
Die Geradengleichung
Die gerade muss mit Hilfe von Vektoren dargestellt werden.
Man braucht einen beliebigen Punkt, der dazu führende Vektor heißt Stützvektor p, einen Richtungsvektor u und einen Parameter s :
x = p + s . u Durch das s – Parameter bewegt man sich vom Stützvektor entlang des Richtungsvektor über die Gerade.s kann positiv oder negativ sein, was die Richtung andeutet.
11
Geraden- und Kugelgleichung kombinieren
s eingesetzt in die Geradengleichung soll einen Punkt liefern, der die Kugelgleichung erfüllt.
Die zwei Gleichungen: g : x = p + s . u k : (x – m)² = r² g wird in k eingesetzt : -u . ( p – m) ± √(u . (p –m))² - u² . ((p-m)² -r²)s1,2 = u²
12
Geraden- und Kugelgleichung kombinieren
Wichtig hier ist die Diskriminante: Diskriminante > 0 : zwei
Schnittpunkte(den kleineren Wert benutzen, näher zum Startpunkt)
Diskriminante = 0 : ein Schnittpunkt Diskriminante < 0 :kein SchnittpunktDas wird dann in die Funktion tbLineHitsSphere gepackt.
13
Linie - Dreieck
Nächster Schritt, falls der vorherige positiv ausgefallen ist : Linie – Dreieck.
Zuerst wird geprüft ob die Linie die Ebene des Dreiecks schneidet.
Vorgehensweise wie bei der Kugel : s eingesetzt in die Geradengleichung, liefert einen Punkt der auch die Ebenengleichung erfüllt
g : x = p + s . u E : n . x + d = 0
14
Linie - Dreieck
g in E einsetzen:
s = - n . p + d n . u Es wird getestet ob der Nenner gleich Null ist und s muss im Intervall [0;1] liegen. Wenn Nenner gleich Null – Linie verläuft parallel zur Ebene, in diesem Fall wird Startpunkt der Linie in die Ebenengleichung eingesetzt.
15
Linie - Dreieck
Daraus wird die Funktion tbLineHitsPlane implementiert.
Schnellere Methode findet den Punkt nicht, sondern ob es einen gibt oder nicht :
Start- und Endpunkt der Linie werden in die Ebenengleichung eingesetzt. Wenn sie gleiche Vorzeichen haben, liegen die auf der gleichen Seite und schneiden die Ebene nicht ;wenn unterschiedliche Vorzeichen – Ebene wird geschnitten; wenn Null – Linie liegt auf der Ebene.
16
Liegt der Schnittpunkt im Dreieck?
Die Fläche eines Dreiecks ist durch drei Ebenen begrenzt, die entlang der Kanten erstrecken und einen Normalenvektor senkrecht zu den Kanten haben.
Die Ebenen werden generiert und der P unkt wird in die Ebenengleichungen eingesetzt.
Wenn ein Wert kleiner null herauskommt, liegt der Punkt nicht auf der Ebenen ; wenn der Wert größer oder gleich null ist liegt der Punkt innerhalb des Dreiecks .
17
Ein anderer Einsatz
Der Schnittpunkt zwischen Linie und Ebene wird berechnet.
Ein neues Koordinatensystem mit Ursprung eines der Punkte des Dreiecks wird gebildet, Achsen sind nicht mehr rechtwinklig.
Position des Schnittpunkts muss ins neue Koordinatensystem umgerechnet werden(baryzentrischen Koordinaten), was sofort die Frage beantwortet:
18
Ein anderer Ainsatz
x-Koordinate < 0: Punkt nicht im Dreieck y- Koordinate < 0: Punkt nicht im Dreieck Summe der x- und y-koordinate > 1:
Punkt nicht im Dreieck
Daraus wird die zweite Funktion für Linie und Dreieck implementiert: tbLineHitsTriangle2
19
Dreieck - Dreieck
Ebene von Dreieck 2 wird berechnet Dreieck 1 wird Punkt für Punkt
durchgegangen; wenn alle Punkte auf der gleichen Seite – Dreiecke schneiden sich nicht
Jetzt das Gleiche, nur umgekehrt, dabei merkt man sich welche Punkte der Dreiecke alleine auf ihrer Ebenenseite liegen
Dreiecke schneiden sich normalerweise in einer Linie – die Schnittlinie L
20
Dreieck - Dreieck
Dreieck 1 schneidet Ebene 2 in Linie L1 und umgekehrt.
Zuerst müssen beide Schnittlinien L1 und L2 gefunden werden; der Bereich, wo sie sich überlappen ist die gesuchte L
L1 und L2 bestehen von zwei Punkten: einen Start- und einen Endpunkt
Das sind die Schnittpunkte der Dreieckvektoren mit der anderen Ebene
21
Dreieck - Dreieck
Es müssen die s-Werte für L1 und L2 berechnet werden
Die Werte für beide Schnittlinien werden sortiert, um zu wissen welcher das Minimum und welcher das Maximum ist
Minimum und Maximum bilden jeweils ein Intervall
Die Intervallüberlapung beider Linien wird gesucht; es gibt sechs Überlapugszustände
22
Dreieck - Dreieck
Die Funktion tbTriangleHitsTriangle wird implementiert
23
Linie - Quader
Unterschied zu Kugeln: - Kugeln sind mathematisch leichter auszudrücken - Eine Drehung verändert ihre Form nicht Berechnung eines Quaders - es werden nur die linke untere vordere Ecke und die rechte obere hintere ecke benötigt - wir arbeiten zuerst mit achsenausgerichteten Umgebungsquadern
24
Linie - Quader
Ein Quader ist ein von sechs Ebenen abgegrenzter geschlossener Raum
Ein Punkt der im Quader liegt, liegt auf der Hinterseite jeder der Ebenen
Es gibt normalerweise zwei Punkte, die den Quader schneiden, wir wählen denjenigen, mit der kürzesten Distanz zum Startpunkt des Strahls
25
Linie - Quader
Bei frei drehbaren Quadern: - müssen nur die Ebenen mit der Transformationsmatrix des Objektes transformiert werden - die Ebenen werden mit Hilfe der Eckpunkte des Quaders berechnet ( für eine Ebene werden drei Punkte benötigt), wenn diese vor Erstellung der Ebene transformiert werden ist das Problem gelöst - für achsenausgerichteten Quadern wird einfach die Identitätsmatrix eingegeben
26
Punkt im Quader
Beim achsenausgerichteten Quader: -wenn die Koordinaten des Punkts auf allen drei Achsen zwischen dem Minimum und Maximum des Quaders auf dieser Achse liegen, dann ist der Punkt drin Beim drehbaren Quader: - setzt man den Punkt in die Gleichungen der sechs Ebenen ein - da alle Ebenen nach außen zeigen, sobald ein positives Ergebnis vorliegt, liegt der Punkt nicht im Quader
27
Punkt im Quader
Die Funktion tbPointHitsBox wird dieses Prinzip angewendet
Bei der Funktion tbPointHitsBox2 : - werden keine Ebenen berechnet - anstatt den Quader zu transformieren, wird der Punkt mit Hilfe der invertierten Transformationsmatrix transformiert - der Punkt erhält Quaderrelevante Koordinaten(hier gilt das Prinzip des achsenausgerichteten Quaders)
28
Linie - Quader
Implementieren der Funktion tbLineHitsBox ;folgende Parameter werden gebraucht:
- Start- und Endpunkt der Linie - Die Eckvektoren des Umgebungsquader - Die Transformationsmatrix - Einen tbVector-3-Zeiger, welcher mit den Schnittpunkten gefüllt wird Wir brauchen die Funktion
tbLineHitsPlaneS,die mit dem Linienabschnitt s rechnet und einen float- Wert zurückgibt
29
Quader - Quader
Zwei Quader Kollidieren genau dann, wenn sich mindestens ein Punkt des einen Quaders innerhalb des anderen befindet; der Quader wird Punkt für Punkt in eine bestimmte Schrittweite durchlaufen(je kleiner die Schrittweite , desto genauer die Kollisionserkennung)
Die Funktion tbBoxHitsBox wird implementiert
30
Wie wird es mit Modellen umgegangen?
1. Optimierung : Bereitstellen der Vektoren und Indizes:
- bei Kollision müssen die einzelnen Vertizes und Indizes schnell griff bereit sein - direkt nach laden des Modells alle Positionsvektoren und Indizes aus den Buffern extrahieren und speichern( für schnelleren Zugriff)
31
Wie wird es mit Modellen umgegangen?
2. Optimierung: Vorberechnung der Dreiecksebenen
- wir berechnen die Ebene des Dreiecks und die drei Seitlichen Ebenen und speichern sie
- dann muss der Schnittpunkt später nur in drei Ebenengleichungen eingesetzt werden
- mit der ersten Ebene des Dreiecks erhalten wir auch noch den Normalenvektor
32
Wie wird es mit Modellen umgegangen?
3. Optimierung: Octrees- für jedes Modell ein Octree erstellen- Octree ist eine baumartige Struktur,
bei der ein Modell in acht Stücke aufgeteilt wird und jedes Stück wiederum aufgeteilt wird bis eine bestimmte Tiefe erreicht wird
- für jedes Teil wird ein umgebender Quader angefertigt
- Die Knoten beinhaltet nur Zeiger auf ihre Unterknoten; nur der Endknoten beinhaltet die eigentlichen Dreiecken
33
Wie wird es mit Modellen umgegangen?
Bäume spielen auch beim Rendern eine große Rolle; nur die sichtbaren Knoten werden gerendert und es werden keine unnötige Brechnungen für die unsichtbaren durchgeführt
34
Vorberechnungen
Zuerst werden die Positionsvektoren jedes Vertex und alle Indizes in der tbModel-Klasse bereitgestellt; das sind die Extradaten
Die Init-Methoden von tbModel erhalten noch zwei weitere BOOL-Parameter
- der eine bestimmt, ob Extradaten generiert werden sollen (bGenerateExtraData)
- der zweite sagt ob nur Extradaten erwünscht sind ; in dem Fall werden dann Vertex-Buffer, Index-Buffer, Effekte, Lichter nach dem Laden gelöscht(bExtraDataOnly)
35
Vorberechnungen
Kopieren der Positionsvektoren - Positionsvektoren und Indizes werden in
tbvector3 gesteckt und es wird genügend Speicherplatz reserviert
- Vertizes bestehen aus mehreren Parametern, wir brauchen nur den Positionsvektor, der immer an erster Stelle ist ; die Größe des Vertex ist auch bekannt, also ist das Herauskopieren kein Problem
-Ein BYTE-Zeiger wird erstellt, der zuerst auf den Anfang des Vertx-Buffer-Daten zeigt, der erste Pos.vektor wird herauskopiert und der Zeiger wird um die Vertexgröße erhöht, um am Anfang des nächsten Vertex zu kommen
36
Vorberechnungen
Kopieren der Indizes – es wird genauso wie bei den Vertizes vorgegangen
Berechnung der vier Ebenen jedes Dreiecks- als erstes wird Speicherplatz reserviert;
Der Zeiger auf die Liste heißt tbPlane* - als nächstes werden die Ebenen berechnet;
dazu wird jedes Dreieck durchgegangen und die Positionsvektoren seiner drei Vertizes herausgefunden
-Dann werden die Ebenen mit den Funktionen tbPlaneFromPoints und tbPlaneFromPointsNormal ausgerechnet
37
Vorberechnungen
Der Octree –Struktur- eine BOOL-Variable, die bestimmt ob ein
Knoten Endknoten ist oder nicht- für normale Knoten: 8 Zeiger auf die
untergeordneten Knoten- für Endknoten: die Anzahl der Dreiecke und
eine Liste mit den Dreiecken dieses Knotens-für alle Knoten speichern wir den Quader, der
diesen knoten und alle untergeordneten Knoten umgibt ; benötigt werden maximaler und minimaler Vektor ; die sechs Ebenen des Quaders werden berechnet und gespeichert
38
Vorberechnungen
Einrichten des Wurzelknotens- der Wurzelknoten ist der Zeiger
m_pRootNode und er enthält 8 Zeiger auf die Unterknoten
- dieser Knoten wird in UpdateExtraData initialisiert, zuerst ist er ein Endknoten und bIsLeaf wird auf true gesetzt
- die darin enthaltenen Dreiecke ensprechen der Anzahl der im Modell enthaltenen
-für die Bounding-box werden die Werte kopiert, die in tbModel gespeichert sind
39
Vorberechnungen
Rekursives Aufteilen eines Knotens- die rekursive Funktion(tbModel::SplitNode)
teilt einen Knoten in 8 Unterknoten auf und ruft sich selbst wieder auf bis eine maximale Unterteilungstiefe erreicht ist, oder ein Knoten nur noch wenige Dreiecke hat
- der rekursiven Funktion wird der zu unterteilende Knoten übergeben(tbmodelOctreeNode) und ein int-Wert mit der maximalen Unterteilungstiefe; beim Wiederaufruf wird dieser wert um eins verringert
40
Vorberechnungen
Schritt 1: Festlegen der Bounding-Box jedes neuen Knotens
- die Methode SplitNode geht in einer for-Schleife alle 8 Knoten durch und reserviert Platz; dann wird die Bounding-Box jedes neuen Unterknotens festgelegt ; später wird bestimmt , welche Dreiecke zu diesem Knoten gehören und welche nicht
- der Knoten wird genau in der Mitte aufgeteilt; der Mittelwert aus maximalen und minimalen Vektor wird in die temporäre Variable vCenter gespeichert
- der erste Knoten soll links unten und vorne liegen; der minimale Vektor wird von dem zu unterteilenden Knoten kopiert ; als maximaler Vektor kommt vCenter in Frage
41
Vorberechnungen
Schritt 2: Zuordnen der Dreiecke Einem Knoten wird ein Dreieck dann
zugeteilt, wenn:- sich mindestens ein Vertex in der
Bounding-Box befindet- mindestens eine Seite die Bounding-
Box schneidet- mindestens eine Seitenhalbierende
die Bounding-Box schneidet
42
Vorberechnungen
Das erste wird mit tbPointHitsBox berechnet und die anderen Bedingungen mit tbLineHitsBox ; es kann vorkommen dass ein Dreieck zu mehreren Boxen gehören kann. Bei Kollision ist das egal, beim rendern würde das aber Probleme bereiten
Wir erstellen eine temporäre Liste die Platz für alle Dreiecke des zu unterteilenden Knotens hat; dann geht man alle Dreiecke durch und prüft ob sie die oberen Bedingungen erfüllen, wenn ja, wird der Dreieck in di temp. Liste aufgenommen und der Zähler wird hochgezählt; die dazugehörigen Dreiecke werden in die eigentliche Liste kopiert
Die bIsLeaf Variable wird entsprechend neugesetz
43
Vorberechnungen
Schritt 3: die Rekursion - nachdem ein neuer Unterknoten erstellt
wurde, muss er wieder unterteilt werden; der Parameter der Unterteilungstiefe wird um eins verringert Löschen des Octrees
- es wird wieder rekursiv vorgegangen; die Funktion DeleteNode wird einmal auf den Wurzelknoten aufgerufen
- DeleteNode löscht zuerst die dreiecksliste, dann die Unterknoten und schließlich den eogenen Knoten
44
Linien und Modelle
Transformation der Linie- anstatt das ganze Modell in absolute
Koordinaten zu transformieren, transformieren wir die Linie mit der inversen Transformationsmatrix Das rekursive Prinzip
- einer rekursiven Funktion werden die Linie(transformiert), das Modell und den Octree-Knoten übergeben
- die Funktion prüft ob die Linie die Bounding-Box trifft; wenn das ein Endknoten ist, wird der Kollisionstest Dreieck für Dreieck durchgeführt
45
Linien und Modelle
Der Test mit den Dreiecken- wir haben bereits die Extradaten
berechnet- zuerst prüfen, ob die Linie die Ebene
des Dreiecks schneidet , wenn nicht, dann Abbrechen
- dann mit der Funktion tbPlaneDotCoords überprüfen ob der Punkt im Dreieck liegt; wenn ein negativer Wert rauskommt , kann es abgebrochen werden
46
Kollision zwischen zwei Modelle
Die rekursive Funktion- die Funktion heißt
tbModelHitsModelRec - sie erhält als Parameter beide
Modelle, die Matrix jedes Modells, die inverse Matrix und den Octree-Knoten 1.Schritt: schneiden sich die Bounding-
Boxes? - zuerst wird geprüft , ob sich die Bounding-Boxes schneiden, wenn nicht brechen wir ab
47
Kollision zwischen zwei Modelle
2.Schritt: Fallunterscheidung – es muss zwischen vier Fälle unterschieden werden
1. Beide Knoten sind Endknoten2. Knoten A ist ein Endknoten, Knoten
B nicht3. knoten B ist ein Endknoten, Knoten
A nicht4. Beide Knoten sind keine Endknoten
48
Kollision zwischen zwei Modelle
Fall 1- es muss die Kollision zwischen den Dreiecken von Knoten A und B getestet werden- anstatt beide Modelle in absolute Koordinaten zu transformieren, transformieren wir das eine Modell in das Koordinatensystem des anderen; die dazu gehörige Matrix ist das Produkt aus der Matrix des zu transformierenden Modells und der inversen Matrix- um Zeit zu sparen wird der Knoten mit den wenigen Dreiecken ausgewählt
49
Kollision zwischen zwei Modelle
- die Dreiecke von Knoten B werden mit einer for-Schleife durchlaufen, die Vektoren werden mit der errechneten Matrix transformiert, die neuen Vektoren werden in vTriA , vTriB und vTriC gespeichert
- die Dreiecke von Knoten A werden analog durchlaufen;
- mit der Funktion tbtringleHitsTriangle, wird die Kollision zwischen zwei Dreiecke getestst
50
Kollision zwischen zwei Modelle
Fall 2 und Fall 3- wenn Knoten A ein Endknoten ist und
Knoten B nicht, dann wird jeder Unterknoten von B durchlaufen und auf Kollision getestet(rekursiv)
- zum Schluss kommt man zum Fall 1 Fall 4
-wenn beide Knoten keine Endknoten sind , wird es wie bei Fall 2 vorgegangen, zum Schluss kommt man zum Fall 1
51
Kollision zwischen zwei Modelle
Der Bounding-Sphere-Test- bevor die rekursive Funktion
tbModelHitsModelRec aufgerufen wird, wird die nicht rekursive Funktion tbModelHitsModel aufgerufen; diese prüft ob sich die Umgebungskugeln der Modelle schneiden und ruft die rekursive Funktion tbModelHitsModelRec aufDie Funktion von der Engine kann auf Wunsch den Ort der Kollision, die Normalenvektoren der kollidierenden Dreiecke und deren Nummern liefern
52
Volltreffer!
Damit die geschossenen Projektile auch ihre Mission erfüllen, muss die Funktion CProjektile::Move erweitert werden
Die Kollisionserkennung- die Projektile werden als Linie betrachtet;
Startpunkt ist die Position vor dem Bewegen und Endpunkt diejenige nach dem Bewegen
- beim Laserstrahl muss noch seine Länge eingerechnet und addiert werden daher auf den Endpunkt noch die z-Achse des Strahls multipliziert mit seiner Länge
53
Volltreffer!
- jetzt werden mit eine for-Schleife alle Schiffe durchgangen
- mit tbLineHitsModel finden wir welcher Schiff einen Treffer einstecken muss
- die Toleranz für die Kollisionserkennung hängt davon ab, ob das Schiff noch genug Schutzschildenergie hat
- das ist der Fall, wenn die fDamageToShields-Variable des Waffentyps kleiner ist als die verbleibende Schutzschildenergie des Schiffs
54
Volltreffer!
Die Wirkung eines Treffers- wenn Kollision, Projektils- Variable auf null
setzen- testen , ob Schutzschildenergie zum
Schutzabwehr ausreicht- wenn nicht, Projektil dringt durch die
Hülle hindurch und beschädigt andere Systemen- der angerichtet schaden wird in der
separaten Methode CShip::DoDemage hinzugefügt, als Parameter werden den Ort des Treffers und die Trefferstärke übergeben
55
Volltreffer!
Hüllenbrüche und defekte Systeme- die DoDemage-Methode wird
implementiert- die Trefferposition wird relativ zum
Schiff umgewandelt- dann braucht man System für
System durchzugehen und die Entfernung zum TrefferPunkt berechnen, je größer die Entfernung zum Einschlagpunkt , desto geringer der Schaden
56
Zusammenstoß zweier Schiffe
Der Test- die Funktion CShip::Move wird so
umgeändert, dass sie in jeder Frame auf Kollision prüft Schaden bei einer Kollision
- die Methode CShip::DoDemage erwartet zwei Parameter: die Stelle, an der das Geschoss einschlägt und die Stärke
- die Stärke hängt von der Differenz zwischen den Bewegungsvektoren der Schiffe und von dem Verhältniss der Massen der Schiffe ab
57
Zusammenstoß zweier Schiffe
Abprallen der Raumschiffe- Kollision zwischen zwei Kugeln(keine
Energie geht verloren)- man verbindet beide
Kugelmittelpunkte im Moment der Kollision, dann teilt man die Geschwindigkeitsvektoren beider Kugeln auf:in jeweils eine Komponente senkrecht zu Verbindungslinie und eine parallel dazu . Beide Kugeln tauschen Ihre Bewegungen parallel zu dieser Linie
58
Zusammenstoß zweier Schiffe
- ein Geschwindigkeitsvektor wird schwer in zwei Komponenten geteilt, es reicht wenn nur eine der beiden Komponenten berechnet wird
- wir berechnen die Komponente des Geschwindigkeitsvektors , die parallel zum Verbindungsvektor steht ; dabei gilt: die parallele Komponente ist gleich dem normalisierten Verbindungsvektor multipliziert mit einem bestimmten Faktor ; Diesen Faktor erhalten wir durch das Punktprodukt aus dem Verbindungsvektor und dem Geschwindigkeitsvektor
