Sobald eine Diskussion um Grafikkarten losgeht, ist man ganz schnell auch bei Begriffen, die nicht mehr viel mit den Grafikkarten selbst zu tun haben, sondern mit dem, was Grafikkarten so bearbeiten: Polygone, Vektoren, Matrizen, Rasterizer, Grafikengines etc. Eine Grafikkarte ist eben immer nur Mittel zum Zweck, um etwas zu erreichen – in diesem Fall die Beschleunigung speziell der Grafikengine eines Spiels. Doch wie funktionieren heutige Grafikengines eigentlich? Hierzu soll dieser Artikel einen kurzen Einblick liefern ...
1.
Einleitung – oder: Historisches
(Spätestens) seitdem erste Computerspiele das Licht der Welt erblickten, musste Grafik auf den Bildschirm gezeichnet werden. Wenn man der Definition des Begriffs "Grafikengine" folgt, welchen die Wikipedia gibt, so ist eine Grafikengine [2]"ein mitunter eigenständiger Teil eines Computerprogramms oder einer Computer-Hardware, welcher für dessen Darstellung von Computergrafik zuständig ist […]". So gesehen hatten selbst Spiele wie Pong [3], Space Invaders [4] oder Pac-Man [5] Grafikengines.
Diese und auch fast alle anderen Spiele, die auf Homecomputern wie dem C64 [6] oder auf Konsolen wie dem NES [7] verfügbar waren, verwendeten 2D-Grafik. Dabei wurde praktisch alles "per Hand" gezeichnet: Hier eine Wolke, da ein Baum, dort ein Strichmännchen. Die dafür nötigen Grafiken wurden per Code erzeugt oder kamen aus Bitmaps. Außerdem kamen Sprites [8] zum Einsatz. Solche Spriteengines wurden immer weiter entwickelt, verbessert, verfeinert. Ihren Höhepunkt fanden sie vielleicht in Spielen wie denen der Turrican [9]-Reihe.
Auf späteren Systemen wie dem Amiga 500 [10] oder dem SNES [11] sollte jedoch nach und nach statt der mittlerweile althergebrachten, spritebasierten 2D-Grafik nun 3D-Grafik zum Einsatz kommen. Die Sprite-Technik war leistungsfähig, für 3D aber vollkommen ungeeignet. Gerade am SNES wurde das Dilemma deutlich: War die Hardware des SNES noch sehr auf Spritedarstellung getrimmt, zeigten doch Erfolge wie der des legendären Mario Kart, wie gut 3D bei den Spielern ankam.
Für eine "echte" 3D-Darstellung war die damalige Hardware jedoch viel zu langsam. Spieleentwickler begannen, das zu tun, was sie schon immer taten: Tricksen!
Auch am PC wurde getrickst, was das Zeug hielt: Es kamen ganz unterschiedliche Ansätze zum Vorschein, dreidimensionale Grafiken zu erzeugen, und keine davon lieferte "echtes" 3D. Das berüchtigte Wolfenstein 3D setzte eine "Raycasting [12]" genannte Technik ein, die später erheblich weiterentwickelt wurde und sich lange als die Technik für Egoshooter zu etablieren schien.
Als Alternative bot sich die voxelbasierte Grafik an, die u.a. Comanche [13] nutzte. Und natürlich gab es auch schon früh polygonbasierende 3D-Grafik. Selbst auf dem C64 war hierfür Stunt Car Racer verfügbar!
Wann nun "echtes" 3D erreicht wird, ist streitig. Momentan lässt Intel verstärkt an Raytracingengines für Computerspiele forschen, weil Raytracing oft als einzige "echte" 3D-Berechnungsmethode angesehen wird. Im Kino läuft "Avatar", die Unterhaltungsindustrie hofft auf "3D" als den nächsten Kassenfüller.
Fakt ist aber, dass als Prinzip für die Grafikberechnung bei Computerspielen die Polygongrafik (eigentlich: Polygonrasterung [14]) als Sieger aus den Achtziger- und Neunzigerjahren hervorgegangen ist. Praktisch jedes 3D-Spiel verwendet heute Polygongrafik. Hauptgründe für deren Sieg sind wohl zum einen die Tatsache, dass Polygongrafik gut und schnell mittels massiver paralleler Numbercruncher (GPUs) zu berechnen ist, zum anderen kommt Polygongrafik "echtem" 3D doch recht nah: Zumindest als mathematisches Konstrukt wird ein echter dreidimensionaler Raum vorgehalten. Dennoch wird auch heute noch getrickst, wo es nur geht …
2.
Mathematik – oder: So einfach funktioniert die Welt
Um geschickte Trickserei soll es hier aber gar nicht gehen. Polygongrafikengines haben eine langjährige Entwicklung hinter sich: Von Stunts ...
... bis zu Crysis ...
... und darüber hinaus. Doch wie funktioniert die Technik?
Wie der Name schon sagt, wird in der Polygongrafik die Grafik aus Polygonen [15] (dt: Vielecken) zusammengesetzt, sogenannten "Primitives [16]". Wenn mehrere solcher Vielecke zu einem Netz (eng: Mesh) zusammengesetzt werden, ergibt sich ein Drahtgittermodell eines dreidimensionalen Objektes, welches dann gerendert [17] wird. Wie dies gemacht wird, soll im Folgenden beschrieben werden.
Zunächst einmal muss klargestellt werden, dass die dreidimensionale Welt "im" bzw. "hinter" dem Bildschirm stattfindet. Stellt man sich den Bildschirm als eine der Flächen eines Würfels vor, so befindet sich im Inneren des Würfels die dreidimensionale Welt. Der Bildschirm ist nur unser Fenster, durch das wir in die Welt im Würfel hineinschauen können.
Die dreidimensionale Welt, die sich im Inneren des Würfels abspielt, hält der Computer in seinem Arbeitsspeicher vor. Genauer gesagt befindet sich im Arbeitsspeicher die dreidimensionale Koordinate eines jeden Eckpunktes eines jeden Polygons der dreidimensionalen Welt. Bewegt sich ein Objekt durch den Raum, werden die Koordinaten der Polygone des betreffenden Objekts entsprechend angepasst. Der Renderer kann dann auf Basis der neuen Daten eine aktualisierte Ansicht unseres Fensters in die Welt berechnen. Es findet eine Projektion [18] statt: Die dreidimensionale Welt wird auf die zweidimensionale Bildschirmoberfläche projiziert.
Üblicherweise werden 3D-Modelle mithilfe einer Modeling-Software wie Blender [19] erzeugt. Hier soll stattdessen ein einfaches Modell "per Hand" definiert werden. Eine quadratische Pyramide soll es sein. Dazu ist ein Quadrat nötig und nur zwei Dreiecke (!), da die Seiten nicht gefüllt werden sollen (der Trick sollte niemandem auffallen, wir verraten es einfach keinem). Das ergibt genau drei Polygone, die zusammen ein Mesh bilden werden.
Hinweis: Mit diesem Mesh würde man bei Direct3D schon nicht sehr weit kommen. Direct3D setzt nämlich voraus, dass alle Polygone aus drei und nur aus drei Ecken bestehen (also Dreiecke sind). Die Grundfläche der Pyramide soll aber ein Quadrat sein. Deswegen wäre es zunächst nötig, das Quadrat in zwei Dreiecke zu zerlegen (zu "triangulieren [20]"). Dieses Erfordernis macht Direct3D aus guten Gründen: Zum einen wird somit eine Einheitlichkeit der Berechnungsalgorithmen ermöglicht, zum anderen wird so sichergestellt, dass Polygone stets konvex sind.
Hier zunächst die vier Koordinaten des Quadrats Q:
Das Quadrat liegt also auf der x-y-Ebene, die Höheninformation z ist für alle Punkte gleich null. Die Mitte des Quadrats ist genau der Ursprung (0, 0, 0). Für die Spitze der Pyramide bietet sich also ein Punkt an, der genau über der Mitte liegt, nur eben hoch genug. So sind auch die beiden Seitenflächen der Pyramide definiert.
Dreieck A:
und Dreieck B:
3.
Punktevergabe – oder: Ran an's Eingemachte
Bis jetzt besteht die Welt aus fünf Punkten, die durch dreidimensionale Vektoren dargestellt werden. Um diese dreidimensionalen Vektoren sinnvoll auf dem Bildschirm darstellen zu können, bedarf es einer Projektion. Um eine solche Projektion durchführen zu können, wird eine Projektionsmatrix benötigt. Diese Matrix bildet die dreidimensionalen Vektoren in den zweidimensionalen Raum ab, indem die Vektoren mit der Matrix multipliziert werden.
Matrizen werden multipliziert, indem ihre Elemente paarweise multipliziert und zeilen-/spaltenweise aufaddiert werden. Dieses kurze Beispiel [21] enthüllt schon das ganze Geheimnis.
Hinweis: Bei der Polygongrafik sind enorm viele solcher Matrixmultiplikationen vonnöten. Man sieht, dass hierfür ausschließlich die Grundrechenarten Multiplikation und Addition benötigt werden. Frühe Grafikbeschleuniger (zu 3fdx-Zeiten) waren simple multiply/add-Maschinen. Heutige Grafikkarten können mehr, da sie auch mehr Aufgaben bekommen, ihre wesentliche Hauptaufgabe ist aber nach wie vor massives Multiplizieren und Addieren. Die Berechnungen sind dabei in aller Regel voneinander unabhängig, so dass viele Berechnungen parallel ablaufen können. Moderne GPUs rechnen eine MUL und eine ADD (auch zu einer MADD zusammengefasst) pro Takt und Paralleleinheit. So kommen viele hundert Milliarden MADDs pro Sekunde zustande.
Wenn der (transponierte) Vektor A die Dimension 1x3 hat und das Ergebnis der Multiplikation die Dimension 1x2 haben soll, wie muss dann die Dimension der Projektionsmatrix P beschaffen sein?
Nach kurzem Hinschauen wird klar, dass als Dimension für P nur in Frage kommt. Jede Matrix P, die diese Eigenschaft erfüllt, ist Projektionsmatrix. Welche Matrix man wählt, entscheidet darüber, welche perspektivische Verzerrung man erhält. Somit kann man z.B. auch das Field of View (FOV) [22] einstellen.
Eine einfache Projektionsmatrix ist die Kavalierprojektion [23]. Diese Matrix sieht wie folgt aus:
Wenn also beispielsweise der erste Punkt des Grundquadrats der Pyramide auf die Ebene projiziert werden soll, ergibt sich:
Der Punkt (1,5 ; 0,25) lässt sich direkt auf das zweidimensionale Koordinatensystem zeichnen. Macht man das für alle Punkte der Szene, erhält man lauter Punkte auf der zweidimensionalen Ebene, die man nur noch so miteinander verbinden muss, wie es eine Vorschrift angibt. Diese Vorschrift ist in der Regel für jedes Polygon gegeben durch "verbinde Punkt eins mit Punkt zwei, Punkt zwei mit Punkt drei und Punkt drei mit Punkt eins". Beim hier verwendeten Grundquadrat muss das Ganze natürlich auf vier Punkte ausgeweitet werden – ein weiterer Grund, warum Direct3D hier nur Dreiecke zulässt: Damit diesbezüglich gar nicht erst Verwirrung aufkommt.
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 [25]. 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 [26] 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 [27] 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 [28]. Dieses eigentlich bis heute nicht vollständig gelöste Problem wird speicherfressend und ineffizient, aber doch zuverlässig mittels eines Z-Buffers [29] 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 [30] 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 [31]. Hier werden zunächst die Vektoren (oder „Vertices [32]“) typisiert. Man beachte, dass die Koordinaten mit Gleitkommazahlen einfacher Genauigkeit [33] 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 [34] 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.
Verweise:
[1] https://www.3dcenter.org/users/bagzzlash
[2] http://de.wikipedia.org/wiki/Grafik-Engine
[3] http://de.wikipedia.org/wiki/Pong
[4] http://de.wikipedia.org/wiki/Space_Invaders
[5] http://de.wikipedia.org/wiki/Pac_Man
[6] http://de.wikipedia.org/wiki/C64
[7] http://de.wikipedia.org/wiki/Nintendo_Entertainment_System
[8] http://de.wikipedia.org/wiki/Sprite_%28Computergrafik%29
[9] http://de.wikipedia.org/wiki/Turrican
[10] http://de.wikipedia.org/wiki/Amiga_500
[11] http://de.wikipedia.org/wiki/SNES
[12] http://de.wikipedia.org/wiki/Raycasting#Raycasting_bei_Computerspielen
[13] http://de.wikipedia.org/wiki/Comanche_%28Computerspiel%29
[14] http://de.wikipedia.org/wiki/Rasterung_von_Polygonen
[15] http://de.wikipedia.org/wiki/Polygon
[16] http://de.wikipedia.org/wiki/Grafisches_Primitiv
[17] http://de.wikipedia.org/wiki/Bildsynthese
[18] http://de.wikipedia.org/wiki/Projektion_%28Mathematik%29
[19] http://www.blender.org/
[20] http://de.wikipedia.org/wiki/Delaunay-Triangulation
[21] http://de.wikipedia.org/wiki/Matrix_%28Mathematik%29#Matrizenmultiplikation
[22] http://de.wikipedia.org/wiki/Field_of_view
[23] http://de.wikipedia.org/wiki/Kavalierprojektion
[24] http://www.forum-3dcenter.org/vbulletin/showthread.php?t=479329
[25] http://de.wikipedia.org/wiki/Bresenham-Algorithmus
[26] http://de.wikipedia.org/wiki/Rotationsmatrix#Drehmatrizen_des_Raumes_R.C2.B3
[27] http://de.wikipedia.org/wiki/Framebuffer
[28] http://de.wikipedia.org/wiki/Sichtbarkeitsproblem
[29] http://de.wikipedia.org/wiki/Z-Buffer
[30] http://de.wikipedia.org/wiki/normalenvektor
[31] http://de.wikipedia.org/wiki/Typisierung_%28Informatik%29
[32] http://de.wikipedia.org/wiki/Vertex#Rechnergrafik
[33] http://de.wikipedia.org/wiki/Einfache_Genauigkeit
[34] http://de.wikipedia.org/wiki/Feld_%28Datentyp%29
[35] https://www.3dcenter.org/abbildung/rotation
[36] https://www.3dcenter.org/abbildung/projekt
[37] https://www.3dcenter.org/abbildung/loop
[38] http://www.3dcenter.org/artikel/ein-kurzer-einblick-die-grundlegende-funktionsweise-von-grafikengines/ein-einblick-die-grund