Book123

    Free register and download UseNet downloader, then you can FREE Download from UseNet.

    Download without Limit " Programming Efficient Collision Detection for Animation and Robotics by " from UseNet for FREE!

Efficient Collision Detection for Animation and Robotics by Ming C. Lin (1993).pdf

Buy Book at Lowest Price on Amazon

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

"

Rating:
2.5 out of 5 by Book123