(一)基本原理
用八叉树来表示三维形体,并研究在这种表示下的各种操作及应用是在进入80年代后才比较全面地开展起来的。这种方法,既可以看成是四叉树方法在三维空间的推广,也可以认为是用三维体素阵列表示形体方法的一种改进。
八叉树的逻辑结构如下:
假设要表示的形体V可以放在一个充分大的正方体C内,C的边长为2n,形体VC,它的八叉树可以用以下的递归方法来定义:
八叉树的每个节点与C的一个子立方体对应,树根与C本身相对应,如果V=C,那么V的八叉树仅有树根,如果V≠C,则将C等分为八个子立方体,每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据,就要被八等分(图2-5-1),从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白,或是完全为V占据,或是其大小已是预先定义的体素大小,并且对它与V之交作一定的“舍入”,使体素或认为是空白的,或认为是V占据的。
如此所生成的八叉树上的节点可分为三类:
灰节点,它对应的立方体部分地为V所占据;
白节点,它所对应的立方体中无V的内容;
黑节点,它所对应的立方体全为V所占据。
后两类又称为叶结点。形体V关于C的八叉树的逻辑结构是这样的:它是一颗树,其上的节点要么是叶节点,要么就是有八个子节点的灰节点。根节点与C相对应,其它节点与C的某个子立方体相对应。
因为八叉树的结构与四叉树的结构是如此的相似,所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。因而,根据不同的存贮方式,八叉树也可以分别称为常规的、线性的、一对八的八叉树等等。
另外,由于这种方法充分利用了形体在空上的相关性,因此,一般来说,它所占用的存贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮,这并不是八叉树的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可以求两个物体的并、交、差等运算),而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。不仅如此,由于这种方法的有序性及分层性,因而对显示精度和速度的平衡、隐线和隐面的消除等,带来了很大的方便,特别有用。
(二)八叉树的存贮结构
八叉树有三种不同的存贮结构,分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明,一对八式八叉树优点更多一些。
1、规则八叉树
规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下,只要描述它是灰、白、黑三类结点中哪一类即可),其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。
规则八叉树缺陷较多,最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示,而结点的描述用一个字节,那么存放指针要占总的存贮量的94%。因此,这种方法虽然十分自然,容易掌握,但在存贮空间的使用率方面不很理想。
2、线性八叉树
线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式),将八叉树转换成一个线性表(图2-5-2),表的每个元素与一个结点相对应。对于结点的描述可以丰富一点,例如用适当的方式来说明它是否为叶结点,如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样,可以在内存中以紧凑的方式来表示线性表,可以不用指针或者仅用一个指针表示即可。
线性八叉树不仅节省存贮空间,对某些运算也较为方便。但是为此付出的代价是丧失了一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点,那么必须先遍历了其余七个子图形对应的所有结点后才能进行;不能方便地以其它遍历方式对树的结点进行存取,导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用,但是仍很难令人满意。
3、一对八式的八叉树
一个非叶结点有八个子结点,为了确定起见,将它们分别标记为0,1,2,3,4,5,6,7。从上面的介绍可以看到,如果一个记录与一个结点相对应,那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处,而且还隐含地假定了这些子结点记录存放的次序。也就是说,即使某个记录是不必要的(例如,该结点已是叶结点),那么相应的存贮位置也必须空闲在那里(图2-5-3),以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费,除非它是完全的八叉树,即所有的叶结点均在同一层次出现,而在该层次之上的所有层中的结点均为非叶结点。
为了克服这种缺陷,有两条途径可以采纳。一是增加计算量,在记录中增加一定的信息,使计算工作适当减少或者更方便。
分享到:
相关推荐
八叉树三维数据结构与示例程序.doc
八叉树三维数据结构及示例程序文件.doc
八叉树结构是三维数据建模中研究和应用最为广泛的栅格数据结构。由于三维扫描的点云数据是基 于物体表面的,其空间离散程度远大于三维实体数据,一般的线性八叉树编码压缩方法都是基于实体数据的,不 能直接应用于三维...
八叉树结构是三维数据建模中研究和应用最为广泛的栅格数据结构。由于三维扫描的点云数据是基于物体表面的,其空间离散程度远大于三维实体数据,一般的线性八叉树编码压缩方法都是基于实体数据的,不能直接应用于三维...
八叉树的三维行程编码 paper 八叉树结构是 3D GIS中一种研究和应用最为广泛的栅格数据结构。在对线性八叉树编码方法进行 分析的基础上 ,将行程编码技术引入八叉树的数据压缩 ,形成三维行程编码方法。 并对三维行程...
基于八叉树结构的全局三维概率混合地图创建,刘忠泽,姜岩,基于八叉树结构的全局三维概率混合地图创建摘要:随着无人地面车应用场景的尺度和复杂度不断增加,2.5维栅格地图逐渐不能满足无人
八叉树模型是计算机科学中常用的一种非线性数据结构。它在 工程中有广泛的应用。笔者选用柱形坐标空间作为八叉树模型的根结点,提出了 一个由三维实体的CSG 模型按递归方式生成实体八叉树模型的算法,找出了八叉 树...
逐渐扩大,获得的相应的三维数据可达 TB 级。因此,如何合理的建立点云索引管理机制,是解决海量点云数据组织和 管理的关键问题。本文首先对传统八叉树数据结构的索引方法进行了优化,然后对三维点云分块,建立八叉树索引...
#资源达人分享计划#
#资源达人分享计划#
在高度真实感的场景绘制中,难免遇到场景中数据量巨大的问题,...作为一种在计算机图形学中广泛使用的树结构,八叉树在很多方面上都有应用。 此篇文章主要是针对实际开发进行讲解,有兴趣的小伙伴可以一起学习研究一下
八叉树结构是三维数据建模中研究和应用最为广泛的栅格数据结构。由于三维扫描的点云数据是基于物体表面的,其空间离散程度远大于三维实体数据,一般的线性八叉树编码压缩方法都是基于实体数据的,不能直接应用于三维...
算法使用八叉树结构生成三维模型的高度场表示,将传统的z向高度场扩展到x,y,z三个方向的高度场。首先,提出了三角面片预处理方法,保证模型精度和数据的完整性;其次,提出了基于投影变换的高度场表示判断及栅格化...
为了有效地表示三维GIS空间实体,在地质块段模型的基础上,提出了基于八叉树和四面体格网的混合数据结构模型(block octree tetrahedron,BOT模型)。采用BOT模型生成算法对块段模型进行重新分割,八叉树作整体描述,...
O-CNN是一个用于三维形状分析的框架,它利用八叉树结构来表示和处理三维形状数据,通过卷积神经网络进行特征提取和分类。项目结构清晰,代码注释详尽,适合用于学习和研究C++、Python、CUDA、MATLAB在三维形状分析中...
本文首先对传统八叉树数据结构的索引方法进行了优化,然后对三维点云分块,建立八叉树索引数据文件,同时用LOD方法对其进行分层抽稀操作,通过建立改进的八叉树与LOD方法相结合的索引,来降低内存的消耗、提高查询的效率,...