How to use PyMeshLab to reduce number of faces to a guaranteed specific number

Question

I have a 3D triangular mesh in PyMeshLab that I want to decimate to a certain number of faces. The number of faces after decimation is not guaranteed - which is a problem for me. I need a specific number of faces.

I'm currently using simplification_quadric_edge_collapse_decimation, however the exact number of faces after the operation is not guaranteed - so often I get a total number of faces that is 1 smaller than the desired number. Are there any good ideas on how to approach this, e.g. by using other filters, pre/post-processing to get the exact number of faces - guaranteed, or something else ;-)

Answer 1

First, you need to understand how the simplification_quadric_edge_collapse_decimation method works. It is based on Michael Garland's QSlim algorithm, which is based on Edge Collapse operations to perform decimation using small steps.

As you can see in the image below, the Edge Collapse operator reduces the number of triangles in your mesh in two. And that's the reason you can not choose the exact number of triangles in the decimated mesh: sometimes you are "one triangle above your target number of triangles" and applying the operator will let you at "one triangle below your target".

Although it looks like "Edge Collapse Decimation" will produce a mesh with the same parity in the number of faces than the initial mesh, this is not always true. When you apply one Edge Collapse operator, it will remove two triangles if the edge is internal (shared by two triangles) but will remove just one triangle if the edge is in the boundary of the mesh. This means that if your mesh has boundaries, you have can end with a parity different of the initial mesh.

My proposal: Decimate your mesh to your target number of triangles, and if you fall below the desired number add one triangle to the mesh. If you have boundaries, you can select one triangle in the boundary and apply just one step of midpoint subdivision. This should affect only one the external edge of the selected triangle, as seen in the image below:

This is the code that implements this method to achieve the precise decimation:

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

#Reduce to TARGET. Sometimes will fall into TARGET-1
ms.meshing_decimation_quadric_edge_collapse(targetfacenum=TARGET, preservenormal=True)

#Check if we need to increase the number of triangles by one
if ms.current_mesh().face_number() < TARGET:
  #Select the boundary of the mesh
  ms.compute_selection_from_mesh_border()
  if ms.current_mesh().selected_face_number() == 0 : 
      raise("No boundary")
  #Choose one triangle from the boundary
  t=next(i for i,x in enumerate(ms.current_mesh().face_selection_array()) if x )
  #print("Subdivide the boundary triangle", t)
  ms.compute_selection_by_condition_per_face(condselect=f'(fi == {t})')
  ms.meshing_surface_subdivision_midpoint(iterations=1,threshold=ml.AbsoluteValue(0),selected=True)
  
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 input and output for Pythagoras mesh (342,297 triangles), given a target number of triangles (6789) that needed the correction step.

If some of your meshes has no boundaries, you may be in a problem if you try to change the parity of the number of triangles.