基于BSP樹的三維場景渲染方法研究

喬云婷，張 弘

(渭南師范學院數學與信息科學學院，陜西渭南714099)

0 引言

在虛擬現實場景漫游中，觀看者移動視點的位置就需要計算機以實時的速度對場景進行處理．通常計算機通過對隱藏面的消除來提高渲染速度，常用的方法有z緩沖算法、畫家算法，但這些方法都有一定的局限性，而BSP樹能夠實現三維場景的快速分割，提高場景的預處理速度．對較大規模三維場景渲染來說，整體分割較為復雜，如果將場景中的物體進行預處理，經處理后的模型表面作為分割平面建立BSP樹，就能夠快速構造BSP樹，快速確定視野體里的模型，使得視野體內的模型能參加觀察變換和象素填充．

1 預處理三維場景方法

1．1 包圍體的概念

包圍體就是將物體組合完全包容起來的一個封閉空間．將復雜物體封裝在簡單的包圍體中，能夠提高幾何運算的效率［1］．包圍體的常見類型有包圍盒、包圍球、包圍柱、離散定向多面體等，在一般的網絡游戲或虛擬現實世界三維場景中，遇到的物體形狀十分復雜，需要將多種包圍體的類型加以靈活運用，表1是幾種包圍體的比較．

表1 幾種不同的包圍體

包圍體的幾何形狀數量有限而且相對簡單，然而實際遇到的物體一般由多邊形或者通過處理成為近似多邊形的數據結構組成，［1］因此對包圍體的檢驗一般要比直接對于物體的檢驗速度快．為了得到復雜物體的包圍體，首先需要分析場景中物體的形狀特征，運用不同類的包圍體將場景中的物體進行分解．如圖1所示，我們對一組三維場景用包圍體進行處理．

圖1 用包圍體對場景進行處理的效果

1．2 備選平面法向量列表的構建

這里，我們以包圍盒(AABB)為例［2］．

Step1:建立場景中要以包圍盒處理的物體模型．

Step2:通過平面中三個不共線的點，作出兩個相交的向量求出該平面的法向量，針對重復的面，可能會有兩個相反的法向量，只選取一個平面法向量即可．

Step3:求出該平面的法向量并將求得的向量加入到備選平面法向量列表中．

Step4:在一個完整的模型中需要定義一個變量Face關聯該模型所有的備選法向量．

1．3 分割面的選擇

分割平面必須是對凹多面體而言的，如果已經形成了凸多面體的空間就不必分割．對于一個凹體而言［3］，分割平面必須在平面的正負方向均出現三角形．如此遞歸分割下去，就能保證將空間最終分割成大量凸多面體集合，分割出來的結果最好是讓一棵樹平衡，平衡二叉樹的操作較快，冗余度小．它的時間復雜度為O(n2)［4］(n是量備選平面法向量列表中平面法向量的數量)．通常在實際的應用中加上相應的限制條件，其時間復雜度會小于O(n2)．

1．4 建立BSP樹

空間二分就是遞歸地通過直線對平面進行分割［4］．如圖2所示，l1分割整個平面，然后l2分割l1上方的平面，l3分割下方的平面，以此繼續分割．分割線不僅會分割平面，也將物體分割成若干碎片，像這樣一直分割下去最終每個子區域中只包含一個碎片．這個過程，就將平面的物體表示成一個二叉樹．在這個二叉樹中，每片葉子分別對應的是最終所得子區域劃分中的一個面，即就是落在這個面中的物體的碎片，將存儲在該片葉子中．每個二叉樹的節點則分別對應一條分割線，這條分割線也就存儲在這個節點中，如果場景中包含一維的物體，這個物體就有可能被包含在一條分割線中，此時，對應的內部節點需要存儲一個列表，記錄這個物體．

圖2 空間二分樹及其對應的樹形表示

樹的遍歷 對于潛在的可見模型可以通過 樹的遍歷來獲得 這樣能夠減少可見性檢測時的模型數量［5］．本方法中雖沒有對模型進行遮擋剔除的處理，但通過包圍盒的簡化，已經使得該BSP中的三角數極大地減少．在BSP的遍歷過程中只需要判斷視野中模型的頂點在當前節點所包含的分割面中的正面或者是負面，對于物體模型跨越分割面這類情況，可以先遍歷當前節點的左子樹，后遍歷右子樹．通過判斷模型包圍體與視野體之間的關系，就能夠確定視野內的模型．通過上述方法，可以得到渲染后的三維場景模型．

2 實驗驗證

通過實驗驗證預處理之后BSP樹的加速渲染效果．

2．1 實驗平臺

實驗軟件平臺為Autodesk 3D Studio Max 2012，硬件平臺如表2．

表2 實驗平臺的配置

2．2 實驗對象

我們用一組虛擬的建筑模型場景作為實驗對象．如圖3所示，實驗中的物體模型主要為3DS模型，實驗中場景的長和寬均為1024，視野體的近平面和遠平面分別為1000和3000．

圖3 實驗的三維效果圖

在該三維場景條件下，通過移動視點獲得測試數據如表3所示．由表3中數據可以看出，通過預處理的BSP樹的渲染與一般BSP樹的渲染，前者通過對模型的預處理的BSP遍歷得到潛在可見模型的數量要小于一般的BSP樹渲染，它最終只渲染在視野體內出現的模型．而后者需要對場景內的所有模型進行處理．通過上述實驗可以看出，在由許多小模型所組成的大規模場景中，用包圍體處理后的BSP樹的方法，能夠大大提高渲染效率．

表3 一般BSP樹與模塊化BSP樹渲染時間對比

3 結語

本文通過對由許多小模型所組成的三維場景漫游特點的分析，給出了一種提高渲染效率的方法，并通過實驗證實了在三維場景中運用包圍盒將物體模塊化分類，有助于提高對場景BSP樹的劃分效率，提高三維場景的顯示速度．需要指出的是，這種方法對小規模的三維場景渲染速度提高較多，但是對大規模的場景提高并不顯著，需要進一步將該方法進行擴展，使其能夠應用在其他大規模場景的渲染和建筑群的全景虛擬．

(指導教師 劉 軍)

［1］李儒茂，郭翠翠．虛擬現實編輯器標準教程［M］．北京:印刷工業出版社，2013．

［2］孫巍，劉金義．基于物體級BSP樹的大規模室外場景渲染［J］．微處理機，2010，(6):68－69．

［3］羅運和，戴青．計算機圖形學基礎［M］．北京:中國計量出版社，2003．

［4］Berg de M，Kreveld van M，Overmars M，etal．Computational Geometry Algorithms and Applications［M］．第2 版．鄧俊輝，譯．北京:清華大學出版社，2005．280 －294．

［5］陶志良，成遲薏，潘志庚，等．多分辨率 BSP樹的生成及應用［J］．軟件學報，2001，12(1):118－125．

［6］耿國華．數據結構:用C語言描述［M］．北京:高等教育出版社，2011．155－161．

［7］呂旭東．基于畫家算法的多面體的消隱方法［J］．計算機輔助設計與圖形學學報，1999，11(2):125－128．

［8］［美］卡斯爾曼．數字圖像處理［M］．朱志剛，譯．北京:電子工業出版社，1998．