new_games_101

第3章:光栅化

章节概述

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

3.1 三角形的离散化

3.1.1 为什么选择三角形

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

三角形的数学表示形式多样,可以用参数方程、隐式方程或重心坐标表示: \(\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)

三角形的拓扑表示

在实际应用中,三角形通常组织成网格(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}_{\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)\)

三角形的层次表示

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

  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}$ 在三角形内部当且仅当:

(假设三角形顶点按逆时针顺序排列)

边函数的优势在于:

  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$。

重心坐标的性质:

重心坐标的计算方法

  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)$ 提供了三角形内部的一种自然参数化。

重心坐标的特殊点

重心坐标的数值稳定性

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

  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);

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

各种方法的比较

方法 计算复杂度 精度 硬件适合性 备注
边函数 O(1) 极好 GPU标准方法
重心坐标 O(1) 同时用于插值
面积法 O(1) 浮点误差累积
角度法 O(1) 需要反三角函数

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)

效率分析:

包围盒优化

  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}}\)

不同形状三角形的填充率:

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

增量算法(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

增量算法的性能分析

相比朴素算法:

并行增量算法

现代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 亚像素精度与定点数

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

定点数转换: \(x_{fixed} = \lfloor x_{float} \times 2^{subpixel\_bits} + 0.5 \rfloor\)

定点数的数学基础

定点数是一种用整数表示小数的方法。对于m.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计算共享边函数
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规则的实现

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)

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

深度测试算法:

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}\)

深度精度问题

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

精度分析: \(\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管线:光栅化 → 深度测试 → 片段着色(仅通过的片段)

启用条件:

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

性能影响

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

3.2.4 抗锯齿基础理论

采样理论

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

频域分析:

图形学中的高频来源:

  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. 深度和覆盖测试对每个采样点独立进行

采样模式:

覆盖计算:

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的优化技术:

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采用大规模并行架构:

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)的重要性:

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操作

带宽优化技术:

3.3.8 可编程管线扩展

网格着色器(Mesh Shader)

新一代几何管线:

可变率着色(VRS)

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

3.3.9 光线追踪硬件集成

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

本章小结

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

关键概念:

重要公式:

性能考虑:

练习题

基础题

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

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

答案 计算三个边函数: - $E_{01}(\mathbf{p}) = (2-0)(0-0) - (1-0)(4-0) = 0 - 4 = -4$ - $E_{12}(\mathbf{p}) = (2-4)(3-0) - (1-0)(2-4) = -6 - (-2) = -4$ - $E_{20}(\mathbf{p}) = (2-2)(0-3) - (1-3)(0-2) = 0 - 4 = -4$ 由于所有边函数值都为负,说明三角形顶点是顺时针排列。对于顺时针排列,点在内部的条件是所有边函数值都小于等于0,因此点 $(2,1)$ 在三角形内部。 验证:可以计算重心坐标 $\alpha = \beta = \gamma = 1/3$,均为正值,确认点在内部。

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

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

