Das bekannte Programm zur optimalen Vorbereitung auf die theoretische Führerscheinprüfung
Analytische Geometrie für Spieleentwickler
Autor/Einsender:   Nico Schertler
Anregungen/Tipps an: Nico Schertler
Für viele Aktionen bei Spielen ist eine Berechnung von Positionen, Geschwindigkeiten usw. notwendig. Diese ist im eindimensionalen Raum – sprich der Bewegung o.Ä. auf einer einzigen Linie – relativ einfach. Etwas komplizierter wird das Ganze, wenn sich etwas in einer Ebene, also im zweidimensionalen Raum, bewegen soll. Und gar unmöglich wird die Berechnung für viele, wenn die Bewegung frei im Raum stattfindet. Dabei ist vieles gar nicht so schwer, wenn man ein paar Grundlagen kennt. Diese sollen im Nachfolgenden näher gebracht werden.
Vektoren
Vektoren sind eine praktische Sache. So ziemlich alles kann man damit berechnen. Das Problem ist, so ziemlich alles kann man auch als Vektoren ansehen. Deswegen beschränken wir uns nur auf die für die Spiele-Programmierung wesentlichen Vektoren, nämlich den rationalen. Diese lassen sich recht anschaulich definieren (man beachte, dass alle weiteren Definitionen nicht unbedingt allgemein gültig sind, sondern sich auf die Spiele-Programmierung beziehen):
Vektoren sind Klassen von Pfeilen, die durch ihre Länge, Richtung und Richtungssinn bestimmt werden.
Ich denke, was ein Pfeil ist, ist jedem klar. Die Länge wohl auch. Wo aber liegt der Unterschied zwischen Richtung und Richtungssinn? Die Richtung ist einfach nur eine Gerade, auf der der Vektor liegt. Der Richtungssinn gibt darüber hinaus noch an, ob der Vektor nach vorn oder nach hinten gerichtet ist.
Die hier abgebildeten Vektoren haben also die gleiche Richtung, aber einen
entgegengesetzten Richtungssinn.

Dann wäre da noch die Sache mit den Klassen … Die klassifizierenden Merkmale von Vektoren sind oben aufgeführt. Darunter fehlt aber ein Merkmal, das Pfeile charakterisiert. Nämlich der Anfangspunkt. Vektoren haben einfach keinen. Man kann sie da hinschieben, wo man sie gerade braucht. Oftmals werden sie an den Koordinatenursprung verschoben. Solche Vektoren heißen Ortsvektoren. Und warum? Weil sie auf einen Ort im Koordinatensystem zeigen. Also kann man mit Vektoren schon mal ganz gut Positionen darstellen. Apropos Darstellung, wie werden eigentlich Vektoren geschrieben? Erst einmal wird ein Vektor in seine Bestandteile entsprechend des Koordinatensystems zerlegt. Bei zweidimensionalen Koordinatensystemen also, wie lang ist der Vektor entlang der x-Achse und wie hoch entlang der y-Achse. Folgendes Beispiel verdeutlicht das:

Der Pfeil erstreckt sich über 2 Einheiten entlang der x-Achse und 4 Einheiten entlang der y-Achse. Diese Bestandteile werden dann in Klammern übereinander geschrieben. Ein Pfeil über der Variablen verdeutlicht, dass es sich um einen Vektor handelt. Das ist aber eigentlich nicht nötig, da wie bereits erwähnt, alles als Vektor betrachtet werden kann:

Diese Art der Schreibweise heißt Koordinatenschreibweise, dabei bilden die Bestandteile die Koordinaten. Die Länge des Vektors lässt sich ganz einfach mit dem Satz des Pythagoras ausrechnen. Denn x-Achse und y-Achse sind senkrecht aufeinander. Die Hypotenuse in dem rechtwinkligen Dreieck ist also die gesuchte Länge, die beiden Katheten bilden die Bestandteile:
Das gleiche gilt für mehrdimensionale Vektoren:
Die Länge des Vektors wird auch Betrag oder Norm genannt. Um die Norm eines Vektors anzugeben, wird der Vektor in doppelte senkrechte Linien eingefasst (s.o.). DirectX stellt die Funktion Vector.Length bereit, die die Länge bereits ausrechnet.
Rechnen mit Vektoren
Grundlegend sind für Vektoren zwei Rechenarten definiert. Die Addition zweier Vektoren und die Multiplikation eines Vektors mit einem Skalar, also mit einer Zahl:
Man beachte, dass die Länge der Summe zweier Vektoren nicht unbedingt die Summe der Längen der beiden Vektoren ist. Dies ist nur der Fall, wenn beide Vektoren in dieselbe Richtung zeigen und denselben Richtungssinn haben. Außerdem kann man recht gut erkennen, dass der Vektor b von a nach (a+b) zeigt. Er ist der Differenzvektor von (a+b) und a. Zur besseren Erklärung, nennen wir den Vektor a+b=c. Es gilt dann:
Um den Abstand zweier Punkte zu berechnen, kann man also die Ortsvektoren der beiden Punkte subtrahieren und die Länge des Differenzvektors berechnen.
Bei der Skalarmultiplikation von Vektoren erzielt man eine Skalierung. Die Richtung wird beibehalten. Ist der Skalar positiv, ändert sich der Richtungssinn auch nicht. Bei negativen Skalaren kehrt sich dieser um. Eine Division ist formal nicht definiert. Hierfür benutzt man die Multiplikation mit dem Reziproke. Will man also einen Vektor halbieren, multipliziert man ihn mit ½.
Eine weitere interessante Sache sind Einheitsvektoren. Einheitsvektoren sind Vektoren der Länge 1. Wenn man einen solchen hat, kann man einen Vektor sehr einfach auf eine beliebige Länge skalieren, nämlich indem man ihn mit dieser Länge multipliziert. Hiermit erhalten wir einen Einheitsvektor e aus einem Vektor v:
Ein Einheitsvektor wird also berechnet, indem der Vektor mit dem Reziproke seiner Länge multipliziert wird.
Lineare Abhängigkeit
Zwei Vektoren können auf Parallelität geprüft werden, indem geprüft wird, ob es einen Faktor k gibt, sodass v2 = k.* v1 . Vielleicht fragt sich jetzt der ein oder andere, warum diese Gleichung keine Lösung haben sollte, wir dividieren einfach durch v1 und schon haben wir die Lösung. Aber Moment … Eine Division Vektor durch Vektor ist nicht definiert. Stattdessen müssen wir die Gleichung in ihre Koordinaten aufteilen. Also bei einem zweidimensionalen Vektor in diese beiden:
Aus der ersten Gleichung erhält man schon mal ein k, für das diese gilt. Entweder unendlich viele, genau eines oder gar keines. Letzteres passiert zum Beispiel in dem Fall 2 = k * 0. Es gibt hier offensichtlich keine Lösung für k. Haben wir jedoch eine Lösung gefunden, prüfen wir diese noch mit der zweiten Gleichung und können so feststellen, ob die beiden Vektoren parallel sind. Sind sie es, sind sie linear abhängig. Das heißt, jeder der Vektoren kann durch Linearkombinationen der anderen Vektoren dargestellt werden. Linearkombinationen sind alle Summen der skalierten Vektoren. Die Linearkombinationen von zwei Vektoren v1 und v2 sind demnach k1 * v1 + k2 * v2 für beliebige Koeffizienten k. Sind zwei Vektoren linear abhängig, lässt sich also jeder der beiden durch Linearkombination des anderen darstellen, also durch Skalierung des anderen, also sind sie parallel.
Man kann auch drei Vektoren auf lineare Abhängigkeit prüfen, indem man folgendes Gleichungssystem in seine Koordinaten aufspaltet und löst:
Erhält man eine Lösung (wobei nicht alle k 0 sein dürfen), sind die Vektoren linear abhängig. Was bedeutet das für die drei Vektoren? Betrachtet man sie als Ortsvektoren, liegen alle in einer Ebene.
Das Skalarprodukt
Das Skalarprodukt ist eine definierte Rechenoperation zwischen zwei Vektoren. Als Ergebnis hat sie ein Skalar, also eine Zahl. Es wird berechnet, in dem die Koordinaten der beiden Vektoren paarweise multipliziert und anschließend addiert werden:
DirectX stellt dafür die Funktion Vector.Dot zur Verfügung.
Bildet man das Skalarprodukt eines Vektors mit sich selbst, erhält man das Quadrat seiner Länge:
Das Skalarprodukt findet seine Anwendung in der Berechnung von Winkeln zwischen zwei Vektoren mit gleichem Anfangspunkt:

