Real-Time Collision Detection (Hardcover)

Christer Ericson

  • 出版商: Morgan Kaufmann
  • 出版日期: 2004-12-01
  • 售價: $5,210
  • 貴賓價: 9.5$4,950
  • 語言: 英文
  • 頁數: 632
  • 裝訂: Hardcover
  • ISBN: 1558607323
  • ISBN-13: 9781558607323
  • 下單後立即進貨 (約2~3週)

買這商品的人也買了...

相關主題

商品描述

Description:

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.

 

 

Table of Contents:

Preface

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
3.1.6.1 ORIENT2D(A, B, C)
3.1.6.2 ORIENT3D(A, B, C, D)
3.1.6.3 INCIRCLE2D(A, B, C, D)
3.1.6.4 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 Barycentric Coordinates
3.5 Lines, Rays, and Segments
3.6 Planes and Halfspaces
3.7 Polygons
3.7.1 Testing Polygonal Convexity
3.8 Polyhedra
3.8.1 Testing Polyhedral Convexity
3.9 Computing Convex Hulls
3.9.1 Andrew's Algorithm
3.9.2 The Quickhull Algorithm
3.10 Voronoi Regions
3.11 Minkowski Sum and Difference
3.12 Summary

4 Bounding Volumes
4.1 Desired BV Characteristics
4.2 Axis-Aligned Bounding Boxes (AABBs)
4.2.1 AABB-AABB Intersection
4.2.2 Computing and Updating AABBs
4.2.3 AABB from the Object Bounding Sphere
4.2.4 AABB Reconstructed from Original Point Set
4.2.5 AABB from Hill-Climbing Vertices of the Object Representation
4.2.6 AABB Recomputed from Rotated AABB
4.3 Spheres
4.3.1 Sphere-Sphere Intersection
4.3.2 Computing a Bounding Sphere
4.3.3 Bounding Sphere from Direction of Maximum Spread
4.3.4 Bounding Sphere Through Iterative Refinement
4.3.5 The Minimum Bounding Sphere
4.4 Oriented Bounding Boxes (OBBs)
4.4.1 OBB-OBB Intersection
4.4.2 Making the Separating-Axis Test Robust
4.4.3 Computing a Tight OBB
4.4.4 Optimizing PCA-Based OBBs
4.4.5 Brute-Force OBB Fitting
4.5 Sphere-Swept Volumes
4.5.1 Sphere-Swept Volume Intersection
4.5.2 Computing Sphere-Swept Bounding Volumes
4.6 Halfspace Intersection Volumes
4.6.1 Kay-Kajiya Slab-Based Volumes
4.6.2 Discrete-Orientation Polytopes (k-DOPs)
4.6.3 k-DOP-k-DOP Overlap Test
4.6.4 Computing and Realigning k-DOPs
4.6.5 Approximate Convex Hull Intersection Tests
4.7 Other Bounding Volumes
4.8 Summary

5 Basic Primitive Tests
5.1 Closest Point Computations
5.1.1 Closest Point on Plane to Point
5.1.2 Closest Point on Line Segment to Point
5.1.2.1 Distance of Point to Segment
5.1.3 Closest Point on AABB to Point
5.1.3.1 Distance of Point to AABB
5.1.4 Closest Point on OBB to Point
5.1.4.1 Distance of Point to OBB
5.1.4.2 Closest Point on 3D Rectangle to Point
5.1.5 Closest Point on Triangle to Point
5.1.6 Closest Point on Tetrahedron to Point
5.1.7 Closest Point on Convex Polyhedron to Point
5.1.8 Closest Points of Two Lines
5.1.9 Closest Points of Two Line Segments
5.1.9.1 2D Segment Intersection
5.1.10 Closest Points of a Line Segment and a Triangle
5.1.11 Closest Points of Two Triangles
5.2 Testing primitives
5.2.1 Separating Axis Test
5.2.1.1 Robustness of the Separating Axis Test
5.2.2 Testing Sphere against Plane
5.2.3 Testing Box against Plane
5.2.4 Testing Cone against Plane
5.2.5 Testing Sphere against AABB
5.2.6 Testing Sphere against OBB
5.2.7 Testing Sphere against Triangle
5.2.8 Testing Sphere against Polygon
5.2.9 Testing AABB against Triangle
5.2.10 Testing Triangle against Triangle
5.3 Intersecting Lines, Rays, and (Directed) Segments
5.3.1 Intersecting Segment against Plane
5.3.2 Intersecting Ray or Segment against Sphere
5.3.3 Intersecting Ray or Segment against Box
5.3.4 Intersecting Line against Triangle
5.3.5 Intersecting Line against Quadrilateral
5.3.6 Intersecting Ray or Segment against Triangle
5.3.7 Intersecting Ray or Segment against Cylinder
5.3.8 Intersecting Ray or Segment against Convex Polyhedron
5.4 Additional Tests
5.4.1 Testing Point in Polygon
5.4.2 Testing Point in Triangle
5.4.3 Testing Point in Polyhedron
5.4.4 Intersection of Two Planes
5.4.5 Intersection of Three Planes
5.5 Dynamic Intersection Tests
5.5.1 Interval Halving for Intersecting Moving Objects
5.5.2 Separating Axis Test for Moving Convex Objects
5.5.3 Intersecting Moving Sphere against Plane
5.5.4 Intersecting Moving AABB against Plane
5.5.5 Intersecting Moving Sphere against Sphere
5.5.6 Intersecting Moving Sphere against Triangle (and Polygon)
5.5.7 Intersecting Moving Sphere against AABB
5.5.8 Intersecting Moving AABB against AABB
5.6 Summary

