Raytracing

Mit Raytracing berechnete Bilder

Raytracing (in englischer Schreibweise meist ray tracing) oder Strahlverfolgung ist ein auf der Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechnung, also zur Ermittlung der Sichtbarkeit von dreidimensionalen Objekten ab einem bestimmten Punkt im Raum. Ebenfalls mit Raytracing bezeichnet man mehrere Erweiterungen dieses grundlegenden Verfahrens, die den weiteren Weg von Strahlen nach dem Auftreffen auf Oberflächen berechnen.

Prominenteste Verwendung findet Raytracing in der 3D-Computergrafik. Hier ist der grundlegende Raytracing-Algorithmus ebenso wie Scanline Rendering eine Möglichkeit zur Darstellung einer 3D-Szene. Erweiterungen, die den Weg von Lichtstrahlen durch die Szene simulieren, dienen, ebenso wie das alternative Radiosity-Verfahren, der Berechnung der Lichtverteilung.

Weitere Anwendungsgebiete von Raytracing sind die Auralisation und Hochfrequenztechnik.

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 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. 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.

Einfache Formen des Raytracing berechnen nur die direkte Beleuchtung, also das direkt von den Lichtquellen eintreffende Licht. Raytracing wurde seit seiner ersten Verwendung in der Computergrafik jedoch mehrmals wesentlich erweitert. Höher entwickelte Formen berücksichtigen auch das indirekte Licht, das von anderen Objekten reflektiert wird; man spricht dann von einem globalen Beleuchtungsverfahren.

Heute verwenden alle hochwertigen Renderer (Computerprogramme zur Erzeugung von Bildern aus einer 3D-Szene) Raytracing, eventuell in Kombination mit weiteren Verfahren.

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

Grundprinzip

Die Erzeugung eines Rasterbildes aus einer 3D-Szene wird Rendern 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

Raytracing.svg 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 Renderprogramme lassen jedoch aus Gründen der Einfachheit nur Dreiecke als Primitiven zu, aus denen sich jedes beliebige Objekt zusammensetzen lässt.

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 = 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.

Raytracing-Voxel.svg, 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, sowie speziell darauf optimierter Unterteilungsschemas I. Wald u. A.: “Interactive Rendering with Coherent Ray Tracing”, Eurographics 2001 Proceedings A. Reshetov u. A.: “Multi-Level Ray Tracing Algorithm”, SIGGRAPH 2005 Proceedings. 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

Raytracing-Schattenstrahl.svg 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

Raytracing reflection.png 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 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.

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 R.L. Cook u. A.: “Distributed ray tracing”, SIGGRAPH 84 Proceedings. Die Idee ist, in verschiedenen Situationen statt eines Strahls 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

Spheres and Checkerboard.jpg 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 J. Kajiya: “The rendering equation”, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, 1986. 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 direkte Erweiterung des Path Tracing, bei der Strahlen sowohl vom Augpunkt als auch von den Lichtquellen aus gesendet und anschließend kombiniert werden 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. Die Auftreffpunkte des Lichtpfades werden als punktförmige virtuelle Lichtquellen zur Beleuchtung des jeweiligen Augpfades herangezogen. Das Verfahren bietet meist eine bessere Leistung als reines Path Tracing, vor allem bei der Berechnung von Kaustiken, beseitigt jedoch nicht vollständig dessen Probleme.

Metropolis Light Transport (MLT): ist eine Erweiterung des bidirektionalen Path Tracing und wurde 1997 von Veach und Guibas vorgestellt E. Veach, L.J. Guibas: “Metropolis Light Transport”, SIGGRAPH 97 Proceedings. MLT ist eine ausgeklügelte Methode, bei der Lichtstrahlen so ausgesendet werden, dass sie sich der Beleuchtung anpassen und die Szene „erkunden“. Die Idee des Verfahrens ist es, „gute“ Pfadkombinationen, über die viel Energie transportiert wird, nach ihrem Auffinden nicht sofort wieder zu verwerfen, sondern weiterzuverwenden. MLT bietet oft deutliche Geschwindigkeitsvorteile und vernünftige Ergebnisse bei Szenen, die mit anderen (vorherigen) Algorithmen nur schwer korrekt zu simulieren sind.

