Bresenham直線演算法

维基百科，自由的百科全书

此條目仍有文字未被翻譯成中文，條目是根據其他語言維基百科的內容進行翻譯的。（2008年5月15日）
歡迎您协助翻译与校对以改善这篇條目。
长期闲置的非中文内容可能会被移除。

Bresenham直線演算法是用來描繪由兩點所決定的直線的演算法，它會算出一條線段在 n 維光柵上最接近的點。這個演算法只會用到較為快速的整數加法、減法和位元移位，常用於繪製電腦畫面中的直線。是計算機圖形學中最先發展出來的演算法。

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

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

「Bresenham」至今仍經常作為整個演算法家族的名稱，即使實際的開發者是其他人。其後尚有接替 Bresenham 的類似方法，詳見參考資料。

[编辑] 演算方法

Bresenham直線演算法描繪的直線。

假設我們需要由 (x₀, y₀) 這一點,繪畫一直線至右下角的另一點(x₁, y₁), x,y分別代表其水平(horizontal)及垂直(vertical)座標.(這是一般電腦常用之設定.)

因此x及y之值分別向下及向右增加.而兩點之水平距離分別為 $x 1 - x 0$ 及y₁-y₀.由此得之,該線的斜率(slope)必定介附於 $- 1$ 至0之間.而此算法之目的,就是找出在 $x 0$ 與 $x 1$ 之間,第x行相對應的第y列,從而得出一映像點(pixel),而此點必須是最接近原本的線.

對於由(x₀, y₀)及(x₁, y₁)兩點所組成之直線,公式如下: $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)$ .由於此值不變,故可於運算前預先計算,減少運算次數.

要實行此算法,我們需計算每一映像點與該線之間的誤差(error).於上述例子中,誤差應為每一點x中,其相對的映像點之y值與該線實際之y值的差距.每當x的值增加1,誤差的值就會增加m.每當誤差的值超出某一限額(如0.5),線就會比較靠近下一個映像點,因此y的值便會加1.反之若誤差少於0.5,y則減1.

下列偽代碼是這算法的簡單表達(其中的plot(x,y)繪畫該點,及abs返回的是絕對值).雖然用了較昂貴的浮点运算,但很容易就可以改用整數運算(詳見最佳化):

 function line(x0, x1, y0, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(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 error ≥ 0.5 then
             y := y + 1
             error := error - 1.0

[编辑] 一般化

This first version only handles lines that descend to the right. We would of course like to be able to draw all lines. The first case is allowing us to draw lines that still slope downwards but head in the opposite direction. This is a simple matter of swapping the initial points if x0 > x1. Trickier is determining how to draw lines that go up. To do this, we check if y₀ ≥ y₁; if so, we step y by -1 instead of 1. Lastly, We still need to generalize the algorithm to drawing lines in all directions. Up until now we have only been able to draw lines with a slope less than one. To be able to draw lines with a steeper slope, we take advantage of the fact that a steep line can be reflected across the line y=x to obtain a line with a small slope. The effect is to switch the x and y variables throughout, including switching the parameters to plot. The code looks like this:

 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

The function now handles all lines and implements the complete Bresenham's algorithm.

[编辑] 最佳化

The problem with this approach is that computers operate relatively slowly on fractional numbers like error and deltaerr; moreover, errors can accumulate over many floating-point additions. Working with integers will be both faster and more accurate. The trick we use is to multiply all the fractional numbers above by deltax, which enables us to express them as integers. The only problem remaining is the constant 0.5—to deal with this, we change the initialization of the variable error. The new program looks like this:

 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

[编辑] 其它的演算方式

Image:BresenhamLine2.png

Principle of the Bresenham line algorithm, the lower part showing the error term

A different approach to the Bresenham algorithm works more from the practical side. It was published by Pitteway ^[1] and confirmed by van Aken ^[2]. Again we first consider a line in the first octant, which means a slope between 0 and 1. Mathematically spoken, we want to draw a line from point (x₁,y₁) to (x₂,y₂). The intervals in the two directions are dx=x₂-x₁ and dy=y₂-y₁, and the slope is dy/dx. The line equation can be written as y=y₁+(x-x₁)*dy/dx. In this first octant, we have 0<dy<=dx.

So, when working pixel-wise along this line, we have one "fast" direction, the positive x direction, and a "slow" direction, the positive y direction, where fewer steps have to be done than in the fast one. So the algorithm simply goes like this: a) Always do a single pixel step in the fast direction. b) Every now and then also do a step in the slow direction.

