基于八叉树的复杂地质体块段模型建模技术.pdf

第3 7 卷第4 期中国矿业大学学报 V 0 1 ．3 7N o ．4 2 0 0 8 年7 月 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g yJ u l ．2 0 0 8 基于八叉树的复杂地质体块段模型建模技术 毕林1 ，王李管1 ’2 ，陈建宏1 ，冯兴隆1 1 ．中南大学资源与安全工程学院，湖南长沙4 1 0 0 8 3 ； 2 ．长沙迪迈信息科技有限公司，湖南长沙 4 1 0 0 8 3 摘要为了有效地减少地质块段模型的数据量，提高建模过程中运算速度及准确性，采用八又树 结构表达块段模型，对三维目标空间进行块段细分；提出八叉树与有向有界箱 0 B B 树相交测试 算法以提高建模过程中的运算速度，同时改进射线法判断点在多面体内外及点在面状模型上下 的算法，以确保复杂地质体块段模型建模的准确性．用C 开发语言实现建模算法并与其它同 类软件相比较，结果表明采用该方法从表面模型到块段模型的转换速度比目前国际上常用的矿 业软件要快3 0 ％～4 0 ％，结果准确，所需存储空间较小，便于空间检索与分析，对于地质模型的 工程应用具有重要意义． 关键词八叉树；块段模型；O B B 树；相交测试；轴分离理论 中图分类号P2 0 8文献标识码A文章编号1 0 0 0 一1 9 6 4 2 0 0 8 0 4 一0 5 3 2 0 6 S t u d yo fO c t r e e B a s e dB 1 0 c kM o d e lo f C o m p l e xG e o l o g i c a lB o d i e s B IL i n l ，W A N GL i g u a n h 2 ，C H E NJ i a n _ h o n 9 1 ，F E N GX i n ．- l o n 9 1 1 ．S c h o o lo fR e s o u r c e sa n dS a f e t yE n g i n e e r i n g ，C e n t r a lS o u t hU n i v e r s i t y ，C h a n g s h a ，H u n a n4 1 0 0 8 3 ，C h i n a ； 2 ．D i g i t a lM i n eC o ．L t d ，C h a n g s h a ，H u n a n4 1 0 0 8 3 ，C h i n a A b s t r a c t I no r d e rt or e d u c et h ed a t aa m o u n to fg e o l o g i c a lb l o c km o d e l ，a n di m p r o v et h es p e e d a n da c c u r a c yo fm o d e l i n g ，ab l o c km o d e lw a su s e st os u b d i v i d et h et a r g e ta r e ab a s e do no c t r e e ． A na l g o r i t h mo ft h ei n t e r s e c t i o nt e s tb e t w e e no c t r e ea n do r i e n t e db o u n d i n gb o x O B B t r e ew a s p r o p o s e dt oi m p r o v et h es p e e do fm o d e l i n g ，a n da na l g o r i t h mf o rju d g e m e n tap o i n ti no ro u to f ap o l y h e d r o na n du po rd o w no faf a c em o d e lw a si m p r o v e dt oa v o i dt h ef a l s er e s u l t ．T h ea l g o r i t h mo fm o d e l i n gw a si m p l e m e n t e dw i t hC ．T h er e s u l t ss h o wt h a tt h ea l g o “t h mh a v ea t i m es a v i n go f3 0 ％一4 0 ％，c o m p a r e dw i t ho t h e rm i n i n gs o f t w a r e ，d u r i n gt h ec o n V e r s i o nf r o m t h eI } r e pm o d e lt ob l o c km o d e l ．T h em o d e l i n gr e s u l ti sa c c u r a t ea n de a s yf o rt h eq u e r ya n da n a l y z e ． I ti ss i g n i f i c a n tt oe n g i n e e r i n ga p p l i c a t i o no ft h eg e 0 1 0 9 i c a le n t i t ym o d e l ． K e yw o r d s o c t r e e ；b l o c km o d e l ；O B Bt r e e ；i n t e r s e c t i o nt e s t ；s e p a r a t i n ga x i st h e o r e m 三维地质模型建模技术是地学领域的一个热 点问题，国内外许多学者对此进行了大量的研 究阻引，目前，地质建模大都采用矢量模型与栅格模 型相结合的方式来准确、完整地表达地质体的空间 形态和内部属性．体元模型可以按体元的类型分为 四面体、六面体、棱柱体和多面体共4 种类型‘3 1 ，目 前应用较为广泛的是六面体，如矿业软件D a t a M i n e ，M i c r o M i n e ，S u r p a c 等都是应用六面体作为 体元进行实体建模，并称为块段模型．传统的块段 模型大都采用简单长方体来表达体元，没有采用结 收稿日期2 0 0 7 一0 8 一0 8 基金项目“十五”国家重点科技攻关项目 2 0 0 4 B A 6 1 5 A 0 4 ；国家自然科学基金项目 5 0 7 7 4 0 9 2 作者简介毕林 1 9 7 5 一 ，男，四川省通江县人，博士研究生，从事G l s 、数字矿山方面的研究． E 一啪i l B i “n 1 6 3 ．c o mT e l 1 3 5 4 9 6 8 2 7 4 5 万方数据 第4 期毕林等基于八叉树的复杂地质体块段模型建模技术5 3 3 构化的数据结构，方法比较简单，但具有如下缺点 1 这种一开始就对整个原型进行初始块段划分， 不可避免的增加了数据量；2 不能区别对待不同 性质的地质体，如岩体或岩层，因为对它们不存在 属性估值，所以对其内部就没有必要进行块段细 分；3 很难找到合适的空间索引方法达到简化操 作、降低计算量从而达到提高运行速度的目的．基 于以上原因笔者采用了八叉树结构来建立和表达 块段模型，并在此基础上提出了八叉树O B B 树进 行相交测试算法，改进了射线法判断点在多面体内 外及点在面状模型上下的算法，最终得以快速、准 确地建立复杂地质体块段模型． 1 基于八叉树的块段模型 1 ．1 块段模型的建立过程 地质块段模型是在表面模型的基础上经过边 界约束建立形成的，其具体步骤如下1 采用钻孔 数据 包括孔口数据、测斜数据、样品数据等 建立 钻孔模型；2 定义剖面，即根据钻孔建模生成的钻 孔数据划分钻孔边界，定义剖面步长和剖面宽度并 生成剖面；3 ．剖面编辑，即根据定义好的三维钻孔 剖面，圈定矿体、地层和断面，通过这种人机交互的 方式可以更准确、直观地显示出矿体剖面的形状； 4 将同属于一个矿体的剖面线相连形成表面模 型；5 对目标地质体进行块段划分，用地质体表面 模型 包括矿体、地层和断面等模型 对实体模型进 行边界约束，在边界处进一步细分，以逼近地质体 的空间形态；6 通过样品组合、样品分析、变异函 数计算、选择正确的估值方法、确定估值参数等一 系列过程对块段进行属性估值，地质体建模总体流 程如图1 所示． 竺曼／区荔吾页瓦疆函l 三丝竺．塾堕堡 一L ．，二二二工二．．L 堂璺堡鱼I 生成块段模型原型卜] I塞兰型堕 一一T 一l 一 样品分析1 ．1I 剖面编辑 ‘I 选择估值方法l‘ 变异函数计算l 1 ■一I 生成地质体实体 ；矗二匝麴亡丁_ 薹藿霍鍪／』三二二二广 品位估值 L 二，’‘’、 ．堕墨生竺 图1地质模型建立过程 F i g ．1M o d e l i n gp r o c e s s 1 ．2 基于八叉树块段模型的优点 八叉树的应用主要集中在计算机制图、计算机 视觉和图象处理等领域，近些年来许多学者将其引 入到地学中进行地质建模[ 4 。] ．在基于八叉树的块 段模型的建立过程中不需要对整个原型进行初始 栅格化，只是在三维目标的空间位置进行栅格化， 这样可以大大避免冗余数据的产生．传统的采用简 单长方体表达块段模型的方法在几何数据上主要 记录每一个块段的中心点坐标以及其细分级数，在 3 2 位系统中，如果坐标点采用双精度浮点型 8 个 字节 ，细分级数采用整型 4 个字节 ，则每个单元 块需要2 8 个字节的存储空间．常规八叉树编码 又 称明晰树编码 是八叉树最基本的编码方法，这种 方法明确存储所有需要的内容，没有任何数据压 缩，因而便于检索，但是存储空间的使用率不高，所 以这种编码方法一般较少运用．线性八叉树的方法 对八叉树的模型进行压缩存储，仅仅存储叶结点的 内容叶结点的位置 I ，J ，K 以及所在八叉树的级 数．在3 2 位系统中，如果结点位置和级数都用一个 整型来表达，则每个块体单元需1 5 个字节．实际 上，在研究的目标范围不是特别大的情况下，结点 位置的每一维只用2 个字节，而级数只用一个字节 来表达，例如在1 0 0o o Om 的范围内，则精确度还 可以达到1 0 0o o O ／2 1 6 1 ．5 3m ，则此时每个块体 只需7 个字节．由此可见采用线性八叉树存储块段 模型，可以极大的减少存储空间．由于八叉树的结 构性、层次性，很容易建立遍历算法 前序遍历、中 序遍历、后序遍历 ，而且时间杂度远低于非结构性 数据组织方式；另外，八叉树结构也很容易寻址结 点的邻居结点，便于空间分析． 基于八叉树的块段模型具有如下优点 1 能较为精确地表示矿体的边界特征； 2 便于空间检索与分析； 3 占用存储空间小，一般仅为三维栅格的 1 0 ％～3 0 ％[ 7 3 ； 4 计算体积较简便； 5 可以利用八叉树层次结构、递归细分等特 点提高建模算法运算速度． 1 ．3 表面模型到八叉树的转换 基于八叉树的块段模型建模技术的关键与难 点是表面模型向八叉树的转换，它直接关系到模型 的建立速度与结果的正确性．表面模型到八叉树的 转换也有不少学者进行过研究[ 8 曲] ，但这些方法或 者实现困难，或者没有提出提高运算速度的方法从 而性能较差，或者不适用于本文提到的块段模型的 建立．本文提出的表面模型到八叉树的转换流程如 图2 所示将所有地质体的边界模型的最小外包长 万方数据 5 3 4中国矿业大学学报第3 7 卷 方体作为八叉树的根结点；然后将根结点与边界模 型作相交测试，在边界相交处细分结点为8 个子结 点，继续将这些结点与边界作相交测试直到块段粒 度满足要求 能较好地表达地质体边界 ． 返回 t 边界模型装入 一个或多个 求包络所有模璎的最小外矫形包 作为原型形成八叉树的根结点 娶否约岁 型是否约束完毕 ≥二 、∥ 寓蠡嘲映多 鹂爹N 叫细化结点| _ J 州 分别取出8 个子结点重复以上操作 退出 图2 块段模型的建立流程 F i g ．2 F l o wc h a r to fm o d e l i n gp r o c e s s 在地质模型的建立过程中，根据表面模型所表 达的实体属性不同可分为矿体模型、岩体模型和断 层模型等；按模型网格是否封闭可分为封闭网格与 开放网格，封闭网格多表达封闭实体 多面体 ，开 放网格多表达层状实体 面状模型 ．矿体模型既存 在封闭网格 多见于金属矿 又存在开放网格 如煤 层 ，岩体模型同样既存在开放网格 如层状岩体 也存在封闭网格 如浸入体 ．封闭网格即为地质的 边界，而开放网格为层状地质体的顶板边界 可以 由顶板等高线形成 ．在对模型进行边界约束时，对 于与边界模型相交的块段进行细分直到达到细分 粒度要求；对于处于封闭网格内部的块段赋于与表 面模型相同的属性；对于处于开放网格下部的块段 赋于与表面模型相同的属性；如果模型表达的是矿 体，由于矿体的不均质性，需要对矿体模型内部进 行块段细分，以达到能精确表达内部属性、满足地 质统计学要求．所以还必须通过判断点在多面体内 外及点在面状模型上下的算法来确定块段的属性 及决定是否进一步细分．本文根据八叉树与O B B 树的特点有机地将它们结合起来进行相交测试，可 以大大提高块段模型的建模速度；同时根据交点为 “人点”与“出点”相继出现的特点改进了射线法判 断点在一般多面体内外算法，使转换得以快速、正 确进行． 2 o B B 树与八叉树相交测试算法 2 ．1o B B 树 有向有界箱 o r i e n t e db o u n d i n gb o x ，O B B 是 S ．G o t t s c h a l k [ 1 0 11 9 9 6 年在R A P I D 系统中首先使 用的，当时该系统声称是最快的碰撞检测系统，曾 一度作为评价碰撞检测算法的标准．O B B 树在寻 找最佳方向、确定在该方向上最小包围盒尺寸时计 算相对复杂．但是它的紧密性是最好的，可以成倍 地减少参与相交测试包围盒的数目和基本几何元 素的数目，在大多数情况下其总体性能要优于 A A B B 轴向包围盒 和包围球．与A A B B 相比， O B B 树的最大特点是其方向的任意性，这使得它 可以根据被包裹对象的形状特点尽可能紧密地包 裹对象．构建O B B 树一般采用下行式方法[ 10 | ，即 从整个数据集开始不断递归细分直到所有的叶子 结点不需再细分．O B B 树的细分规则是用一垂直 最长轴的平面分割数据，分割点为数据中心点 如 图3 ．因为分割点始终是中心‘点，所以0 B B 树总 是平衡树． 图3 构造O B B 树 F i g ．3 B u i Ho f0 B Bt r e e 2 ．2分离轴理论 三维空间中如果存在一个向量 轴 ，使得被检 测的几何体在该轴上的投影不相交，那么这根轴就 是一根分离轴，如图4 所示，在二维空间中说明这 一点，分离有向有界箱A 和B 的平面 在二维中为 直线 如图中的点线．如果找不到分离轴，那么被检 测的几何体相交．如果被检测的几何体是一些简单 的几何体，那么它们之间潜在的分离轴是可以事先 计算出来的．在测试的时候只需测试这些潜在的分 离轴，而不用漫无边际的根据定义去找分离轴．三 维空间中任意方向的长方体与长方体之间的潜在 分离轴最多有一1 5 根．它们是每个长方体的3 根方 向轴，有3 2 6 根潜在分离轴，一个长方体的一 条边矢量与另一个长方体的边矢量的叉乘，有3 3 9 根潜在分离轴．这样只要从这1 5 根潜在的分 离轴中检测出一根就可以判定2 个0 B B 分离，因 此检测效率可以大大提高． 万方数据 第4 期毕林等基于八叉树的复杂地质体块段模型建模技术 5 3 5 图4o B B 轴分离不惹 F i g ．4 2 Ds c h e m a t i cf o r0 B Bi n t e r s e c t i o nd e t e c t l o n 2 ．3 相交测试 O B B 树与八叉树一个结点相交测试流程如图 5 所示．首先对表面模型建立O B B 树，再将即将与 模型进行相交测试的八叉树结点形成一个0 B B ， 然后将O B B 树的根结点与八叉树o B B 根据轴分 离理论开始进行分离测试，如果一个结点与八叉树 0 B B 不可分离则进一步判断该结点是否是叶子结 点，如果不是叶子则取出其子结点重复以上操作， 如是叶子结点则取出该结点中的三角形面片与八 叉树o B B 进行分离测试，如果存在不能分离的三 角形则说明当前八叉树0 B B 对应的八叉树结点与 表面模型相交，需要对其进行细分为8 个子结点． 0 B B 与三角形的分离测试也是利用轴分离理论进 行的，不过此时潜在的分离轴只有1 3 根．它们是三 角形的法矢量及o B B 的3 根方向轴，1 4 5 根； 0 B B 的一条边矢量与三角形的一条边的叉乘，有3 3 9 根潜在分离轴． 将八叉树结点生成O B B 将表面模型母成0 B B 村，从根结点 开始与八叉树0 B B 进行分离测试 l 塑窒望些l 图5O B B 树与八叉树结点相交测试流程 F i g ．5 F l o wc h a f to f i n t e r s e c t i o nt e s t b e t w e e no B Bt r e ea n dO c t r e e 3 点在表面内外 上下 判断算法 3 ．1 点在多面体内部判断 点在多面体内的检测常采用射线法．其方法是 用原点位于检测点P 且方向为d 一 1 ，o ，o 的射线 与多面体的面相交，计算交点的数量，假设该射线 仅与多面体相交于面的内点，交点数量奇偶性说明 了点P 位于里面还是位于外面．如果交点个数为 奇，则位于里面，否则位于外面．然而，当射线与多 面体不是相交于面的内点，而是相交于顶点或边的 内点时，由于在求交点的过程中共享该顶点或边的 面是分别处理的，每一个面都会记录一次交点，致 使结果可能不准确 图6 ．一种处理的方法是利用 随机化方法[ 1 “，其思想是产生随机方向，直到找一 条仅与面相交于内点的射线．虽然期望可以找到这 样一条射线，但不清楚出现多少次迭代才会成功． 还有一种方法是P a e t h “用球面多边形来进行点在 多面体内的检测”中的算法，但这种方法要求计算 实体角度，而且在运算中使用了反三角函数调用， 因此性能很差．根据交点为“入点”与“出点”相继出 现的特点改进了射线法对点在一般多面体内部判 断算法，其步骤如下 步骤1 将多面体面片法向方向一致化，使所 有面片的法向方向都指向多面体外面； 步骤2 找到一面片，使其中点与待判断点的 形成的直线与该面片相交，交点为该中点； 步骤3 求射线与多面体的所有交点，并记下 交点与待判断点的距离及根据射线与面片法线方 向的关系将交点记为“入点”与“出点”； 步骤4 根据距离对交点进行排序，同时要求 “入点”与“出点”交替出现，如果前后两个交点同为 “人点”或同为“出点”，则第2 个交点不记入，这样 就可以避免图6 b 的情况． 步骤5 根据奇偶性判定点位于多面体的里 面还是外面．如果最终记录的交点个数为奇，则位 于里面，否则位于外面． 肓育 必P 避I a 奇偶性没有变化 b 奇偶性发生变化 图6 相交于共享边的内点 F i g ．6 T w oc o n f i g u r a t i o n sf o rw h e nt h et e 8 t r a yi n t e r s e c t sas h a r e de d g ea ta ni n t e r i o re d g ep o i n t 这种判断方法，关键是使多面体面片法向方向 一致化．不难理解，对于一个所有面片法向方向的 封闭多面体其“最左边”的面片法向量是所有面片 法向量中与X 轴最一致 两向量的点乘值最大 ， 并且指向左边，如图7 左图所示．所以一致化的主 要思想是找到“最左边”的面片，如果其法向方向 万方数据 5 3 6中国矿业大学学报第3 7 卷 不是指向左边，则将该面片反向，即改变顶点顺序I 然后以该面片为种子，对其它相连的面片进行处 理，直到所有面片处理完毕．其中找到“最左边”面 片的方法是首先是找到最左边的点，然后从共享 该顶点的所有面片中找到法向方向最与X 轴一致 的面片，即为“最左边”面片． 在求射线与多面体的交点时，同样利用O B B 树．首先用射线与0 B B 结点进行分离测试 只有3 条潜在的分离轴 ，对于不能分离的O B B 叶子结点 才取出其面片与射线求交．这样可以大大提高求交 速度． 脏一 最上边顶点 厂 八枞 L ■片 图7“最左边”与“最上边”面片示意 F i g ．7“L e f t m o s t ”a n d “u p m o s t ’’p o l y g o n 3 ．2 点在层状模型上下判断 对于不封闭的层状模型如果也能够其面片一 致化，使其所有面片的法向方向层状模型的“上 面”，则问题就等同于点在多面体内部判断了．关键 是要找到正确的“种子”，即“最上边”面片，其方法 是首先是找到最上边的顶点，然后从共享该顶点 的所有面片中找到法向方向与y 轴最一致的面 片，即为“最上边”面片，如图7 右图所示． 4 实验及结论 通过V C 开发工具实现了该建立块段模 型的算法，运行环境为W i n d o w s2 0 0 0 操作系统， C P U 为I n t e lP e n t i u m 4 ，3 0 0G H z ，内存5 1 2M ．图 8 a 所示的岩层块段模型为用3 层表面模型约束， 每个表面模型有2 73 6 1 个三角面片，原型长宽高 分别为15 9 8 ．2 8 5 ，10 0 6 ．2 9 6 ，9 2 3 ．9 6 8m ，八叉树 深度为8 ，则边界块段的长宽高分别为1 2 ．4 8 7 ， 7 ．8 6 1 ，7 ．2 1 9m ，建立该块段模型所耗时5 1 ．2 7s ． 图8 b 所示的矿体块段模型，表面模型有1 73 3 2 个 三角面片，原型长宽高分别为7 1 1 ．1 0 2 ，4 5 3 ．0 0 0 ， 4 6 4 ．1 0 1m ，八叉树深度为9 ，则每个块段的长宽高 分别为2 ．7 7 8 ，1 ．7 7 0 ，1 ．8 1 3m ，建立该块段模型 所耗时2 4 1 ．9 5 3s ．表1 为本算法与M i c r o M i n e 用 三角形个数分别为2 73 6 1 ，2 0 98 1 8 ，2 7 95 3 1 个的 D T M 模型进行地表约束形成块段模型所耗用的 时间表，以及采用八叉树结构所占用的内存大小． 表1 块段模型建模实验数据 T a b l e1 M o d e l i n gt 鳟to f b l o c km o d e l a 层状地质体 图8 块段模型 F i g ．8 B l o c km o d e l 通过以上实验可以得到如下结论 1 由于采用了八叉树与O B B 树相交测试算 法，本文提出的块段模型建立方法在速度上比国际 矿业软件M i c r o M i n e 要快3 0 ％～4 0 ％； 2 基于八叉树的块段模型的建立过程中不需 要对整个原型进行初始栅格化，减少了不必要的块 段细分，有效地降低了块段模型的数据量； b 块状地质体 3 八叉树的结构性、层次性，遍历时间杂度 低，八叉树结构也很容易寻址结点的邻居结点，便 于空间分析与空间检索，对于地质模型以后的工程 应用具有重要意义； 4 对于目标范围特别大或者要求的精度特别 高时，块段模型的数据量将会急剧增加，目前通用 的P C 机内存容量很难满足要求，应该考虑用线性 万方数据 第4 期毕林等基于八叉树的复杂地质体块段模型建模技术5 3 7 八叉树编码与B 树相结合的方法实时动态地访问 外存模型数据，对此有待于进一步研究． 参考文献 [ 1 ] 武强，关文革，贾丽萍，等．面向矿区复杂地质体 的四面体生成算法[ J ] ．中国矿业大学学报，2 0 0 5 ，3 4 5 6 1 7 6 2 0 ． W UQ i a n g ，G U A NW e n - g e ，J l AL i - p i n g ，e ta 1 ．A n e wg e n e r a t i o nt e t r a h e d r o nm e s ht e c h n i q u eo fc o m p I e xm i n i n gg e o l o g i c a lb o d i e s [ J ] ．J o u r n a lo fC h i n a U n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ，2 0 0 5 ，3 4 5 6 1 7 6 2 0 ． [ 2 ] 龚健雅，夏宗国．矢量与栅格集成的三维数据模型 口] ．武汉测绘科技大学学报，1 9 9 7 ，2 2 1 7 1 5 ． G o N GJ i a n - y a ，X I AZ o n g g u o ．A ni n t e g r a t e dd a t a m o d e li nt h r e ed i m e n s i o n a lG 1 S [ J ] ． J o u r n a lo fW u h a nT e c h n i c a lU n i v e r s i t yo fS u r v e y i n ga n dM a p p i n g ， 1 9 9 7 ，2 2 1 7 1 5 ． [ 3 ]吴江斌，朱合华．基于D e l a u n a y 构网的地层3 D T E N 模型及建模[ J ] ．岩石力学与工程学报，2 0 0 5 ， 2 4 2 4 4 5 8 1 4 5 8 7 ． W UJ i a n g _ b i n ，Z H UH e h u a ．3 DT E Nm o d e Io f s t r a t aa n di t sr e a “z a t i o nb a s e do nd e l a u n a yt r i a n g u l a t i o n [ J ] ．c h i n e s eJ o u r n a lo fR o c kM e c h a n i c sa n dE n g i n e e r i n g ，2 0 0 5 ，2 4 2 4 4 5 8 1 4 5 8 7 ． [ 4 ] 吴立新，史文中．3 DG I S 与3 DG M s 中的空间构模 技术[ J ] ．地理与地理信息科学．2 0 0 3 ，1 9 1 5 1 1 ． W U1 ．i x i n ，S H IW e n - z h o n g ．S p a t i a lm o d e l i n gt e c h - n o l o g i e sf o r3 DG l sa n d3 DG M s [ J ] ．G e o g r a p h ya n d G e o - I n f o r m a t i o nS c i e n c e 。2 0 0 3 ，1 9 1 5 1 1 ． [ 5 ] 王李管，何昌盛，贾明涛．三维地质体实体建模技术 及其在工程中的应用[ J ] ．金属矿山，2 0 0 6 2 5 8 6 2 ． W A N GL i - g u a n ，H EC h a n g s h e n g ，J 1 AM i n g _ t a o ．3 D g e o l o g i c a ，s o “dm o d e “n gt e c h n o l o g ya n di t sa p p l i c a t i o ni ne n g i n e e “n g [ J ] ．M e t a lM i n e ，2 0 0 6 2 5 8 6 2 ． [ 6 ] 杜培军，郭达志，田艳凤．顾及矿山特性的三维G l S 数据结构与可视化[ J ] ．中国矿业大学学报，2 0 0 1 ，3 0 3 2 3 8 2 4 3 ． D UP e i j u n ，G U oD a z h i ，T I A NY a n r f e n g ．3 DG 1 S d a t as t r u c t u r ea n dv i s u a l i z a t i o nb a s e do nm i n ep r o p e r t i e s [ J ] ．J o u r n a lo fC h i n au n i v e r s i t yo fM i n i n g ＆ T e c h n o l o g y ，2 0 0 1 ，3 0 3 2 3 8 2 4 3 ． [ 7 ] 韩国建，郭达志，金学林．矿体信息的八叉树存储和 检索技术[ J ] ．测绘学报，1 9 9 2 ，2 1 1 1 3 1 7 ． H A NG u 0 - j i a n ，G U oD a z h i ，J I NX u e _ l i n ．S t o r a g e a n di n d e x i n go fo r e b o d yi n f o m a t i o nu s i n go c t r e e s [ J ] ． A c t a G e o d a e t i c ae tc a r I o g r a p h i c as i n i c a ，1 9 9 2 ， 2 1 1 1 3 1 7 ． [ 8 ]N o B o R I oH ，F u K u D As ，A R I M O T 0s ．c o n v e r s i o na l g o r i t h mf r o mt h eb o u n d a r yr e p r e s e n t a t i o nt o t h eo c t r e ea n di t sc o m p l e x i t y [ J ] ．T r a n s a c t i o no ft h e I n f o r m a t i o nP r o c e s s i n gS o c i e t yo fJ a p a n ，19 8 7 ，2 8 1 0 1 0 0 3 1 0 1 1 ． [ 9 ]T A M M l N E NM ，S A M E TH ．E f f i c i e n to c t r e ec o n v e r s i o n b yc o n n e c t i v i t yl a b e l i n g [ J ] ．C o m p u t e r G r a p h i c s ，1 9 8 4 ，1 8 3 4 3 5 1 ． [ 1 0 ]G o T T s c H A L KS ，L I NMC ，M A N 0 c H AD ，e t a 1 ．0 B B t r e e ah i e r a r c h i c a ls t r u c t u r ef o rr a p i di n t e r - f e r e n c ed e t e c t i o n [ C ] ／／P m c e e d i n g so fA C MA n n u a l C o n f e r e n c eo nC o m p u t e rG r a p h i c s ． L o u i s i a n a [ s ． n ．] ．2 0 0 0 1 7 1 1 8 0 ． [ 11 ] P H l I 。I PJS ．D A V I DHE ．G e o m e t r i ct o o l sf o r c o m p u t e rG r a p h i c s [ M ] ．B e 瑶i n g P u b l i s h i n gH o u s e o fE l e c t r o n i c sl n d u s t r y ，2 0 0 4 7 1 2 7 1 3 ． 责任编辑姚志昌 万方数据