GAMES102 Lecture 13 Ray Tracing 1 (Whitted-Style Ray Tracing)

这里回顾GAMES101 Lecture 13，这一讲介绍了光线追踪（基本原理）。

课程主页：

• https://sites.cs.ucsb.edu/~lingqi/teaching/games101.html

课程作业：

• http://games-cn.org/forums/topic/allhw/

课程视频：

• https://www.bilibili.com/video/BV1X7411F744?spm_id_from=333.337.search-card.all.click

为什么需要光线追踪？

• 光栅化无法很好地处理全局效果：
  • （软）阴影；
  • 光线反射多次；
  • 光栅化速度很快，但质量相对较低；
  • 光线追踪很准确，但速度很慢；
    • 光栅化：实时；
    • 光线追踪：离线；
    • 大约10K CPU核心小时在产品中渲染一帧；

基本光线追踪算法

光线

关于光线的三个想法（图形学中的基本假设）：

1. 光以直线传播（虽然这是错误的）；
2. 光线交叉时不会相互“碰撞”
   （虽然这仍然是错误的）；
3. 光线从光源传播到眼睛（可逆性，也可以理解为光线从眼角传播到光源）；

光线投射

基本流程：

1. 对每像素投射一条射线来生成图像；
2. 通过（从图像）向灯光发送光线来检查阴影；

这里有几个基本假设：

• 假设眼睛是一个点；
• 光源是点光源；

产生eye ray

结合上图进行讲解：

1. 首先从眼睛出发一个光线，穿过pixel，指向物体；
2. 找到光线和场景内最近的物体的交点（因为该交点会遮挡后续交点）；
3. 从该交点向光源连线；
4. 根据入射，出射，法线方向计算着色；

注意到该方法认为光线只弹射一次，所以效果和光栅化产不多，为了解决这点，需要引入Recurisive (Whitted-Style)光线追踪，效果为：

Recurisive光线追踪

依然考虑光线投射。当光打到玻璃球上，会发生反射和折射，折射光线会再次发生反射和折射，这个过程会发生无限多次，我们在每个弹射点计算着色结果，最后将其累加到像素上：

这来再对光线进行分类：

• primary ray：从眼角直接发射的光线；
• secondary ray：弹射后的光线；
• shadow rays：向光源连接的光线；

上述是整体思路，下面介绍该算法的细节，从光线和表面交点开始。

光线-表面交点

光线方程

光线是一条射线，由起点和方向定义：

$$\mathbf{r}(t)=\mathbf{o}+t \mathbf{d} \quad 0 \leq t<\infty$$

其中：

• $\mathbf o$是起点；
• $\mathbf d$是单位方向向量；

图示：

光线和球面的交点

球面方程为：

$$\mathbf{p}:(\mathbf{p}-\mathbf{c})^2-R^2=0$$

求交点即为求解如下方程：

$$(\mathbf{o}+t \mathbf{d}-\mathbf{c})^2-R^2=0$$

展开后可得：

$$\begin{aligned} &a t^2+b t+c=0\\ &a=\mathbf{d} \cdot \mathbf{d} \\ &b=2(\mathbf{o}-\mathbf{c}) \cdot \mathbf{d} \\ &c=(\mathbf{o}-\mathbf{c}) \cdot(\mathbf{o}-\mathbf{c})-R^2 \end{aligned}$$

那么：

$$t=\frac{-b \pm \sqrt{b^2-4 a c} }{2 a}$$

判别式$<0, =0, >0$分别对应没有交点，一个交点和两个交点的情形。

光线和显式表面的交点

对球面的情形进行推广，对于一般的显式表面：

$$\mathbf{p}: f(\mathbf{p})=0$$

我们求解如下方程的正实数解：

$$f(\mathbf{o}+t \mathbf{d})=0$$

光线和三角形面的交点

为什么要讨论光线和三角形的交点？

