Kollisionen beschreibenTag 6

Kollision mit einer achsenparallelen Fläche

• Reflektionsgesetz: Einfallswinkel = Ausfallswinkel• Def. Normalenvektor / Flächennormale

steht immer senkrecht auf einer Fläche / Linie hat eine Länge von 1

• bei einer achsenparallelen Kollision ist die Flächennormale der Kollisionsfläche immer parallel oder antiparallel zur x -, y- oder z – Achse ausgerichtet

dementsprechend liegt die Kollisionsfläche in der xy – , yz – oder zx – Ebene

Kollision mit einer achsenparallelen Fläche

• Flugrichtung nach Kollision:

Umkehrung des Vorzeichens derjenigen Komponente, die in Richtung oder Gegenrichtung des Normalenvektors zeigt => im Beispiel: x - Komponente

Kollision mit einer achsenparallelen Fläche

• Codefragment Kollision in yz – Ebene (Beispiel) Normalenvektor der yz – Ebene: n = (1, 0, 0) oder (-1, 0, 0) Flugrichtung.x = - Flugrichtung.x

Flugrichtung.y = Flugrichtung.y

Flugrichtung.z = Flugrichtung.z

• Anwendung bei der Verwendung von achsenausgerichteten Bounding – Boxen (AABB)

• achsenausgerichtet, da die x -, y – und z – Achsen der AABBs mit den Achsen des Weltkoordinatensystems übereinstimmen

Kollision mit einer achsenparallelen Fläche

• beide Kollisionsflächen liegen in der gleichen Ebene

• dadurch Berechnung der neuen Flugrichtung aufgrund vorherigem Schema möglich (Einfallswinkel = Ausfallswinkel) / Umkehrung des Vorzeichens einer Komponente

Kollision an beliebig ausgerichteten Flächen

• Problem der achsenparallelen Flächen:

Orientierung der Objekte wird nicht berücksichtigt => unrealistische (dafür schnelle und einfache) Kollisionsberechnung

• Bounding – Boxen sollten Bewegungen / Skalierungen des Objektes abbilden => bsw. Drehung bei Änderung der Flugrichtung => orientierte Bounding – Box (OOB)

Kollision an beliebig ausgerichteten Flächen

Kollision an beliebig ausgerichteten Flächen

Berechnung der neuen Flugrichtung1. Berechnung des Skalarprodukts von

Flächennormale und Flugrichtung

tempFloat = D3DXVec3Dot(&Normal, &Flugrichtung);

2. Berechnung des negativen Projektionsvektors auf die Flächennormale

Projektionsvektor = - tempFloat * Normal

3. Berechnung der neuen Flugrichtung

Flugrichtung = Flugrichtung + 2 * Projektionsvektor

Kollision an beliebig ausgerichteten Flächen

• Warum geht das so?• Def. Skalarprodukt zweier Vektoren:• Das Ergebnis des Skalarprodukts beinhaltet also immer

auch den Winkel zwischen den beiden Vektoren => im Beispiel ist dies der Einfallswinkel

• da Einfallswinkel = Ausfallswinkel gilt:

Winkel der neuen Flugrichtung = (Winkel zwischen alter Flugrichtung und Flächennormaler) * 2 + alte_Flugrichtung

Flugrichtung(neu) = Flugrichtung(alt) + 2*p

cos*** baba

Kollision an beliebig ausgerichteten Flächen

• statt Bounding – Boxen für Objekte zu entwickeln, kann man auch auf die Flächen dieser Objekte zurückgreifen und diese als Kollisionsflächen verwenden => meist Umschließung der Objektflächen mit Bounding – Boxen

• Vorteile: realistischere Richtungsänderungen geringere Anzahl an Prüfdurchläufen = höhere Performance

Physikalisch korrekte Kollisionsbeschreibung

• bisherige Berechnungsmethoden vernachlässigten die Masse der beteiligten Objekte

• Reflektionsgesetz gilt aber nur dann, wenn die Masse des einen Objekts deutlich größer ist

• demnach:

Stöße

• Formeln: Impuls = Masse * Geschwindigkeit

p = m * v Impulserhaltungssatz: bei einem elastischen Stoß bleibt die Summe der Impulse

beider Objekte vor und nach dem Stoß gleich kinetische Energie: Energieerhaltungssatz:

