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

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

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

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

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

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

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

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

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

9、利用此原理來(lái)判斷觀察點(diǎn)位于物體表面的哪一面，如位于背面一側(cè) ，則表面不可見(jiàn)，應(yīng)被消隱；反之則可見(jiàn)。 對(duì)物體得任意表面，可將其劃分為若干個(gè)平面，在根據(jù)平面上任意三點(diǎn)的坐標(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）為平面上已知得三點(diǎn)坐標(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è)觀察點(diǎn)坐標(biāo)為（x, y, z），如果 ax+by+cz+d = 0，則觀察點(diǎn)（x, y, z） 位于平面上； ax+by+cz+d 0，則觀察點(diǎn)（x, y, z）位于平面背面一側(cè)，平面 不可見(jiàn)，應(yīng)被隱藏； ax+by+cz+d 0，則平面不可見(jiàn)，應(yīng)被隱藏； d 0，則物體表面是可見(jiàn)的朝向觀察點(diǎn)的面；如果，則物體表面是不可見(jiàn)的背向觀察點(diǎn)的面，應(yīng)被消隱。 設(shè)為向量和之間的夾角，視向量的長(zhǎng)度為線段op 的長(zhǎng)度|op|，則根據(jù)向量點(diǎn)積的定義可知=|op|cos 。如果 0，則cos 0（ 即 0）； 反之，

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

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

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

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

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

16、的實(shí)現(xiàn)void cmyview:project(float x, float y, float z)/ 此函數(shù)求點(diǎn)的平行投影和透視投影坐標(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)/ 用三維點(diǎn)坐標(biāo)直接從當(dāng)前點(diǎn)畫線到一點(diǎn)的函數(shù) project(x, y, z); / 將三維點(diǎn)作投影 xscreen = floor(0.5 + xproj * scale +150); / 圓整 yscreen = floor(0.5 + 100 - yproj); / 圓整 pdc-lineto(xscreen, yscreen); / 畫線到一點(diǎn)void cmyview:wmoveto(float x, float y, float z,cdc*pdc)/ 三維坐標(biāo)下直接將當(dāng)前點(diǎn)移動(dòng)到某點(diǎn)的函數(shù) project (x, y, z); / 將三維點(diǎn)作投影 xscreen = floo

18、r(0.5 + xproj * scale + 150); / 圓整 yscreen = floor(0.5 + 100 - yproj); / 圓整 pdc-moveto(xscreen, yscreen); /移動(dòng)到某點(diǎn)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、面三個(gè)頂點(diǎn)調(diào)用求該表面的法矢 / st_i is the i_th point of a face. float p1, p2, p3, q1, q2, q3; / 求一個(gè)向量p1 = stst21 - stst11;p2 = stst22 - stst12;p3 = stst23 - stst13; / 求另一個(gè)向量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ù)量積大于零，表面可見(jiàn)，畫出此表面 pdc-selectobject(poldpen); releasedc(pdc);void cmyview:visionpoint()/ 此函數(shù)用于給出視點(diǎn)位置/ 投影時(shí)初始值即正弦值和余弦值及其乘積的計(jì)算、賦值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; /給出視點(diǎn)位置 o1 = rol * aux7; o2 = rol * aux8; o3 = rol * aux2;void cmyview:mydraw()redrawwindow();readvertics();readfaces();/ 繪出透視投影下的凸多面體圖形visionpoint(); / 給出視點(diǎn)位置 drawobject(); /

23、畫出立體的圖形/ cmyview message handlersvoid cmyview:onkeydown(uint nchar, uint nrepcnt, uint nflags) /此函數(shù)用來(lái)利用上下左右鍵移動(dòng)視點(diǎn)角度位置,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;/計(jì)算頂點(diǎn)坐標(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