任意形状三维物体的Delaunay网格生成算法

DELAUNAY ALGORITHM AND RELATED PROCEDURE TO GENERATE THE TETRAHEDRON MESH FOR AN OBJECT WITH ARBITRARY BOUNDARY

介绍一种基于Delaunay算法的四面体单元的自动网格划分算法。该算法适用于由任意曲面围成的三维物体。在网格生成过程中,运用背景网格加快了四面体网格的生成速度;通过对网格中新插入点的Delaunay空腔的边界面进行检验,避免了四面体单元的重叠。提出一个判断点是否在任意封闭区域内的算法,实现了凹形物体的Delaunay网格生成。算例表明,该算法能够较好地生成任意形状三维物体的四面体单元网格。

Based on Delaunay algorithm, an algorithm is presented to fulfill the generation of tetrahedron mesh. The algorithm is effective for three-dimensional object of arbitrary shape, and it uses some data structures, such as array, chain and structure, to manage the nodes and the elements. Base grid is used to accelerate the generation of tetrahedron mesh. When a new node is added to the existing mesh, the bound face of the new node's Delaunay cavum must be checked, to avoid the overlapping of tetrahedron elements. A method is brought forward to judge whether a node is inside an arbitrary closed area or not, and it can be used to generate the Delaunay mesh for concave object. Examples show that the algorithm is effective to approach to arbitrary coincide.