趙祥好

(安徽省委黨校 信息中心，安徽 合肥 230022)

BSP樹消隱算法的改進研究

趙祥好

(安徽省委黨校 信息中心，安徽 合肥 230022)

BSP樹算法是在三維景物空間中實現(xiàn)消隱的一種常見算法.BSP樹消隱算法中的遍歷算法通常是采用遞歸來實現(xiàn)，在實時虛擬環(huán)境具體實現(xiàn)時會導(dǎo)致很大的系統(tǒng)開銷.本文在分析BSP樹消隱算法中的BSP樹的構(gòu)造和遍歷方法的基礎(chǔ)上，以一種基于順序存儲結(jié)構(gòu)的非遞歸算法來代替通常的遞歸算法，有效的提高了BSP樹的遍歷速度，提高了三維景物空間的消隱的生成速度，降低了場景中的景物表面多邊形的存儲空間，有利于實時虛擬環(huán)境中三維景物的快速生成.

BSP樹算法；中序遍歷；消隱；滿二叉樹

在虛擬現(xiàn)實環(huán)境的設(shè)計中要求計算機所制造的三維虛擬環(huán)境能夠使用戶忘掉現(xiàn)實世界，獲得全身心對VR世界的真實體驗，產(chǎn)生沉浸于等同真實環(huán)境的感受和體驗.在虛擬環(huán)境的設(shè)計中必須要使用戶觀察到的場景是同真實世界一樣的三維場景，這就要求我們對虛擬環(huán)境中的場景繪制必須具有真實感和高質(zhì)量.虛擬環(huán)境中的場景常包含眾多的三維景物，基于真實環(huán)境的情況，采取一定的視點和視線方向時，必定會存在三維景物的一些表面被遮擋住而導(dǎo)致不可見，這一問題被稱為三維景物空間的消隱[1].BSP樹算法正是在三維景物空間中實現(xiàn)消隱的一種算法，該算法特別適用于場景中物體固定位置不變, 僅視點移動的情況，且與其他消隱算法相比，執(zhí)行較為高效.本文在深入研究BSP樹算法的基礎(chǔ)上，對其進遍歷部分采用基于順序存儲結(jié)構(gòu)的非遞歸方法進行了改進，有效地提高了利用BSP樹算法生成場景的效率.

1 BSP樹消隱算法

在虛擬環(huán)境中的場景常常包含許多多邊形，在繪制這些多邊形時，鑒于真實性，必須考慮到在給定某一個視點時，沿一定的視線方向，哪些景物的表面多邊形是可見的，哪些是不可見的.實際上一個物體離視點越遠，它越有可能被一個距離視點較近的物體遮擋[2].BSP樹算法(又被稱為二叉空間剖分樹可見面算法)是基于取任意視點繪制一個多邊形時，只需先繪制其遠離視點一側(cè)的所有多邊形，然后繪制該多邊形，最后繪制位于其視點另一側(cè)的所有多邊形，即可獲得正確繪制結(jié)果的原理.BSP樹算法在具體生成三維空間場景的消隱時分為兩步，先構(gòu)造BSP樹，再顯示它.

1.1 構(gòu)造BSP樹

BSP樹算法是遞歸地將景物空間分成兩個子空間的.首先可以從場景中的多邊形集合中任意選取一個多邊形作為分割面.場景中的其他多邊形，完全位于分割面前側(cè)或后側(cè)的多邊形被歸入相應(yīng)的前半或后半子空間中，與分割面相交的多邊形沿分割面分割成兩部分，分別放入相應(yīng)的前半或后半子空間中.從前半和后半子空間中再分別選取一個多邊形作為分割面，遞歸的分割下去，直到每個子空間中只剩一個多邊形為止.這個將景物空間分割的過程可以用二叉樹來表示，二叉樹的根是最初選擇作為分割面的多邊形，這樣景物空間就可以用一棵BSP樹完全表示出來.

圖1給出了一個簡單的場景以及其構(gòu)造出的BSP樹.假設(shè)該景物空間中存在五個多邊形ABCDE，其中多邊形A、C、E所在的平面垂直于紙面.首先選取多邊形A作為分割面，分割面與多邊形B相交，將多邊形B分成兩個多邊形B1和B2.多邊形B1和C在分割面的前側(cè)，多邊形B2、 D和E位于分割面的后側(cè).接著從樹的前枝中選取多邊形C作為分割面，再次分割.其前枝子空間中包含B1，后枝子空間為空.然后退回到樹根，再從樹的后枝中選取多邊形E作為分割面，分割后多邊形D歸入其前枝子空間，多邊形B2歸入其后枝子空間.這樣每一個分枝子空間中都只含有一個多邊形，所以這個簡單的場景分割完畢.

構(gòu)造BSP樹的算法可描述為：

AddtoBSPtree(polygon,polylist)

