（计算机应用技术专业论文）平面区域有限元三角网格剖分算法研究.pdf

山东大学硕士学位论文 1 给定区域边界的右螺旋a f t 改进算法 本文对于如何决定当前前沿点的生成位置提出了一种针对区域的外边界的 右螺旋a 盯方法，主要思想体现在：首先对区域边界按等分原则进行离散，生成 初始活跃前沿节点和前沿边，然后依次按逆时针方向即右螺旋的方向，选定活跃 前沿边，按等边三角形原则生成节点和单元，从而提高了生成三角剖分网格的效 率和质量。同理，对于区域的内边界可以采用按顺时针方向即左螺旋a f t 方法。 2 给定边界的基于栅格的a f t 改进算法 结合栅格法和a f t 方法，提出一种新的三角网格剖分方法。通常的栅格法是 在将要剖分的区域，用生成的矩形栅格罩住该区域，将在待剖分区域外部及和边 界相交的网格删除，只保留在区域内部的网格，然后在边界处，对栅格进行剪裁 以保证区域边界的完整性。栅格法能产生较好形状的内部单元，但边界单元的形 状较差。而a f t 方法能产生较好形状的边界单元，正好可以弥补栅格法的不足。 另外，本方法提出了用三簇相互交成6 0 0 的平行等距扫描线生成栅格，使区域内 部可以生成质量更佳的正三角形网格。 3 基于两相邻前沿边的a f r 改进算法 本文在分析了两点前沿推进波前法、三点前沿推进波前法和两点三点前沿结 合推进波前法算法的优缺点的基础上，提出了基于两相邻前沿边的a f t 改进算 法。主要思想是以与两相邻波前边相关联的有向线段大小及其夹角，决定网格单 元和节点的生成方式，特别是对夹角小于3 0 0 和夹角大于1 8 0 0 时的处理方法。解 决了只能剖分单连通区域、对于夹角过小或过大的情形未给予考虑的问题，使得 三角网格剖分的效果更佳。 另外，还研究了基于几何多格子方法的三角网格精化算法，分析了其需要对 非协调的三角形作多次协调迭代才能完成，精化剖分的效率较低，精化网格数量 的增加基本上是以两倍的方式增加的两点不足，提出了基于最小权原理的一种新 的改进精化算法，并证明了该改进算法提高了三角网格精化剖分的效率和剖分网 格的数量及质量。 关键词有限元朗格生成；三角网格剖分； f t 方法；精化算法；最小权原理 山东大学硕士学位论文 a l g o r i t h r n i ci m p l e m 即to f 岍m e i l o d ( a d v 锄c i n gf 埘l t1 色d m i q u e ) i l lp l 锄a rf i t i i t e 证锄四em e s hg e n e r a t i o n ，a l l dm en o d 舒，v e 咖rs e g m 翎馈t l l ep o s i t i o nr e l 砒i o n s h i p b e t w e e n 硒a n 西em e s h 豁a n dp o l y 粤mm e s l l 嚣d l 埘n gt l l ep r o c 镐so f 也eg e n 盯撕0 n 1 1 l ed i m c u i t i 髂o fa f tm e m o d 越ea l s o 锄a l y z e d ，锄dt l l r e ei m p m v e da i g o r i t l l 脚m p mf o 内剧db 鹊e do n 血ep r i n c i p l eo fm i n i 咖mp o w e rt o g e l h e r 埘血f e 咖采p o i n t s p r o p e 而器，柚i m p r o v e dr e f i n e da l g o r i t l l ma b o u tb 嬲e do ng m e m c a lm i i i 缸- g t i di s p u tf o n ：l 枷a tl 喊s e v e r a lp r o b l 咖sn e e d e dt ob es o l v e di l lm em e s hg 哪枷o n a l g o r i m ma r es i m p l yp r o s p e c t e d s 吖e r a ld i 衔c i l l t i e sd u r i n gt h ei m p l e m e n to f 朋叮a l g o r i t l l ma m 咖d i e si nt i l i s 伽e s i s a n dt h r e ei i n p r o v e d8 1 9 0 r i t h r 璐a r ep u tf o n 】l ，a 】r db 罄e do n1 1 1 器es t i l d i 器 1 h 印r o v e da l g o 枷l n l o f t l l e 啦m h e l i x 岍i n 垂v a r 鼯 a i 两n ga th 。wt o 如d g et h e 砚i r r 鞠tf b n tp o i n t ，t l l em e s i sp u t sf o r w a r das p e d 最c r i 曲t h e l i xa f tm 抽o di l l 西v e na r e a 、】l 机i c hm a i ni d e 雒m 眦i f 融t l l a t6 r s yb o 吼d a r y s i d e ss h o 试db ed i s p e f s e da c c o r d i r 喀t ot 王l ep r i n c i p l eo fa v e r a g ed i 、，i s i o nt 0g e n e r a i e t h e 研百n a la c t i v ep o i n t 锄d 舶n ts i d e ，锄dt h e i lc o u n t e r - d o c k 谢s e ，n 锄e l y ，也ei i 曲t h e l i xd i r e c t i o n ，t l l ea c t i v ef 如n ts i d 嚣a r es d e c t e d ，n e wn o 曲s 锄dm e s h 郎b e i n g g 跚e r a t e db a s e d0 nm ep f i n c i p l eo fe q i l i l a t e r a lt r i a i l 罾et oi n c r e a s em ee m c i c y 锄d q u a l 砂o fg e i l 枷n gt f i a n 掣em e s h e q u a l l y ，1 l l ei n s i d es i d 鼯o f m ea r e ac a i lb ed e a l t w i 也d o c k 、 ，i s e ，n 锄e i y m el 硪h e l i xa f tm 确o d ， 2 h n p d o v e dg r i d b 嬲e da l g o 栅l mi n 百v e l la m c o m b i n i n g 鲥dm 砒o d s 锄da f rm e t h o d ，t l l i sm e s i sp 吣f o n 盯dan 哪 试卸百em 嚣hg e n e r a d n gm e m o d ，t h ec o i n m o n 鲥dm e m o di s t ou g e n e r a t e d 阳c t 卸翻eg r i dt 0c a v e r n l ea r e aw l l i c hi sg o i n gt ob ed i s s e c e d ，锄dt l l 锄协d e l e t et 1 1 0 s e 鲥d so u t s i d et h ea r 肌dt l l o s em 砒i n t e r s e c t 谢mt 圭l eb 0 眦d a 哆o ft h ea r e 乱o f l l y t l l o s e 曲d sc o v e r e db yt l l er e 比m 西e 撕l lb ep r e s e r v e d 0 nm eb o 眦出观t h e 鲥d 撕l l b ec l i p p e di l lo r d e rt og u a r a n t e et h ei m e 鲥t yo f1 l l ea r e ab o 吼d a r yt h e 鲥dm e 吐1 0 d 懈u a l l yr e s l l l t si ni 蛐e rm e s h e sv v i t i lr e g u l a rs h 印e ，b u | t h es h a p ea 1 0 n gt 量l eb o u n d a i yi s l l s l l a l l yn o t9 0 0 d ；w h i l et l l e 柚丌m e t l l o dc 锄g e n e f a 钯b o l l d a r ym e s h 鼯w i t h9 0 0 d s h a p e ，m 峪也ed i s 蜘t a g ei sm a d eu p h la d d i t i o n ，m i sm 霸h o du s 嚣m r p a r a l l e l e q i l i d i s t a i l ts c 锄n i n gb e 锄s 砌c hi n t e r s e c ti i l t oa 仃i a l l 掣e 、】l i i t l l6 0d e 乒谢me 扯h o i l l e r 蕾0g e r a l e 鲥d s ，嬲ar e s m t ，i i l s i d em ea r e a ；b e t c e re q u i l a f e l 甜t r i ralleleqilidistailtsc锄ningbe锄s砌chintersectiiltoa仃iall掣e、】liitll60de乒谢me扯hoiller蕾09erale鲥ds，嬲aresmt，iilsidemearea；betcerequilafel甜trian西e鲥dwiii 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：函碍劣孽日 f 、- 】一叮忆 论文作者签名：送型笪型兰 日 期：之立：竺 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：建邋导师签名：1 丝日 期：习谚，o 寸 期：趔! ! ：竺 山东大学硕士学位论文 1 1 课题背景 第1 章绪论 近几十年里，随着计算机技术的飞速发展，有限元法无论在理论还是应用上 都取得了巨大的成功，已经成为工业工程设计与分析的重要工具，越来越多的庞 大面且复杂的工程设计都是用有限元法来模拟的。使用有限元法进行工程问题分 析时，其基本过程大体分为三个阶段：有限元模型的建立和数据输入( 即生成有 限元模型) ；用分析软件进行工程计算；分析结果的后处理及评判。有限元分析 的主要困难是分析模型的建立。本文的研究内容属于有限元法的建模或前置处理 领域，是有限单元法在工程实践中有效运用的必要组成部分，是c a d c a e 技术的 重要分支。在有限元的前处理过程中，网格剖分技术是一个核心内容，是生成满 足有限元分析程序要求的有限元网格的关键步骤，也是前处理的重点和难点。网 格剖分的质量和速度直接影响到有限元软件的推广和使用。 1 1 1 有限元法 有限元法( f i n i t ee l e m e n tm e t h o d ) 这个名称，第一次出现在1 9 6 0 年，当 时美国加州大学伯克利分校的飞机结构工程师克劳夫r w c l o u g h “1 在一篇平面 弹性问题的论文中应用过它。几乎与此同时，我国中科院计算所的冯康教授也独 立提出了类似的方法“。2 0 世纪7 0 年代中期，复旦大学数学系与江南造船厂合 作，将有限元法应用于船舶设计计算，使有限元法在中国工程界开始大规模应用。 但是有限元法分析的概念却可以追溯到2 0 世纪4 0 年代。1 9 4 3 年，c o u r 8 n t 第一 次在他的论文中，定义了在三角形域上的分片连续函数，利用最小势能原理研究 了s t v e n a n t 的扭转问题。然而，此方法发展很慢，几乎过了十年才再次有人用 这些离散化的概念。1 9 5 6 年t u r n e r ，c 1 0 u g h ，m a r t i n 和t o p p 等人，在他们的 经典论文中第一次给出了用三角形单元求得的平面应力问题的真正解答。他们利 用弹性理论的方程求出了三角单元的特性，并第一次介绍了今天人们熟知的确定 单元特性的直接刚度法。他们的研究工作随同当时出现的数字计算机一起，打开 山东大学硕士学位论文 点位移作为基本未知量。 ( 3 ) 利用结点未知量，选择一组插值函数唯一地定义每一个单元内相应物理 场( 位移、应力和应变等) 的分布，即选择单元模式或单元列式。 ( 4 ) 将各种类型的荷载变换为只作用在结点上的等效荷载，建立基本未知量 与等效结点荷载之间的基本方程。 ( 5 ) 求解基本方程，得到基本未知量的解答。 整个求解区域的未知场函数可由各个单元结点上的数值以及插值函数近似 表示。这样，在一个问题的有限元分析中，未知场函数的有限个结点值就成为待 求全部的未知量，从而使一个连续体的无限自由度问题简化为有限自由度问题。 1 1 2 有限元网格生成 在有限单元法实施过程中，准备有限元数据部分占相当大的比重，它主要包 括连续体离散化过程和约束信息、荷载信息和材料信息的加载过程。其中，连续 体离散化的过程是这部分工作的核心，称为有限元网格生成。 研究如何在一定的区域中生成满足有限元分析要求网格的方法称为有限元 网格生成方法。这实际上就是定义一个能很好地描述几何区域的形状特征的节点 和单元的集合，并且这些节点和单元符合各种不同的形状和尺寸标准。从几何的 角度出发，有限元网格是由节点和单元组成的。其中，节点是指定区域内选定点 的集合，单元则是这些节点之间的连接关系。所以，由于节点之间连接关系的不 同，在一定的区域内，相同的节点集合会生成不同类型的单元。一般情况下，在 平面区域的网格生成中，既可以产生三角形单元，也可以产生四边形单元；在空 间结构的网格生成中，既可以产生四面体单元，也可以产生六面体单元。只是在 极少数情况下，比如说大小单元之间过渡时可能需要用到锥形或楔形单元。理想 的情况下，三角形和四边形单元分别为正三角形和正方形单元，而四面体和六面 体单元分别为正四面体和正六面体单元。 虽然由于节点之间的连接关系不同可以生成不同的单元，但区域内的节点和 单元之间要满足拓扑有效和几何有效条件。拓扑有效是指，在d 维问题中，两个 单元的d l 维公共部分仅为这二者共享，不会与其他单元共享；几何有效是指， 所有单元的集合覆盖整个求解区域，并且每个单元的j a c o b i n 行列式都为正值。 3 山东大学硕士学位论文 ( 2 ) 领域和主题在不断扩展和深入，研究重点从二维平面问题转移到三维曲 面和三维实体问冠，从三即瓦i 攀蓬婚吾醵州拢；营兰盐善卷罄牙鸯；煞委殄霉辜虽 尽管可哒揖蹲璺巧卷猿堡= 型呈碾箪： 妊堡歪磋；县雕唾迢挥渲培理睫浑国噻嘲；叭蚕曼良恻隧愕堪垲；驯善受 型勋莘甄到叵蟹元 研究的课题之一。 ( 5 ) 有限元向开放式、分布式网格化基础上的c a d c a e c a p p c a m 集成 化、智能化方向发展，真正做到计算机参与方案决策、结构设计、性能分析、图 形处理等设计全过程。 1 3 2 有限元嘲格自动生成技术 有限元网格全自动生成系统的研究是近年来的一个研究热点，正如前面所 说，在众多研究者的辛勤劳动下，己经出现了很多种特性各异的算法，它们其中 的很多种都为流行的商业网格自动剖分系统所采用，并经过实际使用证明了它们 的有效性和实用性。但是，前处理技术仍然存在一些问题，这些问题的存在也指 示了有限元网格自动生成技术研究的方向： ( 1 ) 和实体造型系统的集成。一个有限元自动分析系统的基本要求就是能够 不通过用户的交互作用，直接从c a d 造型系统中所提供的完备的几何描述中获取 有限元计算和分析所必须的数据。这就要求有限元网格自动生成算法能适应任何 实体造型，而目前的有限元建模技术并不能满足这样的要求。随着c a d c a p p c a i 的发展，特别是c i 鼯( c o m p 懒k 唤a t e dm 锄u f h c t l i r i r i gs y s 自锄) 的发展，使得几 何造型系统和有限元网格自动生成系统的集成成为发展的必然趋势。 ( 2 ) 提高计算精度。精度的提高是有限元分析和计算技术的一个重要的任 务，对于前处理技术来说，这包含两方面的含义：提高网格精度，也就是说改 善单元质量。网格精度直接关系到有限元计算的精度，各种方法自动生成的网格 单元由于边界条件的限制而难以完全保证网格的质量符合计算和分析的需要，尽 管可以通过各种单元光滑和单元修正技术进行调整，改善单元质量，但在复杂区 域和复杂边界情形时，这种改善总是有限的，因此如何进一步提高生成单元的精 度仍然是前处理技术研究课题之一。自适应有限元网格生成技术。自适应算法 通过加密网格来提高计 种算法有效而且收敛快，在各个领域自适应算 山东大学硕士学位论文 巨墨 嘭 瑶 巧“ 叼 o 构成的凸包。 在实际应用中，最常用的是二维平面的三角剖分( 其结果是三角形的集合) 和三维空间上的三角剖分( 其结果是四面体的集合) 。在本章中，我们主要研究的 是二维平面的三角剖分( 对于曲面，可看成是二维半空间，在其上的剖分与二维 区域上的剖分有许多相似之处) ，以下给出二维平面三角网格剖分的定义。 定义2 2 二维有限元三角网格剖分：称三角形集合r = 正，疋，巧) 为平 面上m 个非共线有限点集p 的三角剖分，当且仅当t 满足以下三个条件： 1 t 的顶点集为p ： 2 p 的凸包甲= u e ； 3 t 中任两个三角形的交集或者为空集，或者是p 中的点，或者是以t 中 两点为端点的直线段。如图2 1 为一个平面三角剖分。 i 鍪1 2 1 平而点集的一种三角剖分 从定义2 1 和定义2 2 中不难看出，平面三角剖分的实质是以三角形反映数 据点与其邻近点之间的拓扑连接关系，对于一个给定的点集p ，满足定义的三角 剖分不是唯一的，有多种剖分结果都能满足上述定义，需要对t 附加确定的优化 条件才能得到唯一结果。当然，其中只有部分结果的三角剖分网格的形态较优， 能够满足实际应用的需求。在许多应用中，最佳的情形为三角形尽可能是“等边” 的啪1 ，或边的总长度最小嘲，当三角剖分边的总长度减至最小时，则称为最小权 三角剖分。而d e l a u n a y 三角剖分是满足最小内角最大原则的最优三角剖分。 另外还可以得出，在进行网格剖分过程中，生成三角形单元时，必须满足以 下三个约束条件： 山东大学硕士学位论文 2 4 平面区域有限元三角网格剖分算法的度量标准 有限元法的基本思想就是将连续体划分为有限个单元的组合，这些单元的质 量就成为影响有限元计算结果精确程度和可靠程度的关键性因素，所以在网格自 动生成算法中，必须保证网格单元的质量。下面的几个标准用来评价实际的网格 自动生成算法。 ( 1 ) 基本功能的实现 这里所说的基本功能是针对有限元分析功能丽提出的，即网格生成算法应该 根据用户将要分析的不同内容来生成与其相适应的网格。 ( 2 ) 健壮性 评价网格生成算法的主要标准就是它的健壮性和可靠性，网格生成算法应该 适应绝大部分的工程实际情况以及比较复杂的情形，正是由于网格生成算法健壮 性才保证了有限元分析软件的通用性，脆弱的算法由于其适应范围的狭窄而不会 受到欢迎。算法的健壮性依赖于算法的本身，如程序员的编码水平以及测试用例 的数量、范围和复杂程度。 ( 3 ) 生成网格的质量 网格质量好坏的直接度量标准是，有限元分析模块利用此网格进行求解是否 精确，以及求解速度的快慢。 网格质量的评价标准有很多，例如可以根据生成单元的几何形态来度量，常 用的参数有单元最小边长与最大边长的比值，最小角度与最大角度的比值以及单 元平面的翘曲程度等，这些参数在网格生成后评价网格质量方面是非常重要的， 通过这些参数可以基本确定剖分的网格是否可用，是否需要改进或重新剖分。 网格的局部单元质量同整体单元质量一样都是不容忽视的，即使整体网格平 均质量比较高，如果有一些局部单元的质量很坏( 如扁平单元) ，或出现拓扑结构 错误的情况，那么必将导致分析阶段的矩阵形态恶劣乃至错误，难以计算出正确 的解。另一个有关网格质量的度量方式就是检查分析边界处网格的质量，这些地 方的网格质量也将在很大程度上影响分析结果。 ( 4 ) 网格疏密 在大多数计算中，解在计算域的各个位置的变化是不同的，可能在某些位置 变化剧烈而在另一些位置变化缓慢。如在固体力学问题中的应力集中位置，波浪 山东大学硕士学位论文 一浮体问题中的浮体表面和自由表面等处，解的变化比别的区域要剧烈得多。因 此，使用均匀的、疏密不变的网格显然是不妥的，比较好的方法是使网格的疏密 变化与解的变化一致。 ( 5 ) 网格形状 除单元尺寸外，单元形状对计算的影响同样非常显著。网格形状很差时甚至 会使得计算过程无法进行下去。网格中存在的大钝角单元会使插值误差增大嘲， 存在的尖角单元会使有限元离散形成的刚度矩阵的条件数增大，这些对计算都 非常不利。s h e w c h u k 研究了单元形状与插值误差以及刚度矩阵的数学关系，认 为单元形状应尽量接近正三角形为佳。 ( 6 ) 剖分速度 在网格生成的准确性得到保证的前提下，网格生成算法的效率就成为另外一 个受到关注的标准，有限元分析软件采用自动网格生成算法的主要目的就是要提 高建模的速度，提高网格剖分的正确性。建模速度比较快的算法能够大幅度的提 高工程人员的工作效率，节省大量的人力、物力和财力，多快好省地解决急需解 决的问题。除了剖分速度外，还应当考虑算法实施所要求的硬件的条件，应当占 用少的存储空间，更快的做好剖分工作。 ( 7 ) 用户参与程度 许多有限元分析软件的前处理功能是建立在计算机辅助设计系统之上的，因 此网格生成算法必须能够识别出模型的一些局部特征，如小的倒角，短的线段以 及半径小的圆等，当识别出这些特征后，应该不需要用户的干预即可以对这些敏 感的部分进行合理的剖分，以达到比较好的剖分效果和单元质量。另外，好的网 格生成算法应该要求用户输入的数据量尽可能的少，一般来讲，应当仅要求用户 给出模型的实体表示和剖分尺寸。 ( 8 ) 可控制性 有限元网格自动生成算法的最大优点就是基本上不用用户的干预，算法本身 根据模型的具体特征自动的给出网格剖分的单元尺寸，这个尺寸的选择应该能够 保证后来有限元分析结果的正确性。但是，有些时候由于模型过于复杂，网格生 成算法选择的尺寸和细化的区域不适应当前的模型，这个时候就需要人工的干 预，网格生成算法应该为用户提供方便的网格尺寸控制手段，让用户来控制他感 1 4 山东大学硕士学位论文 兴趣的区域的网格生成尺寸，然后根据用户给定的尺寸进行网格剖分。 2 5 平面区域有限元三角网格剖分算法概述 2 5 1 平面区域的敦嚣分类 在实际应用问题中，依据所提供的数据基本特征和要求的不同，二维平面区 域的数据可以分为以下几种类型： ( 1 ) 只给定边界信息的平面区域； ( 2 ) 给定边界和区域内部散乱点的平面区域； ( 3 ) 只给出散乱点的平面区域； ( 4 ) 给定边界及区域内节点分布密度的平面区域。 针对给定的二维平面区域的数据的不同，可以采用不同的三角剖分方法。 对于只给定边界信息的平面区域，需要根据边界信息离散产生边界节点，内 部节点则需自动生成，然后进行三角剖分。 对于给定边界和散乱点的平面区域，常用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 5 2 平面区域有限元三角网格剖分算法分类 按网格生成方法所产生的单元每个内部节点的邻接关系可以分为生成结构 山东大学硕士学位论文 化( s t r u c t u r e d ) 网格的方法、生成非结构化( u n s t r u c t u r e d ) 网格的方法和生成混 合结构化( m i x e ds t r u c t u r e d ) 网格的方法。 在结构化网格中，所有内部节点都有相同数量的邻近节点和相同数量的邻近 单元，即所有的内部节点都具有相同的度。结构化网格中的单元可以是三角形单 元或四边形单元。在非结构化网格中，对节点放松了要求，允许任意数量的单元 在一个节点处交汇，即所有内部节点的度都可能不同。虽然四边形单元也可以构 成非结构化网格，但实际上在非结构化网格中一般采用三角形单元。在混合结构 化两格中，有些内部节点具有相同的度，有些内部节点具有不相同的度，一般由 耦合单元或混合单元组成。混合结构化网格中的单元可以是三角形单元或多边形 单元。 2 5 3 结构化网格生成方法 结构化网格生成方法用来生成结构化网格，这种方法的代表方法是映射法。 映射法出现于2 0 世纪7 0 年代，是最早采用的网格生成方法。早期的有限元网格 生成基本上都依赖于映射方法，所生成的网格通常称为结构化网格。从7 0 年代 开始应用于商品化系统中，目前映射法在现有的商品化系统中仍占统治地位。 映射法可分为映射单元法( m a p p e de 1 e m e n ta p p r o a c h ) 及保角映射法 ( c o n f o r 啮1m a p p i n ga p p r o a c h ) 防“。映射单元法要求将目标区域手工分成许多 有利于映射操作的简单子区域，然后定义映射函数，将非规则区域映射成一个规 则区域( 如正方形区域) ，然后在规则区域上进行网格剖分，再将规则区域上的网 格点反映射到原来的非规则区域上形成网格剖分。现通常用所谓超映射技术来获 得过渡比较光滑的网格。保角映射法能直接处理单连通区域的问题，但是该法难 于控制单元形状和单元密度，很少使用。 映射法的优点在于方法简单、计算效率高、生成的网格分布均匀规则，排列 整齐，能够用于曲面网格的生成。但其最大弊端在于对形状较为复杂的形体适应 性差，需要事先根据所要产生的网格将目标区域分割成一系列可映射的子区域， 这一工作通常需要人工完成，自动化程度较低，人工交互多，不适合于全自动网 格的生成。另外，如何设计映射函数也是一个比较复杂的问题，如果设计不好经 常容易造成网格的重叠或空洞。过去大部分有限元计算模型并不依赖于实体造型 山东大学硕士学位论文 系统( s 0 1 i dm o d e l l i n gs y s t e m ，简称为s m s ) ，所以往往可以根据可映射的补丁 反过来定义目标域。随着计算机实体造型系统的出现，通过与其它方法相结合， 这一类方法的自动化程度也逐渐得到提高。 2 5 4 非结构化圈格生成方法 非结构化网格生成方法用来生成非结构化网格，这一类方法都可实现不同程 度的自动化，所以有时也称其为网格自动生成方法。所谓自动是指算法程序在接 受区域几何表述之后，不再需要任何用户干预就能在任意复杂的区域内生成有效 的有限元网格。非结构化方法由于其应用的灵活性而受到广泛的采纳，有许多有 限元分析软件都包含了此项功能。 非结构化网格生成方法的一个最为突出的优点是可以适应复杂的几何形体， 与几何形体的形状关系不大，结合一定的控制方法，可以生成质量很高的单元， 而且利用非结构化网格生成算法可以实现区域网格生成的自动化，这也是未来网 格生成的大势所趋。非结构化网格生成主要解决的问题是数据结构的设计和操 作，这个问题是所有非结构化网格生成算法的关键问题。几种较常用的非结构化 网格生成方法有：d e l 锄研三角剖分方法、j 岍推进波前法、有限四叉树法唧i l i t e q u a d 仃e em 甜1 0 d ) 、栅格法等。 2 5 5 混合结构化网格生成方法 有限元网格生成的混合法在计算流体力学领域里应用广泛，这种方法允许生 成的单元具有不同数日的边界，也就是说，在二维应用中单元的形状可以是三角 形或多边形。因为模型边界处网格单元的质量要求高，所以在剖分的模型的边界 处，用结构化网格生成高质量的单元，而在模型的内部可以用非结构化两格生成 算法来生成单元。混合法具有几何模型控制的灵活性，可以生成高质量的网格， 为实现自动网格生成提供了便利条件。 混合法的示意图如图2 3 所示。 山东大学硕士学位论文 | 冬l2 _ 3 ”混合结构网格示意| 冬| 混合结构化网格生成算法迄今为止还不太成熟，为了广泛的应用此类算法， 还有许多工作需要做。 2 6 几种较常用的非结构化网格生成方法 2 6 1k i a u n 甜三角剖分方法 三角剖分不仅是有限元网格生成中的重要方法，而且在数学、地理、工程等 许多领域有着重要应用。三角剖分研究可追溯到二十世纪三十年代，并在七十年 代后期得到了较大的发展和应用。其中以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 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 三角化方法在二维问题中应用的一些 关键问题己经基本得到解决，但涉及到三维问题时还有比较困难的问题，这些问 题若可以得到圆满解决，那么d e l a u n a y 三角化方法的应用前景将会更加光明。 1 9 3 4 年，b d e l a u n a y ”1 证踢：必定存在且仅存在一种割分算法，使得所有 山东大学硕士学位论文 题。 在二维平面点集d e l a u n a y 三角剖分的几种典型生成算法中，g r e e n s i b s o n 方法和b o w y e r 方法是直接从d e l a u n a y 三角剖分的定义出发依据t h i e s s e n 区域准则的三角剖分方法，c l l a w s o n 方法、迭代方法( i t e r a t i o n ) 矧和 a k c l i n ea n dr lr e n k a 方法首先对散乱点进行预排序，再依据最小内角最 大准则进行三角剖分的方法。 2 6 2 f t 推进波前法 经过近年来的发展，推进波前法( a d v a n c i n gf r o n tt e c h n i q u e ，简称a f t 方 法) 也已经成为通用的全自动非结构化有限元网格生成方法之一。该方法最早由 r a i n a l dl o h n e r 和s h l o 提出并用于平面区域三角形网格自动生成，在l 0 的方法中，所有网格节点在开始之前已经全部生成。后来p e r a i r e “2 1 等将这种方 法进一步发展并完善推广到二维自适应网格的生成，在p e r a i r e 发展的技术中， 区域内部的节点与单元是在网格化过程中自动、自适应同步生成的，并且通过引 入背景网格( b a c k g r o u n dg r i d ) 概念，由背景网格上各节点的节点间距、延展量 及延展方向等参数插值定义网格中各点的相应参数并根据这些参数控制内部节 点的生成。 a f t 方法的基本思路是先离散区域边界，二维平面区域边界离散后是首尾相 连的线段集合，这种离散以后的区域边界称为前沿。接下来的步骤就是从前沿开 始，依次插入一个新节点或采用一个己存在节点生成一个新单元。一个新的单元 生成以后，前沿要进行更新，即向区域的内部推进。这种插入节点、生成新单元、 更新前沿的过程循环进行，当前沿为空时表明整个区域剖分结束。 a f t 方法的基本思路虽然简单，但是在程序实现上是需要很多技巧的，这是 因为在a f t 方法的实现中，涉及到数据的存储方式，前沿的查找方法，前沿之间 的相交判断等，这些环节的实现效率都直接影响a f t 方法的运行效率。所以，很 多学者对此进行了大量的研究。l o h n e r 等提出了h e a pl i s t 等数据结构，b o n e t 则提出了a l t e r n a t i v ed i g i t a lt r e e 数据结构，用来辅助前沿相交判断，j i n 为了保证生成单元的质量提出了多点选择的方法和单元辅助检查的方法，m o l l e r 等则对用来生成单元的前沿的选择方式进行了讨论。g e o r g e 和l o h n e r 等对a f t 山东大学硕士学位论文 方法的最新进展和在一些特殊领域中的应用进行了概括和总结。 a f i r 方法的特点之一，是能够在生成节点的同时生成单元，这样就可以在生 成节点时对节点的位置加以控制，从而控制单元形状、尺寸以达到质量控制、局 部加密及网格过渡的要求。 a f t 方法的特点之二，是在生成新单元的同时需要进行大量的相交判断、包 含判断、以及为了保证单元的质量而进行的距离判断。相交判断包括线段之间的 相交判断，线段与三角形面片之间的相交判断：包含判断主要指单元是否包含前 沿节点的判断：距离判断包括线段与线段的距离，线段与前沿节点的距离以及线 段与三角形面片的距离。上述判断在整个a f t 方法实施过程中耗用了大约8 0 的 机时。因此在实施a f t 方法时，务必精心设计数据结构，尽量减少需要进行判断 的数量，以提高a f t 方法的效率。其中比较有效的数据结构是a l t e r n 8 t i v e d i g i t a lt r e e 和h e a pl i s t 与基于d e l a u n a y 概念的各种方法相比，a f t 方法虽然它没有后者那样成熟 的理论依据，在很多情形下靠经验解决问题，但是这并不妨碍它的成功应用，因 为它具有更大的灵活性及可靠性。a f t 算法的时间复杂度为( n l o g n ) ，与d e l 8 u n a y 三角化方法、有限四叉树法相当，但对生成单元的控制能力是三者中最强的。a f t 方法最大的缺点是时间效率相对较低，需要有较好的数据结构及算法来提高前沿 生成算法的速度。 本文在第3 章将重点讨论a 盯方法。 2 8 3 有限四叉树法 将四叉树分解方法用于网格生成最早是由y e r r y 和s h e p h a r d 提出来的。其 后k e l a ，b a e h m e n n ，s c h r o e d e r ，y e r r y ，s h e p h a r d 等人又对该方法进行了完善 和发展。y e r r y 和s h e p h a r d 后来将此方法称为有限四叉树方法( f i n i t eq u a d t r e e m e t h o d ) 。目前有限四叉树方法已经成为成功有效的网格生成方法之一。 在四叉树分解方法中，首先将目标区域用一个尽可能小的正方形方盒围住， 然后将这个方盒分解成四个子区域，对每一个子区域测试其是否完全在目标区域 外面或是否满足密度控制计算的精度要求，若满足所给定的条件则停止对此子区 域进行细分，否则将之细分，该过程迭代执行下去直到达到预定的离散要求。 2 1 山东大学硕士学位论文 虽然有限四叉树方法已取得相当大的成功，它适用于任何复杂的二维区域问 题，而且算法效率几乎与单元节点数的增长呈线性关系，其网格生成易于实现密 度控制，易于进行自适应分析。但其缺点也很明显，所生成的网格与所选择初始 栅格有关，网格边界的单元质量较差，程序实现相当复杂，所需内存较大，不利 于实现并行处理等。 2 6 4 栅格法 栅格法的基本思想很简单，对于二维问题来讲，就是取一个内部己经剖分成 栅格的矩形罩住将要剖分的区域，将在待剖分区域内部的网格保留，在边界处对 栅格进行剪裁以保证区域边界的完整性。 栅格法是剖分给定区域的最简单、最直接的方法，整个的区域网格生成以及 边界条件的保证可以实现自动化。栅格法已经被成功的用来解决许多工程实际问 题，效果也比较显著。但是，这个方法也存在着一些问题，其中比较突出的问题 是虽然区域内部单元网格的质量非常好，可区域边界处单元的质量在剪裁时却难 以保证，在二维情况时这个问题处理起来稍微简单一些，在三维情况时，区域边 界处理起来就相当复杂，涉及到三维实体的造型方法和边界表示方法。栅格法要 发展成全自动的无需用户干预的方法，还要做很多工作，主要包括查找算法，数 据结构的组织。比较典型的数据结构是八叉树四叉树结构，算法有多边形多面 体边界剪裁方法以及自适应细化方法。栅格法能产生较好形状的内部单元，但边 界单元的形状较差。 2 7 三角网格剖分的优化准则 所谓对三角网格进行优化，就是要使三角网格整体上尽量均匀，避免出现狭 长三角形或大钝角三角形，也就是获得d e l a u n a y 三角化。 在三角剖分过程中，可以先用一种比较简单的方法构造所给数据点的初始三 角剖分，然后对其进行优化以获得d e l a u n a y 三角剖分。优化的方法则取决于所 采用的优化准则，平面三角剖分最常用的优化准则7 有t h i e s s e n 区域准则 ( t h i e s s e nr e g i o nc r i t e r i o n ) 、最小内角最大准则、空外接圆准则。 s i b s o n “证明了这三个准则的等价性，并指出符合这三个准则的三角剖分只有一 山东大学硕士学位论文 2 7 3 空外接圆准霸 严格凸四边形中的三个顶点确定一个圆，如果第四个顶点落在圆内，则将第 四个顶点与其相对的顶点相连，否则将另外两个顶点相连，这个准则称为圆准则。 也就是说，符合空外接圆准则的三角割分中，任一三危形的外接圆内不应该包含 其他点，如图2 6 所示。 2 7 4 局部优化准尉 | 冬| 2 6 空外接圆准则 定义2 3 局部优化边：在一个三角形剖分网格t 中，称一条内边e 是局部优 化的，是指共享该边的两个三角形是对它们所形成的四边形的一个较好的剖分， 即e 边是不可对角置换的。 换言之，若e 边是局部优化的，那么如果共享该边的两个三角形a b c 与 a c d 形成的四边形a b c d 不是凹多边形，则有a b c 与a c d 中的最小内角大于 a b d 与b c d 中的最小内角。如图2 7 所示。 d a i 荽i2 7 局部优化j f b 山东大学硕士学位论文 局部优化准则是指对任意一个凸四边形的对角线，依据某种优化准则做交换 铡试后所得到的三角剖分。 在局部优化方法中，l a w s o n 局部优化法是一种常见的高效算法。它是一种 与外接圆准则相结合的局部优化准则。其大体步骤是这样的：从任意初始三角形 剖分网格t 出发，设e 是j r 的一条内边，q 是共享e 边的两个三角形形成的四边 形，如果其中的一个三角形的外接圆包含四边形q 的全部4 个顶点，那么将e 用 q 的另一条对角线替换；否则e 是局部优化的，此时保持e 不变。这一交换过程 b i 冬| 2 毒k m s o n 局部优化法 一直进行到所有三角形均满足“空外接圆准则”为止。如图2 8 所示，a b c 外 接圆内无d 点，a c d 的外接圆内无b 点，但a b d 的外接圆内有c 点。所以必 须连接a 、c 两点，丽不能连接b 、d 两点。 2 7 5 全局优化准月 定义2 4 全局优化三角形翻分网格：称三角形网格是全局优化的，如果它的 所有内边都是局部优化的，或者说它的所有内边都是不可对角置换的。 可以证明，在给定节点集合的所有三角剖分网络中，全局优化的三角形网格 是最优的，与d e l a u n a y 三角剖分是等价的。 当三角剖分网格t 中每一条内边上的两个三角形所形成的凸四边形都满足 局部优化准则时，称该三角剖分t 满足全局优化准则。 这样，通过局部优化准则，在三角形网格中考查所有的内边，比较共享该边 山东大学硕士学位论文 的两个三角形组成的四边形的两种剖分结果，选择最小内角最大的一种作为局部 优化。不断重复上述过程，直至所有的内边都是不可置换的，最终得到全局最优 剖分结果。 2 。7 。8 退化准刚 前面己经讲过d e l a u n a y 三角剖分满足空外接圆准则，即任一