需要预先了解：

模型、视图、投影（MVP）变换

1. 模型的表示

我们想要在电脑里创建一个几何体，就是要想办法去存储一个模型。首先，不免要考虑一个模型应当用什么数据表示。表示方式决定了存储、处理和绘制的方方面面。

几何表示分两大类：

隐式表示（implicit representation）：不直接给出表面上的点，而是给出点满足的关系。比如单位球面 $x^2 + y^2 + z^2 = 1$ ，以及距离场、水平集、CSG 等
显式表示（explicit representation）：直接给出点，或者给出从参数到三维点的映射。比如点云、贝塞尔曲面、多边形网格。

两类表示正好互补：

表示方式	典型例子	判断点在内外	找到表面上的点
隐式	代数曲面、距离场	容易，代入函数看符号	困难，需求解方程
显式	点云、贝塞尔曲面、网格	困难	容易，直接给出或按参数计算

我们在实时渲染中更多地会使用显式表示，尤其是网格。因为显式表示可以直接送进 GPU 渲染管线，而隐式表示通常需要先离散化成显式表示才能渲染。

下面介绍几种常见的显式表示方式。

1.1 点云

点云（point cloud）是最朴素的显式表示：一堆三维点 $\{(x_i, y_i, z_i)\}$ ，点与点之间没有任何连接关系。只要采样足够密集，离散的点就能近似出连续的表面——理论上任何表面都可以用它表示。

点云天然地适配三维扫描：激光扫描仪对真实物体表面采样，输出的直接就是点的集合。

点云的缺点也很直接：

覆盖大面积表面需要海量点，采样稀疏处会出现空洞
点云本身没有"面"的信息，缺少着色所需的法线，没法直接送进光栅化管线

实际流程中，点云通常作为中间格式，先重建（reconstruction）成网格再使用。

1.2 贝塞尔曲面

贝塞尔曲面（Bézier surface）是贝塞尔曲线的推广，属于典型的参数化显式表示：给定参数 $(u, v)$ ，代入公式就能直接算出表面上的点。

贝塞尔曲线

一条 $n$ 次贝塞尔曲线由 $n + 1$ 个控制点（control point） $b_0, b_1, \cdots, b_n$ 定义。以三个控制点的二次曲线为例，de Casteljau 算法计算曲线上参数 $t$ 处的点：相邻控制点两两做线性插值，得到一层新点；对新点重复这个过程，每层少一个点，直到只剩一个：

算法展开后有等价的解析形式：

$b^n(t) = \sum_{i=0}^{n} b_i \, B_i^n(t), \qquad B_i^n(t) = \binom{n}{i} t^i (1 - t)^{n - i}$

$B_i^n(t)$ 称为 Bernstein 多项式（Bernstein polynomial）。贝塞尔曲线有几条常用性质：

端点插值： $t = 0$ 时曲线经过 $b_0$ ， $t = 1$ 时经过 $b_n$ ；
端点处的切线方向：起点沿 $b_0 \to b_1$ ，终点沿 $b_{n-1} \to b_n$ ；
凸包性质（convex hull property）：曲线完全落在控制点围成的凸包内，控制点划定了曲线的活动范围。

从曲线到曲面

双三次贝塞尔曲面用 $4 \times 4 = 16$ 个控制点组成的网格定义（每条边界都是一条三次贝塞尔曲线）。计算曲面上的点 $\mathbf{S}(u, v)$ 分两步，本质是两轮 de Casteljau：

固定 $u$ ，对四行控制点各做一次曲线求值，得到 4 个点；
对这 4 个点以参数 $v$ 再做一次曲线求值，结果即 $\mathbf{S}(u, v)$ 。

解析形式是两个方向的 Bernstein 多项式相乘：

$\mathbf{S}(u, v) = \sum_{i=0}^{3} \sum_{j=0}^{3} b_{i,j} \, B_i^3(u) \, B_j^3(v)$

