基于带约束前沿推进的四边形网格生成方法*

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

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

基于带约束前沿推进的四边形网格生成方法*

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

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

针对当前各种Q-Morph算法在生成四边形网格的过程中容易产生残余三角形这一缺陷，提出了一种带约束的前沿推进算法.该方法是一种基于前沿推进思想的Q-Morph算法，由当前前沿生成两条侧边和一条顶边，并删除其内部的三角形，从而将三角形网格合并生成一个四边形网格，并在前沿推进的过程中加入了约束条件，从而可以有效地避免残余三角形的产生，提高了算法的效率和最终生成网格的质量.数值实验表明，该算法能够全自动生成质量较好的四边形网格.

网格生成；四边形网格；Q-Morph；前沿推进

在求解各类工程和科学计算问题上，有限元法或边界元法[1-2]已成为最有效的数值分析方法之一，网格划分是数值分析前处理的重要部分，已成为当前有限元或边界研究的重要领域.四边形网格既可以直接用于壳分析，也可用于六面体网格的输入，而且四边形网格在计算精度、计算效率等方面均优于三角形网格，因此研究四边形网格生成算法很有必要.四边形网格生成算法分为间接法和直接法.其中直接法包括映射法、子域映射法[3-4]和铺砖法[5-6]等，这些算法往往比较复杂或自适应性较差.为了减少四边形网格生成的难度，通常采用间接法[7-8].Lee等提出的Q-Morph算法[9]是典型的间接法，间接法即先生成三角形网格，再将三角形网格转化为四边形网格，常见的转化技巧有2种：分解法，将1个三角形分解为3个四边形；合并法，将两个相邻的三角形合并生成1个四边形[10].合并法在合并操作时会考虑生成四边形网格的质量，因此其生成的初始网格要优于分解算法.合并算法最大的难题在于最后会留下很多残余三角形，阻碍了全四边形网格的生成，此时常见的解决办法是用分解算法，将残余三角形分解为3个四边形，再通过拉普拉斯优化进行局部光顺处理，但是处理过多的残余三角形，不仅耗时较多，算法效率较低，也会影响最终生成网格的质量.为了减少残余三角形的数量，Lo[11]尝试设置一些探索性规则来确定三角形网格的合并顺序；胡向红等[10]在三角形合并的过程中加入了约束条件，从而避免了残余三角形的产生，但是该算法生成的网格质量较差.基于前沿推进的思想，Owen等提出了改进的Q-Morph算法[12-13]，该算法改进Lee等提出算法中存在较多不规则点的缺陷，目前这一算法得到广泛的使用，并已集成到大型的商用有限元软件中.该方法可以生成质量较好的四边形网格，但是在合并的过程中也容易产生残余三角形.

针对上述算法的不足，本文提出了一种基于带约束前沿推进的四边形网格生成方法，该方法以Owen提出的Q-Morph算法为基础，以保证在前沿推进的过程中，生成的四边形质量较好，并且在合并操作的过程中加入了约束条件，以保证前沿推进的过程中不会产生残余三角形，该算法能够自动高效地生成质量较好的四边形网格.

1 算法流程

本文提出的算法是一种间接的四边形网格生成方法.先利用推动波前法生成三角形网格，然后基于Q-Morph算法以及前沿推进的思想，将三角形的外边界作为初始前沿，从外向里推进，将三角形网格合并生成四边形网格，其主要步骤如下，流程图如图1所示.

1)用推动波前法生成初始三角形网格；

2)取三角形网格的外边界，将其加入前沿链表，作为初始前沿；

3)从链表中选取一条前沿作为当前前沿，将其作为当前四边形的底边；

4)在底边的两个端点处生成两条侧边，侧边可以是已经存在的边，也可以是通过对角交换获取的边；

5)通过交换对角线操作获取顶边；

6)将底边、侧边、顶边生成一个四边形，并删除里面包含的三角形；

7)通过局部优化改善四边形网格的质量和周围三角形网格的质量；

8)更新前沿.

图1 算法流程示意图Fig.1 Flow chart of algorithm

2 算法实现

基于前沿推进的Q-Morph算法主要包括：生成侧边、生成顶边、删除四边形内的三角形和局部光顺等几个主要的步骤(如图2所示).

