Collision detection is an important part of many computer games. Many game logic systems depend on fast and accurate execution of the collision detection system in order to determine game state. This book is a valuable resource for any engineer implementing or optimizing a collision detection system for computer games.

Collision detection is a broad topic, covering collisions between primitives, such as triangles and points; collisions between bounding volumes; and collisions between hierarchies of bounding volumes. The book covers the whole spectrum of collision detection from the primitive level to acceleration structures, such as kd-trees, sphere trees, uniform grids, hashed uniform grids, octrees, quadtrees, binary space partitioning trees, and axis-aligned bounding box trees. At the lowest level, the book covers primitive tests, such as closest point to plane, line segment, axis-aligned box, oriented-bounding box, and triangle. !The techniques for intersecting rays against these primitives are covered in detail as well. A chapter on numerical robustness and geometric robustness deals with the real-world problem of making these algorithms run well on machines with limited floating point precision. Finally, the book is topped off with an excellent chapter on optimizing these algorithms to run well on modern computer architectures, paying special attention to the effect of the memory hierarchy and cache coherence on good running speed.

I found this book to be a valuable reference when implementing the collision system for the game I was working on. Several techniques were clearly illustrated by code fragments and diagrams. The book is targeted toward the mathematically inclined engineer, so some familiarity with the topic is recommended. I’ve implemented several of the techniques from the book and found them to be mostly useful, except that they have to be modified to suit your target appli!cation first. For example, the treatment of cache friendly kd-trees is excellent. The author describes interesting bit hacks to compress the kd splitting plane and the splitting plane value into one float in order to fit the largest amount of kd-tree data into one cache line. Unfortunately, the real-world demands of production code usually mean adding game-specific metadata that pollutes the nice clean implementation described. The ideas in the book were very useful in inspiring me while I was optimizing my own collision code. The book is clearly written and relevant to graphics engineers working on computer games. The emphasis on designing algorithms with memory coherence in mind is in line with the latest practices recommended by the central processing unit (CPU) vendors.