Raytracing

Mit Raytracing berechnete Bilder

Strahlverfolgung oder Raytracing (in englischer Schreibweise meist ray tracing) ist ein Oberbegriff für verschiedene Algorithmen der 3D-Computergrafik, bei denen die Ausbreitung von Lichtstrahlen simuliert wird. Wie auch Scanline Rendering ist es ein Algorithmus zur Szenendarstellung. Neben Radiosity ist es außerdem eines der großen und, aufgrund seiner Flexibilität und Eleganz, auch das populärste Verfahren zur Berechnung der Lichtverteilung.

Ursprung und Bedeutung

Vor der Entwicklung von Raytracing bestand das junge Gebiet der 3D-Computergrafik im Wesentlichen aus einer Reihe von „Programmiertricks“, die versuchten, die Schattierung von beleuchteten Objekten nachzuahmen. Raytracing war der erste Algorithmus auf diesem Gebiet, der einen gewissen physikalischen Sinn ergab.

Als Entwickler des Raytracing-Algorithmus gelten Appel, Goldstein und Nagel, die den Algorithmus Ende der 1960er Jahre veröffentlichten. Raytracing basiert jedoch auf der geometrischen Optik, bei der das Licht als eine Gruppe von Strahlen verstanden wird. Die beim Raytracing verwendeten Techniken wurden bereits wesentlich früher, unter anderem von Linsenherstellern, verwendet.

Raytracing im engeren Sinne bezeichnet die einfachste Form, bei der allerdings nur die direkte Beleuchtung simuliert wird. Raytracing wurde seit seiner ersten Verwendung in der Computergrafik mehrmals wesentlich erweitert. Höher entwickelte Formen des Raytracings wie Photon Mapping berücksichtigen auch das indirekte Licht, das von anderen Objekten reflektiert wird; man spricht dann von einem globalen Beleuchtungsverfahren.

Heute verwenden alle hochwertigen Renderer Raytracing, eventuell in Kombination mit weiteren Verfahren.

Der Begriff Raycasting bezeichnet eine vereinfachte Form des Raytracings, wird teils aber auch synonym dazu gebraucht.

Einsatzgebiete

Raytracing-Berechnungen gelten als sehr zeitintensiv. Ein Bild mit Raytracing zu berechnen, kann – abhängig von der verwendeten Technik, der Szenenkomplexität und der verwendeten Hardware – bis zu mehreren Stunden, in Einzelfällen sogar mehrere Tage dauern. Dies lässt jedoch außer acht, dass die Geschwindigkeit von Raytracing in Relation zur erreichten Bildqualität gesetzt werden muss. Für die anspruchsvollen Qualitätsanforderungen der realistischen Bildsynthese gibt es, insbesondere bei komplizierten Szenen mit beliebigen Materialien, keine Alternative zu Raytracing.

Raytracing wird vornehmlich bei der Erzeugung von Darstellungen eingesetzt, bei denen eher die Qualität als die Berechnungszeit im Vordergrund steht. In Bereichen wie der Virtuellen Realität, in der räumliche Darstellungen in Echtzeit berechnet werden müssen, konnte sich Raytracing bisher nicht durchsetzen. Es wurde allerdings manchmal von der Demoszene genutzt.

Dennoch existieren Bestrebungen, echtzeitfähige Raytracer für komplexe Szenen zu implementieren, was bereits unter bestimmten Voraussetzungen mit prozessor- und speicheroptimierten Softwarelösungen gelungen ist. Auf Hardware optimierte Implementierungen von Raytracing zeigen, dass die künftige breite Nutzung von Raytracing im Echtzeitbereich denkbar ist. Auch direkt auf Chips wurde Raytracing bereits implementiert. Gegenüber Scanline-Renderern hat Raytracing mehrere Vorteile:

einfache Implementierung mit überschaubarer Komplexität;
im Gegensatz zur Render-Pipeline eine hohe Flexibilität;
leichtere Austauschbarkeit der Shader und dadurch erleichterte Implementierung neuer Shader.

Grundprinzip

Die Erzeugung eines Rasterbildes aus einer dreidimensionalen Szene wird Rendering oder Bildsynthese genannt. Voraus geht die Erstellung einer solchen Szene vom Benutzer mit Hilfe eines 3D-Modellierungswerkzeugs.

In der Szenenbeschreibung werden zumindest folgende Daten angegeben:

