基于八叉树的复杂产品模型实时绘制技术

赵 磊1, 2，赵 罡1, 2，谈敦铭1, 2



基于八叉树的复杂产品模型实时绘制技术

赵 磊，赵 罡，谈敦铭

（1. 虚拟现实技术与系统国家重点实验室，北京 100191；2. 北京航空航天大学机械工程及自动化学院，北京 100191）

给出基于OpenSceneGraph场景模型的信息提取方法，利用八叉树对场景模型进行分割和视锥体剔除，有效提高了实时绘制的效率，尤其是对浏览场景细节时的绘制效率提高最为明显。采用基于分页技术的Pagelod方法，实现模型的动态调度，以减少I/O的负载，满足在有限硬件条件下虚拟场景中复杂产品模型的实时绘制要求。

虚拟场景；实时绘制；复杂产品模型；八叉树

随着计算机技术的飞速发展，虚拟现实技术（Virtual Reality，简称VR），也称为虚拟环境（Virtual Environment，简称VE），已经对现代社会产生重要影响，并在改变人类的生活和工作方式。目前虚拟现实技术已经成功地应用在医学、军事、航空、制造业、建筑、教育、娱乐、销售等众多领域。

实时绘制（Real Time Rendering）是指系统在满足视觉无闪烁的限制内，完成对场景中各对象的位置和姿态的计算和场景、对象绘制；同时能够对用户的输入立即做出响应，并同步更新画面，实现用户与系统的实时交互。

目前实时绘制技术主要在LOD技术(Levels of Detail)、可见性剔除、分布式并行计算三个方面展开研究。

LOD技术是根据距离等因素采用细节程度不同的模型进行绘制的技术。这些细节程度不同的模型可以提前生成，也可实时生成。应用中多采用提前生成的方式，且一次性将层次细节模型文件读入内存。但当层次细节模型文件很大时将对计算机造成读写压力，影响实时绘制的效果。

可见性剔除是将位于视锥体外或不在视野内的模型从内存中剔除的技术。传统方法多通过计算场景中每一模型的包围盒与视锥体的相对位置来判断是否进行剔除。当场景中模型数量较大时，这种方式就会产生明显的延时。

分布式并行计算是在一组互联的计算机上同时实现虚拟现实技术，对计算机系统的I/O要求很高，这里不处理这种情况。

通过对复杂产品模型的分析，基于八叉树对场景模型进行分割、构建层次细节模型和进行视锥体剔除。基于Pagelod实现对大数据模型的动态加载，解决传统LOD文件需一次性读入内存的问题。

1 开发平台的介绍[7]

虚拟场景的渲染离不开3D API。目前通用的3D API有OpenGL和Direct3D。两种API各有优点，相对于Direct3D，OpenGL是一种开放性的标准，具有良好的跨平台性能。但OpenGL仍具有使用比较繁琐、渲染效率较低、开发周期较长等缺点。为了解决OpenGL的这些缺点，出现了很多封装OpenGL的高级3D API 如Open-SceneGraph（简称OSG），OpenGVS等，这其中又以OSG的性能最突出，渲染效率最高。

OSG图形系统是一个基于工业标准OpenGL，采用C++语言开发的软件接口。它让开发人员能够更快速、便捷地创建高性能、跨平台的交互式图形程序。

采用Visual Studio 2005 和OSG开发。

2 模型相关信息提取

虚拟场景中的模型多由外部软件建模完成，并保存或转换成能被虚拟场景支持的中间格式如.3ds，.obj等。OSG可以读取这些中间格式文件，但为了实现对模型的分割，必须提取场景中每一模型的基本信息（如点、线、三角形等）。

2.1 OSG的渲染场景图形组织方式

OSG场景图形采用一种自顶向下的，分层的树状结构来组织空间数据集，来提升渲染效率。每个OSG程序只有一个根节点(Root)，该根节点可以有多个子节点，子节点可以是叶节点(Geode)或组节点(Group)，如图1所示。叶节点保存了绘制场景所需要的几何信息(Geometry)和状态信息(State)，不能再有子节点。叶节点又由多个Geometry和State组成，每个Geometry都有一个State与其对应，这样的一个组合用Drawable来表示。几何信息集中了渲染本图形单元所需要的顶点、顶点索引、法线、三角形等信息，这些信息又是以数组的方式保存的。而状态则包含了渲染本图形单元所需的材质等信息。组节点(Group)可以有任意个子节点，而这些子节点既可以是叶节点又可以是组节点，这就为管理节点提供了可能。OSG中常用的节点类型还有：MaxtrixTransform(MT)节点、PositionAttitudeTransform(PAT)节点等。

