Join GitHub today
GitHub is home to over 31 million developers working together to host and review code, manage projects, and build software together.Sign up
Pattern fill #33
By carefully choosing where the needle penetrations fall in each row of a fill, we can create some pretty nifty fill effects. It'd be especially cool if the user could add their own, perhaps with a mini extension to set up a template canvas.
@wwderw How often do you use patterned fill?
Wilcom calls them split stitches.
You have "user defined split stitches" that are defined right then and there as you digitized and are only good for that object that its' assigned to. Then you have ones that you can "save" and re-use indefinitely. That I would think would be your "template".
These "splits" also form the basis for motifs for motif runs and motif fills.
They can also be used in the applique module as embellishments.
These are great for textured look as well.
Got it. How highly would you prioritize this feature?
I've only seen a few examples of this kind of thing in the wild. If you have a chance (no rush) could you share a few example design files? It would also be really useful to see what they look like actually stitched out, if you can take a close-up photo.
What's the distinction between a split, motif, motif run and motif fill?
I might be able to over the weekend. I'll just create a couple of examples stitched out.
A split is using extra needle penetrations to create the pattern. A split satin stitch is along the lines of split stitches, just typically right down the center.
A motif is just a single instance of a pattern. But unlike a split stitch, it's actually stitched out on it's own. Run, satin, even fill stitches.
A motif run would be repeating instances of the motif pattern along a line. A motif fill would be the same thing but with the fill of an object.
Ideally, for runs and fills, we would like to be able to tweak an individual object on the fly (typically size) and have that be applied to all the motifs on the run and/or fill. Maybe a height/weight option box to input size?
I happily discovered inkstitch not long ago and was creating some embroidery within the last few days. It's really nice! Just for info, I am using the dst output format.
I haven't got a lot of experience with embroidery at all, so I don't know if it makes sense what I am thinking.
But I'll give it a try.
What do you think about it? Does it make sense?
I think that would only be possible if we used 2 lines and the calculations used the blend feature of inkscape to build the middle patterns and convert them to paths Acually you can do this manualy currently with the blend and do a running stitch on those lines i think 2018-02-12 10:46 GMT+00:00 Kaalleen <firstname.lastname@example.org>:…
I happily discovered inkstitch not long ago and was creating some embroidery within the last few days. It's really nice! Just for info, I am using the dst output format. I haven't got a lot of experience with embroidery at all, so I don't know if it makes sense what I am thinking. But I'll give it a try. Sometimes while creating filled areas, it occurred to me that it'd be nice to have the stitched lines following a curve. This isn't exactly a fill pattern, but it would give some variation to the look of the design. I mean, just like you can force a direction with the crossing paths to the satin column, it might be possible to implement this to a fill area too: draw a simple path through the area which will be filled and the fill would be an array of parallel duplications of this particular curve?!? Perhaps it's easier to explain with an example image: [image: curvefill] <https://user-images.githubusercontent.com/36401965/36093041-a932358e-0fe9-11e8-8590-d3e952006a98.jpg> What do you think about it? Does it make sense? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#33 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKke-mZOyehgEHT8tbTVGxLbUlbgYGaWks5tUBZtgaJpZM4Rqkqk> .
-- Com os melhores cumprimentos, Vinicius Silva
I am not exactly sure what you meant by the blend feature, but I found the interpolate option quiet useful (is it that what you meant?). It's kinda hard to tweak it to the desired density and also to control the stitches to not all being side by side to each other horizontally. But at least, it is working for me now. Thank you.
Curved fill is definitely something I want to support in the future. It's possible but the math involved is pretty complicated, and I haven't wrapped my head around it yet.
You certainly could use interpolate and running stitch, but it's going to look terrible. While it's true that fill stitch is just a bunch of rows of running stitch in alternating directions, you have to carefully control where the needle penetrations fall in each row to get a nice overall appearance. Otherwise, the needle penetrations will randomly line up between rows, creating distracting troughs.
Ultimately, I'd love it if inkstitch could do pattern fill that is also bent into a curve. Someday we'll get there!
Attached are a couple of examples.
The one one top uses motifs that are stored in the program and applies it over the entire area. I don't think that one we would be able to do, as I don't think we would be able to store the motifs in the same manner.
The one on bottom is the one that I think we would be able to do. And it is also the way that @X3msnake is talking about. The biggest difference is that it only applies to the portion of the area that has the desired pattern on top. So if we want the entire area to have that pattern, we have to set it up that way, otherwise it will only apply the stitches over the area that is covered.
I think it's best to leave it that way, because there are some instances we you would only want those areas stitched in that manner and not the entire object. Sometimes, we would want the entire object, but not always.
Cool share your thought process with us No dia quarta-feira, 6 de junho de 2018, Lex Neva <email@example.com> escreveu:…
I have a fairly good idea of how to do at least one kind of pattern fill. It's a fairly big job, so it may be awhile :) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#33 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKke-r8HrlVGglqO2ZzT7YXVEP_pypVAks5t5y0CgaJpZM4Rqkqk> .
-- Com os melhores cumprimentos, Vinicius Silva
I think that having some extra editing tools (like the rungs) would be cool for designing some fills.
But I also got another idea:
Now if you could create some sort of plugin mechanism, where area designers could define a function returning the stitch path and that:
then you maybe could start some sort of competition among programmers to design really cool patterns for InkStitch without having to understand the whole software.
Does that make sense ?
Pretty much what it says in my original post at the top. I'm thinking of allowing the user to create templates for fill stitches as separate SVGs and install them in some known directory. A pattern would just be a set of paths with nodes where you want the stitches to be, just like manual stitch paths. Ink/Stitch would then tile the pattern over the shape and calculate the intersection. I think the patterns would need to be parallel lines, rather than curves or angles like in @danielkschneider's last row, but I'm not sure.
@danielkschneider interesting ideas! The biggest problem is choosing the stitch order. It took me, no kidding, 2 years to figure out how to do the auto-fill algorithm as you see it now. Choosing what order to stitch the rows in a fill is a very difficult problem. Add in the complexity of lines that wander up and down (rather than just being horizontal lines) and I'm not really sure how I'd adapt the stitch routing algorithm to cope.
This is where I'd really love it if a PhD graph theoretician would join the project... ;)
"... I'm not really sure how I'd adapt the stitch routing algorithm to cope." -- This took me a goodly amount to solve. You don't even have the right question. What you actually want to solve is not this more focused problem but the more general one:
The simplest and consequently least helpful solution is by describing each and every stitch. A stitch is the simplest and most basic unit possible to describe a grammar powerful enough to implement every possible fill of every possible area. Traditional embroidery is a very powerful grammar to describe a useful subset of fills. But, consequently by its very nature you can only describe the fills that have been imagined and not the unimaged ones, and those are still far greater than the former. Daniel is, to his credit though, only scratching the surface there. And if you look at some other programs like Excentro which also fills areas with lines, but took a radically different evolutionary path than embroidery and you start to realize there is a lot of stuff that isn't being served by this paradigm.
There is a pretty good reason I'm rather jaded about the whole "vector + fill = embroidery" paradigm, mostly I think it's a high level grammar, that to solve common algorithms like tatami you already need to break into more manageable bits. And several of those bits can be captured by a better, more inclusive, and simple, yet powerful grammar. If you were to describe a tatami algorithm what "parts" would you use how would you describe the order of those parts? And also, how could you describe every possible order of those parts? There doesn't seem a simple socratic question to make the point that these types of grammars actually end up describing parts that have no required relationship to vectors or closed-shape vectors, and that actually ends up making them much more powerful. Though it does require some powerful mathematics but you end up getting tatami with a wavy line for free in them, or a cycloidal line, or ones that bend in defined but fascinating ways, intersect with each other, interact with each other etc.
Imagine how much easier and powerful @danielkschneider idea would be, if you had a properly defined language to describe what a fill is? Because stuff like this line comes from here, in this way, this often, wiggles like this and hits a wall and stops are not events that are impossible to describe in simple yet powerful ways. Or hard to build-out with methods capable enough to capture all the power of traditional embroidery, but without the need to reinvent the wheel because the line zigzags. Those shackles are baked into the traditional methods, they are mathematically required by the paradigm itself.
That's generally why I built the formats engine, because solving the general problem left me sufficiently jaded with regard to the paradigm as a whole. But, every embroidery will, at the bottom, become stitches and get written into commands. So something that turns lines into commands will always be useful.
Though, I'm not a PhD in graph theory (BS in CS), I do have a pretty fundamental understanding of linear geometry and graph theory, enough to suggest that you might want to look into physics engines and raytracing, and the core dynamics of Eulerian graphs as constraints. Or don't.
All of that is interesting stuff, and I see what you're saying. That said, you're speaking in generalities, and where things get difficult is in the specifics.
For example, Eulerian graphs are a really powerful tool for graph creation and solving, but when you get down into the trenches, just because "there exists a solution" does not mean that it's easy to find. Hierholzer's algorithm is great, but you have to find a new loop at each iteration, and that can be very expensive. I too have a BS in CS, and I know my way around a graph, but I'm no PhD. And I have only found a single formal paper that discusses a topic similar enough to embroidery fill stitch to be useful.
I'm actually not ready to work on this right now. If you're interested in working on the auto-fill algorithm, by all means please take a crack at it! Non-linear fills would be an awesome feature. If you're interested in throwing together a PR, I'd love to see what you come up with.
At issue is that to do them you really have to do what it seems like it would be needed. You need to implement a 2d graph engine with collision detection. You need to treat the various lines that emit from a particular type of fill, as rays and do the physics and find the point of the intersection. While you can do some fun things to make simplistic monotone fills, what you are basically doing is making the collision detection easy. When you do things like satin fills these tricks even start to break down. What you actually need is a general solution to the problem if you draw a line from this point going this direction, when do you hit the edge of the shape. You can also do things like make patterns within that ray, reflect the ray, refract the ray, bend the ray as it travels through this particular area, make the end location kinda fuzzy if it's within this other area.
When you actually have a ray tracing algorithm properly implemented then you can do things like make the lines wavy without screwing up the math. The solution ends up sharing more in common with 2d physics engines than the simple methods used in very basic fills.
This also allows you to define fills in terms of lines and sequence. Namely a line where the various points in the line effectively launch rays into some boundary. You can then breakdown the rest of the embroidery into simple commands. So things like tatami fills can be defined in terms of their sequence and simple monotone fills. You basically end up coding a monotone shape partitioning algorithm in sequences like, stitch to here, then fill to this point, stitch to here, fill to this point. But, when you break things down to an easier command like "fill to this point" that has no dependencies on the shape it's filling, you end up with grammars wherein you can more easily describe traditional embroidery but lose nothing in their ability to describe all fills imagined and yet unimagined.
I properly have worked out the specifics. I write my own embroidery program. Hence the well thought out way to implement a highly powerful and useful grammar while maintaining the near infinite possibilities. My somewhat jaded outlook is because that grammar, to be highly powerful, must categorically break the artificial and pointless dynamic that embroidery = shape + fill. And rather treat embroidery as an unbroken sequence of middle-level command paths, that interact with a rich environment that results in line segments. Within that, though, you can properly implement all the various algorithms developed for the traditional embroidery paradigm.
I might be stupid (and probably am since my BS and MS is not in CS, but Equine repro and nutrition, pointless in this discussion). What I'm wondering is how is it that commercial software appears to have reconciled the issue without breaking "embroidery = shape + fill"?
Or is what I'm seeing in the front end (which appears to follow the "embroidery = shape + fill") actually not happening in the back end, but something else is at work?
In all honesty, since I am somewhat of a dumb user (and I really am) the front end has to make sense to me and the results have to look good to me. That paradigm of embroidery = shape +fill does that for me (and a lot of people in this trade that are also less then knowledgeable users when it comes to the back end). Back end I leave up to smarter individuals then I.
So what is that piece that I'm not getting that some software is able to reconcile this issue? Or at least make it appear to me using the front end that they have reconciled the issue? Or has it been mentioned and my lack of knowledge is once again rearing it's ugly head?
To be honest, @tatarize, I can't really follow all of what you're saying. Maybe I lack the background?
In any case, we don't need to implement any special ray-casting algorithms. Shapely (the Python 2d shape library Ink/Stitch uses) can handle that easily.
I freely admit at the far end I come off a little bit raving. But, I honestly think the best way to render even traditional embroidery is by breaking it down into a subset of sequence paths that can themselves be broken down into segments and then into stitch commands. A lot of the problems with various problems with embroidery are made much easier to solve in such a grammar and actually can capture the all the power of possible embroidery without limiting like it is in traditional embroidery. I think something that is basically like a 2d physics engine with some weird highly non-standard properties (like explicit patterns, loops, etc) can be made to map all possible methods for filling a shape.
Take start and end points on a simple to-be-filled sphere. The way the algorithm works is that you underpath between the start point and the topmost splitnode then do a monotone fill down to the end node, you then underpath to the bottom merge node, then do a monotone fill back up until you reach the exit node. The point here is that everything described there is could be its own object at the most basic level. You have path, montone fill, path, and monotone fill. And that's how you fill a sphere, but what if you wanted to do it differently, say move along the edge, monotone fill the entire shape then walk the edge to the end node, or what if you the end user has a better way to do such things that you the programmer hasn't actually thought of?
You end up making these algorithms that work with a bunch of custom middle-level paths objects but you can actually implement those and maintain much of the power such a scheme has. You could with a sort of 2d embroidery/physics engine implement all the lower level pieces without compromising power. Rather than a fill, you could define these lower level elements, and how they interact, and from these you could build any number of important effects without relying on what amounts to pre-established algorithms (though you could certainly have those too).
You can also do things like building other highly powerful methods for making embroidery and share more in common with finger painting than vector graphics.
You can obviously implement these higher level pieces without an effective middle language but it's the reason why when sometimes the algorithms don't give you want you need you have to cut it into smaller pieces and coax it into working for you, rather than having the sequences created by the higher level embroidery objects simply arranged in ways that are less objectionable. The idea would be since things get reduced to their required bits and not one iota more, you'd have a better language than just stitches or shapes.
This is a hard sell to end users. If you want them to swap paradigms, it has to be better then what they are using in every way. Not just equal, equal will get you the newbies, but it has to be superior. If it isn't, you won't get the old timers to switch. It can't also be about theory, it has to be on the ground, ready to go and deliver superior quality.
The first 4 yrs of my learning was manual input. One stitch equals one needle insertion. You don't get much more powerful then that, but that does require a lot of knowledge of the user (more then what you are going to see from the average user today). The last 20 yrs has been following the object based paradigm, but still have the ability to do manual input.
As an end user (not as a programmer mind you) it makes sense to me in a lot of ways and provides a lot of benefits to me beyond just the embroidery = shape + fill with this traditional paradigm. And it also has that nasty 20 yr indoctrination in me as well.
I'm not exactly feeling this.
Now granted, I'm approaching all of this as an end user.
This discussion made me think a bit :) As a fairly newbie end user I also find the "filling shapes" paradigm quite natural, but I cannot come up with a clear ontology of embroidery elements. Firstly, the concept of shape is not uniform. Some distinguish lines, areas (polygons) and columns, others only (out)lines and fills. Areas can have either fills or strokes or both (same as in vector drawing) and both can filled. Notice the different meaning of "fill", i.e. it either means the surface of a polygon or its "embroidery points, i.e. a texture".
Then, there are stitch types, defined apart. From this bag of stitch types one can use some for each shape type, e.g. you can fill an area with a motif done with programmable line stitches or with a repetitive satin stitch. In other words, one cannot tie a stitch type to a shape types since most stitch types can be used in all types of shapes.
On top of that there are modifiers, e.g. add fuzzy edges, partitioning into subsections, direction lines, gradients, curving of fills. Most often, an area is not just filled with a pattern (e.g. like a color in vector drawing), but the way it is filled is defined by various parameters and extra objects such as direction lines.
Anyhow, on a more practical side, I had a look a how some embroidery software defines this "fill" and so far I noticed that fill as "stitch type" and its parameters defines most but not all of the filling. E.g. your rungs are good example of that.
It does seem rather natural and it is. But, if you think of the elements you realize it's a bit arbitrary. Why closed-form shapes. And why does everything need to be in a shape? What if I trace the outlines in a figure defining particular areas. That's not a shape per se. Why do I need to break it into shapes. Why can't you just use a well defined set of areas. Image the outlines of say a coloring book, or something like paint by numbers. Those aren't actually traditional shapes but they would obviously work the same way.
Mathematically the important elements here are defined by the concepts of monotony and sweepability. Can you move a scanline in a particular direction and reach every area of of a shape. And can you move a scanline that you can change the angle of, and reach every part of the shape. The bulk of a lot of algorithms like tatami in other similar genres and maths and procedures are the partitioning of polygons. I printed out a pretty excellent paper on the Optimal uniformly monotone partitioning of polygons with holes which while not strictly about tatami or the traditional algorithms used in embroidery does a lot to point out that there's a rather staggering amount of other ways to partition a polygon, even things like dog-ear partitioning within the triangulation of polygons are ways to break polygons down into monotone shapes.
When you give it some serious thought as to how to classify things it seems like the most basic is a scanline fill of a monotone polygon. But, really you can do a scanline fill of a non-monotone polygon by simply failing to fill these other sections. You end up with a scanline fill that is dictated by its location, and things like tatami are actually algorithms that dictate how a closed-shape polygon can be turned into a sequence of scanline fills, and underpathing. But, there's sometimes issues with the order such algorithms choose and end users need to coax it into filling things in better ways.
Not only can you not tie a stitch type to a shape, but you don't really even need the shape, what you need are contingencies for what happens when atypical events occur. What happens if you aren't bound within an area with walls that a ray would strike? What happens if you cross paths with your own fill? What happens if you hit a different boundary first? These things actually are dealt with in a bunch of different ways and are often called by embroidery programs as invalid geometry. But, really if you're dealing with events rather than geometry you can deal with all of these contingencies and they will result in various different ways to deal with otherwise invalid geometry.
You end up defining fills as what amounts to a sequence. You absolutely cannot avoid having a start position and an end position. But, how you interact with the environment between those points becomes an open question.
Imagine if you had a few different things in an environment, like boundaries, and refraction points or areas that sort of randomize rays or made an endpoint rather fuzzy. And you used in this environment things like direct stitches, pattern stitches, various algorithmically defined stitches, and things like scan line fills. You could use just those elements to basically match any modern embroidery, in fact you could use direct stitches themselves to do all of that. But, you end with only more powerful building blocks but building blocks that are entirely disjointed from the definitions of shapes.
You could apply those modifiers not simply to the fill but to the environment. So you could affect an edge to be more fuzzy, but since it's not so tied in with that particular fill you could define how fuzzy it is and where that fuzziness occurs to a level and degree that would otherwise be impossible. You could define a particular shaping of a fill not just as an effect but in ways that would actually change where that fill ends up filling. If you could tuck around a corner and fill some stuff over there, it might actually be really useful depending on what a person is going for.
The connections between these modifiers and stitchings and modifications of these scanline fills and these other modifications is nothing to do with shapes. The only thing shapes tend to do is serve as boundaries points. So why not just define boundary points and what they do? So you could have areas and shapes, and boundaries that actually have fuzzy edges rather than requiring that be a part of the fill. These are often attempts to blend different colors together after all, and so you need like 3 overlapping areas with different fills and fuzzy edges to get the blending right. Why can't this be one area with some internal fuzzy boundaries and a couple fills and seem much more straightforward.
I'm not entirely suggesting reinventing the wheel here. I'm saying you could certainly do the typical traditional embroidery algorithms. You'd just break those shapes down into their proper subobjects which would then break down into the segments and thus stitch-commands. But, if push came to shove and you didn't like the way the embroidery program did this higher level stuff, your alternative wouldn't be purely stitches or a bunch more shapes to coax it into doing what you want, it could be the middle language the algorithms tend to already use but in a more overt way.
It's just that the elements you use to build these higher level things could be made more overt and defined in a different but better grammar that doesn't lose you any power. If you wanted to use the traditional fills where you draw a circle and fill that circle, define a start and end point and define what kind of zigzag you want around the circle too, then have it it. But, if the program properly dealt with that as an algorithm that defines a boundary, and has one stitch that directly stitches to the top, does a scan-fill line to the endpoint, direct stitches to the bottom scan-fill line to the end point and reaches the end point then follows that same boundary with zigzag pattern back to the end again, you would get the same result, but you could also take any of those elements and change them. You could zigzag around the edge backwards, you could scanline fill the entire shape and use the zigzag to hide the underlay stitches, you could decide to trim the stitches at some point then go off and stitch something else and then come back to the rest of the sequence later.
The higher level traditional embroidery stuff is actually broken in ways that are woefully limiting and few people seem to realize this. Rather than vector based color-forms embroidery can be basically anything. If you can do it with line segments then you can do it with embroidery, so why don't we see many fractal designs in embroidery? Why don't we see many wonderful artistic flourishes that are as amazing as the amazing artists who create them? Why do we see only what basically amounts to really well made clipart with flat fills, with some good experts using the direction of the stitching or length of the stitches to give it a nice effect.
I'm over here able to sew photorealistic raster images with pretty robust set of algorithms and no artistic ability and somehow the paradigm is limiting people to really well thought out clipart isn't at least weird?
The math isn't intractable, nor is it needed to only define some particular method, but the methods needed to produce modern traditional embroidery are replicable given a few different elements, and what the smallest most powerful methods are clearly going to be the best, and exploring what those might be isn't something I've fully done yet, but given a scanline fill and some stitches it's pretty easy to duplicate most all of modern embroidery into elements more complex than stitches and less complex than the larger algorithms but these do not actually limit the power of the medium. Obviously you build the tools people are used to, but you can build them in ways that also give them much more power, rather than a block box wherein you give it a vector shape and it gives you a filled vector shape of stitches.
Apparently people understand this for 3d printers, but don't realize all these same ideas would work fine for embroidery fills of various areas. http://irc.cs.sdu.edu.cn/CFS/
Seriously, if you defined this as a method you could fingerpaint your embroidery. Not that ww loves that idea, but there's clearly a lot more that could be done, though none of this falls into the sort of classic paradigm.
Uh, they aren't all closed form shapes. Manual stitches aren't. Run stitches aren't. Some satin stitches are lines as well. You use some line stitches you can swap between run and satin. Fills, yes they are closed shapes and it makes sense as to why that is.
Unless I'm missing some different mathematical definition of closed form shapes.
Not even in Ink/Stitch are they all closed form shapes.
Quite a bit of manual stitches in there. Not all closed shape fills. In fact, closed shapes (again, unless I'm missing some mathematical definition of closed shapes) aren't use all that much in the design.
You have to understand, that digitizers that came from the days of 1 mouse click equals 1 needle penetration (manual stitches), artistic ability combined with production knowledge is what allows cream to raise to the top.
If it was efficient to do so, the manual stitch tool would be able to do everything that needed to be done (it still does, but with the software that's out there, it's not in good business sense to totally do it that way). Including satisfy this "issue".
I think the biggest issue here, is that there is a huge disconnect of what you are trying to accomplish. The end user has to understand it. I'm sorry, I don't understand a tenth of what you are saying and I'm probably more willing to try to understand then most out there. The examples that I'm seeing, are not the examples that leave my shop. There has to be a connection, a gap that's bridged and it's not there.
From a programmer's perspective, it may be better, more elegant etc (I stress may, because it still seems like a lot of theory still), but if it doesn't connect with the end user that has to buy into it, it doesn't make it.
Basically, the question is how this is applicable to the user.
If I choose a "fill effect" or a "pattern fill" in a design, then I personally do not care what kind of algorithm is being executed. - The main thing: it corresponds to my ideas or wishes and should also be embroidered as previously displayed and set.
From the programmer's point of view, of course, things are different.
I think that @lexelby wants to finish his ToDo list, so that "all" can work and test it and InkStitch works almost flawlessly. That's how it should be.
Well, my comment on this is not really helpful and leading in one direction, but these comments are very exciting to read.
An interesting idea from @tatarize, I have to admit.
P.S. : All roads lead to Rome
As I see it, @tatarize is trying to say (paraphrased):
A reasonable concept. However, as with @wwderw, I'm afraid can't understand a tenth of what you're saying. I can't really make heads or tails of what a "generalized grammar" actually looks like. To be clear, I'm not asking you to explain at this juncture!
As @wwderw implied, we need to focus on our core audience: professionals producing designs for garments, patches, etc. I want to fill out all of the basic features to capture this user base before I spend any development effort on the more esoteric use cases. I don't want to work on Fermat spiral fills right now (for example) because vanishingly few if any designs out in the real world use them.
@tatarize, I think you're concerned that if we don't lay the foundations in the code now for the "generalized grammar for all possible kinds of fills" that we'll be forever stuck with traditional fill styles. I disagree. I'm confident in our ability to refactor the stitch engine in the future.
On the contrary, I fear that, if we start to try to give these esoteric use cases equal footing in the code now, our user interface will inevitably change to facilitate that. There's a slippery slope here: "implementation-driven design". The risk is that complexity under the hood will inevitably result in complexity in the user interface.
Bottom line: I'd like to wrap up this line of discussion now.
This issue will remain to capture one kind of pattern fill: "scanline" fill with carefully-chosen needle penetrations resulting in a patterned visual effect.
For other kinds of fill algorithms, please open individual issues. We'll prioritize them as makes sense given our core target user-base.
One last thing: let's all try to find ways to say more with fewer words. I know we're passionate about this topic, but let's please remember that everyone's time is highly valuable on a volunteer-based project like this. A short, carefully thought-out paragraph can often be far more convincing than ten pages.
I recognize that this comment comes dangerously close to violating that guideline... sorry!
As is, new features will require a lot of new math and a new algorithms to do any new thing. And these basically need to be built from the ground up. There's a rather implicit way of expressing what such features do and a framework that properly captures that grammar is not a massive endeavor, the subset of things to reproduce what other embroidery design software does is far less still. Without such a framework putting a tapering fuzzy edge on a satin fill or a flat fill, or column fill become a six different problems rather than 1, more if you consider how various geometries would affect the math. It isn't about the arcane utility such a system oozes but the mundane solutions it permits. Carefully-chosen needle penetrations in a scan-line fill, will not and cannot say anything about the carefully-chosen needle penetrations within satiny-sweep fills, or spiral fills, or fills between several types of fills between different types of objects.
If you only do zoom and pan your typical affine manipulations are likely doable with some effort and work, and throwing additional math new edge conditions. But this math gets downright trivial if you have transformation matrices and even though it would include some esoteric things like the ability to skew points anchored at a particular position, it's the mundate zooming and panning that make the scheme so powerful. You can build the concepts of needle-penetration patterns and scanline fills and vector objects without building only the concept of a needle-penetration pattern within a scanline fill of a particular vector objects. If you can articulate the ideas independently from medium, you can build a framework that does the same. Then scanline fill and scanline fill doing loop-de-loops, are pretty much the same thing, outside of the loop-de-loops.
@tatarize, you're treading dangerously close to being offensive here. Please stop. I said above (June 6) that the current auto-fill algorithm took me two years to fully understand and implement. It's not due to lack of intelligence or math/programming skill on my part; this problem space is anything but trivial.
I still don't really understand what you're talking about. Perhaps I'd understand better in the form of code. If you'd like to continue along this line of discussion, how about you write up a PR that replaces the existing autofill algorithm with your idea? If it truly does keep the user interface as it is now while also opening doors to future expansion, then I'm all for merging it in.
Apologies. I was wrong.
I did not intend to be insulting. But, I had a completely wrong view of the internal mechanisms for your fill routine. I assumed it was standard. It's not, it's actually novel and brilliant.
Usually fill routines share much more in common flood fill algorithms. In fact they are quite trivial flood fills. You go from the start point, and if there is an area above, that can be filled, you search more and more upwards until you reach the top. You then fill that area in boustrophedonically unless/until you again find an area that isn't filled above where you're filling, it recurses to do step one again at the new location. Underpathing to a new topmost point. And continues until such time as the shape is entirely filled. It requires some caveats, but the code is simple, straightforward, and horrible.
Your approach is actually much more novel and much more useful than those. Rather than mimic a flood fill algorithm you fill the entire polygon with lines and link together the outer edge of the shape, then use the resulting graph to find a Eulerian subset prioritizing the internal lines and allowing edge bits to be deactualized.
I had naively assumed your code would have implemented the actually rather simplistic flood fill approach, but your code is wildly more useful than that. In fact, there's a couple things I hadn't managed to solve that are a bit off the beaten path, that your rather novel approach actually could solve pretty easily. In fact, I daresay you should extend your code to a bit more of a generalized form. It'll obviously work for anything. You really could slap down loop-de-loop (cycloidal) lines, or those with a sinewave, and you'll still end up with a solvable Eulerian graph, even if the signwave forced a collision with a completely different part of a different polygon.
Your code, already works completely independent to the shape. You really could simply leave everything the same, and use wavy lines, or pattern lines or anything. What matters is that you preserve the Eulerian ability, but if you have edges, that you'd be okay removing or duplicating, you could always solve the graph for a Eulerian graph. In fact, you could add some ability to jump small distances when an ever an edge node is close to another edge node and naively break sequence in novel ways to still complete such fills.
I've always loved how gosper flowsnakes look internally and a bunch of other fractals and I had thought of using a polygon-crop to capture the internal bits for a fill, but oddly enough your framework could solve a cropped-edged fractal-fill as a consequence of how it works. rather than as a somewhat alien set of methods. In fact, if using shapes as sort of cutters of internal patterning you really could implement any fill you wanted.
To the contrary, your code is quite clever, and shouldn't limit much of anything. Additions like patterning the stitches or using wavy lines or sign waves are effectively free to you already.
Caveat to statement "What matters is that you preserve the Eulerian ability, but if you have edges, that you'd be okay removing or duplicating, you could always solve the graph for a Eulerian graph." -- The math there actually requires that the original fill is possibly Eulearian. Or rather if it is the case that fill being modeled is internally Eulerian, it have that properly maintained along the edges definitionally. So clearly things like cross hatching or wavy-lines work but nothing about the algorithm could save a fill of a bunch of triangles as a fill. So long as the fill is internally Eulerian. nothing about cropping at the edges and solving would violate that property. You can clearly view the edges like it's own graph. if there's nothing problematic internally, the edges cannot cause a problem. You can have any connections you want at the edge, so you can always have a Eulerian edge.
Thanks, I'm glad you like it. I had one algorithm prior to this that was similar to your "naive" approach: it broke the area into monotone shapes and filled them one at a time, pathing between them using running stitch around the outline of the shape. It could sew along the same spot on the outline many times, which wasn't ideal. The reason I did that was because I could never figure out how to do underpathing (some kind of pathfinding algorithm?) and how to order the sections in such a way as to avoid painting myself into a corner.
That approach worked, but it notably could not handle shapes with holes in them. The problem I had with holes was that it was totally possible to strand myself on the outline of a hole when I've already sewn all the rows touching it.
It took me two separate times reading through the paper I linked to in the comments in autofill.py before I finally understood their key brilliant idea: add edges in such a way as to make the graph eulerian. It's a powerful concept.
And yet, it's the panacea you're suggesting it might be. Yes, making a graph eulerian ensures that a solution exists, but finding it is another thing entirely. The big stumbling block is the step of Hierholzer's algorithm, "find a loop starting and ending at some point along the existing path". Searching for that loop can be difficult.
There are five heuristics used in autofill.py, and four of them are designed to try to ensure that the breadth-first search doesn't end up blowing up and searching way too far. Without them the algorithm wanders around forever and never finds a loop in any kind of reasonable time.
That's what I meant when I said this:
The question in my mind is, if we start making more complex fill patterns (especially ones where rows intersect each other or intersect the outlines in weird ways), do my heuristics begin to fail?
In any case, as you can see from the algorithm, the simple type of pattern fill I mentioned in the original post above, where you just line up needle penetrations in each horizontal row, will definitely work. The autofill algorithm itself won't change, just
BTW, I also have in mind a way to use the eulerian graph approach to solve #214.
Some of you might find the following amusing, an environment to teach programming, i.e. turtle geometry designs that can be stitched. Quite a few examples program fills with turtle geometry. The environment is built on top of Snap!, a slightly more ambitious language forked from Scratch, the popular visual programming language for kids.
E.g. see the leaves done with a function, aka block (click on Variables, then petal)
I did test the software and it does work. DST output misses color change as far as my Brother machine is concerned and I had to add a needle number with another program. Otherwise, an example I made during a meeting stitched just fine. It can export to SVG, i.e. import to InkStitch also.