文章

TinyRenderer（二）：三角形光栅化

发表于 更新于
作者
20 分钟阅读
TinyRenderer（二）：三角形光栅化

上一篇介绍了如何在像素网格上画一条线。现在，我们面对下一个问题：如何在屏幕上填充一个三角形。

三角形是 3D 渲染中最基本的图元。无论多么复杂的模型，最终都会被分解为三角形网格。所以”填充三角形”这一步，是整个软渲染器的核心通道。

tr 的这篇文章给了一个由易到难、层层递进的介绍。本文依照这个思路，先介绍古老的扫描线方法，再介绍现代的包围盒加重心坐标方法，并结合代码讲解重心坐标的求解与应用，最后讨论背面剔除与 z-buffer 的关系。

什么是”好”的三角形填充算法

tr 给出了三条标准：

  1. 简单快速。
  2. 对称性：结果不能依赖于顶点传入的顺序。
  3. 无缝拼接：两个共享边的三角形之间，不能因为光栅化舍入产生缝隙。

第三条尤其重要。现实中一个 mesh 的每条内部边都被两个三角形共享，如果两个三角形对同一条边的光栅化结果不一致，就会出现看得见的黑缝。

扫描线渲染（Scanline Rendering）

扫描线是一种古老但直观的方法，思路来自 CRT 显示器逐行扫描的硬件特性：逐行（scanline）确定填充范围，再水平填色。

顶点排序

给定三角形的三个顶点 $a, b, c$，首先按 $y$ 坐标从小到大排序（$a.y \le b.y \le c.y$）。用冒泡排序对三个元素排序最为直接：

1
2
3

if a.y > b.y: swap(a, b)
if b.y > c.y: swap(b, c)
if a.y > b.y: swap(a, b)

排序后，三角形被两条边”切割”成可以分开处理的两半：

  • 长边（从 $a$ 到 $c$，对应整个高度范围）
  • 短边 B：从 $a$ 到 $b$（下半段），再从 $b$ 到 $c$（上半段）

边界光栅化与填充

对于每一行 $y$（从 $a.y$ 到 $c.y$），分别在长边和当前短边上用线性插值求出左右边界的 $x$ 坐标，然后水平连线填充：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def triangle(a, b, c):
    # 按 y 坐标排序
    pts = sorted([a, b, c], key=lambda p: p.y)
    a, b, c = pts

    total_h = c.y - a.y

    # 下半段：a -> b
    for y in range(a.y, b.y + 1):
        seg_h = b.y - a.y + 1
        t1 = (y - a.y) / total_h   # 长边进度
        t2 = (y - a.y) / seg_h     # 短边进度
        xa = a.x + (c.x - a.x) * t1
        xb = a.x + (b.x - a.x) * t2
        draw_horizontal(min(xa, xb), max(xa, xb), y)

    # 上半段：b -> c
    for y in range(b.y, c.y + 1):
        seg_h = c.y - b.y + 1
        t1 = (y - a.y) / total_h   # 长边进度
        t2 = (y - b.y) / seg_h     # 短边进度
        xa = a.x + (c.x - a.x) * t1
        xb = b.x + (c.x - b.x) * t2
        draw_horizontal(min(xa, xb), max(xa, xb), y)

这个方法在 CPU 单线程环境下相当高效。但扫描线方法的代码并不简洁——需要处理上下两半，还要特别注意共线退化情况（比如三个顶点的 $y$ 坐标有相等的情况）。更重要的是，它本质上是串行的：每行必须在上一行的基础上推进，无法并行。

现代方法：包围盒 + 重心坐标

tr 给出的第二种方法可以说是更”现代”的思路，其伪代码极为简洁：

1
2
3
4
5
6
7
8

triangle(vec2 points[3]) {
    vec2 bbox[2] = find_bounding_box(points);
    for (each pixel in the bounding box) {
        if (inside(points, pixel)) {
            put_pixel(pixel);
        }
    }
}

这种写法对初学者非常友好，在图形学专家眼里也不陌生——GPU 的光栅化硬件本质上就是这样工作的：包围盒内的所有像素由成千上万个线程并行处理，每个线程独立判断自己是否在三角形内。

轴对齐包围盒（AABB）

对三个顶点取 $x, y$ 的最小值和最大值，即可确定 AABB：

