直線和圓弧的生成算法.doc

第3章 直線和圓弧的生成算法3.1直線圖形的生成算法 數(shù)學(xué)上的直線是沒有寬度、由無數(shù)個(gè)點(diǎn)構(gòu)成的集合，顯然，光柵顯示器只能近地似顯示直線。當(dāng)我們對直線進(jìn)行光柵化時(shí)，需要在顯示器有限個(gè)像素中，確定最佳逼近該直線的一組像素，并且按掃描線順序，對這些像素進(jìn)行寫操作，這個(gè)過程稱為用顯示器繪制直線或直線的掃描轉(zhuǎn)換。 由于在一個(gè)圖形中，可能包含成千上萬條直線，所以要求繪制算法應(yīng)盡可能地快。本節(jié)我們介紹一個(gè)像素寬直線繪制的三個(gè)常用算法：數(shù)值微分法（DDA）、中點(diǎn)畫線法和Bresenham算法。3.1.1逐點(diǎn)比較法3.1.2數(shù)值微分(DDA)法設(shè)過端點(diǎn)P0(x0,y0)、P1(x1,y1)的直線段為L(P0,P1)，則直線段L的斜率L的起點(diǎn)P0的橫坐標(biāo)x0向L的終點(diǎn)P1的橫坐標(biāo)x1步進(jìn)，取步長=1(個(gè)像素)，用L的直線方程y=kx+b計(jì)算相應(yīng)的y坐標(biāo)，并取像素點(diǎn)(x,round(y)作為當(dāng)前點(diǎn)的坐標(biāo)。因?yàn)椋簓i+1=kxi+1+b =k1xi+b+kDx =yi+kDx 所以，當(dāng)Dx =1;yi+1=yi+k。也就是說，當(dāng)x每遞增1，y遞增k(即直線斜率)。根據(jù)這個(gè)原理，我們可以寫出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； k=dy/dx,；y=y0； for (x=x0；x1時(shí)，必須把x，y地位互換，y每增加1，x相應(yīng)增加1/k。在這個(gè)算法中，y與k必須用浮點(diǎn)數(shù)表示，而且每一步都要對y進(jìn)行四舍五入后取整，這使得它不利于硬件實(shí)現(xiàn)。動(dòng)畫演示：數(shù)值微分畫線算法（DDA）3.1.3中點(diǎn)畫線法假定直線斜率k在01之間，當(dāng)前像素點(diǎn)為（xp,yp），則下一個(gè)像素點(diǎn)有兩種可選擇點(diǎn)P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點(diǎn)（xp+1,yp+0.5）稱為M，Q為理想直線與x=xp+1垂線的交點(diǎn)。當(dāng)M在Q的下方時(shí)，則取P2應(yīng)為下一個(gè)像素點(diǎn)；當(dāng)M在Q的上方時(shí)，則取P1為下一個(gè)像素點(diǎn)。這就是中點(diǎn)畫線法的基本原理。圖3.1.2 中點(diǎn)畫線法每步迭代涉及的像素和中點(diǎn)示意圖下面討論中點(diǎn)畫線法的實(shí)現(xiàn)。過點(diǎn)(x0,y0)、(x1,y1)的直線段L的方程式為F(x,y)=ax+by+c=0，其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0，欲判斷中點(diǎn)M在Q點(diǎn)的上方還是下方，只要把M代入F（x，y），并判斷它的符號(hào)即可。為此，我們構(gòu)造判別式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c 當(dāng)d0時(shí)，M在L(Q點(diǎn))上方，取P1為下一個(gè)像素； 當(dāng)d=0時(shí)，選P1或P2均可，約定取P1為下一個(gè)像素；注意到d是xp,yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。 若當(dāng)前像素處于d0情況，則取正右方像素P1(xp+1, yp),要判下一個(gè)像素位置，應(yīng)計(jì)算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a，增量為a。 若d0時(shí)，則取右上方像素P2(xp+1,yp+1)。要判斷再下一像素，則要計(jì)算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，因 F(x0,y0)=0，所以d0=a+0.5b。 由于我們使用的只是d的符號(hào)，而且d的增量都是整數(shù)，只是初始值包含小數(shù)。因此，我們可以用2d代替d來擺脫小數(shù)，寫出僅包含整數(shù)運(yùn)算的算法程序。中點(diǎn)畫線算法程序：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； drawpixel(x, y, color); while (xx1) if (d0) x+；y+； d+=d2; else x+； d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */ 舉例：用中點(diǎn)畫線方法掃描轉(zhuǎn)換連接兩點(diǎ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 中點(diǎn)畫線法問題1：若上述算法往下取二步(Di=2)，則算法和像素的取法將變成怎樣？問題2：與DDA法相比，中點(diǎn)法的優(yōu)點(diǎn)是什么？動(dòng)畫演示：中點(diǎn)畫線算法3.1.4 Bresenham算法 Bresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域使用最廣泛的直線掃描轉(zhuǎn)換算法。仍然假定直線斜率在01之間，該方法類似于中點(diǎn)法，由一個(gè)誤差項(xiàng)符號(hào)決定下一個(gè)像素點(diǎn)。 算法原理如下：過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)最近的像素。該算法的巧妙之處在于采用增量計(jì)算，使得對于每一列，只要檢查一個(gè)誤差項(xiàng)的符號(hào)，就可以確定該列的所求像素。 如圖2.1.4所示，設(shè)直線方程為yi+1=yi+k(xi+1-xi)+k。假設(shè)列坐標(biāo)像素已經(jīng)確定為xi，其行坐標(biāo)為yi。那么下一個(gè)像素的列坐標(biāo)為xi1，而行坐標(biāo)要么為yi，要么遞增1為yi1。是否增1取決于誤差項(xiàng)d的值。誤差項(xiàng)d的初值d00，x坐標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。一旦d1，就把它減去1，這樣保證d在0、1之間。當(dāng)d0.5時(shí)，直線與垂線x=xi1交點(diǎn)最接近于當(dāng)前像素(xi，yi)的右上方像素(xi1，yi1)；而當(dāng)d0.5時(shí)，更接近于右方像素(xi1，yi)。為方便計(jì)算，令ed0.5，e的初值為0.5，增量為k。當(dāng)e0時(shí)，取當(dāng)前像素(xi，yi)的右上方像素(xi1，yi1)；而當(dāng)e0時(shí)，取(xi，yi)右方像素(xi1，yi)。圖3.1.4 Bresenham算法所用誤差項(xiàng)的幾何含義Bresenham畫線算法程序：void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy； float k, e; dx = x1-x0；dy = y1- y0；k=dy/dx； e=-0.5； x=x0,；y=y0； for (i=0；idx；i+) drawpixel (x, y, color); x=x+1；e=e+k; if (e0) y+； e=e-1; 舉例：用Bresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。xye00-0.510-0.121-0.731-0.342-0.952-0.5圖3.1.5 Bresenham算法 上述Bresenham算法在計(jì)算直線斜率與誤差項(xiàng)時(shí)用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換：2*e*dx。 改進(jìn)的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; i0，對于圓內(nèi)的點(diǎn)F(x,y)0 。與中點(diǎn)畫線法一樣，構(gòu)造判別式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若d0，則應(yīng)取P1為下一像素，而且再下一像素的判別式為：d=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2=d+2xp+3若d0，則應(yīng)取P2為下一像素，而且下一像素的判別式為：d=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+2(xp-yp)+5我們這里討論的第一個(gè)像素是（0,R），判別式d的初始值為：d0=F(1,R-0.5)=1.25-R圖3.2.1 當(dāng)前像素與下一像素的候選者中點(diǎn)畫圓算法：MidPointCircle(int r int color) int x,y; float d; x=0; y=r;