Flipped triangles when simplifying mesh

[andreiKDI]

Hi!
First of all, thank you for working on this great tool, much appreciated! 👍

I'm trying to simplify some terrain tiles which are basically just grids with a bit of elevation. The problem is that sometimes, the simplification process generates weird meshes, with some triangles flipped, others overlapping and some very thin. You can see all three of them in the "after.obj" attached.
Here's the code I use for simplifying the mesh, although the same happens without the index and vertex remapping, just that the buffers will be bigger. Also, I tried tweaking the threshold and targetError, with similar results.

    // Simplify mesh
    float threshold = 0.2f;
    size_t targetIndexCount = size_t(indexes.size() * threshold);
    float targetError = 1e-2f;

    indexes.resize(meshopt_simplify(indexes.data(), indexes.data(), indexes.size(), &(positions[0].x), positions.size(), sizeof(glm::vec3), targetIndexCount, targetError, nullptr));

    std::vector<unsigned int> vertexRemap(positions.size());
    size_t newVertSize = meshopt_optimizeVertexFetchRemap(vertexRemap.data(), indexes.data(), indexes.size(), vertexRemap.size());
    vertexRemap.resize(newVertSize);

    meshopt_remapIndexBuffer(indexes.data(), indexes.data(), indexes.size(), vertexRemap.data());
    meshopt_remapVertexBuffer(positions.data(), positions.data(), positions.size(), sizeof(glm::vec3), vertexRemap.data());
    meshopt_remapVertexBuffer(texCoords.data(), texCoords.data(), texCoords.size(), sizeof(glm::vec2), vertexRemap.data());
    positions.resize(newVertSize);
    texCoords.resize(newVertSize);

Here you can find the before and after meshes with the fewest grid cells I could reproduce the problem with and without normals, uvs etc: Desktop.zip

I briefly tried to debug the problem myself, but it wasn't obvious to me what happens there. Please let me know if you need more details.

[zeux]

Sorry it took so long, I just resumed working on various simplification backlog items, this being one of them. Unfortunately I'm now having trouble reproducing the results :(

Could you clarify:

• which version of meshoptimizer are you using
• which compiler you're using to build meshoptimizer; in particular whether you're using any special floating point optimization settings such as -ffast-math//fp:fast
• whether you can reproduce the problem in gltfpack by running gltfpack -i after.obj -o new.glb -si X, X being the simplification factor, with your version / compiler?

Sometimes the .obj preprocessing in gltfpack obscures the bugs but it doesn't seem to be the problem here, and I tried running gltfpack in a special mode where the index/vertex buffers from the input are preserved and still can't reproduce this.

[kristoffer-dyrkorn]

