Collision Detection in Interactive 3D Environments (The Morgan Kaufmann Series in Interactive 3D Technology) [Hardcover]

Gino van den Bergen (Author)

Book Description

ISBN-10: 155860801X | ISBN-13: 978-1558608016 | Publication Date: November 10, 2003

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 attempt to build a fast, accurate, and robust collision detection system takes them down a long path fraught with perils and pitfalls unlike most they have ever encountered. Without in-depth knowledge and understanding of the issues associated with engineering a collision detection system, the end of that path is an abyss that has swallowed many a good programmer!

Gino van den Bergen's new book is the story of his successful journey down that path. The outcome is his well-known collision detection system, the SOftware Library for Interference Detection (SOLID). Along the way, he covers the topics of vector algebra and geometry, the various geometric primitives of interest in a collision system, the powerful method of separating axes for the purposes of intersection testing, and the equally powerful Gilbert-Johnson-Keerthi (GJK) algorithm for computing the distance between convex objects. But this book provides much more than a good compendium of the ideas that go into building a collision system. The curse of practical computational geometry is floating-point arithmetic. Algorithms with straightforward implementations when using exact arithmetic can have catastrophic failures in a floating-point system. Specifically, intersection and distance algorithms implemented in a floating-point system tend to fail exactly in the most important case in a collision system-when two objects are just touching. Great care must be taken to properly handle floating-point round off errors. Gino's ultimate accomplishment in this book is his presentation on how to correctly implement the GJK distance algorithm in the presence of single-precision floating-point arithmetic. And what better way to illustrate this than with a case study, the final chapter on the design and implementation of SOLID.

About the CD-ROM
The companion CD-ROM includes the full C++ source code of SOLID 3.5 as well as API documentation in HTML and PDF formats. Both single (32bit) and double (64bit) precision versions of the SOLID SDK plus example programs can be compiled for Linux platforms using GNU g++ version 2.95 to 3.3 and for Win32 platforms using Microsoft Visual C++ version 6.0 to 7.1. Use of the SOLID source code is governed by the terms of either the GNU GPL or the Trolltech QPL (see CD-ROM documentation for details).

About the Author
Gino van den Bergen is a game developer living and working in 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.

*Explains the fundamental geometric and numerical concepts that underlie the key algorithms of collision detection.
*CD-ROM includes the full C++ source code of SOLID, a well-known library for collision detection, plus binaries and example programs for Win32.
*Discusses algorithms for commonly used primitive types, such as spheres, boxes, cylinders, cones, triangles, rays, and convex polyhedra.
*Presents techniques for accelerating collision detection for complex models and scenes.

Editorial Reviews

Review

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

Book Description

The first book on this essential topic in game development and simulation.

See all Editorial Reviews

Product Details

• Hardcover: 277 pages
• Publisher: Morgan Kaufmann (November 10, 2003)
• Language: English
• ISBN-10: 155860801X
• ISBN-13: 978-1558608016
• Product Dimensions: 9.7 x 7.3 x 0.8 inches
• Shipping Weight: 1.5 pounds (View shipping rates and policies)
• Average Customer Review: 4.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #862,960 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

20 of 20 people found the following review helpful:

4.0 out of 5 stars A SOLID discussion of colllision detection, May 12, 2004

By 

Tasha Jessup (San Diego, CA United States) - See all my reviews
(REAL NAME)   

This review is from: Collision Detection in Interactive 3D Environments (The Morgan Kaufmann Series in Interactive 3D Technology) (Hardcover)

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.

2 of 9 people found the following review helpful:

5.0 out of 5 stars Must Have book for your 3D geometry programming, November 10, 2005

By 

Baris Kazar "Geoman" (Boston USA) - See all my reviews
(REAL NAME)   

This review is from: Collision Detection in Interactive 3D Environments (The Morgan Kaufmann Series in Interactive 3D Technology) (Hardcover)

This is a wonderful book. i admire the effort of compiling vast amount of resources into this book. if you are doing 3D programming, you must have this book.