source: trunk/filemanager/tp/dompdf/lib/ttf2ufm/ttf2ufm-src/bitmap.c @ 2000

Revision 2000, 75.7 KB checked in by amuller, 14 years ago (diff)

Ticket #597 - Implementação do módulo gerenciador de arquivos

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