begin

if polylist is empty then

return null

else

if there is only one polygon in polylist then

return

else

begin

call SelectPolygon(polylist,root)

backlist=null

frontlist=null

for each remaining polygon on polylist

if polygon in front of root then

call AddtoBSPlist(polygon,frontlist)

else

if polygon in behind of root then

call AddtoBSPlist(polygon,backlist)

else

begin

call SplitPolygon(polygon,root,frontpart,backpart) call AddtoBSPlist(frontpart,frontlist)

call AddtoBSPlist(backpart,backlist)

end

end

call Combine(frontlist,root,backlist,BSPtree)

end

1.2 遍歷BSP樹

BSP樹消隱算法的一個明顯的特點是在BSP樹生成以后，根據(jù)BSP樹確定可見面時，僅需知道視點與樹的根節(jié)點多邊形的相對位置關(guān)系即可.對BSP樹采取中序遍歷即可確定可見面.BSP樹可見面算法的基本思想是先將離視點最遠的多邊形寫入幀緩存或進行顯示，即按從后到前的順序?qū)Χ噙呅芜M行繪制[3，4，5].這種從后到前的顯示方法是基于在場景生成的過程中被遮擋的像素總是被可見的像素所覆蓋，來實現(xiàn)三維景物的消隱.

對于BSP樹在生成可見面時會有兩種可能情況.如果視點在根節(jié)點多邊形的前面，則BSP樹按后枝、根節(jié)點多邊形、前枝的順序遍歷，而如果視點在根節(jié)點多邊形的后面，則按前枝、根節(jié)點多邊形、后枝的順序遍歷.

BSP樹從后向前遍歷算法可以描述如下：

DisplayBSPtree (BSPtree)

begin

if BSPtree is only one polygon then print(polygon);

else if BSPtree not empty then

if viewpoint in front of root polygon then

begin

call DisplayBSPtree(back_branch)

call DisplayBSPtree(root_polygon)

call DisplayBSPtree(front_branch)

end

else

begin viewpoint in back of root polygon

call DisplayBSPtree(front_branch)

call DisplayBSPtree(root_polygon)

call DisplayBSPtree(back_branch)

end

end

2 BSP樹遍歷算法的改進

從BSP樹遍歷算法中可以看出在生成BSP樹以后，對多邊形的生成是借助于樹的中序遍歷來實現(xiàn)的.然而BSP樹從后向前的遍歷算法是用遞歸來實現(xiàn)的.遞歸算法雖然從程序代碼上看來較為簡單，但是在具體實現(xiàn)時會導(dǎo)致很大的系統(tǒng)開銷[6，7].特別是在實時虛擬環(huán)境中，要求三維景物的生成快，真實度高.因此三維景物空間的消隱必須要求迅速生成，而且場景中的景物表面多邊形的存儲本身就占據(jù)了不少存儲空間，然而遞歸算法的巨大的時間、空間復(fù)雜度必然會給系統(tǒng)帶來重負，從而導(dǎo)致實時性的下降.

針對于這一問題，本文結(jié)合文獻[8，9]對BSP樹的遍歷算法作以下的改進.

首先，對于一個較小的場景所生成的BSP樹，由原來的鏈式存儲結(jié)構(gòu)改成用順序存儲結(jié)構(gòu)——一維數(shù)組進行存儲，以從左向右的方式按層次依次存儲[10].轉(zhuǎn)換的過程中要注意當BSP樹左或右分枝為空時，我們要用一個標志(假定用NO)來表示并且要把該標志存入數(shù)組中.轉(zhuǎn)換的最終目的是將BSP樹補充成一棵同原先的BSP樹等高的滿二叉樹[11].圖1.a將變成圖2的形式.要注意在轉(zhuǎn)換結(jié)束后回收原先鏈式存儲結(jié)構(gòu)所占的空間.

對于這棵滿二叉樹，我們利用它進行中序遍歷并繪制多邊形.對于順序存儲的滿二叉樹中序遍歷的非遞歸算法，我們加以修改可描述如下：

其中n表示樹的深度，N表示由BSP樹生成的滿二叉樹的節(jié)點數(shù)目.由滿二叉樹的特點可知：n=log2(N+1).

DisplayBSPInorder (BSPTree [1-N])

begin

for i = 1 to N

begin

num=i

key=0

while (num mod 2=0)

begin key=key+1

num=num/2

end

k=n-key

j=(num-1)/2;

if (BSPTree[2k-1+j]！=NO) then

//要判斷該節(jié)點是否是為了補滿樹形而加的空節(jié)點

