Mesh analysis

This section describes the analysis routine which is performed in mmg2d in every mode (mesh generation, mesh adaptation, isosurface discretization and lagrangian movement). There are several objectives in this routine, such as identifiying geometric and non-manifold entities, computing normals, transfering information between data structures. This step is performed by calling the function:

int MMG2D_analys(MMG5_pMesh mesh);

The first step of analysis is performed by function:

int MMG2D_assignEdge(MMG5_pMesh mesh);

If the input mesh contains edges, this function transfers information (references and tags, corresponding to the fields mesh->edge.ref and mesh->edge.tag) from the mesh->edge structure that has been filled during mesh reading to the mesh->tria structure. This step is done by creating a hash table to store edges and access them quickly when travelling through the triangles. Then, if the mesh contains quadrangles, the same operation is performed to the mesh->quadra structure. Finally, the hash table and mesh->edge structure are deleted.

The second step consists in creating the adjacency table of triangles, by calling:

int MMG2D_hashTria(MMG5_pMesh mesh);

The adjacency is then stored in the array mesh->adja, which is created according to the following adjacency relation:

\[\text{adja}[3(k-1) + i + 1] = 3l + j\]

means that triangles \(k\) and \(l\) share an edge, and that this edge is locally numbered \(i\) in triangle \(k\) and \(j\) in triangle \(l\), where \(i,j \in \{0,1,2\}\).

Similarly, quadrangle adjacency is build using:

int MMG2D_hashQuad(MMG5_pMesh mesh);

and the adjacency array is stored in mesh->adjq. The adjacency relation between quadrangles is the following:

\[\text{adja}[4(k-1) + i + 1] = 4l + j,\]

where \(i,j \in \{0,1,2,3\}\) denotes the local number of the edge in quadrangles \(k\) and \(l\), respectively.

Then, adjacency between quadrangles and triangles is built according to the following relation:

\[\text{adja}[4(k-1) + i + 1] = -(3l + j),\]

where \(i \in \{0,1,2,3\}\) and \(j \in \{0,1,2\}\) denote the local index of the edge shared by quadrangle \(k\) and triangle \(l\), respectively.

The following step sets the topology of the mesh, by calling:

int MMG2D_setadj(MMG5_pMesh mesh, int8_t init_cc);

This functions travels the mesh by adjacency. If two adjacent triangles share the same domain reference, MG_GEO, MG_REF and MG_BDY tags are removed from the corresponding fields of these edges in mesh->tria structure.

Then, regardless of the values of the references, all tags on this edge are given from a triangle to the other.

If the edge is either MG_GEO, MG_REF and MG_BDY, the tags are transfered to the end vertices of this edge.

If the edge is an external boundary one, i.e. it does not have any adjacent, it receives both MG_BDY and MG_GEO tags. Its end points receive these tags as well.

If the edge is an internal boundary (separating two triangles with different references), the edge and its end points receive both MG_REF and MG_BDY tags.

The function MMG2D_setadj then processes edges that are interfacing a quadrangle and a triangle. Such edges and their endpoints receive MG_BDY and MG_REQ tags.

The following step identifies singularities in the mesh, by calling:

int MMG2D_singul(MMG5_pMesh mesh, MMG5_int ref );

This functions loops over all triangles in the mesh, and over each point of these triangles. For every point, using function MMG5_bouler, geometric points (holding MG_GEO tag) and reference points (holding MG_REF tag) incident to the point are stored.

If the point is already a corner point (MG_CRN tag), no other information is added to the point.

If stricly more than 2 features edges (either MG_GEO or MG_REF tags) are incident to the point, it is declared non-manifold (MG_NOM tag).

If exactly one reference edge and one geometric edge meet at this point, it is tagged as required (MG_REQ).

If the point is the endpoint of an evanescent ridge (i.e. there is exactly one incident geometric edge incident to this point and no other feature edge), it receives both MG_CRN and MG_REQ tags. The same is done in the case of a evanescent reference curve (exactly one incident reference curve and no other feature edge).

Finally, the last case deals with points along a reference curve or a geometric curve (i.e. exactly two references edges or exactly two ridges are incident to this point). In this situation, if the angle is sharper than a threshold (that may be specified by the user), then the point is labeled as a corner point (MG_CRN).

The next step is optional and may be activated with the -xreg command line option. It is performed by function:

int MMG2D_regver(MMG5_pMesh mesh);

The objective of this function is to regularize boundary vertex coordinates, using a Laplacian/anti-Laplacian smoothing. Firstly, the Laplacian smoothing consists in, for every boundary point \(p\), using function MMG2D_bouleendp, the two other boundary points incident to it are identified, denoted \(p^\prime\) and \(p^{\prime\prime}\) below. Then, coordinates of \(p\) are updated according to the following formula:

\[\tilde{p}_i = p_i + \lambda_1(\frac{1}{2}(p^{\prime}_{i}+p^{\prime\prime}_{i}) - p_i),\]

where \(i \in {1,2}\) denotes the coordinate dimension and \(\lambda_1 \in [0,1]\). This parameter controls the strength of the regularization. It is set to 0.4 by default.

Then, a second loop over points is done in order to apply an anti-Laplacian smoothing:

\[\tilde{p}_i = p_i - \lambda_2(\frac{1}{2}(p^{\prime}_{i}+p^{\prime\prime}_{i}) - p_i),\]

where \(\lambda_2 \in [0,1]\) is set by default to 0.399. Finally, a check is made to ensure that no triangles are flipped during the displacement of these points. In the case of a flipped triangle, a dichotomy is performed in order to find the best valid position for the regularized point.

The next step consists in computing normal vectors over the mesh, by calling function:

int MMG2D_norver(MMG5_pMesh mesh, MMG5_int ref);

In mmg2d, normal vectors are computed at boundary vertices (internal or external). However, they are not computed at corner and non-manifold points. For every point belonging to a reference or geometric curve, its normal is computed as the mean of the normals of both its incident feature edges.

The last step is optional and may be triggered by using the -nreg command line option and is similar to MMG2D_regver. The function:

int MMG2D_regnor(MMG5_pMesh mesh);

is used to regularize the normals. This concludes the analysis phase.