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.

[bawar9]

eresting observation about the fix to Boat Proble

Thank you, I'll wait for you changes to get published

[is3D-1]

@bawar9 I don't know where to address this but I have looked at the curvature error method you have committed and I have some concerns:

The idea of taking curvature data into consideration is a great addition to the algorithm however, the way it is implemented is not correct. Let me explain: 1- In the CurvatureError(ref Vertex vert0, ref Vertex vert1) function, you take the maximum value of the dot product of all triangles touching Vert0_or_Vert1 as outer loop and Vert0_and_Vert1 as inner loop. Any triangle that is part of Vert0_and_Vert1 is also part of Vert0_or_Vert1 and thus the dot product of a triangle normal by himself is always 1. Hence, the CurvatureError() function only return the length of the edge... You could fix it by rejecting the case where a triangle is member of both set like that:

                foreach (var triangleWithViAndVjBoth in trianglesWithViAndVjBoth)
                {
                    if (triangleWithViAndVjBoth == triangleWithViOrVjOrBoth)
                        continue;
                    Vector3d normVecTriangleWithViAndVjBoth = triangleWithViAndVjBoth.n;
                    double dot = Vector3d.Dot(ref normVecTriangleWithViOrVjOrBoth, ref normVecTriangleWithViAndVjBoth);

                    if (dot > maxDotInner)
                        maxDotInner = dot;
                }

2- The CalculateError(...) function incorporate CurvatureError(..) only for the first case. Why it is not applied to all case ?

3- A good way to implement the curvature error would be to specify a value between 0..1 instead of a check box [0 or 1] to specify whether to preserve curvature or not. The resulting error would be: error = E(vertex) + alpha * E(curvature) where alpha is [0..1]. Alpha =0 corresponds to keep details while alpha=1 corresponds to keep general shape...

Regards

[bawar9]

@bawar9 I don't know where to address this but I have looked at the curvature error method you have committed and I have some concerns: The idea of taking curvature data into consideration is a great addition to the algorithm however, the way it is implemented is not correct. Let me explain: 1- In the CurvatureError(ref Vertex vert0, ref Vertex vert1) function, you take the maximum value of the dot product of all triangles touching Vert0_or_Vert1 as outer loop and Vert0_and_Vert1 as inner loop. Any triangle that is part of Vert0_and_Vert1 is also part of Vert0_or_Vert1 and thus the dot product of a triangle normal by himself is always 1. Hence, the CurvatureError() function only return the length of the edge... You could fix it by rejecting the case where a triangle is member of both set like that: foreach (var triangleWithViAndVjBoth in trianglesWithViAndVjBoth) { if (triangleWithViAndVjBoth == triangleWithViOrVjOrBoth) continue; Vector3d normVecTriangleWithViAndVjBoth = triangleWithViAndVjBoth.n; double dot = Vector3d.Dot(ref normVecTriangleWithViOrVjOrBoth, ref normVecTriangleWithViAndVjBoth);

                if (dot > maxDotInner)
                    maxDotInner = dot;
            }

2- The CalculateError(...) function incorporate CurvatureError(..) only for the first case. Why it is not applied to all case ? 3- A good way to implement the curvature error would be to specify a value between 0..1 instead of a check box [0 or 1] to specify whether to preserve curvature or not. The resulting error would be: error = E(vertex) + alpha * E(curvature) where alpha is [0..1]. Alpha =0 corresponds to keep details while alpha=1 corresponds to keep general shape... Regards

@is3D-1 Thank you for pointing out the issues. To keep it organized I will answer your points in order

► You're correct in regard to saying "Any triangle that is part of Vert0_and_Vert1 is also part of Vert0_or_Vert1 and thus the dot product of a triangle normal by himself is always 1", however you're incorrect in saying that the "CurvatureError" function will only return the length of the edge (Vi, Vj). This will be true only where the afore mentioned condition is true, which won't be the case always. This is not a mistake done by me but what the authors of the original paper https://www.hindawi.com/journals/mpe/2015/428917/ intended. Below you see 2 images of a model (Before incorporating you condition and After incorporating you condition). The model is simplified to 80% (0.8) and the resulting triangles count is 3608 in both the cases, however your condition seems to disregard discrete surface curvature in some areas of the model.

The curvature of the arm and circle on the belt is preserved nicely

