Hi Michael,
Sorry for the delay! I didn't even know there was an embroidery LPE. I don't see it in 0.92.1... how can I test it out?
The extension that Susan was referring to is here: https://github.com/lexelby/inkscape-embroidery
It started off as a little project by jonh, and then it migrated to github, and then I forked it and hacked the heck out of it. I've rewritten most of the major sections at this point.
For exporting, I'd recommend you examine embroidermodder2. That project seems to be mostly abandoned at this point, but it does have a nice little library that understands all major (and many minor) embroidery machine file formats. You may even be able to get it to convert directly from an SVG to a .PES file, for example. I included some details on this in my README.
The math problem I'm having has to do with fill stitching. The general problem is: how do I fill a generic shape with rows of stitches? The specific parameters are:
1) Stitch back and forth (like mowing a lawn). 2) Don't cut the thread. 3) Don't sew over the same section twice. 4) Don't do running stitch over the top of areas you've already done rows of stiches on. 5) Line all the stitches up to make a visually pleasing pattern.
I have an implementation already, described here: https://github.com/lexelby/inkscape-embroidery#autofill
This works pretty well. Give it a region and it will break it up into sections (each of which by itself can be filled all in one go). To get between sections, it runs around the outline of the shape. The idea here is that usually, one will do satin stitch around the outside of a fill region, covering up the running stitches.
As described in the README, the problem is when you give it a region with holes in it. Things get very complicated, and I have yet to come up with an algorithm that a) can reliably fill all regions without getting "stuck" with nowhere to go, and b) doesn't take forever to run.
Right now, my hacky workaround is to convert a region with holes into one without holes by cutting a very small rectangular section out of the shape (see the README). This works, but it's not ideal and it requires a lot of extra effort on the part of the user.
The ideal solution would somehow figure out an ordering for embroidering the sections, such that every section gets filled in but none of the rules above are violated. Bonus points if it can avoid running around the outside of the shape to get between sections. It would instead run through the middle of regions of the shape that have not yet been filled in, so that the running stitch gets hidden by the rows of stitches that are filled in later.
The biggest problems I have yet to wrap my head around are:
1) How to avoid getting into recursive/NP-complete hell. Taking more than 10-20 seconds would really be a bad user experience; 2-3 seconds max is really what I'm aiming for. 2) How to figure out how to get from point A to point B inside a closed polygon, running over only sections that haven't been filled in yet.
2 is especially hard for me, and I think it's the kind of thing that inkscape devs probably already know how to do! I really don't understand how I can do pathfinding in an arbitrarily complex shape like that without writing thousands of lines of code.
I know this kind of algorithm is possible. Commercial embroidery design software makes this look easy. I want to bring that to the open source world. I haven't been able to find any discussion of this kind of algorithm with repeated and creative googling. The closest I can think of is lawn-mowing algorithms, about which I found one paper that is unfortunately a bit beyond my level of math understanding.
Some examples of what I've made so far: https://github.com/lexelby/inkscape-embroidery/tree/master/images/patches
This one is an especially good example of a complex fill-region with a hole: https://github.com/lexelby/inkscape-embroidery/blob/master/images/patches/cl...
The black circular section in the center contains a hole in the shape of the white spade, because you can't do one color of fill-stitching on top of another. To make this, I manually broke the shape up into sections and tinkered with ordering until it worked out.
Anyway, thanks for listening, and any help would be appreciated! --Lex
On July 30, 2017 6:47:31 AM Michael Soegtrop <MSoegtrop@...3339...> wrote:
Hi Lex,
I did the embroidery stitching LPE and the path cutter LPE, both are very useful for embroidery design. What is the embroidery extension Susan mentioned below? Hope we didn't do the same thing.
Any discussions on the topic are welcome. What is the math issue?
My next plan is to write an export filter in some documented and common import format for stitching machines. Suggestions on the format are welcome.
Best regards,
Michael
On 28.07.2017 20:20, Susan Spencer wrote:
Hi Lex, This is the dev list for Inkscape. There's a wide range in backgrounds for devs here, and new contributors are welcome.
Hi devs, Meet Lex Neva, he's a fantastic programmer and has been contributing to the embroidery extension. He's done some mind blowing work with pattern fill. He's looking at a particular issue and has some questions for the math heads amongst you.
Good luck with 0.92.2 release!
Best,
Susan Spencer http://valentina-project.org http://valentina-project.org/