A Combined Quadtree / Delaunay Method: for 2d Mesh Generation

Unstructured simplicial mesh is an integral and critical part of many computational electromagnetics methods (CEM) such as the finite element method (FEM) and the boundary element method (BEM). Mesh quality and robustness have direct impact on the success of these CEM methods. A combined quadtree/Delunay 2D mesh generator, based on the early work of Schroeder (1991, PhD), is presented. The method produces a triangulation that approximates the original geometric model but is also topologically consistent. The key advantages of the method are: (a) its robustness, (b) ability to create a-priori graded meshes, and (c) its guaranteed mesh quality. The method starts by recursively refining the grid and using a 2:1 balanced quadtree data structure to index each cell. Once the quadtree grid is refined at a user-defined level associated with each geometrical model topological entity, each cell in the grid is successively triangulated using the Delaunay method. Finally, the method handles some modeling errors by merging vertices and allowing overlapped faces.