實時碰撞檢測算法技術

第1章 概述
1.1 內容概覽
1.1.1 第2章 ：碰撞檢測系統(tǒng)中的設計問題
1.1.2 第3章 ：數(shù)學和幾何學入門
1.1.3 第4章 ：包圍體
1.1.4 第5章 ：基本圖元測試
1.1.5 第6章 ：層次包圍體技術
1.1.6 第7章 ：空間劃分
1.1.7 第8章 ：BSP樹層次結構
1.1.8 第9章 ：凸體算法
1.1.9 第10章 ：基于GPU的碰撞檢測
1.1.10 第11章 ：數(shù)值健壯性
1.1.11 第12章 ：幾何健壯性
1.1.12 第13章 ：優(yōu)化操作
1.2 關于本書的代碼
第2章 碰撞檢測系統(tǒng)中的設計問題
2.1 碰撞算法的設計因素
2.2 應用程序中對象的表達方式
2.2.1 對象的表達方式
2.2.2 碰撞與幾何渲染
2.2.3 特定的碰撞檢測算法
2.3 查詢類型
2.4 環(huán)境模擬參數(shù)
2.4.1 物體對象的數(shù)量
2.4.2 順序移動和同步移動
2.4.3 不連續(xù)移動與連續(xù)移動
2.5 性能
2.5.1 優(yōu)化概覽
2.6 健壯性
2.7 實現(xiàn)與使用的簡潔性
2.7.1 碰撞檢測系統(tǒng)的調試
2.8 小結
第3章 數(shù)學和幾何學入門
3.1 矩陣
3.1.1 矩陣運算
3.1.2 矩陣的幾何代數(shù)符號
3.1.3 行列式
3.1.4 利用克萊姆法則計算線性方程組
3.1.5 2x2矩陣和3x3矩陣的逆矩陣
3.1.6 行列式斷言
3.2 坐標系統(tǒng)和頂點
3.3 向量
3.3.1 向量運算
3.3.2 向量的代數(shù)恒等式
3.3.3 點積
3.3.4 點積的代數(shù)恒等式
3.3.5 叉積
3.3.6 叉積的代數(shù)恒等式
3.3.7 標量三重積
3.3.8 標量三重積的代數(shù)恒等式
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 域
3.11 Minkowski和與MinkowSki差
3.12 小結
第4章 包圍體
4.1 BV期望特征
4.2 軸對齊包圍盒
4.2.1 AABB間的相交測試
4.2.2 AABB的計算與更新
4.2.3 基于包圍球的AABB
4.2.4 基于原點的.AABB重構
4.2.5 利用爬山法構造AABB
4.2.6 旋轉AABB后的重計算
4.3 SPlleres球體
4.3.1 其他相交測試
4.3.2 計算包圍球
4.3.3 最大離散方向上的包圍球
4.3.4 采用迭代修正的包圍球
4.3.5 最小包圍球
4.4 方向包圍盒
4.4.1 相交測試
4.4.2 健壯的分離軸測試
4.4.3 計算緊湊的OBB
4.4.4 基于PCA的OBB優(yōu)化
4.4.5 蠻力法實現(xiàn)OBB的擬合
4.5 球掃掠體
4.5.1 球掃掠體的相交測試
4.5.2 球體掃掠體包圍體的計算
4.6 半空間相交體
4.6.1 Kay.Kajiya平行平面空間包圍體
4.6.2 離散有向多面體（k.DOP）
4.6.3 k.DOP-k.DOP相交測試
4.6.4 k.DOP的計算與重對齊
4.6.5 近似凸體相交測試
4.7 其他類型的包圍體
4.8 小結
第5章 基本圖元測試
5.1 最近點計算
5.1.1 點到面的最近點
5.1.2 點至線段的最近點
5.1.3 點至AABB的最近點
5.1.4 點至OBB的最近點
5.1.5 點至三角形的最近點
5.1.6 點到四面體的最近點
5.1.7 點到凸多面體的最近點
5.1.8 兩條直線間的最近點
5.1.9 兩線段上的最近點
5.1.10 線段和三角形最近點
5.1.11 兩個三角形之間的最近點計算
5.2 圖元測試
5.2.1 分離軸測試
5.2.2 球體與平面間的測試
5.2.3 盒體與平面間的測試
5.2.4 錐體與平面間的測試
5.2.5 球體與AABB之間的測試
5.2.6 球體與OBB之間的測試
5.2.7 球體與三角形之間的測試
5.2.8 球體與多邊形之間的測試
5.2.9 AABB與三角形之間的測試
5.2.10 三角形之間的測試
5.3 直線、光線和有向線段的相交測試
5.3.1 線段與平面的相交測試
5.3.2 光線或線段與球體的相交測試
5.3.3 光線或線段與盒體的相交測試
5.3.4 直線與三角形之間的相交測試
5.3.5 直線與四邊形之間的相交測試
5.3.6 光線或線段與三角形之間的相交測試
5.3.7 光線或線段與圓柱體之間的相交測試
5.3.8 光線或線段與凸多面體之間的相交測試
5.4 其他類型的測試
5.4.1 點與多邊形之間的測試
5.4.2 點與三角形之間的測試
5.4.3 點與多面體之間的測試
5.4.4 兩個平面間的相交測試
5.4.5 3個平面間的相交測試
5.5 動態(tài)相交測試
5.5.1 運動物體的區(qū)間半分法相交測試
5.5.2 運動凸體對象的分離軸測試
5.5.3 運動球體與平面間的相交測試
5.5.4 運動AABB與平面間的相交測試
5.5.5 運動球體與球體之間的相交測試
5.5.6 運動球體與三角形以及多邊形之間的相交測試
5.5.7 運動球體與AABB之間的相交測試
5.5.8 運動AABB之間的測試
5.6 小結
第6章 層次包圍體技術
6.1 層次結構設計問題
6.1.1.BVH的期望特征
6.1.2 性能函數(shù)
6.1.3 樹的度數(shù)
6.2 層次結構的構建策略
6.2.1 自頂向下的構造方法
6.2.2 自底向上的構造方法
6.2.3 擴充（插入）構造策略
6.3 層次結構的遍歷
6.3.1 下降規(guī)則
6.3.2 通用的啟發(fā)式深度優(yōu)先遍歷
6.3.3 同步深度優(yōu)先遍歷
6.3.4 優(yōu)化的有向葉節(jié)點深度優(yōu)先遍歷
6.4 包圍體層次結構示例
6.4.1 OBBTreesOBB樹
6.4.2 AABB樹和盒體樹
6.4.3 采用8叉樹子劃分的球體樹
6.4.4 采用球體覆蓋表面的球體樹
6.4.5 生成.修剪球體覆蓋
6.4.6 k.DOP樹
6.5 合并包圍體
6.5.1 合并兩個AABB
6.5.2 合并兩個球體
6.5 13合并兩個OBB
6.5.4 合并兩個k.DOP
6.6 高效的樹型表達方式及遍歷
6.6.1 數(shù)組表達方式
6.6.2 前序遍歷
6.6 13采用偏移量而非指針
6.6.4 采用緩存友好的結構（非二叉樹）
6.6.5 樹節(jié)點和圖元排序
6.6.6 遞歸遍歷
6.6.7 分組查詢
6.7 通過緩存機制改善查詢
6.7.1 表面緩存：緩存相交圖元
6.7.2 前界面追蹤
6.8 小結
第7章 空間劃分
7.1 均勻網(wǎng)格
7.1.1 網(wǎng)格單元的尺寸
7.1.2 采用鏈表數(shù)組表示的網(wǎng)格
7.1.3 哈希存儲與無限網(wǎng)格
7.1.4 靜態(tài)數(shù)據(jù)存儲
7.1.5 隱式網(wǎng)格
7.1.6 使用均勻網(wǎng)格的對象間的測試
7.1.7 網(wǎng)格的其他注意事項
7.2 層次網(wǎng)格
7.2.1 基本的層次網(wǎng)格實現(xiàn)方式
7.2.2 其他類型的層次網(wǎng)格表達方式
7.2.3 其他層次網(wǎng)格
7.3 樹
7.3.1 8叉樹（以及4叉樹）
7.3.2 8叉樹對象的分配
7.3.3 位置碼和8分體的定位
7.3.4 基于哈希存儲的線性樹
7.3.5 計算Morton鍵
7.3.6 松散8叉樹
7.3.7 缸d樹
7.3.8 混合方案
7.4 光線和有向線段的遍歷
7.4.1 缸d樹相交測試
7.4.2 均勻網(wǎng)格的相交測試
7.5 排序掃掠算法
7.5.1 排序鏈表實現(xiàn)方案
7.5.2 基于數(shù)組的排序
7.6 網(wǎng)格單元和偽入口
7.7 避免重復測試
7.7.1 位標志
7.7.2 時間戳
7.7.3 分時清除時間戳
7.8 小結
第8章 BSP樹層次結構
8.1 BSP樹
8.2 BSP樹的類型
8.2.1 采用節(jié)點存儲的BSP樹
8.2.2 采用葉節(jié)點存儲的BSP樹
8.2.3 實體葉節(jié)點BSP樹
8.3 構造BSP樹
8.3.1 分割面的選擇
8.3.2 分割面的評估
8.3.3 基于分割面的多邊形分類
8.3.4 多邊形分割計算
8.3.5 更多討論
8.3.6 BSP樹的性能調試
8.4 BSP樹的應用
8.4.1 點與實體葉節(jié)點：BSP樹間的測試
8.4.2 光線與實體葉節(jié)點BSP樹間的相交測試
8.4.3 基于實體葉節(jié)點BSP樹的多面體查詢
8.5 小結
第9章 凸體算法
9.1 基于邊界的碰撞檢測
9.2 最近特征算法
9.2.1 v.Clip算法
9.3 層次多面體表達形式
9.3.1 Dobkin.Kirkpatrick層次結構
9.4 線性規(guī)劃和二次規(guī)劃
9.4.1 線性規(guī)劃
9.4.2 二次規(guī)劃
9.5 Gilbert.Johnson.Keerthi算法
9.5.1 算法概述
9.5.2 計算單形體內的最小范數(shù)頂點，
9.5.3 GJK算法、最近點以及接觸流形
9.5.4 利用爬山法計算極值頂點
9.5.5 與頂點緩存相關的一致性問題
9.5.6 旋轉對象的優(yōu)化
9.5.7 移動對象的GJK算法
9.6 chung.wang分離向量算法
9.7 小結
第10章 基于GPU的碰撞檢測
10.1 GPU接口
10.1.1 緩沖區(qū)讀取
10.1.2 遮擋查詢
10.2 凸體對象間的測試
10.3 測試凹體對象
10.4 基于GPU的碰撞過濾
10.5 小結
第11章 數(shù)值健壯性
11.1 健壯性問題的分類
11.2 實數(shù)表示法
11.2.1 IEEE.7 54浮點格式
11.2.2 無窮運算
11.2.3 浮點誤差源
11.3 健壯的浮點數(shù)用法
11.3.1 浮點值的誤差容值比較
11.3.2 采用厚平面實現(xiàn)算法的健壯性
11.3.3 采用共享計算實現(xiàn)算法的健壯性
11.3.4 厚對象的健壯性
11.4 區(qū)間計算
11.4.1 區(qū)間計算實例
11.4.2 碰撞檢測中的區(qū)間計算
11.5 精確計算和近似計算
11.5.1 采用整型數(shù)據(jù)實現(xiàn)精確計算
11.5.2 整型除法
11.5 13采用整型運算處理線段相交問題
11.6 提高數(shù)值健壯性的進一步討論
11.7 小結
第12章 幾何健壯性
12.1 頂點焊接
12.2 計算鄰接信息
12.2.1 計算頂點.面表
12.2.2 計算邊.面表
12.2.3 連通性測試
12.3 孔、縫隙、間隙以及t.連接
12.4 共面數(shù)據(jù)面的合并操作
12.4.1 測試多邊形的共面性
12.4.2 多邊形的共面測試
12.5 三角形剖分和凸劃分
12.5.1 耳式剪裁實現(xiàn)三角剖分
12.5.2 多邊形的凸剖分
12.5.3 多面體的凸剖分
12.5.4 不可剖分的凹幾何體
12.6 采用歐拉公式的一致性測試
12.7 小結
第13章 優(yōu)化操作
13.1 CPU緩存
13.2 指令緩存優(yōu)化
13.3 數(shù)據(jù)緩存優(yōu)化
13.3.1 結構優(yōu)化
13.3.2 頂點數(shù)據(jù)的量化操作和壓縮操作
13.3.3 預取和預載操作
13.4 基于緩存感知的數(shù)據(jù)結構和算法
13.4.1 緊湊型靜態(tài)k-d樹
13.4.2 緊湊型AABB樹
13.4.3 緩存參數(shù)無關性
13.5 軟件緩存
13.5.1 緩存線性化操作實例
13.5.2 基于分攤機制的預測線性化緩存
13.6 數(shù)據(jù)別名
13.6.1 基于類型的別名分析
13.6.2 restrict指針：
13.6.3 避免別名問題
13.7 采用SIMD優(yōu)化的并行操作
13.7.1 4球體.4 球體SIMD測試
13.7.2 4球體.4 AABBSIMD測試
13.7.3 4AABB.4 AABBSIMD測試
13.8 分支結構
13.9 小結
參考文獻