《計算機圖形學(xué)》課程設(shè)計簡單幾何體的消隱算法實現(xiàn)

1、課程名稱：計算機圖形學(xué)論文題目：簡單幾何體的消隱算法實現(xiàn)教學(xué)部： 年 級： 班 級： 學(xué) 號： 姓 名： 簡單幾何體的消隱算法實現(xiàn)摘 要：用計算機生成三維物體的真實圖形是計算機圖形學(xué)研究的重要內(nèi)容。真實圖形在仿真模擬、幾何造型、廣告影視、指揮控制和科學(xué)計算的可視化等許多領(lǐng)域都有廣泛應(yīng)用。經(jīng)過消隱得到的投影圖稱為物體的真實圖形。較常用的消隱算法有畫家算法、z-buffer算法及其它一些改進算法。消隱算法從算法基本思想、算法描述和算法步驟等方面對畫家算法、z-buffer算法和其它改進算法進行了分析,并得出了它們相關(guān)的特點。并在vc+中實現(xiàn)了z-buffer算法和區(qū)域子分割算法。關(guān)鍵詞：z-buf

2、fer算法；背面消除法；消隱算法近年來，產(chǎn)生真實的虛擬環(huán)境是計算機圖形學(xué)孜孜以求的目標(biāo)。在虛擬對象或場景的創(chuàng)建中要用到許多綜合處理過程，每一種都非常令人感興趣也非常重要。計算機輔助設(shè)計、科學(xué)可視化、模擬訓(xùn)練、醫(yī)療成像、娛樂、廣告等等，所有的這些，都要依賴于當(dāng)今最前沿的計算機圖形技術(shù)。伴隨著計算機硬件、軟件的飛速發(fā)展，計算機圖形學(xué)技術(shù)也得到了質(zhì)的飛躍。特別是面向?qū)ο蠹夹g(shù)和多媒體技術(shù)取得的成功，使得圖形學(xué)成為計算機軟件業(yè)中一個重要的分支。而程序設(shè)計方法、數(shù)據(jù)庫系統(tǒng)和人工智能等新技術(shù)滲入到計算機圖形學(xué)領(lǐng)域，又為計算機圖形學(xué)提供了更加寬闊的發(fā)展空間和強勁動力。計算機圖形學(xué)是研究通過計算機將數(shù)據(jù)轉(zhuǎn)換成圖

3、形，并在專用顯示設(shè)備上顯示的原理、方法和技術(shù)的學(xué)科。主要介紹了計算機圖形系統(tǒng)的基本知識，圖形生成與顯示的算法，圖形的表示與圖形的數(shù)據(jù)結(jié)構(gòu)，圖形的幾何變換與投影變換，圖形的裁剪技術(shù)，圖形消隱處理，真實感圖形的生成等內(nèi)容。面消隱作為圖形學(xué)中一個分支是本文的一個重要的研究內(nèi)容。一 圖形學(xué)中的面消隱概述 （一）面消隱的基本概念由于屏幕上的一些圖元被另一些圖元擋住所造成的。例如，當(dāng)需要描繪一個由多邊形面組成的三維物體時，那么它的一部分必然要被擋住，要在屏幕上顯示的必須是可見的東西。打個比方，對于一個立方體，無論從哪個方向進行透視處理，最多只能看到其中的三個面。這樣，就要想出一種方法來決定哪些面是所能看到

4、的。 如果使用從屏幕到世界的視處理方法，那么很自然的就能保證只有圖元上正確的部分才顯示在屏幕上。在這種視處理中，可見性在屏幕的每一個像素上進行判斷。從人眼發(fā)出一條射線，穿過一個給定的像素，那么首先與這條射線相交的表面在這一個像素上就是可見的。從這個表面反射的光線能夠進入我們的眼睛。 用計算機生成三維物體的真實圖形，是計算機圖形學(xué)研究的重要內(nèi)容。真實圖形在仿真模擬、幾何造型、廣告影視、指揮控制和科學(xué)計算的可視化。等許多領(lǐng)域都有廣泛應(yīng)用。在用顯示設(shè)備描述物體的圖形時，必須把三維信息經(jīng)過某種投影變換，在二維的顯示表面上繪制出來。由于投影變換失去了深度信息，往往導(dǎo)致圖形的二義性。要消除二義性，就必須在

