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