点数据的八叉树模型.docVIP

点数据的八叉树模型 1、八叉树的原理 八叉树(Octree)又称为分层树结构，它将指定的三维空间区域分成8个卦限(Octants)，且在树上的每个非叶子节点处存储8个数据元素(体素)。每个元素称为体元，其对应的三维空间称为体素。 假设要表示的形体V可以放在一个充分大的正方体C内，它的八叉树可以用以下的递归方法来定义： (包围盒)，把它分解成8个子立方体，并对立方体依次编号为0，1，2，…7。八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果V＝C，那么V的八叉树仅有树根，如果V≠C，则将C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分（图1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。????如此所生成的八叉树上的节点可分为三类： ????灰节点，它对应的立方体部分地为V所占据； ????白节点，它所对应的立方体中无V的内容； ????黑节点，它所对应的立方体全为V所占据。 ????后两类又称为叶结点。形体V关于C的八叉树的逻辑结构是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点根节点与C相对应，其它节点与C的某个子立方体相对应。3，直到达到最大递归深度。 3、八叉树的优点 八叉树算法的特点是，数据结构简单，集合运算容易；形体上各元素已按空间位置排成了一定的顺序，容易找到其所在的空间位置。因此，用八叉树来表示三维形体3维并研究在这种表示下的各种操作及应用3D场景中的位置或侦测与其它物体是否有碰撞以及是否在可视范围内。 八叉树算法的特点是数据结构简单，构造和集合运算容易；具有显式的层次信息且其各节点分布均匀。通过八叉树划分方法，将场景内每个数据点分配到各个相应的子长方体中，通过有哪些信誉好的足球投注网站路径容易找到某一长方体节点所在的空间位置，并获得其父节点和兄弟节点，进而实现快速的kNN查询，这使得八叉树结构十分适合基于外存的海量点云数据管理。此外，由于八叉树各节点具有明显的层次信息，且所对应的空间区域互不重叠，这使得该结构同样也十分利于三位场景的视域裁剪、背景裁剪、遮挡裁剪和LOD细节模型等快速绘制算法的实现。可以说八叉树结构是一种十分合适的海量点云多分辨率层次结构。 4、八叉树的结构 八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。 ?规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可)，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。 规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94％。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。 线性八叉树 ?线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表（图2-5-2），表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。???? 线性八叉树不仅节省存贮空间，对某些运算也较为方便。但是为此付出的代价是丧失了一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点，那么必须先遍历了其余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但是仍很难令人满意一对八式的八叉树 ???? 一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点)，那么相