games101图形学学习笔记

1 线性代数基础

1.1 向量

1.1.1 向量的表示

向量表示既有长度又有方向的量。

其中方向由箭头表示，长度就是线段的距离。
向量也可以用两个点相减表示：
长度计算：
单位向量：

1.1.1 向量运算

• 向量相加
  

• 向量的坐标系表示
  

• 向量相乘
  点乘
  1.点乘的定义
  
  2.点乘的属性
  交换律、结合律、分配律
  
  3.点乘的坐标系表示
  
  4.点乘的作用
  1）计算两个向量的角度(如光线和平面的角度)：
  
  2）计算一个向量在另一个向量上的投影
  如:
  
  求b向量在a向量上的投影b-perpe(红色箭头)
  分析：首先b-perpe一定与a向量(或者a的单位向量)是同一方向，只是长度不一样，所以b-perpe可以表示为b-perpe = k · a的单位向量，接下来只要求k即可，
  而k就是b-perpe的长度，所以k=b的长度 · cos角度
  3）求投影的作用
  可以计算与投影垂直方向的向量(在任意方向上将一个向量进行垂直分解)
  
  4）判断两个向量是相互靠近还是相互远离
  相互靠近，则单位向量点乘的结果逐渐接近1，当平行时等于1
  相互远离，则单位向量点乘的结果逐渐接近0，当垂直时等于0
  5）判断两个向量是同向还是反向
  
  方向相同，则点乘的结果>0
  方向垂直，则点乘的结果=0
  方向相反，则点乘的结果<0

向量叉乘
1.叉乘的定义

2.叉乘的属性

2 光栅化

2.1 MVP变换

链接
MVP变换分别指Model变换、View变换、Projection变换。
打个比方：
Model变换：就是找好相机位置，确定相机坐标；让模特摆好造型
View变换：就是找好相机拍摄的角度
Projection变换：就是按下快门，拍照

首先定义一个相机，
用e表示相机的位置坐标
用g表示相机拍摄的方向
用t表示相机向上摆放的方向

为了方便表示和计算，需要将任意一个相机(e,g,t)移到标准坐标系中，即将
e 移到原点坐标(0,0,0)
g 移到与 -Z 相同的方向
t 移到与 Y相同的方向
注意：默认相机与物体保持相对静止状态，也就是相机怎么移动，物体也要怎么移动

那么要怎么移动呢？
首先将相机坐标移动到原点，如下

然后将
g 移到与 -Z 相同的方向
t 移到与 Y 相同的方向
g x t 移到与 X 相同的方向
如果直接移动，计算非常复杂。所以用逆向思维，将
-Z 移到与 e 相同的方向
Y 移到与 t 相同的方向
X 移到与g x t 相同的方向，
得到如下矩阵，

对该矩阵求逆，即可得到目标矩阵，

以上就完成了Model变换和View变换，接下来进行Projection变换。

Projection变换有两种，分别是Perspective projection(透视投影) 和 orthographic projection(正交投影)

正交投影的理解：
将物体的Z坐标丢弃，然后缩小到[-1,1]^2

一般的正交投影实现方式：
先将物体移动到原点中心，再缩小到[-1,1]^3

透视投影需要先挤压成正交，再进行正交投影。

那怎么挤压呢？

我们从截面观察各点的变化情况，由于远平面f要“挤”到和近平面一样大，所以可推导出图中远平面上的红点的y值会向下移动到y’这么高，所以由相似原理可写出

同理求得x的变化

所以挤压前后坐标变化如下：

为什么乘以z值之后得到的结果还相同？
因为在齐次坐标中，各个维度乘以相同的值得到点和原来一样。

得出挤压后坐标后，就可以得出如下等式：

所以可以得出：

继续利用条件：
由于任何在近平面上的点是不会变的。
任何在远平面的点的z值也不会变。

由以上两条结论可推导出：
n:近平面

可以推出：

可以推出：

再由第二条已知条件，所有在远平面的点的z值不变，可得（f为远平面）：

可以求得：

最后得出透视变正交矩阵：

最后得出透视投影变换矩阵：

做完这些变换后，怎么投射到屏幕上呢？需要做ViewPort(视口)变换。
假设屏幕的宽为width，高度为height，那么视口变换就是把[-1,1]^2的xy平面变到[0,width]x[0,height]，这里为什么没有考虑z轴的变换是因为z轴在之后的其他地方有用。
根据上述可得出视口变换矩阵为：

2.2 光栅化

光栅化就是将图像画在屏幕上，那么怎么画呢？
经过MVP变换后，得到了一个[-1,1]³的正方体。首先忽略Z坐标值，然后将[-1,1]²的xy平面映射到[0,width]x[0,height]屏幕上。

