孟宪海，成文迪，徐 博，杨 钦

（1.北京航空航天大学计算机学院，北京 100191；2.中国石油天然气勘探开发公司，北京 100034）

1 绪 论

网格生成，即是将复杂几何结构离散成一组简单几何单元的过程，生成三角形或四面体网格的过程又称三角化。其中，Delaunay三角形/四面体网格具有很高的质量，对复杂区域有很好的逼近性，应用最为广泛。

Delaunay三角网格在1934年由俄国数学家Delaunay提出[1]，在此类网格中，任何一个三角形/四面体网格单元的外接圆/球中，均不包含网格中的其他顶点。Delaunay三角网格以其优良的几何性质，在工程中得到了十分广泛的应用。

点集的Voronoi图，由每个点的Voronoi单元组成，点a的Voronoi单元，定义为空间中所有到a点的欧氏距离不大于到点集中其他任何点的欧氏距离的所有点的集合。点集的Delaunay三角化结果，和点集的Voronoi图互相对偶。即如果点集中任意两点的Voronoi单元之间存在公共面，则这两点的连线即为Delaunay三角化中的一条边。二者是彼此等价的。

传统的点集Delaunay三角形/四面体网格化算法，可以生成高质量的网格，还能处理一定的限定条件[2-3]。但近年来，由于高精度科学计算，数值仿真等领域的需求，需要处理更大数据量、生成更高精度的网格，还对网格的生成次序、形态等有特殊的要求，这些因素促使人们不断寻求新的网格生成思路。

经典的Delaunay三角化生成算法已经较为成熟。其中以B/W增量算法应用最为广泛[4-5]。在用B/W算法进行点集的Delaunay三角化时，首先用少量点生成初始的粗网格；之后，每插入一个新点时，检查哪些三角网格单元的外接球包含这个点，把他们删去，形成一个空洞；……