Efficient collision detection for point and polygon based models / von Jan Klein. 2005
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.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.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.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