光线追踪及其加速结构
（1）为什么会有光线追踪（Ray Tracing）？
光栅化不能很好地表现全局的效果。如软阴影、⽑玻璃效果、间接光照。光线打到⼀个物体，然后反射打到另⼀个物体，然后打到⼈的眼睛。如窗外的光打到地板上，漫反射⼜打到墙壁上，漫反射⼜打到任何位置上，不断地弹射最后才打到⼈的眼睛⾥去。光线在到达⼈眼之前弹射不⽌⼀次。
光线追踪⾮常慢
⼀帧就需要花费 1 万个 CPU ⼩时。
光线（Light Rays）的定义
光线沿直线传播的；两个光线各传播各的，不会发⽣碰撞；光线从光源出发到达我们的眼睛（光路可逆）。“当你凝视深渊，深渊也在凝视着你”
光线投射（Ray Casting）
根据光路距离判断阴影，之前说过。
光线总要考虑与场景中最近的点
并且该点与光源之间不能有物体阻挡。⿊⾊的箭头是在这⼀点的法线。
有了法线、⼊射⽅向和出射⽅向，就可以计算这⼀点的着⾊。就可以写⼊屏幕上这个像素的值。
然后就可以得到和光栅化近似相同的结果
（2）Whitted-Style 的光线追踪
Whitted-Style 的光线追踪可以做到如下效果：光线打到某个物体上，折射近玻璃球，⼜折射出来打到⼈眼睛。这根光线就弹射了好多次。当年（1979年）渲染这幅图需要 74 分钟，2006 年的个⼈电脑只需要 6 秒，2012年的 GPU 只需要 1 / 30 秒。
那么是如何做到的呢？
光线打到⼀个玻璃球，有⼀部分能量要被反射掉：
有⼀部分要被折射进去，并且可以继续传播：
由于光线弹射次数多了，我在每⼀个点都要去计算着⾊的值。
如果我的光源可以照亮任何⼀个弹射的点，那我就把我算出的着⾊的值最后都给加到那⼀个像素的值⾥⾯去。
定义不同的光线类型：
（3）光线打到物体表⾯的交点怎么求？光线的⼏何定义：
定义：球上的任何⼀个点 p 到球⼼ c 的距离，都等于半径 R。点 p 既在光线上，⼜在球上，那这两个⽅程都要满⾜。
⽅程中不知道的是 t，即传播多久能打到这个位置。可以解出这个公式：
根据解的数量，有相离、相切、相交的情况。就可以解出不同的点。推⼴到光线和⼀般性的隐式表⾯的求交：
把 t 解出来，就可以得到光线与各种各样不同的隐式表⾯求交。对于显式表⾯怎么做？
交点数量是奇数则光线在物体内，交点数量是偶数在物体外。
判断光线是否和物体有交点，那就将三⾓形⼀个⼀个求交，可⾏但⾮常慢。
怎样求光线和三⾓形的交点。三⾓形肯定在⼀个平⾯内，先找到光线和这个平⾯的交点，再判断这个交点在不在三⾓形内。点在不在三⾓形内前⾯已经讲过。
可以⽤⼀个⽅向和⼀个点来定义平⾯
如何将平⾯上的任何⼀个点⽤ p' 和 N 表⽰？就像光线上的任何⼀个点能⽤ o + td 的形式表⽰。
满⾜ pp' 这个向量与法线 N 是垂直的，即可定义。展开了之后就是 ax + by + cz + d = 0，很显然这就是平⾯的⽅程。
⼜回到了刚才的做法，解出 t，下⼀步就是判断这个点是否在三⾓形内就可以了。但是⼈们是偷懒的，有没有⼀种办法我能⼀下解出光线与三⾓形的交点？Möller Trumbore Algorithm
⽤重⼼坐标描述的位置，只要这三个系数加起来等于⼀，我们就可以得到任意⼀个在这三个点所定义的三⾓形所在的平⾯内的点。所以等式右边就是⽤重⼼坐标表⽰的平⾯内的任意⼀个点。
因为向量都是在三维空间的，⼀个都有三个数，可以写成三个式⼦，有三个未知量 t、b1、b2，当然可以把它解出来。解出来就是根据克莱姆法则所列成的上述式⼦。
我怎么知道解出来的就是在三⾓形内呢？三个系数都要是⾮负的，即直接通过重⼼坐标就可以定义点在三⾓形内。
把每个三⾓形都与光线求交，速度很慢，我们怎么把速度提上去？
像下⾯的场景就绝对不能⽤上⾯最原始的⽅法来做：数千万个三⾓形
（4）加速结构
包围盒（Bounding Volumes）
Axis-Aligned Bounding Boxes（AABB）⽤⼀个相对简单的形状将⼀个复杂的物体包起来。
有⼀个简单的概念，如果光线连包围盒都碰不到，那就更不可能碰到包围盒⾥⾯的物体了。
长⽅体就是由三个对⾯形成的交集：前后、左右、上下
如何判断光线和包围盒是否有交点？先看⼆维上怎么做
对于两条竖直的线，在什么时刻会有交点；对于两条⽔平的线，在什么时刻会有交点。对于任何⼀个对⾯，我都可以求出光线进去的时间和出去的时间。那么对于这个盒⼦来说，我是什么时候进⼊和什么时候出去呢？即对这两个线段求了⼀个交集。可以直接拓展到三维情况：
那么什么时候有交点呢？如果进⼊的时刻⼩于出去的时刻就有交点。
如果 texit < 0，那么包围盒在光线的背后；如果 texit ≥ 0 并且 tenter < 0，那么光线起点就在盒⼦内。iff 是当且仅当（if and only if）。
为什么要“轴对齐”？⽅便计算：
利⽤光线对包围盒求交来加速光线追踪
对包围盒的预处理完成。⼀束光线射进包围盒，判断光线是否有可能与格⼦内的物体有交点。只要做若⼲次光线与盒⼦的求交，可以避免与场景中的所有物体求交。
先看看划分成⼀个格⼦，没有任何加速的意义。
格⼦太密集了，就要做好多次光线与格⼦的求交，效率就下去了。
只要知道这⾥有⼀个平衡就可以，格⼦不能太稀疏，也不能太密集。
在这个场景中，各个地⽅都有⼏何的物体，分布就⽐较均匀，⽤格⼦的效果就⽐较好。
⽽对于这个场景，空的地⽅太多了，物体分布挺不均匀的，就不适合⽤均匀的格⼦来解决问题。
空间划分（Spatial Partitions）
这个问题当然并不是最早从图形学上产⽣的。
Oct-Tree（⼋叉树）：把整个场景先想办法包起来，然后把这个包围盒切成⼋份，因为它是空间中的包围盒，类似⼀块⾖腐。⼋叉树在⼆维情况下其实是四叉树，对每⼀个⼦节点，然后⼜把它切成四份，图上只把⼀个地⽅继续进⾏切份，其实其他的地⽅同样要继续进⾏下去。到什么时候停⽌呢？⽐如我可以定⼀个规则，当切成四块后有三块都与物体不相交。也就是说，停下来是取决于各种不同的标准。但是⼈们不喜欢⽤⼋叉树，因为它和维度绑定了，三维情况下是⼋叉树，思维情况下就是 24 = 16 叉树。
KD-Tree：每次只沿⼀个轴把它砍开，就砍⼀⼑。⽐如先⽔平⼀⼑，形成了上下两块，我再在两块分别竖直⼀⼑...三维情况下就是沿着 x、y、z 三个轴⽤平⾯砍开。
BSP-Tree：对空间进⾏⼆分的⽅法。每⼀次选⼀个⽅向进⾏划分，速度肯定赶不上 KD-Tree。并且它在维度⾼的时候仍然越来越不好计算的问题，到了四维及以上就要⽤超平⾯进⾏砍开，越来越复杂。以 KD-Tree 为例
KD-Tree 的数据结构：只存储在叶⼦节点上
那么这个结构实际上应该如何做光线追踪的加速？⼀束光线射进包围盒
如果光线和某⼀个盒⼦没有交点，那什么都不⽤做，如果有交点，那我就知道光线和它的两个⼦节点可能都有交点，所以都判⼀下，直到光线打到叶⼦节点，就要和叶⼦节点⾥的所有物体求⼀次交。
但是 KD-Tree 有⼀些缺点：⽐如同⼀个物体会与多个格⼦相交，三⾓形和不同格⼦的交集很难判断。最近⼗年，⼈们就渐渐不⽤这个 KD-Tree 了。
通过物体来划分（Object Partitions），通过这种划分形成的加速结构称为 Bounding Volume Hierarchy（BVH）。这种结构得到了⾮常⾮常⼴泛的应⽤。在图形学中，不管是做实时还是离线光线追踪，⼤家⽤的都是这么⼀种结构。因为它解决了 KD-Tree 的这两个问题。
划分成两部分，分别去求⼀下它们的包围盒
不同的物体在不同的包围盒内，并且省去了三⾓形和各包围盒求交的过程。但是 BVS 并不是将这些包围盒严格划分开。
判断光线与 BVH 求交的伪代码：
空间划分和物体划分的⽐较：
