Games101_1TO8

下定决心开始学图形学

绪论

什么是图形学

从技术层面而言，画面越亮，全局光照越强，技术越好，画面越好

图形学的基本工业应用有如下一些场景：

游戏
电影
1. 特效的制作，从某个方面来说特效是图形学中较好实现的，因为生活中比较少见
2. 面部，动作捕捉
渲染
1. 毛发，几何形体的表述
2. 渲染，光纤在几何形体中的传播与反射
3. 粒子效果，模拟与动画
设计
1. CAD设计
2. 室内设计
可视化
1. 人体可视化
VR
数字绘画
模拟
1. 物理模拟
2. 光线模拟
GUI
Typography字体表示
1. The Quick Brown Fox Jumps Over The Lazy Dog，常用于测试字体的完整性，因为这一句话包含了所有26个字母

图形学中的问题

Math of （perspective）Projections, curves, surfaces
Physics of lighting and shading
Representing/Operating shapes in 3D
Animation/Simulation

光栅化

将三维空间的几何形体显示在屏幕上的过程称为光栅化

常用于实时计算机图形学（例如游戏）。

在计算机图形学中实时意味着每秒钟生成30副图像（帧），就认为是实时，否则认为是离线

几何

Curves和Meshes的表示

即曲线与曲面的表示，在变化过程中如何保持曲线与曲面的拓扑结构

光纤追踪

Calculate Intersection and shading

Continue to bounce the rays till they hit light sources

动画/仿真

Key frame Animation
Mass-spring System

CV与CG的区别

CG注重建模，模拟，CV注重图像处理（图像分割等设计猜测和推理的操作）

图形学中的线性代数

图形学主要基于以下自然学科：

基础数学：
1. 线性代数
2. 微积分
3. 统计
基础物理
1. 光学
2. 力学
3. 波动光学等等
其他
1. 信号处理
2. 数值分析（大量）
3. 美学（一点点）

向量

数学上更习惯于称为向量

物理上更习惯于称为矢量

向量最重要的两个属性：

方向
长度

向量标准化

向量长度 $||\vec {a}||$
单位向量：
1. 模长（magnitude）为1的向量
2. 向量标准化： $\hat{a} = \vec{a} / ||\vec{a}||$
3. 用于表示方向，不关心她的长度

向量加

平行四边形法则：向量首首相接的平行四边形对角线

三角形法则：向量首尾相接形成的三角形第三条边

在数学上的向量是基于一组基表示的，通常为笛卡尔基（即（1，0）与（0，1）），那么在这种情况下相加则为各坐标分量之和，便于计算向量长度。

向量乘法

点乘

$\vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}|cos\theta$

向量的点乘将得到一个数。

在图形学中，点乘可以用于计算出两个夹角的余弦，当两个向量均为单位向量时，点乘直接为夹角余弦：

$cos\theta = \frac{\vec a \cdot \vec b}{|\vec a||\vec b|} = \hat a \cdot \hat b$

写成矩阵形式如下：

$\vec a \cdot \vec b = {\vec a}^T \vec b$

点乘满足以下定律：

交换律
结合律
分配律

此外，点乘还能用于计算投影：

$ \vec {b_\perp} = k \hat a = |\vec b| cos\theta \hat a = |\vec b| (\hat a \cdot \hat b) \hat a$

利用投影我们可以将一个向量分解为两个相互垂直的向量：

还能通过余弦相似度衡量两个向量的接近程度。

此外，考虑如下情况：

通过余弦函数对钝角与锐角的响应的正负不同，可以判断两个向量的方向是相同还是相反

叉乘

叉乘包括两个输入向量和一个输出向量。最终输出的向量为一个垂直于两个输入向量的新向量，且该向量的大小为：

$|\vec a \times \vec b| = |\vec a||\vec b| sin \phi$

其中 $\phi$ 为向量夹角。

计算公式如下：

$\vec a \times \vec b = (y_az_b - y_bz_a, z_ax_b - x_az_b, x_ay_b - y_ax_b)^T$

其中 $\vec a = (x_a,y_a,z_a), \vec b = (x_b,y_b,z_b)$

还能使用矩阵表示法：

\vec a \times \vec b = A^{*}b = \left( \begin{matrix} 0 & -z_a & y_a \\ z_a & 0 & -x_a \\ -y_a & x_a & 0 \\ \end{matrix} \right) \left( \begin{matrix} x_b \\ y_b \\ z_b \\ \end{matrix} \right)

其中 $A^{*}$ 称为a的dual matrix。

输出向量的方向由右手准则确定。

在三位空间中，给定两个轴，可以使用叉乘计算出第三个轴。如果在一个三维坐标系中，x与y的叉乘得到z，则认为该坐标系为一个右手坐标系。

叉乘满足以下性质：

$\vec a \times \vec b = -\vec b \times \vec a$
$\vec a \times \vec a = \vec 0$
$\vec a \times (\vec b + \vec c) = \vec a \times \vec b + \vec a \times \vec c$ 分配率
$\vec a \times (k\vec b) = k (\vec a \times \vec b)$ 数乘结合律

在图形学中，可以利用叉乘来计算：

一个向量在另一向量的左侧还是右侧
一个向量在一个物体的内测还是外侧

例如对于如下一个x,y平面（z轴垂直于纸面），可以通过 $\vec a$ 与 $\vec b$ 的叉乘的正负判断b在a的左侧还是右侧：

再比如对于如下情况，如何判断P点是否在三角形ABC内部：

判断过程如下：

计算AB与AP的叉乘，得到方向为z轴正方向，P在AB左侧
计算BP与BC的叉乘，得到结果为z轴正方向，P在BC左侧
计算CP与CA的叉乘，得到结果为z轴正方向，P在CA左侧

那么就可以认为P在三角形的内部。即判断P点是否在三条边的同侧

坐标系

有了点乘和叉乘，就可以构造三维坐标系，考虑构造如下坐标系：

|\vec u| = |\vec v| = |\vec w| = 1 \\ \vec u \cdot \vec v = \vec v \cdot \vec w = \vec u \cdot \vec w = 0 \\ \vec w = \vec u \times \vec v (right-handed) \\ \vec p = (\vec p \cdot \vec u)\vec u + (\vec p \cdot \vec v) \vec v + (\vec p \cdot \vec w)\vec w

可见对于任意三维向量P，可以将其分解到这个坐标系

矩阵

矩阵乘法

$(M \times N)(N \times P) = (M \times P)$

其中矩阵 $(M \times P) = C$ 中的元素 $c_{ij}$ 等于矩阵 $(M \times N) = A$ 的第i行表示的向量，点乘，矩阵 $(N \times P) = B$ 的第j列表示的向量。

