cgal
cgal copied to clipboard
CGAL
Allow manually fixing a range of vertices, when using `Mean_curvature_flow_skeletonization`
This patch allows manually fixing a range of vertices, preventing them from moving during contraction when using Mean_curvature_flow_skeletonization. Naturally, this will prevent convergence towards the skeleton, but its intended use is in cases where one is interested in the meso-skeleton and needs to keep part of it fixed, similar to the vertex_is_constrained_map named parameter of many functions. (My current use for it, is in combination with smooth_shape, which is essentially complementary to it and already has the aforementioned vertex_is_constrained_map feature, to achieve relatively uniform contraction of a mesh, keeping a part of it fixed.)
The implementation is trivial, since it uses an existing part of the algorithm and it seems to work as expected in the cases I've tried. The only issue is the interface. I've mimicked the interface of the surface deformation package (as in insert_roi_vertices for instance), but perhaps you'll have a better suggestion. The current implementation has the minor drawback of requiring the creation of a set with the given descriptors, plus a pass through the mesh vertices, which could probably be avoided if the fixed vertices were available during initialization (when copying the input mesh in init()). Other than that the implementation should be ok in terms of operation, as far as I can see.
Let me know if you'd like me to make additional changes; this is only meant as a proof of concept implementation.
Concerning the API maybe a property map with vertex_descriptor as key type and bool as value type would be better?
That was my initial approach, but I decided against it, because I didn't see it used anywhere else for a vertex-is-constrained sort of map. It will have the advantage of making the implementation a bit more straightforward. I'll give it a try.
I've force-pushed a new take on the implementation. The existing code seems to be broken in that the VertexPointMap parameter is passed to init(), which no longer accepts it. I added a fix as a separate commit, which is just guesswork really, as I'm not sure how this parameter needs to be handled, having never had use for it. Please review and advise if changes are needed, or feel free to make them yourself. Also let me know if you'd like me to turn this into a separate PR.
Pinging this, in case it has slipped attention. I'm still very much interested in getting this through (if it is considered acceptable), as I'm already using it at my end.
Could this be a simple member function rather than a parameter of the constructor? That would avoid breaking the API.
It can; in fact that's how it was in the first iteration, before I changed it based on the suggestion of @afabri above. I can change it back if you want, as that approach is equally good, if not better. For reference, this is the impementation:
+ /// \cgalAdvancedFunction
+ /// \cgalAdvancedBegin
+ /// Fixes a range of vertices. Fixed vertices will not be moved
+ /// during contraction and this will therefore prevent convergence
+ /// towards the skeleton if `contract_until_convergence()` is used.
+ /// It is only useful if the object is to retrieve the meso-skeleton
+ /// after a number of `contract_geometry()`, keeping the specified
+ /// vertices fixed in place.
+ /// \cgalAdvancedEnd
+ template<class InputIterator>
+ void set_fixed_vertices(InputIterator begin, InputIterator end)
+ {
+ std::unordered_set<Input_vertex_descriptor> set(begin, end);
+
+ for(vertex_descriptor vd : vertices(m_tmesh))
+ {
+ if (set.find(vd->vertices[0]) != set.end()) {
+ vd->is_fixed = true;
+ }
+ }
+ }
The above has the advantage of allowing one to run a few contraction steps with no fixed vertices say, before fixing some of the partially contracted vertices and contracting the rest some more, or other similar combinations. This is arguably very "advanced" usage, but it doesn't cost anything much to support it either. All of this depends on Skel_HDS_vertex_type::vertices[0] remaining unchanged throughout contraction, but, as far as I can tell, this seems to be the case.
Note though that:
- as far as I can see, the current approach doesn't break the API either; it merely extends it.
- irrespective of the followed approach and the new functionality in general, the first commit of the current PR introduces a fix that is necessary (although it may not be correct, as I have explained above).
I also prefer the first version that does not impact people not fixing any vertex
I also prefer the first version, although, to reiterate, I can't see how the current version impacts the main use-case of not fixing vertices either. In any case, please let me know if it's decided that I should revert the PR to the previous approach and I'll do so.
The current version (using the constructor) does break the API in the sense that if you previously constructed the class with a Traits, it would no longer compile.
Also in the current implementation, you use a property map, but you use a range for the version using the member function. You could also be using a property map in the member function and that would avoid the set. The choice of set vs property map will depend on whether these fixed vertices are usually many or very few.
The current version (using the constructor) does break the API in the sense that if you previously constructed the class with a Traits, it would no longer compile.
You're right of course; I though the API was broken for the unconstrained use-case in general.
You could also be using a property map in the member function and that would avoid the set. The choice of set vs property map will depend on whether these fixed vertices are usually many or very few.
I'm not very familiar with property maps and their various types, but from what I've seen, I'd expect one would typically use a set-backed property map anyway. That said, having the member function accept a property map might still be advantageous, as it would allow reusing a set of the fixed vertices which the user might already have available. It would also be more flexible in general.
On the other hand, similar existing APIs, such as the interface of the surface deformation package (as in insert_roi_vertices for instance) use a range, and I haven't seen any member functions accepting property maps, so it seemed to me that using a property map here, would make the API less consistent. In the end they're all good choices though, and I can implement any of them if it is preferred.
From the preceding discussion, I get the impression that the original implementation is favored. I've therefore reverted the PR to the original implementation, keeping the commit that fixes the handling of the VertexPointMap parameter. I stress again, that this fix is mostly guesswork; it compiles, but I'm not sure it works as intended as I haven't studied the use-case. Please check whether anything else is needed and let me know.
I've tested the new member function and it works as expected. Let me know, if you'd like me to change anything else.