【GAME101】图形学学习记录——光线追踪

阴影映射(Shadow Mapping)

在着色部分中，我们学习了如何表现出一个物体被光线照射时表现出的效果。但是着色无法解决一个问题：如何表现阴影。在光栅化的领域中，解决这一问题的方法是阴影映射。

阴影映射的重要思想是：如果一个点可以被我们看到，且它不在阴影里，那么这个点既可以被摄像机看到，也可以被光源看到。阴影映射只能处理点光源产生的阴影，并且结果非零即一。我们称之为硬阴影。

第一步：在光源处放一个摄像机，看向我们想要渲染的场景，我们会得到一幅图。我们要做的是将这幅图上所有点的深度记录下来。

第二步：在原本的摄像机处看向场景，对于任意一点，我们将其投影回它在上一步得到的图中的位置。将其和之前记录的深度进行比较，如果深度一致，说明这个点可以被光源看到。

阴影映射虽然能解决着色产生不了阴影的问题，但它有着极大的缺点，即只能生成硬阴影，这使得用这种方法产生的阴影在很多情况下并不真实。虽然现在已经有了一些关于这个问题的解决方法，但比较麻烦。

因为光栅化无法很好地解决软阴影和多个光源存在时的渲染等问题，光线追踪的技术应运而生。光线追踪的速度较慢，但质量非常高，因此常被应用于离线场景中（如动画制作）。

基础光线追踪算法

光线

要了解光线追踪，我们首先要了解光线。一般来说，我们认为的光线有以下特点：

• 光线沿直线传播
• 光线之间不会发生碰撞
• 光线从光源出发，到眼睛结束

光线投射

对于上面第三点，有一个性质：光路的可逆性，即对于从光源到眼睛的一条光路，也可以认为是从眼睛发射出的感知光线投射到了光源，路径完全相同，只不过方向相反。光线追踪就利用了这个性质。

在光线追踪的场景里，我们假设眼睛是一个点。对于着色平面上的每一个像素，我们从眼睛处向其投射一道光线（后文简称为eye_ray），eye_ray第一个触碰到的点即为眼睛会看到的点。再将这个点投影向光源，即可根据能否到达光源判断这个点有没有被物体遮挡。当进行完这一过程后，我们已经得到了入射方向、观测方向、法线等信息，可以进行着色。如下图所示：

递归的光线追踪(Whitted-Style Ray Tracing)

在上述的过程中，光线仍然只反射了一次，而在现实生活中，光线是会反射很多次的。Whitted-Style Ray Tracing模拟了这一情形。

如下图所示，当光线照射到玻璃球上时，一部分光会发生折射，另一部分会发生发射，由此产生了多条光路，由此产生多个着色点。每个着色点着色的值都会被计算到成像平面的像素中。

技术细节

虽然上面的过程十分清晰，但实际上有许多技术细节较难实现，主要是如何求eye_ray和物体表面的交点。

首先，我们要知道光线在数学上的定义。光线本质上是一条射线，它有一个起点o和一个方向d。对于光线上任意一个点，都可以用以下形式表示：

$$r(t)=o+td\quad0\leq t<\infty$$

隐式表示

以球体为例，球面的隐式表示为：

$$(p-c)^2-R^2=0$$

将两者联立，即可得到我们要找的交点p。

同理，对于任意图形的隐式表示，我们只需要将光线代入图形函数，即可求出交点位置：

$$r(t)=o+td\quad 0\leq t<\infty \\ p:f(p)=0 \\ f(o+td)=0$$

当求出的t为正实数是，说明其有意义。

显式表示

对于显示表示，我们先考虑怎么实现光线与三角形求交。这个问题可以分成两部分：先求出光线和三角形所在平面的交点，再判断交点是否在三角形内。

我们可以用一个方向（法线）和一个平面上的点来定义任意一个平面，这样就可以轻松得到平面的显式表示。接下来的操作和之前相同。

