?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
added missing member initialization.
[swftools.git] / pdf2swf / ttf2pt1 / pt1.c
blob3f2bc0867f7f32abc1d036bdecad62ba94850c71
1 /*
2 * see COPYRIGHT
3 */
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <sys/types.h>
9 #include <sys/stat.h>
10 #include <fcntl.h>
11 #include <time.h>
12 #include <ctype.h>
13 #include <math.h>
14
15 #ifndef WIN32
16 # include <netinet/in.h>
17 # include <unistd.h>
18 #else
19 # include "win_missing.h"
20 #endif
21
22 #include "ttf.h"
23 #include "pt1.h"
24 #include "global.h"
25
26 /* big and small values for comparisons */
27 #define FBIGVAL (1e20)
28 #define FEPS (100000./FBIGVAL)
29
30 /* names of the axes */
31 #define X 0
32 #define Y 1
33
34 /* the GENTRY extension structure used in fforceconcise() */
35
36 struct gex_con {
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 */
40
41 /* number of reference dots taken from each curve */
42 #define NREFDOTS 3
43
44 double dots[NREFDOTS][2]; /* reference dots */
45
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 */
53
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 */
61
62 /* possibly can be joined with conditions:
63 * (in order of increasing preference, the numeric order is important)
64 */
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 */
70
71 #define GEXF_JMASK 0x00001F00 /* the mask of all above */
72 #define GEXF_JCVMASK 0x00001E00 /* the mask of all above except JLINE */
73
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))
84
85 #define GEXF_VERT 0x00100000 /* is nearly vertical */
86 #define GEXF_HOR 0x00200000 /* is nearly horizontal */
87 #define GEXF_FLAT 0x00400000 /* is nearly flat */
88
89 #define GEXF_VDOTS 0x01000000 /* the dots are valid */
90
91 signed char isd[2 /*X,Y*/]; /* signs of the sizes */
92 };
93 typedef struct gex_con GEX_CON;
94
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)
106
107 /* performance statistics about guessing the concise curves */
108 static int ggoodcv=0, ggoodcvdots=0, gbadcv=0, gbadcvdots=0;
109
110 int stdhw, stdvw; /* dominant stems widths */
111 int stemsnaph[12], stemsnapv[12]; /* most typical stem width */
112
113 int bluevalues[14];
114 int nblues;
115 int otherblues[10];
116 int notherb;
117 int bbox[4]; /* the FontBBox array */
118 double italic_angle;
119
120 GLYPH *glyph_list;
121 int encoding[ENCTABSZ]; /* inverse of glyph[].char_no */
122 int kerning_pairs = 0;
123
124 /* prototypes */
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);
155
156 int
157 isign(
158 int x
159 )
160 {
161 if (x > 0)
162 return 1;
163 else if (x < 0)
164 return -1;
165 else
166 return 0;
167 }
168
169 int
170 fsign(
171 double x
172 )
173 {
174 if (x > 0.0)
175 return 1;
176 else if (x < 0.0)
177 return -1;
178 else
179 return 0;
180 }
181
182 static GENTRY *
183 newgentry(
184 int flags
185 )
186 {
187 GENTRY *ge;
188
189 ge = calloc(1, sizeof(GENTRY));
190
191 if (ge == 0) {
192 fprintf(stderr, "***** Memory allocation error *****\n");
193 exit(255);
194 }
195 ge->stemid = -1;
196 ge->flags = flags;
197 /* the rest is set to 0 by calloc() */
198 return ge;
199 }
200
201 /*
202 * Routines to print out Postscript functions with optimization
203 */
204
205 void
206 rmoveto(
207 int dx,
208 int dy
209 )
210 {
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);
215 else
216 fprintf(pfa_file, "%d %d rmoveto\n", dx, dy);
217 }
218
219 void
220 rlineto(
221 int dx,
222 int dy
223 )
224 {
225 if (optimize && dx == 0 && dy == 0) /* for special pathologic
226 * case */
227 return;
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);
232 else
233 fprintf(pfa_file, "%d %d rlineto\n", dx, dy);
234 }
235
236 void
237 rrcurveto(
238 int dx1,
239 int dy1,
240 int dx2,
241 int dy2,
242 int dx3,
243 int dy3
244 )
245 {
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",
253 dx1, dx2, dy2, dy3);
254 else if (optimize && dx1 == 0 && dy3 == 0)
255 fprintf(pfa_file, "%d %d %d %d vhcurveto\n",
256 dy1, dx2, dy2, dx3);
257 else
258 fprintf(pfa_file, "%d %d %d %d %d %d rrcurveto\n",
259 dx1, dy1, dx2, dy2, dx3, dy3);
260 }
261
262 void
263 closepath(void)
264 {
265 fprintf(pfa_file, "closepath\n");
266 }
267
268 /*
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.
276 */
277
278 /*
279 ** Routine that checks integrity of the path, for debugging
280 */
281
282 void
283 assertpath(
284 GENTRY * from,
285 char *file,
286 int line,
287 char *name
288 )
289 {
290 GENTRY *first, *pe, *ge;
291 int isfloat;
292
293 if(from==0)
294 return;
295 isfloat = (from->flags & GEF_FLOAT);
296 pe = from->prev;
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);
302 abort();
303 }
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",
307 pe, ge, ge->prev);
308 abort();
309 }
310
311 switch(ge->type) {
312 case GE_MOVE:
313 break;
314 case GE_PATH:
315 if (ge->prev == 0) {
316 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
317 fprintf(stderr, "empty path at 0x%x \n", ge);
318 abort();
319 }
320 break;
321 case GE_LINE:
322 case GE_CURVE:
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);
327 abort();
328 }
329 if(ge->prev->type == GE_MOVE) {
330 first = ge;
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);
335 abort();
336 }
337 }
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);
343 abort();
344 }
345 }
346 break;
347 }
348
349 }
350 }
351
352 void
353 assertisfloat(
354 GLYPH *g,
355 char *msg
356 )
357 {
358 if( !(g->flags & GF_FLOAT) ) {
359 fprintf(stderr, "**! Glyph %s is not float: %s\n", g->name, msg);
360 abort();
361 }
362 if(g->lastentry) {
363 if( !(g->lastentry->flags & GEF_FLOAT) ) {
364 fprintf(stderr, "**! Glyphs %s last entry is int: %s\n", g->name, msg);
365 abort();
366 }
367 }
368 }
369
370 void
371 assertisint(
372 GLYPH *g,
373 char *msg
374 )
375 {
376 if( (g->flags & GF_FLOAT) ) {
377 fprintf(stderr, "**! Glyph %s is not int: %s\n", g->name, msg);
378 abort();
379 }
380 if(g->lastentry) {
381 if( (g->lastentry->flags & GEF_FLOAT) ) {
382 fprintf(stderr, "**! Glyphs %s last entry is float: %s\n", g->name, msg);
383 abort();
384 }
385 }
386 }
387
388
389 /*
390 * Routines to save the generated data about glyph
391 */
392
393 void
394 fg_rmoveto(
395 GLYPH * g,
396 double x,
397 double y)
398 {
399 GENTRY *oge;
400
401 if (ISDBG(BUILDG))
402 fprintf(stderr, "%s: f rmoveto(%g, %g)\n", g->name, x, y);
403
404 assertisfloat(g, "adding float MOVE");
405
406 if ((oge = g->lastentry) != 0) {
407 if (oge->type == GE_MOVE) { /* just eat up the first move */
408 oge->fx3 = x;
409 oge->fy3 = y;
410 } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
411 fprintf(stderr, "Glyph %s: MOVE in middle of path\n", g->name);
412 } else {
413 GENTRY *nge;
414
415 nge = newgentry(GEF_FLOAT);
416 nge->type = GE_MOVE;
417 nge->fx3 = x;
418 nge->fy3 = y;
419
420 oge->next = nge;
421 nge->prev = oge;
422 g->lastentry = nge;
423 }
424 } else {
425 GENTRY *nge;
426
427 nge = newgentry(GEF_FLOAT);
428 nge->type = GE_MOVE;
429 nge->fx3 = x;
430 nge->fy3 = y;
431 nge->bkwd = (GENTRY*)&g->entries;
432 g->entries = g->lastentry = nge;
433 }
434
435 if (0 && ISDBG(BUILDG))
436 dumppaths(g, NULL, NULL);
437 }
438
439 void
440 ig_rmoveto(
441 GLYPH * g,
442 int x,
443 int y)
444 {
445 GENTRY *oge;
446
447 if (ISDBG(BUILDG))
448 fprintf(stderr, "%s: i rmoveto(%d, %d)\n", g->name, x, y);
449
450 assertisint(g, "adding int MOVE");
451
452 if ((oge = g->lastentry) != 0) {
453 if (oge->type == GE_MOVE) { /* just eat up the first move */
454 oge->ix3 = x;
455 oge->iy3 = y;
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);
458 } else {
459 GENTRY *nge;
460
461 nge = newgentry(0);
462 nge->type = GE_MOVE;
463 nge->ix3 = x;
464 nge->iy3 = y;
465
466 oge->next = nge;
467 nge->prev = oge;
468 g->lastentry = nge;
469 }
470 } else {
471 GENTRY *nge;
472
473 nge = newgentry(0);
474 nge->type = GE_MOVE;
475 nge->ix3 = x;
476 nge->iy3 = y;
477 nge->bkwd = (GENTRY*)&g->entries;
478 g->entries = g->lastentry = nge;
479 }
480
481 }
482
483 void
484 fg_rlineto(
485 GLYPH * g,
486 double x,
487 double y)
488 {
489 GENTRY *oge, *nge;
490
491 if (ISDBG(BUILDG))
492 fprintf(stderr, "%s: f rlineto(%g, %g)\n", g->name, x, y);
493
494 assertisfloat(g, "adding float LINE");
495
496 nge = newgentry(GEF_FLOAT);
497 nge->type = GE_LINE;
498 nge->fx3 = x;
499 nge->fy3 = y;
500
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 */
504 free(nge);
505 return;
506 }
507 if (g->path == 0) {
508 g->path = nge;
509 nge->bkwd = nge->frwd = nge;
510 } else {
511 oge->frwd = nge;
512 nge->bkwd = oge;
513 g->path->bkwd = nge;
514 nge->frwd = g->path;
515 }
516
517 oge->next = nge;
518 nge->prev = oge;
519 g->lastentry = nge;
520 } else {
521 WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
522 free(nge);
523 }
524
525 if (0 && ISDBG(BUILDG))
526 dumppaths(g, NULL, NULL);
527 }
528
529 void
530 ig_rlineto(
531 GLYPH * g,
532 int x,
533 int y)
534 {
535 GENTRY *oge, *nge;
536
537 if (ISDBG(BUILDG))
538 fprintf(stderr, "%s: i rlineto(%d, %d)\n", g->name, x, y);
539
540 assertisint(g, "adding int LINE");
541
542 nge = newgentry(0);
543 nge->type = GE_LINE;
544 nge->ix3 = x;
545 nge->iy3 = y;
546
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 */
550 free(nge);
551 return;
552 }
553 if (g->path == 0) {
554 g->path = nge;
555 nge->bkwd = nge->frwd = nge;
556 } else {
557 oge->frwd = nge;
558 nge->bkwd = oge;
559 g->path->bkwd = nge;
560 nge->frwd = g->path;
561 }
562
563 oge->next = nge;
564 nge->prev = oge;
565 g->lastentry = nge;
566 } else {
567 WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
568 free(nge);
569 }
570
571 }
572
573 void
574 fg_rrcurveto(
575 GLYPH * g,
576 double x1,
577 double y1,
578 double x2,
579 double y2,
580 double x3,
581 double y3)
582 {
583 GENTRY *oge, *nge;
584
585 oge = g->lastentry;
586
587 if (ISDBG(BUILDG))
588 fprintf(stderr, "%s: f rrcurveto(%g, %g, %g, %g, %g, %g)\n"
589 ,g->name, x1, y1, x2, y2, x3, y3);
590
591 assertisfloat(g, "adding float CURVE");
592
593 if (oge && oge->fx3 == x1 && x1 == x2 && x2 == x3) /* check if it's
594 * actually a line */
595 fg_rlineto(g, x1, y3);
596 else if (oge && oge->fy3 == y1 && y1 == y2 && y2 == y3)
597 fg_rlineto(g, x3, y1);
598 else {
599 nge = newgentry(GEF_FLOAT);
600 nge->type = GE_CURVE;
601 nge->fx1 = x1;
602 nge->fy1 = y1;
603 nge->fx2 = x2;
604 nge->fy2 = y2;
605 nge->fx3 = x3;
606 nge->fy3 = y3;
607
608 if (oge != 0) {
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 */
612 return;
613 }
614 if (g->path == 0) {
615 g->path = nge;
616 nge->bkwd = nge->frwd = nge;
617 } else {
618 oge->frwd = nge;
619 nge->bkwd = oge;
620 g->path->bkwd = nge;
621 nge->frwd = g->path;
622 }
623
624 oge->next = nge;
625 nge->prev = oge;
626 g->lastentry = nge;
627 } else {
628 WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
629 free(nge);
630 }
631 }
632
633 if (0 && ISDBG(BUILDG))
634 dumppaths(g, NULL, NULL);
635 }
636
637 void
638 ig_rrcurveto(
639 GLYPH * g,
640 int x1,
641 int y1,
642 int x2,
643 int y2,
644 int x3,
645 int y3)
646 {
647 GENTRY *oge, *nge;
648
649 oge = g->lastentry;
650
651 if (ISDBG(BUILDG))
652 fprintf(stderr, "%s: i rrcurveto(%d, %d, %d, %d, %d, %d)\n"
653 ,g->name, x1, y1, x2, y2, x3, y3);
654
655 assertisint(g, "adding int CURVE");
656
657 if (oge && oge->ix3 == x1 && x1 == x2 && x2 == x3) /* check if it's
658 * actually a line */
659 ig_rlineto(g, x1, y3);
660 else if (oge && oge->iy3 == y1 && y1 == y2 && y2 == y3)
661 ig_rlineto(g, x3, y1);
662 else {
663 nge = newgentry(0);
664 nge->type = GE_CURVE;
665 nge->ix1 = x1;
666 nge->iy1 = y1;
667 nge->ix2 = x2;
668 nge->iy2 = y2;
669 nge->ix3 = x3;
670 nge->iy3 = y3;
671
672 if (oge != 0) {
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 */
676 return;
677 }
678 if (g->path == 0) {
679 g->path = nge;
680 nge->bkwd = nge->frwd = nge;
681 } else {
682 oge->frwd = nge;
683 nge->bkwd = oge;
684 g->path->bkwd = nge;
685 nge->frwd = g->path;
686 }
687
688 oge->next = nge;
689 nge->prev = oge;
690 g->lastentry = nge;
691 } else {
692 WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
693 free(nge);
694 }
695 }
696 }
697
698 void
699 g_closepath(
700 GLYPH * g
701 )
702 {
703 GENTRY *oge, *nge;
704
705 if (ISDBG(BUILDG))
706 fprintf(stderr, "%s: closepath\n", g->name);
707
708 oge = g->lastentry;
709
710 if (g->path == 0) {
711 WARNING_1 fprintf(stderr, "Warning: **** closepath on empty path in glyph \"%s\" ****\n",
712 g->name);
713 if (oge == 0) {
714 WARNING_1 fprintf(stderr, "No previois entry\n");
715 } else {
716 WARNING_1 fprintf(stderr, "Previous entry type: %c\n", oge->type);
717 if (oge->type == GE_MOVE) {
718 g->lastentry = oge->prev;
719 if (oge->prev == 0)
720 g->entries = 0;
721 else
722 g->lastentry->next = 0;
723 free(oge);
724 }
725 }
726 return;
727 }
728
729 nge = newgentry(oge->flags & GEF_FLOAT); /* keep the same type */
730 nge->type = GE_PATH;
731
732 g->path = 0;
733
734 oge->next = nge;
735 nge->prev = oge;
736 g->lastentry = nge;
737
738 if (0 && ISDBG(BUILDG))
739 dumppaths(g, NULL, NULL);
740 }
741
742 /*
743 * * SB * Routines to smooth and fix the glyphs
744 */
745
746 /*
747 ** we don't want to see the curves with coinciding middle and
748 ** outer points
749 */
750
751 static void
752 fixcvends(
753 GENTRY * ge
754 )
755 {
756 int dx, dy;
757 int x0, y0, x1, y1, x2, y2, x3, y3;
758
759 if (ge->type != GE_CURVE)
760 return;
761
762 if(ge->flags & GEF_FLOAT) {
763 fprintf(stderr, "**! fixcvends(0x%x) on floating entry, ABORT\n", ge);
764 abort(); /* dump core */
765 }
766
767 x0 = ge->prev->ix3;
768 y0 = ge->prev->iy3;
769 x1 = ge->ix1;
770 y1 = ge->iy1;
771 x2 = ge->ix2;
772 y2 = ge->iy2;
773 x3 = ge->ix3;
774 y3 = ge->iy3;
775
776
777 /* look at the start of the curve */
778 if (x1 == x0 && y1 == y0) {
779 dx = x2 - x1;
780 dy = y2 - y1;
781
782 if (dx == 0 && dy == 0
783 || x2 == x3 && y2 == y3) {
784 /* Oops, we actually have a straight line */
785 /*
786 * if it's small, we hope that it will get optimized
787 * later
788 */
789 if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
790 ge->ix1 = x3;
791 ge->iy1 = y3;
792 ge->ix2 = x0;
793 ge->iy2 = y0;
794 } else {/* just make it a line */
795 ge->type = GE_LINE;
796 }
797 } else {
798 if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very
799 * small */
800 ge->ix1 = x2;
801 ge->iy1 = y2;
802 } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */
803 ge->ix1 += dx / 2;
804 ge->iy1 += dy / 2;
805 } else {
806 ge->ix1 += dx / 4;
807 ge->iy1 += dy / 4;
808 }
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);
813 } else {
814 if (abs(x3 - x0) * abs(ge->iy1 - y0) < abs(y3 - y0) * abs(ge->ix1 - x0))
815 ge->iy1 += isign(dy);
816 }
817
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);
824 } else {
825 if (abs(x3 - x0) * abs(y3 - ge->iy2) < abs(y3 - y0) * abs(x3 - ge->ix2))
826 ge->ix1 -= isign(x3 - x2);
827 }
828
829 }
830 } else if (x2 == x3 && y2 == y3) {
831 dx = x1 - x2;
832 dy = y1 - y2;
833
834 if (dx == 0 && dy == 0) {
835 /* Oops, we actually have a straight line */
836 /*
837 * if it's small, we hope that it will get optimized
838 * later
839 */
840 if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
841 ge->ix1 = x3;
842 ge->iy1 = y3;
843 ge->ix2 = x0;
844 ge->iy2 = y0;
845 } else {/* just make it a line */
846 ge->type = GE_LINE;
847 }
848 } else {
849 if (abs(dx) < 4 && abs(dy) < 4) { /* consider it very
850 * small */
851 ge->ix2 = x1;
852 ge->iy2 = y1;
853 } else if (abs(dx) < 8 && abs(dy) < 8) { /* consider it small */
854 ge->ix2 += dx / 2;
855 ge->iy2 += dy / 2;
856 } else {
857 ge->ix2 += dx / 4;
858 ge->iy2 += dy / 4;
859 }
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);
864 } else {
865 if (abs(x3 - x0) * abs(ge->iy2 - y3) < abs(y3 - y0) * abs(ge->ix2 - x3))
866 ge->iy2 += isign(dy);
867 }
868
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);
875 } else {
876 if (abs(x3 - x0) * abs(y0 - ge->iy1) < abs(y3 - y0) * abs(x0 - ge->ix1))
877 ge->ix1 -= isign(x0 - x1);
878 }
879
880 }
881 }
882 }
883
884 /*
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.
889 **
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:
893 **
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
897 **
898 ** See CVDIR_* for exact definitions.
899 */
900
901 static void
902 fixcvdir(
903 GENTRY * ge,
904 int dir
905 )
906 {
907 int a, b, c, d;
908 double kk, kk1, kk2;
909 int changed;
910 int fdir, rdir;
911
912 if(ge->flags & GEF_FLOAT) {
913 fprintf(stderr, "**! fixcvdir(0x%x) on floating entry, ABORT\n", ge);
914 abort(); /* dump core */
915 }
916
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 */
920 else
921 rdir = (dir & CVDIR_REAR) - CVDIR_REQUAL;
922
923 fixcvends(ge);
924
925 c = isign(ge->ix3 - ge->prev->ix3); /* note the direction of
926 * curve */
927 d = isign(ge->iy3 - ge->prev->iy3);
928
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));
938
939 changed = 1;
940 while (changed) {
941 if (ISDBG(FIXCVDIR)) {
942 /* for debugging */
943 fprintf(stderr, "fixcvdir %d %d (%d %d %d %d %d %d) %f %f %f\n",
944 fdir, rdir,
945 ge->ix1 - ge->prev->ix3,
946 ge->iy1 - ge->prev->iy3,
947 ge->ix2 - ge->ix1,
948 ge->iy2 - ge->iy1,
949 ge->ix3 - ge->ix2,
950 ge->iy3 - ge->iy2,
951 kk1, kk, kk2);
952 }
953 changed = 0;
954
955 if (fdir > 0) {
956 if (kk1 > kk) { /* the front end has problems */
957 if (c * (ge->ix1 - ge->prev->ix3) > 0) {
958 ge->ix1 -= c;
959 changed = 1;
960 } if (d * (ge->iy2 - ge->iy1) > 0) {
961 ge->iy1 += d;
962 changed = 1;
963 }
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));
971 }
972 } else if (fdir < 0) {
973 if (kk1 < kk) { /* the front end has problems */
974 if (c * (ge->ix2 - ge->ix1) > 0) {
975 ge->ix1 += c;
976 changed = 1;
977 } if (d * (ge->iy1 - ge->prev->iy3) > 0) {
978 ge->iy1 -= d;
979 changed = 1;
980 }
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));
988 }
989 }
990 if (rdir > 0) {
991 if (kk2 < kk) { /* the rear end has problems */
992 if (c * (ge->ix2 - ge->ix1) > 0) {
993 ge->ix2 -= c;
994 changed = 1;
995 } if (d * (ge->iy3 - ge->iy2) > 0) {
996 ge->iy2 += d;
997 changed = 1;
998 }
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));
1006 }
1007 } else if (rdir < 0) {
1008 if (kk2 > kk) { /* the rear end has problems */
1009 if (c * (ge->ix3 - ge->ix2) > 0) {
1010 ge->ix2 += c;
1011 changed = 1;
1012 } if (d * (ge->iy2 - ge->iy1) > 0) {
1013 ge->iy2 -= d;
1014 changed = 1;
1015 }
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));
1023 }
1024 }
1025 }
1026 fixcvends(ge);
1027 }
1028
1029 /* Get the directions of ends of curve for further usage */
1030
1031 /* expects that the previous element is also float */
1032
1033 static int
1034 fgetcvdir(
1035 GENTRY * ge
1036 )
1037 {
1038 double a, b;
1039 double k, k1, k2;
1040 int dir = 0;
1041
1042 if( !(ge->flags & GEF_FLOAT) ) {
1043 fprintf(stderr, "**! fgetcvdir(0x%x) on int entry, ABORT\n", ge);
1044 abort(); /* dump core */
1045 }
1046
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);
1050
1051 a = fabs(ge->fy1 - ge->prev->fy3);
1052 b = fabs(ge->fx1 - ge->prev->fx3);
1053 if(a < FEPS) {
1054 if(b < FEPS) {
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);
1058 } else
1059 k1 = FBIGVAL;
1060 } else
1061 k1 = b / a;
1062
1063 a = fabs(ge->fy3 - ge->fy2);
1064 b = fabs(ge->fx3 - ge->fx2);
1065 if(a < FEPS) {
1066 if(b < FEPS) {
1067 a = fabs(ge->fy3 - ge->fy1);
1068 b = fabs(ge->fx3 - ge->fx1);
1069 k2 = a < FEPS ? (b < FEPS ? k : 100000.) : ( b / a);
1070 } else
1071 k2 = FBIGVAL;
1072 } else
1073 k2 = b / a;
1074
1075 if(fabs(k1-k) < 0.0001)
1076 dir |= CVDIR_FEQUAL;
1077 else if (k1 < k)
1078 dir |= CVDIR_FUP;
1079 else
1080 dir |= CVDIR_FDOWN;
1081
1082 if(fabs(k2-k) < 0.0001)
1083 dir |= CVDIR_REQUAL;
1084 else if (k2 > k)
1085 dir |= CVDIR_RUP;
1086 else
1087 dir |= CVDIR_RDOWN;
1088
1089 return dir;
1090 }
1091
1092
1093 /* expects that the previous element is also int */
1094
1095 static int
1096 igetcvdir(
1097 GENTRY * ge
1098 )
1099 {
1100 int a, b;
1101 double k, k1, k2;
1102 int dir = 0;
1103
1104 if(ge->flags & GEF_FLOAT) {
1105 fprintf(stderr, "**! igetcvdir(0x%x) on floating entry, ABORT\n", ge);
1106 abort(); /* dump core */
1107 }
1108
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);
1112
1113 a = ge->iy1 - ge->prev->iy3;
1114 b = ge->ix1 - ge->prev->ix3;
1115 if(a == 0) {
1116 if(b == 0) {
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);
1120 } else
1121 k1 = FBIGVAL;
1122 } else
1123 k1 = fabs((double) b / (double) a);
1124
1125 a = ge->iy3 - ge->iy2;
1126 b = ge->ix3 - ge->ix2;
1127 if(a == 0) {
1128 if(b == 0) {
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);
1132 } else
1133 k2 = FBIGVAL;
1134 } else
1135 k2 = fabs((double) b / (double) a);
1136
1137 if(fabs(k1-k) < 0.0001)
1138 dir |= CVDIR_FEQUAL;
1139 else if (k1 < k)
1140 dir |= CVDIR_FUP;
1141 else
1142 dir |= CVDIR_FDOWN;
1143
1144 if(fabs(k2-k) < 0.0001)
1145 dir |= CVDIR_REQUAL;
1146 else if (k2 > k)
1147 dir |= CVDIR_RUP;
1148 else
1149 dir |= CVDIR_RDOWN;
1150
1151 return dir;
1152 }
1153
1154 #if 0
1155 /* a function just to test the work of fixcvdir() */
1156 static void
1157 testfixcvdir(
1158 GLYPH * g
1159 )
1160 {
1161 GENTRY *ge;
1162 int dir;
1163
1164 for (ge = g->entries; ge != 0; ge = ge->next) {
1165 if (ge->type == GE_CURVE) {
1166 dir = igetcvdir(ge);
1167 fixcvdir(ge, dir);
1168 }
1169 }
1170 }
1171 #endif
1172
1173 static int
1174 iround(
1175 double val
1176 )
1177 {
1178 return (int) (val > 0 ? val + 0.5 : val - 0.5);
1179 }
1180
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)
1184 */
1185
1186 void
1187 dumppaths(
1188 GLYPH *g,
1189 GENTRY *start,
1190 GENTRY *end
1191 )
1192 {
1193 GENTRY *ge;
1194 int i;
1195 char mark=' ';
1196
1197 fprintf(stderr, "Glyph %s:\n", g->name);
1198
1199 /* now do the conversion */
1200 for(ge = g->entries; ge != 0; ge = ge->next) {
1201 if(ge == start)
1202 mark = '*';
1203 fprintf(stderr, " %c %8x", mark, ge);
1204 switch(ge->type) {
1205 case GE_MOVE:
1206 case GE_LINE:
1207 if(ge->flags & GEF_FLOAT)
1208 fprintf(stderr," %c float (%g, %g)\n", ge->type, ge->fx3, ge->fy3);
1209 else
1210 fprintf(stderr," %c int (%d, %d)\n", ge->type, ge->ix3, ge->iy3);
1211 break;
1212 case GE_CURVE:
1213 if(ge->flags & GEF_FLOAT) {
1214 fprintf(stderr," C float ");
1215 for(i=0; i<3; i++)
1216 fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
1217 fprintf(stderr,"\n");
1218 } else {
1219 fprintf(stderr," C int ");
1220 for(i=0; i<3; i++)
1221 fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1222 fprintf(stderr,"\n");
1223 }
1224 break;
1225 default:
1226 fprintf(stderr, " %c\n", ge->type);
1227 break;
1228 }
1229 if(ge == end)
1230 mark = ' ';
1231 }
1232 }
1233
1234 /*
1235 * Routine that converts all entries in the path from float to int
1236 */
1237
1238 void
1239 pathtoint(
1240 GLYPH *g
1241 )
1242 {
1243 GENTRY *ge;
1244 int x[3], y[3];
1245 int i;
1246
1247
1248 if(ISDBG(TOINT))
1249 fprintf(stderr, "TOINT: glyph %s\n", g->name);
1250 assertisfloat(g, "converting path to int\n");
1251
1252 fdelsmall(g, 1.0); /* get rid of sub-pixel contours */
1253 assertpath(g->entries, __FILE__, __LINE__, g->name);
1254
1255 /* 1st pass, collect the directions of the curves: have
1256 * to do that in advance, while everyting is float
1257 */
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",
1261 g->name);
1262 exit(1);
1263 }
1264 if(ge->type == GE_CURVE) {
1265 ge->dir = fgetcvdir(ge);
1266 }
1267 }
1268
1269 /* now do the conversion */
1270 for(ge = g->entries; ge != 0; ge = ge->next) {
1271 switch(ge->type) {
1272 case GE_MOVE:
1273 case GE_LINE:
1274 if(ISDBG(TOINT))
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 */
1279 ge->ixn[i] = x[0];
1280 ge->iyn[i] = y[0];
1281 }
1282 if(ISDBG(TOINT))
1283 fprintf(stderr," int x=%d y=%d\n", ge->ix3, ge->iy3);
1284 break;
1285 case GE_CURVE:
1286 if(ISDBG(TOINT))
1287 fprintf(stderr," %c float ", ge->type);
1288
1289 for(i=0; i<3; i++) {
1290 if(ISDBG(TOINT))
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]);
1294 }
1295
1296 if(ISDBG(TOINT))
1297 fprintf(stderr,"\n int ");
1298
1299 for(i=0; i<3; i++) {
1300 ge->ixn[i] = x[i];
1301 ge->iyn[i] = y[i];
1302 if(ISDBG(TOINT))
1303 fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1304 }
1305 ge->flags &= ~GEF_FLOAT; /* for fixcvdir */
1306 fixcvdir(ge, ge->dir);
1307
1308 if(ISDBG(TOINT)) {
1309 fprintf(stderr,"\n fixed ");
1310 for(i=0; i<3; i++)
1311 fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
1312 fprintf(stderr,"\n");
1313 }
1314
1315 break;
1316 }
1317 ge->flags &= ~GEF_FLOAT;
1318 }
1319 g->flags &= ~GF_FLOAT;
1320 }
1321
1322
1323 /* check whether we can fix up the curve to change its size by (dx,dy) */
1324 /* 0 means NO, 1 means YES */
1325
1326 /* for float: if scaling would be under 10% */
1327
1328 int
1329 fcheckcv(
1330 GENTRY * ge,
1331 double dx,
1332 double dy
1333 )
1334 {
1335 if( !(ge->flags & GEF_FLOAT) ) {
1336 fprintf(stderr, "**! fcheckcv(0x%x) on int entry, ABORT\n", ge);
1337 abort(); /* dump core */
1338 }
1339
1340 if (ge->type != GE_CURVE)
1341 return 0;
1342
1343 if( fabs(ge->fx3 - ge->prev->fx3) < fabs(dx) * 10 )
1344 return 0;
1345
1346 if( fabs(ge->fy3 - ge->prev->fy3) < fabs(dy) * 10 )
1347 return 0;
1348
1349 return 1;
1350 }
1351
1352 /* for int: if won't create new zigzags at the ends */
1353
1354 int
1355 icheckcv(
1356 GENTRY * ge,
1357 int dx,
1358 int dy
1359 )
1360 {
1361 int xdep, ydep;
1362
1363 if(ge->flags & GEF_FLOAT) {
1364 fprintf(stderr, "**! icheckcv(0x%x) on floating entry, ABORT\n", ge);
1365 abort(); /* dump core */
1366 }
1367
1368 if (ge->type != GE_CURVE)
1369 return 0;
1370
1371 xdep = ge->ix3 - ge->prev->ix3;
1372 ydep = ge->iy3 - ge->prev->iy3;
1373
1374 if (ge->type == GE_CURVE
1375 && (xdep * (xdep + dx)) > 0
1376 && (ydep * (ydep + dy)) > 0) {
1377 return 1;
1378 } else
1379 return 0;
1380 }
1381
1382 /* float connect the ends of open contours */
1383
1384 void
1385 fclosepaths(
1386 GLYPH * g
1387 )
1388 {
1389 GENTRY *ge, *fge, *xge, *nge;
1390 int i;
1391
1392 assertisfloat(g, "fclosepaths float\n");
1393
1394 for (xge = g->entries; xge != 0; xge = xge->next) {
1395 if( xge->type != GE_PATH )
1396 continue;
1397
1398 ge = xge->prev;
1399 if(ge == 0 || ge->type != GE_LINE && ge->type!= GE_CURVE) {
1400 fprintf(stderr, "**! Glyph %s got empty path\n",
1401 g->name);
1402 exit(1);
1403 }
1404
1405 fge = ge->frwd;
1406 if (fge->prev == 0 || fge->prev->type != GE_MOVE) {
1407 fprintf(stderr, "**! Glyph %s got strange beginning of path\n",
1408 g->name);
1409 exit(1);
1410 }
1411 fge = fge->prev;
1412 if (fge->fx3 != ge->fx3 || fge->fy3 != ge->fy3) {
1413 /* we have to fix this open path */
1414
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);
1417
1418
1419 /* add a new line */
1420 nge = newgentry(GEF_FLOAT);
1421 (*nge) = (*ge);
1422 nge->fx3 = fge->fx3;
1423 nge->fy3 = fge->fy3;
1424 nge->type = GE_LINE;
1425
1426 addgeafter(ge, nge);
1427
1428 if (fabs(ge->fx3 - fge->fx3) <= 2 && fabs(ge->fy3 - fge->fy3) <= 2) {
1429 /*
1430 * small change, try to get rid of the new entry
1431 */
1432
1433 double df[2];
1434
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);
1438 }
1439
1440 if(df[0] == 0. && df[1] == 0.) {
1441 /* closed gap successfully, remove the added entry */
1442 freethisge(nge);
1443 }
1444 }
1445 }
1446 }
1447 }
1448
1449 void
1450 smoothjoints(
1451 GLYPH * g
1452 )
1453 {
1454 GENTRY *ge, *ne;
1455 int dx1, dy1, dx2, dy2, k;
1456 int dir;
1457
1458 return; /* this stuff seems to create problems */
1459
1460 assertisint(g, "smoothjoints int");
1461
1462 if (g->entries == 0) /* nothing to do */
1463 return;
1464
1465 for (ge = g->entries->next; ge != 0; ge = ge->next) {
1466 ne = ge->frwd;
1467
1468 /*
1469 * although there should be no one-line path * and any path
1470 * must end with CLOSEPATH, * nobody can say for sure
1471 */
1472
1473 if (ge == ne || ne == 0)
1474 continue;
1475
1476 /* now handle various joints */
1477
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;
1483
1484 /* check whether they have the same direction */
1485 /* and the same slope */
1486 /* then we can join them into one line */
1487
1488 if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 && dx1 * dy2 == dy1 * dx2) {
1489 /* extend the previous line */
1490 ge->ix3 = ne->ix3;
1491 ge->iy3 = ne->iy3;
1492
1493 /* and get rid of the next line */
1494 freethisge(ne);
1495 }
1496 } else if (ge->type == GE_LINE && ne->type == GE_CURVE) {
1497 fixcvends(ne);
1498
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;
1503
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)
1507 && abs(dy1) <= 4) {
1508 dir = igetcvdir(ne);
1509 ge->iy3 -= dy1;
1510 ne->iy1 -= dy1;
1511 fixcvdir(ne, dir);
1512 if (ge->next != ne)
1513 ne->prev->iy3 -= dy1;
1514 dy1 = 0;
1515 } else if (dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
1516 && icheckcv(ne, -dx1, 0)
1517 && abs(dx1) <= 4) {
1518 /* the same but vertical */
1519 dir = igetcvdir(ne);
1520 ge->ix3 -= dx1;
1521 ne->ix1 -= dx1;
1522 fixcvdir(ne, dir);
1523 if (ge->next != ne)
1524 ne->prev->ix3 -= dx1;
1525 dx1 = 0;
1526 }
1527 /*
1528 * if line is horizontal and curve begins nearly
1529 * horizontally
1530 */
1531 if (dy1 == 0 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0) {
1532 dir = igetcvdir(ne);
1533 ne->iy1 -= dy2;
1534 fixcvdir(ne, dir);
1535 dy2 = 0;
1536 } else if (dx1 == 0 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0) {
1537 /* the same but vertical */
1538 dir = igetcvdir(ne);
1539 ne->ix1 -= dx2;
1540 fixcvdir(ne, dir);
1541 dx2 = 0;
1542 }
1543 } else if (ge->type == GE_CURVE && ne->type == GE_LINE) {
1544 fixcvends(ge);
1545
1546 dx1 = ge->ix3 - ge->ix2;
1547 dy1 = ge->iy3 - ge->iy2;
1548 dx2 = ne->ix3 - ge->ix3;
1549 dy2 = ne->iy3 - ge->iy3;
1550
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)
1554 && abs(dy2) <= 4) {
1555 dir = igetcvdir(ge);
1556 ge->iy3 += dy2;
1557 ge->iy2 += dy2;
1558 fixcvdir(ge, dir);
1559 if (ge->next != ne)
1560 ne->prev->iy3 += dy2;
1561 dy2 = 0;
1562 } else if (dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
1563 && icheckcv(ge, dx2, 0)
1564 && abs(dx2) <= 4) {
1565 /* the same but vertical */
1566 dir = igetcvdir(ge);
1567 ge->ix3 += dx2;
1568 ge->ix2 += dx2;
1569 fixcvdir(ge, dir);
1570 if (ge->next != ne)
1571 ne->prev->ix3 += dx2;
1572 dx2 = 0;
1573 }
1574 /*
1575 * if line is horizontal and curve ends nearly
1576 * horizontally
1577 */
1578 if (dy2 == 0 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0) {
1579 dir = igetcvdir(ge);
1580 ge->iy2 += dy1;
1581 fixcvdir(ge, dir);
1582 dy1 = 0;
1583 } else if (dx2 == 0 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0) {
1584 /* the same but vertical */
1585 dir = igetcvdir(ge);
1586 ge->ix2 += dx1;
1587 fixcvdir(ge, dir);
1588 dx1 = 0;
1589 }
1590 } else if (ge->type == GE_CURVE && ne->type == GE_CURVE) {
1591 fixcvends(ge);
1592 fixcvends(ne);
1593
1594 dx1 = ge->ix3 - ge->ix2;
1595 dy1 = ge->iy3 - ge->iy2;
1596 dx2 = ne->ix1 - ge->ix3;
1597 dy2 = ne->iy1 - ge->iy3;
1598
1599 /*
1600 * check if we have a rather smooth joint at extremal
1601 * point
1602 */
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
1610 ) {
1611 dir = igetcvdir(ge);
1612 ge->ix2 += dx1;
1613 dx1 = 0;
1614 fixcvdir(ge, dir);
1615 dir = igetcvdir(ne);
1616 ne->ix1 -= dx2;
1617 dx2 = 0;
1618 fixcvdir(ne, dir);
1619 }
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
1627 ) {
1628 dir = igetcvdir(ge);
1629 ge->iy2 += dy1;
1630 dy1 = 0;
1631 fixcvdir(ge, dir);
1632 dir = igetcvdir(ne);
1633 ne->iy1 -= dy2;
1634 dy2 = 0;
1635 fixcvdir(ne, dir);
1636 }
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))) {
1640 int tries[6][4];
1641 int results[6];
1642 int i, b;
1643
1644 /* build array of changes we are going to try */
1645 /* uninitalized entries are 0 */
1646 if (k > 0) {
1647 static int t1[6][4] = {
1648 {0, 0, 0, 0},
1649 {-1, 0, 1, 0},
1650 {-1, 0, 0, 1},
1651 {0, -1, 1, 0},
1652 {0, -1, 0, 1},
1653 {-1, -1, 1, 1}};
1654 memcpy(tries, t1, sizeof tries);
1655 } else {
1656 static int t1[6][4] = {
1657 {0, 0, 0, 0},
1658 {1, 0, -1, 0},
1659 {1, 0, 0, -1},
1660 {0, 1, -1, 0},
1661 {0, 1, 0, -1},
1662 {1, 1, -1, -1}};
1663 memcpy(tries, t1, sizeof tries);
1664 }
1665
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]));
1671 }
1672
1673 /* and find the best try */
1674 k = abs(k);
1675 b = 0;
1676 for (i = 1; i < 6; i++)
1677 if (results[i] < k) {
1678 k = results[i];
1679 b = i;
1680 }
1681 /* and finally apply it */
1682 if (dx1 < 0)
1683 tries[b][0] = -tries[b][0];
1684 if (dy2 < 0)
1685 tries[b][1] = -tries[b][1];
1686 if (dy1 < 0)
1687 tries[b][2] = -tries[b][2];
1688 if (dx2 < 0)
1689 tries[b][3] = -tries[b][3];
1690
1691 dir = igetcvdir(ge);
1692 ge->ix2 -= tries[b][0];
1693 ge->iy2 -= tries[b][2];
1694 fixcvdir(ge, dir);
1695 dir = igetcvdir(ne);
1696 ne->ix1 += tries[b][3];
1697 ne->iy1 += tries[b][1];
1698 fixcvdir(ne, dir);
1699 }
1700 }
1701 }
1702 }
1703
1704 /* debugging: print out stems of a glyph */
1705 static void
1706 debugstems(
1707 char *name,
1708 STEM * hstems,
1709 int nhs,
1710 STEM * vstems,
1711 int nvs
1712 )
1713 {
1714 int i;
1715
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' : '-'));
1733 }
1734
1735 /* add pseudo-stems for the limits of the Blue zones to the stem array */
1736 static int
1737 addbluestems(
1738 STEM *s,
1739 int n
1740 )
1741 {
1742 int i;
1743
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;
1749 n++;
1750 s[n].value=bluevalues[i+1];
1751 s[n].flags=ST_ZONE;
1752 /* don't overlap with anything */
1753 s[n].origin=s[n].from=s[n].to= -10000+i+1;
1754 n++;
1755 }
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;
1761 n++;
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;
1766 n++;
1767 }
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;
1773 n++;
1774 s[n].value=otherblues[i+1];
1775 s[n].flags=ST_ZONE;
1776 /* don't overlap with anything */
1777 s[n].origin=s[n].from=s[n].to= -10000+i+1+nblues;
1778 n++;
1779 }
1780 return n;
1781 }
1782
1783 /* sort stems in array */
1784 static void
1785 sortstems(
1786 STEM * s,
1787 int n
1788 )
1789 {
1790 int i, j;
1791 STEM x;
1792
1793
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
1801 */
1802
1803 for (i = 0; i < n; i++)
1804 for (j = i + 1; j < n; j++) {
1805 if(s[i].value < s[j].value)
1806 continue;
1807 if(s[i].value == s[j].value) {
1808 if( (s[i].flags & ST_UP) < (s[j].flags & ST_UP) )
1809 continue;
1810 if( (s[i].flags & ST_UP) == (s[j].flags & ST_UP) ) {
1811 if( s[i].flags & ST_UP ) {
1812 if(
1813 (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1814 >
1815 (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1816 )
1817 continue;
1818 } else {
1819 if(
1820 (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1821 <
1822 (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
1823 )
1824 continue;
1825 }
1826 }
1827 }
1828 x = s[j];
1829 s[j] = s[i];
1830 s[i] = x;
1831 }
1832 }
1833
1834 /* check whether two stem borders overlap */
1835
1836 static int
1837 stemoverlap(
1838 STEM * s1,
1839 STEM * s2
1840 )
1841 {
1842 int result;
1843
1844 if (s1->from <= s2->from && s1->to >= s2->from
1845 || s2->from <= s1->from && s2->to >= s1->from)
1846 result = 1;
1847 else
1848 result = 0;
1849
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);
1853 return result;
1854 }
1855
1856 /*
1857 * check if the stem [border] is in an appropriate blue zone
1858 * (currently not used)
1859 */
1860
1861 static int
1862 steminblue(
1863 STEM *s
1864 )
1865 {
1866 int i, val;
1867
1868 val=s->value;
1869 if(s->flags & ST_UP) {
1870 /* painted size up, look at lower zones */
1871 if(nblues>=2 && val>=bluevalues[0] && val<=bluevalues[1] )
1872 return 1;
1873 for(i=0; i<notherb; i++) {
1874 if( val>=otherblues[i] && val<=otherblues[i+1] )
1875 return 1;
1876 }
1877 } else {
1878 /* painted side down, look at upper zones */
1879 for(i=2; i<nblues; i++) {
1880 if( val>=bluevalues[i] && val<=bluevalues[i+1] )
1881 return 1;
1882 }
1883 }
1884
1885 return 0;
1886 }
1887
1888 /* mark the outermost stem [borders] in the blue zones */
1889
1890 static void
1891 markbluestems(
1892 STEM *s,
1893 int nold
1894 )
1895 {
1896 int i, j, a, b, c;
1897 /*
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
1901 */
1902
1903 /* top zones */
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) )
1910 continue;
1911 c=s[j].value;
1912 if(c<a) /* too low */
1913 break;
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 )
1920 j++;
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;
1925 break;
1926 }
1927 }
1928 }
1929 /* baseline */
1930 if(nblues>=2) {
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 )
1934 continue;
1935 c=s[j].value;
1936 if(c>b) /* too high */
1937 break;
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 )
1944 j--;
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;
1949 break;
1950 }
1951 }
1952 }
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 )
1958 continue;
1959 c=s[j].value;
1960 if(c>b) /* too high */
1961 break;
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 )
1968 j--;
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;
1973 break;
1974 }
1975 }
1976 }
1977 }
1978
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
1982 */
1983 static int
1984 joinmainstems(
1985 STEM * s,
1986 int nold,
1987 int useblues /* do we use the blue values ? */
1988 )
1989 {
1990 #define MAX_STACK 1000
1991 STEM stack[MAX_STACK];
1992 int nstack = 0;
1993 int sbottom = 0;
1994 int nnew;
1995 int i, j, k;
1996 int a, b, c, w1, w2, w3;
1997 int fw, fd;
1998 /*
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
2003 * with priority 1
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
2007 */
2008 int readystem = 0;
2009 int pri;
2010 int nlps = 0; /* number of non-committed
2011 * lowest-priority stems */
2012
2013
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 */
2018 if (readystem)
2019 nnew += 2;
2020 readystem=0;
2021
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++)
2025 {}
2026 b=i; /* our range is a <= i < b */
2027 c= -1; /* index of our best guess up to now */
2028 pri=0;
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)
2033 break;
2034 else
2035 continue;
2036 }
2037 for(j=a; j<b; j++) {
2038 if(!stemoverlap(&s[j], &s[i]) )
2039 continue;
2040 /* consider priorities */
2041 if( ( (s[j].flags|s[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
2042 c=i;
2043 goto bluematch;
2044 }
2045 if( ((s[j].flags|s[i].flags) & ST_END)==0 ) {
2046 if(pri < 2) {
2047 c=i; pri=2;
2048 }
2049 } else {
2050 if(pri == 0) {
2051 c=i; pri=1;
2052 }
2053 }
2054 }
2055 }
2056 bluematch:
2057 /* clean up the stack */
2058 nstack=sbottom=0;
2059 readystem=0;
2060 /* add this stem */
2061 s[nnew++]=s[a];
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 */
2065 s[j]=s[j-1];
2066 b++;
2067 nold++;
2068 }
2069 s[nnew]=s[a];
2070 s[nnew].flags &= ~(ST_UP|ST_BLUE);
2071 nnew++;
2072 i=b-1;
2073 } else {
2074 s[nnew++]=s[c];
2075 i=c; /* skip up to this point */
2076 }
2077 if (ISDBG(MAINSTEMS))
2078 fprintf(pfa_file, "%% +stem %d...%d U BLUE\n",
2079 s[nnew-2].value, s[nnew-1].value);
2080 } else {
2081 if (nstack >= MAX_STACK) {
2082 WARNING_1 fprintf(stderr, "Warning: **** converter's stem stack overflow ****\n");
2083 nstack = 0;
2084 }
2085 stack[nstack++] = s[i];
2086 }
2087 } else if(s[i].flags & ST_BLUE) {
2088 /* again, we just HAVE to use this value */
2089 if (readystem)
2090 nnew += 2;
2091 readystem=0;
2092
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++)
2096 {}
2097 b=i; /* our range is a <= i < b */
2098 c= -1; /* index of our best guess up to now */
2099 pri=0;
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 )
2104 break;
2105 else
2106 continue;
2107 }
2108 for(j=a; j<b; j++) {
2109 if(!stemoverlap(&s[j], &stack[i]) )
2110 continue;
2111 /* consider priorities */
2112 if( ( (s[j].flags|stack[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
2113 c=i;
2114 goto bluedownmatch;
2115 }
2116 if( ((s[j].flags|stack[i].flags) & ST_END)==0 ) {
2117 if(pri < 2) {
2118 c=i; pri=2;
2119 }
2120 } else {
2121 if(pri == 0) {
2122 c=i; pri=1;
2123 }
2124 }
2125 }
2126 }
2127 bluedownmatch:
2128 /* if found no match make a one-dot-wide stem */
2129 if(c<0) {
2130 c=0;
2131 stack[0]=s[b-1];
2132 stack[0].flags |= ST_UP;
2133 stack[0].flags &= ~ST_BLUE;
2134 }
2135 /* remove all the stems conflicting with this one */
2136 readystem=0;
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 */
2142 break;
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;
2146 break;
2147 }
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 */
2153 }
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;
2158 break;
2159 } else {
2160 if (ISDBG(MAINSTEMS))
2161 fprintf(pfa_file, "%% -stem %d...%d p>=2\n",
2162 s[j].value, s[j+1].value);
2163 continue;
2164 }
2165 }
2166 nnew=j+2;
2167 /* add this stem */
2168 if(nnew>=b-1) { /* have no free space */
2169 for(j=nold; j>=b-1; j--) /* make free space */
2170 s[j]=s[j-1];
2171 b++;
2172 nold++;
2173 }
2174 s[nnew++]=stack[c];
2175 s[nnew++]=s[b-1];
2176 /* clean up the stack */
2177 nstack=sbottom=0;
2178 readystem=0;
2179 /* set the next position to search */
2180 i=b-1;
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) {
2185
2186 /*
2187 * check whether our stem overlaps with anything in
2188 * stack
2189 */
2190 for (j = nstack - 1; j >= sbottom; j--) {
2191 if (s[i].value <= stack[j].value)
2192 break;
2193 if (stack[j].flags & ST_ZONE)
2194 continue;
2195
2196 if ((s[i].flags & ST_END)
2197 || (stack[j].flags & ST_END))
2198 pri = 1;
2199 else if ((s[i].flags & ST_FLAT)
2200 || (stack[j].flags & ST_FLAT))
2201 pri = 3;
2202 else
2203 pri = 2;
2204
2205 if (pri < readystem && s[nnew + 1].value >= stack[j].value
2206 || !stemoverlap(&stack[j], &s[i]))
2207 continue;
2208
2209 if (readystem > 1 && s[nnew + 1].value < stack[j].value) {
2210 nnew += 2;
2211 readystem = 0;
2212 nlps = 0;
2213 }
2214 /*
2215 * width of the previous stem (if it's
2216 * present)
2217 */
2218 w1 = s[nnew + 1].value - s[nnew].value;
2219
2220 /* width of this stem */
2221 w2 = s[i].value - stack[j].value;
2222
2223 if (readystem == 0) {
2224 /* nothing yet, just add a new stem */
2225 s[nnew] = stack[j];
2226 s[nnew + 1] = s[i];
2227 readystem = pri;
2228 if (pri == 1)
2229 nlps = 1;
2230 else if (pri == 2)
2231 sbottom = j;
2232 else {
2233 sbottom = j + 1;
2234 while (sbottom < nstack
2235 && stack[sbottom].value <= stack[j].value)
2236 sbottom++;
2237 }
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) {
2243 /*
2244 * doesn't overlap with the
2245 * previous one
2246 */
2247 nnew += 2;
2248 nlps++;
2249 s[nnew] = stack[j];
2250 s[nnew + 1] = s[i];
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) {
2255 /* is narrower */
2256 s[nnew] = stack[j];
2257 s[nnew + 1] = s[i];
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);
2261 }
2262 } else if (pri == 2) {
2263 if (readystem == 2) {
2264 /* choose the narrower stem */
2265 if (w1 > w2) {
2266 s[nnew] = stack[j];
2267 s[nnew + 1] = s[i];
2268 sbottom = j;
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);
2272 }
2273 /* else readystem==1 */
2274 } else if (stack[j].value > s[nnew + 1].value) {
2275 /*
2276 * value doesn't overlap with
2277 * the previous one
2278 */
2279 nnew += 2;
2280 nlps = 0;
2281 s[nnew] = stack[j];
2282 s[nnew + 1] = s[i];
2283 sbottom = j;
2284 readystem = pri;
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) {
2290 /*
2291 * we can replace the top
2292 * stem
2293 */
2294 nlps = 0;
2295 s[nnew] = stack[j];
2296 s[nnew + 1] = s[i];
2297 readystem = pri;
2298 sbottom = j;
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);
2302 }
2303 } else if (readystem == 3) { /* that means also
2304 * pri==3 */
2305 /* choose the narrower stem */
2306 if (w1 > w2) {
2307 s[nnew] = stack[j];
2308 s[nnew + 1] = s[i];
2309 sbottom = j + 1;
2310 while (sbottom < nstack
2311 && stack[sbottom].value <= stack[j].value)
2312 sbottom++;
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);
2316 }
2317 } else if (pri == 3) {
2318 /*
2319 * we can replace as many stems as
2320 * neccessary
2321 */
2322 nnew += 2;
2323 while (nnew > 0 && s[nnew - 1].value >= stack[j].value) {
2324 nnew -= 2;
2325 if (ISDBG(MAINSTEMS))
2326 fprintf(pfa_file, "%% -stem %d..%d\n",
2327 s[nnew].value, s[nnew + 1].value);
2328 }
2329 nlps = 0;
2330 s[nnew] = stack[j];
2331 s[nnew + 1] = s[i];
2332 readystem = pri;
2333 sbottom = j + 1;
2334 while (sbottom < nstack
2335 && stack[sbottom].value <= stack[j].value)
2336 sbottom++;
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);
2340 }
2341 }
2342 }
2343 }
2344 if (readystem)
2345 nnew += 2;
2346
2347 /* change the 1-pixel-wide stems to 20-pixel-wide stems if possible
2348 * the constant 20 is recommended in the Type1 manual
2349 */
2350 if(useblues) {
2351 for(i=0; i<nnew; i+=2) {
2352 if(s[i].value != s[i+1].value)
2353 continue;
2354 if( ((s[i].flags ^ s[i+1].flags) & ST_BLUE)==0 )
2355 continue;
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 */
2359 else
2360 s[i+1].value+=20;
2361 } else {
2362 if(i>0 && s[i-1].value>s[i].value-22)
2363 s[i].value=s[i-1].value+2; /* compensate for fuzziness */
2364 else
2365 s[i].value-=20;
2366 }
2367 }
2368 }
2369 /* make sure that no stem it stretched between
2370 * a top zone and a bottom zone
2371 */
2372 if(useblues) {
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 */
2376
2377 for(j=2; j<nblues; j++) {
2378 c=bluevalues[j];
2379 if( c>=s[i].value && c<=s[i+1].value && c<a )
2380 a=c;
2381 }
2382 if(nblues>=2) {
2383 c=bluevalues[1];
2384 if( c>=s[i].value && c<=s[i+1].value && c>b )
2385 b=c;
2386 }
2387 for(j=1; j<notherb; j++) {
2388 c=otherblues[j];
2389 if( c>=s[i].value && c<=s[i+1].value && c>b )
2390 b=c;
2391 }
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 */
2395 s[j]=s[j-2];
2396 nnew+=2;
2397
2398 if(s[i].value+22 >= a)
2399 s[i+1].value=a-2; /* leave space for fuzziness */
2400 else
2401 s[i+1].value=s[i].value+20;
2402
2403 if(s[i+3].value-22 <= b)
2404 s[i+2].value=b+2; /* leave space for fuzziness */
2405 else
2406 s[i+2].value=s[i+3].value-20;
2407
2408 i+=2;
2409 }
2410 }
2411 }
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;
2418
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;
2422
2423 fw = w3 - w1; /* fuzz in width */
2424 fd = ((c - b) - (b - a)); /* fuzz in distance
2425 * (doubled) */
2426
2427 /* we are able to handle some fuzz */
2428 /*
2429 * it doesn't hurt if the declared stem is a bit
2430 * narrower than actual unless it's an edge in
2431 * a blue zone
2432 */
2433 if (abs(abs(fd) - abs(fw)) * 5 < w2
2434 && abs(fw) * 20 < (w1 + w3)) { /* width dirrerence <10% */
2435
2436 if(useblues) { /* check that we don't disturb any blue stems */
2437 j=c; k=a;
2438 if (fw > 0) {
2439 if (fd > 0) {
2440 if( s[i+5].flags & ST_BLUE )
2441 continue;
2442 j -= fw;
2443 } else {
2444 if( s[i+4].flags & ST_BLUE )
2445 continue;
2446 j += fw;
2447 }
2448 } else if(fw < 0) {
2449 if (fd > 0) {
2450 if( s[i+1].flags & ST_BLUE )
2451 continue;
2452 k -= fw;
2453 } else {
2454 if( s[i].flags & ST_BLUE )
2455 continue;
2456 k += fw;
2457 }
2458 }
2459 pri = ((j - b) - (b - k));
2460
2461 if (pri > 0) {
2462 if( s[i+2].flags & ST_BLUE )
2463 continue;
2464 } else if(pri < 0) {
2465 if( s[i+3].flags & ST_BLUE )
2466 continue;
2467 }
2468 }
2469
2470 /*
2471 * first fix up the width of 1st and 3rd
2472 * stems
2473 */
2474 if (fw > 0) {
2475 if (fd > 0) {
2476 s[i + 5].value -= fw;
2477 c -= fw;
2478 } else {
2479 s[i + 4].value += fw;
2480 c += fw;
2481 }
2482 } else {
2483 if (fd > 0) {
2484 s[i + 1].value -= fw;
2485 a -= fw;
2486 } else {
2487 s[i].value += fw;
2488 a += fw;
2489 }
2490 }
2491 fd = ((c - b) - (b - a));
2492
2493 if (fd > 0) {
2494 s[i + 2].value += abs(fd) / 2;
2495 } else {
2496 s[i + 3].value -= abs(fd) / 2;
2497 }
2498
2499 s[i].flags |= ST_3;
2500 i += 4;
2501 }
2502 }
2503 }
2504
2505 return (nnew & ~1); /* number of lines must be always even */
2506 }
2507
2508 /*
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)
2512 */
2513
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;
2518
2519 #define setbasestem(from, to) \
2520 (xbstem[0]=from, xbstem[1]=to, xblast=1)
2521 #define isbaseempty() (xblast<=0)
2522
2523 /* returns 1 if was overlapping, 0 otherwise */
2524 static int
2525 subfrombase(
2526 int from,
2527 int to
2528 )
2529 {
2530 int a, b;
2531 int i, j;
2532
2533 if(isbaseempty())
2534 return 0;
2535
2536 /* handle the simple case simply */
2537 if(from > xbstem[xblast] || to < xbstem[0])
2538 return 0;
2539
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] */
2544
2545 /* now the interesting examples are:
2546 * (it was hard for me to understand, so I looked at the examples)
2547 * 1
2548 * a|-----| |-----|b |-----| |-----|
2549 * f|-----|t
2550 * 2
2551 * a|-----|b |-----| |-----| |-----|
2552 * f|--|t
2553 * 3
2554 * a|-----|b |-----| |-----| |-----|
2555 * f|-----|t
2556 * 4
2557 * |-----|b a|-----| |-----| |-----|
2558 * f|------------|t
2559 * 5
2560 * |-----| |-----|b |-----| a|-----|
2561 * f|-----------------------------|t
2562 * 6
2563 * |-----|b |-----| |-----| a|-----|
2564 * f|--------------------------------------------------|t
2565 * 7
2566 * |-----|b |-----| a|-----| |-----|
2567 * f|--------------------------|t
2568 */
2569
2570 if(a < b-1) /* hits a gap - example 1 */
2571 return 0;
2572
2573 /* now the subtraction itself */
2574
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);
2578 while(j>=b)
2579 xbstem[i--]=xbstem[j--];
2580 xbstem[b]=from-1;
2581 xbstem[b+1]=to+1;
2582 return 1;
2583 /* becomes
2584 * 2a
2585 * a|b || |-----| |-----| |-----|
2586 * f|--|t
2587 */
2588 }
2589
2590 if(xbstem[b-1] < from) {
2591 /* cuts the back of this subrange - examples 3, 4, 7 */
2592 xbstem[b] = from-1;
2593 b+=2;
2594 /* becomes
2595 * 3a
2596 * a|----| |-----|b |-----| |-----|
2597 * f|-----|t
2598 * 4a
2599 * |---| a|-----|b |-----| |-----|
2600 * f|------------|t
2601 * 7a
2602 * |---| |-----|b a|-----| |-----|
2603 * f|--------------------------|t
2604 */
2605 }
2606
2607 if(xbstem[a+1] > to) {
2608 /* cuts the front of this subrange - examples 4a, 5, 7a */
2609 xbstem[a] = to+1;
2610 a-=2;
2611 /* becomes
2612 * 4b
2613 * a|---| |---|b |-----| |-----|
2614 * f|------------|t
2615 * 5b
2616 * |-----| |-----|b a|-----| ||
2617 * f|-----------------------------|t
2618 * 7b
2619 * |---| a|-----|b || |-----|
2620 * f|--------------------------|t
2621 */
2622 }
2623
2624 if(a < b-1) /* now after modification it hits a gap - examples 3a, 4b */
2625 return 1; /* because we have removed something */
2626
2627 /* now remove the subranges completely covered by the new stem */
2628 /* examples 5b, 6, 7b */
2629 i=b-1; j=a+2;
2630 /* positioned as:
2631 * 5b i j
2632 * |-----| |-----|b a|-----| ||
2633 * f|-----------------------------|t
2634 * 6 i xblast j
2635 * |-----|b |-----| |-----| a|-----|
2636 * f|--------------------------------------------------|t
2637 * 7b i j
2638 * |---| a|-----|b || |-----|
2639 * f|--------------------------|t
2640 */
2641 while(j <= xblast)
2642 xbstem[i++]=xbstem[j++];
2643 xblast=i-1;
2644 return 1;
2645 }
2646
2647 /* for debugging */
2648 static void
2649 printbasestem(void)
2650 {
2651 int i;
2652
2653 printf("( ");
2654 for(i=0; i<xblast; i+=2)
2655 printf("%d-%d ", xbstem[i], xbstem[i+1]);
2656 printf(") %d\n", xblast);
2657 }
2658
2659 /*
2660 * Join the stem borders to build the sets of substituted stems
2661 * XXX add consideration of the italic angle
2662 */
2663 static void
2664 joinsubstems(
2665 STEM * s,
2666 short *pairs,
2667 int nold,
2668 int useblues /* do we use the blue values ? */
2669 )
2670 {
2671 int i, j, x;
2672 static unsigned char mx[MAX_STEMS][MAX_STEMS];
2673
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
2677 */
2678
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
2682 * per glyph
2683 */
2684
2685 /* clean the used part of matrix */
2686 for(i=0; i<nold; i++)
2687 for(j=0; j<nold; j++)
2688 mx[i][j]=0;
2689
2690 /* build the matrix of stem pairs */
2691 for(i=0; i<nold; i++) {
2692 if( s[i].flags & ST_ZONE )
2693 continue;
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 ) {
2701 continue;
2702 }
2703 x=subfrombase(s[j].from, s[j].to);
2704
2705 if(s[j].flags & ST_UP) /* match only up+down pairs */
2706 continue;
2707
2708 mx[i][j]=mx[j][i]=x;
2709
2710 if(isbaseempty()) /* nothing else to do */
2711 break;
2712 }
2713 }
2714 }
2715
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);
2729 }
2730 }
2731
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;
2735
2736 x= -1; /* best pair: none */
2737 lastpri=0;
2738
2739 v=s[i].value;
2740 f=s[i].flags;
2741
2742 if(f & ST_ZONE) {
2743 pairs[i]= -1;
2744 continue;
2745 }
2746
2747 if(f & ST_UP) {
2748 for(j=i+1; j<nold; j++) {
2749 if(mx[i][j]==0)
2750 continue;
2751
2752 if( (f | s[j].flags) & ST_END )
2753 pri=1;
2754 else if( (f | s[j].flags) & ST_FLAT )
2755 pri=3;
2756 else
2757 pri=2;
2758
2759 if(lastpri==0
2760 || pri > lastpri
2761 && ( lastpri==1 || s[j].value-v<20 || (s[x].value-v)*2 >= s[j].value-v ) ) {
2762 lastpri=pri;
2763 x=j;
2764 }
2765 }
2766 } else {
2767 for(j=i-1; j>=0; j--) {
2768 if(mx[i][j]==0)
2769 continue;
2770
2771 if( (f | s[j].flags) & ST_END )
2772 pri=1;
2773 else if( (f | s[j].flags) & ST_FLAT )
2774 pri=3;
2775 else
2776 pri=2;
2777
2778 if(lastpri==0
2779 || pri > lastpri
2780 && ( lastpri==1 || v-s[j].value<20 || (v-s[x].value)*2 >= v-s[j].value ) ) {
2781 lastpri=pri;
2782 x=j;
2783 }
2784 }
2785 }
2786 if(x== -1 && mx[i][i])
2787 pairs[i]=i; /* a special case */
2788 else
2789 pairs[i]=x;
2790 }
2791
2792 if(ISDBG(SUBSTEMS)) {
2793 for(i=0; i<nold; i++) {
2794 j=pairs[i];
2795 if(j>0)
2796 fprintf(pfa_file, "%% %d...%d (%d x %d)\n", s[i].value, s[j].value, i, j);
2797 }
2798 }
2799 }
2800
2801 /*
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().
2806 */
2807 static void
2808 uniformstems(
2809 STEM * s,
2810 short *pairs,
2811 int ns
2812 )
2813 {
2814 int i, j, from, to, val, dir;
2815 int pri, prevpri[2], wd, prevwd[2], prevbest[2];
2816
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;
2822
2823 for(to = from; to<ns && s[to].value == val; to++) {
2824 dir = ((s[to].flags & ST_UP)!=0);
2825
2826 i=pairs[to]; /* the other side of this stem */
2827 if(i<0 || i==to)
2828 continue; /* oops, no other side */
2829 wd=abs(s[i].value-val);
2830 if(wd == 0)
2831 continue;
2832 pri=1;
2833 if( (s[to].flags | s[i].flags) & ST_END )
2834 pri=0;
2835 if( prevbest[dir] == -1 || pri > prevpri[dir] || wd<prevwd[dir] ) {
2836 prevbest[dir]=i;
2837 prevpri[dir]=pri;
2838 prevwd[dir]=wd;
2839 }
2840 }
2841
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);
2849 }
2850 pairs[i] = prevbest[dir];
2851 }
2852 }
2853 }
2854 }
2855
2856 /*
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.
2862 */
2863 static int
2864 findstemat(
2865 int value,
2866 int origin,
2867 GENTRY *ge,
2868 STEM *sp,
2869 short *pairs,
2870 int ns,
2871 int prevbest /* -1 means "none" */
2872 )
2873 {
2874 int i, min, max;
2875 int v, si;
2876 int pri, prevpri; /* priority, 0 = has ST_END, 1 = no ST_END */
2877 int wd, prevwd; /* stem width */
2878
2879 si= -1; /* nothing yet */
2880
2881 /* stems are ordered by value, binary search */
2882 min=0; max=ns; /* min <= i < max */
2883 while( min < max ) {
2884 i=(min+max)/2;
2885 v=sp[i].value;
2886 if(v<value)
2887 min=i+1;
2888 else if(v>value)
2889 max=i;
2890 else {
2891 si=i; /* temporary value */
2892 break;
2893 }
2894 }
2895
2896 if( si < 0 ) /* found nothing this time */
2897 return prevbest;
2898
2899 /* find the priority of the prevbest */
2900 /* we expect that prevbest has a pair */
2901 if(prevbest>=0) {
2902 i=pairs[prevbest];
2903 prevpri=1;
2904 if( (sp[prevbest].flags | sp[i].flags) & ST_END )
2905 prevpri=0;
2906 prevwd=abs(sp[i].value-value);
2907 }
2908
2909 /* stems are not ordered by origin, so now do the linear search */
2910
2911 while( si>0 && sp[si-1].value==value ) /* find the first one */
2912 si--;
2913
2914 for(; si<ns && sp[si].value==value; si++) {
2915 if(sp[si].origin != origin)
2916 continue;
2917 if(sp[si].ge != ge) {
2918 if(ISDBG(SUBSTEMS)) {
2919 fprintf(stderr,
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);
2922 }
2923 continue;
2924 }
2925 i=pairs[si]; /* the other side of this stem */
2926 if(i<0)
2927 continue; /* oops, no other side */
2928 pri=1;
2929 if( (sp[si].flags | sp[i].flags) & ST_END )
2930 pri=0;
2931 wd=abs(sp[i].value-value);
2932 if( prevbest == -1 || pri >prevpri
2933 || pri==prevpri && prevwd==0 || wd!=0 && wd<prevwd ) {
2934 prevbest=si;
2935 prevpri=pri;
2936 prevwd=wd;
2937 continue;
2938 }
2939 }
2940
2941 return prevbest;
2942 }
2943
2944 /* add the substems for one glyph entry
2945 * (called from groupsubstems())
2946 * returns 0 if all OK, 1 if too many groups
2947 */
2948
2949 static int gssentry_lastgrp=0; /* reset to 0 for each new glyph */
2950
2951 static int
2952 gssentry( /* crazy number of parameters */
2953 GENTRY *ge,
2954 STEM *hs, /* horizontal stems, sorted by value */
2955 short *hpairs,
2956 int nhs,
2957 STEM *vs, /* vertical stems, sorted by value */
2958 short *vpairs,
2959 int nvs,
2960 STEMBOUNDS *s,
2961 short *egp,
2962 int *nextvsi,
2963 int *nexthsi /* -2 means "check by yourself" */
2964 ) {
2965 enum {
2966 SI_VP, /* vertical primary */
2967 SI_HP, /* horizontal primary */
2968 SI_SIZE /* size of the array */
2969 };
2970 int si[SI_SIZE]; /* indexes of relevant stems */
2971
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 */
2976
2977 /* yet more temporary storage */
2978 short lb, hb, isvert;
2979 int conflict, grp;
2980 int i, j, x, y;
2981
2982
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
2989 * the last point.
2990 *
2991 */
2992
2993 /* start with the common part, the first point */
2994 x=ge->prev->ix3;
2995 y=ge->prev->iy3;
2996
2997 if(*nextvsi == -2)
2998 si[SI_VP]=findstemat(x, y, ge, vs, vpairs, nvs, -1);
2999 else {
3000 si[SI_VP]= *nextvsi; *nextvsi= -2;
3001 }
3002 if(*nexthsi == -2)
3003 si[SI_HP]=findstemat(y, x, ge, hs, hpairs, nhs, -1);
3004 else {
3005 si[SI_HP]= *nexthsi; *nexthsi= -2;
3006 }
3007
3008 /*
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.
3014 */
3015
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]);
3021 }
3022 }
3023
3024 if(si[SI_VP]+si[SI_HP] == -2) /* no stems, leave it alone */
3025 return 0;
3026
3027 /* build the array of relevant bounds */
3028 nr=0;
3029 for(i=0; i< sizeof(si) / sizeof(si[0]); i++) {
3030 STEM *sp;
3031 short *pairs;
3032 int step;
3033 int f;
3034 int nzones, firstzone, binzone, einzone;
3035 int btype, etype;
3036
3037 if(si[i] < 0)
3038 continue;
3039
3040 if(i<SI_HP) {
3041 r[nr].isvert=1; sp=vs; pairs=vpairs;
3042 } else {
3043 r[nr].isvert=0; sp=hs; pairs=hpairs;
3044 }
3045
3046 r[nr].low=sp[ si[i] ].value;
3047 r[nr].high=sp[ pairs[ si[i] ] ].value;
3048
3049 if(r[nr].low > r[nr].high) {
3050 j=r[nr].low; r[nr].low=r[nr].high; r[nr].high=j;
3051 step= -1;
3052 } else {
3053 step=1;
3054 }
3055
3056 /* handle the interaction with Blue Zones */
3057
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
3062 */
3063 if(sp[ si[i] ].flags & ST_UP) {
3064 r[nr].high+=20;
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;
3070 break;
3071 }
3072 } else {
3073 r[nr].low-=20;
3074 for(j=si[i]-1; j>=0; j--)
3075 if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
3076 == (ST_ZONE) ) {
3077 if(r[nr].low < sp[j].value+2)
3078 r[nr].low=sp[j].value+2;
3079 break;
3080 }
3081 }
3082 }
3083
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 )
3090 continue;
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;
3096 }
3097 einzone=1;
3098
3099 } else { /* the opposite direction */
3100 if(nzones==0) { /* beginning is in a blue zone */
3101 binzone=1;
3102 btype=sp[j].flags & ST_TOPZONE;
3103 }
3104 einzone=0;
3105 }
3106 }
3107
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;
3113 else
3114 r[nr].high=firstzone-2;
3115 } else {
3116 if(firstzone < r[nr].high-22)
3117 r[nr].low=r[nr].high-20;
3118 else
3119 r[nr].low=firstzone+2;
3120 }
3121 }
3122 }
3123
3124 if(ISDBG(SUBSTEMS))
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]]);
3128
3129 nr++;
3130 }
3131
3132 /* now try to find a group */
3133 conflict=0; /* no conflicts found yet */
3134 for(j=0; j<nr; j++)
3135 r[j].already=0;
3136
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;
3142 for(j=0; j<nr; j++)
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 */
3146 r[j].already=1;
3147 else
3148 conflict=1;
3149 }
3150
3151 if(conflict)
3152 break;
3153 }
3154
3155 if(conflict) { /* nope, check all the groups */
3156 for(j=0; j<nr; j++)
3157 r[j].already=0;
3158
3159 for(i=0, grp=0; i<egp[NSTEMGRP-1]; i++) {
3160 if(i == egp[grp]) { /* checked all stems in a group */
3161 if(conflict) {
3162 grp++; conflict=0; /* check the next group */
3163 for(j=0; j<nr; j++)
3164 r[j].already=0;
3165 } else
3166 break; /* insert into this group */
3167 }
3168
3169 lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
3170 for(j=0; j<nr; j++)
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 */
3174 r[j].already=1;
3175 else
3176 conflict=1;
3177 }
3178
3179 if(conflict)
3180 i=egp[grp]-1; /* fast forward to the next group */
3181 }
3182 }
3183
3184 /* do we have any empty group ? */
3185 if(conflict && grp < NSTEMGRP-1) {
3186 grp++; conflict=0;
3187 for(j=0; j<nr; j++)
3188 r[j].already=0;
3189 }
3190
3191 if(conflict) { /* oops, can't find any group to fit */
3192 return 1;
3193 }
3194
3195 /* OK, add stems to this group */
3196
3197 rexpand = nr;
3198 for(j=0; j<nr; j++)
3199 rexpand -= r[j].already;
3200
3201 if(rexpand > 0) {
3202 for(i=egp[NSTEMGRP-1]-1; i>=egp[grp]; i--)
3203 s[i+rexpand]=s[i];
3204 for(i=0; i<nr; i++)
3205 if(!r[i].already)
3206 s[egp[grp]++]=r[i];
3207 for(i=grp+1; i<NSTEMGRP; i++)
3208 egp[i]+=rexpand;
3209 }
3210
3211 ge->stemid = gssentry_lastgrp = grp;
3212 return 0;
3213 }
3214
3215 /*
3216 * Create the groups of substituted stems from the list.
3217 * Each group will be represented by a subroutine in the Subs
3218 * array.
3219 */
3220
3221 static void
3222 groupsubstems(
3223 GLYPH *g,
3224 STEM *hs, /* horizontal stems, sorted by value */
3225 short *hpairs,
3226 int nhs,
3227 STEM *vs, /* vertical stems, sorted by value */
3228 short *vpairs,
3229 int nvs
3230 )
3231 {
3232 GENTRY *ge;
3233 int i, j;
3234
3235 /* temporary storage */
3236 STEMBOUNDS s[MAX_STEMS*2];
3237 /* indexes in there, pointing past the end each stem group */
3238 short egp[NSTEMGRP];
3239
3240 int nextvsi, nexthsi; /* -2 means "check by yourself" */
3241
3242 for(i=0; i<NSTEMGRP; i++)
3243 egp[i]=0;
3244
3245 nextvsi=nexthsi= -2; /* processed no horiz/vert line */
3246
3247 gssentry_lastgrp = 0; /* reset the last group for new glyph */
3248
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 */
3252 continue;
3253 }
3254
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",
3257 g->name, NSTEMGRP);
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)
3260 ge->stemid= -1;
3261 g->nsg=0; /* just to be safe, already is 0 by initialization */
3262 return;
3263 }
3264
3265 /*
3266 * handle the last vert/horiz line of the path specially,
3267 * correct the hint for the first entry of the path
3268 */
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",
3272 g->name, NSTEMGRP);
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)
3275 ge->stemid= -1;
3276 g->nsg=0; /* just to be safe, already is 0 by initialization */
3277 return;
3278 }
3279 }
3280
3281 }
3282
3283 /* find the index of the first empty group - same as the number of groups */
3284 if(egp[0]>0) {
3285 for(i=1; i<NSTEMGRP && egp[i]!=egp[i-1]; i++)
3286 {}
3287 g->nsg=i;
3288 } else
3289 g->nsg=0;
3290
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 );
3296 j=0;
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');
3302 }
3303 fprintf(pfa_file, "\n");
3304 }
3305 }
3306
3307 if(g->nsg==1) { /* it would be the same as the main stems */
3308 /* so erase it */
3309 for (ge = g->entries; ge != 0; ge = ge->next)
3310 ge->stemid= -1;
3311 g->nsg=0;
3312 }
3313
3314 if(g->nsg>0) {
3315 if( (g->nsbs=malloc(g->nsg * sizeof (egp[0]))) == 0 ) {
3316 fprintf(stderr, "**** not enough memory for substituted hints ****\n");
3317 exit(255);
3318 }
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");
3322 exit(255);
3323 }
3324 memmove(g->sbstems, s, egp[g->nsg-1] * sizeof(s[0]));
3325 }
3326 }
3327
3328 void
3329 buildstems(
3330 GLYPH * g
3331 )
3332 {
3333 STEM hs[MAX_STEMS], vs[MAX_STEMS]; /* temporary working
3334 * storage */
3335 short hs_pairs[MAX_STEMS], vs_pairs[MAX_STEMS]; /* best pairs for these stems */
3336 STEM *sp;
3337 GENTRY *ge, *nge, *pge;
3338 int nx, ny;
3339 int ovalue;
3340 int totals, grp, lastgrp;
3341
3342 assertisint(g, "buildstems int");
3343
3344 g->nhs = g->nvs = 0;
3345 memset(hs, 0, sizeof hs);
3346 memset(vs, 0, sizeof vs);
3347
3348 /* first search the whole character for possible stem points */
3349
3350 for (ge = g->entries; ge != 0; ge = ge->next) {
3351 if (ge->type == GE_CURVE) {
3352
3353 /*
3354 * SURPRISE!
3355 * We consider the stems bound by the
3356 * H/V ends of the curves as flat ones.
3357 *
3358 * But we don't include the point on the
3359 * other end into the range.
3360 */
3361
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;
3366
3367 if (ge->ix1 < ge->prev->ix3)
3368 hs[g->nhs].flags = ST_FLAT | ST_UP;
3369 else
3370 hs[g->nhs].flags = ST_FLAT;
3371
3372 hs[g->nhs].origin = ge->prev->ix3;
3373 hs[g->nhs].ge = ge;
3374
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)
3379 hs[g->nhs].from--;
3380 } else {
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)
3384 hs[g->nhs].to++;
3385 }
3386 if (ge->ix1 != ge->prev->ix3)
3387 g->nhs++;
3388 }
3389 /* if it is vertical, add a vstem */
3390 else if (ge->ix1 == ge->prev->ix3) {
3391 vs[g->nvs].value = ge->ix1;
3392
3393 if (ge->iy1 > ge->prev->iy3)
3394 vs[g->nvs].flags = ST_FLAT | ST_UP;
3395 else
3396 vs[g->nvs].flags = ST_FLAT;
3397
3398 vs[g->nvs].origin = ge->prev->iy3;
3399 vs[g->nvs].ge = ge;
3400
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)
3405 vs[g->nvs].from--;
3406 } else {
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)
3410 vs[g->nvs].to++;
3411 }
3412
3413 if (ge->iy1 != ge->prev->iy3)
3414 g->nvs++;
3415 }
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;
3420
3421 if (ge->ix3 < ge->ix2)
3422 hs[g->nhs].flags = ST_FLAT | ST_UP;
3423 else
3424 hs[g->nhs].flags = ST_FLAT;
3425
3426 hs[g->nhs].origin = ge->ix3;
3427 hs[g->nhs].ge = ge->frwd;
3428
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 )
3433 hs[g->nhs].to++;
3434 } else {
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 )
3438 hs[g->nhs].from--;
3439 }
3440
3441 if (ge->ix3 != ge->ix2)
3442 g->nhs++;
3443 }
3444 /* if it is vertical, add a vstem */
3445 else if (ge->ix3 == ge->ix2) {
3446 vs[g->nvs].value = ge->ix3;
3447
3448 if (ge->iy3 > ge->iy2)
3449 vs[g->nvs].flags = ST_FLAT | ST_UP;
3450 else
3451 vs[g->nvs].flags = ST_FLAT;
3452
3453 vs[g->nvs].origin = ge->iy3;
3454 vs[g->nvs].ge = ge->frwd;
3455
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 )
3460 vs[g->nvs].to++;
3461 } else {
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 )
3465 vs[g->nvs].from--;
3466 }
3467
3468 if (ge->iy3 != ge->iy2)
3469 g->nvs++;
3470 } else {
3471
3472 /*
3473 * check the end of curve for a not smooth
3474 * local extremum
3475 */
3476 nge = ge->frwd;
3477
3478 if (nge == 0)
3479 continue;
3480 else if (nge->type == GE_LINE) {
3481 nx = nge->ix3;
3482 ny = nge->iy3;
3483 } else if (nge->type == GE_CURVE) {
3484 nx = nge->ix1;
3485 ny = nge->iy1;
3486 } else
3487 continue;
3488
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;
3493 hs[g->nhs].from
3494 = hs[g->nhs].to
3495 = hs[g->nhs].origin = ge->ix3;
3496 hs[g->nhs].ge = ge->frwd;
3497
3498 if (ge->ix3 < ge->ix2
3499 || nx < ge->ix3)
3500 hs[g->nhs].flags = ST_UP;
3501 else
3502 hs[g->nhs].flags = 0;
3503
3504 if (ge->ix3 != ge->ix2 || nx != ge->ix3)
3505 g->nhs++;
3506 }
3507 /*
3508 * the same point may be both horizontal and
3509 * vertical extremum
3510 */
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;
3515 vs[g->nvs].from
3516 = vs[g->nvs].to
3517 = vs[g->nvs].origin = ge->iy3;
3518 vs[g->nvs].ge = ge->frwd;
3519
3520 if (ge->iy3 > ge->iy2
3521 || ny > ge->iy3)
3522 vs[g->nvs].flags = ST_UP;
3523 else
3524 vs[g->nvs].flags = 0;
3525
3526 if (ge->iy3 != ge->iy2 || ny != ge->iy3)
3527 g->nvs++;
3528 }
3529 }
3530
3531 } else if (ge->type == GE_LINE) {
3532 nge = ge->frwd;
3533
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;
3543 } else {
3544 hs[g->nhs].flags = ST_FLAT;
3545 hs[g->nhs].from = ge->prev->ix3;
3546 hs[g->nhs].to = ge->ix3;
3547 }
3548 hs[g->nhs].origin = ge->ix3;
3549 hs[g->nhs].ge = ge->frwd;
3550
3551 pge = ge->bkwd;
3552
3553 /* add beginning as vstem */
3554 vs[g->nvs].value = pge->ix3;
3555 vs[g->nvs].origin
3556 = vs[g->nvs].from
3557 = vs[g->nvs].to = pge->iy3;
3558 vs[g->nvs].ge = ge;
3559
3560 if(pge->type==GE_CURVE)
3561 ovalue=pge->iy2;
3562 else
3563 ovalue=pge->prev->iy3;
3564
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;
3569 else
3570 vs[g->nvs].flags = 0;
3571
3572 if( vs[g->nvs].flags != 0 )
3573 g->nvs++;
3574
3575 /* add end as vstem */
3576 vs[g->nvs].value = ge->ix3;
3577 vs[g->nvs].origin
3578 = vs[g->nvs].from
3579 = vs[g->nvs].to = ge->iy3;
3580 vs[g->nvs].ge = ge->frwd;
3581
3582 if(nge->type==GE_CURVE)
3583 ovalue=nge->iy1;
3584 else
3585 ovalue=nge->iy3;
3586
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;
3591 else
3592 vs[g->nvs].flags = 0;
3593
3594 if( vs[g->nvs].flags != 0 )
3595 g->nvs++;
3596
3597 g->nhs++;
3598 }
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;
3608 } else {
3609 vs[g->nvs].flags = ST_FLAT;
3610 vs[g->nvs].from = ge->iy3;
3611 vs[g->nvs].to = ge->prev->iy3;
3612 }
3613 vs[g->nvs].origin = ge->iy3;
3614 vs[g->nvs].ge = ge->frwd;
3615
3616 pge = ge->bkwd;
3617
3618 /* add beginning as hstem */
3619 hs[g->nhs].value = pge->iy3;
3620 hs[g->nhs].origin
3621 = hs[g->nhs].from
3622 = hs[g->nhs].to = pge->ix3;
3623 hs[g->nhs].ge = ge;
3624
3625 if(pge->type==GE_CURVE)
3626 ovalue=pge->ix2;
3627 else
3628 ovalue=pge->prev->ix3;
3629
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;
3634 else
3635 hs[g->nhs].flags = 0;
3636
3637 if( hs[g->nhs].flags != 0 )
3638 g->nhs++;
3639
3640 /* add end as hstem */
3641 hs[g->nhs].value = ge->iy3;
3642 hs[g->nhs].origin
3643 = hs[g->nhs].from
3644 = hs[g->nhs].to = ge->ix3;
3645 hs[g->nhs].ge = ge->frwd;
3646
3647 if(nge->type==GE_CURVE)
3648 ovalue=nge->ix1;
3649 else
3650 ovalue=nge->ix3;
3651
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;
3656 else
3657 hs[g->nhs].flags = 0;
3658
3659 if( hs[g->nhs].flags != 0 )
3660 g->nhs++;
3661
3662 g->nvs++;
3663 }
3664 /*
3665 * check the end of line for a not smooth local
3666 * extremum
3667 */
3668 nge = ge->frwd;
3669
3670 if (nge == 0)
3671 continue;
3672 else if (nge->type == GE_LINE) {
3673 nx = nge->ix3;
3674 ny = nge->iy3;
3675 } else if (nge->type == GE_CURVE) {
3676 nx = nge->ix1;
3677 ny = nge->iy1;
3678 } else
3679 continue;
3680
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;
3685 hs[g->nhs].from
3686 = hs[g->nhs].to
3687 = hs[g->nhs].origin = ge->ix3;
3688 hs[g->nhs].ge = ge->frwd;
3689
3690 if (ge->ix3 < ge->prev->ix3
3691 || nx < ge->ix3)
3692 hs[g->nhs].flags = ST_UP;
3693 else
3694 hs[g->nhs].flags = 0;
3695
3696 if (ge->ix3 != ge->prev->ix3 || nx != ge->ix3)
3697 g->nhs++;
3698 }
3699 /*
3700 * the same point may be both horizontal and vertical
3701 * extremum
3702 */
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;
3707 vs[g->nvs].from
3708 = vs[g->nvs].to
3709 = vs[g->nvs].origin = ge->iy3;
3710 vs[g->nvs].ge = ge->frwd;
3711
3712 if (ge->iy3 > ge->prev->iy3
3713 || ny > ge->iy3)
3714 vs[g->nvs].flags = ST_UP;
3715 else
3716 vs[g->nvs].flags = 0;
3717
3718 if (ge->iy3 != ge->prev->iy3 || ny != ge->iy3)
3719 g->nvs++;
3720 }
3721 }
3722 }
3723
3724 g->nhs=addbluestems(hs, g->nhs);
3725 sortstems(hs, g->nhs);
3726 sortstems(vs, g->nvs);
3727
3728 if (ISDBG(STEMS))
3729 debugstems(g->name, hs, g->nhs, vs, g->nvs);
3730
3731 /* find the stems interacting with the Blue Zones */
3732 markbluestems(hs, g->nhs);
3733
3734 if(subhints) {
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);
3739
3740 if (ISDBG(SUBSTEMS))
3741 fprintf(pfa_file, "%% %s: joining subst vertical stems\n", g->name);
3742 joinsubstems(vs, vs_pairs, g->nvs, 0);
3743
3744 groupsubstems(g, hs, hs_pairs, g->nhs, vs, vs_pairs, g->nvs);
3745 }
3746
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);
3753
3754 if (ISDBG(MAINSTEMS))
3755 debugstems(g->name, hs, g->nhs, vs, g->nvs);
3756
3757 if(g->nhs > 0) {
3758 if ((sp = malloc(sizeof(STEM) * g->nhs)) == 0) {
3759 fprintf(stderr, "**** not enough memory for hints ****\n");
3760 exit(255);
3761 }
3762 g->hstems = sp;
3763 memcpy(sp, hs, sizeof(STEM) * g->nhs);
3764 } else
3765 g->hstems = 0;
3766
3767 if(g->nvs > 0) {
3768 if ((sp = malloc(sizeof(STEM) * g->nvs)) == 0) {
3769 fprintf(stderr, "**** not enough memory for hints ****\n");
3770 exit(255);
3771 }
3772 g->vstems = sp;
3773 memcpy(sp, vs, sizeof(STEM) * g->nvs);
3774 } else
3775 g->vstems = 0;
3776
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.
3780 */
3781
3782 totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
3783 lastgrp = -1;
3784
3785 for (ge = g->entries; ge != 0; ge = ge->next) {
3786 grp=ge->stemid;
3787 if(grp >= 0 && grp != lastgrp) {
3788 if(grp==0)
3789 totals += g->nsbs[0];
3790 else
3791 totals += g->nsbs[grp] - g->nsbs[grp-1];
3792
3793 lastgrp = grp;
3794 }
3795 }
3796
3797 /* be on the safe side, check for >= , not > */
3798 if(totals >= max_stemdepth) { /* oops, too deep */
3799 WARNING_2 {
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);
3802 }
3803 if(g->nsg > 0) {
3804 for (ge = g->entries; ge != 0; ge = ge->next)
3805 ge->stemid = -1;
3806 free(g->sbstems); g->sbstems = 0;
3807 free(g->nsbs); g->nsbs = 0;
3808 g->nsg = 0;
3809 }
3810 }
3811
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 */
3816 WARNING_2 {
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);
3819 }
3820 if(g->vstems) {
3821 free(g->vstems); g->vstems = 0; g->nvs = 0;
3822 }
3823 if(g->hstems) {
3824 free(g->hstems); g->hstems = 0; g->nhs = 0;
3825 }
3826 }
3827 }
3828
3829 /* convert weird curves that are close to lines into lines.
3830 */
3831
3832 void
3833 fstraighten(
3834 GLYPH * g
3835 )
3836 {
3837 GENTRY *ge, *pge, *nge, *ige;
3838 double df;
3839 int dir;
3840 double iln, oln;
3841 int svdir, i, o;
3842
3843 for (ige = g->entries; ige != 0; ige = ige->next) {
3844 if (ige->type != GE_CURVE)
3845 continue;
3846
3847 ge = ige;
3848 pge = ge->bkwd;
3849 nge = ge->frwd;
3850
3851 df = 0.;
3852
3853 /* look for vertical then horizontal */
3854 for(i=0; i<2; i++) {
3855 o = !i; /* other axis */
3856
3857 iln = fabs(ge->fpoints[i][2] - pge->fpoints[i][2]);
3858 oln = fabs(ge->fpoints[o][2] - pge->fpoints[o][2]);
3859 /*
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 ?)
3863 */
3864 if( oln < 1.
3865 || ge->fpoints[o][2] == ge->fpoints[o][1]
3866 || ge->fpoints[o][0] == pge->fpoints[o][2]
3867 || iln > 2.
3868 || iln > 1. && iln/oln > 0.1 )
3869 continue;
3870
3871
3872 if(ISDBG(STRAIGHTEN))
3873 fprintf(stderr,"** straighten almost %s\n", (i? "horizontal":"vertical"));
3874
3875 df = ge->fpoints[i][2] - pge->fpoints[i][2];
3876 dir = fsign(ge->fpoints[o][2] - pge->fpoints[o][2]);
3877 ge->type = GE_LINE;
3878
3879 /*
3880 * suck in all the sequence of such almost lines
3881 * going in the same direction but not deviating
3882 * too far from vertical
3883 */
3884 iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3885 oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3886
3887 while (fabs(df) <= 5 && nge->type == GE_CURVE
3888 && dir == fsign(oln) /* that also gives oln != 0 */
3889 && iln <= 2.
3890 && ( iln <= 1. || iln/fabs(oln) <= 0.1 ) ) {
3891 ge->fx3 = nge->fx3;
3892 ge->fy3 = nge->fy3;
3893
3894 if(ISDBG(STRAIGHTEN))
3895 fprintf(stderr,"** straighten collapsing %s\n", (i? "horizontal":"vertical"));
3896 freethisge(nge);
3897 fixendpath(ge);
3898 pge = ge->bkwd;
3899 nge = ge->frwd;
3900
3901 df = ge->fpoints[i][2] - pge->fpoints[i][2];
3902
3903 iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
3904 oln = nge->fpoints[o][2] - ge->fpoints[o][2];
3905 }
3906
3907 /* now check what do we have as previous/next line */
3908
3909 if(ge != pge) {
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 */
3914 pge->fx3 = ge->fx3;
3915 pge->fy3 = ge->fy3;
3916
3917 ige = freethisge(ge)->prev; /* keep the iterator valid */
3918 ge = pge;
3919 fixendpath(ge);
3920 pge = ge->bkwd;
3921 }
3922 }
3923
3924 if(ge != nge) {
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 */
3929 ge->fx3 = nge->fx3;
3930 ge->fy3 = nge->fy3;
3931
3932 freethisge(nge);
3933 fixendpath(ge);
3934 pge = ge->bkwd;
3935 nge = ge->frwd;
3936
3937 }
3938 }
3939
3940 if(ge != pge) {
3941 /* try to align the lines if neccessary */
3942 if(df != 0.)
3943 fclosegap(ge, ge, i, df, NULL);
3944 } else {
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 */
3948 return;
3949 ige = ige->prev;
3950 }
3951
3952 break; /* don't bother looking at the other axis */
3953 }
3954 }
3955 }
3956
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
3961 */
3962
3963 static int
3964 fsqequation(
3965 double a,
3966 double b,
3967 double c,
3968 double *res,
3969 double min,
3970 double max
3971 )
3972 {
3973 double D;
3974 int n;
3975
3976 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq(%g,%g,%g) [%g;%g]\n", a, b, c, min, max);
3977
3978 if(fabs(a) < 0.000001) { /* if a linear equation */
3979 n=0;
3980 if(fabs(b) < 0.000001) /* not an equation at all */
3981 return 0;
3982 res[0] = -c/b;
3983 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: linear t=%g\n", res[0]);
3984 if(res[0] >= min && res[0] <= max)
3985 n++;
3986 return n;
3987 }
3988
3989 D = b*b - 4.0*a*c;
3990 if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: D=%g\n", D);
3991 if(D<0)
3992 return 0;
3993
3994 D = sqrt(D);
3995
3996 n=0;
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)
4000 n++;
4001
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)
4005 n++;
4006
4007 /* return 2nd solution only if it's different enough */
4008 if(n==2 && fabs(res[0]-res[1])<0.000001)
4009 n=1;
4010
4011 return n;
4012 }
4013
4014 /* check that the curves don't cross quadrant boundary */
4015 /* (float) */
4016
4017 /*
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.
4021
4022 The horizontal points are where the derivative
4023 dy/dx is equal to 0. But the Bezier curves are defined by
4024 parametric formulas
4025 x=fx(t)
4026 y=fy(t)
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.
4032
4033 The formulas are:
4034
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)
4038 */
4039
4040 void
4041 ffixquadrants(
4042 GLYPH *g
4043 )
4044 {
4045 GENTRY *ge, *nge;
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 */
4050
4051 for (ge = g->entries; ge != 0; ge = ge->next) {
4052 if (ge->type != GE_CURVE)
4053 continue;
4054
4055 doagain:
4056 np = 0; /* no split points yet */
4057 if(ISDBG(QUAD)) {
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,
4060 ge->fx3, ge->fy3);
4061 }
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];
4066
4067 oldnp = np;
4068 np += fsqequation(
4069 3.0*(-a + 3.0*pts[0] - 3.0*pts[1] + pts[2]),
4070 6.0*(a - 2.0*pts[0] + pts[1]),
4071 3.0*(-a + pts[0]),
4072 &sp[np],
4073 0.0, 1.0); /* XXX range is [0;1] */
4074
4075 if(np == oldnp)
4076 continue;
4077
4078 if(ISDBG(QUAD))
4079 fprintf(stderr, "%s: 0x%x: %d pts(%c): ",
4080 g->name, ge, np-oldnp, i? 'y':'x');
4081
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.
4086 */
4087 for(j = oldnp; j<np; j++) {
4088 dir[j] = i;
4089 if(ISDBG(QUAD))
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");
4095 goto doagain;
4096 }
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");
4102 goto doagain;
4103 }
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");
4110 goto doagain;
4111 }
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");
4117 goto doagain;
4118 }
4119 sp[j] = sp[j+1]; np--; j--;
4120 if(ISDBG(QUAD)) fprintf(stderr, "(rear flat) ");
4121 }
4122 }
4123 if(ISDBG(QUAD)) fprintf(stderr, "\n");
4124 }
4125
4126 if(np==0) /* no split points, leave it alone */
4127 continue;
4128
4129 if(ISDBG(QUAD)) {
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);
4133 for(i=0; i<np; i++)
4134 fprintf(stderr, "%g(%c) ", sp[i], dir[i] ? 'y':'x');
4135 fprintf(stderr, "\n");
4136 }
4137
4138 /* sort the points ascending */
4139 for(i=0; i<np; i++)
4140 for(j=i+1; j<np; j++)
4141 if(sp[i] > sp[j]) {
4142 a = sp[i]; sp[i] = sp[j]; sp[j] = a;
4143 }
4144
4145 /* now finally do the split on each point */
4146 for(j=0; j<np; j++) {
4147 double k1, k2, c;
4148
4149 k1 = sp[j];
4150 k2 = 1 - k1;
4151
4152 if(ISDBG(QUAD)) fprintf(stderr, " 0x%x %g/%g\n", ge, k1, k2);
4153
4154 nge = newgentry(GEF_FLOAT);
4155 (*nge) = (*ge);
4156
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];
4161
4162 /* calculate new internal points */
4163 c = SPLIT(a, b);
4164
4165 ge->fpoints[i][0] = SPLIT(ge->prev->fpoints[i][2], a);
4166 ge->fpoints[i][1] = SPLIT(ge->fpoints[i][0], c);
4167
4168 nge->fpoints[i][1] = SPLIT(b, nge->fpoints[i][2]);
4169 nge->fpoints[i][0] = SPLIT(c, nge->fpoints[i][1]);
4170
4171 ge->fpoints[i][2] = SPLIT(ge->fpoints[i][1],
4172 + nge->fpoints[i][0]);
4173 }
4174 #undef SPLIT
4175
4176 addgeafter(ge, nge);
4177
4178 /* go to the next part, adjust remaining points */
4179 ge = nge;
4180 for(i=j+1; i<np; i++)
4181 sp[i] = (sp[i]-k1) / k2;
4182 }
4183 }
4184
4185 }
4186
4187 /* check if a curve is a zigzag */
4188
4189 static int
4190 iiszigzag(
4191 GENTRY *ge
4192 )
4193 {
4194 double k, k1, k2;
4195 int a, b;
4196
4197 if (ge->type != GE_CURVE)
4198 return 0;
4199
4200 a = ge->iy2 - ge->iy1;
4201 b = ge->ix2 - ge->ix1;
4202 if(a == 0) {
4203 if(b == 0) {
4204 return 0;
4205 } else
4206 k = FBIGVAL;
4207 } else
4208 k = fabs((double) b / (double) a);
4209
4210 a = ge->iy1 - ge->prev->iy3;
4211 b = ge->ix1 - ge->prev->ix3;
4212 if(a == 0) {
4213 if(b == 0) {
4214 return 0;
4215 } else
4216 k1 = FBIGVAL;
4217 } else
4218 k1 = fabs((double) b / (double) a);
4219
4220 a = ge->iy3 - ge->iy2;
4221 b = ge->ix3 - ge->ix2;
4222 if(a == 0) {
4223 if(b == 0) {
4224 return 0;
4225 } else
4226 k2 = FBIGVAL;
4227 } else
4228 k2 = fabs((double) b / (double) a);
4229
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)
4232 return 0;
4233 else
4234 return 1;
4235 }
4236
4237 /* check if a curve is a zigzag - floating */
4238
4239 static int
4240 fiszigzag(
4241 GENTRY *ge
4242 )
4243 {
4244 double k, k1, k2;
4245 double a, b;
4246
4247 if (ge->type != GE_CURVE)
4248 return 0;
4249
4250 a = fabs(ge->fy2 - ge->fy1);
4251 b = fabs(ge->fx2 - ge->fx1);
4252 if(a < FEPS) {
4253 if(b < FEPS) {
4254 return 0;
4255 } else
4256 k = FBIGVAL;
4257 } else
4258 k = b / a;
4259
4260 a = fabs(ge->fy1 - ge->prev->fy3);
4261 b = fabs(ge->fx1 - ge->prev->fx3);
4262 if(a < FEPS) {
4263 if(b < FEPS) {
4264 return 0;
4265 } else
4266 k1 = FBIGVAL;
4267 } else
4268 k1 = b / a;
4269
4270 a = fabs(ge->fy3 - ge->fy2);
4271 b = fabs(ge->fx3 - ge->fx2);
4272 if(a < FEPS) {
4273 if(b < FEPS) {
4274 return 0;
4275 } else
4276 k2 = FBIGVAL;
4277 } else
4278 k2 = b / a;
4279
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)
4282 return 0;
4283 else
4284 return 1;
4285 }
4286
4287 /* split the zigzag-like curves into two parts */
4288
4289 void
4290 fsplitzigzags(
4291 GLYPH * g
4292 )
4293 {
4294 GENTRY *ge, *nge;
4295 double a, b, c, d;
4296
4297 assertisfloat(g, "splitting zigzags");
4298 for (ge = g->entries; ge != 0; ge = ge->next) {
4299 if (ge->type != GE_CURVE)
4300 continue;
4301
4302 /* if the curve is not a zigzag */
4303 if ( !fiszigzag(ge) ) {
4304 continue;
4305 }
4306
4307 if(ISDBG(FCONCISE)) {
4308 double maxsc1, maxsc2;
4309 fprintf(stderr, "split a zigzag ");
4310 fnormalizege(ge);
4311 if( fcrossraysge(ge, ge, &maxsc1, &maxsc2, NULL) ) {
4312 fprintf(stderr, "sc1=%g sc2=%g\n", maxsc1, maxsc2);
4313 } else {
4314 fprintf(stderr, "(rays don't cross)\n");
4315 }
4316 }
4317 /* split the curve by t=0.5 */
4318 nge = newgentry(GEF_FLOAT);
4319 (*nge) = (*ge);
4320 nge->type = GE_CURVE;
4321
4322 a = ge->prev->fx3;
4323 b = ge->fx1;
4324 c = ge->fx2;
4325 d = ge->fx3;
4326 nge->fx3 = d;
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.;
4332
4333 a = ge->prev->fy3;
4334 b = ge->fy1;
4335 c = ge->fy2;
4336 d = ge->fy3;
4337 nge->fy3 = d;
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.;
4343
4344 addgeafter(ge, nge);
4345
4346 if(ISDBG(FCONCISE)) {
4347 dumppaths(g, ge, nge);
4348 }
4349 }
4350 }
4351
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
4355 */
4356
4357 static GENTRY *
4358 freethisge(
4359 GENTRY *ge
4360 )
4361 {
4362 GENTRY *xge;
4363
4364 if (ge->bkwd != ge->prev) {
4365 /* at beginning of the contour */
4366
4367 xge = ge->bkwd;
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 */
4371
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;
4375 else
4376 ge->prev->prev->next = ge->next->next;
4377
4378 if(ge->next->next) {
4379 ge->next->next->prev = ge->prev->prev;
4380 ge->next->next->bkwd = ge->prev->bkwd;
4381 }
4382
4383 xge = ge->next->next;
4384 free(ge->prev); free(ge->next); free(ge);
4385 return xge;
4386 }
4387
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;
4392 } else {
4393 ge->prev->ix3 = xge->ix3;
4394 ge->prev->iy3 = xge->iy3;
4395 }
4396 } else if(ge->frwd != ge->next) {
4397 /* at end of the contour */
4398
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;
4404 } else {
4405 xge->ix3 = ge->bkwd->ix3;
4406 xge->iy3 = ge->bkwd->iy3;
4407 }
4408 }
4409
4410 ge->prev->next = ge->next;
4411 ge->next->prev = ge->prev;
4412 ge->bkwd->frwd = ge->frwd;
4413 ge->frwd->bkwd = ge->bkwd;
4414
4415 xge = ge->next;
4416 free(ge);
4417 return xge;
4418 }
4419
4420 /* inserts a new gentry (LINE or CURVE) after another (MOVE
4421 * or LINE or CURVE)
4422 * corrects the first GE_MOVE if neccessary
4423 */
4424
4425 static void
4426 addgeafter(
4427 GENTRY *oge, /* after this */
4428 GENTRY *nge /* insert this */
4429 )
4430 {
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;
4436 } else {
4437 nge->frwd = oge->next;
4438 nge->bkwd = oge->next->bkwd;
4439 oge->next->bkwd->frwd = nge;
4440 oge->next->bkwd = nge;
4441 }
4442 } else {
4443 nge->frwd = oge->frwd;
4444 nge->bkwd = oge;
4445 oge->frwd->bkwd = nge;
4446 oge->frwd = nge;
4447 }
4448
4449 nge->next = oge->next;
4450 nge->prev = oge;
4451 oge->next->prev = nge;
4452 oge->next = nge;
4453
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;
4459 } else {
4460 nge->frwd->prev->ix3 = nge->ix3;
4461 nge->frwd->prev->iy3 = nge->iy3;
4462 }
4463 }
4464 }
4465
4466 /*
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
4470 */
4471
4472 static void
4473 fixendpath(
4474 GENTRY *ge
4475 )
4476 {
4477 GENTRY *mge;
4478
4479 mge = ge->frwd->prev;
4480 if(mge->type == GE_MOVE) {
4481 if(ge->flags & GEF_FLOAT) {
4482 mge->fx3 = ge->fx3;
4483 mge->fy3 = ge->fy3;
4484 } else {
4485 mge->ix3 = ge->ix3;
4486 mge->iy3 = ge->iy3;
4487 }
4488 }
4489 }
4490
4491 /*
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.
4499 */
4500
4501 static double
4502 fclosegap(
4503 GENTRY *from,
4504 GENTRY *to,
4505 int axis,
4506 double gap,
4507 double *ret
4508 )
4509 {
4510 #define TIMESLARGER 10. /* how many times larger must be a curve to not change too much */
4511 double rm[2];
4512 double oldpos[2];
4513 double times, limit, df, dx;
4514 int j, k;
4515 GENTRY *xge, *pge, *nge, *bge[2];
4516
4517 /* remember the old points to calculate ret */
4518 oldpos[0] = from->prev->fpoints[axis][2];
4519 oldpos[1] = to->fpoints[axis][2];
4520
4521 rm[0] = rm[1] = gap / 2. ;
4522
4523 bge[0] = from; /* this is convenient for iterations */
4524 bge[1] = to;
4525
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. ) {
4528
4529 if(rm[0]+rm[1] == 0.)
4530 break;
4531
4532 /* iterate in both directions, backwards then forwards */
4533 for(j = 0; j<2; j++) {
4534
4535 if(rm[j] == 0.) /* if this direction is exhausted */
4536 continue;
4537
4538 limit = fabs(rm[j]) * (1.+times);
4539
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 */
4544 continue;
4545
4546 if( df >= fabs(rm[j]) )
4547 df = rm[j];
4548 else
4549 df *= fsign(rm[j]); /* we may cover this part of rm */
4550
4551 rm[j] -= df;
4552 limit = fabs(rm[j]) * (1.+times);
4553
4554 if(xge->type == GE_CURVE) { /* correct internal points */
4555 double scale = ((dx+df) / dx) - 1.;
4556 double base;
4557
4558 if(j)
4559 base = xge->fpoints[axis][2];
4560 else
4561 base = xge->prev->fpoints[axis][2];
4562
4563 for(k = 0; k<2; k++)
4564 xge->fpoints[axis][k] += scale *
4565 (xge->fpoints[axis][k] - base);
4566 }
4567
4568 /* move all the intermediate lines */
4569 if(j) {
4570 df = -df; /* absolute direction */
4571 pge = bge[1]->bkwd;
4572 nge = xge->bkwd;
4573 } else {
4574 xge->fpoints[axis][2] += df;
4575 pge = bge[0];
4576 nge = xge->frwd;
4577 }
4578 while(nge != pge) {
4579 if(nge->type == GE_CURVE) {
4580 nge->fpoints[axis][0] +=df;
4581 nge->fpoints[axis][1] +=df;
4582 }
4583 nge->fpoints[axis][2] += df;
4584 if(nge->next != nge->frwd) { /* last entry of contour */
4585 nge->frwd->prev->fpoints[axis][2] += df;
4586 }
4587 nge = nge->cntr[!j];
4588 }
4589
4590 if(rm[j] == 0.)
4591 break;
4592 }
4593 }
4594 }
4595
4596 /* find the difference */
4597 oldpos[0] -= from->prev->fpoints[axis][2];
4598 oldpos[1] -= to->fpoints[axis][2];
4599
4600 if(ret) {
4601 ret[0] = oldpos[0] - from->prev->fpoints[axis][2];
4602 ret[1] = oldpos[1] - to->fpoints[axis][2];
4603 }
4604
4605 #if 0
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]);
4610 }
4611 #endif
4612
4613 return rm[0]+rm[1];
4614 #undef TIMESLARGER
4615 }
4616
4617 /* remove the lines or curves smaller or equal to the size limit */
4618
4619 static void
4620 fdelsmall(
4621 GLYPH *g,
4622 double minlen
4623 )
4624 {
4625 GENTRY *ge, *nge, *pge, *xge, *next;
4626 int i, k;
4627 double dx, dy, d2, d2m;
4628 double minlen2;
4629 #define TIMESLARGER 10. /* how much larger must be a curve to not change too much */
4630
4631 minlen2 = minlen*minlen;
4632
4633 for (ge = g->entries; ge != 0; ge = next) {
4634 next = ge->next;
4635
4636 if (ge->type != GE_CURVE && ge->type != GE_LINE)
4637 continue;
4638
4639 d2m = 0;
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;
4643 d2 = dx*dx + dy*dy;
4644 if(d2m < d2)
4645 d2m = d2;
4646 }
4647
4648 if( d2m > minlen2 ) { /* line is not too small */
4649 /* XXX add more normalization here */
4650 continue;
4651 }
4652
4653 /* if the line is too small */
4654
4655 /* check forwards if we have a whole sequence of them */
4656 nge = ge;
4657 for(xge = ge->frwd; xge != ge; xge = xge->frwd) {
4658 d2m = 0;
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;
4662 d2 = dx*dx + dy*dy;
4663 if(d2m < d2)
4664 d2m = d2;
4665 }
4666 if( d2m > minlen2 ) /* line is not too small */
4667 break;
4668 nge = xge;
4669 if(next == nge) /* move the next step past this sequence */
4670 next = next->next;
4671 }
4672
4673 /* check backwards if we have a whole sequence of them */
4674 pge = ge;
4675 for(xge = ge->bkwd; xge != ge; xge = xge->bkwd) {
4676 d2m = 0;
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;
4680 d2 = dx*dx + dy*dy;
4681 if(d2m < d2)
4682 d2m = d2;
4683 }
4684 if( d2m > minlen2 ) /* line is not too small */
4685 break;
4686 pge = xge;
4687 }
4688
4689 /* now we have a sequence of small fragments in pge...nge (inclusive) */
4690
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);
4695 }
4696
4697 /* reduce whole sequence to one part and remember the middle point */
4698 if(pge != nge) {
4699 while(1) {
4700 xge = pge->frwd;
4701 if(xge == nge) {
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;
4707 freethisge(nge);
4708 break;
4709 }
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;
4716 freethisge(nge);
4717 freethisge(xge);
4718 break;
4719 }
4720 freethisge(pge); pge = xge;
4721 xge = nge->bkwd; freethisge(nge); nge = xge;
4722 }
4723 }
4724 ge = pge;
4725
4726 /* check if the whole sequence is small */
4727 dx = ge->fx3 - ge->prev->fx3;
4728 dy = ge->fy3 - ge->prev->fy3;
4729 d2 = dx*dx + dy*dy;
4730
4731 if( d2 > minlen2 ) { /* no, it is not */
4732 double b, d;
4733
4734 WARNING_3 fprintf(stderr, "glyph %s had a sequence of fragments < %g points each, reduced to one curve\n",
4735 g->name, minlen);
4736
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;
4743 d2 = dx*dx + dy*dy;
4744
4745 dx = ge->fx3 - ge->fx1;
4746 dy = ge->fy3 - ge->fy1;
4747 d2m = dx*dx + dy*dy;
4748
4749 if(d2 > minlen2 && d2m > minlen2) { /* make two straights */
4750 nge = newgentry(GEF_FLOAT);
4751 *nge = *ge;
4752
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;
4759 }
4760 }
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;
4766 }
4767 }
4768 continue;
4769 }
4770
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",
4773 g->name, minlen);
4774
4775 next = freethisge(ge);
4776 continue;
4777 }
4778
4779 /* now close the gap by x and y */
4780 for(i=0; i<2; i++) {
4781 double gap;
4782
4783 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
4784 if( fclosegap(ge, ge, i, gap, NULL) != 0.0 ) {
4785 double scale, base;
4786
4787 /* not good, as the last resort just scale the next line */
4788 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
4789
4790 if(ISDBG(FCONCISE))
4791 fprintf(stderr, " last resort on %c: closing next by %g\n",
4792 (i==0 ? 'x' : 'y'), gap);
4793
4794 nge = ge->frwd;
4795 base = nge->fpoints[i][2];
4796 dx = ge->fpoints[i][2] - base;
4797 if(fabs(dx) < FEPS)
4798 continue;
4799
4800 scale = ((dx-gap) / dx);
4801
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);
4806
4807 ge->fpoints[i][2] -= gap;
4808 }
4809 }
4810
4811 /* OK, the gap is closed - remove this useless GENTRY */
4812 freethisge(ge);
4813 }
4814 #undef TIMESLARGER
4815 }
4816
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.
4823 *
4824 * For convenience there are 2 front-end functions taking
4825 * arguments in different formats
4826 */
4827
4828 struct ray {
4829 double x1, y1, x2, y2;
4830 int isvert;
4831 double k, b; /* lines are represented as y = k*x + b */
4832 double *maxp;
4833 };
4834 static struct ray ray[3];
4835
4836 /* the back-end doing the actual work
4837 * the rays are defined in the static array ray[]
4838 */
4839
4840 static int
4841 fcrossraysxx(
4842 double crossdot[2][2]
4843 )
4844 {
4845 double x, y, max;
4846 int i;
4847
4848 for(i=0; i<2; i++) {
4849 if(ray[i].x1 == ray[i].x2)
4850 ray[i].isvert = 1;
4851 else {
4852 ray[i].isvert = 0;
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;
4855 }
4856 }
4857
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 */
4861 }
4862
4863 if(ray[1].isvert) {
4864 ray[2] = ray[0]; /* exchange them */
4865 ray[0] = ray[1];
4866 ray[1] = ray[2];
4867 }
4868
4869 if(ray[0].isvert) {
4870 x = ray[0].x1;
4871 } else {
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 */
4876 }
4877 x = (ray[1].b - ray[0].b) / (ray[0].k - ray[1].k) ;
4878 }
4879 y = ray[1].k * x + ray[1].b;
4880
4881 for(i=0; i<2; i++) {
4882 if(ray[i].isvert)
4883 max = (y - ray[i].y1) / (ray[i].y2 - ray[i].y1);
4884 else
4885 max = (x - ray[i].x1) / (ray[i].x2 - ray[i].x1);
4886 /* check if wrong sides of rays cross */
4887 if( max < 0 ) {
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);
4890 return 0;
4891 }
4892 if(ray[i].maxp)
4893 *ray[i].maxp = max;
4894 }
4895 if(crossdot != 0) {
4896 crossdot[0][0] = crossdot[1][0] = x;
4897 crossdot[0][1] = crossdot[1][1] = y;
4898 }
4899 return 1;
4900 }
4901
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
4906 */
4907
4908 int
4909 fcrossrayscv(
4910 double curve[4][2 /*X,Y*/],
4911 double *max1,
4912 double *max2
4913 )
4914 {
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];
4919 ray[0].maxp = max1;
4920
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];
4925 ray[1].maxp = max2;
4926
4927 return fcrossraysxx(&curve[1]);
4928 }
4929
4930 /* the front-end getting the arguments from gentries:
4931 * rays are defined as beginning of curve1 and end of curve 2
4932 */
4933
4934 int
4935 fcrossraysge(
4936 GENTRY *ge1,
4937 GENTRY *ge2,
4938 double *max1,
4939 double *max2,
4940 double crossdot[2][2]
4941 )
4942 {
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];
4947 ray[0].maxp = max1;
4948
4949 ray[1].x1 = ge2->fx3;
4950 ray[1].y1 = ge2->fy3;
4951 if(ge2->rtg < 0) {
4952 ray[1].x2 = ge2->prev->fx3;
4953 ray[1].y2 = ge2->prev->fy3;
4954 } else {
4955 ray[1].x2 = ge2->fpoints[X][ge2->rtg];
4956 ray[1].y2 = ge2->fpoints[Y][ge2->rtg];
4957 }
4958 ray[1].maxp = max2;
4959
4960 return fcrossraysxx(crossdot);
4961 }
4962
4963 /* debugging printout functions */
4964
4965 #if defined(DEBUG_DOTSEG) || defined(DEBUG_DOTCURVE) || defined(DEBUG_APPROXCV)
4966
4967 /* for debugging */
4968 static
4969 printdot(
4970 double dot[2]
4971 )
4972 {
4973 fprintf(stderr, "(%g,%g)", dot[0], dot[1]);
4974 }
4975
4976 static
4977 printseg(
4978 double seg[2][2]
4979 )
4980 {
4981 putc('[', stderr);
4982 printdot(seg[0]);
4983 putc(' ', stderr);
4984 printdot(seg[1]);
4985 putc(']', stderr);
4986 }
4987
4988 #endif /* DEBUG_* */
4989
4990 /*
4991 * Find squared distance from a dot to a line segment
4992 */
4993
4994 double
4995 fdotsegdist2(
4996 double seg[2][2 /*X,Y*/],
4997 double dot[2 /*X,Y*/]
4998 )
4999 {
5000 #define x1 seg[0][X]
5001 #define y1 seg[0][Y]
5002 #define x2 seg[1][X]
5003 #define y2 seg[1][Y]
5004 #define xdot dot[X]
5005 #define ydot dot[Y]
5006
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 */
5011
5012 /* handle the situation where the nearest point of the segment is its end */
5013 #define HANDLE_LIMITS(less12, lesscr1, lesscr2) \
5014 if( less12 ) { \
5015 if( lesscr1 ) { \
5016 xcross = x1; \
5017 ycross = y1; \
5018 } else if( !(lesscr2) ) { \
5019 xcross = x2; \
5020 ycross = y2; \
5021 } \
5022 } else { \
5023 if( !(lesscr1) ) { \
5024 xcross = x1; \
5025 ycross = y1; \
5026 } else if( lesscr2 ) { \
5027 xcross = x2; \
5028 ycross = y2; \
5029 } \
5030 } \
5031 /* end of macro */
5032
5033
5034 dx = x2 - x1;
5035 dy = y2 - y1;
5036
5037 if(fabs(dx) < FEPS) {
5038 /* special case - vertical line */
5039 #ifdef DEBUG_DOTSEG
5040 printf("vertical line!\n");
5041 #endif
5042 xcross = x1;
5043 ycross = ydot;
5044 HANDLE_LIMITS( y1 < y2, ycross < y1, ycross < y2);
5045 } else if(fabs(dy) < FEPS) {
5046 /* special case - horizontal line */
5047 #ifdef DEBUG_DOTSEG
5048 printf("horizontal line!\n");
5049 #endif
5050 xcross = xdot;
5051 ycross = y1;
5052 HANDLE_LIMITS( x1 < x2, xcross < x1, xcross < x2)
5053 } else {
5054 kline = dy/dx;
5055 bline = y1 - x1*kline;
5056 kperp = -1./kline;
5057 bperp = ydot - xdot*kperp;
5058
5059 xcross = (bline-bperp) / (kperp-kline);
5060 ycross = kline*xcross + bline;
5061
5062 HANDLE_LIMITS( x1 < x2, xcross < x1, xcross < x2)
5063 }
5064 #ifdef DEBUG_DOTSEG
5065 printf("crossover at (%g,%g)\n", xcross, ycross);
5066 #endif
5067
5068 dx = xdot-xcross;
5069 dy = ydot-ycross;
5070 return dx*dx+dy*dy;
5071 #undef x1
5072 #undef y1
5073 #undef x2
5074 #undef y2
5075 #undef xdot
5076 #undef ydot
5077 #undef HANDLE_LIMITS
5078 }
5079
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
5083 * distance in there
5084 */
5085
5086 double
5087 fdotcurvdist2(
5088 double curve[4][2 /*X,Y*/ ],
5089 struct dot_dist *dots,
5090 int ndots, /* number of entries in dots */
5091 double *maxp
5092 )
5093 {
5094 /* a curve is approximated by this many straight segments */
5095 #define NAPSECT 16
5096 /* a curve is divided into this many sections with equal weight each */
5097 #define NWSECT 4
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 */
5105 double sum[NWSECT];
5106 /* counts by sections */
5107 double count[NWSECT];
5108 int d, i, j;
5109 int id1, id2;
5110 double dist1, dist2, dist3, dx, dy, x, y;
5111 double max = 0.;
5112
5113 if(!havett) {
5114 double t, nt, t2, nt2, step;
5115
5116 havett++;
5117 step = 1. / NAPSECT;
5118 t = 0;
5119 for(i=1; i<NAPSECT; i++) {
5120 t += step;
5121 nt = 1 - t;
5122 t2 = t*t;
5123 nt2 = nt*nt;
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 */
5128 }
5129 }
5130
5131 for(i=0; i<NWSECT; i++) {
5132 sum[i] = 0.;
5133 count[i] = 0;
5134 }
5135
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];
5145 }
5146 }
5147
5148 for(d=0; d<ndots; d++) {
5149 #ifdef DEBUG_DOTCURVE
5150 printf("dot %d ", d); printdot(dots[d].p); printf(":\n");
5151
5152 /* for debugging */
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));
5156 }
5157 #endif
5158
5159 x = dots[d].p[X];
5160 y = dots[d].p[Y];
5161
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
5165 */
5166
5167 id1 = 0;
5168 dx = x - cvd[0][X];
5169 dy = y - cvd[0][Y];
5170 dist1 = dx*dx + dy*dy;
5171 #ifdef DEBUG_DOTCURVE
5172 printf(" dot 0 "); printdot(cvd[id1]); printf(" dist=%g\n", sqrt(dist1));
5173 #endif
5174 for(i = 1; i<=NAPSECT; i++) {
5175 dx = x - cvd[i][X];
5176 dy = y - cvd[i][Y];
5177 dist3 = dx*dx + dy*dy;
5178 #ifdef DEBUG_DOTCURVE
5179 printf(" dot %d ",i); printdot(cvd[i]); printf(" dist=%g\n", sqrt(dist3));
5180 #endif
5181 if(dist3 < dist1) {
5182 dist1 = dist3;
5183 id1 = i;
5184 } else
5185 break;
5186 }
5187
5188 if(id1 < NAPSECT-1) {
5189 id2 = NAPSECT;
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));
5195 #endif
5196 for(i = NAPSECT-1; i>id1+1; i--) {
5197 dx = x - cvd[i][X];
5198 dy = y - cvd[i][Y];
5199 dist3 = dx*dx + dy*dy;
5200 #ifdef DEBUG_DOTCURVE
5201 printf(" dot %d ",i); printdot(cvd[i]); printf(" dist=%g\n", sqrt(dist3));
5202 #endif
5203 if(dist3 < dist2) {
5204 dist2 = dist3;
5205 id2 = i;
5206 } else
5207 break;
5208 }
5209
5210 /* now find which of the local minimums is smaller */
5211 if(dist2 < dist1) {
5212 id1 = id2;
5213 }
5214 }
5215
5216 /* the nearest segment must include the nearest dot */
5217 if(id1==0) {
5218 dots[d].seg = 0;
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);
5223 } else {
5224 dist1 = fdotsegdist2(&cvd[id1], dots[d].p);
5225 dist2 = fdotsegdist2(&cvd[id1-1], dots[d].p);
5226 if(dist2 < dist1) {
5227 dots[d].seg = id1-1;
5228 dots[d].dist2 = dist2;
5229 } else {
5230 dots[d].seg = id1;
5231 dots[d].dist2 = dist1;
5232 }
5233 }
5234
5235 i = dots[d].seg % NWSECT;
5236 sum[i] += dots[d].dist2;
5237 if(dots[d].dist2 > max)
5238 max = dots[d].dist2;
5239 count[i]++;
5240 #ifdef DEBUG_DOTCURVE
5241 printf(" best seg %d sect %d dist=%g\n", dots[d].seg, i, sqrt(dots[d].dist2));
5242 #endif
5243 }
5244
5245 /* calculate the weighted average */
5246 id1=0;
5247 dist1=0.;
5248 for(i=0; i<NWSECT; i++) {
5249 if(count[i]==0)
5250 continue;
5251 id1++;
5252 dist1 += sum[i]/count[i];
5253 }
5254 if(maxp)
5255 *maxp = max;
5256 if(id1==0) /* no dots, strange */
5257 return 0.;
5258 else
5259 return dist1/id1; /* to get the average distance apply sqrt() */
5260 }
5261
5262 /*
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).
5266 */
5267
5268 void
5269 fapproxcurve(
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 */
5273 int ndots
5274 )
5275 {
5276 /* b and c are the middle control points */
5277 #define B 0
5278 #define C 1
5279 /* maximal number of sections on each axis - used for the first step */
5280 #define MAXSECT 2
5281 /* number of sections used for the other steps */
5282 #define NORMSECT 2
5283 /* when the steps become less than this many points, it's time to stop */
5284 #define STEPEPS 1.
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;
5291 char bc[]="BC";
5292 char xy[]="XY";
5293
5294 #ifdef DEBUG_APPROXCV
5295 fprintf(stderr, "Curve points:");
5296 for(i=0; i<4; i++) {
5297 fprintf(stderr, " ");
5298 printdot(cv[i]);
5299 }
5300 fprintf(stderr, "\nDots:");
5301 for(i=0; i<ndots; i++) {
5302 fprintf(stderr, " ");
5303 printdot(dots[i].p);
5304 }
5305 fprintf(stderr, "\n");
5306 #endif
5307
5308 /* load the endpoints and calculate differences */
5309 for(i=0; i<2; i++) {
5310 /* i is X, Y */
5311 middf[B][i] = cv[1][i]-cv[0][i];
5312 middf[C][i] = cv[2][i]-cv[3][i];
5313
5314 /* i is B, C */
5315 from[i] = 0.;
5316 to[i] = 1.;
5317 ncoef[i] = MAXSECT;
5318 }
5319
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]);
5325 #endif
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]);
5331 #endif
5332 }
5333 #ifdef DEBUG_APPROXCV
5334 fprintf(stderr, "\n");
5335 #endif
5336 }
5337 bestres = FBIGVAL;
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];
5344 }
5345 res[i][j] = thisres = fdotcurvdist2(cv, dots, ndots, NULL);
5346 if(thisres < bestres) {
5347 goodres = bestres;
5348 good[B] = best[B];
5349 good[C] = best[C];
5350 bestres = thisres;
5351 best[B] = i;
5352 best[C] = j;
5353 } else if(thisres < goodres) {
5354 goodres = thisres;
5355 good[B] = i;
5356 good[C] = j;
5357 }
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)":"");
5361 #endif
5362 }
5363 }
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));
5369 #endif
5370
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]];
5376 }
5377 #ifdef DEBUG_APPROXCV
5378 fprintf(stderr, "quick approximated middle points "); printdot(cv[1]);
5379 fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n");
5380 #endif
5381 return;
5382 }
5383 keepsym = 0;
5384 if(best[B] != best[C] && best[B]-best[C] == good[C]-good[B]) {
5385 keepsym = 1;
5386 #ifdef DEBUG_APPROXCV
5387 fprintf(stderr, "keeping symmetry!\n");
5388 #endif
5389 }
5390 for(i=0; i<2; i++) { /*B,C*/
5391 if(ncoef[i]==1)
5392 continue;
5393 if(keepsym) {
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]];
5398 } else {
5399 from[i] = coef[i][good[i]];
5400 to[i] = coef[i][best[i]];
5401 }
5402 } else {
5403 df = (to[i]-from[i]) / ncoef[i];
5404 from[i] += df*best[i];
5405 to[i] = from[i] + df;
5406 }
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.;
5410 ncoef[i] = 1;
5411 } else
5412 ncoef[i] = NORMSECT;
5413 }
5414
5415 }
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];
5420 }
5421 #ifdef DEBUG_APPROXCV
5422 fprintf(stderr, "approximated middle points "); printdot(cv[1]);
5423 fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n");
5424 #endif
5425 #undef B
5426 #undef C
5427 #undef MAXSECT
5428 #undef NORMSECT
5429 #undef STEPEPS
5430 }
5431
5432 /*
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.
5436 */
5437
5438 static double
5439 fjointsin2(
5440 GENTRY *ge1,
5441 GENTRY *ge2
5442 )
5443 {
5444 double d[3][2 /*X,Y*/];
5445 double scale1, scale2, len1, len2;
5446 int axis;
5447
5448 if(ge1->rtg < 0) {
5449 d[1][X] = ge1->fx3 - ge1->prev->fx3;
5450 d[1][Y] = ge1->fy3 - ge1->prev->fy3;
5451 } else {
5452 d[1][X] = ge1->fx3 - ge1->fpoints[X][ge1->rtg];
5453 d[1][Y] = ge1->fy3 - ge1->fpoints[Y][ge1->rtg];
5454 }
5455 d[2][X] = ge2->fpoints[X][ge2->ftg] - ge2->prev->fx3;
5456 d[2][Y] = ge2->fpoints[Y][ge2->ftg] - ge2->prev->fy3;
5457
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
5463 */
5464 scale1 = 2./len1;
5465 scale2 = 1./len2;
5466
5467 for(axis=0; axis <2; axis++) {
5468 d[0][axis] = -( d[1][axis] *= scale1 );
5469 d[2][axis] *= scale2;
5470 }
5471 return fdotsegdist2(d, d[2]);
5472 }
5473
5474 #if 0
5475 /* find the area covered by the curve
5476 * (limited by the projections to the X axis)
5477 */
5478
5479 static double
5480 fcvarea(
5481 GENTRY *ge
5482 )
5483 {
5484 double Ly, My, Ny, Py, Qx, Rx, Sx;
5485 double area;
5486
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);
5491 Py = ge->prev->fy3;
5492
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);
5497
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;
5502
5503 return area;
5504 }
5505 #endif
5506
5507 /* find the value of point on the curve at the given parameter t,
5508 * along the given axis (0 - X, 1 - Y).
5509 */
5510
5511 static double
5512 fcvval(
5513 GENTRY *ge,
5514 int axis,
5515 double t
5516 )
5517 {
5518 double t2, mt, mt2;
5519
5520 /* val = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 */
5521 t2 = t*t;
5522 mt = 1-t;
5523 mt2 = mt*mt;
5524
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;
5528 }
5529
5530 /*
5531 * Find ndots equally spaced dots on a curve or line and fill
5532 * their coordinates into the dots array
5533 */
5534
5535 static void
5536 fsampledots(
5537 GENTRY *ge,
5538 double dots[][2], /* the dots to fill */
5539 int ndots
5540 )
5541 {
5542 int i, axis;
5543 double t, nf, dx, d[2];
5544
5545 nf = ndots+1;
5546 if(ge->type == GE_CURVE) {
5547 for(i=0; i<ndots; i++) {
5548 t = (i+1)/nf;
5549 for(axis=0; axis<2; axis++)
5550 dots[i][axis] = fcvval(ge, axis, t);
5551 }
5552 } else { /* line */
5553 d[0] = ge->fx3 - ge->prev->fx3;
5554 d[1] = ge->fy3 - ge->prev->fy3;
5555 for(i=0; i<ndots; i++) {
5556 t = (i+1)/nf;
5557 for(axis=0; axis<2; axis++)
5558 dots[i][axis] = ge->prev->fpoints[axis][2]
5559 + t*d[axis];
5560 }
5561 }
5562 }
5563
5564 /*
5565 * Allocate a structure gex_con
5566 */
5567
5568 static void
5569 alloc_gex_con(
5570 GENTRY *ge
5571 )
5572 {
5573 ge->ext = (void*)calloc(1, sizeof(GEX_CON));
5574 if(ge->ext == 0) {
5575 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
5576 exit(255);
5577 }
5578 }
5579
5580 /*
5581 * Normalize a gentry for fforceconcise() : find the points that
5582 * can be used to calculate the tangents.
5583 */
5584
5585 static void
5586 fnormalizege(
5587 GENTRY *ge
5588 )
5589 {
5590 int midsame, frontsame, rearsame;
5591
5592 if(ge->type == GE_LINE) {
5593 ge->ftg = 2;
5594 ge->rtg = -1;
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);
5599
5600 if(midsame && (frontsame || rearsame) ) {
5601 /* essentially a line */
5602 ge->ftg = 2;
5603 ge->rtg = -1;
5604 } else {
5605 if(frontsame) {
5606 ge->ftg = 1;
5607 } else {
5608 ge->ftg = 0;
5609 }
5610 if(rearsame) {
5611 ge->rtg = 0;
5612 } else {
5613 ge->rtg = 1;
5614 }
5615 }
5616 }
5617 }
5618
5619 /* various definition for the processing of outlines */
5620
5621 /* maximal average quadratic distance from the original curve
5622 * (in dots) to consider the joined curve good
5623 */
5624 #define CVEPS 1.5
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.)
5632
5633 /*
5634 * Normalize and analyse a gentry for fforceconcise() and fill out the gex_con
5635 * structure
5636 */
5637
5638 static void
5639 fanalyzege(
5640 GENTRY *ge
5641 )
5642 {
5643 int i, ix, iy;
5644 double avsd2, dots[3][2 /*X,Y*/];
5645 GEX_CON *gex;
5646
5647 gex = X_CON(ge);
5648 memset(gex, 0, sizeof *gex);
5649
5650 gex->len2 = 0;
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;
5654 }
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);
5662 }
5663 avsd2 = fdotsegdist2(dots, dots[2]);
5664 if(avsd2 <= CVEPS2) {
5665 gex->flags |= GEXF_FLAT;
5666 }
5667 } else {
5668 ge->dir = CVDIR_FEQUAL|CVDIR_REQUAL;
5669 gex->flags |= GEXF_FLAT;
5670 }
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;
5678 }
5679 ix = gex->isd[X] = fsign(gex->d[X]);
5680 iy = gex->isd[Y] = fsign(gex->d[Y]);
5681 if(ix <= 0) {
5682 if(iy <= 0)
5683 gex->flags |= GEXF_QDL;
5684 if(iy >= 0)
5685 gex->flags |= GEXF_QUL;
5686 if(gex->flags & GEXF_HOR)
5687 gex->flags |= GEXF_IDQ_L;
5688 }
5689 if(ix >= 0) {
5690 if(iy <= 0)
5691 gex->flags |= GEXF_QDR;
5692 if(iy >= 0)
5693 gex->flags |= GEXF_QUR;
5694 if(gex->flags & GEXF_HOR)
5695 gex->flags |= GEXF_IDQ_R;
5696 }
5697 if(gex->flags & GEXF_VERT) {
5698 if(iy <= 0) {
5699 gex->flags |= GEXF_IDQ_U;
5700 } else { /* supposedly there is no 0-sized entry */
5701 gex->flags |= GEXF_IDQ_D;
5702 }
5703 }
5704 }
5705
5706 /*
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.
5710 */
5711
5712 static void
5713 fanalyzejoint(
5714 GENTRY *ge
5715 )
5716 {
5717 GENTRY *nge = ge->frwd;
5718 GENTRY tge;
5719 GEX_CON *gex, *ngex;
5720 double avsd2, dots[3][2 /*X,Y*/];
5721 int i;
5722
5723 gex = X_CON(ge); ngex = X_CON(nge);
5724
5725 /* look if they can be joined honestly */
5726
5727 /* if any is flat, they should join smoothly */
5728 if( (gex->flags & GEXF_FLAT || ngex->flags & GEXF_FLAT)
5729 && gex->sin2 > SMOOTHSIN2)
5730 goto try_flatboth;
5731
5732 if(ge->type == GE_LINE) {
5733 if(nge->type == GE_LINE) {
5734 if(gex->len2 > SMALL_LINE2 || ngex->len2 > SMALL_LINE2)
5735 goto try_flatboth;
5736 } else {
5737 if(gex->len2*TIMES_LINE2 > ngex->len2)
5738 goto try_flatboth;
5739 }
5740 } else if(nge->type == GE_LINE) {
5741 if(ngex->len2*TIMES_LINE2 > gex->len2)
5742 goto try_flatboth;
5743 }
5744
5745 /* if curve changes direction */
5746 if( gex->isd[X]*ngex->isd[X]<0 || gex->isd[Y]*ngex->isd[Y]<0)
5747 goto try_idealone;
5748
5749 /* if would create a zigzag */
5750 if( ((ge->dir&CVDIR_FRONT)-CVDIR_FEQUAL) * ((nge->dir&CVDIR_REAR)-CVDIR_REQUAL) < 0 )
5751 goto try_flatone;
5752
5753 if( fcrossraysge(ge, nge, NULL, NULL, NULL) )
5754 gex->flags |= GEXF_JGOOD;
5755
5756 try_flatone:
5757 /* look if they can be joined by flatting out one of the entries */
5758
5759 /* at this point we know that the general direction of the
5760 * gentries is OK
5761 */
5762
5763 if( gex->flags & GEXF_FLAT ) {
5764 tge = *ge;
5765 tge.fx1 = tge.fx3;
5766 tge.fy1 = tge.fy3;
5767 fnormalizege(&tge);
5768 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) )
5769 gex->flags |= GEXF_JFLAT|GEXF_JFLAT1;
5770 }
5771 if( ngex->flags & GEXF_FLAT ) {
5772 tge = *nge;
5773 tge.fx2 = ge->fx3;
5774 tge.fy2 = ge->fy3;
5775 fnormalizege(&tge);
5776 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) )
5777 gex->flags |= GEXF_JFLAT|GEXF_JFLAT2;
5778 }
5779
5780 try_idealone:
5781 /* look if one of the entries can be brought to an idealized
5782 * horizontal or vertical position and then joined
5783 */
5784 if( gex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) {
5785 tge = *ge;
5786 tge.fx1 = tge.fx3;
5787 tge.fy1 = ge->prev->fy3; /* force horizontal */
5788 fnormalizege(&tge);
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 ) {
5792 tge = *ge;
5793 tge.fx1 = ge->prev->fx3; /* force vertical */
5794 tge.fy1 = tge.fy3;
5795 fnormalizege(&tge);
5796 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) )
5797 gex->flags |= GEXF_JID|GEXF_JID1;
5798 }
5799 if( ngex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) {
5800 tge = *nge;
5801 tge.fx2 = ge->fx3;
5802 tge.fy2 = nge->fy3; /* force horizontal */
5803 fnormalizege(&tge);
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 ) {
5807 tge = *nge;
5808 tge.fx2 = nge->fx3; /* force vertical */
5809 tge.fy2 = ge->fy3;
5810 fnormalizege(&tge);
5811 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) )
5812 gex->flags |= GEXF_JID|GEXF_JID2;
5813 }
5814
5815 try_flatboth:
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];
5822 }
5823 if( fdotsegdist2(dots, dots[2]) <= CVEPS2)
5824 gex->flags |= GEXF_JLINE;
5825 }
5826 }
5827
5828 /*
5829 * Force conciseness of one contour in the glyph,
5830 * the contour is indicated by one entry from it.
5831 */
5832
5833 static void
5834 fconcisecontour(
5835 GLYPH *g,
5836 GENTRY *startge
5837 )
5838 {
5839 /* initial maximal number of dots to be used as reference */
5840 #define MAXDOTS ((NREFDOTS+1)*12)
5841
5842 GENTRY *ge, *pge, *nge, *ige;
5843 GEX_CON *gex, *pgex, *ngex, *nngex;
5844 GENTRY tpge, tnge;
5845 int quad, qq, i, j, ndots, maxdots;
5846 int found[2];
5847 int joinmask, pflag, nflag;
5848 struct dot_dist *dots;
5849 double avsd2, maxd2, eps2;
5850 double apcv[4][2];
5851
5852 if(startge == 0) {
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);
5857 return;
5858 }
5859
5860 if(startge->type != GE_CURVE && startge->type != GE_LINE)
5861 return; /* probably a degenerate contour */
5862
5863 if(ISDBG(FCONCISE))
5864 fprintf(stderr, "processing contour 0x%p of glyph %s\n", startge, g->name);
5865
5866 maxdots = MAXDOTS;
5867 dots = (struct dot_dist *)malloc(sizeof(*dots)*maxdots);
5868 if(dots == NULL) {
5869 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
5870 exit(255);
5871 }
5872
5873 ge = startge;
5874 joinmask = GEXF_JGOOD;
5875 while(1) {
5876 restart:
5877 gex = X_CON(ge);
5878 if((gex->flags & GEXF_JMASK) > ((joinmask<<1)-1)) {
5879 if(ISDBG(FCONCISE))
5880 fprintf(stderr, "found higher flag (%x>%x) at 0x%p\n",
5881 gex->flags & GEXF_JMASK, ((joinmask<<1)-1), ge);
5882 joinmask <<= 1;
5883 startge = ge; /* have to redo the pass */
5884 continue;
5885 }
5886 if(( gex->flags & joinmask )==0)
5887 goto next;
5888
5889 /* if we happen to be in the middle of a string of
5890 * joinable entries, find its beginning
5891 */
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;
5898
5899 pge = ge;
5900 pgex = X_CON(pge->bkwd);
5901
5902 if(ISDBG(FCONCISE))
5903 fprintf(stderr, "ge %p prev -> 0x%p ", ge, pge);
5904
5905 while(pgex->flags & GEXF_JCVMASK) {
5906 if( !(pgex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID2)) )
5907 qq = GEXF_QFROM_IDEAL(pgex->flags);
5908 else
5909 qq = pgex->flags & GEXF_QMASK;
5910
5911 if(ISDBG(FCONCISE))
5912 fprintf(stderr, "(%x?%x)", quad, qq);
5913
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 */
5918 if(pge == ge) {
5919 if(ISDBG(FCONCISE))
5920 fprintf(stderr, "\nprev is a better match at %p\n", pge);
5921 startge = ge;
5922 goto next;
5923 } else
5924 pge = pge->frwd;
5925 }
5926 break;
5927 }
5928
5929 quad &= qq;
5930 pge = pge->bkwd;
5931 pgex = X_CON(pge->bkwd);
5932 if(ISDBG(FCONCISE))
5933 fprintf(stderr, "0x%p ", pge);
5934 }
5935
5936 /* collect as many entries for joining as possible */
5937 nge = ge->frwd;
5938 ngex = X_CON(nge);
5939 nngex = X_CON(nge->frwd);
5940
5941 if(ISDBG(FCONCISE))
5942 fprintf(stderr, ": 0x%x\nnext -> 0x%p ", pge, nge);
5943
5944 while(ngex->flags & GEXF_JCVMASK) {
5945 if( !(ngex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID1)) )
5946 qq = GEXF_QFROM_IDEAL(nngex->flags);
5947 else
5948 qq = nngex->flags & GEXF_QMASK;
5949
5950 if(ISDBG(FCONCISE))
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) {
5957 if(ISDBG(FCONCISE))
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);
5960 goto next;
5961 } else
5962 nge = nge->bkwd;
5963 }
5964 break;
5965 }
5966
5967 quad &= qq;
5968 nge = nge->frwd;
5969 ngex = nngex;
5970 nngex = X_CON(nge->frwd);
5971 if(ISDBG(FCONCISE))
5972 fprintf(stderr, "0x%p ", nge);
5973 }
5974
5975 if(ISDBG(FCONCISE))
5976 fprintf(stderr, ": 0x%x\n", nge);
5977
5978 /* XXX add splitting of last entries if neccessary */
5979
5980 /* make sure that all the reference dots are valid */
5981 for(ige = pge; ige != nge->frwd; ige = ige->frwd) {
5982 nngex = X_CON(ige);
5983 if( !(nngex->flags & GEXF_VDOTS) ) {
5984 fsampledots(ige, nngex->dots, NREFDOTS);
5985 nngex->flags |= GEXF_VDOTS;
5986 }
5987 }
5988
5989 /* do the actual joining */
5990 while(1) {
5991 pgex = X_CON(pge);
5992 ngex = X_CON(nge->bkwd);
5993 /* now the segments to be joined are pge...nge */
5994
5995 ndots = 0;
5996 for(ige = pge; ige != nge->frwd; ige = ige->frwd) {
5997 if(maxdots < ndots+(NREFDOTS+1)) {
5998 maxdots += MAXDOTS;
5999 dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots);
6000 if(dots == NULL) {
6001 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
6002 exit(255);
6003 }
6004 }
6005 nngex = X_CON(ige);
6006 for(i=0; i<NREFDOTS; i++) {
6007 for(j=0; j<2; j++)
6008 dots[ndots].p[j] = nngex->dots[i][j];
6009 ndots++;
6010 }
6011 for(j=0; j<2; j++)
6012 dots[ndots].p[j] = ige->fpoints[j][2];
6013 ndots++;
6014 }
6015 ndots--; /* the last point is not interesting */
6016
6017 tpge = *pge;
6018 pflag = pgex->flags;
6019 if(pflag & (GEXF_JGOOD|GEXF_JFLAT2|GEXF_JID2)) {
6020 /* nothing */
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;
6027 else
6028 tpge.fx1 = tpge.bkwd->fx3;
6029 }
6030
6031 tnge = *nge;
6032 nflag = ngex->flags;
6033 if(nflag & (GEXF_JGOOD|GEXF_JFLAT1|GEXF_JID)
6034 && !(nflag & GEXF_JID2)) {
6035 /* nothing */
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;
6042 else
6043 tnge.fx2 = tnge.fx3;
6044 }
6045
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;
6054
6055 /* calculate the precision depending on the smaller dimension of the curve */
6056 maxd2 = apcv[3][X]-apcv[0][X];
6057 maxd2 *= maxd2;
6058 eps2 = apcv[3][Y]-apcv[0][Y];
6059 eps2 *= eps2;
6060 if(maxd2 < eps2)
6061 eps2 = maxd2;
6062 eps2 *= (CVEPS2*4.) / (400.*400.);
6063 if(eps2 < CVEPS2)
6064 eps2 = CVEPS2;
6065 else if(eps2 > CVEPS2*4.)
6066 eps2 = CVEPS2*4.;
6067
6068 fapproxcurve(apcv, dots, ndots);
6069
6070 avsd2 = fdotcurvdist2(apcv, dots, ndots, &maxd2);
6071 if(ISDBG(FCONCISE))
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;
6076
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]);
6081 }
6082 fprintf(stderr, " from\n");
6083 dumppaths(g, pge, nge);
6084 }
6085 for(i=0; i<3; i++) {
6086 pge->fxn[i] = apcv[i+1][X];
6087 pge->fyn[i] = apcv[i+1][Y];
6088 }
6089 pge->type = GE_CURVE;
6090 ge = pge;
6091 for(ige = pge->frwd; ; ige = pge->frwd) {
6092 if(ige == pge) {
6093 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n",
6094 __FILE__, __LINE__);
6095 free(dots);
6096 return;
6097 }
6098 if(startge == ige)
6099 startge = pge;
6100 free(ige->ext);
6101 freethisge(ige);
6102 if(ige == nge)
6103 break;
6104 }
6105 fnormalizege(ge);
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]);
6110 }
6111 fprintf(stderr, "\n");
6112 }
6113 fanalyzege(ge);
6114 fanalyzejoint(ge);
6115 fanalyzege(ge->bkwd);
6116 fanalyzejoint(ge->bkwd);
6117
6118 /* the results of this join will have to be reconsidered */
6119 startge = ge = ge->frwd;
6120 goto restart;
6121 } else {
6122 gbadcv++; gbadcvdots += ndots;
6123 }
6124 }
6125
6126 /* if we're down to 2 entries then the join has failed */
6127 if(pge->frwd == nge) {
6128 pgex->flags &= ~joinmask;
6129 if(ISDBG(FCONCISE))
6130 fprintf(stderr, "no match\n");
6131 goto next;
6132 }
6133
6134 /* reduce the number of entries by dropping one at some end,
6135 * should never drop the original ge from the range
6136 */
6137
6138 if(nge->bkwd == ge
6139 || pge != ge && (pgex->flags & GEXF_JCVMASK) <= (ngex->flags & GEXF_JCVMASK) ) {
6140 pge = pge->frwd;
6141 } else {
6142 nge = nge->bkwd;
6143 }
6144 if(ISDBG(FCONCISE))
6145 fprintf(stderr, "next try: %p to %p\n", pge, nge);
6146 }
6147
6148 next:
6149 ge = ge->frwd;
6150 if(ge == startge) {
6151 joinmask = (joinmask >> 1) & GEXF_JCVMASK;
6152 if(joinmask == 0)
6153 break;
6154 }
6155 }
6156
6157 /* join flat segments into lines */
6158 /* here ge==startge */
6159 while(1) {
6160 gex = X_CON(ge);
6161 if( !(gex->flags & GEXF_JLINE) )
6162 goto next2;
6163
6164 ndots = 0;
6165 dots[ndots].p[X] = ge->fx3;
6166 dots[ndots].p[Y] = ge->fy3;
6167 ndots++;
6168
6169 pge = ge->bkwd;
6170 nge = ge->frwd;
6171
6172 if(ISDBG(FCONCISE))
6173 fprintf(stderr, "joining LINE from %p-%p\n", ge, nge);
6174
6175 while(pge!=nge) {
6176 pgex = X_CON(pge);
6177 ngex = X_CON(nge);
6178 if(ISDBG(FCONCISE))
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) ) {
6182 if(ISDBG(FCONCISE))
6183 fprintf(stderr, "(end p=%p n=%p) ", pge, nge);
6184 break;
6185 }
6186
6187 if(maxdots < ndots+2) {
6188 maxdots += MAXDOTS;
6189 dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots);
6190 if(dots == NULL) {
6191 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
6192 exit(255);
6193 }
6194 }
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];
6200 }
6201 ndots++;
6202 for(i=0; i<ndots; i++) {
6203 avsd2 = fdotsegdist2(apcv, dots[i].p);
6204 if(avsd2 > CVEPS2)
6205 break;
6206 }
6207 if(i<ndots) { /* failed to join */
6208 if(ISDBG(FCONCISE))
6209 fprintf(stderr, "failed to join prev %p ", pge);
6210 ndots--;
6211 pgex->flags &= ~GEXF_JLINE;
6212 } else {
6213 pge = pge->bkwd;
6214 if(pge == nge) {
6215 if(ISDBG(FCONCISE))
6216 fprintf(stderr, "intersected at prev %p ", pge);
6217 break; /* oops, tried to self-intersect */
6218 }
6219 }
6220 } else if(ISDBG(FCONCISE))
6221 fprintf(stderr, "(p=%p) ", pge);
6222
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];
6228 }
6229 ndots++;
6230 for(i=0; i<ndots; i++) {
6231 avsd2 = fdotsegdist2(apcv, dots[i].p);
6232 if(avsd2 > CVEPS2)
6233 break;
6234 }
6235 if(i<ndots) { /* failed to join */
6236 if(ISDBG(FCONCISE))
6237 fprintf(stderr, "failed to join next %p ", nge->frwd);
6238 ndots--;
6239 ngex->flags &= ~GEXF_JLINE;
6240 } else {
6241 nge = nge->frwd;
6242 }
6243 } else if(ISDBG(FCONCISE))
6244 fprintf(stderr, "(n=%p) ", nge);
6245 }
6246
6247 pge = pge->frwd; /* now the limits are pge...nge inclusive */
6248 if(pge == nge) /* a deeply perversive contour */
6249 break;
6250
6251 if(ISDBG(FCONCISE)) {
6252 fprintf(stderr, "\nin %s joined LINE %p-%p from\n", g->name, pge, nge);
6253 dumppaths(g, pge, nge);
6254 }
6255 pge->type = GE_LINE;
6256 for(i=0; i<2; i++) {
6257 pge->fpoints[i][2] = nge->fpoints[i][2];
6258 }
6259 fnormalizege(pge);
6260 X_CON_F(pge) &= ~GEXF_JLINE;
6261
6262 ge = pge;
6263 for(ige = pge->frwd; ; ige = pge->frwd) {
6264 if(ige == pge) {
6265 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n",
6266 __FILE__, __LINE__);
6267 free(dots);
6268 return;
6269 }
6270 if(startge == ige)
6271 startge = pge;
6272 free(ige->ext);
6273 freethisge(ige);
6274 if(ige == nge)
6275 break;
6276 }
6277 next2:
6278 ge = ge->frwd;
6279 if(ge == startge)
6280 break;
6281 }
6282
6283 free(dots);
6284 }
6285
6286 /* force conciseness: substitute 2 or more curves going in the
6287 ** same quadrant with one curve
6288 ** in floating point
6289 */
6290
6291 void
6292 fforceconcise(
6293 GLYPH * g
6294 )
6295 {
6296
6297 GENTRY *ge, *nge, *endge, *xge;
6298
6299 assertisfloat(g, "enforcing conciseness");
6300
6301 fdelsmall(g, 0.05);
6302 assertpath(g->entries, __FILE__, __LINE__, g->name);
6303
6304 if(ISDBG(FCONCISE))
6305 dumppaths(g, NULL, NULL);
6306
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)
6310 fnormalizege(ge);
6311
6312 for (ge = g->entries; ge != 0; ge = ge->next)
6313 if (ge->type == GE_CURVE || ge->type == GE_LINE) {
6314 alloc_gex_con(ge);
6315 fanalyzege(ge);
6316 }
6317
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)
6321 fanalyzejoint(ge);
6322
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);
6327
6328 for (ge = g->entries; ge != 0; ge = ge->next)
6329 if (ge->type == GE_CURVE || ge->type == GE_LINE)
6330 free(ge->ext);
6331 }
6332
6333 void
6334 print_glyph(
6335 int glyphno
6336 )
6337 {
6338 GLYPH *g;
6339 GENTRY *ge;
6340 int x = 0, y = 0;
6341 int i;
6342 int grp, lastgrp= -1;
6343
6344 if(ISDBG(FCONCISE) && glyphno == 0) {
6345 fprintf(stderr, "Guessed curves: bad %d/%d good %d/%d\n",
6346 gbadcv, gbadcvdots, ggoodcv, ggoodcvdots);
6347 }
6348
6349 g = &glyph_list[glyphno];
6350
6351 fprintf(pfa_file, "/%s { \n", g->name);
6352
6353 /* consider widths >MAXLEGALWIDTH as bugs */
6354 if( g->scaledwidth <= MAXLEGALWIDTH ) {
6355 fprintf(pfa_file, "0 %d hsbw\n", g->scaledwidth);
6356 } else {
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);
6360 }
6361
6362 #if 0
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");
6368
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"));
6373 #endif
6374
6375 if (g->hstems)
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",
6379 g->hstems[i].value,
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
6385 );
6386 i += 4;
6387 } else {
6388 fprintf(pfa_file, "%d %d hstem\n", g->hstems[i].value,
6389 g->hstems[i + 1].value - g->hstems[i].value);
6390 }
6391 }
6392
6393 if (g->vstems)
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",
6397 g->vstems[i].value,
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
6403 );
6404 i += 4;
6405 } else {
6406 fprintf(pfa_file, "%d %d vstem\n", g->vstems[i].value,
6407 g->vstems[i + 1].value - g->vstems[i].value);
6408 }
6409 }
6410
6411 for (ge = g->entries; ge != 0; ge = ge->next) {
6412 if(g->nsg>0) {
6413 grp=ge->stemid;
6414 if(grp >= 0 && grp != lastgrp) {
6415 fprintf(pfa_file, "%d 4 callsubr\n", grp+g->firstsubr);
6416 lastgrp=grp;
6417 }
6418 }
6419
6420 switch (ge->type) {
6421 case GE_MOVE:
6422 if (absolute)
6423 fprintf(pfa_file, "%d %d amoveto\n", ge->ix3, ge->iy3);
6424 else
6425 rmoveto(ge->ix3 - x, ge->iy3 - y);
6426 if (0)
6427 fprintf(stderr, "Glyph %s: print moveto(%d, %d)\n",
6428 g->name, ge->ix3, ge->iy3);
6429 x = ge->ix3;
6430 y = ge->iy3;
6431 break;
6432 case GE_LINE:
6433 if (absolute)
6434 fprintf(pfa_file, "%d %d alineto\n", ge->ix3, ge->iy3);
6435 else
6436 rlineto(ge->ix3 - x, ge->iy3 - y);
6437 x = ge->ix3;
6438 y = ge->iy3;
6439 break;
6440 case GE_CURVE:
6441 if (absolute)
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);
6444 else
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);
6448 x = ge->ix3;
6449 y = ge->iy3;
6450 break;
6451 case GE_PATH:
6452 closepath();
6453 break;
6454 default:
6455 WARNING_1 fprintf(stderr, "**** Glyph %s: unknown entry type '%c'\n",
6456 g->name, ge->type);
6457 break;
6458 }
6459 }
6460
6461 fprintf(pfa_file, "endchar } ND\n");
6462 }
6463
6464 /* print the subroutines for this glyph, returns the number of them */
6465 int
6466 print_glyph_subs(
6467 int glyphno,
6468 int startid /* start numbering subroutines from this id */
6469 )
6470 {
6471 GLYPH *g;
6472 int i, grp;
6473
6474 g = &glyph_list[glyphno];
6475
6476 if(!hints || !subhints || g->nsg<1)
6477 return 0;
6478
6479 g->firstsubr=startid;
6480
6481 #if 0
6482 fprintf(pfa_file, "%% %s %d\n", g->name, g->nsg);
6483 #endif
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");
6491 }
6492
6493 return g->nsg;
6494 }
6495
6496 void
6497 print_glyph_metrics(
6498 int code,
6499 int glyphno
6500 )
6501 {
6502 GLYPH *g;
6503
6504 g = &glyph_list[glyphno];
6505
6506 if(transform)
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));
6510 else
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);
6514 }
6515
6516 /*
6517 SB:
6518 An important note about the BlueValues.
6519
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.
6524
6525 The formula for it that is given in the manual is:
6526
6527 BlueScale=point_size/240, for a 300dpi device
6528
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:
6534
6535 BlueScale=pixel_size/1000
6536
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:
6540
6541 max_width < 1000/pixel_size
6542
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.
6549
6550 */
6551
6552 #define MAXBLUEWIDTH (24)
6553
6554 /*
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)
6560 */
6561
6562 #define MAXHYST (2000) /* size of the hystogram */
6563 #define HYSTBASE 500
6564
6565 static int
6566 besthyst(
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 */
6573 )
6574 {
6575 unsigned char hused[MAXHYST / 8 + 1];
6576 int i, max, j, w, last = 0;
6577 int nf = 0;
6578
6579 width--;
6580
6581 memset(hused, 0 , sizeof hused);
6582
6583 max = 1;
6584 for (i = 0; i < nbest && max != 0; i++) {
6585 best[i] = 0;
6586 max = 0;
6587 for (j = 1; j < MAXHYST - 1; j++) {
6588 w = hyst[j];
6589
6590 if (w > max && (hused[j>>3] & (1 << (j & 0x07))) == 0) {
6591 best[i] = j;
6592 max = w;
6593 }
6594 }
6595 if (max != 0) {
6596 if (max < last/2) {
6597 /* do not pick the too low values */
6598 break;
6599 }
6600 for (j = best[i] - width; j <= best[i] + width; j++) {
6601 if (j >= 0 && j < MAXHYST)
6602 hused[j >> 3] |= (1 << (j & 0x07));
6603 }
6604 last = max;
6605 best[i] -= base;
6606 nf = i + 1;
6607 }
6608 }
6609
6610 if (bestindp)
6611 *bestindp = best[0];
6612
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]) {
6617 w = best[i];
6618 best[i] = best[j];
6619 best[j] = w;
6620 }
6621 }
6622
6623 return nf;
6624 }
6625
6626 /*
6627 * Find the next best Blue zone in the hystogram.
6628 * Return the weight of the found zone.
6629 */
6630
6631 static int
6632 bestblue(
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 */
6637 )
6638 {
6639 int i, j, w, max, ind, first, last;
6640
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 */
6644
6645 max = -1;
6646 first = last = -10;
6647 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
6648 w = zhyst[i];
6649 if (w > max) {
6650 first = last = i;
6651 max = w;
6652 } else if (w == max) {
6653 if (last == i - 1)
6654 last = i;
6655 }
6656 }
6657 ind = (first + last) / 2;
6658
6659 if (max == 0) /* no zones left */
6660 return 0;
6661
6662 /* now we reuse `first' and `last' as inclusive borders of the zone */
6663 first = ind;
6664 last = ind + (MAXBLUEWIDTH - 1);
6665
6666 /* our maximal width is far too big, so we try to make it narrower */
6667 w = max;
6668 j = (w & 1); /* a pseudo-random bit */
6669 while (1) {
6670 while (physt[first] == 0)
6671 first++;
6672 while (physt[last] == 0)
6673 last--;
6674 if (last - first < (MAXBLUEWIDTH * 2 / 3) || (max - w) * 10 > max)
6675 break;
6676
6677 if (physt[first] < physt[last]
6678 || physt[first] == physt[last] && j) {
6679 if (physt[first] * 20 > w) /* if weight is >5%,
6680 * stop */
6681 break;
6682 w -= physt[first];
6683 first++;
6684 j = 0;
6685 } else {
6686 if (physt[last] * 20 > w) /* if weight is >5%,
6687 * stop */
6688 break;
6689 w -= physt[last];
6690 last--;
6691 j = 1;
6692 }
6693 }
6694
6695 /* save our zone */
6696 bluetab[0] = first - HYSTBASE;
6697 bluetab[1] = last - HYSTBASE;
6698
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) {
6703 zhyst[i] = 0;
6704 ozhyst[i] = 0;
6705 }
6706 return w;
6707 }
6708
6709 /*
6710 * Try to find the Blue Values, bounding box and italic angle
6711 */
6712
6713 void
6714 findblues(void)
6715 {
6716 /* hystograms for upper and lower zones */
6717 short hystl[MAXHYST];
6718 short hystu[MAXHYST];
6719 short zuhyst[MAXHYST];
6720 short zlhyst[MAXHYST];
6721 int nchars;
6722 int i, j, k, w, max;
6723 GENTRY *ge;
6724 GLYPH *g;
6725 double ang;
6726
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 */
6730
6731 /* re-use hystl for the hystogram of italic angle */
6732
6733 bbox[0] = bbox[1] = 5000;
6734 bbox[2] = bbox[3] = -5000;
6735
6736 for (i = 0; i < MAXHYST; i++)
6737 hystl[i] = 0;
6738
6739 nchars = 0;
6740
6741 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6742 if (g->flags & GF_USED) {
6743 nchars++;
6744
6745 g->rymin = 5000;
6746 g->rymax = -5000;
6747 for (ge = g->entries; ge != 0; ge = ge->next) {
6748 if (ge->type == GE_LINE) {
6749
6750 j = ge->iy3 - ge->prev->iy3;
6751 k = ge->ix3 - ge->prev->ix3;
6752 if (j > 0)
6753 ang = atan2(-k, j) * 180.0 / M_PI;
6754 else
6755 ang = atan2(k, -j) * 180.0 / M_PI;
6756
6757 k /= 100;
6758 j /= 100;
6759 if (ang > -45.0 && ang < 45.0) {
6760 /*
6761 * be careful to not overflow
6762 * the counter
6763 */
6764 hystl[HYSTBASE + (int) (ang * 10.0)] += (k * k + j * j) / 4;
6765 }
6766 if (ge->iy3 == ge->prev->iy3) {
6767 if (ge->iy3 <= g->rymin) {
6768 g->rymin = ge->iy3;
6769 g->flatymin = 1;
6770 }
6771 if (ge->iy3 >= g->rymax) {
6772 g->rymax = ge->iy3;
6773 g->flatymax = 1;
6774 }
6775 } else {
6776 if (ge->iy3 < g->rymin) {
6777 g->rymin = ge->iy3;
6778 g->flatymin = 0;
6779 }
6780 if (ge->iy3 > g->rymax) {
6781 g->rymax = ge->iy3;
6782 g->flatymax = 0;
6783 }
6784 }
6785 } else if (ge->type == GE_CURVE) {
6786 if (ge->iy3 < g->rymin) {
6787 g->rymin = ge->iy3;
6788 g->flatymin = 0;
6789 }
6790 if (ge->iy3 > g->rymax) {
6791 g->rymax = ge->iy3;
6792 g->flatymax = 0;
6793 }
6794 }
6795 if (ge->type == GE_LINE || ge->type == GE_CURVE) {
6796 if (ge->ix3 < bbox[0])
6797 bbox[0] = ge->ix3;
6798 if (ge->ix3 > bbox[2])
6799 bbox[2] = ge->ix3;
6800 if (ge->iy3 < bbox[1])
6801 bbox[1] = ge->iy3;
6802 if (ge->iy3 > bbox[3])
6803 bbox[3] = ge->iy3;
6804 }
6805 }
6806 }
6807 }
6808
6809 /* get the most popular angle */
6810 max = 0;
6811 w = 0;
6812 for (i = 0; i < MAXHYST; i++) {
6813 if (hystl[i] > w) {
6814 w = hystl[i];
6815 max = i;
6816 }
6817 }
6818 ang = (double) (max - HYSTBASE) / 10.0;
6819 WARNING_2 fprintf(stderr, "Guessed italic angle: %f\n", ang);
6820 if (italic_angle == 0.0)
6821 italic_angle = ang;
6822
6823 /* build the hystogram of the lower points */
6824 for (i = 0; i < MAXHYST; i++)
6825 hystl[i] = 0;
6826
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]++;
6831 }
6832 }
6833
6834 /* build the hystogram of the upper points */
6835 for (i = 0; i < MAXHYST; i++)
6836 hystu[i] = 0;
6837
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]++;
6842 }
6843 }
6844
6845 /* build the hystogram of all the possible lower zones with max width */
6846 for (i = 0; i < MAXHYST; i++)
6847 zlhyst[i] = 0;
6848
6849 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
6850 for (j = 0; j < MAXBLUEWIDTH; j++)
6851 zlhyst[i] += hystl[i + j];
6852 }
6853
6854 /* build the hystogram of all the possible upper zones with max width */
6855 for (i = 0; i < MAXHYST; i++)
6856 zuhyst[i] = 0;
6857
6858 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
6859 for (j = 0; j < MAXBLUEWIDTH; j++)
6860 zuhyst[i] += hystu[i + j];
6861 }
6862
6863 /* find the baseline */
6864 w = bestblue(zlhyst, hystl, zuhyst, &bluevalues[0]);
6865 if (0)
6866 fprintf(stderr, "BaselineBlue zone %d%% %d...%d\n", w * 100 / nchars,
6867 bluevalues[0], bluevalues[1]);
6868
6869 if (w == 0) /* no baseline, something weird */
6870 return;
6871
6872 /* find the upper zones */
6873 for (nblues = 2; nblues < 14; nblues += 2) {
6874 w = bestblue(zuhyst, hystu, zlhyst, &bluevalues[nblues]);
6875
6876 if (0)
6877 fprintf(stderr, "Blue zone %d%% %d...%d\n", w * 100 / nchars,
6878 bluevalues[nblues], bluevalues[nblues+1]);
6879
6880 if (w * 20 < nchars)
6881 break; /* don't save this zone */
6882 }
6883
6884 /* find the lower zones */
6885 for (notherb = 0; notherb < 10; notherb += 2) {
6886 w = bestblue(zlhyst, hystl, zuhyst, &otherblues[notherb]);
6887
6888 if (0)
6889 fprintf(stderr, "OtherBlue zone %d%% %d...%d\n", w * 100 / nchars,
6890 otherblues[notherb], otherblues[notherb+1]);
6891
6892
6893 if (w * 20 < nchars)
6894 break; /* don't save this zone */
6895 }
6896
6897 }
6898
6899 /*
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.
6903 */
6904
6905 void
6906 docorrectwidth(void)
6907 {
6908 int i;
6909 GENTRY *ge;
6910 GLYPH *g;
6911 int xmin, xmax;
6912 int maxwidth, minsp;
6913
6914 /* enforce this minimal spacing,
6915 * we limit the amount of the enforced spacing to avoid
6916 * spacing the bold wonts too widely
6917 */
6918 minsp = (stdhw>60 || stdhw<10)? 60 : stdhw;
6919
6920 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6921 g->oldwidth=g->scaledwidth; /* save the old width, will need for AFM */
6922
6923 if (correctwidth && g->flags & GF_USED) {
6924 xmin = 5000;
6925 xmax = -5000;
6926 for (ge = g->entries; ge != 0; ge = ge->next) {
6927 if (ge->type != GE_LINE && ge->type != GE_CURVE)
6928 continue;
6929
6930 if (ge->ix3 <= xmin) {
6931 xmin = ge->ix3;
6932 }
6933 if (ge->ix3 >= xmax) {
6934 xmax = ge->ix3;
6935 }
6936 }
6937
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 );
6943 }
6944 }
6945 }
6946
6947 }
6948
6949 /*
6950 * Try to find the typical stem widths
6951 */
6952
6953 void
6954 stemstatistics(void)
6955 {
6956 #define MINDIST 10 /* minimal distance between the widths */
6957 int hyst[MAXHYST+MINDIST*2];
6958 int best[12];
6959 int i, j, k, w;
6960 int nchars;
6961 int ns;
6962 STEM *s;
6963 GLYPH *g;
6964
6965 /* start with typical stem width */
6966
6967 nchars=0;
6968
6969 /* build the hystogram of horizontal stem widths */
6970 memset(hyst, 0, sizeof hyst);
6971
6972 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
6973 if (g->flags & GF_USED) {
6974 nchars++;
6975 s = g->hstems;
6976 for (j = 0; j < g->nhs; j += 2) {
6977 if ((s[j].flags | s[j + 1].flags) & ST_END)
6978 continue;
6979 w = s[j + 1].value - s[j].value+1;
6980 if(w==20) /* split stems should not be counted */
6981 continue;
6982 if (w > 0 && w < MAXHYST - 1) {
6983 /*
6984 * handle some fuzz present in
6985 * converted fonts
6986 */
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;
6991 }
6992 }
6993 }
6994 }
6995 }
6996
6997 /* find 12 most frequent values */
6998 ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdhw);
6999
7000 /* store data in stemsnaph */
7001 for (i = 0; i < ns; i++)
7002 stemsnaph[i] = best[i];
7003 if (ns < 12)
7004 stemsnaph[ns] = 0;
7005
7006 /* build the hystogram of vertical stem widths */
7007 memset(hyst, 0, sizeof hyst);
7008
7009 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
7010 if (g->flags & GF_USED) {
7011 s = g->vstems;
7012 for (j = 0; j < g->nvs; j += 2) {
7013 if ((s[j].flags | s[j + 1].flags) & ST_END)
7014 continue;
7015 w = s[j + 1].value - s[j].value+1;
7016 if (w > 0 && w < MAXHYST - 1) {
7017 /*
7018 * handle some fuzz present in
7019 * converted fonts
7020 */
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;
7025 }
7026 }
7027 }
7028 }
7029 }
7030
7031 /* find 12 most frequent values */
7032 ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdvw);
7033
7034 /* store data in stemsnaph */
7035 for (i = 0; i < ns; i++)
7036 stemsnapv[i] = best[i];
7037 if (ns < 12)
7038 stemsnapv[ns] = 0;
7039
7040 #undef MINDIST
7041 }
7042
7043 /*
7044 * SB
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.
7048 *
7049 * It was a big headache to discover that.
7050 */
7051
7052 /* works on both int and float paths */
7053
7054 void
7055 reversepathsfromto(
7056 GENTRY * from,
7057 GENTRY * to
7058 )
7059 {
7060 GENTRY *ge, *nge, *pge;
7061 GENTRY *cur, *next;
7062 int i, n, ilast[2];
7063 double flast[2], f;
7064
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);
7069
7070 /* cut out the path itself */
7071 pge = ge->prev; /* GE_MOVE */
7072 if (pge == 0) {
7073 fprintf(stderr, "**! No MOVE before line !!! Fatal. ****\n");
7074 exit(1);
7075 }
7076 nge = ge->bkwd->next; /* GE_PATH */
7077 pge->next = nge;
7078 nge->prev = pge;
7079 ge->bkwd->next = 0; /* mark end of chain */
7080
7081 /* remember the starting point */
7082 if(ge->flags & GEF_FLOAT) {
7083 flast[0] = pge->fx3;
7084 flast[1] = pge->fy3;
7085 } else {
7086 ilast[0] = pge->ix3;
7087 ilast[1] = pge->iy3;
7088 }
7089
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;
7099 f = flast[i];
7100 flast[i] = cur->fpoints[i][2];
7101 cur->fpoints[i][2] = f;
7102 }
7103 } else {
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;
7109 n = ilast[i];
7110 ilast[i] = cur->ipoints[i][2];
7111 cur->ipoints[i][2] = n;
7112 }
7113 }
7114 addgeafter(pge, cur);
7115 }
7116
7117 /* restore the starting point */
7118 if(ge->flags & GEF_FLOAT) {
7119 pge->fx3 = flast[0];
7120 pge->fy3 = flast[1];
7121 } else {
7122 pge->ix3 = ilast[0];
7123 pge->iy3 = ilast[1];
7124 }
7125
7126 ge = nge;
7127 }
7128
7129 }
7130 }
7131
7132 void
7133 reversepaths(
7134 GLYPH * g
7135 )
7136 {
7137 reversepathsfromto(g->entries, NULL);
7138 }
7139
7140 /* add a kerning pair information, scales the value */
7141
7142 void
7143 addkernpair(
7144 unsigned id1,
7145 unsigned id2,
7146 int unscval
7147 )
7148 {
7149 static unsigned char *bits = 0;
7150 static int lastid;
7151 GLYPH *g = &glyph_list[id1];
7152 int i, n;
7153 struct kern *p;
7154
7155 if(unscval == 0 || id1 >= numglyphs || id2 >= numglyphs)
7156 return;
7157
7158 if( (glyph_list[id1].flags & GF_USED)==0
7159 || (glyph_list[id2].flags & GF_USED)==0 )
7160 return;
7161
7162 if(bits == 0) {
7163 bits = calloc( BITMAP_BYTES(numglyphs), 1);
7164 if (bits == NULL) {
7165 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
7166 exit(255);
7167 }
7168 lastid = id1;
7169 }
7170
7171 if(lastid != id1) {
7172 /* refill the bitmap cache */
7173 memset(bits, 0,BITMAP_BYTES(numglyphs));
7174 p = g->kern;
7175 for(i=g->kerncount; i>0; i--) {
7176 n = (p++)->id;
7177 SET_BITMAP(bits, n);
7178 }
7179 lastid = id1;
7180 }
7181
7182 if(IS_BITMAP(bits, id2))
7183 return; /* duplicate */
7184
7185 if(g->kerncount <= g->kernalloc) {
7186 g->kernalloc += 8;
7187 p = realloc(g->kern, sizeof(struct kern) * g->kernalloc);
7188 if(p == 0) {
7189 fprintf (stderr, "** realloc failed, kerning data will be incomplete\n");
7190 }
7191 g->kern = p;
7192 }
7193
7194 SET_BITMAP(bits, id2);
7195 p = &g->kern[g->kerncount];
7196 p->id = id2;
7197 p->val = iscale(unscval) - (g->scaledwidth - g->oldwidth);
7198 g->kerncount++;
7199 kerning_pairs++;
7200 }
7201
7202 /* print out the kerning information */
7203
7204 void
7205 print_kerning(
7206 FILE *afm_file
7207 )
7208 {
7209 int i, j, n;
7210 GLYPH *g;
7211 struct kern *p;
7212
7213 if( kerning_pairs == 0 )
7214 return;
7215
7216 fprintf(afm_file, "StartKernData\n");
7217 fprintf(afm_file, "StartKernPairs %hd\n", kerning_pairs);
7218
7219 for(i=0; i<numglyphs; i++) {
7220 g = &glyph_list[i];
7221 if( (g->flags & GF_USED) ==0)
7222 continue;
7223 p = g->kern;
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 );
7227 }
7228 }
7229
7230 fprintf(afm_file, "EndKernPairs\n");
7231 fprintf(afm_file, "EndKernData\n");
7232 }
7233
7234
7235 #if 0
7236
7237 /*
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().
7242 **
7243 ***********************************************
7244 **
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.
7248 **
7249 ** Find which contours go inside which and what is
7250 ** their proper direction. Then fix the direction
7251 ** to make it right.
7252 **
7253 */
7254
7255 #define MAXCONT 1000
7256
7257 void
7258 fixcontours(
7259 GLYPH * g
7260 )
7261 {
7262 CONTOUR cont[MAXCONT];
7263 short ymax[MAXCONT]; /* the highest point */
7264 short xofmax[MAXCONT]; /* X-coordinate of any point
7265 * at ymax */
7266 short ymin[MAXCONT]; /* the lowest point */
7267 short xofmin[MAXCONT]; /* X-coordinate of any point
7268 * at ymin */
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];
7272 int ncont;
7273 int i;
7274 int dx1, dy1, dx2, dy2;
7275 GENTRY *ge, *nge;
7276
7277 /* find the contours and their most upper/lower points */
7278 ncont = 0;
7279 ymax[0] = -5000;
7280 ymin[0] = 5000;
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;
7286 maxptr[ncont] = ge;
7287 }
7288 if (ge->iy3 < ymin[ncont]) {
7289 ymin[ncont] = ge->iy3;
7290 xofmin[ncont] = ge->ix3;
7291 minptr[ncont] = ge;
7292 }
7293 }
7294 if (ge->frwd != ge->next) {
7295 start[ncont++] = ge->frwd;
7296 ymax[ncont] = -5000;
7297 ymin[ncont] = 5000;
7298 }
7299 }
7300
7301 /* determine the directions of contours */
7302 for (i = 0; i < ncont; i++) {
7303 ge = minptr[i];
7304 nge = ge->frwd;
7305
7306 if (ge->type == GE_CURVE) {
7307 dx1 = ge->ix3 - ge->ix2;
7308 dy1 = ge->iy3 - ge->iy2;
7309
7310 if (dx1 == 0 && dy1 == 0) { /* a pathological case */
7311 dx1 = ge->ix3 - ge->ix1;
7312 dy1 = ge->iy3 - ge->iy1;
7313 }
7314 if (dx1 == 0 && dy1 == 0) { /* a more pathological
7315 * case */
7316 dx1 = ge->ix3 - ge->prev->ix3;
7317 dy1 = ge->iy3 - ge->prev->iy3;
7318 }
7319 } else {
7320 dx1 = ge->ix3 - ge->prev->ix3;
7321 dy1 = ge->iy3 - ge->prev->iy3;
7322 }
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;
7329 }
7330 if (dx1 == 0 && dy1 == 0) { /* a more pathological
7331 * case */
7332 dx2 = ge->ix3 - nge->ix3;
7333 dy2 = ge->iy3 - nge->iy3;
7334 }
7335 } else {
7336 dx2 = ge->ix3 - nge->ix3;
7337 dy2 = ge->iy3 - nge->iy3;
7338 }
7339
7340 /* compare angles */
7341 cont[i].direction = DIR_INNER;
7342 if (dy1 == 0) {
7343 if (dx1 < 0)
7344 cont[i].direction = DIR_OUTER;
7345 } else if (dy2 == 0) {
7346 if (dx2 > 0)
7347 cont[i].direction = DIR_OUTER;
7348 } else if (dx2 * dy1 < dx1 * dy2)
7349 cont[i].direction = DIR_OUTER;
7350
7351 cont[i].ymin = ymin[i];
7352 cont[i].xofmin = xofmin[i];
7353 }
7354
7355 /* save the information that may be needed further */
7356 g->ncontours = ncont;
7357 if (ncont > 0) {
7358 g->contours = malloc(sizeof(CONTOUR) * ncont);
7359 if (g->contours == 0) {
7360 fprintf(stderr, "***** Memory allocation error *****\n");
7361 exit(255);
7362 }
7363 memcpy(g->contours, cont, sizeof(CONTOUR) * ncont);
7364 }
7365 }
7366
7367 #endif
7368
7369 /*
7370 *
7371 */
7372
SWFTools is a collection of utilities for working with Adobe Flash files