src/trace/potrace/decompose.cpp

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