die Position der elementaren Primitiven, wie Polygone oder Kugeln, aus denen sich die Objekte der Szene zusammensetzen;
die lokalen Beleuchtungsmodelle und deren Parameter, die die Farben und Materialien der einzelnen Objekte der Szene bestimmen;
die Lichtquellen der Szene.

Daneben wird beim Raytracing auch die Position eines Augpunktes sowie einer Bildebene angegeben, die zusammen die Perspektive angeben, aus der die Szene betrachtet wird. Der Augpunkt ist ein Punkt im Raum, der der Position einer virtuellen Kamera oder allgemein, eines Beobachters entspricht. Die Bildebene ist ein virtuelles Rechteck, das sich in einiger Entfernung zum Augpunkt befindet. Sie ist die dreidimensionale Entsprechung des zu rendernden Rasterbildes im Raum. Die Bildebene kann man sich in Quadrate unterteilt denken, die den Pixeln des zu erzeugenden Rasterbildes entsprechen.

Verdeckungsberechnung

Datei:Raytracing.png

Das Raytracing-Prinzip: Vom Augpunkt aus wird ein Strahl durch ein Pixel der Bildebene gesendet und auf den nächsten Schnittpunkt mit der Szene getestet. Das Pixel wird entsprechend eingefärbt.

Raytracing ist in erster Linie ein Verfahren zur Verdeckungsberechnung, also zur Ermittlung der Sichtbarkeit von Objekten ab dem Augpunkt. Das Grundprinzip ist recht einfach.

Raytracing arbeitet mit einer Datenstruktur, Strahl genannt, die den Anfangspunkt und die Richtung einer Halbgeraden im Raum angibt. Es wird für jedes Pixel die Richtung des Strahls berechnet, der vom Augpunkt aus zum entsprechenden Pixel der Bildebene weist. Für jedes Primitiv der Szene wird nun mittels geometrischer Verfahren der eventuelle Schnittpunkt, bei dem der Strahl auf das Primitiv trifft, ermittelt. Dabei wird gegebenenfalls die Entfernung vom Augpunkt zum Schnittpunkt berechnet. Der „Gewinner“, also das vom Augpunkt aus sichtbare Primitiv, ist dasjenige mit der geringsten Distanz.

Das Prinzip der Aussendung der Strahlen vom Augpunkt aus ähnelt dem Aufbau einer Lochkamera, bei der ein Objekt auf einem Film abgebildet wird. Beim Raytracing sind allerdings „Film“ (Bildebene) und „Loch“ (Augpunkt) vertauscht. Ähnlich wie bei der Lochkamera bestimmt der Abstand zwischen Bildebene und Augpunkt die „Brennweite“ und damit den Blickwinkel, mit dem die Szene betrachtet wird.

Da die Strahlen nicht wie in der Natur von den Lichtquellen, sondern vom Augpunkt ausgehen, spricht man auch von backward ray tracing. Raytracing beschäftigt sich mit der Frage, woher das Licht kommt (einige Publikationen nennen das Verfahren allerdings kurioserweise auch forward ray tracing).

Schnittpunkttests

Der oben erwähnte Test auf einen eventuellen Schnittpunkt von Strahl und Primitive ist das Herzstück des Raytracings. Solche Tests lassen sich für eine Vielzahl von Primitiventypen formulieren. Neben Dreiecken und Kugeln sind unter anderem Zylinder, Quadriken oder gar Fraktale möglich.

Bei Kugeln ist der Schnittpunkttest eine relativ kurze und einfache Prozedur, was die Popularität dieser Objekte auf Raytracing-Testbildern erklärt. Viele kommerzielle Renderprogramme lassen jedoch aus Gründen der Einfachheit nur Dreiecke als Primitiven zu, aus denen sich jedes beliebige Objekt zusammensetzen lässt.

Beispiel für einen Schnittpunkttest mit einer Kugel

Eine Hohlkugel mit dem Radius r ist durch folgende Gleichung definiert:

x^{2}+y^{2}+z^{2}=r^{2}

.

Der Strahl mit dem Anfangspunkt $\mathbf {p_{0}}$ und der Richtung ${\vec {d}}$ ist durch folgende vektorielle Geradengleichung definiert, wobei $t$ für die Entfernung vom Anfangspunkt steht:

\mathbf {p_{0}} +t\cdot {\vec {d}}

(mit

t\geq 0

).

