二维全四边形网格的自动生成算法

第10卷第1期2003年2月塑性工程学报JOURNA L OF P LASTICITY E NGI NEERI NGV ol 110　N o 11Feb 1　2003二维图形的四边形有限元网格划分(北京机电研究所,北京　100083)　刘晓飞　金泉林摘　要:本文介绍了一种对二维图形进行四边形有限元网格划分的算法,算法的关键在于边界网格单元的生成及处理,以使其能够与原始图形边界相吻合,同时具有较规则的网格形状。

关键词:有限元;四边形网格中图分类号:TG 30 文献标识码:A 文章编号:100722012(2003)0120009204收稿日期:20022012151　引　言在有限元锻压数值模拟计算程序中,对物体进行有限元网格划分是一个关键步骤。

对于二维问题(平面变形问题或轴对称变形问题),有限元网格可分为三角形单元网格和四边形单元网格两种,由于四边形单元网格不管在逼近离散域方面,还是在网格质量方面,以及在计算精度方面都较三角形单元优越,因此二维问题普遍采用四边形单元网格。

进行网格划分包含在两个过程,一是数值模拟计算前对物体进行的初始网格划分;二是在数值模拟计算中,由于物体变形导致部分网格形状畸变而进行的自动网格重划分,从而重新获得规则的网格以继续进行计算。

网格重划分过程涉及到新旧网格之间的节点、单元变量的插值计算和数据转换,因此频繁的网格重划分必然导致计算精度的下降,同时增加了计算时间。

所以,如何获得较规则的单元网格,以便有效的减少网格重划分的次数,使模拟计算过程连贯进行,是四边形单元网格划分算法中的关键之一;同时,单元网格中的边界网格还起着描述物体外形轮廓的作用,它们不但要具有较好的网格形状,而且也要和原始物体的边界轮廓相吻合,否则会造成物体外形失真及体积变化,影响计算结果;当物体的某些局部几何尺寸很小时,则也需要划分相当尺寸的网格才能将它描述精确,如果整个物体都划分为和此网格一样大小的均匀网格,那么网格单元数目将非常多,这将大大增加计算时间。

自动网格生成法二维网格生成—Advancing Front方法从概念上来讲，Advancing front方法是最简洁的方法之一。

单位元素生成算法始于一个特殊边界条件所定义的“front”,此算法逐级地生成各个元素，同时“front”元素离散地前进，直至整个区域都被元素所覆盖。

网格生成过程包括三个主要步骤：1、在边界上生成节点，形成一个离散的区域边界。

2、在离散区域边界内生成元素（亦或节点）。

3、强化节点形状以提高网格图形清晰度。

在介绍这个方法之前我们先介绍以下有关于二维空间地几何表示。

一、二维网格的几何特征我们利用网格参数（一般是空间的函数）来表征网格的一些性质，诸如节点尺寸，节点形状和节点方向等等。

网格参数包括两个相互正交的单位矢量a1和a2表示的方向参数，和由两个相互正交代表节点形状的矢量的模值h1和h2。

前者表征网格节点伸展的方向，注意的是，只有在生成的是非各向同性的网格内，方向参数才有定义，否则方向矢量是常单位矢量，而尺寸参数有h1=h2，这样就定义了各向同性的平凡网格。

二、区域的几何表示边界曲线的表示：我们一般用组合参数样条线表示曲线边界单位，利用参数t，我们利用二维矢量函数表达出曲线边界：r t=x t,y t,0≤t≤1一般来讲，一条组合样条曲线至少是C1连续的，以保证边界曲线平滑和算法要求的数学连续性。

我们下面将要用厄米三阶样条线，当然还有许多就不一一举例了。

样条线的参数表达式如下：X t=H0t,H1t,G0t,G1t∗x0,x1,x,t0,x,t1T,0≤t≤1转置的前两项是曲线的两个端点，而后两项是它们对t求导现在端点处的值。

另外G和H分别是四个三阶厄米多项式：H0t=1−3t2+2t3 ; H1t=3t2−2t3G0t=t−2t2+t3 ; G1t=−t2+t3此时，参数表达式可以通过一个系数矩阵来描述：X t=1,t,t2,t3M x0,x1,x,t0,x,t1T,0≤t≤1其中M矩阵读者很容易写出，是一个4*4的方阵，而每一列是这些厄米多项式的系数排列而成。

网格图形的计算与应用随着计算机技术的不断发展，网格图形在各个领域的计算与应用中发挥着重要的作用。

