Photon tracing for complex environments

Abstract

When used on complex scenes, many high quality image synthesis methods encounter problems. These can either be that their calculation times become unacceptable, or that they would require inordinate amounts of memory. Some - otherwise perfectly useful - methods even suffer from both problems at once. In this context, scene complexity is directly related to the number of geometric primitives used to model the scene. The resource requirements of the image synthesis methods we consider in this work are linked to the number of involved primitives through an at least linear relationship, which leads to the obvious conclusion that a reduction in the number of primitives needed to model a scene is highly desirable. An efficient way of meeting this goal is to use scene description methods with higher descriptive power than the current industry standard of polygonal models. Good choices in this area are the approach of constructive solid geometry and rule-based techniques such as L-systems. However, these memory-saving modeling methods have the disadvantage that so far it has not been possible to use them in conjunction with a particular, highly efficient class of global illumination methods, namely photon tracing algorithms. These techniques calculate the distribution of light in a scene through a stochastic simulation of light propagation. The result of these calculations is stored, and used as a basis for actually displaying the scene in a second step. This two-step approach is highly useful and time-saving if sequences of images - e.g. for animations - are to be rendered, since the first photon tracing step is viewpoint-independent and only has to be performed once for each scene. However, the useful property of retaining illumination information for later use can turn into a serious problem when complex scenes are considered; in that case the memory requirements can grow to such dimensions that use of photon tracing methods becomes totally unfeasible. In this thesis we present three approaches which aim at making the use of photon tracers possible even for complex environments. The first technique aims at reducing the overall scene complexity by making the direct use of CSG models for lightmap-based photon tracers possible. The second addresses the problem of large memory requirements for the storage of illumination information on complex objects by introducing a special type of approximate lightmap which is capable of averaging the indirect illumination on entire objects. While this introduces artifacts, the drastic reduction of needed memory can make the - otherwise impossible - inclusion of complex objects in a photon tracing simulation feasible for the first time. The third extends the second proposal by making it possible to use these approximate data structures even on implicitly defined objects, such as those specified by L-systems. In the appendix we cover several aspects of physically correct predictive rendering. While they are not directly related to the improvements presented in this thesis, they are of interest in this context because the capability of performing global illumination calculations where these effects are taken into consideration is one of the advantages of photon tracing methods. Also, the results which are presented in the appendix were obtained during the work on the main topic of the thesis.

Qualitativ hochwertige Bildsyntheseverfahren haben im Allgemeinen das Problem, dass sie bei Anwendung auf komplexe Szenen entweder zu lange Rechenzeiten benoetigen, oder dass ihr Speicherplatzbedarf zu gross wird; bei manchen ansonsten durchaus brauchbaren Methoden treten auch beide Probleme zugleich auf. Die Komplexitaet einer Szene definiert sich in diesem Zusammenhang normalerweise ueber die Anzahl der zu ihrer Modellierung benoetigten Grundobjekte. Die Ressourcenanforderungen der im Rahmen dieser Arbeit betrachteten photorealistischen Bildsyntheseverfahren steigen mindestens linear mit der Anzahl der beteiligten Objekte, woraus sich ein direkter Zusammenhang zwischen der Szenenkomplexitaet und dem Laufzeitverhalten der Bilderzeugungsprogramme ergibt. Daraus leitet sich als erster Ansatz die Forderung ab, moeglichst nur solche Modellierungsmethoden zu verwenden, die mit verhaeltnismaessig wenigen Grundobjekten bereits imstande sind, Szenen ausreichend zu beschreiben. Konkret geht es darum, die in der Computergraphik-Industrie derzeit uebliche Darstellungsweise durch grosse Mengen an Polygonen zu vermeiden, und effizientere Verfahren wie Constructive Solid Geometry (kurz CSG) oder regelbasierte Modellierung durch Automaten (wie etwa L-Systeme) zu verwenden. Diese speichersparenden Methoden zur Szenenbeschreibung haben allerdings den Nachteil, dass sie aus verschiedenen Gruenden bislang nicht zusammen mit einer bestimmten Klasse von hochwertigen Bildsyntheseverfahren, den sogenannten photon tracing methods, verwendet werden konnten. Diese Verfahren berechnen eine Loesung der Lichtverteilung in einer Szene durch Nachvollziehung der Lichtausbreitung mittels stochastischer Methoden. Das Ergebnis dieser Simulation wird dann in einem zweiten Arbeitsschritt von einem beliebigen Blickpunkt aus dargestellt. Besonders wenn die Erzeugung ganzer Bildsequenzen - beispielsweise fuer Animationen - erforderlich ist, erspart man sich durch diese Teilung des Ablaufes in 2 Phasen, von denen die erste pro Szene nur einmal durchgefuehrt werden muss, einen wesentlichen Aufwand. Allerdings kann der an sich nuetzliche Umstand, dass die Verteilung der Lichtenergie in der Szene in irgendeiner Form zwischen den beiden Arbeitsschritten zwischengespeichert werden muss, auch ein Problem darstellen. Das ist dann der Fall, wenn derartige Verfahren auf komplexe Szenen angewandt werden. Bei diesen wird der Speicherplatzbedarf extrem gross, und kann unter Umstaenden die Verwendung solcher Methoden ueberhaupt unmoeglich machen. Im Rahmen dieser Arbeit werden nun drei Ansaetze aufgezeigt, solche photon tracers doch auch fuer komplexere Umgebungen nutzen zu koennen. Der erste praesentiert eine Moeglichkeit, durch die direkte Verwendung von CSG-Modellen die Szenenkomplexitaet an sich im Vorfeld der Berechnungen zu reduzieren. Der zweite setzt am Problem des Speicheraufwandes fuer die Lichtverteilung an, und stellt ein Verfahren vor, das fuer einzelne komplexe Objekte lediglich eine lokale Naeherung fuer die Beleuchtung speichert. Dadurch werden zwar Abweichungen von der Idealloesung erzeugt, aber der dadurch drastisch reduzierte Platzbedarf kann in manchen Faellen die Einbindung komplexer Objekte erst ermoeglichen. Der dritte erweitert das im zweiten Punkt vorgeschlagene Verfahren insofern, als er die Anwendung dieser Naeherungsverfahren auch auf durch Automaten lediglich implizit gegebene Objekte ermoeglicht, was eine weitere entscheidende Reduktion des zur Durchfuehrung von Beleuchtungsberechnungen erforderlichen Speicherplatzes moeglich macht. Im Anhang der Arbeit werden einige Aspekte der physikalisch korrekten photorealistischen Bildsynthese abgehandelt. Sie stehen zwar nicht in direktem Zusammenhang mit den im Hauptteil der Arbeit praesentierten Verbesserungen, sind aber insofern fuer den Themenbereich relevant, als es einer der Vorteile von photon tracing-Algorithmen ist, derartige Effekte in die Bildberechnungen einbeziehen zu koennen. Die entsprechenden Untersuchungen wurden ebenfalls im Zuge der Arbeit an dieser Dissertation vorgenommen.