5、繪制時消除被遮擋的不可見的線或面，習(xí)慣上稱作消除隱藏線和隱藏面，或簡稱為消隱。經(jīng)過消隱得到的投影圖稱為物體的真實圖形。消隱算法是把線框圖變成實體圖必要的算法。通過看相關(guān)的報道知道，地面勘測衛(wèi)星，氣象衛(wèi)星等要不斷的向地面的工作站發(fā)送圖片資料來幫助技術(shù)人員進行研究。而那個量是非常龐大的，因而接收到圖像時往往是已經(jīng)過壓縮和消隱后得到的圖片。由于最普通的圖元就是多邊形，所以討論的許多技術(shù)都是只針對多邊形模型的。由此將重點討論用于多邊形地形、體素模型的一些技術(shù)，為了能夠更深入的了解消隱有關(guān)的基本知識，做了如下的一些介紹和研究。（二） 常用的面消隱算法面消隱是計算機生成三維物體的真實圖形的重要內(nèi)容，最常用

6、最基本的消隱算法有畫家算法，平面公式法，背面消除法，徑向預(yù)排序法，z-buffer算法。它們的基礎(chǔ)都是背面消隱原理，所謂背面消隱原理， 即相對觀察點來說朝向后面的物體表面是 不可見的，應(yīng)被隱藏。二 簡單幾何體的消隱算法（一） 畫家算法1算法的基本思想畫家算法（也稱為深度排序方法）比較適合于處理簡單多面體的消隱問題其主要思想是將多面體要顯示的各個面按照距離視點的遠近進行排序，如果有相互部分遮擋的情況，則按照交線將其分成更小的面再進行排序，同時將排序的結(jié)果放置在一個表中當(dāng)要顯示這個多面體時，就按照這個表的順序，也就是按照與視點的距離由遠及近地依次顯示各個多邊形面這樣如果某些面之間有重疊，也只可能是

7、離視點較近的面遮住較遠的面，從而就自然而然地解決了消隱的問題，就象是畫家在畫油畫時一般先畫背景，然后再畫中間的景物。2 算法過程的描述畫家算法是比較適合于處理簡單多面體的消隱問題，具體過程描述如下： step1:將屏幕設(shè)成背景色step2:把要畫的物體（多邊形）按其離開視點的從遠到近排序。由此構(gòu)成深度優(yōu)先級表。然后從遠到近畫物體（多邊形），近的就因為優(yōu)先級高而覆蓋遠的多邊形。由此可消隱。3 多邊形優(yōu)先級的考慮畫家算法是按照與視點的距離由遠及近地依次顯示各個多邊形面，所以多邊形優(yōu)先級的判定是很重要的。判定過程具體描述如下：step1:首先對一個簡單的畫面，如圖3-1（a）所示可以直接建立一個確定

8、的深度優(yōu)先表，排序可以一次完成，不會有任何的歧義。例如，多邊形可按其最大或最小值排序，都可以很容易地把它們按深度大小分開。step2:但是，當(dāng)畫面略微復(fù)雜一點，如圖3-1（b）所示，卻無法按簡單的z向排序建立確定的深度優(yōu)先表，以確定每一個多邊形的優(yōu)先級。例如，若按最小z坐標(biāo)值（zmin）對p、q排序，則在深度優(yōu)先表中，p應(yīng)排在q之前，如按此順序?qū)、q寫入幀緩沖器，則q將部分地遮擋p。但實際上是p部分地遮擋q。如果按最大z坐標(biāo)值（zmax）對p、q排序，同樣也不能得到正確的消隱結(jié)果。（二） 平 面 公 式 法 根據(jù)解析幾何原理，通過標(biāo)準(zhǔn)的平面方程可以判斷給定點是在平面的正面還是背面。平面公式法

9、利用此原理來判斷觀察點位于物體表面的哪一面，如位于背面一側(cè) ，則表面不可見，應(yīng)被消隱；反之則可見。 對物體得任意表面，可將其劃分為若干個平面，在根據(jù)平面上任意三點的坐標(biāo)可以求得其平面方程。標(biāo)準(zhǔn)得平面方程為 ax+by+cz+d = 0; 其中a、b、c、d為決定平面得常數(shù)。如果（x1, y1, z1）、（x2, y2, z2）、（x3, y3, z3）為平面上已知得三點坐標(biāo)，則可求得a、b、c、d 如下： a=y1(x2-x3)+y2(z3-z1)+y3(z1-z2);b=z1(x2-x3)+z2(x3-x1)+z3(x1-x2);c=x1(y2-y3)+x2(y3-y1)+x3(y1-y2)

