Real-Time Collision Detection

Real-Time Collision Detection

by Christer Ericson
Released December 2004
Publisher(s): CRC Press
ISBN: 9781000750553

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Written by an expert in the game industry, this book is a comprehensive guide to the components of efficient real-time collision detection systems. It 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 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.

Table of contents

  1. Cover
  2. Half Title
  3. Series Page
  4. Title Page
  5. Copyright Page
  6. Dedication Page
  7. About the Author
  8. Table of Contents
  9. List of Figures
  10. Preface
  11. Chapter 1 Introduction
    1. 1.1 Content Overview
      1. 1.1.1 Chapter 2: Collision Detection Design Issues
      2. 1.1.2 Chapter 3: A Math and Geometry Primer
      3. 1.1.3 Chapter 4: Bounding Volumes
      4. 1.1.4 Chapter 5: Basic Primitive Tests
      5. 1.1.5 Chapter 6: Bounding Volume Hierarchies
      6. 1.1.6 Chapter 7: Spatial Partitioning
      7. 1.1.7 Chapter 8: BSP Tree Hierarchies
      8. 1.1.8 Chapter 9: Convexity-based Methods
      9. 1.1.9 Chapter 10: GPU-assisted Collision Detection
      10. 1.1.10 Chapter 11: Numerical Robustness
      11. 1.1.11 Chapter 12: Geometrical Robustness
      12. 1.1.12 Chapter 13: Optimization
    2. 1.2 About the Code
  12. Chapter 2 Collision Detection Design Issues
    1. 2.1 Collision Algorithm Design Factors
    2. 2.2 Application Domain Representation
      1. 2.2.1 Object Representations
      2. 2.2.2 Collision Versus Rendering Geometry
      3. 2.2.3 Collision Algorithm Specialization
    3. 2.3 Types of Queries
    4. 2.4 Environment Simulation Parameters
      1. 2.4.1 Number of Objects
      2. 2.4.2 Sequential Versus Simultaneous Motion
      3. 2.4.3 Discrete Versus Continuous Motion
    5. 2.5 Performance
      1. 2.5.1 Optimization Overview
    6. 2.6 Robustness
    7. 2.7 Ease of Implementation and Use
      1. 2.7.1 Debugging a Collision Detection System
    8. 2.8 Summary
  13. Chapter 3 A Math and Geometry Primer
    1. 3.1 Matrices
      1. 3.1.1 Matrix Arithmetic
      2. 3.1.2 Algebraic Identities Involving Matrices
      3. 3.1.3 Determinants
      4. 3.1.4 Solving Small Systems of Linear Equation Using Cramer’s Rule
      5. 3.1.5 Matrix Inverses for 2 × 2 and 3 × 3 Matrices
      6. 3.1.6 Determinant Predicates
        1. 3.1.6.1 ORIENT2D(A, B, C)
        2. 3.1.6.2 ORIENT3D(A, B, C, D)
        3. 3.1.6.3 INCIRCLE2D(A, B, C, D)
        4. 3.1.6.4 INSPHERE(A, B, C, D, E)
    2. 3.2 Coordinate Systems and Points
    3. 3.3 Vectors
      1. 3.3.1 Vector Arithmetic
      2. 3.3.2 Algebraic Identities Involving Vectors
      3. 3.3.3 The Dot Product
      4. 3.3.4 Algebraic Identities Involving Dot Products
      5. 3.3.5 The Cross Product
      6. 3.3.6 Algebraic Identities Involving Cross Products
      7. 3.3.7 The Scalar Triple Product
      8. 3.3.8 Algebraic Identities Involving Scalar Triple Products
    4. 3.4 Barycentric Coordinates
    5. 3.5 Lines, Rays, and Segments
    6. 3.6 Planes and Halfspaces
    7. 3.7 Polygons
      1. 3.7.1 Testing Polygonal Convexity
    8. 3.8 Polyhedra
      1. 3.8.1 Testing Polyhedral Convexity
    9. 3.9 Computing Convex Hulls
      1. 3.9.1 Andrew’s Algorithm
      2. 3.9.2 The Quickhull Algorithm
    10. 3.10 Voronoi Regions
    11. 3.11 Minkowski Sum and Difference
    12. 3.12 Summary
  14. Chapter 4 Bounding Volumes
    1. 4.1 Desirable BV Characteristics
    2. 4.2 Axis-aligned Bounding Boxes (AABBs)
      1. 4.2.1 AABB-AABB Intersection
      2. 4.2.2 Computing and Updating AABBs
      3. 4.2.3 AABB from the Object Bounding Sphere
      4. 4.2.4 AABB Reconstructed from Original Point Set
      5. 4.2.5 AABB from Hill-climbing Vertices of the Object Representation
      6. 4.2.6 AABB Recomputed from Rotated AABB
    3. 4.3 Spheres
      1. 4.3.1 Sphere-sphere Intersection
      2. 4.3.2 Computing a Bounding Sphere
      3. 4.3.3 Bounding Sphere from Direction of Maximum Spread
      4. 4.3.4 Bounding Sphere Through Iterative Refinement
      5. 4.3.5 The Minimum Bounding Sphere
    4. 4.4 Oriented Bounding Boxes (OBBs)
      1. 4.4.1 OBB-OBB Intersection
      2. 4.4.2 Making the Separating-axis Test Robust
      3. 4.4.3 Computing a Tight OBB
      4. 4.4.4 Optimizing PCA-based OBBs
      5. 4.4.5 Brute-force OBB Fitting
    5. 4.5 Sphere-swept Volumes
      1. 4.5.1 Sphere-swept Volume Intersection
      2. 4.5.2 Computing Sphere-swept Bounding Volumes
    6. 4.6 Halfspace Intersection Volumes
      1. 4.6.1 Kay–Kajiya Slab-based Volumes
      2. 4.6.2 Discrete-orientation Polytopes (k-DOPs)
      3. 4.6.3 k-DOP–k-DOP Overlap Test
      4. 4.6.4 Computing and Realigning k-DOPs
      5. 4.6.5 Approximate Convex Hull Intersection Tests
    7. 4.7 Other Bounding Volumes
    8. 4.8 Summary
  15. Chapter 5 Basic Primitive Tests
    1. 5.1 Closest-point Computations
      1. 5.1.1 Closest Point on Plane to Point
      2. 5.1.2 Closest Point on Line Segment to Point
        1. 5.1.2.1 Distance of Point To Segment
      3. 5.1.3 Closest Point on AABB to Point
        1. 5.1.3.1 Distance of Point to AABB
      4. 5.1.4 Closest Point on OBB to Point
        1. 5.1.4.1 Distance of Point to OBB
        2. 5.1.4.2 Closest Point on 3D Rectangle to Point
      5. 5.1.5 Closest Point on Triangle to Point
      6. 5.1.6 Closest Point on Tetrahedron to Point
      7. 5.1.7 Closest Point on Convex Polyhedron to Point
      8. 5.1.8 Closest Points of Two Lines
      9. 5.1.9 Closest Points of Two Line Segments
        1. 5.1.9.1 2D Segment Intersection
      10. 5.1.10 Closest Points of a Line Segment and a Triangle
      11. 5.1.11 Closest Points of Two Triangles
    2. 5.2 Testing Primitives
      1. 5.2.1 Separating-axis Test
        1. 5.2.1.1 Robustness of the Separating-axis Test
      2. 5.2.2 Testing Sphere Against Plane
      3. 5.2.3 Testing Box Against Plane
      4. 5.2.4 Testing Cone Against Plane
      5. 5.2.5 Testing Sphere Against AABB
      6. 5.2.6 Testing Sphere Against OBB
      7. 5.2.7 Testing Sphere Against Triangle
      8. 5.2.8 Testing Sphere Against Polygon
      9. 5.2.9 Testing AABB Against Triangle
      10. 5.2.10 Testing Triangle Against Triangle
    3. 5.3 Intersecting Lines, Rays, and (Directed) Segments
      1. 5.3.1 Intersecting Segment Against Plane
      2. 5.3.2 Intersecting Ray or Segment Against Sphere
      3. 5.3.3 Intersecting Ray or Segment Against Box
      4. 5.3.4 Intersecting Line Against Triangle
      5. 5.3.5 Intersecting Line Against Quadrilateral
      6. 5.3.6 Intersecting Ray or Segment Against Triangle
      7. 5.3.7 Intersecting Ray or Segment Against Cylinder
      8. 5.3.8 Intersecting Ray or Segment Against Convex Polyhedron
    4. 5.4 Additional Tests
      1. 5.4.1 Testing Point in Polygon
      2. 5.4.2 Testing Point in Triangle
      3. 5.4.3 Testing Point in Polyhedron
      4. 5.4.4 Intersection of Two Planes
      5. 5.4.5 Intersection of Three Planes
    5. 5.5 Dynamic Intersection Tests
      1. 5.5.1 Interval Halving for Intersecting Moving Objects
      2. 5.5.2 Separating Axis Test for Moving Convex Objects
      3. 5.5.3 Intersecting Moving Sphere Against Plane
      4. 5.5.4 Intersecting Moving AABB Against Plane
      5. 5.5.5 Intersecting Moving Sphere Against Sphere
      6. 5.5.6 Intersecting Moving Sphere Against Triangle (and Polygon)
      7. 5.5.7 Intersecting Moving Sphere Against AABB
      8. 5.5.8 Intersecting Moving AABB Against AABB
    6. 5.6 Summary
  16. Chapter 6 Bounding Volume Hierarchies
    1. 6.1 Hierarchy Design Issues
      1. 6.1.1 Desired BVH Characteristics
      2. 6.1.2 Cost Functions
      3. 6.1.3 Tree Degree
    2. 6.2 Building Strategies for Hierarchy Construction
      1. 6.2.1 Top-down Construction
        1. 6.2.1.1 Partitioning Strategies
        2. 6.2.1.2 Choice of Partitioning Axis
        3. 6.2.1.3 Choice of Split Point
      2. 6.2.2 Bottom-up Construction
        1. 6.2.2.1 Improved Bottom-up Construction
        2. 6.2.2.2 Other Bottom-up Construction Strategies
        3. 6.2.2.3 Bottom-up n-ary Clustering Trees
      3. 6.2.3 Incremental (Insertion) Construction
        1. 6.2.3.1 The Goldsmith–Salmon Incremental Construction Method
    3. 6.3 Hierarchy Traversal
      1. 6.3.1 Descent Rules
      2. 6.3.2 Generic Informed Depth-first Traversal
      3. 6.3.3 Simultaneous Depth-first Traversal
      4. 6.3.4 Optimized Leaf-direct Depth-first Traversal
    4. 6.4 Sample Bounding Volume Hierarchies
      1. 6.4.1 OBB Trees
      2. 6.4.2 AABB Trees and BoxTrees
      3. 6.4.3 Sphere Tree Through Octree Subdivision
      4. 6.4.4 Sphere Tree from Sphere-covered Surfaces
      5. 6.4.5 Generate-and-Prune Sphere Covering
      6. 6.4.6 k-dop Trees
    5. 6.5 Merging Bounding Volumes
      1. 6.5.1 Merging Two AABBs
      2. 6.5.2 Merging Two Spheres
      3. 6.5.3 Merging Two OBBs
      4. 6.5.4 Merging Two k-DOPs
    6. 6.6 Efficient Tree Representation and Traversal
      1. 6.6.1 Array Representation
      2. 6.6.2 Preorder Traversal Order
      3. 6.6.3 Offsets Instead of Pointers
      4. 6.6.4 Cache-friendlier Structures (Nonbinary Trees)
      5. 6.6.5 Tree Node and Primitive Ordering
      6. 6.6.6 On Recursion
      7. 6.6.7 Grouping Queries
    7. 6.7 Improved Queries Through Caching
      1. 6.7.1 Surface Caching: Caching Intersecting Primitives
      2. 6.7.2 Front Tracking
    8. 6.8 Summary
  17. Chapter 7 Spatial Partitioning
    1. 7.1 Uniform Grids
      1. 7.1.1 Cell Size Issues
      2. 7.1.2 Grids as Arrays of Linked Lists
      3. 7.1.3 Hashed Storage and Infinite Grids
      4. 7.1.4 Storing Static Data
      5. 7.1.5 Implicit Grids
      6. 7.1.6 Uniform Grid Object-Object Test
        1. 7.1.6.1 One Test at a Time
        2. 7.1.6.2 All Tests at a Time
      7. 7.1.7 Additional Grid Considerations
    2. 7.2 Hierarchical Grids
      1. 7.2.1 Basic Hgrid Implementation
      2. 7.2.2 Alternative Hierarchical Grid Representations
      3. 7.2.3 Other Hierarchical Grids
    3. 7.3 Trees
      1. 7.3.1 Octrees (and Quadtrees)
      2. 7.3.2 Octree Object Assignment
      3. 7.3.3 Locational Codes and Finding the Octant for a Point
      4. 7.3.4 Linear Octrees (Hash-based)
      5. 7.3.5 Computing the Morton Key
      6. 7.3.6 Loose Octrees
      7. 7.3.7 k-d Trees
      8. 7.3.8 Hybrid Schemes
    4. 7.4 Ray and Directed Line Segment Traversals
      1. 7.4.1 k-d Tree Intersection Test
      2. 7.4.2 Uniform Grid Intersection Test
    5. 7.5 Sort and Sweep Methods
      1. 7.5.1 Sorted Linked-list Implementation
      2. 7.5.2 Array-based Sorting
    6. 7.6 Cells and Portals
    7. 7.7 Avoiding Retesting
      1. 7.7.1 Bit Flags
      2. 7.7.2 Time Stamping
      3. 7.7.3 Amortized Time Stamp Clearing
    8. 7.8 Summary
  18. Chapter 8 BSP Tree Hierarchies
    1. 8.1 BSP Trees
    2. 8.2 Types of BSP Trees
      1. 8.2.1 Node-storing BSP Trees
      2. 8.2.2 Leaf-storing BSPTrees
      3. 8.2.3 Solid-leaf BSP Trees
    3. 8.3 Building the BSP Tree
      1. 8.3.1 Selecting Dividing Planes
      2. 8.3.2 Evaluating Dividing Planes
      3. 8.3.3 Classifying Polygons with Respect to a Plane
      4. 8.3.4 Splitting Polygons Against a Plane
      5. 8.3.5 More on Polygon Splitting Robustness
      6. 8.3.6 Tuning BSP Tree Performance
    4. 8.4 Using the BSP Tree
      1. 8.4.1 Testing a Point Against a Solid-leaf BSP Tree
      2. 8.4.2 Intersecting a Ray Against a Solid-leaf BSP Tree
      3. 8.4.3 Polytope Queries on Solid-leaf BSP Trees
    5. 8.5 Summary
  19. Chapter 9 Convexity-based Methods
    1. 9.1 Boundary-based Collision Detection
    2. 9.2 Closest-features Algorithms
      1. 9.2.1 The V-Clip Algorithm
    3. 9.3 Hierarchical Polyhedron Representations
      1. 9.3.1 The Dobkin–Kirkpatrick Hierarchy
    4. 9.4 Linear and Quadratic Programming
      1. 9.4.1 Linear Programming
        1. 9.4.1.1 Fourier–Motzkin Elimination
        2. 9.4.1.2 Seidel’s Algorithm
      2. 9.4.2 Quadratic Programming
    5. 9.5 The Gilbert–Johnson–Keerthi Algorithm
      1. 9.5.1 The Gilbert–Johnson–Keerthi Algorithm
      2. 9.5.2 Finding the Point of Minimum Norm in a Simplex
      3. 9.5.3 GJK, Closest Points and Contact Manifolds
      4. 9.5.4 Hill Climbing for Extreme Vertices
      5. 9.5.5 Exploiting Coherence by Vertex Caching
      6. 9.5.6 Rotated Objects Optimization
      7. 9.5.7 GJK for Moving Objects
    6. 9.6 The Chung–Wang Separating-vector Algorithm
    7. 9.7 Summary
  20. Chapter 10 GPU-assisted Collision Detection
    1. 10.1 Interfacing with the GPU
      1. 10.1.1 Buffer Readbacks
      2. 10.1.2 Occlusion Queries
    2. 10.2 Testing Convex Objects
    3. 10.3 Testing Concave Objects
    4. 10.4 GPU-based Collision Filtering
    5. 10.5 Summary
  21. Chapter 11 Numerical Robustness
    1. 11.1 Robustness Problem Types
    2. 11.2 Representing Real Numbers
      1. 11.2.1 The IEEE-754 Floating-point Formats
      2. 11.2.2 Infinity Arithmetic
      3. 11.2.3 Floating-point Error Sources
    3. 11.3 Robust Floating-point Usage
      1. 11.3.1 Tolerance Comparisons for Floating-point Values
      2. 11.3.2 Robustness Through Thick Planes
      3. 11.3.3 Robustness Through Sharing of Calculations
      4. 11.3.4 Robustness of Fat Objects
    4. 11.4 Interval Arithmetic
      1. 11.4.1 Interval Arithmetic Examples
      2. 11.4.2 Interval Arithmetic in Collision Detection
    5. 11.5 Exact and Semi-exact Computation
      1. 11.5.1 Exact Arithmetic Using Integers
      2. 11.5.2 Integer Division
      3. 11.5.3 Segment Intersection Using Integer Arithmetic
    6. 11.6 Further Suggestions for Improving Robustness
    7. 11.7 Summary
  22. Chapter 12 Geometrical Robustness
    1. 12.1 Vertex Welding
    2. 12.2 Computing Adjacency Information
      1. 12.2.1 Computing a Vertex-to-Face Table
      2. 12.2.2 Computing an Edge-to-Face Table
      3. 12.2.3 Testing Connectedness
    3. 12.3 Holes, Cracks, Gaps and T-Junctions
    4. 12.4 Merging Co-planar Faces
      1. 12.4.1 Testing Co-planarity of Two Polygons
      2. 12.4.2 Testing Polygon Planarity
    5. 12.5 Triangulation and Convex Partitioning
      1. 12.5.1 Triangulation by Ear Cutting
        1. 12.5.1.1 Triangulating Polygons with Holes
      2. 12.5.2 Convex Decomposition of Polygons
      3. 12.5.3 Convex Decomposition of Polyhedra
      4. 12.5.4 Dealing with “Nondecomposable” Concave Geometry
    6. 12.6 Consistency Testing Using Euler’s Formula
    7. 12.7 Summary
  23. Chapter 13 Optimization
    1. 13.1 CPU Caches
    2. 13.2 Instruction Cache Optimizations
    3. 13.3 Data Cache Optimizations
      1. 13.3.1 Structure Optimizations
      2. 13.3.2 Quantized and Compressed Vertex Data
      3. 13.3.3 Prefetching and Preloading
    4. 13.4 Cache-aware Data Structures and Algorithms
      1. 13.4.1 A Compact Static k-d Tree
      2. 13.4.2 A Compact AABB Tree
      3. 13.4.3 Cache Obliviousness
    5. 13.5 Software Caching
      1. 13.5.1 Cached Linearization Example
      2. 13.5.2 Amortized Predictive Linearization Caching
    6. 13.6 Aliasing
      1. 13.6.1 Type-based Alias Analysis
      2. 13.6.2 Restricted Pointers
      3. 13.6.3 Avoiding Aliasing
    7. 13.7 Parallelism Through SIMD Optimizations
      1. 13.7.1 Four Spheres Versus Four Spheres SIMD Test
      2. 13.7.2 Four Spheres Versus Four AABBs SIMD Test
      3. 13.7.3 Four AABBs Versus Four AABBs SIMD Test
    8. 13.8 Branching
    9. 13.9 Summary
  24. References
  25. Index
  26. About the CD ROM

Product information

  • Title: Real-Time Collision Detection
  • Author(s): Christer Ericson
  • Release date: December 2004
  • Publisher(s): CRC Press
  • ISBN: 9781000750553