Point based multi-resolution rendering [Elektronische Ressource] / vorgelegt von Michael Wand

Miwand

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2004
• Nombre de lectures: 10
• Langue: Deutsch
• Poids de l'ouvrage: 40 Mo

Extrait

Point-Based
Multi-Resolution
Rendering

Dissertation
der Fakultät für Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universität Tübingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)


vorgelegt von
Dipl. Inform. Michael Wand
aus Paderborn



Tübingen
2004

















Tag der mündlichen Qualifikation: 30.06.2004
Dekan: Prof. Dr. Ulrich Güntzer
1. Berichterstatter: Prof. Dr.-Ing. Dr.-Ing. E.h. Wolfgang Straßer
2. Berichterstatter: Prof. Dr. Markus Gross
(Eidgenössische Technische Hochschule Zürich)
3. Berichterstatter: Prof. Dr. Andreas Schilling
Zusammenfassung
Die vorliegende Arbeit beschreibt ein neues Paradigma für die effiziente Darstellung komplexer
dreidimensionaler Szenen: die Verwendung von punktbasierten Multiskalenmodellen. Die Grund-
idee besteht darin, das Erscheinungsbild einer komplexen Szene aus einer (im Vergleich zur po-
tentiellen 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 effi-
ziente 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 Rechenauf-
wand 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 erreich-
te Qualität entspricht dabei in etwa der von gewöhnlichen Tiefenpuffer-Algorithmen. Die zweite
Klasse von Darstellungsalgorithmen („backward mapping“) verallgemeinert die Darstellungs-
technik 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 ei-
nes 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 appro-
ximative 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 Darstellungs-
prozesses 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 be-
stimmt, mit geringem Aufwand sehr klein (beliebig klein bei schwachem Aufwandswachstum)
gehalten werden kann. Die verschiedenen Verfahren zur Stichprobenentnahme werden auch hin-
sichtlich des „oversampling“ verglichen, d.h. dem Verhältnis der Zahl der Stichprobenpunkte zur
iii 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 Im-
plementation 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 wer-
den zudem auf animierte Szenen angewandt, hier am Beispiel von Massenanimationen (z.B. Dar-
stellungen 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 Beobach-
ter 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 be-
rechnen.
iv Abstract
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 differ-
ent 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 ren-
dering 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 ray-
tracing effects such as soft shadows, depth-of-field, or blurry reflections can be approximated effi-
ciently. 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 arbitrar-
ily 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 simu-
lation 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.
v Table of Cont