图形学光栅化

光栅化

光栅化是把标准化立方体渲染到屏幕上的过程

屏幕的定义：

• 一段像素数组
• 像素的数组长度就是分辨率的尺寸
• 屏幕是一个典型的光栅成像设备

像素的定义：

• Pixel 是 Picture Element 的缩写
• 一个简单的假设是每个像素认为是一个拥有单一颜色的小正方形（当然还有更复杂的假设放在后面讨论）
• 每个像素的颜色可以用 RGB 三个分量来表示

屏幕空间的定义（这里和虎书中的定义有所差别）：

• 屏幕空间是一个二维坐标系，原点在左下角，x 轴向右，y 轴向上
• 每个像素的索引由(x, y)唯一表示，x, y 均为整数
• 像素索引的范围是 $[0, width-1] \times [0, height-1]$
• 像素的中心点坐标为 $(x + 0.5, y + 0.5)$
• 屏幕空间的坐标范围是 $[0, width] \times [0, height]$

Viewport 视口变换

Viewport 视口变换是将标准化立方体的坐标转换为屏幕空间坐标的过程。

• 先不管 z 坐标，只需要把标准化$[-1,1]^2$转换为屏幕空间的$[0, width] \times [0, height]$
• 变换过程可以先把立方体平移到$[0,2]^2$再缩放到$[0, width] \times [0, height]$

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

三角形渲染的离散化

• 三角形是一个最基础的多边形
• 其他多边形可以通过三角剖分转换为三角形
• 三角形有一些独特的性质：
  • 唯一确定一个平面
  • 方便定义内外（仅通过叉乘运算即可确定）
  • 方便定义线性插值使三角形内颜色产生渐变过渡

我们该如何渲染一个三角形到一个像素空间中？

我们需要定义一个函数，该函数的输入是三角形在屏幕上的顶点数组，输出是一个个的像素数组来近似渲染一个三角形。三角形是一个连续的矢量图形，而像素是一个离散的栅格图形，所以一种近似的手段即为采样。

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

定义一个函数 $inside(tri, x, y)$，该函数的输入是一个三角形的顶点数组和一个像素的坐标，输出是一个 0 or 1，表示该像素是否要亮起。

最后就可以通过以下代码渲染出这个三角形了：

for (int x = 0; x < width; x++) {
    for (int y = 0; y < height; y++) {
        image[x][y] = inside(tri, x+0.5, y+0.5);
    }
}

判断点在三角形的内部

判断一个点是否在三角形内部可以通过计算该点到三角形三个顶点的向量叉积来实现。

如图，

$P_0 P_1 \times P_0 Q$ 方向朝屏幕外边，即 Q 在$P_0 P_1$的左边
$P_1 P_2 \times P_1 Q$ 方向朝屏幕外边，即 Q 在$P_1 P_2$的左边
$P_2 P_0 \times P_2 Q$ 方向朝屏幕里面，即 Q 在$P_2 P_0$的右边

如果 Q 在三角形内部，那么这三个叉积的方向应该都是朝屏幕外边的，点 Q 均在$P_0 P_1$、$P_1 P_2$、$P_2 P_0$的左边。

如果 Q 在三角形外部，那么至少有一个叉积的方向是朝屏幕里面的，点 Q 在$P_0 P_1$、$P_1 P_2$、$P_2 P_0$的右边。

如果 Q 在三角形的边上，那么至少有一个叉积的方向是 0 的，点 Q 至少在$P_0 P_1$、$P_1 P_2$、$P_2 P_0$的边上。一般来说边界上的点可以自己定义属不属于三角形内部。不影响最终渲染结果。

因此，我们可以通过计算三个叉积的方向来判断点是否在三角形内部。

int inside(const Triangle& tri, float x, float y) {
    Vector2 p0 = tri.v0;
    Vector2 p1 = tri.v1;
    Vector2 p2 = tri.v2;
    Vector2 q(x, y);
    Vector2 v0 = p1 - p0;
    Vector2 v1 = p2 - p1;
    Vector2 v2 = p0 - p2;
    Vector2 q0 = q - p0;
    Vector2 q1 = q - p1;
    Vector2 q2 = q - p2;
    float c0 = v0.cross(q0);
    float c1 = v1.cross(q1);
    float c2 = v2.cross(q2);
    if (c0 > 0 && c1 > 0 && c2 > 0) {
        return 1; // 点在三角形内部
    }
    return 0; // 点在三角形外部或边上
}

