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

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

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

3、笛卡兒坐標(biāo)系 gluOrtho2D（xmin,xmax,ymin,ymax）;Xmin XmaxYmaxYmin顯示窗口顯示窗口屏幕窗口屏幕窗口8 OpenGL畫點(diǎn)函數(shù)glBegin(GL_POINTS); /變量用來(lái)指定要顯示的輸出圖元類型 glVertex*( ); /該函數(shù)要有后綴碼glEnd( ); *函數(shù)后綴碼包括用來(lái)指明空間尺寸、用做坐標(biāo)值的數(shù)據(jù)類型和可能的向量形式坐標(biāo)的描述。of419第二章第二章 光柵圖形學(xué)光柵圖形學(xué) 什么是光柵圖形學(xué)？ 光柵顯示器 圖形光柵化、 光柵化圖形的處理 of4110 光柵圖形學(xué)的研究?jī)?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)換: 確定最佳逼近于該直線的一組象素，并且按掃描線順序，對(duì)這些象素進(jìn)行寫操作。 三個(gè)常用算法：數(shù)值微分法（DDA）中點(diǎn)畫線法Bresenham算法。0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)of41122.1.1 數(shù)值微分?jǐn)?shù)值微分(DDA)法法 基本思想 已知過(guò)端點(diǎn) 的直線段L： 直線斜率為 從 的左端點(diǎn) 開始，向 右端點(diǎn)步進(jìn)。步長(zhǎng)=1(個(gè)象素)，計(jì)算相應(yīng)的y坐標(biāo) ；取象素點(diǎn)(x, round(y)作為當(dāng)前點(diǎn)的坐標(biāo)。0101xxyyk),()

5、,(111000yxPyxPbkxyx0 xxbkxyof4113n作為最底層的光柵圖形算法，在通常的CAD/圖形系統(tǒng)中，會(huì)被大量應(yīng)用，因此，哪怕節(jié)約一個(gè)加法或減法，也是很了不起的改進(jìn)。n由此出發(fā)點(diǎn)，導(dǎo)致增量算法的思想。of4114計(jì)算當(dāng) 時(shí);即：當(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)格點(diǎn)表示象素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 問(wèn)題： 當(dāng) k 1時(shí)，會(huì)如何？of4118注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每增加1, y最多增加1。當(dāng) k 1時(shí)，必須把x，y地位互換 k DDA算法采用點(diǎn)斜式，可否采用其他

7、的直線表示方式？of4120基本思想當(dāng)前象素點(diǎn)為(xp, yp) 。下一個(gè)象素點(diǎn)為P1 或P2 。設(shè)M=(xp+1, yp+0.5)，為p1與p2之中點(diǎn)，Q為理想直線與x=xp+1垂線的交點(diǎn)。將Q與M的y坐標(biāo)進(jìn)行比較。n當(dāng)M在Q的下方，則P2 應(yīng)為 下一個(gè)象素點(diǎn)；nM在Q的上方，應(yīng)取P1為下一點(diǎn)。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點(diǎn))上方，取右方P1為下一個(gè)象素；當(dāng)d=0，選P1或P2均可，約定取P1為下一個(gè)象素

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

9、否再做改進(jìn)？ 能否實(shí)現(xiàn)整數(shù)運(yùn)算？of4125 畫線從(x0, y0)開始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b =a+0.5b?？梢杂?d代替d來(lái)擺脫小數(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例：用中點(diǎn)畫線法 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算法采用點(diǎn)斜式，中點(diǎn)法采用隱式表示。n中點(diǎn)法可以有整

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

12、i）的右上方象素（ ）；n而當(dāng)e0時(shí)，更接近于右方象素（ ）。kyxxkyyiiiii)(1111,iiyxiiyx,111,iiyxiiyx,1of4131可以改用整數(shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換： 例：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算法也是每個(gè)象素，需一個(gè)整數(shù)算法，其優(yōu)點(diǎn)是可以用于其他二次曲線。 至此，直線光柵化是否終結(jié)？of4134 設(shè)計(jì)光柵圖形算法的依據(jù)： 確定最佳逼近圖形的象素集合(尋優(yōu))of4135 算法評(píng)價(jià)指標(biāo)

14、：n準(zhǔn)確性n高效性of4136直線光柵化總結(jié)直線光柵化總結(jié)畫線方法畫線方法直線方程直線方程計(jì)算方法計(jì)算方法決策參數(shù)決策參數(shù)數(shù)值微分法（數(shù)值微分法（DDA）y=kx+b增量算法“四舍五入法”中點(diǎn)法中點(diǎn)法ax+by+c=0增量算法中點(diǎn)坐標(biāo)Bresenham算法算法y=kx+b增量算法誤差項(xiàng)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,原點(diǎn)為C(x,y),半徑為r 如何進(jìn)行圓掃描轉(zhuǎn)換？of41412.2 圓弧的掃描轉(zhuǎn)換算法圓弧的掃描轉(zhuǎn)換算法 圓的方程 一般式： 利用方程，沿x軸從xc-r到xc+r以單位步長(zhǎng)計(jì)算對(duì)應(yīng)的y值，從而得到圓周上每點(diǎn)的位置： 222r)()(ccyyxx22)(yxxryccof4142 參數(shù)方程 x=xc+ rcos y= yc+ rsin 以固定角度為步長(zhǎng)，利用圓周的 等距點(diǎn)來(lái)繪制圓。當(dāng)設(shè)定角度間 隔為1/r時(shí)，可獲得較連續(xù)的邊界。 此時(shí)繪出的

16、像素位置大約間隔一 個(gè)單位。 ycxcr(x,y)of4143 圓的特征圓的特征xy y=x0of4144 圓的特征圓的特征:八對(duì)稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個(gè)圓弧的象素集 決策參數(shù)？決策參數(shù)？of4145 點(diǎn)與圓的位置關(guān)系 圓函數(shù): f=x2+y2-r2 對(duì)于任何一點(diǎn)(x,y),則： 0, (x,y)位于圓邊界外 of4146 決策參數(shù) 當(dāng)前點(diǎn)為xi, 下一個(gè)取樣位置xi+1的兩個(gè)候選點(diǎn)分別為P1 (xi+1,yi)及P2 (xi+1,yi-1)。圓函數(shù)在取樣候選點(diǎn)的中點(diǎn)M(xi+1,yi-0.5)進(jìn)行測(cè)試： 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為下一像素，而且下一象素的判別式為增量為 第 一個(gè)象素是（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方向步進(jìn)方向步進(jìn)n當(dāng)圓心（xc , yc）不在坐標(biāo)原點(diǎn)時(shí)，可以先使

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

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