Raytracing
Raytracing („Strahlverfolgung“, in englischer Schreibweise meist ray tracing, auch ray casting genannt) ist ein Oberbegriff für verschiedene Verfahren der 3D-Computergrafik, bei denen die Ausbreitung von Lichtstrahlen simuliert wird. Es ist neben Radiosity eines der großen, und, aufgrund seiner Flexibilität und Eleganz, auch das populärste Verfahren zur Bilderzeugung.
Ursprung und Bedeutung
Als Entwickler des Raytracing-Algorithmus gelten Appel †, Goldstein und Nagel*. 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. Verfahren wie Radiosity, aber auch 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.
†Appel, A., “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;
Goldstein, R.A., R. Nagel, “3-D Visual Simulation”, Simulation 16(1), 1971
Grundprinzip
Raytracing ist in erster Linie ein Verfahren zur Ermittlung der Sichtbarkeit von Objekten ab einem bestimmten Punkt im Raum.
Bei der Beschreibung einer Szene wird im dreidimensionalen Raum – neben den Primitiven wie Polygonen oder Kugeln – auch die Position eines Augpunktes sowie einer virtuellen Bildebene angegeben, die die Perspektive definieren, aus der die Szene betrachtet wird. Die Bildebene ist in Quadrate unterteilt, die den Pixeln des zu erzeugenden Rasterbildes entsprechen.
Es wird für jeden Pixel die Richtung des „Strahls“ (im Grunde eine Halbgerade) berechnet, die vom Augpunkt aus zum entsprechenden Pixel der Bildebene weist. Für jedes Primitiv der Szene wird nun mittels geometrischer Verfahren der eventuelle Schnittpunkt des Strahls mit dem Primitiv ermittelt. Dieser Arbeitsschritt ist das Herzstück des Raytracings. Dabei wird unter anderem gegebenenfalls die Entfernung vom Augpunkt zum Schnittpunkt berechnet. Der „Gewinner“, also das vom Augpunkt aus sichtbare Primitiv, ist dasjenige mit der geringsten Distanz.
Dass die Strahlen nicht wie in der Natur von den Lichtquellen, sondern vom Augpunkt ausgehen, spricht man auch von backward ray tracing1. Raytracing beschäftigt sich mit der Frage, woher das Licht kommt.
1Einige Publikationen sprechen allerdings kurioserweise auch von forward ray tracing.
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.
Algorithmus
Das Grundprinzip von Raytracing ist sehr einfach; die Programmierung eines einfachen Raytracers erfordert wenig Aufwand. In Pseudocode lässt sich das Prinzip folgendermaßen darstellen:
Strahl.Ursprung = Augpunkt
Für jedes (x,y)-Pixel der Rastergrafik
Strahl.Richtung = [3D-Koordinaten des Pixels der Bildebene]
- [Augpunkt]
MaxDistanz = ∞
Gewinner = (kein)
Für jedes Primitv p der Szene
Schnittpunkt = TestePrimitiv(p, Strahl)
Wenn Schnittpunkt.Distanz < MaxDistanz dann
MaxDistanz = Schnittpunkt.Distanz
Gewinner = p
Wenn Gewinner ≠ (kein) dann
Farbe des (x,y)-Pixels = Shade(Schnittpunkt, Strahl, p)
|
Hierbei testet TestePrimitiv ein Primitiv auf einen Schnittpunkt mit dem Strahl; Shade ermittelt die Farbe. Der Schnittpunkttest ist bei Kugeln 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äßt.
Jeder Raytracer, unabhängig von der verwendeten Raytracing-Variante, folgt einer ähnlichen Grundstruktur aus Hauptprogramm, Schnittpunkttest und Shader.
Beschleunigung
Bei der Bestimmung des dem Augpunkt nächsten Primitivs kann, wie im oben aufgeführten Code, 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 vom Strahl getroffen werden können. Da Schnittpunkttests die größte Laufzeit beim Raytracing verbrauchen, ist es wichtig, so wenig Primitive wie möglich gegen den Strahl zu testen, um die Gesamtlaufzeit gering zu halten.
Bei den Beschleunigungsverfahren wird die Szene meist in irgendeiner Form unterteilt 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 von Bechleunigungstechniken für Raytracing entwickelt. Beispiele für populäre Unterteilungen sind Voxel, BSP-Bäume oder Quader, die die Primitiven umschließen und eine Hierarchie bilden. Die Wahl gestaltet sich als schwierig, da die Effizienz der Techniken szenenabhängig und keine davon generell optimal ist. Die Entwicklung und Analyse von Beschleunigungsverfahren ist eines der Gebiete, auf denen beim Raytracing weiterhin Forschung betrieben wird. Die Komplexität dieser Techniken lassen einen Raytracer schnell zu einem großen Projekt anwachsen.
Erweiterungen
Einer der Gründe für den Erfolg des Raytracing-Verfahrens liegt in seiner Erweiterbarkeit. Das oben beschriebene primitive Verfahren wird praktisch nie angewandt. Es gibt mehrere Erweiterungen und Varianten, von denen einige hier kurz vorgestellt werden sollen.
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. Dies kann 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 läßt 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 muß 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 [1] entwickelt.
†Kay, D.S.: Transparency, Refraction and Ray Tracing for Computer Synthesized Images, M.S. Thesis, Cornell University, Ithaca NY 1979
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 simulieren, das 1984 von Cook et al. veröffentlicht wurde [2]. 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
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 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 [3] beschrieb James Kajyia die Rendergleichung, die die mathematische Basis für alle Methoden der globalen Belecuhtung 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 zuviel 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 Verfahren verwendet.
Forward Raytracing ist eine seltene Variante, bei der die Lichtstrahlen nicht vom Augpunkt, sondern von den Lichtstrahlen ausgesendet werden und auf die Bildebene treffen. Dadurch lassen sich bestimmte Effekte wie Kaustiken gut, andere Effekte jedoch nur sehr ineffizient simulieren.
Weitere Entwicklungen
Da sich einige Effekte nur vom Augpunkt, andere nur von den Lichtquellen aus gut simulieren lassen, wurden Algorithmen entwickelt, die beides kombinieren.
Bidirectional Path Tracing, unabhänig voneinander 1993 und 1994 von Lafortune/Willems [4] und Veach/Guibas [5] 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 [6]. 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 wurde 1995 von Jensen veröffentlicht [7]. 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, als er ermöglichte, die Beleuchtung als Vorbearbeitung zu speichern somit während des Rendervorgangs relativ schnell zu berechnen. Photon Mapping beseitigt viele Probleme der auf Path Tracing aufbauenden Algorithmen, ist jedoch in der Präzision nicht intuitiv kontrollierbar.
Besonderes
Neben den gängigen Varianten des Raytracings existieren noch Erweiterungen, die weitere Effekte ermöglichen. Einige Beispiele:
- Constructive solid geometry (CSG) ist ein verbreitetes Modellierverfahren, bei dem Objekte aus anderen Objekten zusammengesetzt werden. Ray tracing läßt sich relativ einfach um CSG-Funktionalität erweitern [8].
- Texture Mapping, Bump Mapping und Displacement Mapping sind ebenfalls für Raytracing möglich.
- Spektrales Rendering. – Die meisten gängigen Raytracer verwenden den RGB-Farbraum zur Darstellung von Farben, was physikalisch nicht immer korrekt ist. Indem für die Farbe eine von der Wellenlänge des Lichts abhängige Repräsentation verwendet wird, lassen sich Effekte wie Dispersion simulieren. Auch Polarisation und Fluoreszenz sind möglich [9].
- 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 hoher Helligkeitsdynamik problemlos darzustellen.
Einsatzgebiete
Raytracing-Berechnungen gelten als sehr zeitintensiv. So wird Raytracing 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, spielt Raytracing derzeit keine Rolle.
Dennoch existieren Bestrebungen, echtzeitfähige Raytracer zu implementieren, was bereits unter bestimmten Voraussetzungen mit SIMD- und Caching-optimierten Softwarelösungen gelungen ist [10]. Auf Hardware optimierte Implementierungen von Raytracing zeigen, dass die künftige breite Nutzung von Raytracing im Echtzeitbereich denkbar ist. Gegenüber Scanline-Renderern hat Raytracing mehrere Vorteile:
- Einfache Implementierung mit überschaubarer Komplexität
- Kein starres Schema wie bei der Render-Pipeline
- Leichtere Austauschbarkeit der Shader und dadurch erleichterte Implementierung neuer Shader
Einige bekannte Raytracing-fähige Renderer
|
Kommerzielle Programme: |
|
Freie Software: |
Literatur
- 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.
- 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.