計算機圖形學(xué)-第二章

1、計算機圖形學(xué)計算機圖形學(xué)長春師范大學(xué)-數(shù)學(xué)學(xué)院 nenu_ZhangK.2光柵圖形學(xué)光柵圖形學(xué) 直線段的掃描轉(zhuǎn)換算法 圓弧的掃描轉(zhuǎn)換算法 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 字符 裁剪 反走樣 消隱3 什么是光柵圖形學(xué)？ 光柵顯示器 圖形光柵化、 光柵掃描圖形顯示器的構(gòu)成: 幀緩沖存儲器（Frame Buffer)，視頻控制器（Video Controller)，顯示處理器（Display Processor），CRT4較為典型的光柵掃描圖形顯示系統(tǒng)的結(jié)構(gòu) 幀緩沖存儲器：存儲屏幕上像素的顏色值，簡稱幀緩沖器，俗稱顯存。 視頻控制器作用：建立與屏幕像素之間的一一對應(yīng)，負責(zé)刷新。視頻控制器能夠直接存取幀緩

2、存以刷新屏幕。5光柵掃描顯示器的工作原理: 計算機將欲顯示的圖形、圖象轉(zhuǎn)換為位圖，經(jīng)接口電路送入幀緩存；視頻控制器依次掃描幀緩存中的位圖，把位圖轉(zhuǎn)換成亮度或色彩信號來控制電子束的強度；同時光柵掃描電路控制電子束從左到右、從上到下移動。6 光柵顯示器是畫點設(shè)備，可看做是一個點陣單元發(fā)生器（象素矩陣），并可控制每個點陣單元的亮度。顯示器的任務(wù)就是確定最佳逼近圖形的象素集合，并用指定屬性寫象素的過程，這個過程被稱為掃描轉(zhuǎn)換，或光柵化。光柵化將給定直線和其他幾何對象的圖形命令轉(zhuǎn)換為一組與屏幕位置對應(yīng)的離散點。例如：直線的光柵化7 OpenGL中指定的二維世界坐標(biāo)系統(tǒng) gluOrtho2D:設(shè)定一個二維

3、笛卡兒坐標(biāo)系 gluOrtho2D（xmin,xmax,ymin,ymax）;Xmin XmaxYmaxYmin顯示窗口顯示窗口屏幕窗口屏幕窗口8 OpenGL畫點函數(shù)glBegin(GL_POINTS); /變量用來指定要顯示的輸出圖元類型 glVertex*( ); /該函數(shù)要有后綴碼glEnd( ); *函數(shù)后綴碼包括用來指明空間尺寸、用做坐標(biāo)值的數(shù)據(jù)類型和可能的向量形式坐標(biāo)的描述。of419第二章第二章 光柵圖形學(xué)光柵圖形學(xué) 什么是光柵圖形學(xué)？ 光柵顯示器 圖形光柵化、 光柵化圖形的處理 of4110 光柵圖形學(xué)的研究內(nèi)容n直線段的掃描轉(zhuǎn)換算法n圓弧的掃描轉(zhuǎn)換算法n多邊形的掃描轉(zhuǎn)換與區(qū)

4、域填充n字符n裁剪n反走樣n消隱of41112.1 直線段的掃描轉(zhuǎn)換算法直線段的掃描轉(zhuǎn)換算法 直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換: 確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。 三個常用算法：數(shù)值微分法（DDA）中點畫線法Bresenham算法。0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)of41122.1.1 數(shù)值微分?jǐn)?shù)值微分(DDA)法法 基本思想 已知過端點 的直線段L： 直線斜率為 從 的左端點 開始，向 右端點步進。步長=1(個象素)，計算相應(yīng)的y坐標(biāo) ；取象素點(x, round(y)作為當(dāng)前點的坐標(biāo)。0101xxyyk),()

