decompose.c
Go to the documentation of this file.
00001 /* Copyright (C) 2001-2007 Peter Selinger.
00002    This file is part of Potrace. It is free software and it is covered
00003    by the GNU General Public License. See the file COPYING for details. */
00004 
00005 /* $Id: decompose.c 146 2007-04-09 00:43:46Z selinger $ */
00006 
00007 #include <stdio.h>
00008 #include <stdlib.h>
00009 #include <string.h>
00010 #include <limits.h>
00011 
00012 #include "potracelib.h"
00013 #include "curve.h"
00014 #include "lists.h"
00015 #include "auxiliary.h"
00016 #include "bitmap.h"
00017 #include "decompose.h"
00018 #include "progress.h"
00019 
00020 /* ---------------------------------------------------------------------- */
00021 /* auxiliary bitmap manipulations */
00022 
00023 /* set the excess padding to 0 */
00024 static void bm_clearexcess(potrace_bitmap_t *bm) {
00025   potrace_word mask;
00026   int y;
00027 
00028   if (bm->w % BM_WORDBITS != 0) {
00029     mask = BM_ALLBITS << (BM_WORDBITS - (bm->w % BM_WORDBITS));
00030     for (y=0; y<bm->h; y++) {
00031       *bm_index(bm, bm->w, y) &= mask;
00032     }
00033   }
00034 }
00035 
00036 struct bbox_s {
00037   int x0, x1, y0, y1;    /* bounding box */
00038 };
00039 typedef struct bbox_s bbox_t;
00040 
00041 /* clear the bm, assuming the bounding box is set correctly (faster
00042    than clearing the whole bitmap) */
00043 static void clear_bm_with_bbox(potrace_bitmap_t *bm, bbox_t *bbox) {
00044   int imin = (bbox->x0 / BM_WORDBITS);
00045   int imax = ((bbox->x1 + BM_WORDBITS-1) / BM_WORDBITS);
00046   int i, y;
00047 
00048   for (y=bbox->y0; y<bbox->y1; y++) {
00049     for (i=imin; i<imax; i++) {
00050       bm_scanline(bm, y)[i] = 0;
00051     }
00052   }
00053 }
00054 
00055 /* ---------------------------------------------------------------------- */
00056 /* auxiliary functions */
00057 
00058 /* deterministically and efficiently hash (x,y) into a pseudo-random bit */
00059 static inline int detrand(int x, int y) {
00060   unsigned int z;
00061   static const unsigned char t[256] = { 
00062     /* non-linear sequence: constant term of inverse in GF(8), 
00063        mod x^8+x^4+x^3+x+1 */
00064     0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 
00065     0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 
00066     0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 
00067     1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 
00068     0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 
00069     0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 
00070     0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 
00071     0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 
00072     1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 
00073     0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 
00074     1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 
00075   };
00076 
00077   /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible
00078      5-bit sequence */
00079   z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93;
00080   z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff];
00081   return z & 1;
00082 }
00083 
00084 /* return the "majority" value of bitmap bm at intersection (x,y). We
00085    assume that the bitmap is balanced at "radius" 1.  */
00086 static int majority(potrace_bitmap_t *bm, int x, int y) {
00087   int i, a, ct;
00088 
00089   for (i=2; i<5; i++) { /* check at "radius" i */
00090     ct = 0;
00091     for (a=-i+1; a<=i-1; a++) {
00092       ct += BM_GET(bm, x+a, y+i-1) ? 1 : -1;
00093       ct += BM_GET(bm, x+i-1, y+a-1) ? 1 : -1;
00094       ct += BM_GET(bm, x+a-1, y-i) ? 1 : -1;
00095       ct += BM_GET(bm, x-i, y+a) ? 1 : -1;
00096     }
00097     if (ct>0) {
00098       return 1;
00099     } else if (ct<0) {
00100       return 0;
00101     }
00102   }
00103   return 0;
00104 }
00105 
00106 /* ---------------------------------------------------------------------- */
00107 /* decompose image into paths */
00108 
00109 /* efficiently invert bits [x,infty) and [xa,infty) in line y. Here xa
00110    must be a multiple of BM_WORDBITS. */
00111 static void xor_to_ref(potrace_bitmap_t *bm, int x, int y, int xa) {
00112   int xhi = x & -BM_WORDBITS;
00113   int xlo = x & (BM_WORDBITS-1);  /* = x % BM_WORDBITS */
00114   int i;
00115   
00116   if (xhi<xa) {
00117     for (i = xhi; i < xa; i+=BM_WORDBITS) {
00118       *bm_index(bm, i, y) ^= BM_ALLBITS;
00119     }
00120   } else {
00121     for (i = xa; i < xhi; i+=BM_WORDBITS) {
00122       *bm_index(bm, i, y) ^= BM_ALLBITS;
00123     }
00124   }
00125   /* note: the following "if" is needed because x86 treats a<<b as
00126      a<<(b&31). I spent hours looking for this bug. */
00127   if (xlo) {
00128     *bm_index(bm, xhi, y) ^= (BM_ALLBITS << (BM_WORDBITS - xlo));
00129   }
00130 }
00131 
00132 /* a path is represented as an array of points, which are thought to
00133    lie on the corners of pixels (not on their centers). The path point
00134    (x,y) is the lower left corner of the pixel (x,y). Paths are
00135    represented by the len/pt components of a path_t object (which
00136    also stores other information about the path) */
00137 
00138 /* xor the given pixmap with the interior of the given path. Note: the
00139    path must be within the dimensions of the pixmap. */
00140 static void xor_path(potrace_bitmap_t *bm, path_t *p) {
00141   int xa, x, y, k, y1;
00142 
00143   if (p->priv->len <= 0) {  /* a path of length 0 is silly, but legal */
00144     return;
00145   }
00146 
00147   y1 = p->priv->pt[p->priv->len-1].y;
00148 
00149   xa = p->priv->pt[0].x & -BM_WORDBITS;
00150   for (k=0; k<p->priv->len; k++) {
00151     x = p->priv->pt[k].x;
00152     y = p->priv->pt[k].y;
00153 
00154     if (y != y1) {
00155       /* efficiently invert the rectangle [x,xa] x [y,y1] */
00156       xor_to_ref(bm, x, min(y,y1), xa);
00157       y1 = y;
00158     }
00159   }
00160 }
00161 
00162 /* Find the bounding box of a given path. Path is assumed to be of
00163    non-zero length. */
00164 static void setbbox_path(bbox_t *bbox, path_t *p) {
00165   int x, y;
00166   int k;
00167 
00168   bbox->y0 = INT_MAX;
00169   bbox->y1 = 0;
00170   bbox->x0 = INT_MAX;
00171   bbox->x1 = 0;
00172 
00173   for (k=0; k<p->priv->len; k++) {
00174     x = p->priv->pt[k].x;
00175     y = p->priv->pt[k].y;
00176 
00177     if (x < bbox->x0) {
00178       bbox->x0 = x;
00179     }
00180     if (x > bbox->x1) {
00181       bbox->x1 = x;
00182     }
00183     if (y < bbox->y0) {
00184       bbox->y0 = y;
00185     }
00186     if (y > bbox->y1) {
00187       bbox->y1 = y;
00188     }
00189   }
00190 }
00191 
00192 /* compute a path in the given pixmap, separating black from white.
00193    Start path at the point (x0,x1), which must be an upper left corner
00194    of the path. Also compute the area enclosed by the path. Return a
00195    new path_t object, or NULL on error (note that a legitimate path
00196    cannot have length 0). Sign is required for correct interpretation
00197    of turnpolicies. */
00198 static path_t *findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy) {
00199   int x, y, dirx, diry, len, size, area;
00200   int c, d, tmp;
00201   point_t *pt, *pt1;
00202   path_t *p = NULL;
00203 
00204   x = x0;
00205   y = y0;
00206   dirx = 0;
00207   diry = -1;
00208 
00209   len = size = 0;
00210   pt = NULL;
00211   area = 0;
00212   
00213   while (1) {
00214     /* add point to path */
00215     if (len>=size) {
00216       size += 100;
00217       size = (int)(1.3 * size);
00218       pt1 = (point_t *)realloc(pt, size * sizeof(point_t));
00219       if (!pt1) {
00220         goto error;
00221       }
00222       pt = pt1;
00223     }
00224     pt[len].x = x;
00225     pt[len].y = y;
00226     len++;
00227     
00228     /* move to next point */
00229     x += dirx;
00230     y += diry;
00231     area += x*diry;
00232     
00233     /* path complete? */
00234     if (x==x0 && y==y0) {
00235       break;
00236     }
00237     
00238     /* determine next direction */
00239     c = BM_GET(bm, x + (dirx+diry-1)/2, y + (diry-dirx-1)/2);
00240     d = BM_GET(bm, x + (dirx-diry-1)/2, y + (diry+dirx-1)/2);
00241     
00242     if (c && !d) {               /* ambiguous turn */
00243       if (turnpolicy == POTRACE_TURNPOLICY_RIGHT
00244           || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+')
00245           || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-')
00246           || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand(x,y))
00247           || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y))
00248           || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) {
00249         tmp = dirx;              /* right turn */
00250         dirx = diry;
00251         diry = -tmp;
00252       } else {
00253         tmp = dirx;              /* left turn */
00254         dirx = -diry;
00255         diry = tmp;
00256       }
00257     } else if (c) {              /* right turn */
00258       tmp = dirx;
00259       dirx = diry;
00260       diry = -tmp;
00261     } else if (!d) {             /* left turn */
00262       tmp = dirx;
00263       dirx = -diry;
00264       diry = tmp;
00265     }
00266   } /* while this path */
00267 
00268   /* allocate new path object */
00269   p = path_new();
00270   if (!p) {
00271     goto error;
00272   }
00273 
00274   p->priv->pt = pt;
00275   p->priv->len = len;
00276   p->area = area;
00277   p->sign = sign;
00278 
00279   return p;
00280  
00281  error:
00282    free(pt);
00283    return NULL; 
00284 }
00285 
00286 /* Give a tree structure to the given path list, based on "insideness"
00287    testing. I.e., path A is considered "below" path B if it is inside
00288    path B. The input pathlist is assumed to be ordered so that "outer"
00289    paths occur before "inner" paths. The tree structure is stored in
00290    the "childlist" and "sibling" components of the path_t
00291    structure. The linked list structure is also changed so that
00292    negative path components are listed immediately after their
00293    positive parent.  Note: some backends may ignore the tree
00294    structure, others may use it e.g. to group path components. We
00295    assume that in the input, point 0 of each path is an "upper left"
00296    corner of the path, as returned by bm_to_pathlist. This makes it
00297    easy to find an "interior" point. The bm argument should be a
00298    bitmap of the correct size (large enough to hold all the paths),
00299    and will be used as scratch space. Return 0 on success or -1 on
00300    error with errno set. */
00301 
00302 static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) {
00303   path_t *p, *p1;
00304   path_t *heap, *heap1;
00305   path_t *cur;
00306   path_t *head;
00307   path_t **hook, **hook_in, **hook_out; /* for fast appending to linked list */
00308   bbox_t bbox;
00309   
00310   bm_clear(bm, 0);
00311 
00312   /* save original "next" pointers */
00313   list_forall(p, plist) {
00314     p->sibling = p->next;
00315     p->childlist = NULL;
00316   }
00317   
00318   heap = plist;
00319 
00320   /* the heap holds a list of lists of paths. Use "childlist" field
00321      for outer list, "next" field for inner list. Each of the sublists
00322      is to be turned into a tree. This code is messy, but it is
00323      actually fast. Each path is rendered exactly once. We use the
00324      heap to get a tail recursive algorithm: the heap holds a list of
00325      pathlists which still need to be transformed. */
00326 
00327   while (heap) {
00328     /* unlink first sublist */
00329     cur = heap;
00330     heap = heap->childlist;
00331     cur->childlist = NULL;
00332   
00333     /* unlink first path */
00334     head = cur;
00335     cur = cur->next;
00336     head->next = NULL;
00337 
00338     /* render path */
00339     xor_path(bm, head);
00340     setbbox_path(&bbox, head);
00341 
00342     /* now do insideness test for each element of cur; append it to
00343        head->childlist if it's inside head, else append it to
00344        head->next. */
00345     hook_in=&head->childlist;
00346     hook_out=&head->next;
00347     list_forall_unlink(p, cur) {
00348       if (p->priv->pt[0].y <= bbox.y0) {
00349         list_insert_beforehook(p, hook_out);
00350         /* append the remainder of the list to hook_out */
00351         *hook_out = cur;
00352         break;
00353       }
00354       if (BM_GET(bm, p->priv->pt[0].x, p->priv->pt[0].y-1)) {
00355         list_insert_beforehook(p, hook_in);
00356       } else {
00357         list_insert_beforehook(p, hook_out);
00358       }
00359     }
00360 
00361     /* clear bm */
00362     clear_bm_with_bbox(bm, &bbox);
00363 
00364     /* now schedule head->childlist and head->next for further
00365        processing */
00366     if (head->next) {
00367       head->next->childlist = heap;
00368       heap = head->next;
00369     }
00370     if (head->childlist) {
00371       head->childlist->childlist = heap;
00372       heap = head->childlist;
00373     }
00374   }
00375   
00376   /* copy sibling structure from "next" to "sibling" component */
00377   p = plist;
00378   while (p) {
00379     p1 = p->sibling;
00380     p->sibling = p->next;
00381     p = p1;
00382   }
00383 
00384   /* reconstruct a new linked list ("next") structure from tree
00385      ("childlist", "sibling") structure. This code is slightly messy,
00386      because we use a heap to make it tail recursive: the heap
00387      contains a list of childlists which still need to be
00388      processed. */
00389   heap = plist;
00390   if (heap) {
00391     heap->next = NULL;  /* heap is a linked list of childlists */
00392   }
00393   plist = NULL;
00394   hook = &plist;
00395   while (heap) {
00396     heap1 = heap->next;
00397     for (p=heap; p; p=p->sibling) {
00398       /* p is a positive path */
00399       /* append to linked list */
00400       list_insert_beforehook(p, hook);
00401       
00402       /* go through its children */
00403       for (p1=p->childlist; p1; p1=p1->sibling) {
00404         /* append to linked list */
00405         list_insert_beforehook(p1, hook);
00406         /* append its childlist to heap, if non-empty */
00407         if (p1->childlist) {
00408           list_append(path_t, heap1, p1->childlist);
00409         }
00410       }
00411     }
00412     heap = heap1;
00413   }
00414 
00415   return;
00416 }
00417 
00418 /* find the next set pixel in a row <= y. Pixels are searched first
00419    left-to-right, then top-down. In other words, (x,y)<(x',y') if y>y'
00420    or y=y' and x<x'. If found, return 0 and store pixel in
00421    (*xp,*yp). Else return 1. Note that this function assumes that
00422    excess bytes have been cleared with bm_clearexcess. */
00423 static int findnext(potrace_bitmap_t *bm, int *xp, int *yp) {
00424   int x;
00425   int y;
00426 
00427   for (y=*yp; y>=0; y--) {
00428     for (x=0; x<bm->w; x+=BM_WORDBITS) {
00429       if (*bm_index(bm, x, y)) {
00430         while (!BM_GET(bm, x, y)) {
00431           x++;
00432         }
00433         /* found */
00434         *xp = x;
00435         *yp = y;
00436         return 0;
00437       }
00438     }
00439   }
00440   /* not found */
00441   return 1;
00442 }
00443 
00444 /* Decompose the given bitmap into paths. Returns a linked list of
00445    path_t objects with the fields len, pt, area, sign filled
00446    in. Returns 0 on success with plistp set, or -1 on error with errno
00447    set. */
00448 
00449 int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress) {
00450   int x;
00451   int y;
00452   path_t *p;
00453   path_t *plist = NULL;  /* linked list of path objects */
00454   path_t **hook = &plist;  /* used to speed up appending to linked list */
00455   potrace_bitmap_t *bm1 = NULL;
00456   int sign;
00457 
00458   bm1 = bm_dup(bm);
00459   if (!bm1) {
00460     goto error;
00461   }
00462 
00463   /* be sure the byte padding on the right is set to 0, as the fast
00464      pixel search below relies on it */
00465   bm_clearexcess(bm1);
00466 
00467   /* iterate through components */
00468   y = bm1->h - 1;
00469   while (findnext(bm1, &x, &y) == 0) { 
00470     /* calculate the sign by looking at the original */
00471     sign = BM_GET(bm, x, y) ? '+' : '-';
00472 
00473     /* calculate the path */
00474     p = findpath(bm1, x, y+1, sign, param->turnpolicy);
00475     if (p==NULL) {
00476       goto error;
00477     }
00478 
00479     /* update buffered image */
00480     xor_path(bm1, p);
00481 
00482     /* if it's a turd, eliminate it, else append it to the list */
00483     if (p->area <= param->turdsize) {
00484       path_free(p);
00485     } else {
00486       list_insert_beforehook(p, hook);
00487     }
00488 
00489     if (bm1->h > 0) { /* to be sure */
00490       progress_update(1-y/(double)bm1->h, progress);
00491     }
00492   }
00493 
00494   pathlist_to_tree(plist, bm1);
00495   bm_free(bm1);
00496   *plistp = plist;
00497 
00498   progress_update(1.0, progress);
00499 
00500   return 0;
00501 
00502  error:
00503   bm_free(bm1);
00504   list_forall_unlink(p, plist) {
00505     path_free(p);
00506   }
00507   return -1;
00508 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines


portrait_painter
Author(s): Niklas Meinzer, Ina Baumgarten
autogenerated on Wed Dec 26 2012 16:00:43