Border vertex is getting collapsed when border collapsing is turned off

[Zylann]

I have the following mesh:

My version of the library includes the change I made in https://github.com/zeux/meshoptimizer/issues/311#issuecomment-873502795 which is supposed to prevent any border vertices from being collapsed.

Running meshopt_simplify with a target index count set to 0 and error set to 0.0025, a dent appears:

Wireframe comparison:

It sounds like this should not have happened.

For reproduction purposes: This model was generated at runtime and I don't have code around to dump it as a standard format, so I dumped its vertex array as binary: dump.zip First 32-bit integer is vertex count, second 32-bit integer is index count, then follows positions array, then normals array, then index array. Code I used to write it:

    f.store_32(len(positions))
    f.store_32(len(indices))

    for i in len(positions):
        f.store_float(positions[i].x)
        f.store_float(positions[i].y)
        f.store_float(positions[i].z)

    for i in len(normals):
        f.store_float(normals[i].x)
        f.store_float(normals[i].y)
        f.store_float(normals[i].z)

    for i in len(indices):
        f.store_32(indices[i])

I think my version of the lib is 316167c3606c4bfd7647976ca0299afa31163ea7

[zeux]

It would be a bit easier to investigate this if the input was an obj file; it should be as easy to output as a binary file - just output “v” for each vertex position and “f” for each triangle using 1-based indices.

[Zylann]

Yeah I was not sure about turning it into text because I thought it could break determinism, but I can give it a try

[Zylann]

Here is what I could get: dump.zip It doesnt include normals, but I tried feeding it back to my test case and it also produced a dent.

[zeux]

Thanks! I initially thought that classification is to blame here but it looks like the border is correctly classified as, well, border:

(blue=border)

Mesh before simplification:

Mesh after simplification without any patches:

Mesh after simplification to 1% of triangles while disabling border collapses:

It's a little difficult to see because of the different camera angles but it seems to me that this is all correct, and there's no dent.

This is using gltfpack to simplify the .obj file. It's not quite the same as what you do because this welds vertices with the same position (since obj file doesn't have anything else), so it produces a different indexing. I will need to hack gltfpack to use the exact same indexing as present in the original file to analyze this more carefully...

[zeux]

Aha - ok - with the original index data and without any post-processing the classification does not recognize one of the vertices there as the border, hence the error in simplification.

[zeux]

Alright phew - got it. This mesh had degenerate triangles in the input along the border in some places. These triangles really confused the classification code, as there are some shortcuts being taken right now that sort of assume this doesn't happen, which is of course a mistake. I need to figure out what the best way is to deal with these, but after quick patch I get this:

The extra layer of quads on the border is due to the quick patch locking down vertices of degenerate triangles, which is probably too aggressive. I'll need to think about this a bit wrt what the correct solution is but I should be able to fix this later this week.

If you want a quick fix, you can filter out degenerate triangles before simplification. Note that "degenerate" here is in the topological sense - so triangles where either two of the three indices are the same create this issue.

[Zylann]

I'll need to investigate if my implementation of Transvoxel can avoid producing degenerate triangles.

I assume the border of quads actually occurs because my implementation is not able to share vertices in one of the axis directions (because when it starts from the first coordinate of a 2D slice, it has no "previous" to grab from), which results in duplicated vertices along the border.

Simplification takes almost twice the time Transvoxel takes so at the moment I considered running a minimum of optimization steps. I'm also not simplifying too much because when terrain gets remeshed upon modification it causes noticeable glitches.