Real-Time Collision Detection

The most complete engineering guide to Collision Detection available. Presents algorithms and data structures with wide applications to the fields of game development, virtual reality, physically based simulation, CAD/CAM, architectural and scientific visualization, molecular modeling, engineering simulation, GIS, ray tracing, and more; Describes tested, real-world methods, liberally illustrated by C & C++ code; Reviews necessary concepts from mathematics and computational geometry, and includes extensive references to other sources and research literature

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.

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 Detect

Christer Ericson is a senior principal programmer and the tools and technology lead at Sony Computer Entertainment America in Santa Monica. Before joining Sony in 1999, he was a senior programmer at Neversoft Entertainment. Christer received his Masters degree in computer science from Umeå University, Sweden, where he also lectured for several years before moving to the US in 1996. Christer has served on the advisory board for Full Sail's Game Design and Development degree program since 2002. His interests are varied, but he takes a particular interest in program optimization, a topic he has spoken on at the Game Developers Conference.