From 9b3424d16d013c8b529dc32ca112e56f1cfe3208 Mon Sep 17 00:00:00 2001 From: ishmal Date: Fri, 26 Oct 2007 21:01:30 +0000 Subject: [PATCH] Update Potrace to 1.8 --- src/trace/.cvsignore | 4 -- src/trace/potrace/.cvsignore | 3 -- src/trace/potrace/auxiliary.h | 22 +++++++- src/trace/potrace/bitmap.h | 8 ++- src/trace/potrace/curve.cpp | 26 +++++----- src/trace/potrace/curve.h | 9 ++-- src/trace/potrace/decompose.cpp | 71 +++++++++++++++++--------- src/trace/potrace/decompose.h | 5 +- src/trace/potrace/greymap.cpp | 8 +-- src/trace/potrace/greymap.h | 4 +- src/trace/potrace/lists.h | 4 +- src/trace/potrace/potracelib.cpp | 25 ++++++---- src/trace/potrace/potracelib.h | 12 ++--- src/trace/potrace/progress.h | 4 +- src/trace/potrace/render.cpp | 6 ++- src/trace/potrace/render.h | 4 +- src/trace/potrace/trace.cpp | 86 ++++++++++++++++---------------- src/trace/potrace/trace.h | 4 +- 18 files changed, 174 insertions(+), 131 deletions(-) delete mode 100644 src/trace/.cvsignore delete mode 100644 src/trace/potrace/.cvsignore diff --git a/src/trace/.cvsignore b/src/trace/.cvsignore deleted file mode 100644 index 47c85e026..000000000 --- a/src/trace/.cvsignore +++ /dev/null @@ -1,4 +0,0 @@ -.deps -.dirstamp -makefile - diff --git a/src/trace/potrace/.cvsignore b/src/trace/potrace/.cvsignore deleted file mode 100644 index 16e013378..000000000 --- a/src/trace/potrace/.cvsignore +++ /dev/null @@ -1,3 +0,0 @@ -.deps -.dirstamp - diff --git a/src/trace/potrace/auxiliary.h b/src/trace/potrace/auxiliary.h index 18573ad53..7baab851c 100644 --- a/src/trace/potrace/auxiliary.h +++ b/src/trace/potrace/auxiliary.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* This header file collects some general-purpose macros (and static @@ -8,6 +8,10 @@ #ifndef AUXILIARY_H #define AUXILIARY_H +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + /* ---------------------------------------------------------------------- */ /* point arithmetic */ @@ -39,6 +43,14 @@ static inline dpoint_t interval(double lambda, dpoint_t a, dpoint_t b) { } /* ---------------------------------------------------------------------- */ +/* some useful macros. Note: the "mod" macro works correctly for + negative a. Also note that the test for a>=n, while redundant, + speeds up the mod function by 70% in the average case (significant + since the program spends about 16% of its time here - or 40% + without the test). The "floordiv" macro returns the largest integer + <= a/n, and again this works correctly for negative a, as long as + a,n are integers and n>0. */ + /* integer arithmetic */ static inline int mod(int a, int n) { @@ -50,6 +62,12 @@ static inline int floordiv(int a, int n) { } /* Note: the following work for integers and other numeric types. */ +#undef sign +#undef abs +#undef min +#undef max +#undef sq +#undef cu #define sign(x) ((x)>0 ? 1 : (x)<0 ? -1 : 0) #define abs(a) ((a)>0 ? (a) : -(a)) #define min(a,b) ((a)<(b) ? (a) : (b)) diff --git a/src/trace/potrace/bitmap.h b/src/trace/potrace/bitmap.h index f55762f28..2a172b1ad 100644 --- a/src/trace/potrace/bitmap.h +++ b/src/trace/potrace/bitmap.h @@ -1,10 +1,14 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ #ifndef BITMAP_H #define BITMAP_H +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + #include #include diff --git a/src/trace/potrace/curve.cpp b/src/trace/potrace/curve.cpp index 89b6ee5fd..c9a6fbe04 100644 --- a/src/trace/potrace/curve.cpp +++ b/src/trace/potrace/curve.cpp @@ -1,13 +1,15 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ /* private part of the path and curve data structures */ +#include #include #include +#include "potracelib.h" #include "lists.h" #include "curve.h" @@ -34,6 +36,16 @@ path_t *path_new(void) { return NULL; } +/* free the members of the given curve structure. Leave errno unchanged. */ +static void privcurve_free_members(privcurve_t *curve) { + free(curve->tag); + free(curve->c); + free(curve->vertex); + free(curve->alpha); + free(curve->alpha0); + free(curve->beta); +} + /* free a path. Leave errno untouched. */ void path_free(path_t *p) { if (p) { @@ -88,16 +100,6 @@ int privcurve_init(privcurve_t *curve, int n) { return 1; } -/* free the members of the given curve structure */ -void privcurve_free_members(privcurve_t *curve) { - free(curve->tag); - free(curve->c); - free(curve->vertex); - free(curve->alpha); - free(curve->alpha0); - free(curve->beta); -} - /* copy private to public curve structure */ void privcurve_to_curve(privcurve_t *pc, potrace_curve_t *c) { c->n = pc->n; diff --git a/src/trace/potrace/curve.h b/src/trace/potrace/curve.h index 574433518..45c0790be 100644 --- a/src/trace/potrace/curve.h +++ b/src/trace/potrace/curve.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ #ifndef CURVE_H @@ -18,7 +18,7 @@ struct privcurve_s { int n; /* number of segments */ int *tag; /* tag[n]: POTRACE_CORNER or POTRACE_CURVETO */ - dpoint_t (*c)[3]; /* c[n][i]: control points. + dpoint_t (*c)[3]; /* c[n][i]: control points. c[n][0] is unused for tag[n]=POTRACE_CORNER */ /* the remainder of this structure is special to privcurve, and is used in EPS debug output and special EPS "short coding". These @@ -42,7 +42,7 @@ typedef struct sums_s sums_t; /* the path structure is filled in with information about a given path as it is accumulated and passed through the different stages of the - potrace algorithm. Backends only need to read the fcurve and fm + Potrace algorithm. Backends only need to read the fcurve and fm fields of this data structure, but debugging backends may read other fields. */ struct potrace_privpath_s { @@ -71,7 +71,6 @@ path_t *path_new(void); void path_free(path_t *p); void pathlist_free(path_t *plist); int privcurve_init(privcurve_t *curve, int n); -void privcurve_free_members(privcurve_t *curve); void privcurve_to_curve(privcurve_t *pc, potrace_curve_t *c); #endif /* CURVE_H */ diff --git a/src/trace/potrace/decompose.cpp b/src/trace/potrace/decompose.cpp index 512d9f4fe..15c39825e 100644 --- a/src/trace/potrace/decompose.cpp +++ b/src/trace/potrace/decompose.cpp @@ -1,15 +1,21 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ +#include #include +#include #include +#include "potracelib.h" +#include "curve.h" #include "lists.h" +#include "auxiliary.h" #include "bitmap.h" #include "decompose.h" +#include "progress.h" /* ---------------------------------------------------------------------- */ /* auxiliary bitmap manipulations */ @@ -49,10 +55,30 @@ static void clear_bm_with_bbox(potrace_bitmap_t *bm, bbox_t *bbox) { /* ---------------------------------------------------------------------- */ /* auxiliary functions */ -/* return a "random" value which deterministically depends on x,y */ +/* deterministically and efficiently hash (x,y) into a pseudo-random bit */ static inline int detrand(int x, int y) { - srand(x+123456789*y); - return rand(); + unsigned int z; + static const unsigned char t[256] = { + /* non-linear sequence: constant term of inverse in GF(8), + mod x^8+x^4+x^3+x+1 */ + 0, 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, 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, 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, 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, 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, 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, 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, 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, 0, 1, 0, 1, 0, 1, 0, + }; + + /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible + 5-bit sequence */ + z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93; + z = t[z & 0xff] ^ t[(z>>8) & 0xff] ^ t[(z>>16) & 0xff] ^ t[(z>>24) & 0xff]; + return z & 1; } /* return the "majority" value of bitmap bm at intersection (x,y). We @@ -86,7 +112,7 @@ static void xor_to_ref(potrace_bitmap_t *bm, int x, int y, int xa) { int xhi = x & -BM_WORDBITS; int xlo = x & (BM_WORDBITS-1); /* = x % BM_WORDBITS */ int i; - + if (xhi=size) { - size+=100; - //size*=1.3; - size = size * 13 / 10; + size += 100; + size = (int)(1.3 * size); pt1 = (point_t *)realloc(pt, size * sizeof(point_t)); if (!pt1) { goto error; @@ -199,26 +224,26 @@ static path_t *findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turn pt[len].x = x; pt[len].y = y; len++; - + /* move to next point */ x += dirx; y += diry; area += x*diry; - + /* path complete? */ if (x==x0 && y==y0) { break; } - + /* determine next direction */ c = BM_GET(bm, x + (dirx+diry-1)/2, y + (diry-dirx-1)/2); d = BM_GET(bm, x + (dirx-diry-1)/2, y + (diry+dirx-1)/2); - + if (c && !d) { /* ambiguous turn */ if (turnpolicy == POTRACE_TURNPOLICY_RIGHT || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+') || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-') - || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && (detrand(x,y) & 1)) + || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand(x,y)) || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y)) || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) { tmp = dirx; /* right turn */ @@ -252,10 +277,10 @@ static path_t *findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turn p->sign = sign; return p; - + error: free(pt); - return NULL; + return NULL; } /* Give a tree structure to the given path list, based on "insideness" @@ -281,7 +306,7 @@ static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) { path_t *head; path_t **hook, **hook_in, **hook_out; /* for fast appending to linked list */ bbox_t bbox; - + bm_clear(bm, 0); /* save original "next" pointers */ @@ -289,7 +314,7 @@ static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) { p->sibling = p->next; p->childlist = NULL; } - + heap = plist; /* the heap holds a list of lists of paths. Use "childlist" field @@ -304,7 +329,7 @@ static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) { cur = heap; heap = heap->childlist; cur->childlist = NULL; - + /* unlink first path */ head = cur; cur = cur->next; @@ -347,7 +372,7 @@ static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) { heap = head->childlist; } } - + /* copy sibling structure from "next" to "sibling" component */ p = plist; while (p) { @@ -373,7 +398,7 @@ static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) { /* p is a positive path */ /* append to linked list */ list_insert_beforehook(p, hook); - + /* go through its children */ for (p1=p->childlist; p1; p1=p1->sibling) { /* append to linked list */ @@ -441,7 +466,7 @@ int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_pa /* iterate through components */ y = bm1->h - 1; - while (findnext(bm1, &x, &y) == 0) { + while (findnext(bm1, &x, &y) == 0) { /* calculate the sign by looking at the original */ sign = BM_GET(bm, x, y) ? '+' : '-'; diff --git a/src/trace/potrace/decompose.h b/src/trace/potrace/decompose.h index 346b7866a..5552fa0a1 100644 --- a/src/trace/potrace/decompose.h +++ b/src/trace/potrace/decompose.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ @@ -8,7 +8,6 @@ #define DECOMPOSE_H #include "potracelib.h" -#include "curve.h" #include "progress.h" int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress); diff --git a/src/trace/potrace/greymap.cpp b/src/trace/potrace/greymap.cpp index 7d46304cd..53c703aa4 100644 --- a/src/trace/potrace/greymap.cpp +++ b/src/trace/potrace/greymap.cpp @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ @@ -442,7 +442,7 @@ static int bmp_readint(FILE *f, int n, unsigned int *p) { } /* reset padding boundary */ -static void bmp_pad_reset() { +static void bmp_pad_reset(void) { bmp_count = 0; } @@ -488,7 +488,7 @@ static int bmp_forward(FILE *f, int pos) { although most specifications only allow 1,4,8,24,32. We can also read both the old and new OS/2 BMP formats in addition to the Windows BMP format. */ -int gm_readbody_bmp(FILE *f, greymap_t **gmp) { +static int gm_readbody_bmp(FILE *f, greymap_t **gmp) { bmp_info_t bmpinfo; int *coltable; unsigned int b, c; diff --git a/src/trace/potrace/greymap.h b/src/trace/potrace/greymap.h index 816566205..05e01667d 100644 --- a/src/trace/potrace/greymap.h +++ b/src/trace/potrace/greymap.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ diff --git a/src/trace/potrace/lists.h b/src/trace/potrace/lists.h index fe689e4c5..fc853398a 100644 --- a/src/trace/potrace/lists.h +++ b/src/trace/potrace/lists.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ diff --git a/src/trace/potrace/potracelib.cpp b/src/trace/potrace/potracelib.cpp index efd9b14d2..215d3b457 100644 --- a/src/trace/potrace/potracelib.cpp +++ b/src/trace/potrace/potracelib.cpp @@ -1,12 +1,15 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ #include #include +#include "potracelib.h" +#include "curve.h" #include "decompose.h" #include "trace.h" +#include "progress.h" #ifdef HAVE_CONFIG_H #include "config.h" @@ -29,7 +32,7 @@ static const potrace_param_t param_default = { /* Return a fresh copy of the set of default parameters, or NULL on failure with errno set. */ -potrace_param_t *potrace_param_default() { +potrace_param_t *potrace_param_default(void) { potrace_param_t *p; p = (potrace_param_t *) malloc(sizeof(potrace_param_t)); @@ -40,18 +43,18 @@ potrace_param_t *potrace_param_default() { return p; } -/* On success, returns a potrace state st with st->status == - POTRACE_STATUS_OK. On failure, returns NULL if no potrace state - could be created (with errno set), or returns an incomplete potrace +/* On success, returns a Potrace state st with st->status == + POTRACE_STATUS_OK. On failure, returns NULL if no Potrace state + could be created (with errno set), or returns an incomplete Potrace state (with st->status == POTRACE_STATUS_INCOMPLETE). Complete or - incomplete potrace state can be freed with potrace_state_free(). */ + incomplete Potrace state can be freed with potrace_state_free(). */ potrace_state_t *potrace_trace(const potrace_param_t *param, const potrace_bitmap_t *bm) { int r; path_t *plist = NULL; potrace_state_t *st; progress_t prog; progress_t subprog; - + /* prepare private progress bar state */ prog.callback = param->progress.callback; prog.data = param->progress.data; @@ -77,7 +80,7 @@ potrace_state_t *potrace_trace(const potrace_param_t *param, const potrace_bitma st->status = POTRACE_STATUS_OK; st->plist = plist; - st->priv = NULL; + st->priv = NULL; /* private state currently unused */ progress_subrange_end(&prog, &subprog); @@ -94,7 +97,7 @@ potrace_state_t *potrace_trace(const potrace_param_t *param, const potrace_bitma return st; } -/* free a potrace state, without disturbing errno. */ +/* free a Potrace state, without disturbing errno. */ void potrace_state_free(potrace_state_t *st) { pathlist_free(st->plist); free(st); @@ -105,6 +108,6 @@ void potrace_param_free(potrace_param_t *p) { free(p); } -char *potrace_version() { +char *potrace_version(void) { return "potracelib "VERSION""; } diff --git a/src/trace/potrace/potracelib.h b/src/trace/potrace/potracelib.h index 141f1d3be..0b93d65de 100644 --- a/src/trace/potrace/potracelib.h +++ b/src/trace/potrace/potracelib.h @@ -1,11 +1,11 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ #ifndef POTRACELIB_H #define POTRACELIB_H -/* this file defines the API for the core potrace library. For a more +/* this file defines the API for the core Potrace library. For a more detailed description of the API, see doc/potracelib.txt */ /* ---------------------------------------------------------------------- */ @@ -112,7 +112,7 @@ typedef struct potrace_state_s potrace_state_t; /* API functions */ /* get default parameters */ -potrace_param_t *potrace_param_default(); +potrace_param_t *potrace_param_default(void); /* free parameter set */ void potrace_param_free(potrace_param_t *p); @@ -121,11 +121,11 @@ void potrace_param_free(potrace_param_t *p); potrace_state_t *potrace_trace(const potrace_param_t *param, const potrace_bitmap_t *bm); -/* free a potrace state */ +/* free a Potrace state */ void potrace_state_free(potrace_state_t *st); /* return a static plain text version string identifying this version of potracelib */ -char *potrace_version(); +char *potrace_version(void); #endif /* POTRACELIB_H */ diff --git a/src/trace/potrace/progress.h b/src/trace/potrace/progress.h index 3f617c4d1..0e077430d 100644 --- a/src/trace/potrace/progress.h +++ b/src/trace/potrace/progress.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* operations on potrace_progress_t objects, which are defined in diff --git a/src/trace/potrace/render.cpp b/src/trace/potrace/render.cpp index 78b15fc60..f9183b931 100644 --- a/src/trace/potrace/render.cpp +++ b/src/trace/potrace/render.cpp @@ -1,14 +1,16 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ +#include #include #include #include #include "render.h" +#include "greymap.h" #include "auxiliary.h" /* ---------------------------------------------------------------------- */ diff --git a/src/trace/potrace/render.h b/src/trace/potrace/render.h index 0d3835c9e..9c9d921d2 100644 --- a/src/trace/potrace/render.h +++ b/src/trace/potrace/render.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ diff --git a/src/trace/potrace/trace.cpp b/src/trace/potrace/trace.cpp index ae9f756b0..909ffb712 100644 --- a/src/trace/potrace/trace.cpp +++ b/src/trace/potrace/trace.cpp @@ -1,15 +1,20 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ /* transform jaggy paths into smooth curves */ +#include #include #include +#include +#include "potracelib.h" #include "curve.h" #include "lists.h" +#include "auxiliary.h" +#include "trace.h" #include "progress.h" #define INFTY 10000000 /* it suffices that this is longer than any @@ -17,16 +22,8 @@ #define COS179 -0.999847695156 /* the cosine of 179 degrees */ /* ---------------------------------------------------------------------- */ -/* some useful macros. Note: the "mod" macro works correctly for - negative a. Also note that the test for a>=n, while redundant, - speeds up the mod function by 70% in the average case (significant - since the program spends about 16% of its time here - or 40% - without the test). The "floordiv" macro returns the largest integer - <= a/n, and again this works correctly for negative a, as long as - a,n are integers and n>0. */ - #define SAFE_MALLOC(var, n, typ) \ - if ((var = (typ *)malloc((n)*sizeof(typ))) == NULL) goto malloc_error + if ((var = (typ *)malloc((n)*sizeof(typ))) == NULL) goto malloc_error /* ---------------------------------------------------------------------- */ /* auxiliary functions */ @@ -35,7 +32,7 @@ but then restricted to one of the major wind directions (n, nw, w, etc) */ static inline point_t dorth_infty(dpoint_t p0, dpoint_t p2) { point_t r; - + r.y = sign(p2.x-p0.x); r.x = -sign(p2.y-p0.y); @@ -100,21 +97,21 @@ static void pointslope(privpath_t *pp, int i, int j, dpoint_t *ctr, dpoint_t *di i+=n; r+=1; } - + x = sums[j+1].x-sums[i].x+r*sums[n].x; y = sums[j+1].y-sums[i].y+r*sums[n].y; x2 = sums[j+1].x2-sums[i].x2+r*sums[n].x2; xy = sums[j+1].xy-sums[i].xy+r*sums[n].xy; y2 = sums[j+1].y2-sums[i].y2+r*sums[n].y2; k = j+1-i+r*n; - + ctr->x = x/k; ctr->y = y/k; a = (x2-(double)x*x/k)/k; b = (xy-(double)x*y/k)/k; c = (y2-(double)y*y/k)/k; - + lambda2 = (a+c+sqrt((a-c)*(a-c)+4*b*b))/2; /* larger e.value */ /* now find e.vector for lambda2 */ @@ -240,7 +237,7 @@ static double tangent(dpoint_t p0, dpoint_t p1, dpoint_t p2, dpoint_t p3, dpoint a = A - 2*B + C; b = -2*A + 2*B; c = A; - + d = b*b - 4*a*c; if (a==0 || d<0) { @@ -286,7 +283,7 @@ static int calc_sums(privpath_t *pp) { pp->sums[i+1].xy = pp->sums[i].xy + x*y; pp->sums[i+1].y2 = pp->sums[i].y2 + y*y; } - return 0; + return 0; malloc_error: return 1; @@ -308,13 +305,13 @@ static int calc_sums(privpath_t *pp) { satisfy xprod(constraint[0], cur) >= 0 and xprod(constraint[1], cur) <= 0. */ -/* Remark for potrace 1.1: the current implementation of calc_lon is - more complex than the implementation found in potrace 1.0, but it +/* Remark for Potrace 1.1: the current implementation of calc_lon is + more complex than the implementation found in Potrace 1.0, but it is considerably faster. The introduction of the "nc" data structure means that we only have to test the constraints for "corner" points. On a typical input file, this speeds up the calc_lon function by a factor of 31.2, thereby decreasing its time share - within the overall potrace algorithm from 72.6% to 7.82%, and + within the overall Potrace algorithm from 72.6% to 7.82%, and speeding up the overall algorithm by a factor of 3.36. On another input file, calc_lon was sped up by a factor of 6.7, decreasing its time share from 51.4% to 13.61%, and speeding up the overall @@ -357,7 +354,7 @@ static int calc_lon(privpath_t *pp) { /* determine pivot points: for each i, let pivk[i] be the furthest k such that all j with i=0; i--) { ct[0] = ct[1] = ct[2] = ct[3] = 0; @@ -374,7 +371,7 @@ static int calc_lon(privpath_t *pp) { k = nc[i]; k1 = i; while (1) { - + dir = (3+3*sign(pt[k].x-pt[k1].x)+sign(pt[k].y-pt[k1].y))/2; ct[dir]++; @@ -406,7 +403,7 @@ static int calc_lon(privpath_t *pp) { if (xprod(constraint[1], off) <= 0) { constraint[1] = off; } - } + } k1 = k; k = nc[k1]; if (!cyclic(k,i,k1)) { @@ -470,7 +467,7 @@ static int calc_lon(privpath_t *pp) { /* ---------------------------------------------------------------------- */ -/* Stage 2: calculate the optimal polygon (Sec. 2.2.2-2.2.4). */ +/* Stage 2: calculate the optimal polygon (Sec. 2.2.2-2.2.4). */ /* Auxiliary function: calculate the penalty of an edge from i to j in the given path. This needs the "lon" and "sum*" data. */ @@ -492,14 +489,14 @@ static double penalty3(privpath_t *pp, int i, int j) { j-=n; r+=1; } - + x = sums[j+1].x-sums[i].x+r*sums[n].x; y = sums[j+1].y-sums[i].y+r*sums[n].y; x2 = sums[j+1].x2-sums[i].x2+r*sums[n].x2; xy = sums[j+1].xy-sums[i].xy+r*sums[n].xy; y2 = sums[j+1].y2-sums[i].y2+r*sums[n].y2; k = j+1-i+r*n; - + px = (pt[i].x+pt[j].x)/2.0-pt[0].x; py = (pt[i].y+pt[j].y)/2.0-pt[0].y; ey = (pt[j].x-pt[i].x); @@ -508,7 +505,7 @@ static double penalty3(privpath_t *pp, int i, int j) { a = ((x2-2*x*px)/k+px*px); b = ((xy-x*py-y*px)/k+px*py); c = ((y2-2*y*py)/k+py*py); - + s = ex*ex*a + 2*ex*ey*b + ey*ey*c; return sqrt(s); @@ -519,7 +516,7 @@ static double penalty3(privpath_t *pp, int i, int j) { is in the polygon. Fixme: ### implement cyclic version. */ static int bestpolygon(privpath_t *pp) { - int i, j, m, k; + int i, j, m, k; int n = pp->len; double *pen = NULL; /* pen[n+1]: penalty vector */ int *prev = NULL; /* prev[n+1]: best path pointer vector */ @@ -613,7 +610,7 @@ static int bestpolygon(privpath_t *pp) free(seg0); free(seg1); return 0; - + malloc_error: free(pen); free(prev); @@ -657,7 +654,7 @@ static int adjust_vertices(privpath_t *pp) { if (r) { goto malloc_error; } - + /* calculate "optimal" point-slope representation for each line segment */ for (i=0; ibeta[j] = 0.5; } curve->alphacurve = 1; + return 0; } @@ -962,8 +960,8 @@ static int opti_penalty(privpath_t *pp, int i, int j, opti_t *res, double opttol A2 = dpara(p0, p1, p3); A3 = dpara(p0, p2, p3); /* A4 = dpara(p1, p2, p3); */ - A4 = A1+A3-A2; - + A4 = A1+A3-A2; + if (A2 == A1) { /* this should never happen */ return 1; } @@ -971,7 +969,7 @@ static int opti_penalty(privpath_t *pp, int i, int j, opti_t *res, double opttol t = A3/(A3-A4); s = A2/(A2-A1); A = A2 * t / 2.0; - + if (A == 0.0) { /* this should never happen */ return 1; } @@ -1132,14 +1130,14 @@ static int opticurve(privpath_t *pp, double opttolerance) { j = m; for (i=om-1; i>=0; i--) { if (pt[j]==j-1) { - pp->ocurve.tag[i] = pp->curve.tag[mod(j,m)]; - pp->ocurve.c[i][0] = pp->curve.c[mod(j,m)][0]; - pp->ocurve.c[i][1] = pp->curve.c[mod(j,m)][1]; - pp->ocurve.c[i][2] = pp->curve.c[mod(j,m)][2]; - pp->ocurve.vertex[i] = pp->curve.vertex[mod(j,m)]; - pp->ocurve.alpha[i] = pp->curve.alpha[mod(j,m)]; - pp->ocurve.alpha0[i] = pp->curve.alpha0[mod(j,m)]; - pp->ocurve.beta[i] = pp->curve.beta[mod(j,m)]; + pp->ocurve.tag[i] = pp->curve.tag[mod(j,m)]; + pp->ocurve.c[i][0] = pp->curve.c[mod(j,m)][0]; + pp->ocurve.c[i][1] = pp->curve.c[mod(j,m)][1]; + pp->ocurve.c[i][2] = pp->curve.c[mod(j,m)][2]; + pp->ocurve.vertex[i] = pp->curve.vertex[mod(j,m)]; + pp->ocurve.alpha[i] = pp->curve.alpha[mod(j,m)]; + pp->ocurve.alpha0[i] = pp->curve.alpha0[mod(j,m)]; + pp->ocurve.beta[i] = pp->curve.beta[mod(j,m)]; s[i] = t[i] = 1.0; } else { pp->ocurve.tag[i] = POTRACE_CURVETO; @@ -1201,7 +1199,7 @@ int process_path(path_t *plist, const potrace_param_t *param, progress_t *progre } cn = 0; } - + /* call downstream function with each path */ list_forall (p, plist) { TRY(calc_sums(p->priv)); diff --git a/src/trace/potrace/trace.h b/src/trace/potrace/trace.h index e6cac9d97..b33f8ba4d 100644 --- a/src/trace/potrace/trace.h +++ b/src/trace/potrace/trace.h @@ -1,5 +1,5 @@ -/* Copyright (C) 2001-2005 Peter Selinger. - This file is part of potrace. It is free software and it is covered +/* Copyright (C) 2001-2007 Peter Selinger. + This file is part of Potrace. It is free software and it is covered by the GNU General Public License. See the file COPYING for details. */ /* $Id$ */ -- 2.30.2