Bresenham直线演算法

**布雷森漢姆直線演算法**（英語：Bresenham's line algorithm）是用來描繪由兩點所決定的直線的演算法，它會算出一條線段在 n 維點陣圖上最接近的點。這個演算法只會用到較為快速的整數加法、減法和位元移位，常用於繪製電腦畫面中的直線。是計算機圖形學中最先發展出來的演算法。

經過少量的延伸之後，原本用來畫直線的演算法也可用來畫圓。且同樣可用較簡單的算術運算來完成，避免了計算二次方程式或三角函數，或遞歸地分解為較簡單的步驟。

以上特性使其仍是一種重要的演算法，並且用在繪圖儀、繪圖卡中的繪圖晶片，以及各種圖形程式庫。這個演算法非常的精簡，使它被實作於各種裝置的韌體，以及繪圖晶片的硬體之中。

「Bresenham」至今仍經常作為一整個演算法家族的名稱，即使家族中絕大部份演算法的實際開發者是其他人。該家族的演算法繼承了 Bresenham 的基本方法並加以發展，詳見參考資料。

## 演算方法

假設我們需要由 (_x_0, _y_0) 這一點，繪畫一直線至右下角的另一點 (_x_1, _y_1)，x,y 分別代表其水平及垂直坐標，並且 _x_1 - _x_0 > _y_1 - _y_0。在此我們使用電腦系統常用的坐標系，即 x 坐標值沿 x 軸向右增長，y 坐標值沿 y 軸向下增長。

因此 x 及 y 之值分別向右及向下增加，而兩點之水平距離為 $x_{1}-x_{0}$ 且垂直距離為 $y_{1}-y_{0}$ 。由此得之，該線的斜率必定介乎於 0 至 1 之間。而此算法之目的，就是找出在 $x_{0}$ 與 $x_{1}$ 之間，第 x 行相對應的第 y 列，從而得出一像素點，使得該像素點的位置最接近原本的線。

對於由 (_x_0, _y_0) 及 (_x_1, _y_1) 兩點所組成之直線，公式如下：

　
: $y-y_{0}={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})$

因此，對於每一點的 x，其 y 的值是

　
: ${\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}$

因為 x 及 y 皆為整數，但並非每一點 x 所對應的 y 皆為整數，故此沒有必要去計算每一點 x 所對應之 y 值。反之由於此線之斜率介乎於 1 至 0 之間，故此我們只需要找出當 x 到達那一個數值時，會使 y 上升 1，若 x 尚未到此值，則 y 不變。至於如何找出相關的 x 值，則需依靠斜率。斜率之計算方法為 $m=(y_{1}-y_{0})/(x_{1}-x_{0})$ 。由於此值不變，故可於運算前預先計算，減少運算次數。

要實行此算法，我們需計算每一像素點與該線之間的誤差。於上述例子中，誤差應為每一點 x 中，其相對的像素點之 y 值與該線實際之 y 值的差距。每當 x 的值增加 1，誤差的值就會增加 m。每當誤差的值超出 0.5，線就會比較靠近下一個映像點，因此 y 的值便會加 1，且誤差減 1。

下列偽代碼是這算法的簡單表達（其中的 `plot(x,y)` 繪畫該點，`abs` 返回的是絕對值）。雖然用了代價較高的浮點運算，但很容易就可以改用整數運算（詳見最佳化一節）：

```
 **function** line(x0, x1, y0, y1)
     _int_ deltax := x1 - x0
     _int_ deltay := y1 - y0
     _real_ error := 0
     _real_ deltaerr := deltay / deltax    // 假設deltax != 0（非垂直線），
           // 注意：需保留除法運算結果的小數部份
     _int_ y := y0
     **for** x **from** x0 **to** x1
         plot(x,y)
         error := error + deltaerr
         **if** abs (error) ≥ 0.5 **then**
             y := y + 1
             error := error - 1.0
```

## 一般化

雖然以上的演算法只能繪畫由左下至右上，且斜率小於或等於 1 的直線，但我們可以擴展此演算法，使之可繪畫任何的直線。第一個擴展是繪畫反方向，即由右上至左下的直線。這可以簡單地透過在 `x0 > x1` 時交換起點和終點來做到。第二個擴展是繪畫斜率為負的直線。可以檢查 _y_0 ≥ _y_1 是否成立；若該不等式成立，誤差超出 0.5 時 _y_ 的值改為加 - 1。最後，我們還需要擴展該演算法，使之可以繪畫斜率絕對值大於 1 的直線。要做到這點，我們可以利用大斜率直線對直線 _y=x_ 的反射是一條小斜率直線的事實，在整個計算過程中交換 _x_ 和 _y_，並一併將 _plot_ 的參數順序交換。擴展後的偽代碼如下：