矩阵乘法满足以下定律：

结合律
分配律（左分配率，右分配律）

矩阵的转置

转置具有以下性质：

$(AB)^T = B^TA^T$

特殊矩阵

单位矩阵
对角矩阵
逆矩阵，由性质： $(AB)^{-1} = B^{-1}A^{-1}$

矩阵变换

使用矩阵与向量的乘积操作，可以完成向量在坐标系下的变换，例如二维的y轴对称变换：

\left( \begin{matrix} -1 & 0 \\ 0 & 1 \end{matrix} \right) \left( \begin{matrix} x\\ y \end{matrix} \right) = \left( \begin{matrix} -x \\ y \end{matrix} \right)

变换

变换可以大致分为以下两个方面：

Modeling，模型变换
Viewing，视图变换

例如在逆运动学中的应用。

正运动学：已知各个关节的角度，求末端的位置
逆运动学（IK,inverse kinematics）：已知末端的位置，求各个关节的角度

二维线性变换

缩放

二维缩放操作可以用如下数学形式表示：

x' = s_x x \\ y' = s_y y

写成矩阵形式为：

\left( \begin{matrix} x' \\ y' \end{matrix} \right) = \left( \begin{matrix} s_x & 0 \\ 0 & s_y \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right)

反射

二维反射可以用如下数学形式表示：

\left( \begin{matrix} x' \\ y' \end{matrix} \right) = \left( \begin{matrix} -1 & 0 \\ 0 & 1 \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right)

上述操作使得物体按y轴反射

切变（Shear）

注意该变换有如下特点：

垂直方向的坐标并未改变
水平方向上，当y=0时，也不发生变换
水平方向上，当y=1时，原坐标0移动了a个单位

通过观察可以发现水平方向上移动的距离可以用ay来表示，因此该变换可以用如下形式表示：

\left( \begin{matrix} x' \\ y' \end{matrix} \right) = \left( \begin{matrix} 1 & a \\ 0 & 1 \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right)

旋转（Rotate）

此处讨论绕原点逆时针旋转。

我们可以利用特殊点得到旋转的变换矩阵（前提是旋转为线性变换）：

最终得到的变换矩阵为：

\left( \begin{matrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{matrix} \right)

总结

对于上述的可以表示为矩阵乘以向量得到的变换称为线性变换

齐次坐标（Homogeneous Coordinates）

齐次坐标的引入：平移坐标变换的特殊性

若需要将平移变换表示为矩阵形式，那么只能使用如下发给发进行

\left( \begin{matrix} x' \\ y' \end{matrix} \right) = \left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right) + \left( \begin{matrix} t_x \\ t_y \end{matrix} \right)

说明平移变换不再属于线性变换。

但我们希望用一个更鲁棒的方式来表示这些变换。

于是我们在原有的维度上增加一个维度，以二维为例：

表示一个二维的点： $point = (x,y,1)^T$
表示一个二维的向量： $vector = (x,y,0)^T$

为什么要用0和1去区分点和向量呢（怎么有点脆皮鸭内味）

原因是向量具有平移不变性，我们希望对向量进行平移操作时不会导致向量的改变。

更进一步，我们希望在齐次坐标系下，点和向量之间应依然存在如下关系：

vector + vector = vector \\ point - point = point \\ point + vector = point \\ point + point = ??

对于其次坐标系下的的点的加法的定义我们仍然需要进行扩充，考虑相加之后得到的数据：

\left( \begin{matrix} x_1 \\ y_1 \\ w_1 \end{matrix} \right) + \left( \begin{matrix} x_2 \\ y_2 \\ w_2 \end{matrix} \right) = \left( \begin{matrix} (x_1+x_2)/(w_1+w_2) \\ (y_1 + y_2)/(w_1 + w_2) \\ 1 \end{matrix} \right)

若两个数据均为其次坐标系下的点，那么 $w_1 = w_2 = 1$ ，于是该加法就能用于表示两个点的中点。

最后在其次坐标下使用矩阵表示变换就能使用如下形式：

\left( \begin{matrix} x' \\ y' \\ w' \end{matrix} \right) = \left( \begin{matrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{matrix} \right) \left( \begin{matrix} x \\ y \\ 1 \end{matrix} \right) + \left( \begin{matrix} x + t_x \\ y + t_y \\ 1 \end{matrix} \right)

仿射变换（Affine Transformations）

既然有了齐次坐标系这么好的东西，那么我们就能思考如何将线性变换和平移变换进行表示，现在它们有了一个新的名字，我们称线性变换+平移变化 = 仿射变换。

需要注意的是，使用齐次坐标表示的变换矩阵是先进行线性变换再进行平移变换。

\left( \begin{matrix} x' \\ y' \end{matrix} \right) = \left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right) + \left( \begin{matrix} t_x \\ t_y \end{matrix} \right) \\ \left( \begin{matrix} x' \\ y' \\ 1 \end{matrix} \right) = \left( \begin{matrix} a & b & t_x \\ c & d & t_y \\ 0 & 0 & 1 \end{matrix} \right) \left( \begin{matrix} x \\ y \\ 1 \end{matrix} \right)

变换的组合（Composite Transform）

对于默认为列向量，变换通常通过左乘变换矩阵实现，然后以从右到左的计算顺序计算变换的结果，由于矩阵的乘法没有交换率，因此变换的先后顺序变得极为重要。

但由于矩阵满足结合率，因此可以先将变换矩阵相乘后在应用到目标向量上。

A_n(...A_2(A_1(x))) = (A_n ... A_2...A_1) \left( \begin{matrix} x \\ y \\ 1 \end{matrix} \right)

逆变换（Inverse Transform）

逆变换即与某个变换效果相反的变换，在数学上，如果一个变换是通过左乘一个变换矩阵 $M$ 完成的，那么它的逆变换就是变换后的向量左乘一个 $M^{-1}$

变换的分解（Decomposing Complex Transforms)

考虑这样一个问题：

现在存在一个左下角c不在原点的矩形
我们希望以矩形的左下角为基准将其旋转一个角度a

我们可以通过如下几个步骤完成这个操作：

将c点平移到原点
绕原点旋转角度a
将c点移动回原位

三维空间的变换

三维空间中我们同样希望使用齐次坐标系表示三维坐标中的点和向量，于是得到一个与二维空间类似的结果：

表示一个二维的点： $point = (x,y,z,1)^T$
表示一个二维的向量： $vector = (x,y,z,0)^T$

当w不为1且不为0时，齐次坐标系下的点 $(x,y,z,w)$ 所表示的三维空间中的点为： $(x/w,y/w,z/w)$

同样三维空间中的仿射变换可以表示为如下形式：

