近年來，來自計算幾何（Computational Geometry）的方法已被計算機圖形社區廣泛采用，從而產生了許多精致而有效的算法。本書旨在幫助計算機圖形藝術領域的開發人員深入學習計算幾何的各種幾何數據結構，使讀者能夠識別幾何問題，並在開發計算機圖形算法時選擇最合適的數據結構。

●第1章 四叉樹和八叉樹 11.1 定義 11.2 復雜性與構造 21.3 高度場可視化 31.4 等值面生成 71.5 光線發射 101.6 3D八叉樹 111.7 5D八叉樹 14第2章 正交截窗和穿刺查詢 192.1 區間樹 202.2 線段樹 232.3 多層線段樹 282.4 kd樹 322.5 範圍樹 362.6 （軸平行框/軸平行框）截窗問題 402.7 紋理合成 432.8 形狀匹配 45第3章 BSP樹 473.1 沒有Z緩衝區的渲染 483.2 使用BSP表示對像 503.3 布爾運算 503.4 構造啟發式算法 543.4.1 凸面對像 553.4.2 成本驅動的啟發式算法 553.4.3 非均勻查詢 563.4.4 推遲的自組織性BSP 57 第4章 包圍體分層結構 594.1 BVH的構造 634.1.1 構造標準 654.1.2 用於踫撞檢測的標準 674.1.3 構造算法 684.2 更新漸變對像 704.3 踫撞檢測 72第5章 距離場 795.1 距離場的計算和表示 815.1.1 傳播方法 825.1.2 距離函數的投影 835.2 距離場的應用 845.2.1 漸變變形 855.2.2 造型 86第6章 Voronoi圖 896.1 定義和屬性 896.1.1 二維中的Voronoi圖 896.1.2 二維中的德洛內三角剖分 916.2 計算 946.3 Voronoi圖的推廣應用 1026.3.1 在3D中的Voronoi圖和德洛內三角剖分 1026.3.2 受約束的Voronoi圖 1076.3.3 一般化的類型 1096.4 Voronoi圖的應用 1136.4.1 最近鄰或郵局問題 1136.4.2 Voronoi圖在2D和3D中的其他應用 1206.5 計算機圖形學中的Voronoi圖 1236.5.1 馬賽克 1236.5.2 自然鄰居插值 130 第7章 幾何接近圖形 1357.1 一個很小的接近圖形集合 1367.1.1 初步定義 1367.1.2 一些接近圖的定義 1377.1.3 包含屬性 1417.1.4 構造算法 1437.2 分類 1467.2.1 問題描述 1467.2.2 編輯和簡化集合 1487.2.3 用於編輯的接近圖形 1497.2.4 清除訓練集合 1517.3 由點雲定義的表面 1527.3.1 隱式表面建模 1537.3.2 歐幾裡得內核 1557.3.3 測地距離近似 1557.3.4 自動帶寬計算 1567.3.5 自動邊界檢測 1587.3.6 函數復雜度評估 1587.4 點雲之間的交叉檢測 1597.4.1 根劃界 1607.4.2 鄰居的大小 1617.4.3 完成劃界 1627.4.4 插值搜索 1637.4.5 帶邊界的模型 1647.4.6 準確的交點 1657.4.7 運行時間 166第8章 運動數據結構 1698.1 通用術語表 1708.2 靜態分段樹 1718.3 運動分段樹 1728.4 平面中的運動BSP 174 第9章 退化和魯棒性 1819.1 幾何算法中的不穩定性示例 1839.1.1 線段的交點 1839.1.2 用超平面切割多面體 1879.2 魯棒性和穩定性的正式定義 1899.3 幾何計算與算術 1919.3.1 浮點運算 1919.3.2 準確算術 2019.3.3 魯棒而高效的運算 2069.3.4 準確幾何計算（EGC） 2239.4 魯棒的表達式和謂詞 2249.4.1 公式重排的示例 2259.4.2 魯棒表達式綜述 2289.4.3 對行列式的有效評估 2389.5 退化 2399.5.1 退化的形式定義 2399.5.2 符號擾動 2409.5.3 直接擾動 2489.6 不準確的算術方法 2509.6.1 Epsilon算術和近似謂詞 2509.6.2 計算凸包 2529.7 實用建議和現有軟件包 2569.7.1 不準確算術和準確算術 2569.7.2 對於EGC的支持 2569.7.3 軟件包和庫 257第10章 幾何數據結構的動態化 26110.1 動態化示例 26210.1.1 隨著時間的推移分攤kd樹插入操作 26310.1.2 靜態kd分解 26410.1.3 在kd樹二進制表示中的查詢操作 26610.1.4 通過半大小規則對kd樹執行通用刪除操作 26610.1.5 kd樹的半大小規則和二進制分解 26710.2 動態化的模型 26910.3 分攤插入和刪除 27110.3.1 分攤插入：二進制結構 27110.3.2 分攤刪除：半大小規則 27610.3.3 分攤插入和分攤刪除 27710.4 最壞情況下的動態化 27910.5 搜索查詢數據結構的應用 283參考文獻 287

本書詳細闡述了與計算機圖形學中幾何體數據結構相關的基本解決方案，主要包括四叉樹和八叉樹、正交截窗和穿刺查詢、BSP樹、包圍體分層結構、距離場、Voronoi圖、幾何接近圖形、運動數據結構、退化和魯棒性，以及幾何數據結構的動態化等內容。此外，本書還提供了相應的示例，以幫助讀者進一步理解相關方案的實現過程。本書適合作為高等院校計算機及相關專業的教材和教學參考書，也可作為相關開發人員的自學教材和參考手冊。

近年來，來自計算幾何（Computational Geometry）的方法已被計算機圖形社區廣泛采用，從而產生了許多精致而有效的算法。本書旨在幫助計算機圖形藝術領域的開發人員深入學習計算幾何的各種幾何數據結構，使讀者能夠識別幾何問題，並在開發計算機圖形算法時選擇最合適的數據結構。本書將重點介紹已被證明具有通用性、高效性、基礎性和易於實現的算法和數據結構。因此，開發人員和研究人員可以立即在日常工作中體會到本書的好處。本書的目標是讓計算機圖形藝術的開發人員和研究人員熟悉一些非常通用和無處不在的幾何數據結構，使他們能夠在工作中輕松識別幾何問題，有能力根據需要修改算法，並希望能激發讀者對計算幾何領域的探索興趣，進一步發掘出功能更強大的寶藏。為了以引人入勝但又比較合理的方式實現這些目標，全書將貫徹通俗易懂的指導思想，按以下方式呈現每個幾何數據結構：首先，詳細定義和描述數據結構；其次，突出等