Raytracing in Spielen II: Das Reich der Strahlen macht Fortschritte

Raytracing vs. Rasterisierung

Ich wurde des Öfteren gefragt, ab wann Raytracing schneller sein wird als Rasterisierung (der Ansatz der heutigen GPUs zum Rendern). Nun, es gibt bereits jetzt Fälle, in denen Raytracing auf einer einzelnen Desktop-Maschine schneller ist!

Beispiel 1

Raytracing benutzt „Beschleunigungsstrukturen“, die die gesamte Geometrie einer virtuellen Welt anhand ihrer Position im Raum sortieren. Es gibt viele verschiedene Ansätze dies zu tun. Die bei Raytracing am häufigsten benutzten sind Uniform Grids, BSP-trees, kd-trees und Bounding Volume Hierarchies (BVHs).

Wie bereits in der Einleitung beschrieben, muss man beim Schießen eines Strahls herausfinden, welches Objekt entlang des Pfades des Strahls zuerst getroffen wird. Die grundlegende Idee der räumlichen Unterteilung mit Beschleunigungsstrukturen wird am Besten mit einem kleinen Beispiel beschrieben: Man stelle sich vor, man habe ein vier Stockwerke hohes Gebäude. Auf jedem Stockwerk befinden sich vier Räume und der Spieler befindet sich im obersten Stockwerk in dem Zimmer ganz links:

Durch das Verfolgen des Strahls wollen wir herausfinden, ob ein bestimmtes Stück Geometrie getroffen wird oder nicht. In der Raytracing-Sprache: Wir schießen Strahlen aus der „Kamera“ (den Augen des Spielers) um mit diesen „Primärstrahlen“ festzustellen, was sichtbar ist und was nicht. Der naive Ansatz wäre, die Strahlen einfach gegen die komplette Geometrie zu testen, ob sie diese treffen. In unserem Beispiel würde man offensichtlich sehr viel Rechenaufwand verschwenden. Denkt man über die Situation ein wenig nach, so wird schnell klar, dass der Spieler links oben im Raum sehr unwahrscheinlich etwas sehen wird, das sich beispielsweise im Raum rechts unten befindet. Warum sollte man also überhaupt den Strahl darauf testen, ob er Geometrie in diesem Raum rechts unten trifft? Wie kann man diesen überflüssigen Rechenaufwand am Besten vermeiden?

Die Lösung sind hierarchische, räumliche Beschleunigungsstrukturen, mit denen man schnell feststellen kann, ob ein bestimmter Bereich für das Rendern ein relevantes Detail enthält. Ist dies nicht der Fall, so kann man auf einen Schlag einen haufen Berechnungsarbeit sparen und diese in anderen Bereichen nutzen, in denen hoch detaillierte, sichtbare Geometrie vorhanden ist.

Analytisch ausgesprochen ist einer der Vorteile von solch' hierarchischen Datenstrukturen, dass sie eine „lineare Suche“ (jedes Mal alles gegen alles testen) zu einer „logarithmischen Suche“ optimieren. Dies bedeutet, dass man von der obersten Hierarchiestufe, die den Raum aller Geometrie beinhaltet (in unserem Fall das gesamte Gebäude mit den 16 Räumen), nur dann in einen detaillierten Bereich (einen einzelnen Raum) vordringt, wenn es darin wirklich relevante Informationen gibt.

… die nächste Stufe teilt die Räume in der Mitte von oben nach unten ...

… die nächste Stufe teilt die links übrig bleibenden acht Räume in der Mitte und unterteilt sie in zwei Bereiche mit jeweils vier Räumen ...

Im Falle der linearen Suche würde man jeden der einzelnen 16 Räume absuchen. Also einen Arbeitsaufwand von 16 betreiben. Im logarithmischen Fall würde man im Schritt eins die rechte Hälfte eliminieren. Im zweiten Schritt würde man den Bereich links unten eliminieren. Schritt drei würde die rechte Hälfte der vier verbleibenden Räume als irrelevant markieren. Im vierten Schritt findet man schließlich heraus, dass nur der eine Raum links oben relevant ist. Also benötigte man hier nur vier Arbeitseinheiten anstatt 16.

Wenn man nun das Gebäude auf 32 Räume vergrößert, so hätte man im linearen Fall 32 Arbeitseinheiten verglichen, aber nur 5 im Falle der logarithmischen Suche. Allgemein gilt: Wenn man die geometrische Komplexität einer Szene um das Zehnfache steigert, dann erhöht sich der Rechenaufwand bei der Verwendung der hierarchischen Beschleunigungsstrukturen nur um den Faktor zwei. Im Kontrast dazu steht die Rasterisierung mit ihrem linearen Verhalten, bei dem die Steigerung der Geometrie um das Zehnfache auch den zehnfachen Rechenaufwand bedeutet.

Dieses Verhalten ist im folgenden Diagramm dargestellt:

Die graue Kurve repräsentiert den Rechenaufwand von Raytracing, wenn man die Anzahl der Dreiecke erhöht. Die rote zeigt das lineare Verhalten der Rasterisierung. Wie man sehen kann, ist Raytracing bei einer niedrigen Anzahl an Dreiecken im Nachteil. Allerdings treffen sich die Kurven schnell und ab diesem Punkt ist Raytracing bei steigender Komplexität schneller als Rasterisierung, sobald die Beschleunigungsstruktur aufgebaut wurde. Wo genau dieser Schnittpunkt liegt, das hängt von vielen Faktoren ab: Der Performance der CPU, der Performance der GPU usw.. Aber der Trend ist eine mathematische Gewissheit: Die logarithmische Kurve wird immer einen Schnittpunkt mit einer linearen haben.

