Tag 4

Dreidimensionale Spielewelten

-Beschreibung der dreidimensionale Spielewelt durch Vektoren

-dreidimensionale Welttransformationen durch Matrizen

-schnelle Quadratwurzelberechnungen

-schnelle Berechnungen von Rotationsmatrizen

Die Themen heute:

Koordinatensysteme• Linkssystem -positive z-Achse zeigt in den Monitor hinein

y

z

x

DirectX -> Linkssystem!

• Rechtssystem -z-Achse zeigt in die entgegengesetzte Richtung

y

x

z

Das Vektorprodukt

Definition des Vektorproduktes:Das Vektorprodukt (auch Kreuzprodukt) zweier Vektoren a und b ergibt einen Vektor c ,der dazu noch senkrecht auf a und b steht.

IcI=IaI.IbI.sina

- bei Parallelität der Vektoren a und b verschwindet der Flächeninhalt-> IcI=0;

- bei Orthogonalität (orthogonal=senkrecht) nimmt c den maximalen möglichen Wert an

Das Vektorprodukt • ist der Winkel größer als 180°,zeigt c in die entgegengesetzte Richtung, die Fläche

erhält ein negatives Vorzeichen (der Sinuswert eines Winkels größer als 180° ist immer negativ )

• Idee:

anstatt mit einem Winkel größer als 180°,mit dem negativen Winkel arbeiten (Winkel-360°)

Das Vorzeichen des Winkels legt fest, in welcher Folge a und b miteinander multiplizier werden.

Da die Vektoren c1 und c2 antiparallel

sind, folgt:

c1+c2=0=a x b +b x a und somit

a x b= -b x a

Basisvektoren Der mathematische Begriff Basis bezeichnet in der linearen Algebra eine Teilmenge eines

Vektorraumes, mit deren Hilfe sich jeder Vektor des Raumes eindeutig durch Koordinaten beschreiben lässt.

Die Elemente einer Basis heißen Basisvektoren. Die Anzahl der Basisvektoren bestimmt die Dimension des Vektorraumes.

-In unseren Koordinatensystemen repräsentieren die drei zueinander senkrecht stehenden Achsen die Basisvektoren.

- Unter der Annahme, dass diese Vektore normiert sind, lassen sich alle Vektore als lineare Kombination der Basisvektoren aufschreiben.

Basisvektoren eines dreidimensionalen, rechtwinkligen Koordinatensystems: o Basisvektor, der die x-Achse repräsentiert: i=(1 0 0) o Basisvektor, der die y-Achse repräsentiert: j=(0 1 0) o Basisvektor, der die z-Achse repräsentiert: k=(0 0 1)

Beispiel für die Darstellung eines Vektors als lineare Kombination der Basisvektoren: (3 -2 5)=3*i + (-2)*j + 5*k

Berechnung des Vektorproduktes mit Hilfe von Determinanten

• Um eine Determinante ausrechnen zu können, benötigen wir den sog. Laplaceschen Entwicklungssatz

• eine Determinante wird solange in Unterdeterminanten zerlegt, bis letztlich nur noch Zahlen (1x1 Determinanten) übrig bleiben.

• Aus einer 3x3-Determinante werden im ersten Schritt drei 2x2-Determinanten und im zweiten Schritt werden aus jeder dieser 2x2-Determinanten zwei 1x1-Determinnten:

Berechnung des Vektorproduktes mit Hilfe von Determinanten

Und jetzt das gleiche noch einmal mit Zahlen:

Berechnung des Vektorproduktes mit Hilfe von Determinanten

Dreidimensionale Polarkoordinate (Kugelkoordinaten)

Daten für den Navigationscomputer

- der Raumschiff soll Kurs auf die Erde nehmen

- der Navigationscomputer legt folgende Daten vor:

30° nach rechts drehen; 40° nach oben drehen; 0,5 aU geradeaus fliegen

Der Navigationscomputer hat die Ortskoordinaten relativ zum Schiff in Form von dreidimensionale Polarkoordinaten gegeben.

In räumlichen Polarkoordinaten wird ein Punkt durch seinen Abstand vom Ursprung und durch zwei Winkel angegeben. (im Unterschied zur zweidimensionalen Polarkoordinatendarstellung, wo nur die Länge des Ortsvektors und einen Winkel benötigt werden)

Dreidimensionale Polarkoordinate:

x=Entfernung*cos(Vertikalwinkel)*sin(Horizontalwinkel)

y=Entfernung*sin(Vertikalwinkel)

z=Entfernung*cos(Vertikalwinkel)*cos(Horizontalwinkel)

Quadratwurzelberechnung

Quadratwurzeln müssen in einem Spie häufig berechnet werden im Zusammenhang mit Normierung und Längeberechnung von Vektoren

Problem:

Quadratwurzelberechnung beansprucht viel Prozessorleistung

Mögliche Lösung:

