Dienstag, 13. Mai 2014

Quadric Mesh Simplification with Source Code

In the past days I have written a quadric based mesh simplification program. After searching the internet I couldnt find any code that was free to use, not unnecessarily bloated, fast and memory efficient, even the quadric based method is soon 20 years old. I therefore decided to write one myself.

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

The result is short and easy to use in case you need to adopt it to your project. You can fetch the C++ Project with source here: (about 300 lines for the main part, contained in Simplify.h )

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).

42 Kommentare:

  1. 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öschen
  2. Sure 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öschen
  3. Great! Please put it on Github + a licence (can I suggest BSD?)

    Thanks a lot!

    AntwortenLöschen
  4. I added the MIT license now. Also fixed collapsing borders in the new version.

    AntwortenLöschen
  5. Hey man, which IDE are you using for the project?

    AntwortenLöschen
  6. great!

    Maybe 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.

    AntwortenLöschen
  7. 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öschen
  8. Ported your code to java and playing around some. Let you know if I make any improvements.

    Also 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.

    AntwortenLöschen
    Antworten
    1. 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öschen
  9. Come to think of it with models that have seams I guess edges that follow seems have to be locked for simplification to.

    AntwortenLöschen
  10. Locking 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.

    For 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.

    AntwortenLöschen
  11. what is the difference with the openmesh quadric error metric decimation method?

    AntwortenLöschen
    Antworten
    1. I 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öschen
  12. Dear Sir,

    Great 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.

    AntwortenLöschen
  13. The mesh simplification algorithm compiles in Linux as well. The only windows specific parts are the image loading libraries (Devil).

    AntwortenLöschen
  14. Hi,
    Just 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?

    AntwortenLöschen
    Antworten
    1. 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.

      i will answer the second part later

      Löschen
    2. Hello,
      I 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

      Löschen
    3. 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öschen
  15. Thank 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öschen
  16. Also, can anybody please tell me why below condition is enforced for a flipped triangle in flipped function?

    if (fabs(d1.dot(d2)) > 0.999)
    return true;

    AntwortenLöschen
  17. Sorry. Just realized, it is to avoid triangles with very small and very large angles.

    AntwortenLöschen
  18. Hi there, thanx for your library.
    As 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

    AntwortenLöschen
  19. Hello,

    great job! I'm curious... how does it compare to qslim? Faster, but lower quality or am I wrong?

    AntwortenLöschen
  20. I am curious if this application can also handle UV's well.

    AntwortenLöschen
  21. I am curious if this application can also handle UV's well.

    AntwortenLöschen
    Antworten
    1. you need to modify it so that uvs are interpolated like vertices

      Löschen
    2. This 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öschen
    3. I havent tried that yet, but i would interpolate in tangent space

      Löschen
  22. can you provide source code link ?? link posted in blog is not working.

    AntwortenLöschen
    Antworten
    1. https://github.com/sp4cerat/Fast-Quadric-Mesh-Simplification

      Löschen
  23. This line is a great concern to me.

    double threshold = 0.000000001*pow(double(iteration+3),agressiveness);

    can you elaborate more on what this is so I can better generalize the magic number?

    AntwortenLöschen
    Antworten
    1. its an emperical value. the threshold just needs to increase in an exponential manner

      Löschen
  24. Hi, i have created a c# version, that i like to use in my surface algorithm.
    If you want, i can post the code.
    https://www.youtube.com/channel/UCQ2uQQWCnxQJt5m1UTKwEHA

    AntwortenLöschen
    Antworten
    1. yep if you share your code on github.it will very useful

      Löschen
    2. yep if you share your code on github.it will very useful

      Löschen
  25. Hi, 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öschen
  26. Hi, I just rewrote this code to c#. I noticed that in
    bool 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

    AntwortenLöschen
    Antworten
    1. Yeah I noticed that too. Can you try mesh from my link? Does it works for you fine?

      Löschen
  27. Bunny.obj and spehere.obj worked fine. wall.obj is too big for other parts of my app.
    I also tested other models and the results are very good IMHO.

    AntwortenLöschen
  28. 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