Nun muss man die oben genannte vektorielle Geradengleichung in die Kugelgleichung einsetzen. Da eine Gerade eine Kugel an maximal zwei Punkten schneidet, läuft diese Umformung am Ende auf eine quadratische Gleichung hinaus.

(p_{x}+t\cdot d_{x})^{2}+(p_{y}+t\cdot d_{y})^{2}+(p_{z}+t\cdot d_{z})^{2}=r^{2}

Nach dem Ausmultiplizieren und Umstellen zur allgemeinen Form einer quadratischen Gleichung ergibt sich:

(d_{x}^{2}+d_{y}^{2}+d_{z}^{2})\cdot t^{2}+2\cdot (d_{x}\cdot p_{x}+d_{y}\cdot p_{y}+d_{z}\cdot p_{z})\cdot t+p_{x}^{2}+p_{y}^{2}+p_{z}^{2}-r^{2}=0

Die eventuellen Lösungen – die Entfernungen $t_{1}$ und $t_{2}$ zu den Schnittpunkten – können durch Einsetzen in die allgemeine Lösungsformel

t_{1,2}={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}

berechnet werden, wobei	$a=d_{x}^{2}+d_{y}^{2}+d_{z}^{2}$ ,
	$b=2\cdot (d_{x}\cdot p_{x}+d_{y}\cdot p_{y}+d_{z}\cdot p_{z})$ und
	$c=p_{x}^{2}+p_{y}^{2}+p_{z}^{2}-r^{2}$ ist.

Wenn der Wert unter der Wurzel negativ ist, so besitzt die Gleichung keine Lösung, und der Strahl verfehlt die Kugel. Bei genau einer Lösung ist der Strahl tangential zur Kugeloberfläche; bei zwei Lösungen trifft er auf die Kugel.

Da nur der nächste Schnittpunkt zählt, wird bei zwei Lösungen das kleinere $t$ größer 0 verwendet. Der Schnittpunkt kann durch Einsetzen von $t$ in die allgemeine vektorielle Geradengleichung berechnet werden.

Hinweis: Die hier vorgestellte Methode ist nur eine Möglichkeit; für die Kugel gibt es noch einen effizienteren Schnittpunkttest.

Shading

Bei der Ermittlung des nächsten Primitivs wird nicht nur der Schnittpunkt und seine Distanz zum Augpunkt, sondern auch die Normale des Primitivs am Schnittpunkt berechnet. Damit sind alle Informationen vorhanden, um die zum Augpunkt reflektierte „Lichtstärke“ und somit die Farbe zu ermitteln. Dabei werden auch die Beschreibungen der Lichtquellen der Szene genutzt. Den Berechnungen liegen lokale Beleuchtungsmodelle zugrunde, die die Materialbeschaffenheit eines Objekts simulieren. Diesen Teil des Renderers, der für die Ermittlung der Farbe zuständig ist, nennt man Shader.

Beispielcode

Die Programmierung eines einfachen Raytracers erfordert wenig Aufwand. In Pseudocode lässt sich das Prinzip folgendermaßen darstellen:

Prozedur Bild_Rendern
    Strahl.Ursprung = Augpunkt
    Für jedes (x,y)-Pixel der Rastergrafik
        Strahl.Richtung = [3D-Koordinaten des Pixels der Bildebene] - Augpunkt
        Farbe des (x,y)-Pixels = Farbe_aus_Richtung(Strahl)

Funktion Farbe_aus_Richtung(Strahl)
    Schnittpunkt = Nächster_Schnittpunkt(Strahl)
    Wenn Schnittpunkt.Gewinner ≠ (kein) dann
        Farbe_aus_Richtung = Farbe_am_Schnittpunkt(Strahl, Schnittpunkt)

Funktion Nächster_Schnittpunkt(Strahl)
    MaxDistanz = ∞
    Schnittpunkt.Gewinner = (kein)
    Für jedes Primitiv der Szene
        Schnittpunkt = Teste_Primitiv(Primitiv, Strahl)
        Wenn Schnittpunkt.Distanz < MaxDistanz dann
            MaxDistanz = Schnittpunkt.Distanz
            Schnittpunkt.Gewinner = Primitiv
    Nächster_Schnittpunkt = Schnittpunkt

Jeder Raytracer, unabhängig von der verwendeten Raytracing-Variante, folgt einer ähnlichen Struktur, die einen Schnittpunkttest (Teste_Primitiv) und einen Shader (Farbe_am_Schnittpunkt) enthält.