10、;d=-x1(y2z3-y3z2)-x2(y3z1-y1z3)-x3(y1z2-y2z1); 設(shè)觀察點坐標(biāo)為（x, y, z），如果 ax+by+cz+d = 0，則觀察點（x, y, z） 位于平面上； ax+by+cz+d 0，則觀察點（x, y, z）位于平面背面一側(cè)，平面 不可見，應(yīng)被隱藏； ax+by+cz+d 0，則平面不可見，應(yīng)被隱藏； d 0，則物體表面是可見的朝向觀察點的面；如果，則物體表面是不可見的背向觀察點的面，應(yīng)被消隱。 設(shè)為向量和之間的夾角，視向量的長度為線段op 的長度|op|，則根據(jù)向量點積的定義可知=|op|cos 。如果 0，則cos 0（ 即 0）； 反之，

11、如果，則cos 0（ 即 ）。 因此，背面消除法的判據(jù)簡化為： cos 0，則物體表面不可見，應(yīng)被消隱；cos 0則物體表面可見，應(yīng)被畫出。 根據(jù)面法向量的定義可知，在平面上按逆時針方向選取p1（x1, y1, z1）、p2（x2, y2, z2）、p3（x3, y3, z3）三點，則經(jīng)過投影變化后，視向量與z軸是平行的，因此向量和之間的夾角即為z 軸與向量的夾角，所以由 于|0， 所以cos 的正負取決于c，因此背面消除法的判據(jù)轉(zhuǎn)化為：c 0，則物體表面不可見，應(yīng)被消隱；c 0，則物體表面可見，應(yīng)被畫出。（四） 徑 向 預(yù) 排 序 法 徑向預(yù)排序法根據(jù)物體在三維坐標(biāo)系xy 平面中的角位置來判

12、斷哪些物體 擋住了其它物體，物體的哪些表面擋住了其它表面。對具有相同角位置的物體或表面，與觀察點較近的將擋住較遠的。 徑向預(yù)排序法示例 徑向預(yù)排序法消隱的要點是先對物體及物體的表面進行由遠及近的排序 對具有相同角位置的物體或表面，先畫較遠的，后畫較近的，這樣如果較近的物體或表面擋住了較遠的物體或表面，則被遮擋的部分被覆蓋而實現(xiàn)消隱。但對具 有不同角位置的物體或表面，先畫哪一個可根據(jù)需要來決定。如果存在凹面物體的消隱，一般應(yīng)先畫物體中心部分，再畫物體的兩側(cè)，以正確地表現(xiàn)互相重疊的凹面模型。 徑向預(yù)排序法可以對任意形狀的物體進行消隱處理。但需要預(yù)先知道觀察角度，并根據(jù)角位置對物體的畫圖順序預(yù)先排序

13、。而且構(gòu)造模型的編碼受到這種排序的限制，模型不能進行旋轉(zhuǎn)變換。 （五） 徑 向 排 序 法 徑向排序法是對徑向預(yù)排序法的改進算法，使得構(gòu)造模型的編碼能根據(jù)觀察角度的變化，來自動調(diào)整物體或表面的遠近順序即畫圖順序，以實現(xiàn)對模型的旋轉(zhuǎn)變換，以便能從不同的角度來觀察物體。算法需要檢測旋轉(zhuǎn)變換的角度，并隨角度的變化而調(diào)整物體或表面的遠近順序。 （六） z 緩 沖 區(qū) 法 z緩沖區(qū)法首先建立一個大的緩沖區(qū)，用來存儲三維物體沿z軸透視投影而得到的二維圖形的所有象素的值，因此叫做z緩沖區(qū)。z 緩沖區(qū)的單元個數(shù)與屏幕上象素點的個數(shù)相同，也和幀緩沖區(qū)的單元個數(shù)相同，而且它們之間是一一對應(yīng)的z 緩沖區(qū)每個單元的大

