added missing file
[swftools.git] / 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 */