diff options
Diffstat (limited to 'nx-X11/extras/ttf2pt1/bitmap.c')
| -rw-r--r-- | nx-X11/extras/ttf2pt1/bitmap.c | 2633 |
1 files changed, 0 insertions, 2633 deletions
diff --git a/nx-X11/extras/ttf2pt1/bitmap.c b/nx-X11/extras/ttf2pt1/bitmap.c deleted file mode 100644 index d2334e433..000000000 --- a/nx-X11/extras/ttf2pt1/bitmap.c +++ /dev/null @@ -1,2633 +0,0 @@ -/* - * Handling of the bitmapped glyphs - * - * Copyright (c) 2001 by the TTF2PT1 project - * Copyright (c) 2001 by Sergey Babkin - * - * see COPYRIGHT for the full copyright notice - */ - -#include <stdio.h> -#include <stdlib.h> -#include <math.h> -#include "pt1.h" -#include "global.h" - -/* possible values of limits */ -#define L_NONE 0 /* nothing here */ -#define L_ON 1 /* black is on up/right */ -#define L_OFF 2 /* black is on down/left */ - -static int warnedhints = 0; - - -#ifdef USE_AUTOTRACE -#include <autotrace/autotrace.h> - -/* - * Produce an autotraced outline from a bitmap. - * scale - factor to scale the sizes - * bmap - array of dots by lines, xsz * ysz - * xoff, yoff - offset of the bitmap's lower left corner - * from the logical position (0,0) - */ - -static void -autotraced_bmp_outline( - GLYPH *g, - int scale, - char *bmap, - int xsz, - int ysz, - int xoff, - int yoff -) -{ - at_bitmap_type atb; - at_splines_type *atsp; - at_fitting_opts_type *atoptsp; - at_spline_list_type *slp; - at_spline_type *sp; - int i, j, k; - double lastx, lasty; - double fscale; - char *xbmap; - - fscale = (double)scale; - - /* provide a white margin around the bitmap */ - xbmap = malloc((ysz+2)*(xsz+2)); - if(xbmap == 0) { - fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); - exit(255); - } - memset(xbmap, 0, xsz+2); /* top margin */ - for(i=0, j=xsz+2; i<ysz; i++, j+=xsz+2) { - xbmap[j] = 0; /* left margin */ - memcpy(&xbmap[j+1], &bmap[xsz*(ysz-1-i)], xsz); /* a line of bitmap */ - xbmap[j+xsz+1] = 0; /* right margin */ - } - memset(xbmap+j, 0, xsz+2); /* bottom margin */ - xoff--; yoff-=2; /* compensate for the margins */ - - atoptsp = at_fitting_opts_new(); - - atb.width = xsz+2; - atb.height = ysz+2; - atb.np = 1; - atb.bitmap = xbmap; - - atsp = at_splines_new(&atb, atoptsp); - - lastx = lasty = -1.; - for(i=0; i<atsp->length; i++) { - slp = &atsp->data[i]; -#if 0 - fprintf(stderr, "%s: contour %d: %d entries clockwise=%d color=%02X%02X%02X\n", - g->name, i, slp->length, slp->clockwise, slp->color.r, slp->color.g, slp->color.b); -#endif - if(slp->length == 0) - continue; -#if 0 - if(slp->color.r + slp->color.g + slp->color.b == 0) - continue; -#endif - fg_rmoveto(g, fscale*(slp->data[0].v[0].x+xoff), fscale*(slp->data[0].v[0].y+yoff)); - for(j=0; j<slp->length; j++) { -#if 0 - fprintf(stderr, " "); - for(k=0; k<4; k++) - fprintf(stderr, "(%g %g) ", - fscale*(slp->data[j].v[k].x+xoff), - fscale*(ysz-slp->data[j].v[k].y+yoff) - ); - fprintf(stderr, "\n"); -#endif - fg_rrcurveto(g, - fscale*(slp->data[j].v[1].x+xoff), fscale*(slp->data[j].v[1].y+yoff), - fscale*(slp->data[j].v[2].x+xoff), fscale*(slp->data[j].v[2].y+yoff), - fscale*(slp->data[j].v[3].x+xoff), fscale*(slp->data[j].v[3].y+yoff) ); - } - g_closepath(g); - } - - at_splines_free(atsp); - at_fitting_opts_free(atoptsp); - free(xbmap); -} - -#endif /*USE_AUTOTRACE*/ - -/* an extension of gentry for description of the fragments */ -typedef struct gex_frag GEX_FRAG; -struct gex_frag { - /* indexes to len, the exact values and order are important */ -#define GEXFI_NONE -1 -#define GEXFI_CONVEX 0 -#define GEXFI_CONCAVE 1 -#define GEXFI_LINE 2 /* a line with steps varying by +-1 pixel */ -#define GEXFI_EXACTLINE 3 /* a line with exactly the same steps */ -#define GEXFI_SERIF 4 /* small serifs at the ends of stemsi - must be last */ -#define GEXFI_COUNT 5 /* maximal index + 1 */ - unsigned short len[GEXFI_COUNT]; /* length of various fragment types starting here */ - unsigned short lenback[GEXFI_COUNT]; /* length back to the start of curve */ - - signed char ixstart; /* index of the frag type that starts here */ - signed char ixcont; /* index of the frag type that continues here */ - - short flags; -#define GEXFF_HLINE 0x0001 /* the exact line is longer in "horizontal" dimension */ -#define GEXFF_EXTR 0x0002 /* this gentry is an extremum in some direction */ -#define GEXFF_CIRC 0x0004 /* the joint at this gentry is for a circular curve */ -#define GEXFF_DRAWCURVE 0x0008 /* vect[] describes a curve to draw */ -#define GEXFF_DRAWLINE 0x0010 /* vect[] describes a line to draw */ -#define GEXFF_SPLIT 0x0020 /* is a result of splitting a line */ -#define GEXFF_SYMNEXT 0x0040 /* this subfrag is symmetric with next one */ -#define GEXFF_DONE 0x0080 /* this subfrag has been vectorized */ -#define GEXFF_LONG 0x0100 /* this gentry is longer than 1 pixel */ - - unsigned short aidx; /* index of gentry in the array representing the contour */ - - unsigned short vectlen; /* number of gentries represented by vect[] */ - - /* coordinates for vectored replacement of this fragment */ - /* (already scaled because it's needed for curve approximation) */ - double vect[4 /*ref.points*/][2 /*X,Y*/]; - - double bbox[2 /*X,Y*/]; /* absolute sizes of bounding box of a subfragment */ - - /* used when splitting the curved frags into subfrags */ - GENTRY *prevsub; /* to gentries describing neighboring subfrags */ - GENTRY *nextsub; - GENTRY *ordersub; /* single-linked list describing the order of calculation */ - - int sublen; /* length of this subfrag */ - /* the symmetry across the subfrags */ - int symaxis; /* the symmetry axis, with next subfrag */ - int symxlen; /* min length of adjacent symmetric frags */ - /* the symmetry within this subfrag (the axis is always diagonal) */ - GENTRY *symge; /* symge->i{x,y}3 is the symmetry point of symge==0 if none */ - -}; -#define X_FRAG(ge) ((GEX_FRAG *)((ge)->ext)) - -/* various interesting tables related to GEX_FRAG */ -static char *gxf_name[GEXFI_COUNT] = {"Convex", "Concave", "Line", "ExLine", "Serif"}; -static int gxf_cvk[2] = {-1, 1}; /* coefficients of concaveness */ - -/* - * Dump the contents of X_EXT()->len and ->lenback for a contour - */ -static void -gex_dump_contour( - GENTRY *ge, - int clen -) -{ - int i, j; - - for(j = 0; j < GEXFI_COUNT; j++) { - fprintf(stderr, "%-8s", gxf_name[j]); - for(i = 0; i < clen; i++, ge = ge->frwd) - fprintf(stderr, " %2d", X_FRAG(ge)->len[j]); - fprintf(stderr, " %p\n (back) ", ge); - for(i = 0; i < clen; i++, ge = ge->frwd) - fprintf(stderr, " %2d", X_FRAG(ge)->lenback[j]); - fprintf(stderr, "\n"); - } -} - -/* - * Calculate values of X_EXT()->lenback[] for all entries in - * a contour. The contour is identified by: - * ge - any gentry of the contour - * clen - contour length - */ - -static void -gex_calc_lenback( - GENTRY *ge, - int clen -) -{ - int i, j; - int end; - GEX_FRAG *f; - int len[GEXFI_COUNT]; /* length of the most recent fragment */ - int count[GEXFI_COUNT]; /* steps since beginning of the fragment */ - - for(j = 0; j < GEXFI_COUNT; j++) - len[j] = count[j] = 0; - - end = clen; - for(i = 0; i < end; i++, ge = ge->frwd) { - f = X_FRAG(ge); - for(j = 0; j < GEXFI_COUNT; j++) { - if(len[j] != count[j]) { - f->lenback[j] = count[j]++; - } else - f->lenback[j] = 0; - if(f->len[j] != 0) { - len[j] = f->len[j]; - count[j] = 1; /* start with the next gentry */ - /* if the fragment will wrap over the start, process to its end */ - if(i < clen && i + len[j] > end) - end = i + len[j]; - } - } - } - gex_dump_contour(ge, clen); -} - -/* Limit a curve to not exceed the given coordinates - * at its given side - */ - -static void -limcurve( - double curve[4][2 /*X,Y*/], - double lim[2 /*X,Y*/], - int where /* 0 - start, 3 - end */ -) -{ - int other = 3-where; /* the other end */ - int sgn[2 /*X,Y*/]; /* sign for comparison */ - double t, from, to, nt, t2, nt2, tt[4]; - double val[2 /*X,Y*/]; - int i; - - for(i=0; i<2; i++) - sgn[i] = fsign(curve[other][i] - curve[where][i]); - -#if 0 - fprintf(stderr, " limit (%g,%g)-(%g,%g) at %d by (%g,%g), sgn(%d,%d)\n", - curve[0][0], curve[0][1], curve[3][0], curve[3][1], - where, lim[0], lim[1], sgn[0], sgn[1]); -#endif - /* a common special case */ - if( sgn[0]*(curve[where][0] - lim[0]) >= 0. - && sgn[1]*(curve[where][1] - lim[1]) >= 0. ) - return; /* nothing to do */ - - if(other==0) { - from = 0.; - to = 1.; - } else { - from = 1.; - to = 0.; - } -#if 0 - fprintf(stderr, "t="); -#endif - while( fabs(from-to) > 0.00001 ) { - t = 0.5 * (from+to); - t2 = t*t; - nt = 1.-t; - nt2 = nt*nt; - tt[0] = nt2*nt; - tt[1] = 3*nt2*t; - tt[2] = 3*nt*t2; - tt[3] = t*t2; - for(i=0; i<2; i++) - val[i] = curve[0][i]*tt[0] + curve[1][i]*tt[1] - + curve[2][i]*tt[2] + curve[3][i]*tt[3]; -#if 0 - fprintf(stderr, "%g(%g,%g) ", t, val[0], val[1]); -#endif - if(fabs(val[0] - lim[0]) < 0.1 - || fabs(val[1] - lim[1]) < 0.1) - break; - - if(sgn[0] * (val[0] - lim[0]) < 0. - || sgn[1] * (val[1] - lim[1]) < 0.) - to = t; - else - from = t; - } - /* now t is the point of splitting */ -#define SPLIT(pt1, pt2) ( (pt1) + t*((pt2)-(pt1)) ) /* order is important! */ - for(i=0; i<2; i++) { - double v11, v12, v13, v21, v22, v31; /* intermediate points */ - - v11 = SPLIT(curve[0][i], curve[1][i]); - v12 = SPLIT(curve[1][i], curve[2][i]); - v13 = SPLIT(curve[2][i], curve[3][i]); - v21 = SPLIT(v11, v12); - v22 = SPLIT(v12, v13); - v31 = SPLIT(v21, v22); - if(other==0) { - curve[1][i] = v11; - curve[2][i] = v21; - curve[3][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31; - } else { - curve[0][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31; - curve[1][i] = v22; - curve[2][i] = v13; - } - } -#undef SPLIT -#if 0 - fprintf(stderr, "\n"); -#endif -} - -/* - * Vectorize a subfragment of a curve fragment. All the data has been already - * collected by this time - */ - -static void -dosubfrag( - GLYPH *g, - int fti, /* fragment type index */ - GENTRY *firstge, /* first gentry of fragment */ - GENTRY *ge, /* first gentry of subfragment */ - double fscale -) -{ - GENTRY *gel, *gei; /* last gentry of this subfrag */ - GEX_FRAG *f, *ff, *lf, *pf, *xf; - /* maximal amount of space that can be used at the beginning and the end */ - double fixfront[2], fixend[2]; /* fixed points - used to show direction */ - double mvfront[2], mvend[2]; /* movable points */ - double limfront[2], limend[2]; /* limit of movement for movabel points */ - double sympt; - int outfront, outend; /* the beginning/end is going outwards */ - int symfront, symend; /* a ready symmetric fragment is present at front/end */ - int drnd[2 /*X,Y*/]; /* size of the round part */ - int i, j, a1, a2, ndots; - double avg2, max2; /* squared distances */ - struct dot_dist *dots, *usedots; - - ff = X_FRAG(firstge); - f = X_FRAG(ge); - gel = f->nextsub; - lf = X_FRAG(gel); - if(f->prevsub != 0) - pf = X_FRAG(f->prevsub); - else - pf = 0; - - for(i=0; i<2; i++) - drnd[i] = gel->bkwd->ipoints[i][2] - ge->ipoints[i][2]; - - if(f->prevsub==0 && f->ixcont == GEXFI_NONE) { - /* nothing to join with : may use the whole length */ - for(i = 0; i < 2; i++) - limfront[i] = ge->bkwd->ipoints[i][2]; - } else { - /* limit to a half */ - for(i = 0; i < 2; i++) - limfront[i] = 0.5 * (ge->ipoints[i][2] + ge->bkwd->ipoints[i][2]); - } - if( (ge->ix3 == ge->bkwd->ix3) /* vert */ - ^ (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3)) - ^ (fti == GEXFI_CONCAVE) /* counter-clockwise */ ) { - /* the beginning is not a flat 90-degree end */ - outfront = 1; - for(i = 0; i < 2; i++) - fixfront[i] = ge->frwd->ipoints[i][2]; - } else { - outfront = 0; - for(i = 0; i < 2; i++) - fixfront[i] = ge->ipoints[i][2]; - } - - if(lf->nextsub==0 && lf->ixstart == GEXFI_NONE) { - /* nothing to join with : may use the whole length */ - for(i = 0; i < 2; i++) - limend[i] = gel->ipoints[i][2]; - } else { - /* limit to a half */ - for(i = 0; i < 2; i++) - limend[i] = 0.5 * (gel->ipoints[i][2] + gel->bkwd->ipoints[i][2]); - } - gei = gel->bkwd->bkwd; - if( (gel->ix3 == gel->bkwd->ix3) /* vert */ - ^ (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3)) - ^ (fti == GEXFI_CONVEX) /* clockwise */ ) { - /* the end is not a flat 90-degree end */ - outend = 1; - for(i = 0; i < 2; i++) - fixend[i] = gel->bkwd->bkwd->ipoints[i][2]; - } else { - outend = 0; - for(i = 0; i < 2; i++) - fixend[i] = gel->bkwd->ipoints[i][2]; - } - - for(i = 0; i < 2; i++) { - fixfront[i] *= fscale; - limfront[i] *= fscale; - fixend[i] *= fscale; - limend[i] *= fscale; - } - - fprintf(stderr, " %d out(%d[%d %d %d],%d[%d %d %d]) drnd(%d, %d)\n", - fti, - outfront, - (ge->ix3 == ge->bkwd->ix3), - (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3)), - (fti == GEXFI_CONCAVE), - outend, - (gel->ix3 == gel->bkwd->ix3), - (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3)), - (fti == GEXFI_CONVEX), - drnd[0], drnd[1]); - - /* prepare to calculate the distances */ - ndots = f->sublen - 1; - dots = malloc(sizeof(*dots) * ndots); - if(dots == 0) { - fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); - exit(255); - } - for(i = 0, gei = ge; i < ndots; i++, gei = gei->frwd) { - for(a1 = 0; a1 < 2; a1++) - dots[i].p[a1] = fscale * gei->ipoints[a1][2]; - } - - /* see if we can mirror a ready symmetric curve */ - - /* check symmetry with the fragment before this */ - symfront = (pf != 0 && (pf->flags & GEXFF_SYMNEXT) && (pf->flags & GEXFF_DONE) - && ( outend && f->sublen <= pf->sublen - || ( pf->sublen == f->sublen - && (lf->sublen == 0 - || ( abs(limfront[0]-limend[0]) >= abs(pf->vect[0][0]-pf->vect[3][0]) - && abs(limfront[1]-limend[1]) >= abs(pf->vect[0][1]-pf->vect[3][1]) )) - ) - ) - ); - /* check symmetry with the fragment after this */ - symend = ( (f->flags & GEXFF_SYMNEXT) && (lf->flags & GEXFF_DONE) - && ( outfront && f->sublen <= lf->sublen - || ( lf->sublen == f->sublen - && (pf == 0 - || ( abs(limfront[0]-limend[0]) >= abs(lf->vect[0][0]-lf->vect[3][0]) - && abs(limfront[1]-limend[1]) >= abs(lf->vect[0][1]-lf->vect[3][1]) )) - ) - ) - ); - if(symfront || symend) { - /* mirror the symmetric neighbour subfrag */ - if(symfront) { - a1 = (ge->ix3 != ge->bkwd->ix3); /* the symmetry axis */ - a2 = !a1; /* the other axis (goes along the extremum gentry) */ - - /* the symmetry point on a2 */ - sympt = fscale * 0.5 * (ge->ipoints[a2][2] + ge->bkwd->ipoints[a2][2]); - xf = pf; /* the symmetric fragment */ - } else { - a1 = (gel->ix3 != gel->bkwd->ix3); /* the symmetry axis */ - a2 = !a1; /* the other axis (goes along the extremum gentry) */ - - /* the symmetry point on a2 */ - sympt = fscale * 0.5 * (gel->ipoints[a2][2] + gel->bkwd->ipoints[a2][2]); - xf = lf; /* the symmetric fragment */ - } - fprintf(stderr, " sym with %p f=%d(%p) e=%d(%p) a1=%c a2=%c sympt=%g\n", - xf, symfront, pf, symend, lf, - a1 ? 'Y': 'X', a2 ? 'Y': 'X', sympt - ); - for(i=0; i<4; i++) { - f->vect[3-i][a1] = xf->vect[i][a1]; - f->vect[3-i][a2] = sympt - (xf->vect[i][a2]-sympt); - } - if(symfront) { - if(outend || lf->sublen==0) - limcurve(f->vect, limend, 3); - } else { - if(outfront || pf == 0) - limcurve(f->vect, limfront, 0); - } - avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2); - fprintf(stderr, " avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale); - if(max2 <= fscale*fscale) { - f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE); - f->vectlen = f->sublen; - free(dots); - return; - } - } - - if( !outfront && !outend && f->symge != 0) { - /* a special case: try a circle segment as an approximation */ - double lenfront, lenend, len, maxlen; - - /* coefficient for a Bezier approximation of a circle */ -#define CIRCLE_FRAC 0.55 - - a1 = (ge->ix3 == ge->bkwd->ix3); /* get the axis along the front */ - a2 = !a1; /* axis along the end */ - - lenfront = fixfront[a1] - limfront[a1]; - lenend = fixend[a2] - limend[a2]; - if(fabs(lenfront) < fabs(lenend)) - len = fabs(lenfront); - else - len = fabs(lenend); - - /* make it go close to the round shape */ - switch(f->sublen) { - case 2: - maxlen = fscale; - break; - case 4: - case 6: - maxlen = fscale * 2.; - break; - default: - maxlen = fscale * abs(ge->frwd->frwd->ipoints[a1][2] - - ge->ipoints[a1][2]); - break; - } - if(len > maxlen) - len = maxlen; - - mvfront[a1] = fixfront[a1] - fsign(lenfront) * len; - mvfront[a2] = limfront[a2]; - mvend[a2] = fixend[a2] - fsign(lenend) * len; - mvend[a1] = limend[a1]; - - for(i=0; i<2; i++) { - f->vect[0][i] = mvfront[i]; - f->vect[3][i] = mvend[i]; - } - f->vect[1][a1] = mvfront[a1] + CIRCLE_FRAC*(mvend[a1]-mvfront[a1]); - f->vect[1][a2] = mvfront[a2]; - f->vect[2][a1] = mvend[a1]; - f->vect[2][a2] = mvend[a2] + CIRCLE_FRAC*(mvfront[a2]-mvend[a2]); - - avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2); - fprintf(stderr, " avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale); - if(max2 <= fscale*fscale) { - f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE); - f->vectlen = f->sublen; - free(dots); - return; - } -#undef CIRCLE_FRAC - } - for(i=0; i<2; i++) { - f->vect[0][i] = limfront[i]; - f->vect[1][i] = fixfront[i]; - f->vect[2][i] = fixend[i]; - f->vect[3][i] = limend[i]; - } - usedots = dots; - if(outfront) { - usedots++; ndots--; - } - if(outend) - ndots--; - if( fcrossrayscv(f->vect, NULL, NULL) == 0) { - fprintf(stderr, "**** Internal error: rays must cross but don't at %p-%p\n", - ge, gel); - fprintf(stderr, " (%g, %g) (%g, %g) (%g, %g) (%g, %g)\n", - limfront[0], limfront[1], - fixfront[0], fixfront[1], - fixend[0], fixend[1], - limend[0], limend[1] - ); - dumppaths(g, NULL, NULL); - exit(1); - } else { - if(ndots != 0) - fapproxcurve(f->vect, usedots, ndots); - f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE); - f->vectlen = f->sublen; - } - free(dots); -} - -/* - * Subtract a list of gentries (covered by a fragment of higher - * priority) from the set of fragments of a given - * type. - * - * An example is subtraction of the long exact line fragments - * from the curve fragments which get overridden. - */ - -static void -frag_subtract( - GLYPH *g, - GENTRY **age, /* array of gentries for this contour */ - int clen, /* length of the contour */ - GENTRY *ge, /* first gentry to be subtracted */ - int slen, /* number of gentries in the list to be subtracted */ - int d /* type of fragments from which to subtract, as in GEXFI_... */ -) -{ - GENTRY *pge; - GEX_FRAG *f, *pf; - int len, i, j; - - f = X_FRAG(ge); - len = slen; - - /* check if we overlap the end of some fragment */ - if(f->lenback[d]) { - /* chop off the end of conflicting fragment */ - len = f->lenback[d]; - pge = age[(f->aidx + clen - len)%clen]; - pf = X_FRAG(pge); - if(pf->len[d] == clen+1 && pf->flags & GEXFF_CIRC) { - /* the conflicting fragment is self-connected */ - - pf->len[d] = 0; - /* calculate the new value for lenback */ - len = clen+1 - slen; - for(pge = ge; len > 0; pge = pge->bkwd, len--) - X_FRAG(pge)->lenback[d] = len; - /* now pge points to the last entry of the line, - * which is also the new first entry of the curve - */ - X_FRAG(pge)->len[d] = clen+2 - slen; - /* clean lenback of gentries covered by the line */ - for(pge = ge->frwd, j = slen-1; j > 0; pge = pge->frwd, j--) - X_FRAG(pge)->lenback[d] = 0; - fprintf(stderr, " cut %s circular frag to %p-%p\n", - gxf_name[d], pge, ge); - gex_dump_contour(ge, clen); - } else { - /* when we chop off a piece of fragment, we leave the remaining - * piece(s) overlapping with the beginning and possibly the end - * of the line fragment under consideration - */ - fprintf(stderr, " cut %s frag at %p from len=%d to len=%d (end %p)\n", - gxf_name[d], pge, pf->len[d], len+1, ge); - j = pf->len[d] - len - 1; /* how many gentries are chopped off */ - pf->len[d] = len + 1; - i = slen - 1; - for(pge = ge->frwd; j > 0 && i > 0; j--, i--, pge = pge->frwd) - X_FRAG(pge)->lenback[d] = 0; - gex_dump_contour(ge, clen); - - if(j != 0) { - /* the conflicting fragment is split in two by this line - * fragment, fix up its tail - */ - - fprintf(stderr, " end of %s frag len=%d %p-", - gxf_name[d], j+1, pge->bkwd); - X_FRAG(pge->bkwd)->len[d] = j+1; /* the overlapping */ - for(i = 1; j > 0; j--, i++, pge = pge->frwd) - X_FRAG(pge)->lenback[d] = i; - fprintf(stderr, "%p\n", pge->bkwd); - gex_dump_contour(ge, clen); - } - } - } - /* check if we overlap the beginning of some fragments */ - i = slen-1; /* getntries remaining to consider */ - j = 0; /* gentries remaining in the overlapping fragment */ - for(pge = ge; i > 0; i--, pge = pge->frwd) { - if(j > 0) { - X_FRAG(pge)->lenback[d] = 0; - j--; - } - /* the beginning of one fragment may be the end of another - * fragment, in this case if j-- above results in 0, that will - * cause it to check the same gentry for the beginning - */ - if(j == 0) { - pf = X_FRAG(pge); - j = pf->len[d]; - if(j != 0) { - fprintf(stderr, " removed %s frag at %p len=%d\n", - gxf_name[d], pge, j); - gex_dump_contour(ge, clen); - pf->len[d] = 0; - j--; - } - } - } - /* pge points at the last gentry of the line fragment */ - if(j > 1) { /* we have the tail of a fragment left */ - fprintf(stderr, " end of %s frag len=%d %p-", - gxf_name[d], j, pge); - X_FRAG(pge)->len[d] = j; /* the overlapping */ - for(i = 0; j > 0; j--, i++, pge = pge->frwd) - X_FRAG(pge)->lenback[d] = i; - fprintf(stderr, "%p\n", pge->bkwd); - gex_dump_contour(ge, clen); - } else if(j == 1) { - X_FRAG(pge)->lenback[d] = 0; - } -} - -/* - * Produce an outline from a bitmap. - * scale - factor to scale the sizes - * bmap - array of dots by lines, xsz * ysz - * xoff, yoff - offset of the bitmap's lower left corner - * from the logical position (0,0) - */ - -void -bmp_outline( - GLYPH *g, - int scale, - char *bmap, - int xsz, - int ysz, - int xoff, - int yoff -) -{ - char *hlm, *vlm; /* arrays of the limits of outlines */ - char *amp; /* map of ambiguous points */ - int x, y; - char *ip, *op; - double fscale; - - if(xsz==0 || ysz==0) - return; - -#ifdef USE_AUTOTRACE - if(use_autotrace) { - autotraced_bmp_outline(g, scale, bmap, xsz, ysz, xoff, yoff); - return; - } -#endif /*USE_AUTOTRACE*/ - - fscale = (double)scale; - g->flags &= ~GF_FLOAT; /* build it as int first */ - - if(!warnedhints) { - warnedhints = 1; - if(hints && subhints) { - WARNING_2 fprintf(stderr, - "Use of hint substitution on bitmap fonts is not recommended\n"); - } - } - -#if 0 - printbmap(bmap, xsz, ysz, xoff, yoff); -#endif - - /* now find the outlines */ - hlm=calloc( xsz, ysz+1 ); /* horizontal limits */ - vlm=calloc( xsz+1, ysz ); /* vertical limits */ - amp=calloc( xsz, ysz ); /* ambiguous points */ - - if(hlm==0 || vlm==0 || amp==0) { - fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); - exit(255); - } - - /* - * hlm and vlm represent a grid of horisontal and - * vertical lines. Each pixel is surrounded by the grid - * from all the sides. The values of [hv]lm mark the - * parts of grid where the pixel value switches from white - * to black and back. - */ - - /* find the horizontal limits */ - ip=bmap; op=hlm; - /* 1st row */ - for(x=0; x<xsz; x++) { - if(ip[x]) - op[x]=L_ON; - } - ip+=xsz; op+=xsz; - /* internal rows */ - for(y=1; y<ysz; y++) { - for(x=0; x<xsz; x++) { - if(ip[x]) { - if(!ip[x-xsz]) - op[x]=L_ON; - } else { - if(ip[x-xsz]) - op[x]=L_OFF; - } - } - ip+=xsz; op+=xsz; - } - - /* last row */ - ip-=xsz; - for(x=0; x<xsz; x++) { - if(ip[x]) - op[x]=L_OFF; - } - - /* find the vertical limits */ - ip=bmap; op=vlm; - for(y=0; y<ysz; y++) { - if(ip[0]) - op[0]=L_ON; - for(x=1; x<xsz; x++) { - if(ip[x]) { - if(!ip[x-1]) - op[x]=L_ON; - } else { - if(ip[x-1]) - op[x]=L_OFF; - } - } - if(ip[xsz-1]) - op[xsz]=L_OFF; - ip+=xsz; op+=xsz+1; - } - - /* - * Ambiguous points are the nodes of the grids - * that are between two white and two black pixels - * located in a checkerboard style. Actually - * there are only two patterns that may be - * around an ambiguous point: - * - * X|. .|X - * -*- -*- - * .|X X|. - * - * where "|" and "-" represent the grid (respectively members - * of vlm and hlm), "*" represents an ambiguous point - * and "X" and "." represent black and white pixels. - * - * If these sample pattern occur in the lower left corner - * of the bitmap then this ambiguous point will be - * located at amp[1][1] or in other words amp[1*xsz+1]. - * - * These points are named "ambiguous" because it's - * not easy to guess what did the font creator mean - * at these points. So we are going to treat them - * specially, doing no aggressive smoothing. - */ - - /* find the ambiguous points */ - for(y=ysz-1; y>0; y--) - for(x=xsz-1; x>0; x--) { - if(bmap[y*xsz+x]) { - if( !bmap[y*xsz+x-1] && !bmap[y*xsz-xsz+x] && bmap[y*xsz-xsz+x-1] ) - amp[y*xsz+x]=1; - } else { - if( bmap[y*xsz+x-1] && bmap[y*xsz-xsz+x] && !bmap[y*xsz-xsz+x-1] ) - amp[y*xsz+x]=1; - } - } - -#if 0 - printlimits(hlm, vlm, amp, xsz, ysz); -#endif - - /* generate the vectored (stepping) outline */ - - while(1) { - int found = 0; - int outer; /* flag: this is an outer contour */ - int hor, newhor; /* flag: the current contour direction is horizontal */ - int dir; /* previous direction of the coordinate, 1 - L_ON, 0 - L_OFF */ - int startx, starty; /* start of a contour */ - int firstx, firsty; /* start of the current line */ - int newx, newy; /* new coordinates to try */ - char *lm, val; - int maxx, maxy, xor; - - for(y=ysz; !found && y>0; y--) - for(x=0; x<xsz; x++) - if(hlm[y*xsz+x] > L_NONE) - goto foundcontour; - break; /* have no contours left */ - - foundcontour: - ig_rmoveto(g, x+xoff, y+yoff); /* intermediate as int */ - - startx = firstx = x; - starty = firsty = y; - - if(hlm[y*xsz+x] == L_OFF) { - outer = 1; dir = 0; - hlm[y*xsz+x] = -hlm[y*xsz+x]; /* mark as seen */ - hor = 1; x++; - } else { - outer = 0; dir = 0; - hor = 0; y--; - vlm[y*(xsz+1)+x] = -vlm[y*(xsz+1)+x]; /* mark as seen */ - } - - while(x!=startx || y!=starty) { -#if 0 - printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir); -#endif - - /* initialization common for try1 and try2 */ - if(hor) { - lm = vlm; maxx = xsz+1; maxy = ysz; newhor = 0; - } else { - lm = hlm; maxx = xsz; maxy = ysz+1; newhor = 1; - } - xor = (outer ^ hor ^ dir); - - try1: - /* first we try to change axis, to keep the - * contour as long as possible - */ - - newx = x; newy = y; - if(!hor && (!outer ^ dir)) - newx--; - if(hor && (!outer ^ dir)) - newy--; - - if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy) - goto try2; - - if(!xor) - val = L_ON; - else - val = L_OFF; -#if 0 - printf("try 1, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx], - (newhor ? 'h':'v'), newx, newy); -#endif - if( lm[newy*maxx + newx] == val ) - goto gotit; - - try2: - /* try to change the axis anyway */ - - newx = x; newy = y; - if(!hor && (outer ^ dir)) - newx--; - if(hor && (outer ^ dir)) - newy--; - - if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy) - goto try3; - - if(xor) - val = L_ON; - else - val = L_OFF; -#if 0 - printf("try 2, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx], - (newhor ? 'h':'v'), newx, newy); -#endif - if( lm[newy*maxx + newx] == val ) - goto gotit; - - try3: - /* try to continue in the old direction */ - - if(hor) { - lm = hlm; maxx = xsz; maxy = ysz+1; - } else { - lm = vlm; maxx = xsz+1; maxy = ysz; - } - newhor = hor; - newx = x; newy = y; - if(hor && dir) - newx--; - if(!hor && !dir) - newy--; - - if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy) - goto badtry; - - if(dir) - val = L_ON; - else - val = L_OFF; -#if 0 - printf("try 3, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx], - (newhor ? 'h':'v'), newx, newy); -#endif - if( lm[newy*maxx + newx] == val ) - goto gotit; - - badtry: - fprintf(stderr, "**** Internal error in the contour detection code at (%d, %d)\n", x, y); - fprintf(stderr, "glyph='%s' outer=%d hor=%d dir=%d\n", g->name, outer, hor, dir); - fflush(stdout); - exit(1); - - gotit: - if(hor != newhor) { /* changed direction, end the previous line */ - ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */ - firstx = x; firsty = y; - } - lm[newy*maxx + newx] = -lm[newy*maxx + newx]; - hor = newhor; - dir = (val == L_ON); - if(newhor) - x -= (dir<<1)-1; - else - y += (dir<<1)-1; - } -#if 0 - printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir); -#endif - ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */ - g_closepath(g); - } - - - /* try to vectorize the curves and sloped lines in the bitmap */ - if(vectorize) { - GENTRY *ge, *pge, *cge, *loopge; - int i; - int skip; - - dumppaths(g, NULL, NULL); - - /* allocate the extensions */ - for(cge=g->entries; cge!=0; cge=cge->next) { - cge->ext = calloc(1, sizeof(GEX_FRAG) ); - if(cge->ext == 0) { - fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); - exit(255); - } - } - - for(cge=g->entries; cge!=0; cge=cge->next) { - if(cge->type != GE_MOVE) - continue; - - /* we've found the beginning of a contour */ - { - int d, vert, count, stepmore, delaystop; - int vdir, hdir, fullvdir, fullhdir, len; - int dx, dy, lastdx, lastdy; - int k1, k2, reversal, smooth, good; - int line[2 /*H,V*/], maxlen[2 /*H,V*/], minlen[2 /*H,V*/]; - GENTRY **age; /* array of gentries in a contour */ - int clen; /* contour length, size of ths array */ - int i, j; - GEX_FRAG *f; - - /* we know that all the contours start at the top-left corner, - * so at most it might be before/after the last element of - * the last/first fragment - */ - - ge = cge->next; - pge = ge->bkwd; - if(ge->ix3 == pge->ix3) { /* a vertical line */ - /* we want to start always from a horizontal line because - * then we always start from top and that is quaranteed to be a - * fragment boundary, so move the start point of the contour - */ - pge->prev->next = pge->next; - pge->next->prev = pge->prev; - cge->next = pge; - pge->prev = cge; - pge->next = ge; - ge->prev = pge; - ge = pge; pge = ge->bkwd; - cge->ix3 = pge->ix3; cge->iy3 = pge->iy3; - } - - /* fill the array of gentries */ - clen = 1; - for(ge = cge->next->frwd; ge != cge->next; ge = ge->frwd) - clen++; - age = (GENTRY **)malloc(sizeof(*age) * clen); - ge = cge->next; - count = 0; - do { - age[count] = ge; - X_FRAG(ge)->aidx = count++; - - /* and by the way find the extremums */ - for(i=0; i<2; i++) { - if( isign(ge->frwd->ipoints[i][2] - ge->ipoints[i][2]) - * isign(ge->bkwd->bkwd->ipoints[i][2] - ge->bkwd->ipoints[i][2]) == 1) { - X_FRAG(ge)->flags |= GEXFF_EXTR; - fprintf(stderr, " %s extremum at %p\n", (i?"vert":"hor"), ge); - } - if(abs(ge->ipoints[i][2] - ge->bkwd->ipoints[i][2]) > 1) - X_FRAG(ge)->flags |= GEXFF_LONG; - } - - ge = ge->frwd; - } while(ge != cge->next); - - /* Find the serif fragments, looking as either of: - * -+ | - * | | - * +-+ +-+ - * | | - * +--... +--... - * with the thickness of serifs being 1 pixel. We make no - * difference between serifs on vertical and horizontal stems. - */ - - ge = cge->next; - do { - GENTRY *nge; - int pdx, pdy, ndx, ndy; - - /* two gentries of length 1 mean a potential serif */ - pge = ge->bkwd; - nge = ge->frwd; - - dx = nge->ix3 - pge->ix3; - dy = nge->iy3 - pge->iy3; - - if(abs(dx) != 1 || abs(dy) != 1) /* 2 small ones */ - continue; - - if( - (!(X_FRAG(ge)->flags & GEXFF_EXTR) - || !(X_FRAG(ge->bkwd)->flags & GEXFF_EXTR)) - && (!(X_FRAG(ge->frwd)->flags & GEXFF_EXTR) - || !(X_FRAG(ge->frwd->frwd)->flags & GEXFF_EXTR)) - ) - continue; /* either side must be a couple of extremums */ - - pdx = pge->ix3 - pge->bkwd->ix3; - pdy = pge->iy3 - pge->bkwd->iy3; - ndx = nge->frwd->ix3 - nge->ix3; - ndy = nge->frwd->iy3 - nge->iy3; - - if(pdx*dx + pdy*dy > 0 && ndx*dx + ndy*dy > 0) - continue; /* definitely not a serif but a round corner */ - - if(abs(pdx) + abs(pdy) == 1 || abs(ndx) + abs(ndy) == 1) - continue; - - /* we've found a serif including this and next gentry */ - X_FRAG(ge)->len[GEXFI_SERIF] = 2; - - } while( (ge = ge->frwd) != cge->next ); - - - /* Find the convex and concave fragments, defined as: - * convex (clockwise): dy/dx <= dy0/dx0, - * or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx > 0 - * concave (counter-clockwise): dy/dx >= dy0/dx0, - * or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx < 0 - * - * Where dx and dy are measured between the end of this gentry - * and the start of the previous one (dx0 and dy0 are the same - * thing calculated for the previous gentry and its previous one), - * dxthis is between the end and begginning of this gentry. - * - * A reversal is a situation when the curve changes its direction - * along the x axis, so it passes through a momentary vertical - * direction. - */ - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - ge = cge->next; - pge = ge->bkwd; /* the beginning of the fragment */ - count = 1; - lastdx = pge->ix3 - pge->bkwd->bkwd->ix3; - lastdy = pge->iy3 - pge->bkwd->bkwd->iy3; - -#define CHKCURVCONN(ge, msg) do { \ - dx = (ge)->ix3 - (ge)->bkwd->bkwd->ix3; \ - dy = (ge)->iy3 - (ge)->bkwd->bkwd->iy3; \ - if(0 && msg) { \ - fprintf(stderr, " %p: dx=%d dy=%d dx0=%d dy0=%d ", \ - (ge), dx, dy, lastdx, lastdy); \ - } \ - k1 = X_FRAG(ge)->flags; \ - k2 = X_FRAG((ge)->bkwd)->flags; \ - if(0 && msg) { \ - fprintf(stderr, "fl=%c%c%c%c ", \ - (k1 & GEXFF_EXTR) ? 'X' : '-', \ - (k1 & GEXFF_LONG) ? 'L' : '-', \ - (k2 & GEXFF_EXTR) ? 'X' : '-', \ - (k2 & GEXFF_LONG) ? 'L' : '-' \ - ); \ - } \ - if( (k1 & GEXFF_EXTR) && (k2 & GEXFF_LONG) \ - || (k2 & GEXFF_EXTR) && (k1 & GEXFF_LONG) ) { \ - smooth = 0; \ - good = reversal = -1; /* for debugging */ \ - } else { \ - k1 = dy * lastdx; \ - k2 = lastdy * dx; \ - smooth = (abs(dx)==1 || abs(dy)==1); \ - good = (k1 - k2)*gxf_cvk[d] >= 0; \ - if(smooth && !good) { \ - reversal = (k1 == -k2 && abs((ge)->ix3 - (ge)->bkwd->ix3)==1 \ - && dy*dx*gxf_cvk[d] < 0); \ - } else \ - reversal = 0; \ - } \ - if(0 && msg) { \ - fprintf(stderr, "k1=%d k2=%d pge=%p count=%d %s good=%d rev=%d\n", \ - k1, k2, pge, count, gxf_name[d], good, reversal); \ - } \ - } while(0) - - do { - CHKCURVCONN(ge, 1); - - if(smooth && (good || reversal) ) - count++; - else { - /* can't continue */ -#if 0 - if(count >= 4) { /* worth remembering */ - fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); - } -#endif - X_FRAG(pge)->len[d] = count; - if(smooth) { - pge = ge->bkwd; - count = 2; - } else { - pge = ge; - count = 1; - } - } - lastdx = dx; lastdy = dy; - ge = ge->frwd; - } while(ge != cge->next); - - /* see if we can connect the last fragment to the first */ - CHKCURVCONN(ge, 1); - - if(smooth && (good || reversal) ) { - /* -1 to avoid ge->bkwd being counted twice */ - if( X_FRAG(ge->bkwd)->len[d] >= 2 ) - count += X_FRAG(ge->bkwd)->len[d] - 1; - else if(count == clen+1) { - /* we are joining a circular (closed) curve, check whether it - * can be joined at any point or whether it has a discontinuity - * at the point where we join it now - */ - lastdx = dx; lastdy = dy; - CHKCURVCONN(ge->frwd, 0); - - if(smooth && (good || reversal) ) { - /* yes, the curve is truly a circular one and can be - * joined at any point - */ - -#if 0 - fprintf(stderr, " found a circular joint point at %p\n", pge); -#endif - /* make sure that in a circular fragment we start from an extremum */ - while( ! (X_FRAG(pge)->flags & GEXFF_EXTR) ) - pge = pge->frwd; - X_FRAG(pge)->flags |= GEXFF_CIRC; - } - } -#if 0 - fprintf(stderr, " %s joined %p to %p count=%d bk_count=%d\n", gxf_name[d], pge, ge->bkwd, - count, X_FRAG(ge->bkwd)->len[d] ); -#endif - X_FRAG(ge->bkwd)->len[d] = 0; - } - X_FRAG(pge)->len[d] = count; -#if 0 - if(count >= 4) { /* worth remembering */ - fprintf(stderr, " %s last frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); - } -#endif -#undef CHKCURVCONN - - /* do postprocessing */ - ge = cge->next; - do { - f = X_FRAG(ge); - len = f->len[d]; -#if 0 - fprintf(stderr, " %p %s len=%d clen=%d\n", ge, gxf_name[d], len, clen); -#endif - if(len < 3) /* get rid of the fragments that are too short */ - f->len[d] = 0; - else if(len == 3) { - /* _ - * drop the |_| - shaped fragments, leave alone the _| - shaped - * (and even those only if not too short in pixels), - * those left alone are further filtered later - */ - k1 = (ge->ix3 == ge->bkwd->ix3); /* axis of the start */ - if(isign(ge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) - != isign(ge->frwd->ipoints[k1][2] - ge->frwd->frwd->ipoints[k1][2]) - && abs(ge->frwd->frwd->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) > 2) { -#if 0 - fprintf(stderr, " %s frag %p count=%d good shape\n", - gxf_name[d], ge, count); -#endif - } else - f->len[d] = 0; - } else if(len == clen+1) - break; /* a closed fragment, nothing else interesting */ - else { /* only for open fragments */ - GENTRY *gem, *gex, *gei, *ges; - - ges = ge; /* the start entry */ - gem = age[(f->aidx + f->len[d])%clen]; /* entry past the end of the fragment */ - - gei = ge->frwd; - if( (ge->ix3 == ge->bkwd->ix3) /* vert */ - ^ (isign(ge->bkwd->ix3 - gei->ix3)==isign(ge->bkwd->iy3 - gei->iy3)) - ^ !(d == GEXFI_CONVEX) /* counter-clockwise */ ) { - -#if 0 - fprintf(stderr, " %p: %s potential spurious start\n", ge, gxf_name[d]); -#endif - /* the beginning may be a spurious entry */ - - gex = 0; /* the extremum closest to the beginning - to be found */ - for(gei = ge->frwd; gei != gem; gei = gei->frwd) { - if(X_FRAG(gei)->flags & GEXFF_EXTR) { - gex = gei; - break; - } - } - if(gex == 0) - gex = gem->bkwd; - - /* A special case: ignore the spurious ends on small curves that - * either enclose an 1-pixel-wide extremum or are 1-pixel deep. - * Any 5-or-less-pixel-long curve with extremum 2 steps away - * qualifies for that. - */ - - if(len <= 5 && gex == ge->frwd->frwd) { - good = 0; -#if 0 - fprintf(stderr, " E"); -#endif - } else { - good = 1; /* assume that ge is not spurious */ - - /* gei goes backwards, gex goes forwards from the extremum */ - gei = gex; - /* i is the symmetry axis, j is the other axis (X=0 Y=1) */ - i = (gex->ix3 != gex->bkwd->ix3); - j = !i; - for( ; gei!=ge && gex!=gem; gei=gei->bkwd, gex=gex->frwd) { - if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2] - || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2] - != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] - ) { - good = 0; /* no symmetry - must be spurious */ -#if 0 - fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)", - gei, gex, - i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2], - j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2], - gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] ); -#endif - break; - } - } - if(gex == gem) { /* oops, the other side is too short */ - good = 0; -#if 0 - fprintf(stderr, " X"); -#endif - } - if(good && gei == ge) { - if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]) - != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) { - good = 0; /* oops, goes into another direction */ -#if 0 - fprintf(stderr, " D"); -#endif - } - } - } - if(!good) { /* it is spurious, drop it */ -#if 0 - fprintf(stderr, " %p: %s spurious start\n", ge, gxf_name[d]); -#endif - f->len[d] = 0; - ges = ge->frwd; - len--; - X_FRAG(ges)->len[d] = len; - } - } - - gei = gem->bkwd->bkwd->bkwd; - if( (gem->ix3 != gem->bkwd->ix3) /* gem->bkwd is vert */ - ^ (isign(gem->bkwd->ix3 - gei->ix3)==isign(gem->bkwd->iy3 - gei->iy3)) - ^ (d == GEXFI_CONVEX) /* clockwise */ ) { - -#if 0 - fprintf(stderr, " %p: %s potential spurious end\n", gem->bkwd, gxf_name[d]); -#endif - /* the end may be a spurious entry */ - - gex = 0; /* the extremum closest to the end - to be found */ - for(gei = gem->bkwd->bkwd; gei != ges->bkwd; gei = gei->bkwd) { - if(X_FRAG(gei)->flags & GEXFF_EXTR) { - gex = gei; - break; - } - } - if(gex == 0) - gex = ges; - - good = 1; /* assume that gem->bkwd is not spurious */ - /* gei goes backwards, gex goes forwards from the extremum */ - gei = gex; - /* i is the symmetry axis, j is the other axis (X=0 Y=1) */ - i = (gex->ix3 != gex->bkwd->ix3); - j = !i; - for( ; gei!=ges->bkwd && gex!=gem->bkwd; gei=gei->bkwd, gex=gex->frwd) { - if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2] - || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2] - != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] - ) { - good = 0; /* no symmetry - must be spurious */ -#if 0 - fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)", - gei, gex, - i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2], - j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2], - gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] ); -#endif - break; - } - } - if(gei == ges->bkwd) { /* oops, the other side is too short */ - good = 0; -#if 0 - fprintf(stderr, " X"); -#endif - } - if(good && gex == gem->bkwd) { - if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]) - != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) { - good = 0; /* oops, goes into another direction */ -#if 0 - fprintf(stderr, " D"); -#endif - } - } - if(!good) { /* it is spurious, drop it */ -#if 0 - fprintf(stderr, " %p: %s spurious end\n", gem->bkwd, gxf_name[d]); -#endif - X_FRAG(ges)->len[d] = --len; - } - } - if(len < 4) { - X_FRAG(ges)->len[d] = 0; -#if 0 - fprintf(stderr, " %p: %s frag discarded, too small now\n", ge, gxf_name[d]); -#endif - } - if(ges != ge) { - if(ges == cge->next) - break; /* went around the loop */ - else { - ge = ges->frwd; /* don't look at this fragment twice */ - continue; - } - } - } - - ge = ge->frwd; - } while(ge != cge->next); - } - - /* Find the straight line fragments. - * Even though the lines are sloped, they are called - * "vertical" or "horizontal" according to their longer - * dimension. All the steps in the shother dimension must - * be 1 pixel long, all the steps in the longer dimension - * must be within the difference of 1 pixel. - */ - for(d = GEXFI_LINE; d<= GEXFI_EXACTLINE; d++) { - ge = cge->next; - pge = ge->bkwd; /* the beginning of the fragment */ - count = 1; - delaystop = 0; - do { - int h; - - stepmore = 0; - hdir = isign(ge->ix3 - ge->bkwd->ix3); - vdir = isign(ge->iy3 - ge->bkwd->iy3); - vert = (hdir == 0); - if(count==1) { - /* at this point pge==ge->bkwd */ - /* account for the previous gentry, which was !vert */ - if(!vert) { /* prev was vertical */ - maxlen[0] = minlen[0] = 0; - maxlen[1] = minlen[1] = abs(pge->iy3 - pge->bkwd->iy3); - line[0] = (maxlen[1] == 1); - line[1] = 1; - fullhdir = hdir; - fullvdir = isign(pge->iy3 - pge->bkwd->iy3); - } else { - maxlen[0] = minlen[0] = abs(pge->ix3 - pge->bkwd->ix3); - maxlen[1] = minlen[1] = 0; - line[0] = 1; - line[1] = (maxlen[0] == 1); - fullhdir = isign(pge->ix3 - pge->bkwd->ix3); - fullvdir = vdir; - } - } - h = line[0]; /* remember the prevalent direction */ -#if 0 - fprintf(stderr, " %p: v=%d(%d) h=%d(%d) vl(%d,%d,%d) hl=(%d,%d,%d) %s count=%d ", - ge, vdir, fullvdir, hdir, fullhdir, - line[1], minlen[1], maxlen[1], - line[0], minlen[0], maxlen[0], - gxf_name[d], count); -#endif - if(vert) { - if(vdir != fullvdir) - line[0] = line[1] = 0; - len = abs(ge->iy3 - ge->bkwd->iy3); - } else { - if(hdir != fullhdir) - line[0] = line[1] = 0; - len = abs(ge->ix3 - ge->bkwd->ix3); - } -#if 0 - fprintf(stderr, "len=%d\n", len); -#endif - if(len != 1) /* this is not a continuation in the short dimension */ - line[!vert] = 0; - - /* can it be a continuation in the long dimension ? */ - if( line[vert] ) { - if(maxlen[vert]==0) - maxlen[vert] = minlen[vert] = len; - else if(maxlen[vert]==minlen[vert]) { - if(d == GEXFI_EXACTLINE) { - if(len != maxlen[vert]) - line[vert] = 0; /* it can't */ - } else if(len < maxlen[vert]) { - if(len < minlen[vert]-1) - line[vert] = 0; /* it can't */ - else - minlen[vert] = len; - } else { - if(len > maxlen[vert]+1) - line[vert] = 0; /* it can't */ - else - maxlen[vert] = len; - } - } else if(len < minlen[vert] || len > maxlen[vert]) - line[vert] = 0; /* it can't */ - } - - if(line[0] == 0 && line[1] == 0) { -#if 0 - if(count >= 3) - fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); -#endif - X_FRAG(pge)->len[d] = count; - if(d == GEXFI_EXACTLINE && h) { - X_FRAG(pge)->flags |= GEXFF_HLINE; - } - if(count == 1) - pge = ge; - else { - stepmore = 1; /* may reconsider the 1st gentry */ - pge = ge = ge->bkwd; - count = 1; - } - } else - count++; - - ge = ge->frwd; - if(ge == cge->next && !stepmore) - delaystop = 1; /* consider the first gentry again */ - } while(stepmore || ge != cge->next ^ delaystop); - /* see if there is an unfinished line left */ - if(count != 1) { -#if 0 - if(count >= 3) - fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); -#endif - X_FRAG(ge->bkwd->bkwd)->len[d] = 0; - X_FRAG(pge)->len[d] = count; - } - } - - /* do postprocessing of the lines */ -#if 0 - fprintf(stderr, "Line postprocessing\n"); - gex_dump_contour(cge->next, clen); -#endif - - /* the non-exact line frags are related to exact line frags sort - * of like to individual gentries: two kinds of exact frags - * must be interleaved, with one kind having the size of 3 - * and the other kind having the size varying within +-2. - */ - - ge = cge->next; - do { - GEX_FRAG *pf, *lastf1, *lastf2; - int len1, len2, fraglen; - - f = X_FRAG(ge); - - fraglen = f->len[GEXFI_LINE]; - if(fraglen >= 4) { - - vert = 0; /* vert is a pseudo-directon */ - line[0] = line[1] = 1; - maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0; - lastf2 = lastf1 = f; - len2 = len1 = 0; - for(pge = ge, i = 1; i < fraglen; i++, pge=pge->frwd) { - pf = X_FRAG(pge); - len = pf->len[GEXFI_EXACTLINE]; -#if 0 - fprintf(stderr, " pge=%p i=%d of %d ge=%p exLen=%d\n", pge, i, - f->len[GEXFI_LINE], ge, len); -#endif - len1++; len2++; - if(len==0) { - continue; - } - vert = !vert; /* alternate the pseudo-direction */ - if(len > 3) - line[!vert] = 0; - if(maxlen[vert] == 0) - maxlen[vert] = minlen[vert] = len; - else if(maxlen[vert]-2 >= len && minlen[vert]+2 <= len) { - if(len > maxlen[vert]) - maxlen[vert] = len; - else if(len < minlen[vert]) - minlen[vert] = len; - } else - line[vert] = 0; - if(line[0] == 0 && line[1] == 0) { -#if 0 - fprintf(stderr, " Line breaks at %p %c(%d, %d) %c(%d, %d) len=%d fl=%d l2=%d l1=%d\n", - pge, (!vert)?'*':' ', minlen[0], maxlen[0], - vert?'*':' ', minlen[1], maxlen[1], len, fraglen, len2, len1); -#endif - if(lastf2 != lastf1) { - lastf2->len[GEXFI_LINE] = len2-len1; - } - lastf1->len[GEXFI_LINE] = len1+1; - pf->len[GEXFI_LINE] = fraglen+1 - i; -#if 0 - gex_dump_contour(pge, clen); -#endif - - /* continue with the line */ - vert = 0; /* vert is a pseudo-directon */ - line[0] = line[1] = 1; - maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0; - lastf2 = lastf1 = f; - len2 = len1 = 0; - } else { - lastf1 = pf; - len1 = 0; - } - } - } - - ge = ge->frwd; - } while(ge != cge->next); -#if 0 - fprintf(stderr, "Line postprocessing part 2\n"); - gex_dump_contour(cge->next, clen); -#endif - - ge = cge->next; - do { - f = X_FRAG(ge); - - if(f->len[GEXFI_LINE] >= 4) { - len = f->len[GEXFI_EXACTLINE]; - /* if a non-exact line covers precisely two exact lines, - * split it - */ - if(len > 0 && f->len[GEXFI_LINE] >= len+1) { - GEX_FRAG *pf; - pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */ - pf = X_FRAG(pge); - if(f->len[GEXFI_LINE] + 1 == len + pf->len[GEXFI_EXACTLINE]) { - f->len[GEXFI_LINE] = len; - f->flags |= GEXFF_SPLIT; - pf->len[GEXFI_LINE] = pf->len[GEXFI_EXACTLINE]; - pf->flags |= GEXFF_SPLIT; - } - } - } - - ge = ge->frwd; - } while(ge != cge->next); -#if 0 - fprintf(stderr, "Line postprocessing part 2a\n"); - gex_dump_contour(cge->next, clen); -#endif - ge = cge->next; - do { - f = X_FRAG(ge); - - /* too small lines are of no interest */ - if( (f->flags & GEXFF_SPLIT)==0 && f->len[GEXFI_LINE] < 4) - f->len[GEXFI_LINE] = 0; - - len = f->len[GEXFI_EXACTLINE]; - /* too small exact lines are of no interest */ - if(len < 3) /* exact lines may be shorter */ - f->len[GEXFI_EXACTLINE] = 0; - /* get rid of inexact additions to the end of the exact lines */ - else if(f->len[GEXFI_LINE] == len+1) - f->len[GEXFI_LINE] = len; - /* same at the beginning */ - else { - int diff = X_FRAG(ge->bkwd)->len[GEXFI_LINE] - len; - - if(diff == 1 || diff == 2) { - X_FRAG(ge->bkwd)->len[GEXFI_LINE] = 0; - f->len[GEXFI_LINE] = len; - } - } - - ge = ge->frwd; - } while(ge != cge->next); -#if 0 - fprintf(stderr, "Line postprocessing is completed\n"); - gex_dump_contour(cge->next, clen); -#endif - - gex_calc_lenback(cge->next, clen); /* prepare data */ - - /* resolve conflicts between lines and curves */ - - /* - * the short (3-gentry) curve frags must have one of the ends - * coinciding with another curve frag of the same type - */ - - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - ge = cge->next; - do { - f = X_FRAG(ge); - - if(f->len[d] == 3) { - pge = age[(f->aidx + 2)%clen]; /* last gentry of this frag */ - if(f->lenback[d] == 0 && X_FRAG(pge)->len[d] == 0) { - fprintf(stderr, " discarded small %s at %p-%p\n", gxf_name[d], ge, pge); - f->len[d] = 0; - X_FRAG(ge->frwd)->lenback[d] = 0; - X_FRAG(ge->frwd->frwd)->lenback[d] = 0; - } - } - ge = ge->frwd; - } while(ge != cge->next); - } - - /* the serifs take priority over everything else */ - ge = cge->next; - do { - f = X_FRAG(ge); - - len = f->len[GEXFI_SERIF]; - if(len == 0) - continue; - - if(len != 2) { /* this is used in the code below */ - fprintf(stderr, "Internal error at %s line %d: serif frags len is %d\n", - __FILE__, __LINE__, len); - exit(1); - } - - for(d = 0; d < GEXFI_SERIF; d++) { - /* serifs may not have common ends with the other fragments, - * this is expressed as extending them by 1 gentry on each side - */ - frag_subtract(g, age, clen, ge->bkwd, len+2, d); - } - } while( (ge = ge->frwd) != cge->next); - - /* - * longer exact lines take priority over curves; shorter lines - * and inexact lines are resolved with convex/concave conflicts - */ - ge = cge->next; - do { - f = X_FRAG(ge); - - len = f->len[GEXFI_EXACTLINE]; - - if(len < 6) { /* line is short */ - ge = ge->frwd; - continue; - } - - fprintf(stderr, " line at %p len=%d\n", ge, f->len[GEXFI_EXACTLINE]); - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - frag_subtract(g, age, clen, ge, len, d); - } - - ge = ge->frwd; - } while(ge != cge->next); - - /* - * The exact lines take priority over curves that coincide - * with them or extend by only one gentry on either side - * (but not both sides). By this time it applies only to the - * small exact lines. - * - * An interesting general case is when a curve matches more - * than one exact line going diamond-like. - */ - - ge = cge->next; - do { - int done, len2; - int sharpness; - GEX_FRAG *pf; - - f = X_FRAG(ge); - - /* "sharpness" shows how a group of exact line frags is connected: if the gentries - * of some of them overlap, the curve matching requirement is loosened: it may - * extend up to 1 gentry beyond each end of the group of exact line frags - * (sharpness=2); otherwise it may extend to only one end (sharpness=1) - */ - sharpness = 1; - - len = f->len[GEXFI_EXACTLINE]; - if(len >= 4) { - while(len < clen) { - done = 0; - pf = X_FRAG(ge->bkwd); - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - if(f->len[d] == len || f->len[d] == len+1) { - - fprintf(stderr, " removed %s frag at %p len=%d linelen=%d\n", - gxf_name[d], ge, f->len[d], len); - pge = ge->frwd; - for(i = f->len[d]; i > 1; i--, pge = pge->frwd) - X_FRAG(pge)->lenback[d] = 0; - f->len[d] = 0; - gex_dump_contour(ge, clen); - done = 1; - } else if(pf->len[d] == len+1 || pf->len[d] == len+sharpness) { - fprintf(stderr, " removed %s frag at %p len=%d next linelen=%d\n", - gxf_name[d], ge->bkwd, pf->len[d], len); - pge = ge; - for(i = pf->len[d]; i > 1; i--, pge = pge->frwd) - X_FRAG(pge)->lenback[d] = 0; - pf->len[d] = 0; - gex_dump_contour(ge, clen); - done = 1; - } - } - if(done) - break; - - /* is there any chance to match a sequence of exect lines ? */ - if(f->len[GEXFI_CONVEX] < len && f->len[GEXFI_CONCAVE] < len - && pf->len[GEXFI_CONVEX] < len && pf->len[GEXFI_CONCAVE] < len) - break; - - done = 1; - /* check whether the line is connected to another exact line at an extremum */ - pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */ - len2 = X_FRAG(pge)->len[GEXFI_EXACTLINE]; - if(len2 > 0) { - if( len2 >= 4 && (X_FRAG(pge)->flags & GEXFF_EXTR) ) { - len += len2 - 1; - sharpness = 2; - done = 0; - } - } else { - /* see if the extremum is between two exact lines */ - pge = pge->frwd; - if(X_FRAG(pge)->flags & GEXFF_EXTR) { - pge = pge->frwd; - len2 = X_FRAG(pge)->len[GEXFI_EXACTLINE]; - if(len2 >= 4) { - len += len2 + 1; - done = 0; - } - } - } - if(done) - break; - } - } - - ge = ge->frwd; - } while(ge != cge->next); - - /* - * The lines may cover only whole curves (or otherwise empty space), - * so cut them where they overlap parts of the curves. If 2 or less - * gentries are left in the line, remove the line. - * If a line and a curve fully coincide, remove the line. Otherwise - * remove the curves that are completely covered by the lines. - */ - - ge = cge->next; - do { - f = X_FRAG(ge); - - reconsider_line: - len = f->len[GEXFI_LINE]; - - if(len == 0) { - ge = ge->frwd; - continue; - } - - if(f->len[GEXFI_CONVEX] >= len - || f->len[GEXFI_CONCAVE] >= len) { - line_completely_covered: - fprintf(stderr, " removed covered Line frag at %p len=%d\n", - ge, len); - f->len[GEXFI_LINE] = 0; - for(pge = ge->frwd; len > 1; len--, pge = pge->frwd) - X_FRAG(pge)->lenback[GEXFI_LINE] = 0; - gex_dump_contour(ge, clen); - ge = ge->frwd; - continue; - } - - k1 = 0; /* how much to cut at the front */ - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - if(f->lenback[d]) { - pge = age[(f->aidx + clen - f->lenback[d])%clen]; - i = X_FRAG(pge)->len[d] - f->lenback[d] - 1; - if(i > k1) - k1 = i; - } - } - - k2 = 0; /* how much to cut at the end */ - pge = age[(f->aidx + len)%clen]; /* gentry after the end */ - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - i = X_FRAG(pge)->lenback[d] - 1; - if(i > k2) - k2 = i; - } - - if(k1+k2 > 0 && k1+k2 >= len-3) { - fprintf(stderr, " k1=%d k2=%d\n", k1, k2); - goto line_completely_covered; - } - - - if(k2 != 0) { /* cut the end */ - len -= k2; - f->len[GEXFI_LINE] = len; - /* pge still points after the end */ - for(i = k2, pge = pge->bkwd; i > 0; i--, pge = pge->bkwd) - X_FRAG(pge)->lenback[GEXFI_LINE] = 0; - } - if(k1 != 0) { /* cut the beginning */ - len -= k1; - f->len[GEXFI_LINE] = 0; - for(i = 1, pge = ge->frwd; i < k1; i++, pge = pge->frwd) - X_FRAG(pge)->lenback[GEXFI_LINE] = 0; - X_FRAG(pge)->len[GEXFI_LINE] = len; - for(i = 0; i < len; i++, pge = pge->frwd) - X_FRAG(pge)->lenback[GEXFI_LINE] = i; - } - if(k1 != 0 || k2 != 0) { - fprintf(stderr, " cut Line frag at %p by (%d,%d) to len=%d\n", - ge, k1, k2, len); - gex_dump_contour(ge, clen); - - goto reconsider_line; /* the line may have to be cut again */ - } - pge = age[(f->aidx + k1)%clen]; /* new beginning */ - good = 1; /* flag: no need do do a debugging dump */ - for(i=1; i<len; i++, pge = pge->frwd) - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - if(X_FRAG(pge)->len[d]) { - fprintf(stderr, " removed %s frag at %p len=%d covered by line\n", - gxf_name[d], pge, X_FRAG(pge)->len[d], len); - good = 0; - } - X_FRAG(pge)->len[d] = 0; - } - pge = age[(f->aidx + k1 + 1)%clen]; /* next after new beginning */ - for(i=1; i<len; i++, pge = pge->frwd) - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) - X_FRAG(pge)->lenback[d] = 0; - if(!good) - gex_dump_contour(ge, clen); - - ge = ge->frwd; - } while(ge != cge->next); - - /* Resolve conflicts between curves */ - for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { - dx = (GEXFI_CONVEX + GEXFI_CONCAVE) - d; /* the other type */ - ge = cge->next; - do { - GENTRY *sge; - - f = X_FRAG(ge); - len = f->len[d]; - if(len < 2) { - ge = ge->frwd; - continue; - } - sge = ge; /* the start of fragment */ - - i = f->len[dx]; - if(i != 0) { /* two curved frags starting here */ - /* should be i!=len because otherwise they would be - * covered by an exact line - */ - if(i > len) { - curve_completely_covered: - /* remove the convex frag */ - fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n", - gxf_name[d], ge, len, gxf_name[dx]); - f->len[d] = 0; - for(pge = ge->frwd, j = 1; j < len; j++, pge = pge->frwd) - X_FRAG(pge)->lenback[d] = 0; - gex_dump_contour(ge, clen); - - ge = ge->frwd; /* the frag is gone, nothing more to do */ - continue; - } else { - /* remove the concave frag */ - fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n", - gxf_name[dx], ge, i, gxf_name[d]); - f->len[dx] = 0; - for(pge = ge->frwd, j = 1; j < i; j++, pge = pge->frwd) - X_FRAG(pge)->lenback[dx] = 0; - gex_dump_contour(ge, clen); - } - } - - - k1 = X_FRAG(ge->frwd)->lenback[dx]; - if(k1 != 0) { /* conflict at the front */ - GENTRY *gels, *gele, *gei; - - pge = age[(f->aidx + clen - (k1-1))%clen]; /* first gentry of concave frag */ - k2 = X_FRAG(pge)->len[dx]; /* its length */ - - i = k2 - (k1-1); /* amount of overlap */ - if(i > len) - i = len; - /* i >= 2 by definition */ - if(i >= k2-1) { /* covers the other frag - maybe with 1 gentry showing */ - fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n", - gxf_name[dx], pge, k2, gxf_name[d]); - X_FRAG(pge)->len[dx] = 0; - for(pge = pge->frwd, j = 1; j < k2; j++, pge = pge->frwd) - X_FRAG(pge)->lenback[dx] = 0; - if(i >= len-1) { /* covers our frag too - maybe with 1 gentry showing */ - /* our frag will be removed as well, prepare a line to replace it */ - gels = ge; - gele = age[(f->aidx + i - 1)%clen]; - fprintf(stderr, " new Line frag at %p-%p len=%d\n", gels, gele, i); - X_FRAG(gels)->len[GEXFI_LINE] = i; - for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++) - X_FRAG(gei)->lenback[GEXFI_LINE] = j; - } else { - gex_dump_contour(ge, clen); - ge = ge->frwd; - continue; - } - } - if(i >= len-1) /* covers our frag - maybe with 1 gentry showing */ - goto curve_completely_covered; - - /* XXX need to do something better for the case when a curve frag - * is actually nothing but an artifact of two other curves of - * the opposite type touching each other, like on the back of "3" - */ - - /* change the overlapping part to a line */ - gels = ge; - gele = age[(f->aidx + i - 1)%clen]; - /* give preference to local extremums */ - if(X_FRAG(gels)->flags & GEXFF_EXTR) { - gels = gels->frwd; - i--; - } - if(X_FRAG(gele)->flags & GEXFF_EXTR) { - gele = gele->bkwd; - i--; - } - if(gels->bkwd == gele) { - /* Oops the line became negative. Probably should - * never happen but I can't think of any formal reasoning - * leading to that, so check just in case. Restore - * the previous state. - */ - gels = gele; gele = gels->frwd; i = 2; - } - - j = X_FRAG(gels)->lenback[dx] + 1; /* new length */ - if(j != k2) { - X_FRAG(pge)->len[dx] = j; - fprintf(stderr, " cut %s frag at %p len=%d to %p len=%d end overlap with %s\n", - gxf_name[dx], pge, k2, gels, j, gxf_name[d]); - for(gei = gels->frwd; j < k2; gei = gei->frwd, j++) - X_FRAG(gei)->lenback[dx] = 0; - } - - if(gele != ge) { - sge = gele; - f->len[d] = 0; - fprintf(stderr, " cut %s frag at %p len=%d ", gxf_name[d], ge, len); - len--; - for(gei = ge->frwd; gei != gele; gei = gei->frwd, len--) - X_FRAG(gei)->lenback[d] = 0; - X_FRAG(gele)->len[d] = len; - X_FRAG(gele)->lenback[d] = 0; - fprintf(stderr, "to %p len=%d start overlap with %s\n", - sge, len, gxf_name[dx]); - for(gei = gei->frwd, j = 1; j < len; gei = gei->frwd, j++) - X_FRAG(gei)->lenback[d] = j; - - } - if(i > 1) { - fprintf(stderr, " new Line frag at %p-%p len=%d\n", gels, gele, i); - X_FRAG(gels)->len[GEXFI_LINE] = i; - for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++) - X_FRAG(gei)->lenback[GEXFI_LINE] = j; - } - gex_dump_contour(ge, clen); - } - - ge = ge->frwd; - } while(ge != cge->next); - } - - /* - * Assert that there are no conflicts any more and - * for each gentry find the fragment types that start - * and continue here. - */ - ge = cge->next; - do { - f = X_FRAG(ge); - dx = GEXFI_NONE; /* type that starts here */ - dy = GEXFI_NONE; /* type that goes through here */ - /* GEXFI_EXACTLINE and GEXFI_SERIF are auxiliary and don't - * generate any actual lines/curves in the result - */ - for(d = GEXFI_CONVEX; d<= GEXFI_LINE; d++) { - if(f->len[d]) { - if(dx >= 0) { - fprintf(stderr, "**** Internal error in vectorization\n"); - fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n", - g->name, ge, gxf_name[dx], gxf_name[d]); - dumppaths(g, cge->next, cge->next->bkwd); - gex_dump_contour(ge, clen); - exit(1); - } - dx = d; - } - if(f->lenback[d]) { - if(dy >= 0) { - fprintf(stderr, "**** Internal error in vectorization\n"); - fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n", - g->name, ge, gxf_name[dy], gxf_name[d]); - dumppaths(g, cge->next, cge->next->bkwd); - gex_dump_contour(ge, clen); - exit(1); - } - dy = d; - } - } - f->ixstart = dx; - f->ixcont = dy; - ge = ge->frwd; - } while(ge != cge->next); - - /* - * make sure that the contour does not start in the - * middle of a fragment - */ - ge = cge->next; /* old start of the contour */ - f = X_FRAG(ge); - if(f->ixstart == GEXFI_NONE && f->ixcont != GEXFI_NONE) { - /* oops, it's mid-fragment, move the start */ - GENTRY *xge; - - xge = ge->bkwd->next; /* entry following the contour */ - - /* find the first gentry of this frag */ - pge = age[(f->aidx + clen - f->lenback[f->ixcont])%clen]; - - ge->prev = ge->bkwd; - ge->bkwd->next = ge; - - cge->next = pge; - pge->prev = cge; - - pge->bkwd->next = xge; - if(xge) - xge->prev = pge->bkwd; - - cge->ix3 = pge->bkwd->ix3; cge->iy3 = pge->bkwd->iy3; - } - - /* vectorize each fragment separately - * make 2 passes: first handle the straight lines, then - * the curves to allow the curver to be connected smoothly - * to the straights - */ - ge = cge->next; - do { /* pass 1 */ - f = X_FRAG(ge); - switch(f->ixstart) { - case GEXFI_LINE: - len = f->len[GEXFI_LINE]; - pge = age[(f->aidx + len - 1)%clen]; /* last gentry */ - - if(ge->iy3 == ge->bkwd->iy3) { /* frag starts and ends horizontally */ - k1 = 1/*Y*/ ; /* across the direction of start */ - k2 = 0/*X*/ ; /* along the direction of start */ - } else { /* frag starts and ends vertically */ - k1 = 0/*X*/ ; /* across the direction of start */ - k2 = 1/*Y*/ ; /* along the direction of start */ - } - - if(len % 2) { - /* odd number of entries in the frag */ - double halfstep, halfend; - - f->vect[0][k1] = fscale * ge->ipoints[k1][2]; - f->vect[3][k1] = fscale * pge->ipoints[k1][2]; - - halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) - * 0.5 / ((len+1)/2); - if(f->ixcont != GEXFI_NONE) { - halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5; - if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ - halfstep = halfend; - } - if(X_FRAG(pge)->ixstart != GEXFI_NONE) { - halfend = (pge->ipoints[k2][2] - pge->bkwd->ipoints[k2][2]) * 0.5; - if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ - halfstep = halfend; - } - f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep); - f->vect[3][k2] = fscale * (pge->ipoints[k2][2] - halfstep); - } else { - /* even number of entries */ - double halfstep, halfend; - - f->vect[0][k1] = fscale * ge->ipoints[k1][2]; - halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) - * 0.5 / (len/2); - if(f->ixcont != GEXFI_NONE) { - halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5; - if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ - halfstep = halfend; - } - f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep); - - halfstep = (pge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) - * 0.5 / (len/2); - if(X_FRAG(pge)->ixstart != GEXFI_NONE) { - halfend = (pge->ipoints[k1][2] - pge->bkwd->ipoints[k1][2]) * 0.5; - if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ - halfstep = halfend; - } - f->vect[3][k1] = fscale * (pge->ipoints[k1][2] - halfstep); - f->vect[3][k2] = fscale * pge->ipoints[k2][2]; - } - f->vectlen = len; - f->flags |= GEXFF_DRAWLINE; - break; - } - } while((ge = ge->frwd) != cge->next); - - ge = cge->next; - do { /* pass 2 */ - /* data for curves */ - GENTRY *firstge, *lastge, *gef, *gel, *gei, *gex; - GENTRY *ordhd; /* head of the order list */ - GENTRY **ordlast; - int nsub; /* number of subfrags */ - GEX_FRAG *ff, *lf, *xf; - - f = X_FRAG(ge); - switch(f->ixstart) { - case GEXFI_CONVEX: - case GEXFI_CONCAVE: - len = f->len[f->ixstart]; - firstge = ge; - lastge = age[(f->aidx + len - 1)%clen]; /* last gentry */ - - nsub = 0; - gex = firstge; - xf = X_FRAG(gex); - xf->prevsub = 0; - xf->sublen = 1; - xf->flags &= ~GEXFF_DONE; - for(gei = firstge->frwd; gei != lastge; gei = gei->frwd) { - xf->sublen++; - if(X_FRAG(gei)->flags & GEXFF_EXTR) { - xf->nextsub = gei; - for(i=0; i<2; i++) - xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]); - nsub++; - xf = X_FRAG(gei); - xf->prevsub = gex; - xf->sublen = 1; - xf->flags &= ~GEXFF_DONE; - gex = gei; - } - } - xf->sublen++; - xf->nextsub = gei; - for(i=0; i<2; i++) - xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]); - nsub++; - ff = xf; /* remember the beginning of the last subfrag */ - xf = X_FRAG(gei); - xf->prevsub = gex; - if(firstge != lastge) { - xf->nextsub = 0; - xf->sublen = 0; - - /* correct the bounding box of the last and first subfrags for - * intersections with other fragments - */ - if(xf->ixstart != GEXFI_NONE) { - /* ff points to the beginning of the last subfrag */ - for(i=0; i<2; i++) - ff->bbox[i] -= 0.5 * abs(lastge->ipoints[i][2] - lastge->bkwd->ipoints[i][2]); - } - ff = X_FRAG(firstge); - if(ff->ixcont != GEXFI_NONE) { - for(i=0; i<2; i++) - ff->bbox[i] -= 0.5 * abs(firstge->ipoints[i][2] - firstge->bkwd->ipoints[i][2]); - } - } - - fprintf(stderr, " %s frag %p%s nsub=%d\n", gxf_name[f->ixstart], - ge, (f->flags&GEXFF_CIRC)?" circular":"", nsub); - - /* find the symmetry between the subfragments */ - for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { - ff = X_FRAG(gef); - gex = ff->nextsub; - xf = X_FRAG(gex); - gel = xf->nextsub; - if(gel == 0) { - ff->flags &= ~GEXFF_SYMNEXT; - break; /* not a circular frag */ - } - good = 1; /* assume that we have symmetry */ - /* gei goes backwards, gex goes forwards from the extremum */ - gei = gex; - /* i is the symmetry axis, j is the other axis (X=0 Y=1) */ - ff->symaxis = i = (gex->ix3 != gex->bkwd->ix3); - j = !i; - for( ; gei!=gef && gex!=gel; gei=gei->bkwd, gex=gex->frwd) { - if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2] - || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2] - != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] - ) { - good = 0; /* no symmetry */ - break; - } - } - if(good) { - if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]) - != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) { - good = 0; /* oops, goes into another direction */ - } - } - if(good) - ff->flags |= GEXFF_SYMNEXT; - else - ff->flags &= ~GEXFF_SYMNEXT; - } - - for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { - ff = X_FRAG(gef); - if((ff->flags & GEXFF_SYMNEXT)==0) { - ff->symxlen = 0; - continue; - } - gex = ff->prevsub; - if(gex == 0 || (X_FRAG(gex)->flags & GEXFF_SYMNEXT)==0) { - ff->symxlen = 0; - continue; - } - ff->symxlen = X_FRAG(gex)->sublen; - xf = X_FRAG(ff->nextsub); - if(xf->sublen < ff->symxlen) - ff->symxlen = xf->sublen; - } - - /* find the symmetry inside the subfragments */ - for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { - ff = X_FRAG(gef); - - if(ff->sublen % 2) { - /* we must have an even number of gentries for diagonal symmetry */ - ff->symge = 0; - continue; - } - - /* gei goes forwards from the front */ - gei = gef->frwd; - /* gex goes backwards from the back */ - gex = ff->nextsub->bkwd; - - /* i is the direction of gei, j is the direction of gex */ - i = (gei->iy3 != gei->bkwd->iy3); - j = !i; - for( ; gei->bkwd != gex; gei=gei->frwd, gex=gex->bkwd) { - if( abs(gei->bkwd->ipoints[i][2] - gei->ipoints[i][2]) - != abs(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) - break; /* no symmetry */ - i = j; - j = !j; - } - if(gei->bkwd == gex) - ff->symge = gex; - else - ff->symge = 0; /* no symmetry */ - } - - /* find the order of calculation: - * prefer to start from long fragments that have the longest - * neighbours symmetric with them, with all being equal prefer - * the fragments that have smaller physical size - */ - ordhd = 0; - for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { - ff = X_FRAG(gef); - - for(ordlast = &ordhd; *ordlast != 0; ordlast = &xf->ordersub) { - xf = X_FRAG(*ordlast); - if(ff->sublen > xf->sublen) - break; - if(ff->sublen < xf->sublen) - continue; - if(ff->symxlen > xf->symxlen) - break; - if(ff->symxlen < xf->symxlen) - continue; - if(ff->bbox[0] < xf->bbox[0] || ff->bbox[1] < xf->bbox[1]) - break; - } - - ff->ordersub = *ordlast; - *ordlast = gef; - } - - /* vectorize the subfragments */ - for(gef = ordhd; gef != 0; gef = ff->ordersub) { - - /* debugging stuff */ - ff = X_FRAG(gef); - fprintf(stderr, " %p-%p bbox[%g,%g] sym=%p %s len=%d xlen=%d\n", - gef, ff->nextsub, ff->bbox[0], ff->bbox[1], ff->symge, - (ff->flags & GEXFF_SYMNEXT) ? "symnext" : "", - ff->sublen, ff->symxlen); - - dosubfrag(g, f->ixstart, firstge, gef, fscale); - } - - break; - } - } while((ge = ge->frwd) != cge->next); - - free(age); - - } - - } - - /* all the fragments are found, extract the vectorization */ - pge = g->entries; - g->entries = g->lastentry = 0; - g->flags |= GF_FLOAT; - loopge = 0; - skip = 0; - - for(ge = pge; ge != 0; ge = ge->next) { - GEX_FRAG *f, *pf; - - switch(ge->type) { - case GE_LINE: - f = X_FRAG(ge); - if(skip == 0) { - if(f->flags & (GEXFF_DRAWLINE|GEXFF_DRAWCURVE)) { - /* draw a line to the start point */ - fg_rlineto(g, f->vect[0][0], f->vect[0][1]); - /* draw the fragment */ - if(f->flags & GEXFF_DRAWCURVE) - fg_rrcurveto(g, - f->vect[1][0], f->vect[1][1], - f->vect[2][0], f->vect[2][1], - f->vect[3][0], f->vect[3][1]); - else - fg_rlineto(g, f->vect[3][0], f->vect[3][1]); - skip = f->vectlen - 2; - } else { - fg_rlineto(g, fscale * ge->ix3, fscale * ge->iy3); - } - } else - skip--; - break; - case GE_MOVE: - fg_rmoveto(g, -1e6, -1e6); /* will be fixed by GE_PATH */ - skip = 0; - /* remember the reference to update it later */ - loopge = g->lastentry; - break; - case GE_PATH: - /* update the first MOVE of this contour */ - if(loopge) { - loopge->fx3 = g->lastentry->fx3; - loopge->fy3 = g->lastentry->fy3; - loopge = 0; - } - g_closepath(g); - break; - } - } - for(ge = pge; ge != 0; ge = cge) { - cge = ge->next; - free(ge->ext); - free(ge); - } - dumppaths(g, NULL, NULL); - - /* end of vectorization logic */ - } else { - /* convert the data to float */ - GENTRY *ge; - double x, y; - - for(ge = g->entries; ge != 0; ge = ge->next) { - ge->flags |= GEF_FLOAT; - if(ge->type != GE_MOVE && ge->type != GE_LINE) - continue; - - x = fscale * ge->ix3; - y = fscale * ge->iy3; - - ge->fx3 = x; - ge->fy3 = y; - } - g->flags |= GF_FLOAT; - } - - free(hlm); free(vlm); free(amp); -} - -#if 0 -/* print out the bitmap */ -printbmap(bmap, xsz, ysz, xoff, yoff) - char *bmap; - int xsz, ysz, xoff, yoff; -{ - int x, y; - - for(y=ysz-1; y>=0; y--) { - putchar( (y%10==0) ? y/10+'0' : ' ' ); - putchar( y%10+'0' ); - for(x=0; x<xsz; x++) - putchar( bmap[y*xsz+x] ? 'X' : '.' ); - if(-yoff==y) - putchar('_'); /* mark the baseline */ - putchar('\n'); - } - putchar(' '); putchar(' '); - for(x=0; x<xsz; x++) - putchar( x%10+'0' ); - putchar('\n'); putchar(' '); putchar(' '); - for(x=0; x<xsz; x++) - putchar( (x%10==0) ? x/10+'0' : ' ' ); - putchar('\n'); -} - -/* print out the limits of outlines */ -printlimits(hlm, vlm, amp, xsz, ysz) - char *hlm, *vlm, *amp; - int xsz, ysz; -{ - int x, y; - static char h_char[]={ ' ', '~', '^' }; - static char v_char[]={ ' ', '(', ')' }; - - for(y=ysz-1; y>=0; y--) { - for(x=0; x<xsz; x++) { - if(amp[y*xsz+x]) - putchar('!'); /* ambigouos point is always on a limit */ - else - putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]); - putchar(h_char[ hlm[(y+1)*xsz+x] & (L_ON|L_OFF) ]); - } - putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]); - putchar('\n'); - } - /* last line */ - for(x=0; x<xsz; x++) { - putchar(' '); - putchar(h_char[ hlm[x] & (L_ON|L_OFF) ]); - } - putchar(' '); - putchar('\n'); -} -#endif /* 0 */ |