Kollisionen erkennen - Kollisions- und Schnittpunkttests auf Dreieckbasis - Kollisions- und Schnittpunkttests auf Viereckbasis - Einsatz von achsenausgerichteten

Kollisionen erkennenKollisionen erkennen

- Kollisions- und Schnittpunkttests auf DreieckbasisKollisions- und Schnittpunkttests auf Dreieckbasis- Kollisions- und Schnittpunkttests auf ViereckbasisKollisions- und Schnittpunkttests auf Viereckbasis- Einsatz von achsenausgerichteten Bounding Boxen für Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung der Performance bei Kollisions- und die Verbesserung der Performance bei Kollisions- und Schnittpunkttests auf DreieckbasisSchnittpunkttests auf Dreieckbasis- Kollision zweier 3D Modelle:Kollision zweier 3D Modelle:

-OOB-OOB-TestOOB-OOB-Test-AABB-OOB_TestAABB-OOB_Test

Kollisions- und Schnittpunkttests auf Dreieckbasis (1)Kollisions- und Schnittpunkttests auf Dreieckbasis (1)

3D Modell auf Dreieckbasis3D Modell auf Dreieckbasis– Drahtgittermodell (besteht aus Dreiecken) mit Drahtgittermodell (besteht aus Dreiecken) mit

TexturüberzugTexturüberzug– Dreiecke werden zu Kollisions- und Dreiecke werden zu Kollisions- und

Schnittpunkttests herangezogenSchnittpunkttests herangezogen Punkt-in-Dreieck-TestPunkt-in-Dreieck-Test

– Wofür: z.B. um festzustellen ob ein Spieler Wofür: z.B. um festzustellen ob ein Spieler gegen die Wand gerannt istgegen die Wand gerannt ist

Strahl-schneidet-Dreieck-Test:Strahl-schneidet-Dreieck-Test:– Wofür: Zur Bestimmung der Fußboden- und Wofür: Zur Bestimmung der Fußboden- und

TerrainhöheTerrainhöhe


1. Schnittpunkt in der Ebene bestimmen (allgemein):1. Schnittpunkt in der Ebene bestimmen (allgemein):– Mit Normalenform einer EbeneMit Normalenform einer Ebene

- Wenn Punkt innerhalb der Ebene liegt, liegt der Vektor ∆ in der Ebene und ist damit senkrecht zur Flächennormalen n. - Das Skalarprodukt (relative Lage der zwei Vektoren zueinander) ist gleich Null

Es muss zuerst überprüft werden ob zwischen den Objekten in der Umgebung und dem jeweiligen Dreieck in einer Ebene einen Schnittpunkt gibt


Schnittpunktberechnung Schnittpunktberechnung (konkret)(konkret)


Dreieck in der Ebene Dreieck in der Ebene (Konstruktion einer (Konstruktion einer Ebene aus Eckpunkten)Ebene aus Eckpunkten)– Wir kennen die Eckpunkte Wir kennen die Eckpunkte

(Vertices) des Dreiecks (Vertices) des Dreiecks aus denen das 3D Modell aus denen das 3D Modell zusammengesetzt ist zusammengesetzt ist (wurden festgelegt als das (wurden festgelegt als das Gittermodell entworfen Gittermodell entworfen wurde)wurde)

– Daraus muss die Ebene Daraus muss die Ebene berechnet werdenberechnet werden


Der HalbseitentestDer Halbseitentest– Was können wir schon?Was können wir schon?

Aus Punkten Ebene berechnenAus Punkten Ebene berechnen Wir kennen Methode zur Schnittpunktberechnung mit EbeneWir kennen Methode zur Schnittpunktberechnung mit Ebene

– Schnittpunkt muss nicht innerhalb des Dreiecks seinSchnittpunkt muss nicht innerhalb des Dreiecks sein Ebene hat unendliche AusdehnungEbene hat unendliche Ausdehnung Ausdehnung eines Dreiecks ist aber begrenztAusdehnung eines Dreiecks ist aber begrenzt

