TinyRenderer（一）：Bresenham画线算法

在光栅化渲染器中，线段是构成更复杂图元（如三角形、边界与轮廓）的基础。将连续几何映射到离散像素网格，首要问题就是：如何在像素栅格上画出一条尽可能贴近真实直线的离散线条。tinyrenderer（tr）正是从“画线”切入，通过迭代一个简单的画线器，逐步讲清楚栅格化的核心思想。

本文以 Bresenham 画线算法为主线，并与更直观的 DDA（Digital Differential Analyzer）方法对比，看看从浮点斜率插值到整数决策的转变，如何让软渲染器获得更好的稳定性与性能。

DDA

DDA（Digital Differential Analyzer）是一种利用直线的微分方程来生成直线的算法。其核心在于把“绘制一条直线”的任务拆解为“每走一步，计算一下坐标变化”的过程。

tr 给了一个比较完整的画线算法的迭代过程。实际上 tr 一开始的实现更接近 DDA 算法：利用直线的斜率方程 $y = kx + b$，在主位移方向（例如 $x$ 方向）每步进 $1$ 个单位，另一个方向（$y$ 方向）就增加斜率 $k$ 的增量，从而插值出两点间的中间点。

核心思想：

1. 确定主位移方向：比较 $\lvert \Delta x \rvert$ 和 $\lvert \Delta y \rvert$，谁更长就以谁为步进基准（one step）。
2. 计算增量：每次主方向增加 1，次方向增加 $\frac{\Delta y}{\Delta x}$（或 $\frac{\Delta x}{\Delta y}$）。
3. 循环累加：浮点坐标累加，最后四舍五入取整得到像素坐标。

def dda(x1, y1, x2, y2):
    # 计算增量
    dx = x2 - x1
    dy = y2 - y1
    
    # 步长
    steps = max(abs(dx), abs(dy))
    
    # 计算每步的增量
    x_increment = dx / steps
    y_increment = dy / steps
    
    x = x1
    y = y1
    for _ in range(int(steps)):
        print(f"({round(x)}, {round(y)})")  # 绘制当前像素
        x += x_increment
        y += y_increment
    print(f"({round(x)}, {round(y)})")  # 最后一个像素点

# 示例：绘制从 (0, 0) 到 (7, 5) 的直线
dda(0, 0, 7, 5)

Bresenham

虽然 DDA 很直观，但它依赖浮点运算（加法和取整）。在古早的硬件或嵌入式设备上，浮点运算又慢又耗电。Bresenham 算法通过精妙的数学变换，把整个计算过程限制在纯整数加减法的范畴内。

1. 核心推导：从浮点误差到整数决策

我们换个角度，从“累积误差”来理解，这样更能对应代码的实现逻辑。

1. 浮点数直觉（DDA的变体）： 对于斜率 $k = \Delta y / \Delta x$ 的直线，每当 $x$ 移动一步，$y$ 的真实坐标就会增加 $k$。 我们将当前 $y$ 的小数部分称为“误差” error。
   • 每走一步 $x$，累计误差：error += k。
   • 当 error > 0.5 时，说明真实直线已经更接近下一个 $y$ 像素了。此时我们将 $y$ 坐标加 1，并将 error 减去 1.0（重新归零计算下一段）。

2. 整数化魔法： 上述逻辑依然包含除法（$k = \Delta y / \Delta x$）和小数比较（$0.5$）。为了消除它们，我们将整个推导过程的所有数值乘以 $2\Delta x$：

   • 增量 $k$ 变为 $\frac{\Delta y}{\Delta x} \times 2\Delta x = 2\Delta y$。
   • 阈值 $0.5$ 变为 $0.5 \times 2\Delta x = \Delta x$。
   • 减量 $1.0$ 变为 $1.0 \times 2\Delta x = 2\Delta x$。

   最终的整数算法逻辑： 我们维护一个整数变量 err（等价于 error * 2 * dx）：

   • 初始 err = 0。
   • 每步 x 前进，执行 err += 2 * dy。
   • 一旦 err > dx，说明误差积累超过了半个像素：
     • y 步进 1。
     • err -= 2 * dx。

   这正是你在后续 C++ 代码中看到的 err += 2 * std::abs(y1 - y0) 和 if (err > (x1 - x0)) 的来源。

2. 通用化实现

上述推导仅适用于 $x$ 变化大于 $y$ 的情况（缓坡）。对于陡峭的直线（$\lvert \Delta y \rvert > \lvert \Delta x \rvert$），直接步进 $x$ 会导致线条断裂（因为 $y$ 可能会一次跳变多个像素）。

处理技巧（Unified Approach）： 如果直线陡峭，我们交换 $x$ 和 $y$ 的坐标，将其“镜像”为缓坡直线进行计算，但在绘制时再交换回来。这种归一化的思想极大地简化了代码分支。

