CGAL
Gsoc2025 vmas skeleton qhuang
Summary of Changes
Add a new package in CGAL implementing the variational skeletonization algorithm described in Qijia HUANG, Pierre KREAMER, Sylvain THERY, Dominique BECHMANN, Dynamic skeletonization via Variational Medial Axis Sampling In Siggraph Aisa 2024, Tokyo.
Release Management
- Affected package(s): New package
- Feature/Small Feature (if any): To do
- Link to compiled documentation (obligatory for small feature)
- License and copyright ownership:
TODO
- [ ] CHANGES.md
- [ ] Feature page
- [ ] decide what to do with AABB-tree version now that we have sampling in faces
- [ ] check branch size
- [ ] look at the surface bug in the oracle for mesh_3 (filtering with upper bound spheres does not work as expected)
- [ ] move winding numbers in PMP
- [ ] Fix the projection on the sphere.
There was an error while building the doc:
/home/runner/work/cgal/cgal/AABB_tree/include/CGAL/AABB_tree.h:461: warning: Member accelerate_distance_queries(ConstPointIterator first, ConstPointIterator beyond, PointMap pmap) (function) of class CGAL::AABB_tree is not documented.
/home/runner/work/cgal/cgal/Variational_medial_axis/doc/Variational_medial_axis/PackageDescription.txt:33: warning: Found unknown command '\cgalCPRSection'
https://github.com/CGAL/cgal/actions/runs/17037263280
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
There was an error while building the doc:
/home/runner/work/cgal/cgal/AABB_tree/include/CGAL/AABB_tree.h:461: warning: Member accelerate_distance_queries(ConstPointIterator first, ConstPointIterator beyond, PointMap pmap) (function) of class CGAL::AABB_tree is not documented.
https://github.com/CGAL/cgal/actions/runs/17040907874
There was an error while building the doc:
/home/runner/work/cgal/cgal/AABB_tree/include/CGAL/AABB_tree.h:464: warning: Member accelerate_distance_queries(ConstPointIterator first, ConstPointIterator beyond, PointMap pmap) (function) of class CGAL::AABB_tree is not documented.
https://github.com/CGAL/cgal/actions/runs/18689883155
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v0/Manual/index.html
@afabri If you mean the collaborator rights for my personal fork of cgal/CGAL, it’s done.
There was an error while building the doc:
/home/runner/work/cgal/cgal/Variational_medial_axis/doc/Variational_medial_axis/Variational_medial_axis.txt:58: warning: unable to resolve reference to 'Medial_Skeleton' for \ref command
https://github.com/CGAL/cgal/actions/runs/18720905537
There was an error while building the doc:
/home/runner/work/cgal/cgal/Variational_medial_axis/doc/Variational_medial_axis/Variational_medial_axis.txt:58: warning: unable to resolve reference to 'Medial_Skeleton' for \ref command
https://github.com/CGAL/cgal/actions/runs/18722430439
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v1/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v1/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v1/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v1/Manual/index.html
Prereview of the Reference Manual
extract_variational_medial_skeleton()
number_of_spheres
- What does desired mean? Will there be the desired, or sometimes/always more or less
- Why default 100. Should that not depend on the size of the mesh?
- Why less than 300 Does the runtime depend on it?
number_of_samples
- So there will be in any case 10K sample points?
number_of_iterations
- The Default 1000 must be explained. Is it independent from the number of triangles and desired spheres? What happens when I double the number? Does the skeleton stop evolving? Does it get more or more detailed? ... .
- There is also a maximum_number_of_iterations. So does it stop before when it converged to something stable?
In fact you have this sentence in the reference manual page of the class, but I started reading the function "The process terminates when either the desired number of spheres is reached, or a maximum number of iterations is exceeded." And there is also the Note. This one mentions coarse. But coarse should depend on the face count of the input mesh
lambda
-
SQEMand Euclidean energy termsSQEMmust be explained or at least de-acronymized
I did not find the definition of Sphere_id
Don't we need a named parameter geom_traits ?
As we have a CGAL::Kd_tree_tag the CGAL:: BVH_tag should maybe become CGAL::AABB_tree_tag
I do not understand why the MedialSkeleton has the TriangleMesh as tparam.
The title is Dynamic Skeletonization Via Variational Medial Axis Sampling and the short description is
a dynamic approximation of the medial axis inspired by variational shape approximation
This is too much a permutation of words with some words removed others added.
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v1/Manual/index.html
The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9029/v1/Manual/index.html
Prereview of the Reference Manual
extract_variational_medial_skeleton()
number_of_spheres
- What does desired mean? Will there be the desired, or sometimes/always more or less
“Desired” means the number of spheres the user wishes the skeleton to contain at the end of the algorithm. he algorithm attempts to reach that count and converge; however, it may fail (e.g., due to insufficient samples or non-convergence), so the final number of spheres is ≤ desired.
- Why default 100. Should that not depend on the size of the mesh?
This number is independent of the mesh size; it only specifies the target count of spheres in the final skeleton. The default of 100 is a pragmatic starting point and can be adjusted by the user.
- Why less than 300 Does the runtime depend on it?
Most of our benchmarks use between 100 and 200 spheres. The method assumes the number of surface samples is much larger than the number of spheres; if samples are too few, some clusters can become “hungry,” making the optimization ill-conditioned. Runtime naturally increases as the number of spheres grows.
number_of_samples
- So there will be in any case 10K sample points?
Yes, by default we draw 10k samples.
number_of_iterations
- The Default 1000 must be explained. Is it independent from the number of triangles and desired spheres? What happens when I double the number? Does the skeleton stop evolving? Does it get more or more detailed? ... .
The iteration budget scales with the desired number of spheres, not with the triangle count. We start from one sphere and grow the skeleton in batches: every 10 iterations (or once the current batch has converged), we add 10 new spheres. For “few hundred” spheres, 1000 iterations typically suffice. If you increase the cap, the algorithm can continue refining, but it may already have converged earlier.
- There is also a maximum_number_of_iterations. So does it stop before when it converged to something stable?
number_of_iterations is the maximum number of iterations. We also stop early when the residual drops below a threshold (converged → return true), otherwise we return false.
In fact you have this sentence in the reference manual page of the class, but I started reading the function "The process terminates when either the desired number of spheres is reached, or a maximum number of iterations is exceeded." And there is also the Note. This one mentions coarse. But coarse should depend on the face count of the input mesh
I'm not sure that i understand this question, but when I mentioned "coarse", I usually talk about the skeleton, but not the input mesh.
lambda
SQEMand Euclidean energy termsSQEMmust be explained or at least de-acronymized
ok. I will add the full name (Spherical Quadric Error Metric)
I did not find the definition of
Sphere_id
Sphere_id is the index of a sphere in the skeleton. I can add a one-line definition
Don't we need a named parameter
geom_traits?
At the moment we rely on the kernel implied by TriangleMesh but why not?
As we have a
CGAL::Kd_tree_tagtheCGAL:: BVH_tagshould maybe becomeCGAL::AABB_tree_tag
OK.
I do not understand why the
MedialSkeletonhas theTriangleMeshastparam.
Because by defalut we rely on the kernel implied by TriangleMesh. I don't know if there a better way to do it.
The title is Dynamic Skeletonization Via Variational Medial Axis Sampling and the short description is a dynamic approximation of the medial axis inspired by variational shape approximation This is too much a permutation of words with some words removed others added.
OK, I can delete the end of the line. It will just be "The package provides an implementation of a dynamic approximation of the medial axis "
We already have a package with the title _Triangulated Surface Mesh Skeletonization_. This one should be renamed to Triangulated Surface Mesh Mean Curvature Skeletonization, and the package of this PR to Triangulated Surface Mesh XXXX Skeletonization. The "Dynamic" is not needed.