圖形學-光柵化算法

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

2、用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量，計算下一步的x、y值。9.1.1 DDA算法已知一條直線段L（P1, P2）,其端點坐標分別為：P1 (x1, y1), P2(x2, y2)。直線段所在的直線的斜率為：直線方程為則9.1.1 DDA算法因光柵單位為1， 可以采用每次x方向增加1， y方向增加k的辦法得到下一個直線點。9.1.1 DDA算法void Line ( /設0k1,xsxe int xs,ys;/左端點 int xe,ye; /右端點 int value) /賦給線上的像素屬性值 int x; /x以步長為單位從xs增長到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移動步長是斜率k /9.1.1 DDA算法例：用DDA方法掃描轉換連接兩點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 中點畫線法基本原理 假定直線斜率k在0-1之間，當前象素點為（xp,yp），則下一個象素點有兩種

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

5、(Q點)上方，取P1為下一個象素；當d=0時，選P1或P2均可，約定取P1為下一個象素；M9.1.2 中點畫線法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 中點畫線法若d0，中點M在直線上方，取正右方象素P1 (Xp+1,Yp)下一個象素的判別式為： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d + a 增量為a若d0，中點M在直線下方，取右上方象素P2 (Xp+1,Yp+1)再下一個象素的判別式為： 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 中點畫線法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 中點畫線法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 中點畫線法舉例：用中點畫線方法掃描轉換連接兩點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算法使用最廣泛與中點畫線法的思想類似由誤差項符號決定下一個象素取正右方像素還是右上方像素9.1.3 Bresenham算法基本思想比較從理想直線到位于直線上方的像素的距離d2和相鄰的位于直線下方的像素的距離d1根據距離誤差項的符號確定與理想直線最近的象素9.1.3 Bresenham算法x方向遞增一個單位y方向走步與否取決于d1-d2的值取決于誤差e值的大小誤差判斷當e0.5時，最接近P2(xi+1,yi+1), y方向走一步當e0.5時，最接近 P1(xi+1,yi),y方向不走步初值：e0= y/ xeP1P2PeeP1P2Pe9.1.3 Bresenham算法為

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

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

11、0,x=y和x=-y。若已知圓弧上一點(x,y),可以得到其關于四條對稱軸的其它7個點，這種性質稱為圓的八對稱性。 yx(-x,y)(x,y)(-y,x)(y,x)(y,-x)(-y,-x)(-x,-y)(x,-y)oR9.2.1 簡單畫圓法假設圓心在原點 x2+y2=R2 圓的八對稱性只考慮第二個八分圓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 簡單畫圓法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 簡單畫圓法兩種直接離散生成方法離散點開方運算離散角度三角函數(shù)運算缺點：計算量大所畫像素位置間的間距不一致 9.2.2 中點畫圓法F(X,Y)=X2+Y2-R2=0中點 M=(Xp+1,Yp-0.5)當d0時，M在圓內，P1距離圓弧近，取P1當d0時，M在圓外，P2距離圓弧近，取

13、P29.2.2 中點畫圓法 若 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 中點畫圓法輸入圓的半徑R和圓心(xc,yc),先計算以原點為圓心，R為半徑的圓周上的點，令初始點為(x0,y0)=(0,R)設置初始決策參數(shù)d0=1-R在每一個xn（從n=0開始）的位置，進行下列檢測：如果 dn=y為止9.2.2 中點畫圓法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畫圓法順時針畫第一四分圓，下一步選擇哪個點？基本思想：通過比較像素與圓的距離平方來避免開方運算下一像素有3種可能的選擇mH=|(xi+1)2+yi2-R2|mD=|(xi+1)2+(yi-1)2-R2|mV=|xi2 +(yi-1)2-R2 |選擇像素的原則使其與實際圓弧的距離平方 達到最小(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)9.2.3 Bresenham畫圓法圓弧與點(xi,yi)附近光柵網格的相交關系有5種右下角像素D (xi+1,yi-1)與實際圓弧的近似程度i=(

16、xi+1)2+(yi-1)2-R2當i0時，D在圓外，當i=0時，D在圓上，(xi,yi)HPiVD(xi+1,yi)(xi,yi-1)(xi+1,yi-1)9.2.3 Bresenham畫圓法當i0時，D在圓內， 情形，選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畫圓法當i0時，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畫圓法當i=0時，D在圓上，按d判別，有d0，應選D按d判別，有d0，應選D9.2.3 Bresenham畫圓法當i0，選D當i0時,若d 0，選D 若d0，選V當i=0時，選D9.2.3 Bresenham畫圓法判別式的遞推關系當取H(xi+1,yi)時i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1當取V(xi,yi-1)時i

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

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

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

21、始交點x：從當前掃描線到下一條掃描線之間的x增量ymax：邊所交的最高掃描線號對每條掃描線建立一個新邊表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有序邊表填充算法活動邊表的建立5-32.533P1P2P2P3y=1.5207.833P6P1P2P3y=2.5207.1108P6P1P3P4y=3.5從新邊表中取出與掃描線y=1.5相交的初始邊排序放入活性邊表中，填充交點之間的區(qū)域更新邊表，刪除P1P2，插入新邊P6P1，填充交點之間的區(qū)域更新邊表，刪除P2P3，插入新邊P3P4，填充交點之間的區(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，填充兩對交點之間的區(qū)域更新邊表，填充兩對交點之間的區(qū)域更新邊表，刪除P6P1和P5P6，填充交點之間的區(qū)域更新邊表，刪除P4P5和P3P4，活動邊表為空，沒有新邊，填充算法結束9.3.1有序邊表填充算法步驟1、 建立NET表；2、將掃描線縱坐標y的初值置為NET中非空元素的最小序號3、置AET為空；4、執(zhí)行下列步驟直至NET和AEL都為空4.1、如NET中的第y類非空，則將其中的所有邊取出并插入 AEL中；4.2、如果有新邊插入AEL，則對AEL中各邊排序；4.3、對AEL中的邊兩兩配對，獲得有效填充區(qū)段，再填充4.4

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

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

26、94794796754S9328S799缺點？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