Learn From Data

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.]

At November 27, 2011 at 6:49 PM ,  Anonymous said...

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

At November 27, 2011 at 6:52 PM ,  David said...

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.

At December 8, 2011 at 10:37 AM ,  Openphase said...

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

At December 8, 2011 at 11:19 AM ,  Anonymous said...

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

At December 8, 2011 at 1:55 PM ,  Eric (freiheit) said...

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

At December 8, 2011 at 2:18 PM ,  David said...

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/

At December 8, 2011 at 2:38 PM ,  Diane said...

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.

At December 8, 2011 at 8:12 PM ,  David said...

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?

At February 23, 2012 at 11:22 PM ,  Anonymous said...

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.

At February 24, 2012 at 8:36 AM ,  David said...

Yeah, you're right.