Seminar Computergrafik WS 2003/04, von A.Diehl2 Inhalt Kapitel 1: Global Illumination Rendergleichung / Path Notation Monte Carlo Ansatz verschiedene

Seminar Computergrafik WS 2003/04, von A.Diehl 2

Inhalt• Kapitel 1: Global Illumination

Rendergleichung / Path Notation Monte Carlo Ansatz verschiedene Methoden

(Ray Tracing, Radiosity, Path Tracing, …)• Kapitel 2: Ray Tracing Turner Whitteds Einstieg

Funktionsweise Optimierungsmethoden


Kapitel 1: Global Illumination• bezeichnet allgemein die Simulation der

Interaktion von Licht mit der gesamten Umwelt

• zwei Wege diesen komplexen Vorgang zu erfassen:• Rendergleichung• Pfadnotation (Path Notation)


Rendergleichung• 1986 von Jim Kajiya aufgestellt• Gleichung für einen Punkt x einer Oberfläche

),( xxI ),( xxg ),( xx [ s

),,( xxx xdxxI ),( ]

Lichtintensität von x‘ auf x. Sichtbarkeitsfunktion: 0 wenn nicht sichtbar, sonst das inverse Quadrat der Distanz Lichtstrahlung von jedem x‘ auf x. Streufunktion: das Licht von x‘‘ welches über x‘ nach x gestreut wird. Integral über S: alle Punkte der Szene


Rendergleichung• viele Ansätze benutzen modifizierte Versionen

dieser Gleichung• Beispiel:

Radiosity-Gleichung (ausgehende Strahlung von x)

20coscos),(),(),(

),(),(

xxdAxxgxLx

xLxL

inininoutS

in

referefref

• bzw. die bekannte Version:

ij

jijiii BFrEB


Path Notation• einfache Methode die Interaktion zwischen

Flächen auszudrücken• Licht kann auf eine spekulare oder diffuse

Fläche treffen• und selbst von einer spekularen oder

diffusen Fläche kommen

spekulare Oberfläche

diffuse OberflächeL

S

D E

• diese Lichtpfade notiert man in der Form: L ( D|S )* E


Monte Carlo Ansatz• Annäherungsmethode, z.B. zum Lösen von

Integralen, wie z.B. Rendergleichung• Durchschnitt von n Zufallwerten:

einfache Methode• je mehr Zufallswerte man nimmt, desto

genauer wird das Ergebnis• doch weitere Werte haben immer weniger

Effekt daher nimmt man eine feste Zahl von Werten (auch wegen Rechenzeit)


Monte Carlo Ansatz• man unterteilt das Integral in n gleiche

Sektionen, und wendet Stratified Sampling an:

0

f(x)

n

ifn

dxxfI1

1

0

)(1)(

ξ1ξ2

ξn


Einführung: Ray Tracing• Idee: Strahlen durch eine Szene begleiten• dem Licht entgegen: vom Betrachter aus• bei einem Schnitt mit einem Objekt werden

Lichtstrahl, gebrochener und reflektierter Strahl erzeugt

• blickpunktabhängig

Kamera

Leinwand

Licht

Objekt


Ein Beispiel

Ray Tracing Global Illumination

Schattenindirektes LichtLichtbrechung


Einführung: Radiosity• Idee: jede Fläche strahlt Licht ab• d.h. es wird für jede Fläche das Licht von allen

anderen Flächen bestimmt• je nach Material strahlt diese Fläche wieder Licht ab• blickpunktunabhängig

Lichtquelle

Fläche A

Fläche B


Path TracingKajiya stellte fest, dass klassisches Ray Tracingverschwenderisch ist:• es erzeugt mehr und mehr Strahlen, je tiefer der

Algorithmus geht• diese Strahlen haben aber immer weniger Effekt:

Betrachter

Lichtstrahlgebrochenes Licht reflektiertes Licht


Path Tracing• daher die Idee den Pfad eines Strahles zu

verfolgen• hierbei wird zufällig bestimmt, ob reflektierter

oder gebrochener Strahl erzeugt wird• betrifft spekulare und diffuse Flächen• daher müssen pro Pixel auch mehrere Strahlen

initiiert werden:


Path Tracing

Man erhält also folgende Baumstruktur:

Betrachter

Lichtstrahl

reflektiertes LichtgebrochenesLicht

Betrachter

Lichtstrahl

erster Strahl: zweiter Strahl:

4 Strahlen pro Pixel225 Strahlen pro Pixel400 Strahlen pro Pixel

Mit dieser Methode erreicht man volle L(S|D)*E Interaktionen, mit allerdings hohen Kosten:


Distributed Ray Tracing• Erweiterung des klassischen Ray Tracing,

von Cook (1986)• klassisches Ray Tracing ist zu „perfekt“

(scharfe Kanten, perfekte Reflektionen, …)• hierzu wird bei jedem Schnittpunkt eine

gerichtete Menge von Strahlen erzeugt:

Objekt


Distributed Ray TracingDadurch kann man verschiedene Effekte erreichen:

weiche Schattenklassisches Ray Tracing:

verschwommene Reflektionen verschwommene TransparenzDistributed Ray Tracing:

(50 Strahlen)


Two-Pass Ray TracingVon Arvo (1986) vorgeschlagen, als bidirektionale Ray Tracing Methode um Lichtbrechungen darzustellen.• 1.Pass: Lichtstrahlen von den Lichtquellen durch

spekulare Interaktionen begleiten, bis zur ersten diffusen Fläche:

spekulare Oberflächen

Lichtquellediffuse Oberflächen

• Die Lichtenergie muss nun auf den diffusen Oberflächen in einer Art gespeichert werden. (vgl. Texture Map)

• 2.Pass: klassisches Ray Tracing, welches bei diffusen Flächen endet, und die gespeicherte Lichtenergie nutzt, als Annährung:

Light Map

Man erkennt, dass die diffuse Oberfläche der „Treffpunkt“ beider Pässe ist.Wir erhalten z.B. folgende Pfade:LSDELSSDSE

Ein wichtiger Vorteil dieser Methode ist, dass der erste Pass blickpunktunabhängig ist und die Light Maps somit im Vorfeld berechnet werden können.


Two-Pass Ray Tracing

Ein Beispiel, wie sich diese Methode äußert:• je nach Dichte ergeben sich Lichteffekte:

Licht Pass


Multi-Pass MethodenWir haben immer die Unterscheidung:• Blickpunktabhängigkeit (spekulare Interaktionen)• Blickpunktunabhängigkeit (diffuse Interaktionen)Die Two Pass Methode kann nur LS*DS*E Pfade darstellen.Eine Erweiterung nimmt nun die Radiosity Methodehinein:

S

S

D

Light Map

D

Light Map

hierdurch erweitern wir die Pfade zu: LS*D*S*E

neuer Pass: Radiosity


Fragen?


Kapitel 2: Ray Tracing

Auch „Whitted Ray Tracing“ genannt, nach Turner

Whitted, welcher 1980 das erste Bild ray tracte:


Eigenschaften• zentral im Ray Tracing sind

Schnittoperationen• der naive Ansatz testet also für jeden Strahl

den Schnitt mir jeder Fläche!• pro Schnitt werden zwei neue Strahlen

erzeugt• für Schattenberechnung werden pro Schnitt

noch n weitere Strahlen erzeugt (bei n Lichtquellen) sehr aufwendig!


AlgorithmusKamera

Bildebene (in Pixeln)

Objekt / Fläche Lichtstrahl (zu jeder Quelle)

reflektierter Strahlgebrochener Strahl

diffuse Oberfläche

……

…


Rekursion

Dieses Beispiel basiert auf Whitteds Ray Tracing:

Bei jedem Punkt x, der von einem Strahl getroffen

wird haben wir eine lokale und eine globaleKomponente: )()()( xIxIxI globallokal

)()()( gggrrglokal xIkxIkxI


Beispiele


Optimierung• naives Ray Tracing ist sehr

kostenaufwendig• vor allem Schnittberechnungen sind teuer• hohe Rekursionstiefe, wobei tiefere

Strahlen immer weniger Effekt haben• daher wurden einige

Optimierungsmethoden entwickelt …


Adaptive Depth Control

Die Tiefe des Algorithmus hängt stark von derSzene ab:• viele spekulare Objekte bedeuten viele

Reflektionen und hohe Tiefe• bei diffusen Objekten enden die Strahlen

früher

• die Intensität der Strahlen wird immer weiter durch die Koeffizienten vermindert, je tiefer der Algorithmus geht:

• allgemein: k1·k2·…·kn

1

2)(1 xIkrg

)(21 rrgrg xIkk


Adaptive Depth Control• diese Methode setzt einen Minimalwert für

die Intensität eines Strahles• wird dieser Wert unterschritten, bricht der

Algorithmus ab Selbst bei sehr reflektierenden Szenen undeiner maximalen Rekursionstiefe von 15kommt eine durchschnittliche Tiefe von1,71 heraus (nach Hall und Greenberg, 1983).


Hüllkugel: viel LeerraumHüllquader: schon effektiver

Hüllkörper

Weitere Methode die Schnittberechnungen zu optimieren:• Einfassen eines Objekts in einen Hüllkörper

(einfacher Schnitttest)• erst wenn dieser getroffen wird, wird das

Objekt geprüft

• auch Hierarchien von Hüllkörpern werden verwendet• Wahl der Hüllkörper ist ebenfalls wichtig:

Objekt


Hüllkörper

Gängig sind drei Arten von Hüllkörpern:• Hüllkugeln• achsenorientierte Hüllquader• objektorientierte Hüllquader


Räumliche Zusammenhänge• einfache Idee: die Szene wird in Regionen

unterteilt• nun schneidet man einen Strahl mit

Objekten in der Region, die er durchquert• nicht mit allen Objekten!• die Aufteilung geschieht vor dem

eigentlichen Ray Tracing und wird in einer weiteren Datenstruktur gespeichert

einmalige Berechnung


Räumliche Zusammenhänge

Einfaches Beispiel mit Trennebenen:• mehrere Ansätze für diese Idee• variieren im Aufbau der Datenstruktur• meist verbreitet sind:

– BSP – Bäume– Octrees


Ray Space Subdivision• Idee von Arvo und Kirk (1987):• anstatt Szene in Regionen aufzuteilen, teilt

man den Raum der Strahlen• 5D-Hyperwürfel, somit ist ein Strahl ein 5-

Tupel (x, y, z, u, v) mit Ursprung (x, y, z) und Richtung (u, v)

Strahl mit (x, y, z, u, v)

(u, v)


Ray Space Subdivision• diese „Strahlen“ werden mit den Objekten

geschnitten• dadurch erzeugt man eine Liste mit

möglichen Schnittobjekten• benötigt eine 5D-Erweiterung eines Octrees• komplexe Struktur• schwierige Schnittoperation, daher werden

Hüllkugeln empfohlen


Beam TracingBisher wurde eine wichtige Eigenschaft ausgelassen:• ein Strahl hat viele Nachbarn, die ähnliche

Schnittobjekte haben• man folgt also gleich mehreren Strahlen

durch die Szene (sog. Beams)• benötigt transformiertes Koordinatensystem,

beginnt mit Kamera-Koordinatensystem• rekursiver Algorithmus, der mit dem View

Frustum beginnt :


Beam Tracing

geschnittenes Polygon

beginnender Beam

virtueller Blickpunkt

reflektierter Beamgroße Nachteile dieser Technik sind:• nur noch polygonale Objekte (keine Kugeln),

was der große Vorteil des Ray Tracings ist• es können Löcher in den Beams enstehen• Lichtbrechung ist nicht mehr linear berechenbar


weiterer Ansatz

Ein anderer Ansatz ist, die Schnittobjekte des vorherigen Strahls zu benutzen, um die des nächsten vorherzusagen:

O1

O2

r-2r-1r

Um neue Schnitte festzustellen, werden Sicherheitszylinder konstruiert (Bsp. r-2):

O3

• durchstößt der neue Strahl diesen Sicherheitsbereich, werden herkömmliche Schnitttests durchgeführt

• ansonsten die Schnittobjekte des vorherigen Strahls behandelt


weiterer AnsatzDieser Ansatz von Speer (1986) hat dennoch denNachteil, dass er aufwendiger ist, als klassischesRay Tracing, da• zwar ⅔ der Strahlen sich ähnlich verhalten,

aber• die Berechnung der Sicherheitszylinder und• die Durchstoßberechnungen hinzukommen,• denn auch deren Größe sinkt mit der

Komplexität der Szene.


Quellen• „3D Computer Graphics“ von Alan Watt• „An Introduction to Global Illumination“ von

Tomas Akenine-Moeller, (PPT-Vortrag)• „Distributed Ray Tracing“ von Allan Martin

(http://www.cs.wpi.edu/~matt/courses/cs563/talks/dist_ray/dist.html)• „Naive Path Tracing“

(http://www.cs.unc.edu/~naiks/ugrad/cs6620/p4/)• „Global Illumination“ von CS324 Computer

Graphics• WinOSI (http://www.winosi.onlinehome.de/Comp1.htm)


Ende

Vielen Dank für Ihre Aufmerksamkeit!

Documents

Seminar Computergrafik WS 2003/04, von A.Diehl2 Inhalt Kapitel 1: Global Illumination Rendergleichung / Path Notation Monte Carlo Ansatz verschiedene