任意多介质区域变尺寸

1、任意多介质区域变尺寸有限元网格自动剖分吴振君 施斌 祁长青(南京大学地球环境计算工程研究所 南京 210093)【摘 要】以Bowyer/Watson算法为基础，结合Lawson算法等对有限元网格进行Delaunay剖分，引入节点间距函数，在区域内通过布置约束点和边来控制特定位置网格的尺寸，并实现网格的尺寸均匀过渡。采用了多种优化技术对生成的网格进行优化。对Bowyer/Watson算法和Delaunay剖分的一些缺陷及问题作了探讨，并提出了相应的处理办法。编写的网格自动剖分软件具有良好的可视化界面，其图形生成、显示及修改功能十分完善，极大地提高了有限元网格剖分的效率和准确性。【关键词】有限元

2、，Delaunay三角剖分，逐点插入法，多介质 ，网格尺寸，网格质量，可视化 1 引言有限元法(FEM)广泛应用于土木建筑、岩土工程、地铁隧道、水利工程等各个领域中。网格剖分是有限元分析前处理的主要工作。对于大型的计算问题，有限元网格剖分是一项十分繁杂而艰苦的工作，这成为有限元技术应用的瓶颈。近年来，随着电子计算机及计算技术的飞速发展，网格自动剖分技术取得了卓有成效的进展。由于三角形有描述方便、处理简单等特性 ,适用于对复杂区域简化处理,因此三角形单元在有限元分析中广泛被采用 。三角形网格剖分目前以Delaunay剖分方法和推进波前法(Advancing Front Techniqu

3、e)最为流行1,2,3。作者采用Delaunay剖分方法，用VC+编制了可视化的有限元网格自动剖分软件，实现了对多介质、限制数据、变尺寸、多连通域的任意平面区域三角形网格自动剖分。2 Delaunay网格剖分的基本思想定义一：给定平面上的点集,令线段集合 ，在上定义图形，其中，是线段集合的最大子集且满足除端点外的任意两线段互不相交，则称为上的三角剖分。 定义二：给定平面上的点集，对每一个，定义一个区域，对任意点，有不等式,成立，则称为点集的氏图，其中表示与之间的欧氏距离。定义三：给定平面上的点集及其氏图，令线段集合，并且在氏图上的各自区域内具有共同的边界，则为集合的Delaunay三角剖分(其

4、关系如图1示)。                       研究证明,同氏图互为对偶图的Delaunay三角剖分图具有如下性质。(1)空外接圆性质。任何一个三角形的外接圆均不包含其它数据点(见图2)；(2)最小内角最大性质。在所有可能形成的三角剖分中, Delaunay三角剖分中三角形的最小内角之和是最大的。这两个特性保证了Delaunay三角剖分能够尽可能地避免生成小内角的长薄单元，使三角形能

5、够最接近等角或等边,这也是Delaunay三角剖分的算法依据。3 Delaunay三角剖分的逐点插入法Delaunay三角剖分的实现算法很多。Lawson提出了用逐点插入法实现Delaunay三角剖分的算法思想。Lee和Schachter, Bowyer, Watson, Sloan, Macedonio和 Pareschi,Floriani和Puppo,Tsai先后进行了发展和完善，本文是基于Bowyer/Watson算法实现网格剖分的，其基本思想是:在已有网格中，每次插入一个新节点,在网格中找出包含的三角形(图3a),然后从开始递归搜寻外接圆包含点的三角形，并删除这些三角形，形成一个多边形

6、(图3b阴影部分)，连接它的各个顶点和形成新的三角形(图3c)，这可以保证网格为Delaunay剖分。然后进行迭代，直至所有节点处理完。 4 网格自动剖分的实现(1)剖分区域处理。搜寻各个内、外边界及区域内的约束点、边(约束点是为控制网格尺寸而在区域内布置的点，两个约束点就构成了约束边)，生成网格剖分区域。定义介质信息及节点间距控制常数。剖分区域通过屏幕上鼠标绘图完成，参数以可视化方式输入和编辑。对于多种介质组成的区域,不同区域的边界线节点分别按逆时针方向编号。对于多连通域问题,外边界节点的编号为逆时针方向,内边界节点的编号为顺时针方向。这样使得计算区域处于边界线的左侧。区域内约束边若闭合，则

7、同外边界一样，按逆时针方向编号。(2)确定网格的最大包含区域，得到初始剖分三角形，这保证区域内所有的点都落在这个三角形内部。(3)节点间距函数。 确定剖分区域后，为了控制区域内网格的尺寸及蔬密过渡，文中引入了节点间距函数。区域边界点和内部约束各点的节点间距控制信息，通过线性插值可以得到边界和约束边上各点的间距常数。区域内部加入新点后该点的间距函数S如下。式中是该点的初始间距控制常数； 分别是三角形顶点的间距函数值；分别是节点和包含的三角形的顶点坐标。(4)初始剖分。插入边界及区域内约束边上的点，根据节点间距控制信息线性插值确定插入节点的位置。每加入一点，以Bowyer/Watson算法进行剖分

