| Chapter1 introduction | 第1-12页 |
| 1．1 The importance and applications of collision detection | 第8-9页 |
| 1．2 Collision detection objective analysis | 第9-11页 |
| 1．3 The organization of this dissertation | 第11-12页 |
| Chapter 2 Background and Related Work | 第12-34页 |
| 2．1 Problem Classification | 第12-18页 |
| 2．1．1 Model Representations | 第12-15页 |
| 2．1．1．1 Polygonal models | 第12-13页 |
| 2．1．1．2 Constructive Solid Geometry | 第13-14页 |
| 2．1．1．3 Implicit Surfaces | 第14页 |
| 2．1．1．4 Parametric Surfaces | 第14-15页 |
| 2．1．2 Proximity Measures | 第15-17页 |
| 2．1．2．1 Collision and Intersection | 第15-16页 |
| 2．1．2．2 Distance Measures | 第16-17页 |
| 2．1．3 Simulation Environments | 第17-18页 |
| 2．1．3．1 Pair Processing vs．N-Body Processing | 第17页 |
| 2．1．3．2 Dynamic Scenarios and Temporal Coherence | 第17-18页 |
| 2．1．3．3 Rigid Bodies vs． Deformable Models | 第18页 |
| 2．2 Collision Detection for Polygonal Models | 第18-26页 |
| 2．2．1 Convex Polytopes | 第18-25页 |
| 2．2．1．1 Linear Programming | 第19-21页 |
| 2．2．1．2 GJK Minkowski Differences | 第21页 |
| 2．2．1．3 Dobkin-Kirkpatrick Drums | 第21-22页 |
| 2．2．1．4 Lin-Canny Algorithm | 第22-23页 |
| 2．2．1．5 Enhanced GJK | 第23页 |
| 2．2．1．6 Spatial Partitioning for polygon soups | 第23-25页 |
| 2．2．2 Selection of Bounding Volume | 第25-26页 |
| 2．3 Collision detection for non-polygonal models | 第26-32页 |
| 2．3．1 Constructive solid geometry models | 第27-28页 |
| 2．3．2 Parametric surfaces | 第28-31页 |
| 2．3．3 Implicit surface | 第31-32页 |
| 2．4 N-Body Processing | 第32-34页 |
| 2．4．1 Scheduling Scheme | 第32页 |
| 2．4．2 Sorting-Based Sweep and Prune | 第32-33页 |
| 2．4．3 Interval Tree for 2D Intersection Tests | 第33页 |
| 2．4．4 Uniform Spatial Subdivision | 第33-34页 |
| Chapter3 Collision detection in a large-scale VW systems | 第34-49页 |
| 3．1 The basic algotithm analysis | 第34-39页 |
| 3．1．1 Basic algorithm | 第34-37页 |
| 3．1．2 Weaknesses of the Basic Algorithm | 第37-39页 |
| 3．2 Application analysis | 第39-49页 |
| 3．2．1 Large-scale population demand | 第39-40页 |
| 3．2．2 Possible collaboration | 第40页 |
| 3．2．3 Realtime requirements and solution | 第40-49页 |
| Chapter 4 Objectdriven collision detectiona realtime solution | 第49-64页 |
| 4．1 Related solution for allpair weakness | 第49-50页 |
| 4．2 ldea of Object driven collision | 第50-52页 |
| 4．3 The collision detection algorithm | 第52-61页 |
| 4．3．1 Virtual grid | 第52-53页 |
| 4．3．2 The data structure of the objects for collision detection | 第53-54页 |
| 4．3．3 Contact determination | 第54-55页 |
| 4．3．4 refinement and levels of the virtual grid | 第55-57页 |
| 4．3．5 the Pseudocode of the algorithm | 第57-61页 |
| 4．4 Collision detection for distributed virtual world simulation | 第61-64页 |
| Chapter 5 Performance analysis | 第64-69页 |
| 5．1 Theoretic analysis | 第64-66页 |
| 5．2 Empirical Analysis | 第66-69页 |
| Chapter 6 Conclusion and future work | 第69-80页 |
