I would like to ask about 2D skeletonization.
I know this issue was addressed in quite a lot of threads by @laurent_delrieu and @DanielPiker.
The issue:
I have quite standard cases of 2D outlines resulting in forks and beams, but during the pruning process I most often have some little branches left. So it is not clear how many pruning steps are needed or whether the result would be good. More simply, it is difficult to have an error-less process when i.e. a beam would result in 1 central curve, or fork - 3 central curves. Smoothing of polylines does not help much either.
For now I was doing mesh triangulation from closed polyline, and extracting skeleton based on mesh face adjacency.
I attached the set of 2D curves I have in Rhino file.
I also tried Capybara plugin on 3D closed meshes, but the CGAL wrapper does not work on some computers, so I would like to stay with 2D cases.
You need an error function that works for any arbitrary skeleton. This means that you must take into account general aspects, such as scale restrictions, length or angle thresholds, deviations, etc., that fit for your intended use. I don’t think there is a general error function (at least one parameter-free), I think you should define it yourself or change to a better method to extract the medial axis.
My point, stated differently, is that you have so many factors to play with that you need to restrict the problem as much as possible and a good way is to adapt it to your particular problem (your scale, what you expect… all the parameters adapted to your model).
However, I find it strange that simplifying the curve does not help. I don’t mean using the simplify curve component, but a custom simplify method that fits the criteria you need, like preserving the corners for example.
It is more stable but you need to convert to pixels/voxels , solve, and then convert back the points into curves. Even this last step alone is not easy.
Anyway.
Here: https://rosettacode.org/wiki/Zhang-Suen_thinning_algorithm it says that the method have a “circular” check on variation of neighbor values …
The neighbors of a voxel would be other 26 voxels, a 3x3x3 cube. But the cube vertexes have only 3 connections, leaving uneven amount of circular check or using some voxel value twice.
Or you can just do the circular check on the 3 planes having the starting voxel as center…
Computation time will increase by a scary amount.
Thanks @maje90, on 2D case it is rather slow, I will not try the 3D one as you suggest.
For creating a curve, I might try to create a graph and then find connected-components, but I am not sure if that even works. Do you have any suggestions regarding conversion from pixels to curves?
One common interpretation of the medial axis is actually “…the locus of the centres of maximal circles”. See for instance this paper by Pablo Miranda Carranza:
Thank you for the references, maybe you have a code to test?
I wondering if this would work when outlines are very irregular? The prunning in that case often have lots of little branches. I am projecting 3d cloud to 2d, then applying 2d marching squares to get a mesh, from that I get the biggest outline for the skeleton.
I think the idea in the paper I linked above was to prune based on the angle between the 2 lines from the centre of the circle to the 2 closest points on the curve.
Any point which can have circle centred on it tangent to more than 1 point on the curve is part of the medial axis, but I think if the angle between these lines is small, it is more likely to be just a bump rather than what you want as a real branch
Reducing small features (and/or smoothing out) of the input domain geometry is definitely a good idea to reduce the complexity of the medial axis. Or just having clean/minimal inputs in the first place, which is admittedly easier to ensure with e.g. floor-plans (which has been my main application of the medial axis).
I’m afraid the stuff I wrote is owned by my old employer. That said, I think the stuff Pablo did was made open source as I recall (as part if the EU project we both contributed to). Also, here’s the presentation for the paper I wrote that expands a bit on the modelling steps:
