一种基于八叉树的动态场景管理方式

张宇

摘要：在高度真实感的场景绘制中，相当多的应用需要一棵树结构来管理整个场景。对场景的搜索意味着对树结构的遍历的过程，物体的变化意味着对树结构的重新建立过程。这些工作都是相当耗费资源却又无法避免的过程。该文通过建立一棵八叉树来管理整个场景，使用树结点的编码，经过相对简单的计算来得到某结点的相邻结点的编码，并结合树的有序结构，来完成了高效的对于树结点的查找和部分树结构的重建工作。

关键词： 动态场景；八叉树；编码

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）14-0054-04

1 引言

在高度真实感的场景绘制中，常常需要使用一棵树结构来管理整个场景的数据。常见的有BSP树，kd树，八叉树等[1][2]。这样通过对场景的划分，将场景中的各种数据存储到树的各个叶结点中。但是如果我们在搜索某个物体的具体位置的时候，难免需要对整棵树进行遍历。对于动态场景来说，在物体运动过程中，整个场景的树结构不会是一成不变的，因此还涉及到树结构的重建。与前两种结构想比，八叉树具有更直观的特性，并且容易控制，可以根据各种需要设置各种分割标准。作为一种在计算机图形学中广泛使用的树结构，八叉树在很多方面都上都有应用。对其的遍历过程实际上就是找出一系列满足给定要求的结点的过程。在对于这个问题已经提出的方法中，大致分为两类：第一，自底向上的方法。比如在光线追踪中，从光线开始的叶结点出发，按照光线的方向搜索它的兄弟结点和父结点等，以得到一系列的叶结点[3] [4] [5]。第二，自顶向下的方法。它是从树的根结点开始，递归的搜索整棵树的结构，如果当前结点有光线通过，则将当前结点加入到待求序列中，直到搜索完所有的叶结点为止[6] [7] [8] [9] [10]。但是上述方法中都很少对物体发生运动后如何改变树结构进行讨论。本文在八叉树的基础上，设计了动态场景的管理模式，下文结构如下：

第二部分： 编码方法。简要介绍我们对八叉树进行编码的基本方法 。

第三部分：介绍我们用于动态场景管理的数据结构和方法。

第四部分与第五部分得出结论并对将来工作进行展望。

2 对于八叉树的编码及计算方法

我们对八叉树的每个结点进行编码，通过编码结合树结构来完成对八叉树相邻结点的查询[11]。如图1所示， 线性八叉树的编码基准体系划分为：

如果当前编码为0的结点需要进行下一层剖分，则它的八个子结点的编码按照类似顺序依次为：00，01，02，03，04，05，06，07其它依次类推。对于任一结点编码A = q1q2…qi…qn，

我们首先判断其是否为边界结点， 若从q1至qn全部属于E 8 或S 8 或W 8 或N 8 或U 8 或D8，则在有公共面的相邻结点中，其对应的东部结点或南部结点或西部结点或北部结点或上部结点或下部结点将分别不存在。

我们就可以通过当前结点的编码来计算出它的相邻结点的编码，但是要注意这里的计算是采取八进制的。对于相邻的上下结点间的计算如下：若 qn 属于上部集合，根据八叉树编码标准体系，可以直接得其下面结点的编码为A + 4， 而其上面相邻结点编码的求解则要经过如下判断：从编码的末位qn按从右到左的顺序扫描， 直到找到第一个不属于上部集合的编码qi （1≤i≤n- 1， i 为从左到右的码位序号）为止，显然右边的n- i个编码位都属于上部集合，将它们的值均加4，qi的值减4，而q1q2…qi-1的值不变，此时得到的新编码即为所求相邻的上部结点的编码（若找不到不属于上部集合的编码，则表明该结点为上边界结点，其上相邻结点不存在，下面的类似）。若qn 属于下部集合， 则其上面相邻结点编码为A - 4， 对其下部相邻结点编码的求解， 也可从编码的末位qn 按从右到左的顺序扫描， 直到找到第一个不属于下部集合的编码qi （1≤i≤n- 1）为止，显然右边的n- i个编码位都属于下部集合，将它们的值均减4，qi的值加4，其余的不变，得到的新编码即为所求相邻下部结点的编码。

对于已知结点东、南、西、北四个方向相邻结点的编码，当末尾qn 分别是0或者4，1或者5，2或者6，3或者7时，采取相同的计算方法。这样，我们就可以通过当前已知结点的编码，得到和它有公共面的相邻结点的所有编码。这种结算方式将在我们的动态场景管理模式中使用，另一方面，在计算过程中相邻结点大小不一致的情况将在下文中进行讨论。

3 基于八叉树的场景管理

