search

CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
4.87k stars 1.38k forks source link

Is there a function that does inverse subdivision? #3577

Open jasjuang opened 5 years ago

jasjuang commented 5 years ago

Issue Details

Suppose the vertices in my mesh have corresponding UV and I am trying to animate the mesh while maintaining the UV. Since the motion can be non rigid so the first step I did is using Catmull-Clark Subdivision as shown in https://doc.cgal.org/latest/Subdivision_method_3/index.html so I can maintain the UV and avoid stretched triangle when animating the mesh. The problem is after animating the subdivided mesh, I want to apply an "inverse" subdivision to bring the triangle count back down, and ideally "inverse" subdivide less on triangles with larger area and "inverse" subdivide more on triangles with smaller area. Does CGAL provide this kind of functionality?

Note that remeshing or mesh decimation doesn't work in this case because UV cannot be maintained. Hence the need of an "inverse" subdivision to maintain the UV.

Environment

lrineau commented 5 years ago

I think @afabri has implemented an experimental code doing exactly that, if I remember well. Andreas, did it work?

afabri commented 5 years ago

I recorded edge collapse operations for undoing them, so that one can run the Surface Mesh Simplification algorithm. The idea is to store the local context of each call of Euler::collapse_edge(), to have the information at hand to do the inverse operation. Note that one cannot store a Halfedge_handle after the edge collapse, as it might be collapsed after the current collapse.
A minor problem was that it needs the call of three Euler operations to undo Euler::collapse_edge(). Additonal complexity comes from the fact that the subdivision package uses more low level operations than Euler operations. Could be an intersting GSoC 2019 to implement this, and I would be willing to mentor it.

gdamiand commented 5 years ago

It is possible (and not so hard) to define the inverse of the edge collapse as a direct euler operation (we called this operation expansion in one of our paper).