4.
Jonglieren – oder: So hantiert man mit dreidimensionalen Objekten

Aber wie werden die Punkte miteinander verbunden? Klar, mit Linien. Ohne hier allzu sehr in die Tiefe gehen zu wollen, soll gesagt werden, dass dieses Problem keineswegs trivial ist. In der Mathematik ist eine Linie unendlich genau definiert. Diese Linie muss nun auf ein Raster gelegt werden – genau das macht ein Rasterizer. Der Bildschirm besteht aus einem Pixelraster. Um darauf eine Linie zu zeichnen, muss geklärt werden, welches Pixel denn nun gefärbt werden soll, und welches nicht. Ein einfacher Rasterizer für Linien ist der Bresenham-Algorithmus. Dieser Algorithmus ist in den meisten Programmierungs-Hochsprachen bereits implementiert, so dass man dem Compiler einfach sagen kann "verbinde Punkt (x,y) mit Punkt (v,w)".

Projiziert man also alle vier Punkte des Grundquadrats sowie jeweils die drei Punkte der beiden Dreiecke aus dem dreidimensionalen Raum auf die zweidimensionale Ebene und verbindet die so erhaltenen zweidimensionalen Punkte gemäß der entsprechenden Vorschrift miteinander, so erhält man die gewünschte Pyramide:

Jetzt soll sich die Pyramide auch noch bewegen. Grundsätzlich gibt es zwei Arten von Bewegung: Translation (Verschiebung) und Rotation. Allgemein sollten diese Operationen natürlich auf die dreidimensionalen Vektoren angewendet werden. Für die Translation wird zu einem Vektor, der verschoben werden soll, einfach ein Richtungsvektor aufaddiert. Soll etwa die gesamte Pyramide um zwei Einheiten auf der X-Achse verschoben werden, ergibt sich beispielsweise für:

Macht man das für alle Punkte, kann man das ganze Mesh durch die Gegend schieben.

Für Rotationen der Punkte um einen Winkel Alpha müssen die Vektoren mit Rotationsmatrizen multipliziert werden. Für alle drei Rotationsachsen sind jeweils Matrizen definiert, hier exemplarisch die Rotationsmatrix, die einen Punkt im Winkel Alpha um die X-Achse dreht:

Bei den Matrizen handelt es sich um 3x3-Matrizen. Multipliziert man also einen dreidimensionalen Vektor mit einer solchen Matrix, ist das Ergebnis wieder ein dreidimensionaler Vektor – so wie es sein sollte. Das Ergebnis kann dann wieder ganz normal projiziert werden. Multipliziert man alle Punkte eines Mesh nacheinander mit einer Rotationsmatrix, dreht sich das Objekt im Raum.

5.
Ausblick – oder: Was die "Großen" können

So weit, so gut. Ergänzt man die hier vorgestellte Logik noch um einen Loader für Mesh-files, also Dateien, mit denen Drahtgittermodelle gespeichert werden (z.B. das OBJ-Format oder das XML-basierte X-Format von Direct3D), kann man schon einen kleinen Renderer programmieren. Ein Ergebnis könnte dann etwa so aussehen:

Zu einem Computerspiel ist es aber noch weit:

1. Zumindest sollte in einen Framebuffer gezeichnet werden, statt direkt auf den Bildschirm. Zeichnet man die Szenerie direkt auf den Bildschirm, so sieht man das: Das Bild baut sich nach und nach auf, es kommt zu unschönen Flimmereffekten. Um das zu vermeiden, wird das Bild erst in den Speicher (nämlich den Framebuffer) gezeichnet. Das alte Bild wird so lange angezeigt, bis das neue Bild fertig in den Framebuffer gezeichnet ist. Erst dann wird der gesamte Framebuffer auf den Bildschirm kopiert. Dann wird der Framebuffer gelöscht und ein neues Bild kann in den Buffer gezeichnet werden.

2. Es wäre doch schön, wenn die Enterprise nicht durchsichtig wäre, sondern die einzelnen Polygone ausgefüllt wären. Dies zu können, ist wieder einmal keineswegs trivial. Es muss vermieden werden, dass weiter "vorne" liegende Polygone teilweise ausgefüllt werden mit Farben, die weiter "hinten" liegenden Polygonen zugewiesen werden sollten. Weiter "hinten" liegende Polygone, die von weiter "vorne" liegenden Polygonen verdeckt werden (und die damit gar nicht zu sehen sind), sollten am besten gar nicht gezeichnet werden, um Rechenleistung zu sparen.

Der Anspruch der Flächenfüllung und der Anspruch der "hidden surface removal" führen beide zum Sichtbarkeitsproblem. Dieses eigentlich bis heute nicht vollständig gelöste Problem wird speicherfressend und ineffizient, aber doch zuverlässig mittels eines Z-Buffers gelöst. Hierbei wird ein gerendertes Polygon nur dann in den Framebuffer gezeichnet, wenn es an der betreffenden Stelle nicht weiter "hinten" liegt als ein anderes Polygon an derselben Stelle. Hinweis: "Hidden surface removal" ist damit noch nicht automatisch erreicht. Noch immer muss jedes Polygon gerendert werden, um festzustellen, ob es denn wirklich gezeichnet werden muss. Weitere Tricks sind erforderlich.

