耿 宏，刘增森

（中国民航大学电子信息与自动化学院，天津 300300）

0 引言

飞机虚拟维修以培训受训者的维修操作技能为目的，其场景由特定的维修环境、维修工具和维修对象组成，而场景管理的好坏对最终的培训效果有着直接影响。目前最常用的场景管理方式有场景图、八叉树、四叉树和二叉树等。其中场景图主要是对二维动态场景的管理，而八叉树、四叉树和二叉树主要针对静态场景进行管理[1]。由于八叉树算法充分利用了物体在三维空间上的相关性，并且具备构造简单、使用方便等特点，进而被广泛应用于虚拟现实系统的场景管理中。然而基于传统八叉树对飞机虚拟维修场景进行管理会有以下不足：

1）若一个对象横跨在某个节点的任一划分平面上，那么它就会被存储在那个节点中，当对象很小而用于存储它的节点很大时，大大降低空间划分的效率。

2）在维修过程中，当移动对象时，为表现出它的运动，必须更新八叉树中相应部分，这会增加系统的计算开销[2-4]。

3）传统八叉树中不存在对象的概念，场景中所有三角面片视为整体，在维修过程中无法快速定位到维修对象和维修工具，导致无法满足与场景对象进行动态交互的要求。

针对以上问题，通过虚拟维修场景与现实世界进行比较，采用松散八叉树和面向对象概念相结合，构成一种面向对象的松散八叉树。利用树的“松散”特性，将对象尽量放在树的更深层次，以提高场景划分效率；利用对象的尺寸、中心点确定其应处的节点，避免对树的重建，以降低因其移动造成的场景更新时间开销；利用对象的结构树，构建用于存储其几何、物理等信息的AABB树，将对象从场景整体三角面片中划分出来，以满足与场景对象进行动态交互要求。

1 面向对象松散八叉树基本原理

面向对象松散八叉树基本结构由模型对象化和场景空间剖分两部分组成，如图1所示。前者依据对象结构树来构建零件、组件、产品各层次模型的AABB树，根据系统交互需求，在对象AABB树根节点包围盒中加入相关属性索引，其索引内容包括对象的几何、物理、运动类型等信息，对象的三角面片存储在AABB树特定层次的特定包围盒中，图1中RP、RA、RC分别表示产品、组件、零件的根节点，反向虚箭头表示产品AABB树是采用自下而上的方式构建，L、R为零件树的左右子节点，Le为包含面片的叶节点；后者采用松散八叉树对AABB树根节点八叉剖分，以树叶节点存储对象AABB树，构成一棵面向对象的松散八叉树，其中R代表整个虚拟场景的根节点，N为组结点，R到N之间的虚线段代表省略了其上层的非叶节点，Ge为包含模型对象的叶节点。

图1 面向对象松散八叉树基本结构图

2 面向对象松散八叉树模型构建

2.1 场景模型的对象化

将场景模型从面片中分离并形成可交互的对象需以下步骤：

1）根据结构树构建零件AABB树，并在相关节点植入对象信息。除节点索引等信息外，在根、叶节点包围盒添加了对象属性信息索引，属性信息以XML单独存储，中间节点包围盒数据结构除不包含属性信息索引外与根节点相同[5-6]。图2为零件AABB树根、叶节点的数据结构，其中属性信息索引、左右子节点索引均以4 Byte的int型数据表示，6个坐标值以4 Byte的float型数据表示，Flchild，Frchild用于判别根节点的左右子节点是否为叶节点，以1字节char型数据表示，若是叶节点取值为true，否则取false。

表1 AABB树根、叶节点包围盒数据结构表

要构建一棵包含零件属性信息的AABB树，需对零件根节点AABB分割直至叶节点包围盒只含有一个三角面，文中采用分裂平面法对AABB分割，构建过程为：①构建零件的根节点包围盒，记为V；②使用最长轴法确定根节点V的分裂轴，即选择方向轴使包围盒沿轴线方向最长，设轴的方向向量为，轴线由两个面的交线表示，即，均为已知系数；③采用中值法确定分裂点以定位分裂平面，设TCi为节点中三角面片的中心坐标，则