\[x_{min} = \min(x_0, x_1, x_2), \quad x_{max} = \max(x_0, x_1, x_2)\] \[y_{min} = \min(y_0, y_1, y_2), \quad y_{max} = \max(y_0, y_1, y_2)\]

遍历包围盒内所有整数像素坐标 $(x, y)$，对每个点判断其是否在三角形内。

重心坐标（Barycentric Coordinates）

判断点是否在三角形内，最优雅的方法是使用重心坐标。

对于三角形 $ABC$ 和一个点 $P$，我们可以将 $P$ 表示为三顶点的线性组合：

\[P = \alpha A + \beta B + \gamma C\]

其中 $\alpha + \beta + \gamma = 1$。这三个系数 $(\alpha, \beta, \gamma)$ 就是 $P$ 关于 $\triangle ABC$ 的重心坐标。它们有直观的几何含义：

\[\alpha = \frac{\text{Area}(\triangle PBC)}{\text{Area}(\triangle ABC)}, \quad \beta = \frac{\text{Area}(\triangle PCA)}{\text{Area}(\triangle ABC)}, \quad \gamma = \frac{\text{Area}(\triangle PAB)}{\text{Area}(\triangle ABC)}\]

即各坐标分量等于以 $P$ 为顶点、对边为底边的子三角形面积占总面积的比例。利用这一性质可以直接得出内外判断：

  • 当 $\alpha, \beta, \gamma$ 全部 $\geq 0$ 时，$P$ 在三角形内（或边上）。
  • 只要有一个分量 $< 0$，$P$ 在三角形外。

求解重心坐标

将 $P = \alpha A + \beta B + \gamma C$ 结合 $\alpha + \beta + \gamma = 1$ 展开，可以得到：

\[P - C = \alpha (A - C) + \beta (B - C)\]

令 $\vec{CA} = A - C$，$\vec{CB} = B - C$，$\vec{CP} = P - C$，则方程变为：

\[\alpha \cdot \vec{CA} + \beta \cdot \vec{CB} = \vec{CP}\]

展开为分量形式，是一个 $2 \times 2$ 的线性方程组：

\[\begin{bmatrix} CA_x & CB_x \\ CA_y & CB_y \end{bmatrix} \begin{bmatrix} \alpha \\ \beta \end{bmatrix} = \begin{bmatrix} CP_x \\ CP_y \end{bmatrix}\]

解出 $\alpha, \beta$，再由 $\gamma = 1 - \alpha - \beta$ 得到第三个分量。

我们的 C++ 实现

InsideTriangle：叉积符号法

判断点是否在三角形内，还有一种更直接的方法：逐条边检查点在哪一侧。

对有向三角形 $ABC$，从 $A$ 到 $B$，再从 $B$ 到 $C$，再从 $C$ 到 $A$ 依次绕行。对于三角形内的任意点 $P$，向量 $\overrightarrow{AP}$、$\overrightarrow{BP}$、$\overrightarrow{CP}$ 分别与对应边向量的叉积 $z$ 分量，符号全部相同（全为正或全为负）。一旦有符号不同，点就在三角形外。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool TinyRender::InsideTriangle(math::Triangle3f& tri, int x, int y) const
{
    math::Point3f p(x, y, 1);
    math::Point3f a(tri[0]);
    math::Point3f b(tri[1]);
    math::Point3f c(tri[2]);

    auto pa = p - a;
    auto pb = p - b;
    auto pc = p - c;

    // 分别计算 PA×PB、PB×PC、PC×PA 的 z 分量
    auto z1 = math::CrossProduct(pa, pb).z;
    auto z2 = math::CrossProduct(pb, pc).z;
    auto z3 = math::CrossProduct(pc, pa).z;

    // 三个叉积同号，则点在三角形内
    return z1 * z2 > 0 && z2 * z3 > 0;
}

这里计算的是 $\overrightarrow{PA} \times \overrightarrow{PB}$（即以 $P$ 为原点的局部叉积），其 $z$ 分量反映了 $P$ 在有向边 $AB$ 的哪一侧。三个侧面方向一致，则 $P$ 在三角形内部。

ComputeBarycentric：矩阵求逆法

我们用矩阵求逆直接解方程组。按照上面推导的方程 $M \cdot (\alpha, \beta)^T = \vec{CP}$，代码构造系数矩阵并求其逆：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

