談虛擬現(xiàn)實引擎中可見性裁減的一種解決方法

1、談虛擬現(xiàn)實引擎中可見性裁減的一種解決方法     論文關鍵詞：可見性裁減  擴展投影  層次遮擋圖  層次深度圖論文摘要：可見性裁減計算機圖形學的基本問題，也是虛擬現(xiàn)實引擎中的一個關鍵技術。在解決可見性裁減問題時，將 Durand提出的擴展投影作為保守可見性預處理的算法與Greene等人提出的層次遮擋圖和層次深度圖的算法相結合，根據(jù)層次遮擋圖來判斷被遮擋物是否可見，并對算法中視點單元的大小和遮擋板的數(shù)量對裁減結果的影響作了分析。 0  引  言 可見性裁減就是找到從視點處可以看到的并需要進一步處理的所有物

2、體。1974年 ，Sutherland等人  在一份研報告中已經對已有的隱藏面消除 HSR(Hidden Surface Remova1)算法進行了分類，在當時已經基本解決了隱藏面的消除問題。但隨著三維場景的規(guī)模和復雜度的不斷增加，這些方法已經不能滿足如今大規(guī)模場景中隱藏面的消除。大規(guī)模場景的繪制時，在性能上至少有三個目標：每秒有更多的幀、更高的分辨率、更多的場景物體。為加速繪制場景，首先是使用裁減(Cul1ing)技術  。 可見性裁減大致分為三種：背面裁減、視截體裁減和遮擋裁減。視截體和背面裁減是最常用的，而且?guī)缀跏潜夭豢缮俚膬煞N裁減。遮擋裁減比較復雜，對于簡單的場景可

3、能并不需要進行遮擋裁減，但是對于大規(guī)模密集的場景來說遮擋裁減是必不可少的  。本文中的方法主要是針對遮擋裁減。 一種改進可見性裁減的方法。11 場景組織 在進行裁減之前，首先要對場景進行組織。場景的組織是個預處理過程。這里采用二叉包圍盒樹來組織場景，利用兩步來遞歸建立二叉樹：(1)建立一組對象的緊密包圍盒；(2)把這組對象細分為兩組，然后對兩組建立緊密包圍盒。這個遞歸過程將場景圖元細化成最小的組。場景對象的包圍盒采用方向包圍盒(OBB)，在對象進行遮擋測試時，投影就會更接近對象本身的大小。圖 1為實驗場景的包圍盒。12 可見性裁減算法121 視截體裁減 在進行裁減時，首先進行視截體的

4、裁減。判斷場景中的對象是否在視截體中，也就是判斷包圍盒是否在視截體中。包圍盒與一個平面的位置關系可以有三種：在平面正面，在平面反面，與平面相交，如圖2所示。如果包圍盒在視截體平面的反面則包圍盒是不可見的，將不會被渲染；如圖包圍盒在所有平面的正面，則包圍盒是可見的。要判斷包圍盒是否在平面的正面最直接的方法就是判斷包圍盒上的每個頂點是否都在平面的正面，同樣計算量也是相當巨大的，在這里采用包圍盒的中心點與平面的距離來判斷包圍盒的位置。 122 遮擋 裁減 (1)選擇遮擋板 經過視截體裁減，在剩余的對象中選擇一組對象作為遮擋板。選擇遮擋板是至關重要的，應該選擇那些形狀比較大的，距離視點單元較近的對象作

5、為遮擋板，才可能生成較好的遮擋效果，我們根據(jù)公式(1)來選擇遮擋板  。(2)遮擋板和被遮擋物的擴展投影所謂擴展投影就是將基于點的投影擴展到基于空間區(qū)域的投影。算法中的遮擋板和被遮擋物的擴展投影是根據(jù) Durand等人提出的擴展投影作保守可見性預處理算法  中的定義：遮擋板的擴展投影被定義為視點單元上每個頂點處產生投影的交集；而被遮擋物的擴展投影被定義為視點單元上每個頂點處產生投影的并集。通過擴展投影可以在視點單元內部任一點處觀察，被遮擋物的擴展投影都能完全在遮擋板的擴展投影中。(3)層次遮擋圖和層次深度圖 計算完遮擋板的擴展投影，將其渲染到幀緩沖區(qū)中，生成遮擋圖。如圖3所

6、示，遮擋圖只需要占用信息，不需要紋理和光照信息。因此我們將遮擋板渲染成純白色，背景為黑色。而遮擋圖的層次可以通過對前一層的像素累加平均的方法來獲得  。通過深度估計緩沖器來生成遮擋板的深度圖，它的每個像素記錄著對應區(qū)域中遮擋板的最大值。如圖4所示，每一層中的像素對應著上一層中2×2像素塊中的最大值。(4)重疊測試和深度測試 在重疊測試中，采用一種快速的測試方法，取層次遮擋圖中與被遮擋物投影大小接近的矩形，檢測矩形所覆蓋的遮擋圖上的像素是否完全不透明，如圖5所示。圖5中矩形 A所占的區(qū)域是完全不透明的，那么矩形 A通過了重疊測試。而左圖中矩形 B所占的區(qū)域是半透明的，將其與下

