Mesh decimate algorithm

[gimba96]

Hi everyone,

I'm not quite sure if this forum is the right place for this question, please forgive me if it is not . I have started FreeCAD lately as a preprocessor for some FEM work. I have some STL-files (order 90000 facets) that are too large to comfortably import in the FEM software. Hence I created a simple script:

Code: Select all

import Mesh
mesh = Mesh.Mesh('myfile')
mesh.decimate(0.1, 0.5) #tolerance=0.1 and reduction=50%
mesh.write(Filename='myreducedfile', Format='STL')

I was wondering what the mesh.decimate-call actually does. Does it compare facets normals, does it just take any facet and join a number of facets to it?

Hope you can help!

[wmayer]

I was wondering what the mesh.decimate-call actually does. Does it compare facets normals, does it just take any facet and join a number of facets to it?

Here is the paper about the theoretical background:
https://www.ri.cmu.edu/pub_files/pub2/g ... 1997_1.pdf

The reduction is performed by collapsing edges where for each steps two triangles will be eliminated. The algorithm checks beforehand if the operation can be applied (i.e. it must not produce overlapping triangles) and what error it would create.

Depending on the thresholds the algorithm reduces a lot more in rather flat areas and not so much in curved areas.

Here are some links to the actual implementation:
http://voxels.blogspot.de/2014/05/quadr ... ource.html
https://github.com/sp4cerat/Fast-Quadri ... lification

[johnwang]

Depending on the thresholds the algorithm reduces a lot more in rather flat areas and not so much in curved areas.

Is there algorithm to detect surfaces on a cylinder?

[wmayer]

What exactly do you mean?

[gimba96]

Here is the paper about the theoretical background:
https://www.ri.cmu.edu/pub_files/pub2/g ... 1997_1.pdf

The reduction is performed by collapsing edges where for each steps two triangles will be eliminated. The algorithm checks beforehand if the operation can be applied (i.e. it must not produce overlapping triangles) and what error it would create.

Alright, thank you! I will look into the paper and actual implementation! This helps a lot

[johnwang]

What exactly do you mean?

Something like rebuilding cylinder surface from quad mesh

[wmayer]

So, if I got you right then you have a mesh that describes a cylinder and you want to get the exact mathematical representation of this cylinder. This process is called reverse engineering and it has nothing to do with mesh decimation.

[keithsloan52]

I was wondering what the mesh.decimate-call actually does. Does it compare facets normals, does it just take any facet and join a number of facets to it?

Here is the paper about the theoretical background:
https://www.ri.cmu.edu/pub_files/pub2/g ... 1997_1.pdf

The reduction is performed by collapsing edges where for each steps two triangles will be eliminated. The algorithm checks beforehand if the operation can be applied (i.e. it must not produce overlapping triangles) and what error it would create.

Depending on the thresholds the algorithm reduces a lot more in rather flat areas and not so much in curved areas.

Here are some links to the actual implementation:
http://voxels.blogspot.de/2014/05/quadr ... ource.html
https://github.com/sp4cerat/Fast-Quadri ... lification

So the FreeCAD Mesh code that performs decimation is the same as sp4cerat? i.e 4 x faster than MeshLab?

[wmayer]

So the FreeCAD Mesh code that performs decimation is the same as sp4cerat?

FreeCAD uses the modified sp4cerat code: https://github.com/sp4cerat/Fast-Quadri ... Simplify.h