映射矩阵如下：

在这里先定义一下像素，一个像素可以理解为一个正方形。假设一个像素坐标为(x, y)，那么这个像素的中心为(x+0.5, y+0.5)。
计算机图形学中一般都以三角形为画图单位。任务一个物体都可以由若干个三角形表达出来。因此只要考虑三角形与像素之间的关系即可。
现在经过MVP变换后，得到如下三个坐标组成的三角形。

那怎么判断一个像素点是在三角形内还是三角形外呢？
只要设计出如下函数即可：

然后一个像素一个像素的判断：

for (int x = 0; x < xmax; ++x) for (int y = 0; y < ymax; ++y) image[x][y] = inside(tri, x + 0.5, y + 0.5);

那inside(t, x, y)怎么实现呢？
利用向量的叉乘：

只要确定Q点同时在三角形的左边或右边，即可判断Q点是在三角形内还是在三角形外。
第二个问题：一个三角形只包含一部分像素，在判断内外时，没必要把所有像素都判断一遍。那怎么优化呢？
这时候需要用到包围盒的概念。
蓝色的部分就是包围盒，首先判断像素是否在包围盒内，
如果在，则继续判断是否在三角形内，
如果不在，则直接跳过

2.2.1 Z-buffer

在一张图像中，可能有物体遮挡物体的情况，比如这张油画：

树木挡住了地面和山，这个时候如何去画呢？
一种画法是先把山画好，再画地面，再画树木。也就是先画远的物体，再画近的物体。
这个画法在遇到下图时就不管用了：

PQR之间相互遮挡，形成了闭环。

这个时候可以用到Z-buffer(深度缓冲区)。Z-buffer保存的是所有像素的Z坐标值，也就是深度值。
通过比较每个像素的深度值，决定在该像素画什么颜色。具体算法如下：

也就是先将Z-buffer全部初始化为无穷远(一个很大的数也行)。然后在每个三角形中的每个像素判断，
如果当前像素深度值小于Z-buffer中保存的深度值，则将该像素点画上该三角形的颜色。同时更新该像素点的Z-buffer的值。

一个简单的例子：

3 着色shader

着色其实就是给物体打个光，计算不同的光线对物体的明暗影响。比如：
着色前：

着色后：

可以发现，着色后有了明显的明暗对比。有光的地方就亮，没光的地方就暗。

3.1 Blinn-Phong着色模型

Blinn-Phong着色模型主要有3种光线，分别是镜面反射(Specular highlights)、漫反射(Diffuse reflection)和环境光(Ambient lighting)。
首先定义一些概念：

视线方向：v
平面法向量：n
光线方向：l
平面参数：颜色

3.1.1 漫反射Diffuse reflection

漫反射的特点：在所有的方向看平面都是一样的效果。
当物体与光线垂直时，物体会接收光线所有的能量。

当物体与光线有一定的角度时，物体吸收的能量与角度大小有关。

这里再定义一个光照强度的概念：
距离光源为1的地方，光照强度为I
则距离光源为r的地方，光照强度为I/r²

所以可以得出如下漫反射的计算公式：

Ld：漫反射光照强度
kd：漫反射系数，可以是物体表面的颜色，值在[0,255]/255之间，也就是在[0,1]之间。
I/r²：光线到达物体表面时的光照强度
max(0, n·l)：物体表面接收的光照强度

效果：

3.1.2 镜面反射Specular highlights

镜面反射的特点是：当视线方向与反射方向接近时，就能看到镜面反射光线。如图：

为了方便计算，提出了半程向量的概念：半程向量就是光线方向与视线方向的向量和。如图：

可以看出，可以用 半程向量与物体表面法向量的夹角 近似的表示 视线方向与镜面反射方向的夹角。
可以得出如上计算公式：
Ls：镜面反射光照强度
Ks：镜面反射系数，可以是物体表面的颜色，值在[0,255]/255之间，也就是在[0,1]之间。
I/r²：光线到达物体表面时的光照强度
max(0, n·h)^p：在一定角度内才能看到镜面反射光线。
为什么要加个指数p？
因为指数p能够提高真实性。如果没有p，那么在45°时都能看到一定的光线，显然是不真实的。一般p的值在[100, 200]之间。

结合漫反射和镜面反射的效果图：

可以看出Ks越大，表面越亮。p越大，光点越小。

3.1.3 环境光Ambient light

环境光不依赖任何东西。

La：环境光光照强度
ka：环境光系数，可以是物体表面的颜色，值在[0,255]/255之间，也就是在[0,1]之间。
Ia：到达物体表面的环境光光照强度。

结合三种光线的效果图：

