- ホーム
- > 洋書
Full Description
Written by an expert in the game industry, Christer Ericson's new book is a comprehensive guide to the components of efficient real-time collision detection systems. The book provides the tools and know-how needed to implement industrial-strength collision detection for the highly detailed dynamic environments of applications such as 3D games, virtual reality applications, and physical simulators.Of the many topics covered, a key focus is on spatial and object partitioning through a wide variety of grids, trees, and sorting methods. The author also presents a large collection of intersection and distance tests for both simple and complex geometric shapes. Sections on vector and matrix algebra provide the background for advanced topics such as Voronoi regions, Minkowski sums, and linear and quadratic programming.Of utmost importance to programmers but rarely discussed in this much detail in other books are the chapters covering numerical and geometric robustness, both essential topics for collision detection systems. Also unique are the chapters discussing how graphics hardware can assist in collision detection computations and on advanced optimization for modern computer architectures. All in all, this comprehensive book will become the industry standard for years to come.
Contents
Preface1 Introduction1.1 Contents Overview1.2 About the Code2 Collision Detection Design Issues2.1 Collision Algorithm Design Factors2.2 Application Domain Representation2.2.1 Object Representations2.2.2 Collision versus Rendering Geometry2.2.3 Collision Algorithm Specialization2.3 Different Types of Queries2.4 Environment Simulation Parameters2.4.1 Number of Objects2.4.2 Sequential versus Simultaneous Motion2.4.3 Discrete versus Continuous Motion2.5 Performance2.5.1 Optimization Overview2.6 Robustness2.7 Ease of Implementation and Use2.7.1 Debugging a Collision Detection System2.8 Summary3 A Math and Geometry Primer3.1 Matrices3.1.1 Matrix Arithmetic3.1.2 Algebraic Identities Involving Matrices3.1.3 Determinants3.1.4 Solving Small Systems of Linear Equation using Cramer's Rule3.1.5 Matrix Inverses for 2x2 and 3x3 Matrices3.1.6 Determinant Predicates3.1.6.1 ORIENT2D(A, B, C)3.1.6.2 ORIENT3D(A, B, C, D)3.1.6.3 INCIRCLE2D(A, B, C, D)3.1.6.4 INSPHERE(A, B, C, D, E)3.2 Coordinate Systems and Points3.3 Vectors3.3.1 Vector Arithmetic3.3.2 Algebraic Identities Involving Vectors3.3.3 The Dot Product3.3.4 Algebraic Identities Involving Dot Products3.3.5 The Cross Product3.3.6 Algebraic Identities Involving Cross Products3.3.7 The Scalar Triple Product3.3.8 Algebraic Identities Involving Scalar Triple Products3.4 Barycentric Coordinates3.5 Lines, Rays, and Segments3.6 Planes and Halfspaces3.7 Polygons3.7.1 Testing Polygonal Convexity3.8 Polyhedra3.8.1 Testing Polyhedral Convexity3.9 Computing Convex Hulls3.9.1 Andrew's Algorithm3.9.2 The Quickhull Algorithm3.10 Voronoi Regions3.11 Minkowski Sum and Difference3.12 Summary4 Bounding Volumes4.1 Desired BV Characteristics4.2 Axis-Aligned Bounding Boxes (AABBs)4.2.1 AABB-AABB Intersection4.2.2 Computing and Updating AABBs4.2.3 AABB from the Object Bounding Sphere4.2.4 AABB Reconstructed from Original Point Set4.2.5 AABB from Hill-Climbing Vertices of the Object Representation4.2.6 AABB Recomputed from Rotated AABB4.3 Spheres4.3.1 Sphere-Sphere Intersection4.3.2 Computing a Bounding Sphere4.3.3 Bounding Sphere from Direction of Maximum Spread4.3.4 Bounding Sphere Through Iterative Refinement4.3.5 The Minimum Bounding Sphere4.4 Oriented Bounding Boxes (OBBs)4.4.1 OBB-OBB Intersection4.4.2 Making the Separating-Axis Test Robust4.4.3 Computing a Tight OBB4.4.4 Optimizing PCA-Based OBBs4.4.5 Brute-Force OBB Fitting4.5 Sphere-Swept Volumes4.5.1 Sphere-Swept Volume Intersection4.5.2 Computing Sphere-Swept Bounding Volumes4.6 Halfspace Intersection Volumes4.6.1 Kay-Kajiya Slab-Based Volumes4.6.2 Discrete-Orientation Polytopes (k-DOPs)4.6.3 k-DOP-k-DOP Overlap Test4.6.4 Computing and Realigning k-DOPs4.6.5 Approximate Convex Hull Intersection Tests4.7 Other Bounding Volumes4.8 Summary5 Basic Primitive Tests5.1 Closest Point Computations5.1.1 Closest Point on Plane to Point5.1.2 Closest Point on Line Segment to Point5.1.2.1 Distance of Point to Segment5.1.3 Closest Point on AABB to Point5.1.3.1 Distance of Point to AABB5.1.4 Closest Point on OBB to Point5.1.4.1 Distance of Point to OBB5.1.4.2 Closest Point on 3D Rectangle to Point5.1.5 Closest Point on Triangle to Point5.1.6 Closest Point on Tetrahedron to Point5.1.7 Closest Point on Convex Polyhedron to Point5.1.8 Closest Points of Two Lines5.1.9 Closest Points of Two Line Segments5.1.9.1 2D Segment Intersection5.1.10 Closest Points of a Line Segment and a Triangle5.1.11 Closest Points of Two Triangles5.2 Testing primitives5.2.1 Separating Axis Test5.2.1.1 Robustness of the Separating Axis Test5.2.2 Testing Sphere against Plane5.2.3 Testing Box against Plane5.2.4 Testing Cone against Plane5.2.5 Testing Sphere against AABB5.2.6 Testing Sphere against OBB5.2.7 Testing Sphere against Triangle5.2.8 Testing Sphere against Polygon5.2.9 Testing AABB against Triangle5.2.10 Testing Triangle against Triangle5.3 Intersecting Lines, Rays, and (Directed) Segments5.3.1 Intersecting Segment against Plane5.3.2 Intersecting Ray or Segment against Sphere5.3.3 Intersecting Ray or Segment against Box5.3.4 Intersecting Line against Triangle5.3.5 Intersecting Line against Quadrilateral5.3.6 Intersecting Ray or Segment against Triangle5.3.7 Intersecting Ray or Segment against Cylinder5.3.8 Intersecting Ray or Segment against Convex Polyhedron5.4 Additional Tests5.4.1 Testing Point in Polygon5.4.2 Testing Point in Triangle5.4.3 Testing Point in Polyhedron5.4.4 Intersection of Two Planes5.4.5 Intersection of Three Planes5.5 Dynamic Intersection Tests5.5.1 Interval Halving for Intersecting Moving Objects5.5.2 Separating Axis Test for Moving Convex Objects5.5.3 Intersecting Moving Sphere against Plane5.5.4 Intersecting Moving AABB against Plane5.5.5 Intersecting Moving Sphere against Sphere5.5.6 Intersecting Moving Sphere against Triangle (and Polygon)5.5.7 Intersecting Moving Sphere against AABB5.5.8 Intersecting Moving AABB against AABB5.6 Summary6 Bounding Volume Hierarchies6.1 Hierarchy Design Issues6.1.1 Desired BVH Characteristics6.1.2 Cost Functions6.1.3 Tree Degree6.2 Building Strategies for Hierarchy Construction6.2.1 Top-Down Construction6.2.1.1 Partitioning Strategies6.2.1.2 Choice of Partitioning Axis6.2.1.3 Choice of Split Point6.2.2 Bottom-Up Construction6.2.2.1 Improved Bottom-Up Construction6.2.2.2 Other Bottom-Up Construction Strategies6.2.2.3 Bottom-Up N-Ary Clustering Trees6.2.3 Incremental (Insertion) Construction6.2.3.1 The Goldsmith-Salmon Incremental Construction Method6.3 Hierarchy Traversal6.3.1 Descent Rules6.3.2 Generic Informed Depth-First Traversal6.3.3 Simultaneous Depth-First Traversal6.3.4 Optimized Leaf-Direct Depth-First Traversal6.4 Example Bounding Volume Hierarchies6.4.1 OBB-Trees6.4.2 AABB-Trees and BoxTrees6.4.3 Sphere-Tree through Octree Subdivision6.4.4 Sphere-Tree from Sphere-Covered Surfaces6.4.5 Generate-and-Prune Sphere Covering6.4.6 k-DOP Trees6.5 Merging Bounding Volumes6.5.1 Merging Two AABBs6.5.2 Merging Two Spheres6.5.3 Merging Two OBBs6.5.4 Merging Two k-DOPs6.6 Efficient Tree Representation and Traversal6.6.1 Array Representation6.6.2 Preorder Traversal Order6.6.3 Offsets Instead of Pointers6.6.4 Cache-Friendlier Structures (Non-Binary Trees)6.6.5 Tree Node and Primitive Ordering6.6.6 On Recursion6.6.7 Grouping Queries6.7 Improved Queries through Caching6.7.1 Surface Caching: Caching Intersecting Primitives6.7.2 Front Tracking6.8 Summary7 Spatial Partitioning7.1 Uniform Grids7.1.1 Cell Size Issues7.1.2 Grids as Arrays of Linked Lists7.1.3 Hashed Storage and Infinite Grids7.1.4 Storing Static Data7.1.5 Implicit Grids7.1.6 Uniform Grid Object-Object Test7.1.6.1 One Test at a Time7.1.6.2 All Tests at a Time7.1.7 Additional Grid Considerations7.2 Hierarchical Grids7.2.1 Basic Hgrid Implementation7.2.2 Alternative Hierarchical Grid Representations7.2.3 Other Hierarchical Grids7.3 Trees7.3.1 Octrees (and Quadtrees)7.3.2 Octree Object Assignment7.3.3 Locational Codes and Finding the Octant for a Point7.3.4 Linear Octrees (Hash-Based)7.3.5 Computing the Morton Key7.3.6 Loose Octrees7.3.7 k-d Trees7.3.8 Hybrid Schemes7.4 Ray and Directed Line Segment Traversals7.4.1 k-d Tree Intersection Test7.4.2 Uniform Grid Intersection Test7.5 Sort and Sweep Methods7.5.1 Sorted Linked List Implementation7.5.2 Array-Based Sorting7.6 Cells and Portals7.7 Avoiding Retesting7.7.1 Bit Flags7.7.2 Time Stamping7.7.3 Amortized Time Stamp Clearing7.8 Summary8 BSP Tree Hierarchies8.1 BSP Trees8.2 Types of BSP Trees8.2.1 Node-Storing BSP Trees8.2.2 Leaf-Storing BSP Trees8.2.3 Solid-Leaf BSP Trees8.3 Building the BSP Tree8.3.1 Selecting Dividing Planes8.3.2 Evaluating Dividing Planes8.3.3 Classifying Polygons with Respect to a Plane8.3.4 Splitting Polygons against a Plane8.3.5 More on Polygon splitting Robustness8.3.6 Tuning BSP Tree Performance8.4 using the BSP Tree8.4.1 Testing Point against a Solid-Leaf BSP Tree8.4.2 Intersecting Ray against a Solid-Leaf BSP Tree8.4.3 Polytope Queries on Solid-Leaf BSP Trees8.5 Summary9 Convexity-Based Methods9.1 Boundary-Based Collision Detection9.2 Closest Features Algorithms9.2.1 The V-Clip Algorithm9.3 Hierarchical Polyhedron Representations9.3.1 The Dobkin-Kirkpatrick Hierarchy9.4 Linear and Quadratic Programming9.4.1 Linear Programming9.4.1.1 Fourier-Motzkin Elimination9.4.1.2 Seidel's Algorithm9.4.2 Quadratic Programming9.5 The Gilbert-Johnson-Keerthi Algorithm9.5.1 The Gilbert-Johnson-Keerthi Algorithm9.5.2 Finding the Point of Minimum Norm in a Simplex9.5.3 GJK, Closest Points and Contact Manifolds9.5.4 Hill-Climbing for Extreme Vertices9.5.5 Exploiting Coherence by Vertex Caching9.5.6 Rotated Objects Optimization9.5.7 GJK for Moving Objects9.6 The Chung-Wang Separating Vector Algorithm9.7 Summary10 GPU-Assisted Collision Detection10.1 Interfacing with the GPU10.1.1 Buffer Readbacks10.1.2 Occlusion Queries10.2 Testing Convex Objects10.3 Testing Concave Objects10.4 GPU-Based Collision Filtering10.5 Summary11 Numerical Robustness11.1 Robustness Problem Types11.2 Representing Real Numbers11.2.1 The IEEE-754 Floating-Point Formats11.2.2 Infinity Arithmetic11.2.3 Floating-Point Error Sources11.3 Robust Floating-Point Usage11.3.1 Tolerances Comparisons for Floating-Point Values11.3.2 Robustness through Thick Planes11.3.3 Robustness through Sharing of Calculations11.3.4 Robustness of Fat Objects11.4 Interval Arithmetic11.4.1 Interval Arithmetic Examples11.4.2 Interval Arithmetic in Collision Detection11.5 Exact and Semi-Exact Computation11.5.1 Exact Arithmetic using Integers11.5.2 On Integer Division11.5.3 Segment Intersection using Integer Arithmetic11.6 Further Suggestions for Improving Robustness11.7 Summary12 Geometrical Robustness12.1 Vertex Welding12.2 Computing Adjacency Information12.2.1 Computing a Vertex-to-Face Table12.2.2 Computing an Edge-to-Face Table12.2.3 Testing Connectedness12.3 Holes, Cracks, Gaps, and T-Junctions12.4 Merging Coplanar Faces12.4.1 Testing Coplanarity of Two Polygons12.4.2 Testing Polygon Planarity12.5 Triangulation and Convex Partitioning12.5.1 Triangulation by Ear Cutting12.5.1.1 Triangulating Polygons with Holes12.5.2 Convex Decomposition of Polygons12.5.3 Convex Decomposition of Polyhedra12.5.4 Dealing with "Nondecomposable" Concave Geometry12.6 Consistency Testing using Euler's Formula12.7 Summary13 Optimization13.1 CPU Caches13.2 Instruction Cache Optimizations13.3 Data Cache Optimizations13.3.1 Structure Optimizations13.3.2 Quantized and Compressed Vertex Data13.3.3 Prefetching and Preloading13.4 Cache-Aware Data Structures and Algorithms13.4.1 A Compact Static k-d Tree13.4.2 A Compact AABB Tree13.4.3 Cache-Obliviousness13.5 Software Caching13.5.1 Cached Linearization Example13.5.2 Amortized Predictive Linearization Caching13.6 Aliasing13.6.1 Type-Based Alias Analysis13.6.2 Restricted Pointers13.6.3 Avoiding Aliasing13.7 Parallelism through SIMD Optimizations13.7.1 4 Spheres versus 4 Spheres SIMD Test13.7.2 4 Spheres versus 4 AABBs SIMD Test13.7.3 4 AABBs versus 4 AABBs SIMD Test13.8 Branching13.9 SummaryReferencesIndex