网格图形是由一系列节点和边组成的二维或三维结构，它可以用于模拟和分析复杂的现实问题，如物理仿真、医学图像处理、城市规划等。

本文将探讨网格图形的计算方法和应用领域，并介绍一些相关的研究进展。

一、网格图形的计算方法网格图形的计算方法主要包括网格生成、网格优化和网格变形等。

网格生成是指根据给定的几何模型自动生成网格的过程。

常见的网格生成算法有四边形网格生成算法、三角形网格生成算法和自适应网格生成算法等。

网格优化是指通过调整网格节点和边的位置，使得网格的质量达到最优的过程。

常见的网格优化算法有Laplacian平滑算法、Delaunay三角化算法和拓扑优化算法等。

网格变形是指通过对网格节点和边进行形变操作，改变网格的形状和结构。

常见的网格变形算法有拉普拉斯变形算法、弹性网格变形算法和形状优化算法等。

二、网格图形的应用领域网格图形在各个领域的应用非常广泛。

在物理仿真领域，网格图形可以用于模拟材料的力学行为、流体的运动行为和光的传播行为等。

例如，在汽车工业中，可以利用网格图形模拟汽车的碰撞行为，以评估汽车的安全性能。

在医学图像处理领域，网格图形可以用于对医学图像进行分割、配准和重建等操作。

例如，在肿瘤治疗中，可以利用网格图形对患者的CT扫描图像进行分割，以确定肿瘤的位置和大小。

在城市规划领域，网格图形可以用于建立城市的地理信息系统，进行城市的规划和管理。

例如，在城市交通规划中，可以利用网格图形模拟交通流量，以优化交通信号的配时方案。

三、相关研究进展近年来，网格图形的计算和应用方面取得了一些重要的研究进展。

例如，在网格生成方面，研究人员提出了一种基于机器学习的自适应网格生成算法，能够根据输入的几何模型自动调整网格的密度和形状。

在网格优化方面，研究人员提出了一种基于人工智能的拓扑优化算法，能够通过学习和演化的方式优化网格的拓扑结构，提高网格的质量和效率。

四边形网格间接生成方法刘晶;聂玉峰;苏少普【摘要】研究了基于背景三角网格的四边形网格间接生成算法,并针对三角形合并过程中容易残留三角形的缺陷提出了确定侧边的详细算法,该算法主要是依据背景三角网格中边的位置和前沿边的情形,通过背景三角网格中已存在的边、边交换或边分割确定侧边,以避免在三角形合并过程中残留三角形单元.最后给出实例验证了算法的有效性.【期刊名称】《计算机工程与应用》【年(卷),期】2010(046)002【总页数】4页(P44-47)【关键词】四边形网格;三角形合并;前沿边【作者】刘晶;聂玉峰;苏少普【作者单位】西北工业大学,应用数学系,西安,710072;西北工业大学,应用数学系,西安,710072;西北工业大学,应用数学系,西安,710072【正文语种】中文【中图分类】O242.211 引言随着有限元方法在工程中的深入广泛应用，人们对有限元计算精度的要求越来越高，而网格的质量对有限元计算精度有重大影响，因而对网格生成方法的研究一直受到人们的重视[1-13]。

二维区域中常用的有三角形网格和四边形网格，三维区域上则常用四面体、三棱柱或六面体网格。

对二维问题，三角形网格的生成算法理论已相对较为成熟，但在具体的求解过程中，使用三角形元的求解精度通常不及使用四边形元的求解精度，故研究基于三角形网格的四边形网格生成算法。

2 基本概念（1）固定节点和可动节点：位于区域边界上的节点为固定节点，区域内部的点则为可动节点。

（2）节点连通度：在网格内与节点相连的单元数目即为节点的连通度。

（3）不规则节点：在四边形网格内部节点连通度不为4的节点即为不规则节点。

（4）结构化网格：是指网格内部各节点的连通度相同的网格。

（5）非结构化网格：与结构化网格相对，非结构化网格是指网格内部各节点的连通度不同的网格。

（6）几何优化：是指调整可动节点的位置而不改变节点的拓扑连接关系以改进网格质量的操作。

（7）拓扑优化：是指改变可动节点的拓扑连接关系以改进网格质量的操作。

一种全四边形网格生成算法
郑志镇;杨国道
【期刊名称】《华中理工大学学报》
【年(卷),期】1997(025)011
【摘要】提出了一种全四边形网格生成算法，该算法先离散区域的边界，然后从边界开始向内部生成风格，根据边办上相邻节点内角的特征采用不同的生成策略，实现时进一步内部处理的方法，效率较高，由于只考虑区域的局部特征，网格质量较好，通用性较强，最一给出了网格的生成的实例。