曲面同样有凸包性质：整张曲面落在控制点网格的凸包范围内。想把多张贝塞尔曲面拼成一张大表面，还需要满足连续性条件：至少位置连续（边界控制点重合），要看起来光滑则进一步要求跨界处切向共线。

1.3 网格

网格（mesh）是实时渲染中绝对主流的表示。它用一组顶点（vertex），加上描述"顶点如何连成面"的连接信息来描述一个三维几何体。在本篇博客中，我们更多的使用三角形网格（triangle mesh），即以三角形作为基本面片。三点确定一张平面，没有退化歧义，而且天然适配光栅化，整个 GPU 渲染管线都围绕三角形设计。

建模软件里或许更多地会用四边形网格，我们只需要把四边形加上一条对角线即可拆成两个三角形进行处理。

典型的存储结构是两个数组：

// 典型的三角形网格存储
std::vector<Vec3> positions;  // 顶点位置数组
std::vector<int>  indices;    // 索引数组：每 3 个索引组成一个三角形

三角形通过索引来实现共享顶点，既避免重复存储同一位置，也让相邻三角形自然缝合在一起。

上面这份 positions 数组，其实只存了顶点众多属性里最常见的一个：位置。真实的渲染情境里，一个顶点往往还带着法线（用于计算光照）、纹理坐标（用于纹理采样）等属性，每个属性服务于管线里的不同阶段。下面是常见的顶点属性及其用途：

属性	含义	用途
位置（position）	顶点在模型空间中的坐标	必需，决定顶点的空间位置
法线（normal）	顶点处的表面朝向	光照计算
纹理坐标（texture coordinate，UV）	顶点在纹理图片上的位置	纹理采样
颜色（color）	顶点自身的颜色	顶点着色，或作为材质的一部分
切线 / 副切线（tangent / bitangent）	与法线垂直的两个方向	法线贴图

一个顶点有哪些属性、各占多少字节，由顶点格式（vertex format）定义，渲染时顶点着色器按这个格式读取输入。这些属性在内存里的组织有两种典型方式：

交织存储（interleaved，也称 array of structures，AoS）：一个顶点的所有属性连续存放，存完再存下一个顶点，形如 [pos0 normal0 uv0 | pos1 normal1 uv1 | …]。访问单个顶点的全部属性时缓存友好，是多数引擎与图形 API 的默认选择。
分离存储（separate，也称 structure of arrays，SoA）：每种属性单独一个数组，形如 positions[]、normals[]、uvs[]。适合只访问某一种属性的场景（如蒙皮动画只更新位置），但访问单个顶点的全部属性时要跨多个数组取。

有时候，同一个位置需要装配上不同的法线（比如硬边（hard edge）），就必须拆成多个顶点，也就不能通过索引共享位置。

2. 顶点着色

顶点着色（vertex shading）是在 GPU 上对有关顶点的属性做处理的第一步。在进行顶点着色是，GPU 会运行叫做顶点着色器（vertex shader）的程序，逐个顶点地处理顶点属性。顶点着色器是我们见到的第一个可编程着色器，我们可以人为地设置顶点着色器所作的计算，来实现各种各样的效果。

我们前面讲到的 MVP 变换就是顶点着色器最典型的任务。不过很多时候，MVP 矩阵可能是在 CPU 端以及计算好了，顶点着色器（运行在 GPU 上的程序）只负责将 MVP 矩阵左乘到顶点位置上。

注意，虽然顶点着色听起来像是为顶点设置颜色的操作。但是事实上，我们上传到 GPU 的顶点本质上只是一系列用于描述属性的数组，颜色只是其中可能存在的一种（我们通常会用 3 个浮点数来表示其 RGB 值或用 4 个浮点数来表示其 RGB 值 + alpha 值）。顶点着色器本身就是用于对顶点的属性进行处理的程序，其中只强制要求了要输出处理后的顶点的位置，而其他属性则是根据需要进行处理；完全可以不处理颜色属性，甚至于顶点可以本身就不携带颜色相关的属性。

3. 图元的处理