Performance

Beschleunigungstechniken

Bei der Bestimmung des ersten Primitivs, auf das ein Strahl trifft, kann, wie im weiter oben aufgeführten Beispielcode, jedes Primitiv der Szene gegen den Strahl getestet werden. Dies ist jedoch nicht grundsätzlich erforderlich, wenn bekannt ist, dass gewisse Primitive sowieso nicht in der Nähe des Strahls liegen und daher nicht getroffen werden können. Da Schnittpunkttests die größte Laufzeit beim Raytracing beanspruchen, ist es wichtig, so wenig Primitive wie möglich gegen den Strahl zu testen, um die Gesamtlaufzeit gering zu halten.

Beispiel für eine Beschleunigungstechnik: Voxelgitter (Ansicht von oben). Nur die Primitiven der Voxel, durch die der Strahl wandert (grau eingefärbt), müssen auf einen Schnittpunkt getestet werden. Insgesamt müssen nur die beiden Dreiecke getestet werden.

Bei den Beschleunigungsverfahren wird die Szene meist in irgendeiner Form automatisch aufgeteilt und die Primitiven diesen Unterteilungen zugewiesen. Wenn ein Strahl durch die Szene wandert, so wird er nicht gegen die Primitiven, sondern zunächst gegen die Unterteilungen getestet. Dadurch muss der Strahl nur noch gegen die Primitive derjenigen Unterteilung getestet werden, die der Strahl kreuzt.

Es wurden eine Vielzahl derartiger Beschleunigungstechniken für Raytracing entwickelt. Beispiele für Unterteilungsschemas sind Voxelgitter, BSP-Bäume, sowie Quader, die die Primitiven umschließen und eine Hierarchie bilden. Mischformen dieser Techniken sind ebenfalls populär. Auch für Animationen gibt es spezielle Beschleunigungstechniken. Die Komplexität dieser Techniken lassen einen Raytracer schnell zu einem größeren Projekt anwachsen.
Die Wahl einer bestimmten Technik gestaltet sich als schwierig, da deren Effizienz szenenabhängig und keine generell optimal ist. Allerdings reduziert jedes dieser Verfahren die Laufzeit enorm und macht Raytracing erst zu einem praktikablen Algorithmus. Die Entwicklung und Analyse von Beschleunigungsverfahren ist eines der Gebiete, auf denen beim Raytracing weiterhin Forschung betrieben wird. Mehrfach festgestellt wurde jedoch, dass die asymptotische Laufzeit von Raytracing in Abhängigkeit von der Anzahl der Primitiven logarithmisch ist.

Es wurde gezeigt, dass auf modernen Rechnern nicht die Prozessorleistung, sondern die Speicherzugriffe den Flaschenhals beim Raytracing darstellen. Durch sorgfältige Nutzung von Caching durch den Algorithmus ist es möglich, die Laufzeit wesentlich zu verringern. Ebenfalls möglich ist die Nutzung der SIMD-Fähigkeit moderner Prozessoren, die parallele Berechnungen ermöglicht. Damit ist das gleichzeitige Verfolgen mehrerer, in „Paketen“ zusammengefasster, Strahlen möglich. Grund dafür ist, dass die vom Augpunkt ausgesendeten Strahlen meist sehr ähnlich sind, also meist die gleichen Objekte schneiden. Mit dem Befehlssatz SSE etwa können vier Strahlen gleichzeitig auf einen Schnittpunkt mit einem Primitiv getestet werden, was diese Berechnung um ein Vielfaches beschleunigt. Auf entsprechenden Hardwareimplementationen – zum Beispiel auf FPGAs – können auch größere Pakete mit über 1000 Strahlen verfolgt werden. Allerdings büßen Caching- und SIMD-Optimierungen bei erweiterten Formen des Raytracings viel von ihrem Geschwindigkeitsvorteil ein.

Weiterhin ist es möglich, den gesamten Raytracing-Vorgang zu parallelisieren. Dies lässt sich etwa dadurch trivial bewerkstelligen, dass verschiedene Prozessoren bzw. Maschinen unterschiedliche Ausschnitte des Bildes rendern. Lediglich gewisse Beschleunigungstechniken oder Erweiterungen müssen angepasst werden, um parallelisierungstauglich zu sein.

