基于BSP树的三维场景渲染方法研究

乔云婷，张 弘

(渭南师范学院数学与信息科学学院，陕西渭南714099)

0 引言

在虚拟现实场景漫游中，观看者移动视点的位置就需要计算机以实时的速度对场景进行处理．通常计算机通过对隐藏面的消除来提高渲染速度，常用的方法有z缓冲算法、画家算法，但这些方法都有一定的局限性，而BSP树能够实现三维场景的快速分割，提高场景的预处理速度．对较大规模三维场景渲染来说，整体分割较为复杂，如果将场景中的物体进行预处理，经处理后的模型表面作为分割平面建立BSP树，就能够快速构造BSP树，快速确定视野体里的模型，使得视野体内的模型能参加观察变换和象素填充．

1 预处理三维场景方法

1．1 包围体的概念

包围体就是将物体组合完全包容起来的一个封闭空间．将复杂物体封装在简单的包围体中，能够提高几何运算的效率［1］．包围体的常见类型有包围盒、包围球、包围柱、离散定向多面体等，在一般的网络游戏或虚拟现实世界三维场景中，遇到的物体形状十分复杂，需要将多种包围体的类型加以灵活运用，表1是几种包围体的比较．

表1 几种不同的包围体

包围体的几何形状数量有限而且相对简单，然而实际遇到的物体一般由多边形或者通过处理成为近似多边形的数据结构组成，［1］因此对包围体的检验一般要比直接对于物体的检验速度快．为了得到复杂物体的包围体，首先需要分析场景中物体的形状特征，运用不同类的包围体将场景中的物体进行分解．如图1所示，我们对一组三维场景用包围体进行处理．

图1 用包围体对场景进行处理的效果

1．2 备选平面法向量列表的构建

这里，我们以包围盒(AABB)为例［2］．

Step1:建立场景中要以包围盒处理的物体模型．

Step2:通过平面中三个不共线的点，作出两个相交的向量求出该平面的法向量，针对重复的面，可能会有两个相反的法向量，只选取一个平面法向量即可．

Step3:求出该平面的法向量并将求得的向量加入到备选平面法向量列表中．

Step4:在一个完整的模型中需要定义一个变量Face关联该模型所有的备选法向量．

1．3 分割面的选择

分割平面必须是对凹多面体而言的，如果已经形成了凸多面体的空间就不必分割．对于一个凹体而言［3］，分割平面必须在平面的正负方向均出现三角形．如此递归分割下去，就能保证将空间最终分割成大量凸多面体集合，分割出来的结果最好是让一棵树平衡，平衡二叉树的操作较快，冗余度小．它的时间复杂度为O(n2)［4］(n是量备选平面法向量列表中平面法向量的数量)．通常在实际的应用中加上相应的限制条件，其时间复杂度会小于O(n2)．

1．4 建立BSP树

空间二分就是递归地通过直线对平面进行分割［4］．如图2所示，l1分割整个平面，然后l2分割l1上方的平面，l3分割下方的平面，以此继续分割．分割线不仅会分割平面，也将物体分割成若干碎片，像这样一直分割下去最终每个子区域中只包含一个碎片．这个过程，就将平面的物体表示成一个二叉树．在这个二叉树中，每片叶子分别对应的是最终所得子区域划分中的一个面，即就是落在这个面中的物体的碎片，将存储在该片叶子中．每个二叉树的节点则分别对应一条分割线，这条分割线也就存储在这个节点中，如果场景中包含一维的物体，这个物体就有可能被包含在一条分割线中，此时，对应的内部节点需要存储一个列表，记录这个物体．

图2 空间二分树及其对应的树形表示

树的遍历 对于潜在的可见模型可以通过 树的遍历来获得 这样能够减少可见性检测时的模型数量［5］．本方法中虽没有对模型进行遮挡剔除的处理，但通过包围盒的简化，已经使得该BSP中的三角数极大地减少．在BSP的遍历过程中只需要判断视野中模型的顶点在当前节点所包含的分割面中的正面或者是负面，对于物体模型跨越分割面这类情况，可以先遍历当前节点的左子树，后遍历右子树．通过判断模型包围体与视野体之间的关系，就能够确定视野内的模型．通过上述方法，可以得到渲染后的三维场景模型．

2 实验验证

通过实验验证预处理之后BSP树的加速渲染效果．

2．1 实验平台

实验软件平台为Autodesk 3D Studio Max 2012，硬件平台如表2．

表2 实验平台的配置

2．2 实验对象

我们用一组虚拟的建筑模型场景作为实验对象．如图3所示，实验中的物体模型主要为3DS模型，实验中场景的长和宽均为1024，视野体的近平面和远平面分别为1000和3000．

图3 实验的三维效果图

在该三维场景条件下，通过移动视点获得测试数据如表3所示．由表3中数据可以看出，通过预处理的BSP树的渲染与一般BSP树的渲染，前者通过对模型的预处理的BSP遍历得到潜在可见模型的数量要小于一般的BSP树渲染，它最终只渲染在视野体内出现的模型．而后者需要对场景内的所有模型进行处理．通过上述实验可以看出，在由许多小模型所组成的大规模场景中，用包围体处理后的BSP树的方法，能够大大提高渲染效率．

表3 一般BSP树与模块化BSP树渲染时间对比

3 结语

本文通过对由许多小模型所组成的三维场景漫游特点的分析，给出了一种提高渲染效率的方法，并通过实验证实了在三维场景中运用包围盒将物体模块化分类，有助于提高对场景BSP树的划分效率，提高三维场景的显示速度．需要指出的是，这种方法对小规模的三维场景渲染速度提高较多，但是对大规模的场景提高并不显著，需要进一步将该方法进行扩展，使其能够应用在其他大规模场景的渲染和建筑群的全景虚拟．

(指导教师 刘 军)

［1］李儒茂，郭翠翠．虚拟现实编辑器标准教程［M］．北京:印刷工业出版社，2013．

［2］孙巍，刘金义．基于物体级BSP树的大规模室外场景渲染［J］．微处理机，2010，(6):68－69．

［3］罗运和，戴青．计算机图形学基础［M］．北京:中国计量出版社，2003．

［4］Berg de M，Kreveld van M，Overmars M，etal．Computational Geometry Algorithms and Applications［M］．第2 版．邓俊辉，译．北京:清华大学出版社，2005．280 －294．

［5］陶志良，成迟薏，潘志庚，等．多分辨率 BSP树的生成及应用［J］．软件学报，2001，12(1):118－125．

［6］耿国华．数据结构:用C语言描述［M］．北京:高等教育出版社，2011．155－161．

［7］吕旭东．基于画家算法的多面体的消隐方法［J］．计算机辅助设计与图形学学报，1999，11(2):125－128．

［8］［美］卡斯尔曼．数字图像处理［M］．朱志刚，译．北京:电子工业出版社，1998．