Re: [Inkscape-devel] Embroidery extension
Ah, I see. My machine (a Brother SE400) can't cut the thread and continue stitching. It's a pretty difficult limitation to work with. I try to avoid jumps whenever possible, and when I have to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3339...> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver makes a jump. My machine can actually do jumps (knot the threads and cut them at both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just works on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote:
Hi! Sorry for going dark there -- everyday life intrudes fairly often.
Neato, and thanks for the explanation! It does indeed look like your stuff follows a similar method to inkscape-embroidery. A few minor differences:
- The extension handles creating a "grating" of lines automatically and
intersects them with the fill region using Shapely (a Python extension).
- The fill pattern is handled automatically through the insertion of
extra nodes as you mentioned. Currently there's only one pattern: a sort of stair-step/staggered pattern that is visually pleasing. I cribbed it off of a pattern I bought online that was made using a commercial embroidery design program. I'd love to understand how to code more complex patterns, but I haven't given much thought to it yet.
- The extension used to have a TSP solver of its own, but it really
didn't do a particularly good job. I started off trying to fix bugs and ultimately just ripped it out. Instead, I carefully order paths in Inkscape. The new Objects panel is key for this, and it's a hugely awesome addition to Inkscape! The only part I struggle with is that Inkscape doesn't want to let you reorder objects relative to each other if they don't intersect (or nearly intersect).
Ultimately, the problem I brought up for discussion boils down to the same problem you're solving with the your TSP algorithm. *Question: *what does your code do if it needs to get from one section to another that is distant? Does it just jump-stitch?
Here's a brief description of how to use EmbroiderModder2's libembroidery to convert between formats: https://github.com/lexelby/inkscape-embroidery#optional-conversion-program
I'd suggest that your code simply output a CSV in the format libembroidery understands, and then you can make use of its knowledge of pretty much every manufacturer format to convert it to a format compatible with your machine.
--Lex
On 7/30/2017 11:47 AM, Michael Soegtrop wrote:
Dear Lex,
I guess we are trying to solve the same problem, but differently. I wanted to have more control than semi automated fillers provide, so I added 3 LPEs, which are in Inkscape 0.92.2:
1.) A bool LPE to do intersections / unions, ... of areas, so that one can construct the areas to stitch from drawing areas.
2.) A path / path group trimmer LPE, which restricts a set of paths to an area (or oustide of an area. There are already two path interpolation LPEs which allow to create sets of paths with fine control over local direction and density.
3.) An LPE to convert a set of paths into stitches. This includes an almost reasonable traveling salesman problem (TSP) variant solver for ordering groups of stitches to minimize the traveling in between. It can still be improved. It is a bit more complicated than standard TSP solvers, because it looks into groups of parallel stitches which have 4 possible ends.
My approach is as follows
1.) Make a drawing
2.) Use the bool op LPE to create (in a new layer) the areas to fill with each color / stitch style.
3.) Create a set of path to control density and direction using path interpolation LPEs. This allows a great deal of control, e.g. for hair. I don't think any commercial tool allows this amount of control.
4.) Use the path trim/cut LPE to trim the paths created in 3.) to the areas created in 2.)
5.) Use the embroidery stitch LPE to convert the paths to stitches.
Sometimes I use the cut / trim filter also to create intermediate nodes in paths to create special stitching patterns. These nodes are not visible in normal drawing, but after stitching they are visible.
Of cause for simple cases, it would help to extend it with a more automated approach, which is what you appear to be working at.
I am very interested in the import/export library you mentioned.
It would be great to work together on this.
Best regards,
Michael
--
= Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling away at this problem for over a year now. I'm excited to say that I've solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes quite quickly (sub-second in my tests). It travels around the borders of the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a maximum of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They build a graph of all of the rows and outlines -- that much makes sense. The ridiculously clever part is duplicating some of the edges in order to make a graph that must have an Eulerian Path in it. Then you just find such a path using a well-known algorithm, and you've created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make the stitching come out nicely and the pathfinding complete quickly. Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way down there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to the actual stitching, but at this point the algorithm is sound and the rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread and continue stitching. It's a pretty difficult limitation to work with. I try to avoid jumps whenever possible, and when I have to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3339...> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver makes a jump. My machine can actually do jumps (knot the threads and cut them at both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just works on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote:
Hi! Sorry for going dark there -- everyday life intrudes fairly often.
Neato, and thanks for the explanation! It does indeed look like your stuff follows a similar method to inkscape-embroidery. A few minor differences:
- The extension handles creating a "grating" of lines automatically and
intersects them with the fill region using Shapely (a Python extension).
- The fill pattern is handled automatically through the insertion of
extra nodes as you mentioned. Currently there's only one pattern: a sort of stair-step/staggered pattern that is visually pleasing. I cribbed it off of a pattern I bought online that was made using a commercial embroidery design program. I'd love to understand how to code more complex patterns, but I haven't given much thought to it yet.
- The extension used to have a TSP solver of its own, but it really
didn't do a particularly good job. I started off trying to fix bugs and ultimately just ripped it out. Instead, I carefully order paths in Inkscape. The new Objects panel is key for this, and it's a hugely awesome addition to Inkscape! The only part I struggle with is that Inkscape doesn't want to let you reorder objects relative to each other if they don't intersect (or nearly intersect).
Ultimately, the problem I brought up for discussion boils down to the same problem you're solving with the your TSP algorithm. *Question: *what does your code do if it needs to get from one section to another that is distant? Does it just jump-stitch?
Here's a brief description of how to use EmbroiderModder2's libembroidery to convert between formats: https://github.com/lexelby/inkscape-embroidery#optional-conversion-program
I'd suggest that your code simply output a CSV in the format libembroidery understands, and then you can make use of its knowledge of pretty much every manufacturer format to convert it to a format compatible with your machine.
--Lex
On 7/30/2017 11:47 AM, Michael Soegtrop wrote:
Dear Lex,
I guess we are trying to solve the same problem, but differently. I wanted to have more control than semi automated fillers provide, so I added 3 LPEs, which are in Inkscape 0.92.2:
1.) A bool LPE to do intersections / unions, ... of areas, so that one can construct the areas to stitch from drawing areas.
2.) A path / path group trimmer LPE, which restricts a set of paths to an area (or oustide of an area. There are already two path interpolation LPEs which allow to create sets of paths with fine control over local direction and density.
3.) An LPE to convert a set of paths into stitches. This includes an almost reasonable traveling salesman problem (TSP) variant solver for ordering groups of stitches to minimize the traveling in between. It can still be improved. It is a bit more complicated than standard TSP solvers, because it looks into groups of parallel stitches which have 4 possible ends.
My approach is as follows
1.) Make a drawing
2.) Use the bool op LPE to create (in a new layer) the areas to fill with each color / stitch style.
3.) Create a set of path to control density and direction using path interpolation LPEs. This allows a great deal of control, e.g. for hair. I don't think any commercial tool allows this amount of control.
4.) Use the path trim/cut LPE to trim the paths created in 3.) to the areas created in 2.)
5.) Use the embroidery stitch LPE to convert the paths to stitches.
Sometimes I use the cut / trim filter also to create intermediate nodes in paths to create special stitching patterns. These nodes are not visible in normal drawing, but after stitching they are visible.
Of cause for simple cases, it would help to extend it with a more automated approach, which is what you appear to be working at.
I am very interested in the import/export library you mentioned.
It would be great to work together on this.
Best regards,
Michael
--
= Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Sounds incredible. Well done!
*Ryan Gorley* Managing Partner | Dijt https://dijt.co
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...> wrote:
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling away at this problem for over a year now. I'm excited to say that I've solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes quite quickly (sub-second in my tests). It travels around the borders of the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a maximum of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They build a graph of all of the rows and outlines -- that much makes sense. The ridiculously clever part is duplicating some of the edges in order to make a graph that must have an Eulerian Path in it. Then you just find such a path using a well-known algorithm, and you've created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make the stitching come out nicely and the pathfinding complete quickly. Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way down there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to the actual stitching, but at this point the algorithm is sound and the rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread and continue stitching. It's a pretty difficult limitation to work with. I try to avoid jumps whenever possible, and when I have to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3339...> <MSoegtrop@...3339...> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver makes a jump. My machine can actually do jumps (knot the threads and cut them at both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just works on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote:
Hi! Sorry for going dark there -- everyday life intrudes fairly often.
Neato, and thanks for the explanation! It does indeed look like your stuff follows a similar method to inkscape-embroidery. A few minor differences:
- The extension handles creating a "grating" of lines automatically and
intersects them with the fill region using Shapely (a Python extension).
- The fill pattern is handled automatically through the insertion of
extra nodes as you mentioned. Currently there's only one pattern: a sort of stair-step/staggered pattern that is visually pleasing. I cribbed it off of a pattern I bought online that was made using a commercial embroidery design program. I'd love to understand how to code more complex patterns, but I haven't given much thought to it yet.
- The extension used to have a TSP solver of its own, but it really
didn't do a particularly good job. I started off trying to fix bugs and ultimately just ripped it out. Instead, I carefully order paths in Inkscape. The new Objects panel is key for this, and it's a hugely awesome addition to Inkscape! The only part I struggle with is that Inkscape doesn't want to let you reorder objects relative to each other if they don't intersect (or nearly intersect).
Ultimately, the problem I brought up for discussion boils down to the same problem you're solving with the your TSP algorithm. *Question: *what does your code do if it needs to get from one section to another that is distant? Does it just jump-stitch?
Here's a brief description of how to use EmbroiderModder2's libembroidery to convert between formats: https://github.com/lexelby/inkscape-embroidery#optional-conversion-program
I'd suggest that your code simply output a CSV in the format libembroidery understands, and then you can make use of its knowledge of pretty much every manufacturer format to convert it to a format compatible with your machine.
--Lex
On 7/30/2017 11:47 AM, Michael Soegtrop wrote:
Dear Lex,
I guess we are trying to solve the same problem, but differently. I wanted to have more control than semi automated fillers provide, so I added 3 LPEs, which are in Inkscape 0.92.2:
1.) A bool LPE to do intersections / unions, ... of areas, so that one can construct the areas to stitch from drawing areas.
2.) A path / path group trimmer LPE, which restricts a set of paths to an area (or oustide of an area. There are already two path interpolation LPEs which allow to create sets of paths with fine control over local direction and density.
3.) An LPE to convert a set of paths into stitches. This includes an almost reasonable traveling salesman problem (TSP) variant solver for ordering groups of stitches to minimize the traveling in between. It can still be improved. It is a bit more complicated than standard TSP solvers, because it looks into groups of parallel stitches which have 4 possible ends.
My approach is as follows
1.) Make a drawing
2.) Use the bool op LPE to create (in a new layer) the areas to fill with each color / stitch style.
3.) Create a set of path to control density and direction using path interpolation LPEs. This allows a great deal of control, e.g. for hair. I don't think any commercial tool allows this amount of control.
4.) Use the path trim/cut LPE to trim the paths created in 3.) to the areas created in 2.)
5.) Use the embroidery stitch LPE to convert the paths to stitches.
Sometimes I use the cut / trim filter also to create intermediate nodes in paths to create special stitching patterns. These nodes are not visible in normal drawing, but after stitching they are visible.
Of cause for simple cases, it would help to extend it with a more automated approach, which is what you appear to be working at.
I am very interested in the import/export library you mentioned.
It would be great to work together on this.
Best regards,
Michael
--
= Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
I'm excited to see this breakthrough hit the website extensions library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
Sounds incredible. Well done!
Ryan Gorley Managing Partner | Dijt
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...> wrote:
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling away at this problem for over a year now. I'm excited to say that I've solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes quite quickly (sub-second in my tests). It travels around the borders of the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a maximum of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They build a graph of all of the rows and outlines -- that much makes sense. The ridiculously clever part is duplicating some of the edges in order to make a graph that must have an Eulerian Path in it. Then you just find such a path using a well-known algorithm, and you've created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make the stitching come out nicely and the pathfinding complete quickly. Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way down there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to the actual stitching, but at this point the algorithm is sound and the rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread and continue stitching. It's a pretty difficult limitation to work with. I try to avoid jumps whenever possible, and when I have to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3616... -Soegtrop.de> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver makes a jump. My machine can actually do jumps (knot the threads and cut them at both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just works on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote:
Hi! Sorry for going dark there -- everyday life intrudes fairly often.
Neato, and thanks for the explanation! It does indeed look like your stuff follows a similar method to inkscape-embroidery. A few minor differences:
- The extension handles creating a "grating" of lines
automatically and intersects them with the fill region using Shapely (a Python extension).
- The fill pattern is handled automatically through the
insertion of extra nodes as you mentioned. Currently there's only one pattern: a sort of stair-step/staggered pattern that is visually pleasing. I cribbed it off of a pattern I bought online that was made using a commercial embroidery design program. I'd love to understand how to code more complex patterns, but I haven't given much thought to it yet.
- The extension used to have a TSP solver of its own, but it
really didn't do a particularly good job. I started off trying to fix bugs and ultimately just ripped it out. Instead, I carefully order paths in Inkscape. The new Objects panel is key for this, and it's a hugely awesome addition to Inkscape! The only part I struggle with is that Inkscape doesn't want to let you reorder objects relative to each other if they don't intersect (or nearly intersect).
Ultimately, the problem I brought up for discussion boils down to the same problem you're solving with the your TSP algorithm. *Question: *what does your code do if it needs to get from one section to another that is distant? Does it just jump-stitch?
Here's a brief description of how to use EmbroiderModder2's libembroidery to convert between formats: https://github.com/lexelby/inkscape-embroidery#optional-conve rsion-program
I'd suggest that your code simply output a CSV in the format libembroidery understands, and then you can make use of its knowledge of pretty much every manufacturer format to convert it to a format compatible with your machine.
--Lex
On 7/30/2017 11:47 AM, Michael Soegtrop wrote:
Dear Lex,
I guess we are trying to solve the same problem, but differently. I wanted to have more control than semi automated fillers provide, so I added 3 LPEs, which are in Inkscape 0.92.2:
1.) A bool LPE to do intersections / unions, ... of areas, so that one can construct the areas to stitch from drawing areas.
2.) A path / path group trimmer LPE, which restricts a set of paths to an area (or oustide of an area. There are already two path interpolation LPEs which allow to create sets of paths with fine control over local direction and density.
3.) An LPE to convert a set of paths into stitches. This includes an almost reasonable traveling salesman problem (TSP) variant solver for ordering groups of stitches to minimize the traveling in between. It can still be improved. It is a bit more complicated than standard TSP solvers, because it looks into groups of parallel stitches which have 4 possible ends.
My approach is as follows
1.) Make a drawing
2.) Use the bool op LPE to create (in a new layer) the areas to fill with each color / stitch style.
3.) Create a set of path to control density and direction using path interpolation LPEs. This allows a great deal of control, e.g. for hair. I don't think any commercial tool allows this amount of control.
4.) Use the path trim/cut LPE to trim the paths created in 3.) to the areas created in 2.)
5.) Use the embroidery stitch LPE to convert the paths to stitches.
Sometimes I use the cut / trim filter also to create intermediate nodes in paths to create special stitching patterns. These nodes are not visible in normal drawing, but after stitching they are visible.
Of cause for simple cases, it would help to extend it with a more automated approach, which is what you appear to be working at.
I am very interested in the import/export library you mentioned.
It would be great to work together on this.
Best regards,
Michael
-- =========================================== = Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
--------------- Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot%C2%A0 _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
+1 Thanks for helping make Inkscape more useful to a broader audience! If you'd favour us with some photos of the extension working, the Vectors team can prepare a press release to celebrate the new extension on our social networks.
I think it's a cool enough feature to make some noise about. :)
On 25 Sep 2017 4:17 p.m., "Martin Owens" <doctormo@...400...> wrote:
I'm excited to see this breakthrough hit the website extensions library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
Sounds incredible. Well done!
Ryan Gorley Managing Partner | Dijt
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...> wrote:
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling away at this problem for over a year now. I'm excited to say that I've solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes quite quickly (sub-second in my tests). It travels around the borders of the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a maximum of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They build a graph of all of the rows and outlines -- that much makes sense. The ridiculously clever part is duplicating some of the edges in order to make a graph that must have an Eulerian Path in it. Then you just find such a path using a well-known algorithm, and you've created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make the stitching come out nicely and the pathfinding complete quickly. Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way down there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to the actual stitching, but at this point the algorithm is sound and the rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread and continue stitching. It's a pretty difficult limitation to work with. I try to avoid jumps whenever possible, and when I have to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3616... -Soegtrop.de> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver makes a jump. My machine can actually do jumps (knot the threads and cut them at both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just works on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote:
Hi! Sorry for going dark there -- everyday life intrudes fairly often.
Neato, and thanks for the explanation! It does indeed look like your stuff follows a similar method to inkscape-embroidery. A few minor differences:
- The extension handles creating a "grating" of lines
automatically and intersects them with the fill region using Shapely (a Python extension).
- The fill pattern is handled automatically through the
insertion of extra nodes as you mentioned. Currently there's only one pattern: a sort of stair-step/staggered pattern that is visually pleasing. I cribbed it off of a pattern I bought online that was made using a commercial embroidery design program. I'd love to understand how to code more complex patterns, but I haven't given much thought to it yet.
- The extension used to have a TSP solver of its own, but it
really didn't do a particularly good job. I started off trying to fix bugs and ultimately just ripped it out. Instead, I carefully order paths in Inkscape. The new Objects panel is key for this, and it's a hugely awesome addition to Inkscape! The only part I struggle with is that Inkscape doesn't want to let you reorder objects relative to each other if they don't intersect (or nearly intersect).
Ultimately, the problem I brought up for discussion boils down to the same problem you're solving with the your TSP algorithm. *Question: *what does your code do if it needs to get from one section to another that is distant? Does it just jump-stitch?
Here's a brief description of how to use EmbroiderModder2's libembroidery to convert between formats: https://github.com/lexelby/inkscape-embroidery#optional-conve rsion-program
I'd suggest that your code simply output a CSV in the format libembroidery understands, and then you can make use of its knowledge of pretty much every manufacturer format to convert it to a format compatible with your machine.
--Lex
On 7/30/2017 11:47 AM, Michael Soegtrop wrote: > Dear Lex, > > I guess we are trying to solve the same problem, but > differently. I > wanted to have more control than semi automated fillers > provide, so I > added 3 LPEs, which are in Inkscape 0.92.2: > > 1.) A bool LPE to do intersections / unions, ... of areas, > so that one > can construct the areas to stitch from drawing areas. > > 2.) A path / path group trimmer LPE, which restricts a set > of paths to > an area (or oustide of an area. There are already two path > interpolation > LPEs which allow to create sets of paths with fine control > over local > direction and density. > > 3.) An LPE to convert a set of paths into stitches. This > includes an > almost reasonable traveling salesman problem (TSP) variant > solver for > ordering groups of stitches to minimize the traveling in > between. It can > still be improved. It is a bit more complicated than > standard TSP > solvers, because it looks into groups of parallel stitches > which have 4 > possible ends. > > > My approach is as follows > > 1.) Make a drawing > > 2.) Use the bool op LPE to create (in a new layer) the > areas to fill > with each color / stitch style. > > 3.) Create a set of path to control density and direction > using path > interpolation LPEs. This allows a great deal of control, > e.g. for hair. > I don't think any commercial tool allows this amount of > control. > > 4.) Use the path trim/cut LPE to trim the paths created in > 3.) to the > areas created in 2.) > > 5.) Use the embroidery stitch LPE to convert the paths to > stitches. > > Sometimes I use the cut / trim filter also to create > intermediate nodes > in paths to create special stitching patterns. These nodes > are not > visible in normal drawing, but after stitching they are > visible. > > Of cause for simple cases, it would help to extend it with > a more > automated approach, which is what you appear to be working > at. > > I am very interested in the import/export library you > mentioned. > > It would be great to work together on this. > > Best regards, > > Michael >
--
= Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
It took me awhile, but here's something better than photos, a screencast showing how to use it:
https://www.youtube.com/watch?v=qXntE1X1RIw
On Tue, 2017-09-26 at 08:19 +0100, C R wrote:
+1 Thanks for helping make Inkscape more useful to a broader audience! If you'd favour us with some photos of the extension working, the Vectors team can prepare a press release to celebrate the new extension on our social networks.
I think it's a cool enough feature to make some noise about. :)
On 25 Sep 2017 4:17 p.m., "Martin Owens" <doctormo@...400...> wrote:
I'm excited to see this breakthrough hit the website extensions library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
Sounds incredible. Well done!
Ryan Gorley Managing Partner | Dijt
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...>
wrote:
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling
away
at this problem for over a year now. I'm excited to say that
I've
solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes
quite
quickly (sub-second in my tests). It travels around the
borders of
the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a
maximum
of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000
158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They
build
a graph of all of the rows and outlines -- that much makes
sense.
The ridiculously clever part is duplicating some of the edges
in
order to make a graph that must have an Eulerian Path in it.
Then
you just find such a path using a well-known algorithm, and
you've
created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make
the
stitching come out nicely and the pathfinding complete
quickly.
Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way
down
there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to
the
actual stitching, but at this point the algorithm is sound and
the
rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread
and
continue stitching. It's a pretty difficult limitation to
work
with. I try to avoid jumps whenever possible, and when I
have
to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3632......
hael
-Soegtrop.de> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver
makes a
jump. My machine can actually do jumps (knot the threads and cut
them at
both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just
works
on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote: > Hi! Sorry for going dark there -- everyday life intrudes > fairly often. > > Neato, and thanks for the explanation! It does indeed
look
> like your > stuff follows a similar method to inkscape-embroidery. A
few
> minor > differences: > > * The extension handles creating a "grating" of lines > automatically and > intersects them with the fill region using Shapely (a
Python
> extension). > > * The fill pattern is handled automatically through the > insertion of > extra nodes as you mentioned. Currently there's only one > pattern: a > sort of stair-step/staggered pattern that is visually > pleasing. I > cribbed it off of a pattern I bought online that was made > using a > commercial embroidery design program. I'd love to
understand
> how to > code more complex patterns, but I haven't given much
thought
> to it yet. > > * The extension used to have a TSP solver of its own, but
it
> really > didn't do a particularly good job. I started off trying
to
> fix bugs and > ultimately just ripped it out. Instead, I carefully
order
> paths in > Inkscape. The new Objects panel is key for this, and
it's a
> hugely > awesome addition to Inkscape! The only part I struggle
with
> is that > Inkscape doesn't want to let you reorder objects relative
to
> each other > if they don't intersect (or nearly intersect). > > Ultimately, the problem I brought up for discussion boils > down to the > same problem you're solving with the your TSP algorithm. > *Question: > *what does your code do if it needs to get from one
section
> to another > that is distant? Does it just jump-stitch? > > Here's a brief description of how to use
EmbroiderModder2's
> libembroidery to convert between formats: > https://github.com/lexelby/inkscape-embroidery#optional-c
onve
> rsion-program > > I'd suggest that your code simply output a CSV in the
format
> libembroidery understands, and then you can make use of
its
> knowledge of > pretty much every manufacturer format to convert it to a > format > compatible with your machine. > > --Lex > > On 7/30/2017 11:47 AM, Michael Soegtrop wrote: > > Dear Lex, > > > > I guess we are trying to solve the same problem, but > > differently. I > > wanted to have more control than semi automated fillers > > provide, so I > > added 3 LPEs, which are in Inkscape 0.92.2: > > > > 1.) A bool LPE to do intersections / unions, ... of
areas,
> > so that one > > can construct the areas to stitch from drawing areas. > > > > 2.) A path / path group trimmer LPE, which restricts a
set
> > of paths to > > an area (or oustide of an area. There are already two
path
> > interpolation > > LPEs which allow to create sets of paths with fine
control
> > over local > > direction and density. > > > > 3.) An LPE to convert a set of paths into stitches.
This
> > includes an > > almost reasonable traveling salesman problem (TSP)
variant
> > solver for > > ordering groups of stitches to minimize the traveling
in
> > between. It can > > still be improved. It is a bit more complicated than > > standard TSP > > solvers, because it looks into groups of parallel
stitches
> > which have 4 > > possible ends. > > > > > > My approach is as follows > > > > 1.) Make a drawing > > > > 2.) Use the bool op LPE to create (in a new layer) the > > areas to fill > > with each color / stitch style. > > > > 3.) Create a set of path to control density and
direction
> > using path > > interpolation LPEs. This allows a great deal of
control,
> > e.g. for hair. > > I don't think any commercial tool allows this amount of > > control. > > > > 4.) Use the path trim/cut LPE to trim the paths created
in
> > 3.) to the > > areas created in 2.) > > > > 5.) Use the embroidery stitch LPE to convert the paths
to
> > stitches. > > > > Sometimes I use the cut / trim filter also to create > > intermediate nodes > > in paths to create special stitching patterns. These
nodes
> > are not > > visible in normal drawing, but after stitching they are > > visible. > > > > Of cause for simple cases, it would help to extend it
with
> > a more > > automated approach, which is what you appear to be
working
> > at. > > > > I am very interested in the import/export library you > > mentioned. > > > > It would be great to work together on this. > > > > Best regards, > > > > Michael > > >
--
= Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
Check out the vibrant tech community on one of the world's
most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
That's really impressive. I wonder if an extension is capable of setting the keyboard shortcuts ? If it was then you could add an embroidery extension to set and unset the shortcuts you use. That would help to enable the workflows simple for complex domain specific extensions like this.
Question: - if the ice is white - how do you specify a thread change ?
On 12/18/2017 9:24 AM, Lex Neva wrote:
It took me awhile, but here's something better than photos, a screencast showing how to use it:
https://www.youtube.com/watch?v=qXntE1X1RIw
On Tue, 2017-09-26 at 08:19 +0100, C R wrote:
+1 Thanks for helping make Inkscape more useful to a broader audience! If you'd favour us with some photos of the extension working, the Vectors team can prepare a press release to celebrate the new extension on our social networks.
I think it's a cool enough feature to make some noise about. :)
On 25 Sep 2017 4:17 p.m., "Martin Owens" <doctormo@...400...> wrote:
I'm excited to see this breakthrough hit the website extensions library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
Sounds incredible. Well done!
Ryan Gorley Managing Partner | Dijt
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...>
wrote:
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling
away
at this problem for over a year now. I'm excited to say that
I've
solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes
quite
quickly (sub-second in my tests). It travels around the
borders of
the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a
maximum
of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000
158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They
build
a graph of all of the rows and outlines -- that much makes
sense.
The ridiculously clever part is duplicating some of the edges
in
order to make a graph that must have an Eulerian Path in it.
Then
you just find such a path using a well-known algorithm, and
you've
created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make
the
stitching come out nicely and the pathfinding complete
quickly.
Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way
down
there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to
the
actual stitching, but at this point the algorithm is sound and
the
rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread
and
continue stitching. It's a pretty difficult limitation to
work
with. I try to avoid jumps whenever possible, and when I
have
to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3631...
hael
-Soegtrop.de> wrote:
> Dear Lex, > > yes, in case there is a large distance, the TSP solver
makes a
> jump. My > machine can actually do jumps (knot the threads and cut
them at
> both > ends), so my main goal is to optimize the number of jumps. > > What one should do is try to order the groups such that > connections can > be hidden below other stitching, but this is complicated, > especially > when you don't have the concept of an area (my stuff just
works
> on open > paths). > > Best regards, > > Michael > > On 25.08.2017 21:05, Lex Neva wrote: >> Hi! Sorry for going dark there -- everyday life intrudes >> fairly often. >> >> Neato, and thanks for the explanation! It does indeed
look
>> like your >> stuff follows a similar method to inkscape-embroidery. A
few
>> minor >> differences: >> >> * The extension handles creating a "grating" of lines >> automatically and >> intersects them with the fill region using Shapely (a
Python
>> extension). >> >> * The fill pattern is handled automatically through the >> insertion of >> extra nodes as you mentioned. Currently there's only one >> pattern: a >> sort of stair-step/staggered pattern that is visually >> pleasing. I >> cribbed it off of a pattern I bought online that was made >> using a >> commercial embroidery design program. I'd love to
understand
>> how to >> code more complex patterns, but I haven't given much
thought
>> to it yet. >> >> * The extension used to have a TSP solver of its own, but
it
>> really >> didn't do a particularly good job. I started off trying
to
>> fix bugs and >> ultimately just ripped it out. Instead, I carefully
order
>> paths in >> Inkscape. The new Objects panel is key for this, and
it's a
>> hugely >> awesome addition to Inkscape! The only part I struggle
with
>> is that >> Inkscape doesn't want to let you reorder objects relative
to
>> each other >> if they don't intersect (or nearly intersect). >> >> Ultimately, the problem I brought up for discussion boils >> down to the >> same problem you're solving with the your TSP algorithm. >> *Question: >> *what does your code do if it needs to get from one
section
>> to another >> that is distant? Does it just jump-stitch? >> >> Here's a brief description of how to use
EmbroiderModder2's
>> libembroidery to convert between formats: >> https://github.com/lexelby/inkscape-embroidery#optional-c
onve
>> rsion-program >> >> I'd suggest that your code simply output a CSV in the
format
>> libembroidery understands, and then you can make use of
its
>> knowledge of >> pretty much every manufacturer format to convert it to a >> format >> compatible with your machine. >> >> --Lex >> >> On 7/30/2017 11:47 AM, Michael Soegtrop wrote: >>> Dear Lex, >>> >>> I guess we are trying to solve the same problem, but >>> differently. I >>> wanted to have more control than semi automated fillers >>> provide, so I >>> added 3 LPEs, which are in Inkscape 0.92.2: >>> >>> 1.) A bool LPE to do intersections / unions, ... of
areas,
>>> so that one >>> can construct the areas to stitch from drawing areas. >>> >>> 2.) A path / path group trimmer LPE, which restricts a
set
>>> of paths to >>> an area (or oustide of an area. There are already two
path
>>> interpolation >>> LPEs which allow to create sets of paths with fine
control
>>> over local >>> direction and density. >>> >>> 3.) An LPE to convert a set of paths into stitches.
This
>>> includes an >>> almost reasonable traveling salesman problem (TSP)
variant
>>> solver for >>> ordering groups of stitches to minimize the traveling
in
>>> between. It can >>> still be improved. It is a bit more complicated than >>> standard TSP >>> solvers, because it looks into groups of parallel
stitches
>>> which have 4 >>> possible ends. >>> >>> >>> My approach is as follows >>> >>> 1.) Make a drawing >>> >>> 2.) Use the bool op LPE to create (in a new layer) the >>> areas to fill >>> with each color / stitch style. >>> >>> 3.) Create a set of path to control density and
direction
>>> using path >>> interpolation LPEs. This allows a great deal of
control,
>>> e.g. for hair. >>> I don't think any commercial tool allows this amount of >>> control. >>> >>> 4.) Use the path trim/cut LPE to trim the paths created
in
>>> 3.) to the >>> areas created in 2.) >>> >>> 5.) Use the embroidery stitch LPE to convert the paths
to
>>> stitches. >>> >>> Sometimes I use the cut / trim filter also to create >>> intermediate nodes >>> in paths to create special stitching patterns. These
nodes
>>> are not >>> visible in normal drawing, but after stitching they are >>> visible. >>> >>> Of cause for simple cases, it would help to extend it
with
>>> a more >>> automated approach, which is what you appear to be
working
>>> at. >>> >>> I am very interested in the import/export library you >>> mentioned. >>> >>> It would be great to work together on this. >>> >>> Best regards, >>> >>> Michael >>> >> > > -- > =========================================== > = Dipl. Phys. Michael Sögtrop > = Datenerfassungs- und Informationssysteme > = Steuerungs- und Automatisierungstechnik > = > = Anzinger Str. 10c > = 85586 Poing > = > = Tel.: (08121) 972433 > = Fax.: (08121) 972434 > =========================================== >
Check out the vibrant tech community on one of the world's
most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
This email has been checked for viruses by AVG. http://www.avg.com
Fantastic! Love to see the results on a black baseball cap to make it an embroidered Inkscape hat or something. :D -C
On Sun, Dec 17, 2017 at 9:57 PM, Mark Schafer <mschafer@...2596...> wrote:
That's really impressive. I wonder if an extension is capable of setting the keyboard shortcuts ? If it was then you could add an embroidery extension to set and unset the shortcuts you use. That would help to enable the workflows simple for complex domain specific extensions like this.
Question: - if the ice is white - how do you specify a thread change ?
On 12/18/2017 9:24 AM, Lex Neva wrote:
It took me awhile, but here's something better than photos, a screencast showing how to use it:
https://www.youtube.com/watch?v=qXntE1X1RIw
On Tue, 2017-09-26 at 08:19 +0100, C R wrote:
+1 Thanks for helping make Inkscape more useful to a broader audience! If you'd favour us with some photos of the extension working, the Vectors team can prepare a press release to celebrate the new extension on our social networks.
I think it's a cool enough feature to make some noise about. :)
On 25 Sep 2017 4:17 p.m., "Martin Owens" <doctormo@...400...> wrote:
I'm excited to see this breakthrough hit the website extensions library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
Sounds incredible. Well done!
Ryan Gorley Managing Partner | Dijt
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...>
wrote:
SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling
away
at this problem for over a year now. I'm excited to say that
I've
solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes
quite
quickly (sub-second in my tests). It travels around the
borders of
the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a
maximum
of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000
158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They
build
a graph of all of the rows and outlines -- that much makes
sense.
The ridiculously clever part is duplicating some of the edges
in
order to make a graph that must have an Eulerian Path in it.
Then
you just find such a path using a well-known algorithm, and
you've
created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make
the
stitching come out nicely and the pathfinding complete
quickly.
Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way
down
there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to
the
actual stitching, but at this point the algorithm is sound and
the
rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote: > > Ah, I see. My machine (a Brother SE400) can't cut the thread
and
> > continue stitching. It's a pretty difficult limitation to
work
> > with. I try to avoid jumps whenever possible, and when I
have
> > to, I place jumps such that they're easy to trim by hand. > > > On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3631...
hael
> > -Soegtrop.de> wrote: > >> Dear Lex, >> >> yes, in case there is a large distance, the TSP solver
makes a
>> >> jump. My >> machine can actually do jumps (knot the threads and cut
them at
>> >> both >> ends), so my main goal is to optimize the number of jumps. >> >> What one should do is try to order the groups such that >> connections can >> be hidden below other stitching, but this is complicated, >> especially >> when you don't have the concept of an area (my stuff just
works
>> >> on open >> paths). >> >> Best regards, >> >> Michael >> >> On 25.08.2017 21:05, Lex Neva wrote: >>> >>> Hi! Sorry for going dark there -- everyday life intrudes >>> fairly often. >>> >>> Neato, and thanks for the explanation! It does indeed
look
>>> >>> like your >>> stuff follows a similar method to inkscape-embroidery. A
few
>>> >>> minor >>> differences: >>> >>> * The extension handles creating a "grating" of lines >>> automatically and >>> intersects them with the fill region using Shapely (a
Python
>>> >>> extension). >>> >>> * The fill pattern is handled automatically through the >>> insertion of >>> extra nodes as you mentioned. Currently there's only one >>> pattern: a >>> sort of stair-step/staggered pattern that is visually >>> pleasing. I >>> cribbed it off of a pattern I bought online that was made >>> using a >>> commercial embroidery design program. I'd love to
understand
>>> >>> how to >>> code more complex patterns, but I haven't given much
thought
>>> >>> to it yet. >>> >>> * The extension used to have a TSP solver of its own, but
it
>>> >>> really >>> didn't do a particularly good job. I started off trying
to
>>> >>> fix bugs and >>> ultimately just ripped it out. Instead, I carefully
order
>>> >>> paths in >>> Inkscape. The new Objects panel is key for this, and
it's a
>>> >>> hugely >>> awesome addition to Inkscape! The only part I struggle
with
>>> >>> is that >>> Inkscape doesn't want to let you reorder objects relative
to
>>> >>> each other >>> if they don't intersect (or nearly intersect). >>> >>> Ultimately, the problem I brought up for discussion boils >>> down to the >>> same problem you're solving with the your TSP algorithm. >>> *Question: >>> *what does your code do if it needs to get from one
section
>>> >>> to another >>> that is distant? Does it just jump-stitch? >>> >>> Here's a brief description of how to use
EmbroiderModder2's
>>> >>> libembroidery to convert between formats: >>> https://github.com/lexelby/inkscape-embroidery#optional-c
onve
>>> >>> rsion-program >>> >>> I'd suggest that your code simply output a CSV in the
format
>>> >>> libembroidery understands, and then you can make use of
its
>>> >>> knowledge of >>> pretty much every manufacturer format to convert it to a >>> format >>> compatible with your machine. >>> >>> --Lex >>> >>> On 7/30/2017 11:47 AM, Michael Soegtrop wrote: >>>> >>>> Dear Lex, >>>> >>>> I guess we are trying to solve the same problem, but >>>> differently. I >>>> wanted to have more control than semi automated fillers >>>> provide, so I >>>> added 3 LPEs, which are in Inkscape 0.92.2: >>>> >>>> 1.) A bool LPE to do intersections / unions, ... of
areas,
>>>> >>>> so that one >>>> can construct the areas to stitch from drawing areas. >>>> >>>> 2.) A path / path group trimmer LPE, which restricts a
set
>>>> >>>> of paths to >>>> an area (or oustide of an area. There are already two
path
>>>> >>>> interpolation >>>> LPEs which allow to create sets of paths with fine
control
>>>> >>>> over local >>>> direction and density. >>>> >>>> 3.) An LPE to convert a set of paths into stitches.
This
>>>> >>>> includes an >>>> almost reasonable traveling salesman problem (TSP)
variant
>>>> >>>> solver for >>>> ordering groups of stitches to minimize the traveling
in
>>>> >>>> between. It can >>>> still be improved. It is a bit more complicated than >>>> standard TSP >>>> solvers, because it looks into groups of parallel
stitches
>>>> >>>> which have 4 >>>> possible ends. >>>> >>>> >>>> My approach is as follows >>>> >>>> 1.) Make a drawing >>>> >>>> 2.) Use the bool op LPE to create (in a new layer) the >>>> areas to fill >>>> with each color / stitch style. >>>> >>>> 3.) Create a set of path to control density and
direction
>>>> >>>> using path >>>> interpolation LPEs. This allows a great deal of
control,
>>>> >>>> e.g. for hair. >>>> I don't think any commercial tool allows this amount of >>>> control. >>>> >>>> 4.) Use the path trim/cut LPE to trim the paths created
in
>>>> >>>> 3.) to the >>>> areas created in 2.) >>>> >>>> 5.) Use the embroidery stitch LPE to convert the paths
to
>>>> >>>> stitches. >>>> >>>> Sometimes I use the cut / trim filter also to create >>>> intermediate nodes >>>> in paths to create special stitching patterns. These
nodes
>>>> >>>> are not >>>> visible in normal drawing, but after stitching they are >>>> visible. >>>> >>>> Of cause for simple cases, it would help to extend it
with
>>>> >>>> a more >>>> automated approach, which is what you appear to be
working
>>>> >>>> at. >>>> >>>> I am very interested in the import/export library you >>>> mentioned. >>>> >>>> It would be great to work together on this. >>>> >>>> Best regards, >>>> >>>> Michael >>>> >>> >> >> >> -- >> =========================================== >> = Dipl. Phys. Michael Sögtrop >> = Datenerfassungs- und Informationssysteme >> = Steuerungs- und Automatisierungstechnik >> = >> = Anzinger Str. 10c >> = 85586 Poing >> = >> = Tel.: (08121) 972433 >> = Fax.: (08121) 972434 >> =========================================== >> > > -----------------------------------------------------------
> > --------------- > Check out the vibrant tech community on one of the world's
most
> > engaging tech sites, Slashdot.org! http://sdm.link/slashdot > _______________________________________________ > Inkscape-devel mailing list > Inkscape-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
This email has been checked for viruses by AVG. http://www.avg.com
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
On Mon, 2017-12-18 at 10:34 +0000, C R wrote:
Fantastic! Love to see the results on a black baseball cap to make it an embroidered Inkscape hat or something. :D -C
That'd be cool! Alas, my entry-level hobbyist embroidery machine can't do hats :(
On Sun, Dec 17, 2017 at 9:57 PM, Mark Schafer <mschafer@...2596...
wrote: That's really impressive. I wonder if an extension is capable of setting the keyboard shortcuts ? If it was then you could add an embroidery extension to set and unset the shortcuts you use. That would help to enable the workflows simple for complex domain specific extensions like this.
Question: - if the ice is white - how do you specify a thread change ?
On 12/18/2017 9:24 AM, Lex Neva wrote:
It took me awhile, but here's something better than photos, a screencast showing how to use it:
https://www.youtube.com/watch?v=qXntE1X1RIw
On Tue, 2017-09-26 at 08:19 +0100, C R wrote:
+1 Thanks for helping make Inkscape more useful to a broader audience! If you'd favour us with some photos of the extension working, the Vectors team can prepare a press release to celebrate the new extension on our social networks.
I think it's a cool enough feature to make some noise about. :)
On 25 Sep 2017 4:17 p.m., "Martin Owens" <doctormo@...400...> wrote:
I'm excited to see this breakthrough hit the website extensions library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
Sounds incredible. Well done!
Ryan Gorley Managing Partner | Dijt
On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...>
wrote:
> > SOLVED! > > This is a pretty huge breakthrough for me. I've been > puzzling
away
> > at this problem for over a year now. I'm excited to say > that
I've
> > solved it. More details below for those curious. > > My solution can fill a complex region with arbitrary > holes
quite
> > quickly (sub-second in my tests). It travels around the
borders of
> > the fill region (either the outer border or the borders > of the > holes). Any given section of the border is stitched over > a
maximum
> > of twice. No jump stitches are required. > > I owe it all to this paper, "Approximation algorithms for > lawn > mowing and milling": > > http://www.sciencedirect.com/science/article/pii/S0925772 > 100000
158
> > I'd previously reviewed the paper for ideas but I hadn't > fully > grasped the one key aspect to their milling > algorithm. They
build
> > a graph of all of the rows and outlines -- that much > makes
sense.
> > The ridiculously clever part is duplicating some of the > edges
in
> > order to make a graph that must have an Eulerian Path in > it.
Then
> > you just find such a path using a well-known algorithm, > and
you've
> > created your milling path (or stitching, in my case). > > It still required the addition of several heuristics to > make
the
> > stitching come out nicely and the pathfinding complete
quickly.
> > Any old eulerian path solution would technically work, > but it's > going to be weird if you stitch a row here, another one > way
down
> > there, etc. > > Anyway, bottom line is, "a solution exists". I'm still > in the > process of converting from the graph-theoretical solution > to
the
> > actual stitching, but at this point the algorithm is > sound and
the
> > rest is busywork. > > Thanks everyone for the tips and for being a sounding > board! > --Lex > > > On 8/28/2017 3:01 PM, Lex wrote: > > > > Ah, I see. My machine (a Brother SE400) can't cut the > > thread
and
> > > > continue stitching. It's a pretty difficult limitation > > to
work
> > > > with. I try to avoid jumps whenever possible, and when > > I
have
> > > > to, I place jumps such that they're easy to trim by > > hand. > > > > > > On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtr > > op@...3631...
hael
> > > > -Soegtrop.de> wrote: > > > > > Dear Lex, > > > > > > yes, in case there is a large distance, the TSP > > > solver
makes a
> > > > > > jump. My > > > machine can actually do jumps (knot the threads and > > > cut
them at
> > > > > > both > > > ends), so my main goal is to optimize the number of > > > jumps. > > > > > > What one should do is try to order the groups such > > > that > > > connections can > > > be hidden below other stitching, but this is > > > complicated, > > > especially > > > when you don't have the concept of an area (my stuff > > > just
works
> > > > > > on open > > > paths). > > > > > > Best regards, > > > > > > Michael > > > > > > On 25.08.2017 21:05, Lex Neva wrote: > > > > > > > > Hi! Sorry for going dark there -- everyday life > > > > intrudes > > > > fairly often. > > > > > > > > Neato, and thanks for the explanation! It does > > > > indeed
look
> > > > > > > > like your > > > > stuff follows a similar method to inkscape- > > > > embroidery. A
few
> > > > > > > > minor > > > > differences: > > > > > > > > * The extension handles creating a "grating" of > > > > lines > > > > automatically and > > > > intersects them with the fill region using Shapely > > > > (a
Python
> > > > > > > > extension). > > > > > > > > * The fill pattern is handled automatically through > > > > the > > > > insertion of > > > > extra nodes as you mentioned. Currently there's > > > > only one > > > > pattern: a > > > > sort of stair-step/staggered pattern that is > > > > visually > > > > pleasing. I > > > > cribbed it off of a pattern I bought online that > > > > was made > > > > using a > > > > commercial embroidery design program. I'd love to
understand
> > > > > > > > how to > > > > code more complex patterns, but I haven't given > > > > much
thought
> > > > > > > > to it yet. > > > > > > > > * The extension used to have a TSP solver of its > > > > own, but
it
> > > > > > > > really > > > > didn't do a particularly good job. I started off > > > > trying
to
> > > > > > > > fix bugs and > > > > ultimately just ripped it out. Instead, I > > > > carefully
order
> > > > > > > > paths in > > > > Inkscape. The new Objects panel is key for this, > > > > and
it's a
> > > > > > > > hugely > > > > awesome addition to Inkscape! The only part I > > > > struggle
with
> > > > > > > > is that > > > > Inkscape doesn't want to let you reorder objects > > > > relative
to
> > > > > > > > each other > > > > if they don't intersect (or nearly intersect). > > > > > > > > Ultimately, the problem I brought up for discussion > > > > boils > > > > down to the > > > > same problem you're solving with the your TSP > > > > algorithm. > > > > *Question: > > > > *what does your code do if it needs to get from one
section
> > > > > > > > to another > > > > that is distant? Does it just jump-stitch? > > > > > > > > Here's a brief description of how to use
EmbroiderModder2's
> > > > > > > > libembroidery to convert between formats: > > > > https://github.com/lexelby/inkscape-embroidery#opti > > > > onal-c
onve
> > > > > > > > rsion-program > > > > > > > > I'd suggest that your code simply output a CSV in > > > > the
format
> > > > > > > > libembroidery understands, and then you can make > > > > use of
its
> > > > > > > > knowledge of > > > > pretty much every manufacturer format to convert it > > > > to a > > > > format > > > > compatible with your machine. > > > > > > > > --Lex > > > > > > > > On 7/30/2017 11:47 AM, Michael Soegtrop wrote: > > > > > > > > > > Dear Lex, > > > > > > > > > > I guess we are trying to solve the same problem, > > > > > but > > > > > differently. I > > > > > wanted to have more control than semi automated > > > > > fillers > > > > > provide, so I > > > > > added 3 LPEs, which are in Inkscape 0.92.2: > > > > > > > > > > 1.) A bool LPE to do intersections / unions, ... > > > > > of
areas,
> > > > > > > > > > so that one > > > > > can construct the areas to stitch from drawing > > > > > areas. > > > > > > > > > > 2.) A path / path group trimmer LPE, which > > > > > restricts a
set
> > > > > > > > > > of paths to > > > > > an area (or oustide of an area. There are already > > > > > two
path
> > > > > > > > > > interpolation > > > > > LPEs which allow to create sets of paths with > > > > > fine
control
> > > > > > > > > > over local > > > > > direction and density. > > > > > > > > > > 3.) An LPE to convert a set of paths into > > > > > stitches.
This
> > > > > > > > > > includes an > > > > > almost reasonable traveling salesman problem > > > > > (TSP)
variant
> > > > > > > > > > solver for > > > > > ordering groups of stitches to minimize the > > > > > traveling
in
> > > > > > > > > > between. It can > > > > > still be improved. It is a bit more complicated > > > > > than > > > > > standard TSP > > > > > solvers, because it looks into groups of parallel
stitches
> > > > > > > > > > which have 4 > > > > > possible ends. > > > > > > > > > > > > > > > My approach is as follows > > > > > > > > > > 1.) Make a drawing > > > > > > > > > > 2.) Use the bool op LPE to create (in a new > > > > > layer) the > > > > > areas to fill > > > > > with each color / stitch style. > > > > > > > > > > 3.) Create a set of path to control density and
direction
> > > > > > > > > > using path > > > > > interpolation LPEs. This allows a great deal of
control,
> > > > > > > > > > e.g. for hair. > > > > > I don't think any commercial tool allows this > > > > > amount of > > > > > control. > > > > > > > > > > 4.) Use the path trim/cut LPE to trim the paths > > > > > created
in
> > > > > > > > > > 3.) to the > > > > > areas created in 2.) > > > > > > > > > > 5.) Use the embroidery stitch LPE to convert the > > > > > paths
to
> > > > > > > > > > stitches. > > > > > > > > > > Sometimes I use the cut / trim filter also to > > > > > create > > > > > intermediate nodes > > > > > in paths to create special stitching patterns. > > > > > These
nodes
> > > > > > > > > > are not > > > > > visible in normal drawing, but after stitching > > > > > they are > > > > > visible. > > > > > > > > > > Of cause for simple cases, it would help to > > > > > extend it
with
> > > > > > > > > > a more > > > > > automated approach, which is what you appear to > > > > > be
working
> > > > > > > > > > at. > > > > > > > > > > I am very interested in the import/export library > > > > > you > > > > > mentioned. > > > > > > > > > > It would be great to work together on this. > > > > > > > > > > Best regards, > > > > > > > > > > Michael > > > > > > > > > > > > > > -- > > > =========================================== > > > = Dipl. Phys. Michael Sögtrop > > > = Datenerfassungs- und Informationssysteme > > > = Steuerungs- und Automatisierungstechnik > > > = > > > = Anzinger Str. 10c > > > = 85586 Poing > > > = > > > = Tel.: (08121) 972433 > > > = Fax.: (08121) 972434 > > > =========================================== > > > > > > > ----------------------------------------------------- > > ------
> > > > --------------- > > Check out the vibrant tech community on one of the > > world's
most
> > > > engaging tech sites, Slashdot.org! http://sdm.link/slas > > hdot > > _______________________________________________ > > Inkscape-devel mailing list > > Inkscape-devel@lists.sourceforge.net > > https://lists.sourceforge.net/lists/listinfo/inkscape-d > > evel > > ----------------------------------------------------- > --------
> > ------------- > Check out the vibrant tech community on one of the > world's most > engaging tech sites, Slashdot.org! http://sdm.link/slashd > ot > _______________________________________________ > Inkscape-devel mailing list > Inkscape-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/inkscape-dev > el >
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
This email has been checked for viruses by AVG. http://www.avg.com
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
participants (6)
-
C R -
Lex -
Lex Neva -
Mark Schafer -
Martin Owens -
Ryan Gorley