Model Optimization Improvements (low poly simplification, edge collapsing, keep volume)

[hybridherbst]

The original title was "Model where simplification fails badly", but the thread has become a very valuable discussion around optimizations and improvements.

---

Simplification of this (already pretty simple) model fails pretty badly using the default options:
boat_vertexpaint.zip

Target

Actual
LOD 0

LOD 1

Any ideas?

[Whinarn]

I don't have any ideas as to why this would happen, but it's clearly a bug.
I don't have much time to look into this now, so I'll see when I have time.

[bawar9]

This might be partly due to be an inherent limitation of the original algorithm and partly because of some bug. The original mesh simplification algorithm (Surface Simplification Using Quadric Error Metrics by Michael Garland) doesn't take into account the surface curvature to preserve edges with sharper corners(curved edges). I have tweaked the algorithm based of a new approach that takes discrete curvature into account and it generates some very good quality mesh simplification without sacrificing the low poly aspect of the original Garland algorithm. I will contribute my changes to this project when I get time to do so.

[Whinarn]

@bawar9 I'm pretty sure the bug is related to this calculation. I might have made a mistake when I ported the original algorithm, or when I optimized it. Or it's even a problem in the original algorithm.

[bawar9]

@Whinarn There is an obvious problem in the implementation of Garland's algorithm here https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification
The guy modified the original algorithm and skipped the step of keeping a sorted list of Vertices with the least error on top, instead he just used an empirical threshold value to check which vertex pair (edge) to collapse. He did this to gain a big performance boost, but this can result in bad quality simplification. The same can be seen in the UnityMeshSimplifier implementation here https://github.com/Whinarn/UnityMeshSimplifier/blob/master/Runtime/MeshSimplifier.cs#L2467.
@Whinarn can't we keep a sorted heap with the least cost vertex at top instead of just using an empirical threshold value.

[Whinarn]

@bawar9 I am aware. This was actually the reason why I picked this algorithm. I wanted something that was fast. I would be okay with adding a sorted heap, but only if it's optional. I would still like there to be a fast simplification, but that people can enable a less optimized simplification for a higher quality output.

[bawar9]

@bawar9 I am aware. This was actually the reason why I picked this algorithm. I wanted something that was fast. I would be okay with adding a sorted heap, but only if it's optional. I would still like there to be a fast simplification, but that people can enable a less optimized simplification for a higher quality output.

That would be really great, giving people the option to choose for themselves. For quite some time now I've been thinking which algorithm does Cinema4D use for this. It simplifies models super fast and the results are really great. I even created a threaded version of the UnityMeshSimplifier, even that couldn't surpass or even come closer to the Cinema4D mesh simplifier. I don't really mean to question your work in any way, you really have created a very good tool. I am just wondering that the Garland's algorithm has been living for quite some time and there might be newer and better algorithms out there. If I ever find anything better I would love to contribute my changes to the project.

[is3D-1]

@Whinarn Thanks for sharing your code !
I came across your project while searching for ways to manipulate meshes in Unity as a personal journey. I sometimes have to import CAD files data into Unity and the process always involves simplifying the meshes as much as possible. I recently tried a third party plugin called PiXYZ to do it and, I must say, it does a tremendous job at importing from many source formats and at reducing polygons to a high degree with high quality. The only down side is its license cost (more than 1000 Euro/year).
I tried UnityMeshSimplifier (which is free) to "crunch" some imported meshes to a high degree but I've been a bit disappointed with the result. The tool gives good results when the simplification ratio is not to high. After reading the comments here, I decided to dive into the project and try to improve (accuracy and speed) the algorithm as much as possible. Here is what I have experimented so far:

1. implemented a sorted list of edges by increasing order of error to determine the next edge to collapse.
2. improve the quadrics error estimation by updating the error matrix Q after every edge contraction. this may ultimately avoid the need to update the mesh every iteration to improve the error calculation.
3. Unioning the vertices matrix Q instead of adding them when calculating the error associated to an edge contraction.
4. optimize the execution speed to alleviate the additional calculations required by steps 1 to 3.

The resulting algorithm gives pretty good results but it too fails badly on the boat mesh above ! I'm currently working on the problem. What I can say right now about the boat mesh is that there are two problems:

1. Some new vertices appears far away from the boat. This comes from the geometry around the edge and the math behind the calculation of the new vertex location when an edge is collapsed. The location corresponds to a point p(x,y,z) that minimize the quadric error and is calculated by solving a set of 3 linear equations for x,y and z. The quadric error surfaces defined by the error matrix Q normally corresponds to ellipsoids (see section 5.1 of [https://dl.acm.org/doi/pdf/10.1145/258734.258849] and point p should corresponds to the center of these ellipsoids but in some situations, the surface can be degenerated. I suspect it is the case here as this outlier vertex actually corresponds to the minimum error location. So I don't think it's a bug in your code. I tried to catch these cases by inspecting the determinant of matrix Q' but with no success. I neither succeed with solving the set of equations with Gauss-Jordan Elimination method. I end up fixing the problem by testing the location of point p. If p is not along the collapsing edge, I reject p and fall back on the code that choose one the edge end point or midpoint.
2. Some surfaces disappear. This is how the quadric error method works. The authors of the method suggest to add virtual planes with high weigh along the border to avoid collapsing it. I will implement this approach.

If I succeed with all of this I will post the code here and let you decide if it can be incorporated into your project.

Regards

[bawar9]

@is3D-1 Thank you for dedicating your time on the project, it looks like you have really dig deep into the issue. Can you please share your current code step (1- 4)?. I would like to test it on my side as well. You can send me your new "MeshSimplifier.cs" file if that's feasible.

Thank you

[is3D-1]

@bawar9 I would be please to share it but the code has intricate parts with my development project. There are modifications in more than just "MeshSimplifier.cs" file and I have to manually operate the algorithm during this development. In fact I have dropped the uvs, normals and colors... until the mesh is ok. Again I will post it when it will be in a usable state, if you can wait until then...
I have made an interesting observation about the fix to Boat Problem 1 (BP1): it actually improve the result on other meshes as well when the simplification ratio is high. It is like the quadric error metric degenerate the further you increase the reduction ratio and BP1 fix seems to alleviate this.
I will fork the project and gradually pull the code there.

[Whinarn]

@is3D-1 Great work! I'm impressed. I'm looking forward to seeing your results.

[is3D-1]

@Whinarn Thank you. I have to admit I'm far from a working version. In the meantime, it would help if I could get some typical meshes to benchmark the solution. Regards.