gvsig-raster / libjni-potrace / trunk / libjni-potrace / src / main / native / jpotrace / decompose.c @ 1780
History | View | Annotate | Download (13.9 KB)
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. */
|
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 |
} |