Collision Detection in Interactive 3D Environments (Hardcover)

Gino van den Bergen




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.


Table of Contents:

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

About the CD-ROM



Gino van den Bergen的新書講述了他在這條道路上的成功之旅。結果是他著名的碰撞檢測系統SOftware Library for Interference Detection (SOLID)。在這個過程中,他涵蓋了向量代數和幾何學的主題,碰撞系統中感興趣的各種幾何基元,用於交集測試的分離軸方法以及計算凸物體之間距離的強大的Gilbert-Johnson-Keerthi (GJK)算法。但是,這本書提供的不僅僅是建立碰撞系統所需的思想的良好彙編。實際計算幾何的詛咒是浮點數運算。在使用精確算術時,算法的實現可能很簡單,但在浮點系統中可能會發生災難性故障。具體而言,在浮點系統中實現的交集和距離算法往往在碰撞系統中最重要的情況下失敗,即兩個物體僅僅接觸。必須非常小心地處理浮點數舍入誤差。Gino在這本書中的最終成就是他如何在單精度浮點數算術存在的情況下正確實現GJK距離算法的演示。有什麼比通過一個案例研究更好地說明這一點呢?這本書的最後一章是關於SOLID設計和實現的。

附帶的CD-ROM包括SOLID 3.5的完整C++源代碼,以及HTML和PDF格式的API文檔。可以使用GNU g++版本2.95到3.3在Linux平台上編譯SOLID SDK的單精度(32位)和雙精度(64位)版本,並且可以使用Microsoft Visual C++版本6.0到7.1在Win32平台上編譯。使用SOLID源代碼受GNU GPL或Trolltech QPL的條款約束(詳情請參閱CD-ROM文檔)。

Gino van den Bergen是一位居住在荷蘭並從事遊戲開發的開發者。他是SOLID的創造者,並且擁有埃因霍溫科技大學的計算科學博士學位。Gino在NaN Technologies的Blender中實現了碰撞檢測和物理學,這是一個用於交互式3D內容的創作套件。

1 引言
1.1 問題領域
1.2 歷史背景
1.3 組織

2 概念
2.1 幾何
2.1.1 表示法慣例
2.1.2 向量空間
2.1.3 仿射空間
2.1.4 歐幾里得空間
2.1.5 仿射變換
2.1.6 三維空間
2.2 物體
2.2.1 多面體
2.2.2 多邊形
2.2.3 二次曲線
2.2.4 明可夫斯基相加
2.2.5 複雜形狀和場景
2.3 動畫
2.4 時間
2.5 響應
2.6 效能
2.6.1 幀相干性
2.6.2 幾何相干性
2.6.3 平均時間
2.7 韌性
2.7.1 浮點數
2.7.2 穩定性
2.7.3 複製