Häufig werden ortogonale Vektoren benötigt, also solche, die rechtwinklig auf anderen stehen. Da der Kosinus von 90° = 0 ist, muss man dazu „einfach “ einen Vektor finden, dessen Skalarprodukt mit dem vorhandenen Vektor = 0 ist. Im dreidimensionalen gibt es zu einem Vektor unendlich viele, die
orthogonal dazu sind. Lässt man dazu noch die weg, die nur durch Skalierung anderer Vektoren entstehen, bleiben immer noch unendlich viele. Meistens reicht es, einen davon zu suchen. Also nehmen wir einen möglichst einfachen, beispielsweise den, mit der Z-Koordinate 0. Zum Beispiel suchen wir einen zu (5 | -2 | 8) orthogonalen Vektor. Die Z-Koordinate soll 0 sein, also bleibt für das Skalarprodukt:

Die einfachste Lösung dazu wäre {x=2, y=5}. Also haben wir unseren orthogonalen Vektor:
Eine weitere Anwendung des Skalarprodukts ist die Berechnung von Beleuchtungen. Nehmen wir an, eine Fläche wird von einer bestimmten Richtung B aus beleuchtet. Das Normal sei N. Und die Fläche habe eine bestimmte Helligkeit H. Dann ist die sichtbare Helligkeit abhängig von dem Winkel zwischen Normal und Beleuchtungsvektor. Um genau zu sein von dessen Kosinus. Bei Beleuchtung von oben bleibt die Helligkeit unverändert, bei 90° wird sie schwarz. Also ist die sichtbare Helligkeit:

Ein weiteres Produkt – Das Kreuzprodukt
Was aber, wenn wir einen zu zwei Vektoren orthogonalen Vektor suchen? Die eine Möglichkeit, wäre, ein Gleichungssystem aufzustellen. Einfacher geht es mit dem Kreuzprodukt:
Das sieht ja ziemlich kompliziert aus, ist es aber eigentlich nicht wirklich. Es gibt eine nette Eselsbrücke, wie man sich diese Definition merken kann. Da aber DirectX mit der Funktion Vector.Cross das Kreuzprodukt bereits ausrechnen kann, spar ich mir das an dieser Stelle.
Was macht denn nun das Kreuzprodukt? Vom bloßen Hinsehen lässt sich das sicher schwer sagen. Wie schon gesagt entsteht ein Vektor, der orthogonal zu den beiden Ausgangsvektoren ist. Zusätzlich hat er noch die Eigenschaft, dass seine Länge genau dem Flächeninhalt des von den beiden Ausgangsvektoren aufgespannten Parallelogramms entspricht. Aber das nur am Rande. Anwendung findet das Kreuzprodukt zum Beispiel bei der Berechnung von Normalen einer Landschaft.
Meistens wird ein right-handed Koordinatensystem benutzt. Das heißt, wenn der Daumen der rechten Hand in die positive x-Richtung zeigt, der Zeigefinger in positive y-Richtung, dann zeigt der Mittelfinger in positive z-Richtung. Natürlich muss man die Finger so anordnen, dass jeweils die rechten Winkel passen. Bei left-handed Koordinatensystemen analog mit der linken Hand. Und genau mit dieser Hand, mit der man das Koordinatensystem darstellen kann, kann man auch das Ergebnis des Kreuzproduktes darstellen: Daumen erster Operand, Zeigefinger zweiter Operand. Dann zeigt das Ergebnis so wie der Mittelfinger. Natürlich im rechten Winkel zu beiden Operanden.
Beschreibung von geometrischen Objekten
Geraden
Skaliert man einen Vektor schrittweise bis ins unendliche, erhält man eine Gerade durch den Koordinatenursprung mit der Richtung des Vektors. Soll die Gerade nicht durch den Ursprung gehen, verschiebt man sie einfach. Also können alle Punkte auf einer Geraden folgendermaßen dargestellt werden:
Dabei ist s der sogenannte Stützvektor und r der Richtungsvektor. 

