+++ /dev/null
-/*
- * 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_COUNT 4 /* 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"};
-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);
-}
-
-/*
- * 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 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;
- gex_dump_contour(pge, clen);
-
- /* 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
- 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);
- 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
- 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);
- }
-
- /*
- * 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++) {
- GEX_FRAG *pf;
-
- /* 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 - f->len[GEXFI_EXACTLINE];
- 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 - f->len[GEXFI_EXACTLINE];
- /* clean lenback of gentries covered by the line */
- for(pge = ge->frwd, j = f->len[GEXFI_EXACTLINE]-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 = f->len[GEXFI_EXACTLINE] - 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 = f->len[GEXFI_EXACTLINE]-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;
- }
- }
-
- 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.
- */
-
- /* Maybe we should remove only exact coincidences ? */
-
- ge = cge->next;
- do {
- f = X_FRAG(ge);
-
- len = f->len[GEXFI_EXACTLINE];
- if(len >= 4) {
- 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);
- } else if(X_FRAG(ge->bkwd)->len[d] == len+1) {
- fprintf(stderr, " removed %s frag at %p len=%d next linelen=%d\n",
- gxf_name[d], ge->bkwd, X_FRAG(ge->bkwd)->len[d], len);
- pge = ge;
- for(i = len; i > 0; i--, pge = pge->frwd)
- X_FRAG(pge)->lenback[d] = 0;
- X_FRAG(ge->bkwd)->len[d] = 0;
- gex_dump_contour(ge, clen);
- }
- }
- }
-
- 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)
- 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 */
- 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 */
- ge = cge->next;
- do {
- /* 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_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;
- 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;
- }
- ge = ge->frwd;
- } while(ge != 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 */
git.asbjorn.biz / swftools.git / blobdiff