$$r(t)=0+td \quad 0\leq t<\infty \\ p:(p-p\prime)\cdot N=o \\$$

联立解得：

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

判断点是否在三角形内的方法在之前的光栅化部分有所讲解，这里不再重复。

以下是一种可以直接算出光线与三角形的交点并判断其是否在三角形内的算法：Moller Trumbore算法。

在知道了怎么求光线和三角形的交点后，我们只需要求出光线和每一个三角形的交点，取最近的那个即是eye_ray和物体表面的交点。但是这样做的资源消耗太大了，有没有什么加速的方法呢？

加速结构

包围盒(Bounding-Box)是指完全包裹住物体的一块体积。在这里，我们通常使用轴对齐包围盒(Axis-Aligned Bounding Box,AABB)，它是三组对面的交集，相当于划定了x、y、z的范围。

一个重要思想：当光线不与包围盒相交时，它也一定不与物体相交。

首先，我们来了解如何判定光线和包围盒是否相交。

先考虑二维的情况。对于光线和包围盒的两组对面，我们能求出光线进入对面的时间和离开对面的时间（即使得出的时间是负的）。这样我们就得到了两条线段，对这两条线段求交集即可得到光线进出包围盒的时间。如图所示：

三维空间内的做法类似。对于三组对面，我们分别求出三个光线进入对面的时间tmin和三个光线离开对面的时间tmax，取最大的tmin和最小的tmax，即为光线进入和离开包围盒的时间。如果进入的时间小于离开的时间，说明光线和包围盒有交点，反之说明没有交点。

接下来再考虑时间为负的情况。如果离开时间texit<0，说明包围盒在光线的“后面”，一定没有交点。如果t exit>=0且离开时间t enter<0，说明光源在包围盒内，这时一定有交点。

总结一下，光线和包围盒有交点的条件为：

$$t_{enter}<t_{exit}\&\&t_{exit}>=0$$

对于一个场景，我们找出它的一个包围盒，将包围盒均匀划分为一堆格子，并找出那些与物体表面相交的格子。当光线进入包围盒时，我们计算它将与哪些格子相交，当光线与那些和物体表面相交的格子相交时，光线就有可能和物体相交。这时，我们再做光线和物体的求交。这样大大降低了计算时的性能消耗，因为我们认为计算光线和盒子是否相交是非常快的。

以上方法只适用于场景中的物体比较均匀且密集的情况，如果场景较为空旷，光线会穿过许多空格子，造成性能浪费。

空间划分(Spatial Partitions)是上面这种方法的改进。它的思想是在空旷的地方用一个大盒子包围，而物体密集的地方用一个个小的格子进行划分。下面是一些经典的空间划分方法：

KD-Tree有两个问题，一是三角形可能会同时在两个格子里，二是KD-Tree的建立并不简单直观。

Object Partitions & Bounding Volume Hierarchy(BVH)

目前，这个结构得到了广泛的应用，因为塔它基本上解决了KD-Tree的物体。

这种结构的思想是按照物体进行划分。对于一些三角形，先求出它们的一个包围盒。将这些三角形按某种方法分成两部分，对这两部分三角形重新求包围盒，重复操作，直到满足一定的标准。

这样做的好处是每个三角形只会出现在一个包围盒里，但是包围盒之间也有可能产生重叠，在划分时应该尽可能减少这种重叠。

一种简单的划分方法是沿着最长的轴进行划分，并且每次都从之间的三角形处进行划分，这样建立的树较为平衡。有一种可以在O(n)时间内找到无序数列中第i大的数的算法，叫做快速选择。我们可以用这种方法快速找到最中间的三角形。

辐射度量学(Radiometry)

虽然我们之前花了大量的篇幅讲述如何模拟现实中的光照情况，但其仍然是做了许多简化的，例如我们将光简单地定义为一个点及光强，而在现实中显然不是这样。而通过辐射度量学，我们将精准地赋予光一系列物理量，把光及物体的表面和光如何作用等细节精确地表示出来。

