/*
* 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 */
|
Download