7、層的遮擋圖進行比較，得到右圖，可知矩形 B所對應的遮擋圖上的像素是完全透明的，則 B是可見的。當潛在被遮擋物通過了重疊測試，那么接下來進行深度測試。在深度測試中采用與重疊測試類似的方法。將被遮擋物的深度值與最高層上的深度值進行比較，如果被遮擋物的深度值大，則其通過了深度測試，否則將其與下一層深度圖進行比較。完成了重疊測試和深度測試 ，就可以根據(jù)潛在被遮擋物的可見性，對場景的保守可見集進行更新。 2 算法實現(xiàn)與分析 為了測試這個可見性裁減算法，在 OpenGL中導人一個3DS格式的城市模 型，如圖 6所示，模型中共有 2848個頂點，3892個面。在進行算法實現(xiàn)中發(fā)現(xiàn)，影響裁減算法的因素很多，我

8、們主要對視點單元大小和遮擋板的數(shù)量進行分析。 21 視點單元大小對裁減結果的影響 我們分別對視點單元大小為 500、300、100、50、1進行測試得到如表 1所示的結果。根據(jù)表 1和圖7可以看出，視點單元越小 ，就會裁減越多的面，因為隨著視點單元的縮小，擴展投影就越接近透視投影。而視點單元越小，劃分視點單元和計算遮擋裁減的工作量也越大。22 遮擋板數(shù)量對裁減結果的影響      我們分別對遮擋板的數(shù)量為5、20、50、100、200進行測試得到如表2所示的結果。根據(jù)表2和圖 8可以看出，在遮擋板數(shù)量少的時候對裁減的結果影響是很大的，但是當遮擋板的數(shù)量增

9、加到一定程度時，裁減結果的變化就很小了。遮擋板的數(shù)量同樣會影響到運行時間，隨著遮擋板數(shù)量的增加，所需的運行時間也會逐漸增加。 根據(jù)視點單元大小和遮擋板數(shù)量對裁減結果的影響，將以上兩個因素分別取不同的值，觀察對裁減結果的影響，如表3所示。2.3 其他因素的影響 在算法中，還有其他因素會影響到裁減結果以及運行時間。例如，包圍盒類型的選擇，采用沿坐標軸方向的包圍盒(AABB)或方向包圍盒 OBB；包圍盒樹的葉子的大小以及遮擋圖和深度圖的大小同樣會影響裁減結果。但在試驗中，我們將上面的因素作統(tǒng)一的規(guī)定，例如場景劃分采用 OBB包圍盒，包圍盒葉子 的大小設為 1O，遮擋圖或深度圖的分辨率設為256

10、15;256。 3  結 論 在可見性裁減算法中，采用層次遮擋圖與層次深度圖進行重疊測試和深度測試時，可以加快測試速度，減少運行時間。通過對影響算法的兩個主要因素：視點單元大小和遮擋板數(shù)量進行分析，得出視點單元越小，視點單元上的頂點就越集中，遮擋板的擴展投影范圍就越大，越接近單個視點的透視投影，這樣遮擋效果就越好，但是視點單元越小，預處理所需的時間越多，這樣不利于場景的實時性。隨著遮擋板數(shù)量的增加，裁減比例開始急速下降，然后趨于穩(wěn)定，但是運行時間也會隨著遮擋板數(shù)量的增加而成倍增加。 參考文獻 1Sutherland I E，Sproull R F，Schumaeher R AA ch

11、aracterization of ten hidden-surface algorithmsJComputing Surveys，1974，6(1)：1 55 2張毅彬虛擬現(xiàn)實引擎中的入口生成與路徑規(guī)劃D杭州：浙江大學。2002 3王章野，陸艷青，彭群生大規(guī)模場景的消隱技術J計算工程與應用 ，2001，9：812 4Satyan Coorg，Seth TellerRealtime occlusion culling for models with large occludersJIn Michael Cohen and David Zehzer，editors，1997 Sympostum

12、on Interactive 3D Graphics，page 83-90 ACM SIGGRAPH ，April 1997 5Fr6do Durand，George Drettakis，Jolle Thollot，and Claude Puech Conservative visibility preprocessing using extendedprojeetionsC In Kurt Akeley，editor，Siggraph 2000，Computer Graphics Proceed· ings，Annual Conference Series，ACM PressACM SIGGRAPHAddison W esley Longman，2000：239248 6Zhang Hansong，Dinesh Manocha，T