| [ Index ] |
PHP Cross Reference of vtigercrm-6.1.0 |
[Summary view] [Print] [Text view]
1 /* 2 * Handling of the bitmapped glyphs 3 * 4 * Copyright (c) 2001 by the TTF2PT1 project 5 * Copyright (c) 2001 by Sergey Babkin 6 * 7 * see COPYRIGHT for the full copyright notice 8 */ 9 10 #include <stdio.h> 11 #include <stdlib.h> 12 #include <math.h> 13 #include "pt1.h" 14 #include "global.h" 15 16 /* possible values of limits */ 17 #define L_NONE 0 /* nothing here */ 18 #define L_ON 1 /* black is on up/right */ 19 #define L_OFF 2 /* black is on down/left */ 20 21 static int warnedhints = 0; 22 23 24 #ifdef USE_AUTOTRACE 25 #include <autotrace/autotrace.h> 26 27 /* 28 * Produce an autotraced outline from a bitmap. 29 * scale - factor to scale the sizes 30 * bmap - array of dots by lines, xsz * ysz 31 * xoff, yoff - offset of the bitmap's lower left corner 32 * from the logical position (0,0) 33 */ 34 35 static void 36 autotraced_bmp_outline( 37 GLYPH *g, 38 int scale, 39 char *bmap, 40 int xsz, 41 int ysz, 42 int xoff, 43 int yoff 44 ) 45 { 46 at_bitmap_type atb; 47 at_splines_type *atsp; 48 at_fitting_opts_type *atoptsp; 49 at_spline_list_type *slp; 50 at_spline_type *sp; 51 int i, j, k; 52 double lastx, lasty; 53 double fscale; 54 char *xbmap; 55 56 fscale = (double)scale; 57 58 /* provide a white margin around the bitmap */ 59 xbmap = malloc((ysz+2)*(xsz+2)); 60 if(xbmap == 0) { 61 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 62 exit(255); 63 } 64 memset(xbmap, 0, xsz+2); /* top margin */ 65 for(i=0, j=xsz+2; i<ysz; i++, j+=xsz+2) { 66 xbmap[j] = 0; /* left margin */ 67 memcpy(&xbmap[j+1], &bmap[xsz*(ysz-1-i)], xsz); /* a line of bitmap */ 68 xbmap[j+xsz+1] = 0; /* right margin */ 69 } 70 memset(xbmap+j, 0, xsz+2); /* bottom margin */ 71 xoff--; yoff-=2; /* compensate for the margins */ 72 73 atoptsp = at_fitting_opts_new(); 74 75 atb.width = xsz+2; 76 atb.height = ysz+2; 77 atb.np = 1; 78 atb.bitmap = xbmap; 79 80 atsp = at_splines_new(&atb, atoptsp); 81 82 lastx = lasty = -1.; 83 for(i=0; i<atsp->length; i++) { 84 slp = &atsp->data[i]; 85 #if 0 86 fprintf(stderr, "%s: contour %d: %d entries clockwise=%d color=%02X%02X%02X\n", 87 g->name, i, slp->length, slp->clockwise, slp->color.r, slp->color.g, slp->color.b); 88 #endif 89 if(slp->length == 0) 90 continue; 91 #if 0 92 if(slp->color.r + slp->color.g + slp->color.b == 0) 93 continue; 94 #endif 95 fg_rmoveto(g, fscale*(slp->data[0].v[0].x+xoff), fscale*(slp->data[0].v[0].y+yoff)); 96 for(j=0; j<slp->length; j++) { 97 #if 0 98 fprintf(stderr, " "); 99 for(k=0; k<4; k++) 100 fprintf(stderr, "(%g %g) ", 101 fscale*(slp->data[j].v[k].x+xoff), 102 fscale*(ysz-slp->data[j].v[k].y+yoff) 103 ); 104 fprintf(stderr, "\n"); 105 #endif 106 fg_rrcurveto(g, 107 fscale*(slp->data[j].v[1].x+xoff), fscale*(slp->data[j].v[1].y+yoff), 108 fscale*(slp->data[j].v[2].x+xoff), fscale*(slp->data[j].v[2].y+yoff), 109 fscale*(slp->data[j].v[3].x+xoff), fscale*(slp->data[j].v[3].y+yoff) ); 110 } 111 g_closepath(g); 112 } 113 114 at_splines_free(atsp); 115 at_fitting_opts_free(atoptsp); 116 free(xbmap); 117 } 118 119 #endif /*USE_AUTOTRACE*/ 120 121 /* an extension of gentry for description of the fragments */ 122 typedef struct gex_frag GEX_FRAG; 123 struct gex_frag { 124 /* indexes to len, the exact values and order are important */ 125 #define GEXFI_NONE -1 126 #define GEXFI_CONVEX 0 127 #define GEXFI_CONCAVE 1 128 #define GEXFI_LINE 2 /* a line with steps varying by +-1 pixel */ 129 #define GEXFI_EXACTLINE 3 /* a line with exactly the same steps */ 130 #define GEXFI_SERIF 4 /* small serifs at the ends of stemsi - must be last */ 131 #define GEXFI_COUNT 5 /* maximal index + 1 */ 132 unsigned short len[GEXFI_COUNT]; /* length of various fragment types starting here */ 133 unsigned short lenback[GEXFI_COUNT]; /* length back to the start of curve */ 134 135 signed char ixstart; /* index of the frag type that starts here */ 136 signed char ixcont; /* index of the frag type that continues here */ 137 138 short flags; 139 #define GEXFF_HLINE 0x0001 /* the exact line is longer in "horizontal" dimension */ 140 #define GEXFF_EXTR 0x0002 /* this gentry is an extremum in some direction */ 141 #define GEXFF_CIRC 0x0004 /* the joint at this gentry is for a circular curve */ 142 #define GEXFF_DRAWCURVE 0x0008 /* vect[] describes a curve to draw */ 143 #define GEXFF_DRAWLINE 0x0010 /* vect[] describes a line to draw */ 144 #define GEXFF_SPLIT 0x0020 /* is a result of splitting a line */ 145 #define GEXFF_SYMNEXT 0x0040 /* this subfrag is symmetric with next one */ 146 #define GEXFF_DONE 0x0080 /* this subfrag has been vectorized */ 147 #define GEXFF_LONG 0x0100 /* this gentry is longer than 1 pixel */ 148 149 unsigned short aidx; /* index of gentry in the array representing the contour */ 150 151 unsigned short vectlen; /* number of gentries represented by vect[] */ 152 153 /* coordinates for vectored replacement of this fragment */ 154 /* (already scaled because it's needed for curve approximation) */ 155 double vect[4 /*ref.points*/][2 /*X,Y*/]; 156 157 double bbox[2 /*X,Y*/]; /* absolute sizes of bounding box of a subfragment */ 158 159 /* used when splitting the curved frags into subfrags */ 160 GENTRY *prevsub; /* to gentries describing neighboring subfrags */ 161 GENTRY *nextsub; 162 GENTRY *ordersub; /* single-linked list describing the order of calculation */ 163 164 int sublen; /* length of this subfrag */ 165 /* the symmetry across the subfrags */ 166 int symaxis; /* the symmetry axis, with next subfrag */ 167 int symxlen; /* min length of adjacent symmetric frags */ 168 /* the symmetry within this subfrag (the axis is always diagonal) */ 169 GENTRY *symge; /* symge->i{x,y}3 is the symmetry point of symge==0 if none */ 170 171 }; 172 #define X_FRAG(ge) ((GEX_FRAG *)((ge)->ext)) 173 174 /* various interesting tables related to GEX_FRAG */ 175 static char *gxf_name[GEXFI_COUNT] = {"Convex", "Concave", "Line", "ExLine", "Serif"}; 176 static int gxf_cvk[2] = {-1, 1}; /* coefficients of concaveness */ 177 178 /* 179 * Dump the contents of X_EXT()->len and ->lenback for a contour 180 */ 181 static void 182 gex_dump_contour( 183 GENTRY *ge, 184 int clen 185 ) 186 { 187 int i, j; 188 189 for(j = 0; j < GEXFI_COUNT; j++) { 190 fprintf(stderr, "%-8s", gxf_name[j]); 191 for(i = 0; i < clen; i++, ge = ge->frwd) 192 fprintf(stderr, " %2d", X_FRAG(ge)->len[j]); 193 fprintf(stderr, " %p\n (back) ", ge); 194 for(i = 0; i < clen; i++, ge = ge->frwd) 195 fprintf(stderr, " %2d", X_FRAG(ge)->lenback[j]); 196 fprintf(stderr, "\n"); 197 } 198 } 199 200 /* 201 * Calculate values of X_EXT()->lenback[] for all entries in 202 * a contour. The contour is identified by: 203 * ge - any gentry of the contour 204 * clen - contour length 205 */ 206 207 static void 208 gex_calc_lenback( 209 GENTRY *ge, 210 int clen 211 ) 212 { 213 int i, j; 214 int end; 215 GEX_FRAG *f; 216 int len[GEXFI_COUNT]; /* length of the most recent fragment */ 217 int count[GEXFI_COUNT]; /* steps since beginning of the fragment */ 218 219 for(j = 0; j < GEXFI_COUNT; j++) 220 len[j] = count[j] = 0; 221 222 end = clen; 223 for(i = 0; i < end; i++, ge = ge->frwd) { 224 f = X_FRAG(ge); 225 for(j = 0; j < GEXFI_COUNT; j++) { 226 if(len[j] != count[j]) { 227 f->lenback[j] = count[j]++; 228 } else 229 f->lenback[j] = 0; 230 if(f->len[j] != 0) { 231 len[j] = f->len[j]; 232 count[j] = 1; /* start with the next gentry */ 233 /* if the fragment will wrap over the start, process to its end */ 234 if(i < clen && i + len[j] > end) 235 end = i + len[j]; 236 } 237 } 238 } 239 gex_dump_contour(ge, clen); 240 } 241 242 /* Limit a curve to not exceed the given coordinates 243 * at its given side 244 */ 245 246 static void 247 limcurve( 248 double curve[4][2 /*X,Y*/], 249 double lim[2 /*X,Y*/], 250 int where /* 0 - start, 3 - end */ 251 ) 252 { 253 int other = 3-where; /* the other end */ 254 int sgn[2 /*X,Y*/]; /* sign for comparison */ 255 double t, from, to, nt, t2, nt2, tt[4]; 256 double val[2 /*X,Y*/]; 257 int i; 258 259 for(i=0; i<2; i++) 260 sgn[i] = fsign(curve[other][i] - curve[where][i]); 261 262 #if 0 263 fprintf(stderr, " limit (%g,%g)-(%g,%g) at %d by (%g,%g), sgn(%d,%d)\n", 264 curve[0][0], curve[0][1], curve[3][0], curve[3][1], 265 where, lim[0], lim[1], sgn[0], sgn[1]); 266 #endif 267 /* a common special case */ 268 if( sgn[0]*(curve[where][0] - lim[0]) >= 0. 269 && sgn[1]*(curve[where][1] - lim[1]) >= 0. ) 270 return; /* nothing to do */ 271 272 if(other==0) { 273 from = 0.; 274 to = 1.; 275 } else { 276 from = 1.; 277 to = 0.; 278 } 279 #if 0 280 fprintf(stderr, "t="); 281 #endif 282 while( fabs(from-to) > 0.00001 ) { 283 t = 0.5 * (from+to); 284 t2 = t*t; 285 nt = 1.-t; 286 nt2 = nt*nt; 287 tt[0] = nt2*nt; 288 tt[1] = 3*nt2*t; 289 tt[2] = 3*nt*t2; 290 tt[3] = t*t2; 291 for(i=0; i<2; i++) 292 val[i] = curve[0][i]*tt[0] + curve[1][i]*tt[1] 293 + curve[2][i]*tt[2] + curve[3][i]*tt[3]; 294 #if 0 295 fprintf(stderr, "%g(%g,%g) ", t, val[0], val[1]); 296 #endif 297 if(fabs(val[0] - lim[0]) < 0.1 298 || fabs(val[1] - lim[1]) < 0.1) 299 break; 300 301 if(sgn[0] * (val[0] - lim[0]) < 0. 302 || sgn[1] * (val[1] - lim[1]) < 0.) 303 to = t; 304 else 305 from = t; 306 } 307 /* now t is the point of splitting */ 308 #define SPLIT(pt1, pt2) ( (pt1) + t*((pt2)-(pt1)) ) /* order is important! */ 309 for(i=0; i<2; i++) { 310 double v11, v12, v13, v21, v22, v31; /* intermediate points */ 311 312 v11 = SPLIT(curve[0][i], curve[1][i]); 313 v12 = SPLIT(curve[1][i], curve[2][i]); 314 v13 = SPLIT(curve[2][i], curve[3][i]); 315 v21 = SPLIT(v11, v12); 316 v22 = SPLIT(v12, v13); 317 v31 = SPLIT(v21, v22); 318 if(other==0) { 319 curve[1][i] = v11; 320 curve[2][i] = v21; 321 curve[3][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31; 322 } else { 323 curve[0][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31; 324 curve[1][i] = v22; 325 curve[2][i] = v13; 326 } 327 } 328 #undef SPLIT 329 #if 0 330 fprintf(stderr, "\n"); 331 #endif 332 } 333 334 /* 335 * Vectorize a subfragment of a curve fragment. All the data has been already 336 * collected by this time 337 */ 338 339 static void 340 dosubfrag( 341 GLYPH *g, 342 int fti, /* fragment type index */ 343 GENTRY *firstge, /* first gentry of fragment */ 344 GENTRY *ge, /* first gentry of subfragment */ 345 double fscale 346 ) 347 { 348 GENTRY *gel, *gei; /* last gentry of this subfrag */ 349 GEX_FRAG *f, *ff, *lf, *pf, *xf; 350 /* maximal amount of space that can be used at the beginning and the end */ 351 double fixfront[2], fixend[2]; /* fixed points - used to show direction */ 352 double mvfront[2], mvend[2]; /* movable points */ 353 double limfront[2], limend[2]; /* limit of movement for movabel points */ 354 double sympt; 355 int outfront, outend; /* the beginning/end is going outwards */ 356 int symfront, symend; /* a ready symmetric fragment is present at front/end */ 357 int drnd[2 /*X,Y*/]; /* size of the round part */ 358 int i, j, a1, a2, ndots; 359 double avg2, max2; /* squared distances */ 360 struct dot_dist *dots, *usedots; 361 362 ff = X_FRAG(firstge); 363 f = X_FRAG(ge); 364 gel = f->nextsub; 365 lf = X_FRAG(gel); 366 if(f->prevsub != 0) 367 pf = X_FRAG(f->prevsub); 368 else 369 pf = 0; 370 371 for(i=0; i<2; i++) 372 drnd[i] = gel->bkwd->ipoints[i][2] - ge->ipoints[i][2]; 373 374 if(f->prevsub==0 && f->ixcont == GEXFI_NONE) { 375 /* nothing to join with : may use the whole length */ 376 for(i = 0; i < 2; i++) 377 limfront[i] = ge->bkwd->ipoints[i][2]; 378 } else { 379 /* limit to a half */ 380 for(i = 0; i < 2; i++) 381 limfront[i] = 0.5 * (ge->ipoints[i][2] + ge->bkwd->ipoints[i][2]); 382 } 383 if( (ge->ix3 == ge->bkwd->ix3) /* vert */ 384 ^ (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3)) 385 ^ (fti == GEXFI_CONCAVE) /* counter-clockwise */ ) { 386 /* the beginning is not a flat 90-degree end */ 387 outfront = 1; 388 for(i = 0; i < 2; i++) 389 fixfront[i] = ge->frwd->ipoints[i][2]; 390 } else { 391 outfront = 0; 392 for(i = 0; i < 2; i++) 393 fixfront[i] = ge->ipoints[i][2]; 394 } 395 396 if(lf->nextsub==0 && lf->ixstart == GEXFI_NONE) { 397 /* nothing to join with : may use the whole length */ 398 for(i = 0; i < 2; i++) 399 limend[i] = gel->ipoints[i][2]; 400 } else { 401 /* limit to a half */ 402 for(i = 0; i < 2; i++) 403 limend[i] = 0.5 * (gel->ipoints[i][2] + gel->bkwd->ipoints[i][2]); 404 } 405 gei = gel->bkwd->bkwd; 406 if( (gel->ix3 == gel->bkwd->ix3) /* vert */ 407 ^ (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3)) 408 ^ (fti == GEXFI_CONVEX) /* clockwise */ ) { 409 /* the end is not a flat 90-degree end */ 410 outend = 1; 411 for(i = 0; i < 2; i++) 412 fixend[i] = gel->bkwd->bkwd->ipoints[i][2]; 413 } else { 414 outend = 0; 415 for(i = 0; i < 2; i++) 416 fixend[i] = gel->bkwd->ipoints[i][2]; 417 } 418 419 for(i = 0; i < 2; i++) { 420 fixfront[i] *= fscale; 421 limfront[i] *= fscale; 422 fixend[i] *= fscale; 423 limend[i] *= fscale; 424 } 425 426 fprintf(stderr, " %d out(%d[%d %d %d],%d[%d %d %d]) drnd(%d, %d)\n", 427 fti, 428 outfront, 429 (ge->ix3 == ge->bkwd->ix3), 430 (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3)), 431 (fti == GEXFI_CONCAVE), 432 outend, 433 (gel->ix3 == gel->bkwd->ix3), 434 (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3)), 435 (fti == GEXFI_CONVEX), 436 drnd[0], drnd[1]); 437 438 /* prepare to calculate the distances */ 439 ndots = f->sublen - 1; 440 dots = malloc(sizeof(*dots) * ndots); 441 if(dots == 0) { 442 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 443 exit(255); 444 } 445 for(i = 0, gei = ge; i < ndots; i++, gei = gei->frwd) { 446 for(a1 = 0; a1 < 2; a1++) 447 dots[i].p[a1] = fscale * gei->ipoints[a1][2]; 448 } 449 450 /* see if we can mirror a ready symmetric curve */ 451 452 /* check symmetry with the fragment before this */ 453 symfront = (pf != 0 && (pf->flags & GEXFF_SYMNEXT) && (pf->flags & GEXFF_DONE) 454 && ( outend && f->sublen <= pf->sublen 455 || ( pf->sublen == f->sublen 456 && (lf->sublen == 0 457 || ( abs(limfront[0]-limend[0]) >= abs(pf->vect[0][0]-pf->vect[3][0]) 458 && abs(limfront[1]-limend[1]) >= abs(pf->vect[0][1]-pf->vect[3][1]) )) 459 ) 460 ) 461 ); 462 /* check symmetry with the fragment after this */ 463 symend = ( (f->flags & GEXFF_SYMNEXT) && (lf->flags & GEXFF_DONE) 464 && ( outfront && f->sublen <= lf->sublen 465 || ( lf->sublen == f->sublen 466 && (pf == 0 467 || ( abs(limfront[0]-limend[0]) >= abs(lf->vect[0][0]-lf->vect[3][0]) 468 && abs(limfront[1]-limend[1]) >= abs(lf->vect[0][1]-lf->vect[3][1]) )) 469 ) 470 ) 471 ); 472 if(symfront || symend) { 473 /* mirror the symmetric neighbour subfrag */ 474 if(symfront) { 475 a1 = (ge->ix3 != ge->bkwd->ix3); /* the symmetry axis */ 476 a2 = !a1; /* the other axis (goes along the extremum gentry) */ 477 478 /* the symmetry point on a2 */ 479 sympt = fscale * 0.5 * (ge->ipoints[a2][2] + ge->bkwd->ipoints[a2][2]); 480 xf = pf; /* the symmetric fragment */ 481 } else { 482 a1 = (gel->ix3 != gel->bkwd->ix3); /* the symmetry axis */ 483 a2 = !a1; /* the other axis (goes along the extremum gentry) */ 484 485 /* the symmetry point on a2 */ 486 sympt = fscale * 0.5 * (gel->ipoints[a2][2] + gel->bkwd->ipoints[a2][2]); 487 xf = lf; /* the symmetric fragment */ 488 } 489 fprintf(stderr, " sym with %p f=%d(%p) e=%d(%p) a1=%c a2=%c sympt=%g\n", 490 xf, symfront, pf, symend, lf, 491 a1 ? 'Y': 'X', a2 ? 'Y': 'X', sympt 492 ); 493 for(i=0; i<4; i++) { 494 f->vect[3-i][a1] = xf->vect[i][a1]; 495 f->vect[3-i][a2] = sympt - (xf->vect[i][a2]-sympt); 496 } 497 if(symfront) { 498 if(outend || lf->sublen==0) 499 limcurve(f->vect, limend, 3); 500 } else { 501 if(outfront || pf == 0) 502 limcurve(f->vect, limfront, 0); 503 } 504 avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2); 505 fprintf(stderr, " avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale); 506 if(max2 <= fscale*fscale) { 507 f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE); 508 f->vectlen = f->sublen; 509 free(dots); 510 return; 511 } 512 } 513 514 if( !outfront && !outend && f->symge != 0) { 515 /* a special case: try a circle segment as an approximation */ 516 double lenfront, lenend, len, maxlen; 517 518 /* coefficient for a Bezier approximation of a circle */ 519 #define CIRCLE_FRAC 0.55 520 521 a1 = (ge->ix3 == ge->bkwd->ix3); /* get the axis along the front */ 522 a2 = !a1; /* axis along the end */ 523 524 lenfront = fixfront[a1] - limfront[a1]; 525 lenend = fixend[a2] - limend[a2]; 526 if(fabs(lenfront) < fabs(lenend)) 527 len = fabs(lenfront); 528 else 529 len = fabs(lenend); 530 531 /* make it go close to the round shape */ 532 switch(f->sublen) { 533 case 2: 534 maxlen = fscale; 535 break; 536 case 4: 537 case 6: 538 maxlen = fscale * 2.; 539 break; 540 default: 541 maxlen = fscale * abs(ge->frwd->frwd->ipoints[a1][2] 542 - ge->ipoints[a1][2]); 543 break; 544 } 545 if(len > maxlen) 546 len = maxlen; 547 548 mvfront[a1] = fixfront[a1] - fsign(lenfront) * len; 549 mvfront[a2] = limfront[a2]; 550 mvend[a2] = fixend[a2] - fsign(lenend) * len; 551 mvend[a1] = limend[a1]; 552 553 for(i=0; i<2; i++) { 554 f->vect[0][i] = mvfront[i]; 555 f->vect[3][i] = mvend[i]; 556 } 557 f->vect[1][a1] = mvfront[a1] + CIRCLE_FRAC*(mvend[a1]-mvfront[a1]); 558 f->vect[1][a2] = mvfront[a2]; 559 f->vect[2][a1] = mvend[a1]; 560 f->vect[2][a2] = mvend[a2] + CIRCLE_FRAC*(mvfront[a2]-mvend[a2]); 561 562 avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2); 563 fprintf(stderr, " avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale); 564 if(max2 <= fscale*fscale) { 565 f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE); 566 f->vectlen = f->sublen; 567 free(dots); 568 return; 569 } 570 #undef CIRCLE_FRAC 571 } 572 for(i=0; i<2; i++) { 573 f->vect[0][i] = limfront[i]; 574 f->vect[1][i] = fixfront[i]; 575 f->vect[2][i] = fixend[i]; 576 f->vect[3][i] = limend[i]; 577 } 578 usedots = dots; 579 if(outfront) { 580 usedots++; ndots--; 581 } 582 if(outend) 583 ndots--; 584 if( fcrossrayscv(f->vect, NULL, NULL) == 0) { 585 fprintf(stderr, "**** Internal error: rays must cross but don't at %p-%p\n", 586 ge, gel); 587 fprintf(stderr, " (%g, %g) (%g, %g) (%g, %g) (%g, %g)\n", 588 limfront[0], limfront[1], 589 fixfront[0], fixfront[1], 590 fixend[0], fixend[1], 591 limend[0], limend[1] 592 ); 593 dumppaths(g, NULL, NULL); 594 exit(1); 595 } else { 596 if(ndots != 0) 597 fapproxcurve(f->vect, usedots, ndots); 598 f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE); 599 f->vectlen = f->sublen; 600 } 601 free(dots); 602 } 603 604 /* 605 * Subtract a list of gentries (covered by a fragment of higher 606 * priority) from the set of fragments of a given 607 * type. 608 * 609 * An example is subtraction of the long exact line fragments 610 * from the curve fragments which get overridden. 611 */ 612 613 static void 614 frag_subtract( 615 GLYPH *g, 616 GENTRY **age, /* array of gentries for this contour */ 617 int clen, /* length of the contour */ 618 GENTRY *ge, /* first gentry to be subtracted */ 619 int slen, /* number of gentries in the list to be subtracted */ 620 int d /* type of fragments from which to subtract, as in GEXFI_... */ 621 ) 622 { 623 GENTRY *pge; 624 GEX_FRAG *f, *pf; 625 int len, i, j; 626 627 f = X_FRAG(ge); 628 len = slen; 629 630 /* check if we overlap the end of some fragment */ 631 if(f->lenback[d]) { 632 /* chop off the end of conflicting fragment */ 633 len = f->lenback[d]; 634 pge = age[(f->aidx + clen - len)%clen]; 635 pf = X_FRAG(pge); 636 if(pf->len[d] == clen+1 && pf->flags & GEXFF_CIRC) { 637 /* the conflicting fragment is self-connected */ 638 639 pf->len[d] = 0; 640 /* calculate the new value for lenback */ 641 len = clen+1 - slen; 642 for(pge = ge; len > 0; pge = pge->bkwd, len--) 643 X_FRAG(pge)->lenback[d] = len; 644 /* now pge points to the last entry of the line, 645 * which is also the new first entry of the curve 646 */ 647 X_FRAG(pge)->len[d] = clen+2 - slen; 648 /* clean lenback of gentries covered by the line */ 649 for(pge = ge->frwd, j = slen-1; j > 0; pge = pge->frwd, j--) 650 X_FRAG(pge)->lenback[d] = 0; 651 fprintf(stderr, " cut %s circular frag to %p-%p\n", 652 gxf_name[d], pge, ge); 653 gex_dump_contour(ge, clen); 654 } else { 655 /* when we chop off a piece of fragment, we leave the remaining 656 * piece(s) overlapping with the beginning and possibly the end 657 * of the line fragment under consideration 658 */ 659 fprintf(stderr, " cut %s frag at %p from len=%d to len=%d (end %p)\n", 660 gxf_name[d], pge, pf->len[d], len+1, ge); 661 j = pf->len[d] - len - 1; /* how many gentries are chopped off */ 662 pf->len[d] = len + 1; 663 i = slen - 1; 664 for(pge = ge->frwd; j > 0 && i > 0; j--, i--, pge = pge->frwd) 665 X_FRAG(pge)->lenback[d] = 0; 666 gex_dump_contour(ge, clen); 667 668 if(j != 0) { 669 /* the conflicting fragment is split in two by this line 670 * fragment, fix up its tail 671 */ 672 673 fprintf(stderr, " end of %s frag len=%d %p-", 674 gxf_name[d], j+1, pge->bkwd); 675 X_FRAG(pge->bkwd)->len[d] = j+1; /* the overlapping */ 676 for(i = 1; j > 0; j--, i++, pge = pge->frwd) 677 X_FRAG(pge)->lenback[d] = i; 678 fprintf(stderr, "%p\n", pge->bkwd); 679 gex_dump_contour(ge, clen); 680 } 681 } 682 } 683 /* check if we overlap the beginning of some fragments */ 684 i = slen-1; /* getntries remaining to consider */ 685 j = 0; /* gentries remaining in the overlapping fragment */ 686 for(pge = ge; i > 0; i--, pge = pge->frwd) { 687 if(j > 0) { 688 X_FRAG(pge)->lenback[d] = 0; 689 j--; 690 } 691 /* the beginning of one fragment may be the end of another 692 * fragment, in this case if j-- above results in 0, that will 693 * cause it to check the same gentry for the beginning 694 */ 695 if(j == 0) { 696 pf = X_FRAG(pge); 697 j = pf->len[d]; 698 if(j != 0) { 699 fprintf(stderr, " removed %s frag at %p len=%d\n", 700 gxf_name[d], pge, j); 701 gex_dump_contour(ge, clen); 702 pf->len[d] = 0; 703 j--; 704 } 705 } 706 } 707 /* pge points at the last gentry of the line fragment */ 708 if(j > 1) { /* we have the tail of a fragment left */ 709 fprintf(stderr, " end of %s frag len=%d %p-", 710 gxf_name[d], j, pge); 711 X_FRAG(pge)->len[d] = j; /* the overlapping */ 712 for(i = 0; j > 0; j--, i++, pge = pge->frwd) 713 X_FRAG(pge)->lenback[d] = i; 714 fprintf(stderr, "%p\n", pge->bkwd); 715 gex_dump_contour(ge, clen); 716 } else if(j == 1) { 717 X_FRAG(pge)->lenback[d] = 0; 718 } 719 } 720 721 /* 722 * Produce an outline from a bitmap. 723 * scale - factor to scale the sizes 724 * bmap - array of dots by lines, xsz * ysz 725 * xoff, yoff - offset of the bitmap's lower left corner 726 * from the logical position (0,0) 727 */ 728 729 void 730 bmp_outline( 731 GLYPH *g, 732 int scale, 733 char *bmap, 734 int xsz, 735 int ysz, 736 int xoff, 737 int yoff 738 ) 739 { 740 char *hlm, *vlm; /* arrays of the limits of outlines */ 741 char *amp; /* map of ambiguous points */ 742 int x, y; 743 char *ip, *op; 744 double fscale; 745 746 if(xsz==0 || ysz==0) 747 return; 748 749 #ifdef USE_AUTOTRACE 750 if(use_autotrace) { 751 autotraced_bmp_outline(g, scale, bmap, xsz, ysz, xoff, yoff); 752 return; 753 } 754 #endif /*USE_AUTOTRACE*/ 755 756 fscale = (double)scale; 757 g->flags &= ~GF_FLOAT; /* build it as int first */ 758 759 if(!warnedhints) { 760 warnedhints = 1; 761 if(hints && subhints) { 762 WARNING_2 fprintf(stderr, 763 "Use of hint substitution on bitmap fonts is not recommended\n"); 764 } 765 } 766 767 #if 0 768 printbmap(bmap, xsz, ysz, xoff, yoff); 769 #endif 770 771 /* now find the outlines */ 772 hlm=calloc( xsz, ysz+1 ); /* horizontal limits */ 773 vlm=calloc( xsz+1, ysz ); /* vertical limits */ 774 amp=calloc( xsz, ysz ); /* ambiguous points */ 775 776 if(hlm==0 || vlm==0 || amp==0) { 777 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 778 exit(255); 779 } 780 781 /* 782 * hlm and vlm represent a grid of horisontal and 783 * vertical lines. Each pixel is surrounded by the grid 784 * from all the sides. The values of [hv]lm mark the 785 * parts of grid where the pixel value switches from white 786 * to black and back. 787 */ 788 789 /* find the horizontal limits */ 790 ip=bmap; op=hlm; 791 /* 1st row */ 792 for(x=0; x<xsz; x++) { 793 if(ip[x]) 794 op[x]=L_ON; 795 } 796 ip+=xsz; op+=xsz; 797 /* internal rows */ 798 for(y=1; y<ysz; y++) { 799 for(x=0; x<xsz; x++) { 800 if(ip[x]) { 801 if(!ip[x-xsz]) 802 op[x]=L_ON; 803 } else { 804 if(ip[x-xsz]) 805 op[x]=L_OFF; 806 } 807 } 808 ip+=xsz; op+=xsz; 809 } 810 811 /* last row */ 812 ip-=xsz; 813 for(x=0; x<xsz; x++) { 814 if(ip[x]) 815 op[x]=L_OFF; 816 } 817 818 /* find the vertical limits */ 819 ip=bmap; op=vlm; 820 for(y=0; y<ysz; y++) { 821 if(ip[0]) 822 op[0]=L_ON; 823 for(x=1; x<xsz; x++) { 824 if(ip[x]) { 825 if(!ip[x-1]) 826 op[x]=L_ON; 827 } else { 828 if(ip[x-1]) 829 op[x]=L_OFF; 830 } 831 } 832 if(ip[xsz-1]) 833 op[xsz]=L_OFF; 834 ip+=xsz; op+=xsz+1; 835 } 836 837 /* 838 * Ambiguous points are the nodes of the grids 839 * that are between two white and two black pixels 840 * located in a checkerboard style. Actually 841 * there are only two patterns that may be 842 * around an ambiguous point: 843 * 844 * X|. .|X 845 * -*- -*- 846 * .|X X|. 847 * 848 * where "|" and "-" represent the grid (respectively members 849 * of vlm and hlm), "*" represents an ambiguous point 850 * and "X" and "." represent black and white pixels. 851 * 852 * If these sample pattern occur in the lower left corner 853 * of the bitmap then this ambiguous point will be 854 * located at amp[1][1] or in other words amp[1*xsz+1]. 855 * 856 * These points are named "ambiguous" because it's 857 * not easy to guess what did the font creator mean 858 * at these points. So we are going to treat them 859 * specially, doing no aggressive smoothing. 860 */ 861 862 /* find the ambiguous points */ 863 for(y=ysz-1; y>0; y--) 864 for(x=xsz-1; x>0; x--) { 865 if(bmap[y*xsz+x]) { 866 if( !bmap[y*xsz+x-1] && !bmap[y*xsz-xsz+x] && bmap[y*xsz-xsz+x-1] ) 867 amp[y*xsz+x]=1; 868 } else { 869 if( bmap[y*xsz+x-1] && bmap[y*xsz-xsz+x] && !bmap[y*xsz-xsz+x-1] ) 870 amp[y*xsz+x]=1; 871 } 872 } 873 874 #if 0 875 printlimits(hlm, vlm, amp, xsz, ysz); 876 #endif 877 878 /* generate the vectored (stepping) outline */ 879 880 while(1) { 881 int found = 0; 882 int outer; /* flag: this is an outer contour */ 883 int hor, newhor; /* flag: the current contour direction is horizontal */ 884 int dir; /* previous direction of the coordinate, 1 - L_ON, 0 - L_OFF */ 885 int startx, starty; /* start of a contour */ 886 int firstx, firsty; /* start of the current line */ 887 int newx, newy; /* new coordinates to try */ 888 char *lm, val; 889 int maxx, maxy, xor; 890 891 for(y=ysz; !found && y>0; y--) 892 for(x=0; x<xsz; x++) 893 if(hlm[y*xsz+x] > L_NONE) 894 goto foundcontour; 895 break; /* have no contours left */ 896 897 foundcontour: 898 ig_rmoveto(g, x+xoff, y+yoff); /* intermediate as int */ 899 900 startx = firstx = x; 901 starty = firsty = y; 902 903 if(hlm[y*xsz+x] == L_OFF) { 904 outer = 1; dir = 0; 905 hlm[y*xsz+x] = -hlm[y*xsz+x]; /* mark as seen */ 906 hor = 1; x++; 907 } else { 908 outer = 0; dir = 0; 909 hor = 0; y--; 910 vlm[y*(xsz+1)+x] = -vlm[y*(xsz+1)+x]; /* mark as seen */ 911 } 912 913 while(x!=startx || y!=starty) { 914 #if 0 915 printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir); 916 #endif 917 918 /* initialization common for try1 and try2 */ 919 if(hor) { 920 lm = vlm; maxx = xsz+1; maxy = ysz; newhor = 0; 921 } else { 922 lm = hlm; maxx = xsz; maxy = ysz+1; newhor = 1; 923 } 924 xor = (outer ^ hor ^ dir); 925 926 try1: 927 /* first we try to change axis, to keep the 928 * contour as long as possible 929 */ 930 931 newx = x; newy = y; 932 if(!hor && (!outer ^ dir)) 933 newx--; 934 if(hor && (!outer ^ dir)) 935 newy--; 936 937 if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy) 938 goto try2; 939 940 if(!xor) 941 val = L_ON; 942 else 943 val = L_OFF; 944 #if 0 945 printf("try 1, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx], 946 (newhor ? 'h':'v'), newx, newy); 947 #endif 948 if( lm[newy*maxx + newx] == val ) 949 goto gotit; 950 951 try2: 952 /* try to change the axis anyway */ 953 954 newx = x; newy = y; 955 if(!hor && (outer ^ dir)) 956 newx--; 957 if(hor && (outer ^ dir)) 958 newy--; 959 960 if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy) 961 goto try3; 962 963 if(xor) 964 val = L_ON; 965 else 966 val = L_OFF; 967 #if 0 968 printf("try 2, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx], 969 (newhor ? 'h':'v'), newx, newy); 970 #endif 971 if( lm[newy*maxx + newx] == val ) 972 goto gotit; 973 974 try3: 975 /* try to continue in the old direction */ 976 977 if(hor) { 978 lm = hlm; maxx = xsz; maxy = ysz+1; 979 } else { 980 lm = vlm; maxx = xsz+1; maxy = ysz; 981 } 982 newhor = hor; 983 newx = x; newy = y; 984 if(hor && dir) 985 newx--; 986 if(!hor && !dir) 987 newy--; 988 989 if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy) 990 goto badtry; 991 992 if(dir) 993 val = L_ON; 994 else 995 val = L_OFF; 996 #if 0 997 printf("try 3, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx], 998 (newhor ? 'h':'v'), newx, newy); 999 #endif 1000 if( lm[newy*maxx + newx] == val ) 1001 goto gotit; 1002 1003 badtry: 1004 fprintf(stderr, "**** Internal error in the contour detection code at (%d, %d)\n", x, y); 1005 fprintf(stderr, "glyph='%s' outer=%d hor=%d dir=%d\n", g->name, outer, hor, dir); 1006 fflush(stdout); 1007 exit(1); 1008 1009 gotit: 1010 if(hor != newhor) { /* changed direction, end the previous line */ 1011 ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */ 1012 firstx = x; firsty = y; 1013 } 1014 lm[newy*maxx + newx] = -lm[newy*maxx + newx]; 1015 hor = newhor; 1016 dir = (val == L_ON); 1017 if(newhor) 1018 x -= (dir<<1)-1; 1019 else 1020 y += (dir<<1)-1; 1021 } 1022 #if 0 1023 printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir); 1024 #endif 1025 ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */ 1026 g_closepath(g); 1027 } 1028 1029 1030 /* try to vectorize the curves and sloped lines in the bitmap */ 1031 if(vectorize) { 1032 GENTRY *ge, *pge, *cge, *loopge; 1033 int i; 1034 int skip; 1035 1036 dumppaths(g, NULL, NULL); 1037 1038 /* allocate the extensions */ 1039 for(cge=g->entries; cge!=0; cge=cge->next) { 1040 cge->ext = calloc(1, sizeof(GEX_FRAG) ); 1041 if(cge->ext == 0) { 1042 fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__); 1043 exit(255); 1044 } 1045 } 1046 1047 for(cge=g->entries; cge!=0; cge=cge->next) { 1048 if(cge->type != GE_MOVE) 1049 continue; 1050 1051 /* we've found the beginning of a contour */ 1052 { 1053 int d, vert, count, stepmore, delaystop; 1054 int vdir, hdir, fullvdir, fullhdir, len; 1055 int dx, dy, lastdx, lastdy; 1056 int k1, k2, reversal, smooth, good; 1057 int line[2 /*H,V*/], maxlen[2 /*H,V*/], minlen[2 /*H,V*/]; 1058 GENTRY **age; /* array of gentries in a contour */ 1059 int clen; /* contour length, size of ths array */ 1060 int i, j; 1061 GEX_FRAG *f; 1062 1063 /* we know that all the contours start at the top-left corner, 1064 * so at most it might be before/after the last element of 1065 * the last/first fragment 1066 */ 1067 1068 ge = cge->next; 1069 pge = ge->bkwd; 1070 if(ge->ix3 == pge->ix3) { /* a vertical line */ 1071 /* we want to start always from a horizontal line because 1072 * then we always start from top and that is quaranteed to be a 1073 * fragment boundary, so move the start point of the contour 1074 */ 1075 pge->prev->next = pge->next; 1076 pge->next->prev = pge->prev; 1077 cge->next = pge; 1078 pge->prev = cge; 1079 pge->next = ge; 1080 ge->prev = pge; 1081 ge = pge; pge = ge->bkwd; 1082 cge->ix3 = pge->ix3; cge->iy3 = pge->iy3; 1083 } 1084 1085 /* fill the array of gentries */ 1086 clen = 1; 1087 for(ge = cge->next->frwd; ge != cge->next; ge = ge->frwd) 1088 clen++; 1089 age = (GENTRY **)malloc(sizeof(*age) * clen); 1090 ge = cge->next; 1091 count = 0; 1092 do { 1093 age[count] = ge; 1094 X_FRAG(ge)->aidx = count++; 1095 1096 /* and by the way find the extremums */ 1097 for(i=0; i<2; i++) { 1098 if( isign(ge->frwd->ipoints[i][2] - ge->ipoints[i][2]) 1099 * isign(ge->bkwd->bkwd->ipoints[i][2] - ge->bkwd->ipoints[i][2]) == 1) { 1100 X_FRAG(ge)->flags |= GEXFF_EXTR; 1101 fprintf(stderr, " %s extremum at %p\n", (i?"vert":"hor"), ge); 1102 } 1103 if(abs(ge->ipoints[i][2] - ge->bkwd->ipoints[i][2]) > 1) 1104 X_FRAG(ge)->flags |= GEXFF_LONG; 1105 } 1106 1107 ge = ge->frwd; 1108 } while(ge != cge->next); 1109 1110 /* Find the serif fragments, looking as either of: 1111 * -+ | 1112 * | | 1113 * +-+ +-+ 1114 * | | 1115 * +--... +--... 1116 * with the thickness of serifs being 1 pixel. We make no 1117 * difference between serifs on vertical and horizontal stems. 1118 */ 1119 1120 ge = cge->next; 1121 do { 1122 GENTRY *nge; 1123 int pdx, pdy, ndx, ndy; 1124 1125 /* two gentries of length 1 mean a potential serif */ 1126 pge = ge->bkwd; 1127 nge = ge->frwd; 1128 1129 dx = nge->ix3 - pge->ix3; 1130 dy = nge->iy3 - pge->iy3; 1131 1132 if(abs(dx) != 1 || abs(dy) != 1) /* 2 small ones */ 1133 continue; 1134 1135 if( 1136 (!(X_FRAG(ge)->flags & GEXFF_EXTR) 1137 || !(X_FRAG(ge->bkwd)->flags & GEXFF_EXTR)) 1138 && (!(X_FRAG(ge->frwd)->flags & GEXFF_EXTR) 1139 || !(X_FRAG(ge->frwd->frwd)->flags & GEXFF_EXTR)) 1140 ) 1141 continue; /* either side must be a couple of extremums */ 1142 1143 pdx = pge->ix3 - pge->bkwd->ix3; 1144 pdy = pge->iy3 - pge->bkwd->iy3; 1145 ndx = nge->frwd->ix3 - nge->ix3; 1146 ndy = nge->frwd->iy3 - nge->iy3; 1147 1148 if(pdx*dx + pdy*dy > 0 && ndx*dx + ndy*dy > 0) 1149 continue; /* definitely not a serif but a round corner */ 1150 1151 if(abs(pdx) + abs(pdy) == 1 || abs(ndx) + abs(ndy) == 1) 1152 continue; 1153 1154 /* we've found a serif including this and next gentry */ 1155 X_FRAG(ge)->len[GEXFI_SERIF] = 2; 1156 1157 } while( (ge = ge->frwd) != cge->next ); 1158 1159 1160 /* Find the convex and concave fragments, defined as: 1161 * convex (clockwise): dy/dx <= dy0/dx0, 1162 * or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx > 0 1163 * concave (counter-clockwise): dy/dx >= dy0/dx0, 1164 * or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx < 0 1165 * 1166 * Where dx and dy are measured between the end of this gentry 1167 * and the start of the previous one (dx0 and dy0 are the same 1168 * thing calculated for the previous gentry and its previous one), 1169 * dxthis is between the end and begginning of this gentry. 1170 * 1171 * A reversal is a situation when the curve changes its direction 1172 * along the x axis, so it passes through a momentary vertical 1173 * direction. 1174 */ 1175 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1176 ge = cge->next; 1177 pge = ge->bkwd; /* the beginning of the fragment */ 1178 count = 1; 1179 lastdx = pge->ix3 - pge->bkwd->bkwd->ix3; 1180 lastdy = pge->iy3 - pge->bkwd->bkwd->iy3; 1181 1182 #define CHKCURVCONN(ge, msg) do { \ 1183 dx = (ge)->ix3 - (ge)->bkwd->bkwd->ix3; \ 1184 dy = (ge)->iy3 - (ge)->bkwd->bkwd->iy3; \ 1185 if(0 && msg) { \ 1186 fprintf(stderr, " %p: dx=%d dy=%d dx0=%d dy0=%d ", \ 1187 (ge), dx, dy, lastdx, lastdy); \ 1188 } \ 1189 k1 = X_FRAG(ge)->flags; \ 1190 k2 = X_FRAG((ge)->bkwd)->flags; \ 1191 if(0 && msg) { \ 1192 fprintf(stderr, "fl=%c%c%c%c ", \ 1193 (k1 & GEXFF_EXTR) ? 'X' : '-', \ 1194 (k1 & GEXFF_LONG) ? 'L' : '-', \ 1195 (k2 & GEXFF_EXTR) ? 'X' : '-', \ 1196 (k2 & GEXFF_LONG) ? 'L' : '-' \ 1197 ); \ 1198 } \ 1199 if( (k1 & GEXFF_EXTR) && (k2 & GEXFF_LONG) \ 1200 || (k2 & GEXFF_EXTR) && (k1 & GEXFF_LONG) ) { \ 1201 smooth = 0; \ 1202 good = reversal = -1; /* for debugging */ \ 1203 } else { \ 1204 k1 = dy * lastdx; \ 1205 k2 = lastdy * dx; \ 1206 smooth = (abs(dx)==1 || abs(dy)==1); \ 1207 good = (k1 - k2)*gxf_cvk[d] >= 0; \ 1208 if(smooth && !good) { \ 1209 reversal = (k1 == -k2 && abs((ge)->ix3 - (ge)->bkwd->ix3)==1 \ 1210 && dy*dx*gxf_cvk[d] < 0); \ 1211 } else \ 1212 reversal = 0; \ 1213 } \ 1214 if(0 && msg) { \ 1215 fprintf(stderr, "k1=%d k2=%d pge=%p count=%d %s good=%d rev=%d\n", \ 1216 k1, k2, pge, count, gxf_name[d], good, reversal); \ 1217 } \ 1218 } while(0) 1219 1220 do { 1221 CHKCURVCONN(ge, 1); 1222 1223 if(smooth && (good || reversal) ) 1224 count++; 1225 else { 1226 /* can't continue */ 1227 #if 0 1228 if(count >= 4) { /* worth remembering */ 1229 fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); 1230 } 1231 #endif 1232 X_FRAG(pge)->len[d] = count; 1233 if(smooth) { 1234 pge = ge->bkwd; 1235 count = 2; 1236 } else { 1237 pge = ge; 1238 count = 1; 1239 } 1240 } 1241 lastdx = dx; lastdy = dy; 1242 ge = ge->frwd; 1243 } while(ge != cge->next); 1244 1245 /* see if we can connect the last fragment to the first */ 1246 CHKCURVCONN(ge, 1); 1247 1248 if(smooth && (good || reversal) ) { 1249 /* -1 to avoid ge->bkwd being counted twice */ 1250 if( X_FRAG(ge->bkwd)->len[d] >= 2 ) 1251 count += X_FRAG(ge->bkwd)->len[d] - 1; 1252 else if(count == clen+1) { 1253 /* we are joining a circular (closed) curve, check whether it 1254 * can be joined at any point or whether it has a discontinuity 1255 * at the point where we join it now 1256 */ 1257 lastdx = dx; lastdy = dy; 1258 CHKCURVCONN(ge->frwd, 0); 1259 1260 if(smooth && (good || reversal) ) { 1261 /* yes, the curve is truly a circular one and can be 1262 * joined at any point 1263 */ 1264 1265 #if 0 1266 fprintf(stderr, " found a circular joint point at %p\n", pge); 1267 #endif 1268 /* make sure that in a circular fragment we start from an extremum */ 1269 while( ! (X_FRAG(pge)->flags & GEXFF_EXTR) ) 1270 pge = pge->frwd; 1271 X_FRAG(pge)->flags |= GEXFF_CIRC; 1272 } 1273 } 1274 #if 0 1275 fprintf(stderr, " %s joined %p to %p count=%d bk_count=%d\n", gxf_name[d], pge, ge->bkwd, 1276 count, X_FRAG(ge->bkwd)->len[d] ); 1277 #endif 1278 X_FRAG(ge->bkwd)->len[d] = 0; 1279 } 1280 X_FRAG(pge)->len[d] = count; 1281 #if 0 1282 if(count >= 4) { /* worth remembering */ 1283 fprintf(stderr, " %s last frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); 1284 } 1285 #endif 1286 #undef CHKCURVCONN 1287 1288 /* do postprocessing */ 1289 ge = cge->next; 1290 do { 1291 f = X_FRAG(ge); 1292 len = f->len[d]; 1293 #if 0 1294 fprintf(stderr, " %p %s len=%d clen=%d\n", ge, gxf_name[d], len, clen); 1295 #endif 1296 if(len < 3) /* get rid of the fragments that are too short */ 1297 f->len[d] = 0; 1298 else if(len == 3) { 1299 /* _ 1300 * drop the |_| - shaped fragments, leave alone the _| - shaped 1301 * (and even those only if not too short in pixels), 1302 * those left alone are further filtered later 1303 */ 1304 k1 = (ge->ix3 == ge->bkwd->ix3); /* axis of the start */ 1305 if(isign(ge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) 1306 != isign(ge->frwd->ipoints[k1][2] - ge->frwd->frwd->ipoints[k1][2]) 1307 && abs(ge->frwd->frwd->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) > 2) { 1308 #if 0 1309 fprintf(stderr, " %s frag %p count=%d good shape\n", 1310 gxf_name[d], ge, count); 1311 #endif 1312 } else 1313 f->len[d] = 0; 1314 } else if(len == clen+1) 1315 break; /* a closed fragment, nothing else interesting */ 1316 else { /* only for open fragments */ 1317 GENTRY *gem, *gex, *gei, *ges; 1318 1319 ges = ge; /* the start entry */ 1320 gem = age[(f->aidx + f->len[d])%clen]; /* entry past the end of the fragment */ 1321 1322 gei = ge->frwd; 1323 if( (ge->ix3 == ge->bkwd->ix3) /* vert */ 1324 ^ (isign(ge->bkwd->ix3 - gei->ix3)==isign(ge->bkwd->iy3 - gei->iy3)) 1325 ^ !(d == GEXFI_CONVEX) /* counter-clockwise */ ) { 1326 1327 #if 0 1328 fprintf(stderr, " %p: %s potential spurious start\n", ge, gxf_name[d]); 1329 #endif 1330 /* the beginning may be a spurious entry */ 1331 1332 gex = 0; /* the extremum closest to the beginning - to be found */ 1333 for(gei = ge->frwd; gei != gem; gei = gei->frwd) { 1334 if(X_FRAG(gei)->flags & GEXFF_EXTR) { 1335 gex = gei; 1336 break; 1337 } 1338 } 1339 if(gex == 0) 1340 gex = gem->bkwd; 1341 1342 /* A special case: ignore the spurious ends on small curves that 1343 * either enclose an 1-pixel-wide extremum or are 1-pixel deep. 1344 * Any 5-or-less-pixel-long curve with extremum 2 steps away 1345 * qualifies for that. 1346 */ 1347 1348 if(len <= 5 && gex == ge->frwd->frwd) { 1349 good = 0; 1350 #if 0 1351 fprintf(stderr, " E"); 1352 #endif 1353 } else { 1354 good = 1; /* assume that ge is not spurious */ 1355 1356 /* gei goes backwards, gex goes forwards from the extremum */ 1357 gei = gex; 1358 /* i is the symmetry axis, j is the other axis (X=0 Y=1) */ 1359 i = (gex->ix3 != gex->bkwd->ix3); 1360 j = !i; 1361 for( ; gei!=ge && gex!=gem; gei=gei->bkwd, gex=gex->frwd) { 1362 if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2] 1363 || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2] 1364 != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] 1365 ) { 1366 good = 0; /* no symmetry - must be spurious */ 1367 #if 0 1368 fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)", 1369 gei, gex, 1370 i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2], 1371 j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2], 1372 gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] ); 1373 #endif 1374 break; 1375 } 1376 } 1377 if(gex == gem) { /* oops, the other side is too short */ 1378 good = 0; 1379 #if 0 1380 fprintf(stderr, " X"); 1381 #endif 1382 } 1383 if(good && gei == ge) { 1384 if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]) 1385 != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) { 1386 good = 0; /* oops, goes into another direction */ 1387 #if 0 1388 fprintf(stderr, " D"); 1389 #endif 1390 } 1391 } 1392 } 1393 if(!good) { /* it is spurious, drop it */ 1394 #if 0 1395 fprintf(stderr, " %p: %s spurious start\n", ge, gxf_name[d]); 1396 #endif 1397 f->len[d] = 0; 1398 ges = ge->frwd; 1399 len--; 1400 X_FRAG(ges)->len[d] = len; 1401 } 1402 } 1403 1404 gei = gem->bkwd->bkwd->bkwd; 1405 if( (gem->ix3 != gem->bkwd->ix3) /* gem->bkwd is vert */ 1406 ^ (isign(gem->bkwd->ix3 - gei->ix3)==isign(gem->bkwd->iy3 - gei->iy3)) 1407 ^ (d == GEXFI_CONVEX) /* clockwise */ ) { 1408 1409 #if 0 1410 fprintf(stderr, " %p: %s potential spurious end\n", gem->bkwd, gxf_name[d]); 1411 #endif 1412 /* the end may be a spurious entry */ 1413 1414 gex = 0; /* the extremum closest to the end - to be found */ 1415 for(gei = gem->bkwd->bkwd; gei != ges->bkwd; gei = gei->bkwd) { 1416 if(X_FRAG(gei)->flags & GEXFF_EXTR) { 1417 gex = gei; 1418 break; 1419 } 1420 } 1421 if(gex == 0) 1422 gex = ges; 1423 1424 good = 1; /* assume that gem->bkwd is not spurious */ 1425 /* gei goes backwards, gex goes forwards from the extremum */ 1426 gei = gex; 1427 /* i is the symmetry axis, j is the other axis (X=0 Y=1) */ 1428 i = (gex->ix3 != gex->bkwd->ix3); 1429 j = !i; 1430 for( ; gei!=ges->bkwd && gex!=gem->bkwd; gei=gei->bkwd, gex=gex->frwd) { 1431 if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2] 1432 || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2] 1433 != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] 1434 ) { 1435 good = 0; /* no symmetry - must be spurious */ 1436 #if 0 1437 fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)", 1438 gei, gex, 1439 i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2], 1440 j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2], 1441 gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] ); 1442 #endif 1443 break; 1444 } 1445 } 1446 if(gei == ges->bkwd) { /* oops, the other side is too short */ 1447 good = 0; 1448 #if 0 1449 fprintf(stderr, " X"); 1450 #endif 1451 } 1452 if(good && gex == gem->bkwd) { 1453 if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]) 1454 != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) { 1455 good = 0; /* oops, goes into another direction */ 1456 #if 0 1457 fprintf(stderr, " D"); 1458 #endif 1459 } 1460 } 1461 if(!good) { /* it is spurious, drop it */ 1462 #if 0 1463 fprintf(stderr, " %p: %s spurious end\n", gem->bkwd, gxf_name[d]); 1464 #endif 1465 X_FRAG(ges)->len[d] = --len; 1466 } 1467 } 1468 if(len < 4) { 1469 X_FRAG(ges)->len[d] = 0; 1470 #if 0 1471 fprintf(stderr, " %p: %s frag discarded, too small now\n", ge, gxf_name[d]); 1472 #endif 1473 } 1474 if(ges != ge) { 1475 if(ges == cge->next) 1476 break; /* went around the loop */ 1477 else { 1478 ge = ges->frwd; /* don't look at this fragment twice */ 1479 continue; 1480 } 1481 } 1482 } 1483 1484 ge = ge->frwd; 1485 } while(ge != cge->next); 1486 } 1487 1488 /* Find the straight line fragments. 1489 * Even though the lines are sloped, they are called 1490 * "vertical" or "horizontal" according to their longer 1491 * dimension. All the steps in the shother dimension must 1492 * be 1 pixel long, all the steps in the longer dimension 1493 * must be within the difference of 1 pixel. 1494 */ 1495 for(d = GEXFI_LINE; d<= GEXFI_EXACTLINE; d++) { 1496 ge = cge->next; 1497 pge = ge->bkwd; /* the beginning of the fragment */ 1498 count = 1; 1499 delaystop = 0; 1500 do { 1501 int h; 1502 1503 stepmore = 0; 1504 hdir = isign(ge->ix3 - ge->bkwd->ix3); 1505 vdir = isign(ge->iy3 - ge->bkwd->iy3); 1506 vert = (hdir == 0); 1507 if(count==1) { 1508 /* at this point pge==ge->bkwd */ 1509 /* account for the previous gentry, which was !vert */ 1510 if(!vert) { /* prev was vertical */ 1511 maxlen[0] = minlen[0] = 0; 1512 maxlen[1] = minlen[1] = abs(pge->iy3 - pge->bkwd->iy3); 1513 line[0] = (maxlen[1] == 1); 1514 line[1] = 1; 1515 fullhdir = hdir; 1516 fullvdir = isign(pge->iy3 - pge->bkwd->iy3); 1517 } else { 1518 maxlen[0] = minlen[0] = abs(pge->ix3 - pge->bkwd->ix3); 1519 maxlen[1] = minlen[1] = 0; 1520 line[0] = 1; 1521 line[1] = (maxlen[0] == 1); 1522 fullhdir = isign(pge->ix3 - pge->bkwd->ix3); 1523 fullvdir = vdir; 1524 } 1525 } 1526 h = line[0]; /* remember the prevalent direction */ 1527 #if 0 1528 fprintf(stderr, " %p: v=%d(%d) h=%d(%d) vl(%d,%d,%d) hl=(%d,%d,%d) %s count=%d ", 1529 ge, vdir, fullvdir, hdir, fullhdir, 1530 line[1], minlen[1], maxlen[1], 1531 line[0], minlen[0], maxlen[0], 1532 gxf_name[d], count); 1533 #endif 1534 if(vert) { 1535 if(vdir != fullvdir) 1536 line[0] = line[1] = 0; 1537 len = abs(ge->iy3 - ge->bkwd->iy3); 1538 } else { 1539 if(hdir != fullhdir) 1540 line[0] = line[1] = 0; 1541 len = abs(ge->ix3 - ge->bkwd->ix3); 1542 } 1543 #if 0 1544 fprintf(stderr, "len=%d\n", len); 1545 #endif 1546 if(len != 1) /* this is not a continuation in the short dimension */ 1547 line[!vert] = 0; 1548 1549 /* can it be a continuation in the long dimension ? */ 1550 if( line[vert] ) { 1551 if(maxlen[vert]==0) 1552 maxlen[vert] = minlen[vert] = len; 1553 else if(maxlen[vert]==minlen[vert]) { 1554 if(d == GEXFI_EXACTLINE) { 1555 if(len != maxlen[vert]) 1556 line[vert] = 0; /* it can't */ 1557 } else if(len < maxlen[vert]) { 1558 if(len < minlen[vert]-1) 1559 line[vert] = 0; /* it can't */ 1560 else 1561 minlen[vert] = len; 1562 } else { 1563 if(len > maxlen[vert]+1) 1564 line[vert] = 0; /* it can't */ 1565 else 1566 maxlen[vert] = len; 1567 } 1568 } else if(len < minlen[vert] || len > maxlen[vert]) 1569 line[vert] = 0; /* it can't */ 1570 } 1571 1572 if(line[0] == 0 && line[1] == 0) { 1573 #if 0 1574 if(count >= 3) 1575 fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); 1576 #endif 1577 X_FRAG(pge)->len[d] = count; 1578 if(d == GEXFI_EXACTLINE && h) { 1579 X_FRAG(pge)->flags |= GEXFF_HLINE; 1580 } 1581 if(count == 1) 1582 pge = ge; 1583 else { 1584 stepmore = 1; /* may reconsider the 1st gentry */ 1585 pge = ge = ge->bkwd; 1586 count = 1; 1587 } 1588 } else 1589 count++; 1590 1591 ge = ge->frwd; 1592 if(ge == cge->next && !stepmore) 1593 delaystop = 1; /* consider the first gentry again */ 1594 } while(stepmore || ge != cge->next ^ delaystop); 1595 /* see if there is an unfinished line left */ 1596 if(count != 1) { 1597 #if 0 1598 if(count >= 3) 1599 fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count); 1600 #endif 1601 X_FRAG(ge->bkwd->bkwd)->len[d] = 0; 1602 X_FRAG(pge)->len[d] = count; 1603 } 1604 } 1605 1606 /* do postprocessing of the lines */ 1607 #if 0 1608 fprintf(stderr, "Line postprocessing\n"); 1609 gex_dump_contour(cge->next, clen); 1610 #endif 1611 1612 /* the non-exact line frags are related to exact line frags sort 1613 * of like to individual gentries: two kinds of exact frags 1614 * must be interleaved, with one kind having the size of 3 1615 * and the other kind having the size varying within +-2. 1616 */ 1617 1618 ge = cge->next; 1619 do { 1620 GEX_FRAG *pf, *lastf1, *lastf2; 1621 int len1, len2, fraglen; 1622 1623 f = X_FRAG(ge); 1624 1625 fraglen = f->len[GEXFI_LINE]; 1626 if(fraglen >= 4) { 1627 1628 vert = 0; /* vert is a pseudo-directon */ 1629 line[0] = line[1] = 1; 1630 maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0; 1631 lastf2 = lastf1 = f; 1632 len2 = len1 = 0; 1633 for(pge = ge, i = 1; i < fraglen; i++, pge=pge->frwd) { 1634 pf = X_FRAG(pge); 1635 len = pf->len[GEXFI_EXACTLINE]; 1636 #if 0 1637 fprintf(stderr, " pge=%p i=%d of %d ge=%p exLen=%d\n", pge, i, 1638 f->len[GEXFI_LINE], ge, len); 1639 #endif 1640 len1++; len2++; 1641 if(len==0) { 1642 continue; 1643 } 1644 vert = !vert; /* alternate the pseudo-direction */ 1645 if(len > 3) 1646 line[!vert] = 0; 1647 if(maxlen[vert] == 0) 1648 maxlen[vert] = minlen[vert] = len; 1649 else if(maxlen[vert]-2 >= len && minlen[vert]+2 <= len) { 1650 if(len > maxlen[vert]) 1651 maxlen[vert] = len; 1652 else if(len < minlen[vert]) 1653 minlen[vert] = len; 1654 } else 1655 line[vert] = 0; 1656 if(line[0] == 0 && line[1] == 0) { 1657 #if 0 1658 fprintf(stderr, " Line breaks at %p %c(%d, %d) %c(%d, %d) len=%d fl=%d l2=%d l1=%d\n", 1659 pge, (!vert)?'*':' ', minlen[0], maxlen[0], 1660 vert?'*':' ', minlen[1], maxlen[1], len, fraglen, len2, len1); 1661 #endif 1662 if(lastf2 != lastf1) { 1663 lastf2->len[GEXFI_LINE] = len2-len1; 1664 } 1665 lastf1->len[GEXFI_LINE] = len1+1; 1666 pf->len[GEXFI_LINE] = fraglen+1 - i; 1667 #if 0 1668 gex_dump_contour(pge, clen); 1669 #endif 1670 1671 /* continue with the line */ 1672 vert = 0; /* vert is a pseudo-directon */ 1673 line[0] = line[1] = 1; 1674 maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0; 1675 lastf2 = lastf1 = f; 1676 len2 = len1 = 0; 1677 } else { 1678 lastf1 = pf; 1679 len1 = 0; 1680 } 1681 } 1682 } 1683 1684 ge = ge->frwd; 1685 } while(ge != cge->next); 1686 #if 0 1687 fprintf(stderr, "Line postprocessing part 2\n"); 1688 gex_dump_contour(cge->next, clen); 1689 #endif 1690 1691 ge = cge->next; 1692 do { 1693 f = X_FRAG(ge); 1694 1695 if(f->len[GEXFI_LINE] >= 4) { 1696 len = f->len[GEXFI_EXACTLINE]; 1697 /* if a non-exact line covers precisely two exact lines, 1698 * split it 1699 */ 1700 if(len > 0 && f->len[GEXFI_LINE] >= len+1) { 1701 GEX_FRAG *pf; 1702 pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */ 1703 pf = X_FRAG(pge); 1704 if(f->len[GEXFI_LINE] + 1 == len + pf->len[GEXFI_EXACTLINE]) { 1705 f->len[GEXFI_LINE] = len; 1706 f->flags |= GEXFF_SPLIT; 1707 pf->len[GEXFI_LINE] = pf->len[GEXFI_EXACTLINE]; 1708 pf->flags |= GEXFF_SPLIT; 1709 } 1710 } 1711 } 1712 1713 ge = ge->frwd; 1714 } while(ge != cge->next); 1715 #if 0 1716 fprintf(stderr, "Line postprocessing part 2a\n"); 1717 gex_dump_contour(cge->next, clen); 1718 #endif 1719 ge = cge->next; 1720 do { 1721 f = X_FRAG(ge); 1722 1723 /* too small lines are of no interest */ 1724 if( (f->flags & GEXFF_SPLIT)==0 && f->len[GEXFI_LINE] < 4) 1725 f->len[GEXFI_LINE] = 0; 1726 1727 len = f->len[GEXFI_EXACTLINE]; 1728 /* too small exact lines are of no interest */ 1729 if(len < 3) /* exact lines may be shorter */ 1730 f->len[GEXFI_EXACTLINE] = 0; 1731 /* get rid of inexact additions to the end of the exact lines */ 1732 else if(f->len[GEXFI_LINE] == len+1) 1733 f->len[GEXFI_LINE] = len; 1734 /* same at the beginning */ 1735 else { 1736 int diff = X_FRAG(ge->bkwd)->len[GEXFI_LINE] - len; 1737 1738 if(diff == 1 || diff == 2) { 1739 X_FRAG(ge->bkwd)->len[GEXFI_LINE] = 0; 1740 f->len[GEXFI_LINE] = len; 1741 } 1742 } 1743 1744 ge = ge->frwd; 1745 } while(ge != cge->next); 1746 #if 0 1747 fprintf(stderr, "Line postprocessing is completed\n"); 1748 gex_dump_contour(cge->next, clen); 1749 #endif 1750 1751 gex_calc_lenback(cge->next, clen); /* prepare data */ 1752 1753 /* resolve conflicts between lines and curves */ 1754 1755 /* 1756 * the short (3-gentry) curve frags must have one of the ends 1757 * coinciding with another curve frag of the same type 1758 */ 1759 1760 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1761 ge = cge->next; 1762 do { 1763 f = X_FRAG(ge); 1764 1765 if(f->len[d] == 3) { 1766 pge = age[(f->aidx + 2)%clen]; /* last gentry of this frag */ 1767 if(f->lenback[d] == 0 && X_FRAG(pge)->len[d] == 0) { 1768 fprintf(stderr, " discarded small %s at %p-%p\n", gxf_name[d], ge, pge); 1769 f->len[d] = 0; 1770 X_FRAG(ge->frwd)->lenback[d] = 0; 1771 X_FRAG(ge->frwd->frwd)->lenback[d] = 0; 1772 } 1773 } 1774 ge = ge->frwd; 1775 } while(ge != cge->next); 1776 } 1777 1778 /* the serifs take priority over everything else */ 1779 ge = cge->next; 1780 do { 1781 f = X_FRAG(ge); 1782 1783 len = f->len[GEXFI_SERIF]; 1784 if(len == 0) 1785 continue; 1786 1787 if(len != 2) { /* this is used in the code below */ 1788 fprintf(stderr, "Internal error at %s line %d: serif frags len is %d\n", 1789 __FILE__, __LINE__, len); 1790 exit(1); 1791 } 1792 1793 for(d = 0; d < GEXFI_SERIF; d++) { 1794 /* serifs may not have common ends with the other fragments, 1795 * this is expressed as extending them by 1 gentry on each side 1796 */ 1797 frag_subtract(g, age, clen, ge->bkwd, len+2, d); 1798 } 1799 } while( (ge = ge->frwd) != cge->next); 1800 1801 /* 1802 * longer exact lines take priority over curves; shorter lines 1803 * and inexact lines are resolved with convex/concave conflicts 1804 */ 1805 ge = cge->next; 1806 do { 1807 f = X_FRAG(ge); 1808 1809 len = f->len[GEXFI_EXACTLINE]; 1810 1811 if(len < 6) { /* line is short */ 1812 ge = ge->frwd; 1813 continue; 1814 } 1815 1816 fprintf(stderr, " line at %p len=%d\n", ge, f->len[GEXFI_EXACTLINE]); 1817 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1818 frag_subtract(g, age, clen, ge, len, d); 1819 } 1820 1821 ge = ge->frwd; 1822 } while(ge != cge->next); 1823 1824 /* 1825 * The exact lines take priority over curves that coincide 1826 * with them or extend by only one gentry on either side 1827 * (but not both sides). By this time it applies only to the 1828 * small exact lines. 1829 * 1830 * An interesting general case is when a curve matches more 1831 * than one exact line going diamond-like. 1832 */ 1833 1834 ge = cge->next; 1835 do { 1836 int done, len2; 1837 int sharpness; 1838 GEX_FRAG *pf; 1839 1840 f = X_FRAG(ge); 1841 1842 /* "sharpness" shows how a group of exact line frags is connected: if the gentries 1843 * of some of them overlap, the curve matching requirement is loosened: it may 1844 * extend up to 1 gentry beyond each end of the group of exact line frags 1845 * (sharpness=2); otherwise it may extend to only one end (sharpness=1) 1846 */ 1847 sharpness = 1; 1848 1849 len = f->len[GEXFI_EXACTLINE]; 1850 if(len >= 4) { 1851 while(len < clen) { 1852 done = 0; 1853 pf = X_FRAG(ge->bkwd); 1854 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1855 if(f->len[d] == len || f->len[d] == len+1) { 1856 1857 fprintf(stderr, " removed %s frag at %p len=%d linelen=%d\n", 1858 gxf_name[d], ge, f->len[d], len); 1859 pge = ge->frwd; 1860 for(i = f->len[d]; i > 1; i--, pge = pge->frwd) 1861 X_FRAG(pge)->lenback[d] = 0; 1862 f->len[d] = 0; 1863 gex_dump_contour(ge, clen); 1864 done = 1; 1865 } else if(pf->len[d] == len+1 || pf->len[d] == len+sharpness) { 1866 fprintf(stderr, " removed %s frag at %p len=%d next linelen=%d\n", 1867 gxf_name[d], ge->bkwd, pf->len[d], len); 1868 pge = ge; 1869 for(i = pf->len[d]; i > 1; i--, pge = pge->frwd) 1870 X_FRAG(pge)->lenback[d] = 0; 1871 pf->len[d] = 0; 1872 gex_dump_contour(ge, clen); 1873 done = 1; 1874 } 1875 } 1876 if(done) 1877 break; 1878 1879 /* is there any chance to match a sequence of exect lines ? */ 1880 if(f->len[GEXFI_CONVEX] < len && f->len[GEXFI_CONCAVE] < len 1881 && pf->len[GEXFI_CONVEX] < len && pf->len[GEXFI_CONCAVE] < len) 1882 break; 1883 1884 done = 1; 1885 /* check whether the line is connected to another exact line at an extremum */ 1886 pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */ 1887 len2 = X_FRAG(pge)->len[GEXFI_EXACTLINE]; 1888 if(len2 > 0) { 1889 if( len2 >= 4 && (X_FRAG(pge)->flags & GEXFF_EXTR) ) { 1890 len += len2 - 1; 1891 sharpness = 2; 1892 done = 0; 1893 } 1894 } else { 1895 /* see if the extremum is between two exact lines */ 1896 pge = pge->frwd; 1897 if(X_FRAG(pge)->flags & GEXFF_EXTR) { 1898 pge = pge->frwd; 1899 len2 = X_FRAG(pge)->len[GEXFI_EXACTLINE]; 1900 if(len2 >= 4) { 1901 len += len2 + 1; 1902 done = 0; 1903 } 1904 } 1905 } 1906 if(done) 1907 break; 1908 } 1909 } 1910 1911 ge = ge->frwd; 1912 } while(ge != cge->next); 1913 1914 /* 1915 * The lines may cover only whole curves (or otherwise empty space), 1916 * so cut them where they overlap parts of the curves. If 2 or less 1917 * gentries are left in the line, remove the line. 1918 * If a line and a curve fully coincide, remove the line. Otherwise 1919 * remove the curves that are completely covered by the lines. 1920 */ 1921 1922 ge = cge->next; 1923 do { 1924 f = X_FRAG(ge); 1925 1926 reconsider_line: 1927 len = f->len[GEXFI_LINE]; 1928 1929 if(len == 0) { 1930 ge = ge->frwd; 1931 continue; 1932 } 1933 1934 if(f->len[GEXFI_CONVEX] >= len 1935 || f->len[GEXFI_CONCAVE] >= len) { 1936 line_completely_covered: 1937 fprintf(stderr, " removed covered Line frag at %p len=%d\n", 1938 ge, len); 1939 f->len[GEXFI_LINE] = 0; 1940 for(pge = ge->frwd; len > 1; len--, pge = pge->frwd) 1941 X_FRAG(pge)->lenback[GEXFI_LINE] = 0; 1942 gex_dump_contour(ge, clen); 1943 ge = ge->frwd; 1944 continue; 1945 } 1946 1947 k1 = 0; /* how much to cut at the front */ 1948 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1949 if(f->lenback[d]) { 1950 pge = age[(f->aidx + clen - f->lenback[d])%clen]; 1951 i = X_FRAG(pge)->len[d] - f->lenback[d] - 1; 1952 if(i > k1) 1953 k1 = i; 1954 } 1955 } 1956 1957 k2 = 0; /* how much to cut at the end */ 1958 pge = age[(f->aidx + len)%clen]; /* gentry after the end */ 1959 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1960 i = X_FRAG(pge)->lenback[d] - 1; 1961 if(i > k2) 1962 k2 = i; 1963 } 1964 1965 if(k1+k2 > 0 && k1+k2 >= len-3) { 1966 fprintf(stderr, " k1=%d k2=%d\n", k1, k2); 1967 goto line_completely_covered; 1968 } 1969 1970 1971 if(k2 != 0) { /* cut the end */ 1972 len -= k2; 1973 f->len[GEXFI_LINE] = len; 1974 /* pge still points after the end */ 1975 for(i = k2, pge = pge->bkwd; i > 0; i--, pge = pge->bkwd) 1976 X_FRAG(pge)->lenback[GEXFI_LINE] = 0; 1977 } 1978 if(k1 != 0) { /* cut the beginning */ 1979 len -= k1; 1980 f->len[GEXFI_LINE] = 0; 1981 for(i = 1, pge = ge->frwd; i < k1; i++, pge = pge->frwd) 1982 X_FRAG(pge)->lenback[GEXFI_LINE] = 0; 1983 X_FRAG(pge)->len[GEXFI_LINE] = len; 1984 for(i = 0; i < len; i++, pge = pge->frwd) 1985 X_FRAG(pge)->lenback[GEXFI_LINE] = i; 1986 } 1987 if(k1 != 0 || k2 != 0) { 1988 fprintf(stderr, " cut Line frag at %p by (%d,%d) to len=%d\n", 1989 ge, k1, k2, len); 1990 gex_dump_contour(ge, clen); 1991 1992 goto reconsider_line; /* the line may have to be cut again */ 1993 } 1994 pge = age[(f->aidx + k1)%clen]; /* new beginning */ 1995 good = 1; /* flag: no need do do a debugging dump */ 1996 for(i=1; i<len; i++, pge = pge->frwd) 1997 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 1998 if(X_FRAG(pge)->len[d]) { 1999 fprintf(stderr, " removed %s frag at %p len=%d covered by line\n", 2000 gxf_name[d], pge, X_FRAG(pge)->len[d], len); 2001 good = 0; 2002 } 2003 X_FRAG(pge)->len[d] = 0; 2004 } 2005 pge = age[(f->aidx + k1 + 1)%clen]; /* next after new beginning */ 2006 for(i=1; i<len; i++, pge = pge->frwd) 2007 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) 2008 X_FRAG(pge)->lenback[d] = 0; 2009 if(!good) 2010 gex_dump_contour(ge, clen); 2011 2012 ge = ge->frwd; 2013 } while(ge != cge->next); 2014 2015 /* Resolve conflicts between curves */ 2016 for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) { 2017 dx = (GEXFI_CONVEX + GEXFI_CONCAVE) - d; /* the other type */ 2018 ge = cge->next; 2019 do { 2020 GENTRY *sge; 2021 2022 f = X_FRAG(ge); 2023 len = f->len[d]; 2024 if(len < 2) { 2025 ge = ge->frwd; 2026 continue; 2027 } 2028 sge = ge; /* the start of fragment */ 2029 2030 i = f->len[dx]; 2031 if(i != 0) { /* two curved frags starting here */ 2032 /* should be i!=len because otherwise they would be 2033 * covered by an exact line 2034 */ 2035 if(i > len) { 2036 curve_completely_covered: 2037 /* remove the convex frag */ 2038 fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n", 2039 gxf_name[d], ge, len, gxf_name[dx]); 2040 f->len[d] = 0; 2041 for(pge = ge->frwd, j = 1; j < len; j++, pge = pge->frwd) 2042 X_FRAG(pge)->lenback[d] = 0; 2043 gex_dump_contour(ge, clen); 2044 2045 ge = ge->frwd; /* the frag is gone, nothing more to do */ 2046 continue; 2047 } else { 2048 /* remove the concave frag */ 2049 fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n", 2050 gxf_name[dx], ge, i, gxf_name[d]); 2051 f->len[dx] = 0; 2052 for(pge = ge->frwd, j = 1; j < i; j++, pge = pge->frwd) 2053 X_FRAG(pge)->lenback[dx] = 0; 2054 gex_dump_contour(ge, clen); 2055 } 2056 } 2057 2058 2059 k1 = X_FRAG(ge->frwd)->lenback[dx]; 2060 if(k1 != 0) { /* conflict at the front */ 2061 GENTRY *gels, *gele, *gei; 2062 2063 pge = age[(f->aidx + clen - (k1-1))%clen]; /* first gentry of concave frag */ 2064 k2 = X_FRAG(pge)->len[dx]; /* its length */ 2065 2066 i = k2 - (k1-1); /* amount of overlap */ 2067 if(i > len) 2068 i = len; 2069 /* i >= 2 by definition */ 2070 if(i >= k2-1) { /* covers the other frag - maybe with 1 gentry showing */ 2071 fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n", 2072 gxf_name[dx], pge, k2, gxf_name[d]); 2073 X_FRAG(pge)->len[dx] = 0; 2074 for(pge = pge->frwd, j = 1; j < k2; j++, pge = pge->frwd) 2075 X_FRAG(pge)->lenback[dx] = 0; 2076 if(i >= len-1) { /* covers our frag too - maybe with 1 gentry showing */ 2077 /* our frag will be removed as well, prepare a line to replace it */ 2078 gels = ge; 2079 gele = age[(f->aidx + i - 1)%clen]; 2080 fprintf(stderr, " new Line frag at %p-%p len=%d\n", gels, gele, i); 2081 X_FRAG(gels)->len[GEXFI_LINE] = i; 2082 for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++) 2083 X_FRAG(gei)->lenback[GEXFI_LINE] = j; 2084 } else { 2085 gex_dump_contour(ge, clen); 2086 ge = ge->frwd; 2087 continue; 2088 } 2089 } 2090 if(i >= len-1) /* covers our frag - maybe with 1 gentry showing */ 2091 goto curve_completely_covered; 2092 2093 /* XXX need to do something better for the case when a curve frag 2094 * is actually nothing but an artifact of two other curves of 2095 * the opposite type touching each other, like on the back of "3" 2096 */ 2097 2098 /* change the overlapping part to a line */ 2099 gels = ge; 2100 gele = age[(f->aidx + i - 1)%clen]; 2101 /* give preference to local extremums */ 2102 if(X_FRAG(gels)->flags & GEXFF_EXTR) { 2103 gels = gels->frwd; 2104 i--; 2105 } 2106 if(X_FRAG(gele)->flags & GEXFF_EXTR) { 2107 gele = gele->bkwd; 2108 i--; 2109 } 2110 if(gels->bkwd == gele) { 2111 /* Oops the line became negative. Probably should 2112 * never happen but I can't think of any formal reasoning 2113 * leading to that, so check just in case. Restore 2114 * the previous state. 2115 */ 2116 gels = gele; gele = gels->frwd; i = 2; 2117 } 2118 2119 j = X_FRAG(gels)->lenback[dx] + 1; /* new length */ 2120 if(j != k2) { 2121 X_FRAG(pge)->len[dx] = j; 2122 fprintf(stderr, " cut %s frag at %p len=%d to %p len=%d end overlap with %s\n", 2123 gxf_name[dx], pge, k2, gels, j, gxf_name[d]); 2124 for(gei = gels->frwd; j < k2; gei = gei->frwd, j++) 2125 X_FRAG(gei)->lenback[dx] = 0; 2126 } 2127 2128 if(gele != ge) { 2129 sge = gele; 2130 f->len[d] = 0; 2131 fprintf(stderr, " cut %s frag at %p len=%d ", gxf_name[d], ge, len); 2132 len--; 2133 for(gei = ge->frwd; gei != gele; gei = gei->frwd, len--) 2134 X_FRAG(gei)->lenback[d] = 0; 2135 X_FRAG(gele)->len[d] = len; 2136 X_FRAG(gele)->lenback[d] = 0; 2137 fprintf(stderr, "to %p len=%d start overlap with %s\n", 2138 sge, len, gxf_name[dx]); 2139 for(gei = gei->frwd, j = 1; j < len; gei = gei->frwd, j++) 2140 X_FRAG(gei)->lenback[d] = j; 2141 2142 } 2143 if(i > 1) { 2144 fprintf(stderr, " new Line frag at %p-%p len=%d\n", gels, gele, i); 2145 X_FRAG(gels)->len[GEXFI_LINE] = i; 2146 for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++) 2147 X_FRAG(gei)->lenback[GEXFI_LINE] = j; 2148 } 2149 gex_dump_contour(ge, clen); 2150 } 2151 2152 ge = ge->frwd; 2153 } while(ge != cge->next); 2154 } 2155 2156 /* 2157 * Assert that there are no conflicts any more and 2158 * for each gentry find the fragment types that start 2159 * and continue here. 2160 */ 2161 ge = cge->next; 2162 do { 2163 f = X_FRAG(ge); 2164 dx = GEXFI_NONE; /* type that starts here */ 2165 dy = GEXFI_NONE; /* type that goes through here */ 2166 /* GEXFI_EXACTLINE and GEXFI_SERIF are auxiliary and don't 2167 * generate any actual lines/curves in the result 2168 */ 2169 for(d = GEXFI_CONVEX; d<= GEXFI_LINE; d++) { 2170 if(f->len[d]) { 2171 if(dx >= 0) { 2172 fprintf(stderr, "**** Internal error in vectorization\n"); 2173 fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n", 2174 g->name, ge, gxf_name[dx], gxf_name[d]); 2175 dumppaths(g, cge->next, cge->next->bkwd); 2176 gex_dump_contour(ge, clen); 2177 exit(1); 2178 } 2179 dx = d; 2180 } 2181 if(f->lenback[d]) { 2182 if(dy >= 0) { 2183 fprintf(stderr, "**** Internal error in vectorization\n"); 2184 fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n", 2185 g->name, ge, gxf_name[dy], gxf_name[d]); 2186 dumppaths(g, cge->next, cge->next->bkwd); 2187 gex_dump_contour(ge, clen); 2188 exit(1); 2189 } 2190 dy = d; 2191 } 2192 } 2193 f->ixstart = dx; 2194 f->ixcont = dy; 2195 ge = ge->frwd; 2196 } while(ge != cge->next); 2197 2198 /* 2199 * make sure that the contour does not start in the 2200 * middle of a fragment 2201 */ 2202 ge = cge->next; /* old start of the contour */ 2203 f = X_FRAG(ge); 2204 if(f->ixstart == GEXFI_NONE && f->ixcont != GEXFI_NONE) { 2205 /* oops, it's mid-fragment, move the start */ 2206 GENTRY *xge; 2207 2208 xge = ge->bkwd->next; /* entry following the contour */ 2209 2210 /* find the first gentry of this frag */ 2211 pge = age[(f->aidx + clen - f->lenback[f->ixcont])%clen]; 2212 2213 ge->prev = ge->bkwd; 2214 ge->bkwd->next = ge; 2215 2216 cge->next = pge; 2217 pge->prev = cge; 2218 2219 pge->bkwd->next = xge; 2220 if(xge) 2221 xge->prev = pge->bkwd; 2222 2223 cge->ix3 = pge->bkwd->ix3; cge->iy3 = pge->bkwd->iy3; 2224 } 2225 2226 /* vectorize each fragment separately 2227 * make 2 passes: first handle the straight lines, then 2228 * the curves to allow the curver to be connected smoothly 2229 * to the straights 2230 */ 2231 ge = cge->next; 2232 do { /* pass 1 */ 2233 f = X_FRAG(ge); 2234 switch(f->ixstart) { 2235 case GEXFI_LINE: 2236 len = f->len[GEXFI_LINE]; 2237 pge = age[(f->aidx + len - 1)%clen]; /* last gentry */ 2238 2239 if(ge->iy3 == ge->bkwd->iy3) { /* frag starts and ends horizontally */ 2240 k1 = 1/*Y*/ ; /* across the direction of start */ 2241 k2 = 0/*X*/ ; /* along the direction of start */ 2242 } else { /* frag starts and ends vertically */ 2243 k1 = 0/*X*/ ; /* across the direction of start */ 2244 k2 = 1/*Y*/ ; /* along the direction of start */ 2245 } 2246 2247 if(len % 2) { 2248 /* odd number of entries in the frag */ 2249 double halfstep, halfend; 2250 2251 f->vect[0][k1] = fscale * ge->ipoints[k1][2]; 2252 f->vect[3][k1] = fscale * pge->ipoints[k1][2]; 2253 2254 halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) 2255 * 0.5 / ((len+1)/2); 2256 if(f->ixcont != GEXFI_NONE) { 2257 halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5; 2258 if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ 2259 halfstep = halfend; 2260 } 2261 if(X_FRAG(pge)->ixstart != GEXFI_NONE) { 2262 halfend = (pge->ipoints[k2][2] - pge->bkwd->ipoints[k2][2]) * 0.5; 2263 if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ 2264 halfstep = halfend; 2265 } 2266 f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep); 2267 f->vect[3][k2] = fscale * (pge->ipoints[k2][2] - halfstep); 2268 } else { 2269 /* even number of entries */ 2270 double halfstep, halfend; 2271 2272 f->vect[0][k1] = fscale * ge->ipoints[k1][2]; 2273 halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) 2274 * 0.5 / (len/2); 2275 if(f->ixcont != GEXFI_NONE) { 2276 halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5; 2277 if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ 2278 halfstep = halfend; 2279 } 2280 f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep); 2281 2282 halfstep = (pge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) 2283 * 0.5 / (len/2); 2284 if(X_FRAG(pge)->ixstart != GEXFI_NONE) { 2285 halfend = (pge->ipoints[k1][2] - pge->bkwd->ipoints[k1][2]) * 0.5; 2286 if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */ 2287 halfstep = halfend; 2288 } 2289 f->vect[3][k1] = fscale * (pge->ipoints[k1][2] - halfstep); 2290 f->vect[3][k2] = fscale * pge->ipoints[k2][2]; 2291 } 2292 f->vectlen = len; 2293 f->flags |= GEXFF_DRAWLINE; 2294 break; 2295 } 2296 } while((ge = ge->frwd) != cge->next); 2297 2298 ge = cge->next; 2299 do { /* pass 2 */ 2300 /* data for curves */ 2301 GENTRY *firstge, *lastge, *gef, *gel, *gei, *gex; 2302 GENTRY *ordhd; /* head of the order list */ 2303 GENTRY **ordlast; 2304 int nsub; /* number of subfrags */ 2305 GEX_FRAG *ff, *lf, *xf; 2306 2307 f = X_FRAG(ge); 2308 switch(f->ixstart) { 2309 case GEXFI_CONVEX: 2310 case GEXFI_CONCAVE: 2311 len = f->len[f->ixstart]; 2312 firstge = ge; 2313 lastge = age[(f->aidx + len - 1)%clen]; /* last gentry */ 2314 2315 nsub = 0; 2316 gex = firstge; 2317 xf = X_FRAG(gex); 2318 xf->prevsub = 0; 2319 xf->sublen = 1; 2320 xf->flags &= ~GEXFF_DONE; 2321 for(gei = firstge->frwd; gei != lastge; gei = gei->frwd) { 2322 xf->sublen++; 2323 if(X_FRAG(gei)->flags & GEXFF_EXTR) { 2324 xf->nextsub = gei; 2325 for(i=0; i<2; i++) 2326 xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]); 2327 nsub++; 2328 xf = X_FRAG(gei); 2329 xf->prevsub = gex; 2330 xf->sublen = 1; 2331 xf->flags &= ~GEXFF_DONE; 2332 gex = gei; 2333 } 2334 } 2335 xf->sublen++; 2336 xf->nextsub = gei; 2337 for(i=0; i<2; i++) 2338 xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]); 2339 nsub++; 2340 ff = xf; /* remember the beginning of the last subfrag */ 2341 xf = X_FRAG(gei); 2342 xf->prevsub = gex; 2343 if(firstge != lastge) { 2344 xf->nextsub = 0; 2345 xf->sublen = 0; 2346 2347 /* correct the bounding box of the last and first subfrags for 2348 * intersections with other fragments 2349 */ 2350 if(xf->ixstart != GEXFI_NONE) { 2351 /* ff points to the beginning of the last subfrag */ 2352 for(i=0; i<2; i++) 2353 ff->bbox[i] -= 0.5 * abs(lastge->ipoints[i][2] - lastge->bkwd->ipoints[i][2]); 2354 } 2355 ff = X_FRAG(firstge); 2356 if(ff->ixcont != GEXFI_NONE) { 2357 for(i=0; i<2; i++) 2358 ff->bbox[i] -= 0.5 * abs(firstge->ipoints[i][2] - firstge->bkwd->ipoints[i][2]); 2359 } 2360 } 2361 2362 fprintf(stderr, " %s frag %p%s nsub=%d\n", gxf_name[f->ixstart], 2363 ge, (f->flags&GEXFF_CIRC)?" circular":"", nsub); 2364 2365 /* find the symmetry between the subfragments */ 2366 for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { 2367 ff = X_FRAG(gef); 2368 gex = ff->nextsub; 2369 xf = X_FRAG(gex); 2370 gel = xf->nextsub; 2371 if(gel == 0) { 2372 ff->flags &= ~GEXFF_SYMNEXT; 2373 break; /* not a circular frag */ 2374 } 2375 good = 1; /* assume that we have symmetry */ 2376 /* gei goes backwards, gex goes forwards from the extremum */ 2377 gei = gex; 2378 /* i is the symmetry axis, j is the other axis (X=0 Y=1) */ 2379 ff->symaxis = i = (gex->ix3 != gex->bkwd->ix3); 2380 j = !i; 2381 for( ; gei!=gef && gex!=gel; gei=gei->bkwd, gex=gex->frwd) { 2382 if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2] 2383 || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2] 2384 != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] 2385 ) { 2386 good = 0; /* no symmetry */ 2387 break; 2388 } 2389 } 2390 if(good) { 2391 if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]) 2392 != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) { 2393 good = 0; /* oops, goes into another direction */ 2394 } 2395 } 2396 if(good) 2397 ff->flags |= GEXFF_SYMNEXT; 2398 else 2399 ff->flags &= ~GEXFF_SYMNEXT; 2400 } 2401 2402 for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { 2403 ff = X_FRAG(gef); 2404 if((ff->flags & GEXFF_SYMNEXT)==0) { 2405 ff->symxlen = 0; 2406 continue; 2407 } 2408 gex = ff->prevsub; 2409 if(gex == 0 || (X_FRAG(gex)->flags & GEXFF_SYMNEXT)==0) { 2410 ff->symxlen = 0; 2411 continue; 2412 } 2413 ff->symxlen = X_FRAG(gex)->sublen; 2414 xf = X_FRAG(ff->nextsub); 2415 if(xf->sublen < ff->symxlen) 2416 ff->symxlen = xf->sublen; 2417 } 2418 2419 /* find the symmetry inside the subfragments */ 2420 for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { 2421 ff = X_FRAG(gef); 2422 2423 if(ff->sublen % 2) { 2424 /* we must have an even number of gentries for diagonal symmetry */ 2425 ff->symge = 0; 2426 continue; 2427 } 2428 2429 /* gei goes forwards from the front */ 2430 gei = gef->frwd; 2431 /* gex goes backwards from the back */ 2432 gex = ff->nextsub->bkwd; 2433 2434 /* i is the direction of gei, j is the direction of gex */ 2435 i = (gei->iy3 != gei->bkwd->iy3); 2436 j = !i; 2437 for( ; gei->bkwd != gex; gei=gei->frwd, gex=gex->bkwd) { 2438 if( abs(gei->bkwd->ipoints[i][2] - gei->ipoints[i][2]) 2439 != abs(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) 2440 break; /* no symmetry */ 2441 i = j; 2442 j = !j; 2443 } 2444 if(gei->bkwd == gex) 2445 ff->symge = gex; 2446 else 2447 ff->symge = 0; /* no symmetry */ 2448 } 2449 2450 /* find the order of calculation: 2451 * prefer to start from long fragments that have the longest 2452 * neighbours symmetric with them, with all being equal prefer 2453 * the fragments that have smaller physical size 2454 */ 2455 ordhd = 0; 2456 for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) { 2457 ff = X_FRAG(gef); 2458 2459 for(ordlast = &ordhd; *ordlast != 0; ordlast = &xf->ordersub) { 2460 xf = X_FRAG(*ordlast); 2461 if(ff->sublen > xf->sublen) 2462 break; 2463 if(ff->sublen < xf->sublen) 2464 continue; 2465 if(ff->symxlen > xf->symxlen) 2466 break; 2467 if(ff->symxlen < xf->symxlen) 2468 continue; 2469 if(ff->bbox[0] < xf->bbox[0] || ff->bbox[1] < xf->bbox[1]) 2470 break; 2471 } 2472 2473 ff->ordersub = *ordlast; 2474 *ordlast = gef; 2475 } 2476 2477 /* vectorize the subfragments */ 2478 for(gef = ordhd; gef != 0; gef = ff->ordersub) { 2479 2480 /* debugging stuff */ 2481 ff = X_FRAG(gef); 2482 fprintf(stderr, " %p-%p bbox[%g,%g] sym=%p %s len=%d xlen=%d\n", 2483 gef, ff->nextsub, ff->bbox[0], ff->bbox[1], ff->symge, 2484 (ff->flags & GEXFF_SYMNEXT) ? "symnext" : "", 2485 ff->sublen, ff->symxlen); 2486 2487 dosubfrag(g, f->ixstart, firstge, gef, fscale); 2488 } 2489 2490 break; 2491 } 2492 } while((ge = ge->frwd) != cge->next); 2493 2494 free(age); 2495 2496 } 2497 2498 } 2499 2500 /* all the fragments are found, extract the vectorization */ 2501 pge = g->entries; 2502 g->entries = g->lastentry = 0; 2503 g->flags |= GF_FLOAT; 2504 loopge = 0; 2505 skip = 0; 2506 2507 for(ge = pge; ge != 0; ge = ge->next) { 2508 GEX_FRAG *f, *pf; 2509 2510 switch(ge->type) { 2511 case GE_LINE: 2512 f = X_FRAG(ge); 2513 if(skip == 0) { 2514 if(f->flags & (GEXFF_DRAWLINE|GEXFF_DRAWCURVE)) { 2515 /* draw a line to the start point */ 2516 fg_rlineto(g, f->vect[0][0], f->vect[0][1]); 2517 /* draw the fragment */ 2518 if(f->flags & GEXFF_DRAWCURVE) 2519 fg_rrcurveto(g, 2520 f->vect[1][0], f->vect[1][1], 2521 f->vect[2][0], f->vect[2][1], 2522 f->vect[3][0], f->vect[3][1]); 2523 else 2524 fg_rlineto(g, f->vect[3][0], f->vect[3][1]); 2525 skip = f->vectlen - 2; 2526 } else { 2527 fg_rlineto(g, fscale * ge->ix3, fscale * ge->iy3); 2528 } 2529 } else 2530 skip--; 2531 break; 2532 case GE_MOVE: 2533 fg_rmoveto(g, -1e6, -1e6); /* will be fixed by GE_PATH */ 2534 skip = 0; 2535 /* remember the reference to update it later */ 2536 loopge = g->lastentry; 2537 break; 2538 case GE_PATH: 2539 /* update the first MOVE of this contour */ 2540 if(loopge) { 2541 loopge->fx3 = g->lastentry->fx3; 2542 loopge->fy3 = g->lastentry->fy3; 2543 loopge = 0; 2544 } 2545 g_closepath(g); 2546 break; 2547 } 2548 } 2549 for(ge = pge; ge != 0; ge = cge) { 2550 cge = ge->next; 2551 free(ge->ext); 2552 free(ge); 2553 } 2554 dumppaths(g, NULL, NULL); 2555 2556 /* end of vectorization logic */ 2557 } else { 2558 /* convert the data to float */ 2559 GENTRY *ge; 2560 double x, y; 2561 2562 for(ge = g->entries; ge != 0; ge = ge->next) { 2563 ge->flags |= GEF_FLOAT; 2564 if(ge->type != GE_MOVE && ge->type != GE_LINE) 2565 continue; 2566 2567 x = fscale * ge->ix3; 2568 y = fscale * ge->iy3; 2569 2570 ge->fx3 = x; 2571 ge->fy3 = y; 2572 } 2573 g->flags |= GF_FLOAT; 2574 } 2575 2576 free(hlm); free(vlm); free(amp); 2577 } 2578 2579 #if 0 2580 /* print out the bitmap */ 2581 printbmap(bmap, xsz, ysz, xoff, yoff) 2582 char *bmap; 2583 int xsz, ysz, xoff, yoff; 2584 { 2585 int x, y; 2586 2587 for(y=ysz-1; y>=0; y--) { 2588 putchar( (y%10==0) ? y/10+'0' : ' ' ); 2589 putchar( y%10+'0' ); 2590 for(x=0; x<xsz; x++) 2591 putchar( bmap[y*xsz+x] ? 'X' : '.' ); 2592 if(-yoff==y) 2593 putchar('_'); /* mark the baseline */ 2594 putchar('\n'); 2595 } 2596 putchar(' '); putchar(' '); 2597 for(x=0; x<xsz; x++) 2598 putchar( x%10+'0' ); 2599 putchar('\n'); putchar(' '); putchar(' '); 2600 for(x=0; x<xsz; x++) 2601 putchar( (x%10==0) ? x/10+'0' : ' ' ); 2602 putchar('\n'); 2603 } 2604 2605 /* print out the limits of outlines */ 2606 printlimits(hlm, vlm, amp, xsz, ysz) 2607 char *hlm, *vlm, *amp; 2608 int xsz, ysz; 2609 { 2610 int x, y; 2611 static char h_char[]={ ' ', '~', '^' }; 2612 static char v_char[]={ ' ', '(', ')' }; 2613 2614 for(y=ysz-1; y>=0; y--) { 2615 for(x=0; x<xsz; x++) { 2616 if(amp[y*xsz+x]) 2617 putchar('!'); /* ambigouos point is always on a limit */ 2618 else 2619 putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]); 2620 putchar(h_char[ hlm[(y+1)*xsz+x] & (L_ON|L_OFF) ]); 2621 } 2622 putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]); 2623 putchar('\n'); 2624 } 2625 /* last line */ 2626 for(x=0; x<xsz; x++) { 2627 putchar(' '); 2628 putchar(h_char[ hlm[x] & (L_ON|L_OFF) ]); 2629 } 2630 putchar(' '); 2631 putchar('\n'); 2632 } 2633 #endif /* 0 */
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 |