Design, analysis, and evaluation of a data structure for distributed virtual environments / von Matthias Fischer. 2005
Inhalt
1 Introduction to a System for Networked Virtual Environments
2 Background and State of the Art
2.1 Classification of Methods for Scene Complexity Reduction
2.1.1 Level of Detail Concepts
2.1.2 Polygonal Surface Simplification
2.1.3 Point Sampling
2.1.4 Visibility Culling
2.2 Parallel Rendering and Networked Virtual Environments
2.2.1 Real-Time Rendering on Clusters
2.2.2 Remote Rendering
2.2.3 Visibility-Based Approaches
2.2.4 Networked Virtual Environments
2.3 Data Structures from Computational Geometry
3 Architecture and Functionality of the System
3.1 Underlying Abstraction of Dynamic, Fully Distributed Scenes
3.1.1 Scenes Composed from Abstract Objects
3.1.2 Interactive Multi-User Navigation and Manipulation
3.1.3 Distributed Virtual Scenes
3.1.4 Bubbles: A Spatial Hierarchy of Caches
3.2 Elementary Operations for Navigation and Manipulation
3.2.1 Reporting from the Scene
3.2.2 Insertion to and Deletion from the Scene
3.2.3 Incremental Motion of Bubbles
3.3 Resulting Requirements to the Data Structure
3.3.1 Spatial Locality
3.3.2 Support for Cut and Paste
3.3.3 Support for Duplication
3.3.4 Support for a Combined Bubble and Storage Hierarchy
3.4 Summary and Discussion
4 Our Data Structure and Algorithms
4.1 Weak-Spanner Approach
4.2 The Sectorgraph
4.2.1 Circular Range Query in Output-Sensitive Time
4.2.2 Constructing the Sectorgraph in O(n log(n))
4.3 Limitations and Overcoming Them
4.3.1 Deserts and Long Edges
4.3.2 Unbounded Accumulation
4.3.3 Crowded Scenes, Dummy Balls, and Non-Overlapping Objects
4.4 Implementation of Bubbles Using the Sectorgraph
4.4.1 Cutting a Subgraph of the Sectorgraph
4.4.2 Algorithms for Reporting and Incremental Motion
4.4.3 Algorithms for Insertion and Deletion
4.4.4 Composing a Large Scene
4.5 Summary and Discussion
5 Implementation and Evaluation
5.1 Functionality and User Interfaces
5.1.1 Scene Construction and 2D Viewer
5.1.2 Generation of an Arbitrary Bubble Hierarchy
5.1.3 3D Navigation and Manipulation of the Scene
5.2 Implementation of the Bubbles
5.3 Benchmark
5.4 Construction and Recomputation of a Scene
5.4.1 Construction Time for Different Storage Types
5.4.2 Multiple Managers for a Storage Across a Network
5.5 Motions Through the Scene
5.5.1 The Radii of Bubbles
5.5.2 Benchmark
5.5.3 Movements with one Bubble
5.5.4 Movements with two Bubbles
5.6 Summary and Discussion
6 Conclusion and Further Development
Bibliography