圖形可見(jiàn)面算法分析

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

2、,所生成的圖像具有連續(xù)色調(diào),能產(chǎn)生陰影、透明、表面紋理以及反射、折射等視覺(jué)效果。但這類算法比較慢,產(chǎn)生一幅圖需用幾分鐘甚至幾個(gè)小時(shí)。在算法設(shè)計(jì)上,需要在計(jì)算速度和圖形細(xì)節(jié)之間進(jìn)行權(quán)衡。沒(méi)有一種算法可以兩者兼得。隨著計(jì)算機(jī)硬件速度的提高和快速算法的出現(xiàn),畫(huà)面中已能包含較多的圖形細(xì)節(jié),然而,無(wú)疑永遠(yuǎn)會(huì)有更多的圖形細(xì)節(jié)需加以描繪。所有可見(jiàn)面算法都涉及到排序。一般來(lái)說(shuō),先取哪一個(gè)幾何坐標(biāo)進(jìn)行排序?qū)λ惴ǖ男什⒉恢匾Ｅ判虻暮诵氖欠直骟w、線、面、點(diǎn)與觀察點(diǎn)間幾何距離的遠(yuǎn)近。按距離排序基于一個(gè)前提,即一個(gè)物體離觀察點(diǎn)越遠(yuǎn),它越有可能被遮擋。在確定各景物在距離和深度上的順序后,還需對(duì)它們作橫向和縱向排序,以

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

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

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

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

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

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

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

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

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

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

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

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

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

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