基于密集型区域的八叉树划分算法

2012-06-13张佳杰黄海端

科技传播 2012年2期

关键词：八叉树存储空间密集型

张佳杰，黄海端

河北联合大学迁安学院，河北迁安 064400

基于密集型区域的八叉树划分算法

张佳杰，黄海端

河北联合大学迁安学院，河北迁安 064400

虚拟场景中数据量的存储是关系查找速度的关键问题，本文针对传统八叉树存储的不足，采用密集型八叉树组织场景，利用改进的八叉树对虚拟场景进行划分。实验结果表明：此种八叉树的划分方法，充分发挥了空间划分的优势，节约了存储空间，加快了场景的查找速度。

虚拟场景；密集型区域；八叉树

注：本文系唐山市科技局项目（NO: 09130201C）

0 引言

随着虚拟现实技术的日益成熟，虚拟场景越来越复杂，要存储的数据量也越来越大，迫切需要一种高效存储结构解决这一问题。八叉树是一种较常用的空间数据组织结构，目前，研究者们主要针对分布较松散的区域采用八叉树进行可见性裁剪，来减少确定对象的处理时间以及存储空间。而对于密集型区域的场景数据，采用传统的八叉树存储结构进行划分其查找时间和存储空间的代价较大。针对这一问题，提出了一种基于密集型区域的八叉树划分算法。通过实验分析此种八叉树的划分方法，充分发挥了空间划分的优势，节约了存储空间，加快了场景的查找速度。

1 八叉树存储结构

八叉树（Octree）是一种用于描述三维空间的树状数据结构，也是由四叉树推广到三维空间而形成的一种三维栅格数据结构。八叉树的每个结点表示一个正方体的体积元素，每个结点有八个子结点，将八个子结点所表示的体积元素加在一起就等于父结点的体积。用八叉树来表示三维形体，可以认为是用三维体积阵列表示形体方法的一种改进。它作为一种场景组织方法，广泛应用于虚拟现实系统，可显著减少对场景中多边形进行排序的时间。Octree用于3D空间中管理场景时，可以快速确定物体在3D场景中的位置，是否在可视范围内，并侦测是否与其它物体有碰撞产生。

传统八叉树是将一个立方体的三维空间均匀的分割成8个单元，其根表示了整个场景，如果8个子空间内的物体属性相同就不再划分。否则，将该子空间再细分为八个空间，如此递归下去，直到每个子空间内物体的属性均相同或达到规定的限差为止。传统八叉树有三种不同的类型，分别为规则八叉树、线性八叉树和一对八式八叉树。

规则八叉树的存储结构用一个由九个字段的记录来表示树中的每个结点，如图1所示。其中一个字段用来描述该结点的特性，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存储结构方式。

图1 规则八叉树的存储结构

规则八叉树的最大问题是指针占用了大量的空间。假设每个指针占用两个字节，结点的描述占用一个字节，那么只是指针的存储就要占去存储空间的94%。因此，尽管规则八叉树方法自然，并且容易掌握，但由于其在存储空间的使用率方面很差，开发者很少使用这种方法。

线性八叉树注重考虑如何提高空间利用率。例如，采用深度优先次序遍历一棵八叉树，先将八叉树转换成一个线性表，表的每个元素对应一个结点，如图2所示。对于叶结点可以用适当的方式来说明，如果不是叶结点就将其八个子结点值的平均值作为非叶结点的值。这样，可以在内存中以紧凑的方式来代替指针表示线性表。

图2 线性八叉树的存储结构

线性八叉树运算起来比较方便，而且节省了存储空间。但是丧失了一定的灵活性，增加了各结点的遍历时间。例如，要存取某图形右下角的子图形对应的结点，必须先遍历前面的七个子图形对应的所有结点后才能进行，降低了运算效率。因此，尽管线性八叉树的应用在很多文章中都进行了讨论，但是仍很难达到令人满意的效果。

一对八式的八叉树是指非叶结点均有八个子结点，将八个子结点分别标记为0，1，2，3，4，5，6，7。一对八式的存储结构中一个记录对应一个结点，记录描述该结点的八个子结点的特性值，指针描述该八个子结点所对应记录的存放处，并且在指针中还隐含了这些子结点记录存放的次序，如图3所示。这样造成了空间的浪费，即使该结点已是叶结点，它相应的存储位置也必须保留，为的是保证存取的准确性。这种方法只适合完全八叉树，而该完全八叉树还必须满足所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。

图3 一对八式八叉树的存储结构

2 基于密集型区域八叉树算法

为了解决八叉树存储空间浪费以及遍历时间长的问题，提出基于密集型区域八叉树的存储方式。密集型区域八叉树的网格划分算法是对每个子空间重新建立最小包围盒，这样避免了在建立顶点树时，由于该部分顶点在空间上分布不均匀而导致树的深度的增加，进而减少了存储空间，加快了网格模型数据的读取速度。另外，由于建立了顶点的最小包围盒，在误差较小时，只有空间距离比较近的顶点才会聚合在一起；而相距较远的顶点只有在深层次简化时才会聚合，这些特点在一定程度上保证了简化时网格模型的逼真度。

密集型区域八叉树划分方法的算法描述如下：

1 ）找出场景的最大尺寸，使用包围盒方法建立模型的最小包围盒；

2 ）以包围盒的X轴、Y轴、Z轴方向的中分面作为分割基准，将包围盒平均划分为八个子包围盒，在每个子包围盒中将紧凑部分的物体用更小的包围盒包围，进行进一步的划分；

3 ）如果每个子空间内存在物体的属性不相同或未达到规定的限差，则重新从1）开始进行划分，直到子包围盒物体跟上一层包围盒物体一样为止。否则，划分结束，并对划分后的每一个结点记录下一结点的编号、划分标志、结点在顶点树中的深度以及它所含的景物面片表的入口指针。

下面是根据生成虚拟场景的二维地图，采用密集型区域八叉树的划分算法划分虚拟场景的过程及生成的顶点树，划分过程共分为三步如图4所示：

图4 密集型区域八叉树的划分过程

图5为根据划分过程产生的顶点树。根据生成的顶点树，可知基于密集型区域的八叉树生成过程首先由根结点生成整个树结构，然后再对网格模型进行划分，当结点空间确定后，如果它是叶结点，可根据整个景物空间的三角片表来确定该结点空间的三角片表；如果不是，再查找它的子结点直至获得它的三角片表，最终完成对整个虚拟场景的划分。