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