一種改進的基于切片的可視面片選擇方法

摘要：在三維場景處理中，如何快速選擇可見面片是提高場景顯示速度的關鍵。基于切片的可視面片選擇方法能夠有效地減少選擇可見面片時的計算量，但是該算法的計算結果是基于直線的視線傳達，無法真實再現人眼的視角特征。本人提出了基于切片的一種改進算法，能夠快速的計算出上層切片可視部分在下層切片上的投影邊界，實現了切片算法的視角改進。

關鍵詞：遮擋算法；可見性；視角；切片算法

中圖分類號：TP391文獻標識碼：A文章編號：1009-3044(2008)17-21505-02

1 引言

現代計算機圖形技術和計算機硬件設備飛速發展為各種復雜的圖形顯示效果提供了強大的基礎平臺。但虛擬顯示技術所處理的場景越來越復雜，不斷地對計算機顯示硬件提出更高的要求，使得計算機硬件仍不能很好地滿足大規模復雜場景實時繪制的要求。因此，還需要研究各種加速方法。其中，提高可見面選取的效率，是一種非常重要的加速技術，因為這可以很好地降低場景繪制的復雜度。

在可見面的選擇技術方面，國內外已經有了很多的研究。一個面片是可見的，它必須滿足下列條件：它在成像的視域內，它的法向不是背離視點的，而且它沒有被離視點更近的面片所遮擋.目前的可見性處理方法大致可以分為兩類：一類是對場景中的面片進行一定的組織，為各個局部子空間建立可見面集合，以便每次成像時可以處理較少的面片；另一類是利用成像過程中的遮擋關系，很快地排除不可見面片。目前已經提出了如：場景空間加上視線方位的5維空間進行局部子空間的可見面分類表達；基于門窗為建筑物中的各個子空間建立可見面集合；基于包圍盒測試和法向檢測的可見性處理方法；基于可見性誤差估計的層次化迭加處理的方法；基于面片法向編碼的方法；z-buffer技術與四叉樹、八叉樹技術相結合的方法等。

現在已經提出了很多方法來加快交互漫游應用程序的繪制速度，層次細節(Level Of Detail)算法在城市仿真中用的比較多，因為它在運行的時候不需要大的計算量。另一種簡單而且普遍的剔除方法是視錐剔除，如果一個繪制元素位于視域平頭四棱錐之外，則該繪制元素必不可見，這樣就可以不需要對其進行繪制了，它可以適用于大多數的模型。Teller和Sequin[4]提出了一個預處理方法來計算特定視點區域的可見面集合，在漫游時，只需處理相對當前視點和視線方向的所有可能可見面片，但是不能滿足對多余的細節可以迅速的簡化。

2 典型的可見性算法

2.1 Beam樹算法

為了避免重復繪制，Beam樹算法按從前向后的次序繪制場景，即當一個面繪制后，該面就占據了屏幕上的一個區域，后繪制的面中位于此占據區域內的部分將不再繪制，而只繪制不位于此占據區域內的部分，并使占據區域擴大。一個面在屏幕上形成的占據區域，是指從視點處發出的光線因被多邊形面遮擋而在屏幕上形成的陰影區域，陰影區域和視點形成三維空間的一個錐體，稱為陰影錐。隨著繪制的進行，占據區域將逐漸擴大，陰影錐的數目逐漸增加。為了快速檢索，用一株二元樹來組織陰影錐，稱為Beam樹。

Beam樹是BSP(BinarySpacePartitioning)樹，其結點記錄陰影錐的側面，面的一側為陰影錐的內部，另一側為陰影錐的外部。

Beam樹算法處理一個面的基本方法為：搜索Beam樹，如果面完全位于陰影區域外，則繪制該面，并將該面對應的二元樹插入到Beam樹中；如果面完全位于陰影區域內，則不繪制該面；如果面與Beam樹的結點平面相交，則用結點平面將該面切分成兩個面，對每個面及其對應的Beam子樹，算法遞歸執行。

