share/extensions/render_alphabetsoup.py

   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