圖形學(xué)實(shí)驗(yàn)七課件

1、貴州大學(xué)實(shí)驗(yàn)報(bào)告學(xué)院： 計(jì)信學(xué)院 專業(yè)：計(jì)科 班級(jí)：計(jì)科101姓名羅琳學(xué)號(hào)1008060016實(shí)驗(yàn)組無(wú)實(shí)驗(yàn)時(shí)間2013-4-29指導(dǎo)教師吳云成績(jī)實(shí)驗(yàn)項(xiàng)目名稱消隱實(shí)驗(yàn)?zāi)康恼莆粘Ｓ玫牟脺p及消隱算法：直線、多邊形的裁減；消除隱藏面算法：Roberts消隱算法、Z緩沖器算法、掃描線Z緩沖器算法、光線跟蹤算法。實(shí)驗(yàn)要求分別實(shí)現(xiàn)一個(gè)直線裁減算法、多邊形的裁減算法、面消隱算法實(shí)驗(yàn)原理Roberts消隱算法算法原理：Roberts消隱算法是在圖像空間實(shí)現(xiàn)的消隱算法，數(shù)學(xué)處理嚴(yán)謹(jǐn)，計(jì)算量甚大。Roberts算法要求所有被顯示的物體都是凸的，因此對(duì)凹體要先分割成許多個(gè)凸體的組合。此算法的基本步驟是：l 逐個(gè)的獨(dú)立

2、的考慮每個(gè)物體自身，找出為其自身所遮擋的邊和面；l 將每一物體上留下的邊再與其它物體逐個(gè)的進(jìn)行比較，以確定其是完全可見(jiàn)還是部分或全部被遮擋；l 確定由于物體之間的相互貫穿等原因，是否要形成新的顯示邊等。從而使被顯示各物體更接近現(xiàn)實(shí)。下面先介紹一些用到的一些基本概念以及有關(guān)的數(shù)學(xué)方法。l 體矩陣：假設(shè)在三維空間中，一平面的方程表示為：ax+by+cz+d=0,令P=a,b,c,d，表示平面的系數(shù)向量；又令S=x,y,z,1，表示三維空間重點(diǎn)的其次坐標(biāo)。上式改寫為：S·PT=0。所以凸體可由平面方程系數(shù)組成的體矩陣表示：矩陣的每一列表示物體的對(duì)應(yīng)平面方程的系數(shù)，其列數(shù)與物體的面數(shù)一致。由

3、于當(dāng)PT是一平面系數(shù)時(shí)，-PT也是該平面的系數(shù)，因此為了計(jì)算的需要，Roberts算法規(guī)定：對(duì)平面多面體內(nèi)部的任一點(diǎn)S0，要使得 S0·V=Q=q1,q2,q3,qn式中的每一個(gè)分量qi都不小于零(i=1,2,n)。適當(dāng)選取物體內(nèi)部一點(diǎn)S0，用以測(cè)試單調(diào)態(tài)平面系數(shù)的符號(hào)，使其滿足Roberts算法的規(guī)定，這是本算法最基本的一步。平面系數(shù)的計(jì)算方法： 方法一：根據(jù)平面上的已知點(diǎn)，求解線性方程組。已知平面上不共線三點(diǎn)(x1,y1,z1)，(x2,y2,z2)，(x3,y3,z3)，得到規(guī)范方程組：寫成矩陣形式為：記為：XC=D，解得平面方程系數(shù)為：C=X-1D 方法二：根據(jù)平面的法矢量和

4、平面上一已知點(diǎn)，求得平面系數(shù)。已知平面的法矢量為：n=ai+bj+ck，其中i，j，k分別為x，y，z方向的單位矢量，且又已知平面上一點(diǎn)(x1,y1,z1)。則平面方程是：  ax+by+cz+d=0，其中   d=-(ax1+by1+cz1) 方法三：采用Martin Newell方法，即最佳逼近法，計(jì)算任何平面多邊形所在平面的精確方程或接近于平面的多邊形的最佳逼近平面方程。假設(shè)給定n個(gè)點(diǎn)(xi,yi,zi)(i=1,2,n)，則平面系數(shù)可用于下式計(jì)算：其中：若in，則j=i+1，否則j=1。d可由下式求得：d=-(ax1+by1+cz1) 體矩陣的變換在消隱算

