Testberichte

• MAGIX Music Maker 2007
• Wings 3D - a subdivision modeler
• Texture-Painting in Bodypaint 3D

Erfahrungsberichte

• Games Convention 2006, Leipzig

Wissensbasis

• Photon Mapping

Viele werden diesen Begriff bestimmt noch nie gehört haben. Daher gleich vorweg: Es handelt sich um einen sehr geschickten Ansatz, alle denkbaren visuellen Effekte beim Rendering einer 3d-Welt darzustellen. Was das genau bedeutet und was dabei geschieht, möchte ich euch in folgendem Artikel näher bringen. Auf ein wenig Mathematik kann ich dabei leider nicht verzichten, dennoch werde ich versuchen alles möglichst einfach zu erklären.

Entwickelt wurde Photon Mapping schon 1993/94 von Henrik Wann Jensen, von dem auch einige der folgenden Bilder in diesem Artikel stammen. Wer sich noch mehr dafür interessiert, kann ja gerne mal auf seiner Seite vorbeischauen: http://graphics.stanford.edu/~henrik/



Man unterscheidet zwischen zwei großen Gruppen, zum einen das Echtzeitrendering (für Computerspiele usw.) und zum anderen die fotorealistische Computergrafik. Das Ziel der fotorealistischen Computergrafik ist in der Regel, ein Bild möglichst realistisch darzustellen.  Natürlich trifft dieses Ziel nicht auf jedes Rendering zu, denn manchmal soll das Ergebnis gar nicht realistisch aussehen oder es spielen andere Faktoren eine wichtigere Rolle, beispielsweise die Renderzeit wenn es um Computerspiele geht, bei denen ca. 20 Bilder/Sekunde dargestellt werden müssen.
Für uns geht es beim Photon Mapping nun jedoch vorrangig darum, 3d-Welten möglichst realistisch darstellen zu können und dabei auch bei sehr komplexen Szenen oder Objekten eine möglichst "kurze" Renderzeit zu erreichen.
Noch viel abstrakter ausgedrückt: Wir wollen die Szene, die wir in unserem 3d-Programm (Cinema 4d, Maya, 3dsMax usw.) erstellt haben auf ein 2d-Bild abbilden.
Um dies zu erreichen gibt es mehrere Möglichkeiten, wobei sich diese im Realismus, im Rechenaufwand und der überhaupt darstellbaren Effekte unterscheiden. Beispiele für diese sogenannten globalen Beleuchtungsmodelle sind Raytracing und Radiosity. Unter globalen Beleuchtungsmodellen versteht man, dass Licht nur mit dem Wissen über die komplette Szene berechnet werden kann, bedeutet man betrachtet nicht nur die Stelle, auf der Licht auftrifft, sondern auch wo es herkommt, ob an dieser Stelle eventuell Schatten ist usw.
Lokale Beleuchtungsmodelle hingegen simulieren lediglich die Ausbreitung von Licht auf einem Objekt. Das beste Beispiel dafür ist das Glanzlicht.


Versuchen wir zunächst einmal zu verstehen, was die Idee hinter Photon Mapping ist und wie wir uns diese vorstellen können.

Der Algorithmus selbst ist in zwei Schritte unterteilt. Im ersten Schritt werden von jeder Lichtquelle in einem Raum Photonen in die Szene geschickt. Man spricht dabei vom Particle Tracing.
Der Einfachheit halber stellen wir uns Photonen als Punkte vor, die in diesem Raum verteilt werden. Landen auf einer Stelle bzw. in einem Bereich des Raumes viele Photonen, so wird dieser Bereich im Endeffekt heller dargestellt, als ein Bereich, auf dem weniger Photonen erfasst wurden. Die Photonen werden dabei in einer Photon Map abgespeichert, damit wir nach dem ersten Schritt wissen, wo die Photonen gelandet sind.
Im zweiten Schritt wird diese Photon Map dann ausgewertet. Wie das geschieht schauen wir uns später noch genauer an.



Im ersten Schritt wollen wir nun also die Photonen im Raum verteilen. Dafür benötigen wir eine Strategie, wie wir die Photonen nun so verteilen, dass diese unsere Szene möglichst realistisch ausleuchten.
Fangen wir bei der Lichtquelle selbst an. Die Basis unserer Strategie ist die Verteilung des Lichtstroms über die verschiedenen Raumwinkel. Man spricht dabei von der Lichtstärkeverteilung. Einem Objekt direkt unter der Lampe sollen mehr Photonen zugewiesen werden als einem Objekt, welches sich seitlich oder sogar hinter unserer Lichtquelle befindet.
Schauen wir uns dazu einfach die Definition der Lichtstärke an:



Im Zähler steht der Lichtstrom, im Nenner der Raumwinkel. Die Lichtstärke ist demnach bei einem hohen Lichtstrom und einem niedrigen Raumwinkel größer als bei niedrigem Lichtstrom und einem großen Raumwinkel. Allgemein ausgedrückt: Direkt vor der Lichtquelle ist es heller als etwas daneben.

Wir wissen nun, wie die Photonen von unserer Lichtquelle abgesendet werden. Im geringen Winkel zu der Lichtquelle werden viele Photonen ausgesandt, im großen Winkel wenigere.
Trifft ein Photon nun auf die Oberfläche unseres Objekt’s müssen wir entscheiden was damit passiert. Dies ist abhängig vom Material. Schauen wir uns dazu einfach folgende Grafik an:



Wir gehen davon aus, dass die Lichtquelle 4 Photonen versendet. Photon 1 landet auf einem diffusen Material (ein Blatt Papier beispielsweise). Somit wird das Photon abgespeichert (blauer Punkt) und weiterverfolgt. Photon 2 wird reflektiert (ein Spiegel beispielsweise), heißt es wird nicht abgespeichert, aber weiterverfolgt. Beim Auftreffen auf die Decke entscheiden wir wieder neu je nach Materialeigenschaften, was mit dem Photon passieren soll. Photon 3 ist ebenfalls wieder diffus. Das 4te Photon wird absorbiert, also abgespeichert und nicht weiterverfolgt.
Wichtig ist, dass man im Vorhinein eine Rekursionstiefe definiert. Das bedeutet, dass ein Photon beispielsweise maximal 2 Mal weiter verfolgt werden soll, damit es nicht theoretisch unendlich lange im Raum hin und her springen kann.
Wir sprechen bei diesem Algorithmus vom Photon Scattering. Dass es sich dabei um wesentlich mehr Photonen handelt dürfte klar sein. Eine durchschnittliche Größenordnung könnte beispielsweise bei 1 Millionen Photonen liegen, die in der Szene "verteilt" werden.

Haben wir ein Material, das zu 50% diffus , zu 25% spiegelnd und zu 25% absorbierend ist, so entscheiden wir beim Auftreffen eines Photons nach dem Zufallsprinzip (Russisches Roulette) was damit passiert.


Während des Photon Scattering müssen die Photonen nun irgendwie in unserer Szene abgespeichert werden. Dass eine sehr effiziente Speicherung dabei sehr wichtig ist, dürfte schon alleine durch die enorme Anzahl der Photonen klar sein. Zudem sind Nachbarschaftsbeziehungen für uns wichtig, was bedeutet, dass wir später das Wissen über umliegende Photonen benötigen.
Daher verwenden wir als Datenstruktur den kd-Tree, auf dessen Aufbau ich an dieser Stelle jedoch nicht näher eingehen werde. Für uns ist lediglich relevant, dass wir in dieser Struktur mit wenig Aufwand ein bestimmtes Photon finden können (O(log n)) und ebenso auch dessen k Nachbarn (O(k+log n)). k steht in diesem Fall für eine noch unbestimmte beliebige Anzahl an Nachbarn. Wofür wir diese benötigen schauen wir uns später genauer an.
Für jedes Photon speichern wir nun die Position, die Einfallsrichtung, den Lichtstrom und einen zusätzlichen Wert, der für den kd-Tree benötigt wird. Somit benötigen wir insgesamt 28 Byte pro Photon.


Bisher war immer die Rede von einer Photon Map. Sinnvoll ist es aber, gleich zwei solcher Photon Maps zu verwenden. Wir erinnern uns: In der Photon Map werden die in der Szene gelandeten Photonen abgespeichert.
Zerteilen wir den Begriff der Photon Map nun in eine global Map und in eine Caustic Map.
In der global Map werden wie bisher die Photonen zur Beleuchtung unserer Szene gespeichert. In der Caustic Map werden nun zusätzlich ein Vielfaches mehr an Photonen (ca. 10 Mal mehr als in der global Map, szenenabhängig) in der Szene verwendet um sogenannte Kaustiken (engl. Caustic; ein durch Lichtbrechung entstandenes geometrisches Helligkeitsmuster) darstellen zu können.


Quelle: www.wikipedia.de

Links im Bild sehen wir die Caustic Map, in der die Photonen als gelbe Punkte dargestellt werden. Das andere Bild zeigt das fertig gerenderte Resultat, bei der wir die Kaustiken ganz deutlich erkennen können.


Bisher haben wir zwei Photon Maps erstellt, eine für die globale Beleuchtung und eine für die Berechnung der Kaustiken. Dazu haben wir unsere Photonen beim Photon Scattering in unserer Szene verteilt und in einem kd-Tree abgespeichert.

Kommen wir also zum 2. Schritt des Photon Mappings.