• 渲染：可见性，阴影，灯光 ；
• 几何：光线内部/外部测试；
  • 对于封闭的曲面，如果一个射线和该曲面有奇数个交点，则在曲面内，否则在曲面外；

如何计算？
让我们分解一下：

• 简单的想法：只需将射线与每个三角形相交；
• 简单但缓慢（如何加速？）；
• 注意：可以有0或1个交点
  （忽略多个交点情形）；

光线和三角形的交点

注意到三角形在某个平面内，所以将该问题分解为两个步骤：

• 求解光线和平面的交点；
• 判断交点是否在三角形内；

平面方程

平面有平面上一个点和法向量定义：

平面方程：

$$\mathbf{p}:\left(\mathbf{p}-\mathbf{p}^{\prime}\right) \cdot \mathbf{N}=0$$

标准形式为：

$$a x+b y+c z+d=0$$

将光线方程$\mathbf{r}(t)=\mathbf{o}+t \mathbf{d}, 0 \leq t<\infty$代入可得：

$$\begin{aligned} \left(\mathbf{p}-\mathbf{p}^{\prime}\right) \cdot \mathbf{N} &=\left(\mathbf{o}+t \mathbf{d}-\mathbf{p}^{\prime}\right) \cdot \mathbf{N}\\ &=0 \\ t&=\frac{\left(\mathbf{p}^{\prime}-\mathbf{o}\right) \cdot \mathbf{N} }{\mathbf{d} \cdot \mathbf{N} } \end{aligned}$$

求解后再检查是否满足$0\le t<\infty$以及交点是否在三角形内。

Möller Trumbore算法

Möller Trumbore算法利用重心坐标进行求解：

$${\mathbf{O} }+t {\mathbf{D} }=\left(1-b_1-b_2\right) {\mathbf{P} }_0+b_1 {\mathbf{P} }_1+b_2 {\mathbf{P} }_2$$

变形可得：

$$\begin{aligned} -t{\mathbf{D} }+b_1\left({\mathbf{P} }_1-{\mathbf{P} }_0 \right) +b_2\left({\mathbf{P} }_2-{\mathbf{P} }_0 \right) &={\mathbf{O} }-{\mathbf{P} }_0 \end{aligned}$$

记：

$$\begin{aligned} &{\mathbf{E} }_1={\mathbf{P} }_1-{\mathbf{P} }_0 \\ &{\mathbf{E} }_2={\mathbf{P} }_2-{\mathbf{P} }_0 \\ &{\mathbf{S} }={\mathbf{O} }-{\mathbf{P} }_0\\ &{\mathbf{S} }_1={\mathbf{D} } \times {\mathbf{E} }_2 \\ &{\mathbf{S} }_2={\mathbf{S} } \times {\mathbf{E} }_1 \end{aligned}$$

那么方程变换为：

$$\begin{aligned} -t{\mathbf{D} }+b_1{\mathbf{E} }_1 +b_2 {\mathbf{E} }_2 &={\mathbf{S} } \end{aligned}$$

两边点乘法$\mathbf S_1$可得：

$$b_1{\mathbf{E} }_1 .\mathbf S_1=\mathbf S. \mathbf S_1, b_1=\frac{\mathbf S. \mathbf S_1}{\mathbf S_1 .{\mathbf{E} }_1 }$$

两边点乘$\mathbf S_2$可得：

$$-t(\mathbf D. \mathbf S_2) +b_2 (\mathbf E_2 . \mathbf S_2)=0$$

两边点乘${\mathbf{E} }_1\times \mathbf E_2$可得：

$$-t{\mathbf{D} }.({\mathbf{E} }_1\times \mathbf E_2)=\mathbf S. ({\mathbf{E} }_1\times \mathbf E_2)$$

注意到：

$${\mathbf{D} }.({\mathbf{E} }_1\times \mathbf E_2) =-{\mathbf{E} }_1 .({\mathbf{D} } \times {\mathbf{E} }_2) =-{\mathbf{E} }_1 .\mathbf S_1 \\ \mathbf S. ({\mathbf{E} }_1\times \mathbf E_2)={\mathbf{E} }_1.({\mathbf{S} } \times {\mathbf{E} }_1)={\mathbf{S} }_2.\mathbf E_2$$