The curvature of the highlighted regions is slightly disrupted (Which is not the case with the original code. See the image above ^^^)

► Thank you for pointing it out this is a mistake on my side, I actually overlooked the second case. I'll make the changes and do a pull request after @Whinarn approves my last pull request.

► We can incorporate curvature error using
error = E(vertex) + alpha * E(curvature) where alpha is [0..1]. However the effect would be the same, I usually stress on simplicity and code readability so I used simple boolean conditions so that anyone can easily understand the code

[is3D-1]

@bawar9 Thanks for your reply. I don't want to accuse you or anyone else who is contributing to the project. I view it simply as a discussion to improve the final result and again I appreciate your answer with pictures that clearly illustrate your point ! Regards

[bawar9]

@bawar9 Thanks for your reply. I don't want to accuse you or anyone else who is contributing to the project. I view it simply as a discussion to improve the final result and again I appreciate your answer with pictures that clearly illustrate your point ! Regards

@is3D-1 I am sorry if I sounded a little offensive, I can assure you that I was not. I am very happy to see some one like you contributing to the project, someone who knows what he's doing. This is a great chance for me to learn and enhance my knowledge from good people around. By no means am I an expert on this subject, in fact I am still a student and by far from being a pro. Please do point out any problems that you see, I would appreciate positive discussion and/or criticism.

Kind Regards

[is3D-1]

I finally got some results I would like to share with you. I've put a lot of effort to come to a solution for the boat problem but I'm not sure if it's a robust solution that would solve all the cases out there. I basically implemented the solution described above for a heap of edges keyed by increasing quadrics error order. I added weighted penalty planes to try to preserve 2D borders on open meshes. This version utilizes the available "smart link" and "preserve surface" features but implements its own "preserve border edge". The method collapses all edges in a single pass until the quality ratio is reached. Parameters "max iteration count" and "agressiveness" are not used. Also note that vertices attributes like uv, colors, etc are not fixed yet. Test case 1. The boat (posted version has 2196Tris, 3851Verts). From top left to bottom right: (Quality=0.5, 1098Tris, 604Verts), (Quality=0.2, 439Tris, 267Verts), (Quality=0.1, 220Tris, 149Verts) Test case 2. Men washroom device (original version has 8866Tris, 3851Verts). From left to right: (Quality=1.0, 8866Tris, 3851Verts), (Quality=0.3, 2500Tris, 1255Verts), (Quality=0.1, 726Tris, 368Verts), (Quality=0.05, 284Tris, 148Verts). handle.zip ...And the execution time is quite fast too. Some observations from my experiments:

1. I would check on "smart link" all the time with a link distance of 0.0005. In metric units, this corresponds to 0.5 mm and is not noticeable. This feature improves greatly the quality of the reduced mesh as it closes the mesh and favours uniformity of the resulting mesh.
2. Option "preserve surface" is also beneficial almost all the times as it tends to eliminates small details and preserves the general shape at high quality ratio. I have also noticed that it improves the performance (speed) of the keyed heap and favours uniformity of the resulting mesh.
3. "Preserve border edges" helps only for open meshes and is detrimental for execution speed.

Regards

[is3D-1]

I improved the approach to preserve 2D border edges: instead of adding a heavily weighted plane along the border, I add two very close planes, one on each side of the border so that the quadrics error metric is always much greater than zero anywhere near the border. This has solved the problem: Test case 3. Two basic perpendicular planes. From left to right: a) Quality=1.0, 400Tris, 242Verts b) Quality=0.1, 40Tris, 32Verts, preserve border edge = ON, preserve surface = ON c) Quality=0.1, 40Tris, 32Verts, preserve border edge = ON, preserve surface = OFF d) Quality=0.1, 40Tris, 32Verts, preserve border edge = OFF, preserve surface = OFF

I know almost nothing about UV (same for vertex attributes) but I'm asking anyway : do you think the approach to preserve border edge could work to preserve UV seam edges ?

I so, I could easily extend the code to manage these options before I publish.

regards

[bawar9]

@is3D-1 Great work !. Indeed your approach to preserve 2D border edges using weighted virtual planes seems to work. I can't wait to get my hands on the code. About preserving UV Seam Edges, I haven't looked at how it is implemented and without seeing your current changes, it would be hard to say that whether it would work or not. I think @Whinarn would know better. One question I wanted to ask, how much does this all affect the performance of the Whinarn's original implementation?. I suspect the sorted heap would have made a huge difference and caused the original algorithm to become slower. Did you try to actually benchmark the 2 variants using an actual time metric ?.

