pdf2swf/ttf2pt1/bitmap.c

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