src/trace/potrace/decompose.cpp

   1 /* Copyright (C) 2001-2007 Peter Selinger.
   2    This file is part of Potrace. It is free software and it is covered
   3    by the GNU General Public License. See the file COPYING for details. */
   4
   5 /* $Id$ */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <limits.h>
  11
  12 #include "potracelib.h"
  13 #include "curve.h"
  14 #include "lists.h"
  15 #include "auxiliary.h"
  16 #include "bitmap.h"
  17 #include "decompose.h"
  18 #include "progress.h"
  19
  20 /* ---------------------------------------------------------------------- */
  21 /* auxiliary bitmap manipulations */
  22
  23 /* set the excess padding to 0 */
  24 static void bm_clearexcess(potrace_bitmap_t *bm) {
  25   potrace_word mask;
  26   int y;
  27
  28   if (bm->w % BM_WORDBITS != 0) {
  29     mask = BM_ALLBITS << (BM_WORDBITS - (bm->w % BM_WORDBITS));
  30     for (y=0; y<bm->h; y++) {
  31       *bm_index(bm, bm->w, y) &= mask;
  32     }
  33   }
  34 }
  35
  36 struct bbox_s {
  37   int x0, x1, y0, y1;    /* bounding box */
  38 };
  39 typedef struct bbox_s bbox_t;
  40
  41 /* clear the bm, assuming the bounding box is set correctly (faster
  42    than clearing the whole bitmap) */
  43 static void clear_bm_with_bbox(potrace_bitmap_t *bm, bbox_t *bbox) {
  44   int imin = (bbox->x0 / BM_WORDBITS);
  45   int imax = ((bbox->x1 + BM_WORDBITS-1) / BM_WORDBITS);
  46   int i, y;
  47
  48   for (y=bbox->y0; y<bbox->y1; y++) {
  49     for (i=imin; i<imax; i++) {
  50       bm_scanline(bm, y)[i] = 0;
  51     }
  52   }
  53 }
  54
  55 /* ---------------------------------------------------------------------- */
  56 /* auxiliary functions */
  57
  58 /* deterministically and efficiently hash (x,y) into a pseudo-random bit */
  59 static inline int detrand(int x, int y) {
  60   unsigned int z;
  61   static const unsigned char t[256] = {
  62     /* non-linear sequence: constant term of inverse in GF(8),
  63        mod x^8+x^4+x^3+x+1 */
  64     0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1,
  65     0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0,
  66     0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
  67     1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1,
  68     0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0,
  69     0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0,
  70     0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0,
  71     0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1,
  72     1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0,
  73     0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1,
  74     1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
  75   };
  76
  77   /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible
  78      5-bit sequence */
  79   z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93;
  80   z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff];
  81   return z & 1;
  82 }
  83
  84 /* return the "majority" value of bitmap bm at intersection (x,y). We
  85    assume that the bitmap is balanced at "radius" 1.  */
  86 static int majority(potrace_bitmap_t *bm, int x, int y) {
  87   int i, a, ct;
  88
  89   for (i=2; i<5; i++) { /* check at "radius" i */
  90     ct = 0;
  91     for (a=-i+1; a<=i-1; a++) {
  92       ct += BM_GET(bm, x+a, y+i-1) ? 1 : -1;
  93       ct += BM_GET(bm, x+i-1, y+a-1) ? 1 : -1;
  94       ct += BM_GET(bm, x+a-1, y-i) ? 1 : -1;
  95       ct += BM_GET(bm, x-i, y+a) ? 1 : -1;
  96     }
  97     if (ct>0) {
  98       return 1;
  99     } else if (ct<0) {
 100       return 0;
 101     }
 102   }
 103   return 0;
 104 }
 105
 106 /* ---------------------------------------------------------------------- */
 107 /* decompose image into paths */
 108
 109 /* efficiently invert bits [x,infty) and [xa,infty) in line y. Here xa
 110    must be a multiple of BM_WORDBITS. */
 111 static void xor_to_ref(potrace_bitmap_t *bm, int x, int y, int xa) {
 112   int xhi = x & -BM_WORDBITS;
 113   int xlo = x & (BM_WORDBITS-1);  /* = x % BM_WORDBITS */
 114   int i;
 115
 116   if (xhi<xa) {
 117     for (i = xhi; i < xa; i+=BM_WORDBITS) {
 118       *bm_index(bm, i, y) ^= BM_ALLBITS;
 119     }
 120   } else {
 121     for (i = xa; i < xhi; i+=BM_WORDBITS) {
 122       *bm_index(bm, i, y) ^= BM_ALLBITS;
 123     }
 124   }
 125   /* note: the following "if" is needed because x86 treats a<<b as
 126      a<<(b&31). I spent hours looking for this bug. */
 127   if (xlo) {
 128     *bm_index(bm, xhi, y) ^= (BM_ALLBITS << (BM_WORDBITS - xlo));
 129   }
 130 }
 131
 132 /* a path is represented as an array of points, which are thought to
 133    lie on the corners of pixels (not on their centers). The path point
 134    (x,y) is the lower left corner of the pixel (x,y). Paths are
 135    represented by the len/pt components of a path_t object (which
 136    also stores other information about the path) */
 137
 138 /* xor the given pixmap with the interior of the given path. Note: the
 139    path must be within the dimensions of the pixmap. */
 140 static void xor_path(potrace_bitmap_t *bm, path_t *p) {
 141   int xa, x, y, k, y1;
 142
 143   if (p->priv->len <= 0) {  /* a path of length 0 is silly, but legal */
 144     return;
 145   }
 146
 147   y1 = p->priv->pt[p->priv->len-1].y;
 148
 149   xa = p->priv->pt[0].x & -BM_WORDBITS;
 150   for (k=0; k<p->priv->len; k++) {
 151     x = p->priv->pt[k].x;
 152     y = p->priv->pt[k].y;
 153
 154     if (y != y1) {
 155       /* efficiently invert the rectangle [x,xa] x [y,y1] */
 156       xor_to_ref(bm, x, min(y,y1), xa);
 157       y1 = y;
 158     }
 159   }
 160 }
 161
 162 /* Find the bounding box of a given path. Path is assumed to be of
 163    non-zero length. */
 164 static void setbbox_path(bbox_t *bbox, path_t *p) {
 165   int x, y;
 166   int k;
 167
 168   bbox->y0 = INT_MAX;
 169   bbox->y1 = 0;
 170   bbox->x0 = INT_MAX;
 171   bbox->x1 = 0;
 172
 173   for (k=0; k<p->priv->len; k++) {
 174     x = p->priv->pt[k].x;
 175     y = p->priv->pt[k].y;
 176
 177     if (x < bbox->x0) {
 178       bbox->x0 = x;
 179     }
 180     if (x > bbox->x1) {
 181       bbox->x1 = x;
 182     }
 183     if (y < bbox->y0) {
 184       bbox->y0 = y;
 185     }
 186     if (y > bbox->y1) {
 187       bbox->y1 = y;
 188     }
 189   }
 190 }
 191
 192 /* compute a path in the given pixmap, separating black from white.
 193    Start path at the point (x0,x1), which must be an upper left corner
 194    of the path. Also compute the area enclosed by the path. Return a
 195    new path_t object, or NULL on error (note that a legitimate path
 196    cannot have length 0). Sign is required for correct interpretation
 197    of turnpolicies. */
 198 static path_t *findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy) {
 199   int x, y, dirx, diry, len, size, area;
 200   int c, d, tmp;
 201   point_t *pt, *pt1;
 202   path_t *p = NULL;
 203
 204   x = x0;
 205   y = y0;
 206   dirx = 0;
 207   diry = -1;
 208
 209   len = size = 0;
 210   pt = NULL;
 211   area = 0;
 212
 213   while (1) {
 214     /* add point to path */
 215     if (len>=size) {
 216       size += 100;
 217       size = (int)(1.3 * size);
 218       pt1 = (point_t *)realloc(pt, size * sizeof(point_t));
 219       if (!pt1) {
 220         goto error;
 221       }
 222       pt = pt1;
 223     }
 224     pt[len].x = x;
 225     pt[len].y = y;
 226     len++;
 227
 228     /* move to next point */
 229     x += dirx;
 230     y += diry;
 231     area += x*diry;
 232
 233     /* path complete? */
 234     if (x==x0 && y==y0) {
 235       break;
 236     }
 237
 238     /* determine next direction */
 239     c = BM_GET(bm, x + (dirx+diry-1)/2, y + (diry-dirx-1)/2);
 240     d = BM_GET(bm, x + (dirx-diry-1)/2, y + (diry+dirx-1)/2);
 241
 242     if (c && !d) {               /* ambiguous turn */
 243       if (turnpolicy == POTRACE_TURNPOLICY_RIGHT
 244           || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+')
 245           || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-')
 246           || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand(x,y))
 247           || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y))
 248           || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) {
 249         tmp = dirx;              /* right turn */
 250         dirx = diry;
 251         diry = -tmp;
 252       } else {
 253         tmp = dirx;              /* left turn */
 254         dirx = -diry;
 255         diry = tmp;
 256       }
 257     } else if (c) {              /* right turn */
 258       tmp = dirx;
 259       dirx = diry;
 260       diry = -tmp;
 261     } else if (!d) {             /* left turn */
 262       tmp = dirx;
 263       dirx = -diry;
 264       diry = tmp;
 265     }
 266   } /* while this path */
 267
 268   /* allocate new path object */
 269   p = path_new();
 270   if (!p) {
 271     goto error;
 272   }
 273
 274   p->priv->pt = pt;
 275   p->priv->len = len;
 276   p->area = area;
 277   p->sign = sign;
 278
 279   return p;
 280
 281  error:
 282    free(pt);
 283    return NULL;
 284 }
 285
 286 /* Give a tree structure to the given path list, based on "insideness"
 287    testing. I.e., path A is considered "below" path B if it is inside
 288    path B. The input pathlist is assumed to be ordered so that "outer"
 289    paths occur before "inner" paths. The tree structure is stored in
 290    the "childlist" and "sibling" components of the path_t
 291    structure. The linked list structure is also changed so that
 292    negative path components are listed immediately after their
 293    positive parent.  Note: some backends may ignore the tree
 294    structure, others may use it e.g. to group path components. We
 295    assume that in the input, point 0 of each path is an "upper left"
 296    corner of the path, as returned by bm_to_pathlist. This makes it
 297    easy to find an "interior" point. The bm argument should be a
 298    bitmap of the correct size (large enough to hold all the paths),
 299    and will be used as scratch space. Return 0 on success or -1 on
 300    error with errno set. */
 301
 302 static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) {
 303   path_t *p, *p1;
 304   path_t *heap, *heap1;
 305   path_t *cur;
 306   path_t *head;
 307   path_t **hook, **hook_in, **hook_out; /* for fast appending to linked list */
 308   bbox_t bbox;
 309
 310   bm_clear(bm, 0);
 311
 312   /* save original "next" pointers */
 313   list_forall(p, plist) {
 314     p->sibling = p->next;
 315     p->childlist = NULL;
 316   }
 317
 318   heap = plist;
 319
 320   /* the heap holds a list of lists of paths. Use "childlist" field
 321      for outer list, "next" field for inner list. Each of the sublists
 322      is to be turned into a tree. This code is messy, but it is
 323      actually fast. Each path is rendered exactly once. We use the
 324      heap to get a tail recursive algorithm: the heap holds a list of
 325      pathlists which still need to be transformed. */
 326
 327   while (heap) {
 328     /* unlink first sublist */
 329     cur = heap;
 330     heap = heap->childlist;
 331     cur->childlist = NULL;
 332
 333     /* unlink first path */
 334     head = cur;
 335     cur = cur->next;
 336     head->next = NULL;
 337
 338     /* render path */
 339     xor_path(bm, head);
 340     setbbox_path(&bbox, head);
 341
 342     /* now do insideness test for each element of cur; append it to
 343        head->childlist if it's inside head, else append it to
 344        head->next. */
 345     hook_in=&head->childlist;
 346     hook_out=&head->next;
 347     list_forall_unlink(p, cur) {
 348       if (p->priv->pt[0].y <= bbox.y0) {
 349         list_insert_beforehook(p, hook_out);
 350         /* append the remainder of the list to hook_out */
 351         *hook_out = cur;
 352         break;
 353       }
 354       if (BM_GET(bm, p->priv->pt[0].x, p->priv->pt[0].y-1)) {
 355         list_insert_beforehook(p, hook_in);
 356       } else {
 357         list_insert_beforehook(p, hook_out);
 358       }
 359     }
 360
 361     /* clear bm */
 362     clear_bm_with_bbox(bm, &bbox);
 363
 364     /* now schedule head->childlist and head->next for further
 365        processing */
 366     if (head->next) {
 367       head->next->childlist = heap;
 368       heap = head->next;
 369     }
 370     if (head->childlist) {
 371       head->childlist->childlist = heap;
 372       heap = head->childlist;
 373     }
 374   }
 375
 376   /* copy sibling structure from "next" to "sibling" component */
 377   p = plist;
 378   while (p) {
 379     p1 = p->sibling;
 380     p->sibling = p->next;
 381     p = p1;
 382   }
 383
 384   /* reconstruct a new linked list ("next") structure from tree
 385      ("childlist", "sibling") structure. This code is slightly messy,
 386      because we use a heap to make it tail recursive: the heap
 387      contains a list of childlists which still need to be
 388      processed. */
 389   heap = plist;
 390   if (heap) {
 391     heap->next = NULL;  /* heap is a linked list of childlists */
 392   }
 393   plist = NULL;
 394   hook = &plist;
 395   while (heap) {
 396     heap1 = heap->next;
 397     for (p=heap; p; p=p->sibling) {
 398       /* p is a positive path */
 399       /* append to linked list */
 400       list_insert_beforehook(p, hook);
 401
 402       /* go through its children */
 403       for (p1=p->childlist; p1; p1=p1->sibling) {
 404         /* append to linked list */
 405         list_insert_beforehook(p1, hook);
 406         /* append its childlist to heap, if non-empty */
 407         if (p1->childlist) {
 408           list_append(path_t, heap1, p1->childlist);
 409         }
 410       }
 411     }
 412     heap = heap1;
 413   }
 414
 415   return;
 416 }
 417
 418 /* find the next set pixel in a row <= y. Pixels are searched first
 419    left-to-right, then top-down. In other words, (x,y)<(x',y') if y>y'
 420    or y=y' and x<x'. If found, return 0 and store pixel in
 421    (*xp,*yp). Else return 1. Note that this function assumes that
 422    excess bytes have been cleared with bm_clearexcess. */
 423 static int findnext(potrace_bitmap_t *bm, int *xp, int *yp) {
 424   int x;
 425   int y;
 426
 427   for (y=*yp; y>=0; y--) {
 428     for (x=0; x<bm->w; x+=BM_WORDBITS) {
 429       if (*bm_index(bm, x, y)) {
 430         while (!BM_GET(bm, x, y)) {
 431           x++;
 432         }
 433         /* found */
 434         *xp = x;
 435         *yp = y;
 436         return 0;
 437       }
 438     }
 439   }
 440   /* not found */
 441   return 1;
 442 }
 443
 444 /* Decompose the given bitmap into paths. Returns a linked list of
 445    path_t objects with the fields len, pt, area, sign filled
 446    in. Returns 0 on success with plistp set, or -1 on error with errno
 447    set. */
 448
 449 int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress) {
 450   int x;
 451   int y;
 452   path_t *p;
 453   path_t *plist = NULL;  /* linked list of path objects */
 454   path_t **hook = &plist;  /* used to speed up appending to linked list */
 455   potrace_bitmap_t *bm1 = NULL;
 456   int sign;
 457
 458   bm1 = bm_dup(bm);
 459   if (!bm1) {
 460     goto error;
 461   }
 462
 463   /* be sure the byte padding on the right is set to 0, as the fast
 464      pixel search below relies on it */
 465   bm_clearexcess(bm1);
 466
 467   /* iterate through components */
 468   y = bm1->h - 1;
 469   while (findnext(bm1, &x, &y) == 0) {
 470     /* calculate the sign by looking at the original */
 471     sign = BM_GET(bm, x, y) ? '+' : '-';
 472
 473     /* calculate the path */
 474     p = findpath(bm1, x, y+1, sign, param->turnpolicy);
 475     if (p==NULL) {
 476       goto error;
 477     }
 478
 479     /* update buffered image */
 480     xor_path(bm1, p);
 481
 482     /* if it's a turd, eliminate it, else append it to the list */
 483     if (p->area <= param->turdsize) {
 484       path_free(p);
 485     } else {
 486       list_insert_beforehook(p, hook);
 487     }
 488
 489     if (bm1->h > 0) { /* to be sure */
 490       progress_update(1-y/(double)bm1->h, progress);
 491     }
 492   }
 493
 494   pathlist_to_tree(plist, bm1);
 495   bm_free(bm1);
 496   *plistp = plist;
 497
 498   progress_update(1.0, progress);
 499
 500   return 0;
 501
 502  error:
 503   bm_free(bm1);
 504   list_forall_unlink(p, plist) {
 505     path_free(p);
 506   }
 507   return -1;
 508 }