計(jì)算機(jī)圖形學(xué)課程論文

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

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

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

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

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

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

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

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

9、遞增1,y遞增k（即直線斜率）；上述分析的算法僅適用于|k|<1的情形。在這種情況下，x每增加1,y最多增加1當(dāng)|k|>1時(shí)，必須把x,y地位互換2.1.3 數(shù)值微分算法設(shè)計(jì)與代碼實(shí)現(xiàn)線段DDA算法偽代碼描述下面用偽代碼給出DDA算法。ProcedureDDA-line(x1,y1,x2,y2)BEGIN/求線段在兩坐標(biāo)軸方向改變量的較大者/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é)這種方法計(jì)算方法的缺點(diǎn)是計(jì)算量大。考慮到在計(jì)算機(jī)上實(shí)時(shí)編輯修改圖形時(shí)，連續(xù)不斷的需要在顯示器上顯示出大量的直線段，畫線的速度就會(huì)非常地慢。因此需要對(duì)上述結(jié)果詳細(xì)分析已給出較快的算法。2.2 直線中點(diǎn)畫線算法2.2.1 數(shù)值微分算法基本原理原理假設(shè)直線的斜率0<k<1；當(dāng)前像素點(diǎn)為P(xp,yp),下一個(gè)像素為Pi或P2設(shè)M=(xp+1,yp+0.5

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

12、重疊，任取R、P20如果取R,則可合并為d0時(shí)取Pi判別式d的增量算法:設(shè)確定Pi(xi,y)位置時(shí)判別式的值為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直線的起始端點(diǎn)坐標(biāo)為(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,為浮點(diǎn)運(yùn)算)整數(shù)算法:算法中僅用到判別式d的符號(hào)，所以可用2d代替d進(jìn)行遞增運(yùn)算:2.2.3 中點(diǎn)劃線算法設(shè)計(jì)與代碼實(shí)現(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都必須用浮點(diǎn)數(shù)表示，并且每一步運(yùn)算都要對(duì)y進(jìn)行舍入取整，這不利于硬件實(shí)現(xiàn)。中點(diǎn)畫線法只包含整數(shù)變量，并且不含乘除法，因而解決了上述問題2.3 直線Breseham畫線算法2.3.1 直線Breseham畫線基本原理Bresenham直線算法最初是為數(shù)字繪圖儀

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

16、i+i,yi+i)=(Xi+1,yi+m)的最近似的像素點(diǎn)的可能位置是(Xi+1,yi)或(Xi+1,yi+1)。在x=Xi+1處，直線上點(diǎn)的坐標(biāo)y=m(Xi+1)+b.該點(diǎn)與點(diǎn)(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這兩個(gè)距離的差為：d1-d2=2m(Xi+1)-2yi+2b-1這個(gè)差有如下幾何意義:?當(dāng)此值為正時(shí)，真正的直線上點(diǎn)離像素點(diǎn)(Xi+1,yi+1)較近，說明下一個(gè)直線上的像素點(diǎn)應(yīng)取(Xi+1,yi+1)。(2)當(dāng)此值為負(fù)時(shí)，真正的直線上離像素點(diǎn)(Xi+1,y

17、i)較近，說明下一個(gè)直線像素點(diǎn)應(yīng)取(Xi+1,yi)。(3)當(dāng)此值為零時(shí)，真正的直線上離上、下兩個(gè)像素點(diǎn)的距離相等，我們規(guī)定取(Xi+1,yi)作為下一個(gè)直線像素點(diǎn)。？因止匕，只要利用(di-d2)的符號(hào)就可以決定下一個(gè)像素點(diǎn)的選擇。如果我們定義一個(gè)新的判別式：?Pi=?x?(di-d2)=2?y-i-2?xiy+c(2.2.18)因此式中的?x=(X2-xi)>0,pi與(di-d2)有相同符號(hào)；?y=y2-yi；常數(shù)c=2?y+?x(2b-i)。pi的一個(gè)優(yōu)點(diǎn)是省去了(di-d2)中為了計(jì)算m所需要的除法運(yùn)算。我們知道除法運(yùn)算用硬件實(shí)現(xiàn)是比較復(fù)雜的。現(xiàn)在我們要進(jìn)一步化簡(jiǎ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)再假設(shè)直線的初始端點(diǎn)恰好是其像素點(diǎn)的坐標(biāo),即滿足：于是可得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. 直線點(diǎn)陣轉(zhuǎn)換算法(3).如果pi<0,yi+i=yi?pi+i=pi+2?y從式(2.2.20)可以看出，第i+1步

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

20、復(fù)步驟直到x逐步增加到xe為此。？在前面的處理中，我們假設(shè)m60,1。這一假設(shè)的幾何意義是要繪的直線段與x-軸的夾角不超過與y-軸的夾角?；蛘吒庇^地，直線段的方向更靠近x-軸方向，如果有m>1,則說明直線段的方向更靠近y-軸方向。如果我們互換兩個(gè)坐標(biāo)軸，則直線段就滿足前面的假設(shè)條件.因此，只要將算法中的x和y對(duì)換,則上述兩個(gè)公式依然有效。如果m<0,則相應(yīng)的只是x或y的方向的改變后，上述兩個(gè)公式依然有效。這時(shí)實(shí)際上只是改變？x或?y的符號(hào)即可.2.3.3 直線Breseham畫線算法設(shè)計(jì)與代碼實(shí)現(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é)以下是近似圖形和真實(shí)直

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、掃描線）執(zhí)行下列步驟，直到NET和AET都變成空為止：將AET中滿足y=ymax的邊刪去； 如果NET中的第y行元素非空，則將屬于該行的所有邊從NET中取出并插入AET中，AET中的各邊按照x值（當(dāng)x的值相等時(shí)，按Ax值）遞增方向排序； 若相對(duì)于當(dāng)前掃描線，AET非空，則將AET中的邊兩兩依次配對(duì)，即第1,2邊為一對(duì)，第3,4邊為一對(duì)，依此類推。每一對(duì)邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對(duì)這些區(qū)段上的點(diǎn)（像素）按多邊形屬性著色； 將AET剩下的每一條邊的x域累加Ax,即令x=x+Ax; 將當(dāng)前的掃描線的縱坐標(biāo)值y累加，即y=y+1。4.1.2種子填充算法設(shè)計(jì)與代碼實(shí)現(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 邊標(biāo)志填充算法4.2.1 邊標(biāo)志填充算法基本步驟與代碼邊界填充算法與注入填充算法的本質(zhì)其實(shí)是一樣的，都是遞歸和搜索，區(qū)別只在于對(duì)邊界的確認(rèn)，也就是遞歸的結(jié)束條件不一樣。注入填充算法沒有邊界的概念，