games101-14-Ray-Tracing2

​ 如果整个场景只有一个极其复杂的单一人物模型，那么只对这一个物体做包围盒的话，相当于对效率没有任何提升。如果整个场景充斥着大量的细小模型，如草，花之类的，每个模型可能只有很少的面，如果此时对每个物体求包围盒，得到的包围盒数量会相当之多，对于光线追踪效率来说效率提升有限。基于以上两点考虑，AABB并不应只局限于以物体模型为单位，因此如何更好的划分场景形成不同的AABB，使得划分之后的AABB能够更好的加速光线追踪，就是接下来要考虑的问题关键。

均匀空间划分

（1）对所要考虑的场景找一个包围盒：

（2）在光线追踪之前，均匀用小格子划分这个大包围盒（相当于把场景均匀划分成更小的AABB包围盒）：

（3）标记出与物体表面相交的格子(不包括物体内部)，存储物体模型信息:

（4）根据光线的方向与判断出所有与光线相交的格子(这一步可以利用bresenham算法，如对于朝右上方的光线，光线经过的下一个格子为当前格子的右边或者上边的格子，求交点找更近的格子)，倘若格子还与物体表面相交，就说明光线可能会和物体相交，再进一步将光线与格子中的物体模型或是三角形面求交。

问题1：小格子的大小

​ 在该方法中，更多的计算是光线与AABB包围盒（小格子）而不是物体，通过包围盒把计算的三角形面限制在更小的范围内，所以某种程度上可以加速计算。但是格子的大小也会影响计算速度。在极端情况下，假如格子的大小为1✖1,相当于没有进行划分。如果格子太过密集，要计算的小格子很多，也会影响计算速度。较好的划分程度为格子数=C✖物体个数，在3维情况下C的值一般取27。

问题2：均匀划分场景引发的问题

​ 如果说场景较为空旷，物体较小且分离得比较开，那么均匀分割的效果就会很差了，因为会有很多无效的方格与光线的求交过程。例如对于一个空旷的操场，操场中间放置了一个茶壶，光线到达茶壶之前，需要计算光线和很多空格子求交过程。因此空旷的地方不适合划分太多小格子，用大格子快速跳过空旷位置的计算。均匀划分的方法适合的场景是空间中均匀布满了三角形面，如下图这种场景，物体多的地方适合划分更多的小格子，将需要计算的三角形面限制在更小范围，如果格子太大，就需要将光线和更多的三角面求交：

如下是其他划分方法：

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

（2）KD-Tree，每次将空间划分为两部分，且划分依次沿着x-axis，y-axis，z-axis交替进行，使得空间划分相对均匀，终止条件与八叉树类似。

（3）BSP-Tree，其与KD-Tree类似，唯一不同的是划分不再沿着固定一轴，可以任意方向划分，缺点是划分的空间没有规则性，对比于AABB来说，求交困难。

KD-Tree空间划分

​ 如下所有操作都在光线追踪之前，对场景预处理，以2维为例。

​ 先将整个场景放在包围盒中，将空间分为两部分：

​ 对左右两个子空间换个方向再分为两部分(这里只画出了右半部分，其实左边也是一样)，之后以此类推进一步分割，形成KD-tree。

（1）依次沿着x-axis,y-axis,z-axis划分，使得空间被划分的更加平衡
（2）划分的位置由空间中三角面的分布决定，具体细节不展开
（3） 叶子节点存储对应空间的所有物体或三角面信息，中间节点仅存储指针指向两个子空间
（4） 当划分空间太小或是子空间内只有少量三角形则停止划分

​ 对于一条光线，第一步判断光线是否与最外层的包围盒相交，如果相交进一步判断是否与对应的两个子空间相交：

​ 因图中做了简化，最大包围盒的左半边并没继续进行划分(实际上应该要划分的)，所以左半部分对应的1号空间是叶子节点，如果光线与之相交，进一步判断与存储在叶子节点的物体求交。

​ 左半边判断完之后，接着判断右半部分，如果对于右半部分存在相交情况，则对于右半部分的所有子空间，递归的执行这个步骤即可：

​ 利用KD-Tree的结构来对空间划分AABB包围盒的好处是倘若光线与哪一部分空间不相交，那么则可以省略该部分空间所有子空间的判断过程，提升了效率。缺点是判断包围盒与三角面的是否相交较难，因此划分的过程不是那么想象的简单，其次同一个三角形面或物体可能被不同的包围盒同时占有，不同包围盒内的叶节点会同时存储这一个三角形面或物体。

BVH物体划分

​ BVH与前几种方法最显著的区别就是，不再以空间作为划分依据，而是从物体对象的角度考虑，即三角形面（物体）。作业中的实现方法如下：

​ 第一步同样找出场景的整体包围盒作为根节点。该包围盒需要包围住所有物体对象的包围盒（每个物体对象自己也有包围盒）:

​ 第二步找到合适的划分点，将最大包围盒内的三角形面分为两部分，再分别重新就算新的包围盒。关于找到合适的划分点：划分顺序可以按照xyz轴。不过为了划分均匀，也可以每次划分一般选择包围盒最长的那一轴划分，假设是x轴，n个物体对象从左到右，找到中位数的物体对象进行左右划分（对于x轴，将物体对象包围盒中心坐标按照x排序，找到中间的物体对象），如此便能保证划分的左右两边物体对象数量尽可能差不多。（也可以直接将轴分成左右两部分，坐标小于轴中点将其划分到左边）