\left( \begin{matrix} x' \\ y' \\ z' \\ 1 \end{matrix} \right) = \left( \begin{matrix} a & b & c & t_x \\ d & e & f & t_y \\ g & h & i & t_z \\ 0 & 0 & 0 & 1 \end{matrix} \right) \left( \begin{matrix} x \\ y \\ z \\ 1 \end{matrix} \right)

二位变换补充：

在不考虑齐次坐标的情况下，旋转变换使用的矩阵是一个正交矩阵（Orthogonal Matrix），实际上他还是一个单位正交阵

三维空间中的线性变换与平移变换

缩放

S(s_x, s_y, s_z) = \left( \begin{matrix} s_x & 0 & 0 & 0 \\ 0 & s_y & 0 & 0 \\ 0 & 0 & s_z & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right)

平移

T(t_x, t_y, t_z) = \left( \begin{matrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{matrix} \right)

旋转

x轴

R_x(\alpha) = \left( \begin{matrix} 1 & 0 & 0 & 0 \\ 0 & cos\alpha & -sin\alpha & 0 \\ 0 & sin\alpha & cos\alpha & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right)

y轴

R_y(\alpha) = \left( \begin{matrix} cos\alpha & 0 & sin\alpha & 0 \\ 0 & 1 & 0 & 0 \\ -sin\alpha & 0 & cos\alpha & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right)

z轴

R_z(\alpha) = \left( \begin{matrix} cos\alpha & -sin\alpha & 0 & 0 \\ sin\alpha & cos\alpha & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right)

对于如上公式，我们观察到，在对y轴进行旋转的矩阵中，如果将非0，1的数值提取出来组成2维变换矩阵，得到的变换矩阵与其余两个轴形成的变换矩阵刚好互为逆，这是为什么呢？因为此处反应的是x叉乘z，在右手坐标系中x叉乘z得到的是-y，因此此处为原2维变换的逆。

那么在三维空间中的旋转可以通过组合三种单轴的旋转得到：

R_{xyz}(\alpha, \beta,\gamma) = R_x(\alpha)R_y(\beta)R_z(\gamma)

这些旋转角度被称为欧拉角
可用于飞机的模拟：roll，pitch，yaw

罗德里格斯旋转公式（Rodrigues‘ Rotation Formula）(待证)

对于一个旋转轴 $\vec n$ 与旋转角度 $\alpha$ ，有：

R(\vec n, \alpha) = cos(\alpha)I + (1-cos(\alpha)\vec n {\vec n}^T \\ + sin(\alpha)) \underbrace { \left( \begin{matrix} 0 & -n_z & n_y \\ n_z & 0 & -n_x \\ -n_y & n_x & 0 \end{matrix} \right) }_N \\

可见最后一项使用的矩阵是一个dual matrix，可联想到之前学过的叉积的矩阵表示。

此外旋转变换中还有一个概念叫四元数，该概念主要解决的是旋转中插值的问题，即：对于一个向量先旋转15°再旋转25°，如果我们将两个变换矩阵加起来求平均再应用到目标向量上，得到的结果并不是旋转20°

观测变换Viewing transformation

视图变换View/Camera Transformation

思考显示生活中如何得到一张三维世界的照片：

找到一个好的位置，给拍照的人都安排好占位（对应图形学中的模型变换model transformation）
找好角度，放置摄像机（对应图形学中的视图变换View transformation）
拍照（对应图形学中的投影变换Projection transformation）

因此可以体会出视图变换的第一步是摆放相机，也就是确定相机的位置。

相机的位置Position $\vec e$
视线方向Look-at/gaze direction $\vec g$
拍摄方式（横拍还是竖拍），可以定义一个向上方向 $\vec t$ 用以表示相机的垂直方向。

下面我们思考这样一个简单的物理问题：

如果一个被拍摄物体发生了移动，相机也放生了完全相同的移动，那么我们最终拍摄出来的照片将不会改变。

即物体相对相机静止。

因此为了便于之后的计算，我们为相机设置了一个标准位置：

初始位置时相机位于坐标（0，0，0）
认为 $\vec t$ 为Y轴， $\vec g$ 为-Z轴
然后对物体做相同的变换操作即可

那么对于一个原本位置描述为 $\vec e,\vec g,\vec t$ 的相机，将其移动到标准位置后，被该相机拍摄的物体应该做如下变换：

将 $\vec e$ 平移到(0,0,0)
将 $\vec g$ 旋转到-Z
将 $\vec t$ 旋转到Y
将 $\vec t \times \vec g$ 旋转到X

那么思考如上的变换转化为矩阵形式应该怎么做呢？我们一步一步来。

首先需要进行平移变换，于是可以写出平移变换矩阵：

T_{view} = \left[ \begin{matrix} 1 & 0 & 0 & -x_{\vec e} \\ 0 & 1 & 0 & -y_{\vec e} \\ 0 & 0 & 1 & -z_{\vec e} \\ 0 & 0 & 0 & 1 \end{matrix} \right]

使用该矩阵就能将点 $\vec e$ 平移到原点。

接下来思考剩下的三个旋转操作，对于这三个旋转问题求解显然比较困难，此时我们可以使用逆向思维，先求出逆向变换的变换矩阵，再通过求逆向变换矩阵的逆得到正向变换的矩阵。

考虑由将-Z旋转到 $\vec g$ ；将Y旋转为 $\vec t$ ；将X旋转为 $\vec t \times \vec g$ ，可以使用如下矩阵进行：

R^{-1}_{view} = \left[ \begin{matrix} x_{\hat g \times \hat t} & x_{\vec t} & x_{- \vec g} & 0 \\ y_{\hat g \times \hat t} & y_{\vec t} & y_{-\vec g} & 0 \\ z_{\hat g \times \hat t} & z_{\vec t} & z_{-\vec g} & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right]

那么如何求这个矩阵的逆矩阵呢？这就联想到之前说到的旋转矩阵是一个正交阵。因此该矩阵的逆矩阵等于其转置，于是最终得到的正向旋转矩阵为：

R_{view} = \left[ \begin{matrix} x_{\hat g \times \hat t} & y_{\hat g \times \hat t} & z_{\hat g \times \hat t} & 0 \\ x_{\vec t} & y_{\vec t} & z_{\vec t} & 0 \\ x_{- \vec g} & y_{-\vec g} & z_{-\vec g} & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right]

最终得到的变换矩阵就为：（注意顺序）

M_{view} = R_{view}T_{view}

可见视图变换最终得到的矩阵与模型变换一样，最终需要应用到模型上，因此，视图变换与模型变换通常被合称为模型视图变换（ModelView Transformation）

投影变换（Projection transformation）

正交投影（Orthographic projection）
透视投影（Perspective projection）

他们的本质区别是：正交投影不会造成近大远小的线性。

此处引用一个非常经典的梗[道理我都懂，但是为什么鸽子这么大]((3 封私信 / 50 条消息) “你说的好有道理，但是鸽子为什么这么大啊？”什么意思 - 知乎 (zhihu.com))

实际上，从数学角度说明：

所谓透视投影，我们认为摄像机放置在空间中的某个位置，并且认为摄像机是一个点
所谓正交投影，我们认为摄像机与被摄像物体距离无限远。

正交投影

将相机放置在标准位置
忽略Z轴
使用缩放、平移变换讲物体变换到 $[-1,1]^2$

更正式的做法是：

我们希望讲如下定义的一个空间立方体
- 定义x轴y轴z轴分别属于如下三个范围
- [l,r],[b,t],[f,n]
现在我们希望对其进行Canonical（正则、标准、规范）化，即将该立方体映射为 $[-1,1]^3$ 定义的范围
那么我们可以使用如下两部操作对其进行变换：
- 将中心点移动到坐标原点
- 将三个轴分别映射到[-1,1]
那么我们可以得到如下的变换矩阵：
$M_{ortho} = \left[ \begin{matrix} \frac{2}{r-l} & 0 & 0 & 0 \\ 0 & \frac{2}{t-b} & 0 & 0 \\ 0 & 0 & \frac{2}{n-f} & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right] \left[ \begin{matrix} 1 & 0 & 0 & -\frac{r+l}{2} \\ 0 & 1 & 0 & -\frac{t+b}{2} \\ 0 & 0 & 1 & -\frac{n+f}{2} \\ 0 & 0 & 0 & 1 \end{matrix} \right]$
需要注意的是此处我们是向着-Z方向观测，因此near(n)的值要比far(f)的值大
- 这也是OpenGL中使用的是左手系的原因

透视投影

透视投影是图形学中使用做广泛的投影变换

会产生近大远小的线性

相互平行的先将不在平行，而是相交于一个点

欧式几何中定义的是一个同一平面内平行的线不会相交，而透视投影会将物体投影到另一平面

透视投影的做法：

此处我们引入一个几何图形：Frustum：
- 那么透视投影可以分解为两个部分：
  - 将位于Frustum远处的四边形通过挤压使得大小等于位于近处的四边形，即将Frustum变换为Cuboid
  - 然后对Cuboid进行正交投影即可
- 对于挤压操作，我们需要它具有如下性质：
  - 挤压操作不会使得近平面发生变化
  - 挤压操作不会使得远平面上的点的Z坐标发生变化
  - 挤压操作不会使得远平面的中心点发生变化

于是我们需要求出从Frustum变化为Cuboid的变化矩阵：

首先我们希望挤压使得远平面上的点与近平面对其，因此我们从x轴负方向观测这个图像可以得到如下结果：

可见图中存在一对很明显的相似三角形，因此利用相似三角形对应边成比例的性质，我们可以得到如下变换： $y' = \frac{n}{z}y$

同理可以得到x的变换为 $x' = \frac{n}{z}x$
因此可以暂时性的写出变换后的形式：

\left[ \begin{matrix} x \\ y \\ z \\ 1 \end{matrix} \right] \to \left[ \begin{matrix} nx/z \\ ny/z \\ unknown \\ 1 \end{matrix} \right] \left[ \begin{matrix} nx \\ ny \\ still unknown \\ z \end{matrix} \right]

因此从结果推过程，我们可以得到变换矩阵的部分形式如下：

M_{persp\to ortho} = \left[ \begin{matrix} n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ ? & ? & ? & ? \\ 0 & 0 & 1 & 0 \end{matrix} \right]

那么对于未知值我们应该如何补充呢？我们发现我们还有两个可以使用的条件：

挤压操作不会使得近平面发生变化
挤压操作不会使得远平面上的点的Z坐标发生变化

那么对于在近平面上的任意一点，它变换后最终会得到如下结果：

\left[ \begin{matrix} x \\ y \\ n \\ 1 \end{matrix} \right] \to \left[ \begin{matrix} x \\ y \\ n \\ 1 \end{matrix} \right] == \left[ \begin{matrix} nx \\ ny \\ n^2 \\ n \end{matrix} \right]

通过得到的Z坐标是不含xy的常数，我们可以假设变换矩阵中的第三行为如下形式：

\left[ \begin{matrix} 0 & 0 & A & B \end{matrix} \right] \left[ \begin{matrix} x \\ y \\ n \\ 1 \end{matrix} \right] =n^2

而对于在远平面上的任意一点，它也会遵循Z不变的结果，此时我们取具有代表性的中心点，计算它经过变换后的得到的点将是：

\left[ \begin{matrix} 0 \\ 0 \\ f \\ 1 \end{matrix} \right] \to \left[ \begin{matrix} 0 \\ 0 \\ f \\ 1 \end{matrix} \right] == \left[ \begin{matrix} 0 \\ 0 \\ f^2 \\ f \end{matrix} \right]

于是又可以得到一个方程：

\left[ \begin{matrix} 0 & 0 & A & B \end{matrix} \right] \left[ \begin{matrix} 0 \\ 0 \\ f \\ 1 \end{matrix} \right] =f^2

最终我们得到了如下方程组：

\begin{cases} An + B = n^2 \\ Af + B = f^2 \end{cases}

最终解出AB得到变换矩阵：

M_{persp\to ortho} = \left[ \begin{matrix} n & 0 & 0 & 0 \\ 0 & n & 0 & 0 \\ 0 & 0 & n+f & -nf \\ 0 & 0 & 1 & 0 \end{matrix} \right]

光栅化Rasterize

现定义视锥中的两个概念：

aspect ratio——可见范围的长宽比
Field of View（fov）可视角度
- vertical field of view （fovY）垂直可视角

现在我们将视锥变换到与正交投影长方体相同的空间：

Canonical Cube to Screen

完成MVP（modeling，viewing，Projection）变换后，我们希望能将完成变换的标准化矩形 $[-1,1]^3$ 显示在屏幕上，那么我们首先必须确定，什么是屏幕。

我们认为屏幕是：

二维像素数组
分辨率（resolution）：数组大小
一个典型的光栅（raster）成像设备

Raster光栅

实际上Raster正是德语中的屏幕Screen

而光栅化（Rasterize）就是指将物体画在屏幕上的过程

像素Pixel

像素实际上是picture element的缩写
到目前为止我们可以认为一个像素就是一个小方块，其中被统一的颜色填充。

屏幕空间

在本节课中，我们定义屏幕空间的原点位于屏幕的左下角。（区别于图像处理中的左上角）

对于屏幕上的像素，我们使用一对屏幕空间中的坐标 $(x,y)$ 表示，其中下x，y为整数。

实际上坐标为 $(x,y)$ 的像素的中心位于 $(x+0.5, y+0.5)$

转换到屏幕空间

转化到屏幕空间时，我们需要两部操作：

忽略z
将xy由 $[-1,1]^2$ 转化到 $[0, width] \times [0, height]$

于是我们可以写出变换矩阵：

M_{vierwport} = \left[ \begin{matrix} \frac{width}{2} & 0 & 0 & \frac{width}{2} \\ 0 & \frac{height}{2} & 0 & \frac{height}{2} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right]

该变换被称为视口变换，改变换相当于先做了一次拉伸，再将左下角平移到屏幕中心。

为了更好的理解光栅化，接下来列举以下绘画机器：

CNC Sharpie Drawing Machine
Laser Cutters

然后再来看看一些不同的光栅设备：

Oscilloscope 示波器
- 与早期的电视机一样，使用阴极射线管(Cathode Ray Tube)成像，即CRT显示器
- 其中使用了一项隔行扫描的技术，对于一张图，先显示其奇数行，再显示器偶数行
- 该方法会导致严重的画面撕裂
现代显示技术使用了显存技术（Frame Buffer）
Flat Panel Displays平板显示设备
- LCD（Liquid Crystal Display）液晶显示器
  - 利用的是液晶的物理特性
- LED （Light emitting diode array）
- Electrophoretic（Electronic Ink）Display

下面我们讨论如何在上述显示设备上绘制

三角形

图形学中表示一个形体有：

Polygon Meshes
Triangle Meshes

下面我们着重来讨论以下三角形。

为什么使用三角形来表示呢：

三角形是三维空间中最基础的多边形
任何不同的多边形都可以拆解为三角形
给定任意三个点连成的三角形一定能形成一个平坦的平面
三角形的内外定义十分清晰（不存在既是凸多边形又是三角形的形体）
对于一个三角形，其内部的点的可以通过该点与三角形的三个顶点的位置关系，描述一个渐变的属性，即可以很好的完成插值

那么考虑使用一个三角形来将物体绘制到屏幕上。

采样

采样，即将一个连续函数离散化的过程。

图形学中采样的应用非常广泛。

下面以对一个三角形的采样为例：

实际上这个过长就是计算哪些像素的中心被三角形包围的过程。于是我们可以使用如下的二值函数表示：

inside(t,x,y) = \begin{cases} 1 & Point (x,y) in & triangle & t \\ 0 & otherwise \end{cases}

那么采样代可以这样表示：

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);
    }
}

