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

De
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.
Publié le : jeudi 1 janvier 2004
Lecture(s) : 10
Tags :
Source : W210.UB.UNI-TUEBINGEN.DE/DBT/VOLLTEXTE/2004/1414/PDF/DISSMICHAELWAND.PDF
Nombre de pages : 247
Voir plus Voir moins



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 Contents

Preface xi
Introduction xiii
1 Background 1
1.1 Rendering.....................................................................................................................................1
1.1.1 Geometric Scene Description............................................................................................1
1.1.2 Shading ..............................................................................................................................4
1.1.3 Projection ...........................................................................................................................4
1.1.4 The Rendering Task..........................................................................................................5
1.2 Output-Sensitive Rendering .......................................................................................................5
1.3 Sampling and Aliasing......7
1.3.1 Uniform Sampling.............................................................................................................7
1.3.2 Non-Uniform Sampling9
1.3.3 Sampling Statistics .........................................................................................................16
2 Rendering Techniques 19
2.1 Classification..............................................................................................................................19
2.2 Forward Mapping ......................................................................................................................20
2.2.1 The z-Buffer Algorithm...................................................................................................20
2.2.2 Limitations.......................................................................................................................20
2.2.3 Simplification..21
2.2.4 Image-Based Rendering..................................................................................................27
2.2.5 Occlusion Culling ............................................................................................................30
2.3 Backward Mapping....................................................................................................................32
2.3.1 The Raytracing Algorithm ..............................................................................................32
2.3.2 Data Structures for Efficient Ray Queries ....................................................................33
2.3.3 Antialiasing .....................................................................................................................35
3 Point-Based Multi-Resolution Rendering 37
3.1 Limitations of Previous Techniques .........................................................................................37
3.2 Related Work in Point-Based Rendering .................................................................................39
3.2.1 The History of Point-Based Computer Graphics...........................................................40
3.2.2 Recent Developments......................................................................................................44
3.3 Components of the Point-Based Rendering Framework.........................................................48
3.3.1 Overview ..........................................................................................................................48
vii 4 Data Structures 51
4.1 Dynamic Sampling.................................................................................................................... 52
4.1.1 Overview.......................................................................................................................... 52
4.1.2 Area-Based Sampling..................................................................................................... 52
4.1.3 Spatial Adaptivity........................................................................................................... 53
4.1.4 Orientational Adaptivity................................................................................................ 58
4.1.5 Identifying “Large Triangles” ........................................................................................ 59
4.1.6 Instantiation ...................................................................................................................60
4.1.7 Dynamic Updates 61
4.2 Static Sampling......................................................................................................................... 63
4.2.1 Overview.......................................................................................................................... 63
4.2.2 Precomputed Sample Sets.............................................................................................. 64
4.2.3 Sampling and Stratification........................................................................................... 66
4.2.4 Point Representations and Point Properties ................................................................ 78
4.2.5 Instantiation.81
4.2.6 Caching............................................................................................................................ 82
4.3 Animated Geometry.................................................................................................................. 83
4.3.1 Input Model.....................................................................................................................83
4.3.2 Hierarchy Creation......................................................................................................... 83
4.3.3 Sampling ......................................................................................................................... 85
4.3.4 Instantiation ...................................................................................................................89
4.4 Comparing the Data Structures .............................................................................................. 89
5 Forward Mapping 93
5.1 Perspective Projection..... 93
5.2 Hierarchy Traversal ................................................................................................................. 96
5.2.1 The Rendering Algorithm for Dynamic Sampling........................................................ 96
5.2.2 The Rendering Algoor Static Sampling............................................................. 98
5.2.3 Analysis ........................................................................................................................... 98
5.3 Image Reconstruction ............................................................................................................. 110
5.3.1 Recon of Occlusion......................................................................................... 110
5.3.2 Scattered Data Interpolation....................................................................................... 113
5.4 Overall Efficiency.................................................................................................................... 116
6 Backward Mapping 117
6.1 Motivation ............................................................................................................................... 117
6.2 The Raytracing Algorithm...................................................................................................... 119
6.2.1 Overview........................................................................................................................ 119
6.2.2 Data Structure .............................................................................................................. 121
6.2.3 Ray Representation 122
6.2.4 Ray-Surface Interaction ............................................................................................... 123
viii
6.2.5 Intersection Calculations..............................................................................................125
6.2.6 Compositing ...................................................................................................................128
6.2.7 Subpixel-Masks .............................................................................................................129
6.2.8 Adaptive Resolution ......................................................................................................131
6.2.9 Implementation Notes ..................................................................................................132
7 Implementation and Results 133
7.1 Implementation .......................................................................................................................133
7.1.1 Software Architecture ...................................................................................................133
7.1.2 Implementation of Algorithms and Data Structures..................................................139
7.1.3 Technical Aspects ..........................................................................................................140
7.2 Preprocessing and Rendering Parameters.............................................................................143
7.2.1 Dynamic Sampling ........................................................................................................143
7.2.2 Static Sampling .............................................................................................................150
7.3 Comparing Forward Mapping Techniques ............................................................................158
7.3.1 Performance...................................................................................................................158
7.3.2 Image Reconstruction ...................................................................................................161
7.3.3 Comparison with Conventional Rendering Techniques .............................................169
7.4 Animated Scenes .....................................................................................................................170
7.5 Evaluation of Backward-Mapping Techniques......................................................................174
7.5.1 Performance and Image Quality ..................................................................................175
7.5.2 Special Effects181
8 Extensions 185
8.1 Volume Rendering ...................................................................................................................185
8.1.1 Overview ........................................................................................................................185
8.1.2 Analysis and Consequences..........................................................................................187
8.1.3 Implementation and Results ........................................................................................190
8.2 Out-of-Core Storage.................................................................................................................190
8.2.1 Overview.190
8.2.2 Modifications to the Static Sampling Data Structure ................................................191
8.2.3 Preliminary Results ......................................................................................................192
8.3 Sound Rendering .....................................................................................................................192
8.3.1 Overview ........................................................................................................................192
8.3.2 The Sound Rendering Algorithm..................................................................................193
8.3.3 Results............................................................................................................................194
8.4 Caustics Rendering..................................................................................................................194
8.4.1 Overview.194
8.4.2 Problems and Solutions ................................................................................................195
8.4.3 Results....196
ix 9 Conclusions and Future Work 197
9.1 Conclusions.............................................................................................................................. 197
9.1.1 Summary....................................................................................................................... 197
9.1.2 Main Results ................................................................................................................. 198
9.1.3 Discussion ..................................................................................................................... 200
9.1.4 Conclusions ................................................................................................................... 201
9.2 Future Work........ 201

Appendix A : Tables / Measurements 205
References 211
x

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.