Dimitris P. Vartziotis - The GETMe Mesh Smoothing Framework: A Geometric Way to Quality Finite Element Meshes

Meshes are gapless and overlapping free tessellations of domains, such as surfaces or volumes, into primitives such as triangles, quadrilaterals, tetrahedra, or hexahedra. Using geometrically simple elements of only one or a few preferably polytope types brings both the flexibility to represent large-scale domains by locally placed small elements and the flexibility to represent complex domains by uniformly shaped simple elements.

Areas of application range from art and architecture to the general field of approximation theory, including mathematical, physical, engineering, and design applications. For example, depicts the Aletis car model and mesh by TWT GmbH Science & Innovation combining design and simulation aspects.

These different fields of application often come with their own specific mesh quality requirements; for example, they may be aesthetically motivated in design and computer visualization applications or mathematically motivated in the case of finite element methods. In both cases, meshes usually have to be conformal and of good quality. That is, two elements are either disjoint or share one common node, edge or face, respectively, and each element must fulfill certain quality criteria with respect to its shape. In this context, regularly shaped elements are often preferred.

Ideally, mesh quality is an objective of the mesh generation process. For simple domains, this can, for example, be ensured by using parametric generation processes for structured meshes. A more flexible and generally applicable meshing method is the Delaunay triangulation. In a Delaunay mesh, each circumcircle of a triangle contains no other node of the mesh. It follows that the Delaunay triangulation of a set of nodes maximizes the smallest interior angle over all triangles. Delaunay triangulation is fast, flexible, robust, and generally applicable for simplicial mesh generation in arbitrary dimensions. Furthermore, it generates meshes of reasonable quality.

In contrast, mesh generation involving non-simplicial polytopes such as hexahedra as elements becomes significantly more complex, since the conformal mesh criterion imposes strong structural restrictions for element connectivity. In such cases a common scheme is to partition the domain to be meshed into simple-shaped subdomains, which can be meshed individually by a parameterized approach considering the conformal interface meshes of such subdomains. Depending on the application, more complex elements can have favorable properties. Hence, mesh generation should find a compromise between computational and implementational complexity, flexibility, and the resulting mesh quality.

Figure 1.1. Detail of the Medusa floor mosaic found in Zea (Piraeus), 2nd century AD. Image provided by user Jebulon, Wikimedia Commons, license CC0 1.0 [].

Therefore, it is common practice to address mesh quality aspects by a separate improvement step after mesh generation. This also holds for applications where the simulation domain changes its shape over time. To avoid a costly generation of a new mesh within each simulation step, the existing mesh is transformed and improved. This can either be done by local topological modifications, like splitting, inserting, or removing elements, or by node relocations only. The latter mesh improvement methods are called smoothing methods.

Depending on the element type, a local topological modification might propagate through the entire mesh to preserve conformity. For example, in a regular three-dimensional grid, splitting a cube into two equal hexahedra leads to a splitting of the mesh along an entire plane. Hence, in practice, mesh smoothing methods are preferred if the quality problems are not caused by adverse topological configurations.

One of the most common and simplest mesh smoothing methods is Laplacian smoothing, where each node is replaced by the arithmetic mean of its edge-connected neighbors. This smoothing scheme is iteratively applied a given number of times to all inner mesh nodes or iteratively applied until node positions converge. Due to its implementational simplicity and computational efficiency, Laplacian smoothing is still popular, although it might lead to the generation of inverted elements. These are elements that violate a prescribed orientation or have a negative determinant. Smart Laplacian smoothing methods avoid the generation of inverted elements by node movement restrictions or node resetting techniques. Laplacian smoothing belongs to the class of geometric smoothing schemes, since its node relocation approach and its termination criterion are entirely based on geometric entities.

Figure 1.2. Tensile structure in the Munich Olympic Park. Image provided by Diego Delso, delso.photo, Wikimedia Commons, license CC-BY-SA [].

Mesh quality is a matter of the quality criterion under consideration. The choice of the quality criterion itself depends on the field of application. Having a specific quality criterion in mind, it is an obvious approach to incorporate it into an objective function used to improve quality by means of mathematical optimization. Local optimization-based smoothing methods use this approach to move nodes of a single element or nodes shared by some elements to improve local mesh quality. In contrast, global optimization-based mesh smoothing methods incorporate the quality of all mesh elements into one objective function and relocate all non-fixed mesh nodes within one iteration step. Such steps are iterated until quality improvement drops below a given threshold. Using a strict mathematical optimization approach, these methods aim to reach at least a local maximum of mesh quality, thus providing the benchmark with respect to quality. However, using optimization-based methods comes at the cost of higher implementational and computational complexity, due to the evaluation of quality functions and numerical optimization. Therefore, various hybrid methods have been proposed to find a balance between complexity and quality.

Figure 1.3. Aletis car model and mesh by TWT GmbH Science & Innovation combining design and simulation aspects.

Many element quality criteria are based on measuring the deviation of an arbitrary element from its regular counterpart. They differ, for example, in computational complexity, generalizability with respect to different element types, and applicability with respect to optimization-based methods. Regular elements offer a high degree of symmetry. This is particularly favorable in the context of finite element methods. Here, mesh elements are used as supports for locally defined trial functions, building the basis for function spaces in which a physical solution of a partial differential equation is sought. Thus, the shape of the mesh elements has an impact on the trial functions, and, with this, on the approximation power of the associated function space.

The foundation of the geometric element transformation-based mesh smoothing framework described in this work lies within a geometric play-around with paper and pen. By constructing similar triangles on the sides of a polygon and taking the apices as new polygon points, one of the authors observed that the resulting polygon became more and more regular if applied iteratively []. A question emerged as to whether such a transformation could be used for mesh improvement by iteratively transforming the mesh element with the lowest quality, and this set the seed point for developing the geometric element transformation method, abbreviated by the acronym GETMe. Since these first steps in 2007, the theory of regularizing geometric element transformations and the associated GETMe smoothing algorithms have been developed into a powerful smoothing framework with a wide range of applications.