Infinite loop in ETManifoldMesh::GetBoundaryPolygons()

[here-abarany]

After upgrading from GTE 6.5, I have encountered infinite loops in ETManifoldMesh::GetBoundaryPolygons(). This appears to have regressed in commit dfafe0e90ef3fcd7b13c21e8ac6e706a6ffc151e "Modifications and new files for 2-manifold and 3-manifold meshes."

An example test case is as follows:

    std::vector<std::uint32_t> indices =
    {
        1, 2, 3,
        0, 1, 3,
        6, 1, 0,
        5, 6, 0,
        4, 5, 0,
        7, 5, 4,
        6, 5, 7,
        10, 6, 7,
        11, 6, 10,
        9, 6, 11,
        8, 9, 11,
        13, 15, 14,
        16, 9, 8,
        15, 9, 16,
        12, 15, 16,
        13, 12, 17,
        14, 13, 17,
        19, 14, 17,
        18, 19, 17,
        21, 19, 18,
        20, 21, 18,
        2, 21, 20,
        3, 2, 20,
    };

    gte::ETManifoldMesh manifoldMesh;
    for (std::size_t i = 0; i < indices.size()/3; ++i)
        manifoldMesh.Insert(indices[i*3], indices[i*3 + 1], indices[i*3 + 2]);

    std::vector<std::vector<int>> boundaries;
    manifoldMesh.GetBoundaryPolygons(boundaries, false);

The previous behavior appears to have been a single boundary with all indices.

For context, this is known to be an invalid mesh, and is immediately obvious when viewing the output in a modeling program. This is output from a mesh generation algorithm that is known to fail in a small percentage of cases, and the results of the manifold mesh are used as one factor to determine whether the algorithm succeeded or failed. Using GTE 6.5 and earlier we are able to correctly flag the output as invalid after inspecting the manifold mesh.

[davideberly]

Apologies for not responding immediately, on site with a client. Thank you for reporting this. I will look into it.

[davideberly]

The modification from GTE 6.5 to GTE 6.6 is where the behavior changed. The update history for January 17, 2023 (Gte6UpdateHistory.pdf) mentions the change was based on a mesh for which GetBoundaryPolygons failed (when I ported the GTE code to GTL and added GTL-based unit tests). It appears that you have been relying on behavior from GetBoundaryPolygons to flag invalid meshes, but you have been lucky in that no failures occurred in this function for those meshes.

In the example you provided, I do not have your vertices to visualize, but I sketched an example based on the topology. In 2D, my sketch shows that triangle <14,13,17> has winding order opposite that of the other triangles. In 3D, my sketch shows that you have a nonorientable mesh (looks like a Moebius strip). Detecting a nonorientable mesh is a global topological concept--you cannot determine from a single triangle insertion whether you have created a nonorientable mesh (i.e. each insertion has only local information about the topology).

In both GTE 6.5 and GTE 6.6, after you insert the triangles into manifoldMesh, make the call "bool isOrientable = manifoldMesh.IsOriented();" In either version, the return value is 'false', so the mesh it not orientable. Perhaps you can use this test to flag an invalid mesh and not make the call to GetBoundaryPolygons(); however, there might be other invalid meshes you encounter which are not due to orientability?

The IsOriented() function essentially tries to create a consistent winding order for the mesh. For a nonorientable mesh, it finds this out only by starting with a triangle of one winding order and follows a path of triangles that returns to the starting triangle. All triangles along the path have the same winding order as the starting triangle, but when the path gets back to the starting triangle, the winding order of the penultimate triangle is inconsistent with that of the starting triangle.

[here-abarany]

Thanks, some initial testing seems to show that calling IsOriented() avoids the infinite loop and doesn't introduce any false positives for my test cases. I'll have to keep an eye on it when we have a chance to update GTE and run at scale.

however, there might be other invalid meshes you encounter which are not due to orientability?

Yes, we expect at least one of the extracted polygons to be at a specific height. If there are no polygons at that height, or some vertices within a candidate polygon are at a different height, then we discard it as a failure. I'm also not entirely sure all non-manifold meshes would be non-oriented.

When I originally stated that the resulting polygons were only used for error checking, I was confusing it with another part of the algorithm: we are actually using the resulting boundary polygons for other operations beyond error checking.

