Discussion about Medial Axis

While looking around the net for Medial Axis stuff... I found some promising source-code implementations of the Delaunay + Voronoi diagram stuff...

I actually stumbled on this on Stack Overflow:

This solution assumes that you have a data structure that represents the Delaunay triangulation using a "virtual infinite Delaunay vertex" the way CGAL does it (see details here).

The idea is to find the boundary Delaunay edges: the edges connecting two consecutive sample points; and then "flood" through the Delaunay triangulation to classify the Delaunay faces. One knows that the infinite vertex is exterior so one can classify its neighbors (and neighbors' neighbors, etc.) as exterior as long as one does not cross boundary edges. If one reaches a boundary edge one can simply mark the neighbor triangle as interior and continue similarly.

Input: set of points densely sampling of the boundary of a closed shape, which can even contain holes Output: Voronoi diagram in the interior of the shape (approximation of the medial axis of the shape)

Compute the Delaunay triangulation of your points Mark the Delaunay edges which connect two consecutive sample points. (See page 4-5 of this paper how you can do this with a local test on every Delaunay edge) Classify all infinite Delaunay faces as OUTSIDE and push them to a queue Q. While Q is not empty Delaunay face f = Pop from Q For every unclassified neighbor triangle t of f if the Delaunay edge shared by t and f is marked, classify t as the opposite of f else classify t the same like f push t to Q For every Delaunay edge e if the two neighbor Delaunay triangles d1, d2 are both classified as INTERIOR, output the segment connecting the circumcenter of d1 and d2. For an input like this

Which led to:

https://code.google.com/p/mesecina/ Example

Isn't this exactly what we're after? - I mean... if we're doing medial axis, we already know the region is smaller than 2 perimeters, and we can test if the distance from any point on the medial axis to our perimeter is above a threshold... or not... maybe just measuring the distance to the perimeter gives us the perimeter width.

would be nice if we could have a flow rate that varies from start to finish ;)

anyway... hope this is helpful and isn't repeating what you already found... tried to find your email address, but apparently email is dead - so I had to converse by "issue"

thanks.

and a really really cool video about the Scale Axis Transform which is, as I understand it, a further refinement of the medial axis algorithm...

http://www.balintmiklos.com/scale-axis/theory_socg_2009.html#tab

REALLY cool info.

Sorry if my email address is hard to find. I do have it posted on this page: http://sheldrake.net/cardboards/candy.html In a hopefully mostly bot-invisible way.

There's a lot of cool stuff out there around medial axis. The first main thing you posted here is similar to what we can pull off with Triangle, or probably even the Math::Voronoi perl module. One issue is the adequate sampling of the polygon. You want to avoid oversampling if possible. Sampling at a low multiple of extrusion width gives way too many points in most cases.

Also, notice in the leaf image you posted how the medial axis approximation gets all zig-zaggy in the stem. That's not acceptable. Currently Slic3r tries to straighten this out with a combination of high sample resolution and simplification of the result - lots of extra work and memory, and it doesn't always work well.

The mic_adjust() utility I've worked up for this perl module straightens out the medial axis approximation from a lower-resolution sampling, giving much better results without having to turn the resolution up too much. It's got a few glitches - certain combinations of shape features still cause irregularities in the medial axis result. But over all, it seems to work well.

The Scale Axis Transform is trying to simplify the medial axis with the assumption that the original shape is a mostly a smooth curve, or should be a smooth curve, or we'd rather it was a smooth curve. I'm currently focusing on the medial axis of polygons taken to actually be polygons, with straight segments and real corners at all the points where segments meet - and not as approximations of curves. For Slic3r, I'm taking the slice polygons from the model to be authoritative. Until we eventually get into curved facets in models, that means everything for now is a straight segment or point, and any smoothing or simplification of the medial axis is likely to lose important information.

For polygons, all those medial axis "hairs" that shoot off the main central branches are actually significant - I'm not looking to filter them out. Also, they are important for getting a representation of the polygon that's compatible with the offset perimeter polygons we get from Clipper.

Currently I'm working with Boost::Polygon's Voronoi diagram code to get a medial axis out of that. It gives better results for a Voronoi diagram that's supposed to respect segments as well as points. Triangle is aware of segments with regard to the Delaunay triangulation, but not the Voronoi diagram. Mic_adjust() uses features of both to make the adjustments needed for a decent medial axis. But Boost::Polygon::Voronoi uses an algorithm that takes segments into account completely from the start.

(I'm not implying a deficiency in Triangle. It's not designed as a medial axis generator. It's just a pretty good base for rolling you own approximator. It's real strength is mesh generation.)

Regarding variable width perimeters - we can see that on the horizon. It's just not as simple as it seems.

Actually the primary purpose of the scale axis is to eliminate the hairy medial axis without losing finer details on the perimeter. In other words, noisy perimeters give rise to noisy medial axis that we don't want to clean up. Scale Axis eliminates the unimportant hairs while preserving most important medial axis bits.

It's also does a pretty good job of straightening out the medial axis within features like the stem.

But regardless - sounds like you've got something that is promising with your Mic_adjust().

question though - what's the issue with a zigzag if it's really supposed to be there? other than potentially hitting a physical limitation of the printer?

Zigzag, as seen in the stem of the leaf above, comes from using the Voronoi diagram of the polygon's points as the basis for the medial axis approximation, without regard for the segments between the points. In other words, there is no polygon in that case, only a collection of points. If you try to draw maximal inscribed circles at the resulting voronoi vertices, you generally won't be able to do it - you won't be able to size the circle to just touch at least two segments at once, because the circle centers were derived from the points, not the segments.

What we really want to start with is the Voronoi diagram of the polygon's segments. Higher point sampling approximates this. Mic_adjust() corrects toward that ideal. But Boost::Polygon::Voronoi provides this as part of the initial sweepline processing of the original polygon.

"Hairs" are important - all of them. That's the approach I'm taking. They represent quantized curvature, and with them you can reproduce the exact original polygon, plus a whole family of nested polygons in relation to it. Approaches to eliminating them amount to smoothing and loss of information, and bring up the tricky problems about what features and feature scales are significant.

Look at the giraffes on the top of the scale axis page. If those back legs are "thin walls" in the 3D printing context, we have to somehow determine the correct scale axis factor to use so that we preserve the distinct medial axis sections going into the two legs, and preserve the proper point where the medial axis forks there. s=2.9 looks promising for the legs, but leaves out the ears. If it turns out s=2.75 works well for the giraffe, there's no guarantee that same factor will work for the legs on a spider, or the arms of a snowflake.

mesheldrake / Math-Geometry-Delaunay

Discussion about Medial Axis #3