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++
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:


Here another comparison: Program output (left) and Meshlab (right).

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