1、 圖形可見面算法分析胡寧寧,周公博,賈曉娜中國礦業大學機電學院,江蘇徐州(221008摘要:本文分析了近16種現有的典型可見面消隱算法的原理與特點,提出了一種算法分類的方法,比較了各類算法的執行性能及適用領域。關鍵詞:消隱算法,圖像空間,景物空間,算法分析1 引言可見面算法,在計算機圖形學發展的初期被稱為隱藏線、隱藏面算法。由于圖形可能出現二義性,消除圖形中的隱藏線、面或體,是必要的。消隱問題本身的復雜性導致許多不同的算法,其中相當多的部分是針對某些特定的應用問題而設計的。沒有一種算法是十全十美的。實時模擬如飛行模擬等需要以視頻速率(每秒30幀畫面快速消隱;而計算機動畫卻采用高度真實感圖形算法

2、,所生成的圖像具有連續色調,能產生陰影、透明、表面紋理以及反射、折射等視覺效果。但這類算法比較慢,產生一幅圖需用幾分鐘甚至幾個小時。在算法設計上,需要在計算速度和圖形細節之間進行權衡。沒有一種算法可以兩者兼得。隨著計算機硬件速度的提高和快速算法的出現,畫面中已能包含較多的圖形細節,然而,無疑永遠會有更多的圖形細節需加以描繪。所有可見面算法都涉及到排序。一般來說,先取哪一個幾何坐標進行排序對算法的效率并不重要。排序的核心是分辨體、線、面、點與觀察點間幾何距離的遠近。按距離排序基于一個前提,即一個物體離觀察點越遠,它越有可能被遮擋。在確定各景物在距離和深度上的順序后,還需對它們作橫向和縱向排序,以

3、便確定一個物體實際上是否為那些距離觀察點較近的物體所遮擋。可見面算法的效率很大程度上取決于排序的效率。通常利用連貫性來提高排序過程的效率。可見面算法可以依據算法實現時所在的坐標系或空間進行分類,分為景物空間、圖像空間及優先級排序算法。2 典型用于景物空間的算法景物空間算法在景物被定義時所處的坐標系中實現,這種算法精度較高,通常只受限于所采用的顯示設備的分辨率,生成的圖形可以放大很多倍而仍然令人滿意,景物空間算法特別適用于精密的工程應用領域。從理論上分析,在景物空間算法中,場景中的每一個景物都需與場景中的其他景物一一比較,其計算量將隨場景中的景物數以平方律(2n增長。對象空間消隱算法以場景中的物

4、體為處理單元, 算法可描述為:for (場景中的每一個物體將其與場景中的其它物體比較, 確定其表面的可見部分;顯示該物體表面的可見部分;2 2.1 Roberts算法Roberts算法1是第一個知名的可見面算法,它在景物空間中實現,數學處理嚴謹。該算法要求畫面中所有物體都是凸的,凹體則需預先分解為凸體的組合,算法首先消除被物體自身遮擋的邊和面。然后,每一物體上剩下的邊再與其他物體一一比較,以確定這些邊上哪些 部分被遮擋。顯然,Roberts 算法的計算量隨著場景中物體數量的平方遞增。另外,光柵掃描顯示應用日益廣泛,而光柵顯示算法一般都在圖像空間中實現,這使得Roberts 算法大為遜色。但Ro

5、berts 算法數學處理簡單、精確、適用性強,且可以用它說明一些重要的概念。若采用Z 向優先級預排序以及簡單的最大最小包圍盒等方法,可使該算法的計算量幾乎與景物個數呈線性增長。算法分為三部分:第一部分對每一物體進行分析,消去自隱藏面。第二部分對余下的邊與所有其他的物體一一比較以確定被其他物體所遮擋的部分。第三部分確定貫穿物體之間的相貫線。假定物體為多面體,表面由棱邊圍成。而棱邊由頂點決定,所有的頂點、棱邊和表面都附屬于一定的物體。2.2 Weiler-Atherton 算法Weiler-Atherton 算法1基于Weiler-Atherton 多邊形裁剪算法。算法在景物空間中以任意給定精度進

6、行運算,其輸出結果仍為多邊形。故便于用做可見線、可見面算法。可見面算法可分為四步:按深度進行預排序;用距視點最近的多邊形對所有多邊形進行裁剪和區域分類;刪去位于離視點最近的多邊形之后的其他多邊形;必要時遞歸地進行分割。最后用深度排序消除所有不確定性。2.3 景物空間掃描線算法1和許多經典的在圖像空間實現的掃描線算法不同,Sechrest 和Greenberg 針對非相交多邊形提出了一種在景物空間實現的類似于掃描線算法的方法。由于在多邊形場景中可見性的改變僅出現在邊的交叉處或頂點處,該算法引入了Appel 算法1中可見性量化的思想,將場景沿垂直方向劃分成一系列的水平帶、在每一水平帶中掃描線的可見

7、性不變。初始時,僅在每個物體最小y 值頂點處分割場景。算法采用了一種很精巧的數據結構,按y 進行排序并建立活化邊表。在處理活化邊表的過程中,初始的場景分割被不斷細化,其分割位置逐漸包括所有頂點和邊的交叉處。算法最后輸出具有景物空間精度的可見邊段,并輔以足夠的信息來重建可見多邊形。算法使用背面剔除法來消除自隱藏面。3 典型用于圖像空間的算法圖像空間算法在景物顯示時所在的屏幕坐標系中實現,一旦達到屏幕的分辨率,計算就不再進行下去。通常一幅畫面取10241280×個整數點,這當然還十分粗糙,圖像空間算法生成的畫面在放大后往往不能令人滿意,例如線段端點之間可能不再銜接等。從理論上說,在圖像空

8、間算法中,場景中的每一個景物必須與屏幕坐標系中的每一個像素進行比較,其計算量為nN 其中n 為場景中的景物數(體、面或邊,而N 為屏幕的像素個數。一般說來,由于N n <(N 通常為6100.23.1×,景物空間算法較圖像空間算法計算量小。因此,從理論上分析,大多數算法應在景物空間中實現。然而實際情況并非如此,由于在光柵掃描過程中易于利用畫面的連貫性,圖像空間算法實現效率往往更高。圖象空間的消隱算法以窗口內的每個像素為處理單元, 算法可描述為:for (窗口內的每一個像素確定距視點最近的物體, 以該物體表面的顏色來顯示像素;2 3.1 浮動水平線算法浮動水平線算法1常用于形如(

9、0,=z y x F 的曲面中,由于曲面方程的特定表現形式,算法通常在圖像空間中實現。其基本思想是:采用一系列與坐標平面平行的平面(x 、y 或z 為定值去切割曲面,把三維問題轉化成二維問題。如圖1所示,當z 取一系列常數值時,可定義一簇平行平面。函數(0=z ,y ,x F 表示的曲面與每一平行平面的交線為一條曲線,即(z ,x f y =或(z ,y g x =其中z 為常數。一般地,浮動水平線算法的基本前提是假設曲面在每個剖面上的交線,特別是輪廓線,必須僅為x (或y 的函數。 圖1 坐標常數值剖面3.2 Z 緩沖器算法Z 緩沖器算法1即深度緩存算法,該算法需要兩個緩沖器:幀緩沖器用以存

10、儲圖像空間中每個像素的屬性(光亮度;Z 緩沖器用來存儲圖像空間中每一可見像素相應的深度或z 坐標,它是一個獨立的深度緩沖器。其基本原理是:計算準備寫入幀緩沖器像素的深度即z 值,并與已存儲在Z 緩沖器中該像素的原深度比較。如果新像素位于幀緩沖器上原像素的前面,則將新像素寫入幀緩沖器,同時Z 緩沖器用新的z 值更新。否則,不寫入也不更新。本算法的實質是對一給定的y x ,查找最大的(y x z ,值。Z 緩沖器算法簡單穩定,利于硬件實現。但是,它需要一個額外的Z 緩沖器,在每個多邊形占據的每個像素處都要計算深度值,計算量大,而且在處理斜直線的階梯效應、透明與半透明效果等問題時存在較大的困難。3.

11、3 曲面分割算法曲面分割算法1是針對雙三次曲面片的,遞歸地分割曲面,但其基本原理適用于任何曲面。算法的效率取決于曲面分割的效率。該算法可簡述為:遞歸地將曲面分割為子曲面片直到每一子曲面片在圖像空間的投影至多覆蓋一個像素中心為止;決定子曲面片在像素中心處的深度;使用Z 緩沖器算法,確定該曲面片是否可見;如果該曲面片可見,則計算在此像素區域上曲面的屬性并顯示該像素。 3.4 A 緩沖器算法A 緩沖器算法1是Z 緩沖器算法思想的延伸,A 表示反走樣、區域平均和累計緩沖器。Z 緩沖器算法的一個缺點是只能處理非透明的物體表面,而無法處理透明面片所存在的在各像素點處對多張面片進行光強度累計的問題。A 緩沖

12、器算法對深度緩沖器作了擴充,使其各單元均對應一張面片列表,這樣,可考慮各像素點處多張面片對其屬性值的影響,還可對物體的邊界進行反走樣處理。A 緩沖器可類似于深度緩沖器進行有效的組織,即沿每條掃描線判別以找出各像素點所覆蓋面片。曲面片可分割為多邊形網絡,并用像素邊界對它們進行裁剪。采用透明因子和面片覆蓋度,可將所有覆蓋面片對該像素點的影響取平均以計算該點的屬性值。3.5 幾種基于掃描線技術的算法此類算法按掃描線順序依次處理場景,算法在圖像空間中實現。它將三維的可見線、可見面問題簡化為二維的問題。由視點(位于z 軸正向無窮遠處和掃描線所確定的平面稱為掃描平面,如圖1(a所示。掃描平面與三維場景的交

13、線定義一個掃描線窗口,可見面問題就在此掃描線窗口中解決。圖1(b給出了掃描平面與場景中多邊形的交線。從該圖可知可見面問題可簡化為在掃描線的每個點上判定哪一條線段可見的問題。 圖2 掃描平面掃描線Z 緩沖器算法1,作為Z 緩沖器算法的特例,是一種最簡單的掃描線消隱算法。該算法中顯示窗口的高為一條掃描線的高度,寬即其水平顯示寬度。其幀緩沖器和Z 緩沖器所需的存儲量僅為深度水平顯示分辨率××1。Z 緩沖器的深度位數決定于z 的取值范圍。該算法是將它記錄的整屏深度數據改為只記錄當前掃描線所在行的各點深度數據,在計算出一條掃描線上的所有多邊形的各點深度并填充其象素值之后,才刷新行深度

14、緩存數組,以便計算下一行掃描線上對應的所有圖形。這樣循環處理之后,即一次性的逐行顯示出整個畫面上的圖形。克服了深度緩存算法占用存儲單元太大的不足,減少了占用的存儲空間。掃描線深度緩存算法的一個主要優點是縮小了z 向深度緩存數組,便于用軟件實現該算法。 區間掃描線算法1,又稱間隔掃描線算法,是將一個平面分成了3種類型的間隔區間:區間為空,區間中僅含有一條線段和區間中含有多條線段。當掃描區間時,只需在此區間中顯示畫面的背景色;當掃描區間中僅含有一條線段時,只要顯示這條線段相應多邊形的顏色即可;區間中只包含一個區段,掃描區間時,按該段所在多邊形的屬性顯示;區間中包含多個區段,則在掃描時計算該區間中各

15、區段的深度,具有最大z 值的區段為該區間中的可見段,按此區段所在的多邊形屬性顯示。掃描線Z 緩沖器算法需要計算多邊形中每個象素的深度,而區間掃描線算法可以減少計算深度的次數,并使它能適應透明或半透明有界表面的輸出。區間掃描線算法的一個優點在于利用平面之間邊線的相關性,分割各原有界平面,避免了深度優先級算法中多邊形之間相交、交叉重疊分割處理復雜這一難題。曲面掃描線算法1是在曲面分割算法的基礎上,引入掃描線技術,改進而成的,與曲面分割算法不同的是,該算法按照掃描線的次序輸出結果。此算法直接從曲面的定義出發,按掃描線順序顯示雙參數多項式曲面。算法過程為:通過視點和掃描線所確定的掃描平面與場景相交,由

16、此即發現在處理多邊形表面和參數曲面之間的差別。對于多邊形表面,所有交線均為直線段,這些直線段易于由其端點表示。對于參數曲面,掃描平面與參數曲面的交線由下式給出(t tan cons ysan w ,u y =其中w ,u 為曲面的參數,所得交線稱為層面線或等高線。交線不一定是單值的。其次在同一層面上可能有多條交線。最后,求出掃描線對應的曲線后,尚需確定沿掃描線相應曲線上每點的位置即,(w ,u x x =,并計算出在此位置上曲面的深度(w ,u z z =以確定它是否可見。3.6 光線跟蹤算法光線跟蹤算法1,又稱光線投射算法4,是將通過繪圖窗口內每一個像素的投影線與場景中的所有多邊形求交。如果有交點, 用深度值最大的交點(最近的所屬的多邊形的顏色顯示相應的像素;如果沒有交點, 說明沒有多邊形的投影覆蓋此像素, 用背景色顯示即可。其工作過程是:假定場景中的景物均已變換到圖像空間。暫不考慮透視變換,并設視點或觀察者位于