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

喬云婷，張 弘

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

0 引言

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

1 預(yù)處理三維場景方法

1．1 包圍體的概念

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

表1 幾種不同的包圍體

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

圖1 用包圍體對場景進(jìn)行處理的效果

1．2 備選平面法向量列表的構(gòu)建

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

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

Step2:通過平面中三個(gè)不共線的點(diǎn)，作出兩個(gè)相交的向量求出該平面的法向量，針對重復(fù)的面，可能會(huì)有兩個(gè)相反的法向量，只選取一個(gè)平面法向量即可．

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

Step4:在一個(gè)完整的模型中需要定義一個(gè)變量Face關(guān)聯(lián)該模型所有的備選法向量．

1．3 分割面的選擇

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

1．4 建立BSP樹

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

圖2 空間二分樹及其對應(yīng)的樹形表示

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

2 實(shí)驗(yàn)驗(yàn)證

通過實(shí)驗(yàn)驗(yàn)證預(yù)處理之后BSP樹的加速渲染效果．

2．1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)軟件平臺(tái)為Autodesk 3D Studio Max 2012，硬件平臺(tái)如表2．

表2 實(shí)驗(yàn)平臺(tái)的配置

2．2 實(shí)驗(yàn)對象

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

圖3 實(shí)驗(yàn)的三維效果圖

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

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

3 結(jié)語

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

(指導(dǎo)教師 劉 軍)

［1］李儒茂，郭翠翠．虛擬現(xiàn)實(shí)編輯器標(biāo)準(zhǔn)教程［M］．北京:印刷工業(yè)出版社，2013．

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

［3］羅運(yùn)和，戴青．計(jì)算機(jī)圖形學(xué)基礎(chǔ)［M］．北京:中國計(jì)量出版社，2003．

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

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

［6］耿國華．?dāng)?shù)據(jù)結(jié)構(gòu):用C語言描述［M］．北京:高等教育出版社，2011．155－161．

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

［8］［美］卡斯?fàn)柭當(dāng)?shù)字圖像處理［M］．朱志剛，譯．北京:電子工業(yè)出版社，1998．