share/extensions/render_alphabetsoup.py

   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
   6
   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.
  11
  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.
  16
  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 '''
  21
  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
  36
  37 syntax   = render_alphabetsoup_config.syntax
  38 alphabet = render_alphabetsoup_config.alphabet
  39 units   = render_alphabetsoup_config.units
  40 font     = render_alphabetsoup_config.font
  41
  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
  58
  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
  68
  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]
  75
  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]
  82
  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)
  90
  91 def cbrt(x):
  92         if x >= 0:
  93                 return x**(1.0/3.0)
  94         else:
  95                 return -((-x)**(1.0/3.0))
  96
  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)
 109
 110                 y2, y3 = solveQuadratic(1, y1, p + y1**2)
 111
 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 []
 122
 123 def getPathBoundingBox( sp ):
 124
 125         box = None
 126         last = None
 127         lostctrl = None
 128
 129         for cmd,params in sp:
 130
 131                 segmentBox = None
 132
 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]))
 145
 146                                 bx0, by0 = last[:]
 147                                 bx1, by1, bx2, by2, bx3, by3 = params[:]
 148
 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])
 161
 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))
 174
 175                         last = params[-2:]
 176                         lastctrl = params[2:4]
 177
 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]
 184
 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]
 191
 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
 198
 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 )
 204
 205         lrimage = tbimage
 206         if ( stack[0] == "|" ):                                                   # left-right flip
 207                 flipLeftRight(tbimage, width)
 208                 stack.pop( 0 )
 209         return lrimage
 210
 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
 217
 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
 226
 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
 245
 246 def draw( stack ):                                                                         # draw a character based on a tree stack
 247         state = stack.pop(0)
 248         #print state,
 249
 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
 273
 274                 for i in range( 0, len(images)):
 275                         currimg, width, height = images[i]
 276
 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 )
 284
 285                 stack.pop( 0 )
 286                 return image, width, height
 287
 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]
 294
 295 def randomize_input_string( str, zoom ):                                           # generate list of images based on input string
 296         imagelist = []
 297
 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
 313
 314 def optikern( image, width, zoom ):                                   # optical kerning algorithm
 315         left  = []
 316         right = []
 317
 318         for i in range( 0, 36 ):
 319                 y = 0.5 * (i + 0.5) * zoom
 320                 xmin = None
 321                 xmax = None
 322
 323                 for cmd,params in image:
 324
 325                         segmentBox = None
 326
 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
 341
 342                                         if x:
 343                                                 if xmin == None or x < xmin: xmin = x
 344                                                 if xmax == None or x > xmax: xmax = x
 345
 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[:]
 352
 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
 357
 358                                         ts = findRealRoots(a, b, c, d)
 359
 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
 368
 369                                 last = params[-2:]
 370                                 lastctrl = params[2:4]
 371
 372                         elif cmd == 'Q':
 373                                 # Quadratic beziers are ignored
 374                                 last = params[-2:]
 375                                 lastctrl = params[2:4]
 376
 377                         elif cmd == 'A':
 378                                 # Arcs are ignored
 379                                 last = params[-2:]
 380                                 lastctrl = params[2:4]
 381
 382
 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 )
 389
 390         return (left, right)
 391
 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
 402
 403         workspace = None
 404
 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]
 411
 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 )
 419
 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
 425
 426         return workspace
 427
 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")
 443
 444         def effect(self):
 445                 zoom = self.options.zoom
 446                 random.seed(self.options.seed)
 447
 448                 imagelist = randomize_input_string(self.options.text, zoom)
 449                 image = layoutstring( imagelist, zoom )
 450
 451                 if image:
 452                         s = { 'stroke': 'none', 'fill': '#000000' }
 453
 454                         new = inkex.etree.Element(inkex.addNS('path','svg'))
 455                         new.set('style', simplestyle.formatStyle(s))
 456
 457                         new.set('d', simplepath.formatPath(image))
 458                         self.current_layer.append(new)
 459
 460 if __name__ == '__main__':
 461     e = AlphabetSoup()
 462     e.affect()
 463