3.2 着色频率

观察上面三个球，发现效果不一样。这是因为：
第一个球是以表面(三角形)为单位进行着色的。该方法称为Flat shading
第二个球是以顶点为单位进行着色的。该方法称为Gouraud shading
第三个球是以像素点为单位进行着色的。该方法称为Phong shading

看这个效果图：

可以发现，当顶点数量达到一定程度的时候，用Flat shding也可以满足要求。所以并不是Phong shading就一定是最好的选择。
要想以顶点和像素点进行着色，就需要知道顶点和像素点的法向量n，这个后面再说。

3.3 图形管线(实时渲染管线)

图形管线过程如下：

1 输入3D中的顶点坐标
2 通过MVP变化，计算出对应的在屏幕上的顶点坐标
3 将屏幕上的顶点连接成三角形
4 通过光栅化，将三角形画在屏幕上
5 像素着色
6 输出图形

目前GPU都采用可编程渲染管线shader，也就是用户决定着色。通过编写shader代码，实现着色功能。
OpenGL例子：

uniform sampler2D myTexture; 
uniform vec3 lightDir; 
varying vec2 uv; 
varying vec3 norm; 
void diffuseShader() 
{ vec3 kd; kd = texture2d(myTexture, uv); kd *= clamp(dot(–lightDir, norm), 0.0, 1.0);  //Blinn Phong Diffuse reflectgl_FragColor = vec4(kd, 1.0);  //输出颜色	
}

3.4 纹理映射

纹理就是一张图，纹理中的每个坐标由(u, v)表示。所谓映射，就是计算出与2D屏幕坐标(x, y)相对应的纹理坐标(u, v)。然后将(u, v)的颜色信息贴到2D屏幕中。
纹理的问题：
1 纹理比屏幕尺寸小
就用双线性插值匹配
2 纹理比屏幕尺寸大
用MipMap
纹理的其他作用：待补充。

3.5 三角形插值：重心坐标

一般都是知道三角形三个顶点的各种属性，然后要实现三角形内各个像素的属性的循序渐变。所谓的属性包括纹理坐标、颜色、法向量等等。这时候要用到重心坐标。
重心坐标定义如下：

三角形内部的每个点坐标都可以由三个顶点坐标的线性组合组成。A、B、C对应的权值分别是α、β、γ。α、β、γ就是所谓的重心坐标。
比如A的重心坐标：

比如重心点的重心坐标：

通用的重心坐标计算公式：

比如颜色插值：

3.6 阴影Shadow-Mapping

注意：着色点在阴影内，则该点不能被光源看到。
在光栅化中，想要实现阴影，主要有两步。
第一步，从光源看向场景，做一次光栅化，记录整个场景的深度图。

第二步，从视角处看向场景，将每个点重新投影到光源处，计算出此时的深度，再与第一步中得到的深度做比较：
如果第二步的深度与第一步的深度近似相等，则该点能被光源看到。
如果第二步的深度远大于第一步的深度，则该点不能被光源看到，即该点处有阴影。

4 几何Geometry

几何表示的是物体或模型的形状。
几何可以隐式(Implicit)表示和显示(Explicit)表示。

4.1 隐式表示

所谓的隐式表示，就是通过一个表达式或者函数来表达物体的形状。比如：
x² + y² + z² = 1，或f(x, y, z) = x² + y² + z² - 1表示一个球体。
隐式表示的优点是能够直接计算出特定的点是否在物体上。

如果函数计算出的结果小于0，则说明该点在球内
如果函数计算出的结果等于0，则说明该点在球上
如果函数计算出的结果大于0，则说明该点在球外

隐式表示的缺点是无法直接看出或算出物体的形状。
比如下图：直接通过表达式无法看出物体的形状。

4.2 显示表示

显示表示就是所有的点的坐标都给出来，或者通过映射的方式给出来。比如

通过左边的(u, v)坐标可以计算出右边的马鞍面的(x, y, z)坐标。
又比如：

显示表示的优点是可以直接看出物体的形状，但是很难判断指定的点与物体的位置关系，是在内还是在外。

4.3 更多的隐式表示

4.3.1 Constructive Solid Geometry(CSG)

通过布尔运算，将多个隐式几何组合到一起。

4.3.2 Signed Distance Functions

Signed Distance Functions，即有向距离函数。
使用距离函数，可以得到如下效果：

也就是两个物体融合到一起，融合的程度由距离函数决定。
那什么是距离函数呢？
距离函数定义：空间中任意一点到所在物体表面任意一点的最近距离。距离函数的值可以是正的也可以是负的。如果是正的，则空间中的点在物体外，如果是负的，则该点在物体内。
看下图：

