Robust And Efficient Constrained Delaunay Tetrahedral Mesh Generation

The Finite Element Method (FEM) is increasingly important in the field of the structure analyzing and design. Combining with the computer Aided Design (CAD), FEM has become one of the essential parts of the Computer Aided Engineering (CAE). As the increasing complexity of the engineering problems, the fully automatic mesh generation is more crucial than before. The efficiency and robustness of the tetrahedral mesh generation is the guarantee of the application of FEM in engineering and science.In this paper, the Delaunay tetrahedral mesh generation method is well studied and improved.In the first section of this paper, the recent work of the unstructured mesh generation is discussed. Firstly, kinds of popular unstructured mesh generation algorithms are illustrated here. Then we introduce the Delaunay triangulation from the following aspects:(1) the boundary recovery; (2) the inner nodes generation; (3) the elimination of sliver elements. We demonstrate the current researches as well as the existing algorithms.In section 2, the frame of the algorithm proposed in this paper is illustrated. To be more exactly, the components of the frame are the rapid node inserting, the confirming boundary recovery, the constrained boundary recovery and the inner node generation. Based on existing algorithm, we improve the current mesh generating methods by enhance their robustness.In section 3, a rapid Delaunay inserting process is proposed. It enlarges the solution scale of the generation method, which can generate more than 10 million elements in one personal computer. We achieve this from two aspects, speeding up the node locating and the new tetrahedral constructing. Through proposing different methods for three mostly used point sets (which are the random point set, the cubic point set and the triangular surface point set) respectively, we make tetrahedral generator works well in vast engineering applications.In section 4, a robust confirming boundary recovery method is developed. Robust geometric predicates are employed to detect the intersection of an edge and a facet. Then arbitrary triangular boundaries are recovered with the help of these predicates. Through a heuristic insertion process, the algorithm reduces the number of Steiner points on the boundary. We resolve the problem of the tetrahedralization for the concave domain (which is impossible for classical Delaunay triangulation) successfully. In section 5, a constrained boundary recovery algorithm is proposed. Despite the confirming boundary recovery method recovered the geometry boundary of the given model, the topological property of the original triangular mesh is destroyed during the process of Steiner nodes inserting. To solve this problem, we employ a kind of dynamic programming method to remove the Steiner nodes on the boundary. Although this algorithm generates elements with zero volume, we utilize a modified Laplacian smoothing method to eliminate the zero-volume elements. In theory, the constrained boundary recovery method can recover arbitrary boundary.In section 6, a Delaunay triangulation with advancing front technology (AFT) is introduced. This approach takes the initialized Delaunay triangulation as background mesh, and then generates the new nodes by AFT. Finally the new generated nodes are inserted by constrained Delaunay inserting process. This method combines the merits of Delaunay triangulation and AFT.Finally, a summery is given and the future work is discussed.