Incremental Vertex Deletion

Incremental vertex deletion begins with an existing valid fine mesh and removes unwanted vertices one at a time, with a valid mesh after each deletion. This approach always results in a valid coarse mesh, even though it does not necessarily remove all unwanted vertices. In two dimensions, vertex deletion succeeds in removing all vertices for cases to date, although there is no proof of this property. In three dimensions, vertex deletion often leaves a few unwanted vertices in the coarse mesh, but always a small fraction of requested deletions.

The kernel of the incremental vertex deletion algorithm is an edge-contraction algorithm for deleting a single vertex.^6.2A vertex is removed by shrinking one of its incident edges to zero length, as illustrated in two dimensions in Figure 6.2. The left half of the figure shows a vertex 0 -- which is to be removed from the mesh -- and its immediate neighbors in the mesh. Vertex 0 will be removed by sliding it along the edge $\overline{06}$ to vertex 6. In the process, cells  $\bigtriangleup061$ and $\bigtriangleup056$ are removed, as are edges $\overline{01}$, $\overline{05}$ and $\overline{06}$. The resulting mesh fragment is shown in the right half of Figure 6.2. The kernel extends directly to three dimensions, with additional bookkeeping as the only complication.

Figure 6.2: Vertex removal by edge contraction in two dimensions

Invoking Vertex Deletion

The incremental deletion algorithm makes multiple passes through the mesh, continuing until a pass removes no vertices or until all vertices selected for deletion have been removed. Between passes, local reconnection and smoothing are applied to improve the poorest-quality regions of the mesh and facilitate further vertex removal. During each pass, for each vertex marked for deletion in the coarse mesh, an edge is selected for contraction based on the following criteria:

1. Feature hierarchy. A vertex must be removed by contraction onto a vertex that is no lower in the feature hierarchy. For example, surface vertices must be moved onto other surface vertices (including fold and apex vertices). Without this restriction, a surface vertex could be removed by contraction onto an interior vertex, changing the surface shape significantly. This rule also prevents saw-toothing of folds in three-dimensional meshes.
2. Mesh validity. The resulting mesh fragment must not have inverted cells. For example, in Figure 6.2, vertex 0 can not be moved onto vertex 1 or vertex 5 without creating a cell ( $\bigtriangleup156$) with a negative area.
3. Mesh quality. The algorithm chooses the edge contraction that gives the best quality for the resulting mesh fragment. A good choice of quality measure here is the maxmin sine criterion. This criterion maximizes the minimum sine of the angles of the cell (dihedral angles in 3D), avoiding both large and small angles. For the case in Figure 6.2, this rules out moving vertex 0 onto vertex 3, because this contraction produces the poorly-shaped cell  $\bigtriangleup345$. If edge contraction would form too poor a cell in three dimensions, the vertex is not removed; often the same vertex can be successfully removed in a subsequent pass through the mesh. This cutoff is unnecessary in two dimensions.

Mesh Post-processing

After the incremental deletion algorithm has made a complete pass through the mesh, local reconnection is used to improve mesh connectivity, and therefore the effectiveness of edge contraction in the next pass. In this context, we reconnect the mesh using both face and edge swapping and perform one pass of optimization-based smoothing with a floating threshold [3]. Both mesh optimization techniques have the goal of maximizing the minimum sine of angles.

After all vertex removal is complete, we do additional post-processing to improve coarse mesh quality. In two dimensions, we use five passes of optimization-based smoothing with a floating threshold, using the maxmin sine criterion. After the third pass, we use a single pass of mesh reconnection. In three dimensions, we again use a combination of smoothing and swapping, beginning with two passes of optimization-based smoothing with a floating threshold, followed by application of heuristics aimed at removing the worst cells in the mesh by using face and edge swapping, and finishing with two more passes of smoothing. Our post-processing regimen for three-dimensional meshes is consistent with the experimentally-inspired recommendations of Freitag and Ollivier-Gooch [3]. Post-processing improves the smallest angle in the output mesh significantly and cost is quite modest, at less than 10% of CPU time in two dimensions and far less than that in three dimensions.