【总页数】3页(P76-78)
【作者】郑志镇;杨国道
【作者单位】机械科学与工程学院;机械科学与工程学院
【正文语种】中文
【中图分类】O242.21
【相关文献】
1.一种新型四边形网格生成的自动算法 [J], 张卫东;阮雪榆
2.一种全四边形网格生成方法——改进模板法 [J], 李华;李笑牛;程耿东;吴杰
3.一种改进的全四边形网格生成方法及优化 [J], 李晓辉;李昌华
4.一种改进的高品质全四边形网格生成方法 [J], 林胜良;方兴;张武;王正光
5.一种全四边形有限元网格生成方法─—堆砌法 [J], 王世军;黄玉美;张广鹏
因版权原因，仅展示原文概要，查看原文内容请购买。

一种全四边形有限元网格生成方法——堆砌法一种全四边形有限元网格生成方法——堆砌法第36卷第l0期2000年10月机械工程CHINESEJOURNALOFMECHANICALENGINEERING V36No10Oct.2000一种全四边形有限元网格生成方法——堆砌法王世军(西安理工夫学机械与张广鹏院西安710048)7一7仡1))中围j2_-一——,0《ul1..0前言有限元方法是一种在工程上非常重要的数值分析方法,尤其是在复杂结构的分析中得到广泛应用随着计算机技术的快速发展,分析问题的规模越来越大,从印,70年代的几十至几百个结点到目前的几十万至几百万个结点.用人工进行网格划分已经不能满足需要.另一方面,自适应分析与设计技术的出现与发展,也迫切要求网格划分自动化.有限元网格的自动生成算法有着潜在的,巨大的价值,在这个领域一直有着广泛的研究.这些研究多数都使用三角形网格,三角形单元的精度较四边形低,在分析过程中并不推荐使用.也有部分算法可以实现部分的或完全的四边形网格划分,但是这些算法往往存在这样或那样的问题,不能获得广泛使用.铺路法(Pavingmethod)_】是目前较好的一种全四边形网格生成算法_2"J,生成的网格质量较高.缺点是算法复杂,计算时问长,对复杂形状的划分区域适应性差,因此,难以将其推广到三维区域.本文针对铺路法的这些特点,提出了一种改进算法一堆砌法,较好地克服了铺路法存在的缺点.1堆砌法的原理铺路技术是将单元一层一层从边界铺到区域的内部,如图1所示,这些单元最终会填满整个划分区域.一般说,在区域内部铺设单元时,肯定会产生交叠.在一层单元铺设完毕后,要对交叉的部分进行特殊处理——边的缝合和单元湮灭,使得生成的单*西安理工大学青年科技基盎资助项目,20000228收到初稿2o~o4i5收到修改祷元之间保持相容性.之后进行光顺处理.交叉部分的处理,是铺路技术的难点.区域形状越复杂,产生的交叉越多,处理起来越麻烦,处理时间也越长.口口(b)日醒噩(c)图1铺路法原理堆砌技术的基本思想是沿着网格划分区域内的一条直线铺设单元,铺完一层单元以后,平移这条直线,在新的平行线上继续铺设新一层单元.直到整个区域铺满单元.如图2所示,在铺设每一层单元时,都是从区域的一个边界开始向另一个边界铺设.(B)图2螓砌浩原理图口加∞年1O月王世军等:一种全四边形有限元网格生成方法——堆砌法铺完一层后,再开始铺设另一层,直到铺满整个区域.可以看出,与铺路法明显不同的是,这里每一个单元层都是不封闭的,一般情况下只有2个端点在固定边界上,单元层不会产生交叉,避免了复杂的单元缝合处理.下面说明堆砌法的几个主要步骤.1.1单元的生成单元的生成是堆砌法的核心,涉及多方面的内容.首先是选择背景线的起点,问距和推进方向,其次是单元组中单元的生成,最后是单元的光顺处理.在任何一个单元生成之前,必须首先定义单元的大小(单元的尺度).单元的尺度是以单元的边长来表示的,它是单元边长的期望值.单元尺度是在划分区域的背景上,以尺度场的方式定义的.1.2背景线的确定背景线(也称为水面线)是一条指示单元层铺设位置和方向的线.背景线的起点可以是任意的边界位置,方向也可以随机选定.在铺出第1层单元以后,根据第2层单元中的最大的基本尺寸确定第2条背景线的位置.通常,背景线的方向可以选择几何区域最大尺寸的方向,这样生成的单元层数比较少,相应地,不规则结点的数目也比较少.如图3所示,由于背景线的控制,不会发生铺路法中必然产生的单元层的交叠.(日)多十浮动边界的生成(b)多十浮动边界的台井图3浮动边界的生成与合并1.3根结点的选定与单元层的生成网格划分之前,首先要将区域的边界按指定的单元数目或大小进行离散,形成离散边界.选择背景线以下与离散边界结点最近的结点作为第1层单元的根结点.第1层单元的铺设是从根结点开始,沿着固定边界向第2个根结点单向铺设.浮动边界与固定边界的交点作为单元层的生长结点从第2 层开始,以新旧浮动边界的交点作为单元的生长结点.单元层的第1个生长结点总是浮动边界与固定边界的交点.这样,可以避免铺路法中单元铺设位置的复杂判断.通常情况下,根结点是成对的.而且可以有多对.在单元的生成过程中,可以产生新的根结点,原有的根结点也可能湮灭.如图3所示.1.4单元组中单元的生成单元的生成分两步,第1步是预测,第2步是校正. 图4显示了预测步骤的过程.构造1个矢量厶c-,矢量的方向根据结点A剩余角度大小相应地取1/2,1/3剩余角度,保证新生成单元A点内角尽图4新结点位置的搜索可能接近90~.类似地可以构造另一个矢量k,.两个矢量的交点就是新结点的试探位置C.找到初始的试探位置后,还需进一步的校正,以改善新单元的质量.以基本边长为半径,以A,B结点为圆心,构造2个圆.求2个圆的交点.交点可能有2个,1个,或者没有.对于存在2个交点的情况.取内角为正的结点为.可以证明,对于有一个交点和没有交点的情况,只要保证前面生成单元的内角均接近90~,就不会发生这2种情况.得到2个新结点的位置以后,以这两个结点联线的中点作为新单元的最终结点位置C.这样获得的单元,兼顾边长和角度的要求,单元生成的速度比较快.在试探新结点位置之前,要先作一下检查,防止生成单元交叠或与边界不相容.如图4所示.检查的方法是以为半径,以当前结点为圆心,构造一个圆=kl^r一l+N (I)k是1个系数.一和+是2个矢量,起点都是结点^r,末端点分别是结点—I和^r…,如图4所74机械工程第36卷第lO期示.较快.在这个圆内,可能存在固定边界上的结点或多于1个的旧浮动边界上的结点.如果存在这两种情况,就不能按照前面的步骤生成单元.第1种情况,圆内存在固定边界结点,说明浮动边界已经接近固定边界.如果固定结点在半径为R:√21的同心圆内,则以固定比边界上的结点作为新结点位置.l为基本边长.固定边界和浮动边界因为有公共结点而被分为2个部分.新生成的固定边界和浮动边界两两构成的封闭区域,其边界结点数应保持为偶数,否则不应以这个固定结点作新结点,而位取另1个相邻的固定结点作边界结点.如果在圆内存在另外1个与之相邻的固定边界结点,就选择另1个.否则,按前述方法生成新结点.第2种情况,圆内存在第二个浮动边界上的结点,新结点的位置应该取在圆心与浮动边界的结点联线的中心上.为保持浮动边界的平直性,新单元生成以后,应当结束单元层的生成,从新的根结点开始生成新一层单元.由上述单元生成过程可以看出,新方法与铺路法相比,有几个优点.第一,不会产生铺路法特有的单元交叠,从而避免了包含复杂的拓扑形状判断的单元缝合过程.第二,铺路法中楔单元的插入和角结点单元的形成在这里都是单元生成过程中自然形成的,不需要特殊处理,程序结构得到简化.第三,单元的生成过程已经考虑到相邻的未生成单元的形状,不会生成质量越来越差的单元.避免了铺路法中每生成一个单元都要进行的局部光顺处理.2单元的光顺处理在区域内充满单元以后,对整体单元的质量进行一次检查,如果单元角度或边长比有超过允许值的,需要对整体单元进行光顺处理,以进一步提高整体单元的质量.这里使用修正的加权长度的拉普拉斯光顺算法j.这种算法是用一系列矢量从一个内部结点指向这个结点所有相邻结点.用一个贡献矢量作为这个内部结点相邻结点的贡献量.如图5所示,结点位置的修正量为互IcJIcj△=号置'cJIc是与内部结点i相邻结点的贡献矢量,是与结点i相邻结点的个数.这个算法使得边界单元的边趋向垂直于边界,边长则趋于均化,而且收敛速度3算例N.图5单元的光顺处理图6是在一个内部含有空洞的区域上获得的网图6古有复杂内部边界的区域剖分效果格.背景线方向沿水平方向,自下而上推进.网格的基本尺寸定义得比较大,生成网格在边界上仍然有较好的形状和尺寸一致性最大偏差角△=29.1..图7是一个具有复杂边界形状的陕西省地图的固7具有复杂外边界的区域剖分效果2OOO年10月王世军等:一种全四边形有限元网格生成方法——堆砌法轮廓.网格密度定义为上疏下密.背景线方向沿水平方向,推进方向也是自下而上.图示结果表明,算法对复杂边界的适应性是比较强的,疏密过渡也较为平滑.最大偏差角A:3O.7..4结论由于网格划分过程的复杂性,精确地评价一个算法的优劣是困难的.新算法避免了单元层之间的交叠,从而避免了网格生成过程中复杂的拓扑结构的判断和单元形状校正所需的迭代计算.因而可以定性地说,这-t-~t法与铺路法相比是一个好的算法.圈8是实测的网格结点数与划分时间的关系.在60∞个结点以下,结点数与时间基本保持线性关系之*匠蕾晶同格结点数/个数图8网格结点数与时间的关系参考文献TedDIll~ker,Micl~lBsIpIler咖Paving:ar?e8pn日chL0automatedq【md_咖meshm帆IntJ.Numberie~9inbginl1g,1991,32:811—847752SabinM.Criteriaforc0ⅢD日m0fal1l0mcmeshge~aon m由A.EI】gs0盘ware,1991,13(5/6):2213—2253Hc-LeKFimteelementmesh珊0I|meLl:areviewarIdcl~itlcationC~uter-Aided咄,1988,加(1):27—384M哪S.NoelF,LeonJC.r唧劬0n0fquadrilateralmesl1s 0nfree-ferm目u1b∞C∞1a-,d~ures,1999,71:505—524HEA]PlNG:ANEWM咽1l10DmRALLQ10~DIlILA/~_,SttGE既10NWang蜘皿ⅫY~2eiZhangGuo,~,peng(_衄妇ofwf0)Atr毗Ametl~a—b嘲pil】gmeIIl0d,Ⅶl1icI1岬b曰oulld htodetenffmer日∞e_吐ofquadrilateralelements presentedThemd-l0disn∞陀simplelpavingIT_et}-0din ~turearld_细inu目eitavoidsa∞8esimelcrIslⅥe目lelemellnt~laye~-Inthisp日per,II'e0fyofl|pn,tetl~is缸irred.Secondly,tw.忸amplesaregiven.AIl86t.;tsl~erfol'lnanceiBevuaKey,r凼:Finiteele~enlMee~hQI1ad同日-eIalH嘲ping作者荷彳r王世军,男,1967年出生,讲师.博士生.主要从事机械结掏的有限元分析爰同格捌分算{击的研究.(上接第71页)REC暇E圈睡:ED00N0FAMaI】.I℃H'sE】GAGEMENTGeAn//nGao咖.肺删(同of西)Ab喇AI1ewccmetl~ofhydrauliceyli~risput.ItcontroltI.ecydir?d盱speedbdiscretepr黜ise也pIcem咖.Theperformi~itufionAjIfr(A岫舢a0edmeclmi~tI】蛐日mis吕i0I.)vehicle'sclutchalwaysadop饵hya~alcylindBr.But mt~iollpIeE艘1bedbe血gectedl0manyfaete~inreBIily,has血ec0f胡'svi州arIdtI.ete帅force0fIIg,eIc.Itbr;di伍to.1heperimen出thattI.epmf~edmethodcanetI.eclutcher日IaHy~--eeisepeedarld删atv0ffaulttoler~.脚:Hy~ulieeyli~rHiglIswitchdec舡啊rmrcvalveSpeed∞rIⅡ0l作者苘彳r葛安林.男,1936年出生.吉林工业大学穰力机艟传动研究所所长,教授,博士生导师,主要从事自动变速理论与控制技术的研究.先后获国家,省部毅奖励lO余璃.发明专利6项,发表论文6o余篇。

