526互联

10.Ray Tracing(Whitted-Style)

发布时间 2023-07-01 13:13:45作者: oOLzYOo

光栅化的局限性

  • 软阴影实现效果不好
  • 尤其是当光线不止一次反射时

光线追踪研究前提

研究光线追踪的假设前提：

  • 光线是沿着直线传播的
  • 光线与光线之间是不发生碰撞
  • 光线的可逆性。比如一条光线是从光源到物体再反射到眼睛中去，也可以说是从眼睛发出一条光线到物体表面再反射到光源中。

观测点的前提假设：

  • 观测点眼睛是一个点一个位置
  • 光源假设是点光源
  • 光线打到物体上 产生的反射是完美的

zhen孔摄像机模型

  • 摄像机（眼睛）射线通过了一个屏幕像素后，映射到某个物体上一个点
  • 从光源射出一条光线连接该点，判断该线过程中有没有被遮挡，有则在阴影中，没有就亮
  • 黑色箭头为该点的法线
  • 有了这三条线，可以得到该点的渲染模型

Whitted-Style 版光线追踪

  1. 从眼睛射出一条线看到像素，映射到某个物体上的一个点
  2. 该点处发生了一系列的光线的折射和反射
  3. 再从光源出连接各个折射到物体上的点和反射到物体上的点
  4. 对每条光源到物体点的连线做 路径判断，判断该路径是否被遮挡
  • primary ray: 从眼睛发射的线
  • secondary rays:折射或者反射后的线
  • shadow rays：从光源处连接各个物体表面的线

求光线与物体的交点

光线定义

  • 光线有一个起点并且是一个向量
  • 光线上任意一个点能用下面式子表示

\[r(t)=o+td(0<=t<\infty) \]

光线与球的交点(隐式几何)

球体上一点到圆心

\[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)

  1. 一个场景中有5个圆圈，对该场景做包围盒
  2. 将包围盒做格子分割
  3. 保存每个格子内有图形的格子
  4. 对于一条光线，计算光线经过的每一个格子中是否有图像，如果有再判断是否与图像相交
  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实际操作过程

  1. 依次沿着x-axis,y-axis,z-axis划分，使得空间被划分的更加平衡
  2. 划分的位置由空间中三角面的分布决定，具体细节不展开
  3. 叶子节点存储对应空间的所有物体或三角面信息，中间节点仅存储指针指向两个子空间
  4. 当划分空间太小或是子空间内只有少量三角形则停止划分
遍历DK-Tree

  • 正序遍KD-Tree，对于每一个叶子节点的包围盒求交
  • 若与叶子节点里的包围盒有交点，则需要对叶子节点内的所有物体求交
  • 顺序A（1）──B（2）──C（3）──D（4，5）...，直到最后的叶子节点，依次类推
KD-Tree的优缺点
  • 优点
  1. 利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交，那么则可以省略该部分空间所有子空间的判断过程，在原始的纯粹的AABB之上更进一步提升了加速效率。
  • 缺点
  1. 缺点是判断包围盒与三角面的是否相交较难，因此划分的过程不是那么想象的简单，其次同一个三角面可能被不同的包围盒同时占有，这两个不同包围盒内的叶节点会同时存储这一个三角形面

综上所述，我们详细介绍了利用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,有则开始切分
  • 如果是叶子节点，则检测光线与所有物体的求交，取最近的一个
  • 如果不是叶子节点是中间节点，则拆分后求光线与子节点的交点，取最近的一个