1、第3章 直線和圓弧的生成算法3.1 直線圖形的生成算法     數學上的直線是沒有寬度、由無數個點構成的集合，顯然，光柵顯示器只能近地似顯示直線。當我們對直線進行光柵化時，需要在顯示器有限個像素中，確定最佳逼近該直線的一組像素，并且按掃描線順序，對這些像素進行寫操作，這個過程稱為用顯示器繪制直線或直線的掃描轉換。    由于在一個圖形中，可能包含成千上萬條直線，所以要求繪制算法應盡可能地快。本節我們介紹一個像素寬直線繪制的三個常用算法：數值微分法（DDA）、中點畫線法和Bresenham算法。3.1.1逐點比較法3

2、.1.2數值微分(DDA)法設過端點P0(x0 ,y0)、P1(x1 ,y1)的直線段為L(P0 ,P1)，則直線段L的斜率 L的起點P0的橫坐標x0向L的終點P1的橫坐標x1步進，取步長=1(個像素)，用L的直線方程y=kx+b計算相應的y坐標，并取像素點(x,round(y)作為當前點的坐標。因為：    yi+1 = kxi+1+b         = k1xi+b+kDx  &#

3、160;      = yi+kDx  所以，當Dx =1; yi+1 = yi+k。也就是說，當x每遞增1，y遞增k(即直線斜率)。根據這個原理，我們可以寫出DDA（Digital Differential Analyzer）畫線算法程序。 DDA畫線算法程序：void DDALine(int x0,int y0,int x1,int y1,int color) int x；  float dx, dy, y, k；  dx = x1-x0； dy=y1-y0；&

4、#160; k=dy/dx,；y=y0；  for (x=x0；x< x1；x+)  drawpixel (x, int(y+0.5), color);       y=y+k;  注意：我們這里用整型變量color表示像素的顏色和灰度。  舉例：用DDA方法掃描轉換連接兩點P0（0,0）和P1（5,2）的直線段。xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5圖3.1.1 直線段的掃描轉換    

5、注意：上述分析的算法僅適用于|k| 1的情形。在這種情況下，x每增加1,y最多增加1。當 |k| > 1時，必須把x，y地位互換，y每增加1，x相應增加1/k。在這個算法中，y與k必須用浮點數表示，而且每一步都要對y進行四舍五入后取整，這使得它不利于硬件實現。動畫演示：數值微分畫線算法（DDA） 3.1.3中點畫線法    假定直線斜率k在01之間，當前像素點為（xp,yp），則下一個像素點有兩種可選擇點P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點（xp+1,yp+0.5）

6、稱為M，Q為理想直線與x=xp+1垂線的交點。當M在Q的下方時，則取P2應為下一個像素點；當M在Q的上方時，則取P1為下一個像素點。這就是中點畫線法的基本原理。  圖3.1.2 中點畫線法每步迭代涉及的像素和中點示意圖     下面討論中點畫線法的實現。過點(x0,y0)、(x1, y1)的直線段L的方程式為F(x, y)=ax+by+c=0，其中，a=y0-y1, b=x1-x0, c=x0y1-x1y0，欲判斷中點M在Q點的上方還是下方，只要把M代入F（x，y），并判斷它的符號即可

7、。為此，我們構造判別式：d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c     當d<0時，M在L(Q點)下方，取P2為下一個像素；     當d>0時，M在L(Q點)上方，取P1為下一個像素；     當d=0時，選P1或P2均可，約定取P1為下一個像素；注意到d是xp, yp的線性函數，可采用增量計算，提高運算效率。    若當前像素處于d³0情況，則取正右方像素

8、P1(xp+1, yp),要判下一個像素位置，應計算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a，增量為a。    若d<0時，則取右上方像素P2(xp+1, yp+1)。要判斷再下一像素，則要計算d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ，增量為ab。畫線從(x0, y0)開始，d的初值 d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，因 

9、; F(x0, y0)=0，所以d0=a+0.5b。    由于我們使用的只是d的符號，而且d的增量都是整數，只是初始值包含小數。因此，我們可以用2d代替d來擺脫小數，寫出僅包含整數運算的算法程序。 中點畫線算法程序：void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y；  a=y0-y1； b=x1-x0；d=2*a+b；  d1=2*a；d2=2* (a+b)；  x=x0；y=y0； 

10、; drawpixel(x, y, color);  while (x<x1)  if (d<0)   x+；y+； d+=d2;     else      x+； d+=d1;    drawpixel (x, y, color);  /* while */ /* mid PointLine */  舉例：用中點畫線方法掃描轉換連接兩點P0（0,0）和P1（5,2）的直線段。a=y0-y1=-2; b=x1-x

11、0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 ,xyd00110-321331-14255215圖3.1.3 中點畫線法問題1：若上述算法往下取二步(Di=2)，則算法和像素的取法將變成怎樣？問題2：與DDA法相比，中點法的優點是什么？動畫演示：中點畫線算法 Bresenham算法    Bresenham算法是計算機圖形學領域使用最廣泛的直線掃描轉換算法。仍然假定直線斜率在01之間，該方法類似于中點法，由一個誤差項符號決定下一個像素點。    算法原理如下：過各行各列像素中心構造一組虛擬網格線。按直線

12、從起點到終點的順序計算直線與各垂直網格線的交點，然后確定該列像素中與此交點最近的像素。該算法的巧妙之處在于采用增量計算，使得對于每一列，只要檢查一個誤差項的符號，就可以確定該列的所求像素。    如圖所示，設直線方程為yi+1=yi+k(xi+1-xi)+k。假設列坐標像素已經確定為xi，其行坐標為yi。那么下一個像素的列坐標為xi1，而行坐標要么為yi，要么遞增1為yi1。是否增1取決于誤差項d的值。誤差項d的初值d00，x坐標每增加1，d的值相應遞增直線的斜率值k，即ddk。一旦 d1，就把它減去1，這樣保證d在0、1之間。當d0.5時，直線與垂線x

13、=xi1交點最接近于當前像素(xi，yi)的右上方像素(xi1，yi1)；而當d<0.5時，更接近于右方像素(xi1，yi)。為方便計算，令ed0.5，e的初值為0.5，增量為k。當e0時，取當前像素(xi，yi)的右上方像素(xi1，yi1)；而當e<0時，取(xi，yi)右方像素(xi1，yi)。圖3.1.4 Bresenham算法所用誤差項的幾何含義Bresenham畫線算法程序：void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy；  float k, e;

14、0; dx = x1-x0；dy = y1- y0；k=dy/dx；  e=-0.5； x=x0,；y=y0；  for (i=0；i<dx；i+)  drawpixel (x, y, color);    x=x+1；e=e+k;    if (e³0)    y+； e=e-1;    舉例：用Bresenham方法掃描轉換連接兩點P0（0,0）和P1（5,2）的直線段。xye00-0.510-0.121-0.731-0.342-0.9

15、52-0.5圖3.1.5 Bresenham算法     上述Bresenham算法在計算直線斜率與誤差項時用到小數與除法。可以改用整數以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換：2*e*dx。    改進的Bresenham畫線算法程序：void InterBresenhamline (int x0,int y0,int x1, int y1,int color) dx = x1-x0,；dy = y1- y0,；e=-dx;  x=x0； y=y0;  for (i=0; i<d

16、x; i+)  drawpixel (x, y, color);   x+； e=e+2*dy;   if (e³0) y+; e=e-2*dx;   動畫演示：Bresenham畫線算法：3.2 圓弧的掃描轉換算法   這一節我們來討論圓弧的掃描轉換算法。3.2.1圓的特征    圓被定義為到給定中心位置(xc,yc)距離為r的點集。圓心位于原點的圓有四條對稱軸x=0,y=0,x=y和x=-y。若已知圓弧上一點(x,y),可以得到其關于四條對稱

17、軸的其它7個點，這種性質稱為圓的八對稱性。因此，只要掃描轉換八分之一圓弧，就可以求出整個圓弧的像素集。  顯示圓弧上的八個對稱點的算法：void CirclePoints(int x,int y,int color) drawpixel(x,y,color); drawpixel(y,x,color);  drawpixel(-x,y,color); drawpixel(y,-x,color);  drawpixel(x,-y,color); drawpixel(-y,x,color);  drawpixel(-x,-y,color); drawpixe

18、l(-y,-x,color);3.2.2中點畫圓法    如果我們構造函數 F(x,y)=x2+y2-R2，則對于圓上的點有F(x,y)=0，對于圓外的點有F(x,y)>0，對于圓內的點F(x,y)<0 。與中點畫線法一樣，構造判別式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若 d<0，則應取P1為下一像素，而且再下一像素的判別式為：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3若d0，則應取P2為下一像素，而且下一像素的判別式為：d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5我們這里討論的第一個像素是（0,R），判別式d的初始值為：d0=F(1,R-0.5)=1.25-R圖3.2.1 當前像素與下一像素的候選者 中點畫圓算法：MidPointCircle(int r int color) int x,y;  float d;  x=0; y=r; d=