Vortrag: Echtzeit-Raytracing
11.11.2010 Vortragender: Benedikt Müller
In der realen Welt funktioniert das Sehen so: Lichtquellen strahlen Licht aus, das auf Oberflächen von Gegenständen auftrifft und von dort je nach Oberflächenbeschaffenheit weitergeleitet wird: Es wird reflektiert, gebrochen, gestreut, gebeugt und ein Teil wird absorbiert. Einige wenige der Lichtwege enden auf der Netzhaut und erzeugen das Bild, das wir sehen. Theoretisch lässt sich dieser Prozess auch im Rechner simulieren. Da aber nur ein verschwindend geringer Teil der Strahlen auf der simulierten Netzhaut landen würde, dreht man den Prozess um. Beim Raytracing starten alle Strahlen am Augpunkt und durchqueren die Bildebene. Im einfachsten Fall wird ein Strahl pro Pixel losgeschickt und der erste Schnittpunkt mit Geometrie in der Szene bestimmt.
Mit Hilfe des Richtungsvektors des Strahls, der Oberflächennormale des Objekts am Auftreffpunkt und Vektoren, die in Richtung der Lichtquellen zeigen, lässt sich die direkte Beleuchtung an dieser Stelle berechnen. Wenn man vom Auftreffpunkt einen Strahl in Richtung einer Lichtquelle losschickt, kann man die Sichtbarkeit der Lichtquelle für diesen Punkt bestimmen. Ist sie nicht sichtbar, so ist der Punkt verschattet. Raytracing berechnet auf einfache Weise sehr exakte, harte Schattenwürfe. Es gibt noch zwei weitere Phänomene, die sich sehr exakt bestimmen lassen. Das Material am Auftreffpunkt kann spiegelnd sein, dann kann man rekursiv einen weiteren Strahl in die Reflexionsrichtung senden. Oder es kann transparent sein, dann lässt sich ein Strahl in die Richtung senden, die mit Hilfe des Brechungsindex bestimmt wird. Raytracing ermöglicht dadurch ebenso einfach die Berechnung von präzisen Reflexionen und Lichtbrechungen. Die resultierende Farbe des Pixels der Bildebene berechnet sich aus der gewichteten Addition der direkten Beleuchtungsstärken am 1. Auftreffpunkt und den Auftreffpunkten der Reflexions- und Brechungsstrahlen.
Das beschriebene rekursive Raytracing wird nach seinem Erfinder Whitted-style Raytracing genannt und ist meistens gemeint, wenn Echtzeit-Frameraten erreicht werden sollen.
Bild: Zwei Ansichten eines mit Raytracing gerenderten Autoscheinwerfers. (ca. 10 FPS auf einem Cluster von 16 dual-AthlonMP 1800+ PCs)
Beschleunigungsstrukturen
Eine naive Implementierung eines Raytracers bestimmt den ersten Schnittpunkt des Strahls, indem sie den Schnittpunkt mit allen Primitiven ermittelt und den nahesten zurückgibt. Was für einen "Hello World"-Raytracer ausreicht, ist auch für Nicht-Echtzeit-Raytracer viel zu ineffizient. Bei n Primitiven benötigt die Schnittpunktsbestimmung O(n) Rechenzeit. Deswegen wird der Raum in der Szene hierarchisch unterteilt und die Primitive in die Hierarchie eingeordnet. Der Strahl traversiert die Hierarchie und wird nur mit den Primitiven tatsächlich geschnitten, die überhaupt in seiner Nähe liegen. Zur Raumunterteilung sind 2 Methoden weit verbreitet: kd-Trees und Bounding Volume Hierarchies. Die Verwendung einer Hierarchie beschleunigt die Schnittpunktbestimmung auf eine mittlere Rechenzeit in O(log n).
Die logarithmische Abhängigkeit von der Geometrie ermöglicht die Darstellung sehr komplexer Modelle. Die abgebildete Waldszene enthält über 1 Milliarde Polygone und wird auf einem leistungsstarken Cluster in wenigen Sekunden gerendert.
Echtzeit-Raytracing
Bei circa 6 Bildern pro Sekunde kann ein Benutzer einigermaßen flüssig mit einer Szene interagieren, er hat dann interaktive Frameraten. Der Übergang zu Echtzeit-Frameraten ist fließend, ca. 15-30 FPS werden als flüssig wahrgenommen. Um solche Frameraten auch auf einzelnen Rechner zu erhalten, reichen High-Level-Optimierungen wie z.B. eine Hierarchie nicht aus. Es sind Low-Level-Optimierungen nötig, die die verwendete CPU oder GPU optimal nutzen. Kohärente Strahlen, also Strahlen, die nahe beieinander liegen, haben eine hohe Wahrscheinlichkeit, die Hierarchie auf ähnlichen Wegen zu traversieren. Auf niedrigster Ebene kann dies genutzt werden um Operationen von 4 Strahlen parallel mit den SIMD-Instruktionen der CPU auszuführen. Mehrere dieser aus 4 Strahlen bestehenden SIMD-Strahlen lassen sich auch zu größeren Strahl-Paketen zusammenfassen, um Cache-Misses zu reduzieren. Mit Hilfe des Bounding Frustums der Strahl-Pakete lässt sich auch die Traversierung der Hierarchie beschleunigen.
Raytracing ist ein sehr parallel arbeitendes Verfahren und profitiert somit von vielen CPU-Kernen. Moderne Grafikprozessoren haben bis zu ca. 500 Streamprozessoren, die mittlerweile auch frei programmierbar sind ( GPGPU ). Raytracing auf GPUs konnte dennoch bis vor kurzem lediglich die Geschwindigkeit von CPU-Implementierungen erreichen, da es viele bedinge Sprünge ( if-Anweisungen ) benötigt, die auf den Streamprozessoren der GPUs nur sehr langsam möglich sind. Die Rekursion muss in eine iterative Form überführt werden. Die Programmierbarkeit von GPUs hat sich im Zuge der letzten Entwicklungsschritte verbessert, sodass leistungsstärkere GPU-Raytracer verfügbar sind ( z.B. Nvidia Optix ).
Weblinks, Literatur:
http://www.codinghorror.com/blog/2008/03/real-time-raytracing.html
http://www.scarydevil.com/~peter/io/raytracing-vs-rasterization.html
http://www.pcper.com/article.php?aid=506&type=expert
Introduction to Real Time Ray Tracing, Präsentation
Realtime Ray Tracing and Interactive Global Illumination, Doktorarbeit
Large Ray Packets for Real-time Whitted Ray Tracing, PDF
Bildquellen:
Bild 1 (Diagramm): nachgezeichnet nach: http://www.codinghorror.com/blog/2008/03/real-time-raytracing.html
Bild 2 (Scheinwerfer): Ingo Wald, Realtime Ray Tracing and Interactive Global Illumination, Doktorarbeit
Bild 3 (Waldszene): Slussalek, Shirley, Mark, Stoll, Wald, Introduction to Real Time Ray Tracing, Präsentation, SIGGRAPH2005
Gute Flash-Spiele: evonets.com