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