Initial import of upstream code

Embroidery output extension for Inkscape;
downloaded from http://www.jonh.net/~jonh/inkscape-embroidery/
on 2014-12-26 19:38 CET

Copyright 2010 by Jon Howell, licensed under GPLv3.

8 files changed, 1111 insertions, 0 deletions

diff --git a/PyEmb.py b/PyEmb.py
new file mode 100644
index 00000000..6f14fded
--- /dev/null
+++ b/PyEmb.py
@@ -0,0 +1,241 @@
+#!python
+#!/usr/bin/python
+# http://www.achatina.de/sewing/main/TECHNICL.HTM
+
+import math
+import sys
+dbg = sys.stderr
+
+def abs(x):
+	if (x<0): return -x
+	return x
+
+class Point:
+	def __init__(self, x, y):
+		self.x = x
+		self.y = y
+
+	def __add__(self, other):
+		return Point(self.x+other.x, self.y+other.y)
+
+	def __sub__(self, other):
+		return Point(self.x-other.x, self.y-other.y)
+
+	def mul(self, scalar):
+		return Point(self.x*scalar, self.y*scalar)
+	
+	def __repr__(self):
+		return "Pt(%s,%s)" % (self.x,self.y)
+
+	def length(self):
+		return math.sqrt(math.pow(self.x,2.0)+math.pow(self.y,2.0))
+
+	def unit(self):
+		return self.mul(1.0/self.length())
+
+	def rotate_left(self):
+		return Point(-self.y, self.x)
+
+	def as_int(self):
+		return Point(int(round(self.x)), int(round(self.y)))
+
+	def as_tuple(self):
+		return (self.x,self.y)
+
+	def __cmp__(self, other):
+		return cmp(self.as_tuple(), other.as_tuple())
+
+class Embroidery:
+	def __init__(self):
+		self.coords = []
+
+	def addStitch(self, coord):
+		self.coords.append(coord)
+
+	def translate_to_origin(self):
+		if (len(self.coords)==0):
+			return
+		(maxx,maxy) = (self.coords[0].x,self.coords[0].y)
+		(minx,miny) = (self.coords[0].x,self.coords[0].y)
+		for p in self.coords:
+			minx = min(minx,p.x)
+			miny = min(miny,p.y)
+			maxx = max(maxx,p.x)
+			maxy = max(maxy,p.y)
+		sx = maxx-minx
+		sy = maxy-miny
+		for p in self.coords:
+			p.x -= minx
+			p.y -= miny
+		dbg.write("Field size %s x %s\n" % (sx,sy))
+
+	def scale(self, sc):
+		for p in self.coords:
+			p.x *= sc
+			p.y *= sc
+			
+	def export_ksm(self, dbg):
+		str = ""
+		self.pos = Point(0,0)
+		lastColor = None
+		for stitch in self.coords:
+			if (lastColor!=None and stitch.color!=lastColor):
+				mode_byte = 0x99
+				#dbg.write("Color change!\n")
+			else:
+				mode_byte = 0x80
+				#dbg.write("color still %s\n" % stitch.color)
+			lastColor = stitch.color
+			new_int = stitch.as_int()
+			old_int = self.pos.as_int()
+			delta = new_int - old_int
+			assert(abs(delta.x)<=127)
+			assert(abs(delta.y)<=127)
+			str+=chr(abs(delta.y))
+			str+=chr(abs(delta.x))
+			if (delta.y<0):
+				mode_byte |= 0x20
+			if (delta.x<0):
+				mode_byte |= 0x40
+			str+=chr(mode_byte)
+			self.pos = stitch
+		return str
+
+	def export_melco(self, dbg):
+		self.str = ""
+		self.pos = self.coords[0]
+		dbg.write("stitch count: %d\n" % len(self.coords))
+		lastColor = None
+		numColors = 0x0
+		for stitch in self.coords[1:]:
+			if (lastColor!=None and stitch.color!=lastColor):
+				numColors += 1
+				# color change
+				self.str += chr(0x80)
+				self.str += chr(0x01)
+#				self.str += chr(numColors)
+#				self.str += chr(((numColors+0x80)>>8)&0xff)
+#				self.str += chr(((numColors+0x80)>>0)&0xff)
+			lastColor = stitch.color
+			new_int = stitch.as_int()
+			old_int = self.pos.as_int()
+			delta = new_int - old_int
+
+			def move(x,y):
+				if (x<0): x = x + 256
+				self.str+=chr(x)
+				if (y<0): y = y + 256
+				self.str+=chr(y)
+				
+			while (delta.x!=0 or delta.y!=0):
+				def clamp(v):
+					if (v>127):
+						v = 127
+					if (v<-127):
+						v = -127
+					return v
+				dx = clamp(delta.x)
+				dy = clamp(delta.y)
+				move(dx,dy)
+				delta.x -= dx
+				delta.y -= dy
+				
+			#dbg.write("Stitch: %s delta %s\n" % (stitch, delta))
+			self.pos = stitch
+		return self.str
+
+class Test:
+	def __init__(self):
+		emb = Embroidery()
+		for x in range(0,301,30):
+			emb.addStitch(Point(x, 0));
+			emb.addStitch(Point(x, 15));
+			emb.addStitch(Point(x, 0));
+
+		for x in range(300,-1,-30):
+			emb.addStitch(Point(x, -12));
+			emb.addStitch(Point(x, -27));
+			emb.addStitch(Point(x, -12));
+
+		fp = open("test.exp", "wb")
+		fp.write(emb.export_melco())
+		fp.close()
+
+class Turtle:
+	def __init__(self):
+		self.emb = Embroidery()
+		self.pos = Point(0.0,0.0)
+		self.dir = Point(1.0,0.0)
+		self.emb.addStitch(self.pos)
+
+	def forward(self, dist):
+		self.pos = self.pos+self.dir.mul(dist)
+		self.emb.addStitch(self.pos)
+
+	def turn(self, degreesccw):
+		radcw =  -degreesccw/180.0*3.141592653589
+		self.dir = Point(
+			math.cos(radcw)*self.dir.x-math.sin(radcw)*self.dir.y,
+			math.sin(radcw)*self.dir.x+math.cos(radcw)*self.dir.y)
+
+	def right(self, degreesccw):
+		self.turn(degreesccw)
+
+	def left(self, degreesccw):
+		self.turn(-degreesccw)
+	
+class Koch(Turtle):
+	def __init__(self, depth):
+		Turtle.__init__(self)
+
+		edgelen = 750.0
+		for i in range(3):
+			self.edge(depth, edgelen)
+			self.turn(120.0)
+
+		fp = open("koch%d.exp" % depth, "wb")
+		fp.write(self.emb.export_melco())
+		fp.close()
+	
+	def edge(self, depth, dist):
+		if (depth==0):
+			self.forward(dist)
+		else:
+			self.edge(depth-1, dist/3.0)
+			self.turn(-60.0)
+			self.edge(depth-1, dist/3.0)
+			self.turn(120.0)
+			self.edge(depth-1, dist/3.0)
+			self.turn(-60.0)
+			self.edge(depth-1, dist/3.0)
+
+class Hilbert(Turtle):
+	def __init__(self, level):
+		Turtle.__init__(self)
+
+		self.size = 10.0
+		self.hilbert(level, 90.0)
+
+		fp = open("hilbert%d.exp" % level, "wb")
+		fp.write(self.emb.export_melco())
+		fp.close()
+
+	# http://en.wikipedia.org/wiki/Hilbert_curve#Python
+	def hilbert(self, level, angle):
+		if (level==0):
+			return
+		self.right(angle)
+		self.hilbert(level-1, -angle)
+		self.forward(self.size)
+		self.left(angle)
+		self.hilbert(level-1, angle)
+		self.forward(self.size)
+		self.hilbert(level-1, angle)
+		self.left(angle)
+		self.forward(self.size)
+		self.hilbert(level-1, -angle)
+		self.right(angle)
+
+if (__name__=='__main__'):
+	#Koch(4)
+	Hilbert(6)
diff --git a/embroider.inx b/embroider.inx
new file mode 100644
index 00000000..25ea423d
--- /dev/null
+++ b/embroider.inx
@@ -0,0 +1,19 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<inkscape-extension xmlns="http://www.inkscape.org/namespace/inkscape/extension">
+    <_name>Embroider</_name>
+    <id>jonh.embroider</id>
+    <dependency type="executable" location="extensions">embroider.py</dependency>
+    <dependency type="executable" location="extensions">inkex.py</dependency>
+    <param name="row_spacing_mm"       type="float"   min="0.01" max="5.00" _gui-text="Row spacing (mm)">0.40</param>
+    <param name="max_stitch_len_mm"       type="float"   min="0.1" max="10.0" _gui-text="Maximum stitch length (mm)">3.0</param>
+    <param name="preserve_order"       type="boolean"   _gui-text="Preserve stacking order" description="if false, sorts by color, which saves thread changes. True preserves stacking order, important if you're laying colors over each other.">false</param>
+    <effect>
+        <object-type>all</object-type>
+                <effects-menu>
+                    <submenu _name="Render"/>
+                </effects-menu>
+    </effect>
+    <script>
+        <command reldir="extensions" interpreter="python">embroider.py</command>
+    </script>
+</inkscape-extension>
diff --git a/embroider.py b/embroider.py
new file mode 100644
index 00000000..c9c30039
--- /dev/null
+++ b/embroider.py
@@ -0,0 +1,691 @@
+#!/usr/bin/python
+#
+# documentation: see included index.html
+# LICENSE:
+# This code is copyright 2010 by Jon Howell,
+# licensed under <a href="http://www.gnu.org/licenses/quick-guide-gplv3.html">GPLv3</a>.
+#
+# Important resources:
+# lxml interface for walking SVG tree:
+# http://codespeak.net/lxml/tutorial.html#elementpath
+# Inkscape library for extracting paths from SVG:
+# http://wiki.inkscape.org/wiki/index.php/Python_modules_for_extensions#simplepath.py
+# Shapely computational geometry library:
+# http://gispython.org/shapely/manual.html#multipolygons
+# Embroidery file format documentation:
+# http://www.achatina.de/sewing/main/TECHNICL.HTM
+# 
+
+import sys
+sys.path.append("/usr/share/inkscape/extensions")
+import os
+from copy import deepcopy
+import time
+import inkex
+import simplepath
+import simplestyle
+import cspsubdiv
+import cubicsuperpath
+import PyEmb
+import math
+import random
+import operator
+import lxml.etree as etree
+from lxml.builder import E
+import shapely.geometry as shgeo
+
+dbg = open("embroider-debug.txt", "w")
+PyEmb.dbg = dbg
+pixels_per_millimeter = 90.0 / 25.4
+
+def bboxarea(poly):
+	x0=None
+	x1=None
+	y0=None
+	y1=None
+	for pt in poly:
+		if (x0==None or pt[0]<x0): x0 = pt[0]
+		if (x1==None or pt[0]>x1): x1 = pt[0]
+		if (y0==None or pt[1]<y0): y0 = pt[1]
+		if (y1==None or pt[1]>y1): y1 = pt[1]
+	return (x1-x0)*(y1-y0)
+
+def area(poly):
+	return bboxarea(poly)
+
+def byarea(a,b):
+	return -cmp(area(a), area(b))
+
+def cspToShapelyPolygon(path):
+	poly_ary = []
+	for sub_path in path:
+		point_ary = []
+		last_pt = None
+		for csp in sub_path:
+			pt = (csp[1][0],csp[1][1])
+			if (last_pt!=None):
+				vp = (pt[0]-last_pt[0],pt[1]-last_pt[1])
+				dp = math.sqrt(math.pow(vp[0],2.0)+math.pow(vp[1],2.0))
+				#dbg.write("dp %s\n" % dp)
+				if (dp > 0.01):
+					# I think too-close points confuse shapely.
+					point_ary.append(pt)
+					last_pt = pt
+			else:
+				last_pt = pt
+		poly_ary.append(point_ary)
+	# shapely's idea of "holes" are to subtract everything in the second set
+	# from the first. So let's at least make sure the "first" thing is the
+	# biggest path.
+	poly_ary.sort(byarea)
+
+	polygon = shgeo.MultiPolygon([(poly_ary[0], poly_ary[1:])])
+	return polygon
+
+def shapelyCoordsToSvgD(geo):
+	coords = list(geo.coords)
+	new_path = []
+	new_path.append(['M', coords[0]])
+	for c in coords[1:]:
+		new_path.append(['L', c])
+	return simplepath.formatPath(new_path)
+
+def shapelyLineSegmentToPyTuple(shline):
+	tuple = ((shline.coords[0][0],shline.coords[0][1]),
+			(shline.coords[1][0],shline.coords[1][1]))
+	return tuple
+
+def dupNodeAttrs(node):
+	n2 = E.node()
+	for k in node.attrib.keys():
+		n2.attrib[k] = node.attrib[k]
+	del n2.attrib["id"]
+	del n2.attrib["d"]
+	return n2
+
+class Patch:
+	def __init__(self, color, sortorder, stitches=None):
+		self.color = color
+		self.sortorder = sortorder
+		if (stitches!=None):
+			self.stitches = stitches
+		else:
+			self.stitches = []
+
+	def addStitch(self, stitch):
+		self.stitches.append(stitch)
+
+	def reverse(self):
+		return Patch(self.color, self.sortorder, self.stitches[::-1])
+
+class DebugHole:
+	pass
+
+class PatchList:
+	def __init__(self, patches):
+		self.patches = patches
+
+	def sort_by_sortorder(self):
+		def by_sort_order(a,b):
+			return cmp(a.sortorder, b.sortorder)
+		self.patches.sort(by_sort_order)
+
+	def partition_by_color(self):
+		self.sort_by_sortorder()
+		dbg.write("Sorted by sortorder:\n");
+		dbg.write("  %s\n" % ("\n".join(map(lambda p: str(p.sortorder), self.patches))))
+		out = []
+		lastPatch = None
+		for patch in self.patches:
+			if (lastPatch!=None and patch.color==lastPatch.color):
+				out[-1].patches.append(patch)
+			else:
+				out.append(PatchList([patch]))
+			lastPatch = patch
+		dbg.write("Emitted %s partitions\n" % len(out))
+		return out
+		
+	def tsp_by_color(self):
+		list_of_patchLists = self.partition_by_color()
+		for patchList in list_of_patchLists:
+			patchList.traveling_salesman()
+		return PatchList(reduce(operator.add,
+			map(lambda pl: pl.patches, list_of_patchLists)))
+
+#	# TODO apparently dead code; replaced by partition_by_color above
+#	def clump_like_colors_together(self):
+#		out = PatchList([])
+#		lastPatch = None
+#		for patch in self.patches:
+#			if (lastPatch!=None and patch.color==lastPatch.color):
+#				out.patches[-1] = Patch(
+#					out.patches[-1].color,
+#					out.patches[-1].sortorder,
+#					out.patches[-1].stitches+patch.stitches)
+#			else:
+#				out.patches.append(patch)
+#			lastPatch = patch
+#		return out
+
+	def get(self, i):
+		if (i<0 or i>=len(self.patches)):
+			return None
+		return self.patches[i]
+
+	def cost(self, a, b):
+		if (a==None or b==None):
+			rc = 0.0
+		else:
+			rc = (a.stitches[-1] - b.stitches[0]).length()
+		#dbg.write("cost(%s, %s) = %5.1f\n" % (a, b, rc))
+		return rc
+
+	def try_swap(self, i, j):
+		# i,j are indices;
+		dbg.write("swap(%d, %d)\n" % (i,j))
+		oldCost = (
+			 self.cost(self.get(i-1), self.get(i))
+			+self.cost(self.get(i), self.get(i+1))
+			+self.cost(self.get(j-1), self.get(j))
+			+self.cost(self.get(j), self.get(j+1)))
+		npi = self.get(j)
+		npj = self.get(i)
+		rpi = npi.reverse()
+		rpj = npj.reverse()
+		options = [
+			(npi,npj),
+			(rpi,npj),
+			(npi,rpj),
+			(rpi,rpj),
+		]
+		def costOf(np):
+			(npi,npj) = np
+			return (
+				 self.cost(self.get(i-1), npi)
+				+self.cost(npi, self.get(i+1))
+				+self.cost(self.get(j-1), npj)
+				+self.cost(npj, self.get(j+1)))
+		costs = map(lambda o: (costOf(o), o), options)
+		costs.sort()
+		(cost,option) = costs[0]
+		savings = oldCost - cost
+		if (savings > 0):
+			self.patches[i] = option[0]
+			self.patches[j] = option[1]
+			success = "!"
+		else:
+			success = "."
+
+		dbg.write("old %5.1f new %5.1f savings: %5.1f\n" % (oldCost, cost, savings))
+		return success
+
+	def try_reverse(self, i):
+		dbg.write("reverse(%d)\n" % i)
+		oldCost = (self.cost(self.get(i-1), self.get(i))
+			+self.cost(self.get(i), self.get(i+1)))
+		reversed = self.get(i).reverse()
+		newCost = (self.cost(self.get(i-1), reversed)
+			+self.cost(reversed, self.get(i+1)))
+		savings = oldCost - newCost
+		if (savings > 0.0):
+			self.patches[i] = reversed
+			success = "#"
+		else:
+			success = "_"
+		return success
+
+	def traveling_salesman(self):
+		# shockingly, this is non-optimal and pretty much non-efficient. Sorry.
+		self.centroid = PyEmb.Point(0.0,0.0)
+		self.pointList = []
+		for patch in self.patches:
+			def visit(idx):
+				ep = deepcopy(patch.stitches[idx])
+				ep.patch = patch
+				self.centroid+=ep
+				self.pointList.append(ep)
+
+			visit(0)
+			visit(-1)
+
+		self.centroid = self.centroid.mul(1.0/float(len(self.pointList)))
+
+		def linear_min(list, func):
+			min_item = None
+			min_value = None
+			for item in list:
+				value = func(item)
+				#dbg.write('linear_min %s: value %s => %s (%s)\n' % (func, item, value, value<min_value))
+				if (min_value==None or value<min_value):
+					min_item = item
+					min_value = value
+			#dbg.write('linear_min final item %s value %s\n' % (min_item, min_value))
+			return min_item
+
+		sortedPatchList = PatchList([])
+		def takePatchStartingAtPoint(point):
+			patch = point.patch
+			dbg.write("takePatchStartingAtPoint angling for patch %s--%s\n" % (
+				patch.stitches[0],
+				patch.stitches[-1]))
+			self.pointList = filter(lambda pt: pt.patch!=patch, self.pointList)
+			reversed = ""
+			if (point!=patch.stitches[0]):
+				reversed = " (reversed)"
+				dbg.write('patch.stitches[0] %s point %s match %s\n' % (
+					patch.stitches[0],
+					point,
+					point==patch.stitches[0]))
+				patch = patch.reverse()
+			sortedPatchList.patches.append(patch)
+			dbg.write('took patch %s--%s %s\n' % (
+				patch.stitches[0],
+				patch.stitches[-1],
+				reversed))
+
+		# Take the patch farthest from the centroid first
+		# O(n)
+		dbg.write('centroid: %s\n' % self.centroid)
+		def neg_distance_from_centroid(p):
+			return -(p-self.centroid).length()
+		farthestPoint = linear_min(self.pointList, neg_distance_from_centroid)
+		takePatchStartingAtPoint(farthestPoint)
+		#sortedPatchList.patches[0].color = "#000000"
+
+		# Then greedily take closer-and-closer patches
+		# O(n^2)
+		while (len(self.pointList)>0):
+			dbg.write('pass %s\n' % len(self.pointList));
+			last_point = sortedPatchList.patches[-1].stitches[-1]
+			dbg.write('last_point now %s\n' % last_point)
+			def distance_from_last_point(p):
+				return (p-last_point).length()
+			nearestPoint = linear_min(self.pointList, distance_from_last_point)
+			takePatchStartingAtPoint(nearestPoint)
+
+		# install the initial result
+		self.patches = sortedPatchList.patches
+
+		if (1):
+			# Then hill-climb.
+			dbg.write("len(self.patches) = %d\n" % len(self.patches))
+			count = 0
+			successStr = ""
+			while (count < 100):
+				i = random.randint(0, len(self.patches)-1)
+				j = random.randint(0, len(self.patches)-1)
+				successStr += self.try_swap(i,j)
+
+				count += 1
+			# tidy up at end as best we can
+			for i in range(len(self.patches)):
+				successStr += self.try_reverse(i)
+
+			dbg.write("success: %s\n" % successStr)
+
+class EmbroideryObject:
+	def __init__(self, patchList, row_spacing_px):
+		self.patchList = patchList
+		self.row_spacing_px = row_spacing_px
+
+	def emit_melco(self):
+		emb = PyEmb.Embroidery()
+		for patch in self.patchList.patches:
+			for stitch in patch.stitches:
+				newStitch = PyEmb.Point(stitch.x, -stitch.y)
+				dbg.write("melco stitch color %s\n" % patch.color)
+				newStitch.color = patch.color
+				emb.addStitch(newStitch)
+		emb.translate_to_origin()
+		emb.scale(10.0/pixels_per_millimeter)
+		fp = open("embroider-output.exp", "wb")
+		#fp = open("output.ksm", "wb")
+		fp.write(emb.export_melco(dbg))
+		fp.close()
+
+	def emit_inkscape(self, parent):
+		lastPatch = None
+		for patch in self.patchList.patches:
+			if (lastPatch!=None):
+				# draw jump stitch
+				inkex.etree.SubElement(parent,
+					inkex.addNS('path', 'svg'),
+					{	'style':simplestyle.formatStyle(
+							{ 'stroke': lastPatch.color,
+								'stroke-width':str(self.row_spacing_px*0.25),
+								'stroke-dasharray':'0.99, 1.98',
+								'fill': 'none' }),
+						'd':simplepath.formatPath([
+							['M', (lastPatch.stitches[-1].as_tuple())],
+							['L', (patch.stitches[0].as_tuple())]
+						]),
+					})
+			lastPatch = patch
+				
+			new_path = []
+			new_path.append(['M', patch.stitches[0].as_tuple()])
+			for stitch in patch.stitches[1:]:
+				new_path.append(['L', stitch.as_tuple()])
+			inkex.etree.SubElement(parent,
+				inkex.addNS('path', 'svg'),
+				{	'style':simplestyle.formatStyle(
+						{ 'stroke': patch.color,
+							'stroke-width':str(self.row_spacing_px*0.25),
+							'fill': 'none' }),
+					'd':simplepath.formatPath(new_path),
+				})
+
+	def bbox(self):
+		x = []
+		y = []
+		for patch in self.patchList.patches:
+			for stitch in patch.stitches:
+				x.append(stitch.x)
+				y.append(stitch.y)
+		return (min(x), min(y), max(x), max(y))
+
+class SortOrder:
+	def __init__(self, threadcolor, stacking_order, preserve_order):
+		self.threadcolor = threadcolor
+		if (preserve_order):
+			dbg.write("preserve_order is true:\n");
+			self.sorttuple = (stacking_order, threadcolor)
+		else:
+			dbg.write("preserve_order is false:\n");
+			self.sorttuple = (threadcolor, stacking_order)
+
+	def __cmp__(self, other):
+		return cmp(self.sorttuple, other.sorttuple)
+	
+	def __repr__(self):
+		return "sort %s color %s" % (self.sorttuple, self.threadcolor)
+
+class Embroider(inkex.Effect):
+	def __init__(self, *args, **kwargs):
+		dbg.write("args: %s\n" % repr(sys.argv))
+		inkex.Effect.__init__(self)
+		self.stacking_order_counter = 0
+		self.OptionParser.add_option("-r", "--row_spacing_mm",
+			action="store", type="float",
+			dest="row_spacing_mm", default=0.4,
+			help="row spacing (mm)")
+		self.OptionParser.add_option("-l", "--max_stitch_len_mm",
+			action="store", type="float",
+			dest="max_stitch_len_mm", default=3.0,
+			help="max stitch length (mm)")
+		self.OptionParser.add_option("-f", "--flatness",
+			action="store", type="float", 
+			dest="flat", default=0.1,
+			help="Minimum flatness of the subdivided curves")
+		self.OptionParser.add_option("-o", "--preserve_order",
+			action="store", type="choice", 
+			choices=["true","false"],
+			dest="preserve_order", default="false",
+			help="Sort by stacking order instead of color")
+		self.patches = []
+
+	def get_sort_order(self, threadcolor):
+		self.stacking_order_counter += 1
+		return SortOrder(threadcolor, self.stacking_order_counter, self.options.preserve_order=="true")
+
+	def process_one_path(self, shpath, threadcolor, sortorder):
+		#self.add_shapely_geo_to_svg(shpath.boundary, color="#c0c000")
+
+		rows_of_segments = self.intersect_region_with_grating(shpath)
+		segments = self.visit_segments_one_by_one(rows_of_segments)
+
+		def small_stitches(patch, beg, end):
+			old_dist = None
+			while (True):
+				vector = (end-beg)
+				dist = vector.length()
+				assert(old_dist==None or dist<old_dist)
+				old_dist = dist
+				patch.addStitch(beg)
+				if (dist < self.max_stitch_len_px):
+					patch.addStitch(end)
+					return
+
+				one_stitch = vector.mul(1.0/dist*self.max_stitch_len_px)
+				beg = beg + one_stitch
+				
+		swap = False
+		patches = []
+		for (beg,end) in segments:
+			patch = Patch(color=threadcolor,sortorder=sortorder)
+			if (swap):
+				(beg,end)=(end,beg)
+			swap = not swap
+			small_stitches(patch, PyEmb.Point(*beg),PyEmb.Point(*end))
+			patches.append(patch)
+		return patches
+
+	def intersect_region_with_grating(self, shpath):
+		dbg.write("bounds = %s\n" % str(shpath.bounds))
+		bbox = shpath.bounds
+		
+		delta = self.row_spacing_px/2.0
+		bbox_sz = (bbox[2]-bbox[0],bbox[3]-bbox[1])
+		if (bbox_sz[0] > bbox_sz[1]):
+			# wide box, use vertical stripes
+			p0 = PyEmb.Point(bbox[0]-delta,bbox[1])
+			p1 = PyEmb.Point(bbox[0]-delta,bbox[3])
+			p_inc = PyEmb.Point(self.row_spacing_px, 0)
+			count = (bbox[2]-bbox[0])/self.row_spacing_px + 2
+		else:
+			# narrow box, use horizontal stripes
+			p0 = PyEmb.Point(bbox[0], bbox[1]-delta)
+			p1 = PyEmb.Point(bbox[2], bbox[1]-delta)
+			p_inc = PyEmb.Point(0, self.row_spacing_px)
+			count = (bbox[3]-bbox[1])/self.row_spacing_px + 2
+
+		rows = []
+		steps = 0
+		while (steps < count):
+			try:
+				steps += 1
+				p0 += p_inc
+				p1 += p_inc
+				endpoints = [p0.as_tuple(), p1.as_tuple()]
+				shline = shgeo.LineString(endpoints)
+				res = shline.intersection(shpath)
+				if (isinstance(res, shgeo.MultiLineString)):
+					runs = map(shapelyLineSegmentToPyTuple, res.geoms)
+				else:
+					runs = [shapelyLineSegmentToPyTuple(res)]
+				rows.append(runs)
+			except Exception, ex:
+				dbg.write("--------------\n")
+				dbg.write("%s\n" % ex)
+				dbg.write("%s\n" % shline)
+				dbg.write("%s\n" % shpath)
+				dbg.write("==============\n")
+				continue
+		return rows
+		
+	def visit_segments_one_by_one(self, rows):
+		def pull_runs(rows):
+			new_rows = []
+			run = []
+			for r in rows:
+				(first,rest) = (r[0], r[1:])
+				run.append(first)
+				if (len(rest)>0):
+					new_rows.append(rest)
+			return (run, new_rows)
+
+		linearized_runs = []
+		count = 0
+		while (len(rows) > 0):
+			(one_run,rows) = pull_runs(rows)
+			linearized_runs.extend(one_run)
+
+			rows = rows[::-1]
+			count += 1
+			if (count>100): raise "kablooey"
+		return linearized_runs
+
+	def handle_node(self, node):
+
+		if (node.tag != self.svgpath):
+			dbg.write("%s\n"%str((id, etree.tostring(node, pretty_print=True))))
+			dbg.write("not a path; recursing:\n")
+			for child in node.iter(self.svgpath):
+				self.handle_node(child)
+			return
+
+		dbg.write("Node: %s\n"%str((id, etree.tostring(node, pretty_print=True))))
+
+		israw = False
+		desc = node.findtext(inkex.addNS('desc', 'svg'))
+		if (desc!=None):
+			israw = desc.find("embroider_raw")>=0
+		if (israw):
+			self.patchList.patches.extend(self.path_to_patch_list(node))
+		else:
+			if (self.get_style(node, "fill")!=None):
+				self.patchList.patches.extend(self.filled_region_to_patchlist(node))
+			if (self.get_style(node, "stroke")!=None):
+				self.patchList.patches.extend(self.path_to_patch_list(node))
+
+	def get_style(self, node, style_name):
+		style = simplestyle.parseStyle(node.get("style"))
+		if (style_name not in style):
+			return None
+		value = style[style_name]
+		if (value==None or value=="none"):
+			return None
+		return value
+		
+	def effect(self):
+		self.row_spacing_px = self.options.row_spacing_mm * pixels_per_millimeter
+		self.max_stitch_len_px = self.options.max_stitch_len_mm*pixels_per_millimeter 
+
+		self.svgpath = inkex.addNS('path', 'svg')
+		self.patchList = PatchList([])
+		for id, node in self.selected.iteritems():
+			self.handle_node(node)
+
+		self.patchList = self.patchList.tsp_by_color()
+		dbg.write("patch count: %d\n" % len(self.patchList.patches))
+
+		eo = EmbroideryObject(self.patchList, self.row_spacing_px)
+
+		eo.emit_melco()
+
+		new_group = inkex.etree.SubElement(self.current_layer,
+				inkex.addNS('g', 'svg'), {})
+		eo.emit_inkscape(new_group)
+
+		self.emit_inkscape_bbox(new_group, eo)
+
+	def emit_inkscape_bbox(self, parent, eo):
+		(x0, y0, x1, y1) = eo.bbox()
+		new_path = []
+		new_path.append(['M', (x0,y0)])
+		new_path.append(['L', (x1,y0)])
+		new_path.append(['L', (x1,y1)])
+		new_path.append(['L', (x0,y1)])
+		new_path.append(['L', (x0,y0)])
+		inkex.etree.SubElement(parent,
+			inkex.addNS('path', 'svg'),
+			{	'style':simplestyle.formatStyle(
+					{ 'stroke': '#ff00ff',
+						'stroke-width':str(1),
+						'fill': 'none' }),
+				'd':simplepath.formatPath(new_path),
+			})
+
+	def path_to_patch_list(self, node):
+		threadcolor = simplestyle.parseStyle(node.get("style"))["stroke"]
+		stroke_width_str = simplestyle.parseStyle(node.get("style"))["stroke-width"]
+		if (stroke_width_str.endswith("px")):
+			# don't really know how we should be doing unit conversions.
+			# but let's hope px are kind of like pts?
+			stroke_width_str = stroke_width_str[:-2]
+		stroke_width = float(stroke_width_str)
+		dbg.write("stroke_width is <%s>\n" % repr(stroke_width))
+		dbg.flush()
+		sortorder = self.get_sort_order(threadcolor)
+		path = simplepath.parsePath(node.get("d"))
+
+		# regularize the points lists.
+		# (If we're parsing beziers, there will be a list of multi-point
+		# subarrays.)
+
+		emb_point_list = []
+		for (type,points) in path:
+			dbg.write("path_to_patch_list parses pt %s\n" % points)
+			pointscopy = list(points)
+			while (len(pointscopy)>0):
+				emb_point_list.append(PyEmb.Point(pointscopy[0], pointscopy[1]))
+				pointscopy = pointscopy[2:]
+
+		STROKE_MIN = 0.5	# a 0.5pt stroke becomes a straight line.
+		if (stroke_width <= STROKE_MIN):
+			dbg.write("self.max_stitch_len_px = %s\n" % self.max_stitch_len_px)
+			patch = self.stroke_points(emb_point_list, self.max_stitch_len_px, 0.0, threadcolor, sortorder)
+		else:
+			patch = self.stroke_points(emb_point_list, self.row_spacing_px*0.5, stroke_width, threadcolor, sortorder)
+		return patch
+
+	def stroke_points(self, emb_point_list, row_spacing_px, stroke_width, threadcolor, sortorder):
+		patch = Patch(color=threadcolor, sortorder=sortorder)
+		p0 = emb_point_list[0]
+		for segi in range(1, len(emb_point_list)):
+			p1 = emb_point_list[segi]
+
+			# how far we have to go along segment
+			seg_len = (p1 - p0).length()
+			if (seg_len < row_spacing_px*0.5):
+				# hmm. segment so short we can't do much sane with
+				# it. Ignore the point p1 and move along (but keep p0
+				# as the beginning).
+				continue;
+
+			# vector pointing along segment
+			along = (p1 - p0).unit()
+			# vector pointing to edge of stroke width
+			perp = along.rotate_left().mul(stroke_width*0.5)
+
+			# iteration variable: how far we are along segment
+			rho = 0.0
+			while (rho <= seg_len):
+				left_pt = p0+along.mul(rho)+perp
+				patch.addStitch(left_pt)
+				rho += row_spacing_px
+				if (rho > seg_len):
+					break
+
+				right_pt = p0+along.mul(rho)+perp.mul(-1.0)
+				patch.addStitch(right_pt)
+				rho += row_spacing_px
+
+			# make sure we turn sharp corners when stroking thin paths.
+			patch.addStitch(p1)
+
+			p0 = p1
+
+		return [patch]
+
+	def filled_region_to_patchlist(self, node):
+		p = cubicsuperpath.parsePath(node.get("d"))
+		cspsubdiv.cspsubdiv(p, self.options.flat)
+		shapelyPolygon = cspToShapelyPolygon(p)
+		threadcolor = simplestyle.parseStyle(node.get("style"))["fill"]
+		sortorder = self.get_sort_order(threadcolor)
+		return self.process_one_path(
+				shapelyPolygon,
+				threadcolor,
+				sortorder)
+
+	#TODO def make_stroked_patch(self, node):
+
+if __name__ == '__main__':
+	sys.setrecursionlimit(100000);
+	e = Embroider()
+	e.affect()
+	dbg.write("aaaand, I'm done. seeeya!\n")
+	dbg.flush()
+
+dbg.close()
diff --git a/images/draft1.jpg b/images/draft1.jpg
new file mode 100644
index 00000000..5127ce35
--- /dev/null
+++ b/images/draft1.jpg
diff --git a/images/draft2.jpg b/images/draft2.jpg
new file mode 100644
index 00000000..e053d11f
--- /dev/null
+++ b/images/draft2.jpg
diff --git a/images/shirt.jpg b/images/shirt.jpg
new file mode 100644
index 00000000..da5d635e
--- /dev/null
+++ b/images/shirt.jpg
diff --git a/index.html b/index.html
new file mode 100644
index 00000000..c1a2f377
--- /dev/null
+++ b/index.html
@@ -0,0 +1,157 @@
+<title>Embroidery output extension for Inkscape</title>
+<h1>Embroidery output extension for Inkscape</h1>
+
+Inkscape is a natural tool for designing embroidery patterns;
+the only challenge is converting the Inkscape design to a stitch file.
+Here's a rough cut as such a tool that got me through my first project;
+it may work for you, or maybe you can fix a bug or two and make it
+more robust for your application.
+
+<center>
+<br><img src="images/draft1.jpg">
+<br>My very first outputs. Scale is wrong, stitch spacing is wrong.
+<br><img src="images/draft2.jpg">
+<br>A better version. Mostly correct, but still shows poor spacing.
+Jump stitches all over the place because
+the first TSP implementation was very broken.
+<br><img src="images/shirt.jpg">
+<br>And now it's working well enough to embroider this shirt!
+<p>
+The most difficult part was carefully lining up the sequential panels
+to make the design appear continuous. One tip: baste the working piece down
+to a big piece of stabilizer, so that they stay together as the hoop is
+repositioned.
+</center>
+
+<h3>Installation.</h3>
+
+<br><a href="embroider.tgz">Download the distribution from here.</a>
+<br>Install <a href="http://trac.gispython.org/lab/wiki/Shapely">shapely</a>, Python bindings to the GEOS library.
+<pre>apt-get install python-shapely</pre>
+<br>Place or link embroider.{inx,py} into ${HOME}/.config/inkscape/extensions.
+
+<h3>Usage.</h3>
+
+Create a drawing in Inkscape made of filled regions.
+Select the regions you want to export as a stitch file.
+Ungroup repeatedly until there are no groups left,
+and convert objects to paths.
+(Embroider doesn't know how to handle text or rectangle objects;
+they must be converted down to paths before it can work with them.
+I don't know how to call "back into" Inkscape to do this automatically.)
+Select the Embroider filter.
+<p>
+If it works (and it very well might!), you'll get a new grouped object
+showing the proposed stitching path. It may be easy to miss, since the
+new strokes appear in the same color as the underlying fill. (If you
+forgot the "ungroup" step, it may also appear at a random place on
+your canvas; see BUGS below.)
+<p>
+As a side effect, Embroider also creates a file in Inkscape's current
+directory called embroider-output.exp.
+If you like the stitch pattern you see, then open that output file
+in a converter program and save it to the appropriate format for
+your machine.
+(I use Wilcom's TrueSizer, available as free-as-in-beerware,
+inside WINE to convert my output to Brother .PES format.)
+
+
+
+<h3>Theory of operation.</h3>
+
+For each input path,
+if the path is closed & filled,
+we fill it with rows of stitches.
+That's done by finding the path's bounding box,
+deciding whether to use horizontal or vertical rows based on the long
+axis of the region,
+drawing a bunch of equally-spaced line segments across the bounding box,
+and finding the intersection of the row lines with the path region.
+(We import shapely to do the intersection computation.)
+<p>
+Each path generates a "patch" of stitching.
+We sort all the patches by color, to minimize thread changes.
+Then we use a Traveling Salesman Problem implementation
+(a cheesy, greedy one, plus a little hill-climbing at the end)
+to sort the patches to minimize the length of the jump stitches
+(the unintended stitches between patches).
+
+<h3>updates</h3>
+
+2012.10.19  Implemented stroke stitches. Strokes &lt;= 0.5pt are rendered
+as straight lines, following the Inkscape path, obeying the max_stitch_len
+parameter.
+Strokes wider than 0.5pt are drawn with a zig-zag stitch. It's a bit
+ugly around corners and sharp curves, leaving gaps at the outside edge,
+but come on, I wrote it in like 45 minutes. [An ideal algorithm would
+compute the boundary of the stroke correctly, and then come up with a nice
+way to fill it with the zig-zag. This one isn't ideal.]
+
+<p>You can use strokes to do applique embroidery. Draw a (not-too-complicated)
+closed curve. Generate it both as a 0.5pt line and again with a wider stroke
+width, like 3mm. Stack two fabrics in the hoop, and embroider the thin path.
+Remove the hoop from the machine (but leave the fabrics in the hoop).
+Carefully trim away the top fabric at the stitched boundary. Then replace
+the hoop and embroider the wide path. The wider path will cover the first
+stitch line and secure the applique'd piece.
+
+<p>
+<b>Tips on strokes</b>: use Extensions -&gt; Modify Path -&gt; Flatten Beziers
+to change curves down to linear approximations. (The Embroider
+extension's supposed to do this, but it's not so good at it.)
+
+<p>
+<a href="embroider-howto/">
+<img src="embroider-howto/traced-exploded.png" width=200><br>
+More tips on using Inkscape to get from a raster example to an embroidery file.
+</a>
+
+
+<h3>TODOs.</h3>
+<p>
+TODO: when a single patch is split into multiple sections (because
+of concavities), two problems occur:
+<p>
+First, the sections are treated
+as one big patch with an implicit jump. It would be better to make
+them separate patches so that TSP can do a better job planning to
+minimize jumps.
+<p>
+Second, the algorithm "assumes" that all the stitches
+in the left "column" are part of the same patch, so it will also incur
+horizontal implied jump stitches because it doesn't realize that the
+rows are from disjoint parts of the underlying region. A smarter algorithm
+would break each time the number-of-segments changes, and start a new
+patch each time, again relying on TSP to put them back together in a
+sane order.
+<p>
+TODO: when a row is longer than the max stitch length, use a global-phase
+("tajima") stitch, rather than phase relative to where the row starts,
+to avoid troughs in the middle of the filled region.
+<p>
+TODO: remove small stitches. TrueSizer uses a 0.5mm threshhold.
+<p>
+TODO: implement melco jump-stitch, so jumps don't put holes in the fabric.
+<p>
+done: sort compound paths biggest-area first, to at least get holes right.
+<p>
+BUGS: shapely thinks all compound paths are holes; it doesn't understand
+the even-odd rule.
+<p>
+BUGS: Can't handle the "transform=" property that inkscape loves to
+glue onto &lt;g&gt;roups. To work around this, ungroup all the way down to
+separate &lt;path&gt;s, # which applies all the transforms down to the path
+point level, then regroup as desired.
+<p>
+TODO: Call into Inkscape to do this behind the scenes.
+<p>
+TODO: Call into Inkscape to convert objects to paths automatically.
+
+<h3>LICENSE</h3>
+This code is copyright 2010 by Jon Howell,
+licensed under <a href="http://www.gnu.org/licenses/quick-guide-gplv3.html">GPLv3</a>.
+
+<h3>AUTHOR</h3>
+Written by Jon Howell, <a href="mailto:jonh@jonh.net">jonh@jonh.net</a>.
+If you email me, expect an initial bounce with instructions to pass the
+spam filter.
diff --git a/makefile b/makefile
new file mode 100644
index 00000000..4c306e11
--- /dev/null
+++ b/makefile
@@ -0,0 +1,3 @@
+embroider.tgz: makefile index.html embroider.py embroider.inx images/draft1.jpg images/draft2.jpg images/shirt.jpg PyEmb.py
+	ln -fs embroider .
+	tar czf $@ $^