图1 抽象的场景图

2.2 OSG中模型信息提取方式

实际场景的组织方式很复杂，如何准确获取其中每一叶节点的相关信息将会很困难。经过2.1节的总结可以看出，遍历场景根节点的每一子节点，若此子节点是叶节点则提取模型信息，否则继续遍历该子节点的所有子节点，当新的子节点为叶节点时提取信息，直到遍历完所有叶节点。根据这一思想，提出如下的模型信息提取方法：

Step 1 初始化

判断根节点是否有子节点，若无子节点退出，否则提取根节点中子节点的数量。

Step 2 提取子节点信息

判断节点类型，若为MT节点则要提取矩阵信息。若为PAT节点则要提取位置、朝向、姿态、比例等信息。MT节点和PAT节点都要提取参考框架(ReferenceFrame)类型。所有节点都要提取节点掩码(NodeMask)等。

Step 3 提取叶节点信息

分析子节点中的每个叶节点，并提取叶节点中的每个Drawable的几何和状态信息。

Step 4 循环与退出

若根节点中还有未被提取信息的子节点则执行Step 2，反之退出。

通过对场景模型信息提取，就将场景中每一模型转保存为一组基本信息，处理这些基本信息可以实现对场景进行精确分割、调整等操作。

3 模型分割

目前虚拟场景中的数据多采用树状结构的方法来表示。虚拟场景的树状结构表示减少了可见性计算、碰撞检测等，可以提高图形的实时绘制能力。目前通用的场景数据表示方法有：四叉树、八叉树、BSP树等。

四叉树是一种二维表示格式，是对二维平面在两个方向上进行连续分割以形成象限的方式得到，如图2(a)所示。由于该方法是一种二维表示方式，实际中多用于大地形数据的分割。

八叉树是可以看作是对四叉树在三维上的推广，如图2(b)所示。场景的八叉树层次结构在预处理阶段生成，在实时绘制阶段根据视点或距离原则对树结构进行自适应修改。

二叉树（Binary Space Portioning Tree，简称BSP），其思想是依据空间中的平面，将整个空间分割成两个半空间，根据这种思想实现场景分割，如图2(c)所示。相对于前两种方法，BSP树简单但是会产生更多的节点。

本文需要对复杂产品模型进行分割，从而生成层次细节模型。采用基于八叉树对场景模型进行分割，该方法停止递归的条件为达到了设定的分割层数或已无模型在当前节点内。下面将介绍创建的八叉树节点和模型分割算法。

(a) 四叉树

(b) 八叉树

(c) BSP树

3.1 八叉树节点

每个八叉树节点不仅要保存本节点的信息，通过该八叉树节点还应能够找到父节点(如果存在)和子节点(如果存在)。下面直接用C++伪代码描述八叉树节点所含信息。

class OctreeNode

{ 节点名称； 节点中心；

包围盒的长宽高； 节点所含的模型；

是否是根节点； 是否是最后一级节点；

八叉树的级别； 在父节点中位置；

八叉树节点所含模型的数量；

八叉树节点包围盒的八个顶点；

八叉树节点的八个子节点；

八叉树节点的父节点；

……

}；

3.2 模型分割

采用初始模型的包围盒作为八叉树根节点。对场景进行基于八叉树的分割，要通过多次递归才能实现，而其中一次的分割算法如下：

Step 1 初始化

待分割的模型(由一个或多个零件组成)，待计算的八叉树节点。

Step 2 计算零件包络体信息

提取待分割模型中的一个零件并计算其包围盒、包围球半径。

Step 3 分割零件

计算Step 2求得的包围盒的8个顶点与八叉树节点的位置关系。若8个顶点都在八叉树节点中，则将本零件加入到八叉树节点模型中；若待分割模型仍有零件未被处理，转Step 2；若待分割模型中不存在未被处理的零件则退出。若8个顶点不全在八叉树节点中，依据2.2节中的方式提取零件信息。

Step 4 分割和重构三角形

