第3章：光栅化

章节概述

光栅化是将连续的几何图元转换为离散像素的过程，是现代实时渲染的核心技术。本章深入探讨光栅化的数学原理、算法实现和硬件优化策略。我们将从三角形的离散化开始，逐步深入到深度测试、抗锯齿技术，最后探讨现代GPU的光栅化管线设计。通过本章学习，读者将掌握从几何到像素的完整转换过程，理解现代图形硬件的设计哲学，并能够分析和优化光栅化性能。

3.1 三角形的离散化

3.1.1 为什么选择三角形

三角形是计算机图形学中最基本的图元，其优势包括：

• 平面性保证：三个不共线的点唯一确定一个平面，避免了非平面多边形的歧义性
• 凸性质：三角形必定是凸多边形，简化了内外判断和光栅化算法
• 插值简单：重心坐标提供了自然的线性插值框架，保证了C⁰连续性
• 硬件友好：固定的顶点数量便于并行处理和硬件优化
• 数学优雅：仿射不变性和投影不变性使得变换计算简洁高效

三角形的数学表示形式多样，可以用参数方程、隐式方程或重心坐标表示： $$\mathbf{p}(u,v) = (1-u-v)\mathbf{v}_0 + u\mathbf{v}_1 + v\mathbf{v}_2, \quad u,v \geq 0, u+v \leq 1$$

三角形的几何性质

三角形具有许多重要的几何性质，这些性质是光栅化算法的理论基础：

1. 单纯形性质：三角形是二维空间中的单纯形（simplex），这意味着它是能够张成二维空间的最小凸集。

2. 重心坐标的几何意义： - 重心坐标 $(\alpha, \beta, \gamma)$ 表示点到对边的有向距离比 - 物理意义：如果在三个顶点放置质量为 $(\alpha, \beta, \gamma)$ 的质点，则质心位于点 $\mathbf{p}$ - 面积比：$\alpha = \frac{\text{Area}(\mathbf{p}\mathbf{v}_1\mathbf{v}_2)}{\text{Area}(\mathbf{v}_0\mathbf{v}_1\mathbf{v}_2)}$

3. 仿射不变性：重心坐标在仿射变换下保持不变 $$T(\alpha\mathbf{v}_0 + \beta\mathbf{v}_1 + \gamma\mathbf{v}_2) = \alpha T(\mathbf{v}_0) + \beta T(\mathbf{v}_1) + \gamma T(\mathbf{v}_2)$$ 这个性质保证了我们可以在任意坐标系中进行插值计算。

4. 欧拉公式的应用：对于三角形网格，顶点数V、边数E、面数F满足： $$V - E + F = 2 - 2g$$ 其中g是亏格（genus）。对于简单连通网格，$g=0$，因此 $F \approx 2V$。

三角形与其他图元的比较

四边形：

• 优点：更少的图元数量，某些情况下更自然（如地形网格）
• 缺点：可能非平面，需要分割成三角形，插值更复杂

多边形：

• 优点：更灵活的建模
• 缺点：需要三角化，凹多边形处理复杂，硬件支持有限

曲面片（如Bézier）：

• 优点：更高的几何精度，更少的存储
• 缺点：计算复杂，需要细分（tessellation）成三角形

三角形的拓扑表示

在实际应用中，三角形通常组织成网格（mesh）结构：

1. 独立三角形：每个三角形存储三个顶点 - 优点：简单，无依赖 - 缺点：顶点重复，内存浪费

2. 索引三角形列表：顶点数组 + 索引数组 - 优点：共享顶点，节省内存 - 缺点：额外的间接访问

3. 三角形条带（Triangle Strip）： - 表示：$v_0, v_1, v_2, v_3, ...$ 形成三角形 $(v_0,v_1,v_2), (v_1,v_2,v_3), ...$ - 优点：最少的索引数据 - 缺点：需要退化三角形连接不同条带

4. 三角形扇（Triangle Fan）： - 表示：中心点 $v_0$ 与边界点 $v_1, v_2, ...$ 形成三角形 - 优点：适合圆形或扇形区域 - 缺点：应用场景有限

3.1.2 三角形的表示

三角形可以通过三个顶点 $\mathbf{v}_0, \mathbf{v}_1, \mathbf{v}_2$ 表示，每个顶点包含：

• 位置：$\mathbf{p} = (x, y, z, w)^T$（齐次坐标）
• 属性：颜色、法线、纹理坐标等

在屏幕空间中，经过投影变换后的顶点坐标为： $$\mathbf{p}_{\text{screen}} = \begin{pmatrix} x_s \ y_s \ z_s \end{pmatrix} = \begin{pmatrix} \frac{x_{ndc} + 1}{2} \cdot \text{width} \ \frac{y_{ndc} + 1}{2} \cdot \text{height} \ z_{ndc} \end{pmatrix}$$ 其中NDC（Normalized Device Coordinates）坐标范围为$[-1, 1]^3$。需要注意的是，$z_s$通常会经过非线性变换以优化深度精度分布。

三角形的隐式表示使用平面方程： $$\mathbf{n} \cdot (\mathbf{p} - \mathbf{v}_0) = 0$$ 其中法向量$\mathbf{n} = (\mathbf{v}_1 - \mathbf{v}_0) \times (\mathbf{v}_2 - \mathbf{v}_0)$决定了三角形的朝向。

坐标系变换链

三角形顶点经历的完整变换链：

1. 模型空间（Model Space） → 世界空间（World Space） $$\mathbf{p}_{world} = \mathbf{M}_{model} \mathbf{p}_{model}$$

2. 世界空间 → 观察空间（View Space） $$\mathbf{p}_{view} = \mathbf{V} \mathbf{p}_{world}$$

3. 观察空间 → 裁剪空间（Clip Space） $$\mathbf{p}_{clip} = \mathbf{P} \mathbf{p}_{view}$$ 此时坐标为齐次坐标 $(x_c, y_c, z_c, w_c)$

4. 透视除法 → NDC空间 $$\mathbf{p}_{ndc} = \begin{pmatrix} x_c/w_c \ y_c/w_c \ z_c/w_c \end{pmatrix}$$

