1st Edition
Collision Detection in Interactive 3D Environments
By Gino van den Bergen
Copyright 2003
308 Pages
by
CRC Press
277 Pages
by
CRC Press
Also available as eBook on:
The heart of any system that simulates the physical interaction between objects is collision detection-the ability to detect when two objects have come into contact. This system is also one of the most difficult aspects of a physical simulation to implement correctly, and invariably it is the main consumer of CPU cycles. Practitioners, new to the field or otherwise, quickly discover that the... Read more
1 Introduction
1.1 Problem Domain
1.2 Historical Background
1.3 Organization
2 Concepts
2.1 Geometry
2.1.1 Notational Conventions
2.1.2 Vector Spaces
2.1.3 Affine Spaces
2.1.4 Euclidean Spaces
2.1.5 Affine Transformations
2.1.6 Three-dimensional Space
2.2 Objects
2.2.1 Polytopes
2.2.2 Polygons
2.2.3 Quadrics
2.2.4 Minkowski Addition
2.2.5 Complex Shapes and Scenes
2.3 Animation
2.4 Time
2.5 Response
2.6 Performance
2.6.1 Frame Coherence
2.6.2 Geometric Coherence
2.6.3 Average Time
2.7 Robustness
2.7.1 Floating-Point Numbers
2.7.2 Stability
2.7.3 Coping with Numerical Problems
3 Basic Primitives
3.1 Spheres
3.1.1 Sphere-Sphere Test
3.1.2 Ray-Sphere Test
3.1.3 Line-Segment-Sphere Test
3.2 Axis-Aligned Boxes
3.2.1 Ray-Box Test
3.2.2 Sphere-Box Test
3.3 Separating Axes
3.3.1 Line-Segment-Box Test
3.3.2 Triangle-Box Test
3.3.3 Box-Box Test
3.4 Polygons
3.4.1 Ray-Triangle Test
3.4.2 Line Segment-Triangle Test
3.4.3 Ray-Polygon Test
3.4.4 Triangle-Triangle Test
3.4.5 Polygon-Polygon Test
3.4.6 Triangle-Sphere Test
3.4.7 Polygon-Volume Tests
4 Convex Objects
4.1 Proximity Queries
4.2 Overview of Algorithms for Polytopes
4.2.1 Finding a Common Point
4.2.2 Finding a Separating Plane
4.2.3 Distance and Penetration Depth Computation
4.3 The Gilbert-Johnson-Keerthi Algorithm
4.3.1 Overview
4.3.2 Convergence and Termination
4.3.3 Johnson's Distance Algorithm
4.3.4 Support Mappings
4.3.5 Implementing the GJK Algorithm
4.3.6 Numerical Aspects of the GJK Algorithm
4.3.7 Testing for Intersections
4.3.8 Penetration Depth
5 Spatial Data Structures
5.1 Nonconvex Polyhedra
5.1.1 Convex Decomposition
5.1.2 Polyhedral Surfaces
5.1.3 Point in Nonconvex Polyhedron
5.2 Space Partitioning
5.2.1 Voxel Grids
5.2.2 Octrees and k-d Trees
5.2.3 Binary Space Partitioning Trees
5.2.4 Discussion
5.3 Model Partitioning
5.3.1 Bounding Volumes
5.3.2 Bounding-Volume Hierarchies
5.3.3 AABB Trees versus OBB Trees
5.3.4 AABB Trees and Deformable Models
5.4 Broad Phase
5.4.1 Sweep and Prune
5.4.2 Implementing the Sweep-and-Prune Algorithm
5.4.3 Ray Casting and AABBs
6 Design of SOLID
6.1 Requirements
6.2 Overview of SOLID
6.3 Design Decisions
6.3.1 Shape Representation
6.3.2 Motion Specification
6.3.3 Response Handling
6.3.4 Algorithms
6.4 Evaluation
6.5 Implementation Notes
6.5.1 Generic Data Types and Algorithms
6.5.2 Fundamental 3D Classes
7 Conclusion
7.1 State of the Art
7.2 Future Work
Bibliography
Index
About the CD-ROM
Trademarks
1.1 Problem Domain
1.2 Historical Background
1.3 Organization
2 Concepts
2.1 Geometry
2.1.1 Notational Conventions
2.1.2 Vector Spaces
2.1.3 Affine Spaces
2.1.4 Euclidean Spaces
2.1.5 Affine Transformations
2.1.6 Three-dimensional Space
2.2 Objects
2.2.1 Polytopes
2.2.2 Polygons
2.2.3 Quadrics
2.2.4 Minkowski Addition
2.2.5 Complex Shapes and Scenes
2.3 Animation
2.4 Time
2.5 Response
2.6 Performance
2.6.1 Frame Coherence
2.6.2 Geometric Coherence
2.6.3 Average Time
2.7 Robustness
2.7.1 Floating-Point Numbers
2.7.2 Stability
2.7.3 Coping with Numerical Problems
3 Basic Primitives
3.1 Spheres
3.1.1 Sphere-Sphere Test
3.1.2 Ray-Sphere Test
3.1.3 Line-Segment-Sphere Test
3.2 Axis-Aligned Boxes
3.2.1 Ray-Box Test
3.2.2 Sphere-Box Test
3.3 Separating Axes
3.3.1 Line-Segment-Box Test
3.3.2 Triangle-Box Test
3.3.3 Box-Box Test
3.4 Polygons
3.4.1 Ray-Triangle Test
3.4.2 Line Segment-Triangle Test
3.4.3 Ray-Polygon Test
3.4.4 Triangle-Triangle Test
3.4.5 Polygon-Polygon Test
3.4.6 Triangle-Sphere Test
3.4.7 Polygon-Volume Tests
4 Convex Objects
4.1 Proximity Queries
4.2 Overview of Algorithms for Polytopes
4.2.1 Finding a Common Point
4.2.2 Finding a Separating Plane
4.2.3 Distance and Penetration Depth Computation
4.3 The Gilbert-Johnson-Keerthi Algorithm
4.3.1 Overview
4.3.2 Convergence and Termination
4.3.3 Johnson's Distance Algorithm
4.3.4 Support Mappings
4.3.5 Implementing the GJK Algorithm
4.3.6 Numerical Aspects of the GJK Algorithm
4.3.7 Testing for Intersections
4.3.8 Penetration Depth
5 Spatial Data Structures
5.1 Nonconvex Polyhedra
5.1.1 Convex Decomposition
5.1.2 Polyhedral Surfaces
5.1.3 Point in Nonconvex Polyhedron
5.2 Space Partitioning
5.2.1 Voxel Grids
5.2.2 Octrees and k-d Trees
5.2.3 Binary Space Partitioning Trees
5.2.4 Discussion
5.3 Model Partitioning
5.3.1 Bounding Volumes
5.3.2 Bounding-Volume Hierarchies
5.3.3 AABB Trees versus OBB Trees
5.3.4 AABB Trees and Deformable Models
5.4 Broad Phase
5.4.1 Sweep and Prune
5.4.2 Implementing the Sweep-and-Prune Algorithm
5.4.3 Ray Casting and AABBs
6 Design of SOLID
6.1 Requirements
6.2 Overview of SOLID
6.3 Design Decisions
6.3.1 Shape Representation
6.3.2 Motion Specification
6.3.3 Response Handling
6.3.4 Algorithms
6.4 Evaluation
6.5 Implementation Notes
6.5.1 Generic Data Types and Algorithms
6.5.2 Fundamental 3D Classes
7 Conclusion
7.1 State of the Art
7.2 Future Work
Bibliography
Index
About the CD-ROM
Trademarks
Biography
Gino van den Bergen is a game developer working for the Playlogic Game Factory, Breda, The Netherlands. He is the creator of SOLID and holds a Ph.D. in computing science from Eindhoven University of Technology. Gino implemented collision detection and physics in NaN Technologies' Blender, a creation suite for interactive 3D content.
"Having read this book from cover to cover, I can summarize my opinion in two words from a mathematician's lexicon: elegant and beautiful. There is very little to criticize in this exquisite work."
-Ian Ashdown, byHeart Consultants, Inc.
"Building a real-time collision detection system is by no means a trivial task. A firm understanding is required of the geometry and mathematics for intersection testing, especially when the objects are in motion. The skilled use of convexity is essential for distance calculations. The system must be designed carefully to support high-performance physical simulations. In particular, spatial partitioning and tight-fitting bounding volumes must play a role in minimizing the computational requirements of the system. The system is sufficiently large that the principles of software engineering apply to its development. Moreover, collision detection is notoriously difficult to implement robustly when using floating-point arithmetic. The challenges of architecting and implementing a collision detection system are formidable!
Collision Detection in Interactive 3D Environments is an elegantly written treatise on this topic. Gino guides you through the basic concepts, provides insightful discussions on how to cope with the problems inherent in floating-point arithmetic, covers the all-important topic of computing distance between convex objects, and presents an informative summary of the spatial data structures that are commonly encountered in practice. And as an artisan of the field, Gino finishes the story with a case study-the design and implementation of his own working collision detection system, SOLID.
This is the first book to provide all the details necessary to build a collision detection system that really works. I hope you will find, as I did, that the amount of material in this book is incredible, making it an extremely valuable resource."
-Dave Eberly, president, Magic Software, Inc., and author of 3D Game Engine Design, co-author with Philip Schneider of Geometric Tools for Computer Graphics, and author of Game Physics.
