第三章二維圖形的生成_直線和圓

1、2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)1第四章、二維圖形的生成和變換第四章、二維圖形的生成和變換4.1、直線段的掃描轉(zhuǎn)換算法 4.1.1、DDA算法 4.1.2、中點(diǎn)畫線法 4.1.3、Bresenham畫線算法4.2、圓弧掃描轉(zhuǎn)換算法 4.2.1、中點(diǎn)算法 4.2.2、Bresenham畫圓算法 4.2.3、生成圓弧的正負(fù)法4.3、橢圓弧生成算法 2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)2 對一維圖形，不考慮線寬，則用一個(gè)像素寬的直線來顯示圖形。二維圖形的光柵化，即區(qū)域的填充：確定像素集，填色或圖案。 任何圖形的光柵化，必須顯示在一個(gè)窗口內(nèi)，否則不予顯示。即確定一個(gè)圖形的哪些部分在窗口內(nèi)，

2、哪些在窗口外，即裁剪。 圖形的掃描轉(zhuǎn)換（光柵化）：確定一個(gè)像素集合，用于顯示一個(gè)圖形的過程。步驟如下：1、確定有關(guān)像素2、用圖形的顏色或其它屬性，對像素進(jìn)行寫操作2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)3圖形顯示前需要：掃描轉(zhuǎn)換+裁剪u裁剪-掃描轉(zhuǎn)換：最常用，節(jié)約計(jì)算時(shí)間。u掃描轉(zhuǎn)換-裁剪：算法簡單；2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)4v圖形顯示器是由一個(gè)個(gè)排列有序的像素構(gòu)成，劃分的像素點(diǎn)越多分辨率就越高。例如640X480的顯示器，分成640X480個(gè)網(wǎng)格，網(wǎng)格單元視為像素，一條線段就是由一些連續(xù)可見的像素所組成，如下圖所示：4.1 直線段的掃描轉(zhuǎn)換算法v在數(shù)學(xué)上，理想的直線是沒有寬度

3、的，是由無數(shù)個(gè)在它上面的點(diǎn)構(gòu)成的集合。直線可以向一個(gè)方向及其相反的方向無限延長。v在圖形學(xué)中研究的對象是直線段，它是一條具有一個(gè)Pixel或多個(gè)Pixel寬的直線段。2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)5由上圖可知：由上圖可知：畫一條直線實(shí)際上就是根據(jù)一系列計(jì)算出來并與畫一條直線實(shí)際上就是根據(jù)一系列計(jì)算出來并與該直線靠近的像素繪制的該直線靠近的像素繪制的。Line: P0(0,0)P1(5,2)0143215234各行各列像素中心構(gòu)成的一組虛擬網(wǎng)格線像素單元4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法0123456 701234562022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)6v直線的掃描

4、轉(zhuǎn)換直線的掃描轉(zhuǎn)換: : 確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進(jìn)行寫操作。v直線段是最基本的圖形，因此直線段生成的質(zhì)量好直線段是最基本的圖形，因此直線段生成的質(zhì)量好壞與速度快慢將直接影響整個(gè)圖形生成的質(zhì)量和速壞與速度快慢將直接影響整個(gè)圖形生成的質(zhì)量和速度。度。v三個(gè)常用算法：數(shù)值微分法（DDA）中點(diǎn)畫線法Bresenham算法。4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)74.1.1、數(shù)值微分法（） 假定直線的起點(diǎn)、終點(diǎn)分別為:(x0,y0),(x1,y1)，且都為整數(shù)。柵格交點(diǎn)表示象素點(diǎn)位置(X i+1 ,Yi + k)(X

5、 i , Yi)4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)8v基本思想 已知直線L兩端點(diǎn)位P0 (x0, y0), P1(x1, y1)4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法kdxdy斜率即0101xxyyxy可以通過x方向的增量x，計(jì)算y的增量y來生成直線。yyyii 1xxxyyyyii0101101011xxyyyyii當(dāng)1x得4.1.1、數(shù)值微分法（）2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)9v即：當(dāng)x方向每遞增1像素，y方向遞增k(即直線斜率)；每次通過上式計(jì)算出（xi，yi）取整后輸出顯示器。v注意上述分析的算法僅適用于k 1

6、的情形。在這種情況下，x每增加1,y最多增加1。4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法01011xxyyyyii當(dāng)1x得4.1.1、數(shù)值微分法（）2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)10v注：當(dāng) 時(shí)，必須把x,y位置互換，即利用遞推式 ，y每增加1，x相應(yīng)增加 。所以取 和 中較大者為步進(jìn)方向，如下圖1 kykxxii 11k112xx 12yy 1k 當(dāng)時(shí)x為步進(jìn)方向?yàn)椴竭M(jìn)方向y為步進(jìn)方向?yàn)椴竭M(jìn)方向4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)110 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)v例：畫直線段

7、P0(0,0)-P1(5,2) k=0.4 x y+k 四舍五入int（y+0.5) 0 0 0 1 0.4 0 2 0.8 1 3 1.2 1 4 1.6 2 5 2 24.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.1、數(shù)值微分法（）2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)12void 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; xx1, x+) putpixel (x, int(y+0.5

8、), color); y=y+k; 4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.1、數(shù)值微分法（）2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)13v增量算法：在一個(gè)迭代算法中，如果每一步的x、y值是用前一步的值加上一個(gè)增量來獲得，則稱為增量算法。vDDA算法就是一個(gè)增量算法。4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法v該算法的優(yōu)點(diǎn)是繪制實(shí)數(shù)直線效果好，誤差小。缺點(diǎn)是實(shí)現(xiàn)較復(fù)雜，不利于硬件實(shí)現(xiàn)。v該算法涉及到實(shí)數(shù)乘除法運(yùn)算，y與k必須用浮點(diǎn)數(shù)表示，而且每一步都要對y進(jìn)行四舍五入后取整。4.1.1、數(shù)值微分法（）2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)144.1.2、中點(diǎn)畫線法v原理

9、：假定直線斜率0K P2離直線更近更近-取P2 。M在Q的上方- P1離直線更近更近-取P1M與Q重合， P1、P2任取一點(diǎn)。問題：如何判斷M與Q點(diǎn)的關(guān)系？P=(xp,yp)QP2P1M4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)16欲判斷中點(diǎn)M點(diǎn)是在Q點(diǎn)上方還是在Q點(diǎn)下方，只需把M代入F(x,y),并檢查它的符號。在直線下方點(diǎn)在直線上方點(diǎn)在直線上面點(diǎn)),(0,),(0,),(0,yxyxFyxyxFyxyxFP=(xp,yp)QP2P1M4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法 假設(shè)直線方程為：a

10、x+by+c=0 其中a=y0-y1, b=x1-x0, c=x0y1-x1y02022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)17當(dāng)d=0，選P1或P2均可，約定取P1；P=(xP=(xp p,y,yp p) )QP P2P P14.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法構(gòu)造判別式： d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c當(dāng)d0，M在直線(Q點(diǎn))上方，取右方P1；能否采用增量算法呢？M2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)18情形1.若d0 -M在直線上方-取P1; 此時(shí)再下一個(gè)象素的判別式為 d1=F(xp+2, yp+0

11、.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 即d的增量為a,QP2P14.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法P=(xP=(xp p,y,yp p) )M4.1.2、中點(diǎn)畫線法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)19情形2.若dM在直線下方-取P2; 此時(shí)再下一個(gè)象素的判別式為 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ；即d的增量為abP=(xp,yp)QP2P14.1 直線段的掃描轉(zhuǎn)換算法直線段的掃

12、描轉(zhuǎn)換算法M4.1.2、中點(diǎn)畫線法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)20 畫線從(x0, y0)開始，d 的初值d0 0= =F( (x0 0+1, , y0 0+ +0.5)= a( (x0 0 +1)+ +b( (y0 0 + +0.5)+c = = F( (x0 0, , y0 0) )+a+0.5b = = a+0.5b 由于只用 d 的符號作判斷，為了只包含整數(shù)運(yùn)算, 可以用2d 代替 d 來擺脫小數(shù)，提高效率。4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法即d02*a+b 若d 0 增量為2*a 若d0 增量為2*(a+b)4.1.2、中點(diǎn)畫線法2022-7-2西安工程大學(xué)

13、計(jì)算機(jī)圖形學(xué)210 1 2 3 4 5321例：用中點(diǎn)畫線法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 ixiyid 1001 210-3 3213 431-1 54254.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.2、中點(diǎn)畫線法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)22中點(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=

14、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 */4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)234.1.3、直線的Bresenham算法 4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法 算法原理：過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點(diǎn)到終點(diǎn)的順序計(jì)

15、算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列象素中與此交點(diǎn)最近的象素。該算法的巧妙之處在于采用增量計(jì)算，使得對于每一列，只要檢查一個(gè)誤差項(xiàng)的符號，就可以確定該列的所求象素。 2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)24 為了討論方便，我們假定直線的斜率在01之間，其它情況類似處理如右圖所示，設(shè)直線方程為 ),(iiyx其中k=dy/dx。 假設(shè)當(dāng)前象素已經(jīng)確定為(xi, yi)那么下一個(gè)象素的列坐標(biāo)為xi1，而行坐標(biāo)要么不變?yōu)閥i，要么遞增1為yi1。 xkyxxkyyiiiii )(11yx4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.3、直線的Bresenham算法 bkxy則有20

16、22-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)25 是否增1取決于如圖所示誤差項(xiàng) d 的值。因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng) d 的初值d00 因?yàn)閤 每增加1，d 的值相應(yīng)遞增直線的斜率值 k，即ddk。1、當(dāng)d0.5時(shí)，直線與xi1列垂直網(wǎng)格交點(diǎn)最接近的象素為 右上方象素（xi+1，yi1）；）； 2 2、當(dāng)d0.5時(shí)，更接近直線的為正右方象素（xi1，yi）。 4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法注：一旦y方向上走一步，d=d-1。圖5-8 改進(jìn)的Brensemham算法繪制直線的原理ddddkkkkk2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)26為方便計(jì)算，令ed0.5，e 的初

17、值為0.5，增量為 k。結(jié)論：1. d 的初值d00， ddk；2.當(dāng) d 0.5時(shí)，下一個(gè)像素取為，右上方象素（xi+1，yi1）；）；3.當(dāng) d 0.5時(shí)，下一個(gè)像素取為 正右方象素（xi1，yi）。）。 2.2.當(dāng)e00，則(x,y)更新為(x+1,y+1)，同時(shí)將e更新為e-1；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒有畫完時(shí)，重復(fù)步驟3和4。否則結(jié)束。2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)28 舉例舉例1:用用BresenhamBresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和和P1（5,2）的直線段的直線段。斜率斜率K=2/5=0.4e0=-0.5

18、 e=d-0.5 , d=d+k, k=dy/dx當(dāng)當(dāng)e0時(shí)，取當(dāng)前像素的右上方像素為下一個(gè)像素時(shí)，取當(dāng)前像素的右上方像素為下一個(gè)像素當(dāng)當(dāng)e0時(shí)，取當(dāng)前像素的正右方像素為下一個(gè)像素時(shí)，取當(dāng)前像素的正右方像素為下一個(gè)像素4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法0143215234xe y e-10 0.5 01 0.1 02 0.3 1 0.73 0.3 14 0.1 2 0.95 0.5 22022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)29Bresenham畫線算法參考程序畫線算法參考程序 (0k1)：void Bresenhamline (int x0,int y0,int x1, int

19、 y1,int color) q int x,y,i;q float dx, dy ,k, e;q dx = x1-x0, dy = y1- y0, k=dy/dx;q e=-0.5, x=x0, y=y0;p for (i=0; i=0) y+, e=e-1;p p 4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法因?yàn)橐驗(yàn)橐坏┮坏﹜方向上走方向上走一步，就減去一步，就減去1。沒有擺脫浮點(diǎn)沒有擺脫浮點(diǎn)數(shù)計(jì)算數(shù)計(jì)算2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)30v 上述bresenham算法在計(jì)算誤差項(xiàng)與直線斜率時(shí)用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號，因此可作如下替換

20、： xyxyee210改進(jìn)的Bresenham畫線算法程序：4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法yxex22xee 2xe0遞增量遞增量y2初始量初始量原先原先10eeexxexe222即即xeee202022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)31void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy, e; dx = x1-x0;dy = y1- y0; e=-dx; x=x0; y=y0; for (i=0; i=0) y+; e=e-2*dx; 2022-7-2西安工程大學(xué)計(jì)算機(jī)圖

21、形學(xué)32Bresenham Bresenham 算法的優(yōu)點(diǎn)算法的優(yōu)點(diǎn)是：是：1 1、不必計(jì)算直線之斜率，因此不做除法；、不必計(jì)算直線之斜率，因此不做除法；2 2、不用浮點(diǎn)數(shù)，只用整數(shù)；、不用浮點(diǎn)數(shù)，只用整數(shù)；3 3、只做整數(shù)加減法和乘、只做整數(shù)加減法和乘2 2運(yùn)算，運(yùn)算， 而乘而乘2 2運(yùn)算可以用硬件移位實(shí)現(xiàn)。運(yùn)算可以用硬件移位實(shí)現(xiàn)。Bresenham Bresenham 算法速度很快，并適于用硬件實(shí)現(xiàn)算法速度很快，并適于用硬件實(shí)現(xiàn)。4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法4.1.3、直線的Bresenham算法 2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)33(1)(1)上述算法只對斜率

22、在上述算法只對斜率在0101之間的直線段生成適合，之間的直線段生成適合， 當(dāng)直線的斜率大于當(dāng)直線的斜率大于1 1時(shí)，算法應(yīng)該如何改進(jìn)時(shí)，算法應(yīng)該如何改進(jìn)? ?Max xMax y(0,0)(50,20)Max yMax x(0,0)(50,20)dddd注意：此時(shí)注意：此時(shí)d d或或e e的增量為的增量為 kk1 kdd1 幾點(diǎn)討論和思考幾點(diǎn)討論和思考4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)34pfor(i=0;i=0)p x=x+1;p e=e-1;p pv(2)(2)Bresenham畫線算法參考程序畫線算法參考程序 (k1)：vBresen

23、ham_line (int x0,int y0,int x1,int y1, int color)vint x,i,y;v float dx,dy,k,k1,e;v dx=x1-x0;v dy=y1-y0;v k=dy/dx;v k1=1/k;v e=-0.5;v x=x0;v y=y0;4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)35v(3)(3)根據(jù)上述的思想，我們?nèi)绾螌⑺惴〝U(kuò)展到，任根據(jù)上述的思想，我們?nèi)绾螌⑺惴〝U(kuò)展到，任一八分圓坐標(biāo)空間圖，從而形成一般一八分圓坐標(biāo)空間圖，從而形成一般BresenhamBresenham算算法？法？ 如下圖：如

24、下圖：4.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法v(4)(4)適用于任意斜率的適用于任意斜率的BresenhamBresenham直線生成算法直線生成算法程序示例程序示例2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)364.2 圓的掃描轉(zhuǎn)換算法 下面僅以圓心在原點(diǎn)、半徑R為整數(shù)的圓為例，討論圓的生成算法。假設(shè)圓的方程為： X2 + Y2 = R2 若圓心不在原點(diǎn)可以通過坐標(biāo)變換畫出任意位置的圓。2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)374.2.1圓弧掃描算法 X2 + Y2 = R2 Y = Sqrt(R2 - X2)在一定范圍內(nèi)，每給定一X值，可得一Y值。當(dāng)X取整數(shù)時(shí)，Y須取整。缺點(diǎn)：浮點(diǎn)

25、運(yùn)算，開方，取整，不均勻。yx2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)384.2.2 角度DDA法 xn+1 = x n + dx = x n R sin d =x n (y ny 0 )d y n+1 = y n + dy = y n + R cos d =y n + (x nx 0 )d 給定圓上的初始值x1，y1及d值后，即可以增量方式獲得圓周上的坐標(biāo)，然后取整可得象素坐標(biāo)。但要采用浮點(diǎn)運(yùn)算、乘法運(yùn)算、取整運(yùn)算。圓的極坐標(biāo)方程 x = x0 + Rcos y = y0 + Rsin 求微分 dx = Rsin d dy = Rcos d 記 xn+1xn dx yn+1yn dy2022

26、-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)394.2.3 中點(diǎn)畫圓法第二個(gè)8分圓P為當(dāng)前點(diǎn)亮象素，那么，下一個(gè)點(diǎn)亮的象素可能是P1(Xp+1，Yp)或P2(Xp +1，Yp 1)。MP1P2P（Xp ，Yp ）利用圓的對稱性，只須討論1/8圓。XYY=XY=-X2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)40構(gòu)造判別函數(shù)： F（X，Y）=X2 + Y2 - R2 ；若 F（X，Y）= 0 則（X，Y）在圓上； F（X，Y） 0 則（X，Y）在圓外。設(shè)M為P1、P2間的中點(diǎn)，M=(Xp+1,Yp-0.5)MP1P24.2.3 中點(diǎn)畫圓法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)41有如下結(jié)論： F(M) = 0

27、 M在圓外 取P2為此，可采用如下判別式： MP1P2P(xp,yp)4.2.3 中點(diǎn)畫圓法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)42 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - R2 若若d=0, 則則P2 為下一個(gè)象素，那么再下一個(gè)象素為下一個(gè)象素，那么再下一個(gè)象素的判別的判別 式為式為： d1 = F(xp + 2, yp - 1.5)= (xp + 2)2 + (yp - 1.5) 2 - R2 = d + （2xp + 3）+（-2 yp + 2）即即d 的增量為的增量為 2 (xp - yp) +5. d的

28、初值的初值:d0 = F(1, R-0.5)= 1 + (R-0.5)2 - R2 即即：d0 = 1.25 - RMP1P2P2P(xp,yp)4.2.3 中點(diǎn)畫圓法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)44 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; putpixel(x,y,color); while(xy) if(d=0)v putpixel(x,y,color);v if(deltaD0)v deltaHD=2*(deltaD+y)1;v if(deltaHD0) vdeltaDV=2

29、*(deltaD-x)-1; if(deltaDV=0)direction=2;velse direction=3; else direction=2;switch(direction) v case1: x+;v deltaD+=2*x+1;v break;case2: x+; y-; deltaD+=2*(x-y+1); break;case3: y-; deltaD+=(-2*y+1); break; /*switch*/ /*while*/*Bresenham_Ciecle*/HDVDV2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)66Bresenham畫圓算法 現(xiàn)在從(0,R)點(diǎn)開始向右下

30、方逐點(diǎn)來尋找圓弧上的點(diǎn)。如圖中點(diǎn)Pi是已選中的一個(gè)表示圓弧上的點(diǎn)，根據(jù)圓弧的走向，下一個(gè)點(diǎn)應(yīng)該從Hi或者Li中選擇。顯然應(yīng)選離圓弧最近的點(diǎn)作為顯示圓弧的點(diǎn)。PiHiLi假設(shè)圓的半徑為R，顯然，當(dāng) xhi2 + yhi2 -R2 R2 - (xli2 + yli2)時(shí)應(yīng)該取Li。否則取Hi。令di = xhi2 + yhi2 + xli2 + yli2 2R2 顯然， 當(dāng)di 0 時(shí)應(yīng)該取Li。否則，取Hi。2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)67di = (xi+1)2+yi2+(xi+1)2 +(yi-1)2-2R2 =2(xi+1)2 + 2yi2 - 2yi +1- 2R2 當(dāng)當(dāng)di

31、0 -取取Hi ( (xi+1,+1,yi) ) ，則，則PiHiLi 下步就是如何快速的計(jì)算di。設(shè)圖中Pi的坐標(biāo)(xi,yi)則Hi 和Li 的坐標(biāo)為(xi+1,yi)和(xi1,yi-1 )di+1=(xi+1+1)2+yi2+(xi+1+1)2+(yi-1)2- 2R2 =2(xi+1)2+ 2yi2 - 2yi +1 - 2R2 + 4xi + 6 =di + 4xi + 6Bresenham畫圓算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)68當(dāng)當(dāng)d di i00時(shí)時(shí)-取取L Li i(x(xi i1,y1,yi i-1 )-1 ) ，則，則 di+1+1 = ( = (xi +1+

32、1)+1+1)2 2 +( +(yi-1)-1)2 2 + + ( (xi+1+1)+1+1)2 2 +( +(yi-1-1)-1-1)2 2 - -2R2 2 = =di + 4( + 4(xi - - yi)+10 )+10 PiHiLi 易知易知 x0 0=0=0，y0 0= =R, ,x1 1= =x0 0+1+1 因此因此 d0 0=12 2 + +y0 02 2+1+12 2+(+(y0 0-1)-1)2 2 - -2R2 2 = 3 - 2 = 3 - 2y0 0 = 3 - 2 = 3 - 2RBresenham畫圓算法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)69生成圓弧的正負(fù)

33、法 原理： 設(shè)圓的方程為F(x,y)=X2+ Y2- - R2=0; 假設(shè)求得Pi的坐標(biāo)為(xi,yi)；則 當(dāng)Pi在圓內(nèi)時(shí)- F(xi , yi) 向右- 向圓外 當(dāng)Pi在圓外時(shí)- F(xi , yi)0 - 向下- 向圓內(nèi)2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)70即求得Pi點(diǎn)后選擇下一個(gè)象素點(diǎn)Pi+1的規(guī)則為： 當(dāng)F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi; 當(dāng)F(xi,yi) 0 取xi+1 = xi， yi+1 = yi - 1; 這樣用于表示圓弧的點(diǎn)均在圓弧附近，且使F(xi,yi) 時(shí)正時(shí)負(fù)，故稱正負(fù)法。 快速計(jì)算的關(guān)鍵是F(xi,yi) 的計(jì)算，能否采用

34、增量算法？ 生成圓弧的正負(fù)法2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)71v若若F(xF(xi i,y,yi i) ) 已知，計(jì)算已知，計(jì)算F(xF(xi+1i+1,y,yi+1i+1) ) 可分兩種可分兩種情況：情況：v1 1、F(xF(xi i,y,yi i)0- x)0- xi+1i+1 = x = xi i+1+1，y yi+1i+1 = y = yi i; ;v - F(x - F(xi+1i+1,y,yi+1i+1)= (x)= (xi+1 i+1 ) )2 +(y+(yi+1i+1 ) )2 -R-R2v - = (x- = (xi i+1)+1)2+ y+ yi i2 -R-R2

35、 = F(x= F(xi i,y,yi i) +2x) +2xi i +1+1v2 2、 F(xF(xi i,y,yi i) )0- x0- xi+1i+1 = x = xi i，y yi+1i+1 = y = yi i -1;-1;v - F(x - F(xi+1i+1,y,yi+1i+1)= (x)= (xi+1 i+1 ) )2 +(y+(yi+1i+1 ) )2 -R-R2v - = x- = xi i2+(y+(yi i 1)1)2-R-R2 = F(x= F(xi i,y,yi i) - 2y) - 2yi i +1+1v3 3、初始值：略、初始值：略生成圓弧的正負(fù)法2022-7-

36、2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)724.3 橢圓的掃描轉(zhuǎn)換vF(x , y)=b2x2+a2y2-a2b2=0v橢圓的對稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點(diǎn)作為分界點(diǎn).也就是法向量中x 和y 分量相等的點(diǎn).v橢圓上一點(diǎn)處的法向：N(x,y) = Fx i + Fy j = 2b2 x i + 2a2 y j上半部分上半部分下半部分下半部分2022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)73上半部分,法向量的y 分量大。法向量法向量兩分量相等兩分量相等在當(dāng)前中點(diǎn)處，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分分量量比x分量分量大,即： b2 (Xp+1) =0

37、=0，中點(diǎn)在橢圓外，取正下方象素，判別式更新為： d2= =F F(X(Xp+0.5,Y+0.5,Yp-2)=-2)=d2+ +a2 2(3-2Y(3-2Yp) )d2的增量為的增量為a2(3-2Y Yp).4.3 橢圓的掃描轉(zhuǎn)換vd1的初始值：橢圓弧起點(diǎn)為(0，b)；第一個(gè)中點(diǎn)為(1,b-0.5) .初始判別式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)v轉(zhuǎn)入下部分，下一象素可能是正下方或右下方，此時(shí)判別式要初始化。假定上半部分最后一像素為(xp,yp),下一步像素的中點(diǎn)即為: (xp+0.5,yp-1), d20=F(xp+0.5,yp-1)=b2(xp+0.5)2+a

38、2(yp-1)2-a2b2v下半部分弧的終止條件為 y = 02022-7-2西安工程大學(xué)計(jì)算機(jī)圖形學(xué)78程序：MidpointEllipe(a,b, color)int a,b,color; int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); 一、反走樣技術(shù)的定義和概述 前面介紹的各種光柵化算法，除水平或垂直的直線外或多或少會(huì)產(chǎn)生鋸齒或階梯狀，如圖所示。由于直線和多邊形邊界的數(shù)學(xué)描述是連續(xù)的，而在光柵顯示器中，像素點(diǎn)是占有一定面積是離散的。我們把這種用離散量表示連續(xù)量引起的失真稱為走樣(Aliasing)。走樣是數(shù)字化發(fā)展的必然產(chǎn)物。所謂的反走樣(Antialiasing)技術(shù)，就是減緩或者消除走樣效果的技術(shù)。 4.4反走樣技術(shù) 第一類方法是通過提高采樣頻率(提高光柵分辨率)