An Overview of Mesh Improvement Techniques
Judy Hill
Geometric Modeling Project
Spring, 1998

With the advent of the supercomputer, the use of finite elements to model complex systems has dramatically increased. Because of parallel processing and increased computational speed, finite element meshes now contain millions of elements. Automatic mesh generators, using algorithms such as Delaunay triangulation, create these large meshes. However, invariably after meshing, areas of the mesh are distorted and may cause numerical instability in the analysis. Reconfiguration of the elements may improve accuracy.

Algorithms have been developed which, when implemented as a post-processor to mesh generation, can improve mesh quality. These techniques are classified as follows:

• Mesh relaxation.
• Mesh smoothing
• Topological optimization

A relatively new technique, Frey and Field first proposed mesh relaxation in 1991. Prior to the development of this method, mesh smoothing (to be discussed later) was applied directly after triangulation. However, Frey and Field suggested improving mesh regularity by altering its connectivity would improve the quality of the mesh before smoothing.

Frey and Field defined the degree of a node as the number of edges connected to it. For example, in Figure 1, the degree of node A is eight. Similarly, the degree of node B is seven and node C is four. Delaunay triangulation is based on maximizing the minimum angle in the mesh and, ideally, produces a mesh of equilateral triangles. Thus, we can conclude that the ideal degree of interior nodes is six. The ideal degree of boundary nodes is determined separately.

Figure 1. Mesh with badly formed elements.

Mesh relaxation identifies the interior nodes with degrees greater or less than the ideal. Thus, in Figure 1, there are three nodes with degrees greater than six (black) and three with degrees less than six (white). There is also one "ideal" node (gray). The connectivity of the mesh can be changed by swapping edges to improve the degrees of the non-ideal nodes.

As an example, in Figure 2a, a polygon is highlighted. Two nodes have degrees greater than six (black) and two have degrees less than six (white). By changing the connectivity of the diagonal of this polygon as shown in Figure 2b, the two of the nodes now have degrees that are ideal (gray). Applying this technique throughout the mesh may improve the degree of the interior nodes in the mesh. Indirectly, it also improves the interior angles of the mesh.

Figure 2. Mesh elements (a) before relaxation, (b) after relaxation.

From this simple description of the algorithm, it is evident that mesh relaxation is relatively simple to implement as a post-processor to a mesh generator.

However, mesh relaxation has several disadvantages. Mesh relaxation, when implemented for an entire mesh, is order dependent. Thus, traversing the nodes in the mesh will generate two different meshes. Determining the absolute global optimum requires a comparison of many different relaxed meshes. Second, the method described is only applicable to convex domain. For concave boundaries, an edge swap may result in a boundary violation. Finally, to improve the shape and angles of the triangular elements, interior point spacing must vary smoothly along the domain.

Application of mesh relaxation to three-dimensions is a relatively new research area. There are two complications that result from three-dimensional applications. Determining the ideal degree of a node in three dimensions is much more difficult. Three-dimensional edge swapping is more difficult and computationally expensive to solve because it becomes a face-swapping problem.

Practical Application of Mesh Relaxation (Improvement obtained using relaxation techniques in a real mesh)

In the last 10 years, the development of and improvement of mesh smoothing methods has been, and continues to be, a research area of considerable interest. Mesh smoothing changes the topology of a finite element mesh by relocating internal nodes to a more "favorable" position, thus improving the local quality of the mesh. Typically, multiple sweeps of the internal nodes are performed until the elements have been sufficiently repaired.

Cavendish first proposed mesh smoothing in 1978 as a method for improving the quality of planar meshes. Since named Laplacian smoothing, many of the newer techniques are variations and improvements on this method. Laplacian smoothing will be discussed in the greatest detail, with brief mention to other methods.

Geometrically, Laplacian smoothing is relatively easy to visualize in two-dimensional space. As shown in Figure 3a, an automatic mesh generator can generate non-uniform elements. Some elements exhibit a high aspect ratio causing numerical inaccuracy in FEM analysis.