物理量

辐射度量学定义了光照的若干属性，如Radiant flux（光通量）,intensity（光强）,irradiance（辉度）,radiance（光亮度）。接下来将一一讲解。

Radiant Energy and Flux(Power)

Radiant Energy表示的是光源辐射出来的能量，而Radiant flux是单位时间内的能量，即光通量，类似于功率。

$$Q[J=Joule] \\ \phi =\frac {dQ}{dt}\quad[W=Watt][lm=lumen]^*$$

Radiant Intensity,Irradiance and Radiance

Intensity定义了某个单位立体角内的光通量。所谓的立体角是二维角度在三维空间中的延伸。从一个球的球心向球面投影一块面积，面积除以球半径的平方就是对应立体角的大小。

$$I(\omega)=\frac {d\phi}{d\omega}\quad[\frac \omega{sr}][\frac {lm}{sr}=cd=candela]$$

Irradiance是指单位面积上的光通量。

$$E(x)=\frac{d\phi(x)}{dA}\quad [\frac W{m^2}][\frac{lm}{m^2}=lux]$$

而Radiance定义了单位立体角和单位面积上的光通量，这意味着我们要对光通量做两次微分：

$$L(p,\omega)=\frac{d^2\phi(p,\omega)}{d\omega dAcos\theta}\quad[\frac W{srm^2}][\frac{cd}{m^2}=\frac{lm}{srm^2}=nit]$$

Radiance和Irradiance之间的差异就是方向性。

Bidirectional Reflectance Distribution Function(BRDF)

BRDF的意思是双向反射分布函数。这个函数真实地定义了反射的过程。它描述了有多少能量如果从某个方向进来，它会怎么向不同的方向分散。我们也可以理解成光线照射到某一个物体表面被吸收，物体表面再将能量发射出去。从这个角度，我们就可以用Radiance和Irradiance来理解反射。如图所示：

从一个单位立体角照射而来的Radiance被一小块单位面积dA吸收，得到了dA的Irradiance，而BRDF能告诉我们dA向各个方向单位立体角辐射的Radiance的大小。

$$f_r(\omega_i\to\omega_r)=\frac{dL_r(\omega_r)}{dE_i(\omega_i)}=\frac{dL_r(\omega_r)}{L_i(\omega_i)cos\theta_id\omega_i}\quad[\frac1{sr}]$$

将每一个方向的入射光对出射光方向的贡献加起来，就可以得到出射光方向的光照效果。以下就是反射方程：

$$L_r(p,\omega_r)=\int_{H^2}f_r(p,\omega_i\to\omega_r)L_i(p,\omega_i)cos\theta_id\omega_i$$

用更通用的方式重写这个方程，并考虑物体自身发光的情况，就得到了渲染方程：

$$L_o(p.\omega_o)=L_e(p,\omega_o)+\int_{\Omega+}L_i(p,\omega_i)f_r(p,\omega_i,\omega_o)(n\cdot \omega_i)d\omega_i$$

将光线传播写成算子形式，并进行展开，可以得到：

$$L=E+KE+K^2E+K^3E+...$$

这中间的过程比较复杂，这里不做说明。我们需要知道的是，上面这个公式的意思是，全局光照由直接光照和间接光照相加得到，间接光照包括一次反射、两次反射、三次反射……。

路径追踪

概率论

在开始接下来的学习之前，我们先复习一些概率论的知识。

随机变量：

$$X$$

随机变量服从于某种分布：

$$X\sim p(x)$$

X可能的取值：

$$x_i$$

X取xi概率：

$$p_i$$

需要满足的要求：

$$p_i\geq 0 \\ \sum_{i=1}^np_i=1$$

期望：

$$E[X]=\sum_{i=1}^nx_ip_x$$

在连续的情况下：

