實(shí)時碰撞檢測算法技術(shù)

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