4.5 Delaunay Methods

The Delaunay Triangulation which will be discussed in detail in Chapter 5 can be efficiently utilized as robust tetrahedralization engine for practical meshing applications. A Delaunay based meshing approach is a concept which consists of two tasks. One addresses the mesh topography which is defined through the placement of mesh points. The other task is to create the mesh topology by performing the Delaunay Triangulation for a known point set. The sequence in which the two tasks are carried out is a matter of choice and therefore two classes can be distinguished.

• The mesh points are first created by a variety of techniques. The Delaunay Triangulation is performed afterwards on the complete set of points.
• The Delaunay Triangulation is first computed for the boundary without internal points (boundary mesh). The mesh points are then inserted incrementally into the triangulation/tetrahedralization and the topology is updated according to the Delaunay definition.

The two approaches can also be combined. Both gain advantages from the Delaunay Triangulation. The creation of an initial set of points by e.g. advancing front, octree, or structured methods is much easier, because the constraint to avoid overlapping or inconsistent elements (in this case only points) is much simpler to handle. All topological issues will be addressed later by the Delaunay Triangulation in a rigorous and precisely defined way. On the other hand a Delaunay boundary mesh provides a lot of information on the structure. Internal mesh points can be added in an intelligent way (in what order and where) based on the size and location of the elements of the boundary mesh^4.2. The local topology update after the insertion of a point poses no problem and is taken care of by many Delaunay algorithms^4.3.

A tetrahedralization engine based on the Delaunay Triangulation allows a fast generation of elements without for instance the expensive intersection tests of advancing front methods. The reason can be seen in the global definition of the topology^4.4. It is therefore not necessary to check and compare one region of the mesh with every other region to verify the mesh consistency. Instead only a locally confined test of the Delaunay definition is required and the knowledge of other regions is implicit.

Fully unstructured meshes with anisotropic capabilities can be generated. Figure 4.10 depicts a detail of the Flash EEPROM in comparison to Fig. 4.7.

Figure 4.10: Boundary mesh of the floating gate structure, 36 tetrahedra.

However, the concept where the mesh topography is dealt with separately from the mesh topology is for anisotropic applications not always advantageous. The topology for a given set of mesh points might not be as expected and might destroy the desired anisotropy. For the last of the following anisotropic schemes the construction of protection layers depends on the ability of the Delaunay method to cope with thin layers.

• The mesh points are for example distributed in an advancing front style with a small stepsize compared to the lateral distances. The tetrahedralization engine is supplied with the point set. Adverse effects can occur when additional points are inserted and the topology is updated.
• In two dimensions the triangulation engine is supplied with grid lines to enforce a certain topology. It can be advantageous if these grid lines are not split. A Delaunay Triangulation can be employed without the insertion of additional points^4.5. The Delaunay criterion for elements near those grid lines and at the boundaries is not necessarily fulfilled.
• The triangulation/tetrahedralization engine is supplied with grid lines/facets. The Delaunay Triangulation results in a refinement and the Delaunay criterion is fulfilled. An anisotropic refinement technique which can handle thin layers is mandatory.

All types of thin layers including planar and bounding box aligned layers require sophisticated algorithms to be managed well. The ideal case is when a minimum of refinement is induced which occurs at corner regions of thin layers to satisfy the Delaunay criterion. How many refinement points are required and how close they must lie to a corner vertex depends on the angles formed by a non-planar thin layer in relation to its thickness. In the example of Fig. 4.10 absolutely no refinement was necessary. A thinner layer containing sharper angles complicates the situation.

Another characteristic of Delaunay methods which is important for meshing applications is the global optimization of the element quality^4.6. Unfortunately it is not always identical to the desired mesh quality, e.g. non-obtuse dihedral angles or more specific mesh requirements as described in Section 3.2. However, interesting results have been obtained which show that a three-dimensional Delaunay Triangulation combined with a local optimization of the required mesh quality is superior to methods which only perform local optimizations without concern of the Delaunay criterion [71,100,73]. Local improvements of the dihedral angle results in a topology which can be globally far from optimal. Alternating between the Delaunay criterion and a minimum maximum dihedral angle criterion can achieve better results.