Speicherbedarf

Das grundlegende Raytracing-Verfahren benötigt kaum Speicher. Jedoch belegt die Szene selbst, die sich heutzutage bei komplexen Szenen oft aus mehreren Millionen Primitiven zusammensetzt, sehr viel Speicher und kann mehrere Gigabyte umfassen. Hinzu kommt der mehr oder weniger hohe zusätzliche Speicherbedarf der Beschleunigungstechniken. Da solch große Szenen nicht vollständig in den Arbeitsspeicher des Rechners passen, wird häufig Swapping nötig.

Bei größeren Objekten, die mehrmals in der Szene vorhanden sind und sich nur durch ihre Position und Größe unterscheiden (etwa bei einem Wald voller Bäume), muss nicht die gesamte Geometrie neu gespeichert werden. Durch diese Instancing genannte Technik lässt sich bei bestimmten Szenen erheblich Platz einsparen.

Ebenso lässt sich der Speicherbedarf durch eine Wahl kompakterer Repräsentationen der Szenengeometrie drastisch verringern. So wurden punktbasierte Repräsentationen entwickelt, die gegenüber den herkömmlichen Dreiecksprimitiven weniger Speicher belegen, bisher jedoch keine weite Verbreitung gefunden haben.

Erweiterungen

Einer der Gründe für den Erfolg des Raytracing-Verfahrens liegt in seiner natürlichen Erweiterbarkeit. Das oben beschriebene primitive Verfahren ist für die heutigen Anforderungen der Bildsynthese unzureichend. Mit steigender Rechenleistung und zunehmender Inspiration aus der Physik – vor allem der Optik und der Radiometrie – kamen mehrere Erweiterungen und Varianten auf, von denen einige hier kurz vorgestellt werden sollen.

Grundsätzlich gilt, dass mit jeder Erweiterung die erreichbare Qualität der gerenderten Bilder sowie der relative Zeitbedarf stark anstieg und mit Path Tracing das Maximum erreichte. Erst nachfolgende Entwicklungen zielten darauf ab, den Zeitaufwand von Path Tracing zu verringern, ohne an Qualität einzubüßen.

Schatten

Datei:Raytracing-Schattenstrahl.png

Simulation von Schatten

Aufgrund der Flexibilität des Raytracing-Algorithmus ist es möglich, Lichtstrahlen nicht nur vom Augpunkt, sondern auch von beliebigen anderen Punkten des Raums auszusenden. Wie Appel bereits 1968 demonstrierte, kann dies dazu benutzt werden, Schatten zu simulieren.

Ein beliebiger Punkt einer Oberfläche befindet sich genau dann im Schatten, wenn sich zwischen ihm und der Lichtquelle ein Objekt befindet. Indem vom Schnittpunkt an der Oberfläche ein Schattenstrahl in Richtung der Lichtquelle ausgesendet wird, lässt sich bestimmen, ob ein Objekt dessen Weg kreuzt. Ist dies der Fall, so befindet sich der Schnittpunkt im Schatten und es wird als Helligkeit des Strahls 0 zurückgegeben. Im anderen Fall findet normales Shading statt.

Rekursives Raytracing

Mit rekursivem Raytracing berechnetes Bild

Raytracing lässt sich nicht nur auf einfache lichtundurchlässige, sondern auch auf durchsichtige und spiegelnde, reflektierende Objekte anwenden. Dabei werden weitere Lichtstrahlen von den Schnittpunkten ausgesendet. Bei spiegelnden Flächen etwa muss dabei lediglich die Richtung des von der Fläche ausgehenden Strahls gemäß dem Reflexionsgesetz (Einfallswinkel ist gleich Reflexionswinkel) berücksichtigt und ein entsprechender Reflexionsstrahl errechnet werden.

Bei lichtdurchlässigen Objekten wird ein Strahl gemäß dem Brechungsgesetz ausgesendet, diesmal ins Innere des betreffenden Objektes. Generell reflektieren transparente Objekte auch einen Teil des Lichts. Die relativen Farbanteile des reflektierten und des gebrochenen Strahls lassen sich mit den Fresnelschen Formeln berechnen. Diese Strahlen werden auch Sekundärstrahlen genannt.

Da die Sekundärstrahlen auf weitere Objekte fallen können, wird der Algorithmus rekursiv aufgerufen, um mehrfache Spiegelungen und Lichtbrechungen zu ermöglichen. Die hierarchische Gesamtheit der Aufrufe wird auch Renderbaum genannt.

