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