那么如很判断一个像素点是否在三角形内部呢？

这一点在叉积中有所体积，即只需要使用该点与三角形的三个边进行叉积，判断三个叉积结果的正负是否相同即可。

边界处理

但是对于落在三角形边上的像素点我们应该如何处理呢？

实际上OpenGL与DirectX中使用左上原则（top-left rule）处理，即落在三角形上边与左边的点被认为属于三角形内部

加速

但是现在又有一个性能上的问题，那就是对于任意三角形，我们是否有必要对屏幕上的所有像素都判断一边呢？

显然这样会使得性能浪费，因此我们取三角形顶点坐标的x与y的极大极小值形成一个足以包裹该三角形的矩阵，只需要对该矩形进行光栅化即可得到想要的效果，该矩形称为Bounding Box，即包围盒，此处使用的是轴向包围盒，Aixe Align Bounding Box，AABB。

但实际上还有更快的加速方式，比如对每一行都找最左和最右像素点，相当于对每一行寻找一个包围盒。

该方法解决了AABB中，如果一个三角形很长但很扁，且倾斜了45°时的性能浪费。

实际屏幕上的光栅化

可见实际上一个像素并不是由一个单一的小方块形成，而是类似上图中的RGB条，或其他具有结构的小块。

例如S5中应用的是Bayer Pattern，可以发现其中绿色的点比红蓝分布的更密集，原因是人眼对绿色更敏感

