光栅化

需要预先学习：

• 顶点、图元与屏幕映射

---

1. 光栅化

光栅化（rasterization）是把 图元 转换为 片元（fragment）的过程。

光栅化是渲染管线中从"几何"跨越到"图像"的一步：之前的模型变换、视图变换、投影变换处理的都是连续的几何数据，而屏幕是离散的像素网格，光栅化负责决定每个像素显示成什么颜色。

本笔记的光栅化只考虑三角形图元，不对其他图元（线段、点、曲面）做讨论。

那么，光栅化一个三角形的核心问题只有一个：哪些像素被这个三角形覆盖？

---

1.1 三角形设置

三角形设置（triangle setup）在硬件里由光栅器的固定功能单元完成，对每个三角形执行一次。我们会在此阶段提前算出后面三角形遍历阶段要反复用的全部常量，给后面遍历做预处理，避免每个像素重复算一遍。

输入是三个屏幕空间的顶点（已经过了 视口变换），尽量做到把能提前算的都提前算好，追求在逐像素阶段就只剩加法与比较。

有向面积的计算

我们将三角形顶点记为 $P_0 = (x_0, y_0)$、$P_1 = (x_1, y_1)$、$P_2 = (x_2, y_2)$，可以通过叉积计算有向面积：

$$A_2 = (x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)$$

这里的 $A_2$ 的绝对值是三角形面积的两倍，符号表示顶点的绕序：$A_2 > 0$ 表示顶点按逆时针顺序排列，$A_2 < 0$ 表示顺时针；$A_2 = 0$ 说明三点共线，三角形在屏幕上没有任何面积，直接丢弃。

后续在裁剪阶段，可以通过顶点绕序来判断三角形的正面与背面，决定是否丢弃背面三角形。

边函数的计算

接着要给三条边各建一个边函数（edge function）。我们约定第 $i$ 条边是顶点 $P_i$ 的对边（从 $P_{i+1}$ 指向 $P_{i+2}$，下标模 3）：

$$E_i(x, y) = (P_{i+1} - P_{i+2}) \times (P - P_{i+2}) = a_i x + b_i y + c_i$$

几何上它是点 $P$ 与这条边围成的平行四边形的有向面积，也就是 $\triangle P P_{i+1} P_{i+2}$ 面积的两倍；符号说明 $P$ 在边的哪一侧。三个边函数相加是个常数：

$$E_0 + E_1 + E_2 = A_2$$

含 $x$、$y$ 的项全部抵消，只剩面积。这个恒等式我们后面求 重心坐标 的步骤会用到。

包围盒的计算

这里的包围盒（bounding box）就是一个确保整个三角形都在其内部的矩形，我们实际找寻在三角形内部的所有像素时，可以只扫描包围盒范围内的像素，而不必扫全屏。

理论上，包围盒越小、贴三角形越紧，遍历的像素就越少，效率就越高。但是，包围盒的计算也要消耗时间，过于复杂的计算可能得不偿失。我们通常只会计算 AABB（axis-aligned bounding box，轴对齐包围盒），对于当前二维三角形的包围矩形情景计算思路如下：

1. 对三角形的三个顶点的 $x$、$y$ 坐标分别取最小值和最大值，得到包围盒的左下角 $(x_{min}, y_{min})$ 和右上角 $(x_{max}, y_{max})$；
2. 对包围盒进行取取整，得到整数像素索引范围：

   $$x_{min}' = \max(0, \lfloor x_{min} \rfloor), \quad y_{min}' = \max(0, \lfloor y_{min} \rfloor) \\ x_{max}' = \min(\text{width} - 1, \lceil x_{max} \rceil - 1), \quad y_{max}' = \min(\text{height} - 1, \lceil y_{max} \rceil - 1)$$

最终的包围盒是 $[x_{min}', x_{max}'] \times [y_{min}', y_{max}']$ 的矩形，遍历时只需要扫描这个范围内的像素。

更进一步地，我们可以在三角形设置阶段就计算好 $x$、$y$ 方向的增量：$$E_i(x + 1, y) = E_i(x, y) + a_i, \qquad E_i(x, y + 1) = E_i(x, y) + b_i$$ 这样内层循环可以做到没有乘法，只有加法。

代码示例

struct TriangleSetup
{
    float a[3], b[3], c[3];            // 三条边的边函数，下标 i 对应顶点 i 对面的边
    float area2;                       // 2 * 有向面积
    int   x_min, y_min, x_max, y_max;  // 包围盒（像素索引）
};

// 边函数 E(x, y) = (end - start) × (P - start) = a*x + b*y + c
void edgeFunction(const Vec2& start, const Vec2& end, float& a, float& b, float& c)
{
    a = start.y - end.y;
    b = end.x - start.x;
    c = (end.y - start.y) * start.x - (end.x - start.x) * start.y;
}

