幾種面消隱算法的研究與比較

《幾種面消隱算法的研究與比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、引言消隱(HiddenSurfaceRemoval)是在一定觀察方向下消除不可見的線和面。有時(shí)也稱為可見性測(cè)試。雖然各種消隱算法在可見性測(cè)試和不可見面消除方法上區(qū)別不大．但這些消隱方法有時(shí)還可以一起被統(tǒng)稱為不可見面的消除．簡(jiǎn)稱消隱。在三維造型技術(shù)、真實(shí)感圖形的顯示、慮擬場(chǎng)景的顯示、以及在地形．地圖的繪制中．消隱都起到至關(guān)重要的作用。所以研究和實(shí)現(xiàn)消隱算法，并根據(jù)場(chǎng)景的復(fù)雜度和各個(gè)不同應(yīng)用領(lǐng)域的場(chǎng)景來(lái)提高消隱算法的速度是很有必要的，它對(duì)整個(gè)三維圖形顯示．真實(shí)感圖形的顯示以及各種地形地貌圖形的顯示是很有意義的。1面消隱算法的分類就目前研究出的面消隱算法，按照它們對(duì)消隱算法加速的方法不同可分

2、為兩類：一類是致力于消隱方法的研究：(1)現(xiàn)有的消隱算法研究?，F(xiàn)有的常用的幾種面消隱算法主要有：Z-buffer算法、掃描線算法、畫家算法、BSP樹算法等，其主要區(qū)別在于它們消隱空間不同、可見面測(cè)試方法和不可見消除方法不同，故它們所適用的范圍也不同。本文將在第三部分從每種算法本身的特點(diǎn)、消隱空間、排序效率和對(duì)場(chǎng)景的限制上對(duì)這幾種消隱算法來(lái)分析和比較。(2)由于消隱算法不同，它們適用的場(chǎng)景類型和復(fù)雜度也不同，所以有一些專門用于針對(duì)地形、地圖的繪制、凸多邊體消隱、復(fù)雜形體消隱、對(duì)某一種形體表示的場(chǎng)景的消隱、對(duì)曲面消隱等的算法研究。(3)研究新的消隱方法或用不同方法對(duì)已有算法改進(jìn)來(lái)提高消隱速

3、度．如樹結(jié)構(gòu)的消隱算法、改進(jìn)的掃描線算法、BSP樹法在輻射度顯示中的應(yīng)用、BSP樹法加入到層次遮擋圖(HOM)算法、BSP樹法結(jié)合Imagecache(Sprite)算法等．可以在不同程度的提高圖形繪制效率。對(duì)于BSP樹加入到其它算法中可提高其它算法效率，本文也將在第三部分進(jìn)行比較。另一類是致力于減少視域中的待處理的景物面片數(shù),來(lái)達(dá)到加速消隱過(guò)程的目的。硬件Z-buffer算法是目前最為常用的實(shí)時(shí)圖形繪制算法，盡管其線性復(fù)雜度為O(N)(N為面片數(shù))，但該算法由于不考慮景物的空間連貫性，需逐一繪制景物面片而不管它是否隱藏。因而，對(duì)高度復(fù)雜的場(chǎng)景，硬件Z-buffer算法仍難以達(dá)到實(shí)時(shí)。

4、解決這一個(gè)問(wèn)題的關(guān)鍵是減少?gòu)?fù)雜場(chǎng)景中需實(shí)時(shí)繪制的景物面片數(shù)N。而減少視域中的待處理面片數(shù)目前有兩種途徑：(1)基于空間連貫性的快速消隱算法。這種算法并不簡(jiǎn)化場(chǎng)景幾何，而是充分利用景物空間、圖象空間和時(shí)間域上的可見性和不可見性連貫性來(lái)剔除被遮擋的景物面片。層次遮擋圖算法和層次Z—buffer算法是這類算法的典型代表。這兩個(gè)算法均將景物空間組織成層次結(jié)構(gòu)，并把面片的可見性計(jì)算分解為深度排序和在屏幕卜的重疊測(cè)試兩個(gè)過(guò)程。算法引入深度z錐來(lái)實(shí)現(xiàn)快速的保守排序，而圖象錐則用來(lái)加速面片的重疊測(cè)試，這兩個(gè)層次結(jié)構(gòu)的引入使得快速剔除不可見面成為可能．從而極大地降低了后續(xù)硬件Z-buffer算法的繪制復(fù)

