一种基于子域分解的表面混合网格生成方法

汪 攀 韩 磊 鞠传明 池宝涛 张见明

湖南大学汽车车身先进设计制造国家重点实验室，长沙,410082

一种基于子域分解的表面混合网格生成方法

汪 攀 韩 磊 鞠传明 池宝涛 张见明

湖南大学汽车车身先进设计制造国家重点实验室，长沙,410082

提出了一种新的基于子域分解的混合网格生成方法。该方法首先用映射法生成结构化背景网格，并确定实体表面上包含的小孔、键槽等小特征在背景网格中的位置，然后删除这些小特征覆盖的背景网格，并在这些区域内生成三角形网格，最后将剩余的背景网格和生成的三角形网格合并，得到整个目标域的网格。该算法综合了映射法效率高、网格质量好、四边形网格计算精度高，以及三角形网格几何适应能力强的优势。数值实验表明，针对复杂的实体表面，新方法能够全自动地生成质量较好的混合网格，生成的网格质量及算法效率均优于传统的推进波前法和铺砖法。

混合网格; 背景网格; 网格生成; 子域分解

0 引言

在求解各类工程和科学计算问题时，有限元法或边界元法[1-2]已成为最有效的数值分析方法，其中，网格的划分直接影响计算精度和计算效率。在表面网格剖分方法中，三角形网格的自动生成技术已经相当成熟，如Delaunay三角剖分算法[3-4]、前沿推进法(advancingfrontmethod,AFM)[5]等。在实际应用中，结构化的四边形网格在计算精度和计算效率上都优于三角形网格，但是相对于三角形网格的自动生成，四边形网格的自动生成算法不是很成熟。常见的四边形网格生成算法有映射法[6]、Q-Morph算法[7-8]、铺砖法[9-10]，这些算法往往比较复杂，效率低，或者生成的网格质量不好。

在机械产品中，有许多含有小孔、键槽等小特征的零部件，若忽略这些小特征，则有一部分零部件的实体表面可以用映射法或子域映射法生成质量非常好的结构化四边形网格，可是由于这些小特征的存在，无法用映射法生成结构化网格。为了解决这一问题，本文提出了一种新的基于子域分解的混合网格生成方法。该方法首先将复杂的目标域分解为多个简单的子域，然后在各个子域上进行网格剖分，最后将各个子域的网格数据进行组装，从而得到整个目标域的网格。对于带小孔、键槽等小特征的表面，可将目标域的网格分为两块，第一块是背景网格中删除小孔覆盖的区域后剩余的网格，这一部分区域不需要进行网格划分，取有效的背景网格即可；第二块是包含小特征的一个矩形空腔，这一部分区域相对狭小且无规则，对这一子块进行网格剖分的时候，可以选用健壮性较好的算法生成非结构化的三角形网格。本文生成的网格用于边界元软件开发的前处理过程，由于边界元法特殊的优势，面与面之间的网格可以不连续。

1 四边形质量因子

网格质量直接影响计算精度，本文采用几何准则对生成的网格质量进行评价。图1所示的四边形ABCD中，连接其对角线AC、BD，得到4个三角形△ABC、△ABD、△CDB、△CDA，先计算这4个三角形的质量因子，然后根据这4个质量因子，得到四边形ABCD的质量因子。

三角形的质量因子α就是三角形的面积与边长的平方和之比，即

α越大表示质量越好。令4个三角形△ABC、△ABD、△CDB、△CDA的质量因子依次为α1、α2、α3、α4，假设α1≥α2≥α3≥α4，则四边形ABCD的质量因子β为

2 算法原理

本文提出的算法是一种基于子域分解的网格生成方法，该方法将一个复杂实体表面分解为多个子域，然后在子域上进行网格划分，最后将子域网格合并，得到整个目标域的网格，其主要步骤如下:

(1)生成背景网格。以外边界为基础，用映射或子域映射法生成结构化的四边形网格。结构化网格有很多优点：网格生成的速度快，网格生成的质量高，数据结构简单，算法效率高。

(2)确定小孔的位置。点在背景网格中的位置用参数Ncol、Nrow表示，其中Ncol为列数，Nrow为行数。为了确定小孔的位置，首先离散小孔边界得到一系列的点，然后计算这些点对应的Ncol、Nrow，最后通过这些点在背景网格中的位置来确定小孔的位置。

(3)生成三角形网格。去除小孔覆盖的背景网格，得到一个空腔，将此空腔和空腔包含的小孔作为前沿，运用其他健壮性较强的网格生成算法(本文采用推进波前法)生成三角形网格。

(4)数据的组装。将有效的结构化四边形网格和非结构化三角形网格组装起来，得到整个目标域的网格数据。

