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

1、 圖形可見(jiàn)面算法分析胡寧寧,周公博,賈曉娜中國(guó)礦業(yè)大學(xué)機(jī)電學(xué)院,江蘇徐州(221008E-mail:zhougongbo1985摘要:本文分析了近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à)面快速

2、消隱;而計(jì)算機(jī)動(dòng)畫(huà)卻采用高度真實(shí)感圖形算法,所生成的圖像具有連續(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ū)λ惴ǖ男什⒉恢匾?。排序的核心是分辨體、線、面、點(diǎn)與觀察點(diǎn)間幾何距離的遠(yuǎn)近。按距離排序基于一個(gè)前提,即一個(gè)物體離觀察點(diǎn)越遠(yuǎn),它越有可能被遮擋。在確定各景物在距離和深度

3、上的順序后,還需對(duì)它們作橫向和縱向排序,以便確定一個(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ù)以平方

4、律(2n增長(zhǎng)。對(duì)象空間消隱算法以場(chǎng)景中的物體為處理單元, 算法可描述為: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),

5、這使得Roberts 算法大為遜色。但Roberts 算法數(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 多邊形

6、裁剪算法。算法在景物空間中以任意給定精度進(jìn)行運(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)景沿垂直方向劃分成

7、一系列的水平帶、在每一水平帶中掃描線的可見(jiàn)性不變。初始時(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à)面在放大后往往不能令人滿意,例如線段端

8、點(diǎn)之間可能不再銜接等。從理論上說(shuō),在圖像空間算法中,場(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

9、浮動(dòng)水平線算法浮動(dòng)水平線算法1常用于形如(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即深度緩存

10、算法,該算法需要兩個(gè)緩沖器:幀緩沖器用以存儲(chǔ)圖像空間中每個(gè)像素的屬性(光亮度;Z 緩沖器用來(lái)存儲(chǔ)圖像空間中每一可見(jiàn)像素相應(yīng)的深度或z 坐標(biāo),它是一個(gè)獨(dú)立的深度緩沖器。其基本原理是:計(jì)算準(zhǔn)備寫入幀緩沖器像素的深度即z 值,并與已存儲(chǔ)在Z 緩沖器中該像素的原深度比較。如果新像素位于幀緩沖器上原像素的前面,則將新像素寫入幀緩沖器,同時(shí)Z 緩沖器用新的z 值更新。否則,不寫入也不更新。本算法的實(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)、透

11、明與半透明效果等問(wèn)題時(shí)存在較大的困難。3.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)

12、處對(duì)多張面片進(jìn)行光強(qiáng)度累計(jì)的問(wèn)題。A 緩沖器算法對(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)處和掃描線所確定的平面稱為掃描平

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

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

15、只包含一個(gè)區(qū)段,掃描區(qū)間時(shí),按該段所在多邊形的屬性顯示;區(qū)間中包含多個(gè)區(qū)段,則在掃描時(shí)計(jì)算該區(qū)間中各區(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ù)雜這一難題。3.5.3 曲面掃描線算法曲面掃描線算法1是在曲面分割算法的基礎(chǔ)上,引入掃描線技術(shù),改進(jìn)而成的,與曲面分割算法不同的是,該算法按照掃描線的次序輸出

16、結(jié)果。此算法直接從曲面的定義出發(fā),按掃描線順序顯示雙參數(shù)多項(xiàng)式曲面。算法過(guò)程為:通過(guò)視點(diǎn)和掃描線所確定的掃描平面與場(chǎng)景相交,由此即發(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 =以確定它是否可

17、見(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)或觀察者位于z 軸正向的無(wú)窮遠(yuǎn)處,因此所有光線均平行于z 軸。光線從觀察者出發(fā),通過(guò)光柵中像素的中心進(jìn)入場(chǎng)景。然后沿光線路徑進(jìn)行跟蹤,以確定它與場(chǎng)景中的哪一物體相交。每一條光線均需與場(chǎng)景中的每一個(gè)物體進(jìn)行比較。如果相交,則需求出該光線與物體的所有可能的交點(diǎn)。光

18、線可能與場(chǎng)景中多個(gè)物體相交而形成多個(gè)交點(diǎn)。將這些交點(diǎn)按深度排序,具有最大z 值的交點(diǎn)對(duì)應(yīng)的面為在此像素的可見(jiàn)面。該像素處的顯示值由相應(yīng)物體的屬性決定。該算法具有并行性質(zhì), 因此可以在并行處理的硬件上快速實(shí)現(xiàn)光線投射算法。但是, 該算法計(jì)算量非常大, 因此,顯示速度慢。 4 優(yōu)先級(jí)排序算法 優(yōu)先級(jí)排序表算法的實(shí)現(xiàn)則同時(shí)涉及到景物和圖像兩個(gè)空間。具體來(lái)說(shuō)，優(yōu)先級(jí)排序表 的計(jì)算在景物空間中進(jìn)行， 計(jì)算結(jié)果寫入圖像空間幀緩存區(qū)中。 使用幀緩存區(qū)是這個(gè)算法的 關(guān)鍵之處。一個(gè)典型的優(yōu)先級(jí)排序表算法由三步組成：首先，將所有景物按某種度量作優(yōu)先 級(jí)排序； 然后， 識(shí)別和解決所有可能出現(xiàn)的二義性問(wèn)題， 獲得一個(gè)

19、確定的優(yōu)先級(jí)順序； 最后， 從前至后，順序?qū)?yōu)先級(jí)表中的物體作掃描轉(zhuǎn)換。 4.1 深度優(yōu)先表算法 深度優(yōu)先表算法1從深度優(yōu)先級(jí)排序開(kāi)始，按照畫(huà)面中各元素離視點(diǎn)的距離確定一個(gè)深 度優(yōu)先級(jí)表。若該表是完全正確的，則畫(huà)面中任兩個(gè)元素在深度上均不重疊。算法執(zhí)行時(shí)， 先從離視點(diǎn)最遠(yuǎn)的畫(huà)面元素開(kāi)始， 依次將每個(gè)元素寫入幀緩沖器。 表中離視點(diǎn)較近的元素覆 蓋幀緩沖器中原有的內(nèi)容。 在處理簡(jiǎn)單的畫(huà)面元素， 如多邊形時(shí)， 該算法常被稱為畫(huà)家算法， 這是由于算法過(guò)程與畫(huà)家創(chuàng)作一幅油畫(huà)的過(guò)程類似。 4.2 Newell-Newell-Sancha 算法 Newell、Newell 和 Sancha1提出了一個(gè)特定的

20、排序方法解決建立深度優(yōu)先表時(shí)所出現(xiàn)的 優(yōu)先級(jí)矛盾。該算法在處理每一幅畫(huà)面時(shí)，動(dòng)態(tài)地計(jì)算和產(chǎn)生一個(gè)新的深度優(yōu)先表，而對(duì)畫(huà) 面環(huán)境的復(fù)雜性和描述畫(huà)面元素的多邊形類型均無(wú)限制。此算法是用于處理多邊形的。 4.3 二叉空間剖分樹(shù)算法 二叉空間剖分算法1，即 BSP 樹(shù)算法3的基本原理是：取任意視點(diǎn)繪制一個(gè)多邊形，先 繪制其遠(yuǎn)離視點(diǎn)一側(cè)的所有多邊形， 然后繪制該多邊形， 最后繪制位于其視點(diǎn)一側(cè)的所有多 邊形，即可獲得正確的繪制結(jié)果。BSP 樹(shù)算法分兩步，即先構(gòu)造 BSP 樹(shù)，再顯示該樹(shù)。 BSP 樹(shù)的構(gòu)造是在景物空間中完成的。BSP 樹(shù)算法遞歸地將空間分為兩個(gè)子空間，它取 場(chǎng)景中的一個(gè)多邊形作為分離或分

21、割面， 場(chǎng)景的其他多邊形中， 完全位于剖分平面某一側(cè)的 多邊形被歸入相應(yīng)得子空間， 與剖分面相交的多邊形沿剖分面被分割成兩部分， 分別放入相 應(yīng)得子空間。 這兩個(gè)子空間再分別選一個(gè)多邊形作分割面遞歸的子分下去， 直到每個(gè)子空間 只剩一個(gè)多邊形為止。 BSP 樹(shù)的顯示是在圖像空間中完成的。 它不依賴于視點(diǎn)的位置， 依據(jù) BSP 樹(shù)確定可見(jiàn)面 時(shí)， 僅需知道視點(diǎn)與樹(shù)的根結(jié)點(diǎn)多邊形的相對(duì)位置關(guān)系即可。 對(duì)樹(shù)的中序遍歷算法稍加修改 就可確定可見(jiàn)面，即先遍歷一子數(shù)、訪問(wèn)根結(jié)點(diǎn)、再遍歷其另一子樹(shù)。該遍歷算法的時(shí)間復(fù) 雜度是線性的。 5 既可用于圖像空間又實(shí)用于景物空間的算法 Warnock 算法1是一種既

22、可用于圖像空間又可用于景物空間的算法， 其基本思想很普通， 它模擬了一種假設(shè)， 即人的眼睛與大腦處理包含在一副畫(huà)面中的信息的方法假設(shè)認(rèn)為人 的眼光往往會(huì)掠過(guò)畫(huà)面上信息貧乏的部分，而大都停留在畫(huà)面上蘊(yùn)涵信息豐富的區(qū)域。 Warnock 算法以及由它派生出的其他算法試圖利用如下事實(shí)：在圖形顯示中，畫(huà)面上大 片區(qū)域是相似的。這種性質(zhì)稱為區(qū)域連貫性，即畫(huà)面在 x 和 y 方向上的相鄰區(qū)域 (像素內(nèi) 大都相似。此算法先考察在圖像空間 (或景物空間的一個(gè)窗口 (或區(qū)域。判定該窗口是否 空，或該窗口所包含的畫(huà)面是否足夠簡(jiǎn)單可以立即顯示。否則，分割該窗口，直到子窗口內(nèi) -6- 所包含的畫(huà)面相當(dāng)簡(jiǎn)單可以立即顯示

23、或者子窗口尺寸已達(dá)到給定的分辨率為止。若為后者， 則根據(jù)子窗口中余留的信息進(jìn)行計(jì)算。 如果算法在景物空間實(shí)現(xiàn)， 則需將精確的信息寫入文 件以備進(jìn)一步處理；若僅需圖像空間精度，則以單一光強(qiáng)或顏色顯示所得結(jié)果.圖像空間實(shí) 現(xiàn)可結(jié)合進(jìn)行反走樣處理， 這只需將圖形分割到超出顯示分辨率， 然后取各子像素顯示值的 平均作為原像素的顯示值即可。 Warnock 算法的具體實(shí)現(xiàn)過(guò)程也不盡相同，其區(qū)別在于窗口的具體分割方法以及判定窗 口內(nèi)畫(huà)面是否足夠簡(jiǎn)單以致可直接顯示的具體條件。在原始 Warnock 算法中，每一窗口被 分割成四個(gè)相等的子窗口。 6 小結(jié) 前文討論了多種用于解決可見(jiàn)面、可見(jiàn)線問(wèn)題的基本算法，但這些算法并不都具有通用