假设物体A坐标1/3被挡住了是黑色的，物体B左边2/3被挡住了是黑色的。如果把A和B直接线性组合就得到右上角的图，左黑，中间灰，右白。如果我们想得到右下角左黑右白，就要用SDF。
可以看出
A物体的1/3左边的SDF是负的，1/3右边是正的。
B物体的2/3左边的SDF是负的，2/3右边是正的。
将A和B的SDF值相加，等于0处的地方就是两者融合的终点位置。也就是融合的程序。
再看下图：

假设正方体和球体中间空间中有个点，离正方体的距离为1，此时正方体在该点的SDF值为1。那么找到球体内一个点的SDF值为-1。再将正方体的右上角平移到该点，则实现了正方体与球体的融合。

4.3.3 Level Set Methods

Level Set Methods，即水平集。(没有理解)

4.4 更多的显示表示

4.4.1 Polygon Mesh多边形表示

Polygon Mesh，即多边形面。基本上都是用三角形或四边形。
比如下图：

在图形学中用一种特定的文件格式表达一个物体的形状。
文件格式称为The Wavefront Object File，简称.obj文件。通过指定顶点坐标、法向量、纹理坐标。然后将他们联合起来。如下图：

v：表示顶点坐标
vt：表示纹理坐标
vn：表示每个面法向量
f：表示三角形
比如第一个f，就是由顶点(5,1,3)、纹理(1,2,3)、法向量(1)组成的一个三角形。将所有的三角形粘合到一起，就是一个正方体。

对于多边形表示有一个问题，就是多边形的数量或者密集程度问题。如下图：

可以看出，多边形的数量直接影响了模型的真实程度。所有就有了提高多边形数量和降低多边形数量的方法。
提高多边形数量叫做网格细分(Mesh Subdivision)。如下图
降低多边形数量称为网格简化(Mesh Simplification)。如下图：

4.4.1.1 网格细分

4.4.1.1.1 Loop细分

注意：Loop细分只能用于三角形的细分。

Loop细分，主要分为两步，
第一步，将大的三角形划分成更多的小的三角形。

第二步，更新新的顶点和旧的顶点的坐标。

划分三角形是非常容易的，就是取每条边的中点，分别连起来就可以了。顶点坐标怎么更新呢？
对于新的顶点，方法如下：

如图，其中白点代表新的顶点，这个顶点在两个三角形的共线上(不在边界线上)。要求该点的坐标，就是把周围4个顶点的坐标做一个加权求和。公式就是3/8 * (A + B) + 1/8 * (C + D)。

对于旧的顶点，方法如下：

如图，其中白点表示待更新的旧顶点。在这里要定义两个新的概念，分别是：
n：表示顶点的度，也就是该顶点连接了几条线。
u：权值。
最后得出计算公式：(1 - n*u) * original_position + u * neighbor_position_sum。
通过以上公式，可以看出，当该点的连接的线越多，也就是n越大，该点自身所占的权值就越低。反之，当该点的连接的线越少，也就是n越小，该点自身所占的权值就越大。

4.4.1.1.2 Catmull-Clark细分

注意：Catmull-Clark细分可以处理三角形和四边形，以及多边形。
对于下图所示的包含四边形和三角形的形状：

只需要取每个边的中点，以及每个多边形的中点，并将中点两两连接起来，就可以得到细分后的图形。如下图所示：

在上图中，顶点位置坐标已经更新了。
那顶点位置坐标怎么更新的呢？如图：

其中f表示多边形的中点，e表示边的中点，p表示就顶点。

细分效果图如下：

4.4.1.2 网格简化

网格简化要用到边坍缩的方法。那什么是边坍缩呢？如图

就是将一条边的两个顶点融合到一起，这样两个顶点就变成了一个顶点。
那模型中边有那么多，怎么确认哪些边坍缩后影响最小呢？
那就要用计算每条边的二次度量误差的值，值最小的最先坍缩。
那什么是二次度量误差？待补充。

4.4.2 贝塞尔曲线

链接1
链接2
我的理解：贝塞尔曲线就是通过确定的几个点，按照某种规则计算出一个点。如果确定的几个点有n个，就能按照规则计算出n个点。再将这n个点连接就是贝塞尔曲线。
举个例子：

有b0， b1，b2三个点组成的两条线段。首先在线段b0b1上距离b0点t位置处取一点b01，在线段b1b2上距离b1点t位置处取一点b11，连接b01和b11，再在该线段t位置处取一点b02。则b02就是最终所求的点。
按照同样的规则，将线段上所有的点求出对应的最终点，连起来就是贝塞尔曲线。
动图展示：

更多的点：

4.4.2.1 贝塞尔曲线代数表示