6 Bounding Volume Hierarchies
6.1 Hierarchy Design Issues
6.1.1 Desired BVH Characteristics
6.1.2 Cost Functions
6.1.3 Tree Degree
6.2 Building Strategies for Hierarchy Construction
6.2.1 Top-Down Construction
6.2.1.1 Partitioning Strategies
6.2.1.2 Choice of Partitioning Axis
6.2.1.3 Choice of Split Point
6.2.2 Bottom-Up Construction
6.2.2.1 Improved Bottom-Up Construction
6.2.2.2 Other Bottom-Up Construction Strategies
6.2.2.3 Bottom-Up N-Ary Clustering Trees
6.2.3 Incremental (Insertion) Construction
6.2.3.1 The Goldsmith-Salmon Incremental Construction Method
6.3 Hierarchy Traversal
6.3.1 Descent Rules
6.3.2 Generic Informed Depth-First Traversal
6.3.3 Simultaneous Depth-First Traversal
6.3.4 Optimized Leaf-Direct Depth-First Traversal
6.4 Example Bounding Volume Hierarchies
6.4.1 OBB-Trees
6.4.2 AABB-Trees and BoxTrees
6.4.3 Sphere-Tree through Octree Subdivision
6.4.4 Sphere-Tree from Sphere-Covered Surfaces
6.4.5 Generate-and-Prune Sphere Covering
6.4.6 k-DOP Trees
6.5 Merging Bounding Volumes
6.5.1 Merging Two AABBs
6.5.2 Merging Two Spheres
6.5.3 Merging Two OBBs
6.5.4 Merging Two k-DOPs
6.6 Efficient Tree Representation and Traversal
6.6.1 Array Representation
6.6.2 Preorder Traversal Order
6.6.3 Offsets Instead of Pointers
6.6.4 Cache-Friendlier Structures (Non-Binary Trees)
6.6.5 Tree Node and Primitive Ordering
6.6.6 On Recursion
6.6.7 Grouping Queries
6.7 Improved Queries through Caching
6.7.1 Surface Caching: Caching Intersecting Primitives
6.7.2 Front Tracking
6.8 Summary

7 Spatial Partitioning
7.1 Uniform Grids
7.1.1 Cell Size Issues
7.1.2 Grids as Arrays of Linked Lists
7.1.3 Hashed Storage and Infinite Grids
7.1.4 Storing Static Data
7.1.5 Implicit Grids
7.1.6 Uniform Grid Object-Object Test
7.1.6.1 One Test at a Time
7.1.6.2 All Tests at a Time
7.1.7 Additional Grid Considerations
7.2 Hierarchical Grids
7.2.1 Basic Hgrid Implementation
7.2.2 Alternative Hierarchical Grid Representations
7.2.3 Other Hierarchical Grids
7.3 Trees
7.3.1 Octrees (and Quadtrees)
7.3.2 Octree Object Assignment
7.3.3 Locational Codes and Finding the Octant for a Point
7.3.4 Linear Octrees (Hash-Based)
7.3.5 Computing the Morton Key
7.3.6 Loose Octrees
7.3.7 k-d Trees
7.3.8 Hybrid Schemes
7.4 Ray and Directed Line Segment Traversals
7.4.1 k-d Tree Intersection Test
7.4.2 Uniform Grid Intersection Test
7.5 Sort and Sweep Methods
7.5.1 Sorted Linked List Implementation
7.5.2 Array-Based Sorting
7.6 Cells and Portals
7.7 Avoiding Retesting
7.7.1 Bit Flags
7.7.2 Time Stamping
7.7.3 Amortized Time Stamp Clearing
7.8 Summary

