Fast centroidal Voronoi Delaunay triangulation for unstructured mesh generation

• Published in: Journal of computational and applied mathematics 2015-05, Vol.280, p.158-173
• Main Authors: Wang, B., Khoo, B.C., Xie, Z.Q., Tan, Z.J.
• Format: Article
• Language: English
• Subjects: Algorithms; Centroidal Voronoi tessellation; Conforming mesh; Delaunay triangulation; Finite element method; Graph theory; Iterative methods; Mathematical analysis; Mathematical models; Mesh generation; Unstructured mesh
• ISSN: 0377-0427; 1879-1778
• DOI: 10.1016/j.cam.2014.11.035

A fast unstructured mesh generation algorithm based on conforming centroidal Voronoi Delaunay triangulation (CfCVDT) algorithm (Ju, 2007) is proposed in this paper. In the new algorithm, the constrained Delaunay triangulation (CDT) algorithm is used only for the generation of the initial mesh. The mesh quality shall be continuously improved by updating the positions of vertices and flipping edges in a number of iterations. Since the most time consuming procedure in CfCVDT algorithm is the CDT in each iteration which has been successfully avoided in this new algorithm the efficiency has been significantly improved. Furthermore, the meshes generated by this algorithm have similar high quality features as that generated by CfCVDT. When complex interfaces are involved, our algorithm can keep the mesh conforming to the interfaces very efficiently. By using various density functions, this algorithm can produce high quality non-uniform meshes for potentially many applications. •A fast high quality triangular mesh generation algorithm (FCfCVDT) is proposed based on the CfCVDT algorithm.•The FCfCVDT algorithm significantly improves the efficiency of CfCVDT algorithm at the same time maintains the mesh quality.•It is capable of generating high quality body/interface fitted meshes for complicate domains/interfaces.