（应用数学专业论文）大规模散乱数据插值方法的研究.pdf

中文摘要 本文介绍了科学计算可视化的研究背景、发展现状殿应用领域，总结了近1 0 零塞鸯隈元翳掺生成方法懿磷突进震，壤述了霾兹磅究与应蔫爨然较蠢活跃豹遴 用网格生成方法，如映射法，基于栅格法，d e l a t m a y 三角割分方法，其中包括约 束d t 的边界饿发算法和薄冗的处理方法，推进波前法镣的最新研究进展。对当 蘩瓣主要矮究热轰，磐裁嚣瓣壤生或，其中包疆浃瓣滚强壹菝法；六瑟侮瓣摆垒 成，其中包括原型法、映射法和扫描法，蒸于栅格法，扩展的a f t 方法，以及 多子区域方法；网格生成并行算法等进行了阐述。 本文还霹d e l a u n a y 三角裁分方法送行了详鲴美傍戆搓透黟讨论，舟绍了 v o r o n i o 图和d e l a t m 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 三角剖分 方法，它首先把数据集划分为若干网格块，按照格网划分的逆序对每个网格块采 瘸蕤予毫逶瘦潮格翊分豹分密l 一合并葵法送 亍d e l a u n a y 三角割分，挺网格袭 d e l a t m 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 三角裁分弼旗翻努 a b s ，i i r a c t t h i sp a p e rp m s 啪t st h eb a c k g r o u n da n du t i l i t yo f c o m p u t a t i o n a lv i s u a l i z a t i o n ，a n d t h ea d v a n c e so f r e s e a r c hi nm e s hg e n e r a t i o nf o rf i n i t ee l e m e n t c o m p u t a t i o ni nl a s tt e n y e a r s 。t h ea d v a n c e do f t h ec o m m o nm e t h o d ss u c ha sm a p p i n gm e t h o d s ，g r i d - b a s e d m e t h o d s ( i n c l u d ef i n i t eq u a d t r e e o c t r e em e t h o d s ) ，d e l a u n a yt r a n g u l a t i o na n da f t m e t h o d sa r ee m p h a s i z e d t h em a i nr e s e a r c hf i e l d ss u c ha ss u r f a c em e s h i n g ( i n c l u d e ) ， a l l - h e xm e s h i n ga n dp a r a l l e lm e s hg e n e r a t i o na r ed i s c u s s e di nd e t a i l t h i sp a p e rp r e s e n t sa n dd i s c u s s e st h ed e l a u n a yt r i a n g u l a t i o nm e t h o d si nd e t a i l s ，s u c h a st h ed e f i n i t i o na n dt h ec h a r a c t e r so f t h ev o r o n i op i c t u r ea n dt h ed e l a t m a ym e t h o d s a n ds o m eu s e f u lc o n s t r u c t e dm e t h o d s o f d e l a u n a y t r i a n g u l a t i o nm e t h o d s ，s u c ha s ad e l a u n a yt r i a n g u l a t i o nm e t h o di sb r o u g h tf o r w a r do r i e n t e dm a s s i v ed a t a ，w h i c h b a s e do nt h e 蝣dp a t i t i o nm e t h o d i td i v i d e st h ed a t as e ti n t os o m e 垂矗t i l e s ， c o n s t r u c t sd e l a u n a yt r i a n g u l a t i o nf o re a c h 谢dt i l eb yd i v i d e a n d c o n q u e ra l g o r i t h m b a s e do ns e l f - a d a p t 鲥dp a r t i t i o n , a n ds m r es o m eu n a f f e c t e dt r i a n g l e s ，t h e nm e r g e s a d j a c e n td e l a u n a yt r i a n g u l a t i o n s 钯w h o l eo rw h o l e - l i k ed e l a u u a yt r i a n g u l a t i o n 。t h i s m e t h o dr e q u i r e sl o wc o m p u t e rh a r d w a r e ，f i t sf o rp a r a l l e lp r o c e s s i n g ，c a l lp r o c e s s d e l a t m a yt r i a n g u l a t i o no fm a s s i v ed a t a a tl a s t ，t h et r e n d so fm e s hg e n e r a t i o na r e p r e s e n t e db r i e f l y k e yw o r d s ：tc o m p u t a t i o n a lv i s u a l i s a t i o n , i n t e r p o l a t i o no fl a r g es c a l ed a t a , d e l a u n a yt r i a n g u l a t i o n ，g r i dp a t i t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 磷裁成果，除了文中特别加以标注和致谢之处外，论文中不包含其镶人已经发表 袋撰写过豹磷究成票，遣不镦余为获褥蒸鎏盘鲎或箕毽教育瓿褥秘学位或诞 书丽使用过的材料。与我一i 瓠z 作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：卿签字日期：彬咿岁年月，日 学位论文版权使用授权书 零学经论文终者完全了疑盘壅态壁毒关缣蘩、捷弱学谴论文翡囊定。 特授权叁蓬基茎可以将学位论文的众部或部分内容编入有关数据库进行检 綮，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向弱家有关部门或机构送交论文的复e p 件帮磁盘。 ( 保密静学位论文在解寮嚣适臻本授寝说秘) 学位论文作者箍名： i 矗嘲 导师签名： 嫦綦 熬掌墨裁：彬y 每，是哆霹签字矗嬲；彬年层哆匿 天津大学硕士学位论文第一章绪论 第一章绪论 1 1 科学计算可视化产生的背景 进入8 0 年代以后，随着计算机技术在各学科领域中的广泛应用，尤其是在 天体物理、地质、石油、气象、医学等领域，产生了大量的科学数据。以前对这 些数据只能采用人工方式进行处理和分析，或者使用绘图仪输出二维图形。人工 处理和分析数据十分繁杂，而且所需的处理和分析时间往往是计算时间的十几倍 甚至几十倍，因此不仅不能及时地得到有关计算结果的直观、形象的整体概念， 而且有可能丢失大量信息。随着计算机运算能力的飞速提高，在这些领域内所产 生的数据量越来越多。由于不能及时解释和利用这些数据，所产生的海量数据只 能通过存储设备存储起来，实际上对资源形成了极大的浪费。因而，科学计算结 果的后处理已经成为提高科学计算质量和效率的主要问题之一。 随着计算机技术的发展，图形图像技术得到了长足的发展，由于图形图像所 具有的不可比拟的优点，即信息量丰富、形象直观，所以它通常是人类认识世界 的重要手段。而且近年来随着计算机运用能力迅速提高，许多重要的图形学和图 像处理算法已经用硬件实现，显示速度得到了极大的提高，一些高档工作站已经 能达到实时显示。因此，利用计算机图形学及图像处理技术形象、直观地显示科 学计算的中间结果及最终结果并进行交互处理已经成为现实。 各领域对于科学计算可视化的需求终于促使了这门学科的产生，1 9 8 7 年2 月， 美国国家科学基金会在华盛顿召开了有关科学计算可视化的首次会议，会议认为 将图形图像技术应用于科学计算是一个全新的领域，并指出科学家们不仅需要分 析由计算机得出的计算数据，而且需要了解在计算过程中数据的变化，而这些都 需要借助于计算机图形学及图像处理技术。会议将这一涉及多个学科的领域定名 为“v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ”，从而正式给出了科学计算可视化的定 义、覆盖的领域以及近期与长期的研究方向，这些都标志着科学计算可视化这一 学科的正式诞生i 】j 。 因此，科学计算可视化的产生是当代科学技术飞速发展的结果，也是各学科 需求的必然结果，同时它也是一门交叉学科，研究的内容涉及了许多学科的诸多 专业知识，是一门与专业相关的应用性极强的学科。 天津大学硕士学位论文第一章绪论 1 2 科学计算可视化的研究内容 通常，科学计算可视化所面对的数据场可按数据场的各种几何属性或物理属 性分为：标量场、矢量场、张量场或规则场、不规则场等。由于可视化是面对数 据场的，因此，各种数据场所采用的可视化方法也有较大不同。而且由于可视化 的目的是为了探求数据场内部蕴涵的物理规雄、几何属性，因此，对于统一数据 场往往也有多种不同的可视化方法。通过多种方式来对同一数据场进行可视化也 有助于克服单一可视化方法产生弊端，从而可以全面对数据场的各种属性进行可 视化，这些特点使得可视化方法多种多样。而且经常对可视化的需求是实时或近 乎实时的，因此充足的硬件资源，甚至分布计算能力也是科学计算可视化的研究 内容之一。 因此在科学计算可视化过程涉及的多方面的技术问题可以总结如下： ( 1 】标量、矢量和张量的可视化 ( 2 ) 数据场和流场的动态显示 ( 3 ) 多变量数据场的显示 ( 4 1 并行或分布计算算法 其中可视化技术研究的一个重点领域是标量场可视化，特别是三维标量场可 视化技术。 对于分布在三维空间的体数据来说，有两类不同的可视化方法。 第一类方法称为面绘制方法，首先由三维数据场构造出中间几何图元( 如曲 面、平面、曲线等) ，然后再由传统的计算机图形学技术实现绘制。其中常见的 可视化技术有等值面显示、截面云图显示、空间断层等值线显示等技术，这些可 视化方法仍然是基于传统图形学技术的，可以在通用图形平台上实现，利用图形 硬件实现绘制、渲染加速，能达到较快的速度。此类绘制算法利用了传统图形学 的造型技术和绘制技术，因为面绘制要构造中间曲面或瞌线，必然要通过闽值或 极值等方法提取出等值曲面或曲线，这是一个分割的过程，分割过程基本是二者 取一的方法，分割点只能是对数据场属性的某种逼近。因此，许多三维数据场的 细节信息被丢失，生成结果的保真性较差。 第二类方法则完全不同，它放弃了传统图形学从三维数据场构造中间的方法 采用体绘制光照模型直接研究光线穿过三维数据场时的变化，从而得到最终的绘 制结果，由生成的图像表现出各类物理量的分布情况。这种算法能产生三维数据 场的整体图像，保留了数据场中的许多细节信息，结果的可信度大为增加。因此 场的整体图像，保留了数据场中的许多细节信息，结果的可信度大为增加。因此 天津大学硕士学位论文第一章绪论 它被称为体绘$ 0 ( v o l u m er e n d e r i n g ) 或者有时也被成为直接体绘$ 1 j ( d i r e c tv o l u m e r e n d e r i n g ) 。 1 3 科学计算可视化技术的发展现状 由于科学计算可视化研究内容和应用场合的多样性，当前科学计算可视化技 术的研究及应用十分活跃。科学计算可视化正在从早期的对数据场的后处理逐渐 向实时处理和交互控制发展。其中研究的重点包括：矢量场的实时动态显示算法， 如流场的实时动态显示算法；标量场的实时显示，如医学c t 数据场体绘制的实 时动态交互剖切、实时局部显示、实时动态旋转控制：图形绘制加速算法，如利 用图形工作站的性能实现数据场的动态显示；并行或分布式计算算法，如研究能 利用局域网多个计算机各自计算能力的并行或分布计算算法；数据场特征抽取， 提取数据场中感兴趣的特征属性等方面。 因此近年来，在发达国家研究方向中，科学计算可视化的研究工作已经将计 算机、光纤高速网、高性能图形工作站及虚拟现实四者结合起来，体现出这一领 域技术发展的重要方向【2 j 。 当前发达国家已经开发出了商品化的通用科学计算可视化系统以及一些专 用的科学计算可视化软件，甚至开发出了面向对象的可视化编程语言，在这些系 统中集成了计算机图形学和科学计算可视化的基本算法，因此能直接利用软件对 数据场进行处理，并且这些软件允许用户根据各自的要求进行二次开发，得到特 殊用途的可视化应用软件。此类软件由以下几类。 i 通用的科学可视化系统 比较著名的有美国s t a r d e n t 计算机公司开发的a v s ( a p p l i e a t i o nv i s u a l i z a t i o n s y s t e m ) ，s g i 公司开发的i r i se x p l o r e r 以及俄亥俄超级计算中心开发的a p e 系 统等。 由于科学计算可视化的应用领域非常广泛，输入数据的大小和格式各不相同， 对输出图像的要求也千差万别，而且科学计算工作者往往不熟悉计算机软件的开 发，因此，这些通用的可视化软件一般采用开放式体系结构，使系统功能很容易 扩展，以满足各种不同的可视化应用领域的需求。 2 专用的科学计算可视化软件 当前许多c t 和m r i 设备生产商同时也提供了显示三维医学图像的商品化系 统，如美国通用电器公司生产的螺旋c t 扫描设备均附有基于图形工作站的医学 天津大学硕士学位论文第一章绪论 图像可视化系统，可以将多层c t 或m r i 图像输入计算机以后，此系统可以沿x 、 y 、z 三个方向逐帧显示输入图像，可以用不同方法构造三维形体，可以对三维 图像进行逐层剥离或进行任意割切以观看内部结构，同时也可以对所构造的三维 形体通过对鼠标的移动作实时的平移、旋转、缩放，此系统通常需要计算速度很 高、存储容量很大的计算机系统。 此外还有用于气象数据、计算流体力学等场合的可视化软件。 3 面向对象的可视化编程语言 此技术吸收了当前通用编程语言中先进的面向对象的思想，将通用数学运 算、数据接口、数据模型、图形显示分别以对象的形式提供给用户，语言本身高 度集成了可视化技术中常用的各项数据处理技术、图形显示技术，甚至此类语言 还提供了高度独立的可视化编程环境，提供了丰富的、独立的界面制作工具，从 而使利用此类语言制作的可视化软件不再具有平台相关性。此类典型的编程语言 如i d l ( i n t e r a e t i v ed a t al a n g u a g e ) ，此语言在许多场合得到了应用，而且使用此 语言进行专用可视化软件的编制工作量也大为减少。 1 4 科学计算可视化技术的应用领域 当前可视化技术得到了广泛的应用，几乎涉及自然科学及工程技术的一切领 域。其中的主要应用领域为医学、地质勘探、气象学、分子模型构造、计算流体 力学和有限元分析等。 1 医学 虽然随着科学技术的发展，计算机断层扫描( c t ) 及核磁共振图像己经广 泛应用于疾病的诊断，但是，这些图像只能提供人体内部的二维图像。医生只能 凭经验由多幅二维图像去估计病灶的大小及形状，以及病灶与其周围组织的三维 几何关系，这就给治疗带来了困难。 科学计算可视化技术可以在计算机内由一系列二维图像重构出三维形体，从 而指导医生的手术或配合其他治疗。 2 石油勘探 在石油勘探过程中，通常通过地震勘探了解大范围内的地质结构，发现可能 的含油构造，并通过测井数据了解局部区域的地层构造，探明油藏位置及其分布， 估计蕴藏量及勘探价值。由于地震数据及测井数据的数据量及其庞大，而且高度 分布不均匀，因而很难直接从数据作出分析。利用可视化技术可以从大量的地震 天津大学硕士学位论文 第一章绪论 数据和测井数据中构造出感兴趣的等值面、等值线，显示其分布范围及变化趋势， 并用不同颜色显示出来，从而使专业人员对原始数据做出正确的解释，得到关于 矿藏的一系列重要信息。这样可以减少无效井位，节约资金，从而大大提高工作 效率。 3 气象学 当前超级计算机在气象预报的过程中起着关键性的作用，气象预报的准确性 也主要依赖对超级计算机所产生的海量数据的正确分析。对于这些海量数据，只 使用人力是根本无法完成分析的，因此，使用可视化技术可以将大量的数据转化 为图像，在屏幕上显示出某一时刻的等压面、等温面、位涡，云层的位置及运动、 暴风雨的位置及其强度、风力的大小及方向等，从而使预报人员能对未来的天气 做出正确的分析和预测。 4 计算流体力学 在飞机、汽车、船舶等的外形设计中都必须考虑在气体、液体高速运动的环 境中能否正常工作，并且要使阻力最小。过去此过程通常是在风洞中作模拟实验， 根据实验结果，修改设计。当前，已经可以在计算机内部建立飞机等的几何模型， 进行流体力学的模拟计算，目前，利用超级计算机已经可以对复杂几何模型进行 流体力学的模拟计算，但是产生的数据量十分庞大，于是利用可视化技术对流体 计算结果进行处理，将结果数据动态显示出来，从而可以得到流体场各种属性的 直观显示。 5 有限元分析 在有限元分析中，需要应用可视化技术实现形体的网格剖分及有限元结果数 据的图形图像显示，并根据分析结果实现网格剖分的优化，使得计算结果更加可 行和精确。 此外，科学计算可视化技术还在天体物理、数学等领域内得到了广泛的应用。 1 5 论文内容安排 本章介绍了科学计算可视化的研究背景、发展现状及应用领域，第二章介绍 当前有限元网格生成的几个主要研究方向，第三章介绍有限元网格生成的通用方 法。第四章具体介绍和讨论了d e l a u n a y 三角剖分的方法，并重点介绍了一种基 于均匀网格的d e l a u n a y 三角剖分算法。第五章具体介绍了一种新的基于网格划 分的d e l 姗a y 三角剖分的方法在内存空间的占用以及计算速度上都有很大改进。 天津大学硕士学位论文第二章有限元网格生成的通用方法 第二章有限元网格生成的通用方法 有限元网格生成是工程科学与计算科学相交叉的一个重要研究领域，在经历 了3 0 多年发展后的今天依然十分活跃。一方面，有限元法已成为一种能够有效 地求解各类工程和科学计算问题的通用数值分析方法；另一方面，计算机硬件运 算能力的不断提高也容许人们对工程和科学计算的规模、复杂度、效率、精度等 方面提出更高的要求。作为有限元走向工程应用的桥梁的有限元网格生成由此获 得了源源不断的外在动力。同时，有限元网格生成算法研究中的某些难点问题始 终未能获得真正意义上的解决，它们的研究解决对计算几何与计算数学都具有重 要的理论价值。 有限元网格生成方法研究领域已取得许多重要成果，形成了独特的方法论体 系，提出了许多有效的算法并研制出一些成功的工程化软件产品。许多学者对有 限元网格生成方法研究进行了概括和总结，如t h a c k c r ，h o l ek ，s h e p h a r d ， b a k e r ，g e o r g e 和胡思球等对7 0 - - 9 0 年代初期该领域的研究进展作了系统的回顾 与阐述；吕军，魏红宁和b 1 a e k e r 等对某些重要分支领域的研究进展进行了评述。 近1 0 年来，有限元网格生成方法研究有两个显著特点：( 1 ) 与其它研究领域一样，经历 了一个进化过程，一些方法的研究与应用出现停滞，而另外一些方法在不断地深入、完善和 发展，成为适应性强、应用范围广泛的通用方法：( 2 ) 领域和主题在不断扩展和深入，研究 重点由二维平面问题转移到三维曲面和三维实体问题，从三角形四面体网格自动生成转移 到四边形六面体网格自动生成，在并行网格生成、自适应网格生成、贴体坐标网格生成、 各向异性网格生成等方面亦取得许多重要进展。 2 1 映射法 映射法既是结构化网格生成方法，又是非结构化网格生成方法。它的基本步 骤是：通过适当的映射函数将待副分物理域映射到参数空间中形成规则参数域； 对规则参数域进行网格剖分；将参数域的网格反向映射回物理空间，从而得到物 理域的有限元网格。映射法可分为保角映射法( c o n f o n n a l i n 印p i n g m e m o d ) m 3 8 1 、 基于偏微分方程法( d d e b a s e d m e t h o d ) 3 9 , 4 0 ，以及代数插值法( a l g e b r a i c 天津大学硕士学位论文第二章有限元网格生成的通用方法 i n t e r p o l a t i o nm e t h o d ) 4 1 , 4 2 三大类。 保角映射法能够处理多于4 条边界的单连域问题，但难于控制单元形状和单 元密度，且不能直接应用于三维问题。t h o m p s o n 等【4 3 卅】首次提出的基于偏微分 方程法，通过数值求解偏微分方程而得到参数空间与物理空间之间的映射关 系基于偏微分方程法可细分为椭圆型、抛物线型和双曲线型三大类，其中最常 用的是椭圆型p o i s s o n 方程和l a p l a c e 方程网格生成方法【4 ”。 基于偏微分方程法主要应用于c f d ( e o m p u t a t i o n a l f l u i dd y n a m i c s ) 领域的贴体 坐标( b o t m d m - y - f i t t e dc o o r d i n a t e ) 霞j 格生成问题，目前仍在深入研究和发展中。 代数插值法是一种应用相当广泛的网格生成方法，它通过代数插值来描述参 数空间与物理空间之间的映射关系，其中最重要的一个类别是超限插值 ( t r a n s f i n i t ei n t e r p o l a t i o n ) t 4 7 ，z i e n k i e w i c z 提出的等参映射就是超限插值的种特 殊形式。超限插值既可适应特殊的区域边界形状，又可控制所生成单元的形状和 密度，成为代数插值网格生成的一个标准方法。 映射法的优点是算法简单、速度快、单元质量好、密度可控制，它既可生成 结构化网格又可生成非结构化网格；既可生成四边形单元网格又可生成六面体单 元网格，可用于曲面网格生成，可与形状优化算法集成等。因此，映射法在众多 的商业有限元分析软件中占有重要的地位。 映射法一般可直接处理单连通域问题，但对于复杂多连通域问题，需要首先 用手工或自动方法将待剖分域分解成几何形状规则的可映射子区域，然后在每个 子区域内应用映射法。然而在实践中仍有几个难点需要克服： ( 1 ) 如何自动地将复杂的不可映射的待剖分域分解成简单的可映射的子区域； ( 2 ) 如何满足某些物理问题中对网格疏密过渡的要求； ( 3 ) 如何满足子区域之间的网格相容性要求。 子区域分解( 特别是三维实体) 是应用映射法生成有限元网格的最大困难， 不少学者对此提出了多种解决方法0 5 ”+ ，其中中轴线法和中面法具有代表性。 t a m 与a r m s t r o n g 首次提出可用中轴线法将二维待剖分域分解为简单子区域，随 后p r i c e 与a r m s t r o n g 等”2 7 提出用中面法将三维待剖分域分解成简单子区域。 由于中轴线法中面法得到的子区域一般具有可映射特性，因此可以将映射法与 中轴线法中面法相结合形成复杂域全自动网格生成方法。目前，二维问题的中 轴线提取算法已经相当成熟，而三维问题的中面提取算法还存在一些问题，特别 是几何适应能力问题。 对于网格疏密过渡问题和网格相容性问题，李华与程耿东等提出了一种在正 7 天津大学硕士学位论文 第二章有限元网格生成的通用方法 方形子区域上实现网格在两个坐标方向均能过渡的全四边形单元生成方法 模板法将该方法和映射法结合可以有效地在两个坐标方向上实现网格疏密过渡 以及对局部点或局部区域进行网格加密处理，而对没有网格疏密过渡要求的区域 可以生成和映射法一致的结构化网格。在此基础上，李华和程耿东又提出了三维 组合式模板，实现了立方体子区域上的在三个坐标方向上均能过渡的全六面体单 元生成方法；并通过采用线性整数目标规划技术求解模板组合参数，解决了子区 域与子区域之间的网格相容性问题。 2 2 基于栅格法 基于栅格法( g r i d b a s e da p p r o a c h ) 的基本流程：首先用一组不相交的尺寸相同 或不同的栅格( c e l l s ) 覆盖在目标区域上面，保留完全或部分落在目标区域之内的 栅格，删除完全落在目标区域之外的栅格；然后对与物体边界相交的栅格进行调 整、剪裁、再分解等操作，使其更准确地逼近目标区域；最后对内部栅格和边界 栅格( 特别是边界栅格) 进行栅格级的网格剖分，进而得到整个目标区域的有限 元网格。 基于栅格法又可分为正则栅格法( r e g u l a r 鲥d m e t l l o ( 1 ) 和有限四( 八) 叉树法 ( f i n i t eq u a d t r e e o c t r e em e t h o d s ) 两大类。正则栅格法与有限四( 八) 叉树法在算法 的总体流程上基本一致，它们之间的最大区别在于正则栅格法采用尺寸相同的正 则栅格覆盖目标区域，而有限四( 八) 叉树法采用基于四( 八) 叉树数据结构的 可递归细分的变尺寸栅格来覆盖t f l 标区域。与正则栅格法相比，有限四( 八) 叉 树法能够更好地协调边界逼近精度与生成单元数量之间的平衡，因此应用更为广 泛。 y e r r y 和s h a p h a r d 首先将用于近似表达几何对象的四( 八) 叉树法空间分解 法引入到网格剖分领域，其后又有许多学者对该方法进行了完善和发展，形成了 有限四( 八) 叉树方法。有限四( 八) 叉树方法适用予复杂二维和三维域网格生 成，几何适应性强，网格密度可控制，且算法效率较高( 时间复杂度为o ( n l o g n ) ， 实际观察接近于0 0 田，其中n 为生成单元总数) 。但该方法也存在如生成网格 与所选择的初始栅格及其取向有关、目标域边界处单元质量较差等严重缺点。 有限四( 八) 叉树方法的主要步骤包括：叉树的构建，叉树的平衡，交点过 滤，内部栅格与边界栅格的相容网格剖分，网格优化等。其中，内部栅格与边界 栅格的相容网格剖分在实现上具有相当的难度。例如，对于三维内部栅格的网格 天津大学硕士学位论文 第二章有限元网格生成的通用方法 剖分问题，如果相邻八分区( o c t e t ) 最多相差一个级别的划分水平，那么内部栅格 的拓扑形式就存在4 0 9 6 种可能性，即使考虑到对称与旋转特性也需要建? r 7 8 种模 板。为了简化算法，y e r r y 等提出可将内部栅格分解为6 个锥体，然后再将锥体刻 分成所需单元，但是该方法生成单元太多，且质量较差。s c h r o e d e r 等将d e l a u n a y 方法引入到有限四( 八) 叉树方法中，解决内部栅格与边界栅格的相容网格剖分 问题，一定程度上降低了程序实现的复杂度并提高了边界网格质量m c m o r r i s 等提出了将八叉树法与推进网阵法相结合的生成曲面网格和三维实体网格的新 方法，成功地应用于计算流体动力学中的网格生成问题。 与推进波前法和d e l a u n a y 三角化法相比，有限四( 八) 叉树方法在三角形 四面体网格生成方面并不具有优势但是，有限四( 八) 叉树方法也有自己独特 的内在品质，因而在相当广泛的领域获得了成功的应用s c h n e i d e r s 等提出基于 八叉树法的全六面体网格生成方法，值得注意的是，该方法将父栅格划分为2 7 个子栅格，而非标准的8 个子栅格。f r e y 等指出，以往的网格生成方法只是使用 了四( 八) 叉树提供的邻接空间信息( 用于增强搜索效率) ，而没有作为控制空 间信息( 用于控制单元尺寸) 。事实上，在自适应有限元分析中可以通过调整叉 树结构使得修正后的栅格尺寸与根据误差估算得到的期望的单元大小相匹配。 s a x e n a 等。”将四( 八) 叉树法作为背景栅格来驱动并行网格生成，l o h n e r 等提出 的并行化算法也采用八叉树为框架。 2 3d e l a u n a y 三角剖分方法 d e l a u n a y 三角剖分( 简称d t ) 是目前最流行的通用的全自动网格生成方法 之一。d t 有两个重要特性：最大一最小角特性和空外接圆特性。d t 的最大一 最小角特性使它在二维情况下自动地避免了生成小内角的长薄单元，因此特别适 用于有限元网格生成。所谓空外接圆特性，就是d t 中的每个三角形单元或四面 体单元的外接圆( 二维) 或外接球( 三维) 都不包含其它节点，b o w y e r w a t s o n 算法正是利用了这一特性。 三维b o w y e r - w a t s o n 算法的基本步骤：首先定义一个包含所有节点的初始网 格，最简单的情形是单个四面体；向网格中插入一个节点，找出其外接球包含此 节点的所有四面体单元，删除这些单元形成一个包含插入节点的空腔( c a v i t y ) ；将 该插入节点与空腔的每个表面相连，形成新的四面体网格；重复进行上述的节点 插入过程，直到全部节点插入完毕。 天津大学硕士学位论文第二章有限元网格生成的通用方法 d e l a u n a y 三角剖分算法的计算效率与具体的实现相关。大体上可将d t 算法 分为三大类：分治算法，逐点插入法和三角网生长法。b o w y e r w a t s o n 算法是一 种典型的逐点插入法，其时间复杂度为o f n ”2 ) ，采用四( 八) 叉树数据结构的 b o w y e r - w a t s o n 算法可达到o ( n l o g n ) ，分治算法的时间复杂度为0 ( n l o g n ) ，三 角网生长法的时间复杂度为o ( n 3 2 ) ，其中n 为生成单元总数。 经典d t 技术已经相当成熟，近年来的研究重点是约束d t 的边界恢复算法， 以及如何克服b o w y e r - w a t s o n 算法退化现象所产生的薄元( s l i v e r e l e m e n t ) 问题1 4 9 。 2 3 1 约束d t 的边界恢复算法 由于d e l a t m a y 三角割分算法仅对凸域的剖分有效，对于非凸域则不能保证其 边界的完整性，因此对非凸域应用d e l a u n a y 三角剖分算法时必须引入一个恢复 边界的步骤。恢复了边界完整性的三角剖分并不能严格满足d e l a t m a y 准则，因 此称为约束d t 。 二维问题的边界恢复比较简单，并且有明确的理论保证边界恢复结果是收敛 的一种边界恢复算法是由g e o r g e 等提出的边交换法1 ，该方法基于一个简单 的原理：相邻两个三角形所构成的四边形的两个对角线可以互换而不影响这两个 三角形与相邻三角形的相容关系。这样，就可以通过一系列的四边形对角线的交 换来恢复目标域边界的完整性。另一种常用的二维边界恢复算法是最近点连线 法，该方法首先找到与已经丢失的边界线段相交的所有三角形，这样可以得到一 组互相邻接的三角形，然后将这些三角形所代表的单元删除，仅留下节点；从距 离丢失的边界线段最近的节点开始，逐一将节点与丢失的边界线段或其它新生成 的线段重新生成三角形单元；这样循环迭代，直到所有节点使用完毕。 三维问题的边界恢复过程要比二维问题复杂得多，在二维问题中行之有效的 边界恢复算法不能直接扩展到三维问题中。三维域的边界由系列三角形面片组 成，其边界恢复基本上可分成两步： ( 1 ) 恢复边界的边三角形面片的边； ( 2 ) 恢复边界的面三角形面片本身。 由于三角形边的存在有时并不能保证此三角形面在剖分结果中存在，所以f 2 ) 也是必需的。 一种比较常用的三维问题边界恢复算法称为装订法。这种方法首先恢复边界 的边，当边界边与其它单元相交时则在边界边上插入节点，边界边即可被恢复。 然后恢复边界的三角形面，思路与此类似，也是在三角形面上插入节点来恢复边 天津大学硕士学位论文第二章有限元网格生成的通用方法 界面。这种边界恢复算法是有效的，但应注意到该算法在边界边以及边界面上插 入了新的节点，初始边界三角形也被分解为多个小三角形，因而新的边界并不是 严格意义上的原有边界。 另一种边界恢复算法被称为分治算法，这种算法不是在实体剖分完成之后恢 复边界，而是在实体剖分之前将问题域划分成若干个凸域，对每一个凸域进行 d e l a u n a y 三角剖分时就可以保证原问题域边界的完整性。当然，凸域分割增加了 额外的工作量。 2 3 2 薄元的处理方法 d e l a u n a y 三角剖分算法在二维问题中不仅可以保证剖分的收敛，而且也能够 保证剖分结果是最优的。但在三维情况下，这些性质都不能得到保证，其中一个 比较典型的问题是薄元问题。所谓薄元是指一个四面体的4 个节点几乎共面，但 这个四面体仍然符合d e l a u n a y 三角剖分准则。这种单元的质量很差，可能导致 有限元计算结果的严重误差，因而必须加以处理。 目前有两种常用的薄元处理方法： ( 1 ) 节点抖动法。该方法试图将一个薄元的一个节点沿着某个方向移动，以增 加薄元的“厚度”、提高单元质量，但抖动算法在实际应用中有许多困难，而且 在某些情况下将会失效； ( 2 ) 薄元分解法。该方法基于这样一个事实，即薄元一般都相当于比较薄的面 片，可以在面片的形心处插入一个新的节点，该节点可阻同与此薄元邻接的4 个 单元形成4 个新的单元，用来代替薄元，实践证明这种方法实施简单，行之有效。 2 4 推进波前法 经过近年来的发展，推进波前法( a d v a n c i n g , f r o n tt e c h n i q u e ，a f t ) i5 0 已成为 目前最流行的通用的全自动网格生成方法之一。该方法的提出应归功于l o h n e r 和l o 。a f t 方法没有d e l a t m a y 三角剖分算法那样成熟的理论依据，在很多情形 下a f t 方法是靠经验解决问题，但是这并不妨碍它的成功应用。a f t 算法的时 间复杂度为o ( n l o g n ) ，与d e l a u n a y 三角化算法、有限四( 八) 叉树法相当，但 其生成单元的质量是三者中最好的。 a f t 方法的基本流程是：首先离散待割分域的边界，二维待剖分域的边界离 散后是首尾相连的线段的集合，三维待剖分域的边界离散后是拓扑相容的三角形 天津大学硕士学位论文第二章有限元网格生成的通用方法 面片的集合，这种离散后的域边界称为前沿；然后从前沿开始，依次插入一个节 点，并连接生成一个新的单元；更新前沿，这样前沿即可向待剖分域的内部推 进这种插入节点、生成新单元、更新前沿的过程循环进行，当前沿为空时表明 整个域剖分结束。 a f t 方法的特点之一是能够在生成节点的同时生成单元，这样就可以在生成 节点时对节点的位置加以控制，从而控制单元形状、尺寸以达到质量控制、局部 加密及网格过渡的要求。大量文献提出了各种不同的节点生成方法及单元生成方 法。 a f t 方法的特点之二是在生成新单元时需要进行大量的相交判断、包含判 断，以及为了保证单元的质量而进行的距离判断。相交判断包括线段之间的相交 判断，线段与三角形面片之间的相交判断；包含判断主要指单元是否包含前沿节 点的判断；距离判断包括线段与线段的距离，线段与前沿节点的距离以及线段与 三角形面片的距离。上述判断的计算，在整个a f t 方法实施过程中耗用了大约 8 0 的机时。因此，在实施a f t 方法对，务必精心设计数据结构，尽量减少需 要进行判断的数量，以提高a f t 方法的效率。其中比较有效的数据结构是 a l t e m a t i v e d i g i t a l t r e e 和h e a p l i s t ，实践证明，这两种数据结构的联合应用可以显 著地提高a f t 方法的计算效率。 a f t 方法存在一个收敛性问题。所谓收敛性问题是指在三维问题的某些特殊 情况下，一个多面体内部如果不插入额外的节点，则该多面体不能够被剖分成几 个四面体的集合，一个典型的例子是s c h o n h a r d t 多面体。a f t 方法的收敛性问 题有其特殊性，因此有些特殊问题并不能够通过插入节点而得到解决，必须采取 其它方法加以解决。这里给出一个比较有效的解决方法：一般来讲，采用a f t 方法剖分网格到最后遇到的不收敛的区域不止一个，对于每一个区域生成一个包 含此区域的所有节点的立方体，然后将那些有节点在此立方体中存在的单元删 除，这样便形成一个新的多面体，对于这个新的多面体重新生成单元。对每一个 不收敛区域都按照这个方法重新生成单元，经过几次循环迭代以后，结果一般都 是收敛的。 本章介绍了有限元网格生成的通用方法：映射法，基于栅格法，d e l a t m a y 三 角剖分方法，其中包括约束d t 的边界恢复算法和薄元的处理方法，推进波前法。 下一章将介绍当前有限元网格生成的几个主要研究方向 天津大学硕士学位论文第三章当前有限元网格生成的几个主要研究方向 第三章当前有限元网格生成的几个主要研究方向 3 1 曲面网格生成 曲面网格生成是有限元网格生成技术中的一个重要研究领域，它的应用相当 广泛。工程结构中常用的薄壳结构，如球罐、压力容器、冷凝塔、飞机蒙皮、汽 车外完等，都是由圆柱、圆锥、球面等规则曲面以及b 6 z i e r ，n u r b s 等自由曲 面组合而成的。此外，曲面的网格划分结果往往是三维实体网格生成方法的输入 数据，是三维实体网格划分的前提和基础，其质量的优劣对后续生成的三维实体 网格的质量有很大影响。目前，曲面网格划分方法大致可分为映射法和直接法两 类。 3 1 1 映射法 映射法首先在曲面的二维参数空间中利用平面域网格生成方法进行网格剖 分，然后将剖分结果反向映射回物理空间形成曲面网格。曲面网格剖分的映射法 也称为参数空间法。平面域网格生成方法已经相当成熟，可生成质量良好的三角 形、四边形单元网格。但是，参数空间上单元形状良好的网格映射到物理空间后 往往会出现畸变。许多学者针对此问题对传统映射法进行了不懈的改进，使映射 法的曲面适应能力得到了增强。 z h e n g 等 3 - 4 在曲面的参数空间中引入了延展因子概念。通过计算曲面边界 曲线的离散线段在物理空间和参数空间的长度比值，来估算曲面边界曲线上各离 散点的延展因子；然后利用延展因子对原始参数空间作比例变换，使曲面在参数 空间的映射结果( 闭合平面域) 大体保持各向同性，从而消除或减弱由映射函数 引起的畸变。但该方法不能适用于内部与边界的畸变状态差别较大的曲面。 c h e n 等f s 对d e l a u n a y 三角化方法的适应性进行改进，用外接椭圆准则替代 传统的外接圆准则，保证了参数空间的d e l a u n a y 剖分结果( 形状可能比较差) 在映射到物理空间后具有良好的几何性态。c h e n 方法对曲面边界和内部的映射 畸变给出了统一的计算方法，克服了z h e n g 方法的缺陷，在实践中取得了成功。 熊英等 6 】在c h e n 方法的基础上提出了新的椭圆构造算法以及椭圆圆心的定位方 天津大学硕士学位论文第三章当前有限元网格生成的几个主要研究方向 法，并解决了求解椭圆效率不高的问题。 d a n i e l 等【7 】对a f t 方法进行了适应性改进，使其节点插入规则和单元连接规 则与各向异性的剖分控制函数保持一致，从而保证了剖分结果在物理空间的几何 性态。d a n i e l 方法的优势主要有两点： ( 1 ) 用初始背景网格作为建立剖分控制函数的依据，较c h e r t 方法能更为准确 地描绘映射畸变的程度； ( 2 ) 用改进的a f t 方法作为二维剖分方法，使节点的生成和连接都考虑了映 射畸变的影响，而改进的d e l a u n a y 方法只是在节点连接过程中考虑映射畸变的 影响。 c u i l l i e r e t 8 】从曲面的参数方程出发，提出了一套度量映射畸变的新方法。通过 数学推导建立了一套曲面相关的代数方程，用来描述由映射引发的畸变。与 d a n i e l 的方法相类似，在二维网格划分上c u i l l i e r e 使用a f t 方法，并也对其进 行了适应性的改进。c u i l l i e r e 方法的优点是给出了对映射畸变的解析形式描述方 法，对映射畸变的度量更为精确。但在通用性