网格生成技术在有限元分析、计算机图形学、科学计算可视化、生物医学和地理信息系统等领域有着广泛的应用,该技术是制约这些领域发展的一个关键因素,因此很多年来其一直是诸多学者研究的热点问题。 在众多网格生成算法中,Delaunay三角化方法由于其算法效率高、剖分单元质量好、完善的数学理论基础及其判断准则,非常适合二维平面及三维实体的网格剖分,具有其它算法不可比拟的优越之处。本文研究内容如下: (1)以计算几何理论为基础,应用计算几何理论中的凸壳技术、Voronoi图及其Delaunay三角化算法,着重研究了约束Delaunay四面体网格生成算法,并在逐点插入的Delaunay三角化流程基础上引入了随机扰动算法,提高了剖分的四面体单元的质量。 (2)重点研究了Delaunay三角化算法急需解决的两个关键性问题:指定区域的边界边和边界面的一致性问题以及如何解决薄元的问题。二维的边界恢复已经得到了很好的解决,但因为三维中点、边、面和四面体之间的复杂关系,一直没有得到很好的解决,本文详细分析了点、边、面和四面体之间的各种几何位置关系,提出了可以解决各种复杂情况下的边界恢复问题。而在四面体网格生成过程中,经常会出现狭长四面体——薄元,薄元的存在是提高四面体网格单元质量的重要影响因素,本文通过对薄元进行分解很好的解决了该问题。 (3)最后在边界恢复和薄元消除的基础上,采用相邻单元体间的局部变换以及网格的光顺技术,很好地保证了网格的质量。 实验表明,本文提出的改进约束Delaunay三角化算法、边界恢复算法和薄元消除算法,效率高、普适性好、网格单元质量高且易于实现。