1、計(jì)算機(jī)圖形學(xué)第3章 基本光柵圖形算法1直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換2圓的掃描轉(zhuǎn)換圓的掃描轉(zhuǎn)換3多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換4區(qū)域填充區(qū)域填充5字符的生成字符的生成6光柵圖形的反走樣算法光柵圖形的反走樣算法22014-2015-1:CG:SCUEC本章內(nèi)容直線的掃描轉(zhuǎn)換生成直線算法的基本要求生成直線算法的基本要求基本增量算法基本增量算法中點(diǎn)法中點(diǎn)法BresenhamBresenham算法算法3直線掃描轉(zhuǎn)換的定義直線掃描轉(zhuǎn)換的定義2014-2015-1:CG:SCUECv 所畫(huà)的直線是離散的像素集合所畫(huà)的直線是離散的像素集合v 只有畫(huà)水平線只有畫(huà)水平線,垂直線垂直線,及正方及正方形對(duì)角線時(shí)形對(duì)

2、角線時(shí),像素點(diǎn)集的位置像素點(diǎn)集的位置才是準(zhǔn)確的才是準(zhǔn)確的A(x1,y1)、B(x2,y2)、v 在計(jì)算機(jī)顯示器上畫(huà)一條直線在計(jì)算機(jī)顯示器上畫(huà)一條直線和在紙上畫(huà)一條直線有什么本和在紙上畫(huà)一條直線有什么本質(zhì)的區(qū)別質(zhì)的區(qū)別? ?v 顯示器是一個(gè)有限的像素矩陣顯示器是一個(gè)有限的像素矩陣4直線掃描轉(zhuǎn)換的定義2014-2015-1:CG:SCUEC直線掃描轉(zhuǎn)換的定義v在計(jì)算機(jī)顯示器上畫(huà)一條直線，只能在顯示器在計(jì)算機(jī)顯示器上畫(huà)一條直線，只能在顯示器所給定的有限個(gè)像素組成的點(diǎn)陣中，選擇能最所給定的有限個(gè)像素組成的點(diǎn)陣中，選擇能最佳地逼近于該直線的一組像素，并對(duì)這些像素佳地逼近于該直線的一組像素，并對(duì)這些像素按

3、指定的屬性進(jìn)行寫(xiě)操作。這就是通常所說(shuō)的按指定的屬性進(jìn)行寫(xiě)操作。這就是通常所說(shuō)的用顯示器繪制直線，即用顯示器繪制直線，即直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換。v直線掃描轉(zhuǎn)換的主要工作：快速找出像素點(diǎn)陣直線掃描轉(zhuǎn)換的主要工作：快速找出像素點(diǎn)陣中距直線最近的網(wǎng)格點(diǎn)，用這些網(wǎng)格點(diǎn)對(duì)應(yīng)的中距直線最近的網(wǎng)格點(diǎn)，用這些網(wǎng)格點(diǎn)對(duì)應(yīng)的像素表示該直線。像素表示該直線。2014-2015-1:CG:SCUEC5v給定一個(gè)寫(xiě)像素函數(shù)給定一個(gè)寫(xiě)像素函數(shù)DrawPixelDrawPixel（x,y,color),x,y,color),能不能直接用數(shù)學(xué)公式生成直線？能不能直接用數(shù)學(xué)公式生成直線？A(x0,y0)B(x1,y1)vo

4、id DirectLine(int x0, int y0, int x1, int y1, int color) int x； float dx, dy, b, k; dx = x1-x0, dy=y1-y0; k=dy/dx, b=y0-k*x0; for (x=x0; x x1; x+) DrawPixel (x, int(k*x+b), color); 生成直線算法的基本要求62014-2015-1:CG:SCUECoxyk1(xi,yi)(xi+1,yi+1)v 數(shù)學(xué)公式生成直線的討論：數(shù)學(xué)公式生成直線的討論： 生成的直線可能不直生成的直線可能不直 算法復(fù)雜度高，運(yùn)算速度慢算法復(fù)雜度高

5、，運(yùn)算速度慢生成直線算法的基本要求7v 生成直線算法的基本要求生成直線算法的基本要求 生成的直線要直生成的直線要直 直線的端點(diǎn)要準(zhǔn)確，保證繪制無(wú)定向性直線的端點(diǎn)要準(zhǔn)確，保證繪制無(wú)定向性 直線的亮度、色澤要均勻，避免在視覺(jué)上造成一段亮直線的亮度、色澤要均勻，避免在視覺(jué)上造成一段亮一段暗的感覺(jué)一段暗的感覺(jué) 畫(huà)線的速度要盡可能的快畫(huà)線的速度要盡可能的快 有可能產(chǎn)生隔行顯示有可能產(chǎn)生隔行顯示2014-2015-1:CG:SCUEC問(wèn)題問(wèn)題直接用直線方程直接用直線方程y=kx+b來(lái)生成直線，之來(lái)生成直線，之所以算法復(fù)雜度高，是因?yàn)樵诘^(guò)程所以算法復(fù)雜度高，是因?yàn)樵诘^(guò)程中每次都要用到浮點(diǎn)數(shù)的乘法運(yùn)算

6、，那中每次都要用到浮點(diǎn)數(shù)的乘法運(yùn)算，那是否可以去掉浮點(diǎn)數(shù)的乘法運(yùn)算呢？是否可以去掉浮點(diǎn)數(shù)的乘法運(yùn)算呢？基本增量算法8v 最基本的增量算法是最基本的增量算法是DDADDA算法算法 數(shù)值微分分析器數(shù)值微分分析器(Digital Differential Analyzer)(Digital Differential Analyzer) DDADDA算法的本質(zhì)是用數(shù)值方法解直線的微分方程算法的本質(zhì)是用數(shù)值方法解直線的微分方程v 基本思想：基本思想：如果在一個(gè)迭代算法中，每一步的如果在一個(gè)迭代算法中，每一步的x值和值和y值都可以由前一步的的值加一個(gè)增量得到，那么這值都可以由前一步的的值加一個(gè)增量得到，那

7、么這種算法就稱(chēng)為增量算法。種算法就稱(chēng)為增量算法。2014-2015-1:CG:SCUEC生成直線的DDA算法v設(shè)直線的起點(diǎn)坐標(biāo)為設(shè)直線的起點(diǎn)坐標(biāo)為(x0 , y0)，終點(diǎn)坐標(biāo)為，終點(diǎn)坐標(biāo)為(x1 , y1)，令令 x = x1 x0， y = y1 - y0，則直線微分方程為，則直線微分方程為:, dxdyxydtdtv該方程的數(shù)值解的遞推公式為該方程的數(shù)值解的遞推公式為xi+1 = xi + x t ( t 表示步長(zhǎng)）表示步長(zhǎng)）yi+1 = yi + y t92014-2015-1:CG:SCUECv如果取 t=1/x，我們有： xi+1 = xi + 1 yi+1 = yi + kv即x方

8、向每次增加1，y方向增加k(直線的斜率)；生成直線的DDA算法void DDALine1(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; x x1, x+) drawpixel (x, int(y+0.5), color); y = y + k; 102014-2015-1:CG:SCUECDDA算法畫(huà)線舉例例：用例：用DDADDA法畫(huà)線法畫(huà)線)2 , 5()0 , 0(10PP0 1 2 3 4 5321Line: P

9、0(0,0)P1(5,2)x y+0.5 int(y+0.5)0 0.5 01 0.4+0.5 0 2 0.8+0.5 1 3 1.2+0.5 1 4 1.6+0.5 2 5 2.0+0.5 2 注：網(wǎng)格點(diǎn)表示象素112014-2015-1:CG:SCUECv 討論：討論： 根直接用數(shù)學(xué)公式畫(huà)直線相比，算法效率有較大提高。根直接用數(shù)學(xué)公式畫(huà)直線相比，算法效率有較大提高。 還是有可能造成隔行顯示還是有可能造成隔行顯示DDA算法的分析oxyoxy(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)122014-2015-1:CG:SCUECv為了解決隔行顯示的問(wèn)題，分成兩種情況

10、考慮：首先為了解決隔行顯示的問(wèn)題，分成兩種情況考慮：首先考慮直線斜率的絕對(duì)值小于考慮直線斜率的絕對(duì)值小于1的情況，這時(shí)的情況，這時(shí)| x| | y| 0，我們?nèi)。覀內(nèi)?t=1/| x|，DDA數(shù)值解的遞推公式為數(shù)值解的遞推公式為: xi+1 = xi + 1， yi+1 = yi + k v其次考慮直線斜率的絕對(duì)值大于其次考慮直線斜率的絕對(duì)值大于1的情況，這時(shí)的情況，這時(shí)0| x| | y|，我們?nèi)。覀內(nèi)?t=1/| y|，DDA數(shù)值解的遞推公式為數(shù)值解的遞推公式為: xi+1 = xi + 1/k， yi+1 = yi + 1 v綜合起來(lái)，綜合起來(lái)， 取步長(zhǎng)取步長(zhǎng) t = min1/|

11、x|,1/| y|即即根據(jù)斜率根據(jù)斜率 k 的偏移程度，決定是以的偏移程度，決定是以 x 為步進(jìn)方向還是以為步進(jìn)方向還是以 y 為步進(jìn)為步進(jìn)方向。然后在相應(yīng)的步進(jìn)方向上，步進(jìn)變量每次增加方向。然后在相應(yīng)的步進(jìn)方向上，步進(jìn)變量每次增加一個(gè)像素，而另一個(gè)相關(guān)坐標(biāo)變量則為一個(gè)像素，而另一個(gè)相關(guān)坐標(biāo)變量則為 yi+1 = yi + k （以（以 x 為步進(jìn)變量為例為步進(jìn)變量為例xi+1 = xi+1）DDA算法的改進(jìn)132014-2015-1:CG:SCUECDDA算法的進(jìn)一步改進(jìn)v 討論：如果直線段的兩個(gè)端點(diǎn)不是整數(shù)怎么辦？討論：如果直線段的兩個(gè)端點(diǎn)不是整數(shù)怎么辦？142014-2015-1:CG:

12、SCUECvoid DDALine (float xs, float ys, float xe, float ye, int color)int n, ix, iy, idx, idy ;int Flag; /插補(bǔ)方向標(biāo)記插補(bǔ)方向標(biāo)記int Length; /插補(bǔ)長(zhǎng)度插補(bǔ)長(zhǎng)度f(wàn)loat x, y, dx, dy;dx = xe - xs;dy = ye - ys;if (fabs(dy) = fabs(dx) /X方向長(zhǎng)，方向長(zhǎng)，|斜率斜率|1Length = abs(Round(ye)-Round(ys);Flag=0;iy = Round(ys); /初始初始Y點(diǎn)點(diǎn)idy = sign(d

13、y); /Y方向單位增量方向單位增量x= xs+dx/dy*(float)(iy)-ys); /初始初始X點(diǎn)修正點(diǎn)修正dx=dx/fabs(dy); /X方向增量方向增量(斜率的倒數(shù)斜率的倒數(shù))if (Flag) /X方向單位增量方向單位增量for (n=0; n= Length; n+) /X方向插補(bǔ)過(guò)程方向插補(bǔ)過(guò)程DrawPixel(ix, Round(y), color);ix+=idx;y+=dy; /End of for /End of ifelse /Y方向斜率增量方向斜率增量for (n=0; n 0, F(x, y) 0, 分別表示點(diǎn)分別表示點(diǎn)(x, y)在直線上、直線上方和直

14、線下方在直線上、直線上方和直線下方( )(1 ,0.5)(1)(0.5)iiiiidFMF xyaxb yc v要判斷點(diǎn)要判斷點(diǎn)M M在直線上，上方還是下方可將在直線上，上方還是下方可將M M代入代入下面的判別式判斷其正負(fù)即可下面的判別式判斷其正負(fù)即可202014-2015-1:CG:SCUECvdi 0，取PB為下一像素vdi = 0，可在兩個(gè)點(diǎn)中任取一個(gè)，約定取下方的點(diǎn)PBMP=(x,y)QPTPBv思考：這樣做，每一個(gè)像素的計(jì)算量是多少？21中點(diǎn)法的具體實(shí)現(xiàn)v答案：每一個(gè)像素的計(jì)算量是4個(gè)加法，兩個(gè)乘法。比DDA算還要壞，“山窮水盡疑無(wú)路了嗎？”2014-2015-1:CG:SCUECv

15、 若若di 0時(shí)，時(shí)，22ddady 當(dāng)當(dāng)d abs(y1-y0) /X方向長(zhǎng)，方向長(zhǎng)，|斜率斜率| x1) /起點(diǎn)在右方，和終點(diǎn)交換起點(diǎn)在右方，和終點(diǎn)交換 x=x0;x0=x1;x1=x;y=y0;y0=y1;y1=y; a = y0 - y1; b = x1 - x0; if (a 0) / 斜率斜率0step =1;d = (a1) + b; /判別式的初始值判別式的初始值dt1 = a =0時(shí)的判別式增量時(shí)的判別式增量dt2 = (a + b) 1; /d時(shí)的判別式增量時(shí)的判別式增量x=x0;y=y0;DrawPixel(x,y,color); /畫(huà)起點(diǎn)畫(huà)起點(diǎn)完整的中點(diǎn)法算法描述29 while(x x1) if ( d 1 if (y0 y1)x=x0;x0=x1;x1=x;y=y0;y0=y1;y1=y; a = x0 - x1; b = y1 - y0; if (a 0) a = -a; step = -1;else step =1;完整的中點(diǎn)法算法描述30d = (a1) + b; /判別式的初始值