Triangles

2023-04-27

视口变换

由前面的知识知道，经过 MVP 操作之后，我们会得到一个中心在坐标原点的 $2 \times 2 \times 2$ 的标准立方体（ $[-1, 1]^3$ ）。

图一：标准立方体

接下来的工作就是要把这个立方体里面的内容显示到屏幕上。而要把东西画在屏幕上，我们首先要定义什么是屏幕：

屏幕是最典型的光栅成像设备（Raster display）
屏幕是一个由许多像素（pixels）组成的数组
屏幕的分辨率（resolution）就是数组的大小

Raster 的来源是德语，表示屏幕的意思。Rasterize 意思就是绘制到屏幕上（drawing onto the screen），也就是我们说的光栅化。

Pixel 是 Picture Element 的简写。到目前为止，可以把像素简单理解为一个小方块（实际上像素要远比这复杂），填充小方块的，只能是一种颜色。而颜色是由红、绿、蓝（red, green, blue）混合而来。

接着需要理解的一个概念是屏幕空间（Screen Space）。假设屏幕左下角在坐标原点， $x$ 轴向右， $y$ 轴向上（也有其他表示方法就不展开说了，以课件内容为主）。然后我们根据该坐标系定义像素的位置和范围：

用 $(x, y)$ 表示像素的位置（或索引），其中 $x$ 和 $y$ 都是整数
像素位置（或索引）的范围是 (0, 0) ~ (width-1, height-1)
像素 $(x, y)$ 的中心是 $(x + 0.5, y + 0.5)$
屏幕空间的覆盖范围是 (0, 0) ~ (width, height)

图二：屏幕空间

要把三维的 $2 \times 2 \times 2$ 的标准立方体（ $[-1, 1]^3$ ）绘制在二维的屏幕上，我们还有一个 $z$ 轴相关的问题没有讨论，在这里我们依然先忽略它，放到后面再单独说。忽略掉 $z$ 的话，剩下的就好办了，就是把 $xy$ 平面的 $[-1, 1]^2$ 的区间映射到屏幕空间 $[0, width] \times [0, height]$ 上。而这个操作我们之前学过：

x 缩放 $\frac{width}{2}$ 倍
y 缩放 $\frac{height}{2}$ 倍
此时中心还在原点，而屏幕是左下角在原点，故需平移 $(\frac{width}{2}, \frac{height}{2})$

图三：视口变换

这一变换也叫做视口变换，由上面的分析得知其变换矩阵为（注意这里由于忽略了 $z$ 方向，故矩阵第 3 行第 3 列值为 1）：

$M_{viewport} = \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)$

绘制三角形

视口变换后的结果也还只是在数学上描述了图像的位置信息，并没有精确到像素。而我们最终要做的事情是把这些用数字描述的图像跟屏幕上的像素一一对应起来。

图四：由三角形组成的图像

通常图像会被描述成由许多个多边形组成，尤其以三角形最为经典与广泛使用，因为相比于其他多边形，三角形有许多不错的性质：

三角形是最基础的多边形
- 其他多边形都可以分割成多个三角形
独特属性
- 三角形三边相连保证是在一个平面上（eg. 四边形对角对折可折成两个平面）
- 三角形对内和外有良好的定义（参考 Vectors 叉积相关的模块）
- 定义三角形三个顶点的不同属性，可以方便地在三角形内可以做渐变。即有定义良好的三角形顶点插值方法（质心插值）

所以很多情况下，把整个图像映射到屏幕像素上的过程也就相当于把所有组成图像的三角形映射到它对应的屏幕像素上，如下图五（注意看坐标的值，这里 $y$ 轴是向下的，也就是屏幕左上角在原点。跟我们前面的定义不一样，不过不影响理解）。那么我们要如何做呢？

图五：三角形光栅化

采样

一个简单的方法是采样。采样可以简单理解为是对一个连续的函数离散化的过程，也就是我们可以通过采样对一个函数进行离散化：

for (int x = 0; x < xmax; ++x) {
  output[x] = f(x);
}

因此我们可以定义一个函数：

inside(tri, x, y)
x, y 不一定是整数

这个函数的作用是：输入一个三角形和一个点 (x, y)，如果这个点在三角形内，则输出 1，否则输出 0。接着，我们遍历屏幕上所有像素，如果像素中心在三角形内，就判断为该像素在三角形内：

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); // 每一个像素的中心在 (x + 0.5, y + 0.5)
  }
}

而在 Vectors 叉积相关的模块里面我们已经讨论过了如何判断一个点是否在三角形里面了。如果点刚好在三角形边上，根据实际场景，可以认为它在三角形里面，也可以认为在外面。

到这里，我们就相当于把三角形绘制在屏幕上了：

图六：三角形绘制在屏幕上

锯齿（走样）

图我们绘制出来了，但它看起来不太对，因为它出现了很严重的锯齿（Jaggies）。锯齿出现的原因有两个：

每个像素本身就占据一定的大小
信号采样率不够高，导致了信号走样（Aliasing）

我们将在 Antialiasing 里面处理这个问题。

优化

仔细看前面的步骤，会发现一个效率的问题：

我们在绘制三角形时遍历了整个屏幕。

事实上我们不需要这么做，因为我们知道，一些离三角形很远的像素是肯定不可能落在三角形里面的。因此，我们可以根据三角形的位置，划分出一块需要进行遍历的区域。因为三角形的三个顶点我们是知道的，那我们就可以根据三角形三个顶点划分出左右上下四个边界，只对边界区域内的像素进行遍历。而这个区域就叫做轴向包围盒（axis-aligned bounding box - AABB）。