《点数据的八叉树模型.doc》由会员分享，可在线阅读，更多相关《点数据的八叉树模型.doc（5页珍藏版）》请在三一文库上搜索。
1、点数据的八叉树模型1、八叉树的原理八叉树(Octree)又称为分层树结构，它将指定的三维空间区域分成8个卦限(Octants),且在树上的每个非叶子节点处存储8个数据元素(体素)。每个元素称为体元，其对应的三维空间称为体素。假设要表示的形体V可以放在一个充分大的正方体C内，它的八叉树可以用以下的递归方法来定义：利用物体的最大和最小坐标值，围绕该物体定义一个平行六面体(包围盒)，把它分解成8个子立方体, 并对立方体依次编号为0, 1, 2,7。八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果V二C,那么V的八叉树仅有树根，如果VMC,则将C等分为 八个子立方 体，每个子立方体与树
2、根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分(图1),从而对应的节点也就有了八个子节点。这样的递归判断、分割一 直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。图1立方体的八叉树分割如此所生成的八叉树上的节点可分为三类：灰节点，它对应的立方体部分地为V所占据；白节点，它所对应的立方体中无V的内容；黑节点，它所对应的立方体全为V所占据。后两类又称为叶结点。因此，综上所述，形体V关于C的八叉树的逻辑结构是这样的：它是一颗 树，其上的节点要么是叶
3、节点，要么就是有八个子节点的灰节点，即若不为空树的话，树中任一节点的子节点恰好只会有八个或零个，也就是子节点不会有零与八以外的数目。根节点与c相对应，其它节点与C的某个子立方体相对应。2、建立八叉树的步骤(1) 设定最大递归深度；(2) 找出场景的最大尺寸，并以此尺寸建立第一个立方体；(3) 依序将单位元元素丢入能被包含且没有子节点的立方体；(4) 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体；(5) 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是
4、一样 数目，则再怎么切数目还是一样，会造成无穷切割的情形；（6）重复3,直到达到最大递归深度。3、八叉树的优点八叉树算法的特点是，数据结构简单，集合运算容易；形体上各元素己按空间位置排成了一定的顺 序，容易找到其所在的空间位置。因此，用八叉树来表示三维形体及3维空间中的场景管理，并研究在这种表示下的各种操作及应用，可以很快地知道物体在3D场景中的位置或侦测与其它物体是否有碰撞以及是否在可视范围内。八叉树算法的特点是数据结构简单，构造和集合运算容易；具有显式的层次信息且其各节点分布均 匀。通过八叉树划分方法，将场景内每个数据点分配到各个相应的子长方体中，通过搜索路径容易找到某一 长方体节点所在的
5、空间位置，并获得其父节点和兄弟节点，进而实现快速的kNN查询，这使得八叉树结构 十分适合基于外存的海量点云数据管理。此外，由于八叉树各节点具有明显的层次信息，且所对应的空间区域互不重叠，这使得该结构同样也十分利于三位 场景的视域裁剪、背景裁剪、遮挡裁剪和LOD细节模型等快速绘制算法的实现。可以说八叉树结构是一种十 分合适的海量点云多分辨率层次结构。4、八叉树的存储结构由于八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的 有关方法。八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树 也分别称为规则八叉树、线性八叉树以及一对八式八叉
6、树。不同的存贮结构的空间利用率及运算操作的方 便性是不同的。分析表明，一对八式八叉树优点更多一些。1）规则八叉树规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结 点的特性（在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可），其余的八个字段用来 作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而 结点的描述用一个字节，那么存放指针要占总的存贮量的94%。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。2）线性八叉树
7、线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树（例如以深度第一的 方式），将八叉树转换成一个线性表（图2-5-2 ）,表的每个元素与一个结点相对应。对于结点的描述 可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平 均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。0f2其线性表为，/U123.7CDEFGH树根耳时结点图2线性八叉树线性八叉树不仅节省存贮空间，对某些运算也较为方便。但是为此付出的代价是丧失了一定的灵活 性。例如为了存取属于原图形右下角的子图形对应的结点，那
8、么必须先遍历了其余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但是仍很难令人满意。3）一对八式的八叉树一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0, 1, 2, 3, 4, 5, 6,7o从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子 结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的（例如，该结点已是叶结点），那么相应的存贮位置也必须空闲
9、在那里（图2-5-3）,以保证不会错误地存取到其它 同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次岀现，而在该层次之上的所有层中的结点均为非叶结点。B0 12S .C D E F G H卜n图3 一对八式的八叉树为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一定的信息，使计算工作适当 减少或者更方便。四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值（或灰度）。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性
10、值或灰度为止。四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六 个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存 量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。线性四叉树则只存贮最后叶结点的信息。包扌舌叶结点的位置、深度和木结点的属性或灰度值。所谓深 度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规 则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的
11、 Mor ton 码。八叉树结构就是将空间区域不断地分解为八个同样大小的子区域（即将一个六面的立方体再分解为八 个相同大小的小立方体），分解的次数越多，子区域就越小，一直到同一区域的属性单一为止。按从下而 上合并的方式来说，就是将研究区空间先按一定的分辨率将三维空间划分为三维栅格网，然后按规定的顺 序每次比较3个相邻的栅格单元，如果其属性值相同则合并，否则就记盘。依次递归运算，直到每个子区 域均为单值为止。八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位，即八个指向子结点的指针，一个指向父结点的指针和一个属性值 （或标识号）。而线性八叉树则只需要记录叶结点的地址码和属性值。因此，它的主要优点是，其一节省存储空间，因为只需对叶结点编码，节省了大量中间结点的存储。每个结点的指针也免除了，而从根到 某一特定结点的方向和路径的信息隐含在定位码之中，定位码数字的个位数显示分辨率的高低或分解程度； 其次，线性八叉树可直接寻址，通过其坐标值则能计算出任何输入结点的定位码（称编码），而不必实 际建立八叉树，并且定位码木身就是坐标的另一种形式，不必有意去存储坐标值。若需要的话还能从定位码 中获取其坐标值（称解码）；其三，在操作方面，所产生的定位码容易存储和执行，容易实现象集合、相 加等组合操作。