Punktbasierte Multiskalendarstellung

This thesis describes a new rendering paradigm for handling complex scenes, point-based multi-resolution rendering. The basic idea is to approximate the appearance of complex scenes using a small set of surface sample points. Using hierarchical data structures, the sampling process can be performed in time mostly independent of the scene complexity. This allows an efficient display of highly complex scenes. The thesis proposes different variants of sampling data structures that are useful in different application scenarios, including a variant for handling animated scenes (general keyframe animations). Two different rendering approaches are described: The first approach is a real-time forward mapping algorithm, being a point-based generalization of z-buffer rendering. In contrast to conventional z-buffer rendering, the point-based multi-resolution algorithm can render scenes consisting of trillions of primitives at real-time frame rates while maintaining a comparable rendering quality. The second approach is a backward mapping (i.e. raytracing) algorithm that aims at offline rendering. It is able to compute shadows, reflections, and refractions. It uses a hierarchy of prefiltered sample points to provide efficient antialiasing. Additionally, classic distributed raytracing effects such as soft shadows, depth-of-field, or blurry reflections can be approximated efficiently. In comparison with classic stochastic raytracing techniques, the new algorithm provides noise-free renderings at lower costs than stochastic oversampling for scenes of high variance. The image quality is roughly comparable to that of the classic approach; only a small bias is observed. The thesis provides a theoretical analysis of the sampling and rendering process. Upper bounds for the rendering time are established. For the randomized components of some of the algorithms, analytical lower bounds for the failure probability are derived, showing that arbitrarily high confidence probabilities can be achieved at a small increase of computational costs. An analysis of oversampling properties of different sampling and stratification strategies allows a quantitative comparison, needed to choose the best technique for a certain application. A prototype implementation is presented. The influence of different algorithmic parameters is evaluated empirically and compared to theoretical predictions. Practical applications of the proposed algorithms comprise real-time walkthroughs of highly complex static scenes as well as real-time visualizations of large crowd animations such as a herd of animals or a football stadium with ten thousands of animated football fans. In addition, dynamic modifications of the data structure as needed for interactive editing is examined. Finally, extensions to volume rendering, out-of-core rendering, sound rendering, and simulation of caustics from area light sources are discussed briefly. Overall, the presented techniques extend the possibilities for rendering of highly complex scenes to areas that could not be treated before with comparable efficiency.Die vorliegende Arbeit beschreibt ein neues Paradigma für die effiziente Darstellung komplexer dreidimensionaler Szenen: die Verwendung von punktbasierten Multiskalenmodellen. Die Grundidee besteht darin, das Erscheinungsbild einer komplexen Szene aus einer (im Vergleich zur potentiellen Szenenkomplexität) kleinen Stichprobe von Oberflächenpunkten zu rekonstruieren. Hierarchische Datenstrukturen erlauben es, solche Stichproben effizient zu bestimmen, d.h. mit einer Laufzeit, die weitgehend unabhängig von der Komplexität der Szene ist. Dies ermöglicht es, Szenen mit sehr großer Komplexität effizient zu behandeln. Es werden verschiedene Varianten von Datenstrukturen beschrieben, die eine solche effiziente Stichprobennahme erlauben, darunter auch eine Variante, die erlaubt, animierte Szenen (Keyframeanimationen) zu behandeln. Die Datenstrukturen dienen als Basis für verschiedene Darstellungsalgorithmen. Dabei werden zwei wesentliche Strategien behandelt: Die erste Klasse („forward mapping“) bildet die Szene unter einer einfachen perspektivischen Projektion ab. Eine Tiefenpuffertechnik rekonstruiert dann das Bild aus den Stichprobenpunkten. Der Rechenaufwand wächst dabei nur schwach mit der Szenenkomplexität, so daß Szenen mit enormen Mengen von Primitiva (Billiarden Dreiecke und mehr) in Echtzeit dargestellt werden können. Die erreichte Qualität entspricht dabei in etwa der von gewöhnlichen Tiefenpuffer-Algorithmen. Die zweite Klasse von Darstellungsalgorithmen („backward mapping“) verallgemeinert die Darstellungstechnik so, daß ein Raytracing auf punktbasierten Multiskalenmodellen durchgeführt werden kann. Dies erlaubt die Berechnung von Schatten, Spiegelungen und Brechung. Der Algorithmus benutzt eine Multiskalenhierarchie von vorgefilterten Stichprobenpunkten (also Stichproben eines jeweils entsprechend der Stichprobendichte bandbeschränkten Signals). Damit können Bilder ohne Aliasingprobleme erzeugt werden. Außerdem sind auch Approximationen von Effekten des klassischen „distributed raytracing“ wie etwa weiche Schatten, verschwommene Reflektionen oder Tiefenunschärfe mit geringen Kosten (ein Primärstrahl pro Pixel) möglich. Im Vergleich zum klassischen „distributed raytracing“ erzeugt der Algorithmus die Bilder effizienter, insbesondere wenn die Bildsignale eine hohe Farbvarianz aufweisen und Rauschartefakte vermieden werden müssen. Die Bildqualität ist grob vergleichbar mit der klassischen (korrekten) Lösung, die approximative Multiskalenstrategie führt nur zu kleineren systematischen Abweichungen. Die vorliegende Arbeit führt eine theoretische Analyse der Stichprobenbestimmungs- und Darstellungsalgorithmen durch. Es werden obere Schranken für die Laufzeit des Darstellungsprozesses bewiesen, so daß eine Effizienz des Verfahrens unter relativ allgemeinen Bedingungen sichergestellt ist. Einzelne Schritte benutzen randomisierte Algorithmen. Hier wird gezeigt, daß die Wahrscheinlichkeit dafür, daß der Algorithmus zufällig nicht das gewünschte Ergebnis bestimmt, mit geringem Aufwand sehr klein (beliebig klein bei schwachem Aufwandswachstum) gehalten werden kann. Die verschiedenen Verfahren zur Stichprobenentnahme werden auch hinsichtlich des „oversampling“ verglichen, d.h. dem Verhältnis der Zahl der Stichprobenpunkte zur tatsächlich notwendigen Anzahl bei einer optimalen Auswahl. Die besten vorgestellten Verfahren sind dabei nur um einen kleinen Faktor vom Optimum entfernt. Weiterhin werden experimentelle Ergebnisse vorgestellt, die auf einer prototypischen Implementation der vorgeschlagenen Algorithmen beruhen. Damit wird der Einfluß verschiedener Parameter der Algorithmen auf Laufzeit und Bildqualität in der Praxis untersucht und mit den theoretischen Voraussagen verglichen. Außerdem werden Beispielanwendungen beschrieben, in denen Szenen mit sehr großer Komplexität in Echtzeit dargestellt werden können. Dabei wird auch gezeigt, daß effiziente dynamische Modifikationen der Datenstrukturen möglich sind, die für interaktives Editieren komplexer Szenen benötigt werden. Die Darstellungsalgorithmen werden zudem auf animierte Szenen angewandt, hier am Beispiel von Massenanimationen (z.B. Darstellungen großer Menschenmassen oder Tierherden mit dynamischem Verhalten). Abschließend wird noch kurz auf Verallgemeinerungen eingegangen. Diese betreffen die Echtzeitdarstellung sehr großer Volumendatensätze, eine effiziente Darstellung von Datensätzen, die aufgrund ihrer Größe auf Hintergrundspeichermedien (Festplatte) gehalten werden müssen, sowie eine Anwendung auf die Berechnung von Geräuschkulissen, die ein interaktiver Beobachter in Szenen mit einer großen Anzahl von Schallquellen wahrnimmt. Ein weiterer kurzer Exkurs diskutiert eine Echtzeitberechnung von Kaustiken von ausgedehnten Lichtquellen, die ebenfalls auf punktbasierten Diskretisierungen von Oberflächen beruht. Insgesamt erweitern die neu vorgeschlagenen punktbasierten Multiskalenansätze deutlich die bisherigen Möglichkeiten, Abbildungen komplexer dreidimensionaler Szenen effizient zu berechnen