圖形學(xué)-光柵化算法

1、1.整體介紹2.建模（圖形描述）3.繪制(光柵化算法)4.光照模型內(nèi)容提要直線光柵化算法 圓光柵化算法 多邊形的填充9.1 直線光柵化算法假設(shè)整型坐標(biāo)系，直線段斜率0m1對(duì)m1，x、y互換基本原理確定最佳逼近于該直線的一組象素按掃描線順序，對(duì)這些象素進(jìn)行寫操作9.1 直線光柵化算法已知線段端點(diǎn)：P0(x0,y0), P1(x1,y1)直線方程 y=k(x-x0)+y0浮點(diǎn)數(shù)取整 : yi=round(yi)=(int)(yi+0.5)用到浮點(diǎn)數(shù)的乘法、加法和取整運(yùn)算9.1.1 DDA算法 數(shù)值微分分析（Digital Differential Analyzer，DDA）是一種增量算法。其實(shí)質(zhì)是

2、用數(shù)值方法解微分方程，通過同時(shí)對(duì)x和y各增加一個(gè)小增量，計(jì)算下一步的x、y值。9.1.1 DDA算法已知一條直線段L（P1, P2）,其端點(diǎn)坐標(biāo)分別為：P1 (x1, y1), P2(x2, y2)。直線段所在的直線的斜率為：直線方程為則9.1.1 DDA算法因光柵單位為1， 可以采用每次x方向增加1， y方向增加k的辦法得到下一個(gè)直線點(diǎn)。9.1.1 DDA算法void Line ( /設(shè)0k1,xsxe int xs,ys;/左端點(diǎn) int xe,ye; /右端點(diǎn) int value) /賦給線上的像素屬性值 int x; /x以步長(zhǎng)為單位從xs增長(zhǎng)到xe double dx =xe-xs;

3、 double dy =ye-ys; double k =dy/dx; / 直線之斜率k double y =ys; for (x=xs; x=xe; x+) WritePixel(x,Round(y),value); /像素屬性值value y+=k; / y移動(dòng)步長(zhǎng)是斜率k /9.1.1 DDA算法例：用DDA方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。x round(y) y(yi+k)0 0 01 0 0.42 1 0.83 1 1.24 2 1.65 2 2.09.1.2 中點(diǎn)畫線法基本原理 假定直線斜率k在0-1之間，當(dāng)前象素點(diǎn)為（xp,yp），則下一個(gè)象素點(diǎn)有兩種

4、可選擇點(diǎn)P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點(diǎn)（xp+1,yp+0.5）稱為M，Q為理想直線與x=xp+1垂線的交點(diǎn)。當(dāng)M在Q的下方時(shí)，則取P2應(yīng)為下一個(gè)象素點(diǎn)；當(dāng)M在Q的上方時(shí)，則取P1為下一個(gè)象素點(diǎn)。M9.1.2 中點(diǎn)畫線法問題：判斷距離理想直線最近的下一個(gè)象素點(diǎn)已知：線段兩端點(diǎn)(x0,y0)，(x1,y1)直線方程：F(x,y)=ax+by+c=0a=y0-y1b=x1-x0c=x0y1-x1y0M如何判斷M點(diǎn)在Q點(diǎn)上方還是在Q點(diǎn)下方？9.1.2 中點(diǎn)畫線法構(gòu)造判別式： d=F(M)=F(Xp+1,Yp+0.5)由d0，d0可判定下一個(gè)象素當(dāng)d0時(shí)，M在L

5、(Q點(diǎn))上方，取P1為下一個(gè)象素；當(dāng)d=0時(shí)，選P1或P2均可，約定取P1為下一個(gè)象素；M9.1.2 中點(diǎn)畫線法MP1P2P(Xp+1,Yp+0.5)d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c9.1.2 中點(diǎn)畫線法若d0，中點(diǎn)M在直線上方，取正右方象素P1 (Xp+1,Yp)下一個(gè)象素的判別式為： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d + a 增量為a若d0，中點(diǎn)M在直線下方，取右上方象素P2 (Xp+1,Yp+1)再下一個(gè)象素的判別式為： d2=F(Xp+1)+1,(Yp+1)+0.5) =a(Xp

6、+2)+b(Yp+1.5)+c =d + a+b 增量為a+bMP1P2MP1P29.1.2 中點(diǎn)畫線法d的初始值d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5b =a+0.5bd的增量都是整數(shù)用2d代替d：d0=2a+b=a+a+b d1=2a d2=2(a+b)因(X0,Y0)在直線上，所以F(X0,Y0)=09.1.2 中點(diǎn)畫線法void 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；d