Rekursives Raytracing wurde um 1980 von Kay und Whitted entwickelt.

In Pseudocode sieht der Shader beim rekursiven Raytracing in etwa wie folgt aus:

Funktion Farbe_am_Schnittpunkt(Strahl, Schnittpunkt)
    Wenn Schnittpunkt.Gewinner.Material = spiegelnd oder transparent dann
        Reflektierter_Anteil = Fresnel(Strahl, Schnittpunkt)
        Farbe = Reflektierter_Anteil × Farbe_aus_Richtung([Reflexionsstrahl])
                + (1 - Reflektierter_Anteil) × Farbe_aus_Richtung([Gebrochener Strahl])
    ansonsten
        Farbe = 0
        Für jede Lichtquelle
            Schattenstrahl = Lichtquelle.Position - Schnittpunkt.Position
            SchattenSchnittpunkt = Nächster_Schnittpunkt(Schattenstrahl)
            Wenn SchattenSchnittpunkt.Gewinner ≠ (kein) dann
                Farbe = Farbe + Direkte_Beleuchtung(Strahl, Lichtquelle)
    Farbe_am_Schnittpunkt = Farbe

Der Rest des Programms kann wie beim einfachen Raytracing bleiben. Die hier aufgerufene Funktion Farbe_aus_Richtung kann wiederum Farbe_am_Schnittpunkt aufrufen, woraus der rekursive Charakter des Verfahrens deutlich wird.

Diffuses Raytracing

Hauptartikel: Diffuses Raytracing

Rekursives Raytracing ermöglicht neben Lichtbrechung und -reflexion die Simulation von harten Schatten. In Wirklichkeit haben Lichtquellen jedoch eine bestimmte Größe, was dazu führt, dass Schatten weich und verschwommen wirken.

Dieser Effekt, sowie Antialiasing, glänzende Reflexion und mehr, lassen sich mit diffusem Raytracing (auch stochastisches Raytracing oder distributed ray tracing genannt) simulieren, das 1984 von Cook u. A. veröffentlicht wurde. Die Idee ist, statt eines Strahls in verschiedenen Situationen mehrere Strahlen auszusenden und aus den errechneten Farben den Mittelwert zu bilden. Beispielsweise lassen sich weiche Schatten mit Kern- und Halbschatten erzeugen, indem die Richtungen der Schattenstrahlen zufällig verteilt die Oberfläche der Lichtquelle abtasten. Der Nachteil ist, dass dabei Bildrauschen entsteht, wenn zu wenig Strahlen verwendet werden. Es gibt jedoch Möglichkeiten wie Importance Sampling, die das Rauschen reduzieren. Auch Photon Mapping lässt sich dazu verwenden, das Rauschen weiter zu verringern.

Path Tracing und Forward Raytracing

Beispielbild für Lichtbrechung (links) und Reflexion (rechts), hier mit globaler Beleuchtung

Hauptartikel: Path Tracing

Obwohl diffuses Raytracing zahlreiche Effekte ermöglicht, ist es immer noch nicht in der Lage, die globale Beleuchtung mit Effekten wie diffuser Interreflexion und Kaustiken (durch Bündelung von Licht erzeugte helle Lichtflecken) zu simulieren. Dies liegt daran, dass zwar bei spiegelnden Reflexionen, nicht jedoch bei diffusen Oberflächen Sekundärstrahlen ausgesendet werden.

In seiner 1986 veröffentlichten Publikation beschrieb James Kajiya die Rendergleichung, die die mathematische Basis für alle Methoden der globalen Beleuchtung bildet. Dabei zeigte er, dass zur globalen Beleuchtung Sekundärstrahlen von allen Oberflächen ausgesendet werden müssen. Daneben wies er auch darauf hin, dass ein Renderbaum den Nachteil hat, dass zu viel Arbeit für die Berechnungen in großer Hierarchietiefe verschwendet wird und es besser ist, jeweils einen einzigen Strahl auszusenden. Diese Methode ist heute als Path Tracing bekannt, da ein Strahl sich vom Augpunkt aus seinen „Weg“ durch die Szene sucht. Das Supersampling findet einzig auf Pixelebene statt. Path Tracing hat eine rigorose mathematische und physikalische Basis.