Entwicklung einer eigenen Quadratwurzel-Routine

Ein Iterationsverfahren für die Berechnung von Quadratwurzeln

Begriff:

Die Iteration (von lateinisch iterare, „wiederholen“) ist ein Begriff aus der numerischen Mathematik und bezeichnet eine Methode, sich der Lösung eines Rechenproblems schrittweise, aber zielgerichtet anzunähern. Sie besteht in der wiederholten Anwendung desselben Rechenverfahrens.

Quadratwurzelberechnung

Ausgangpunkt: das Heron-Verfahren für Wurzelziehung.

-x1 ist der Startwert der Rechnung

-x2 ergibt sich aus der vierten Gleichung

-x1‘ ist der Mittelwert von x1 und x2

-x1‘ wird jetzt als neuer Startwert verwendet

- die Rechnungen werden solange wiederholt ,bis die gewünschte Genauigkeit erreicht ist

Quadratwurzelberechnung

Eine Funktion für die Berechnung einer Quadratwurzel- der erste Versuch

Nachteil:

-Startwerte zu schlecht-> viele Iterations-

schritte notwendig

-Schleifenkonstruktion verlangsamt die

Berechnung zusätzlich

Quadratwurzelberechnung• Idee: - durch Iteration wird den reziproke Wert der gesuchten Quadratwurzel berechnet - die reziproke Quadratwurzel wird als Startwert in die Quadratwurzel-Routine eingesetzt

Eine Funktion für die Berechnung einer Quadratwurzel- der zweite Versuch

Vorteil: schon nach zwei Iterationsschritte ist die Quadratwurzel genügend genau bestimmtNachteil: Divisionen beanspruchen viel Rechenzeit!

Quadratwurzelberechnung• Unnötige Divisionen sollten immer, wenn möglich, vermieden werden.• Besser: eine Multiplikation mit dem inversen Element:

a/2.0f=0.5f*a

Zweites Näherungsverfahren für unsere Quadratwurzel-Routine, das ohne Division auskommt:

Implementation in der FastWurzelExact()-Funktion:

Funktionen für die Normierung und Längeberechnung von Vektoren

• Unter Verwendung der FastWurzelExact()-Funktion lässt sich jetzt eine Funktion für die Berechnung des Vektorbertrags schreiben. Die quadratische Länge des Vektors wird mittels der DirectX-Funktion D3DVec3LenghtSq() berechnen.

• Für die Normierung eines Vektors bietet sich der Einsatz von drei verschiedenen Funktionen an. Hier die Standartvariante:

Funktionen für die Normierung und Längeberechnung von Vektoren

• Nicht immer ist es erforderlich, einen Vektor exakt zu normieren. In diesem Fall bietet sich der Einsatz der FastWurzel()- Funktion an:

• Eine Funktion für Normierung eines noch nicht normierten Vektors:

Manipulation der 3D-Welt• Wichtigste Matrizen zur Manipulation der 2D-Welt schon bekannt -> Übertragen der Konzepten

auf die dreidimensionale Welt

• DirectX bietet die Funktion SetTransform() an, mit deren Hilfe nicht jeder Vertex einzeln transformiert werden soll. Als Argumente werden übergeben nur die Adresse der Transformationsmatrix und der Hinweis, dass sich die Transformation auf das Weltkoordinatensystem bezieht.

SetTransform(D3DTS_WORLD ,&TransformationsMatrix); Grafische Darstellung (der Renderprozess) erfolgt in der korrekten Größe (Skalierung),

Ausrichtung und Verschiebung.

Die Translationsmatrix für Bewegung im Raum

Eine Translationsmatrix lässt sich mit Hilfe der folgenden DirectX-Funktion erzeugen:

D3DMATRIX* D3DMatrixTranslation(D3DMATRIX* pOut, FLOAT x, FLOAT y, FLOAT z);

Manipulation der 3D-WeltDie Skalierungsmatrix

Eine Skalierungsmatrix lässt sich mit Hilfe der folgenden DirectX-Funktion erzeugen:

D3DMATRIX* D3DMatrixScaling(D3DMATRIX* pOut, FLOAT sx, FLOAT sy, FLOAT sz);

Die Einheitsmatrix Alle Transformationsmatrizen werden stets als Einheitsmatrizen initialisiert.

Eine Einheitsmatrix lässt sich mit Hilfe der folgenden DirectX-Funktion erzeugen:

D3DMATRIX* D3DMatrixIdentity(D3DMATRIX* pOut);

Transformation eines Vektors durch eine Matrix• Eine Funktion für die Multiplikation eines Vektors mit einer Matrix

• DirectX-Funktion für die Transformation eines Vektors:

D3DVECTOR3* D3DVec3TransformCoord(D3DXVECTOR3* pOut,

const D3DXVECTOR3* pV,

const D3DMATRIX* pM);

• Eine Funktion für die Multiplikation eines Vektors mit einer Rotationsmatrix