Nachdem wir unsere Photonen in der Szene verteilt haben, wollen wir nun auch die Helligkeit für bestimmte Bereiche abschätzen. Dazu suchen wir zu einem beliebigen Punkt ein Photon und dessen n Nachbarn. Nun erhalten wir beispielsweise 20 Photonen, deren Lichtstrom wir aufsummieren und dann durch die Fläche teilen. Das machen wir um das Rauschen in einer Szene zu vermindern. Stellen wir uns zum Beispiel vor, dass es genau unter der Lichtquelle einen Punkt gibt, auf dem zufällig kein einziges Photon gelandet ist. Natürlich ist dieser Fall recht unwahrscheinlich, schauen wir nun aber in unserer global Map nach und finden dort kein Photon, so müsste dieser Bereich eigentlich schwarz bzw. dunkel dargestellt werden. Betrachten wir aber alle Nachbarn des Photons, so erhalten wir einen Mittelwert für die betrachtete Fläche.
Genau das ist auch der Grund, warum wir die Photon Map nicht direkt zur Beleuchtung unserer Szene verwenden. Die Bilder würden enorm verrauscht aussehen, da unsere Photonen nach dem Zufallsprinzip in der Szene verteilt wurden.
Doch wozu dann der ganze Aufwand? Ganz umsonst ist er nicht, denn zum einen verwenden wir die Caustic Map um Kaustiken darstellen zu können und zum anderen verwenden wir die global Map zur Approximation des indirekten Lichtes.

Okay, was genau bedeutet das:
Unseren direkten Lichteinfall von der Lichtquelle berechnen wir mit einem Path Tracer oder Final Gathering usw. Ich werde im Folgenden Path Tracing als Renderingmethode annehmen, natürlich wäre das Rendering aber auch mit einem vergleichbaren Algorithmus durchführbar.
Mit Path Tracing können wir unser Bild ebenfalls sehr realistisch rendern, was in der Praxis aber meist viel zu langsam ist. Zudem sind Effekte wie Kaustiken nicht darstellbar. Wie genau Path Tacing funktioniert würde an dieser Stelle jedoch den Rahmen sprengen, daher gehe ich nicht weiter darauf ein.
Wir kombinieren nun also einen leicht modifizierten Path Tracer mit Photon Mapping, wobei wir zweites für die Berechnung der Kaustiken und für das indirekte Licht benötigen.


Um das Bild letztendlich zu rendern gibt es viele Möglichkeiten. Schon angesprochen wurde ein Path Tracer, der nun mit Photon Mapping kombiniert wird. Dafür unterscheiden wir zwischen einer exakten und einer ungefähren Berechnung (Approximation). Die ungefähre Berechnung wird immer dann verwendet, wenn der aktuelle Strahl nicht mehr viel zu unserem Bild bzw. zum Gesamtergebnis beiträgt. Somit sparen wir uns Rechenzeit, da wir Dinge, die wir eh fast gar nicht wahrnehmen, lediglich abschätzen bzw. nähern.
Das direkte sowie das indirekte Licht der Szene berechnen wir zunächst exakt mit einem Path Tracer. Trägt ein Strahl nicht mehr viel zum Gesamtergebnis bei, so lesen wir den Wert einfach aus unserer mit Photon Mapping erzeugten global Map ab, da diese eine Schätzung der Helligkeit für einen bestimmten Bereich liefert.
Die Kaustiken können wir mit einem Path Tracer nicht berechnen, daher werden diese immer aus der Caustic Map berechnet.
Spiegelungen können mit Photon Mapping nicht dargestellt werden, daher geschieht diese Berechnung über den Path Tracer.


Was genau passiert nun also zusammenfassend beim Photon Mapping:
Es werden Photonen in unserer Szene verteilt. Diese werden in zwei verschiedenen Photon Maps gespeichert. Die global Map benötigen wir hauptsächlich zur Abschätzung von direktem und indirektem Licht unserer Szene, die exakte Berechnung führen wir jedoch mit einem Path Tracer durch. Die Kaustiken werden durch unsere Caustic Map berechnet, da dieser Effekt von einem normalen Path Tracer nicht berechnet werden kann.
Durch diese Kombination von Path Tracing und Photon Mapping erreichen wir kürzere Renderzeiten und können zusätzlich Effekte wie Kaustiken sehr realistisch darstellen. Ein weiterer Vorteil ist die Geometrieunabhängigkeit, so dass die Anzahl der Polygone einer Szene keine Rolle spielen. Der zusätzliche Aufwand, Photon Mapping zu verwenden lohnt sich also. Zudem ist Photon Mapping relativ leicht zu implementieren. Daher wird es von den meisten großen Renderern unterstützt, zu denen beispielsweise Mental Ray oder der Maxwell Renderer gehören.


Fragen, Anmerkungen, Lob und Kritik zu diesem Artikel können gerne im Forum gepostet werden. Ich freue mich über jede Art der Resonanz.

Liebe Grüße,
Manuel