std::tuple<float, float, float> TinyRender::ComputeBarycentric(math::Triangle3f& tri, int x, int y)
{
    // 计算向量 CA, CB, CP
    math::Vec2f CA(tri[0].x - tri[2].x, tri[0].y - tri[2].y);
    math::Vec2f CB(tri[1].x - tri[2].x, tri[1].y - tri[2].y);
    math::Vec2f CP(x - tri[2].x, y - tri[2].y);

    // 构造 2x2 矩阵（注意：内部以行向量方式存储 CA, CB）
    math::Matrix2f m(CA.x, CA.y, CB.x, CB.y);
    auto inv = m.Inverse();

    // 通过矩阵逆解出 α, β
    float u = CP.x * inv.a + CP.y * inv.c;  // α
    float v = CP.x * inv.b + CP.y * inv.d;  // β
    return { u, v, 1 - u - v };             // (α, β, γ)
}

这里有一个值得注意的小细节：矩阵以行优先（Row-major）的方式存储 $\vec{CA}$ 和 $\vec{CB}$，即 m 的布局是：

\[M = \begin{bmatrix} CA_x & CA_y \\ CB_x & CB_y \end{bmatrix}\]

这是列系数矩阵的转置。用这个矩阵的逆直接”点乘” $\vec{CP}$ 的分量（而非标准矩阵-向量乘），恰好等价于求解正确的方程组——本质上是用了 Cramer 法则，只是绕了一下代数弯路。可以验证结果与直接用 Cramer 法则展开完全一致：

\[\alpha = \frac{CP_x \cdot CB_y - CP_y \cdot CB_x}{CA_x \cdot CB_y - CA_y \cdot CB_x}, \quad \beta = \frac{CP_y \cdot CA_x - CP_x \cdot CA_y}{CA_x \cdot CB_y - CA_y \cdot CB_x}\]

分母 $CA_x \cdot CB_y - CA_y \cdot CB_x$ 正是 $\vec{CA} \times \vec{CB}$ 的 $z$ 分量，即三角形面积的两倍（带符号）。

DrawTriangle：包围盒遍历 + z-buffer

有了上面两个工具，填充三角形的核心函数就非常清晰了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

void TinyRender::DrawTriangle(math::Triangle3f& tri, int width, int height, math::Color&& color)
{
    // 1. 计算 AABB
    math::Vec2f bounding_min, bounding_max;
    bounding_min.x = std::min(tri[0].x, std::min(tri[1].x, tri[2].x));
    bounding_min.y = std::min(tri[0].y, std::min(tri[1].y, tri[2].y));
    bounding_max.x = std::max(tri[0].x, std::max(tri[1].x, tri[2].x));
    bounding_max.y = std::max(tri[0].y, std::max(tri[1].y, tri[2].y));

    // 2. 遍历包围盒内所有像素
    for (int x = std::floor(bounding_min.x); x <= std::ceil(bounding_max.x); x++)
    {
        for (int y = std::floor(bounding_min.y); y <= std::ceil(bounding_max.y); y++)
        {
            if (x >= width || y >= height || x < 0 || y < 0) continue;

            if (InsideTriangle(tri, x, y))
            {
                // 3. 插值深度，进行 z-buffer 测试
                auto [alpha, beta, gamma] = ComputeBarycentric(tri, x, y);
                auto inteZ = alpha * tri[0].z + beta * tri[1].z + gamma * tri[2].z;
                int offset = y * width + x;
                if (m_zBuffer[offset] < inteZ)
                {
                    m_zBuffer[offset] = inteZ;
                    offset *= 3;
                    m_frameBuffer[offset]     = color.r;
                    m_frameBuffer[offset + 1] = color.g;
                    m_frameBuffer[offset + 2] = color.b;
                }
            }
        }
    }
}

深度插值 inteZ 是利用重心坐标对三个顶点 $z$ 值的加权平均（正交投影下精确，透视投影下需要额外的透视校正，这留到后面讨论）。

z-buffer：解决深度排序

三角形光栅化解决了”如何填充一个三角形”，但还没有解决”多个三角形叠在一起时，谁应该挡住谁”的问题。

最朴素的做法是画家算法：先画远处的三角形，再画近处的，近处的自然覆盖远处的。但画家算法有一个致命缺陷——如果两个三角形互相穿插，就不存在一个全局有效的绘制顺序。

z-buffer（深度缓冲）彻底解决了这个问题，思路极为简单：为每个像素维护一个当前已渲染的最近深度值，每次尝试写入一个像素时，只有新片段更近时才覆盖。

