Keeping track of the history of edge's collapses

[Louis-Pujol]

Hello,

First of all thank you for this very nice python wrapper of fqmr. For one of my projects, I need to decimate triangular meshes and keep the history of the successive collapses. This can help for various tasks :

• It allows to "replay" the decimation process and make accessible intermediate states of the mesh between the input and the output
• It allows to compute a map from the vertices of the input and the one of the output. In my application some vertices of the input are marked as landmarks and I want to conserve these landmarks on the output
• If one has a collection of registered meshes (as the SCAPE dataset) it allows to simplify one mesh and apply the same simplification process to the other meshes. This results in a collection of simplified registered meshes

I created a fork of this repository here to implement a version of simplification with collapses recording. I modified the code of fast_simplification in order to be able to access the collapses history, encoded as a (n_collapses, 2) integer array. If collapses[j] = [i0, i1], it means that the (j+1)th collapses edge was (i0, i1) with the convention that the index of the point resulting from the collapse is i0.

• In Simplify.h : a global variable collapses (vector<vector <int>>) is created and when a collapse occurs in the function simplify_mesh it is updated with collapses.push_back(std::vector<int>({i0,i1}));
• wrapper.h, _simplify.pyx are modified to make accessible collapses in python. get_collapses() and return_collapses() functions are defined in the same way as get_points(), get_triangles(), return_points(), return_triangles()
• The python interface in simplify.py is modified to make access to collapses. In simplify(), I have added an argument return_collapses (default to False). If return_collapses is True, then the output of simplify is (points, triangles, collapses) instead of (points, triangles). In simplify_mesh(), I added collapse as a field data of the output mesh

All the tests previously defined still pass and I added two tests to check that input.n_points - n_collapses = output.n_points in a separate test file

Do you think this could be pertinent to merge these modifications to fast_simplification ?

Having access to collapses is a first step for the tasks I mentioned above. I am working on implementing these based on the (points, triangles, collapses) information in another repository (it is a draft for the moment). Maybe it could be of interest to also add these to fast-simplification in the future ?

Thank you,

[akaszynski]

I'd welcome these changes. If you'd like, please submit a PR with the changes and I'll be sure to review it.

[akaszynski]

Thanks for your work. v0.1.1 should be out on PyPI shortly. When you get a chance, please verify the built library.

[Louis-Pujol]

Thanks, I've tested it on Ubuntu with python 3.8 to 3.11 and it worked well.