| [ Index ] |
PHP Cross Reference of vtigercrm-6.1.0 |
[Summary view] [Print] [Text view]
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 WINDOWS 16 # include <netinet/in.h> 17 # include <unistd.h> 18 #else 19 # include "windows.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 best[B] = best[C] = 0; 5339 /* i iterates by ncoef[B], j iterates by ncoef[C] */ 5340 for(i=0; i<ncoef[B]; i++) { 5341 for(j=0; j<ncoef[C]; j++) { 5342 for(k=0; k<2; k++) { /*X, Y*/ 5343 cv[1][k] = cv[0][k] + middf[B][k]*coef[B][i]; 5344 cv[2][k] = cv[3][k] + middf[C][k]*coef[C][j]; 5345 } 5346 res[i][j] = thisres = fdotcurvdist2(cv, dots, ndots, NULL); 5347 if(thisres < bestres) { 5348 goodres = bestres; 5349 good[B] = best[B]; 5350 good[C] = best[C]; 5351 bestres = thisres; 5352 best[B] = i; 5353 best[C] = j; 5354 } else if(thisres < goodres) { 5355 goodres = thisres; 5356 good[B] = i; 5357 good[C] = j; 5358 } 5359 #ifdef DEBUG_APPROXCV 5360 fprintf(stderr, " at (%g,%g) dist=%g %s\n", coef[B][i], coef[C][j], sqrt(thisres), 5361 (best[B]==i && best[C]==j)? "(BEST)":""); 5362 #endif 5363 } 5364 } 5365 #ifdef DEBUG_APPROXCV 5366 fprintf(stderr, " best: at (%g, %g) dist=%g\n", 5367 coef[B][best[B]], coef[C][best[C]], sqrt(bestres)); 5368 fprintf(stderr, " B:%d,%d C:%d,%d -- 2nd best: at (%g, %g) dist=%g\n", 5369 best[B], good[B], best[C], good[C], coef[B][good[B]], coef[C][good[C]], sqrt(goodres)); 5370 #endif 5371 5372 if(bestres < (0.1*0.1)) { /* consider it close enough */ 5373 /* calculate the coordinates to return */ 5374 for(k=0; k<2; k++) { /*X, Y*/ 5375 cv[1][k] = cv[0][k] + middf[B][k]*coef[B][best[B]]; 5376 cv[2][k] = cv[3][k] + middf[C][k]*coef[C][best[C]]; 5377 } 5378 #ifdef DEBUG_APPROXCV 5379 fprintf(stderr, "quick approximated middle points "); printdot(cv[1]); 5380 fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n"); 5381 #endif 5382 return; 5383 } 5384 keepsym = 0; 5385 if(best[B] != best[C] && best[B]-best[C] == good[C]-good[B]) { 5386 keepsym = 1; 5387 #ifdef DEBUG_APPROXCV 5388 fprintf(stderr, "keeping symmetry!\n"); 5389 #endif 5390 } 5391 for(i=0; i<2; i++) { /*B,C*/ 5392 if(ncoef[i]==1) 5393 continue; 5394 if(keepsym) { 5395 /* try to keep the symmetry */ 5396 if(best[i] < good[i]) { 5397 from[i] = coef[i][best[i]]; 5398 to[i] = coef[i][good[i]]; 5399 } else { 5400 from[i] = coef[i][good[i]]; 5401 to[i] = coef[i][best[i]]; 5402 } 5403 } else { 5404 df = (to[i]-from[i]) / ncoef[i]; 5405 from[i] += df*best[i]; 5406 to[i] = from[i] + df; 5407 } 5408 if( fabs(df*middf[i][0]) < STEPEPS && fabs(df*middf[i][1]) < STEPEPS) { 5409 /* this side has converged */ 5410 from[i] = to[i] = (from[i]+to[i]) / 2.; 5411 ncoef[i] = 1; 5412 } else 5413 ncoef[i] = NORMSECT; 5414 } 5415 5416 } 5417 /* calculate the coordinates to return */ 5418 for(k=0; k<2; k++) { /*X, Y*/ 5419 cv[1][k] = cv[0][k] + middf[B][k]*from[B]; 5420 cv[2][k] = cv[3][k] + middf[C][k]*from[C]; 5421 } 5422 #ifdef DEBUG_APPROXCV 5423 fprintf(stderr, "approximated middle points "); printdot(cv[1]); 5424 fprintf(stderr, " "); printdot(cv[2]); fprintf(stderr, "\n"); 5425 #endif 5426 #undef B 5427 #undef C 5428 #undef MAXSECT 5429 #undef NORMSECT 5430 #undef STEPEPS 5431 } 5432 5433 /* 5434 * Find the squared value of the sinus of the angle between the 5435 * end of ge1 and the beginning of ge2 5436 * The curve must be normalized. 5437 */ 5438 5439 static double 5440 fjointsin2( 5441 GENTRY *ge1, 5442 GENTRY *ge2 5443 ) 5444 { 5445 double d[3][2 /*X,Y*/]; 5446 double scale1, scale2, len1, len2; 5447 int axis; 5448 5449 if(ge1->rtg < 0) { 5450 d[1][X] = ge1->fx3 - ge1->prev->fx3; 5451 d[1][Y] = ge1->fy3 - ge1->prev->fy3; 5452 } else { 5453 d[1][X] = ge1->fx3 - ge1->fpoints[X][ge1->rtg]; 5454 d[1][Y] = ge1->fy3 - ge1->fpoints[Y][ge1->rtg]; 5455 } 5456 d[2][X] = ge2->fpoints[X][ge2->ftg] - ge2->prev->fx3; 5457 d[2][Y] = ge2->fpoints[Y][ge2->ftg] - ge2->prev->fy3; 5458 5459 len1 = sqrt( d[1][X]*d[1][X] + d[1][Y]*d[1][Y] ); 5460 len2 = sqrt( d[2][X]*d[2][X] + d[2][Y]*d[2][Y] ); 5461 /* scale the 2nd segment to the length of 1 5462 * and to make sure that the 1st segment is longer scale it to 5463 * the length of 2 and extend to the same distance backwards 5464 */ 5465 scale1 = 2./len1; 5466 scale2 = 1./len2; 5467 5468 for(axis=0; axis <2; axis++) { 5469 d[0][axis] = -( d[1][axis] *= scale1 ); 5470 d[2][axis] *= scale2; 5471 } 5472 return fdotsegdist2(d, d[2]); 5473 } 5474 5475 #if 0 5476 /* find the area covered by the curve 5477 * (limited by the projections to the X axis) 5478 */ 5479 5480 static double 5481 fcvarea( 5482 GENTRY *ge 5483 ) 5484 { 5485 double Ly, My, Ny, Py, Qx, Rx, Sx; 5486 double area; 5487 5488 /* y = Ly*t^3 + My*t^2 + Ny*t + Py */ 5489 Ly = -ge->prev->fy3 + 3*(ge->fy1 - ge->fy2) + ge->fy3; 5490 My = 3*ge->prev->fy3 - 6*ge->fy1 + 3*ge->fy2; 5491 Ny = 3*(-ge->prev->fy3 + ge->fy1); 5492 Py = ge->prev->fy3; 5493 5494 /* dx/dt = Qx*t^2 + Rx*t + Sx */ 5495 Qx = 3*(-ge->prev->fx3 + 3*(ge->fx1 - ge->fx2) + ge->fx3); 5496 Rx = 6*(ge->prev->fx3 - 2*ge->fx1 + ge->fx2); 5497 Sx = 3*(-ge->prev->fx3 + ge->fx1); 5498 5499 /* area is integral[from 0 to 1]( y(t) * dx(t)/dt *dt) */ 5500 area = 1./6.*(Ly*Qx) + 1./5.*(Ly*Rx + My*Qx) 5501 + 1./4.*(Ly*Sx + My*Rx + Ny*Qx) + 1./3.*(My*Sx + Ny*Rx + Py*Qx) 5502 + 1./2.*(Ny*Sx + Py*Rx) + Py*Sx; 5503 5504 return area; 5505 } 5506 #endif 5507 5508 /* find the value of point on the curve at the given parameter t, 5509 * along the given axis (0 - X, 1 - Y). 5510 */ 5511 5512 static double 5513 fcvval( 5514 GENTRY *ge, 5515 int axis, 5516 double t 5517 ) 5518 { 5519 double t2, mt, mt2; 5520 5521 /* val = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 */ 5522 t2 = t*t; 5523 mt = 1-t; 5524 mt2 = mt*mt; 5525 5526 return ge->prev->fpoints[axis][2]*mt2*mt 5527 + 3*(ge->fpoints[axis][0]*mt2*t + ge->fpoints[axis][1]*mt*t2) 5528 + ge->fpoints[axis][2]*t*t2; 5529 } 5530 5531 /* 5532 * Find ndots equally spaced dots on a curve or line and fill 5533 * their coordinates into the dots array 5534 */ 5535 5536 static void 5537 fsampledots( 5538 GENTRY *ge, 5539 double dots[][2], /* the dots to fill */ 5540 int ndots 5541 ) 5542 { 5543 int i, axis; 5544 double t, nf, dx, d[2]; 5545 5546 nf = ndots+1; 5547 if(ge->type == GE_CURVE) { 5548 for(i=0; i<ndots; i++) { 5549 t = (i+1)/nf; 5550 for(axis=0; axis<2; axis++) 5551 dots[i][axis] = fcvval(ge, axis, t); 5552 } 5553 } else { /* line */ 5554 d[0] = ge->fx3 - ge->prev->fx3; 5555 d[1] = ge->fy3 - ge->prev->fy3; 5556 for(i=0; i<ndots; i++) { 5557 t = (i+1)/nf; 5558 for(axis=0; axis<2; axis++) 5559 dots[i][axis] = ge->prev->fpoints[axis][2] 5560 + t*d[axis]; 5561 } 5562 } 5563 } 5564 5565 /* 5566 * Allocate a structure gex_con 5567 */ 5568 5569 static void 5570 alloc_gex_con( 5571 GENTRY *ge 5572 ) 5573 { 5574 ge->ext = (void*)calloc(1, sizeof(GEX_CON)); 5575 if(ge->ext == 0) { 5576 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 5577 exit(255); 5578 } 5579 } 5580 5581 /* 5582 * Normalize a gentry for fforceconcise() : find the points that 5583 * can be used to calculate the tangents. 5584 */ 5585 5586 static void 5587 fnormalizege( 5588 GENTRY *ge 5589 ) 5590 { 5591 int midsame, frontsame, rearsame; 5592 5593 if(ge->type == GE_LINE) { 5594 ge->ftg = 2; 5595 ge->rtg = -1; 5596 } else { /* assume it's a curve */ 5597 midsame = (fabs(ge->fx1-ge->fx2)<FEPS && fabs(ge->fy1-ge->fy2)<FEPS); 5598 frontsame = (fabs(ge->fx1-ge->prev->fx3)<FEPS && fabs(ge->fy1-ge->prev->fy3)<FEPS); 5599 rearsame = (fabs(ge->fx3-ge->fx2)<FEPS && fabs(ge->fy3-ge->fy2)<FEPS); 5600 5601 if(midsame && (frontsame || rearsame) ) { 5602 /* essentially a line */ 5603 ge->ftg = 2; 5604 ge->rtg = -1; 5605 } else { 5606 if(frontsame) { 5607 ge->ftg = 1; 5608 } else { 5609 ge->ftg = 0; 5610 } 5611 if(rearsame) { 5612 ge->rtg = 0; 5613 } else { 5614 ge->rtg = 1; 5615 } 5616 } 5617 } 5618 } 5619 5620 /* various definition for the processing of outlines */ 5621 5622 /* maximal average quadratic distance from the original curve 5623 * (in dots) to consider the joined curve good 5624 */ 5625 #define CVEPS 1.5 5626 #define CVEPS2 (CVEPS*CVEPS) 5627 /* squared sinus of the maximal angle that we consider a smooth joint */ 5628 #define SMOOTHSIN2 0.25 /* 0.25==sin(30 degrees)^2 */ 5629 /* squared line length that we consider small */ 5630 #define SMALL_LINE2 (15.*15.) 5631 /* how many times a curve must be bigger than a line to join, squared */ 5632 #define TIMES_LINE2 (3.*3.) 5633 5634 /* 5635 * Normalize and analyse a gentry for fforceconcise() and fill out the gex_con 5636 * structure 5637 */ 5638 5639 static void 5640 fanalyzege( 5641 GENTRY *ge 5642 ) 5643 { 5644 int i, ix, iy; 5645 double avsd2, dots[3][2 /*X,Y*/]; 5646 GEX_CON *gex; 5647 5648 gex = X_CON(ge); 5649 memset(gex, 0, sizeof *gex); 5650 5651 gex->len2 = 0; 5652 for(i=0; i<2; i++) { 5653 avsd2 = gex->d[i] = ge->fpoints[i][2] - ge->prev->fpoints[i][2]; 5654 gex->len2 += avsd2*avsd2; 5655 } 5656 gex->sin2 = fjointsin2(ge, ge->frwd); 5657 if(ge->type == GE_CURVE) { 5658 ge->dir = fgetcvdir(ge); 5659 for(i=0; i<2; i++) { 5660 dots[0][i] = ge->prev->fpoints[i][2]; 5661 dots[1][i] = ge->fpoints[i][2]; 5662 dots[2][i] = fcvval(ge, i, 0.5); 5663 } 5664 avsd2 = fdotsegdist2(dots, dots[2]); 5665 if(avsd2 <= CVEPS2) { 5666 gex->flags |= GEXF_FLAT; 5667 } 5668 } else { 5669 ge->dir = CVDIR_FEQUAL|CVDIR_REQUAL; 5670 gex->flags |= GEXF_FLAT; 5671 } 5672 if(gex->flags & GEXF_FLAT) { 5673 if( fabs(gex->d[X]) > FEPS && fabs(gex->d[Y]) < 5. 5674 && fabs(gex->d[Y] / gex->d[X]) < 0.2) 5675 gex->flags |= GEXF_HOR; 5676 else if( fabs(gex->d[Y]) > FEPS && fabs(gex->d[X]) < 5. 5677 && fabs(gex->d[X] / gex->d[Y]) < 0.2) 5678 gex->flags |= GEXF_VERT; 5679 } 5680 ix = gex->isd[X] = fsign(gex->d[X]); 5681 iy = gex->isd[Y] = fsign(gex->d[Y]); 5682 if(ix <= 0) { 5683 if(iy <= 0) 5684 gex->flags |= GEXF_QDL; 5685 if(iy >= 0) 5686 gex->flags |= GEXF_QUL; 5687 if(gex->flags & GEXF_HOR) 5688 gex->flags |= GEXF_IDQ_L; 5689 } 5690 if(ix >= 0) { 5691 if(iy <= 0) 5692 gex->flags |= GEXF_QDR; 5693 if(iy >= 0) 5694 gex->flags |= GEXF_QUR; 5695 if(gex->flags & GEXF_HOR) 5696 gex->flags |= GEXF_IDQ_R; 5697 } 5698 if(gex->flags & GEXF_VERT) { 5699 if(iy <= 0) { 5700 gex->flags |= GEXF_IDQ_U; 5701 } else { /* supposedly there is no 0-sized entry */ 5702 gex->flags |= GEXF_IDQ_D; 5703 } 5704 } 5705 } 5706 5707 /* 5708 * Analyse a joint between this and following gentry for fforceconcise() 5709 * and fill out the corresponding parts of the gex_con structure 5710 * Bothe entries must be analyzed first. 5711 */ 5712 5713 static void 5714 fanalyzejoint( 5715 GENTRY *ge 5716 ) 5717 { 5718 GENTRY *nge = ge->frwd; 5719 GENTRY tge; 5720 GEX_CON *gex, *ngex; 5721 double avsd2, dots[3][2 /*X,Y*/]; 5722 int i; 5723 5724 gex = X_CON(ge); ngex = X_CON(nge); 5725 5726 /* look if they can be joined honestly */ 5727 5728 /* if any is flat, they should join smoothly */ 5729 if( (gex->flags & GEXF_FLAT || ngex->flags & GEXF_FLAT) 5730 && gex->sin2 > SMOOTHSIN2) 5731 goto try_flatboth; 5732 5733 if(ge->type == GE_LINE) { 5734 if(nge->type == GE_LINE) { 5735 if(gex->len2 > SMALL_LINE2 || ngex->len2 > SMALL_LINE2) 5736 goto try_flatboth; 5737 } else { 5738 if(gex->len2*TIMES_LINE2 > ngex->len2) 5739 goto try_flatboth; 5740 } 5741 } else if(nge->type == GE_LINE) { 5742 if(ngex->len2*TIMES_LINE2 > gex->len2) 5743 goto try_flatboth; 5744 } 5745 5746 /* if curve changes direction */ 5747 if( gex->isd[X]*ngex->isd[X]<0 || gex->isd[Y]*ngex->isd[Y]<0) 5748 goto try_idealone; 5749 5750 /* if would create a zigzag */ 5751 if( ((ge->dir&CVDIR_FRONT)-CVDIR_FEQUAL) * ((nge->dir&CVDIR_REAR)-CVDIR_REQUAL) < 0 ) 5752 goto try_flatone; 5753 5754 if( fcrossraysge(ge, nge, NULL, NULL, NULL) ) 5755 gex->flags |= GEXF_JGOOD; 5756 5757 try_flatone: 5758 /* look if they can be joined by flatting out one of the entries */ 5759 5760 /* at this point we know that the general direction of the 5761 * gentries is OK 5762 */ 5763 5764 if( gex->flags & GEXF_FLAT ) { 5765 tge = *ge; 5766 tge.fx1 = tge.fx3; 5767 tge.fy1 = tge.fy3; 5768 fnormalizege(&tge); 5769 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) ) 5770 gex->flags |= GEXF_JFLAT|GEXF_JFLAT1; 5771 } 5772 if( ngex->flags & GEXF_FLAT ) { 5773 tge = *nge; 5774 tge.fx2 = ge->fx3; 5775 tge.fy2 = ge->fy3; 5776 fnormalizege(&tge); 5777 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) ) 5778 gex->flags |= GEXF_JFLAT|GEXF_JFLAT2; 5779 } 5780 5781 try_idealone: 5782 /* look if one of the entries can be brought to an idealized 5783 * horizontal or vertical position and then joined 5784 */ 5785 if( gex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) { 5786 tge = *ge; 5787 tge.fx1 = tge.fx3; 5788 tge.fy1 = ge->prev->fy3; /* force horizontal */ 5789 fnormalizege(&tge); 5790 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) ) 5791 gex->flags |= GEXF_JID|GEXF_JID1; 5792 } else if( gex->flags & GEXF_VERT && gex->isd[Y]*ngex->isd[Y]>=0 ) { 5793 tge = *ge; 5794 tge.fx1 = ge->prev->fx3; /* force vertical */ 5795 tge.fy1 = tge.fy3; 5796 fnormalizege(&tge); 5797 if( fcrossraysge(&tge, nge, NULL, NULL, NULL) ) 5798 gex->flags |= GEXF_JID|GEXF_JID1; 5799 } 5800 if( ngex->flags & GEXF_HOR && gex->isd[X]*ngex->isd[X]>=0 ) { 5801 tge = *nge; 5802 tge.fx2 = ge->fx3; 5803 tge.fy2 = nge->fy3; /* force horizontal */ 5804 fnormalizege(&tge); 5805 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) ) 5806 gex->flags |= GEXF_JID|GEXF_JID2; 5807 } else if( ngex->flags & GEXF_VERT && gex->isd[Y]*ngex->isd[Y]>=0 ) { 5808 tge = *nge; 5809 tge.fx2 = nge->fx3; /* force vertical */ 5810 tge.fy2 = ge->fy3; 5811 fnormalizege(&tge); 5812 if( fcrossraysge(ge, &tge, NULL, NULL, NULL) ) 5813 gex->flags |= GEXF_JID|GEXF_JID2; 5814 } 5815 5816 try_flatboth: 5817 /* look if we can change them to one line */ 5818 if(gex->flags & GEXF_FLAT && ngex->flags & GEXF_FLAT) { 5819 for(i=0; i<2; i++) { 5820 dots[0][i] = ge->prev->fpoints[i][2]; 5821 dots[1][i] = nge->fpoints[i][2]; 5822 dots[2][i] = ge->fpoints[i][2]; 5823 } 5824 if( fdotsegdist2(dots, dots[2]) <= CVEPS2) 5825 gex->flags |= GEXF_JLINE; 5826 } 5827 } 5828 5829 /* 5830 * Force conciseness of one contour in the glyph, 5831 * the contour is indicated by one entry from it. 5832 */ 5833 5834 static void 5835 fconcisecontour( 5836 GLYPH *g, 5837 GENTRY *startge 5838 ) 5839 { 5840 /* initial maximal number of dots to be used as reference */ 5841 #define MAXDOTS ((NREFDOTS+1)*12) 5842 5843 GENTRY *ge, *pge, *nge, *ige; 5844 GEX_CON *gex, *pgex, *ngex, *nngex; 5845 GENTRY tpge, tnge; 5846 int quad, qq, i, j, ndots, maxdots; 5847 int found[2]; 5848 int joinmask, pflag, nflag; 5849 struct dot_dist *dots; 5850 double avsd2, maxd2, eps2; 5851 double apcv[4][2]; 5852 5853 if(startge == 0) { 5854 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n", 5855 __FILE__, __LINE__); 5856 fprintf(stderr, "Strange contour in glyph %s\n", g->name); 5857 dumppaths(g, NULL, NULL); 5858 return; 5859 } 5860 5861 if(startge->type != GE_CURVE && startge->type != GE_LINE) 5862 return; /* probably a degenerate contour */ 5863 5864 if(ISDBG(FCONCISE)) 5865 fprintf(stderr, "processing contour 0x%p of glyph %s\n", startge, g->name); 5866 5867 maxdots = MAXDOTS; 5868 dots = (struct dot_dist *)malloc(sizeof(*dots)*maxdots); 5869 if(dots == NULL) { 5870 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 5871 exit(255); 5872 } 5873 5874 ge = startge; 5875 joinmask = GEXF_JGOOD; 5876 while(1) { 5877 restart: 5878 gex = X_CON(ge); 5879 if((gex->flags & GEXF_JMASK) > ((joinmask<<1)-1)) { 5880 if(ISDBG(FCONCISE)) 5881 fprintf(stderr, "found higher flag (%x>%x) at 0x%p\n", 5882 gex->flags & GEXF_JMASK, ((joinmask<<1)-1), ge); 5883 joinmask <<= 1; 5884 startge = ge; /* have to redo the pass */ 5885 continue; 5886 } 5887 if(( gex->flags & joinmask )==0) 5888 goto next; 5889 5890 /* if we happen to be in the middle of a string of 5891 * joinable entries, find its beginning 5892 */ 5893 if( gex->flags & (GEXF_JCVMASK^GEXF_JID) ) 5894 quad = gex->flags & X_CON_F(ge->frwd) & GEXF_QMASK; 5895 else if( gex->flags & GEXF_JID2 ) 5896 quad = gex->flags & GEXF_QFROM_IDEAL(X_CON_F(ge->frwd)) & GEXF_QMASK; 5897 else /* must be GEXF_JID1 */ 5898 quad = GEXF_QFROM_IDEAL(gex->flags) & X_CON_F(ge->frwd) & GEXF_QMASK; 5899 5900 pge = ge; 5901 pgex = X_CON(pge->bkwd); 5902 5903 if(ISDBG(FCONCISE)) 5904 fprintf(stderr, "ge %p prev -> 0x%p ", ge, pge); 5905 5906 while(pgex->flags & GEXF_JCVMASK) { 5907 if( !(pgex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID2)) ) 5908 qq = GEXF_QFROM_IDEAL(pgex->flags); 5909 else 5910 qq = pgex->flags & GEXF_QMASK; 5911 5912 if(ISDBG(FCONCISE)) 5913 fprintf(stderr, "(%x?%x)", quad, qq); 5914 5915 if( !(quad & qq) ) { 5916 if( !(X_CON_F(pge) & (GEXF_JCVMASK^GEXF_JID)) 5917 && pgex->flags & (GEXF_JCVMASK^GEXF_JID) ) { 5918 /* the previos entry is definitely a better match */ 5919 if(pge == ge) { 5920 if(ISDBG(FCONCISE)) 5921 fprintf(stderr, "\nprev is a better match at %p\n", pge); 5922 startge = ge; 5923 goto next; 5924 } else 5925 pge = pge->frwd; 5926 } 5927 break; 5928 } 5929 5930 quad &= qq; 5931 pge = pge->bkwd; 5932 pgex = X_CON(pge->bkwd); 5933 if(ISDBG(FCONCISE)) 5934 fprintf(stderr, "0x%p ", pge); 5935 } 5936 5937 /* collect as many entries for joining as possible */ 5938 nge = ge->frwd; 5939 ngex = X_CON(nge); 5940 nngex = X_CON(nge->frwd); 5941 5942 if(ISDBG(FCONCISE)) 5943 fprintf(stderr, ": 0x%x\nnext -> 0x%p ", pge, nge); 5944 5945 while(ngex->flags & GEXF_JCVMASK) { 5946 if( !(ngex->flags & ((GEXF_JCVMASK^GEXF_JID)|GEXF_JID1)) ) 5947 qq = GEXF_QFROM_IDEAL(nngex->flags); 5948 else 5949 qq = nngex->flags & GEXF_QMASK; 5950 5951 if(ISDBG(FCONCISE)) 5952 fprintf(stderr, "(%x?%x)", quad, qq); 5953 if( !(quad & qq) ) { 5954 if( !(X_CON_F(nge->bkwd) & (GEXF_JCVMASK^GEXF_JID)) 5955 && ngex->flags & (GEXF_JCVMASK^GEXF_JID) ) { 5956 /* the next-next entry is definitely a better match */ 5957 if(nge == ge->frwd) { 5958 if(ISDBG(FCONCISE)) 5959 fprintf(stderr, "\nnext %x is a better match than %x at %p (jmask %x)\n", 5960 ngex->flags & GEXF_JCVMASK, gex->flags & GEXF_JCVMASK, nge, joinmask); 5961 goto next; 5962 } else 5963 nge = nge->bkwd; 5964 } 5965 break; 5966 } 5967 5968 quad &= qq; 5969 nge = nge->frwd; 5970 ngex = nngex; 5971 nngex = X_CON(nge->frwd); 5972 if(ISDBG(FCONCISE)) 5973 fprintf(stderr, "0x%p ", nge); 5974 } 5975 5976 if(ISDBG(FCONCISE)) 5977 fprintf(stderr, ": 0x%x\n", nge); 5978 5979 /* XXX add splitting of last entries if neccessary */ 5980 5981 /* make sure that all the reference dots are valid */ 5982 for(ige = pge; ige != nge->frwd; ige = ige->frwd) { 5983 nngex = X_CON(ige); 5984 if( !(nngex->flags & GEXF_VDOTS) ) { 5985 fsampledots(ige, nngex->dots, NREFDOTS); 5986 nngex->flags |= GEXF_VDOTS; 5987 } 5988 } 5989 5990 /* do the actual joining */ 5991 while(1) { 5992 pgex = X_CON(pge); 5993 ngex = X_CON(nge->bkwd); 5994 /* now the segments to be joined are pge...nge */ 5995 5996 ndots = 0; 5997 for(ige = pge; ige != nge->frwd; ige = ige->frwd) { 5998 if(maxdots < ndots+(NREFDOTS+1)) { 5999 maxdots += MAXDOTS; 6000 dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots); 6001 if(dots == NULL) { 6002 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 6003 exit(255); 6004 } 6005 } 6006 nngex = X_CON(ige); 6007 for(i=0; i<NREFDOTS; i++) { 6008 for(j=0; j<2; j++) 6009 dots[ndots].p[j] = nngex->dots[i][j]; 6010 ndots++; 6011 } 6012 for(j=0; j<2; j++) 6013 dots[ndots].p[j] = ige->fpoints[j][2]; 6014 ndots++; 6015 } 6016 ndots--; /* the last point is not interesting */ 6017 6018 tpge = *pge; 6019 pflag = pgex->flags; 6020 if(pflag & (GEXF_JGOOD|GEXF_JFLAT2|GEXF_JID2)) { 6021 /* nothing */ 6022 } else if(pflag & GEXF_JFLAT) { 6023 tpge.fx1 = tpge.fx3; 6024 tpge.fy1 = tpge.fy3; 6025 } else if(pflag & GEXF_JID) { 6026 if(pflag & GEXF_HOR) 6027 tpge.fy1 = tpge.bkwd->fy3; 6028 else 6029 tpge.fx1 = tpge.bkwd->fx3; 6030 } 6031 6032 tnge = *nge; 6033 nflag = ngex->flags; 6034 if(nflag & (GEXF_JGOOD|GEXF_JFLAT1|GEXF_JID) 6035 && !(nflag & GEXF_JID2)) { 6036 /* nothing */ 6037 } else if(nflag & GEXF_JFLAT) { 6038 tnge.fx2 = tnge.bkwd->fx3; 6039 tnge.fy2 = tnge.bkwd->fy3; 6040 } else if(nflag & GEXF_JID) { 6041 if(X_CON_F(nge) & GEXF_HOR) 6042 tnge.fy2 = tnge.fy3; 6043 else 6044 tnge.fx2 = tnge.fx3; 6045 } 6046 6047 fnormalizege(&tpge); 6048 fnormalizege(&tnge); 6049 if( fcrossraysge(&tpge, &tnge, NULL, NULL, &apcv[1]) ) { 6050 apcv[0][X] = tpge.bkwd->fx3; 6051 apcv[0][Y] = tpge.bkwd->fy3; 6052 /* apcv[1] and apcv[2] were filled by fcrossraysge() */ 6053 apcv[3][X] = tnge.fx3; 6054 apcv[3][Y] = tnge.fy3; 6055 6056 /* calculate the precision depending on the smaller dimension of the curve */ 6057 maxd2 = apcv[3][X]-apcv[0][X]; 6058 maxd2 *= maxd2; 6059 eps2 = apcv[3][Y]-apcv[0][Y]; 6060 eps2 *= eps2; 6061 if(maxd2 < eps2) 6062 eps2 = maxd2; 6063 eps2 *= (CVEPS2*4.) / (400.*400.); 6064 if(eps2 < CVEPS2) 6065 eps2 = CVEPS2; 6066 else if(eps2 > CVEPS2*4.) 6067 eps2 = CVEPS2*4.; 6068 6069 fapproxcurve(apcv, dots, ndots); 6070 6071 avsd2 = fdotcurvdist2(apcv, dots, ndots, &maxd2); 6072 if(ISDBG(FCONCISE)) 6073 fprintf(stderr, "avsd = %g, maxd = %g, ", sqrt(avsd2), sqrt(maxd2)); 6074 if(avsd2 <= eps2 && maxd2 <= eps2*2.) { 6075 /* we've guessed a curve that is close enough */ 6076 ggoodcv++; ggoodcvdots += ndots; 6077 6078 if(ISDBG(FCONCISE)) { 6079 fprintf(stderr, "in %s joined %p-%p to ", g->name, pge, nge); 6080 for(i=0; i<4; i++) { 6081 fprintf(stderr, " (%g, %g)", apcv[i][X], apcv[i][Y]); 6082 } 6083 fprintf(stderr, " from\n"); 6084 dumppaths(g, pge, nge); 6085 } 6086 for(i=0; i<3; i++) { 6087 pge->fxn[i] = apcv[i+1][X]; 6088 pge->fyn[i] = apcv[i+1][Y]; 6089 } 6090 pge->type = GE_CURVE; 6091 ge = pge; 6092 for(ige = pge->frwd; ; ige = pge->frwd) { 6093 if(ige == pge) { 6094 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n", 6095 __FILE__, __LINE__); 6096 free(dots); 6097 return; 6098 } 6099 if(startge == ige) 6100 startge = pge; 6101 free(ige->ext); 6102 freethisge(ige); 6103 if(ige == nge) 6104 break; 6105 } 6106 fnormalizege(ge); 6107 if(ISDBG(FCONCISE)) { 6108 fprintf(stderr, "normalized "); 6109 for(i=0; i<3; i++) { 6110 fprintf(stderr, " (%g, %g)", ge->fpoints[X][i], ge->fpoints[Y][i]); 6111 } 6112 fprintf(stderr, "\n"); 6113 } 6114 fanalyzege(ge); 6115 fanalyzejoint(ge); 6116 fanalyzege(ge->bkwd); 6117 fanalyzejoint(ge->bkwd); 6118 6119 /* the results of this join will have to be reconsidered */ 6120 startge = ge = ge->frwd; 6121 goto restart; 6122 } else { 6123 gbadcv++; gbadcvdots += ndots; 6124 } 6125 } 6126 6127 /* if we're down to 2 entries then the join has failed */ 6128 if(pge->frwd == nge) { 6129 pgex->flags &= ~joinmask; 6130 if(ISDBG(FCONCISE)) 6131 fprintf(stderr, "no match\n"); 6132 goto next; 6133 } 6134 6135 /* reduce the number of entries by dropping one at some end, 6136 * should never drop the original ge from the range 6137 */ 6138 6139 if(nge->bkwd == ge 6140 || pge != ge && (pgex->flags & GEXF_JCVMASK) <= (ngex->flags & GEXF_JCVMASK) ) { 6141 pge = pge->frwd; 6142 } else { 6143 nge = nge->bkwd; 6144 } 6145 if(ISDBG(FCONCISE)) 6146 fprintf(stderr, "next try: %p to %p\n", pge, nge); 6147 } 6148 6149 next: 6150 ge = ge->frwd; 6151 if(ge == startge) { 6152 joinmask = (joinmask >> 1) & GEXF_JCVMASK; 6153 if(joinmask == 0) 6154 break; 6155 } 6156 } 6157 6158 /* join flat segments into lines */ 6159 /* here ge==startge */ 6160 while(1) { 6161 gex = X_CON(ge); 6162 if( !(gex->flags & GEXF_JLINE) ) 6163 goto next2; 6164 6165 ndots = 0; 6166 dots[ndots].p[X] = ge->fx3; 6167 dots[ndots].p[Y] = ge->fy3; 6168 ndots++; 6169 6170 pge = ge->bkwd; 6171 nge = ge->frwd; 6172 6173 if(ISDBG(FCONCISE)) 6174 fprintf(stderr, "joining LINE from %p-%p\n", ge, nge); 6175 6176 while(pge!=nge) { 6177 pgex = X_CON(pge); 6178 ngex = X_CON(nge); 6179 if(ISDBG(FCONCISE)) 6180 fprintf(stderr, "(p=%p/%x n=0x%x/%x) ", pge, pgex->flags & GEXF_JLINE, 6181 nge, ngex->flags & GEXF_JLINE); 6182 if( !((pgex->flags | ngex->flags) & GEXF_JLINE) ) { 6183 if(ISDBG(FCONCISE)) 6184 fprintf(stderr, "(end p=%p n=%p) ", pge, nge); 6185 break; 6186 } 6187 6188 if(maxdots < ndots+2) { 6189 maxdots += MAXDOTS; 6190 dots = (struct dot_dist *)realloc((void *)dots, sizeof(*dots)*maxdots); 6191 if(dots == NULL) { 6192 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 6193 exit(255); 6194 } 6195 } 6196 if( pgex->flags & GEXF_JLINE ) { 6197 for(i=0; i<2; i++) { 6198 apcv[0][i] = pge->bkwd->fpoints[i][2]; 6199 apcv[1][i] = nge->fpoints[i][2]; 6200 dots[ndots].p[i] = pge->fpoints[i][2]; 6201 } 6202 ndots++; 6203 for(i=0; i<ndots; i++) { 6204 avsd2 = fdotsegdist2(apcv, dots[i].p); 6205 if(avsd2 > CVEPS2) 6206 break; 6207 } 6208 if(i<ndots) { /* failed to join */ 6209 if(ISDBG(FCONCISE)) 6210 fprintf(stderr, "failed to join prev %p ", pge); 6211 ndots--; 6212 pgex->flags &= ~GEXF_JLINE; 6213 } else { 6214 pge = pge->bkwd; 6215 if(pge == nge) { 6216 if(ISDBG(FCONCISE)) 6217 fprintf(stderr, "intersected at prev %p ", pge); 6218 break; /* oops, tried to self-intersect */ 6219 } 6220 } 6221 } else if(ISDBG(FCONCISE)) 6222 fprintf(stderr, "(p=%p) ", pge); 6223 6224 if( ngex->flags & GEXF_JLINE ) { 6225 for(i=0; i<2; i++) { 6226 apcv[0][i] = pge->fpoints[i][2]; /* pge points before the 1st segment */ 6227 apcv[1][i] = nge->frwd->fpoints[i][2]; 6228 dots[ndots].p[i] = nge->fpoints[i][2]; 6229 } 6230 ndots++; 6231 for(i=0; i<ndots; i++) { 6232 avsd2 = fdotsegdist2(apcv, dots[i].p); 6233 if(avsd2 > CVEPS2) 6234 break; 6235 } 6236 if(i<ndots) { /* failed to join */ 6237 if(ISDBG(FCONCISE)) 6238 fprintf(stderr, "failed to join next %p ", nge->frwd); 6239 ndots--; 6240 ngex->flags &= ~GEXF_JLINE; 6241 } else { 6242 nge = nge->frwd; 6243 } 6244 } else if(ISDBG(FCONCISE)) 6245 fprintf(stderr, "(n=%p) ", nge); 6246 } 6247 6248 pge = pge->frwd; /* now the limits are pge...nge inclusive */ 6249 if(pge == nge) /* a deeply perversive contour */ 6250 break; 6251 6252 if(ISDBG(FCONCISE)) { 6253 fprintf(stderr, "\nin %s joined LINE %p-%p from\n", g->name, pge, nge); 6254 dumppaths(g, pge, nge); 6255 } 6256 pge->type = GE_LINE; 6257 for(i=0; i<2; i++) { 6258 pge->fpoints[i][2] = nge->fpoints[i][2]; 6259 } 6260 fnormalizege(pge); 6261 X_CON_F(pge) &= ~GEXF_JLINE; 6262 6263 ge = pge; 6264 for(ige = pge->frwd; ; ige = pge->frwd) { 6265 if(ige == pge) { 6266 fprintf(stderr, "WARNING: assertion in %s line %d, please report it to the ttf2pt1 project\n", 6267 __FILE__, __LINE__); 6268 free(dots); 6269 return; 6270 } 6271 if(startge == ige) 6272 startge = pge; 6273 free(ige->ext); 6274 freethisge(ige); 6275 if(ige == nge) 6276 break; 6277 } 6278 next2: 6279 ge = ge->frwd; 6280 if(ge == startge) 6281 break; 6282 } 6283 6284 free(dots); 6285 } 6286 6287 /* force conciseness: substitute 2 or more curves going in the 6288 ** same quadrant with one curve 6289 ** in floating point 6290 */ 6291 6292 void 6293 fforceconcise( 6294 GLYPH * g 6295 ) 6296 { 6297 6298 GENTRY *ge, *nge, *endge, *xge; 6299 6300 assertisfloat(g, "enforcing conciseness"); 6301 6302 fdelsmall(g, 0.05); 6303 assertpath(g->entries, __FILE__, __LINE__, g->name); 6304 6305 if(ISDBG(FCONCISE)) 6306 dumppaths(g, NULL, NULL); 6307 6308 /* collect more information about each gentry and their joints */ 6309 for (ge = g->entries; ge != 0; ge = ge->next) 6310 if (ge->type == GE_CURVE || ge->type == GE_LINE) 6311 fnormalizege(ge); 6312 6313 for (ge = g->entries; ge != 0; ge = ge->next) 6314 if (ge->type == GE_CURVE || ge->type == GE_LINE) { 6315 alloc_gex_con(ge); 6316 fanalyzege(ge); 6317 } 6318 6319 /* see what we can do about joining */ 6320 for (ge = g->entries; ge != 0; ge = ge->next) 6321 if (ge->type == GE_CURVE || ge->type == GE_LINE) 6322 fanalyzejoint(ge); 6323 6324 /* now do the joining */ 6325 for (ge = g->entries; ge != 0; ge = ge->next) 6326 if(ge->type == GE_MOVE) 6327 fconcisecontour(g, ge->next); 6328 6329 for (ge = g->entries; ge != 0; ge = ge->next) 6330 if (ge->type == GE_CURVE || ge->type == GE_LINE) 6331 free(ge->ext); 6332 } 6333 6334 void 6335 print_glyph( 6336 int glyphno 6337 ) 6338 { 6339 GLYPH *g; 6340 GENTRY *ge; 6341 int x = 0, y = 0; 6342 int i; 6343 int grp, lastgrp= -1; 6344 6345 if(ISDBG(FCONCISE) && glyphno == 0) { 6346 fprintf(stderr, "Guessed curves: bad %d/%d good %d/%d\n", 6347 gbadcv, gbadcvdots, ggoodcv, ggoodcvdots); 6348 } 6349 6350 g = &glyph_list[glyphno]; 6351 6352 fprintf(pfa_file, "/%s { \n", g->name); 6353 6354 /* consider widths >MAXLEGALWIDTH as bugs */ 6355 if( g->scaledwidth <= MAXLEGALWIDTH ) { 6356 fprintf(pfa_file, "0 %d hsbw\n", g->scaledwidth); 6357 } else { 6358 fprintf(pfa_file, "0 1000 hsbw\n"); 6359 WARNING_2 fprintf(stderr, "glyph %s: width %d seems to be buggy, set to 1000\n", 6360 g->name, g->scaledwidth); 6361 } 6362 6363 #if 0 6364 fprintf(pfa_file, "%% contours: "); 6365 for (i = 0; i < g->ncontours; i++) 6366 fprintf(pfa_file, "%s(%d,%d) ", (g->contours[i].direction == DIR_OUTER ? "out" : "in"), 6367 g->contours[i].xofmin, g->contours[i].ymin); 6368 fprintf(pfa_file, "\n"); 6369 6370 if (g->rymin < 5000) 6371 fprintf(pfa_file, "%d lower%s\n", g->rymin, (g->flatymin ? "flat" : "curve")); 6372 if (g->rymax > -5000) 6373 fprintf(pfa_file, "%d upper%s\n", g->rymax, (g->flatymax ? "flat" : "curve")); 6374 #endif 6375 6376 if (g->hstems) 6377 for (i = 0; i < g->nhs; i += 2) { 6378 if (g->hstems[i].flags & ST_3) { 6379 fprintf(pfa_file, "%d %d %d %d %d %d hstem3\n", 6380 g->hstems[i].value, 6381 g->hstems[i + 1].value - g->hstems[i].value, 6382 g->hstems[i + 2].value, 6383 g->hstems[i + 3].value - g->hstems[i + 2].value, 6384 g->hstems[i + 4].value, 6385 g->hstems[i + 5].value - g->hstems[i + 4].value 6386 ); 6387 i += 4; 6388 } else { 6389 fprintf(pfa_file, "%d %d hstem\n", g->hstems[i].value, 6390 g->hstems[i + 1].value - g->hstems[i].value); 6391 } 6392 } 6393 6394 if (g->vstems) 6395 for (i = 0; i < g->nvs; i += 2) { 6396 if (g->vstems[i].flags & ST_3) { 6397 fprintf(pfa_file, "%d %d %d %d %d %d vstem3\n", 6398 g->vstems[i].value, 6399 g->vstems[i + 1].value - g->vstems[i].value, 6400 g->vstems[i + 2].value, 6401 g->vstems[i + 3].value - g->vstems[i + 2].value, 6402 g->vstems[i + 4].value, 6403 g->vstems[i + 5].value - g->vstems[i + 4].value 6404 ); 6405 i += 4; 6406 } else { 6407 fprintf(pfa_file, "%d %d vstem\n", g->vstems[i].value, 6408 g->vstems[i + 1].value - g->vstems[i].value); 6409 } 6410 } 6411 6412 for (ge = g->entries; ge != 0; ge = ge->next) { 6413 if(g->nsg>0) { 6414 grp=ge->stemid; 6415 if(grp >= 0 && grp != lastgrp) { 6416 fprintf(pfa_file, "%d 4 callsubr\n", grp+g->firstsubr); 6417 lastgrp=grp; 6418 } 6419 } 6420 6421 switch (ge->type) { 6422 case GE_MOVE: 6423 if (absolute) 6424 fprintf(pfa_file, "%d %d amoveto\n", ge->ix3, ge->iy3); 6425 else 6426 rmoveto(ge->ix3 - x, ge->iy3 - y); 6427 if (0) 6428 fprintf(stderr, "Glyph %s: print moveto(%d, %d)\n", 6429 g->name, ge->ix3, ge->iy3); 6430 x = ge->ix3; 6431 y = ge->iy3; 6432 break; 6433 case GE_LINE: 6434 if (absolute) 6435 fprintf(pfa_file, "%d %d alineto\n", ge->ix3, ge->iy3); 6436 else 6437 rlineto(ge->ix3 - x, ge->iy3 - y); 6438 x = ge->ix3; 6439 y = ge->iy3; 6440 break; 6441 case GE_CURVE: 6442 if (absolute) 6443 fprintf(pfa_file, "%d %d %d %d %d %d arcurveto\n", 6444 ge->ix1, ge->iy1, ge->ix2, ge->iy2, ge->ix3, ge->iy3); 6445 else 6446 rrcurveto(ge->ix1 - x, ge->iy1 - y, 6447 ge->ix2 - ge->ix1, ge->iy2 - ge->iy1, 6448 ge->ix3 - ge->ix2, ge->iy3 - ge->iy2); 6449 x = ge->ix3; 6450 y = ge->iy3; 6451 break; 6452 case GE_PATH: 6453 closepath(); 6454 break; 6455 default: 6456 WARNING_1 fprintf(stderr, "**** Glyph %s: unknown entry type '%c'\n", 6457 g->name, ge->type); 6458 break; 6459 } 6460 } 6461 6462 fprintf(pfa_file, "endchar } ND\n"); 6463 } 6464 6465 /* print the subroutines for this glyph, returns the number of them */ 6466 int 6467 print_glyph_subs( 6468 int glyphno, 6469 int startid /* start numbering subroutines from this id */ 6470 ) 6471 { 6472 GLYPH *g; 6473 int i, grp; 6474 6475 g = &glyph_list[glyphno]; 6476 6477 if(!hints || !subhints || g->nsg<1) 6478 return 0; 6479 6480 g->firstsubr=startid; 6481 6482 #if 0 6483 fprintf(pfa_file, "%% %s %d\n", g->name, g->nsg); 6484 #endif 6485 for(grp=0; grp<g->nsg; grp++) { 6486 fprintf(pfa_file, "dup %d {\n", startid++); 6487 for(i= (grp==0)? 0 : g->nsbs[grp-1]; i<g->nsbs[grp]; i++) 6488 fprintf(pfa_file, "\t%d %d %cstem\n", g->sbstems[i].low, 6489 g->sbstems[i].high-g->sbstems[i].low, 6490 g->sbstems[i].isvert ? 'v' : 'h'); 6491 fprintf(pfa_file, "\treturn\n\t} NP\n"); 6492 } 6493 6494 return g->nsg; 6495 } 6496 6497 void 6498 print_glyph_metrics( 6499 FILE *afm_file, 6500 int code, 6501 int glyphno 6502 ) 6503 { 6504 GLYPH *g; 6505 6506 g = &glyph_list[glyphno]; 6507 6508 if(transform) 6509 fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n", 6510 code, g->scaledwidth, g->name, 6511 iscale(g->xMin), iscale(g->yMin), iscale(g->xMax), iscale(g->yMax)); 6512 else 6513 fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n", 6514 code, g->scaledwidth, g->name, 6515 g->xMin, g->yMin, g->xMax, g->yMax); 6516 6517 } 6518 6519 void 6520 print_glyph_metrics_ufm( 6521 FILE *ufm_file, 6522 int code, 6523 int glyphno 6524 ) 6525 { 6526 GLYPH *g; 6527 6528 g = &glyph_list[glyphno]; 6529 6530 fprintf(ufm_file, "U %d ; WX %d ; N %s ; G %d ;\n", 6531 code, g->scaledwidth, g->name, glyphno); 6532 } 6533 /* 6534 SB: 6535 An important note about the BlueValues. 6536 6537 The Adobe documentation says that the maximal width of a Blue zone 6538 is connected to the value of BlueScale, which is by default 0.039625. 6539 The BlueScale value defines, at which point size the overshoot 6540 suppression be disabled. 6541 6542 The formula for it that is given in the manual is: 6543 6544 BlueScale=point_size/240, for a 300dpi device 6545 6546 that makes us wonder what is this 240 standing for. Incidentally 6547 240=72*1000/300, where 72 is the relation between inches and points, 6548 1000 is the size of the glyph matrix, and 300dpi is the resolution of 6549 the output device. Knowing that we can recalculate the formula for 6550 the font size in pixels rather than points: 6551 6552 BlueScale=pixel_size/1000 6553 6554 That looks a lot simpler than the original formula, does not it ? 6555 And the limitation about the maximal width of zone also looks 6556 a lot simpler after the transformation: 6557 6558 max_width < 1000/pixel_size 6559 6560 that ensures that even at the maximal pixel size when the overshoot 6561 suppression is disabled the zone width will be less than one pixel. 6562 This is important, failure to comply to this limit will result in 6563 really ugly fonts (been there, done that). But knowing the formula 6564 for the pixel width, we see that in fact we can use the maximal width 6565 of 24, not 23 as specified in the manual. 6566 6567 */ 6568 6569 #define MAXBLUEWIDTH (24) 6570 6571 /* 6572 * Find the indexes of the most frequent values 6573 * in the hystogram, sort them in ascending order, and save which one 6574 * was the best one (if asked). 6575 * Returns the number of values found (may be less than maximal because 6576 * we ignore the zero values) 6577 */ 6578 6579 #define MAXHYST (2000) /* size of the hystogram */ 6580 #define HYSTBASE 500 6581 6582 static int 6583 besthyst( 6584 int *hyst, /* the hystogram */ 6585 int base, /* the base point of the hystogram */ 6586 int *best, /* the array for indexes of best values */ 6587 int nbest, /* its allocated size */ 6588 int width, /* minimal difference between indexes */ 6589 int *bestindp /* returned top point */ 6590 ) 6591 { 6592 unsigned char hused[MAXHYST / 8 + 1]; 6593 int i, max, j, w, last = 0; 6594 int nf = 0; 6595 6596 width--; 6597 6598 memset(hused, 0 , sizeof hused); 6599 6600 max = 1; 6601 for (i = 0; i < nbest && max != 0; i++) { 6602 best[i] = 0; 6603 max = 0; 6604 for (j = 1; j < MAXHYST - 1; j++) { 6605 w = hyst[j]; 6606 6607 if (w > max && (hused[j>>3] & (1 << (j & 0x07))) == 0) { 6608 best[i] = j; 6609 max = w; 6610 } 6611 } 6612 if (max != 0) { 6613 if (max < last/2) { 6614 /* do not pick the too low values */ 6615 break; 6616 } 6617 for (j = best[i] - width; j <= best[i] + width; j++) { 6618 if (j >= 0 && j < MAXHYST) 6619 hused[j >> 3] |= (1 << (j & 0x07)); 6620 } 6621 last = max; 6622 best[i] -= base; 6623 nf = i + 1; 6624 } 6625 } 6626 6627 if (bestindp) 6628 *bestindp = best[0]; 6629 6630 /* sort the indexes in ascending order */ 6631 for (i = 0; i < nf; i++) { 6632 for (j = i + 1; j < nf; j++) 6633 if (best[j] < best[i]) { 6634 w = best[i]; 6635 best[i] = best[j]; 6636 best[j] = w; 6637 } 6638 } 6639 6640 return nf; 6641 } 6642 6643 /* 6644 * Find the next best Blue zone in the hystogram. 6645 * Return the weight of the found zone. 6646 */ 6647 6648 static int 6649 bestblue( 6650 short *zhyst, /* the zones hystogram */ 6651 short *physt, /* the points hystogram */ 6652 short *ozhyst, /* the other zones hystogram */ 6653 int *bluetab /* where to put the found zone */ 6654 ) 6655 { 6656 int i, j, w, max, ind, first, last; 6657 6658 /* find the highest point in the zones hystogram */ 6659 /* if we have a plateau, take its center */ 6660 /* if we have multiple peaks, take the first one */ 6661 6662 max = -1; 6663 first = last = -10; 6664 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) { 6665 w = zhyst[i]; 6666 if (w > max) { 6667 first = last = i; 6668 max = w; 6669 } else if (w == max) { 6670 if (last == i - 1) 6671 last = i; 6672 } 6673 } 6674 ind = (first + last) / 2; 6675 6676 if (max == 0) /* no zones left */ 6677 return 0; 6678 6679 /* now we reuse `first' and `last' as inclusive borders of the zone */ 6680 first = ind; 6681 last = ind + (MAXBLUEWIDTH - 1); 6682 6683 /* our maximal width is far too big, so we try to make it narrower */ 6684 w = max; 6685 j = (w & 1); /* a pseudo-random bit */ 6686 while (1) { 6687 while (physt[first] == 0) 6688 first++; 6689 while (physt[last] == 0) 6690 last--; 6691 if (last - first < (MAXBLUEWIDTH * 2 / 3) || (max - w) * 10 > max) 6692 break; 6693 6694 if (physt[first] < physt[last] 6695 || physt[first] == physt[last] && j) { 6696 if (physt[first] * 20 > w) /* if weight is >5%, 6697 * stop */ 6698 break; 6699 w -= physt[first]; 6700 first++; 6701 j = 0; 6702 } else { 6703 if (physt[last] * 20 > w) /* if weight is >5%, 6704 * stop */ 6705 break; 6706 w -= physt[last]; 6707 last--; 6708 j = 1; 6709 } 6710 } 6711 6712 /* save our zone */ 6713 bluetab[0] = first - HYSTBASE; 6714 bluetab[1] = last - HYSTBASE; 6715 6716 /* invalidate all the zones overlapping with this one */ 6717 /* the constant of 2 is determined by the default value of BlueFuzz */ 6718 for (i = first - (MAXBLUEWIDTH - 1) - 2; i <= last + 2; i++) 6719 if (i >= 0 && i < MAXHYST) { 6720 zhyst[i] = 0; 6721 ozhyst[i] = 0; 6722 } 6723 return w; 6724 } 6725 6726 /* 6727 * Try to find the Blue Values, bounding box and italic angle 6728 */ 6729 6730 void 6731 findblues(void) 6732 { 6733 /* hystograms for upper and lower zones */ 6734 short hystl[MAXHYST]; 6735 short hystu[MAXHYST]; 6736 short zuhyst[MAXHYST]; 6737 short zlhyst[MAXHYST]; 6738 int nchars; 6739 int i, j, k, w, max; 6740 GENTRY *ge; 6741 GLYPH *g; 6742 double ang; 6743 6744 /* find the lowest and highest points of glyphs */ 6745 /* and by the way build the values for FontBBox */ 6746 /* and build the hystogram for the ItalicAngle */ 6747 6748 /* re-use hystl for the hystogram of italic angle */ 6749 6750 bbox[0] = bbox[1] = 5000; 6751 bbox[2] = bbox[3] = -5000; 6752 6753 for (i = 0; i < MAXHYST; i++) 6754 hystl[i] = 0; 6755 6756 nchars = 0; 6757 6758 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { 6759 if (g->flags & GF_USED) { 6760 nchars++; 6761 6762 g->rymin = 5000; 6763 g->rymax = -5000; 6764 for (ge = g->entries; ge != 0; ge = ge->next) { 6765 if (ge->type == GE_LINE) { 6766 6767 j = ge->iy3 - ge->prev->iy3; 6768 k = ge->ix3 - ge->prev->ix3; 6769 if (j > 0) 6770 ang = atan2(-k, j) * 180.0 / M_PI; 6771 else 6772 ang = atan2(k, -j) * 180.0 / M_PI; 6773 6774 k /= 100; 6775 j /= 100; 6776 if (ang > -45.0 && ang < 45.0) { 6777 /* 6778 * be careful to not overflow 6779 * the counter 6780 */ 6781 hystl[HYSTBASE + (int) (ang * 10.0)] += (k * k + j * j) / 4; 6782 } 6783 if (ge->iy3 == ge->prev->iy3) { 6784 if (ge->iy3 <= g->rymin) { 6785 g->rymin = ge->iy3; 6786 g->flatymin = 1; 6787 } 6788 if (ge->iy3 >= g->rymax) { 6789 g->rymax = ge->iy3; 6790 g->flatymax = 1; 6791 } 6792 } else { 6793 if (ge->iy3 < g->rymin) { 6794 g->rymin = ge->iy3; 6795 g->flatymin = 0; 6796 } 6797 if (ge->iy3 > g->rymax) { 6798 g->rymax = ge->iy3; 6799 g->flatymax = 0; 6800 } 6801 } 6802 } else if (ge->type == GE_CURVE) { 6803 if (ge->iy3 < g->rymin) { 6804 g->rymin = ge->iy3; 6805 g->flatymin = 0; 6806 } 6807 if (ge->iy3 > g->rymax) { 6808 g->rymax = ge->iy3; 6809 g->flatymax = 0; 6810 } 6811 } 6812 if (ge->type == GE_LINE || ge->type == GE_CURVE) { 6813 if (ge->ix3 < bbox[0]) 6814 bbox[0] = ge->ix3; 6815 if (ge->ix3 > bbox[2]) 6816 bbox[2] = ge->ix3; 6817 if (ge->iy3 < bbox[1]) 6818 bbox[1] = ge->iy3; 6819 if (ge->iy3 > bbox[3]) 6820 bbox[3] = ge->iy3; 6821 } 6822 } 6823 } 6824 } 6825 6826 /* get the most popular angle */ 6827 max = 0; 6828 w = 0; 6829 for (i = 0; i < MAXHYST; i++) { 6830 if (hystl[i] > w) { 6831 w = hystl[i]; 6832 max = i; 6833 } 6834 } 6835 ang = (double) (max - HYSTBASE) / 10.0; 6836 WARNING_2 fprintf(stderr, "Guessed italic angle: %f\n", ang); 6837 if (italic_angle == 0.0) 6838 italic_angle = ang; 6839 6840 /* build the hystogram of the lower points */ 6841 for (i = 0; i < MAXHYST; i++) 6842 hystl[i] = 0; 6843 6844 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { 6845 if ((g->flags & GF_USED) 6846 && g->rymin + HYSTBASE >= 0 && g->rymin < MAXHYST - HYSTBASE) { 6847 hystl[g->rymin + HYSTBASE]++; 6848 } 6849 } 6850 6851 /* build the hystogram of the upper points */ 6852 for (i = 0; i < MAXHYST; i++) 6853 hystu[i] = 0; 6854 6855 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { 6856 if ((g->flags & GF_USED) 6857 && g->rymax + HYSTBASE >= 0 && g->rymax < MAXHYST - HYSTBASE) { 6858 hystu[g->rymax + HYSTBASE]++; 6859 } 6860 } 6861 6862 /* build the hystogram of all the possible lower zones with max width */ 6863 for (i = 0; i < MAXHYST; i++) 6864 zlhyst[i] = 0; 6865 6866 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) { 6867 for (j = 0; j < MAXBLUEWIDTH; j++) 6868 zlhyst[i] += hystl[i + j]; 6869 } 6870 6871 /* build the hystogram of all the possible upper zones with max width */ 6872 for (i = 0; i < MAXHYST; i++) 6873 zuhyst[i] = 0; 6874 6875 for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) { 6876 for (j = 0; j < MAXBLUEWIDTH; j++) 6877 zuhyst[i] += hystu[i + j]; 6878 } 6879 6880 /* find the baseline */ 6881 w = bestblue(zlhyst, hystl, zuhyst, &bluevalues[0]); 6882 if (0) 6883 fprintf(stderr, "BaselineBlue zone %d%% %d...%d\n", w * 100 / nchars, 6884 bluevalues[0], bluevalues[1]); 6885 6886 if (w == 0) /* no baseline, something weird */ 6887 return; 6888 6889 /* find the upper zones */ 6890 for (nblues = 2; nblues < 14; nblues += 2) { 6891 w = bestblue(zuhyst, hystu, zlhyst, &bluevalues[nblues]); 6892 6893 if (0) 6894 fprintf(stderr, "Blue zone %d%% %d...%d\n", w * 100 / nchars, 6895 bluevalues[nblues], bluevalues[nblues+1]); 6896 6897 if (w * 20 < nchars) 6898 break; /* don't save this zone */ 6899 } 6900 6901 /* find the lower zones */ 6902 for (notherb = 0; notherb < 10; notherb += 2) { 6903 w = bestblue(zlhyst, hystl, zuhyst, &otherblues[notherb]); 6904 6905 if (0) 6906 fprintf(stderr, "OtherBlue zone %d%% %d...%d\n", w * 100 / nchars, 6907 otherblues[notherb], otherblues[notherb+1]); 6908 6909 6910 if (w * 20 < nchars) 6911 break; /* don't save this zone */ 6912 } 6913 6914 } 6915 6916 /* 6917 * Find the actual width of the glyph and modify the 6918 * description to reflect it. Not guaranteed to do 6919 * any good, may make character spacing too wide. 6920 */ 6921 6922 void 6923 docorrectwidth(void) 6924 { 6925 int i; 6926 GENTRY *ge; 6927 GLYPH *g; 6928 int xmin, xmax; 6929 int maxwidth, minsp; 6930 6931 /* enforce this minimal spacing, 6932 * we limit the amount of the enforced spacing to avoid 6933 * spacing the bold wonts too widely 6934 */ 6935 minsp = (stdhw>60 || stdhw<10)? 60 : stdhw; 6936 6937 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { 6938 g->oldwidth=g->scaledwidth; /* save the old width, will need for AFM */ 6939 6940 if (correctwidth && g->flags & GF_USED) { 6941 xmin = 5000; 6942 xmax = -5000; 6943 for (ge = g->entries; ge != 0; ge = ge->next) { 6944 if (ge->type != GE_LINE && ge->type != GE_CURVE) 6945 continue; 6946 6947 if (ge->ix3 <= xmin) { 6948 xmin = ge->ix3; 6949 } 6950 if (ge->ix3 >= xmax) { 6951 xmax = ge->ix3; 6952 } 6953 } 6954 6955 maxwidth=xmax+minsp; 6956 if( g->scaledwidth < maxwidth ) { 6957 g->scaledwidth = maxwidth; 6958 WARNING_3 fprintf(stderr, "glyph %s: extended from %d to %d\n", 6959 g->name, g->oldwidth, g->scaledwidth ); 6960 } 6961 } 6962 } 6963 6964 } 6965 6966 /* 6967 * Try to find the typical stem widths 6968 */ 6969 6970 void 6971 stemstatistics(void) 6972 { 6973 #define MINDIST 10 /* minimal distance between the widths */ 6974 int hyst[MAXHYST+MINDIST*2]; 6975 int best[12]; 6976 int i, j, k, w; 6977 int nchars; 6978 int ns; 6979 STEM *s; 6980 GLYPH *g; 6981 6982 /* start with typical stem width */ 6983 6984 nchars=0; 6985 6986 /* build the hystogram of horizontal stem widths */ 6987 memset(hyst, 0, sizeof hyst); 6988 6989 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { 6990 if (g->flags & GF_USED) { 6991 nchars++; 6992 s = g->hstems; 6993 for (j = 0; j < g->nhs; j += 2) { 6994 if ((s[j].flags | s[j + 1].flags) & ST_END) 6995 continue; 6996 w = s[j + 1].value - s[j].value+1; 6997 if(w==20) /* split stems should not be counted */ 6998 continue; 6999 if (w > 0 && w < MAXHYST - 1) { 7000 /* 7001 * handle some fuzz present in 7002 * converted fonts 7003 */ 7004 hyst[w+MINDIST] += MINDIST-1; 7005 for(k=1; k<MINDIST-1; k++) { 7006 hyst[w+MINDIST + k] += MINDIST-1-k; 7007 hyst[w+MINDIST - k] += MINDIST-1-k; 7008 } 7009 } 7010 } 7011 } 7012 } 7013 7014 /* find 12 most frequent values */ 7015 ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdhw); 7016 7017 /* store data in stemsnaph */ 7018 for (i = 0; i < ns; i++) 7019 stemsnaph[i] = best[i]; 7020 if (ns < 12) 7021 stemsnaph[ns] = 0; 7022 7023 /* build the hystogram of vertical stem widths */ 7024 memset(hyst, 0, sizeof hyst); 7025 7026 for (i = 0, g = glyph_list; i < numglyphs; i++, g++) { 7027 if (g->flags & GF_USED) { 7028 s = g->vstems; 7029 for (j = 0; j < g->nvs; j += 2) { 7030 if ((s[j].flags | s[j + 1].flags) & ST_END) 7031 continue; 7032 w = s[j + 1].value - s[j].value+1; 7033 if (w > 0 && w < MAXHYST - 1) { 7034 /* 7035 * handle some fuzz present in 7036 * converted fonts 7037 */ 7038 hyst[w+MINDIST] += MINDIST-1; 7039 for(k=1; k<MINDIST-1; k++) { 7040 hyst[w+MINDIST + k] += MINDIST-1-k; 7041 hyst[w+MINDIST - k] += MINDIST-1-k; 7042 } 7043 } 7044 } 7045 } 7046 } 7047 7048 /* find 12 most frequent values */ 7049 ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdvw); 7050 7051 /* store data in stemsnaph */ 7052 for (i = 0; i < ns; i++) 7053 stemsnapv[i] = best[i]; 7054 if (ns < 12) 7055 stemsnapv[ns] = 0; 7056 7057 #undef MINDIST 7058 } 7059 7060 /* 7061 * SB 7062 * A funny thing: TTF paths are going in reverse direction compared 7063 * to Type1. So after all (because the rest of logic uses TTF 7064 * path directions) we have to reverse the paths. 7065 * 7066 * It was a big headache to discover that. 7067 */ 7068 7069 /* works on both int and float paths */ 7070 7071 void 7072 reversepathsfromto( 7073 GENTRY * from, 7074 GENTRY * to 7075 ) 7076 { 7077 GENTRY *ge, *nge, *pge; 7078 GENTRY *cur, *next; 7079 int i, n, ilast[2]; 7080 double flast[2], f; 7081 7082 for (ge = from; ge != 0 && ge != to; ge = ge->next) { 7083 if(ge->type == GE_LINE || ge->type == GE_CURVE) { 7084 if (ISDBG(REVERSAL)) 7085 fprintf(stderr, "reverse path 0x%x <- 0x%x, 0x%x\n", ge, ge->prev, ge->bkwd); 7086 7087 /* cut out the path itself */ 7088 pge = ge->prev; /* GE_MOVE */ 7089 if (pge == 0) { 7090 fprintf(stderr, "**! No MOVE before line !!! Fatal. ****\n"); 7091 exit(1); 7092 } 7093 nge = ge->bkwd->next; /* GE_PATH */ 7094 pge->next = nge; 7095 nge->prev = pge; 7096 ge->bkwd->next = 0; /* mark end of chain */ 7097 7098 /* remember the starting point */ 7099 if(ge->flags & GEF_FLOAT) { 7100 flast[0] = pge->fx3; 7101 flast[1] = pge->fy3; 7102 } else { 7103 ilast[0] = pge->ix3; 7104 ilast[1] = pge->iy3; 7105 } 7106 7107 /* then reinsert them in backwards order */ 7108 for(cur = ge; cur != 0; cur = next ) { 7109 next = cur->next; /* or addgeafter() will screw it up */ 7110 if(cur->flags & GEF_FLOAT) { 7111 for(i=0; i<2; i++) { 7112 /* reverse the direction of path element */ 7113 f = cur->fpoints[i][0]; 7114 cur->fpoints[i][0] = cur->fpoints[i][1]; 7115 cur->fpoints[i][1] = f; 7116 f = flast[i]; 7117 flast[i] = cur->fpoints[i][2]; 7118 cur->fpoints[i][2] = f; 7119 } 7120 } else { 7121 for(i=0; i<2; i++) { 7122 /* reverse the direction of path element */ 7123 n = cur->ipoints[i][0]; 7124 cur->ipoints[i][0] = cur->ipoints[i][1]; 7125 cur->ipoints[i][1] = n; 7126 n = ilast[i]; 7127 ilast[i] = cur->ipoints[i][2]; 7128 cur->ipoints[i][2] = n; 7129 } 7130 } 7131 addgeafter(pge, cur); 7132 } 7133 7134 /* restore the starting point */ 7135 if(ge->flags & GEF_FLOAT) { 7136 pge->fx3 = flast[0]; 7137 pge->fy3 = flast[1]; 7138 } else { 7139 pge->ix3 = ilast[0]; 7140 pge->iy3 = ilast[1]; 7141 } 7142 7143 ge = nge; 7144 } 7145 7146 } 7147 } 7148 7149 void 7150 reversepaths( 7151 GLYPH * g 7152 ) 7153 { 7154 reversepathsfromto(g->entries, NULL); 7155 } 7156 7157 /* add a kerning pair information, scales the value */ 7158 7159 void 7160 addkernpair( 7161 unsigned id1, 7162 unsigned id2, 7163 int unscval 7164 ) 7165 { 7166 static unsigned char *bits = 0; 7167 static int lastid; 7168 GLYPH *g = &glyph_list[id1]; 7169 int i, n; 7170 struct kern *p; 7171 7172 if(unscval == 0 || id1 >= numglyphs || id2 >= numglyphs) 7173 return; 7174 7175 if( (glyph_list[id1].flags & GF_USED)==0 7176 || (glyph_list[id2].flags & GF_USED)==0 ) 7177 return; 7178 7179 if(bits == 0) { 7180 bits = calloc( BITMAP_BYTES(numglyphs), 1); 7181 if (bits == NULL) { 7182 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 7183 exit(255); 7184 } 7185 lastid = id1; 7186 } 7187 7188 if(lastid != id1) { 7189 /* refill the bitmap cache */ 7190 memset(bits, 0,BITMAP_BYTES(numglyphs)); 7191 p = g->kern; 7192 for(i=g->kerncount; i>0; i--) { 7193 n = (p++)->id; 7194 SET_BITMAP(bits, n); 7195 } 7196 lastid = id1; 7197 } 7198 7199 if(IS_BITMAP(bits, id2)) 7200 return; /* duplicate */ 7201 7202 if(g->kerncount <= g->kernalloc) { 7203 g->kernalloc += 8; 7204 p = realloc(g->kern, sizeof(struct kern) * g->kernalloc); 7205 if(p == 0) { 7206 fprintf (stderr, "** realloc failed, kerning data will be incomplete\n"); 7207 } 7208 g->kern = p; 7209 } 7210 7211 SET_BITMAP(bits, id2); 7212 p = &g->kern[g->kerncount]; 7213 p->id = id2; 7214 p->val = iscale(unscval) - (g->scaledwidth - g->oldwidth); 7215 g->kerncount++; 7216 kerning_pairs++; 7217 } 7218 7219 /* print out the kerning information */ 7220 7221 void 7222 print_kerning( 7223 FILE *afm_file 7224 ) 7225 { 7226 int i, j, n; 7227 GLYPH *g; 7228 struct kern *p; 7229 7230 if( kerning_pairs == 0 ) 7231 return; 7232 7233 fprintf(afm_file, "StartKernData\n"); 7234 fprintf(afm_file, "StartKernPairs %hd\n", kerning_pairs); 7235 7236 for(i=0; i<numglyphs; i++) { 7237 g = &glyph_list[i]; 7238 if( (g->flags & GF_USED) ==0) 7239 continue; 7240 p = g->kern; 7241 for(j=g->kerncount; j>0; j--, p++) { 7242 fprintf(afm_file, "KPX %s %s %d\n", g->name, 7243 glyph_list[ p->id ].name, p->val ); 7244 } 7245 } 7246 7247 fprintf(afm_file, "EndKernPairs\n"); 7248 fprintf(afm_file, "EndKernData\n"); 7249 } 7250 7251 7252 #if 0 7253 7254 /* 7255 ** This function is commented out because the information 7256 ** collected by it is not used anywhere else yet. Now 7257 ** it only collects the directions of contours. And the 7258 ** direction of contours gets fixed already in draw_glyf(). 7259 ** 7260 *********************************************** 7261 ** 7262 ** Here we expect that the paths are already closed. 7263 ** We also expect that the contours do not intersect 7264 ** and that curves doesn't cross any border of quadrant. 7265 ** 7266 ** Find which contours go inside which and what is 7267 ** their proper direction. Then fix the direction 7268 ** to make it right. 7269 ** 7270 */ 7271 7272 #define MAXCONT 1000 7273 7274 void 7275 fixcontours( 7276 GLYPH * g 7277 ) 7278 { 7279 CONTOUR cont[MAXCONT]; 7280 short ymax[MAXCONT]; /* the highest point */ 7281 short xofmax[MAXCONT]; /* X-coordinate of any point 7282 * at ymax */ 7283 short ymin[MAXCONT]; /* the lowest point */ 7284 short xofmin[MAXCONT]; /* X-coordinate of any point 7285 * at ymin */ 7286 short count[MAXCONT]; /* count of lines */ 7287 char dir[MAXCONT]; /* in which direction they must go */ 7288 GENTRY *start[MAXCONT], *minptr[MAXCONT], *maxptr[MAXCONT]; 7289 int ncont; 7290 int i; 7291 int dx1, dy1, dx2, dy2; 7292 GENTRY *ge, *nge; 7293 7294 /* find the contours and their most upper/lower points */ 7295 ncont = 0; 7296 ymax[0] = -5000; 7297 ymin[0] = 5000; 7298 for (ge = g->entries; ge != 0; ge = ge->next) { 7299 if (ge->type == GE_LINE || ge->type == GE_CURVE) { 7300 if (ge->iy3 > ymax[ncont]) { 7301 ymax[ncont] = ge->iy3; 7302 xofmax[ncont] = ge->ix3; 7303 maxptr[ncont] = ge; 7304 } 7305 if (ge->iy3 < ymin[ncont]) { 7306 ymin[ncont] = ge->iy3; 7307 xofmin[ncont] = ge->ix3; 7308 minptr[ncont] = ge; 7309 } 7310 } 7311 if (ge->frwd != ge->next) { 7312 start[ncont++] = ge->frwd; 7313 ymax[ncont] = -5000; 7314 ymin[ncont] = 5000; 7315 } 7316 } 7317 7318 /* determine the directions of contours */ 7319 for (i = 0; i < ncont; i++) { 7320 ge = minptr[i]; 7321 nge = ge->frwd; 7322 7323 if (ge->type == GE_CURVE) { 7324 dx1 = ge->ix3 - ge->ix2; 7325 dy1 = ge->iy3 - ge->iy2; 7326 7327 if (dx1 == 0 && dy1 == 0) { /* a pathological case */ 7328 dx1 = ge->ix3 - ge->ix1; 7329 dy1 = ge->iy3 - ge->iy1; 7330 } 7331 if (dx1 == 0 && dy1 == 0) { /* a more pathological 7332 * case */ 7333 dx1 = ge->ix3 - ge->prev->ix3; 7334 dy1 = ge->iy3 - ge->prev->iy3; 7335 } 7336 } else { 7337 dx1 = ge->ix3 - ge->prev->ix3; 7338 dy1 = ge->iy3 - ge->prev->iy3; 7339 } 7340 if (nge->type == GE_CURVE) { 7341 dx2 = ge->ix3 - nge->ix1; 7342 dy2 = ge->iy3 - nge->iy1; 7343 if (dx1 == 0 && dy1 == 0) { /* a pathological case */ 7344 dx2 = ge->ix3 - nge->ix2; 7345 dy2 = ge->iy3 - nge->iy2; 7346 } 7347 if (dx1 == 0 && dy1 == 0) { /* a more pathological 7348 * case */ 7349 dx2 = ge->ix3 - nge->ix3; 7350 dy2 = ge->iy3 - nge->iy3; 7351 } 7352 } else { 7353 dx2 = ge->ix3 - nge->ix3; 7354 dy2 = ge->iy3 - nge->iy3; 7355 } 7356 7357 /* compare angles */ 7358 cont[i].direction = DIR_INNER; 7359 if (dy1 == 0) { 7360 if (dx1 < 0) 7361 cont[i].direction = DIR_OUTER; 7362 } else if (dy2 == 0) { 7363 if (dx2 > 0) 7364 cont[i].direction = DIR_OUTER; 7365 } else if (dx2 * dy1 < dx1 * dy2) 7366 cont[i].direction = DIR_OUTER; 7367 7368 cont[i].ymin = ymin[i]; 7369 cont[i].xofmin = xofmin[i]; 7370 } 7371 7372 /* save the information that may be needed further */ 7373 g->ncontours = ncont; 7374 if (ncont > 0) { 7375 g->contours = malloc(sizeof(CONTOUR) * ncont); 7376 if (g->contours == 0) { 7377 fprintf(stderr, "***** Memory allocation error *****\n"); 7378 exit(255); 7379 } 7380 memcpy(g->contours, cont, sizeof(CONTOUR) * ncont); 7381 } 7382 } 7383 7384 #endif 7385 7386 /* 7387 * 7388 */ 7389
title
Description
Body
title
Description
Body
title
Description
Body
title
Body
| Generated: Fri Nov 28 20:08:37 2014 | Cross-referenced by PHPXref 0.7.1 |