```
 **function** line(x0, x1, y0, y1)
     _boolean_ steep := abs(y1 - y0) > abs(x1 - x0)
     **if** steep **then**
         swap(x0, y0)
         swap(x1, y1)
     **if** x0 > x1 **then**
         swap(x0, x1)
         swap(y0, y1)
     _int_ deltax := x1 - x0
     _int_ deltay := abs(y1 - y0)
     _real_ error := 0
     _real_ deltaerr := deltay / deltax
     _int_ ystep
     _int_ y := y0
     **if** y0 < y1 **then** ystep := 1 **else** ystep := -1
     **for** x **from** x0 **to** x1
         **if** steep **then** plot(y,x) **else** plot(x,y)
         error := error + deltaerr
         **if** error ≥ 0.5 **then**
             y := y + ystep
             error := error - 1.0
```

以上的程序可以處理任何的直線，實現了完整的 Bresenham 直線演算法。

## 最佳化

以上的程序有一個問題：電腦處理浮點運算的速度比較慢，而 `error` 與 `deltaerr` 的計算是浮點運算。此外，`error` 的值經過多次浮點數加法之後，可能有累積誤差。使用整數運算可令演算法更快、更準確。只要將所有以上的分數數值乘以 `deltax`，我們就可以用整數來表示它們。唯一的問題是程序中的常數 0.5— 我們可以透過改變 `error` 的初始方法，以及將 `error` 的計算由遞增改為遞減來解決。新的程序如下：

```
 **function** line(x0, x1, y0, y1)
     _boolean_ steep := abs(y1 - y0) > abs(x1 - x0)
     **if** steep **then**
         swap(x0, y0)
         swap(x1, y1)
     **if** x0 > x1 **then**
         swap(x0, x1)
         swap(y0, y1)
     _int_ deltax := x1 - x0
     _int_ deltay := abs(y1 - y0)
     _int_ error := deltax / 2
     _int_ ystep
     _int_ y := y0
     **if** y0 < y1 **then** ystep := 1 **else** ystep := -1
     **for** x **from** x0 **to** x1
         **if** steep **then** plot(y,x) **else** plot(x,y)
         error := error - deltay
         **if** error < 0 **then**
             y := y + ystep
             error := error + deltax
```

## 歷史

Jack E. Bresenham 於 1962 年在 IBM 發明了此演算法。據他本人表示，他於 1963 年在丹佛舉行的美國計算機協會全國大會上發表了該演算法，論文則登載於 1965 年的《IBM 系統期刊》（IBM Systems Journal）之中。Bresenham 直線演算法其後被修改為能夠畫圓，修改後的演算法有時被稱為「Bresenham 畫圓演算法」或中點畫圓演算法。

## 參考資料

* "The Bresenham Line-Drawing Algorithm" （頁面存檔備份，存於網際網路檔案館）, by Colin Flanagan

## 參閱

* Patrick-Gilles Maillot's Thesis （頁面存檔備份，存於網際網路檔案館） an extension of the Bresenham line drawing algorithm to perform 3D hidden lines removal; also published in MICAD '87 proceedings on CAD/CAM and Computer Graphics, page 591 - ISBN 2-86601-084-1.
* 數字微分分析儀演算法，描畫直線和三角形的一種簡單通用方法。
* 吳小林直線演算法，以同樣快速的方法繪製反鋸齒線。
* 中點畫圓演算法，以類似的方法繪畫圓。

## 外部連結

* Analyze Bresenham's line algorithm in an online Javascript IDE （頁面存檔備份，存於網際網路檔案館）
* _The Bresenham Line-Drawing Algorithm_ by Colin Flanagan （頁面存檔備份，存於網際網路檔案館）
* National Institute of Standards and Technology page on Bresenham's algorithm （頁面存檔備份，存於網際網路檔案館）
* Calcomp 563 Incremental Plotter Information （頁面存檔備份，存於網際網路檔案館）
* Bresenham's Original Paper （頁面存檔備份，存於網際網路檔案館）
* An implementation in Java （頁面存檔備份，存於網際網路檔案館） at the Code Codex