第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章 几何接近图形

7.1 一个很小的接近图形集合

7.1.1 初步定义

7.1.2 一些接近图的定义

7.1.3 包含属性

7.1.4 构造算法

7.2 分类

7.2.1 问题描述

7.2.2 编辑和简化集合

7.2.3 用于编辑的接近图形

7.2.4 清除训练集合

7.3 由点云定义的表面

7.3.1 隐式表面建模

7.3.2 欧几里得内核

7.3.3 测地距离近似

7.3.4 自动带宽计算

7.3.5 自动边界检测

7.3.6 函数复杂度评估

7.4 点云之间的交叉检测

7.4.1 根划界

7.4.2 邻居的大小

7.4.3 完成划界

7.4.4 插值搜索

7.4.5 带边界的模型

7.4.6 精确的交点

7.4.7 运行时间

第8章 运动数据结构

8.1 通用术语表

8.2 静态分段树

8.3 运动分段树

8.4 平面中的运动BSP

第9章 退化和鲁棒性

9.1 几何算法中的不稳定性示例

9.1.1 线段的交点

9.1.2 用超平面切割多面体

9.2 鲁棒性和稳定性的正式定义

9.3 几何计算与算术

9.3.1 浮点运算

9.3.2 精确算术

9.3.3 鲁棒而高效的运算

9.3.4 精确几何计算（EGC）

9.4 鲁棒的表达式和谓词

9.4.1 公式重排的示例

9.4.2 鲁棒表达式综述

9.4.3 对行列式的有效评估

9.5 退化

9.5.1 退化的形式定义

9.5.2 符号扰动

9.5.3 直接扰动

9.6 不精确的算术方法

9.6.1 Epsilon算术和近似谓词

9.6.2 计算凸包

9.7 实用建议和现有软件包

9.7.1 不精确算术和精确算术

9.7.2 对于EGC的支持

9.7.3 软件包和库

第10章 几何数据结构的动态化

10.1 动态化示例

10.1.1 随着时间的推移分摊kd树插入操作

10.1.2 静态kd树的二元分解

10.1.3 在kd树二进制表示中的查询操作

10.1.4 通过半大小规则对kd树执行通用删除操作

10.1.5 kd树的半大小规则和二进制分解

10.2 动态化的模型

10.3 分摊插入和删除

10.3.1 分摊插入：二进制结构

10.3.2 分摊删除：半大小规则

10.3.3 分摊插入和分摊删除

10.4 最坏情况下的动态化

10.5 搜索查询数据结构的应用

参考文献