Bresenham's trick is the introduction of an error term, which deals with the decision, when to do also this extra step in the slow direction. The line equation is transformed into 0=dx*(y-y₁)-dy*(x-x₁), and then the null on the left side is replaced by the error term. A step by 1 in the x direction (variable x) causes a decrement of the error term by one times dy. If the error term gets below zero due to this, it will be increased by one times dx through a step by 1 in the y direction (variable y). Because of dx>=dy, this will render the error term positive again in any case, at least brought back to zero.

You realize a cross-wise subtraction of dy from the error term for any x step and an addition of dx for any y step. This way, the division dy/dx for the slope is dissolved into a number of more elementar operations.

A critical issue is the initialisation of the error term. In this approach here, we simply consider a line with dy=1, so with only one single step in the y direction along the whole line. Of course for the best look of the line, we want this step to happen right in the middle of the line. This leads to initialising the error term to dx/2. (Rounding this term to integers in case of odd dx is no problem.)

This approach comes out a little different from the original, as it avoids the additional factor of 2 on both sides, which has to do with the initialisation.

To generalize this algorithm for all octants, you will again have to do role changes of x and y and consider the different signs of dx and dy.

A simple implementation of this approach is not very elegant, but demonstrates the principle of the algorithm fairly well.

REM Bresenham algorithm for a line in the first octant in Pseudo Basic
dx = xend-xstart
dy = yend-ystart
REM in first octant, we have 0 < dy <= dx

REM Initialisations
x = xstart
y = ystart
SETPIXEL x,y
error = dx/2 

REM Pixel loop: always do a step in fast direction, every now and then also one in the slow direction
WHILE x < xend
   REM Step in fast direction
   x = x + 1
   error = error-dy
   IF error < 0 THEN
      REM Step in slow direction
      y = y + 1
      error = error + dx
      END IF
   SETPIXEL x,y
   WEND

[编辑] 畫圓版本

Image:Bresenham circle3.png

Rasterisation of a circle by the Bresenham algorithm

The approach for the Circle Variant shown here is also not originally from Bresenham, see again references to Pitteway and van Aken below. The algorithm starts accordingly with the circle equation x²+y²=r². Again we consider first only the first octant. Here you want to draw a curve which starts at point (r,0) and then proceeds to the top left, up to reaching the angle of 45°.

The "fast" direction here is the y direction. You always do a step in the positive y direction (upwards), and every now and then you also have to do a step in the "slow" direction, the negative x direction.

The frequent computations of squares in the circle equation, trigonometric expressions or square roots can again be avoided by dissolving everything into single steps and recursive computation of the quadratic terms from the preceding ones.

From the circle equation you get to the transformed equation 0=x²+y²-r² with r² to be computed only a single time during initialisation, x²=(xpreceding-1)²=xpreceding²-2*xpreceding+1 (according for y), where x² (or xpreceding²) is kept as an own variable. Additionally you need to add the mid point coordinates when setting a pixel. These frequent integer additions do not limit the performance much, as you spare those square (root) computations in the inner loop in turn. Again the zero in the transformed circle equation is replaced by the error term.

The initialization of the error term is derived from an offset of ½ pixel at the start. Until the intersection with the perpendicular line, this leads to an accumulated value of r in the error term, so that this value is used for initialisation.

The following implementation is shown here only for the first octant, and again the other octants need sign changes for x and/or y and the swapping of x and y. An easy expansion for full circles, as it is possible for graphics displays, but not for plotters, is added in the comments.

REM Bresenham Algorithm for one eighth of a circle in Pseudo-Basic
REM given: r, xmid, ymid
REM initialisations for the first octant
r2 = r*r : REM single multiplication
x = r
y = 0
error = r
SETPIXEL xmid + x, ymid + y

REM Pixel loop: always a step in fast direction, every now and then also in slow one
WHILE y <= x
   REM step in fast direction (positive y direction)
   dy = y*2+1 : REM in Assembler implementation *2 per Shift
   y = y+1
   error = error-dy
   IF error<0 THEN
      REM step in slow direction (here the negative x direction)
      dx = 1-x*2 : REM in Assembler implementation *2 per Shift
      x = x-1
      error = error-dx
      END IF
   SETPIXEL  xmid+x, ymid+y
   REM If this deals with a screen and not a mechanical plotter,
   REM you can cover simultaneously also the other octants:
   REM SETPIXEL xmid-x, ymid+y
   REM SETPIXEL xmid-x, ymid-y
   REM SETPIXEL xmid+x, ymid-y
   REM SETPIXEL xmid+y, ymid+x
   REM SETPIXEL xmid-y, ymid+x
   REM SETPIXEL xmid-y, ymid-x
   REM SETPIXEL xmid+y, ymid-x
   WEND

