Vol.15,No.1
Jan.,2003
有限元网格生成方法研究的新进展
关振群 宋超 顾元宪 隋晓峰
(大连理工大学工业装备结构分析国家重点实验室 大连 116024)(大连理工大学工程力学系 大连 116024)
摘要 总结了近10年来有限元网格生成方法的研究进展.首先,概述了目前研究与应用仍然较为活跃的通用网格生成方法,如映射法、基于栅格法、Delaunay三角化法和推进波前法的最新研究进展;其次,对当前的主要研究热点,如曲面网格生成、全六面体网格生成和并行网格生成等进行了阐述;最后,简要地探讨了该领域的发展趋势.关键词 有限元;网格生成;映射法;基于栅格法;四叉树Π八叉树;Delaunay三角化;推进波前法;曲面网格;六面体网格;并行算法中图法分类号 TP391
RecentAdvancesofResearchonFiniteElementMeshGenerationMethods
GuanZhenqun SongChao GuYuanxian SuiXiaofeng
(StateKayLaboratoryofStructuralAnalysisforIndustrialEquipment,DalianUniversityofTechnology,Dalian 116024)(DepartmentofEngineeringMechanics,DalianUniversityofTechnology,Dalian 116024)
Abstract Thispaperpresentstheadvancesofresearchinmeshgenerationforfiniteelementcomputationinlasttenyears.Firstly,theadvancedofthecommonmethodssuchasmappingmethods,grid2basedmethods
(includefinitequadtreeΠoctreemethods),DelaunaytriangulationandAFTmethodsareemphasized;secondly,themainresearchfieldssuchassurfacemeshing,all2hexmeshingandparallelmeshgenerationarediscussedindetail;finally,thetrendsofmeshgenerationarepresentedbriefly.
Keywords finiteelement;meshgeneration;mappingmethod;grid2basedmethod;quadtreeΠoctree;Delau2naytriangulation;AFT;surfacemesh;all2hexmesh;parallelalgorithm
率、精度等方面提出更高的要求.作为有限元走向工
1 引 言
有限元网格生成是工程科学与计算科学相交叉的一个重要研究领域,在经历了30多年发展后的今天依然十分活跃.一方面,有限元法已成为一种能够有效地求解各类工程和科学计算问题的通用数值分析方法;另一方面,计算机硬件运算能力的不断提高也容许人们对工程和科学计算的规模、复杂度、效
程应用的桥梁的有限元网格生成由此获得了源源不
断的外在动力.同时,有限元网格生成算法研究中的某些难点问题始终未能获得真正意义上的解决,它们的研究解决对计算几何与计算数学都具有重要的理论价值.
有限元网格生成方法研究领域已取得许多重要成果,形成了独特的方法论体系,提出了许多有效的算法并研制出一些成功的工程化软件产品.许多学
原稿收到日期:2002208230.本课题得到国家自然科学基金(10002006)、国家重点基础研究专项经费(G1999032805)和国家“八六三”高技术研究发展计划专项经费(2001AA412220)资助.关振群,男,1965年生,副教授,主要研究方向为有限元网格生成、科学计算可视化、CADΠCAE.宋 超,男,1976年生,博士研究生,主要研究方向为有限元网格生成方法.顾元宪,男,1954年生,教授,博士生导师,主要研究方向为计算力学、科学计算可视化、计算工程软件.隋晓峰,男,1977年生,硕士研究生,主要研究方向为有限元网格生成方法.
2
计算机辅助设计与图形学学报2003年
者对有限元网格生成方法研究进行了概括和总结,如Thacker,Ho2LeK,Shephard,Baker,George和胡恩球[127]
等对70～90年代初期该领域的研究进展作了系
[8210]
统的回顾与阐述;吕军,魏红宁和Blacker等对某些重要分支领域的研究进展进行了评述.
近10年来,有限元网格生成方法研究有两个显著特点:(1)与其它研究领域一样,经历了一个进化过程,一些方法的研究与应用出现停滞,而另外一些方法在不断地深入、完善和发展,成为适应性强、应用范围广泛的通用方法;(2)领域和主题在不断扩展和深入,研究重点由二维平面问题转移到三维曲面和三维实体问题,从三角形Π四面体网格自动生成转移到四边形Π六面体网格自动生成,在并行网格生成、自适应网格生成、贴体坐标网格生成、各向异性网格生成等方面亦取得许多重要进展.
射就是超限插值的一种特殊形式.超限插值既可适应特殊的区域边界形状,又可控制所生成单元的形状和密度,成为代数插值网格生成的一个标准方法.
映射法的优点是算法简单、速度快、单元质量好、密度可控制,它既可生成结构化网格又可生成非结构化网格;既可生成四边形单元网格又可生成六面体单元网格,可用于曲面网格生成,可与形状优化算法集成等.因此,映射法在众多的商业有限元分析软件中占有重要的地位.
映射法一般可直接处理单连通域问题,但对于复杂多连通域问题,需要首先用手工或自动方法将待剖分域分解成几何形状规则的可映射子区域,然后在每个子区域内应用映射法.然而在实践中仍有几个难点需要克服:(1)如何自动地将复杂的不可映射的待剖分域分解成简单的可映射的子区域;(2)如何满足某些物理问题中对网格疏密过渡的要求;(3)如何满足子区域之间的网格相容性要求.
子区域分解(特别是三维实体)是应用映射法生成有限元网格的最大困难,不少学者对此提出了多
[24228]
种解决方法,其中中轴线法和中面法具有代表性.Tam与Armstrong首次提出可用中轴线法将二维待剖分域分解为简单子区域,随后Price与Arm2
[25226,29]
strong等提出用中面法将三维待剖分域分解成简单子区域.由于中轴线法Π中面法得到的子区域一般具有可映射特性,因此可以将映射法与中轴线法Π中面法相结合形成复杂域全自动网格生成方法.目前,二维问题的中轴线提取算法已经相当成熟,而三维问题的中面提取算法还存在一些问题,特别是几何适应能力问题.
对于网格疏密过渡问题和网格相容性问题,李华与程耿东等提出了一种在正方形子区域上实现网格在两个坐标方向均能过渡的全四边形单元生成方法———模板法.将该方法和映射法结合可以有效地在两个坐标方向上实现网格疏密过渡以及对局部点或局部区域进行网格加密处理,而对没有网格疏密过渡要求的区域可以生成和映射法一致的结构
[32]
化网格.在此基础上,李华和程耿东又提出了三维组合式模板,实现了立方体子区域上的在三个坐标方向上均能过渡的全六面体单元生成方法;并通过采用线性整数目标规划技术求解模板组合参数,解决了子区域与子区域之间的网格相容性问题.2.2 基于栅格法
基于栅格法(grid2basedapproach)的基本流程:
[30231]
[24]
2 有限元网格生成的通用方法
2.1 映射法
映射法既是结构化网格生成方法,又是非结构化网格生成方法.它的基本步骤是:通过适当的映射函数将待剖分物理域映射到参数空间中形成规则参数域;对规则参数域进行网格剖分;将参数域的网格反向映射回物理空间,从而得到物理域的有限元网格.映射法可分为保角映射法(conformalmapping
[11213]
method)、基于偏微分方程法(PDE2basedmeth2[14219]od)以及代数插值法(algebraicinterpolationmeth2[20223]od)三大类.保角映射法能够处理多于4条边界的单连域问题,但难于控制单元形状和单元密度,且不能直接应用于三维问题.Thompson等首次提出的基于偏微分方程法,通过数值求解偏微分方程而得到参数空间与物理空间之间的映射关系.基于偏微分方程法可细分为椭圆型、抛物线型和双曲线型三大类,其中最常用的是椭圆型Poisson方程和Laplace方程网格生成方法.基于偏微分方程法主要应用于CFD(computationalfluiddynamics)领域的贴体坐标(boundary2fittedcoordinate)网格生成问题,目前仍在深入研究和发展中.
代数插值法是一种应用相当广泛的网格生成方法,它通过代数插值来描述参数空间与物理空间之间的映射关系,其中最重要的一个类别是超限插值(transfiniteinterpolation)[20],Zienkiewicz提出的等参映
[16219]
[14215]
1期关振群等:有限元网格生成方法研究的新进展
3
首先用一组不相交的尺寸相同或不同的栅格(cells)覆盖在目标区域上面,保留完全或部分落在目标区域之内的栅格,删除完全落在目标区域之外的栅格;然后对与物体边界相交的栅格进行调整、剪裁、再分解等操作,使其更准确地逼近目标区域;最后对内部栅格和边界栅格(特别是边界栅格)进行栅格级的网格剖分,进而得到整个目标区域的有限元网格.
基于栅格法又可分为正则栅格法(regulargridmethod)和有限四(八)叉树法(finitequadtreeΠoctreemethods)两大类.正则栅格法与有限四(八)叉树法在算法的总体流程上基本一致,它们之间的最大区别在于正则栅格法采用尺寸相同的正则栅格覆盖目标区域,而有限四(八)叉树法采用基于四(八)叉树数据结构的可递归细分的变尺寸栅格来覆盖目标区域.与正则栅格法相比,有限四(八)叉树法能够更好地协调边界逼近精度与生成单元数量之间的平衡,因此应用更为广泛.
[33]
Yerry和Shephard首先将用于近似表达几何对象的四(八)叉树法空间分解法引入到网格剖分领域,其后又有许多学者对该方法进行了完善和发展,形成了有限四(八)叉树方法.有限四(八)叉树方法适用于复杂二维和三维域网格生成,几何适应性强,网格密度可控制,且算法效率较高(时间复杂度为O(NlogN),实际观察接近于O(N),其中N为生成单元总数).但该方法也存在如生成网格与所选择的初始栅格及其取向有关、目标域边界处单元质量较差等严重缺点.
有限四(八)叉树方法的主要步骤包括:叉树的构建,叉树的平衡,交点过滤,内部栅格与边界栅格的相容网格剖分,网格优化等.其中,内部栅格与边界栅格的相容网格剖分在实现上具有相当的难度.例如,对于三维内部栅格的网格剖分问题,如果相邻八分区(octant)最多相差一个级别的划分水平,那么内部栅格的拓扑形式就存在4096种可能性,即使考
[34]
虑到对称与旋转特性也需要建立78种模板.为了简化算法,Yerry等提出可将内部栅格分解为6个锥体,然后再将锥体剖分成所需单元,但是该方法
[35]
生成单元太多,且质量较差.Schroeder等将Delau2nay方法引入到有限四(八)叉树方法中,解决内部栅格与边界栅格的相容网格剖分问题,一定程度上降低了程序实现的复杂度并提高了边界网格质量.
[36]
McMorris等提出了将八叉树法与推进网阵法相结合的生成曲面网格和三维实体网格的新方法,成功
[34]
地应用于计算流体动力学中的网格生成问题.
与推进波前法和Delaunay三角化法相比,有限四(八)叉树方法在三角形Π四面体网格生成方面并不具有优势.但是,有限四(八)叉树方法也有自己独特的内在品质,因而在相当广泛的领域获得了成功的应用.Schneiders等提出基于八叉树法的全六面体网格生成方法,值得注意的是,该方法将父栅格划分为27个子栅格,而非标准的8个子栅格.Frey[38]等指出,以往的网格生成方法只是使用了四(八)叉树提供的邻接空间信息(用于增强搜索效率),而没有作为控制空间信息(用于控制单元尺寸).事实上,在自适应有限元分析中可以通过调整叉树结构使得修正后的栅格尺寸与根据误差估算得到的期望
[39]
的单元大小相匹配.Saxena等将四(八)叉树法作
[40]
为背景栅格来驱动并行网格生成,Lohner等提出的并行化算法也采用八叉树为框架.2.3 Delaunay三角剖分方法
Delaunay三角剖分(简称DT)是目前最流行的通用的全自动网格生成方法之一.DT有两个重要特性:最大2最小角特性和空外接圆特性.DT的最大2最小角特性使它在二维情况下自动地避免了生成小内角的长薄单元,因此特别适用于有限元网格生成.所谓空外接圆特性,就是DT中的每个三角形单元或四面体单元的外接圆(二维)或外接球(三维)都不
[41242]
包含其它节点,Bowyer2Watson算法正是利用了这一特性.
三维Bowyer2Watson算法的基本步骤:首先定义一个包含所有节点的初始网格,最简单的情形是单个四面体;向网格中插入一个节点,找出其外接球包含此节点的所有四面体单元,删除这些单元形成一个包含插入节点的空腔(cavity);将该插入节点与空腔的每个表面相连,形成新的四面体网格;重复进行上述的节点插入过程,直到全部节点插入完毕.
Delaunay三角剖分算法的计算效率与具体的实现相关.大体上可将DT算法分为三大类:分治算法,逐点插入法和三角网生长法.Bowyer2Watson算法是一种典型的逐点插入法,其时间复杂度为
3Π2
O(N),采用四(八)叉树数据结构的Bowyer2Watson算法可达到O(NlogN),分治算法的时间复杂度为
3Π2
O(NlogN),三角网生长法的时间复杂度为O(N),其中N为生成单元总数.
经典DT技术已经相当成熟,近年来的研究重
[43249]
点是约束DT的边界恢复算法,以及如何克服
[37]
4
计算机辅助设计与图形学学报2003年
Bowyer2Watson算法退化现象所产生的薄元(sliverel2
[50251]
ement)问题.2.3.1 约束DT的边界恢复算法
由于Delaunay三角剖分算法仅对凸域的剖分有效,对于非凸域则不能保证其边界的完整性,因此对非凸域应用Delaunay三角剖分算法时必须引入一个恢复边界的步骤.恢复了边界完整性的三角剖分并不能严格满足Delaunay准则,因此称为约束DT.
二维问题的边界恢复比较简单,并且有明确的理论保证边界恢复结果是收敛的.一种边界恢复算法是由George等提出的边交换法,该方法基于一个简单的原理:相邻两个三角形所构成的四边形的两个对角线可以互换而不影响这两个三角形与相邻三角形的相容关系.这样,就可以通过一系列的四边形对角线的交换来恢复目标域边界的完整性.另一种常用的二维边界恢复算法是最近点连线法,该方法首先找到与已经丢失的边界线段相交的所有三角形,这样可以得到一组互相邻接的三角形,然后将这些三角形所代表的单元删除,仅留下节点;从距离丢失的边界线段最近的节点开始,逐一将节点与丢失的边界线段或其它新生成的线段重新生成三角形单元;这样循环迭代,直到所有节点使用完毕.
三维问题的边界恢复过程要比二维问题复杂得多,在二维问题中行之有效的边界恢复算法不能直接扩展到三维问题中.三维域的边界由一系列三角形面片组成,其边界恢复基本上可分成两步:(1)恢复边界的边———三角形面片的边;(2)恢复边界的面———三角形面片本身.由于三角形边的存在有时并不能保证此三角形面在剖分结果中存在,所以(2)也是必需的.
一种比较常用的三维问题边界恢复算法称为装[45]
订法.这种方法首先恢复边界的边,当边界边与其它单元相交时则在边界边上插入节点,边界边即可被恢复.然后恢复边界的三角形面,思路与此类似,也是在三角形面上插入节点来恢复边界面.这种边界恢复算法是有效的,但应注意到该算法在边界边以及边界面上插入了新的节点,初始边界三角形也被分解为多个小三角形,因而新的边界并不是严格意义上的原有边界.
[46]
另一种边界恢复算法被称为分治算法,这种算法不是在实体剖分完成之后恢复边界,而是在实体剖分之前将问题域划分成若干个凸域,对每一个凸域进行Delaunay三角剖分时就可以保证原问题域边
[44]
[43]
界的完整性.当然,凸域分割增加了额外的工作量.2.3.2 薄元的处理方法
Delaunay三角剖分算法在二维问题中不仅可以保证剖分的收敛,而且也能够保证剖分结果是最优的.但在三维情况下,这些性质都不能得到保证,其中一个比较典型的问题是薄元问题.所谓薄元是指一个四面体的4个节点几乎共面,但这个四面体仍然符合Delaunay三角剖分准则.这种单元的质量很差,可能导致有限元计算结果的严重误差,因而必须加以处理.
目前有两种常用的薄元处理方法:(1)节点抖动法.该方法试图将一个薄元的一个节点沿着某个方向移动,以增加薄元的“厚度”、提高单元质量,但抖动算法在实际应用中有许多困难,而且在某些
[51]
情况下将会失效;(2)薄元分解法.该方法基于这样一个事实,即薄元一般都相当于比较薄的面片,可以在面片的形心处插入一个新的节点,该节点可以同与此薄元邻接的4个单元形成4个新的单元,用来代替薄元,实践证明,这种方法实施简单、行之有效.
2.4 推进波前法
[50]
经过近年来的发展,推进波前法(Advancing
[52260]
FrontTechnique,AFT)已成为目前最流行的通用的全自动网格生成方法之一.该方法的提出应归功
[60][59]
于Lohner和Lo.AFT方法没有Delaunay三角剖分算法那样成熟的理论依据,在很多情形下AFT方法是靠经验解决问题,但是这并不妨碍它的成功应用.AFT算法的时间复杂度为O(NlogN),与Delaunay三角化算法、有限四(八)叉树法相当,但其生成单元的质量是三者中最好的.
AFT方法的基本流程是:首先离散待剖分域的
边界,二维待剖分域的边界离散后是首尾相连的线段的集合,三维待剖分域的边界离散后是拓扑相容的三角形面片的集合,这种离散后的域边界称为前沿;然后从前沿开始,依次插入一个节点,并连接生成一个新的单元;更新前沿,这样前沿即可向待剖分域的内部推进.这种插入节点、生成新单元、更新前沿的过程循环进行,当前沿为空时表明整个域剖分结束.
AFT方法的特点之一是能够在生成节点的同时生成单元,这样就可以在生成节点时对节点的位置加以控制,从而控制单元形状、尺寸以达到质量控制、局部加密及网格过渡的要求.大量文献提出了各
1期关振群等:有限元网格生成方法研究的新进展
5
种不同的节点生成方法及单元生成方法.
AFT方法的特点之二是在生成新单元时需要进行大量的相交判断、包含判断,以及为了保证单元的质量而进行的距离判断.相交判断包括线段之间的相交判断,线段与三角形面片之间的相交判断;包含判断主要指单元是否包含前沿节点的判断;距离判断包括线段与线段的距离,线段与前沿节点的距离以及线段与三角形面片的距离.上述判断的计算,在整个AFT方法实施过程中耗用了大约80%的机时.因此,在实施AFT方法时,务必精心设计数据结构,尽量减少需要进行判断的数量,以提高AFT方法的效率.其中比较有效的数据结构是AlternativeDig2italTree
[61]
直接法两类.
3.1.1 映射法
映射法首先在曲面的二维参数空间中利用平面域网格生成方法进行网格剖分,然后将剖分结果反向映射回物理空间形成曲面网格.曲面网格剖分的映射法也称为参数空间法.平面域网格生成方法已经相当成熟,可生成质量良好的三角形、四边形单元网格.但是,参数空间上单元形状良好的网格映射到物理空间后往往会出现畸变.许多学者针对此问题对传统映射法进行了不懈的改进,使映射法的曲面适应能力得到了增强.
[64265]
Zheng等在曲面的参数空间中引入了延展因子概念.通过计算曲面边界曲线的离散线段在物理空间和参数空间的长度比值,来估算曲面边界曲线上各离散点的延展因子;然后利用延展因子对原始参数空间作比例变换,使曲面在参数空间的映射结果(闭合平面域)大体保持各向同性,从而消除或减弱由映射函数引起畸变.但该方法不能适用于内部与边界的畸变状态差别较大的曲面.
[66]
Chen等对Delaunay三角化方法的适应性进行改进,用外接椭圆准则替代传统的外接圆准则,保证了参数空间的Delaunay剖分结果(形状可能比较差)在映射到物理空间后具有良好的几何性态.Chen方法对曲面边界和内部的映射畸变给出了统一的计算方法,克服了Zheng方法的缺陷,在实践中取得了成功.熊英等在Chen方法的基础上提出了新的椭圆构造算法以及椭圆圆心的定位方法,并解决了求解椭圆效率不高的问题.
[68]
Daniel等对AFT方法进行了适应性改进,使其节点插入规则和单元连接规则与各向异性的剖分控制函数保持一致,从而保证了剖分结果在物理空间的几何性态.Daniel方法的优势主要有两点:(1)用初始背景网格作为建立剖分控制函数的依据,较Chen方法能更为准确地描绘映射畸变的程度;(2)用改进的AFT方法作为二维剖分方法,使节点的生成和连接都考虑了映射畸变的影响,而改进的Delaunay方法只是在节点连接过程中考虑映射畸变的影响.
[69]
Cuilliere从曲面的参数方程出发,提出了一套度量映射畸变的新方法.通过数学推导建立了一套曲面相关的代数方程,用来描述由映射引发的畸变.与Daniel的方法相类似,在二维网格划分上Cuilliere使用AFT方法,并也对其进行了适应性的改进.
[67]
和Heaplist
[62]
,实践证明,这两种数据结构
的联合应用可以显著地提高AFT方法的计算效率.
AFT方法存在一个收敛性问题.所谓收敛性问
题是指在三维问题的某些特殊情况下,一个多面体内部如果不插入额外的节点,则该多面体不能够被剖分成几个四面体的集合,一个典型的例子是Schonhardt多面体
[63]
.AFT方法的收敛性问题有其特
殊性,因此有些特殊问题并不能够通过插入节点而得到解决,必须采取其它方法加以解决.这里给出一个比较有效的解决方法:一般来讲,采用AFT方法剖分网格到最后遇到的不收敛的区域不止一个,对于每一个区域生成一个包含此区域的所有节点的立方体,然后将那些有节点在此立方体中存在的单元删除,这样便形成一个新的多面体,对于这个新的多面体重新生成单元.对每一个不收敛区域都按照这个方法重新生成单元,经过几次循环迭代以后,结果一般都是收敛的.
3 当前几个主要研究方向
3.1 曲面网格生成
曲面网格生成是有限元网格生成技术中的一个重要研究领域,它的应用相当广泛.工程结构中常用的薄壳结构,如球罐、压力容器、冷凝塔、飞机蒙皮、汽车外壳等,都是由圆柱、圆锥、球面等规则曲面以及Bézier,NURBS等自由曲面组合而成的.此外,曲面的网格划分结果往往是三维实体网格生成方法的输入数据,是三维实体网格划分的前提和基础,其质量的优劣对后续生成的三维实体网格的质量有很大影响.目前,曲面网格划分方法大致可分为映射法和
6
计算机辅助设计与图形学学报2003年
Cuilliere方法的优点是给出了对映射畸变的解析形
式描述方法,对映射畸变的度量更为精确.但在通用性和执行效率方面,该方法相对上述几种方法则略显不足.
综上所述,解决曲面网格划分中的映射失真问题可从以下两方面入手:(1)修改或重新定义曲面的参数表达,使参数空间到物理空间的映射函数的畸变性降低;(2)修改二维网格生成方法,在节点插入和连接时考虑映射函数的畸变性,使参数空间内生成的网格在映射回物理空间后具有良好的几何性态.3.1.2 直接法
界层内的液体流动计算中,极狭长六面体单元的计
算精度远远优于极狭长四面体单元.在某些情况下,如当用有限体积法与边界适应坐标系统求解复杂形体的控制守恒方程时,只能采用六面体单元进行有
[72]
限元分析.几十年来,众多学者致力于六面体单元网格自动生成方法研究,但复杂三维实体的全六面体单元网格全自动生成问题始终未能获得真正意义上的解决,全六面体网格由此被称为“神圣网格”(holygrid).近几年来,全六面体网格自动生成再度成为焦点问题,并取得了一些研究进展.目前有代表性的全六面体网格自动生成方法有:原型法,映射法,扫描法,基于栅格法,扩展的AFT方法和多子区域法.3.2.1 原型法、映射法和扫描法
原型法是用预先设定的网格剖分模板来剖分可被识别的简单几何形体的一种网格生成方法.六面体网格原型就是可用网格剖分模板分解为六面体网格的简单几何形体.最基本的六面体原型为四面体,
[73]
它可被分解为4个六面体.目前,复杂三维实体的全四面体网格全自动生成算法已经很成熟,结合四面体到六面体的网格剖分模板,即可轻易地实现复杂三维实体的全六面体网格生成.但遗憾的是,这种方法的边界拟合能力弱,生成的网格质量较差.左
[74]
旭等采用十节点曲边四面体代替直边四面体,并采用非线性约束优化算法来提高六面体单元的质量,但只是部分地克服了上述两个缺点.
映射法可以被认为是原型法的一种扩展,因为映射法在参数空间中的网格剖分一般使用一种最简单的六面体原型———正立方体.
[75278]
扫描法是由二维四边形有限元网格通过旋转、扫描、拉伸等操作而形成六面体网格的一种方法.在扫描过程中,扫描断面还可以进行扭转与变[75,78]形,形成特殊形状的实体网格.这种方法难度较低、较容易实现,在当今大多数的商用CAD软件和有限元前置处理软件中均有这种功能.但是,这种方法只能适用于形状简单的三维物体,且主要依靠人机交互来实现,自动化程度低.3.2.2 基于栅格法
由于三维栅格本身就是质量优良的六面体,因此无论是正则栅格法还是有限八叉树法,在六面体网格生成方面都具有得天独厚的条件.将基于栅格法应用于六面体网格生成已取得许多成果,比较有
[79,37][80]
代表性的是Schneiders和Loic提出的方法.
与映射法不同,直接法的曲面网格划分是直接在曲面的物理空间进行.由于剖分过程直接以曲面的局部几何形态为参考,并根据曲面的局部状况采取不同的剖分策略,因此直接法的曲面适应能力较映射法强,其生成的网格能较好地逼近原始曲面,而且网格的质量也较高.直接法的研究起步较晚,目前
[70]
主要有两个分支:曲面分解法和基于AFT的直接[71]法.
曲面分解法是一种基于四叉树分解的曲面剖分方法.它的基本思想是:将原始曲面不断地递归分解为较小的面片,直到这些小面片在给定的逼近误差下可精确模拟原始曲面为止;然后再将小面片转换为三角网格,最终形成对原始曲面的三角划分.这种方法最大的优点就是具有曲面自适应能力,对复杂曲面的逼近程度较好.但相对于映射法来说,它的执行速度较慢,缺乏网格的局部控制能力.
基于AFT的直接法是对AFT技术的一个发展,它对传统的二维AFT三角化方法进行了三维扩展:引入了新的判别算子,扩充了控制前沿网格生成的约束条件,使用投影算法以保证插入节点在曲面上的精确定位.基于AFT的直接法具有灵活、可靠、简单等特点,而且由于同时使用曲面曲率和密度函数作为网格剖分的控制因子,它不仅表现出良好的曲面适应能力(在曲率变化平缓的地方生成的网格比较稀疏,在曲率变化激烈的地方生成的网格比较稠密),还具有网格的局部加密能力,是一种很有前途的曲面网格全自动生成方法.但相对于映射法来说,其计算效率略显不足.3.2 六面体网格生成有限元法的研究表明,六面体单元具有许多四面体单元无法比拟的优异特性和更好的计算精度,可在不失精度的情况下进行某方向的伸缩.如在边
1期关振群等:有限元网格生成方法研究的新进展
[79]
7
提出了采用所谓同构技术(isomor2
phismtechnique)的基于正则栅格的六面体网格剖分方法,该方法的基本步骤是首先用尺寸相同的正则化栅格(cells)覆盖在目标区域上面,删除完全落在目标区域之外的栅格、与目标域边界相交的边界栅
Schneiders而是它的对偶形式———空间缠绕连续集.一旦得到
完整的空间缠绕连续集,六面体单元就可在其指导
[84]
下安装到待剖分域中.Folwell和Mitchell提出基于曲线收缩的编须算法:首先求得待剖分域表面四边形网格的对偶曲线环,通过对这些对偶曲线环进行拓扑操作使得环与环之间的交点数量减少,当一条曲线环不再与其它曲线环相交时就收缩为一点;当所有对偶曲线环均收缩成一点时算法结束.如果初始对偶曲线环自相交时,需采用局部预处理算法,扰动表面四边形网格而使对偶曲线环简化.关于初始对偶曲线环自相交问题的更深入的研究可参阅文献[85].
粘贴算法基于局部几何测试来推进网格,对于复杂的几何实体很难闭合网格内部连通性.与粘贴算法相反,编须算法基于与全局对偶密切相关的连通性信息进行网格推进,边界处的几何判据处于次要地位.编须算法生成的六面体网格质量(尤其是边界单元的质量)是所有算法中最好的,但它的实现也具有最高难度.虽然取得了一定的成功,但该方法对求解各类问题的健壮性与可靠性还有待于进一步证实.3.2.4 多子区域方法
多子区域方法(multi2subdomainmethods)是基于“分而治之(divideandconquer)”思想的一大类方法.具体地讲,多子区域方法分为三个主要步骤:首先将复杂目标域分解为可用已有算法进行剖分的简单子区域,然后对每个子区域进行剖分,最后将各个子区域的网格剖分结果组装起来从而形成目标域的整体网格.这样,一个大问题就被分解为三个较小的问题:一是复杂目标域的自动分解,二是简单子区域的网格剖分,三是满足有限元网格相容性要求的子区域网格组装.原型法、映射法和扫描法都可以作为子区域的网格剖分方法;子区域网格组装与子区域的网格剖分有密切关系,在某些情况下子区域网格在组装时能够自动满足相容性要求;而复杂三维实体的自动分解则是多子区域方法中最主要的困难.
(1)自动分解技术
自动分解技术的研究相当活跃,其中有代表性的工作是中面法和基于特征识别技术的三维实体自动分解方法.
文献[25226,29]提出用中面法将三维待剖分域分解成简单可剖分子区域.中面定义为三维实体内最大球的球心的集合,所谓最大球是指不能为实体
格和距离边界非常接近的内部栅格,保留下来的内部栅格称为初始栅格,这时在初始栅格与目标域边界之间存在着未被覆盖的缝隙;然后将初始栅格表面的每一个顶点投射到目标边界上并生成一个对应点,注意到初始栅格的表面面片全部是四边形网格,这样每一个面片都可以在表面找到一个对应面;最后连接相对应的四边形得到全六面体网格.
基于正则栅格的缺点是,为了剖分带有小尺寸几何特征的目标域,栅格尺寸也要相应缩小,这样就会产生太多的单元.在前面所提到的工作基础上,又提出了基于八叉树的六面体网格
剖分方法.该方法最主要的贡献在于解决了不同级八分区之间的网格相容性问题,它将父栅格划分为27个子栅格而非标准的8个子栅格,结合过渡模板成功地实现了相容性网格生成.Schneiders等
Loic提出的基于八叉树的六面体网格剖分方
[37]
法,在实现上与Schneiders方法有很大的不同.该方法在八叉树建立时并不删除边界栅格,且在建立八叉树之后就立即插入相容六面体模板.对于边界栅格,将其顶点投射并移动到目标域表面,这样就恢复了目标域的边界.为了改善边界单元特性可插入一个边界层栅格,然后通过节点优化来改善整体网格的质量.3.2.3 扩展的AFT方法
Tautges和Blacker提出的编须算法(whisker[81]
weaving),以及Blacker和Meyers提出的粘贴算法
[82]
(Plastering)都是AFT方法的扩展形式.粘贴算法始终维护网格前沿,即用来描述已剖分区域边界的四边形面片集.剖分器迭代地从网格前沿中选择一个或多个四边形,粘贴上相应的六面体并更新前沿,直到整个域被剖分.然而在实践中,该方法通常会留下一些孔洞,这些未被剖分的区域只能用四面体填充.
编须算法是一种基于空间缠绕连续集(spatial
[83]
twistcontinuum,STC)概念的扩展的AFT方法.所谓空间缠绕连续集就是在三个方向平分六面体单元的相互交叉表面的组合,是六面体网格的一种对偶表达形式.编须算法首先生成的并不是六面体网格,
8
计算机辅助设计与图形学学报2003年
内其它球所含的球.待剖分域被中面分割后所得到的子区域一般具有可映射特性,这对六面体网格剖分是非常有利的.但是,现有中面算法一般需要大量几何与代数计算,自动化程度和几何适应能力也有待于提高.
提出一种基于特征识别技术的三维实
体自动分解方法,该方法可分为三个相对独立的步骤:采用特征识别技术提取模型的分解特征,生成切割表面和切割目标域从而生成分离的三维子区域.由于引入了一些启发性规则,该方法可以一定程度Lu等
[27]
实际上就是一个完整的计算机,处理结点只能通过通信网络传递消息来进行通信.由于分布式内存MIMD系统具有一定优势,以下的讨论将针对分布式内存MIMD系统.
衡量网格生成并行算法的主要指标是算法的可伸缩性、并行效率和网格质量稳定性,其中最重要的是可伸缩性,因为它保证了当处理器增加时可在一个合理时间内求解更大规模的问题.目前的网格生成并行算法都涉及到“分区(domainpartitioning)”概念,所谓分区就是将目标域分解为多个子区域并提交给多个处理器,好的分区应保证处理结点的负载平衡.目前的并行网格生成算法大体可以分为三[88]
类:(1)子区域界面网格生成在前;(2)子区域界面网格生成在后;(3)子区域网格生成与界面网格生成同步.
第一类算法是将目标域分割为多个子区域,并在网格生成之前预先生成界面网格,这样在子区域的网格生成过程中就无需处理结点之间的通信.该类方法可按子区域的分区形式进一步地细分为三个子类:初始粗网格分区,背景树分区,表面网格直接分区.初始粗网格分区的通常做法是:生成初始粗网格,将初始粗网格分区为多个子区域,细分初始粗网格界面至一个合适的尺寸,将子区域分配给处理结
[39]
点,剖分子区域.Saxena等将四(八)叉树法作为背景栅格来驱动并行网格生成,当八叉树被分区后,无论是内部栅格还是边界栅格的网格剖分都不再需要通信.当插入节点的顺序满足一定条件时,平面Delaunay准则能够保障八分区共享面的相容网格三
[89]
角化.Galtier和George提出了一种通过三角化分离面(separator)而将待剖分区域一分为二的分区方法,该方法的输入是由表面网格描述的待剖分区域,分离面是一个位置良好的剖切平面.与分离面相关的三角化并非通常意义上的三角化,而是由与分离面相邻的三角面片组成的网格.通过这种方法,输入表面网格被先期细分为多个由表面网格描述的子区域.该类算法的优点是子区域网格生成不需要处理结点之间的通信,能够保障可伸缩性;缺点是由于在区域内部人工地加入了界面可能使网格质量降低.
第二类算法是首先进行子区域网格生成,而子区域界面的网格生成留待以后处理.这类方法首先由Shostko和lohner提出,deCougny和Sheph2[88,91][92]ard以及张明敏和潘志庚等提出的并行网格生成方法也属于这一类.在deCougny和Shephard提
[90]
地模仿人们处理复杂几何体网格生成问题时的思考过程,加之可以和CAD系统紧密集成,这是一种有前途的自动分解算法.
(2)典型的多子区域方法———中面法
Tam等
[86]
的中面法的基本步骤是:首先使用中
面提取算法计算出三维目标域中面,其次根据中面将三维目标域分解为预定义的13种类型简单子区域;然后采用中点分解技术将每个子区域划分为六面体网格;最后将所有子区域生成的六面体网格组装成全域六面体网格.如果没有网格变密度要求,中点分解技术可自动满足子区域之间的网格相容性要求;但如果有网格变密度要求,则需要采用整数规划技术来确定每条边的分割数,从而在满足相容性要求的条件下实现网格的密度控制.中面法可以应用于带有凹边或凹顶点的实体及退化情况,进而实现复杂实体(如带有孔、凹角等)的六面体网格生成.该方法已在多个商业软件中得以实现.3.3网格生成并行算法
先进的可伸缩的并行计算机的出现为求解超大规模问题提供了可能性.有限元分析求解器的并行化已取得了许多重要进展,但网格生成并行化研究却相对落后.当问题的规模达到百万节点量级时,单机或串行机有限元网格生成就成了严重问题:一方面网格生成时间过长,另一方面单机内存容量也不能满足要求.网格生成已成为大规模及超大规模科学计算的瓶颈问题,因而网格生成算法的并行化是一个相当迫切的研究课题.
目前的并行计算机可分为共享内存MIMD系统
[87]
和分布式内存MIMD系统两大体系结构.在共享内存MIMD系统中,所有处理器使用一个公共内存.在分布式内存MIMD系统中,每个处理器都有自己的局部内存,它们由通信网络来相互连接.每个处理器和它的局部内存合称为处理结点,每个处理结点
[26]
1期关振群等:有限元网格生成方法研究的新进展
9
出的方法中,对于输入的表面网格,首先建立一个满足剖分尺寸要求的分布八叉树,对该树采用递归平分(recursivebisection)方法并行地进行分区,并提交给处理结点进行网格剖分.体积的网格剖分采用两种技术:对内部末端八分区采用模板法进行剖分,而对已被剖分的八分区与表面网格之间的未被剖分的区域采用表面移去技术进行剖分.由于网格剖分是分布式进行的,子区域之间的界面区域还未进行剖
[91]
分.对此,deCougny等采用层次化再分区技术,对界面区域进行再分区及网格剖分操作,直至所有区域均被剖分.文献[92]提出了一种基于分治算法的可对任意散乱点集进行Delaunay三角剖分的分布并行算法,该算法具有容错性和自动负载平衡的能力.这类方法不需要处理结点之间的通信,能够保障可伸缩性,然而再分区操作可能会降低算法的整体效率.
第三类算法与传统的做法不同,子区域网格生成与子区域之间界面的网格生成同步进行,由
[93]
Chrisochoides等提出的Bowyer2Watson算法的并行化实现是这类算法的典型实例.Bowyer2Watson并行算法的输入是边界相容的初始化三角网格,当插入结点所形成的空腔(cavity)不跨越子区域界面时,网格剖分操作无需处理结点之间的通信;当插入结点
所形成的空腔跨越子区域界面时,该结点的插入过程将延迟,直至邻接子区域的处理结点提供所需的相关信息,并且在网格生成的同时子区域也要更新以保证处理结点的负载平衡.这类算法的优点是在目标域内部未加入人工界面,所得到的网格质量较好;缺点是需要处理结点之间的通信,不能够保障并行算法的可伸缩性.此类算法有较大的发展潜力,通过对算法的精细设计甚至可达到比传统算法更高的效率.4 总结与展望
有限元网格生成方法是一个相当宽的研究领域,全面而系统地进行综述是相当困难的.除了本文涉及的通用网格生成算法和几个有代表性研究热点以外,还有许多分支领域未进行讨论,如自适应网格生成、结构化网格生成(特别是贴体坐标网格生成)、各向异性网格生成、混合网格等,这些领域亦取得许
[942109]
多重要进展.表1所示为三种全自动网格生成方法的主要性能比较,其中的部分内容参考了文献[7],并根据近年来的研究进展对有关内容进行了相
应的更新.
表1 三种全自动网格生成方法比较
性能\\方法
Delaunay三角化法
有限四(八)叉树法
2D,3D均为O(Nlog(N)),实际观察
推进波前法
2D,3D均为O(Nlog(N))
计算效率(随生成单
2D,3D均为O(Nlog(N))
元总数N的变化)
三者中效率最高
所生成的网格单元质2D网格质量较好,3D易产生薄元,但区域内部网格质量较好,边界网格质
2D、3D网格质量都较好
量已有解决办法量较差单元密度控制
事先、事后密度控制均可,局部性一般事先、事后密度控制均可,局部性好
能直接生成三角形、四边形、四面体
单元,经扩展可直接生成六面体单元全自动太复杂
2D、3D任意区域均可
2D任意区域较好,3D任意区域尚可
事先、事后密度控制均可,局部性好能直接生成三角形、四边形、四面体
单元,经扩展可直接生成六面体单元全自动中等难度
2D、3D任意区域均可2D、3D任意区域可靠性,均好
所能生成的单元种类能直接生成三角形、四面体单元自动化程度程序实现复杂度问题区域适用性程序的可靠性各向异性网格生成结构化网格生成并行网格生成自适应网格生成曲面网格生成六面体网格生成算法应用频度
全自动相对较容易
2D、3D任意区域均可2D、3D任意区域可靠性,均好
可以不能
困难不能
好不能
能.主要作为子区域网格剖分方法能.密度控制能力强
直接法、间接法均可,生成单元质量好经扩展可直接生成六面体单元高
能.可以将分区域网格生成合并为一
能.叉树结构可以作为框架数据结构
个过程,有发展潜力能.密度控制能力一般间接法,生成单元质量好不能三者中最高
能.密度控制能力强
直接法、间接法均可,生成单元一般经扩展可直接生成六面体单元低,主要应用于六面体网格生成
近年来有限元网格生成方法研究领域最重要的进展是实现了复杂三维域有限元网格全自动生成,
10
计算机辅助设计与图形学学报2003年
这在很大程度上使得网格生成不再是有限元法工程应用的瓶颈问题.然而,这并不表明网格生成算法已经达到顶峰.一方面有限元网格生成还有许多难点问题未能解决,另一方面现有的算法在效率、质量、可靠性、几何适应性、规模、便捷性等方面还存在许多问题,需要进一步研究.下面提出有限元网格生成及其相关领域的几个研究方向,供大家探讨.
(1)通用算法的数据结构与多种算法的联合应用.在通用算法的研究方面,应注意数据结构的研究和多种算法的联合应用,提高核心算法的可靠性和几何适应性,达到速度与质量之间的平衡,实现核心算法的黑箱化.
(2)CADΠCAE的集成与参数化动态有限元建模.参数化CAD技术、有限元分析技术、优化技术的发展,已使参数化的结构优化设计成为可能,而参数化动态有限元建模是实现这一先进分析设计技术的基础.参数化设计是新一代智能化、集成化CAD系统的核心技术之一,参数化动态有限元建模就是以参数化CAD系统为平台,将CAD的参数化设计技术应用到有限元建模过程之中,以设计参数来驱动有限元模型的生成与更新,实现设计参数、几何模型、有限元模型之间的高效率参数联动.目前,这方
[1102111]
面工作已经取得一定进展.
(3)自适应网格生成技术.近年来,自适应网格生成技术发展非常迅速.事实证明,自适应网格生成对于提高有限元分析的精度是非常有效的.自适应网格生成算法与实际模型的求解方程、算法特征相关联,随着有限元研究与应用领域的不断扩展,自适应网格生成算法也会不断发展.
(4)网格生成算法的并行化和分布化.并行化计算环境对于大规模、超大规模科学计算以及高端工程应用是必需的,而分布式计算环境可作为一种中端工程应用解决方案.现有网格生成并行化或分布化算法在计算效率、内存管理、生成单元质量等方面还不够完善,还有许多潜力可挖.另外,并行计算环境与分布式计算环境的控制软件日趋成熟,这为算法的并行化、分布化开发提供了更强有力的技术保障.
(5)网格生成的智能化.目前的网格生成算法及其软件还需要许多人工干预,如节点密度控制、门槛值设定、单元类型选择等.这一方面给用户提供了更多的控制能力,但同时也给用户增加了困扰.一种便捷、易用、能够充分利用经验,并根据目标域特征自动给出合理的网格剖分结果的傻瓜型智能化网格剖
分器一直是工程设计人员所渴望的.目前,计算机科学领域中的人工智能、专家系统、几何造型方法及特征识别等方面的研究成果为智能化网格剖分提供了可能性.
(6)有限元网格生成算法的开放问题.复杂三维实体全六面体网格生成无疑是最艰难的一个开放问题,目前虽然取得一些阶段性的研究成果,但离问题的最终解决还有相当长的距离.编须算法似乎是一种有潜力的方法,仍有一些技术上的难题需要解答,值得深入研究.当然,也期待新理论与新方法的出现.参 考 文 献
[1]
ThackerWC.Abriefreviewofmethodsusedforgeneratingirregularcomputationalgrids[J].InternationalJournalforNumericalMethodsinEngineering,1980,15():1335～1341[2][3]
Ho2LeK.Finiteelementmeshgenerationmethods:Areviewandclassification[J].ComputerAidedDesign,1988,20(1):27～38ShephardMS.Approachestotheautomaticgenerationandcontroloffiniteelementmeshes[J].AppliedMechanicsReview,1988,41(4):169～185[4]
ShephardMS,GriceKR,LoJA,etal.Trendsinautomaticthree2dimensionalmeshgeneration[J].Computer&Structures,1988,30(1Π2):421～429[5][6][7]
BakerTJ.Developmentsandtrendsinthree2dimensionalmeshgen2eration[J].AppliedNumericalMathematics,1989,5(4):275～304GeorgePL.Automaticmeshgeneration.ApplicationstoFiniteEle2mentMethods[M].NewYork:Willey,1991
HuEQ,ZhangXF,XiangW,etal.AReviewofmeshgenerationmethodsforfiniteelementcomputation[J].JournalofComputer2Aid2edDesign&ComputerGraphics,1997,9(4):378～383(inChi2nese)
(胡恩球,张新访,向 文,等.有限元网格生成方法发展综
述[J].计算机辅助设计与图形学学报,1997,9(4):378～
383)[8]
LuJ,WangZJ,WangZR.Generationoffiniteelementhexahedralmeshanditstrendofdevelopment[J].JournalofHarbinInstituteofTechnology,2001,33(4):485～490(inChinese)
(吕 军,王忠金,王仲仁.有限元六面体网格的典型生成方
法及发展趋势[J].哈尔滨工业大学学报,2001,33(4):485～
490)[9]
WeiHN,ZhouBK.Ontheselectionofproperautomaticmeshgen2eratorsforadaptivefiniteelementanalysis[J].JournalofSouthwestJiaotongUniversity,1997,32(5):477～482(inChinese)
(魏红宁,周本宽.自适应有限元分析的网格自动生成方法的
选择[J].西南交通大学学报,1997,32(5):477～482)
[10]
BlackerT.Automatedconformalhexahedralmeshingconstraints,challengesandopportunities[J].EngineeringwithComputers,2001,17(3):201～210
1期
[11]
关振群等:有限元网格生成方法研究的新进展
BrownPR.Anon2interactivemethodfortheautomaticgenerationof
[26]
11
PriceMA,ArmstrongCG.Hexahedralmeshgenerationbymedialsurfacesubdivision:PartII[J].InternationalJournalforNumericalMethodsinEngineering,1997,40(1):111～136
finiteelementmeshesusingtheSchwarz2Christoffeltransformation[J].Computermethodsinappliedmechanicsandengineering,1981,25(1):101～126[12]
BaldwinKH,SchreyerHL.Automaticgenerationofquadrilateralelementsbyaconformalmapping[J].EngineeringwithComputers,1985,2(3):187～194[13]
YangGW,EQ,LiFW.Useofconformalmappingingridgenera2tionforcomplextwo2andthree2dimensionalconfigurations.ACTAAerodynamicaSINICA,1997,15(3):378～385(inChinese)(杨国伟,鄂 秦,李凤蔚.保角变换在复杂外形网格生成中[29][28][27]
LuY,GadhR,TautgesTJ.Featurebasedhexmeshingmethodolo2gy:Featurerecognitionandvolumedecomposition[J].Computer2AidedDesign,2001,33(3):221～232
ShefferA,EtzionM,RappoportA,etal.Hexahedralmeshgenera2tionusingtheembeddedVoronoigraph[A].In:Proceedingsofthe7thInternationalMeshingRoundtable,Dearborn,1998.347～364LiTS,McKeagRM,ArmstrongCG.Hexahedralmeshingusingmidpointsubdivisionandintegerprogramming[J].ComputerMethodsinAppliedMechanicsandEngineering,1995,124():171～193
的应用[J].空气动力学学报,1997,15(3):378～385)
[14]
ThompsonJF,ThamesFC,MartinCW.Automaticnumericalgen2erationofbody2fittedcurvilinearcoordinatessystemforfieldcontain2inganynumberofarbitrarytwo2dimensionalbodies[J].JournalofComputationalPhysics,1974,15():299～319[15]
ThompsonJF,WarsiZUA,MastinCW.Boundary2fittedcoordi2natesystemsfornumericalsolutionofpartialdifferentialequations
[30]
LiH,ChengGD,GuYX.Anewmethodforfastingmeshgenera2tionofquadrilateralfiniteelements2patternmodule’smethod[J].ComputationalStructuralMechanicsandApplications,1996,13(1):25～33(inChinese)
(李 华,程耿东,顾元宪.一种新的全四边形网格快速生成
方法———模板法[J].计算结构力学及其应用,1996,13(1):
25～33)[31]
LiH,LiXN,ChengGD,etal.Amethodformeshgenerationofallquadrilateralfiniteelements2improvedpatternmodule’smethod[J].ChineseJournalofComputationalMechanics,2002,19(1):16
———Areview.JournalofComputationalPhysics,1982,47():1～
108[16]
ThompsonJF,WarsiZUA,MastinCW.NumericalGridGenera2tion:FoundationsandApplications[M].NewYork:Elsevier,1985[17]
ThompsonJF.Acompositegridgenerationcodeforgeneral3Dre2gions———TheEAGLEcode[J].AIAAJournal,1988,26(3):271
～19(inChinese)
(李 华,李笑牛,程耿东,等.一种全四边形网格生成方法
———改进模板法[J].计算力学学报,2002,19(1):16～19)
[32]
LiH,ChengGD.Newmethodforgradedmeshgenerationofquad2rilateralfiniteelements[J].ComputersandStructures,1996,59(5):823～829
[33]
YerryMA,ShephardMS.Amodifiedquadtreeapproachtofiniteelementmeshgeneration[J].IEEEComputerGraphics&Applica2tions,1983,3(1):39～46[34]
YerryMA,ShephardMS.Automaticthree2dimensionalmeshgener2ationbythemodified2octreetechnique[J].InternationalJournalforNumericalMethodsinEngineering,1984,20(11):1965～1990[35]
SchroederWJ,ShephardMS.AcombinedoctreeΠDelaunaymethodforfullyautomatic32Dmeshgeneration[J].InternationalJournalforNumericalMethodsinEngineering,1990,29(1):37～55[36]
McMorrisH,KallinderisY.Octree2advancingfrontmethodforgen2erationofunstructuredsurfaceandvolumemeshes[J].AIAAJour2nal,1997,35(6):976～984[37]
SchneidersR,SchindlerR,WeilerF.Octree2basedgenerationofhexahedralelementmeshes[A].In:Proceedingsofthe5thInterna2tionalMeshingRoundtable,Pittsburgh,1996.205～216[38]
FreyPJ,LoicM.Fastadaptivequadtreemeshgeneration[A].In:Proceedingsofthe7thInternationalMeshingRoundtable,Dearborn,1998.211～224[39]
SaxenaM,PerucchioR.ParallelFEMalgorithmsbasedonrecursivespatialdecomposition———I.automaticmeshgeneration[J].Comput2ers&Structures,1992,45(5Π6):817～831[40]
LohnerR,JuanRC.ParallelAdvancingfrontgridgeneration[A].In:Proceedingsofthe8thInternationalMeshingRoundtable,SouthLakeTahoe,CA,1999.67～74
～272
[18]
HsuK,LeeSL.Anumericaltechniquefortwo2dimensionalgridgenerationwithgridcontrolatalloftheboundaries[J].JournalofComputationalPhysics,1991,96(2):451～469[19]
SpekreijseSP.EllipticgridgenerationbasedonLaplaceequationsandalgebraictransformations[J].JournalofComputationalPhysics,1995,118(1):38～61[20]
GordonWJ,HallCA.Constructionofcurvilinearcoordinatesys2temsandapplicationstomeshgeneration[J].InternationalJournalforNumericalMethodsinEngineering,1973,7():461～477[21]
ErikssonLE.Generationofboundaryconforminggridsaroundwing2bodyconfigurationsusingtransfiniteinterpolation[J].AIAAJournal,1982,20(10):1313～1320[22]
YangWJ,BaoZX,FuMF,etal.MappingappliedforHexahe2dralmeshgeneration[J].JournalofNanchangUniversity(Engineer2ing&Technology),1999,21(4):39～43(inChinese)
(杨伟军,包忠诩,扶名福,等.映射法在三维六面体有限元网
格生成中的应用[J].南昌大学学报,1999,21(4):39～43)
[23]
KadivarMH,SharifiH.Doublemappingofisoparametricmeshgen2eration[J].Computer&Structure,1996,59(3):471～477[24]
TamTKH,ArmstrongCG.2DFiniteelementmeshgenerationbymedialaxissubdivision[J].AdvancesinEngineeringSoftware,1991,13(5Π6):313～324[25]
PriceMA,ArmstrongCG.Hexahedralmeshgenerationbymedialsurfacesubdivision:PartI[J].InternationalJournalforNumericalMethodsinEngineering,1995,38(19):3335～3359
12
[41]
计算机辅助设计与图形学学报
WatsonD.Computingthen2dimensionalDelaunaytesselationwithapplicationstoVoronoipolytopes[J].TheComputerJournal,1981,24(2):167～172
[55]
2003年
JinH,TannerRI.Generationofunstructuredtetrahedralmeshesbyadvancingfronttechnique[J].InternationalJournalforNumericalMethodsinEngineering,1993,36(11):1805～1823
MollerP,HansboP.Onadvancingfrontmeshgenerationinthreedi2mensions[J].InternationalJournalforNumericalMethodsinEngi2neering,1995,38(21):3551～3569
[42][43]
BowyerA.ComputingDirichlettessellations[J].TheComputerJour2nal,1981,24(2):162～166
GeorgePL,HechtF,SaltelE.Automaticmeshgeneratorwithspec2ifiedboundary[J].ComputerMethodsinAppliedMechanicsandEn2gineering,1991,92(3):269～288
[56]
[57]RassineuxA.Generationandoptimizationoftetrahedralmeshesbyadvancingfronttechnique[J].InternationalJournalforNumericalMethodsinEngineering,1998,41(4):651～674
LoSH.Volumediscretizationintotetrahedra———I.Verificationandorientationofboundarysurfaces[J].ComputersandStructures,1991,39(5):493～500
LoSH.Volumediscretizationintotetrahedra———II.3DTriangula2tionbyadvancingfrontapproach[J].ComputersandStructures,1991,39(5):501～511
LohnerR,ParikhP,GumbertC.Interactivegenerationofunstruc2turedgridforthreedimensionalproblems[A].In:ProceedingsofNumericalGridGenerationinComputationalFluidMechanics’88,PineridgePress,1988.687～697
BonetJ,PeraireJ.Analternatingdigitaltree(ADT)algorithmforgeometricsearchingandintersectionproblems[J].InternationalJour2nalforNumericalMethodsinEngineering,1991,31(1):1～17LohnerR.Someusefuldatastructuresforthegenerationofunstruc2turedgrids[J].CommunicationsinAppliedNumericalMethods,1988,4(1):123～135
RuppertJ,SeidelR.Onthedifficultyoftriangulatingthree2dimen2sionalnonconvexpolyhedra[J].Discrete&ComputationalGeometry,1992,7(3):227～253
ZhengY,LewisRW,GethinDT.Three2dimensionalunstructuredmeshgeneration:PartI.Foundationalaspectsoftrianglationsandpointcreation[J].ComputerMethodsinAppliedMechanicsandEn2gineering,1996,134(3Π4):249～268
ZhengY,LewisRW,GethinDT.Three2dimensionalunstructuredmeshgeneration:PartII.Surfacemesh[J].ComputerMethodsinAppliedMechanicsandEngineering,1996,134(3Π4):269～284
[44][45]
GeorgePL,BorouchakiH.DelaunayTriangulationandMeshing:ApplicationtoFiniteElements[M].Paris:EditionsHERMES,1998WeatherillNP,HassanO.Efficientthree2dimensionalDelaunaytri2angulationwithautomaticpointcreationandimposedboundarycon2strains[J].InternationalJournalforNumericalMethodsinEngineer2ing,1994,37(12):2005～2039[59][58][46]JoeB.GEOMPACK———Asoftwarepackageforthegenerationofmeshesusinggeometricalgorithms[J].AdvancesinEngineeringSoft2ware,1991,56(13):325～331
[60]
[47]ZhouXY,LiuSQ.ArobustalgorithmforconstrainedDelaunaytri2angulation[J].ChineseJournalofComputers,1996,19(8):615～626(inChinese)
(周晓云,刘慎权.实现约束Delaunay三角剖分的健壮算法[J].计算机学报,1996,19(8):615～626)
[61]
[48]YangQ,XuYA,ChenQM,TanJR.Researchon3DconstrainedDelaunaytriangulation[J].JournalofComputer2AidedDesign&ComputerGraphics,2000,12(8):590～594(inChinese)
(杨钦,徐永安,陈其明,谭建荣.三维约束Delaunay三角化的
[62]
研究[J].计算机辅助设计与图形学学报,2000,12(8):590～
594)[49]
XuYA,YangQ,WuZZ,etal.Thealgorithmof3DconstrainedDelaunaytriangulation[J].ChineseJournalofSoftware,2001,12(1):103～110(inChinese)
(徐永安,杨钦,吴壮志,等.三维约束Delaunay三角化的实现[J].软件学报,2001,12(1):103～110)
[50]
CanvendishJC,FieldDA,FreyWH.Anapproachtoautomaticthree2dimensionalfiniteelementmeshgeneration[J].InternationalJournalforNumericalMethodsinEngineering,1985,21(2):329～347[51]
SongC.Themethodofautomaticmeshgenerationforarbitraryshapevolumesanditsimplementationinprogram[MasterThesis].Dalian:DalianUniversityofTechnology,2001(inChinese)
(宋 超.任意三维实体四面体单元网格自动剖分方法及程
[63]
[64]
[65]
[66]ChenH,BishopJ.Delaunaytriangulationforcurvedsurface[A].In:Proceedingsofthe6thInternationalMeshingRoundtable,ParkCity,1997.115～127
[67]XiongY,HuYJ,etal.AnalgorithmofsurfacetriangulationbasedonmappingmethodandDelaunaytriangulation[J].JournalofCom2puter2AidedDesign&ComputerGraphics,2002,14(1):56～60(inChinese)
(熊 英,胡于进,等.基于映射法和Delaunay方法的曲面三
序实现[硕士学位论文].大连:大连理工大学,2001)
[52]
LohnerR,ParikhP.Generationofthree2dimensionalunstructuredgridsbytheadvancing2frontmethod[J].InternationalJournalforNu2mericalMethodsinFluids,1988,8(10):1135～1149[53]
LohnerR,ParikhP,GumbertC.Interactivegenerationofunstruc2turedgridforthreedimensionalproblems[A].In:ProceedingsofNumericalGridGenerationinComputationalFluidMechanics’88,Swansea:PineridgePress,1988.687～697[54]
LohnerR.Progressingridgenerationviatheadvancingfronttech2nique[J].EngineeringwithComputers,1996,12(3Π4):186～210
[69][68]
角网格划分算法[J].计算机辅助设计与图形学学报,2002,
14(1):56～60)
DanielRypl,PetrKrysl.Triangulationof3Dsurfaces[J].Engineer2ingwithComputers,1997,13(2):87～98
CuilliereJC.Anadaptivemethodfortheautomatictriangulationof3Dparametricsurface[J].ComputerAidedDesign,1998,30(2):139～149
1期
[70]
关振群等:有限元网格生成方法研究的新进展
MeiZY,FanYQ,etal.FiniteelementmeshgenerationofNURBSsurface[J].JournalofComputer2AidedDesign&ComputerGraph2ics,1997,9(4):289～294(inChinese)
(梅中义,范玉青,等.NURBS曲面的有限元网格三角剖分[J].计算辅助设计与图形学学报,1997,9(4):289～294)
[84][83]
13
MurdochP,BenzleySE.Thespatialtwistcontinuum[A].In:Pro2ceedingsofthe4thInternationalMeshingRoundtable,Albuquerque,1995.243～251
FolwellNT,MitchellSA.Reliablewhiskerweavingviacurvecont2raction[A].In:Proceedingsofthe7thInternationalMeshingRoundt2able,Dearborn,1998.365～378
[71][72]
LauTS,LoSH.Finiteelementmeshgenerationoveranalyticalcurvedsurfaces[J].Computer&Structures,1994,59(2):301～309LandertshamanF,SteffanH.Methodtogenerationcomplexcomputa2tionalmeshesefficiently[J].CommunicationsinNumericalMethodsinEngineering,1994,10(5):373～384
[86][85]
Müller2HannemannM.Quadrilateralsurfacemesheswithoutself2in2tersectingdualcyclesforhexahedralmeshgeneration[J].Computa2tionalGeometry,2002,22(1Π3):75～97
TamTKH,ArmstrongCG.Finiteelementmeshcontrolbyintegerpreprogramming[J].InternationalJournalforNumericalMethodsinEngineering,1993,36(15):2581～2605
[73]TakeoTaniguchi,TomoakiGoda,HaraldKasper,etal.Hexahedralmeshgenerationofcomplexcompositedomain[A].In:Proceedingsofthe5thInternationalConferenceonGridGenerationinComputationalFieldSimulations,MississippiStateUniversity,1996.699～707
[87]
RooseD,DriesscheRV.ParallelcomputersandparallelalgorithmsforCFD[J].AdvancesinMechanics,1998,28(1):11～126(inChinese)
(RooseD,DriesscheRV.并行计算机和计算流体力学并行算
[74]ZuoX,WeiYP,ChJ,etal.Anelementtransformationandopti2mizationmethodin3Dautomatichexahedralmeshgeneration[J].ChineseJournalofComputationalMechanics,1999,16(3):343～348(inChinese)
(左 旭,卫原平,陈 军,等.三维六面体有限元网格自动
[88]
法[J].力学进展,1998,28(1):11～126)
deCougnyHL,ShephardMS.Parallelvolumemeshingusingfaceremovalsandhierarchicalrepartitioning[J].ComputerMethodsinAppliedMechanicsandEngineering,1999,174(3Π4):275～298[89]
GaltierJ,GeorgePL.Prepartitioningasawaytomeshsubdomainsinparallel[A].In:Proceedingsofthe5thInternationalMeshingRoundtable,Pittsburgh,1996.107～121
[90]
ShostkoA,LohnerR.Three2dimensionalparallelunstructuredgridgeneration[J].InternationalJournalforNumericalMethodsinEngi2neering,1995,38(6):905～925[91]
deCougnyHL,ShephardMS,OzturanC.Parallelthree2dimen2sionalmeshgenerationondistributedmemoryMIMDcomputers[J].EngineeringwithComputers,1996,12(2):94～106
[92]
ZhangMM,PanZG,ZhengWT,etal.Adistributedparallelal2gorithmforDelaunaytriangulationofscattereddatapoints[J].Jour2nalofComputer2AidedDesign&ComputerGraphics,2000,12(7):484～487(inChinese)
(张明敏,潘志庚,郑文庭,等.散乱点集Delaunay三角剖分的
划分中的一种单元转换优化算法[J].计算力学学报,1999,
16(3):343～348)[75]
StatenML,CanannSA,OwenSJ.BMSWEEP:Locatinginteriornodesduringsweeping[A].In:Proceedingsofthe7thInternationalMeshingRoundtable,Dearborn,1998.7～18[76]
LaiMW,BenzleySE,SjaardemaG,etal.Amultiplesourceandtargetsweepingmethodforgeneratingall2hexahedralfiniteelementmeshes[A].In:Proceedingsofthe5thInternationalMeshingRoundtable,Dearborn,1998.217～228
[77]
GuanZQ,GuYX,MaZHY,etal.Finiteelementmodelingpro2gramAutoFEMbasedonAutoCAD[J].ChineseJournalofComputa2tionalMechanics,1998,15(2):239～244(inChinese)
(关振群,顾元宪,马正阳,等.基于AutoCAD的有限元建模系
统AutoFEM[J].计算力学学报,1998,15(2):239～244)
[78]
FiniteelementanalysisanddesignoptimizationsoftwaresystemJIFEXV2.0manual.Dalian:DalianUniversityoftechnology,1999(inChinese)
(有限元分析与优化设计软件系统JIFEXV2.0用户手册.大
[93]
分布并行算法[J].计算机辅助设计与图形学学报,2000,12
(7):484～487)
ChrisochoidesN,NaveD.Simultaneousmeshgenerationandparti2tioningforDelaunaymeshes[J].MathematicsandComputersinSim2ulation,2000,54(4Π5):321～339[94]
KhoeiAR,LewisRW.H2adaptivefiniteelementanalysisforlocal2izationphenomenawithreferencetometalpowderforming[J].FiniteElementsinAnalysisandDesign,2002,38(6):503～519
[95]
FuenmayorFJ,RestrepoJL,TarancónJE,etal.Errorestimationandh2adaptiverefinementintheanalysisofnaturalfrequencies[J].FiniteElementsinAnalysisandDesign,2001,38(2):137～153
[96]
HanCS,WriggersP.Anh2adaptivemethodforelasto2plasticshellproblems[J].ComputerMethodsinAppliedMechanicsandEngi2neering,2000,189(2):651～671[97]
TerescoJD,BeallMW,FlahertyJE,etal.Ahierarchicalparti2tionmodelforadaptivefiniteelementcomputation[J].ComputerMethodsinAppliedMechanicsandEngineering,2000,184(2Π4):269～285
连:大连理工大学,1999)
[79]
SchneidersR.Agrid2basedalgorithmforthegenerationofhexahedralelementmeshes[J].EngineeringWithComputers,1996,12(3Π4):168～177[80]
LoicM.Anewapproachtooctree2basedhexahedralmeshing[A].In:Proceedingsofthe10thInternationalMeshingRoundtable,New2portBeach,2001.209～221[81]
TautgesTJ,BlackerT,MitchellS.Thewhisker2weavingalgo2rithm:Aconnectivitybasedmethodforconstructingall2hexahedralfi2niteelementmeshes[J].InternationalJournalforNumericalMethodsinEngineering,1996,39(19):3327～3349[82]
BlackerTD,MeyersRJ.Seamsandwedgesinplastering:A3Dhexahedralmeshgenerationalgorithm[J].EngineeringWithComput2ers,1993,9(2):83～93
14
[98]
计算机辅助设计与图形学学报
AlmeidaRC,FeijoRA,etal.Adaptivefiniteelementcomputa2tionalfluiddynamicsusingananisotropicerrorestimator[J].Com2puterMethodsinAppliedMechanicsandEngineering,2000,182(3Π4):379～400
[106]
2003年
QiXY,YangF,QiC,etal.Studyongridgenerationtechniqueforbody2fittedcoordinatesystem[J].JournalofEngineeringThermo2physics,2001,22:29～32(inChinese)
(齐学义,杨 帆,齐 冲,等.贴体坐标网格生成技术的研究[J].工程热物理学报,2001,22(S1):29～32)
[99]ZhuHQ,WangMQ,ChengXL.Generationof2Dirregularadapt2edVoronoicellsbasedgridanditsapplications[J].ChineseJournalofComputationalMechanics,2002,19(1):105～108(inChinese)(朱怀球,王美秋,程雪玲.基于Voronoicells的二维不规则自
[107]
HeH,WangXF,LuRS.Anewmethodforgenerationoforthogo2nalbody2fittedcurvilinearcoordinatesystems[J].JournalofWuhanUniversityofHydraulicandElectricEngineering,1999,32(4):20～23(inChinese)
(何 泓,王献孚,陆瑞松.正交贴体坐标生成的一种方法[J].
适应网格的生成及其应用[J].计算力学学报,2002,19(1):105～108)
[100]
WangWX,DengDH.Anadaptivemeshgenerationalgorithmbasedongeometricfeaturesandmechanicalproperties[J].JournalofComputer2AidedDesign&ComputerGraphics,2001,13(1):52～55(inChinese)
(王威信,邓达华.基于几何特征和力学特性的自适应网格生
[108]武汉水利电力大学学报,1999,32(4):20～23)
ZhangLP,XuQX,ZhangHX.ParallelnumericalsimulationsofcomplexinviscidflowsonunstructuredandstructuredΠunstructuredhybridgrids[J].ActaAerodynamicaSinica,2002,20:14～20(inChinese)
(张来平,徐庆新,张涵信.非结构网格及混合网格复杂无粘
成算法[J].计算机辅助设计与图形学学报,2001,13(1):52～
55)
[101]
HuangCY.Recentprogressinmultiblockhybridstructuredandun2structuredmeshgeneration[J].ComputerMethodsinAppliedMe2chanicsandEngineering,1997,150(1Π4):1～24
[102]
LoSH.3Danisotropicmeshrefinementincompliancewithageneralmetricspecification[J].FiniteElementsinAnalysisandDesign,2001,38(1):3～19
[103]
XuMH,TaoWQ.Generationandapplicationof2Danisotropicun2structuredgrids[J].JournalofXi’anJiaotongUniversity,2002,36(3):221～225(inChinese)
(徐明海,陶文铨.二维各向异性非结构化网格的自动生成与
[110][109]
流场并行计算方法研究[J].空气动力学学报,2002,20(S1):
14～20)
WangP,ZhuZQ,TuoSF,etal.2Dhybridstructured2unstruc2turedgridgenerationandflowsimulation[J].ActaAeronauticaetAstronauticaSinica,2001,22(6):536～538(inChinese)
(王 平,朱自强,拓双芬,等.二维结构Π非结构混合网格的生
成及其流场模拟[J].航空学报,2001,22(6):536～538)
GuanZQ,SuiSF,SongC,etal.ACAD2basedparameterizationmethodoffiniteelementmodelingforstructuralshapeoptimization[A].In:Proceedingsofthe4thWorldCongressofStructuralandMultidisciplinaryOptimization,Dalian,2001.418～420
[111]
DaiL,SuiXF,GuanZQ,etal.Aparameterizationmethodoffi2niteelementmodelingforthree2dimensionalcompositesurface[J].JournalofHarbinInstituteofTechnology,2001,33(suppl):138～140(inChinese)
(戴 磊,隋晓峰,关振群,等.空间组合曲面的参数化有限元
应用[J].西安交通大学学报,2002,36(3):221～225)
[104]
WuZN.AnisotropicCartesiangridmethodfortheNavier2Stokesequations[J].JournalComputationalPhysics,1998,15(4):463～475(inChinese)
(吴子牛.NS方程的各向异性笛卡尔网格法研究[J].计算物
理,1998,15(4):463～475)
[105]
WeiWL,ZhangZX,LiuYL,etal.ResearchonthesourcetermsPandQofPossionequationsforgridgeneration[J].ChineseJournalofAppliedMechanics,2000,17(3):87～91(inChinese)
(魏文礼,张宗孝,刘玉玲,等.采用Poisson方程生成曲线网格
建模方法[J].哈尔滨工业大学学报,2001,33(增刊):138～
140)
时源项P、Q选择的研究[J].应用力学学报,2000,17(3):87～
91)
因篇幅问题不能全部显示，请点此查看更多更全内容