（计算机软件与理论专业论文）二维有限元网格自动生成软件系统.pdf

摘要 网格自动生成是进行有限元分析和计算的重要前提。在当前二维四边形网格生成 方法中，铺路算法自动化程度高、生成的单元质量好，是一种非常值得研究的网格生 成的算法。但原算法存在一些不足，对此本文做了的改进和创新，提高了算法的稳定 性和可靠性。加入网格质量优化算法和节点编号优化算法，提高了网格质量、减少了 总刚度矩阵的半带宽，引入了网格加密算法，提高了网格计算精度。基于改进后算法 编制了网格自动生成器，用此生成器产生大量实例，证明了改进算法的有效性。 关键词：有限元铺路法四边形网格网格加密 a b s t r a c t t h ea u t o m a t i cm e s hg e n e r a t i o ni st h ei m p o r t a n tp r e c o n d i t i o no ff i n i t e e l e m e n ta n a l y s i sa n dc a l c u t a t i o n i nt h er e c e n tm e t h o d so ft w o d i m e n s i o n a l q u a d r i l a t e r a lm e s hg e n e r a t i o n ，t h ep a v i n gm e t h o di sw o r t h yo fs t u d y i n g ，w h i c h p o s s e s s e sp r o p e r t i e so fh i g ha u t o m a t i z a t i o nd e g r e ea n dg e n e r a t i n ge x c e l l e n t e l e m e n t b u tt h ed e f i c i e n c yo ft h i sm e t h o ds t i l le x i s t s f o re n h a n c i n gt h e r e l i a b i l i t ya n da p p l i c a b i l i t yo ft h em e t h o d ，t h i sp a p e rm a k e ss o m eb e n e f i c i a l i m p r o v e m e n t t h eq u a l i t yo ft h em e s hh a sb e e ni m p r o v e da n dt h eh a l f b a n d w i d t h o ft h eg l o b a ls t i f f n e s sm a t r i xh a sb e e nd e c r e a s e db ya d d i n gt h ea l g o r i t h mf o r m e s hq u a l i t yo p t i m i z a t i o na n dt h ea l g o r i t h mf o rt h eo p t i m i z i n go fn o d en u m b e r t h ea c c u r a c yh a sb e e ni m p r o v e db yi n t r o d u c i n gt h ea l g o r i t h mf o rm e s he n c r y p t i o n a c c o r d i n gt ot h ei m p r o v e da l g o r i t h mm e t h o d ，t h ea u t o m a t i cm e s hg e n e r a t o rh a s b e e nd e v e l o p e d ，m a n ye x a m p l e st h a th a v eb e e nc r e a t e db yu s i n gt h i sg e n e r a t o r i sp r o v e dt ot h ee f f i c i e n c yo ft h ei m p r o v e da l g o r it h m k e yw o r d s ：f i n i t ee l e m e n tp a v i n gm e t h o dq u a d r i l a t e r a lm e s h m e s he n c r y p t i o n i i 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，二维有限元网格自动生成软件系统是 本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的 内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者躲她年当出 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使 用规定”，同意长春理工大学保留并向国家有关部门或机构送交学位论文的复印件和电 子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文。 作者签名： 指导导师签 缝盟鱼丝 耻月彳日 名：秘蛐旦月蛎 第一章绪论 1 1 选题的目的和意义 有限元法是一种十分有效的工程分析法。其特点是对几何上具有复杂的不规刚边 界、有裂缝或厚度突变、加筋以及物理上、材料具有各向异性等各种复杂结构进行分 析。它是解决各类复杂工程分析计算问题的有效途径。由于有限元法在解决实际问题 中的有效性，很快就引起了人们的重视和注意，并使其在理论上逐渐完善，应用越来 越广泛。有限元法已成为结构分析的有效方法和手段，己成为c a d 的重要组成部分。 目前有限元法的应用领域，由结构领域发展到了包括热传导、流变学和电磁场等 非结构领域。它的应用领域几乎涵盖了自然科学和工程技术的所有方面，如力学、热 传导、电磁场、声场、机械、建筑结构和渗流等复杂连续介质问题的求解计算，最近 又发展到求解多学科交叉的问题。由于该方法所涉及的原理和数学基础的普遍性和广 泛性，使得有限元法成为“适用于求解全部应用数学、连续体力学、工程和物理中的 问题”。有限元技术的发展，促使许多有影响力的有限元软件相继问世。如国外的 n a s t r a n ，a b a q s ，a d i n a ，a n s y s ，s a p ，国内的北大的s a p s p ，s a p 8 4 ，大连理工大学的j f x w 和中国农业机械化科学研究所开发的m a s 等“删。 有限元方法的解题过程总体上分三步：前处理，有限元计算和后处理。然而与有限 元计算功能高度发展极不相称的是，以网格自动剖分为主要特征的有限元前处理功能 却很弱。这严重地制约了有限元技术的发展和应用，具体表现在以下两个方面： 1 前处理建模时间长 传统的手工网格剖分或计算机辅助的人机交互半自动网格剖分过程十分复杂繁 琐，费时，费工，而且容易出错。据有关资料分析，在整个有限元处理时间中，前处 理部分占4 0 一4 5 ，后处理过程占5 5 - 6 0 ，而求解计算的过程只占5 左右。 2 前处理建模难度大 对分析人员而言，有限元仿真分析前处理建模不仅需要具备多学科的知识，而且 需要具备对实际项目进行分析的知识和经验。且这种数据准备是建立在对有限元知识 和前处理数据格式充分理解的基础上的。对于有限元知识掌握不多的工程技术人员， 要开展有限元技术应用，要完成繁杂的有限元前处理工作往往很困难。因此，只有发 展以网格自动剖分为特征的前处理技术，才能真正解决有限元仿真分析迈向实际工程 应用的障碍”。 通过以上分析表明：有限元网格自动生成技术的研究和开发，直接关系到有限元技 术的发展和实用化，因此开展基于有限元网格自动剖分为特征的有限元前处理的研究， 研究有效的网格自动剖分算法，开发二维有限元网格自动生成软件，具有重要的理论 价值和实际意义。基于上述原因，本文研究了二维有限元网格自动生成软件系统。 1 2 网格分类及生成算法介绍 1 2 i 网格的分类 现有的网格生成方法不下数百种，但这些方法大致分为两大类睁7 ：结构化网格和非 结构化网格。结构化网格是指网格区域内所有的内部节点都具有数量相等的毗邻单元。 一般来讲，二维结构化网格的单元全为四边形。结构化网格有许多优点： 1 它可以保证边界附近的单元与边界对齐，适用于流体力学和表面应力集中等对边 界较为敏感的问题的计算。 2 网格的生成速度快。 3 网格质量好。 4 数据结构简单。 结构化网格生成技术的缺点也是明显的，它只能对四边形区域( 或者经过映射后能 转化为四边形区域) 进行剖分。在处理复杂区域时，必须事先人为地将复杂区域划分为 若干简单的四边形区域。近年来，随着计算机技术和数值方法的快速发展，有限元方 法日益深入到工程实践，求解区域越来越复杂，结构化网格生成技术就显得力不从心 了。与结构化网格相对应，非结构化网格是指网格区域内的内部节点具有数量不等的 毗邻单元。即与网格剖分内的不同内部节点相连的网格数目不同。根据定义可以知道， 非结构化网格中的部分区域可能形成局部的结构化网格。非结构化网格技术从六十年 代开始得到了发展，主要是为了弥补结构化网格不能够解决任意形状和任意连通区域 的网格剖分的欠缺。由于非结构化网格生成技术比较复杂，随着求解区域复杂性的不 断提高，对非结构化网格生成技术的要求也越来越高。在非结构化网格生成技术中， 只有平面三角形网格的自动生成技术已经比较成熟，平面四边形网格生成技术j 下在走 向成熟。 根据应用领域的不同，可将非结构化网格技术分为两类：应用于差分法的网格生成 技术和应用于有限元方法的网格生成技术。应用于有限元计算的网格，生成的网格只 要满足一些几何形状上的要求就可以了，相对比较自由：应用于差分计算领域的网格， 除了要满足几何形状要求以外，还要满足某些特殊性质，垂直正交、与流线平行正交 等，技术实现上相对困难一些。本文主要讨论应用于有限元计算的二维非结构化网格 生成技术。 i 2 2 网格生成算法综述 在国外，有限元网格生成方法研究领域已取得许多重要成果，形成了独特的方法论 体系，提出了许多有效的算法并研制出一些成功的工程化软件产品。许多学者对网格生 成方法研究进行了概括和总结。如l ( h o - l e ”1 曾将1 9 8 8 年以前的算法进行了分类，是以点 和单元产生的先后顺序作为分类基准。有限元分析的单元类型是多种多样的，最常见 的一般是三角形单元和四边形单元。总的说来，三角形网格发展至今已相对成熟，如 d e l a u n a y 算法嘲。但由于用四边形网格进行的有限元分析的结果精确度更高，所以很多 人倾向于研究四边形网格生成算法，以发掘其在有限元分析中的优点，提高有限元计 2 算的精度。算法的种类是多种多样的，而且一些新思想新算法还在不断出现，难以用 一个统一的准则将它们分类，根据算法的几何分析域的特点，大致将各种算法归纳为 下面几类： 1 推进前沿法( a d v a n c i n gf r o n tm e t h o d ) 推进前沿法现在已经成为一种常用的三角形网格生成算法。乔治梅森大学的 r a i n a l dl o h n e r “和香港大学的s ，h l o “”等人对该方法作了深入的研究。推进前沿 法最初用于生成非结构化的三角形网格。 该类算法的基本思想是：从几何区域的边界出发，由外向内一次移去一个三角形， 迭代执行直到最后剩下一个三角形为止。从几何区域的边界开始，定义一个前沿，在 前沿上满足一定条件的地方生成一个符合要求的三角形单元，同时更新前沿，如此不 断重复，直至前沿为空，网格生成结束。运用这种方法时，可引入单元尺寸函数，控 制单元尺寸变化。如图1 1 所示，先把几何区域的边界离散，形成一个由边界节点组 成的环，把它定义为初始前沿，然后进行以下三步迭代：( 1 ) 检查前沿上每个节点的内 角，确定新生成单元的位置。( 2 ) 在满足条件的节点处生成一个单元。( 3 ) 更新前沿， 把新生成的边界加入前沿中，删除旧边界。推进前沿法最早由s ll o 提出，应用于平 面区域三角形网格全自动生成，取得很好的效果，后来p e r a r i e 将这个方法进行推广， 用于二维自适应网格生成。此后，l o h n e r 把这种技术推广到任意形状区域的三维四面 体网格生成，l o h n e r 和b o n e t 针对推进前沿法存在大量搜索查询操作的特点提出了一 些有用的数据结构和算法，大大提高了推进前沿法的效率。通用有限元分析软件a n s y s 已经采用了l o 的算法“。 推进前沿法只需要给定区域边界便可生成网格，但这种方法需要相对较长的运行 时间。推进前沿法生成网格具有可重复性，即对于相同的几何边界，生成的网格也是 相同的；推进前沿法具有适应性广，通常情况下单元质量高等优点。缺点主要是由于 没有理论基础，不能保证算法的收敛性，成功与否取决于个人对特定问题的经验积累。 ( a )( b ) 图1 1 推进前沿法示意图( a ) 边界初始化( b ) 网格生成过程 2 d e l a u n a y 三角化方法 运用d e l a u n a y 准则进行三角形网格生成是迄今为止最成熟的网格生成算法。 d e l a u n a y 准则可表述为：对于给定的平面点集进行三角化，其中的每个三角形的外接圆 不包含点集中其他任何点，如图1 2 。如果满足d e l a u n a y 准则，那么所有的三角形的 最小内角之和取得最大值，而所有的三角形的最大内角之和取得最小值。d e l a u n a y 准 则是由俄国数学家b o r i sn d e l a u n a y 于1 9 3 4 年提出的，但是直至二十世纪八十年代 3 初才由c h a r l e sl a w s o n “”和d a v ew a t s o n “”运用该准则提出平面点集的三角化方法。 随着有限元技术的迅猛发展，t i m o t h yb a k e r 、n i g e lw e a t h e r i l l ”和p a u l l o u i s g e o r g e “”各自将该算法运用于平面区域三角形网格自动生成。 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 网格生 成算法。 新节点的生成：最简单的方法是从覆盖几何区域的规则格栅得到所需节点的位置， 可事先定义一个尺寸函数，插入新节点直至满足这个尺寸函数的要求：也可以反复的在 三角形形心处插入新节点。 c h e w ”和r u p p e r t 。”提出在每个三角形的外接圆圆心处插入新节点的方法。当按 一定的顺序插入节点时，可生成质量很高的三角形网格。卡内基梅隆大学( c a r n e g i e m e l l o nu n i v e r s i t y ) 的j o n t h a ns h e w c h u k 运用此算法开发了二维网格生成程序，源代 码可免费下载”。 r e b a y 汹1 提出一种v o r o n o i 线段插点法( v o r o n o i s e g m e n tp o i n ti n s e r t i o n m e t h o d ) 。v o r o n o i 线段是指连接两个相邻三角形外接圆圆心的线段。按照单元尺寸的 要求，在v o r o n o i 线段上选取某一位置插入新节点。运用这种方法，可生成结构化程 度很高的三角形网格，即每个内部节点周围有六个三角形单元。 另一种方法是由d a v i dl m a r c u m ”提出的前沿推进插点法，新节点由边界向区域 内部逐渐插入。这种方法在边界处能生成比较规整且结构化程度高的网格。m a r e u m 就 此开发了一个二维的网格生成程序e r c ”1 。 h b o r o u c h a k i 。”开发的网格生成程序g s h 3 d 中，运用了一种更为直接的插点方法： 根据一定的尺寸要求，在区域内部的三角形边上，按照单元尺寸要求布置新节点，然 后根据d e l a u n a y 准则生成三角形网格。反复进行这个过程，直至单元尺寸满足要求。 节点生成方法对d e l a u n a y 方法形成的网格质量具有重要影响，是d e l a u n a y 方法 重要的研究内容。上述是几种主要的插点方法，此外也有许多方法，但思想与上面几 4 种方法均大同小异，不再赘述。 3 映射法 映射法是早期出现的较优秀的一种方法，映射法一般先以手工方式将复杂区域分 解为简单区域，将子区域映射到易生成网格的规则区域，它只能算是一种半自动的方 法，对规则均一的区域，适用性很强，所以得到了较大的发展，并一度成为商用软件 的主要方法。映射法的原理是把待分析图形经过坐标变换，映射成形状规则的几何图 形，然后再对新的坐标系下的规则图形进行网格划分。划分结束后，再把划分结果转 换到原坐标系中，于是在原图形上就得到了通过坐标变换映射而来的网格划分图形。 这里坐标变换就是通过映射函数实现的。 映射方法主要分为如下几种： ( 1 ) 保角映射 保角映射处理多于四个边的单连通区域，适应范围广。但它没有流行起来，因为 单元形状和网格密度难于控制”7 “。 ( 2 ) 拉普拉斯映射 它是利用l a p l a c i a n 方程的有限差分形式产生节点，x y 平面上的一个二维结构 一对一地转化到可在整数点分划的i j 平面上”1 。 ( 3 ) 等参映射 ，它是超限映射的一种特殊情形，其四边形四个边的曲线为拉格朗日多项式表达， 对边具有相等分割，通过适当的节点记号格式可以使目标刚度矩阵有最小半带宽，故 单独提出。 4 节点连接法 节点连接法也称填充法，是一种利用区域内离散点生成网格的方法。该方法首先 要在待解区域内产生一系列合适的节点，然后再以一定的规则把这些节点连在一起形 成单元。节点连接法的时间耗费很高，但是比起其他方法稳定性较好，易产生形状较 好的网格。产生网格节点的方法有c a v e n d i s h 9 ”随机节点生成法，l o 。”非随机节点法等。 在二维划分中，c a v e n d i s h 采用划分区域来辅助定义区域网格密度，在每个辅助区 域用正交点阵生成内部结点，s h a w 等人用1 ：3 的矩阵点阵辅助生成内部节点，这种 点阵使得内部的相邻三点组成正三角形。l o 用水平线来辅助生成内部结点。这三种方 法在形成三角形网格时都是从边界开始，向内寻找一个最优点形成一个角单元。并修 改边界，因为要判断单元之间的覆盖，选取合法的最优点非常费时。 节点连接法用来生成三角形的算法已经比较成熟了，但生成四边形的算法还有待 进一步完善，并且该方法在边界上的单元质量不够理想。当前，节点连接法中应用 d e l a u n a y 准则生成三角形网格的算法最广泛。它与普通填充法的区别在于它是根据单 元外接圆内部不包含其它点的准则来生成三角形网格。 在二维划分中，j o e 9 ”的方法是将复杂域分解为凸多边形域，再对每个凸域用缩 小多边形生成内部结点，并形成凸域的d e l a u n a y 三角划分( 以下简称为d 划分) 。 s a p i d i s 用增加边界点的方法来保证边界一定包含在d 划分中。该方法先生成复杂域内 的点集的凸包的d 划分，然后对于不包含在d 划分中的边界边的中点并入点集得到新 的d 划分，直到所有的边界都包含在d 划分中时。这种弥补边界的方法可能会引入不 理想的过密点分布，从而导致畸形单元。w e a t h e r i n 用以下将讨论的前沿法形成三角单 元时，同时保证形成的网格是d 划分。 5 拓扑切割分解法 切割法在保证拓扑结构连续性的基础上，每次切下一个单元。在二维划分中， s a d e k 3 用切割法实现了二维复杂域的三角形网格划分，准则是使切下的单元尽可能地 接近正三角形。d e l j o u i e r a k b s h a n d e h 先将多连通域分解成凸多边形再对其进行切割 划分，该法对边界离散化时采用等比数列法。并在切割单元时将边界密度平滑地传播 到形体内部；z h u 。”研究了用切割法生成复杂域的四边形单元网格，此法思路简捷，能 实现全自动网格划分并较好地传播边界网格密度，但它的包含和覆盖检测计算量很大。 6 栅格法 栅格法又分为栅格叠合法和四叉树法。栅格叠合法最早由t h a c k e r ，g o n z a l e z 和 p u t l a n d 提出，它是将栅格置放于物体之上。既可在栅格的规则点处布置节点，也可 在栅格单元中随机布置结点，容易得到均匀网格，然后对栅格与物体求交，将在物体 外的栅格去掉，物体内的栅格保留作为网格。在边界处的栅格需要变形，也就是要调 整节点的位置以满足边界条件的要求，最终产生的网格内部单元完全一样，只是边界 单元不同。 在二维划分中，y e r r y 和s h e p h a r d 等人。7 1 用四叉树编码法发展了该法。这种方法 基于二维域的四叉图树表示，后来又对其进行了改进， 称之为改进的四叉树法。改进四叉树法在二维区域的 四叉树表示上作了两点改进：一是限定了离散深度以 使所有单元大小差不多；二是引入了c u t - - n o d e ，把在 形体边界的正方形改为与边界相交的多边形。后来有 人分别在提高算法对复杂形体处理的可靠性和减少单 元数目方面进行了改进。改进的四叉树法自动化程度 很高，很容易与造型系统集成。缺点是复杂形体的边 界单元质量不好，初始正方形的选定也会人为地造成 畸形边界单元。这类方法有很大的适应性，缺点是复 杂形体的边界单元的质量不易控制。 ， l | 书 | f | | 、 l l 、卜止il h 一l j 一 r 图1 3 四叉树法 在国内，对网格技术的研究晚于国外，但发展很快。随着网络计算机发展，为了 满足有限元网格计算和分析的实际需要，国内学者也提出了很多好的网格生成算法， 满足了在实际应用中对网格计算的要求。如由于映射法不能适应物理问题中网格疏密 过渡的要求，即大单元的对边单元分割数不等的情况下，网格的生成比较困难。对此 李华等提出了一种正方形亲单元上实现网格在两个坐标方向均能过渡的全四边形单元 生成方法随”，该方法允许正方形周边节点任意分布，并可以对单元密度进行控制，可 以有效地在两个方向上实现网格疏密过渡、对局部点和区域进行局部网格加密处理， 将该法和映射法结合解决了用映射单元法对结构进行四边形单元划分时存在的网格过 渡的这一关键问题。网格向前推进生成算法存在的主要问题是：当边界离散点及起始 点确定后，网格便确定。而实际应用中往往有一些特殊的需要如要求网格最长也不能 超出某给定值时上述算法不能处理，为此吴淑芳，姚圣雄提出了基于约束网格向前推 进生成算法，该算法给出了两种约束：尺寸约束和角度约束。运用该方法可有效的 解决了上述存在的闻题。 1 3 网格生成技术的发展趋势 有限元网格全自动生成系统的研究是近年来的一个研究热点，正如前面所说，在 众多研究者的辛勤劳动下，已经出现了很多种特性各异的算法，它们其中的很多种都 为流行的商业网格自动剖分系统所采用，并经过实际使用证明了它们的有效性和实用 性。但是，前处理技术仍然存在一些问题，这些问题的存在也指示了有限元网格自动 生成技术研究的方向： 1 和实体造型系统的集成。一个有限元自动分析系统的基本要求就是能够不通过 用户的交互作用，直接从c a d 造型系统中所提供的完备的几何描述中获取有限元计算 和分析所必须的数据。这就要求有限元网格自动生成算法能适应任何实体造型，而目 前的有限元建模技术并不能满足这样的要求。随着c a d c a p p c 酬的发展，特别是c i m s 的发展，使得几何造型系统和有限元网格自动生成系统的集成成为发展的必然趋势。 2 提高计算精度。精度的提高是有限元分析和计算技术的一个重要的任务，对于 前处理技术来说，这包含两方面的含义：( 1 ) 提高网格精度，也就是说改善单元质量。 网格精度直接关系到有限元计算的精度，各种方法自动生成的网格单元由于边界条件 的限制而难以完全保证网格的质量符合计算和分析的需要，尽管可以通过各种单元光 滑和单元修正技术进行调整，改善单元质量，但在复杂区域和复杂边界情形时，这种 改善总是有限的，因此如何进一步提高生成单元的精度仍然是前处理技术研究课题之 一。( 2 ) 自适应有限元网格生成技术。自适应算法通过加密网格来提高计算精度，这种 算法有效而且收敛快，在各个领域自适应算法都将会有更大的发展。自适应算法实现 的关键就在于如何进行误差估计，在不同领域中的不同问题的误差估计是不尽相同的， 这也是目前有限元前处理技术发展的主要方向之一。 3 并行计算算法的研究。随着计算机技术的发展，并行计算技术在工程计算和分 析中越来越凸现其优势。而现有的大部分自动网格剖分算法在本质上都是串行的，因 此，如何开发出适合于矢量或并行计算机的高效的网格自动生成的并行算法就成为前 处理技术研究的一个方向。 4 智能化的网格生成以及基于专家系统的有限元模型的自动生成。一是网格生成 7 要体现人的意志，充分利用以往人工剖分经验和要求，来指导理想的网格剖分。另一 方面，仿真技术要求前处理技术模拟工程技术中的各种问题，如施工过程、施工优化 等等，这也指引前处理技术的进一步发展的方向。 5 集成化的网格剖分系统的研制。基于以上的研究成果，研制能够将几何造型系 统、网格剖分系统、自适应分析系统结合的集成化、智能化、全自动化的网格剖分系 统。 1 4 本文研究的主要内容及组织安排 本文研究的主要内容是以改进后的铺路算法、网格局部加密算法和网格质量优化 算法为基础开发出一个二维有限元网格自动生成系统，此系统能够实现网格的自动生 成、加密、稀疏及网格质量的优化和网格节点编号优化。生成的以四边形为单位的网 格满足有限元网格计算的要求。 本文章节安排如下： 第一章主要是对现有的二维网格生成算法作了回顾，比较了结构化网格与非结构 化网格的优劣，简单介绍了网格优化技术及网格未来的的发展趋势。 第二章将具体介绍铺路算法原理，以及对该算法作的改进： ( 1 ) 删除了原算法过于复杂的节点分类和原始体判断。 ( 2 ) 改进了边界和内部节点的光滑方法。 ( 3 ) 在网格生成前对固定边界进行先处理，增强了程序的适应性。 ( 4 ) 增加了生成新节点时的越界处理，程序的健壮性得到增强，同时使相交处 理得到极大简化。 ( 5 ) 原方法中待一层单元生成完毕后再进行相交处理，本文则采用每次生成新 单元时都进行相交判断，一旦发现相交情况发生，立即转入相交处理模块， 使相交处理得到极大的简化。 第三章主要介绍网格局部的加密算法，采用此加密算法可以对需要加密的部分网 格进行加密，提高了网格的计算精度。此外还介绍了网格质量优化和节点编号优化算 法，经过优化后网格质量更高，利用节点编号优化算法，减少了网格的半带宽，节省存 储容量，而且能够提高计算速度。 第四章重点介绍了铺路算法的程序实现过程。 第五章主要是对本文所编制的网格自动生成系统介绍，并利用此系统生成一些网 格实例，证明了改进后算法的有效性。 第六章对毕业论文进行了总结。 8 第二章基于铺路法的网格生成算法 在二维有限元计算中，主要采用三节点三角形单元和四节点四边形单元。三角形 单元的网格自动生成技术已经比较成熟，但其精度没有四边形高，所以人们更倾向 于使用四边形网格单元。近2 0 年来，已研究出很多种生成四边形网格的算法“1 删， 主要有映射法、四叉树法、推进前沿法和铺路法等。这些方法针对具体的分析对象 时都显示出其自身特有的优点，其中有些方法已被装入现代有限元分析软件包中得 到了广泛的应用。本文采用的铺路法生成的网格质量高，特别是边界单元( 接近正方 形) ；并且自动化程度很高，只需给出边界和单元尺寸，不需要过多的人为参与。但原 算法对于边界不规则区域易出现交叉现象，判断和解决交叉问题既复杂又耗时，处 理不好将直接影响网格生成的进程。因此，本文对该方法进行了改进： ( 1 ) 删除了原算法过于复杂的节点分类和原始体判断。 ( 2 ) 改进了边界和内部节点的光滑方法。 ( 3 ) 在网格生成前对固定边界进行先处理，增强了程序的适应性。 ( 4 ) 增加了生成新节点时的越界处理，程序的健壮性得到增强，同时使相交处理 得到极大简化。 ( 5 ) 原方法中待一层单元生成完毕后再进行相交处理，本文则采用每次生成新单 元时都进行相交判断，一旦发现相交情况发生，立即转入相交处理模块，使相 交处理得到极大的简化。 用改进后的网格生成算法，降低了网格生成的难度，提高了网格生成速度，而且对网 格的生成更加容易控制。 2 1 算法概述 铺路法的基本思想是由区域的边界向内部一层一层生成单元，直至最后整个区域 都铺满单元为止。如图2 1 所示。如果网格单元之间发生重叠，则采用相交处理以生 成有效的单元。本章将首先定义一些术语和说明网格生成前需要输入的信息：其次，绘 出了铺路法操作流程；最后详细介绍各步骤。 t j 一 图2 1 铺路法的生成过程：( a ) 初始边界，( b ) 初始边界网格生成， ( c ) 动态边界网格生成，( d ) 网格生成完毕 9 铺路法始于一组或多组有序的、封闭的节点环，不需要预先配置好内部节点，内 部节点和单元都在网格生成过程中自动生成。外边界按逆时针方向由外向内生成单元， 而内边界则按顺时针方向由内向外生成单元。内外边界相交时采用相交处理生成一个 新的外铺路边界。 在每层单元铺路开始时，选择内角最小的节点作为起始点，在铺路过程中，这些 固定边界上的节点不允许变动。 为了下面叙述的方便，结合边界的示意图( 图2 2 ) 介绍几个术语： 1 固定边界指几何区域的初始边界。固定边乔分为外固定边界和内固定边界， 对于一个待剖分区域，有且仅有一个外固定边界，且组成此边界的节点环不能 相交，方向为逆时针。内固定边界可以有多个，方向为顺时针。所有的固定边 界都不能相交。 2 铺路边界是指铺路过程中区域内部网格的动态边界，它只是一个临时的概 念，在铺路过程中不停的变化着，当网格生成完毕，它也就消失了。 3 固定节点指位于固定边界上的节点。 4 可动节点指位于铺路边界上的非固定节点。 5 铺路节点指位于铺路边界上的节点，它既包括了固定节点，又包括了可动节 点。 6 节点内角指在铺路边界上，该节点与前一个节点和后一个节点间连线的夹 角，顺时针为正。 7 层由一系列节点相连接而构成的单连通封闭曲线。 外固定节点外固定边界 图2 2 内外铺路边界示意图 对于一个待剖分区域，必然存在一个外固定边界，但可有几个内固定边界，固定 1 0 边界之间是不可能相交的，它保证了区域之间的相容性。与固定边界类似，铺路边界 也可分为内部边界和外部边赛。尽管在开始的时候只有一个外铺路边界，但在生成过 程中，可能产生几个外部铺路边界。 为了保证生成全四边形网格，每条铺路边界都必须包含偶数个节点。网格中单元 的尺寸由铺路边界上的节点间距决定，而铺路边界上的节点间距是由初始的固定边界 上的节点间距决定的。在整个网格生成过程中，尽量保持这种间距大小的不变。这样， 用户就可以利用边界上节点间距来控制网格单元的大小，并且边界上的节点间距不要 求一致，能够非常好地处理单元大小之间的过渡。 2 2 算法数学原理 2 2 1 铺路法的基本操作 ， 用铺路算法生成四边形网格，为了保证网格的生成质量，该算法包括了很多的操 作步骤，在实际生成网格过程中，必须严格控制这些操作步骤。基本操作如下： 1 层的选择选择产生下一层单元的起点和终点。 2 封闭检查在网格生成过程中必须时刻检查铺路边界的节点个数，确保多于六 个节点。如果节点数等于或少于六个，则使用封闭处理技术来结束此边界。 3 生成单元在铺路边界上生成网格单元，与原方法一层层生成单元不同，本文 采用一个个生成单元，如果发生相交情况，立即转入相交处理模块。 4 光滑处理在网格生成过程中，对可动节点进行调整和光滑处理，以改善网格 的质量和提高铺路边界的光滑度。 5 缝合处理这包括两个方面，一是小角度缝合，对铺路边界上具有较小内角的 节点处进行缝合：二是过渡缝合，针对在铺路边界上相邻边长的比例过大的时候 需要处理。 6 层的调整为了保证单元尺寸不至于太小或太大，对新生成的层进行楔入单元 和删除单元的操作。 7 相交处理在网格生成过程中，检查铺路边界是否与自身相交或与其他铺路边 界相交，如果相交，在相交处连接相交的铺路边界，分割成两个新的铺路边界或 者相连形成一个边界。 8 网格质量优化整个网格划分完毕后，对网格节点和单元作优化操作，提高单元 质量。 2 2 2 算法流程图 铺路过程实际上是一个重复迭代的过程，如何控制上述的操作步骤在整个网格生 成中的顺序，是能否生成高质量网格单元的关键。铺路算法的控制流程如图2 3 所示。 其中n 代表的是铺路边界上的节点数目，当n 小于6 时不再产生节点，要进行封闭处 理。 开始 上 输入边界节点信息 哥 2 2 3 初始边界节点的条件及层起始点的选择 对于一个指定的区域，首先要根据实际的要求离散初始边男，形成组或几组连 续的、有序的、封闭的初始边界节点。为了保证在区域内生成的单元全部为四边形单 元，要求初始边界的节点数目为偶数，否则会产生三角形单元。 在铺路过程中，新一层网格节点的位置是由上一层铺路边界节点来决定的。因此， 选择合适的铺路节点为起始点对于维持边界单元的灵敏性、保证网格单元随边界的走 向而变化是很关键的，同时也能减少不规则节点( 节点周围的单元数不等于4 ) 的数目和 控制不规则节点的位置。为了生成网格节点的需要，对节点内角按大小进行分类。具 体的分类如下所示： 1 终止节点a 1 2 0 0 + d 2 边节点1 2 0 0 + 6 e 矧8 0 。( 2 1 4 ) i l a其它 图2 1 2 角度的调整 在角度调整过程中，点n ，的位置变化量。为： c = p e ：一p -( 2 1 5 ) 角度调整有助于保持单元边的相互垂直和促进铺路边界的光滑性。对于铺路边界上只 相邻两个单元的节点n 。，其最终的位置变化量。为： 。= 垒 _ 型生( 2 1 6 ) 2 尽管这一步的算法操作起来比较复杂，但它能有效的调整单元的大小和形状，保证整 个铺路过程的顺利进行。式( 2 1 4 ) 中，在原铺路法的基础上加入了角度口作为判断条 件，其主要目的在于使生成的网格更加均匀。特别是内部边界为圆周，向区域内部生 成单元时，可以非常有效地避免光滑处理时单元被压缩的情况发生。 2 内部光滑 边界光滑之后紧接着进行内部节点的光滑处理，为了提高方法的效率，同时边界 的变动对于离边界较远的内部节点影响很小，故只对边界附近三层单元内的节点进行。 本文采用有效且简便的质心光滑方法，该方法的基本思路如下：包含某内部结点的所有 单元的质心构成一个多边形，将该内部结点调整到这个多边形的质心位置，网格更优， 其计算公式如下： 工。寺弘 汜 一瓦1 萎y j ， 其中n 。为结点i 周围的单元总数，x ，和y ，为单元j 的质心位置的横坐标和竖坐标的值。 2 2 ，6 缝合处理 在生成网格的过程中，新生成的铺