深入理解数值计算网格(3)–非结构化网格生成算法

通常说的非结构网格主要指非四边形和六面体网格,包含三角形,四面体,楔形,金字塔等, 在实际应用中最常用的还是三角形和四面体。本文也主要介绍三角形和四面体的生成算法。

 

非结构化网格自动生成主要包含三种方法:

1.Delaunay method

(关于此方法的汉语翻译特别杂,不建议用中文翻译)

2.Advancing-Front method(波前法)

3.Spatial decomposition based method

(基于空间分解方法)

 

1.Delaunay method

生成三角形最常用的方法是Delaunay方法,也是所有网格生成算法中的最“基础方法”,在很多开源软件中都有其方法的实现。

Delaunay三角网格定义:平面上的点集P是一种三角剖分,使得P中没有点严格处于剖分后中任意一个三角形外接圆的内部。简单讲,给出一堆离散点,Delaunay网格是满足所有网格质量最好的网格。

Delaunay方法目前有很多改进方法,只介绍其中最基础的一种方法:逐点插入法

 

生成算法:

1.给出一堆离散点,初始化三角形链表

2.给出一个大三角形包含所有离散点

3.计算三角形链表中的每一个三角形的外接圆圆心和半径

4.如果点在已知三角形外接圆内,则把三角形的三条边加入到边数组中,在三角形链表中删除该三角形

5.删除所有重复的边,重复步骤3

6.用点和边数组中的每条边都组合成一个三角形,加入到三角形链表中,重复步骤2

微信图片_20221024225900

 Delaunay网格插入点UML活动图

 

作为基础的网格生成算法,Delaunay不仅支持二维,而且也支持三维。在三维计算中,只需将外接圆的判断改为外接球的判断即可。

 

2.Advancing-Front method(波前法)

Advancing-Front 方法又叫波前法,前沿推进法等。

其核心思想是沿着原始的网格边界生成网格,然后逐步推进生成,类似于波浪向未划分网格区域前进,直到所有区域被网格填满。

波前法思路清晰,尤其适用于已知边界的情况,其网格属性在生成过程中可以动态调整,控制性好,最终生成的网格质量也比较好,是生成非结构化网格的基础算法之一,同时Advancing-Front 方法的经过改进,也适用于四边形和六面体等结构化网格生成。

 

经典的波前法对二维从一组边开始,对三维从一组三角形面开始。以二维为例,网格生成策略一方面逐个单元逐个单元生成,创建插入新点和新单元,同时新的单元和之前的单元保持连通性。算法的一个关键点是如何插入新的点,新的单元需要满足网格尺寸和单元质量要求,波前法的一个优势是启发式(heuristic)算法,可以生成高质量,梯度可控的网格。相比其它算法,边界的完整性可以得到保证。其不足是在三维方法时,有可能出现不收敛的情况,即有些区域很难完全填充网格。

 

波前法的典型流程:

  1. 定义网格输入数据和参数,包括整几何区域,边界,网格尺寸,网格梯度

  2. 离散边界

  3. 从边界任意位置开始,逐步插入点,形成单元,迭代指导求解区域被网格填满

 

在这个过程中,如何插入点和形成单元是算法最核心的部分,其涉及到:

  1. 前进方向的单元选择

  2. 前进分析以及定义最优点需要考虑的各种可能性

  3. 单元构建有效性分析

  4. 选择合适的数据结构

 

相比较其它方法,波前法在三维实现上要远远高于二维。三维需要考虑更多的因素和特殊情况,同时在算法效率上,三维的要求也更高。

 

3.Spatial decomposition based method

(基于空间分解方法)

基于空间分解方法相对简单,主要用到空间树结构,即二维四叉树和三维八叉树。以平面四叉树为例:

  1. 根据几何对象,创建合适的树边界

  2. 根据对象点的分布,创建四叉树结构

  3. 在每个四叉树内部,利用四叉树的边和点,生成网格

  4. 调整网格,使其满足网格质量要求和梯度分布

     

 

一个典型的例子如下:

微信图片_20221024225910

对于使用四叉树和八叉树方法生成网格,两个核心点:

  1. 动态生成不平衡的树,即每个同级的树结点数目并不相同;

  2. 在树结点内部选择合适的算法生成初始网格

 

笔者在几何,图形,网格,求解器开发中,都较多的使用到了八叉树结构,八叉树结构可以说是一种基础性的数据结构和方法。

 

三种方法生成的网格比较:

微信图片_20221024225916

np为点的数目,ne为单元的数目,Qm为网格的质量,Qworst为最差的网格质量

微信图片_20221024225920

 

图片从上往下方法分别是:

四叉树,波前法,Delaunay     

图片皆来自于书 Mesh Generation (Application to Finite Elements),考虑到网格参数设置的差异,重点关注网格质量和分布

 

在实际应用中,三种方法并不是独立存在,经常会有方法混用的情况,比如在CFD网格中,不同区域采用不同的网格策略,可能效率和稳定性更好。

 

本文介绍了非结构化网格的三种常用方法,其中树结构方法和delaunay方法是比较常用的方法,作为研发人员,应该熟练掌握,最好能独立开发相关算法。

 

参考书目:

Mesh generation Application to Finite Elements

Finite element mesh generation

© 版权声明
THE END
喜欢就支持一下吧
点赞8635 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容