Mesh adaptation¶

This section describes the mesh adaptation process and the mesh modification operations related to it. The default version of the algorithm is performed by the following function:

int MMG5_mmg3d1_delone(MMG5_pMesh mesh,MMG5_pSol met,MMG5_int *permNodGlob);

The remeshing strategy in mmg3d relies on the intertwining of four local remeshing operations, namely:

Edge split: a new vertex is created and inserted on long edges, which are then split into two smaller edges. The underlying tetrahedra are split and updated accordingly.
Edge collapse: the endpoints of a short edge are merged and the underlying tetrahedra are updated accordingly.
Edge swap: the positions of the vertices are unaltered, but the connections of tetrahedra are modified.
Vertex relocation: one vertex is moved (and its connections are unaltered) with the aim to improve the quality of the mesh.

Below is a general overview of the remeshing procedure in mmg3d. There are three main stages:

At first, one relies on several iterations of the function $\texttt{MMG5_anatet(MMG5_pMesh mesh,MMG5_pSol met,int8_t typchk, int patternMode)}$, in that of the two possible modes identified by typchk = 1. This procedure encompasses a succession of (in this order):
- Boundary edge splits, performed by calling the function $\texttt{MMG3D_anatets}$,
- Internal edge splits, performed by $\texttt{MMG3D_anatetv}$,
- Edge collapses, via function $\texttt{MMG5_coltet}$,
- Edge swaps, thanks to functions $\texttt{MMG5_swpmsh}$ (for surface edge swaps) and $\texttt{MMG5_swptet}$ (for internal edge swaps).
Then, a metric is defined, and graded, thanks to the functions $\texttt{MMG3D_defsiz}$ and $\texttt{MMG3D_gradsiz}$. The resulting met field is defined at the vertices of $\texttt{mesh}$, and it contains the local size prescription at these entities.

A second round of iterations of the function $\texttt{MMG5_anatet}$ is carried out, with the argument typchk = 2. This indicates that the remeshing operators described above are triggered based on the local size prescribed by met (e.g. the notions of long and short edge).
Finally, one last round of iterations is carried out, using the function $\texttt{MMG5_adptet_delone}$. Vertex relocations are introduced in this step for quality enhancement.

Edge split¶

The location of the inserted vertex depends on the geometric nature of the split edge:

During $\texttt{MMG5_anatet}$ calls, splitting operations are performed by several functions, depending on the parameters: in isotropic mode, $\texttt{MMG3D_anatets_iso}$ is called, whereas $\texttt{MMG3D_anatets_ani}$ is called in anistropic mode. Both of these functions deal with splitting of surface tetrahedra. Additionally, in pattern mode, i.e. in the mode that uses pattern strategies to perform splittings (opposed to the default mode, which resorts to the Delaunay kernel), function $\texttt{MMG3D_anatetv}$ is called as well, to deal with internal tetrahedra splits.

During the two calls to $\texttt{MMG5_anatet}$, length criterion depends on whether it is the first or second call. During the first call, function $\texttt{MMG3D_anatets_iso}$ procedes as follows:

At first, a loop over all the elements is performed in order to flag all the edges that are too long,

Edge collapse¶

The edge collapse operation is perhaps the most delicate one of the four. It operates on an edge $\texttt{nump-numq}$ of the mesh, and merges $\texttt{nump}$ onto $\texttt{numq}$, as illustrated below in two dimensions. As a result:

All the tetrahedra in the shell of $\texttt{nump-numq}$ (i.e. those tetrahedra containing $\texttt{nump}$ and $\texttt{numq}$ as vertices) disappear.
All the tetrahedra in the ball of $\texttt{nump}$, and not in the shell of $\texttt{nump-numq}$ (i.e. those tetrahedra containing $\texttt{nump}$ but not $\texttt{numq}$ as vertex) have $\texttt{nump}$ replaced by $\texttt{numq}$.

../../_images/collex.webp — In two space dimensions, collapse of point $\texttt{nump}$ onto $\texttt{numq}$: the red elements in the shell of $\texttt{nump-numq}$ disappear, and the vertex $\texttt{nump}$ is replaced by $\texttt{numq}$ in the elements in the ball of $\texttt{nump}$.¶

All edges of the mesh are travelled and analyzed to see if collapse is suitable, using function:

static int MMG5_coltet(MMG5_pMesh mesh,MMG5_pSol met,char typchk)

Again, two modes are available, depending on whether $\texttt{typchk}$ equals 1 (in which case, short edges are identified according to their length with respect to the input parameter $\texttt{hmin}$) or 2 (when the length is calculated with respect to the size prescriptions in $\texttt{met}$).

Several checks are in order when it comes to collapsing one point onto another. When a boundary edge (identified by a tetrahedron $\texttt{k}$, a face $\texttt{iface=0,1,2,3}$ in $\texttt{k}$ and an edge $\texttt{iedg=0,1,2}$ on this face) is collapsed, checks are performed thanks to the function