使用Beam樹算法不會出現重復繪制，但它引入的開銷非常巨大。隨著繪制的進程，Beam樹越來越深，繪制一個面時，搜索和裁剪的工作越來越多。在Quake游戲中，有人曾經嘗試使用Beam樹算法，但由于對復雜的場景，搜索和裁剪的開銷太大，不能保證圖形的實時繪制，結果放棄了該算法。

2.2 PVS技術

PVS(PotentialVisibleSet)算法是對視點所在區域，預先計算出當視點在區域內漫游時，場景中各景物的可見性，表示這個可見性的集合稱之為PVS。在顯示時，根據視點所在區域的PVS決定景物是否需要進行繪制。預先計算PVS的好處在于：它能大大提高對視錐外景物的剔除速度，并且對位于視錐內的景物只有少量的重復繪制(通常會出現50%的重復繪制)；它導致性能更加平均，由于不必再對復雜場景進行附加的可見性測試，使最差情況與最好情況下的性能差距變小了。但預計算PVS的過程比較復雜，計算量很大，另外，PVS的大小也是一個要考慮的問題。對于有上萬個多邊形的場景來說，一個未被壓縮的PVS大小為幾兆到幾十兆字節，所以必須對PVS進行合理的數據壓縮。

給定的視點A，AB 與AC 形成觀察視角如圖1 所示，元素a，b，c，d，e，f，g 可以分成三類，元素a，b，e，g 是遮擋類，其中元素a，e，g 是部分遮擋的，b 是完全遮擋的，元素c，f 是完全在其里面類，元素d 是屬于分離類。對所有的基本元素進行分類后，可以執行下列操作：

1)刪除屬于分離類的基本元素；

2)對于所有屬于遮擋類的元素，找到位于最前面的一個完全遮擋元素，然后刪除在其后的所有元素（包括部分遮擋的和完全在其里面的元素），這樣，余下的基本元素變形成了該視點范圍的PVS。

算法以視點為中心構造一個立方體包圍盒，對包圍盒的6 個面做二維分割，其3D 示意圖如圖2 所示。視點與包圍盒表面上的每一個方格形成一個光束，光束在給定視點路徑的兩點之間進行滑動，形成一個光束體（如圖3 所示）。場景中的物體跟這個光束體關系有三種，物體在光束體的外面時，就可以剔除；與光束體相交的物體，判斷物體的先后關系，可以剔除位于與光束體完全相交的物體之后的物體；在光束體的里面時，需要進一步的細分光束體來判斷其可見性。最后對每個光束體的可見面進行融合，這樣就可得到了這個路徑區域的PVS。

2.3 遮擋物思想

考慮到場景中的遮擋主要是由一些大遮擋物產生的。該算法根據視點的位置動態地在場景中選取一小部分遮擋物，以備遮擋時選用，由于在許多情況下，場景中的大部分遮擋是由視點附近的一些多邊形引起的，因此選取視點附近的多邊形作為遮擋物。

3 一種改進的基于切片的可視面片選擇方法

新方法由預處理和成像時選取可見面兩個部分組成。預處理時，新方法首先根據面片的法向進行分類，使法向相近的面片屬于一類，以便成像時更多、更快地排除法向背離視點的不可見面片；然后，對每一類面片分別形成垂直于X軸、Y軸和Z軸的3組層次狀索引結構，每一組這樣的結構都是根據面片的空間位置形成它們基于坐標的有序排列。由此，選取可見面時則能利用二分查找的技術提高搜索速度。

成像時，根據視點相對于場景的方位，選取一組索引結構。然后根據成像面上的可見像素對此結構中的面片進行由近及遠的處理來選取可見面(可見像素，就是那些還沒有被真正離它最近的面片所覆蓋的像素，即在繪制工作完成之前，像素的深度信息還可能發生變化的像素)。當然，根據可見像素上的成像視線選取可見面，不會處理那些法向背離視點的面片。

