光柵圖形學教學課件

1、第二講 光柵圖形學光柵圖形學部分重要概念直線的生成圓的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換字符的顯示方法裁剪反走樣消隱 光柵掃描式顯示器是一種畫點設(shè)備，可看作是一個點陣單元發(fā)生器，并可控制每個點陣單元的亮度。 每個可尋址的點陣單元稱為一個像素（ pixel ）。 顯示器在水平和垂直方向上能夠?qū)ぶ返南袼財?shù)稱為分辨率。 光柵圖顯示器特征部分重要概念區(qū)域充填光柵化（掃描轉(zhuǎn)化）確定最佳逼近圖形的像素集合，并用指定屬性寫像素的過程稱為圖形的掃描轉(zhuǎn)化或光柵化。確定二維圖形內(nèi)部區(qū)域?qū)?yīng)的像素集，并用指定的屬性或圖案進行顯示的過程。部分重要概念走樣和反走樣裁剪消隱（消除隱藏線和隱藏面）確定一個圖形的哪些部分在窗口內(nèi)，必須

2、顯示；哪些部分落在窗口之外，不該顯示的過程稱為裁剪。因像素逼近誤差，使圖形產(chǎn)生畸變（臺階、鋸齒）的現(xiàn)象稱之為走樣。用于減少或消除走樣的技術(shù)稱為反走樣。為了提高圖形的真實性，必須把隱藏的部分從圖中刪除，習慣上稱為消除隱藏線和隱藏面，或簡稱消隱。直線段的掃描轉(zhuǎn)換算法直線的掃描轉(zhuǎn)換: 確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。在介紹三個常用算法前，先介紹一種最容易想到的算法： 直接計算法！0 直接計算法 假定直線的起點、終點分別為：（x0,y0), (x1,y1)，且都為整數(shù)。 計算出斜率k=(y1-y0)/(x1-x0) , 在Y軸的截距b=y0-k*x0 y=k*x