我们选取八叉树来对整个场景的结构进行组织，用它来划分整个场景的空间，划分的标准是八叉树的单个结点内最多含有的物体数量。在开始讨论前，为了方便与直观先进行几项假设：第一，假设与在场景中的物体所占有的空间相比，整个场景的空间占有绝对性优势，换句话说，整个场景的空间范围远大于整个场景中所有物体所占有的空间范围；第二，假设树结构建立后，场景中的最大物体占有的空间范围不会超过最小的结点的空间范围，也就是说，不会有物体在树结构刚建立好的时候占有一个结点以上的空间，并且在树结构发生改变后也不会有这样的情况出现。由于我们主要考虑的问题就是当场景中有物体发生运动或者其他改变的时候，整个场景的树结构跟着变化的过程。在这样的过程中，整棵树都重新建立一次是不太现实的，会造成过多的时间和计算开销；整棵树完全不变也是不太可能的，这样很难反映出场景中发生的变化；只将发生变化的那部分树结构进行重建是一种相对比较好的选择。因此，我们将场景中的物体数据和树结构分离开来，在树结构中不涉及到具体的物体数据，只存储指向每一个物体数据的指针，这样在发生变化时只需要进行指针的移动而不用移动大量的数据。例如有一个物体M当前位于A结点内（为划分后的叶子结点，下同），将向A结点右边相邻的B结点运动，如图2所示。则只需要将存储在A结点内的指向物体M的指针转赋给B结点并清除A结点内的指针即可。

3.1 八叉树的建立

建立树的过程如下所述：第一步，建立一个根结点，将场景中的所有物体都赋予该结点。第二步，判断此结点是否满足划分要求（比如，单个结点中最多只能有一个物体存在），如果满足要求，则分别判断每个物体在根结点中的所在位置，在相应位置分别生成相应的子结点，将物体赋予生成的结点，并将其父结点中的该物体撤销掉。第三步，对每一个子结点重复步骤二，直到没有可以再次划分的结点为止。最后物体只应该存在于八叉树的叶结点中。假设在场景初始化的时候，生成如下所示的树型结构（未含有物体的叶结点没有表示出来）：

3.2 动态场景的管理

3.2.1 编码的应用

这时我们就可以通过计算A的右边相邻结点B的编码，然后搜索上述结构，得到结点B的位置。由于我们计算编码的方法是按照都是同一层次的结点计算的，所以这里存在搜索不到的情况，这表示结点B和结点A不是一个层次上的，我们需要采取不规则处理。基于我们的假设一，树中含有物体的叶结点数量会远小于总结点数量，并不会使用太多的额外存储开销，所以这样的搜索效率远远高于去遍历树来得到结点B的位置。事实上在一般空间场景中，这样的假设总是成立的，故这样的方法是可行的。

3.2.2 不规则相邻结点的处理

在实际测试中，发生这种情况的概率很大，因此这部分才是影响我们方法的主要部分。在下面的讨论中，为了绘图直观，我们用平面的四叉树来代替立体的八叉树，但是在方法上二者是一致的。分别由两种情况存在：分别是物体从层次较底的结点（半径较大的结点）向层次较高的结点（半径较小的结点）运动或者相反。

如图5.a和5.b 所示，当物体从层次较低的结点向层次较高的结点运动时，我们按照上述方法计算出的结点编码实际上是结点B的编码q1q2…qi…qn，因此我们不会在当前的MAP结构中搜索到结点B。我们需要得到的是结点B2的编码，显然，在当前MAP结构中的编码位数小于n的结点不符合要求，将剩下的结点编码按照从左向右完全匹配的原则，重新搜索q1q2…qi…qn，我们将得到q1q2…qi…qn …q n + m 这样的编码值，若未能得到结果，则将如图6.c或者图6.d 所示。此时我们选取相对位数较少的编码q1q2…qi…qn …q n + m，寻找该结点的父结点，直到得到编码为q1q2…qi…qn的结点为止，即为当前的结点B。判断交界点P位于结点B的位置，如果当前位置有已存在的结点，则将物体加入到该结点中，并判断此结点现在是否需要进行划分，如图5.a。如果当前位置没有已存在的叶结点，则建立一个结点，其父结点为B，将其添加到八叉树中，如图5.b。如果当前位置有存在的非叶子结点，则重复上述方法，直到确定该目标结点的准确位置为止。

如图5.c和5.d所示，当物体从层级较高的结点向层次较低的结点运动时，我们按照上述编码方法找到的结点实际上是结点B的一部分。因此我们将计算结果q1q2…qi…qn去掉最后一位，变成q1q2…qi…q n – 1，然后在MAP中按照从左到右的原则进行匹配搜索，如果能得到完全一致的结果，即为在MAP中有q1q2…qi…q n – 1该编码的存在。则如图5.c所示，将物体加入到该结点中并判断是否需要进行下一层次的划分。如果没有完全一致的结果，不过搜索到q1q2…qi…q n – 1 …q n – 1 + m这样的编码，则从中选取位数较小的一个，寻找该结点的父结点，直到得到编码为q1q2…qi…q n – 1的结点为止，即位当前的结点B，如图5.d所示。判断交界点P位于结点B的位置，此时当前位置不会有已存在的叶结点，如果当前位置没有已存在的结点，则建立一个结点，其父结点为B，将其添加到八叉树中。如果当前位置有存在的非叶子结点，则就变成如图5.a或5.b所示的情况。如果上述搜索没有得到合适的结果，再去掉编码的最后一位，变成q1q2…qi…q n – 2重复上述过程，当该值只剩下一位数时仍然没有得到结果的话，则在根结点的相关位置建立此结点并添加到八叉树中。