网格里的顶点数据按照这样的方式传递：CPU 把模型的顶点属性打包进顶点缓冲（vertex buffer）并上传到 GPU，随后顶点着色器（vertex shader）逐个处理这些顶点。顶点着色器最常见的任务，是给每个顶点的位置左乘 MVP 矩阵，把位置从模型空间一路变换到裁剪空间（clip space）。

注：顶点着色器本质上是"一个顶点进、一个顶点出"的程序，对顶点做任何计算都可以，MVP 变换只是最典型的一种。事实上，MVP 变换既可以在 CPU 端做完，也可也在顶点着色器（GPU中的程序）中完成。

顶点着色器的输出，是一串孤立的顶点。它们还没有形成图元（这里我们就认为是三角形），要把这串顶点变成屏幕上的图像，还要经过以下三步：

图元装配：把孤立顶点按图元拓扑组装成图元；
图元裁剪：把可视范围外的图元丢弃，跨越边界的图元裁成新图元；
屏幕映射：把图元映射到屏幕坐标。

3.1 图元装配

图元装配（primitive assembly）是渲染管线里把孤立的顶点按照一定规律"打包"成图元的步骤。

图元装配的输入是顶点着色器输出的顶点数据，输出是图元数据。具体的装配规则由图元的类型与图元拓扑决定，下表以 OpenGL 的图元拓扑设置为例，介绍常见的规则：

拓扑模式	分组规则
`GL_POINTS`	每个顶点单独组成一个点图元
`GL_LINES`	每两个顶点组成一个线段图元，顶点数为奇数时最后一个顶点被丢弃
`GL_LINE_STRIP`	第一个顶点与第二个顶点组成第一条线段，第二个顶点与第三个顶点组成第二条线段，依次类推
`GL_LINE_LOOP`	与 `GL_LINE_STRIP` 类似，会将顶点组装为折线。但最后一个顶点会与第一个顶点连接闭合
`GL_TRIANGLES`	每三个顶点组成一个三角形图元，顶点数不是 3 的倍数时，余下的顶点被丢弃
`GL_TRIANGLE_STRIP`	第一个顶点与第二个顶点与第三个顶点组成第一个三角形，第二个顶点与第三个顶点与第四个顶点组成第二个三角形，依次类推
`GL_TRIANGLE_FAN`	所有三角形共享第一个顶点（扇形）

以 GL_TRIANGLES 为例，如果顶点着色器输出了 9 个顶点，装配后就是 3 个三角形；用 GL_TRIANGLE_STRIP 的话，同样 9 个顶点能装配出 7 个三角形。即图元装配可以通过不同的拓扑模式来节省顶点与带宽。

在实际的工程里，往往会默认使用 GL_TRIANGLES，因为它的装配规则最简单，便于控制。虽然会有重复的冗余顶点，但是对现代 GPU 的性能来说，顶点着色器的计算量远大于图元装配的计算量，冗余顶点带来的性能损失可以忽略不计。

3.2 图元裁剪

图元装配完成后，图元处于裁剪空间（clip space），坐标是齐次坐标 $(x, y, z, w)$ 。能被渲染的区域由六个不等式限定：

$-w \le x \le w, \qquad -w \le y \le w, \qquad -w \le z \le w$

每个不等式对应一个裁剪平面（如 $x = w$ 、 $x = -w$ 、 $y = w$ 等），六个平面围成的区域叫裁剪体积（clip volume）。

注：这里与 $w$ 比较而不是与 $1$ 比较，是因为裁剪发生在透视除法之前， $w$ 未必等于 $1$ ；而且对 $w = 0$ 的点（正好落在摄像机平面上的点）直接做除法会出错。这组不等式的效果，是把图元限制在透视除法后的标准立方体内。

裁剪（clipping）做的事，是求图元与裁剪体积的交集，留下完全落在可视范围内的部分。

首先是正确性要求：跨越近平面甚至跑到摄像机背后的图元，若不裁掉，透视除法后坐标会出错
其次是减少无用图元。对一个图元，结果分三种以下情况：

