GAMES101 现代图形学入门笔记：5、6 – 光栅化

该课程是 GAMES 开设的现代计算机图形学课程，系统而全面的介绍：光栅化、几何表示、光的传播理论、动画与模拟。每个方面都从基础原理出发讲解到实际应用，并介绍前沿的理论研究。本文是其 5、6 章光栅化的学习笔记。

1. 完成观测拼图 – 视口变换

透视投影

回顾：

• 六个参数，l、r、b、t、n、f
• 正交投影和透视投影的 z 保持不变
• 远近平面都投射在近平面上

frustum 的定义：

• 为近平面定义宽度、高度、宽高比（aspect radio）
• 定义 field-of-view（forvY），即可视角度范围；水平可视角度可以通过垂直可视角度和长宽比得到

可得：

\begin{aligned}
\tan{\frac{forvY}{2}} &= \frac{t}{|n|} \
aspect &= \frac{r}{t}
\end{aligned}
\tag{1}

屏幕

什么是屏幕？

• 一个像素的数组
• 数组的尺寸：分辨率
• 屏幕是一种典型的光栅成像设备（raster display）

什么是光栅？Raster 是德语中的屏幕；什么是光栅化？绘制到屏幕上。

什么是像素？

• FYI，picture element 的缩写
• 在课程中认为其为拥有原子颜色的小方块
• 颜色是不同等级 RGB 的混合

什么是屏幕空间？该课程中的屏幕空间定义

• 定义屏幕的左下角是屏幕空间的原点
• 认为像素的坐标是 x y 的二维元祖
• 认为数组的起始点是 0 0，终止点为 width-1 height-1
• 认为像素的中心为 (x+0.5,y+0.5)
• 屏幕覆盖范围为 0 0 到 width height

标准立方体的屏幕绘制

• 将 [-1,1]^2 变换到 [0,width] \times [0, height]
• 暂时不考虑 z
• 视口转换矩阵为：

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)
\tag{2}

接下来需要将三角形绘制到像素点

2. 光栅化：光栅显示器绘制

绘制机器

路径绘制机器：

• CNC Sharpie Drawing Machine – 路径绘制器
• Laser Cutters – 激光切割器

不同光栅现实设备：

• Oscilloscope – 示波器
  • Cathode Ray Tube 阴极射线管，偏转电子打到某个位置上
• Raster Display CRT – CRT 显示器
  • 逐行扫描
  • 视觉暂留，隔行扫描；每秒扫描奇偶数行；告诉运动存在撕裂
• Frame Buffer：Memory for a Raster Display
  • 将内存中的某个区域映射到图像
• Flat Panel Display 平板显示设备
• Liquid Crystal Display （LCD）Pixel
  • 存在以不同方向排布的两个光栅，光经过光栅只会留下在规定的方向上震动的能量
  • 通过液晶的扭曲改变光的方向
• LED 发光二极管
  • 亮或不亮
• Electronic Ink（Electrophoresis）Display – 电子墨水屏
  • 刷新率低

光栅显示器绘制

曲面细分：

• 三角曲面
• 多边形曲面

为什么使用三角形？

• 最基础的多边形
• 任何其他多边形可以拆分为三角形
• 独特的性质：
  • 三角形确定平面
  • 给定三角形三个顶点的属性，其内部点的属性能够通过它计算出来（插值）- 质心坐标插值

三角光栅化

要判断像素中心与三角形的关系；或者判断定义在屏幕空间上的某个函数在不同像素中心的值；甚至时间、空间、朝向、体积、反射等各种性质。

采样

采用一种简单的方法：采样。即给定一个连续的函数，给出对应位置的值。通俗地说，是将连续的值离散化的过程。

最基本的定义：inside(tri, x, y)

