直線和圓弧的生成算法

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

=yi+kx

所以,當x=1;yi+1=yi+k。也就是說,當x每遞增1,y遞增k<即直線斜率>。根據(jù)這個原理,我們可以寫出DDA〔DigitalDifferentialAnalyzer畫線算法程序。DDA畫線算法程序：voidDDALine<intx0,inty0,intx1,inty1,intcolor>{intx；

floatdx,dy,y,k；

dx=x1-x0；dy=y1-y0；

k=dy/dx,；y=y0；

for<x=x0；x<x1；x++>

{drawpixel<x,int<y+0.5>,color>;

y=y+k;

}}注意：我們這里用整型變量color表示像素的顏色和灰度。舉例：用DDA方法掃描轉(zhuǎn)換連接兩點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注意：上述分析的算法僅適用于|k|≤1的情形。在這種情況下,x每增加1,y最多增加1。當|k|1時,必須把x,y地位互換,y每增加1,x相應增加1/k。在這個算法中,y與k必須用浮點數(shù)表示,而且每一步都要對y進行四舍五入后取整,這使得它不利于硬件實現(xiàn)。動畫演示：數(shù)值微分畫線算法〔DDA中點畫線法假定直線斜率k在0~1之間,當前像素點為〔xp,yp,則下一個像素點有兩種可選擇點P1〔xp+1,yp或P2〔xp+1,yp+1。若P1與P2的中點〔xp+1,yp+0.5稱為M,Q為理想直線與x=xp+1垂線的交點。當M在Q的下方時,則取P2應為下一個像素點；當M在Q的上方時,則取P1為下一個像素點。這就是中點畫線法的基本原理。圖3.1.2下面討論中點畫線法的實現(xiàn)。過點<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,并判斷它的符號即可。為此,我們構造判別式：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的線性函數(shù),可采用增量計算,提高運算效率。

若當前像素處于d0情況,則取正右方像素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,增量為a＋b。畫線從<x0,y0>開始,d的初值d0=F<x0+1,y0+0.5>=F<x0,y0>+a+0.5b,因

F<x0,y0>=0,所以d0=a+0.5b。

由于我們使用的只是d的符號,而且d的增量都是整數(shù),只是初始值包含小數(shù)。因此,我們可以用2d代替d來擺脫小數(shù),寫出僅包含整數(shù)運算的算法程序。中點畫線算法程序：voidMidpointLine<intx0,inty0,intx1,inty1,intcolor>{inta,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；

drawpixel<x,y,color>;

while<x<x1>{if(d<0)

{x++；y++；d+=d2;}

else

{x++；d+=d1;}

drawpixel<x,y,color>;

}/*while*/}/*midPointLine*/舉例：用中點畫線方法掃描轉(zhuǎn)換連接兩點P0〔0,0和P1〔5,2的直線段。a=y0-y1=-2;b=x1-x0=5;d0=2*a+b=1;d1=2*a=-4;d2=2*<a+b>=6,xyd00110-321331-14255215圖3.1.3問題1：若上述算法往下取二步<i=2>,則算法和像素的取法將變成怎樣？問題2：與DDA法相比,中點法的優(yōu)點是什么？動畫演示：中點畫線算法Bresenham算法

Bresenham算法是計算機圖形學領域使用最廣泛的直線掃描轉(zhuǎn)換算法。仍然假定直線斜率在0~1之間,該方法類似于中點法,由一個誤差項符號決定下一個像素點。

算法原理如下：過各行各列像素中心構造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點,然后確定該列像素中與此交點最近的像素。該算法的巧妙之處在于采用增量計算,使得對于每一列,只要檢查一個誤差項的符號,就可以確定該列的所求像素。

如圖所示,設直線方程為yi+1=yi+k<xi+1-xi>+k。假設列坐標像素已經(jīng)確定為xi,其行坐標為yi。那么下一個像素的列坐標為xi＋1,而行坐標要么為yi,要么遞增1為yi＋1。是否增1取決于誤差項d的值。誤差項d的初值d0＝0,x坐標每增加1,d的值相應遞增直線的斜率值k,即d＝d＋k。一旦

d≥1,就把它減去1,這樣保證d在0、1之間。當d≥0.5時,直線與垂線x=xi＋1交點最接近于當前像素<xi,yi>的右上方像素<xi＋1,yi＋1>；而當d<0.5時,更接近于右方像素<xi＋1,yi>。為方便計算,令e＝d－0.5,e的初值為－0.5,增量為k。當e≥0時,取當前像素<xi,yi>的右上方像素<xi＋1,yi＋1>；而當e<0時,取<xi,yi>右方像素<xi＋1,yi>。圖3.1.4○B(yǎng)resenham畫線算法程序：voidBresenhamline<intx0,inty0,intx1,inty1,intcolor>{intx,y,dx,dy；

floatk,e;

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<e0>{y++；e=e-1;}

}}舉例：用Bresenham方法掃描轉(zhuǎn)換連接兩點P0〔0,0和P1〔5,2的直線段。xye00-0.510-0.121-0.731-0.342-0.952-0.5圖3.1.5上述Bresenham算法在計算直線斜率與誤差項時用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項的符號,因此可作如下替換：2*e*dx。改進的Bresenham畫線算法程序：voidInterBresenhamline<intx0,inty0,intx1,inty1,intcolor>{dx=x1-x0,；dy=y1-y0,；e=-dx;

x=x0；y=y0;

for<i=0;i<dx;i++>

{drawpixel<x,y,color>;

x++；e=e+2*dy;

if<e0>{y++;e=e-2*dx;}

}}動畫演示：Bresenham畫線算法：3.2圓弧的掃描轉(zhuǎn)換算法這一節(jié)我們來討論圓弧的掃描轉(zhuǎn)換算法。圓的特征圓被定義為到給定中心位置<xc,yc>距離為r的點集。圓心位于原點的圓有四條對稱軸x=0,y=0,x=y和x=-y。若已知圓弧上一點<x,y>,可以得到其關于四條對稱軸的其它7個點,這種性質(zhì)稱為圓的八對稱性。因此,只要掃描轉(zhuǎn)換八分之一圓弧,就可以求出整個圓弧的像素集。顯示圓弧上的八個對稱點的算法：voidCirclePoints<intx,inty,intcolor>{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>;drawpixel<-y,-x,color>;}中點畫圓法

如果我們構造函數(shù)F<x,y>=x2+y2-R2,則對于圓上的點有F<x,y>=0,對于圓外的點有F<x,y>>0,對于圓內(nèi)的點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若d≥0,則應取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<intrintcolor>{intx,y