BSP树消隐算法的改进研究

赵祥好

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

BSP树消隐算法的改进研究

赵祥好

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

BSP树算法是在三维景物空间中实现消隐的一种常见算法.BSP树消隐算法中的遍历算法通常是采用递归来实现，在实时虚拟环境具体实现时会导致很大的系统开销.本文在分析BSP树消隐算法中的BSP树的构造和遍历方法的基础上，以一种基于顺序存储结构的非递归算法来代替通常的递归算法，有效的提高了BSP树的遍历速度，提高了三维景物空间的消隐的生成速度，降低了场景中的景物表面多边形的存储空间，有利于实时虚拟环境中三维景物的快速生成.

BSP树算法；中序遍历；消隐；满二叉树

在虚拟现实环境的设计中要求计算机所制造的三维虚拟环境能够使用户忘掉现实世界，获得全身心对VR世界的真实体验，产生沉浸于等同真实环境的感受和体验.在虚拟环境的设计中必须要使用户观察到的场景是同真实世界一样的三维场景，这就要求我们对虚拟环境中的场景绘制必须具有真实感和高质量.虚拟环境中的场景常包含众多的三维景物，基于真实环境的情况，采取一定的视点和视线方向时，必定会存在三维景物的一些表面被遮挡住而导致不可见，这一问题被称为三维景物空间的消隐[1].BSP树算法正是在三维景物空间中实现消隐的一种算法，该算法特别适用于场景中物体固定位置不变, 仅视点移动的情况，且与其他消隐算法相比，执行较为高效.本文在深入研究BSP树算法的基础上，对其进遍历部分采用基于顺序存储结构的非递归方法进行了改进，有效地提高了利用BSP树算法生成场景的效率.

1 BSP树消隐算法

在虚拟环境中的场景常常包含许多多边形，在绘制这些多边形时，鉴于真实性，必须考虑到在给定某一个视点时，沿一定的视线方向，哪些景物的表面多边形是可见的，哪些是不可见的.实际上一个物体离视点越远，它越有可能被一个距离视点较近的物体遮挡[2].BSP树算法(又被称为二叉空间剖分树可见面算法)是基于取任意视点绘制一个多边形时，只需先绘制其远离视点一侧的所有多边形，然后绘制该多边形，最后绘制位于其视点另一侧的所有多边形，即可获得正确绘制结果的原理.BSP树算法在具体生成三维空间场景的消隐时分为两步，先构造BSP树，再显示它.

1.1 构造BSP树

BSP树算法是递归地将景物空间分成两个子空间的.首先可以从场景中的多边形集合中任意选取一个多边形作为分割面.场景中的其他多边形，完全位于分割面前侧或后侧的多边形被归入相应的前半或后半子空间中，与分割面相交的多边形沿分割面分割成两部分，分别放入相应的前半或后半子空间中.从前半和后半子空间中再分别选取一个多边形作为分割面，递归的分割下去，直到每个子空间中只剩一个多边形为止.这个将景物空间分割的过程可以用二叉树来表示，二叉树的根是最初选择作为分割面的多边形，这样景物空间就可以用一棵BSP树完全表示出来.

图1给出了一个简单的场景以及其构造出的BSP树.假设该景物空间中存在五个多边形ABCDE，其中多边形A、C、E所在的平面垂直于纸面.首先选取多边形A作为分割面，分割面与多边形B相交，将多边形B分成两个多边形B1和B2.多边形B1和C在分割面的前侧，多边形B2、 D和E位于分割面的后侧.接着从树的前枝中选取多边形C作为分割面，再次分割.其前枝子空间中包含B1，后枝子空间为空.然后退回到树根，再从树的后枝中选取多边形E作为分割面，分割后多边形D归入其前枝子空间，多边形B2归入其后枝子空间.这样每一个分枝子空间中都只含有一个多边形，所以这个简单的场景分割完毕.

构造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树生成以后，根据BSP树确定可见面时，仅需知道视点与树的根节点多边形的相对位置关系即可.对BSP树采取中序遍历即可确定可见面.BSP树可见面算法的基本思想是先将离视点最远的多边形写入帧缓存或进行显示，即按从后到前的顺序对多边形进行绘制[3，4，5].这种从后到前的显示方法是基于在场景生成的过程中被遮挡的像素总是被可见的像素所覆盖，来实现三维景物的消隐.