– Methode um festzustellen ob ein Schnittpunkt einer Methode um festzustellen ob ein Schnittpunkt einer Ebene innerhalb des Dreiecks liegt ist HalbseitentestEbene innerhalb des Dreiecks liegt ist Halbseitentest Es wird überprüft auf welcher Seite einer Dreieckskante der Es wird überprüft auf welcher Seite einer Dreieckskante der

Schnittpunkt liegtSchnittpunkt liegt Liegt der Schnittpunkt immer innerhalb der drei Dreieckskanten, Liegt der Schnittpunkt immer innerhalb der drei Dreieckskanten,

liegt er auch innerhalb des Dreiecks liegt er auch innerhalb des Dreiecks


Halbseitentest die Zweite:Halbseitentest die Zweite:

Test ist möglich für zweidimensionale, konvexe Polygone

Konvex = Innenwinkel aller benachbarter Kanten ist < 180 °

Für dreidimensionale Polygone gibt es den Halbraumtest

Kleiner mathematisch-terminologischer Exkurs:-Der Mathematiker bezeichnet sowohl die Innen-, als auch die Außenseite als Halbseite Deshalb der Name


Auf zur Praxis:Auf zur Praxis:– Klasse CTriangle Klasse CTriangle

wird implementiertwird implementiert

3 Vektoren für die Eckpunkte3 Vektoren für die Senkrechten der Dreieckskanten

Normalenvektor

Konstruktor/Destruktor hat keine Funktion

Dreiecksnummer


Was machen die Funktionen:

Init_Triangle()

-Aufgabe: Initialisierung eines Dreiecks- Skalierte sowie unskalierte Eckpunkte können übergeben werden

-Damit das Dreieck mit unskalierten Eckpunkten richtig skaliert werden kann, muss der Skalierungsfaktor mit übergeben werden

Warum skaliert, warum unskalierte Eckpunkte:

- Bei wenigen Objekten ist es sinnvoll die Eckpunkte als skaliert schon vorliegen zu haben (also ein 3D Modell zu übergeben)-Bei mehreren Objekten ist es sinnvoller wenige 3D Modelle zu verwenden und durch Variation des Skalierungsfaktors variable Objekte zu erzeugen (bsplw. Bei Asteroiden)

- Nach Zuweisung der Eckpunkte wird der Normalvektor, sowie die Senkrechten der Dreieckskanten berechnet

Init_Triangle()


Test_for_Ray_Intersection()Test_for_Ray_Intersection()– Führt Schnittpunkttest zwischen einem Strahl Führt Schnittpunkttest zwischen einem Strahl

(z.B. Sonnenstrahl) und einem Dreieck durch(z.B. Sonnenstrahl) und einem Dreieck durch Schritt 1: es wird überprüft ob Normalvektor und die Schritt 1: es wird überprüft ob Normalvektor und die

Richtung des Strahls senkrecht zueinander sindRichtung des Strahls senkrecht zueinander sind– Wenn ja, kann es keinen Schnittpunkt gebenWenn ja, kann es keinen Schnittpunkt geben

Schritt 2: intersection_parameter (entspricht Variable Schritt 2: intersection_parameter (entspricht Variable a aus 7.3) wird berechneta aus 7.3) wird berechnet

– Um Schnittpunkt zu bestimmen wird dieser Parameter Um Schnittpunkt zu bestimmen wird dieser Parameter anschließend in die Geradengleichung eingesetztanschließend in die Geradengleichung eingesetzt

Schritt 3: HalbseitentestSchritt 3: Halbseitentest

Test_for_Ray_Intersection()Test_for_Ray_Intersection()


Test_for_Point_Collision()Test_for_Point_Collision()– Kollisionstest zwischen Punkt und einem Dreieck wird gemacht Kollisionstest zwischen Punkt und einem Dreieck wird gemacht

(Raketen, Laserimpulswaffen (Raketen, Laserimpulswaffen ))– Übergeben werden:Übergeben werden:

Adresse des Ortsvektors der Objektmittelpunktes Adresse des Ortsvektors der Objektmittelpunktes Adresse der ObjektflugrichtungAdresse der Objektflugrichtung Adresse einer GanzzahlvariablenAdresse einer Ganzzahlvariablen