图2 四边形网格生成过程Fig.2 Theprocess of quadrilateral mesh generation

2.1 侧边的生成

下面介绍以AB为前沿边，生成侧边AD和BC，步骤如下：

1)确定当前前沿和相邻前沿的角平分线，如图3(a)所示的虚线；

2)计算与前沿结点相连的边与角平分的夹角，如图3(a)所示的α1，α2，并取其中的最小值α=min(α1,α2)；

3)根据α确定侧边的生成方式，如果α≤ε(本文中ε取π/6)则直接以α对应的边作为侧边，如图3(b)所示的BC.否则，采取交换对角线的方式获取侧边，如图3(d)所示的AD.

从侧边的生成过程可以看出，该方式生成的网格质量相比传统的直接删除一条公共边生成的四边形网格质量要好.当α较小时，直接取该边做侧边，当α较大时，则必然存在分居角平分线两侧的边，此时通过交换对角线得到的新边，则必然与角平分线的夹角较小，即适合做侧边，因此，此方法总能找到一条合适的侧边.

图3 侧边的生成过程Fig.3 The generation of side edge

2.2 顶边的生成

在以AB为前沿边，生成侧边AD和BC以后，连接CD，CD即为顶边，但是很可能CD并不是三角形中已经存在的边，此时需要通过交换对角线，恢复边CD.对于任意的三角网，理论可以证明，可以通过有限次对角线交换恢复给定的任意一条边，具体步骤如下：

1)连接CD，得到所有与CD相交的三角形.如图4所示的T0,T1,T2,T3；

2)由C点开始，依次交换T0,T1,T2,T3的对角线，交换对角线时，如果相邻两个三角形构成的四边形是凹四边形，则将对角线交换的过程延后至下一次循环中进行；

3)当出现CD边时，循环终止，即得到了顶边CD，否则进入步骤2).直至恢复了顶边CD.

图4 交换对角线得到顶边Fig.4 Gettop edge by exchanging diagonal

2.3 删除内部三角形

生成四边形ABCD以后，需删除四边形内部的三角形，本文删除内部三角形的方法也是基于前沿推进的思想提出来的，具体步骤如下(如图5所示)：

1)将四边形内部的三角形加入前沿链表中；

2)以当前前沿为基础，搜索与其相邻的三角形，删除该三角形，并判断该三角形另外两条边，若该边为前沿边，则将其从前沿链表中删除，否则将其加入前沿链表；

3)当前沿链表为空时，该过程结束，否则进入步骤2)，直至前沿链表为空.

图5 删除四边形内部的三角形Fig.5 Deletethe internal triangle

2.4 约束条件

Owen提出的Q-Morph算法[13]是以前沿推进的方式生成四边形，但是在前沿推进的过程中，无法保证待合并的三角形区域是一个单连通域，也就是说三角形区域可能被前沿分割成几个相互独立的区域，这就大大增加了产生残余三角形的概率.为了解决此问题，可以在前沿推进的过程中加入约束条件，以确保待合并的三角形始终是单连通域，从而避免了残余三角形的产生.首先引入几个定义.前沿边：位于四边形区域与三角形区域分界线上的边.前沿结点：位于前沿边上的结点.在以当前前沿(如图6所示的AB)生成四边形单元的过程中，可能出现的所有情况如图6所示.

图6 前沿推进过程中可能出现的10种情况Fig.6 Ten casespossible to occur in the process of advancing front

从图6中可以看出，在(a)，(d)，(f)，(i)和(j)所示的情形下，三角形区域在前沿AB生成四边形以后仍然是一个单连通区域，此时可以以AB为前沿生成四边形ABCD，除此之外，在生成四边形ABCD后，前沿会将三角形区域分割成多个块，从而可能会导致残余三角形的形成，此时不能以AB为前沿生成四边形ABCD.用nFrontNode表示ABCD中前沿结点的个数，nFrontEdge表示ABCD中前沿边的个数，则前沿推进的约束条件可以归纳如下：

1)nFrontNode=2；

2)nFrontNode=3，nFrontEdge=2；

3)nFrontNode=4，nFrontEdge>2.

