计算机图形学——几何体数据结构

        近年来，来自计算几何（Computational Geometry）的方法已被计算机图形社区广泛采用，从而产生了许多精致而有效的算法。本书旨在帮助计算机图形艺术领域的开发人员深入学习计算几何的各种几何数据结构，使读者能够识别几何问题，并在开发计算机图形算法时选择*合适的数据结构。

        本书详细阐述了与计算机图形学中几何体数据结构相关的基本解决方案，主要包括四叉树和八叉树、正交截窗和穿刺查询、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

前    言
近年来，来自计算几何（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资助。