3. Der Szene Beleuchtung und Schattierung hinzuzufügen, um einen noch realistischeren Eindruck zu erhalten, ist mit der hier vorgestellten Technik nicht so einfach; beim Raytracing hingegen passiert beides praktisch automatisch. Ausgefeilte Algorithmen ermöglichen Licht und Schatten auch bei der Polygongrafik, beides benötigt aber massive Berechnungsleistung.

4. Natürlich sollen Polygone auch texturiert werden. Nach Sortieren der Z-Order der Polygone mit dem Z-Buffer passiert folgendes: Die als Textur verwendete Bitmap muss perspektivisch korrekt verzerrt und beschnitten werden und anschließend an die passende Stelle auf der zweidimensionalen Szenerie aufgetragen werden. Soll die Textur dabei bilinear, trilinear oder gar anisotrop gefiltert werden, stehen wieder einmal viele Berechnungen an.

5. All diese Berechnungen sollten spätestens dann von dedizierter Hardware ausgeführt werden. Spricht man von hardwarebeschleunigter Grafik, setzt man praktisch selbstverständlich auf eine Hardware-API wie Direct3D oder OpenGL. Funktionen wie Mesh-Loader, Rotation und Translation, Z-Buffer, Texturierung, Beleuchtung und Schattierung oder Texturfilterung muss man dann nicht mehr selbst schreiben. Alles wird praktisch mitgeliefert. Eine Enterprise kann dann auch so aussehen:

6. Jedem Polygon wird ein sogenannter Normalenvektor zugeordnet. Dies ist ein (gedachter) Vektor, der rechtwinklig auf der Polygonfläche steht und sozusagen angibt, wo bei dem Polygon "vorne" ist. Diese Information ist wichtig für die Beleuchtung, aber auch, um Polygone, die von der Kamera weg zeigen (deren Rückseite man also eigentlich betrachten würde), gar nicht erst zeichnen zu müssen.

Ein letzter Hinweis: "Richtige" Renderer wie der von Direct3D gehen etwas anders als hier beschrieben an die Darstellung der Szenerie heran. Was ist denn, wenn nicht nur die Objekte, sondern auch die Kamera sich bewegt? Alle Objekte der Szenerie müssen dann im korrekten Winkel gedreht werden, und zwar so, dass auch der Eindruck der Position der Objekte im Raum zueinander gewahrt bleibt. Mit den einfachen Rotations- und Translationsmethoden, die hier vorgestellt wurden, ist das schwer zu realisieren.

In Direct3D wird eine Welt definiert, in die alle Objekte hineingepackt werden können. Objekte können beleuchtet und schattiert werden. Desweiteren gibt es eine virtuelle Kamera, die sich an einem bestimmten Punkt im Raum befindet und auf einen bestimmten Punkt im Raum blickt (Blickrichtung). Auch hier kann ein FOV definiert werden. Die Kamera kann frei bewegt und geschwenkt werden. Direct3D kümmert sich von selbst darum, dass Kamera und Welt stets konsistent zueinander bleiben, d.h. subjektive Rotation und Translation der Objekte etwa bei einer Kamerafahrt berechnet die API selbst.

Anhang
Programmieren – oder: So kann man's umsetzen

Zunächst sollte man sich das Leben leicht machen und einige Datentypen typisieren. Hier werden zunächst die Vektoren (oder „Vertices“) typisiert. Man beachte, dass die Koordinaten mit Gleitkommazahlen einfacher Genauigkeit definiert werden. Das sollte reichen, Grafikkarten rechnen in der Regel mit demselben Typ.

Aufbauend auf den Vertex-Typen können nun ganze Polygone definiert werden. Man beachte hier, dass Polygone nicht notwendigerweise aus drei Ecken bestehen müssen. Sie sind definiert als dynamische Arrays von (praktisch beliebig vielen) Vertices.

Schließlich sollte man die Projektions- und Rotationsmatrix definieren. Dies könnte in Form "echter" Matrizen erfolgen, also in Form mehrdimensionaler Arrays. Eine einfache Typisierung aus einzelnen Variablen tut es aber auch und ist in der Regel etwas schneller.

Als nächstes werden die Funktionen für Translation, Rotation und Projektion vorgestellt. Für jeden Durchlauf und innerhalb dessen für jedes Polygon muss das Ergebnis der Berechnung entsprechend der Anzahl der Vertices pro Polygon neu dimensioniert werden. Wie vorhin schon beschrieben kostet diese Flexibilität Performance.

Der simpelste Main-Loop sieht so aus. Es wird nichts getan, außer eben die Grafik zu berechnen. Es gibt auch keine Abbruchbedingung. Dem Loop muss ein Programmteil vorgeschaltet sein, der die Polygone mit Daten füttert (Mesh-Loader). Dies und einige simple Initialisierungen vorausgesetzt, kann es losgehen:

Schlusswort – oder: Was war. Was wird.

Dieser Artikel konnte und sollte keine Programmieranleitung und kein Mathematiktutorium darstellen. Er sollte einen Einblick geben in die grundlegende Funktionsweise und Mathematik hinter der Grafik-Technologie der Spiele, die wir heute so spielen. Wie weit die Polygongrafik noch reichen wird, muss die Zeit zeigen.

Möglicherweise ist sie in zehn Jahren vom Raytracing oder eine anderen Technik längst abgelöst und vergessen. Vielleicht ist aber auch in zehn Jahren das Raytracing immer noch genau so ein Luftschloss wie vor zehn Jahren. Momentan jedenfalls sitzt die Polygontechnik fest im Sattel, und so schnell wird sich das wohl auch nicht ändern.