《計(jì)算機(jī)圖形學(xué)》08消隱技術(shù)

第八章消隱技術(shù)8.1基本概念一.為什么要消隱因?yàn)橛?jì)算機(jī)圖形處理的過程中，不會自動消去隱藏部分，相反會將所有的線和面都顯示出來。問題：①對于線畫圖形會出現(xiàn)多義性。對于光柵掃描著色的面圖形則會導(dǎo)致圖形錯(cuò)誤。②要增強(qiáng)圖形的真實(shí)感必須進(jìn)行消隱處理。二.消隱的分類

1.消除隱藏線對于采用物體的棱線或輪廓線表示的線畫圖形，應(yīng)消去物體本身看不見的棱線和輪廓線部分，以及因物體間的互相遮擋而被隱藏的棱線和輪廓線。2.消除隱藏面對于采用光柵掃描著色方法（即采用物體表面不同的明暗度）繪制的圖形，應(yīng)消除物體上看不見的面以及因物體間的互相遮擋而被隱藏的面。與此相對應(yīng)，消隱的算法也可分為兩種：

第一種方法是以場景中的物體為處理單元，將一個(gè)物體與其余的k－1個(gè)物體逐一比較，僅顯示它可見的表面以達(dá)到消隱的目的。此類算法通常用于消除隱藏線。假定場景中有k個(gè)物體，平均每個(gè)物體的表面由h個(gè)多邊形構(gòu)成，其計(jì)算復(fù)雜度為O((kh)2)。

算法描述如下：for(場景中的每一個(gè)物體){將該物體與場景中的其它物體進(jìn)行比較，確定其表面的可見部分；顯示該物體表面的可見部分；}

第二種方法是以窗口內(nèi)的每個(gè)像素為處理單元，確定在每一個(gè)像素處，場景中的物體哪一個(gè)距離觀察點(diǎn)最近（可見的），從而用它的顏色來顯示該像素。此類算法通常用于消除隱藏面。若顯示區(qū)域中有m×n個(gè)像素，則其計(jì)算復(fù)雜度為O(mnkh)。算法描述如下：for(窗口內(nèi)的每一個(gè)像素){確定距觀察點(diǎn)最近的物體，以該物體表面的顏色來顯示像素；}三.消隱算法中常用的處理技術(shù)1.排序確定物體間遮擋關(guān)系的要素：視點(diǎn)位置視線方向按觀察方向上離視點(diǎn)（投影參考點(diǎn)）的遠(yuǎn)近（通常用z值來表示）排序。2.測試用以判斷點(diǎn)與面、線與面、面與面之間的關(guān)系。u(x)v(y)n(z)視點(diǎn)z值包含測試：測試空間點(diǎn)的投影是否在某個(gè)空間多邊形的投影內(nèi)，若在，則可能存在遮擋關(guān)系；若不在，則不存在遮擋關(guān)系。測試方法：從空間點(diǎn)的投影開始向與－y軸平行的方向作射線，計(jì)算該射線與空間多邊形的投影的交點(diǎn)個(gè)數(shù)，若為奇數(shù)，則點(diǎn)的投影在多邊形的投影內(nèi)；若為偶數(shù)，則點(diǎn)的投影不在多邊形的投影內(nèi)。xy特殊情況左閉右開重疊測試：測試兩個(gè)空間多邊形的投影是否重疊，若重疊，則可能存在遮擋關(guān)系；若不重疊，則不存在遮擋關(guān)系。測試方法：四.提高消隱算法效率的常用方法利用連貫性包圍盒技術(shù)背面剔除將透視投影轉(zhuǎn)換成平行投影空間分割技術(shù)

復(fù)雜度比較物體分層表示

1.利用相關(guān)性（連貫性）

物體的相關(guān)性：若物體A與物體B是完全相互分離的，消隱時(shí)只需比較A、B兩物體之間的遮擋關(guān)系，而不需對其表面多邊形逐一進(jìn)行測試。

面的相關(guān)性：一個(gè)面內(nèi)的各種屬性值（坐標(biāo)值、灰度值等）一般都是緩慢變化的，可采用簡單增量方式進(jìn)行計(jì)算。

區(qū)域相關(guān)性：一個(gè)區(qū)域是指屏幕上一組相鄰的像素，它們通常屬于同一個(gè)可見面。區(qū)域相關(guān)性表現(xiàn)在一條掃描線上時(shí),即為掃描線上的每個(gè)區(qū)間內(nèi)只有一個(gè)面可見。掃描線相關(guān)性：在相鄰的兩條掃描線上，可見面的分布情況相似。

深度相關(guān)性：物體的同一表面上的相鄰部分深度是相近的。

