圖形學實驗七課件

1、貴州大學實驗報告學院： 計信學院 專業(yè)：計科 班級：計科101姓名羅琳學號1008060016實驗組無實驗時間2013-4-29指導教師吳云成績實驗項目名稱消隱實驗目的掌握常用的裁減及消隱算法：直線、多邊形的裁減；消除隱藏面算法：Roberts消隱算法、Z緩沖器算法、掃描線Z緩沖器算法、光線跟蹤算法。實驗要求分別實現(xiàn)一個直線裁減算法、多邊形的裁減算法、面消隱算法實驗原理Roberts消隱算法算法原理：Roberts消隱算法是在圖像空間實現(xiàn)的消隱算法，數(shù)學處理嚴謹，計算量甚大。Roberts算法要求所有被顯示的物體都是凸的，因此對凹體要先分割成許多個凸體的組合。此算法的基本步驟是：l 逐個的獨立

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

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

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

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

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

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

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

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

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

11、)其中：g=0,0,-1,0,與視線方向E=0,0,1,0相反，且與t的意義相同。給定一個t值，對應邊線P1P2上的一點P(t)，同樣對于給定一個值，則決定了從該點至視點線段上的一點。所以Q(,t)可以看作是定義了這平面上的一點集,給定和t，就確定了這個平面上的一點?？偸侨≌?，這是因為只有平面的這一區(qū)域才能包含遮擋上述邊線的物體。如果物體于平面的交集不定，且落在點集Q(,t)中，則這個物體部分或全部地遮擋邊線P1P2。否則，P1P2就不會被這個物體所遮擋。 現(xiàn)在把邊線的對于給定物體的可見性問題，轉(zhuǎn)為物體與整個點集之交是否為空集的問題。因為前面已經(jīng)規(guī)定：物體中的點與體矩陣的乘積所產(chǎn)生的向量中所

12、有元素均為非負數(shù)。所以，H=u·VT=s·VT+t·dVT+·gVT0(0t1，0)對于物體中的每個面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于是，可見與不可見的臨界條件是hj=0。當hj=0時，該點恰好位于對應的平面上。若對物體的每一平面取hj=0，可得有關(guān)和t的聯(lián)立方程組。為了求解這個方程

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

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

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

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

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

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

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

20、號皆相反，則光線與包圍盒相交；否則不相交。實驗環(huán)境硬件平臺：PC軟件(推薦)：Windows平臺，Visual C+，matlab實驗步驟1. 掌握算法原理；2. 依據(jù)算法，編寫源程序并進行調(diào)試；3. 對運行結(jié)果進行保存與分析；4. 把源程序以文件的形式提交；5. 按格式書寫實驗報告。實驗內(nèi)容面消隱算法程序如下：void CTestView:ReadFace()/設(shè)置立方體的6個面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;/面的頂點號;Pointedge=BoxNew.PPointNumber;CreatBucket();/建立桶結(jié)點Et();/用于建立邊表GetMinDeep(mdc);/計算面的最小深度for(int i=0;i

23、<6;i+)/輸出排序前深度 if(Fi.MinDeep>=SpecialZValue|Fi.MinDeep<=-SpecialZValue)/處理面深度無限大異常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)/獲得每個面的最小深度FFace.MinDeep=SpecialZValue;doubleCurDeep=0.0;/當前掃描線的深度doubleDeepStep=0.0;/當前掃描線隨著x增長的深度步長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;/計算curDeep;從x=xMin開始計算，此時針對yiDeepStep=-A/C;HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/訪問所有桶結(jié)點for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)/訪問桶中排序前的邊結(jié)點Edge *TEdge=new Edge;TEdge->x=CurrentE->x;TEdge->yMax=CurrentE->yMax;TEdge->k=CurrentE->k;TEdge->next=NULL;AddAet(TEdge);/將該邊插入臨時Aet表AetOrder();