Analysis routines

After reading the input mesh, mmg3d performs an analysis of the mesh in order to identify many information about the topology of the mesh. The file \(\texttt{analys_3d.c}\) contains several routines that allow to process the mesh, and notably set the relevant tags to its entities.

Overview of the \(\texttt{MMG3D_analys}\) function

In every mode (mesh adaptation, iso-surface discretization and lagrangian movement), mesh analysis is performed by calling:

int MMG3D_analysis(MMG5_pMesh mesh);

This function is comprised of several steps that can be divided in two major sections: setup of the adjacency and topology analysis.

The \(\texttt{MMG3D_analys}\) function creates the triangle mesh of the boundary, and eventually transfers the information back to the xtetra structure. A rough overview of the operations performed in this function is as follows.

  • The function \(\texttt{MMG5_chkBdryTria}\) physically creates a triangle mesh for the boundary of the considered mesh.

  • The structure xtetra is temporarily eliminated.

  • The surface triangle mesh is analyzed:

    • The triangles that should not be affected by remeshing (and their edges) are tagged appropriately in the function \(\texttt{MMG3D_set_reqBoundaries}\).

    • The surface triangle adjacencies are created in \(\texttt{MMG3D_hashTria}\).

    • A hash table is created for the particular edges supplied by the user in \(\texttt{MMG5_hGeom}\).

    • The function \(\texttt{MMG5_setadj}\) is used.

    • The normal vector to the surface part is computed, regularized, and stored at boundary vertices through the functions \(\texttt{MMG5_norver}\) and \(\texttt{MMG5_regnor}\).

  • All the information borne by the mesh->tria structure is transferred to the mesh->xtetra structure by the function \(\texttt{MMG5_bdrySet}\): all the information about the boundary is thence carried by the tetrahedra, and the triangles entities are eliminated.

The remainder of this section describes the various components of analysis in more details.

\(\texttt{MMG3D_hashTetra}\)

The first step of analysis consists in filling the tetrahedra adjacency array by calling:

int  MMG3D_hashTetra(MMG5_pMesh mesh, int pack);

Tetrahedra adjacency is filled in mesh->adja and is organized according to the following convention:

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

means that tetrahedra \(k\) and \(l\) share a face, and this face is locally numbered \(i\) in triangle \(k\) and \(j\) in triangle \(l\), where \(i,j \in \{0,1,2,3\}\).

\(\texttt{MMG3D_update_xtetra}\)

In iso-surface discretization mode (-ls) and open-boundary mode (-opnbdy), the xtetra structure is updated. In other modes, since this structure has not been created yet, this function is skipped.

\(\texttt{MMG3D_hashPrism}\)

Prism adjacency array mesh->adjapr is filled according to the following adjacency relation:

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

where prisms \(k\) and \(l\) share a face, which is respectively numbered \(i\) and \(j\), with \(i,j \in \{0,1,2,3,4\}\).

\(\texttt{MMG3D_bdryPerm}\)

This step consists in:

  1. Hashing triangles

  2. Looping over faces in tetrahedra, checking consistency of orientation between tetrahedra faces and triangles. The orientation is defined by the order in which vertices are stored in arrays tria[].v and tetra[].v.

\(\texttt{MMG5_chkBdryTria}\)

This function physically creates a triangle mesh for the boundary of the input mesh. This function mainly encapsulates the other function \(\texttt{MMG3D_bdryBuild}\).

\(\texttt{MMG3D_bdryBuild}\)

This function physically creates the surface entities (triangles and edges) of the input mesh. Relying on the information contained in the mesh->xtetra structure, the fields mesh->tria and mesh->edge are filled.

\(\texttt{MMG3D_hashTria}\)

This function essentially calls the common function \(\texttt{MMG5_mmgHashTria}\). The latter creates the adjacency relations within the surface mesh, by filling the table mesh->adjt. On the fly, non manifold edges are identified as those edges shared by strictly more than 2 triangles; the tags MG_NOM are set accordingly.

\(\texttt{MMG5_hGeom}\)

This function creates a hash structure for the special edges, that deserve a particular care during the remeshing process.

  • If the user has supplied particular edges, these are added to the hash structure, and in addition, other particular edges are inferred from the triangles structure.

  • Else, a hash structure is created for those special edges.

In both situations, the mesh->htab field is filled with a hash structure for surface edges. Moreover, the tags and references of these edges are consistently set in the ->tag[i] and ->edg[i] fields of surface triangles.

\(\texttt{MMG5_setadj}\)

This function travels the surface mesh by adjacency, and detects potential Mobius flips. Meanwhile, it sets the tags MG_REF and MG_OPNBDY by traveling the surface mesh and checking adjacencies.

\(\texttt{MMG5_setdhd}\)

This function travels an input boundary mesh, made of triangles.

  • Step 1. It identifies whether some ridges provided by the user may be accidental, in the sense that the angle between the corresponding triangles is nearly flat.

  • Step 2. It tags edges between triangles with a large dihedral angle with an MG_GEO tag, and those between triangles with different references with an MG_REF tag.

\(\texttt{MMG5_setNmTag}\)