八叉树数据模型在三维地质建模中应用.docVIP

八叉树数据模型在三维地质建模中应用 　　摘要介绍三维地质建模中的八叉树数据模型,并设计一个三维地质建模的实验系统,对这个实验系统实行的算法进行分析,实验分析结果表明实验系统和同类系统比具有很大的优越性。 　　关键词八叉树;三维地质建模;三维地质体 　　中图分类号TP3文献标识码A文章编号1673-9671-(2010)061-0097-01 　　 　　1八叉树数据模型 　　八叉树是一种能很好的表示三维地质体的数据结构,他能做到在压缩数据的同时很好地表达地质体的几何特征,它表现为以分支关系定义的层次结构或树形结构,对地质体的空间分析具有别的存储结构达不到的优势。 　　一般把三维地质体放在一个2n×2n×2n的立方体内,2n为立方体的边长,立方体与八叉树的根结点相对应;若整个立方体被地质体完全充满,那么这个八叉树就只有一个节点――根结点;否则这个立方体要继续分解成8个相等的子立方体,称为八分体(Octant)。每个八分体与树根的一个子结点相对应,八分体的边长为根立方体边长的1/2。对每个八分体,如果为空或为实节点,则该八分体不再分解;若八分体为部分满,则该八分体进一步分解为八个子八分体;如此递归地分解,直到每个子八分体已达到分解的精度,或子八分体均为全满或全空为止。 　　通过递归分解,最终形成一棵度为8的树,即八叉树(Octree)。若经过n次分解,n为八叉树的分辨精度或分辨率,立方体的边长为2n。整个立方体空间用八叉树的根结点表示;部分满的八分体对应于八叉树的分支结点,称为灰结点(Grey Node);全满或全空的八分体对应于八叉树的叶结点,分别称为黑结点(Black Node)或白结点(White Node)。结点的层次(Level)从根结点开始定义,根结点为第0层,根结点的所有孩子结点为第1层,第1层结点的所有孩子结点为第2层,依此类推。八叉树的每个结点由1个编码(code)和8个指向结点的指针(指针号为0-7)组成。如果code=black,则该结点所表示的空间部分全部为实心,且指针0-7为0,亦即该结点为叶结点。如果code=white,则所表示的空间部分全为空,该结点亦为叶结点。第三种情况是code=grey,说明所表示空间部分为实,部分为空,在这种情况下,8个指针指向8个子结点。这些子结点与它们的父结点的一个规则划分相对应。 　　设立方体空间的上为N,下为S,左为W,右为E,前为F,后为B,则八个八分体可分别表示为NWF、NEF、SWF、SEF、NWB、NEB、SWB、SEB,并对其有如下编号: 　　NWF-0,NEF-1,SWF-2,SEF-3,NWB-4,NEB-5,SWB-6,SEB-7。 　　八叉树方法充分利用了形体在空间上的相关性,与体素模型相比,它节省了存储空间,而且仍自然地表达了空间实体。 　　八叉树最自然的存储方式,每个结点可以用一条记录和八个指针表示。在立体造型中,八叉树一般由体素构成。每个体素类型与八叉树结点两者之间需要一分类例程,它应区分下列三种情况:1)被考虑的结点完全在体素外;2)被考虑的结点完全在体素内;3)被考虑的结点部分在体素内。 　　分类例程采用递归方式。首先被研究的空间用一个结点来描述,其code=white,而且算法从单个的white编码的结点开始。每个结点用分类例程对体素分类,如果全空则结点被标识为white,如果全满则结点被标识为black,否则将结点标识为grey,继续将它按上述方法进行分解,并且对每个卦限调用其本身,继续划分到节点为全空、全满、或者到预先设定的分辨率为止,根据地质体的大小,通常需要8-13级的八叉树。下列程序给出八叉树构造算法的概要,按体素的类型码、维数和方向参数来表示实体的体素。 　　记录存储结点的属性,而八个指针存储了指向其他子结点的地址。这种结构虽然简单,但是指针部分耗费了大量的存储的存储空间。假定假定每个指针要用2个字节表示(最小情况),而结点描述用1个字节,那么存储指针的空间也要占总空间的94%,因此,在海量空间数据存储时,这种算法特别浪费存储空间。为了解决存储浪费的空间这个问题,有学者提出了线性八叉树的方法。并在此基础上发展出来虚拟八叉树和线性八叉树来面向各种应用的需求。而为了克服八叉树模型描述表面精度能力较弱的缺点。还有学者提出了使用多分辨率的扩展八叉树结构。 　　2八叉树数据模型三维地质建模算法实验系统 　　利用VC++6.0和OpenGL实现了文中提出的算法,开发出了算法的实验系统,并在实验系统上进行了实验。 　　算法实验系统由四大模块构成:1)构建线性八叉树模块(Octreeshe 　　ngch):主要功能是对指定地质体空间8n地质体进行体素化,通过划分的体素构建相应的线性八叉树;2)构建临时线性八