3、+b(X i+1, kX i+1+b)(X i , Yi)(X i , Yi)柵格交點表示象素點位置。 直接計算法 這樣一來，只要給定 x的值，根據(jù)解析式立即可以計算出對應(yīng)的y值，然后輸出(x,round(y). 這種方法直觀，但效率太低，因為每一步需要一次浮點乘法、一次浮點加法和一次舍入運算。(X i+1, kX i+1+b)(X i , Yi)(X i , Yi)。直線的生成直線段掃描轉(zhuǎn)換算法： 數(shù)值微分法DDA算法 中點畫線法 Bresenham畫線算法1 數(shù)值微分法（） 假定直線的起點、終點分別為：（x0,y0), (x1,y1)，且都為整數(shù)。(X i+1 ,Yi + k)(X i ,

4、 Int(Yi +0.5)(X i , Yi)。數(shù)值微分(DDA)法基本思想已知過端點P0 (x0, y0), P1(x1, y1)的直線段L y=kx+b直線斜率為考慮當x從xixi+1時y的變化規(guī)律： 設(shè)x=xi+1- xi xi+1= xi+ x數(shù)值微分(DDA)法計算yi+1= kxi+1+b= k(xi+ x) +b = kxi+b+kx = yi+kx 當x =1;yi+1 = yi+k 即：當x每遞增1，y遞增k(即直線斜率)；注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每增加1,y最多增加1。當 k 1時，必須把x，y地位互換數(shù)值微分(DDA)法增量算法：在一個迭代

5、算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。數(shù)值微分(DDA)法void 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; 數(shù)值微分(DDA)法例：畫直線段P0(0,0)-P1(5,2) k=0.4x y int(y+0.5) 0 0 0 0.4

6、0 0.8 131.2 141.6252.02數(shù)值微分(DDA)法缺點： 在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實現(xiàn)。2 中點畫線法原理：假定直線斜率0K P2離直線更近更近-取P2 。M在Q的上方- P1離直線更近更近-取P1M與Q重合， P1、P2任取一點。問題：如何判斷M與Q點的關(guān)系？中點畫線法由常識知：若y=kx+b;F(x,y)=y-kx-b;則有中點畫線法假設(shè)直線方程為：ax+by+c=0通過兩點不能唯一確定a,b,c,取 a=y0-y1, b=x1-x0, c=x0y1-x1y0，F(xiàn)(x,y)=ax+by+c; 則有欲判斷M點是在Q點上方還

7、是在Q點下方，只需把M代入F(x,y),并檢查它的符號。中點畫線法構(gòu)造判別式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c當d0，M在直線(Q點)上方，取右方P1；當d=0，選P1或P2均可，約定取P1；能否采用增量算法呢？中點畫線法若d0 -M在直線上方-取P1;此時再下一個象素的判別式為 d1=F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量為a中點畫線法若dM在直線下方-取P2;此時再下一個象素的判別式為 d2= F(xp+2, yp+1.5) =a(x

8、p+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量為ab中點畫線法畫線從(x0, y0)開始，d的初值d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符號作判斷，為了只包含整數(shù)運算, 可以用2d代替d來擺脫小數(shù)，提高效率。中點畫線法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=

9、x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xx1) if (d1則(y0,x0)和(y1,x1)所確定的 直線斜率k 0,1， 適用于前面討論的情形。對(y0,x0)和(y1,x1)所確定的 直線進行掃描轉(zhuǎn)換， 每確定一組(x,y)，輸出(y,x)。(x0,y0)(y1,x1)(x1,y1)(y0,x0)斜率不在0,1的直線的處理若-1k0先對(x0,-y0)和(x1,-y1)所確定的 直線進行掃描轉(zhuǎn)換， 每確定一組(x,y)，輸出(x,-y)。(x0,y0)(x1,-y1)(

10、x1,y1)(x0,-y0)斜率不在0,1的直線的處理若k0.5，則(x,y)更新為(x+1,y+1)，同時將d更新為d-1；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。改進1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if (e0) then e=e-1算法步驟為：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值x、y、e=-0.5、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+k，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-1；否則(x,y)更新為(x+1,y)。5.

11、當直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。改進2：用2ex來替換ee初=-x，每走一步有e=e+2y。if (e0) then e=e-2xe=e+ke=e+y/xx e= x e+ ye=-0.52e=-1算法步驟：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值x、y、e=-x、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+2y，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2x；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。Bresenham畫線算法BresenhamLine(x

12、0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy,e; dx = x1-x0; dy = y1-y0; e = -dx; x=x0; y=y0; for( i=0; i= 0) e = e - 2*dx; y+; 舉例：用Bresenham方法掃描轉(zhuǎn)換連接兩點P0（0,0）和P1（5,2）的直線段。 x y e e0=-5; dx=5;dy=20 0 -1 1 0 3 (-7 )2 1 -3 3 1 1(-9)4 2 -5 5 2 -1Bresenham算法Bresenham畫線算法 在直線生成的算法中Bresenham算法是最有效的

13、算法之一。令 k=y/x，就0k1的情況來說明Bresenham算法。由DDA算法可知：yi+1=yi+k (1) 由于k不一定是整數(shù)，由此式求出的yi也不一定是整數(shù)，因此要用坐標為（xi,yir）的象素來表示直線上的點，其中yir表示最靠近yi的整數(shù)。實驗報告1：名稱：直線的掃描轉(zhuǎn)換目的要求：理解和掌握直線掃描轉(zhuǎn)換的三種算法，并在某種開發(fā)環(huán)境下將其具體實現(xiàn)。實驗步驟：（要寫出實際實現(xiàn)的程序和結(jié)果，切忌將書上或筆記上的程序照搬）要有實驗總結(jié)。基本要求理解圖形的掃描轉(zhuǎn)換的含義；掌握DDA、MIDPoint、Bresenham畫線算法。（算法的原理、代碼表示、特點等）能夠編程處理任意直線。課堂測試

14、（一）奇數(shù)列：解釋下列名詞：光柵化、區(qū)域填充、裁剪請說明中點劃線法的基本思想根據(jù)中點劃線法用C語言完成下列函數(shù)2012/2/29 / SetPixel 為已有函數(shù)，描畫點(x,y)void SetPixel(int x, int y, int color);void MidpointLine( int x0,int y0,int x1,int y1, int color)用中點劃線法光柵化連接點p1(0,0)和p2(6,3)的直線課堂測試（一）偶數(shù)列：解釋下列名詞：走樣、反走樣、消隱請說明Bresenham劃線法的基本思想根據(jù)Bresenham劃線法用C語言完成下列函數(shù)2012/2/29 /

15、SetPixel 為已有函數(shù)，描畫點(x,y)void SetPixel(int x, int y, int color);void MidpointLine( int x0,int y0,int x1,int y1, int color)用Bresenham劃線法光柵化連接點p1(0,0)和p2(6,3)的直線圓的掃描轉(zhuǎn)換1 基礎(chǔ)知識2 中點畫圓法3 Bresenham畫圓法1）直接利用圓的方程生成圓 下面先以圓心在原點、半徑r為整數(shù)的圓為例，討論圓的生成算法。假設(shè)圓的方程為： x2 + y2 = r21 基礎(chǔ)知識x2 + y2 = r2y = sqrt(r2 - x2)在一定范圍內(nèi)，每給定

16、一x值，可得一y值。當x取整數(shù)時，y須取整。缺點：浮點運算，開方，取整，不均勻。yx也可應(yīng)用圓的參數(shù)方程畫出分布比較均勻的點x = rcosy = rsin 但仍要采用浮點運算、乘法運算、取整運算。(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)2）八分法畫圓利用圓的對稱性：結(jié)論：只需對一個八分圓進行掃描轉(zhuǎn)換。 當圓心坐標(xc ，yc ) ，半徑為整數(shù)r時： (x-xc)2+(y-yc)2=r2 可以先對圓心坐標(0 ，0 ) ，半徑為r的八分圓進行掃描轉(zhuǎn)換，根據(jù)圓的對稱性，得到八個對稱點，再將這八個點進行平移，即可得到原始圓上的對應(yīng)點。3）畫任意圓的方

17、法 void Circle8Points(int x0,int y0, int x,int y,COLORREF c) pDC-SetPixel(x0+x,y0+y,c); pDC-SetPixel(x0-x,y0+y,c); pDC-SetPixel(x0+x,y0-y,c); pDC-SetPixel(x0-x,y0-y,c); pDC-SetPixel(x0+y,y0+x,c); pDC-SetPixel(x0-y,y0+x,c); pDC-SetPixel(x0+y,y0-x,c); pDC-SetPixel(x0-y,y0-x,c); 對于圓心在（x0,y0)、半徑為r的圓，先對圓心

18、在原點，半徑為r的8分圓進行掃描轉(zhuǎn)換，每確定一個象素，可輸出原始圓的8個點。2 中點畫圓法利用圓的對稱性，只須討論1/8圓。第二個8分圓。P為當前點亮象素，那么，下一個點亮的象素可能是P1（xp+1，yp）或P2（xp +1，yp +1)。(|dy|=|x/y|*|dx|)MP1P2P（xp ，yp ）P2構(gòu)造函數(shù)：F（X，Y）=X2 + Y2 - r2 ；則 F（X，Y）= 0 （X，Y）在圓上； F（X，Y） 0 （X，Y）在圓外。設(shè)M為P1、P2間的中點，M=(Xp+1,Yp-0.5)MP1有如下結(jié)論： F（M）M在圓內(nèi)- 取P1 F（M）= 0 -M在圓外- 取P2為此，可采用如下判別

19、式： MP1P2 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2 - r2 若d=0, 則P2 為下一個象素，那么再下一個象素的判別式為： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - r2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量為 2 (xp - yp) +5. MP1P2M最后一個問題：判別式d的初始值算法步驟：1.輸入圓的半徑R。2.計算初始值d=1.25-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.

20、判斷d的符號。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x=y時，重復(fù)步驟3和4。否則結(jié)束。中點畫圓法程序代碼 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(x=y) if(d0) d=d+2*x+3; x+ elsed= d+2*(x-y) + 5; x+;y-; drawpixel(x,y,color); 為了進一步提高算法的效

21、率，可以將上面的算法中的浮點數(shù)改寫成整數(shù)，將乘法運算改成加法運算，即僅用整數(shù)實現(xiàn)中點畫圓法。使用e=d-0.25代替de0=1-rd0e-0.25由于e的初值為整數(shù)，且在運算過程中的增量也是整數(shù)，故e始終是整數(shù)，所以e-0.25 e0。算法優(yōu)化算法步驟：1.輸入圓的半徑R。2.計算初始值d=1-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x=y時，重復(fù)步驟3和4。否則結(jié)束。中點畫圓法程序代碼 M

22、idpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1-r; drawpixel(x,y,color); while(x=y) if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; drawpixel(x,y,color); 上述算法能否再改進呢？注意到d的增量是x,y的線性函數(shù)，每當x遞增1，則d的增量遞增x=2每當y遞減1，則d的增量遞增y=2x初始值=3；y初始值=-2r+2x=0; y=r; d=1-r; .if(d0) d+ = 2*x+3; x+ ;elsed+

23、= 2*(x-y) + 5; x+;y-; x=0;y=r;d=1-r;d1=3;d2=-2*r+2; .if(d0) d+ = d1; x+;d1+=2 ;elsed+ = d1+d2; x+;y-; d1+=2;d2+=2 MidpointCircle(int r, int color) int x,y; int d; x=0; y=r; d=1-r;d1=3;d2=-2*r+2; drawpixel(x,y,color); while(x=y) if(d0和dD0若pi0，即dH 0，必有pi0，dD0，必有pi0。得出結(jié)論： pi做判別量， pi0選H點為下一個象素點，當pi0時，選D點為下一個象素點。HD(xi,yi)從pi計算pi+1 HD(xi,yi)dDdH從pi計算pi+1 當pi0時，應(yīng)選D點，即選當pi0時，應(yīng)選H點，即選 HD(xi,yi)dDdH畫圓的起始點是(0，R)，即x1=0，y1=R，代入前式，令i=1，就得到： HD(xi,yi)dDdHvoid BresenhamCircle(int R) int x,y,p;x=0; y=R;p=3-2*R;for(;x=0)p+=4*(x-y)+10;y-;else p+=4*x+6;HD(xi,yi)dDdH只