设分裂轴上n个投影点的中值坐标为TC_CENTER，则中值坐标可由下式求得，

④利用分裂平面将当前节点中的三角面片划分到左右两个子节点中，取分裂平面上任意点的坐标e，令分别为左右子节点包含的三角面数，依据表1判定三角面片应处的子节点。

表2 面片应处节点判定表

⑤将左右子节点作为根节点，返回步骤②直到每个叶节点包围盒仅含有一个三角面片。

2）根据零件AABB树构建组件AABB树

若一个组件由n个零件组成，分别以M1～Mn表示，B（M1）～B（Mn）为 M1～Mn的 AABB 树根节点，为构建 AABB 树，CBVT（M1～Mn）利用零件树的根节点建立父节点CB（M1～Mn）将它们联系起来，它可表示为B（M1）～B（Mn）的并集[7-8]。

另外，根据AABB的定义可得

表3为组件树根节点的数据结构，根据结构树，一个产品由N个组件构成，则产品AABB树可由N个组件的AABB树整合而成，其构成原理与组件AABB树相同。

3）对象AABB树的更新

设Bcenter为包围盒中心初始坐标，最大、最小值顶点为Bmax、Bmin，运动后的最大、最小值顶点为B'max，B'min，B'center为运动后的包围盒中心，B'center沿 X，Y，Z轴的平移向量为

表3 组件树根节点的数据结构

Bcenter绕 X，Y，Z轴的旋转角度分别为 α，β，θ，旋转矩阵分别设为Rot（x，α），Rot（y，α），Rot（z，α），绕X轴旋转得，，同理可得绕Y，Z轴的旋转矩阵分别为。若对象只进行平移运动，只需求出变换后的最大、最小值点即可确定新位置处对象的包围盒，即。当对象发生旋转运动时，不能直接利用旋转矩阵将包围盒变换到新位置，这里采用一种技巧，首先测出包围盒最长边的长度，记为Len，对象旋转后以B'center为中心，边长为len的立方体作为新包围盒，B'center经旋转运动后的位置可以用旋转矩阵求得，假设包围盒中心点依次绕Z轴、Y轴、X轴旋转，设ROT为旋转矩阵，则

2.2 场景的空间剖分

定义空间为包含多个对象模型的立方体，采用松散八叉树对其在X，Y，Z 3个方向上剖分，这里涉及到约束条件的建立、对象AABB树根节点的剖分、树的更新。

约束条件为树的最大分裂深度Dmax，和节点可包含的最大面片数Fmax，两参数确定方法如下：设传统八叉树某一节点的包围盒边长为u，松散系数为k，松散后的包围盒边长为L，则 L=ku，k∈（1，+∞），设场景根节点包围盒边长为U，在深度d下的松散节点包围盒边长为L=k×U/2d，设对象AABB树根节点包围盒的最大边长为l，对于含有n个对象模型的场景，设lmin为所有对象树根节点包围盒l的最小值，为保证场景中最小八叉树节点的包围盒可包含最小的对象AABB树根包围盒，令L≥lmin，得：

基于AABB树根节点包围盒对场景剖分时，若当前节点深度小于Dmax且包含的三角面片数大于Fmax，则对该节点继续划分，直到满足约束条件要求。在剖分过程中，该树结构可将对象尽量存储在更深层次的节点中，以此提高划分效率，基本原理是：若对象横跨划分平面，常规的处理方法是把该对象存储在当前两节点的上一层节点，这里将节点边长扩大k倍，以便对象可被深层单个节点容纳，这种处理方法将对象存储在树更深层次的节点中[9]。

当对象移动时，须对八叉树进行更新，其基本原理如下：

在松散八叉树中，对于一个特定的物体，它应插入的深度和节点可根据其尺寸大小和中心位置求得[10]。对于给定深度depth的松散节点，它在该深度任意位置可容纳小于等于八叉树节点包围盒边长1/2，大于1/4的对象AABB树根节点包围盒，尺寸比此更小的包围盒应存在更深层次的节点中。

由以上可得下列各式：

则取depth的极大值为