5、雜度。更進(jìn)一步，時(shí)問(wèn)域上可見性連貫性的使用保證了Z錐和圖象錐具有一個(gè)極好的初始條件，為快速繪制提供了重要保障。由于著眼于開發(fā)不可見景物的空間連貫性，這類算法對(duì)高遮擋率的場(chǎng)景非常有效．但對(duì)遮擋復(fù)雜性不高的復(fù)雜場(chǎng)景卻毫無(wú)優(yōu)勢(shì)，仍無(wú)法達(dá)到實(shí)時(shí)。(2)基于層次細(xì)節(jié)的圖形繪制技術(shù)。這種算法根據(jù)視覺(jué)特性．對(duì)離視點(diǎn)較遠(yuǎn)的景物進(jìn)行幾何簡(jiǎn)化，從而達(dá)到降低場(chǎng)景復(fù)雜性的目的．或利用其它幾何方法對(duì)整個(gè)場(chǎng)景面片進(jìn)行簡(jiǎn)化，來(lái)減少場(chǎng)景面片數(shù)。這種方法大大的減少了場(chǎng)景的復(fù)雜度．提高了繪制場(chǎng)景的速度，但對(duì)高度復(fù)雜的場(chǎng)景．經(jīng)過(guò)幾何簡(jiǎn)化后的場(chǎng)景可能仍無(wú)法實(shí)時(shí)繪制．直到九十年代中期發(fā)展起來(lái)的紋理簡(jiǎn)化技術(shù)較好地解決了這類問(wèn)題。

6、其典型代表是Shade的圖象緩存(ImageCache)技術(shù)，該算法結(jié)合幾何簡(jiǎn)化和基于圖象的繪制技術(shù)的優(yōu)點(diǎn)。算法首先將場(chǎng)景組織成一棵BSP樹。漫游時(shí)，算法自動(dòng)地決定BSP樹中各個(gè)結(jié)點(diǎn)中的景物是否滿足紋理簡(jiǎn)化的誤差要求，若滿足．則取圖象緩存中對(duì)應(yīng)圖象作為紋理．將其映射到一空間四邊形表面：來(lái)取代結(jié)點(diǎn)中的幾何來(lái)繪制域面：否則，直接采用幾何來(lái)繪制。顯然，這種動(dòng)態(tài)圖象簡(jiǎn)化技術(shù)大大減低了場(chǎng)景的復(fù)雜性．從而提高了圖形的繪制效率。但由于該算法采用從后向前的繪制方式，不能利用前述的空問(wèn)不可見性連貫性來(lái)加速消隱過(guò)程。為此，鄭文庭，鮑虎軍等結(jié)合了層次遮擋圖和圖象緩存算法．提出了基于時(shí)空連貫性和幾何簡(jiǎn)化技術(shù)的

7、復(fù)雜場(chǎng)景快速消隱繪制算法口，可以適合對(duì)各種復(fù)雜場(chǎng)景的實(shí)時(shí)繪制．提高了圖形繪制效率，加速了消隱過(guò)程。2研究消隱算法的方法2.1從消隱空間來(lái)分析對(duì)消隱算法消隱空間的分析是對(duì)消隱算法的效率的分析的一個(gè)重要方面。因?yàn)檫@樣可以對(duì)消隱算法進(jìn)行歸類，并為提高消隱算法的效率打好基礎(chǔ)。根據(jù)消隱所在的空間分為消隱算法可以分為三大類：(a)物體空間法(光線投射Roberts)：物體空問(wèn)是用戶來(lái)定義三維形體的三維空間．即所說(shuō)的世界坐標(biāo)系空間。它是三維形體還沒(méi)有被投影到