$$p(x)\geq0 \quad and\quad\int p(x)dx=1 \\ E[X]=\int xp(x)dx$$

概率密度函数(Probability Distribution Function,PDF)：

随机变量是函数的情况：

$$X\sim p(x) \\ Y=f(X) \\ E[Y]=E[f[X]]=\int f(x)p(x)dx$$

蒙特卡洛积分

蒙特卡洛积分是一种求复杂函数定积分的值的方法。它的思想是在积分范围内随机取一点并将以积分范围为底，随机点处的值为高的长方形的面积近似当作定积分的值。重复多次并求平均，结果会越来越精准。

$$\int_a^bf(x)dx \\ X_i\sim p(x) \\ N_N=\frac1N\sum_{i=1}N\frac{f(X_i)}{p(X_i)}$$

路径追踪的实现

之前我们得到了渲染方程，而接下来的工作就是去解这个方程。而渲染方程中最重要的部分是一个定积分，我们将用蒙特卡洛方法去解这个定积分。

忽略物体自身发光的情况，渲染方程如下：

$$L_o(p.\omega_o)=\int_{\Omega+}L_i(p,\omega_i)f_r(p,\omega_i,\omega_o)(n\cdot \omega_i)d\omega_i$$

首先我们只考虑直接光照。为了方便计算，我们假设对每个方向进行采样的概率相等。这样一来，我们就可以写出积分的蒙特卡洛形式：

$$L_O(P,\Omega_o)=\int_{\Omega+}L_i(p,\omega_i)f_r(p,\omega_i,\omega_o)(n\cdot\omega_i)d\omega_i\approx\frac1N\sum_{i=1}^N\frac{L_i(p,\omega_i)f_r(p,\omega_i,\omega_o)(n\cdot\omega_i)}{p(\omega_i)} \\ p(\omega_i)=\frac1{2\pi}$$

伪代码：

接下来考虑包含间接光照的情况。对于着色点p，假设有一点q在受到光源照射后会反射给p，那么我们用直接光照的算法算出q点向四周辐射的能量，再将q点当作光源，就可以用相同的方法算出q点对于p点的贡献。伪代码：

虽然上面的想法很美好，但还有一个严重的问题：随着反射次数的提升，光线的数量会呈指数级增长，而这样的性能消耗是我们无法承受的。目前来说，路径追踪的做法是令n=1（这样显然会造成结果的不精确，解决方法会在之后细说），这样无论反射多少次，光线都不会增加。我们在每一个像素内取许多个采样点，对于每个采样点都连一条到达光源的路径，这在一定程度上和蒙特卡洛积分中取n个采样点的做法相同。这也是这个方法被称为路径追踪的原因。令n!=1的做法叫做分布式光线追踪。

另一个问题是，这个算法是一个递归的算法，但是它没有设置递归出口。这个问题的解决方法是“俄罗斯轮盘赌”。

我们都知道俄罗斯轮盘赌是一个概率问题，而在这里，它的思想是设置一个概率p，在每一次计算时，有p的概率会发射一条光线出去，得到的着色结果是Lo/p，而有(1-p)的概率不发射光线出去，得到的结果自然是0.这样做的好处是，最终得到的期望依旧是Lo。伪代码：

以上就是路径追踪的大致内容。

优化

在进行蒙特卡洛采样时，如果用完全随机的方法，路径到达光源的几率较低，这样很多光线就被浪费了。如果我们能找到一个更好的采样方法，这个问题将会得到改善。

如果只在光源上进行采样，那么所有的光线都将到达光源，自然不会产生浪费。问题是蒙特卡洛积分要求采样位置和积分位置相同，因此我们要将渲染方程中对方位角的积分改写成对光源面积的积分，下面直接给出结果：

这样，对于光源产生的光照，我们直接进行计算，而对于间接光照，我们仍使用俄罗斯轮盘赌的方法，伪代码如下：

当然，还要注意光源被物体遮挡的情况。