对于BSP树在生成可见面时会有两种可能情况.如果视点在根节点多边形的前面，则BSP树按后枝、根节点多边形、前枝的顺序遍历，而如果视点在根节点多边形的后面，则按前枝、根节点多边形、后枝的顺序遍历.

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树以后，对多边形的生成是借助于树的中序遍历来实现的.然而BSP树从后向前的遍历算法是用递归来实现的.递归算法虽然从程序代码上看来较为简单，但是在具体实现时会导致很大的系统开销[6，7].特别是在实时虚拟环境中，要求三维景物的生成快，真实度高.因此三维景物空间的消隐必须要求迅速生成，而且场景中的景物表面多边形的存储本身就占据了不少存储空间，然而递归算法的巨大的时间、空间复杂度必然会给系统带来重负，从而导致实时性的下降.

针对于这一问题，本文结合文献[8，9]对BSP树的遍历算法作以下的改进.

首先，对于一个较小的场景所生成的BSP树，由原来的链式存储结构改成用顺序存储结构——一维数组进行存储，以从左向右的方式按层次依次存储[10].转换的过程中要注意当BSP树左或右分枝为空时，我们要用一个标志(假定用NO)来表示并且要把该标志存入数组中.转换的最终目的是将BSP树补充成一棵同原先的BSP树等高的满二叉树[11].图1.a将变成图2的形式.要注意在转换结束后回收原先链式存储结构所占的空间.

对于这棵满二叉树，我们利用它进行中序遍历并绘制多边形.对于顺序存储的满二叉树中序遍历的非递归算法，我们加以修改可描述如下：

其中n表示树的深度，N表示由BSP树生成的满二叉树的节点数目.由满二叉树的特点可知：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

//要判断该节点是否是为了补满树形而加的空节点

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

end

end

3 性能分析

本文为了验证采用顺序存储非递归算法遍历的BSP树消隐算法的性能，进行了仿真研究与分析.实验环境为：PC机1台，CPU为1.6GHz，内存512M，操作系统为Windows XP.

为了测试改进后的BSP消隐算法，本文对三维场景中数目动态变化的多边形进行实际测试.具体实验方案为：由于三维场景中动态物体的不可预知性，为了保证实验数据的真实性，对同一场景中参与测试的平均多边形片数进行统计，同时对于传统BSP树和改进后的BSP树消隐算法生成同一三维场景的绘制时间进行统计.表1为改进后的算法与传统BSP树消隐算法绘制时间的比较.其中n表示BSP树的深度，N为测试用平均多边形的片数.从表1中可以看出，改进后的BSP消隐算法在运行效率上得到了大幅度的提高.

表1 改进后的顺序存储结构非递归中序遍历算法与递归中序遍历算法的运行效率的比较

4 总结

BSP树消隐算法是一种高效的在三维景物空间中实现消隐的算法，该算法特别适用于场景中物体固定位置不变, 仅视点移动的情况.本文在详细探讨了BSP树模型的基础上，针对于BSP树的中序遍历，以一种基于顺序存储结构的非递归算法来代替通常的递归算法，有效的提高了BSP树的遍历速度，从而加速了三维景物消隐的生成.

[1] 石教英，主编.虚拟现实基础及实用算法[M]．北京：科学出版社，2002.

[2] [美]罗杰斯(Rogers，D.F.)著，石教英，等译.计算机图形学的算法基础[M]．北京：机械工业出版社，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] 生滨，李东，徐学敢.缓冲区消隐算法的改进[J].计算机工程与应用，2001.23:114-116.

[8] 吴福英，谭罗生，王明文．顺序存储的满二叉树中序遍历的非递归算法[J].江西师范大学学报：自然科学版，2003,27(4)：372-375.

[9] 刘恒，江南，魏楠.基于BSP树的启发式阴影生成算法[J].计算机仿真,2006,23(11)：220-223.

[10] 李丽,战守义.一种凸多面体的阴影生成方法[J].计算机仿真,2004,21(5):133-135.

[11] 于文洋,杨崇俊,乐小虬,陈飞翔.三维复杂场景管理研究[J].计算机工程与应用，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-)，男，安徽六安人，副教授，主要从事计算机技术应用及信息处理方面的研究.

赵祥好.BSP树消隐算法的改进研究[J].安徽师范大学学报：自然科学版，2015，38(5)：427-431.

TP391.41

A

1001-2443(2015)05-0427-05