– Im Falle eines positiven Kollisionstests übergibt man die DreiecksnummerIm Falle eines positiven Kollisionstests übergibt man die Dreiecksnummer

Diese Funktion für den Punkt und die „Strahlfunktion“ sind Diese Funktion für den Punkt und die „Strahlfunktion“ sind identischidentisch– Einziger Unterschied:Einziger Unterschied:

Abstandstest zwischen Dreieck und ObjektmittelpunktAbstandstest zwischen Dreieck und Objektmittelpunkt– Ist der Abstand zu groß liegt keine Kollision vorIst der Abstand zu groß liegt keine Kollision vor– Ist Abstand in bestimmten Rahmen, liegt Kollision vorIst Abstand in bestimmten Rahmen, liegt Kollision vor– Die Größe des Rahmens soll man durch ausprobieren herausfindenDie Größe des Rahmens soll man durch ausprobieren herausfinden

Test_for_Point_Collision()Test_for_Point_Collision()

Test_for_Point_Collision_Wall()Test_for_Point_Collision_Wall()

Abwandlung der Abwandlung der Test_for_Point_Collision() für Test_for_Point_Collision() für den Kollisionstest an einer den Kollisionstest an einer WandWand– Keine Adresse der Keine Adresse der

Bewegungsrichtung wird mit Bewegungsrichtung wird mit übergebenübergeben

Als Richtung wird immer Als Richtung wird immer der negative der negative Normalenvektor der Normalenvektor der Wand verwendetWand verwendet


CTriangle() wird später zur genauen Treffer- und CTriangle() wird später zur genauen Treffer- und Schnittpunkterkennung in Indoor und Schnittpunkterkennung in Indoor und Terainrenderer verwendetTerainrenderer verwendet– Bei der Initialisierung werden immer die Bei der Initialisierung werden immer die

Modellkoordinaten der Dreiecke einer 3 D Modells an Modellkoordinaten der Dreiecke einer 3 D Modells an die Funktion Init_Triangle() übergebendie Funktion Init_Triangle() übergeben

– Im Spiel hingegen unterliegen die Modelle ständigen Im Spiel hingegen unterliegen die Modelle ständigen TransformationenTransformationen

Frage: Wie soll Treffererkennung ohne Kenntnis Frage: Wie soll Treffererkennung ohne Kenntnis der Weltkoordinaten der 3 D Modelle der Weltkoordinaten der 3 D Modelle funktionieren? funktionieren?


Beispiel:Beispiel:– Rakete fliegt, Raumschiff (fliegt), Treffer soll Rakete fliegt, Raumschiff (fliegt), Treffer soll

erkannt werdenerkannt werden– Mittels Funktion Test_for_Point_Collision() soll Mittels Funktion Test_for_Point_Collision() soll

getroffenes Dreieck gefunden werdengetroffenes Dreieck gefunden werden Lösung:Lösung:

– Ortsvektor und Bewegungsrichtung der Rakete müssen so Ortsvektor und Bewegungsrichtung der Rakete müssen so transformiert werden, dass Modellkoordinaten der Dreiecke transformiert werden, dass Modellkoordinaten der Dreiecke des Raumschiffs für die Treffererkennung verwendet des Raumschiffs für die Treffererkennung verwendet werden könnenwerden können

RücktransformationRücktransformation

Für Treffertest müssen Position und Flugrichtung transformiert werden

- Inverse Rotationsmatrix des Raumschiffes wird benötigt

Inverse Rotationsmatrix macht die Transformationen der Oirginalmatrix wieder rückgängig


Dreieck-Dreieck-KollisionstestDreieck-Dreieck-Kollisionstest– Wenn sich zwei Dreiecke schneiden muss mindestens Wenn sich zwei Dreiecke schneiden muss mindestens

eine Kante des einen Dreiecks eine Fläche des anderen eine Kante des einen Dreiecks eine Fläche des anderen schneidenschneiden Schnittpunktberechnungsfunktion kennen wir bereitsSchnittpunktberechnungsfunktion kennen wir bereits

