深度緩沖器法的消隱問題

深度緩沖器法的消隱問題

0消隱的投影圖的表現(xiàn)在現(xiàn)實(shí)世界中，如果觀察到一個不透明的物體，我們只能看到物體表面朝我們所見的表面，而其他表面可能無法看到。在計(jì)算機(jī)生成立體圖形時,物體的所有部分都將表現(xiàn)出來,不管是可見的還是不可見的。這樣的圖形所表示的物體形狀是不清楚的,甚至是不確定的。如圖1(a)所示的立方體,就可以有圖(b)、(c)兩種解釋:其一是從立方體的左上方向下看得到(b);其二是從立方體的右下方向上看到到(c)。由此可見要得到一個確定的立體感強(qiáng)的投影圖,就需要消除穩(wěn)藏線和隱藏面,也就是在給定的投影圖中,確定物體哪些邊、面是可見的,哪些邊、面是不可見的,并消除那些不可見的棱線和表面,這就是所謂的消隱問題。消隱問題是計(jì)算機(jī)圖形學(xué)研究的重點(diǎn)課程之一。1消隱方法1.1法向量的方向背面消除不是一個完整的隱面消除方法,但它是隱面消除算法中的關(guān)鍵部分。對于單個凸多邊體背面消除即可以達(dá)到隱面消除的目的。假設(shè)給定視點(diǎn)位置,為了決定一個面相對于視點(diǎn)為可見還是不如圖3所示,在某一表面內(nèi)取兩個向量P(p1,p2,p3)和q(q1,q2,q3),它們向量積p×q是一個與該向量所確定的平面垂直的法向量n=p×q,n方向由右手法則定義。為了得到符合要求的p和q,對所考慮的表面按逆時針方向取出2、3、8號三個頂點(diǎn),根據(jù)2、3、8號頂點(diǎn)坐標(biāo)算出p和q的各分向量p1,p2,p3和q1,q2,q3,根據(jù)p和q,就可算出n。視線向量v=(v1,v2,v3),由視點(diǎn)和2號坐標(biāo)可求分向量v1,v2,v3。法向量n和視線向量v之間夾角有如下關(guān)系:根據(jù)該結(jié)果的正負(fù)號判定θ大小范圍,數(shù)量積大于0,則θ<90°,否則0≥90°。如前所述,0<90°時表示表面可見,否則為不可見。對于一個單一的凸多面體而言,背面消除可以完全消除不可見的面,而對于一個多物體組成的復(fù)雜體,僅僅通過背面消除是不夠的,還需要做進(jìn)一步的測試。但是背面消除是一個關(guān)系的步驟,簡單地經(jīng)過該過程就可以消去大約50%的隱藏面。1.2像素點(diǎn)位置的處理深度緩沖器法是圖象空間中一種常用的方法。它的基本思想是對于顯示屏上的每一個像素點(diǎn),測試一系列平面,記錄下位于此像素投射線上最靠近觀察點(diǎn)的平面的深度。除了深度外,還需要記錄下用以顯示此對象的亮度值。深度緩沖器算法采用兩個數(shù)組,一個記錄每一個像素點(diǎn)的深度值;一個記錄此像素點(diǎn)所對應(yīng)對象的亮度值,其過程為:(1)對于屏上每個像素點(diǎn),置深度緩沖器Depth[x][y]為一較大值,置亮度緩沖器為背景值;(2)對于景中的每個多邊形,找出多邊形投影到屏上時位于其邊界內(nèi)的全部像素。對于這些像素計(jì)算出此多邊形在(x,y)處的深度z;如果z<Depth[x][y],此多邊形相對于其它多邊形在(x,y)處更靠近觀察者,所以置Depth[x][y]=z,置亮度數(shù)組為該多邊形的亮度值。如果z>Depth[x][y],說明該多邊形在此像素點(diǎn)處被其它多邊形隱藏,所以不采取任何行動。當(dāng)對所有像素進(jìn)行掃描后,深度緩沖器和亮度緩沖器分別包含了所有可見點(diǎn)及可見的亮度值。由于采用屏幕坐系進(jìn)行計(jì)算,所以每個像素點(diǎn)(x,y)處的深度值可由如下方程直接計(jì)算。z=?Ax?By?DC這時,當(dāng)掃描線沿X方向增加一個單位時,像素點(diǎn)(x+1,y)處的深度值為:z′=?A(x+1)?By?DC同理,當(dāng)y=y-1時,像素點(diǎn)(x,y-1)處的深度值為:z′=?Ax?B(y?1)?DC深度緩沖器法量種比較簡單的隱面消除法,應(yīng)用在許多圖象顯示系統(tǒng)中。1.3深度優(yōu)先表的建立畫家方法就是按照畫家作畫的過程形成一幅圖象的方法。它是根據(jù)物體的遠(yuǎn)近程度的不同來完成隱面消除的。它也稱為表優(yōu)先級法,在物體空間預(yù)先計(jì)算物體各面可見性優(yōu)先級,然后在圖象空間產(chǎn)生消隱圖。它是以深度優(yōu)先級進(jìn)行排序的,按照多邊形離觀察者的遠(yuǎn)近來建立一張深度優(yōu)先級表,離觀察者遠(yuǎn)的優(yōu)先級低,近的優(yōu)先級高。當(dāng)深度優(yōu)先級表確定以后,畫面中任意兩個圖形元素在深度上均不重疊,從而解決消隱問題。表優(yōu)先級算法的基本思想是建好深度優(yōu)先級表后,只要從優(yōu)先級低的多邊形開始,依次把多邊形顏色填入幀緩沖存儲器中以形成多邊形圖形,直到優(yōu)先級最高的多邊形送入幀緩沖器后,整幅圖就顯示好了。如圖4所示,物體按C、B、A次序進(jìn)行顯示。在建立深度優(yōu)先表時,對于比較簡單的畫面,可直接按畫中各元素的最大或最小z值排序,如圖5(a)所示的情形。但是,對于比較復(fù)雜的畫面,若按最大或最小z值建立深度優(yōu)先表,就容易出現(xiàn)錯誤的結(jié)果,如圖5(b)所示。若按最大z值對圖形元素A、B進(jìn)行排序,則在深度優(yōu)先表中,A應(yīng)排在B的前面。按照這一順序?qū)懭霂彺嫫?B將部分地遮擋A。然而實(shí)際上A部分地遮擋B。為了得到正確的處理結(jié)果需要在深度優(yōu)先表中交換A、B的位置。建立深度優(yōu)先表時,常常出現(xiàn)的另一個問題是多邊形的相互覆蓋或多邊形的相互貫穿。如圖6(a)所示,A在B的前面,B在C的前面,而C反過來又在A的前面。多邊形互相貫穿時,也會出現(xiàn)類似的覆蓋情況。如圖6(b)所示,P部分地位于Q的前面,而Q又部分地在P的前面。在這兩個例子中,都無法根據(jù)物體Z值來建立確定的深度優(yōu)先表。解決的方法是對多邊形進(jìn)行子分割,就是利用多邊形所在平面間的交線來分割多邊形,如圖中的虛線。經(jīng)過分割后的多邊形就可以按Z坐標(biāo)值的大小進(jìn)行排序。從建立正確的深度優(yōu)先表。這種方法是在處理每一幅畫面時,動態(tài)地計(jì)算并產(chǎn)生一個深度優(yōu)先表,在通過一系列檢驗(yàn)確定其深度優(yōu)先表正確性后,寫入幀緩存器,否則重新計(jì)算并產(chǎn)生一個新的深度優(yōu)先表。下面給出這種算法過程的簡單描述。(1)計(jì)算多邊形最大Z值max,并以此值的優(yōu)先級進(jìn)行排序,建立初步的深度優(yōu)先表。按Z值從大到小對多邊形進(jìn)行排序,并記P1P2……Pn。(2)檢查表中每個多邊形P2P3……Pn與P1的關(guān)系a.若P1的最近頂點(diǎn)P1Zmin高視點(diǎn)距離比P2P3……Pn的最遠(yuǎn)頂點(diǎn)還遠(yuǎn),即PjZmax≤P1Zmin(j為2,3,……n),則P1不遮擋其它多邊形,轉(zhuǎn)(5),否則轉(zhuǎn)下一步;b.若不滿足a,將PjZmax≤P1Zmin的多邊形記為Qi(i=1,2,…k),檢查P1是否遮擋多邊形QI,置i=1。若遮擋轉(zhuǎn)(3)否則轉(zhuǎn)下步;c.判斷是i≤k(k≤n),若成立置i=i+1,轉(zhuǎn)d,否則轉(zhuǎn)(5)。d.檢查P1是否遮擋Qi,若遮擋轉(zhuǎn)(3),否則轉(zhuǎn)C。(3)變換P1與Qi在表中位置,對重新排列結(jié)果重復(fù)上述試驗(yàn),即轉(zhuǎn)(2),若所得檢驗(yàn)結(jié)果需要再次交換P1與Qi的位置,則表明P1與Qi之間存在交叉覆蓋情況,這時轉(zhuǎn)(4)。(4)用P1所在面與Q1所在面的交線分割多邊形P1,并且從表中刪除多邊形P1,轉(zhuǎn)(1)。(5)將P1寫入幀緩沖器并以P2替P1,轉(zhuǎn)(2)。如何來確定兩個平面P和Q是否遮擋呢?下面給出幾種分類測試方法:①深度覆蓋測試設(shè)在深度分類表中,P和Q是兩個相鄰多邊形平面,當(dāng)P、Q滿足條件Pzmin≤Qzmin,Pzmax≤Qzmin時,P位于Q之前。②面積覆蓋測試如果多邊形平面P和Q在XOY面投影無覆蓋關(guān)系,P與Q分離。③兩平面前后關(guān)系如果P平面的各頂點(diǎn)位于Q平面遠(yuǎn)離視點(diǎn)一側(cè),或者Q項(xiàng)點(diǎn)都在P的靠近視點(diǎn)一側(cè),則P不遮檔Q。④平面分解如果上述測試全部失敗,則必需求取交線,對平面進(jìn)行分解。1.4窗口再分割算法描述Warnock算法是一種區(qū)域細(xì)分算法,它既可用于消除隱藏線,也可用于消除隱藏面,它適用于解決多邊形所表示的畫面的消隱問題。Warnock算法遵循“細(xì)分與占領(lǐng)”的設(shè)計(jì)思想。首先在圖像空間中設(shè)置一個窗口,用遞歸過程來判定窗口內(nèi)是否有可見的目標(biāo)(多邊形)。當(dāng)判定的窗口中不包含任何多邊形或者窗口內(nèi)只有與一個多邊形的相交部分時,稱這個多邊形為可見。這時可直接顯示該窗口,否則,就將該窗口分割成若干較小的窗口,直到被分割的窗口所含的畫面足夠簡單可直接顯示為止。每分割一次窗口,就把上述判斷推理的原則遞歸地應(yīng)用到每一個較小的窗口中去。多邊形與窗口之間存在以下四種關(guān)系,如圖7所示:當(dāng)窗口與每個多邊形關(guān)系確定后,有些窗口內(nèi)的圖形便可顯示輸出,另外一些還需要進(jìn)一步細(xì)化,Warnock方法具體過程表述為:(1)設(shè)置一個與圖形視見區(qū)域同樣大小的窗口,并取為當(dāng)前窗口。(2)確定當(dāng)前窗口與多邊形的關(guān)系。(3)檢驗(yàn)當(dāng)前窗口是否需要再分割,原則上有幾種:a.若畫面中所有多邊形與當(dāng)前窗口分離,則此窗口為空,不需要再分割,以背景的明暗度或顏色顯示窗口,并轉(zhuǎn)步驟(5)。b.若當(dāng)前窗口中僅包含一個多邊形,則此窗口內(nèi)多邊形外區(qū)域作為背景顯示,多邊形內(nèi)區(qū)域,以該多邊形明暗度或顏色顯示,并轉(zhuǎn)步驟(5)。c.若窗口與一多邊形相交,則窗口中多邊形的區(qū)域外按背景顯示,相交多邊形位于窗口內(nèi)的區(qū)域以該多邊形明暗度或顏色顯示,并轉(zhuǎn)步驟(5)。d.若當(dāng)前窗口為一多邊形所包圍,且窗口內(nèi)無其它多邊形或相交多邊形部分,則該窗口以包圍多邊形相應(yīng)明暗度或顏色顯示,并轉(zhuǎn)步驟(5)。e.若當(dāng)前窗口至少為一個多邊形所包圍,且此多邊形離視點(diǎn)最近,則這一窗口按此多邊形相對應(yīng)的明暗度或顏色顯示,并轉(zhuǎn)步驟(5)。f.若不屬于上述五種情