先看三个点组成的贝塞尔曲线的代数表示：

其中的b都代表坐标值。可以发现，最终展开式是一个(s + t)² 的形式，其中s=1-t。
可以推出，当有n+1个点组成的贝塞尔曲线表达式：

其中用到伯恩斯坦(Bernstein)多项式。

4.4.2.2 分段贝塞尔曲线

对于下图10个控制点画出来的贝塞尔曲线，想要移动点控制线的形状比较麻烦。因此可以应用分段贝塞尔曲线。

分段贝塞尔曲线，最常用的就是每4个控制点得到一条贝塞尔曲线。如下图

使用分段贝塞尔曲线，只需要注意连接点处的平滑性。所谓平滑性，就是两条线在连接点处的一阶导数相等。

4.4.3 贝塞尔曲面

贝塞尔曲面效果图如下：

通过4x4个控制点，就可以得到一个贝塞尔曲面。那怎么实现的呢？

通过最左边4个点就可以得到一条贝塞尔曲线，同样的其他3x4个点，也能得到3条贝塞尔曲线。
然后在4条贝塞尔曲线上分别取得4个点，又可以组成一条贝塞尔曲线。
将4条贝塞尔曲线上所有的点都组成贝塞尔曲线，就形成了贝塞尔曲面。如图：

5 光线追踪Ray Trace

假设从眼睛中射出一条光线，经过成像平面中的某个像素后，射到场景中的最近的某物体上的某一点。("最近"这个词就解决了光栅化中Shadow Mapping的阴影的深度测试问题)。
确定了光线的位置后，就要看这个点会不会被光源照亮。怎么做呢？
就是从该点连接一条线到光源。如果没有任何物体阻挡，则可以确定该点可以被光源照亮。
然后就可以计算该点的着色，并将颜色值写到成像平面的像素中。

5.1 Whitted-Style光线追踪

Whitted-Style光线追踪可以用来出来光线在场景中不断弹射和折射的情况。

光线在射到物体上时，会发生反射和折射。经过反射和折射后会照射到别的物体上的某个点。然后将这些点与光源连接，如果没有物体遮挡，则说明该点能够被光源照亮，则对该点进行着色计算，并将计算的颜色值加到成像平面的像素上。(其他的所有点都是一样的)

当然，光的能量在反射和折射后，是不断损失的。
重新定义光线名称：

效果图：

5.1.1 光线与平面的交点

首先定义光线：光线是一条射线，并随着时间越来越远。

O：代表光源位置
d：代表照射方向

5.1.1.1 光线与隐式表面的交点

交点就意味着该点既在光线上也在球上。那么知道表达出球的等式，代入即可求解。

其中，p是光线与球的交点。

经过计算，可以得到两个时间t。要选择实数且大于0的。通过t也可以看出光线与球有几个交点。
同样，光线与其他隐式几何，可以用同样的方法计算。如下图：

5.1.1.2 光线与显示表面交点

要求光线与三角形交点，可以分为两步：
第一步，计算光线与三角形所在平面的交点
第二部，判断该点是否在三角形内。
先完成第一步：
首先定义一个平面：一个点和一条法线就可以定义一个平面。

平面内的任意一点与p^’ 的连线都与法线垂直。

因此，可以代入后，可以得出t值。

这种方法比较麻烦，下面Möller Trumbore 算法比较简洁，可以直接得出t值。

等式左边是光线的表达式，右边是三角形内任意一点的重心坐标表达式。可以看出，只要计算出t、b1、b2即可。计算结果如下：

5.1.2 AABB包围盒

因为一个场景内三角形的数量有很多，我们在处理的时候，不可能遍历每一个三角形判断光线是否与它相交。因此，需要提出一些加速方法，包围盒就是一种加速方法。所谓的包围盒就是用一个封闭空间将场景内的某些物体包围起来，如果光线都不与包围盒相交，则说明光线不会与包围盒内的物体相交。如光线与包围盒相交，再继续判断光线是否与物体相交。包围盒内有一种名为AABB的包围盒。
AABB，即Axis-Aligned Bounding Box，翻译过来就是轴对称包围盒。
在二维平面中，包围盒是一个矩形。在三维世界中，包围盒是一个长方体结构。
可以认为这个长方体是由3对平行的面包围而成，且每对平面之间都是垂直的。如下图：

那么怎么判断光线是否与这个包围盒相交呢？
由于3D的比较复杂，由繁入简，先考虑2D的情况。

