Straight skeleton?

[niklasvh]

Did you end up creating a full working implementation of the straight skeleton algorithm? I see there's a lot of the parts needed for it here, but was it completed, working for both concave/convex polygons?

[triffid]

No, sorry I haven't. I've been side-tracked by other projects.

I will be getting back to it soon though, once netrap is in a more mature state

If you want to give me a hand, that would be most appreciated :)

In truth, I was hoping that someone else would write one before I got back to it!

On Fri, Aug 3, 2012 at 9:26 PM, Niklas von Hertzen reply@reply.github.com wrote:

Did you end up creating a full working implementation of the straight skeleton algorithm? I see there's a lot of the parts needed for it here, but was it completed, working for both concave/convex polygons?

---

Reply to this email directly or view it on GitHub: https://github.com/triffid/WebSkein/issues/1

[niklasvh]

Haha, I know what you mean. It certainly sounds lot easier on paper than actually implementing it.

Do you recall how far you got into implementing it, what is still missing?

[triffid]

The motorcycle graph algorithm is functioning, but crude. it runs through all the vertices way too many times for my liking while building it, certainly far too many times to achieve the efficiency I want from it. I'm sure there's a way to hugely simplify that, haven't looked into it just yet, was too busy just getting the thing working in the first place!

Working out a sensible data structure to step from the motorcycle graph to the full straight skeleton, as well as extending the motorcycle graph in both directions is where I stopped. When running the graph, we need to be able to add and remove nodes from the various lists, preferably without altering the original graphs since we will want to reuse them for other operations.

It's not like we're just going to take the outline and offset it a couple of times in the same direction for the perimeters- once we have outlines, we will propagate them up and down through the stack of layers and do boolean ops with the regions on those layers to discover regions of top/bottom solid infill, bridges, overhangs, etc etc, so it's important that we preserve the skeletons so we can reuse them.

I find it somewhat ironic that the trickiest part of the whole slicing process is this polygon offset routine!

On Fri, Aug 3, 2012 at 9:42 PM, Niklas von Hertzen reply@reply.github.com wrote:

Haha, I know what you mean. It certainly sounds lot easier on paper than actually implementing it.

Do you recall how far you got into implementing it, what is still missing?

---

Reply to this email directly or view it on GitHub: https://github.com/triffid/WebSkein/issues/1#issuecomment-7481477

[niklasvh]

Thanks for the update. I'll see whether I can come to a work around without using straight skeletons, but else I'll probably end up either continuing your implementation or make one from scratch. I'll keep you updated in case I'll end up working on an implementation.

[triffid]

It's one thing to be able to move vertices along the bisectors, it's quite another to know when a reflex vertex has met a segment coming from the other side and it's time to split the polygon in two.. That's an N^2 or maybe even N^3 operation if we skip the motorcycle graph!

The straight skeleton algorithm uses the motorcycle graph to predict when those events will occur so we don't have to keep searching for them, by inserting extra vertices into the original outline that will eventually converge on that split event

On Fri, Aug 3, 2012 at 11:38 PM, Niklas von Hertzen reply@reply.github.com wrote:

Thanks for the update. I'll see whether I can come to a work around without using straight skeletons, but else I'll probably end up either continuing your implementation or make one from scratch. I'll keep you updated in case I'll end up working on an implementation.

---

Reply to this email directly or view it on GitHub: https://github.com/triffid/WebSkein/issues/1#issuecomment-7483515