在其他的成像设备上，例如彩色打印机，我们能看到更复杂的结构：

现在我们可以看到一个三角形图片，最终在我们定义的显示器显示的样子了：

真实三角形：

我们显示的三角形：

是不是很奇怪？奇怪就对了，于是乎我们可以在这引出一个概念：Jaggies锯齿

事实上，锯齿并不是什么新鲜概念，从信号处理的角度来说，锯齿实际上就是由于采样率较低导致的，我们还可以称其为：Aliasing走样

反走样与深度缓冲（Antialiasing and Z-Buffering）

由于采样在显示生活中广泛存在，因此，例如图像中的像素、动画、音频中的帧等等，因此，在这些领域中均存在下采样的问题。

于是我们引出一个图形学中用于表示错误的词：Artifacts，他可以表示Errors/Mistakes/Inaccuracies。

图形学中常见的Artifacts

Jaggies锯齿

Moire Patterns摩尔纹

该现象是由于采样时跳过一些奇数行或列导致的

Wagon Wheel Illusion

即显示生活中看到的车轮倒转的现象，这是由于我们人脑在时间上采样不足导致的。

总的来说，走样是由于型号变化的速度太快，而我们采样的速度太慢导致的。

解决走样的方法

在采样前，先做一次平滑（Blurring），即使用低通滤波进行过滤。

但是我们先进行采样，在进行模糊，经得到并不理想的结果：

频域Frequency Domain

为了简单理解，我们从最简单的正余弦函数开始：

下面我们对引入x的系数f，我们称它为频率，它反映了正余弦函数变化的快慢：

定义周期，表示每隔多久函数会重复一次，周期为频率的倒数

傅里叶变换Fourier Transform

所起傅里叶变换，就不得不提傅里叶级数展开。

傅里叶认为任何周期函数，都能表示为一些列正余弦函数的线性组合以及一个常数项。

考虑这个傅里叶展开的过程，展开形成的正余弦函数均具有不一样的频率，且从低到高排列，常数可以认为频率为0，也就意味着每一个正余弦项，都代表了一个特殊的频率。

那我我们先来看看对不同频率的函数进行采样：

可见，对于频率越高的函数，采样后越无法恢复，再看如下图：

可见，对于图上蓝色与灰色的两个函数，他们的采样结果是一样的，这就意味着我们通过采样恢复得到原函数是不唯一的，这就是走样的更准确定义。

下面我们看看傅里叶变换：

傅里叶变换可以让图片从时域转化为频域

右图就表示了左图的频域信息，越靠近中心，频率越低，越往四周，频率越高，可见图片大部分信息集中在低频。

