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

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

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

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

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

復雜度比較物體分層表示

1.利用相關性（連貫性）

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

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

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

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

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

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

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

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

方法：將父節(jié)點所代表的物體看成子節(jié)點所代表物體的包圍盒，當兩個父節(jié)點之間不存在遮擋關系時，就沒有必要對兩者的子節(jié)點做進一步測試。父節(jié)點之間的遮擋關系可以用它們之間的包圍盒進行預測試。8.2深度緩存算法(Z—buffer算法)1.Z—Buffer用于存放與屏幕上像素點對應的物體上點的深度值。xyz視線方向視點位置屏幕像素F—BufferZ—Buffer投影面可見點不可見點2.算法初始化：ZB(i,j)=機器最大值；FB(i,j)=背景色。for(j=1;j<=n;j++)/*共有n根掃描線*/for(i=1;i<=m;i++)/*每根掃描線上有m個像素點*/for(k=1;k<=p;k++)/*共有p個多邊形*/{判斷像素點(i,j)是否在多邊形Fk在投影面上的投影內(nèi);若(i,j)在多邊形Fk的投影內(nèi)，計算多邊形Fk上對應于像素點(i,j)處的深度值Zi,j;if(Zi,j<ZB(i,j)){ZB(i,j)=Zi,j;FB(i,j)=多邊形Fk的顏色}else不作處理}3.算法實現(xiàn)中的關鍵問題①判斷點(i,j)是否在多邊形Fk在投影面上的投影內(nèi)解決辦法：采用包含測試。②計算多邊形Fk在點(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.算法的特點①簡單不需要將所有的多邊形按離視點的遠近排序，其算法的復雜度只與多邊形的個數(shù)成正比。②需要有一個較大容量的Z—Buffer。5.算法的改進①采用包圍框技術，提高算法的效率。②采用硬件Z—Buffer來實現(xiàn)。

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

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

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

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