因此，只有满足这三个条件之一，才可以生成四边形.此外，除了上述10种情况以外，还有一种特殊情况，如图7所示.

图7 前沿推进过程中的特殊处理Fig.7 Special handling in the process of advancing front

在常规的前沿推进的过程中，若出现如图8(a)所示的情形时(粗线段为前沿)，以AB为前沿，在形成侧边时(如图8(b)所示)，若α1满足要求，则BD是一条侧边，生成的如图8(b)所示的四边形ABDE，更新前沿后会产生如图8(c)所示的残余三角形BCD.若在前沿推进的过程中，加入上述约束条件，则可以避免残余三角形的产生，因为生成图8(b)所示的四边形ABDE时，nFrontNode=4，nFrontEdge=2，不满足约束条件，此时不能生成四边形，然后循环前沿链表中的下一前沿BC，对于可能生成的四边形BCDE(如图9(a)所示)，nFrontNode=4，nFrontEdge=3，满足约束条件，则可生成四边形单元，更新前沿后如图9(c)所示，同理，再以EF为前沿时生成四边形EFAB，更新前沿后如图9(d)所示，显而易见，经过了带约束的前沿推进操作，生成了四边形ABCD和EFAB后，三角形区域仍是一个单连通域，没有残余三角形的产生.从图9可以看出，带约束条件的前沿推进不会产生残余三角形，从而避免了处理残余三角形这一复杂程序带来的时间消耗，以保证生产高质量的全四边形网格，提高了算法效率和网格质量.

(a)AB为当前前沿 (b)AB前沿生成四边形 (c)前沿更新图8 常规的前沿推进Fig.8 General front advancing process

(a)初始前沿 (b)BC前沿生成四边形 (c)BE前沿生成四边形 (d)前沿更新图9 带约束条件的前沿推进Fig.9 Front advancing process with constraint condition

3 数值算例

本文采用几何准则对生成的网格质量进行评价.如图10所示的四边形ABCD，连接其对角线AC，BD，得到ABC，ABD，CDB，CDA等4个三角形，先计算这4个三角形的质量因子，然后根据这4个三角形的质量因子，得到四边形ABCD的质量因子.

图10 四边形网格的质量因子Fig.10 Quality factor of quadrilateral mesh

其中三角形的质量因子α[9]定义如下：

α的意义就是三角形的面积与边长的平方和之比，0<α≤1，α越大表示质量越好.令4个三角形△ABC，△ABD，△CDB，△CDA的α因子依次为α1，α2，α3，α4，假设α1≥α2≥α3≥α4，则四边形ABCD的质量因子β[14]定义如下：

其中0<β≤1，β越大表示网格质量越好.

为了说明本文提出算法的优越性，下面给出一个带小孔的平板的算例(因为对称性，在分析时取其1/4即可).并和Owen的算法[13]以及胡向红等人的算法[10]进行对比，如图11所示.

(a)Owen的算法[13] (b)胡向红等人的算法[10] (c)本文的算法图11 3种方法的网格划分示意图Fig.11 Quadrilateral mesh generated by three different methods

从图11和表1中可以看出：Owen的算法[13]生成的四边形网格质量较好，但是有残余三角形的存在.胡向红等人的算法[10]生成的网格没有残余三角形，但是网格质量较差.本文提出的算法可以有效地解决上述两种算法的不足，生成高质量的全四边形网格.下面给出一个复杂多连通域实体的表面网格划分(如图12所示).

表1 网格质量数据Tab.1 Quality data for meshes

图12 复杂实体的网格划分Fig.12 Quadrilateral mesh generation for complex solid

从图12中可以看出，对于复杂的多连通域,本文的算法也可以生成高质量的四边形网格,从而进一步说明该算法的可行性.

4 结 论

本文提出的算法是一种间接的四边形网格生成方法，该方法基于前沿推进的思想，在单个前沿推进的过程中，取合适侧边和顶边，控制当前前沿生成的网格质量，并在推进的过程中加入约束条件，避免了残余三角形的产生，数值算例表明该算法能够生成质量较好的四边形网格.相对于常规的前沿推进算法，本文方法可以有效避免残余三角形的产生，提高了算法的效率和网格生成的质量.相对于胡向红的区域生长算法[10]，本文方法可以有效控制当前四边形的质量，从而使最终生成的网格质量有显著的提高.

