16 # include <netinet/in.h>
19 # include "win_missing.h"
26 /* big and small values for comparisons */
27 #define FBIGVAL (1e20)
28 #define FEPS (100000./FBIGVAL)
30 /* names of the axes */
34 /* the GENTRY extension structure used in fforceconcise() */
37 double d[2 /*X, Y*/]; /* sizes of curve */
38 double sin2; /* squared sinus of the angle to the next gentry */
39 double len2; /* squared distance between the endpoints */
41 /* number of reference dots taken from each curve */
44 double dots[NREFDOTS][2]; /* reference dots */
46 int flags; /* flags for gentry and tits joint to the next gentry */
47 /* a vertical or horizontal line may be in 2 quadrants at once */
48 #define GEXF_QUL 0x00000001 /* in up-left quadrant */
49 #define GEXF_QUR 0x00000002 /* in up-right quadrant */
50 #define GEXF_QDR 0x00000004 /* in down-right quadrant */
51 #define GEXF_QDL 0x00000008 /* in down-left quadrant */
52 #define GEXF_QMASK 0x0000000F /* quadrant mask */
54 /* if a line is nearly vertical or horizontal, we remember that idealized quartant too */
55 #define GEXF_QTO_IDEAL(f) (((f)&0xF)<<4)
56 #define GEXF_QFROM_IDEAL(f) (((f)&0xF0)>>4)
57 #define GEXF_IDQ_L 0x00000090 /* left */
58 #define GEXF_IDQ_R 0x00000060 /* right */
59 #define GEXF_IDQ_U 0x00000030 /* up */
60 #define GEXF_IDQ_D 0x000000C0 /* down */
62 /* possibly can be joined with conditions:
63 * (in order of increasing preference, the numeric order is important)
65 #define GEXF_JLINE 0x00000100 /* into one line */
66 #define GEXF_JIGN 0x00000200 /* if one entry's tangent angle is ignored */
67 #define GEXF_JID 0x00000400 /* if one entry is idealized to hor/vert */
68 #define GEXF_JFLAT 0x00000800 /* if one entry is flattened */
69 #define GEXF_JGOOD 0x00001000 /* perfectly, no additional maodifications */
71 #define GEXF_JMASK 0x00001F00 /* the mask of all above */
72 #define GEXF_JCVMASK 0x00001E00 /* the mask of all above except JLINE */
74 /* which entry needs to be modified for conditional joining */
75 #define GEXF_JIGN1 0x00002000
76 #define GEXF_JIGN2 0x00004000
77 #define GEXF_JIGNDIR(dir) (GEXF_JIGN1<<(dir))
78 #define GEXF_JID1 0x00008000
79 #define GEXF_JID2 0x00010000
80 #define GEXF_JIDDIR(dir) (GEXF_JID1<<(dir))
81 #define GEXF_JFLAT1 0x00020000
82 #define GEXF_JFLAT2 0x00040000
83 #define GEXF_JFLATDIR(dir) (GEXF_JFLAT1<<(dir))
85 #define GEXF_VERT 0x00100000 /* is nearly vertical */
86 #define GEXF_HOR 0x00200000 /* is nearly horizontal */
87 #define GEXF_FLAT 0x00400000 /* is nearly flat */
89 #define GEXF_VDOTS 0x01000000 /* the dots are valid */
91 signed char isd[2 /*X,Y*/]; /* signs of the sizes */
93 typedef struct gex_con GEX_CON;
95 /* convenience macros */
96 #define X_CON(ge) ((GEX_CON *)((ge)->ext))
97 #define X_CON_D(ge) (X_CON(ge)->d)
98 #define X_CON_DX(ge) (X_CON(ge)->d[0])
99 #define X_CON_DY(ge) (X_CON(ge)->d[1])
100 #define X_CON_ISD(ge) (X_CON(ge)->isd)
101 #define X_CON_ISDX(ge) (X_CON(ge)->isd[0])
102 #define X_CON_ISDY(ge) (X_CON(ge)->isd[1])
103 #define X_CON_SIN2(ge) (X_CON(ge)->sin2)
104 #define X_CON_LEN2(ge) (X_CON(ge)->len2)
105 #define X_CON_F(ge) (X_CON(ge)->flags)
107 /* performance statistics about guessing the concise curves */
108 static int ggoodcv=0, ggoodcvdots=0, gbadcv=0, gbadcvdots=0;
110 int stdhw, stdvw; /* dominant stems widths */
111 int stemsnaph[12], stemsnapv[12]; /* most typical stem width */
117 int bbox[4]; /* the FontBBox array */
121 int encoding[ENCTABSZ]; /* inverse of glyph[].char_no */
122 int kerning_pairs = 0;
125 static void fixcvdir( GENTRY * ge, int dir);
126 static void fixcvends( GENTRY * ge);
127 static int fgetcvdir( GENTRY * ge);
128 static int igetcvdir( GENTRY * ge);
129 static int fiszigzag( GENTRY *ge);
130 static int iiszigzag( GENTRY *ge);
131 static GENTRY * freethisge( GENTRY *ge);
132 static void addgeafter( GENTRY *oge, GENTRY *nge );
133 static GENTRY * newgentry( int flags);
134 static void debugstems( char *name, STEM * hstems, int nhs, STEM * vstems, int nvs);
135 static int addbluestems( STEM *s, int n);
136 static void sortstems( STEM * s, int n);
137 static int stemoverlap( STEM * s1, STEM * s2);
138 static int steminblue( STEM *s);
139 static void markbluestems( STEM *s, int nold);
140 static int joinmainstems( STEM * s, int nold, int useblues);
141 static void joinsubstems( STEM * s, short *pairs, int nold, int useblues);
142 static void fixendpath( GENTRY *ge);
143 static void fdelsmall( GLYPH *g, double minlen);
144 static void alloc_gex_con( GENTRY *ge);
145 static double fjointsin2( GENTRY *ge1, GENTRY *ge2);
146 static double fcvarea( GENTRY *ge);
147 static double fcvval( GENTRY *ge, int axis, double t);
148 static void fsampledots( GENTRY *ge, double dots[][2], int ndots);
149 static void fnormalizege( GENTRY *ge);
150 static void fanalyzege( GENTRY *ge);
151 static void fanalyzejoint( GENTRY *ge);
152 static void fconcisecontour( GLYPH *g, GENTRY *ge);
153 static double fclosegap( GENTRY *from, GENTRY *to, int axis,
154 double gap, double *ret);
189 ge = calloc(1, sizeof(GENTRY));
192 fprintf(stderr, "***** Memory allocation error *****\n");
197 /* the rest is set to 0 by calloc() */
202 * Routines to print out Postscript functions with optimization
211 if (optimize && dx == 0)
212 fprintf(pfa_file, "%d vmoveto\n", dy);
213 else if (optimize && dy == 0)
214 fprintf(pfa_file, "%d hmoveto\n", dx);
216 fprintf(pfa_file, "%d %d rmoveto\n", dx, dy);
225 if (optimize && dx == 0 && dy == 0) /* for special pathologic
228 else if (optimize && dx == 0)
229 fprintf(pfa_file, "%d vlineto\n", dy);
230 else if (optimize && dy == 0)
231 fprintf(pfa_file, "%d hlineto\n", dx);
233 fprintf(pfa_file, "%d %d rlineto\n", dx, dy);
246 /* first two ifs are for crazy cases that occur surprisingly often */
247 if (optimize && dx1 == 0 && dx2 == 0 && dx3 == 0)
248 rlineto(0, dy1 + dy2 + dy3);
249 else if (optimize && dy1 == 0 && dy2 == 0 && dy3 == 0)
250 rlineto(dx1 + dx2 + dx3, 0);
251 else if (optimize && dy1 == 0 && dx3 == 0)
252 fprintf(pfa_file, "%d %d %d %d hvcurveto\n",
254 else if (optimize && dx1 == 0 && dy3 == 0)
255 fprintf(pfa_file, "%d %d %d %d vhcurveto\n",
258 fprintf(pfa_file, "%d %d %d %d %d %d rrcurveto\n",
259 dx1, dy1, dx2, dy2, dx3, dy3);
265 fprintf(pfa_file, "closepath\n");
269 * Many of the path processing routines exist (or will exist) in
270 * both floating-point and integer version. Fimally most of the
271 * processing will go in floating point and the integer processing
272 * will become legacy.
273 * The names of floating routines start with f, names of integer
274 * routines start with i, and those old routines existing in one
275 * version only have no such prefix at all.
279 ** Routine that checks integrity of the path, for debugging
290 GENTRY *first, *pe, *ge;
295 isfloat = (from->flags & GEF_FLOAT);
297 for (ge = from; ge != 0; pe = ge, ge = ge->next) {
298 if( (ge->flags & GEF_FLOAT) ^ isfloat ) {
299 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
300 fprintf(stderr, "float flag changes from %s to %s at 0x%p (type %c, prev type %c)\n",
301 (isfloat ? "TRUE" : "FALSE"), (isfloat ? "FALSE" : "TRUE"), ge, ge->type, pe->type);
304 if (pe != ge->prev) {
305 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
306 fprintf(stderr, "unidirectional chain 0x%x -next-> 0x%x -prev-> 0x%x \n",
316 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
317 fprintf(stderr, "empty path at 0x%x \n", ge);
323 if(ge->frwd->bkwd != ge) {
324 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
325 fprintf(stderr, "unidirectional chain 0x%x -frwd-> 0x%x -bkwd-> 0x%x \n",
326 ge, ge->frwd, ge->frwd->bkwd);
329 if(ge->prev->type == GE_MOVE) {
331 if(ge->bkwd->next->type != GE_PATH) {
332 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
333 fprintf(stderr, "broken first backlink 0x%x -bkwd-> 0x%x -next-> 0x%x \n",
334 ge, ge->bkwd, ge->bkwd->next);
338 if(ge->next->type == GE_PATH) {
339 if(ge->frwd != first) {
340 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
341 fprintf(stderr, "broken loop 0x%x -...-> 0x%x -frwd-> 0x%x \n",
342 first, ge, ge->frwd);
358 if( !(g->flags & GF_FLOAT) ) {
359 fprintf(stderr, "**! Glyph %s is not float: %s\n", g->name, msg);
363 if( !(g->lastentry->flags & GEF_FLOAT) ) {
364 fprintf(stderr, "**! Glyphs %s last entry is int: %s\n", g->name, msg);
376 if( (g->flags & GF_FLOAT) ) {
377 fprintf(stderr, "**! Glyph %s is not int: %s\n", g->name, msg);
381 if( (g->lastentry->flags & GEF_FLOAT) ) {
382 fprintf(stderr, "**! Glyphs %s last entry is float: %s\n", g->name, msg);
390 * Routines to save the generated data about glyph
402 fprintf(stderr, "%s: f rmoveto(%g, %g)\n", g->name, x, y);
404 assertisfloat(g, "adding float MOVE");
406 if ((oge = g->lastentry) != 0) {
407 if (oge->type == GE_MOVE) { /* just eat up the first move */
410 } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
411 fprintf(stderr, "Glyph %s: MOVE in middle of path\n", g->name);
415 nge = newgentry(GEF_FLOAT);
427 nge = newgentry(GEF_FLOAT);
431 nge->bkwd = (GENTRY*)&g->entries;
432 g->entries = g->lastentry = nge;
435 if (0 && ISDBG(BUILDG))
436 dumppaths(g, NULL, NULL);
448 fprintf(stderr, "%s: i rmoveto(%d, %d)\n", g->name, x, y);
450 assertisint(g, "adding int MOVE");
452 if ((oge = g->lastentry) != 0) {
453 if (oge->type == GE_MOVE) { /* just eat up the first move */
456 } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
457 fprintf(stderr, "Glyph %s: MOVE in middle of path, ignored\n", g->name);
477 nge->bkwd = (GENTRY*)&g->entries;
478 g->entries = g->lastentry = nge;
492 fprintf(stderr, "%s: f rlineto(%g, %g)\n", g->name, x, y);
494 assertisfloat(g, "adding float LINE");
496 nge = newgentry(GEF_FLOAT);
501 if ((oge = g->lastentry) != 0) {
502 if (x == oge->fx3 && y == oge->fy3) { /* empty line */
503 /* ignore it or we will get in troubles later */
509 nge->bkwd = nge->frwd = nge;
521 WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
525 if (0 && ISDBG(BUILDG))
526 dumppaths(g, NULL, NULL);
538 fprintf(stderr, "%s: i rlineto(%d, %d)\n", g->name, x, y);
540 assertisint(g, "adding int LINE");
547 if ((oge = g->lastentry) != 0) {
548 if (x == oge->ix3 && y == oge->iy3) { /* empty line */
549 /* ignore it or we will get in troubles later */
555 nge->bkwd = nge->frwd = nge;
567 WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
588 fprintf(stderr, "%s: f rrcurveto(%g, %g, %g, %g, %g, %g)\n"
589 ,g->name, x1, y1, x2, y2, x3, y3);
591 assertisfloat(g, "adding float CURVE");
593 if (oge && oge->fx3 == x1 && x1 == x2 && x2 == x3) /* check if it's
595 fg_rlineto(g, x1, y3);
596 else if (oge && oge->fy3 == y1 && y1 == y2 && y2 == y3)
597 fg_rlineto(g, x3, y1);
599 nge = newgentry(GEF_FLOAT);
600 nge->type = GE_CURVE;
609 if (x3 == oge->fx3 && y3 == oge->fy3) {
610 free(nge); /* consider this curve empty */
611 /* ignore it or we will get in troubles later */
616 nge->bkwd = nge->frwd = nge;
628 WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
633 if (0 && ISDBG(BUILDG))
634 dumppaths(g, NULL, NULL);
652 fprintf(stderr, "%s: i rrcurveto(%d, %d, %d, %d, %d, %d)\n"
653 ,g->name, x1, y1, x2, y2, x3, y3);
655 assertisint(g, "adding int CURVE");
657 if (oge && oge->ix3 == x1 && x1 == x2 && x2 == x3) /* check if it's
659 ig_rlineto(g, x1, y3);
660 else if (oge && oge->iy3 == y1 && y1 == y2 && y2 == y3)
661 ig_rlineto(g, x3, y1);
664 nge->type = GE_CURVE;
673 if (x3 == oge->ix3 && y3 == oge->iy3) {
674 free(nge); /* consider this curve empty */
675 /* ignore it or we will get in troubles later */
680 nge->bkwd = nge->frwd = nge;
692 WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
706 fprintf(stderr, "%s: closepath\n", g->name);
711 WARNING_1 fprintf(stderr, "Warning: **** closepath on empty path in glyph \"%s\" ****\n",
714 WARNING_1 fprintf(stderr, "No previois entry\n");
716 WARNING_1 fprintf(stderr, "Previous entry type: %c\n", oge->type);
717 if (oge->type == GE_MOVE) {
718 g->lastentry = oge->prev;
722 g->lastentry->next = 0;
729 nge = newgentry(oge->flags & GEF_FLOAT); /* keep the same type */
738 if (0 && ISDBG(BUILDG))
739 dumppaths(g, NULL, NULL);
743 * * SB * Routines to smooth and fix the glyphs
747 ** we don't want to see the curves with coinciding middle and
757 int x0, y0, x1, y1, x2, y2, x3, y3;
759 if (ge->type != GE_CURVE)
762 if(ge->flags & GEF_FLOAT) {
763 fprintf(stderr, "**! fixcvends(0x%x) on floating entry, ABORT\n", ge);
764 abort(); /* dump core */
777 /* look at the start of the curve */
778 if (x1 == x0 && y1 == y0) {
782 if (dx == 0 && dy == 0
783 || x2 == x3 && y2 == y3) {
784 /* Oops, we actually have a straight line */
786 * if it's small, we hope that it will get optimized
789 if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
794 } else {/* just make it a line */
798 if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very
802 } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */
809 /* make sure that it's still on the same side */
810 if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
811 if (abs(x3 - x0) * abs(ge->iy1 - y0) > abs(y3 - y0) * abs(ge->ix1 - x0))
812 ge->ix1 += isign(dx);
814 if (abs(x3 - x0) * abs(ge->iy1 - y0) < abs(y3 - y0) * abs(ge->ix1 - x0))
815 ge->iy1 += isign(dy);
818 ge->ix2 += (x3 - x2) / 8;
819 ge->iy2 += (y3 - y2) / 8;
820 /* make sure that it's still on the same side */
821 if (abs(x3 - x0) * abs(y3 - y2) < abs(y3 - y0) * abs(x3 - x2)) {
822 if (abs(x3 - x0) * abs(y3 - ge->iy2) > abs(y3 - y0) * abs(x3 - ge->ix2))
823 ge->iy1 -= isign(y3 - y2);
825 if (abs(x3 - x0) * abs(y3 - ge->iy2) < abs(y3 - y0) * abs(x3 - ge->ix2))
826 ge->ix1 -= isign(x3 - x2);
830 } else if (x2 == x3 && y2 == y3) {
834 if (dx == 0 && dy == 0) {
835 /* Oops, we actually have a straight line */
837 * if it's small, we hope that it will get optimized
840 if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
845 } else {/* just make it a line */
849 if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very
853 } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */
860 /* make sure that it's still on the same side */
861 if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
862 if (abs(x3 - x0) * abs(ge->iy2 - y3) > abs(y3 - y0) * abs(ge->ix2 - x3))
863 ge->ix2 += isign(dx);
865 if (abs(x3 - x0) * abs(ge->iy2 - y3) < abs(y3 - y0) * abs(ge->ix2 - x3))
866 ge->iy2 += isign(dy);
869 ge->ix1 += (x0 - x1) / 8;
870 ge->iy1 += (y0 - y1) / 8;
871 /* make sure that it's still on the same side */
872 if (abs(x3 - x0) * abs(y0 - y1) < abs(y3 - y0) * abs(x0 - x1)) {
873 if (abs(x3 - x0) * abs(y0 - ge->iy1) > abs(y3 - y0) * abs(x0 - ge->ix1))
874 ge->iy1 -= isign(y0 - y1);
876 if (abs(x3 - x0) * abs(y0 - ge->iy1) < abs(y3 - y0) * abs(x0 - ge->ix1))
877 ge->ix1 -= isign(x0 - x1);
885 ** After transformations we want to make sure that the resulting
886 ** curve is going in the same quadrant as the original one,
887 ** because rounding errors introduced during transformations
888 ** may make the result completeley wrong.
890 ** `dir' argument describes the direction of the original curve,
891 ** it is the superposition of two values for the front and
892 ** rear ends of curve:
894 ** >EQUAL - goes over the line connecting the ends
895 ** =EQUAL - coincides with the line connecting the ends
896 ** <EQUAL - goes under the line connecting the ends
898 ** See CVDIR_* for exact definitions.
912 if(ge->flags & GEF_FLOAT) {
913 fprintf(stderr, "**! fixcvdir(0x%x) on floating entry, ABORT\n", ge);
914 abort(); /* dump core */
917 fdir = (dir & CVDIR_FRONT) - CVDIR_FEQUAL;
918 if ((dir & CVDIR_REAR) == CVDIR_RSAME)
919 rdir = fdir; /* we need only isign, exact value doesn't matter */
921 rdir = (dir & CVDIR_REAR) - CVDIR_REQUAL;
925 c = isign(ge->ix3 - ge->prev->ix3); /* note the direction of
927 d = isign(ge->iy3 - ge->prev->iy3);
929 a = ge->iy3 - ge->prev->iy3;
930 b = ge->ix3 - ge->prev->ix3;
931 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
932 a = ge->iy1 - ge->prev->iy3;
933 b = ge->ix1 - ge->prev->ix3;
934 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
935 a = ge->iy3 - ge->iy2;
936 b = ge->ix3 - ge->ix2;
937 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
941 if (ISDBG(FIXCVDIR)) {
943 fprintf(stderr, "fixcvdir %d %d (%d %d %d %d %d %d) %f %f %f\n",
945 ge->ix1 - ge->prev->ix3,
946 ge->iy1 - ge->prev->iy3,
956 if (kk1 > kk) { /* the front end has problems */
957 if (c * (ge->ix1 - ge->prev->ix3) > 0) {
960 } if (d * (ge->iy2 - ge->iy1) > 0) {
964 /* recalculate the coefficients */
965 a = ge->iy3 - ge->prev->iy3;
966 b = ge->ix3 - ge->prev->ix3;
967 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
968 a = ge->iy1 - ge->prev->iy3;
969 b = ge->ix1 - ge->prev->ix3;
970 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
972 } else if (fdir < 0) {
973 if (kk1 < kk) { /* the front end has problems */
974 if (c * (ge->ix2 - ge->ix1) > 0) {
977 } if (d * (ge->iy1 - ge->prev->iy3) > 0) {
981 /* recalculate the coefficients */
982 a = ge->iy1 - ge->prev->iy3;
983 b = ge->ix1 - ge->prev->ix3;
984 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
985 a = ge->iy3 - ge->prev->iy3;
986 b = ge->ix3 - ge->prev->ix3;
987 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
991 if (kk2 < kk) { /* the rear end has problems */
992 if (c * (ge->ix2 - ge->ix1) > 0) {
995 } if (d * (ge->iy3 - ge->iy2) > 0) {
999 /* recalculate the coefficients */
1000 a = ge->iy3 - ge->prev->iy3;
1001 b = ge->ix3 - ge->prev->ix3;
1002 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1003 a = ge->iy3 - ge->iy2;
1004 b = ge->ix3 - ge->ix2;
1005 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1007 } else if (rdir < 0) {
1008 if (kk2 > kk) { /* the rear end has problems */
1009 if (c * (ge->ix3 - ge->ix2) > 0) {
1012 } if (d * (ge->iy2 - ge->iy1) > 0) {
1016 /* recalculate the coefficients */
1017 a = ge->iy3 - ge->prev->iy3;
1018 b = ge->ix3 - ge->prev->ix3;
1019 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1020 a = ge->iy3 - ge->iy2;
1021 b = ge->ix3 - ge->ix2;
1022 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
1029 /* Get the directions of ends of curve for further usage */
1031 /* expects that the previous element is also float */
1042 if( !(ge->flags & GEF_FLOAT) ) {
1043 fprintf(stderr, "**! fgetcvdir(0x%x) on int entry, ABORT\n", ge);
1044 abort(); /* dump core */
1047 a = fabs(ge->fy3 - ge->prev->fy3);
1048 b = fabs(ge->fx3 - ge->prev->fx3);
1049 k = a < FEPS ? (b < FEPS ? 1. : 100000.) : ( b / a);
1051 a = fabs(ge->fy1 - ge->prev->fy3);
1052 b = fabs(ge->fx1 - ge->prev->fx3);
1055 a = fabs(ge->fy2 - ge->prev->fy3);
1056 b = fabs(ge->fx2 - ge->prev->fx3);
1057 k1 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a);
1063 a = fabs(ge->fy3 - ge->fy2);
1064 b = fabs(ge->fx3 - ge->fx2);
1067 a = fabs(ge->fy3 - ge->fy1);
1068 b = fabs(ge->fx3 - ge->fx1);
1069 k2 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a);
1075 if(fabs(k1-k) < 0.0001)
1076 dir |= CVDIR_FEQUAL;
1082 if(fabs(k2-k) < 0.0001)
1083 dir |= CVDIR_REQUAL;
1093 /* expects that the previous element is also int */
1104 if(ge->flags & GEF_FLOAT) {
1105 fprintf(stderr, "**! igetcvdir(0x%x) on floating entry, ABORT\n", ge);
1106 abort(); /* dump core */
1109 a = ge->iy3 - ge->prev->iy3;
1110 b = ge->ix3 - ge->prev->ix3;
1111 k = (a == 0) ? (b == 0 ? 1. : 100000.) : fabs((double) b / (double) a);
1113 a = ge->iy1 - ge->prev->iy3;
1114 b = ge->ix1 - ge->prev->ix3;
1117 a = ge->iy2 - ge->prev->iy3;
1118 b = ge->ix2 - ge->prev->ix3;
1119 k1 = (a == 0) ? (b == 0 ? k : 100000.) : fabs((double) b / (double) a);
1123 k1 = fabs((double) b / (double) a);
1125 a = ge->iy3 - ge->iy2;
1126 b = ge->ix3 - ge->ix2;
1129 a = ge->iy3 - ge->iy1;
1130 b = ge->ix3 - ge->ix1;
1131 k2 = (a == 0) ? (b == 0 ? k : 100000.) : fabs((double) b / (double) a);
1135 k2 = fabs((double) b / (double) a);
1137 if(fabs(k1-k) < 0.0001)
1138 dir |= CVDIR_FEQUAL;
1144 if(fabs(k2-k) < 0.0001)
1145 dir |= CVDIR_REQUAL;
1155 /* a function just to test the work of fixcvdir() */
1164 for (ge = g->entries; ge != 0; ge = ge->next) {
1165 if (ge->type == GE_CURVE) {
1166 dir = igetcvdir(ge);
1178 return (int) (val > 0 ? val + 0.5 : val - 0.5);
1181 /* for debugging - dump the glyph
1182 * mark with a star the entries from start to end inclusive
1183 * (start == NULL means don't mark any, end == NULL means to the last)
1197 fprintf(stderr, "Glyph %s:\n", g->name);
1199 /* now do the conversion */
1200 for(ge = g->entries; ge != 0; ge = ge->next) {
1203 fprintf(stderr, " %c %8x", mark, ge);
1207 if(ge->flags & GEF_FLOAT)
1208 fprintf(stderr," %c float (%g, %g)\n", ge->type, ge->fx3, ge->fy3);
1210 fprintf(stderr," %c int (%d, %d)\n", ge->type, ge->ix3, ge->iy3);
1213 if(ge->flags & GEF_FLOAT) {
1214 fprintf(stderr," C float ");
1216 fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
1217 fprintf(stderr,"\n");
1219 fprintf(stderr," C int ");
1221 fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1222 fprintf(stderr,"\n");
1226 fprintf(stderr, " %c\n", ge->type);
1235 * Routine that converts all entries in the path from float to int
1249 fprintf(stderr, "TOINT: glyph %s\n", g->name);
1250 assertisfloat(g, "converting path to int\n");
1252 fdelsmall(g, 1.0); /* get rid of sub-pixel contours */
1253 assertpath(g->entries, __FILE__, __LINE__, g->name);
1255 /* 1st pass, collect the directions of the curves: have
1256 * to do that in advance, while everyting is float
1258 for(ge = g->entries; ge != 0; ge = ge->next) {
1259 if( !(ge->flags & GEF_FLOAT) ) {
1260 fprintf(stderr, "**! glyphs %s has int entry, found in conversion to int\n",
1264 if(ge->type == GE_CURVE) {
1265 ge->dir = fgetcvdir(ge);
1269 /* now do the conversion */
1270 for(ge = g->entries; ge != 0; ge = ge->next) {
1275 fprintf(stderr," %c float x=%g y=%g\n", ge->type, ge->fx3, ge->fy3);
1276 x[0] = iround(ge->fx3);
1277 y[0] = iround(ge->fy3);
1278 for(i=0; i<3; i++) { /* put some valid values everywhere, for convenience */
1283 fprintf(stderr," int x=%d y=%d\n", ge->ix3, ge->iy3);
1287 fprintf(stderr," %c float ", ge->type);
1289 for(i=0; i<3; i++) {
1291 fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
1292 x[i] = iround(ge->fxn[i]);
1293 y[i] = iround(ge->fyn[i]);
1297 fprintf(stderr,"\n int ");
1299 for(i=0; i<3; i++) {
1303 fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1305 ge->flags &= ~GEF_FLOAT; /* for fixcvdir */
1306 fixcvdir(ge, ge->dir);
1309 fprintf(stderr,"\n fixed ");
1311 fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1312 fprintf(stderr,"\n");
1317 ge->flags &= ~GEF_FLOAT;
1319 g->flags &= ~GF_FLOAT;
1323 /* check whether we can fix up the curve to change its size by (dx,dy) */
1324 /* 0 means NO, 1 means YES */
1326 /* for float: if scaling would be under 10% */
1335 if( !(ge->flags & GEF_FLOAT) ) {
1336 fprintf(stderr, "**! fcheckcv(0x%x) on int entry, ABORT\n", ge);
1337 abort(); /* dump core */
1340 if (ge->type != GE_CURVE)
1343 if( fabs(ge->fx3 - ge->prev->fx3) < fabs(dx) * 10 )
1346 if( fabs(ge->fy3 - ge->prev->fy3) < fabs(dy) * 10 )
1352 /* for int: if won't create new zigzags at the ends */
1363 if(ge->flags & GEF_FLOAT) {
1364 fprintf(stderr, "**! icheckcv(0x%x) on floating entry, ABORT\n", ge);
1365 abort(); /* dump core */
1368 if (ge->type != GE_CURVE)
1371 xdep = ge->ix3 - ge->prev->ix3;
1372 ydep = ge->iy3 - ge->prev->iy3;
1374 if (ge->type == GE_CURVE
1375 && (xdep * (xdep + dx)) > 0
1376 && (ydep * (ydep + dy)) > 0) {
1382 /* float connect the ends of open contours */
1389 GENTRY *ge, *fge, *xge, *nge;
1392 assertisfloat(g, "fclosepaths float\n");
1394 for (xge = g->entries; xge != 0; xge = xge->next) {
1395 if( xge->type != GE_PATH )
1399 if(ge == 0 || ge->type != GE_LINE && ge->type!= GE_CURVE) {
1400 fprintf(stderr, "**! Glyph %s got empty path\n",
1406 if (fge->prev == 0 || fge->prev->type != GE_MOVE) {
1407 fprintf(stderr, "**! Glyph %s got strange beginning of path\n",
1412 if (fge->fx3 != ge->fx3 || fge->fy3 != ge->fy3) {
1413 /* we have to fix this open path */
1415 WARNING_4 fprintf(stderr, "Glyph %s got path open by dx=%g dy=%g\n",
1416 g->name, fge->fx3 - ge->fx3, fge->fy3 - ge->fy3);
1419 /* add a new line */
1420 nge = newgentry(GEF_FLOAT);
1422 nge->fx3 = fge->fx3;
1423 nge->fy3 = fge->fy3;
1424 nge->type = GE_LINE;
1426 addgeafter(ge, nge);
1428 if (fabs(ge->fx3 - fge->fx3) <= 2 && fabs(ge->fy3 - fge->fy3) <= 2) {
1430 * small change, try to get rid of the new entry
1435 for(i=0; i<2; i++) {
1436 df[i] = ge->fpoints[i][2] - fge->fpoints[i][2];
1437 df[i] = fclosegap(nge, nge, i, df[i], NULL);
1440 if(df[0] == 0. && df[1] == 0.) {
1441 /* closed gap successfully, remove the added entry */
1455 int dx1, dy1, dx2, dy2, k;
1458 return; /* this stuff seems to create problems */
1460 assertisint(g, "smoothjoints int");
1462 if (g->entries == 0) /* nothing to do */
1465 for (ge = g->entries->next; ge != 0; ge = ge->next) {
1469 * although there should be no one-line path * and any path
1470 * must end with CLOSEPATH, * nobody can say for sure
1473 if (ge == ne || ne == 0)
1476 /* now handle various joints */
1478 if (ge->type == GE_LINE && ne->type == GE_LINE) {
1479 dx1 = ge->ix3 - ge->prev->ix3;
1480 dy1 = ge->iy3 - ge->prev->iy3;
1481 dx2 = ne->ix3 - ge->ix3;
1482 dy2 = ne->iy3 - ge->iy3;
1484 /* check whether they have the same direction */
1485 /* and the same slope */
1486 /* then we can join them into one line */
1488 if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 && dx1 * dy2 == dy1 * dx2) {
1489 /* extend the previous line */
1493 /* and get rid of the next line */
1496 } else if (ge->type == GE_LINE && ne->type == GE_CURVE) {
1499 dx1 = ge->ix3 - ge->prev->ix3;
1500 dy1 = ge->iy3 - ge->prev->iy3;
1501 dx2 = ne->ix1 - ge->ix3;
1502 dy2 = ne->iy1 - ge->iy3;
1504 /* if the line is nearly horizontal and we can fix it */
1505 if (dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
1506 && icheckcv(ne, 0, -dy1)
1508 dir = igetcvdir(ne);
1513 ne->prev->iy3 -= dy1;
1515 } else if (dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1516 && icheckcv(ne, -dx1, 0)
1518 /* the same but vertical */
1519 dir = igetcvdir(ne);
1524 ne->prev->ix3 -= dx1;
1528 * if line is horizontal and curve begins nearly
1531 if (dy1 == 0 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0) {
1532 dir = igetcvdir(ne);
1536 } else if (dx1 == 0 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0) {
1537 /* the same but vertical */
1538 dir = igetcvdir(ne);
1543 } else if (ge->type == GE_CURVE && ne->type == GE_LINE) {
1546 dx1 = ge->ix3 - ge->ix2;
1547 dy1 = ge->iy3 - ge->iy2;
1548 dx2 = ne->ix3 - ge->ix3;
1549 dy2 = ne->iy3 - ge->iy3;
1551 /* if the line is nearly horizontal and we can fix it */
1552 if (dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
1553 && icheckcv(ge, 0, dy2)
1555 dir = igetcvdir(ge);
1560 ne->prev->iy3 += dy2;
1562 } else if (dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1563 && icheckcv(ge, dx2, 0)
1565 /* the same but vertical */
1566 dir = igetcvdir(ge);
1571 ne->prev->ix3 += dx2;
1575 * if line is horizontal and curve ends nearly
1578 if (dy2 == 0 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0) {
1579 dir = igetcvdir(ge);
1583 } else if (dx2 == 0 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0) {
1584 /* the same but vertical */
1585 dir = igetcvdir(ge);
1590 } else if (ge->type == GE_CURVE && ne->type == GE_CURVE) {
1594 dx1 = ge->ix3 - ge->ix2;
1595 dy1 = ge->iy3 - ge->iy2;
1596 dx2 = ne->ix1 - ge->ix3;
1597 dy2 = ne->iy1 - ge->iy3;
1600 * check if we have a rather smooth joint at extremal
1603 /* left or right extremal point */
1604 if (abs(dx1) <= 4 && abs(dx2) <= 4
1605 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1606 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1607 && (ge->iy3 < ge->prev->iy3 && ne->iy3 < ge->iy3
1608 || ge->iy3 > ge->prev->iy3 && ne->iy3 > ge->iy3)
1609 && (ge->ix3 - ge->prev->ix3) * (ne->ix3 - ge->ix3) < 0
1611 dir = igetcvdir(ge);
1615 dir = igetcvdir(ne);
1620 /* top or down extremal point */
1621 else if (abs(dy1) <= 4 && abs(dy2) <= 4
1622 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
1623 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
1624 && (ge->ix3 < ge->prev->ix3 && ne->ix3 < ge->ix3
1625 || ge->ix3 > ge->prev->ix3 && ne->ix3 > ge->ix3)
1626 && (ge->iy3 - ge->prev->iy3) * (ne->iy3 - ge->iy3) < 0
1628 dir = igetcvdir(ge);
1632 dir = igetcvdir(ne);
1637 /* or may be we just have a smooth junction */
1638 else if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0
1639 && 10 * abs(k = abs(dx1 * dy2) - abs(dy1 * dx2)) < (abs(dx1 * dy2) + abs(dy1 * dx2))) {
1644 /* build array of changes we are going to try */
1645 /* uninitalized entries are 0 */
1647 static int t1[6][4] = {
1654 memcpy(tries, t1, sizeof tries);
1656 static int t1[6][4] = {
1663 memcpy(tries, t1, sizeof tries);
1666 /* now try the changes */
1667 results[0] = abs(k);
1668 for (i = 1; i < 6; i++) {
1669 results[i] = abs((abs(dx1) + tries[i][0]) * (abs(dy2) + tries[i][1]) -
1670 (abs(dy1) + tries[i][2]) * (abs(dx2) + tries[i][3]));
1673 /* and find the best try */
1676 for (i = 1; i < 6; i++)
1677 if (results[i] < k) {
1681 /* and finally apply it */
1683 tries[b][0] = -tries[b][0];
1685 tries[b][1] = -tries[b][1];
1687 tries[b][2] = -tries[b][2];
1689 tries[b][3] = -tries[b][3];
1691 dir = igetcvdir(ge);
1692 ge->ix2 -= tries[b][0];
1693 ge->iy2 -= tries[b][2];
1695 dir = igetcvdir(ne);
1696 ne->ix1 += tries[b][3];
1697 ne->iy1 += tries[b][1];
1704 /* debugging: print out stems of a glyph */
1716 fprintf(pfa_file, "%% %s\n", name);
1717 fprintf(pfa_file, "%% %d horizontal stems:\n", nhs);
1718 for (i = 0; i < nhs; i++)
1719 fprintf(pfa_file, "%% %3d %d (%d...%d) %c %c%c%c%c\n", i, hstems[i].value,
1720 hstems[i].from, hstems[i].to,
1721 ((hstems[i].flags & ST_UP) ? 'U' : 'D'),
1722 ((hstems[i].flags & ST_END) ? 'E' : '-'),
1723 ((hstems[i].flags & ST_FLAT) ? 'F' : '-'),
1724 ((hstems[i].flags & ST_ZONE) ? 'Z' : ' '),
1725 ((hstems[i].flags & ST_TOPZONE) ? 'T' : ' '));
1726 fprintf(pfa_file, "%% %d vertical stems:\n", nvs);
1727 for (i = 0; i < nvs; i++)
1728 fprintf(pfa_file, "%% %3d %d (%d...%d) %c %c%c\n", i, vstems[i].value,
1729 vstems[i].from, vstems[i].to,
1730 ((vstems[i].flags & ST_UP) ? 'U' : 'D'),
1731 ((vstems[i].flags & ST_END) ? 'E' : '-'),
1732 ((vstems[i].flags & ST_FLAT) ? 'F' : '-'));
1735 /* add pseudo-stems for the limits of the Blue zones to the stem array */
1744 for(i=0; i<nblues && i<2; i+=2) { /* baseline */
1745 s[n].value=bluevalues[i];
1746 s[n].flags=ST_UP|ST_ZONE;
1747 /* don't overlap with anything */
1748 s[n].origin=s[n].from=s[n].to= -10000+i;
1750 s[n].value=bluevalues[i+1];
1752 /* don't overlap with anything */
1753 s[n].origin=s[n].from=s[n].to= -10000+i+1;
1756 for(i=2; i<nblues; i+=2) { /* top zones */
1757 s[n].value=bluevalues[i];
1758 s[n].flags=ST_UP|ST_ZONE|ST_TOPZONE;
1759 /* don't overlap with anything */
1760 s[n].origin=s[n].from=s[n].to= -10000+i;
1762 s[n].value=bluevalues[i+1];
1763 s[n].flags=ST_ZONE|ST_TOPZONE;
1764 /* don't overlap with anything */
1765 s[n].origin=s[n].from=s[n].to= -10000+i+1;
1768 for(i=0; i<notherb; i+=2) { /* bottom zones */
1769 s[n].value=otherblues[i];
1770 s[n].flags=ST_UP|ST_ZONE;
1771 /* don't overlap with anything */
1772 s[n].origin=s[n].from=s[n].to= -10000+i+nblues;
1774 s[n].value=otherblues[i+1];
1776 /* don't overlap with anything */
1777 s[n].origin=s[n].from=s[n].to= -10000+i+1+nblues;
1783 /* sort stems in array */
1794 /* a simple sorting */
1795 /* hm, the ordering criteria are not quite simple :-)
1796 * if the values are tied
1797 * ST_UP always goes under not ST_UP
1798 * ST_ZONE goes on the most outer side
1799 * ST_END goes towards inner side after ST_ZONE
1800 * ST_FLAT goes on the inner side
1803 for (i = 0; i < n; i++)
1804 for (j = i + 1; j < n; j++) {
1805 if(s[i].value < s[j].value)
1807 if(s[i].value == s[j].value) {
1808 if( (s[i].flags & ST_UP) < (s[j].flags & ST_UP) )
1810 if( (s[i].flags & ST_UP) == (s[j].flags & ST_UP) ) {
1811 if( s[i].flags & ST_UP ) {
1813 (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1815 (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1820 (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1822 (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1834 /* check whether two stem borders overlap */
1844 if (s1->from <= s2->from && s1->to >= s2->from
1845 || s2->from <= s1->from && s2->to >= s1->from)
1850 if (ISDBG(STEMOVERLAP))
1851 fprintf(pfa_file, "%% overlap %d(%d..%d)x%d(%d..%d)=%d\n",
1852 s1->value, s1->from, s1->to, s2->value, s2->from, s2->to, result);
1857 * check if the stem [border] is in an appropriate blue zone
1858 * (currently not used)
1869 if(s->flags & ST_UP) {
1870 /* painted size up, look at lower zones */
1871 if(nblues>=2 && val>=bluevalues[0] && val<=bluevalues[1] )
1873 for(i=0; i<notherb; i++) {
1874 if( val>=otherblues[i] && val<=otherblues[i+1] )
1878 /* painted side down, look at upper zones */
1879 for(i=2; i<nblues; i++) {
1880 if( val>=bluevalues[i] && val<=bluevalues[i+1] )
1888 /* mark the outermost stem [borders] in the blue zones */
1898 * traverse the list of Blue Values, mark the lowest upper
1899 * stem in each bottom zone and the topmost lower stem in
1900 * each top zone with ST_BLUE
1904 for(i=2; i<nblues; i+=2) {
1905 a=bluevalues[i]; b=bluevalues[i+1];
1906 if(ISDBG(BLUESTEMS))
1907 fprintf(pfa_file, "%% looking at blue zone %d...%d\n", a, b);
1908 for(j=nold-1; j>=0; j--) {
1909 if( s[j].flags & (ST_ZONE|ST_UP|ST_END) )
1912 if(c<a) /* too low */
1914 if(c<=b) { /* found the topmost stem border */
1915 /* mark all the stems with the same value */
1916 if(ISDBG(BLUESTEMS))
1917 fprintf(pfa_file, "%% found D BLUE at %d\n", s[j].value);
1918 /* include ST_END values */
1919 while( s[j+1].value==c && (s[j+1].flags & ST_ZONE)==0 )
1921 s[j].flags |= ST_BLUE;
1922 for(j--; j>=0 && s[j].value==c
1923 && (s[j].flags & (ST_UP|ST_ZONE))==0 ; j--)
1924 s[j].flags |= ST_BLUE;
1931 a=bluevalues[0]; b=bluevalues[1];
1932 for(j=0; j<nold; j++) {
1933 if( (s[j].flags & (ST_ZONE|ST_UP|ST_END))!=ST_UP )
1936 if(c>b) /* too high */
1938 if(c>=a) { /* found the lowest stem border */
1939 /* mark all the stems with the same value */
1940 if(ISDBG(BLUESTEMS))
1941 fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
1942 /* include ST_END values */
1943 while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
1945 s[j].flags |= ST_BLUE;
1946 for(j++; j<nold && s[j].value==c
1947 && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
1948 s[j].flags |= ST_BLUE;
1953 /* bottom zones: the logic is the same as for baseline */
1954 for(i=0; i<notherb; i+=2) {
1955 a=otherblues[i]; b=otherblues[i+1];
1956 for(j=0; j<nold; j++) {
1957 if( (s[j].flags & (ST_UP|ST_ZONE|ST_END))!=ST_UP )
1960 if(c>b) /* too high */
1962 if(c>=a) { /* found the lowest stem border */
1963 /* mark all the stems with the same value */
1964 if(ISDBG(BLUESTEMS))
1965 fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
1966 /* include ST_END values */
1967 while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
1969 s[j].flags |= ST_BLUE;
1970 for(j++; j<nold && s[j].value==c
1971 && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
1972 s[j].flags |= ST_BLUE;
1979 /* Eliminate invalid stems, join equivalent lines and remove nested stems
1980 * to build the main (non-substituted) set of stems.
1981 * XXX add consideration of the italic angle
1987 int useblues /* do we use the blue values ? */
1990 #define MAX_STACK 1000
1991 STEM stack[MAX_STACK];
1996 int a, b, c, w1, w2, w3;
1999 * priority of the last found stem:
2000 * 0 - nothing found yet
2001 * 1 - has ST_END in it (one or more)
2002 * 2 - has no ST_END and no ST_FLAT, can override only one stem
2004 * 3 - has no ST_END and at least one ST_FLAT, can override one
2005 * stem with priority 2 or any number of stems with priority 1
2006 * 4 (handled separately) - has ST_BLUE, can override anything
2010 int nlps = 0; /* number of non-committed
2011 * lowest-priority stems */
2014 for (i = 0, nnew = 0; i < nold; i++) {
2015 if (s[i].flags & (ST_UP|ST_ZONE)) {
2016 if(s[i].flags & ST_BLUE) {
2017 /* we just HAVE to use this value */
2022 /* remember the list of Blue zone stems with the same value */
2023 for(a=i, i++; i<nold && s[a].value==s[i].value
2024 && (s[i].flags & ST_BLUE); i++)
2026 b=i; /* our range is a <= i < b */
2027 c= -1; /* index of our best guess up to now */
2029 /* try to find a match, don't cross blue zones */
2030 for(; i<nold && (s[i].flags & ST_BLUE)==0; i++) {
2031 if(s[i].flags & ST_UP) {
2032 if(s[i].flags & ST_TOPZONE)
2037 for(j=a; j<b; j++) {
2038 if(!stemoverlap(&s[j], &s[i]) )
2040 /* consider priorities */
2041 if( ( (s[j].flags|s[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
2045 if( ((s[j].flags|s[i].flags) & ST_END)==0 ) {
2057 /* clean up the stack */
2062 if(c<0) { /* make one-dot-wide stem */
2063 if(nnew>=b) { /* have no free space */
2064 for(j=nold; j>=b; j--) /* make free space */
2070 s[nnew].flags &= ~(ST_UP|ST_BLUE);
2075 i=c; /* skip up to this point */
2077 if (ISDBG(MAINSTEMS))
2078 fprintf(pfa_file, "%% +stem %d...%d U BLUE\n",
2079 s[nnew-2].value, s[nnew-1].value);
2081 if (nstack >= MAX_STACK) {
2082 WARNING_1 fprintf(stderr, "Warning: **** converter's stem stack overflow ****\n");
2085 stack[nstack++] = s[i];
2087 } else if(s[i].flags & ST_BLUE) {
2088 /* again, we just HAVE to use this value */
2093 /* remember the list of Blue zone stems with the same value */
2094 for(a=i, i++; i<nold && s[a].value==s[i].value
2095 && (s[i].flags & ST_BLUE); i++)
2097 b=i; /* our range is a <= i < b */
2098 c= -1; /* index of our best guess up to now */
2100 /* try to find a match */
2101 for (i = nstack - 1; i >= 0; i--) {
2102 if( (stack[i].flags & ST_UP)==0 ) {
2103 if( (stack[i].flags & (ST_ZONE|ST_TOPZONE))==ST_ZONE )
2108 for(j=a; j<b; j++) {
2109 if(!stemoverlap(&s[j], &stack[i]) )
2111 /* consider priorities */
2112 if( ( (s[j].flags|stack[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
2116 if( ((s[j].flags|stack[i].flags) & ST_END)==0 ) {
2128 /* if found no match make a one-dot-wide stem */
2132 stack[0].flags |= ST_UP;
2133 stack[0].flags &= ~ST_BLUE;
2135 /* remove all the stems conflicting with this one */
2137 for(j=nnew-2; j>=0; j-=2) {
2138 if (ISDBG(MAINSTEMS))
2139 fprintf(pfa_file, "%% ?stem %d...%d -- %d\n",
2140 s[j].value, s[j+1].value, stack[c].value);
2141 if(s[j+1].value < stack[c].value) /* no conflict */
2143 if(s[j].flags & ST_BLUE) {
2144 /* oops, we don't want to spoil other blue zones */
2145 stack[c].value=s[j+1].value+1;
2148 if( (s[j].flags|s[j+1].flags) & ST_END ) {
2149 if (ISDBG(MAINSTEMS))
2150 fprintf(pfa_file, "%% -stem %d...%d p=1\n",
2151 s[j].value, s[j+1].value);
2152 continue; /* pri==1, silently discard it */
2154 /* we want to discard no nore than 2 stems of pri>=2 */
2155 if( ++readystem > 2 ) {
2156 /* change our stem to not conflict */
2157 stack[c].value=s[j+1].value+1;
2160 if (ISDBG(MAINSTEMS))
2161 fprintf(pfa_file, "%% -stem %d...%d p>=2\n",
2162 s[j].value, s[j+1].value);
2168 if(nnew>=b-1) { /* have no free space */
2169 for(j=nold; j>=b-1; j--) /* make free space */
2176 /* clean up the stack */
2179 /* set the next position to search */
2181 if (ISDBG(MAINSTEMS))
2182 fprintf(pfa_file, "%% +stem %d...%d D BLUE\n",
2183 s[nnew-2].value, s[nnew-1].value);
2184 } else if (nstack > 0) {
2187 * check whether our stem overlaps with anything in
2190 for (j = nstack - 1; j >= sbottom; j--) {
2191 if (s[i].value <= stack[j].value)
2193 if (stack[j].flags & ST_ZONE)
2196 if ((s[i].flags & ST_END)
2197 || (stack[j].flags & ST_END))
2199 else if ((s[i].flags & ST_FLAT)
2200 || (stack[j].flags & ST_FLAT))
2205 if (pri < readystem && s[nnew + 1].value >= stack[j].value
2206 || !stemoverlap(&stack[j], &s[i]))
2209 if (readystem > 1 && s[nnew + 1].value < stack[j].value) {
2215 * width of the previous stem (if it's
2218 w1 = s[nnew + 1].value - s[nnew].value;
2220 /* width of this stem */
2221 w2 = s[i].value - stack[j].value;
2223 if (readystem == 0) {
2224 /* nothing yet, just add a new stem */
2234 while (sbottom < nstack
2235 && stack[sbottom].value <= stack[j].value)
2238 if (ISDBG(MAINSTEMS))
2239 fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2240 stack[j].value, s[i].value, pri, nlps);
2241 } else if (pri == 1) {
2242 if (stack[j].value > s[nnew + 1].value) {
2244 * doesn't overlap with the
2251 if (ISDBG(MAINSTEMS))
2252 fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2253 stack[j].value, s[i].value, pri, nlps);
2254 } else if (w2 < w1) {
2258 if (ISDBG(MAINSTEMS))
2259 fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d %d->%d\n",
2260 stack[j].value, s[i].value, pri, nlps, w1, w2);
2262 } else if (pri == 2) {
2263 if (readystem == 2) {
2264 /* choose the narrower stem */
2269 if (ISDBG(MAINSTEMS))
2270 fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2271 stack[j].value, s[i].value, pri, nlps);
2273 /* else readystem==1 */
2274 } else if (stack[j].value > s[nnew + 1].value) {
2276 * value doesn't overlap with
2285 if (ISDBG(MAINSTEMS))
2286 fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2287 stack[j].value, s[i].value, pri, nlps);
2288 } else if (nlps == 1
2289 || stack[j].value > s[nnew - 1].value) {
2291 * we can replace the top
2299 if (ISDBG(MAINSTEMS))
2300 fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2301 stack[j].value, s[i].value, pri, nlps);
2303 } else if (readystem == 3) { /* that means also
2305 /* choose the narrower stem */
2310 while (sbottom < nstack
2311 && stack[sbottom].value <= stack[j].value)
2313 if (ISDBG(MAINSTEMS))
2314 fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
2315 stack[j].value, s[i].value, pri, nlps);
2317 } else if (pri == 3) {
2319 * we can replace as many stems as
2323 while (nnew > 0 && s[nnew - 1].value >= stack[j].value) {
2325 if (ISDBG(MAINSTEMS))
2326 fprintf(pfa_file, "%% -stem %d..%d\n",
2327 s[nnew].value, s[nnew + 1].value);
2334 while (sbottom < nstack
2335 && stack[sbottom].value <= stack[j].value)
2337 if (ISDBG(MAINSTEMS))
2338 fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
2339 stack[j].value, s[i].value, pri, nlps);
2347 /* change the 1-pixel-wide stems to 20-pixel-wide stems if possible
2348 * the constant 20 is recommended in the Type1 manual
2351 for(i=0; i<nnew; i+=2) {
2352 if(s[i].value != s[i+1].value)
2354 if( ((s[i].flags ^ s[i+1].flags) & ST_BLUE)==0 )
2356 if( s[i].flags & ST_BLUE ) {
2357 if(nnew>i+2 && s[i+2].value<s[i].value+22)
2358 s[i+1].value=s[i+2].value-2; /* compensate for fuzziness */
2362 if(i>0 && s[i-1].value>s[i].value-22)
2363 s[i].value=s[i-1].value+2; /* compensate for fuzziness */
2369 /* make sure that no stem it stretched between
2370 * a top zone and a bottom zone
2373 for(i=0; i<nnew; i+=2) {
2374 a=10000; /* lowest border of top zone crosing the stem */
2375 b= -10000; /* highest border of bottom zone crossing the stem */
2377 for(j=2; j<nblues; j++) {
2379 if( c>=s[i].value && c<=s[i+1].value && c<a )
2384 if( c>=s[i].value && c<=s[i+1].value && c>b )
2387 for(j=1; j<notherb; j++) {
2389 if( c>=s[i].value && c<=s[i+1].value && c>b )
2392 if( a!=10000 && b!= -10000 ) { /* it is stretched */
2393 /* split the stem into 2 ghost stems */
2394 for(j=nnew+1; j>i+1; j--) /* make free space */
2398 if(s[i].value+22 >= a)
2399 s[i+1].value=a-2; /* leave space for fuzziness */
2401 s[i+1].value=s[i].value+20;
2403 if(s[i+3].value-22 <= b)
2404 s[i+2].value=b+2; /* leave space for fuzziness */
2406 s[i+2].value=s[i+3].value-20;
2412 /* look for triple stems */
2413 for (i = 0; i < nnew; i += 2) {
2414 if (nnew - i >= 6) {
2415 a = s[i].value + s[i + 1].value;
2416 b = s[i + 2].value + s[i + 3].value;
2417 c = s[i + 4].value + s[i + 5].value;
2419 w1 = s[i + 1].value - s[i].value;
2420 w2 = s[i + 3].value - s[i + 2].value;
2421 w3 = s[i + 5].value - s[i + 4].value;
2423 fw = w3 - w1; /* fuzz in width */
2424 fd = ((c - b) - (b - a)); /* fuzz in distance
2427 /* we are able to handle some fuzz */
2429 * it doesn't hurt if the declared stem is a bit
2430 * narrower than actual unless it's an edge in
2433 if (abs(abs(fd) - abs(fw)) * 5 < w2
2434 && abs(fw) * 20 < (w1 + w3)) { /* width dirrerence <10% */
2436 if(useblues) { /* check that we don't disturb any blue stems */
2440 if( s[i+5].flags & ST_BLUE )
2444 if( s[i+4].flags & ST_BLUE )
2450 if( s[i+1].flags & ST_BLUE )
2454 if( s[i].flags & ST_BLUE )
2459 pri = ((j - b) - (b - k));
2462 if( s[i+2].flags & ST_BLUE )
2464 } else if(pri < 0) {
2465 if( s[i+3].flags & ST_BLUE )
2471 * first fix up the width of 1st and 3rd
2476 s[i + 5].value -= fw;
2479 s[i + 4].value += fw;
2484 s[i + 1].value -= fw;
2491 fd = ((c - b) - (b - a));
2494 s[i + 2].value += abs(fd) / 2;
2496 s[i + 3].value -= abs(fd) / 2;
2505 return (nnew & ~1); /* number of lines must be always even */
2509 * these macros and function allow to set the base stem,
2510 * check that it's not empty and subtract another stem
2511 * from the base stem (possibly dividing it into multiple parts)
2514 /* pairs for pieces of the base stem */
2515 static short xbstem[MAX_STEMS*2];
2516 /* index of the last point */
2517 static int xblast= -1;
2519 #define setbasestem(from, to) \
2520 (xbstem[0]=from, xbstem[1]=to, xblast=1)
2521 #define isbaseempty() (xblast<=0)
2523 /* returns 1 if was overlapping, 0 otherwise */
2536 /* handle the simple case simply */
2537 if(from > xbstem[xblast] || to < xbstem[0])
2540 /* the binary search may be more efficient */
2541 /* but for now the linear search is OK */
2542 for(b=1; from > xbstem[b]; b+=2) {} /* result: from <= xbstem[b] */
2543 for(a=xblast-1; to < xbstem[a]; a-=2) {} /* result: to >= xbstem[a] */
2545 /* now the interesting examples are:
2546 * (it was hard for me to understand, so I looked at the examples)
2548 * a|-----| |-----|b |-----| |-----|
2551 * a|-----|b |-----| |-----| |-----|
2554 * a|-----|b |-----| |-----| |-----|
2557 * |-----|b a|-----| |-----| |-----|
2560 * |-----| |-----|b |-----| a|-----|
2561 * f|-----------------------------|t
2563 * |-----|b |-----| |-----| a|-----|
2564 * f|--------------------------------------------------|t
2566 * |-----|b |-----| a|-----| |-----|
2567 * f|--------------------------|t
2570 if(a < b-1) /* hits a gap - example 1 */
2573 /* now the subtraction itself */
2575 if(a==b-1 && from > xbstem[a] && to < xbstem[b]) {
2576 /* overlaps with only one subrange and splits it - example 2 */
2577 j=xblast; i=(xblast+=2);
2579 xbstem[i--]=xbstem[j--];
2585 * a|b || |-----| |-----| |-----|
2590 if(xbstem[b-1] < from) {
2591 /* cuts the back of this subrange - examples 3, 4, 7 */
2596 * a|----| |-----|b |-----| |-----|
2599 * |---| a|-----|b |-----| |-----|
2602 * |---| |-----|b a|-----| |-----|
2603 * f|--------------------------|t
2607 if(xbstem[a+1] > to) {
2608 /* cuts the front of this subrange - examples 4a, 5, 7a */
2613 * a|---| |---|b |-----| |-----|
2616 * |-----| |-----|b a|-----| ||
2617 * f|-----------------------------|t
2619 * |---| a|-----|b || |-----|
2620 * f|--------------------------|t
2624 if(a < b-1) /* now after modification it hits a gap - examples 3a, 4b */
2625 return 1; /* because we have removed something */
2627 /* now remove the subranges completely covered by the new stem */
2628 /* examples 5b, 6, 7b */
2632 * |-----| |-----|b a|-----| ||
2633 * f|-----------------------------|t
2635 * |-----|b |-----| |-----| a|-----|
2636 * f|--------------------------------------------------|t
2638 * |---| a|-----|b || |-----|
2639 * f|--------------------------|t
2642 xbstem[i++]=xbstem[j++];
2654 for(i=0; i<xblast; i+=2)
2655 printf("%d-%d ", xbstem[i], xbstem[i+1]);
2656 printf(") %d\n", xblast);
2660 * Join the stem borders to build the sets of substituted stems
2661 * XXX add consideration of the italic angle
2668 int useblues /* do we use the blue values ? */
2672 static unsigned char mx[MAX_STEMS][MAX_STEMS];
2674 /* we do the substituted groups of stems first
2675 * and it looks like it's going to be REALLY SLOW
2676 * AND PAINFUL but let's bother about it later
2679 /* for the substituted stems we don't bother about [hv]stem3 -
2680 * anyway the X11R6 rasterizer does not bother about hstem3
2681 * at all and is able to handle only one global vstem3
2685 /* clean the used part of matrix */
2686 for(i=0; i<nold; i++)
2687 for(j=0; j<nold; j++)
2690 /* build the matrix of stem pairs */
2691 for(i=0; i<nold; i++) {
2692 if( s[i].flags & ST_ZONE )
2694 if(s[i].flags & ST_BLUE)
2695 mx[i][i]=1; /* allow to pair with itself if no better pair */
2696 if(s[i].flags & ST_UP) { /* the down-stems are already matched */
2697 setbasestem(s[i].from, s[i].to);
2698 for(j=i+1; j<nold; j++) {
2699 if(s[i].value==s[j].value
2700 || s[j].flags & ST_ZONE ) {
2703 x=subfrombase(s[j].from, s[j].to);
2705 if(s[j].flags & ST_UP) /* match only up+down pairs */
2708 mx[i][j]=mx[j][i]=x;
2710 if(isbaseempty()) /* nothing else to do */
2716 if(ISDBG(SUBSTEMS)) {
2717 fprintf(pfa_file, "%% ");
2718 for(j=0; j<nold; j++)
2719 putc( j%10==0 ? '0'+(j/10)%10 : ' ', pfa_file);
2720 fprintf(pfa_file, "\n%% ");
2721 for(j=0; j<nold; j++)
2722 putc('0'+j%10, pfa_file);
2723 putc('\n', pfa_file);
2724 for(i=0; i<nold; i++) {
2725 fprintf(pfa_file, "%% %3d ",i);
2726 for(j=0; j<nold; j++)
2727 putc( mx[i][j] ? 'X' : '.', pfa_file);
2728 putc('\n', pfa_file);
2732 /* now use the matrix to find the best pair for each stem */
2733 for(i=0; i<nold; i++) {
2734 int pri, lastpri, v, f;
2736 x= -1; /* best pair: none */
2748 for(j=i+1; j<nold; j++) {
2752 if( (f | s[j].flags) & ST_END )
2754 else if( (f | s[j].flags) & ST_FLAT )
2761 && ( lastpri==1 || s[j].value-v<20 || (s[x].value-v)*2 >= s[j].value-v ) ) {
2767 for(j=i-1; j>=0; j--) {
2771 if( (f | s[j].flags) & ST_END )
2773 else if( (f | s[j].flags) & ST_FLAT )
2780 && ( lastpri==1 || v-s[j].value<20 || (v-s[x].value)*2 >= v-s[j].value ) ) {
2786 if(x== -1 && mx[i][i])
2787 pairs[i]=i; /* a special case */
2792 if(ISDBG(SUBSTEMS)) {
2793 for(i=0; i<nold; i++) {
2796 fprintf(pfa_file, "%% %d...%d (%d x %d)\n", s[i].value, s[j].value, i, j);
2802 * Make all the stems originating at the same value get the
2803 * same width. Without this the rasterizer may move the dots
2804 * randomly up or down by one pixel, and that looks bad.
2805 * The prioritisation is the same as in findstemat().
2814 int i, j, from, to, val, dir;
2815 int pri, prevpri[2], wd, prevwd[2], prevbest[2];
2817 for(from=0; from<ns; from=to) {
2818 prevpri[0] = prevpri[1] = 0;
2819 prevwd[0] = prevwd[1] = 0;
2820 prevbest[0] = prevbest[1] = -1;
2821 val = s[from].value;
2823 for(to = from; to<ns && s[to].value == val; to++) {
2824 dir = ((s[to].flags & ST_UP)!=0);
2826 i=pairs[to]; /* the other side of this stem */
2828 continue; /* oops, no other side */
2829 wd=abs(s[i].value-val);
2833 if( (s[to].flags | s[i].flags) & ST_END )
2835 if( prevbest[dir] == -1 || pri > prevpri[dir] || wd<prevwd[dir] ) {
2842 for(i=from; i<to; i++) {
2843 dir = ((s[i].flags & ST_UP)!=0);
2844 if(prevbest[dir] >= 0) {
2845 if(ISDBG(SUBSTEMS)) {
2846 fprintf(stderr, "at %d (%s %d) pair %d->%d(%d)\n", i,
2847 (dir ? "UP":"DOWN"), s[i].value, pairs[i], prevbest[dir],
2848 s[prevbest[dir]].value);
2850 pairs[i] = prevbest[dir];
2857 * Find the best stem in the array at the specified (value, origin),
2858 * related to the entry ge.
2859 * Returns its index in the array sp, -1 means "none".
2860 * prevbest is the result for the other end of the line, we must
2861 * find something better than it or leave it as it is.
2871 int prevbest /* -1 means "none" */
2876 int pri, prevpri; /* priority, 0 = has ST_END, 1 = no ST_END */
2877 int wd, prevwd; /* stem width */
2879 si= -1; /* nothing yet */
2881 /* stems are ordered by value, binary search */
2882 min=0; max=ns; /* min <= i < max */
2883 while( min < max ) {
2891 si=i; /* temporary value */
2896 if( si < 0 ) /* found nothing this time */
2899 /* find the priority of the prevbest */
2900 /* we expect that prevbest has a pair */
2904 if( (sp[prevbest].flags | sp[i].flags) & ST_END )
2906 prevwd=abs(sp[i].value-value);
2909 /* stems are not ordered by origin, so now do the linear search */
2911 while( si>0 && sp[si-1].value==value ) /* find the first one */
2914 for(; si<ns && sp[si].value==value; si++) {
2915 if(sp[si].origin != origin)
2917 if(sp[si].ge != ge) {
2918 if(ISDBG(SUBSTEMS)) {
2920 "dbg: possible self-intersection at v=%d o=%d exp_ge=0x%x ge=0x%x\n",
2921 value, origin, ge, sp[si].ge);
2925 i=pairs[si]; /* the other side of this stem */
2927 continue; /* oops, no other side */
2929 if( (sp[si].flags | sp[i].flags) & ST_END )
2931 wd=abs(sp[i].value-value);
2932 if( prevbest == -1 || pri >prevpri
2933 || pri==prevpri && prevwd==0 || wd!=0 && wd<prevwd ) {
2944 /* add the substems for one glyph entry
2945 * (called from groupsubstems())
2946 * returns 0 if all OK, 1 if too many groups
2949 static int gssentry_lastgrp=0; /* reset to 0 for each new glyph */
2952 gssentry( /* crazy number of parameters */
2954 STEM *hs, /* horizontal stems, sorted by value */
2957 STEM *vs, /* vertical stems, sorted by value */
2963 int *nexthsi /* -2 means "check by yourself" */
2966 SI_VP, /* vertical primary */
2967 SI_HP, /* horizontal primary */
2968 SI_SIZE /* size of the array */
2970 int si[SI_SIZE]; /* indexes of relevant stems */
2972 /* the bounds of the existing relevant stems */
2973 STEMBOUNDS r[ sizeof(si) / sizeof(si[0]) * 2 ];
2974 char rexpand; /* by how much we need to expand the group */
2975 int nr; /* and the number of them */
2977 /* yet more temporary storage */
2978 short lb, hb, isvert;
2983 /* for each line or curve we try to find a horizontal and
2984 * a vertical stem corresponding to its first point
2985 * (corresponding to the last point of the previous
2986 * glyph entry), because the directions of the lines
2987 * will be eventually reversed and it will then become the last
2988 * point. And the T1 rasterizer applies the hints to
2993 /* start with the common part, the first point */
2998 si[SI_VP]=findstemat(x, y, ge, vs, vpairs, nvs, -1);
3000 si[SI_VP]= *nextvsi; *nextvsi= -2;
3003 si[SI_HP]=findstemat(y, x, ge, hs, hpairs, nhs, -1);
3005 si[SI_HP]= *nexthsi; *nexthsi= -2;
3009 * For the horizontal lines we make sure that both
3010 * ends of the line have the same horizontal stem,
3011 * and the same thing for vertical lines and stems.
3012 * In both cases we enforce the stem for the next entry.
3013 * Otherwise unpleasant effects may arise.
3016 if(ge->type==GE_LINE) {
3017 if(ge->ix3==x) { /* vertical line */
3018 *nextvsi=si[SI_VP]=findstemat(x, ge->iy3, ge->frwd, vs, vpairs, nvs, si[SI_VP]);
3019 } else if(ge->iy3==y) { /* horizontal line */
3020 *nexthsi=si[SI_HP]=findstemat(y, ge->ix3, ge->frwd, hs, hpairs, nhs, si[SI_HP]);
3024 if(si[SI_VP]+si[SI_HP] == -2) /* no stems, leave it alone */
3027 /* build the array of relevant bounds */
3029 for(i=0; i< sizeof(si) / sizeof(si[0]); i++) {
3034 int nzones, firstzone, binzone, einzone;
3041 r[nr].isvert=1; sp=vs; pairs=vpairs;
3043 r[nr].isvert=0; sp=hs; pairs=hpairs;
3046 r[nr].low=sp[ si[i] ].value;
3047 r[nr].high=sp[ pairs[ si[i] ] ].value;
3049 if(r[nr].low > r[nr].high) {
3050 j=r[nr].low; r[nr].low=r[nr].high; r[nr].high=j;
3056 /* handle the interaction with Blue Zones */
3058 if(i>=SI_HP) { /* only for horizontal stems */
3059 if(si[i]==pairs[si[i]]) {
3060 /* special case, the outermost stem in the
3061 * Blue Zone without a pair, simulate it to 20-pixel
3063 if(sp[ si[i] ].flags & ST_UP) {
3065 for(j=si[i]+1; j<nhs; j++)
3066 if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
3067 == (ST_ZONE|ST_TOPZONE) ) {
3068 if(r[nr].high > sp[j].value-2)
3069 r[nr].high=sp[j].value-2;
3074 for(j=si[i]-1; j>=0; j--)
3075 if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
3077 if(r[nr].low < sp[j].value+2)
3078 r[nr].low=sp[j].value+2;
3084 /* check that the stem borders don't end up in
3085 * different Blue Zones */
3086 f=sp[ si[i] ].flags;
3087 nzones=0; einzone=binzone=0;
3088 for(j=si[i]; j!=pairs[ si[i] ]; j+=step) {
3089 if( (sp[j].flags & ST_ZONE)==0 )
3091 /* if see a zone border going in the same direction */
3092 if( ((f ^ sp[j].flags) & ST_UP)==0 ) {
3093 if( ++nzones == 1 ) {
3094 firstzone=sp[j].value; /* remember the first one */
3095 etype=sp[j].flags & ST_TOPZONE;
3099 } else { /* the opposite direction */
3100 if(nzones==0) { /* beginning is in a blue zone */
3102 btype=sp[j].flags & ST_TOPZONE;
3108 /* beginning and end are in Blue Zones of different types */
3109 if( binzone && einzone && (btype ^ etype)!=0 ) {
3110 if( sp[si[i]].flags & ST_UP ) {
3111 if(firstzone > r[nr].low+22)
3112 r[nr].high=r[nr].low+20;
3114 r[nr].high=firstzone-2;
3116 if(firstzone < r[nr].high-22)
3117 r[nr].low=r[nr].high-20;
3119 r[nr].low=firstzone+2;
3125 fprintf(pfa_file, "%% at(%d,%d)[%d,%d] %d..%d %c (%d x %d)\n", x, y, i, nr,
3126 r[nr].low, r[nr].high, r[nr].isvert ? 'v' : 'h',
3127 si[i], pairs[si[i]]);
3132 /* now try to find a group */
3133 conflict=0; /* no conflicts found yet */
3137 /* check if it fits into the last group */
3138 grp = gssentry_lastgrp;
3139 i = (grp==0)? 0 : egp[grp-1];
3140 for(; i<egp[grp]; i++) {
3141 lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
3143 if( r[j].isvert==isvert /* intersects */
3144 && r[j].low <= hb && r[j].high >= lb ) {
3145 if( r[j].low == lb && r[j].high == hb ) /* coincides */
3155 if(conflict) { /* nope, check all the groups */
3159 for(i=0, grp=0; i<egp[NSTEMGRP-1]; i++) {
3160 if(i == egp[grp]) { /* checked all stems in a group */
3162 grp++; conflict=0; /* check the next group */
3166 break; /* insert into this group */
3169 lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
3171 if( r[j].isvert==isvert /* intersects */
3172 && r[j].low <= hb && r[j].high >= lb ) {
3173 if( r[j].low == lb && r[j].high == hb ) /* coincides */
3180 i=egp[grp]-1; /* fast forward to the next group */
3184 /* do we have any empty group ? */
3185 if(conflict && grp < NSTEMGRP-1) {
3191 if(conflict) { /* oops, can't find any group to fit */
3195 /* OK, add stems to this group */
3199 rexpand -= r[j].already;
3202 for(i=egp[NSTEMGRP-1]-1; i>=egp[grp]; i--)
3207 for(i=grp+1; i<NSTEMGRP; i++)
3211 ge->stemid = gssentry_lastgrp = grp;
3216 * Create the groups of substituted stems from the list.
3217 * Each group will be represented by a subroutine in the Subs
3224 STEM *hs, /* horizontal stems, sorted by value */
3227 STEM *vs, /* vertical stems, sorted by value */
3235 /* temporary storage */
3236 STEMBOUNDS s[MAX_STEMS*2];
3237 /* indexes in there, pointing past the end each stem group */
3238 short egp[NSTEMGRP];
3240 int nextvsi, nexthsi; /* -2 means "check by yourself" */
3242 for(i=0; i<NSTEMGRP; i++)
3245 nextvsi=nexthsi= -2; /* processed no horiz/vert line */
3247 gssentry_lastgrp = 0; /* reset the last group for new glyph */
3249 for (ge = g->entries; ge != 0; ge = ge->next) {
3250 if(ge->type!=GE_LINE && ge->type!=GE_CURVE) {
3251 nextvsi=nexthsi= -2; /* next path is independent */
3255 if( gssentry(ge, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
3256 WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
3258 /* it's better to have no substituted hints at all than have only part */
3259 for (ge = g->entries; ge != 0; ge = ge->next)
3261 g->nsg=0; /* just to be safe, already is 0 by initialization */
3266 * handle the last vert/horiz line of the path specially,
3267 * correct the hint for the first entry of the path
3269 if(ge->frwd != ge->next && (nextvsi != -2 || nexthsi != -2) ) {
3270 if( gssentry(ge->frwd, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
3271 WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
3273 /* it's better to have no substituted hints at all than have only part */
3274 for (ge = g->entries; ge != 0; ge = ge->next)
3276 g->nsg=0; /* just to be safe, already is 0 by initialization */
3283 /* find the index of the first empty group - same as the number of groups */
3285 for(i=1; i<NSTEMGRP && egp[i]!=egp[i-1]; i++)
3291 if(ISDBG(SUBSTEMS)) {
3292 fprintf(pfa_file, "%% %d substem groups (%d %d %d)\n", g->nsg,
3293 g->nsg>1 ? egp[g->nsg-2] : -1,
3294 g->nsg>0 ? egp[g->nsg-1] : -1,
3295 g->nsg<NSTEMGRP ? egp[g->nsg] : -1 );
3297 for(i=0; i<g->nsg; i++) {
3298 fprintf(pfa_file, "%% grp %3d: ", i);
3299 for(; j<egp[i]; j++) {
3300 fprintf(pfa_file, " %4d...%-4d %c ", s[j].low, s[j].high,
3301 s[j].isvert ? 'v' : 'h');
3303 fprintf(pfa_file, "\n");
3307 if(g->nsg==1) { /* it would be the same as the main stems */
3309 for (ge = g->entries; ge != 0; ge = ge->next)
3315 if( (g->nsbs=malloc(g->nsg * sizeof (egp[0]))) == 0 ) {
3316 fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3319 memmove(g->nsbs, egp, g->nsg * sizeof(short));
3320 if( (g->sbstems=malloc(egp[g->nsg-1] * sizeof (s[0]))) == 0 ) {
3321 fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3324 memmove(g->sbstems, s, egp[g->nsg-1] * sizeof(s[0]));
3333 STEM hs[MAX_STEMS], vs[MAX_STEMS]; /* temporary working
3335 short hs_pairs[MAX_STEMS], vs_pairs[MAX_STEMS]; /* best pairs for these stems */
3337 GENTRY *ge, *nge, *pge;
3340 int totals, grp, lastgrp;
3342 assertisint(g, "buildstems int");
3344 g->nhs = g->nvs = 0;
3345 memset(hs, 0, sizeof hs);
3346 memset(vs, 0, sizeof vs);
3348 /* first search the whole character for possible stem points */
3350 for (ge = g->entries; ge != 0; ge = ge->next) {
3351 if (ge->type == GE_CURVE) {
3355 * We consider the stems bound by the
3356 * H/V ends of the curves as flat ones.
3358 * But we don't include the point on the
3359 * other end into the range.
3362 /* first check the beginning of curve */
3363 /* if it is horizontal, add a hstem */
3364 if (ge->iy1 == ge->prev->iy3) {
3365 hs[g->nhs].value = ge->iy1;
3367 if (ge->ix1 < ge->prev->ix3)
3368 hs[g->nhs].flags = ST_FLAT | ST_UP;
3370 hs[g->nhs].flags = ST_FLAT;
3372 hs[g->nhs].origin = ge->prev->ix3;
3375 if (ge->ix1 < ge->prev->ix3) {
3376 hs[g->nhs].from = ge->ix1+1;
3377 hs[g->nhs].to = ge->prev->ix3;
3378 if(hs[g->nhs].from > hs[g->nhs].to)
3381 hs[g->nhs].from = ge->prev->ix3;
3382 hs[g->nhs].to = ge->ix1-1;
3383 if(hs[g->nhs].from > hs[g->nhs].to)
3386 if (ge->ix1 != ge->prev->ix3)
3389 /* if it is vertical, add a vstem */
3390 else if (ge->ix1 == ge->prev->ix3) {
3391 vs[g->nvs].value = ge->ix1;
3393 if (ge->iy1 > ge->prev->iy3)
3394 vs[g->nvs].flags = ST_FLAT | ST_UP;
3396 vs[g->nvs].flags = ST_FLAT;
3398 vs[g->nvs].origin = ge->prev->iy3;
3401 if (ge->iy1 < ge->prev->iy3) {
3402 vs[g->nvs].from = ge->iy1+1;
3403 vs[g->nvs].to = ge->prev->iy3;
3404 if(vs[g->nvs].from > vs[g->nvs].to)
3407 vs[g->nvs].from = ge->prev->iy3;
3408 vs[g->nvs].to = ge->iy1-1;
3409 if(vs[g->nvs].from > vs[g->nvs].to)
3413 if (ge->iy1 != ge->prev->iy3)
3416 /* then check the end of curve */
3417 /* if it is horizontal, add a hstem */
3418 if (ge->iy3 == ge->iy2) {
3419 hs[g->nhs].value = ge->iy3;
3421 if (ge->ix3 < ge->ix2)
3422 hs[g->nhs].flags = ST_FLAT | ST_UP;
3424 hs[g->nhs].flags = ST_FLAT;
3426 hs[g->nhs].origin = ge->ix3;
3427 hs[g->nhs].ge = ge->frwd;
3429 if (ge->ix3 < ge->ix2) {
3430 hs[g->nhs].from = ge->ix3;
3431 hs[g->nhs].to = ge->ix2-1;
3432 if( hs[g->nhs].from > hs[g->nhs].to )
3435 hs[g->nhs].from = ge->ix2+1;
3436 hs[g->nhs].to = ge->ix3;
3437 if( hs[g->nhs].from > hs[g->nhs].to )
3441 if (ge->ix3 != ge->ix2)
3444 /* if it is vertical, add a vstem */
3445 else if (ge->ix3 == ge->ix2) {
3446 vs[g->nvs].value = ge->ix3;
3448 if (ge->iy3 > ge->iy2)
3449 vs[g->nvs].flags = ST_FLAT | ST_UP;
3451 vs[g->nvs].flags = ST_FLAT;
3453 vs[g->nvs].origin = ge->iy3;
3454 vs[g->nvs].ge = ge->frwd;
3456 if (ge->iy3 < ge->iy2) {
3457 vs[g->nvs].from = ge->iy3;
3458 vs[g->nvs].to = ge->iy2-1;
3459 if( vs[g->nvs].from > vs[g->nvs].to )
3462 vs[g->nvs].from = ge->iy2+1;
3463 vs[g->nvs].to = ge->iy3;
3464 if( vs[g->nvs].from > vs[g->nvs].to )
3468 if (ge->iy3 != ge->iy2)
3473 * check the end of curve for a not smooth
3480 else if (nge->type == GE_LINE) {
3483 } else if (nge->type == GE_CURVE) {
3489 /* check for vertical extremums */
3490 if (ge->iy3 > ge->iy2 && ge->iy3 > ny
3491 || ge->iy3 < ge->iy2 && ge->iy3 < ny) {
3492 hs[g->nhs].value = ge->iy3;
3495 = hs[g->nhs].origin = ge->ix3;
3496 hs[g->nhs].ge = ge->frwd;
3498 if (ge->ix3 < ge->ix2
3500 hs[g->nhs].flags = ST_UP;
3502 hs[g->nhs].flags = 0;
3504 if (ge->ix3 != ge->ix2 || nx != ge->ix3)
3508 * the same point may be both horizontal and
3511 /* check for horizontal extremums */
3512 if (ge->ix3 > ge->ix2 && ge->ix3 > nx
3513 || ge->ix3 < ge->ix2 && ge->ix3 < nx) {
3514 vs[g->nvs].value = ge->ix3;
3517 = vs[g->nvs].origin = ge->iy3;
3518 vs[g->nvs].ge = ge->frwd;
3520 if (ge->iy3 > ge->iy2
3522 vs[g->nvs].flags = ST_UP;
3524 vs[g->nvs].flags = 0;
3526 if (ge->iy3 != ge->iy2 || ny != ge->iy3)
3531 } else if (ge->type == GE_LINE) {
3534 /* if it is horizontal, add a hstem */
3535 /* and the ends as vstems if they brace the line */
3536 if (ge->iy3 == ge->prev->iy3
3537 && ge->ix3 != ge->prev->ix3) {
3538 hs[g->nhs].value = ge->iy3;
3539 if (ge->ix3 < ge->prev->ix3) {
3540 hs[g->nhs].flags = ST_FLAT | ST_UP;
3541 hs[g->nhs].from = ge->ix3;
3542 hs[g->nhs].to = ge->prev->ix3;
3544 hs[g->nhs].flags = ST_FLAT;
3545 hs[g->nhs].from = ge->prev->ix3;
3546 hs[g->nhs].to = ge->ix3;
3548 hs[g->nhs].origin = ge->ix3;
3549 hs[g->nhs].ge = ge->frwd;
3553 /* add beginning as vstem */
3554 vs[g->nvs].value = pge->ix3;
3557 = vs[g->nvs].to = pge->iy3;
3560 if(pge->type==GE_CURVE)
3563 ovalue=pge->prev->iy3;
3565 if (pge->iy3 > ovalue)
3566 vs[g->nvs].flags = ST_UP | ST_END;
3567 else if (pge->iy3 < ovalue)
3568 vs[g->nvs].flags = ST_END;
3570 vs[g->nvs].flags = 0;
3572 if( vs[g->nvs].flags != 0 )
3575 /* add end as vstem */
3576 vs[g->nvs].value = ge->ix3;
3579 = vs[g->nvs].to = ge->iy3;
3580 vs[g->nvs].ge = ge->frwd;
3582 if(nge->type==GE_CURVE)
3587 if (ovalue > ge->iy3)
3588 vs[g->nvs].flags = ST_UP | ST_END;
3589 else if (ovalue < ge->iy3)
3590 vs[g->nvs].flags = ST_END;
3592 vs[g->nvs].flags = 0;
3594 if( vs[g->nvs].flags != 0 )
3599 /* if it is vertical, add a vstem */
3600 /* and the ends as hstems if they brace the line */
3601 else if (ge->ix3 == ge->prev->ix3
3602 && ge->iy3 != ge->prev->iy3) {
3603 vs[g->nvs].value = ge->ix3;
3604 if (ge->iy3 > ge->prev->iy3) {
3605 vs[g->nvs].flags = ST_FLAT | ST_UP;
3606 vs[g->nvs].from = ge->prev->iy3;
3607 vs[g->nvs].to = ge->iy3;
3609 vs[g->nvs].flags = ST_FLAT;
3610 vs[g->nvs].from = ge->iy3;
3611 vs[g->nvs].to = ge->prev->iy3;
3613 vs[g->nvs].origin = ge->iy3;
3614 vs[g->nvs].ge = ge->frwd;
3618 /* add beginning as hstem */
3619 hs[g->nhs].value = pge->iy3;
3622 = hs[g->nhs].to = pge->ix3;
3625 if(pge->type==GE_CURVE)
3628 ovalue=pge->prev->ix3;
3630 if (pge->ix3 < ovalue)
3631 hs[g->nhs].flags = ST_UP | ST_END;
3632 else if (pge->ix3 > ovalue)
3633 hs[g->nhs].flags = ST_END;
3635 hs[g->nhs].flags = 0;
3637 if( hs[g->nhs].flags != 0 )
3640 /* add end as hstem */
3641 hs[g->nhs].value = ge->iy3;
3644 = hs[g->nhs].to = ge->ix3;
3645 hs[g->nhs].ge = ge->frwd;
3647 if(nge->type==GE_CURVE)
3652 if (ovalue < ge->ix3)
3653 hs[g->nhs].flags = ST_UP | ST_END;
3654 else if (ovalue > ge->ix3)
3655 hs[g->nhs].flags = ST_END;
3657 hs[g->nhs].flags = 0;
3659 if( hs[g->nhs].flags != 0 )
3665 * check the end of line for a not smooth local
3672 else if (nge->type == GE_LINE) {
3675 } else if (nge->type == GE_CURVE) {
3681 /* check for vertical extremums */
3682 if (ge->iy3 > ge->prev->iy3 && ge->iy3 > ny
3683 || ge->iy3 < ge->prev->iy3 && ge->iy3 < ny) {
3684 hs[g->nhs].value = ge->iy3;
3687 = hs[g->nhs].origin = ge->ix3;
3688 hs[g->nhs].ge = ge->frwd;
3690 if (ge->ix3 < ge->prev->ix3
3692 hs[g->nhs].flags = ST_UP;
3694 hs[g->nhs].flags = 0;
3696 if (ge->ix3 != ge->prev->ix3 || nx != ge->ix3)
3700 * the same point may be both horizontal and vertical
3703 /* check for horizontal extremums */
3704 if (ge->ix3 > ge->prev->ix3 && ge->ix3 > nx
3705 || ge->ix3 < ge->prev->ix3 && ge->ix3 < nx) {
3706 vs[g->nvs].value = ge->ix3;
3709 = vs[g->nvs].origin = ge->iy3;
3710 vs[g->nvs].ge = ge->frwd;
3712 if (ge->iy3 > ge->prev->iy3
3714 vs[g->nvs].flags = ST_UP;
3716 vs[g->nvs].flags = 0;
3718 if (ge->iy3 != ge->prev->iy3 || ny != ge->iy3)
3724 g->nhs=addbluestems(hs, g->nhs);
3725 sortstems(hs, g->nhs);
3726 sortstems(vs, g->nvs);
3729 debugstems(g->name, hs, g->nhs, vs, g->nvs);
3731 /* find the stems interacting with the Blue Zones */
3732 markbluestems(hs, g->nhs);
3735 if (ISDBG(SUBSTEMS))
3736 fprintf(pfa_file, "%% %s: joining subst horizontal stems\n", g->name);
3737 joinsubstems(hs, hs_pairs, g->nhs, 1);
3738 uniformstems(hs, hs_pairs, g->nhs);
3740 if (ISDBG(SUBSTEMS))
3741 fprintf(pfa_file, "%% %s: joining subst vertical stems\n", g->name);
3742 joinsubstems(vs, vs_pairs, g->nvs, 0);
3744 groupsubstems(g, hs, hs_pairs, g->nhs, vs, vs_pairs, g->nvs);
3747 if (ISDBG(MAINSTEMS))
3748 fprintf(pfa_file, "%% %s: joining main horizontal stems\n", g->name);
3749 g->nhs = joinmainstems(hs, g->nhs, 1);
3750 if (ISDBG(MAINSTEMS))
3751 fprintf(pfa_file, "%% %s: joining main vertical stems\n", g->name);
3752 g->nvs = joinmainstems(vs, g->nvs, 0);
3754 if (ISDBG(MAINSTEMS))
3755 debugstems(g->name, hs, g->nhs, vs, g->nvs);
3758 if ((sp = malloc(sizeof(STEM) * g->nhs)) == 0) {
3759 fprintf(stderr, "**** not enough memory for hints ****\n");
3763 memcpy(sp, hs, sizeof(STEM) * g->nhs);
3768 if ((sp = malloc(sizeof(STEM) * g->nvs)) == 0) {
3769 fprintf(stderr, "**** not enough memory for hints ****\n");
3773 memcpy(sp, vs, sizeof(STEM) * g->nvs);
3777 /* now check that the stems won't overflow the interpreter's stem stack:
3778 * some interpreters (like X11) push the stems on each change into
3779 * stack and pop them only after the whole glyphs is completed.
3782 totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3785 for (ge = g->entries; ge != 0; ge = ge->next) {
3787 if(grp >= 0 && grp != lastgrp) {
3789 totals += g->nsbs[0];
3791 totals += g->nsbs[grp] - g->nsbs[grp-1];
3797 /* be on the safe side, check for >= , not > */
3798 if(totals >= max_stemdepth) { /* oops, too deep */
3800 fprintf(stderr, "Warning: glyph %s needs hint stack depth %d\n", g->name, totals);
3801 fprintf(stderr, " (limit %d): removed the substituted hints from it\n", max_stemdepth);
3804 for (ge = g->entries; ge != 0; ge = ge->next)
3806 free(g->sbstems); g->sbstems = 0;
3807 free(g->nsbs); g->nsbs = 0;
3812 /* now check if there are too many main stems */
3813 totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3814 if(totals >= max_stemdepth) {
3815 /* even worse, too much of non-substituted stems */
3817 fprintf(stderr, "Warning: glyph %s has %d main hints\n", g->name, totals);
3818 fprintf(stderr, " (limit %d): removed the hints from it\n", max_stemdepth);
3821 free(g->vstems); g->vstems = 0; g->nvs = 0;
3824 free(g->hstems); g->hstems = 0; g->nhs = 0;
3829 /* convert weird curves that are close to lines into lines.
3837 GENTRY *ge, *pge, *nge, *ige;
3843 for (ige = g->entries; ige != 0; ige = ige->next) {
3844 if (ige->type != GE_CURVE)
3853 /* look for vertical then horizontal */
3854 for(i=0; i<2; i++) {
3855 o = !i; /* other axis */
3857 iln = fabs(ge->fpoints[i][2] - pge->fpoints[i][2]);
3858 oln = fabs(ge->fpoints[o][2] - pge->fpoints[o][2]);
3860 * if current curve is almost a vertical line, and it
3861 * doesn't begin or end horizontally (and the prev/next
3862 * line doesn't join smoothly ?)
3865 || ge->fpoints[o][2] == ge->fpoints[o][1]
3866 || ge->fpoints[o][0] == pge->fpoints[o][2]
3868 || iln > 1. && iln/oln > 0.1 )
3872 if(ISDBG(STRAIGHTEN))
3873 fprintf(stderr,"** straighten almost %s\n", (i? "horizontal":"vertical"));
3875 df = ge->fpoints[i][2] - pge->fpoints[i][2];
3876 dir = fsign(ge->fpoints[o][2] - pge->fpoints[o][2]);
3880 * suck in all the sequence of such almost lines
3881 * going in the same direction but not deviating
3882 * too far from vertical
3884 iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3885 oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3887 while (fabs(df) <= 5 && nge->type == GE_CURVE
3888 && dir == fsign(oln) /* that also gives oln != 0 */
3890 && ( iln <= 1. || iln/fabs(oln) <= 0.1 ) ) {
3894 if(ISDBG(STRAIGHTEN))
3895 fprintf(stderr,"** straighten collapsing %s\n", (i? "horizontal":"vertical"));
3901 df = ge->fpoints[i][2] - pge->fpoints[i][2];
3903 iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3904 oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3907 /* now check what do we have as previous/next line */
3910 if( pge->type == GE_LINE && pge->fpoints[i][2] == pge->prev->fpoints[i][2]
3911 && fabs(pge->fpoints[o][2] != pge->prev->fpoints[o][2]) ) {
3912 if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with previous 0x%x 0x%x\n", pge, ge);
3913 /* join the previous line with current */
3917 ige = freethisge(ge)->prev; /* keep the iterator valid */
3925 if (nge->type == GE_LINE && nge->fpoints[i][2] == ge->fpoints[i][2]
3926 && fabs(nge->fpoints[o][2] != ge->fpoints[o][2]) ) {
3927 if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with next 0x%x 0x%x\n", ge, nge);
3928 /* join the next line with current */
3941 /* try to align the lines if neccessary */
3943 fclosegap(ge, ge, i, df, NULL);
3945 /* contour consists of only one line, get rid of it */
3946 ige = freethisge(ge); /* keep the iterator valid */
3947 if(ige == 0) /* this was the last contour */
3952 break; /* don't bother looking at the other axis */
3957 /* solve a square equation,
3958 * returns the number of solutions found, the solutions
3959 * are stored in res which should point to array of two doubles.
3960 * min and max limit the area for solutions
3976 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq(%g,%g,%g) [%g;%g]\n", a, b, c, min, max);
3978 if(fabs(a) < 0.000001) { /* if a linear equation */
3980 if(fabs(b) < 0.000001) /* not an equation at all */
3983 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: linear t=%g\n", res[0]);
3984 if(res[0] >= min && res[0] <= max)
3990 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: D=%g\n", D);
3997 res[0] = (-b+D) / (2*a);
3998 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t1=%g\n", res[0]);
3999 if(res[0] >= min && res[0] <= max)
4002 res[n] = (-b-D) / (2*a);
4003 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t2=%g\n", res[n]);
4004 if(res[n] >= min && res[n] <= max)
4007 /* return 2nd solution only if it's different enough */
4008 if(n==2 && fabs(res[0]-res[1])<0.000001)
4014 /* check that the curves don't cross quadrant boundary */
4018 Here we make sure that the curve does not continue past
4019 horizontal or vertical extremums. The horizontal points are
4020 explained, vertical points are by analogy.
4022 The horizontal points are where the derivative
4023 dy/dx is equal to 0. But the Bezier curves are defined by
4027 so finding this derivative is complicated.
4028 Also even if we find some point (x,y) splitting at this point
4029 is far not obvious. Fortunately we can use dy/dt = 0 instead,
4030 this gets to a rather simple square equation and splitting
4031 at a known value of t is simple.
4035 y = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3
4036 y = (-A+3*B-3*C+D)*t^3 + (3*A-6*B+3*C)*t^2 + (-3*A+3*B)*t + A
4037 dy/dt = 3*(-A+3*B-3*C+D)*t^2 + 2*(3*A-6*B+3*C)*t + (-3*A+3*B)
4046 int i, j, np, oldnp;
4047 double sp[5]; /* split points, last one empty */
4048 char dir[5]; /* for debugging, direction by which split happened */
4049 double a, b, *pts; /* points of a curve */
4051 for (ge = g->entries; ge != 0; ge = ge->next) {
4052 if (ge->type != GE_CURVE)
4056 np = 0; /* no split points yet */
4058 fprintf(stderr, "%s: trying 0x%x (%g %g) (%g %g) (%g %g) (%g %g)\n ", g->name,
4059 ge, ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
4062 for(i=0; i<2; i++) { /* first for x then for y */
4063 /* find the cooridnates of control points */
4064 a = ge->prev->fpoints[i][2];
4065 pts = &ge->fpoints[i][0];
4069 3.0*(-a + 3.0*pts[0] - 3.0*pts[1] + pts[2]),
4070 6.0*(a - 2.0*pts[0] + pts[1]),
4073 0.0, 1.0); /* XXX range is [0;1] */
4079 fprintf(stderr, "%s: 0x%x: %d pts(%c): ",
4080 g->name, ge, np-oldnp, i? 'y':'x');
4082 /* remove points that are too close to the ends
4083 * because hor/vert ends are permitted, also
4084 * if the split point is VERY close to the ends
4085 * but not exactly then just flatten it and check again.
4087 for(j = oldnp; j<np; j++) {
4090 fprintf(stderr, "%g ", sp[j]);
4091 if(sp[j] < 0.03) { /* front end of curve */
4092 if(ge->fpoints[i][0] != ge->prev->fpoints[i][2]) {
4093 ge->fpoints[i][0] = ge->prev->fpoints[i][2];
4094 if(ISDBG(QUAD)) fprintf(stderr, "flattened at front\n");
4097 if( ge->fpoints[i][1] != ge->fpoints[i][0]
4098 && fsign(ge->fpoints[i][2] - ge->fpoints[i][1])
4099 != fsign(ge->fpoints[i][1] - ge->fpoints[i][0]) ) {
4100 ge->fpoints[i][1] = ge->fpoints[i][0];
4101 if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at front\n");
4104 sp[j] = sp[j+1]; np--; j--;
4105 if(ISDBG(QUAD)) fprintf(stderr, "(front flat) ");
4106 } else if(sp[j] > 0.97) { /* rear end of curve */
4107 if(ge->fpoints[i][1] != ge->fpoints[i][2]) {
4108 ge->fpoints[i][1] = ge->fpoints[i][2];
4109 if(ISDBG(QUAD)) fprintf(stderr, "flattened at rear\n");
4112 if( ge->fpoints[i][0] != ge->fpoints[i][1]
4113 && fsign(ge->prev->fpoints[i][2] - ge->fpoints[i][0])
4114 != fsign(ge->fpoints[i][0] - ge->fpoints[i][1]) ) {
4115 ge->fpoints[i][0] = ge->fpoints[i][1];
4116 if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at rear\n");
4119 sp[j] = sp[j+1]; np--; j--;
4120 if(ISDBG(QUAD)) fprintf(stderr, "(rear flat) ");
4123 if(ISDBG(QUAD)) fprintf(stderr, "\n");
4126 if(np==0) /* no split points, leave it alone */
4130 fprintf(stderr, "%s: splitting 0x%x (%g %g) (%g %g) (%g %g) (%g %g) at %d points\n ", g->name,
4131 ge, ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
4132 ge->fx3, ge->fy3, np);
4134 fprintf(stderr, "%g(%c) ", sp[i], dir[i] ? 'y':'x');
4135 fprintf(stderr, "\n");
4138 /* sort the points ascending */
4140 for(j=i+1; j<np; j++)
4142 a = sp[i]; sp[i] = sp[j]; sp[j] = a;
4145 /* now finally do the split on each point */
4146 for(j=0; j<np; j++) {
4152 if(ISDBG(QUAD)) fprintf(stderr, " 0x%x %g/%g\n", ge, k1, k2);
4154 nge = newgentry(GEF_FLOAT);
4157 #define SPLIT(pt1, pt2) ( (pt1) + k1*((pt2)-(pt1)) ) /* order is important! */
4158 for(i=0; i<2; i++) { /* for x and y */
4159 a = ge->fpoints[i][0]; /* get the middle points */
4160 b = ge->fpoints[i][1];
4162 /* calculate new internal points */
4165 ge->fpoints[i][0] = SPLIT(ge->prev->fpoints[i][2], a);
4166 ge->fpoints[i][1] = SPLIT(ge->fpoints[i][0], c);
4168 nge->fpoints[i][1] = SPLIT(b, nge->fpoints[i][2]);
4169 nge->fpoints[i][0] = SPLIT(c, nge->fpoints[i][1]);
4171 ge->fpoints[i][2] = SPLIT(ge->fpoints[i][1],
4172 + nge->fpoints[i][0]);
4176 addgeafter(ge, nge);
4178 /* go to the next part, adjust remaining points */
4180 for(i=j+1; i<np; i++)
4181 sp[i] = (sp[i]-k1) / k2;
4187 /* check if a curve is a zigzag */
4197 if (ge->type != GE_CURVE)
4200 a = ge->iy2 - ge->iy1;
4201 b = ge->ix2 - ge->ix1;
4208 k = fabs((double) b / (double) a);
4210 a = ge->iy1 - ge->prev->iy3;
4211 b = ge->ix1 - ge->prev->ix3;
4218 k1 = fabs((double) b / (double) a);
4220 a = ge->iy3 - ge->iy2;
4221 b = ge->ix3 - ge->ix2;
4228 k2 = fabs((double) b / (double) a);
4230 /* if the curve is not a zigzag */
4231 if (k1+0.0001 >= k && k2 <= k+0.0001 || k1 <= k+0.0001 && k2+0.0001 >= k)
4237 /* check if a curve is a zigzag - floating */
4247 if (ge->type != GE_CURVE)
4250 a = fabs(ge->fy2 - ge->fy1);
4251 b = fabs(ge->fx2 - ge->fx1);
4260 a = fabs(ge->fy1 - ge->prev->fy3);
4261 b = fabs(ge->fx1 - ge->prev->fx3);
4270 a = fabs(ge->fy3 - ge->fy2);
4271 b = fabs(ge->fx3 - ge->fx2);
4280 /* if the curve is not a zigzag */
4281 if (k1+0.0001 >= k && k2 <= k+0.0001 || k1 <= k+0.0001 && k2+0.0001 >= k)
4287 /* split the zigzag-like curves into two parts */
4297 assertisfloat(g, "splitting zigzags");
4298 for (ge = g->entries; ge != 0; ge = ge->next) {
4299 if (ge->type != GE_CURVE)
4302 /* if the curve is not a zigzag */
4303 if ( !fiszigzag(ge) ) {
4307 if(ISDBG(FCONCISE)) {
4308 double maxsc1, maxsc2;
4309 fprintf(stderr, "split a zigzag ");
4311 if( fcrossraysge(ge, ge, &maxsc1, &maxsc2, NULL) ) {
4312 fprintf(stderr, "sc1=%g sc2=%g\n", maxsc1, maxsc2);
4314 fprintf(stderr, "(rays don't cross)\n");
4317 /* split the curve by t=0.5 */
4318 nge = newgentry(GEF_FLOAT);
4320 nge->type = GE_CURVE;
4327 nge->fx2 = (c + d) / 2.;
4328 nge->fx1 = (b + 2. * c + d) / 4.;
4329 ge->fx3 = (a + b * 3. + c * 3. + d) / 8.;
4330 ge->fx2 = (a + 2. * b + c) / 4.;
4331 ge->fx1 = (a + b) / 2.;
4338 nge->fy2 = (c + d) / 2.;
4339 nge->fy1 = (b + 2. * c + d) / 4.;
4340 ge->fy3 = (a + b * 3. + c * 3. + d) / 8.;
4341 ge->fy2 = (a + 2. * b + c) / 4.;
4342 ge->fy1 = (a + b) / 2.;
4344 addgeafter(ge, nge);
4346 if(ISDBG(FCONCISE)) {
4347 dumppaths(g, ge, nge);
4352 /* free this GENTRY, returns what was ge->next
4353 * (ge must be of type GE_LINE or GE_CURVE)
4354 * works on both float and int entries
4364 if (ge->bkwd != ge->prev) {
4365 /* at beginning of the contour */
4368 if(xge == ge) { /* was the only line in contour */
4369 /* remove the contour completely */
4370 /* prev is GE_MOVE, next is GE_PATH, remove them all */
4372 /* may be the first contour, then ->bkwd points to ge->entries */
4373 if(ge->prev->prev == 0)
4374 *(GENTRY **)(ge->prev->bkwd) = ge->next->next;
4376 ge->prev->prev->next = ge->next->next;
4378 if(ge->next->next) {
4379 ge->next->next->prev = ge->prev->prev;
4380 ge->next->next->bkwd = ge->prev->bkwd;
4383 xge = ge->next->next;
4384 free(ge->prev); free(ge->next); free(ge);
4388 /* move the start point of the contour */
4389 if(ge->flags & GEF_FLOAT) {
4390 ge->prev->fx3 = xge->fx3;
4391 ge->prev->fy3 = xge->fy3;
4393 ge->prev->ix3 = xge->ix3;
4394 ge->prev->iy3 = xge->iy3;
4396 } else if(ge->frwd != ge->next) {
4397 /* at end of the contour */
4399 xge = ge->frwd->prev;
4400 /* move the start point of the contour */
4401 if(ge->flags & GEF_FLOAT) {
4402 xge->fx3 = ge->bkwd->fx3;
4403 xge->fy3 = ge->bkwd->fy3;
4405 xge->ix3 = ge->bkwd->ix3;
4406 xge->iy3 = ge->bkwd->iy3;
4410 ge->prev->next = ge->next;
4411 ge->next->prev = ge->prev;
4412 ge->bkwd->frwd = ge->frwd;
4413 ge->frwd->bkwd = ge->bkwd;
4420 /* inserts a new gentry (LINE or CURVE) after another (MOVE
4422 * corrects the first GE_MOVE if neccessary
4427 GENTRY *oge, /* after this */
4428 GENTRY *nge /* insert this */
4431 if(oge->type == GE_MOVE) {
4432 /* insert before next */
4433 if(oge->next->type == GE_PATH) {
4434 /* first and only GENTRY in path */
4435 nge->frwd = nge->bkwd = nge;
4437 nge->frwd = oge->next;
4438 nge->bkwd = oge->next->bkwd;
4439 oge->next->bkwd->frwd = nge;
4440 oge->next->bkwd = nge;
4443 nge->frwd = oge->frwd;
4445 oge->frwd->bkwd = nge;
4449 nge->next = oge->next;
4451 oge->next->prev = nge;
4454 if(nge->frwd->prev->type == GE_MOVE) {
4455 /* fix up the GE_MOVE entry */
4456 if(nge->flags & GEF_FLOAT) {
4457 nge->frwd->prev->fx3 = nge->fx3;
4458 nge->frwd->prev->fy3 = nge->fy3;
4460 nge->frwd->prev->ix3 = nge->ix3;
4461 nge->frwd->prev->iy3 = nge->iy3;
4467 * Check if this GENTRY happens to be at the end of path
4468 * and fix the first MOVETO accordingly
4469 * handles both int and float
4479 mge = ge->frwd->prev;
4480 if(mge->type == GE_MOVE) {
4481 if(ge->flags & GEF_FLOAT) {
4492 * This function adjusts the rest of path (the part from...to is NOT changed)
4493 * to cover the specified gap by the specified axis (0 - X, 1 - Y).
4494 * Gap is counted in direction (end_of_to - beginning_of_from).
4495 * Returns by how much the gap was not closed (0.0 if it was fully closed).
4496 * Ret contains by how much the first and last points of [from...to]
4497 * were moved to bring them in consistence to the rest of the path.
4498 * If ret==NULL then this info is not returned.
4510 #define TIMESLARGER 10. /* how many times larger must be a curve to not change too much */
4513 double times, limit, df, dx;
4515 GENTRY *xge, *pge, *nge, *bge[2];
4517 /* remember the old points to calculate ret */
4518 oldpos[0] = from->prev->fpoints[axis][2];
4519 oldpos[1] = to->fpoints[axis][2];
4521 rm[0] = rm[1] = gap / 2. ;
4523 bge[0] = from; /* this is convenient for iterations */
4526 /* first try to modify large curves but if have none then settle for small */
4527 for(times = (TIMESLARGER-1); times > 0.1; times /= 2. ) {
4529 if(rm[0]+rm[1] == 0.)
4532 /* iterate in both directions, backwards then forwards */
4533 for(j = 0; j<2; j++) {
4535 if(rm[j] == 0.) /* if this direction is exhausted */
4538 limit = fabs(rm[j]) * (1.+times);
4540 for(xge = bge[j]->cntr[j]; xge != bge[!j]; xge = xge->cntr[j]) {
4541 dx = xge->fpoints[axis][2] - xge->prev->fpoints[axis][2];
4542 df = fabs(dx) - limit;
4543 if( df <= FEPS ) /* curve is too small to change */
4546 if( df >= fabs(rm[j]) )
4549 df *= fsign(rm[j]); /* we may cover this part of rm */
4552 limit = fabs(rm[j]) * (1.+times);
4554 if(xge->type == GE_CURVE) { /* correct internal points */
4555 double scale = ((dx+df) / dx) - 1.;
4559 base = xge->fpoints[axis][2];
4561 base = xge->prev->fpoints[axis][2];
4563 for(k = 0; k<2; k++)
4564 xge->fpoints[axis][k] += scale *
4565 (xge->fpoints[axis][k] - base);
4568 /* move all the intermediate lines */
4570 df = -df; /* absolute direction */
4574 xge->fpoints[axis][2] += df;
4579 if(nge->type == GE_CURVE) {
4580 nge->fpoints[axis][0] +=df;
4581 nge->fpoints[axis][1] +=df;
4583 nge->fpoints[axis][2] += df;
4584 if(nge->next != nge->frwd) { /* last entry of contour */
4585 nge->frwd->prev->fpoints[axis][2] += df;
4587 nge = nge->cntr[!j];
4596 /* find the difference */
4597 oldpos[0] -= from->prev->fpoints[axis][2];
4598 oldpos[1] -= to->fpoints[axis][2];
4601 ret[0] = oldpos[0] - from->prev->fpoints[axis][2];
4602 ret[1] = oldpos[1] - to->fpoints[axis][2];
4606 if( rm[0]+rm[1] != gap - oldpos[1] + oldpos[0]) {
4607 fprintf(stderr, "** gap=%g rm[0]=%g rm[1]=%g o[0]=%g o[1]=%g rg=%g og=%g\n",
4608 gap, rm[0], rm[1], oldpos[0], oldpos[1], rm[0]+rm[1],
4609 gap - oldpos[1] + oldpos[0]);
4617 /* remove the lines or curves smaller or equal to the size limit */
4625 GENTRY *ge, *nge, *pge, *xge, *next;
4627 double dx, dy, d2, d2m;
4629 #define TIMESLARGER 10. /* how much larger must be a curve to not change too much */
4631 minlen2 = minlen*minlen;
4633 for (ge = g->entries; ge != 0; ge = next) {
4636 if (ge->type != GE_CURVE && ge->type != GE_LINE)
4640 for(i= (ge->type==GE_CURVE? 0: 2); i<3; i++) {
4641 dx = ge->fxn[i] - ge->prev->fx3;
4642 dy = ge->fyn[i] - ge->prev->fy3;
4648 if( d2m > minlen2 ) { /* line is not too small */
4649 /* XXX add more normalization here */
4653 /* if the line is too small */
4655 /* check forwards if we have a whole sequence of them */
4657 for(xge = ge->frwd; xge != ge; xge = xge->frwd) {
4659 for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
4660 dx = xge->fxn[i] - xge->prev->fx3;
4661 dy = xge->fyn[i] - xge->prev->fy3;
4666 if( d2m > minlen2 ) /* line is not too small */
4669 if(next == nge) /* move the next step past this sequence */
4673 /* check backwards if we have a whole sequence of them */
4675 for(xge = ge->bkwd; xge != ge; xge = xge->bkwd) {
4677 for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
4678 dx = xge->fxn[i] - xge->prev->fx3;
4679 dy = xge->fyn[i] - xge->prev->fy3;
4684 if( d2m > minlen2 ) /* line is not too small */
4689 /* now we have a sequence of small fragments in pge...nge (inclusive) */
4691 if(ISDBG(FCONCISE)) {
4692 fprintf(stderr, "glyph %s has very small fragments(%x..%x..%x)\n",
4693 g->name, pge, ge, nge);
4694 dumppaths(g, pge, nge);
4697 /* reduce whole sequence to one part and remember the middle point */
4702 pge->fx1 = pge->fx2 = pge->fx3;
4703 pge->fx3 = nge->fx3;
4704 pge->fy1 = pge->fy2 = pge->fy3;
4705 pge->fy3 = nge->fy3;
4706 pge->type = GE_CURVE;
4710 if(xge == nge->bkwd) {
4711 pge->fx1 = pge->fx2 = (pge->fx3+xge->fx3)/2.;
4712 pge->fx3 = nge->fx3;
4713 pge->fy1 = pge->fy2 = (pge->fy3+xge->fy3)/2.;
4714 pge->fy3 = nge->fy3;
4715 pge->type = GE_CURVE;
4720 freethisge(pge); pge = xge;
4721 xge = nge->bkwd; freethisge(nge); nge = xge;
4726 /* check if the whole sequence is small */
4727 dx = ge->fx3 - ge->prev->fx3;
4728 dy = ge->fy3 - ge->prev->fy3;
4731 if( d2 > minlen2 ) { /* no, it is not */
4734 WARNING_3 fprintf(stderr, "glyph %s had a sequence of fragments < %g points each, reduced to one curve\n",
4737 /* check that we did not create a monstrosity spanning quadrants */
4738 if(fsign(ge->fx1 - ge->prev->fx1) * fsign(ge->fx3 - ge->fx1) < 0
4739 || fsign(ge->fy1 - ge->prev->fy1) * fsign(ge->fy3 - ge->fy1) < 0 ) {
4740 /* yes, we did; are both parts of this thing big enough ? */
4741 dx = ge->fx1 - ge->prev->fx3;
4742 dy = ge->fy1 - ge->prev->fy3;
4745 dx = ge->fx3 - ge->fx1;
4746 dy = ge->fy3 - ge->fy1;
4747 d2m = dx*dx + dy*dy;
4749 if(d2 > minlen2 && d2m > minlen2) { /* make two straights */
4750 nge = newgentry(GEF_FLOAT);
4753 for(i=0; i<2; i++) {
4754 ge->fpoints[i][2] = ge->fpoints[i][0];
4755 b = nge->fpoints[i][0];
4756 d = nge->fpoints[i][2] - b;
4757 nge->fpoints[i][0] = b + 0.1*d;
4758 nge->fpoints[i][1] = b + 0.9*d;
4761 for(i=0; i<2; i++) { /* make one straight or first of two straights */
4762 b = ge->prev->fpoints[i][2];
4763 d = ge->fpoints[i][2] - b;
4764 ge->fpoints[i][0] = b + 0.1*d;
4765 ge->fpoints[i][1] = b + 0.9*d;
4771 if(ge->frwd == ge) { /* points to itself, just remove the path completely */
4772 WARNING_3 fprintf(stderr, "glyph %s had a path made of fragments < %g points each, removed\n",
4775 next = freethisge(ge);
4779 /* now close the gap by x and y */
4780 for(i=0; i<2; i++) {
4783 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
4784 if( fclosegap(ge, ge, i, gap, NULL) != 0.0 ) {
4787 /* not good, as the last resort just scale the next line */
4788 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
4791 fprintf(stderr, " last resort on %c: closing next by %g\n",
4792 (i==0 ? 'x' : 'y'), gap);
4795 base = nge->fpoints[i][2];
4796 dx = ge->fpoints[i][2] - base;
4800 scale = ((dx-gap) / dx);
4802 if(nge->type == GE_CURVE)
4803 for(k = 0; k<2; k++)
4804 nge->fpoints[i][k] = base +
4805 scale * (nge->fpoints[i][k] - base);
4807 ge->fpoints[i][2] -= gap;
4811 /* OK, the gap is closed - remove this useless GENTRY */
4817 /* find the point where two rays continuing vectors cross
4818 * returns 1 if they cross, 0 if they don't
4819 * If they cross optionally (if the pointers are not NULL) returns
4820 * the maximal scales for both vectors and also optionally the point
4821 * where the rays cross (twice).
4822 * Expects that the curves are normalized.
4824 * For convenience there are 2 front-end functions taking
4825 * arguments in different formats
4829 double x1, y1, x2, y2;
4831 double k, b; /* lines are represented as y = k*x + b */
4834 static struct ray ray[3];
4836 /* the back-end doing the actual work
4837 * the rays are defined in the static array ray[]
4842 double crossdot[2][2]
4848 for(i=0; i<2; i++) {
4849 if(ray[i].x1 == ray[i].x2)
4853 ray[i].k = (ray[i].y2 - ray[i].y1) / (ray[i].x2 - ray[i].x1);
4854 ray[i].b = ray[i].y2 - ray[i].k * ray[i].x2;
4858 if(ray[0].isvert && ray[1].isvert) {
4859 if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: both vertical\n");
4860 return 0; /* both vertical, don't cross */
4864 ray[2] = ray[0]; /* exchange them */
4872 if( fabs(ray[0].k - ray[1].k) < FEPS) {
4873 if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: parallel lines, k = %g, %g\n",
4874 ray[0].k, ray[1].k);
4875 return 0; /* parallel lines */
4877 x = (ray[1].b - ray[0].b) / (ray[0].k - ray[1].k) ;
4879 y = ray[1].k * x + ray[1].b;
4881 for(i=0; i<2; i++) {
4883 max = (y - ray[i].y1) / (ray[i].y2 - ray[i].y1);
4885 max = (x - ray[i].x1) / (ray[i].x2 - ray[i].x1);
4886 /* check if wrong sides of rays cross */
4888 if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: %c scale=%g @(%g,%g) (%g,%g)<-(%g,%g)\n",
4889 (i?'Y':'X'), max, x, y, ray[i].x2, ray[i].y2, ray[i].x1, ray[i].y1);
4896 crossdot[0][0] = crossdot[1][0] = x;
4897 crossdot[0][1] = crossdot[1][1] = y;
4902 /* the front-end getting the arguments from 4 dots defining
4903 * a curve in the same format as for fapproxcurve():
4904 * rays are defined as beginning and end of the curve,
4905 * the crossdot is inserted as the two middle dots of the curve
4910 double curve[4][2 /*X,Y*/],
4915 ray[0].x1 = curve[0][X];
4916 ray[0].y1 = curve[0][Y];
4917 ray[0].x2 = curve[1][X];
4918 ray[0].y2 = curve[1][Y];
4921 ray[1].x1 = curve[2][X];
4922 ray[1].y1 = curve[2][Y];
4923 ray[1].x2 = curve[3][X];
4924 ray[1].y2 = curve[3][Y];
4927 return fcrossraysxx(&curve[1]);
4930 /* the front-end getting the arguments from gentries:
4931 * rays are defined as beginning of curve1 and end of curve 2
4940 double crossdot[2][2]
4943 ray[0].x1 = ge1->prev->fx3;
4944 ray[0].y1 = ge1->prev->fy3;
4945 ray[0].x2 = ge1->fpoints[X][ge1->ftg];
4946 ray[0].y2 = ge1->fpoints[Y][ge1->ftg];
4949 ray[1].x1 = ge2->fx3;
4950 ray[1].y1 = ge2->fy3;
4952 ray[1].x2 = ge2->prev->fx3;
4953 ray[1].y2 = ge2->prev->fy3;
4955 ray[1].x2 = ge2->fpoints[X][ge2->rtg];
4956 ray[1].y2 = ge2->fpoints[Y][ge2->rtg];
4960 return fcrossraysxx(crossdot);
4963 /* debugging printout functions */
4965 #if defined(DEBUG_DOTSEG) || defined(DEBUG_DOTCURVE) || defined(DEBUG_APPROXCV)
4973 fprintf(stderr, "(%g,%g)", dot[0], dot[1]);
4988 #endif /* DEBUG_* */
4991 * Find squared distance from a dot to a line segment
4996 double seg[2][2 /*X,Y*/],
4997 double dot[2 /*X,Y*/]
5000 #define x1 seg[0][X]
5001 #define y1 seg[0][Y]
5002 #define x2 seg[1][X]
5003 #define y2 seg[1][Y]
5007 double dx, dy; /* segment dimensions */
5008 double kline, bline; /* segment line formula is y=k*x+b */
5009 double kperp, bperp; /* perpendicular from the dot to the line */
5010 double xcross, ycross; /* where the perpendicular crosses the segment */
5012 /* handle the situation where the nearest point of the segment is its end */
5013 #define HANDLE_LIMITS(less12, lesscr1, lesscr2) \
5018 } else if( !(lesscr2) ) { \
5023 if( !(lesscr1) ) { \
5026 } else if( lesscr2 ) { \
5037 if(fabs(dx) < FEPS) {
5038 /* special case - vertical line */
5040 printf("vertical line!\n");
5044 HANDLE_LIMITS( y1 < y2, ycross < y1, ycross < y2);
5045 } else if(fabs(dy) < FEPS) {
5046 /* special case - horizontal line */
5048 printf("horizontal line!\n");
5052 HANDLE_LIMITS( x1 < x2, xcross < x1, xcross < x2)
5055 bline = y1 - x1*kline;
5057 bperp = ydot - xdot*kperp;
5059 xcross = (bline-bperp) / (kperp-kline);
5060 ycross = kline*xcross + bline;
5062 HANDLE_LIMITS( x1 < x2, xcross < x1, xcross < x2)
5065 printf("crossover at (%g,%g)\n", xcross, ycross);
5077 #undef HANDLE_LIMITS
5080 /* find the weighted quadratic average for the distance of a set
5081 * of dots from the curve; also fills out the individual distances
5082 * for each dot; if maxp!=NULL then returns the maximal squared
5088 double curve[4][2 /*X,Y*/ ],
5089 struct dot_dist *dots,
5090 int ndots, /* number of entries in dots */
5094 /* a curve is approximated by this many straight segments */
5096 /* a curve is divided into this many sections with equal weight each */
5098 /* table of coefficients for finding the dots on the curve */
5099 /* tt[0] is left unused */
5100 static double tt[NAPSECT][4];
5101 static int havett = 0; /* flag: tt is initialized */
5102 /* dots on the curve */
5103 double cvd[NAPSECT+1][2 /*X,Y*/];
5104 /* sums by sections */
5106 /* counts by sections */
5107 double count[NWSECT];
5110 double dist1, dist2, dist3, dx, dy, x, y;
5114 double t, nt, t2, nt2, step;
5117 step = 1. / NAPSECT;
5119 for(i=1; i<NAPSECT; i++) {
5124 tt[i][0] = nt2*nt; /* (1-t)^3 */
5125 tt[i][1] = 3*nt2*t; /* 3*(1-t)^2*t */
5126 tt[i][2] = 3*nt*t2; /* 3*(1-t)*t^2 */
5127 tt[i][3] = t2*t; /* t^3 */
5131 for(i=0; i<NWSECT; i++) {
5136 /* split the curve into segments */
5137 for(d=0; d<2; d++) { /* X and Y */
5138 cvd[0][d] = curve[0][d]; /* endpoints */
5139 cvd[NAPSECT][d] = curve[3][d];
5140 for(i=1; i<NAPSECT; i++) {
5141 cvd[i][d] = curve[0][d] * tt[i][0]
5142 + curve[1][d] * tt[i][1]
5143 + curve[2][d] * tt[i][2]
5144 + curve[3][d] * tt[i][3];
5148 for(d=0; d<ndots; d++) {
5149 #ifdef DEBUG_DOTCURVE
5150 printf("dot %d ", d); printdot(dots[d].p); printf(":\n");
5153 for(i=0; i< NAPSECT; i++) {
5154 dist1 = fdotsegdist2(&cvd[i], dots[d].p);
5155 printf(" seg %d ",i); printseg(&cvd[i]); printf(" dist=%g\n", sqrt(dist1));
5162 /* find the nearest dot on the curve
5163 * there may be up to 2 local minimums - so we start from the
5164 * ends of curve and go to the center
5170 dist1 = dx*dx + dy*dy;
5171 #ifdef DEBUG_DOTCURVE
5172 printf(" dot 0 "); printdot(cvd[id1]); printf(" dist=%g\n", sqrt(dist1));
5174 for(i = 1; i<=NAPSECT; i++) {
5177 dist3 = dx*dx + dy*dy;
5178 #ifdef DEBUG_DOTCURVE
5179 printf(" dot %d ",i); printdot(cvd[i]); printf(" dist=%g\n", sqrt(dist3));
5188 if(id1 < NAPSECT-1) {
5190 dx = x - cvd[NAPSECT][X];
5191 dy = y - cvd[NAPSECT][Y];
5192 dist2 = dx*dx + dy*dy;
5193 #ifdef DEBUG_DOTCURVE
5194 printf(" +dot %d ", id2); printdot(cvd[id2]); printf(" dist=%g\n", sqrt(dist2));
5196 for(i = NAPSECT-1; i>id1+1; i--) {
5199 dist3 = dx*dx + dy*dy;
5200 #ifdef DEBUG_DOTCURVE
5201 printf(" dot %d ",i); printdot(cvd[i]); printf(" dist=%g\n", sqrt(dist3));
5210 /* now find which of the local minimums is smaller */
5216 /* the nearest segment must include the nearest dot */
5219 dots[d].dist2 = fdotsegdist2(&cvd[0], dots[d].p);
5220 } else if(id1==NAPSECT) {
5221 dots[d].seg = NAPSECT-1;
5222 dots[d].dist2 = fdotsegdist2(&cvd[NAPSECT-1], dots[d].p);
5224 dist1 = fdotsegdist2(&cvd[id1], dots[d].p);
5225 dist2 = fdotsegdist2(&cvd[id1-1], dots[d].p);
5227 dots[d].seg = id1-1;
5228 dots[d].dist2 = dist2;
5231 dots[d].dist2 = dist1;
5235 i = dots[d].seg % NWSECT;
5236 sum[i] += dots[d].dist2;
5237 if(dots[d].dist2 > max)
5238 max = dots[d].dist2;
5240 #ifdef DEBUG_DOTCURVE
5241 printf(" best seg %d sect %d dist=%g\n", dots[d].seg, i, sqrt(dots[d].dist2));
5245 /* calculate the weighted average */
5248 for(i=0; i<NWSECT; i++) {
5252 dist1 += sum[i]/count[i];
5256 if(id1==0) /* no dots, strange */
5259 return dist1/id1; /* to get the average distance apply sqrt() */
5263 * Approximate a curve matching the giving set of points and with
5264 * middle reference points going along the given segments (and no farther
5265 * than these segments).
5270 double cv[4][2 /*X,Y*/ ], /* points 0-3 are passed in, points 1,2 - out */
5271 struct dot_dist *dots, /* the dots to approximate - distances returned
5272 * there may be invalid */
5276 /* b and c are the middle control points */
5279 /* maximal number of sections on each axis - used for the first step */
5281 /* number of sections used for the other steps */
5283 /* when the steps become less than this many points, it's time to stop */
5285 double from[2 /*B,C*/], to[2 /*B,C*/];
5286 double middf[2 /*B,C*/][2 /*X,Y*/], df;
5287 double coef[2 /*B,C*/][MAXSECT];
5288 double res[MAXSECT][MAXSECT], thisres, bestres, goodres;
5289 int ncoef[2 /*B,C*/], best[2 /*B,C*/], good[2 /*B,C*/];
5290 int i, j, k, keepsym;
5294 #ifdef DEBUG_APPROXCV
5295 fprintf(stderr, "Curve points:");
5296 for(i=0; i<4; i++) {
5297 fprintf(stderr, " ");
5300 fprintf(stderr, "\nDots:");
5301 for(i=0; i<ndots; i++) {
5302 fprintf(stderr, " ");
5303 printdot(dots[i].p);
5305 fprintf(stderr, "\n");
5308 /* load the endpoints and calculate differences */
5309 for(i=0; i<2; i++) {
5311 middf[B][i] = cv[1][i]-cv[0][i];
5312 middf[C][i] = cv[2][i]-cv[3][i];
5320 while(ncoef[B] != 1 || ncoef[C] != 1) {
5321 /* prepare the values of coefficients */
5322 for(i=0; i<2; i++) { /*B,C*/
5323 #ifdef DEBUG_APPROXCV
5324 fprintf(stderr, "Coefficients by %c(%g,%g):", bc[i], from[i], to[i]);
5326 df = (to[i]-from[i]) / (ncoef[i]*2);
5327 for(j=0; j<ncoef[i]; j++) {
5328 coef[i][j] = from[i] + df*(2*j+1);
5329 #ifdef DEBUG_APPROXCV
5330 fprintf(stderr, " %g", coef[i][j]);
5333 #ifdef DEBUG_APPROXCV
5334 fprintf(stderr, "\n");
5338 /* i iterates by ncoef[B], j iterates by ncoef[C] */
5339 for(i=0; i<ncoef[B]; i++) {
5340 for(j=0; j<ncoef[C]; j++) {
5341 for(k=0; k<2; k++) { /*X, Y*/
5342 cv[1][k] = cv[0][k] + middf[B][k]*coef[B][i];
5343 cv[2][k] = cv[3][k] + middf[C][k]*coef[C][j];
5345 res[i][j] = thisres = fdotcurvdist2(cv, dots, ndots, NULL);
5346 if(thisres < bestres) {
5353 } else if(thisres < goodres) {
5358 #ifdef DEBUG_APPROXCV
5359 fprintf(stderr, " at (%g,%g) dist=%g %s\n", coef[B][i], coef[C][j], sqrt(thisres),
5360 (best[B]==i && best[C]==j)? "(BEST)":"");
5364 #ifdef DEBUG_APPROXCV
5365 fprintf(stderr, " best: at (%g, %g) dist=%g\n",
5366 coef[B][best[B]], coef[C][best[C]], sqrt(bestres));
5367 fprintf(stderr, " B:%d,%d C:%d,%d -- 2nd best: at (%g, %g) dist=%g\n",
5368 best[B], good[B], best[C], good[C], coef[B][good[B]], coef[C][good[C]], sqrt(goodres));
5371 if(bestres < (0.1*0.1)) { /* consider it close enough */
5372 /* calculate the coordinates to return */
5373 for(k=0; k<2; k++) { /*X, Y*/
5374 cv[1][k] = cv[0][k] + middf[B][k]*coef[B][best[B]];
5375 cv[2][k] = cv[3][k] + middf[C][k]*coef[C][best[C]];
5377 #ifdef DEBUG_APPROXCV
5378 fprintf(stderr, "quick approximated middle points "); printdot(cv[1]);
5379 fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n");
5384 if(best[B] != best[C] && best[B]-best[C] == good[C]-good[B]) {
5386 #ifdef DEBUG_APPROXCV
5387 fprintf(stderr, "keeping symmetry!\n");
5390 for(i=0; i<2; i++) { /*B,C*/
5394 /* try to keep the symmetry */
5395 if(best[i] < good[i]) {
5396 from[i] = coef[i][best[i]];
5397 to[i] = coef[i][good[i]];
5399 from[i] = coef[i][good[i]];
5400 to[i] = coef[i][best[i]];
5403 df = (to[i]-from[i]) / ncoef[i];
5404 from[i] += df*best[i];
5405 to[i] = from[i] + df;
5407 if( fabs(df*middf[i][0]) < STEPEPS && fabs(df*middf[i][1]) < STEPEPS) {
5408 /* this side has converged */
5409 from[i] = to[i] = (from[i]+to[i]) / 2.;
5412 ncoef[i] = NORMSECT;
5416 /* calculate the coordinates to return */
5417 for(k=0; k<2; k++) { /*X, Y*/
5418 cv[1][k] = cv[0][k] + middf[B][k]*from[B];
5419 cv[2][k] = cv[3][k] + middf[C][k]*from[C];
5421 #ifdef DEBUG_APPROXCV
5422 fprintf(stderr, "approximated middle points "); printdot(cv[1]);
5423 fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n");
5433 * Find the squared value of the sinus of the angle between the
5434 * end of ge1 and the beginning of ge2
5435 * The curve must be normalized.
5444 double d[3][2 /*X,Y*/];
5445 double scale1, scale2, len1, len2;
5449 d[1][X] = ge1->fx3 - ge1->prev->fx3;
5450 d[1][Y] = ge1->fy3 - ge1->prev->fy3;
5452 d[1][X] = ge1->fx3 - ge1->fpoints[X][ge1->rtg];
5453 d[1][Y] = ge1->fy3 - ge1->fpoints[Y][ge1->rtg];
5455 d[2][X] = ge2->fpoints[X][ge2->ftg] - ge2->prev->fx3;
5456 d[2][Y] = ge2->fpoints[Y][ge2->ftg] - ge2->prev->fy3;
5458 len1 = sqrt( d[1][X]*d[1][X] + d[1][Y]*d[1][Y] );
5459 len2 = sqrt( d[2][X]*d[2][X] + d[2][Y]*d[2][Y] );
5460 /* scale the 2nd segment to the length of 1
5461 * and to make sure that the 1st segment is longer scale it to
5462 * the length of 2 and extend to the same distance backwards
5467 for(axis=0; axis <2; axis++) {
5468 d[0][axis] = -( d[1][axis] *= scale1 );
5469 d[2][axis] *= scale2;
5471 return fdotsegdist2(d, d[2]);
5475 /* find the area covered by the curve
5476 * (limited by the projections to the X axis)
5484 double Ly, My, Ny, Py, Qx, Rx, Sx;
5487 /* y = Ly*t^3 + My*t^2 + Ny*t + Py */
5488 Ly = -ge->prev->fy3 + 3*(ge->fy1 - ge->fy2) + ge->fy3;
5489 My = 3*ge->prev->fy3 - 6*ge->fy1 + 3*ge->fy2;
5490 Ny = 3*(-ge->prev->fy3 + ge->fy1);
5493 /* dx/dt = Qx*t^2 + Rx*t + Sx */
5494 Qx = 3*(-ge->prev->fx3 + 3*(ge->fx1 - ge->fx2) + ge->fx3);
5495 Rx = 6*(ge->prev->fx3 - 2*ge->fx1 + ge->fx2);
5496 Sx = 3*(-ge->prev->fx3 + ge->fx1);
5498 /* area is integral[from 0 to 1]( y(t) * dx(t)/dt *dt) */
5499 area = 1./6.*(Ly*Qx) + 1./5.*(Ly*Rx + My*Qx)
5500 + 1./4.*(Ly*Sx + My*Rx + Ny*Qx) + 1./3.*(My*Sx + Ny*Rx + Py*Qx)
5501 + 1./2.*(Ny*Sx + Py*Rx) + Py*Sx;
5507 /* find the value of point on the curve at the given parameter t,
5508 * along the given axis (0 - X, 1 - Y).
5520 /* val = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 */
5525 return ge->prev->fpoints[axis][2]*mt2*mt
5526 + 3*(ge->fpoints[axis][0]*mt2*t + ge->fpoints[axis][1]*mt*t2)
5527 + ge->fpoints[axis][2]*t*t2;
5531 * Find ndots equally spaced dots on a curve or line and fill
5532 * their coordinates into the dots array
5538 double dots[][2], /* the dots to fill */
5543 double t, nf, dx, d[2];
5546 if(ge->type == GE_CURVE) {
5547 for(i=0; i<ndots; i++) {
5549 for(axis=0; axis<2; axis++)
5550 dots[i][axis] = fcvval(ge, axis, t);
5553 d[0] = ge->fx3 - ge->prev->fx3;
5554 d[1] = ge->fy3 - ge->prev->fy3;
5555 for(i=0; i<ndots; i++) {
5557 for(axis=0; axis<2; axis++)
5558 dots[i][axis] = ge->prev->fpoints[axis][2]
5565 * Allocate a structure gex_con
5573 ge->ext = (void*)calloc(1, sizeof(GEX_CON));
5575 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
5581 * Normalize a gentry for fforceconcise() : find the points that
5582 * can be used to calculate the tangents.
5590 int midsame, frontsame, rearsame;
5592 if(ge->type == GE_LINE) {
5595 } else { /* assume it's a curve */
5596 midsame = (fabs(ge->fx1-ge->fx2)<FEPS && fabs(ge->fy1-ge->fy2)<FEPS);
5597 frontsame = (fabs(ge->fx1-ge->prev->fx3)<FEPS && fabs(ge->fy1-ge->prev->fy3)<FEPS);
5598 rearsame = (fabs(ge->fx3-ge->fx2)<FEPS && fabs(ge->fy3-ge->fy2)<FEPS);
5600 if(midsame && (frontsame || rearsame) ) {
5601 /* essentially a line */
5619 /* various definition for the processing of outlines */
5621 /* maximal average quadratic distance from the original curve
5622 * (in dots) to consider the joined curve good
5625 #define CVEPS2 (CVEPS*CVEPS)
5626 /* squared sinus of the maximal angle that we consider a smooth joint */
5627 #define SMOOTHSIN2 0.25 /* 0.25==sin(30 degrees)^2 */
5628 /* squared line length that we consider small */
5629 #define SMALL_LINE2 (15.*15.)
5630 /* how many times a curve must be bigger than a line to join, squared */
5631 #define TIMES_LINE2 (3.*3.)
5634 * Normalize and analyse a gentry for fforceconcise() and fill out the gex_con
5644 double avsd2, dots[3][2 /*X,Y*/];
5648 memset(gex, 0, sizeof *gex);
5651 for(i=0; i<2; i++) {
5652 avsd2 = gex->d[i] = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
5653 gex->len2 += avsd2*avsd2;
5655 gex->sin2 = fjointsin2(ge, ge->frwd);
5656 if(ge->type == GE_CURVE) {
5657 ge->dir = fgetcvdir(ge);
5658 for(i=0; i<2; i++) {
5659 dots[0][i] = ge->prev->fpoints[i][2];
5660 dots[1][i] = ge->fpoints[i][2];
5661 dots[2][i] = fcvval(ge, i, 0.5);
5663 avsd2 = fdotsegdist2(dots, dots[2]);
5664 if(avsd2 <= CVEPS2) {
5665 gex->flags |= GEXF_FLAT;
5668 ge->dir = CVDIR_FEQUAL|CVDIR_REQUAL;
5669 gex->flags |= GEXF_FLAT;
5671 if(gex->flags & GEXF_FLAT) {
5672 if( fabs(gex->d[X]) > FEPS && fabs(gex->d[Y]) < 5.
5673 && fabs(gex->d[Y] / gex->d[X]) < 0.2)
5674 gex->flags |= GEXF_HOR;
5675 else if( fabs(gex->d[Y]) > FEPS && fabs(gex->d[X]) < 5.
5676 && fabs(gex->d[X] / gex->d[Y]) < 0.2)
5677 gex->flags |= GEXF_VERT;
5679 ix = gex->isd[X] = fsign(gex->d[X]);
5680 iy = gex->isd[Y] = fsign(gex->d[Y]);
5683 gex->flags |= GEXF_QDL;
5685 gex->flags |= GEXF_QUL;
5686 if(gex->flags & GEXF_HOR)
5687 gex->flags |= GEXF_IDQ_L;
5691 gex->flags |= GEXF_QDR;
5693 gex->flags |= GEXF_QUR;
5694 if(gex->flags & GEXF_HOR)
5695 gex->flags |= GEXF_IDQ_R;
5697 if(gex->flags & GEXF_VERT) {
5699 gex->flags |= GEXF_IDQ_U;
5700 } else { /* supposedly there is no 0-sized entry */
5701 gex->flags |= GEXF_IDQ_D;
5707 * Analyse a joint between this and following gentry for fforceconcise()
5708 * and fill out the corresponding parts of the gex_con structure
5709 * Bothe entries must be analyzed first.
5717 GENTRY *nge = ge->frwd;
5719 GEX_CON *gex, *ngex;
5720 double avsd2, dots[3][2 /*X,Y*/];
5723 gex = X_CON(ge); ngex = X_CON(nge);
5725 /* look if they can be joined honestly */
5727 /* if any is flat, they should join smoothly */
5728 if( (gex->flags & GEXF_FLAT || ngex->flags & GEXF_FLAT)
5729 && gex->sin2 > SMOOTHSIN2)
5732 if(ge->type == GE_LINE) {
5733 if(nge->type == GE_LINE) {
5734 if(gex->len2 > SMALL_LINE2 || ngex->len2 > SMALL_LINE2)
5737 if(gex->len2*TIMES_LINE2 > ngex->len2)
5740 } else if(nge->type == GE_LINE) {
5741 if(ngex->len2*TIMES_LINE2 > gex->len2)
5745 /* if curve changes direction */
5746 if( gex->isd[X]*ngex->isd[X]<0 || gex->isd[Y]*ngex->isd[Y]<0)
5749 /* if would create a zigzag */
5750 if( ((ge->dir&CVDIR_FRONT)-CVDIR_FEQUAL) * ((nge->dir&CVDIR_REAR)-CVDIR_REQUAL) < 0 )
5753 if( fcrossraysge(ge, nge, NULL, NULL, NULL) )
5754 gex->flags |= GEXF_JGOOD;
5757 /* look if they can be joined by flatting out one of the entries */
5759 /* at this point we know that the general direction of the
5763 if( gex->flags & GEXF_FLAT ) {
5768 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) )
5769 gex->flags |= GEXF_JFLAT|GEXF_JFLAT1;
5771 if( ngex->flags & GEXF_FLAT ) {
5776 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) )
5777 gex->flags |= GEXF_JFLAT|GEXF_JFLAT2;
5781 /* look if one of the entries can be brought to an idealized
5782 * horizontal or vertical position and then joined
5784 if( gex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) {
5787 tge.fy1 = ge->prev->fy3; /* force horizontal */
5789 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) )
5790 gex->flags |= GEXF_JID|GEXF_JID1;
5791 } else if( gex->flags & GEXF_VERT && gex->isd[Y]*ngex->isd[Y]>=0 ) {
5793 tge.fx1 = ge->prev->fx3; /* force vertical */
5796 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) )
5797 gex->flags |= GEXF_JID|GEXF_JID1;
5799 if( ngex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) {
5802 tge.fy2 = nge->fy3; /* force horizontal */
5804 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) )
5805 gex->flags |= GEXF_JID|GEXF_JID2;
5806 } else if( ngex->flags & GEXF_VERT && gex->isd[Y]*ngex->isd[Y]>=0 ) {
5808 tge.fx2 = nge->fx3; /* force vertical */
5811 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) )
5812 gex->flags |= GEXF_JID|GEXF_JID2;
5816 /* look if we can change them to one line */
5817 if(gex->flags & GEXF_FLAT && ngex->flags & GEXF_FLAT) {
5818 for(i=0; i<2; i++) {
5819 dots[0][i] = ge->prev->fpoints[i][2];
5820 dots[1][i] = nge->fpoints[i][2];
5821 dots[2][i] = ge->fpoints[i][2];
5823 if( fdotsegdist2(dots, dots[2]) <= CVEPS2)
5824 gex->flags |= GEXF_JLINE;
5829 * Force conciseness of one contour in the glyph,
5830 * the contour is indicated by one entry from it.
5839 /* initial maximal number of dots to be used as reference */
5840 #define MAXDOTS ((NREFDOTS+1)*12)
5842 GENTRY *ge, *pge, *nge, *ige;
5843 GEX_CON *gex, *pgex, *ngex, *nngex;
5845 int quad, qq, i, j, ndots, maxdots;
5847 int joinmask, pflag, nflag;
5848 struct dot_dist *dots;
5849 double avsd2, maxd2, eps2;
5853 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n",
5854 __FILE__, __LINE__);
5855 fprintf(stderr, "Strange contour in glyph %s\n", g->name);
5856 dumppaths(g, NULL, NULL);
5860 if(startge->type != GE_CURVE && startge->type != GE_LINE)
5861 return; /* probably a degenerate contour */
5864 fprintf(stderr, "processing contour 0x%p of glyph %s\n", startge, g->name);
5867 dots = (struct dot_dist *)malloc(sizeof(*dots)*maxdots);
5869 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
5874 joinmask = GEXF_JGOOD;
5878 if((gex->flags & GEXF_JMASK) > ((joinmask<<1)-1)) {
5880 fprintf(stderr, "found higher flag (%x>%x) at 0x%p\n",
5881 gex->flags & GEXF_JMASK, ((joinmask<<1)-1), ge);
5883 startge = ge; /* have to redo the pass */
5886 if(( gex->flags & joinmask )==0)
5889 /* if we happen to be in the middle of a string of
5890 * joinable entries, find its beginning
5892 if( gex->flags & (GEXF_JCVMASK^GEXF_JID) )
5893 quad = gex->flags & X_CON_F(ge->frwd) & GEXF_QMASK;
5894 else if( gex->flags & GEXF_JID2 )
5895 quad = gex->flags & GEXF_QFROM_IDEAL(X_CON_F(ge->frwd)) & GEXF_QMASK;
5896 else /* must be GEXF_JID1 */
5897 quad = GEXF_QFROM_IDEAL(gex->flags) & X_CON_F(ge->frwd) & GEXF_QMASK;
5900 pgex = X_CON(pge->bkwd);
5903 fprintf(stderr, "ge %p prev -> 0x%p ", ge, pge);
5905 while(pgex->flags & GEXF_JCVMASK) {
5906 if( !(pgex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID2)) )
5907 qq = GEXF_QFROM_IDEAL(pgex->flags);
5909 qq = pgex->flags & GEXF_QMASK;
5912 fprintf(stderr, "(%x?%x)", quad, qq);
5914 if( !(quad & qq) ) {
5915 if( !(X_CON_F(pge) & (GEXF_JCVMASK^GEXF_JID))
5916 && pgex->flags & (GEXF_JCVMASK^GEXF_JID) ) {
5917 /* the previos entry is definitely a better match */
5920 fprintf(stderr, "\nprev is a better match at %p\n", pge);
5931 pgex = X_CON(pge->bkwd);
5933 fprintf(stderr, "0x%p ", pge);
5936 /* collect as many entries for joining as possible */
5939 nngex = X_CON(nge->frwd);
5942 fprintf(stderr, ": 0x%x\nnext -> 0x%p ", pge, nge);
5944 while(ngex->flags & GEXF_JCVMASK) {
5945 if( !(ngex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID1)) )
5946 qq = GEXF_QFROM_IDEAL(nngex->flags);
5948 qq = nngex->flags & GEXF_QMASK;
5951 fprintf(stderr, "(%x?%x)", quad, qq);
5952 if( !(quad & qq) ) {
5953 if( !(X_CON_F(nge->bkwd) & (GEXF_JCVMASK^GEXF_JID))
5954 && ngex->flags & (GEXF_JCVMASK^GEXF_JID) ) {
5955 /* the next-next entry is definitely a better match */
5956 if(nge == ge->frwd) {
5958 fprintf(stderr, "\nnext %x is a better match than %x at %p (jmask %x)\n",
5959 ngex->flags & GEXF_JCVMASK, gex->flags & GEXF_JCVMASK, nge, joinmask);
5970 nngex = X_CON(nge->frwd);
5972 fprintf(stderr, "0x%p ", nge);
5976 fprintf(stderr, ": 0x%x\n", nge);
5978 /* XXX add splitting of last entries if neccessary */
5980 /* make sure that all the reference dots are valid */
5981 for(ige = pge; ige != nge->frwd; ige = ige->frwd) {
5983 if( !(nngex->flags & GEXF_VDOTS) ) {
5984 fsampledots(ige, nngex->dots, NREFDOTS);
5985 nngex->flags |= GEXF_VDOTS;
5989 /* do the actual joining */
5992 ngex = X_CON(nge->bkwd);
5993 /* now the segments to be joined are pge...nge */
5996 for(ige = pge; ige != nge->frwd; ige = ige->frwd) {
5997 if(maxdots < ndots+(NREFDOTS+1)) {
5999 dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots);
6001 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
6006 for(i=0; i<NREFDOTS; i++) {
6008 dots[ndots].p[j] = nngex->dots[i][j];
6012 dots[ndots].p[j] = ige->fpoints[j][2];
6015 ndots--; /* the last point is not interesting */
6018 pflag = pgex->flags;
6019 if(pflag & (GEXF_JGOOD|GEXF_JFLAT2|GEXF_JID2)) {
6021 } else if(pflag & GEXF_JFLAT) {
6022 tpge.fx1 = tpge.fx3;
6023 tpge.fy1 = tpge.fy3;
6024 } else if(pflag & GEXF_JID) {
6025 if(pflag & GEXF_HOR)
6026 tpge.fy1 = tpge.bkwd->fy3;
6028 tpge.fx1 = tpge.bkwd->fx3;
6032 nflag = ngex->flags;
6033 if(nflag & (GEXF_JGOOD|GEXF_JFLAT1|GEXF_JID)
6034 && !(nflag & GEXF_JID2)) {
6036 } else if(nflag & GEXF_JFLAT) {
6037 tnge.fx2 = tnge.bkwd->fx3;
6038 tnge.fy2 = tnge.bkwd->fy3;
6039 } else if(nflag & GEXF_JID) {
6040 if(X_CON_F(nge) & GEXF_HOR)
6041 tnge.fy2 = tnge.fy3;
6043 tnge.fx2 = tnge.fx3;
6046 fnormalizege(&tpge);
6047 fnormalizege(&tnge);
6048 if( fcrossraysge(&tpge, &tnge, NULL, NULL, &apcv[1]) ) {
6049 apcv[0][X] = tpge.bkwd->fx3;
6050 apcv[0][Y] = tpge.bkwd->fy3;
6051 /* apcv[1] and apcv[2] were filled by fcrossraysge() */
6052 apcv[3][X] = tnge.fx3;
6053 apcv[3][Y] = tnge.fy3;
6055 /* calculate the precision depending on the smaller dimension of the curve */
6056 maxd2 = apcv[3][X]-apcv[0][X];
6058 eps2 = apcv[3][Y]-apcv[0][Y];
6062 eps2 *= (CVEPS2*4.) / (400.*400.);
6065 else if(eps2 > CVEPS2*4.)
6068 fapproxcurve(apcv, dots, ndots);
6070 avsd2 = fdotcurvdist2(apcv, dots, ndots, &maxd2);
6072 fprintf(stderr, "avsd = %g, maxd = %g, ", sqrt(avsd2), sqrt(maxd2));
6073 if(avsd2 <= eps2 && maxd2 <= eps2*2.) {
6074 /* we've guessed a curve that is close enough */
6075 ggoodcv++; ggoodcvdots += ndots;
6077 if(ISDBG(FCONCISE)) {
6078 fprintf(stderr, "in %s joined %p-%p to ", g->name, pge, nge);
6079 for(i=0; i<4; i++) {
6080 fprintf(stderr, " (%g, %g)", apcv[i][X], apcv[i][Y]);
6082 fprintf(stderr, " from\n");
6083 dumppaths(g, pge, nge);
6085 for(i=0; i<3; i++) {
6086 pge->fxn[i] = apcv[i+1][X];
6087 pge->fyn[i] = apcv[i+1][Y];
6089 pge->type = GE_CURVE;
6091 for(ige = pge->frwd; ; ige = pge->frwd) {
6093 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n",
6094 __FILE__, __LINE__);
6106 if(ISDBG(FCONCISE)) {
6107 fprintf(stderr, "normalized ");
6108 for(i=0; i<3; i++) {
6109 fprintf(stderr, " (%g, %g)", ge->fpoints[X][i], ge->fpoints[Y][i]);
6111 fprintf(stderr, "\n");
6115 fanalyzege(ge->bkwd);
6116 fanalyzejoint(ge->bkwd);
6118 /* the results of this join will have to be reconsidered */
6119 startge = ge = ge->frwd;
6122 gbadcv++; gbadcvdots += ndots;
6126 /* if we're down to 2 entries then the join has failed */
6127 if(pge->frwd == nge) {
6128 pgex->flags &= ~joinmask;
6130 fprintf(stderr, "no match\n");
6134 /* reduce the number of entries by dropping one at some end,
6135 * should never drop the original ge from the range
6139 || pge != ge && (pgex->flags & GEXF_JCVMASK) <= (ngex->flags & GEXF_JCVMASK) ) {
6145 fprintf(stderr, "next try: %p to %p\n", pge, nge);
6151 joinmask = (joinmask >> 1) & GEXF_JCVMASK;
6157 /* join flat segments into lines */
6158 /* here ge==startge */
6161 if( !(gex->flags & GEXF_JLINE) )
6165 dots[ndots].p[X] = ge->fx3;
6166 dots[ndots].p[Y] = ge->fy3;
6173 fprintf(stderr, "joining LINE from %p-%p\n", ge, nge);
6179 fprintf(stderr, "(p=%p/%x n=0x%x/%x) ", pge, pgex->flags & GEXF_JLINE,
6180 nge, ngex->flags & GEXF_JLINE);
6181 if( !((pgex->flags | ngex->flags) & GEXF_JLINE) ) {
6183 fprintf(stderr, "(end p=%p n=%p) ", pge, nge);
6187 if(maxdots < ndots+2) {
6189 dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots);
6191 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
6195 if( pgex->flags & GEXF_JLINE ) {
6196 for(i=0; i<2; i++) {
6197 apcv[0][i] = pge->bkwd->fpoints[i][2];
6198 apcv[1][i] = nge->fpoints[i][2];
6199 dots[ndots].p[i] = pge->fpoints[i][2];
6202 for(i=0; i<ndots; i++) {
6203 avsd2 = fdotsegdist2(apcv, dots[i].p);
6207 if(i<ndots) { /* failed to join */
6209 fprintf(stderr, "failed to join prev %p ", pge);
6211 pgex->flags &= ~GEXF_JLINE;
6216 fprintf(stderr, "intersected at prev %p ", pge);
6217 break; /* oops, tried to self-intersect */
6220 } else if(ISDBG(FCONCISE))
6221 fprintf(stderr, "(p=%p) ", pge);
6223 if( ngex->flags & GEXF_JLINE ) {
6224 for(i=0; i<2; i++) {
6225 apcv[0][i] = pge->fpoints[i][2]; /* pge points before the 1st segment */
6226 apcv[1][i] = nge->frwd->fpoints[i][2];
6227 dots[ndots].p[i] = nge->fpoints[i][2];
6230 for(i=0; i<ndots; i++) {
6231 avsd2 = fdotsegdist2(apcv, dots[i].p);
6235 if(i<ndots) { /* failed to join */
6237 fprintf(stderr, "failed to join next %p ", nge->frwd);
6239 ngex->flags &= ~GEXF_JLINE;
6243 } else if(ISDBG(FCONCISE))
6244 fprintf(stderr, "(n=%p) ", nge);
6247 pge = pge->frwd; /* now the limits are pge...nge inclusive */
6248 if(pge == nge) /* a deeply perversive contour */
6251 if(ISDBG(FCONCISE)) {
6252 fprintf(stderr, "\nin %s joined LINE %p-%p from\n", g->name, pge, nge);
6253 dumppaths(g, pge, nge);
6255 pge->type = GE_LINE;
6256 for(i=0; i<2; i++) {
6257 pge->fpoints[i][2] = nge->fpoints[i][2];
6260 X_CON_F(pge) &= ~GEXF_JLINE;
6263 for(ige = pge->frwd; ; ige = pge->frwd) {
6265 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n",
6266 __FILE__, __LINE__);
6286 /* force conciseness: substitute 2 or more curves going in the
6287 ** same quadrant with one curve
6288 ** in floating point
6297 GENTRY *ge, *nge, *endge, *xge;
6299 assertisfloat(g, "enforcing conciseness");
6302 assertpath(g->entries, __FILE__, __LINE__, g->name);
6305 dumppaths(g, NULL, NULL);
6307 /* collect more information about each gentry and their joints */
6308 for (ge = g->entries; ge != 0; ge = ge->next)
6309 if (ge->type == GE_CURVE || ge->type == GE_LINE)
6312 for (ge = g->entries; ge != 0; ge = ge->next)
6313 if (ge->type == GE_CURVE || ge->type == GE_LINE) {
6318 /* see what we can do about joining */
6319 for (ge = g->entries; ge != 0; ge = ge->next)
6320 if (ge->type == GE_CURVE || ge->type == GE_LINE)
6323 /* now do the joining */
6324 for (ge = g->entries; ge != 0; ge = ge->next)
6325 if(ge->type == GE_MOVE)
6326 fconcisecontour(g, ge->next);
6328 for (ge = g->entries; ge != 0; ge = ge->next)
6329 if (ge->type == GE_CURVE || ge->type == GE_LINE)
6342 int grp, lastgrp= -1;
6344 if(ISDBG(FCONCISE) && glyphno == 0) {
6345 fprintf(stderr, "Guessed curves: bad %d/%d good %d/%d\n",
6346 gbadcv, gbadcvdots, ggoodcv, ggoodcvdots);
6349 g = &glyph_list[glyphno];
6351 fprintf(pfa_file, "/%s { \n", g->name);
6353 /* consider widths >MAXLEGALWIDTH as bugs */
6354 if( g->scaledwidth <= MAXLEGALWIDTH ) {
6355 fprintf(pfa_file, "0 %d hsbw\n", g->scaledwidth);
6357 fprintf(pfa_file, "0 1000 hsbw\n");
6358 WARNING_2 fprintf(stderr, "glyph %s: width %d seems to be buggy, set to 1000\n",
6359 g->name, g->scaledwidth);
6363 fprintf(pfa_file, "%% contours: ");
6364 for (i = 0; i < g->ncontours; i++)
6365 fprintf(pfa_file, "%s(%d,%d) ", (g->contours[i].direction == DIR_OUTER ? "out" : "in"),
6366 g->contours[i].xofmin, g->contours[i].ymin);
6367 fprintf(pfa_file, "\n");
6369 if (g->rymin < 5000)
6370 fprintf(pfa_file, "%d lower%s\n", g->rymin, (g->flatymin ? "flat" : "curve"));
6371 if (g->rymax > -5000)
6372 fprintf(pfa_file, "%d upper%s\n", g->rymax, (g->flatymax ? "flat" : "curve"));
6376 for (i = 0; i < g->nhs; i += 2) {
6377 if (g->hstems[i].flags & ST_3) {
6378 fprintf(pfa_file, "%d %d %d %d %d %d hstem3\n",
6380 g->hstems[i + 1].value - g->hstems[i].value,
6381 g->hstems[i + 2].value,
6382 g->hstems[i + 3].value - g->hstems[i + 2].value,
6383 g->hstems[i + 4].value,
6384 g->hstems[i + 5].value - g->hstems[i + 4].value
6388 fprintf(pfa_file, "%d %d hstem\n", g->hstems[i].value,
6389 g->hstems[i + 1].value - g->hstems[i].value);
6394 for (i = 0; i < g->nvs; i += 2) {
6395 if (g->vstems[i].flags & ST_3) {
6396 fprintf(pfa_file, "%d %d %d %d %d %d vstem3\n",
6398 g->vstems[i + 1].value - g->vstems[i].value,
6399 g->vstems[i + 2].value,
6400 g->vstems[i + 3].value - g->vstems[i + 2].value,
6401 g->vstems[i + 4].value,
6402 g->vstems[i + 5].value - g->vstems[i + 4].value
6406 fprintf(pfa_file, "%d %d vstem\n", g->vstems[i].value,
6407 g->vstems[i + 1].value - g->vstems[i].value);
6411 for (ge = g->entries; ge != 0; ge = ge->next) {
6414 if(grp >= 0 && grp != lastgrp) {
6415 fprintf(pfa_file, "%d 4 callsubr\n", grp+g->firstsubr);
6423 fprintf(pfa_file, "%d %d amoveto\n", ge->ix3, ge->iy3);
6425 rmoveto(ge->ix3 - x, ge->iy3 - y);
6427 fprintf(stderr, "Glyph %s: print moveto(%d, %d)\n",
6428 g->name, ge->ix3, ge->iy3);
6434 fprintf(pfa_file, "%d %d alineto\n", ge->ix3, ge->iy3);
6436 rlineto(ge->ix3 - x, ge->iy3 - y);
6442 fprintf(pfa_file, "%d %d %d %d %d %d arcurveto\n",
6443 ge->ix1, ge->iy1, ge->ix2, ge->iy2, ge->ix3, ge->iy3);
6445 rrcurveto(ge->ix1 - x, ge->iy1 - y,
6446 ge->ix2 - ge->ix1, ge->iy2 - ge->iy1,
6447 ge->ix3 - ge->ix2, ge->iy3 - ge->iy2);
6455 WARNING_1 fprintf(stderr, "**** Glyph %s: unknown entry type '%c'\n",
6461 fprintf(pfa_file, "endchar } ND\n");
6464 /* print the subroutines for this glyph, returns the number of them */
6468 int startid /* start numbering subroutines from this id */
6474 g = &glyph_list[glyphno];
6476 if(!hints || !subhints || g->nsg<1)
6479 g->firstsubr=startid;
6482 fprintf(pfa_file, "%% %s %d\n", g->name, g->nsg);
6484 for(grp=0; grp<g->nsg; grp++) {
6485 fprintf(pfa_file, "dup %d {\n", startid++);
6486 for(i= (grp==0)? 0 : g->nsbs[grp-1]; i<g->nsbs[grp]; i++)
6487 fprintf(pfa_file, "\t%d %d %cstem\n", g->sbstems[i].low,
6488 g->sbstems[i].high-g->sbstems[i].low,
6489 g->sbstems[i].isvert ? 'v' : 'h');
6490 fprintf(pfa_file, "\treturn\n\t} NP\n");
6497 print_glyph_metrics(
6504 g = &glyph_list[glyphno];
6507 fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n",
6508 code, g->scaledwidth, g->name,
6509 iscale(g->xMin), iscale(g->yMin), iscale(g->xMax), iscale(g->yMax));
6511 fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n",
6512 code, g->scaledwidth, g->name,
6513 g->xMin, g->yMin, g->xMax, g->yMax);
6518 An important note about the BlueValues.
6520 The Adobe documentation says that the maximal width of a Blue zone
6521 is connected to the value of BlueScale, which is by default 0.039625.
6522 The BlueScale value defines, at which point size the overshoot
6523 suppression be disabled.
6525 The formula for it that is given in the manual is:
6527 BlueScale=point_size/240, for a 300dpi device
6529 that makes us wonder what is this 240 standing for. Incidentally
6530 240=72*1000/300, where 72 is the relation between inches and points,
6531 1000 is the size of the glyph matrix, and 300dpi is the resolution of
6532 the output device. Knowing that we can recalculate the formula for
6533 the font size in pixels rather than points:
6535 BlueScale=pixel_size/1000
6537 That looks a lot simpler than the original formula, does not it ?
6538 And the limitation about the maximal width of zone also looks
6539 a lot simpler after the transformation:
6541 max_width < 1000/pixel_size
6543 that ensures that even at the maximal pixel size when the overshoot
6544 suppression is disabled the zone width will be less than one pixel.
6545 This is important, failure to comply to this limit will result in
6546 really ugly fonts (been there, done that). But knowing the formula
6547 for the pixel width, we see that in fact we can use the maximal width
6548 of 24, not 23 as specified in the manual.
6552 #define MAXBLUEWIDTH (24)
6555 * Find the indexes of the most frequent values
6556 * in the hystogram, sort them in ascending order, and save which one
6557 * was the best one (if asked).
6558 * Returns the number of values found (may be less than maximal because
6559 * we ignore the zero values)
6562 #define MAXHYST (2000) /* size of the hystogram */
6563 #define HYSTBASE 500
6567 int *hyst, /* the hystogram */
6568 int base, /* the base point of the hystogram */
6569 int *best, /* the array for indexes of best values */
6570 int nbest, /* its allocated size */
6571 int width, /* minimal difference between indexes */
6572 int *bestindp /* returned top point */
6575 unsigned char hused[MAXHYST / 8 + 1];
6576 int i, max, j, w, last = 0;
6581 memset(hused, 0 , sizeof hused);
6584 for (i = 0; i < nbest && max != 0; i++) {
6587 for (j = 1; j < MAXHYST - 1; j++) {
6590 if (w > max && (hused[j>>3] & (1 << (j & 0x07))) == 0) {
6597 /* do not pick the too low values */
6600 for (j = best[i] - width; j <= best[i] + width; j++) {
6601 if (j >= 0 && j < MAXHYST)
6602 hused[j >> 3] |= (1 << (j & 0x07));
6611 *bestindp = best[0];
6613 /* sort the indexes in ascending order */
6614 for (i = 0; i < nf; i++) {
6615 for (j = i + 1; j < nf; j++)
6616 if (best[j] < best[i]) {
6627 * Find the next best Blue zone in the hystogram.
6628 * Return the weight of the found zone.
6633 short *zhyst, /* the zones hystogram */
6634 short *physt, /* the points hystogram */
6635 short *ozhyst, /* the other zones hystogram */
6636 int *bluetab /* where to put the found zone */
6639 int i, j, w, max, ind, first, last;
6641 /* find the highest point in the zones hystogram */
6642 /* if we have a plateau, take its center */
6643 /* if we have multiple peaks, take the first one */
6647 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
6652 } else if (w == max) {
6657 ind = (first + last) / 2;
6659 if (max == 0) /* no zones left */
6662 /* now we reuse `first' and `last' as inclusive borders of the zone */
6664 last = ind + (MAXBLUEWIDTH - 1);
6666 /* our maximal width is far too big, so we try to make it narrower */
6668 j = (w & 1); /* a pseudo-random bit */
6670 while (physt[first] == 0)
6672 while (physt[last] == 0)
6674 if (last - first < (MAXBLUEWIDTH * 2 / 3) || (max - w) * 10 > max)
6677 if (physt[first] < physt[last]
6678 || physt[first] == physt[last] && j) {
6679 if (physt[first] * 20 > w) /* if weight is >5%,
6686 if (physt[last] * 20 > w) /* if weight is >5%,
6696 bluetab[0] = first - HYSTBASE;
6697 bluetab[1] = last - HYSTBASE;
6699 /* invalidate all the zones overlapping with this one */
6700 /* the constant of 2 is determined by the default value of BlueFuzz */
6701 for (i = first - (MAXBLUEWIDTH - 1) - 2; i <= last + 2; i++)
6702 if (i >= 0 && i < MAXHYST) {
6710 * Try to find the Blue Values, bounding box and italic angle
6716 /* hystograms for upper and lower zones */
6717 short hystl[MAXHYST];
6718 short hystu[MAXHYST];
6719 short zuhyst[MAXHYST];
6720 short zlhyst[MAXHYST];
6722 int i, j, k, w, max;
6727 /* find the lowest and highest points of glyphs */
6728 /* and by the way build the values for FontBBox */
6729 /* and build the hystogram for the ItalicAngle */
6731 /* re-use hystl for the hystogram of italic angle */
6733 bbox[0] = bbox[1] = 5000;
6734 bbox[2] = bbox[3] = -5000;
6736 for (i = 0; i < MAXHYST; i++)
6741 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6742 if (g->flags & GF_USED) {
6747 for (ge = g->entries; ge != 0; ge = ge->next) {
6748 if (ge->type == GE_LINE) {
6750 j = ge->iy3 - ge->prev->iy3;
6751 k = ge->ix3 - ge->prev->ix3;
6753 ang = atan2(-k, j) * 180.0 / M_PI;
6755 ang = atan2(k, -j) * 180.0 / M_PI;
6759 if (ang > -45.0 && ang < 45.0) {
6761 * be careful to not overflow
6764 hystl[HYSTBASE + (int) (ang * 10.0)] += (k * k + j * j) / 4;
6766 if (ge->iy3 == ge->prev->iy3) {
6767 if (ge->iy3 <= g->rymin) {
6771 if (ge->iy3 >= g->rymax) {
6776 if (ge->iy3 < g->rymin) {
6780 if (ge->iy3 > g->rymax) {
6785 } else if (ge->type == GE_CURVE) {
6786 if (ge->iy3 < g->rymin) {
6790 if (ge->iy3 > g->rymax) {
6795 if (ge->type == GE_LINE || ge->type == GE_CURVE) {
6796 if (ge->ix3 < bbox[0])
6798 if (ge->ix3 > bbox[2])
6800 if (ge->iy3 < bbox[1])
6802 if (ge->iy3 > bbox[3])
6809 /* get the most popular angle */
6812 for (i = 0; i < MAXHYST; i++) {
6818 ang = (double) (max - HYSTBASE) / 10.0;
6819 WARNING_2 fprintf(stderr, "Guessed italic angle: %f\n", ang);
6820 if (italic_angle == 0.0)
6823 /* build the hystogram of the lower points */
6824 for (i = 0; i < MAXHYST; i++)
6827 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6828 if ((g->flags & GF_USED)
6829 && g->rymin + HYSTBASE >= 0 && g->rymin < MAXHYST - HYSTBASE) {
6830 hystl[g->rymin + HYSTBASE]++;
6834 /* build the hystogram of the upper points */
6835 for (i = 0; i < MAXHYST; i++)
6838 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6839 if ((g->flags & GF_USED)
6840 && g->rymax + HYSTBASE >= 0 && g->rymax < MAXHYST - HYSTBASE) {
6841 hystu[g->rymax + HYSTBASE]++;
6845 /* build the hystogram of all the possible lower zones with max width */
6846 for (i = 0; i < MAXHYST; i++)
6849 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
6850 for (j = 0; j < MAXBLUEWIDTH; j++)
6851 zlhyst[i] += hystl[i + j];
6854 /* build the hystogram of all the possible upper zones with max width */
6855 for (i = 0; i < MAXHYST; i++)
6858 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
6859 for (j = 0; j < MAXBLUEWIDTH; j++)
6860 zuhyst[i] += hystu[i + j];
6863 /* find the baseline */
6864 w = bestblue(zlhyst, hystl, zuhyst, &bluevalues[0]);
6866 fprintf(stderr, "BaselineBlue zone %d%% %d...%d\n", w * 100 / nchars,
6867 bluevalues[0], bluevalues[1]);
6869 if (w == 0) /* no baseline, something weird */
6872 /* find the upper zones */
6873 for (nblues = 2; nblues < 14; nblues += 2) {
6874 w = bestblue(zuhyst, hystu, zlhyst, &bluevalues[nblues]);
6877 fprintf(stderr, "Blue zone %d%% %d...%d\n", w * 100 / nchars,
6878 bluevalues[nblues], bluevalues[nblues+1]);
6880 if (w * 20 < nchars)
6881 break; /* don't save this zone */
6884 /* find the lower zones */
6885 for (notherb = 0; notherb < 10; notherb += 2) {
6886 w = bestblue(zlhyst, hystl, zuhyst, &otherblues[notherb]);
6889 fprintf(stderr, "OtherBlue zone %d%% %d...%d\n", w * 100 / nchars,
6890 otherblues[notherb], otherblues[notherb+1]);
6893 if (w * 20 < nchars)
6894 break; /* don't save this zone */
6900 * Find the actual width of the glyph and modify the
6901 * description to reflect it. Not guaranteed to do
6902 * any good, may make character spacing too wide.
6906 docorrectwidth(void)
6912 int maxwidth, minsp;
6914 /* enforce this minimal spacing,
6915 * we limit the amount of the enforced spacing to avoid
6916 * spacing the bold wonts too widely
6918 minsp = (stdhw>60 || stdhw<10)? 60 : stdhw;
6920 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6921 g->oldwidth=g->scaledwidth; /* save the old width, will need for AFM */
6923 if (correctwidth && g->flags & GF_USED) {
6926 for (ge = g->entries; ge != 0; ge = ge->next) {
6927 if (ge->type != GE_LINE && ge->type != GE_CURVE)
6930 if (ge->ix3 <= xmin) {
6933 if (ge->ix3 >= xmax) {
6938 maxwidth=xmax+minsp;
6939 if( g->scaledwidth < maxwidth ) {
6940 g->scaledwidth = maxwidth;
6941 WARNING_3 fprintf(stderr, "glyph %s: extended from %d to %d\n",
6942 g->name, g->oldwidth, g->scaledwidth );
6950 * Try to find the typical stem widths
6954 stemstatistics(void)
6956 #define MINDIST 10 /* minimal distance between the widths */
6957 int hyst[MAXHYST+MINDIST*2];
6965 /* start with typical stem width */
6969 /* build the hystogram of horizontal stem widths */
6970 memset(hyst, 0, sizeof hyst);
6972 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6973 if (g->flags & GF_USED) {
6976 for (j = 0; j < g->nhs; j += 2) {
6977 if ((s[j].flags | s[j + 1].flags) & ST_END)
6979 w = s[j + 1].value - s[j].value+1;
6980 if(w==20) /* split stems should not be counted */
6982 if (w > 0 && w < MAXHYST - 1) {
6984 * handle some fuzz present in
6987 hyst[w+MINDIST] += MINDIST-1;
6988 for(k=1; k<MINDIST-1; k++) {
6989 hyst[w+MINDIST + k] += MINDIST-1-k;
6990 hyst[w+MINDIST - k] += MINDIST-1-k;
6997 /* find 12 most frequent values */
6998 ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdhw);
7000 /* store data in stemsnaph */
7001 for (i = 0; i < ns; i++)
7002 stemsnaph[i] = best[i];
7006 /* build the hystogram of vertical stem widths */
7007 memset(hyst, 0, sizeof hyst);
7009 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
7010 if (g->flags & GF_USED) {
7012 for (j = 0; j < g->nvs; j += 2) {
7013 if ((s[j].flags | s[j + 1].flags) & ST_END)
7015 w = s[j + 1].value - s[j].value+1;
7016 if (w > 0 && w < MAXHYST - 1) {
7018 * handle some fuzz present in
7021 hyst[w+MINDIST] += MINDIST-1;
7022 for(k=1; k<MINDIST-1; k++) {
7023 hyst[w+MINDIST + k] += MINDIST-1-k;
7024 hyst[w+MINDIST - k] += MINDIST-1-k;
7031 /* find 12 most frequent values */
7032 ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdvw);
7034 /* store data in stemsnaph */
7035 for (i = 0; i < ns; i++)
7036 stemsnapv[i] = best[i];
7045 * A funny thing: TTF paths are going in reverse direction compared
7046 * to Type1. So after all (because the rest of logic uses TTF
7047 * path directions) we have to reverse the paths.
7049 * It was a big headache to discover that.
7052 /* works on both int and float paths */
7060 GENTRY *ge, *nge, *pge;
7065 for (ge = from; ge != 0 && ge != to; ge = ge->next) {
7066 if(ge->type == GE_LINE || ge->type == GE_CURVE) {
7067 if (ISDBG(REVERSAL))
7068 fprintf(stderr, "reverse path 0x%x <- 0x%x, 0x%x\n", ge, ge->prev, ge->bkwd);
7070 /* cut out the path itself */
7071 pge = ge->prev; /* GE_MOVE */
7073 fprintf(stderr, "**! No MOVE before line !!! Fatal. ****\n");
7076 nge = ge->bkwd->next; /* GE_PATH */
7079 ge->bkwd->next = 0; /* mark end of chain */
7081 /* remember the starting point */
7082 if(ge->flags & GEF_FLOAT) {
7083 flast[0] = pge->fx3;
7084 flast[1] = pge->fy3;
7086 ilast[0] = pge->ix3;
7087 ilast[1] = pge->iy3;
7090 /* then reinsert them in backwards order */
7091 for(cur = ge; cur != 0; cur = next ) {
7092 next = cur->next; /* or addgeafter() will screw it up */
7093 if(cur->flags & GEF_FLOAT) {
7094 for(i=0; i<2; i++) {
7095 /* reverse the direction of path element */
7096 f = cur->fpoints[i][0];
7097 cur->fpoints[i][0] = cur->fpoints[i][1];
7098 cur->fpoints[i][1] = f;
7100 flast[i] = cur->fpoints[i][2];
7101 cur->fpoints[i][2] = f;
7104 for(i=0; i<2; i++) {
7105 /* reverse the direction of path element */
7106 n = cur->ipoints[i][0];
7107 cur->ipoints[i][0] = cur->ipoints[i][1];
7108 cur->ipoints[i][1] = n;
7110 ilast[i] = cur->ipoints[i][2];
7111 cur->ipoints[i][2] = n;
7114 addgeafter(pge, cur);
7117 /* restore the starting point */
7118 if(ge->flags & GEF_FLOAT) {
7119 pge->fx3 = flast[0];
7120 pge->fy3 = flast[1];
7122 pge->ix3 = ilast[0];
7123 pge->iy3 = ilast[1];
7137 reversepathsfromto(g->entries, NULL);
7140 /* add a kerning pair information, scales the value */
7149 static unsigned char *bits = 0;
7151 GLYPH *g = &glyph_list[id1];
7155 if(unscval == 0 || id1 >= numglyphs || id2 >= numglyphs)
7158 if( (glyph_list[id1].flags & GF_USED)==0
7159 || (glyph_list[id2].flags & GF_USED)==0 )
7163 bits = calloc( BITMAP_BYTES(numglyphs), 1);
7165 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
7172 /* refill the bitmap cache */
7173 memset(bits, 0,BITMAP_BYTES(numglyphs));
7175 for(i=g->kerncount; i>0; i--) {
7177 SET_BITMAP(bits, n);
7182 if(IS_BITMAP(bits, id2))
7183 return; /* duplicate */
7185 if(g->kerncount <= g->kernalloc) {
7187 p = realloc(g->kern, sizeof(struct kern) * g->kernalloc);
7189 fprintf (stderr, "** realloc failed, kerning data will be incomplete\n");
7194 SET_BITMAP(bits, id2);
7195 p = &g->kern[g->kerncount];
7197 p->val = iscale(unscval) - (g->scaledwidth - g->oldwidth);
7202 /* print out the kerning information */
7213 if( kerning_pairs == 0 )
7216 fprintf(afm_file, "StartKernData\n");
7217 fprintf(afm_file, "StartKernPairs %hd\n", kerning_pairs);
7219 for(i=0; i<numglyphs; i++) {
7221 if( (g->flags & GF_USED) ==0)
7224 for(j=g->kerncount; j>0; j--, p++) {
7225 fprintf(afm_file, "KPX %s %s %d\n", g->name,
7226 glyph_list[ p->id ].name, p->val );
7230 fprintf(afm_file, "EndKernPairs\n");
7231 fprintf(afm_file, "EndKernData\n");
7238 ** This function is commented out because the information
7239 ** collected by it is not used anywhere else yet. Now
7240 ** it only collects the directions of contours. And the
7241 ** direction of contours gets fixed already in draw_glyf().
7243 ***********************************************
7245 ** Here we expect that the paths are already closed.
7246 ** We also expect that the contours do not intersect
7247 ** and that curves doesn't cross any border of quadrant.
7249 ** Find which contours go inside which and what is
7250 ** their proper direction. Then fix the direction
7251 ** to make it right.
7255 #define MAXCONT 1000
7262 CONTOUR cont[MAXCONT];
7263 short ymax[MAXCONT]; /* the highest point */
7264 short xofmax[MAXCONT]; /* X-coordinate of any point
7266 short ymin[MAXCONT]; /* the lowest point */
7267 short xofmin[MAXCONT]; /* X-coordinate of any point
7269 short count[MAXCONT]; /* count of lines */
7270 char dir[MAXCONT]; /* in which direction they must go */
7271 GENTRY *start[MAXCONT], *minptr[MAXCONT], *maxptr[MAXCONT];
7274 int dx1, dy1, dx2, dy2;
7277 /* find the contours and their most upper/lower points */
7281 for (ge = g->entries; ge != 0; ge = ge->next) {
7282 if (ge->type == GE_LINE || ge->type == GE_CURVE) {
7283 if (ge->iy3 > ymax[ncont]) {
7284 ymax[ncont] = ge->iy3;
7285 xofmax[ncont] = ge->ix3;
7288 if (ge->iy3 < ymin[ncont]) {
7289 ymin[ncont] = ge->iy3;
7290 xofmin[ncont] = ge->ix3;
7294 if (ge->frwd != ge->next) {
7295 start[ncont++] = ge->frwd;
7296 ymax[ncont] = -5000;
7301 /* determine the directions of contours */
7302 for (i = 0; i < ncont; i++) {
7306 if (ge->type == GE_CURVE) {
7307 dx1 = ge->ix3 - ge->ix2;
7308 dy1 = ge->iy3 - ge->iy2;
7310 if (dx1 == 0 && dy1 == 0) { /* a pathological case */
7311 dx1 = ge->ix3 - ge->ix1;
7312 dy1 = ge->iy3 - ge->iy1;
7314 if (dx1 == 0 && dy1 == 0) { /* a more pathological
7316 dx1 = ge->ix3 - ge->prev->ix3;
7317 dy1 = ge->iy3 - ge->prev->iy3;
7320 dx1 = ge->ix3 - ge->prev->ix3;
7321 dy1 = ge->iy3 - ge->prev->iy3;
7323 if (nge->type == GE_CURVE) {
7324 dx2 = ge->ix3 - nge->ix1;
7325 dy2 = ge->iy3 - nge->iy1;
7326 if (dx1 == 0 && dy1 == 0) { /* a pathological case */
7327 dx2 = ge->ix3 - nge->ix2;
7328 dy2 = ge->iy3 - nge->iy2;
7330 if (dx1 == 0 && dy1 == 0) { /* a more pathological
7332 dx2 = ge->ix3 - nge->ix3;
7333 dy2 = ge->iy3 - nge->iy3;
7336 dx2 = ge->ix3 - nge->ix3;
7337 dy2 = ge->iy3 - nge->iy3;
7340 /* compare angles */
7341 cont[i].direction = DIR_INNER;
7344 cont[i].direction = DIR_OUTER;
7345 } else if (dy2 == 0) {
7347 cont[i].direction = DIR_OUTER;
7348 } else if (dx2 * dy1 < dx1 * dy2)
7349 cont[i].direction = DIR_OUTER;
7351 cont[i].ymin = ymin[i];
7352 cont[i].xofmin = xofmin[i];
7355 /* save the information that may be needed further */
7356 g->ncontours = ncont;
7358 g->contours = malloc(sizeof(CONTOUR) * ncont);
7359 if (g->contours == 0) {
7360 fprintf(stderr, "***** Memory allocation error *****\n");
7363 memcpy(g->contours, cont, sizeof(CONTOUR) * ncont);