8、。把节点插入到剖分集合中去,形成标准的单连通凸域Delaunay剖分。(见图4)(5)对多介质区域的处理。各种介质的边界编号都是逆时针方向，按照(4)中方法分别对各种介质进行网格剖分，然后合并这些区域，生成统一的节点、单元编号。              (6)边界追踪。恢复区域原来边界，然后删除边界外的辅助三角形。(见图5)(7)网格单元质量判断。衡量网格的质量一般通过检查网格的每个三角形单元是否满足给定的尺度要求。常用的有：面积、边长、外接圆半径等。本文采用外接圆半径作为判断尺度。

9、设三角形外接圆半径为，三角形顶点的间距函数分别为,如果某三角形单元满足：<0.7*(),则三角形为可接受的。如果网格中所有三角形均为可接受的,则表示网格剖分结束。 (8)插入新节点以及插入点位置。外接圆半径较大,未达到要求的三角形是不可接受的。不可接受的三角形可以分为活跃的(active)和等待的(waiting),前者位于区域边界上或至少有一个邻接单元是可以接受的,后者的邻接单元都是不可接受的。本文在活跃三角形的边界或和可接受的三角形相邻边对应的Voronoi边上插入新节点。(选择活跃三角形中外接圆半径/内切圆半径比值最大者。)如图6所示，ABC是活跃三角形， O1 、O2分别是三角形

10、ABC和ACD外接圆圆心， AC是考虑的边，O1 、O2为对应的Voronoi边，M是AC的中点，P是要插入的新节点。根据节点间距函数S求得M点处的外接圆半径RM，令|AB|=，|MO1|=，显然APC的外接圆半径的表达式为： 由此可以计算点的位置。插入该点后，按(4)进行剖分。判断网格单元是否满足要求，若满足则网格剖分结束。                      

11、0;(9)网格松弛。所得网格，如果节点周围单元数大于7或者小于5，通过交换共边三角形对角线实现均匀分布。(10)平滑处理。可能会有退化的三角形存在，本文采用Laplacian smoothing10进行处理。在保证网格拓扑结构不变的情况下，移动非边界节点的坐标,使得网格形状更加合理。    其方法是：对于一个非边界上的节点,使其坐标等于该点周围相连节点坐标的平均值,其中,为与节点相连的节点个数, 是与相连的节点。(11)对生成的网格节点、单元重新编号，以节省有限元计算时的存储空间。(12)处理组成区域的各种介质的标识及边界条件。得到有限元计算所需网格。5 关于一些

12、问题(1) 舍入误差(round-off errors)对两个三角形有公共外接圆的情况，若采用Bowyer/Watson算法递归搜索插点多边形，由于浮点舍入误差，无法判断应删除那个三角形，选择不当将造成错误的剖分结果(见图7)。对这种情况有如下解决办法：一，采用Lawson的换边算法(edge-flips)避免这种无意义的剖分。虽然Lawson算法并不能完全解决这个问题，但几乎不会失效。二，还是用Bowyer/Watson算法，但是确定插点多边形时，从初始三角形开始以深度搜索算法搜索，可解决这个问题。三，检查要插入的点，如有问题，则挪动该点，然后再恢复，这种方法在三维情况下表现不佳。本文用到的

13、是第一种方法。(2) 区域内部插点区域内部插点位置是网格剖分中一个比较关键的问题。常用的插点方法有：一，在三角形的重心处，这种方法不必再搜索包含三角形，可以明显提高计算效率；二，在三角形外接圆圆心处，对于一般三角形，该方法可以使点分布更均匀；三，在Voronoi边上插点，即本文所用。实验表明三种方法都能得到令人满意的结果13，其中第三种方法效果最好。(3) 算法的复杂度Bowyer/Watson算法最差情况的时间复杂度为o(n2),但是对于非结构化的有限元网格，二维和三维情况下其算法时间复杂度基本上是线性的，即近似为o(n)11,12。而且，研究表明：算法的最坏情况对应着病态网格，随机选取插入

14、点顺序能很容易避免这种情况。6 可视化网格剖分软件基于如上方法，用VC+的MFC编写了网格自动剖分模块和基于文档视图的矢量图形处理模块，实现了可视化网格自动剖分。在该软件中，网格的边界节点、内部约束点可以用鼠标在计算机屏幕上输入，参数以交互对话方式输入和编辑。并可随时根据需要修改已建剖分区域,调用网格剖分模块对区域进行剖分，通过数据的动态更新，显示出网格的整个生成过程。7 有限元网格剖分实例利用该剖分技术可以为岩土工程等领域的有限元分析计算提供高质量的有限元网格。图8是一个堤坝问题的有限元网格剖分，区域由三种介质组成，组成坝体的混凝土及两层粘土。网格单元大都接近正三角形。在不同介质交界处，网格划分得比较细密。由于坝体内部的应力应变不是计算分析的重点，网格适当做了稀疏处理。最下面的粘土层受影响很小，网格也比较稀疏，并从上至下由细密向稀疏过渡。图9是洞室开挖问题的有限元网格剖分。洞室附近因开挖导致应力应变变化很大，是分析的重点位置，所以网格剖分得细密；剖分区域的边界受洞室开挖影响甚微，网格可以划分得稀疏一些，以减少有限元分析的运算。8 结论以Bowyer/Watson为基础，结合Lawson算法等进行Delaunay三角网格剖分。引入节点间