布雷森漢姆直線算法

布雷森漢姆直線演算法一般指本詞條

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創建的。

相關詞條

熱門詞條

聯絡我們