一种全四边形的网格自动生成方法-铺砌法２０００年１２月第２９卷第６期河北工业大学学报Ｄｅｃｅｍｂｅｒ２０００ｊ０ＵＲＮＡＬ０ＦＨＥＢＥｌｌ掰ｌＶＥＲＳｌ下ＹｏＦＴＥＣＨＮｏｋｏＧＹ、蝴．２９Ｎｏ．６文章编号：１００７＿２３７３（２０００）０６＿０∞９．４３一种全四边形的网格自动生成方法一铺砌法傅苏红，马书尧（河ｊｂ工业大学机械学院，辩墨葛；ｉｊ！ｊ从而：煎黉塞一番嚣季邓伸拍叁儡嚣葺薹×冀鬻警牟§，应当有一种实现等精度加工的方法，根据技术要求，找出曲面上不同点的经济步长，据此确定出迸刀策略．下面将讨论实现这种自适应规划的方法．２．１行距的确定加工图ｌ所示表面时，当刀具走完第一条等参数曲线后，如何确定加工下一条等参数曲线时刀心的位置呢？若加工的第一条等参数曲线为尉“．，∞，选择的刀具半径为Ｒ，则加工第一条参数曲线时刀心的位置在品（“．．∞上．从图４可得到两个加工特征三角形△ｏＡｃ和△ＯｃＢ，Ａ、Ｂ两点分别为赢（“。

