Real-Time Collision Detection

1st Edition

Print ISBN: 9781558607323
Imprint: Morgan Kaufmann
Published Date: 22nd December 2004
Page Count: 632


This product is currently not available for sale.


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.

Key Features

Presents algorithms and data structures with wide applications to the fields of game development, virtual reality, physically based simulation, CAD/CAM, architectural and scientific visualization, molecular modeling, engineering simulation, GIS, ray tracing, and more.
Describes tested, real-world methods, liberally illustrated by C & C++ code.
*Reviews necessary concepts from mathematics and computational geometry, and includes extensive references to other sources and research literature.


Professionals or students working in software engineering, game development, simulation, scientific visualization, or virtual reality.

Table of Contents


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 ORIENT2D(A, B, C) ORIENT3D(A, B, C, D) INCIRCLE2D(A, B, C, D) 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 Barycentri


No. of pages:
© Morgan Kaufmann 2005
Morgan Kaufmann
Hardcover ISBN:


"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. Chris