計(jì)算機(jī)圖形學(xué)課件

1、像素像素像素（pixels）：圖像的基本光柵（raster）：像素的光分辨光分辨率像素的行列數(shù)，比如像素顏像素顏三原色（紅、綠、蘭）的RGB顏色空RGB顏色空=aR+bG+c彩色CRT顯彩色CRT顯示平板平板顯示器（平板平板顯示器（flat- Plasmapanels優(yōu)勢：無幾何失真、無閃爍、低耗、輻其他顯示設(shè)平其他顯示設(shè)平三三維（IMAX眼三維（IMAX眼 輸入設(shè)輸入設(shè)三維：三維數(shù)字掃描儀、CT（Computedtomography）、（Magneticresonanceimaging）、itron圖形的圖形的光圖形系圖像在圖形系圖像在幀緩沖區(qū)幀緩沖區(qū)（frame圖像顯圖像顯示：填充像如何畫

2、圖如何畫圖考慮：考慮：如何畫一條直圖形的光柵圖形的光柵怎么確定表示圖形的像素反走直線在直線在點(diǎn)陣設(shè)備上的表現(xiàn)形光柵化如何將一光柵化如何將一般圖形顯示為一系列的像素亦稱為掃描轉(zhuǎn)換）系統(tǒng)往系統(tǒng)往某個(gè)位置(x,y)上“寫”一個(gè)write_pixel(x,圖形的光圖形的光柵化：直直線段的掃描轉(zhuǎn)直線的掃描轉(zhuǎn)換確定最近于直線段的掃描轉(zhuǎn)直線的掃描轉(zhuǎn)換確定最近于該直線的組象素，并且按掃描線順序，對這些象進(jìn)行寫操作三個(gè)常用算法直線段的掃描轉(zhuǎn)直線段的掃描轉(zhuǎn)首先考慮端點(diǎn)坐標(biāo)為整數(shù)的m = y =mx + (1) DDA算yzer 數(shù)字(1) DDA算yzer 數(shù)字微分析ymxhdy/dx=m=Dy/Dx=(y2 f

3、or(x=x1;x=x2;write_pixel(x,對于每個(gè)x畫出最接近的整數(shù)(1) DDA算(1) DDA算計(jì)算:1 = = + + = + 當(dāng)1時(shí)1注意上述分析的算法僅適用于m1的情形。在這1.DDA算法：斜率大的1.DDA算法：斜率大的直(1) DDA算void(1) DDA算voidfloatdx, dy,y,dx=x1-x0;dy=y1-y0; k=dy/dx; y=y0;for (x=x0; xx1, (y+0.5), 注意：用( + 0.5)取整的目的是為取離真正交點(diǎn)近的像素網(wǎng)格點(diǎn)作光柵化后的點(diǎn). 比如0.8離1近，(0.8)=0,但(1) DDAx0123450011220)

4、-321012345注(1) DDAx0123450011220)-321012345注：網(wǎng)格點(diǎn)表示象(2中點(diǎn)基:當(dāng)前象素點(diǎn)為(2中點(diǎn)基:當(dāng)前象素點(diǎn)為, 下一個(gè)象素點(diǎn)為或設(shè)為與為理想直線與垂線的交將與的坐標(biāo)進(jìn)行比較當(dāng)在的下方則應(yīng)為下一個(gè)象素點(diǎn)當(dāng)在的上方，應(yīng)取為下一點(diǎn)QP=(xp,yp)(2中點(diǎn) (2中點(diǎn) 對直線段 QP=(xp,yp)其中a=y0-y1b=x1-x0c=x0y1-構(gòu)造判別式d是xpyp。(2)中點(diǎn)增量計(jì) (2)中點(diǎn)增量計(jì) 要判下一個(gè)象素位置，應(yīng)計(jì)算d1=F(xp+2, 增量為若d0時(shí)，則取右上方象素 要判斷再下一象素，則要計(jì)d2=F(xp+2,增量為P=(xp,yp)(2中點(diǎn)畫

5、線從(x0, y(2中點(diǎn)畫線從(x0, y0)開始，dd0=F(x0+1y0+0.5)=F(x0y0)+a+0.5ba+0.5b令d0=2a+bd1=2a,。(2中點(diǎn)voidLine(2中點(diǎn)voidLinea,b,d1,d2,d,x,a=y0-y1,b=x1-x0,d=2*a+b; d1=2*a, d2=2* (a+b);x=x0, y=y0; whileifx+,y+,d+=d2;x+,drawpixel (x, y, /*while/*midLine(2中點(diǎn)a=y0-y1=-d0=2a+b=(2中點(diǎn)a=y0-y1=-d0=2a+b=b=x1-x0=d1=2a=-4,d2=-3-i12345

6、0123400112(3) BresenhamDDA算法中(3) BresenhamDDA算法中每一步需要一次浮點(diǎn)在Bresenham算法中可以不出現(xiàn)任何浮點(diǎn)只考慮0k1（3） Bresenham：過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線按（3） Bresenham：過各行各列象素中心構(gòu)造一組虛擬網(wǎng)格線按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交根據(jù)誤差項(xiàng)的符號確定該列象素中與此交點(diǎn)最近的象dddd（3） Bresenham算:1 設(shè)直線方程為：: = + = + （3） Bresenham算:1 設(shè)直線方程為：: = + = + , 其中為斜因?yàn)橹本€的起始點(diǎn)在象素中心，所以誤差項(xiàng)的初值0

7、= X下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即當(dāng)d0.5時(shí)，最接近于當(dāng)前象素的右上方象素(1,1) = 而當(dāng)d0.5時(shí)，更接近于右方象素( + 1, 為方便計(jì)算，令ed-e的初值為-0.5，增量為k當(dāng)e0時(shí)，取當(dāng)前象素(, )的右上方象素+1), = +1,而當(dāng)e0時(shí)，更接近于右方象素+1,dddd（3） Bresenham(連接兩點(diǎn) （3） Bresenham(連接兩點(diǎn) (其中 例：LineP0(00),x012345y001122e-321（3） Bresenhamvoid Bresenhamline （3） Bresenhamvoid Bresenhamline x,y,dx,fl

8、oatk,dx=x1-x0,dy=y1-y0,e=-0.5,x=x0,for(i=0;idx;drawpixel (x, y, color); ify+,e=e-3.3.如何222假設(shè)圓的方如何222假設(shè)圓的方程為+=YR圓的圓的圓的圓的中點(diǎn)Bresenham算正負(fù)判定中點(diǎn)畫P（Xp ，Yp ）1能是中點(diǎn)畫P（Xp ，Yp ）1能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)M中點(diǎn)畫222R +Y-0 （X，Y中點(diǎn)畫222R +Y-0 （X，Y）F（X，Y）M中點(diǎn)畫有如下結(jié)論F（M）M在圓內(nèi)取F（M）中點(diǎn)畫有如下結(jié)論F（M）M在圓內(nèi)取F（M）= 0 -M在圓外- 取為此，可采用如下判

9、別M中點(diǎn)畫d=F(M) =F(xp +1,-2=(x +2-2+-pp若d0則P1d1=F(xp +2,中點(diǎn)畫d=F(M) =F(xp +1,-2=(x +2-2+-pp若d=0則P2為下一個(gè)象素，那么再下一個(gè)象素d1 =F(xp+2, yp- 222= (xp中點(diǎn)畫若d=0則P2為下一個(gè)象素，那么再下一個(gè)象素d1 =F(xp+2, yp- 222= (xp+ + (yp- -=d + （2xp+ 3）+（-2 即d2xpyp+ d0=F(1, R-22=1 +(R-=1.25 -M中點(diǎn)畫中點(diǎn)畫floatx=0;y=r;d=1.25-if(d取yi=yi-1-1,P=diBresenhamyi

10、=yi-1,4xi-=+ 當(dāng)di0時(shí)-取yi=yi-1-1,P=di +4(xi-1-yi-1)+A應(yīng)取Hi還是取-y2+d=12 12000= =3 - B生成圓弧的正負(fù)222+Y 生成圓弧的正負(fù)222+Y R假設(shè)求得Pi的坐標(biāo)為則當(dāng)Pi在圓內(nèi)時(shí)F(xi,yi)0向下生成圓弧取生成圓弧取當(dāng)F(xi,yi當(dāng)F(xi,yi) =xi+1，yi+1 =-生成圓弧若情況1、F(xi,yi)0=2)2-)-22-R2F(x,y生成圓弧若情況1、F(xi,yi)0=2)2-)-22-R2F(x,y) =yiiiii=2=yi -F(xi,yi)0-)2)2-x2+(y 1)2-R2=F(x,y-iiii

11、i一般曲一般曲線的情況呢?cái)?shù)學(xué)表函數(shù)數(shù)學(xué)表函數(shù)表參數(shù)表曲線的離散：采曲線的離散：采分段線近：多曲線的離散：曲線的離散：采問題近問題近硬件實(shí)畫線硬件實(shí)畫線的方法已經(jīng)由硬件文字的光文字的光柵隱函數(shù)隱函數(shù)表達(dá)的曲線+2= 2 + 2 + = + + = = 2(2 利用區(qū)間算術(shù)和仿射算法繪制隱式曲線曲利用區(qū)間算術(shù)和仿射算法繪制隱式曲線曲利用區(qū)間算術(shù)和仿射算法繪制隱式利用區(qū)間算術(shù)和仿射算法繪制隱式曲線曲隱式曲隱式曲隱式曲隱式曲隱式曲藺宏偉隱式曲藺宏偉等GPU的隱式曲面繪制和網(wǎng)格化J計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 23(5): 763-770.圖形的光圖形的光柵化：多內(nèi)外檢內(nèi)外檢如何決定封閉多邊

12、形的內(nèi)內(nèi)外檢內(nèi)外檢如何決定封閉多邊形的內(nèi)內(nèi)外檢測：奇偶內(nèi)外檢測：奇偶檢也稱為內(nèi)外檢測：奇偶內(nèi)外檢測：奇偶檢奇異情內(nèi)外檢內(nèi)外檢測：奇偶檢內(nèi)外檢內(nèi)外檢測：奇偶檢內(nèi)外檢內(nèi)外檢測：纏擾數(shù)多邊形的掃描轉(zhuǎn)多邊形的掃描轉(zhuǎn)多邊形的填充：決定多邊的像多邊形的掃描轉(zhuǎn)多邊形的掃描轉(zhuǎn)頂點(diǎn)表點(diǎn)陣表多邊形的掃描轉(zhuǎn)換:把多邊形的頂點(diǎn)多邊形的掃描轉(zhuǎn)多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形多邊形的掃描轉(zhuǎn)多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形多邊形的掃描轉(zhuǎn)換：掃描線多邊形的掃描轉(zhuǎn)換：掃描線算基：按掃描線順序，計(jì)算掃描線與多邊形的 對一條掃描線填充過程可以分為四個(gè)步驟（1）求交（2）排（3）配對（4）填多邊形的掃描轉(zhuǎn)多邊

13、形的掃描轉(zhuǎn)換：掃描線多邊形的掃描多邊形的掃描轉(zhuǎn)換：掃描線多邊形的掃描轉(zhuǎn)換：掃描線算CDABxymaxxymaxxymaxx-720708728多邊形的掃描轉(zhuǎn)換：掃描線算CDABxymaxxymaxxymaxx-720708728多邊形的掃描轉(zhuǎn)換：掃描線算數(shù)據(jù)結(jié)構(gòu)：活性邊表把它們按與掃描線交點(diǎn)結(jié)點(diǎn)內(nèi)容：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)：從當(dāng)前掃描線到下一條掃描線間的增多邊形的掃描轉(zhuǎn)換：掃描線算數(shù)據(jù)結(jié)構(gòu)：活性邊表把它們按與掃描線交點(diǎn)結(jié)點(diǎn)內(nèi)容：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)：從當(dāng)前掃描線到下一條掃描線間的增：該邊所交的最高掃描線號CDABxymaxxymaxxymax-720708728多邊形的掃描轉(zhuǎn)換：掃描線算

14、數(shù)據(jù)結(jié)構(gòu)：新邊表點(diǎn)的坐標(biāo)為876543210上圖所示各條掃描線的新邊表533082075-25-7528多邊形的掃描轉(zhuǎn)換：掃描線算數(shù)據(jù)結(jié)構(gòu)：新邊表點(diǎn)的坐標(biāo)為876543210上圖所示各條掃描線的新邊表533082075-25-752869 10 多邊形的掃描轉(zhuǎn)換：掃描線算若已知當(dāng)前掃描線多邊形的掃描轉(zhuǎn)換：掃描線算若已知當(dāng)前掃描線與多邊形某一條邊交點(diǎn)的下一條掃描線與該邊的交點(diǎn)不需重新計(jì)算，只需增加一個(gè)增量設(shè)該邊的方程為： = 若 = 則當(dāng) = 1時(shí)= 1:1 其中，= 為常約定， = 0時(shí)， = 多邊形的掃描轉(zhuǎn)換：掃描多邊形的掃描轉(zhuǎn)換：掃描線算掃描線與多邊形的頂點(diǎn)或邊界相交時(shí)，必須進(jìn)行正確的交點(diǎn)

15、取舍只需檢查交點(diǎn)的相鄰邊的另外兩個(gè)端點(diǎn)的y按這兩個(gè)y值中大于交點(diǎn)y值的個(gè)數(shù)是0,1,213多邊形的掃描轉(zhuǎn)換：掃描線算polyfill for (各條掃描線多邊形的掃描轉(zhuǎn)換：掃描線算polyfill for (各條掃描線) 初始化新邊表頭指針把= 的邊放進(jìn)邊表yfor (各條掃描線i多邊形的掃描轉(zhuǎn)換：掃描線算把新邊表NET i 中的邊結(jié)點(diǎn)用 (x,y)，用多邊形的掃描轉(zhuǎn)換：掃描線算把新邊表NET i 中的邊結(jié)點(diǎn)用 (x,y)，用(x, y, 遍歷AET表，把i i 結(jié)點(diǎn)的x值遞增把/* 基：經(jīng)過的像素打上標(biāo)志基：經(jīng)過的像素打上標(biāo)志 void edgemark_fill(polydef,對多邊形i

16、nside=void edgemark_fill(polydef,對多邊形inside=每條邊進(jìn)行直線掃描轉(zhuǎn)換；)(每條與多邊形polydef相交的掃描線forxif(象素 x 被打上邊標(biāo)志) inside(inside);if(inside！= FALSE) drawpixel(x,y,color);elsedrawpixel(x,y,用實(shí)現(xiàn)時(shí)，掃描線算用實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)法的執(zhí)行速度幾乎相同但由于邊界標(biāo)志算法不邊表及對它進(jìn)行排序，所以邊界標(biāo)志算法更區(qū)域填充算區(qū)域區(qū)域填充算區(qū)域邊界向連通區(qū)域和向連通區(qū)域區(qū)域填充區(qū)域填充算法要求區(qū)域是連通區(qū)域填充算4向連通區(qū)域和8向連通區(qū)域表示內(nèi)區(qū)域填充算4向連通區(qū)域和8向連通區(qū)域表示內(nèi)表示邊界區(qū)域填充算法如果已知位于多邊區(qū)域填充算法如果已知位于多邊點(diǎn)，那么可以遞歸填（WHITE）的一把多邊轉(zhuǎn)化要填充的顏色內(nèi)點(diǎn)表示的4連通區(qū)域的遞內(nèi)點(diǎn)表示的4連通區(qū)域的遞歸填充算法void區(qū)域填填邊界表示的4連通區(qū)域的遞歸填充算法void區(qū)域填填邊界表示的4連通區(qū)域的遞歸填充算法voidif(color!=newcolor&BoundaryFill4(x,y-1,boundarycolor,newcolor); Bounda