Quadric Edge Collapse Decimation/TriEdgeCollapse Spiky triangle issue

[CarsF]

In both Meshlab and VCGLib from C++ source the Quadric Edge Collapse Decimation has issues on certain meshes that causes a vertex in the mesh to move away in the distance.

I have managed to create some simple reproduction steps and manage to recreate it consistently with the following mesh (.obj). The mesh is only a few vertices and faces which should hopefully make it easier to track down the issue.
problem_mesh.zip
Steps

• Unzip problem_mesh.zip
• Open MeshLab
• Import problem_mesh.obj
• This will show the mesh as in before.png
• Open Mesh Simplification: Quadric Edge Collapse Decimation
• Click Apply with the following settings:
• See result (after.png image)

BEFORE

AFTER

This seems like unexpected behavior that shouldn't occur, is there a code fix available for this issue that we can apply?
Or is it possible for you to fix the code if a fix isn't available yet?
Or Is there anything (mesh process) that can be done about this to prevent this issue from happening? Maybe there is something wrong with the mesh that I am missing?

This happens on different meshes as well, but they are more complex and this was the simplest mesh i could provide to recreate this on.

Let me know if you need more information.

Thanks,

[cignoni]

Thanks for the sample!
A quick workaround is just enabling the "planar simplification" option in the dialog it avoids exactly this kind of issue.

[jmespadero]

This problem is also avoided enabling the "Preserve Normal" flag, Which by the way, never hurts to enable. Probably should be enabled by default.

The problem is produced by that degenerate triangle (extremely obtuse) on the boundary, and the way the optimal position for the new vertex is computed.

[CarsF]

Hi thanks for your fast replies

Thanks for the sample! A quick workaround is just enabling the "planar simplification" option in the dialog it avoids exactly this kind of issue.

This does seem to solve/hide the issue on this mesh and another mesh that I tried quickly. I have not tried it on some more complex meshes but will do when I get a chance.

This problem is also avoided enabling the "Preserve Normal" flag, Which by the way, never hurts to enable. Probably should be enabled by default.

The problem is produced by that degenerate triangle (extremely obtuse) on the boundary, and the way the optimal position for the new vertex is computed.

In the C++ implementation i already had this feature enabled when checking which parameter meshlab actually sends to VCG lib, so while this helped in meshlab, sadly i still got the issue in the past with this option enabled when trying to cutdown process some meshes previously.

My worry is is that the Planar Simplification actually does something similar to the Preserve Normal option, it will fix certain cases the but problem may still persist in some other geometry.

I tried debugging the code myself a few months ago and remember that the vertex that moves away from the mesh actually wasn't the first corrupted vertex that was created, at some point in the process one of these corrupted vertices gets made and then still used throughout the process to find the most optimal vertex. So this initial vertex corrupts future vertices. I don't know if this helps you with making the VCG code more robust, or if this is just a limitation of the algorithm as I don't understand the math behind it at all.

Is there any other functions in VCG lib that could prevent these issues? I already tried most of the cleanup functions like degenerate geometry, but maybe you have some other advice that are just a good idea in general to apply to meshes?

If i find any more examples that still have the issue I will see if its possible to share the meshes to help you recreate it, this might take a while though since it seems very rare that this issue happens (hopefully the option described above resolves it in all cases though).

Thanks!

[jmespadero]

Maybe the problem is at this potential division-by-zero in Quadric::Minimum()

double relative_error = (A*xe - be).norm() / be.norm();
if(relative_error> Quadric<ScalarType>::RelativeErrorThr() ) 
  return false;

What happen if be.norm() is near to 0.0?