5、,(111000yxPyxPbkxyx0 xxbkxyof4113n作為最底層的光柵圖形算法，在通常的CAD/圖形系統(tǒng)中，會被大量應(yīng)用，因此，哪怕節(jié)約一個加法或減法，也是很了不起的改進。n由此出發(fā)點，導(dǎo)致增量算法的思想。of4114計算當(dāng) 時;即：當(dāng)x每遞增1，y遞增k(即直線斜率)； xkyxkbkxbkxyiiii 111xkyyii1of4115例：畫直線段x int(y+0.5) y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：網(wǎng)格點表示象素0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2 ,

6、5()0 ,0(10PPof4116void 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+) drawpixel (x, int(y+0.5), color); y=y+k; of4117 問題： 當(dāng) k 1時，會如何？of4118注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每增加1, y最多增加1。當(dāng) k 1時，必須把x，y地位互換 k DDA算法采用點斜式，可否采用其他

7、的直線表示方式？of4120基本思想當(dāng)前象素點為(xp, yp) 。下一個象素點為P1 或P2 。設(shè)M=(xp+1, yp+0.5)，為p1與p2之中點，Q為理想直線與x=xp+1垂線的交點。將Q與M的y坐標(biāo)進行比較。n當(dāng)M在Q的下方，則P2 應(yīng)為 下一個象素點；nM在Q的上方，應(yīng)取P1為下一點。P=(xp,yp)QP2P1of4121構(gòu)造判別式:d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 其中a=y0-y1, b=x1-x0, c=x0y1-x1y0當(dāng)d0，M在L(Q點)上方，取右方P1為下一個象素；當(dāng)d=0，選P1或P2均可，約定取P1為下一個象素

8、；of4122但這樣做，每一個象素的計算量是4個加法，兩個乘法。如果也采用增量算法呢？ d是xp, yp的線性函數(shù)，因此可采用增量計算，提高運算效率。of4123 若當(dāng)前象素處于d0情況，則取正右方象素P1 (xp+1, yp), 要判下一個象素位置，應(yīng)計算 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a； 增量為a 若d0時，則取右上方象素P2 (xp+1, yp+1)。要判斷再下一象素，則要計算 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b ；增量為abof4124 至此，至少新算法可以和DDA算法一樣好。 能

9、否再做改進？ 能否實現(xiàn)整數(shù)運算？of4125 畫線從(x0, y0)開始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b =a+0.5b?？梢杂?d代替d來擺脫小數(shù)，提高效率。令 d0=2a+b, d1=2a, d2=2a+2b,我們有如下算法 。of4126void 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; drawpix

10、el(x, y, color); while (xx1) if (d0) x+, y+, d+=d2; else x+, d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */of4127例：用中點畫線法 i xiyid1 0012 10-33 2134 31-15 4250 1 2 3 4 5321)2, 5()0 ,0(10PP5,20110 xxbyya,6)(2,42, 12210badadbadof41282.1.3 Bresenham算法算法 基本思想nDDA算法采用點斜式，中點法采用隱式表示。n中點法可以有整

11、數(shù)算法。n其他表示可以推出整數(shù)算法嗎？of4129n 過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線。按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后根據(jù)誤差項的符號確定該列象素中與此交點最近的象素。ddddof4130設(shè)直線方程為： ，其中k=dy/dx。 因為直線的起始點在象素中心，所以誤差項d的初值d00。X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即ddk。一旦d1，就把它減去1，這樣保證d在0、1之間。n當(dāng)d0.5時，最接近于當(dāng)前象素的右上方象素（ ）n而當(dāng)d0.5時，更接近于右方象素（ ）。為方便計算，令ed-0.5，e的初值為-0.5，增量為k。n當(dāng)e0時，取當(dāng)前象素（xi，y

12、i）的右上方象素（ ）；n而當(dāng)e0時，更接近于右方象素（ ）。kyxxkyyiiiii)(1111,iiyxiiyx,111,iiyxiiyx,1of4131可以改用整數(shù)以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換： 例：Line: P0(0, 0), P1(5,2) k=dy/dx=0.4 x y e 0 0 -0.5 1 0 -0.1 2 1 0.3 3 1 -0.3 4 2 0.1 5 2 -0.5 大于零，大于零，y加加1，小于零，不變，小于零，不變dxee*2 0 1 2 3 4 5321of4132void Bresenhamline (int x0,int y0,i

13、nt 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; of4133 最終，Bresenham算法也是每個象素，需一個整數(shù)算法，其優(yōu)點是可以用于其他二次曲線。 至此，直線光柵化是否終結(jié)？of4134 設(shè)計光柵圖形算法的依據(jù)： 確定最佳逼近圖形的象素集合(尋優(yōu))of4135 算法評價指標(biāo)

14、：n準(zhǔn)確性n高效性of4136直線光柵化總結(jié)直線光柵化總結(jié)畫線方法畫線方法直線方程直線方程計算方法計算方法決策參數(shù)決策參數(shù)數(shù)值微分法（數(shù)值微分法（DDA）y=kx+b增量算法“四舍五入法”中點法中點法ax+by+c=0增量算法中點坐標(biāo)Bresenham算法算法y=kx+b增量算法誤差項of4137新方法：BRDC: binary representation of displacement code for lineMiao LF, Liu XG, Peng QS, Bao HJCOMPUTERS & GRAPHICS-UK 26 (3): 401-408 JUN 2002of4138

15、 其他圖形 of41392.2 圓弧的掃描轉(zhuǎn)換算法圓弧的掃描轉(zhuǎn)換算法 常見的圓of41402.2 圓弧的掃描轉(zhuǎn)換算法圓弧的掃描轉(zhuǎn)換算法 思考？思考？ 圓C,原點為C(x,y),半徑為r 如何進行圓掃描轉(zhuǎn)換？of41412.2 圓弧的掃描轉(zhuǎn)換算法圓弧的掃描轉(zhuǎn)換算法 圓的方程 一般式： 利用方程，沿x軸從xc-r到xc+r以單位步長計算對應(yīng)的y值，從而得到圓周上每點的位置： 222r)()(ccyyxx22)(yxxryccof4142 參數(shù)方程 x=xc+ rcos y= yc+ rsin 以固定角度為步長，利用圓周的 等距點來繪制圓。當(dāng)設(shè)定角度間 隔為1/r時，可獲得較連續(xù)的邊界。 此時繪出的

16、像素位置大約間隔一 個單位。 ycxcr(x,y)of4143 圓的特征圓的特征xy y=x0of4144 圓的特征圓的特征:八對稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個圓弧的象素集 決策參數(shù)？決策參數(shù)？of4145 點與圓的位置關(guān)系 圓函數(shù): f=x2+y2-r2 對于任何一點(x,y),則： 0, (x,y)位于圓邊界外 of4146 決策參數(shù) 當(dāng)前點為xi, 下一個取樣位置xi+1的兩個候選點分別為P1 (xi+1,yi)及P2 (xi+1,yi-1)。圓函數(shù)在取樣候選點的中點M(xi+1,yi-0.5)進行測試： Pk=f(xi+1,yi-0.5)=(xi+1)2+(yi-0.5

17、)2-r2 0, M位于圓邊界外， P1、P2均可P=(xp,yp)P1P2Mof4147 若 Pk =0, 則應(yīng)取P2為下一像素，而且下一象素的判別式為增量為 第 一個象素是（0,r）， 決策參數(shù)Pk的初始值為32px32)5 . 0()2()5 . 0, 2(k222kpppppxPryxyxFP5)(2)5 . 1()2()5 . 1, 2(k222kppppppyxPryxyxFPrrFP25.1)5 .0, 1 (05)(2ppyxkPof4148 注意！n第一象限，圓弧從x=0到x=y，曲線斜率從0變化到-1.x x方向步進方向步進n當(dāng)圓心（xc , yc）不在坐標(biāo)原點時，可以先使

18、用算法計算圓心在（0,0）的圓的像素位置，然后通過將xc加到x,且yc加到y(tǒng)，從而把計算出的每個位置移動到其相應(yīng)的屏幕位置。n算法可實現(xiàn)整數(shù)運算： P0=1-r (r是整數(shù))of4149 中點畫圓算法步驟 1.輸入圓半徑r和圓心（xc , yc），并得到圓周（圓心在原點）上的第一點： （x0, y0）=（0，r） 2.計算決策參數(shù)初始值：P0=1.25-r 3.在每個xi位置（從i=0）開始，完成下列測試： 假如Pk0,下一個點在（ xi+1 , yk ）,且 否則，下一個點在（ xi+1 , yk-1 ）,且 4.確定在其他七個八分圓中的對稱點 5.若原始圓圓心不在原點，則將每個計算出的像素

19、位置（x,y）移動到圓心（xc , yc）的圓路徑上，并畫坐標(biāo)值x=x + xc,y=y + yc 6.重復(fù)步驟3-5，直至xy32kkixPP5)(2kkiiyxPPof4150 例題： 給定圓的圓心在坐標(biāo)原點，半徑r=10，使用中點畫圓算法畫圖初始點：（x0 , y0）=(0,10)決策參數(shù)初始值：P0=1-r=-9決策參數(shù)初始增量：若P00,下一個點在( xi+1 , yk ),且P =2 x0 +3=3 若P0 0下一個點在(xi+1 , yk-1),且 P=2(x0 - y0)+5=-15iPk(xi+1,yi+1)2xi+12yi+1P0-9(1,10)22031-6(2,10)523456of4151關(guān)于y=x對稱關(guān)于y軸對稱關(guān)于x軸對稱of4152算法算法MidPointCircle(int r int color)int x,y; float d; x=0; y=r; d=1.25-r; circlep