在上图中，O点表示光源起点，d表示光线方向。
最左边表示光线与轴平面x相交的情况，显然可以计算出，光线进入该平面的时间t_xmin 和光线从该平面离开的时间t_xmax 。
同理，可以计算出光线进入轴平面y的时间t_ymin 和光线从轴平面y离开的时间t_ymax 。
接下来只要选择进入时间的最大值(即t_enter = MAX(t_xmin ，t_ymin ))和离开时间的最小值(即t_exit = MIN(t_xmax ，t_ymax ))。
为什么要这样选择呢？
因为光线只有进入所有的平面才算进入包围盒，所以进入的时间选最大的。只要光线离开第一个平面，就算离开包围盒，所以离开的时间选最小的。

根据现实情况，可以得出下列结论：
如果t_exit小于0，则包围盒在光源后面，也就是光线与包围盒没有交点。
如果t_enter小于0且t_exit大于等于0，则光源在包围盒中，则一定有交点。
如果t_enter小于t_exit，则光线一定经过包围盒。

5.1.2.1 使用包围盒加速

5.1.2.1.1 均匀网格 Uniform grids

第一步：创建一个包围盒

第二步：在包围盒内划分网格

第三步：保存每个与物体相交的网格

第四步：判断光线是否与网格相交，若相交，则判断光线是否与物体相交。

注意：划分表格的密度应该是物体的27倍左右。

使用实例：
对于这种物体铺满画面的可以用该方法。

5.1.2.1.2 空间划分Spatial partitions

空间划分主要有3种，如图：

Oct-Tree：八叉树划分，就是按照等分的方式划分。
KD-Tree：与八叉树类似，只是不在等分划分。
BSP-Tree：不再横平竖直划分。
主要说明KD-Tree。
假设下图是KD-Tree的一种划分结果：

假设从坐上往右下有一条光线，如图：

那么怎么判断光线是否与物体相交呢？
第一步，首先判断与根节点包围盒A是否有交点。发现有交点，同时A节点还有字节点，则继续判断与A的两个子节点是否相交。如图：


第二步：与A的两个子节点分别判断，发现1节点是叶子节点，则判断光线是否与1节点内的物体相交。发现B节点不是叶子节点，则分别判断光线是否与B的两个叶子节点相交。
第三步：以此类推。。。最终判断到最外层叶子节点

这种方法有两个问题：
1 三角形与包围盒是否相交难以判断
2 一个物体可能在多个空间中

使用实例：
对于这种空间有大部分空白的图像，适合这种方法。

5.1.2.1.3 物体划分Object partitions

为了解决上述两个问题，可以使用物体划分的方式，物体划分也叫Bounding Volume Hierarchy (BVH)。
如图，一个包围盒内有多个三角形：

将包围盒内的三角形划分成两队，并重新形成两个包围盒。

可以发现物体只存在一个包围盒中。
继续划分：

当每个包围盒中有5个左右的三角形时，就可以停止划分。

说明一下二叉树的数据结构：
根节点和中间节点保存：包围盒和子节点
叶子节点保存：包围盒和物体列表
伪代码：

Intersect(Ray ray, BVH node) {if (ray misses node.bbox) return;　//如果没有遇到包围盒则返回if (node is a leaf node) //如果是一个叶子节点test intersection with all objs; //判断光线是否与包围盒内所有物体相交return closest intersection; //返回最近的交点hit1 = Intersect(ray, node.child1); //递归判断字节点1hit2 = Intersect(ray, node.child2); //递归判断字节点2return the closer of hit1, hit2;
}

5.2 辐射度量学Radiometry

辐射度量学可以按照正确的物理规律进行光线的能量计算。
首先看几个概念：
Radiant Energy：就是能量Q，单位是焦耳J
Radiant flux (power)：就是功率，用Φ表示，单位是瓦特W或者流明lm
还有3个概念如图：

Radiant Intensity：光从光源射出来的能量(power)。
Irradiance：光在接收处的能量(power)
Radiance：光在传播过程中的能量(power)

5.2.1 Radiant Intensity

首先解释Radiant Intensity，定义：在单位立体角上的功率(power)。公式表示如下：

Radiant Intensity的单位是W/sr或lm/sr或cd。

那什么是立体角呢？先考虑二维的情况。

在二维的圆中，角度可以由弧长/半径来表示。整个圆的角度为2Π。
在三维世界中，

立体角可以由球表面面积/半径的平方来表示。整个球的立体角为4Π。
接下来计算单位立体角，

矩形A的面积=边长x边长。

通过下列公式，可以求出Radiant Intensity：I

所以可以计算灯泡的Radiant Intensity：

5.2.2 Irradiance

Irradiance的定义：单位面积上的功率(power)。用字母E表示，单位是W/m² 或lm/m² 或lux。

当光线与面有一个角度时，就需要乘以这个角度的余弦。