再看频域有很明显的两条中轴线，实际上这代表了图像的四个边界，我们在求傅里叶变幻时，实际上将一个没有周期特性的图片进行了周期延拓（考虑对非周期函数进行傅里叶展开时的操作），也就意味着我们将这张图在他的四个方向上复制了很多分并紧挨着排列。因此这些图片会在边界上发生剧烈的变化，也就意味着频率非常高，反映到频域就是中间的两条白线（实际上这些白线最开始会出现在四周，为了便于观测，我们对频域进行了平移，将低频移动到了中心，详见数字图像处理中的傅里叶变换）

下面我们对这张图的频域应用一个滤波，看看会有什么效果：

如图是应用高通滤波产生的效果，可见频域中的低频信息被去掉了（中间被掏空），反应到图像中则是边界被保留了，相反的则是低通滤波，下过如下：

此外还有保留特定频率的带通滤波器：

卷积Convolution

卷积定理Convolution Theorem

空域（时域）的两个函数卷积等于两个函数在频域上的乘积，空域（时域）的两个函数乘积等于两个函数在频域上的卷积

盒式滤波器Box Filter

考虑盒式滤波器的大小对其在频域内图像的影响，对于更大长宽的盒式滤波器，经其处理过的图片将更加平滑，因此反应到频域就是保留了更小范围的频率：

采样

下面从频域的角度再次审视采样，实际上就是重复频率或频域上的内容。

利用卷积定理：在空域的乘积等于频域的卷积，可以得到：对空域中的采样可以认为是使用一组取值为1的脉冲函数与原函数的乘积得到如下图所示：

如果将函数a与脉冲函数c进行傅里叶变换，我们来看看他们在频域中的表现：

可见，在频域中b与d进行卷积得到了图f，而图f是图b的频率图像的周期重复。

走样

接着，我们再从频域的角度来思考走样的问题：对于如下采样的结果：

可见原函数的每一次频域图像的重复可以很清晰的分辨出来，但是如果我们的采样频率降低，即对用在频域中的f取值减小，间隔减小那么将得到如下的采样结果：

可见，相邻两个原函数频域图像的复制叠加在了一起，于是便难以区分原函数的样貌，这就产生了走样（或者说混叠）

反走样

于是我们可以根据采样的原理，来分析一下反走样的方法：

增加采样率
- 例如使用高像素的显示器，传感器
- 但是这种方法开销很大，需要很高的分辨率
反走样（Antialiasing）
- 例如前文提到的先做模糊再做采样
- 反应到频域就是将高频信号阶段再做复制：

MSAA(Multi Samples AntiAliasing)

由上述反采样的分析，我们得到了一个似乎可行的方案：

先使用1像素的盒式滤波器对原图像进行平滑
再对平滑后的图像进行采样

但是使用1像素（物理）的盒式滤波器如何进行平滑呢？我们可以通过计算该像素中的灰度值平均来实现，例如下图中，黑色部分代表被物体覆盖的区域，白色代表背景：

但是这个面积往往难以求解，于是提出了将该像素（物理），再细分为4*4个像素（逻辑）的近似方法MSAA：

但是，MSAA，代价是什么呢？

计算量被增加了，4*4将使得计算量增加16倍
而工业上将使用更少的点，并将这些逻辑像素按照更有效的图案（而非均匀）地分布到物理像素中去，一些逻辑像素还将被相邻的物理像素复用。
因此平时打游戏时开启MSAA帧数并不会下降到原来的1/4

此外还有其他抗锯齿的方法，比如：

FXAA（Fast Approximate AA）
- 先采样得到一副有锯齿的图形，然后通过图像处理的方法，找到有锯齿的边界，并将这些边界替换为没有锯齿的边界
TAA（Temporal AA）
- 通过寻找上一帧的像素信息，仍然使用一个物理像素来判断该像素是否在物体内，但是会使用上一帧的像素和这一帧的像素来判断，类似于动态模糊，相当于将MSAA中的逻辑像素划分放在了时间上，将上一帧的边界信息复用到下一帧来显示。
- 但该方法会产生拖影。

以上两种得到了工业上的广泛应用。

另外，还有一个与抗锯齿类似的操作：超分辨率（Super resolution/Super sampling）

该问题可描述为：将低分辨率拉伸为高分辨率（放大的过程会使得产生更明显的锯齿效果）
该问题实际上还是一个如何解决采样率不够的问题
解决该方法的技术有著名的DLSS（Deep Learning Super Sampling），也就是通过使用深度学习的方法将放大后缺失的部分猜出来

可见性与遮挡

考虑在绘制一幅图形时，我们应该如何体现物体的远近之分？

考虑绘制油画时的处理方式，先绘制远处的物体，然后绘制近处的，让近处的物体覆盖远处的物体。这就是画家算法的思想。

即画家算法的思想就是：让后绘制的物体永远覆盖先绘制的物体。

但当我们需要绘制立方体这张多个面堆叠的物体时，与我们远近相同的四个面，我们应该以怎样的顺序去绘制呢？

考虑采用左下右上的顺序绘制该立方体，我们将得到正确的遮挡顺序，但如果我们采用右上左下的顺序绘制呢？由于右边比上边晚绘制，因此左侧将覆盖上侧，那么最终绘制的图像将如下图所示：

原因就是左侧比上侧晚画，因此上侧无法将左侧的边界遮盖。

画家算法

那么画家算法该如何区分物体的顺序呢？一个很简单的思路就是将物体（三角形）按深度大小排序，排序时间复杂度为 $O(nlogn)$ ，但是我们考虑下面的情况：

PQR呈现两两相互覆盖的视觉特征，这样我们就很难定义谁在前谁在后，因此就无法对他们进行深度的排序，更不用说正确的绘制它们了。

Z-Buffer（深度缓冲/缓存）

经过上面的分析我们发现，画家算法并不能很好的完成任务，因此诞生了一种目前工业界广泛采用的算法：Z-Buffer

Z-Buffer的思想就是：

既然我们考虑整改三角形的远近关系存在问题，那么我们就更细微的去考虑每个像素的深度关系
每一个像素内，记录它的最小深度。
- 例如下图中的一个像素点，由于先绘制了地板，该像素的深度值被记录为了地板的深度值，接下来绘制立方体时，发现立方体也需要绘制在该像素上，且立方体在该像素上的z值小于原先该像素的z值，于是该像素将记录新的z值
引入一个额外的缓存区域用于存储这些深度信息：z-buffer
- frame buffer用于存储颜色信息
- z-buffer用于存储深度信息

而联系到我们之前讨论的相机的标准位置，我们认为相机的视线方向是z轴的负方向，这样会导致越小的z反应了越远的距离，这样有点反直觉，因此此处规定：

