14光线追踪（加速结构）

1.Uniform Spatial Partitions(Grids)—均匀空间划分

1.1场景预处理

1. Find bounding box
2. Create grid
3. Store each object in overlapping cells判断哪些网格可能有物体，有物体的格子做上特殊标记

1.2开始光线追踪

开始做光追→ 光线到有物体的格子 → 判断是否有交点

如果在一个小格子中既有物体又有光线，那么说明光线和物体可能有交点，就在这个格子里进行光线与物体表面的求交计算，否则就不会计算。那么我们怎么知道光线穿过了哪些格子呢？要一个一个进行求交计算吗？实际上是不需要的，这里其实可以用到光栅化直线的算法，如引入增量运算的Bresenham算法等，直接可以计算在光线在哪一个格子内，以及下一个格子是谁

1.3格子的划分

划分的如果太稀疏，假如不划分，只用一个大包围盒，那相当于没有加速结构，而如果划分的太密集我们又要多次计算光线与小网格的求交。而经过不断的尝试人们发现，划分网格的数量应该等于某一个常数C乘上场景中物体的数量。

1.4适用场景

大小、空间分布均匀的场景，不适用空旷的场景

2.Spatial Partitions—空间划分（KDtree）

Oct-Tree(八叉树)，KD-Tree(KD树)，BSP-Tree(二叉空间划分树)。这里主要介绍KD-Tree，原因是KD-Tree在高维仍然很好用，而像八叉树在二维空间中是四叉树，三维空间是八叉树，更高维的空间就变成了2的n次方叉树。而BSP树，在二维空间我们是用线划分，三维空间用平面划分，而高维空间我们则需要用超平面划分，也很麻烦。而KD树的做法是各个维度按顺序依次划分，先对着x划分，然后y，然后z，然后再xyz，如果更高维度就变成xyzw循环，每次对空间划分只划分两个区域。

KD树也是在我们做光线追踪前对包围盒的预处理。与此同时，中间节点A,B,C,D并不存储任何对象，而对象物体都存储在叶子节点中。中间节点存储划分的轴以及划分的位置，以及它的子节点

在预处理完包围盒之后，我们就可以对划分的区域进行求交了，

先对A求交，发现与A有交点，那么就要对A的子节点也进行求交，因为1没有继续划分，所以对1内的物体进行求交，再对B节点求交，然后沿着子节点依次这么做，最后对C节点的子节点3内的物体求交时成功找到了光线与物体的交点。

当然KD-Tree也有它的问题，例如，我们怎么判断一个立方体格子和一个三角形求交。其次一个物体可能会被存储在很多不同的格子里，这显然加大了复杂程度。
?

3.Object Partitions & Bounding Volume Hierarchy(BVH)—对象分区&边界体积层次

BVH是直接根据物体划分。首先为场景找到一个包围盒，将这堆三角形尽量均匀的分成两部分，然后重新为这两部分设置包围盒，然后重复前面两步的操作，直到最后每个包围的三角形趋近于一定的数量。用这种方法我们同样可以建立起一个树结构，同样中间节点只存包围盒与子节点的指针，只有叶子节点存储物体。而且有效避免了KD-Tree中一个三角形出现在多个节点中的问题。

当然BVH也有它的问题，如这些重新划分的包围盒之间会有重合，当然重合的影响并不是致命的，只要划分的重合度导致的误差过大不至于发生错误。所以怎么划分也是一个很重要的问题。

为了均匀划分，我们通常每次都沿着最长的轴划分，从而保证包围盒不过于“细长”或者“矮扁”。

如何把物体分成两半呢？人们通常取处在中间位置的物体来划分，这样可以保证两部分的物体数量差不多，也就可以使得构建的树结构的最大深度最小，也就是树两个叉的深度平衡。而这本质是一个取中位数的问题，在n个数中快速取得第i大的数实际上是一个快速选择算法，时间复杂度是O(n)。当每个节点的涵盖的三角形数量是五（假设）的话，就停止划分。

BVH的数据结构

光线与BVH求交的伪代码，原理和KDtree差不多，如果与父节点有交点，则递归计算与其它两个子节点的求交，如果与子节点有交点则计算光线与叶子节点内物体的求交，

KDtree与BVH的比较

最后做一下比较，对于KD-Tree，它是对空间划分，并且一个物体可能被存储在不同的区域。而对于BVH，则是对对象进行划分，并且它们重新划分的区域可能会重叠。