inside(t, x, y) =
\left {
\begin{aligned} &1, &(x, y)\ in\ triangle\ t\\&0, &otherwise \end{aligned}
\right.
\tag{3}

采样代码如下：

采样函数评估

可以使用叉乘法：按照某个特定循环顺序叉乘向量及点和三角形顶点连线，如果乘积同号则在内部。

边界情况？

• 本课程不作处理
• OpenGL 认为点在上边和左边在三角形内部，下边和右边不算

判断范围限定

只计算轴向包围盒 [xmin, xmax] \times [ymin, ymax]；Axis Aligned Bounding Box 轴向包围盒

对于占用空间小，但包围盒大的三角形，可以对每行计算包围盒，加速计算

实际屏幕的光栅化

显示器 RGB 像素点按照一定排列分布，并非原子性；且绿色较多，因为人眼绿色敏感。

打印为减色系统，要控制墨水量，且精准控制较为困难。

采样率不够高，且离散会产生锯齿

3. 反走样

采样理论

走样

锯齿（Jaggies）的学名叫做走样（Aliasing）：

• 光栅化的过程是在 2D 空间中对位置做采样的过程
• 照相是采样图像传感器平面的过程；
• 视频是对时间的采样

计算机图形学中的采样瑕疵：Sampling Artifacts（Errors/Mistakes/Inaccuracies）。典型的瑕疵包括：

• 锯齿：空间中的采样
• 摩尔纹：undersampling images
• 车轮效应（Wagon wheel effect）：时间上的采样
• 其他

隐藏在采样瑕疵之后的是 — 过快的信号变化速度，相对较慢的采样速度。

频率域和走样

傅立叶级数展开：任何一个周期函数都能够写成一系列正弦和余弦函数的组合加常数项；给定任何一个函数，都可以经过一个复杂的操作变成另一个函数，还可以通过逆变换变成另一个函数。

\begin{aligned}
F(\omega) &= \int_{-\infty}^{\infty}{f(x)e^{-2 \pi i\omega x}dx} \
f(x) &= \int_{-\infty}^{\infty}{F(\omega)e^{2\pi i\omega x}dw}
\end{aligned} \
Recall\ e^{ix} = \cos{x} + i\sin{x}

当频率过高时，采样的点无法恢复出原函数。同样的采样方法采样不同频率的两个函数，其结果无法区分，称为走样。

滤波

删除某些特定频率的内容称为滤波。

傅立叶变换可以将图像从时域转换到频域，然后进行滤波。删除低频信号则会保留边界信息 – 高通滤波器；删除高频信息则会模糊 – 低通滤波器；将高频、低频去掉，保留中间一些特定频率，则会保留一些变化不是很激烈的边界 – 带通滤波器。

卷积理论

滤波 Filtering = 卷积 Convolution = 平均 Averaging。卷积理论：时域上的卷积对应了频域上的乘积。

将原图和模版（卷积核）分别进行傅立叶变换，相乘，乘积进行逆傅立叶变换则得到结果。

更宽的滤波器核对应更低的频率。

采样分析

原函数乘以冲激函数可以得到采样结果。转换到频率则对应卷积，采样即重复原始信号的频谱。

采样的间隔会引起原始信号的频谱间隔较小，会发生重复。

实践中的反走样

典型的采样方法

• 增大采样率
  • 增加傅立叶变换后频域中原始信号复制的间隔
  • 需要更高的显示分辨率、传感器、帧缓冲
  • 成本较高或者条件不能满足
• 反走样
  • 傅立叶变换将高频信息去掉，然后采样

采样前滤波 Blurring（Pre-Filtering）Before Sampling

在采样前先对三角形进行模糊（滤波），然后对像素的颜色进行采样。反之不可以，称之为 Blurred Aliasing。

该方法相当于将傅立叶变换后频域中相互重叠的部分砍掉。然后使用原本的采样率采样。

实际操作中，用一定大小的低通滤波器进行卷积：

• Convolve: f(x,y) by a 1-pixel box-blur
• Then sample at every pixel’s center

相当于使用一个像素大小的滤波器给三角形进行平均 。

MSAA：Antialiasing By Supersampling

对于任何一个像素被划分为小的像素，对小的像素进行采样，使用采样结果进行平均。

MSAA 不是靠提升分辨率直接解决问题，而是靠提升分辨率进行模糊。

MSAA 的代价和缓解

MSAA 平方地增加了代价：

• 不规则划分
• 复用像素

其他抗锯齿

• FXAA（Fast Approximate AA）：先计算出原图，然后使用后图像处理去除锯齿，找到边界，替换为无锯齿的边界
• TAA（Temporal AA）：找上帧的信息，复用上帧的结果，相当于将 MSAA 的结果复用在时间上；对于运动的物体有特殊的运用

超分辨率/超采样

• 从低分辨率到高分辨率
• 仍然存在采样不足的问题
• DLSS（Deep Learning Super Sampling）：使用深度学习进行缺失细节的猜测

4. 可见性/遮挡

可见性/遮挡

直观的想法：先将较远的物体绘制在屏幕上，再绘制较近的物体，将其覆盖远处的物体，叫做画家（油画家）算法。

• 该方法可能难以检测深度
• 含有排序，其复杂度 O(nlogn)
• 覆盖关系可能复杂，形成环，难以判断远近关系

深度缓冲

该方法最终胜利，其思想为：

• 存储每个采样的 z 最小的属性
• 需要一个额外的位置存储深度信息：
  • 帧缓存颜色信息
  • 深度缓存（depth buffer/z-buffer）存储深度

注意：为了简化计算，我们认为 z 永远是正的，越小的 z 越近。

示例算法：

假设不会出现重叠的像素：实际中一般不可能判断相等的浮点数。该算法广泛地在所有 GPU 中实现。

对于 MSAA 需要对每个采样点计算深度。

复杂度：

• 深度缓存 O(n)
• 画家算法 O(nlogn)