z永远为正
z越小，反应的深度越近

如下图所示的两幅图在采用了z-buffer的渲染中是同步产生的：

右图中越黑的地方反应了越小的z值，也就是离摄像机越近。

由此可以得到算法的伪代码如下：

可以通过如下图示进一步理解，其中R代表无限大（C++中可以使用inf代表）：

考虑该算法的时间复杂度，该算法的过程中我们并没有对其进行排序，只需要遍历每个三角形的每个像素即可，而我们认为每个三角形中的像素个数为常数个，因此最终该算法的时间复杂度可以认为是 $O(n)$ ,n为三角形个数。

考虑该算法是否会像画家算法一样，因为绘制的顺序不同而产生不同的结果呢？若不存在两个物体在同一个像素具有相同的深度，那么答案显然是不会的。

而实际上我们假设不存在两个在同一像素位置具有相同深度的物体是有迹可循的，因为计算机中深度信息通常使用浮点数进行存储，浮点数相等需要非常苛刻的条件。但实际上也确实存在深度发生冲突的情况，详细可见3D渲染中的Z-fighting现象 - 知乎 (zhihu.com)

而当我们使用MSAA将一个像素细分时，Z-Buffer就要对每一个采样点（逻辑像素）记录一个深度信息。

此外，z-buffer无法处理透明物体，需要使用特殊的方法处理。

着色（Shading）

Illumination，Shading and Graphics Pipeline

此处引用Merriam-Webster Dictionary对shading的定义：

shading, noun

The darkening or coloring of an illustration or diagram with parallel lines or a block of color

而在Game101课中shading给出如下定义：

The process of applying a material to a object

Blinn-Phong Reflectance Model

一个简单的着色模型

我们先来看看光在实际生活中的模样：

下图中的杯子我们可以大致将光分为三种：

高光
漫反射光
间接光照

那么我们可以定义某个材质的三个部分的光与杯子的光相同，以此定义一种材质。

我们先给出一些定义：

shading point，一个需要考虑着色的单位，通常是位于物体表面的一小块区域，如果区域足够小，我们则可以认为他是一个平面。
View direction，v，观测方向，相机与shading point的连线向量
Surface normal，n，平面法线，垂直于shading point的向量
Light direction，l，光照方向，光源与shading point的连线向量
Surface parameters，物体表面属性，例如color，shininess等等
为了便于计算，上述向量均为单位向量
此外，此时讨论的作色为Local Shading，即局部光照，不考虑某物体的光照对其他物体的影响，比如阴影。

漫反射Diffuse Reflection

对于漫反射而言，从不同的角度对这一块区域进行观测应该能观测到相同的颜色

而由于物体表面接受到的光照并不一样，因此才产生了不同的颜色，那我我们如何去衡量物体的一个面接受到了多少光照呢？此处我们将光照视为一种能量，考虑一个观测点附近的单位面积：

可见，接收到的光照的强度与观测点法线于光照方向的夹角存在一定的关系，事实上它们是成正比的。由此可以计算出有多少光在这一着色点上会被接收。

然后我们进一步考虑光源发出的能量：

考虑光在传播的过程中不会出现能量的损失，而光在各个方向行动的速度是相等的，那么，能量将被集中在一个球壳上，而随着球壳的增大，由于能量受能定律，越往外，球壳上的单位能量就越小，可见球壳上某一点的光照能量与该点到光源的距离成平方反比。

因此对于一个着色点，如果我们已知它与光源的距离，就能计算出有多少光传播到了该着色点。

到目前为止，我们得到了以下两项指标：

有多少光传播到了一个着色点
该着色点接收了多少光

由此可以得到漫反射的计算公式：

$L_d = k_d(I/r^2)max(0,\vec n \cdot \vec l)$

其中I代表单位距离上点光源的光强。
max函数用于排除向量n与l夹角余弦为负的情况，在该情况下，表示一束光从物体的内部穿过到达了着色点，该情况暂时不予考虑
其中 $k_d$ 表示反射系数，即显示生活中物体将会吸收一部分频率的光，反射另一部分，该系数表示了着色点反射了多少能量，反应到观感上就是明暗信息，将其分别应用于r，g，b三通道，就能得到该作色点的颜色。该值更直观的展示可以看如下图：
可见该公式中并没有出现观测方向向量v，可以体现出漫反射与我们观测的视角并没有关系。

高光Specular Term

高光的效果存在一种特性：反射方向非常接近镜面反射的方向，即出射方向集中于一个方向。

因此只有当我们观察的方向于高光的出射方向足够接近时，才可能看到高光。

但是Blinn-Phong模型观察到了一个更有意思的现象，那就是：当观测方向V与镜面反射方向R接近时，光照方向I与观测方向V的半程向量h与法线n非常接近，也就是如下图所示的情况：

其中半程向量是指向量I与V角平分线方向定义的单位向量，由向量加法的平行四边形法则我们可以很容易的得到向量h，即：

h = bisector(\vec V, \vec I) \\ = \frac{\vec V + \vec I}{|\vec V + \vec I|}

由此我们就可以很好的避免去求一个反射向量R

那么在根据前文提到的漫反射计算方法，就能得到高光的计算方式：

L_s = k_s(I/r^2)max(0, cos\alpha)^p \\ = k_s(I/r^2)max(0, \vec n \cdot \vec h)^p

其中 $k_s$ 表示物体吸收的光谱，但高光部分通常认为是纯白色
此外事实上也要考虑入射角对光照强度的影响，但是该模型中并没有考虑
指数p则需要通过如下的图示来解释：

我们知道高光往往是一个非常小的范围，而直接使用余弦相似度来判断是否属于高光，会得到一个非常大的范围，因为余弦相似度对夹角的变化不够敏感，可以看到第一张图中，当夹角增加到45°时，余弦值依然很大，因此，我们需要通过增加余弦函数对夹角的敏感度来调整这个范围，于是想到了给它加一个指数，可以看到p越大越敏感。通常情况下在该模型中p一般取100-200。这类图像我们可以称为Cosine Power Plots。

如下图是一个不同 $k_s$ 值与p值组成的矩阵：

为了能更好的观察高光，此处在渲染高光的同时也渲染了漫反射。

可见随着p的增大，高光范围在逐渐缩小

可以看到，虽然并没有给出颜色信息，但是我们也能大致感受到这些物体属于不同的材质。

间接光照Ambient Term

在Blinn-Phong模型中，对这一部分的内容进行了简化，由于环境中的光十分复杂，经过各种反射最终到达物体，于是该模型直接摆烂了😆，既然环境光无处不在，并且能作用到物体的每一个地方，那么干脆就不考虑入射方向和观测点，如下图所示：