设对象AABB树根节点包围盒中心点坐标为Ocenter，由depth已知，此时只需选择距离中心坐标最近的节点作为存储物体的节点，所有节点的中心坐标集合可表示为：

则节点node的索引公式可表示为：

其中find为自定义函数，作用是搜索距Ocenter最小点，并输出与其对应节点信息。

3 实例

为验证本文算法的有效性，将文中算法、传统算法分别应用到飞机虚拟维修机库AH（Aircraft hangar）、电子设备舱 EEC（Electronic equipment cabin）场景，对所测性能数据进行统计和对比。图2为机库场景的实现图，运用其Ⅰ～Ⅳ阶段实现算法如下：

Ⅰ该阶段是将零件模型对象化。首先，获取对象的最大、最小值顶点坐标，建立其AABB树根节点包围盒，以梯子横板为例，其最大、最小值坐标分别为：

图2 文中算法在机库场景的实现图

其次，遍历构成该对象的所有三角面片，获取面片总数 n 和顶点坐标（pi，qi，ri）ni=1，由式（1）到式（3）求得分裂点 TC_center=（452.129，532.915，29.75），测得n=2 158；最后，根据表2判定面片应处的子节点位置，首次分裂最长轴方向向量 a取（0，0，1），重复以上步骤对子节点分裂，直到每个节点只包含一个面片，依据表1完成对零件AABB树根节点和叶节点相关索引信息的添加。

Ⅱ此阶段的任务是在Ⅰ的基础上，将组件或产品模型对象化处理。图2中横板和支撑杆作为构成梯子16零件中的两个，虚线表示省略了其他零件，测得AABB树16个根节点的包围盒的最大、最小值顶点为：

根据式（4）可得

由此可构建梯子AABB树，依据表3完成根节点相关索引信息的添加。

Ⅲ该阶段是在Ⅰ、Ⅱ阶段的基础上，利用松散八叉树对场景进行八叉剖分，本文取k=2、=3，同时测得 U≈350，lmin≈8，NUMmin=1 371，则据式（8）、式（9）可得Dmax=6，Fmax=4 113，以两参数为约束条件，完成对场景的剖分。

Ⅳ该阶段主要处理场景中运动对象的更新问题，这里的更新包括两方面，一是对象AABB树的更新，二是松散八叉树的更新。由图2，梯子由位置A移动至位置B，其转换过程为先绕Z轴旋转8°，即α=0°，β=0°，θ=8°，测得梯子初始包围盒中心 Bcenter=（898.795，586.029，32.135），再按平移矩阵（-36.182，127.23，0.0）T进行平移到达B 位置，

结合式（5）～ 式（7）得

利用len=36.327作出对象运动后的AABB树。对象运动后还需对八叉树更新，已知梯子的l≈36，则根据式（10）可得 depth=3，结合式（11）得梯子应放节点的索引公式

其 i=1，…，n，（xi，yi，zi）遍历节点自动获取。

表4和图3记录了传统算法与本文算法在飞机虚拟场景管理方面的性能参数，这里将平均绘制帧速、场景更新平均耗时和平均交互灵敏度（受训者点击交互对象到对象响应时间间隔）作为两者对比主要的性能参数。场景更新平均耗时选用飞机电子设备舱进行测试，通过改变设备舱内移动物体的数量，记录在两种算法下场景更新时间变化。

表4 两种算法下帧速、灵敏度对比表

图3 AH、EEC场景更新时间对比图

由表4，与传统算法相比，本文算法在机库和飞机电子设备舱内的平均绘制帧速分别提高了34.8%、19.8%，平均交互灵度分别降低了62.3%、46.8%的时间开销，由图3，在本文算法下，随着场景中移动对象的增多，场景更新操时间并没有显著增加。

4 结论

针对飞机虚拟维修场景的组织管理效率低的问题，提出一种面向对象松散八叉树场景管理方法，将面向对象概念和松散八叉树相结合，以树叶节点来存储包含对象属性信息的AABB树，利用该方法对维修对象和工具进行快速的定位、简化了运动物体更新操作过程、降低了场景更新时间开销，最终提高了飞机虚拟维修场景的组织管理效率。