5.2.3 Radiance

Irradiance结合了Radiant Intensity和 Irradiance。
Radiance定义：在单位立体角和单位面积上的功率(power)。
单位是W/sr m² 或lm/sr m² 或cd/m² 或nit。

所以Radiance可以说是单位面积的Radiant Intensity(也就是输出光线能量)；有可以说是单位立体角的Irradiance(也就是输入光线能量)。

所以出射(反射)Radiance可以表示为：
单位面积的Radiant Intensity

所以入射Radiance可以表示为：
单位立体角的Irradiance

5.2.4 Bidirectional Reflectance Distribution Function (BRDF)

Bidirectional Reflectance Distribution Function (BRDF)：双向反射分布函数

Irradiance vs. Radiance

Irradiance ：表达的是dA面积上接收到的来及各个方向的power。
Radiance：表达的是dA面积上接收到的来自dw方向的power。
所以有：

Reflection at a Point

BRDF
备注：没有理解
BRDF是用来计算每个入射方向经反射后从w_r 方向射出的power。

反射方程

渲染方程

渲染方程的理解

5.3 概率论复习

概率

期望

概率密度函数
链接

随机变量函数

5.3.1 Monte Carlo积分

链接

对于任何形状的概率密度函数，若想求[a, b]范围上的概率，也就是[a, b]上的定积分。都可以转换为下列等式：

举例：
设一个函数为f(x)=3x² ，计算它在[a, b]上的积分。假设[a, b]为[1, 3]，则积分结果为3x3² - 1x1² = 26。
若用Monte Carlo积分，可以得出等式：

那么，若样本是{2}，则F₁(x) = 24；若样本是{1, 2, 3}，则F₃(x) = 28；若样本是{1.0, 1.25, 1.5, 1.75, 2, 2.25, 2.5, 2.75, 3.0}，则F₉(x) = 26.5。以这个趋势，不断在逼近的积分结果26。若随机采样10k个均匀的随机采样点，那么它的结果一定是逼近26的。

5.4 PathTracing

前面说过Whitted-style光线追踪，效果挺好的。但是它有两个问题：
第一，它可以处理镜面反射，但无法处理Glossy反射。

第二，它可以处理直接光照(光源直接照射目标像素后反射)，但不能处理间接光照(光源在照射某个物体后反射出来的光再照射目标像素)。

左边是直接光照，右边包含间接光照

Whitted-style光线追踪是有问题的，但是前面说过的渲染方程是完全正确的，因为它是按照物理规律计算出来的。

要想使用渲染方程，还要解决两个问题：
1 在半球上面进行积分
2 递归的执行

5.4.1 在半球上积分

为简化计算，首先只考虑直接光照，不考虑物体本身亮度和间接光照。
计算过程如下：

可以转化为：

所以可以写出算法：

shade(p, wo)Randomly choose N directions wi~pdf //随机选择N个方向Lo = 0.0 //初始化为0For each wi //对于每一个方向wiTrace a ray r(p, wi) //跟踪p到wi的方向If ray r hit the light //如果碰到光源，则计算LoLo += (1 / N) * L_i * f_r * cosine / pdf(wi)Return Lo

关于方向wi，如下图：
默认光源是一个面积光源，不是点光源

接下来，把间接光照考虑进去。

此时P接收的是经过Q点反射后的光线。对于Q反射后的光线，可以认为是光源经过Q点后直接光照的结果。所以只要在算法中，加一层对Q点的直接关照计算即可。

shade(p, wo)Randomly choose N directions wi~pdfLo = 0.0For each wiTrace a ray r(p, wi)If ray r hit the lightLo += (1 / N) * L_i * f_r * cosine / pdf(wi)Else If ray r hit an object at q//如果光线打到物体q则计算q点直接光照Lo += (1 / N) * shade(q, -wi) * f_r * cosine / pdf(wi)
Return Lo

这样就完美了吗？还没有。
因为在上述算法中，考虑的是对半球上随机N个方向进行计算(N越多，Monte Carlo积分越准确)。但N越多，一旦经过间接光照，就会发散成N^反射次数 条光线，这个计算量是非常大的。因此，只需要考虑N=1时，就不会有指数级的计算量。因为1ⁿ = 1。
那么可以修改算法：

shade(p, wo)Randomly choose ONE direction wi~pdf(w) //只考虑一个方向的光线Trace a ray r(p, wi)If ray r hit the lightReturn L_i * f_r * cosine / pdf(wi)Else If ray r hit an object at qReturn shade(q, -wi) * f_r * cosine / pdf(wi)

