编写光栅化渲染器（三）绘制直线

# DDA Line

DDA(Digital Differential Analyzer) 正如其名，就是最直观的直线画法，原始的算法的描述如下：

假设存在屏幕空间上的两个点 $(x1, y1)$ 和 $(x2, y2)$

计算 $dx=x2-x1$，$dy=y2-y1$。
计算斜率 $k=\frac{dy}{dx}$。
x 从 x1 出发，每次向 x2 移动一个单位，计算 $y=y1+k(x–x1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void DDA(int x0, int y0, int x1, int y1)
{
    // 计算 dx & dy & k
    int dx = x1 - x0;
    int dy = y1 - y0;
    float k = dy / dx;

    // 循环绘制每一个像素
    for (int x = x1; x <= x2; x++) {
        putpixel(x, round(y1 + k * (x - x1)), RED);
    }
}

原始算法看起来很可靠，但是仍然有一些可以优化的地方，因为直线是线性且均匀的，所以假如提前计算好了每一次循环的增量，就可以避免 y1 + k * (x - x1) 中的浮点数乘法。

优化过后的 DDA 算法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void DDA(int x0, int y0, int x1, int y1)
{
    // 计算 dx & dy 
    int dx = x1 - x0;
    int dy = y1 - y0;

    // 计算需要计算多少步像素
    int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

    // 计算 x & y 每一步的增量
    float xinc = dx / (float)steps;
    float yinc = dy / (float)steps;

    // 循环绘制每一个像素
    float x = x0;
    float y = y0;
    for (int i = 0; i <= steps; i++) {
        putpixel(round(x), round(y), RED);
        x += xinc;
        y += yinc;
    }
}

# Bresenham’s Line

从上面 DDA 的优化案例可以看出，避免浮点数操作就是优化画线算法的关键。

Bresenham's Line 相比 DDA 不仅有更少的浮点数运算，而且没有浮点数和整数的类型转换。

算法的核心思想如下：

Bresenham’s Line

在 $(x_k, y_k)$ 的位置时候，可能走向 $(x_k+1, y_k)$ 也可能走向 $(x_k+1, y_k+1)$，显然，斜线的交点更加靠近谁，就往哪个方向走。

斜率:

$$ k = \frac{\Delta y}{\Delta x} $$

对于每一次循环，执行：

$$ x_{i+1} = x_i + 1\ e_{i+1} = e_i + k\ $$

同时，始终保证 $0 < e < 1$：

$$ e_{i+1} = e_{i+1} - 1, e_{i+1} > 1 $$

最后，得出这个点的 y：

$$ y_{i+1} = \begin{cases} y_i+1 &\text{if } e_{i+1} \gt 0.5\cr y_i &\text{if } e_{i+1} \le 0.5\cr \end{cases} $$

上面的算法是 Bresenham's Line 的基本思想，还需要进一步优化，减少浮点数运算。

可能产生浮点数的地方是 $k = \frac{\Delta y}{\Delta x}$ 和 $e_{i+1} \gt 0.5$，所以我们最后再把上面所有的过程乘以 $2\Delta x$。

最终，我们的代码如下，其中 $\Delta x = x_2 - x_1, \Delta y = y_2 - y_1$：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void bresenham(int x1, int y1, int x2, int y2)
{
    int m = 2 * (y2 - y1);
    int slope_error = m - (x2 - x1);
    for (int x = x1, y = y1; x <= x2; x++) {
        putpixel(x, y, RED);

        slope_error += m;

        if (slope_error >= 0) {
            y++; 
            slope_error -= 2 * (x2 - x1); 
        }
    }
}

最后的代码虽然看起来简洁，但是因为优化过，第一次接触容易摸不着头脑。

# 其他算法

还有一种叫 Mid-Point Line ，因为它即没有 DDA 简单直接，也没有 Bresenham 效率高，这里就不介绍了。