Thanks

[is3D-1]

@bawar9 You are right, the performance has taken its toll ! The algorithm is somewhere between 5 to 10 times slower than @Whinarn version. This is partly due to the sorted heap management and partly to quadrics error planes and error evaluation on every edge collapsed. I have not changed the data structure of @Whinarn model beside to add an Edge class. Although I may have changed many things, I have tried to fit into @Whinarn model as much as possible. The major aspects are :

I- Managing the edges heap with two data structures:

1. A sorted list of edges by increasing order of error.
2. A dictionary of all edges to allow referencing an edge from any other object in the model

II- Convert all struct data type to class data type: This was necessary for the edge based approach to create pointer to other objects in the model without having to instantiate data for every variable. This change alone speed up @Whinarn algorithm by a factor of 2 to 3.

III- Managing the option to preserve features usually add extra calculation that increased time. however, I have found that "preserving surface" option often reduced the calculation time. I think the error change calculated by this option improve the hashing of the sorted list algorithm and ultimately speed up the Add/Remove operations.

So overall the algorithm is an order of magnitude slower than @Whinarn version.

Regards

[bawar9]

@is3D-1 Thanks for the detailed breakdown. In the custom version of Whinarn's mesh simplifier that I have tailored to fit my needs, I had also made the following changes:

1> As you did, I had also converted all struct/value types to class types, this greatly increases the performance simply because structures are immutable and any change to a structure requires copy pasting all the data from one to another.

2> Heavily threaded Whinarn's implementation so that it uses best of what the CPU can offer.

3> Did some other minor tweaks to gain some performance.

Although this made a huge difference but it still was no where near to the mesh simplification offered in 3D Modeling tools. I use Cinema4D and don't know what kind of magic it does but it is super fast at simplifying even complex meshes with a lot of preservation options checked (Preserve border edges, UV Seams etc) and the simplified mesh quality is great. @is3D-1 This just leaves me with one clue, I think they are somehow using the parallel power of GPU to do all the heavy lifting. They might have their own proprietary algorithm which would be tailored to run best on parallel cores. What do you think of this?. Can we use a compute shader in Unity and somehow parallelize /distribute the algorithm for the GPU?

Oh, and btw in point 1 I suggest you use HashSet instead of a Dictionary if that's possible. Insertions in Dictionaries are a little slower than HashSets. Also if you somehow get duplicate values in the Dictionary the lookup can get very slow somewhere around O(n) due to Hash collisions.

Thanks

[Whinarn]

@is3D-1 Impressive work.

do you think the approach to preserve border edge could work to preserve UV seam edges ?

I'd need to see the code in order to answer that. But I'd assume that preserving UV seams would require a different approach, but don't take my word for it.

II- Convert all struct data type to class data type: This was necessary for the edge based approach to create pointer to other objects in the model without having to instantiate data for every variable. This change alone speed up @Whinarn algorithm by a factor of 2 to 3.

I'm actually very surprised about this, I might have to evaluate it myself. I might have done some pre-mature optimizations here then, because the idea of using struct was to make it faster and avoid extra allocations. But I should have profiled the code before making assumptions.

So overall the algorithm is an order of magnitude slower than @Whinarn version.

As long as it's opt-in, I'd be fine with it.

If you keep this up, and your code looks promising, I might ask you to take over maintaining this project. With me being absent and uninterested, and people still using it, I feel like it deserves a more active and interested maintainer (with a lot more knowledge about this as well). If you'd be up for it that is. I have wanted to archive this project, because I don't feel like I have the time for it, but I would feel bad about the fact that people still use it in their projects.

[is3D-1]

Please be very cautious with respect to this algorithm. I have made a lot of promises based on the test cases above after tweaking the code to obtain the best result possible at high reduction ratio. But it has not been tested seriously yet...

I have finally not implemented the fix for the boat problem because it has disappeared by itself when I implemented the quadrics unioning for error calculation. Hence it may reappear and probably will...

