（计算机应用技术专业论文）地质建模中若干算法的研究与应用.pdf

浙江大学顾十学位论文摘要 摘要 经过几千万年的地质演化，各种地质结构变得错综复杂。利用计算机辅助三 维地质信息的采集、存储、管理以及建立三维地质模型并进行相应的空间分析一 直是地质研究、地质勘探、矿业工程和水利工程科技工作者的梦想。 三维地质模型是指使用适当的数据结构在计算机中建立一个数字地质模型， 该模型能反映地质结构以及各个结构之间的关系。这是一种崭新的研究手段和研 究方法，有利于合理、有效地对地形地貌、矿产资源等进行各种预测与评价，节 约资金，减少实际应用中的盲目性，降低风险，对生产及环境分析发挥指导和决 策作用，具有重大的经济与社会效益。 地质数据一方面数据量庞大，另一方面，有时又很稀疏，而且包含了不规则 以及不确定性，给地质建模带来了很大的困难。 论文的主要结构如下： 第一章介绍了地质建模的意义和应用需求，并大致描述了我们的研究工作。 第二章描述了地质建模中点云到网格的转换，我们介绍了几种不同的点云三 角化方法，并进行了不同用途的比较。还介绍了一种点云聚类方法，使得三角化 更合理，更有效，避免了在断层处产生无意义的三角片。 第三章介绍了地质建模中三角网格的一些编辑算法，包括网格简化、网格求 交和裁除以及b 一样条曲面延拓三个算法。这些操作对于节约计算资源、提高处理 效率有很大帮助。 第四章对全文进行了总结，并对未来的工作提出了展望。 我们结合本文开发了一个三维地质建模算法的软件包，主要应用于稀疏地质 数据的分析、整合，对于不规则、有断层的数据也可以进行分割。但是对于大规 模数据的处理能力还有待进一步研究。 关键词地质数据，三角化，重建，网格 浙江大学硕士学位论文 a b s t r a c t a f t e rt h o u s a n d so f y e a r se v o l u t i o n ，m o s to f t h eg e o l o g i c a ls t r u c t u r e sh a v eb e c o m e v e r yc o m p l i c a t e d w i t ht h eh e l po fc o m p u t e r s ，t h ec o l l e c t i o n ，s t o r a g e ，m a n a g e m e n ta n d e s t a b l i s h m e n to f t h e3 dg e o l o g i c a lm o d e l sa n dt h er e l a t i v es p a t i a la n a l y s i so nt h e ma r e u r g e n tr e q u i r e m e n t si nt h ef i e l d so f g e o l o g i c a lr e s e a r c h ，g e o l o g i c a le x p l o r a t i o n ，m i n i n g e n g i n e e r i n ga n dw a t e rc o n s e r v a n c y t h e3 dg e o l o g i c a lm o d e l i n gi st oc o n s t r u c ta3 dd i g i t a lg e o l o g i c a lm o d e lw i t ht h e a p p r o p r i a t ed a t as t r u c t u r e s t h e3 dg e o l o g i c a lm o d e ls h o u l dr e f l e c tt h eu n d e r l y i n g g e o l o g i c a ls t r u c t u r e sa n dt h er e l a t i o n sa m o n gt h e m i ti sah e l p f u lr e s e a r c hm e t h o df o r t h ee f f i c i e n tf o r e c a s ta n de s t i m a t i o no ft h et e r r a i n sa n dp h y s i o g n o m i e s ，m i n er e s o u r c e i t i sa l s oe f f i c i e n tw a yt os a v et h ee x p l o r a t i o nc o s t ，r e d u c et h ee x p l o r a t i o nv e n t u r e f u r t h e r m o r ei tc a ng u i d et h em i n ea n do i lp r o d u c t i o n sa n de n v i r o n m e n ta n a l y s i s t h u s i tc a r lb r i n gh u g ee c o n o n f i c a la n ds o c i a lb e n e f i t s t h es i z eo fg e o l o g i c a ld a t ai sa l w a y sv e r yl a r g e o nt h eo t h e rs i d e ，t h ed a t ai s s o m e t i m e ss p a r s e ，i r r e g u l a ra n du n c e r t a i nw h i c ha r et h em a i no b s t a c l e si nt h e3 d g e o l o g i c a lm o d e l i n g o u rr e s e a r c ht r i e st os o l v es o m ea s p e c t so fa b o v ed i f f i c u l t i e si n t h e3 dg e o l o g i c a lm o d e l i n g t h et h e s i si so r g a n i z e da sf o l l o w s ： c h a p t e r 1i n t r o d u c e st h e3 dg e o l o g i c a lm o d e l i n ga n dt h e i ra p p l i c a t i o n s t h e o u t l i n e so fo u rw o r ka r ea l s og i v e n c h a p t e r2d e s c r i b e sh o wt oc o n s t r u c tt h et r i a n g u l a rm e s hf r o mt h ep o i n tc l o u d si n t h e3 dg e o l o g i c a l m o d e l i n g 。s e v e r a lt r i a n g u l a t i o nm e t h o d s a r ep r o p o s e df o r t h e d i f f e r e n tp u r p o s e s ，ap o i n tc l o u d sc l u s t e rm e t h o di sa l s og i v e n ，w h i c hm a k e st h e t r i a n g u l a t i o nm o r er e a s o n a b l ea n de f f i c i e n t ，a n dc a na v o i dt h em e a n i n g l e s st r i a n g l e si n f a u l t s c h a p t e r3i n t r o d u c e ss o m eg e o m e t r i co p e r a t i o n so nt h et r i a n g u l a rm e s h e si nt h e 3 dg e o l o g i c a lm o d e l i n g ，w h i c hi n c l u d e sm e s hs i m p l i f i c a t i o n ，m e s h e si n t e r s e c t i o na n d s p l i t ，b s p l i n e s u r f a c ee x t e n s i o n t h e s eo p e r a t i o n sa r eh e l p f u lt os a y ec o m p u t i n g r e s o u r c ea n di m p r o v et h ep e r f o r m a n c e c h a p t e r4d r a w st h ec o n c l u s i o na n dg i v e ss o m ef u t u r ew o r k s t h ed e v e l o p e ds o f t w a r ei nt h i s p a p e r c a nb ee m p l o y e di nt h ea n a l y s i sa n d i n t e g r a t i o no ft h e3 ds p a r s eg e o l o g i c a ld a t a i tc a na l s os p l i tt h ei r r e g u l a rd a t aw i t h f a u l t s t h ef u r t h e rr e s e a r c hi sn e c e s s a r yt op r o c e s st h el a r g es i z ed a t a 浙江大学硕士学位论文 k e y w o r d sg e o l o g i c a ld a t a ，t r i a n g u l a t i o n ，r e c o n s t r u c t i o n ，m e s h 浙江大学硕上学位论文图目录 图目录 图1 1m a l l e t 的d s i 结果2 图1 _ 2 我们实现的d s i 结果2 图1 3m e s h 简化作用在地质数据上5 图1 4m e s h 求交及裁除6 图1 5b s p l i n e 曲面拟合与延拓7 图1 - 6 空间散乱点的边界7 图l - 7m e s h 分割8 图1 8 点云聚类9 图1 9 平面d e l a u n a y 三角化在空间散乱点上面的结果。9 图2 1 使用p c a 方法计算1 3 图2 - 2 平面散乱点集的包围盒1 3 图2 3 角度约束下的边界合并。1 4 图2 - 4 内点与边界点1 5 图2 5 可以直接投影点云的边界生成。1 6 图2 6 不可直接投影点云的边界生成1 6 图2 7v o r o n o i 图和d e l a u n a y 图关系1 7 图2 8 分而自治法。18 图2 - 9 增量式插点法。1 8 图2 1 0 扫描式方法1 8 图2 1 1 线段中点剖分1 9 图2 1 2 除去比较差的三角形1 9 图2 1 3 数据结构对比。2 0 图2 1 4 平面d e l a u n a y 三角化在空间散乱点上的结果2 0 图2 15 将边界线参数化到一个平面正方形上2 l 图2 1 6 参数平面三角化实验结果2 2 图2 1 7 两种三角化方法运用于地质数据的比较2 2 图2 18 参数化过程2 4 图2 1 9 重采样过程2 4 图2 2 0 重采样实例2 5 图2 2 1b 样条拟合结果2 6 图2 2 2 空间分割2 7 图2 2 3 增加非表面点2 7 图2 2 4r b f 重建2 9 图2 2 5 点云聚类结果3 0 图3 1 点对收缩3 3 图3 - 2 网格简化实例3 5 i i i 浙江大学硕士学位论文图目录 图3 3 地质数据网格简化实例3 6 图3 4b 样条曲线的延拓3 8 图3 5b 样条曲面延拓3 8 图3 - 6 地质数据延拓后求交3 9 i v 浙江大学硕士学位论文第l 章绪论 第1 章绪论 地质建模，就是对于已知的地形、地貌和地质情况在计算机中进行抽象、重 新整合以及建立模型以便观察、研究和分析的过程。主要应用于地质研究和资源 勘探等方面，对于了解地震、山体滑坡和泥石流等灾害也有一定的帮助。 通常，地质数据是散乱的、无规则的，并且具有一定的不确定性。因此，就 需要一些高效的、鲁棒的算法来对这些数据进行操作。 在本章中，我们首先简要说明地质建模的研究现状，然后介绍一些常见的概 念和地质建模的需求及应用，也就是我们工作的部分内容，再介绍一下地质建摸 的数据来源，最后给出本文的主要内容和组织结构。 1 1 研究现状 下面分国外、国内两部分对当前三维地质建模领域内的研究和发展现状进行 分析。 国外三维地质建模最典型的代表是g o c a d 。g o c a d 研究计划是1 9 8 8 年法 国n a n c y 大学的j l m a l l e t 教授推出的，目的是要开发一种新的地质目标计算机 辅助设计方法，以适应地质、地球物理和油藏工程的需要。该计划得到了世界上 4 3 个大公司和2 8 所大学的支持，其研究成果已经被国外的许多地球物理公司和 石油公司采用。g o c a d 的核心是离散光滑插值( d s l ) 方法。利用d s i 方法插值生 成断层面，然后利用d e l a u n a y 三角化生成连续的地层网格，根据己知的断距和 o n t s u r f , v e c l i n k 约束条件对地层面进行断裂和插值，生成断裂的地层面。根据 生成的断层面、地层面生成边界面表示的地质体，并在此基础上生成属性模型。 在地质建模问题中，有些时候给定的型值点很少，很难用b 样条曲面或b ( z i e r 曲面等自由曲面来拟合。而d s i 方法则可以从函数曲面的一阶和二阶偏导出发， 建立相邻的点与点之间的联系，从而来插值一个曲面。从本质上来说，这也是一 个通过令偏导等于零，然后解方程的方法。通过d s i 插值，我们可以得到一系列 给定网格点的函数值。这些函数值分为两类：一类为给定型值点的函数值；另一 类为通过d s i 算法得到的函数值。图1 1 为m a l l e t 的部分实验结果【l 】，图1 2 为 我们实现的d s i 部分结果。 浙江大学硕士学位论文第1 章绪论 图1 - 1m a l l e t 的d s i 结果。 图1 2 我们实现的d s l 结果。 近年来，国内的一些高校和科研院所也在陆续地展开了三维地质建模技术的 研究，但由于一些关键技术未能掌握，也都没有像国外大公司那样成型的产品。 国内有些学者采用层状地质体来模拟地下结构，其构建方法是先构建断层的三角 网格，然后生成地层三角网格和层状地质体。采用这种方法在模拟出断层面之后， 对于同沉积断层，采用两边分别插值生成地层面，而对于逆断层存在而造成的多 值面( m u l t i v a l u es u r f a c e ) 并不能给出满意的解决方案。 也有学者中采用三维规则网格法，即将研究空间剖分为多个规则的网格，然 2 浙江大学硕士学位论文第l 章绪论 后用相应的网格描述地质体。该方法是二维规则网格法在三维空间中的延伸，针 对被规则剖分的空间，可以建立简单的数据结构和运用简单的算法。三维规则网 格法的特点是简单，不足之处是巨大的数据集和计算工作量。 中国地质大学的张蔚等人提出了一种新的三维地质建模方法：似三棱柱法 ( s t p 法) f 2 ，用它作为基本体元来实现三维地质数据的可视化。该方法首先将 原始数据经过预处理，形成各个地层上下对应的三角网格数据，然后连接相邻地 层上下对应的网格形成似三棱柱。 北京大学的屈红刚等人针对部分三维地质表面建模方法依赖于“平行剖面”、 “平剖面”的不足，提出“基于交叉折剖面的三维地质表面建模”的新思路，并 从理论、方法和原型系统开发及应用试验三个方面进行了深入研刭3 1 。 经过漫长的地质演变，三维地质模型具有以下一些特点：地质结构千奇百怪， 非常复杂；不连续、离散、高度非线性；采样数据不均匀、不完整；存在断层； 建模结果难以直接验证。 根据以上对国内外研究状况的分析，我们发现当前国内外的三维地质建模系 统在解决复杂地质结构建模时存在一些问题： 1 缺乏一套全自动( 必要时可以由用户交互地干预，基于用户的地质知识库 建模) 的建模理论和相关产品，相关的文献或产品都集中在由用户交互式地建立 模型，所生成的三维地质模型的精度完全由用户根据已知数据凭借经验交互编辑 所决定。建立一个三维地质模型需要较长的时间，在己知数据更改时不能很快地 生成新的三维地质模型，更新速度馒。 2 在生成断层模型时不能很好的处理断层相交情况，一般需要交互地编辑相 交部分，才能生成在相交部分完全吻合的断层网格。在处理的过程中还要与真实 情况断层断裂的次序相一致，所需要的交互工作就更加繁重。 综上所述，建立一套能够全自动的三维地质建模理论是三维地质建模领域一 个研究的热点，国内外的研究机构都在结合自身的实际情况进行研究。这种建模 理论的研究是一个跨学科的综合性研究，研究周期长、难度大，具有很高的理论 价值和实际的应用前景，值得作进一步的研究。 1 2 常见概念 点云( p o i n t sc l o u d ) ：也称为散乱点( s c a t t e r e dp o i n t s ) ，数量从几十到几千的 3 浙江大学硕士学位论文第1 章绪论 点聚集在一个空问内，既无规则、也无序。 网格( m e s h ) ：通过对点云进行三角化操作，将点云中的每个点都与其周围的 点进行适当地连接，从而形成的一种结构。 断层面( f a u l ts u r f a c e ) ：断层面是构成断层的破裂面，即断层两边发生相对 位移的面。它是一个三维空间的曲面，可以是由地震解释的断层多边形、断层段 或散乱点数据经过网格化( 插值) 后形成的三维曲面。 层面( h o r i z o n ) ：层面和断层面一样也是三维空间的曲面。它可以是由地震解 释的层位数据、井分层数据或散乱点数据经过网格化( 插值) 后形成的三维曲面。 断块( f a u l tb l o c k ) ：断块是指岩石圈中为断裂所围限的断裂块体，是纵横两 类断裂相结合所划出的地质构造单元 交线( i n t e r s e c tl i n e ) ：交线是一个三维空间的线，它是由两个曲面相交形成 的，包括断层交线和层面交线。 构造模型( s t r u c t u r em o d e l ) ：对断层、层位网格化，处理好断层与断层、层 位与层位、断层与层位的交切关系后形成构造模型。 储层网格( r e s e r v o i rg r i d ) ：储层网格有多种：规则的地震数据网格( 规则 六面体) 、不规则的地层网格( 不规则六面体) 、四面体网格。 1 3 与地质建模相关的一些算法与技术 m e s h 简化 在大规模地质数据进行操作或显示时，常常希望得到一个数据的简化版本， 并且该简化数据保留了原始数据的一些基本特征，使得操作或显示即能满足实 时，又不失真。这种对数据进行简化的算法，我们简称为模型简化。 s c h r o e d e r 等人提出了一种点消除算法【4 l 。他们的方法迭代地消除网格中的顶 点以及与该顶点相邻的三角片，并对由此而出现的空洞进行重新三角化。这个方 法必须对模型的拓扑结构进行维护，因此比较适合于医学成像等对于拓扑结构有 较高要求的领域。但是，仅仅对于绘制来说，拓扑结构并不重要。 本文介绍的即为已实现的针对m e s h 模型的一种简化算法【5 】。该算法接受一个 原始m e s h 模型，对其简化，得到一个保留原始m e s h 特征的简化m e s h 。图1 3 即为我们实现的网格简化实验结果。 4 浙江大学硕上学位论文第1 章绪论 图i - 3m e s h 简化作用在地质数据上。 点云m e s h 求交以及裁除 在地质建模以及各种地下工程设计等三维表达、分析领域，大规模复杂三角 形网格的求交计算是三维建模的一个关键算法。对两块m e s h 进行求交，在交线 处对各块m e s h 进行分割，得到新的求交后的m e s h 。按照交线以及边界线对新 m e s h 进行区域划分，并可选择相应区域，把它从新m e s h 中进行删除【6 】川。 中南大学的尹长林等人根据三角网格中相邻三角形之间的拓扑邻接关系以 及交线的连续性，提出了一种基于拓扑搜索的三角网格求交算法喁】。该算法引入 空间辅助网格对原始三角网格进行筛选，并在候选三角形集合中依次追踪、计算 构成交线的交线段，在获得每个交线段的同时完成了线段之间的连接。 北京信息工程学院的许晓革等人提出的离散化跟踪求交算法【9 l ，是用离散方 法求出交线上的某一个交点，然后根据两相交小三角面片的空间几何关系确定该 交线段的方向。依次用跟踪法求出整条交线，这样就有效她避免了用离散法求出 的交线不连贯问题。 图1 - 4 是我们实现的两片网格求交及裁除结果。 浙江大学硕士学位论文 第1 章绪论 图1 4m e s h 求交及裁除。a ) 两片m e s h 相交。b ) 求得交线。c ) 选定裁除m e s h 区域。d ) 裁除后的结果。 散乱点的b - s p l i n e 曲面拟合与延拓 给定空间的散乱点，根据最小二乘原理拟合一个b 样条曲面。b 样条曲面是 一类张量积自由曲面，从b 样条曲面的公式可以看到有以下几个关键的因素：节 点向量的确定、控制顶点的产生、控制顶点个数的选择以及与之相关的给定的数 据点( 用来拟合的点) 的参数化。控制顶点个数的选择与误差的控制以及延拓的 效果都有关。在其它条件不变的情况下，控制顶点个数越多，拟合的误差越小， 但是，另一方面，控制顶点越多，延拓的出来的曲面的扭曲也越大。 清华大学的胡事民等人提出了一个基于u n e l a m p i n g 算法的b 一样条曲线曲面 延拓算法【i o 】。该方法通过外插值控制顶点来使得b 样条曲线经过某些预先给定的 点，这些点可以人工指定，也可以用其它方法计算得到。同时，该方法也可以延 拓b 样条曲面，使其经过预先给定的曲线。 我们实现的方法中，并没有增加控制顶点，而是对d eb o o r - c o x 公式进行修 改，使得它可以计算原来定义域以外的点。图1 5 就是我们实现的结果。 6 浙江大学硕士学位论文第1 章绪论 图1 - 5b s p l i n e 曲面拟合与延拓。a ) 为b 一样条拟合的结果，b ) 桔黄色m e s h 为拟合结果， 绿色为延拓的结果。 空间散乱点的边界生成 给定散乱点，从其中找出一系列点，按顺序连接构成一条封闭的空间曲线， 使得其它散乱点在此空间曲线的“内部”，则这条空间曲线称为空间散乱点的边 界线。目前已有的算法主要是各种凸包算法。凸包算法的缺点在于，对于比较稠 密的散乱点，由凸包定义的边界线可能不紧凑，造成边界点的遗漏。我们提出了 一种新的算法生成空间散乱点的边界，辅之以适当的交互手段，可以得到令人满 意的结果。 山东大学的潘荣江等人提出一种提取点云封闭边界线的方法【1 ”。该方法首先 对点云空间进行均匀划分，然后把位于一个点的邻域内的所有点投影到拟合平面 上，并判断是该点是否为边界点。最后将所有边界点连接形成边界线。 我们对上述算法进行了一点改进，就是不对空间点云进行均匀划分的预处 理。如果所有找到的边界点可以直接投影在一个拟舍平面上时，则可以直接生成 边界线。否则，再对所有的边界点进行空间划分，最后生成边界线，这样可以节 约计算量。图1 - 6 即为我们实现的散乱点边界生成算法的实验结果。 图l - 6 空间散乱点的边界。对于角度约束的选择，可以使得边界线紧凑而又不毛糙。 7 浙江大学硕上学位论文第l 章绪论 交互式m e s h 分割 在输入的三角网格上指定撕裂线，通过拓扑连接关系，在需要进行撕裂的顶 点处，构建新的顶点，并重新连接三角网格。最后输出新生成的网格。图1 - 7 即 为我们实现的算法结果。 图1 - 7 m e s h 分割。图中黄线为指定的撕裂线。a ) 原m e s h ，b ) 按黄线分割结果，c ) 原m e s h ， d ) 按黄线分割结果。 点云聚类 根据散乱点的距离关系，聚类算法将输入点云分解为点云子块，便于进一步 的三角化等操作。 鞍山科技大学的孙红岩等人采用k m e a n s 聚类分析方法对三维点云模型进行 分割。论文指出，对于分布呈现类内团聚状的三维点云模型，k 均值聚类分割可 以得到较好的结果【1 2 】。 我们实现了一种采用f l o o d i n g 思想的算法，图1 8 即是我们的实验结果。 8 浙江大学硕士学位论文第l 章绪论 i )b ， 图1 - 8 点云聚类。通过选择不同参数。可以得到图a ) 和图b ) 两种不同结果。 基于边界约束的空间散乱点三角化 基于边界约束的空间散乱点三角化算法是计算几何中有待解决的问题。类似 于前面边界提取算法，我们将问题进行简化：即将散乱点三角化问题通过最小二 乘投影，转化为平面上的三角化问题。而对于平面上的三角化算法，目前有着大 量成熟的研究。 d e r - t s a il e e 和b r u c ej s e h a c h t e r 提出的分而自治方法 ( d i v i d e a n d c o n q u e r ) t 1 3 】【1 4 】【1 5 】。该方法对点集先进行垂直剖分区域，然后分别三角 化和再进行合并得到最终的三角化。后来，r e xa d w y e r 对此算法进行改进，提 出了水平和垂直交互式剖分区域的方法，提高了计算效率。 c ，l l a w s o n 提出的增量式插点法( i n c r e m e n t a li n s e r t i o n ) 1 1 4 】【1 6 1 。该方法首先求 得的是一个凸包，在对凸包上的点进行三角化之后，将其余的点逐个加入进行三 角化。 s t e v e nf o r t u n e 提出的扫描式方法( s w e 印l i n ed e l a n n a yt r i a n g u l a t i o n ) t i t l i l 8 】。该 方法根据一条由上而下的扫描线，对平面点集逐序进行三角化。 图1 - 9 即是我们实现的空间散乱点三角化实验结果。 图l - 9 平面d e a u n a y 三角化在空间散乱点上面的结果。 9 浙江大学硕士学位论文第1 章绪论 1 4 数据来源 现有的三维地质建模系统很大程度上依赖于大量的实际数据“9 1 。然而，这些 地质数据往往是稀疏的、不规则的，并且含有一定的不确定性。因此，如何准确 地应用这些数据，或者对这些数据进行改进、优化，就成了一个地质建模中重要 的问题。三维地质建模技术对于地质数据的取得、存储、处理和显示带来了巨大 的变革。但是这一技术需要大量的数据，包括：地震波数据、钻井数据和横断面 数据等。然而，在很多情况下，地震波数据很少，钻井数据又很稀疏，因此，依 靠这些数据来建立有效的模型是相当困难的。总体来说，地质数据具有多样性、 不确定性以及复杂性等特点。 我们根据数据的可靠性和应用场合将数据分为三类：直接数据、间接数据和 辅助数据。 直接数据 比如：钻井数据及其属性数据。这些数据是通过直接的观察、测量和采样而 来，具有高度的准确性。这些原始数据可以直接应用于三维建模系统，一般存储 于数据库中。 间接数据 也是原始数据，但是在不同的解析度下有不同的精确度，比如：边界、断层、 褶皱、拓扑图，也包括2 d 或三维的地震波反射数据等。这些数据在数字化以后 以文件的形式保存。 辅助数据 三维建模过程中的图标或者纹理图，包括：卫星图片、航拍图片等。 1 5 本章小结 本章首先介绍了地质建模的一些国内外研究现状，然后给出了一些常见概 念，接着对地质建模相关算法和技术进行了分门别类的介绍，并给出我们实验的 部分结果，最后介绍一下地质数据的来源。 本文的主要内容和组织结构如下： 1 地质建模中点云到网格的转换。 我们从钻井、地震波等得到的地质数据往往是稀疏的、不规则的，空间感很 l o 浙江大学硕t 学位论文第1 章绪论 差，因此首先要完成从点云到网格的转化，这样使得数据更直观，并且可以进行 下一步对网格的操作。 2 地质建模中对于网格的操作。 从三维地质点云数据得到网格以后，就要对网格进行一系列操作，来达到更 好地观察、分析地质数据的目的。网格与点云最大的区别在于，网格具有拓扑性 质，在对网格进行操作的同时，不能随意更改其原有的拓扑性质，不然，可能造 成意想不到的空洞。 本论文共分为四章，本章介绍了地质建模的一些基本概念、地质建模相关算 法、地质数据来源和本文的研究内容。第二章介绍地质建模中点云到网格的转换。 第三章介绍地质建模中对于网格的操作。第四章对本文的工作进行了总结，并对 未来的工作提出了展望。 浙江大学硕上学位论文第2 章地质建模中点云到网格的转换 第2 章地质建模中点云到网格的转换 我们从钻井、地震波等得到的地质数据往往是稀疏的、不规则的，空间感很 差，因此首先要完成从点云到网格的转化，这样使得数据更直观，并且可以进行 下一步，对网格的操作。 本章将给出一系列从点云到网格的转换方法，针对不同情况的点云有不同处 理方法。 2 1 空间散乱点的边界生成 我们给出空间散乱点集边界线的定义为：在满足角度约束下，包含型值点最 多的折线。角度约束为任意两条相邻折线段之间的有向转角( 外角) 不能小于给 定的角度阈值。地质建模中的空问散乱点一般表示断层或者地层的空间位置信 息，所以它们的弯曲程度较小，通常我们可以找到一个拟合平面，将空问散乱点 投影到该平面上，且保持原有的邻接关系不变。这样，只要求得平面上散乱点的 边界，就可以得到原空间散乱点的边界。 生成散乱点集p = p i = x i ，y i ，z i ) ，i - - 1 ，n 的边界线分为如下四个步骤： 1 通过p c a 分析，求得点集p 的主方向，从而确定p 的拟合平面。得到p 的投影点集，记为p p r o j e c t 。 2 查找p 。r o j e a 的四个角点，确定四个跟踪方向。 3 在各个方向上分别生成从起点到终点的满足角度约束的边界线段，并最终 连成的闭合折线即为p p r o j 。t 的边界线。 4 由p 舯耐的边界线得到p 的边界线。 2 1 1p c a 分析 p = p i - x l ，y i ，z i ) ，i - - i ，n ) 为三维空间中的离散点集且n 3 ，p 对应 的协方差矩阵s = - ( d t d ) ( n - 1 ) ，矩阵d 定义为： 。：卜m0 司 l x 一x y n yz n z l 1 2 浙江大学硕士学位论文第2 章地质建模中点云到阿格的转换 其中万= ( i ，只习= ( 去喜畸，去喜j ，去喜z ，) 为质心坐标。s 为3 3 实对称矩阵， 存在三个实特征值九l ，池，b ，且对应的特征向量两两正交。不妨设九i 2 5 b 。 使用j a c o b i 迭代求解矩阵s 的三个特征值及其对应的特征向量。如图2 - i 所示： ，l 。 一7 _ 焉 参。，z 。l 驴 “尹j 蠡菇赫季” v 2 图2 - i 使用p c a 方法计算类中点集的三个特征值、相应的特征向量和拟台平面。 使用p c a 分析给定空间散乱点集p 。最小的特征值h 对应的特征向量v l 即 为拟合平面的法向。将p 投影得到平面点集p 嘲胁，求得p p r o j e c t 的包围盒。点集 p 邮阳的角点记为包围盒的四个顶点在p 帅幻中分别对应的四个最近点： p o o 、p o l 、 pl l 、p1 0 1 ，如图2 - 2 所示。从而确定四个跟踪方向： p o o 、po d 、 p 0 1 、pl l 、 pi i 、p l o 、 p l o 、e o o ) 。最后分别在四个方向上求出边界。下面主要以 p o o 、p 0 1 ) 方向为例，介绍边界线的生成算法，在其它三个方向上的边界线类似可得。如图 2 2 所示： 我们使用优先队列数据结构求得包围盒对应的最近点，在边界跟踪过程中， 也频繁使用优先队列快速查找给定点在散乱点集中的k 个邻近点。 图2 - 2 平面散乱点集的包围盒、角点及其对应的最近点，边界的 p 、p o l 方向走向。 2 1 2 边界跟踪算法 默认值设置： 浙江大学硕士学位论文 第2 章地质建模中点云到网格的转换 1 边界m a r c h i n g 的步长s t e p ：点云中，型值点间距离的估算值+ 2 。 2 查找的k 邻域值：k = 1 0 。 3 边界上的两相邻边夹角下限为1 2 0 度。 4 筛选候选点的角度下限为9 0 度。 设点集的包围盒为 b b 。| n 、b b 。) ， p o o 、po l 的方向d i r 为x 轴正向，点 p o o 在x 轴、y 轴正向上的分量分别记为p o o ；和p o o 边界跟踪算法分为如下四yo 个步骤： 1 设定阈值；角度约束a n g l e 值和每次跟踪时查找的邻点个数k 。设定或者 估算区间步长s t e p 用于查找k 邻近点。 2 p 0 0 为边界跟踪的起点，取点p c 一= p o 吣，b b m mv ) 。 3 在p p t o j 。t 中查找点p m 的k 个邻近点p x n e i = p i = x i ， y i ，z i ) ，i ：1 ， 蚪。查找的权值设为点p i 到点p 一的距离值，同时满足：向量p i p c 。在d i r 上 的投影值位于查找区间【o ，s t e p 之内。将p k n c i 按d i r 方向的分量值升序排序。 i 若p l p l m e i 且p l - x p 唧，则驭s t e p = s t e p 2 重新查找，否则： i i 依次取出p i a l c i 中的点p i ：若p i x po l 。，则结束。 1 1 i 若已有边界线最后一段e j 的末顶点与p i 不同，生成新边球l ： i 若e i 与e 件l 之间的夹角满足角度约束，则生成下一条边，否则： i i 合并边e l 与e + l ，得到新的线段，重复判断、合并过程，直到满 足角度约束。如图2 3 所示： 4 p fp k 。回到步骤3 。 图2 - 3 角度约束下的边界合并。原有的边界为序列为 z 知，最- j ，与) ，加入点一后生成新 的边界序列为 ! 知，辱f 1 4 浙江大学硕士学位论文第2 章地质建模中点云到网格的转换 2 1 3 算法加速 在生成边界的过程中，查找邻近点需要花费大量的时间，因此可以使用均匀 网格将散乱点集分区，每次查找时只需要考虑相应网格空间中包含的型值点即 可。 2 1 4 不可直接投影点云的边界 对应不可直接投影的点云，需要找出边界点的候选点集，并将候选点集中的 有效点连接成相应的边界。内点与边界点的区别如图2 4 所示： 图2 - 4 内点与边界点。左边为位于点云内部的点，其邻域点比较均匀地分布在其四周，右边 为位于边界上的候选点，其邻域点分布偏向一侧。 处于点云内部的点，其邻域点一般比较均匀地分布在其四周，位于边界上的 候选点，其邻域点分布偏向一侧。利用这个性质可以使用如下的方法找出候选点 集： 查找点云中各点的k 邻域点p i ，通过p c a 分析得到拟合平面，各个邻域点投 影至该拟合平面，分别计算两个相邻的点之间构成的角度值，如果存在角度大于 设定的阈值，则将p i 标记为候选点。 一般得到的候选点集都可以找到投影平面，因此可以用上述的方法连接得到 边界线。如果候选点集不可投影，则可以将空间均匀剖分，利用网格分布的有序 性得到候选点之间的连接关系，生成点云的边界。图2 5 及2 - 6 即是我们实现的 空间点云边界生成算法实验结果。 浙江大学硕士学位论文第2 章地质建模中点云到网格的转换 图2 - 5 可以直接投影点云的边界生成。 图2 - 6 不可直接投影点云的边界生成。 2 1 5 结论 针对散乱点的边界生成问题，本文给出了散乱点边界线的定义，并基于该定 义提出一种新的边界跟踪算法，利用角度约束生成合理的边界线。快速算法的速 度取决于边界线边缘区域的型值点分布，与散乱点总数无关，时间复杂度为 o ( n i o g n ) 。对于空间不可投影的散乱点集，可以先找出候选点，再连接成点云的 边界。由于点云中所有型值点都要参加判断，所以时间复杂度为o ( n 2 ) 。实验结 果证明，本算法是快速高效且鲁棒的算法。 2 2 基于边界约束的空间散乱点三角化 如果要使得地质数据更直观，就必须对其进行三角化操作，这样一来，可以 把点云连接成网格。 浙江丈学硕七学位论文第2 章地质建模中点云到网格的转换 2 2 。ld e l a u n a y 三角化算法 平面三角化的概念就是给定一个平面点集，通过点与点之问的非交叉连接， 对平面实现区域的最大剖分，一般没有什么特别的约束，只要满足：1 最大剖分： 2 连接非交叉。 与d e l a u n a y 三角化相对应的概念是v o r o n o i 图，确定的是平面点集中，分别 到每一点最近的一个区域，比如说你在城市中需要寄信时所要确定离你所在位置 最近的邮局，v o r o n o i 图就满足了这个需求，它对邮局的最近区域进行了划分。 如图2 7 所示： 图2 - 7v o r o n o i 图和d e l a u n a y 图关系。 v o r o n o i 边界一般通过作邻近点的中垂线得到。当v o r o n o i 图确定之后，对有 公共区域边界的点进行连接所得到的就是d e l a u l a y 图。图2 7 表示的就是两者之 间的联系。 一般生成的d e t a u n a y 三角化结果有两个特点： 1 得到的是点集的凸包( c o n v e xh u l l ) 。 2 三个点所在的圆不包含其它任意一点( e m p t ) ，c i r c l e ) 。 有三种三角化方法，包括： 1 d e r - t s a il e e 和b r u c ej s c h a c h t e r 提出的分而自治方法 ( d i v i d e a n d - c o n q u e r ) 1 1 3 】【1 4 l 【堋。如图2 - 8 所示。 2 c l l a w s o n 提出的增量式觥( i n c r e m e n t a li n s e r t i o n ) t 1 4 1 1 1 6 1 。如图2 - 9 所 不o 3 s t e v e n f o r t u n e 提出的扫描式方法( s w e 印l i n e d e l a u n a y t r i a n g u l a t i o n ) 1 1 7 1 1 8 1 。 浙江大学硕士学位论文第2 章地质建模中点云到网格的转换 如图2 - 1 0 所示。 国鸟嗡 图2 - 8 分而自治法。 & 险鹞嗡 图2 - 9 增量式插点法。 图2 - 1 0 扫描式方法。 d i v i d e a n d c o n q u e r 法对点集先进行垂直剖分区域，然后分别三角化和再进行 合并得到最终的三角化。后来，r e x a d w y q b l 对此算法进行改进，提出了水平和 垂直交互式剖分区域的方法，提高了计算效率。 i n c r e m e n t a li n s e r t i o n 法首先求得的是一个凸包，在对凸包上的点进行三角化 之后，将其余的点逐个加入进行三角化。 s w e e p l i n e 法根据一条由上而下的扫描线，对平面点集逐序进行三角化，见图 2 - l o 。其中绿色水平线为扫描线，粉红色为d e l a u n a y 边界，蓝色为v o r o n o i 图。