5、法執(zhí)行之前，為了得到從一指定的試點(diǎn)以給定的觀察方向來(lái)看所需要顯示的物體，常常先要對(duì)物體進(jìn)行三維坐標(biāo)變換。因此，在變換確定之后，或給定了變換矩陣T以后，需要對(duì)每一個(gè)物體的體矩陣V作一個(gè)相應(yīng)的變換，得到變換后的體矩陣VT。同時(shí)，還要對(duì)物體的頂點(diǎn)齊次坐標(biāo)矩陣B作一個(gè)相應(yīng)的變換，得到變換后的頂點(diǎn)齊次坐標(biāo)矩陣BT。有兩種常用的計(jì)算VT的方法： 方法一：假設(shè)B與BT分別為在體矩陣變換前后的物體頂點(diǎn)齊次坐標(biāo)構(gòu)成的矩陣，則 BT=BT因?yàn)橛蠿C=D，所以可得到該物體原各平面的方程為： BV=D 其中：D為零矩陣。同樣，變換后的平面方程也可表示為：BTVT=D并且：BTVT=BV 代入到BT=BT，方程兩邊消去

6、B并左乘T-1，得到：VT=T-1V;所以，變換后的體矩陣是由原來(lái)的體矩陣左乘變換矩陣的逆矩陣而得到的。 方法二：假設(shè)原先并未計(jì)算形體矩陣V，也不希望計(jì)算T的逆矩陣，則可光計(jì)算：BT=BT,然后用變換后的物體頂點(diǎn)坐標(biāo)BT，按照前面介紹的Martin Newell方法，直接計(jì)算變換后的體矩陣VT，兩種方法所得結(jié)果完全一致。 視方向朝向z軸負(fù)向無(wú)窮遠(yuǎn)處 視方向朝向z軸正向無(wú)窮遠(yuǎn)處 結(jié)果圖 自消隱方法:自消隱是對(duì)物體自身所遮擋的面(自隱面)和邊(自隱邊)的消除。對(duì)于不同的視點(diǎn)及視方向，既是對(duì)同一個(gè)物體來(lái)說(shuō)，也會(huì)產(chǎn)生不同的自隱面和自隱邊。因此自隱面和自隱邊不僅取決于物體的形狀，而且與視點(diǎn)方向相關(guān)。假設(shè)

7、視點(diǎn)位于z的負(fù)無(wú)窮遠(yuǎn)處，視方向?yàn)閦軸的正向，即視方向朝z軸正向無(wú)窮遠(yuǎn)處，在齊次坐標(biāo)系中，該方向矢量為：E=0,0,1,0顯然，若視方向E和體矩陣VT的乘積中有負(fù)的元素，則E在這此元素對(duì)應(yīng)的面與形體相對(duì)的另一側(cè)，而這正說(shuō)明這些面被物體自身所遮擋。所以利用 E·VT=w1,w2,wn(表示視線與表面內(nèi)法線矢量夾角關(guān)系)尋找所有wi0的i值，其對(duì)應(yīng)面即為自隱面，可被消除。 當(dāng)找到了所有的自隱面之后，就可以確定自隱線，自隱線的確定方法是：若相交的兩各平面都是自隱面的話，它們的相交邊線就是自隱線，可以消除，否則為物體的可見(jiàn)邊線。在確定了自隱面和自隱線之后，該物體余下的邊線應(yīng)當(dāng)與其它物體一一比較

8、，以確定他們是否為其他物體所遮擋。為了提高算法的執(zhí)行效率，應(yīng)先將一些很明顯由很容易確定的不必要的比較排除在外，常用的一些方法是最大最小測(cè)試法和邊框測(cè)試法等。最大最小測(cè)試法是對(duì)要被顯示的每一個(gè)物體，以其最小Z值(即最靠近視點(diǎn)的點(diǎn))進(jìn)行排序，由大到小組成一個(gè)Z值的表，比較某一邊線，若它的最大Z值小于表中某一元素，則從該元素起及其以后的元素所對(duì)應(yīng)的物體均不可能遮擋該邊線，所以不用進(jìn)一步的比較。邊框測(cè)試法是為較復(fù)雜物體加上如球或長(zhǎng)方體之類的邊框，這樣只要能確定某些邊線完全處于這些框的上面、下面、左面、右面后前面時(shí)，邊框內(nèi)的物體就不會(huì)遮擋該邊線。優(yōu)先級(jí)1優(yōu)先級(jí)2分割平面yz最大最小測(cè)試法如下：若物體1的

