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