4.2.1.1 Mesh Refinement

The most important metrics of a mesh refinement algorithm are locality and preservation of the quality of the elements. Recursive and iterative refinement algorithms for three-dimensional tetrahedral meshes were introduced in [65] and [66], respectively. Both algorithms are based on the intersection of an edge of a tetrahedron and result in the very same (refined) tetrahedralization. They take into account the history of refinement steps and work in the following way:

• In a first step all tetrahedrons for which an estimated error exceeds a certain limit are marked for refinement.

• Second, all marked tetrahedrons are split along their refinement edge. Depending on the used algorithm this split is either performed recursively or iteratively. Note that also elements that originally were not marked for refinement can be refined.

The criterion for selecting the refinement edge depends on the history of a given tetrahedron. The algorithm defines three generations of refined elements, where each generation is refined differently. The generations are numbered in ascending order with the children of generation three belonging again to generation one. The algorithm results in choosing the longest edge in many cases. The above mentioned algorithms keep the refinement local by refraining from refining the longest edge in some cases. The iterative algorithm is more complicated to implement, the recursive algorithm requires a hard criterion on the initial tetrahedralization.

The refinement algorithm that is implemented in our simulator is a simplification of the above mentioned algorithms. For sake of simplicity it always recursively refines the longest edge of the tetrahedron under consideration. Fig. 4.6, Fig. 4.7, and Fig. 4.8 illustrate the algorithm.

Figure 4.6: Initial tetrahedralization.

Figure 4.7: Mesh after first two recursion steps.

Figure 4.8: Final refinement result.

Fig. 4.6 depicts the initial input mesh with one tetrahedron marked for refinement (drawn in thick lines). The edges $e1$, $e2$, and $e3$ depict the longest edge of every tetrahedron respectively. Both edges $e2$ and $e3$ are longer as edge $e1$, thus the neighboring elements are refined recursively. Fig. 4.7 illustrates the case after two recursion steps. New tetrahedrons and edges ($n1$ to $n4$) were introduced by splitting along edges $e2$ and $e3$ of the original mesh. Fig. 4.8 shows the final result of the refinement step. The tetrahedrons that result by splitting the originally marked element are drawn in thick lines. In this example a total of $6$ new tetrahedrons was generated. The recursion is guaranteed to stop, although in the worst case every tetrahedron of the mesh will be refined. However, the application of the algorithm in two and three dimensions showed very good locality (see Fig. 4.12 and Fig. 4.13) which justifies the usage of this simple refinement mechanism.

Since the longest edge of a tetrahedron implies the biggest dihedral angle, one could suspect that a bisection of the longest edge of any tetrahedron allows to make the resulting mesh conforming to the angle criterion by an iterative application. Unfortunately, this is not the case, since geometrical similarities can not be generally avoided for successive refinement steps even if all edges violating the angle criterion are refined. Fig. 4.9

Figure 4.9: Two-dimensional example of geometrical similarities occurring during recursive mesh refinement. The dash-dotted line depicts the optimal point at which the edge $e1$ should be split.

indicates a simple two-dimensional case for such a geometrical similarity. Although by bisecting the edge its length $l_k$ is reduced and thus it improves the angle criterion (4.1), the sum will never become positive if it was originally negative for that edge. Additionally, new edges might be introduced that have an even larger negative sum as the worst edge in the initial mesh. Thus, the bisection algorithms in conjunction with the angle criterion can not generally be applied as an operation to improve mesh quality.

2003-03-27