光线追踪Ray Tracing(2)（笔记）

---

前言

本篇的内容是光线追踪的加速方法。

---

四、Uniform grids

预处理(Pre-Processing)——构建加速网格

1.找到场景包围盒。2.创建网格。3.将场景中的每个物体存入重叠的格子中，也就是将于物体表面相交的格子标记出来。

求光线-场景相交

我们首先假设，光线与格子相交相对于与物体相交的效率更高。我们按照光线的寻访顺序将与光线相交的格子再标记出来。然后测试同时与光线和物体相交的格子中，光线与物体是否相交。

格子的分辨率

格子不能太稀疏也不能太密集。人们根据经验总结得出以上公式。

Uniform Grads的利弊

对于上述方法，当处理物体分布均匀的场景时。带来的性能提升比较明显。

对于场景中物体分布比较稀疏的场景，比如类似“运动场中的茶壶”这样的场景，拥有大片留空的场景，效果就很不好。因为会进行大量无用的计算。

五、空间划分Spatial Partitions

空间划分的思想是，识别空间中比较空旷的区域，采用不同大小的网格。

不同的空间划分示例

八叉树(Oct-Tree)：二叉树是一个节点有两个子节点，八叉树就是一个节点有八个子节点。
八叉树空间划分将一个三维空间切成八份(上图用二维空间演示所有是四分，不要奇怪)。再将切出来的子空间再切成八份。直到出现某些子空间不再包围物体，或者该子空间如果再切的话其中七个子空间都不再包围物体，或者子空间已经很小了（我想说的是，切到什么程度有不同的标准）。
通过上述切割方法，我们将原本的空间划分成若干大小不均匀的空间。
八叉树有个问题，如果我们不是在三维空间中使用空间划分（游戏应该用不上），而是在更高维的空间中使用，比如说四维空间，那就不是八叉树了而是十六叉树。

KD-Tree：KD-Tree和八叉树有点相似，但是KD-Tree会在一个格子中，沿着x，y或者z轴，找到一个特定的位置，再在这个特定位置沿着特定轴划分空间。

BSP-Tree：相较于KD-Tree，BSP-Tree不再局限于沿着x，y，z轴，而是沿着任意方向划分空间。但是还记得之前提到过的吗？AABB之所以要沿轴是因为沿轴的公式相对简单。所以KD-Tree在性能上要优于BSP-Tree。

KD-Tree预处理

该怎么做，之前已经说了。需要再提一句的是，对于KD-Tree分割完毕的实际物体信息，我们只需要存储到叶子节点就行了。

用于存储KD-Tree的数据结构

那么如何存储KD-Tree。对于中间节点我们需要保存切割轴，切割点，以及切割后的子节点。不需要保存物体信息。
对于叶子节点，我们需要存储实际的物体信息。

KD-Tree的遍历(Traversing a KD-Tree)

当光线穿过叶子节点时， 计算与该叶子节点中的物体的交点。当不是叶子节点时，遍历到下一级。

六、物体划分与层次包围盒(Object Partitions & Bounding Volume Hierarchy, BVH)

BVH的原理

将一个场景中的物体(三角形)组织成两部分，再分别求他们的包围盒。

接着，对划分之后的两部分再进行划分，再分别求包围盒。
可以看出，BVH解决了KD-Tree单个几何结构会出现在多个子节点的问题。但是BVH自己也有一个问题，那就是包围盒可能重叠，如上图出现的情况。所以BVH的物体划分是一门学问。

BVH的构建

选择一个维度(x, y, z)来进行划分。

技巧1：总是选择节点中最长的轴来进行划分，假如是一堆物体在空间中占了一个长条，也就是在某个轴上占的越多，那么就划分这个轴。
技巧2：在中间的物体那里将物体分成两部分。这样能保证分出来的两部分包含的物体数量差不多。在数据结构中，这样的结构更利于查询。具体做法可以根据物体在轴上的位置进行排序来得到中间的物体。

当划分后的节点中物体数量很少（比如小于5个）时，就不再进行划分。

BVH的存储数据结构

中间节点只存储包围盒，和子节点指针。叶子节点存储包围盒以及其中的物体。和KD-Tree的数据结构相似。

BVH的光线求交算法

上图为BVH节点和光线求交的伪代码。如果节点为叶子节点，我们就需要将光线和叶子节点中的物体再求交。如果节点为中间节点，也就是光线确实打到了Bounding Box的同时打到的不是叶子节点，那么我们需要递归计算该中间节点的两个子节点和光线的相交。

空间划分与物体划分的比较(Spatial vs Object Partitions)

空间划分划分出的空间不会重叠，但是一个物体可能被划分到多个空间。物体划分划分出的空间可能会重叠，但是一个物体只会被划分到一个空间。事实是，空间重叠带来的问题并不大。

课程的最后

接下来的内容为辐射度量学。