pyvista / fast-simplification

Fast Quadratic Mesh Simplification
https://pyvista.github.io/fast-simplification/
MIT License
108 stars 15 forks source link

Holes generation in flat geometries #39

Open AliE89 opened 3 months ago

AliE89 commented 3 months ago

Hello guys,

Thanks for this tool, quite interesting. Today, I was playing around and I noticed that fast_simplification produces holes in the geometry if operating on flat surfaces 2D surfaces. Does this ring a bell?

Commnad I ma using is simply: points_out, faces_out = fast_simplification.simplify(points, faces, 0.5)

Maybe I can add more flags to prevent this.

Many thanks.

AliE89 commented 3 months ago

image

Louis-Pujol commented 3 months ago

Hi !

Is it possible for you to share the input data ? It seems to me that if input does not have holes the algorithm should not create ones, it would be interesting to have a closer look at your example to figure out what's going wrong here.

AliE89 commented 3 months ago

Hello Louis,

sure, please find attached one stl you can play with. test.zip

It's likely I am mistaking something... sorry about that.

Cheers,

Louis-Pujol commented 2 months ago

Hi @AliE89,

Sorry for the late answer. I've written a script to understand what happened here. I wrote a count_holes function that counts the number of holes in a triangular structure using the topological data analysis library gudhi. Then I compare the result of decimation using fast-simplification and the decimate method of PyVista:

import pyvista as pv
import gudhi
import fast_simplification

def count_holes(triangles):
    """Count the number of holes in a triangle mesh"""

    st = gudhi.SimplexTree()
    for t in triangles:
        st.insert(t)

    st.compute_persistence()

    # The first Betti number is the number of connected components
    # The second Betti number is the number of holes
    return st.betti_numbers()[1]

# Load the data
mesh = pv.read("test0.stl")
points, faces = mesh.points, mesh.regular_faces

# Decimate with fast-simplification
points_out, faces_out = fast_simplification.simplify(points, faces, 0.5)
mesh_decimated_fast_simplification = pv.PolyData.from_regular_faces(
    points_out,
    faces=faces_out
    )

# Decimate with PyVista
mesh_decimated_pyvista = mesh.decimate(0.5)
points_out_pyvista, faces_out_pyvista = mesh_decimated_pyvista.points, mesh_decimated_pyvista.regular_faces

plotter = pv.Plotter(shape=(1, 3))
plotter.subplot(0, 0)
plotter.add_mesh(mesh)
plotter.add_text(f"Input: {count_holes(faces)} holes")
plotter.subplot(0, 1)
plotter.add_mesh(mesh_decimated_fast_simplification)
plotter.add_text(f"Fast-simplification: {count_holes(faces_out)} holes")
plotter.subplot(0, 2)
plotter.add_mesh(mesh_decimated_pyvista)
plotter.add_text(f"PyVista: {count_holes(faces_out_pyvista)} holes")
plotter.show()

And there is the result I obtain:

image

There, even if they are imperceptible, your input geometry has some holes, and the number of holes decreases after decimation. I am almost sure that there cannot be more holes after decimation than before. The operation of edge contraction described in this paper can fill holes but never create new ones.

The decimation algorithm of fast-simplification is a fast version of vtk QuadricDecimation (this is the method wrapped by pyvista). You can read more about the fast algorithm on the associated GitHub, where it is stated that: "It uses a threshold to determine which triangles to delete, which avoids sorting but might lead to lesser quality"

For your problem, you can use the slower decimation from pyvista that seems visually better or try filling the imperceptible holes in the mesh before decimation. You can try pymeshfix; I never use it so I cannot tell if it will work on your example.