​ 注意到这里，包围盒会重叠，但一个物体对象只会被存储在唯一的包围盒内，而这也就解决了KD-Tree的缺点。接下来与KD-Tree的建立类似，递归的对所有子空间重复该步骤（如何划分使得重叠部分更少很有讲究），当叶子节点物体对象个数足够少停止（一般≤5）。

​ 如果不是叶子节点，需要记录指向左右子节点的指针以及自己的包围盒。如果只剩下一个物体对象，则生成叶子节点，叶子节点需要除了上述信息还需要记录物体对象信息（以叶子节点中一个物体对象为例）。如果只剩下两个物体对象，为当前节点生成两个叶子节点即可。

​ 之后判断光线与包围盒求交的步骤同KD-Tree。BVH不需要判断包围盒和物体对象的关系。判断过程如下：

1、当前节点所代表的大的包围盒与光线无交点：则不用计算左右子树。返回空交点。

2、当前节点所代表的大的包围盒与光线有交点：如果为叶子节点，计算包围盒内部的物体对象与光线的相交情况；如果还有左右子树，则递归处理左右子树。

计算包围盒内部的物体对象与光线的相交情况:

例如，当一个物体非常复杂，比如进行模型加载。在加载模型时，需要将网格模型变成多个三角形对象。将这些三角形作为物体对象，构建新的bvh树。计算包围盒内部的物体对象与光线的相交情况前，先计算光线和物体的bvh树，如果到达叶子节点，就是光线和三角形求交。

最后得到的应该是与该光线相交的最近的交点及物体信息。

使用SAH进一步加速BVH

当物体/三角形分布不均匀的时候，上面将轴分成两半/将物体个数分成左右两半得到的划分结果会变得很差。例如在左边有大量物体，右侧只有一个。如下左侧是按照原始方法划分的结果。由于划分时要尽可能减少划分后两部分包围盒重叠的体积，因为重叠的体积越大，光线穿过重叠区域的可能性越大，遍历两个子树的可能性就越高，计算消耗越多。所以原始划分方法是在物体跨度最大的轴上进行划分。结合物体分布不均匀以及尽可以减少重叠面积两个问题，新方法采用基于表面积的启发式评估划分方法。如右侧。

该方法通过对求交代价和遍历代价进行评估，给出了每一种划分的代价，而目的是去寻找代价最小的划分。假设当前节点的包围体中存在 n 个物体，设对每一个物体求交的代价为 t(i) ，如果不做划分依次对其求交则总的代价为：

如果这些物体划分为2组，这两组物体分别处于它们的包围盒A和B中。设光线击中它们的概率分别为 p(A) 和 p(B) 。p(A)的概率等于A包围盒大小/包含AB的大包围盒大小；p(B)的概率等于B包围盒大小/包含AB的大包围盒大小。AB并不一定会填满其父节点的包围体，并且AB可能存在重叠，因此 p(A) 和 p(B) 的和不一定为1，且它们的和越大说明 A 和 B 的重叠程度越大。综上所述，当前节点求交的代价可以写为

其中 ttrav 表示遍历树状结构的代价。一般来说，假设对所有图元的求交代价是相同的，可设 t(i)=1 ，又遍历的代价小于求交的代价，可设 ttrav=0.125 。设包围盒A中图元的个数为 a ，B中图元的个数为 b ，则：

光线击中包围盒的概率可以根据包围体的表面积来估计，即在父节点的包围体C中，A和B的表面积越大它们被击中的概率也就越大，设 A ， B 和 C 的表面积为 S(A) ， S(B) 和 S(C) ，则有：

辐射度量学Radiometry

​ 在Blinn-Phong模型中，光的能量用常数I表示，没有单位和一个准确的定义。该模型在计算高光的时候，只考虑是否能看见高光，不考虑实际接收到的能量，即光线方向和法线的关系。whited-style的光线追踪模型中，认为所有反射都是完美镜面反射，对于漫反射的光线没有进行追踪，直接用当前点的颜色。并且光在多次折射和反射中会有能量损失，能量损失的值是自定义的。

（1）Radiant Energy:光源辐射出能量Q[J]

（2）Radiant flux:单位时间内光源辐射出的能量（时间越长能量越多，在辐射度量学中考虑单位时间的性质）光源包含的各种波长（对应一种颜色）的能量。 即如下函数的总面积。计算机图形使用RGB作为辐射通量表示的简化。

（3）Radiant intensity：单位时间光源在单位立体角（某个方向）上辐射出的能量

​ 弧度制，数学术语，指用弧长与半径之比度量对应圆心角角度的方式。用符号rad表示，读作弧度。等于半径长的圆弧所对的圆心角叫做1弧度的角。由于圆弧长短与圆半径之比，不因为圆的大小而改变，所以弧度数也是一个与圆的半径无关的量。（圆周长2 πR，面积 πR^2）整个圆的弧度为2 π。

​ 对应在三维上的球的弧度(立体角)的计算方式如下，立体角度所对应球上的投影面积比上半径的平方，整个球的立体角为4 π 。（球表面积 4πR^2）（投射到单位求上截面的面积。可以当作一个带有体积的方向。）

​ 利用微分立体角dw定义一个方向（就好比用一个浮点数定义一个时间），计算如下：通过θ,ϕ确定空间中一个方向，在这两个角度上分别增加一个微分值，其中rdθ 是微分面积元的高，rsinθdϕ 是微分面积元的宽，二者相乘是微分立体角在球面上的面积。用该微分面积除以半径的平方即为微分立体角的值。

​ 对dw在整个球上积分，积分结果为4π。

​ 对各向同性点光源，所有方向上的亮度都与方向无关，所以I是一个常数，因此对Φ积分时只用对立体角积分。最后推算出的I是一个常数。