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

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

　　《计算机图形学：几何体数据结构》详细阐述了与计算机图形学中几何体数据结构相关的基本解决方案，主要包括四叉树和八叉树、正交截窗和穿刺查询、BSP树、包围体分层结构、距离场、Voronoi图、几何接近图形、运动数据结构、退化和鲁棒性，以及几何数据结构的动态化等内容。此外，该书还提供了相应的示例，以帮助读者进一步理解相关方案的实现过程。
　　《计算机图形学：几何体数据结构》适合作为高等院校计算机及相关专业的教材和教学参考书，也可作为相关开发人员的自学教材和参考手册。

第1章 四叉树和八叉树
1．1 定义
1．2 复杂性与构造
1．3 高度场可视化
1．4 等值面生成
1．5 光线发射
1．6 3D八叉树
1．7 5D八叉树

第2章 正交截窗和穿刺查询
2．1 区间树
2．2 线段树
2．3 多层线段树
2．4 kd树
2．5 范围树
2．6 （轴平行框／轴平行框）截窗问题
2．7 纹理合成
2．8 形状匹配

第3章 BSP树
3．1 没有Z缓冲区的渲染
3．2 使用BSP表示对象
3．3 布尔运算
3．4 构造启发式算法
3．4．1 凸面对象
3．4．2 成本驱动的启发式算法
3．4．3 非均匀查询
3．4．4 推迟的自组织性BSP

第4章 包围体分层结构
4．1 BVH的构造
4．1．1 构造标准
4．1．2 用于碰撞检测的标准
4．1．3 构造算法
4．2 更新渐变对象
4．3 碰撞检测

第5章 距离场
5．1 距离场的计算和表示
5．1．1 传播方法
5．1．2 距离函数的投影
5．2 距离场的应用
5．2．1 渐变变形
5．2．2 造型

第6章 Voronoi图
6．1 定义和属性
6．1．1 二维中的Voronoi图
6．1．2 二维中的德洛内三角剖分
6．2 计算
6．3 Voronoi图的推广应用
6．3．1 在3D中的Voronoi图和德洛内三角剖分
6．3．2 受约束的Voronoi图
6．3．3 一般化的类型
6．4 Voronoi图的应用
6．4．1 最近邻或邮局问题
6．4．2 Voronoi图在2D和3D中的其他应用
6．5 计算机图形学中的Voronoi图
6．5．1 马赛克
6．5．2 自然邻居插值
……
第7章 几何接近图形
第8章 运动数据结构
第9章 退化和鲁棒性
第10章 几何数据结构的动态化
参考文献

　　1993年10月8日，一款令当时无数玩家为之疯狂的游戏诞生了，那就是由ID Software 公司推出的DOOM（中文版名称《毁灭战士》），在那个以MS-DOS操作系统为主流的年代， 《毁灭战士》以流畅的操作、快节奏的打击感，赢得了众多玩家的好评，成为一代人心目中令人怀念的游戏。《毁灭战士》为什么能获得如此高的评价？主要原因在于它开创性地采用了BSP树技术，在碰撞检测方面拥有极高的效率，从而使它在那个计算资源非常欠缺的年代，仍然以流畅的游戏体验，赢得了广大玩家的厚爱。
　　事实上，BSP树只是众多计算几何方法中的一种。实践证明，要想在电子游戏、虚拟现实和动画娱乐等方面取得开创性的成绩，就必须认真学习和研究底层算法。独特而先进的算法往往是开发人员成功的关键。本书是对计算机图形艺术中几何数据结构及其算法的深度阐释，包含对四叉树、kd树、BSP树、Voronoi图、接近图形、包围体分层结构以及几何数据结构的动态化等的主题讨论和算法分析。通过对各种研究成果的介绍，使读者对几何数据结构的应用有比较全面的了解，从而帮助读者结合自己的工作实际，研究和探索新颖而高效的算法。
　　在翻译本书的过程中，译者力争做到小心求证、准确表述。但是由于计算机图形艺术的发展日新月异，中文对大量新出现的术语的翻译缺乏标准和统一，所以，为了保证译文术语的一致性，译者对于关键术语提供了相应的英文对照，消除了读者的阅读理解障碍。除此之外，译者也鼓励读者多接受以中英文对照的形式了解专业术语，掌握更多的英文术语原文，这不但有助于对各种理论和算法的准确理解，也便于和国外同行一起学习和交流。
　　本书适用于三维计算机图形学（虚拟现实、计算机辅助设计／计算机辅助制造、娱乐、动画等）的从业人员和爱好者，以及计算机图形学和计算几何学专业的学生。
　　本书由黄刚翻译，马宏华、陈凯、黄进青、熊爱华、黄永强也参与了本书的翻译工作。由于译者水平有限，错漏之处在所难免，在此诚挚欢迎读者提出任何意见和建议。