（计算机软件与理论专业论文）三维地质重构相关算法研究及应用.pdf

摘要 三维地质重构是“数字化地球”的重要组成部分，其难点是数学模型的建立 和基于特定数学模型的地质重构及剖分算法，目前尚无统一的优化解决方案。本 文从表面模型出发，提出了一种新的数学模型：基于此数学模型，提出了一种地 质重构算法，该算法正确处理了渐灭、断层、褶皱等复杂地质现象；同时提出了 一种三维地质体的交互式切割算法，该算法是第四系剖面分析的基础。用实际地 质钻孔数据进行测试的结果表明所重构的地质体是正确的，而交互式切割是满足 剖面分析的需求的。此外，针对表面模型中的不规则三角网，本文提出了新的网 格生成及切割算法，与已有的不规则三角网的生成及切割算法相比，本文提出的 网格生成算法有易于并行化的优点，而切割算法有精确度高和易于实现的优点， 两种算法的效率均与经典算法相当。 关键字：算法地理信息地质重构剖面分析不规则三角网 a b s t r a c t a sa p a r to fd i g i t a le a r t h g e o l o g i c a lr e c o n s t r u c t i o n h a si t ss p e c i a li m p o r t a n c e t h e m o s td i f f i c u l tw o r ki st od e s i g nb o t hag o o dm a t h e m a t i c a lm o d e la n da s e r i e so fe f f i c i e n t a l g o r i t h m sb a s e do nt h em a t h e m a t i c a lm o d e l t h i sp a p e rp r e s e n t san e w m a t h e m a t i c a l m o d e lw h i c hb e l o n g st oac l u s t e ro fs u r f a c em o d e l b a s e do nt h i sm a t h e m a t i c a lm o d e l ，a n e wa l g o r i t h mf o rg e o l o g i c a lr e c o n s t r u c t i o ni sc o m eu p ，w h i c he x a c t l yh a n d l e ss o m e g e o l o g i c a lp h e n o m e n o n s u c ha sl a y e r sd i s a p p e a r a n c e ，b r e a ka w a y , p u c k e re t c a l s o ，a n e wa l g o r i t h mf o rc u t t i n gt h r e e d i m e n s i o ns t r u c t u r ei sc r e a t e d w h i c hi sa ni m p o r t a n t f o u n d a t i o no fc u t t i n g s u r f a c ea n a l y s i s t e s tb a s e do nas e to fr e a lg e o l o g i c a ld a t ai s c a r r i e do u t t h er e s u l ts h o w st h a tp r e s e n t e da l g o r i t h m si sa c c u r a t ea n de 街c i e n tb o t hf o r g e o l o g i c a l r e c o n s t r u c t i o na n df o rt h r e e d i m e n s i o n c u t t i n g b e s i d e s ，a f e wn e w a l g o r i t h m s a r ep r e s e n t e d w h i c hi sf o rm e s hg e n e r a t i o na n dm e s hc u t t i n gb a s e do n s u r f a c em o d e l t h e ya r ea n a l y z e da n dc o m p a r e dw i t hc l a s s i c a ia l g o r i t h m sf o rm e s h g e n e r a t i o na n dm e s hc u t t i n g t h e r e s u l ts h o w st h a t p r e s e n t e da l g o r i t h m f o rm e s h g e n e r a t i o ni s e a s i e rt o p a r a l l e l a n da l g o r i t h mf o rm e s hc u t t i n gi s m o r ea c c u r a t ea n d e a s i e rt or e a l i z e w h i l et h e i re f f i c i e n c yc a nm a t c hw i t hc l a s s i c a la l g o r i t h m s k e y w o r d ：a l g o r i t h mg e o g r a p h i ei n f o r m a t i o ng e o l o g i c a lr e c o n s t r u c t i o n c u t t i n g - s u r f a c ea n a l y s i si r r e g u l a rt r i a n g l en e t 创新性声明 y6 9 5 6 9 0 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名坛! ! 主 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： ；基! j ：皇日期兰堕：西 导师签名：壅 ! 曼日期 z 。酊ic 占， 第一章绪论 第一章绪论 1 1 地理信息系统 人类有一个梦想，就是想用一种方法，把世间一切事物都统管起来a 上至浩 瀚宇宙，下至地心海洋，人类为此探索的脚步从未停止过。望远镜的发明使我们 看得更远，航天技术的问世使我们到达外太空，潜艇带我们深入海底，地质勘测 使我们了解神秘的地球深处，但是，我们梦想的那种统管一切的方法仍然没有找 到。直到计算机科学的问世及随后的高速发展才为我们找到了实现梦想的手段， 这个手段就是“数字地球”，而“3 s ”是“数字地球”的核心组成部分。所谓“3 s ”， 是指遥感技术( r s ) 、全球定位系统( g p s ) 、地理信息系统( g i s ) 三者的有机结 合【l l 口遥感技术是信息采集的主力：全球定位系统对遥感图像及从中提取的信息进 行定位，赋予坐标，使其能和“电子地图”进行套合；地理信息系统则是信息的 “大管家”。将这三者有机地组合起来，人类的梦想就实现了。“3 s ”是一个动态 的、可视的、不断更新的、通过计算机网络能够传输的、三维立体的、不同地域 和层次都可以使用的、“活”的系统。 遥感，顾名恩义，就是遥远的感知。地球上的每一个物体都在不停的吸收、 发射和反射信息和能量。这种信息和能量的一种形式电磁波早已被人们认识 和利用。不同物体的电磁波有不同的特性。遥感就是根据这个原理通过探测地表 物体对电磁波的吸收、发射和反射，从而提取信息完成远距离物体的识别的。人 们从一张遥感图像上可以辨别出很多信息，如水体( 河流、湖泊、水库、盐池、 鱼塘等) 、植被( 森林、果园、草地、农作物、沼泽、水生植物等) 、土地( 农田、 林地、居民地、厂矿企事业单位、沙漠、海岸、荒原、道路等) 、山地( 丘岭、高 山、雪山) 等等。由于遥感一般是从人们无法到达的高度去“拍照”，所以从宏观 视野上，有着人力所不能及的优势。 全球定位系统( 目前投入运行的) 由处于2 万公里高度的6 个轨道平面中的 2 4 颗卫星组成。此系统用于在任何时间，向地球上任何地方的用户提供高精度的 位置、速度、时间信息，或给用户提供其邻近者的这种信息。我们知道，一张像 片是没有坐标的，而像片上的信息，特别是遥感图像上的信息，是需要定出位置 的，只有“有位置的信息”，才能成为地理信息。那么怎样来给遥感图像确定位置 昵? 一种方便、快捷的手段就是全球卫星定位系统。 全球定位系统主要有六大特点： 全天候，不受任何天气的影响； 全球覆盖，覆盖率高达9 8 ； 2 三维地质重构相关算法研究及应用 高精度三维定速定时； 快速、省时、高效率： 应用广泛、多功能： 可移动定位。 地理信息系统是专门管理地理信息的计算机软件系统。据统计，人类所获得 的信息总量有8 5 是与地理位置有关的信息，这些信息就叫地理信息。地理信息相 当广泛，如耕地林地的分布、城镇的分布、楼房等建筑物的分布、道路、河流、 海岸、人口、医院、学校、企事业单位、管线、派出所、甚至门牌、电闸、水表、 开关等等，只要能用“位置”去描述的东西，都属于“地理信息”。遥感所提取的 信息也全部包含在地理信息之中。地理信息系统不但能分门别类、分级分层的去 管理上述信息，而且还能将它们进行各种组合、分析、再组合、再分析，能查询、 检索、修改、输出、更新等。地理信息系统还有一个特殊的“可视化”功能，就 是通过计算机屏幕把所有的信息逼真地再现出来，清晰直观地表现出信息的规律 和分析结果，同时还能动态的在屏幕上监督“信息”的变化。地理信息系统由计 算机、地理信息系统软件、空间数据库、分析应用模型和图形用户界面及系统人 员组成。 地理信息系统( g i s ，g e o g r a p h i c i n f o r m a t i o ns y s t e m ) 是随着地理科学、计算 机技术、遥感技术和信息科学的发展而发展起来的一个学科，是将计算机硬件、 软件、地理数据以及系统管理人员组织而成的对任一形式的地理信息进行高效获 取、存储、更新、操作、分析及显示的集成系统。在计算机发展史上，计算机辅 助设计技术( c a d ) 的出现使人们可以用计算机处理象图形这样的数据，图形数 据的标志之一就是图形元素有明确的位置坐标，不同图形之间有各种各样的拓扑 关系。拓扑关系指图形元素之间的空闻位置和连接关系。在实际应用中，一个地 理信息系统要管理大量复杂的数据，还要计算和管理这些数据之间的各种复杂的 空间关系。 我国地理信息系统( g i s ) 的发展经历了四个阶段，即起步( 1 9 7 0 1 9 8 0 ) 、准备 ( 1 9 8 0 1 9 8 5 ) 、发展( 1 9 8 5 1 9 9 5 ) 、产业 ) 6 ( 1 9 9 6 以后) 阶段。现在，部分大中城市的 测绘地理信息系统和测绘数据库正在运行或建设中，一批高等院校已设立了与g i s 有关的专业或学科，一些专门从事g i s 产业活动的高新技术产业相继成立，“中 国g i s 协会”和“中国g i s 技术应用协会”也应运而生，使地理信息系统这个新 兴的学科日益深入到国民经济建设中，发挥越来越大的作用。从应用方面看，地 理信息系统己在资源开发、环境保护、城市规划建设、土地管理、农作物调查与 结产、交通、能源、通讯、地图测绘、林业、房地产开发、自然灾害的监测与评 估、金融、保险、石油与天然气、军事、犯罪分析、运输与导航、1 1 0 报警系统及 公共汽车调度等方面得到了具体应用。 第一章绪论 g i s 主要解决的问题是： 定位对象在何处? ： 条件查询哪些地方符合某些特定的条件? ； 趋势分析及预演从何时起发生了变化? 未来将发生什么变化? ； 计算机模拟如果发生了某些事，将会怎样怎样? 可视化将不可见的或无法整体可见的东西显示给我看： 智能专家系统告诉我发生了什么，建议我该怎么办。 目前，g i s 的研究和应用可分为两大部分一地表以上部分和地表以下部分。 地表以上部分主要解决定位、条件查询、可视化等问题，应用最广的有城市配电 网建设、移动定位、房地产等；地表以下部分主要解决趋势分析及预演、计算机 模拟、可视化、智能专家系统等，主要的应用领域有：农业土壤地质资源勘查、 地下水流域分析、矿区管理及可视化【2 l 、地铁及道路选址、人迹罕至地带的地质勘 查p 】、城市规划、环境保护等，其核心课题就是三维地质重构( 即地质三维数字化) 。 1 2 地质三维数字化 地质三维数字化是以各种地质、测量、采矿工程数据为基础，以三维可视化 技术以及地质建模技术为手段，在计算机上实时显示地下三维信息的管理系统。 它的处理对象是地球三维地理空间中的地下信息，包括地层、土质、岩石、地下 水、海水、废物、石油、天然气、矿藏等，目的是对这些对象在相应地球三维地 理空间上的属性、状态、特征等的分布建立一种统一的三维数字化描述，以便充 分利用这些信息来促进和改进地下、市政、交通、水利、港航、电力等土木建筑 工程，以及规划、环保、矿藏开采、减灾防灾等“数字地球”各领域的深入发展 与应用。 其实，地质数字化的工作由来己久了，我们最熟悉的地图制作就是最早的地 质数字化工作，勘察系统进行的勘察报告也是一种简单的地质数字化工作，包括 后来发展起来的平面电子地图等，它们都是二维意义上的地质数字化。后来，地 理信息系统与工程地质、石油地质等方面的结合是更高层次上的地质数字化工作， 工程数值分析也是研究工程地质应力与应变属性的一项数字化工作，这些是三维 意义上的地质数字化。 地质三维数字化是地学、数学、计算机、软件、信息、环保、工程、建筑等 多领域相结合的边缘高新技术领域，它将在勘察业、软件业、工程数值分析、数 字地球四个层次和领域拥有广泛的应用前景【4 】。 分别如下： 4 三维地质重构相关算法研究及应用 变革勘察业的成果：地质三维数字化可以提供全方位、可视化、动态、虚 拟化的勘察报告，彻底改变传统勘查业两点一连线简单而又欠科学分析的 勘察报告方式，从而大大提高工程投标、设计、分析的竞争力，有利于走 向国际社会，参与国际大型工程竞争，开拓新的市场。 开拓软件业高科技市场：地质三维数字化可以将g i s 发展成为g d s ( g e o g r a p h i cd i g i t a ls y s t e m ) ，开创全新的经济形式。g d s 是以地球地理 位置、全面地下信息的三维分布为平台建立起来的地球地下信息数字化系 统，它将是g i s 的高级形式，能够真正进行高层次的智能应用与分析，它 将成为构筑“数字地球”体系的核心软件平台之一。 实现工程数值分析的革命：地质三维数字化不仅可以为工程数值分析提供 充分准确的已知边界条件，改进数值分析的精度，而且使建立概率性、随 机性、模糊性数值分析方法成为可能。 构筑“数字地球”的核心支撑子系统：地质三维数字化可以实现智能建筑、 环保、防灾、规划、地矿、石油、海洋等有关新世纪“数字地球”关键技 术的革命。全面地质资料的信息化、可视化查询，抗震、滑坡、塌陷等防 灾专家智能化分析，环境工程、地下水污染、地下放射性废物、地下垃圾 等的专家智能化环保分析，建筑工程设计、监理、施工、咨询等专家智能 化分析，城市建筑、交通等专家智能化规划，各种地下管线、管道、地下 建筑物的寿命、安全、布局的专家智能化分析，油田、煤炭、天然气、矿 藏等的专家智能化评估、管理与开发，以及以上各种内容的远程虚拟化技 术应用等，都离不开地质三维数字化。比如要分析地下水污染的影响，就 必须了解地下水在整个地下的运动途径，要了解这个运动途径，就必须掌 握它所流经地区的三维地质分布，因为不同的土层对地下水将有不同的影 响，因此可以说没有真正的地质三维数字化，就谈不上更高层次的对地下 水污染的研究与防治。 地质三维数字化在计算机实现上的难点主要体现在三个方面：其一，尽管地 质三维数字化属于g i s 的范畴，但它不再是传统意义上的g i s ，它是g i s 的更高 研究阶段，因此它不象传统的g i s 系统那样只计算面数据。它所面对的地质三维 数据是真正的体数据，所以如何应用计算机快速生成三维地质体的海量数据是第 一个难点：其二，海量数据的三维地质体在台式电脑或笔记本电脑上实现图形的 实时显示及交互操作是第二个难点；其三，地质三维数字化的深入应用，在某种 意义上就是对地质体内部三维空间属性的展示与分析，因此实现三维地质体交互 式切割与分析，是需要解决的最后一个也是最重要的难题。 本文的研究重点正是三维地质体的快速生成算法和三维地质体的交互式切割 算法，并提出了一种新的三维地质重构的数学模型。 第一章绪论 1 3 研究现状 目前，g i s 的研究成果和应用系统主要集中予描述二维空间信息，各项技术已 较为成熟。但f l u j ：- - 维地理信息系统将实际的三维事物采用二维的方式表示，具 有很大的局限性，大量的多维空间信息无法得到利用。三维g i s 的研究不是对二 维g i s 的简单扩展，它要求从空间模型分析到空间数据库的结构直至三维数据的 可视化，都必须进行系统的研究例。许多研究者已经开发了三维g i s 的原型系统， 使得三维g i s 技术在矿产资源管理、数字城市等许多领域得到应用。主要有：加 拿大n e wb r u n s w i c k 大学的k a v o u r a s 和m a s r y 在1 9 8 7 年开发了用于矿产资源评 估和开采的三维g i s 原型系统网；德国r o s t o c k 大学、s t u t t g a r t 大学等研究机构目 前正联合研究三维g i s 在数字城市模型中的应用，他们对城市的空间对象进行了 分类和表示，建立了数字城市模拟系统，对城市基础设施( 包括房屋、道路、绿地 等) 可方便地进行查询、分析和显示；一些商用g i s 系统中，也加入了三维g i s 模块，如e r d a s 公司的i m a g i n ev i r t u a lg i s 模块，能在实时三维环境下，提供 g i s 分析和实时三维飞行方式的访问和漫游：还有其它一些模拟实验系统，其研究 集中于三维可视化和虚拟现实功能方面d j 。 三维地质重构的基础和核心是三维地质的数学模型，所有相关算法都是基于 既定的数学模型设计的。虽然到目前为止已经在这方面进行了大量的研究，但其 理论与技术尚未成熟，仍需在实践中不断地探索。目前所使用的三维数学模型多 种多样，但每种方法各有利弊。矢量模型具有表达精度高、数据量小、能显示表 达空间元素间的拓扑关系等优点，适合于作空间查询、拓扑查询、邻接性分析、 网络分析等操作，但其操作算法比较复杂、难以表达体内的不均一性，实现叠加 分析较为困难。表面模型中t i n ( 不规则三角网) 模型具有实现简单、算法成熟、 数据冗余小、存储效率高、且能较好地估计地形特征_ 和适合多层次表达等突出优 点，但t i n 模型只能控制地质体的表面，不能控制地质体的内部，是一种空心的 2 5 维模型，而且它不能直接描述复杂的物体。三维栅格模型操作算法简单，数学 模型简单、标准、通用，能表达体内的不均一性，叠加分析、缓冲区分析都很容 易实现，不足之处是对空间目标的表达精度低、数据置巨大、无法表达实体之间 的关系。体元模型不仅可以展现空间复杂物体的表面形态，而且还可以表达物体 内部的结构和属性信息，但是其缺乏对几何元素之间的拓扑关系的表达，不具备 空间拓扑查询和分析功能，数据量较大，算法实现复杂【z 】。 在综合现有数学模型优缺点的基础上，本文提出了一种新的数学模型三 角柱体网格，它基于表面模型中的t i n 模型，同时又体现了体元的优点，因此它 是真三维的，它克服了t i n 模型不能控制地质体内部的缺点，保留了t i n 模型数 据冗余小、存储效率高、能精确反映地形特征等所有优点，同时能很好地支持空 6 三维地质重构相关算法研究及应用 间拓扑查询及多种信息叠加。 1 4 论文主要内容及安排 本文系统研究了三维地质重构的相关算法，主要有表面网格生成算法及切割 算法、三维地质体重构算法及基于三维地质体的交互式切割算法。论文各章的安 排如下： 第二章是表面网格的生成及切割算法。其中2 1 小节是表面模型的基本概念， 重点是表面模型中最常用的两种网格数据结构规则格网和不规则三角网，讨 论了两者各自的优缺点及应用场合，由于在实际应用中需要将这两种数据格式互 相转换，本文详细论述了它们之闻的转换算法：2 2 小节是表面网格生成算法，详 细论述了表面网格的优化准则和优化方法、以及各种不规则表面的网格生成算法， 并通过与经典算法的分析与对比，提出了自己的算法基于凸包逐点内插网格 生成算法。因为所提出算法属于渐进算法的一种，而渐进算法的效率瓶颈是点的 定位算法，因此也论述了两种点定位算法；2 3 小节是表面网格切割算法，详细论 述了不规则表面的网格切割算法，即通过生成一个带约束条件的d e l a u n a y 三角网 ( c d t ) 达到网格切割的目的，带约束条件的d e l a u n a y 三角网的生成主要是约束 边的插入算法。因此首先介绍约束边插入算法。然后提出一种折线切割算法，该 算法基于平面细分算法、是平面细分思想在网格切割方面的迸一步应用，同时也 详细论述了另一种网格切割算法一活跃点移动法，并对两种切割算法作了分析 对比；2 4 小节是本章算法的实验结果及分析。 第三章是三维地质重构及切割算法，详细论述所提出的真三维地质重构数学 模型三角柱体网格，阐述该数学模型的构建；详细论述基于该数学模型的三 维交互式切割算法，该算法是对第二章所论述的不规则表面的网格切割算法的改 进，改进的目的在于正确处理地层之间的位置及属性关系；而基于此改进算法， 进一步提出了解决地质重构三大难题渐灭、断层、褶皱的统一而有效的方法。 其中3 1 小节提出了一种新的三维地质重构的数学模型，论述了该数学模型的概 念及构建方法；3 2 小节提出了一种基于地质重构的网格剖分改进算法，将其应用 到三角柱体网格中，实现了三维地质体的交互式切割；3 3 小节将改进的网格剖分 算法进一步应用到三维地质重构中，提出了处理渐灭、断层、褶皱的统一方法： 3 4 小节是本章算法的实验结果及分析。 第四章是空间数据信息叠加，论述空间数据信息叠加的意义，详细介绍最基 本的两种空间数据信息遥感影像和地形数据的叠加方法。 第五章是结论及迸一步工作，对本文的研究工作进行总结，并讨论在三维地 质重构这个大课题下尚待完成的研究。 第二章表面网格的生成及切割算法 第二章表面网格的生成及切割算法 2 1 表面模型 表面模型是一种空心的2 5 维的地质重构数学模型，它通过生成地质体的上下 表面及侧面，然后把这些面围起来就完成了地质体的重构。表面模型的核心是不 规则表面的生成，通常用有限元方法，即用有限的数据元重构原表面。这些数据 元一般是点数据。重构的方法是用这些数据元的五y 坐标生成平面网格，再用它 们的z 坐标提升这个网格 7 1 。如图2 1 所示。 图2 1 表面网格 常用的表面网格有规则格网( g 赳d ) 和不规则三角网( t 烈) 两种。 2 1 1 规则格网( g r d ) 规则格网，通常是正方形，也可以是矩形、三角形等规则网格。规则网格将 区域空间切分为规则的格网单元，每个格网单元对应一个数值。数学上可以表示 为一个矩阵，在计算机实现中则是一个二维数组。每个格网单元或数组的一个元 素，对应一个高程值，如图2 2 所示。 多18 84 68 79 05 8 3 68 57 79 86 64 5 5 85 96 97 17 48 4 8 88 98 58 26 97 9 5 96 58 78 45 49 0 6 86 66 75 98 07 6 图2 2 规则格网( g r i d ) 三维地质重构相关算法研究及应用 对于每个格网的数值有两种不同的解释 8 1 。第一种是格网栅格观点，认为该格 网单元的数值是其中所有点的高程值，即格网单元对应的地面面积内高程是均一 的高度，这种数字高程模型是一个不连续的函数。第二种是点栅格观点，认为该 网格单元的数值是网格中心点的高程或该网格单元的平均高程值，这样就需要用 一种插值方法来计算每个点的高程。计算任何不是网格中心的数据点的高程值， 使用周围4 个中心点的高程值，采用距离加权平均方法进行计算，当然也可使用 样条函数和克里金插值方法。 规则格网的高程矩阵。可以很容易地用计算机进行处理，特别是栅格数据结 构的地理信息系统。它还可以很容易她计算等高线、坡度坡向、山坡阴影和自动 提取流域地形，使得它成为数字高程模型( d e m ) 最广泛使用的格式，目前许多 国家提供的d e m 数据都是以规则格网的数据矩阵形式提供的。规则格网的缺点是 不能准确表示表面网格所代表的地形的结构和细部：在地形平坦的地方，存在大 量的数据冗余：在不改变格网大小的情况下，又难以表达复杂地形的突变现象。 此外，规则格网的数据量通常比较大，给数据管理带来了不便，需要进行压缩存 储。如果采用无损压缩难以达到很好的压缩效果，如果要保证压缩效果，只能采 用有损压缩，郎牺牲了地形的细节信息。 2 1 2 不规则三角网( n ) 不规则三角网( t r i a n g u l a t e di r r e g u l a r n e t w o r k ，t i n ) 是另外一种表示地形表面 网格的方法，它减少了规则格网带来的数据冗余，同时在计算效率和表达精度方 面也有其优越性。 不规则三角网是根据区域有限个点集将区域划分为相连的三角面网络，区域 中任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程 值通常通过线性插值的方法得到( 在边上用边的两个顶点的高程，在三角形内则 用三个顶点的高程) 。所以不规则三角网是一个三维空闰的分段线性模型，在整个 区域内连续但不可微。 不规则三角网的数据存储方式比规则格网复杂，它不仅要存储每个点的高程， 还要存储其平面坐标、节点连接的拓扑结构，三角形及邻接三角形等关系。不规 则三角网在概念上类似于多边形网络的矢量拓扑结构，只是它通常不定义“岛” 和“洞”的拓扑关系。 。 有许多种表达t i n 拓扑结构的存储方式，一个简单的记录方式是：对于每一 个三角形、边和节点都对应一个记录，三角形的记录包括三个指向它三个边记录 的指针；边的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它的 两个顶点的记录的指针；也可以直接对每个三角形记录其顶点和相邻三角形。每 个节点包括三个坐标值的字段，分别存储其x ，y ，：坐标。这种拓扑网络结构的特 第二章表面网格的生成及切割算法 9 点是对于给定一个三角形查询其三个顶点高程和相邻三角形所用的时间是定长 的，在沿直线计算地形剖面线时具有较高的效率。当然可以在此结构的基础上增 加其它变化，以提高某些特殊运算的效率，例如在顶点的记录里增加指向其关联 的边的指针。 不规则三角网由连续的三角面组成，三角面的形状和大小取决子不规则分布 的测点，或节点的位置和密度。不规则三角网与规则格网不同之处是随地形起伏 变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形平 坦时的数据冗余，又能按地形特征点如山脊、山谷线、地形变化线等表示数字高 程特征。因此在地质三维数字化的表面模型里，一般用不规则三角网来表示地质 体的表面网格。 2 1 3g l u d 和t n 的相互转换 前面介绍了不规则三角网( t i n ) 和规贝格网( g r i d ) 各自的优缺点，以及 它们分别适用于哪些场合，但是在某些时候，需要将它们互相转换。比如，许多 国家的标准地形数据是以g r i d 形式提供的，而我们想要进行一些基于t i n 的计 算和空间拓扑信息查询( t i n 具有空间拓扑结构，而g r i d 没有) ：再比如，已经 生成的t i n 想要以统一的数据交换格式挂接到标准数据库，此时也往往需要将其 转换为g r i d ，因为t i n 必须要存储其拓扑结构，而某些数据库的标准数据交换格 式不支持t i n 数据。 2 1 - 3 1g r i d 转换为t i n 将格网g r i d 转成t i n 可以看作是一种规则分布的采样点生成t i n 的特例，其目 的是尽量减少t i n 的顶点数目，同时尽可能多地保留地形信息，如山峰、山脊、谷 底和坡度突变处。规则格网可以简单地生成一个精细的规则三角网，针对它有许 多算法，绝大多数算法都有两个重要的特征： 筛选要保留或丢弃的格网点： 判断停止筛选的条件。 其中两个代表性的算法是保留重要点法和启发丢弃法1 8 】。 保留重要点法( 、) 该方法通过保留规则格网中的重要点来构造不规则三角网 c h e n 、g a u v a r a ( 1 9 8 7 ) 】。它首先计算每个格网点的重要性，通过比较重要性来保留重要的格网 点。重要点记为( v e r yi m p o r t a n tp o h a t ) 。 格网结点的重要性是通过3 * 3 的模板来计算的，如图2 3 所示，它将格网点的 高程值与它的8 邻点的高程内插值进行比较，其差分即为该节点的重要性：如果该 l o 三维地质重构相关算法研究及应用 值超过某个阂值，则该节点是重要点，它将被保留下来作为三角网顶点生成三角 网：否则，该节点不是重要点，它将被删除。所以，一个网格点是不是重要点， 是根据它的八邻点的高程值决定的。图2 3 中，由3 * 3 的模板得到中心点p 和8 邻点的 离程值，计算中心点p 到直线4 e ，c g ，b f ，硎距离，如右图所示，再计算4 个 距离的平均值，这个平均值就是格网点p 的重要性。如果这个值超过阚值，p 点为 重要点，则保留，否则去除p 点。 ab h p g f c d e 圈2 3v i p 方法示意 启发丢弃法( d h - - d r o p h e u r i s t i c ) 该方法将重要点的选择作为个优化问题进行处理。在给定了规则格网和转 换后不规则三角网节点数量上限的前提下，算法寻求g r i d 与t i n 的最佳拟合。 该算法是对整个输入格网进行迭代计算，逐渐删除那些不太重要的点。算法 终止条件：未被删除的点的数量满足转换后允许保留的t i n 节点的数量限制条件， 或者满足了一定的精度要求。具体过程如下： 首先将格网输入生成一个规则的三角网，此时所有格网结点都是规则三角网的 节点，方法是将每个格网单元中的两个相对节点连接起来，将每个格网单元剖分 成两个三角形即可； 然后对规则三角网进行迭代计算，每一次迭代去掉一个最不重要的节点，从 而得到一个节点越来越少的不规则三角网( 1 r i n ) ，直到满足算法的终止条件。 迭代式丢弃一个节点的过程如图2 。4 所示，待处理的节点是p ，包含p 的原 三角网如图2 4 中细线所示。取p 的邻接点a ，置c ：d ，e 用这些邻接点重新构造一 个n ，如图2 4 中粗黑线所示。用p 的平面坐标g 力寻找它在新的三角网中所在 的三角形( 图2 a 中是新三角形b d g ) ，在三角形b d e 中计算一个对应于点p 的 平面插值点( 该点在b d e 所决定的平面上，五y 坐标与点p 的玉y 坐标相同，只是 高程不同) ，求该点与p 的高程差分，如果该差分大于某个阀值，则p 点为重要 点，应该保留，新生成的三角网被忽略；否则，点p 被丢弃，用新生成的三角网 替代原三角网即可。 第二章表面网格的生成及切割算法 c d 图2 4 迭代式丢弃点p 两种方法比较：v i p 方法在保留关键网格点方面( 顶点、凹点) 最好；d h 方 法在每次丢弃数据点时确保信息丢失最少，但要求计算量大。各种方法各有利弊， 实际应用中根据不同的需要，如检测极值点，高效存储，最小误差，可以选择使 用不同的方法。 2 1 3 2t 酣转换为g r i d 相比之下，t i n 转换为g r i d 非常简单。t i n 转成格网d e m 可以看作普通的 不规则点生成规则格网的过程。方法是按要求的分辨率大小和方向生成规则格网， 对每一个格网搜索最近的t i n 数据点，按线性或非线性插值函数计算格网点高程 即可。 2 2 表面网格生成算法 本文此处及以后部分所用的表面网格均为不规则三角网( n n ) 。在采用不规 则三角网来表示地质体的表面网格时，为了得到质量较高的网格，不规则三角网 需要进行优化，优化的目标是尽量使其规则化，即使其所包含的三角形个数达到 最少。最常用的优化方法是三角形角度优化【”，即保证所有三角形的最小内角最大 化；f r a n za u r e n h a m m e re ta l1 9 9 9 年提出了另一种优化方法【9 】该方法包含三个优 化准则，分别是：最长边与最短边的长度比最小化、最短边长度最大化、三角形 周长最大化；j i mr u p p e r t 在网格质量优化方面做了有效的工作f l o j ；而d a v i d e p p s t e i n 给出了网格质量的评价标准【1 l 】，并提出了一种全局优化方法。本文采用的 是通用的角度优化方法。 2 2 1 角度优化及d e l a u n a y 准则 定义1 两个相邻三角形构成四边形，它们的公共边是该四边形的一条对角线， 三维地质重构相关算法研究及应用 如果交换四边形的两条对角线，引起了最小内角的增大，则原对角线是一条非法 边。 定义2 至少包含了一条非法边的三角形是非法三角形。 不规则三角网的角度优化原则：三角网中不存在非法三角形。 非法三角形和非法边的测试，不需要按定义去验证内角是否增大。e g u e h i 给 出了证明口l ：如果两个相邻三角形对应于其公共边的对角顶点都不落在对方的外接 圆内，则它们的公共边不是非法边，这两个相邻三角形也不是非法三角形；否则， 它们分别是非法边和非法三角形。 如图2 5 所示。两个相邻三角形孔和疋的公共边是五i ，五相对于三l 的对角 顶点p i 落在了噩的外接圆内，同样乃相对于三l 的对角顶点m 也落在了乃的外接 圆内，因此三l 是非法边，力和疋都是非法三角形。 图2 51 f 法边羽1 1 f 法三角形 不规则三角网的角度优化方法：图2 5 中乃和乃构成四边形，它们的公共边 三l 是四边形的一条对角线，如果厶是非法边，则交换四边形的两条对角线，生成 两个新的三角形瓦和矗即完成了三角形的角度优化，如图2 6 所示。工2 是乃和霸 的公共边，可以看出，乃相对于如的对角顶点庙没有落在矗的外接圆内，同样 乃相对于三2 的对角顶点内也没有落在乃的外接圆内，因此三2 不是非法边，乃和 乃都不是非法三角形。 图2 6 交换对角线进行角度优化 第二章表面网格的生成及切割算法 d e l a u n a y 三角剖分是被广泛采用的不规则三角网的优化标准，它由d e l a u n a y 准则来界定。d e l a u n a y 准则包含以下几条： 运用d e l a u n a y 三角剖分得到的不规则三角网是唯一的； 该三角网拥有一个“凸”的外壳； 该三角网中任意一个三角形的外接圆内不包含其余的点( 空外接圆准则) ； 如果将三角网中所有三角形的最小内角按升序排列，则d e l a u n a y 三角剖 分得到此最大值，即它拥有最大化的最小内角。 如果初始的数据元只有点数据，则d e l a u n a y 三角剖分得到的三角网称为 d e l a t m a yt r i a n g u l a t i o n ( d t ) ，它满足d e l a u n a y 准则。如果初始的数据元包含了一 些不相交的边，则d e l a u n a y 三角剖分得到的三角网称为c o n s t r a i n e dd e l a u n a y t r i a n g u l a t i o n ( c d t ) f 1 2 】，它不能保证完全满足d e l a u n a y 准则。不相交的边称为约 束边，正是这些约束边的存在使得c d t 违背了d e l a u n a y 准则。c d t 不保证满足 d e l a u n a y 的空外接圆准则，因为以约束边为非法边的非法三角形不允许进行角度 优化，c d t 也不保证拥有凸多边形“外壳”，这使它的应用更广。比如，g i s 中， 如果用d t 来重构地形，则不能处理地质结构中的洞和孤岛现象，而用c d t 就完 全可以。 d t 和c d t 的生成示意如图2 7 和图2 8 所示。它们拥有相同的点集p ，唯 一的区别在于图2 8 中多了一条约束边a 。可以看出，图2 8 中生成的两个三角形 是非法三角形，而图2 7 中的两个三角形不是。 图2 7 生成d t 图2 8 生成c d t 1 4 三维地质重构相关算法研究及应用 在过去的几十年中，d t 和c d t 的研究已经取得了很大的进展，许多算法已经 被广泛采用。这些算法主要分为三类( d t 和c d t 的分类相同) ： 基于分治策略的算法：这一类算法是典型的并行化算法，通常是将区域划 分成足够小的单元，然后并行处理。单元的尺寸要小到进一步的三角剖分 几乎不需要特别的策略。因此单元尺寸的控制是这类算法的一个关键环 节。与大多数并行算法相似，基于分治策略的算法大都采用树形数据结构。 最常见的是四叉树，也有采用八叉树的。主要有：c h e w ，1 9 8 7 口硼和r u p p e r t ， 1 9 9 3 1 4 】等。 扫描线( s w e e p - l i n e ) 算法：这一类算法是用一条虚拟的扫描线将区域分 为两部分，位于扫描线后面的部分是已经完成了三角割分的，丽位于扫描 线前面的部分则尚待处理。它一次将一个点或一条边加到扫描线后面的区 域边界上，同时移动扫描线。主要有f o r t u n e ，1 9 8 7 1 5 】和s h e w c h u k ，2 0 0 0 1 6 1 。 渐进算法：在d t 和c d t 的生成算法中，渐进算法是目前使用最广泛的 一种。它与前两种算法相比，主要的好处是算法简单，性能稳定，因此多 种简单数据结构可供选用。它一次加一个点或一条边到已有三角网中，故 而得其名。渐进算法又分为两种：逐步增长和逐步插入。前者在已有三角 网的外围添加点或边，使三角网向外扩展，后者在已有三角网的内部插入 点或边，使三角网完善。渐进算法的缺点是区域边界要到算法结束才能得 到，不易于并行化。主要有a n g l a d a , 1 9 9 7 1 7 1 、z a l i k ，2 0 0 3 1 8 1 和 d o m i t e r , 2 0 0 4 娜。 鉴于渐进算法的稳定性，本文的研究均基于这一类算法。 2 2 2 逐步增长算法 是一种最简单的三角网生成算法，算法的每一步都保证三角网是全局优化的。 给定点集p ，设栉为p 的点数。求p 的中心点作为起点，其余点按与中心点的距 离进行排序。取排序后的第一点，与中心点相连生成第一条边。以第一条边为起 点。求与它距离最近且不共线的另一个点，相连生成第一个三角形。判断该三角 形的外接圆中是否包含了其余点。如果包含，删除该三角形及新生成的两条边， 用被包含的点重复以上过程，直到生成的三角形满足空外接圆原则；否则，以该 三角形的三条边为起点，向外扩张再生成三个三角形。重复这一过程，直到所有 点都生成了三角形。算法如下： m e s h _ c r e a t e _ b y _ g r o w t h ( p o i n t 】) 逐步增长网格生成算法 1 f i n d c e n t e r p o i n t ( p o i n t ) ；，在点集p o i n t 中寻找中心点 第二章表面网格的生成及切割算法 2s o r t ( ) ；对其余点按其与中心点的距离排序a c c o r d i n g d i s t a n c ep o i n t 3g e tf i r s t l i n e ( p o i n t o ，p o i n t 1 ，f i n e ) ；生成第一条边 4 g e ta n o t h e rp o i n t ( p o i n t , l i n e ) ；t - 找与给定边不共线且距离最近的点 5g e te m p t y _ c i r c l e _ t r i a n g l e ( t r i ) ；，生成个满足空外接圆准则的三角形 6w h i l e ( 疗 0 ) d o x 寸其余的n 3 个点逐个处理 7 f o r j l i n e 们) ；寻找该边的另一点 9g e t _ e m p t y _ c i r c l e _ t r i a n g l e ( n e w t r i ) ；胜成新的三角形 1 0n n 一1 ： 11 u p d a t a _ w a i t _ t f i a n g l e _ q u e u e ( n e w t r i ) ；更新等待三角形队列 1 2 内层循环结束 1 3 仃i - - g e t _ n e x t _ w a i t _ t r i a