（计算机应用技术专业论文）基于fgt的曲面三角网格自动生成软件系统.pdf

摘要 本文通过阅读大量文献，对曲面三角网格自动生成各种方法进行比较，得出 了一种曲面三角网格自动生成的方法，该方法以直接法为基础，即直接在曲面上 进行三角网格划分，利用网格向前推进生成技术，考虑到工程实际复杂曲面多由 b 样条曲面拼接而成，故本文以单张b 样条曲面作为曲面网格生成对象，对b 样条曲面进行三角形网格自动牛成。基于网格向前推进生成技术，给出所有可能 的几何拓扑特征下生成三角形的算法；采用求解非线性方程组的b r o y d e n 方法， 在曲面网格自动生成过程中对三角形进行求解，该方法己知三角形两点有效地找 到第三个点：对b 样条曲面三角网格自动生成进行数学分析、原理研究、编程 与实验设计，同时对曲面三角网格生成过程中的一些特殊情况进行处理；利用直 接法和网格向前推进生成技术，编制一个基于f g t 的曲面三角网格自动生成软 件系统，该系统对不同控制点下的各种形态的曲面进行三角形网格全自动生成， 验证了算法及程序的有效性。 关键字推进波前法直接法b 样条曲面曲面网格三角形网格 a b s t r a c t c o m p a n n gv a r i o u sm e t h o d so ft h ec u r v e ds u r f a c et r i a n g l em e s ha u t o m a t i c g e n e r a t i o nt h r o u g hr e a d i n gt h em a s s i v ep a p e r s ，i tp r o d u c e sam e t h o do ft h ec u e d s u r f a c et r i a n g l em e s ha u t o m a t i cg e n e r a t i o n t h i sm e t h o dw i t hd i r e c t a p p r o a c hf o r f o u n d a t i o n ，n a m e l yt h ec u r v e ds u r f a c et r i a n g l em e s ha u t o m a t i cg e n e r a t i o ni sd i r e c tt 0 c a r r yo nm t h ep h y s i c ss p a c eo ft h ec u r v e d s u r f a c e ，m a k i n gu s eo ft h em c s ht o a d v a n c i n gf r o n tg e n e r a t i o nt e c h n i q u ea tt h es a m et i m e ，t a k i n gi n t oa o c o u n tt l l e p r o j e c ta c t u a lc o m p l e xc u r v e ds u r f a c ep r o d u c e db yt h ebc u r v e ds u r f a c e s 舶m s p l i c i n g , t h ep a p e rc h o o s i n gt h es i n g l es h e e tbc u r v e ds u r f a c ea sac u i v e ds u i j a c e m e s hg e n e r a t i o nt a r g e t ，c a r r i e so nt h e t r i a n g l em e s ht obc u r v e ds u d 涵c ea n dv a r i o u s p a r 锄e t e rc u r v e ds u r f a c ea u t o m a t i cg e n e r a t i o n f o rm a k i n gu s eo ff g t m e t h o da i l d g e n e r a t l n gt h ec u r v e ds u r f a c et r i a n g l em e s h ，t h ea l g o r i t h mw i t ht h a ti tg e n e r a t e st h e t r i a n g l e st oa l lp o s s i b l ec a s e si ng e o m e t r i ct o p o l o g yf e a t u r e sw e r ec a 玎i e do nt h e r e s e a r c h i n g u s i n gt h es o l u t i o nn o n l i n e a r c a l lf i n dt h et h i r dp o i n te f f e c t i v e l yi fw e e q u a t i o n sb r o y d e nm e t h o dw i t hw h i c hw e k n o wt r i a n g l e st w op o i n t s ，c a r r i e so nt h e s 0 1 u t i o no ft h et r i a n g l ei nt h ec u r v e ds u r f a c eg r i da u t o m a t i cg e n e r a t i o n p r o c e s s t h i s t e x tw a sb o r nt oc a r r yo nt h em a t h e m a t i c a la n a l y s i s ，t h et h e o r ya b o u t t h er e s e a r c h t h e p r o g r a m m m g t h ee x p e r i m e n t a ld e s i g nt ot h ee q u i l a t e r a lt r i a n g l em e s hg e n e r a t i o no fb c u r v e ds u r f a c er e s e a r c ha n dd e a lw i t ht h et r i a n g l em e s hg e n e r a t i o np r o c e s s ss o m e p e c u l i a rc a s e sa tt h es a m et i m e m a k i n gu s eo ft h et e x t u a lm e t h o d ，m a ：k ei n t ot h e s o t t w a r es y s t e mo ft h ec u r v e ds u r f a c et r i a n g l em e s ha u t o m a t i cg e n e r a t i o na n d u s i n g t h i ss y s t e mt ot h ec u r v e ds u r f a c eo ft h e g e n e r a t i o nc a r r y so nt h ee x p e r i m e n t d i f f e r e n tc o n t r o lp o i n t sm e s ht h ea u t o m a t i c l 沁yw o r d s ：a d v a n c i n gf r o n tg e n e r a t i o nt e c h n i q u e d i r e c ta p p r o a e l l bc u r v e ds u r f a c et h ec u r v e ds u r f a c em e s h t h e t r i a n g l em e s h 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，基于f g t 的曲面三角网格自动生成软 件系统是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经 注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者签名：纵啤年三月堕日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使 用规定 ，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学位论文 全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文。 作者豁：箍斟蹲年立月丝日 师签名：趟呼吐月攀日 第一章绪论 有限元网格生成是工程科学与计算科学相交叉的一个重要研究领域，在经历了几 十年发展后的今天依然十分活跃。一方面，有限元法已成为一种能够有效地求解各类工 程和科学计算问题的通用数值分析方法；另一方面，计算机硬件运算能力的不断提高 也容许人们对工程和科学计算的规模、复杂度、效率、精度等方面提出更高的要求。 作为有限元走向工程应用的桥梁的有限元网格生成由此获得了源源不断的外在动力。 首先，曲面网格生成是有限元网格生成技术中的一个重要研究领域：其次，曲面网格 生成的研究作为计算机的前沿领域，也是非常活跃、并富有挑战的研究课题，其研究 将涉及到计算数学、计算机图形学、数据结构等多门学科领域：最后，有限元网格的 生成也是个难题。在以往的工作中，必须花费大量的时间和精力去建立分析模型，产 生一个分析模型总是要经过几何模型简化、网格划分、载荷和约束的定义、材料定义 等步骤。而这种模型抽象化的过程常常要依赖于有经验的分析人员，但是有限元网格 的生成都是在手工或半自动中进行的，决大部分时间都花费在网格生成等繁重、冗长 的数据准备上，并且数据可靠性差，严重阻碍有限元的推广及应用。可以说，有限元 网格生成问题是阻碍有限元法迅速发展的“瓶颈”之一，因此，近年来关于有限元网 格生成算法的研究非常热门。据此本文对此课题进行了深入的探讨，并且在曲面网格 划分方面，由于工程中许多自由曲面多数由b 样条曲面插值或拟合而生成的，故本文 用单张b 样条曲面作为曲面网格生成对象：本文以直接法为基础，对不同控制点下的 各种形态的三角网格自动生成问题进行了研究。 本章主要介绍曲面网格自动生成技术的发展现状及趋势，以及本文研究的目的和 主要内容。 1 1 曲面网格自动生成技术的发展现状及趋势 1 , 1 1 曲面网格自动生成技术发展现状 曲面网格自动生成是有限元解决复杂工程实际问题的日订提。随着计算机辅助设计 和制造技术的同趋成熟，设计人员迫切需要一种对所做的设计进行精确评价和分析的 工具，而不再仅仅依靠以往积累的经验和知识去估计。鉴于这种目的。人们希望将工 程领域罩广泛应用的有限元分析方法与c a d 技术相集成，共同实现“设计评价一 一再设计任务的自动化，以提高设计的精确程度和效率。 c a d 与有限元分析技术的集成存在的主要问题 第一：如何实现从几何模型到有限元分析模型的自动转换。 第二：有限元网格的生成是个难题。在以往的工作中，必须花费大量的时间和精 力去建立分析模型，产生一个分析模型总是要经过几何模型简化、网格划分、载荷和 约束的定义、材料定义等步骤。而这种模型抽象化的过程常常要依赖于有经验的分析 人员，但是有限元网格的生成都是在手工或半自动中进行的，决大部分时间都花费在 网格生成等繁重、冗长的数据准备上，并且数据可靠性差，严重阻碍有限元的推广及 应用。可以说，有限元网格生成问题是阻碍有限元法迅速发展的“瓶颈”之一。 1 1 2 曲面网格自动生成技术的发展趋势 曲面网格自动生成技术研究领域已取得许多重要成果，形成了独特的方法论体系， 提出了许多有效的算法并研制出一些成功的工程化软件产品。 近十年来，曲面网格自动生成技术方法研究有以下几个显著特点【1 】： 1 与其它研究领域一样，经历了一个进化过程，一些方法的研究与应用出现停滞， 而另外一些方法在不断地深入、完善和发展，成为适应性强、应用范围广泛的通用方 法； 2 领域和主题在不断扩展和深入，研究重点由二维平面问题转移到三维曲面和三 维实体问题，从三角形、四面体网格自动生成转移到四边形、六面体网格自动生成， 在并行网格生成、自适应网格生成、贴体坐标网格生成、各向异性网格生成等方面亦 取得许多重要进展。 随着计算机技术的普及和计算速度的不断提高，曲面网格自动生成技术在工程设计和 分析中得到了广泛重视，已经成为解决复杂的工程分析计算问题的有效途径，现在从 汽车到航天飞机几乎所有的设计制造都已离不开有限元分析计算，其在机械制造、材 料加工、航空航天、汽车、土木建筑、电子电器，国防军工，船舶，铁道，石化，能 源，科学研究等各个领域的广泛使用已使设计水平发生了质的飞跃。 3 自适应网格生成技术。近年来，自适应网格生成技术发展非常迅速。自适应网 格生成对于提高有限元分析的精度是非常有效的，自适应网格生成算法与实际模型的 求解方程、算法特征相关联，随着有限元研究与应用领域的不断扩展，自适应网格生 成算法也会不断发展。 4 网格生成算法的并行化和分布化。并行化计算环境对于大规模、超大规模科学 计算以及高端工程应用是必需的，而分布式计算环境可作为一种中端工程应用解决方 案。现有网格生成并行化或分布化算法在计算效率、内存管理、生成单元质量等方面 还不够完善，还有许多潜力可挖。另外，并行计算环境与分布式计算环境的控制软件 日趋成熟，这为算法的并行化、分布化开发提供了更强有力的技术保障。 5 网格生成的智能化。目前的网格生成算法及其软件还需要许多人工干预，如节 点密度控制、门槛值设定、单元类型选择等。这一方面给用户提供了更多的控制能力， 但同时也给用户增加了困扰。一种便捷、易用、能够充分利用经验，并根据目标域特 征自动给出合理的网格剖分结果的傻瓜型智能化网格剖分器一直是工程设计人员所渴 2 望的。目前，计算机科学领域中的人工智能、专家系统、几何造型方法及特征识别等 方面的研究成果为智能化网格剖分提供了可能性。 6 提高计算精度将是有限元技术发展的另一任务。网格精度直接影响到有限元计 算精度，各种方法自动生成的网格单元受其边界条件制约较大。尽管可以通过单元光 滑法和单元修正技术进行调整，但在复杂区域和复杂边界时这是有限的。因此如何进 一步提高生成单元的精度仍是有限元研究的课题之一。 1 2 曲面网格自动生成方法分类 在众多研究者的辛勤工作下，曲面网格生成方法的研究工作取得了丰富的成果。 曲面网格生成方法的研究已有3 0 多年的历史，国内外研究者先后提出了许许多多网格 生成算法。网格剖分是有限元法的主要瓶颈，同时也是计算几何的一个主要研究对象， 到现在已经形成了大量的实现方法而且随着时间的推移，原有的方法必将得到不断扬 弃或者完善，而新的方法也将会不断的出现。下面在阅读大量曲面网格生成文献的基 础上，将流行的曲面网格方法进行归类【2 矧。 1 2 1 映射法 映射法既是结构化网格生成方法，又是非结构化网格生成方法【6 ，7 1 。它的基本步骤 是：通过适当的映射函数将待剖分物理域映射到参数空间中形成规则参数域；对规则 参数域进行网格剖分；将参数域的网格反向映射回物理空间，从而得到物理域的有限 元网格。曲面网格剖分的映射法也称为参数空间法【8 ，9 】。平面域网格生成方法已经相当 成熟，可生成质量良好的三角形、四边形单元网格。但是，参数空间上单元形状良好 的网格映射到物理空间后往往会出现畸变。许多学者针对此问题对传统映射法进行了 不懈的改进，使映射法的曲面适应能力得到了增强。 映射法的优点是算法简单、速度快、单元质量好、密度可控制，它既可生成结构 化网格又可生成非结构化网格。因此，映射法商业有限元分析软件中占有重要的地位。 图1 1 参考网格和真实区域网格之间的映射关系 3 映射法一般可直接处理单连通域问题，但对于复杂多连通域问题。需要首先用手 工或自动方法将待剖分域分解成几何形状规则的可映射子区域。然后在每个子区域内 应用映射法。然而在实践中仍有几个难点需要克服：( 1 ) 如何自动地将复杂的不可映射 的待剖分域分解成简单的可映射的子区域；( 2 ) 如何满足某些物理问题中对网格疏密过 渡的要求；( 3 ) j z l ：l 何满足子区域之间的网格相容性要求。 子区域分解( 特别是三维实体) 是应用映射法生成有限元网格的最大困难，不少学者 对此提出了多种解决方法，其中中轴线法和中面法具有代表性。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 等提 出用中面法将三维待剖分域分解成简单子区域。由于中轴线法中面法得到的子区域 一般具有可映射特性，因此可以将映射法与中轴线法中面法相结合形成复杂域全自 动网格生成方法。目前，二维问题的中轴线提取算法已经相当成熟，而三维问题的中 面提取算法还存在一些问题，特别是几何适应能力问题。 综上所述，解决曲面网格划分中的映射失真问题可从以下两方面入手：( 1 ) 修改或 重新定义曲面的参数表达，使参数空间到物理空间的映射函数的畸变性降低；( 2 ) 修改 二维网格生成方法，在节点插入和连接时考虑映射函数的畸变性，使参数空间内生成 的网格在映射回物理空间后具有良好的几何性态。 1 2 。2 基于栅格法 基于栅格法( g r i d b a s e da p p r o a c h ) 的基本流程：首先用一组不相交的尺寸相同或不同 的栅格( c e l l s ) 覆盖在目标区域上面，保留完全或部分落在目标区域之内的栅格，删除完 全落在目标区域之外的栅格；然后对与物体边界相交的栅格进行调整、剪裁、再分解 等操作，使其更准确地逼近目标区域；最后对内部栅格和边界栅格( 特别是边界栅格) 进行栅格级的网格剖分，进而得到整个目标区域的有限元网格【l 叭。 基于栅格法又可分为f 则栅格法( r e g u l a rg r i dm e t h o d ) 和有限四( 八) 叉树法【1 1 j ( f i n i t e q u a d t r e e o c t r e em e t h o d s ) 两大类。j 下则栅格法与有限四( 八) 叉树法在算法的总体流程上 基本一致，它们之间的最大区别在于正则栅格法采用尺寸相同的正则栅格覆盖目标区 域，而有限四( 八) 叉树法采用基于四( 八) 叉树数据结构的可递归细分的变尺寸栅格来覆 盖目标区域。与正则栅格法相比，有限四( 八_ ) 叉树法能够更好地协调边界逼近精度与生 成单元数量之间的平衡，因此应用更为广泛。 栅格叠合法是早期典型的基于栅格法。栅格叠合法是由y e r r i 和s h e p h a r d l l 2 】等提出 并发展的。它预先将一个无穷大的规则栅格铺在物体上，然后将栅格与物体求交，在 物体外的栅格去掉，物体内的栅格保留作为网格，与物体边界相交的栅格则进一步处 理形成网格。 4 在栅格叠合法中，当物体的边界变化很剧烈或拐弯很多时，栅格的间距会很小， 这就导致单元的数目急剧增多，甚至会产生溢出。为了解决这个问题，y c r r i 和s h e p h a r d 等又用基于四又树的栅格代替均匀栅格。它解决了均匀栅格数量太多的问题，对网格 的密度有一定的自适应性。 y e r r y 和s h e p h a r d 首先将用于近似表达几何对象的四( 八) 叉树法空间分解法引入到 网格剖分领域，其后又有许多学者对该方法进行了完善和发展，形成了有限四( 八) 叉树 方法。有限四( 八) 叉树方法适用于复杂二维和三维域网格生成，几何适应性强，网格密 度可控制，且算法效率较高( 时间复杂度为o ( n l o gn ) ，实际观察接近于o ( ，其中n 为生成单元总数1 。但该方法也存在如生成网格与所选择的初始栅格及其取向有关、目 标域边界处单元质量较差等严重缺点。 与推进波前法和d e l a u n a y 三角化法相比，有限四( 八) 叉树方法在三角形四面体 网格生成方面并不具有优势。但是，有限四( 八) 叉树方法也有自己独特的内在品质，因 而在相当广泛的领域获得了成功的应用。 1 2 3 推进波前法 推进波前法1 1 3 , 1 4 ( a d v a n c i n gf r o n tt e c h n i q u e ，简称a f n 或者叫网格向前推进生成 技术( a d v a n c i n gf r o n t g e n t r a t i o nt e c h n i q u e ，简称f g t ) 是一种全自动网格 生成方法，它的思想最初是由g e o r g e 提出的，此后许多人都提出相同或类似的思想及 算法。这种方法最主要的特点是从物体的边界开始，定义一个“前沿”。在前沿上满足 一定条件的地方生成一个单元，同时更新“前沿 ，如此不断地重复，直到前沿变为空， 网格生成结束。在生成过程中，前沿就像波浪一样往前推进，直到消失，这就是此方 法命名的由来，通常也叫前沿推进法1 1 5 , 1 6 j 。 先把物体的边界离散，形成一个节点组成的环，并把它定义为初始前沿。物体边 界上节点的密度和分布对最终网格的质量和尺寸分布影响很大。特别是，在生成四边 形网格时，边界上节点的个数必须为偶数，这是由四边形网格的拓扑关系决定的。 ( a ) 内角合适生成二角形( b ) 内角人生成两个三角形( c ) 两边成直线 图1 2 创建单元的几种方法 在初始自仃沿定义后，进行以下三步迭代： 5 ( 1 ) 检查前沿上每个节点的内角，确定新生成单元的位置； ( 2 ) 在满足条件的节点处创建一个或几个单元； ( 3 ) 更新前沿，即把新生成的边界加入环中，删除旧的边界。 单元生成有两种不同的策略。有的算法从整个前沿的所有节点中寻找适合于生成 单元的节点，生成单元的过程中优先使用第一种创建形式，当所有的节点内角都不满 足第一种情况时，才使用第二、三种方法，如 图1 2 所示( 以三角形单元为f i t ) ，有的 算法则在两个节点之间生成一排单元。 在创建单元的过程中，关键是要检查新生成节点的位置，既不能落到物体之外， 也不能落到其它单元内，这个检查是推进波前法中最关键的一点。检查时主要是看前 沿是否自交或两个前沿之间是否相交，若有这两种情况发生，则把前沿分为两个( 或多 个) ，或合并为一个。但检查前沿是否自交在三维曲面上是不可行的，三维曲面前沿上 单元的边界相互从附近穿过，而很少真正相交。为了判断这种情况，p e r a i r e 在参数空 间中进行判断，r o g e r 等则使用一个接近因子来判断前沿的节点之间的接近程度。 当边界上的节点分布不均匀时，生成的小尺寸单元只分布在靠近节点密集的边界处 的部分区域，而其它部分全是大尺寸单元。另外，在三维曲面网格划分中，区域内部 的单元尺寸仅靠边界上节点的分布来控制是不够的，譬如曲面的曲率也是一个重要的 因素，曲率小的地方网格尺寸小，曲率大的地方网格尺寸可以较大。在有限元分析中， 网格尺寸还受接触情况、应变分布等的影响。因此，有时须要定义一整个区域上的单 元尺寸分布函数。 推进波前法能够生成的单元类型较多，对复杂物体的适应性强，它的最大优点是 边界上单元的质量很好。它的缺点是效率较低，有时甚至会因为生成单元的条件太苛 刻而不能进行到底。 经过近年来的发展，推进波前法已成为目前最流行的通用的全自动网格生成方法 之一。该方法的提出应归功于l o h n e r 和l 0 【1 7 l ，灿丌方法没有d e l a u n a y 三角剖分算法 那样成熟的理论依据，在很多情形下a f t 方法是靠经验解决问题，但是这并不妨碍它 的成功应用。舢盯算法的时间复杂度为o ( n l o gn ) ，与d e l a u n a y 三角化算法、有限四( 八) 叉树法相当，但其生成单元的质量是三者中最好的。a f t 方法的基本流程是：首先离 散待剖分域的边界，二维待剖分域的边界离散后是首尾相连的线段的集合，三维待剖 分域的边界离散后是拓扑相容的三角形面片的集合，这种离散后的域边界称为前沿； 然后从前沿开始，依次插入一个节点，并连接生成一个新的单元；更新前沿，这样前 沿即可向待剖分域的内部推进。这种插入节点、生成新单元、更新前沿的过程循环进 行，当前沿为空时表明整个域剖分结束。 a f t 方法的特点之一是能够在生成节点的同时生成单元，这样就可以在生成节点 时对节点的位置加以控制，从而控制单元形状、尺寸以达到质量控制、局部加密及网 格过渡的要求。大量文献提出了各种不同的节点生成方法及单元生成方法。 a f t 方法的特点之二是在生成新单元时需要进行大量的相交判断、包含判断，以 6 及为了保证单元的质量而进行的距离判断，相交判断包括线段之间的相交判断，线段 与三角形面片之间的相交判断；包含判断主要指单元是否包含前沿节点的判断；距离 判断包括线段与线段的距离，线段与前沿节点的距离以及线段与三角形面片的距离。 上述判断的计算，在整个a f t 方法实施过程中耗用了大约8 0 的机时。因此，在实施 a f t 方法时，务必精心设计数据结构，尽量减少需要进行判断的数量，以提高a f t 方 法的效率。其中比较有效的数据结构是a l t e r n 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 方法剖分网格到最后遇到的 不收敛的区域不止一个，对于每一个区域生成一个包含此区域的所有节点的立方体， 然后将那些有节点在此立方体中存在的单元删除，这样便形成一个新的多面体，对于 这个新的多面体重新生成单元。 1 2 4d e l a u n a y 三角剖分法 d e l a u n a y 三角剖分法【1 8 , 1 9 】是一种利用离散点集生成网格的方法。 图1 3 给出了 一个由8 个点组成的平面点集s ，二维v o r o n o i 图是由一些凸多边形组成，且具有以下 性质： ( 1 ) 点集中的任一节点与凸多边形v ( 只) 一一对应； ( 2 ) v ( 只) 内部任意点均以只为“最近邻”； ( 3 ) - - 个或更多的凸多边形可交于一点，这些点称为v o r o n o i 顶点； ( 4 ) 外部的v o r o n o i 多边形为开的，而内部的多边形均为闭式的。如果两个节点相 邻，则它们的v o r o n o i 多边形必然相邻。 图1 3v o r o n o i 图( 虚线) 及其d e l a u n a y 三角剖分( 实线) 7 d e l a u n a y 三角剖分法实质上也是结点连元法，d e l a u n a y 三角剖分在散乱数据场的 可视化、逆向工程、地理信息系统( 如地貌的不规则网格建模) 、v r m l 产品建模等领域 都有十分广泛的应用，尤其在有限元网格自动生成方面广为流行。在平面域的d e l a u n a y 三角剖分中，理论上已经严格证明，只要给定的结点分布中不存在四点及四点以上共 圆时，有最优解，即所有三角形单元中最小内角之和可达到最大值。在d e l a u n a y 三角 剖分后，形成许许多多彼此相连的v o r o n o i 多边形，每个只有一个结点，每一个v o r o n o i 多边形的边实际上就是其内结点与相临v o r o n o i 多边形内结点连线的中垂线，所有 v o r o n o i 多边形的集合叫做d i r i c h l e t 图，连接相临v o r o n o i 多边形内的结点便形成三 角形网格。实现d e l a u n a y 三角剖分乜们的方法很多，常用的一种算法是逐个插入结点的 递归算法。该算法要求生成的d e l a u n a y 三角形的外接圆内不允许存在其他结点，若有 其他结点，则应局部修改原来的剖分。基本过程为：先构造一个大外接圆，将所有结 点都包含进去，然后找出已有三角形中哪些三角形的外接圆内包含新加入的结点，删 除这些三角形内离新结点距离最近的一条边，将新结点与周围的老结点连线形成新的 三角剖分。 除了逐个插入结点的递归算法，在二维d e l a u n a y 三角形划分中，j o e 采用的方法是 先将复杂域分解为凸多边形域，再对每个凸域用缩小多边形生成内部结点并形成凸域 的d e l a u n a y 划分。s a p i d i s 幢等人用增加边界点的方法来保证边界一定包含在 d e l a u n a y 三角剖分中。 在三维划分中，若用逐点插入递归算法，将二维情况推广到三维，则采用四面体 的外接球内不包含其他点的准则来生成四面体网格。不过应注意一些特殊情况的处理， 第一种特殊情况是，新加入的结点恰好落在外接球表面，处理办法是少量摄动新结点位 置，再让程序继续运算；第二种特殊情况是四面体的四个顶点接近共面，尽管四个表 面的三角形形状良好，但四面体的体积近于0 ，称其为薄元，必须要消除薄元，方法为： 若与薄元四面体相临的两个四面体有公共顶点，则删除该薄元，在薄元所接近的平面 内，置换对角线，形成两个新的相临四面体单元；若与薄元相临的四面体的任何两个 无公共顶点，采用增加薄元厚度的方法处理。若将二维的硬币填充算法扩展到三维形 体的情况，就是球填充法，同样从边界丌始逐层向里铺点，该算法具有灵活的填充能 力，可以有效防止薄元的产生，计算效率高。 d c 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 算法j 下是利用了这一特性。 d e l a u n a y 三角剖分算法的计算效率与具体的实现相关。大体上可将d t 算法分为三 大类：分治算法，逐点插入法和三角网生长法。b o w y e r - w a t s o n 算法是一种典型的逐点 8 插入法，其时间复杂度为o ( 厂副。) ，采用四( 八) 叉树数据结构的b o w y e r w a t s o n 算法 乜2 1 可达到0 ( n l o g n ) ，分治算法的时间复杂度为0 ( n l o gn ) ，三角网生长法的时f b j 复杂 度为0 ( 厂驯2 ) ，其中n 为生成单元总数。 s i b s o n 证明了平面任意给定点集的d e l a u n a y 三角剖分的结果具有整体优化的性质， 它满足“最大最小角准则，( 即所有三角形的最小内角之和最大) 。与“最大最小角 准则等价的条件是“外接圆 准则，即对于d e l a u n a y 三角剖分中每个三角形没有一个节 点落到其外接圆的内部，而只可能位于其外接圆之上或外部。 b o w y e r 和w a t s o n 2 3 1 分别提出了计算n 维空间中任意给定点集的、，o r o n o i 【2 4 l 图的有 效算法。l a w s o n 根据“最大最小角”准则，通过“对角线交换”方法实现了二维给定 点集的d e l a u n a y 三角剖分。 但w a t s o n 的算法效率更高，它对节点没有任何约束，只能用于解决凸边界的问题。 对于任意凸多边形可直接利用w a t s o n 算法。丁永祥博士使用“修正的外接圆 准则来 实现任意边界条件下的d e l a u n a y 三角剖分，而卢朝阳博士则实现了内部也带约束的 d e l a u n a y 三角剖分【2 5 , 2 6 】 在有限元网格划分中，节点不是预先给定的，而是在划分之初或中间生成的。有 入利用均匀栅格的交点作为d e l a u n a y 三角剖分中的内部节点，l o 用波前法来生成内部 节点，丁永祥博士在生成过程中选择三角形插入新节点，而s h i m a d a 则用圆模拟v o r o n o i 图结构，更容易控制网格的尺寸。 目前三维曲面的三角形网格生成方法已比较成熟，而三维曲面的四边形网格( 网格 全部为四边形) 生成方法还不成熟。四边形网格生成主要使用波前法和d e l a u n a y 三角剖 分，使用d e l a u n a y 三角剖分要使用转换算法把三角形网格转换为四边形网格，实际算法 很不成熟。当前，在曲面片上划分网格可借用前面所提到的算法，主要的问题是拼合 时相邻曲面片之间容易产生缝隙，这是由相邻曲面片公共边界上节点的数量和位置不 一致引起的。由于实际应用中曲面片之间的大小相差很大，有的曲面片甚至远小于单 元的尺寸，或者非常狭长，在一个方向上的尺寸小于单元尺寸，另外有的曲面片上存 在小孔，在进行网格划分时要忽略，这给数据的组织和网格的划分带来很大的困难。 网格划分时怎样处理这些曲面片和小孔，目前还没有得到很好地解决，有待进一步研 究。 1 2 5 直接法 与映射法不同，直接法的曲面网格划分【2 7 1 是直接在曲面的物理空间进行。由于剖 分过程直接以曲面的局部几何形态为参考，并根据曲面的局部状况采取不同的剖分策 略，因此直接法的曲面自适应能力较映射法强，其生成的网格能较好地逼近原始曲面。 而且网格的质量也较高，直接法的研究起步较晚，目前主要有两个分支：曲面分解法 9 和基于a f t 的直接法。 曲面分解法是一种基于四叉树分解的曲面剖分方法。它的基本思想是：将原始曲面 不断地递归分解为较小的面片，直到这些小面片在给定的逼近误差下可精确模拟原始 曲面为止：然后再将小面片转换为三角网格，最终形成对原始曲面三角划分1 2 8 , 2 9 j 。这 种方法最大的优点就是能够生成曲面自适应网格【删，对复杂曲面的逼近程度较好。但 相对于映射法来说，它的执行速度较慢，缺乏网格的局部控制能力。 表1 1 三种全自动网格生成方法比较 性能方法 d e l a u n a y 三角化法 有限四( 八) 叉树法 推进波前法 计算效率( 随生成单2 d ，3 d 均为2 d ，3 d 均为2 d ，3 d 均为 元总数n 的变化) o ( nl o g ( n ) )o ( n l o g ( n ) ) ，实际o ( ul o g ( n ) ) 观察三者中效率最高 所生成的网格单元质2 d 网格质量较好，3 d区域内部网格质量较2 d 、3 d 网格质量都 量 易产生薄元，但已有好，边界网格质量较 较好 解决办法差 单元密度控制 事先、事后密度控制事先、事后密度控制 事先、事后密度控制 均可，局部性一般均可，局部性好均可，局部性好 所能生成的单元种类能直接生成三角形、能直接生成三角形、能直接生成三角形、 四面体单元四边形、四面体单元，四边形、四面体单元， 经扩展可直接生成人经扩展可直接生成六 面体单元面体单元 自动化程度全白动全自动 全自动 程序实现复杂度相对较容易太复杂中等雉度 问题区域适用性2 d 、3 d 任意区域均2 d 、3 d 任意区域均2 d 、3 d 任意区域均 可可可 程序的可靠性2 d 、3 d 任意区域可2 d 任意区域均好，3 d2 d 、3 d 任意区域可 靠性均好任意区域尚可靠性均好 各向异性网格生成可以i i 4 难好 结构化网格生成不能不能 不能 并行网格生成能可将分区域网格能叉树结构可以作能主要作为子区域 生成合并为一个过为框架数据结构网格剖分方法 程，有发展潜力 白适应网格生成 能密度控制能力一 能密度控制能力强能密度控制能力强 般 曲面网格生成 间接法，生成单元质 直接法、间接法均可，直接法、间接法均可， 量好生成单元一般生成单元质带好 人面体网格生成不能经扩展叮直接生成六经扩展可直接生成人 面体单元面体单元 算法应用频度二者中最高低，i 要应j 钓丁六面局 体网格生成 1 0 基于a f t 的直接法是对a f t 技术的一个发展，它对传统的二维a f t 三角化方法 进行了三维扩展：引入了新的判别算子，扩充了控制前沿网格生成的约束条件，使用 投影算法以保证插入节点在曲面上的精确定位。基于a f t 的直接法具有灵活、可靠、 简单等特点，而且由于同时使用曲面曲率和密度函数作为网格剖分的控制因子，它不 仅表现出良好的曲面适应能力( 在曲率变化平缓的地方生成的网格比较稀疏，在曲率变 化激烈的地方生成的网格比较稠密) ，还具有网格的局部加密能力，是一种很有前途的 曲面网格全自动生成方法1 3 。但相对于映射法来说，其计算效率略显不足。 上面表1 1 所示为三种全自动网格生成方法的主要性能比较。 虽然d e l a u n a y 三角剖分对于给定的点集来说其形成的网格质量是最优的，但往往 生成的网格与实体的边界会出现不相容的情况，要进一步处理边界。波前法的主要思 想是将边界剖分得到的线段作为初始前沿，对前沿中的每条线段寻找域内的一个点与 之形成合法、且质量最好的三角形；在此过程中不断更新前沿，直至前沿为空时结束 剖分。对具有复杂几何形状和边界的二维形体的剖分，波前法具有很好的灵活性和可 靠性；但它必须不断维护前沿，而且查找的时间耗费也很大。在l osh 之后，有许多 人对波前法作了大量的工作，主要集中在将波前法由二维向三维扩展，以及合并布内 节点和生成单元这两个步骤上，但对如何既简单、有效地提高波前法的效率未作深入 的讨论。 1 3 本文研究的目的及主要内容 曲面网格生成是有限元网格生成技术中的一个重要领域，它的应用相当广泛。工 程结构中常用的薄壳，如球罐、压力容器、冷凝塔、飞机蒙皮、汽车外壳等，都是由 圆柱、圆锥、球面等规则曲面以及b e z i e r 、b 样条，n u r b s 等自由曲面组合而成的。 此外，曲面的网格划分结果往往是三维实体网格划分的前提和基础，其质量的优 劣对后续生成的三维实体网格的质量有很大影响。 曲面网格生成是个难题。在以往的工作中，必须花费大量的时间和精力去建立分 析模型，产生一个分析模型总是要经过几何模型简化、网格划分、载荷和约束的定义、 材料定义等步骤。而这种模型抽象化的过程常常要依赖于有经验的分析人员，但是有 限元网格的生成都是在手工或半自动中进行的，决大部分时间都花费在网格生成等繁 重、冗长的数据准备上，并且数据可靠性差，严重阻碍有限元的推广及应用。可以说， 曲面网格生成问题是阻碍有限元法迅速发展的“瓶颈”之一。 b 样条曲面的三角化问题，也是曲面近似、曲面造型中不容忽视的重要问题之一。 早期的b 样条曲面三角剖分算法大多采用参数映射法，这种方法一般利用平面网格生 成技术对曲面参数域上的网格结点建立连接关系，经映射后，得到曲面的网格剖分结 果。参数映射法对于比较光滑均匀的曲面可能会得到比较好的剖分结果，但对于一些 形状复杂的曲面，在参数域上具有良好形状的网格，在曲面上可能产生严重畸变的网 格。 为了克服参数映射法的弊端，本文以直接法为基础，利用网格向前推进生成技术 直接对曲面进行j 下三角形网格生成。直接法曲面网格划分是直接在曲面的物理空间进 行，由于划分过程直接以曲面的局部几何形态为参考，并根据曲面的局部状况采取不 同的划分策略，因此直接法的曲面适应能力较映射法强，其生成的网格能较好地逼近 原始曲面，而且网格的质量也较高。 本文将讨论的是：一边产生节点一边产生网格的方法，其中最具代表性的就是网 格向前推进生成技术，即a d v a n c i n gf r o n tg e n e r a t i o nt e c h n i q u e ( 简称 f g t ) ，实用性广，对区域边界描述简单。利用网格向前推进生成技术在曲面上直接进 行三角化的方法，目前利用这种方法生成曲面网格的比较少，难点在于直接在曲面上 网格生成过程中，点p 比较难求，主要是必须求解非线性方程组。利用该方法生成曲 面三角网格的优点是直接在曲面上生成正三角形，其网格的大小及拉伸可以由空间域 及背景网格精确控制，网格的质量比较好。由于工程中自由曲面都可以由b 样条拟合、 插值而成，故本文以b 样条为基本生成曲面研究曲面网格自动生成。 本文研究的主要内容： 1 、以直接法为基础，利用网格向前推进生成技术，对b 样条曲面进行f 三角形网 格生成； 2 、基于网格向前推进生成技术，给出所有可能的几何拓扑特征下生成三角形的算 法： 3 、对b 样条曲面三角网格自动生成进行数学分析、原理研究、编程与实验设计， 同时对网格生成过程中的一些特殊情况进行处理； 4 、采用求解非线性方程组的b r o y d e n 方法，在曲面网格自动生成过程中对三角形 进行求解，该方法已知三角形两点有效地找到第三个点； 5 、利用直接法和网格向前推进生成技术，编制一个基于f g t 的曲面三角网格自 动生成软件系统，该系统对不同控制点下的各种形态的曲面进行证三角形网格全自动 生成，验证了算法及程序的有效性。 1 2 第二章b 样条曲面三角网格自动生成的数学原理 本文以直接法为基础，即直接在b 样条曲面上进行三角网格划分，利用网格向前 推进生成技术( f g t ) ，生成曲面三角形网格，用此方法提高了网格生成的效率。目前利 用这种方法做曲面网格生成的比较少，难点在于直接在曲面上曲格生成过程中，以当 前前沿为边的三角形的另外一点p 比较难求，需要求解非线性方程组，本文用b r o y d c n