Sind zwei Gerade durch

gegeben, so kann man (falls vorhanden) einen Punkt finden, der zu beiden Geraden gehört, ihr Schnittpunkt:

Löst man dieses koordinatenweise, kann man die Lösung in eine der beiden Ausgangsgleichungen einsetzen und man erhält den Schnittpunkt. Gibt es keine Lösung, gibt es keinen Schnittpunkt, gibt es unendlich viele, sind die Geraden identisch. Manchmal ist es erforderlich, zu einer Geraden eine parallele mit einem bestimmten Abstand d zu finden. Damit sie parallel ist, kann der Richtungsvektor übernommen werden. Brauchen wir also nur noch einen neuen Stützvektor. Dieser soll den Abstand d von der Gerade haben. Also suchen wir einen zu dem Richtungsvektor orthogonalen Einheitsvektor, multiplizieren ihn mit d und addieren ihn zu dem ursprünglichen Stützvektor und fertig ist der neue Stützvektor.
Je nachdem, was man für Werte für den Parameter t zulässt, kann man auch Strahlen beschreiben (t³0) oder auch Strecken (0£t£1).
Ebenen
Eine Ebene kann man herstellen, indem man eine Gerade in eine bestimmte Richtung schrittweise bis ins Unendliche verschiebt. Das heißt, wir brauchen für unsere Gleichung einfach einen zweiten Richtungsvektor:
Schnittpunkte zwischen Geraden und Ebenen kann man wie schon bei Geraden mit Geraden berechnen, indem die beiden Gleichungen gleichgesetzt werden. Ein Beispiel, wo eine solche Berechnung nötig ist, ist die Berechnung der Mausposition auf einer Ebene. Durch die Projektion der Maus in das Welt-Koordinaten-System erhält man nicht einen einzigen Punkt, sondern eine ganze Menge, die alle auf einer Geraden liegen. Hat man zwei solche Punkte, kann man sich eine Geradengleichung zurechtbasteln. Der Stützvektor ist der erste Punkt und der Richtungsvektor die Differenz von zweitem und ersten Punkt. Man stellt das Gleichungssystem mit der gegebenen Ebene auf, löst es, setzt die Lösung in der Geradengleichung ein und man erhält den gesuchten Punkt. Hat man keine Ebene, auf die geklickt werden soll, sondern eine dreidimensionale Landschaft, wird diese in einzelne Dreiecke zerlegt und für jedes dieser Dreiecke geprüft, ob die Gerade das Dreieck schneidet. Die Gerade schneidet ein Dreieck, wenn die Parameter der Richtungsvektoren des Dreiecks folgende Bedingungen erfüllen:
  1. Beide Parameter sind positiv
  2. Die Summe der Parameter ist kleiner oder gleich 1
Würde man beide Parameter bis 1 erlauben, ergäbe sich nicht das gesuchte Dreieck, sondern ein Parallelogramm. (Rot in der Skizze die Richtungsvektoren jeweils mit dem Parameter 0.5 und grün mit 0.25 / 0.75)
Kreise / Kugeln
Kreise im zweidimensionalen bzw. Kugeln im dreidimensionalen Raum zeichnen sich dadurch aus, dass ihre Punkte alle einen konstanten Abstand zum Mittelpunkt haben, genannt Radius. Also kann man diese so darstellen:
Ob sich ein Punkt in einem Kreis befindet kann man so auch ganz einfach herausfinden, indem man den Abstand des Punktes zum Mittelpunkt berechnet und mit dem Radius vergleicht.
Bei Geraden kann man das sehr ähnlich machen: Man berechnet den Abstand des Mittelpunktes zur Geraden. Aber wie? Als erstes verschieben wir den Punkt und die Gerade zum Koordinatenursprung indem wir von beiden den Stützvektor abziehen. Der Abstand ändert sich dabei natürlich nicht. Als nächstes projizieren wir den modifizierten Ortsvektor des Mittelpunktes orthogonal auf den verbleibenden Richtungsvektor:

Der Abstand des projizierten Vektors und des modifizierten
Mittelpunktes ist genau der Abstand des Punkts von der Gerade:

