参考链接：真实图形学（光照模型）
其他参考：计算机图形学----DDA、Bresenham直线算法
https://wenku.baidu.com/view/3c1913bd83d049649b665844.html
和老ban 讲的差不多~可以做为总结啦
这里主要是——关于减小光线跟踪过程求交次数的几种方法：
（1）KDD算法
DDA（数值微分算法）算法是一个增量算法。增量算法：在一个迭代算法中，每一步的x、y值是用前一步的值加上一个增量来获得。
通过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。
DDA需要考虑所画直线的斜率k：
当 |k|<1 , x每增加1，y 增加k。
当 |k|>1 , y每增加1，x增加1/k。
（a）基本思想：
将景物空间剖分为网络，由于空间的连贯性，被跟踪的光线从起始点出发，依次穿越它所经过的空间网格，直至第一个交点，这种方法称为空间剖分技术，可以利用这种空间相关性来加速光线跟踪。
三维DDA网络跨越过程，根据d确定两组始面和终面，并得到最终终面，以此终面为下一个穿越立方格。算法对于稠密的场景，选取适当的空间剖分分辨率，可以使算法非常有效。
（b）方法：
景物空间均匀分割为一系列均匀的3维网格，建立辅助数据结构SEADS，确定后的SEADS结构中的每一个网格可用三元组（i,j,k）精确定位，均设立其所含景物面片的指针。光线跟踪只需依次与其所经过的空间网格中所含景物面片进行求交测试。
将直线光栅化的DDA算法推广到三维，来加速光线跟踪。
光线的方向向量V（V_{x},V_{y},V_{z}），主轴方向就是abs(V_{d}}=max(abs(V_{x}),abs(V_{y}),abs(V_{z}))。算法先将光线垂直投影到交于主轴的两个坐标平面上，然后对两投影线分别执行二维DDA算法。
（2）空间八叉树剖分技术
（a）基本思想
空间八叉树剖分技术是一种空间一个空间非均匀网络剖分算法，该算法将含有整个场景的空间立方体按三个方向分割成八个子立方体网络，组织成一颗八叉树。若某一子立方体网络中所含景物面片数大于给定的阈值，则为改子立方体进行进一步的剖分，直到面片数目小于阈值。
利用空间连贯性来加速光线跟踪。
八叉树的最大深度表示空间分割所达到的层次，称为空间分辨率。八叉树的深度为N，八叉树终节点的编码q_{1}q_{2}...q_{i}FF...F,q_{1},q_{2},...q_{n} \in {0,1,2,...7},i在[0,N]之间，F为异于0，1,...7的符号。由八叉树节点编码方式很容易找到空间任一点所在的空间网络单元。
（b）方法：
（3）包围盒及层次结构
（a）基本思想：
用一些形状简单的包围盒将复杂景物包围起来，求交的光线首先跟包围盒进行求交测试，若相交，则光线再与景物求交，否则，光线与景物必无交。
利用形状简单的包围盒与光线求交的速度较快来提高算法的效率。
（b）层次结构：
包围盒技术的一个重要改进是引进层次结构，其基本原理是根据景物的分布情况，将相距较近的景物组成一组局部场景，相邻各组又组成更大的组，这样，将整个景物空间组织成树状的吃呢该次结构。
（c）求交测试方法：
测试光线首先进入该层次的根节点，并从根节点开始，从上向下与各相关节点的包围盒进行求交测试。若一节点的包围盒与光线有交，则光线将递归地与其子节点进行求交测试，否则，该节点的所有景物与光线均无交，该节点的子树无需进行求交测试。
（4）自适应深度控制
在基本的光线跟踪算法中，结束光线跟踪的条件是光线不与任何物体相交，或已经达到预定的最大光线跟踪深度。事实上，对复杂的场景，没有必要跟踪光线到很深的深度，应根据光线所穿过的区域的性质来改变跟踪深度，来适应地控制深度。