7、2=2* (a+b)； x=x0；y=y0； drawpixel(x, y, color); while (xx1) if (d0) x+；y+； d+=d2; else x+； d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */9.1.2 中點(diǎn)畫線法舉例：用中點(diǎn)畫線方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。 a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 x y d 0 0 1 1 0 -32 1 3 3 1 -1 2 5 2 19.

8、1.3 Bresenham算法使用最廣泛與中點(diǎn)畫線法的思想類似由誤差項(xiàng)符號(hào)決定下一個(gè)象素取正右方像素還是右上方像素9.1.3 Bresenham算法基本思想比較從理想直線到位于直線上方的像素的距離d2和相鄰的位于直線下方的像素的距離d1根據(jù)距離誤差項(xiàng)的符號(hào)確定與理想直線最近的象素9.1.3 Bresenham算法x方向遞增一個(gè)單位y方向走步與否取決于d1-d2的值取決于誤差e值的大小誤差判斷當(dāng)e0.5時(shí)，最接近P2(xi+1,yi+1), y方向走一步當(dāng)e0.5時(shí)，最接近 P1(xi+1,yi),y方向不走步初值：e0= y/ xeP1P2PeeP1P2Pe9.1.3 Bresenham算法為

9、方便與0比較，設(shè)e=e-0.5當(dāng)e0時(shí)，最接近P2(xi+1,yi+1), y方向走一步當(dāng)e0時(shí)，最接近P1(xi+1,yi), y 方向不走步e0=y/ x-0.5eP1P2PeeP1P2Pe9.1.3 Bresenham算法設(shè)e=e2x，不影響判斷的準(zhǔn)確性當(dāng)e0時(shí)，最接近P2(xi+1,yi+1), y方向走一步當(dāng)e0時(shí)，最接近P1(xi+1,yi), y 方向不走步e0=2y - xeP1P2PeeP1P2Pe9.1.3 Bresenham算法下一步誤差的計(jì)算當(dāng)e0時(shí)，y方向走一步 e=2y/ x - 1 e=e + 2y - 2x當(dāng)e0時(shí)，y方向不走步 e=2y/ x e=e + 2y

10、eP1P2PeeP1P2Pe9.1.3 Bresenham算法9.1.3 Bresenham算法例：用Bresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。 xye00-1031-3112-52-19.1.3 Bresenham算法優(yōu)點(diǎn)整數(shù)運(yùn)算，速度快精度高乘2運(yùn)算可用移位實(shí)現(xiàn)，適于硬件實(shí)現(xiàn)9.1.3 Bresenham算法 已知直線段起點(diǎn)(0, 0)，終點(diǎn)(8,6)，利用Bresenham算法和中點(diǎn)畫線算法生成此直線段，寫出生成過程中坐標(biāo)點(diǎn)及誤差e的變化情況,并在下面的方格中，標(biāo)出直線上各點(diǎn) 9.2 圓的光柵化算法圓的八對(duì)稱性 圓心位于原點(diǎn)的圓有四條對(duì)稱軸x=0,y=

11、0,x=y和x=-y。若已知圓弧上一點(diǎn)(x,y),可以得到其關(guān)于四條對(duì)稱軸的其它7個(gè)點(diǎn)，這種性質(zhì)稱為圓的八對(duì)稱性。 yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR9.2.1 簡(jiǎn)單畫圓法假設(shè)圓心在原點(diǎn) x2+y2=R2 圓的八對(duì)稱性只考慮第二個(gè)八分圓For(x=0;x=R/ )yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR9.2.1 簡(jiǎn)單畫圓法void CirclePoints(int x,int y,int color) drawpixel(x,y,color); drawpix

12、el(y,x,color); drawpixel(-x,y,color); drawpixel(y,-x,color); drawpixel(x,-y,color); drawpixel(-y,x,color); drawpixel(-x,-y,color); drawpixel(-y,-x,color); 9.2.1 簡(jiǎn)單畫圓法兩種直接離散生成方法離散點(diǎn)開方運(yùn)算離散角度三角函數(shù)運(yùn)算缺點(diǎn)：計(jì)算量大所畫像素位置間的間距不一致 9.2.2 中點(diǎn)畫圓法F(X,Y)=X2+Y2-R2=0中點(diǎn) M=(Xp+1,Yp-0.5)當(dāng)d0時(shí)，M在圓內(nèi)，P1距離圓弧近，取P1當(dāng)d0時(shí)，M在圓外，P2距離圓弧近，取

13、P29.2.2 中點(diǎn)畫圓法 若 d=0, 取P2為下一象素，再下一象素的判別式為 初始象素是（0,R），判別式d的初值為: d0=F(1,R-0.5)=1.25-RP1(Xp+1,Yp)P2(Xp+1,Yp-1)使用e=d-0.25代替d, e0=1-R9.2.2 中點(diǎn)畫圓法輸入圓的半徑R和圓心(xc,yc),先計(jì)算以原點(diǎn)為圓心，R為半徑的圓周上的點(diǎn)，令初始點(diǎn)為(x0,y0)=(0,R)設(shè)置初始決策參數(shù)d0=1-R在每一個(gè)xn（從n=0開始）的位置，進(jìn)行下列檢測(cè)：如果 dn=y為止9.2.2 中點(diǎn)畫圓法MidPointCircle(int r int color) int x,y; float