– Die Dreieckskante die man der Funktion übergibt muss Die Dreieckskante die man der Funktion übergibt muss man relativ zu den Modellkoordinaten des anderen man relativ zu den Modellkoordinaten des anderen Dreiecks transformierenDreiecks transformieren Eckpunkte des Dreiecks transformieren und aus ihnen die Eckpunkte des Dreiecks transformieren und aus ihnen die

Kanten berechnenKanten berechnen

– Dann intersection_parameter berechnenDann intersection_parameter berechnen Hat dieser einen Wert >=0 und <=1schneidet die Kante Hat dieser einen Wert >=0 und <=1schneidet die Kante

diejenige Ebene in der das andere Dreieck liegt diejenige Ebene in der das andere Dreieck liegt

Kollisions- und Schnittpunkttests auf Viereckbasis (1)Kollisions- und Schnittpunkttests auf Viereckbasis (1)

Unterschied zu Tests auf Dreieckbasis:Unterschied zu Tests auf Dreieckbasis:– Beim Halbseitentest kommt eine weitere Kante hinzuBeim Halbseitentest kommt eine weitere Kante hinzu– Mit Klasse ClQuad()Mit Klasse ClQuad()

Hat zwei weitere FunktionenHat zwei weitere Funktionen– Test_for_axis_aligned_Ray_Intersection()Test_for_axis_aligned_Ray_Intersection()

Schnittpunkt zwischen Strahl und achsenausgerichtetem Schnittpunkt zwischen Strahl und achsenausgerichtetem Rechteck/Quader kann schneller berechnet werden als mit Rechteck/Quader kann schneller berechnet werden als mit Test_for_Ray_Intersection() Test_for_Ray_Intersection() Schnittpunkte sind einfacher Schnittpunkte sind einfacher und auf Halbseitentest kann verzichtet werden, und nur und auf Halbseitentest kann verzichtet werden, und nur Ausdehnung in x-, y- und z-Richtung wird benötigtAusdehnung in x-, y- und z-Richtung wird benötigt

– Test_Portal_Durchtritt()Test_Portal_Durchtritt() Verwendet Seitentest den wir schon kennen (in Verbindung Verwendet Seitentest den wir schon kennen (in Verbindung

mit Portalen)mit Portalen)

Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung der Performance bei Kollisions- und Schnittpunkttests auf Dreieckbasisder Performance bei Kollisions- und Schnittpunkttests auf Dreieckbasis

Sind viele Objekte vorhanden deren Kollisionen berechnet Sind viele Objekte vorhanden deren Kollisionen berechnet werden müssen kommt es ab einem gewissen Grad zu werden müssen kommt es ab einem gewissen Grad zu Performance-Problemen (alle Dreiecke müssen auf Performance-Problemen (alle Dreiecke müssen auf Kollision getestet werden)Kollision getestet werden)– Bounding Boxen bringen hier große VorteileBounding Boxen bringen hier große Vorteile

Zuerst Treffertest mit Boxen und Waffe durchgeführtZuerst Treffertest mit Boxen und Waffe durchgeführt Ist dieser positiv können alle Dreiecke in anderen Boxen vernachlässigt Ist dieser positiv können alle Dreiecke in anderen Boxen vernachlässigt

werdenwerden Nur die in der positiv getesteten Box liegenden Dreiecke werden Nur die in der positiv getesteten Box liegenden Dreiecke werden

getestetgetestet

Treffertest zwischen AABB und Lenkwaffe ist ohne großen Treffertest zwischen AABB und Lenkwaffe ist ohne großen Rechenaufwand möglichRechenaufwand möglich– Position der Lenkwaffe wird mit den Eckpunkten der Box verglichenPosition der Lenkwaffe wird mit den Eckpunkten der Box verglichen

Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung der Performance bei Kollisions- und Schnittpunkttests auf Dreieckbasis der Performance bei Kollisions- und Schnittpunkttests auf Dreieckbasis

(2)(2)

