引言
GAMES101现代图形学入门是由闫令琪老师教授。今天我们来讲光线追踪的最后一部分，回顾之前的渲染方程和概率只是，介绍蒙特卡洛积分并引入路径追踪。
A Brief Review
Review - The Rendering Equation
上节课最重要最重要的内容就是渲染方程，它描述了光线的传播方式。今天我们自然而然要解决渲染方程的计算问题。
Review - Probabilities
第二个复习就是之前关于概率的一些事情。在渲染里面我们更多考虑的是连续型随机变量，离散的我们不说了，连续性的随机变量 $x$ 符合某一种概率密度分布，概率密度函数需要满足：
- 概率密度函数必须非负，并且积分起来是 1
- 期望为它的值乘以概率密度，连续性体现为积分
Monte Carlo Integration
我们现在要讲一个积分方法：蒙特卡洛积分。
Monte Carlo Integration
我们学习蒙特卡洛积分为了什么呢？刚才提到随机变量满足什么样的概率，自然蒙特卡洛需要用到它，但首先蒙特卡洛积分解决的是定积分问题：给任何一个函数，计算定积分。假设这个函数比较复杂不好解析的积出来，这是一种数值的方法，我最后关心的是这个积分最后的值是多少，我就关心这一个数。
蒙特卡洛怎么做呢？在讲蒙特卡洛之前我们先回忆一下微积分提过黎曼几何的概念，所谓黎曼积分就是把 $a$ 和 $b$ 之间均匀拆成 100 份，每一份取它的中间位置 $x_i$，找到对应的 $y_i$，我就认为每一份都是微小的长方形，就可以把这份曲线下方的面积分解成各个不同的小的长方形的面积之和。
蒙特卡洛积分是另外一种积分方法，它考虑一种随机的采样。比如它在 $a$ 和 $b$ 之间随机取一个数 $x$，找到对应的 $f(x)$，假设这个曲线就是一个长方形，它的高度就是我取的值对应位置的高度、宽度就是 $a$ 和 $b$。也就是说我用这么一个长方形的大小或面积来近似一个曲线下围出来的面积，那我自然可以把这个过程重复多做很多次，在 $a$ 和 $b$ 之间采样很多次，每一次用的长方形面积各不相同，把这些长方形面积平均起来可不就能得到一个相对准确的结果。蒙特卡洛积分就是在积分域不断采样，然后把所有长方形面积加起来求平均。
在积分域我随机采一个变量或位置，蒙特卡洛积分告诉我们这个积分可以近似成 $f(X_i)/p(X_i)$ 求和之后的平均。
Example: Uniform Monte Carlo Estimator
我们举一个简单的例子，我在 $a$ 到 $b$ 之间均匀采样，这样采样所用的 PDF 应该是各处相同的，应该是个常数 $C$，最后这个 PDF 解出来为常数 $\frac{1}{b-a}$。
现在我们用蒙特卡洛积分的方法来算，需要知道 $f(x)$ 和 $p(x)=\frac{1}{b-a}$，数学变换一下得到 $F_N = \frac{b-a}{N}\sum^N_{i = 1}{f(X_i)}$。
从一个更通用的角度来说，不管我怎么对随机变量进行采样，只要有一个满足的 PDF，采样出来的求平均就可以得到定积分的近似了。这样一来我们就可以得到任何一个积分。
它好用在我们只需要对积分域之间以一种方式采样，知道采样对应的 PDF 是多少就可以了。这里有几点需要注意的事情：
- 采样越多结果越接近
- 对 $x$ 积分则要对 $x$ 采样
Path Tracing
Motivation: Whitted-Style Ray Tracing
路径追踪一下子和我们之前的 Whitted 风格的光线追踪联系起来。
Whitted 风格光线追踪做的是不断弹射光线，任何一次弹射的位置都和光源连一条线。那么它是怎么弹射光线的呢？有两种情况：当你一个光线打到一个所谓光滑的物体上，它会沿着镜面方向反射或折射；如果这条光线打到所谓漫反射的物体，那么这条光线就停了，不会再往前走了。
现在我们回过头来思考这样一个问题，这两个事情真的对吗？我们要提出路径追踪正是为了解决之前 Whitted 风格光线追踪里面很多非物理不正确的一些问题。
Whitted-Style Ray Tracing: Problem 1
Whitted 风格光线追踪哪里做错了呢？这里有两个茶壶，左边更像镜子，右边更像正常的金属，类似磨砂的感觉。
对于镜子这种反射，我们定义为 specular 完全镜面，一根光线打过去一定沿着镜面反射方向去，这就是为什么壶身上映出了环境光的样子。右边这种稍微有一点镜子的感觉，但又有点糊，我们称为 glossy 材质。它没有那么光滑，但能产生高光。
现在我们如果套用 Whitted 风格光线追踪，那么 specular 材质就是对的，glossy 材质就是不对的。因为它为什么看上去是糊的呢？就是因为光线在壶上打出一条光线来，它应该是会被反射到镜面反射周围的一小片区域，多少有点粗糙程度。
Whitted-Style Ray Tracing: Problem 2
第二个问题是 Whitted 风格光线追踪认为光线打到漫反射物体就停止了，不会往后面继续去计算光线，这是不对的。为什么叫漫反射？因为它会把光线给均匀反射到各个不同方向上去，所以漫反射物体被光线打到后仍然会反射，仅仅是会反射到不同的方向去而已。这里我不考虑意味着漫反射物体之间的光线都被忽略。
上面两幅图都是由路径追踪得到的，区别是直接光照和全局光照。可以很明显看到右边全局光照的效果才是我希望看到的效果，而且红墙和绿墙映射到立方体上，人们形象的把这种现象称为“color bleed”。这说明我们光线打到漫反射材质绝对不应该就停住，而是应该真正往四面八方散射，这是 Whitted 风格做不来的事情。
Whitted-Style Ray Tracing is Wrong
我们意识到 Whitted 风格光线追踪是错的，那么什么是对的？上一节课说到各种各样辐射度量学正是为了提供这么一个标准，渲染方程是正确的，因为它是完完全全按照物理量推导出来的，刚才我们复习的时候还说了一下，它的概念就是告诉我们从某一点看到的光要么是自己发出来的，要么是从四面八方反射来的。
咱们要正确算出来看到物体的一个点的光是多少，自然而然需要正确解出渲染方程。为了解这个渲染方程，我们来看一下渲染方程本身的结构：首先不考虑发光项它很明显是一个积分，我要考虑来自四面八方的光照就要考虑整个半球的积分；另外一点从积分还会看到从另外一些方向进来的光线，这些光线有可能是直接的光照，有可能是其他微反射的光照我们不做区分，这是一个递归的问题。
A Simple Monte Carlo Solution
首先为了解渲染方程，我们先不考虑多次弹射的复杂情况，我们先考虑一个简单情况：只考虑一个像素点的直接光照。渲染方程涉及到观测方向从着色点到摄像机 $\omega_o$，各个方向进来的光我都认为均匀分布在球面上的，$\omega_i$ 表示各个不同的入射方向。当然了，渲染方程里我们考虑的所有方向都是向外，这和我们之前的 Blinn-Phong 模型是有一样的。
对于这个点的直接光照自然来自四面八方的入射光照强度，从这里开始我们忽略渲染方程的发光项，不再区分渲染方程和反射方程。对于刚才的着色点来说，它的 Radiance 就是四面八方来的光和 BRDF 作用之后反射到我们的观察方向上去，也就是任何一个 $\omega_i$ 反射到 $\omega_o$ 整个一个球面积分起来就可以了。
既然我们说明是直接光照，四面八方进来的光 $L_i$ 只有可能是光源自己带的，不考虑多次反射，不可能是其他东西反射过来的。
这个式子看起来很复杂，其实它就是一个积分，它就是在半球上不同方向上的积分，那我们就可以用蒙特卡洛方法来解：在半球上对不同方向采样计算 $f(x)$ 和 PDF。
我们考虑着色点假如叫 p 点，它的 Radiance 从这点反射到摄像机的 Radiance 是多少呢？计算这个积分根据蒙特卡洛方法我们在积分域上进行采样得到一个样本 $x$，然后对于 $x$ 来说算它的 $f(x)/PDF$ 求平均就好了。
那完全可以迁移到我们现在要做的事情上，这个函数的被积函数 $f(x)$ 为 $L_i(p,\omega_i)f_r(p,\omega_i,\omega_o)(n \cdot \omega_i)$，而 PDF 涉及到我们如何对半球进行采样。这里给大家一个最简单的采样方法：均匀采样，我认为我采样的任何一个在半球上的方向的概率密度是相同的，球面面积为 $4\pi$，半球面为 $2\pi$，所以 PDF 为 $1/2\pi$。
现在完全可以写成蒙特卡洛的积分方式，每一次取一个 $\omega_i$ 求和求平均。从这个式子我们可以算出任何一个着色点它的 Radiance 是多少，可以写成一个算法：
Introducing Global Illumination
我们作为直接光照这部分就是这么简单做完，但可以更进一步引入间接光照。图中可视 Q 为光源，只需算出 Q 到 P 反射的 Radiance 就行了，这就好像我们从 P 点观察 Q 点算 Q 点的直接光照。
所以我们可以在之前的简单算法上加上一个递归分支，得到一个支持全局光照的路径追踪算法。如果我打到的不是光源而是物体，我们就考虑物体对应的 q 点反射过来的能量是多少，也就是 q 点的直接光照。
那这个问题是否就已经解决了呢？答案是没有。
Path Tracing
第一个问题是递归的方式来计算光线数量会导致崩溃。我们有 1 根光线打到物体上，往四面八方打出假设 100 根光线，这 100 根光线都有可能打到第二个物体 ，而这 100 根光线每一根再发出 100 根光线，就变成了 10000 根光线……这就非常非常严重了，这样做我光线弹射两次之后就已经承受不住了，光线的数量为弹射次数的指数次。
那么我们怎么办呢？当 $N=1$ 时指数不会产生影响，这也告诉我们一个着色点打出很多光线是不是不太好，那我只打出一条光线没什么问题。
我们可以用一根光线解决问题，稍微修改一下之前的算法：随机往一个方向去采样 $\omega_i$。虽然结果可能充满噪音，但到此为止，我们用 $N = 1$ 来做蒙特卡洛积分称为路径追踪。
Ray Generation
那为什么叫路径追踪呢？我们最后要的是一个像素的 Radiance，穿过一个像素可以有很多不同的路径，这些所有的路径最后都会穿过一个像素，这个像素最后的 Radiance 就是这些路径求平均，我只要用足够多的路径就可以了。
我们最后是为了渲染一张图，我肯定是说每一个像素发出一系列光线，然后在任何一个打到的点上把它着色的结果求平均算出来。
在像素内均匀的取 $N$ 个不同的位置，对于任何一个我选取的位置从视点连一根光线连到样本的位置形成一条光线，如果我这条光线打到了场景中的位置，那么就要算这一点的着色。这里也算是一个蒙特卡洛积分，相当于我随机的对像素里取了很多不同的样本，产生了很多不同的路径，这些路径最后的贡献取平均计算出来。
刚才那个算法到目前为止对了吗？还没对，因为它有一个严重的问题：递归需要递归基，否则这个算法是永远进行的，我没有判断到什么时候需要我停下来。
很多人会质疑：真实世界里光线本身的弹射次数也不会停，这种情况下怎么办呢？如果我限制这个光的弹射次数只能等于某个次数（比如是三次）得到上图。
再设置为 17 次得到这张图，那么说如果我提前把光限制弹射次数是不对的，多次弹射的能量损失掉了。现在陷入了两难的境地：真实情况下光就是弹射无数次，我在计算机不能模拟弹射无数次；如果限制弹射次数又会面临能量损失。
Solution: Russian Roulette (RR)
人们引入了一种方法，这种方法叫做俄罗斯轮盘赌（RR）。
你有一把左轮手枪，正常情况弹容量 6 发，里面放入若干数量的子弹，把弹夹一转。这个时候你就不知道下一发打出来到底有子弹没子弹，这种情况下有人会对自己开枪或者轮流开枪看运气。假如我们往左轮里装入两枚子弹，你的生存概率就是 $4/6 = 2/3$。
那么这个俄罗斯轮盘赌和我之前说的光弹射次数有什么关系呢？有关系，我们引入这样一个概念来决定一定概率去停止继续往下追踪。
首先我们最后得到的积分结果要算出某一个着色点的 Radiance $L_o$。我自己给自己定一个（或者动态生成）概率 $P$，以一定的概率 $P$ 我们往某一个方向打这条光线，最后得到一定的结果再把它除以概率，得到返回值；在 $1-P$ 的概率下我就不打这根光线，得到的结果自然是 0。
这就是俄罗斯轮盘赌妙的地方，因为这里你仍然可以期望最后得到的结果是 $L_o$：
$$
E = P * (L_o/P) + (1 - P) * 0 = L_o
$$
可以看到期望得到的结果仍然是 $L_o$，通过这种方式我以一定的概率有时候往外打一根光线，有时候不打光线，只不过我打光线的时候得到的值除以 $P$ 能够得到正确的结果。
总结到代码上要修改的地方极少：我随机选一个概率 $P_{RR}$，对于任何一点的着色我要么往外打一根光线；要么我不打这根光线，最后产生的结果除以生存的概率就好了。
现在就已经是一个正确的路径追踪了，但它还有一个小问题：它并不高效。
Sampling the Light
我考虑都是同一个点，场景中的光源有大有小，在着色点往外打多少根光线是不同的。比如左边的场景我打 5 根光线就可以碰到光源；中间的场景打了 500 根光线可能会碰到光源；对于右边的场景则可能需要 50000 根光线才能打到光源。着色点均匀采样会造成有很多光线被浪费掉了，是否有别的采样方法呢？
Sampling the Light (pure math)
蒙特卡洛方法从来没说你只能用一种均匀的 PDF，它可以用任何的。那咱们说怎么才是完全不浪费光线的采样方法？自然就是说如果我不管光源的大小直接在光源上采样，这样所有的光线就都不会浪费了。
对于着色点我不再四面八方均匀采样，我在光源上进行采样，和着色点连接起来形成两个法线夹角 $\theta$ 和 $\theta’$。假设光源面积为 $A$，我们现在想采样光源 $\int{pdf\space dA = 1}$，那么 $pdf = 1/A$。但是渲染方程不是定义在光源上，这个积分是定义在立体角上的，而之前蒙特卡洛积分提到积分必须在积分域上，现在是在光源的面积上采样，积分是在立体角上采样，这是不对的。
我想让蒙特卡洛还继续生效怎么办？我得把渲染方程写成在光源上采样的积分。
很简单，$dA$ 是在光源上的小的表面，$d\omega$ 是小表面投影到单位球上立体角是多少，我们只需要知道 $d\omega$ 和 $dA$ 的关系就可以了：
$$
d\omega = \frac{dA \cos{\theta’}}{||x’-x||^2}
$$
更近一步我们可以把渲染方程重写，微积分上简单的变量替换用 $dA$ 替换 $d\omega$。最直观的理解是原本我的积分是在空间上，现在我要把它改变积分域到另一个空间上去，就是两个积分域如何联系起来的问题。
现在渲染方程已经写成对光源的积分，那这时候问题就变得无比简单，因为我对光源进行采样积分，积分起来 $f(x)$ 和 $pdf$ 都是已知，得到蒙特卡洛积分的结果。
之前我们是盲目的在着色点上往各个不同的方向去采样，打不打的到光源是随缘的。但现在我们直接对光源进行采样，可以把之前的算法改一改：
- 光源的贡献（直接光照）
- 其他所有非光源的贡献（间接光照）
Some Side Notes
最后我们说一说不是那么重要的东西，写对路径追踪是非常有挑战性的东西。
Is Path Tracing Correct?
路径追踪是几乎 100% 正确的算法，左边是真正的康奈尔盒的模型，右边是渲染出来的全局光照环境。所以路径追踪可以做到照片级真实感，这是一个里程碑式的研究。
Ray tracing: Previous vs. Modern Concepts
直到今天还有人在用光线追踪的概念，我们该如何去区分呢？这里我简单总结一下：
- 之前图形学课上学到的光线追踪更多的是 Whitted-style ray tracing
- 现代的光线追踪我认为是一个光线传播方法的大集合，包括（单/双向）路径追踪、光子映射、光线传输以及 VCM 和 UPBP 等等
Things we haven’t covered / won’t cover