14、小取決于圖形在觀察坐標(biāo)系中z方向的變化范圍。緩區(qū)的每個單元的值是對應(yīng)象素點所對應(yīng)的物體表面點坐標(biāo)值。 利z 緩沖區(qū)法進行消隱和造型的過程就是對屏幕中每一點進行判斷并給幀 緩沖區(qū)z 緩沖區(qū)中相應(yīng)單元進行賦值的過程?，F(xiàn)用形式化語言描述該算法如下： z緩沖區(qū)消隱算法1）將幀緩沖區(qū)各單元的值置為背景色值;2）將z緩沖區(qū)各單元的值置為z坐標(biāo)可能出現(xiàn)的最大值;3）循環(huán)：對每一物體循環(huán)：對物體每一面的每一點（x, y, z）i)對（x, y, z）做透視投影變換，得到變換后的x、y坐標(biāo)（x*, y*）；ii)如果z緩沖區(qū)中（x*, y*）對應(yīng)單元的值小于z，則 a)將z緩沖區(qū)中（x*, y*）對應(yīng)單元的值置

15、為z;b)將幀緩沖區(qū)中（x*, y*）對應(yīng)單元的值置為點（x, y, z）的屬性值（通常是亮度、顏色值或顏色查找表的索引值）;iii)如果z緩沖區(qū)中（x*, y*）對應(yīng)單元的值大于z，則 a)說明目前幀緩沖區(qū)中（x*, y*）對應(yīng)單元的所表示的物體上點比點（x, y, z）更接近觀察點，即點（x, y, z）應(yīng)被消隱；b)將z緩沖區(qū)和幀緩沖區(qū)中（x*, y*）對應(yīng)單元的值均保持不變；4）循環(huán)：對屏幕上每一點（x*, y*）根據(jù)幀緩沖區(qū)中（x*, y*）對應(yīng)單元的值畫出象素點。 z 緩沖區(qū)消隱算法簡單、可靠，而且消隱和表現(xiàn)效果很好。 但需要的內(nèi)存 容量大，運算復(fù)雜，費時。 三 消隱算法在vc+下

16、的實現(xiàn)void cmyview:project(float x, float y, float z)/ 此函數(shù)求點的平行投影和透視投影坐標(biāo)值 xobs = -x * aux1 + y * aux3; yobs = -x * aux5 - y * aux6 + z * aux4; / 求透視投影坐標(biāo)值 zobs = -x * aux7 - y * aux8 - z * aux2 + rol; xproj = de * xobs / zobs; yproj = de * yobs / zobs;void cmyview:wlineto(float x, float y, float z,cdc*p

17、dc)/ 用三維點坐標(biāo)直接從當(dāng)前點畫線到一點的函數(shù) project(x, y, z); / 將三維點作投影 xscreen = floor(0.5 + xproj * scale +150); / 圓整 yscreen = floor(0.5 + 100 - yproj); / 圓整 pdc-lineto(xscreen, yscreen); / 畫線到一點void cmyview:wmoveto(float x, float y, float z,cdc*pdc)/ 三維坐標(biāo)下直接將當(dāng)前點移動到某點的函數(shù) project (x, y, z); / 將三維點作投影 xscreen = floo

18、r(0.5 + xproj * scale + 150); / 圓整 yscreen = floor(0.5 + 100 - yproj); / 圓整 pdc-moveto(xscreen, yscreen); /移動到某點void cmyview:visionvector(int st1) /* 該函數(shù)用于求觀察方向矢量 st1 is the first point of a face. */ v1=o1-stst11; v2=o2-stst12; v3=o3-stst13;void cmyview:normalvector(int st1, int st2, int st3)/ 此函數(shù)用表

19、面三個頂點調(diào)用求該表面的法矢 / st_i is the i_th point of a face. float p1, p2, p3, q1, q2, q3; / 求一個向量p1 = stst21 - stst11;p2 = stst22 - stst12;p3 = stst23 - stst13; / 求另一個向量q1 = stst31 - stst11;q2 = stst32 - stst12;q3 = stst33 - stst13; /用向量積求法向量n1 = p2 * q3 - q2 * p3;n2 = p3 * q1 - q3 * p1;n3 = p1 * q2 - q1 * p