ｖ）和品（蚰，一上的两对应点，ｃ点为两对应刀位包络面的交点．从这两个三角形可求出口点的坐标．由于爿Ｂ线段较短，可近似看作一圆弧，其半径为一曰曲线段中点的曲率半径．由图司得，０姐＝卢±Ｒ，０ｃ＝卢士一ｋ，爿ｃ＝月；根据三角定理可知：。

＿ｃｏｓ叫骘舞虢锄铲］（６）式中：ｐ为参数曲线斟“．由上铣刀切削点的曲率半径．“＋”用于加工凸曲面，“．”用于加工凹曲面．又从图可知△ＡｏＢ为近似等腰三角形，顶角为２Ⅱ，而２ａ是。

君两点法矢量的夹角，所以有：吉蔷泓…√专蔷泓…。

≈ａ∽Ｆ：×ｉ：儿。

，。

ｌ一．ｘＦ：ｍ。

，。

‘“Ｌ７Ｊ当已知给定的行距误差一ｋ，铣刀半径Ｒ及初始铣削行参数雪（砺，∞后，由（６）、（７）式就可求出下一铣削参数曲线ｊ（∞，∞或行距一“．由公式可以看出，当ｄＡ。

确定阱后，铣刀半径越大，所允许的行距越大，铣削点曲率半径越大，所允许的行距越大．按照上述方法确定的行距进刀，曲面上每行刀具轨迹的最大碳留量将是一致的．２．２步距的确定当行距确定后，刀具在雪（珥，ｖ）上做怎样的插补运动才能切出各点步距方向过切量（一‰）相等的包络面呢？如图５所示，当刀具从ｃ点吾（“。

