Design, analysis, and evaluation of a data structure for distributed virtual environments / von Matthias Fischer. 2005
Content
- 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