本文主要是Games101 Ray tracing部分的学习笔记。内容主要包括：
- whitted-style 光线追踪，也是古典光线追踪
- 光线与物体求交，加速结构（BVH）等
- 辐射度量学
- 路径追踪
光线追踪的核心逻辑：
三个关于光线追踪的假设：
- 光线是沿着直线传播的。（在物理上并不正确）
- 两个光线发生交叉时不会相互碰撞。（在物理上仍然不正确）
- 光线从光源出发，在物体上不断反射最终进入人眼。（同时遵循互易性——意味着，我们可以认为从眼睛射出光线经过一系列反射最终进入光源）（核心思想）
whitted-style ray tracing
一种递归的实现光线追踪的方法，基本思想是光线在任何地方都可能发生弹射，弹射之后在任何交点都计算它的着色和阴影，然后将这些结果加起来就是像素点最终的颜色。
whitted style风格的光线追踪存在的问题：
- 假设物体永远是高光反射或散射
- 光线在漫反射的物体上就停止继续反射
计算光线和物体的求交
光线是一条射线，由原点和一个有方向的向量定义。用方程表示：
与隐式几何
隐式几何是用方程来表示的，所以光线与隐式几何的求交就是解一个方程组。
与显示几何（网格面）
三角形是表示网格体几何重要的工具，计算与三角形的求交是很重要的， 一种计算方法： 首先计算三角形所在平面与光线的交点，在判断交点是否在三角形内部。 平面可以由平面法向量及平面上的一个点来表示。 
定义了两者方程，求交点就很好解决了，就是简单的解方程组。 
使用AABBs加速光线追踪计算方法：
模型表面有很多的三角形，直接求交计算量会很大。 通过采用包围盒（bounding box ）技术求交可以加速计算过程。（如果光线没有穿过包围盒，那更不可能穿过物体）
如何判断光线是否穿过bounding box哪 ？把盒子理解成由三对相对的平面求交的组合，通过AABBs（Axis-Aligned Bounding boxes），计算光线与盒子的三个平面的交集，
INFO
计算的一个核心思想是： 如果光线进入盒子，那么它必须进入所有的三个对立平面；如果光线离开盒子，只要他离开了任意一个平面即可。
注：这是一种比较巧妙的解决办法。
那么如何建立AABBs哪，这里介绍两种方法：
uniform grids partitions统一网格划分
uniform grids partitions是把空间划分为均匀的格子，建立这些格子与物体的关系（是否包含物体），然后再计算光线穿过的格子（仅计算穿过物体的）。 
uniform grids partitions方法网格划分的数量有一定的讲究，划分的过多计算效率低，划分少起不到加速计算光线与物体求交的效果，业界实践中发现的较好的划分网格的数量：物体数量 x 27
uniform grids partitions方法对于场景中物体数量较多的情况效果不错，但对于较为空旷的场景加速效果不佳。
因为没有结合场景中物体进行划分
spatial partitions 空间划分
spatial partitions的思想是根据场景中的物体的位置，对场景进行划分。有几种划分结构，其中kd-tree是应用较多的一种结构。 
kd-tree是一种二叉树的结构，如上图所示，根据一定的划分规则（考虑场景中物体），一层层递归的将空间一分为二。
为了使划分后的空间均匀，通常每次沿着不同的轴划分，比如第一次x轴平面将空间一分为二，第二次沿着y轴平面，第三次沿着z轴平面......
kd-tree结构的特点：
- 非叶子结点中存储
- 进行划分的轴：x-/y-/z- Axis
- 进行划分的平面的坐标：
- 子节点
- 不存储包含的物体
- 叶子结点
- 存储包含的所有物体
实践中人们通常不使用kd-tree空间划分，因为kd-tree空间划分方式存在一些问题：
- 一个物体可能同时存在与多个节点中（需要计算多次）
- **aabbs盒与三角形求交很难，**因为三角形的三个顶点可能都不在盒子中。在计算划分后的空间节点中包含哪些物体（假设是三角形网格），需要进行计算
Bounding Volume Hierarchy(BVH）
BVH的思想是完全根据物体对空间进行划分。 BVH方法的步骤：
- 找出所有物体的总包围盒bounding box
- 递归的将包围盒中的物体为两部分（子集）
- 计算子集的包围盒 bounding box
- 达到某一条件后，停止继续分割
- 在叶子节点中存储所包含的物体
BVH实践中如何分割节点呢？
- 选择某个维度对包围盒进行分割（x/y/z)
- 技巧1：永远选择最长的轴（x/y/z）进行分割，保证最后分割的空间尽量均匀
- 技巧2： 从空间中从中间物体所在的位置进行分割。（eg：有10个物体，从第5个物体处分割）
BVH结构：非叶子节点中存储：
- bounding box
- 子节点的指针
叶子节点中存储：
- bounding box
- 包含的物体
kd-tree VS BVH
基于空间的划分（kd-tree) 对比 基于物体的划分（object partitions）： ** Spatial partition **(e.g:KD-tree) ：
- 空间会划分为未重叠的区域
- 一个物体可能会包含在不同的区域
object partitions（eg:bvh）:
- 所有的物体会被划分在不同的区域
- 区域会有重叠
辐射度量学 Radiant Energy and Flux(Power)
辐射度量学是基于物理的渲染（Physically Based Rendering）的理论基础。
一些基础概念：
Radiant energy
辐射能量，单位是Q[J = Joule]。
Radiant flux(power)
辐射通量/光通量，单位时间释放(emitted)、反射(emitted)、透射(transmitted)或接受(received)的辐射能量，类似于功率的概念。计做
，单位是W或者流明lumen（lm）。 
Radiant Intensity
辐射强度，光源发出的在单位立体角上的能量/光通量。记做
，单位Candela（cd）。 
solid angle：立体角，
立体角是空间中的一个角。定义方法是在一个单位球里，立体角所对应的球面面积 
Irradiance
辐射度， 每（垂直/投影）单位面积上接收的光通量。记做
，公式为
，单位为（W/m2）。
注意这里单位面积是指与光线垂直方向的面积。如果不垂直需要计算投影到垂直方向上的面积。
和辐射强度不同，**irradiance**会随着距离衰减。因为从光源发射的是固定的光通量，离光源的距离越远，分布的面积就越大，因此Irradiance就越小，是一个平方衰减的关系。
Radiance 辐射/亮度
Radiance是光线传播过程中度量它的属性。 定义：表面上每单位立体角、每单位投影面积上所发射(emitted)、反射(reflected)、透射(transmitted)或接收(received)的Radiant Flux（需两次微分），Radiance记做L。 
Radiance与irradiance及radiance intensity在概念上的区分：
- 每单位立体角的辐射度（irradiance）
- 每单位投影面积的辐射强度（radiance intensity）
Incident Radiance
指到达表面的单位立体角的Irradiance。即它是沿着给定光线到达表面的光(入射方向指向表面) （就是考虑某个方向上，有多少光射到单位表面上） 
exiting radiance
从单位投影面积的表面上发出的辐射强度。 
rradiance VS. Radiance
Irradiance是每单位面积上（可以理解为某个点）接受到的能量总和。 Radiance是每单位面积上从某方向上接受到的能量。 那么在单位面积上，所有方向的Radiance之和就是Irradiance。
BRDF 双向反射分布函数
Bidirectional Reflectance Distribution Function双向反射分布函数
BRDF是从辐射度量学的角度来理解反射现象，光线照射到物体表面，被物体表面吸收，再从物体表面将这部分能量发射出去。 换言之，BRDF就是根据表面性质，给定一个方向的入射光之后，每个方向有多少反射光。
相当于一个比例问题，物体表面接受到的能量按多大比例朝不同方向反射。
the reflection equation 反射方程
反射方程的基本思想是对每一个光源入射方向的radiance与BRDF相乘的结果（某一反射方向
的radiance）进行积分，最后就可以得到表面上某个点在方向的radiance。 
the rendering equation 渲染方程
渲染方程是kajiya提出的
在反射方程的基础上添加自发光影响就可以得到更通用的渲染方程。 
把渲染方程用算子的形式去写： 
- 蒙特卡洛路径追踪
whitted-style ray tracing
平时我们所说的光线追踪一般指的是这个古典的光线追踪。 whitted-style ray tracing不断的弹射光线，每次弹射的位置都会和光源连一条线，如果打到是光滑的物体，会沿着反射方向发射，沿着折射的方向折射。如果光线打到了漫反射的物体，光线就停了，就不会往前走。
路径追踪 path tracing
路径追踪是实现光线追踪的一种算法，路径追踪的提出主要是解决
Whitted-style ray tracing出现的问题，解决非基于物理，不正确的一些问题，来进行改进掉，产生路径追踪的算法。
n=1时的蒙特卡洛积分，是路径追踪。
n!=1时，分布式路径追踪
路径追踪
路径追踪也是一种实现光线追踪的算法，路径追踪是基于物理的（辐射度量学），路径追踪算法可以解决whitted style光线追踪算法存在的非物理的、不正确的一些问题。 路径追踪的核心思想：
- 渲染方程
- 蒙特卡洛积分解渲染方程
- 每个击中的点只随机反射一条光线，但像素采样发射多条光线
- 俄罗斯轮盘赌概率来结束光线不断弹射
前置知识
基础概率论
- **X ： **随机变量
- **X ~ P(x) ： **概率分布函数PDF，表示随机变量X出现的概率。例如：对于掷骰子，1~6出现的概率都为1/6
- **E[X] ： **随机变量X的期望，表示如果对X进行多次(N)取样后的平均值。例如：对于掷骰子，
对于连续函数的概率分布函数PDF：X~P(x) ， PDF函数曲线为下图。 
有： 
蒙特卡洛积分 Monte Carlo Integration
Monte Carlo Integration是一种积分求解方法，它的基本思想是对函数
的区间范围[a,b]进行采样，对于每一个
，都计算
与区间[a,b]组成的长方形的面积，最后对所有的采样结果取平均值，求得
的值。 知道了基本思想，我们来看如何具体的计算Monte Carlo Integration： 
如何理解这个公式哪？我们来看一种最简单的情况，在区间[a,b]中进行均匀的采样： 
所以在均匀采样的情况下，蒙特卡洛积分公式为下式：
这也符合我们的直觉，因为长方形的宽为b-a，高为
对于蒙特卡洛积分有一些性质：
- 采样点越多，求得的结果越准
- 在X上采样，就在X上积分
路径追踪
渲染方程是严格基于物理的，如果我们能按渲染方程来渲染画面，就可以得到真实的效果。
接下来我们就尝试通过蒙特卡洛积分去解渲染方程：
只考虑直接光照的情形
我们首先只考虑直接光照，不考虑反射的情形：
此时渲染方程用蒙特卡洛积分来求解：（注意此时考虑均匀的在半球上采样，
) 
注：课上不理解上式中BRDF函数 fr 部分怎么解，通过作业7理解了，BRDF函数不用解，因为BRDF是作用在材质上的，每一种材质都会有相应的BRDF函数，在现实中，人们还会用仪器去测量BRDF函数。
用伪代码的形式来表述计算过程： 
考虑间接光照
当着色点P接受到了另一个物体上q点反射过来的光线，此时可以把Q点当成另外一个光源，来求解渲染方程。 伪代码如下：我们只需要判断当光线打到了物体上q点时，递归的调用shade函数，计算q点反射到**-wi**方向的光线。 
此时我们已经写出了渲染方程的基本解法，但还存在两个问题：
问题1：光线爆炸问题
假设每个着色点都向外放出N根光线， 那么光线每次的弹射都会造成计算量呈指数型的增长。
当N为1时，即每个着色点只放出一根光线，就不会造成光线爆炸。 
这就是路径追踪（N=1），当N!=1时，是分布式光线追踪。
当只发出一根光线时，会造成噪点（采样过少）。注意我们最终渲染出的是一张图片，所以我们可以从像素点入手，每个像素点发出多根光线，将计算结果进行加权平均，来解决这个问题。 伪代码如下： 
问题2： 无法终止光线弹射（俄罗斯轮盘赌）
目前我们实现的递归算法没有终止条件（光线回无休止的弹射下去），所以我们引入俄罗斯轮盘赌（Russian Roulette RR)来解决这个问题。
俄罗斯
它的基本思想是对每次光线是否继续弹射有一个概率P（0<P<1)，比如说我们在[0,1]之间随机取值，当落在[0,P]时，才继续弹射光线。 RR方法概述：设定概率为P，
- 落在概率P，射出光线并返回着色结果L0/p
- 落在概率1-P，返回结果0
此时，期望值仍为L0。 
这块并不理解
引入俄罗斯轮盘赌后的路线追踪伪代码： 
学习过程中一些不理解的点和思考
在学习的过程中不理解课上从光源采样的渲染方程到给出的伪代码的转变： 渲染方程： 
伪代码： 
不理解的点在于我是对光源面积A上进行积分，用蒙特卡洛积分方法应该写成： 
，为什么伪代码直接写成：在光源上随机采样一个点
，然后就可以用这个点来计算蒙特卡洛积分。
经过看作业7配套的代码，目前自己的理解是：这种做法是一种近似，为了减少计算量，在光源上随机的取一个点进行加权平均计算，作为最终的结果。考虑到实践中我们通常会在一个像素上采样多个点，所以这种近似方式也可以取得不错的效果。
问题3： 采样浪费（效率问题）
还存在一个问题，如上图所示，在低采样率时，我们得到的画面会存在很多噪点。这是因为：我们在物体表面随机的采样光线，很多光线都没有打到光源上，所以这个点看上去就会是黑色的。
我们可以通过直接对光源采样来解决这个问题： 蒙特卡洛积分没有限制我们如何采样，所以我们可以直接对光源进行采样。 但渲染方程是在半球上积分的，所以也要在半球上采样。如何把积分域转换到光源面积A上呢？ 
首先回顾空间角的定义：任意物体投影到单位球上的投影面积，即为该物体相对于该观测点的立体角。 所以可得： 
这样我们可以重写渲染方程： 
这样我们就解决了“光线浪费”的问题。此时我们把场景中物体接受的光线分为两部分：
- 光源本身（直接光照）
- 其他反射 （间接光照）
重写伪代码： 
总结
本节课介绍了光线追踪的两种实现算法：whitted style(古典光线追踪）、路径追踪（现代、基于物理的）。同时详细讲了两种算法的实现。
- 光线追踪与光栅化是两种图形学的渲染方式（不知道怎么说），光栅化的思路是从场景中的物体角度出发，通过一系列的坐标变换后转换为屏幕上的像素点。光线追踪是从像素点出发，向场景中投射出光线获得与物体的交点，然后计算该交点的着色情况。
- 光线追踪的一个核心思路是光线是可逆的，所以可以从相机发出光线；
- 计算光线与物体的交点，可以通过包围盒的思想来加速计算。包括AABBs 和 BVH结构。
- 辐射度量学是基于物理的光照的基础，描述了如何定义光照，定义了一系列描述光照的方法和单位。其中
Radiance是光线传播过程中度量它的属性，定义了在单位面积、单位立体角上的辐射通量Radiant flux - 渲染方程通过一个极为简单的数学函数，描述光线的传播。它也是所有全局光照方法的理论基础。
- 路径追踪是一种通过蒙特卡洛积分解渲染方程的算法。