Advances in mesh optimisation based on algebraic quality metrics

Abstract

In this work we focus our attention on two aspects related to node movement in surface meshes: smoothing of triangular meshes defined on surfaces and the adaption of these meshes to match given curves or contours.The improvement in quality of the mesh is obtained by an iterative process in which each node mesh is moved to a new position that minimises a certain objective function. The objective function is derived from some algebraic quality measures [l, 2] of the local submesh, that is, the set of triangles connected to the adjustable or free node.When we deal with meshes defined on surfaces we have to impose some restrictions on the movement of the free node. Firstly, it is clear that such a node must be sited on the surface after optimisation. However, this is not the only constraint. If we allow the free node to move on the surface without imposing any other restriction, apart from being guided by the improvement in quality, the optimisation procedure can construct a high-quality local mesh, but with this node in an unacceptable position. To avoid this problem the optimisation is done in the parametric mesh, where the presence of barriers in the objective function maintains the free node inside the feasible region. In this way, the original problem on the surface is transformed into a two-dimensional one on the parametric space. In our case, the parametric space is a plane, chosen in terms of the local mesh, in such a way that this mesh can be optimally projected performing a valid mesh, that is, without inverted elements.We use the flexibility that this techniques provides to adapt a given surface mesh to a curve defined on it. The idea consists of displacing the nodes close to the curve to positions sited on the curve. The process is repeated until it is correctly approximated (interpolated) by a set of mesh edges which are linked.To determine of which nodes can be projected on the curve we analyse if there is a position on the curve on which the free node can be projected without inverting any triangle of its local submesh. The optimal position of the free node on the curve is determined, attending to the quality of the local submesh.Sometimes we lack an analytical expression for the curve to be interpolated and, instead, this is given by a set of aligned points with a high enough density. This is the case, for example, for data supplied by digitalised maps describing coastal shores or river banks.