引言
GAMES101现代图形学入门是由闫令琪老师教授。今天我们来讲Whitted Style的光线追踪和其实现的若干技术细节。
Why Ray Tracing?
Rasterization couldn’t handle global effects well
- (Soft) shadows
- And especially when the light bounces more than once
我们为什么引入光线追踪呢？因为我们在之前谈到光栅化的时候它有一些问题解决的并不是很好，最大的问题是它不是很好去表示全局的效果，包括软阴影、Glossy反射和间接光照等等。
Rasterization is fast, but quality is relatively low
通常情况下，光栅化是一种很快但很近似的渲染方法。比如大家看到图中绝地求生中的载具，没有阴影，模型精度非常低纹理也看不太清楚，是一种很原始的渲染结果。那么为什么大家只能做到这么原始的效果呢？因为游戏地图本身非常大，整个渲染对GPU要求非常高，所以他们对画质不能做过多的要求。
所以光栅化本质上来说它是一种快速的近似，质量相对较低。
Ray tracing is accurate, but is very slow
- Rasterization: real-time, ray tracing: offline
- ~10K CPU core hours to render one frame in production
对比下来光线追踪是一种准确的方法，但它也有问题，并不能替代光栅化。其最严重的问题是非常慢，光栅化通常瞄准实时每秒钟30帧，而光线追踪更多被用来做离线的应用比如电影。电影的制作商花大量的时间生成好这个电影然后放映，1帧需要花1万个CPU小时，对比光栅化显然是没办法比的。
Basic Ray-Tracing Algorithm
Light Rays
Three ideas about light rays
- Light travels in straight lines (though this is wrong)
- Light rays do not “collide” with each other if they cross (though this is still wrong)
- Light rays travel from the light sources to the eye (but the physics is invariant under path reversal - reciprocity).
“And if you gaze long into an abyss, the abyss also gazes into you.” — Friedrich Wilhelm Nietzsche (translated)
在定义光线追踪之前，我们先把光线定义下来：
- 光线沿着直线传播而不考虑其波动性
- 光线和光线不会发生碰撞
- 光线一定是从光源发射最终进入人的眼睛
整个光线追踪就是在做这样一个视图模拟的过程，运用了光线的可逆性，可以是光源发出光线然后不断弹射打到人的眼睛里；我也可以认为我的眼睛是可以发出一些感知射线打到这些物体，最后打到光源上。如果我在场景中找到一条光路，光源可以通过某种办法看到相机，那么相机也有办法看到光源。
Emission Theory of Vision
Ray Casting
Appel 1968 - Ray casting
- Generate an image by casting one ray per pixel
- Check for shadows by sending a ray to the light
首先我们要做光线的投射，假设我们在往一个虚拟的世界中看，面前放着一个成像的平面。成像平面被我们划成不同的像素的格子，对于每一个像素我们可以从摄像机连一条线穿过这个像素，然后打出一根光线，这根光线一定会打到场景中的某个位置或者和所有物体都不相交。
如果相交，我们把这个点和光源做一个连线，判定交点是否对光源可见，也就是判断是不是在阴影里，如果这个点不在阴影中，那么就形成了一条有效的光路：光源-交点-相机，就可以计算这条光路的能量，最后把看到的颜色算出来。
Generating Eye Rays
在做光线追踪时，我们假设眼睛永远是针孔摄像机，是一个点/位置，不考虑实际的相机应该如何处理；光源这里也假设为点光源；对于场景中的物体，我们认为光线打到它之后会发生完美的折射或反射。
Ray Casting - Shading Pixels (Local Only)
求最近交点时自然会知道法线，有了法线、入射方向和出射方向，我们就可以算这一点的着色，最后写入像素的值。
可以看到，光线投射做的就是每个像素投出去一根光线，从眼睛开始和场景相交求最近交点，找到交点后和光源连线判定是否对光源可见，最后计算着色写回像素的值。
Recursive (Whitted-Style) Ray Tracing
听起来是一个自然而然的过程，之前这么一个方法生成出来的结果和光栅化近似。然而我们只考虑光线弹射一次，光线其实可以弹射很多次，Whitted Style光线追踪就来解决这个问题。
我们还是从光线投射开始，每一个像素找到最近的交点，考虑如果这个点是玻璃球，光线打到这种透明的介质上肯定有一部分能量要被反射掉，另一部分能量要折射进去，很像小时候激光照射水面的实验。
所以光线在交点处做一个镜面反射射出反射光，如上图所示。
同样道理，这个玻璃球还可以折射进去，在内部传播打到另外一个点再折射出来。图中的反射光路弹射了两次，折射光路弹射了三次，也就是说光线可以弹射无限次，Whitted Style它说的就是这么个意思，在任意一个点你可以继续传播这条光线，只需要正确的计算它的反射方向、折射方向就可以。
在 Whitted Style 光线追踪中，它的着色也发生了一点点变化。原本光线投射观察交点是否被照亮就计算着色，但现在在这里光线弹射次数增加，每一个弹射的点都会去计算着色的值加回原像素中。有人会问这里会不会有能量损失？当然了，经过越来越多次数的弹射能量不会一直累加，否则看到的结果是类似过曝的纯白色，比如在最近交点折射和反射要分配能量，都是要考虑进去的。
对于不同类型的光线我们做一个简单的归类，之前我们定义的从眼睛打出来的第一根光线eye ray或者camera ray被称为primary ray；在之后的弹射我们都管它叫做second ray；为了判定可见性与光源连接的叫shadow ray。
这就是Whitted Style光线追踪的做法，可以看到最后把光路结果加到这么一个像素上，得到最终的结果。
从这个结果上我们还可以看到一些其他的信息，比如左侧的阴影就没右侧那么暗，原因在于光线会穿过玻璃球进而收到更多的能量，所以会投射出比较淡的阴影。
Ray-Surface Intersection
Ray Equation
光线在数学上就是一个射线，有一个起点o，传播方向为d，用这两个量就可以简单定义一条光线。在光线上的任何一点我都可以用o + td来表示，因为沿着这条光线无非是从o开始往d方向走了多远。同时由于光线是射线，我们认为光线只能往一个方向传播，所以$0 \leq t \leq \infty$。
这个时候我们再回到之前所说，图形学很少考虑这种边界条件，比如$t$究竟是大于0还是大于等于0意义不是很大。
Ray Intersection With Sphere
那么我们来谈谈光线如何与不同物体求交的最简单情况–光线与球做交点。球在数学上的定义也非常简单，球到任何一个点到球心c的距离都等于半径R得到隐式函数：$(p-c)^2-R^2=0$。
那么现在我们要求光线与球的交点，而交点代表着该点又在光线上又在球上，那么这个点才是叫交点，所以根据点$p$联立起来得到$(o + td - c)^2 - R^2 = 0$，顺理成章就可以解出来：
简单的把联立方程展开，求根公式得到最终的结果t。为了满足t的实际物理意义，结果要确保是正值；根据t的不同有相离（0）、相切（1）和相交（2）三个状态。
Ray Intersection With Implicit Surface
这个问题可以推广到光线和一般性的隐式表面求交，因为交点所以它必在射线和隐式表面上，表达为$f(o + td) = 0$。目前来说数值计算非常发达，可以很快求解出函数根t，所以对于一般的隐式表面也是求出时间，再带入光线方程求出交点。
Ray Intersection With Triangle Mesh
对于显式表面光线和三角形求交是一个非常重要的话题。光线如果知道如何和三角形求交，我就能找到交点判断光线是不是被遮挡。
还有一个很有意思的应用，通过光线和三角形求交点甚至可以判断给你一个点这个点是不是在物体内/外。大家可以在纸上画一条封闭的曲线，然后在这个形状内部点一个点，从任意方向打一根光线出去，判断光线和物体有多少个交点。我们会发现一个很神奇的事情，如果点在形状内，你得到的交点数量一定是奇数，所以如果交点是奇数个那么一定在物体内；偶数个交点在物体外，推广到三维仍然可行。
回到光线和三角形求交，最简单的做法是一个一个三角形判断是不是和光线有交点，找出$t$最小的那个。这个思路肯定是对的，当然这也是非常非常慢的一个事情，加速的方法之后再说。
Ray Intersection With Triangle
三角形一定在一个平面内，那我把这个三角形和光线求交的问题分解成光线和平面求交、判定交点是否在三角形内。
Plane Equation
平面我们可以定义成一个方向和一个点。平面一定有一个法线，但只有法线还不够，平面还可以沿着法线移动，必须定义平面过某个点，也就是立体几何中的点法式。通过直观上几何上垂直的定义，我们可以定义任何一个在平面上的点。
Ray Intersection With Plane
交点一定又在光线上又在平面上。所以点$p$也可以写成$o+td$的形式，带入垂直方程得到$t$。这样我就可以解出光线和平面的交点。
Möller Trumbore Algorithm
A faster approach, giving barycentric coordinate directly
Derivation in the discussion section!
人是懒惰的，人们发现Möller Trumbore算法直接求出光线与三角形的交点。如果两者相交，那么光线表达式也可以表示为三角形的重心坐标表示形式，三个方程三个未知量，可以求解线性方程组。
在线性代数中，求解线性方程组我们使用克莱姆法则。解出之后需要判断是否合理，$t$是否是正值；重心坐标表示必须非负点才能在三角形内。
Accelerating Ray-Surface Intersection
Ray Tracing – Performance Challenges
Simple ray-scene intersection
- Exhaustively test ray-intersection with every triangle
- Find the closest hit (i.e. minimum t)
Problem:
- Naive algorithm = #pixels ⨉ # traingles (⨉ #bounces)
- Very slow!
For generality, we use the term objects instead of triangles later (but doesn’t necessarily mean entire objects)
加速求交是一件必要的事情，如果我们用之前说的最原始的做法当然可以求出光线和整个场景最近的交点，但效率大打折扣。
上面两个场景都是千万级别的三角形数量，如果用原始的方法肯定是不行的，所以我们要想办法加速。
Bounding Volumes
Quick way to avoid intersections: bound complex object
with a simple volume
- Object is fully contained in the volume
- If it doesn’t hit the volume, it doesn’t hit the object
- So test BVol first, then test object if it hits
为了加速有一个很重要的概念：包围盒/体积，通过这种包围盒的方式我们可以加速。比如我有一个复杂的物体，可以用一个相对简单的形状包起来，保证物体一定在这个简单的形状之内，对于图中二维的情况看到一个二维的茶壶，我可以用矩形或圆形框起来，这样就做出来一个包围盒。
包围盒的好处存在一个逻辑问题，如果光线连包围盒都碰不到，那更不可能碰到包围盒中的物体。这个思路虽然简单，但非常有效。
Ray-Intersection With Box
Understanding: box is the intersection of 3 pairs of slabs
对于三维的情况，大家用的最多的就是一个长方体。右边是一个简单的长方体，我们理解为三对平面的交集，通常在实际应用中用的是轴对称包围盒，缩写为AABB。
Ray Intersection with Axis-Aligned Box
如何判定光线和盒子有交点呢？二维情况下定义包围盒，考虑$x_0、x_1、y_0、y_1$，光线在$t_{min}$时间和左边的面$x_0$相交，在$t_{max}$和右边的面$x_1$形成交点；同理对于水平方向也可以求出两个交点，也就是说我对于任何一个对面都可以求出光线的进出时间。
这两个线段实际上求了一个交集，对于光线来说就是实际进入和移出盒子的时间。
Recall: a box (3D) = three pairs of infinitely large slabs
Key ideas
- The ray enters the box only when it enters all pairs of slabs
- The ray exits the box as long as it exits any pair of slabs
For each pair, calculate the $t_{min}$ and $t_{max}$ (negative is fine)
For the 3D box, $t_{enter} = max{t_{min}}$ ,$t_{exit} = min{t_{max}}$
If $t_{enter} < t_{exit}$, we know the ray stays a while in the box (so they must intersect!) (not done yet, see the next slide)
只有当光线进入所有的对面（3）我们才能说光线进入了盒子，而光线只要离开任意一对对面这个光线就已经离开盒子了。我们据此可以立刻得到算法，在三维空间中有三组不同的对面，各计算一次光线进入对面的最小时间和最大时间，对于所有的进入时间$t_{min}$求出最大值，这是最晚光线进入最后一个对面的时间，也是光线真正进入盒子的时间$t_{enter}$；同样道理，只要光线离开任何一个对面，这个光线就离开盒子，最小的离开时间$t_{max}$就是光线离开时间$t_{exit}$。
如果进入时间小于离开时间，说明这个光线在这段时间就在盒子里，反之就没有交点。
However, ray is not a line
- Should check whether t is negative for physical correctness!
What if $t_{exit} < 0$?
- The box is “behind” the ray — no intersection!
What if $t_{exit} >= 0 and t_{enter} < 0$?
- The ray’s origin is inside the box — have intersection!
In summary, ray and AABB intersect iff
- $t_{enter} < t_{exit} \space && \space t_{exit} >= 0$
当且仅当进入时间小于离开时间，并且离开时间非负大于等于0就可以得到最后的结论。
Why Axis-Aligned?