反走样

在光栅化过程中，直接使用像素中心点进行采样可能会导致锯齿状的边缘。为了减少这种锯齿现象，可以使用反走样技术。

图形在空间中采样导致的问题

高速行驶的车轮看起来像倒着转，本质是在时间上采样导致的问题

所有的这些采样都可能导致 aliasing 问题，本质上是因为采样的频率不够高，导致高频信息被丢失。

一种解决方案是降低高频信号，如图对原始图形先进行模糊操作，再进行采样：

频域

如图可以看到对三角函数采样，采样点能还原回的曲线越来越走样。

滤波

滤波：将特定频率的信号去除

如图是将图像变换到频域中的图像，频域图像从中心到周围频率越来越高。

中心集中较亮，说明图像的低频信息较多，高频信息较少。

加入使用高通滤波器抹除低频信号，图像只保留高频信号，图像可以看到边缘，这可以用于边缘检测。

加入使用低通滤波器抹除高频信号，图像只保留低频信号，图像变得模糊，这可以用于去除锯齿。

加入使用带通滤波器只保留中频信号，图像变成如图

卷积

滤波 = 平均 = 卷积

如图卷积就是卷积核在一个信号上滑动窗口，计算卷积核和信号的点乘，得到一个新的信号。

卷积定理：

• 时域的卷积等价于频域的乘积
• 时域的乘积等价于频域的卷积

二维图像上的卷积可以看作是二维卷积核在图像上滑动窗口，计算卷积核和图像的点乘，得到一个新的图像。

卷积核的大小和形状决定了滤波的效果，常见的卷积核有：

• 平均滤波器：所有权重相等的卷积核
• 高斯滤波器：权重按照高斯分布分布的卷积核
• 边缘检测滤波器：如 Sobel 滤波器、Laplacian 滤波器等

采样

采样就是在重复频率信号上的内容。

$X_{\alpha}(t)$ 是在时域上的一段信号，$X_{\alpha}(f)$ 是在频域上的傅里叶变换后的结果。

$P_{\delta}(t)$ 是在时域上的冲激函数，$P_{\delta}(f)$ 是在频域上的结果

$S(t)$表示$X_{\alpha}(t) \ast P_{\delta}(t)$，即在时域上对信号进行采样。

$S(f)$表示$X_{\alpha}(f)$, $ P_{\delta}(f)$做卷积，根据时域上的乘积等于频域上的卷积，这两者是等价的。

反走样

在一个三角形光栅化的过程中，我们可以计算三角形覆盖了一个像素的多少面积，根据面积求平均颜色，即$f(x, y) = inside(triangle, x, y)$的返回值不再是 0 或 1，而是一个 0 到 1 之间的浮点数，表示该像素被三角形覆盖的面积比例。

SSAA 算法

SSAA（Supersample Anti-Aliasing）是一种常用的反走样技术，它通过在每个像素内进行多次采样来减少锯齿现象。

如图是 2xSSAA 的采样方式，每个像素内有四个采样点，每个采样点都计算一次$inside(triangle, x, y)$，然后将四个采样点的结果平均化，得到该像素的最终颜色。

一个简单的代码如下：

int inside_binary(const Triangle& tri, float x, float y) {
    Vector2 p0 = tri.v0;
    Vector2 p1 = tri.v1;
    Vector2 p2 = tri.v2;
    Vector2 q(x, y);
    Vector2 v0 = p1 - p0;
    Vector2 v1 = p2 - p1;
    Vector2 v2 = p0 - p2;
    Vector2 q0 = q - p0;
    Vector2 q1 = q - p1;
    Vector2 q2 = q - p2;
    float c0 = v0.cross(q0);
    float c1 = v1.cross(q1);
    float c2 = v2.cross(q2);

    // 计算平均值
    return (c0 > 0 && c1 > 0 && c2 > 0) ? 1 : 0; // 点在三角形内部
}

