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
detrand(int x,int y)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 */
bm_clearexcess(potrace_bitmap_t * bm)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) */
clear_bm_with_bbox(potrace_bitmap_t * bm,bbox_t * bbox)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. */
majority(potrace_bitmap_t * bm,int x,int y)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. */
xor_to_ref(potrace_bitmap_t * bm,int x,int y,int xa)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. */
xor_path(potrace_bitmap_t * bm,path_t * p)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. */
setbbox_path(bbox_t * bbox,path_t * p)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. */
findpath(potrace_bitmap_t * bm,int x0,int y0,int sign,int turnpolicy)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
pathlist_to_tree(path_t * plist,potrace_bitmap_t * bm)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. */
findnext(potrace_bitmap_t * bm,int * xp,int * yp)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
bm_to_pathlist(const potrace_bitmap_t * bm,path_t ** plistp,const potrace_param_t * param,progress_t * progress)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 }
639