9、最大Z值物體2的最小Z值, 則物體1的優(yōu)先級(jí)為1,物體2的優(yōu)先級(jí)為2 優(yōu)先級(jí)小的物體離視點(diǎn)距離較近 優(yōu)先級(jí)小的物體可能遮擋優(yōu)先極大的物體 優(yōu)先級(jí)小的物體先投影(x_maxp , y_maxp )(x_maxe , y_maxe )(x_mine , y_mine )(x_minp , y_minp )邊框測(cè)試法如下：判斷下式：x_minpx_maxe ORx_minex_maxp ORy_minpy_maxe OR y_miney_maxpl 若上式為真，邊與多邊形不相交；若上式為假，二邊框相交，但邊與多邊形可能相交，可能不相交，需進(jìn)行第二次邊框測(cè)試。l 第二次邊框測(cè)試：把邊的邊框和多邊形的每

10、條邊的邊框進(jìn)行比較，進(jìn)行交點(diǎn)測(cè)試。l 交點(diǎn)測(cè)試：對(duì)求出的交點(diǎn)，判別其是否同時(shí)在邊或多邊形邊上(交點(diǎn)的x,y值是否在邊的范圍內(nèi))， 若是，邊與多邊形的邊相交；若不是，邊與多邊形的邊不相交。邊線與物體的比較方法:p1p2gE完成上述工作后，還有一定數(shù)量的邊要通過(guò)與其它物體的比較后方能確定其可見(jiàn)性。假設(shè)考慮邊線P1P2的可見(jiàn)性，被比較的物體體矩陣為VT。采用直線的參數(shù)表示形式：P(t)=P1+(P2-P1)t 0t1 或 v=s+dt 0t1其中：v是邊線上點(diǎn)的位置矢量，s是起始點(diǎn)，d為直線的方向。再構(gòu)造由P1P2上一點(diǎn)至視點(diǎn)的直線，其參數(shù)表示形式為：Q(,t)=u=v+g=s+dt+g(0t1,0

11、)其中：g=0,0,-1,0,與視線方向E=0,0,1,0相反，且與t的意義相同。給定一個(gè)t值，對(duì)應(yīng)邊線P1P2上的一點(diǎn)P(t)，同樣對(duì)于給定一個(gè)值，則決定了從該點(diǎn)至視點(diǎn)線段上的一點(diǎn)。所以Q(,t)可以看作是定義了這平面上的一點(diǎn)集,給定和t，就確定了這個(gè)平面上的一點(diǎn)。總是取正值，這是因?yàn)橹挥衅矫娴倪@一區(qū)域才能包含遮擋上述邊線的物體。如果物體于平面的交集不定，且落在點(diǎn)集Q(,t)中，則這個(gè)物體部分或全部地遮擋邊線P1P2。否則，P1P2就不會(huì)被這個(gè)物體所遮擋。 現(xiàn)在把邊線的對(duì)于給定物體的可見(jiàn)性問(wèn)題，轉(zhuǎn)為物體與整個(gè)點(diǎn)集之交是否為空集的問(wèn)題。因?yàn)榍懊嬉呀?jīng)規(guī)定：物體中的點(diǎn)與體矩陣的乘積所產(chǎn)生的向量中所

12、有元素均為非負(fù)數(shù)。所以，H=u·VT=s·VT+t·dVT+·gVT0(0t1，0)對(duì)于物體中的每個(gè)面j=1,2,n，使得 hj=pj+tqj+wj0 (0t1，0)其中pj，qj，wj，hj分別為向量P，Q，W，H的分量：P=(p1,p2,pn)=s·VTQ=(q1,q2,qn)=d·VTW=(w1,w2,wn)=g·VTH=(h1,h2,hn)=Q(,t)·VT于是，可見(jiàn)與不可見(jiàn)的臨界條件是hj=0。當(dāng)hj=0時(shí)，該點(diǎn)恰好位于對(duì)應(yīng)的平面上。若對(duì)物體的每一平面取hj=0，可得有關(guān)和t的聯(lián)立方程組。為了求解這個(gè)方程

