Collision Detection in Interactive 3D Environments

Rating:
Summary: A SOLID discussion of colllision detection
Review: In "Collision Detection in Interactive 3D Environments," Gino van den Bergen explores the algorithms necessary to determine whether polygonal intersections occur in a real-time interactive simulation. Published by Morgan Kaufmann for $59.99, the book spans 277 pages through seven chapters and includes a CDROM containing the source code to SOLID 3.5, a collision detection library for interactive 3D computer animation.

After the first chapter's brief introduction and overview, the second chapter details the required concepts of the text. Generally, the collision detection algorithms presented in the book operate convex objects. As such, methods are described to decompose complex shapes into various convex primitives such as spheres, triangles, and boxes. Lastly, some consideration is given to collision response, performance optimizations through frame and geometric coherence, and problems arising from floating point error in calculations. The chapter is heavy in mathematics and notation and makes for a slow and sometimes tedious read.

Chapter three introduces algorithms for various types of primitive collisions through four broad categories: spheres, axis-aligned boxes, separating axes, and polygons. Each category contains an algorithm for various primitive combinations. For example, under the sphere category the routines presented are sphere to sphere, ray to sphere, and line segment to sphere. The each algorithm is well described mathematically then some pseudo-code is provided to illustrate the implementation. Performance is considered when selecting an algorithm and in its implementation. However, each category's primitive combination type presents just one algorithm. While other sources for algorithms are well-cited throughout the book, it would have been beneficial to compare multiple collision algorithms based on various scenarios to explore the topic completely. The SOLID library uses the routines chosen and presented in the text.

In chapter four, convex objects are considered. Van den Bergen considers both single-shot and incremental algorithms designed to perform several types of proximity queries on polytopes. In particular, each algorithm's computational complexity is provided and references are given for additional detail. The bulk of the chapter is devoted to discussion of the Gilbert-Johnson-Keerthi (GJK) algorithm which is used to determine distance and collision of general convex objects. The GJK algorithm is an iterative distance routine but can also be applied to general convex objects. Additionally, the GJK algorithm can exploit frame coherence to improve its performance roughly equivalent with other incremental methods.

Chapter five discusses data structures that reduce the scope of collision calculations during run-time. Through a combination of spatial partitioning, model partitioning, and frame coherence (an assumption that motion is generally smooth and changes per frame are small in a given scene), optimizations can be made to reduce overall computational time in calculating pair-wise collisions between the various types of polyhedra. Each section presents several partitioning methods and provides a case study regarding their performance with a test bed of complex objects to help highlight the performance differences.

Chapter six discusses SOLID, a Software Library for Interference Detection, which is included on the CDROM. Under development for the past seven years, the chapter provides the goals, an overview, design decisions, and restrictions of the library. In fact, the material presented in the preceding chapters is implemented as the SOLID library. The source code to SOLID is provided on the CDROM helps solidify the algorithms and discussion presented in the text. Finally, the last chapter describes the current limitations of collision detection and considers future research areas where further improvement might occur.

Overall, the book does an excellent job presenting the challenges and necessary considerations when designing a collision detection system but not in a manner that is approachable by everyone. Developers capable of appreciating the mathematics and theory will benefit from van den Bergen's description of his insights and experience which ultimately culminate in the design and construction of SOLID.