Geschichte
Die Verfahren aus den letzten Kapiteln sind nicht auf einmal entstanden. Jede Stufe war die beste Antwort auf die Rechenleistung ihrer Zeit. Und fast immer steckte dahinter eine Idee, wie man mit weniger Rechnung auskommt.
Nur Linien
Die ersten 3D-Spiele, etwa Battlezone (1980), zeigen von jedem Körper nur die Kanten. Gespeichert ist eine Liste von Eckpunkten und eine Liste von Kanten, die je zwei Eckpunkte verbinden. In jedem Bild passiert dreierlei:
- Jeden Eckpunkt drehen und verschieben (Kapitel 1).
- Jeden Eckpunkt auf den Bildschirm projizieren (Kapitel 4, Schritt 2).
- Für jede Kante eine Linie zwischen ihren beiden Bildpunkten ziehen.
Warum keine gefüllten Flächen? Jedes gefüllte Pixel muss einzeln berechnet und gespeichert werden. Ein Würfel, der ein Viertel des Bildschirms füllt, bedeutet Zehntausende Pixel. Seine zwölf Kanten berühren nur ein paar Hundert. Die Rechner dieser Zeit waren millionenfach langsamer als heutige. Linien waren das, was in 1/30 Sekunde zu schaffen war.
Gefüllte Flächen
Mit schnelleren Prozessoren werden die Dreiecke einfarbig gefüllt, zunächst in Flugsimulatoren und Rennspielen. Damit entsteht ein neues Problem: Welche Fläche verdeckt welche?
Die damalige Lösung ist der Maleralgorithmus. Er arbeitet wie jemand, der ein Landschaftsbild malt: erst den Himmel, dann die Berge, dann das Haus, zuletzt den Baum im Vordergrund. Was später gemalt wird, übermalt das Frühere. Für den Computer heißt das:
- Alle Dreiecke nach ihrer Entfernung zur Kamera sortieren.
- Mit dem entferntesten beginnen und der Reihe nach zeichnen.
Aufwand: Das Sortieren von n Dreiecken kostet etwa n · log₂ n Schritte, und zwar in jedem Bild neu, weil sich die Kamera bewegt.
Die Schwäche: Wenn sich zwei Dreiecke durchdringen, liegt keines vollständig vor dem anderen. Dann gibt es keine richtige Reihenfolge, und im Bild entstehen Fehler. Der Tiefenpuffer aus Kapitel 4 löst das, indem er für jedes Pixel einzeln entscheidet. Er braucht aber eine zweite Tabelle, so groß wie das ganze Bild. Dafür war Speicher damals zu teuer.
Räumlich aussehen, flach rechnen
Wolfenstein 3D (1992) zeigt Gänge und Räume aus der Ich-Perspektive, flüssig und mit Texturen an den Wänden. Für echtes 3D mit Dreiecken, Rasterisierung und Tiefenvergleich waren die Rechner noch zu langsam. Das Spiel umgeht das mit einer starken Vereinfachung.
Die Welt ist ein Grundriss
Der ganze Level ist eine Karte aus quadratischen Feldern, von oben gesehen. Jedes Feld ist entweder Wand oder frei. Es gibt keine Dreiecke und keine Höhe.
karte = ["##########",
"#........#",
"#..##....#", # "#" = Wand, "." = frei
"#..#.....#",
"##########"]
spieler_x, spieler_y = 1.5, 1.5 # Position auf der Karte
blickrichtung = 0.8 # ein WinkelAuch die Spielfigur hat nur zwei Koordinaten und eine Blickrichtung. Sie kann nicht springen und nicht nach oben oder unten schauen.
Ein Strahl pro Bildspalte
Das Bild wird Spalte für Spalte erzeugt. Für jede Spalte des Bildschirms wird auf der Karte ein Strahl in die passende Richtung verfolgt, bis er auf ein Wandfeld trifft. Das einzige Ergebnis ist eine Zahl: die Entfernung zur Wand.
Aus dieser Entfernung wird ein senkrechter Wandstreifen gezeichnet. Ist die Wand nah, wird der Streifen hoch, ist sie fern, wird er niedrig. Das ist dieselbe Regel wie bei der Projektion: Größe geteilt durch Entfernung. Viele Streifen nebeneinander ergeben ein Bild, das räumlich aussieht.
Links siehst du, was der Computer wirklich berechnet: Strahlen auf einer flachen Karte. Rechts steht das Bild, das daraus entsteht. Wähle mit dem Regler eine Bildspalte und verfolge ihren Strahl auf der Karte.
for spalte in range(bildbreite):
winkel = blickrichtung + (spalte / bildbreite - 0.5) * sichtfeld
weg = 0
while karte[int(spieler_y + weg * sin(winkel))][int(spieler_x + weg * cos(winkel))] != "#":
weg = weg + SCHRITT # auf der Karte weiterwandern
zeichne_wandstreifen(spalte, hoehe = bildhoehe / weg)Aufwand: Bei 320 Bildspalten sind es 320 Strahlen pro Bild, jeder nur ein paar Schritte auf einer kleinen Karte. Es gibt nichts zu sortieren und keinen Tiefenpuffer, denn jeder Strahl findet von selbst die vorderste Wand.
Der Preis: Alle Wände sind gleich hoch und stehen senkrecht. Es gibt keine Treppen, keine Brücken und keine Räume übereinander. Deshalb spricht man von 2,5D. Doom (1993) erlaubte unterschiedlich hohe Böden und Decken, blieb im Kern aber ebenfalls ein Grundriss.
Echtes 3D mit Texturen
Quake (1996) baut Räume, Gegner und Gegenstände vollständig aus Dreiecken mit Texturen. Man kann in jede Richtung schauen, Räume liegen übereinander. Gezeichnet wird so, wie es Kapitel 4 beschreibt: Projektion, Rasterisierung, Textur und Tiefenvergleich.
Die Prozessoren von 1996 hätten das für einen ganzen Level nicht geschafft. Quake wird durch Vorberechnung möglich: Aufwendige Rechnungen werden nicht während des Spiels ausgeführt, sondern einmal vorher, wenn der Level gebaut wird. Das Ergebnis wird gespeichert und im Spiel nur nachgeschlagen.
- Sichtbarkeit: Der Level ist in Bereiche unterteilt. Für jeden Bereich wird vorab eine Liste angelegt, welche anderen Bereiche von dort aus überhaupt zu sehen sind. Im Spiel werden nur die Dreiecke dieser Bereiche gezeichnet. Alles hinter geschlossenen Wänden entfällt, ohne dass ein einziges Pixel dafür geprüft wird.
- Licht: Licht und Schatten auf den Wänden werden vorab mit einem langsamen, genauen Verfahren berechnet. Das dauerte pro Level Minuten bis Stunden. Das Ergebnis wird als Bild gespeichert und im Spiel wie eine zweite Textur über die Wände gelegt.
Die Idee dahinter: Rechenzeit gegen Speicher tauschen. Der Preis: Was vorberechnet ist, kann sich nicht ändern. Wände bewegen sich nicht, Lampen lassen sich nicht ausschalten.
Grafikkarten
Ein Prozessor besitzt wenige, sehr vielseitige Rechenkerne. Jeder kann beliebige Programme ausführen, arbeitet aber einen Befehl nach dem anderen ab. Für ein Bild mit zwei Millionen Pixeln heißt das: zwei Millionen Mal dieselbe kleine Rechnung, hintereinander.
Eine Grafikkarte ist anders gebaut. Sie enthält Tausende sehr einfacher Recheneinheiten. Jede einzelne kann viel weniger als ein Prozessorkern, aber alle arbeiten gleichzeitig. Das lohnt sich nur bei Aufgaben, die sich in viele gleiche, voneinander unabhängige Teile zerlegen lassen. Genau so eine Aufgabe ist das Zeichnen: Die Farbe eines Pixels hängt nicht von der Farbe des Nachbarpixels ab (Kapitel 4, Aufwand).
In der Demo färbt jede Recheneinheit pro Zeitschritt ein Pixel. Die Arbeit bleibt dieselbe, 600 Pixel. Aber mit 256 Einheiten ist sie nach 3 Zeitschritten erledigt statt nach 600.
Vom festen Ablauf zum Programm
- 1996: Die ersten verbreiteten 3D-Karten übernehmen Rasterisierung, Textur und Tiefenpuffer. Die Projektion der Eckpunkte rechnet weiter der Prozessor.
- 1999: Die Karten übernehmen auch Drehung, Verschiebung und Projektion der Eckpunkte. Seitdem heißt der Baustein GPU (Graphics Processing Unit).
- Ab 2001: Bis dahin war der Rechenweg in der Karte fest verdrahtet. Jetzt lässt er sich programmieren. Spielestudios schreiben kleine Programme, die die Karte für jeden Eckpunkt und für jedes Pixel ausführt. Sie heißen Shader. Ein Pixel-Shader berechnet zum Beispiel die Helligkeit aus dem Winkel zum Licht (Kapitel 5, Weg 1) für jedes Pixel einzeln statt einmal pro Dreieck.
Die Idee dahinter: nicht schneller rechnen, sondern gleichzeitig.
Raytracing in Echtzeit
Raytracing (Kapitel 5, Weg 2) galt lange als zu teuer für Spiele. Pro Strahl muss der Baum aus Hüllkörpern durchlaufen werden: Trifft der Strahl diesen Quader? Trifft er dieses Dreieck? Diese beiden Tests fallen milliardenfach pro Sekunde an.
Seit 2018 enthalten Grafikkarten dafür eigene Schaltungen. Das bedeutet: Der Test ist nicht mehr ein Programm, das Befehl für Befehl abgearbeitet wird. Er ist direkt als Bauteil in den Chip gebaut. Ein solches Bauteil kann nur diese eine Rechnung, erledigt sie aber um ein Vielfaches schneller, und es gibt sehr viele davon nebeneinander.
Trotzdem reicht die Leistung nur für wenige Strahlen pro Pixel. Für weiche Schatten oder Spiegelungen auf rauen Flächen bräuchte man eigentlich Hunderte. Das Ergebnis mit wenigen Strahlen ist körnig, wie ein Foto bei zu wenig Licht. Deshalb wird das Bild anschließend entrauscht: Jedes Pixel wird mit seinen Nachbarn und mit dem vorherigen Bild verrechnet.
Heutige Spiele kombinieren beide Welten: Rasterisierung für das Grundbild, Raytracing für Schatten, Spiegelungen und indirektes Licht.
- Weil keines der beiden vollständig vor dem anderen liegt.
- Weil Sortieren zu langsam ist.
- Weil Dreiecke keine Farbe haben.
- Weil es keine Texturen hat.
- Weil die Welt ein flacher Grundriss ohne Höhe ist.
- Weil es keine Perspektive zeigt.
- Eine lange Rechnung, bei der jeder Schritt das Ergebnis des vorigen braucht.
- Sehr viele gleiche, voneinander unabhängige kleine Rechnungen.
- Das Lesen einer Datei von der Festplatte.
Aufgabe: Wolfenstein 3D lief mit 320 × 200 Pixeln. Vergleiche die Zahl der Strahlen beim Verfahren mit dem Grundriss mit der Zahl der Strahlen, die Raytracing wie in Kapitel 5 bräuchte.
Lösung anzeigen
Grundriss: 320 Strahlen, einer pro Bildspalte. Raytracing: 320 · 200 = 64 000 Kamerastrahlen und bis zu ebenso viele Schattenstrahlen, also das 200- bis 400-Fache.
Aufgabe: Ein Bild hat 2 Millionen Pixel. Eine Recheneinheit braucht für ein Pixel einen Zeitschritt. Wie viele Zeitschritte dauert das Bild mit einer Einheit, wie viele mit 4 000 Einheiten?
Lösung anzeigen
Mit einer Einheit 2 000 000 Zeitschritte. Mit 4 000 Einheiten 2 000 000 ÷ 4 000 = 500 Zeitschritte.
Aufgabe: Bei Quake sind Licht und Schatten vorberechnet. Nenne einen Vorteil und einen Nachteil.
Lösung anzeigen
Vorteil: Im Spiel kostet das Licht fast keine Rechenzeit, es wird nur ein gespeichertes Bild über die Wand gelegt. Nachteil: Das Licht kann sich nicht ändern. Eine bewegte Lampe oder eine Tür, die Licht hereinlässt, ist so nicht darstellbar.