How to use PyMeshLab to reduce vertex number to a certain number

[jmespadero]

This script was created as side result of this question in stackOverflow about how to decimate a mesh (reduce the number of vertex and faces) to a target number of vertex choosed by the user.

The question can be summarized as: "I know I can use simplification_quadric_edge_collapse_decimation filter to reduce the face number which means the vertex number will be reduced accordingly. But the problem is that I have to use the method several times in order to get the vertex number exactly down to 10000."

The decimation algorithm in meshlab/pymeshlab is based on Michael Garland's QSlim algorithm, which is based on Edge Collapse operations to perform the decimation using smalls step and a smart way to keep track of the amount of error introduced by current and previous steps.

As you can see in the image below, the Edge Collapse operator reduces in two the number of triangles in your mesh (one, if the edge is in the boundary) and reduce the number of vertices by one (two, if collapsing an edge of a isolated triangle make it to go banished) .

This means that it is possible to estimate how many edge collapses we need to apply to reduce the number of vertex, but... we can't feed that number to the algorithm, only the desired number of faces of the mesh. Both values are correllated but the exact number of steps depends of the presence of boundaries, and this depends on the geometry of the mesh.

So the idea is to implement a "soft landing" algorithm that reduce the number of faces in batches whose size depends of the excess of vertex (the current number of vertex minux the desired number of vertex), decreasing the size of the batch until the vertex count converges into the target.

import pymeshlab as ml
ms = ml.MeshSet()
ms.load_new_mesh('input.ply')
m = ms.current_mesh()
print('input mesh has', m.vertex_number(), 'vertex and', m.face_number(), 'faces')

#Target number of vertex
TARGET=10000

# Clean-up in case of input has duplicate/unreferenced vertices
ms.meshing_remove_duplicate_vertices()
ms.meshing_remove_unreferenced_vertices()

#Initial estimation number of faces, designed to be superior than the teorical value
numFaces = 100 + ms.current_mesh().face_number() - (ms.current_mesh().vertex_number() - TARGET)

#Simplify the mesh
while (ms.current_mesh().vertex_number() > TARGET):
    ms.meshing_decimation_quadric_edge_collapse(targetfacenum=numFaces, preservenormal=True)
    print("Mesh decimated to", numFaces, "faces contains", ms.current_mesh().vertex_number(), "vertex")
    #Refine our estimation to slowly converge to TARGET vertex number
    numFaces = numFaces - (ms.current_mesh().vertex_number() - TARGET)

m = ms.current_mesh()
print('output mesh has', m.vertex_number(), 'vertex and', m.face_number(), 'faces')
ms.save_current_mesh('output.ply')

This is the result applied to the Pythagore model courtesy of Geoffrey Marchal...

Please, note that:

• Sometimes you just can't reduce exactly to the desired number vertex, and will end with one less vertex.
• With this formula, each step will remove about half of the vertices exceeding TARGET, giving a "soft landing" into your desired number of vertices. A typical execution should reduce to about 10050 vertices, then 10025, 10012, 10006, 10003, 10001, and finally 10000 vertices. The final number of faces depends of the said Euler Characteristic of the input model.
• Only the first simplification step will take significant execution time (depending of number of triangles in the input mesh), and next simplification steps will be very fast.
• If you still want to speed-up the method you can do numFaces = numFaces - int(1.5*(ms.current_mesh().vertex_number() - TARGET)), but this increases the chances of ending under 9999 vertex and execution time won't be affected much.
• This method should work with any decimation algorithm based on faces, it is not exclusive for quadric edge collapse.