bool setupTriangle(const Vec2& p0, const Vec2& p1, const Vec2& p2,
                   int width, int height, TriangleSetup& ts)
{
    const Vec2 v[3] = { p0, p1, p2 };

    ts.area2 = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
    if (std::abs(ts.area2) < 1e-6f) return false;   // 退化三角形，直接丢弃

    for (int i = 0; i < 3; ++i)
        edgeFunction(v[(i + 1) % 3], v[(i + 2) % 3], ts.a[i], ts.b[i], ts.c[i]);

    float min_x = std::min({ p0.x, p1.x, p2.x });
    float max_x = std::max({ p0.x, p1.x, p2.x });
    float min_y = std::min({ p0.y, p1.y, p2.y });
    float max_y = std::max({ p0.y, p1.y, p2.y });

    ts.x_min = std::max(0, (int)std::floor(min_x));
    ts.y_min = std::max(0, (int)std::floor(min_y));
    ts.x_max = std::min(width - 1,  (int)std::ceil(max_x) - 1);
    ts.y_max = std::min(height - 1, (int)std::ceil(max_y) - 1);
    return ts.x_min <= ts.x_max && ts.y_min <= ts.y_max;
}

---

1.2 三角形遍历

三角形遍历（triangle traversal）也叫扫描转换（scan conversion）：在屏幕（计算包围盒后当然会使用包围盒）内逐像素采样并 判断采样点是否落在三角形内，落在内部就生成一个片元：

• 采样点：默认取像素中心 $(m + 0.5,\ n + 0.5)$，具体约定参见 顶点、图元与屏幕映射 ；
• 覆盖测试：三个边函数在采样点上同号即视为覆盖，符号统一以 $A_2$ 为准，顺、逆时针两种绕序都能处理；
• 填充规则：共享边只能属于一个三角形。常用的上左规则（top-left rule）规定落在上边与左边上的点算覆盖、下边与右边不算，否则相邻三角形会把同一条边画两遍，混合与模板会出错；
• 生成片元：被覆盖的像素产出一个 片元，携带屏幕位置、深度与插值后的属性。

// 伪代码：三角形遍历
for (int y = ts.y_min; y <= ts.y_max; ++y)
{
    for (int x = ts.x_min; x <= ts.x_max; ++x)
    {
        float px = x + 0.5f;   // 像素中心，也就是采样点
        float py = y + 0.5f;

        float e0 = ts.a[0] * px + ts.b[0] * py + ts.c[0];
        float e1 = ts.a[1] * px + ts.b[1] * py + ts.c[1];
        float e2 = ts.a[2] * px + ts.b[2] * py + ts.c[2];

        // 简化写法：严格实现还要用上左规则决定 0 算不算覆盖
        bool covered = ts.area2 > 0.0f
                     ? (e0 >= 0.0f && e1 >= 0.0f && e2 >= 0.0f)
                     : (e0 <= 0.0f && e1 <= 0.0f && e2 <= 0.0f);
        if (!covered) continue;

        Fragment f;
        f.x = x;
        f.y = y;
        f.depth = ...;          // 插值得到的深度
        f.attributes = ...;     // 插值得到的颜色、法线、UV
        emit(f);
    }
}

这段代码里每像素做三次乘加，实际硬件会采用用上面提及的增量代替：一行开始时算一次，往右走一步就加 $a_i$，换行时加 $b_i$ 再减去整行的跨度。对于边函数逐像素求值只依赖加法，天然适合大规模并行，也不必处理扫描线算法里各种退化情形

---

1.3 属性插值

把边函数归一化，就得到该点的 重心坐标 ：

$$\lambda_i = \frac{E_i}{A_2}, \qquad \lambda_0 + \lambda_1 + \lambda_2 = 1$$

点在内部时三个权重都非负，数值上正好等于三个子三角形的面积比。顶点属性（颜色、法线、UV 等）按权重加权：

$$A_{screen} = \lambda_0 A_0 + \lambda_1 A_1 + \lambda_2 A_2$$

它是 $(x, y)$ 的仿射函数，同样可以增量求值，所以"插值"本身时间开销很小。学习阶段，我们更加关心插值操作的正确性。

屏幕上均匀的间距，在透视投影下对应的视图空间间距并不均匀：近处一个像素跨过的表面小，远处一个像素跨过的表面大。直接把 $\lambda$ 用在顶点属性上，远处的纹理会显得被拉平、颜色与法线的变化也会失真。正确做法是让硬件分别插值 $A/w$ 与 $1/w$，在片元里相除：

$$A = \frac{\frac{\lambda_0 A_0}{w_0} + \frac{\lambda_1 A_1}{w_1} + \frac{\lambda_2 A_2}{w_2}}{\frac{\lambda_0}{w_0} + \frac{\lambda_1}{w_1} + \frac{\lambda_2}{w_2}}$$

其中 $w$ 是裁剪空间的齐次分量。分子分母都是屏幕空间的仿射函数，硬件照常增量求值，最后每个片元多做一次除法。

