有限元网格生成算法的评述

有限元网格生成算法的评述

李卫民

(泰州职业技术学院机电工程系,江苏泰州　225300)

摘　要:对几种常用有限元网格生成算法进行了评述,指出它们各自的优点和缺点;并阐述了

有限元网格划分的发展趋势。

关键词:有限元法;网格生成

中图分类号:TH12　　　　文献标识码

:A 　　　　文章编号:1671-0142(2004)01-0012-03

自从利用计算机技术进行有限元网格划分以来,人们已经研究了大量的算法,一般地,衡量一个有限元网格生成算法的好坏,可以用以下几个指标:剖分成的单元品质好;算法简单易行,容易编程;网格生成自动化程度高,人工输入数量少,使用方便;运算速度快。

由于网格划分的要求很多,各种算法可能有一定有的针对性,从而有各自的优点和缺点。这里对几种用途广泛的有限元网格生成算法进行分类和比较,并指出它们各自的优点和缺点,以供借鉴。1、分解法

1.1拓扑分解法

在几何造型系统中,形体的描述一般用两个信息,即几何信息和拓扑信息。几何信息定义形体元素的空间位置和形状表示;拓扑信息则定义各个构成元素间的相互连接关系,而不管元素的具体形状。拓扑分解法就是从形体的拓扑因素着手进行分割。如图1所示的多边形,首先连接它的各个顶点,形成宏观的三角分割,然后再把这些单元进行一步细化,以满足密度分布要求。

图1　多边形的拓扑分解法

细化时,有一些基本的操作,例如,对半分割、中心分割和对角线置换等操作,如图2所示。

图2　基本细化操作方法

第4卷第1期2004年2月　　　　　　　　　　　泰州职业技术学院学报Journal of T aizhou P olytechnical Institute 　　　　　　　　　　　V ol.4　N o.1Feb.2004

拓扑分解法原理简单,引入的算子概念,使得程序易于实现模块化,处理容易。但是该方法只从拓扑关系入手,不考虑几何因素,因此难以保证网格质量,而且检测量很大,对包含曲面的三维形体也难以处理。

112几何分解法

凡在产生结点的同时也确定结点间连接关系的方法均称为几何分解法,常用的有两种:递归法和迭代法。

递归法:先离散二维物体边界,然后沿离散边界向物体内挖掉一个、两个或三个三角形,重复此操作直到区域挖空为止。或首先从物体中挖掉边界层而不是单元,然后三角化边界层。上述为二维迭代法,Chae 在此基础上发展了三维迭代几何分解法,主要分两步:采用二维迭代几何分解法生成表面三角形,然后采用三种算子挖切凸体为四面体。在挖切时,突出的特点在于采用新方法生成关键点。关键点的生成分两步考虑:一是考虑新点对周围面和边的影响;二是通过调整比例因子来确定新点位置。Chae 也将所提出的算法成功地应用于自适应网格生成中,但由于被剖分物体形状必须是单连通凸域,因此,不能实现全自动网格生成。

迭代法:Bykat 采用该法。他首先将物体划分为凸体(手工或自动),随后根据网格密度分布,在每个凸体边界上插入结点,然后将物体中间“最长轴”一分为二,在该轴上插入结点,继续对两部分做递归分割直到最后子域均为三角形为止。商业网格生成软件Triquamesh 仍采用该法,只是分割线的选取与Bykat 不同。

几何分解法的最大优点是在离散物体时考虑网格单元的形状和大小,因此,所生成的网格单元形状和分布均较好。最大缺点是自动化程度低,不利于复杂件网格生成。

2、网格模板法

2.1映射法

映射法是一种半自动网格生成方法,根据映射函数的不同,主要可分为超限映射和等参映射。因前一种映射在几何逼近精度上比后一种高,故被广泛采用。映射法的基本思想是:在简单区域内采用某种映射函数构造简单区域的边界点和内点,并按某种规则连接结点构成网格单元。这种方法可以很方便地生成四边形和六面体单元,若需要,也很容易转换成三角形和四面体单元。该法的主要缺点;首先必须将待分区域子划分为所要求的简单区域,这是一个十分复杂且很难实现自动化的过程。对复杂域采用手工方法划分甚至不可能。通常各简单区域边界采用等份划分。另外,该法在控制单元形状及网格密度方面是困难的。鉴于简单区域自动划分的困难性,Blacker 试图采用知识系统和联合体素方法解决,但在复杂多孔域上仍难以处理,主要是体素数量和形状有限,将待分区域全自动划分为有限的预定体素并集是很难完全实现的。

2.2栅格法

栅格法首先用交互方式将物体划分为形状简单的子区域,每个子区域分别用定型的网格模板作为规整的部分。再用适当的措施,使得相邻子区域在结合面共享公共的节点,并且网格相容。