2.包圍盒技術(shù)用于對物體間的某些關(guān)系進(jìn)行比較和測試，從而可避免盲目的求交運(yùn)算，減少計(jì)算量，提高效率。一個(gè)好的包圍盒要具有兩個(gè)條件：（1）包圍盒充分緊密包圍著形體；（2）對其的測試比較簡單。二維圖形-----包圍框（重疊測試）；三維物體-----包圍盒、包圍球。3.背面剔除一個(gè)平面多面體的表面由若干個(gè)平面多邊形構(gòu)成，若一個(gè)多邊形表面的外法線方向與投影方向（觀察方向）的夾角為鈍角，則該面為前向面；若其夾角為銳角，則為后向面或背面。剔除依據(jù)：物體表面是封閉的，背面總是被前向面所遮擋，從而始終是不可見的。投影方向ABCD4.將透視投影轉(zhuǎn)換成平行投影消隱與透視關(guān)系密切,體現(xiàn)有： 1）消隱必須在投影之前完成； 2）物體之間的遮擋關(guān)系與投影中心（視點(diǎn)）的選取有關(guān)； 3）物體之間的遮擋關(guān)系與投影方式有關(guān)5.空間分割技術(shù)

依據(jù)：場景中的物體，它們的投影在投影平面上是否有重疊部分？（是否存在相互遮擋的可能？）對于根本不存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測試。方法：將投影平面上的窗口分成若干小區(qū)域；為每個(gè)小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷那個(gè)物體可見時(shí)，只要對該區(qū)域的相關(guān)物體表中的物體進(jìn)行比較即可。6.復(fù)雜度比較：不妨假定每個(gè)小區(qū)域的相關(guān)物體表中平均有h個(gè)物體，場景中有k個(gè)物體，由于物體在場景中的分布是分散的，顯然h遠(yuǎn)小于k。根據(jù)第二種消隱方法所述，其算法復(fù)雜度為O(h*h),遠(yuǎn)小于O(k*k)。7.物體分層表示

表示形式：模型變換中的樹形表示方式

原理：減少場景中物體的個(gè)數(shù)，從而降低算法復(fù)雜度。

方法：將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)所代表物體的包圍盒，當(dāng)兩個(gè)父節(jié)點(diǎn)之間不存在遮擋關(guān)系時(shí)，就沒有必要對兩者的子節(jié)點(diǎn)做進(jìn)一步測試。父節(jié)點(diǎn)之間的遮擋關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測試。8.2深度緩存算法(Z—buffer算法)1.Z—Buffer用于存放與屏幕上像素點(diǎn)對應(yīng)的物體上點(diǎn)的深度值。xyz視線方向視點(diǎn)位置屏幕像素F—BufferZ—Buffer投影面可見點(diǎn)不可見點(diǎn)2.算法初始化：ZB(i,j)=機(jī)器最大值；FB(i,j)=背景色。for(j=1;j<=n;j++)/*共有n根掃描線*/for(i=1;i<=m;i++)/*每根掃描線上有m個(gè)像素點(diǎn)*/for(k=1;k<=p;k++)/*共有p個(gè)多邊形*/{判斷像素點(diǎn)(i,j)是否在多邊形Fk在投影面上的投影內(nèi);若(i,j)在多邊形Fk的投影內(nèi)，計(jì)算多邊形Fk上對應(yīng)于像素點(diǎn)(i,j)處的深度值Zi,j;if(Zi,j<ZB(i,j)){ZB(i,j)=Zi,j;FB(i,j)=多邊形Fk的顏色}else不作處理}3.算法實(shí)現(xiàn)中的關(guān)鍵問題①判斷點(diǎn)(i,j)是否在多邊形Fk在投影面上的投影內(nèi)解決辦法：采用包含測試。②計(jì)算多邊形Fk在點(diǎn)(i,j)處的深度值Zi,j

若多邊形Fk的平面方程為：ax+by+cz+d=0若c≠0，則ai+bj+dc若c=0，則多邊形Fk的法線方向與Z軸垂直，F(xiàn)k在投影面上的投影為一條直線，可不予考慮。Zi,j=—4.算法的特點(diǎn)①簡單不需要將所有的多邊形按離視點(diǎn)的遠(yuǎn)近排序，其算法的復(fù)雜度只與多邊形的個(gè)數(shù)成正比。②需要有一個(gè)較大容量的Z—Buffer。5.算法的改進(jìn)①采用包圍框技術(shù)，提高算法的效率。②采用硬件Z—Buffer來實(shí)現(xiàn)。

6.算法的進(jìn)一步改進(jìn)①采用分區(qū)處理方法。②利用相關(guān)性。8.3列表優(yōu)先算法（畫家算法）

基本思路：根據(jù)物體上各個(gè)面（多邊形）距離視點(diǎn)的遠(yuǎn)近進(jìn)行排序，建立一張優(yōu)先級表。約定距離視點(diǎn)近的優(yōu)先級高，距離視點(diǎn)遠(yuǎn)的優(yōu)先級低。生成圖象時(shí)，優(yōu)先級低的多邊形先畫，優(yōu)先級高的多邊形后畫。

關(guān)鍵問題：在深度方向上對多邊形進(jìn)行正確的排序。ABC分離面PDExyzo空中小三角形面片xyo

8.4光線投射算法算法思路將通過繪圖窗口內(nèi)每一個(gè)像素的投影線與場景中的所有多邊形求交。如果有交點(diǎn)，用深度值最大的交點(diǎn)（最近的）所屬的多邊形的顏色顯示相應(yīng)的像素；