It is rare that any mesh generation algorithm will be able to define a mesh that is optimal without some form of post-processing to improve the overall quality of the elements. The two main categories of mesh improvement include smoothing and clean-up. Smoothing includes any method that adjusts node locations while maintaining the element connectivity. Clean-up generally refers to any process that changes the element connectivity.

5.1 Smoothing

Most smoothing procedures involve some form of iterative process that repositions individual nodes to improve the local quality of the elements. A wide variety of smoothing techniques have been proposed. These methods can generally be classified as follows:

Averaging methods
Optimization-based methods
Physically-based methods
Mid-node placement

5.1.1 Averaging Methods

Of the wide variety of smoothing algorithms, the simplest and most straight forward is Laplacian smoothing [87]. With this method, an internal node in the mesh is placed at the average location of any node connected to it by an edge. With little modification, this technique can be applicable for any element shape. Most smoothing procedures will iterate through all the internal nodes in the mesh several times until any individual node has not moved more than a specified tolerance. Although it has its problems, it is simple to implement and is in wide use. Similar to Laplacian, there are a variety of other smoothing techniques, which iteratively reposition nodes based on a weighted average of the geometric properties of the surrounding nodes and elements. Canann [88] provides an overview of some of the common methods in use.

Averaging methods quite often also employ some form of additional constraint on the movement of a node. For example, because Laplacian smoothing alone sometimes has the tendency to invert or degrade the local element quality, a comparison of local element quality is made before and after the proposed move and the node moved only if element quality is improved. This is often referred to as constrained Laplacian smoothing. Canann[88] presents criteria for the movement of the node with this method.

5.1.2 Optimization-Based Methods

Rather than relying on heuristic averaging methods, some codes use optimization techniques to improve element quality. Optimization-based smoothing techniques measure the quality of the surrounding elements to a node and attempt to optimize by computing the local gradient of the element quality with respect to the node location. The node is moved in the direction of the increasing gradient until an optimum is reached. Canann [88] and Freitag[89] both present optimization-based smoothing algorithms.

While maintaining that optimization-based smoothing techniques provide superior mesh quality, the computational time involved is generally too excessive to use in standard practice. Canann [88] and Freitag[90] both recommend a combined Laplacian/optimzation-based approach. What is generally advocated is that Laplacian smoothing is done for the majority of the time, reverting to optimization based smoothing only when local element shape metrics drop below a certain threshold.

5.1.3 Physically-Based Methods

Another important area of mesh improvement includes methods that reposition nodes based on a simulated physically based attraction or repulsion force. Lohner[91] simulates the force between neighboring nodes as a system of springs interacting with each other. Shimada [92] and Bossen[93] view the nodes as the center of bubbles that are repositioned to attain equilibrium. With changes in the magnitude and direction of inter-particle forces, different anisotropic characteristics and element sizes can be achieved.

5.1.4 Mid-node Placement

While most smoothing methods focus on repositioning corner nodes, Salem[94] recently introduced a method providing criteria for repositioning mid-nodes on quadratic elements to improve element quality. This method computes a region surrounding the mid-node known as the mid-node admissible space (MAS), shown in Figure 12, where the mid-node can safely be moved and maintain or improve element quality.

Figure 12. Mid-node admissible space for node at A

5.2 Cleanup

Like smoothing, there are a wide variety of methods currently employed to improve the quality of the mesh by making local changes to the element connectivities. Cleanup methods generally apply some criteria that must be met in order to perform a local operation. The criteria in general can be defined as: 1) shape improvement or 2) topological improvement.

In addition, cleanup operations are generally not done alone, but are used in conjunction with smoothing. Freitag [95] describes how smoothing and cleanup may be combined to efficiently improve overall element quality.

5.2.1 Shape Improvement

For triangle meshes, simple diagonal swaps are often performed. For each interior edge in the triangulation a check can be made to determine at what position the edge would effectively improve the overall or minimum shape metric of its two adjacent triangles. The Delaunay criteria can also be used to determine the position of an edge. For Tetrahedral meshes, Barry Joe [96] presents a series of local transformations that are designed to improve the element quality. These include swapping two adjacent interior tets sharing the same face for three tets (see Figure 3). Likewise, three tets can be replaced with two. Other more complex transformations are also defined.

In some applications where mixed element meshes are supported, the element quality of two adjacent triangles may be preferable to a single poor quality quadrilateral. When this is the case, selected quadrilaterals may be split.

In some cases, particularly with curved surfaces, the elements resulting from the mesh generator may deviate significantly from the underlying geometry. For a triangle mesh, edge swaps can be performed based on which local position of the edge will deviate least from the surface. Although not strictly a cleanup operation, local refinement of the mesh may also be considered to capture surface features.