答案 使用重心坐标进行线性插值: $$\mathbf{color} = \alpha \cdot \mathbf{c}_0 + \beta \cdot \mathbf{c}_1 + \gamma \cdot \mathbf{c}_2$$ $$= 0.5 \cdot (1,0,0) + 0.3 \cdot (0,1,0) + 0.2 \cdot (0,0,1)$$ $$= (0.5, 0, 0) + (0, 0.3, 0) + (0, 0, 0.2)$$ $$= (0.5, 0.3, 0.2)$$ 因此该点的颜色为 RGB = $(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$,再进行透视除法。

答案 首先插值 $1/w$: $$\frac{1}{w} = 0.4 \times 0.5 + 0.4 \times 0.25 + 0.2 \times 0.125 = 0.2 + 0.1 + 0.025 = 0.325$$ 然后计算每个分量的权重: $$\text{weight}_0 = \frac{0.4 \times 0.5}{0.325} = \frac{0.2}{0.325} = \frac{8}{13}$$ $$\text{weight}_1 = \frac{0.4 \times 0.25}{0.325} = \frac{0.1}{0.325} = \frac{4}{13}$$ $$\text{weight}_2 = \frac{0.2 \times 0.125}{0.325} = \frac{0.025}{0.325} = \frac{1}{13}$$ 最后插值纹理坐标: $$u = \frac{8}{13} \times 0 + \frac{4}{13} \times 1 + \frac{1}{13} \times 0.5 = \frac{4.5}{13} \approx 0.346$$ $$v = \frac{8}{13} \times 0 + \frac{4}{13} \times 0 + \frac{1}{13} \times 1 = \frac{1}{13} \approx 0.077$$ 透视正确的纹理坐标为 $(0.346, 0.077)$。

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

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

答案 三角形边界是从左下到右上的对角线,可以表示为:$y = x$ 对于每个采样点,检查是否在边界下方(假设三角形在边界下方): 1. $(-0.25, -0.25)$:$-0.25 < -0.25$ 不成立,不被覆盖 2. $(0.25, -0.25)$:$-0.25 < 0.25$ 成立,被覆盖 3. $(-0.25, 0.25)$:$0.25 < -0.25$ 不成立,不被覆盖 4. $(0.25, 0.25)$:$0.25 < 0.25$ 不成立,不被覆盖 覆盖率 = 1/4 = 25% 注意:如果三角形在边界上方,则采样点1和3会被覆盖,覆盖率为50%。

挑战题

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

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

答案 保守光栅化算法设计: 1. **边界扩展方法**: - 将每条边沿法线方向向外扩展 $\frac{\sqrt{2}}{2}$ 个像素(最坏情况下的像素对角线长度) - 边函数修改:$E'(p) = E(p) - \frac{\sqrt{2}}{2} \cdot ||\mathbf{n}||$ 2. **实现步骤**: ``` for each edge (v0, v1): normal = perpendicular(v1 - v0) offset = 0.5 * sqrt(2) * normalize(normal) expanded_edge = translate edge by offset ``` 3. **极小三角形处理**: - 如果三角形面积小于一个像素,至少光栅化其质心所在的像素 - 使用包围球测试:如果像素中心到三角形的距离小于 $\frac{\sqrt{2}}{2}$,则光栅化 4. **优化考虑**: - 使用分离轴定理进行精确的像素-三角形相交测试 - 对于轴对齐的边,扩展可以简化为0.5像素 5. **应用场景**: - 体素化 - 碰撞检测 - 阴影体生成

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

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

答案 自适应超采样系统设计: 1. **边缘检测标准**: ``` edge_score = max( |depth_center - depth_neighbor| / depth_center, |color_center - color_neighbor|, |normal_center · normal_neighbor - 1| ) ``` 2. **采样策略分级**: - Level 0 (1×): edge_score < 0.1 - Level 1 (4×): 0.1 ≤ edge_score < 0.3 - Level 2 (8×): 0.3 ≤ edge_score < 0.6 - Level 3 (16×): edge_score ≥ 0.6 3. **实现流程**: - Pass 1: 以1×采样率渲染,同时输出G-buffer - Analysis: 分析G-buffer,标记需要超采样的像素 - Pass 2: 对标记的像素进行超采样 - Resolve: 合并结果 4. **优化技术**: - 时间复用:结合TAA,减少当前帧的采样需求 - 预测:基于前一帧的边缘信息预测当前帧 - 分块处理:以2×2或4×4块为单位决定采样率 5. **性能分析**: - 最佳情况:大部分平滑区域,接近1×性能 - 最坏情况:全是边缘,退化为完全超采样 - 典型场景:20-40%的像素需要超采样,性能提升2-3倍

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

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

答案 1. **对数深度推导**: 标准深度:$z_{std} = \frac{f+n}{f-n} - \frac{2fn}{(f-n)z}$ 对数深度:$z_{log} = \frac{\log(z/n)}{\log(f/n)}$ 精度分析: - 标准深度:$\frac{dz_{std}}{dz} = \frac{2fn}{(f-n)z^2}$(随z²下降) - 对数深度:$\frac{dz_{log}}{dz} = \frac{1}{z\log(f/n)}$(随z线性下降) 2. **24位编码方案**: ``` encode(z_eye): // 使用伪对数编码 if z_eye < split_distance: // 近处使用线性 encoded = (z_eye - n) / (split - n) * 0.5 else: // 远处使用对数 encoded = 0.5 + 0.5 * log(z_eye/split) / log(f/split) return uint24(encoded * (2^24 - 1)) ``` 3. **精度分布优化**: - 分割点选择:$split = \sqrt{nf}$(几何平均) - 近处精度:~0.01mm at 1m - 远处精度:~1m at 1000m 4. **实际考虑**: - 反向Z + 浮点:利用浮点数的指数特性 - W缓冲:直接存储线性深度1/w - 多级深度:近景和远景使用独立缓冲

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

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

答案 1. **理论分析**: **8×8分块**: - 优点:细粒度负载均衡,小三角形效率高 - 缺点:管理开销大,大三角形跨越多个块 **16×16分块**: - 优点:平衡的选择,适合中等大小三角形 - 缺点:某些场景可能不够灵活 **32×32分块**: - 优点:管理开销小,大三角形效率高 - 缺点:负载不均衡风险,小三角形浪费 2. **性能模型**: ``` Cost = N_tiles × (C_setup + N_prims × C_raster + N_pixels × C_shade) 其中: - N_tiles = ceil(W/tile_size) × ceil(H/tile_size) - N_prims = avg_prims_per_tile(与分块大小相关) - N_pixels = tile_size²(实际着色的像素可能更少) ``` 3. **实验设计**: ``` for tile_size in [8, 16, 32]: for scene in [many_small_tris, few_large_tris, mixed]: measure: - Frame time - Tile occupancy - Cache miss rate - Warp divergence ``` 4. **自适应策略**: - 基于场景统计动态选择 - 混合分块:不同区域使用不同大小 - 预测模型:基于前几帧的统计信息 5. **实际建议**: - UI渲染:8×8(many small triangles) - 游戏场景:16×16(平衡选择) - CAD/建筑:32×32(大型三角形)

常见陷阱与错误(Gotchas)

1. 精度相关问题

浮点精度导致的裂缝

深度精度不足

2. 插值错误

屏幕空间线性插值

属性插值溢出

3. 性能陷阱

过度绘制(Overdraw)

小三角形问题

4. 抗锯齿相关

MSAA与透明度

TAA鬼影

5. GPU特定问题

Warp发散

纹理缓存未命中

6. 调试技巧

视觉化调试

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

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

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

性能分析要点

最佳实践检查清单

光栅化设计审查

几何处理

精度管理

性能优化

抗锯齿策略

内存与带宽

着色器最佳实践

现代特性利用

调试与验证

代码质量