几何查询加速

几何查询的复杂性

简单的光线-网格交互，需要计算光线与所有三角形的交互，判断是否交叉、计算最近点。朴素算法的时间复杂度相当于像素数*三角形数，非常慢且低效。

光线与三角形交叉的更快算法：

给定一个包含N个图像基元的几何网格与一条光线r(t)，找到光线首个击中的点。最简单的方法是计算光线和每个三角形可能的交点，然后更新最近的交点。时间复杂度为O(N)。

包围盒

一种快速 (初步) 判断交叉的方法：用最小的立方体包围复杂的几何物体 (包含其所有图像基元)。

包围盒就是三对无限平面的交集，通常选择轴对齐包围盒（AABB）（大大简化计算），即包围盒的任意一面都沿着相应的xyz轴。

包围盒的性能

层次包围盒BVH

一种树形结构，对空间中的几何对象进行分层划分

查询时：

• 从树的顶部开始，逐级检查光线是否与节点的包围盒相交

• 若不是，则跳过包围盒内的所有几何对象

• 大大减少需要进行精确交叉检查的几何对象数量

层次包围盒 (BVH) 包含两种节点：

• 叶子节点：包含一个图像基元列表

• 中间节点：通向多个图像基元列表 (即多个叶子结点) 的代理，存储子树中所有图像基元的包围盒

层次包围盒的构建

构建层次包围盒的启发式规则

启发式规则 1：总是选择节点中最长的维度划分

启发式规则 2：在中间基元的位置划分

终止划分的规则：当节点包含合适数量的图像基元 (比如 5 个)

优化基于 BVH 的几何查询

1. 尽早终止查询

2. 更好的 BVH 结构

一个好的划分应尽可能减少在树中找到与光线最接近的图像基元的开销。

如何衡量划分的质量？

实现分区

其他图像基元划分方法

• 基于图像基元的划分：

  • 将节点的基元划分为不相交的包围盒（包围盒在空间上可能重叠）

  • 比如层次包围盒

• 基于空间的划分

  • 将空间划分为不相交的区域（同一个基元可以包含在空间的多个区域中）

  • 比如均匀空间划分，KD树

均匀网格划分

优点：实现简单

缺点：对于大部分场景，网格中大多数单元格都是空的，适合大量图像基元在大小和空间上分布均匀。均匀网格无法适应场景中非均匀分布的几何物体，比如具有高分辨率的物体（包含大量图像基元）仅分布在空间中的一小部份。

KD树划分

不同加速结构的比较