5.2.2 Topological Improvement

A common method for improving meshes is to attempt to optimize the number of edges sharing a single node. This is sometimes referred to as node valence or degree. In doing so, it is assumed that the local element shapes will improve. For a triangle mesh there should optimally be 6 edges at a node and four edges at a node surrounded by quads. Whenever there is a node that does not have an ideal valence, the quality of the elements surrounding it will also be less than optimal. Performing local transformations to the elements can improve topology and hence element quality. Several methods have been proposed for improving node valence for both triangle [97] and quadrilateral[98] [99] meshes.

For volumetric meshes, valence optimization becomes more complex. In addition to optimizing the number of edges at a node, the number of faces at an edge can also be considered. For tetrahedral meshes this can involve a complex series of local transformations. For hexahedral elements, valence optimization is generally not considered tractable. The reason for this is that local modifications to a hex mesh will typically propagate themselves to more than the immediate vicinity. One special case of cleanup in hex meshes used in conjunction with the whisker weaving algorithm is presented by Mitchell[100] .

5.3 Refinement

Element refinement procedures are numerous. For our purposes, refinement is defined as any operation performed on the mesh that effectively reduces the local element size. The reduction in size may be required in order to capture a local physical phenomenon, or it may be done simply to improve the local element quality. Some refinement methods in themselves can be considered mesh generation algorithms. Starting with a coarse mesh, a refinement procedure can be applied until the desired nodal density has been achieved. Quite frequently, refinement algorithms are used as part of an adaptive solution process, where the results from a previous solution provide criteria for mesh refinement. Methods have been proposed for triangle and tet refinement as well as quad and hex.

5.3.1 Triangle/Tetrahedral Refinement

Although there are certainly more methods defined, three of the principal methods for triangle and tetrahedral refinement include:

Edge bisection
Point insertion
Templates

5.3.1.1 Edge Bisection

Edge bisection involves splitting individual edges in the triangulation. As a result, the two triangles adjacent the edge are split into two. Extended to volumetric meshing, any tetrahedron sharing the edge to be split must also be split as illustrated in Figure 13. Rivara[101] proposes criteria for the splitting of edges based on the longest edge of a triangle or tetrahedron.

Figure 13. Edge bisection in a tetrahedral mesh. Edge A-B is split at point C, also splitting its surrounding tetrahedra.

5.3.1.2 Point Insertion

A simple approach to refinement is to insert a single node at the centroid of an existing element, dividing the triangle into three or tetrahedron into four. This method does not generally provide good quality elements, particularly after several iterations of the scheme. To improve upon the scheme, a Delaunay approach can be used that will delete the local triangles or tetrahedra and connect the node to the triangulation maintaining the Delaunay criterion. Any of the Delaunay point insertion methods discussed previously could effectively be used for refinement.

Figure 14. Example of Delaunay refinement, where point A is inserted.

5.3.1.3 Templates

A template refers to a specific decomposition of the triangle. One example is to decompose a single triangle into four similar triangles by inserting a new node at each of its edges as show in Figure 15. The equivalent tetrahedron template would decompose it into eight tetrahedra where each face of the tet has been decomposed into 4 similar triangles. To maintain a conforming mesh, additional templates can also be defined based on the number of edges that have been split. Staten[102] outlines the various templates needed to locally refine tetrahedra while maintaining a conforming mesh.

Figure 15. Example of local triangle refinement using a template where elements at A and B are refined

5.3.2 Quad/Hex Refinement

Because of the structured nature of quad and hex meshes, the point insertion and edge bisection methods are generally not applicable. The main methods used for quad and hex refinement involve decomposing the elements based on a set of predefined templates. Both Schneiders[103] and Staten[98] propose algorithms and a series of templates for element decomposition. An example of local quad refinement is shown in Figure 16. In order to maintain a conforming mesh, some quad and hex refinement schemes will often necessarily introduce triangle or alternate shaped elements including tetrahedra and pentahedra.

Figure 16. Example of local quad refinement where elements at A and B are refined by one half.

6. Conclusion

This survey has touched only briefly on some of the main issues and algorithms used in unstructured mesh generation. There are many more important aspects of unstructured mesh generation that were not addressed. Due to time and space constraints, it was not intended to be a comprehensive overview of the subject. Instead, it was the intent to focus on some of the more fundamental algorithms and procedures. Often times in the research and development of software, we tend to forget what has gone before us, or fail to look at what is already readily available. The most efficient way to provide new and innovative technology is to build on the accomplishments of others. We should recognize the innovations and creativity of others in the field and try to improve upon what has gone before.

Back to Surface Meshing.

Go to Introduction.

Continue to References.

sjowen@sandia.gov