Simplification produces non manifold edges

[roenyroeny]

Might be related to https://github.com/zeux/meshoptimizer/issues/698 / https://github.com/zeux/meshoptimizer/issues/346

Simplifying this mesh procures output with 1 non manifold edge ( edge with more than 2 faces )

input wireframe:

output wireframe:

This edge is non manifold: Meshlab has a handy view for this.

(fixed) repro.zip containing the input mesh and code to reproduce.

repro case it should output

duplicate face found 102 104

[zeux]

Are you sure you attached the correct input mesh? I had to change main.cpp to open input.obj instead of test.obj, but after doing that I do not get the "duplicate face" output using latest master like this:

g++ main.cpp ../src/simplifier.cpp -I../src -DTRACE=0 && ./a.out

(note, had to also add includes math.h, string.h, and change void main to int main for code to compile)

[roenyroeny]

My bad. I think i attached the wrong one. Will update asap!

[roenyroeny]

Sorry about that. i accidentally attached the obj from the other issue. I've reuploaded the repro in the first post and added the missing includes. i used MSVC which magically provides these.

Thanks for looking into this, much appreciated!

[zeux]

I've spent some time today reducing this example and debugging to understand the behavior. Attaching a minimal repro for completeness (24 input triangles, 10 output triangles):

repro-minimal.zip

Here's the visualization of the simplification steps that happen to achieve the result. All vertex indices here (annotated with yellow) refer to zero-based indices in the test.obj file, and are consistent between images. The first image shows first 8 collapses, annotated with numbers in blue.

This shows the final two collapses; during these collapses two triangles with vertices 6, 7, 10 are created; the second image shows the mesh at a little bit of an angle to show the triangle more clearly - note that the flipped version of the same triangle is visible from the other side.

I'm not sure what to think about this issue atm; for some reason I thought that manifoldness gets preserved during simplification, but this is clearly not the case, and I'm not sure whether this is something that will be fixed or not yet.

[zeux]

Yeah, thinking about this more there should just not be an assumption that the output of simplification is manifold; the edge collapse algorithms usually don't guarantee this, and I don't think topological analysis here is warranted.

Note that in this case, the creation of the edge can be viewed as a subset of #346 - the last two collapses shown on the image (the ones that directly create the two-sided triangle) both result in a ~82 degree rotation. A more aggressive threshold would prevent the collapses shown above. However, this is probably separate from the topological restrictions - a reasonable assumption should probably be that non-manifold edges may appear in the output, but improvements to flipping logic would solve this specific case.

[RikoOphorst]

@zeux Extremely impressive debugging work, that's a seriously difficult problem! If you have the time for it, could you share some light on how you build these step by step visualizations of this problem?

[zeux]

I wish there was a trick to this :sweat_smile: I'm using a combination of Blender (in this specific case it helps that Blender's builtin visualization of vertex indices, which is enabled via "developer extras" in interface settings, displays indices that are aligned with .obj file when exporting only positional data), small tracing additions to simplifier.cpp that I will submit later to make detailed debugging like this easier in the future (via TRACE macro), and just hand annotating things based on this data with iPad / pencil.

It helped that I was able to reduce this test input iteratively to be manageable by changing the repro source code to brute force search every possible target index count (as the problem is dependent on the specific collapse set which varies a little depending on target index count, and you need to make sure the problematic edge doesn't get collapsed after being created), and just manually removing geometry while the problem persisted.

[RikoOphorst]

@zeux That's impressive! Figured the workflow would be something along the lines of this. I really should get more comfortable with tools like Blender to make all this less painful to debug - that tidbit on the vertex indices visualization is very useful. Thanks for sharing!