A possible implementation of the Bresenham Algorithm for a full circle in C. Here another variable for recursive computation of the quadratic terms is used, which corresponds with the term 2*n+1 above. It just has to be increased by 2 from one step to the next:

 void rasterCircle(int x0, int y0, int radius)
 {
   int f = 1 - radius;
   int ddF_x = 0;
   int ddF_y = -2 * radius;
   int x = 0;
   int y = radius;
 
   setPixel(x0, y0 + radius);
   setPixel(x0, y0 - radius);
   setPixel(x0 + radius, y0);
   setPixel(x0 - radius, y0);
 
   while(x < y) 
   {
     if(f >= 0) 
     {
       y--;
       ddF_y += 2;
       f += ddF_y;
     }
     x++;
     ddF_x += 2;
     f += ddF_x + 1;    
     setPixel(x0 + x, y0 + y);
     setPixel(x0 - x, y0 + y);
     setPixel(x0 + x, y0 - y);
     setPixel(x0 - x, y0 - y);
     setPixel(x0 + y, y0 + x);
     setPixel(x0 - y, y0 + x);
     setPixel(x0 + y, y0 - x);
     setPixel(x0 - y, y0 - x);
   }
 }

[编辑] 繪製弧線

The implementations above always only draw complete octants or circles. If you want to draw only a certain arc from an angle α to an angle β, you have to implement it in a way to first calculate the x and y coordinates of these end points, where you inevitably have to resort to trigonometric or square root computations (see Methods of computing square roots). Then you run the Bresenham algorithm over the complete octant or circle and set the pixels only if they fall into the wanted interval. After finishing this arc, you can abort the algorithm prematurely.

[编辑] 橢圓

By scaling the drawn x and y values (and horizontal or vertical line expansion, respectively) you can produce even ellipses parallel to the x or y axis. For this, you use the circle algorithm with the smaller ellipse axis as radius and add a value in the other direction, which again is computed through another Bresenham line algorithm increasing from the pole to the equator. As the ellipse has to be elongated into the longer axis direction, you don't set single pixels anymore, but have to draw lines (though simple ones, only horizontal or vertical) from the previous to the next point.

A general ellipse can be derived from such an axis-parallel one by application of a shearing operation on it. Again you use an additional Bresenham line algorithm to compute the offset increasing in one of the axis directions and to let it contribute to every drawn coordinate.

[编辑] 歷史

The algorithm was developed by Jack E. Bresenham in 1962 at IBM. In 2001 Bresenham wrote:

"I was working in the computation lab at IBM's San Jose development lab. A Calcomp plotter had been attached to an IBM 1401 via the 1407 typewriter console. [The algorithm] was in production use by summer 1962, possibly a month or so earlier. Programs in those days were freely exchanged among corporations so Calcomp (Jim Newland and Calvin Hefte) had copies. When I returned to Stanford in Fall 1962, I put a copy in the Stanford comp center library.

A description of the line drawing routine was accepted for presentation at the 1963 ACM national convention in Denver, Colorado. It was a year in which no proceedings were published, only the agenda of speakers and topics in an issue of Communications of the ACM. A person from the IBM Systems Journal asked me after I made my presentation if they could publish the paper. I happily agreed, and they printed it in 1965."

Bresenham later modified his algorithm to produce circles.

[编辑] 參考資料

"The Bresenham Line-Drawing Algorithm", by Colin Flanagan

Bresenham also published a Run-Slice (as opposed to the Run-Length) computational algorithm.

^ Pitteway, M.L.V., "Algorithm for Drawing Ellipses or Hyperbolae with a Digital Plotter", Computer J., 10(3) November 1967, pp 282-289
^ Van Aken, J.R., "An Efficient Ellipse Drawing Algorithm", CG&A, 4(9), September 1984, pp 24-35

[编辑] 參閱

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.
吳小林直線演算法，以同樣快速的方法繪製反鋸齒線。

[编辑] 外部連結

分类: 幾何學演算法 | 算法 | 數位幾何學

2个隐藏分类: 自2008年5月正在翻譯的條目 | 正在翻譯的條目

See also ebooksgratis.com: no banners, no cookies, totally FREE.