20、2;float cmyview:scaleproduct(float v1, float v2, float v3, float n1, float n2, float n3)/ 此函數(shù)用于求觀察方向矢量與表面法矢的數(shù)量積 float sproduct;sproduct = v1 * n1 + v2 * n2 + v3 * n3;return(sproduct);void cmyview:drawface(cdc*pdc)/ 畫出立體上的平面 int s, ns, no; float x, y, z, x0, y0, z0; ns = fcf0; for ( s = 1; sselectobj

21、ect(&pen1); for ( f = 1; f 0 ) / 判斷數(shù)量積正否 pdc-selectobject(&pen1); drawface(pdc); / 數(shù)量積大于零，表面可見，畫出此表面 pdc-selectobject(poldpen); releasedc(pdc);void cmyview:visionpoint()/ 此函數(shù)用于給出視點位置/ 投影時初始值即正弦值和余弦值及其乘積的計算、賦值float th, ph; th = 3.1415926 * theta / 180; ph = 3.1415926 * phi / 180; aux1 = sin(th); aux2

22、 = sin(ph); aux3 = cos(th); aux4 = cos(ph); aux5 = aux3 * aux2; aux6 = aux1 * aux2; aux7 = aux3 * aux4; aux8 = aux1 * aux4; /給出視點位置 o1 = rol * aux7; o2 = rol * aux8; o3 = rol * aux2;void cmyview:mydraw()redrawwindow();readvertics();readfaces();/ 繪出透視投影下的凸多面體圖形visionpoint(); / 給出視點位置 drawobject(); /

23、畫出立體的圖形/ cmyview message handlersvoid cmyview:onkeydown(uint nchar, uint nrepcnt, uint nflags) /此函數(shù)用來利用上下左右鍵移動視點角度位置,c鍵切換投影類型.switch(nchar)case vk_up:/上下左右鍵選擇phi=phi-incang;mydraw();break;case vk_down:phi=phi+incang;mydraw();break;case vk_right:theta=theta+incang;mydraw();break;case vk_left:theta=th

24、eta-incang;mydraw();break;default:break;void cmyview:ontumianti() rol = 600.0;s=1;theta = 60;phi = 135;de = 1000;mydraw();cdc*pdc=getdc();pdc-textout(10,10,按下鍵盤上的“上”、“下”、“左”、“右”箭頭可從各方位觀看圖形);releasedc(pdc);void cmyview:onyuanjin() / todo: add your command handler code hereredrawwindow();cclientdc *pd

25、c=new cclientdc(this);cpen *pen1=new cpen(ps_solid,1,rgb(0,0xff,0);cpen *pen2=new cpen(ps_solid,1,rgb(255,0,0);cpen *oldpen=pdc-selectobject(pen1);cbrush brush;brush.createsolidbrush(rgb(0,0,0);cbrush *oldbrush=(cbrush*)pdc-selectobject(&brush);int flag,col,r,ww,k1,k2,r1,r2,n,d,m,p,osw,osh,left,top;

26、int xs1,xs2,xs3,xs4,ys1,ys2,ys3,ys4,i,j,lastp;double x,y,z,cx,cy,cz,thx,th1,th3,yw,zw,xw,thy,th,th2;double pi,ed,od,eh,zzw,ppw;double xs5017,zs5017,ys5017,zc5017,x1,y1;int zz850,pp850;r1=100;r2=40;k1=20;k2=16;ed=1500; eh=0;od=0;n=0;pi=3.14159;th3=1;thx=0.9;/計算頂點坐標(biāo)值for(d=-1;d=1;d+=2) for(th1=0; th1=2

27、*pi+0.1;th1+=2*pi/k1)n=n+1; m=0;for(th2=0;th2=2*pi+0.1;th2+=2*pi/k2)m=m+1;x=r1+r2*cos(th2);y=r2*sin(th2);z=0;thy=th1;zw=z; xw=x;x=zw*cos(thy)-xw*sin(thy);z=zw*sin(thy)+xw*cos(thy);x=x+r1/2*d;if(d=1) yw=y; zw=z; y=yw*cos(pi/2)-zw*sin(pi/2); z=yw*sin(pi/2)+zw*cos(pi/2);thy=th3;zw=z; xw=x;x=zw*cos(thy)-xw*sin(thy);z=zw*sin(thy)+xw*cos