基于直角切割点调整的二维网格生成方法

于上

摘要：目前网格生成占用了流场计算的大量时间，为了进一步缩短网格生成的计算时间，该文在直角网格上直接进行快速的网格调整，针对多种边界情况进行了分类，保持了对复杂边界良好的适应性，同时在网格质量可以接受的范围内，可以在与网格单元数量成线性增长的时间复杂度下生成网格。最后以NACA0012翼型为例给出计算结果，验证了算法的有效性。

关键词：网格生成；直角网格；网格边界调整

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）22-0164-03

Abstract： Currently， mesh generation for CFD takes up considerable time of the whole calculation. To further reduce the time spent on mesh generation， a new method has been proposed to make adjustment quickly on Cartesian mesh for complex shapes. The mesh is adjusted according to different situations of mesh boundary， so it performs well on complex boundary. The quality of mesh will be in an acceptable range and the time complexity is linear to the number of grid cells. An example of generation on NACA0012 airfoil is given to confirm the effectiveness of the algorithm.

Key words： mesh generation； Cartesian mesh； mesh boundary adjustment

网格生成技术，是计算流体力学（CFD）的关键技术之一。网格生成的过程，把连续的计算区域划分成许多子区域，以便进行后续的计算。在目前的CFD计算周期中，网格生成占用了很大一部分时间，并且后续的计算精度和计算效率也很大程度上依赖于网格生成的质量和方法。

生成的网格从拓扑结构上分，主要分为结构化网格和非结构化网格。结构化网格数据结构简单，生成速度快。结构化网格在网格边界处通常使用适体坐标法[1]，但对于复杂外形的适应性比较差。非结构化网格对于复杂区域的适应性较强，但网格质量不好控制，计算效率相对结构化网格要低。现在非结构网格通常采用带约束的Delaunay三角剖分的方法[2]或四叉树方法[3]。针对不同网格的不同优点及缺点，混合网格应用的也越来越广泛[4]。

为了进一步提升网格生成的计算效率，本文所采用了一种在直角网格上调整顶点来适应边界的生成方法。这样做的优点是：与背景的结构化网格衔接时不需要做特殊处理；在边界附近对被切割的网格分情况讨论去调整网格，利用直角网格生成速度快的优势，避免了复杂度较高的Delaunay三角剖分。

本文的方法主要分为3个步骤，生成边界网格与计算交点，调整交点位置，生成最终网格，最后以NACA0012翼型为例，给出网格的生成结果。

1 光滑边界的网格生成

Wenjun Ying和Wei-Cheng Wang的方法[5]可以直接应用到光滑边界的网格生成中。在该方法中，所有边界与网格的交点都被称为控制点。与网格点距离近的称为主要控制点，与网格点距离远的称为次要控制点。

将结构网格上顶点 坐标移动到对应的主要控制点，就完成了网格的调整，如图1（b）的箭头方向所示。

然而这个方法并没有考虑到复杂外形边界上不光滑的尖点。所以本文在此基础上，针对尖点的边界附近的所有情况给出调整方案，把这个调整边界网格的方法推广到复杂的外形上。

2 尖点附近的网格生成

这里的“尖点”是指曲线在该点处，两侧的导数不相等。

2.1 尖点附近需要处理的问题

光滑邊界的外形所有的点附近都是平滑的，而尖点两侧曲线的切向不同，如果仅仅用交点去近似，会非常不准确。

假设网格足够密，使得外形在3*3的网格范围内最多只有1个尖点。又因为这个顶点两端的切向量不同，所以对于方形结构网格的每个顶点，最多有2条近似的直线与顶点周围的4条边产生交点。

针对2.1中的顶点以及图2的6种情况，将会在2.3分别给出调整的方案。在2.2中先给出了计算前的预处理步骤。

2.2 网格调整前的预处理

初始的网格是与背景网格相同的正方形网格，根据四个顶点在网格的内外的情况，划分出流场网格、物面网格和固体网格。计算区域在现有的物面网格的基础上，向外侧扩展2层，扩展后的物面网格的外侧顶点会自然地与背景网格衔接起来。之后计算外形与网格线的交点。

2.3 直角网格的调整方法

2.3.1 尖点的位置调整

对于外形上的尖点，穿过尖点的曲线两侧切向不同，不可能用一条直线近似。所以调整的方式是直接把距离最近的网格点移动到这个尖点处，如图3所示。