float inside(const Triangle& tri, float x, float y) {
    float sum = 0.0f;
    // 2xSSAA
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            sum += inside1(tri, x + i * 0.5f, y + j * 0.5f);
        }
    }
    return sum / 4.0f; // 返回平均值
}

现代化的其他反走样算法

NxSSAA 理论会增大了 N^2 倍的计算量。

FXAA（Fast Approximate Anti-Aliasing）是一种基于图像处理的反走样技术，它实际上是一种后期处理技术，通过检测图像边缘锯齿，对其进行模糊处理来减少锯齿现象。

TAA（Temporal Anti-Aliasing）是一种基于时间的反走样技术，它通过对连续帧进行比较来减少锯齿现象。

超分辨率（Super Resolution）是一种通过对低分辨率图像进行处理，生成高分辨率图像的技术。它可以用于提高图像质量，减少锯齿现象。如 DLSS（Deep Learning Super Sampling）等技术。

深度测试 Z-Buffer

画家算法

画家算法是一种简单的渲染算法，它通过将物体按照从远到近的顺序进行绘制，来解决物体之间的遮挡问题。

画家算法在画之前需要对物体进行排序，按照从远到近的顺序进行绘制。排序算法时间复杂度为 O(n log n)，其中 n 是物体的数量。

但可能存在无法排序的情况，如图所示：

当如图的三角形 A、B、C 互相两两之间都存在遮挡时，画家算法无法正确渲染出物体的遮挡关系。

Z-Buffer

Z-Buffer（深度缓冲区）是一种解决物体遮挡问题的算法，它通过在渲染过程中维护一个深度缓冲区来记录每个像素的深度值，从而实现正确的遮挡关系。

• 假设 z 值越小离摄像机越近
• 对每个像素，如果其 z 坐标深度比当前深度缓存区的深度值小，则更新该像素的颜色和深度值
• 最终同时得到了 frame buffer 和 depth buffer 两幅图

PS: 在先前透视投影推导中，相机的视线是朝向负 z 轴的，所以 z 值越大的反而离摄像机越近。

这里为了方便起见，假设 depth buffer 的 z 值是反过来的，只取正数，越小的 z 越近，越大的 z 越远。

class FrameBuffer {
public:
    FrameBuffer(int width, int height) : width(width), height(height) {
        buffer.resize(width * height, Color(0, 0, 0));
    }
    void clear() {
        std::fill(buffer.begin(), buffer.end(), Color(0, 0, 0));
    }
    Color getColor(int x, int y) const {
        return buffer[y * width + x];
    }
    void setColor(int x, int y, const Color& color) {
        buffer[y * width + x] = color;
    }
}

class DepthBuffer {
public:
    DepthBuffer(int width, int height) : width(width), height(height) {
        buffer.resize(width * height, std::numeric_limits<float>::infinity());
    }
    void clear() {
        std::fill(buffer.begin(), buffer.end(), std::numeric_limits<float>::infinity());
    }
    float getDepth(int x, int y) const {
        return buffer[y * width + x];
    }
    void setDepth(int x, int y, float depth) {
        buffer[y * width + x] = depth;
    }
private:
    int width, height;
    std::vector<float> buffer;
};

void renderTriangle(const Triangle& tri, FrameBuffer& frameBuffer, DepthBuffer& depthBuffer) {
    for (int x = 0; x < frameBuffer.width; x++) {
        for (int y = 0; y < frameBuffer.height; y++) {
            float z = inside(tri, x + 0.5f, y + 0.5f);
            if (z < depthBuffer.getDepth(x, y)) {
                frameBuffer.setColor(x, y, tri.color);
                depthBuffer.setDepth(x, y, z);
            }
        }
    }
}

void main() {
    FrameBuffer frameBuffer(width, height);
    DepthBuffer depthBuffer(width, height);

    // 初始化深度缓冲区为无穷大
    depthBuffer.clear();

    Triangle tri = {v0, v1, v2, color};
    renderTriangle(tri, frameBuffer, depthBuffer);

    // 输出帧缓冲区到屏幕
    frameBuffer.display();
}