5. 视口变换 → 屏幕空间 $$x_s = (x_{ndc} + 1) \cdot \frac{width}{2} + x_{viewport}$$ $$y_s = (y_{ndc} + 1) \cdot \frac{height}{2} + y_{viewport}$$

三角形的数据结构

高效的三角形表示需要考虑内存布局和缓存友好性：

struct Vertex {
    float3 position;     // 12 bytes
    float3 normal;       // 12 bytes
    float2 texcoord;     // 8 bytes
    float4 tangent;      // 16 bytes (含手性)
    // 总计 48 bytes，对齐到 64 bytes
};

struct Triangle {
    uint3 indices;       // 顶点索引
    uint materialID;     // 材质索引
    float area;          // 预计算的面积
    float3 normal;       // 预计算的法线
};

退化三角形的处理

退化三角形是指面积为零或接近零的三角形，可能由以下原因产生：

1. 共线顶点：三个顶点在一条直线上
2. 重复顶点：两个或更多顶点位置相同
3. 数值精度：浮点误差导致的近似共线

检测方法： $$\text{area} = \frac{1}{2}||(\mathbf{v}_1 - \mathbf{v}_0) \times (\mathbf{v}_2 - \mathbf{v}_0)|| < \epsilon$$ 处理策略：

• 预处理剔除：在网格处理阶段删除
• 运行时跳过：光栅化时检测并跳过
• 顶点合并：将距离过近的顶点合并

三角形的方向与缠绕顺序

缠绕顺序（winding order）决定了三角形的正面：

1. 逆时针（CCW）：OpenGL默认 - 从观察者角度看，顶点按逆时针排列为正面 - 法线指向观察者

2. 顺时针（CW）：DirectX默认 - 从观察者角度看，顶点按顺时针排列为正面

叉积与缠绕顺序的关系： $$\mathbf{n} = (\mathbf{v}_1 - \mathbf{v}_0) \times (\mathbf{v}_2 - \mathbf{v}_0)$$

• CCW：法线指向外（正面）
• CW：法线指向内（背面）

三角形的层次表示

对于复杂模型，三角形常组织成层次结构：

1. BVH（Bounding Volume Hierarchy）： - 每个节点包含子三角形的包围盒 - 用于加速光线追踪和碰撞检测

2. LOD（Level of Detail）： - 不同距离使用不同精度的三角形网格 - 减少远处物体的渲染开销

3. 空间划分： - Octree、KD-Tree等结构 - 加速空间查询和剔除

3.1.3 点在三角形内的判断

叉积法（Edge Function）

对于屏幕空间中的点 $\mathbf{p} = (x, y)$，判断其是否在三角形内部最常用的方法是边函数（edge function）： $$E_{01}(\mathbf{p}) = (x - x_0)(y_1 - y_0) - (y - y_0)(x_1 - x_0)$$ 边函数的几何意义是有向面积的两倍，符号表示点在边的哪一侧。点 $\mathbf{p}$ 在三角形内部当且仅当：

• $E_{01}(\mathbf{p}) \geq 0$
• $E_{12}(\mathbf{p}) \geq 0$
• $E_{20}(\mathbf{p}) \geq 0$

（假设三角形顶点按逆时针顺序排列）

边函数的优势在于：

1. 增量计算：相邻像素的边函数值可通过简单加法获得
2. 并行友好：不同像素的计算完全独立
3. 精确性：使用整数运算可避免浮点误差

边函数的数学性质

边函数具有以下重要性质：

1. 线性性：边函数是位置的线性函数 $$E(x+\Delta x, y+\Delta y) = E(x,y) + A\Delta x + B\Delta y$$ 其中 $A = y_1 - y_0$, $B = x_0 - x_1$

2. 符号几何意义： - $E > 0$：点在边的左侧（逆时针方向） - $E < 0$：点在边的右侧 - $E = 0$：点在边上

3. 与有向面积的关系： $$E_{01}(\mathbf{p}) = 2 \cdot \text{SignedArea}(\mathbf{v}_0, \mathbf{v}_1, \mathbf{p})$$

4. 缩放不变性： $$E_{01}(s\mathbf{p}) = s^2 E_{01}(\mathbf{p})$$

边函数的向量形式

使用向量表示可以更清晰地理解边函数： $$E_{01}(\mathbf{p}) = \det\begin{pmatrix} \mathbf{p} - \mathbf{v}_0 & \mathbf{v}_1 - \mathbf{v}_0 \end{pmatrix} = (\mathbf{p} - \mathbf{v}_0) \times (\mathbf{v}_1 - \mathbf{v}_0)$$ 这表明边函数实际上是两个向量的叉积的z分量。

精确边界处理（Edge Rules）

当像素中心恰好落在三角形边界上时，需要明确的规则避免：

• 像素被多个三角形同时覆盖
• 像素未被任何三角形覆盖

Top-Left规则：

bool is_top_edge(v0, v1) {
    return v0.y == v1.y && v0.x < v1.x;  // 水平且向右
}

bool is_left_edge(v0, v1) {
    return v0.y < v1.y;  // 向上
}

// 边界测试
if (E == 0) {
    accept = is_top_edge(v0, v1) || is_left_edge(v0, v1);
}

定点数实现

为了保证精确性，实际实现中使用定点数：

// 转换为定点数（16.8格式）
int32_t to_fixed(float f) {
    return (int32_t)(f * 256.0f + 0.5f);
}

// 定点数边函数
int32_t edge_fixed(int32_t x, int32_t y, 
                   int32_t x0, int32_t y0,
                   int32_t x1, int32_t y1) {
    return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);
}

优势：

• 精确：无浮点舍入误差
• 快速：整数运算
• 一致：相邻三角形共享边产生相同结果

重心坐标（Barycentric Coordinates）