[1] ZHANG Jianming，QIN Xianyun，HAN Xu.A boundary face method for potential problems in three dimensions[J].International Journal for Numerical Method in Engineering，2009，80(3)：320-337.

[2] 张见明，李湘贺，陆陈俊，等.多域边界面法在稳态热传导问题中的应用[J].湖南大学学报：自然科学版，2014，41(5)：58-64.

ZHANG Jianming，LI Xianghe，LU Chenjun，etal.Application of multi-domain boundary face method in steady state heat conduction[J].Journal of Hunan University：Natural Sciences，2014，41(5)：58-64.(In Chinese)

[4] MUKHERJEE N.An art gallery approach to submap meshing[J].Procedia Engineering，2014，82(82)：313-324.

[5] BLACKER T D，STEPHENSON M B.Paving：a new appro-ach to automated quadrilateral mesh generation[J].International Journal for Numerical Methods in Engineering，1991，32(4)：811-847.

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

MEI Zhongyi，FAN Yuqing.A modified paving technique for quadrilateral mesh generation in planar regions[J].Journal of Computer-Aided Design & Computer Graphics，2000，12(6)：428-434.(In Chinese)

[7] PELLENARD B，ORBAY G，CHEN J，etal.QMCF：QMorph cross field-driven quad-dominant meshing algorithm[J].Procedia Engineering，2014，82：338-350.

[8] MERHOF D，GROSS R，TREMEL U，etal.Anisotropic quadrilateral meshing generation：anindirect approach[J].Engineering Computational Technology，2007，38(11/12)：860-867.

[9] LEE C K，LO S H.A new scheme for the generation of a graded quadrilateral mesh[J].Computers & Structures，1994，52(5)：847-857.

[10]胡向红，陈康宁.由区域生长算法实现四边形网格划分[J].计算机辅助设计与图形学学报，2004，16(1)：29-34.

HU Xianghong，CHEN kangning.Generating quadrilateral meshes by using region growth algorithm[J].Journal of Computer Aided Design & Computer Graphics，2004，16(1)：29-34.(In Chinese)

[11]LO S H.Generating quadrilateral elements on plane and over curved surfaces[J].Computers & Structures，1989，31(3)：421-426.

[12]OWEN S J，STATEN M L，CANANN S A，etal.Q-Morph：an indirect approach to advancing front quad meshing[J].International Journal for Numerical Methods in Engineering，1999，44(9)：1317-1340.

[13]OWEN S J，STATEN M L，CANANN S A.Advancing front quadrilateral meshing using triangle transformations[C]//Proceedings of the 9th International Meshing Roundtable.New Orleans，2000：409-428.

[14]PARK C，NOH J S，JANG I S，etal.A new automated scheme of quadrilateral mesh generation for randomly distributed line constraints[J].Computer-Aided Design，2007，39(4)：258-267.

An Advancing Front Quadrilateral Mesh Generation Method with Constraint

WANG Pan，ZHANG Jianming†，HAN Lei，JU Chuanming，CHI Baotao

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

In view of the limitation of the current various Q-Morph algorithms that can generate isolated triangles in the process of generating quadrilateral mesh，a new advancing front method with constraint was proposed.The method is a kind of Q-Morph algorithm based on advancing front.First，the two side edges and one top edge are generated according to the current front.Then the triangles in the quadrangle are eliminated from the triangular domain.Finally a quadrilateral mesh is generated.Moreover，some constraining conditions are imposed on the advancing procedure to avoid generating isolated triangles，which can improve algorithm efficiency and mesh quality.Numerical experiments are presented to demonstrate that the new method could generate high-quality quadrilateral meshes for complex surface automatically.

mesh generation；quadrilateral mesh；Q-Morph；advancing front

1674-2474(2017)08-0029-06

10.16339/j.cnki.hdxbzkb.2017.08.005

2016-12-11

国家自然科学基金资助项目(11472102),National Natural Science Foundation of China(11472102)

汪攀(1987—)，男，湖北汉川人，湖南大学博士研究生

†通讯联系人，E-mail: zhangjm@hnu.edu.cn

TP391

A