Simple example that causes MMG to crash and freeze

[kraft]

I am investigating a class of simple graphs which cause MMG to freeze, crash, and fail. I’m more interested in solving the freezing case if it matters; as it requires Task Manager to end the process.

The graphs all follow a similar format:

• I’m using the MMG2D api, MMG2D_mmg2dmesh(mesh, solution)
• input graph contains only vertices and edges
• all vertices and edges are marked as “required”.

I have hundreds of other tests which run MMG2D_mmg2dmesh which work fine. What seems to be unique about these cases is the presence of simple edge loops (triangles) intended to remain intact, and the issue seems to be when they are enclosed interior to other polygons.

The difference between these is the addition of two more collinear vertices. Collinear vertices do not cause a freeze, they are present in both. Rest assured, the polygons are simple and edges are well formed. Here is another similar example:

Again, two more collinear vertices in B2 from B1 causes a freeze. The move from B3 and B4 is interesting because there is a clue in the debug logs regarding the edge that cuts through the small square. In B1/B2/B3, this edge is interior, and B4 it’s exterior. I only get logs for B1 and B4, not B2 or B3 because of freezing/crashing. Notice the log is complaining about edge (7 9)- this is that same edge- the edge cutting across the smaller inner square.

Here’s the input graph and the logs for B1. You can see the 8th edge connects vertices (7 9).

std::vector<double> v { -2, -2, 2, -2, 2, 0, 2, 2, -2, 2, -2, 0, -1, 0, 0, -1, 1, 0, 0, 1 };
std::vector<int> e {
	1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 1,
	6, 7, 7, 9, 9, 3,
	7, 8, 8, 9, 9, 10, 10, 7
};
std::vector<int> reqV{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector<int> reqE{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 };

B1 log:

  ## Warning: MMG2D_bdryenforcement: at least 1 missing edge (7 9).
  ## Error: MMG2D_locateEdge: unexpected failure. Check your initial data and/or report the bug. lon:1. 0.000000e+00 2.500000e-01 5.000000e-01
 tria 4: 6 5 12,
  ## Error: MMG2D_bdryenforcement: at least 1 edge not found.
  ## Error: MMG2D_mmg2d2: unable to enforce the boundaries.
  ## Warning: MMG2D_pack: unexpected edge table... Ignored data.
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
   MODULE MMG2D: 5.8.0 (Oct. 30, 2024)
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  -- MMG2DMESH: INPUT DATA
  --  INPUT DATA COMPLETED.     0.000s
  MAXIMUM NUMBER OF POINTS    (NPMAX) :    50000
  MAXIMUM NUMBER OF TRIANGLES (NTMAX) :   100000
  -- PHASE 1 : MESH GENERATION
           10 vertex inserted        0 not inserted
     unable to insert        0 vertex : cavity        0 -- delaunay        0 
            0 vertex inserted        0 not inserted
     unable to insert        0 vertex : cavity        0 -- delaunay        0 
     Insertion succeed
 ** number of missing edges : 1
  -- edge enforcement 7 9
 Try to enforce edge 7 9
     NUMBER OF VERTICES             14   CORNERS        0
     NUMBER OF TRIANGLES            22
     NUMBER OF EDGES                 4
  %% files/crash-test-horizontal-fails.msh OPENED

B4 is a success, it’s log is uneventful.

  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
   MODULE MMG2D: 5.8.0 (Oct. 30, 2024)
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  -- MMG2DMESH: INPUT DATA
  --  INPUT DATA COMPLETED.     0.000s
  -- PHASE 1 : MESH GENERATION
     Insertion succeed
            2 sub-domains
  -- PHASE 1 COMPLETED.     0.000s
  -- PHASE 2 : ANALYSIS
  -- PHASE 2 COMPLETED.     0.000s
  -- PHASE 3 : MESH IMPROVEMENT (ISOTROPIC)
  -- GRADATION : 1.300000 
  -- PHASE 3 COMPLETED.     0.000s
  -- MESH QUALITY   7
     BEST   0.866025  AVRG.   0.767051  WRST.   0.692820 (1)
     HISTOGRAMM:  100.00 % > 0.12
  -- MESH PACKED UP
     NUMBER OF VERTICES              8   CORNERS        5
     NUMBER OF TRIANGLES             7
     NUMBER OF EDGES                 9
   MMG2DMESH: ELAPSED TIME  0.000s
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
   END OF MODULE MMG2D
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  %% files/crash-test-half-horizontal-success.msh OPENED

Can someone explain what exactly is going on when MMG says MMG2D_bdryenforcement: at least 1 missing edge (7 9) (the first line in B1’s log). I feel like this must be related to the issue where MMG freezes, but do you have any further ideas why?

Happy to share anything else or try any of your ideas, thank you!

[kraft]

Reposting this because I had a typo, sorry! (I called MMG2D_Set_meshSize with v.size() for edges instead of e.size())

Here is the above case which freezes as a C++ function. I’ve now tested on Mac and Windows.

int TestMMGFreezeIssue() {
	std::vector<double> v {
		// origin-centered square, side length 4, with 4 corner vertices and 4 side-midpoint vertices
		-2, -2, 0, -2, 2, -2, 2, 0, 2, 2, 0, 2, -2, 2, -2, 0,
		// an interior 45deg rotated square (diamond shape)
		-1, 0, 0, -1, 1, 0, 0, 1
	};
	std::vector<int> e {
		// 8 edges around the boundary of the outer square
		1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 1,
		// 3 edges to cut a horizontal line through the middle of the square
		8, 9, 9, 11, 11, 4,
		// 4 edges to form the interior diamond shape
		9, 10, 10, 11, 11, 12, 12, 9
	};

	// initialize
	MMG5_pMesh mesh = nullptr;
	MMG5_pSol solution = nullptr;
	if (!MMG2D_Init_mesh(MMG5_ARG_start,
		MMG5_ARG_ppMesh, &mesh,
		MMG5_ARG_ppMet, &solution,
		MMG5_ARG_end)) { return 10; }

	// fill mesh
	if (!MMG2D_Set_meshSize(mesh, (int32_t)(v.size() / 2), 0, 0, (int32_t)(e.size() / 2))) { return 11; }
	if (!MMG2D_Set_vertices(mesh, v.data(), nullptr)) { return 12; }
	if (!MMG2D_Set_edges(mesh, e.data(), nullptr)) { return 13; }

	// all vertices and edges are set to required
	int reqV = 1;
	for (int i = 0; i < v.size() / 2; i += 1) { reqV &= MMG2D_Set_requiredVertex(mesh, i + 1); }
	if (!reqV) { return 15; }
	int reqE = 1;
	for (int i = 0; i < e.size() / 2; i += 1) { reqE &= MMG2D_Set_requiredEdge(mesh, i + 1); }
	if (!reqE) { return 16; }

	// parameters
	MMG2D_Set_iparameter(mesh, solution, MMG2D_IPARAM_debug, 1);
	MMG2D_Set_iparameter(mesh, solution, MMG2D_IPARAM_verbose, 10);

	// optionally, set a target size. this is not needed
	// MMG2D_Set_dparameter(mesh, solution, MMG2D_DPARAM_hsiz, 0.2);

	// if required edges are included, we have to ask the mesher to not allow these
	// edge lengths to influence the size of other edges.
	MMG2D_Set_iparameter(mesh, solution, MMG2D_IPARAM_nosizreq, 1);
	MMG2D_Set_dparameter(mesh, solution, MMG2D_DPARAM_hgradreq, -1);

	// create the initial mesh
	int mesherResult = MMG2D_mmg2dmesh(mesh, solution);
	if (mesherResult == MMG5_STRONGFAILURE) { return 1; }
	if (mesherResult == MMG5_LOWFAILURE) { return 2; }
	// if (!MMG2D_Chk_meshData(mesh, solution)) { return 3; }

	// write result to file
	MMG2D_saveMshMesh(mesh, nullptr, "test-mmg-freeze-issue.msh");

	// free memory
	if (!MMG2D_Free_all(MMG5_ARG_start,
		MMG5_ARG_ppMesh, &mesh,
		MMG5_ARG_ppMet, &solution,
		MMG5_ARG_end)) { return 22; }
	return 0;
}

[kraft]

I’m gaining a little more insight now running the process through a debugger.

Sending a SIGSTOP after it freezes always halts in file enforcement_2d.c in function MMG2D_bdryenforcement at line 212 which is itself inside of a couple loops:

188:   while ( ilon > 0 ) {
...
206:     for (i=0; i<3; i++) {
...
212:       if ( pt1->base != (mesh->base+1) ) continue

here is the terminal output that prints before the freeze.

Process 22241 launched: '/Users/Maya/Code/mmg/build/tests/a.out' (arm64)

  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
   MODULE MMG2D: 5.8.0 (Oct. 30, 2024)
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
     git branch: master
     git commit: 4d8232c8aebfed877935d75d4d4a67e850962422
     git date:   2024-10-29 11:41:45 +0100


  -- MMG2DMESH: INPUT DATA
  --  INPUT DATA COMPLETED.     0.000s
  MAXIMUM NUMBER OF POINTS    (NPMAX) :    50000
  MAXIMUM NUMBER OF TRIANGLES (NTMAX) :   100000

  -- PHASE 1 : MESH GENERATION
     After truncature computation:   hmin 0.004000 (user setted 0)
                                     hmax 8.000000 (user setted 0)
           12 vertex inserted        0 not inserted
     unable to insert        0 vertex : cavity        0 -- delaunay        0
            0 vertex inserted        0 not inserted
     unable to insert        0 vertex : cavity        0 -- delaunay        0
     Insertion succeed

  ## Warning: MMG2D_bdryenforcement: at least 1 missing edge (9 11).
 ** number of missing edges : 1

  -- edge enforcement 9 11
 Try to enforce edge 9 11

  ## Warning: MMG2D_bdryenforcement: few edges... 1

here is the debugger output after halting the process:

Process 22241 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
    frame #0: 0x000000010005a0a0 a.out`MMG2D_bdryenforcement(mesh=0x0000000125f04388, sol=0x0000600000f30008) at enforcement_2d.c:212:36
   209 	          /* Check the adjacent triangle in the pipe */
   210 	          adj = adja[ir] / 3;
   211 	          pt1 = &mesh->tria[adj];
-> 212 	          if ( pt1->base != (mesh->base+1) ) continue;
   213
   214 	          /* Swap edge ir in triangle k, corresponding to a situation where both triangles are to base+1 */
   215 	          if ( !MMG2D_swapdelone(mesh,sol,k,ir,1e+4,list2) ) {
Target 0: (a.out) stopped.

and again here is the input mesh

I would also be interested in a stopgap- if there is a way to infer that this issue might happen before calling the mesher, I can tell MMG to refuse to process meshes like this one. Maybe it’s meshes which have this “missing edges” property.

[cprigent]

Hello,

Thank you very much for your question. It appears that there is a bug in the procedure of generating the mesh.

When mmg is called to generate a 2D mesh, it will first create the points of the bounding box. Then, it will insert all the points given by the user, regardless of the provided edges. This is done by calling the function MMG2D_insertpointdelone and produces the following mesh:

As you noticed, a function named MMG2D_bdryenforcement is then called to properly enforce the edges given by the user. As you can see, the edge 9 - 11 is not included in the mesh yet, and mmg will attempt to enforce its presence.

To do so, mmg needs to identify all the triangles that will be intersected by the edge 9 - 11. In this case, there are two of them (9 - 12 - 10 and 10 - 11 - 12). However, the procedure does not correctly identify that there are two triangles. The consequence of this miscalculation is that it produces an infinite loop.

I have identified where the problem precisely occurs. I will fix this issue in mmg shortly.

Kind regards,
Corentin

[cprigent]

Hello again,

I have created a patch that you may apply to the sources of mmg in order to correct your problem. Up to the tests I have performed, it seems to solve the problem of freezes.
I will merge this modification in the develop branch of mmg to acknowledge this modification permanently.
Please do not hesitate to come back to me if there are still some problems that you encounter.

I thank you again for your contribution to mmg.

Kind regards,
Corentin

fix-bdry-enforcement.patch (790 Bytes)

[kraft]

Hello Corentin,
I applied your patch, rebuilt MMG, and the above example worked!
Thank you so much for looking into it and finding a fix so quickly!
Later this week I will also test the additional cases that I previously found and in case there are any errors I will follow up here.
Thanks again and take care,
-Maya