MESH RELAXATION - A NEW TECHNIQUE FOR IMPROVING TRIANGULATIONS

Given a list of points defining a domain boundary, a three-stage process is often used to triangulate a domain. First, an appropriate distribution of interior points is generated. Next the points are connected to form triangles. And, finally, the connectivity data are used to reposition the interior points using the Laplacian smoothing technique, thereby usually improving the shapes of the triangles. This paper describes a new technique for mesh improvement-adjusting the connection structure during the second stage of this process. The new scheme, which we call mesh relaxation, consists of a procedure for iteratively making the mesh topology more regular by edge swapping. For each interior edge, a relaxation index is computed that depends on the degrees of its end points and adjacent points. Any edge for which this index exceeds a prescribed threshold will be swapped, i.e. replaced by a new edge connecting the adjacent points of the original edge. After all edge swaps are completed, Laplacian smoothing is applied to the mesh. Examples show that, when the mesh point density varies smoothly and due care is taken in the vicinity of the boundary, mesh relaxation can dramatically increase the regularity of the mesh and produce improved triangle shapes.