对提取到的每个三角形，先计算其最小外接圆(半径和圆心)，计算圆心和八叉树节点中心的距离，依据，，之间的关系分别处理：

（1）若<(+)则这个三角形可能和八叉树节点相交，计算三角形的三个顶点和八叉树节点的包围盒的关系，若三个顶点都在八叉树中则将本三角形添加到相应的数组中，否则按一个顶点在八叉树节点中、两个顶点在八叉树节点、三个顶点都不在八叉树节点中，这三种情况计算三角形和八叉树节点的交点，利用所求交点和原来在八叉树节点中的顶点创建新的三角形（注意：三角形的法线一定要和原三角形的法线同向），将新三角形添加到相应的数组中；

（2）若≥(+)则三角形和八叉树节点不相交。

Step 5 创建新叶节点

依据Step 3的结果新建Drawable，循环执行直到本节点中的Drawable都被处理。依据这些新建的Drawable创建新节点，并将这些新节点作为一个整体添加到八叉树节点中。

Step 6 循环处理与退出

若待分割模型中仍有未被处理的子节点，则执行Step 2，否则退出。

图3为模型分割方法在飞机机尾模型上的应用，图3(a)为原始飞机机尾模型，图3(b)为经过二级分割后的模型，其中的线框为分割后模型的每个八叉树子节点的包围盒，从图中可以看出被分割后的机尾与原始模型相比不仅保留了完整性而且具有很好的外观。

完成基于八叉树的模型分割后，就可以将分割后的最后一级节点已.ive或.osg格式保存到硬盘，形成一级层次细节模型文件。对同一模型的不同精度等级的模型分别进行分割就可以形成多级层次细节模型文件，为实时绘制做预处理。

(a) 原始模型

(b) 二级分割后的模型

图3 飞机机尾模型进行二级分割

4 动态加载和快速视锥体剔除方法

前文分析了传统LOD的缺点，本节将基于Pagelod实现以视点到模型中心点的距离为原则的动态加载。

为加快视锥体剔除效率，采用八叉树方式来构建场景，将视锥体与八叉树节点进行比较，来实现视锥体剔除。

4.1 动态加载模型

Pagelod就是采用分页数据库技术，以距离为原则动态加载相应的层次细节模型文件，由单独线程实现加载，因此效率远高于传统的LOD技术。

初始化时，只需给出保存层次细节模型文件的路径和名称，并设定各LOD节点在哪个距离段显示即可。渲染场景时，系统将自动选取需渲染的节点。这种方法对于简单的模型，视觉上会产生一定的跳跃，但是对于复杂的场景并采用比较连续的简化模型将减少跳跃感。

4.2 基于八叉树的视锥体剔除

本节将利用第3节的分割结果实现视锥体剔除。

计算机绘制场景的步骤为：视图变换，模型变换，投影变换和视口变换。在实际应用中，尤其对于从文件读取的模型不用进行模型变换，只要获得视图变换、投影变换和视口变换的矩阵，就可以获得模型绘制对模型要进行的变换。

视锥体是一个平截头体，其可以通过一个单位正方体的各面与一个变换矩阵()相乘获得。这个变换矩阵，可以通过获取当前场景的视图变换矩阵()和投影变换矩阵()，并将它们相乘获得，即：=*。例如：初始化单位正方体（如图4(a)）的6个面分别为+++=0。以每个平面的参数，，，构造向量=（，，，），=*，设新=（′，′，′，′），则′，′，′，就为新平面方程的系数，如此则得到当前视锥体的六个面的平面方程，如图4(b)所示。

(a) 初始的单位视锥体 (b) 变换后得到视锥体

采用如下的方法确定一个八叉树节点是否位于视锥体外部：

判断八叉树根节点的八个顶点和八叉树节点中心是否在视锥体外，若都在视锥体外部，则将根节点及其下所有子节点的位于视锥体外的标志量设为true，并将根节点下所有模型节点的可见属性设为false；否则递归判断八叉树的八个子节点(节点中若没有模型则不用判断)是否在视锥体外。

位于视锥体外的节点再次进入视锥体内时：

首先判断八叉树节点的八个顶点是否位于是视锥体内，若都位于视锥体内部，且当前八叉树节点的位于视锥体外的标志量为true，则将八叉树节点和其子八叉树节点的位于视锥体外的标志量设为false，并将本八叉树节点下的所有模型节点的可见属性设为true，并将这些模型节点加载到场景绘制中。

