Saturday, November 26, 2011

Simulated Knitting

Alternate title: I'm a big fan of the Fruchterman & Reingold graph embedding algorithm.

Recently I created a site for trying to predict the pattern of colors in pooled knitting.

Next I wanted to be able to predict the shape of a knitted object. I'll explain more in a minute, but first here are some examples (click on the images for a gif movie):

A hat:

Some flat knitting (doesn't look flat to you? I'll explain in a minute):

So, what's going on here? I've done two things:
1.  Construct an abstract graph corresponding to something someone might knit
2. Embed that graph in 3D (determine where each of the points of the graph should go)
The tricky part is (2), although, as you'll see, I didn't do any of the work on that myself. I was thinking that I should approach the embedding by simulating each vertex as acted on by two forces:
• Attractive:  Applies to each pair of vertices connected by an edge, tries to pull them close to each other like a spring.
• Repulsive: Applies to each pair of vertices (regardless of whether they are connected by an edge), pushes them apart. Primarily a close-range force, infinitely strong in the limit as the points get very close together.
As it turns out, this is a very popular algorithm from Fruchterman & Reingold for graph embeddings (already implemented in iGraph). The classic paper is all about embeddings in 2D, but there's no reason not to do this in 3D. In their algorithm, the attractive force increases as distance^2 (unlike springs), and the repulsive force increases as (1/distance).

So, I just have to construct graphs that correspond to things you might knit. To illustrate the idea, here's a very simple example:

And the code (after I wrote the appropriate methods) to generate it:

g = KnittedGraph()  #Create new "KnittedGraph" object
g.NewRow()          #Create a new row
g.FinishRow()       #Finish the new row


This creates the graph, adds five stitches, starts a new row, and then finishes that row. The "flat knitting" above was created just like this: "cast on" 50 stitches, and then knit 20 rows back and forth. Why didn't it lie flat, though? The real answer: Forcing it to lie flat isn't what would make sense! The real knitting (just like a real "flat") piece of paper has the option to bend in one direction at a time. The algorithm has a certain distance apart that it wants each pair of linked vertices to be, and the object doesn't have to lie flat to achieve that.

Extending this a little, I can add an "increase" (two stitches connected to the same stitch in the previous row):

g = KnittedGraph()  #Create new "KnittedGraph" object
g.NewRow()          #Create a new row
g.FinishRow()       #Finish the new row
g.NewRow()
g.Increase()        #Add an "increase" (one stitch connected to two in the previous row)


We can also knit "in the round" by knitting a row and then connecting the current stitch to the first stitch:

g = KnittedGraph()
g.ConnectToZero() #Connect the current stitch to the original stitch


Here's an example of the same thing (but larger -- 20 circular rows of 50 stitches each) embedded in 3d:

As a final example, let's try to make something with constant negative curvature (a pseudo-sphere).  Geeky knitters often do this for fun by knitting in a circle (as above) and increasing the number of stitches at a constant rate:

The way I like to think about this mathematically, negative curvature for a surface means that small discs of a given radius have more volume than on a flat plane (and the opposite for positive curvature). Think of squashing a saddle flat and having extra material, vs. squashing a hemisphere flat and not having enough.

And here's mine:

Here's my code on GitHub.

(Including a modified version of this code for plotting in 3D.  Thanks Michael!)

[Edit: Using Ubuntu 10.04.3 LTS & Python 2.6.5, I installed python-iGraph with:
sudo aptitude install python-igraph

Apparently that's not working in Ubuntu 11.10. See this G+ thread for more. Thanks, Shae.]

1. Very cool- can you combine the shape and the color information?

2. Yeah, I don't think that would be too hard. I'm also thinking about maybe a nice web front-end (like the color thing) for non-techie users to enter their own patterns.

3. Here is the ppa link for igraph supported by the core team, https://launchpad.net/~igraph/+archive/ppa. Just go there and follow the instructions and your igraph sadness should disappear. -- Peter G. Marshall

4. I bet Ravelry.com would love if you could build a friendly UX on top of this.

5. Work that up to take KnitML input? :)
http://www.knitml.com/blog/

6. Nice idea! I'd never heard of KnitML.

It looks like someone has done that, probably better than mine, too.

http://sourceforge.net/projects/knitter/

7. Are you assuming a certain stitch pattern like garter stitch? If it were stockinette, I would expect the edges to roll, which would be really interesting to model.

8. It's not really sophisticated enough to take that sort of thing into account. I guess for that maybe I would have to specify that certain edges in the graph like to be at certain angles with each other?

9. The hyperbolic item pictured is best done in crotchet, as the pseudo-sphere pictured appears to be. Its easy to do in crotchet as the needle is only in contact with the last stitch at any given time. If knitted, the continuous enlargening of the row being worked on would require circular needles, and would eventually get too big to fit onto any circular needle. In knitting, the stitches of a row are all in continuous contact with the needles. If using a stitch 1 add 1 formula the object would quickly become unmanageable. The wonderful Hyperbolic Coral Reef project is done in crotchet.

10. Yeah, you're right.

11. Thank you for give very good information.
Online Clothes Stores

12. This is absolutely wonderful, I saw the crochet simulator, and you have changed my life. Thank you for this beautiful creation.

13. First-time knitters and those new to the specialty regularly begin with an example like the fastener line scarf. This basic example is very essential in that is requires just the weave fasten. The final product, in any case, has an increasingly confused looking ribbed plan and is an appealing style frill that makes a perfect present for friends and family.
Knitting kits

14. This is exceptionally instructive substance and composed well for a change. It's pleasant to see that a few individuals still see how to compose a quality post!  https://mycrochetpattern.com/baby/

15. I would like to convey my admiration for your generosity in support of men and women that have the need for help with this particular concern. Your special dedication to getting the message all over had been wonderfully productive and have all the time made professionals much like me to attain their dreams. Your own invaluable tutorial means a great deal to me and additionally to my office workers. Thank you; from everyone of us. patterns

16. Explore Knitterbox's collection of free knitting & Free Crochet Patterns to inspire your next knitting project

17. Knits are a staple in every woman's wardrobe. Because they are so easy to wear and maintain, syntetgarn

18. This particular is usually apparently essential and moreover outstanding truth along with for sure fair-minded and moreover admittedly useful My business is looking to find in advance designed for this specific useful stuffs… lingarn vĂ¤vning

19. tages in the creating of knitting images. From a knitting pattern, a stitch mesh is created. redesign staging sacramento ca