三维约束 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为，贝V约束四面体网格生成（CDT由以下 几步构建。
（1）采用基于空外接圆（球）准则的 B-W增量插点算法， 对点集中点进行初始的 Delaunay 四面体网格生成。
（2）通过在丢失的边上插点恢复内中的边，更新。
（ 3）通过点的扰动或插入新点， 去除内的局部退化， 更新，。（ 4）
通过空腔重新生成四面体的方法，恢复内中的面，实 现面的恢复。
步骤（ 1）主要是构建，先寻找一个外接圆包含待插入点的 基单元，再利用单元相邻关系找到所有不符合外接圆准则的单元 （空腔），然后删除空腔内所有单元，连接待插入点和空腔边界 三角形，在空腔内形成新的三角化。经过边恢复（ 2）和局部退 化（3）后，保证了的CDT存在。步骤4可以在不增加点的前提 下实现面恢复。
（四）算法实现
算法代码在 Visual C++6.0 下编写，主体程序包括输入输出、 控制和网格划分三大部分，程序总体流程见图 1。在数据结构上 采用点―边―面―四面体―四面体网格的存在结构和链表的存 储方式来实现图元数据的存储， 用指针实现图元之间的联系。 同 时，程序为CDT算法提供了必要的数据交换接口， 将现有CAD软 件模型导入、 有限元网格数据生成及有限元软件分析功能综合在 一起，为工程应用搭建了平台。
三、应用实例
图2（a）为一个由3DMA）创建的机械部件模型，图 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 四面体算法是三维四面体网 格化的有效方案。