Ist der Abstand kleiner als der Radius, schneidet die Gerade den Kreis. Ist er gleich dem Radius, ist die Gerade eine Tangente an dem Kreis.

Matrizen
Durch Matrizen können lineare Abbildungen dargestellt werden. Um jetzt nicht zu tief in die Mathematik einzudringen, kann man kurz sagen: Durch Matrizen können Vektoren transformiert werden. Dazu werden die Matrizen mit dem Vektor multipliziert. Besonders günstig sind quadratische Matrizen, denn dann hat der entstehende Vektor die gleiche Dimension wie der Ausgangsvektor. Bei dreidimensionalen Vektoren bräuchte man also eine 3x3 Matrix. Hm … DirectX verwendet doch 4x4 Matrizen, wie soll das denn gehen? Naja, 3-dimensionale Vektoren können nicht mit 4x4 Matrizen multipliziert werden. Aber das macht ja DirectX auch gar nicht. Durch „einfache“ Matrixmultiplikation können nur lineare Abbildungen dargestellt werden – also zum Beispiel Rotationen, Skalierungen und Scherungen. Verschiebungen sind damit nicht möglich. Das ist eine sogenannte affine Transformation. Um diese durchführen zu können, wird im homogenen Vektorraum gerechnet. Der Vektor bekommt eine weitere Komponente – die w-Komponente. Bei Punkten ist diese 1 und bei Richtungsvektoren 0. Die Matrizen erhalten genauso eine Spalte und Zeile mehr. Verschiebungen können so in der letzen Spalte einer Matrix untergebracht werden. Diese wird also bei Punkten einfach zum Vektor hinzugefügt und bei Richtungsvektoren ignoriert.
Außerdem ist noch ein weiterer Transformationstyp vorhanden – die perspektivischen Transformationen. Sie dienen – wie der Name schon sagt – zu perspektivischen Verzerrungen. Grundlage dessen ist, wie DirectX die letztendliche Position eines Vektors berechnet. Nämlich durch Division aller Komponenten durch die w-Komponente. In der letzten Zeile einer Matrix kann also die w-Komponente in Abhängigkeit von den anderen Komponenten verändert werden. Bei geeigneten Werten einsteht eine perspektivische Transformation.
Transformationen können durch Multiplikation der Matrizen kombiniert werden. Dabei ist zu beachten, dass die Matrizenmultiplikation nicht kommutativ ist, also die Reihenfolge eine Rolle spielt. Anscheinend führt erst eine Translation und anschließende Rotation (um den Koordinatenursprung) zu einem anderen Ergebnis als eine Rotation gefolgt von einer Translation.
DirectX speichert Matrizen nicht wie in der Mathematik Zeile für Zeile, sondern Spalte für Spalte. Also die transponierte Matrix. Dadurch ist es auch möglich, die entsprechenden Matrizen in der Reihenfolge ihrer Transformation zu multiplizieren, denn bei der Transposition kehrt sich die Multiplikation jeweils um. Die Reihenfolge bei einer Transformation, die erst eine Rotation R, dann eine Translation T und schließlich eine Skalierung S ausführt, ist also: R*T*S. Wären die Matrizen nicht transponiert, würde die Reihenfolge andersrum lauten.
DirectX bietet für so ziemlich jede Grundtransformation Funktionen, die diese Matrizen berechnen. Deswegen will ich nicht weiter darauf eingehen. 
Mit diesen Grundlagen sollte ein Großteil der benötigten Berechnungen hergeleitet werden können. Viel Spaß beim Programmieren.
Bei Fragen zu diesem Tutorial nutzen Sie bitte unser DirectX-Forum.


Zum Seitenanfang

Startseite | VB-/VBA-Tipps | Projekte | Tutorials | API-Referenz | Komponenten | Bücherecke | Gewinnspiele | VB-/VBA-Forum | DirectX-Forum | VB.Net | .Net-Forum | Foren-Archiv | Chat | Spielplatz | Links | Suchen | Stichwortverzeichnis | Feedback | Impressum

Seite empfehlen Bug-Report
Letzte Aktualisierung: Sonntag, 4. Juli 2010