1 #!/usr/bin/env python \r
2 '''\r
3 Copyright (C) 2001-2002 Matt Chisholm matt@theory.org\r
4 Copyright (C) 2008 Joel Holdsworth joel@airwebreathe.org.uk\r
5 for AP\r
6 \r
7 This program is free software; you can redistribute it and/or modify\r
8 it under the terms of the GNU General Public License as published by\r
9 the Free Software Foundation; either version 2 of the License, or\r
10 (at your option) any later version.\r
11 \r
12 This program is distributed in the hope that it will be useful,\r
13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
15 GNU General Public License for more details.\r
16 \r
17 You should have received a copy of the GNU General Public License\r
18 along with this program; if not, write to the Free Software\r
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\r
20 '''\r
21 \r
22 import copy\r
23 import inkex\r
24 import simplestyle\r
25 import math\r
26 import cmath\r
27 import string\r
28 import random\r
29 import render_alphabetsoup_config\r
30 import bezmisc\r
31 import simplepath\r
32 import os\r
33 import sys\r
34 import gettext\r
35 _ = gettext.gettext\r
36 \r
37 syntax = render_alphabetsoup_config.syntax\r
38 alphabet = render_alphabetsoup_config.alphabet\r
39 units = render_alphabetsoup_config.units\r
40 font = render_alphabetsoup_config.font\r
41 \r
42 # Loads a super-path from a given SVG file\r
43 def loadPath( svgPath ):\r
44 extensionDir = os.path.normpath(\r
45 os.path.join( os.getcwd(), os.path.dirname(__file__) )\r
46 )\r
47 # __file__ is better then sys.argv[0] because this file may be a module\r
48 # for another one.\r
49 tree = inkex.etree.parse( extensionDir + "/" + svgPath )\r
50 root = tree.getroot()\r
51 pathElement = root.find('{http://www.w3.org/2000/svg}path')\r
52 if pathElement == None:\r
53 return None, 0, 0\r
54 d = pathElement.get("d")\r
55 width = float(root.get("width"))\r
56 height = float(root.get("height"))\r
57 return simplepath.parsePath(d), width, height # Currently we only support a single path\r
58 \r
59 def combinePaths( pathA, pathB ):\r
60 if pathA == None and pathB == None:\r
61 return None\r
62 elif pathA == None:\r
63 return pathB\r
64 elif pathB == None:\r
65 return pathA\r
66 else:\r
67 return pathA + pathB\r
68 \r
69 def flipLeftRight( sp, width ):\r
70 for cmd,params in sp:\r
71 defs = simplepath.pathdefs[cmd]\r
72 for i in range(defs[1]):\r
73 if defs[3][i] == 'x':\r
74 params[i] = width - params[i]\r
75 \r
76 def flipTopBottom( sp, height ):\r
77 for cmd,params in sp:\r
78 defs = simplepath.pathdefs[cmd]\r
79 for i in range(defs[1]):\r
80 if defs[3][i] == 'y':\r
81 params[i] = height - params[i]\r
82 \r
83 def solveQuadratic(a, b, c):\r
84 det = b*b - 4.0*a*c\r
85 if det >= 0: # real roots\r
86 sdet = math.sqrt(det)\r
87 else: # complex roots\r
88 sdet = cmath.sqrt(det)\r
89 return (-b + sdet) / (2*a), (-b - sdet) / (2*a)\r
90 \r
91 def cbrt(x): \r
92 if x >= 0:\r
93 return x**(1.0/3.0)\r
94 else:\r
95 return -((-x)**(1.0/3.0))\r
96 \r
97 def findRealRoots(a,b,c,d):\r
98 if a != 0:\r
99 a, b, c, d = 1, b/float(a), c/float(a), d/float(a) # Divide through by a\r
100 t = b / 3.0\r
101 p, q = c - 3 * t**2, d - c * t + 2 * t**3\r
102 u, v = solveQuadratic(1, q, -(p/3.0)**3)\r
103 if type(u) == type(0j): # Complex Cubic Root\r
104 r = math.sqrt(u.real**2 + u.imag**2)\r
105 w = math.atan2(u.imag, u.real)\r
106 y1 = 2 * cbrt(r) * math.cos(w / 3.0)\r
107 else: # Complex Real Root\r
108 y1 = cbrt(u) + cbrt(v)\r
109 \r
110 y2, y3 = solveQuadratic(1, y1, p + y1**2)\r
111 \r
112 if type(y2) == type(0j): # Are y2 and y3 complex?\r
113 return [y1 - t]\r
114 return [y1 - t, y2 - t, y3 - t]\r
115 elif b != 0:\r
116 det=c*c - 4.0*b*d\r
117 if det >= 0:\r
118 return [(-c + math.sqrt(det))/(2.0*b),(-c - math.sqrt(det))/(2.0*b)]\r
119 elif c != 0:\r
120 return [-d/c]\r
121 return []\r
122 \r
123 def getPathBoundingBox( sp ):\r
124 \r
125 box = None\r
126 last = None\r
127 lostctrl = None\r
128 \r
129 for cmd,params in sp:\r
130 \r
131 segmentBox = None\r
132 \r
133 if cmd == 'M':\r
134 # A move cannot contribute to the bounding box\r
135 last = params[:]\r
136 lastctrl = params[:]\r
137 elif cmd == 'L':\r
138 if last:\r
139 segmentBox = (min(params[0], last[0]), max(params[0], last[0]), min(params[1], last[1]), max(params[1], last[1]))\r
140 last = params[:]\r
141 lastctrl = params[:]\r
142 elif cmd == 'C':\r
143 if last: \r
144 segmentBox = (min(params[4], last[0]), max(params[4], last[0]), min(params[5], last[1]), max(params[5], last[1]))\r
145 \r
146 bx0, by0 = last[:]\r
147 bx1, by1, bx2, by2, bx3, by3 = params[:]\r
148 \r
149 # Compute the x limits\r
150 a = (-bx0 + 3*bx1 - 3*bx2 + bx3)*3\r
151 b = (3*bx0 - 6*bx1 + 3*bx2)*2\r
152 c = (-3*bx0 + 3*bx1)\r
153 ts = findRealRoots(0, a, b, c)\r
154 for t in ts:\r
155 if t >= 0 and t <= 1: \r
156 x = (-bx0 + 3*bx1 - 3*bx2 + bx3)*(t**3) + \\r
157 (3*bx0 - 6*bx1 + 3*bx2)*(t**2) + \\r
158 (-3*bx0 + 3*bx1)*t + \\r
159 bx0\r
160 segmentBox = (min(segmentBox[0], x), max(segmentBox[1], x), segmentBox[2], segmentBox[3])\r
161 \r
162 # Compute the y limits\r
163 a = (-by0 + 3*by1 - 3*by2 + by3)*3\r
164 b = (3*by0 - 6*by1 + 3*by2)*2\r
165 c = (-3*by0 + 3*by1)\r
166 ts = findRealRoots(0, a, b, c)\r
167 for t in ts:\r
168 if t >= 0 and t <= 1: \r
169 y = (-by0 + 3*by1 - 3*by2 + by3)*(t**3) + \\r
170 (3*by0 - 6*by1 + 3*by2)*(t**2) + \\r
171 (-3*by0 + 3*by1)*t + \\r
172 by0\r
173 segmentBox = (segmentBox[0], segmentBox[1], min(segmentBox[2], y), max(segmentBox[3], y))\r
174 \r
175 last = params[-2:]\r
176 lastctrl = params[2:4]\r
177 \r
178 elif cmd == 'Q':\r
179 # Provisional\r
180 if last:\r
181 segmentBox = (min(params[0], last[0]), max(params[0], last[0]), min(params[1], last[1]), max(params[1], last[1]))\r
182 last = params[-2:]\r
183 lastctrl = params[2:4]\r
184 \r
185 elif cmd == 'A':\r
186 # Provisional\r
187 if last:\r
188 segmentBox = (min(params[0], last[0]), max(params[0], last[0]), min(params[1], last[1]), max(params[1], last[1]))\r
189 last = params[-2:]\r
190 lastctrl = params[2:4]\r
191 \r
192 if segmentBox:\r
193 if box:\r
194 box = (min(segmentBox[0],box[0]), max(segmentBox[1],box[1]), min(segmentBox[2],box[2]), max(segmentBox[3],box[3]))\r
195 else:\r
196 box = segmentBox \r
197 return box\r
198 \r
199 def mxfm( image, width, height, stack ): # returns possibly transformed image\r
200 tbimage = image \r
201 if ( stack[0] == "-" ): # top-bottom flip\r
202 flipTopBottom(tbimage, height)\r
203 stack.pop( 0 )\r
204 \r
205 lrimage = tbimage\r
206 if ( stack[0] == "|" ): # left-right flip\r
207 flipLeftRight(tbimage, width)\r
208 stack.pop( 0 )\r
209 return lrimage\r
210 \r
211 def comparerule( rule, nodes ): # compare node list to nodes in rule\r
212 for i in range( 0, len(nodes)): # range( a, b ) = (a, a+1, a+2 ... b-2, b-1)\r
213 if (nodes[i] == rule[i][0]):\r
214 pass\r
215 else: return 0\r
216 return 1\r
217 \r
218 def findrule( state, nodes ): # find the rule which generated this subtree\r
219 ruleset = syntax[state][1]\r
220 nodelen = len(nodes)\r
221 for rule in ruleset:\r
222 rulelen = len(rule)\r
223 if ((rulelen == nodelen) and (comparerule( rule, nodes ))):\r
224 return rule\r
225 return \r
226 \r
227 def generate( state ): # generate a random tree (in stack form)\r
228 stack = [ state ]\r
229 if ( len(syntax[state]) == 1 ): # if this is a stop symbol\r
230 return stack\r
231 else:\r
232 stack.append( "[" )\r
233 path = random.randint(0, (len(syntax[state][1])-1)) # choose randomly from next states\r
234 for symbol in syntax[state][1][path]: # recurse down each non-terminal\r
235 if ( symbol != 0 ): # 0 denotes end of list ###\r
236 substack = generate( symbol[0] ) # get subtree\r
237 for elt in substack: \r
238 stack.append( elt )\r
239 if (symbol[3]):stack.append( "-" ) # top-bottom flip\r
240 if (symbol[4]):stack.append( "|" ) # left-right flip\r
241 #else:\r
242 #inkex.debug("found end of list in generate( state =", state, ")") # this should be deprecated/never happen\r
243 stack.append("]")\r
244 return stack\r
245 \r
246 def draw( stack ): # draw a character based on a tree stack\r
247 state = stack.pop(0)\r
248 #print state,\r
249 \r
250 image, width, height = loadPath( font+syntax[state][0] ) # load the image\r
251 if (stack[0] != "["): # terminal stack element\r
252 if (len(syntax[state]) == 1): # this state is a terminal node\r
253 return image, width, height\r
254 else:\r
255 substack = generate( state ) # generate random substack\r
256 return draw( substack ) # draw random substack\r
257 else:\r
258 #inkex.debug("[")\r
259 stack.pop(0)\r
260 images = [] # list of daughter images\r
261 nodes = [] # list of daughter names\r
262 while (stack[0] != "]"): # for all nodes in stack\r
263 newstate = stack[0] # the new state\r
264 newimage, width, height = draw( stack ) # draw the daughter state\r
265 if (newimage):\r
266 tfimage = mxfm( newimage, width, height, stack ) # maybe transform daughter state\r
267 images.append( [tfimage, width, height] ) # list of daughter images\r
268 nodes.append( newstate ) # list of daughter nodes\r
269 else:\r
270 #inkex.debug(("recurse on",newstate,"failed")) # this should never happen\r
271 return None, 0, 0\r
272 rule = findrule( state, nodes ) # find the rule for this subtree\r
273 \r
274 for i in range( 0, len(images)):\r
275 currimg, width, height = images[i]\r
276 \r
277 if currimg:\r
278 #box = getPathBoundingBox(currimg)\r
279 dx = rule[i][1]*units\r
280 dy = rule[i][2]*units\r
281 #newbox = ((box[0]+dx),(box[1]+dy),(box[2]+dx),(box[3]+dy))\r
282 simplepath.translatePath(currimg, dx, dy)\r
283 image = combinePaths( image, currimg )\r
284 \r
285 stack.pop( 0 )\r
286 return image, width, height\r
287 \r
288 def draw_crop_scale( stack, zoom ): # draw, crop and scale letter image\r
289 image, width, height = draw(stack)\r
290 bbox = getPathBoundingBox(image) \r
291 simplepath.translatePath(image, -bbox[0], 0) \r
292 simplepath.scalePath(image, zoom/units, zoom/units)\r
293 return image, bbox[1] - bbox[0], bbox[3] - bbox[2]\r
294 \r
295 def randomize_input_string( str, zoom ): # generate list of images based on input string\r
296 imagelist = []\r
297 \r
298 for i in range(0,len(str)):\r
299 char = str[i]\r
300 #if ( re.match("[a-zA-Z0-9?]", char)):\r
301 if ( alphabet.has_key(char)):\r
302 if ((i > 0) and (char == str[i-1])): # if this letter matches previous letter\r
303 imagelist.append(imagelist[len(stack)-1])# make them the same image\r
304 else: # generate image for letter\r
305 stack = string.split( alphabet[char][random.randint(0,(len(alphabet[char])-1))] , "." )\r
306 #stack = string.split( alphabet[char][random.randint(0,(len(alphabet[char])-2))] , "." ) \r
307 imagelist.append( draw_crop_scale( stack, zoom ))\r
308 elif( char == " "): # add a " " space to the image list\r
309 imagelist.append( " " )\r
310 else: # this character is not in config.alphabet, skip it\r
311 inkex.errormsg(_("bad character") + " = 0x%x" % ord(char))\r
312 return imagelist\r
313 \r
314 def optikern( image, width, zoom ): # optical kerning algorithm\r
315 left = []\r
316 right = []\r
317 \r
318 for i in range( 0, 36 ):\r
319 y = 0.5 * (i + 0.5) * zoom\r
320 xmin = None\r
321 xmax = None\r
322 \r
323 for cmd,params in image:\r
324 \r
325 segmentBox = None\r
326 \r
327 if cmd == 'M':\r
328 # A move cannot contribute to the bounding box\r
329 last = params[:]\r
330 lastctrl = params[:]\r
331 elif cmd == 'L':\r
332 if (y >= last[1] and y <= params[1]) or (y >= params[1] and y <= last[1]):\r
333 if params[0] == last[0]:\r
334 x = params[0]\r
335 else:\r
336 a = (params[1] - last[1]) / (params[0] - last[0])\r
337 b = last[1] - a * last[0]\r
338 if a != 0:\r
339 x = (y - b) / a\r
340 else: x = None\r
341 \r
342 if x:\r
343 if xmin == None or x < xmin: xmin = x\r
344 if xmax == None or x > xmax: xmax = x\r
345 \r
346 last = params[:]\r
347 lastctrl = params[:]\r
348 elif cmd == 'C':\r
349 if last: \r
350 bx0, by0 = last[:]\r
351 bx1, by1, bx2, by2, bx3, by3 = params[:]\r
352 \r
353 d = by0 - y\r
354 c = -3*by0 + 3*by1\r
355 b = 3*by0 - 6*by1 + 3*by2\r
356 a = -by0 + 3*by1 - 3*by2 + by3\r
357 \r
358 ts = findRealRoots(a, b, c, d)\r
359 \r
360 for t in ts:\r
361 if t >= 0 and t <= 1: \r
362 x = (-bx0 + 3*bx1 - 3*bx2 + bx3)*(t**3) + \\r
363 (3*bx0 - 6*bx1 + 3*bx2)*(t**2) + \\r
364 (-3*bx0 + 3*bx1)*t + \\r
365 bx0\r
366 if xmin == None or x < xmin: xmin = x\r
367 if xmax == None or x > xmax: xmax = x\r
368 \r
369 last = params[-2:]\r
370 lastctrl = params[2:4]\r
371 \r
372 elif cmd == 'Q':\r
373 # Quadratic beziers are ignored\r
374 last = params[-2:]\r
375 lastctrl = params[2:4]\r
376 \r
377 elif cmd == 'A':\r
378 # Arcs are ignored\r
379 last = params[-2:]\r
380 lastctrl = params[2:4]\r
381 \r
382 \r
383 if xmin != None and xmax != None:\r
384 left.append( xmin ) # distance from left edge of region to left edge of bbox\r
385 right.append( width - xmax ) # distance from right edge of region to right edge of bbox\r
386 else:\r
387 left.append( width )\r
388 right.append( width )\r
389 \r
390 return (left, right)\r
391 \r
392 def layoutstring( imagelist, zoom ): # layout string of letter-images using optical kerning\r
393 kernlist = []\r
394 length = zoom\r
395 for entry in imagelist:\r
396 if (entry == " "): # leaving room for " " space characters\r
397 length = length + (zoom * render_alphabetsoup_config.space)\r
398 else:\r
399 image, width, height = entry\r
400 length = length + width + zoom # add letter length to overall length\r
401 kernlist.append( optikern(image, width, zoom) ) # append kerning data for this image \r
402 \r
403 workspace = None\r
404 \r
405 position = zoom\r
406 for i in range(0, len(kernlist)):\r
407 while(imagelist[i] == " "):\r
408 position = position + (zoom * render_alphabetsoup_config.space )\r
409 imagelist.pop(i)\r
410 image, width, height = imagelist[i]\r
411 \r
412 # set the kerning\r
413 if i == 0: kern = 0 # for first image, kerning is zero\r
414 else:\r
415 kerncompare = [] # kerning comparison array\r
416 for j in range( 0, len(kernlist[i][0])):\r
417 kerncompare.append( kernlist[i][0][j]+kernlist[i-1][1][j] )\r
418 kern = min( kerncompare )\r
419 \r
420 position = position - kern # move position back by kern amount\r
421 thisimage = copy.deepcopy(image) \r
422 simplepath.translatePath(thisimage, position, 0)\r
423 workspace = combinePaths(workspace, thisimage)\r
424 position = position + width + zoom # advance position by letter width\r
425 \r
426 return workspace\r
427 \r
428 class AlphabetSoup(inkex.Effect):\r
429 def __init__(self):\r
430 inkex.Effect.__init__(self)\r
431 self.OptionParser.add_option("-t", "--text",\r
432 action="store", type="string", \r
433 dest="text", default="Inkscape",\r
434 help="The text for alphabet soup")\r
435 self.OptionParser.add_option("-z", "--zoom",\r
436 action="store", type="float", \r
437 dest="zoom", default="8.0",\r
438 help="The zoom on the output graphics")\r
439 self.OptionParser.add_option("-s", "--seed",\r
440 action="store", type="int", \r
441 dest="seed", default="0",\r
442 help="The random seed for the soup")\r
443 \r
444 def effect(self):\r
445 zoom = self.options.zoom\r
446 random.seed(self.options.seed)\r
447 \r
448 imagelist = randomize_input_string(self.options.text, zoom)\r
449 image = layoutstring( imagelist, zoom )\r
450 \r
451 if image:\r
452 s = { 'stroke': 'none', 'fill': '#000000' }\r
453 \r
454 new = inkex.etree.Element(inkex.addNS('path','svg'))\r
455 new.set('style', simplestyle.formatStyle(s))\r
456 \r
457 new.set('d', simplepath.formatPath(image))\r
458 self.current_layer.append(new)\r
459 \r
460 if __name__ == '__main__':\r
461 e = AlphabetSoup()\r
462 e.affect()\r
463 \r