14、 d; x=0; y=r; d=1-r; circlepoints (x,y,color); while(x=y) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; circlepoints (x,y,color); R=5xyd05-415-1254343436MidPointCircle(int r int color) int x,y; float d; x=0; y=r; d=1-r; circlepoints (x,y,color); while(xy) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; ci

15、rclepoints (x,y,color); 9.2.3 Bresenham畫圓法順時(shí)針畫第一四分圓，下一步選擇哪個(gè)點(diǎn)？基本思想：通過比較像素與圓的距離平方來避免開方運(yùn)算下一像素有3種可能的選擇mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2 +(yi-1)2-R2 |選擇像素的原則使其與實(shí)際圓弧的距離平方 達(dá)到最小(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)9.2.3 Bresenham畫圓法圓弧與點(diǎn)(xi,yi)附近光柵網(wǎng)格的相交關(guān)系有5種右下角像素D (xi+1,yi-1)與實(shí)際圓弧的近似程度i=(

16、xi+1)2+(yi-1)2-R2當(dāng)i0時(shí)，D在圓外，當(dāng)i=0時(shí)，D在圓上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)9.2.3 Bresenham畫圓法當(dāng)i0時(shí)，D在圓內(nèi)， 情形，選mH ，mD 中最小者d=mH - mD =|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2| =(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2 =2 (i+yi)-1若d0，則選D若d=0，則選H情形也適用9.2.3 Bresenham畫圓法當(dāng)i0時(shí)，D在圓外， 情形，選mv ，mD 中最小者d=mD - mV =|(x

17、i+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1若d0，則選V若d=0，則選D情形也適用9.2.3 Bresenham畫圓法當(dāng)i=0時(shí)，D在圓上，按d判別，有d0，應(yīng)選D按d判別，有d0，應(yīng)選D9.2.3 Bresenham畫圓法當(dāng)i0，選D當(dāng)i0時(shí),若d 0，選D 若d0，選V當(dāng)i=0時(shí)，選D9.2.3 Bresenham畫圓法判別式的遞推關(guān)系當(dāng)取H(xi+1,yi)時(shí)i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1當(dāng)取V(xi,yi-1)時(shí)i

18、+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1當(dāng)取D(xi+1,yi-1)時(shí)i+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+29.2.3 Bresenham畫圓法9.3 多邊形填充算法 所謂填充算法就是如何用顏色或圖案來填充一個(gè)任意多邊形。 掃描線填充算法 邊填充算法 種子填充算法 求出一根掃描線與多邊形各邊的交點(diǎn)： 對(duì)求得的交點(diǎn)進(jìn)行排序： 奇偶配對(duì)求出掃描線與多邊形的相交區(qū)間： 對(duì)這些相交區(qū)間填色。掃描線的連貫性圖形的空間連貫性I4, I3, I2, I1I1, I2, I3, I4(I1, I2), (I3, I4)9.

19、3.1 掃描線填充算法 求出一根掃描線與多邊形各邊的交點(diǎn)： 對(duì)求得的交點(diǎn)進(jìn)行排序： 奇偶配對(duì)求出掃描線與多邊形的相交區(qū)間： 對(duì)這些相交區(qū)間填色。012345671234567yx88910掃描線5P4P1P2P3P5掃描線2I1I2I3I4掃描線的連貫性圖形的空間連貫性I4, I3, I2, I1I1, I2, I3, I4(I1, I2), (I3, I4)9.3.1 掃描線填充算法9.3.1 掃描線填充算法-填充擴(kuò)大化解決方法：取中心掃描線y+0.5檢查交點(diǎn)右方像素的中心是否落在區(qū)間內(nèi) xlx+0.5xr9.3.1 掃描線填充算法-頂點(diǎn)交點(diǎn)計(jì)數(shù) 檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值，按這兩

20、個(gè)y值中大于頂點(diǎn)y值的個(gè)數(shù)是0、1、2來決定交點(diǎn)是計(jì)0次、1次還是2次。543210P1P2P3P4I1I2I3I4P5掃描線5掃描線4掃描線3掃描線2掃描線1I5I6計(jì)數(shù)0次計(jì)數(shù)1次計(jì)數(shù)2次9.3.1 有序邊表填充算法活性邊表的建立結(jié)點(diǎn)信息x：當(dāng)前掃描線與邊的交點(diǎn)x：從當(dāng)前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線號(hào)x =1/k活性邊表的更新節(jié)點(diǎn)更新新邊插入舊邊刪除9.3.1有序邊表填充算法結(jié)點(diǎn)信息x0：掃描線與邊的初始交點(diǎn)x：從當(dāng)前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線號(hào)對(duì)每條掃描線建立一個(gè)新邊表9.3.1有序邊表填充算法結(jié)點(diǎn)信息x0：掃描線與邊的初

21、始交點(diǎn)x：從當(dāng)前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線號(hào)對(duì)每條掃描線建立一個(gè)新邊表9.3.1有序邊表填充算法新邊表8.57.56.55.54.53.52.51.50.5528.5-1.5711082072-32.533P4P5P5P6P3P4P6P1P1P2P2P3yx0123456789101112345678P6P4P1P5P2P32-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5528.P4P51108P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108P3P43.5

22、-1.57P5P6207.P6P1y=6.59.3.1有序邊表填充算法活動(dòng)邊表的建立5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5從新邊表中取出與掃描線y=1.5相交的初始邊排序放入活性邊表中，填充交點(diǎn)之間的區(qū)域更新邊表，刪除P1P2，插入新邊P6P1，填充交點(diǎn)之間的區(qū)域更新邊表，刪除P2P3，插入新邊P3P4，填充交點(diǎn)之間的區(qū)域9.3.1有序邊表填充算法528.P4P51108P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108P3P43.5-1.57P5P6207.P6P1y=6.592

23、8.P4P51108P3P4y=7.5更新邊表，插入新邊P5P6和P4P5，填充兩對(duì)交點(diǎn)之間的區(qū)域更新邊表，填充兩對(duì)交點(diǎn)之間的區(qū)域更新邊表，刪除P6P1和P5P6，填充交點(diǎn)之間的區(qū)域更新邊表，刪除P4P5和P3P4，活動(dòng)邊表為空，沒有新邊，填充算法結(jié)束9.3.1有序邊表填充算法步驟1、 建立NET表；2、將掃描線縱坐標(biāo)y的初值置為NET中非空元素的最小序號(hào)3、置AET為空；4、執(zhí)行下列步驟直至NET和AEL都為空4.1、如NET中的第y類非空，則將其中的所有邊取出并插入 AEL中；4.2、如果有新邊插入AEL，則對(duì)AEL中各邊排序；4.3、對(duì)AEL中的邊兩兩配對(duì)，獲得有效填充區(qū)段，再填充4.4

24、、將當(dāng)前掃描線縱坐標(biāo)y值遞增1；4.5、將AEL中滿足yymax邊刪去4.6、對(duì)AEL中剩下的每一條邊的x遞增 x，即x = x+ x9.3.1有序邊表填充算法優(yōu)點(diǎn)：對(duì)每個(gè)像素只訪問一次與設(shè)備無(wú)關(guān)缺點(diǎn)：數(shù)據(jù)結(jié)構(gòu)復(fù)雜只適合軟件實(shí)現(xiàn)9.3.2 邊填充算法9.3.2 邊填充算法優(yōu)點(diǎn)：最適合于有幀緩存的顯示器可按任意順序處理多邊形的邊僅訪問與該邊有交點(diǎn)的掃描線上右方的像素，算法簡(jiǎn)單缺點(diǎn)：對(duì)復(fù)雜圖形，每一像素可能被訪問多次，輸入/輸出量大圖形輸出不能與掃描同步進(jìn)行，只有全部畫完才能打印9.3.3 種子填充算法假設(shè)多邊形區(qū)域內(nèi)至少有一個(gè)像素已知區(qū)域定義法Interior-definedBoundary-d

25、efinedFlood-fill algorithmBoundary-fill algorithm區(qū)域連通方式：4-connected8-connected9.3.3 種子填充算法區(qū)域連通方式對(duì)填充結(jié)果的影響4連通區(qū)域邊界填充算法的填充結(jié)果8連通區(qū)域邊界填充算法的填充結(jié)果9.3.3 種子填充算法簡(jiǎn)單的種子填充算法（4連通邊界）種子像素入棧當(dāng)棧非空時(shí)，重復(fù)以下步驟：棧頂像素出棧將出棧象素置成填充色 按左、上、右、下順序檢查與出棧象素相鄰的四象素，若其中某象素不在邊界上且未被置成填充色，則將其入棧 填充算法演示6754S9328S2479384794847956847968479784798479

26、94794796754S9328S799缺點(diǎn)？9.3.3 種子填充算法4-connected boundary-fill void BoundaryFill4(int x,int y,int fill,int boundary) int current; current = getpixel(x, y); if (current != boundary) & (current != fill) putpixel(x, y, fill); BoundaryFill4(x+1, y, fill, boundary); BoundaryFill4(x-1, y, fill, boundary); BoundaryFill4