1st Edition

Real-Time Collision Detection

By Christer Ericson Copyright 2005

    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.

    Preface

    1 Introduction
    1.1 Contents Overview
    1.2 About the Code

    2 Collision Detection Design Issues
    2.1 Collision Algorithm Design Factors
    2.2 Application Domain Representation
    2.2.1 Object Representations
    2.2.2 Collision versus Rendering Geometry
    2.2.3 Collision Algorithm Specialization
    2.3 Different Types of Queries
    2.4 Environment Simulation Parameters
    2.4.1 Number of Objects
    2.4.2 Sequential versus Simultaneous Motion
    2.4.3 Discrete versus Continuous Motion
    2.5 Performance
    2.5.1 Optimization Overview
    2.6 Robustness
    2.7 Ease of Implementation and Use
    2.7.1 Debugging a Collision Detection System
    2.8 Summary

    3 A Math and Geometry Primer
    3.1 Matrices
    3.1.1 Matrix Arithmetic
    3.1.2 Algebraic Identities Involving Matrices
    3.1.3 Determinants
    3.1.4 Solving Small Systems of Linear Equation using Cramer's Rule
    3.1.5 Matrix Inverses for 2x2 and 3x3 Matrices
    3.1.6 Determinant Predicates
    3.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 Points
    3.3 Vectors
    3.3.1 Vector Arithmetic
    3.3.2 Algebraic Identities Involving Vectors
    3.3.3 The Dot Product
    3.3.4 Algebraic Identities Involving Dot Products
    3.3.5 The Cross Product
    3.3.6 Algebraic Identities Involving Cross Products
    3.3.7 The Scalar Triple Product
    3.3.8 Algebraic Identities Involving Scalar Triple Products
    3.4 Barycentric Coordinates
    3.5 Lines, Rays, and Segments
    3.6 Planes and Halfspaces
    3.7 Polygons
    3.7.1 Testing Polygonal Convexity
    3.8 Polyhedra
    3.8.1 Testing Polyhedral Convexity
    3.9 Computing Convex Hulls
    3.9.1 Andrew's Algorithm
    3.9.2 The Quickhull Algorithm
    3.10 Voronoi Regions
    3.11 Minkowski Sum and Difference
    3.12 Summary

    4 Bounding Volumes
    4.1 Desired BV Characteristics
    4.2 Axis-Aligned Bounding Boxes (AABBs)
    4.2.1 AABB-AABB Intersection
    4.2.2 Computing and Updating AABBs
    4.2.3 AABB from the Object Bounding Sphere
    4.2.4 AABB Reconstructed from Original Point Set
    4.2.5 AABB from Hill-Climbing Vertices of the Object Representation
    4.2.6 AABB Recomputed from Rotated AABB
    4.3 Spheres
    4.3.1 Sphere-Sphere Intersection
    4.3.2 Computing a Bounding Sphere
    4.3.3 Bounding Sphere from Direction of Maximum Spread
    4.3.4 Bounding Sphere Through Iterative Refinement
    4.3.5 The Minimum Bounding Sphere
    4.4 Oriented Bounding Boxes (OBBs)
    4.4.1 OBB-OBB Intersection
    4.4.2 Making the Separating-Axis Test Robust
    4.4.3 Computing a Tight OBB
    4.4.4 Optimizing PCA-Based OBBs
    4.4.5 Brute-Force OBB Fitting
    4.5 Sphere-Swept Volumes
    4.5.1 Sphere-Swept Volume Intersection
    4.5.2 Computing Sphere-Swept Bounding Volumes
    4.6 Halfspace Intersection Volumes
    4.6.1 Kay-Kajiya Slab-Based Volumes
    4.6.2 Discrete-Orientation Polytopes (k-DOPs)
    4.6.3 k-DOP-k-DOP Overlap Test
    4.6.4 Computing and Realigning k-DOPs
    4.6.5 Approximate Convex Hull Intersection Tests
    4.7 Other Bounding Volumes
    4.8 Summary

    5 Basic Primitive Tests
    5.1 Closest Point Computations
    5.1.1 Closest Point on Plane to Point
    5.1.2 Closest Point on Line Segment to Point
    5.1.2.1 Distance of Point to Segment
    5.1.3 Closest Point on AABB to Point
    5.1.3.1 Distance of Point to AABB
    5.1.4 Closest Point on OBB to Point
    5.1.4.1 Distance of Point to OBB
    5.1.4.2 Closest Point on 3D Rectangle to Point
    5.1.5 Closest Point on Triangle to Point
    5.1.6 Closest Point on Tetrahedron to Point
    5.1.7 Closest Point on Convex Polyhedron to Point
    5.1.8 Closest Points of Two Lines
    5.1.9 Closest Points of Two Line Segments
    5.1.9.1 2D Segment Intersection
    5.1.10 Closest Points of a Line Segment and a Triangle
    5.1.11 Closest Points of Two Triangles
    5.2 Testing primitives
    5.2.1 Separating Axis Test
    5.2.1.1 Robustness of the Separating Axis Test
    5.2.2 Testing Sphere against Plane
    5.2.3 Testing Box against Plane
    5.2.4 Testing Cone against Plane
    5.2.5 Testing Sphere against AABB
    5.2.6 Testing Sphere against OBB
    5.2.7 Testing Sphere against Triangle
    5.2.8 Testing Sphere against Polygon
    5.2.9 Testing AABB against Triangle
    5.2.10 Testing Triangle against Triangle
    5.3 Intersecting Lines, Rays, and (Directed) Segments
    5.3.1 Intersecting Segment against Plane
    5.3.2 Intersecting Ray or Segment against Sphere
    5.3.3 Intersecting Ray or Segment against Box
    5.3.4 Intersecting Line against Triangle
    5.3.5 Intersecting Line against Quadrilateral
    5.3.6 Intersecting Ray or Segment against Triangle
    5.3.7 Intersecting Ray or Segment against Cylinder
    5.3.8 Intersecting Ray or Segment against Convex Polyhedron
    5.4 Additional Tests
    5.4.1 Testing Point in Polygon
    5.4.2 Testing Point in Triangle
    5.4.3 Testing Point in Polyhedron
    5.4.4 Intersection of Two Planes
    5.4.5 Intersection of Three Planes
    5.5 Dynamic Intersection Tests
    5.5.1 Interval Halving for Intersecting Moving Objects
    5.5.2 Separating Axis Test for Moving Convex Objects
    5.5.3 Intersecting Moving Sphere against Plane
    5.5.4 Intersecting Moving AABB against Plane
    5.5.5 Intersecting Moving Sphere against Sphere
    5.5.6 Intersecting Moving Sphere against Triangle (and Polygon)
    5.5.7 Intersecting Moving Sphere against AABB
    5.5.8 Intersecting Moving AABB against AABB
    5.6 Summary

    6 Bounding Volume Hierarchies
    6.1 Hierarchy Design Issues
    6.1.1 Desired BVH Characteristics
    6.1.2 Cost Functions
    6.1.3 Tree Degree
    6.2 Building Strategies for Hierarchy Construction
    6.2.1 Top-Down Construction
    6.2.1.1 Partitioning Strategies
    6.2.1.2 Choice of Partitioning Axis
    6.2.1.3 Choice of Split Point
    6.2.2 Bottom-Up Construction
    6.2.2.1 Improved Bottom-Up Construction
    6.2.2.2 Other Bottom-Up Construction Strategies
    6.2.2.3 Bottom-Up N-Ary Clustering Trees
    6.2.3 Incremental (Insertion) Construction
    6.2.3.1 The Goldsmith-Salmon Incremental Construction Method
    6.3 Hierarchy Traversal
    6.3.1 Descent Rules
    6.3.2 Generic Informed Depth-First Traversal
    6.3.3 Simultaneous Depth-First Traversal
    6.3.4 Optimized Leaf-Direct Depth-First Traversal
    6.4 Example Bounding Volume Hierarchies
    6.4.1 OBB-Trees
    6.4.2 AABB-Trees and BoxTrees
    6.4.3 Sphere-Tree through Octree Subdivision
    6.4.4 Sphere-Tree from Sphere-Covered Surfaces
    6.4.5 Generate-and-Prune Sphere Covering
    6.4.6 k-DOP Trees
    6.5 Merging Bounding Volumes
    6.5.1 Merging Two AABBs
    6.5.2 Merging Two Spheres
    6.5.3 Merging Two OBBs
    6.5.4 Merging Two k-DOPs
    6.6 Efficient Tree Representation and Traversal
    6.6.1 Array Representation
    6.6.2 Preorder Traversal Order
    6.6.3 Offsets Instead of Pointers
    6.6.4 Cache-Friendlier Structures (Non-Binary Trees)
    6.6.5 Tree Node and Primitive Ordering
    6.6.6 On Recursion
    6.6.7 Grouping Queries
    6.7 Improved Queries through Caching
    6.7.1 Surface Caching: Caching Intersecting Primitives
    6.7.2 Front Tracking
    6.8 Summary

    7 Spatial Partitioning
    7.1 Uniform Grids
    7.1.1 Cell Size Issues
    7.1.2 Grids as Arrays of Linked Lists
    7.1.3 Hashed Storage and Infinite Grids
    7.1.4 Storing Static Data
    7.1.5 Implicit Grids
    7.1.6 Uniform Grid Object-Object Test
    7.1.6.1 One Test at a Time
    7.1.6.2 All Tests at a Time
    7.1.7 Additional Grid Considerations
    7.2 Hierarchical Grids
    7.2.1 Basic Hgrid Implementation
    7.2.2 Alternative Hierarchical Grid Representations
    7.2.3 Other Hierarchical Grids
    7.3 Trees
    7.3.1 Octrees (and Quadtrees)
    7.3.2 Octree Object Assignment
    7.3.3 Locational Codes and Finding the Octant for a Point
    7.3.4 Linear Octrees (Hash-Based)
    7.3.5 Computing the Morton Key
    7.3.6 Loose Octrees
    7.3.7 k-d Trees
    7.3.8 Hybrid Schemes
    7.4 Ray and Directed Line Segment Traversals
    7.4.1 k-d Tree Intersection Test
    7.4.2 Uniform Grid Intersection Test
    7.5 Sort and Sweep Methods
    7.5.1 Sorted Linked List Implementation
    7.5.2 Array-Based Sorting
    7.6 Cells and Portals
    7.7 Avoiding Retesting
    7.7.1 Bit Flags
    7.7.2 Time Stamping
    7.7.3 Amortized Time Stamp Clearing
    7.8 Summary

    8 BSP Tree Hierarchies
    8.1 BSP Trees
    8.2 Types of BSP Trees
    8.2.1 Node-Storing BSP Trees
    8.2.2 Leaf-Storing BSP Trees
    8.2.3 Solid-Leaf BSP Trees
    8.3 Building the BSP Tree
    8.3.1 Selecting Dividing Planes
    8.3.2 Evaluating Dividing Planes
    8.3.3 Classifying Polygons with Respect to a Plane
    8.3.4 Splitting Polygons against a Plane
    8.3.5 More on Polygon splitting Robustness
    8.3.6 Tuning BSP Tree Performance
    8.4 using the BSP Tree
    8.4.1 Testing Point against a Solid-Leaf BSP Tree
    8.4.2 Intersecting Ray against a Solid-Leaf BSP Tree
    8.4.3 Polytope Queries on Solid-Leaf BSP Trees
    8.5 Summary

    9 Convexity-Based Methods
    9.1 Boundary-Based Collision Detection
    9.2 Closest Features Algorithms
    9.2.1 The V-Clip Algorithm
    9.3 Hierarchical Polyhedron Representations
    9.3.1 The Dobkin-Kirkpatrick Hierarchy
    9.4 Linear and Quadratic Programming
    9.4.1 Linear Programming
    9.4.1.1 Fourier-Motzkin Elimination
    9.4.1.2 Seidel's Algorithm
    9.4.2 Quadratic Programming
    9.5 The Gilbert-Johnson-Keerthi Algorithm
    9.5.1 The Gilbert-Johnson-Keerthi Algorithm
    9.5.2 Finding the Point of Minimum Norm in a Simplex
    9.5.3 GJK, Closest Points and Contact Manifolds
    9.5.4 Hill-Climbing for Extreme Vertices
    9.5.5 Exploiting Coherence by Vertex Caching
    9.5.6 Rotated Objects Optimization
    9.5.7 GJK for Moving Objects
    9.6 The Chung-Wang Separating Vector Algorithm
    9.7 Summary

    10 GPU-Assisted Collision Detection
    10.1 Interfacing with the GPU
    10.1.1 Buffer Readbacks
    10.1.2 Occlusion Queries
    10.2 Testing Convex Objects
    10.3 Testing Concave Objects
    10.4 GPU-Based Collision Filtering
    10.5 Summary

    11 Numerical Robustness
    11.1 Robustness Problem Types
    11.2 Representing Real Numbers
    11.2.1 The IEEE-754 Floating-Point Formats
    11.2.2 Infinity Arithmetic
    11.2.3 Floating-Point Error Sources
    11.3 Robust Floating-Point Usage
    11.3.1 Tolerances Comparisons for Floating-Point Values
    11.3.2 Robustness through Thick Planes
    11.3.3 Robustness through Sharing of Calculations
    11.3.4 Robustness of Fat Objects
    11.4 Interval Arithmetic
    11.4.1 Interval Arithmetic Examples
    11.4.2 Interval Arithmetic in Collision Detection
    11.5 Exact and Semi-Exact Computation
    11.5.1 Exact Arithmetic using Integers
    11.5.2 On Integer Division
    11.5.3 Segment Intersection using Integer Arithmetic
    11.6 Further Suggestions for Improving Robustness
    11.7 Summary

    12 Geometrical Robustness
    12.1 Vertex Welding
    12.2 Computing Adjacency Information
    12.2.1 Computing a Vertex-to-Face Table
    12.2.2 Computing an Edge-to-Face Table
    12.2.3 Testing Connectedness
    12.3 Holes, Cracks, Gaps, and T-Junctions
    12.4 Merging Coplanar Faces
    12.4.1 Testing Coplanarity of Two Polygons
    12.4.2 Testing Polygon Planarity
    12.5 Triangulation and Convex Partitioning
    12.5.1 Triangulation by Ear Cutting
    12.5.1.1 Triangulating Polygons with Holes
    12.5.2 Convex Decomposition of Polygons
    12.5.3 Convex Decomposition of Polyhedra
    12.5.4 Dealing with "Nondecomposable" Concave Geometry
    12.6 Consistency Testing using Euler's Formula
    12.7 Summary

    13 Optimization
    13.1 CPU Caches
    13.2 Instruction Cache Optimizations
    13.3 Data Cache Optimizations
    13.3.1 Structure Optimizations
    13.3.2 Quantized and Compressed Vertex Data
    13.3.3 Prefetching and Preloading
    13.4 Cache-Aware Data Structures and Algorithms
    13.4.1 A Compact Static k-d Tree
    13.4.2 A Compact AABB Tree
    13.4.3 Cache-Obliviousness
    13.5 Software Caching
    13.5.1 Cached Linearization Example
    13.5.2 Amortized Predictive Linearization Caching
    13.6 Aliasing
    13.6.1 Type-Based Alias Analysis
    13.6.2 Restricted Pointers
    13.6.3 Avoiding Aliasing
    13.7 Parallelism through SIMD Optimizations
    13.7.1 4 Spheres versus 4 Spheres SIMD Test
    13.7.2 4 Spheres versus 4 AABBs SIMD Test
    13.7.3 4 AABBs versus 4 AABBs SIMD Test
    13.8 Branching
    13.9 Summary

    References
    Index

    Biography

    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.

    "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