Rotationsmatrizen für die Drehung im Raum• Rotation um die x-Achse xneu=x yneu=ycosa –zsina zneu=ysina+zcosa Zugehörige Matrix Rx:

Die x-Achsen-Rotationsmatrix lässt sich mit Hilfe der Folgenden DirectX-Funktion erzeugen: D3DXMATRIX* D3DXMatrixRotationX(D3DXMATRIX* pOut, FLOAT Angle)

• Rotation um die y-Achse xneu=xcosa+zsina yneu=y zneu=-xsina+zcosa Zugehörige Matrix Ry:

Die y-Achsen-Rotationsmatrix lässt sich mit Hilfe der Folgenden DirectX-Funktion erzeugen: D3DXMATRIX* D3DXMatrixRotationY(D3DXMATRIX* pOut, FLOAT Angle)

Rotationsmatrizen für die Drehung im Raum• Rotation um die z-Achse

xneu=xcosa-ysina

yneu=xsina +ycosa

zneu=z

Zugehörige Matrix Rz:

Die x-Achsen-Rotationsmatrix lässt sich mit Hilfe der Folgenden DirectX-Funktion erzeugen:

D3DXMATRIX* D3DXMatrixRotationZ(D3DXMATRIX* pOut, FLOAT Angle)

Rotation um eine beliebige Achse

Notwendig: Transformation der Rotationsachse auf eine der drei Achsen, für die die Rotationsmatrix schon bekannt ist. (z.B. z-Achse)

Anschließend wird die behelfsmäßige Rotationsachse wieder in die ursprüngliche Rotationsachse zurücktransformiert

Hiefür benötigt man die inversen x- und y-Achsen-Rotationsmatrizen:

Rotationsmatrizen für die Drehung im Raum

Frame-Rotationsmatrizen und Gesamtrotationsmatrizen

Bei der Drehung eines Objektes gilt es, zwischen zwei Arten von Rotationsmatrizen zu unterscheiden:

-Gesamtrotationsmatrix- beschreibt die endgültige Ausrichtung eines Objektes aus dessen Anfangsorientierung heraus

-Frame-Rotationsmatrix- beschreibt nur die Drehung während des aktuellen Frames

Die neue Gesamtrotationsmatrix nach einer Framedrehung erhält man durch die Multiplikation der Frame-Rotationsmatrix mit der Gesamtrotationsmatrix des vorangegangenen Frames. Dabei ist die Multiplikationsreihenfolge abhängig vom gegebenen Problem!

Beispiel 1: Rotation von Planeten, Wolken, Asteroiden

R (neue Rotationsmatrix)= R (alte Rotationsmatrix)* R( für die Drehung pro Frame)

Beispiel 2: Simulation von Kurvenbewegung eines Raumschiffs

R (neue Rotationsmatrix)= R( für die Drehung pro Frame)* R (alte Rotationsmatrix)

Wichtig: zu Beginn des Spiels muss die Gesamtrotationsmatrix R als Einheitsmatrix initialisiert werden!

Simulation der Bewegung eines Asteroiden

Simulation der Bewegung eines Asteroiden

Schnelle Berechnung von Rotationsmatrizen

DirectX stellt für die Erzeugung von Rotationsmatrizen eine Reihe von Funktionen zur Verfügung.

• Problem: bei der Berechnung von Sinus- und Kosinuswerte kommt eine relativ langsame API-Funktion zum Einsatz

• Mögliche Lösung: Einsetzen von Look-up-Tabellen für die schnelle Berechnung von Sinus- und Kosinuswerten.

Anstatt Look-up-Tabellen für alle Werte von -360° bis +360° zu erstellen, kann man die negativen Winkel in positive umwandeln.

360°+negativer Winkel= positiver Winkel

Rotationsmatrizen mit gleichbleibendem Rotationswinkel

Wenn Rotationsmatrizen mit gleichbleibendem Rotationswinkel ständig benötigt werden, kann man diese Matrizen nur einmal erzeugen und dann immer wieder verwenden

Rotationsmatrizen mit Hilfe von vorberechneten Sinus- und Kosinuswerten erzeugen

- anstatt mit Winkeln, arbeiten mit vorberechneten Sinus- und Kosinuswerten

Cosinus symmetrische Funktion: cos(10°) =cos(-10°)

Sinus asymmetrische Funktion: -sin(10°)=sin(-10°)

Rotationsmatrizen mit Hilfe von vorberechneten Sinus- und Kosinuswerten erzeugen

Rotationsmatrizen für kleine Winkel• Objekte drehen sich in jedem Frame nur um einen kleinen Winkel• Etwa bis zu einem Winkel von 10° gilt folgende Näherung : (Maclaurin-Reihe)

sin(a)~a (Näherung bezieht sich auf Winkel im Bogenmaß)

cos(a)~1-0.5*a² (Näherung bezieht sich auf Winkel im Bogenmaß)