图2.1 常见的网格生成算法
有限八叉树法的基本流程包括:叉树的构建、平衡，过滤交点，内部栅格与边界栅格的网格剖分相容，优化网格等。其中，内部栅格与边界栅格的网格剖分相容在实现上有一定难度。为此，Yerry等人提出先将内部栅格分割成6个锥体，再将其划分成要求的网格单元，但是这样生成的网格单元质量差并且单元数量也太多。Schroeder等人将该方法与Delaunay方法结合，从而解决了内部栅格与边界栅格的网格剖分相容的问题，降低了算法实现的复杂程度，而且提高了边界处的网格单元的质量。有限八叉树法与推进波前法AFT和Delaunay三角化方法相比较，其在三角形/四面体网格生成方面并不占优势，因此不把它作为研究重点。
（2）推进波前法
近年来，推进波前法[5]（Advancing Front Technique，简称AFT）也成为目前最流行通用的全自动生成非结构化有限元网格的方法之一。AFT法最早是由Rainald Lohner和S.H.Lo提出的，该方法不像Delaunay三角化方法具有可靠的数学理论依据，很多时候都是靠实际经验来解决问题，但这并没有阻碍它的广泛应用。Altair公司的Hypermesh软件，Femsys公司的FEMGV软件，ANSYS公司的ANSYS软件都采用了AFT法。该方法的时间复杂度为 o(N fog N)，与有限八叉树法，Delaunay三角化方法相当，但是在三种方法中具有最强的对生成网格单元的控制能力。
推进波前法的基本思路是首先将待剖分区域的边界进行离散，二文平面中，待剖分区域的边界离散后是一系列首尾相连的线段的集合;三文空间中，待剖分区域的边界离散后是一系列拓扑相容的三角形面片的集合。这种离散以后的区域边界称为前沿，接下来的步骤就是从前沿开始，依次插入一个新节点或采用一个已存在节点生成一个新单元，一个新的单元生成以后，前沿要进行更新，即向区域的内部推进，这种插入节点、生成新单元、更新前沿的过程循环进行，当前沿为空时表示整个区域分割结束。
推进波前法能够处理比较复杂的对象，但在理论上无法保证生成的三角形或四面体网格的质量达到一定的标准。推进波前法中存在大量的查询操作及网格前沿面的相交检测，这些操作时很费时的。所以本文不采用推进波前法。
（3）Delaunay三角划分
Delaunay三角化法[6]是目前最流行通用的全自动生成非结构化有限元网格的方法之一。Delaunay三角剖分不仅是生成有限元网格的重要方法，而且在数学、地理、工程等许多领域有着重要应用。
与其它三角网格相比，Delaunay三角网格具有两大优点:
1)Delaunay三角网格是一种空间优化结构
在构建点集的三角网格的过程中，可以按照不同的方式将点连成三角形(二文)或四面体(三文)。当把点连成Delaunay三角形或四面体时，生成的网格单元质量饱满，能够满足有限元分析计算对网格单元质量的要求，以提高计算精度。
2)Delaunay三角网格具有较好的可操作性
Delaunay三角网格是voronoi图的几何对偶图。具有严格的定义和可靠的数学理论基础，能保证对任意复杂模型进行三角剖分的算法收敛性，算法灵活性好，生成的网格单元容易控制，质量高且具有唯一性。完成网格划分后，执行插入点和删除点操作时，有可靠的理论依据，并且能保证生成的新网格仍然满足Delaunay准则。
Delaunay是本文重点研究的算法，此处只做了简短的介绍，在接下去的章节中将对该算法做进一步的详细介绍。

2.3 网格自动生成的发展与期望
有限元网格自动生成技术未来的研究热点和方向有如下几个方面[7]：
根据问题的物理特性对网格进行修改, 有两个主要的问题生成具有所有性质或部分性质的网格对现有的网格进行修改以获得所期望的性质, 其中自适应有限元分析是一个最为主要的研究领域。 MATLAB+Delaunay三角剖分算法网格生成方法的研究(4):http://www.751com.cn/zidonghua/lunwen_9243.html