def bresenham(x1, y1, x2, y2):
    # 1. 陡峭处理：如果 y 变化更大，交换 x,y 以保证以长轴为驱动
    steep = False
    if abs(x2 - x1) < abs(y2 - y1):
        x1, y1 = y1, x1
        x2, y2 = y2, x2
        steep = True

    # 2. 方向处理：确保从左向右画 (x1 < x2)，便于循环
    if x1 > x2:
        x1, x2 = x2, x1
        y1, y2 = y2, y1

    dx = x2 - x1
    dy = abs(y2 - y1)
    
    # 这里的 err 对应推导中的 P/2，逻辑是一样的
    # err 从 dx/2 开始减，相当于 P 从 2dy - dx 开始
    err = dx // 2  
    ystep = 1 if y1 < y2 else -1
    
    y = y1
    for x in range(x1, x2 + 1):
        # 3. 绘制：如果是 steep 模式，由于之前交换了 xy，这里要反过来画
        if steep:
            print(f"({y}, {x})")
        else:
            print(f"({x}, {y})")
            
        err -= dy
        if err < 0:
            y += ystep
            err += dx

# 示例：绘制从 (0, 0) 到 (7, 5) 的直线
bresenham(0, 0, 7, 5)

tr 的这篇文章给出了非常直觉化的DDA到Bresenham的代码优化过程，建议仔细阅读代码与解释，感受其中的巧妙。

3. 为什么说 Bresenham 没有“飘移”？

你可能会问：DDA 算法中 $x, y$ 每次增加一个浮点斜率，哪怕用 float，加个几千次，精度误差不就大到像素偏离了吗？

是的，DDA 会产生累积误差（Drift）。 例如斜率是 $1/3$，在计算机里可能是 $0.333333…$。累加多次后，$y$ 的值可能会因为精度丢失而偏离理论直线的 $y$ 值，导致最终画出的线“歪”了或者漏掉像素。

但 Bresenham 绝对精确。 注意看代码中的变量 dx, dy, err，它们全部是整数。

• dx, dy 来自像素坐标差，天生是整数。
• err 的初始化、加法、减法，全都是整数运算。

整数运算在计算机中是精确的（只要不溢出）。这意味着，无论直线多长，Bresenham 算法计算出的每一步决策，都严格对应直线方程 $Ax + By + C = 0$ 的符号判断。它不是“近似”画线，而是“精确地”寻找离数学直线最近的那个格点。永远不会因为线太长而画歪。

我们的C++实现

在理解了 Bresenham 的核心逻辑后，我们可以把它应用到高性能的 C++ 渲染器中。这里的实现做了几个关键的工程化处理：

1. 统一坐标系：通过 steep 标志位和 swap 操作，把 8 个象限的画线问题统一归约为“第一象限且斜率小于 1”或类似的标准情况。这极大地简化了代码分支。
2. 去除浮点数：完全使用整型（int）进行坐标和误差计算，确保效率。
3. 紧凑的循环体：将误差更新和坐标步进的逻辑压缩在几行代码内。

void TinyRender::DrawLine(math::Point2i& p0, math::Point2i& p1, int width, int height, math::Color&& color)
{
    auto x0 = p0.x, y0 = p0.y;
    auto x1 = p1.x, y1 = p1.y;
    
    // 检查直线是否过于陡峭（高度变化大于宽度变化）
    // 如果是，则交换 x 和 y 坐标，使其在 x 轴上变化平缓
    // 这样我们只需要统一处理 |slope| < 1 的情况
    bool steep = false;
    if (std::abs(x0 - x1) < std::abs(y0 - y1))
    {
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    
    // 确保从左往右绘制（x0 < x1）
    if (x0 > x1)
    {
        std::swap(x0, x1);
        std::swap(y0, y1);
    }

    int y = y0;
    int err = 0; // 累计误差值，初始化为0

    // 沿 x 轴步进
    for (int x = x0; x < x1; x++)
    {
        // 绘制像素
        // 如果之前交换了 x/y（steep 为 true），说明我们实际上是在沿 y 轴画线，
        // 所以写入 buffer 时需要把 x 作为纵坐标，y 作为横坐标
        if (steep)
        {
            int offset = (x * width + y) * 3;
            if (offset < width * height * 3) {
                m_frameBuffer[offset] = color.r;
                m_frameBuffer[offset + 1] = color.g;
                m_frameBuffer[offset + 2] = color.b;
            }
        }
        else
        {
            int offset = (y * width + x) * 3;
            if (offset < width * height * 3) {
                m_frameBuffer[offset] = color.r;
                m_frameBuffer[offset + 1] = color.g;
                m_frameBuffer[offset + 2] = color.b;
            }
        }
        
        // 更新误差项
        // err 增加 dy 的两倍（对应 P += 2*dy）
        err += 2 * std::abs(y1 - y0);
        
        // 如果累积误差超过了 dx（对应 P > 0）
        // 则在 y 方向步进 1，并修正误差 err
        if (err > (x1 - x0)) {
            y += (y1 > y0 ? 1 : -1);
            err -= 2 * (x1 - x0);
        }
    }
}