包围体(Bounding Volume)

使用包围体可以简化很多计算，当光线没有与某物体的包围体相交时，那就没必要去计算光线是否与该物体的所有面相交了。

轴对齐包围盒AABB

AABB(Axis-Aligned Bounding Box)，是由三对平面的交集构成的包围盒，任意一对平面都与x、y或z轴垂直，因此是轴对齐包围盒：

以2D的AABB为例，进行光线与包围盒的求交：

1. 求出光线和两个x平面的交点，然后把先进入的(偏小)记为，后出去的(偏大)记为；

2. 求出光线和两个y平面的交点，也记录和，这里是负的没关系，表示反向传播与对应平面的交点；

3. 找到真正与包围盒的交点，，如最右图所示。

4. 验证和的合法性，如下图：

AABB可以使得计算更加简便，我们计算平面与光线的交点只需要一次减法一次除法即可：

空间划分(Spatial Partitions )

AABB并不应只局限于以物体模型为单位，可以更加精细的考虑到以三角面为单位。另外对于场景的许许多多包围盒来说应该要有一种数据结构将其统领起来。 因此如何更好的划分场景形成不同的AABB，使得划分之后的AABB能够更好的加速光线追踪，这就是接下来要考虑的问题关键！

均匀空间划分(Grids)

均匀空间划分是最简单的空间划分。该方法适合的场景就是空间中均匀布满了三角形面，例如：

首先要进行场景的预处理，基本步骤如下：

1. 对要考虑的场景找一个包围盒：

2. 用小格子均匀划分这个大包围盒：

3. 在每个与物体表面相交的小格子上存储物体模型信息：

然后就能做光线追踪了，可以利用Bresenham算法来判断与光线相交的方格，如果格子中存储了物体模型/三角形面信息，再进一步进行光线与表面求交的操作：

格子划分程度也和加速效率有关，太少无效率，太多却拖累效率，人们通过总结如下：

用一个常数C乘上场景中的物体数就行。

八叉树空间划分(Oct-Tree)

每次将空间分为8个相等的部分，再递归的对子空间进行划分，因为图中是2维例子，所以只划分了4部分。当划分的子空间足够小或是空间中三角形面的数量很少的时候会停止划分。这种方法的显著缺点是，随着维度的上升划分的空间数量会呈指数级增长。

KD-Tree空间划分

每次将空间某个值划分为两部分，且划分依次沿着x-axis，y-axis，z-axis，即如图中所示，第一次横着将2维空间分为上下，第二次再竖着将上下两个子空间分别划分为左右部分，依次递归划分，终止条件与八叉树类似。

需要按照如下规则，使用KD树进行空间划分：

1 依次沿着x-axis,y-axis,z-axis划分，使得空间被划分的更加平衡

2 划分的位置由空间中三角面的分布决定，具体细节不展开

3 叶子节点存储对应空间的所有物体或三角面信息，中间节点仅存储指针指向两个子空间

4 当划分空间太小或是子空间内只有少量三角形则停止划分

（为了方便展示，只划分了一半）

划分好空间后，就能进行光线追踪了。仍以上图为例，一般步骤如下：

1. 判断光线是否与最外层的AABB相交：

2. 如果相交了，进一步判断是否与它的两个子空间相交：

   首先是左边的1号节点（这里做了简化，没有继续划分）：

   然后是右边的B节点：

   发现也有相交，于是继续判断B的两个子空间……

3. 重复上述步骤，直到和某物体相交：

使用KD-Tree可以省略一些计算，提高光追效率，但判断包围盒与三角形面是否相交很困难，并且一个物体也可能存在两个包围盒里，造成重复判断。

BSP-Tree空间划分

对空间二分，与KD-Tree类似，唯一不同的是划分不再沿着固定一轴，可以任意方向划分，缺点自然是划分的空间没有规则性，求交困难。

这些技术在业界之中以及逐渐不再被多使用，但依然有很多借鉴参考价值。

包围体分层(BVH)

BVH(Bounding Volume Hierarchy)，与前几种方法最显著的区别就是，不再以空间作为划分依据，而是从物体本身的角度考虑，即三角形面，基本过程如下：

1. 将场景整体的包围盒作为根节点：

2. 将内部三角形分成两部分，再分别求包围盒：

3. 重复以上步骤，满足最终划分条件（可以是一个包围盒里最多5个三角形）为止：

   (这里为了方便展示，只划分了左半部分的)

划分规则

每次划分一般选择最长的那一轴划分，假设是x轴，那么划分点选择所有三角面的重心坐标在x坐标上的中位数进行划分，如此便能保证划分的三角形左右两边三角形数量尽可能差不多，让树结构平衡，提高效率。

数据结构

伪代码

SAH(Surface Area Heuristic)

由于BVH存在着包围盒重叠的问题，若一个空间中物体分布得很不均匀时比如右边存在大量物体，而左边只有少量物体，此时使用BVH就会得到很差的划分结果。

（待补充）

参考资料

• GAMES101-现代计算机图形学入门
• 计算机图形学十三：利用包围盒技术加速光线追踪（KD-Tree and BVH） - 知乎 (zhihu.com)