--- /dev/null
+/*
+ * The font parser for the BDF files
+ *
+ * Copyright (c) 2001 by the TTF2PT1 project
+ * Copyright (c) 2001 by Sergey Babkin
+ *
+ * see COPYRIGHT for the full copyright notice
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include "pt1.h"
+#include "global.h"
+
+/* prototypes of call entries */
+static void openfont(char *fname, char *arg);
+static void closefont( void);
+static int getnglyphs ( void);
+static int glnames( GLYPH *glyph_list);
+static void readglyphs( GLYPH *glyph_list);
+static int glenc( GLYPH *glyph_list, int *encoding, int *unimap);
+static void fnmetrics( struct font_metrics *fm);
+static void glpath( int glyphno, GLYPH *glyph_list);
+static void kerning( GLYPH *glyph_list);
+
+/* globals */
+
+/* front-end descriptor */
+struct frontsw bdf_sw = {
+ /*name*/ "bdf",
+ /*descr*/ "BDF bitmapped fonts",
+ /*suffix*/ { "bdf" },
+ /*open*/ openfont,
+ /*close*/ closefont,
+ /*nglyphs*/ getnglyphs,
+ /*glnames*/ glnames,
+ /*glmetrics*/ readglyphs,
+ /*glenc*/ glenc,
+ /*fnmetrics*/ fnmetrics,
+ /*glpath*/ glpath,
+ /*kerning*/ kerning,
+};
+
+/* statics */
+
+#define MAXLINE 10240 /* maximal line length in the input file */
+
+static int lineno; /* line number */
+
+#define GETLEN(s) s, (sizeof(s)-1)
+#define LENCMP(str, txt) strncmp(str, txt, sizeof(txt)-1)
+
+static FILE *bdf_file;
+static int nglyphs;
+static struct font_metrics fmet;
+
+/* many BDF fonts are of small pixel size, so we better try
+ * to scale them by an integer to keep the dimensions in
+ * whole pixels. However if the size is too big and a non-
+ * integer scaling is needed, we use the standard ttf2pt1's
+ * scaling abilities.
+ */
+static int pixel_size;
+static int scale;
+static int scale_external;
+
+static char *slant;
+static char xlfdname[201];
+static char *spacing;
+static char *charset_reg;
+static char *charset_enc;
+static char *fnwidth;
+static int is_unicode = 0;
+
+/* tempoary storage for returning data to ttf2pt1 later on request */
+static int maxenc = 0;
+static int *fontenc;
+static GENTRY **glpaths;
+
+static int got_glyphs = 0;
+static GLYPH *glyphs;
+static int curgl;
+
+static int readfile(FILE *f, int (*strfunc)(int len, char *str));
+
+/*
+ * Read the file and parse each string with strfunc(),
+ * until strfunc() returns !=0 or the end of file happens.
+ * Returns -1 on EOF or strfunc() returning <0, else 0
+ */
+
+static int
+readfile(
+ FILE *f,
+ int (*strfunc)(int len, char *str)
+)
+{
+ static char str[MAXLINE]; /* input line, maybe should be dynamic ? */
+ char *s;
+ int len, c, res;
+
+ len=0;
+ while(( c=getc(f) )!=EOF) {
+ if(c=='\n') {
+ str[len]=0;
+
+ res = strfunc(len, str);
+ lineno++;
+ if(res<0)
+ return -1;
+ else if(res!=0)
+ return 0;
+
+ len=0;
+ } else if(len<MAXLINE-1) {
+ if(c!='\r')
+ str[len++]=c;
+ } else {
+ fprintf(stderr, "**** bdf: line %d is too long (>%d)\n", lineno, MAXLINE-1);
+ exit(1);
+ }
+ }
+ return -1; /* EOF */
+}
+
+/*
+ * Parse the header of the font file.
+ * Stop after the line CHARS is encountered. Ignore the unknown lines.
+ */
+
+struct line {
+ char *name; /* property name with trailing space */
+ int namelen; /* length of the name string */
+ enum {
+ ALLOW_REPEAT = 0x01, /* this property may be repeated in multiple lines */
+ IS_SEEN = 0x02, /* this property has been seen already */
+ MUST_SEE = 0x04, /* this property must be seen */
+ IS_LAST = 0x08 /* this is the last property to be read */
+ } flags;
+ char *fmt; /* format string for the arguments, NULL means a string arg */
+ int nvals; /* number of values to be read by sscanf */
+ void *vp[4]; /* pointers to values to be read */
+};
+
+static struct line header[] = {
+ { GETLEN("FONT "), 0, " %200s", 1, {&xlfdname} },
+ { GETLEN("SIZE "), MUST_SEE, " %d", 1, {&pixel_size} },
+ { GETLEN("FONTBOUNDINGBOX "), MUST_SEE, " %hd %hd %hd %hd", 4,
+ {&fmet.bbox[2], &fmet.bbox[3], &fmet.bbox[0], &fmet.bbox[1]} },
+ { GETLEN("FAMILY_NAME "), MUST_SEE, NULL, 1, {&fmet.name_family} },
+ { GETLEN("WEIGHT_NAME "), MUST_SEE, NULL, 1, {&fmet.name_style} },
+ { GETLEN("COPYRIGHT "), 0, NULL, 1, {&fmet.name_copyright} },
+ { GETLEN("SLANT "), MUST_SEE, NULL, 1, {&slant} },
+ { GETLEN("SPACING "), 0, NULL, 1, {&spacing} },
+ { GETLEN("SETWIDTH_NAME "), 0, NULL, 1, {&fnwidth} },
+ { GETLEN("CHARSET_REGISTRY "), 0, NULL, 1, {&charset_reg} },
+ { GETLEN("CHARSET_ENCODING "), 0, NULL, 1, {&charset_enc} },
+ { GETLEN("FONT_ASCENT "), 0, " %hd", 1, {&fmet.ascender} },
+ { GETLEN("FONT_DESCENT "), 0, " %hd", 1, {&fmet.descender} },
+
+ /* these 2 must go in this order for post-processing */
+ { GETLEN("UNDERLINE_THICKNESS "), 0, " %hd", 1, {&fmet.underline_thickness} },
+ { GETLEN("UNDERLINE_POSITION "), 0, " %hd", 1, {&fmet.underline_position} },
+
+ { GETLEN("CHARS "), MUST_SEE|IS_LAST, " %d", 1, {&nglyphs} },
+ { NULL, 0, 0 } /* end mark: name==NULL */
+};
+
+static int
+handle_header(
+ int len,
+ char *str
+)
+{
+ struct line *cl;
+ char *s, *p;
+ int c;
+
+#if 0
+ fprintf(stderr, "line: %s\n", str);
+#endif
+ for(cl = header; cl->name != 0; cl++) {
+ if(strncmp(str, cl->name, cl->namelen))
+ continue;
+#if 0
+ fprintf(stderr, "match: %s\n", cl->name);
+#endif
+ if(cl->flags & IS_SEEN) {
+ if(cl->flags & ALLOW_REPEAT)
+ continue;
+
+ fprintf(stderr, "**** input line %d redefines the property %s\n", lineno, cl->name);
+ exit(1);
+ }
+ cl->flags |= IS_SEEN;
+ if(cl->fmt == 0) {
+ s = malloc(len - cl->namelen + 1);
+ if(s == 0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ *((char **)(cl->vp[0])) = s;
+
+ /* skip until a quote */
+ for(p = str+cl->namelen; (c = *p)!=0; p++) {
+ if(c == '"') {
+ p++;
+ break;
+ }
+ }
+ for(; (c = *p)!=0; p++) {
+ if(c == '"') {
+ c = *++p;
+ if(c == '"')
+ *s++ = c;
+ else
+ break;
+ } else
+ *s++ = c;
+ }
+ *s = 0; /* end of line */
+ } else {
+ c = sscanf(str+cl->namelen, cl->fmt, cl->vp[0], cl->vp[1], cl->vp[2], cl->vp[3]);
+ if(c != cl->nvals) {
+ fprintf(stderr, "**** property %s at input line %d must have %d arguments\n",
+ cl->name, lineno, cl->nvals);
+ exit(1);
+ }
+ }
+ if(cl->flags & IS_LAST)
+ return 1;
+ else
+ return 0;
+ }
+ return 0;
+}
+
+/*
+ * Parse the description of the glyphs
+ */
+
+static int
+handle_glyphs(
+ int len,
+ char *str
+)
+{
+ static int inbmap=0;
+ static char *bmap;
+ static int xsz, ysz, xoff, yoff;
+ static int curln;
+ int i, c;
+ char *p, *plim, *psz;
+
+ if(!LENCMP(str, "ENDFONT")) {
+ if(curgl < nglyphs) {
+ fprintf(stderr, "**** unexpected end of font file after %d glyphs\n", curgl);
+ exit(1);
+ } else
+ return 1;
+ }
+ if(curgl >= nglyphs) {
+ fprintf(stderr, "**** file contains more glyphs than advertised (%d)\n", nglyphs);
+ exit(1);
+ }
+ if(!LENCMP(str, "STARTCHAR")) {
+ /* sizeof will count \0 instead of ' ' */
+ for(i=sizeof("STARTCHAR"); str[i] == ' '; i++)
+ {}
+
+ glyphs[curgl].name = strdup(str + i);
+ if(glyphs[curgl].name == 0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ } else if(!LENCMP(str, "ENCODING")) {
+ if(sscanf(str, "ENCODING %d", &fontenc[curgl])!=1) {
+ fprintf(stderr,"**** weird ENCODING statement at line %d\n", lineno);
+ exit(1);
+ }
+ if(fontenc[curgl] == -1) /* compatibility format */
+ sscanf(str, "ENCODING -1 %d", &fontenc[curgl]);
+ if(fontenc[curgl] > maxenc)
+ maxenc = fontenc[curgl];
+ } else if(!LENCMP(str, "DWIDTH")) {
+ if(sscanf(str, "DWIDTH %d %d", &xsz, &ysz)!=2) {
+ fprintf(stderr,"**** weird DWIDTH statement at line %d\n", lineno);
+ exit(1);
+ }
+ glyphs[curgl].width = xsz*scale;
+ } else if(!LENCMP(str, "BBX")) {
+ if(sscanf(str, "BBX %d %d %d %d", &xsz, &ysz, &xoff, &yoff)!=4) {
+ fprintf(stderr,"**** weird BBX statement at line %d\n", lineno);
+ exit(1);
+ }
+ bmap=malloc(xsz*ysz);
+ if(bmap==0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ glyphs[curgl].lsb = -xoff*scale;
+ glyphs[curgl].xMin = -xoff*scale;
+ glyphs[curgl].xMax = (xsz-xoff)*scale;
+ glyphs[curgl].yMin = -yoff*scale;
+ glyphs[curgl].yMax = (ysz-xoff)*scale;
+ } else if(!LENCMP(str, "BITMAP")) {
+ inbmap=1;
+ curln=ysz-1; /* the lowest line has index 0 */
+ } else if(!LENCMP(str, "ENDCHAR")) {
+ inbmap=0;
+ if(bmap) {
+ glyphs[curgl].lastentry = 0;
+ glyphs[curgl].path = 0;
+ glyphs[curgl].entries = 0;
+ bmp_outline(&glyphs[curgl], scale, bmap, xsz, ysz, xoff, yoff);
+ free(bmap);
+ /* remember in a static table or it will be erased */
+ glpaths[curgl] = glyphs[curgl].entries;
+ glyphs[curgl].entries = 0;
+
+ if(glpaths[curgl])
+ glyphs[curgl].ttf_pathlen = 1;
+ else
+ glyphs[curgl].ttf_pathlen = 0;
+ }
+ curgl++;
+ } else if(inbmap) {
+ if(curln<0) {
+ fprintf(stderr,"**** bitmap is longer than %d lines at line %d\n", ysz, lineno);
+ exit(1);
+ }
+
+ i=0;
+ p=&bmap[curln*xsz]; psz=p+xsz;
+ while(i<len) {
+ c=str[i++];
+ if(!isxdigit(c)) {
+ fprintf(stderr,"**** non-hex digit in bitmap at line %d\n", lineno);
+ exit(1);
+ }
+ if(c<='9')
+ c-='0';
+ else
+ c= tolower(c)-'a'+10;
+
+ for(plim=p+4; p<psz && p<plim; c<<=1)
+ *p++ = (( c & 0x08 )!=0);
+ }
+ if(p<psz) {
+ fprintf(stderr,"**** bitmap line is too short at line %d\n", lineno);
+ exit(1);
+ }
+ curln--;
+ }
+ return 0;
+}
+
+/*
+ * Read all the possible information about the glyphs
+ */
+
+static void
+readglyphs(
+ GLYPH *glyph_list
+)
+{
+ int i;
+ GLYPH *g;
+
+ if(got_glyphs)
+ return;
+
+ /* pass them to handle_glyphs() through statics */
+ glyphs = glyph_list;
+ curgl = 2; /* skip the empty glyph and .notdef */
+
+ /* initialize the empty glyph and .notdef */
+
+ for(i=0; i<2; i++) {
+ g = &glyphs[i];
+ g->lsb = 0;
+ g->width = fmet.bbox[2];
+ g->xMin = 0;
+ g->yMin = 0;
+ }
+ g = &glyphs[0];
+ g->name = ".notdef";
+ g->xMax = fmet.bbox[2]*4/5;
+ g->yMax = fmet.bbox[3]*4/5;
+ g->entries = g->path = g->lastentry = 0;
+ /* make it look as a black square */
+ fg_rmoveto(g, 0.0, 0.0);
+ fg_rlineto(g, 0.0, (double)g->yMax);
+ fg_rlineto(g, (double)g->xMax, (double)g->yMax);
+ fg_rlineto(g, (double)g->xMax, 0.0);
+ fg_rlineto(g, 0.0, 0.0);
+ g_closepath(g);
+ glpaths[0] = g->entries;
+ g->entries = 0;
+ g->ttf_pathlen = 4;
+
+ g = &glyphs[1];
+ g->name = ".null";
+ g->xMax = g->yMax = 0;
+ g->ttf_pathlen = 0;
+
+ if(readfile(bdf_file, handle_glyphs) < 0) {
+ fprintf(stderr, "**** file does not contain the ENDFONT line\n");
+ exit(1);
+ }
+ got_glyphs = 1;
+}
+
+/*
+ * Open font and prepare to return information to the main driver.
+ * May print error and warning messages.
+ * Exit on error.
+ */
+
+static void
+openfont(
+ char *fname,
+ char *arg /* unused now */
+)
+{
+ struct line *cl;
+ int i, l;
+
+ if ((bdf_file = fopen(fname, "r")) == NULL) {
+ fprintf(stderr, "**** Cannot open file '%s'\n", fname);
+ exit(1);
+ } else {
+ WARNING_2 fprintf(stderr, "Processing file %s\n", fname);
+ }
+
+ lineno = 1;
+
+ for(cl = header; cl->name != 0; cl++)
+ cl->flags &= ~IS_SEEN;
+ if(readfile(bdf_file, handle_header) < 0) {
+ fprintf(stderr, "**** file does not contain the CHARS definition\n");
+ exit(1);
+ }
+ for(cl = header; cl->name != 0; cl++) {
+ if( (cl->flags & MUST_SEE) && !(cl->flags & IS_SEEN) ) {
+ fprintf(stderr, "**** mandatory property %sis not found in the input line\n",
+ cl->name); /* cl->name has a space at the end */
+ exit(1);
+ }
+
+ /* set a few defaults */
+ if( !(cl->flags & IS_SEEN) ) {
+ if(cl->vp[0] == &fmet.underline_thickness) {
+ fmet.underline_thickness = 1;
+ } else if(cl->vp[0] == &fmet.underline_position) {
+ fmet.underline_position = fmet.bbox[1] + fmet.underline_thickness
+ - (pixel_size - fmet.bbox[3]);
+ } else if(cl->vp[0] == &fmet.ascender) {
+ fmet.ascender = fmet.bbox[2] + fmet.bbox[0];
+ } else if(cl->vp[0] == &fmet.descender) {
+ fmet.descender = fmet.bbox[0];
+ }
+ }
+ }
+
+ nglyphs += 2; /* add empty glyph and .notdef */
+
+ /* postprocessing to compensate for the differences in the metric formats */
+ fmet.bbox[2] += fmet.bbox[0];
+ fmet.bbox[3] += fmet.bbox[1];
+
+ scale = 1000/pixel_size; /* XXX ? */
+ if(scale*pixel_size < 950) {
+ scale = 1;
+ scale_external = 1;
+ fmet.units_per_em = pixel_size;
+ } else {
+ scale_external = 0;
+ fmet.units_per_em = scale*pixel_size;
+
+ fmet.underline_position *= scale;
+ fmet.underline_thickness *= scale;
+ fmet.ascender *= scale;
+ fmet.descender *= scale;
+ for(i=0; i<4; i++)
+ fmet.bbox[i] *= scale;
+ }
+
+ fmet.italic_angle = 0.0;
+ if(spacing == 0 /* possibly an old font */
+ || toupper(spacing[0]) != 'P') /* or anything non-proportional */
+ fmet.is_fixed_pitch = 1;
+ else
+ fmet.is_fixed_pitch = 0;
+
+ if(fmet.name_copyright==NULL)
+ fmet.name_copyright = "";
+
+ /* create the full name */
+ l = strlen(fmet.name_family)
+ + (fmet.name_style? strlen(fmet.name_style) : 0)
+ + (fnwidth? strlen(fnwidth) : 0)
+ + strlen("Oblique") + 1;
+
+ if(( fmet.name_full = malloc(l) )==NULL) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ strcpy(fmet.name_full, fmet.name_family);
+ if(fnwidth && strcmp(fnwidth, "Normal")) {
+ strcat(fmet.name_full, fnwidth);
+ }
+ if(fmet.name_style && strcmp(fmet.name_style, "Medium")) {
+ strcat(fmet.name_full, fmet.name_style);
+ }
+ switch(toupper(slant[0])) {
+ case 'O':
+ strcat(fmet.name_full, "Oblique");
+ break;
+ case 'I':
+ strcat(fmet.name_full, "Italic");
+ break;
+ }
+
+ fmet.name_ps = fmet.name_full;
+ fmet.name_version = "1.0";
+
+ if(charset_reg && charset_enc
+ && !strcmp(charset_reg, "iso10646") && !strcmp(charset_enc, "1"))
+ is_unicode = 1;
+
+ if(( fontenc = calloc(nglyphs, sizeof *fontenc) )==NULL) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ for(i=0; i<nglyphs; i++)
+ fontenc[i] = -1;
+ if(( glpaths = calloc(nglyphs, sizeof *glpaths) )==NULL) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+}
+
+/*
+ * Close font.
+ * Exit on error.
+ */
+
+static void
+closefont(
+ void
+)
+{
+ if(fclose(bdf_file) < 0) {
+ WARNING_1 fprintf(stderr, "Errors when closing the font file, ignored\n");
+ }
+}
+
+/*
+ * Get the number of glyphs in font.
+ */
+
+static int
+getnglyphs (
+ void
+)
+{
+ return nglyphs;
+}
+
+/*
+ * Get the names of the glyphs.
+ * Returns 0 if the names were assigned, non-zero if the font
+ * provides no glyph names.
+ */
+
+static int
+glnames(
+ GLYPH *glyph_list
+)
+{
+ readglyphs(glyph_list);
+ return 0;
+}
+
+/*
+ * Get the original encoding of the font.
+ * Returns 1 for if the original encoding is Unicode, 2 if the
+ * original encoding is other 16-bit, 0 if 8-bit.
+ */
+
+static int
+glenc(
+ GLYPH *glyph_list,
+ int *encoding,
+ int *unimap
+)
+{
+ int i, douni, e;
+
+ if(is_unicode || forcemap)
+ douni = 1;
+ else
+ douni = 0;
+
+ for(i=0; i<nglyphs; i++) {
+ e = fontenc[i];
+ if(douni)
+ e = unicode_rev_lookup(e);
+ if(e>=0 && e<ENCTABSZ && encoding[e] == -1)
+ encoding[e] = i;
+ }
+
+ if(is_unicode)
+ return 1;
+ else if(maxenc > 255)
+ return 2;
+ else
+ return 0;
+}
+
+/*
+ * Get the font metrics
+ */
+static void
+fnmetrics(
+ struct font_metrics *fm
+)
+{
+ *fm = fmet;
+}
+
+/*
+ * Get the path of contrours for a glyph.
+ */
+
+static void
+glpath(
+ int glyphno,
+ GLYPH *glyf_list
+)
+{
+ readglyphs(glyf_list);
+ glyf_list[glyphno].entries = glpaths[glyphno];
+ glpaths[glyphno] = 0;
+}
+
+/*
+ * Get the kerning data.
+ */
+
+static void
+kerning(
+ GLYPH *glyph_list
+)
+{
+ return; /* no kerning in BDF */
+}
--- /dev/null
+/*
+ * Handling of the bitmapped glyphs
+ *
+ * Copyright (c) 2001 by the TTF2PT1 project
+ * Copyright (c) 2001 by Sergey Babkin
+ *
+ * see COPYRIGHT for the full copyright notice
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include "pt1.h"
+#include "global.h"
+
+/* possible values of limits */
+#define L_NONE 0 /* nothing here */
+#define L_ON 1 /* black is on up/right */
+#define L_OFF 2 /* black is on down/left */
+
+static int warnedhints = 0;
+
+
+#ifdef USE_AUTOTRACE
+#include <autotrace/autotrace.h>
+
+/*
+ * Produce an autotraced outline from a bitmap.
+ * scale - factor to scale the sizes
+ * bmap - array of dots by lines, xsz * ysz
+ * xoff, yoff - offset of the bitmap's lower left corner
+ * from the logical position (0,0)
+ */
+
+static void
+autotraced_bmp_outline(
+ GLYPH *g,
+ int scale,
+ char *bmap,
+ int xsz,
+ int ysz,
+ int xoff,
+ int yoff
+)
+{
+ at_bitmap_type atb;
+ at_splines_type *atsp;
+ at_fitting_opts_type *atoptsp;
+ at_spline_list_type *slp;
+ at_spline_type *sp;
+ int i, j, k;
+ double lastx, lasty;
+ double fscale;
+ char *xbmap;
+
+ fscale = (double)scale;
+
+ /* provide a white margin around the bitmap */
+ xbmap = malloc((ysz+2)*(xsz+2));
+ if(xbmap == 0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ memset(xbmap, 0, xsz+2); /* top margin */
+ for(i=0, j=xsz+2; i<ysz; i++, j+=xsz+2) {
+ xbmap[j] = 0; /* left margin */
+ memcpy(&xbmap[j+1], &bmap[xsz*(ysz-1-i)], xsz); /* a line of bitmap */
+ xbmap[j+xsz+1] = 0; /* right margin */
+ }
+ memset(xbmap+j, 0, xsz+2); /* bottom margin */
+ xoff--; yoff-=2; /* compensate for the margins */
+
+ atoptsp = at_fitting_opts_new();
+
+ atb.width = xsz+2;
+ atb.height = ysz+2;
+ atb.np = 1;
+ atb.bitmap = xbmap;
+
+ atsp = at_splines_new(&atb, atoptsp);
+
+ lastx = lasty = -1.;
+ for(i=0; i<atsp->length; i++) {
+ slp = &atsp->data[i];
+#if 0
+ fprintf(stderr, "%s: contour %d: %d entries clockwise=%d color=%02X%02X%02X\n",
+ g->name, i, slp->length, slp->clockwise, slp->color.r, slp->color.g, slp->color.b);
+#endif
+ if(slp->length == 0)
+ continue;
+#if 0
+ if(slp->color.r + slp->color.g + slp->color.b == 0)
+ continue;
+#endif
+ fg_rmoveto(g, fscale*(slp->data[0].v[0].x+xoff), fscale*(slp->data[0].v[0].y+yoff));
+ for(j=0; j<slp->length; j++) {
+#if 0
+ fprintf(stderr, " ");
+ for(k=0; k<4; k++)
+ fprintf(stderr, "(%g %g) ",
+ fscale*(slp->data[j].v[k].x+xoff),
+ fscale*(ysz-slp->data[j].v[k].y+yoff)
+ );
+ fprintf(stderr, "\n");
+#endif
+ fg_rrcurveto(g,
+ fscale*(slp->data[j].v[1].x+xoff), fscale*(slp->data[j].v[1].y+yoff),
+ fscale*(slp->data[j].v[2].x+xoff), fscale*(slp->data[j].v[2].y+yoff),
+ fscale*(slp->data[j].v[3].x+xoff), fscale*(slp->data[j].v[3].y+yoff) );
+ }
+ g_closepath(g);
+ }
+
+ at_splines_free(atsp);
+ at_fitting_opts_free(atoptsp);
+ free(xbmap);
+}
+
+#endif /*USE_AUTOTRACE*/
+
+/* an extension of gentry for description of the fragments */
+typedef struct gex_frag GEX_FRAG;
+struct gex_frag {
+ /* indexes to len, the exact values and order are important */
+#define GEXFI_NONE -1
+#define GEXFI_CONVEX 0
+#define GEXFI_CONCAVE 1
+#define GEXFI_LINE 2 /* a line with steps varying by +-1 pixel */
+#define GEXFI_EXACTLINE 3 /* a line with exactly the same steps */
+#define GEXFI_COUNT 4 /* maximal index + 1 */
+ unsigned short len[GEXFI_COUNT]; /* length of various fragment types starting here */
+ unsigned short lenback[GEXFI_COUNT]; /* length back to the start of curve */
+
+ signed char ixstart; /* index of the frag type that starts here */
+ signed char ixcont; /* index of the frag type that continues here */
+
+ short flags;
+#define GEXFF_HLINE 0x0001 /* the exact line is longer in "horizontal" dimension */
+#define GEXFF_EXTR 0x0002 /* this gentry is an extremum in some direction */
+#define GEXFF_CIRC 0x0004 /* the joint at this gentry is for a circular curve */
+#define GEXFF_DRAWCURVE 0x0008 /* vect[] describes a curve to draw */
+#define GEXFF_DRAWLINE 0x0010 /* vect[] describes a line to draw */
+#define GEXFF_SPLIT 0x0020 /* is a result of splitting a line */
+#define GEXFF_SYMNEXT 0x0040 /* this subfrag is symmetric with next one */
+#define GEXFF_DONE 0x0080 /* this subfrag has been vectorized */
+#define GEXFF_LONG 0x0100 /* this gentry is longer than 1 pixel */
+
+ unsigned short aidx; /* index of gentry in the array representing the contour */
+
+ unsigned short vectlen; /* number of gentries represented by vect[] */
+
+ /* coordinates for vectored replacement of this fragment */
+ /* (already scaled because it's needed for curve approximation) */
+ double vect[4 /*ref.points*/][2 /*X,Y*/];
+
+ double bbox[2 /*X,Y*/]; /* absolute sizes of bounding box of a subfragment */
+
+ /* used when splitting the curved frags into subfrags */
+ GENTRY *prevsub; /* to gentries describing neighboring subfrags */
+ GENTRY *nextsub;
+ GENTRY *ordersub; /* single-linked list describing the order of calculation */
+
+ int sublen; /* length of this subfrag */
+ /* the symmetry across the subfrags */
+ int symaxis; /* the symmetry axis, with next subfrag */
+ int symxlen; /* min length of adjacent symmetric frags */
+ /* the symmetry within this subfrag (the axis is always diagonal) */
+ GENTRY *symge; /* symge->i{x,y}3 is the symmetry point of symge==0 if none */
+
+};
+#define X_FRAG(ge) ((GEX_FRAG *)((ge)->ext))
+
+/* various interesting tables related to GEX_FRAG */
+static char *gxf_name[GEXFI_COUNT] = {"Convex", "Concave", "Line", "ExLine"};
+static int gxf_cvk[2] = {-1, 1}; /* coefficients of concaveness */
+
+/*
+ * Dump the contents of X_EXT()->len and ->lenback for a contour
+ */
+static void
+gex_dump_contour(
+ GENTRY *ge,
+ int clen
+)
+{
+ int i, j;
+
+ for(j = 0; j < GEXFI_COUNT; j++) {
+ fprintf(stderr, "%-8s", gxf_name[j]);
+ for(i = 0; i < clen; i++, ge = ge->frwd)
+ fprintf(stderr, " %2d", X_FRAG(ge)->len[j]);
+ fprintf(stderr, " %p\n (back) ", ge);
+ for(i = 0; i < clen; i++, ge = ge->frwd)
+ fprintf(stderr, " %2d", X_FRAG(ge)->lenback[j]);
+ fprintf(stderr, "\n");
+ }
+}
+
+/*
+ * Calculate values of X_EXT()->lenback[] for all entries in
+ * a contour. The contour is identified by:
+ * ge - any gentry of the contour
+ * clen - contour length
+ */
+
+static void
+gex_calc_lenback(
+ GENTRY *ge,
+ int clen
+)
+{
+ int i, j;
+ int end;
+ GEX_FRAG *f;
+ int len[GEXFI_COUNT]; /* length of the most recent fragment */
+ int count[GEXFI_COUNT]; /* steps since beginning of the fragment */
+
+ for(j = 0; j < GEXFI_COUNT; j++)
+ len[j] = count[j] = 0;
+
+ end = clen;
+ for(i = 0; i < end; i++, ge = ge->frwd) {
+ f = X_FRAG(ge);
+ for(j = 0; j < GEXFI_COUNT; j++) {
+ if(len[j] != count[j]) {
+ f->lenback[j] = count[j]++;
+ } else
+ f->lenback[j] = 0;
+ if(f->len[j] != 0) {
+ len[j] = f->len[j];
+ count[j] = 1; /* start with the next gentry */
+ /* if the fragment will wrap over the start, process to its end */
+ if(i < clen && i + len[j] > end)
+ end = i + len[j];
+ }
+ }
+ }
+ gex_dump_contour(ge, clen);
+}
+
+/* Limit a curve to not exceed the given coordinates
+ * at its given side
+ */
+
+static void
+limcurve(
+ double curve[4][2 /*X,Y*/],
+ double lim[2 /*X,Y*/],
+ int where /* 0 - start, 3 - end */
+)
+{
+ int other = 3-where; /* the other end */
+ int sgn[2 /*X,Y*/]; /* sign for comparison */
+ double t, from, to, nt, t2, nt2, tt[4];
+ double val[2 /*X,Y*/];
+ int i;
+
+ for(i=0; i<2; i++)
+ sgn[i] = fsign(curve[other][i] - curve[where][i]);
+
+#if 0
+ fprintf(stderr, " limit (%g,%g)-(%g,%g) at %d by (%g,%g), sgn(%d,%d)\n",
+ curve[0][0], curve[0][1], curve[3][0], curve[3][1],
+ where, lim[0], lim[1], sgn[0], sgn[1]);
+#endif
+ /* a common special case */
+ if( sgn[0]*(curve[where][0] - lim[0]) >= 0.
+ && sgn[1]*(curve[where][1] - lim[1]) >= 0. )
+ return; /* nothing to do */
+
+ if(other==0) {
+ from = 0.;
+ to = 1.;
+ } else {
+ from = 1.;
+ to = 0.;
+ }
+#if 0
+ fprintf(stderr, "t=");
+#endif
+ while( fabs(from-to) > 0.00001 ) {
+ t = 0.5 * (from+to);
+ t2 = t*t;
+ nt = 1.-t;
+ nt2 = nt*nt;
+ tt[0] = nt2*nt;
+ tt[1] = 3*nt2*t;
+ tt[2] = 3*nt*t2;
+ tt[3] = t*t2;
+ for(i=0; i<2; i++)
+ val[i] = curve[0][i]*tt[0] + curve[1][i]*tt[1]
+ + curve[2][i]*tt[2] + curve[3][i]*tt[3];
+#if 0
+ fprintf(stderr, "%g(%g,%g) ", t, val[0], val[1]);
+#endif
+ if(fabs(val[0] - lim[0]) < 0.1
+ || fabs(val[1] - lim[1]) < 0.1)
+ break;
+
+ if(sgn[0] * (val[0] - lim[0]) < 0.
+ || sgn[1] * (val[1] - lim[1]) < 0.)
+ to = t;
+ else
+ from = t;
+ }
+ /* now t is the point of splitting */
+#define SPLIT(pt1, pt2) ( (pt1) + t*((pt2)-(pt1)) ) /* order is important! */
+ for(i=0; i<2; i++) {
+ double v11, v12, v13, v21, v22, v31; /* intermediate points */
+
+ v11 = SPLIT(curve[0][i], curve[1][i]);
+ v12 = SPLIT(curve[1][i], curve[2][i]);
+ v13 = SPLIT(curve[2][i], curve[3][i]);
+ v21 = SPLIT(v11, v12);
+ v22 = SPLIT(v12, v13);
+ v31 = SPLIT(v21, v22);
+ if(other==0) {
+ curve[1][i] = v11;
+ curve[2][i] = v21;
+ curve[3][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31;
+ } else {
+ curve[0][i] = fabs(v31 - lim[i]) < 0.1 ? lim[i] : v31;
+ curve[1][i] = v22;
+ curve[2][i] = v13;
+ }
+ }
+#undef SPLIT
+#if 0
+ fprintf(stderr, "\n");
+#endif
+}
+
+/*
+ * Vectorize a subfragment of a curve fragment. All the data has been already
+ * collected by this time
+ */
+
+static void
+dosubfrag(
+ GLYPH *g,
+ int fti, /* fragment type index */
+ GENTRY *firstge, /* first gentry of fragment */
+ GENTRY *ge, /* first gentry of subfragment */
+ double fscale
+)
+{
+ GENTRY *gel, *gei; /* last gentry of this subfrag */
+ GEX_FRAG *f, *ff, *lf, *pf, *xf;
+ /* maximal amount of space that can be used at the beginning and the end */
+ double fixfront[2], fixend[2]; /* fixed points - used to show direction */
+ double mvfront[2], mvend[2]; /* movable points */
+ double limfront[2], limend[2]; /* limit of movement for movabel points */
+ double sympt;
+ int outfront, outend; /* the beginning/end is going outwards */
+ int symfront, symend; /* a ready symmetric fragment is present at front/end */
+ int drnd[2 /*X,Y*/]; /* size of the round part */
+ int i, j, a1, a2, ndots;
+ double avg2, max2; /* squared distances */
+ struct dot_dist *dots, *usedots;
+
+ ff = X_FRAG(firstge);
+ f = X_FRAG(ge);
+ gel = f->nextsub;
+ lf = X_FRAG(gel);
+ if(f->prevsub != 0)
+ pf = X_FRAG(f->prevsub);
+ else
+ pf = 0;
+
+ for(i=0; i<2; i++)
+ drnd[i] = gel->bkwd->ipoints[i][2] - ge->ipoints[i][2];
+
+ if(f->prevsub==0 && f->ixcont == GEXFI_NONE) {
+ /* nothing to join with : may use the whole length */
+ for(i = 0; i < 2; i++)
+ limfront[i] = ge->bkwd->ipoints[i][2];
+ } else {
+ /* limit to a half */
+ for(i = 0; i < 2; i++)
+ limfront[i] = 0.5 * (ge->ipoints[i][2] + ge->bkwd->ipoints[i][2]);
+ }
+ if( (ge->ix3 == ge->bkwd->ix3) /* vert */
+ ^ (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3))
+ ^ (fti == GEXFI_CONCAVE) /* counter-clockwise */ ) {
+ /* the beginning is not a flat 90-degree end */
+ outfront = 1;
+ for(i = 0; i < 2; i++)
+ fixfront[i] = ge->frwd->ipoints[i][2];
+ } else {
+ outfront = 0;
+ for(i = 0; i < 2; i++)
+ fixfront[i] = ge->ipoints[i][2];
+ }
+
+ if(lf->nextsub==0 && lf->ixstart == GEXFI_NONE) {
+ /* nothing to join with : may use the whole length */
+ for(i = 0; i < 2; i++)
+ limend[i] = gel->ipoints[i][2];
+ } else {
+ /* limit to a half */
+ for(i = 0; i < 2; i++)
+ limend[i] = 0.5 * (gel->ipoints[i][2] + gel->bkwd->ipoints[i][2]);
+ }
+ gei = gel->bkwd->bkwd;
+ if( (gel->ix3 == gel->bkwd->ix3) /* vert */
+ ^ (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3))
+ ^ (fti == GEXFI_CONVEX) /* clockwise */ ) {
+ /* the end is not a flat 90-degree end */
+ outend = 1;
+ for(i = 0; i < 2; i++)
+ fixend[i] = gel->bkwd->bkwd->ipoints[i][2];
+ } else {
+ outend = 0;
+ for(i = 0; i < 2; i++)
+ fixend[i] = gel->bkwd->ipoints[i][2];
+ }
+
+ for(i = 0; i < 2; i++) {
+ fixfront[i] *= fscale;
+ limfront[i] *= fscale;
+ fixend[i] *= fscale;
+ limend[i] *= fscale;
+ }
+
+ fprintf(stderr, " %d out(%d[%d %d %d],%d[%d %d %d]) drnd(%d, %d)\n",
+ fti,
+ outfront,
+ (ge->ix3 == ge->bkwd->ix3),
+ (isign(ge->bkwd->ix3 - ge->frwd->ix3)==isign(ge->bkwd->iy3 - ge->frwd->iy3)),
+ (fti == GEXFI_CONCAVE),
+ outend,
+ (gel->ix3 == gel->bkwd->ix3),
+ (isign(gel->ix3 - gei->ix3)==isign(gel->iy3 - gei->iy3)),
+ (fti == GEXFI_CONVEX),
+ drnd[0], drnd[1]);
+
+ /* prepare to calculate the distances */
+ ndots = f->sublen - 1;
+ dots = malloc(sizeof(*dots) * ndots);
+ if(dots == 0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ for(i = 0, gei = ge; i < ndots; i++, gei = gei->frwd) {
+ for(a1 = 0; a1 < 2; a1++)
+ dots[i].p[a1] = fscale * gei->ipoints[a1][2];
+ }
+
+ /* see if we can mirror a ready symmetric curve */
+
+ /* check symmetry with the fragment before this */
+ symfront = (pf != 0 && (pf->flags & GEXFF_SYMNEXT) && (pf->flags & GEXFF_DONE)
+ && ( outend && f->sublen <= pf->sublen
+ || ( pf->sublen == f->sublen
+ && (lf->sublen == 0
+ || ( abs(limfront[0]-limend[0]) >= abs(pf->vect[0][0]-pf->vect[3][0])
+ && abs(limfront[1]-limend[1]) >= abs(pf->vect[0][1]-pf->vect[3][1]) ))
+ )
+ )
+ );
+ /* check symmetry with the fragment after this */
+ symend = ( (f->flags & GEXFF_SYMNEXT) && (lf->flags & GEXFF_DONE)
+ && ( outfront && f->sublen <= lf->sublen
+ || ( lf->sublen == f->sublen
+ && (pf == 0
+ || ( abs(limfront[0]-limend[0]) >= abs(lf->vect[0][0]-lf->vect[3][0])
+ && abs(limfront[1]-limend[1]) >= abs(lf->vect[0][1]-lf->vect[3][1]) ))
+ )
+ )
+ );
+ if(symfront || symend) {
+ /* mirror the symmetric neighbour subfrag */
+ if(symfront) {
+ a1 = (ge->ix3 != ge->bkwd->ix3); /* the symmetry axis */
+ a2 = !a1; /* the other axis (goes along the extremum gentry) */
+
+ /* the symmetry point on a2 */
+ sympt = fscale * 0.5 * (ge->ipoints[a2][2] + ge->bkwd->ipoints[a2][2]);
+ xf = pf; /* the symmetric fragment */
+ } else {
+ a1 = (gel->ix3 != gel->bkwd->ix3); /* the symmetry axis */
+ a2 = !a1; /* the other axis (goes along the extremum gentry) */
+
+ /* the symmetry point on a2 */
+ sympt = fscale * 0.5 * (gel->ipoints[a2][2] + gel->bkwd->ipoints[a2][2]);
+ xf = lf; /* the symmetric fragment */
+ }
+ fprintf(stderr, " sym with %p f=%d(%p) e=%d(%p) a1=%c a2=%c sympt=%g\n",
+ xf, symfront, pf, symend, lf,
+ a1 ? 'Y': 'X', a2 ? 'Y': 'X', sympt
+ );
+ for(i=0; i<4; i++) {
+ f->vect[3-i][a1] = xf->vect[i][a1];
+ f->vect[3-i][a2] = sympt - (xf->vect[i][a2]-sympt);
+ }
+ if(symfront) {
+ if(outend || lf->sublen==0)
+ limcurve(f->vect, limend, 3);
+ } else {
+ if(outfront || pf == 0)
+ limcurve(f->vect, limfront, 0);
+ }
+ avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2);
+ fprintf(stderr, " avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale);
+ if(max2 <= fscale*fscale) {
+ f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE);
+ f->vectlen = f->sublen;
+ free(dots);
+ return;
+ }
+ }
+
+ if( !outfront && !outend && f->symge != 0) {
+ /* a special case: try a circle segment as an approximation */
+ double lenfront, lenend, len, maxlen;
+
+ /* coefficient for a Bezier approximation of a circle */
+#define CIRCLE_FRAC 0.55
+
+ a1 = (ge->ix3 == ge->bkwd->ix3); /* get the axis along the front */
+ a2 = !a1; /* axis along the end */
+
+ lenfront = fixfront[a1] - limfront[a1];
+ lenend = fixend[a2] - limend[a2];
+ if(fabs(lenfront) < fabs(lenend))
+ len = fabs(lenfront);
+ else
+ len = fabs(lenend);
+
+ /* make it go close to the round shape */
+ switch(f->sublen) {
+ case 2:
+ maxlen = fscale;
+ break;
+ case 4:
+ case 6:
+ maxlen = fscale * 2.;
+ break;
+ default:
+ maxlen = fscale * abs(ge->frwd->frwd->ipoints[a1][2]
+ - ge->ipoints[a1][2]);
+ break;
+ }
+ if(len > maxlen)
+ len = maxlen;
+
+ mvfront[a1] = fixfront[a1] - fsign(lenfront) * len;
+ mvfront[a2] = limfront[a2];
+ mvend[a2] = fixend[a2] - fsign(lenend) * len;
+ mvend[a1] = limend[a1];
+
+ for(i=0; i<2; i++) {
+ f->vect[0][i] = mvfront[i];
+ f->vect[3][i] = mvend[i];
+ }
+ f->vect[1][a1] = mvfront[a1] + CIRCLE_FRAC*(mvend[a1]-mvfront[a1]);
+ f->vect[1][a2] = mvfront[a2];
+ f->vect[2][a1] = mvend[a1];
+ f->vect[2][a2] = mvend[a2] + CIRCLE_FRAC*(mvfront[a2]-mvend[a2]);
+
+ avg2 = fdotcurvdist2(f->vect, dots, ndots, &max2);
+ fprintf(stderr, " avg=%g max=%g fscale=%g\n", sqrt(avg2), sqrt(max2), fscale);
+ if(max2 <= fscale*fscale) {
+ f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE);
+ f->vectlen = f->sublen;
+ free(dots);
+ return;
+ }
+#undef CIRCLE_FRAC
+ }
+ for(i=0; i<2; i++) {
+ f->vect[0][i] = limfront[i];
+ f->vect[1][i] = fixfront[i];
+ f->vect[2][i] = fixend[i];
+ f->vect[3][i] = limend[i];
+ }
+ usedots = dots;
+ if(outfront) {
+ usedots++; ndots--;
+ }
+ if(outend)
+ ndots--;
+ if( fcrossrayscv(f->vect, NULL, NULL) == 0) {
+ fprintf(stderr, "**** Internal error: rays must cross but don't at %p-%p\n",
+ ge, gel);
+ fprintf(stderr, " (%g, %g) (%g, %g) (%g, %g) (%g, %g)\n",
+ limfront[0], limfront[1],
+ fixfront[0], fixfront[1],
+ fixend[0], fixend[1],
+ limend[0], limend[1]
+ );
+ dumppaths(g, NULL, NULL);
+ exit(1);
+ } else {
+ if(ndots != 0)
+ fapproxcurve(f->vect, usedots, ndots);
+ f->flags |= (GEXFF_DONE | GEXFF_DRAWCURVE);
+ f->vectlen = f->sublen;
+ }
+ free(dots);
+}
+
+/*
+ * Produce an outline from a bitmap.
+ * scale - factor to scale the sizes
+ * bmap - array of dots by lines, xsz * ysz
+ * xoff, yoff - offset of the bitmap's lower left corner
+ * from the logical position (0,0)
+ */
+
+void
+bmp_outline(
+ GLYPH *g,
+ int scale,
+ char *bmap,
+ int xsz,
+ int ysz,
+ int xoff,
+ int yoff
+)
+{
+ char *hlm, *vlm; /* arrays of the limits of outlines */
+ char *amp; /* map of ambiguous points */
+ int x, y;
+ char *ip, *op;
+ double fscale;
+
+ if(xsz==0 || ysz==0)
+ return;
+
+#ifdef USE_AUTOTRACE
+ if(use_autotrace) {
+ autotraced_bmp_outline(g, scale, bmap, xsz, ysz, xoff, yoff);
+ return;
+ }
+#endif /*USE_AUTOTRACE*/
+
+ fscale = (double)scale;
+ g->flags &= ~GF_FLOAT; /* build it as int first */
+
+ if(!warnedhints) {
+ warnedhints = 1;
+ if(hints && subhints) {
+ WARNING_2 fprintf(stderr,
+ "Use of hint substitution on bitmap fonts is not recommended\n");
+ }
+ }
+
+#if 0
+ printbmap(bmap, xsz, ysz, xoff, yoff);
+#endif
+
+ /* now find the outlines */
+ hlm=calloc( xsz, ysz+1 ); /* horizontal limits */
+ vlm=calloc( xsz+1, ysz ); /* vertical limits */
+ amp=calloc( xsz, ysz ); /* ambiguous points */
+
+ if(hlm==0 || vlm==0 || amp==0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+
+ /*
+ * hlm and vlm represent a grid of horisontal and
+ * vertical lines. Each pixel is surrounded by the grid
+ * from all the sides. The values of [hv]lm mark the
+ * parts of grid where the pixel value switches from white
+ * to black and back.
+ */
+
+ /* find the horizontal limits */
+ ip=bmap; op=hlm;
+ /* 1st row */
+ for(x=0; x<xsz; x++) {
+ if(ip[x])
+ op[x]=L_ON;
+ }
+ ip+=xsz; op+=xsz;
+ /* internal rows */
+ for(y=1; y<ysz; y++) {
+ for(x=0; x<xsz; x++) {
+ if(ip[x]) {
+ if(!ip[x-xsz])
+ op[x]=L_ON;
+ } else {
+ if(ip[x-xsz])
+ op[x]=L_OFF;
+ }
+ }
+ ip+=xsz; op+=xsz;
+ }
+
+ /* last row */
+ ip-=xsz;
+ for(x=0; x<xsz; x++) {
+ if(ip[x])
+ op[x]=L_OFF;
+ }
+
+ /* find the vertical limits */
+ ip=bmap; op=vlm;
+ for(y=0; y<ysz; y++) {
+ if(ip[0])
+ op[0]=L_ON;
+ for(x=1; x<xsz; x++) {
+ if(ip[x]) {
+ if(!ip[x-1])
+ op[x]=L_ON;
+ } else {
+ if(ip[x-1])
+ op[x]=L_OFF;
+ }
+ }
+ if(ip[xsz-1])
+ op[xsz]=L_OFF;
+ ip+=xsz; op+=xsz+1;
+ }
+
+ /*
+ * Ambiguous points are the nodes of the grids
+ * that are between two white and two black pixels
+ * located in a checkerboard style. Actually
+ * there are only two patterns that may be
+ * around an ambiguous point:
+ *
+ * X|. .|X
+ * -*- -*-
+ * .|X X|.
+ *
+ * where "|" and "-" represent the grid (respectively members
+ * of vlm and hlm), "*" represents an ambiguous point
+ * and "X" and "." represent black and white pixels.
+ *
+ * If these sample pattern occur in the lower left corner
+ * of the bitmap then this ambiguous point will be
+ * located at amp[1][1] or in other words amp[1*xsz+1].
+ *
+ * These points are named "ambiguous" because it's
+ * not easy to guess what did the font creator mean
+ * at these points. So we are going to treat them
+ * specially, doing no aggressive smoothing.
+ */
+
+ /* find the ambiguous points */
+ for(y=ysz-1; y>0; y--)
+ for(x=xsz-1; x>0; x--) {
+ if(bmap[y*xsz+x]) {
+ if( !bmap[y*xsz+x-1] && !bmap[y*xsz-xsz+x] && bmap[y*xsz-xsz+x-1] )
+ amp[y*xsz+x]=1;
+ } else {
+ if( bmap[y*xsz+x-1] && bmap[y*xsz-xsz+x] && !bmap[y*xsz-xsz+x-1] )
+ amp[y*xsz+x]=1;
+ }
+ }
+
+#if 0
+ printlimits(hlm, vlm, amp, xsz, ysz);
+#endif
+
+ /* generate the vectored (stepping) outline */
+
+ while(1) {
+ int found = 0;
+ int outer; /* flag: this is an outer contour */
+ int hor, newhor; /* flag: the current contour direction is horizontal */
+ int dir; /* previous direction of the coordinate, 1 - L_ON, 0 - L_OFF */
+ int startx, starty; /* start of a contour */
+ int firstx, firsty; /* start of the current line */
+ int newx, newy; /* new coordinates to try */
+ char *lm, val;
+ int maxx, maxy, xor;
+
+ for(y=ysz; !found && y>0; y--)
+ for(x=0; x<xsz; x++)
+ if(hlm[y*xsz+x] > L_NONE)
+ goto foundcontour;
+ break; /* have no contours left */
+
+ foundcontour:
+ ig_rmoveto(g, x+xoff, y+yoff); /* intermediate as int */
+
+ startx = firstx = x;
+ starty = firsty = y;
+
+ if(hlm[y*xsz+x] == L_OFF) {
+ outer = 1; dir = 0;
+ hlm[y*xsz+x] = -hlm[y*xsz+x]; /* mark as seen */
+ hor = 1; x++;
+ } else {
+ outer = 0; dir = 0;
+ hor = 0; y--;
+ vlm[y*(xsz+1)+x] = -vlm[y*(xsz+1)+x]; /* mark as seen */
+ }
+
+ while(x!=startx || y!=starty) {
+#if 0
+ printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir);
+#endif
+
+ /* initialization common for try1 and try2 */
+ if(hor) {
+ lm = vlm; maxx = xsz+1; maxy = ysz; newhor = 0;
+ } else {
+ lm = hlm; maxx = xsz; maxy = ysz+1; newhor = 1;
+ }
+ xor = (outer ^ hor ^ dir);
+
+ try1:
+ /* first we try to change axis, to keep the
+ * contour as long as possible
+ */
+
+ newx = x; newy = y;
+ if(!hor && (!outer ^ dir))
+ newx--;
+ if(hor && (!outer ^ dir))
+ newy--;
+
+ if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy)
+ goto try2;
+
+ if(!xor)
+ val = L_ON;
+ else
+ val = L_OFF;
+#if 0
+ printf("try 1, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx],
+ (newhor ? 'h':'v'), newx, newy);
+#endif
+ if( lm[newy*maxx + newx] == val )
+ goto gotit;
+
+ try2:
+ /* try to change the axis anyway */
+
+ newx = x; newy = y;
+ if(!hor && (outer ^ dir))
+ newx--;
+ if(hor && (outer ^ dir))
+ newy--;
+
+ if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy)
+ goto try3;
+
+ if(xor)
+ val = L_ON;
+ else
+ val = L_OFF;
+#if 0
+ printf("try 2, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx],
+ (newhor ? 'h':'v'), newx, newy);
+#endif
+ if( lm[newy*maxx + newx] == val )
+ goto gotit;
+
+ try3:
+ /* try to continue in the old direction */
+
+ if(hor) {
+ lm = hlm; maxx = xsz; maxy = ysz+1;
+ } else {
+ lm = vlm; maxx = xsz+1; maxy = ysz;
+ }
+ newhor = hor;
+ newx = x; newy = y;
+ if(hor && dir)
+ newx--;
+ if(!hor && !dir)
+ newy--;
+
+ if(newx < 0 || newx >= maxx || newy < 0 || newy >= maxy)
+ goto badtry;
+
+ if(dir)
+ val = L_ON;
+ else
+ val = L_OFF;
+#if 0
+ printf("try 3, want %d have %d at %c(%d, %d)\n", val, lm[newy*maxx + newx],
+ (newhor ? 'h':'v'), newx, newy);
+#endif
+ if( lm[newy*maxx + newx] == val )
+ goto gotit;
+
+ badtry:
+ fprintf(stderr, "**** Internal error in the contour detection code at (%d, %d)\n", x, y);
+ fprintf(stderr, "glyph='%s' outer=%d hor=%d dir=%d\n", g->name, outer, hor, dir);
+ fflush(stdout);
+ exit(1);
+
+ gotit:
+ if(hor != newhor) { /* changed direction, end the previous line */
+ ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */
+ firstx = x; firsty = y;
+ }
+ lm[newy*maxx + newx] = -lm[newy*maxx + newx];
+ hor = newhor;
+ dir = (val == L_ON);
+ if(newhor)
+ x -= (dir<<1)-1;
+ else
+ y += (dir<<1)-1;
+ }
+#if 0
+ printf("trace (%d, %d) outer=%d hor=%d dir=%d\n", x, y, outer, hor, dir);
+#endif
+ ig_rlineto(g, x+xoff, y+yoff); /* intermediate as int */
+ g_closepath(g);
+ }
+
+
+ /* try to vectorize the curves and sloped lines in the bitmap */
+ if(vectorize) {
+ GENTRY *ge, *pge, *cge, *loopge;
+ int i;
+ int skip;
+
+ dumppaths(g, NULL, NULL);
+
+ /* allocate the extensions */
+ for(cge=g->entries; cge!=0; cge=cge->next) {
+ cge->ext = calloc(1, sizeof(GEX_FRAG) );
+ if(cge->ext == 0) {
+ fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
+ exit(255);
+ }
+ }
+
+ for(cge=g->entries; cge!=0; cge=cge->next) {
+ if(cge->type != GE_MOVE)
+ continue;
+
+ /* we've found the beginning of a contour */
+ {
+ int d, vert, count, stepmore, delaystop;
+ int vdir, hdir, fullvdir, fullhdir, len;
+ int dx, dy, lastdx, lastdy;
+ int k1, k2, reversal, smooth, good;
+ int line[2 /*H,V*/], maxlen[2 /*H,V*/], minlen[2 /*H,V*/];
+ GENTRY **age; /* array of gentries in a contour */
+ int clen; /* contour length, size of ths array */
+ int i, j;
+ GEX_FRAG *f;
+
+ /* we know that all the contours start at the top-left corner,
+ * so at most it might be before/after the last element of
+ * the last/first fragment
+ */
+
+ ge = cge->next;
+ pge = ge->bkwd;
+ if(ge->ix3 == pge->ix3) { /* a vertical line */
+ /* we want to start always from a horizontal line because
+ * then we always start from top and that is quaranteed to be a
+ * fragment boundary, so move the start point of the contour
+ */
+ pge->prev->next = pge->next;
+ pge->next->prev = pge->prev;
+ cge->next = pge;
+ pge->prev = cge;
+ pge->next = ge;
+ ge->prev = pge;
+ ge = pge; pge = ge->bkwd;
+ cge->ix3 = pge->ix3; cge->iy3 = pge->iy3;
+ }
+
+ /* fill the array of gentries */
+ clen = 1;
+ for(ge = cge->next->frwd; ge != cge->next; ge = ge->frwd)
+ clen++;
+ age = (GENTRY **)malloc(sizeof(*age) * clen);
+ ge = cge->next;
+ count = 0;
+ do {
+ age[count] = ge;
+ X_FRAG(ge)->aidx = count++;
+
+ /* and by the way find the extremums */
+ for(i=0; i<2; i++) {
+ if( isign(ge->frwd->ipoints[i][2] - ge->ipoints[i][2])
+ * isign(ge->bkwd->bkwd->ipoints[i][2] - ge->bkwd->ipoints[i][2]) == 1) {
+ X_FRAG(ge)->flags |= GEXFF_EXTR;
+ fprintf(stderr, " %s extremum at %p\n", (i?"vert":"hor"), ge);
+ }
+ if(abs(ge->ipoints[i][2] - ge->bkwd->ipoints[i][2]) > 1)
+ X_FRAG(ge)->flags |= GEXFF_LONG;
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ /* Find the convex and concave fragments, defined as:
+ * convex (clockwise): dy/dx <= dy0/dx0,
+ * or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx > 0
+ * concave (counter-clockwise): dy/dx >= dy0/dx0,
+ * or a reversal: dy/dx == - dy0/dx0 && abs(dxthis) == 1 && dy/dx < 0
+ *
+ * Where dx and dy are measured between the end of this gentry
+ * and the start of the previous one (dx0 and dy0 are the same
+ * thing calculated for the previous gentry and its previous one),
+ * dxthis is between the end and begginning of this gentry.
+ *
+ * A reversal is a situation when the curve changes its direction
+ * along the x axis, so it passes through a momentary vertical
+ * direction.
+ */
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ ge = cge->next;
+ pge = ge->bkwd; /* the beginning of the fragment */
+ count = 1;
+ lastdx = pge->ix3 - pge->bkwd->bkwd->ix3;
+ lastdy = pge->iy3 - pge->bkwd->bkwd->iy3;
+
+#define CHKCURVCONN(ge, msg) do { \
+ dx = (ge)->ix3 - (ge)->bkwd->bkwd->ix3; \
+ dy = (ge)->iy3 - (ge)->bkwd->bkwd->iy3; \
+ if(0 && msg) { \
+ fprintf(stderr, " %p: dx=%d dy=%d dx0=%d dy0=%d ", \
+ (ge), dx, dy, lastdx, lastdy); \
+ } \
+ k1 = X_FRAG(ge)->flags; \
+ k2 = X_FRAG((ge)->bkwd)->flags; \
+ if(0 && msg) { \
+ fprintf(stderr, "fl=%c%c%c%c ", \
+ (k1 & GEXFF_EXTR) ? 'X' : '-', \
+ (k1 & GEXFF_LONG) ? 'L' : '-', \
+ (k2 & GEXFF_EXTR) ? 'X' : '-', \
+ (k2 & GEXFF_LONG) ? 'L' : '-' \
+ ); \
+ } \
+ if( (k1 & GEXFF_EXTR) && (k2 & GEXFF_LONG) \
+ || (k2 & GEXFF_EXTR) && (k1 & GEXFF_LONG) ) { \
+ smooth = 0; \
+ good = reversal = -1; /* for debugging */ \
+ } else { \
+ k1 = dy * lastdx; \
+ k2 = lastdy * dx; \
+ smooth = (abs(dx)==1 || abs(dy)==1); \
+ good = (k1 - k2)*gxf_cvk[d] >= 0; \
+ if(smooth && !good) { \
+ reversal = (k1 == -k2 && abs((ge)->ix3 - (ge)->bkwd->ix3)==1 \
+ && dy*dx*gxf_cvk[d] < 0); \
+ } else \
+ reversal = 0; \
+ } \
+ if(0 && msg) { \
+ fprintf(stderr, "k1=%d k2=%d pge=%p count=%d %s good=%d rev=%d\n", \
+ k1, k2, pge, count, gxf_name[d], good, reversal); \
+ } \
+ } while(0)
+
+ do {
+ CHKCURVCONN(ge, 1);
+
+ if(smooth && (good || reversal) )
+ count++;
+ else {
+ /* can't continue */
+#if 0
+ if(count >= 4) { /* worth remembering */
+ fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
+ }
+#endif
+ X_FRAG(pge)->len[d] = count;
+ if(smooth) {
+ pge = ge->bkwd;
+ count = 2;
+ } else {
+ pge = ge;
+ count = 1;
+ }
+ }
+ lastdx = dx; lastdy = dy;
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ /* see if we can connect the last fragment to the first */
+ CHKCURVCONN(ge, 1);
+
+ if(smooth && (good || reversal) ) {
+ /* -1 to avoid ge->bkwd being counted twice */
+ if( X_FRAG(ge->bkwd)->len[d] >= 2 )
+ count += X_FRAG(ge->bkwd)->len[d] - 1;
+ else if(count == clen+1) {
+ /* we are joining a circular (closed) curve, check whether it
+ * can be joined at any point or whether it has a discontinuity
+ * at the point where we join it now
+ */
+ lastdx = dx; lastdy = dy;
+ CHKCURVCONN(ge->frwd, 0);
+
+ if(smooth && (good || reversal) ) {
+ /* yes, the curve is truly a circular one and can be
+ * joined at any point
+ */
+
+#if 0
+ fprintf(stderr, " found a circular joint point at %p\n", pge);
+#endif
+ /* make sure that in a circular fragment we start from an extremum */
+ while( ! (X_FRAG(pge)->flags & GEXFF_EXTR) )
+ pge = pge->frwd;
+ X_FRAG(pge)->flags |= GEXFF_CIRC;
+ }
+ }
+#if 0
+ fprintf(stderr, " %s joined %p to %p count=%d bk_count=%d\n", gxf_name[d], pge, ge->bkwd,
+ count, X_FRAG(ge->bkwd)->len[d] );
+#endif
+ X_FRAG(ge->bkwd)->len[d] = 0;
+ }
+ X_FRAG(pge)->len[d] = count;
+#if 0
+ if(count >= 4) { /* worth remembering */
+ fprintf(stderr, " %s last frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
+ }
+#endif
+#undef CHKCURVCONN
+
+ /* do postprocessing */
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+ len = f->len[d];
+#if 0
+ fprintf(stderr, " %p %s len=%d clen=%d\n", ge, gxf_name[d], len, clen);
+#endif
+ if(len < 3) /* get rid of the fragments that are too short */
+ f->len[d] = 0;
+ else if(len == 3) {
+ /* _
+ * drop the |_| - shaped fragments, leave alone the _| - shaped
+ * (and even those only if not too short in pixels),
+ * those left alone are further filtered later
+ */
+ k1 = (ge->ix3 == ge->bkwd->ix3); /* axis of the start */
+ if(isign(ge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2])
+ != isign(ge->frwd->ipoints[k1][2] - ge->frwd->frwd->ipoints[k1][2])
+ && abs(ge->frwd->frwd->ipoints[k1][2] - ge->bkwd->ipoints[k1][2]) > 2) {
+#if 0
+ fprintf(stderr, " %s frag %p count=%d good shape\n",
+ gxf_name[d], ge, count);
+#endif
+ } else
+ f->len[d] = 0;
+ } else if(len == clen+1)
+ break; /* a closed fragment, nothing else interesting */
+ else { /* only for open fragments */
+ GENTRY *gem, *gex, *gei, *ges;
+
+ ges = ge; /* the start entry */
+ gem = age[(f->aidx + f->len[d])%clen]; /* entry past the end of the fragment */
+
+ gei = ge->frwd;
+ if( (ge->ix3 == ge->bkwd->ix3) /* vert */
+ ^ (isign(ge->bkwd->ix3 - gei->ix3)==isign(ge->bkwd->iy3 - gei->iy3))
+ ^ !(d == GEXFI_CONVEX) /* counter-clockwise */ ) {
+
+#if 0
+ fprintf(stderr, " %p: %s potential spurious start\n", ge, gxf_name[d]);
+#endif
+ /* the beginning may be a spurious entry */
+
+ gex = 0; /* the extremum closest to the beginning - to be found */
+ for(gei = ge->frwd; gei != gem; gei = gei->frwd) {
+ if(X_FRAG(gei)->flags & GEXFF_EXTR) {
+ gex = gei;
+ break;
+ }
+ }
+ if(gex == 0)
+ gex = gem->bkwd;
+
+ /* A special case: ignore the spurious ends on small curves that
+ * either enclose an 1-pixel-wide extremum or are 1-pixel deep.
+ * Any 5-or-less-pixel-long curve with extremum 2 steps away
+ * qualifies for that.
+ */
+
+ if(len <= 5 && gex == ge->frwd->frwd) {
+ good = 0;
+#if 0
+ fprintf(stderr, " E");
+#endif
+ } else {
+ good = 1; /* assume that ge is not spurious */
+
+ /* gei goes backwards, gex goes forwards from the extremum */
+ gei = gex;
+ /* i is the symmetry axis, j is the other axis (X=0 Y=1) */
+ i = (gex->ix3 != gex->bkwd->ix3);
+ j = !i;
+ for( ; gei!=ge && gex!=gem; gei=gei->bkwd, gex=gex->frwd) {
+ if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2]
+ || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]
+ != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]
+ ) {
+ good = 0; /* no symmetry - must be spurious */
+#if 0
+ fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)",
+ gei, gex,
+ i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2],
+ j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2],
+ gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] );
+#endif
+ break;
+ }
+ }
+ if(gex == gem) { /* oops, the other side is too short */
+ good = 0;
+#if 0
+ fprintf(stderr, " X");
+#endif
+ }
+ if(good && gei == ge) {
+ if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2])
+ != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) {
+ good = 0; /* oops, goes into another direction */
+#if 0
+ fprintf(stderr, " D");
+#endif
+ }
+ }
+ }
+ if(!good) { /* it is spurious, drop it */
+#if 0
+ fprintf(stderr, " %p: %s spurious start\n", ge, gxf_name[d]);
+#endif
+ f->len[d] = 0;
+ ges = ge->frwd;
+ len--;
+ X_FRAG(ges)->len[d] = len;
+ }
+ }
+
+ gei = gem->bkwd->bkwd->bkwd;
+ if( (gem->ix3 != gem->bkwd->ix3) /* gem->bkwd is vert */
+ ^ (isign(gem->bkwd->ix3 - gei->ix3)==isign(gem->bkwd->iy3 - gei->iy3))
+ ^ (d == GEXFI_CONVEX) /* clockwise */ ) {
+
+#if 0
+ fprintf(stderr, " %p: %s potential spurious end\n", gem->bkwd, gxf_name[d]);
+#endif
+ /* the end may be a spurious entry */
+
+ gex = 0; /* the extremum closest to the end - to be found */
+ for(gei = gem->bkwd->bkwd; gei != ges->bkwd; gei = gei->bkwd) {
+ if(X_FRAG(gei)->flags & GEXFF_EXTR) {
+ gex = gei;
+ break;
+ }
+ }
+ if(gex == 0)
+ gex = ges;
+
+ good = 1; /* assume that gem->bkwd is not spurious */
+ /* gei goes backwards, gex goes forwards from the extremum */
+ gei = gex;
+ /* i is the symmetry axis, j is the other axis (X=0 Y=1) */
+ i = (gex->ix3 != gex->bkwd->ix3);
+ j = !i;
+ for( ; gei!=ges->bkwd && gex!=gem->bkwd; gei=gei->bkwd, gex=gex->frwd) {
+ if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2]
+ || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]
+ != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]
+ ) {
+ good = 0; /* no symmetry - must be spurious */
+#if 0
+ fprintf(stderr, " M(%p,%p)(%d %d,%d)(%d %d,%d)",
+ gei, gex,
+ i, gei->bkwd->ipoints[i][2], gex->ipoints[i][2],
+ j, gei->bkwd->ipoints[j][2] - gei->ipoints[j][2],
+ gex->bkwd->ipoints[j][2] - gex->ipoints[j][2] );
+#endif
+ break;
+ }
+ }
+ if(gei == ges->bkwd) { /* oops, the other side is too short */
+ good = 0;
+#if 0
+ fprintf(stderr, " X");
+#endif
+ }
+ if(good && gex == gem->bkwd) {
+ if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2])
+ != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) {
+ good = 0; /* oops, goes into another direction */
+#if 0
+ fprintf(stderr, " D");
+#endif
+ }
+ }
+ if(!good) { /* it is spurious, drop it */
+#if 0
+ fprintf(stderr, " %p: %s spurious end\n", gem->bkwd, gxf_name[d]);
+#endif
+ X_FRAG(ges)->len[d] = --len;
+ }
+ }
+ if(len < 4) {
+ X_FRAG(ges)->len[d] = 0;
+#if 0
+ fprintf(stderr, " %p: %s frag discarded, too small now\n", ge, gxf_name[d]);
+#endif
+ }
+ if(ges != ge) {
+ if(ges == cge->next)
+ break; /* went around the loop */
+ else {
+ ge = ges->frwd; /* don't look at this fragment twice */
+ continue;
+ }
+ }
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+ }
+
+ /* Find the straight line fragments.
+ * Even though the lines are sloped, they are called
+ * "vertical" or "horizontal" according to their longer
+ * dimension. All the steps in the shother dimension must
+ * be 1 pixel long, all the steps in the longer dimension
+ * must be within the difference of 1 pixel.
+ */
+ for(d = GEXFI_LINE; d<= GEXFI_EXACTLINE; d++) {
+ ge = cge->next;
+ pge = ge->bkwd; /* the beginning of the fragment */
+ count = 1;
+ delaystop = 0;
+ do {
+ int h;
+
+ stepmore = 0;
+ hdir = isign(ge->ix3 - ge->bkwd->ix3);
+ vdir = isign(ge->iy3 - ge->bkwd->iy3);
+ vert = (hdir == 0);
+ if(count==1) {
+ /* at this point pge==ge->bkwd */
+ /* account for the previous gentry, which was !vert */
+ if(!vert) { /* prev was vertical */
+ maxlen[0] = minlen[0] = 0;
+ maxlen[1] = minlen[1] = abs(pge->iy3 - pge->bkwd->iy3);
+ line[0] = (maxlen[1] == 1);
+ line[1] = 1;
+ fullhdir = hdir;
+ fullvdir = isign(pge->iy3 - pge->bkwd->iy3);
+ } else {
+ maxlen[0] = minlen[0] = abs(pge->ix3 - pge->bkwd->ix3);
+ maxlen[1] = minlen[1] = 0;
+ line[0] = 1;
+ line[1] = (maxlen[0] == 1);
+ fullhdir = isign(pge->ix3 - pge->bkwd->ix3);
+ fullvdir = vdir;
+ }
+ }
+ h = line[0]; /* remember the prevalent direction */
+#if 0
+ fprintf(stderr, " %p: v=%d(%d) h=%d(%d) vl(%d,%d,%d) hl=(%d,%d,%d) %s count=%d ",
+ ge, vdir, fullvdir, hdir, fullhdir,
+ line[1], minlen[1], maxlen[1],
+ line[0], minlen[0], maxlen[0],
+ gxf_name[d], count);
+#endif
+ if(vert) {
+ if(vdir != fullvdir)
+ line[0] = line[1] = 0;
+ len = abs(ge->iy3 - ge->bkwd->iy3);
+ } else {
+ if(hdir != fullhdir)
+ line[0] = line[1] = 0;
+ len = abs(ge->ix3 - ge->bkwd->ix3);
+ }
+#if 0
+ fprintf(stderr, "len=%d\n", len);
+#endif
+ if(len != 1) /* this is not a continuation in the short dimension */
+ line[!vert] = 0;
+
+ /* can it be a continuation in the long dimension ? */
+ if( line[vert] ) {
+ if(maxlen[vert]==0)
+ maxlen[vert] = minlen[vert] = len;
+ else if(maxlen[vert]==minlen[vert]) {
+ if(d == GEXFI_EXACTLINE) {
+ if(len != maxlen[vert])
+ line[vert] = 0; /* it can't */
+ } else if(len < maxlen[vert]) {
+ if(len < minlen[vert]-1)
+ line[vert] = 0; /* it can't */
+ else
+ minlen[vert] = len;
+ } else {
+ if(len > maxlen[vert]+1)
+ line[vert] = 0; /* it can't */
+ else
+ maxlen[vert] = len;
+ }
+ } else if(len < minlen[vert] || len > maxlen[vert])
+ line[vert] = 0; /* it can't */
+ }
+
+ if(line[0] == 0 && line[1] == 0) {
+#if 0
+ if(count >= 3)
+ fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
+#endif
+ X_FRAG(pge)->len[d] = count;
+ if(d == GEXFI_EXACTLINE && h) {
+ X_FRAG(pge)->flags |= GEXFF_HLINE;
+ }
+ if(count == 1)
+ pge = ge;
+ else {
+ stepmore = 1; /* may reconsider the 1st gentry */
+ pge = ge = ge->bkwd;
+ count = 1;
+ }
+ } else
+ count++;
+
+ ge = ge->frwd;
+ if(ge == cge->next && !stepmore)
+ delaystop = 1; /* consider the first gentry again */
+ } while(stepmore || ge != cge->next ^ delaystop);
+ /* see if there is an unfinished line left */
+ if(count != 1) {
+#if 0
+ if(count >= 3)
+ fprintf(stderr, " %s frag %p-%p count=%d\n", gxf_name[d], pge, ge->bkwd, count);
+#endif
+ X_FRAG(ge->bkwd->bkwd)->len[d] = 0;
+ X_FRAG(pge)->len[d] = count;
+ }
+ }
+
+ /* do postprocessing of the lines */
+#if 0
+ fprintf(stderr, "Line postprocessing\n");
+ gex_dump_contour(cge->next, clen);
+#endif
+
+ /* the non-exact line frags are related to exact line frags sort
+ * of like to individual gentries: two kinds of exact frags
+ * must be interleaved, with one kind having the size of 3
+ * and the other kind having the size varying within +-2.
+ */
+
+ ge = cge->next;
+ do {
+ GEX_FRAG *pf, *lastf1, *lastf2;
+ int len1, len2, fraglen;
+
+ f = X_FRAG(ge);
+
+ fraglen = f->len[GEXFI_LINE];
+ if(fraglen >= 4) {
+
+ vert = 0; /* vert is a pseudo-directon */
+ line[0] = line[1] = 1;
+ maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0;
+ lastf2 = lastf1 = f;
+ len2 = len1 = 0;
+ for(pge = ge, i = 1; i < fraglen; i++, pge=pge->frwd) {
+ pf = X_FRAG(pge);
+ len = pf->len[GEXFI_EXACTLINE];
+#if 0
+ fprintf(stderr, " pge=%p i=%d of %d ge=%p exLen=%d\n", pge, i,
+ f->len[GEXFI_LINE], ge, len);
+#endif
+ len1++; len2++;
+ if(len==0) {
+ continue;
+ }
+ vert = !vert; /* alternate the pseudo-direction */
+ if(len > 3)
+ line[!vert] = 0;
+ if(maxlen[vert] == 0)
+ maxlen[vert] = minlen[vert] = len;
+ else if(maxlen[vert]-2 >= len && minlen[vert]+2 <= len) {
+ if(len > maxlen[vert])
+ maxlen[vert] = len;
+ else if(len < minlen[vert])
+ minlen[vert] = len;
+ } else
+ line[vert] = 0;
+ if(line[0] == 0 && line[1] == 0) {
+#if 0
+ fprintf(stderr, " Line breaks at %p %c(%d, %d) %c(%d, %d) len=%d fl=%d l2=%d l1=%d\n",
+ pge, (!vert)?'*':' ', minlen[0], maxlen[0],
+ vert?'*':' ', minlen[1], maxlen[1], len, fraglen, len2, len1);
+#endif
+ if(lastf2 != lastf1) {
+ lastf2->len[GEXFI_LINE] = len2-len1;
+ }
+ lastf1->len[GEXFI_LINE] = len1+1;
+ pf->len[GEXFI_LINE] = fraglen+1 - i;
+ gex_dump_contour(pge, clen);
+
+ /* continue with the line */
+ vert = 0; /* vert is a pseudo-directon */
+ line[0] = line[1] = 1;
+ maxlen[0] = minlen[0] = maxlen[1] = minlen[1] = 0;
+ lastf2 = lastf1 = f;
+ len2 = len1 = 0;
+ } else {
+ lastf1 = pf;
+ len1 = 0;
+ }
+ }
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+#if 0
+ gex_dump_contour(cge->next, clen);
+#endif
+
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+
+ if(f->len[GEXFI_LINE] >= 4) {
+ len = f->len[GEXFI_EXACTLINE];
+ /* if a non-exact line covers precisely two exact lines,
+ * split it
+ */
+ if(len > 0 && f->len[GEXFI_LINE] > len+1) {
+ GEX_FRAG *pf;
+ pge = age[(f->aidx + len - 1)%clen]; /* last gentry of exact line */
+ pf = X_FRAG(pge);
+ if(f->len[GEXFI_LINE] + 1 == len + pf->len[GEXFI_EXACTLINE]) {
+ f->len[GEXFI_LINE] = len;
+ f->flags |= GEXFF_SPLIT;
+ pf->len[GEXFI_LINE] = pf->len[GEXFI_EXACTLINE];
+ pf->flags |= GEXFF_SPLIT;
+ }
+ }
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+
+ /* too small lines are of no interest */
+ if( (f->flags & GEXFF_SPLIT)==0 && f->len[GEXFI_LINE] < 4)
+ f->len[GEXFI_LINE] = 0;
+
+ len = f->len[GEXFI_EXACTLINE];
+ /* too small exact lines are of no interest */
+ if(len < 3) /* exact lines may be shorter */
+ f->len[GEXFI_EXACTLINE] = 0;
+ /* get rid of inexact additions to the end of the exact lines */
+ else if(f->len[GEXFI_LINE] == len+1)
+ f->len[GEXFI_LINE] = len;
+ /* same at the beginning */
+ else {
+ int diff = X_FRAG(ge->bkwd)->len[GEXFI_LINE] - len;
+
+ if(diff == 1 || diff == 2) {
+ X_FRAG(ge->bkwd)->len[GEXFI_LINE] = 0;
+ f->len[GEXFI_LINE] = len;
+ }
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+#if 0
+ gex_dump_contour(cge->next, clen);
+#endif
+
+ gex_calc_lenback(cge->next, clen); /* prepare data */
+
+ /* resolve conflicts between lines and curves */
+
+ /*
+ * the short (3-gentry) curve frags must have one of the ends
+ * coinciding with another curve frag of the same type
+ */
+
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+
+ if(f->len[d] == 3) {
+ pge = age[(f->aidx + 2)%clen]; /* last gentry of this frag */
+ if(f->lenback[d] == 0 && X_FRAG(pge)->len[d] == 0) {
+ fprintf(stderr, " discarded small %s at %p-%p\n", gxf_name[d], ge, pge);
+ f->len[d] = 0;
+ X_FRAG(ge->frwd)->lenback[d] = 0;
+ X_FRAG(ge->frwd->frwd)->lenback[d] = 0;
+ }
+ }
+ ge = ge->frwd;
+ } while(ge != cge->next);
+ }
+
+ /*
+ * longer exact lines take priority over curves, shorter lines
+ * and inexact lines are resolved with convex/concave conflicts
+ */
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+
+ len = f->len[GEXFI_EXACTLINE];
+
+ if(len < 6) { /* line is short */
+ ge = ge->frwd;
+ continue;
+ }
+
+ fprintf(stderr, " line at %p len=%d\n", ge, f->len[GEXFI_EXACTLINE]);
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ GEX_FRAG *pf;
+
+ /* check if we overlap the end of some fragment */
+ if(f->lenback[d]) {
+ /* chop off the end of conflicting fragment */
+ len = f->lenback[d];
+ pge = age[(f->aidx + clen - len)%clen];
+ pf = X_FRAG(pge);
+ if(pf->len[d] == clen+1 && pf->flags & GEXFF_CIRC) {
+ /* the conflicting fragment is self-connected */
+
+ pf->len[d] = 0;
+ /* calculate the new value for lenback */
+ len = clen+1 - f->len[GEXFI_EXACTLINE];
+ for(pge = ge; len > 0; pge = pge->bkwd, len--)
+ X_FRAG(pge)->lenback[d] = len;
+ /* now pge points to the last entry of the line,
+ * which is also the new first entry of the curve
+ */
+ X_FRAG(pge)->len[d] = clen+2 - f->len[GEXFI_EXACTLINE];
+ /* clean lenback of gentries covered by the line */
+ for(pge = ge->frwd, j = f->len[GEXFI_EXACTLINE]-1; j > 0; pge = pge->frwd, j--)
+ X_FRAG(pge)->lenback[d] = 0;
+ fprintf(stderr, " cut %s circular frag to %p-%p\n",
+ gxf_name[d], pge, ge);
+ gex_dump_contour(ge, clen);
+ } else {
+ /* when we chop off a piece of fragment, we leave the remaining
+ * piece(s) overlapping with the beginning and possibly the end
+ * of the line fragment under consideration
+ */
+ fprintf(stderr, " cut %s frag at %p from len=%d to len=%d (end %p)\n",
+ gxf_name[d], pge, pf->len[d], len+1, ge);
+ j = pf->len[d] - len - 1; /* how many gentries are chopped off */
+ pf->len[d] = len + 1;
+ i = f->len[GEXFI_EXACTLINE] - 1;
+ for(pge = ge->frwd; j > 0 && i > 0; j--, i--, pge = pge->frwd)
+ X_FRAG(pge)->lenback[d] = 0;
+ gex_dump_contour(ge, clen);
+
+ if(j != 0) {
+ /* the conflicting fragment is split in two by this line
+ * fragment, fix up its tail
+ */
+
+ fprintf(stderr, " end of %s frag len=%d %p-",
+ gxf_name[d], j+1, pge->bkwd);
+ X_FRAG(pge->bkwd)->len[d] = j+1; /* the overlapping */
+ for(i = 1; j > 0; j--, i++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[d] = i;
+ fprintf(stderr, "%p\n", pge->bkwd);
+ gex_dump_contour(ge, clen);
+ }
+ }
+ }
+ /* check if we overlap the beginning of some fragments */
+ i = f->len[GEXFI_EXACTLINE]-1; /* getntries remaining to consider */
+ j = 0; /* gentries remaining in the overlapping fragment */
+ for(pge = ge; i > 0; i--, pge = pge->frwd) {
+ if(j > 0) {
+ X_FRAG(pge)->lenback[d] = 0;
+ j--;
+ }
+ /* the beginning of one fragment may be the end of another
+ * fragment, in this case if j-- above results in 0, that will
+ * cause it to check the same gentry for the beginning
+ */
+ if(j == 0) {
+ pf = X_FRAG(pge);
+ j = pf->len[d];
+ if(j != 0) {
+ fprintf(stderr, " removed %s frag at %p len=%d\n",
+ gxf_name[d], pge, j);
+ gex_dump_contour(ge, clen);
+ pf->len[d] = 0;
+ j--;
+ }
+ }
+ }
+ /* pge points at the last gentry of the line fragment */
+ if(j > 1) { /* we have the tail of a fragment left */
+ fprintf(stderr, " end of %s frag len=%d %p-",
+ gxf_name[d], j, pge);
+ X_FRAG(pge)->len[d] = j; /* the overlapping */
+ for(i = 0; j > 0; j--, i++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[d] = i;
+ fprintf(stderr, "%p\n", pge->bkwd);
+ gex_dump_contour(ge, clen);
+ } else if(j == 1) {
+ X_FRAG(pge)->lenback[d] = 0;
+ }
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ /*
+ * The exact lines take priority over curves that coincide
+ * with them or extend by only one gentry on either side
+ * (but not both sides). By this time it applies only to the
+ * small exact lines.
+ */
+
+ /* Maybe we should remove only exact coincidences ? */
+
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+
+ len = f->len[GEXFI_EXACTLINE];
+ if(len >= 4) {
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ if(f->len[d] == len || f->len[d] == len+1) {
+
+ fprintf(stderr, " removed %s frag at %p len=%d linelen=%d\n",
+ gxf_name[d], ge, f->len[d], len);
+ pge = ge->frwd;
+ for(i = f->len[d]; i > 1; i--, pge = pge->frwd)
+ X_FRAG(pge)->lenback[d] = 0;
+ f->len[d] = 0;
+ gex_dump_contour(ge, clen);
+ } else if(X_FRAG(ge->bkwd)->len[d] == len+1) {
+ fprintf(stderr, " removed %s frag at %p len=%d next linelen=%d\n",
+ gxf_name[d], ge->bkwd, X_FRAG(ge->bkwd)->len[d], len);
+ pge = ge;
+ for(i = len; i > 0; i--, pge = pge->frwd)
+ X_FRAG(pge)->lenback[d] = 0;
+ X_FRAG(ge->bkwd)->len[d] = 0;
+ gex_dump_contour(ge, clen);
+ }
+ }
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ /*
+ * The lines may cover only whole curves (or otherwise empty space),
+ * so cut them where they overlap parts of the curves. If 2 or less
+ * gentries are left in the line, remove the line.
+ * If a line and a curve fully coincide, remove the line. Otherwise
+ * remove the curves that are completely covered by the lines.
+ */
+
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+
+ reconsider_line:
+ len = f->len[GEXFI_LINE];
+
+ if(len == 0) {
+ ge = ge->frwd;
+ continue;
+ }
+
+ if(f->len[GEXFI_CONVEX] >= len
+ || f->len[GEXFI_CONCAVE] >= len) {
+ line_completely_covered:
+ fprintf(stderr, " removed covered Line frag at %p len=%d\n",
+ ge, len);
+ f->len[GEXFI_LINE] = 0;
+ for(pge = ge->frwd; len > 1; len--, pge = pge->frwd)
+ X_FRAG(pge)->lenback[GEXFI_LINE] = 0;
+ gex_dump_contour(ge, clen);
+ ge = ge->frwd;
+ continue;
+ }
+
+ k1 = 0; /* how much to cut at the front */
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ if(f->lenback[d]) {
+ pge = age[(f->aidx + clen - f->lenback[d])%clen];
+ i = X_FRAG(pge)->len[d] - f->lenback[d] - 1;
+ if(i > k1)
+ k1 = i;
+ }
+ }
+
+ k2 = 0; /* how much to cut at the end */
+ pge = age[(f->aidx + len)%clen]; /* gentry after the end */
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ i = X_FRAG(pge)->lenback[d] - 1;
+ if(i > k2)
+ k2 = i;
+ }
+
+ if(k1+k2 > 0 && k1+k2 >= len-3)
+ goto line_completely_covered;
+
+ if(k2 != 0) { /* cut the end */
+ len -= k2;
+ f->len[GEXFI_LINE] = len;
+ /* pge still points after the end */
+ for(i = k2, pge = pge->bkwd; i > 0; i--, pge = pge->bkwd)
+ X_FRAG(pge)->lenback[GEXFI_LINE] = 0;
+ }
+ if(k1 != 0) { /* cut the beginning */
+ len -= k1;
+ f->len[GEXFI_LINE] = 0;
+ for(i = 1, pge = ge->frwd; i < k1; i++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[GEXFI_LINE] = 0;
+ X_FRAG(pge)->len[GEXFI_LINE] = len;
+ for(i = 0; i < len; i++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[GEXFI_LINE] = i;
+ }
+ if(k1 != 0 || k2 != 0) {
+ fprintf(stderr, " cut Line frag at %p by (%d,%d) to len=%d\n",
+ ge, k1, k2, len);
+ gex_dump_contour(ge, clen);
+
+ goto reconsider_line; /* the line may have to be cut again */
+ }
+ pge = age[(f->aidx + k1)%clen]; /* new beginning */
+ good = 1; /* flag: no need do do a debugging dump */
+ for(i=1; i<len; i++, pge = pge->frwd)
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ if(X_FRAG(pge)->len[d]) {
+ fprintf(stderr, " removed %s frag at %p len=%d covered by line\n",
+ gxf_name[d], pge, X_FRAG(pge)->len[d], len);
+ good = 0;
+ }
+ X_FRAG(pge)->len[d] = 0;
+ }
+ pge = age[(f->aidx + k1 + 1)%clen]; /* next after new beginning */
+ for(i=1; i<len; i++, pge = pge->frwd)
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++)
+ X_FRAG(pge)->lenback[d] = 0;
+ if(!good)
+ gex_dump_contour(ge, clen);
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ /* Resolve conflicts between curves */
+ for(d = GEXFI_CONVEX; d<= GEXFI_CONCAVE; d++) {
+ dx = (GEXFI_CONVEX + GEXFI_CONCAVE) - d; /* the other type */
+ ge = cge->next;
+ do {
+ GENTRY *sge;
+
+ f = X_FRAG(ge);
+ len = f->len[d];
+ if(len < 2) {
+ ge = ge->frwd;
+ continue;
+ }
+ sge = ge; /* the start of fragment */
+
+ i = f->len[dx];
+ if(i != 0) { /* two curved frags starting here */
+ /* should be i!=len because otherwise they would be
+ * covered by an exact line
+ */
+ if(i > len) {
+ curve_completely_covered:
+ /* remove the convex frag */
+ fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n",
+ gxf_name[d], ge, len, gxf_name[dx]);
+ f->len[d] = 0;
+ for(pge = ge->frwd, j = 1; j < len; j++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[d] = 0;
+ gex_dump_contour(ge, clen);
+
+ ge = ge->frwd; /* the frag is gone, nothing more to do */
+ continue;
+ } else {
+ /* remove the concave frag */
+ fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n",
+ gxf_name[dx], ge, i, gxf_name[d]);
+ f->len[dx] = 0;
+ for(pge = ge->frwd, j = 1; j < i; j++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[dx] = 0;
+ gex_dump_contour(ge, clen);
+ }
+ }
+
+
+ k1 = X_FRAG(ge->frwd)->lenback[dx];
+ if(k1 != 0) { /* conflict at the front */
+ GENTRY *gels, *gele, *gei;
+
+ pge = age[(f->aidx + clen - (k1-1))%clen]; /* first gentry of concave frag */
+ k2 = X_FRAG(pge)->len[dx]; /* its length */
+
+ i = k2 - (k1-1); /* amount of overlap */
+ if(i > len)
+ i = len;
+ /* i >= 2 by definition */
+ if(i >= k2-1) { /* covers the other frag - maybe with 1 gentry showing */
+ fprintf(stderr, " removed %s frag at %p len=%d covered by %s\n",
+ gxf_name[dx], pge, k2, gxf_name[d]);
+ X_FRAG(pge)->len[dx] = 0;
+ for(pge = pge->frwd, j = 1; j < k2; j++, pge = pge->frwd)
+ X_FRAG(pge)->lenback[dx] = 0;
+ if(i >= len-1) { /* covers our frag too - maybe with 1 gentry showing */
+ /* our frag will be removed as well, prepare a line to replace it */
+ gels = ge;
+ gele = age[(f->aidx + i - 1)%clen];
+ fprintf(stderr, " new Line frag at %p-%p len=%d\n", gels, gele, i);
+ X_FRAG(gels)->len[GEXFI_LINE] = i;
+ for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++)
+ X_FRAG(gei)->lenback[GEXFI_LINE] = j;
+ } else {
+ gex_dump_contour(ge, clen);
+ ge = ge->frwd;
+ continue;
+ }
+ }
+ if(i >= len-1) /* covers our frag - maybe with 1 gentry showing */
+ goto curve_completely_covered;
+
+ /* XXX need to do something better for the case when a curve frag
+ * is actually nothing but an artifact of two other curves of
+ * the opposite type touching each other, like on the back of "3"
+ */
+
+ /* change the overlapping part to a line */
+ gels = ge;
+ gele = age[(f->aidx + i - 1)%clen];
+ /* give preference to local extremums */
+ if(X_FRAG(gels)->flags & GEXFF_EXTR) {
+ gels = gels->frwd;
+ i--;
+ }
+ if(X_FRAG(gele)->flags & GEXFF_EXTR) {
+ gele = gele->bkwd;
+ i--;
+ }
+ if(gels->bkwd == gele) {
+ /* Oops the line became negative. Probably should
+ * never happen but I can't think of any formal reasoning
+ * leading to that, so check just in case. Restore
+ * the previous state.
+ */
+ gels = gele; gele = gels->frwd; i = 2;
+ }
+
+ j = X_FRAG(gels)->lenback[dx] + 1; /* new length */
+ if(j != k2) {
+ X_FRAG(pge)->len[dx] = j;
+ fprintf(stderr, " cut %s frag at %p len=%d to %p len=%d end overlap with %s\n",
+ gxf_name[dx], pge, k2, gels, j, gxf_name[d]);
+ for(gei = gels->frwd; j < k2; gei = gei->frwd, j++)
+ X_FRAG(gei)->lenback[dx] = 0;
+ }
+
+ if(gele != ge) {
+ sge = gele;
+ f->len[d] = 0;
+ fprintf(stderr, " cut %s frag at %p len=%d ", gxf_name[d], ge, len);
+ len--;
+ for(gei = ge->frwd; gei != gele; gei = gei->frwd, len--)
+ X_FRAG(gei)->lenback[d] = 0;
+ X_FRAG(gele)->len[d] = len;
+ X_FRAG(gele)->lenback[d] = 0;
+ fprintf(stderr, "to %p len=%d start overlap with %s\n",
+ sge, len, gxf_name[dx]);
+ for(gei = gei->frwd, j = 1; j < len; gei = gei->frwd, j++)
+ X_FRAG(gei)->lenback[d] = j;
+
+ }
+ if(i > 1) {
+ fprintf(stderr, " new Line frag at %p-%p len=%d\n", gels, gele, i);
+ X_FRAG(gels)->len[GEXFI_LINE] = i;
+ for(gei = gels->frwd, j = 1; j < i; gei = gei->frwd, j++)
+ X_FRAG(gei)->lenback[GEXFI_LINE] = j;
+ }
+ gex_dump_contour(ge, clen);
+ }
+
+ ge = ge->frwd;
+ } while(ge != cge->next);
+ }
+
+ /*
+ * Assert that there are no conflicts any more and
+ * for each gentry find the fragment types that start
+ * and continue here.
+ */
+ ge = cge->next;
+ do {
+ f = X_FRAG(ge);
+ dx = GEXFI_NONE; /* type that starts here */
+ dy = GEXFI_NONE; /* type that goes through here */
+ for(d = GEXFI_CONVEX; d<= GEXFI_LINE; d++) {
+ if(f->len[d]) {
+ if(dx >= 0) {
+ fprintf(stderr, "**** Internal error in vectorization\n");
+ fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n",
+ g->name, ge, gxf_name[dx], gxf_name[d]);
+ dumppaths(g, cge->next, cge->next->bkwd);
+ gex_dump_contour(ge, clen);
+ exit(1);
+ }
+ dx = d;
+ }
+ if(f->lenback[d]) {
+ if(dy >= 0) {
+ fprintf(stderr, "**** Internal error in vectorization\n");
+ fprintf(stderr, "CONFLICT in %s at %p between %s and %s\n",
+ g->name, ge, gxf_name[dy], gxf_name[d]);
+ dumppaths(g, cge->next, cge->next->bkwd);
+ gex_dump_contour(ge, clen);
+ exit(1);
+ }
+ dy = d;
+ }
+ }
+ f->ixstart = dx;
+ f->ixcont = dy;
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ /*
+ * make sure that the contour does not start in the
+ * middle of a fragment
+ */
+ ge = cge->next; /* old start of the contour */
+ f = X_FRAG(ge);
+ if(f->ixstart == GEXFI_NONE && f->ixcont != GEXFI_NONE) {
+ /* oops, it's mid-fragment, move the start */
+ GENTRY *xge;
+
+ xge = ge->bkwd->next; /* entry following the contour */
+
+ /* find the first gentry of this frag */
+ pge = age[(f->aidx + clen - f->lenback[f->ixcont])%clen];
+
+ ge->prev = ge->bkwd;
+ ge->bkwd->next = ge;
+
+ cge->next = pge;
+ pge->prev = cge;
+
+ pge->bkwd->next = xge;
+ if(xge)
+ xge->prev = pge->bkwd;
+
+ cge->ix3 = pge->bkwd->ix3; cge->iy3 = pge->bkwd->iy3;
+ }
+
+ /* vectorize each fragment separately */
+ ge = cge->next;
+ do {
+ /* data for curves */
+ GENTRY *firstge, *lastge, *gef, *gel, *gei, *gex;
+ GENTRY *ordhd; /* head of the order list */
+ GENTRY **ordlast;
+ int nsub; /* number of subfrags */
+ GEX_FRAG *ff, *lf, *xf;
+
+ f = X_FRAG(ge);
+ switch(f->ixstart) {
+ case GEXFI_LINE:
+ len = f->len[GEXFI_LINE];
+ pge = age[(f->aidx + len - 1)%clen]; /* last gentry */
+
+ if(ge->iy3 == ge->bkwd->iy3) { /* frag starts and ends horizontally */
+ k1 = 1/*Y*/ ; /* across the direction of start */
+ k2 = 0/*X*/ ; /* along the direction of start */
+ } else { /* frag starts and ends vertically */
+ k1 = 0/*X*/ ; /* across the direction of start */
+ k2 = 1/*Y*/ ; /* along the direction of start */
+ }
+
+ if(len % 2) {
+ /* odd number of entries in the frag */
+ double halfstep, halfend;
+
+ f->vect[0][k1] = fscale * ge->ipoints[k1][2];
+ f->vect[3][k1] = fscale * pge->ipoints[k1][2];
+
+ halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2])
+ * 0.5 / ((len+1)/2);
+ if(f->ixcont != GEXFI_NONE) {
+ halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5;
+ if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
+ halfstep = halfend;
+ }
+ if(X_FRAG(pge)->ixstart != GEXFI_NONE) {
+ halfend = (pge->ipoints[k2][2] - pge->bkwd->ipoints[k2][2]) * 0.5;
+ if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
+ halfstep = halfend;
+ }
+ f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep);
+ f->vect[3][k2] = fscale * (pge->ipoints[k2][2] - halfstep);
+ } else {
+ /* even number of entries */
+ double halfstep, halfend;
+
+ f->vect[0][k1] = fscale * ge->ipoints[k1][2];
+ halfstep = (pge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2])
+ * 0.5 / (len/2);
+ if(f->ixcont != GEXFI_NONE) {
+ halfend = (ge->ipoints[k2][2] - ge->bkwd->ipoints[k2][2]) * 0.5;
+ if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
+ halfstep = halfend;
+ }
+ f->vect[0][k2] = fscale * (ge->bkwd->ipoints[k2][2] + halfstep);
+
+ halfstep = (pge->ipoints[k1][2] - ge->bkwd->ipoints[k1][2])
+ * 0.5 / (len/2);
+ if(X_FRAG(pge)->ixstart != GEXFI_NONE) {
+ halfend = (pge->ipoints[k1][2] - pge->bkwd->ipoints[k1][2]) * 0.5;
+ if(fabs(halfstep) < fabs(halfend)) /* must be at least half gentry away */
+ halfstep = halfend;
+ }
+ f->vect[3][k1] = fscale * (pge->ipoints[k1][2] - halfstep);
+ f->vect[3][k2] = fscale * pge->ipoints[k2][2];
+ }
+ f->vectlen = len;
+ f->flags |= GEXFF_DRAWLINE;
+ break;
+ case GEXFI_CONVEX:
+ case GEXFI_CONCAVE:
+ len = f->len[f->ixstart];
+ firstge = ge;
+ lastge = age[(f->aidx + len - 1)%clen]; /* last gentry */
+
+ nsub = 0;
+ gex = firstge;
+ xf = X_FRAG(gex);
+ xf->prevsub = 0;
+ xf->sublen = 1;
+ xf->flags &= ~GEXFF_DONE;
+ for(gei = firstge->frwd; gei != lastge; gei = gei->frwd) {
+ xf->sublen++;
+ if(X_FRAG(gei)->flags & GEXFF_EXTR) {
+ xf->nextsub = gei;
+ for(i=0; i<2; i++)
+ xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]);
+ nsub++;
+ xf = X_FRAG(gei);
+ xf->prevsub = gex;
+ xf->sublen = 1;
+ xf->flags &= ~GEXFF_DONE;
+ gex = gei;
+ }
+ }
+ xf->sublen++;
+ xf->nextsub = gei;
+ for(i=0; i<2; i++)
+ xf->bbox[i] = abs(gei->ipoints[i][2] - gex->bkwd->ipoints[i][2]);
+ nsub++;
+ ff = xf; /* remember the beginning of the last subfrag */
+ xf = X_FRAG(gei);
+ xf->prevsub = gex;
+ if(firstge != lastge) {
+ xf->nextsub = 0;
+ xf->sublen = 0;
+
+ /* correct the bounding box of the last and first subfrags for
+ * intersections with other fragments
+ */
+ if(xf->ixstart != GEXFI_NONE) {
+ /* ff points to the beginning of the last subfrag */
+ for(i=0; i<2; i++)
+ ff->bbox[i] -= 0.5 * abs(lastge->ipoints[i][2] - lastge->bkwd->ipoints[i][2]);
+ }
+ ff = X_FRAG(firstge);
+ if(ff->ixcont != GEXFI_NONE) {
+ for(i=0; i<2; i++)
+ ff->bbox[i] -= 0.5 * abs(firstge->ipoints[i][2] - firstge->bkwd->ipoints[i][2]);
+ }
+ }
+
+ fprintf(stderr, " %s frag %p%s nsub=%d\n", gxf_name[f->ixstart],
+ ge, (f->flags&GEXFF_CIRC)?" circular":"", nsub);
+
+ /* find the symmetry between the subfragments */
+ for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
+ ff = X_FRAG(gef);
+ gex = ff->nextsub;
+ xf = X_FRAG(gex);
+ gel = xf->nextsub;
+ if(gel == 0) {
+ ff->flags &= ~GEXFF_SYMNEXT;
+ break; /* not a circular frag */
+ }
+ good = 1; /* assume that we have symmetry */
+ /* gei goes backwards, gex goes forwards from the extremum */
+ gei = gex;
+ /* i is the symmetry axis, j is the other axis (X=0 Y=1) */
+ ff->symaxis = i = (gex->ix3 != gex->bkwd->ix3);
+ j = !i;
+ for( ; gei!=gef && gex!=gel; gei=gei->bkwd, gex=gex->frwd) {
+ if( gei->bkwd->ipoints[i][2] != gex->ipoints[i][2]
+ || gei->bkwd->ipoints[j][2] - gei->ipoints[j][2]
+ != gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]
+ ) {
+ good = 0; /* no symmetry */
+ break;
+ }
+ }
+ if(good) {
+ if( isign(gei->bkwd->ipoints[j][2] - gei->ipoints[j][2])
+ != isign(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) ) {
+ good = 0; /* oops, goes into another direction */
+ }
+ }
+ if(good)
+ ff->flags |= GEXFF_SYMNEXT;
+ else
+ ff->flags &= ~GEXFF_SYMNEXT;
+ }
+
+ for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
+ ff = X_FRAG(gef);
+ if((ff->flags & GEXFF_SYMNEXT)==0) {
+ ff->symxlen = 0;
+ continue;
+ }
+ gex = ff->prevsub;
+ if(gex == 0 || (X_FRAG(gex)->flags & GEXFF_SYMNEXT)==0) {
+ ff->symxlen = 0;
+ continue;
+ }
+ ff->symxlen = X_FRAG(gex)->sublen;
+ xf = X_FRAG(ff->nextsub);
+ if(xf->sublen < ff->symxlen)
+ ff->symxlen = xf->sublen;
+ }
+
+ /* find the symmetry inside the subfragments */
+ for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
+ ff = X_FRAG(gef);
+
+ if(ff->sublen % 2) {
+ /* we must have an even number of gentries for diagonal symmetry */
+ ff->symge = 0;
+ continue;
+ }
+
+ /* gei goes forwards from the front */
+ gei = gef->frwd;
+ /* gex goes backwards from the back */
+ gex = ff->nextsub->bkwd;
+
+ /* i is the direction of gei, j is the direction of gex */
+ i = (gei->iy3 != gei->bkwd->iy3);
+ j = !i;
+ for( ; gei->bkwd != gex; gei=gei->frwd, gex=gex->bkwd) {
+ if( abs(gei->bkwd->ipoints[i][2] - gei->ipoints[i][2])
+ != abs(gex->bkwd->ipoints[j][2] - gex->ipoints[j][2]) )
+ break; /* no symmetry */
+ i = j;
+ j = !j;
+ }
+ if(gei->bkwd == gex)
+ ff->symge = gex;
+ else
+ ff->symge = 0; /* no symmetry */
+ }
+
+ /* find the order of calculation:
+ * prefer to start from long fragments that have the longest
+ * neighbours symmetric with them, with all being equal prefer
+ * the fragments that have smaller physical size
+ */
+ ordhd = 0;
+ for(gef = firstge, count=0; count < nsub; gef = ff->nextsub, count++) {
+ ff = X_FRAG(gef);
+
+ for(ordlast = &ordhd; *ordlast != 0; ordlast = &xf->ordersub) {
+ xf = X_FRAG(*ordlast);
+ if(ff->sublen > xf->sublen)
+ break;
+ if(ff->sublen < xf->sublen)
+ continue;
+ if(ff->symxlen > xf->symxlen)
+ break;
+ if(ff->symxlen < xf->symxlen)
+ continue;
+ if(ff->bbox[0] < xf->bbox[0] || ff->bbox[1] < xf->bbox[1])
+ break;
+ }
+
+ ff->ordersub = *ordlast;
+ *ordlast = gef;
+ }
+
+ /* vectorize the subfragments */
+ for(gef = ordhd; gef != 0; gef = ff->ordersub) {
+
+ /* debugging stuff */
+ ff = X_FRAG(gef);
+ fprintf(stderr, " %p-%p bbox[%g,%g] sym=%p %s len=%d xlen=%d\n",
+ gef, ff->nextsub, ff->bbox[0], ff->bbox[1], ff->symge,
+ (ff->flags & GEXFF_SYMNEXT) ? "symnext" : "",
+ ff->sublen, ff->symxlen);
+
+ dosubfrag(g, f->ixstart, firstge, gef, fscale);
+ }
+
+ break;
+ }
+ ge = ge->frwd;
+ } while(ge != cge->next);
+
+ free(age);
+
+ }
+
+ }
+
+ /* all the fragments are found, extract the vectorization */
+ pge = g->entries;
+ g->entries = g->lastentry = 0;
+ g->flags |= GF_FLOAT;
+ loopge = 0;
+ skip = 0;
+
+ for(ge = pge; ge != 0; ge = ge->next) {
+ GEX_FRAG *f, *pf;
+
+ switch(ge->type) {
+ case GE_LINE:
+ f = X_FRAG(ge);
+ if(skip == 0) {
+ if(f->flags & (GEXFF_DRAWLINE|GEXFF_DRAWCURVE)) {
+ /* draw a line to the start point */
+ fg_rlineto(g, f->vect[0][0], f->vect[0][1]);
+ /* draw the fragment */
+ if(f->flags & GEXFF_DRAWCURVE)
+ fg_rrcurveto(g,
+ f->vect[1][0], f->vect[1][1],
+ f->vect[2][0], f->vect[2][1],
+ f->vect[3][0], f->vect[3][1]);
+ else
+ fg_rlineto(g, f->vect[3][0], f->vect[3][1]);
+ skip = f->vectlen - 2;
+ } else {
+ fg_rlineto(g, fscale * ge->ix3, fscale * ge->iy3);
+ }
+ } else
+ skip--;
+ break;
+ case GE_MOVE:
+ fg_rmoveto(g, -1e6, -1e6); /* will be fixed by GE_PATH */
+ skip = 0;
+ /* remember the reference to update it later */
+ loopge = g->lastentry;
+ break;
+ case GE_PATH:
+ /* update the first MOVE of this contour */
+ if(loopge) {
+ loopge->fx3 = g->lastentry->fx3;
+ loopge->fy3 = g->lastentry->fy3;
+ loopge = 0;
+ }
+ g_closepath(g);
+ break;
+ }
+ }
+ for(ge = pge; ge != 0; ge = cge) {
+ cge = ge->next;
+ free(ge->ext);
+ free(ge);
+ }
+ dumppaths(g, NULL, NULL);
+
+ /* end of vectorization logic */
+ } else {
+ /* convert the data to float */
+ GENTRY *ge;
+ double x, y;
+
+ for(ge = g->entries; ge != 0; ge = ge->next) {
+ ge->flags |= GEF_FLOAT;
+ if(ge->type != GE_MOVE && ge->type != GE_LINE)
+ continue;
+
+ x = fscale * ge->ix3;
+ y = fscale * ge->iy3;
+
+ ge->fx3 = x;
+ ge->fy3 = y;
+ }
+ g->flags |= GF_FLOAT;
+ }
+
+ free(hlm); free(vlm); free(amp);
+}
+
+#if 0
+/* print out the bitmap */
+printbmap(bmap, xsz, ysz, xoff, yoff)
+ char *bmap;
+ int xsz, ysz, xoff, yoff;
+{
+ int x, y;
+
+ for(y=ysz-1; y>=0; y--) {
+ putchar( (y%10==0) ? y/10+'0' : ' ' );
+ putchar( y%10+'0' );
+ for(x=0; x<xsz; x++)
+ putchar( bmap[y*xsz+x] ? 'X' : '.' );
+ if(-yoff==y)
+ putchar('_'); /* mark the baseline */
+ putchar('\n');
+ }
+ putchar(' '); putchar(' ');
+ for(x=0; x<xsz; x++)
+ putchar( x%10+'0' );
+ putchar('\n'); putchar(' '); putchar(' ');
+ for(x=0; x<xsz; x++)
+ putchar( (x%10==0) ? x/10+'0' : ' ' );
+ putchar('\n');
+}
+
+/* print out the limits of outlines */
+printlimits(hlm, vlm, amp, xsz, ysz)
+ char *hlm, *vlm, *amp;
+ int xsz, ysz;
+{
+ int x, y;
+ static char h_char[]={ ' ', '~', '^' };
+ static char v_char[]={ ' ', '(', ')' };
+
+ for(y=ysz-1; y>=0; y--) {
+ for(x=0; x<xsz; x++) {
+ if(amp[y*xsz+x])
+ putchar('!'); /* ambigouos point is always on a limit */
+ else
+ putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]);
+ putchar(h_char[ hlm[(y+1)*xsz+x] & (L_ON|L_OFF) ]);
+ }
+ putchar(v_char[ vlm[y*(xsz+1)+x] & (L_ON|L_OFF) ]);
+ putchar('\n');
+ }
+ /* last line */
+ for(x=0; x<xsz; x++) {
+ putchar(' ');
+ putchar(h_char[ hlm[x] & (L_ON|L_OFF) ]);
+ }
+ putchar(' ');
+ putchar('\n');
+}
+#endif /* 0 */
git.asbjorn.biz / swftools.git / commitdiff