直線和圓弧的生成算法

1、第3章直線和圓弧的生成算法3.1 直線圖形的生成算法數(shù)學(xué)上的直線是沒有寬度、由無數(shù)個(gè)點(diǎn)構(gòu)成的集合，顯然，光柵顯示器只 能近地似顯示直線。當(dāng)我們對(duì)直線進(jìn)行光柵化時(shí)，需要在顯示器有限個(gè)像素中， 確定最佳逼近該直線的一組像素，并且按掃描線順序，對(duì)這些像素進(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)R（x0 ,y。、P1（X1 y）的直線段為L(zhǎng)（Po

2、R）,則直線段L的斜率為”也 要在顯示器顯示也 必須確定最佳逼近£的氟素集合口我們從 內(nèi)一兩L的起點(diǎn)Po的橫坐標(biāo)X0向L的終點(diǎn)Pi的橫坐標(biāo)xi步進(jìn)，取步長(zhǎng)=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)椋簓+1= kxi+1+b=k1xi+b+ k x=yi+k x所以，當(dāng)X =1;yi+i = y+ko也就是說，當(dāng)x每遞增1, y遞增k(即直線斜率)。根據(jù)這個(gè)原理，我們可以寫出DDA ( Digital Differential Analyzer )畫線算法程序。DDA畫線算法程序:void DDALine(in

3、t 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 ； x< x1 ； x+) drawpixel (x, int(y+0.5), color);y=y+k;注意：我們這里用整型變量color表示像素的顏色和灰度。舉例：用DDA方法掃描轉(zhuǎn)換連接兩點(diǎ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直線段的

4、掃描轉(zhuǎn)換注意：上述分析的算法僅適用于|k|<1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)|k| 1時(shí)，必須把x, y地位互換，y每增加1, x相應(yīng)增加 1/k。在這個(gè)算法中，y與k必須用浮點(diǎn)數(shù)表示，而且每一步都要對(duì)y進(jìn)行四舍五 入后取整，這使得它不利于硬件實(shí)現(xiàn)。動(dòng)畫演示：數(shù)值微分畫線算法(DDA)用仍用方筑益柏轉(zhuǎn)換盤盤兩直 亞3G笈P (5,2)的去俵包O 一為起始點(diǎn)一為當(dāng)前象親點(diǎn)o 為終止點(diǎn)522.。| 0. 5Word資料3.1.3 中點(diǎn)畫線法假定直線斜率k在01之間，當(dāng)前像素點(diǎn)為(”,yp),則下一個(gè)像素點(diǎn) 有兩種可選擇點(diǎn)Pi (xp+1,yp)或P2 (xp+1,yp+1

5、 )。若Pi與沁的中點(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í)，則取Pi為下一個(gè)像素點(diǎn)。這就是中點(diǎn)畫 線法的基本原理。圖3.1.2中點(diǎn)畫線法每步迭代涉及的像素和中點(diǎn)示意圖下面討論中點(diǎn)畫線法的實(shí)現(xiàn)。過點(diǎn)(xo,y。)、(xi, yi)的直線段L的方程式為 F(x, y)=ax+by+c= 0,其中，a=yo-yi, b=xi-xo, c=xoyi-xiyo,欲判斷中點(diǎn) M 在 Q 點(diǎn) 的上方還是下方，只要把 M代入F (x, y),并判斷它的符號(hào)即可。為此，我們 構(gòu)造判別式：d= F(M)= F(x

6、o+i, yp+0.5)= a(xp+i)+ b(yp+0.5)+ c當(dāng)d<0時(shí)，M在L(Q點(diǎn))下方，取8為下一個(gè)像素；當(dāng)d>0時(shí)，M在L(Q點(diǎn))上方，取Pi為下一個(gè)像素；當(dāng)d=0時(shí)，選Pi或P2均可，約定取Pi為下一個(gè)像素； 注意到d是xp,yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。若當(dāng)前像素處于d 0情況，則取正右方像素Pi(xp+1, yp),要判下一個(gè)像素 位置，應(yīng)計(jì)算 di = F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)= d + a,增量為 a。若d<0時(shí)，則取右上方像素P2(xp+1, yp+1)0要判斷再下一像素，則要計(jì) 算 d2=

7、 F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b，增量為 a+ b。畫線從(xo,yo) 開始，d 的初值 do=F(xo+1, yo+o.5)=F(xo, yo)+a+o.5b,因 F(xo, yo)=o,所以 do= a+o.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,