之前A作为包含物体的叶结点总是存在的，在物体M离开结点A后，如果结点A内部仍然有物体存在，则这部分树结构保持不变。如果结点A内没有物体，则我们需要把结点A从树结构中删除和在MAP中删除。然后考虑A的父结点是否还满足划分条件，如果满足的话则其余结构不用更改，如果不满足则需要将该父结点的其他子结点从上述两个结构中删除，并将属于其他子结点的物体赋予给该父结点，然后再加入到MAP中。对于有物体进入的结点B，我们在上述处理结束后，从MAP中删除掉已经在树结构中不存在的叶结点，并加入新生成的有物体存在的叶结点。

当我们在MAP中没有搜索到求出的编码值q1q2…qi…qn时，此时就面临着选择该运动情况是从层次较高的结点向层次较低的结点还是从层次较低的结点向层次较高的结点。实际上只有一种可能，因此我们要尽量避免多余的判断和计算。我们假设在当前整棵树中，最深层次为a，在我们的定义中，结点的层次n在数值上越大，则它的层次越低。若结点A的层次n < a/2，则我们的判断先向更高的层次进行，也就是说对于从结点A运动到结点B的物体，我们先按照上述从低层次结点向高层次结点运动的方法处理，若这样没有得到我们想要的结果，则按照相反的方向进行处理。若结点A的层次n >= a/2，则我们按照先按照高层次结点向低层次结点运动的方向处理，未能得到结果再反过来处理。

3.2.3 场景裁减

由于我们采用的八叉树结构每个结点都是立方体，因此对于场景裁减的操作比较简单。用当前MAP中的叶结点的六个面和视角锥体进行比较，很容易得出哪些结点完全位于场景裁减中，哪些部分位于以及哪些不在其中，完成对整个场景的裁剪。

4 实验结果与结论

测试场景由12个精细的并且都能够在场景中自由运动的物体构成，在它们开始运动之前，场景与树结构如图6所示。经过一段时间的运动后，场景与树的结构如图7所示。在这个过程中，八叉树的结构一直随着物体的运动发生改变，中间没有停顿。在我们的例子中，黄色的线表示结点的范围，蓝色的线表示物体的AABB包围盒[12]，它是用来进行碰撞检测的。整个方法的工作情况和我们之前讨论的一致，因此这是一种有用的管理动态场景的方法。

5 未来工作展望

由于暂时缺乏时间，没有来得及进行大规模的数据测试，故这是我们下一步需要进行的工作。在这之后，可以更改八叉树的划分标准，比如单个结点内表面的多边型数量。在这种情况下，我们可以将对物体LOD模型的操作和整个场景结合起来，进一步提高渲染效率。

参考文献：

[1] GLASSNER A.An Introduction to Ray Tracing[M]. Morgan Kaufmann， 1989.

[2] HAVRAN V.Heuristic Ray Shooting Algorithms[D].Czech Technical University in Prague， 2001.

[3] Glassner A S. Space Subdivision for Fast Ray Tracing[J]. IEEE Computer Graphics & Applications， 1984，4（10）：15-22.

[4] Samet H. Implementing Ray Tracing with Octrees and Neighbor Finding[J]. Computer & Graphics，1989，13（4）：445-460.

[5] Samet H.Applications of Spatial Data Structures： Computer Graphics， Image Processing， and GIS. Addison-Wesley，1990.

[6] Agate M， Grimsdale R L， Lister P F. The HERO Algorithm for Ray Tracing Octrees. Advances in Computer Graphics Hardware IV R.L. Grimsdale， W. Strasser （eds） Springer-Verlag， New York， 1991.

[7] Cohen D， Shaked A. Photo-Realistic Imaging of Digital Terrains[J]. Computer Graphics Forum， 1993，12（3）：363-376.

[8] Endl R， Sommer M. Classification of Ray-Generators in Uniform Subdivisions an Octrees for Ray Tracing[J]. Computer Graphics Forum，1994，13（1）.

[9] Jansen F W. Data Structures for Ray-tracing. Data Structures for Raster Graphics L. Kessner， F.Peters， M. van Lierop （eds）. Springer-Verlag， 1985：57-73.

[10] Gargantini I， Atkinson H H. Ray Tracing an Octree： Numerical Evaluation of the First Intersection[J]. Computer Graphics Forum， 1993，12（4）.

[11] 肖乐斌，龚建华，谢传节.线性四叉树和线性八叉树邻域寻找的一种新算法[J]. 测绘学报， 1998，27（3）.

[12] Gottschalk S.Collision Dctection Using Oriented Bounding Boxes[D]. Dept. Comput. Sci.， UNC Chapel Hill， 2000.