diff options
author | Peter Breitenlohner <peb@mppmu.mpg.de> | 2011-12-22 12:05:55 +0000 |
---|---|---|
committer | Peter Breitenlohner <peb@mppmu.mpg.de> | 2011-12-22 12:05:55 +0000 |
commit | 6b6a57de24d436e9b5f47fd031f5347de05e7e80 (patch) | |
tree | 4db5f719bcdd2b1f92ec15e3b60de2d5d4f6b9d3 /Build/source/texk/dvisvgm/dvisvgm-1.0.9/potracelib/decompose.c | |
parent | f4a722180ef0a33d802f5cf15b65fda6e6df0187 (diff) |
dvisvgm 1.0.10
git-svn-id: svn://tug.org/texlive/trunk@24907 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-1.0.9/potracelib/decompose.c')
-rw-r--r-- | Build/source/texk/dvisvgm/dvisvgm-1.0.9/potracelib/decompose.c | 514 |
1 files changed, 0 insertions, 514 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-1.0.9/potracelib/decompose.c b/Build/source/texk/dvisvgm/dvisvgm-1.0.9/potracelib/decompose.c deleted file mode 100644 index 376af015df3..00000000000 --- a/Build/source/texk/dvisvgm/dvisvgm-1.0.9/potracelib/decompose.c +++ /dev/null @@ -1,514 +0,0 @@ -/* Copyright (C) 2001-2011 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 <stdio.h> -#include <stdlib.h> -#include <string.h> -#include <limits.h> - -#include "potracelib.h" -#include "curve.h" -#include "lists.h" -#include "bitmap.h" -#include "decompose.h" -#include "progress.h" - -/* ---------------------------------------------------------------------- */ -/* deterministically and efficiently hash (x,y) into a pseudo-random bit */ - -static inline int detrand(int x, int y) { - 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; -} - -/* ---------------------------------------------------------------------- */ -/* auxiliary bitmap manipulations */ - -/* set the excess padding to 0 */ -static void bm_clearexcess(potrace_bitmap_t *bm) { - potrace_word mask; - int y; - - if (bm->w % BM_WORDBITS != 0) { - mask = BM_ALLBITS << (BM_WORDBITS - (bm->w % BM_WORDBITS)); - for (y=0; y<bm->h; y++) { - *bm_index(bm, bm->w, y) &= mask; - } - } -} - -struct bbox_s { - int x0, x1, y0, y1; /* bounding box */ -}; -typedef struct bbox_s bbox_t; - -/* clear the bm, assuming the bounding box is set correctly (faster - than clearing the whole bitmap) */ -static void clear_bm_with_bbox(potrace_bitmap_t *bm, bbox_t *bbox) { - int imin = (bbox->x0 / BM_WORDBITS); - int imax = ((bbox->x1 + BM_WORDBITS-1) / BM_WORDBITS); - int i, y; - - for (y=bbox->y0; y<bbox->y1; y++) { - for (i=imin; i<imax; i++) { - bm_scanline(bm, y)[i] = 0; - } - } -} - -/* ---------------------------------------------------------------------- */ -/* auxiliary functions */ - -/* return the "majority" value of bitmap bm at intersection (x,y). We - assume that the bitmap is balanced at "radius" 1. */ -static int majority(potrace_bitmap_t *bm, int x, int y) { - int i, a, ct; - - for (i=2; i<5; i++) { /* check at "radius" i */ - ct = 0; - for (a=-i+1; a<=i-1; a++) { - ct += BM_GET(bm, x+a, y+i-1) ? 1 : -1; - ct += BM_GET(bm, x+i-1, y+a-1) ? 1 : -1; - ct += BM_GET(bm, x+a-1, y-i) ? 1 : -1; - ct += BM_GET(bm, x-i, y+a) ? 1 : -1; - } - if (ct>0) { - return 1; - } else if (ct<0) { - return 0; - } - } - return 0; -} - -/* ---------------------------------------------------------------------- */ -/* decompose image into paths */ - -/* efficiently invert bits [x,infty) and [xa,infty) in line y. Here xa - must be a multiple of BM_WORDBITS. */ -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<xa) { - for (i = xhi; i < xa; i+=BM_WORDBITS) { - *bm_index(bm, i, y) ^= BM_ALLBITS; - } - } else { - for (i = xa; i < xhi; i+=BM_WORDBITS) { - *bm_index(bm, i, y) ^= BM_ALLBITS; - } - } - /* note: the following "if" is needed because x86 treats a<<b as - a<<(b&31). I spent hours looking for this bug. */ - if (xlo) { - *bm_index(bm, xhi, y) ^= (BM_ALLBITS << (BM_WORDBITS - xlo)); - } -} - -/* a path is represented as an array of points, which are thought to - lie on the corners of pixels (not on their centers). The path point - (x,y) is the lower left corner of the pixel (x,y). Paths are - represented by the len/pt components of a path_t object (which - also stores other information about the path) */ - -/* xor the given pixmap with the interior of the given path. Note: the - path must be within the dimensions of the pixmap. */ -static void xor_path(potrace_bitmap_t *bm, path_t *p) { - int xa, x, y, k, y1; - - if (p->priv->len <= 0) { /* a path of length 0 is silly, but legal */ - return; - } - - y1 = p->priv->pt[p->priv->len-1].y; - - xa = p->priv->pt[0].x & -BM_WORDBITS; - for (k=0; k<p->priv->len; k++) { - x = p->priv->pt[k].x; - y = p->priv->pt[k].y; - - if (y != y1) { - /* efficiently invert the rectangle [x,xa] x [y,y1] */ - xor_to_ref(bm, x, min(y,y1), xa); - y1 = y; - } - } -} - -/* Find the bounding box of a given path. Path is assumed to be of - non-zero length. */ -static void setbbox_path(bbox_t *bbox, path_t *p) { - int x, y; - int k; - - bbox->y0 = INT_MAX; - bbox->y1 = 0; - bbox->x0 = INT_MAX; - bbox->x1 = 0; - - for (k=0; k<p->priv->len; k++) { - x = p->priv->pt[k].x; - y = p->priv->pt[k].y; - - if (x < bbox->x0) { - bbox->x0 = x; - } - if (x > bbox->x1) { - bbox->x1 = x; - } - if (y < bbox->y0) { - bbox->y0 = y; - } - if (y > bbox->y1) { - bbox->y1 = y; - } - } -} - -/* compute a path in the given pixmap, separating black from white. - Start path at the point (x0,x1), which must be an upper left corner - of the path. Also compute the area enclosed by the path. Return a - new path_t object, or NULL on error (note that a legitimate path - cannot have length 0). Sign is required for correct interpretation - of turnpolicies. */ -static path_t *findpath(potrace_bitmap_t *bm, int x0, int y0, int sign, int turnpolicy) { - int x, y, dirx, diry, len, size, area; - int c, d, tmp; - point_t *pt, *pt1; - path_t *p = NULL; - - x = x0; - y = y0; - dirx = 0; - diry = -1; - - len = size = 0; - pt = NULL; - area = 0; - - while (1) { - /* add point to path */ - if (len>=size) { - size += 100; - size = (int)(1.3 * size); - pt1 = (point_t *)realloc(pt, size * sizeof(point_t)); - if (!pt1) { - goto error; - } - pt = pt1; - } - 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)) - || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY && majority(bm, x, y)) - || (turnpolicy == POTRACE_TURNPOLICY_MINORITY && !majority(bm, x, y))) { - tmp = dirx; /* right turn */ - dirx = diry; - diry = -tmp; - } else { - tmp = dirx; /* left turn */ - dirx = -diry; - diry = tmp; - } - } else if (c) { /* right turn */ - tmp = dirx; - dirx = diry; - diry = -tmp; - } else if (!d) { /* left turn */ - tmp = dirx; - dirx = -diry; - diry = tmp; - } - } /* while this path */ - - /* allocate new path object */ - p = potrace_path_new(); - if (!p) { - goto error; - } - - p->priv->pt = pt; - p->priv->len = len; - p->area = area; - p->sign = sign; - - return p; - - error: - free(pt); - return NULL; -} - -/* Give a tree structure to the given path list, based on "insideness" - testing. I.e., path A is considered "below" path B if it is inside - path B. The input pathlist is assumed to be ordered so that "outer" - paths occur before "inner" paths. The tree structure is stored in - the "childlist" and "sibling" components of the path_t - structure. The linked list structure is also changed so that - negative path components are listed immediately after their - positive parent. Note: some backends may ignore the tree - structure, others may use it e.g. to group path components. We - assume that in the input, point 0 of each path is an "upper left" - corner of the path, as returned by bm_to_pathlist. This makes it - easy to find an "interior" point. The bm argument should be a - bitmap of the correct size (large enough to hold all the paths), - and will be used as scratch space. Return 0 on success or -1 on - error with errno set. */ - -static void pathlist_to_tree(path_t *plist, potrace_bitmap_t *bm) { - path_t *p, *p1; - path_t *heap, *heap1; - path_t *cur; - path_t *head; - path_t **plist_hook; /* for fast appending to linked list */ - path_t **hook_in, **hook_out; /* for fast appending to linked list */ - bbox_t bbox; - - bm_clear(bm, 0); - - /* save original "next" pointers */ - list_forall(p, plist) { - p->sibling = p->next; - p->childlist = NULL; - } - - heap = plist; - - /* the heap holds a list of lists of paths. Use "childlist" field - for outer list, "next" field for inner list. Each of the sublists - is to be turned into a tree. This code is messy, but it is - actually fast. Each path is rendered exactly once. We use the - heap to get a tail recursive algorithm: the heap holds a list of - pathlists which still need to be transformed. */ - - while (heap) { - /* unlink first sublist */ - cur = heap; - heap = heap->childlist; - cur->childlist = NULL; - - /* unlink first path */ - head = cur; - cur = cur->next; - head->next = NULL; - - /* render path */ - xor_path(bm, head); - setbbox_path(&bbox, head); - - /* now do insideness test for each element of cur; append it to - head->childlist if it's inside head, else append it to - head->next. */ - hook_in=&head->childlist; - hook_out=&head->next; - list_forall_unlink(p, cur) { - if (p->priv->pt[0].y <= bbox.y0) { - list_insert_beforehook(p, hook_out); - /* append the remainder of the list to hook_out */ - *hook_out = cur; - break; - } - if (BM_GET(bm, p->priv->pt[0].x, p->priv->pt[0].y-1)) { - list_insert_beforehook(p, hook_in); - } else { - list_insert_beforehook(p, hook_out); - } - } - - /* clear bm */ - clear_bm_with_bbox(bm, &bbox); - - /* now schedule head->childlist and head->next for further - processing */ - if (head->next) { - head->next->childlist = heap; - heap = head->next; - } - if (head->childlist) { - head->childlist->childlist = heap; - heap = head->childlist; - } - } - - /* copy sibling structure from "next" to "sibling" component */ - p = plist; - while (p) { - p1 = p->sibling; - p->sibling = p->next; - p = p1; - } - - /* reconstruct a new linked list ("next") structure from tree - ("childlist", "sibling") structure. This code is slightly messy, - because we use a heap to make it tail recursive: the heap - contains a list of childlists which still need to be - processed. */ - heap = plist; - if (heap) { - heap->next = NULL; /* heap is a linked list of childlists */ - } - plist = NULL; - plist_hook = &plist; - while (heap) { - heap1 = heap->next; - for (p=heap; p; p=p->sibling) { - /* p is a positive path */ - /* append to linked list */ - list_insert_beforehook(p, plist_hook); - - /* go through its children */ - for (p1=p->childlist; p1; p1=p1->sibling) { - /* append to linked list */ - list_insert_beforehook(p1, plist_hook); - /* append its childlist to heap, if non-empty */ - if (p1->childlist) { - list_append(path_t, heap1, p1->childlist); - } - } - } - heap = heap1; - } - - return; -} - -/* find the next set pixel in a row <= y. Pixels are searched first - left-to-right, then top-down. In other words, (x,y)<(x',y') if y>y' - or y=y' and x<x'. If found, return 0 and store pixel in - (*xp,*yp). Else return 1. Note that this function assumes that - excess bytes have been cleared with bm_clearexcess. */ -static int findnext(potrace_bitmap_t *bm, int *xp, int *yp) { - int x; - int y; - int x0; - - x0 = (*xp) & ~(BM_WORDBITS-1); - - for (y=*yp; y>=0; y--) { - for (x=x0; x<bm->w; x+=BM_WORDBITS) { - if (*bm_index(bm, x, y)) { - while (!BM_GET(bm, x, y)) { - x++; - } - /* found */ - *xp = x; - *yp = y; - return 0; - } - } - x0 = 0; - } - /* not found */ - return 1; -} - -/* Decompose the given bitmap into paths. Returns a linked list of - path_t objects with the fields len, pt, area, sign filled - in. Returns 0 on success with plistp set, or -1 on error with errno - set. */ - -int bm_to_pathlist(const potrace_bitmap_t *bm, path_t **plistp, const potrace_param_t *param, progress_t *progress) { - int x; - int y; - path_t *p; - path_t *plist = NULL; /* linked list of path objects */ - path_t **plist_hook = &plist; /* used to speed up appending to linked list */ - potrace_bitmap_t *bm1 = NULL; - int sign; - - bm1 = bm_dup(bm); - if (!bm1) { - goto error; - } - - /* be sure the byte padding on the right is set to 0, as the fast - pixel search below relies on it */ - bm_clearexcess(bm1); - - /* iterate through components */ - x = 0; - y = bm1->h - 1; - while (findnext(bm1, &x, &y) == 0) { - /* calculate the sign by looking at the original */ - sign = BM_GET(bm, x, y) ? '+' : '-'; - - /* calculate the path */ - p = findpath(bm1, x, y+1, sign, param->turnpolicy); - if (p==NULL) { - goto error; - } - - /* update buffered image */ - xor_path(bm1, p); - - /* if it's a turd, eliminate it, else append it to the list */ - if (p->area <= param->turdsize) { - potrace_path_free(p); - } else { - list_insert_beforehook(p, plist_hook); - } - - if (bm1->h > 0) { /* to be sure */ - progress_update(1-y/(double)bm1->h, progress); - } - } - - pathlist_to_tree(plist, bm1); - bm_free(bm1); - *plistp = plist; - - progress_update(1.0, progress); - - return 0; - - error: - bm_free(bm1); - list_forall_unlink(p, plist) { - potrace_path_free(p); - } - return -1; -} |