面向高端复杂装备模型的并行网格剖分算法综述

2018-12-25赵宝臣朱晨澍郜超超

数字技术与应用 2018年3期

赵宝臣朱晨澍郜超超

(1.河北工业大学理学院,天津 300400;2.河北工业大学计算机与软件学院,天津 300400)

1 研究背景

随着科技的发展,在机械工程领域中所应用的装备更加复杂,传统的对这些装备的力学静、动态分析的软件CAE运行时间过长,精度无法满足需求,这直接影响了工业生产的要求。有限元法是常用的方法,而网格剖分是应用有限元法的前提。因此,研究如何快速精准复杂连续体剖分成微小的网格单元,并且在单元上快速求解近似变分方程具有重要意义。

对于该问题的研究国内外已经有了初步的成果,网格生成更多的使用Delaunay网格,以及通过简化模型来提高结构分析效率。复杂装备设计的精度和速度问题的解决是多学科团队积极协作的结果,现有研究已从网格剖分、并行算法优化等角度,证明多学科技术的融合有利于提升结构快速分析的可靠性,提升复杂装备设计的效率。

2 研究内容

2.1 网格分类

结构化网格、非结构化网格、混合网格和特殊网格是目前网格的四个主要类别。结构化网格生成速度快、质量好、数据结构简单,但适用范围窄,有适体坐标法、块结构化网格等生成方法;非结构化网格多用于复杂流体机械物理模型的网格生成,此网格有利于使用自适应技术,提高计算精度。但有两个缺点:一是网格填充效率不高,二不能很好地处理粘性问题,生成该网格有Delaunay三角剖分、阵面推进法等方法;混合网格糅合了结构化和非结构化网格的优点,剖分灵活、易于实现网格自适应等;特殊的网格用于处理一些复杂的问题,能得到高质量高精度的网格,通过曲面网格、自适应网格等生成技术可以实现。

2.2 网格划分算法

2.2.1 实际模型提取

网格划分是实体模型做网格划分的前提和基础,进行曲面网格划分的第一步就是对实体信息的提取。Open CASCADE (OCC)是常使用的平台,该软件提供的数据交换功能,可以直接从实体模型中读取网格划分所需要的数据,并使将不同数据存储格式传统一化,便于后期读取与处理。

2.2.2 Delaunay三角剖分

由俄国数学家M.G. Voronoi提出的Voronoi图,由平面区域中连接两邻点的线段的中垂线所形成的区域,实际上就是一种三角剖分。

在许多领域中,Delaunay三角剖分做出的网格相比较其他三角剖分具有很好的数学性质,因而被普遍的使用。在完成一般的三角剖分之后,二维上依照圆准则、最小内角最大准则、Thiessen区域准则等判据,三维上依据空球准则、最小立体角最大化优化准则等准则,通过翻转等方法可以对其Delaunay化。但是在翻转操作中有两种特殊情况,一种是退化情况,一种是不可翻转情况,此时需要进行修复。其中翻转有:2-2翻转、1-3翻转、3-1翻转、2-3翻转、3-2翻转、4-1翻转、4-4翻转等。生成网格的同时,难免会有畸形网格出现,常用的改进网格质量的方法主要有两类:Laplace光顺方法和Delaunay细化算法。

2.2.3 三角剖分算法

以三角形网格的构建过程的为依据将算法分为生长法,逐点插入法,和分治算法。

生长法在第三点的寻找上花费时间最大,因此,相应的实现算法差别主要表现在“第三点”的搜寻策略上。

逐点插入法中的各种算法的区别在于初始多边形构建所采用的方法,如何搜索定位三角形和三角形重构的方法。

分治算法的各种实现算法的不同在于点集划分的标准,子三角网生成采用的算法以及各子三角网合并的方法。

由于生长法需要在搜索第三点上消耗很长的时间,现在已经很少使用。逐点插入算法和分治算法是现在流行的两类算法,前者实现难度较小,所需内存较小,但相比较分治算法,时间复杂度较高。由于大量的递归调用是分治算法的一个较为明显的特点,因此会占用较大内存空间,对大数据集剖分时要求较高。有学者给出了合成算法,在分治算法中糅合了逐点插入算法,集中体现了两种不同的算法的优势。

2.2.4 并行化

目前的并行模式主要有三种:

适用于内存共享的多线程编程模型:如OpenMP并行模式、GPU并行模式;

适用于分布内存的消息传递编程模型:如常用的PVM和MPI;

混合编程模型:如许彦芹等人首次提出了一种基于SMP集群的MPI+CUDA并行模式,刘青昆等人提出来的基于OpenMP, MPI,CUDA混合并行编程模型。

并行算法设计是算法理论和计算机并行体系相结合的结果,并行网格生成的两种主流方法为数据并行和任务并行。数据并行是将数据域划分为有限个区域,并将每个区域映射到一个相应的处理器上,调用算法生成有限个网格;任务并行是在不同粒度层级上将算法运行所需要的时间和运行环境并行化,再利用并行开发工具设计新算法来完成并行网格的生成。前者反复使用已有的网格生成算法,实现较为容易,因此成为并行网格生成算法研究和开发的主流。对于并行网格生成算法的优劣性,Chrisochoides给出了三个评价标准:稳定性,复用性,可扩展性。基于任务并行的并行Delaunay方法主要是构建在并行Bowyer-Watson内核之上;基于数据并行模式的并行Delaunay方法有基于分割平面的并行,基于PDT理论的并行,基于稀疏网格的并行等方法,它们的主要区别是其所采用的数据分解方式不同。

2.2.5 修复

边界边、边界面是否一致是网格生成后依然会存在的问题,网格生成过程中不可避免的会有Sliver单元出现,如何消除是另外一个重要的问题。保证剖分前后的模型边界一致是一个准确的算法应该具有的结果。然而,因为仅仅考虑了点与点之间的连接状况,Delaunay剖分算法无法解决边界边与边界面的存在问题,只能确保该点在三角化中依然存在。恢复算法主要有三种:CDA、ADA和CDT。由于选取Delaunay算法生成的网格中一定会存在一些Sliver单元,影响网格质量,因此消除Sliver单元是网格生成中无法回避的问题。国内外专家提出了多种消除方法,主要分为两种方法:优化消除Sliver单元以及运用Chew加密算法、Cheng加密算法、Li加密算法等三种算法进行加密来消除Sliver单元。