8 BSP Tree Hierarchies
8.1 BSP Trees
8.2 Types of BSP Trees
8.2.1 Node-Storing BSP Trees
8.2.2 Leaf-Storing BSP Trees
8.2.3 Solid-Leaf BSP Trees
8.3 Building the BSP Tree
8.3.1 Selecting Dividing Planes
8.3.2 Evaluating Dividing Planes
8.3.3 Classifying Polygons with Respect to a Plane
8.3.4 Splitting Polygons against a Plane
8.3.5 More on Polygon splitting Robustness
8.3.6 Tuning BSP Tree Performance
8.4 using the BSP Tree
8.4.1 Testing Point against a Solid-Leaf BSP Tree
8.4.2 Intersecting Ray against a Solid-Leaf BSP Tree
8.4.3 Polytope Queries on Solid-Leaf BSP Trees
8.5 Summary

9 Convexity-Based Methods
9.1 Boundary-Based Collision Detection
9.2 Closest Features Algorithms
9.2.1 The V-Clip Algorithm
9.3 Hierarchical Polyhedron Representations
9.3.1 The Dobkin-Kirkpatrick Hierarchy
9.4 Linear and Quadratic Programming
9.4.1 Linear Programming
9.4.1.1 Fourier-Motzkin Elimination
9.4.1.2 Seidel's Algorithm
9.4.2 Quadratic Programming
9.5 The Gilbert-Johnson-Keerthi Algorithm
9.5.1 The Gilbert-Johnson-Keerthi Algorithm
9.5.2 Finding the Point of Minimum Norm in a Simplex
9.5.3 GJK, Closest Points and Contact Manifolds
9.5.4 Hill-Climbing for Extreme Vertices
9.5.5 Exploiting Coherence by Vertex Caching
9.5.6 Rotated Objects Optimization
9.5.7 GJK for Moving Objects
9.6 The Chung-Wang Separating Vector Algorithm
9.7 Summary

10 GPU-Assisted Collision Detection
10.1 Interfacing with the GPU
10.1.1 Buffer Readbacks
10.1.2 Occlusion Queries
10.2 Testing Convex Objects
10.3 Testing Concave Objects
10.4 GPU-Based Collision Filtering
10.5 Summary

11 Numerical Robustness
11.1 Robustness Problem Types
11.2 Representing Real Numbers
11.2.1 The IEEE-754 Floating-Point Formats
11.2.2 Infinity Arithmetic
11.2.3 Floating-Point Error Sources
11.3 Robust Floating-Point Usage
11.3.1 Tolerances Comparisons for Floating-Point Values
11.3.2 Robustness through Thick Planes
11.3.3 Robustness through Sharing of Calculations
11.3.4 Robustness of Fat Objects
11.4 Interval Arithmetic
11.4.1 Interval Arithmetic Examples
11.4.2 Interval Arithmetic in Collision Detection
11.5 Exact and Semi-Exact Computation
11.5.1 Exact Arithmetic using Integers
11.5.2 On Integer Division
11.5.3 Segment Intersection using Integer Arithmetic
11.6 Further Suggestions for Improving Robustness
11.7 Summary

12 Geometrical Robustness
12.1 Vertex Welding
12.2 Computing Adjacency Information
12.2.1 Computing a Vertex-to-Face Table
12.2.2 Computing an Edge-to-Face Table
12.2.3 Testing Connectedness
12.3 Holes, Cracks, Gaps, and T-Junctions
12.4 Merging Coplanar Faces
12.4.1 Testing Coplanarity of Two Polygons
12.4.2 Testing Polygon Planarity
12.5 Triangulation and Convex Partitioning
12.5.1 Triangulation by Ear Cutting
12.5.1.1 Triangulating Polygons with Holes
12.5.2 Convex Decomposition of Polygons
12.5.3 Convex Decomposition of Polyhedra
12.5.4 Dealing with "Nondecomposable" Concave Geometry
12.6 Consistency Testing using Euler's Formula
12.7 Summary