As for failure cases with the newer implementation, if it fails with an assertion exception that's fine on our end: we catch the exception, log the failure, and execute a fallback same as if one of the explicit checks flags an invalid case. However, an infinite loop poses a major problem as we are unable to continue execution. How confident are you that the non-oriented case is the only one that would initiate the infinite loop? Are there some additional checks that could be done in GetBoundaryPolygons() to detect an infinite loop and throw an assertion instead?

[davideberly]

The mesh can be nonmanifold if there is at least one edge that is shared by 3 or more triangles. This is a local property, and the Insert call throws an exception (as long as you have mThrowOnNonmanifoldInsertion set to 'true').

I need to review the new implementation of GetBoundaryPolygon() to determine what happens if you have a vertex shared by multiple triangles but the union of the triangles is not a polygon. For example a bow-tie formed from two triangles is not a manifold mesh. Using the terminology of Triangle Meshes: Summary, a bow-tie does not satisfy the edge-connected property.

I will modify GetBoundaryPolygon() to detect the infinite loop and throw an exception. My schedule will not allow me to get to this until next week.

[here-abarany]

Thanks! There's no rush on our end, we can continue to use the older version until we're confident that a newer version won't hit an infinite loop.

[davideberly]

I posted a modification that traps the infinite loop.

During the analysis, I noticed that ETManifoldMesh::Insert will decide that two triangles share an edge that is "unordered" (EdgeKey, the value v[0] < v[1] is ensured). The design of ETManifoldMesh was to allow you to insert any triangles, and I provided the ability to make the winding order consistent (if possible). In your example, triangle <13,15,14> is inserted. Later triangle <14,13,17> is inserted. The two triangles share the "unordered" edge <13,14> because the ETManifoldMesh::Insert function allows this. However, both triangles have ordered edges <14,13> which leads to nonmanifold (shared edge in manifold mesh needs one ordered edge <v0,v1> and one ordered edge <v1,v0>).

Perhaps this choice needs to be revisited. Options: (1) Keep the current behavior. (2) Do not share the edge and do not throw. This prevents nonorientability which means several ETManifoldMesh function members can be removed. (3) Do not share the edge but throw. This means if you thought your triangles form a manifold mesh, they do not. But now you have to do a try-catch when calling the Insert function.

If you have a preference, please let me know.

[here-abarany]

Thanks for the update.

Option 3 sounds like the best choice in my opinion. Unless there's a large performance penalty, if you're attempting to create a non-manifold mesh then I think it's best to be alerted as soon as possible. Option 1 is still fine for our use case, but I'm not sure if there are other use cases that could end up with non-manifold meshes but not have another operation fail.

Option 2 sounds like it would silently drop invalid triangles, which I think shouldn't be done. This could make it so callers don't know they are providing invalid output, and cause unexpected behavior as a result.

[davideberly]

I will modify the code to use Option 3. There is no performance penalty, just a comparison of the vertex indices that form the edge.

[davideberly]

I added option 3 to ETManifoldMesh.h (on November 20). If an edge in the mesh is <v0,v1> and if it occurs because of an adjacent triangle, then the adjacent triangle edge should be <v1,v0>. The default behavior of the class has been to throw an exception if 3 or more triangles share a (unordered) edge. Now it also throws an exception if 2 triangles share an edge and the ordered edge is the same for the two triangles (which is nonmanifold).

[owai1980]

Since this commit, i have problems doing the triangulateCDT ()...

Indeed it now throws exception... And doesn't do the job anymore.

I'm still trying to understand... But today i reverted to the previous commit, waiting to have time to understand.

Le dim. 3 déc. 2023 à 01:26, David Eberly @.***> a écrit :

I added option 3 to ETManifoldMesh.h (on November 20). If an edge in the mesh is <v0,v1> and if it occurs because of an adjacent triangle, then the adjacent triangle edge should be <v1,v0>. The default behavior of the class has been to throw an exception if 3 or more triangles share a (unordered) edge. Now it also throws an exception if 2 triangles share an edge and the ordered edge is the same for the two triangles (which is nonmanifold).

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/71#issuecomment-1837291290, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQJ5NFRLC4EAOIUGITTYHPBJVAVCNFSM6AAAAAA4MHW5M2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZXGI4TCMRZGA . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[davideberly]

