引言
最近打算重新温习一下 GAMES101 现代计算机图形学入门的课程内容，做一个总结与梳理比较重要的内容以便快速复习。
Review of Linear Algebra
Vector
Normalization
Addition
Multiplication
Dot Product
通过判断点乘的正负判断两个方向向量有多么接近：
dotProduct > 0 ? forward: backward; |
Cross Product
叉乘向量的方向用右手螺旋定则判断，类似于大拇指点赞。
叉乘没有交换律，但分配律和结合律依然存在。
叉积有两个作用：
判定左右（不经过逆/顺时针旋转保持方向一致）
判定内外（叉乘符号保持一致）
Matrix
Matrix-Matrix Multiplication
矩阵间的乘法规则为”前行乘后列”，算第几行第几列就去找左矩阵第几行和右矩阵第几列。
矩阵间的乘法不满足交换律，但满足结合律和分配律。
Transpose
矩阵转置就是把行列互换。
Identity Matrix
只有对角线上有非零元素的矩阵被称为对角阵，单位矩阵则都为 1。矩阵与矩阵的逆相乘得到单位矩阵。
Transformation
2D Transformation
Scale Matrix
Reflection Matrix
Shear Matrix
水平方向的切变。
Rotate Matrix
旋转默认原点为中心逆时针方向，推导过程如下：
Homogenous Coordinates
齐次坐标服务于平移变换，把二维的点增加一个纬度变成齐次坐标，所有变换形式上简化为一个矩阵乘以一个向量。
2D Transformation
Inverse Transformation
Composing Transforms
变换顺序从右到左非常重要，可以视作交换律的不可用。
旋转时的中心点始终为原点，所以保证旋转时物体在原点，之后再做其他的变换操作。
3D Transform
Scale & Translation
Rotation
$Z x X = Y$
推导过程如下：
Viewing Transform
View/Camera Transform
相机身处原点，法向为 Y，朝向为 -Z 的标准位置。
Model Transform
视图矩阵需要先平移至原点，然后一次旋转到标准轴。
齐次坐标先做平移后做旋转。
虽然任意轴旋转到标准轴很难推导，但是这个逆过程标准轴旋转到任意方向还算简单，又因为旋转矩阵的逆矩阵与转置矩阵相等最后可以推导出来。
Projection Transform
透视投影(P)会有近大远小的现象，而正交投影(O)没有。
Orthographic Projection
- 相机从原点看向 -Z 方向，头顶朝向 Y 方向
- 扔掉 Z 轴
- 缩放变换 X、Y 至 [-1, 1]
首先把立方体中心从负方向移到原点，然后再做一个缩放把长度变为 2。
Perspective Projection
透视投影可以拆分为两步：首先将 Frustum 挤成 Cuboid；然后直接用正交投影。
使用 (0，0，n) 和 (0，0，f) 两个特殊点代入，就可以得出最终的矩阵
Viewport Transform
- 长宽比：aspect ratio
- 垂直可视角度：fovY(field-of-view)
Rasterization
Screen Space
- 像素 (x, y) 的中心为 (x + 0.5, y + 0.5)。
- 以左下角为原点，屏幕的像素空间从 (0, 0) 到 (width - 1, height - 1)。
视口变换从 [-1, 1]^2 空间映射到 [0, width]x[0, height]。
Sample
给予屏幕空间任何一点，需要知道是否在三角形内。
for(int x = 0; x < xmax; ++x) |
之前叉积可以判断点是否在三角形内。
Aliasing
采样造成的走样问题本质都是信号变化太快以至于采样速度跟不上产生瑕疵 Artifact。
Antialiased Sampling
频率分析上有可能完全不同的函数采样出完全相同的结果，而我们无法区分，这种现象就叫作走样。
- 增加采样率
- 先做模糊再做采样
MSAA
通过更多的 Supersampling 采样点来进行反走样
Antialiasing Today
Z-Buffering
Painter’s Algorithm
Z-Buffer
Z-buffer Algorithm
for (each triangle T) |
Z-Buffer Complexity
Shading
Definition
韦氏字典告诉我们着色引入了明暗和颜色的不同。在图形学中 Shading 定义为 对不同物体应用不同材质的过程。
Blinn-Phong Reflectance Model
该图展示了 Specular highlights-高光、Diffuse reflection-漫反射 和 Ambient lighting-间接光照。
n着色点法向v视野朝向I光照方向
Diffuse Reflection
漫反射就是一根光线打到点上，会被均匀反射到不同的方向上去。
当着色点表面朝向和光线有一定夹角的时候，会发现明暗不同，夹角决定物体的亮度。
Lambertian(Diffuse) Shading
$$
L_d = k_d (I / r^2) max(0, n \cdot l)
$$
假设点光源离 Shading Point 有一定距离 r，定义光源的强度为 I，Kd 为漫反射项系数（可以直观理解为吸收能量后反射部分能量，1 表示该点完全不吸收能量，0 表示所有光线都被吸收了没有能量反射出去）。这里取最大值是避免点乘为负的情况，这种情况不可能有贡献，没有物理意义。
Specular Term(Blin-Phong)
高光项反射接近镜面反射，观察方向 v 足够接近高光方向 R 时方可看到高光。
$$
L_s = k_s(I / r^2) max(0, n \cdot h)^p
$$
高光项的衡量标准可以转化为半程向量 h 与着色点法线 n 是否接近，相较于反射更容易计算。
指数 p 将夹角的余弦函数的变化程度加剧，符合高光项仅存在于一小部分的事实，用于控制高光大小。
Ambient Term
$$
L_a = k_a I_a
$$
假设环境光与观测方向无关，接受环境的光永远是相同的，强度为 Ia，环境光系数为 Ka。
Blinn-Phong Reflection Model
$$
L = L_a + L_d + L_s = k_a I_a + k_d(I / r^2)max(0, n \cdot l) + k_s(I / r^2)max(0, n \cdot h)^p
$$
Shading Frequencies
Flat Shading
求出每个 三角形 的法线，根据 Shading 结果对三角形面片进行着色。
Gouraud Shading
求出每个 顶点 的法线，根据 Shading 结果对三角形内部进行插值算出来。
Phong Shading
求出每个 像素 独立的法线方向，根据 Shading 结果对每一个像素进行着色。
Graphics Pipeline
Vertex Processing
在顶点这里做 Model-View-Projection 变换。
Triangle Processing
屏幕采样判断点是否在三角形内部发生在光栅化阶段。
Rasterization
光栅化产生像素后需要判定可见性和深度缓存相关。
Fragment Processing
着色过程同时发生在顶点和像素阶段，主要考虑不同的着色频率。
Texture Mapping
Barycentric Coordinates
第一个话题是如何在任意三角形内部进行插值。
首先我们为什么要对三角形进行插值？之前我们很多操作都是在三角形的顶点上，在三角形内部我们需要一个平滑的过渡。
其次是插值的内容，可以是纹理坐标、颜色法线、法线坐标等等……
在三角形 ABC 所形成的平面内任何一点(x, y)，都可以表示成这三个顶点 ABC 的线性组合。
重心坐标公式。
Applying Textures
Texture Magnification(easy case)
Bilinear interpolation
$$
1D: lerp(x, v_0, v_1) = v_0 + x(v_1 - v_0)
$$
水平方向和竖直方向都做一次线性插值，被称为双线性插值。
Texture Magnification(hard case)
远处是摩尔纹，近处是锯齿，也是之前我们说的走样问题。
Application of Texture
Environment Map
我们可以用纹理去描述环境光长什么样，再用环境光去渲染其他物体。
Environmental Lighting
Affect Shading
Bump Mapping
$$
dp = c * [h(p + 1) - h(p)]
$$
dp 用差分方法求出，再通过逆时针旋转得到法向 n。
- $dp/du = c_1 * [h(u + 1) - h(u)]$
- $dp/dv = c_2 * [h(v + 1) - h(v)]$
Displacement Mapping
Displacement mapping 位移贴图移动了顶点的位置，而凹凸贴图没有改变任何的几何。
Geometry
Introduction
Examples of Geometry
图形学将几何划分为 隐式几何(Implicit) 和 显式几何(Explicit)。
“Implicit” Representations of Geometry
隐式几何描述的是顶点之间的特殊关系，可以描述为 $f(x, y, z) = 0$，例如球体的解析式 $x^2 + y^2 + z^2 = 1$。
“Explicit” Representations of Geometry
显式几何则会通过直接提供顶点或者参数映射方法定义。
Many Implicit Representations in Graphics
Constructive Solid Geometry
通过布尔运算表示几何。
Distance Function
Point Cloud
用点云表示复杂模型需要非常精细密集。
Polygon Mesh
Curves
Bezier curves
Algebraic Formula
$$
b^2_0(t) = (1 - t)^2b_0 + 2t(1 - t)b_1 + t^2b_2
$$
Ray Tracing
Whitted-Style Ray Tracing
Why Ray Tracing
我们为什么引入光线追踪呢？因为我们在之前谈到光栅化的时候它有一些问题解决的并不是很好，最大的问题是它不是很好去表示全局的效果，包括软阴影、Glossy 反射和间接光照等等。
Basic Ray-Tracing Algorithm
Light Rays
在定义光线追踪之前，我们先把光线定义下来：
- 光线沿着直线传播而不考虑其波动性
- 光线和光线不会发生碰撞
- 光线一定是从光源发射最终进入人的眼睛
整个光线追踪就是在做这样一个视图模拟的过程，运用了光线的可逆性，可以是光源发出光线然后不断弹射打到人的眼睛里；我也可以认为我的眼睛是可以发出一些感知射线打到这些物体，最后打到光源上。如果我在场景中找到一条光路，光源可以通过某种办法看到相机，那么相机也有办法看到光源。
Ray Casting
首先我们要做光线的投射，假设我们在往一个虚拟的世界中看，面前放着一个成像的平面。成像平面被我们划成不同的像素的格子，对于每一个像素我们可以从摄像机连一条线穿过这个像素，然后打出一根光线，这根光线一定会打到场景中的某个位置或者和所有物体都不相交。
如果相交，我们把这个点和光源做一个连线，判定交点是否对光源可见，也就是判断是不是在阴影里，如果这个点不在阴影中，那么就形成了一条有效的光路：光源-交点-相机，就可以计算这条光路的能量，最后把看到的颜色算出来。
光线投射做的就是每个像素投出去一根光线，从眼睛开始和场景相交求最近交点，找到交点后和光源连线判定是否对光源可见，最后计算着色写回像素的值。
Ray Equation
光线在数学上就是一个射线，有一个起点 o，传播方向为 d，用这两个量就可以简单定义一条光线。在光线上的任何一点我都可以用 o + td 来表示，因为沿着这条光线无非是从 o 开始往 d 方向走了多远。同时由于光线是射线，我们认为光线只能往一个方向传播，所以 $0 \leq t \leq \infty$。
这个时候我们再回到之前所说，图形学很少考虑这种边界条件，比如 $t$ 究竟是大于 0 还是大于等于 0 意义不是很大。
那么我们来谈谈光线如何与不同物体求交的最简单情况–光线与球做交点。球在数学上的定义也非常简单，球到任何一个点到球心c的距离都等于半径R得到隐式函数：$(p-c)^2-R^2=0$。
那么现在我们要求光线与球的交点，而交点代表着该点又在光线上又在球上，那么这个点才是叫交点，所以根据点$p$联立起来得到$(o + td - c)^2 - R^2 = 0$，顺理成章就可以解出来：
简单的把联立方程展开，求根公式得到最终的结果 t。为了满足 t 的实际物理意义，结果要确保是正值；根据 t 的不同有相离（0）、相切（1）和相交（2）三个状态。
Plane Equation
交点一定又在光线上又在平面上。所以点 $p$ 也可以写成 $o+td$ 的形式，带入垂直方程得到 $t$。这样我就可以解出光线和平面的交点。
Möller Trumbore Algorithm
人是懒惰的，人们发现 Möller Trumbore 算法直接求出光线与三角形的交点。如果两者相交，那么光线表达式也可以表示为三角形的重心坐标表示形式，三个方程三个未知量，可以求解线性方程组。
在线性代数中，求解线性方程组我们使用克莱姆法则。解出之后需要判断是否合理，$t$是否是正值；重心坐标表示必须非负点才能在三角形内。
Acceleration & Radiometry
Accelerating Ray-Surface Intersection
加速求交是一件必要的事情，如果我们用之前说的最原始的做法当然可以求出光线和整个场景最近的交点，但效率大打折扣。
Bounding Volumes
为了加速有一个很重要的概念：包围盒/体积，通过这种包围盒的方式我们可以加速。比如我有一个复杂的物体，可以用一个相对简单的形状包起来，保证物体一定在这个简单的形状之内，对于图中二维的情况看到一个二维的茶壶，我可以用矩形或圆形框起来，这样就做出来一个包围盒。
包围盒的好处存在一个逻辑问题，如果光线连包围盒都碰不到，那更不可能碰到包围盒中的物体。这个思路虽然简单，但非常有效。
对于三维的情况，大家用的最多的就是一个长方体。右边是一个简单的长方体，我们理解为三对平面的交集，通常在实际应用中用的是轴对称包围盒，缩写为AABB。