diff options
Diffstat (limited to 'nx-X11/extras/ttf2pt1/pt1.c')
| -rw-r--r-- | nx-X11/extras/ttf2pt1/pt1.c | 7374 |
1 files changed, 7374 insertions, 0 deletions
diff --git a/nx-X11/extras/ttf2pt1/pt1.c b/nx-X11/extras/ttf2pt1/pt1.c new file mode 100644 index 000000000..b1c46d57a --- /dev/null +++ b/nx-X11/extras/ttf2pt1/pt1.c @@ -0,0 +1,7374 @@ +/* + * see COPYRIGHT + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <fcntl.h> +#include <time.h> +#include <ctype.h> +#include <math.h> + +#ifndef WINDOWS +# include <netinet/in.h> +# include <unistd.h> +#else +# include "windows.h" +#endif + +#include "ttf.h" +#include "pt1.h" +#include "global.h" + +/* big and small values for comparisons */ +#define FBIGVAL (1e20) +#define FEPS (100000./FBIGVAL) + +/* names of the axes */ +#define X 0 +#define Y 1 + +/* the GENTRY extension structure used in fforceconcise() */ + +struct gex_con { + double d[2 /*X, Y*/]; /* sizes of curve */ + double sin2; /* squared sinus of the angle to the next gentry */ + double len2; /* squared distance between the endpoints */ + +/* number of reference dots taken from each curve */ +#define NREFDOTS 3 + + double dots[NREFDOTS][2]; /* reference dots */ + + int flags; /* flags for gentry and tits joint to the next gentry */ +/* a vertical or horizontal line may be in 2 quadrants at once */ +#define GEXF_QUL 0x00000001 /* in up-left quadrant */ +#define GEXF_QUR 0x00000002 /* in up-right quadrant */ +#define GEXF_QDR 0x00000004 /* in down-right quadrant */ +#define GEXF_QDL 0x00000008 /* in down-left quadrant */ +#define GEXF_QMASK 0x0000000F /* quadrant mask */ + +/* if a line is nearly vertical or horizontal, we remember that idealized quartant too */ +#define GEXF_QTO_IDEAL(f) (((f)&0xF)<<4) +#define GEXF_QFROM_IDEAL(f) (((f)&0xF0)>>4) +#define GEXF_IDQ_L 0x00000090 /* left */ +#define GEXF_IDQ_R 0x00000060 /* right */ +#define GEXF_IDQ_U 0x00000030 /* up */ +#define GEXF_IDQ_D 0x000000C0 /* down */ + +/* possibly can be joined with conditions: + * (in order of increasing preference, the numeric order is important) + */ +#define GEXF_JLINE 0x00000100 /* into one line */ +#define GEXF_JIGN 0x00000200 /* if one entry's tangent angle is ignored */ +#define GEXF_JID 0x00000400 /* if one entry is idealized to hor/vert */ +#define GEXF_JFLAT 0x00000800 /* if one entry is flattened */ +#define GEXF_JGOOD 0x00001000 /* perfectly, no additional maodifications */ + +#define GEXF_JMASK 0x00001F00 /* the mask of all above */ +#define GEXF_JCVMASK 0x00001E00 /* the mask of all above except JLINE */ + +/* which entry needs to be modified for conditional joining */ +#define GEXF_JIGN1 0x00002000 +#define GEXF_JIGN2 0x00004000 +#define GEXF_JIGNDIR(dir) (GEXF_JIGN1<<(dir)) +#define GEXF_JID1 0x00008000 +#define GEXF_JID2 0x00010000 +#define GEXF_JIDDIR(dir) (GEXF_JID1<<(dir)) +#define GEXF_JFLAT1 0x00020000 +#define GEXF_JFLAT2 0x00040000 +#define GEXF_JFLATDIR(dir) (GEXF_JFLAT1<<(dir)) + +#define GEXF_VERT 0x00100000 /* is nearly vertical */ +#define GEXF_HOR 0x00200000 /* is nearly horizontal */ +#define GEXF_FLAT 0x00400000 /* is nearly flat */ + +#define GEXF_VDOTS 0x01000000 /* the dots are valid */ + + signed char isd[2 /*X,Y*/]; /* signs of the sizes */ +}; +typedef struct gex_con GEX_CON; + +/* convenience macros */ +#define X_CON(ge) ((GEX_CON *)((ge)->ext)) +#define X_CON_D(ge) (X_CON(ge)->d) +#define X_CON_DX(ge) (X_CON(ge)->d[0]) +#define X_CON_DY(ge) (X_CON(ge)->d[1]) +#define X_CON_ISD(ge) (X_CON(ge)->isd) +#define X_CON_ISDX(ge) (X_CON(ge)->isd[0]) +#define X_CON_ISDY(ge) (X_CON(ge)->isd[1]) +#define X_CON_SIN2(ge) (X_CON(ge)->sin2) +#define X_CON_LEN2(ge) (X_CON(ge)->len2) +#define X_CON_F(ge) (X_CON(ge)->flags) + +/* performance statistics about guessing the concise curves */ +static int ggoodcv=0, ggoodcvdots=0, gbadcv=0, gbadcvdots=0; + +int stdhw, stdvw; /* dominant stems widths */ +int stemsnaph[12], stemsnapv[12]; /* most typical stem width */ + +int bluevalues[14]; +int nblues; +int otherblues[10]; +int notherb; +int bbox[4]; /* the FontBBox array */ +double italic_angle; + +GLYPH *glyph_list; +int encoding[ENCTABSZ]; /* inverse of glyph[].char_no */ +int kerning_pairs = 0; + +/* prototypes */ +static void fixcvdir( GENTRY * ge, int dir); +static void fixcvends( GENTRY * ge); +static int fgetcvdir( GENTRY * ge); +static int igetcvdir( GENTRY * ge); +static int fiszigzag( GENTRY *ge); +static int iiszigzag( GENTRY *ge); +static GENTRY * freethisge( GENTRY *ge); +static void addgeafter( GENTRY *oge, GENTRY *nge ); +static GENTRY * newgentry( int flags); +static void debugstems( char *name, STEM * hstems, int nhs, STEM * vstems, int nvs); +static int addbluestems( STEM *s, int n); +static void sortstems( STEM * s, int n); +static int stemoverlap( STEM * s1, STEM * s2); +static int steminblue( STEM *s); +static void markbluestems( STEM *s, int nold); +static int joinmainstems( STEM * s, int nold, int useblues); +static void joinsubstems( STEM * s, short *pairs, int nold, int useblues); +static void fixendpath( GENTRY *ge); +static void fdelsmall( GLYPH *g, double minlen); +static void alloc_gex_con( GENTRY *ge); +static double fjointsin2( GENTRY *ge1, GENTRY *ge2); +#if 0 +static double fcvarea( GENTRY *ge); +#endif +static double fcvval( GENTRY *ge, int axis, double t); +static void fsampledots( GENTRY *ge, double dots[][2], int ndots); +static void fnormalizege( GENTRY *ge); +static void fanalyzege( GENTRY *ge); +static void fanalyzejoint( GENTRY *ge); +static void fconcisecontour( GLYPH *g, GENTRY *ge); +static double fclosegap( GENTRY *from, GENTRY *to, int axis, + double gap, double *ret); + +int +isign( + int x +) +{ + if (x > 0) + return 1; + else if (x < 0) + return -1; + else + return 0; +} + +int +fsign( + double x +) +{ + if (x > 0.0) + return 1; + else if (x < 0.0) + return -1; + else + return 0; +} + +static GENTRY * +newgentry( + int flags +) +{ + GENTRY *ge; + + ge = calloc(1, sizeof(GENTRY)); + + if (ge == 0) { + fprintf(stderr, "***** Memory allocation error *****\n"); + exit(255); + } + ge->stemid = -1; + ge->flags = flags; + /* the rest is set to 0 by calloc() */ + return ge; +} + +/* + * Routines to print out Postscript functions with optimization + */ + +void +rmoveto( + int dx, + int dy +) +{ + if (optimize && dx == 0) + fprintf(pfa_file, "%d vmoveto\n", dy); + else if (optimize && dy == 0) + fprintf(pfa_file, "%d hmoveto\n", dx); + else + fprintf(pfa_file, "%d %d rmoveto\n", dx, dy); +} + +void +rlineto( + int dx, + int dy +) +{ + if (optimize && dx == 0 && dy == 0) /* for special pathologic + * case */ + return; + else if (optimize && dx == 0) + fprintf(pfa_file, "%d vlineto\n", dy); + else if (optimize && dy == 0) + fprintf(pfa_file, "%d hlineto\n", dx); + else + fprintf(pfa_file, "%d %d rlineto\n", dx, dy); +} + +void +rrcurveto( + int dx1, + int dy1, + int dx2, + int dy2, + int dx3, + int dy3 +) +{ + /* first two ifs are for crazy cases that occur surprisingly often */ + if (optimize && dx1 == 0 && dx2 == 0 && dx3 == 0) + rlineto(0, dy1 + dy2 + dy3); + else if (optimize && dy1 == 0 && dy2 == 0 && dy3 == 0) + rlineto(dx1 + dx2 + dx3, 0); + else if (optimize && dy1 == 0 && dx3 == 0) + fprintf(pfa_file, "%d %d %d %d hvcurveto\n", + dx1, dx2, dy2, dy3); + else if (optimize && dx1 == 0 && dy3 == 0) + fprintf(pfa_file, "%d %d %d %d vhcurveto\n", + dy1, dx2, dy2, dx3); + else + fprintf(pfa_file, "%d %d %d %d %d %d rrcurveto\n", + dx1, dy1, dx2, dy2, dx3, dy3); +} + +void +closepath(void) +{ + fprintf(pfa_file, "closepath\n"); +} + +/* + * Many of the path processing routines exist (or will exist) in + * both floating-point and integer version. Fimally most of the + * processing will go in floating point and the integer processing + * will become legacy. + * The names of floating routines start with f, names of integer + * routines start with i, and those old routines existing in one + * version only have no such prefix at all. + */ + +/* +** Routine that checks integrity of the path, for debugging +*/ + +void +assertpath( + GENTRY * from, + char *file, + int line, + char *name +) +{ + GENTRY *first, *pe, *ge; + int isfloat; + + if(from==0) + return; + isfloat = (from->flags & GEF_FLOAT); + pe = from->prev; + for (ge = from; ge != 0; pe = ge, ge = ge->next) { + if( (ge->flags & GEF_FLOAT) ^ isfloat ) { + fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name); + fprintf(stderr, "float flag changes from %s to %s at 0x%p (type %c, prev type %c)\n", + (isfloat ? "TRUE" : "FALSE"), (isfloat ? "FALSE" : "TRUE"), ge, ge->type, pe->type); + abort(); + } + if (pe != ge->prev) { + fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name); + fprintf(stderr, "unidirectional chain 0x%x -next-> 0x%x -prev-> 0x%x \n", + pe, ge, ge->prev); + abort(); + } + + switch(ge->type) { + case GE_MOVE: + break; + case GE_PATH: + if (ge->prev == 0) { + fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name); + fprintf(stderr, "empty path at 0x%x \n", ge); + abort(); + } + break; + case GE_LINE: + case GE_CURVE: + if(ge->frwd->bkwd != ge) { + fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name); + fprintf(stderr, "unidirectional chain 0x%x -frwd-> 0x%x -bkwd-> 0x%x \n", + ge, ge->frwd, ge->frwd->bkwd); + abort(); + } + if(ge->prev->type == GE_MOVE) { + first = ge; + if(ge->bkwd->next->type != GE_PATH) { + fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name); + fprintf(stderr, "broken first backlink 0x%x -bkwd-> 0x%x -next-> 0x%x \n", + ge, ge->bkwd, ge->bkwd->next); + abort(); + } + } + if(ge->next->type == GE_PATH) { + if(ge->frwd != first) { + fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name); + fprintf(stderr, "broken loop 0x%x -...-> 0x%x -frwd-> 0x%x \n", + first, ge, ge->frwd); + abort(); + } + } + break; + } + + } +} + +void +assertisfloat( + GLYPH *g, + char *msg +) +{ + if( !(g->flags & GF_FLOAT) ) { + fprintf(stderr, "**! Glyph %s is not float: %s\n", g->name, msg); + abort(); + } + if(g->lastentry) { + if( !(g->lastentry->flags & GEF_FLOAT) ) { + fprintf(stderr, "**! Glyphs %s last entry is int: %s\n", g->name, msg); + abort(); + } + } +} + +void +assertisint( + GLYPH *g, + char *msg +) +{ + if( (g->flags & GF_FLOAT) ) { + fprintf(stderr, "**! Glyph %s is not int: %s\n", g->name, msg); + abort(); + } + if(g->lastentry) { + if( (g->lastentry->flags & GEF_FLOAT) ) { + fprintf(stderr, "**! Glyphs %s last entry is float: %s\n", g->name, msg); + abort(); + } + } +} + + +/* + * Routines to save the generated data about glyph + */ + +void +fg_rmoveto( + GLYPH * g, + double x, + double y) +{ + GENTRY *oge; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: f rmoveto(%g, %g)\n", g->name, x, y); + + assertisfloat(g, "adding float MOVE"); + + if ((oge = g->lastentry) != 0) { + if (oge->type == GE_MOVE) { /* just eat up the first move */ + oge->fx3 = x; + oge->fy3 = y; + } else if (oge->type == GE_LINE || oge->type == GE_CURVE) { + fprintf(stderr, "Glyph %s: MOVE in middle of path\n", g->name); + } else { + GENTRY *nge; + + nge = newgentry(GEF_FLOAT); + nge->type = GE_MOVE; + nge->fx3 = x; + nge->fy3 = y; + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + } + } else { + GENTRY *nge; + + nge = newgentry(GEF_FLOAT); + nge->type = GE_MOVE; + nge->fx3 = x; + nge->fy3 = y; + nge->bkwd = (GENTRY*)&g->entries; + g->entries = g->lastentry = nge; + } + + if (0 && ISDBG(BUILDG)) + dumppaths(g, NULL, NULL); +} + +void +ig_rmoveto( + GLYPH * g, + int x, + int y) +{ + GENTRY *oge; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: i rmoveto(%d, %d)\n", g->name, x, y); + + assertisint(g, "adding int MOVE"); + + if ((oge = g->lastentry) != 0) { + if (oge->type == GE_MOVE) { /* just eat up the first move */ + oge->ix3 = x; + oge->iy3 = y; + } else if (oge->type == GE_LINE || oge->type == GE_CURVE) { + fprintf(stderr, "Glyph %s: MOVE in middle of path, ignored\n", g->name); + } else { + GENTRY *nge; + + nge = newgentry(0); + nge->type = GE_MOVE; + nge->ix3 = x; + nge->iy3 = y; + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + } + } else { + GENTRY *nge; + + nge = newgentry(0); + nge->type = GE_MOVE; + nge->ix3 = x; + nge->iy3 = y; + nge->bkwd = (GENTRY*)&g->entries; + g->entries = g->lastentry = nge; + } + +} + +void +fg_rlineto( + GLYPH * g, + double x, + double y) +{ + GENTRY *oge, *nge; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: f rlineto(%g, %g)\n", g->name, x, y); + + assertisfloat(g, "adding float LINE"); + + nge = newgentry(GEF_FLOAT); + nge->type = GE_LINE; + nge->fx3 = x; + nge->fy3 = y; + + if ((oge = g->lastentry) != 0) { + if (x == oge->fx3 && y == oge->fy3) { /* empty line */ + /* ignore it or we will get in troubles later */ + free(nge); + return; + } + if (g->path == 0) { + g->path = nge; + nge->bkwd = nge->frwd = nge; + } else { + oge->frwd = nge; + nge->bkwd = oge; + g->path->bkwd = nge; + nge->frwd = g->path; + } + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + } else { + WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name); + free(nge); + } + + if (0 && ISDBG(BUILDG)) + dumppaths(g, NULL, NULL); +} + +void +ig_rlineto( + GLYPH * g, + int x, + int y) +{ + GENTRY *oge, *nge; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: i rlineto(%d, %d)\n", g->name, x, y); + + assertisint(g, "adding int LINE"); + + nge = newgentry(0); + nge->type = GE_LINE; + nge->ix3 = x; + nge->iy3 = y; + + if ((oge = g->lastentry) != 0) { + if (x == oge->ix3 && y == oge->iy3) { /* empty line */ + /* ignore it or we will get in troubles later */ + free(nge); + return; + } + if (g->path == 0) { + g->path = nge; + nge->bkwd = nge->frwd = nge; + } else { + oge->frwd = nge; + nge->bkwd = oge; + g->path->bkwd = nge; + nge->frwd = g->path; + } + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + } else { + WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name); + free(nge); + } + +} + +void +fg_rrcurveto( + GLYPH * g, + double x1, + double y1, + double x2, + double y2, + double x3, + double y3) +{ + GENTRY *oge, *nge; + + oge = g->lastentry; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: f rrcurveto(%g, %g, %g, %g, %g, %g)\n" + ,g->name, x1, y1, x2, y2, x3, y3); + + assertisfloat(g, "adding float CURVE"); + + if (oge && oge->fx3 == x1 && x1 == x2 && x2 == x3) /* check if it's + * actually a line */ + fg_rlineto(g, x1, y3); + else if (oge && oge->fy3 == y1 && y1 == y2 && y2 == y3) + fg_rlineto(g, x3, y1); + else { + nge = newgentry(GEF_FLOAT); + nge->type = GE_CURVE; + nge->fx1 = x1; + nge->fy1 = y1; + nge->fx2 = x2; + nge->fy2 = y2; + nge->fx3 = x3; + nge->fy3 = y3; + + if (oge != 0) { + if (x3 == oge->fx3 && y3 == oge->fy3) { + free(nge); /* consider this curve empty */ + /* ignore it or we will get in troubles later */ + return; + } + if (g->path == 0) { + g->path = nge; + nge->bkwd = nge->frwd = nge; + } else { + oge->frwd = nge; + nge->bkwd = oge; + g->path->bkwd = nge; + nge->frwd = g->path; + } + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + } else { + WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name); + free(nge); + } + } + + if (0 && ISDBG(BUILDG)) + dumppaths(g, NULL, NULL); +} + +void +ig_rrcurveto( + GLYPH * g, + int x1, + int y1, + int x2, + int y2, + int x3, + int y3) +{ + GENTRY *oge, *nge; + + oge = g->lastentry; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: i rrcurveto(%d, %d, %d, %d, %d, %d)\n" + ,g->name, x1, y1, x2, y2, x3, y3); + + assertisint(g, "adding int CURVE"); + + if (oge && oge->ix3 == x1 && x1 == x2 && x2 == x3) /* check if it's + * actually a line */ + ig_rlineto(g, x1, y3); + else if (oge && oge->iy3 == y1 && y1 == y2 && y2 == y3) + ig_rlineto(g, x3, y1); + else { + nge = newgentry(0); + nge->type = GE_CURVE; + nge->ix1 = x1; + nge->iy1 = y1; + nge->ix2 = x2; + nge->iy2 = y2; + nge->ix3 = x3; + nge->iy3 = y3; + + if (oge != 0) { + if (x3 == oge->ix3 && y3 == oge->iy3) { + free(nge); /* consider this curve empty */ + /* ignore it or we will get in troubles later */ + return; + } + if (g->path == 0) { + g->path = nge; + nge->bkwd = nge->frwd = nge; + } else { + oge->frwd = nge; + nge->bkwd = oge; + g->path->bkwd = nge; + nge->frwd = g->path; + } + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + } else { + WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name); + free(nge); + } + } +} + +void +g_closepath( + GLYPH * g +) +{ + GENTRY *oge, *nge; + + if (ISDBG(BUILDG)) + fprintf(stderr, "%s: closepath\n", g->name); + + oge = g->lastentry; + + if (g->path == 0) { + WARNING_1 fprintf(stderr, "Warning: **** closepath on empty path in glyph \"%s\" ****\n", + g->name); + if (oge == 0) { + WARNING_1 fprintf(stderr, "No previois entry\n"); + } else { + WARNING_1 fprintf(stderr, "Previous entry type: %c\n", oge->type); + if (oge->type == GE_MOVE) { + g->lastentry = oge->prev; + if (oge->prev == 0) + g->entries = 0; + else + g->lastentry->next = 0; + free(oge); + } + } + return; + } + + nge = newgentry(oge->flags & GEF_FLOAT); /* keep the same type */ + nge->type = GE_PATH; + + g->path = 0; + + oge->next = nge; + nge->prev = oge; + g->lastentry = nge; + + if (0 && ISDBG(BUILDG)) + dumppaths(g, NULL, NULL); +} + +/* + * * SB * Routines to smooth and fix the glyphs + */ + +/* +** we don't want to see the curves with coinciding middle and +** outer points +*/ + +static void +fixcvends( + GENTRY * ge +) +{ + int dx, dy; + int x0, y0, x1, y1, x2, y2, x3, y3; + + if (ge->type != GE_CURVE) + return; + + if(ge->flags & GEF_FLOAT) { + fprintf(stderr, "**! fixcvends(0x%x) on floating entry, ABORT\n", ge); + abort(); /* dump core */ + } + + x0 = ge->prev->ix3; + y0 = ge->prev->iy3; + x1 = ge->ix1; + y1 = ge->iy1; + x2 = ge->ix2; + y2 = ge->iy2; + x3 = ge->ix3; + y3 = ge->iy3; + + + /* look at the start of the curve */ + if (x1 == x0 && y1 == y0) { + dx = x2 - x1; + dy = y2 - y1; + + if ((dx == 0 && dy == 0) + || (x2 == x3 && y2 == y3)) { + /* Oops, we actually have a straight line */ + /* + * if it's small, we hope that it will get optimized + * later + */ + if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) { + ge->ix1 = x3; + ge->iy1 = y3; + ge->ix2 = x0; + ge->iy2 = y0; + } else {/* just make it a line */ + ge->type = GE_LINE; + } + } else { + if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very + * small */ + ge->ix1 = x2; + ge->iy1 = y2; + } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */ + ge->ix1 += dx / 2; + ge->iy1 += dy / 2; + } else { + ge->ix1 += dx / 4; + ge->iy1 += dy / 4; + } + /* make sure that it's still on the same side */ + if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) { + if (abs(x3 - x0) * abs(ge->iy1 - y0) > abs(y3 - y0) * abs(ge->ix1 - x0)) + ge->ix1 += isign(dx); + } else { + if (abs(x3 - x0) * abs(ge->iy1 - y0) < abs(y3 - y0) * abs(ge->ix1 - x0)) + ge->iy1 += isign(dy); + } + + ge->ix2 += (x3 - x2) / 8; + ge->iy2 += (y3 - y2) / 8; + /* make sure that it's still on the same side */ + if (abs(x3 - x0) * abs(y3 - y2) < abs(y3 - y0) * abs(x3 - x2)) { + if (abs(x3 - x0) * abs(y3 - ge->iy2) > abs(y3 - y0) * abs(x3 - ge->ix2)) + ge->iy1 -= isign(y3 - y2); + } else { + if (abs(x3 - x0) * abs(y3 - ge->iy2) < abs(y3 - y0) * abs(x3 - ge->ix2)) + ge->ix1 -= isign(x3 - x2); + } + + } + } else if (x2 == x3 && y2 == y3) { + dx = x1 - x2; + dy = y1 - y2; + + if (dx == 0 && dy == 0) { + /* Oops, we actually have a straight line */ + /* + * if it's small, we hope that it will get optimized + * later + */ + if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) { + ge->ix1 = x3; + ge->iy1 = y3; + ge->ix2 = x0; + ge->iy2 = y0; + } else {/* just make it a line */ + ge->type = GE_LINE; + } + } else { + if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very + * small */ + ge->ix2 = x1; + ge->iy2 = y1; + } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */ + ge->ix2 += dx / 2; + ge->iy2 += dy / 2; + } else { + ge->ix2 += dx / 4; + ge->iy2 += dy / 4; + } + /* make sure that it's still on the same side */ + if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) { + if (abs(x3 - x0) * abs(ge->iy2 - y3) > abs(y3 - y0) * abs(ge->ix2 - x3)) + ge->ix2 += isign(dx); + } else { + if (abs(x3 - x0) * abs(ge->iy2 - y3) < abs(y3 - y0) * abs(ge->ix2 - x3)) + ge->iy2 += isign(dy); + } + + ge->ix1 += (x0 - x1) / 8; + ge->iy1 += (y0 - y1) / 8; + /* make sure that it's still on the same side */ + if (abs(x3 - x0) * abs(y0 - y1) < abs(y3 - y0) * abs(x0 - x1)) { + if (abs(x3 - x0) * abs(y0 - ge->iy1) > abs(y3 - y0) * abs(x0 - ge->ix1)) + ge->iy1 -= isign(y0 - y1); + } else { + if (abs(x3 - x0) * abs(y0 - ge->iy1) < abs(y3 - y0) * abs(x0 - ge->ix1)) + ge->ix1 -= isign(x0 - x1); + } + + } + } +} + +/* +** After transformations we want to make sure that the resulting +** curve is going in the same quadrant as the original one, +** because rounding errors introduced during transformations +** may make the result completeley wrong. +** +** `dir' argument describes the direction of the original curve, +** it is the superposition of two values for the front and +** rear ends of curve: +** +** >EQUAL - goes over the line connecting the ends +** =EQUAL - coincides with the line connecting the ends +** <EQUAL - goes under the line connecting the ends +** +** See CVDIR_* for exact definitions. +*/ + +static void +fixcvdir( + GENTRY * ge, + int dir +) +{ + int a, b, c, d; + double kk, kk1, kk2; + int changed; + int fdir, rdir; + + if(ge->flags & GEF_FLOAT) { + fprintf(stderr, "**! fixcvdir(0x%x) on floating entry, ABORT\n", ge); + abort(); /* dump core */ + } + + fdir = (dir & CVDIR_FRONT) - CVDIR_FEQUAL; + if ((dir & CVDIR_REAR) == CVDIR_RSAME) + rdir = fdir; /* we need only isign, exact value doesn't matter */ + else + rdir = (dir & CVDIR_REAR) - CVDIR_REQUAL; + + fixcvends(ge); + + c = isign(ge->ix3 - ge->prev->ix3); /* note the direction of + * curve */ + d = isign(ge->iy3 - ge->prev->iy3); + + a = ge->iy3 - ge->prev->iy3; + b = ge->ix3 - ge->prev->ix3; + kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + a = ge->iy1 - ge->prev->iy3; + b = ge->ix1 - ge->prev->ix3; + kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + a = ge->iy3 - ge->iy2; + b = ge->ix3 - ge->ix2; + kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + + changed = 1; + while (changed) { + if (ISDBG(FIXCVDIR)) { + /* for debugging */ + fprintf(stderr, "fixcvdir %d %d (%d %d %d %d %d %d) %f %f %f\n", + fdir, rdir, + ge->ix1 - ge->prev->ix3, + ge->iy1 - ge->prev->iy3, + ge->ix2 - ge->ix1, + ge->iy2 - ge->iy1, + ge->ix3 - ge->ix2, + ge->iy3 - ge->iy2, + kk1, kk, kk2); + } + changed = 0; + + if (fdir > 0) { + if (kk1 > kk) { /* the front end has problems */ + if (c * (ge->ix1 - ge->prev->ix3) > 0) { + ge->ix1 -= c; + changed = 1; + } if (d * (ge->iy2 - ge->iy1) > 0) { + ge->iy1 += d; + changed = 1; + } + /* recalculate the coefficients */ + a = ge->iy3 - ge->prev->iy3; + b = ge->ix3 - ge->prev->ix3; + kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + a = ge->iy1 - ge->prev->iy3; + b = ge->ix1 - ge->prev->ix3; + kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + } + } else if (fdir < 0) { + if (kk1 < kk) { /* the front end has problems */ + if (c * (ge->ix2 - ge->ix1) > 0) { + ge->ix1 += c; + changed = 1; + } if (d * (ge->iy1 - ge->prev->iy3) > 0) { + ge->iy1 -= d; + changed = 1; + } + /* recalculate the coefficients */ + a = ge->iy1 - ge->prev->iy3; + b = ge->ix1 - ge->prev->ix3; + kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + a = ge->iy3 - ge->prev->iy3; + b = ge->ix3 - ge->prev->ix3; + kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + } + } + if (rdir > 0) { + if (kk2 < kk) { /* the rear end has problems */ + if (c * (ge->ix2 - ge->ix1) > 0) { + ge->ix2 -= c; + changed = 1; + } if (d * (ge->iy3 - ge->iy2) > 0) { + ge->iy2 += d; + changed = 1; + } + /* recalculate the coefficients */ + a = ge->iy3 - ge->prev->iy3; + b = ge->ix3 - ge->prev->ix3; + kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + a = ge->iy3 - ge->iy2; + b = ge->ix3 - ge->ix2; + kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + } + } else if (rdir < 0) { + if (kk2 > kk) { /* the rear end has problems */ + if (c * (ge->ix3 - ge->ix2) > 0) { + ge->ix2 += c; + changed = 1; + } if (d * (ge->iy2 - ge->iy1) > 0) { + ge->iy2 -= d; + changed = 1; + } + /* recalculate the coefficients */ + a = ge->iy3 - ge->prev->iy3; + b = ge->ix3 - ge->prev->ix3; + kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + a = ge->iy3 - ge->iy2; + b = ge->ix3 - ge->ix2; + kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a)); + } + } + } + fixcvends(ge); +} + +/* Get the directions of ends of curve for further usage */ + +/* expects that the previous element is also float */ + +static int +fgetcvdir( + GENTRY * ge +) +{ + double a, b; + double k, k1, k2; + int dir = 0; + + if( !(ge->flags & GEF_FLOAT) ) { + fprintf(stderr, "**! fgetcvdir(0x%x) on int entry, ABORT\n", ge); + abort(); /* dump core */ + } + + a = fabs(ge->fy3 - ge->prev->fy3); + b = fabs(ge->fx3 - ge->prev->fx3); + k = a < FEPS ? (b < FEPS ? 1. : 100000.) : ( b / a); + + a = fabs(ge->fy1 - ge->prev->fy3); + b = fabs(ge->fx1 - ge->prev->fx3); + if(a < FEPS) { + if(b < FEPS) { + a = fabs(ge->fy2 - ge->prev->fy3); + b = fabs(ge->fx2 - ge->prev->fx3); + k1 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a); + } else + k1 = FBIGVAL; + } else + k1 = b / a; + + a = fabs(ge->fy3 - ge->fy2); + b = fabs(ge->fx3 - ge->fx2); + if(a < FEPS) { + if(b < FEPS) { + a = fabs(ge->fy3 - ge->fy1); + b = fabs(ge->fx3 - ge->fx1); + k2 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a); + } else + k2 = FBIGVAL; + } else + k2 = b / a; + + if(fabs(k1-k) < 0.0001) + dir |= CVDIR_FEQUAL; + else if (k1 < k) + dir |= CVDIR_FUP; + else + dir |= CVDIR_FDOWN; + + if(fabs(k2-k) < 0.0001) + dir |= CVDIR_REQUAL; + else if (k2 > k) + dir |= CVDIR_RUP; + else + dir |= CVDIR_RDOWN; + + return dir; +} + + +/* expects that the previous element is also int */ + +static int +igetcvdir( + GENTRY * ge +) +{ + int a, b; + double k, k1, k2; + int dir = 0; + + if(ge->flags & GEF_FLOAT) { + fprintf(stderr, "**! igetcvdir(0x%x) on floating entry, ABORT\n", ge); + abort(); /* dump core */ + } + + a = ge->iy3 - ge->prev->iy3; + b = ge->ix3 - ge->prev->ix3; + k = (a == 0) ? (b == 0 ? 1. : 100000.) : fabs((double) b / (double) a); + + a = ge->iy1 - ge->prev->iy3; + b = ge->ix1 - ge->prev->ix3; + if(a == 0) { + if(b == 0) { + a = ge->iy2 - ge->prev->iy3; + b = ge->ix2 - ge->prev->ix3; + k1 = (a == 0) ? (b == 0 ? k : 100000.) : fabs((double) b / (double) a); + } else + k1 = FBIGVAL; + } else + k1 = fabs((double) b / (double) a); + + a = ge->iy3 - ge->iy2; + b = ge->ix3 - ge->ix2; + if(a == 0) { + if(b == 0) { + a = ge->iy3 - ge->iy1; + b = ge->ix3 - ge->ix1; + k2 = (a == 0) ? (b == 0 ? k : 100000.) : fabs((double) b / (double) a); + } else + k2 = FBIGVAL; + } else + k2 = fabs((double) b / (double) a); + + if(fabs(k1-k) < 0.0001) + dir |= CVDIR_FEQUAL; + else if (k1 < k) + dir |= CVDIR_FUP; + else + dir |= CVDIR_FDOWN; + + if(fabs(k2-k) < 0.0001) + dir |= CVDIR_REQUAL; + else if (k2 > k) + dir |= CVDIR_RUP; + else + dir |= CVDIR_RDOWN; + + return dir; +} + +#if 0 +/* a function just to test the work of fixcvdir() */ +static void +testfixcvdir( + GLYPH * g +) +{ + GENTRY *ge; + int dir; + + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type == GE_CURVE) { + dir = igetcvdir(ge); + fixcvdir(ge, dir); + } + } +} +#endif + +static int +iround( + double val +) +{ + return (int) (val > 0 ? val + 0.5 : val - 0.5); +} + +/* for debugging - dump the glyph + * mark with a star the entries from start to end inclusive + * (start == NULL means don't mark any, end == NULL means to the last) + */ + +void +dumppaths( + GLYPH *g, + GENTRY *start, + GENTRY *end +) +{ + GENTRY *ge; + int i; + char mark=' '; + + fprintf(stderr, "Glyph %s:\n", g->name); + + /* now do the conversion */ + for(ge = g->entries; ge != 0; ge = ge->next) { + if(ge == start) + mark = '*'; + fprintf(stderr, " %c %8x", mark, ge); + switch(ge->type) { + case GE_MOVE: + case GE_LINE: + if(ge->flags & GEF_FLOAT) + fprintf(stderr," %c float (%g, %g)\n", ge->type, ge->fx3, ge->fy3); + else + fprintf(stderr," %c int (%d, %d)\n", ge->type, ge->ix3, ge->iy3); + break; + case GE_CURVE: + if(ge->flags & GEF_FLOAT) { + fprintf(stderr," C float "); + for(i=0; i<3; i++) + fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]); + fprintf(stderr,"\n"); + } else { + fprintf(stderr," C int "); + for(i=0; i<3; i++) + fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]); + fprintf(stderr,"\n"); + } + break; + default: + fprintf(stderr, " %c\n", ge->type); + break; + } + if(ge == end) + mark = ' '; + } +} + +/* + * Routine that converts all entries in the path from float to int + */ + +void +pathtoint( + GLYPH *g +) +{ + GENTRY *ge; + int x[3], y[3]; + int i; + + + if(ISDBG(TOINT)) + fprintf(stderr, "TOINT: glyph %s\n", g->name); + assertisfloat(g, "converting path to int\n"); + + fdelsmall(g, 1.0); /* get rid of sub-pixel contours */ + assertpath(g->entries, __FILE__, __LINE__, g->name); + + /* 1st pass, collect the directions of the curves: have + * to do that in advance, while everyting is float + */ + for(ge = g->entries; ge != 0; ge = ge->next) { + if( !(ge->flags & GEF_FLOAT) ) { + fprintf(stderr, "**! glyphs %s has int entry, found in conversion to int\n", + g->name); + exit(1); + } + if(ge->type == GE_CURVE) { + ge->dir = fgetcvdir(ge); + } + } + + /* now do the conversion */ + for(ge = g->entries; ge != 0; ge = ge->next) { + switch(ge->type) { + case GE_MOVE: + case GE_LINE: + if(ISDBG(TOINT)) + fprintf(stderr," %c float x=%g y=%g\n", ge->type, ge->fx3, ge->fy3); + x[0] = iround(ge->fx3); + y[0] = iround(ge->fy3); + for(i=0; i<3; i++) { /* put some valid values everywhere, for convenience */ + ge->ixn[i] = x[0]; + ge->iyn[i] = y[0]; + } + if(ISDBG(TOINT)) + fprintf(stderr," int x=%d y=%d\n", ge->ix3, ge->iy3); + break; + case GE_CURVE: + if(ISDBG(TOINT)) + fprintf(stderr," %c float ", ge->type); + + for(i=0; i<3; i++) { + if(ISDBG(TOINT)) + fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]); + x[i] = iround(ge->fxn[i]); + y[i] = iround(ge->fyn[i]); + } + + if(ISDBG(TOINT)) + fprintf(stderr,"\n int "); + + for(i=0; i<3; i++) { + ge->ixn[i] = x[i]; + ge->iyn[i] = y[i]; + if(ISDBG(TOINT)) + fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]); + } + ge->flags &= ~GEF_FLOAT; /* for fixcvdir */ + fixcvdir(ge, ge->dir); + + if(ISDBG(TOINT)) { + fprintf(stderr,"\n fixed "); + for(i=0; i<3; i++) + fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]); + fprintf(stderr,"\n"); + } + + break; + } + ge->flags &= ~GEF_FLOAT; + } + g->flags &= ~GF_FLOAT; +} + + +/* check whether we can fix up the curve to change its size by (dx,dy) */ +/* 0 means NO, 1 means YES */ + +/* for float: if scaling would be under 10% */ + +int +fcheckcv( + GENTRY * ge, + double dx, + double dy +) +{ + if( !(ge->flags & GEF_FLOAT) ) { + fprintf(stderr, "**! fcheckcv(0x%x) on int entry, ABORT\n", ge); + abort(); /* dump core */ + } + + if (ge->type != GE_CURVE) + return 0; + + if( fabs(ge->fx3 - ge->prev->fx3) < fabs(dx) * 10 ) + return 0; + + if( fabs(ge->fy3 - ge->prev->fy3) < fabs(dy) * 10 ) + return 0; + + return 1; +} + +/* for int: if won't create new zigzags at the ends */ + +int +icheckcv( + GENTRY * ge, + int dx, + int dy +) +{ + int xdep, ydep; + + if(ge->flags & GEF_FLOAT) { + fprintf(stderr, "**! icheckcv(0x%x) on floating entry, ABORT\n", ge); + abort(); /* dump core */ + } + + if (ge->type != GE_CURVE) + return 0; + + xdep = ge->ix3 - ge->prev->ix3; + ydep = ge->iy3 - ge->prev->iy3; + + if (ge->type == GE_CURVE + && (xdep * (xdep + dx)) > 0 + && (ydep * (ydep + dy)) > 0) { + return 1; + } else + return 0; +} + +/* float connect the ends of open contours */ + +void +fclosepaths( + GLYPH * g +) +{ + GENTRY *ge, *fge, *xge, *nge; + int i; + + assertisfloat(g, "fclosepaths float\n"); + + for (xge = g->entries; xge != 0; xge = xge->next) { + if( xge->type != GE_PATH ) + continue; + + ge = xge->prev; + if(ge == 0 || (ge->type != GE_LINE && ge->type!= GE_CURVE)) { + fprintf(stderr, "**! Glyph %s got empty path\n", + g->name); + exit(1); + } + + fge = ge->frwd; + if (fge->prev == 0 || fge->prev->type != GE_MOVE) { + fprintf(stderr, "**! Glyph %s got strange beginning of path\n", + g->name); + exit(1); + } + fge = fge->prev; + if (fge->fx3 != ge->fx3 || fge->fy3 != ge->fy3) { + /* we have to fix this open path */ + + WARNING_4 fprintf(stderr, "Glyph %s got path open by dx=%g dy=%g\n", + g->name, fge->fx3 - ge->fx3, fge->fy3 - ge->fy3); + + + /* add a new line */ + nge = newgentry(GEF_FLOAT); + (*nge) = (*ge); + nge->fx3 = fge->fx3; + nge->fy3 = fge->fy3; + nge->type = GE_LINE; + + addgeafter(ge, nge); + + if (fabs(ge->fx3 - fge->fx3) <= 2 && fabs(ge->fy3 - fge->fy3) <= 2) { + /* + * small change, try to get rid of the new entry + */ + + double df[2]; + + for(i=0; i<2; i++) { + df[i] = ge->fpoints[i][2] - fge->fpoints[i][2]; + df[i] = fclosegap(nge, nge, i, df[i], NULL); + } + + if(df[0] == 0. && df[1] == 0.) { + /* closed gap successfully, remove the added entry */ + freethisge(nge); + } + } + } + } +} + +void +smoothjoints( + GLYPH * g +) +{ + GENTRY *ge, *ne; + int dx1, dy1, dx2, dy2, k; + int dir; + + return; /* this stuff seems to create problems */ + + assertisint(g, "smoothjoints int"); + + if (g->entries == 0) /* nothing to do */ + return; + + for (ge = g->entries->next; ge != 0; ge = ge->next) { + ne = ge->frwd; + + /* + * although there should be no one-line path * and any path + * must end with CLOSEPATH, * nobody can say for sure + */ + + if (ge == ne || ne == 0) + continue; + + /* now handle various joints */ + + if (ge->type == GE_LINE && ne->type == GE_LINE) { + dx1 = ge->ix3 - ge->prev->ix3; + dy1 = ge->iy3 - ge->prev->iy3; + dx2 = ne->ix3 - ge->ix3; + dy2 = ne->iy3 - ge->iy3; + + /* check whether they have the same direction */ + /* and the same slope */ + /* then we can join them into one line */ + + if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 && dx1 * dy2 == dy1 * dx2) { + /* extend the previous line */ + ge->ix3 = ne->ix3; + ge->iy3 = ne->iy3; + + /* and get rid of the next line */ + freethisge(ne); + } + } else if (ge->type == GE_LINE && ne->type == GE_CURVE) { + fixcvends(ne); + + dx1 = ge->ix3 - ge->prev->ix3; + dy1 = ge->iy3 - ge->prev->iy3; + dx2 = ne->ix1 - ge->ix3; + dy2 = ne->iy1 - ge->iy3; + + /* if the line is nearly horizontal and we can fix it */ + if (dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0 + && icheckcv(ne, 0, -dy1) + && abs(dy1) <= 4) { + dir = igetcvdir(ne); + ge->iy3 -= dy1; + ne->iy1 -= dy1; + fixcvdir(ne, dir); + if (ge->next != ne) + ne->prev->iy3 -= dy1; + dy1 = 0; + } else if (dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0 + && icheckcv(ne, -dx1, 0) + && abs(dx1) <= 4) { + /* the same but vertical */ + dir = igetcvdir(ne); + ge->ix3 -= dx1; + ne->ix1 -= dx1; + fixcvdir(ne, dir); + if (ge->next != ne) + ne->prev->ix3 -= dx1; + dx1 = 0; + } + /* + * if line is horizontal and curve begins nearly + * horizontally + */ + if (dy1 == 0 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0) { + dir = igetcvdir(ne); + ne->iy1 -= dy2; + fixcvdir(ne, dir); + dy2 = 0; + } else if (dx1 == 0 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0) { + /* the same but vertical */ + dir = igetcvdir(ne); + ne->ix1 -= dx2; + fixcvdir(ne, dir); + dx2 = 0; + } + } else if (ge->type == GE_CURVE && ne->type == GE_LINE) { + fixcvends(ge); + + dx1 = ge->ix3 - ge->ix2; + dy1 = ge->iy3 - ge->iy2; + dx2 = ne->ix3 - ge->ix3; + dy2 = ne->iy3 - ge->iy3; + + /* if the line is nearly horizontal and we can fix it */ + if (dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0 + && icheckcv(ge, 0, dy2) + && abs(dy2) <= 4) { + dir = igetcvdir(ge); + ge->iy3 += dy2; + ge->iy2 += dy2; + fixcvdir(ge, dir); + if (ge->next != ne) + ne->prev->iy3 += dy2; + dy2 = 0; + } else if (dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0 + && icheckcv(ge, dx2, 0) + && abs(dx2) <= 4) { + /* the same but vertical */ + dir = igetcvdir(ge); + ge->ix3 += dx2; + ge->ix2 += dx2; + fixcvdir(ge, dir); + if (ge->next != ne) + ne->prev->ix3 += dx2; + dx2 = 0; + } + /* + * if line is horizontal and curve ends nearly + * horizontally + */ + if (dy2 == 0 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0) { + dir = igetcvdir(ge); + ge->iy2 += dy1; + fixcvdir(ge, dir); + dy1 = 0; + } else if (dx2 == 0 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0) { + /* the same but vertical */ + dir = igetcvdir(ge); + ge->ix2 += dx1; + fixcvdir(ge, dir); + dx1 = 0; + } + } else if (ge->type == GE_CURVE && ne->type == GE_CURVE) { + fixcvends(ge); + fixcvends(ne); + + dx1 = ge->ix3 - ge->ix2; + dy1 = ge->iy3 - ge->iy2; + dx2 = ne->ix1 - ge->ix3; + dy2 = ne->iy1 - ge->iy3; + + /* + * check if we have a rather smooth joint at extremal + * point + */ + /* left or right extremal point */ + if (abs(dx1) <= 4 && abs(dx2) <= 4 + && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0 + && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0 + && ((ge->iy3 < ge->prev->iy3 && ne->iy3 < ge->iy3) + || (ge->iy3 > ge->prev->iy3 && ne->iy3 > ge->iy3)) + && (ge->ix3 - ge->prev->ix3) * (ne->ix3 - ge->ix3) < 0 + ) { + dir = igetcvdir(ge); + ge->ix2 += dx1; + dx1 = 0; + fixcvdir(ge, dir); + dir = igetcvdir(ne); + ne->ix1 -= dx2; + dx2 = 0; + fixcvdir(ne, dir); + } + /* top or down extremal point */ + else if (abs(dy1) <= 4 && abs(dy2) <= 4 + && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0 + && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0 + && ((ge->ix3 < ge->prev->ix3 && ne->ix3 < ge->ix3) + || (ge->ix3 > ge->prev->ix3 && ne->ix3 > ge->ix3)) + && (ge->iy3 - ge->prev->iy3) * (ne->iy3 - ge->iy3) < 0 + ) { + dir = igetcvdir(ge); + ge->iy2 += dy1; + dy1 = 0; + fixcvdir(ge, dir); + dir = igetcvdir(ne); + ne->iy1 -= dy2; + dy2 = 0; + fixcvdir(ne, dir); + } + /* or may be we just have a smooth junction */ + else if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 + && 10 * abs(k = abs(dx1 * dy2) - abs(dy1 * dx2)) < (abs(dx1 * dy2) + abs(dy1 * dx2))) { + int tries[6][4]; + int results[6]; + int i, b; + + /* build array of changes we are going to try */ + /* uninitalized entries are 0 */ + if (k > 0) { + static int t1[6][4] = { + {0, 0, 0, 0}, + {-1, 0, 1, 0}, + {-1, 0, 0, 1}, + {0, -1, 1, 0}, + {0, -1, 0, 1}, + {-1, -1, 1, 1}}; + memcpy(tries, t1, sizeof tries); + } else { + static int t1[6][4] = { + {0, 0, 0, 0}, + {1, 0, -1, 0}, + {1, 0, 0, -1}, + {0, 1, -1, 0}, + {0, 1, 0, -1}, + {1, 1, -1, -1}}; + memcpy(tries, t1, sizeof tries); + } + + /* now try the changes */ + results[0] = abs(k); + for (i = 1; i < 6; i++) { + results[i] = abs((abs(dx1) + tries[i][0]) * (abs(dy2) + tries[i][1]) - + (abs(dy1) + tries[i][2]) * (abs(dx2) + tries[i][3])); + } + + /* and find the best try */ + k = abs(k); + b = 0; + for (i = 1; i < 6; i++) + if (results[i] < k) { + k = results[i]; + b = i; + } + /* and finally apply it */ + if (dx1 < 0) + tries[b][0] = -tries[b][0]; + if (dy2 < 0) + tries[b][1] = -tries[b][1]; + if (dy1 < 0) + tries[b][2] = -tries[b][2]; + if (dx2 < 0) + tries[b][3] = -tries[b][3]; + + dir = igetcvdir(ge); + ge->ix2 -= tries[b][0]; + ge->iy2 -= tries[b][2]; + fixcvdir(ge, dir); + dir = igetcvdir(ne); + ne->ix1 += tries[b][3]; + ne->iy1 += tries[b][1]; + fixcvdir(ne, dir); + } + } + } +} + +/* debugging: print out stems of a glyph */ +static void +debugstems( + char *name, + STEM * hstems, + int nhs, + STEM * vstems, + int nvs +) +{ + int i; + + fprintf(pfa_file, "%% %s\n", name); + fprintf(pfa_file, "%% %d horizontal stems:\n", nhs); + for (i = 0; i < nhs; i++) + fprintf(pfa_file, "%% %3d %d (%d...%d) %c %c%c%c%c\n", i, hstems[i].value, + hstems[i].from, hstems[i].to, + ((hstems[i].flags & ST_UP) ? 'U' : 'D'), + ((hstems[i].flags & ST_END) ? 'E' : '-'), + ((hstems[i].flags & ST_FLAT) ? 'F' : '-'), + ((hstems[i].flags & ST_ZONE) ? 'Z' : ' '), + ((hstems[i].flags & ST_TOPZONE) ? 'T' : ' ')); + fprintf(pfa_file, "%% %d vertical stems:\n", nvs); + for (i = 0; i < nvs; i++) + fprintf(pfa_file, "%% %3d %d (%d...%d) %c %c%c\n", i, vstems[i].value, + vstems[i].from, vstems[i].to, + ((vstems[i].flags & ST_UP) ? 'U' : 'D'), + ((vstems[i].flags & ST_END) ? 'E' : '-'), + ((vstems[i].flags & ST_FLAT) ? 'F' : '-')); +} + +/* add pseudo-stems for the limits of the Blue zones to the stem array */ +static int +addbluestems( + STEM *s, + int n +) +{ + int i; + + for(i=0; i<nblues && i<2; i+=2) { /* baseline */ + s[n].value=bluevalues[i]; + s[n].flags=ST_UP|ST_ZONE; + /* don't overlap with anything */ + s[n].origin=s[n].from=s[n].to= -10000+i; + n++; + s[n].value=bluevalues[i+1]; + s[n].flags=ST_ZONE; + /* don't overlap with anything */ + s[n].origin=s[n].from=s[n].to= -10000+i+1; + n++; + } + for(i=2; i<nblues; i+=2) { /* top zones */ + s[n].value=bluevalues[i]; + s[n].flags=ST_UP|ST_ZONE|ST_TOPZONE; + /* don't overlap with anything */ + s[n].origin=s[n].from=s[n].to= -10000+i; + n++; + s[n].value=bluevalues[i+1]; + s[n].flags=ST_ZONE|ST_TOPZONE; + /* don't overlap with anything */ + s[n].origin=s[n].from=s[n].to= -10000+i+1; + n++; + } + for(i=0; i<notherb; i+=2) { /* bottom zones */ + s[n].value=otherblues[i]; + s[n].flags=ST_UP|ST_ZONE; + /* don't overlap with anything */ + s[n].origin=s[n].from=s[n].to= -10000+i+nblues; + n++; + s[n].value=otherblues[i+1]; + s[n].flags=ST_ZONE; + /* don't overlap with anything */ + s[n].origin=s[n].from=s[n].to= -10000+i+1+nblues; + n++; + } + return n; +} + +/* sort stems in array */ +static void +sortstems( + STEM * s, + int n +) +{ + int i, j; + STEM x; + + + /* a simple sorting */ + /* hm, the ordering criteria are not quite simple :-) + * if the values are tied + * ST_UP always goes under not ST_UP + * ST_ZONE goes on the most outer side + * ST_END goes towards inner side after ST_ZONE + * ST_FLAT goes on the inner side + */ + + for (i = 0; i < n; i++) + for (j = i + 1; j < n; j++) { + if(s[i].value < s[j].value) + continue; + if(s[i].value == s[j].value) { + if( (s[i].flags & ST_UP) < (s[j].flags & ST_UP) ) + continue; + if( (s[i].flags & ST_UP) == (s[j].flags & ST_UP) ) { + if( s[i].flags & ST_UP ) { + if( + ((s[i].flags & (ST_ZONE|ST_FLAT|ST_END)) ^ ST_FLAT) + > + ((s[j].flags & (ST_ZONE|ST_FLAT|ST_END)) ^ ST_FLAT) + ) + continue; + } else { + if( + ((s[i].flags & (ST_ZONE|ST_FLAT|ST_END)) ^ ST_FLAT) + < + ((s[j].flags & (ST_ZONE|ST_FLAT|ST_END)) ^ ST_FLAT) + ) + continue; + } + } + } + x = s[j]; + s[j] = s[i]; + s[i] = x; + } +} + +/* check whether two stem borders overlap */ + +static int +stemoverlap( + STEM * s1, + STEM * s2 +) +{ + int result; + + if ((s1->from <= s2->from && s1->to >= s2->from) + || (s2->from <= s1->from && s2->to >= s1->from)) + result = 1; + else + result = 0; + + if (ISDBG(STEMOVERLAP)) + fprintf(pfa_file, "%% overlap %d(%d..%d)x%d(%d..%d)=%d\n", + s1->value, s1->from, s1->to, s2->value, s2->from, s2->to, result); + return result; +} + +/* + * check if the stem [border] is in an appropriate blue zone + * (currently not used) + */ + +static int +steminblue( + STEM *s +) +{ + int i, val; + + val=s->value; + if(s->flags & ST_UP) { + /* painted size up, look at lower zones */ + if(nblues>=2 && val>=bluevalues[0] && val<=bluevalues[1] ) + return 1; + for(i=0; i<notherb; i++) { + if( val>=otherblues[i] && val<=otherblues[i+1] ) + return 1; + } + } else { + /* painted side down, look at upper zones */ + for(i=2; i<nblues; i++) { + if( val>=bluevalues[i] && val<=bluevalues[i+1] ) + return 1; + } + } + + return 0; +} + +/* mark the outermost stem [borders] in the blue zones */ + +static void +markbluestems( + STEM *s, + int nold +) +{ + int i, j, a, b, c; + /* + * traverse the list of Blue Values, mark the lowest upper + * stem in each bottom zone and the topmost lower stem in + * each top zone with ST_BLUE + */ + + /* top zones */ + for(i=2; i<nblues; i+=2) { + a=bluevalues[i]; b=bluevalues[i+1]; + if(ISDBG(BLUESTEMS)) + fprintf(pfa_file, "%% looking at blue zone %d...%d\n", a, b); + for(j=nold-1; j>=0; j--) { + if( s[j].flags & (ST_ZONE|ST_UP|ST_END) ) + continue; + c=s[j].value; + if(c<a) /* too low */ + break; + if(c<=b) { /* found the topmost stem border */ + /* mark all the stems with the same value */ + if(ISDBG(BLUESTEMS)) + fprintf(pfa_file, "%% found D BLUE at %d\n", s[j].value); + /* include ST_END values */ + while( s[j+1].value==c && (s[j+1].flags & ST_ZONE)==0 ) + j++; + s[j].flags |= ST_BLUE; + for(j--; j>=0 && s[j].value==c + && (s[j].flags & (ST_UP|ST_ZONE))==0 ; j--) + s[j].flags |= ST_BLUE; + break; + } + } + } + /* baseline */ + if(nblues>=2) { + a=bluevalues[0]; b=bluevalues[1]; + for(j=0; j<nold; j++) { + if( (s[j].flags & (ST_ZONE|ST_UP|ST_END))!=ST_UP ) + continue; + c=s[j].value; + if(c>b) /* too high */ + break; + if(c>=a) { /* found the lowest stem border */ + /* mark all the stems with the same value */ + if(ISDBG(BLUESTEMS)) + fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value); + /* include ST_END values */ + while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 ) + j--; + s[j].flags |= ST_BLUE; + for(j++; j<nold && s[j].value==c + && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++) + s[j].flags |= ST_BLUE; + break; + } + } + } + /* bottom zones: the logic is the same as for baseline */ + for(i=0; i<notherb; i+=2) { + a=otherblues[i]; b=otherblues[i+1]; + for(j=0; j<nold; j++) { + if( (s[j].flags & (ST_UP|ST_ZONE|ST_END))!=ST_UP ) + continue; + c=s[j].value; + if(c>b) /* too high */ + break; + if(c>=a) { /* found the lowest stem border */ + /* mark all the stems with the same value */ + if(ISDBG(BLUESTEMS)) + fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value); + /* include ST_END values */ + while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 ) + j--; + s[j].flags |= ST_BLUE; + for(j++; j<nold && s[j].value==c + && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++) + s[j].flags |= ST_BLUE; + break; + } + } + } +} + +/* Eliminate invalid stems, join equivalent lines and remove nested stems + * to build the main (non-substituted) set of stems. + * XXX add consideration of the italic angle + */ +static int +joinmainstems( + STEM * s, + int nold, + int useblues /* do we use the blue values ? */ +) +{ +#define MAX_STACK 1000 + STEM stack[MAX_STACK]; + int nstack = 0; + int sbottom = 0; + int nnew; + int i, j, k; + int a, b, c, w1, w2, w3; + int fw, fd; + /* + * priority of the last found stem: + * 0 - nothing found yet + * 1 - has ST_END in it (one or more) + * 2 - has no ST_END and no ST_FLAT, can override only one stem + * with priority 1 + * 3 - has no ST_END and at least one ST_FLAT, can override one + * stem with priority 2 or any number of stems with priority 1 + * 4 (handled separately) - has ST_BLUE, can override anything + */ + int readystem = 0; + int pri; + int nlps = 0; /* number of non-committed + * lowest-priority stems */ + + + for (i = 0, nnew = 0; i < nold; i++) { + if (s[i].flags & (ST_UP|ST_ZONE)) { + if(s[i].flags & ST_BLUE) { + /* we just HAVE to use this value */ + if (readystem) + nnew += 2; + readystem=0; + + /* remember the list of Blue zone stems with the same value */ + for(a=i, i++; i<nold && s[a].value==s[i].value + && (s[i].flags & ST_BLUE); i++) + {} + b=i; /* our range is a <= i < b */ + c= -1; /* index of our best guess up to now */ + pri=0; + /* try to find a match, don't cross blue zones */ + for(; i<nold && (s[i].flags & ST_BLUE)==0; i++) { + if(s[i].flags & ST_UP) { + if(s[i].flags & ST_TOPZONE) + break; + else + continue; + } + for(j=a; j<b; j++) { + if(!stemoverlap(&s[j], &s[i]) ) + continue; + /* consider priorities */ + if( ( (s[j].flags|s[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) { + c=i; + goto bluematch; + } + if( ((s[j].flags|s[i].flags) & ST_END)==0 ) { + if(pri < 2) { + c=i; pri=2; + } + } else { + if(pri == 0) { + c=i; pri=1; + } + } + } + } + bluematch: + /* clean up the stack */ + nstack=sbottom=0; + readystem=0; + /* add this stem */ + s[nnew++]=s[a]; + if(c<0) { /* make one-dot-wide stem */ + if(nnew>=b) { /* have no free space */ + for(j=nold; j>=b; j--) /* make free space */ + s[j]=s[j-1]; + b++; + nold++; + } + s[nnew]=s[a]; + s[nnew].flags &= ~(ST_UP|ST_BLUE); + nnew++; + i=b-1; + } else { + s[nnew++]=s[c]; + i=c; /* skip up to this point */ + } + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% +stem %d...%d U BLUE\n", + s[nnew-2].value, s[nnew-1].value); + } else { + if (nstack >= MAX_STACK) { + WARNING_1 fprintf(stderr, "Warning: **** converter's stem stack overflow ****\n"); + nstack = 0; + } + stack[nstack++] = s[i]; + } + } else if(s[i].flags & ST_BLUE) { + /* again, we just HAVE to use this value */ + if (readystem) + nnew += 2; + readystem=0; + + /* remember the list of Blue zone stems with the same value */ + for(a=i, i++; i<nold && s[a].value==s[i].value + && (s[i].flags & ST_BLUE); i++) + {} + b=i; /* our range is a <= i < b */ + c= -1; /* index of our best guess up to now */ + pri=0; + /* try to find a match */ + for (i = nstack - 1; i >= 0; i--) { + if( (stack[i].flags & ST_UP)==0 ) { + if( (stack[i].flags & (ST_ZONE|ST_TOPZONE))==ST_ZONE ) + break; + else + continue; + } + for(j=a; j<b; j++) { + if(!stemoverlap(&s[j], &stack[i]) ) + continue; + /* consider priorities */ + if( ( (s[j].flags|stack[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) { + c=i; + goto bluedownmatch; + } + if( ((s[j].flags|stack[i].flags) & ST_END)==0 ) { + if(pri < 2) { + c=i; pri=2; + } + } else { + if(pri == 0) { + c=i; pri=1; + } + } + } + } + bluedownmatch: + /* if found no match make a one-dot-wide stem */ + if(c<0) { + c=0; + stack[0]=s[b-1]; + stack[0].flags |= ST_UP; + stack[0].flags &= ~ST_BLUE; + } + /* remove all the stems conflicting with this one */ + readystem=0; + for(j=nnew-2; j>=0; j-=2) { + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% ?stem %d...%d -- %d\n", + s[j].value, s[j+1].value, stack[c].value); + if(s[j+1].value < stack[c].value) /* no conflict */ + break; + if(s[j].flags & ST_BLUE) { + /* oops, we don't want to spoil other blue zones */ + stack[c].value=s[j+1].value+1; + break; + } + if( (s[j].flags|s[j+1].flags) & ST_END ) { + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% -stem %d...%d p=1\n", + s[j].value, s[j+1].value); + continue; /* pri==1, silently discard it */ + } + /* we want to discard no nore than 2 stems of pri>=2 */ + if( ++readystem > 2 ) { + /* change our stem to not conflict */ + stack[c].value=s[j+1].value+1; + break; + } else { + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% -stem %d...%d p>=2\n", + s[j].value, s[j+1].value); + continue; + } + } + nnew=j+2; + /* add this stem */ + if(nnew>=b-1) { /* have no free space */ + for(j=nold; j>=b-1; j--) /* make free space */ + s[j]=s[j-1]; + b++; + nold++; + } + s[nnew++]=stack[c]; + s[nnew++]=s[b-1]; + /* clean up the stack */ + nstack=sbottom=0; + readystem=0; + /* set the next position to search */ + i=b-1; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% +stem %d...%d D BLUE\n", + s[nnew-2].value, s[nnew-1].value); + } else if (nstack > 0) { + + /* + * check whether our stem overlaps with anything in + * stack + */ + for (j = nstack - 1; j >= sbottom; j--) { + if (s[i].value <= stack[j].value) + break; + if (stack[j].flags & ST_ZONE) + continue; + + if ((s[i].flags & ST_END) + || (stack[j].flags & ST_END)) + pri = 1; + else if ((s[i].flags & ST_FLAT) + || (stack[j].flags & ST_FLAT)) + pri = 3; + else + pri = 2; + + if ((pri < readystem && s[nnew + 1].value >= stack[j].value) + || !stemoverlap(&stack[j], &s[i])) + continue; + + if (readystem > 1 && s[nnew + 1].value < stack[j].value) { + nnew += 2; + readystem = 0; + nlps = 0; + } + /* + * width of the previous stem (if it's + * present) + */ + w1 = s[nnew + 1].value - s[nnew].value; + + /* width of this stem */ + w2 = s[i].value - stack[j].value; + + if (readystem == 0) { + /* nothing yet, just add a new stem */ + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + readystem = pri; + if (pri == 1) + nlps = 1; + else if (pri == 2) + sbottom = j; + else { + sbottom = j + 1; + while (sbottom < nstack + && stack[sbottom].value <= stack[j].value) + sbottom++; + } + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } else if (pri == 1) { + if (stack[j].value > s[nnew + 1].value) { + /* + * doesn't overlap with the + * previous one + */ + nnew += 2; + nlps++; + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } else if (w2 < w1) { + /* is narrower */ + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d %d->%d\n", + stack[j].value, s[i].value, pri, nlps, w1, w2); + } + } else if (pri == 2) { + if (readystem == 2) { + /* choose the narrower stem */ + if (w1 > w2) { + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + sbottom = j; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } + /* else readystem==1 */ + } else if (stack[j].value > s[nnew + 1].value) { + /* + * value doesn't overlap with + * the previous one + */ + nnew += 2; + nlps = 0; + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + sbottom = j; + readystem = pri; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } else if (nlps == 1 + || stack[j].value > s[nnew - 1].value) { + /* + * we can replace the top + * stem + */ + nlps = 0; + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + readystem = pri; + sbottom = j; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } + } else if (readystem == 3) { /* that means also + * pri==3 */ + /* choose the narrower stem */ + if (w1 > w2) { + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + sbottom = j + 1; + while (sbottom < nstack + && stack[sbottom].value <= stack[j].value) + sbottom++; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } + } else if (pri == 3) { + /* + * we can replace as many stems as + * neccessary + */ + nnew += 2; + while (nnew > 0 && s[nnew - 1].value >= stack[j].value) { + nnew -= 2; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% -stem %d..%d\n", + s[nnew].value, s[nnew + 1].value); + } + nlps = 0; + s[nnew] = stack[j]; + s[nnew + 1] = s[i]; + readystem = pri; + sbottom = j + 1; + while (sbottom < nstack + && stack[sbottom].value <= stack[j].value) + sbottom++; + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n", + stack[j].value, s[i].value, pri, nlps); + } + } + } + } + if (readystem) + nnew += 2; + + /* change the 1-pixel-wide stems to 20-pixel-wide stems if possible + * the constant 20 is recommended in the Type1 manual + */ + if(useblues) { + for(i=0; i<nnew; i+=2) { + if(s[i].value != s[i+1].value) + continue; + if( ((s[i].flags ^ s[i+1].flags) & ST_BLUE)==0 ) + continue; + if( s[i].flags & ST_BLUE ) { + if(nnew>i+2 && s[i+2].value<s[i].value+22) + s[i+1].value=s[i+2].value-2; /* compensate for fuzziness */ + else + s[i+1].value+=20; + } else { + if(i>0 && s[i-1].value>s[i].value-22) + s[i].value=s[i-1].value+2; /* compensate for fuzziness */ + else + s[i].value-=20; + } + } + } + /* make sure that no stem it stretched between + * a top zone and a bottom zone + */ + if(useblues) { + for(i=0; i<nnew; i+=2) { + a=10000; /* lowest border of top zone crosing the stem */ + b= -10000; /* highest border of bottom zone crossing the stem */ + + for(j=2; j<nblues; j++) { + c=bluevalues[j]; + if( c>=s[i].value && c<=s[i+1].value && c<a ) + a=c; + } + if(nblues>=2) { + c=bluevalues[1]; + if( c>=s[i].value && c<=s[i+1].value && c>b ) + b=c; + } + for(j=1; j<notherb; j++) { + c=otherblues[j]; + if( c>=s[i].value && c<=s[i+1].value && c>b ) + b=c; + } + if( a!=10000 && b!= -10000 ) { /* it is stretched */ + /* split the stem into 2 ghost stems */ + for(j=nnew+1; j>i+1; j--) /* make free space */ + s[j]=s[j-2]; + nnew+=2; + + if(s[i].value+22 >= a) + s[i+1].value=a-2; /* leave space for fuzziness */ + else + s[i+1].value=s[i].value+20; + + if(s[i+3].value-22 <= b) + s[i+2].value=b+2; /* leave space for fuzziness */ + else + s[i+2].value=s[i+3].value-20; + + i+=2; + } + } + } + /* look for triple stems */ + for (i = 0; i < nnew; i += 2) { + if (nnew - i >= 6) { + a = s[i].value + s[i + 1].value; + b = s[i + 2].value + s[i + 3].value; + c = s[i + 4].value + s[i + 5].value; + + w1 = s[i + 1].value - s[i].value; + w2 = s[i + 3].value - s[i + 2].value; + w3 = s[i + 5].value - s[i + 4].value; + + fw = w3 - w1; /* fuzz in width */ + fd = ((c - b) - (b - a)); /* fuzz in distance + * (doubled) */ + + /* we are able to handle some fuzz */ + /* + * it doesn't hurt if the declared stem is a bit + * narrower than actual unless it's an edge in + * a blue zone + */ + if (abs(abs(fd) - abs(fw)) * 5 < w2 + && abs(fw) * 20 < (w1 + w3)) { /* width dirrerence <10% */ + + if(useblues) { /* check that we don't disturb any blue stems */ + j=c; k=a; + if (fw > 0) { + if (fd > 0) { + if( s[i+5].flags & ST_BLUE ) + continue; + j -= fw; + } else { + if( s[i+4].flags & ST_BLUE ) + continue; + j += fw; + } + } else if(fw < 0) { + if (fd > 0) { + if( s[i+1].flags & ST_BLUE ) + continue; + k -= fw; + } else { + if( s[i].flags & ST_BLUE ) + continue; + k += fw; + } + } + pri = ((j - b) - (b - k)); + + if (pri > 0) { + if( s[i+2].flags & ST_BLUE ) + continue; + } else if(pri < 0) { + if( s[i+3].flags & ST_BLUE ) + continue; + } + } + + /* + * first fix up the width of 1st and 3rd + * stems + */ + if (fw > 0) { + if (fd > 0) { + s[i + 5].value -= fw; + c -= fw; + } else { + s[i + 4].value += fw; + c += fw; + } + } else { + if (fd > 0) { + s[i + 1].value -= fw; + a -= fw; + } else { + s[i].value += fw; + a += fw; + } + } + fd = ((c - b) - (b - a)); + + if (fd > 0) { + s[i + 2].value += abs(fd) / 2; + } else { + s[i + 3].value -= abs(fd) / 2; + } + + s[i].flags |= ST_3; + i += 4; + } + } + } + + return (nnew & ~1); /* number of lines must be always even */ +} + +/* + * these macros and function allow to set the base stem, + * check that it's not empty and subtract another stem + * from the base stem (possibly dividing it into multiple parts) + */ + +/* pairs for pieces of the base stem */ +static short xbstem[MAX_STEMS*2]; +/* index of the last point */ +static int xblast= -1; + +#define setbasestem(from, to) \ + (xbstem[0]=from, xbstem[1]=to, xblast=1) +#define isbaseempty() (xblast<=0) + +/* returns 1 if was overlapping, 0 otherwise */ +static int +subfrombase( + int from, + int to +) +{ + int a, b; + int i, j; + + if(isbaseempty()) + return 0; + + /* handle the simple case simply */ + if(from > xbstem[xblast] || to < xbstem[0]) + return 0; + + /* the binary search may be more efficient */ + /* but for now the linear search is OK */ + for(b=1; from > xbstem[b]; b+=2) {} /* result: from <= xbstem[b] */ + for(a=xblast-1; to < xbstem[a]; a-=2) {} /* result: to >= xbstem[a] */ + + /* now the interesting examples are: + * (it was hard for me to understand, so I looked at the examples) + * 1 + * a|-----| |-----|b |-----| |-----| + * f|-----|t + * 2 + * a|-----|b |-----| |-----| |-----| + * f|--|t + * 3 + * a|-----|b |-----| |-----| |-----| + * f|-----|t + * 4 + * |-----|b a|-----| |-----| |-----| + * f|------------|t + * 5 + * |-----| |-----|b |-----| a|-----| + * f|-----------------------------|t + * 6 + * |-----|b |-----| |-----| a|-----| + * f|--------------------------------------------------|t + * 7 + * |-----|b |-----| a|-----| |-----| + * f|--------------------------|t + */ + + if(a < b-1) /* hits a gap - example 1 */ + return 0; + + /* now the subtraction itself */ + + if(a==b-1 && from > xbstem[a] && to < xbstem[b]) { + /* overlaps with only one subrange and splits it - example 2 */ + j=xblast; i=(xblast+=2); + while(j>=b) + xbstem[i--]=xbstem[j--]; + xbstem[b]=from-1; + xbstem[b+1]=to+1; + return 1; + /* becomes + * 2a + * a|b || |-----| |-----| |-----| + * f|--|t + */ + } + + if(xbstem[b-1] < from) { + /* cuts the back of this subrange - examples 3, 4, 7 */ + xbstem[b] = from-1; + b+=2; + /* becomes + * 3a + * a|----| |-----|b |-----| |-----| + * f|-----|t + * 4a + * |---| a|-----|b |-----| |-----| + * f|------------|t + * 7a + * |---| |-----|b a|-----| |-----| + * f|--------------------------|t + */ + } + + if(xbstem[a+1] > to) { + /* cuts the front of this subrange - examples 4a, 5, 7a */ + xbstem[a] = to+1; + a-=2; + /* becomes + * 4b + * a|---| |---|b |-----| |-----| + * f|------------|t + * 5b + * |-----| |-----|b a|-----| || + * f|-----------------------------|t + * 7b + * |---| a|-----|b || |-----| + * f|--------------------------|t + */ + } + + if(a < b-1) /* now after modification it hits a gap - examples 3a, 4b */ + return 1; /* because we have removed something */ + + /* now remove the subranges completely covered by the new stem */ + /* examples 5b, 6, 7b */ + i=b-1; j=a+2; + /* positioned as: + * 5b i j + * |-----| |-----|b a|-----| || + * f|-----------------------------|t + * 6 i xblast j + * |-----|b |-----| |-----| a|-----| + * f|--------------------------------------------------|t + * 7b i j + * |---| a|-----|b || |-----| + * f|--------------------------|t + */ + while(j <= xblast) + xbstem[i++]=xbstem[j++]; + xblast=i-1; + return 1; +} + +/* for debugging */ +static void +printbasestem(void) +{ + int i; + + printf("( "); + for(i=0; i<xblast; i+=2) + printf("%d-%d ", xbstem[i], xbstem[i+1]); + printf(") %d\n", xblast); +} + +/* + * Join the stem borders to build the sets of substituted stems + * XXX add consideration of the italic angle + */ +static void +joinsubstems( + STEM * s, + short *pairs, + int nold, + int useblues /* do we use the blue values ? */ +) +{ + int i, j, x; + static unsigned char mx[MAX_STEMS][MAX_STEMS]; + + /* we do the substituted groups of stems first + * and it looks like it's going to be REALLY SLOW + * AND PAINFUL but let's bother about it later + */ + + /* for the substituted stems we don't bother about [hv]stem3 - + * anyway the X11R6 rasterizer does not bother about hstem3 + * at all and is able to handle only one global vstem3 + * per glyph + */ + + /* clean the used part of matrix */ + for(i=0; i<nold; i++) + for(j=0; j<nold; j++) + mx[i][j]=0; + + /* build the matrix of stem pairs */ + for(i=0; i<nold; i++) { + if( s[i].flags & ST_ZONE ) + continue; + if(s[i].flags & ST_BLUE) + mx[i][i]=1; /* allow to pair with itself if no better pair */ + if(s[i].flags & ST_UP) { /* the down-stems are already matched */ + setbasestem(s[i].from, s[i].to); + for(j=i+1; j<nold; j++) { + if(s[i].value==s[j].value + || s[j].flags & ST_ZONE ) { + continue; + } + x=subfrombase(s[j].from, s[j].to); + + if(s[j].flags & ST_UP) /* match only up+down pairs */ + continue; + + mx[i][j]=mx[j][i]=x; + + if(isbaseempty()) /* nothing else to do */ + break; + } + } + } + + if(ISDBG(SUBSTEMS)) { + fprintf(pfa_file, "%% "); + for(j=0; j<nold; j++) + putc( j%10==0 ? '0'+(j/10)%10 : ' ', pfa_file); + fprintf(pfa_file, "\n%% "); + for(j=0; j<nold; j++) + putc('0'+j%10, pfa_file); + putc('\n', pfa_file); + for(i=0; i<nold; i++) { + fprintf(pfa_file, "%% %3d ",i); + for(j=0; j<nold; j++) + putc( mx[i][j] ? 'X' : '.', pfa_file); + putc('\n', pfa_file); + } + } + + /* now use the matrix to find the best pair for each stem */ + for(i=0; i<nold; i++) { + int pri, lastpri, v, f; + + x= -1; /* best pair: none */ + lastpri=0; + + v=s[i].value; + f=s[i].flags; + + if(f & ST_ZONE) { + pairs[i]= -1; + continue; + } + + if(f & ST_UP) { + for(j=i+1; j<nold; j++) { + if(mx[i][j]==0) + continue; + + if( (f | s[j].flags) & ST_END ) + pri=1; + else if( (f | s[j].flags) & ST_FLAT ) + pri=3; + else + pri=2; + + if(lastpri==0 + || ( pri > lastpri + && ( lastpri==1 || s[j].value-v<20 || (s[x].value-v)*2 >= s[j].value-v ) ) ) { + lastpri=pri; + x=j; + } + } + } else { + for(j=i-1; j>=0; j--) { + if(mx[i][j]==0) + continue; + + if( (f | s[j].flags) & ST_END ) + pri=1; + else if( (f | s[j].flags) & ST_FLAT ) + pri=3; + else + pri=2; + + if(lastpri==0 + || ( pri > lastpri + && ( lastpri==1 || v-s[j].value<20 || (v-s[x].value)*2 >= v-s[j].value ) ) ) { + lastpri=pri; + x=j; + } + } + } + if(x== -1 && mx[i][i]) + pairs[i]=i; /* a special case */ + else + pairs[i]=x; + } + + if(ISDBG(SUBSTEMS)) { + for(i=0; i<nold; i++) { + j=pairs[i]; + if(j>0) + fprintf(pfa_file, "%% %d...%d (%d x %d)\n", s[i].value, s[j].value, i, j); + } + } +} + +/* + * Make all the stems originating at the same value get the + * same width. Without this the rasterizer may move the dots + * randomly up or down by one pixel, and that looks bad. + * The prioritisation is the same as in findstemat(). + */ +static void +uniformstems( + STEM * s, + short *pairs, + int ns +) +{ + int i, j, from, to, val, dir; + int pri, prevpri[2], wd, prevwd[2], prevbest[2]; + + for(from=0; from<ns; from=to) { + prevpri[0] = prevpri[1] = 0; + prevwd[0] = prevwd[1] = 0; + prevbest[0] = prevbest[1] = -1; + val = s[from].value; + + for(to = from; to<ns && s[to].value == val; to++) { + dir = ((s[to].flags & ST_UP)!=0); + + i=pairs[to]; /* the other side of this stem */ + if(i<0 || i==to) + continue; /* oops, no other side */ + wd=abs(s[i].value-val); + if(wd == 0) + continue; + pri=1; + if( (s[to].flags | s[i].flags) & ST_END ) + pri=0; + if( prevbest[dir] == -1 || pri > prevpri[dir] || wd<prevwd[dir] ) { + prevbest[dir]=i; + prevpri[dir]=pri; + prevwd[dir]=wd; + } + } + + for(i=from; i<to; i++) { + dir = ((s[i].flags & ST_UP)!=0); + if(prevbest[dir] >= 0) { + if(ISDBG(SUBSTEMS)) { + fprintf(stderr, "at %d (%s %d) pair %d->%d(%d)\n", i, + (dir ? "UP":"DOWN"), s[i].value, pairs[i], prevbest[dir], + s[prevbest[dir]].value); + } + pairs[i] = prevbest[dir]; + } + } + } +} + +/* + * Find the best stem in the array at the specified (value, origin), + * related to the entry ge. + * Returns its index in the array sp, -1 means "none". + * prevbest is the result for the other end of the line, we must + * find something better than it or leave it as it is. + */ +static int +findstemat( + int value, + int origin, + GENTRY *ge, + STEM *sp, + short *pairs, + int ns, + int prevbest /* -1 means "none" */ +) +{ + int i, min, max; + int v, si; + int pri, prevpri; /* priority, 0 = has ST_END, 1 = no ST_END */ + int wd, prevwd; /* stem width */ + + si= -1; /* nothing yet */ + + /* stems are ordered by value, binary search */ + min=0; max=ns; /* min <= i < max */ + while( min < max ) { + i=(min+max)/2; + v=sp[i].value; + if(v<value) + min=i+1; + else if(v>value) + max=i; + else { + si=i; /* temporary value */ + break; + } + } + + if( si < 0 ) /* found nothing this time */ + return prevbest; + + /* find the priority of the prevbest */ + /* we expect that prevbest has a pair */ + if(prevbest>=0) { + i=pairs[prevbest]; + prevpri=1; + if( (sp[prevbest].flags | sp[i].flags) & ST_END ) + prevpri=0; + prevwd=abs(sp[i].value-value); + } + + /* stems are not ordered by origin, so now do the linear search */ + + while( si>0 && sp[si-1].value==value ) /* find the first one */ + si--; + + for(; si<ns && sp[si].value==value; si++) { + if(sp[si].origin != origin) + continue; + if(sp[si].ge != ge) { + if(ISDBG(SUBSTEMS)) { + fprintf(stderr, + "dbg: possible self-intersection at v=%d o=%d exp_ge=0x%x ge=0x%x\n", + value, origin, ge, sp[si].ge); + } + continue; + } + i=pairs[si]; /* the other side of this stem */ + if(i<0) + continue; /* oops, no other side */ + pri=1; + if( (sp[si].flags | sp[i].flags) & ST_END ) + pri=0; + wd=abs(sp[i].value-value); + if( prevbest == -1 || pri >prevpri + || (pri==prevpri && prevwd==0) || (wd!=0 && wd<prevwd) ) { + prevbest=si; + prevpri=pri; + prevwd=wd; + continue; + } + } + + return prevbest; +} + +/* add the substems for one glyph entry + * (called from groupsubstems()) + * returns 0 if all OK, 1 if too many groups + */ + +static int gssentry_lastgrp=0; /* reset to 0 for each new glyph */ + +static int +gssentry( /* crazy number of parameters */ + GENTRY *ge, + STEM *hs, /* horizontal stems, sorted by value */ + short *hpairs, + int nhs, + STEM *vs, /* vertical stems, sorted by value */ + short *vpairs, + int nvs, + STEMBOUNDS *s, + short *egp, + int *nextvsi, + int *nexthsi /* -2 means "check by yourself" */ +) { + enum { + SI_VP, /* vertical primary */ + SI_HP, /* horizontal primary */ + SI_SIZE /* size of the array */ + }; + int si[SI_SIZE]; /* indexes of relevant stems */ + + /* the bounds of the existing relevant stems */ + STEMBOUNDS r[ sizeof(si) / sizeof(si[0]) * 2 ]; + char rexpand; /* by how much we need to expand the group */ + int nr; /* and the number of them */ + + /* yet more temporary storage */ + short lb, hb, isvert; + int conflict, grp; + int i, j, x, y; + + + /* for each line or curve we try to find a horizontal and + * a vertical stem corresponding to its first point + * (corresponding to the last point of the previous + * glyph entry), because the directions of the lines + * will be eventually reversed and it will then become the last + * point. And the T1 rasterizer applies the hints to + * the last point. + * + */ + + /* start with the common part, the first point */ + x=ge->prev->ix3; + y=ge->prev->iy3; + + if(*nextvsi == -2) + si[SI_VP]=findstemat(x, y, ge, vs, vpairs, nvs, -1); + else { + si[SI_VP]= *nextvsi; *nextvsi= -2; + } + if(*nexthsi == -2) + si[SI_HP]=findstemat(y, x, ge, hs, hpairs, nhs, -1); + else { + si[SI_HP]= *nexthsi; *nexthsi= -2; + } + + /* + * For the horizontal lines we make sure that both + * ends of the line have the same horizontal stem, + * and the same thing for vertical lines and stems. + * In both cases we enforce the stem for the next entry. + * Otherwise unpleasant effects may arise. + */ + + if(ge->type==GE_LINE) { + if(ge->ix3==x) { /* vertical line */ + *nextvsi=si[SI_VP]=findstemat(x, ge->iy3, ge->frwd, vs, vpairs, nvs, si[SI_VP]); + } else if(ge->iy3==y) { /* horizontal line */ + *nexthsi=si[SI_HP]=findstemat(y, ge->ix3, ge->frwd, hs, hpairs, nhs, si[SI_HP]); + } + } + + if(si[SI_VP]+si[SI_HP] == -2) /* no stems, leave it alone */ + return 0; + + /* build the array of relevant bounds */ + nr=0; + for(i=0; i< sizeof(si) / sizeof(si[0]); i++) { + STEM *sp; + short *pairs; + int step; + int f; + int nzones, firstzone, binzone, einzone; + int btype, etype; + + if(si[i] < 0) + continue; + + if(i<SI_HP) { + r[nr].isvert=1; sp=vs; pairs=vpairs; + } else { + r[nr].isvert=0; sp=hs; pairs=hpairs; + } + + r[nr].low=sp[ si[i] ].value; + r[nr].high=sp[ pairs[ si[i] ] ].value; + + if(r[nr].low > r[nr].high) { + j=r[nr].low; r[nr].low=r[nr].high; r[nr].high=j; + step= -1; + } else { + step=1; + } + + /* handle the interaction with Blue Zones */ + + if(i>=SI_HP) { /* only for horizontal stems */ + if(si[i]==pairs[si[i]]) { + /* special case, the outermost stem in the + * Blue Zone without a pair, simulate it to 20-pixel + */ + if(sp[ si[i] ].flags & ST_UP) { + r[nr].high+=20; + for(j=si[i]+1; j<nhs; j++) + if( (sp[j].flags & (ST_ZONE|ST_TOPZONE)) + == (ST_ZONE|ST_TOPZONE) ) { + if(r[nr].high > sp[j].value-2) + r[nr].high=sp[j].value-2; + break; + } + } else { + r[nr].low-=20; + for(j=si[i]-1; j>=0; j--) + if( (sp[j].flags & (ST_ZONE|ST_TOPZONE)) + == (ST_ZONE) ) { + if(r[nr].low < sp[j].value+2) + r[nr].low=sp[j].value+2; + break; + } + } + } + + /* check that the stem borders don't end up in + * different Blue Zones */ + f=sp[ si[i] ].flags; + nzones=0; einzone=binzone=0; + for(j=si[i]; j!=pairs[ si[i] ]; j+=step) { + if( (sp[j].flags & ST_ZONE)==0 ) + continue; + /* if see a zone border going in the same direction */ + if( ((f ^ sp[j].flags) & ST_UP)==0 ) { + if( ++nzones == 1 ) { + firstzone=sp[j].value; /* remember the first one */ + etype=sp[j].flags & ST_TOPZONE; + } + einzone=1; + + } else { /* the opposite direction */ + if(nzones==0) { /* beginning is in a blue zone */ + binzone=1; + btype=sp[j].flags & ST_TOPZONE; + } + einzone=0; + } + } + + /* beginning and end are in Blue Zones of different types */ + if( binzone && einzone && (btype ^ etype)!=0 ) { + if( sp[si[i]].flags & ST_UP ) { + if(firstzone > r[nr].low+22) + r[nr].high=r[nr].low+20; + else + r[nr].high=firstzone-2; + } else { + if(firstzone < r[nr].high-22) + r[nr].low=r[nr].high-20; + else + r[nr].low=firstzone+2; + } + } + } + + if(ISDBG(SUBSTEMS)) + fprintf(pfa_file, "%% at(%d,%d)[%d,%d] %d..%d %c (%d x %d)\n", x, y, i, nr, + r[nr].low, r[nr].high, r[nr].isvert ? 'v' : 'h', + si[i], pairs[si[i]]); + + nr++; + } + + /* now try to find a group */ + conflict=0; /* no conflicts found yet */ + for(j=0; j<nr; j++) + r[j].already=0; + + /* check if it fits into the last group */ + grp = gssentry_lastgrp; + i = (grp==0)? 0 : egp[grp-1]; + for(; i<egp[grp]; i++) { + lb=s[i].low; hb=s[i].high; isvert=s[i].isvert; + for(j=0; j<nr; j++) + if( r[j].isvert==isvert /* intersects */ + && r[j].low <= hb && r[j].high >= lb ) { + if( r[j].low == lb && r[j].high == hb ) /* coincides */ + r[j].already=1; + else + conflict=1; + } + + if(conflict) + break; + } + + if(conflict) { /* nope, check all the groups */ + for(j=0; j<nr; j++) + r[j].already=0; + + for(i=0, grp=0; i<egp[NSTEMGRP-1]; i++) { + if(i == egp[grp]) { /* checked all stems in a group */ + if(conflict) { + grp++; conflict=0; /* check the next group */ + for(j=0; j<nr; j++) + r[j].already=0; + } else + break; /* insert into this group */ + } + + lb=s[i].low; hb=s[i].high; isvert=s[i].isvert; + for(j=0; j<nr; j++) + if( r[j].isvert==isvert /* intersects */ + && r[j].low <= hb && r[j].high >= lb ) { + if( r[j].low == lb && r[j].high == hb ) /* coincides */ + r[j].already=1; + else + conflict=1; + } + + if(conflict) + i=egp[grp]-1; /* fast forward to the next group */ + } + } + + /* do we have any empty group ? */ + if(conflict && grp < NSTEMGRP-1) { + grp++; conflict=0; + for(j=0; j<nr; j++) + r[j].already=0; + } + + if(conflict) { /* oops, can't find any group to fit */ + return 1; + } + + /* OK, add stems to this group */ + + rexpand = nr; + for(j=0; j<nr; j++) + rexpand -= r[j].already; + + if(rexpand > 0) { + for(i=egp[NSTEMGRP-1]-1; i>=egp[grp]; i--) + s[i+rexpand]=s[i]; + for(i=0; i<nr; i++) + if(!r[i].already) + s[egp[grp]++]=r[i]; + for(i=grp+1; i<NSTEMGRP; i++) + egp[i]+=rexpand; + } + + ge->stemid = gssentry_lastgrp = grp; + return 0; +} + +/* + * Create the groups of substituted stems from the list. + * Each group will be represented by a subroutine in the Subs + * array. + */ + +static void +groupsubstems( + GLYPH *g, + STEM *hs, /* horizontal stems, sorted by value */ + short *hpairs, + int nhs, + STEM *vs, /* vertical stems, sorted by value */ + short *vpairs, + int nvs +) +{ + GENTRY *ge; + int i, j; + + /* temporary storage */ + STEMBOUNDS s[MAX_STEMS*2]; + /* indexes in there, pointing past the end each stem group */ + short egp[NSTEMGRP]; + + int nextvsi, nexthsi; /* -2 means "check by yourself" */ + + for(i=0; i<NSTEMGRP; i++) + egp[i]=0; + + nextvsi=nexthsi= -2; /* processed no horiz/vert line */ + + gssentry_lastgrp = 0; /* reset the last group for new glyph */ + + for (ge = g->entries; ge != 0; ge = ge->next) { + if(ge->type!=GE_LINE && ge->type!=GE_CURVE) { + nextvsi=nexthsi= -2; /* next path is independent */ + continue; + } + + if( gssentry(ge, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) { + WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n", + g->name, NSTEMGRP); + /* it's better to have no substituted hints at all than have only part */ + for (ge = g->entries; ge != 0; ge = ge->next) + ge->stemid= -1; + g->nsg=0; /* just to be safe, already is 0 by initialization */ + return; + } + + /* + * handle the last vert/horiz line of the path specially, + * correct the hint for the first entry of the path + */ + if(ge->frwd != ge->next && (nextvsi != -2 || nexthsi != -2) ) { + if( gssentry(ge->frwd, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) { + WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n", + g->name, NSTEMGRP); + /* it's better to have no substituted hints at all than have only part */ + for (ge = g->entries; ge != 0; ge = ge->next) + ge->stemid= -1; + g->nsg=0; /* just to be safe, already is 0 by initialization */ + return; + } + } + + } + + /* find the index of the first empty group - same as the number of groups */ + if(egp[0]>0) { + for(i=1; i<NSTEMGRP && egp[i]!=egp[i-1]; i++) + {} + g->nsg=i; + } else + g->nsg=0; + + if(ISDBG(SUBSTEMS)) { + fprintf(pfa_file, "%% %d substem groups (%d %d %d)\n", g->nsg, + g->nsg>1 ? egp[g->nsg-2] : -1, + g->nsg>0 ? egp[g->nsg-1] : -1, + g->nsg<NSTEMGRP ? egp[g->nsg] : -1 ); + j=0; + for(i=0; i<g->nsg; i++) { + fprintf(pfa_file, "%% grp %3d: ", i); + for(; j<egp[i]; j++) { + fprintf(pfa_file, " %4d...%-4d %c ", s[j].low, s[j].high, + s[j].isvert ? 'v' : 'h'); + } + fprintf(pfa_file, "\n"); + } + } + + if(g->nsg==1) { /* it would be the same as the main stems */ + /* so erase it */ + for (ge = g->entries; ge != 0; ge = ge->next) + ge->stemid= -1; + g->nsg=0; + } + + if(g->nsg>0) { + if( (g->nsbs=malloc(g->nsg * sizeof (egp[0]))) == 0 ) { + fprintf(stderr, "**** not enough memory for substituted hints ****\n"); + exit(255); + } + memmove(g->nsbs, egp, g->nsg * sizeof(short)); + if( (g->sbstems=malloc(egp[g->nsg-1] * sizeof (s[0]))) == 0 ) { + fprintf(stderr, "**** not enough memory for substituted hints ****\n"); + exit(255); + } + memmove(g->sbstems, s, egp[g->nsg-1] * sizeof(s[0])); + } +} + +void +buildstems( + GLYPH * g +) +{ + STEM hs[MAX_STEMS], vs[MAX_STEMS]; /* temporary working + * storage */ + short hs_pairs[MAX_STEMS], vs_pairs[MAX_STEMS]; /* best pairs for these stems */ + STEM *sp; + GENTRY *ge, *nge, *pge; + int nx, ny; + int ovalue; + int totals, grp, lastgrp; + + assertisint(g, "buildstems int"); + + g->nhs = g->nvs = 0; + memset(hs, 0, sizeof hs); + memset(vs, 0, sizeof vs); + + /* first search the whole character for possible stem points */ + + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type == GE_CURVE) { + + /* + * SURPRISE! + * We consider the stems bound by the + * H/V ends of the curves as flat ones. + * + * But we don't include the point on the + * other end into the range. + */ + + /* first check the beginning of curve */ + /* if it is horizontal, add a hstem */ + if (ge->iy1 == ge->prev->iy3) { + hs[g->nhs].value = ge->iy1; + + if (ge->ix1 < ge->prev->ix3) + hs[g->nhs].flags = ST_FLAT | ST_UP; + else + hs[g->nhs].flags = ST_FLAT; + + hs[g->nhs].origin = ge->prev->ix3; + hs[g->nhs].ge = ge; + + if (ge->ix1 < ge->prev->ix3) { + hs[g->nhs].from = ge->ix1+1; + hs[g->nhs].to = ge->prev->ix3; + if(hs[g->nhs].from > hs[g->nhs].to) + hs[g->nhs].from--; + } else { + hs[g->nhs].from = ge->prev->ix3; + hs[g->nhs].to = ge->ix1-1; + if(hs[g->nhs].from > hs[g->nhs].to) + hs[g->nhs].to++; + } + if (ge->ix1 != ge->prev->ix3) + g->nhs++; + } + /* if it is vertical, add a vstem */ + else if (ge->ix1 == ge->prev->ix3) { + vs[g->nvs].value = ge->ix1; + + if (ge->iy1 > ge->prev->iy3) + vs[g->nvs].flags = ST_FLAT | ST_UP; + else + vs[g->nvs].flags = ST_FLAT; + + vs[g->nvs].origin = ge->prev->iy3; + vs[g->nvs].ge = ge; + + if (ge->iy1 < ge->prev->iy3) { + vs[g->nvs].from = ge->iy1+1; + vs[g->nvs].to = ge->prev->iy3; + if(vs[g->nvs].from > vs[g->nvs].to) + vs[g->nvs].from--; + } else { + vs[g->nvs].from = ge->prev->iy3; + vs[g->nvs].to = ge->iy1-1; + if(vs[g->nvs].from > vs[g->nvs].to) + vs[g->nvs].to++; + } + + if (ge->iy1 != ge->prev->iy3) + g->nvs++; + } + /* then check the end of curve */ + /* if it is horizontal, add a hstem */ + if (ge->iy3 == ge->iy2) { + hs[g->nhs].value = ge->iy3; + + if (ge->ix3 < ge->ix2) + hs[g->nhs].flags = ST_FLAT | ST_UP; + else + hs[g->nhs].flags = ST_FLAT; + + hs[g->nhs].origin = ge->ix3; + hs[g->nhs].ge = ge->frwd; + + if (ge->ix3 < ge->ix2) { + hs[g->nhs].from = ge->ix3; + hs[g->nhs].to = ge->ix2-1; + if( hs[g->nhs].from > hs[g->nhs].to ) + hs[g->nhs].to++; + } else { + hs[g->nhs].from = ge->ix2+1; + hs[g->nhs].to = ge->ix3; + if( hs[g->nhs].from > hs[g->nhs].to ) + hs[g->nhs].from--; + } + + if (ge->ix3 != ge->ix2) + g->nhs++; + } + /* if it is vertical, add a vstem */ + else if (ge->ix3 == ge->ix2) { + vs[g->nvs].value = ge->ix3; + + if (ge->iy3 > ge->iy2) + vs[g->nvs].flags = ST_FLAT | ST_UP; + else + vs[g->nvs].flags = ST_FLAT; + + vs[g->nvs].origin = ge->iy3; + vs[g->nvs].ge = ge->frwd; + + if (ge->iy3 < ge->iy2) { + vs[g->nvs].from = ge->iy3; + vs[g->nvs].to = ge->iy2-1; + if( vs[g->nvs].from > vs[g->nvs].to ) + vs[g->nvs].to++; + } else { + vs[g->nvs].from = ge->iy2+1; + vs[g->nvs].to = ge->iy3; + if( vs[g->nvs].from > vs[g->nvs].to ) + vs[g->nvs].from--; + } + + if (ge->iy3 != ge->iy2) + g->nvs++; + } else { + + /* + * check the end of curve for a not smooth + * local extremum + */ + nge = ge->frwd; + + if (nge == 0) + continue; + else if (nge->type == GE_LINE) { + nx = nge->ix3; + ny = nge->iy3; + } else if (nge->type == GE_CURVE) { + nx = nge->ix1; + ny = nge->iy1; + } else + continue; + + /* check for vertical extremums */ + if ((ge->iy3 > ge->iy2 && ge->iy3 > ny) + || (ge->iy3 < ge->iy2 && ge->iy3 < ny)) { + hs[g->nhs].value = ge->iy3; + hs[g->nhs].from + = hs[g->nhs].to + = hs[g->nhs].origin = ge->ix3; + hs[g->nhs].ge = ge->frwd; + + if (ge->ix3 < ge->ix2 + || nx < ge->ix3) + hs[g->nhs].flags = ST_UP; + else + hs[g->nhs].flags = 0; + + if (ge->ix3 != ge->ix2 || nx != ge->ix3) + g->nhs++; + } + /* + * the same point may be both horizontal and + * vertical extremum + */ + /* check for horizontal extremums */ + if ((ge->ix3 > ge->ix2 && ge->ix3 > nx) + || (ge->ix3 < ge->ix2 && ge->ix3 < nx)) { + vs[g->nvs].value = ge->ix3; + vs[g->nvs].from + = vs[g->nvs].to + = vs[g->nvs].origin = ge->iy3; + vs[g->nvs].ge = ge->frwd; + + if (ge->iy3 > ge->iy2 + || ny > ge->iy3) + vs[g->nvs].flags = ST_UP; + else + vs[g->nvs].flags = 0; + + if (ge->iy3 != ge->iy2 || ny != ge->iy3) + g->nvs++; + } + } + + } else if (ge->type == GE_LINE) { + nge = ge->frwd; + + /* if it is horizontal, add a hstem */ + /* and the ends as vstems if they brace the line */ + if (ge->iy3 == ge->prev->iy3 + && ge->ix3 != ge->prev->ix3) { + hs[g->nhs].value = ge->iy3; + if (ge->ix3 < ge->prev->ix3) { + hs[g->nhs].flags = ST_FLAT | ST_UP; + hs[g->nhs].from = ge->ix3; + hs[g->nhs].to = ge->prev->ix3; + } else { + hs[g->nhs].flags = ST_FLAT; + hs[g->nhs].from = ge->prev->ix3; + hs[g->nhs].to = ge->ix3; + } + hs[g->nhs].origin = ge->ix3; + hs[g->nhs].ge = ge->frwd; + + pge = ge->bkwd; + + /* add beginning as vstem */ + vs[g->nvs].value = pge->ix3; + vs[g->nvs].origin + = vs[g->nvs].from + = vs[g->nvs].to = pge->iy3; + vs[g->nvs].ge = ge; + + if(pge->type==GE_CURVE) + ovalue=pge->iy2; + else + ovalue=pge->prev->iy3; + + if (pge->iy3 > ovalue) + vs[g->nvs].flags = ST_UP | ST_END; + else if (pge->iy3 < ovalue) + vs[g->nvs].flags = ST_END; + else + vs[g->nvs].flags = 0; + + if( vs[g->nvs].flags != 0 ) + g->nvs++; + + /* add end as vstem */ + vs[g->nvs].value = ge->ix3; + vs[g->nvs].origin + = vs[g->nvs].from + = vs[g->nvs].to = ge->iy3; + vs[g->nvs].ge = ge->frwd; + + if(nge->type==GE_CURVE) + ovalue=nge->iy1; + else + ovalue=nge->iy3; + + if (ovalue > ge->iy3) + vs[g->nvs].flags = ST_UP | ST_END; + else if (ovalue < ge->iy3) + vs[g->nvs].flags = ST_END; + else + vs[g->nvs].flags = 0; + + if( vs[g->nvs].flags != 0 ) + g->nvs++; + + g->nhs++; + } + /* if it is vertical, add a vstem */ + /* and the ends as hstems if they brace the line */ + else if (ge->ix3 == ge->prev->ix3 + && ge->iy3 != ge->prev->iy3) { + vs[g->nvs].value = ge->ix3; + if (ge->iy3 > ge->prev->iy3) { + vs[g->nvs].flags = ST_FLAT | ST_UP; + vs[g->nvs].from = ge->prev->iy3; + vs[g->nvs].to = ge->iy3; + } else { + vs[g->nvs].flags = ST_FLAT; + vs[g->nvs].from = ge->iy3; + vs[g->nvs].to = ge->prev->iy3; + } + vs[g->nvs].origin = ge->iy3; + vs[g->nvs].ge = ge->frwd; + + pge = ge->bkwd; + + /* add beginning as hstem */ + hs[g->nhs].value = pge->iy3; + hs[g->nhs].origin + = hs[g->nhs].from + = hs[g->nhs].to = pge->ix3; + hs[g->nhs].ge = ge; + + if(pge->type==GE_CURVE) + ovalue=pge->ix2; + else + ovalue=pge->prev->ix3; + + if (pge->ix3 < ovalue) + hs[g->nhs].flags = ST_UP | ST_END; + else if (pge->ix3 > ovalue) + hs[g->nhs].flags = ST_END; + else + hs[g->nhs].flags = 0; + + if( hs[g->nhs].flags != 0 ) + g->nhs++; + + /* add end as hstem */ + hs[g->nhs].value = ge->iy3; + hs[g->nhs].origin + = hs[g->nhs].from + = hs[g->nhs].to = ge->ix3; + hs[g->nhs].ge = ge->frwd; + + if(nge->type==GE_CURVE) + ovalue=nge->ix1; + else + ovalue=nge->ix3; + + if (ovalue < ge->ix3) + hs[g->nhs].flags = ST_UP | ST_END; + else if (ovalue > ge->ix3) + hs[g->nhs].flags = ST_END; + else + hs[g->nhs].flags = 0; + + if( hs[g->nhs].flags != 0 ) + g->nhs++; + + g->nvs++; + } + /* + * check the end of line for a not smooth local + * extremum + */ + nge = ge->frwd; + + if (nge == 0) + continue; + else if (nge->type == GE_LINE) { + nx = nge->ix3; + ny = nge->iy3; + } else if (nge->type == GE_CURVE) { + nx = nge->ix1; + ny = nge->iy1; + } else + continue; + + /* check for vertical extremums */ + if ((ge->iy3 > ge->prev->iy3 && ge->iy3 > ny) + || (ge->iy3 < ge->prev->iy3 && ge->iy3 < ny)) { + hs[g->nhs].value = ge->iy3; + hs[g->nhs].from + = hs[g->nhs].to + = hs[g->nhs].origin = ge->ix3; + hs[g->nhs].ge = ge->frwd; + + if (ge->ix3 < ge->prev->ix3 + || nx < ge->ix3) + hs[g->nhs].flags = ST_UP; + else + hs[g->nhs].flags = 0; + + if (ge->ix3 != ge->prev->ix3 || nx != ge->ix3) + g->nhs++; + } + /* + * the same point may be both horizontal and vertical + * extremum + */ + /* check for horizontal extremums */ + if ((ge->ix3 > ge->prev->ix3 && ge->ix3 > nx) + || (ge->ix3 < ge->prev->ix3 && ge->ix3 < nx)) { + vs[g->nvs].value = ge->ix3; + vs[g->nvs].from + = vs[g->nvs].to + = vs[g->nvs].origin = ge->iy3; + vs[g->nvs].ge = ge->frwd; + + if (ge->iy3 > ge->prev->iy3 + || ny > ge->iy3) + vs[g->nvs].flags = ST_UP; + else + vs[g->nvs].flags = 0; + + if (ge->iy3 != ge->prev->iy3 || ny != ge->iy3) + g->nvs++; + } + } + } + + g->nhs=addbluestems(hs, g->nhs); + sortstems(hs, g->nhs); + sortstems(vs, g->nvs); + + if (ISDBG(STEMS)) + debugstems(g->name, hs, g->nhs, vs, g->nvs); + + /* find the stems interacting with the Blue Zones */ + markbluestems(hs, g->nhs); + + if(subhints) { + if (ISDBG(SUBSTEMS)) + fprintf(pfa_file, "%% %s: joining subst horizontal stems\n", g->name); + joinsubstems(hs, hs_pairs, g->nhs, 1); + uniformstems(hs, hs_pairs, g->nhs); + + if (ISDBG(SUBSTEMS)) + fprintf(pfa_file, "%% %s: joining subst vertical stems\n", g->name); + joinsubstems(vs, vs_pairs, g->nvs, 0); + + groupsubstems(g, hs, hs_pairs, g->nhs, vs, vs_pairs, g->nvs); + } + + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% %s: joining main horizontal stems\n", g->name); + g->nhs = joinmainstems(hs, g->nhs, 1); + if (ISDBG(MAINSTEMS)) + fprintf(pfa_file, "%% %s: joining main vertical stems\n", g->name); + g->nvs = joinmainstems(vs, g->nvs, 0); + + if (ISDBG(MAINSTEMS)) + debugstems(g->name, hs, g->nhs, vs, g->nvs); + + if(g->nhs > 0) { + if ((sp = malloc(sizeof(STEM) * g->nhs)) == 0) { + fprintf(stderr, "**** not enough memory for hints ****\n"); + exit(255); + } + g->hstems = sp; + memcpy(sp, hs, sizeof(STEM) * g->nhs); + } else + g->hstems = 0; + + if(g->nvs > 0) { + if ((sp = malloc(sizeof(STEM) * g->nvs)) == 0) { + fprintf(stderr, "**** not enough memory for hints ****\n"); + exit(255); + } + g->vstems = sp; + memcpy(sp, vs, sizeof(STEM) * g->nvs); + } else + g->vstems = 0; + + /* now check that the stems won't overflow the interpreter's stem stack: + * some interpreters (like X11) push the stems on each change into + * stack and pop them only after the whole glyphs is completed. + */ + + totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */ + lastgrp = -1; + + for (ge = g->entries; ge != 0; ge = ge->next) { + grp=ge->stemid; + if(grp >= 0 && grp != lastgrp) { + if(grp==0) + totals += g->nsbs[0]; + else + totals += g->nsbs[grp] - g->nsbs[grp-1]; + + lastgrp = grp; + } + } + + /* be on the safe side, check for >= , not > */ + if(totals >= max_stemdepth) { /* oops, too deep */ + WARNING_2 { + fprintf(stderr, "Warning: glyph %s needs hint stack depth %d\n", g->name, totals); + fprintf(stderr, " (limit %d): removed the substituted hints from it\n", max_stemdepth); + } + if(g->nsg > 0) { + for (ge = g->entries; ge != 0; ge = ge->next) + ge->stemid = -1; + free(g->sbstems); g->sbstems = 0; + free(g->nsbs); g->nsbs = 0; + g->nsg = 0; + } + } + + /* now check if there are too many main stems */ + totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */ + if(totals >= max_stemdepth) { + /* even worse, too much of non-substituted stems */ + WARNING_2 { + fprintf(stderr, "Warning: glyph %s has %d main hints\n", g->name, totals); + fprintf(stderr, " (limit %d): removed the hints from it\n", max_stemdepth); + } + if(g->vstems) { + free(g->vstems); g->vstems = 0; g->nvs = 0; + } + if(g->hstems) { + free(g->hstems); g->hstems = 0; g->nhs = 0; + } + } +} + +/* convert weird curves that are close to lines into lines. +*/ + +void +fstraighten( + GLYPH * g +) +{ + GENTRY *ge, *pge, *nge, *ige; + double df; + int dir; + double iln, oln; + int svdir, i, o; + + for (ige = g->entries; ige != 0; ige = ige->next) { + if (ige->type != GE_CURVE) + continue; + + ge = ige; + pge = ge->bkwd; + nge = ge->frwd; + + df = 0.; + + /* look for vertical then horizontal */ + for(i=0; i<2; i++) { + o = !i; /* other axis */ + + iln = fabs(ge->fpoints[i][2] - pge->fpoints[i][2]); + oln = fabs(ge->fpoints[o][2] - pge->fpoints[o][2]); + /* + * if current curve is almost a vertical line, and it + * doesn't begin or end horizontally (and the prev/next + * line doesn't join smoothly ?) + */ + if( oln < 1. + || ge->fpoints[o][2] == ge->fpoints[o][1] + || ge->fpoints[o][0] == pge->fpoints[o][2] + || iln > 2. + || (iln > 1. && iln/oln > 0.1) ) + continue; + + + if(ISDBG(STRAIGHTEN)) + fprintf(stderr,"** straighten almost %s\n", (i? "horizontal":"vertical")); + + df = ge->fpoints[i][2] - pge->fpoints[i][2]; + dir = fsign(ge->fpoints[o][2] - pge->fpoints[o][2]); + ge->type = GE_LINE; + + /* + * suck in all the sequence of such almost lines + * going in the same direction but not deviating + * too far from vertical + */ + iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]); + oln = nge->fpoints[o][2] - ge->fpoints[o][2]; + + while (fabs(df) <= 5 && nge->type == GE_CURVE + && dir == fsign(oln) /* that also gives oln != 0 */ + && iln <= 2. + && ( iln <= 1. || iln/fabs(oln) <= 0.1 ) ) { + ge->fx3 = nge->fx3; + ge->fy3 = nge->fy3; + + if(ISDBG(STRAIGHTEN)) + fprintf(stderr,"** straighten collapsing %s\n", (i? "horizontal":"vertical")); + freethisge(nge); + fixendpath(ge); + pge = ge->bkwd; + nge = ge->frwd; + + df = ge->fpoints[i][2] - pge->fpoints[i][2]; + + iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]); + oln = nge->fpoints[o][2] - ge->fpoints[o][2]; + } + + /* now check what do we have as previous/next line */ + + if(ge != pge) { + if( pge->type == GE_LINE && pge->fpoints[i][2] == pge->prev->fpoints[i][2] + && fabs(pge->fpoints[o][2] != pge->prev->fpoints[o][2]) ) { + if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with previous 0x%x 0x%x\n", pge, ge); + /* join the previous line with current */ + pge->fx3 = ge->fx3; + pge->fy3 = ge->fy3; + + ige = freethisge(ge)->prev; /* keep the iterator valid */ + ge = pge; + fixendpath(ge); + pge = ge->bkwd; + } + } + + if(ge != nge) { + if (nge->type == GE_LINE && nge->fpoints[i][2] == ge->fpoints[i][2] + && fabs(nge->fpoints[o][2] != ge->fpoints[o][2]) ) { + if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with next 0x%x 0x%x\n", ge, nge); + /* join the next line with current */ + ge->fx3 = nge->fx3; + ge->fy3 = nge->fy3; + + freethisge(nge); + fixendpath(ge); + pge = ge->bkwd; + nge = ge->frwd; + + } + } + + if(ge != pge) { + /* try to align the lines if neccessary */ + if(df != 0.) + fclosegap(ge, ge, i, df, NULL); + } else { + /* contour consists of only one line, get rid of it */ + ige = freethisge(ge); /* keep the iterator valid */ + if(ige == 0) /* this was the last contour */ + return; + ige = ige->prev; + } + + break; /* don't bother looking at the other axis */ + } + } +} + +/* solve a square equation, + * returns the number of solutions found, the solutions + * are stored in res which should point to array of two doubles. + * min and max limit the area for solutions + */ + +static int +fsqequation( + double a, + double b, + double c, + double *res, + double min, + double max +) +{ + double D; + int n; + + if(ISDBG(SQEQ)) fprintf(stderr, "sqeq(%g,%g,%g) [%g;%g]\n", a, b, c, min, max); + + if(fabs(a) < 0.000001) { /* if a linear equation */ + n=0; + if(fabs(b) < 0.000001) /* not an equation at all */ + return 0; + res[0] = -c/b; + if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: linear t=%g\n", res[0]); + if(res[0] >= min && res[0] <= max) + n++; + return n; + } + + D = b*b - 4.0*a*c; + if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: D=%g\n", D); + if(D<0) + return 0; + + D = sqrt(D); + + n=0; + res[0] = (-b+D) / (2*a); + if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t1=%g\n", res[0]); + if(res[0] >= min && res[0] <= max) + n++; + + res[n] = (-b-D) / (2*a); + if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t2=%g\n", res[n]); + if(res[n] >= min && res[n] <= max) + n++; + + /* return 2nd solution only if it's different enough */ + if(n==2 && fabs(res[0]-res[1])<0.000001) + n=1; + + return n; +} + +/* check that the curves don't cross quadrant boundary */ +/* (float) */ + +/* + Here we make sure that the curve does not continue past + horizontal or vertical extremums. The horizontal points are + explained, vertical points are by analogy. + + The horizontal points are where the derivative + dy/dx is equal to 0. But the Bezier curves are defined by + parametric formulas + x=fx(t) + y=fy(t) + so finding this derivative is complicated. + Also even if we find some point (x,y) splitting at this point + is far not obvious. Fortunately we can use dy/dt = 0 instead, + this gets to a rather simple square equation and splitting + at a known value of t is simple. + + The formulas are: + + y = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 + y = (-A+3*B-3*C+D)*t^3 + (3*A-6*B+3*C)*t^2 + (-3*A+3*B)*t + A + dy/dt = 3*(-A+3*B-3*C+D)*t^2 + 2*(3*A-6*B+3*C)*t + (-3*A+3*B) + */ + +void +ffixquadrants( + GLYPH *g +) +{ + GENTRY *ge, *nge; + int i, j, np, oldnp; + double sp[5]; /* split points, last one empty */ + char dir[5]; /* for debugging, direction by which split happened */ + double a, b, *pts; /* points of a curve */ + + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type != GE_CURVE) + continue; + + doagain: + np = 0; /* no split points yet */ + if(ISDBG(QUAD)) { + fprintf(stderr, "%s: trying 0x%x (%g %g) (%g %g) (%g %g) (%g %g)\n ", g->name, + ge, ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2, + ge->fx3, ge->fy3); + } + for(i=0; i<2; i++) { /* first for x then for y */ + /* find the cooridnates of control points */ + a = ge->prev->fpoints[i][2]; + pts = &ge->fpoints[i][0]; + + oldnp = np; + np += fsqequation( + 3.0*(-a + 3.0*pts[0] - 3.0*pts[1] + pts[2]), + 6.0*(a - 2.0*pts[0] + pts[1]), + 3.0*(-a + pts[0]), + &sp[np], + 0.0, 1.0); /* XXX range is [0;1] */ + + if(np == oldnp) + continue; + + if(ISDBG(QUAD)) + fprintf(stderr, "%s: 0x%x: %d pts(%c): ", + g->name, ge, np-oldnp, i? 'y':'x'); + + /* remove points that are too close to the ends + * because hor/vert ends are permitted, also + * if the split point is VERY close to the ends + * but not exactly then just flatten it and check again. + */ + for(j = oldnp; j<np; j++) { + dir[j] = i; + if(ISDBG(QUAD)) + fprintf(stderr, "%g ", sp[j]); + if(sp[j] < 0.03) { /* front end of curve */ + if(ge->fpoints[i][0] != ge->prev->fpoints[i][2]) { + ge->fpoints[i][0] = ge->prev->fpoints[i][2]; + if(ISDBG(QUAD)) fprintf(stderr, "flattened at front\n"); + goto doagain; + } + if( ge->fpoints[i][1] != ge->fpoints[i][0] + && fsign(ge->fpoints[i][2] - ge->fpoints[i][1]) + != fsign(ge->fpoints[i][1] - ge->fpoints[i][0]) ) { + ge->fpoints[i][1] = ge->fpoints[i][0]; + if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at front\n"); + goto doagain; + } + sp[j] = sp[j+1]; np--; j--; + if(ISDBG(QUAD)) fprintf(stderr, "(front flat) "); + } else if(sp[j] > 0.97) { /* rear end of curve */ + if(ge->fpoints[i][1] != ge->fpoints[i][2]) { + ge->fpoints[i][1] = ge->fpoints[i][2]; + if(ISDBG(QUAD)) fprintf(stderr, "flattened at rear\n"); + goto doagain; + } + if( ge->fpoints[i][0] != ge->fpoints[i][1] + && fsign(ge->prev->fpoints[i][2] - ge->fpoints[i][0]) + != fsign(ge->fpoints[i][0] - ge->fpoints[i][1]) ) { + ge->fpoints[i][0] = ge->fpoints[i][1]; + if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at rear\n"); + goto doagain; + } + sp[j] = sp[j+1]; np--; j--; + if(ISDBG(QUAD)) fprintf(stderr, "(rear flat) "); + } + } + if(ISDBG(QUAD)) fprintf(stderr, "\n"); + } + + if(np==0) /* no split points, leave it alone */ + continue; + + if(ISDBG(QUAD)) { + fprintf(stderr, "%s: splitting 0x%x (%g %g) (%g %g) (%g %g) (%g %g) at %d points\n ", g->name, + ge, ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2, + ge->fx3, ge->fy3, np); + for(i=0; i<np; i++) + fprintf(stderr, "%g(%c) ", sp[i], dir[i] ? 'y':'x'); + fprintf(stderr, "\n"); + } + + /* sort the points ascending */ + for(i=0; i<np; i++) + for(j=i+1; j<np; j++) + if(sp[i] > sp[j]) { + a = sp[i]; sp[i] = sp[j]; sp[j] = a; + } + + /* now finally do the split on each point */ + for(j=0; j<np; j++) { + double k1, k2, c; + + k1 = sp[j]; + k2 = 1 - k1; + + if(ISDBG(QUAD)) fprintf(stderr, " 0x%x %g/%g\n", ge, k1, k2); + + nge = newgentry(GEF_FLOAT); + (*nge) = (*ge); + +#define SPLIT(pt1, pt2) ( (pt1) + k1*((pt2)-(pt1)) ) /* order is important! */ + for(i=0; i<2; i++) { /* for x and y */ + a = ge->fpoints[i][0]; /* get the middle points */ + b = ge->fpoints[i][1]; + + /* calculate new internal points */ + c = SPLIT(a, b); + + ge->fpoints[i][0] = SPLIT(ge->prev->fpoints[i][2], a); + ge->fpoints[i][1] = SPLIT(ge->fpoints[i][0], c); + + nge->fpoints[i][1] = SPLIT(b, nge->fpoints[i][2]); + nge->fpoints[i][0] = SPLIT(c, nge->fpoints[i][1]); + + ge->fpoints[i][2] = SPLIT(ge->fpoints[i][1], + + nge->fpoints[i][0]); + } +#undef SPLIT + + addgeafter(ge, nge); + + /* go to the next part, adjust remaining points */ + ge = nge; + for(i=j+1; i<np; i++) + sp[i] = (sp[i]-k1) / k2; + } + } + +} + +/* check if a curve is a zigzag */ + +static int +iiszigzag( + GENTRY *ge +) +{ + double k, k1, k2; + int a, b; + + if (ge->type != GE_CURVE) + return 0; + + a = ge->iy2 - ge->iy1; + b = ge->ix2 - ge->ix1; + if(a == 0) { + if(b == 0) { + return 0; + } else + k = FBIGVAL; + } else + k = fabs((double) b / (double) a); + + a = ge->iy1 - ge->prev->iy3; + b = ge->ix1 - ge->prev->ix3; + if(a == 0) { + if(b == 0) { + return 0; + } else + k1 = FBIGVAL; + } else + k1 = fabs((double) b / (double) a); + + a = ge->iy3 - ge->iy2; + b = ge->ix3 - ge->ix2; + if(a == 0) { + if(b == 0) { + return 0; + } else + k2 = FBIGVAL; + } else + k2 = fabs((double) b / (double) a); + + /* if the curve is not a zigzag */ + if ((k1+0.0001 >= k && k2 <= k+0.0001) || (k1 <= k+0.0001 && k2+0.0001 >= k)) + return 0; + else + return 1; +} + +/* check if a curve is a zigzag - floating */ + +static int +fiszigzag( + GENTRY *ge +) +{ + double k, k1, k2; + double a, b; + + if (ge->type != GE_CURVE) + return 0; + + a = fabs(ge->fy2 - ge->fy1); + b = fabs(ge->fx2 - ge->fx1); + if(a < FEPS) { + if(b < FEPS) { + return 0; + } else + k = FBIGVAL; + } else + k = b / a; + + a = fabs(ge->fy1 - ge->prev->fy3); + b = fabs(ge->fx1 - ge->prev->fx3); + if(a < FEPS) { + if(b < FEPS) { + return 0; + } else + k1 = FBIGVAL; + } else + k1 = b / a; + + a = fabs(ge->fy3 - ge->fy2); + b = fabs(ge->fx3 - ge->fx2); + if(a < FEPS) { + if(b < FEPS) { + return 0; + } else + k2 = FBIGVAL; + } else + k2 = b / a; + + /* if the curve is not a zigzag */ + if ((k1+0.0001 >= k && k2 <= k+0.0001) || (k1 <= k+0.0001 && k2+0.0001 >= k)) + return 0; + else + return 1; +} + +/* split the zigzag-like curves into two parts */ + +void +fsplitzigzags( + GLYPH * g +) +{ + GENTRY *ge, *nge; + double a, b, c, d; + + assertisfloat(g, "splitting zigzags"); + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type != GE_CURVE) + continue; + + /* if the curve is not a zigzag */ + if ( !fiszigzag(ge) ) { + continue; + } + + if(ISDBG(FCONCISE)) { + double maxsc1, maxsc2; + fprintf(stderr, "split a zigzag "); + fnormalizege(ge); + if( fcrossraysge(ge, ge, &maxsc1, &maxsc2, NULL) ) { + fprintf(stderr, "sc1=%g sc2=%g\n", maxsc1, maxsc2); + } else { + fprintf(stderr, "(rays don't cross)\n"); + } + } + /* split the curve by t=0.5 */ + nge = newgentry(GEF_FLOAT); + (*nge) = (*ge); + nge->type = GE_CURVE; + + a = ge->prev->fx3; + b = ge->fx1; + c = ge->fx2; + d = ge->fx3; + nge->fx3 = d; + nge->fx2 = (c + d) / 2.; + nge->fx1 = (b + 2. * c + d) / 4.; + ge->fx3 = (a + b * 3. + c * 3. + d) / 8.; + ge->fx2 = (a + 2. * b + c) / 4.; + ge->fx1 = (a + b) / 2.; + + a = ge->prev->fy3; + b = ge->fy1; + c = ge->fy2; + d = ge->fy3; + nge->fy3 = d; + nge->fy2 = (c + d) / 2.; + nge->fy1 = (b + 2. * c + d) / 4.; + ge->fy3 = (a + b * 3. + c * 3. + d) / 8.; + ge->fy2 = (a + 2. * b + c) / 4.; + ge->fy1 = (a + b) / 2.; + + addgeafter(ge, nge); + + if(ISDBG(FCONCISE)) { + dumppaths(g, ge, nge); + } + } +} + +/* free this GENTRY, returns what was ge->next + * (ge must be of type GE_LINE or GE_CURVE) + * works on both float and int entries + */ + +static GENTRY * +freethisge( + GENTRY *ge +) +{ + GENTRY *xge; + + if (ge->bkwd != ge->prev) { + /* at beginning of the contour */ + + xge = ge->bkwd; + if(xge == ge) { /* was the only line in contour */ + /* remove the contour completely */ + /* prev is GE_MOVE, next is GE_PATH, remove them all */ + + /* may be the first contour, then ->bkwd points to ge->entries */ + if(ge->prev->prev == 0) + *(GENTRY **)(ge->prev->bkwd) = ge->next->next; + else + ge->prev->prev->next = ge->next->next; + + if(ge->next->next) { + ge->next->next->prev = ge->prev->prev; + ge->next->next->bkwd = ge->prev->bkwd; + } + + xge = ge->next->next; + free(ge->prev); free(ge->next); free(ge); + return xge; + } + + /* move the start point of the contour */ + if(ge->flags & GEF_FLOAT) { + ge->prev->fx3 = xge->fx3; + ge->prev->fy3 = xge->fy3; + } else { + ge->prev->ix3 = xge->ix3; + ge->prev->iy3 = xge->iy3; + } + } else if(ge->frwd != ge->next) { + /* at end of the contour */ + + xge = ge->frwd->prev; + /* move the start point of the contour */ + if(ge->flags & GEF_FLOAT) { + xge->fx3 = ge->bkwd->fx3; + xge->fy3 = ge->bkwd->fy3; + } else { + xge->ix3 = ge->bkwd->ix3; + xge->iy3 = ge->bkwd->iy3; + } + } + + ge->prev->next = ge->next; + ge->next->prev = ge->prev; + ge->bkwd->frwd = ge->frwd; + ge->frwd->bkwd = ge->bkwd; + + xge = ge->next; + free(ge); + return xge; +} + +/* inserts a new gentry (LINE or CURVE) after another (MOVE + * or LINE or CURVE) + * corrects the first GE_MOVE if neccessary + */ + +static void +addgeafter( + GENTRY *oge, /* after this */ + GENTRY *nge /* insert this */ +) +{ + if(oge->type == GE_MOVE) { + /* insert before next */ + if(oge->next->type == GE_PATH) { + /* first and only GENTRY in path */ + nge->frwd = nge->bkwd = nge; + } else { + nge->frwd = oge->next; + nge->bkwd = oge->next->bkwd; + oge->next->bkwd->frwd = nge; + oge->next->bkwd = nge; + } + } else { + nge->frwd = oge->frwd; + nge->bkwd = oge; + oge->frwd->bkwd = nge; + oge->frwd = nge; + } + + nge->next = oge->next; + nge->prev = oge; + oge->next->prev = nge; + oge->next = nge; + + if(nge->frwd->prev->type == GE_MOVE) { + /* fix up the GE_MOVE entry */ + if(nge->flags & GEF_FLOAT) { + nge->frwd->prev->fx3 = nge->fx3; + nge->frwd->prev->fy3 = nge->fy3; + } else { + nge->frwd->prev->ix3 = nge->ix3; + nge->frwd->prev->iy3 = nge->iy3; + } + } +} + +/* + * Check if this GENTRY happens to be at the end of path + * and fix the first MOVETO accordingly + * handles both int and float + */ + +static void +fixendpath( + GENTRY *ge +) +{ + GENTRY *mge; + + mge = ge->frwd->prev; + if(mge->type == GE_MOVE) { + if(ge->flags & GEF_FLOAT) { + mge->fx3 = ge->fx3; + mge->fy3 = ge->fy3; + } else { + mge->ix3 = ge->ix3; + mge->iy3 = ge->iy3; + } + } +} + +/* + * This function adjusts the rest of path (the part from...to is NOT changed) + * to cover the specified gap by the specified axis (0 - X, 1 - Y). + * Gap is counted in direction (end_of_to - beginning_of_from). + * Returns by how much the gap was not closed (0.0 if it was fully closed). + * Ret contains by how much the first and last points of [from...to] + * were moved to bring them in consistence to the rest of the path. + * If ret==NULL then this info is not returned. + */ + +static double +fclosegap( + GENTRY *from, + GENTRY *to, + int axis, + double gap, + double *ret +) +{ +#define TIMESLARGER 10. /* how many times larger must be a curve to not change too much */ + double rm[2]; + double oldpos[2]; + double times, limit, df, dx; + int j, k; + GENTRY *xge, *pge, *nge, *bge[2]; + + /* remember the old points to calculate ret */ + oldpos[0] = from->prev->fpoints[axis][2]; + oldpos[1] = to->fpoints[axis][2]; + + rm[0] = rm[1] = gap / 2. ; + + bge[0] = from; /* this is convenient for iterations */ + bge[1] = to; + + /* first try to modify large curves but if have none then settle for small */ + for(times = (TIMESLARGER-1); times > 0.1; times /= 2. ) { + + if(rm[0]+rm[1] == 0.) + break; + + /* iterate in both directions, backwards then forwards */ + for(j = 0; j<2; j++) { + + if(rm[j] == 0.) /* if this direction is exhausted */ + continue; + + limit = fabs(rm[j]) * (1.+times); + + for(xge = bge[j]->cntr[j]; xge != bge[!j]; xge = xge->cntr[j]) { + dx = xge->fpoints[axis][2] - xge->prev->fpoints[axis][2]; + df = fabs(dx) - limit; + if( df <= FEPS ) /* curve is too small to change */ + continue; + + if( df >= fabs(rm[j]) ) + df = rm[j]; + else + df *= fsign(rm[j]); /* we may cover this part of rm */ + + rm[j] -= df; + limit = fabs(rm[j]) * (1.+times); + + if(xge->type == GE_CURVE) { /* correct internal points */ + double scale = ((dx+df) / dx) - 1.; + double base; + + if(j) + base = xge->fpoints[axis][2]; + else + base = xge->prev->fpoints[axis][2]; + + for(k = 0; k<2; k++) + xge->fpoints[axis][k] += scale * + (xge->fpoints[axis][k] - base); + } + + /* move all the intermediate lines */ + if(j) { + df = -df; /* absolute direction */ + pge = bge[1]->bkwd; + nge = xge->bkwd; + } else { + xge->fpoints[axis][2] += df; + pge = bge[0]; + nge = xge->frwd; + } + while(nge != pge) { + if(nge->type == GE_CURVE) { + nge->fpoints[axis][0] +=df; + nge->fpoints[axis][1] +=df; + } + nge->fpoints[axis][2] += df; + if(nge->next != nge->frwd) { /* last entry of contour */ + nge->frwd->prev->fpoints[axis][2] += df; + } + nge = nge->cntr[!j]; + } + + if(rm[j] == 0.) + break; + } + } + } + + /* find the difference */ + oldpos[0] -= from->prev->fpoints[axis][2]; + oldpos[1] -= to->fpoints[axis][2]; + + if(ret) { + ret[0] = oldpos[0] - from->prev->fpoints[axis][2]; + ret[1] = oldpos[1] - to->fpoints[axis][2]; + } + +#if 0 + if( rm[0]+rm[1] != gap - oldpos[1] + oldpos[0]) { + fprintf(stderr, "** gap=%g rm[0]=%g rm[1]=%g o[0]=%g o[1]=%g rg=%g og=%g\n", + gap, rm[0], rm[1], oldpos[0], oldpos[1], rm[0]+rm[1], + gap - oldpos[1] + oldpos[0]); + } +#endif + + return rm[0]+rm[1]; +#undef TIMESLARGER +} + +/* remove the lines or curves smaller or equal to the size limit */ + +static void +fdelsmall( + GLYPH *g, + double minlen +) +{ + GENTRY *ge, *nge, *pge, *xge, *next; + int i, k; + double dx, dy, d2, d2m; + double minlen2; +#define TIMESLARGER 10. /* how much larger must be a curve to not change too much */ + + minlen2 = minlen*minlen; + + for (ge = g->entries; ge != 0; ge = next) { + next = ge->next; + + if (ge->type != GE_CURVE && ge->type != GE_LINE) + continue; + + d2m = 0; + for(i= (ge->type==GE_CURVE? 0: 2); i<3; i++) { + dx = ge->fxn[i] - ge->prev->fx3; + dy = ge->fyn[i] - ge->prev->fy3; + d2 = dx*dx + dy*dy; + if(d2m < d2) + d2m = d2; + } + + if( d2m > minlen2 ) { /* line is not too small */ + /* XXX add more normalization here */ + continue; + } + + /* if the line is too small */ + + /* check forwards if we have a whole sequence of them */ + nge = ge; + for(xge = ge->frwd; xge != ge; xge = xge->frwd) { + d2m = 0; + for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) { + dx = xge->fxn[i] - xge->prev->fx3; + dy = xge->fyn[i] - xge->prev->fy3; + d2 = dx*dx + dy*dy; + if(d2m < d2) + d2m = d2; + } + if( d2m > minlen2 ) /* line is not too small */ + break; + nge = xge; + if(next == nge) /* move the next step past this sequence */ + next = next->next; + } + + /* check backwards if we have a whole sequence of them */ + pge = ge; + for(xge = ge->bkwd; xge != ge; xge = xge->bkwd) { + d2m = 0; + for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) { + dx = xge->fxn[i] - xge->prev->fx3; + dy = xge->fyn[i] - xge->prev->fy3; + d2 = dx*dx + dy*dy; + if(d2m < d2) + d2m = d2; + } + if( d2m > minlen2 ) /* line is not too small */ + break; + pge = xge; + } + + /* now we have a sequence of small fragments in pge...nge (inclusive) */ + + if(ISDBG(FCONCISE)) { + fprintf(stderr, "glyph %s has very small fragments(%x..%x..%x)\n", + g->name, pge, ge, nge); + dumppaths(g, pge, nge); + } + + /* reduce whole sequence to one part and remember the middle point */ + if(pge != nge) { + while(1) { + xge = pge->frwd; + if(xge == nge) { + pge->fx1 = pge->fx2 = pge->fx3; + pge->fx3 = nge->fx3; + pge->fy1 = pge->fy2 = pge->fy3; + pge->fy3 = nge->fy3; + pge->type = GE_CURVE; + freethisge(nge); + break; + } + if(xge == nge->bkwd) { + pge->fx1 = pge->fx2 = (pge->fx3+xge->fx3)/2.; + pge->fx3 = nge->fx3; + pge->fy1 = pge->fy2 = (pge->fy3+xge->fy3)/2.; + pge->fy3 = nge->fy3; + pge->type = GE_CURVE; + freethisge(nge); + freethisge(xge); + break; + } + freethisge(pge); pge = xge; + xge = nge->bkwd; freethisge(nge); nge = xge; + } + } + ge = pge; + + /* check if the whole sequence is small */ + dx = ge->fx3 - ge->prev->fx3; + dy = ge->fy3 - ge->prev->fy3; + d2 = dx*dx + dy*dy; + + if( d2 > minlen2 ) { /* no, it is not */ + double b, d; + + WARNING_3 fprintf(stderr, "glyph %s had a sequence of fragments < %g points each, reduced to one curve\n", + g->name, minlen); + + /* check that we did not create a monstrosity spanning quadrants */ + if(fsign(ge->fx1 - ge->prev->fx1) * fsign(ge->fx3 - ge->fx1) < 0 + || fsign(ge->fy1 - ge->prev->fy1) * fsign(ge->fy3 - ge->fy1) < 0 ) { + /* yes, we did; are both parts of this thing big enough ? */ + dx = ge->fx1 - ge->prev->fx3; + dy = ge->fy1 - ge->prev->fy3; + d2 = dx*dx + dy*dy; + + dx = ge->fx3 - ge->fx1; + dy = ge->fy3 - ge->fy1; + d2m = dx*dx + dy*dy; + + if(d2 > minlen2 && d2m > minlen2) { /* make two straights */ + nge = newgentry(GEF_FLOAT); + *nge = *ge; + + for(i=0; i<2; i++) { + ge->fpoints[i][2] = ge->fpoints[i][0]; + b = nge->fpoints[i][0]; + d = nge->fpoints[i][2] - b; + nge->fpoints[i][0] = b + 0.1*d; + nge->fpoints[i][1] = b + 0.9*d; + } + } + for(i=0; i<2; i++) { /* make one straight or first of two straights */ + b = ge->prev->fpoints[i][2]; + d = ge->fpoints[i][2] - b; + ge->fpoints[i][0] = b + 0.1*d; + ge->fpoints[i][1] = b + 0.9*d; + } + } + continue; + } + + if(ge->frwd == ge) { /* points to itself, just remove the path completely */ + WARNING_3 fprintf(stderr, "glyph %s had a path made of fragments < %g points each, removed\n", + g->name, minlen); + + next = freethisge(ge); + continue; + } + + /* now close the gap by x and y */ + for(i=0; i<2; i++) { + double gap; + + gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2]; + if( fclosegap(ge, ge, i, gap, NULL) != 0.0 ) { + double scale, base; + + /* not good, as the last resort just scale the next line */ + gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2]; + + if(ISDBG(FCONCISE)) + fprintf(stderr, " last resort on %c: closing next by %g\n", + (i==0 ? 'x' : 'y'), gap); + + nge = ge->frwd; + base = nge->fpoints[i][2]; + dx = ge->fpoints[i][2] - base; + if(fabs(dx) < FEPS) + continue; + + scale = ((dx-gap) / dx); + + if(nge->type == GE_CURVE) + for(k = 0; k<2; k++) + nge->fpoints[i][k] = base + + scale * (nge->fpoints[i][k] - base); + + ge->fpoints[i][2] -= gap; + } + } + + /* OK, the gap is closed - remove this useless GENTRY */ + freethisge(ge); + } +#undef TIMESLARGER +} + +/* find the point where two rays continuing vectors cross + * returns 1 if they cross, 0 if they don't + * If they cross optionally (if the pointers are not NULL) returns + * the maximal scales for both vectors and also optionally the point + * where the rays cross (twice). + * Expects that the curves are normalized. + * + * For convenience there are 2 front-end functions taking + * arguments in different formats + */ + +struct ray { + double x1, y1, x2, y2; + int isvert; + double k, b; /* lines are represented as y = k*x + b */ + double *maxp; +}; +static struct ray ray[3]; + +/* the back-end doing the actual work + * the rays are defined in the static array ray[] + */ + +static int +fcrossraysxx( + double crossdot[2][2] +) +{ + double x, y, max; + int i; + + for(i=0; i<2; i++) { + if(ray[i].x1 == ray[i].x2) + ray[i].isvert = 1; + else { + ray[i].isvert = 0; + ray[i].k = (ray[i].y2 - ray[i].y1) / (ray[i].x2 - ray[i].x1); + ray[i].b = ray[i].y2 - ray[i].k * ray[i].x2; + } + } + + if(ray[0].isvert && ray[1].isvert) { + if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: both vertical\n"); + return 0; /* both vertical, don't cross */ + } + + if(ray[1].isvert) { + ray[2] = ray[0]; /* exchange them */ + ray[0] = ray[1]; + ray[1] = ray[2]; + } + + if(ray[0].isvert) { + x = ray[0].x1; + } else { + if( fabs(ray[0].k - ray[1].k) < FEPS) { + if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: parallel lines, k = %g, %g\n", + ray[0].k, ray[1].k); + return 0; /* parallel lines */ + } + x = (ray[1].b - ray[0].b) / (ray[0].k - ray[1].k) ; + } + y = ray[1].k * x + ray[1].b; + + for(i=0; i<2; i++) { + if(ray[i].isvert) + max = (y - ray[i].y1) / (ray[i].y2 - ray[i].y1); + else + max = (x - ray[i].x1) / (ray[i].x2 - ray[i].x1); + /* check if wrong sides of rays cross */ + if( max < 0 ) { + if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: %c scale=%g @(%g,%g) (%g,%g)<-(%g,%g)\n", + (i?'Y':'X'), max, x, y, ray[i].x2, ray[i].y2, ray[i].x1, ray[i].y1); + return 0; + } + if(ray[i].maxp) + *ray[i].maxp = max; + } + if(crossdot != 0) { + crossdot[0][0] = crossdot[1][0] = x; + crossdot[0][1] = crossdot[1][1] = y; + } + return 1; +} + +/* the front-end getting the arguments from 4 dots defining + * a curve in the same format as for fapproxcurve(): + * rays are defined as beginning and end of the curve, + * the crossdot is inserted as the two middle dots of the curve + */ + +int +fcrossrayscv( + double curve[4][2 /*X,Y*/], + double *max1, + double *max2 +) +{ + ray[0].x1 = curve[0][X]; + ray[0].y1 = curve[0][Y]; + ray[0].x2 = curve[1][X]; + ray[0].y2 = curve[1][Y]; + ray[0].maxp = max1; + + ray[1].x1 = curve[2][X]; + ray[1].y1 = curve[2][Y]; + ray[1].x2 = curve[3][X]; + ray[1].y2 = curve[3][Y]; + ray[1].maxp = max2; + + return fcrossraysxx(&curve[1]); +} + +/* the front-end getting the arguments from gentries: + * rays are defined as beginning of curve1 and end of curve 2 + */ + +int +fcrossraysge( + GENTRY *ge1, + GENTRY *ge2, + double *max1, + double *max2, + double crossdot[2][2] +) +{ + ray[0].x1 = ge1->prev->fx3; + ray[0].y1 = ge1->prev->fy3; + ray[0].x2 = ge1->fpoints[X][ge1->ftg]; + ray[0].y2 = ge1->fpoints[Y][ge1->ftg]; + ray[0].maxp = max1; + + ray[1].x1 = ge2->fx3; + ray[1].y1 = ge2->fy3; + if(ge2->rtg < 0) { + ray[1].x2 = ge2->prev->fx3; + ray[1].y2 = ge2->prev->fy3; + } else { + ray[1].x2 = ge2->fpoints[X][ge2->rtg]; + ray[1].y2 = ge2->fpoints[Y][ge2->rtg]; + } + ray[1].maxp = max2; + + return fcrossraysxx(crossdot); +} + +/* debugging printout functions */ + +#if defined(DEBUG_DOTSEG) || defined(DEBUG_DOTCURVE) || defined(DEBUG_APPROXCV) + +/* for debugging */ +static +printdot( + double dot[2] +) +{ + fprintf(stderr, "(%g,%g)", dot[0], dot[1]); +} + +static +printseg( + double seg[2][2] +) +{ + putc('[', stderr); + printdot(seg[0]); + putc(' ', stderr); + printdot(seg[1]); + putc(']', stderr); +} + +#endif /* DEBUG_* */ + +/* + * Find squared distance from a dot to a line segment + */ + +double +fdotsegdist2( + double seg[2][2 /*X,Y*/], + double dot[2 /*X,Y*/] +) +{ +#define x1 seg[0][X] +#define y1 seg[0][Y] +#define x2 seg[1][X] +#define y2 seg[1][Y] +#define xdot dot[X] +#define ydot dot[Y] + + double dx, dy; /* segment dimensions */ + double kline, bline; /* segment line formula is y=k*x+b */ + double kperp, bperp; /* perpendicular from the dot to the line */ + double xcross, ycross; /* where the perpendicular crosses the segment */ + +/* handle the situation where the nearest point of the segment is its end */ +#define HANDLE_LIMITS(less12, lesscr1, lesscr2) \ + if( less12 ) { \ + if( lesscr1 ) { \ + xcross = x1; \ + ycross = y1; \ + } else if( !(lesscr2) ) { \ + xcross = x2; \ + ycross = y2; \ + } \ + } else { \ + if( !(lesscr1) ) { \ + xcross = x1; \ + ycross = y1; \ + } else if( lesscr2 ) { \ + xcross = x2; \ + ycross = y2; \ + } \ + } \ + /* end of macro */ + + + dx = x2 - x1; + dy = y2 - y1; + + if(fabs(dx) < FEPS) { + /* special case - vertical line */ +#ifdef DEBUG_DOTSEG + printf("vertical line!\n"); +#endif + xcross = x1; + ycross = ydot; + HANDLE_LIMITS( y1 < y2, ycross < y1, ycross < y2); + } else if(fabs(dy) < FEPS) { + /* special case - horizontal line */ +#ifdef DEBUG_DOTSEG + printf("horizontal line!\n"); +#endif + xcross = xdot; + ycross = y1; + HANDLE_LIMITS( x1 < x2, xcross < x1, xcross < x2) + } else { + kline = dy/dx; + bline = y1 - x1*kline; + kperp = -1./kline; + bperp = ydot - xdot*kperp; + + xcross = (bline-bperp) / (kperp-kline); + ycross = kline*xcross + bline; + + HANDLE_LIMITS( x1 < x2, xcross < x1, xcross < x2) + } +#ifdef DEBUG_DOTSEG + printf("crossover at (%g,%g)\n", xcross, ycross); +#endif + + dx = xdot-xcross; + dy = ydot-ycross; + return dx*dx+dy*dy; +#undef x1 +#undef y1 +#undef x2 +#undef y2 +#undef xdot +#undef ydot +#undef HANDLE_LIMITS +} + +/* find the weighted quadratic average for the distance of a set + * of dots from the curve; also fills out the individual distances + * for each dot; if maxp!=NULL then returns the maximal squared + * distance in there + */ + +double +fdotcurvdist2( + double curve[4][2 /*X,Y*/ ], + struct dot_dist *dots, + int ndots, /* number of entries in dots */ + double *maxp +) +{ + /* a curve is approximated by this many straight segments */ +#define NAPSECT 16 + /* a curve is divided into this many sections with equal weight each */ +#define NWSECT 4 + /* table of coefficients for finding the dots on the curve */ + /* tt[0] is left unused */ + static double tt[NAPSECT][4]; + static int havett = 0; /* flag: tt is initialized */ + /* dots on the curve */ + double cvd[NAPSECT+1][2 /*X,Y*/]; + /* sums by sections */ + double sum[NWSECT]; + /* counts by sections */ + double count[NWSECT]; + int d, i, j; + int id1, id2; + double dist1, dist2, dist3, dx, dy, x, y; + double max = 0.; + + if(!havett) { + double t, nt, t2, nt2, step; + + havett++; + step = 1. / NAPSECT; + t = 0; + for(i=1; i<NAPSECT; i++) { + t += step; + nt = 1 - t; + t2 = t*t; + nt2 = nt*nt; + tt[i][0] = nt2*nt; /* (1-t)^3 */ + tt[i][1] = 3*nt2*t; /* 3*(1-t)^2*t */ + tt[i][2] = 3*nt*t2; /* 3*(1-t)*t^2 */ + tt[i][3] = t2*t; /* t^3 */ + } + } + + for(i=0; i<NWSECT; i++) { + sum[i] = 0.; + count[i] = 0; + } + + /* split the curve into segments */ + for(d=0; d<2; d++) { /* X and Y */ + cvd[0][d] = curve[0][d]; /* endpoints */ + cvd[NAPSECT][d] = curve[3][d]; + for(i=1; i<NAPSECT; i++) { + cvd[i][d] = curve[0][d] * tt[i][0] + + curve[1][d] * tt[i][1] + + curve[2][d] * tt[i][2] + + curve[3][d] * tt[i][3]; + } + } + + for(d=0; d<ndots; d++) { +#ifdef DEBUG_DOTCURVE + printf("dot %d ", d); printdot(dots[d].p); printf(":\n"); + + /* for debugging */ + for(i=0; i< NAPSECT; i++) { + dist1 = fdotsegdist2(&cvd[i], dots[d].p); + printf(" seg %d ",i); printseg(&cvd[i]); printf(" dist=%g\n", sqrt(dist1)); + } +#endif + + x = dots[d].p[X]; + y = dots[d].p[Y]; + + /* find the nearest dot on the curve + * there may be up to 2 local minimums - so we start from the + * ends of curve and go to the center + */ + + id1 = 0; + dx = x - cvd[0][X]; + dy = y - cvd[0][Y]; + dist1 = dx*dx + dy*dy; +#ifdef DEBUG_DOTCURVE + printf(" dot 0 "); printdot(cvd[id1]); printf(" dist=%g\n", sqrt(dist1)); +#endif + for(i = 1; i<=NAPSECT; i++) { + dx = x - cvd[i][X]; + dy = y - cvd[i][Y]; + dist3 = dx*dx + dy*dy; +#ifdef DEBUG_DOTCURVE + printf(" dot %d ",i); printdot(cvd[i]); printf(" dist=%g\n", sqrt(dist3)); +#endif + if(dist3 < dist1) { + dist1 = dist3; + id1 = i; + } else + break; + } + + if(id1 < NAPSECT-1) { + id2 = NAPSECT; + dx = x - cvd[NAPSECT][X]; + dy = y - cvd[NAPSECT][Y]; + dist2 = dx*dx + dy*dy; +#ifdef DEBUG_DOTCURVE + printf(" +dot %d ", id2); printdot(cvd[id2]); printf(" dist=%g\n", sqrt(dist2)); +#endif + for(i = NAPSECT-1; i>id1+1; i--) { + dx = x - cvd[i][X]; + dy = y - cvd[i][Y]; + dist3 = dx*dx + dy*dy; +#ifdef DEBUG_DOTCURVE + printf(" dot %d ",i); printdot(cvd[i]); printf(" dist=%g\n", sqrt(dist3)); +#endif + if(dist3 < dist2) { + dist2 = dist3; + id2 = i; + } else + break; + } + + /* now find which of the local minimums is smaller */ + if(dist2 < dist1) { + id1 = id2; + } + } + + /* the nearest segment must include the nearest dot */ + if(id1==0) { + dots[d].seg = 0; + dots[d].dist2 = fdotsegdist2(&cvd[0], dots[d].p); + } else if(id1==NAPSECT) { + dots[d].seg = NAPSECT-1; + dots[d].dist2 = fdotsegdist2(&cvd[NAPSECT-1], dots[d].p); + } else { + dist1 = fdotsegdist2(&cvd[id1], dots[d].p); + dist2 = fdotsegdist2(&cvd[id1-1], dots[d].p); + if(dist2 < dist1) { + dots[d].seg = id1-1; + dots[d].dist2 = dist2; + } else { + dots[d].seg = id1; + dots[d].dist2 = dist1; + } + } + + i = dots[d].seg % NWSECT; + sum[i] += dots[d].dist2; + if(dots[d].dist2 > max) + max = dots[d].dist2; + count[i]++; +#ifdef DEBUG_DOTCURVE + printf(" best seg %d sect %d dist=%g\n", dots[d].seg, i, sqrt(dots[d].dist2)); +#endif + } + + /* calculate the weighted average */ + id1=0; + dist1=0.; + for(i=0; i<NWSECT; i++) { + if(count[i]==0) + continue; + id1++; + dist1 += sum[i]/count[i]; + } + if(maxp) + *maxp = max; + if(id1==0) /* no dots, strange */ + return 0.; + else + return dist1/id1; /* to get the average distance apply sqrt() */ +} + +/* + * Approximate a curve matching the giving set of points and with + * middle reference points going along the given segments (and no farther + * than these segments). + */ + +void +fapproxcurve( + double cv[4][2 /*X,Y*/ ], /* points 0-3 are passed in, points 1,2 - out */ + struct dot_dist *dots, /* the dots to approximate - distances returned + * there may be invalid */ + int ndots +) +{ + /* b and c are the middle control points */ +#define B 0 +#define C 1 + /* maximal number of sections on each axis - used for the first step */ +#define MAXSECT 2 + /* number of sections used for the other steps */ +#define NORMSECT 2 + /* when the steps become less than this many points, it's time to stop */ +#define STEPEPS 1. + double from[2 /*B,C*/], to[2 /*B,C*/]; + double middf[2 /*B,C*/][2 /*X,Y*/], df; + double coef[2 /*B,C*/][MAXSECT]; + double res[MAXSECT][MAXSECT], thisres, bestres, goodres; + int ncoef[2 /*B,C*/], best[2 /*B,C*/], good[2 /*B,C*/]; + int i, j, k, keepsym; + char bc[]="BC"; + char xy[]="XY"; + +#ifdef DEBUG_APPROXCV + fprintf(stderr, "Curve points:"); + for(i=0; i<4; i++) { + fprintf(stderr, " "); + printdot(cv[i]); + } + fprintf(stderr, "\nDots:"); + for(i=0; i<ndots; i++) { + fprintf(stderr, " "); + printdot(dots[i].p); + } + fprintf(stderr, "\n"); +#endif + + /* load the endpoints and calculate differences */ + for(i=0; i<2; i++) { + /* i is X, Y */ + middf[B][i] = cv[1][i]-cv[0][i]; + middf[C][i] = cv[2][i]-cv[3][i]; + + /* i is B, C */ + from[i] = 0.; + to[i] = 1.; + ncoef[i] = MAXSECT; + } + + while(ncoef[B] != 1 || ncoef[C] != 1) { + /* prepare the values of coefficients */ + for(i=0; i<2; i++) { /*B,C*/ +#ifdef DEBUG_APPROXCV + fprintf(stderr, "Coefficients by %c(%g,%g):", bc[i], from[i], to[i]); +#endif + df = (to[i]-from[i]) / (ncoef[i]*2); + for(j=0; j<ncoef[i]; j++) { + coef[i][j] = from[i] + df*(2*j+1); +#ifdef DEBUG_APPROXCV + fprintf(stderr, " %g", coef[i][j]); +#endif + } +#ifdef DEBUG_APPROXCV + fprintf(stderr, "\n"); +#endif + } + bestres = FBIGVAL; + /* i iterates by ncoef[B], j iterates by ncoef[C] */ + for(i=0; i<ncoef[B]; i++) { + for(j=0; j<ncoef[C]; j++) { + for(k=0; k<2; k++) { /*X, Y*/ + cv[1][k] = cv[0][k] + middf[B][k]*coef[B][i]; + cv[2][k] = cv[3][k] + middf[C][k]*coef[C][j]; + } + res[i][j] = thisres = fdotcurvdist2(cv, dots, ndots, NULL); + if(thisres < bestres) { + goodres = bestres; + good[B] = best[B]; + good[C] = best[C]; + bestres = thisres; + best[B] = i; + best[C] = j; + } else if(thisres < goodres) { + goodres = thisres; + good[B] = i; + good[C] = j; + } +#ifdef DEBUG_APPROXCV + fprintf(stderr, " at (%g,%g) dist=%g %s\n", coef[B][i], coef[C][j], sqrt(thisres), + (best[B]==i && best[C]==j)? "(BEST)":""); +#endif + } + } +#ifdef DEBUG_APPROXCV + fprintf(stderr, " best: at (%g, %g) dist=%g\n", + coef[B][best[B]], coef[C][best[C]], sqrt(bestres)); + fprintf(stderr, " B:%d,%d C:%d,%d -- 2nd best: at (%g, %g) dist=%g\n", + best[B], good[B], best[C], good[C], coef[B][good[B]], coef[C][good[C]], sqrt(goodres)); +#endif + + if(bestres < (0.1*0.1)) { /* consider it close enough */ + /* calculate the coordinates to return */ + for(k=0; k<2; k++) { /*X, Y*/ + cv[1][k] = cv[0][k] + middf[B][k]*coef[B][best[B]]; + cv[2][k] = cv[3][k] + middf[C][k]*coef[C][best[C]]; + } +#ifdef DEBUG_APPROXCV + fprintf(stderr, "quick approximated middle points "); printdot(cv[1]); + fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n"); +#endif + return; + } + keepsym = 0; + if(best[B] != best[C] && best[B]-best[C] == good[C]-good[B]) { + keepsym = 1; +#ifdef DEBUG_APPROXCV + fprintf(stderr, "keeping symmetry!\n"); +#endif + } + for(i=0; i<2; i++) { /*B,C*/ + if(ncoef[i]==1) + continue; + if(keepsym) { + /* try to keep the symmetry */ + if(best[i] < good[i]) { + from[i] = coef[i][best[i]]; + to[i] = coef[i][good[i]]; + } else { + from[i] = coef[i][good[i]]; + to[i] = coef[i][best[i]]; + } + } else { + df = (to[i]-from[i]) / ncoef[i]; + from[i] += df*best[i]; + to[i] = from[i] + df; + } + if( fabs(df*middf[i][0]) < STEPEPS && fabs(df*middf[i][1]) < STEPEPS) { + /* this side has converged */ + from[i] = to[i] = (from[i]+to[i]) / 2.; + ncoef[i] = 1; + } else + ncoef[i] = NORMSECT; + } + + } + /* calculate the coordinates to return */ + for(k=0; k<2; k++) { /*X, Y*/ + cv[1][k] = cv[0][k] + middf[B][k]*from[B]; + cv[2][k] = cv[3][k] + middf[C][k]*from[C]; + } +#ifdef DEBUG_APPROXCV + fprintf(stderr, "approximated middle points "); printdot(cv[1]); + fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n"); +#endif +#undef B +#undef C +#undef MAXSECT +#undef NORMSECT +#undef STEPEPS +} + +/* + * Find the squared value of the sinus of the angle between the + * end of ge1 and the beginning of ge2 + * The curve must be normalized. + */ + +static double +fjointsin2( + GENTRY *ge1, + GENTRY *ge2 +) +{ + double d[3][2 /*X,Y*/]; + double scale1, scale2, len1, len2; + int axis; + + if(ge1->rtg < 0) { + d[1][X] = ge1->fx3 - ge1->prev->fx3; + d[1][Y] = ge1->fy3 - ge1->prev->fy3; + } else { + d[1][X] = ge1->fx3 - ge1->fpoints[X][ge1->rtg]; + d[1][Y] = ge1->fy3 - ge1->fpoints[Y][ge1->rtg]; + } + d[2][X] = ge2->fpoints[X][ge2->ftg] - ge2->prev->fx3; + d[2][Y] = ge2->fpoints[Y][ge2->ftg] - ge2->prev->fy3; + + len1 = sqrt( d[1][X]*d[1][X] + d[1][Y]*d[1][Y] ); + len2 = sqrt( d[2][X]*d[2][X] + d[2][Y]*d[2][Y] ); + /* scale the 2nd segment to the length of 1 + * and to make sure that the 1st segment is longer scale it to + * the length of 2 and extend to the same distance backwards + */ + scale1 = 2./len1; + scale2 = 1./len2; + + for(axis=0; axis <2; axis++) { + d[0][axis] = -( d[1][axis] *= scale1 ); + d[2][axis] *= scale2; + } + return fdotsegdist2(d, d[2]); +} + +#if 0 +/* find the area covered by the curve + * (limited by the projections to the X axis) + */ + +static double +fcvarea( + GENTRY *ge +) +{ + double Ly, My, Ny, Py, Qx, Rx, Sx; + double area; + + /* y = Ly*t^3 + My*t^2 + Ny*t + Py */ + Ly = -ge->prev->fy3 + 3*(ge->fy1 - ge->fy2) + ge->fy3; + My = 3*ge->prev->fy3 - 6*ge->fy1 + 3*ge->fy2; + Ny = 3*(-ge->prev->fy3 + ge->fy1); + Py = ge->prev->fy3; + + /* dx/dt = Qx*t^2 + Rx*t + Sx */ + Qx = 3*(-ge->prev->fx3 + 3*(ge->fx1 - ge->fx2) + ge->fx3); + Rx = 6*(ge->prev->fx3 - 2*ge->fx1 + ge->fx2); + Sx = 3*(-ge->prev->fx3 + ge->fx1); + + /* area is integral[from 0 to 1]( y(t) * dx(t)/dt *dt) */ + area = 1./6.*(Ly*Qx) + 1./5.*(Ly*Rx + My*Qx) + + 1./4.*(Ly*Sx + My*Rx + Ny*Qx) + 1./3.*(My*Sx + Ny*Rx + Py*Qx) + + 1./2.*(Ny*Sx + Py*Rx) + Py*Sx; + + return area; +} +#endif + +/* find the value of point on the curve at the given parameter t, + * along the given axis (0 - X, 1 - Y). + */ + +static double +fcvval( + GENTRY *ge, + int axis, + double t +) +{ + double t2, mt, mt2; + + /* val = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 */ + t2 = t*t; + mt = 1-t; + mt2 = mt*mt; + + return ge->prev->fpoints[axis][2]*mt2*mt + + 3*(ge->fpoints[axis][0]*mt2*t + ge->fpoints[axis][1]*mt*t2) + + ge->fpoints[axis][2]*t*t2; +} + +/* + * Find ndots equally spaced dots on a curve or line and fill + * their coordinates into the dots array + */ + +static void +fsampledots( + GENTRY *ge, + double dots[][2], /* the dots to fill */ + int ndots +) +{ + int i, axis; + double t, nf, dx, d[2]; + + nf = ndots+1; + if(ge->type == GE_CURVE) { + for(i=0; i<ndots; i++) { + t = (i+1)/nf; + for(axis=0; axis<2; axis++) + dots[i][axis] = fcvval(ge, axis, t); + } + } else { /* line */ + d[0] = ge->fx3 - ge->prev->fx3; + d[1] = ge->fy3 - ge->prev->fy3; + for(i=0; i<ndots; i++) { + t = (i+1)/nf; + for(axis=0; axis<2; axis++) + dots[i][axis] = ge->prev->fpoints[axis][2] + + t*d[axis]; + } + } +} + +/* + * Allocate a structure gex_con + */ + +static void +alloc_gex_con( + GENTRY *ge +) +{ + ge->ext = (void*)calloc(1, sizeof(GEX_CON)); + if(ge->ext == 0) { + fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); + exit(255); + } +} + +/* + * Normalize a gentry for fforceconcise() : find the points that + * can be used to calculate the tangents. + */ + +static void +fnormalizege( + GENTRY *ge +) +{ + int midsame, frontsame, rearsame; + + if(ge->type == GE_LINE) { + ge->ftg = 2; + ge->rtg = -1; + } else { /* assume it's a curve */ + midsame = (fabs(ge->fx1-ge->fx2)<FEPS && fabs(ge->fy1-ge->fy2)<FEPS); + frontsame = (fabs(ge->fx1-ge->prev->fx3)<FEPS && fabs(ge->fy1-ge->prev->fy3)<FEPS); + rearsame = (fabs(ge->fx3-ge->fx2)<FEPS && fabs(ge->fy3-ge->fy2)<FEPS); + + if(midsame && (frontsame || rearsame) ) { + /* essentially a line */ + ge->ftg = 2; + ge->rtg = -1; + } else { + if(frontsame) { + ge->ftg = 1; + } else { + ge->ftg = 0; + } + if(rearsame) { + ge->rtg = 0; + } else { + ge->rtg = 1; + } + } + } +} + +/* various definition for the processing of outlines */ + +/* maximal average quadratic distance from the original curve + * (in dots) to consider the joined curve good + */ +#define CVEPS 1.5 +#define CVEPS2 (CVEPS*CVEPS) +/* squared sinus of the maximal angle that we consider a smooth joint */ +#define SMOOTHSIN2 0.25 /* 0.25==sin(30 degrees)^2 */ +/* squared line length that we consider small */ +#define SMALL_LINE2 (15.*15.) +/* how many times a curve must be bigger than a line to join, squared */ +#define TIMES_LINE2 (3.*3.) + +/* + * Normalize and analyse a gentry for fforceconcise() and fill out the gex_con + * structure + */ + +static void +fanalyzege( + GENTRY *ge +) +{ + int i, ix, iy; + double avsd2, dots[3][2 /*X,Y*/]; + GEX_CON *gex; + + gex = X_CON(ge); + memset(gex, 0, sizeof *gex); + + gex->len2 = 0; + for(i=0; i<2; i++) { + avsd2 = gex->d[i] = ge->fpoints[i][2] - ge->prev->fpoints[i][2]; + gex->len2 += avsd2*avsd2; + } + gex->sin2 = fjointsin2(ge, ge->frwd); + if(ge->type == GE_CURVE) { + ge->dir = fgetcvdir(ge); + for(i=0; i<2; i++) { + dots[0][i] = ge->prev->fpoints[i][2]; + dots[1][i] = ge->fpoints[i][2]; + dots[2][i] = fcvval(ge, i, 0.5); + } + avsd2 = fdotsegdist2(dots, dots[2]); + if(avsd2 <= CVEPS2) { + gex->flags |= GEXF_FLAT; + } + } else { + ge->dir = CVDIR_FEQUAL|CVDIR_REQUAL; + gex->flags |= GEXF_FLAT; + } + if(gex->flags & GEXF_FLAT) { + if( fabs(gex->d[X]) > FEPS && fabs(gex->d[Y]) < 5. + && fabs(gex->d[Y] / gex->d[X]) < 0.2) + gex->flags |= GEXF_HOR; + else if( fabs(gex->d[Y]) > FEPS && fabs(gex->d[X]) < 5. + && fabs(gex->d[X] / gex->d[Y]) < 0.2) + gex->flags |= GEXF_VERT; + } + ix = gex->isd[X] = fsign(gex->d[X]); + iy = gex->isd[Y] = fsign(gex->d[Y]); + if(ix <= 0) { + if(iy <= 0) + gex->flags |= GEXF_QDL; + if(iy >= 0) + gex->flags |= GEXF_QUL; + if(gex->flags & GEXF_HOR) + gex->flags |= GEXF_IDQ_L; + } + if(ix >= 0) { + if(iy <= 0) + gex->flags |= GEXF_QDR; + if(iy >= 0) + gex->flags |= GEXF_QUR; + if(gex->flags & GEXF_HOR) + gex->flags |= GEXF_IDQ_R; + } + if(gex->flags & GEXF_VERT) { + if(iy <= 0) { + gex->flags |= GEXF_IDQ_U; + } else { /* supposedly there is no 0-sized entry */ + gex->flags |= GEXF_IDQ_D; + } + } +} + +/* + * Analyse a joint between this and following gentry for fforceconcise() + * and fill out the corresponding parts of the gex_con structure + * Bothe entries must be analyzed first. + */ + +static void +fanalyzejoint( + GENTRY *ge +) +{ + GENTRY *nge = ge->frwd; + GENTRY tge; + GEX_CON *gex, *ngex; + double avsd2, dots[3][2 /*X,Y*/]; + int i; + + gex = X_CON(ge); ngex = X_CON(nge); + + /* look if they can be joined honestly */ + + /* if any is flat, they should join smoothly */ + if( (gex->flags & GEXF_FLAT || ngex->flags & GEXF_FLAT) + && gex->sin2 > SMOOTHSIN2) + goto try_flatboth; + + if(ge->type == GE_LINE) { + if(nge->type == GE_LINE) { + if(gex->len2 > SMALL_LINE2 || ngex->len2 > SMALL_LINE2) + goto try_flatboth; + } else { + if(gex->len2*TIMES_LINE2 > ngex->len2) + goto try_flatboth; + } + } else if(nge->type == GE_LINE) { + if(ngex->len2*TIMES_LINE2 > gex->len2) + goto try_flatboth; + } + + /* if curve changes direction */ + if( gex->isd[X]*ngex->isd[X]<0 || gex->isd[Y]*ngex->isd[Y]<0) + goto try_idealone; + + /* if would create a zigzag */ + if( ((ge->dir&CVDIR_FRONT)-CVDIR_FEQUAL) * ((nge->dir&CVDIR_REAR)-CVDIR_REQUAL) < 0 ) + goto try_flatone; + + if( fcrossraysge(ge, nge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JGOOD; + +try_flatone: + /* look if they can be joined by flatting out one of the entries */ + + /* at this point we know that the general direction of the + * gentries is OK + */ + + if( gex->flags & GEXF_FLAT ) { + tge = *ge; + tge.fx1 = tge.fx3; + tge.fy1 = tge.fy3; + fnormalizege(&tge); + if( fcrossraysge(&tge, nge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JFLAT|GEXF_JFLAT1; + } + if( ngex->flags & GEXF_FLAT ) { + tge = *nge; + tge.fx2 = ge->fx3; + tge.fy2 = ge->fy3; + fnormalizege(&tge); + if( fcrossraysge(ge, &tge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JFLAT|GEXF_JFLAT2; + } + +try_idealone: + /* look if one of the entries can be brought to an idealized + * horizontal or vertical position and then joined + */ + if( gex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) { + tge = *ge; + tge.fx1 = tge.fx3; + tge.fy1 = ge->prev->fy3; /* force horizontal */ + fnormalizege(&tge); + if( fcrossraysge(&tge, nge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JID|GEXF_JID1; + } else if( gex->flags & GEXF_VERT && gex->isd[Y]*ngex->isd[Y]>=0 ) { + tge = *ge; + tge.fx1 = ge->prev->fx3; /* force vertical */ + tge.fy1 = tge.fy3; + fnormalizege(&tge); + if( fcrossraysge(&tge, nge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JID|GEXF_JID1; + } + if( ngex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) { + tge = *nge; + tge.fx2 = ge->fx3; + tge.fy2 = nge->fy3; /* force horizontal */ + fnormalizege(&tge); + if( fcrossraysge(ge, &tge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JID|GEXF_JID2; + } else if( ngex->flags & GEXF_VERT && gex->isd[Y]*ngex->isd[Y]>=0 ) { + tge = *nge; + tge.fx2 = nge->fx3; /* force vertical */ + tge.fy2 = ge->fy3; + fnormalizege(&tge); + if( fcrossraysge(ge, &tge, NULL, NULL, NULL) ) + gex->flags |= GEXF_JID|GEXF_JID2; + } + +try_flatboth: + /* look if we can change them to one line */ + if(gex->flags & GEXF_FLAT && ngex->flags & GEXF_FLAT) { + for(i=0; i<2; i++) { + dots[0][i] = ge->prev->fpoints[i][2]; + dots[1][i] = nge->fpoints[i][2]; + dots[2][i] = ge->fpoints[i][2]; + } + if( fdotsegdist2(dots, dots[2]) <= CVEPS2) + gex->flags |= GEXF_JLINE; + } +} + +/* + * Force conciseness of one contour in the glyph, + * the contour is indicated by one entry from it. + */ + +static void +fconcisecontour( + GLYPH *g, + GENTRY *startge +) +{ +/* initial maximal number of dots to be used as reference */ +#define MAXDOTS ((NREFDOTS+1)*12) + + GENTRY *ge, *pge, *nge, *ige; + GEX_CON *gex, *pgex, *ngex, *nngex; + GENTRY tpge, tnge; + int quad, qq, i, j, ndots, maxdots; + int found[2]; + int joinmask, pflag, nflag; + struct dot_dist *dots; + double avsd2, maxd2, eps2; + double apcv[4][2]; + + if(startge == 0) { + fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n", + __FILE__, __LINE__); + fprintf(stderr, "Strange contour in glyph %s\n", g->name); + dumppaths(g, NULL, NULL); + return; + } + + if(startge->type != GE_CURVE && startge->type != GE_LINE) + return; /* probably a degenerate contour */ + + if(ISDBG(FCONCISE)) + fprintf(stderr, "processing contour 0x%p of glyph %s\n", startge, g->name); + + maxdots = MAXDOTS; + dots = (struct dot_dist *)malloc(sizeof(*dots)*maxdots); + if(dots == NULL) { + fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); + exit(255); + } + + ge = startge; + joinmask = GEXF_JGOOD; + while(1) { + restart: + gex = X_CON(ge); + if((gex->flags & GEXF_JMASK) > ((joinmask<<1)-1)) { + if(ISDBG(FCONCISE)) + fprintf(stderr, "found higher flag (%x>%x) at 0x%p\n", + gex->flags & GEXF_JMASK, ((joinmask<<1)-1), ge); + joinmask <<= 1; + startge = ge; /* have to redo the pass */ + continue; + } + if(( gex->flags & joinmask )==0) + goto next; + + /* if we happen to be in the middle of a string of + * joinable entries, find its beginning + */ + if( gex->flags & (GEXF_JCVMASK^GEXF_JID) ) + quad = gex->flags & X_CON_F(ge->frwd) & GEXF_QMASK; + else if( gex->flags & GEXF_JID2 ) + quad = gex->flags & GEXF_QFROM_IDEAL(X_CON_F(ge->frwd)) & GEXF_QMASK; + else /* must be GEXF_JID1 */ + quad = GEXF_QFROM_IDEAL(gex->flags) & X_CON_F(ge->frwd) & GEXF_QMASK; + + pge = ge; + pgex = X_CON(pge->bkwd); + + if(ISDBG(FCONCISE)) + fprintf(stderr, "ge %p prev -> 0x%p ", ge, pge); + + while(pgex->flags & GEXF_JCVMASK) { + if( !(pgex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID2)) ) + qq = GEXF_QFROM_IDEAL(pgex->flags); + else + qq = pgex->flags & GEXF_QMASK; + + if(ISDBG(FCONCISE)) + fprintf(stderr, "(%x?%x)", quad, qq); + + if( !(quad & qq) ) { + if( !(X_CON_F(pge) & (GEXF_JCVMASK^GEXF_JID)) + && pgex->flags & (GEXF_JCVMASK^GEXF_JID) ) { + /* the previos entry is definitely a better match */ + if(pge == ge) { + if(ISDBG(FCONCISE)) + fprintf(stderr, "\nprev is a better match at %p\n", pge); + startge = ge; + goto next; + } else + pge = pge->frwd; + } + break; + } + + quad &= qq; + pge = pge->bkwd; + pgex = X_CON(pge->bkwd); + if(ISDBG(FCONCISE)) + fprintf(stderr, "0x%p ", pge); + } + + /* collect as many entries for joining as possible */ + nge = ge->frwd; + ngex = X_CON(nge); + nngex = X_CON(nge->frwd); + + if(ISDBG(FCONCISE)) + fprintf(stderr, ": 0x%x\nnext -> 0x%p ", pge, nge); + + while(ngex->flags & GEXF_JCVMASK) { + if( !(ngex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID1)) ) + qq = GEXF_QFROM_IDEAL(nngex->flags); + else + qq = nngex->flags & GEXF_QMASK; + + if(ISDBG(FCONCISE)) + fprintf(stderr, "(%x?%x)", quad, qq); + if( !(quad & qq) ) { + if( !(X_CON_F(nge->bkwd) & (GEXF_JCVMASK^GEXF_JID)) + && ngex->flags & (GEXF_JCVMASK^GEXF_JID) ) { + /* the next-next entry is definitely a better match */ + if(nge == ge->frwd) { + if(ISDBG(FCONCISE)) + fprintf(stderr, "\nnext %x is a better match than %x at %p (jmask %x)\n", + ngex->flags & GEXF_JCVMASK, gex->flags & GEXF_JCVMASK, nge, joinmask); + goto next; + } else + nge = nge->bkwd; + } + break; + } + + quad &= qq; + nge = nge->frwd; + ngex = nngex; + nngex = X_CON(nge->frwd); + if(ISDBG(FCONCISE)) + fprintf(stderr, "0x%p ", nge); + } + + if(ISDBG(FCONCISE)) + fprintf(stderr, ": 0x%x\n", nge); + + /* XXX add splitting of last entries if neccessary */ + + /* make sure that all the reference dots are valid */ + for(ige = pge; ige != nge->frwd; ige = ige->frwd) { + nngex = X_CON(ige); + if( !(nngex->flags & GEXF_VDOTS) ) { + fsampledots(ige, nngex->dots, NREFDOTS); + nngex->flags |= GEXF_VDOTS; + } + } + + /* do the actual joining */ + while(1) { + pgex = X_CON(pge); + ngex = X_CON(nge->bkwd); + /* now the segments to be joined are pge...nge */ + + ndots = 0; + for(ige = pge; ige != nge->frwd; ige = ige->frwd) { + if(maxdots < ndots+(NREFDOTS+1)) { + maxdots += MAXDOTS; + dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots); + if(dots == NULL) { + fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); + exit(255); + } + } + nngex = X_CON(ige); + for(i=0; i<NREFDOTS; i++) { + for(j=0; j<2; j++) + dots[ndots].p[j] = nngex->dots[i][j]; + ndots++; + } + for(j=0; j<2; j++) + dots[ndots].p[j] = ige->fpoints[j][2]; + ndots++; + } + ndots--; /* the last point is not interesting */ + + tpge = *pge; + pflag = pgex->flags; + if(pflag & (GEXF_JGOOD|GEXF_JFLAT2|GEXF_JID2)) { + /* nothing */ + } else if(pflag & GEXF_JFLAT) { + tpge.fx1 = tpge.fx3; + tpge.fy1 = tpge.fy3; + } else if(pflag & GEXF_JID) { + if(pflag & GEXF_HOR) + tpge.fy1 = tpge.bkwd->fy3; + else + tpge.fx1 = tpge.bkwd->fx3; + } + + tnge = *nge; + nflag = ngex->flags; + if(nflag & (GEXF_JGOOD|GEXF_JFLAT1|GEXF_JID) + && !(nflag & GEXF_JID2)) { + /* nothing */ + } else if(nflag & GEXF_JFLAT) { + tnge.fx2 = tnge.bkwd->fx3; + tnge.fy2 = tnge.bkwd->fy3; + } else if(nflag & GEXF_JID) { + if(X_CON_F(nge) & GEXF_HOR) + tnge.fy2 = tnge.fy3; + else + tnge.fx2 = tnge.fx3; + } + + fnormalizege(&tpge); + fnormalizege(&tnge); + if( fcrossraysge(&tpge, &tnge, NULL, NULL, &apcv[1]) ) { + apcv[0][X] = tpge.bkwd->fx3; + apcv[0][Y] = tpge.bkwd->fy3; + /* apcv[1] and apcv[2] were filled by fcrossraysge() */ + apcv[3][X] = tnge.fx3; + apcv[3][Y] = tnge.fy3; + + /* calculate the precision depending on the smaller dimension of the curve */ + maxd2 = apcv[3][X]-apcv[0][X]; + maxd2 *= maxd2; + eps2 = apcv[3][Y]-apcv[0][Y]; + eps2 *= eps2; + if(maxd2 < eps2) + eps2 = maxd2; + eps2 *= (CVEPS2*4.) / (400.*400.); + if(eps2 < CVEPS2) + eps2 = CVEPS2; + else if(eps2 > CVEPS2*4.) + eps2 = CVEPS2*4.; + + fapproxcurve(apcv, dots, ndots); + + avsd2 = fdotcurvdist2(apcv, dots, ndots, &maxd2); + if(ISDBG(FCONCISE)) + fprintf(stderr, "avsd = %g, maxd = %g, ", sqrt(avsd2), sqrt(maxd2)); + if(avsd2 <= eps2 && maxd2 <= eps2*2.) { + /* we've guessed a curve that is close enough */ + ggoodcv++; ggoodcvdots += ndots; + + if(ISDBG(FCONCISE)) { + fprintf(stderr, "in %s joined %p-%p to ", g->name, pge, nge); + for(i=0; i<4; i++) { + fprintf(stderr, " (%g, %g)", apcv[i][X], apcv[i][Y]); + } + fprintf(stderr, " from\n"); + dumppaths(g, pge, nge); + } + for(i=0; i<3; i++) { + pge->fxn[i] = apcv[i+1][X]; + pge->fyn[i] = apcv[i+1][Y]; + } + pge->type = GE_CURVE; + ge = pge; + for(ige = pge->frwd; ; ige = pge->frwd) { + if(ige == pge) { + fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n", + __FILE__, __LINE__); + free(dots); + return; + } + if(startge == ige) + startge = pge; + free(ige->ext); + freethisge(ige); + if(ige == nge) + break; + } + fnormalizege(ge); + if(ISDBG(FCONCISE)) { + fprintf(stderr, "normalized "); + for(i=0; i<3; i++) { + fprintf(stderr, " (%g, %g)", ge->fpoints[X][i], ge->fpoints[Y][i]); + } + fprintf(stderr, "\n"); + } + fanalyzege(ge); + fanalyzejoint(ge); + fanalyzege(ge->bkwd); + fanalyzejoint(ge->bkwd); + + /* the results of this join will have to be reconsidered */ + startge = ge = ge->frwd; + goto restart; + } else { + gbadcv++; gbadcvdots += ndots; + } + } + + /* if we're down to 2 entries then the join has failed */ + if(pge->frwd == nge) { + pgex->flags &= ~joinmask; + if(ISDBG(FCONCISE)) + fprintf(stderr, "no match\n"); + goto next; + } + + /* reduce the number of entries by dropping one at some end, + * should never drop the original ge from the range + */ + + if(nge->bkwd == ge + || (pge != ge && (pgex->flags & GEXF_JCVMASK) <= (ngex->flags & GEXF_JCVMASK)) ) { + pge = pge->frwd; + } else { + nge = nge->bkwd; + } + if(ISDBG(FCONCISE)) + fprintf(stderr, "next try: %p to %p\n", pge, nge); + } + +next: + ge = ge->frwd; + if(ge == startge) { + joinmask = (joinmask >> 1) & GEXF_JCVMASK; + if(joinmask == 0) + break; + } + } + + /* join flat segments into lines */ + /* here ge==startge */ + while(1) { + gex = X_CON(ge); + if( !(gex->flags & GEXF_JLINE) ) + goto next2; + + ndots = 0; + dots[ndots].p[X] = ge->fx3; + dots[ndots].p[Y] = ge->fy3; + ndots++; + + pge = ge->bkwd; + nge = ge->frwd; + + if(ISDBG(FCONCISE)) + fprintf(stderr, "joining LINE from %p-%p\n", ge, nge); + + while(pge!=nge) { + pgex = X_CON(pge); + ngex = X_CON(nge); + if(ISDBG(FCONCISE)) + fprintf(stderr, "(p=%p/%x n=0x%x/%x) ", pge, pgex->flags & GEXF_JLINE, + nge, ngex->flags & GEXF_JLINE); + if( !((pgex->flags | ngex->flags) & GEXF_JLINE) ) { + if(ISDBG(FCONCISE)) + fprintf(stderr, "(end p=%p n=%p) ", pge, nge); + break; + } + + if(maxdots < ndots+2) { + maxdots += MAXDOTS; + dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots); + if(dots == NULL) { + fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); + exit(255); + } + } + if( pgex->flags & GEXF_JLINE ) { + for(i=0; i<2; i++) { + apcv[0][i] = pge->bkwd->fpoints[i][2]; + apcv[1][i] = nge->fpoints[i][2]; + dots[ndots].p[i] = pge->fpoints[i][2]; + } + ndots++; + for(i=0; i<ndots; i++) { + avsd2 = fdotsegdist2(apcv, dots[i].p); + if(avsd2 > CVEPS2) + break; + } + if(i<ndots) { /* failed to join */ + if(ISDBG(FCONCISE)) + fprintf(stderr, "failed to join prev %p ", pge); + ndots--; + pgex->flags &= ~GEXF_JLINE; + } else { + pge = pge->bkwd; + if(pge == nge) { + if(ISDBG(FCONCISE)) + fprintf(stderr, "intersected at prev %p ", pge); + break; /* oops, tried to self-intersect */ + } + } + } else if(ISDBG(FCONCISE)) + fprintf(stderr, "(p=%p) ", pge); + + if( ngex->flags & GEXF_JLINE ) { + for(i=0; i<2; i++) { + apcv[0][i] = pge->fpoints[i][2]; /* pge points before the 1st segment */ + apcv[1][i] = nge->frwd->fpoints[i][2]; + dots[ndots].p[i] = nge->fpoints[i][2]; + } + ndots++; + for(i=0; i<ndots; i++) { + avsd2 = fdotsegdist2(apcv, dots[i].p); + if(avsd2 > CVEPS2) + break; + } + if(i<ndots) { /* failed to join */ + if(ISDBG(FCONCISE)) + fprintf(stderr, "failed to join next %p ", nge->frwd); + ndots--; + ngex->flags &= ~GEXF_JLINE; + } else { + nge = nge->frwd; + } + } else if(ISDBG(FCONCISE)) + fprintf(stderr, "(n=%p) ", nge); + } + + pge = pge->frwd; /* now the limits are pge...nge inclusive */ + if(pge == nge) /* a deeply perversive contour */ + break; + + if(ISDBG(FCONCISE)) { + fprintf(stderr, "\nin %s joined LINE %p-%p from\n", g->name, pge, nge); + dumppaths(g, pge, nge); + } + pge->type = GE_LINE; + for(i=0; i<2; i++) { + pge->fpoints[i][2] = nge->fpoints[i][2]; + } + fnormalizege(pge); + X_CON_F(pge) &= ~GEXF_JLINE; + + ge = pge; + for(ige = pge->frwd; ; ige = pge->frwd) { + if(ige == pge) { + fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n", + __FILE__, __LINE__); + free(dots); + return; + } + if(startge == ige) + startge = pge; + free(ige->ext); + freethisge(ige); + if(ige == nge) + break; + } +next2: + ge = ge->frwd; + if(ge == startge) + break; + } + + free(dots); +} + +/* force conciseness: substitute 2 or more curves going in the +** same quadrant with one curve +** in floating point +*/ + +void +fforceconcise( + GLYPH * g +) +{ + + GENTRY *ge, *nge, *endge, *xge; + + assertisfloat(g, "enforcing conciseness"); + + fdelsmall(g, 0.05); + assertpath(g->entries, __FILE__, __LINE__, g->name); + + if(ISDBG(FCONCISE)) + dumppaths(g, NULL, NULL); + + /* collect more information about each gentry and their joints */ + for (ge = g->entries; ge != 0; ge = ge->next) + if (ge->type == GE_CURVE || ge->type == GE_LINE) + fnormalizege(ge); + + for (ge = g->entries; ge != 0; ge = ge->next) + if (ge->type == GE_CURVE || ge->type == GE_LINE) { + alloc_gex_con(ge); + fanalyzege(ge); + } + + /* see what we can do about joining */ + for (ge = g->entries; ge != 0; ge = ge->next) + if (ge->type == GE_CURVE || ge->type == GE_LINE) + fanalyzejoint(ge); + + /* now do the joining */ + for (ge = g->entries; ge != 0; ge = ge->next) + if(ge->type == GE_MOVE) + fconcisecontour(g, ge->next); + + for (ge = g->entries; ge != 0; ge = ge->next) + if (ge->type == GE_CURVE || ge->type == GE_LINE) + free(ge->ext); +} + +void +print_glyph( + int glyphno +) +{ + GLYPH *g; + GENTRY *ge; + int x = 0, y = 0; + int i; + int grp, lastgrp= -1; + + if(ISDBG(FCONCISE) && glyphno == 0) { + fprintf(stderr, "Guessed curves: bad %d/%d good %d/%d\n", + gbadcv, gbadcvdots, ggoodcv, ggoodcvdots); + } + + g = &glyph_list[glyphno]; + + fprintf(pfa_file, "/%s { \n", g->name); + + /* consider widths >MAXLEGALWIDTH as bugs */ + if( g->scaledwidth <= MAXLEGALWIDTH ) { + fprintf(pfa_file, "0 %d hsbw\n", g->scaledwidth); + } else { + fprintf(pfa_file, "0 1000 hsbw\n"); + WARNING_2 fprintf(stderr, "glyph %s: width %d seems to be buggy, set to 1000\n", + g->name, g->scaledwidth); + } + +#if 0 + fprintf(pfa_file, "%% contours: "); + for (i = 0; i < g->ncontours; i++) + fprintf(pfa_file, "%s(%d,%d) ", (g->contours[i].direction == DIR_OUTER ? "out" : "in"), + g->contours[i].xofmin, g->contours[i].ymin); + fprintf(pfa_file, "\n"); + + if (g->rymin < 5000) + fprintf(pfa_file, "%d lower%s\n", g->rymin, (g->flatymin ? "flat" : "curve")); + if (g->rymax > -5000) + fprintf(pfa_file, "%d upper%s\n", g->rymax, (g->flatymax ? "flat" : "curve")); +#endif + + if (g->hstems) + for (i = 0; i < g->nhs; i += 2) { + if (g->hstems[i].flags & ST_3) { + fprintf(pfa_file, "%d %d %d %d %d %d hstem3\n", + g->hstems[i].value, + g->hstems[i + 1].value - g->hstems[i].value, + g->hstems[i + 2].value, + g->hstems[i + 3].value - g->hstems[i + 2].value, + g->hstems[i + 4].value, + g->hstems[i + 5].value - g->hstems[i + 4].value + ); + i += 4; + } else { + fprintf(pfa_file, "%d %d hstem\n", g->hstems[i].value, + g->hstems[i + 1].value - g->hstems[i].value); + } + } + + if (g->vstems) + for (i = 0; i < g->nvs; i += 2) { + if (g->vstems[i].flags & ST_3) { + fprintf(pfa_file, "%d %d %d %d %d %d vstem3\n", + g->vstems[i].value, + g->vstems[i + 1].value - g->vstems[i].value, + g->vstems[i + 2].value, + g->vstems[i + 3].value - g->vstems[i + 2].value, + g->vstems[i + 4].value, + g->vstems[i + 5].value - g->vstems[i + 4].value + ); + i += 4; + } else { + fprintf(pfa_file, "%d %d vstem\n", g->vstems[i].value, + g->vstems[i + 1].value - g->vstems[i].value); + } + } + + for (ge = g->entries; ge != 0; ge = ge->next) { + if(g->nsg>0) { + grp=ge->stemid; + if(grp >= 0 && grp != lastgrp) { + fprintf(pfa_file, "%d 4 callsubr\n", grp+g->firstsubr); + lastgrp=grp; + } + } + + switch (ge->type) { + case GE_MOVE: + if (absolute) + fprintf(pfa_file, "%d %d amoveto\n", ge->ix3, ge->iy3); + else + rmoveto(ge->ix3 - x, ge->iy3 - y); + if (0) + fprintf(stderr, "Glyph %s: print moveto(%d, %d)\n", + g->name, ge->ix3, ge->iy3); + x = ge->ix3; + y = ge->iy3; + break; + case GE_LINE: + if (absolute) + fprintf(pfa_file, "%d %d alineto\n", ge->ix3, ge->iy3); + else + rlineto(ge->ix3 - x, ge->iy3 - y); + x = ge->ix3; + y = ge->iy3; + break; + case GE_CURVE: + if (absolute) + fprintf(pfa_file, "%d %d %d %d %d %d arcurveto\n", + ge->ix1, ge->iy1, ge->ix2, ge->iy2, ge->ix3, ge->iy3); + else + rrcurveto(ge->ix1 - x, ge->iy1 - y, + ge->ix2 - ge->ix1, ge->iy2 - ge->iy1, + ge->ix3 - ge->ix2, ge->iy3 - ge->iy2); + x = ge->ix3; + y = ge->iy3; + break; + case GE_PATH: + closepath(); + break; + default: + WARNING_1 fprintf(stderr, "**** Glyph %s: unknown entry type '%c'\n", + g->name, ge->type); + break; + } + } + + fprintf(pfa_file, "endchar } ND\n"); +} + +/* print the subroutines for this glyph, returns the number of them */ +int +print_glyph_subs( + int glyphno, + int startid /* start numbering subroutines from this id */ +) +{ + GLYPH *g; + int i, grp; + + g = &glyph_list[glyphno]; + + if(!hints || !subhints || g->nsg<1) + return 0; + + g->firstsubr=startid; + +#if 0 + fprintf(pfa_file, "%% %s %d\n", g->name, g->nsg); +#endif + for(grp=0; grp<g->nsg; grp++) { + fprintf(pfa_file, "dup %d {\n", startid++); + for(i= (grp==0)? 0 : g->nsbs[grp-1]; i<g->nsbs[grp]; i++) + fprintf(pfa_file, "\t%d %d %cstem\n", g->sbstems[i].low, + g->sbstems[i].high-g->sbstems[i].low, + g->sbstems[i].isvert ? 'v' : 'h'); + fprintf(pfa_file, "\treturn\n\t} NP\n"); + } + + return g->nsg; +} + +void +print_glyph_metrics( + int code, + int glyphno +) +{ + GLYPH *g; + + g = &glyph_list[glyphno]; + + if(transform) + fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n", + code, g->scaledwidth, g->name, + iscale(g->xMin), iscale(g->yMin), iscale(g->xMax), iscale(g->yMax)); + else + fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n", + code, g->scaledwidth, g->name, + g->xMin, g->yMin, g->xMax, g->yMax); +} + +/* + SB: + An important note about the BlueValues. + + The Adobe documentation says that the maximal width of a Blue zone + is connected to the value of BlueScale, which is by default 0.039625. + The BlueScale value defines, at which point size the overshoot + suppression be disabled. + + The formula for it that is given in the manual is: + + BlueScale=point_size/240, for a 300dpi device + + that makes us wonder what is this 240 standing for. Incidentally + 240=72*1000/300, where 72 is the relation between inches and points, + 1000 is the size of the glyph matrix, and 300dpi is the resolution of + the output device. Knowing that we can recalculate the formula for + the font size in pixels rather than points: + + BlueScale=pixel_size/1000 + + That looks a lot simpler than the original formula, does not it ? + And the limitation about the maximal width of zone also looks + a lot simpler after the transformation: + + max_width < 1000/pixel_size + + that ensures that even at the maximal pixel size when the overshoot + suppression is disabled the zone width will be less than one pixel. + This is important, failure to comply to this limit will result in + really ugly fonts (been there, done that). But knowing the formula + for the pixel width, we see that in fact we can use the maximal width + of 24, not 23 as specified in the manual. + +*/ + +#define MAXBLUEWIDTH (24) + +/* + * Find the indexes of the most frequent values + * in the hystogram, sort them in ascending order, and save which one + * was the best one (if asked). + * Returns the number of values found (may be less than maximal because + * we ignore the zero values) + */ + +#define MAXHYST (2000) /* size of the hystogram */ +#define HYSTBASE 500 + +static int +besthyst( + int *hyst, /* the hystogram */ + int base, /* the base point of the hystogram */ + int *best, /* the array for indexes of best values */ + int nbest, /* its allocated size */ + int width, /* minimal difference between indexes */ + int *bestindp /* returned top point */ +) +{ + unsigned char hused[MAXHYST / 8 + 1]; + int i, max, j, w, last = 0; + int nf = 0; + + width--; + + memset(hused, 0 , sizeof hused); + + max = 1; + for (i = 0; i < nbest && max != 0; i++) { + best[i] = 0; + max = 0; + for (j = 1; j < MAXHYST - 1; j++) { + w = hyst[j]; + + if (w > max && (hused[j>>3] & (1 << (j & 0x07))) == 0) { + best[i] = j; + max = w; + } + } + if (max != 0) { + if (max < last/2) { + /* do not pick the too low values */ + break; + } + for (j = best[i] - width; j <= best[i] + width; j++) { + if (j >= 0 && j < MAXHYST) + hused[j >> 3] |= (1 << (j & 0x07)); + } + last = max; + best[i] -= base; + nf = i + 1; + } + } + + if (bestindp) + *bestindp = best[0]; + + /* sort the indexes in ascending order */ + for (i = 0; i < nf; i++) { + for (j = i + 1; j < nf; j++) + if (best[j] < best[i]) { + w = best[i]; + best[i] = best[j]; + best[j] = w; + } + } + + return nf; +} + +/* + * Find the next best Blue zone in the hystogram. + * Return the weight of the found zone. + */ + +static int +bestblue( + short *zhyst, /* the zones hystogram */ + short *physt, /* the points hystogram */ + short *ozhyst, /* the other zones hystogram */ + int *bluetab /* where to put the found zone */ +) +{ + int i, j, w, max, ind, first, last; + + /* find the highest point in the zones hystogram */ + /* if we have a plateau, take its center */ + /* if we have multiple peaks, take the first one */ + + max = -1; + first = last = -10; + for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) { + w = zhyst[i]; + if (w > max) { + first = last = i; + max = w; + } else if (w == max) { + if (last == i - 1) + last = i; + } + } + ind = (first + last) / 2; + + if (max == 0) /* no zones left */ + return 0; + + /* now we reuse `first' and `last' as inclusive borders of the zone */ + first = ind; + last = ind + (MAXBLUEWIDTH - 1); + + /* our maximal width is far too big, so we try to make it narrower */ + w = max; + j = (w & 1); /* a pseudo-random bit */ + while (1) { + while (physt[first] == 0) + first++; + while (physt[last] == 0) + last--; + if (last - first < (MAXBLUEWIDTH * 2 / 3) || (max - w) * 10 > max) + break; + + if (physt[first] < physt[last] + || (physt[first] == physt[last] && j)) { + if (physt[first] * 20 > w) /* if weight is >5%, + * stop */ + break; + w -= physt[first]; + first++; + j = 0; + } else { + if (physt[last] * 20 > w) /* if weight is >5%, + * stop */ + break; + w -= physt[last]; + last--; + j = 1; + } + } + + /* save our zone */ + bluetab[0] = first - HYSTBASE; + bluetab[1] = last - HYSTBASE; + + /* invalidate all the zones overlapping with this one */ + /* the constant of 2 is determined by the default value of BlueFuzz */ + for (i = first - (MAXBLUEWIDTH - 1) - 2; i <= last + 2; i++) + if (i >= 0 && i < MAXHYST) { + zhyst[i] = 0; + ozhyst[i] = 0; + } + return w; +} + +/* + * Try to find the Blue Values, bounding box and italic angle + */ + +void +findblues(void) +{ + /* hystograms for upper and lower zones */ + short hystl[MAXHYST]; + short hystu[MAXHYST]; + short zuhyst[MAXHYST]; + short zlhyst[MAXHYST]; + int nchars; + int i, j, k, w, max; + GENTRY *ge; + GLYPH *g; + double ang; + + /* find the lowest and highest points of glyphs */ + /* and by the way build the values for FontBBox */ + /* and build the hystogram for the ItalicAngle */ + + /* re-use hystl for the hystogram of italic angle */ + + bbox[0] = bbox[1] = 5000; + bbox[2] = bbox[3] = -5000; + + for (i = 0; i < MAXHYST; i++) + hystl[i] = 0; + + nchars = 0; + + for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { + if (g->flags & GF_USED) { + nchars++; + + g->rymin = 5000; + g->rymax = -5000; + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type == GE_LINE) { + + j = ge->iy3 - ge->prev->iy3; + k = ge->ix3 - ge->prev->ix3; + if (j > 0) + ang = atan2(-k, j) * 180.0 / M_PI; + else + ang = atan2(k, -j) * 180.0 / M_PI; + + k /= 100; + j /= 100; + if (ang > -45.0 && ang < 45.0) { + /* + * be careful to not overflow + * the counter + */ + hystl[HYSTBASE + (int) (ang * 10.0)] += (k * k + j * j) / 4; + } + if (ge->iy3 == ge->prev->iy3) { + if (ge->iy3 <= g->rymin) { + g->rymin = ge->iy3; + g->flatymin = 1; + } + if (ge->iy3 >= g->rymax) { + g->rymax = ge->iy3; + g->flatymax = 1; + } + } else { + if (ge->iy3 < g->rymin) { + g->rymin = ge->iy3; + g->flatymin = 0; + } + if (ge->iy3 > g->rymax) { + g->rymax = ge->iy3; + g->flatymax = 0; + } + } + } else if (ge->type == GE_CURVE) { + if (ge->iy3 < g->rymin) { + g->rymin = ge->iy3; + g->flatymin = 0; + } + if (ge->iy3 > g->rymax) { + g->rymax = ge->iy3; + g->flatymax = 0; + } + } + if (ge->type == GE_LINE || ge->type == GE_CURVE) { + if (ge->ix3 < bbox[0]) + bbox[0] = ge->ix3; + if (ge->ix3 > bbox[2]) + bbox[2] = ge->ix3; + if (ge->iy3 < bbox[1]) + bbox[1] = ge->iy3; + if (ge->iy3 > bbox[3]) + bbox[3] = ge->iy3; + } + } + } + } + + /* get the most popular angle */ + max = 0; + w = 0; + for (i = 0; i < MAXHYST; i++) { + if (hystl[i] > w) { + w = hystl[i]; + max = i; + } + } + ang = (double) (max - HYSTBASE) / 10.0; + WARNING_2 fprintf(stderr, "Guessed italic angle: %f\n", ang); + if (italic_angle == 0.0) + italic_angle = ang; + + /* build the hystogram of the lower points */ + for (i = 0; i < MAXHYST; i++) + hystl[i] = 0; + + for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { + if ((g->flags & GF_USED) + && g->rymin + HYSTBASE >= 0 && g->rymin < MAXHYST - HYSTBASE) { + hystl[g->rymin + HYSTBASE]++; + } + } + + /* build the hystogram of the upper points */ + for (i = 0; i < MAXHYST; i++) + hystu[i] = 0; + + for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { + if ((g->flags & GF_USED) + && g->rymax + HYSTBASE >= 0 && g->rymax < MAXHYST - HYSTBASE) { + hystu[g->rymax + HYSTBASE]++; + } + } + + /* build the hystogram of all the possible lower zones with max width */ + for (i = 0; i < MAXHYST; i++) + zlhyst[i] = 0; + + for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) { + for (j = 0; j < MAXBLUEWIDTH; j++) + zlhyst[i] += hystl[i + j]; + } + + /* build the hystogram of all the possible upper zones with max width */ + for (i = 0; i < MAXHYST; i++) + zuhyst[i] = 0; + + for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) { + for (j = 0; j < MAXBLUEWIDTH; j++) + zuhyst[i] += hystu[i + j]; + } + + /* find the baseline */ + w = bestblue(zlhyst, hystl, zuhyst, &bluevalues[0]); + if (0) + fprintf(stderr, "BaselineBlue zone %d%% %d...%d\n", w * 100 / nchars, + bluevalues[0], bluevalues[1]); + + if (w == 0) /* no baseline, something weird */ + return; + + /* find the upper zones */ + for (nblues = 2; nblues < 14; nblues += 2) { + w = bestblue(zuhyst, hystu, zlhyst, &bluevalues[nblues]); + + if (0) + fprintf(stderr, "Blue zone %d%% %d...%d\n", w * 100 / nchars, + bluevalues[nblues], bluevalues[nblues+1]); + + if (w * 20 < nchars) + break; /* don't save this zone */ + } + + /* find the lower zones */ + for (notherb = 0; notherb < 10; notherb += 2) { + w = bestblue(zlhyst, hystl, zuhyst, &otherblues[notherb]); + + if (0) + fprintf(stderr, "OtherBlue zone %d%% %d...%d\n", w * 100 / nchars, + otherblues[notherb], otherblues[notherb+1]); + + + if (w * 20 < nchars) + break; /* don't save this zone */ + } + +} + +/* + * Find the actual width of the glyph and modify the + * description to reflect it. Not guaranteed to do + * any good, may make character spacing too wide. + */ + +void +docorrectwidth(void) +{ + int i; + GENTRY *ge; + GLYPH *g; + int xmin, xmax; + int maxwidth, minsp; + + /* enforce this minimal spacing, + * we limit the amount of the enforced spacing to avoid + * spacing the bold wonts too widely + */ + minsp = (stdhw>60 || stdhw<10)? 60 : stdhw; + + for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { + g->oldwidth=g->scaledwidth; /* save the old width, will need for AFM */ + + if (correctwidth && g->flags & GF_USED) { + xmin = 5000; + xmax = -5000; + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type != GE_LINE && ge->type != GE_CURVE) + continue; + + if (ge->ix3 <= xmin) { + xmin = ge->ix3; + } + if (ge->ix3 >= xmax) { + xmax = ge->ix3; + } + } + + maxwidth=xmax+minsp; + if( g->scaledwidth < maxwidth ) { + g->scaledwidth = maxwidth; + WARNING_3 fprintf(stderr, "glyph %s: extended from %d to %d\n", + g->name, g->oldwidth, g->scaledwidth ); + } + } + } + +} + +/* + * Try to find the typical stem widths + */ + +void +stemstatistics(void) +{ +#define MINDIST 10 /* minimal distance between the widths */ + int hyst[MAXHYST+MINDIST*2]; + int best[12]; + int i, j, k, w; + int nchars; + int ns; + STEM *s; + GLYPH *g; + + /* start with typical stem width */ + + nchars=0; + + /* build the hystogram of horizontal stem widths */ + memset(hyst, 0, sizeof hyst); + + for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { + if (g->flags & GF_USED) { + nchars++; + s = g->hstems; + for (j = 0; j < g->nhs; j += 2) { + if ((s[j].flags | s[j + 1].flags) & ST_END) + continue; + w = s[j + 1].value - s[j].value+1; + if(w==20) /* split stems should not be counted */ + continue; + if (w > 0 && w < MAXHYST - 1) { + /* + * handle some fuzz present in + * converted fonts + */ + hyst[w+MINDIST] += MINDIST-1; + for(k=1; k<MINDIST-1; k++) { + hyst[w+MINDIST + k] += MINDIST-1-k; + hyst[w+MINDIST - k] += MINDIST-1-k; + } + } + } + } + } + + /* find 12 most frequent values */ + ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdhw); + + /* store data in stemsnaph */ + for (i = 0; i < ns; i++) + stemsnaph[i] = best[i]; + if (ns < 12) + stemsnaph[ns] = 0; + + /* build the hystogram of vertical stem widths */ + memset(hyst, 0, sizeof hyst); + + for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { + if (g->flags & GF_USED) { + s = g->vstems; + for (j = 0; j < g->nvs; j += 2) { + if ((s[j].flags | s[j + 1].flags) & ST_END) + continue; + w = s[j + 1].value - s[j].value+1; + if (w > 0 && w < MAXHYST - 1) { + /* + * handle some fuzz present in + * converted fonts + */ + hyst[w+MINDIST] += MINDIST-1; + for(k=1; k<MINDIST-1; k++) { + hyst[w+MINDIST + k] += MINDIST-1-k; + hyst[w+MINDIST - k] += MINDIST-1-k; + } + } + } + } + } + + /* find 12 most frequent values */ + ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdvw); + + /* store data in stemsnaph */ + for (i = 0; i < ns; i++) + stemsnapv[i] = best[i]; + if (ns < 12) + stemsnapv[ns] = 0; + +#undef MINDIST +} + +/* + * SB + * A funny thing: TTF paths are going in reverse direction compared + * to Type1. So after all (because the rest of logic uses TTF + * path directions) we have to reverse the paths. + * + * It was a big headache to discover that. + */ + +/* works on both int and float paths */ + +void +reversepathsfromto( + GENTRY * from, + GENTRY * to +) +{ + GENTRY *ge, *nge, *pge; + GENTRY *cur, *next; + int i, n, ilast[2]; + double flast[2], f; + + for (ge = from; ge != 0 && ge != to; ge = ge->next) { + if(ge->type == GE_LINE || ge->type == GE_CURVE) { + if (ISDBG(REVERSAL)) + fprintf(stderr, "reverse path 0x%x <- 0x%x, 0x%x\n", ge, ge->prev, ge->bkwd); + + /* cut out the path itself */ + pge = ge->prev; /* GE_MOVE */ + if (pge == 0) { + fprintf(stderr, "**! No MOVE before line !!! Fatal. ****\n"); + exit(1); + } + nge = ge->bkwd->next; /* GE_PATH */ + pge->next = nge; + nge->prev = pge; + ge->bkwd->next = 0; /* mark end of chain */ + + /* remember the starting point */ + if(ge->flags & GEF_FLOAT) { + flast[0] = pge->fx3; + flast[1] = pge->fy3; + } else { + ilast[0] = pge->ix3; + ilast[1] = pge->iy3; + } + + /* then reinsert them in backwards order */ + for(cur = ge; cur != 0; cur = next ) { + next = cur->next; /* or addgeafter() will screw it up */ + if(cur->flags & GEF_FLOAT) { + for(i=0; i<2; i++) { + /* reverse the direction of path element */ + f = cur->fpoints[i][0]; + cur->fpoints[i][0] = cur->fpoints[i][1]; + cur->fpoints[i][1] = f; + f = flast[i]; + flast[i] = cur->fpoints[i][2]; + cur->fpoints[i][2] = f; + } + } else { + for(i=0; i<2; i++) { + /* reverse the direction of path element */ + n = cur->ipoints[i][0]; + cur->ipoints[i][0] = cur->ipoints[i][1]; + cur->ipoints[i][1] = n; + n = ilast[i]; + ilast[i] = cur->ipoints[i][2]; + cur->ipoints[i][2] = n; + } + } + addgeafter(pge, cur); + } + + /* restore the starting point */ + if(ge->flags & GEF_FLOAT) { + pge->fx3 = flast[0]; + pge->fy3 = flast[1]; + } else { + pge->ix3 = ilast[0]; + pge->iy3 = ilast[1]; + } + + ge = nge; + } + + } +} + +void +reversepaths( + GLYPH * g +) +{ + reversepathsfromto(g->entries, NULL); +} + +/* add a kerning pair information, scales the value */ + +void +addkernpair( + unsigned id1, + unsigned id2, + int unscval +) +{ + static unsigned char *bits = 0; + static int lastid; + GLYPH *g = &glyph_list[id1]; + int i, n; + struct kern *p; + + if(unscval == 0 || id1 >= numglyphs || id2 >= numglyphs) + return; + + if( (glyph_list[id1].flags & GF_USED)==0 + || (glyph_list[id2].flags & GF_USED)==0 ) + return; + + if(bits == 0) { + bits = calloc( BITMAP_BYTES(numglyphs), 1); + if (bits == NULL) { + fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); + exit(255); + } + lastid = id1; + } + + if(lastid != id1) { + /* refill the bitmap cache */ + memset(bits, 0,BITMAP_BYTES(numglyphs)); + p = g->kern; + for(i=g->kerncount; i>0; i--) { + n = (p++)->id; + SET_BITMAP(bits, n); + } + lastid = id1; + } + + if(IS_BITMAP(bits, id2)) + return; /* duplicate */ + + if(g->kerncount <= g->kernalloc) { + g->kernalloc += 8; + p = realloc(g->kern, sizeof(struct kern) * g->kernalloc); + if(p == 0) { + fprintf (stderr, "** realloc failed, kerning data will be incomplete\n"); + } + g->kern = p; + } + + SET_BITMAP(bits, id2); + p = &g->kern[g->kerncount]; + p->id = id2; + p->val = iscale(unscval) - (g->scaledwidth - g->oldwidth); + g->kerncount++; + kerning_pairs++; +} + +/* print out the kerning information */ + +void +print_kerning( + FILE *afm_file +) +{ + int i, j, n; + GLYPH *g; + struct kern *p; + + if( kerning_pairs == 0 ) + return; + + fprintf(afm_file, "StartKernData\n"); + fprintf(afm_file, "StartKernPairs %hd\n", kerning_pairs); + + for(i=0; i<numglyphs; i++) { + g = &glyph_list[i]; + if( (g->flags & GF_USED) ==0) + continue; + p = g->kern; + for(j=g->kerncount; j>0; j--, p++) { + fprintf(afm_file, "KPX %s %s %d\n", g->name, + glyph_list[ p->id ].name, p->val ); + } + } + + fprintf(afm_file, "EndKernPairs\n"); + fprintf(afm_file, "EndKernData\n"); +} + + +#if 0 + +/* +** This function is commented out because the information +** collected by it is not used anywhere else yet. Now +** it only collects the directions of contours. And the +** direction of contours gets fixed already in draw_glyf(). +** +*********************************************** +** +** Here we expect that the paths are already closed. +** We also expect that the contours do not intersect +** and that curves doesn't cross any border of quadrant. +** +** Find which contours go inside which and what is +** their proper direction. Then fix the direction +** to make it right. +** +*/ + +#define MAXCONT 1000 + +void +fixcontours( + GLYPH * g +) +{ + CONTOUR cont[MAXCONT]; + short ymax[MAXCONT]; /* the highest point */ + short xofmax[MAXCONT]; /* X-coordinate of any point + * at ymax */ + short ymin[MAXCONT]; /* the lowest point */ + short xofmin[MAXCONT]; /* X-coordinate of any point + * at ymin */ + short count[MAXCONT]; /* count of lines */ + char dir[MAXCONT]; /* in which direction they must go */ + GENTRY *start[MAXCONT], *minptr[MAXCONT], *maxptr[MAXCONT]; + int ncont; + int i; + int dx1, dy1, dx2, dy2; + GENTRY *ge, *nge; + + /* find the contours and their most upper/lower points */ + ncont = 0; + ymax[0] = -5000; + ymin[0] = 5000; + for (ge = g->entries; ge != 0; ge = ge->next) { + if (ge->type == GE_LINE || ge->type == GE_CURVE) { + if (ge->iy3 > ymax[ncont]) { + ymax[ncont] = ge->iy3; + xofmax[ncont] = ge->ix3; + maxptr[ncont] = ge; + } + if (ge->iy3 < ymin[ncont]) { + ymin[ncont] = ge->iy3; + xofmin[ncont] = ge->ix3; + minptr[ncont] = ge; + } + } + if (ge->frwd != ge->next) { + start[ncont++] = ge->frwd; + ymax[ncont] = -5000; + ymin[ncont] = 5000; + } + } + + /* determine the directions of contours */ + for (i = 0; i < ncont; i++) { + ge = minptr[i]; + nge = ge->frwd; + + if (ge->type == GE_CURVE) { + dx1 = ge->ix3 - ge->ix2; + dy1 = ge->iy3 - ge->iy2; + + if (dx1 == 0 && dy1 == 0) { /* a pathological case */ + dx1 = ge->ix3 - ge->ix1; + dy1 = ge->iy3 - ge->iy1; + } + if (dx1 == 0 && dy1 == 0) { /* a more pathological + * case */ + dx1 = ge->ix3 - ge->prev->ix3; + dy1 = ge->iy3 - ge->prev->iy3; + } + } else { + dx1 = ge->ix3 - ge->prev->ix3; + dy1 = ge->iy3 - ge->prev->iy3; + } + if (nge->type == GE_CURVE) { + dx2 = ge->ix3 - nge->ix1; + dy2 = ge->iy3 - nge->iy1; + if (dx1 == 0 && dy1 == 0) { /* a pathological case */ + dx2 = ge->ix3 - nge->ix2; + dy2 = ge->iy3 - nge->iy2; + } + if (dx1 == 0 && dy1 == 0) { /* a more pathological + * case */ + dx2 = ge->ix3 - nge->ix3; + dy2 = ge->iy3 - nge->iy3; + } + } else { + dx2 = ge->ix3 - nge->ix3; + dy2 = ge->iy3 - nge->iy3; + } + + /* compare angles */ + cont[i].direction = DIR_INNER; + if (dy1 == 0) { + if (dx1 < 0) + cont[i].direction = DIR_OUTER; + } else if (dy2 == 0) { + if (dx2 > 0) + cont[i].direction = DIR_OUTER; + } else if (dx2 * dy1 < dx1 * dy2) + cont[i].direction = DIR_OUTER; + + cont[i].ymin = ymin[i]; + cont[i].xofmin = xofmin[i]; + } + + /* save the information that may be needed further */ + g->ncontours = ncont; + if (ncont > 0) { + g->contours = malloc(sizeof(CONTOUR) * ncont); + if (g->contours == 0) { + fprintf(stderr, "***** Memory allocation error *****\n"); + exit(255); + } + memcpy(g->contours, cont, sizeof(CONTOUR) * ncont); + } +} + +#endif + +/* + * + */ + |