第5卷第1期2006年2月江南大学学报(自然科学版Journal of Southern Yangtze U niversity(N atural Science EditionVol.5No.1Feb.2006文章编号:1671-7147(200601-0070-04收稿日期:2004-12-07;修订日期:2005-02-21.基金项目:浙江省教育厅回国人员基金项目(113201-G 59990.作者简介:林胜良(1976-,男,浙江温州人,结构工程专业硕士研究生.3通讯联系人:张武(1964-,男,四川涪陵人,副教授,工学博士,硕士生导师.主要从事有限元等研究.Email :zhangwu @一种改进的高品质全四边形网格生成方法林胜良,方兴,张武3,王正光(浙江大学建筑工程学院,浙江杭州310027摘要:在网格生成诸方法中,铺路法自动化程度高、生成的单元质量好,是一种很值得研究的方法.但该方法步骤繁琐,且相交处理过程非常复杂,为了提高该方法的可靠性和适应性,文中作了一些改进,在删除一些繁琐操作的同时,加入了一些新的算法规则,采用边生成网格边进行相交判断的方法,一旦发现相交情况发生,立即终止网格生成而转入相交处理模块.最后给出了两个网格实例,证明了该改进方法的有效性.关键词:网格生成;四边形单元;铺路法中图分类号:TP 399文献标识码:AA Modif ied Method of G enerating Excellent Q uadrilateral MeshL IN Sheng 2liang ,FAN G Xing ,ZHAN G Wu 3,WAN G Zheng 2guang(Architecture and Civil Engineering Institute ,ZhejiangUniversity ,Hangzhou ,310027,ChinaAbstract :In t he met hods of mesh generation ,t he paving met hod is wort hy of st udying ,which possesses p roperties of high automatizatio n degree and generating excellent element.But t he p rocess is f ussy ,and t he course of intersection dispo sal is very complex.For enhancing t he reliability and applicability of t he met hod ,t his paper make some beneficial improvement.Removing so me f ussy operations ,and t he same time ,adding some new arit hmetic algorit hms.Adopting t he met hod of carrying t hrough intersection judgment while generating mesh.Terminating mesh generation immediately and switching to t he module of intersection dispo sal while finding intersection occuring.In t he end ,two examples are given to verify t he validity of t he modified met hod.K ey w ords :mesh generation ;quadrilateral element ;paving met hod网格剖分在有限元方法中占有非常重要的地位.随着有限元方法的广泛应用,网格剖分技术的研究也越来越受到重视.早期的研究主要集中在三角形网格的生成,但三角形网格的精度不高,在分析流体或受到震动时误差较大.于是出现了一些四边形单元生成方法,如三角形合并法、模板法、映射法、波前推进法、直接法等[1~5].铺路法[6]是由Ted D.Blacker 和Michael B.Step henson 两人提出的,这种方法生成的网格质量和灵活性要高于其他算法.作者研究了此方法后,将一排排生成单元改成一个个生成单元,这样相交处理就得到很大的简化,同时对光顺处理的算法作了一些改进,使处理后的网格更加均匀.最后给出了两个网格生成实例,验证了改进后方法的有效性.1算法原理1.1边界离散和节点分类1.1.1边界离散对边界离散时,外边界节点按逆时针顺序连接,内边界则按顺时针顺序连接,并且每条边界的节点数目必须为偶数.1.1.2节点分类为了阐述方便,先定义节点内角.节点内角是指节点N i与其所在边界上前一节点N i -1和后一节点N i +1所构成的夹角,方向为顺时针,不同类型的节点生成单元的方法也不同.根据节点的内角可以分成4种类型:①终止节点,α≤120°+δ;②边节点,120°+δ<α≤240°+δ;③角节点,240°+δ<α≤300°+δ;④转节点:α>300°+δ.其中,取5°<δ<10°.1.2网格单元的生成新节点的生成是以当前边界上N i -1,N i ,N i +1这3个节点为基础的.设节点N i 的内角为,d 1为节点N i -1到节点N i 的距离,d 2为节点N i 到N i +1的距离.1.2.1以边节点为基础的算法如图1,由N i -1、N i 、N i +1生成一个新节点N j ,同时这4个节点形成一个单元.矢量V 平分内角α,长度由下式定义V =d 1+d 22・sin (α/2(1图1边节点生成单元Fig.1Side node generate element1.2.2以角节点为基础的算法如图2,由N i-1、N i 、N i+1生成3个新节点N j 、N k 、N l ,同时形成2个单元.矢量V j 、V k 、V l 与N i-1N i 的夹角分别为α/3、α/2、2α/3,长度由下式定义V j=d 1+d 22・sin (α/3,V k=2V j ,V l=V j(21.2.3以转节点为基础的算法如图3,由N i-1、图2角节点生成单元Fig.2Corner node generate elementN i 、N i+1生成5个新节点N j 、N k 、N l 、N m 、N n ,同时形成3个单元.矢量V j 、V k 、V l 、V m 、V n 与N i-1N i 的夹角分别为α/4、3α/8、α/2、5α/8、3α/4,长度如下V j =d 1+d 22・sin (α/4,V k=2V j ,V l=V j ,V m=V k ,V n=V j(3图3转节点生成单元Fig.3R eversal node generate element1.3生成单元的特殊情况在生成单元时,有5种特殊情况需要考虑.这些特殊情况的共同点是所生成的新节点不在边界内部,这样便会有相交情况发生,但若将这几种情况单独考虑效果将会更好.如图4所示,N i N k 与原始几何边界相交.此时将节点N k 进行衰减处理,直至N i N k 不与边界相交为止,然后生成新单元,文中取衰减系数为0.5.图4重叠处理1Fig.4Overlap disposal 1如图5和图6所示,新生成的节点N k 不在浮动边界内部,此时不生成新节点,而是按照虚线所示生成单元.如图7和图8所示,此时是以第2个终止节点前的节点为基础生成新节点,按照图中虚线所示生成2个单元,之后要进行光顺处理和缝合检测.17第1期林胜良等:一种改进的高品质全四边形网格生成方法图5重叠处理2Fig.5Overlap disposal2图6重叠处理3 Fig.6Overlap disposal3图7重叠处理4Fig.7Overlap disposal 4图8重叠处理5Fig.8Overlap disposal 51.4光顺处理光顺处理是网格生成过程中最常用的操作,其目的是为了保证单元的尺寸和垂直度.光顺处理分为两步:首先,只对边界上的点进行处理,称之为边界光滑;其次,对边界附近的内部点进行处理,称之为内部光滑.1.4.1边界光滑V i 表示从原点到节点N i 的矢量.假定N i 与n 个单元相邻,V m j 、V m k 、V m l 分别表示从原点到第m 个单元中的节点N j 、N k 、N l 的矢量,这些节点为顺时针或者逆时针方向排序.V i ′表示从原点到光顺处理后N i 节点的矢量,则有V i ′=1n∑nm =1V m j+V ml -V mk (4如果节点N i 只与两个单元相邻,则应用式(5计算其位置变化.ΔB =V j -V i +(ΔA +V i -V j l Dl A(5图9对矢量V i j 的长度进行了修正.图10则对它的角度进行修正.向量P B 1平分P i-1和P i+1的夹角,向量P B 2平分P B 1和P i 的夹角.Q 点为N i-1、N i+1连线和P B 2的交点,记l Q 为N j 点到Q 点的距离,l D表示以N j 为基点按照式(1、(2或者(3计算的长度,则P B 2的长度定义如下:图9长度调整Fig.9Length adjustment图10角度调整Fig.10Angle adjustmentP B 2=l Q +l D2,l D >l Q 且α≤180°l D 其他(6角度修正后N i 点位置的变化量可由ΔC 给出ΔC =P B 2-P i(7对只与两个单元相邻的边界节点,其修正后最终位置的变化量由Δi 给出:Δi =ΔB +ΔC 2(8式(6中,在原铺路法的基础上加入了角度a 作为判断条件,其目的在于使生成的网格更加均匀.特别在内部边界为圆周,且向区域内部生成单元27江南大学学报(自然科学版第5卷时,可有效地避免单元被压缩的情况发生.1.4.2内部节点光滑边界光滑后即进行内部节点的光顺处理,采用最为典型的拉普拉斯修匀[7,8].P =14n ∑nm =1(P m j +P ml +2P m k =1s∑st =1P t (91.5相交处理在网格生成过程中,新形成的边界有可能会与它自己相交,也有可能与其它边界相交.文中采用的相交处理方法是将相交的边合并,见图11.图11相交处理Fig.11I ntersection disposal用铺砌法生成网格,必须保证边界的节点数为偶数,所以若新形成的边界节点数不为偶数时,则考虑与上一条或者下一条边合并,具体与哪一条合并应视两条边的距离和平行程度而定.由于本文是一个个单元生成,当发现新单元有相交情况发生时,立即进行相交处理,这样可使问题得到极大简化.2网格生成实例图12为生成的网格实例[9].网格生成时只需给出边界控制点及划分密度.图12网格生成实例Fig.12Example of mesh generation3结语在原铺路法的基础上作了改进,单元为一个个生成,边生成单元边进行相交判断,使相交处理得到简化;同时加入单元生成过程中重叠情况的处理,极大地提高了方法的适应性.另外,还改进了光顺处理算法,使生成的单元更均匀,给出的实例证明了网格单元的质量较高,有很好的应用价值.参考文献:[1]K Ho ΟLe.Finite element mesh generatio n methods :A review and classification [J ].C omputer Aided Design ,1988,20:27-38.[2]张建华,叶尚辉.有限元网格自动生成典型方法及发展方向[J ].计算机辅助设计与制造,1996,(2:28-31.[3]李华,李笑天,陈耿东,等.一种全四边形网格生成方法———改进模板法[J ].计算力学学报,2002,19(1:16-19.[4]Zhu J Z ,Zienkiewicz O C ,Hinton E ,et al.A new approach to the development of automatic quadrilateralmesh generation[J ].Int.J.for Numer.Meth in Eng ,1991,32:849-866.[5]Bruce P Johnston.Automatic conversion of triangular finite element meshes to quadrilateral elements[J ].I J NM E ,1991,31:67-84.[6]Ted D Blacker ,Michael B Stephenson.Paving :A new approach to automated quadrilateral mesh generation [J ].International Journal for Numerical Methods in Engineering ,1991,32:811-847.[7]罗特军,罗季军,汪榴.有限元网格优化方法[J ].四川联合大学学报:工程科学版,1999,3(3:65-72.[8]Herrman n L R .Laplacian Οisoparametric grid generationscheme[J ].J.Eng.Mech.Div.ASCE ,1976,102:749-756.[9]孙家广,杨长贵.计算机图形学[M ].北京:清华大学出版社,1998.(责任编辑:彭守敏37第1期林胜良等:一种改进的高品质全四边形网格生成方法。