Bresenham的直線算法是一種算法，它確定應該選擇的n維光柵的點，以便形成兩點之間的直線的近似近似。 它通常用於在點陣圖圖像中（例如在計算機螢幕上）繪製線基元，因為它僅使用整數加法，減法和位移，所有這些都是標準計算機體系結構中非常便宜的操作。 它是一種增量錯誤算法。 它是計算機圖形學領域最早開發的算法之一。 原始算法的擴展可用於繪製圓圈。
基本介紹
- 中文名：布雷森漢姆直線算法
- 外文名：Bresenham's line algorithm
歷史,代碼案例,類似的算法,
歷史
Bresenham的線算法以Jack Elton Bresenham命名，他於1962年在IBM開發。 2001年Bresenham寫道：
我在IBM的聖何塞開發實驗室的計算實驗室工作。 Calcomp繪圖儀已通過1407打字機控制台連線到IBM 1401。 在1962年夏天投入生產，可能提前一個月左右。當時的節目在公司之間自由交換，因此Calcomp（Jim Newland和Calvin Hefte）有副本。當我在1962年秋季回到斯坦福時，我在史丹福大學中心圖書館裡放了一份副本。 1963年在科羅拉多州丹佛舉行的ACM全國大會上接受了線描例程的描述。這一年沒有出版任何會議記錄，只有發言人的議程和ACM通訊問題的議題。一位來自IBM Systems Journal的人在我發表演講後問我是否可以發表論文。我很高興地同意了，他們在1965年將它列印出來。
Bresenham的算法後來被擴展為產生圓，所得到的算法有時被稱為Bresenham的圓算法或中點圓算法。
代碼案例
通過檢查y是否需要增加或減少（即dy <0），可以擴展算法以覆蓋0和-1之間的梯度。
plotLineLow(x0,y0, x1,y1) dx = x1 - x0 dy = y1 - y0 yi = 1 if dy < 0 yi = -1 dy = -dy end if D = 2*dy - dx y = y0 for x from x0 to x1 plot(x,y) if D > 0 y = y + yi D = D - 2*dx end if D = D + 2*dy
通過切換x和y軸，可以寫出正或負陡梯度的實現：
plotLineHigh(x0,y0, x1,y1) dx = x1 - x0 dy = y1 - y0 xi = 1 if dx < 0 xi = -1 dx = -dx end if D = 2*dx - dy x = x0 for y from y0 to y1 plot(x,y) if D > 0 x = x + xi D = D - 2*dy end if D = D + 2*dx
類似的算法
Bresenham算法可以解釋為略微修改的數字微分分析儀（使用0.5作為誤差閾值而不是0，這是非重疊多邊形光柵化所必需的）。
使用增量錯誤代替除法運算的原理在圖形中有其他套用。 可以使用此技術在紋理映射多邊形的光柵掃描期間計算U，V坐標。 在一些PC遊戲中看到的體素高度圖軟體渲染引擎也使用了這個原理。
Bresenham還發布了Run-Slice（而不是Run-Length）計算算法。
處理粗線的算法的擴展是由Alan Murphy在IBM創建的。