13、組，可將其中的方程兩兩聯(lián)立，得到所有可能的和t值?？赡艿慕獾目倲?shù)為n(n-1)/2。然后在(0t1,0)范圍內(nèi)求出t的最小值tmin和最大值tmax和相應(yīng)的值。對(duì)于tminttmax,必須0，使得Q(,t)落在物體中，所有這樣的t值是邊線上被遮擋的點(diǎn)，對(duì)于那些=0的解，說(shuō)明邊線真正貫穿了物體。要保存這些貫穿點(diǎn)，然后連接這些貫穿點(diǎn)，得到的貫穿線再與其它物體相比較，其中可見(jiàn)部分就是可見(jiàn)貫穿線?？梢?jiàn)貫穿線若下圖所示: 紅色處為貫穿點(diǎn)的位置紫色為可見(jiàn)貫穿線，黃色為不可見(jiàn)貫穿線 (不可見(jiàn)貫穿線僅列出幾條)上述方法的計(jì)算量很大，下面介紹一種判別完全可見(jiàn)線段的方法，可節(jié)省計(jì)算量。 該方法的基本思想是判斷一線

14、段的兩端點(diǎn)是否位于視點(diǎn)和一可見(jiàn)面之間，若是，則完全可見(jiàn)。根據(jù) u=s+dt+g (0t1,0) 當(dāng)=0時(shí)，u表示該邊線本身，此時(shí)當(dāng)t=0和t=1是，分別表示該邊線的兩個(gè)端點(diǎn)，則：hj=u·VT=pj+qj·t+w·當(dāng)=0和t=1時(shí)，pj+qj表示該邊線另一端點(diǎn)和物體上j個(gè)平面的點(diǎn)積。因?yàn)閣j0表示物體的第j個(gè)平面可見(jiàn)，所以，如果wj0和pj+qj0，則表示該端點(diǎn)位于可見(jiàn)面上或位于視點(diǎn)與可見(jiàn)面之間。綜上，在物體中只要存在一個(gè)j，使得wj0&pj0&pj+qj0成立，則該邊線完全可見(jiàn)。Z緩沖器算法算法原理：Z緩沖器算法是所有圖像空間算法中最簡(jiǎn)單的一種隱

15、藏面消除算法。幀緩沖器用來(lái)存儲(chǔ)圖像空間中每一個(gè)象素的屬性（光強(qiáng)度），Z緩沖器是用來(lái)存儲(chǔ)圖像空間中每一個(gè)可見(jiàn)象素相應(yīng)的深度(或Z坐標(biāo))，是一個(gè)獨(dú)立的深度緩沖器。算法主要是計(jì)算將要寫入幀緩沖器象素的深度(或Z值)，并與已存儲(chǔ)在Z緩沖器中該象素的原來(lái)深度進(jìn)行比較 ：若新象素點(diǎn)位于幀緩沖器中原象素點(diǎn)的前面，則將新象素的屬性寫入幀緩沖器，并將相應(yīng)的深度(Z值)也寫入Z緩沖器；否則，幀緩沖器和Z緩沖器中的內(nèi)容不變。本算法的實(shí)質(zhì)是對(duì)給定的x,y,尋找最小的z(x,y)值。掃描線Z緩沖器算法算法原理：在多邊形填充算法中，活性邊表的使用取得了節(jié)省運(yùn)行空間的效果。用同樣的思想改造Z-buffer算法：將整個(gè)繪圖區(qū)

