第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

前    言
近年來，來自計算幾何（Computational Geometry）的方法已被計算機圖形社區廣泛采用，從而產生了許多精致而有效的算法。本書旨在幫助計算機圖形藝術領域的開發人員深入學習計算幾何的各種幾何數據結構，使讀者能夠識別幾何問題，並在開發計算機圖形算法時選擇合適的數據結構。
本書將重點介紹已被證明具有通用性、高效性、基礎性和易於實現的算法和數據結構。因此，開發人員和研究人員可以立即在日常工作中體會到本書的好處。
本書的目標是讓計算機圖形藝術的開發人員和研究人員熟悉一些非常通用和無處不在的幾何數據結構，使他們能夠在工作中輕松識別幾何問題，有能力根據需要修改算法，並希望能激發讀者對計算幾何領域的探索興趣，進一步發掘出功能更強大的寶藏。
為了以引人入勝但又比較合理的方式實現這些目標，全書將貫徹通俗易懂的指導思想，按以下方式呈現每個幾何數據結構：首先，詳細定義和描述數據結構；其次，突出顯示數據結構的一些基本屬性；然後，呈現基於數據結構的一個或多個計算幾何算法；後，詳細描述來自計算機圖形的許多的、有代表性的，以及在實踐上高度相關的算法，以創造性和啟發性的方式顯示數據結構的應用方案。
本書不會試圖對該領域所涉及的主題進行面面俱到的闡述，這遠遠超出了本書的範圍。此外，本書也不追求為給定問題提供所謂和好的算法，這樣說是出於以下兩個理由：首先，本書的重點是幾何數據結構，我們不希望用復雜的算法來轉移讀者的    視線；其次，我們認為，從實用主義的角度出發，掌握簡單和效率之間的良好平衡非常重要。
本書的目標受眾是三維計算機圖形學（虛擬現實、計算機輔助設計/計算機輔助制造、娛樂、動畫等）的從業人員，以及計算機圖形學和計算幾何學的學生。讀者應熟悉計算機圖形學的基本原理和該領域問題的類型。
本書已經從易到難對章節內容進行了大致的安排。分層數據結構將按靈活性的增加來排序，而非分層數據結構則可以相互構建。此外，後3章還介紹了使幾何數據結構變得更加活躍、健壯和動態的通用技巧。
 
上圖提供了將在本書章節中討論的一些數據結構的概覽。第1章介紹了四叉樹和八叉樹，它們可以說是計算機圖形學中流行的數據結構。接下來解除了其中一個限制，使得數據結構更加靈活，這就是在第2章中介紹的kd樹；而到了第3章，又出現了BSP樹，這同樣可以使數據結構更加靈活；從kd樹出發，還可以推導出包圍體分層結構，而這正是第4章的內容；從四叉樹（甚至是網格）開始，可以存儲有關對像的更多信息，從而引入第5章將要介紹的距離場概念；在某種意義上，距離場是Voronoi圖的離散化版本，所以，在第6章中更詳細地介紹了Voronoi圖；在第7章中，討論了幾何接近圖形的一般分類，其中一種是德洛內圖，這已經在第6章中介紹過；第8章介紹了運動對像專用空間數據結構的一般性概念，並通過實例進行了討論；在第9章中，考慮了幾何計算中的退化和魯棒性問題；後，在第10章中介紹了一個簡單的動態化通用方案。
致謝
我們要感謝Reinhard Klein教授和Rolf Klein教授在本書寫作期間給予的鼓勵和建議。還要感謝AnsgarGrüne、Tom Kamphans、Adalbert Prokop、Manuel Wedemeier和Michael Bazanski，他們辛苦校閱了本書的部分手稿。此外，還要感謝Jan Klein的精彩合作。我們感謝Alice和Klaus Peters策劃了本書的創作，也感謝Kevin Jackson-Mead管理該項目以及他的耐心。Zachmann的部分工作由DFG的基金ZA292/1資助。