Efficient data structures for distributed and mobile geometry processing [Elektronische Ressource] / vorgelegt von Jianhua Wu

Jianhua Wu

Sujets

• Informatik

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2006
• Nombre de lectures: 22
• Langue: Deutsch
• Poids de l'ouvrage: 25 Mo

Extrait

E cient Data Structures for
Distributed and Mobile
Geometry Processing
Von der Fakulatt fur Mathematik, Informatik und
Naturwissenschaften der Rheinisch-Westf alischen Technischen
Hochschule Aachen zur Erlangung des akademischen Grades
eines Doktors der Naturwissenschaften genehmigte Dissertation
vorgelegt von
Master-of-Science Jianhua Wu
aus Zhejiang, China
Berichter: Prof. Dr. Leif Kobbelt
Prof. Dr. Shimin Hu
Prof. Dr. Petri M ahonen
Tag der mund lichen Prufung : 07. M arz 2006
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugb ar.Contents
Preface v
Zusammenfassung vii
Acknowledgements ix
1 Introduction 1
1.1 3D Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Distributed and Mobile Processing . . . . . . . . . . . . . . . . . . . . . 4
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Geometric Data Structures 11
2.1 Parametric Representations . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Explicit Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Implicit Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Special Notes On Conversion and Compression . . . . . . . . . . . . . . . 19
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Part I: Parametric 23
3 Multiple-Choice Decimation 25
3.1 Standard Mesh Decimation Algorithms . . . . . . . . . . . . . . . . . . . 26
3.2 Multiple-Choice Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3Choice Decimation . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
iContents
3.3.2 Mapping MCA to Mesh Decimation . . . . . . . . . . . . . . . . . 30
3.3.3 Detailed Decimation Algorithm . . . . . . . . . . . . . . . . . . . 31
3.4 Comparisons and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 Progressive Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 Geometric Stream Decimation 41
4.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 Ideal Stream Algorithm for Decimation . . . . . . . . . . . . . . . . . . . 44
4.3 Real Stream Algorithm for Decimation . . . . . . . . . . . . . . . . . . . 46
4.3.1 Overall Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.2 Reading Input Streams . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.3 Multiple-Choice Decimation . . . . . . . . . . . . . . . . . . . . . 51
4.3.4 Writing Output Streams . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.1 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 3D Digital Watermarking 59
5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Overview of the Watermarking Algorithm . . . . . . . . . . . . . . . . . 62
5.3 New Orthogonal Basis Functions . . . . . . . . . . . . . . . . . . . . . . 64
5.4 Watermark Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.5 Watermark Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.6 Watermarking Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.6.1 Overall Performance . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.6.2 Robustness Against Attacks . . . . . . . . . . . . . . . . . . . . . 72
5.6.3 Comparing to Laplace Basis Functions . . . . . . . . . . . . . . . 74
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Part II: Explicit 79
6 Optimized Splat Sub-Sampling 81
6.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2 Previous Work on Explicit Geometry . . . . . . . . . . . . . . . . . . . . 83
iiContents
6.3 Sub-Sampling Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.4 Initial Splat Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.4.1 Elliptical Splats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.4.2 Hole-free Approximation . . . . . . . . . . . . . . . . . . . . . . . 89
6.5 Greedy Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.6 Global Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.6.1 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.6.2 Removing Redundant Splats . . . . . . . . . . . . . . . . . . . . . 94
6.7 Results and Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.7.1 Elliptical vs. Circular Splats . . . . . . . . . . . . . . . . . . . . . 98
6.7.2 Comparing to Point Cloud Simpli cation . . . . . . . . . . . . . . 98
6.7.3 Comparing to Mesh Simpli cation . . . . . . . . . . . . . . . . . . 99
6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7 Progressive Splatting 103
7.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.2 Progressive Splat Decimation Algorithm . . . . . . . . . . . . . . . . . . 106
7.3 Initial Splat Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.4 Error Metrics and Splat Merge Operators . . . . . . . . . . . . . . . . . . 107
27.4.1 L Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
2,17.4.2 L Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.5 Progressive Splat Structures . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.6 Compressed Progressive Splat Transmission . . . . . . . . . . . . . . . . 110
7.6.1 Structure Transformation . . . . . . . . . . . . . . . . . . . . . . 111
7.6.2 The Prediction Rule . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.6.3 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.6.4 Entropy coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.6.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.7 Results and Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.7.1 Comparison to Splat Decimation Methods . . . . . . . . . . . . . 116
7.7.2 Comparison to Mesh Simpli cation . . . . . . . . . . . . . . . . . 118
7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Part III: Implicit 123
iiiContents
8 Piecewise Linear Distance Fields 125
8.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.2 Previous Implicit Data Structures . . . . . . . . . . . . . . . . . . . . . . 128
8.3 Piecewise Linear Signed Distance Fields . . . . . . . . . . . . . . . . . . 129
8.4 Generation Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.4.1 Least Squares Linear Approximation . . . . . . . . . . . . . . . . 131
8.4.2 BSP Splitting Plane Selection . . . . . . . . . . . . . . . . . . . . 132
8.4.3 Final Linear Approximation Correction . . . . . . . . . . . . . . . 136
8.4.4 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.5 Results and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
9 Robust Structure Recovery 143
9.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.2 Variational Surface Approximation . . . . . . . . . . . . . . . . . . . . . 146
9.3 Hybrid Variational Surface Approximation . . . . . . . . . . . . . . . . . 147
9.3.1 Sphere Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
9.3.2 Cylinder Fitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.3.3 Rolling-Ball Blend Patch Fitting . . . . . . . . . . . . . . . . . . 152
9.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
10 Conclusion 161
Bibliography 169
Curriculum Vitae 189
ivPreface
This thesis addresses the data structure and geometry representation problems which
arise in the emerging interdisciplinary research eld of distributed and mobile geometry
processing.
On the one hand, three-dimensional geometry is now establishing as a new digital
multimedia data type after text and sound in 1980’ and images and video in 1990’. The
major advantage of 3D geometric data over previous multimedia data is that it enables
users to actually interact with the displayed contents, which paves the way to more and
enhanced interactive multimedia applications.
On the other hand, the rapid evolution of the network technology brings new poten-
tials for communication between people and computers in heterogeneous environments.
Nowadays computing hardware becomes more powerful and also turns out to be ubiqui-
tous thanks to the ever increasing availability of distributed and mobile digital devices.
When we combine the strength from both above elds, we come to