光栅化之 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

歡迎關注個人公衆号，實時推送最新博文！