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_analys(MMG5_pMesh mesh)¶

preprocessing stage: mesh analysis.

At the end of this function:

triangles have been deleted and stored in xtetra;
Boundary point have been analyzed and associated to xpoints (if needed). If computed tangent is stored in ppt->n and normals in pxp->n1 and pxp->n2. Following list summerizes computed (and not computed) data depending on point type:
- Corner point (MG_CRN): no computation (and no xpoint);
- Required points have different treatment depending if they are along a ‘regular’ surf point, along an internal or external non-manifold edge, along a non connex mesh part(so they may have a xpoint, a tangent and a normal or not) but their normal is not used during remeshing. See comments in MMG3D_nmgeom
- Reference point (MG_REF): xpoint, tangent, 1 normal;
- Ridge point (MG_GEO): xp, tangent,2 normals;
- Non-manifold point (MG_NOM): xp, tangent, no normal if internal, 1 normal if external
- Open boundary points (MG_OPNBDY) are treated as nm points.

Parameters:: mesh – pointer to mesh
Returns:: 1 if successful, 0 if fail

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 \(\texttt{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 \(\texttt{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 \(\texttt{mesh->tria}\) structure is transferred to the \(\texttt{mesh->xtetra}\) structure by the function \(\texttt{MMG5_bdrySet}\): all the information about the boundary is then 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)¶

Create array of adjacency.

Create table of adjacency. Set pack variable to 0 for a compact mesh and to 1 for a mesh that need to be packed.

Parameters:

mesh – pointer to the mesh structure.
pack – we pack the mesh at function begining if \(pack=1\).

Returns:

0 if failed, 1 otherwise.

Tetrahedra adjacency is filled in \(\texttt{mesh->adja}\) and is organized according to the following convention:

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

which 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 (\(\texttt{-ls}\)) and open-boundary mode (\(\texttt{-opnbdy}\)), the \(\texttt{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:

Hashing triangles
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 makes various verifications concerning the integrity and consistency of data related to mesh boundary. These checks are divided in the following sub-steps:

int MMG5_chkBdryTria_countBoundaries(MMG5_pMesh mesh, MMG5_int *ntmesh, MMG5_int *ntpres)¶

Step 1 of MMG5_chkBdryTria : scan the mesh and count the boundaries.

Parameters:

mesh – pointer to the mesh structure.
ntmesh – number of boundary triangles.
ntpres – number of preserved boundaries (open boundary mode).

Returns:

0 if failed, 1 if success.

Count the number of boundary faces in tetrahedral mesh: a face is considered a boundary if the tetrahedron has no neighbour across this face or if the neighbouring tetrahedron has a different reference value (indicating a different material).
A similar procedure is performed for faces belonging to prisms.
In open boundary mode, faces belonging to a open boundary (a boundary that is not delimiting two different materials, but that are still marked as boundary by the user) are also counted.

int MMG5_chkBdryTria_hashBoundaries(MMG5_pMesh mesh, MMG5_int ntmesh, MMG5_Hash *hashElt)¶

Step 2 of MMG5_chkBdryTria : create hash tables of boundaries in the mesh

Parameters:

mesh – pointer to the mesh structure.
ntmesh – number of boundary triangles in the mesh.
hashElt – pointer towards face hash table.

Returns:

0 if failed, 1 if success.

Boundary faces of tetrahedra and prisms are hashed by this function in order to check which faces may be counted twice or that may be missing in the tria array, storing data in the form of MMG5_Tria data structure. In open boundary mode, all faces are hashed.
Flagging of such extra triangles is performed by function:

int MMG5_chkBdryTria_flagExtraTriangles(MMG5_pMesh mesh, MMG5_int *ntpres, MMG5_Hash *hashElt)¶

Step 2.5 of MMG5_chkBdryTria : Travel through the tria, delete those that are not in the hash tab or that are stored more that once.

Parameters:: mesh – pointer to the mesh structure.
Returns:: 0 if failed, 1 if success.

Effective removal of flagged triangles is then performed by calling:

int MMG5_chkBdryTria_deleteExtraTriangles(MMG5_pMesh mesh, MMG5_int *permtria)¶

The final sub-step is then performed with:

int MMG5_chkBdryTria_addMissingTriangles(MMG5_pMesh mesh, MMG5_int ntmesh, MMG5_int ntpres)¶

Step 3 of MMG5_chkBdryTria : add the missing boundary triangles or, if the mesh contains prisms, set to required the triangles at interface betwen prisms and tet

Parameters:: mesh – pointer to the mesh structure.
Returns:: 0 if failed, 1 if success.

If triangle count is correct, \(\texttt{MG_BDY}\) tag is added to all points belonging to a triangle.
Otherwise, if found number exceed given one, missing boundary triangles are added using MMG5_bdryTria.

\(\texttt{MMG5_freeXTets}\) and \(\texttt{MMG5_freeXPrisms}\)¶

These two functions reset all data relative to \(\texttt{xtetra}\) and \(\texttt{xprisms}\) in the \(\texttt{mesh}\) structure:

void MMG5_freeXTets(MMG5_pMesh mesh)¶

Free xtetra structure.

Parameters:: mesh – pointer to the mesh structure.

void MMG5_freeXPrisms(MMG5_pMesh mesh)¶

Free xprism structure.

Parameters:: mesh – pointer to the mesh structure.

\(\texttt{MMG3D_set_reqBoundaries}\)¶

void MMG3D_set_reqBoundaries(MMG5_pMesh mesh)¶

Set all boundary triangles to required and add a tag to detect that they are not really required.

Parameters:: mesh – pointer towards the mesh structure.

This function is used with the \(\texttt{-nosurf}\) option, which prevents mesh adaptation of the surface. To do so, boundaries triangles are given the \(\texttt{MG_REQ}\) tag, which indicates that the entity must not be modified, and the \(\texttt{MG_NOSURF}\) tag, which indicates that the \(\texttt{MG_REQ}\) was not given by the user, i.e. that it is not actually required. This allows for the removal of the tag if needed.

Additionally, when using parmmg, similar treatment is done when dealing with parallel triangles, which must not be modified when adapting subgroups of the mesh.

\(\texttt{MMG3D_hashTria}\)¶

int MMG3D_hashTria(MMG5_pMesh mesh, MMG5_Hash *hash)¶

Create surface adjacency table. Allocate the edge hash table hash but don’t free it.

Parameters:

mesh – pointer to the mesh structure.
hash – Edges hash table.

Returns:

1 if success, 0 if failed.

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

\(\texttt{MMG5_hGeom}\)¶

int MMG5_hGeom(MMG5_pMesh mesh)¶

Build hash table for initial mesh edges.

Parameters:: mesh – pointer to the mesh structure.
Returns:: 0 if failed, 1 otherwise

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 triangle structure.
Else, a hash structure is created for those special edges.

In both situations, the \(\texttt{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 \(\texttt{tag[i]}\) and \(\texttt{->edg[i]}\) fields of surface triangles.

\(\texttt{MMG5_setadj}\)¶

int MMG5_setadj(MMG5_pMesh mesh)¶

topology: set tria adjacency, detect Moebius, flip faces, count connected comp.

Remark

: as all triangles are mesh boundaries, we do not need to mark their adges as MG_BDY so the MG_BDY tag may be used inside geometrical triangles (external non-parallel, or internal parallel) to tag edges on the intersection with purely parallel (non-geometrical) triangles. The MG_PARBDYBDY tag is also added, as it does not have a supporting triangle to inherit this tag from.

Remark

REQ, NOSURF, etc… tags are added only inside xtetra.

Remark

In openbdy mode, all non-manifold edges are marked as opnbdy.

Parameters:: mesh – pointer towarad the mesh structure.
Returns:: 0 if fail, 1 otherwise.

This function travels the surface mesh by adjacency, and detects potential Mobius flips. Meanwhile, it sets the tags \(\texttt{MG_REF}\) and \(\texttt{MG_OPNBDY}\) by travelling the surface mesh and checking adjacencies.

\(\texttt{MMG5_setdhd}\)¶

int MMG5_setdhd(MMG5_pMesh mesh)¶: check for ridges: dihedral angle

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 a \(\texttt{MG_GEO}\) tag, and those between triangles with different references with a \(\texttt{MG_REF}\) tag.

\(\texttt{MMG5_setNmTag}\)¶

int MMG5_setNmTag(MMG5_pMesh mesh, MMG5_Hash *hash)¶

Set tags to non-manifold edges and vertices. Not done before because we need the MMG5_xTetra table.

Warning

if fail, the edge hash table hash is not freed.

Parameters:

mesh – pointer towar the mesh structure.
hash – edges hash table.

Returns:

1 if success, 0 if failed.