重心坐标 $(\alpha, \beta, \gamma)$ 定义了点相对于三角形的位置： $$\mathbf{p} = \alpha \mathbf{v}_0 + \beta \mathbf{v}_1 + \gamma \mathbf{v}_2$$ 其中 $\alpha + \beta + \gamma = 1$。计算公式为： $$\alpha = \frac{E_{12}(\mathbf{p})}{E_{12}(\mathbf{v}_0)}$$ $$\beta = \frac{E_{20}(\mathbf{p})}{E_{20}(\mathbf{v}_1)}$$ $$\gamma = \frac{E_{01}(\mathbf{p})}{E_{01}(\mathbf{v}_2)}$$ 点在三角形内部当且仅当 $\alpha, \beta, \gamma \geq 0$。

重心坐标的性质：

• 仿射不变性：在仿射变换下保持不变
• 插值性质：任何顶点属性都可以通过重心坐标线性插值
• 归一化：$\alpha + \beta + \gamma = 1$ 确保了插值的正确性

重心坐标的计算方法

1. 面积比方法： $$\alpha = \frac{\text{Area}(\triangle \mathbf{p}\mathbf{v}_1\mathbf{v}_2)}{\text{Area}(\triangle \mathbf{v}_0\mathbf{v}_1\mathbf{v}_2)}$$ 使用叉积计算面积： $$\text{Area} = \frac{1}{2}|(\mathbf{v}_1 - \mathbf{v}_0) \times (\mathbf{v}_2 - \mathbf{v}_0)|$$

2. 线性系统方法： 解线性方程组： $$\begin{pmatrix} x \ y \ 1 \end{pmatrix} = \begin{pmatrix} x_0 & x_1 & x_2 \ y_0 & y_1 & y_2 \ 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} \alpha \ \beta \ \gamma \end{pmatrix}$$ 使用克拉默法则： $$\alpha = \frac{\det\begin{pmatrix} x & x_1 & x_2 \ y & y_1 & y_2 \ 1 & 1 & 1 \end{pmatrix}}{\det\begin{pmatrix} x_0 & x_1 & x_2 \ y_0 & y_1 & y_2 \ 1 & 1 & 1 \end{pmatrix}}$$

3. 边函数方法（最常用）： $$\alpha = \frac{E_{12}(\mathbf{p})}{2A}, \quad \beta = \frac{E_{20}(\mathbf{p})}{2A}, \quad \gamma = \frac{E_{01}(\mathbf{p})}{2A}$$ 其中 $A$ 是三角形面积。

重心坐标的几何解释

1. 质心解释：如果在三个顶点分别放置质量为 $(\alpha, \beta, \gamma)$ 的质点，系统的质心就在点 $\mathbf{p}$。

2. 垂直距离解释：重心坐标与点到对边的垂直距离成比例。

3. 参数化解释：$(\alpha, \beta, \gamma)$ 提供了三角形内部的一种自然参数化。

重心坐标的特殊点

