喬云婷,張 弘
(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,陜西渭南714099)
在虛擬現(xiàn)實(shí)場景漫游中,觀看者移動視點(diǎn)的位置就需要計(jì)算機(jī)以實(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)的模型能參加觀察變換和象素填充.
包圍體就是將物體組合完全包容起來的一個封閉空間.將復(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)行處理的效果
這里,我們以包圍盒(AABB)為例[2].
Step1:建立場景中要以包圍盒處理的物體模型.
Step2:通過平面中三個不共線的點(diǎn),作出兩個相交的向量求出該平面的法向量,針對重復(fù)的面,可能會有兩個相反的法向量,只選取一個平面法向量即可.
Step3:求出該平面的法向量并將求得的向量加入到備選平面法向量列表中.
Step4:在一個完整的模型中需要定義一個變量Face關(guān)聯(lián)該模型所有的備選法向量.
分割平面必須是對凹多面體而言的,如果已經(jīng)形成了凸多面體的空間就不必分割.對于一個凹體而言[3],分割平面必須在平面的正負(fù)方向均出現(xiàn)三角形.如此遞歸分割下去,就能保證將空間最終分割成大量凸多面體集合,分割出來的結(jié)果最好是讓一棵樹平衡,平衡二叉樹的操作較快,冗余度?。臅r間復(fù)雜度為O(n2)[4](n是量備選平面法向量列表中平面法向量的數(shù)量).通常在實(shí)際的應(yīng)用中加上相應(yīng)的限制條件,其時間復(fù)雜度會小于O(n2).
空間二分就是遞歸地通過直線對平面進(jìn)行分割[4].如圖2所示,l1分割整個平面,然后l2分割l1上方的平面,l3分割下方的平面,以此繼續(xù)分割.分割線不僅會分割平面,也將物體分割成若干碎片,像這樣一直分割下去最終每個子區(qū)域中只包含一個碎片.這個過程,就將平面的物體表示成一個二叉樹.在這個二叉樹中,每片葉子分別對應(yīng)的是最終所得子區(qū)域劃分中的一個面,即就是落在這個面中的物體的碎片,將存儲在該片葉子中.每個二叉樹的節(jié)點(diǎn)則分別對應(yīng)一條分割線,這條分割線也就存儲在這個節(jié)點(diǎn)中,如果場景中包含一維的物體,這個物體就有可能被包含在一條分割線中,此時,對應(yīng)的內(nèi)部節(jié)點(diǎn)需要存儲一個列表,記錄這個物體.
圖2 空間二分樹及其對應(yīng)的樹形表示
樹的遍歷 對于潛在的可見模型可以通過 樹的遍歷來獲得 這樣能夠減少可見性檢測時的模型數(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)的模型.通過上述方法,可以得到渲染后的三維場景模型.
通過實(shí)驗(yàn)驗(yàn)證預(yù)處理之后BSP樹的加速渲染效果.
實(shí)驗(yàn)軟件平臺為Autodesk 3D Studio Max 2012,硬件平臺如表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)的三維效果圖
在該三維場景條件下,通過移動視點(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樹渲染時間對比
本文通過對由許多小模型所組成的三維場景漫游特點(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]孫巍,劉金義.基于物體級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é)報,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é)報,1999,11(2):125-128.
[8][美]卡斯?fàn)柭當(dāng)?shù)字圖像處理[M].朱志剛,譯.北京:電子工業(yè)出版社,1998.