情况	处理
完全在裁剪体积内	原样传给下一阶段
完全在裁剪体积外	直接丢弃
一部分在内、一部分在外	在图元与裁剪平面的交点处生成新顶点，裁掉外面的部分

以三角形为例，一个跨越边界的三角形会被裁成落在体积内的一个或多个新三角形；新顶点通常是原边与裁剪平面的交点，它的属性（颜色、法线等）由原顶点插值得到。

判断顶点在平面的哪一侧、求边与平面的交点，都要用到平面的表示（见平面的表示方式），比如用平面方程 $Ax + By + Cz + D = 0$ 计算顶点到平面的有符号距离。裁剪完成后，剩下的图元严格落在裁剪体积内，可以安全地进入屏幕映射。

4. 屏幕映射

屏幕映射把裁剪后的图元从裁剪空间搬到屏幕上，分两步：先做透视除法（perspective division），再做视口变换（viewport transform）。

4.1 透视除法

经过透视投影后，所求得的空间的坐标是 $w \neq 1$ 的齐次坐标 $(x, y, z, w)$ 。透视除法把前三个分量统一除以 $w$ ：

$(x, y, z, w) \longrightarrow \left(\frac{x}{w},\ \frac{y}{w},\ \frac{z}{w},\ 1\right)$

将最后的 $w=1$ 的分量舍去，最终得到了落在 $[-1, 1]^3$ 内的坐标，我们将其称为 NDC坐标，也就是标准立方体里面的坐标。

如果不做透视除法，后续的处理里对这样的坐标进行线性插值时，会出现非线性的结果。

4.2 视口变换

得到了 NDC坐标后，还要将其映射到实际的屏幕窗口。设视口左下角在屏幕上的位置为 $(x_0, y_0)$ ，宽高为 $w_{vp}$ 、 $h_{vp}$ ，深度范围为 $[n_{vp}, f_{vp}]$ ：

$x_{screen} = \frac{x_{ndc} + 1}{2} \cdot w_{vp} + x_0$

$y_{screen} = \frac{y_{ndc} + 1}{2} \cdot h_{vp} + y_0$

$z_{depth} = \frac{z_{ndc} + 1}{2} \cdot (f_{vp} - n_{vp}) + n_{vp}$

其中 $x_{screen}$ 、 $y_{screen}$ 被称为屏幕坐标（screen coordinates），屏幕坐标和 $z_{depth}$ 一起，被称为窗口坐标（window coordinates）。

视口变换本质上只做了两件事：

把 $x$ 、 $y$ 从 $[-1, 1]$ 拉到视口的宽高，得到屏幕坐标；
把 $z$ 从 $[-1, 1]$ 拉到深度范围 $[n_{vp}, f_{vp}]$ ，得到深度值。这里的 $[n_{vp}, f_{vp}]$ 一般取 $[0, 1]$ （ OpenGL 里是 $[-1, 1]$ ）

4.3 屏幕坐标与实际像素的对应关系

只考虑横向上，最左侧像素的中心点坐标是 0.5，其范围是 $[0, 1)$ 。

本博客里约定：像素的索引从 0 开始，从左到右、从下至上递增。则左下角第一个像素是 $(0, 0)$ ；不难发现，坐标为 $(m, n)$ 的像素对应的屏幕坐标的范围是 $[m, m + 1) \times [n, n + 1)$ ，中心点坐标是 $(m + 0.5, n + 0.5)$ 。

示例：假设某个点的 NDC 坐标为： $(0.351 , 0.254 , 0.705)$ ，视口宽 800 像素、高 600 像素。

经过视口变换后，得到窗口坐标： $(540.4, 376.2, 0.8525)$ $(540.4, 376.2, 0.8525)$
- $\frac{(0.351 + 1)}{2} \times 800 = 540.4$
- $\frac{(0.254 + 1)}{2} \times 600 = 376.2$
- $\frac{(0.705 + 1)}{2} \times 1 = 0.8525$
对应可以找到像素索引为 $(540, 376)$