Figure 3. Mesh (a) before Laplacian smoothing, (b) after Laplacian smoothing.

The goal, though unrealistic, of Laplacian smoothing is to relocate the internal nodes of the mesh so that the elements are equilateral. As depicted in Figure 3a, the boundary nodes are fixed due to the problem constraints. However, the internal nodes can be relocated. For each internal node, the node is relocated to the geometric center, or centroid, of the polygon comprised of the elements containing the internal node. Typically, two passes through the internal nodes are needed to significantly improve the mesh.

The disadvantage of Laplacian smoothing is that it operates heuristically and, thus, does not guarantee an improvement in the element quality, especially when the element angles are quite large or quite small. When this method is used, care must be taken that elements are not inverted when nodes are relocated. Furthermore, Laplacian smoothing does not necessarily guarantee a valid mesh after smoothing. Delaunay properties are not necessarily preserved after Laplacian smoothing.

Because of the disadvantages of the Laplacian algorithm, improvements to the method have been made. These include, but are not limited to, optimization-based smoothing and techniques based on element-side length, rather than the centroidal location.

The first revision of the Laplacian smoothing algorithm added a quality measure to the mesh. If the new local mesh quality was better than the previous quality (plus some user designed threshold value), the node was moved. However, if the local transformation did not significantly improve the quality of the mesh, it was not. This eliminates the problem of guaranteeing an improved mesh, but does not improve elements with extreme angles.

To address the problem of improving elements with extreme angles, local optimization smoothing methods have been proposed by many people, including Freitag and Ollivier-Gooch (1996) and Bank and Smith. These methods have largely addressed the problem of improving elements angles. However, it is much more computationally expensive.

The length constraint method, while modifying the nodal coordinates of the elements as does Laplacian smoothing, uses different criteria to identify elements of "poor quality". In this method, element types, tetrahedra, hexahedra, pyramids, etc, have ideal lengths for each side. For example, for a cube, the ideal length of each side is L and each diagonal on a face is 1.414L. For a very localized region of a mesh, this method is improves the aspect relation of the elements.

Practical Applications of Mesh Smoothing (Improvements obtained using smoothing techniques in real meshes)

Local mesh reconfiguration involves changing the connectivity of a small area of the mesh and, thus, changing the topology of a given set of vertices. In theory, an improvement in a local area of the mesh should improve the overall mesh quality. Local mesh reconfiguration methods are divided into two classes:

0. Face swapping
1. Edge swapping

These two methods are discussed in detail below.

Face swapping is the reconnection of the vertices of two existing elements forming new elements. For the five vertices of two tetrahedra, many new configurations can be imagined; however, only two configurations are physically realizable in the global mesh. Figure 4 illustrates the two possible reconnection schemes.

Figure 4. Two configurations for face swapping. (Freitag and Ollivier-Gooch, 1997)

Figure 4a replaces two elements with three elements, whereas Figure 4b replaces two elements with two different elements. Note that in Figure 4a, an additional edge is created during the reconnection. In Figure 4b, the shaded faces represent coplanar faces, such as might be found on a boundary, that remain coplanar after reconnection to ensure connectivity with the global mesh.

Face swapping has two significant advantages. First, because there are only two realizable reconfigurations, implementation of swapping is relatively simple. Second, determining the optimum of the two configurations is computationally inexpensive.

The disadvantage to face swapping is that has yet to be proven whether a series of local reconfigurations will produce a globally optimum mesh. Whether the local transformation significantly improves the final outcome needs to be determined.

To reconfigure tetrahedra of poor quality that share a common edge, edge swapping is often used. Determination of tetrahedral quality is related to the size of the dihedral angles and the solid angles, though exact quality measures are personal preference. If several tetrahedra are identified as being of poor quality, improvement may be possible using edge swapping. A diagram of an edge swap is shown in Figure 5.

