Design, Analysis, and Evaluation of a Data Structure
for Distributed Virtual Environments
Dissertation von Matthias Fischer
Schriftliche Arbeit zur Erlangung des Grades eines Doktors der Naturwissenschaften
Heinz Nixdorf Institut und
Institut f¨ur Informatik
Fakult¨at f¨ur Elektrotechnik, Informatik und Mathematik
Universit¨at Paderborn Paderborn, im Februar 2005
F¨ur meine Eltern,
meine Frau Hanne und
meine Kinder Miriam & Carolin
Herzlichen Dank
f¨ur ihre ideelle Unterst¨utzung,
ihre Geduld, Entbehrungen und ihr Verst¨andnis
Contents
1 Introduction to a System for Networked Virtual Environments 5
2 Background and State of the Art 11
2.1 Classification of Methods for Scene Complexity Reduction . . . . . . . . 15
2.1.1 Level of Detail Concepts . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Polygonal Surface Simplification . . . . . . . . . . . . . . . . . . 18
2.1.3 Point Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.4 Visibility Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Parallel Rendering and Networked Virtual Environments . . . . . . . . . 24
2.2.1 Real-Time Rendering on Clusters . . . . . . . . . . . . . . . . . . 26
2.2.2 Remote Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.3 Visibility-Based Approaches . . . . . . . . . . . . . . . . . . . . . 29
2.2.4 Networked Virtual Environments . . . . . . . . . . . . . . . . . . 30
2.3 Data Structures from Computational Geometry . . . . . . . . . . . . . . 32
2.3.1 Range Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.2 Graph Spanners and Geometric Spanners . . . . . . . . . . . . . 34
2.3.3 Spatial Data Structures . . . . . . . . . . . . . . . . . . . . . . . 38
3 Architecture and Functionality of the System 41
3.1 Underlying Abstraction of Dynamic, Fully Distributed Scenes . . . . . . 41
3.1.1 Scenes Composed from Abstract Objects . . . . . . . . . . . . . 41
3.1.2 Interactive Multi-User Navigation and Manipulation . . . . . . . 43
3.1.3 Distributed Virtual Scenes . . . . . . . . . . . . . . . . . . . . . . 44
3.1.4 Bubbles: A Spatial Hierarchy of Caches . . . . . . . . . . . . . . 45
3.2 Elementary Operations for Navigation and Manipulation . . . . . . . . . 47
3.2.1 Reporting from the Scene . . . . . . . . . . . . . . . . . . . . . . 48
3.2.2 Insertion to and Deletion from the Scene . . . . . . . . . . . . . . 49
3.2.3 Incremental Motion of Bubbles . . . . . . . . . . . . . . . . . . . 50
3.3 Resulting Requirements to the Data Structure . . . . . . . . . . . . . . 50
1
Loading more pages...