Obwohl Path Tracing theoretisch die globale Beleuchtung simulieren kann, nimmt die Effizienz des Verfahrens bei kleinen Lichtquellen ab. Insbesondere Kaustiken und deren Reflexionen sind mit Path Tracing sehr verrauscht. Deshalb werden meist andere, auf Path Tracing basierende Verfahren oder Erweiterungen verwendet.

Forward Raytracing ist eine seltene Variante, bei der die Lichtstrahlen nicht vom Augpunkt, sondern von den Lichtquellen ausgesendet werden. Die Pixel, die vom Strahl auf der Bildebene getroffen werden, werden eingefärbt. Dadurch lassen sich bestimmte Effekte wie Kaustiken gut, andere Effekte jedoch nur sehr ineffizient simulieren, da viele Strahlen die Bildebene verfehlen.

Weitere Entwicklungen

Da sich einige Effekte nur vom Augpunkt, andere nur von den Lichtquellen aus gut simulieren lassen, wurden Algorithmen entwickelt, die beide Methoden kombinieren. Das Ziel ist es, Szenen mit beliebig komplexer Lichtverteilung und -reflexion effizient rendern zu können.

Bidirektionales Path Tracing,: unabhängig voneinander 1993 und 1994 von Lafortune/Willems und Veach/Guibas entwickelt, ist eine Variante des Path Tracing, bei der Strahlen sowohl vom Augpunkt als auch von den Lichtquellen aus gesendet und anschließend kombiniert werden. Es bietet meist eine bessere Leistung als reines Path Tracing, beseitigt jedoch nicht vollständig dessen Probleme.

Metropolis Light Transport (MLT): wurde 1997 von Veach und Guibas vorgestellt. MLT ist eine ausgeklügelte Methode, bei der Lichtstrahlen so ausgesendet werden, dass sie sich der Beleuchtung anpassen und die Szene „erkunden“. MLT bietet oft vernünftige Ergebnisse bei Szenen, die mit anderen (vorherigen) Algorithmen nur schwer korrekt zu simulieren sind.

Photon Mapping ermöglicht die effiziente Simulation von Kaustiken

Photon Mapping: wurde 1995 von Jensen veröffentlicht. Das Verfahren besteht im Aussenden von Partikeln von den Lichtquellen aus und deren Speicherung in einer speziellen, von der Geometrie unabhängigen Struktur. Dieser Algorithmus war insofern ein Durchbruch, weil er es ermöglicht, die Beleuchtung in einem Vorbearbeitungsschritt zu speichern und diese während des Rendervorgangs relativ schnell zu rekonstruieren.

Photon Mapping ist kein eigenständiges Rendering-Verfahren, sondern dient der Ergänzung von anderen Raytracing-Methoden – entweder, um diffuses Raytracing um globale Beleuchtung zu erweitern, oder um den Zeitaufwand bei Path Tracing zu verringern und andere Probleme zu lösen. Ein Nachteil von Photon Mapping ist jedoch, dass es in der Präzision nur schwer intuitiv kontrollierbar ist.

Anders als (bidirektionales) Path Tracing und MLT hat Photon Mapping schnell Verbreitung in diversen Softwarepaketen gefunden.

Übersicht

Raytracing-Verfahren	Schatten	Lichtreflexion und -brechung	Beleuchtung
Nur Verdeckungsberechnung	-	-	-
Simulation von Schatten (mit nur einem Schattenstrahl)	Nur harte Schatten	-	Nur direkte Beleuchtung
Rekursives Raytracing	Nur harte Schatten	Ja (Lichtreflexion nur von spiegelnden Oberflächen)	Nur direkte Beleuchtung oder spiegelnde Reflexion
Diffuses Raytracing	Ja (echte Schatten)	Ja (Lichtreflexion nur von spiegelnden/glänzenden Oberflächen)	Nur direkte Beleuchtung oder spiegelnde/glänzende Reflexion
Path Tracing (und nachfolgende Verfahren)	Ja (echte Schatten)	Ja (Lichtreflexion von allen Oberflächen)	Direkte und indirekte Beleuchtung von allen Oberflächen (Globale Beleuchtung)

Besonderes

Die angeführten gängigen Varianten des Raytracings lassen sich erweitern, um zusätzliche Effekte zu ermöglichen. Einige Beispiele:

Constructive Solid Geometry (CSG): ist ein verbreitetes Modellierverfahren, bei dem Objekte aus anderen Objekten zusammengesetzt werden. Raytracing lässt sich relativ einfach um CSG-Funktionalität erweitern.

