Features / Summary:
- Threshold based, therefore faster than sorting based methods
- Since the Quadric Matrices are symmetric, only 10 elements are stored & computed per Matrix instead of 16
- Non-closed meshes are supported by extra treating mesh borders
- Simplifies 2.000.000 triangles to 20.000 triangles in 3 seconds on a Core i7
- MIT License
- MS Visual Studio 2012 , C++
Update Sept.20th 2014 : improved quality of reduced borders
Download Source and Data
The code is about 4x-7x faster than Meshlab, which is already fast. Using multi-core programming, it could even be faster.
Here a comparison along Meshlab, QSlim and this method:
Program output (left) and Meshlab (right). Note that Meshlab produces floating teeth and looses details around the eyes, nose and the mouth region. Reduction was 85k -> 3k Triangles.
Original (left) this code (middle) and meshlab (right)
Here another comparison: Program output (left) and Meshlab (right).
What license has the code? I mean, can I use it on commercial projects? (I'll include your link to this page of course if I happen to use it.)
AntwortenLöschenSure you can use it for any purpose. I will add a license statement for the next version. I link to my page is appreciated !
AntwortenLöschenGreat! Please put it on Github + a licence (can I suggest BSD?)
AntwortenLöschenThanks a lot!
I added the MIT license now. Also fixed collapsing borders in the new version.
AntwortenLöschenHey man, which IDE are you using for the project?
AntwortenLöschenVisual Studio Express 2012
AntwortenLöschengreat!
AntwortenLöschenMaybe a first step should be to traverse and remove vertexes for which all triangles have the same normal. This would create some flat polygons in the model that would need retriangulation. A model like wall.obj that have big flat areas, would greatly benefit from this approach to decrease the triangle count before the simplification.
That could work by first searching the boundary edges and then performing a triangulation ( such as with https://code.google.com/p/polypartition/ ). Not sure if its faster due to the extra step at the beginning, but it could lead to a better result.
AntwortenLöschenPorted your code to java and playing around some. Let you know if I make any improvements.
AntwortenLöschenAlso wondering about the best way to generate new texture coordinates for a simplified model. Since the code just not eliminate vertexes but alter the position of the existing ones. There must be a good way to recompute the texture coordinates to during the simplification or at least after the simplification.
Mind sharing your Java implementation with us? I wonder how you managed to do this, given the many dependencies on other C++ libraries in the source ....
LöschenCome to think of it with models that have seams I guess edges that follow seems have to be locked for simplification to.
AntwortenLöschenLocking the outer seams is not good. This is a similar idea to locking outer open edges of the 3D model, where not all sides are having triangle bounding. It will leave too many triangles. The solution is to collapse no edge that connects to a vertex of the seam, unless it contains two vertices of the same seam. This technology is already implemented above.
AntwortenLöschenFor texture coordinates, they can be interpolated along with the vertex positions I believe. It just gets more difficult if a vertex has multiple texture coordinates for each triangle it connects to.. Therefore, perhaps storing the texture coordinates inside the triangle structure can solve that.
Also if multiple materials are used, it might be good to treat material boundaries extra, similar to boundaries of the object.
Java-port sounds cool. If you decide to make it open source, let me know. I will add a link to your page.
what is the difference with the openmesh quadric error metric decimation method?
AntwortenLöschenI dont know openmesh - but the general difference to the common method is to remove triangles based on an error threshold rather than a sorted list
LöschenDear Sir,
AntwortenLöschenGreat Job!. Unfortunately for my application I need everything running under Linux. Is there any information about compiling under some Linux? Have someone tried to compile under Linux?
Thank you very much for your answer.
The mesh simplification algorithm compiles in Linux as well. The only windows specific parts are the image loading libraries (Devil).
AntwortenLöschenHi,
AntwortenLöschenJust discovered your algorithm, it's very cool.
Over here:
if(count<=v0.count)
{
// save ram
if(count)memcpy(&refs[v0.start],&refs[start],count*sizeof(Ref));
}
after the copy I believe you should release the unused memory, something like:
refs.resize(start);
Because currently it looks like you're not actually "saving" any ram.
Another thing I wanted to discuss is the merging of points, specifically adding Quadric / Symmetric Matrices:
Imagine you have a situation like that:
you've got one point that belongs to a face with plane position zero (0, 0, 0), and normal facing up (0, 1, 0).
You test it against a "TEST" point (0, 1, 0), and the 'vertex_error' correctly returns "1", because it's one unit away from the plane.
Now, the issue appears after merging:
having the original:
plane position zero (0, 0, 0), and normal facing up (0, 1, 0).
you merge it with another point from the same triangle, so:
plane position zero (0, 0, 0), and normal facing up (0, 1, 0).
Because the SymmetricMatrix& operator+=(const SymmetricMatrix& n) is used, it ends up having matrix with 2x bigger values.
And now when you test the new matrix against the same "TEST" point as before (0, 1, 0), the 'vertex_error' will now return "2", even though
the merged points were on the same plane position, with the same normal.
I think this case should handle some extra math.
I've tried doing some normalization of the matrix after the SymmetricMatrix+= operator, but ended up having worse results, perhaps it's more complex.
SymmetricMatrix sm(0, 1, 0, 0); // one matrix facing up, plane =0
flt error=vertex_error(sm, 0, 1, 0); // distance = 1, error=1, OK!
sm+=sm; // happens when merging two vertices with same parameters
flt new_error=vertex_error(sm, 0, 1, 0); // distance is still = 1, new_error=2, NOT OK?
For the first issue, "save ram" is maybe not exact enought. Its more about not allocating new ram. For the resize, that wont free any ram. vectors can only release ram by swapping with an empty vector.
Löscheni will answer the second part later
Hello,
LöschenI believe you are incorrect:
if I put
"int x=refs.size();"
just before compact_mesh();
I get 9005 with your code when optimizing the bunny mesh
and I get 8879 after my fix of:
if(count<=v0.count)
{
// save ram
if(count)memcpy(&refs[v0.start],&refs[start],count*sizeof(Ref));
refs.resize(start);
}
This is about preventing:
"refs.push_back(r);" from allocating new elements
doing this resize is quite risky, as there is no guarantee that the removed triangle is that last in the list. also will a resize not release any memory. to release the memory of a vector, you have to use its swap function and swap it with an empty vector.
LöschenThank you very much for the code. I am a newbie to this topic. Can anybody please tell me how the threshold value is set? Thanks
AntwortenLöschenAlso, can anybody please tell me why below condition is enforced for a flipped triangle in flipped function?
AntwortenLöschenif (fabs(d1.dot(d2)) > 0.999)
return true;
Sorry. Just realized, it is to avoid triangles with very small and very large angles.
AntwortenLöschenHi there, thanx for your library.
AntwortenLöschenAs others, i have problems with texture coordinates.
I do store the coordinates in Triangle structure (as 'int vt[3];', right next to 'int v[3];').
Then i modify the 'write_obj' function to write texture coordinates and face indices for this as well ('vt' and 'f 1/1 2/2 3/3' thing).
However, the result is messy on parts where the simplication took process. Perhaps we need to somehow update this in say 'update_triangles' or somewhere else?
Thanx
Hello,
AntwortenLöschengreat job! I'm curious... how does it compare to qslim? Faster, but lower quality or am I wrong?
I am curious if this application can also handle UV's well.
AntwortenLöschenI am curious if this application can also handle UV's well.
AntwortenLöschenyou need to modify it so that uvs are interpolated like vertices
LöschenThis is easy to do for the det == 0 case but interpolating UV for the other cause (with the determinants) is not straightfoward. Can you please elaborate on how we might do this?
LöschenI havent tried that yet, but i would interpolate in tangent space
Löschencan you provide source code link ?? link posted in blog is not working.
AntwortenLöschenhttps://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification
LöschenThis line is a great concern to me.
AntwortenLöschendouble threshold = 0.000000001*pow(double(iteration+3),agressiveness);
can you elaborate more on what this is so I can better generalize the magic number?
its an emperical value. the threshold just needs to increase in an exponential manner
LöschenHi, i have created a c# version, that i like to use in my surface algorithm.
AntwortenLöschenIf you want, i can post the code.
https://www.youtube.com/channel/UCQ2uQQWCnxQJt5m1UTKwEHA
yep if you share your code on github.it will very useful
Löschenyep if you share your code on github.it will very useful
LöschenHi, For some reason in makes holes in some (not all) meshes for me. Can you check this mesh for example: http://s000.tinyupload.com/index.php?file_id=00057796949679137529 ?
AntwortenLöschenHi, I just rewrote this code to c#. I noticed that in
AntwortenLöschenbool flipped(vec3f p, int i0, int i1, Vertex &v0, Vertex &v1, std::vector &deleted)
i0 and v1 are never used.
I´m not sure if that matters at all.
Anyway, thank you for sharing, works like a charm
Yeah I noticed that too. Can you try mesh from my link? Does it works for you fine?
LöschenBunny.obj and spehere.obj worked fine. wall.obj is too big for other parts of my app.
AntwortenLöschenI also tested other models and the results are very good IMHO.
Very impressive results , I want to try but Download link doesn't exist, can you give working one ? you may give here or you can send me on matangpanchal@gmail.com.
AntwortenLöschen