那么直接让物体整个全部变亮即可，于是就得到了如下的近似公式：

L_a = k_aI_a

其中 $I_a$ 代表环境光照的单位光强
实际上如果位置确定，对于入射角度与观测角度而言，该式计算出来就是一个常数

在该模型中，间接光照的作用就仅仅体现在了让物体没有一块非常暗的区域上了。

总结

于是我们将三个部分结合起来，就得到了最终Blinn-Phong模型的表示方式：

L = L_a + L_d + L_s \\ = k_aI_a \\ + k_d(I/r^2)max(0,\vec n \cdot \vec l) \\ + k_s(I/r^2)max(0, \vec n \cdot \vec h)^p

最终着色效果如下：

可见该模型在着色上取得的了相对较好的结果，但事实上还有很多我们没有考虑的问题，比如下凹的区域的间接光照会比平坦的区域小，比如观测点距离越远看到的物体越暗（需要使用Radiance来解释）等等。

作色频率Shading Frequencies

下面我们来讨论以下作色频率。

那么什么是着色频率呢？观察下面的图：

图一中我们以平面为单位进行着色，以该平面的法线来计算其颜色，然后将该平面涂上一样的颜色
图二中使用了插值的方法，每个平面由顶点确定，于是我们计算各个顶点处的颜色，然后使用插值的方法计算出顶点围成的平面中的颜色。
图三中的着色则是应用在每个像素上，先求出每个平面的顶点的法线方向，然后通过插值计算出平面内部各个像素的法线方向，根据这些法线，计算每个顶点的着色

下面我们对这三种方法给出更严格的定义：

Flat Shading
- 对于每一个三角形面计算出该面的法线方向（任意两边的叉积），根据这个法线为平面着色
- 这种方式无法得到一个平滑的表面
Gouraud Shading（高洛德着色）
- 对于每个三角形，计算出他们顶点的法线方向，根据这些法线，计算出顶点的颜色，然后使用插值的方法来计算出三角形内部的颜色
- 当三角形稍微大一点（模型精度不够）时，高光就会不怎么明显，可见下图棕色球体，但比Flat更平滑。
Phong Shading（冯着色）
- 对于每个三角形，计算出他顶点的法线方向，然后通过插值，计算出三角形内部每个顶点的法线方向后根据这些法线计算出每个像素的着色
- 可以看到下图中的效果很不错
- 值得一提的是冯着色的发明者与上文提到的着色模型作者相同，但天妒英才，他在攻读博士期间因病去世。

从这些着色频率可以看出着色的工作量按顺序递增，并且着色的效果与模型的精细度还是有关系的，从下面的图片可以看出，在建模非常精细的情况下，三种着色频率能够得到相似的效果，此时我们通常会采用更节约算力的方法：

那么，抛开Flat Shading不谈，其余两种作色频率均需要我们去计算某个点的法线，这些法线应该如何计算呢？对于特定的机构，例如使用一系列三角形来模拟一个球体，那么这些三角形的顶点显然也对应了原本球体上的点，那么这些点就可以通过计算圆心到该点的方向得到法线方向：

但对于其他图形该怎么办呢？

计算顶点的法线

那么对于其他图形，我们可以借助共用这个顶点的其他三角形来计算该点的法线，例如下面这幅图：

对于共用该点的四个面，我们分别求出他们的法线，然后使用这些法线求平均，即可计算出该点的法线，但为了避免过于平均，即体现出面积更大的三角形贡献的更多，需要计算这些法线的加权平均，公式简写为如下形式：

N_v = \frac{\sum_i N_i}{|\sum_i N_I|}

计算逐像素的法线

通过上面的分析我们可以知道，能够通过插值的方法得到三角形内每个点的法线，如下图所示：

计算这些法线需要使用到重心插值法Barycentric Interpolation，由Kai Hormann与2014年出版于期刊Approximation Theory XIV: San Antonio 2013 上的一篇论文。之后会进行详细说明。

渲染管线（Graphics（Real-time Rendering）Pipeline）

渲染管线实际上就是定义了一个场景，到最后显示的一幅图片这一过程期间经过了怎样的过程。而实际上这些过程我们已经通过之前的学习有所了解了，接下来可以结合这幅图将之前学过的一些东西进行一个总结，就可以得到一个渲染管线了：

其中Fragments借用了OpenGL中的一个概念，也就是前文讨论光栅化时为了便于理解而引入的物理像素

我们可以将之前学到的只是进行如下排序：

顶点处理
- Vertex Processing，将三维空间中的点经过变换与投影，转化到二维空间，这一步结束将得到Vertex Stream
- Triangle Processing，将这些点连接形成三角形，这一步结束将得到Triangle Stream
光栅化（Rasterization）
- 即对原三角形进行采样与深度测试，这一步结束将得到Fragment Stream
着色
- Fragment Processing，对每个Fragment进行单独的着色，这一步结束将得到Shaded Fragments
- Framebuffer Operations，将Fragment结合得到最终需要显示的由像素组成的图片。

接下来我们在来看看之前学过的内容都发生在哪些位置：

Model，View，Projection transforms，即变换，应该发生在Vertex Processing阶段
Sampling triangle coverage，采样，发生在Rasterization阶段
Z-Buffer Visibility Tests，深度测试，发生在Fragment Processing阶段，事实上也可以认为他是一个属于光栅化的步骤
Shading，着色，发生在Vertex Processing或Fragment Processing阶段，如果我们使用Gouraud Shading渲染频率，那么一旦顶点产生就可以计算顶点的颜色，但如果我们使用Flat Shading或者Phong Shading，我们则需要在Fragment Processing中进行着色或进行下一步操作。
Texture Mapping，纹理映射，发生在Vertex Processing或Fragment Processing，后文将介绍这一块内容。

Shader Programs

每个顶点或片段（像素）都会执行的程序
- 对于顶点操作的程序称为Vertex Shader，顶点着色器。
- 对于片段（像素）操作的程序称为Fragment Shader，像素着色器

下面来看一个GLSL（GL Shader Language）的例子：

使用如下网站可以帮助我们实验shading的过程：

Shadertoy BETA

网站由Inigo Quilez提供，该用户在B站有账号。

图形管线的一种实现就是GPUs，GPU可以理解为高度并行的CPU。

纹理映射Texture Mapping

如图所示，其中小球上不同的位置具有不同的颜色反馈，由此可以体现出小球上不同的花纹，同理，地板上也能呈现出不同的花纹，通过学习Blinn-Phong模型我们知道，可以通过控制漫反射系数来控制漫反射颜色效果，因此，纹理映射就可定义为确定一组漫反射系数，使得物体表面的颜色反馈达到某一特定效果。那么我们如何定义物体表面呢？