6.1 Choosing the right unstructured algorithm

Gmsh currently provides a choice between three 2D unstructured algorithms and between two 3D unstructured algorithms. Each algorithm has its own advantages and disadvantages.

For all 2D unstructured algorithms a Delaunay mesh that contains all the points of the 1D mesh is initially constructed using a divide-and-conquer algorithm(7). Missing edges are recovered using edge swaps(8). After this initial step three different algorithms can be applied to generate the final mesh:

1. The “MeshAdapt” algorithm(9) is based on local mesh modifications. This technique makes use of edge swaps, splits, and collapses: long edges are split, short edges are collapsed, and edges are swapped if a better geometrical configuration is obtained.
2. The “Delaunay” algorithm is inspired by the work of the GAMMA team at INRIA(10). New points are inserted sequentially at the circumcenter of the element that has the largest adimensional circumradius. The mesh is then reconnected using an anisotropic Delaunay criterion.
3. The “Frontal” algorithm is inspired by the work of S. Rebay(11).

These algorithms can be ranked as follows:

              Robustness        Performance      Element quality
MeshAdapt         1                  3                 2
Delaunay          2                  1                 2
Frontal           3                  2                 1

For very complex curved surfaces the “MeshAdapt” algorithm is the best choice. When high element quality is important, the “Frontal” algorithm should be tried. For very large meshes of plane surfaces the “Delaunay” algorithm is the fastest.

In 3D two unstructured algorithms are available:

1. The “Delaunay” algorithm is split into two separate steps. First, an initial mesh of the union of all the volumes in the model is performed using H. Si's Tetgen algorithm(12). Then a three-dimensional version of the 2D Delaunay algorithm described above is applied.
2. The “Frontal” algorithm uses J. Schoeberl's Netgen algorithm (13).

The “Delaunay” algorithm is the most robust and the fastest, and is the only one that supports the Field mechanism to specify element sizes (see section Characteristic lengths). However, this algorithm will sometimes modify the surface mesh, and is thus not suitable for producing hybrid structured/unstructured grids. In that case the “Frontal” algorithm should be preferred. The quality of the elements produced by both algorithms is comparable. If element quality is important the mesh optimizer(s) should be applied.