8、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 */ /* 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

9、 ,xyd00110-321331-14255215圖3.1.3中點(diǎn)畫線法問題1:若上述算法往下取二步(i=2),則算法和像素的取法將變成怎樣?問題2:與DDA法相比，中點(diǎn)法的優(yōu)點(diǎn)是什么?動(dòng)畫演示：中點(diǎn)畫線算法用中支詼假力俊扣盤搶排連接國直亞9G和制(52)的支修段d=F(M)=F (jp+1, yptJL 5) =a (sp+1 > +b (yp+0.5)+a a=y0-yl=-2: W1-j(O5; d0=2*a+b= 1 ;d1=2*a= ;d2=2*(a+b) =6 a以正石用象系為卜一個(gè)家靠位置一水電收右上方發(fā)黃力下，個(gè)象然他附3.1.4 Bresenham 算法Bresenh

10、am算法是計(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ì)算，使得對(duì)于每一列，只要檢查一個(gè)誤差項(xiàng)的符號(hào)，就可以確定該列的所求像素。如圖2.1.4所示，設(shè)直線方程為yi+產(chǎn)yi+k(x+xi)+k。假設(shè)列坐標(biāo)像素已經(jīng) 確定為x,其行坐標(biāo)為yio那么下一個(gè)像素的列坐標(biāo)為 x+1,而行坐標(biāo)要么為V，要么遞增1為yi+ 1。是否增1取決于誤差項(xiàng)d

11、的值。誤差項(xiàng)d的初值d0=0, x坐標(biāo)每增加1, d的值相應(yīng)遞增直線的斜率值k,即=十七一旦d1,就 把它減去1,這樣保證d在0、1之間。當(dāng)d >0.5時(shí)，直線與垂線x=x+1交點(diǎn) 最接近于當(dāng)前像素僅i, yi)的右上方像素(x+1, y+1);而當(dāng)d<0.5時(shí)，更接近于 右方像素(x+1, y)。為方便計(jì)算，令e = d 0.5, e的初值為-0.5,增量為k。 當(dāng)e0時(shí)，取當(dāng)前像素(x, yi)的右上方像素(x+1, yi+1);而當(dāng)e<0時(shí)，取僅i, yi)右方像素(xi+1, y)。圖3.1.4 Bresenham算法所用誤差項(xiàng)的幾何含義O Bresenham畫線算法

12、程序： 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 ； i<dx ； i+) drawpixel (x, y, color);x=x+1 ； e=e+k;if (e 0) y+； e=e-1;舉例：用Bresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)P0 (0,0)和P1 (5,2)的直線段xye00-0.510-0.121-0.731-0

13、.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; i<dx; i+)drawpixel (x, y, color);x+ ； e=e+2*

14、dy;if (e 0) y+; e=e-2*dx;動(dòng)畫演示： Bresenham 畫線算法:用方?？巯噢D(zhuǎn)穩(wěn)屈曩愚魚P0。.切備W (5)的直我期*d 0, 5, d+k, k-dv/dx»'戶QHlr取與前兼索加在匕以朱春為下 個(gè)以意-為當(dāng)前象素點(diǎn)一為，一個(gè)象素點(diǎn)O 為初始點(diǎn)o -為終止點(diǎn)1 0-U.5-0. JU " -o. 5 -o. 52 5 3-0.73 1-0. 731 20, 1-055 2-0.9-0. 5rep1 ay3.2 圓弧的掃描轉(zhuǎn)換算法這一節(jié)我們來討論圓弧的掃描轉(zhuǎn)換算法。3.2.1 圓的特征圓被定義為到給定中心位置(xc,yc)距離為r的點(diǎn)集

15、。圓心位于原點(diǎn)的圓有 四條對(duì)稱軸x=0,y=0,x=y和x=-y。若已知圓弧上一點(diǎn)(x,y),可以得到其關(guān)于四條對(duì) 稱軸的其它7個(gè)點(diǎn)，這種性質(zhì)稱為圓的八對(duì)稱性。因此，只要掃描轉(zhuǎn)換八分之一 圓弧，就可以求出整個(gè)圓弧的像素集。顯示圓弧上的八個(gè)對(duì)稱點(diǎn)的算法：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);

16、drawpixel(-x,-y,color); drawpixel(-y,-x,color);3.2.2 中點(diǎn)畫圓法如果我們構(gòu)造函數(shù)F(x,y)=x2+y2-R2,則對(duì)于圓上的點(diǎn)有F(x,y)=0 ,對(duì)于圓外的點(diǎn)有F(x,y)>0,對(duì)于圓內(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若d<0,則應(yīng)取Pi為下一像素，而且再下一像素的判別式為：d= F(xp+2,yp-0.5)=( xp+2)2+(yp-0.5)2- R2=d+2xp+3若d冷，則應(yīng)取P2為下一像素，而且下 一像

17、素的判別式為：d= F(xp+2,yp-1.5)=( xp+2)2+(yp-1.5)2- R2=d+2( xp- yp)+5我們這里討論的第一個(gè)像素是(0,R),判別式d的初始值為：do=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; d=1.25-r;circlepoints (x,y,color);while(x<=y) if(d<0) d+=2*x+3;else d+=2*(x-y)+5; y-;x+;circlepoin

18、ts (x,y,color);為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。動(dòng)畫演示：中點(diǎn)畫圓算法:圓的對(duì)稱性假設(shè)已知小同心在原點(diǎn)的圜 上 點(diǎn)a, 丫）根據(jù)對(duì)稱性可得 另外L個(gè)八分網(wǎng)上的對(duì)榔直.二:中點(diǎn)畫圓算法判別式的構(gòu)造考慮中心在原點(diǎn)，舉獨(dú)為R的四的第二個(gè)A 分圓.假定需坐標(biāo)為心的賽素中.與該圈強(qiáng) 最近的祿素已定,為巴加那么，下一 1、。%冏瓢心近的象素只能是口豫常正右方 的Pl&p+If Vr）或右下方的P（Yp+l,昨一D兩 者之一.構(gòu)造函數(shù)：所以，沿正右方向,d的增量為2小十；，此時(shí)FM4時(shí),M在囪外,總距離眥瓠 更近”則應(yīng)取P九曾FOO=。時(shí)，Pi 與巴任取個(gè)：我們約定聯(lián)IF檢設(shè)M是內(nèi)和匕的中點(diǎn),即5) 那么.當(dāng)FOOS時(shí).M在做內(nèi),這說明巴 鹿總同菰更近.應(yīng)取因作為下 奧素.構(gòu)璉判別式為：介丹“尸四¥,+1,丁0.5)(片十1尸十(廣。5)二爐若d<0,則應(yīng)取P1為下一象素，而且再下一個(gè)象嚷的判別式為rf=>X/>+2f >-O.5)=(A)>+2)-+(匕“().5尸-/?工=+2勾43而若d”0,則P2是卜一象素，而且下一象素的判別式為二代加+2g".5尸(而十力十0/，3)二代 =J+(2x-+3)+(- 2)+