Raytracing

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Raytracing oder Strahlenverfolgung (in englischer Schreibweise meist ray tracing, seltener ray shooting) ist ein auf der Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechnung, also zur Ermittlung der Sichtbarkeit von dreidimensionalen Objekten von einem bestimmten Punkt im Raum aus. 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 Radiosity-Verfahren, der Berechnung der Lichtverteilung.

Weitere Anwendungsgebiete von Raytracing sind die Auralisation und Hochfrequenztechnik.

Mit Raytracing berechnetes Bild

[Bearbeiten] 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.^[1]^[2]^[3] 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.

[Bearbeiten] 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 Primitive, 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. Rasterförmig verteilte Punkte auf der Bildebene entsprechen den Pixeln des zu erzeugenden Rasterbildes.

[Bearbeiten] Verdeckungsberechnung

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.

Eine dem Raytracing ähnliche Technik wird zum Zeichnen einer Laute angewandt (Holzschnitt von Albrecht Dürer, 1525)

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

[Bearbeiten] 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, Punktwolken 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.

Seit kurzem werden auch komplexere Geometrien für den Schnittpunkttest wie etwa NURBS verwendet.^[4] Vorteilhaft dabei ist ein Maximum an Präzision, da die Fläche nicht wie sonst üblich in Dreiecke unterteilt wird. Der Nachteil ist eine erhöhte Renderzeit, da der Schnittpunkttest mit komplexen Freiformflächen sehr viel aufwändiger als mit einfachen Dreiecken ist. Eine hinreichende Annäherung an die Genauigkeit von NURBS ist zwar auch mit Dreiecken möglich, in diesem Fall muss aber eine sehr große Anzahl gewählt werden.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Performance

[Bearbeiten] 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.

Keine Technik ist generell optimal; die Effizienz ist szenenabhängig. Dennoch reduziert jedes Beschleunigungsverfahren die Laufzeit enorm und macht Raytracing erst zu einem praktikablen Algorithmus. Auf Kd-Bäumen basierende Unterteilungen sind für die meisten nicht-animierten Szenen die effizienteste oder nahezu effizienteste Technik, da sie sich mittels Heuristiken optimieren lassen.^[5]^[6] Mehrfach festgestellt wurde, 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.^[7]^[8] 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Schatten

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.

[Bearbeiten] 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.^[9]^[10]

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

[Bearbeiten] 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.^[11] 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.

[Bearbeiten] Path Tracing und Forward Raytracing

Globale Beleuchtung mittels Raytracing. Deutlich zu sehen sind Effekte wie die Kaustik unter der Glaskugel und das „Abfärben“ der Wände auf andere Flächen.

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.^[12] 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. Path Tracing hat eine rigorose mathematische und physikalische Basis.

Obwohl Path Tracing 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, sofern nicht sehr viele Strahlen ausgesendet werden. 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.

[Bearbeiten] 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.^[13]^[14] 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.^[15] 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. Ebenso wie Path Tracing und bidirektionales Path Tracing liefert MLT bei geeigneter Implementierung statistisch unverzerrte Bilder, das heißt, die einzige Abweichung vom idealen Bild besteht im Bildrauschen; andere Fehler sind ausgeschlossen.

Ein mit Photon Mapping gerendertes Bild; zu erkennen ist eine mit diesem Algorithmus effizient simulierte Kaustik.

Photon Mapping: wurde 1995 von Jensen veröffentlicht.^[16] 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. Allerdings ist Photon Mapping nicht statistisch unverzerrt, in der Präzision schwer intuitiv kontrollierbar und weniger robust als MLT. Dies macht sich vor allem bei Szenen mit schwierigen Lichtverhältnissen bemerkbar.

[Bearbeiten] Übersicht

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)

[Bearbeiten] 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.^[17]

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.^[18]

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

[Bearbeiten] Einsatzgebiete

[Bearbeiten] 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.^[19] 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.

[Bearbeiten] Weitere Anwendungsgebiete

Das Raytracing-Prinzip 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.

[Bearbeiten] Siehe auch

[Bearbeiten] Literatur

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

Weiterführende Artikel in Fachzeitschriften:

↑ 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
↑ O. Abert u. a.: “Direct and Fast Ray Tracing of NURBS Surfaces”, Proceedings of IEEE Symposium on Interactive Ray Tracing, Salt Lake City, 2006
↑ V. Havran u. a.: “Statistical Comparison of Ray-Shooting Efficiency Schemes”, Technical Report, Best Efficiency Scheme project, 2000
↑ I. Wald, V. Havran: “On building fast kd-trees for ray tracing, and on doing that in O(N log N)”, Proceedings of IEEE Symposium on Interactive Ray Tracing 2006
↑ 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
↑ 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
↑ 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
↑ E. Veach, L.J. Guibas: “Metropolis Light Transport”, SIGGRAPH 97 Proceedings
↑ H.W. Jensen, N.J. Christensen: “Photon Maps in Bidirectional Monte Carlo Ray Tracing of Complex Objects”, Computers & Graphics 19(2), 1995
↑ P.R. Atherton: “A scan-line hidden surface removal procedure for constructive solid geometry”, SIGGRAPH 83 Proceedings
↑ A. Wilkie u. a.: “Combined Rendering of Polarization and Fluorescence Effects”, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, 2001
↑ J. Schmittler u. a.: “A Hardware Architecture For Ray Tracing”, Graphics Hardware 2002 Proceedings

[Bearbeiten] Weblinks

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

Sonstiges:

Dieser Artikel wurde in die Liste exzellenter Artikel aufgenommen.

Von „http://de.wikipedia.org../../../r/a/y/Raytracing.html“

Kategorien: Exzellent | Algorithmus (Computergrafik)