（机械设计及理论专业论文）四边形网格生成算法研究.pdf

华中科技大学硕士学位论文 摘要 随着科技水平的提高，有限元方法已经成为i _ , l k 设计和分析的支柱，有限元模拟 的设计越来越复杂，随着它的应用越来越广，其关键性的技术一网格划分越来越重 要。有限元网格划分是工程科学与计算科学相交叉的一个重要研究领域，其研究重 点由传统的三角形四面体网格转移到四边形六面体网格。本文详细地阐述了三角形 到四边形网格转换生成算法研究。 奉文介绍和比较四边形网格生成技术的各种算法，并且讨沦了一种新的任意曲面 的四边形生成算法q m o r p h ，该算法从三角网格开始，沿着边界从外向内将三角 单元系统地转换为沿边界排列的全四边形网格，并且只产生少量不规则点。本文详 细地介绍了q - - m o r p h 算法的内容及其程序实现。 网格优化过程包括拓扑优化、边界优化、形状优化和尺寸优化。本文详细地介绍 在四边形网格中以上各种优化类型的应用范围，对每一种优化形式给出实例，并总 结经验，提供解决方案。 光顺是网格划分的重要步骤，它通过不断地调整节点位置来减小单元变形。本文 在捕述l a p a c i a n 光顺和基于优化的光顺算法的基础上，提出了种对三角网格、四 边形网格和三角四边形混合网格的光顺算法一基于角度的光顺算法。通过与几种光 顺算法的精度和计算量的对比，可知该算法的效果和效率相结合方面要优于其他算 i 去。 关键字：有限元方法四边形网格网格优化基于角度的光顺 华中科技大学硕士学位论文 a b s t r a c t w i t ht h ea d v a n c eo fs c i e n c ea n dt e c h n o l o g y , f i n i t ee l e m e n tm e t h o di nr e c e n td e c a d e s h a sb e c o m eam a i n s t a yf o ri n d u s t r i a le n g i n e e r i n gd e s i g na n d a n a l y s i s i n c r e a s i n g l yl a r g e r a n dm o r ec o m p l e x d e s i g n sa r eb e i n gs i m u l a t e du s i n gt h ef i n i t ee l e m e n tm e t h o d w i t hi t s i n c r e a s i n gp o p u l a r i t yc o m e s t h ei n c e n t i v et oi m p r o v ea u t o m a t i cm e s h i n ga l g o r i t h m s a s a n i m p o r t a n tr e s e a r c hf i e l dc o m b i n ge n g i n e e r i n gs c i e n c ew i t hc o m p u t e rs c i e n c e ，f i n i t e e l e m e n tm e s hg e n e r m i o nh a sc o n v e r ti t sr e s e a r c hf o c u sf r o mt h ea l g o r i t h m so ft r a d i t i o n a l t r i a n g l e t e t r a h e d r o nm e s hg e n e r a t i o nt ot h o s eo fq u a d r i l a t e r a l h e x a h e d r o n i nt h i sp a p e r , t h er e s e a r c ho n q u a d r i l a t e r a lm e s hg e n e r a t i o na l g o r i t h m si sp r e s e n t e d i nd e t a i l a l g o r i t h m so fq u a d r i l a t e r a lm e s hg e n e r a t i o na r ed e s c r i b e da n dc o m p a r e d ，t h e n an e w m e t h o d ，k n o w na sq m o 曲，f o rq u a d r i l a t e r a lm e s hg e n e r a t i o no na r b i t r a r ys u r f a c e si s i n t r o d u c e d t h e a l g o r i t h mb e g i n s w i t ha t r i a n g u l a r m e s h ，o v e rw h i c hs y s t e m a t i c t r a n s f o r m a t i o n sa r ep e r f o r m e do nt h et r i a n g l e sw o r k i n gf r o mt h eb o u n d a r yt o w a r dt h e i n t e r i o r ab o u n d a r y a l i g n e da l lq u a d r i l a t e r a lm e s hw i t hf e wi r r e g u l a ri n t e r n a ln o d e si s p r o d u c e d i t sa l g o r i t h mp r o c e d u r e sa n d r e a l i z a t i o nw i t hp r o g r a m m i n ga r ee x p a t i a t e d m e s hr e f i n e m e n tp r o c e s si n c l u d e st o p o l o g yr e f i n e m e n t ，b o u n d a r yr e f i n e m e n t ，s h a p e r e f i n e m e n ta n ds i z er e f i n e m e n t i nt h i sp a p e r , t h ea p p l i c a t i o n so fe a c hr e f i n e m e n tt y p et o q u a d r i l a t e r a l m e s ha r ee x p o u n d e dw i t hm a n ye x a m p l e s a c c o r d i n gt o t h e e x p e r i e n c e a u r i n gh a n d l i n g t h e s ee x a m p l e s ，t h es o l u t i o n st oe a c he x a m p l ea r eo f f e r e d s m o o t h i n g i sac r i t i c a ls t e po fm e s hg e n e r a t i o n ，w h i c hr e p o s i t i o n sn o d nl o c a t i o n s ，s o a st om i n i m i z ee l e m e n td i s t o r t i o n i nt h i sp a p e r , b a s e do nl a p l a c i a ns m o o t h i n ga l g o r i t h m a n d o p t i m i z a t i o n b a s e ds m o o t h i n ga l g o r i t h m s a n o v e r a l l m e s h s m o o t h i n g s c h e m e ， a n g l e b a s e ds m o o t h i n ga l g o r i t h m ，i s p r e s e n t e d f o rm e s h e sc o n s i s t i n go ft r i a n g u l a r q u a d r i l a t e r a l ，o rm i x e dt r i a n g u l a r a n d q u a d r i l a t e r a le l e m e n t s k e y w o r d s ：f i n i t e e l e m e n tm e t h o d q u a d r i l a t e r a lm e s h m e s hr e f i n e m e n t a n g l e b a s e ds m o o t h i n g ； i i 华中科技大学硕士学位论文 ；= = = ；= = = = = = = = = = = = = = = = = = = = = = = = = = 一 1 绪论 1 1 课题的目的及意义 有限元网格生成是工程科学与计算机科学相交叉的一个重要研究领域，在经过- 十多年发展后的今天依然非常活跃。一方面，有限元法已成为一种能够何效地求删 各类工程和科学计算问题通用的数值分析方法；另一方面，计算机硬件运算能力的 不断提高也允许人们对工程和科学计算的规模、复杂度、效率、精度等方面提出更 高的要求。作为有限元走向工程应用的桥梁的有限元网格生成由此获得了源源不断 的外在动力。同时，有限元网格生成算法研究中的某些难点问题始终未能获得真j f ： 意义上的解决，它们的研究解决对计算几何与计算数学都具有重要的理沦价值。 有限元网格生成方法研究领域已取得了很多重要成果，形成了独特的方法沦体 系，提出了许多有效的算法并研制出一些成功的工程化软件产品。近l o 年来，有瞅 元网格生成方法研究有两个显著特点：( 1 ) 与其他研究领域群经历了个进化 过程，一些方法的研究与应用出现停滞，而另外一些方法在不断地深入、完蒋剐发 展，成为适应性强、应用范围广泛的通用方法；( 2 ) 领域和主题在不断扩展和深入， 研究重点由二维平面转移到三维曲面和三维实体问题，从三角形叫面体嘲格自动7 i ? 成转移到四边形六面体网格自动生成，在并行网格生成、自适应网格生成、贴体k 标网格生成、各向异性网格生成等方面亦取得很多重要进展。 本课题紧随有限元网格发展的趋势，着重研究三角形网格到四边形例格的转换罅 法，其目的是丌发转换算法的程序。 1 2 有限元网格生成技术 网格划分( 又叫结构离散) 是有限元建模( 即6 u 处理) 的关键技术。_ ! 【1 果睨何限 元建模目自u 是限制有限元方法推广和应用的主要瓶颈，那么制约有限元建模技术进 一步发展的主要瓶颈就是网格化分技术，即全自动、快速、高质量、自适应的刚格 生成技术。网格划分是一个计算几何中比较新的领域，也是有限元建模技术的研究 热点之一 1 卅。 l _ 2 i 有限元网格划分的基本原则 有限元网格生成器是有限元建模工具的核心部分，有限元的形：状、火小、疏密等 都是影响有限元分析结果的重要的因素。因此，有限元网格划分必须遵衍一定的原 华中科技大学硕士学位论文 则。这些基本原则包括： 拓扑f 确性原则 设e ，、，分别为结构离散后的任意两个单元，p ，、e ，、，分别为单元e 的节点、 单元边、单元面。若满足e ，n e ，= 0 v nv p ，v 则称单元巨，是拓扑正确的。 这罩，o 表示空。简言之，拓扑正确性原则即两单元的交为空或为单元顶点，或为 单元边，或为单元面。 几何保形原则 设原始结构为q ，e ，( i _ 1 ，2 n ) 为离散后的单元，若当仃j 。时，满足 ij ，= q 则称单元几何保形。简言之，几何保形原则即所有单元的集合为原结构的 近似。 特性一致性原则 即一个单元内的物理特性和几何特性必须相同。如：材料相同，厚度相同等。 以上三条是网格划分必须遵守的最基本原则，拓扑正确性原则保证了单元与单元 不可能出现相交，单元与单元之间不可能出现裂缝。几何保形原则保证了不存在与 原始结构边界相交的单元，单元内也不可能出现孔洞，同时，还保证了单元的边界 节点只能精确地布置在原始结构的点、边、面上。特性一致性原则是进行单元力学 特性分析的基本条件。 为了保证有限元计算结果的精度和可靠性，在进行网格划分时，还应遵循如下两 条基本原则： 单元形状优良原则 j ；二网格形状是影响计算精度的重要因素之一。若网格形状太差，严重时会导致不可 靠的计算结果或不能进行计算。所以，通常对网格的几何形状都有一定的要求。如 网格各边的长度比例不能太悬殊或网格的各边夹角应大于3 5 度和小于1 3 5 度。三角 形的最优形状是等边三角形，四边形的最优形状是正方形。 密度可控原则 叫格划分应兼顾计算精度和计算机处理速度与存储空间的要求。一般来说，阿格 越密，越多计算精度越高，但网格越多，计算量越大，计算机存储空间要求越大。 因此，网状划分应在保证必要精度的条件下，网格疏一些，致使整个网格划分的数 量最，) 。 华中科技大学硕士学位论文 = = 目= = ；= = ；= = = = = = = = = ；= = 自。= 。= = = ；= = ： 有限元网格划分除了需要满足上述最基本的原则外，在具体的工程应用环境中 应该满足各种不同的要求。工程上对网格生成器的要求主要涉及：基本功能一肚： 棒可靠性；网格质量；速度；尽可能少的用户干预；可控制性。在为满足这些要 丽对算法和总体方案作出评价的时候，就不得不权衡它们以最佳地满足用- 的要j 例如，速度通常是和几乎所有其他的要求( 特别是鲁棒性和整体网格质量) 相矛 的。 1 3 四边形网格剖分方法概述 全自动非结构化的网格生成算法的研究大部分集中在不同的三角网格生成方 上。象三角形和四面体这样简单的单元适合离散任意复杂区域，特别是需要梯度 格的区域。最近以来，网格划分的重点转移到四边形和六面体网格生成算法上。 为在一般情况下，对于相同自由度的网格而言，四边形网格比三角形网格有更好 计算精度，例如壳体结构有限元分析和汽车碰撞模拟常优先考虑采用四边形例格 因此四边形网格在工程应用中更受欢迎。 四边形网格生成方法主要有间接法和直接法两类1 2 “。 1 3 1 间接方法 1 31 j 转换策略 这类方法先在剖分域生成三角形网格，然后通过合并或分裂把三角形网格转化 四边形网格【7 】【8 】。有三种策略可使三角形网格转化成四边形网格： ( 1 、一个三角形单元分裂成三个四边形单元( 如图1 1 ) 。每个三角形可以剖分 三个四边形，三角形每边上增加一个点，通常是浚边的中点。三角形内部增加的 个点通常是三角形的重心。很明显采用这种策略可以将任何三角形网格转化成四 形网格，但是这种网格的质量很差。 图1 1 一个三角形单元分裂成三个四边形单元( 左) ； 两个三角形单元合并为一个四边形单元( 右) ( 2 ) 两个相邻三角形单元合并为一个四边形单元( 如圈1 1 ) 。 t 华中科技大学硕士学位论文 目= ；= = = ；= = ；= = = ；= = ；= = = = = = = = ；= 一= = 将三角形单元个数为奇数的网格完全转化成四边形网格，而对单元个数为偶数的三 角网格来说，也有可能产生孤立三角形，这些孤立的三角形周围全是四边形。曲面 上的两个三角形单元合并后得到的四边形般是不共面的。在有限元分析中，虽允 许四边形有轻微翘曲，但不能超过一定限度，否则会严重影响有限元求解的精度。 ( 3 ) 两个相邻三角形单元合并后分裂为四个四边形单元( 如图1 2 ) 。除了某些孤 岛三角形外，可以生成四边形网格。但采用第一种策略，孤岛三角形可以剖分成三 个阴边形。所以采用这种策略可以将三角形网格完全转化成四边形网格。 图1 2 两个三角形单元合并后分裂为一个四边形单 既然在f 刚接方案中，四边形网格是由三角形网格转化而来的，通过高梯度的三角 形网格不难得到高梯度的四边形网格，不规则、多连接区域也很容易处理。遗憾的 是用这种方法生成的四边形网格相对于直接法而言，往往质量较差。因此，要产生 适合于自适应有限元分析的高梯度高质量四边形网格，必须对网格进行优化、光顺。 1 3 1 2 转换方法 在间接方法中，四边形网格的质量很大程度上取决于是由哪对三角形联合的。四 边形单元的形状和余下的三角网格的数目也取决于三角形对的选择。在大多数情况 下，工程分析中有足够质量保证的四边形网格采用下述网格转换方法一j 。 a 三角单元数量最小化的转换方法 这种类型的方法计算每一个三角形周围未被处理的邻接三角形的数目，并且对那 些只有一个级别较高的未处理的邻接三角形的那些三角形做上标记。然后提取这些 三角形，并将其与其邻接的三角形转换为四边形单元。在转换过程中，三角形的邻 接关系要动态地更新，并且在这个过程中，很多三角形优先级升高，并加以标识a 最后，大量有标识的三角形转换为四边形单元，从而产生了四边形为主的网格。由 于这些方法的目的是要生成全四边形网格，因此也包括一些将剩余的三角形进行转 换的后处理。 b 最小化几何不规则性的转换方法 这类方法首先计算由所有可能的四边形的形状质量的数量方程的值。然后根据方 程的值的顺序将三角形对转换为四边形单元。评估四边形形状系数的方程有很多。 4 华中科技大学硕士学位论文 ；= = = ；2 = = = 。；= ；= = ；自；= ；= = = ；= = = 目= 。一= l o 等提出通过四边形的两条对角线将四边形划分为四个三角形，然后求出这些三 角彤的形状系数，通过一个评估方程来比较这些三角形形状系数的比来得到四边形 的形状系数。b o r o u c h a k i 等提出基于四边形四个顶点处的角度的评估方程。这些在 后续章节都将有介绍。 c 类似于边界推进的转换方法 在很爹隋况下，沿区域边界的单元在工程分析中是至关重要的，因此网格单元沿 区域边界排列整齐是比较理想的。可以先结合输入三角网格边界处的三角形，这种 三角形到四边形的转换方法可以得到沿边界排列整齐的四边形网格。s h i m a d a 等设 计了一种方法，首先将三角形网格沿着边界分为一层层的子域，然后在每一层内将 这些三角形结合起来生成四边形单元。该方法生成几何规则的网格网格单元的形 状可以通过光顺过程得到改善。o w e n 等提出“q - - m o r p h ”算法，该算法首先按顺 序对输入三角网格的边界边进行处理，然后沿着该边界边通过重新连接其附近的一 些边来生成四边形。生成的四边形网格质量很高，并且能很好地与区域边界排列整 齐，这一点与边界推进发生成的网格类似。 1 32 直接方法 直接法的曲面网格划分直接在物理空间中进行。由于剖分过程直接以局部几何形 态为参考，并根据局部状况采用不同的部分策略，因此直接法的适应能力较映射法 强，其生成的网格能较好地逼近原始曲面，而且网格的质量比较高。直接生成四边 形网格的方法有很多，这些方法可以分为两种类型。第一种方法将整个区域划分为 多个可通过模板进行划分的简单区域。另一种方法使用边界推进法直接布置节点和 边。 13 21 分解法的四边形网格划分 分解法是一种基于西又树分解的剖分方法。它的基本思想是：将原始区域不断地 递归分解为较小的子域，直到这些子域在给定的逼近误差下可精确模拟原始区域为 止：然后再将予域转换为网格单元，最终形成对原始曲面的网格划分。这种方法最 大的优点就是具有自适应能力，对复杂区域的逼近程度较好。但它的执行速度较慢， 缺乏网格的局部控制能力。 由b a e h m a n n 提出的八叉树分解法是最先利用分解区域来进行四边形网格化的方 法之一。将二维空间分解成基于本地基本特征的尺寸，然后将四边形单元放入八叉 树的树，并调节结点以与边界一致。t a l b e r t 后来提出另一种分解技巧。该法递归地 将区域分成简单的多边形，这些多边形符合一些可以插入四边形的模板。t a m 首先 华中科技大学硕士学位论文 ；= = ；= 目= = = = 2 = ；= = = = = 2 = = = = = = = = = = = = 提出了利用中线来分解区域得到四边形网格的方法。中线表示连接覆盖表面的最大 网心的一系列连线。分解为简单区域后，利用模板将四边形单元插入到区域中。利 用线性编程技巧来维护相邻区域交界处的元素分解的兼容性。j o e 同样也利用分解算 法来将区域分解为凸多边形。利用已有的三角形网格生成技术，j o e 在每一个凸的子 域内构建了边界约束的四边形网格。 】3 22 边界推进法四边形剖分 基于边界推进法的直接法是对边界推进法技术的一个发展，具有灵活、可靠、简 单等特点，而且由于同时使用曲面曲率和密度函数作为网格耐分的控制因子，它不 仅表现出良好的适应能力，还具有网格的局部加密能力，是一种很有前途的网格全 自动生成方法，但其计算效率略显不足。 z h u 首先应用边界推进法直接生成四边形网格。开始时在边界上布置初始节点， 然后将边向内部投射形成一个单元。使用传统的边界推进法生成两个三角形，然后 把两个三角形合并成一个四边形。b l a c k e r 和s t e p h e n s o n 提出铺砌算法，浚法从边界 同内生成一排四边形，并讨论了包括投射节点，特殊的几何情况，和相对的边界交 叉的问题。c a s s 改进铺砌算法使之推广到三维的曲面。w h i t e 最近改进了铺砌算法， 使之能生成单个单元，而不是一整排的单元。 1 4 四边形质量评价准则 1 4 1l e e 和l o 的四边形标准1 0 】 1 三角形口系数 三角形口系数按照如下定义： 啦删观括剖篙 ， 。的值域是 o ，l 】，越大表明质量越好，2 3 是个数量因子来使等边三角形为最 大值1 。典型的三角形口系数如图1 3 所示： 6 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = q = 1q = 0 8 6 6a = o 7 6 图1 3 典型三角形的a 系数 2 四边形单元形状准则 四边形单元的形状质量评价准则通常使用b 系数。 把四边形a b c d 沿对角线分割成四个三角形a d c a 、b c a 、a d b c 、d b a ， 设对应的q 系数是oi 、o2 、o ”q4 ，且按降序排列即oio2o3q4 ，则 四边形单元的b 系数定义为： d ( 1 2 ) h 图1 4 四边形的b 系数 s 系数越大，表明四边形质量越好。凸四边形的8 系数在 o ，1 1 区帕j ，矩形的b = 1 ；如果四边形退化为三角形，0 = o ；凹四边形的b 系数小于0 。 1 4 2b o r o u c h a k i 的四边形质量评价标准 1 2 l i 3 】 设三角形a b c ，b c 和翩的夹角0 。， 华中科技大学硕士学位论文 0 b = l b c b a i 吖5 l 丽硐j z s ( 晶o b a 设角度质量系数为妒( 口) ，其中0 o b c 删 o ( a sb e ) n0 【一l ， i n 足在三角形中点处的啦面法线向量。引入符号i 是为了发现映像单元 l e e 的标准唯一的改变。n 的值域为 一l ，1 ，越大表 明质量越好，当q 小于0 时，三角形为映象三角形。如 图l5 中所示的映象a d b c ，公式1 1 得出的q = o 8 6 6 ，公式1 6 得出的a = - - 0 8 6 6 ，准确反应出形状 的不合理性。 2 四边形单元形状准则1 该准则也同样基于l e e 和l o 提出的四边形形状准则 上晴拍公式1 2 稍作改动： = m i n ( a i ，口2 ，口3 ，a 4 ) 一n e g v a l a 这是对 c b 图1 5 映象三角单元 同样稍微做了些改动。对 f 1 7 ) 其l j 一，口用改进后的公式1 6 计算。若四边形有一个角度小于6 度，或者有两个节 点在误差范围内重合，或者有两个三角形是映像三角形( 即口，是负的) ，n e g v a l = 1 。 如果有三个口是负的，n e g v a l = 2 ，有四个a 。是负的，n e g v a l = 3 ：陔常量对节点移 动是否真的改善了网格质量做了一个客观的 数量化评估。 公式12 中的三角形系数a 由公式1 1 计算 得出，由于上述的公式对映象单元没有辨别能 力，因此公式1 中的b 系数也不能反映出映 象四边形单元。公式1 7 允许负的度量值出现， a 图1 6 窄长条和映象四边形 9 d c几u a b 华中科技大学硕士学位论文 在有两个或者四个口是负值的时候，b 值就会显示为错误值。此外，l e e 的标准不 能发现比例问题，应用他的标准，图1 6 所示的窄长条矩形0 = l ，也被认为是形状 最佳的四边形。而这种类型的四边形单元质量很差。公式1 7 避免出现这种情况。 1 5 网格划分发展的趋势 自本世纪五十年代至今，随着科学技术的不断进步有限元网格划分技术飞速发 展。一方面有限元网格生成还有很多难点问题未能解决，另一方面现有的算法在效 率、质量、可靠性、几何适应性、规模、便捷性等方面还存在许多问题，需要进一 步研究。自动网格划分技术在今后的发展可能会出现以下特点： ( 1 )通用算法的数据结构与多种算法的联合应用。在通用算法的研究方面，应注 意数据结构的研究和多种算法的联合应用，提高核心算法的可靠性和几何适 应性，达到速度与质量之间的平衡，实现核心算法的黑箱化。 ( 2 )自适应网格生成技术。近年来，自适应网格生成技术发展非常迅速。事实证 明，自适应网格生成对于提高有限元分析的精度是非常有效的。自适应网格 生成算法与实际模型的求解方程、算法特征相关联，随着有限元研究与应用 领域的不断扩展，自适应网格生成算法也会不断发展。 ( 3 )网格生成算法的并行化和分布化。并行化计算环境对于大规模、超大规模科 学计算以及高端工程应用是必需的，而分布式计算环境可作为一种中端工程 应用解决方案。并行计算环境与分布式计算环境的控制软件f 趋成熟，这为 算法的并行化、分布化开发提供了更强有力的技术保障。 r 4 )网格生成的智能化。目前的网格生成算法及其软件还需要很多人工干涉，这 一方面给用户提供了更多的控制能力，但同时也给用户增加了困扰。一种便 捷、易用、能够充分利用经验傻瓜型智能化网格剖分器一直是工程设计人员 所渴望的。目前，计算机科学领域中的人工智能、专家系统、几何造型一法 及特征识别等方面的研究成果为智能化网格剖分提供了可能性。 f 5 )有限元网格生成算法的开放问题。复杂三维实体全六面体网格生成无疑是最 艰难的个开放问题。目前虽然取得一些阶段行的研究成果，但离问题的最 终解决还有相当长的距离。仍有一些技术上的难题需要解答，值得深入研究。 当然，也期待新理论与新方法的出现。 华中科技大学硕士学位论文 1 6 本文的主要工作 1 通过对当今有限元网格划分技术进行比较全面的研究和概括，总结有限元网 格划分技术的发展趋势。 2 通过对四边形网格划分方法深入的研究和总结，提出一种基于结合边界推进 法和间接法的新的四边形网格生成方法一q m o l p h ，详细讨论其算法过程。 3 ，网格优化过程包括拓扑优化、边界优化、形状优化和尺寸优化。在四边形网 格中应用上述各种优化类型进行实例研就究，总结经验，提供解决方案。 4 将提出了一种基于角度的网格光顺算法，该算法可用于任意二维平面网格一 三角形网格、四边形网格和三角形四边形混合网格。 5 在理论和算法分析基础上，在v c + + 6 0 软件集成环境下用面向对象技术实现 本文所提出的算法。 1 7 本章小结 本章明确了本课题的目的和意义。对有限元网格的划分基本原则和各类方法进行 了描述。简要介绍了曲面四边形的各种生成算法以及算法的分类，并对各种算法的 优缺点进行比较。然后介绍了三角形形状准则、四边形形状准则，在原有基础上， 提出了一些改进。最后总结了有限元网格划分的发展趋势，对本文的主要工作做了 概述。 华中科技大学硕士学位论文 = 自；= = 自= = = = = = = = = = = = = = = = = = = = = = = = = 2 i 引言 2q m o r p h 算法 非结构化四边形网格划分有直接法和间接方法两种。在直接生成四边形网格的方 法中，b l a c k e r 和s t e p h e n s o n 提出的铺砌算法有很多优点：( 1 ) 边界敏感性。即网格 轮廓非常接近边界的轮廓，这样边界处的网格就会具有良好的形状。( 2 ) 方位不敏 感一腔。旋转或者转换既定的几何形状不会影响到最终的网格拓扑关系。转换后的网 格等同于初始网格。( 3 ) 少量的不规则点。由于共点单元的数量甚至决定光顺后的 网格单元的最终形状，因此只有少量不规则点的网格。这点对网格拓扑特征至关重 要，特别是在网格形状非常关键的边界处。目前铺砌算法得到了广泛的应用。自浚 算法提出以来，不断地得到改进，现在已经应用到三维曲面了。 尽管铺砌算法有诸多优点，但是它的些质量和应用问题应当引起注意。为了避 免单元交叉，铺砌算法推进过程中处理每排单元时需要大量的交叉计算。图2 1 a 所 示的就是一个必须进行交叉检查的简单侧子。图2 1 b 描述的是推进过程中经常遇到 ( a )b 图2 1 ( a ) 铺砌算法产生的第一排网格之问相对的单元干涉 ( b ) 在推迸中相对边界的大的网格尺寸差导致网格质量差 的边界冲突问题。如果单元尺寸相差很大，就会产生质量差的网格。 本文介绍了传统的铺砌算法的改进算法，即q u a d m o r p h i n g ( q m o r p h ) 算法。 继承了铺砌算法的优点，同时改正了它的一些弱点。q m o r p h 可被归入非结构化的， 间接的利用边界推进法的全四边形网格的生成方法。作为一种间接方法t 它能够利 用初始三角化的局部拓扑信息。但是与其他的间接方法不同的是，它能生成具有边 界敏感性的一排排单元，同时只有少量不规则点。 1 2 华中科技大学硕士学位论文 = = = ；= = = = ；= = = = ；= = = = = = ；= = = = = ；= = = = = ；= = = ： q m o t h 算法可以利用任何三角生成方法，得到初始三角网格。自从5 0 年代开 始研究网格划分以来，在二维三角化领域已经取得了很大的成功，出现了很多成熟 的划分算法，最常见的二维网格划分方法有网格推进法、递归的区域分解法( 即四 叉树方法) 、d e l a u n a y 三角化等方法。其中，d e l a u n a y 三角化( d e l a u n a y t 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 具有非常坚实的数学基础。所以本文采用d e l a u n a y 三角化来生成初始的三 角网格。 2 2 d e l a u n a y 三角化简介 在二维中，对一个点集v 的三角化是指由构成点集v 的顶点连接生成的三角形 的集合。这些三角形的并完全充满点集v 构成的多边形。d e l a u n a y 【。4 】在1 9 3 4 年引 入了d e l a u n a y 三角化的概念，若点集v 的任何点( 顶点可在圆弧上) 不在三角形的 外接圆内，则称这个圆是空圆。当旦仅当一个三角形的外接圆为空圆时，则称陔三 d e l a u n a y 三角形非d e l a u n a y 三角形 图2 , 2d e l a u n a y 空圆特性 角形为d e l a u n a y 三角形。 d e l a u n a v 三角化之所以得到支持与广泛深入的研究，主要是因为它具有系列优 良性质，最大化最小角和空外接圆是其中两个重要特性。前者说明d e l a u n a y 三角化 网格的单元质量是最优的，后者使得基于三角形外接圆插点的d e t 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 t 把平面直线图( p l a n a r s t r a i g h t l i n eg r a p h ，简称p s l g ) 作为输入。约束d t 生成算法一般有两种：一种是 分步法，即首先对点集进行无约束三角化，然后在此基础上局部修改三角网以满足 约束边要求；另一种是直接法，即一开始就考虑到输入点集及约束边的存在，在约 束空恻逐步寻找满足约束条件的三角网，直至形成最终三角网格陋”j 。 而实际应用中，如果节点分布状况不好，最终生成的网格质量是不能满足要求的。 而这些都可以通过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 特性，使 得生成的网格在单元质量和规模上都满足给定的要求。 2 3 q u a d - - m o r p h i n g 算法介绍 1 初始三角网格 图2 3q m o t h 算法流程图 4 华中科技大学硕士学位论文 = ；# ；= = = = = = = 。= = = 先对表面进行三角化，可以用任何表面三角化方法。由于d e l a u n a y 三角化有上 述优点，本文采用d e l a u n a y 来进行网格初始三角化。任何尺寸或适应信息都应该包 含在初始的三角化中。最终的四边形网格的局部尺寸大致与三角形网格一致。 2 边界定义 初始边界在初始三角化网格中定义，在三角网格中，所有只和一个三角形相连的 边就是边界边。为了保证生成全四边形网格，首先要检查三角网格中的边界边是否 为偶数，若不是，则选择在最长的边界边的中点处插入一点，更新相应的网格关系， 同时重新定义边界。 边界边的状态通过边的两个端点处与相邻边界 边的夹角来确定，由左右节点的状态来表示。如果 节点处的夹角a 。小于一个给定的值如3n 4 ，则设 定该节点的状态( 1 ) ，反之则不进行设定( 0 ) 。节 点处的夹角可以通过累加相邻的三角形的角度来 得到。如图2 4 所示，边界节点帆处的夹角吼可 近似于： a 。= a i = l 图2 4 a 。的计算 黼。s 。( 端 b ， 3 边界边分类 边界边分为四类( 如图2 5 所示) ，存放到一个链表中。根据边界边的状态对其 归类有两个目的。第一，定义哪些边必须在四边形化之前定义，侧边只有在陔边的 位为0 时必须被定义。第二，将要处理的边排优先顺序，其优先级别按顺序排列为： i l ，0 一l ，l 一0 ，o o 。 圆留 状态0状态1状态0状态1 图2 5 边界边状态定义 4 边界边的处理过程 如图所示，边界边的处理过程可以分为以下几步： 1 5 华中科技大学硕士学位论文 群攀攀 颦澄h ，- n a 生成四边形 局部光顺 图2 6边界边的处理 ( 1 ) 处理特例 在处理当前边界构建四边形之前，要检查以下几个特例：边界边之间大的过渡和 小的夹角。当两条边界边的夹角口很小时，进行缝操作。除了夹角口外，处理缝的 标准也取决于该节点处的四边形的数目。处理标准有两种： 1 口 占- ， 2 口 占2 。设q l 是与e 和e r 中较长的一条边相连的四边形，q 被分裂成 两个四边形和一个三角形如图2 8 a 所示。边界边。在中点处劈丌，与其相连的三 角形也被劈开。在9 的中心插入一点。e ，f ，e p 为新产生的边界边。与过渡缝 处理操作累死，e ，被定义为状态为l 一1 的边界边进行处理，生成一个新的四边形。 图c 所示的是经过光顺和边界边重新分类后的情况。 a 插入点b 处理新的边界c 光顺 图2 8 过渡缝一夹角大的情况 f 2 ) 确定侧边 边界边的当前状念决定了边处理的过程。状态为o 一0 ，o l ，l o 的边界边必 须首先确定一条或者两条侧边。侧边可通过以下三种方式获得：( 1 ) 使用初始三角 网格中已存在的边，( 2 ) 交换相邻的两个三角形的对角线，或者( 3 ) 通过插点劈开 一对三角形后产生的边。 图所示的是使用现有边的情况。在边乓和 e ，、之阳j 的节点n 。处要确定一条侧边。新侧边的 理想向量通过平分和e r 形成的向量得到。 p 角为圪与所有经过节点n 。的三角形的边e ，的 央角。曰最小的边作为候选侧边，并且口必须要 图2 , 9 已有边为侧边 华中科技大学硕士学位论文 ；= ；# = = = = # 一 小于某个常量( 6 ) 。 a 交换后的对角边为侧边b 插点得到侧边 图2 1 0 选择侧边 如果所有的0 都大于e ，还有两种选择：交换或者劈开对边( 图中的e 。) 。如果k 和f 。的夹角b 小于e ，则选择交换对边。如果b 大于e 或者通过交换后的e 的长度 远远超过e “和e n ，则劈开对边。后种情况下，在向量圪和边e 。的交点处插入新 点连接边e 。和边e 。，边毛就可作为四边形的侧边。以下是产生新四边形的侧 边e ，的标准的概述： 巨= e s w a p j n i n s p l i t ：nk n 。 伊 蛆虬l i 压竖掣 其他 ( 2 2 ) f 2 ) 项边恢复 四边形的底边和两条侧边确定后，下一步就确定顶边。连接两条侧边的两个终点 的边为顶边。顶边恢复过程中，要系统地交换相邻三角形的对边，直到边的端点为 预期点。图所示的是一个边恢复的例子。该例中的总共四次局部交换都是为了从三 角化中恢复边。一m ，。 9 华中科技大学硕士学位论文 = = = = ；= ；= = = = = = = = = = = ；= ；= = ；= = = = = = = = = = = = = ；= ： 黼。黼。 a b 爝爝 c 图2 1 1 顶边恢复过程 d f 4 1 生成四边形 、 四边形由边界边，两条侧边和恢复后的顶边构成。在生成四边形之前，必须清除 包含在这四条边之间的三角形。可以通过一个递归的过程来实现。从与边界边相接 的三角形丌始，递进地推进到相邻的三角形，同时删除这些三角形，其中的点和边 也要清除，这个过程一直重复到遇到顶边或侧边为止。 ( 5 ) 局部光顺与边界边的更新重分类 光顺是q - - m o r p h 算法的一个重要组成部分。新的四边形及其周围的节点位置被 重新调整来改善元素形状，包括当前边界前后的节点。由于光顺后相邻的边界边之 间的夹角会发生变化，从而影响边界边的状态以及最终四边形的拓扑关系，因此局 部光顺要在处理下条边界边之前完成。在实际应用中，新四边形的每个节点和与四 边形相连的每条边的节点都要进行光顺。边界边上的节点与边界边前后的节点处理 的方式要有所不同。 四边形单元生成后，要更新当前边界边列表。那些和三角形和四边形相接的边被 放到列表中，而那些不再和三角形相接的边从列表中清除。由于光顺的原因，周围 的边界边也有必要更新。 重复边界边的处理过程，直到边界边的链表为空。如果初始边界边为偶数，就会 生成全四边形网格。如果是奇数边界，则在网格的中心将黍4 一个三角形单元。 5 网格优化及光顺 网格优化和光顺是q - - m o r p h 算法的重要组成部分，在第三章和第四章将有详细 介绍。 华中科技大学硕士学位论文 2 4 实例 熏熬拦艟 初始网格 2 5 本章小结 第一层处理后第六层处理后 最终网格 图2 1 2q m o r p h 算法实例 本章介绍的q m o r p h 算法利用推进边界的方法来将三角网格转换为四边 形网格的涮接四边形网格生成算法。如果给定偶数边界，可以生成全四边形网格， 该网格内部不规则点少，并且通常来说边界保形。网格整体质量非常好。 2 1 华中科技大学硕士学位论文 = ；= = = = = = = = = = ；= = = = = = = = = # = = = = = = = = 3 四边形网格优化 3 1 引言 尽管q m o r p h 算法尽可能地减少了不规则点，但是由于存在一些客观原因如非 话交边界、单元尺寸过渡等，不规则点不可能完全消除。此外，当初始三角网格的 局部节点密度和连接关系不足以生成正方形时，也有可能引入不规则点。当所有的 边界边处理完毕后，执行一些优化操作能改善网格质量，减少网格中的不规则点数 量，进一步改善网格形态和质量，从而提高有限元计算的精度。在网格生成后，网 格优化过程通过改变单元的尺寸、形状和网格中单元的次序来增加网格