《計算機圖形學——幾何體數據結構》是2019年8月清華大學出版社出版的圖書，作者是[美]埃爾馬·拉格迪普（Elmar Langetepe ）、[美] 加布里埃爾·扎克曼（Gabriel Zachmann）。
基本介紹
- 書名：計算機圖形學——幾何體數據結構
- 作者：[美]埃爾馬·拉格迪普（Elmar Langetepe ）、[美] 加布里埃爾·扎克曼（Gabriel Zachmann）
- 譯者：黃剛
- 出版社：清華大學出版社
- 出版時間：2019年08月
- 定價：109 元
- ISBN：9787302527930
內容簡介,圖書目錄,
內容簡介
本書詳細闡述了與計算機圖形學中幾何體數據結構相關的基本解決方案，主要包括四叉樹和八叉樹、正交截窗和穿刺查詢、BSP樹、包圍體分層結構、距離場、Voronoi圖、幾何接近圖形、運動數據結構、退化和魯棒性，以及幾何數據結構的動態化等內容。此外，本書還提供了相應的示例，以幫助讀者進一步理解相關方案的實現過程。
本書適合作為高等院校計算機及相關專業的教材和教學參考書，也可作為相關開發人員的自學教材和參考手冊。
圖書目錄
第1章 四叉樹和八叉樹 1
1.1 定義 1
1.2 複雜性與構造 2
1.3 高度場可視化 3
1.4 等值面生成 7
1.5 光線發射 10
1.6 3D八叉樹 11
1.7 5D八叉樹 14
第2章 正交截窗和穿刺查詢 19
2.1 區間樹 20
2.2 線段樹 23
2.3 多層線段樹 28
2.4 kd樹 32
2.5 範圍樹 36
2.6 （軸平行框/軸平行框）截窗問題 40
2.7 紋理合成 43
2.8 形狀匹配 45
第3章 BSP樹 47
3.1 沒有Z緩衝區的渲染 48
3.2 使用BSP表示對象 50
3.3 布爾運算 50
3.4 構造啟發式算法 54
3.4.1 凸面對象 55
3.4.2 成本驅動的啟發式算法 55
3.4.3 非均勻查詢 56
3.4.4 推遲的自組織性BSP 57
第4章 包圍體分層結構 59
4.1 BVH的構造 63
4.1.1 構造標準 65
4.1.2 用於碰撞檢測的標準 67
4.1.3 構造算法 68
4.2 更新漸變對象 70
4.3 碰撞檢測 72
第5章 距離場 79
5.1 距離場的計算和表示 81
5.1.1 傳播方法 82
5.1.2 距離函式的投影 83
5.2 距離場的套用 84
5.2.1 漸變變形 85
5.2.2 造型 86
第6章 Voronoi圖 89
6.1 定義和屬性 89
6.1.1 二維中的Voronoi圖 89
6.1.2 二維中的德洛內三角剖分 91
6.2 計算 94
6.3 Voronoi圖的推廣套用 102
6.3.1 在3D中的Voronoi圖和德洛內三角剖分 102
6.3.2 受約束的Voronoi圖 107
6.3.3 一般化的類型 109
6.4 Voronoi圖的套用 113
6.4.1 最近鄰或郵局問題 113
6.4.2 Voronoi圖在2D和3D中的其他套用 120
6.5 計算機圖形學中的Voronoi圖 123
6.5.1 馬賽克 123
6.5.2 自然鄰居插值 130
第7章 幾何接近圖形 135
7.1 一個很小的接近圖形集合 136
7.1.1 初步定義 136
7.1.2 一些接近圖的定義 137
7.1.3 包含屬性 141
7.1.4 構造算法 143
7.2 分類 146
7.2.1 問題描述 146
7.2.2 編輯和簡化集合 148
7.2.3 用於編輯的接近圖形 149
7.2.4 清除訓練集合 151
7.3 由點雲定義的表面 152
7.3.1 隱式表面建模 153
7.3.2 歐幾里得核心 155
7.3.3 測地距離近似 155
7.3.4 自動頻寬計算 156
7.3.5 自動邊界檢測 158
7.3.6 函式複雜度評估 158
7.4 點雲之間的交叉檢測 159
7.4.1 根劃界 160
7.4.2 鄰居的大小 161
7.4.3 完成劃界 162
7.4.4 插值搜尋 163
7.4.5 帶邊界的模型 164
7.4.6 精確的交點 165
7.4.7 運行時間 166
第8章 運動數據結構 169
8.1 通用術語表 170
8.2 靜態分段樹 171
8.3 運動分段樹 172
8.4 平面中的運動BSP 174
第9章 退化和魯棒性 181
9.1 幾何算法中的不穩定性示例 183
9.1.1 線段的交點 183
9.1.2 用超平面切割多面體 187
9.2 魯棒性和穩定性的正式定義 189
9.3 幾何計算與算術 191
9.3.1 浮點運算 191
9.3.2 精確算術 201
9.3.3 魯棒而高效的運算 206
9.3.4 精確幾何計算（EGC） 223
9.4 魯棒的表達式和謂詞 224
9.4.1 公式重排的示例 225
9.4.2 魯棒表達式綜述 228
9.4.3 對行列式的有效評估 238
9.5 退化 239
9.5.1 退化的形式定義 239
9.5.2 符號擾動 240
9.5.3 直接擾動 248
9.6 不精確的算術方法 250
9.6.1 Epsilon算術和近似謂詞 250
9.6.2 計算凸包 252
9.7 實用建議和現有軟體包 256
9.7.1 不精確算術和精確算術 256
9.7.2 對於EGC的支持 256
9.7.3 軟體包和庫 257
第10章 幾何數據結構的動態化 261
10.1 動態化示例 262
10.1.1 隨著時間的推移分攤kd樹插入操作 263
10.1.2 靜態kd樹的二元分解 264
10.1.3 在kd樹二進制表示中的查詢操作 266
10.1.4 通過半大小規則對kd樹執行通用刪除操作 266
10.1.5 kd樹的半大小規則和二進制分解 267
10.2 動態化的模型 269
10.3 分攤插入和刪除 271
10.3.1 分攤插入：二進制結構 271
10.3.2 分攤刪除：半大小規則 276
10.3.3 分攤插入和分攤刪除 277
10.4 最壞情況下的動態化 279
10.5 搜尋查詢數據結構的套用 283
參考文獻 287