Figure 5. Edge swapping configuration. (Freitag and Ollivier-Gooch, 1997)

Initially, five tetrahedra, identified as 01BT, 12BT, 23BT, 34BT, and 40BT, shared the edge TB. The common edge, BT, was removed and the original tetrahedra were replaced by six new elements: 012T, 021B, 024T, 042B, 234T, and 234B.

In general, if an edge is shared by N tetrahedra, the N tetrahedra are replaced with 2N-4 tetrahedra. Because, as N becomes larger, the reconfigured local mesh contains many more elements than the original, values greater than 7 for N are typically never used.

There are several disadvantages to the edge swapping technique. For each original configuration, especially as N becomes larger, determining the optimum geometry requires comparing multiple configurations, a computationally expensive process. Due to symmetry and redundancy in the geometry of the tetrahedra, comparison algorithms can be implemented to reduce computation time. However, comparison algorithms create a memory storage issue. Therefore, edge swapping is a trade-off between computation time and memory storage.

Practical Applications of Topological Optimization (Improvements obtained using face and edge swapping in real meshes)

Mesh improvement is a "hot topic" in finite element research today. The demand for accuracy and stability in FEM meshes necessitates the need for improving the current mesh refiniement methods. Because each method presented has disadvantages, there is room for further research.

Mesh relaxation, because it is such a new development, appears to have the greatest potential for future research. A three-dimensional implementation has yet to be developed because of the difficulty of determining the "ideal" nodal degree. Thus, quantifying this ideal in three-dimensions would be a significant breakthrough, especially from the application point-of-view.

Though Laplacian mesh smoothing is well-defined, it is apparent that it does not produce the best quality mesh. Further research which can encompass the computational efficiency of Laplacian smoothing with the accuracy of other methods, such as optimization-based smoothing is needed.

It has yet to be proven that a local topological improvement will globally improve the FEM mesh. Furthermore, determining the optimal combination of computational time and memory storage seems to be yet unresolved.

Though these algorithms have been presented independently, very rarely are they used independently in practice. Most often, a relaxation technique is combined with a smoothing technique to generate a globally optimum mesh. Misshapen elements are then topologically improved by either face or edge swapping. It has been shown that a combination of all three methods tends to provide the best mesh for numerical stability and accuracy.

Amezua, Hormaza, Hernandez, Ajuria. 1995. A method for the improvement of 3D solid finite-element meshes. Advances in Engineering Software. 22:45-53.

Boender, E. 1994. Reliable Delaunay-based mesh generation and mesh improvement. Communications in Numerical Methods in Engineering. 10:773-783.

Freitag, L. 1997. On Combining Laplacian and optimization-based mesh smoothing techniques. Trends in Unstructured Mesh Generation, ASME Applied Mechanics Division. Volume AMD-Vol. 220, pp. 37-44.

Frietag, L.A. and C. Ollivier-Gooch. 1997. Tetrahedral mesh improvement using swapping and smoothing. Int. J. for Numerical Methods in Engineering. 40(21): 3979-4002.

Frey, W.H. and D.A. Field. 1991. Mesh relaxation: A new technique for improving triangulations. International Journal for Numerical Methods in Engineering. 31(6): 1121-1133.

Bank and Smith. Mesh smoothing using a posteriori error estimates. To appear in SIAM Journal of Numerical Analysis.

Borouchaki, and P.L. George. 1997. Aspects of 2-D Delaunay mesh generation. International Journal for Numerical Methods in Engineering. 40(11): 1957-1975.

Cavendish, J.C. 1978. Automatic triangulation of arbitrary planar domains. International Journal for Numerical Methods in Engineering. 8(4): 679-696.

Field, D.A. 1988. Laplacian smoothing and Delaunay triangulations. Communications and Applied Numerical Methods. 4(6): 709-712.

Lo, S. 1985. A new mesh generation scheme for arbitrary planar domains. International Journal for Numerical Methods in Engineering. 21(8): 1403-1426.