所以：

$$t=\frac{ {\mathbf{S} }_2.\mathbf E_2}{\mathbf S_1 .{\mathbf{E} }_1 }$$

根据$t$和$b_2$的关系可得：

$$t=\frac{ \mathbf S_2 . \mathbf D}{\mathbf S_1 .\mathbf E_1}$$

即：

$$\left[\begin{array}{l} t \\ b_1 \\ b_2 \end{array}\right]=\frac{1}{ {\mathbf{S} }_1 \cdot {\mathbf{E} }_1}\left[\begin{array}{c} {\mathbf{S} }_2 \cdot {\mathbf{E} }_2 \\ {\mathbf{S} }_1 \cdot {\mathbf{S} } \\ {\mathbf{S} }_2 \cdot {\mathbf{D} } \end{array}\right]$$

加速光线和表面交点的计算

光线追踪——性能挑战

简单的光线场景相交

• 详尽地测试每个三角形的光线交点；
• 找到最近的命中（即最小$t$）
  ；

问题：

• 朴素算法 = #pixels ⨉ #traingles (⨉ #bounces)
• 非常慢！

为了一般性，我们稍后使用术语对象而不是三角形（但不一定表示整个对象）

包围盒

避免交点的快速方法，用简单的体积包围复杂的对象：

• 对象完全包含在盒中；
• 如果光线不和盒相交，光线就不会和对象相交；
• 所以首先测试BVol，然后测试对象是否相交；

图示：

光线与盒子的交点

• 长方体的理解：box是3对平行面形成的交集；
• 具体来说：
  我们经常使用Axis-Aligned Bounding Box (AABB) (轴对齐包围盒)
  ，即BB的任何一侧都沿x、y或z轴；

光线和Axis-Aligned Box的交点

计算与平行面的交点，并取tmin/tmax区间的交集（以2D为例）：

求出光线关于x平面和y平面的进入和离开的时间$t_{\mathrm{min} }/t_{\mathrm{max} }$，对两次求得的区间$[t_{\min}, t_{\max}]$求交集。

对于3D盒子 = 三对无限大的平板，关键思想为：

• 光线只有在进入所有成对的平板时才会进入盒子；
• 只要光线离开任何一对平板，光线就会离开盒子；
• 所以对于每一对平板，计算tmin和tmax（负数也ok）
• 对于3D box，$t_{\mathrm{enter} } = \max{t_{\min} } $，$t_{\mathrm{exit} } = \min{t_{\max} }$
• 如果$t_{\mathrm{enter} } < t_{\mathrm{exit} }$，我们知道光线在盒子里停留了一段时间（所以必须相交！）；
• 然而，射线不是直线；
  • 应该检查$t$对应的实际情形是否正确；
• 如果$t_{\mathrm{exit} }$怎么办？
  • 盒子在光线“后面”——没有交点！
• 如果$t_{\mathrm{exit} }\ge 0$并且$t_{\mathrm{enter} }<0$怎么办？
  • 光线的起点在盒子内——有交点！
• 综上所述，ray和AABB当且仅当：
  • $t_{\mathrm{enter} } < t_{\mathrm{exit} }$并且$t_{\mathrm{exit} }\ge 0$；

为什么要使用轴对齐

最后一个问题，为什么要使用轴对齐包围盒？原因很简单，为了计算方便。

对于一般情形：

公式

$$t=\frac{\left(\mathbf{p}^{\prime}-\mathbf{o}\right) \cdot \mathbf{N} }{\mathbf{d} \cdot \mathbf{N} }$$

对于轴对齐情形：

公式：

$$t_x=\frac{\mathbf{p}_x^{\prime}-\mathbf{o}_x}{\mathbf{d}_x}$$