Durch das nahezu perfekte Skalierungsverhalten von Raytracing würde die graue Kurve bei einer Verdoppelung der CPUs oder CPU-Cores um die Hälfte schrumpfen und somit den Schnittpunkt näher in den Bereich der im Diagramm eingezeichneten Null bewegen. Je mehr CPUs bzw. Cores zur Verfügung stehen, umso schneller kommt man also an den Punkt, an dem man schneller als das Rasterisierungsverfahren auf der GPU ist.

Ein Beispiel, das eindeutig über dem Schnittpunkt liegt, ist das Modell einer Boeing 777 mit 350 Millionen Dreiecken. Dieses extrem hoch detaillierte Modell beinhaltet jede Schraube des Flugzeugs und wurde von Boeing Wissenschaftlern zur Verfügung gestellt, um nach Methoden zu forschen, mit denen man das komplette Flugzeug am besten in Bewegung grafisch darstellen kann.

Raytracing hat sich als die korrekte Lösung dafür erwiesen. Bereits im Jahr 2004 konnte die Forschungsgruppe der Universität des Saarlandes dieses Modell mit 3 bis 7 Bildern pro Sekunde in einer Auflösung von 640x480 auf einer Dual-Core-CPU der damaligen Zeit rendern.

Es mag die Frage aufkommen, warum die erwähnten Beschleunigungsstrukturen nicht auch in der Rasterisierung verwendet werden? Sie werden benutzt! Allerdings mit einer geringeren Präzision. Einige Spiele haben gar verschieden aufgelöste Granulare zum Rendern von Grafik, für die Kollisionserkennung oder die AI (manchmal erzeugt über Bibliotheken von anderen Softwareherstellern). Neben dem erhöhten Speicherverbrauch ist ein weiteres Problem dieser multiplen Strukturen, dass man sie konsistent halten muss.

Hier ein Beispiel dafür, was passiert, wenn die Informationen aus der Kollisionserkennung nicht mit denen aus der Datenstruktur zum Rendern konsistent sind: In dem Spiel „Oblivion“ werden unterschiedlich detaillierte Repräsentationen der Welt zum Rendern bzw. für die Kollisionserkennung benutzt. Wenn sich eine Tür in dem Spiel langsam schließt, so ist dies für den Spieler klar sichtbar. In jedem Bild verändert sich der Winkel leicht, bis die Tür geschlossen ist. Daher kann man annehmen, dass es mindestens vier verschiedene Zustände für diese Tür gibt: offen, schließend, geschlossen, öffnend. Doch die Datenstruktur der Kollisionserkennung aktualisiert sich nicht mit demselben Detailgrad. Somit können andere computergesteuerte Charaktere wie „Velwyn“ nur zwei Zustände der Tür ausmachen: offen oder geschlossen.

Im Spiel kann es daher dazu kommen, dass die Türe für den Spieler offensichtlich gerade dabei ist sich zu schließen, da Velwyn aber nur die Information bekommen kann, dass die Türe nicht geschlossen ist, kommt er zu der Annahme, dass die Tür also offen sein muss. Daher bewegt sich Velywn auf die Türe zu, bis er schlagartig darin feststeckt, sobald der Status der Tür auf geschlossen aktualisiert wurde. Das sieht dann so aus:

(Natürlich kann man Raytracing auch für Kollisionserkennung benutzen um solche Probleme zu verhindern, aber das ist eine andere Geschichte).

Aber auch falls die Beschleunigungsstrukturen zum Rendern mit den anderen in der Rasterisierung konsistent sind, gibt es noch ein anderes Problem: In Raytracing testet man die Strahlen pixelgenau gegen die Dreiecke. In der Rasterisierung gibt es hingegen keine Strahlen, die genau gegen die Beschleunigungsstruktur getestet werden können, daher muss man sich wieder auf weniger effiziente Approximationen verlassen. Dies kann mit verschiedenen Methoden getan werden. Hier ein kurzer Überblick über zwei davon:

• Zeitaufwendige Vorberechnungen, die Aussagen liefern wie „Wenn ich in Zimmer 1 bin, dann könnte ich möglicherweise Zimmer 2 und 3 sehen, aber nicht Zimmer 4“. Weitere Informationen zu diesem Verfahren gibt es in der Wikipedia in dem Eintrag zu „Potentially Visible Set“
  
  
• Manuell platzierte Hinweise von Level-Designern, so genannte Sichtbarkeitsportale. Diese benötigen viel zusätzlichen Zeitaufwand seitens der Programmierer. Das originale Quake 4 benutzt beispielsweise 3.200 Stück davon und automatisierte Algorithmen zum Setzen der Portale haben ihren Weg nicht in die Praxis der Spieleentwickler gefunden. Die Auswertung der Portale beim Rendern in der Rasterisierung führt zu komplizierten Multi-Pass-Techniken: Zuerst wird die Szene mit Platzhaltern für die Portale gerendert. Nachdem erkannt wurde, dass einer der Platzhalter sichtbar ist, wird dieser Teil der Szene erneut gerendert, dieses Mal mit dem vollen Detail. Weitere Informationen zum „Portal Rendering“ sind in der Wikipedia zu finden.