print (BSPTree[[2k-1+j]);//繪制多邊形

end

end

3 性能分析

本文為了驗證采用順序存儲非遞歸算法遍歷的BSP樹消隱算法的性能，進行了仿真研究與分析.實驗環(huán)境為：PC機1臺，CPU為1.6GHz，內(nèi)存512M，操作系統(tǒng)為Windows XP.

為了測試改進后的BSP消隱算法，本文對三維場景中數(shù)目動態(tài)變化的多邊形進行實際測試.具體實驗方案為：由于三維場景中動態(tài)物體的不可預(yù)知性，為了保證實驗數(shù)據(jù)的真實性，對同一場景中參與測試的平均多邊形片數(shù)進行統(tǒng)計，同時對于傳統(tǒng)BSP樹和改進后的BSP樹消隱算法生成同一三維場景的繪制時間進行統(tǒng)計.表1為改進后的算法與傳統(tǒng)BSP樹消隱算法繪制時間的比較.其中n表示BSP樹的深度，N為測試用平均多邊形的片數(shù).從表1中可以看出，改進后的BSP消隱算法在運行效率上得到了大幅度的提高.

表1 改進后的順序存儲結(jié)構(gòu)非遞歸中序遍歷算法與遞歸中序遍歷算法的運行效率的比較

4 總結(jié)

BSP樹消隱算法是一種高效的在三維景物空間中實現(xiàn)消隱的算法，該算法特別適用于場景中物體固定位置不變, 僅視點移動的情況.本文在詳細探討了BSP樹模型的基礎(chǔ)上，針對于BSP樹的中序遍歷，以一種基于順序存儲結(jié)構(gòu)的非遞歸算法來代替通常的遞歸算法，有效的提高了BSP樹的遍歷速度，從而加速了三維景物消隱的生成.

[1] 石教英，主編.虛擬現(xiàn)實基礎(chǔ)及實用算法[M]．北京：科學出版社，2002.

[2] [美]羅杰斯(Rogers，D.F.)著，石教英，等譯.計算機圖形學的算法基礎(chǔ)[M]．北京：機械工業(yè)出版社，2002.

[3] LUEBKE D, ERIKSON C. View-dependent simplification of arbitrary polygonal environments[J]. Computer Graph ics, 1997,31(3):199-208.

[4] Harlen Costa Batagelo, Ilaim Costa Junior. Real-time shadow generation using BSP trees and stencil buffers[M]. Brazilian Symposium on Computer Graphics and Image Processing,1999：93-102.

[5] Samuel Ranta-Eskola. Binary space partioning trees and polygon removal in real time 3D rendering[M]. Sweden: Information Technology Computing Science Department Uppsala University. 2001:8-9.

[6] 張俊蘭，馮伍，高文全．幾種典型消隱面算法的性能分析[J].延安大學學報：自然科學版，2006,25(1)：17-20.

[7] 生濱，李東，徐學敢.緩沖區(qū)消隱算法的改進[J].計算機工程與應(yīng)用，2001.23:114-116.

[8] 吳福英，譚羅生，王明文．順序存儲的滿二叉樹中序遍歷的非遞歸算法[J].江西師范大學學報：自然科學版，2003,27(4)：372-375.

[9] 劉恒，江南，魏楠.基于BSP樹的啟發(fā)式陰影生成算法[J].計算機仿真,2006,23(11)：220-223.

[10] 李麗,戰(zhàn)守義.一種凸多面體的陰影生成方法[J].計算機仿真,2004,21(5):133-135.

[11] 于文洋,楊崇俊,樂小虬,陳飛翔.三維復(fù)雜場景管理研究[J].計算機工程與應(yīng)用，2006,13:38-40.

A Study and Realization of Binary Space Partitioning Tree Culling Algorithm

ZHAO Xiang-hao

(The Information Center, Anhui Province Committee Party School， Hefei 230022, China)

The Binary Space Partitioning tree algorithm is an usual culling algorithm in three-dimensional scene. Studying the current Binary Space Partitioning tree culling algorithm, we find that the recursion is used to realize the traversal of Binary Space Partitioning tree culling algorithm, which will lead to prodigious systematic spending in concrete realizing of real-time virtual environment. Based on analyzing the construction and traversal of Binary Space Partitioning tree, a non-recursion algorithm founded on the ordinal store structure is used to replace the usual recursion algorithm, which effectively enhances the traversal speed of Binary Space Partitioning tree and the creating culling speed of the three-dimensional scene, reduces the memory spaces of scene surface polygon, and is propitious to fast create the three-dimensional scene in real-time virtual environment.

Binary Space Partitioning tree algorithm； inorder traversing； culling； full Binary tree

10.14182/J.cnki.1001-2443.2015.05.004

2015-03-06

趙祥好(1969-)，男，安徽六安人，副教授，主要從事計算機技術(shù)應(yīng)用及信息處理方面的研究.

趙祥好.BSP樹消隱算法的改進研究[J].安徽師范大學學報：自然科學版，2015，38(5)：427-431.

TP391.41

A

1001-2443(2015)05-0427-05