Swapping

Mesh swapping improves the quality of unstructured meshes by changing the local topology of the mesh.  This technique is
especially helpful in three dimensions, where the combination of swapping and shape improvement has been shown to dramatically improve mesh quality and simulation efficiency.  As part of SciDAC-1, a state-of-the-art swapping algorithm (part of the GRUMMP meshing suite) was re-implemented using the mesh and geometry interfaces. This swapping software is already in use in one widely-distributed SciDAC meshing code (GRUMMP) with over 500 downloads per year for applications in fluid and solid mechanics, medicine, and astrophysics.

In two dimensions, face swapping chooses the best diagonal for the quadrilateral formed by two neighboring triangles. Pre-defined quality  criteria include the Delaunay criterion and the maximum angle criterion.

<>In three dimensions, the swapping service performs both face swapping and edge swapping.  The former reconfigures tetrahedra that share a common face, while the latter reconfigures all tetrahedra incident on a single edge.  The canonical face swapping case is exchanging two tetrahedra that share a face with three tetrahedra, as shown in the top left part of Figure 1. The inverse swap, from three to two tetrahedra, is also possible. In addition, we allow reconfiguration of two tets to two (T22 case in the figure); in this case, the two shaded faces must be co-planar, and swapping decisions reduce to choosing the best diagonal for the coplanar quadrilateral. If two pairs of tetrahedra in the interior of the mesh share a pair of coplanar faces, this swap is also permitted; in this case, two T22 configurations are back-to-back in the mesh. In addition to these swappable configurations, there are a number of unswappable cases, some of which are illustrated in the bottom of Figure 1.

Edge swapping is a more complicated procedure, replacing N tetrahedra incident a single edge by a new set of 2N-4 tetrahedra. In the example of Figure 2, the edge TB is perpendicular to the screen. The five tetrahedra originally incident on it (01TB, 12TB, 23TB, 34TB, 40TB) are replaced by six new tetrahedra, two for each of the triangles of the (non-planar) triangulation of polygon 01234: 012T, 024T, 234T, 021B, 042B, and 324B.

The challenge with edge swapping is that the number of possible configurations grows rapidly with the number of tetrahedra incident on the edge to be removed, as seen in the table below. In practice, the number of successful 7-for-10 swaps is very small, so the swapping service does not explore possible swaps for more complex initial configurations.

<> Clearly, checking the quality of each tetrahedron in each possible configuration is a costly undertaking; instead, the quality for each unique tetrahedron is computed only once, and the quality of a given configuration is the minimum quality among its tetrahedra. To simplify bookkeeping, we also take advantage of the symmetries of the post-edge-swapping configurations and store only a small set of canonical post-swap configurations, as shown in Figure 3.

Both face and edge swapping support pre-defined quality measures that enforce the Delaunay criterion, maximize the minimum sine of dihedral angles (recommended) or minimize the maximum dihedral angle. User-defined quality measures are also supported.