book

Real-Time Collision Detection

Name: Real-Time Collision Detection
Author: Christer Ericson
ISBN: 9781000750553

by Christer Ericson

December 2004

Intermediate to advanced

632 pages

17h 25m

English

CRC Press

Read now

Unlock full access

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication Page
About the Author
Table of Contents
List of Figures
Preface

Chapter 1 Introduction
1.1 Content Overview1.1.1 Chapter 2: Collision Detection Design Issues1.1.2 Chapter 3: A Math and Geometry Primer1.1.3 Chapter 4: Bounding Volumes1.1.4 Chapter 5: Basic Primitive Tests1.1.5 Chapter 6: Bounding Volume Hierarchies1.1.6 Chapter 7: Spatial Partitioning1.1.7 Chapter 8: BSP Tree Hierarchies1.1.8 Chapter 9: Convexity-based Methods1.1.9 Chapter 10: GPU-assisted Collision Detection1.1.10 Chapter 11: Numerical Robustness1.1.11 Chapter 12: Geometrical Robustness1.1.12 Chapter 13: Optimization1.2 About the Code
Chapter 2 Collision Detection Design Issues
2.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 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
Chapter 3 A Math and Geometry Primer
3.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 2 × 2 and 3 × 3 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 Summary
Chapter 4 Bounding Volumes
4.1 Desirable 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
Chapter 5 Basic Primitive Tests
5.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 Summary
Chapter 6 Bounding Volume Hierarchies
6.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 Sample 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 (Nonbinary 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
Chapter 7 Spatial Partitioning
7.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 Summary
Chapter 8 BSP Tree Hierarchies
8.1 BSP Trees8.2 Types of BSP Trees8.2.1 Node-storing BSP Trees8.2.2 Leaf-storing BSPTrees8.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 a Point Against a Solid-leaf BSP Tree8.4.2 Intersecting a Ray Against a Solid-leaf BSP Tree8.4.3 Polytope Queries on Solid-leaf BSP Trees8.5 Summary
Chapter 9 Convexity-based Methods
9.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 Summary
Chapter 10 GPU-assisted Collision Detection
10.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
Chapter 11 Numerical Robustness
11.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 Tolerance 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 Integer Division11.5.3 Segment Intersection Using Integer Arithmetic11.6 Further Suggestions for Improving Robustness11.7 Summary
Chapter 12 Geometrical Robustness
12.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 Co-planar Faces12.4.1 Testing Co-planarity 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 Summary
Chapter 13 Optimization
13.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 Four Spheres Versus Four Spheres SIMD Test13.7.2 Four Spheres Versus Four AABBs SIMD Test13.7.3 Four AABBs Versus Four AABBs SIMD Test13.8 Branching13.9 Summary
References
Index
About the CD ROM

Content preview from Real-Time Collision Detection

Wrapping objects in bounding volumes and performing tests on the bounding volumes before testing the object geometry itself can result in significant performance improvements. However, although the tests themselves have been simplified, the same number of pairwise tests are still being performed. The asymptotic time complexity remains the same and the use of bounding volumes improves the situation by a constant factor. By arranging the bounding volumes into a tree hierarchy called a bounding volume hierarchy (BVH), the time complexity can be reduced to logarithmic in the number of tests performed.

The original set of bounding volumes forms the leaf nodes of the tree that is this bounding volume hierarchy. ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781558607323

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Real-Time Collision Detection

by Christer Ericson

Chapter 6

Bounding Volume Hierarchies

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.