13 Optimization
13.1 CPU Caches
13.2 Instruction Cache Optimizations
13.3 Data Cache Optimizations
13.3.1 Structure Optimizations
13.3.2 Quantized and Compressed Vertex Data
13.3.3 Prefetching and Preloading
13.4 Cache-Aware Data Structures and Algorithms
13.4.1 A Compact Static k-d Tree
13.4.2 A Compact AABB Tree
13.4.3 Cache-Obliviousness
13.5 Software Caching
13.5.1 Cached Linearization Example
13.5.2 Amortized Predictive Linearization Caching
13.6 Aliasing
13.6.1 Type-Based Alias Analysis
13.6.2 Restricted Pointers
13.6.3 Avoiding Aliasing
13.7 Parallelism through SIMD Optimizations
13.7.1 4 Spheres versus 4 Spheres SIMD Test
13.7.2 4 Spheres versus 4 AABBs SIMD Test
13.7.3 4 AABBs versus 4 AABBs SIMD Test
13.8 Branching
13.9 Summary

References
Index

商品描述(中文翻譯)

描述:
由遊戲業界專家Christer Ericson所撰寫的新書是一本關於高效實時碰撞檢測系統組件的全面指南。該書提供了實現工業級碰撞檢測所需的工具和知識,適用於3D遊戲、虛擬現實應用和物理模擬器等高度詳細的動態環境。

該書涵蓋了許多主題,其中一個重點是通過各種網格、樹和排序方法進行空間和物體分割。作者還提供了大量的簡單和複雜幾何形狀的交點和距離測試。向量和矩陣代數的部分為進階主題如Voronoi區域、Minkowski和線性和二次規劃提供了背景知識。

對於程序員來說,但在其他書籍中很少詳細討論的兩個章節是數值和幾何的穩健性,這對於碰撞檢測系統至關重要。還有獨特的章節討論了圖形硬件如何協助碰撞檢測計算以及現代計算機架構的高級優化。總而言之,這本全面的書將成為未來多年的行業標準。

目錄:
前言
1. 簡介
1.1 內容概述
1.2 代碼說明

2. 碰撞檢測設計問題
2.1 碰撞算法設計因素
2.2 應用領域表示
2.2.1 物體表示
2.2.2 碰撞與渲染幾何
2.2.3 碰撞算法專業化
2.3 不同類型的查詢
2.4 環境模擬參數
2.4.1 物體數量
2.4.2 連續運動與同時運動
2.4.3 離散運動與連續運動
2.5 效能
2.5.1 優化概述
2.6 穩健性
2.7 實現和使用的便利性
2.7.1 調試碰撞檢測系統
2.8 總結

3. 數學和幾何基礎
3.1 矩陣
3.1.1 矩陣運算
3.1.2 涉及矩陣的代數恆等式
3.1.3 行列式
3.1.4 使用Cramer法則解決小型線性方程組
3.1.5 2x2和3x3矩陣的逆矩陣
3.1.6 行列式判斷
3.1.6.1 ORIENT2D(A, B, C)
3.1.6.2 ORIENT3D(A, B, C, D)
3.1.6.3 INCIRCLE2D(A, B, C, D)
3.1.6.4 INSPHERE(A, B, C, D, E)
3.2 坐標系統和點
3.3 向量
3.3.1 向量運算
3.3.2 涉及向量的代數恆等式
3.3.3 點積
3.3.4 涉及點積的代數恆等式
3.3.5 叉積
3.3.6 涉及叉積的代數恆等式
3.3.7 純量三重積
3.3.8 涉及純量三重積的代數恆等式
3.4 重心坐標
3.5 線、射線和線段
3.6 平面和半空間
3.7 多邊形
3.7.1 測試多邊形凸性
3.8 多面體
3.8.1 測試多面體凸性
3.9 計算凸包
3.9.1 Andrew算法
3.9.2 Quickhull算法
3.10 Voronoi區域
3.11 Minkowski和差
3.12 總結

4. 包圍體
4.1 期望的包圍體特性
4.2 軸對齊包圍盒(AABB)
4.2.1```