Texture Mapping: sowie Displacement Mapping und Bumpmapping sind ebenfalls für Raytracing möglich. Bei letzterem Verfahren muss allerdings – im Gegensatz zu Scanline Rendering – darauf geachtet werden, dass die erzeugten Reflexionsrichtungen stets vom Objekt weg weisen.

Volumenstreuung: ermöglicht die realistische Simulation teilweise durchscheinender und das Licht streuender Objekte. Dazu gehören beispielsweise Milch oder Blätter, aber auch das Himmelsblau und atmosphärische Bedingungen.

Spektrales Rendering: Die meisten gängigen Raytracer verwenden den RGB-Farbraum zur Darstellung von Farben, was nur eine Annäherung an das kontinuierliche Lichtspektrum darstellt und nicht immer physikalisch plausibel ist. Indem für die Farbe eine von der Wellenlänge des Lichts abhängige Repräsentation verwendet wird, lassen sich Effekte wie Metamerie und Dispersion simulieren. Auch Polarisation und Fluoreszenz sind möglich.

Tone mapping: Indem HDRIs als Rasterformat verwendet werden, ist es möglich, Helligkeit und Kontrast von gerenderten Bildern nachträglich ohne Qualitätsverlust beliebig zu verändern. Daneben ist es möglich, durch Tone mapping Szenen mit großen Helligkeitsunterschieden problemlos darzustellen.

Literatur

Bücher:

Andrew S. Glassner: An Introduction to Ray tracing. Morgan Kaufmann 1989, ISBN 01-2286-160-4
Andrew S. Glassner: Principles of Digital Image Synthesis. Morgan Kaufmann 1995, ISBN 15-5860-276-3
Henrik Wann Jensen, Realistic Image Synthesis Using Photon Mapping. AK Peters 2001, ISBN 15-688-1147-0
Tomas Akenine-Möller, Eric Haines: Real-Time Rendering, AK Peters, 2^nd edition 2002, ISBN 15-6881-182-9
Philip Dutré, Philippe Bekaert, Kavita Bala: Advanced Global Illumination. AK Peters 2003, ISBN 15-6881-177-2
Matt Pharr, Greg Humphreys: Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann 2004, ISBN 01-2553-180-X

Erwähnte Veröffentlichungen:

A. Appel: “Some Techniques for Shading Machine Renderings of Solids”, Proceedings of the Spring Joint Computer Conference, 1968
Mathematical Applications Group, Inc.: “3-D Simulated Graphics Offered by Service Bureau”, Datamation 13(1), 1969
R.A. Goldstein, R. Nagel: “3-D Visual Simulation”, Simulation 16(1), 1971
D.S. Kay: Transparency, Refraction and Ray Tracing for Computer Synthesized Images, M.S. Thesis, Cornell University, Ithaca NY, 1979
T. Whitted: “An Improved Illumination Model for Shaded Display”, Communications of the ACM 23(6), 1980
P.R. Atherton: “A scan-line hidden surface removal procedure for constructive solid geometry”, SIGGRAPH 83 Proceedings
R.L. Cook u. A.: “Distributed ray tracing”, SIGGRAPH 84 Proceedings
J. Kajiya: “The rendering equation”, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, 1986
E.P. Lafortune, Y.D. Willems: “Bi-Directional Path Tracing”, Proceedings of Compugraphics, 1993
E. Veach, L.J. Guibas, “Bidirectional Estimators for Light Transport”, Eurographics Rendering Workshop Proceedings, 1994
H.W. Jensen, N.J. Christensen: “Photon Maps in Bidirectional Monte Carlo Ray Tracing of Complex Objects”, Computers & Graphics 19(2), 1995
E. Veach, L.J. Guibas: “Metropolis Light Transport”, SIGGRAPH 97 Proceedings
A. Wilkie u. A.: “Combined Rendering of Polarization and Fluorescence Effects”, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, 2001
I. Wald u. A.: “Interactive Rendering with Coherent Ray Tracing”, Eurographics 2001 Proceedings
J. Schmittler u. A.: “A Hardware Architecture For Ray Tracing”, Graphics Hardware 2002 Proceedings

Weblinks

Einige Konferenzen und Magazine, die unter anderem Raytracing zum Inhalt haben:

Sonstiges: