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

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

3、指定的屬性進行寫操作。這就是通常所說的按指定的屬性進行寫操作。這就是通常所說的用顯示器繪制直線，即用顯示器繪制直線，即直線的掃描轉換直線的掃描轉換。v直線掃描轉換的主要工作：快速找出像素點陣直線掃描轉換的主要工作：快速找出像素點陣中距直線最近的網格點，用這些網格點對應的中距直線最近的網格點，用這些網格點對應的像素表示該直線。像素表示該直線。2014-2015-1:CG:SCUEC5v給定一個寫像素函數給定一個寫像素函數DrawPixelDrawPixel（x,y,color),x,y,color),能不能直接用數學公式生成直線？能不能直接用數學公式生成直線？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 數學公式生成直線的討論：數學公式生成直線的討論： 生成的直線可能不直生成的直線可能不直 算法復雜度高，運算速度慢算法復雜度高

5、，運算速度慢生成直線算法的基本要求7v 生成直線算法的基本要求生成直線算法的基本要求 生成的直線要直生成的直線要直 直線的端點要準確，保證繪制無定向性直線的端點要準確，保證繪制無定向性 直線的亮度、色澤要均勻，避免在視覺上造成一段亮直線的亮度、色澤要均勻，避免在視覺上造成一段亮一段暗的感覺一段暗的感覺 畫線的速度要盡可能的快畫線的速度要盡可能的快 有可能產生隔行顯示有可能產生隔行顯示2014-2015-1:CG:SCUEC問題問題直接用直線方程直接用直線方程y=kx+b來生成直線，之來生成直線，之所以算法復雜度高，是因為在迭代過程所以算法復雜度高，是因為在迭代過程中每次都要用到浮點數的乘法運算

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

7、么這種算法就稱為增量算法。種算法就稱為增量算法。2014-2015-1:CG:SCUEC生成直線的DDA算法v設直線的起點坐標為設直線的起點坐標為(x0 , y0)，終點坐標為，終點坐標為(x1 , y1)，令令 x = x1 x0， y = y1 - y0，則直線微分方程為，則直線微分方程為:, dxdyxydtdtv該方程的數值解的遞推公式為該方程的數值解的遞推公式為xi+1 = xi + x t ( t 表示步長）表示步長）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算法畫線舉例例：用例：用DDADDA法畫線法畫線)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 注：網格點表示象素112014-2015-1:CG:SCUECv 討論：討論： 根直接用數學公式畫直線相比，算法效率有較大提高。根直接用數學公式畫直線相比，算法效率有較大提高。 還是有可能造成隔行顯示還是有可能造成隔行顯示DDA算法的分析oxyoxy(xi,yi)(xi+1,yi+1)(xi,yi)(xi+1,yi+1)122014-2015-1:CG:SCUECv為了解決隔行顯示的問題，分成兩種情況

10、考慮：首先為了解決隔行顯示的問題，分成兩種情況考慮：首先考慮直線斜率的絕對值小于考慮直線斜率的絕對值小于1的情況，這時的情況，這時| x| | y| 0，我們取，我們取 t=1/| x|，DDA數值解的遞推公式為數值解的遞推公式為: xi+1 = xi + 1， yi+1 = yi + k v其次考慮直線斜率的絕對值大于其次考慮直線斜率的絕對值大于1的情況，這時的情況，這時0| x| | y|，我們取，我們取 t=1/| y|，DDA數值解的遞推公式為數值解的遞推公式為: xi+1 = xi + 1/k， yi+1 = yi + 1 v綜合起來，綜合起來， 取步長取步長 t = min1/|

11、x|,1/| y|即即根據斜率根據斜率 k 的偏移程度，決定是以的偏移程度，決定是以 x 為步進方向還是以為步進方向還是以 y 為步進為步進方向。然后在相應的步進方向上，步進變量每次增加方向。然后在相應的步進方向上，步進變量每次增加一個像素，而另一個相關坐標變量則為一個像素，而另一個相關坐標變量則為 yi+1 = yi + k （以（以 x 為步進變量為例為步進變量為例xi+1 = xi+1）DDA算法的改進132014-2015-1:CG:SCUECDDA算法的進一步改進v 討論：如果直線段的兩個端點不是整數怎么辦？討論：如果直線段的兩個端點不是整數怎么辦？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; /插補方向標記插補方向標記int Length; /插補長度插補長度float x, y, dx, dy;dx = xe - xs;dy = ye - ys;if (fabs(dy) = fabs(dx) /X方向長，方向長，|斜率斜率|1Length = abs(Round(ye)-Round(ys);Flag=0;iy = Round(ys); /初始初始Y點點idy = sign(d

13、y); /Y方向單位增量方向單位增量x= xs+dx/dy*(float)(iy)-ys); /初始初始X點修正點修正dx=dx/fabs(dy); /X方向增量方向增量(斜率的倒數斜率的倒數)if (Flag) /X方向單位增量方向單位增量for (n=0; n= Length; n+) /X方向插補過程方向插補過程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, 分別表示點分別表示點(x, y)在直線上、直線上方和直

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

15、 若若di 0時，時，22ddady 當當d abs(y1-y0) /X方向長，方向長，|斜率斜率| x1) /起點在右方，和終點交換起點在右方，和終點交換 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時的判別式增量時的判別式增量dt2 = (a + b) 1; /d時的判別式增量時的判別式增量x=x0;y=y0;DrawPixel(x,y,color); /畫起點畫起點完整的中點法算法描述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;完整的中點法算法描述30d = (a1) + b; /判別式的初始值