計算機圖形學課程論文

1、計算機圖形學課程論文課程名稱計算機圖形學授課教師XXX專業(yè)軟件工程年級2013姓名XXX學號2013XXXXXXX學期20152016學年第二學期成績授課教師簽名計算機圖形學期末綜合理論摘要:計算機圖形學直線變換算法二維圖形算法圖形填充算法31言：計算機圖形學是一種使用數(shù)學算法將二維或三維圖形轉(zhuǎn)化為計算機顯示器的柵格形式的科學。簡單地說，計算機圖形學的主要研究內(nèi)容就是研究如何在計算機中表示圖形、以及利用計算機進行圖形的計算、處理和顯示的相關原理與算法。雖然通常認為CG是指三維圖形的處理，事實上也包括了二維圖形及圖像的處理。狹義地理解，計算機圖形學是數(shù)字圖象處理或計算機視覺的逆過程：計算機圖形學

2、是用計算機來畫圖像的學科，數(shù)字圖象處理是把外界獲得的圖象用計算機進行處理的學科，計算機視覺是根據(jù)獲取的圖像來理解和識別其中的物體的三維信息及其他信息。實際上，計算機圖形學、數(shù)字圖象處理和計算機視覺在很多地方的區(qū)別不是非常清晰，很多概念是相通的，而且隨著研究的深入，這些學科方向不斷的交叉融入，形成一個更大的學科方向，可稱之為“可視計算”。計算機圖形學主要包含四大部分的內(nèi)容：建模(Modeling卜渲染(Rendering)動畫(Animation)和人機交互(Human-computerInteraction,HCI)。目錄1、概論41.1 什么是計算機圖形學41.2 計算機圖形學的研究內(nèi)容41

3、.3 什么是計算機圖形學41.4 計算機中表示圖形的方法52、直線生成算法42.1 直線數(shù)值微分算法52.1.1 數(shù)值微分算法基本原理62.1.2 數(shù)值微分算法基本原理62.1.3 數(shù)值微分算法設計與代碼實現(xiàn)72.1.4 數(shù)值微分算法設計與代碼實現(xiàn)82.1.5 小結(jié)92.2 直線中點畫線算法92.2.1 直線中點畫線算法基本原理92.2.2 數(shù)值微分算法描述與步驟102.2.3 中點劃線算法設計與代碼實現(xiàn)122.2.4 小結(jié)102.3 直線Breseham畫線算法122.3.1 直線Breseham畫線基本原理132.3.2 直線Breseham畫線算法描述與步驟132.3.3 直線Brese

4、ham畫線算法設計與代碼實現(xiàn)172.3.4 小結(jié)183、二維圖形變換193.1 二維圖形平移變換193.1.1 二維圖形平移變換基本原理193.1.2 二維圖形平移變換算法描述與步驟193.1.3 二維圖形平移變換算設計與代碼實現(xiàn)213.2 二維圖形縮放變換213.2.1 二維圖形縮放變換基本原理213.2.2 二維圖形縮放變換算法描述與步驟213.2.3 二維圖形縮放變換算法設計與代碼實現(xiàn)223.3 二維圖形對換變換233.3.1 二維圖形對換變換基本原理233.3.2 二維圖形對換變換算法描述與步驟233.3.3 二維圖形對換變換算設計與代碼實現(xiàn)253.4 二維圖形旋轉(zhuǎn)變換263.4.1

5、二維圖形旋轉(zhuǎn)變換基本原理263.4.2 二維圖形旋轉(zhuǎn)變換算法描述與步驟263.4.3 二維圖形旋轉(zhuǎn)變換算設計與代碼實現(xiàn)264、圖形填充算法274.1 種子填充算法304.1.1 種子填充算法基本步驟304.1.2 種子填充算法設計與代碼實現(xiàn)304.2 邊標志填充算法304.2.1 邊標志填充算法基本步驟314.2.2 種子填充算法設計與代碼實現(xiàn)314.3 小結(jié)325、總結(jié)和展望326、參考文獻331、概論1.1 什么是計算機圖形學計算機圖形學是利用計算機研究圖形的表示、生成、處理、顯示的學科。計算機圖形學計算機科學中，最為活躍、得到廣泛應用的分支之一。1.2 計算機圖形學的研究內(nèi)容如何在計算機

6、中表示圖形、以及利用計算機進行圖形的計算、處理和顯示的相關原理與算法，構(gòu)成了計算機圖形學的主要研究內(nèi)容。圖形硬件、圖形標準、圖形交互技術、光柵圖形生成算法、曲線曲面造型、實體造型、真實感圖形計算與顯示算法，以及科學計算可視化、計算機動畫、自然景物仿真、虛擬現(xiàn)實等。1.3 基本概念1.3.1 怎樣用計算機生成、處理和顯示圖形的學科(1)圖形的輸入如何開發(fā)利用圖形輸入設備及軟件將圖形輸入到計算機中去，以便作各種處理(2)圖形的處理包括對圖形進行變換(幾何變換，投影變換)和運算(集合運算)，裁減，著色，形變等(3)圖形的輸出如何將圖形特定的表示形式轉(zhuǎn)換成圖形輸出系統(tǒng)便于接受的表示形式，并將圖形在顯示

7、屏或打印機等輸出設備上輸出，或以文件的形式保存在磁盤上。1.3.2 相關的概念(1)圖形：計算機圖形學的研究對象，能在人的視覺系統(tǒng)中產(chǎn)生視覺印象的客觀對象，包括自然景物、拍攝到的圖片、用數(shù)學方法描述的圖形等等構(gòu)成圖形的要素(2)幾何要素：刻畫對象的輪廓、形狀等(3)非幾何要素：刻畫對象的顏色、材質(zhì)等1.4 計算機中表示圖形的方法1.4.1 點陣表示枚舉出圖形中所有的點（強調(diào)圖形由點構(gòu)成）簡稱為圖像（數(shù)字圖像）1.4.2 參數(shù)表示由圖形的形狀參數(shù)（方程或分析表達式的系數(shù)，線段的端點坐標等）以及屬性參數(shù)（顏色、線型等）來表示圖形簡稱為圖形2.直線生成算法2.1 直線數(shù)值微分算法2.1.1 數(shù)值微分

8、算法基本原理設直線的起點坐標為（x0,y0）,終點坐標為（x1,y1）,二者均為整數(shù)坐標值,令dx=x1-x0,dy=y1-y0,則直線斜率k為：k=dy/dx目標是能快速地求出能很好地表示直線的像素，涉及到大量的重復性的運算，因此，盡量用加法代替乘法運算，因為計算機中：加法運算比乘法運算效率高2.1.2 數(shù)值微分算法描述與步驟當|k|01時，從x的左端點x0開始，向x右端點步進。步長=1個像素（即Dx=1）,計算相應的y坐標y=kx+B；取像素點（x,round（y）作為當前點的坐標。注意到：yi+1=kxi+1+B=k（xi+Dx）+B=kxi+B+kDx=yi+kDx=yi+k即：當x每

9、遞增1,y遞增k（即直線斜率）；上述分析的算法僅適用于|k|<1的情形。在這種情況下，x每增加1,y最多增加1當|k|>1時，必須把x,y地位互換2.1.3 數(shù)值微分算法設計與代碼實現(xiàn)線段DDA算法偽代碼描述下面用偽代碼給出DDA算法。ProcedureDDA-line(x1,y1,x2,y2)BEGIN/求線段在兩坐標軸方向改變量的較大者/IFabs(x2-x1)>=abs(y2-y1)THENlength=abs(x2-x1)ELSElength=abs(y2-y1)ENDIF/定義dx或dy中的較大值為1/dx=(x2-x1)/lengthdy=(y2-y1)/leng

10、thx=x1+0.5*Sign(dx)y=y1+0.5*Sign(dy)i=1WHILE(i<length)PLOT(Integer(x),Integer(y)x=x+dxy=y+dyi=i+lENDWHILEEND2.1.4 小結(jié)這種方法計算方法的缺點是計算量大?？紤]到在計算機上實時編輯修改圖形時，連續(xù)不斷的需要在顯示器上顯示出大量的直線段，畫線的速度就會非常地慢。因此需要對上述結(jié)果詳細分析已給出較快的算法。2.2 直線中點畫線算法2.2.1 數(shù)值微分算法基本原理原理假設直線的斜率0<k<1；當前像素點為P(xp,yp),下一個像素為Pi或P2設M=(xp+1,yp+0.5

11、),為pi與p2之中點，Q為理想直線與x=xp+1垂線的交點。將Q與M的y坐標進行比較：M在Q的下方，則P2為下一點；M在Q的上方，則R為下一點。圖2.1a圖2.1b2.2.2 數(shù)值微分算法描述與步驟構(gòu)造直線方程F(x,y)=ax+by+c=0調(diào)整方程參數(shù)，使得：點(x,y淞于直線上方：F(x,y)>0;點(x,y淞于直線下方：F(x,y)<0;把中點M的坐標帶入方程，構(gòu)造判別式：=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c因此：當d>0時，點M位于Q點上方，取R為下一點；當d<0時，點M位于Q點下方，取P2為下一點；d=0時，Q和M

12、重疊，任取R、P20如果取R,則可合并為d0時取Pi判別式d的增量算法:設確定Pi(xi,y)位置時判別式的值為di,則:如果di斗，貝UXi=Xi-1+1,yi=yi-1di=F(Xi-i+1,yi-i+0.5)=F(xi,yi+0.5)=axi+b(yi+0.5)+cdi+1=F(Xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c=axi+b(yi+0.5)+c+a=di+adi洲Ti+1=di+a如果di<0,則xi=xi-1+1,yi=yi-1+1di=F(xi-1+1,yi-1+0.5)=F(xi,yi-0.5)=axi+b(yi-0.5)+cdi+1=F(xi+

13、1,yi+0.5)=a(xi+1)+b(yi+0.5)+c=axi+b(yi-0.5)+c+a+b=di+(a+b)di<0di+1=di+a+b直線的起始端點坐標為(x0,y0),則:di=F(x0+1,y0+0.5)=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b(F(x0,y0)=0)=a+0.5b(存在0.5b,為浮點運算)整數(shù)算法:算法中僅用到判別式d的符號，所以可用2d代替d進行遞增運算:2.2.3 中點劃線算法設計與代碼實現(xiàn)voidMidpointLine(intx0,inty0,intxi,intyi,intcolor)inta,b,di,d2,d,x,

14、y;a=y0-yi,b=xi-x0,d=2*a+b;di=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<xi)if(d<0)x+,y+,d+=d2;elsex+,d+=d1;drawpixel(x,y,color);2.2.4 小結(jié)如上面代碼所示，DDA算法中的y和k都必須用浮點數(shù)表示，并且每一步運算都要對y進行舍入取整，這不利于硬件實現(xiàn)。中點畫線法只包含整數(shù)變量，并且不含乘除法，因而解決了上述問題2.3 直線Breseham畫線算法2.3.1 直線Breseham畫線基本原理Bresenham直線算法最初是為數(shù)字繪圖儀

15、而設計的。它的目標是選擇表示直線的最佳像素點位置.為此,算法根據(jù)直線的斜率確定在x或y方向上每次遞增一個單位，而另一方向上根據(jù)理論直線段與最近像素點的距離每次的增量為0或1。我們首先討論直線斜率m0,1耳x2>xi時的整數(shù)Bresenham算法，然后再推廣到畫任意線段的算法。2.3.2 直線Breseham畫線算法描述與步驟當直線斜率m60,1,且x2>xi時,根據(jù)式(2.2.9府:(叫+1=Xi+1%+i=yi+m又由于顯示直線的像素點只能取整數(shù)值坐標，可以假設直線上第i個像素點坐標為(Xi,yi),它是直線上點(Xi,yi)的最近似并且Xi=xio于是，要表達的直線上下一個(X

16、i+i,yi+i)=(Xi+1,yi+m)的最近似的像素點的可能位置是(Xi+1,yi)或(Xi+1,yi+1)。在x=Xi+1處，直線上點的坐標y=m(Xi+1)+b.該點與點(Xi+1,yi)和(Xi+1,yi+1)的距離分別是d1和d2：d1=y-yi=m(Xi+1)+b-yi?d2=(yi+1)-y=(yi+1)-m(Xi+1)-b這兩個距離的差為：d1-d2=2m(Xi+1)-2yi+2b-1這個差有如下幾何意義:?當此值為正時，真正的直線上點離像素點(Xi+1,yi+1)較近，說明下一個直線上的像素點應取(Xi+1,yi+1)。(2)當此值為負時，真正的直線上離像素點(Xi+1,y

17、i)較近，說明下一個直線像素點應取(Xi+1,yi)。(3)當此值為零時，真正的直線上離上、下兩個像素點的距離相等，我們規(guī)定取(Xi+1,yi)作為下一個直線像素點。？因止匕，只要利用(di-d2)的符號就可以決定下一個像素點的選擇。如果我們定義一個新的判別式：?Pi=?x?(di-d2)=2?y-i-2?xiy+c(2.2.18)因此式中的?x=(X2-xi)>0,pi與(di-d2)有相同符號；?y=y2-yi；常數(shù)c=2?y+?x(2b-i)。pi的一個優(yōu)點是省去了(di-d2)中為了計算m所需要的除法運算。我們知道除法運算用硬件實現(xiàn)是比較復雜的?，F(xiàn)在我們要進一步化簡上述誤差判別式

18、以得到遞推公式，消除常數(shù)c.以i+i代換此式中的i,得到：Pi+i=2?y-i+i-2?xi+i+c與前式相減，并利用xi+i=xi+i,可得，Pi+i=pi+2?y-2?xi(y-yi)再假設直線的初始端點恰好是其像素點的坐標,即滿足：于是可得Pi的初值yi=mxi+bpi=2?y-?x這樣，利用誤差判別變量，并注意到每一步x的增量為xi+i-xi=i就可得到如下算法表示：(1) .(2) .如果R>0,pi=2?y-?xxi+i=xi+i(2.2.23)2.2. 直線點陣轉(zhuǎn)換算法(3).如果pi<0,yi+i=yi?pi+i=pi+2?y從式(2.2.20)可以看出，第i+1步

19、的判別變量*僅與第i步的判別變量p直線的兩個端點坐標分增量？x和？y有關,計算也很簡單，只用整數(shù)相加和乘2運算，沒有四舍五入處理，而乘2可利用左移一位來實現(xiàn)，因此這個算法速度快并易于硬件實現(xiàn)。該算法的主要步驟如下：？(1)輸入線段的兩個端點分別存于(xs,ys)和(xe,ye)中,(2)將第一點作為起始點，即有(xi,yi)=(xs,ys),(3)分別計算？x、?y>pi,pi<0,下一點為(xi+1,yi),否則，取(xi+1,yi+i),?(4)以單位步長增加x坐標，按式(2.2.24)或(2.2.25)計算pi。若pi<0,下一點的y坐標不變，否則y坐標加1。？(5)重

20、復步驟直到x逐步增加到xe為此。？在前面的處理中，我們假設m60,1。這一假設的幾何意義是要繪的直線段與x-軸的夾角不超過與y-軸的夾角?；蛘吒庇^地，直線段的方向更靠近x-軸方向，如果有m>1,則說明直線段的方向更靠近y-軸方向。如果我們互換兩個坐標軸，則直線段就滿足前面的假設條件.因此，只要將算法中的x和y對換,則上述兩個公式依然有效。如果m<0,則相應的只是x或y的方向的改變后，上述兩個公式依然有效。這時實際上只是改變？x或?y的符號即可.2.3.3 直線Breseham畫線算法設計與代碼實現(xiàn)ProcedureBresenham-line(xs,ys,xe,ye)BEGINd

21、x=ABS(xe-xs);dy=ABS(ye-ys);x=xs;y=yss1=SIGN(xe-xs),s2=SIGN(ye-ys)Ifdy>dxTHENtemp=dx;dx=dy:dy=tempinterchange=1ELSEinterchange=OENDIFp=2*dy-dxFORi=1TOdxPLOT(x,y)IFp>=OTHENIFinterchange=1x=x+s1ELSEy=y+s2ENDIFp=p-2*dxENDIFIFinterchange=1THENy=y+s2ELSEx=x+s1ENDIFp=p+2*dyNEXTiEND2.3.4 小結(jié)以下是近似圖形和真實直

22、線之間的差距，可以看得出來，其實實際上圖形差距已經(jīng)很小了。(2).實際要求的直線及其近似點3 .二維圖形變換3.1 二維圖形平移變換3.1.1 二維圖形平移變換基本原理平移是指點從一個位置到另一個位置的直線移動，即把點P(x,y)平移到P(x'，y),在x-方向移動了距離Tx,在y-方向移動了距離Ty。于是可得平移公式冷范(621)平移變換用向量解釋更清晰：平面上每一點都對應著一個從坐標原點到這一點的向量，平移變換實際上就是把整幅圖形沿某個方向移動一段距離，這就是每個點加上一個向量.用坐標表示出的這個向量就是Tm=(Tx,Ty),稱為平移矢量或位移矢量。用向量表示的平移變換公式就是1

23、k*¥>OPf=OP+PPf=OP+Tm(622)3.1.2 二維圖形平移變換算法描述與步驟顯然多邊形的平移變換是由構(gòu)成多邊形的每一條線的始、末點的坐標都加上相應的平移量而得到的。如圖6.1所示,多邊形從一個位置平移至另一個位置時，其平移量為(Tx,Ty)o由此可見。多邊形的平移是通過改變定義其邊的坐標值實現(xiàn)的，不需要對多邊形邊上的每一點都作變換。而圓和橢圓的平移則需要通過移動其園心坐標和依據(jù)其半徑來實現(xiàn)。平移坐標系的平移變換最后要說明的是如果認為坐標系在X-方向移動了距離Tx,在y-方向移動了距離Ty,得到新的坐標系O'x'Y:則在新的坐標系下，相當于點在X-

24、方向反向移動了距離Tx,在y-方向反向移動了距離Tyo于是可得平移公式(6.2.4)y=y-Ty而不是(6.2.1).用向量表示的平移變換公式就是(yp=OP-OOf(625)3.1.3 二維圖形平移變換算設計與代碼實現(xiàn)voidmyDrawl(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/將當前矩陣設為單位矩陣glColor3f(1.0,0.0,0.0);drawSquare();/在原點處繪制邊長為2紅色正方形glTranslatef(2.0,3.0,0.0);向右移動2單位，向上移動3單位glColor3f(0.0,1.0,

25、0.0);drawSquare();/繪制邊長為2綠色正方形glTranslatef(0.0,-3.0,0.0);/再向下移動3單位glColor3f(0.0,0.0,1.0);drawSquare();/繪制邊長為2藍色正方形glFlush();3.2 二維圖形縮放變換3.2.1 二維圖形縮放變換基本原理一個圖形的尺寸，變換前、后成比例變化，即稱之為比例變換。通過x-和y-坐標軸方向的比例變換因子Sx和Sy使點P(x,y)變換為P'(x'，y),則(627)3.2.2 二維圖形縮放變換算法描述與步驟如果選擇一個能控制圖形比例變換的點，使該點在變換后仍保持不變,則稱其為基點。可

26、以選擇圖形的頂點、中心點或其他任何位置的點為基點。上述比例變換只適合基點在坐標原點的比例變換對于一個指定基點（xF,yF）（見圖6.3）的比伊J變換,首先把坐標系原點平移到基點,來的原在新坐標系下作基點在原點的比例變換，然后再把坐標系的原點平移回原點。這時的比例變換公式為：.X圖6.3圖形相對于基點年冉學尸）的比例變換(629)工=工+(工-HF)Sc/=yr+(I/-既3.2.3 二維圖形縮放變換算法設計與代碼實現(xiàn)voidmyDraw12(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/將當前矩陣設為單位矩陣glColor3f(

27、1.0,0.0,0.0);drawSquare();/在原點處繪制邊長為2紅色正方形glScalef(1.0,1.5,1.0);/X和Z方向保持不變，Y方向放大為原來的1.5倍glColor3f(0.0,1.0,0.0);drawSquare();/繪制邊長為2綠色正方形glTranslatef(0.0,-3.0,0.0);/再向下移動3單位glColor3f(0.0,0.0,1.0);drawSquare();/繪制邊長為2藍色正方形glFlush();)3.3 二維圖形對稱變換3.3.1 二維圖形對稱變換基本原理對稱變換又可稱為反射變換，鏡像變換，從幾何直觀上表現(xiàn)為不同的類型：有關于x-軸

28、，y-軸的對稱變換，以及關于直線y=x,y=-x的直線對稱變換，當然也有關于任意一條直線的對稱變換。3.3.2 二維圖形對稱變換算法描述與步驟(1)關于x-軸的對稱變換?設對點P(x,y)乍關于x-軸的對稱變換后，得到點'''一、一，、一一P(x,y),則變換的特點是x坐標不變，y坐標由正變負，由負變正，即改變了符號.于是變換公式為：(6218)J=T虱=-y這一變換的矩陣表示如下:(6,2.19)(2)關于y-軸的對稱變換設對點P(x,y)作關于y-軸對稱變換后，得到點P'(x'，y'),則變換的特點是y坐標不變，x坐標由正變負，由負變正，即改

29、變了符號.于是變換公式為這一變換的矩陣表示如下:Tf=Xyf=y(6220)(6221)圖63點（招引的各種對禰點位置示意圖(一E,（4）關于任意直線，任意點的對稱變換上述對稱變換是對特定的直線和點的對稱變換.對于任意點（這一點稱對稱中心）的對稱變換，類似于前面的一般的比例變換和旋轉(zhuǎn)變換，先要把坐標系原點平移到對稱中心，再進行坐標系原點的對稱變換，然后把坐標系平移回原來的坐標系原點。關于以任意指定直線作對稱軸的對稱變換，可先把坐標系原點平移到對稱軸線上,再旋轉(zhuǎn)坐標系，使x-軸（或上述其它三種軸對稱變換的軸線）重合于這里的軸線；這時作相應的軸對稱變換；然后，反向旋轉(zhuǎn)坐標系到原來的坐標系方向，并把

30、坐標系原點平移回原來的坐標系原點即可把關于坐標系原點及兩條坐標軸的對稱變換和比例變換結(jié)合起來考慮，我們可以看出比例變換的比例系數(shù)也可以是負數(shù)，這時的變換結(jié)果實際上相當于同時進行了比例變換和對稱變換.如果兩個比例系數(shù)都是負數(shù)，則對稱變換是關于原點的對稱變換；如果只有一個比例系數(shù)是負數(shù)，則對稱變換是關于負數(shù)比例因子對應的坐標軸的對稱變換。3.3.3 二維圖形對稱變換算法設計與代碼實現(xiàn)voidmyDraw3(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/將當前矩陣設為單位矩陣glColor3f(1.0,0.0,0.0);drawSqu

31、are();/在原點處繪制邊長為2紅色正方形glScalef(1.0,1.5,1.0);/X和Z方向保持不變，Y方向放大為原來的1.5倍glColor3f(0.0,1.0,0.0);drawSquare();/繪制邊長為2綠色正方形glSymmetry(0.0,-3.0,0.0);/對稱變換glColor3f(0.0,0.0,1.0);drawSquare();/繪制邊長為2藍色正方形glFlush();3.4 二維圖形旋轉(zhuǎn)變換3.4.1 二維圖形旋轉(zhuǎn)變換基本原理圖形上的點以坐標原點為中心旋轉(zhuǎn)一定角度產(chǎn)生的變換稱為旋轉(zhuǎn)變換。設點P(x,y流轉(zhuǎn)至P'(x',y'),旋轉(zhuǎn)角

32、為0(為確定起見設逆時針方向為旋轉(zhuǎn)的正方向)3.4.2 二維圖形旋轉(zhuǎn)變換算法描述與步驟角小是P(x,y)點在xy-平面內(nèi)與x-軸的夾角，用來定義對點P(x,y)乍旋轉(zhuǎn)變換時的起始位置，即有x=rcos2/=rsind(6212)3.4.3 二維圖形變換算法設計與代碼實現(xiàn)voidmyDraw4(void)(glClear(GL_COLOR_BUFFER_BIT);/清空glLoadIdentity();/將當前矩陣設為單位矩陣glColor3f(1.0,0.0,0.0);drawSquare();/在原點處繪制邊長為2紅色正方形glScalef(1.0,1.5,1.0);/X和Z方向保持不變，Y

33、方向放大為原來的1.5倍glColor3f(0.0,1.0,0.0);drawSquare();/繪制邊長為2綠色正方形glRotatef(30,0.0,0.0,1.0);/順時針旋轉(zhuǎn)30角度glColor3f(0.0,0.0,1.0);drawSquare();/繪制邊長為2藍色正方形glFlush();4 .圖形填充算法4.1 種子填充算法4.1.1 種子填充算法基本步驟(1)多邊形的表示方法表小方法：頂點表小和點陣表小頂點表示是用多邊形的頂點的序列來描述多邊形，該表示幾何意義強、占內(nèi)存少，但它不能直觀地說明哪些像素在多邊形內(nèi)。點陣表示是用位于多邊形內(nèi)的像素的集合來刻劃多邊形，該方法雖然沒

34、有多邊形的幾何信息，是面著色所需要的圖像表示形式。多邊形填充就是把多邊形的頂點表示轉(zhuǎn)換為點陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個像素，并將幀緩沖器內(nèi)的各個對應元素設置相應的灰度或顏色。多邊形頂點表示多邊形點陣表示(2)活性邊表算法掃描線算法基本思想：按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。對于一條掃描線填充過程可以分為四個步驟：(1)求交(2)排序(3)配對(4)填色存在問題多邊形頂點與掃描線相交，交點數(shù)量計算不當會產(chǎn)生交點配對錯誤。解決方式：下閉上開邊界像素是否填充，處理不當造成填充不足或填充范圍擴大化。解決方式：左閉右開

35、數(shù)據(jù)結(jié)構(gòu)活性邊表(AET):把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中，結(jié)點內(nèi)容包括:x:當前掃描線與邊的交點x坐標x:從當前掃描線到下一條掃描線間x的增量ymax該邊所交的最高掃描線號ymax指向鏈表中下一單元的指針(該結(jié)構(gòu)中隱含了y值為當前的掃描線號)P6P1P5P6P4P5P3P42-o207Axymax例5-I.。7Bxymax72I108CxymaxDxymax算法步驟：1. （AET初始化）將邊的活性邊表AET設置為空；2. （y初始化）取掃描線縱坐標y的初始值為新邊表NET中非空元素的最小序號；3. 按順序?qū)v坐標值為y的掃描線（當前

36、掃描線）執(zhí)行下列步驟，直到NET和AET都變成空為止：將AET中滿足y=ymax的邊刪去； 如果NET中的第y行元素非空，則將屬于該行的所有邊從NET中取出并插入AET中，AET中的各邊按照x值（當x的值相等時，按Ax值）遞增方向排序； 若相對于當前掃描線，AET非空，則將AET中的邊兩兩依次配對，即第1,2邊為一對，第3,4邊為一對，依此類推。每一對邊與當前掃描線的交點所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點（像素）按多邊形屬性著色； 將AET剩下的每一條邊的x域累加Ax,即令x=x+Ax; 將當前的掃描線的縱坐標值y累加，即y=y+1。4.1.2種子填充算法設計與代碼實現(xiàn)voidFl

37、oodSeedFill(intx,inty,intold_color,intnew_color)if(GetPixelColor(x,y)=old_color)(SetPixelColor(x,y,new_color);for(inti=0;i<COUNT_OF(direction_8);i+)(FloodSeedFill(x+direction_8i.x_offset,y+direction_8i.y_offset,old_color,new_color);4.2 邊標志填充算法4.2.1 邊標志填充算法基本步驟與代碼邊界填充算法與注入填充算法的本質(zhì)其實是一樣的，都是遞歸和搜索，區(qū)別只在于對邊界的確認，也就是遞歸的結(jié)束條件不一樣。注入填充算法沒有邊界的概念，