约束Delaunay四面体剖分

张娟

摘 要：文章研究了约束Delaunay四面体网格生成算法，引入了优化的网格算法，提高了四面体剖分单元的质量；重点研究了指定区域的边界边与边界面的一致性这两个Delaunay三角化算法迫切需要解决的关键性问题。结果表明，文章提出的约束Delaunay三角化算法适用性、效率及网格单元质量等方面都得到了提高，且该算法易于实现。

关键词：约束Delaunay三角化；网格算法；四面体剖分

有限元方法是一种解决复杂工程实际问题的有效手段，基于三维实体四面体剖分相对于二维领域的复杂性，Delaunay算法的研究成果还不够完善。目前Delaunay三角化方法仍具有算法速度慢、稳定性不良、适用范围有限、网格质量较差等和其他三维区域四面体剖分算法一样普遍存在的问题。

Delaunay准则是保证优化的网格结构的前提，由于目前现有的算法都无法较好地保证Delaunay准则，因此导致网格质量无法保证，造成狭长三角形单元的出现，致使误差超出范围，造成算法不稳定性。而需要解决的最关键的三维Delaunay三角化方法的问题就是指定区域的边界边、边界面的一致性问题。为了保证指定区域边界的一致性，保证边界边、边界面在Delaunay三角化中的存在性，必须要进行边界的恢复。

1 Delaunay四面体剖分的基本理论—边界一致

设Σ是一个三围区域W边界的离散化-曲面网格。边界一致的问题是要求生成一个符合Σ的四面体网格T，即Σ是一个由Γ元素组成的组合体。T中可以有额外的点（Steiner点），但是这种点的数目应该被限制得越少越好，这个问题对很多应用软件来说是最基本的。

在三维中，解决这个问题面临很多困难，有一些简单的多面体如果没有Steiner点（40个），就不能被四面体剖分。判定一个非凸多面体不存在Steiner点能否进行四面体剖分，是NP（NP-complete）问题，Chazelle认为对一个简单的多面体进行四面体剖分可能需要很多Steiner点。

目前已经提出了很多的边界一致的算法，这些方法都有一个共同特点。首先，建立对多面体P的顶点集的初始Delaunay四面体剖分；然后，多面体P的边界会被覆盖，通过修改这个四面体剖分實现边/面恢复，当需要的时候可以加入Steiner点，对于解决很多工程问题这个方法是有效的，但是它们不是对任意的输入都可行，对于一些反常的案例Steiner点的数目可能会很大。

约束Delaunay四面体剖分的特性的一个理论上的方法是通过往多面体P的边界里加入Steiner点，以丰富多面体P的顶点集V，直到丰富后的顶点集的边界被恢复。

对多面体P的约束Delaunay四面体剖分被定义为将P剖分成T，使得T是单纯复型且每个单一的T都满足约束Delaunay规则。按照这个定义，对P的约束Delaunay四面体剖分可能包含Steiner点，这些点包含在S＼V（P）中。

对曲面网格Σ进行“约束四面体剖分”被定义为对所有的单纯复形Σ的四面体剖分后的T也是单纯复形，这就意味着非Steiner点被加入到Σ，但也可能加入到区域Ω的内部。约束Delaunay四面体剖分的定义中，在Σ和Ω中允许存在Steiner点。在这个意义上，它也可以被称作是“半约束”四面体剖分。

一般来说，对P（Steiner点的不同选择）有多种约束Delaunay四面体剖分，我们完全有能力找到一个对P的约束Delaunay四面体剖分，使得它包含的Steiner点最少。

2 无约束Delaunay四面体剖分

Delaunay三角剖分是网格生成技术的研究重点，但是约束四面体剖分需要满足两个必要条件：（1）符合Delaunay准则；（2）满足点、线、面在网格中的存在性。这两个条件使Delaunay三角剖分变得很复杂，本文主要从算法研究解决这个问题。

本文是基于逐点插入法的三维Delaunay三角化方法，对三维空间进行四面体剖分。定义：（输入模型）输入模型Ω由3元组{V，S，F}构成，其中：

V（vertices） ={ vi }代表点的集合；

S（segment） ={ sj }代表约束线段的集合；

F（Facet） ={ fk }代表约束面的集合；

从输入模型Ω开始，对输入三维模型进行三角化需要以下几个步骤：

Stepl：生成一个包含输入模型Ω的初始四面体凸壳；

Step2：对输入的点集V进行初始Delaunay四面体剖分；

Step3：检测发生丢失约束线段并对其进行恢复；

Step4：检测发生丢失约束面并对其进行恢复；

Step5：网格细化及优化。

3 算法实现及开发平台

3.1 开发平台

本文涉及的数据结构和算法采用C#编程语言在Visual Studio.NET开发平台进行程序开发，实现约束Delaunay四面体剖分，并利用微软提供的Direct X 9.0控件显示三维网格剖分结果。微软 Direct X 控件是用于三维可视化的控件，与C#能够很好地集成，便于实现三维网格剖分与可视化。

3.2 实验数据说明

算法实现采用了微软.X 数据格式，这种数据的数据结构简单，便于在程序中处理。.X数据的头文件中说明了离散点、约束边、约束面的个数及其相关信息，同时文件中包含了离散点的坐标，约束边与约束面的顶点索引等信息。

3.3 实验结果分析

该算法已经通过C#编程实现，并在CPU主频为1.81 GHz的AMD Athlon（tm） 64 Processor 3000+处理器及512 MB内存的PC机，基于Windows XP操作系统进行测试，算法可处理空间散乱点，实现对空间离散点的Delaunay四面体剖分。有8个顶点的六面体以及一个约束面，经过Delaunay四面体剖分后的网格图，其中初始剖分生成的四面体个数为6个，插入约束面后的四面体个数为11个，共插入Steiner点2个（见图1）。