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       pt1 = (point_t *)realloc(pt, size * sizeof(point_t));
 192       if (!pt1) {
 193         goto error;
 194       }
 195       pt = pt1;
 196     }
 197     pt[len].x = x;
 198     pt[len].y = y;
 199     len++;
 200
 201     /* move to next point */
 202     x += dirx;
 203     y += diry;
 204     area += x*diry;
 205
 206     /* path complete? */
 207     if (x==x0 && y==y0) {
 208       break;
 209     }
 210
 211     /* determine next direction */
 212     c = BM_GET(bm, x + (dirx+diry-1)/2, y + (diry-dirx-1)/2);
 213     d = BM_GET(bm, x + (dirx-diry-1)/2, y + (diry+dirx-1)/2);
 214
 215     if (c && !d) {               /* ambiguous turn */
 216       if (turnpolicy == POTRACE_TURNPOLICY_RIGHT
 217           || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+')
 218           || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-')
 219           || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && (detrand(x,y) & 1))
 220           || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y))
 221           || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) {
 222         tmp = dirx;              /* right turn */
 223         dirx = diry;
 224         diry = -tmp;
 225       } else {
 226         tmp = dirx;              /* left turn */
 227         dirx = -diry;
 228         diry = tmp;
 229       }
 230     } else if (c) {              /* right turn */
 231       tmp = dirx;
 232       dirx = diry;
 233       diry = -tmp;
 234     } else if (!d) {             /* left turn */
 235       tmp = dirx;
 236       dirx = -diry;
 237       diry = tmp;
 238     }
 239   } /* while this path */
 240
 241   /* allocate new path object */
 242   p = path_new();
 243   if (!p) {
 244     goto error;
 245   }
 246
 247   p->priv->pt = pt;
 248   p->priv->len = len;
 249   p->area = area;
 250   p->sign = sign;
 251
 252   return p;
 253
 254  error:
 255    free(pt);
 256    return NULL;
 257 }
 258
 259 /* Give a tree structure to the given path list, based on "insideness"
 260    testing. I.e., path A is considered "below" path B if it is inside
 261    path B. The input pathlist is assumed to be ordered so that "outer"
 262    paths occur before "inner" paths. The tree structure is stored in
 263    the "childlist" and "sibling" components of the path_t
 264    structure. The linked list structure is also changed so that
 265    negative path components are listed immediately after their
 266    positive parent.  Note: some backends may ignore the tree
 267    structure, others may use it e.g. to group path components. We
 268    assume that in the input, point 0 of each path is an "upper left"
 269    corner of the path, as returned by bm_to_pathlist. This makes it
 270    easy to find an "interior" point. The bm argument should be a
 271    bitmap of the correct size (large enough to hold all the paths),
 272    and will be used as scratch space. Return 0 on success or -1 on
 273    error with errno set. */
 274
 275 static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) {
 276   path_t *p, *p1;
 277   path_t *heap, *heap1;
 278   path_t *cur;
 279   path_t *head;
 280   path_t **hook, **hook_in, **hook_out; /* for fast appending to linked list */
 281   bbox_t bbox;
 282
 283   bm_clear(bm, 0);
 284
 285   /* save original "next" pointers */
 286   list_forall(p, plist) {
 287     p->sibling = p->next;
 288     p->childlist = NULL;
 289   }
 290
 291   heap = plist;
 292
 293   /* the heap holds a list of lists of paths. Use "childlist" field
 294      for outer list, "next" field for inner list. Each of the sublists
 295      is to be turned into a tree. This code is messy, but it is
 296      actually fast. Each path is rendered exactly once. We use the
 297      heap to get a tail recursive algorithm: the heap holds a list of
 298      pathlists which still need to be transformed. */
 299
 300   while (heap) {
 301     /* unlink first sublist */
 302     cur = heap;
 303     heap = heap->childlist;
 304     cur->childlist = NULL;
 305
 306     /* unlink first path */
 307     head = cur;
 308     cur = cur->next;
 309     head->next = NULL;
 310
 311     /* render path */
 312     xor_path(bm, head);
 313     setbbox_path(&bbox, head);
 314
 315     /* now do insideness test for each element of cur; append it to
 316        head->childlist if it's inside head, else append it to
 317        head->next. */
 318     hook_in=&head->childlist;
 319     hook_out=&head->next;
 320     list_forall_unlink(p, cur) {
 321       if (p->priv->pt[0].y <= bbox.y0) {
 322         list_insert_beforehook(p, hook_out);
 323         /* append the remainder of the list to hook_out */
 324         *hook_out = cur;
 325         break;
 326       }
 327       if (BM_GET(bm, p->priv->pt[0].x, p->priv->pt[0].y-1)) {
 328         list_insert_beforehook(p, hook_in);
 329       } else {
 330         list_insert_beforehook(p, hook_out);
 331       }
 332     }
 333
 334     /* clear bm */
 335     clear_bm_with_bbox(bm, &bbox);
 336
 337     /* now schedule head->childlist and head->next for further
 338        processing */
 339     if (head->next) {
 340       head->next->childlist = heap;
 341       heap = head->next;
 342     }
 343     if (head->childlist) {
 344       head->childlist->childlist = heap;
 345       heap = head->childlist;
 346     }
 347   }
 348
 349   /* copy sibling structure from "next" to "sibling" component */
 350   p = plist;
 351   while (p) {
 352     p1 = p->sibling;
 353     p->sibling = p->next;
 354     p = p1;
 355   }
 356
 357   /* reconstruct a new linked list ("next") structure from tree
 358      ("childlist", "sibling") structure. This code is slightly messy,
 359      because we use a heap to make it tail recursive: the heap
 360      contains a list of childlists which still need to be
 361      processed. */
 362   heap = plist;
 363   if (heap) {
 364     heap->next = NULL;  /* heap is a linked list of childlists */
 365   }
 366   plist = NULL;
 367   hook = &plist;
 368   while (heap) {
 369     heap1 = heap->next;
 370     for (p=heap; p; p=p->sibling) {
 371       /* p is a positive path */
 372       /* append to linked list */
 373       list_insert_beforehook(p, hook);
 374
 375       /* go through its children */
 376       for (p1=p->childlist; p1; p1=p1->sibling) {
 377         /* append to linked list */
 378         list_insert_beforehook(p1, hook);
 379         /* append its childlist to heap, if non-empty */
 380         if (p1->childlist) {
 381           list_append(path_t, heap1, p1->childlist);
 382         }
 383       }
 384     }
 385     heap = heap1;
 386   }
 387
 388   return;
 389 }
 390
 391 /* find the next set pixel in a row <= y. Pixels are searched first
 392    left-to-right, then top-down. In other words, (x,y)<(x',y') if y>y'
 393    or y=y' and x<x'. If found, return 0 and store pixel in
 394    (*xp,*yp). Else return 1. Note that this function assumes that
 395    excess bytes have been cleared with bm_clearexcess. */
 396 static int findnext(potrace_bitmap_t *bm, int *xp, int *yp) {
 397   int x;
 398   int y;
 399
 400   for (y=*yp; y>=0; y--) {
 401     for (x=0; x<bm->w; x+=BM_WORDBITS) {
 402       if (*bm_index(bm, x, y)) {
 403         while (!BM_GET(bm, x, y)) {
 404           x++;
 405         }
 406         /* found */
 407         *xp = x;
 408         *yp = y;
 409         return 0;
 410       }
 411     }
 412   }
 413   /* not found */
 414   return 1;
 415 }
 416
 417 /* Decompose the given bitmap into paths. Returns a linked list of
 418    path_t objects with the fields len, pt, area, sign filled
 419    in. Returns 0 on success with plistp set, or -1 on error with errno
 420    set. */
 421
 422 int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress) {
 423   int x;
 424   int y;
 425   path_t *p;
 426   path_t *plist = NULL;  /* linked list of path objects */
 427   path_t **hook = &plist;  /* used to speed up appending to linked list */
 428   potrace_bitmap_t *bm1 = NULL;
 429   int sign;
 430
 431   bm1 = bm_dup(bm);
 432   if (!bm1) {
 433     goto error;
 434   }
 435
 436   /* be sure the byte padding on the right is set to 0, as the fast
 437      pixel search below relies on it */
 438   bm_clearexcess(bm1);
 439
 440   /* iterate through components */
 441   y = bm1->h - 1;
 442   while (findnext(bm1, &x, &y) == 0) {
 443     /* calculate the sign by looking at the original */
 444     sign = BM_GET(bm, x, y) ? '+' : '-';
 445
 446     /* calculate the path */
 447     p = findpath(bm1, x, y+1, sign, param->turnpolicy);
 448     if (p==NULL) {
 449       goto error;
 450     }
 451
 452     /* update buffered image */
 453     xor_path(bm1, p);
 454
 455     /* if it's a turd, eliminate it, else append it to the list */
 456     if (p->area <= param->turdsize) {
 457       path_free(p);
 458     } else {
 459       list_insert_beforehook(p, hook);
 460     }
 461
 462     if (bm1->h > 0) { /* to be sure */
 463       progress_update(1-y/(double)bm1->h, progress);
 464     }
 465   }
 466
 467   pathlist_to_tree(plist, bm1);
 468   bm_free(bm1);
 469   *plistp = plist;
 470
 471   progress_update(1.0, progress);
 472
 473   return 0;
 474
 475  error:
 476   bm_free(bm1);
 477   list_forall_unlink(p, plist) {
 478     path_free(p);
 479   }
 480   return -1;
 481 }