光栅化的局限性
- 软阴影实现效果不好
- 尤其是当光线不止一次反射时
光线追踪研究前提
研究光线追踪的假设前提：
- 光线是沿着直线传播的
- 光线与光线之间是不发生碰撞
- 光线的可逆性。比如一条光线是从光源到物体再反射到眼睛中去，也可以说是从眼睛发出一条光线到物体表面再反射到光源中。
观测点的前提假设：
- 观测点眼睛是一个点一个位置
- 光源假设是点光源
- 光线打到物体上 产生的反射是完美的
zhen孔摄像机模型
- 摄像机（眼睛）射线通过了一个屏幕像素后，映射到某个物体上一个点
- 从光源射出一条光线连接该点，判断该线过程中有没有被遮挡，有则在阴影中，没有就亮
- 黑色箭头为该点的法线
- 有了这三条线，可以得到该点的渲染模型
Whitted-Style 版光线追踪
- 从眼睛射出一条线看到像素，映射到某个物体上的一个点
- 该点处发生了一系列的光线的折射和反射
- 再从光源出连接各个折射到物体上的点和反射到物体上的点
- 对每条光源到物体点的连线做 路径判断，判断该路径是否被遮挡
- primary ray: 从眼睛发射的线
- secondary rays:折射或者反射后的线
- shadow rays：从光源处连接各个物体表面的线
求光线与物体的交点
光线定义
- 光线有一个起点并且是一个向量
- 光线上任意一个点能用下面式子表示
光线与球的交点(隐式几何)
球体上一点到圆心
\[p:(p-c)^2-R^2=0 \]联立两式子得
\[(o+td-c)^2-R^2=0 \]-
t需要满足>0,因为光线是射线
-
可能得到0~2个交点
总结
- 光线上的点满足r(t)=o+td
- 几何表面上任意一个点满足 p: f(p)=0
- 光线相交几何表面，所以可以表示为 f(o+td)=0
光线与球的交点（显式几何）
-
根据一条光线与封闭几何的交点数量，可以得出该光源与几何的位置关系（是否在内部）。
-
若在内部只有奇数个交点，外部有偶数个交点。
-
简单的想法：判断每条光线与三角形的交点数量
-
简单，但是太慢了，每条面都要判断，每个像素也要总结合
简化流程
- 判断每个三角形太慢了，我们判断光线与平面的交点，因为三角形一定是在某个平面上
- 判断光线与平面得到的交点是否在三角形内
平面的定义
- 需要一个向量，该向量表示为平面的法线
- 还需要该向量上的一个点，确定该平面位于该向量的y轴位置
- p点是所求点，p’是平面上已知的某一个点
- N表示平面法向量，p-p'与法线N垂直 乘积为0
- 平面上任意一个点p都会满足上式子
联立方程可得
- 得到交点后 记得要判断 交点是否在三角形内**
- 为了想一次性得到交点并判断是否在三角形内，于是引入了下面这个算法**
Möller-Trumbore 算法
\[\vec{O}+t\vec{D}=(1-b_1-b_2)\vec{P_0}+b_1\vec{P_1}+b_2\vec{P_2} \]- 上式子表示为三角形的中用重心坐标表示的平面内任意一个点
- O+tD是光线上的一个点，联立后可得
光线与三角形面求交优化
- 上面提到的计算方式，在复杂的场景中计算会非常的缓慢。
- 例如：一个有10.7M个三角形的场景中，每一条光线都要与这么多三角形做计算，而且关系反射和折射不至一次，因此计算过程会非常复杂。
包围盒
- 定义一个长方体包围盒（AABB包围盒），是由三个不同的‘对面’组成的
- 如果光线没有击到包围盒那么物体也必然没有被击中
光线与包围盒的求交
2D包围盒
- 光线从o点朝d方向发射，时间为tmin时，与包围盒有了一次碰撞，tmax时间时出了包围盒
- tmin到tmax的时间为，光线在包围盒内的时间
3D包围盒中
- 只有当光线进入所有的每一‘对面’，则光线进入了包围盒
- 当光线离开了任意一‘对面’，则光线离开了包围盒
- 所以在三维物体中，当光线最后一次碰到包围盒即tenter=max｛tmin｝,时，光线才算进入了包围盒
- 如果tenter<texit,光线的进入时间小于离开的时间，则光线在包围盒中待了一段时间，说明光线与包围盒是有交点的
注意点
- 光线不是线，是射线，
- 要考虑物理意义当t(exit)，光线的离开时间<0,说明包围盒在光线的后面，是没有交点的
- 当t（exit）>=0光线离开时间大于0，且t(enter),光线进入时间<0，说明光线起点在包围盒内部，是有交点的
- 结论，当且仅当 t(enter)<t（exit）&&t(exit)>=0时，光线与包围盒有交点
加速光线与包围盒的求交
1.格子切割法Uniform Spatial Partitions(Grids)
- 一个场景中有5个圆圈，对该场景做包围盒
- 将包围盒做格子分割
- 保存每个格子内有图形的格子
- 对于一条光线，计算光线经过的每一个格子中是否有图像，如果有再判断是否与图像相交
- 光线怎么计算与格子的相交？从光线所在的格子为初始位置，向上或者当前位置前的格子做判断，取一个更接近的，就是下一列光线所经过的格子。
格子切割法局限性
- 上图中为不同分割的格子数量，格子数量不能太稀疏也不能太密集。
- 当一个物体在一个很大的场景中时格子切割法就变得不合适了。
- “茶壶在一个空旷的操场上。”
2.空间划分法
1.八叉树Oct-Tree
-
把一张图片切分成4块，假如每个小块内的物体数量小于等于1个，则停止切分
-
若数量大于1则继续切分成4块。
-
缺点：对于二维空间内是四叉树。对于三维空间是八叉树，但如果维度越高则越来越不方便
2.KD-Tree
-
对于二维空间，如上图中，对一张图，从中间横着切第一刀（视作二叉树第一层）
-
一刀后上下两侧的物体数量都超过了两个，则从两个物体间都各竖着各切一刀（视作二叉树的第二层，这里体现了每层二叉树的区分，同一层的的切分方式是一致的）
-
同理第三层是横着切，假如二层后的方块内物体数量>1则继续切分，以此类推
-
三维空间内：依次按照 从x轴切分，从y轴切分，从z轴切分，依次循环
3.BSP-Tree
-
跟KD-Tree类似，不同方向斜着切
-
高纬度后也不好用
KD-Tree Pre-Processing实际操作过程
- 依次沿着x-axis,y-axis,z-axis划分，使得空间被划分的更加平衡
- 划分的位置由空间中三角面的分布决定，具体细节不展开
- 叶子节点存储对应空间的所有物体或三角面信息，中间节点仅存储指针指向两个子空间
- 当划分空间太小或是子空间内只有少量三角形则停止划分
遍历DK-Tree
- 正序遍KD-Tree，对于每一个叶子节点的包围盒求交
- 若与叶子节点里的包围盒有交点，则需要对叶子节点内的所有物体求交
- 顺序A（1）──B（2）──C（3）──D（4，5）...，直到最后的叶子节点，依次类推
KD-Tree的优缺点
- 优点
- 利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交，那么则可以省略该部分空间所有子空间的判断过程，在原始的纯粹的AABB之上更进一步提升了加速效率。
- 缺点
- 缺点是判断包围盒与三角面的是否相交较难，因此划分的过程不是那么想象的简单，其次同一个三角面可能被不同的包围盒同时占有，这两个不同包围盒内的叶节点会同时存储这一个三角形面
综上所述，我们详细介绍了利用AABB的均匀划分方法，KD-Tree划分方法，也简略提及了Oct-Tree以及BSP-Tree。但其实这些技术在业界之中以及逐渐不再被多使用，但依然有很多借鉴参考价值，在下面一节会介绍一种现在被广泛使用的加速光线追踪的方法，即Bounding Volume Hierarchy。
3.物体划分 Bounding Bolume Hierarchy(BVH)
- BVH与前几种方法最显著的区别就是，不再以空间作为划分依据，而是从对象的角度考虑，即三角形面，过程如下：
- 第一步同样找出场景的整体包围盒作为根节点
- 第二步找到合适的划分点，将最大包围盒内的三角形面分为两部分，再分别重新就算新的包围盒
- 注意到这里，包围盒会重叠，但一个三角形面只会被存储在唯一的包围盒内，而这也就解决了KD-Tree的缺点！
- 接下来与KD-Tree的建立类似，递归的对所有子空间重复该步骤
- 最终可以建立出如上图的所示的树形结构，同样为了画图方便，只进行了左半部分的划分，右半部分其实同理。
注意要点
- 每次划分一般选择最长的那一轴划分，假设是x轴，那么划分点选择所有三角面的重心坐标在x坐标上的中位数进行划分，如此便能保证划分的三角形左右两边三角形数量尽可能差不多，当然也就使得树形结构建立的更加平衡，深度更小，平均搜索次数更少，提高了效率，这些都是数据结构的知识，相信大家掌握的都不错，就不多赘述了。
- 与KD-Tree一样，中间节点不存储物体三角面信息，只在叶节点中存储，终止条件可设定为当前包围盒内三角形数量足够少 （e.g. 5个）
光线与BVH求交的伪代码
- 判断光线与最大包围盒是否相交，没有就直接return,有则开始切分
- 如果是叶子节点，则检测光线与所有物体的求交，取最近的一个
- 如果不是叶子节点是中间节点，则拆分后求光线与子节点的交点，取最近的一个