Re: Embroidery extension

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Susan Spencer-2
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

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Inkscape - Dev mailing list
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/>

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Lex Neva
In reply to this post by Susan Spencer-2
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/clinton_poker_league.jpg

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
<[hidden email]> 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/>
>



------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Inkscape - Dev mailing list
In reply to this post by Susan Spencer-2
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

------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Windell H. Oskay
In reply to this post by Lex Neva
Hi Lex,
The generic fill shape problem is the same one that I reported seven years ago, in the context of LPEs: https://bugs.launchpad.net/inkscape/+bug/657139

I too have written a tutorial (very similar to yours) on how to get around the problem by taking a thin slice out of an object: http://wiki.evilmadscientist.com/Creating_filled_regions#Workarounds_for_hollow_geometry_hatch_fills


We did go a few steps further and write an extension ("eggbot_hatch") that could fill an arbitrary region with paths. It does not have awareness of thread, stitch length, and some of the other parameters, but is reasonably quick, does the back-and-forth rows, can manage insets, avoids overlapping lines, and does indeed handle cases of complex geometry. We use it in the context of pen plotters, to fill arbitrary regions with a pen path.

It's available as part of the EggBot project, here: https://github.com/evil-mad/EggBot/tree/master/inkscape_driver


As you note, this is a "solved" problem, since it is done extensively in other contexts as well. Aside from pen plotters and embroidery, one notable context is that of 3D printers, where the print head must fill arbitrary, complex regions that result from slicing through a physical object, without the print head overlapping its previous position (at any given height). If you would like another possible starting point for looking at this problem (aside from LPEs and the eggbot_hatch), you might consider starting with their existing codebases that manage this process. One well known "slicing" tool chain written in python is Skeinforge: http://reprap.org/wiki/Skeinforge


Side note: It would be really fantastic if embroidery file format support was eventually added.

Cheers,
-Windell

> On Jul 30, 2017, at 7:56 AM, Lex Neva <[hidden email]> wrote:
>
> 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/clinton_poker_league.jpg
>
> 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


Windell H. Oskay, Ph.D.
Co-Founder and Chief Scientist
Evil Mad Scientist Laboratories
175 San Lazaro Ave, STE 150
Sunnyvale CA 94086
http://www.evilmadscientist.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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Mark Schafer
In reply to this post by Lex Neva
This problem might also be viewed as the standard raster fill problem
common in CG texts for many years.  A lot of work has been done on this
including efficiency.
Polygon to raster conversion and filling.
I'd suggest starting with:
  -
http://what-when-how.com/computer-graphics-and-geometric-modeling/raster-algorithms-basic-computer-graphics-part-2/
  - https://www.cosc.brocku.ca/Offerings/3P98/course/lectures/2d/

but many more under a search like "raster fill algorithms"
To avoid going over the top of another embroidered thread consider
polygon clipping algorithms.


On 7/31/2017 2:56 AM, Lex Neva wrote:

> 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/clinton_poker_league.jpg
>
> 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
> <[hidden email]> 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/>
>>
>
>
>
> ------------------------------------------------------------------------------
>
> 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
> [hidden email]
> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Brynn
In reply to this post by Lex Neva
Welcome Lex!

I'm not a developer.  But just wanted to comment from a user perspective.

This has often been requested in forums.  I know one member who has managed to
take Inkscape designs to machine embroidery.  But he has to use a different
product in between.  An all-Inkscape product would be awesome!

Good luck :-)
brynn

-----Original Message-----
From: Lex Neva
Sent: Sunday, July 30, 2017 8:56 AM
To: Michael Soegtrop ; Susan Spencer ; [hidden email]
Subject: Re: [Inkscape-devel] Embroidery extension

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/clinton_poker_league.jpg

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
<[hidden email]> 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/>
>



------------------------------------------------------------------------------
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Lex Neva
In reply to this post by Lex Neva

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





------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Lex Neva
In reply to this post by Windell H. Oskay
Hi Windell!