It seems I am able to reproduce this bug (ie overlapping triangles) using gltfpack 0.17 on macos (binary downloaded from here: https://github.com/zeux/meshoptimizer/releases/tag/v0.17) and also the latest built npm-based gltfpack (the artifact from here: https://github.com/zeux/meshoptimizer/actions/runs/2531821310, ie https://github.com/zeux/meshoptimizer/suites/7014049981/artifacts/275430512).

Command line (and output) was:
./gltfpack -v -noq -si 0.2 -i test.obj -o test.glb
input: 0 nodes, 0 meshes (1 primitives), 0 materials, 0 skins, 0 animations
input: 1 mesh primitives (4802 triangles, 14406 vertices); 1 draw calls (1 instances, 4802 triangles)
output: 1 mesh primitives (959 triangles, 509 vertices); 1 draw calls (1 instances, 959 triangles)
output: 1 nodes, 1 meshes (1 primitives), 0 materials
output: JSON 552 bytes, buffers 11864 bytes
output: buffers: vertex 6108 bytes, index 5754 bytes, skin 0 bytes, time 0 bytes, keyframe 0 bytes, instance 0 bytes, image 0 bytes

Please see attached file for screenshots and obj file used as input:
files.zip

[happyfrank]

I tested a small model and it still seems to have this problem -.-
version: version 0.18
void simplify(const Mesh& mesh, float threshold = 0.2f)
test_mesh

[zeux]

@happyfrank would you mind attaching the example to this issue as a .zip file? The link is not reachable.

[happyfrank]

@zeux Certainly, I can confirm that the link is now working and you can access the example.
Please try accessing it again and let me know if you encounter any issues. test_mesh

[zeux]

@happyfrank I can download this now, but I'm having trouble locating the geometry with the overlap in Blender in the simplified scene, and unfortunately MeshLab (which I think the screenshot is from) crashes when trying to open it :-/ If you could upload a separate .obj file with just the geometry with the overlap shown in the screenshot, that would help - I'd normally be able to cut it out myself but I can't quite understand what portions of the screenshot correspond to what objects in the original scene as well :) as it's very chaotic.

[happyfrank]

@zeux I apologize for the confusion earlier. I have created a new .obj file with just the overlapping geometry shown in the screenshot, and you can download it from here: test_mesh2 I also simplified the model to make it easier to work with. Let me know if you have any further questions or concerns.
version: version 0.18
void simplify(const Mesh& mesh, float threshold = 0.2f)

[zeux]

Perfect, thanks! I can reproduce this on that file now. Reuploading the file so that it is attached to the issue:
mesh_flip.zip

[zeux]

#698 has another example of this problem; I thought it would be useful to comment here on the specific sequence of steps that can lead to this.

During edge collapses, the simplifier doesn't collapse edges when the edge collapse will lead to flipping of the orientation of an individual triangle. Unfortunately, there are cases where a triangle can still be flipped.

In this sequence, a mesh is simplified in a sequence of edge collapses; green arrows represent a set of "normal" collapses, a red arrow represents a single problematic edge collapse (the edge that is collapsed is highlighted).

In this case, there's one problematic collapse (first one) that results in production of a fairly thin triangle. The triangle is produced by moving the vertex of another triangle, and this movement is just barely keeping the triangle in the original triangle's half space -- the angle between the original triangle and the new triangle is almost 90 degrees (the dot product of normals is ~0.03 => 88 degree angle). The area of the triangle that the collapse produces is ~10x smaller. The triangle is highlighted in blue.

After this, one of the vertices of the new triangle can be moved to rotate the triangle again, this time the rotation is less severe (dot product ~0.2 => 78 degree angle). The area grows by 10x during this collapse, and the thin triangle grows to the large flipped triangle (highlighted in blue).

There are some cases I've debugged in the past where the problem occurs as a result of a longer sequence of collapses, where a triangle is rotated by less than 70-80 degrees gradually, but this is not as common. Right now the cutoff is exactly 90 degrees because that allows for a more numerically stable check.

There's probably three broad ways to deal with this:

• Adjust the hasTriangleFlip predicate to use a rotation cut off that is smaller than 90 degrees. This is delicate and needs to be tested carefully, both because of the numerical stability concerns, and because a too severe cutoff may restrict collapses too much on complex meshes where the flipping problem doesn't occur
• Add an area based condition that prevents significant area changes. I'm not sure if this is strictly speaking a good idea, but most of the specific cases I've debugged here in the past involve thin triangles and maybe restricting area changes is less constraining than the above.
• Change the approach to preventing flips by comparing the new triangles vs some sort of expected normal direction for a given vertex that is computed for the original mesh. For example, in the case above, the first red collapse allows the second red collapse to happen, but by itself the first collapse is, while not ideal, also not catastrophic. But by the time we do the second red collapse we lose the sense of the expected triangle normal direction adjacent to the original vertex. The issue here is that this also may be too restrictive on real geometry.

I plan to investigate solutions to this more in the coming weeks.

[mathieu-lemuzic]

FYI, I got decent results by discarding collapses producing triangles whose largest angle is greater than 175 degrees in hasTriangleFlip(), neither triangle area or normal angle restrictions worked for me.

[zeux]

Yeah for most previous reports I've been testing the version of (1) which I've now refined to something like this (which is numerically safe as worst case scenario is for the sqrtf argument to underflow to zero and that's equivalent to the check we're doing now):

@@ -892,10 +892,14 @@ static bool hasTriangleFlip(const Vector3& a, const Vector3& b, const Vector3& c
        Vector3 nbc = {eb.y * ec.z - eb.z * ec.y, eb.z * ec.x - eb.x * ec.z, eb.x * ec.y - eb.y * ec.x};
        Vector3 nbd = {eb.y * ed.z - eb.z * ed.y, eb.z * ed.x - eb.x * ed.z, eb.x * ed.y - eb.y * ed.x};
 
-       return nbc.x * nbd.x + nbc.y * nbd.y + nbc.z * nbd.z <= 0;
+       float ndot = nbc.x * nbd.x + nbc.y * nbd.y + nbc.z * nbd.z;
+       float abc = nbc.x * nbc.x + nbc.y * nbc.y + nbc.z * nbc.z;
+       float abd = nbd.x * nbd.x + nbd.y * nbd.y + nbd.z * nbd.z;
+
+       return ndot <= 0.25f * sqrtf(abc * abd);
 }

I think 0.25f is the lowest constant that solves the previously reported issues with some headroom (iirc some reported case had something like a 0.15f dot product limit on bad collapses), it corresponds to a 75 degree limit (compared to the 90 degree limit right now). Perhaps surprisingly I don't see this having any notable detrimental effect on performance or quality of simplification, as in this seems to be not-worse than what we're doing right now. I've also tested 0.50f (60 degree limit, this is nice because it takes 3 full limit rotations to cross a 180 degree threshold) and that also seems reasonable, but less conservative so perhaps best left for a future change.

I need to test this a little more, hopefully this will be a reasonable solution. There might still be some complex cases with lots of collapses where in the end you get inverted structures because the restriction is local but improving that could be a separate line of research, as more basic problems keep coming up that would all be solved by this simple fix.