int MMG5_chkcol_bdy(MMG5_pMesh mesh,MMG5_pSol met,int k,char iface,
                  char iedg,int *listv,int ilistv,int *lists,int ilists,
                  char typchk)

This function starts by reordering the surface ball $\texttt{lists}$ via the call of:

MMG5_startedgsurfball(mesh,nump,numq,lists,ilists);

in such a way that the first element (l=0) and last element (l=\texttt{ilists-1}) contain the collapsed edge $\texttt{nump}-\texttt{numq}$ (and are thus those surface triangles vanishing in the process).

Then, this function performs the following verifications:

For all the tetras of the shell of the collapsed edge, it should not happen that either all four faces of the tetrahedron are boundary, or that the two identified faces via the collapse are boundary, as illustrated below:

../../_images/collshell.webp — (Left) If the two merged faces in the shell tetrahedron $\texttt{nump-numq-ipa-ipb}$ are boundary, collapse should be prevented; (right) If one of the two merged faces (in white) is not boundary, this phenomenon does not show up, even if the other three faces are boundary.¶

Tetras in the ball of $\texttt{p}$, outside the shell of $\texttt{pq}$, are required not to get four boundary vertices as a result of the collapse;
The Jacobian of the newly created elements stays positive (actually, the quality of the resulting elements is not too much degraded);
Several tests are carried out concerning the surface ball of the collapsed point $\texttt{p}$:
- The angle between the normal vector to each face (but for the two disappearing) before collapse ($\texttt{ncurold}$) and after collapse ($\texttt{ncurnew}$) should be less than $90^\circ$ (no flipping).
- For each face $l=1,\cdots,\texttt{ilists}$ in the surfacic ball, the deviation between the normal vector to the previous face $l-1$ ($\texttt{nprvold}$ or $\texttt{nprvnew}$) and that to $l$ ($\texttt{ncurold}$ or $\texttt{ncurnew}$) should not be increased too much.
- The update triangles $l=1,\cdots,\texttt{ilists-2}$ do not show a too large degradation of the geometric approximation of the support.

Aside from these checks, several additional verifications are conducted to deal with the surface triangles gathered in the list $\texttt{lists}$. Note that these are only external surface triangles (so that the degradation over the geometric approximation of the implicit boundary joining at the collapsed edge is not monitored). Notably, in the $\texttt{-ls}$ option, the following function is called

int MMG5_chkmanicoll(MMG5_pMesh mesh,int k,int iface,int iedg,int ndepmin,
                      int ndepplus,char isminp,char isplp);

Outside from the $\texttt{-ls}$ option, the following function is called:

MMG5_topchkcol_bdy(MMG5_pMesh mesh,int k,int iface,char iedg,int *lists,int ilists);

Here,

the collapse of the edge $\texttt{iedg} = 0,1,2 $ on the face $\texttt{iface}=0,1,2,3$ of tetra $\texttt{k}$ is considered. More precisely, $\texttt{nump}$ is collapsed on $\texttt{numq}$ (see illustration below).
The surfacic ball of $\texttt{nump}$ is provided and it is assumed that the two vanishing faces in the collapse are $\texttt{lists[0]}$ and $\texttt{lists[ilists-1]}$ (typically, the function $\texttt{MMG5_startedgsurfball}$ has been called previously).

../../_images/topchkcol.webp — Configuration assumed by the function $\texttt{MMG5_topchkcol_bdy}$.¶

This function then checks that:

The points $\texttt{nap}$ and $\texttt{naq}$ are different, and that so are the points $\texttt{nbp}$ and $\texttt{nbq}$ (i.e. there is no small bubble of void).
The deviation between the normal vectors of $\texttt{nap-numq-nro}$ and $\texttt{numq-naq-nro}$ is not much larger than that between $\texttt{nump-numq-nro}$ and $\texttt{numq-naq-nro}$ (and similarly for the configuration next to $\texttt{lists[ilists-1]}$).

Edge swap¶

Vertex relocation¶

The vertex relocation procedure is called by $texttt{MMG5_adptet_delone}. It is achieved by the function:

int MMG5_movtet(MMG5_pMesh mesh,MMG5_pSol met, MMG3D_pPROctree PROctree,
              double clickSurf,double clickVol,int moveVol, int improveSurf,
              int improveVolSurf, int improveVol, int maxit,int testmark)

Essentially, this function travels all the vertices in $\texttt{mesh}$ by travelling all the tetrahedra $(\texttt{k=1,...,mesh$\to$ne})$, all the faces ($\texttt{i=0,...,3}$), and the three vertices of each face $(\texttt{j=0,...,2})$ and calls a particular procedure depending on the geometric nature of the vertex ($\texttt{MG_NOM}$, $\texttt{MG_GEO}$, etc.).