Bei Schnittpunktberechnung zwischen Strahl und Bei Schnittpunktberechnung zwischen Strahl und Box wird überprüft ob der Strahl eine der sechs Box wird überprüft ob der Strahl eine der sechs Flächen der Box schneidetFlächen der Box schneidet

Bei Verwendung von AABB kann Bei Verwendung von AABB kann Test_for_axis_aligned_Ray_Intersection()- Test_for_axis_aligned_Ray_Intersection()- Methode benutzt werdenMethode benutzt werden

Praktikabelste Lösung ist eine eigene Klasse zur Praktikabelste Lösung ist eine eigene Klasse zur Erzeugung einer AA Bounding Box anzulegenErzeugung einer AA Bounding Box anzulegen– Damit AABB korrekt initialisiert werden kann, müssen Damit AABB korrekt initialisiert werden kann, müssen

der Klasseninstanz vor dem Aufruf der der Klasseninstanz vor dem Aufruf der Initialisierungmethode die minimalen und maximalen x-, Initialisierungmethode die minimalen und maximalen x-, y- und z-Werte übergeben werdeny- und z-Werte übergeben werden

Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung der Einsatz von achsenausgerichteten Bounding Boxen für die Verbesserung der Performance bei Kollisions- und Schnittpunkttests auf Dreieckbasis (3)Performance bei Kollisions- und Schnittpunkttests auf Dreieckbasis (3)

Ermittlung der Eckpunkte der Box

3 Seiten Quelltext Siehe Buch S. 204-208 (Aufruf der CAABB Kollisions- und Schnittpunkttests aus einer 3D Modellklasse heraus)

Kollision zweier 3D Modelle (1)Kollision zweier 3D Modelle (1)

Kollisionsprüfungen brauchen sehr viel Zeit (wurde Kollisionsprüfungen brauchen sehr viel Zeit (wurde schon sehr oft gesagt schon sehr oft gesagt ))

Dem entgegen wirken Boundingboxen (wurde Dem entgegen wirken Boundingboxen (wurde auch schon oft gesagt auch schon oft gesagt ))

Man hat die Wahl diese Boxen in einer einfachen Man hat die Wahl diese Boxen in einer einfachen Baumstruktur zu organisieren Baumstruktur zu organisieren – Hierarchisches KollisionsmodellHierarchisches Kollisionsmodell

Oder als einen Satz gleichberechtigter Boxen zu Oder als einen Satz gleichberechtigter Boxen zu definierendefinieren– All-equal KollisionsmodellAll-equal Kollisionsmodell

Muss Modellgeometrie möglichst gut wiedergebenMuss Modellgeometrie möglichst gut wiedergeben


All-equal KollisionsmodellAll-equal Kollisionsmodell– Kommt mit wenigen Boxen aus und ist einfach zu Kommt mit wenigen Boxen aus und ist einfach zu

implementierenimplementieren– Ohne weitere Optimierung ist die benötigte Rechenzeit Ohne weitere Optimierung ist die benötigte Rechenzeit

für einen vollständigen Prüflauf an Dreieck-Dreieck für einen vollständigen Prüflauf an Dreieck-Dreieck Kollisionstests deutlich höher als bei einem Kollisionstests deutlich höher als bei einem hierarchischem Kollisionsmodellhierarchischem Kollisionsmodell

– Bei nur 6 Boxen müssten schlimmstenfalls 36 Box-Box -Bei nur 6 Boxen müssten schlimmstenfalls 36 Box-Box -Kollisionstests durchgeführt werdenKollisionstests durchgeführt werden Bestenfalls nur ein TestBestenfalls nur ein Test


Hierarchisches Kollisionsmodell:Hierarchisches Kollisionsmodell:– Jedes Dreieck soll von einer Bounding Box umschlossen werden Jedes Dreieck soll von einer Bounding Box umschlossen werden – BaumstrukturBaumstruktur

Sollte augeglichen seinSollte augeglichen sein– Kommt in der Realität aber fast nie vorKommt in der Realität aber fast nie vor

– Findet eine Box-Box Kollision statt, wird noch ein Dreieck-Dreieck-Findet eine Box-Box Kollision statt, wird noch ein Dreieck-Dreieck-Kollisionstest durchgeführtKollisionstest durchgeführt

