cnt
| | Tarih: 08.10.2005, 21:01 Mesaj konusu: Efficient Collision Detection for Animation and Robotics by | |
| Efficient Collision Detection for Animation and Robotics by Ming C. Lin (1993).pdf
D.L.
Contents
List of Figures viii
1 Introduction 1
1.1 Previous Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
1.2 Overview of the Thesis : : : : : : : : : : : : : : : : : : : : : : : : : : 9
2 Background 12
2.1 Basic Concenpts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12
2.1.1 Model Representations : : : : : : : : : : : : : : : : : : : : : : 12
2.1.2 Data Structures and Basic Terminology : : : : : : : : : : : : : 14
2.1.3 Voronoi Diagram : : : : : : : : : : : : : : : : : : : : : : : : : 16
2.1.4 Voronoi Region : : : : : : : : : : : : : : : : : : : : : : : : : : 17
2.2 Object Modeling : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17
2.2.1 Motion Description : : : : : : : : : : : : : : : : : : : : : : : : 18
2.2.2 System of Algebraic Equations : : : : : : : : : : : : : : : : : : 19
3 An Incremental Distance Computation Algorithm 21
3.1 Closest Feature Pair : : : : : : : : : : : : : : : : : : : : : : : : : : : 22
3.2 Applicability Criteria : : : : : : : : : : : : : : : : : : : : : : : : : : : 25
3.2.1 Point-Vertex Applicability Criterion : : : : : : : : : : : : : : : 25
3.2.2 Point-Edge Applicability Criterion : : : : : : : : : : : : : : : 25
3.2.3 Point-Face Applicability Criterion : : : : : : : : : : : : : : : : 26
3.2.4 Subdivision Procedure : : : : : : : : : : : : : : : : : : : : : : 28
3.2.5 Implementation Issues : : : : : : : : : : : : : : : : : : : : : : 29
3.3 The Algorithm : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 32
3.3.1 Description of the Overall Approach : : : : : : : : : : : : : : 32
3.3.2 Geometric Subroutines : : : : : : : : : : : : : : : : : : : : : : 36
3.3.3 Analysis of the Algorithm : : : : : : : : : : : : : : : : : : : : 38
3.3.4 Expected Running Time : : : : : : : : : : : : : : : : : : : : : 39
3.4 Proof of Completeness : : : : : : : : : : : : : : : : : : : : : : : : : : 40
3.5 Numerical Experiments : : : : : : : : : : : : : : : : : : : : : : : : : : 52
vi
3.6 Dynamic Collision Detection for Convex Polyhedra : : : : : : : : : : 56
4 Extension to Non-Convex Objects and Curved Objects 58
4.1 Collision Detection for Non-convex Objects : : : : : : : : : : : : : : : 58
4.1.1 Sub-Part Hierarchical Tree Representation : : : : : : : : : : : 58
4.1.2 Detection for Non-Convex Polyhedra : : : : : : : : : : : : : : 61
4.2 Collision Detection for Curved Objects : : : : : : : : : : : : : : : : : 64
4.2.1 Collision Detection and Surface Intersection : : : : : : : : : : 64
4.2.2 Closest Features : : : : : : : : : : : : : : : : : : : : : : : : : : 64
4.2.3 Contact Formulation : : : : : : : : : : : : : : : : : : : : : : : 68
4.3 Coherence for Collision Detection between Curved Objects : : : : : : 71
4.3.1 Approximating Curved Objects by Polyhedral Models : : : : : 71
4.3.2 Convex Curved Surfaces : : : : : : : : : : : : : : : : : : : : : 72
4.3.3 Non-Convex Curved Objects : : : : : : : : : : : : : : : : : : : 74
5 Interference Tests for Multiple Objects 77
5.1 Scheduling Scheme : : : : : : : : : : : : : : : : : : : : : : : : : : : : 78
5.1.1 Bounding Time to Collision : : : : : : : : : : : : : : : : : : : 78
5.1.2 The Overall Approach : : : : : : : : : : : : : : : : : : : : : : 80
5.2 Sweep & Sort and Interval Tree : : : : : : : : : : : : : : : : : : : : : 81
5.2.1 Using Bounding Volumes : : : : : : : : : : : : : : : : : : : : : 81
5.2.2 One-Dimensional Sort and Sweep : : : : : : : : : : : : : : : : 84
5.2.3 Interval Tree for 2D Intersection Tests : : : : : : : : : : : : : 85
5.3 Other Approaches : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86
5.3.1 BSP-Trees and Octrees : : : : : : : : : : : : : : : : : : : : : : 86
5.3.2 Uniform Spatial Subdivision : : : : : : : : : : : : : : : : : : : 87
5.4 Applications in Dynamic Simulation and Virtual Environment : : : : 87
6 An Opportunistic Global Path Planner 89
6.1 Background : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 90
6.2 A Maximum Clearance Roadmap Algorithm : : : : : : : : : : : : : : 92
6.2.1 De nitions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 92
6.2.2 The General Roadmap : : : : : : : : : : : : : : : : : : : : : : 93
6.3 De ning the Distance Function : : : : : : : : : : : : : : : : : : : : : 99
6.4 Algorithm Details : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 100
6.4.1 Freeways and Bridges : : : : : : : : : : : : : : : : : : : : : : : 101
6.4.2 Two-Dimensional Workspace : : : : : : : : : : : : : : : : : : : 103
6.4.3 Three-Dimensional Workspace : : : : : : : : : : : : : : : : : : 106
6.4.4 Path Optimization : : : : : : : : : : : : : : : : : : : : : : : : 107
6.5 Proof of Completeness for an Opportunistic Global Path Planner : : 108
6.6 Complexity Bound : : : : : : : : : : : : : : : : : : : : : : : : : : : : 114
6.7 Geometric Relations between Critical Points and Contact Constraints 114
vii
6.8 Brief Discussion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 116
7 Conclusions 118
7.1 Summary : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 118
7.2 Future Work : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 119
7.2.1 Overlap Detection for Convex Polyhedra : : : : : : : : : : : : 120
7.2.2 Intersection Test for Concave Objects : : : : : : : : : : : : : : 121
7.2.3 Collision Detection for Deformable objects : : : : : : : : : : : 123
7.2.4 Collision Response : : : : : : : : : : : : : : : : : : : : : : : : 125
Bibliography 127
A Calculating the Nearest Points between Two Features 136
B Pseudo Code of the Distance Algorithm 139
rar password: Kod: www.elektrotekno.com
|
|
