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