Glas-2000-enery.jpg.]]

Photon Mapping: wurde 1995 von Jensen veröffentlicht H.W. Jensen, N.J. Christensen: “Photon Maps in Bidirectional Monte Carlo Ray Tracing of Complex Objects”, Computers & Graphics 19(2), 1995. 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 auf 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

{| width="700px"

! style="background-color:#CEE2D8" | Raytracing-Verfahren Schatten Lichtreflexion und -brechung Beleuchtung Nur Verdeckungsberechnung Nein Nein Nein Simulation von Schatten
(mit nur einem Schattenstrahl) Nur harte Schatten Nein Nur direkte Beleuchtung Rekursives Raytracing Nur harte Schatten Nur bei spiegelnden Oberflächen Nur direkte Beleuchtung oder spiegelnde Reflexion Diffuses Raytracing Vollständig Nur bei spiegelnden/glänzenden Oberflächen Nur direkte Beleuchtung oder spiegelnde/glänzende Reflexion Path Tracing
(und nachfolgende Verfahren) Vollständig Vollständig Vollständig (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 P.R. Atherton: “A scan-line hidden surface removal procedure for constructive solid geometry”, SIGGRAPH 83 Proceedings.

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 A. Wilkie u. A.: “Combined Rendering of Polarization and Fluorescence Effects”, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, 2001.

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.

Siehe auch: Vierdimensionales Raytracing

Einsatzgebiete

Computergrafik

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 Mikroprozessoren wurde Raytracing bereits implementiert J. Schmittler u. A.: “A Hardware Architecture For Ray Tracing”, Graphics Hardware 2002 Proceedings. 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.

Weitere Anwendungsgebiete

Das grundlegende Raytracing-Prinzip zur Verdeckungsberechnung kann auf beliebige Anwendungsbereiche ausgeweitet werden, bei denen die Ausbreitung von Wellen in einer Szene simuliert werden soll. Strahlen repräsentieren dabei stets die Normalenvektoren zu einer Wellenfront. In der Auralisation und Hochfrequenztechnik versucht man, die Auswirkungen einer Szene auf die Akustik beziehungsweise auf ein elektromagnetisches Feld zu simulieren. Das Ziel ist es, für bestimmte Frequenzen den Energieanteil zu berechnen, der von einem Sender zu einem Empfänger über die verschiedenen möglichen Wege durch die Szene übertragen wird.

In der Akustik ist Raytracing neben der Spiegelschallquellenmethode und der Diffusschallberechnung eine Möglichkeit zur Lösung dieses Problems. Zur Simulation müssen die Materialeigenschaften der verschiedenen Körper sowie die Dämpfung des Schalls durch die Luft berücksichtigt werden.

Eine Möglichkeit zum Auffinden der Übertragungswege besteht darin, Strahlen von einer Quelle isotrop (in alle Richtungen) auszusenden, eventuell mit Energieverlust an den Gegenständen zu reflektieren und die Gesamtenergie der auf den Empfänger auftreffenden Strahlen zu ermitteln. Diese Methode wird Ray launching genannt. Strahlen können auch eine bestimmte „Form“ – etwa die einer Röhre – haben, um punktförmige Empfänger simulieren zu können. Der Nachteil dieser Methode ist ihre Langsamkeit, da viele Strahlen nie den Empfänger erreichen und für präzise Statistiken eine hohe Anzahl vonnöten ist.
Ein weiteres Problem ergibt sich dadurch, dass die Wellenlänge oft nicht gegenüber den Abmessungen der Körper innerhalb einer Szene vernachlässigbar ist. Sofern die Beugung von Strahlen nicht berücksichtigt wird, kann es daher zu merklichen Fehlern in der Simulation kommen.

Literatur

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
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
Matt Pharr, Greg Humphreys: Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann 2004, ISBN 01-2553-180-X

Weblinks

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

Sonstiges:

Artikel in Fachzeitschriften

3D-Computergrafik | 3D-Computergrafik | Algorithmus

Gourt Home::Gourt :: Raytracing