3 算法实现过程

3.1 确定小孔在背景网格中的位置

小孔在背景网格中的位置由NcolL、NcolR、NrowD、NrowU4个参数确定，其中NcolL、NcolR表示矩形框的左右列数，NrowU、NrowD表示矩形框的上下行数。具体方法如下：首先将小孔的边界离散，得到一系列的点，在参数空间计算每一个点在背景网格中的位置Ncol、Nrow。在图2所示的背景网格中，假设点P在参数空间的坐标为(u,v)，第1行1列的点设为基准点，即图2所示的(u0,v0)，设U向离散段数为NU，V向离散段数为NV，则Ncol和Nrow可以通过下式计算：

Ncol=(u-u0)/(Umax-Umin)NU
Nrow=(v-v0)/(Vmax-Vmin)NV

图2 点在背景网格1中的位置Fig.2 The point location in background mesh 1

在图3所示的背景网格中，由于参数空间相邻的节点不是等距的，所以不能用图2中的方法求Ncol和Nrow。此时应按如下方法计算：假设背景网格总行数为N+1，总列数为M+1，标记背景网格中任意一个节点的坐标为(um,vn)，其中m表示列数，n表示行数，假定P点的坐标为(u,v)，首先确定P点所在的列，若P点在(um,v0)、(um+1,v0)、(um+1,vN)、(um,vN)所构成的矩形框内，则有Ncol=m，然后确定P点位于哪一行，若点P在(um,vn)、(um+1,vn)、(um+1,vn+1)、(um,vn+1)所构成的矩形框内，则有Nrow=n，此时点在背景网格中的位置坐标(Ncol,Nrow)为(m,n)。

图3 点在背景网格2中的位置Fig.3 The point location in background mesh 2

在实际操作中，可以根据需要适当扩大空腔，避免因空腔与小孔边界构成的区域过于狭长而导致生成的三角形网格质量不理想。

3.2 确定有效的背景网格

小孔覆盖的背景网格是无效的，这一部分的网格数据需要去除，如何快速定位这些无效的网格数据，将在很大程度上影响网格生成的效率。假设小孔在背景网格中的位置参数(NcolL、NcolR、NrowD、NrowU)已确定，则小孔覆盖的无效节点在存储节点的一维数组Node[·]中的位置可以通过下式计算：