具体来说，渲染开始时将 m_zBuffer 所有元素初始化为负无穷（最远）：

1
2

for (int i = 0; i < width * height; i++)
    m_zBuffer[i] = -std::numeric_limits<float>::infinity();

在 DrawTriangle 中，对包围盒内每个通过测试的像素，先用重心坐标插值出该像素的深度 inteZ，再与 m_zBuffer 中记录的已有深度比较：

1
2
3
4
5
6
7

auto inteZ = alpha * tri[0].z + beta * tri[1].z + gamma * tri[2].z;
int offset = y * width + x;
if (m_zBuffer[offset] < inteZ)   // 新片段更近
{
    m_zBuffer[offset] = inteZ;   // 更新深度
    // 写入 framebuffer...
}

这里 $z$ 值越大表示越靠近相机（我们使用右手坐标系，相机看向 $-z$ 方向，近处 $z$ 值较大）。整个算法的正确性不依赖于三角形的绘制顺序，每个像素都独立做出最优决策——这也是它天然适合并行化的原因。

z-buffer 的空间开销是一张与 framebuffer 同等分辨率的浮点数组。时间上，每个像素只需一次比较和一次写入，几乎没有额外负担。这就是为什么现代 GPU 将 z-buffer 作为标准硬件功能深度集成，而不是用软件实现。

背面剔除（Back-face Culling）

如果直接光栅化模型所有三角形，由于没有深度排序，”背面”的三角形会画在”正面”三角形之上，产生混乱的视觉结果。

一个快速但粗糙的解决方案是背面剔除：丢弃所有朝向摄像机背面的三角形。

tr 用一个简单的 1D 类比说明这一思路：对一个 2D 多边形边 $AB$，将其投影到屏幕 $x$ 轴，计算投影长度 $L_{AB} = B_x - A_x$。若 $L_{AB} < 0$，说明该边朝后，可以丢弃。

推广到 3D：对三角形三个顶点，计算其表面法向量，再与光照方向（或视线方向）做点积：

\[\vec{n} = (\vec{v_2} - \vec{v_0}) \times (\vec{v_1} - \vec{v_0})\] \[\text{intensity} = \vec{n} \cdot \vec{l}\]

若 intensity > 0，三角形面朝光源，可见且有光照；若 intensity ≤ 0，三角形背向光源，直接跳过：

1
2
3
4
5
6
7
8
9
10

// Cross product to get surface normal
math::Vec3f normal = ((v2 - v0) ^ (v1 - v0)).normalize();
auto intensity = normal * lightDir;

// 背面剔除：法向量与光照方向点积 <= 0 时跳过
if (intensity > 0)
{
    DrawTriangle(tri, width, height,
        math::Color(intensity * 255, intensity * 255, intensity * 255));
}

这里同时完成了两件事：

  1. 背面剔除：intensity > 0 的条件筛掉了背面三角形。
  2. 漫反射光照（Lambertian shading）：用 $\cos\theta$（即法向量与光方向的点积）调制颜色亮度，表面法向量越正对光源，颜色越亮。

需要注意，背面剔除并不能完全解决深度排序问题。tr 指出：正面三角形之间仍然可能发生互相遮挡（比如嘴巴内部的三角形画在嘴唇上面），彻底的解决方案是 z-buffer。我们的代码已经有了 m_zBuffer，在 DrawTriangle 中进行深度测试，能够正确处理正面三角形之间的遮挡关系。

小结

本文从两个方向讨论了三角形光栅化：

方法优点缺点
扫描线精细控制每行，效率高（CPU 单线程）代码复杂，串行，边界情况多
包围盒 + 重心坐标代码简洁，天然并行，易于扩展包围盒内有大量无效像素（细长三角形时浪费大）

我们的实现选择了第二种方案，并在此基础上加入了 z-buffer 和背面剔除，形成了一个能够渲染带纹理 3D 模型的基础软渲染器。

重心坐标是图形学中一个非常基础且重要的工具，不仅仅用于内外判断——它是任何属性（深度、纹理坐标、法向量、颜色……）在三角形内插值的通用机制。在后续讨论透视投影校正、纹理滤波、顶点着色等话题时，我们还会频繁用到它。

下一篇讨论如何移动相机，推导 MVP 变换中的 View 和 Projection 矩阵。

技术笔记
图形学 渲染 光栅化
本文由作者按照 CC BY 4.0 进行授权