三维约束Delaunay四面体网格生成算法及实现

【摘 要】三维四面体网格生成算法在有限元分析领域具有重要的应用价值，约束Delaunay四面体（CDT）算法是三维四面体网格化的有效方案。本文讨论了CDT关键概念，设计出三维域CDT算法，并基于此算法编制了网格生成程序，给出了工程实例的网格生成，获得了理想结果。

【关键词】网格生成；四面体网格；约束Delaunay四面体；算法

一、引言

网格生成是工程科学与计算科学相交叉的一个重要研究领域，是有限元前置处理的关键技术。从总体上讲，网格生成技术分为结构化网格和非结构化网格两大类，其中，非结构网格能适应复杂外形且自动性高，逐渐成为数值求解偏微分方程的有效方法之一，它在有限元分析、科学计算可视化、生物医学和机器人等学科领域具有重要的应用价值。

当前，典型的非结构四面体网格生成算法主要有八叉树法（Octree）、前沿推进法（AFT）和Delauay法等。较其它方法而言，Delauay法具有成熟的理论基础和判断准则，更适用于三维实体的网格生成。Delaunay法最早由Delaunay于1934年提出，在此基础上，Chew、Ruppert、Miller和等学者在算法改良方面开展了大量研究。目前，二维Delaunay法的研究已趋成熟，但三维Delaunay法在处理复杂实体的边界一致性问题仍是学者研究的热点。本文在前人研究的基础上，采用约束Delaunay四面体（Constrained Delaunay Tetrahedralization ，CDT）法来处理指定区域的边界一致性问题，编制了基于CDT的三维自适应四面体网格生成程序，并对工程实例进行了分析。

二、CDT定义及算法

（一）CDT定义

在三维区域的四面体网格生成中，四面体的外接球内部不包含任何网格顶点的四面体称为符合Delaunay准则的四面体，如果一个点集的四面体生成中每个四面体都符合Delaunay准则，则此四面体生成是点集的Delaunay四面体生成。在一定条件限定之下以Delaunay准则为标准将空间分解成许多四面体称为约束Delaunay四面体生成。通常情况下，将约束Delaunay三角（二维）/四面体（三维）生成的问题记为CDT。

（二）CDT存在性

由于三维空间存在不能划分为四面体集合的多面体（如多面体），故给定一个用分段线性复合体（piecewise linear complexes，PLCs）描述的三维区域，的CDT可能不存在。对于CDT算法，一个关键的问题就是要保证计算域的CDT存在。在实际应用中，假定为中的点的Delaunay四面体网格划分，为中的一个四面体，为的一个相邻的四面体（与共面），是和的点集。如果中所有的点都在同一个外接球内，就称为的局部退化[9]。如果D不包含局部退化，并且包含着中所有的线段，则的CDT存在。

（三）CDT算法

假定初始的PLC为，则约束四面体网格生成（CDT）由以下几步构建。

（1）采用基于空外接圆（球）准则的B-W增量插点算法，对点集中点进行初始的Delaunay四面体网格生成。

（2）通过在丢失的边上插点恢复内中的边，更新。

（3）通过点的扰动或插入新点，去除内的局部退化，更新，。

（4）通过空腔重新生成四面体的方法，恢复内中的面，实现面的恢复。

步骤（1）主要是构建，先寻找一个外接圆包含待插入点的基单元，再利用单元相邻关系找到所有不符合外接圆准则的单元（空腔），然后删除空腔内所有单元，连接待插入点和空腔边界三角形，在空腔内形成新的三角化。经过边恢复（2）和局部退化（3）后，保证了的CDT存在。步骤4可以在不增加点的前提下实现面恢复。

（四）算法实现

算法代码在Visual C++6.0下编写，主体程序包括输入输出、控制和网格划分三大部分，程序总体流程见图1。在数据结构上采用点—边—面—四面体—四面体网格的存在结构和链表的存储方式来实现图元数据的存储，用指针实现图元之间的联系。同时，程序为CDT算法提供了必要的数据交换接口，将现有CAD软件模型导入、有限元网格数据生成及有限元软件分析功能综合在一起，为工程应用搭建了平台。

三、应用实例

图2（a）为一个由3DMAX创建的机械部件模型，图2（b）、（c）、（d）给出了不同控制参数（、）下，应用本文算法生成的模型顶部网格生成截面放大图实例，表格1给出了、分别为（2.0，—）、（1.2，—）、（2.0，3.0）、（2.0，2.0）、（1.2，2.0）时对应的生成网格参数。其中，为外接球半径与四面体最短边长的比率，为四面体单元的最大体积限制，硬件平台为P4 2.6GHz、512M内存。

图2及表1表明：（1）该算法可以生成三维约束Delaunay四面体网格，生成网格的质量以及计算时间能够满足有限元计算的要求。（2）三维约束Delaunay四面体网格的质量要求越高，所需的剖分时间相对更长，可根据实际网格质量需求选择合适的生成控制参数进行网格生成。

四、结束语

本文基于Delaunay理论及准则，采用约束Delaunay四面体法处理三维计算区域的边界一致性问题，利用Visual C++6.0编制了基于CDT算法的三维约束四面体网格生成程序，并对工程实例进行了网格生成。结果表明，本文所研究的算法可以生成三维约束Delaunay四面体网格，生成的网格能够满足科学计算及工程分析的实际需要，约束Delaunay四面体算法是三维四面体网格化的有效方案。

参考文献：

[1]H-Si. Meshing Piecewise Linear Complexesby Constrained Delaunay Tetrahedralizations[A]. In：14th International Meshing Roundtable[C].（ 2005），P.147-161.

[2]J.R. Shewchuk. General-Dimensional Constrained Delaunay and Constrained Regular Triangulations.To appear in Discrete&Computational Geometry（2005）.

[3]J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of Algorithms（J）.Vol.18（1995），P.548–585

[4]G.L. Miller， T. Phillips， D. Sheehy. Linear-size meshes[C]. In：20th Canadian Conference on Computational Geometry（2008）

[5] E. die Zerlegung von Dreieckspolyedern in Tetraeder.Mathematische Annalen. 1928（98）：309～312.

[6]Si. Hang. An Analysis of Shewchuk's Delaunay Refinement Algorithm， in： Proc. 18th International Meshing（2009）

基金支持：云南省自然科學研究基金（基于时域有限元的谐振腔问题研究，2011）

作者简介：钟汝能（1979—），男，云南临沧人，讲师，主要从事电磁场数值计算研究。