for(i=NrowD+1；i

for(j=NcolL+1；j

Node[k]=NU*i+j

确定了无效节点后，通过结构化网格的拓扑关系搜索到与无效节点连接的边，标记这些搜索到的边为无效边，小孔覆盖的无效单元在存储单元的一维数组Cell[·]的位置可以用下式计算：

for(i=NrowD；i

for(j=NcolL；j

Cell[k]=(NU-1)*i+j

在背景网格中，去除这些无效的节点、边、单元之后，得到一个空腔。相对于整个目标域，此空腔相对狭小，在此狭小的空腔内，本文采用比较成熟且自适应能力较强的推进波前法生成非结构化的三角形网格。

3.3 得到前沿

用合适的尺寸对小孔进行离散，得到一系列的离散点，这一系列的点以及空腔的边界，即为新的前沿。将新的前沿加入到前沿链表中，作为推进波前法的初始前沿，在基于八叉树以及自适应尺寸场共同作用的尺寸控制方式下，可以生成质量良好且过渡均匀的非结构化三角形网格。由于每次输入推进波前法的空腔以及空腔内包含的小孔必须一一对应，因此，当实体表面上包含多个小孔时，应对其小孔进行循环。每次输入一个空腔以及其包含的小孔，若小孔所对应的空腔有重叠，会导致前沿相交，无法形成封闭的前沿，此时应对空腔进行特殊的处理，将重叠的空腔合并，得到一个连续封闭的环，并将其加入前沿链表。合并前后的空腔前沿如图4所示。

(a)合并前 (b)合并后图4 空腔前沿Fig.4 The front of cavities

3.4 边界处网格质量的改善

实际计算中，边界处的网格质量尤为重要，本文采用的推进波前法可以在边界处生成质量较好且过渡均匀的三角形网格，但是在同等条件下，其计算精度和效率还是低于质量较好的结构化四边形网格。为了改善小孔附近的网格质量，可以在小孔边界处以按层推进的方式铺设结构化四边形网格，推进的层数由小孔边界与空腔的最近距离决定。假设推进的层数为N，小孔边界与空腔的最近距离为Dmin，网格尺寸为ksize，则有N=Dmin/ksize-2，其中减2的几何意义是预留2层，使得这部分过渡区域能够用推进波前法生成质量相对较好的三角形网格。当铺设好的四边形网格边界与空腔边界较近时，即使自适应能力较强的推进波前法也无法生成质量较好的三角形网格。图5所示为小孔边界推进层数为2的网格划分。图6所示为小孔的边界与空腔边界距离较小，推进的层数为0的网格划分。

图5 边界推进层数为2的网格划分Fig.5 The mesh generation with the layer of 2 boundary advancing

图6 边界推进层数为0的网格划分Fig.6 The mesh generation with the layer of 0 boundary advancing

当出现小孔理想的离散尺寸远小于全局的网格尺寸的情况时，为满足计算精度，小孔附近的网格尺寸不宜过大；但由于网格连续性，会导致网格数目的增加。为了解决这个问题，本文引入了过渡单元，使小孔附近较小的网格尺寸保证了计算精度，且背景网格较大的网格尺寸减少了网格数目。网格划分如图7所示。

图7 添加过渡模块后的网格划分Fig.7 The mesh generation with transition template

综上所述，实现此算法的流程如下：

(1)用映射法或子域映射法生成结构化的四边形背景网格。

(2)确定每个小孔在背景网格中的位置，然后删除这些小孔覆盖的背景网格。

(3)根据小孔在背景网格中的位置，对小孔进行分组，将空腔重叠的小孔分为一组，并对其空腔进行合并操作，假设小孔分为N组。

(4)for(i=0;i

{

得到小孔对应的空腔的前沿；

离散小孔，得到实体边界的前沿；

根据实体边界前沿与空腔的距离，选取合成的推进层数，生成结构化四边形网格；

将上述前沿输入推进波前法生成三角形网格；

}

(5)将有效的背景网格和生成的三角形网格进行组装，得到整个目标域的网格数据，组装后的网格在三角形和四边形的交界处满足网格连续性。

4 算例

本文给出4个常见的机械零部件模型的混合网格划分实例，分别为带孔洞的垫片(图8a)、法兰盘(图8b)、阶梯轴(图8c)、带焊缝的钢架(图9)。

(a)垫片 (b)法兰盘

(c)阶梯轴图8 混合网格划分Fig.8 The hybrid meshe generation

图9 带焊缝的钢架的混合网格划分Fig.9 The hybrid mesh generation of steel frame with welds

由图8、图9可知，本文提出的新方法在实际应用中具有可行性，从网格分布来说大部分区域具有结构化四边形网格，少部分区域具有非结构化三角形网格。需要特别指出的是，对于带焊缝的钢架模型，由于系统误差或布尔操作等原因，使得CAD数据中存在着小短边、窄面和不光滑边界等常见人工特征[11]。这些特征使得生成的网格质量较差，甚至会导致网格划分失败(如用铺砖法生成四边形网格)。对经过拓扑修复后的钢架模型，用传统的推进波前法则对钢架进行网格划分，会生成43 576个节点、 73 786个单元；采用本文介绍的新方法，会生成36 518个节点、43 267个单元。由此可见，新方法较大幅度地减小了生成网格的规模。

为了进一步说明新方法的优越性，将法兰盘和阶梯轴中用新方法进行网格划分的实体表面分别用推进波前法和铺砖法进行网格划分，网格划分结果如图10、图11所示。对其生成的网格数量、质量及效率进行对比，结果如表1所示。

由表1可知，相对于推进波前法，新方法生成的网格数量减少了近1/2。对于法兰盘和阶梯轴，用新方法的耗时分别为推进波前法的1/5和1/3左右。相对于铺砖法，新方法较大程度地提高了生成网格的质量，且耗时分别为铺砖法的1/18和1/5。

(a)三角形网格 (b)四边形网格图10 法兰盘的网格划分Fig.10 The mesh generation of flange

(a)三角形网格 (b)四边形网格图11 阶梯轴的网格划分Fig.11 The mesh generation of stepped shaft

表1 网格数量、质量及三种方法效率的对比

5 结论

(1)本文提出的新方法生成的网格由绝大部分区域的结构化四边形网格和少数区域的三角形网格组成，整个目标域的网格质量较好。

(2)新方法充分利用了映射法算法简单、效率高、生成的网格好等优势，同时利用了推进波前法几何自适应能力强的优势。

(3)数值实验表明，本文提出的算法能够针对复杂实体的表面全自动地生成质量较好的混合网格，且算法效率较高。

[1]ZHANGJianming,QINXianyun,HANXu.ABoundaryFaceMethodforPotentialProblemsinThreeDimensions[J].InternationalJournalforNumericalMethodinEngineering, 2009, 80(3): 320-337.

[2]DONGYunqiao,ZHANGJianming,XIEGuizhong,etal.AGeneralAlgorithmfortheNumericalEvaluationofDomainIntegralsin3DBoundaryElementMethodforTransientHeatConduction[J].EngineeringAnalysiswithBoundaryElements, 2015, 51(3): 30-36.

[3]SUT,WANGW,LVZ,etal.RapidDelaunayTriangulationforRandomlyDistributedPointCloudDataUsingAdaptiveHilbertCurve[J].Computers&Graphics, 2015, 54(C):65-74.

[4]BEDREGALC,RIVARAMC.NewResultsonLEPP-delaunayAlgorithmforQualityTriangulations[J].ProcediaEngineering, 2015, 124:317-329.

[5] 覃先云. 边界面法的单元实现及其在复杂结构分析中的应用[D]. 长沙: 湖南大学, 2012.QINXianyun.AnElementImplementationoftheBoundaryFaceMethodandItsApplicationinAnalysisofComplexStructures[D].Changsha:HunanUniversity, 2012.

[6]RUIZ-GIRONSE,SARRATEJ.GenerationofStructuredMeshesinMultiplyConnectedSurfacesUsingSubmapping[J].AdvancesinEngineeringSoftware, 2010, 41(2):379-387.

[7] 李毅, 鲍劲松, 金烨,等. 二维域多约束四边形有限元网格生成算法[J]. 计算机辅助设计与图形学学报, 2008, 20(4):488-493.LIYi,BAOJinsong,JINYe,etal.QuadrilateralMeshGenerationAlgorithmforPlanarDomainwithMulti-constraints[J].JournalofComputer-AidedDesign&ComputerGraphics, 2008, 20(4):488-493.

[8]MERHOFD,GROSSR,TREMELU,etal.AnisotropicQuadrilateralMeshingGeneration:AnindirectApproach[J].EngineeringComputationalTechnology, 2007, 38(11/12): 860-867.

[9] 梅中义, 范玉青. 一种用于自动生成二维全四边形有限元网格的改进的铺设算法[J]. 计算机辅助设计与图形学学报, 2000，12 (6)：428-434.MEIZhongyi,FANYuqing.AModifiedPavingTechniqueforQuadrilateralMeshGenerationinPlanarRegions[J].JournalofComputer-AidedDesign&ComputerGraphics,2000,12(6):428-434.

[10] 郭新强. 边界面法四边形网格生成研究与应用[D]. 长沙: 湖南大学, 2011.GUOXinqiang.StudyonQuadrilateralMeshGenerationfortheBoundaryFaceMethodandTheirImplementation[D].Changsha:HunanUniversity, 2011.

[11]BEALMW,WALSHJ,SHEPHARDMS.AccessingCADGeometryforMeshGeneration[J].InternationalMeshingRoundtableSandiaNationalLaboratories, 2003:33-42.

(编辑 王旻玥)

A New Surface Hybrid Mesh Generation Method Based on Subdomain Decomposition

WANG Pan HAN Lei JU Chuanming CHI Baotao ZHANG Jianming

State Key Laboratory of Advanced Design and Manufacturing for Vehicle Body,Hunan University,Changsha，410082

A new hybrid mesh generation method was proposed based on subdomain decomposition. First, the structured background meshes were generated by mapping method and the locations of small features such as hole and keyway were determined. Then, the meshes which covered by small features were eliminated from background meshes, and unstructured triangular meshes were generated in this region. Finally, the meshes of target domain were obtained by combining the background meshes and the unstructured triangular meshes. It is capable of preserving the advantages of mapping’s high efficiency and high quality of the meshes, high computational accuracy of quadrangle meshes and the powerful geometric adaptive capacity of triangle meshes. Numerical experiments show that the proposed method may generate high quality hybrid meshes for complex surfaces automatically, the quality of resulting meshes and the algorithm efficiency are superior to traditional methods such as advancing front method and paving.

hybrid mesh; background mesh; mesh generation; subdomain decomposition

2016-07-11

国家自然科学基金资助项目(11472102)

TP391DOI：10.3969/j.issn.1004-132X.2017.06.008

汪 攀，男，1987年生。湖南大学汽车车身先进设计制造国家重点实验室博士研究生。主要研究方向为有限元网格划分技术。韩 磊，男，1988年生。湖南大学汽车车身先进设计制造国家重点实验室博士研究生。鞠传明，男，1991年生。湖南大学汽车车身先进设计制造国家重点实验室博士研究生。池宝涛，男，1991年生。湖南大学汽车车身先进设计制造国家重点实验室博士研究生。张见明(通信作者)，男，1965年生。湖南大学汽车车身先进设计制造国家重点实验室教授、博士研究生导师。E-mail:zhangjm@hnu.edu.cn。