喬云婷，張 弘

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

0 引言

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

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

1．1 包圍體的概念

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

表1 幾種不同的包圍體

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

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

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

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

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

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

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

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

1．3 分割面的選擇

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

1．4 建立BSP樹(shù)

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

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

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

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

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

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)對(duì)象

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

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

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

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

3 結(jié)語(yǔ)

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

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

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

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

［3］羅運(yùn)和，戴青．計(jì)算機(jī)圖形學(xué)基礎(chǔ)［M］．北京:中國(guó)計(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樹(shù)的生成及應(yīng)用［J］．軟件學(xué)報(bào)，2001，12(1):118－125．

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

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

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