这样就完美了吗？还没有。
前面提到，N越大，Monte Carlo积分越准确。现在N只有1，那么Monte Carlo积分将会严重的失真，对整个画面将产生很多的噪声。那怎么办呢？
这时候需要计算经过同一个像素的多个光线，并对他们的值求平均。如图

算法如下：

ray_generation(camPos, pixel) //输入相机位置和像素位置Uniformly choose N sample positions within the pixel //在像素内均匀选择N个位置pixel_radiance = 0.0For each sample in the pixel //对于像素内的每一个位置Shoot a ray r(camPos, cam_to_sample) //连接相机和像素位置，形成一条光线If ray r hit the scene at p //如果光线打到物体p，则计算pixel_radiance pixel_radiance += 1 / N * shade(p, sample_to_cam) Return pixel_radiance

5.4.2 递归问题

这样就完美了吗？还没有。
回到shade算法

shade(p, wo)Randomly choose ONE direction wi~pdf(w) //只考虑一个方向的光线Trace a ray r(p, wi)If ray r hit the lightReturn L_i * f_r * cosine / pdf(wi)Else If ray r hit an object at qReturn shade(q, -wi) * f_r * cosine / pdf(wi)

我们发现在这个递归算法中，它没有一个结束的点。这会导致程序一直往下执行，不会返回。
那我们能给它指定递归的次数吗？先看效果图：
递归3次：

递归17次：

可以发现，递归17次比递归3次更亮一些。而真实的光线是不会停下来的，会一直反射。也就是说递归次数越多，图像越真实。但又不能真的无限递归，那怎么办呢？
这里就需要提高俄罗斯轮盘赌。

这个枪的弹夹能放6颗子弹，如果放进去2颗子弹。则射出子弹的概率是2/6，没有子弹射出的概率是4/6。假设没有子弹射出概率为P， 则有子弹射出概率为1-P。
同样，我们同样设置一个概率P：
让光线递归后，有P的概率继续递归下去，有1-P的概率停止递归。
同时规定：
如果递归计算下去，则返回Lo / P
如果没有递归计算下去，则返回0。
这样就可以得出期望仍然是Lo：E = P * (Lo / P) + (1 - P) * 0 = Lo

那么修改算法：

shade(p, wo)Manually specify a probability P_RR //指定P_RR的值Randomly select ksi in a uniform dist. in [0, 1] //随机选择一个[0,1]范围内的数ksiIf (ksi > P_RR) return 0.0; //假设P_RR=0.8，若ksi大于0.8，就返回0// Randomly choose ONE direction wi~pdf(w)Trace a ray r(p, wi)If ray r hit the lightReturn L_i * f_r * cosine / pdf(wi) / P_RRElse If ray r hit an object at qReturn shade(q, -wi) * f_r * cosine / pdf(wi) / P_RR

这样就完美了吗？还没有。
看效果图：

左边的像素采样少，图像质量差。右边像素采样多，图像质量好。
那怎么解决这个问题呢？
首先分析问题的原因，先看下图：

每个图的面光源的大小不一样，左边的最大，那么只要射出5条光线就能打到光源；中间要500条光线打到光源；右边的要50000条光线才能打到光源。那么可以想象出，光源越大，打到光源概率越大，对该像素着色概率越大。
这就可以解释上面效果图的差别：低SPP的时候，打到光源概率低，着色概率小。高SPP，打到光源概率高，着色概率高。

那怎么在低SPP的时候，提高打到光源的概率呢？
解决方法就是：不在随机任意方向wi上采样了，在光源上面采样。那怎么做呢？

假设光源的面积大小为dA， 则Monte Carlo积分公式中的p(X_i) = 1 / dA。

可是渲染方程中是对wi进行积分的，怎么将对w积分转为对A积分呢？如图：

根据立体角的定义：球表面面积/半径的平方。因此可以得出：

所以渲染公式可以变成：

对于直接光照可以用上面的方法转换，对于间接光照还是按照前面的方法不变。所以可以得出新的算法：

shade(p, wo)// Contribution from the light source. 直接光照Uniformly sample the light at x’ (pdf_light = 1 / A)Shoot a ray from p to x’ //判断直接光照光线是否被别的物体遮挡If the ray is not blocked in the middle //若没有遮挡L_dir = L_i * f_r * cos θ * cos θ’ / |x’ - p|^2 / pdf_light // Contribution from other reflectors. 间接光照L_indir = 0.0Test Russian Roulette with probability P_RRUniformly sample the hemisphere toward wi (pdf_hemi = 1 / 2pi)Trace a ray r(p, wi)If ray r hit a non-emitting object at qL_indir = shade(q, -wi) * f_r * cos θ / pdf_hemi / P_RRReturn L_dir + L_indir

这就完美了吗？是的，完美了！