Collision Detection in Interactive 3D Environments

ISBN: 9781558608016 出版年：2003 页码：309 van den Bergen, Gino CRC Press

1 Introduction 1.1 Problem Domain 1.2 Historical Background 1.3 Organization 2 Concepts 2.1 Geometry 2.1.1 Notational Conventions 2.1.2 Vector Spaces 2.1.3 Affine Spaces 2.1.4 Euclidean Spaces 2.1.5 Affine Transformations 2.1.6 Three-dimensional Space 2.2 Objects 2.2.1 Polytopes 2.2.2 Polygons 2.2.3 Quadrics 2.2.4 Minkowski Addition 2.2.5 Complex Shapes and Scenes 2.3 Animation 2.4 Time 2.5 Response 2.6 Performance 2.6.1 Frame Coherence 2.6.2 Geometric Coherence 2.6.3 Average Time 2.7 Robustness 2.7.1 Floating-Point Numbers 2.7.2 Stability 2.7.3 Coping with Numerical Problems 3 Basic Primitives 3.1 Spheres 3.1.1 Sphere-Sphere Test 3.1.2 Ray-Sphere Test 3.1.3 Line-Segment-Sphere Test 3.2 Axis-Aligned Boxes 3.2.1 Ray-Box Test 3.2.2 Sphere-Box Test 3.3 Separating Axes 3.3.1 Line-Segment-Box Test 3.3.2 Triangle-Box Test 3.3.3 Box-Box Test 3.4 Polygons 3.4.1 Ray-Triangle Test 3.4.2 Line Segment-Triangle Test 3.4.3 Ray-Polygon Test 3.4.4 Triangle-Triangle Test 3.4.5 Polygon-Polygon Test 3.4.6 Triangle-Sphere Test 3.4.7 Polygon-Volume Tests 4 Convex Objects 4.1 Proximity Queries 4.2 Overview of Algorithms for Polytopes 4.2.1 Finding a Common Point 4.2.2 Finding a Separating Plane 4.2.3 Distance and Penetration Depth Computation 4.3 The Gilbert-Johnson-Keerthi Algorithm 4.3.1 Overview 4.3.2 Convergence and Termination 4.3.3 Johnson's Distance Algorithm 4.3.4 Support Mappings 4.3.5 Implementing the GJK Algorithm 4.3.6 Numerical Aspects of the GJK Algorithm 4.3.7 Testing for Intersections 4.3.8 Penetration Depth 5 Spatial Data Structures 5.1 Nonconvex Polyhedra 5.1.1 Convex Decomposition 5.1.2 Polyhedral Surfaces 5.1.3 Point in Nonconvex Polyhedron 5.2 Space Partitioning 5.2.1 Voxel Grids 5.2.2 Octrees and k-d Trees 5.2.3 Binary Space Partitioning Trees 5.2.4 Discussion 5.3 Model Partitioning 5.3.1 Bounding Volumes 5.3.2 Bounding-Volume Hierarchies 5.3.3 AABB Trees versus OBB Trees 5.3.4 AABB Trees and Deformable Models 5.4 Broad Phase 5.4.1 Sweep and Prune 5.4.2 Implementing the Sweep-and-Prune Algorithm 5.4.3 Ray Casting and AABBs 6 Design of SOLID 6.1 Requirements 6.2 Overview of SOLID 6.3 Design Decisions 6.3.1 Shape Representation 6.3.2 Motion Specification 6.3.3 Response Handling 6.3.4 Algorithms 6.4 Evaluation 6.5 Implementation Notes 6.5.1 Generic Data Types and Algorithms 6.5.2 Fundamental 3D Classes 7 Conclusion 7.1 State of the Art 7.2 Future Work Bibliography Index About the CD-ROM Trademarks