Real-Time Collision DetectionBy
- Christer Ericson, Sony Computer Entertainment America, Santa Monica, California, U.S.A.
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.
Professionals or students working in software engineering, game development, simulation, scientific visualization, or virtual reality.
Published: December 2004
Imprint: Morgan Kaufmann
"Accurate and efficient collision detection in complex environments is one of the foundations of today's cutting-edge computer games. Yet collision detection is notoriously difficult to implement robustly and takes up an increasingly large fraction of compute cycles in current game engines as increasingly detailed environments are becoming the norm. Real-time Collision Detection is a comprehensive reference on this topic, covering it with both breadth and depth. Not only are the fundamental algorithms explained clearly and in detail, but Ericson's book covers crucial implementation issues, including geometric and numeric robustness and cache-efficient implementations of the algorithms. Together, these make this book a 'must have' practical reference for anyone interested in developing interactive applications with complex environments." Matt Pharr, NVIDIA "Christer Ericson's Real-time Collision Detection is an excellent resource that covers the fundamentals as well as a broad array of techniques applicable to game development." Jay Stelly, Valve "Christer Ericson provides a practical and very accessible treatment of real-time collision detection. This includes a comprehensive set of C++ implementations of a very large number of routines necessary to build such applications in a context which is much broader than just game programming. The programs are well-thought out and the accompanying discussion reveals a deep understanding of the graphics, algorithms, and ease of implementation issues. It will find a welcome home on any graphics programmer's bookshelf although it will most likely not stay there long as others will be constantly borrowing it...." Hanan Samet, University of Maryland "Real-Time Collision Detection is an excellent resource that every serious engine programmer should have on his bookshelf. Christer Ericson covers an impressive range of techniques and presents them using concise mathematics, insightful figures, and practical code." Eric Lengyel, Senior Programmer, Naughty Dog "If you think you already know everything about collision detection, you're in for a surprise! This book not only does an excellent job at presenting all the collision detection methods known to date, it also goes way beyond the standard material thanks to a plethora of juicy, down-to-earth, hard-learned implementation tips and tricks. This produces a perfect blend between theory and practice, illustrated by the right amount of source code in appropriate places. Basically the book just oozes with experience. Christer doesn't forget all the alternative topics that, despite not directly related to collision detection, can ruin your implementation if you don't include them in your design. The chapters on robustness and optimization are priceless in this respect. Its carefully crafted compact kd-tree implementation beautifully concludes a unique book full of luminous gems." Pierre Terdiman, principal software engineer, NovodeX AG, and writer of the popular collision detection library Opcode "When I received a copy of Real-Time Collision Detection for review, I was in the midst of redesigning an architectural visualization and lighting design program. The Bounding Volume Hierarchies chapter allowed me to quickly and easily design and implement an efficient ray tracing acceleration scheme. It also provided me with a wealth of information on various design strategies, which gave me the confidence that I had chosen a near-optimal approach. What one of my clients recently said about the finished software reflects my opinion of this fantastic book: 'Holy cow! Excellent work!'" Ian Ashdown, byHeart Consultants Limited
1 Introduction1.1 Contents Overview1.2 About the Code
2 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 Summary
3 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 Predicates220.127.116.11 ORIENT2D(A, B, C)18.104.22.168 ORIENT3D(A, B, C, D)22.214.171.124 INCIRCLE2D(A, B, C, D)126.96.36.199 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 Summary
4 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 Summary
5 Basic Primitive Tests5.1 Closest Point Computations5.1.1 Closest Point on Plane to Point5.1.2 Closest Point on Line Segment to Point188.8.131.52 Distance of Point to Segment5.1.3 Closest Point on AABB to Point184.108.40.206 Distance of Point to AABB5.1.4 Closest Point on OBB to Point220.127.116.11 Distance of Point to OBB18.104.22.168 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 Segments22.214.171.124 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 Test126.96.36.199 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 Summary
6 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 Construction188.8.131.52 Partitioning Strategies184.108.40.206 Choice of Partitioning Axis220.127.116.11 Choice of Split Point6.2.2 Bottom-Up Construction18.104.22.168 Improved Bottom-Up Construction22.214.171.124 Other Bottom-Up Construction Strategies126.96.36.199 Bottom-Up N-Ary Clustering Trees6.2.3 Incremental (Insertion) Construction188.8.131.52 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 Summary
7 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 Test184.108.40.206 One Test at a Time220.127.116.11 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 Summary
8 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 Summary
9 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 Programming18.104.22.168 Fourier-Motzkin Elimination22.214.171.124 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 Summary
10 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 Summary
11 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 Summary
12 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 Cutting126.96.36.199 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 Summary
13 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 Summary