RT(光线追踪)

光线追踪应该算是终极显卡杀手了，尽管拥有高端的画质，但是对性能的要求实时渲染的领域始终是望而生畏。不过，很多全局光照的算法都是基于光线追踪的基础上简化而来的，了解光线追踪还是有必要的。

1.光线的描述：

r(t) = o + t d，o是起点，d是单位方向向量，t是时间也可以说是变量，r(t)就是射线。

2.光线和物体求交：

光线和物体的交点，就是这根光线的可见点。如果物体的表面由隐函数F(x, y, z)=0表示，这个F是个通用的符号，例如如果物体是个球，则：

x2 + y2 +z2- r2 = 0，代入x，y，z的值

 (Ox+t*dx)2+(Oy+t*dy)2+ (Oz+t*dz)2 - r2 = 0，求出t值，找出近交点。这种求交方式如果不进行处理，每一根光线都得跟场景中所以物体进行就交，这样就没法玩了。

3.场景结果优化：

4.光的分布：光关于对倾斜面的cosine衰减和距离平方的反比衰减，这个是点光源的。

5.可见性：判断光是否被遮挡了，在光与点之间建立一条射线，对所有物体进行碰撞。如果，有碰撞判断碰到的点与光源，那个离渲染点近。

6.镜面反射：镜面反射的是物体也不是光源，要做到这种效果，就必须在渲染点上向多个方向发出射线，而不是仅仅往光源的方向发出射线。

7.传播介质：由于介质也会对光造成一定的影响，甚至是改变光的方向，例如大气散射之类的。

总结：光线追踪的原理是比较简单的，但是在运用上算法的效率不具备收敛性，这是它很难适应市场的主要原因。动不动为了求交就来个全场景遍历，即便是增加了场景管理等优化措施也是很消耗的，再者为此增加了场景管理的负担。可见，光线追踪就是一个华丽的负担。

尽管如此，却依旧可以尝试，简化，把算法简化到效率和效果都可接受的范围，谁如果能够在效果上找到折中的点，谁就是赢家。

目前光线追踪比较成熟的技术还是在CPU端实现的，因为这个设计到使用包围盒之类的东西简化计算的问题，当然空间划分也是其中一部分。

2.基于KD-Tree的场景空间划分：

光线跟踪渲染的主要运算操作耗费在光线与场景求交的过程中，而对空间的划分可以防止不必要的遍历，从而减少浪费。当前主要使用的空间划分技术有基于空间划分的均匀网格，八叉树，KD-Tree等，效果较理想的是KD-Tree。

KD-Tree的优点：

1.KD-Tree是一种特殊的BSP树，它将BSP划分中的任意分割平面退化为轴对齐的分割平面，这样就降低了BSP生成时的几何体元分割操作。但是它却同样具有BSP树的优良特征，即一定程度上的启发式空间划分，这样可以使得到的最终划分二叉树尽可能地平衡，这样就降低了最坏情况下的光线与划分结构之间的求交次数，进而提升的效率。

2.由于KD-Tree是一种二叉树，因此在遍历的时间就要比八叉树等非二叉树的划分结构更简单，这也推广了它的使用范围。

3.最后，很重要的一点是由于二叉树遍历的简易性可以使它们比较容易移植于不支持堆栈递归结构的GPU之中。

KD-Tree的创建：

KD-Tree的创建过程是一个自顶向下的递归过程，从根结点开始执行向下的空间划分，空间划分过程中最主的操作就是对分割平面的选取。分割平面是轴对齐的，然后在此基础上对分割面进行定位，定位的基本原则是得到的tree尽量平衡，也就是分割面两边的几何体元(三角形)最好一样多。

针对于分割时，分割面可能与三角形体元有三种关系：与分割面相交，在分割面左边，在分割面右边。分割面相交时可以选择对体元进行分割，也可以把其算做某一边，一般选择后面这种处理方式来简化计算。

在确定分割平面位置的时候，使用体元的AABB包围盒在分割平面法向量上的位置来作为分割平面的潜在位置。这样的好处是分割面潜在位置被确定，接下来只需要选择最优的潜在位置即可。

创建KD树主要的工作是确定分割面，在分割面的选取上，是直接把体元在分割面法向量上的位置作为潜在位置。这里需要注意的是，每一个AABB包围盒会确定两个潜在点。

叶子节点的确定，有两种方式，一种是当节点里面的体元数到达一定数量的时候，确定为叶子节点。一种方式是分割的层次到达一定的程度后，确定为叶子节点。

细节优化：1.在创建KD-tree的时候，前面几个级别使用均匀分割，因为体元多使用精确的分割会占用大量计算的时间。当体元数量达到一定数值的时候，使用精确分割来减少tree的不均匀。2.将KD-Tree信息、场景原始几何数据，分别归类存放于不同纹理之中，通过纹理参照在需要进行同类型数据的访问。这样一方面可以利用纹理提供的虚拟cache提高数据访问时的效率，另一方面相关数据的打包存放又减少了相同数据的重复访问次数，减少了访问的延时。

KD-Tree的遍历：

在CPU中tree的深度遍历可以用堆栈进行很好的解决，但是GPU中无堆栈。在遍历的时候，需要解决两个问题，一个是子遍历完要回到父，另一个就是对遍历过的子要设置一个已遍历的状态来进行描述。

总结：光线追踪就两个重点，一个是场景的管理，另一个是求交和光照计算。光线追踪算法本身并不复杂，只是效率不高而已。其中，使用KD之类的场景管理，嵌入到GPU时并不是太容易，需要使用更通用计算的API来实现，DX11是不行的。