栅格法能够生成的单元类型很多,划分简单,效率较高。尽管网格构造方法差别很大,但得到的结果相似,容易控制网格的形状和密度,物体内部的单元质量比较好。最大的缺点是物体边界的网格质量不好,需要人工干预,很难完全自动化。

2.3网格模板法网格模板法(RS D 法)生成有限元网格主要分两步(以介绍三维实体为主):其一、将待分实体用适当大小的立方体箱(树根)完全包容,按“一化八”原则递归离散,然后对每个八分块分类为RS D 模型。其二,对已经形成的RS D 模型,目前已有多种生成网格的处理方法。主要有三种:RS D/G DT 法、RS D/EE 法和RS D/DDT 法。

各种RS D 法的优点是网格生成完全自动,网格剖分速度快,非常适用于自适应网格生成。主要缺点是边界单元形状难于完全保证。另外,RS D 法对物体的方向特别敏感。

31第1期　　　　　　　　　　　　　　李卫民:有限元网格生成算法的评述　　　　　　　　　　　　　　　　

2.4节点连接法

该法是先生成结点,然后连接结点构成单元。最常用的是DT法和AFM法。

DT法的基本原理:任意给定N个平面点P i,(i=1,2,…,N)构成的点集为S,称满足下列条件的点集V i为Voronoi多边形。其中,V i满足下列条件:V i={X:|X-P i|(|X-P i|,X(R2,i(j,j=1,2,…,N}V i凸多边形,称{V i}mi=1为Dirichlet T esselation图或对偶的Voronoi图。连接相邻Voronoi多边形的内核点可构成三角形Tk,称集合{Tk}为Delaunay三角剖分。DT法的最大优点是遵循“最小角最大”和“空球”准则。因此,在各种二维三角剖分中,只有Delaunay三角剖分才同时满足全局和局部最优。“最小角最大”准则是在不出现奇异性的情况下,Delaunay三角剖分最小角之和均大于任何非Delaunay剖分所形成三角形最小角之和。“空球”准则是Delaunay三角剖分中任意三角形的外接圆(四面体为外接球)内不包括其他结点。实现Delaunay三角剖分有多钟方法。Lee和Schachter操作很有效,但很难实现。而Wats on、Cline和Renka、Sloan因操作容易、时间效率较好等优点而被广泛采用。为了进一步提高效率,Sloan研究其算法操作,提出了时间复杂性为0(N)(N为结点总数)的操作方法,从而为快速Delaunay三角剖分提供了有效途径。虽然DT法既适用于二维域也适用于三维域,但直接的Delaunay三角剖分只适用于凸域,不适用于非凸域,因此发展了多种非凸域的Delaunay剖分。

AFM法的基本原理:设区域的有向离散外边界集和边界前沿点集已经确定,按某种条件沿区域边界向区域内部扣除三角形(四面体)直到区域为空集。AFM法的关键技术有两个:一是区域的边界离散和和内点的合理生成。二是扣除三角形条件。

3、自动自适应网格剖分

有限元的自适应性就是在现有网格基础上,根据有限元计算结果估计计算误差、重新剖分网格和再计算的一个闭路循环过程。当误差达到预规定值时,自适应过程结束。因此,有效的误差估计和良好的自适应网格生成是自适应有限元分析两大关键技术。就目前国外研究来看,自动自适应网格生成从大的方面可分为两类:网格增加技术和网格再生技术。

网格增加技术:该法主要依靠增加自由度总数来提高有限元分析的精度。目前主要采用三种类型方法提高有限元分析精度:h—型、p—型、和h—p—型。h—型采用有选择地进一步子划分网格单元来细化网格以提高自由度。该法使用特别广泛,RS D模型的网格改进正是利用该法。p—型在保持网格划分不变的情况下,通过提高插值函数的阶数获得高的求解精度。h—旷型是将h—型和p—型两种结合的一种方法。该法虽然实现不容易,但它却可使收敛速率明显加快。实践表明,在获得同一精度时,上述三种类型收敛速率是按h—型?p—型?h—p—型顺序增加的。

网格再生技术:根据现有网格并配合误差估计确定新的结点密度分布,然后重新划分网格,再计算并重复上述过程直到求解精度达到预定目标为止。目前,网格再生技术在平面区域已得到了较好地实现。从理论上讲,该原理可扩充到三维实体域,但由于三维实体域难以完全自动用等结点密度曲面来分割任意实体,因此在三维域的扩充至今仍未实现。

实践表明,网格再生技术比网格增加技术具有更大的优点,主要表现在前者收敛速度快、网格单元形状稳定。

R esearch about the Arithmetic of Mesh G eneration of FEM

LI Wei-min

(Mechanical and Electronic Dept.Taizhou Po1ytechnical Institute,Taizhou Jiangsu225300,China)

Abstract:By analyzing the arithmetics O fmesh generation O fFE M,this article presents each excel lenceand disadvantage of them,then discusses thefuture of mesh generation of FE M.

K ey w ords:Finite E lement Method(FE M);Mesh generation

(责任编辑　施　翔)