Just to be certain, are you using TriangulateCDT that is NOT marked as "deprecated"? If you have the time, please provide me with a dataset for which the exceptions are thrown. That will help me diagnose any side effects that occur because of the new code.

The change to ETManifoldMesh.h involved only a few lines of code. You can turn off the nonmanifold exception: ETManifoldMesh mesh{}; mesh.ThrowOnNonmanifoldInsertion(false);

[owai1980]

Thank you for your reply...

Tomorrow i will investigate more and try to provide you a dataset (btw, it is still the same data as last time...)

I will answer your questions too.

Le dim. 3 déc. 2023 à 17:42, David Eberly @.***> a écrit :

Just to be certain, are you using TriangulateCDT that is NOT marked as "deprecated"? If you have the time, please provide me with a dataset for which the exceptions are thrown. That will help me diagnose any side effects that occur because of the new code.

The change to ETManifoldMesh.h involved only a few lines of code. You can turn off the nonmanifold exception: ETManifoldMesh mesh{}; mesh.ThrowOnNonmanifoldInsertion(false);

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/71#issuecomment-1837534547, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQKGWRXSUZ7IFEFUZKLYHSTY3AVCNFSM6AAAAAA4MHW5M2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZXGUZTINJUG4 . You are receiving this because you commented.Message ID: @.***>

[davideberly]

I deal with a lot of issues and folks using the code, so I do not know which dataset you are referring to with "btw, it is still the same data as last time". I browsed the closed issues, but I must be missing which one has your "same data as last time".

Yes, having a dataset will be useful.

For now, unless there are objections from folks using this code, I will roll back ETManifoldMesh.h to its previous state. I need to investigate whether GTE some classes that use ETManifoldMesh.h allow building a manifold mesh but without consistent triangle winding order.

[davideberly]

I found the dataset, in the open issue for TriangulateEC. I was searching for closed issues involving TriangulateCDT. I am able to generate the exceptions in the test program I used for this dataset.

[owai1980]

sorry that i wasn't clear.

thank you again for testing my problems so quickly!

to answer your previous questions: i WAS using the deprecated version of triangulateCDT. Now i'm using triangulateCDT and the problem is still present.

ok.. so if you can reproduce... i hope you will find a solution. no pressure from me ya ;-)

Johan

[owai1980]

one more information: in my dataset there are 1 "outer" and many inners. i think the problem exists even without the inners.

[davideberly]

Yes, the problem occurs without the inner polygons. In either case, something is wrong with the edge and triangle indices in the comparison that throws the exception. These occur when I add the "insertion polygon" to the graph in Delaunay2. I had tested using meshes not built from Delaunay triangulation. Yet another example of my failing to have insufficient testing.

[owai1980]

don't blame yourself... you do a wonderful job, and i'm sure you'll understand the reason!

[davideberly]

Thanks for the comment, but I am to blame. Just not enough testing. The problem had to do with the comparison of the directed edge indices. It was slightly more complicated than the code I had pushed before. I pushed the fix.

[owai1980]

I will test it right now!

Thanks

Le mar. 5 déc. 2023 à 01:49, David Eberly @.***> a écrit :

Thanks for the comment, but I am to blame. Just not enough testing. The problem had to do with the comparison of the directed edge indices. It was slightly more complicated than the code I had pushed before. I pushed the fix.

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/71#issuecomment-1839812111, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQI63VFNRDSNKW2W4ETYHZVTDAVCNFSM6AAAAAA4MHW5M2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZZHAYTEMJRGE . You are receiving this because you commented.Message ID: @.***>

[owai1980]

Perfect!

Thank you... Again! 👍

Le mar. 5 déc. 2023 à 08:16, Johan Miller @.***> a écrit :

I will test it right now!

Thanks

Le mar. 5 déc. 2023 à 01:49, David Eberly @.***> a écrit :

Thanks for the comment, but I am to blame. Just not enough testing. The problem had to do with the comparison of the directed edge indices. It was slightly more complicated than the code I had pushed before. I pushed the fix.

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/71#issuecomment-1839812111, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQI63VFNRDSNKW2W4ETYHZVTDAVCNFSM6AAAAAA4MHW5M2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMZZHAYTEMJRGE . You are receiving this because you commented.Message ID: @.***>