16、域分割成若干個(gè)小區(qū)域，然后一個(gè)區(qū)域一個(gè)區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只要等于一個(gè)區(qū)域內(nèi)像素的個(gè)數(shù)就可以了。如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線Z緩沖器算法。光線跟蹤算法光線跟蹤算法是一種帶有強(qiáng)制性的方法，其基本思想是：觀察者能夠看到的物體是光源發(fā)出的光所照射著的物體，其中一部分的光到達(dá)人的眼睛，引起視覺(jué)。觀察者看到的光可以是從物體表面反射來(lái)得，也可以是從物體背面折射或透射過(guò)來(lái)的。如果從光源出發(fā)跟蹤光線，則只有其中極少部分的光線能到達(dá)觀察者的眼睛，顯然效率太低。所以光線跟蹤算法是按反過(guò)程進(jìn)行的，即從觀察者到物體的方向。光線光柵網(wǎng)格算法原理： 假設(shè)圖中的物體已變換到圖像空間，且視點(diǎn)或觀察

17、者位于z軸負(fù)無(wú)窮遠(yuǎn)處。光從觀察者 出發(fā)，經(jīng)過(guò)光柵屏幕上的像素點(diǎn)進(jìn)入畫面，然后沿光線方向進(jìn)行跟蹤，以確定該光線與畫面中的哪一個(gè)物體相交。從視點(diǎn)至每一個(gè)像素點(diǎn) 所形成的光線都要與畫面中的每一個(gè)物體進(jìn)行比較。若光線與物體相交，則需計(jì)算它們之間所有可能的交點(diǎn)。若光線與畫面中若干物體相交而出現(xiàn)多個(gè)交點(diǎn)，則按深度排序，具有最小Z值的交點(diǎn)所對(duì)應(yīng)的面為此像素點(diǎn)的可見(jiàn)面，該像點(diǎn)的顯示值由相應(yīng)物體的屬性(強(qiáng)度或顏色）所決定。觀察者光柵網(wǎng)格 若視點(diǎn)不在無(wú)窮遠(yuǎn)處，則算法要復(fù)雜一些。假設(shè)觀察者位于坐標(biāo)系原點(diǎn)，方向朝Z軸，光柵平面垂直于Z軸，這樣從視點(diǎn)對(duì)物體做透視變換且投影于光柵平面即可。 對(duì)于光線跟蹤算法，最重要的部分

18、是為了確定可見(jiàn)面進(jìn)行的求交運(yùn)算。這里介紹一種減少求交運(yùn)算的方法： 檢查光線與包圍該物體的包圍體（如包圍盒和包圍球）是否相交； 若相交，則需計(jì)算光線與包圍體內(nèi)的物體的交點(diǎn)； 否則不交，不用進(jìn)一步處理。在這里，對(duì)于包圍球來(lái)說(shuō)，判斷一條光線與球面是否相交很簡(jiǎn)單：若包圍球的球心至光線的距離小于球的半徑，則該光線與包圍球相交；若包圍球的球心至光線的距離大于球的半徑，則該光線與包圍球不相交，則肯定光線與包圍求內(nèi)的物體不可能相交。于是只需計(jì)算點(diǎn)(球心)至一直線(光線)的距離。設(shè)點(diǎn)P1(x1,y1,z1)和P2(x2,y2,z2)連線的參數(shù)表示形式為：  P(t)=P1+(P2-P1)t 其中相應(yīng)的

19、分量為： x=x1+(x2-x1)t=x1+aty=y1+(y2-y1)t=y1+btz=z1+(z2-z1)t=z1+ct點(diǎn)P0(x0,y0,z0)至該直線的最短距離d為： d2=(x-x0)2+(y-y0)2+(z-z0)2 此時(shí)參數(shù)t為：若d2R2(R為包圍球的半徑)，則光線與包圍球中的物體不相交。相交無(wú)交光線無(wú)交若包圍盒檢查則計(jì)算量大得多。一般光線至少與包圍盒的三個(gè)平面相交，而且得到的交點(diǎn)不一定在包圍盒邊界之內(nèi)，因此要對(duì)每個(gè)交點(diǎn)作包含性檢查。下面是一種簡(jiǎn)化的方法： 將光線平移和旋轉(zhuǎn)，使其與z軸重合，且對(duì)包圍盒作相應(yīng)變換； 如果在變換后的包圍盒的xmin和xmax，ymin和ymax的符

20、號(hào)皆相反，則光線與包圍盒相交；否則不相交。實(shí)驗(yàn)環(huán)境硬件平臺(tái)：PC軟件(推薦)：Windows平臺(tái)，Visual C+，matlab實(shí)驗(yàn)步驟1. 掌握算法原理；2. 依據(jù)算法，編寫源程序并進(jìn)行調(diào)試；3. 對(duì)運(yùn)行結(jié)果進(jìn)行保存與分析；4. 把源程序以文件的形式提交；5. 按格式書寫實(shí)驗(yàn)報(bào)告。實(shí)驗(yàn)內(nèi)容面消隱算法程序如下：void CTestView:ReadFace()/設(shè)置立方體的6個(gè)面F0.EdgeNum=4;F0.p0=0;F0.p1=1;F0.p2=2;F0.p3=3;F0.Color=RGB(255,255,0);/底面F1.EdgeNum=4;F1.p0=0;F1.p1=3;F1.p2=7

21、;F1.p3=4;F1.Color=RGB(0,255,255);/左面F2.EdgeNum=4;F2.p0=0;F2.p1=1;F2.p2=5;F2.p3=4;F2.Color=RGB(0,0,255);/前面F3.EdgeNum=4;F3.p0=1;F3.p1=2;F3.p2=6;F3.p3=5;F3.Color=RGB(0,255,0);/右面F4.EdgeNum=4;F4.p0=4;F4.p1=5;F4.p2=6;F4.p3=7;F4.Color=RGB(255,0,0);/頂面 F5.EdgeNum=4;F5.p0=3;F5.p1=2;F5.p2=6;F5.p3=7;F5.Color

22、=RGB(255,0,255);/后面bool CTestView:Painter(CDC* mdc)/畫家算法 Rotate();for(Face=0;Face<6;Face+)int TotalEdge=FFace.EdgeNum;for(int edge=0;edge<TotalEdge;edge+)/邊循環(huán) int PointNumber=FFace.pedge;/面的頂點(diǎn)號(hào);Pointedge=BoxNew.PPointNumber;CreatBucket();/建立桶結(jié)點(diǎn)Et();/用于建立邊表GetMinDeep(mdc);/計(jì)算面的最小深度f(wàn)or(int i=0;i

23、<6;i+)/輸出排序前深度 if(Fi.MinDeep>=SpecialZValue|Fi.MinDeep<=-SpecialZValue)/處理面深度無(wú)限大異常Fi.MinDeep=0;CString zBeforeSort;zBeforeSort.Format("%5.2f",Fi.MinDeep);Sorted();/深度排序for(i=0;i<6;i+)/輸出排序后深度CString zAfterSort;zAfterSort.Format("%5.2f",Fi.MinDeep);DrawPolygon(mdc);/繪制

24、排序后的面return true;void CTestView:GetMinDeep(CDC* mdc)/獲得每個(gè)面的最小深度FFace.MinDeep=SpecialZValue;doubleCurDeep=0.0;/當(dāng)前掃描線的深度doubleDeepStep=0.0;/當(dāng)前掃描線隨著x增長(zhǎng)的深度步長(zhǎng)doubleA=0.0;/平面方程系數(shù)AdoubleB=0.0;/平面方程系數(shù)BdoubleC=0.0;/平面方程系數(shù)CdoubleD=0.0;/平面方程系數(shù)DA=(Point1.y-Point2.y)*(Point1.z-Point3.z)-(Point1.y-Point3.y)*(Poin

25、t1.z-Point2.z);B=(Point1.x-Point3.x)*(Point1.z-Point2.z)-(Point1.z-Point3.z)*(Point1.x-Point2.x);C=(Point1.x-Point2.x)*(Point1.y-Point3.y)-(Point1.x-Point3.x)*(Point1.y-Point2.y);D=-A*Point1.x-B*Point1.y-C*Point1.z;/計(jì)算curDeep;從x=xMin開始計(jì)算，此時(shí)針對(duì)yiDeepStep=-A/C;HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/訪問(wèn)所有桶結(jié)點(diǎn)for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)/訪問(wèn)桶中排序前的邊結(jié)點(diǎn)Edge *TEdge=new Edge;TEdge->x=CurrentE->x;TEdge->yMax=CurrentE->yMax;TEdge->k=CurrentE->k;TEdge->next=NULL;AddAet(TEdge);/將該邊插入臨時(shí)Aet表AetOrder();