光栅化之 Bresenham 算法

布雷森汉姆直线算法（英语： Bresenham’s line algorithm）是用来描绘由两点所决定的直线的算法，它会算出一条线段在 n 维位图上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。由 Jack E. Bresenham 于 1962 年在 IBM 发明了此算法，因此得名。

假定已知直线方程为

在绘制时依次递增 x，在（x，y）处绘制了点之后，该直线在其放置位置方面的选择范围就非常有限在接下来需要绘制的一点：

它可以绘制点（x + 1，y）

它可以绘制点（x + 1，y + 1）

由于 m 是实数，在从 x 到 x + 1 的移动中，y 增加 m，此时 y 不一定为整数，并没有与像素一一对应，新值（y + e + m）与 y 之差小于 0.5 ，我们将选择绘制（x + 1，y）否则（x + 1，y + 1）

根据上面两种不同情况更新 e 的值

因此可得 Bresenham 绘制的伪代码如下

// Bresenham 伪代码
e = 0, y = y1
For x = x1 to x2 do
    Plot point at (x, y)
    If (e + m < 0.5)
        e = e + m
    Else
        y = y + 1, e = e + m - 1
    EndIf
EndFor
           

这仍然采用浮点值。但是，请考虑一下，如果我们在检测条件的两边乘以 Δx 然后再乘以 2，并令 e’ = eΔx，可得

同上更新 e 的值的方式可转换为

因此可得 Bresenham 改进版绘制的伪代码如下

// Bresenham 改进版伪代码
e' = 0, y = y1
For x = x1 to x2 do
    Plot point at (x, y)
    If (2(e' + Δy) < Δx)
        e' = e' + Δy
    Else
        y = y + 1, e' = e' + Δy - Δx
    EndIf
EndFor
           

这里将 DDA 中计算 y 值每次进行一次浮点计算优化为每次计算一次整数加法和一个符号判断，该算法的效率非常高，以至于它已经被固化为图形芯片中的一条指令。

参考链接：

[1] The Bresenham Line-Drawing Algorithm https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

[2] Bresenham’s line algorithm https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

欢迎关注个人公众号，实时推送最新博文！