<3 Egg-bot!  I don't have one myself, but the related inkscape
extensions have been very useful to me, both for embroidery and for
playing with my newer toy, a Silhouette die-cutter/pen-plotter.  Fun stuff.

Thanks for the tip on Skeinforge.  I'm having a bit of a hard time
finding solid documentation on it, but judging by google image search,
it does indeed solve a very similar problem!  I'll definitely have to
dig further into it.

One thing I can't tell from images and due to my lack of knowledge of 3d
printing is whether the machine has any ability to stop extruding a
color, move elsewhere, and start again.  That'd be akin to the ability
of egg-bot and other pen-plotters to lift the pen and move elsewhere. 
That's a luxury I don't have in embroidery, which is what bends my mind
so much.

I think maybe from looking at Skeinforge screenshots that it possibly
doesn't have the stop/move/start capability but can move in the Z axis. 
Perhaps creating a one-layer-deep object in skeinforge is the same
problem as embroidering a fill region. I'll have to look into this more
closely.

Thanks,

Lex

On 7/30/2017 3:27 PM, Windell H. Oskay wrote:

> Hi Lex,
> The generic fill shape problem is the same one that I reported seven years ago, in the context of LPEs: https://bugs.launchpad.net/inkscape/+bug/657139
>
> I too have written a tutorial (very similar to yours) on how to get around the problem by taking a thin slice out of an object: http://wiki.evilmadscientist.com/Creating_filled_regions#Workarounds_for_hollow_geometry_hatch_fills
>
>
> We did go a few steps further and write an extension ("eggbot_hatch") that could fill an arbitrary region with paths. It does not have awareness of thread, stitch length, and some of the other parameters, but is reasonably quick, does the back-and-forth rows, can manage insets, avoids overlapping lines, and does indeed handle cases of complex geometry. We use it in the context of pen plotters, to fill arbitrary regions with a pen path.
>
> It's available as part of the EggBot project, here: https://github.com/evil-mad/EggBot/tree/master/inkscape_driver
>
>
> As you note, this is a "solved" problem, since it is done extensively in other contexts as well. Aside from pen plotters and embroidery, one notable context is that of 3D printers, where the print head must fill arbitrary, complex regions that result from slicing through a physical object, without the print head overlapping its previous position (at any given height). If you would like another possible starting point for looking at this problem (aside from LPEs and the eggbot_hatch), you might consider starting with their existing codebases that manage this process. One well known "slicing" tool chain written in python is Skeinforge: http://reprap.org/wiki/Skeinforge
>
>
> Side note: It would be really fantastic if embroidery file format support was eventually added.
>
> Cheers,
> -Windell
>
>> On Jul 30, 2017, at 7:56 AM, Lex Neva <[hidden email]> wrote:
>>
>> 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/clinton_poker_league.jpg
>>
>> 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
>
> Windell H. Oskay, Ph.D.
> Co-Founder and Chief Scientist
> Evil Mad Scientist Laboratories
> 175 San Lazaro Ave, STE 150
> Sunnyvale CA 94086
> http://www.evilmadscientist.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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Inkscape - Dev mailing list
In reply to this post by Susan Spencer-2
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


------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Lex Neva
In reply to this post by Lex Neva
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
<[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Lex Neva
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 [hidden email] 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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Ryan Gorley-2
Sounds incredible. Well done!

Ryan Gorley
Managing Partner | Dijt

On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <[hidden email]> 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 [hidden email] 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
[hidden email]
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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

Martin Owens-2
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 <[hidden email]> 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@Michael
> > > -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 
> > > [hidden email] 
> > > 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
> > [hidden email]
> > 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
> [hidden email]
> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel
C R
Reply | Threaded
Open this post in threaded view
|

Re: Embroidery extension

C R
+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" <[hidden email]> 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 <[hidden email]> 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@Michael
> > > -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 
> > > [hidden email] 
> > > 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
> > [hidden email]
> > 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
> [hidden email]
> 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
[hidden email]
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/inkscape-devel