• 重心：$(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ - 三条中线的交点
• 外心：到三个顶点距离相等的点
• 内心：$(\frac{a}{a+b+c}, \frac{b}{a+b+c}, \frac{c}{a+b+c})$ - 其中$a,b,c$是边长
• 垂心：三条高线的交点

重心坐标的数值稳定性

当三角形接近退化时，重心坐标计算可能不稳定。稳健的实现需要：

1. 条件数检查： $$\kappa = \frac{\max(|\mathbf{v}_0|, |\mathbf{v}_1|, |\mathbf{v}_2|) \cdot \max(|\mathbf{v}_1-\mathbf{v}_0|, |\mathbf{v}_2-\mathbf{v}_1|, |\mathbf{v}_0-\mathbf{v}_2|)}{2A}$$ 当 $\kappa$ 很大时，计算不稳定。

2. 退化处理： if (area < epsilon) { // 退化为线段或点 // 使用投影到最长边的方法 }

3. 双精度计算：对于大型场景，使用双精度避免精度损失。

其他判断方法

同侧法：检查点是否与对面顶点在每条边的同一侧。

对于每条边 $(\mathbf{v}_i, \mathbf{v}_j)$，检查： $$\text{sign}(E_{ij}(\mathbf{p})) = \text{sign}(E_{ij}(\mathbf{v}_k))$$ 其中 $\mathbf{v}_k$ 是第三个顶点。

面积法：比较子三角形面积之和与原三角形面积： $$\text{Area}(PAB) + \text{Area}(PBC) + \text{Area}(PCA) = \text{Area}(ABC)$$ 由于浮点误差，实际判断时需要容差： $$|\sum \text{Area}_i - \text{Area}_{total}| < \epsilon$$ 向量法：使用向量叉积的方向一致性：

vec2 v0v1 = v1 - v0;
vec2 v1v2 = v2 - v1;
vec2 v2v0 = v0 - v2;

vec2 v0p = p - v0;
vec2 v1p = p - v1;
vec2 v2p = p - v2;

float cross0 = v0v1.x * v0p.y - v0v1.y * v0p.x;
float cross1 = v1v2.x * v1p.y - v1v2.y * v1p.x;
float cross2 = v2v0.x * v2p.y - v2v0.y * v2p.x;

// 所有叉积同号则在内部
return (cross0 >= 0 && cross1 >= 0 && cross2 >= 0) ||
       (cross0 <= 0 && cross1 <= 0 && cross2 <= 0);

角度法：计算点对三角形三条边的张角之和：

• 内部点：张角之和 = $2\pi$
• 外部点：张角之和 < $2\pi$
• 边界点：张角之和 = $\pi$

各种方法的比较

| 方法 | 计算复杂度 | 精度 | 硬件适合性 | 备注 |

3.1.4 光栅化算法

包围盒算法（Bounding Box）

最简单的光栅化算法：

1. 计算三角形的轴对齐包围盒（AABB）
2. 遍历包围盒内的所有像素
3. 对每个像素进行内外测试

xmin = floor(min(x0, x1, x2))
xmax = ceil(max(x0, x1, x2))
ymin = floor(min(y0, y1, y2))
ymax = ceil(max(y0, y1, y2))

for y in [ymin, ymax]:
    for x in [xmin, xmax]:
        if (x, y) inside triangle:
            shade_pixel(x, y)

效率分析：

• 时间复杂度：$O((x_{max}-x_{min})(y_{max}-y_{min}))$
• 对于细长三角形效率低下（大量像素在三角形外）
• 适合小三角形或接近正方形的三角形

包围盒优化

1. 像素中心对齐： // 考虑像素中心偏移 xmin = floor(min(x0, x1, x2) - 0.5) xmax = ceil(max(x0, x1, x2) - 0.5)

2. 保守包围盒： 为了处理浮点误差，稍微扩大包围盒： const float epsilon = 0.001f; xmin = floor(min(x0, x1, x2) - epsilon); xmax = ceil(max(x0, x1, x2) + epsilon);

3. 空包围盒检查： if (xmin > xmax || ymin > ymax) { return; // 退化三角形，跳过 }

填充率分析

定义填充率（fill rate）为： $$\text{Fill Rate} = \frac{\text{Triangle Area}}{\text{Bounding Box Area}}$$ 不同形状三角形的填充率：

• 正三角形：约50%
• 直角三角形：50%
• 细长三角形：可能低至1%

低填充率意味着大量无效测试，需要更精细的算法。

增量算法（Incremental Algorithm）

边函数具有线性性质： $$E(x+1, y) = E(x, y) + (y_1 - y_0)$$ $$E(x, y+1) = E(x, y) - (x_1 - x_0)$$ 利用这一性质可以避免重复计算：

1. 计算起始点的边函数值
2. 使用增量更新相邻像素的值
3. 减少乘法运算，提高效率

增量算法的优化版本：

// 预计算增量
A01 = y0 - y1, B01 = x1 - x0
A12 = y1 - y2, B12 = x2 - x1
A20 = y2 - y0, B20 = x0 - x2

// 起始点边函数值
w0_row = E01(xmin, ymin)
w1_row = E12(xmin, ymin)
w2_row = E20(xmin, ymin)

for y in [ymin, ymax]:
    w0 = w0_row
    w1 = w1_row
    w2 = w2_row
    for x in [xmin, xmax]:
        if (w0 >= 0 && w1 >= 0 && w2 >= 0):
            shade_pixel(x, y)
        w0 += A01
        w1 += A12
        w2 += A20
    w0_row += B01
    w1_row += B12
    w2_row += B20

增量算法的性能分析

相比朴素算法：

• 乘法操作：从每像素 6 次减少到 0 次
• 加法操作：每像素 9 次（三个边函数，每个 3 次）
• 内存访问：顺序访问，缓存友好

并行增量算法

现代GPU使用2×2像素块（quad）为单位：

// 计算quad左上角的边函数值
float3 w_base = compute_edge_functions(quad_x, quad_y);

// 并行计算四个像素
float3 w00 = w_base;
float3 w10 = w_base + float3(A01, A12, A20);
float3 w01 = w_base + float3(B01, B12, B20);
float3 w11 = w_base + float3(A01+B01, A12+B12, A20+B20);

// SIMD处理
bool4 inside = (w00 >= 0) & (w10 >= 0) & (w01 >= 0) & (w11 >= 0);

定点数增量算法

为了保证精度，使用定点数运算：

// 16.16定点数格式
typedef int32_t fixed16;

// 转换为定点数
fixed16 to_fixed16(float f) {
    return (fixed16)(f * 65536.0f + 0.5f);
}

// 定点数增量
fixed16 w0 = to_fixed16(E01(xmin, ymin));
fixed16 A01_fixed = to_fixed16(y0 - y1);
fixed16 B01_fixed = to_fixed16(x1 - x0);

// 内循环
for (int x = xmin; x <= xmax; x++) {
    if (w0 >= 0 && w1 >= 0 && w2 >= 0) {
        shade_pixel(x, y);
    }
    w0 += A01_fixed;
    w1 += A12_fixed;
    w2 += A20_fixed;
}

分块光栅化（Tiled Rasterization）

现代GPU采用分块策略：

1. 将屏幕划分为固定大小的块（如8×8或16×16）
2. 首先进行块级别的粗测试
3. 只对可能相交的块进行像素级测试

层次化测试策略：

• 粗粒度测试：使用块的四个角点快速排除完全在外的块
• 细粒度测试：对通过粗测试的块进行逐像素测试
• 早期退出：一旦确定块完全在内，跳过像素级测试

扫描线算法（Scanline Algorithm）

经典的光栅化方法，特别适合软件实现：

1. 找出三角形与每条扫描线的交点
2. 对每条扫描线，填充交点之间的像素
3. 使用活动边表（AET）维护当前相交的边

扫描线转换的优势：

• 内存访问模式友好（行优先）
• 易于实现反走样（通过子像素精度）
• 适合并行化（不同扫描线独立）

Pineda算法

一种高效的并行光栅化算法：

1. 同时计算三个边函数
2. 使用边函数的符号判断像素位置
3. 支持任意遍历顺序（如Hilbert曲线）

3.1.5 亚像素精度与定点数

为避免浮点误差导致的裂缝，现代光栅化器使用定点数表示：

• 典型精度：16.8或24.8格式（整数部分.小数部分位数）
• 子像素精度：1/256像素（8位小数）或1/65536像素（16位小数）
• 保证相邻三角形的边界精确对齐

定点数转换： $$x_{fixed} = \lfloor x_{float} \times 2^{subpixel_bits} + 0.5 \rfloor$$

定点数的数学基础

定点数是一种用整数表示小数的方法。对于m.n格式：

• m位表示整数部分
• n位表示小数部分
• 总位数 = m + n
• 精度 = $2^{-n}$
• 范围 = $[-2^{m-1}, 2^{m-1} - 2^{-n}]$

定点数运算：

// 加法：直接相加
fixed_c = fixed_a + fixed_b;

// 乘法：需要右移
fixed_c = (fixed_a * fixed_b) >> n;

// 除法：需要左移
fixed_c = (fixed_a << n) / fixed_b;

为什么需要亚像素精度

1. 消除裂缝： - 浮点误差可能导致相邻三角形之间出现缝隙 - 定点数保证共享边的计算结果完全一致

2. 精确的边界处理： - 像素中心可能恰好落在三角形边上 - 需要一致的规则决定归属

3. 反走样支持： - 计算部分覆盖的像素 - 需要亚像素级别的精度

裂缝问题的根源

浮点运算的不精确性会导致：

1. T型接缝：共享边的两个三角形在光栅化时产生缝隙
2. 重复像素：同一像素被多个三角形覆盖
3. 丢失像素：边界上的像素未被任何三角形覆盖

裂缝问题的具体例子

考虑两个共享边的三角形：

• 三角形A：$(0,0), (10,0), (5,10)$
• 三角形B：$(10,0), (5,10), (10,10)$
• 共享边：$(10,0) - (5,10)$

如果使用浮点计算：

// 三角形A计算共享边函数
E_A = (x - 10) * (10 - 0) - (y - 0) * (5 - 10)
    = 10x - 100 + 5y

// 三角形B计算同一条边（反向）
E_B = (x - 5) * (0 - 10) - (y - 10) * (10 - 5)
    = -10x + 50 - 5y + 50
    = -10x - 5y + 100

// 理论上：E_A + E_B = 0
// 实际上：浮点误差可能导致 E_A + E_B ≠ 0

裂缝的视觉影响

裂缝在以下情况下尤为明显：

1. 高对比度场景：亮色背景上的暗色物体
2. 运动场景：裂缝会随着视角变化而闪烁
3. 反走样后：裂缝可能被放大

定点数运算规则

为保证水密性（watertight），必须遵循：

1. 顶点捕捉：共享顶点必须捕捉到相同的定点坐标
2. 填充规则：采用统一的边界归属规则（如top-left rule）
3. 边函数一致性：共享边的边函数计算必须产生相同结果

Top-left填充规则：

• 像素中心恰好在边上时，只有当边是"top"或"left"边时才包含该像素
• Top边：水平且位于三角形上方
• Left边：非水平且位于三角形左侧

Top-Left规则的实现

bool is_top_left_edge(vec2 v0, vec2 v1) {
    vec2 edge = v1 - v0;

    // Top edge: horizontal and going right
    if (edge.y == 0 && edge.x > 0) return true;

    // Left edge: going up
    if (edge.y > 0) return true;

    return false;
}

// 在边函数测试中应用
float bias = is_top_left_edge(v0, v1) ? 0 : -1;
if (edge_function + bias >= 0) {
    // 像素在三角形内
}

定点数的溢出处理

定点数运算可能溢出，需要谨慎选择位宽：

1. 边函数计算： - 输入：m.n格式的坐标 - 乘积：需要2m位 - 差值：需要2m+1位（考虑符号）

2. 安全位宽选择： - 屏幕坐标：16.8（支持65536×65536） - 边函数：32位有符号整数 - 插值参数：16.16（更高精度）

定点数与浮点数的混合使用

在现代GPU中，通常混合使用：

• 定点数：用于光栅化阶段（保证精确性）
• 浮点数：用于着色计算（需要大范围）

转换点：

// 光栅化后，转换回浮点
float x_float = fixed_x / (float)(1 << FRAC_BITS);
float y_float = fixed_y / (float)(1 << FRAC_BITS);

// 进行着色计算
color = shade_pixel(x_float, y_float, attributes);

定点数的性能优势

1. 确定性：相同输入总是产生相同输出
2. 并行性：无需处理浮点异常
3. 硬件效率：整数运算单元更简单、更快

定点数硬件实现

现代GPU中的定点数单元：

1. 专用定点数ALU： - 定点乘法器 - 移位器（用于除法） - 饱和算术（防止溢出）

2. 流水线设计： Stage 1: 坐标转换 (float -> fixed) Stage 2: 边函数计算 Stage 3: 覆盖测试 Stage 4: 属性插值设置

3. SIMD优化： - 4个像素同时处理 - 向量化的定点数运算

未来趋势

随着浮点单元的进步，一些新技术正在出现：

1. 混合精度模式： - 边界测试使用定点数 - 内部填充使用浮点数

2. 可配置精度： - 根据场景需求调整 - VR需要更高精度 - 移动设备可以降低精度

3. AI辅助裂缝检测： - 机器学习检测潜在裂缝 - 自动修复算法

3.1.6 属性插值

对于三角形内部的点，所有顶点属性需要进行插值：

透视正确插值

屏幕空间的线性插值不等于世界空间的线性插值。透视正确插值公式： $$\frac{1}{w} = \frac{\alpha}{w_0} + \frac{\beta}{w_1} + \frac{\gamma}{w_2}$$ $$attribute = \frac{\frac{\alpha \cdot attr_0}{w_0} + \frac{\beta \cdot attr_1}{w_1} + \frac{\gamma \cdot attr_2}{w_2}}{\frac{1}{w}}$$ 其中 $w$ 是齐次坐标的第四分量。

透视插值的必要性

考虑一条在3D空间中均匀分布的纹理坐标线，投影到屏幕后：

• 近处的间隔在屏幕上显得大
• 远处的间隔在屏幕上显得小
• 直接的屏幕空间插值会导致纹理扭曲

数学推导： 设世界空间中的线性插值参数为 $t$，则： $$\mathbf{p}_{world} = (1-t)\mathbf{p}_0 + t\mathbf{p}_1$$ 投影后在屏幕空间： $$t_{screen} = \frac{t/w_1}{(1-t)/w_0 + t/w_1}$$ 这表明屏幕空间的参数与世界空间的参数呈非线性关系。

插值优化

现代GPU采用的优化策略：

1. 预计算倒数：顶点着色器输出 $1/w$ 而非 $w$
2. 增量插值：利用重心坐标的线性性质
3. SIMD并行：同时插值多个属性

插值器硬件设计：

// 每个属性的插值
for each attribute:
    I = a0/w0 * α + a1/w1 * β + a2/w2 * γ
    attribute = I * w

特殊属性的处理

1. 深度值：通常线性插值 $z/w$，因为深度缓冲存储的就是这个值
2. 法线向量：插值后需要重新归一化
3. 颜色：可以选择是否进行透视校正（Gouraud着色通常不需要）

3.2 深度测试与抗锯齿

3.2.1 深度缓冲（Z-Buffer）

深度缓冲是解决可见性问题的标准方法：

• 为每个像素存储当前最近的深度值
• 新片段只有在更近时才会更新
• 与绘制顺序无关（order-independent）

深度测试算法：

for each fragment at (x, y) with depth z:
    if z < depth_buffer[x][y]:
        depth_buffer[x][y] = z
        color_buffer[x][y] = fragment_color

深度值的表示

从眼空间到NDC空间的深度变换： $$z_{ndc} = \frac{f+n}{f-n} + \frac{2fn}{f-n} \cdot \frac{1}{z_{eye}}$$ 归一化到[0,1]的窗口空间深度： $$z_{window} = \frac{z_{ndc} + 1}{2}$$

深度精度问题

透视投影导致深度精度分布极不均匀：

• 近处精度高，远处精度低
• 50%的精度集中在[n, 2n]范围内
• Z-fighting：深度值接近时的闪烁

精度分析： $$\frac{dz_{window}}{dz_{eye}} = \frac{fn}{(f-n)z_{eye}^2}$$ 这表明精度随距离平方反比下降。

深度精度优化方案

1. 对数深度缓冲： $$z_{log} = \frac{\log(z/n)}{\log(f/n)}$$

• 优点：精度分布更均匀
• 缺点：需要着色器计算，不兼容硬件深度测试

2. 反向Z（Reversed-Z）： - 使用 $1-z$ 作为深度值 - 配合浮点深度缓冲，利用浮点数在0附近的高精度 - DirectX 12和Vulkan的推荐做法

3. 多级深度缓冲（Cascaded Depth）： - 将场景分为多个深度范围 - 每个范围使用独立的深度缓冲 - 常用于大规模场景（如飞行模拟器）

4. W缓冲： - 直接存储线性深度 $w = z_{eye}$ - 精度分布均匀但总体精度较低 - 早期硬件支持，现已少见

3.2.2 早期深度测试（Early Z）

现代GPU在片段着色前进行深度测试：

• 减少无用的片段着色计算
• 要求深度写入是单调的
• 某些操作会禁用Early Z

Early Z的工作原理

传统管线：光栅化 → 片段着色 → 深度测试 Early Z管线：光栅化 → 深度测试 → 片段着色（仅通过的片段）

启用条件：

1. 片段着色器不修改深度值
2. 不使用discard或clip
3. 不启用alpha test
4. 深度测试函数是单调的（如LESS、GREATER）

性能影响

Early Z的效果取决于：

• 绘制顺序：前到后绘制可最大化Early Z效益
• 场景复杂度：overdraw越严重，Early Z收益越大
• 着色器复杂度：片段着色器越复杂，节省越多

3.2.3 层次深度缓冲（Hierarchical Z）

使用深度金字塔加速剔除：

• 存储块级别的最大/最小深度
• 快速剔除被遮挡的大块区域
• 与分块光栅化配合使用

Hi-Z的构建

自底向上构建深度金字塔：

// 对于每个上层像素
z_max = max(child[0], child[1], child[2], child[3])
z_min = min(child[0], child[1], child[2], child[3])

Hi-Z测试流程

1. 计算图元的保守深度范围[z_prim_min, z_prim_max]
2. 从粗到细进行层次测试： - 如果 z_prim_min > z_tile_max：图元被遮挡，剔除 - 如果 z_prim_max < z_tile_min：图元在前，快速通过 - 否则：细分到下一层继续测试

Z-Cull vs Z-Pass

• Z-Cull：Hi-Z测试失败，整块剔除
• Z-Pass：Hi-Z测试通过，跳过像素级深度测试
• 两者结合可显著减少深度缓冲带宽

3.2.4 抗锯齿基础理论

采样理论

根据奈奎斯特-香农采样定理，采样频率必须大于信号最高频率的两倍才能完美重建信号。图形学中的锯齿本质是采样不足导致的混叠（aliasing）。

频域分析：

• 原始信号：$f(x)$
• 采样过程：$f_s(x) = f(x) \cdot \sum_{n} \delta(x - nT)$
• 频谱混叠：当 $f_s < 2f_{max}$ 时，高频成分折叠到低频

图形学中的高频来源：

1. 几何边界：阶跃函数包含无限高频
2. 纹理细节：高频纹理模式
3. 镜面高光：急剧变化的光照
4. 几何细节：细小的几何特征

预滤波vs后滤波

1. 预滤波（Pre-filtering）： - 在采样前去除高频成分 - 理论上正确但计算困难 - 需要解析计算覆盖面积

2. 后滤波（Post-filtering）： - 对采样结果进行重建 - 实际常用但理论不完美 - 包括各种图像空间技术

理想的抗锯齿是预滤波，但计算成本高。实践中常采用超采样近似预滤波。

滤波核函数

常用的重建滤波器：

1. 盒式滤波器（Box）：$w(x) = 1, |x| < 0.5$
2. 三角滤波器（Tent）：$w(x) = 1 - |x|, |x| < 1$
3. 高斯滤波器：$w(x) = e^{-x^2/2\sigma^2}$
4. Lanczos滤波器：$w(x) = \text{sinc}(x)\text{sinc}(x/a), |x| < a$

3.2.5 超采样抗锯齿（SSAA）

最直接的抗锯齿方法：

• 以更高分辨率渲染
• 对结果进行下采样

计算成本：$O(n^2)$，其中 $n$ 是超采样倍数。

3.2.6 多重采样抗锯齿（MSAA）

MSAA优化了SSAA的性能：

1. 每个像素存储多个采样点
2. 片段着色只执行一次
3. 深度和覆盖测试对每个采样点独立进行

采样模式：

• 2×MSAA：旋转网格模式
• 4×MSAA：旋转盒模式或Quincunx
• 8×MSAA：优化的Poisson分布

覆盖计算：

coverage = 0
for each sample in pixel:
    if sample inside triangle:
        coverage += 1/num_samples
final_color = coverage * fragment_color + (1-coverage) * background

3.2.7 覆盖采样抗锯齿（CSAA）

NVIDIA的优化技术：

• 分离覆盖采样和颜色/深度采样
• 16×覆盖配合4×颜色/深度
• 减少内存带宽需求

3.2.8 时间抗锯齿（TAA）

利用时间域的信息：

1. 每帧使用不同的采样偏移（jittering）
2. 将多帧结果进行时间积累
3. 使用运动向量处理动态场景

时间积累公式： $$color_{new} = \alpha \cdot color_{current} + (1-\alpha) \cdot color_{history}$$ 其中 $\alpha$ 通常为 0.1-0.2。

3.2.9 形态学抗锯齿（MLAA/FXAA/SMAA）

后处理抗锯齿技术：

1. 边缘检测：识别几何边界
2. 模式匹配：确定边缘形状
3. 混合：根据模式进行像素混合

FXAA的亮度边缘检测： $$edge = |L_N - L_S| + |L_E - L_W| > threshold$$ 其中 $L$ 表示像素亮度。

3.3 现代GPU光栅化管线

3.3.1 GPU架构概述

现代GPU采用大规模并行架构：

• 流多处理器（SM）：独立的计算单元
• SIMT执行模型：单指令多线程
• Warp/Wavefront：32/64线程的执行组

3.3.2 图元装配（Primitive Assembly）

将顶点组装成图元：

1. 索引缓冲读取
2. 图元拓扑解释（点、线、三角形）
3. 图元剔除（背面、视锥体外）

背面剔除： $$\mathbf{n} \cdot \mathbf{v} = (v_1 - v_0) \times (v_2 - v_0) \cdot \mathbf{view} > 0$$

3.3.3 图元分配（Primitive Distribution）

将图元分配到屏幕分块：

1. 计算图元的屏幕空间包围盒
2. 确定覆盖的分块列表
3. 将图元引用添加到分块队列

分块大小权衡：

• 小分块：更好的负载均衡，更多的管理开销
• 大分块：更少的重复工作，可能的负载不均

3.3.4 片段生成与调度

每个分块独立处理：

1. 从队列读取图元
2. 生成片段（2×2像素块为单位）
3. 调度到着色单元

2×2像素块（Quad）的重要性：

• 计算屏幕空间导数（ddx、ddy）
• 纹理LOD计算
• 保证SIMD执行效率

3.3.5 深度缓冲压缩

减少带宽需求的关键技术：

差分压缩

对于平面区域，存储基准值和差分： $$z_{compressed} = z_{base} + \Delta z_x \cdot x + \Delta z_y \cdot y$$

深度范围压缩

存储块的最小/最大值和相对偏移： $$z_{normalized} = \frac{z - z_{min}}{z_{max} - z_{min}}$$

3.3.6 渲染输出单元（ROP）

负责最终的像素操作：

1. 深度测试
2. 模板测试
3. 混合操作
4. 写入帧缓冲

原子操作保证：

• 同一像素的操作串行化
• 不同像素可以并行

3.3.7 内存层次结构

优化的缓存设计：

1. L1缓存：纹理缓存、常量缓存
2. L2缓存：统一缓存，所有单元共享
3. 帧缓冲缓存：专用于ROP操作

带宽优化技术：

• Delta色彩压缩：存储与参考值的差
• 快速清除：标记而非实际写入
• 事务消除：检测并跳过冗余写入

3.3.8 可编程管线扩展

网格着色器（Mesh Shader）

新一代几何管线：

• 替代传统的顶点/几何着色器
• 支持GPU生成几何体
• 更灵活的图元剔除

可变率着色（VRS）

允许不同区域使用不同的着色率：

• 1×1、1×2、2×2、4×4等
• 基于内容的自适应
• 注视点渲染优化

3.3.9 光线追踪硬件集成

现代GPU集成了光线追踪单元：

• RT Core：硬件加速的BVH遍历
• 光栅化与光追混合：主要场景用光栅化，反射/阴影用光追
• 时间去噪：利用TAA框架降噪

本章小结

光栅化是将连续几何转换为离散像素的核心过程。本章涵盖了：

关键概念：

• 三角形离散化的数学基础：边函数、重心坐标
• 透视正确插值：$\frac{1}{w}$ 的线性插值
• 深度缓冲与可见性：Z-Buffer算法及其优化
• 抗锯齿理论：采样定理与各种AA技术
• GPU管线架构：从图元到像素的并行处理

重要公式：

• 边函数：$E(\mathbf{p}) = (\mathbf{p} - \mathbf{v}_0) \times (\mathbf{v}_1 - \mathbf{v}_0)$
• 重心坐标：$\mathbf{p} = \alpha \mathbf{v}_0 + \beta \mathbf{v}_1 + \gamma \mathbf{v}_2$
• 透视插值：$attr = \frac{\sum \frac{\alpha_i \cdot attr_i}{w_i}}{\sum \frac{\alpha_i}{w_i}}$
• 深度映射：$z_{ndc} = \frac{f+n}{f-n} + \frac{2fn}{f-n} \cdot \frac{1}{z_{eye}}$

性能考虑：

• 分块光栅化减少overdraw
• Early-Z避免无用着色
• 压缩技术降低带宽需求
• SIMT执行模型的并行效率

练习题

基础题

3.1 边函数计算 给定三角形顶点 $\mathbf{v}_0 = (0, 0)$, $\mathbf{v}_1 = (4, 0)$, $\mathbf{v}_2 = (2, 3)$，计算点 $\mathbf{p} = (2, 1)$ 的三个边函数值，并判断该点是否在三角形内部。

提示：注意顶点的顺序和边函数的符号。

3.2 重心坐标插值 三角形三个顶点的颜色分别为红色 $(1,0,0)$、绿色 $(0,1,0)$ 和蓝色 $(0,0,1)$。如果某点的重心坐标为 $(\alpha, \beta, \gamma) = (0.5, 0.3, 0.2)$，计算该点的插值颜色。

提示：直接应用重心坐标的定义。

3.3 透视正确插值 在屏幕空间，三角形顶点的深度值（$1/w$）分别为 0.5、0.25 和 0.125。某点的重心坐标为 $(0.4, 0.4, 0.2)$。如果顶点的纹理坐标分别为 $(0,0)$、$(1,0)$ 和 $(0.5,1)$，计算该点的透视正确纹理坐标。

提示：先插值 $1/w$，再进行透视除法。

3.4 MSAA覆盖计算 使用4×MSAA，采样点位置为像素中心偏移 $(-0.25, -0.25)$、$(0.25, -0.25)$、$(-0.25, 0.25)$ 和 $(0.25, 0.25)$。如果三角形边界恰好通过像素中心（从左下到右上的对角线），计算该像素的覆盖率。

提示：判断每个采样点相对于边界的位置。

挑战题

3.5 保守光栅化 设计一个保守光栅化算法，确保所有与三角形有任何重叠的像素都被标记。描述你的算法并分析其与标准光栅化的差异。考虑：如何扩展三角形边界？如何处理极小的三角形？

提示：考虑将三角形边界向外扩展半个像素。

3.6 自适应超采样 设计一个自适应超采样系统，只在需要的地方（如边缘）使用高采样率。你的系统应该包括：边缘检测标准、采样模式选择、以及性能与质量的权衡分析。

提示：可以基于深度或颜色的梯度来检测边缘。

3.7 深度缓冲精度优化 推导对数深度缓冲的数学公式，并分析其相对于标准深度缓冲的精度分布。实现一个深度值编码/解码方案，在24位定点数中最大化可用精度。

提示：考虑人眼对近处细节的敏感度。

3.8 GPU分块大小优化 分析不同分块大小（8×8, 16×16, 32×32）对GPU光栅化性能的影响。考虑：缓存命中率、负载均衡、几何复杂度的影响。设计一个实验来确定特定场景的最优分块大小。

提示：考虑三角形大小分布和屏幕空间局部性。

常见陷阱与错误（Gotchas）

1. 精度相关问题

浮点精度导致的裂缝

• 问题：相邻三角形的共享边在光栅化时可能产生裂缝
• 原因：浮点运算的舍入误差
• 解决：使用定点数运算，确保共享顶点的坐标完全相同

深度精度不足

• 问题：Z-fighting，远处物体深度分辨率低
• 原因：透视投影的非线性深度分布
• 解决：调整near/far平面，使用对数深度或反向Z

2. 插值错误

屏幕空间线性插值

• 问题：纹理扭曲，光照不正确
• 原因：忘记进行透视校正
• 解决：始终使用 $1/w$ 进行插值权重计算

属性插值溢出

• 问题：颜色值超出[0,1]范围
• 原因：重心坐标计算错误或数值精度问题
• 解决：验证重心坐标和为1，添加范围检查

3. 性能陷阱

过度绘制（Overdraw）

• 问题：同一像素被多次着色
• 原因：绘制顺序不当，缺少早期剔除
• 解决：前向后渲染不透明物体，使用Early-Z

小三角形问题

• 问题：GPU利用率低
• 原因：小于2×2像素的三角形导致quad利用率低
• 解决：使用LOD，合并小三角形

4. 抗锯齿相关

MSAA与透明度

• 问题：Alpha-tested几何体边缘仍有锯齿
• 原因：MSAA只对几何边缘有效，不处理着色器discard
• 解决：使用Alpha to Coverage或专门的透明度AA

TAA鬼影

• 问题：移动物体出现拖尾
• 原因：历史帧权重过高或运动向量不准确
• 解决：降低历史帧权重，改进运动向量计算

5. GPU特定问题

Warp发散

• 问题：性能显著下降
• 原因：同一warp内的线程执行不同分支
• 解决：排序绘制调用，减少动态分支

纹理缓存未命中

• 问题：带宽瓶颈
• 原因：纹理访问模式随机，mipmap选择不当
• 解决：改善UV布局，正确计算LOD

6. 调试技巧

视觉化调试

// 可视化重心坐标
color = vec3(alpha, beta, gamma);

// 可视化mipmap级别
color = heat_map(mipmap_level);

// 可视化overdraw
color = vec3(overdraw_count / max_overdraw);

性能分析要点

• 使用GPU profiler识别瓶颈
• 监控各阶段的吞吐量
• 检查缓存命中率

最佳实践检查清单

光栅化设计审查

几何处理

• [ ] 三角形顶点按一致顺序（通常逆时针）
• [ ] 共享顶点使用索引缓冲
• [ ] 避免退化三角形（面积接近0）
• [ ] 合理的三角形大小（避免过小）

精度管理

• [ ] 定点数用于光栅化坐标
• [ ] 适当的子像素精度（通常8-16位）
• [ ] Near/far平面合理设置
• [ ] 深度缓冲格式选择得当

性能优化

• [ ] 实施背面剔除
• [ ] 启用Early-Z（避免禁用它的操作）
• [ ] 合理的绘制顺序（不透明物体前到后）
• [ ] 批处理相似的绘制调用

抗锯齿策略

• [ ] 根据目标平台选择AA方法
• [ ] MSAA采样模式优化
• [ ] TAA的运动向量正确
• [ ] 后处理AA作为备选方案

内存与带宽

• [ ] 深度缓冲压缩启用
• [ ] 颜色缓冲压缩启用
• [ ] 合理的渲染目标格式
• [ ] 避免不必要的缓冲清除

着色器最佳实践

• [ ] 避免着色器中的discard（影响Early-Z）
• [ ] 减少动态分支
• [ ] 利用插值器硬件
• [ ] 正确的导数计算（维持2×2 quad）

现代特性利用

• [ ] VRS用于性能优化
• [ ] Mesh shader用于几何优化
• [ ] 硬件光追的选择性使用
• [ ] 多分辨率渲染技术

调试与验证

• [ ] 无渲染错误（裂缝、闪烁）
• [ ] 性能指标达标
• [ ] 内存使用合理
• [ ] 支持必要的调试可视化

代码质量

• [ ] 光栅化参数可配置
• [ ] 适当的错误处理
• [ ] 性能计数器集成
• [ ] 清晰的管线状态管理