这种剔除方式对实时绘制速度有明显的提高，尤其在浏览场景细节时提高的最为明显。

5 实验结果与分析

将上文的方法在PC机（奔腾4 CPU 3.00G,内存1.00G）上实现。原始模型如图5(a)所示，由348万个顶点、418万个三角形组成。对该模型进行多级分割实验，结果如表1所示。从表1中可以看出，二级分割和三级分割后增加的顶点数量和帧频率的降低情况相近，而三级分割和四级分割则产生了太多的顶点同时帧频率也产生了明显降低。对模型进行二级分割后的结果如图5(b)所示。

表1 模型多级分割数据

对原始模型简化（每次减少10 %），形成了100%到10%的11级LOD。表2中的前三组数据给出了100%、50%、10%三组模型经实时绘制方法处理后的帧频率变化情况。由于分割造成模型的顶点和三角形增多，所以帧频率出现了一定的衰减，但衰减的量不多。表2中后两组数据，分别为当场景中显示如图5(c)、图5(d)的细节，采用实时绘制方法前后的帧频率。从细节1的数据可以看出，虽然显示相近的细节部分但采用实时绘制技术后场景中实际绘制的三角形数量却减少了很多，帧频率也出现了明显的提高。细节2，相对于模型整体只显示了很小一部分信息，大部分数据被剔除出场景，场景中绘制的三角形的数量非常少，极大地提高了帧频率。

表 2 实时绘制五组数据

由以上实验和分析可知，对模型采用合适的分割级数，可以明显提高实时绘制的效率。

6 结束语

给出了模型信息提取的有效方法，基于八叉树实现了对OSG场景中模型的分割算法和视锥体剔除方法，提高了模型绘制的速度，在显示模型细节时绘制速度提高的更明显。采用基于分页数据库的Pagelod实现了模型的动态加载。但由于八叉树节点的构造是均匀的，没有考虑模型在空间上分布的不均衡，所以当浏览模型细节时若细节所在处模型集中，则场景中绘制的顶点会很多，帧频率只会产生一定的提高；当场景中显示的细节不集中，则场景中绘制的顶点数会非常少，帧频率能够产生极大的提高。

(a) 原始模型     (b) 分割后场景中的模型

(c) 细节1      (d) 细节2

图5 整体模型与细节显示

[1] Stytz M. Distributed virtual environments [J]. IEEE Computer Graphics and Application, 1996, 16(3): 19-33.

[2] Burdea G C, Coiffet P. 虚拟现实技术[M]. 魏迎梅, 等译. 北京: 机械工业出版社, 2005. 231-270.

[3] 冀俊峰. 细节模型实时绘制加速技术研究[D]. 北京:中国科学院研究生院, 2005.

[4] 陈雷霆. 三维复杂场景实时绘制技术[D]. 成都: 电子科技大学, 2007.

[5] DeHaemer Jr M, Zyda M J. Simplification of object rendered by polygonal approximations [J]. Computer & Graphics, 1991, 15(2): 175-184.

[6] Airey J. Towads image realism with interactive update rates in complex virtual building environm ents [J]. Computer Graphics, 1990, 24(1): 41-51.

[7] OpenSceneGraph 说明手册[EB/OL]. http://www. open-scenegraph.org/projects/osg/wiki.

Real-time Rending for Complex Product Model Based on Octree

ZHAO Lei, ZHAO Gang, TAN Dun-ming

( 1. State Key Laboratory of Virtual Reality Technology and Systems, Beijing 100191, China; 2. School of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100191, China )

In order to improve the efficiency of real-time rendering, a method to extract the model information of OpenSceneGraph using scene model dividing up and view frustum culling based on Octree is proposed. This method has a better performance when visualizing the detail scene of virtual environment. Pagelod, which is based on DatabasePager, is also applied to implement the dynamic data translation, reduce the I/O overload greatly and satisfy real-time requirement for complex product model in virtual environment under limited hardware resources.

virtual environment; real-time rendering; complex product model; octree

TP 391

A

1003-0158(2011)03-0069-06

2009-12-30

虚拟现实技术与系统国家重点实验室探索性自选课题资助项目（200806123）

赵 磊（1986-），男，江苏宿迁人，硕士研究生，主要研究方向为CAD/CAM。