对网格调整后，最终的生成结果还需要去除内部的网格以及生成三角形网格两步工作。

2.4 去除内部的网格

如果外形没有凹角，4个点都不在外部即可判为内部网格。允许外形有凹角时，内部网格的判定分为如下几种：

第1种是4个顶点都不在外部，且有2个或2个以上是内部点，一定是内部网格。

第2种是1个顶点在内部，3个顶点在边界上的情况，此时如果网格的2条边在外部，说明部分在内部，应该保留3个边界点形成的三角形；如果网格3条边或4条边都在内部，说明网格是内部网格。

第3种是4个顶点都在边界上的情况。如果网格中心点在内部，说明是内部网格。

2.5 需要变成三角形的网格

需变为三角形的网格分为如下几种。

第1种是上文2.4的第2种情况中提到的，此时应将内部点去掉，留下其余3个顶点变成三角形网格。

第2种是有且只有1个顶点在外部，即其它3个顶点可能在内部或者边界上。此时要做判断，如果不是凹角附近的网格，则将这个外部点以及与它相邻的2个点构成的三角形，作为此处的网格，如图6（a）所示。

第3种是2个对角的顶点在外，另外2个对角的顶点在内。此时需要分成2个三角形。

后两种情况变成三角形网格之后，需要对网格连接的合法性重新检查，避免三角形网格穿过外形的内部，如图6（b）所示，顶点按照箭头方向调整过后，避免了右上的三角形穿过外形内部。

3 算法的分析

3.1 网格质量

在光滑边界的区域上，根据主要控制点的性质，2个主要控制点的距离最近为[22]倍背景网格边长。在尖点附近，如果四边形网格的4个顶点中包含有尖点，虽无法保证最短边的长度，但一个网格单元中的尖点只有一个，所以其它3条边的长度是大于[22]倍边长的。

如果三角形网格有一个顶点就是尖点，最小边的长度至少为[12]倍边长。所以这一方法在一定程度上保证了网格的质量。

3.2 网格数量

本文的方法每个正方形网格最多分成2个三角形网格。网格生成的总数量不超过原始网格的2倍。且本文的方法仅仅在外形的边界上至边界外2层的范围内进行计算，将需要计算的网格数量减少到最小。

3.3 时间复杂度分析

设边界附近的网格数量为n。

2.1至2.5中的所有操作都是依赖于网格数量的，并且都是O（n）的复杂度。但因为2.3～2.5的步骤中都需要进行分情况判断，可能复杂度的常系数比较高。

对比Delaunay三角剖分的方法，因为流场的内外边界有约束，所以这里需要用到约束的Delaunay三角剖分方法，时间复杂度最少为O（nlogn）。因此，只要n足够大，本文的方法就会比带约束的Delaunay三角剖分的方法快。

4 算法实例

5 结论

在二维复杂外形的边界生成网格时，本文的方法根据外形与网格边界的交点，分情况讨论，制定出一套网格调整的方案，时间复杂度低于通常使用的Delaunay三角剖分方法。虽然网格的质量达不到最优的，但因为交点的选取策略保证了网格点之间的距离，所以网格的质量通常不会很差。

本文方法的优势是在网格质量可以接受的限度内，用复杂度O（n）的算法快速生成网格。

该方法为复杂外形的网格生成带来了新的思路，今后还可以向在自适应加密以及三维网格的方向推广。

参考文献：

[1] 齐学义，杨帆，齐冲.贴体坐标网格生成技术的研究[J].工程热物理学报. 2001， 22（S1）：29-32.

[2] L.Paul Chew. Constrained delaunay triangulations [J]. Algorithmica. 1989， 4（1-4）：97-108.

[3] 楊名生，王冬.有限元网格全自动生成的四分法[J].计算结构力学及其应用， 1989， 06（04）：61-68.

[4] 张来平，张涵信，高树椿.矩形/非结构混合网格技术及在二维/三维复杂无粘流场数值模拟中的应用[J]. 空气动力学学报， 1998， 16（1）：79-88.

[5] W.-J. Ying， W.-C. Wang， A kernel-free boundary integral method for implicitly defined surfaces， Journal of Computational Physics 252 （2013） 606–624.

[6] 杨钦，刘瑞刚，孟宪海，等. 二维复杂限定Delaunay三角化算法[J].计算机辅助设计与图形学学报， 2007， 19（02）：145-150.