My approach from the beginning is to avoid restricting the quadrics natural behavior as much as possible to achieve high reduction ratio while still recognizing the shape. So I tolerate triangles that are visually degenerated for the benefit of a high ratio. I have also observed that the more triangles that get merged at a vertex, the more stiff this vertex becomes and prevents the algorithm from doing a better job around it (the "preserve surface" feature help a lot to overcome this problem). So there is still a lot of work to do if one wants... and much more than I expected at the beginning of the project...

Hope to post the code soon

[is3D-1]

@bawar9

This just leaves me with one clue, I think they are somehow using the parallel power of GPU to do all the heavy lifting. They might have their own proprietary algorithm which would be tailored to run best on parallel cores. What do you think of this?

All these editing tools have detailed and efficient data structures to store the mesh information and to be able to quickly locate a face, edge or vertex when you click somewhere in the screen, and this is already setup before you click the optimize/reduce mesh button. On the other end, @Whinarn version receive the data from Unity and it needs to create internal arrays of triangles, vertices and references plus edges analysis to find borders... just to have the information ready for processing by the SimplifyMesh() function. To be fair with @Whinarn version, I would only measure the time it takes to actually run the SimplifyMesh() function and compare this result with the time Cinema4D takes on his side when you click its optimize button. Timing Cinema4D is feasible if you run the optimization algorithm from a python script (I think I may have such a script if you want). I would be curious to see the result. For the GPU, I think you could do a test: if you have a built-in video card, then you could disable the GPU card in Windows (Device Manager>Graphic cards>Deactivate) and test Cinema4D with/without the GPU.

They might have their own proprietary algorithm which would be tailored to run best on parallel cores. What do you think of this?. Can we use a compute shader in Unity and somehow parallelize /distribute the algorithm for the GPU?

I can't help you on this one.

Regards

[is3D-1]

@bawar9

Oh, and btw in point 1 I suggest you use HashSet instead of a Dictionary if that's possible. Insertions in Dictionaries are a little slower than HashSets. Also if you somehow get duplicate values in the Dictionary the lookup can get very slow somewhere around O(n) due to Hash collisions.

I would like to explore that possibility and some others but only after you have seen the code. I think I could post the code this week-end. Thanks

[is3D-1]

@Whinarn

If you keep this up, and your code looks promising, I might ask ...

Please give me some time. I will get back to you for sure. Regards

[bawar9]

@bawar9

This just leaves me with one clue, I think they are somehow using the parallel power of GPU to do all the heavy lifting. They might have their own proprietary algorithm which would be tailored to run best on parallel cores. What do you think of this?

All these editing tools have detailed and efficient data structures to store the mesh information and to be able to quickly locate a face, edge or vertex when you click somewhere in the screen, and this is already setup before you click the optimize/reduce mesh button.

Hi, Sorry for the late response. I have been quite busy lately. You're right I should do performance benchmarking disregarding the initialization on Whinarn's mesh simplifier. If you have the python script for C4D (Cinema4D) please do send it over. I'll perform some performance tests on both and get back to you later this week. Disabling the dedicated GPU and then testing on C4D would still allow it to access the integrated GPU in the processor, but I'll give this a try.

I have also explored the topic of GPU based mesh decimation and it looks like there are a lot of papers on this topic that utilize the parallel processing capabilities of the GPU. I read one of them that used OpenCL to practically implement the algorithm.

[bawar9]

I would like to explore that possibility and some others but only after you have seen the code. I think I could post the code this week-end. Thanks

Sure, Thank you

[is3D-1]

@bawar9

I have also explored the topic of GPU based mesh decimation and it looks like there are a lot of papers on this topic that utilize the parallel processing capabilities of the GPU. I read one of them that used OpenCL to practically implement the algorithm.

Very interesting. We may not be at the right place to discuss it without polluting the OP Boat Problem thread ! However, it seems you are seeking a solution to process thousands of gameobjects in the fastest time. I have just reduced a scene containing 311500 objects from 15.5M triangles down to 10.0M with a commercial application that did it in 65 seconds with quadrics. The app takes advantage of duplicated objects by just reducing one of the siblings and copying it over. It uses the CPU at 100% so all cores are working and no GPU at all ! But it takes a lot of memory, around 8 Gb. This suggests the data structure is extremely important...

[bawar9]

This suggests the data structure is extremely important...

You're right we shouldn't spam this thread. Great conclusions anyways, indeed choosing the right data structures are crucial.