---

1.4 硬件中的光栅化

三角形设置与遍历都由 GPU 的固定功能单元完成，不可编程；顶点着色器接在它前面，片元着色器接在它后面。硬件实现与教科书算法的主要差别有三点：

• 分块（tile-based）：移动端 GPU 先把屏幕切成小块（常见 $16 \times 16$ 或 $32 \times 32$ 像素），几何阶段把每个三角形放进它覆盖的块列表，再逐块光栅化与着色。一个块的颜色、深度都放得进片上缓存，省下大量显存带宽。
• 保守光栅化（conservative rasterization）：默认规则只认"采样点落在三角形内"；三角形比一个像素还小时，采样点可能全部落空，整个三角形被漏掉，画面闪烁。保守光栅化把"与像素矩形有交集"也算覆盖，代价是边缘像素被重复着色。
• 按 quad 着色：片元着色器以 $2 \times 2$ 的像素块（quad）为单位执行，这样 dFdx、dFdy 能由相邻像素的差算出来（见 纹理映射）。三角形边缘的 quad 里，没被覆盖的像素会被屏蔽，但着色仍然执行，小三角形的着色成本因此被放大。

---

2. 采样与走样

---

2.1 点采样

遍历阶段每覆盖一个像素中心就生成一个片元，等价于在像素中心对连续图像取一个值：

$$I_{pixel}(m, n) = I(m + 0.5,\ n + 0.5)$$

这就是点采样（point sampling）。像素本身有面积，采样却只用一个点——三角形边缘横穿像素时，采样点只能落在某一边，像素要么整块取三角形的颜色，要么整块取背景色。

---

2.2 奈奎斯特采样定理

采样是有条件的。奈奎斯特-香农采样定理（Nyquist–Shannon sampling theorem）说：若信号的最高频率为 $f_{max}$，采样率 $f_s$ 必须满足

$$f_s > 2 f_{max}$$

才能由采样值无失真地重建原信号，$f_s / 2$ 称为奈奎斯特频率。采样率不够时，高于 $f_s/2$ 的成分不会消失，而是"折叠"成低频，看起来像一个原本不存在的低频图案，这叫混叠（aliasing），图形学里叫走样。

三角形边缘是阶跃信号：在像素内从一个值瞬间跳到另一个值，频谱无限宽。也就是 $f_{max} = \infty$，任何有限采样率都不满足定理——锯齿在数学上无法消除，只能减轻。分辨率越高，采样越密，锯齿越细，这就是"提高分辨率能减轻锯齿"的原因。

---

2.3 走样的表现

• 几何锯齿：三角形边缘呈阶梯状，放大看是一级一级的方块；
• 摩尔纹（moiré）：棋盘格、砖墙、网格这类细密纹理缩小时，出现大尺度的条纹与色块，本质是高频纹理被低频采样混成了低频图案（纹理的解法是 mipmap，见 纹理映射）；
• 时间走样：相机或物体移动时边缘"爬行"、远处高光闪烁，因为每一帧的采样点相对场景都挪了一点。

---

2.4 卷积

要消掉走样，思路不是"多取几个点"，而是"先模糊再采样"：先滤掉高于奈奎斯特频率的成分，再采样。滤波在数学上是卷积（convolution）：

$$I_{filtered}(x, y) = \iint I(u, v)\, h(x - u,\ y - v)\, du\, dv$$

$h$ 是滤波核。最简单的是盒式滤波器（box filter）：像素区域内权重相同，区域外为 0。于是像素值退化成区域内信号的平均：

$$C_{pixel} = \frac{1}{A_{pixel}} \iint_{\text{pixel}} I(u, v)\, du\, dv$$

三角形边缘的理想取值就是这个积分：被三角形覆盖的面积占像素面积的比例，即覆盖率（coverage）。一个像素 70% 被覆盖，理想结果就是 70% 的三角形颜色混上 30% 的背景色。各种抗锯齿算法都在用不同的代价近似这个积分。

---

2.5 反走样方法

• SSAA（超采样抗锯齿）：把场景渲染到更高分辨率的缓冲再平均，等价于在每个像素内多放了几个采样点，代价与采样数成正比；
• MSAA（多重采样抗锯齿）：只在光栅化阶段增加子采样点，覆盖测试与深度按子采样点进行，着色仍按像素执行一次，最后按覆盖率解析（见 抗锯齿算法）；
• FXAA / SMAA 等后处理：不增加采样，直接从渲染好的图像里检测边缘、猜测覆盖率；
• TAA 等时间方案：把采样点分散到多帧累积，静止时逐渐收敛，运动时靠重投影复用历史。

完整对比与实现见 抗锯齿算法。

注：光栅化只负责提供采样点，覆盖率的用法与着色频率由抗锯齿方案决定。不开抗锯齿时，一个像素仍然只贡献一个采样点。

---