– Zudem kann es vorkommen, dass die zu testende Box des einen Zudem kann es vorkommen, dass die zu testende Box des einen Baumes mehrere Boxen eines anderen Baumes schneidetBaumes mehrere Boxen eines anderen Baumes schneidet Dadurch müssen mehrere Testläufe in Kauf genommen werdenDadurch müssen mehrere Testläufe in Kauf genommen werden

Bounding-Box-KollisionstestsBounding-Box-Kollisionstests– 3D Modelle unterliegen in der Spielerealität ständigen 3D Modelle unterliegen in der Spielerealität ständigen

Veränderungen, weshalb der AABB-AABB Kollisionstest nicht Veränderungen, weshalb der AABB-AABB Kollisionstest nicht angewendet werden kannangewendet werden kann

– Deshalb gibt es eine logische Erweiterung, den OBB-OBB Deshalb gibt es eine logische Erweiterung, den OBB-OBB Kollisionstest Kollisionstest


Der OBB-OBB KollisionstestDer OBB-OBB Kollisionstest– OB Boxen haben unendlich OB Boxen haben unendlich

viele viele OrientierungsmöglichkeitenOrientierungsmöglichkeiten

– Es ergeben sich nicht weniger Es ergeben sich nicht weniger als 15 potentielle separierbare als 15 potentielle separierbare Achsen, die nacheinander Achsen, die nacheinander geprüft werden müssengeprüft werden müssen

– Siehe Beispiel S. 210-215Siehe Beispiel S. 210-215 OBB-OBB Kollisionstest wird OBB-OBB Kollisionstest wird

genau unter die Lupe genommen genau unter die Lupe genommen und Problemfälle erläutertund Problemfälle erläutert


AABB-OBB-KollisionstestAABB-OBB-Kollisionstest– Etwas einfacher aufgebaut, da eine Etwas einfacher aufgebaut, da eine

achsenausgerichtete BB eines achsenausgerichtete BB eines untransformierten Objektes gegen eine untransformierten Objektes gegen eine orientierte BB eines transformierten Objektes orientierte BB eines transformierten Objektes getestet werden mussgetestet werden muss

– Orientierte BB des transf. Objektes müssen auf Orientierte BB des transf. Objektes müssen auf die Modellkoordinaten des untransformierten die Modellkoordinaten des untransformierten Objektes rücktransformiert werdenObjektes rücktransformiert werden Siehe S. 216-219Siehe S. 216-219


Ein all-equal Modell im EinsatzEin all-equal Modell im Einsatz– Mit Hilfe einer Methode, aus C_OBB, Init_as_AABB() können Mit Hilfe einer Methode, aus C_OBB, Init_as_AABB() können

achsenausgerichtete BB für die 3D Modelle erzeugt werdenachsenausgerichtete BB für die 3D Modelle erzeugt werden– 1. Schritt eines Kollisionstests besteht also darin die BB des einen 1. Schritt eines Kollisionstests besteht also darin die BB des einen

Objektes (pObject[jj]) auf die Modellkoordinaten des anderen Objektes (pObject[jj]) auf die Modellkoordinaten des anderen Objektes (pObject[j]) rück zu transformierenObjektes (pObject[j]) rück zu transformieren

– Dafür stehen drei Rotationsmatrizen zur Verfügung:Dafür stehen drei Rotationsmatrizen zur Verfügung:


Im einfachsten Fall werden dann alle ausger. BB des untr. Objektes (pObject[j]) Im einfachsten Fall werden dann alle ausger. BB des untr. Objektes (pObject[j]) paarweise gegen alle OBB des tr. Obejktes (pObject[jj]) auf mögliche Kollision getestetpaarweise gegen alle OBB des tr. Obejktes (pObject[jj]) auf mögliche Kollision getestet

Documents

Kollisionen erkennen - Kollisions- und Schnittpunkttests auf Dreieckbasis - Kollisions- und Schnittpunkttests auf Viereckbasis - Einsatz von achsenausgerichteten