隨著繪制過程的繼續進行，可見像素越來越少，但它們的分布卻不一定規則。為此，我們引用動態屏幕管理技術來管理這些可見像素，以使成像過程中選取可見面的操作能夠高效地進行。由于面片是基于空間剖分進行索引化組織的，新方法可以很方便地將可見像素與其相應的空間區域快速關聯。由此，在根據可見像素選取可見面時，那些與可見像素沒有關聯的區域中的面片就被隱含地剔除了。

4 基于可見像素選擇可見面

根據視點相對于場景包圍盒的方位，選擇某組索引結構進行可見性面片的選取。如圖4中的二維示意圖所示，如果視點位于1區和2區，則選切片垂直于Y軸的索引結構；如果視點位于3區和4區，則選切片垂直于X軸的索引結構；視點位于5，6，7，8區，則可任選一組索引結構。對于三維的情況可以類推。選擇不同的索引結構的目的，是為了成像時便于由近及遠地處理面片，以便更好地利用前面面片對后面面片的遮擋性，避免對不可見面片的處理。

在選擇了索引結構后，我們就可以根據成像面上的可見像素來選擇可見面。不失一般性，設所選擇的索引結構的切片是垂直于Z軸的，而視點的Z坐標是小于這些切片的Z坐標的。由此，對這些切片進行由近及遠的逐個處理，并在處理每一個切片時，根據成像面的可見像素在此切片的實網格中挑選出可見面片。當可見像素被真正離它最近的面片填充后，它就變成了填充像素，不再參與選擇可見面的操作。

5 動態物體的處理

新方法能夠很好地處理帶有剛性運動物體的場景。首先，預處理時我們為每一個動態物體按其局部坐標系建立層次索引結構；在繪制時，可以先對動態場景和背景的層次索引結構進行合并；然后按照相同的方法繪制所有的面片。但是，合并索引結構的操作需要很大的開銷。

為了方便地處理動態物體，并與靜態場景進行協調的繪制，我們采用以下的方式：確定視點和成像面以后，首先分別繪制所有的動態物體；在繪制這些物體時，所用的坐標系是每個物體的層次索引結構所在的局部坐標系，不同的是，需要將成像面上像素的深度坐標從物體所在的局部坐標系轉換到場景對應的全局坐標系下，這樣就可以根據轉換后的深度坐標進行比較來選擇動態物體中的可見面進行繪制；繪制完動態物體后，再對場景進行繪制。這時，一些成像面上像素的深度坐標已經改變，而且選擇了一些臨時的可見面。但是，我們把所有這些像素仍然當作可見像素，以進行對靜態場景中可見面的選擇。這樣，由于像素上深度坐標的存在，動態物體上的可見面能得到保留，而不可見面會被自動地覆蓋掉。

6 總結

本文介紹了常見的遮擋算法，針對各種遮擋算法的不足提出的可見面選取方法對面片進行基于法向的分類，并對每類面片進行基于空間位置的有序的層次化索引構造。這樣，各條視線可以方便地將法向背離視點的不可見面片進行成群的剔除，視線在尋找可見面時可以利用高效的檢索技術加快前行的步長，以提高檢測速度，因為索引構造能夠很好地、有序地反映面片的空間位置。此外，成像時，基于可見像素來選擇可見面，能夠很好地利用已繪制的可見面片隱含地剔除大量被遮擋的面片，節省了大量時間。由于新方法的預處理結果是可以相對于物體的局部空間來計算的，物體運動對預處理結果沒什么改變，因此新方法能夠方便地處理動態場景。總之，新方法對可見面的選取具有很高的精度，并且速度很快，能方便地處理動態場景。

參考文獻：

[1] 魏峰，王文成，吳恩華.快速高精度的可見面選擇[J].軟件學報，2006(10).

[2] 王益.基于視域剪裁的三維場景快速消隱算法[J].系統仿真學報，2001(11).

[3] 馬自萍.基于線性八叉樹的一種消隱算法[J].寧夏工程技術，2006(9).

[4] 任重，華煒，鮑虎軍，等.全局遮擋圖[J].計算機學報，2005(6).

[5] 志庚，傅國良，王毅剛.一種基于視角剖分的可見性算法[J].系統仿真學報，2004(8).

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文