zusammengefasst:

bfbafabibaia vmvmvmvm

²*5,0 mv

²**5,0²*5,0²**5,0²*5,0 bfbafabibaia vmvmvmvm

)/())()1(( babaaibibaf mmmmvvmev

)/())()1(( bababiaiabf mmmmvvmev

Eindimensionaler Stoß

• Stoßpartner bewegen sich vor und nach dem Stoß auf einer Linie => Kollisionsachse

• als Kollisionsachse wird der Einfachheit halber die x -, y – oder z – Achse gewählt

• anelastische Stöße Endgeschwindigkeiten kleiner als bei einem elastischen Stoß,

da ein Teil der Energie für die Verformung der Objekte verbraucht wird

dieser Verlust wird durch einen Faktor ausgedrückt, der für die Kollisionsberechnung festgelegt wird => für e = 1 ist der Stoß elastisch, für e < 1 zunehmend anelastisch

)/())()1(( babaaibibaf mmmmvvmev

)/())()1(( bababiaiabf mmmmvvmev

Eindimensionaler Stoß mit beliebig orientierter Kollisionsachse

Eindimensionaler Stoß mit beliebig orientierter Kollisionsachse

• Vektor n = Differenzvektor der Ortsvektoren beider Stoßpartner => Schwerpunktsdifferenzvektor

• normierter Schwerpunktsdifferenzvektor => Kollisionsrichtung

• zur Bestimmung der Endgeschwindigkeiten werden vorherige Gleichungen verwendet => diese beziehen sich aber auf eine Bewegung parallel zur Kollisionsrichtung

• Endgeschwindigkeit.x = Geschwindigkeitsbetrag * Kollisionsrichtung.x

Endgeschwindigkeit.y = Geschwindigkeitsbetrag * Kollisionsrichtung.y

Endgeschwindigkeit.z = Geschwindigkeitsbetrag * Kollisionsrichtung.z

Dreidimensionaler Stoß

• Wiederholung:• bei einer Kollision mit einer Fläche ändert sich nur

diejenige Komponente, die parallel zur Kollisionsflächennormalen liegt

• der Kollisionsrichtungsvektor entspricht der Flächennormalen der Kollisionsfläche

wie trennt man die Geschwindigkeitskomponenten, die sich während des Stoßes ändern von denen, die gleich bleiben?

Dreidimensionaler Stoß

• Zerlegung der Geschwindigkeiten in 3 Komponenten: 1. Komponente zeigt in Richtung der Flächennormalen 2. und 3. Komponente in Richtung der Spannvektoren der

Kollisionsfläche diese 3 Vektoren stehen alle senkrecht aufeinander und sind

somit linear unabhängig im 3 – dimensionalen Raum kann man durch die Kombination

von 3 linear – unabhängigen Vektoren jeden anderen Vektor darstellen

die Orthogonalität ist durch das Vorgehen bei der Bestimmung der Vektoren gewährleistet

Kreuzprodukt => das Kreuzprodukt zweier Vektoren ist ein Vektor, der auf beiden anderen Vektoren senkrecht steht

Dreidimensionaler Stoß

1. Spannvektor1 = Kollisionsrichtung x Richtungsvektor eines beteiligten Objektes

2. Spannvektor2 = Kollisionsrichtung x Spannvektor1 alle 3 Vektoren stehen senkrecht aufeinander• für die Berechnung des Kreuzprodukts verwendet

man die DirectX – Methode

D3DXVec3Cross(&Ziel, &Vektor1, &Vektor2)

Dreidimensionaler Stoß

• durch die Kombination der 3 linear – unabhängigen Vektoren kann man jeden Vektor im R³ darstellen

• Geschwindigkeitskompo- nente parallel zum Spannvektor s1:

xsvafs .1|| 1

Dreidimensionaler Stoßinline void Compute_3D_Collision_Response(D3DXVECTOR3* Velocity1, D3DXVECTOR3* Velocity2, float& mass1, float& mass2, D3DXVECTOR3* SchwerpunktsDiffVektor){ //Berechnung der Spannvektoren der Kollisionsebene: D3DXVec3Cross(&KollisionsSenkrechte1,&Kollisionsrichtung,Velocity1); NormalizeVector(&KollisionsSenkrechte1,&KollisionsSenkrechte1); D3DXVec3Cross(&KollisionsSenkrechte2,&KollisionsSenkrechte1,&Kollisionsrichtung); NormalizeVector(&KollisionsSenkrechte2,&KollisionsSenkrechte2); //Berechnung der Anfangsgeschwindigkeiten bezüglich dieser Achsen: temp1Factor = D3DXVec3Dot(Velocity1, &KollisionsSenkrechte1); temp2Factor = D3DXVec3Dot(Velocity1, &KollisionsSenkrechte2); temp3Factor = D3DXVec3Dot(Velocity1, &Kollisionsrichtung); temp4Factor = D3DXVec3Dot(Velocity2, &KollisionsSenkrechte1); temp5Factor = D3DXVec3Dot(Velocity2, &KollisionsSenkrechte2); temp6Factor = D3DXVec3Dot(Velocity2, &Kollisionsrichtung); // Die Geschwindigkeitsbeträge bezüglich der KollisionsSenkrechten // bleiben beim Stoss unverändert. // Nur die beiden Geschwindigkeitsbeträge bezüglich der Kollisionsrichtung verändern sich! temp9Factor = mass1 + mass2; temp10Factor = mass1 - mass2; // Berechnung der Endgeschwindigkeiten bezüglich der Kollisionsachse //Formeln vorherige Folie temp7Factor = (2*mass2*temp6Factor + temp3Factor*temp10Factor)/temp9Factor; temp8Factor = (2*mass1*temp3Factor - temp6Factor*temp10Factor)/temp9Factor; // Die Endgeschwindigkeiten bezüglich der Kollisionsrichtung und der KollisionsSenkrechten sind berechnet. // Jetzt müssen die Endgeschwindigkeiten bezüglich der x-, y- und z-Achse berechnet werden: // Rechnung für Objekt2 mit temp8 analog Velocity1->x = temp1Factor*KollisionsSenkrechte1.x + temp2Factor*KollisionsSenkrechte2.x + temp7Factor*Kollisionsrichtung.x; Velocity1->y = temp1Factor*KollisionsSenkrechte1.y + temp2Factor*KollisionsSenkrechte2.y + temp7Factor*Kollisionsrichtung.y; Velocity1->z = temp1Factor*KollisionsSenkrechte1.z + temp2Factor*KollisionsSenkrechte2.z + temp7Factor*Kollisionsrichtung.z;}

Methoden zur Kollisionsfeststellung

• Bounding – Circle / Bounding – Sphären –

Test• AABB – AABB – Test

Bounding – Sphären - Test

• sehr einfache Methode => man definiert für jedes Objekt einen Bounding – Circle (2D) bzw. eine Bounding – Sphäre (3D)

• die Definition erfolgt über die Festlegung eines Radius um den Mittelpunkt des Objekts

• im ersten Schritt berechnet man den quadratischen Abstand der Mittelpunkte beider Objekte

• ist dieser kleiner als die Summe der Quadrate der Kollisionsradien, liegt eine Kollision vor

Bounding – Sphären – Test

Der AABB – AABB – Test

• weniger rechenintensiv als Bounding – Sphären Test. dafür aber etwas ungenauer

• verwendet achsenausgerichtete Bounding – Boxen• Def. separierende Achse

eine separierbare Achse steht immer senkrecht zur getesteten Fläche der Bounding – Box und somit parallel zur x -, y – oder z – Achse des Weltkoordinatensystems

• Logik:

eine Kollision kann immer dann ausgeschlossen werden, wenn sich die Objekte entlang der separierbaren Achse nicht überlappen

Der AABB – AABB – Test

ist die Summe der

Abstände zwischen dem

Mittelpunkt der Objekte

entlang der

Kollisionsachse größer als

die Ausdehnung der

Bounding – Boxen, liegt

keine Kollision vor

Der AABB – AABB – Test

struct C_AABB{

D3DXVECTOR3 Mittelpunkt; D3DXVECTOR3 Ausdehnung;

};inline BOOL AABB_AABB_Collision(C_AABB* pBox1, C_AABB*

pBox2){ if(fabs(pBox2->Mittelpunkt.x - pBox1->Mittelpunkt.x) > pBox2->Ausdehnung.x + pBox1->Ausdehnung.x) return FALSE;if(fabs(pBox2->Mittelpunkt.y - pBox1->Mittelpunkt.y) > pBox2->Ausdehnung.y + pBox1->Ausdehnung.y) return FALSE;if(fabs(pBox2->Mittelpunkt.z - pBox1->Mittelpunkt.z) > pBox2->Ausdehnung.z + pBox1->Ausdehnung.z) return FALSE; return TRUE;}

Kollisionsausschlussmethoden

• Ziel ist die Optimierung der Performance• Warum ist dies notwendig?

bei einer großen Anzahl an Objekten müssen theoretisch permanent alle Objekte paarweise auf Kollisionen getestet werden

bei n Objekten wären dies n*(n-1)/2 Testdurchläufe bsw. 4950 Tests bei 100 Objekten

somit ist die Verwendung effizienter Ausschlussmethoden sinnvoll

Kollisionsausschlussmethoden

• eine Kollisionsprüfung zweier Objekte kann vermieden werden, wenn: gerade eine Kollision stattgefunden hat => für den aktuellen

Testdurchlauf ist eine Prüfung erst dann wieder notwendig, wenn eines der Objekte mit einem 3. Objekt erneut kollidiert ist

sich die Kollision im Blickfeld des Spielers abspielt => Blickfeld von 90° => ca. ¼ der Objekte können überhaupt wahrgenommen werden

die Entfernung zum Spieler sehr groß ist => ausbleibender Kollisionstest wird in den meisten Fällen nicht wahrgenommen

Kollisionsausschlussmethoden

• partielle Kollisionsüberprüfung pro Frame läuft das Spiel mit bsw. 50 fps, ist es eigentlich unnötig für jeden

Frame alle möglichen Kollisionen zu überprüfen speziell bei langsamen Objekten wird dies deutlich darum werden in solchen Fällen häufig nur 25% - 50% aller

möglichen Kollisionen getestet

• Begrenzte Treffertests selbst bei einer Schlacht mit vielen Schiffen ist es unnötig, für

jedes Waffenobjekt Kollisionen zu testen speziell zielsuchende Objekte benötigen eigentlich nur Tests mit

dem Zielobjekt => sehr unwahrscheinlich, dass auf dem Weg ein anderes Objekt getroffen wird

bei manueller Zielerfassung müssen nur die Objekte getestet werden, die im Blickfeld des Spielers liegen => Sichtbarkeitstest

Sektorisierung der Spielwelt

• Prinzip:

Kollisionstests werden nur innerhalb eines Sektors durchgeführt

• Art der Sektorisierung ist abhängig vom Spielgenre 2D – Sektorisierung bei Terrain – Games 3D – Sektorisierung bei bsw. Space – Simulationen

Sektorisierung der Spielwelt

Sektorisierung der Spielwelt

• Problem:

Es kann vorkommen, dass die Bounding – Sphäre eines Objekts über Sektorgrenzen hinausreicht

• Lösung: die Objekt – ID des Objekts wird in die Listen aller

Sektoren geschrieben, in die die Bounding – Sphäre hineinreicht

dies spart überflüssige Kollisionstests zwischen den Objekten eines Sektors mit benachbarten Sektoren

Sektorisierung der Spielewelt

Sektor zu Position (-1 / -5)

long SpaltenNr = (-1 + 6)/4 = 1;

long ZeilenNr = (6 – (- 5))/4 = 2

long SektorNr = 2 * 3 + 1 = 7

Für 3D – Sektoren ergänzt man

dieses Schema Schema um eine

zusätzliche Zeile zur Berücksichtigung

der y – Komponente.

Portale

• bei Indoor – Games bietet sich eine Kollisionsüberprüfung Raum für Raum an

• Übergang von Raum zu Raum erfolgt durch Portale• wird das Portal zwischen Raum A und Raum B

überschritten, weiß man automatisch, dass sich der Spieler nun in Raum B befindet

• Portal ist eine Fläche => mit Hilfe der Flächennormalen und dem Skalarprodukt des Differenzvektors zwischen Objekt – und Portalmittelpunkt kann man feststellen, ob sich der Spieler vor oder hinter dem Portal befindet

Portale

9000 ba

Es gilt:

der Winkel zwischen n und s – o

ist also entscheidend für das

Vorzeichen des Skalarprodukts

180900 ba

Portale

EndeFragen?