gvsig-raster / libjni-potrace / trunk / libjni-potrace / src / main / native / jpotrace / decompose.c @ 1780
History | View | Annotate | Download (13.9 KB)
1 | 1780 | nbrodin | /* 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. */
|
||
4 | |||
5 | /* $Id: decompose.c 146 2007-04-09 00:43:46Z selinger $ */
|
||
6 | |||
7 | #include <stdio.h> |
||
8 | #include <stdlib.h> |
||
9 | #include <string.h> |
||
10 | #include <limits.h> |
||
11 | |||
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" |
||
19 | |||
20 | /* ---------------------------------------------------------------------- */
|
||
21 | /* auxiliary bitmap manipulations */
|
||
22 | |||
23 | /* set the excess padding to 0 */
|
||
24 | static void bm_clearexcess(potrace_bitmap_t *bm) { |
||
25 | potrace_word mask; |
||
26 | int y;
|
||
27 | |||
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 | } |
||
35 | |||
36 | struct bbox_s {
|
||
37 | int x0, x1, y0, y1; /* bounding box */ |
||
38 | }; |
||
39 | typedef struct bbox_s bbox_t; |
||
40 | |||
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;
|
||
47 | |||
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 | } |
||
54 | |||
55 | /* ---------------------------------------------------------------------- */
|
||
56 | /* auxiliary functions */
|
||
57 | |||
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 | }; |
||
76 | |||
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 | } |
||
83 | |||
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;
|
||
88 | |||
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 | } |
||
105 | |||
106 | /* ---------------------------------------------------------------------- */
|
||
107 | /* decompose image into paths */
|
||
108 | |||
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;
|
||
115 | |||
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 | } |
||
131 | |||
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) */
|
||
137 | |||
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;
|
||
142 | |||
143 | if (p->priv->len <= 0) { /* a path of length 0 is silly, but legal */ |
||
144 | return;
|
||
145 | } |
||
146 | |||
147 | y1 = p->priv->pt[p->priv->len-1].y;
|
||
148 | |||
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; |
||
153 | |||
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 | } |
||
161 | |||
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;
|
||
167 | |||
168 | bbox->y0 = INT_MAX; |
||
169 | bbox->y1 = 0;
|
||
170 | bbox->x0 = INT_MAX; |
||
171 | bbox->x1 = 0;
|
||
172 | |||
173 | for (k=0; k<p->priv->len; k++) { |
||
174 | x = p->priv->pt[k].x; |
||
175 | y = p->priv->pt[k].y; |
||
176 | |||
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 | } |
||
191 | |||
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;
|
||
203 | |||
204 | x = x0; |
||
205 | y = y0; |
||
206 | dirx = 0;
|
||
207 | diry = -1;
|
||
208 | |||
209 | len = size = 0;
|
||
210 | pt = NULL;
|
||
211 | area = 0;
|
||
212 | |||
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++; |
||
227 | |||
228 | /* move to next point */
|
||
229 | x += dirx; |
||
230 | y += diry; |
||
231 | area += x*diry; |
||
232 | |||
233 | /* path complete? */
|
||
234 | if (x==x0 && y==y0) {
|
||
235 | break;
|
||
236 | } |
||
237 | |||
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); |
||
241 | |||
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 */
|
||
267 | |||
268 | /* allocate new path object */
|
||
269 | p = path_new(); |
||
270 | if (!p) {
|
||
271 | goto error;
|
||
272 | } |
||
273 | |||
274 | p->priv->pt = pt; |
||
275 | p->priv->len = len; |
||
276 | p->area = area; |
||
277 | p->sign = sign; |
||
278 | |||
279 | return p;
|
||
280 | |||
281 | error:
|
||
282 | free(pt); |
||
283 | return NULL; |
||
284 | } |
||
285 | |||
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. */
|
||
301 | |||
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; |
||
309 | |||
310 | bm_clear(bm, 0);
|
||
311 | |||
312 | /* save original "next" pointers */
|
||
313 | list_forall(p, plist) { |
||
314 | p->sibling = p->next; |
||
315 | p->childlist = NULL;
|
||
316 | } |
||
317 | |||
318 | heap = plist; |
||
319 | |||
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. */
|
||
326 | |||
327 | while (heap) {
|
||
328 | /* unlink first sublist */
|
||
329 | cur = heap; |
||
330 | heap = heap->childlist; |
||
331 | cur->childlist = NULL;
|
||
332 | |||
333 | /* unlink first path */
|
||
334 | head = cur; |
||
335 | cur = cur->next; |
||
336 | head->next = NULL;
|
||
337 | |||
338 | /* render path */
|
||
339 | xor_path(bm, head); |
||
340 | setbbox_path(&bbox, head); |
||
341 | |||
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 | } |
||
360 | |||
361 | /* clear bm */
|
||
362 | clear_bm_with_bbox(bm, &bbox); |
||
363 | |||
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 | } |
||
375 | |||
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 | } |
||
383 | |||
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); |
||
401 | |||
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 | } |
||
414 | |||
415 | return;
|
||
416 | } |
||
417 | |||
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;
|
||
426 | |||
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 | } |
||
443 | |||
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. */
|
||
448 | |||
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;
|
||
457 | |||
458 | bm1 = bm_dup(bm); |
||
459 | if (!bm1) {
|
||
460 | goto error;
|
||
461 | } |
||
462 | |||
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); |
||
466 | |||
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) ? '+' : '-'; |
||
472 | |||
473 | /* calculate the path */
|
||
474 | p = findpath(bm1, x, y+1, sign, param->turnpolicy);
|
||
475 | if (p==NULL) { |
||
476 | goto error;
|
||
477 | } |
||
478 | |||
479 | /* update buffered image */
|
||
480 | xor_path(bm1, p); |
||
481 | |||
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 | } |
||
488 | |||
489 | if (bm1->h > 0) { /* to be sure */ |
||
490 | progress_update(1-y/(double)bm1->h, progress); |
||
491 | } |
||
492 | } |
||
493 | |||
494 | pathlist_to_tree(plist, bm1); |
||
495 | bm_free(bm1); |
||
496 | *plistp = plist; |
||
497 | |||
498 | progress_update(1.0, progress); |
||
499 | |||
500 | return 0; |
||
501 | |||
502 | error:
|
||
503 | bm_free(bm1); |
||
504 | list_forall_unlink(p, plist) { |
||
505 | path_free(p); |
||
506 | } |
||
507 | return -1; |
||
508 | } |