Content

•  
   Acknowledgements
•  
   1 Introduction
•  
  2 Related Work
•  
   2.1 Problem Statement
•  
  2.2 Polygonal Collision Detection
•  
   2.2.1 Bounding Volume Hierarchies
•  
   2.2.2 Space-Subdivision Approaches
•  
   2.2.3 Distance Fields
•  
   2.2.4 Hardware-Assisted Collision Detection
•  
   2.2.5 Theoretical Results
•  
   2.3 Point Cloud Collision Detection
•  
   2.3.1 Surface Definition
•  
   2.3.2 Algorithms for Point Cloud Collision Detection
•  
   2.4 Time-Critical Collision Detection
•  
   2.5 Summary and Discussion
•  
  3 An Average-Case Approach for Real-Time Collision Detection
•  
   3.1 Overview of our Approach
•  
   3.2 Terms and Definitions
•  
   3.3 Data Structure
•  
  3.4 Probability Parameters
•  
   3.4.1 Uniform polygon distribution
•  
   3.4.2 Non-uniform polygon distribution
•  
  3.5 Probability Computations
•  
   3.5.1 Probability of collision cells
•  
   3.5.2 Probability of collision
•  
   3.5.3 Probability of intersection in a cell
•  
   3.6 Intersection Volume
•  
   3.7 Expected Running Time of Hierarchical Collision Detection
•  
   3.8 Results
•  
   3.8.1 Benchmark Scenario
•  
   3.8.2 Distribution of Possible Collision Cells
•  
   3.8.3 Preprocessing
•  
   3.8.4 Performance and Quality
•  
   3.9 Summary and Discussion
•  
   3.10 Future Work
•  
   4 Point Cloud Surfaces using Geometric Proximity Graphs
•  
   4.1 Implicit Surface Model
•  
   4.1.1 WLS Surface Definition
•  
   4.1.2 Problems with the Euclidean Kernel
•  
   4.2 Geodesic Distance Approximation
•  
   4.2.1 Geodesic Kernel
•  
   4.2.2 Proximity by Delaunay Graph
•  
   4.2.3 Proximity by Sphere-of-Influence Graph
•  
   4.2.4 Extensions of the SIG
•  
   4.2.5 Automatic and local bandwidth computation
•  
   4.2.6 Automatic boundary detection
•  
   4.2.7 Smooth Surfaces
•  
   4.3 Running time and Complexity
•  
   4.3.1 Close-Pairs Shortest-Paths
•  
   4.3.2 Pre-computations of Proximity Graphs
•  
   4.3.3 Function Evaluation
•  
   4.3.4 Dynamic Point Clouds
•  
   4.4 Results
•  
   4.5 Summary and Discussion
•  
   4.6 Future Work
•  
   5 Point Cloud Collision Detection
•  
   5.1 Terms and Definitions
•  
   5.2 An Efficient Point Cloud Hierarchy Traversal
•  
   5.2.1 Point Cloud Hierarchy
•  
   5.2.2 Exclusion and Priority Criterion
•  
   5.2.3 RST: Randomized Sampling Technique
•  
   5.2.4 Time-Critical Collision Detection
•  
   5.2.5 Automatic Bandwidth Detection
•  
   5.2.6 Sample Size
•  
   5.2.7 Running time and Complexity
•  
   5.2.8 Results
•  
   5.3 Interpolation Search for Point Cloud Intersection
•  
   5.3.1 Root Bracketing
•  
   5.3.2 Size of Neighborhoods and Surfel Density
•  
   5.3.3 Completing the Brackets
•  
   5.3.4 Interpolation Search
•  
   5.3.5 Models with Boundaries
•  
   5.3.6 Precise Intersection Points
•  
   5.3.7 Complexity Considerations
•  
   5.3.8 Results
•  
   5.4 Summary and Discussion
•  
   5.5 Future Work
•  
   6 Conclusions and Future Work
•  
   Bibliography