原理

Forward Tracing

当一束光照射在物体上，其反射的光子只有少数能到达我们眼睛。如果我们将光源发射的光线逐一进行模拟，进行成千上万次反射折射，直到计算出每一个像素点的每一道光，就可模拟出光线追踪的效果。这种方法被称为Forward Tracing，很显然，在复杂的环境中基本无法被实现，于是我们有了反向的Backward Tracing。

Backward Tracing

既然Forward Tracing很难被实现，我们可以从另一个角度来看这个问题：将光线视为从眼睛发出，当照射到物体上时进行反射折射，最终若回到某个光源，则说明能获得照明，若被遮挡则说明处于阴影之中。

算法

光线与场景求交

光线方程 $p(t)=e+td$ ，e为视点，d为光线向量。

球面方程 $(p-c)\cdot(p-c)-R^2=0$ ，c为圆心。

三角形方程 $p=\alpha+\beta(b-a)+\gamma(c-a)$ ，abc为三角形顶点。

光线与面方程联立即可求交点。

Whitted着色模型

I_\lambda=L_ak_aO_{a\lambda}+\Sigma_{lights}f_{att}L_{p\lambda}[k_dO_{d\lambda}(n\cdot l)+k_sO_{s\lambda}(r\cdot v)^n]+k_sO_{s\lambda}I_{r\lambda}+k_tO_{t\lambda}I_{t\lambda}

这个着色模型的前三项我们应该十分熟悉了，对应的是之前介绍过的环境光、漫反射以及镜面反射项。那么后面两项呢？

由于在光线追踪模型中，光线会在场景中进行多次的反射与折射，所以最后两项就是反射（reflected）与折射（transmitted）的 递归项 。

Shadow Ray

在光线追踪模型中，阴影的计算需要依托于反射光线与场景的碰撞。当前光线照到物体表面，进行反射，反射出的shadow ray若不会碰撞到场景中的任何物体，则说明最终能被看到，否则说明其为阴影。

图片来源网络

细节

空间加速

当我们在计算光线与场景的碰撞时，若用传统做法难免需要遍历所有物体，包括一些离得很远，明显不可能碰撞到的物体，这样造成了极大的资源浪费。所以在进行遍历之前我们一般将场景 均匀分割为网格 ，先判断光线与网格的判断，再对碰撞到的网格进行其中的物体碰撞。

但是，若物体的分布十分不均匀，比如说全部集中在一个网格内，那么我们采用这种方法不但要遍历每个物体，还得额外出遍历每个网格的操作，不但没有加速，反而减速了。于是我们又引入了 八叉树Octree （在二维空间即为四叉树）的做法：将空间平均分为八份，当子空间为空或物体个数较少时便不再细分。这样的分法可以减少无用网格的个数，从而优化遍历速度。

但是，八叉树也存在其局限性：每多一层分割深度，都会指数级地增加网格数，大大影响效率。于是我们又引入了 k-d树 ，k-d树每次以当前空间所有对象的中位数进行剖分，进行更为有效的分割，避免了指数爆炸的情况。

但是不论是使用八叉树或者k-d树，都可能存在一个物体隶属两个网格的情况。所以，我们又又又引入了 BVH（Bounding Volume Hierarchy，层次包围盒）树 ，直观来看就是用一个正方体将物体包围，基本类似于unity或cocos等主流游戏引擎中碰撞检测的碰撞包围盒。先剖分出大的包围盒，再对与光线碰撞的包围盒进行深层剖分。由于该结构允许区间重叠，所以不会出现一个物体隶属两个网格的情况。