w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

stemdb.c
Go to the documentation of this file.
1 /* Copyright (C) 2005-2012 by George Williams and Alexey Kryukov */
2 /*
3  * Redistribution and use in source and binary forms, with or without
4  * modification, are permitted provided that the following conditions are met:
5 
6  * Redistributions of source code must retain the above copyright notice, this
7  * list of conditions and the following disclaimer.
8 
9  * Redistributions in binary form must reproduce the above copyright notice,
10  * this list of conditions and the following disclaimer in the documentation
11  * and/or other materials provided with the distribution.
12 
13  * The name of the author may not be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15 
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
17  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
19  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 #include "fontforge.h"
28 #include "edgelist2.h"
29 #include "stemdb.h"
30 
31 #include <math.h>
32 #include <utype.h>
33 
34 #define GLYPH_DATA_DEBUG 0
35 #define PI 3.14159265358979323846264338327
36 
37 /* A diagonal end is like the top or bottom of a slash. Should we add a vertical stem at the end? */
38 /* A diagonal corner is like the bottom of circumflex. Should we add a horizontal stem? */
43 
44 float stem_slope_error = .05061454830783555773, /* 2.9 degrees */
45  stub_slope_error = .317649923862967983; /* 18.2 degrees */
46 
47 static double dist_error_hv = 3.5;
48 static double dist_error_diag = 5.5;
49 /* It's easy to get horizontal/vertical lines aligned properly */
50 /* it is more difficult to get diagonal ones done */
51 /* The "A" glyph in Apple's Times.dfont(Roman) is off by 6 in one spot */
52 static double dist_error_curve = 22;
53 /* The maximum possible distance between the edge of an active zone for */
54 /* a curved spline segment and the spline itself */
55 
56 struct st {
58  double st, lt;
59 };
60 
61 static int GetBlueFuzz(SplineFont *sf) {
62  char *str, *end;
63 
64  if ( sf == NULL || sf->private == NULL ||
65  (str=PSDictHasEntry( sf->private,"BlueFuzz" )) == NULL || !isdigit( str[0] ))
66 return 1;
67 return strtod( str, &end );
68 }
69 
70 static int IsUnitHV( BasePoint *unit,int strict ) {
71  double angle = atan2( unit->y,unit->x );
72  double deviation = ( strict ) ? stem_slope_error : stub_slope_error;
73 
74  if ( fabs( angle ) >= PI/2 - deviation && fabs( angle ) <= PI/2 + deviation )
75 return( 2 );
76  else if ( fabs( angle ) <= deviation || fabs( angle ) >= PI - deviation )
77 return( 1 );
78 
79 return( 0 );
80 }
81 
82 static int UnitCloserToHV( BasePoint *u1,BasePoint *u2 ) {
83  double adiff1, adiff2;
84 
85  adiff1 = fabs( atan2( u1->y,u1->x ));
86  adiff2 = fabs( atan2( u2->y,u2->x ));
87 
88  if ( adiff1 > PI*.25 && adiff1 < PI*.75 )
89  adiff1 = fabs( adiff1 - PI*.5 );
90  else if ( adiff1 >= PI*.75 )
91  adiff1 = PI - adiff1;
92 
93  if ( adiff2 > PI*.25 && adiff2 < PI*.75 )
94  adiff2 = fabs( adiff2 - PI*.5 );
95  else if ( adiff2 >= PI*.75 )
96  adiff2 = PI - adiff2;
97 
98  if ( adiff1 < adiff2 )
99 return( 1 );
100  else if ( adiff1 > adiff2 )
101 return( -1 );
102  else
103 return( 0 );
104 }
105 
106 static double GetUnitAngle( BasePoint *u1,BasePoint *u2 ) {
107  double dx, dy;
108 
109  dy = u1->x*u2->y - u1->y*u2->x;
110  dx = u1->x*u2->x + u1->y*u2->y;
111 return( atan2( dy,dx ));
112 }
113 
114 static int UnitsOrthogonal( BasePoint *u1,BasePoint *u2,int strict ) {
115  double angle, deviation = ( strict ) ? stem_slope_error : stub_slope_error;
116 
117  angle = GetUnitAngle( u1,u2 );
118 
119 return( fabs( angle ) >= PI/2 - deviation && fabs( angle ) <= PI/2 + deviation );
120 }
121 
123  double angle, deviation = ( strict ) ? stem_slope_error : stub_slope_error;
124 
125  angle = GetUnitAngle( u1,u2 );
126 
127 return( fabs( angle ) <= deviation || fabs( angle ) >= PI - deviation );
128 }
129 
130 static int IsInflectionPoint( struct glyphdata *gd,struct pointdata *pd ) {
131  SplinePoint *sp = pd->sp;
132  double CURVATURE_THRESHOLD = 1e-9;
133  struct spline *prev, *next;
134  double in, out;
135 
136  if ( sp->prev == NULL || sp->next == NULL || !pd->colinear )
137 return( false );
138 
139  /* point of a single-point contour can't be an inflection point. */
140  if ( sp->prev->from == sp )
141 return( false );
142 
143  prev = sp->prev;
144  in = 0;
145  while ( prev != NULL && fabs(in) < CURVATURE_THRESHOLD ) {
146  in = SplineCurvature( prev,1 );
147  if ( fabs( in ) < CURVATURE_THRESHOLD ) in = SplineCurvature( prev, 0 );
148  if ( fabs( in ) < CURVATURE_THRESHOLD ) prev = prev->from->prev;
149  if ( gd->points[prev->to->ptindex].colinear )
150  break;
151  }
152 
153  next = sp->next;
154  out = 0;
155  while ( next != NULL && fabs( out ) < CURVATURE_THRESHOLD ) {
156  out = SplineCurvature( next,0 );
157  if ( fabs( out ) < CURVATURE_THRESHOLD ) out = SplineCurvature( next, 1 );
158  if ( fabs( out ) < CURVATURE_THRESHOLD ) next = next->to->next;
159  if ( gd->points[next->from->ptindex].colinear )
160  break;
161  }
162 
163  if ( in==0 || out==0 || ( prev != sp->prev && next != sp->next ))
164 return( false );
165 
166  in/=fabs(in);
167  out/=fabs(out);
168 
169 return ( in*out < 0 );
170 }
171 
172 static int SplineFigureOpticalSlope(Spline *s,int start_at_from,BasePoint *dir) {
173  /* Sometimes splines have tiny control points, and to the eye the slope */
174  /* of the spline has nothing to do with that specified by the cps. */
175  /* So see if the spline is straightish and figure the slope based on */
176  /* some average direction */
177  /* dir is a input output parameter. */
178  /* it should be initialized to the unit vector determined by the appropriate cp */
179  /* if the function returns true, it will be set to a unit vector in the average direction */
180  BasePoint pos, *base, average_dir, normal;
181  double t, len, incr, off;
182  double dx, dy, ax, ay, d, a;
183 
184  /* The vector is already nearly vertical/horizontal, no need to modify*/
185  if ( IsUnitHV( dir,true ))
186 return( false );
187 
188  if ( start_at_from ) {
189  incr = -.1;
190  base = &s->from->me;
191  } else {
192  incr = .1;
193  base = &s->to->me;
194  }
195 
196  t = .5-incr;
197  memset(&average_dir,0,sizeof(average_dir));
198  while ( t>0 && t<1.0 ) {
199  pos.x = ((s->splines[0].a*t+s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
200  pos.y = ((s->splines[1].a*t+s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
201 
202  average_dir.x += (pos.x-base->x); average_dir.y += (pos.y-base->y);
203  t += incr;
204  }
205 
206  len = sqrt( pow( average_dir.x,2 ) + pow( average_dir.y,2 ));
207  if ( len==0 )
208 return( false );
209  average_dir.x /= len; average_dir.y /= len;
210  normal.x = average_dir.y; normal.y = - average_dir.x;
211 
212  t = .5-incr;
213  while ( t>0 && t<1.0 ) {
214  pos.x = ((s->splines[0].a*t+s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
215  pos.y = ((s->splines[1].a*t+s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
216  off = (pos.x-base->x)*normal.x + (pos.y-base->y)*normal.y;
217  if ( off<-dist_error_hv || off>dist_error_hv )
218 return( false );
219  t += incr;
220  }
221 
222  if ( UnitsParallel( dir,&normal,true )) {
223  /* prefer the direction which is closer to horizontal/vertical */
224  if ( (dx=dir->x)<0 ) dx = -dx;
225  if ( (dy=dir->y)<0 ) dy = -dy;
226  d = (dx<dy) ? dx : dy;
227  if ( (ax=average_dir.x)<0 ) ax = -ax;
228  if ( (ay=average_dir.y)<0 ) ay = -ay;
229  a = (ax<ay) ? ax : ay;
230  if ( d<a )
231 return( false );
232  }
233 
234  *dir = average_dir;
235 return( true );
236 }
237 
238 static int IsSplinePeak( struct glyphdata *gd,struct pointdata *pd,int outer,int is_x,int flags );
239 
240 static void PointInit( struct glyphdata *gd,SplinePoint *sp, SplineSet *ss ) {
241  struct pointdata *pd, *prevpd=NULL, *nextpd=NULL;
242  double len, same;
243  int hv;
244 
245  if ( sp->ptindex >= gd->pcnt )
246 return;
247  pd = &gd->points[sp->ptindex];
248  pd->sp = sp;
249  pd->ss = ss;
250  pd->x_extr = pd->y_extr = 0;
251  pd->base = sp->me;
252  pd->ttfindex = sp->ttfindex;
253  pd->nextcnt = pd->prevcnt = 0;
254  pd->nextstems = pd->prevstems = NULL;
255  pd->next_is_l = pd->prev_is_l = NULL;
256 
257  if ( !sp->nonextcp && gd->order2 && sp->nextcpindex < gd->realcnt ) {
258 
259  nextpd = &gd->points[sp->nextcpindex];
260  nextpd->ss = ss;
261  nextpd->x_extr = nextpd->y_extr = 0;
262  nextpd->base = sp->nextcp;
263  nextpd->ttfindex = sp->nextcpindex;
264  }
265  if ( !sp->noprevcp && gd->order2 && sp->prev != NULL &&
266  sp->prev->from->nextcpindex < gd->realcnt ) {
267 
268  nextpd = &gd->points[sp->prev->from->nextcpindex];
269  nextpd->ss = ss;
270  nextpd->x_extr = nextpd->y_extr = 0;
271  nextpd->base = sp->prevcp;
272  nextpd->ttfindex = sp->prev->from->nextcpindex;
273  }
274 
275  if ( sp->next==NULL ) {
276  pd->nextunit.x = ss->first->me.x - sp->me.x;
277  pd->nextunit.y = ss->first->me.y - sp->me.y;
278  pd->nextlinear = true;
279  } else if ( sp->next->knownlinear ) {
280  pd->nextunit.x = sp->next->to->me.x - sp->me.x;
281  pd->nextunit.y = sp->next->to->me.y - sp->me.y;
282  pd->nextlinear = true;
283  } else if ( sp->nonextcp ) {
284  pd->nextunit.x = sp->next->to->prevcp.x - sp->me.x;
285  pd->nextunit.y = sp->next->to->prevcp.y - sp->me.y;
286  } else {
287  pd->nextunit.x = sp->nextcp.x - sp->me.x;
288  pd->nextunit.y = sp->nextcp.y - sp->me.y;
289  }
290  len = sqrt( pow( pd->nextunit.x,2 ) + pow( pd->nextunit.y,2 ));
291  if ( len==0 )
292  pd->nextzero = true;
293  else {
294  pd->nextlen = len;
295  pd->nextunit.x /= len;
296  pd->nextunit.y /= len;
297  if ( sp->next!=NULL && !sp->next->knownlinear )
298  SplineFigureOpticalSlope(sp->next,true,&pd->nextunit);
299  hv = IsUnitHV( &pd->nextunit,true );
300  if ( hv == 2 ) {
301  pd->nextunit.x = 0; pd->nextunit.y = pd->nextunit.y>0 ? 1 : -1;
302  } else if ( hv == 1 ) {
303  pd->nextunit.y = 0; pd->nextunit.x = pd->nextunit.x>0 ? 1 : -1;
304  }
305  if ( pd->nextunit.y==0 ) pd->next_hor = true;
306  else if ( pd->nextunit.x==0 ) pd->next_ver = true;
307 
308  if ( nextpd != NULL ) {
309  nextpd->prevunit.x = -pd->nextunit.x;
310  nextpd->prevunit.y = -pd->nextunit.y;
311  }
312  }
313 
314  if ( sp->prev==NULL ) {
315  pd->prevunit.x = ss->last->me.x - sp->me.x;
316  pd->prevunit.y = ss->last->me.y - sp->me.y;
317  pd->prevlinear = true;
318  } else if ( sp->prev->knownlinear ) {
319  pd->prevunit.x = sp->prev->from->me.x - sp->me.x;
320  pd->prevunit.y = sp->prev->from->me.y - sp->me.y;
321  pd->prevlinear = true;
322  } else if ( sp->noprevcp ) {
323  pd->prevunit.x = sp->prev->from->nextcp.x - sp->me.x;
324  pd->prevunit.y = sp->prev->from->nextcp.y - sp->me.y;
325  } else {
326  pd->prevunit.x = sp->prevcp.x - sp->me.x;
327  pd->prevunit.y = sp->prevcp.y - sp->me.y;
328  }
329  len = sqrt( pow( pd->prevunit.x,2 ) + pow( pd->prevunit.y,2 ));
330  if ( len==0 )
331  pd->prevzero = true;
332  else {
333  pd->prevlen = len;
334  pd->prevunit.x /= len;
335  pd->prevunit.y /= len;
336  if ( sp->prev!=NULL && !sp->prev->knownlinear )
337  SplineFigureOpticalSlope(sp->prev,false,&pd->prevunit);
338  hv = IsUnitHV( &pd->prevunit,true );
339  if ( hv == 2 ) {
340  pd->prevunit.x = 0; pd->prevunit.y = pd->prevunit.y>0 ? 1 : -1;
341  } else if ( hv == 1 ) {
342  pd->prevunit.y = 0; pd->prevunit.x = pd->prevunit.x>0 ? 1 : -1;
343  }
344  if ( pd->prevunit.y==0 ) pd->prev_hor = true;
345  else if ( pd->prevunit.x==0 ) pd->prev_ver = true;
346 
347  if ( prevpd != NULL ) {
348  prevpd->nextunit.x = -pd->prevunit.x;
349  prevpd->nextunit.y = -pd->prevunit.y;
350  }
351  }
352  {
353  same = pd->prevunit.x*pd->nextunit.x + pd->prevunit.y*pd->nextunit.y;
354  if ( same<-.95 )
355  pd->colinear = true;
356  }
357  if (( pd->prev_hor || pd->next_hor ) && pd->colinear ) {
358  if ( IsSplinePeak( gd,pd,false,false,1 )) pd->y_extr = 1;
359  else if ( IsSplinePeak( gd,pd,true,false,1 )) pd->y_extr = 2;
360  } else if (( pd->prev_ver || pd->next_ver ) && pd->colinear ) {
361  if ( IsSplinePeak( gd,pd,true,true,1 )) pd->x_extr = 1;
362  else if ( IsSplinePeak( gd,pd,false,true,1 )) pd->x_extr = 2;
363  } else {
364  if (( pd->nextunit.y < 0 && pd->prevunit.y < 0 ) || ( pd->nextunit.y > 0 && pd->prevunit.y > 0 )) {
365  if ( IsSplinePeak( gd,pd,false,false,2 )) pd->y_corner = 1;
366  else if ( IsSplinePeak( gd,pd,true,false,2 )) pd->y_corner = 2;
367  }
368  if (( pd->nextunit.x < 0 && pd->prevunit.x < 0 ) || ( pd->nextunit.x > 0 && pd->prevunit.x > 0 )) {
369  if ( IsSplinePeak( gd,pd,true,true,2 )) pd->x_corner = 1;
370  else if ( IsSplinePeak( gd,pd,false,true,2 )) pd->x_corner = 2;
371  }
372  }
374  if (( pd->y_corner || pd->y_extr ) &&
375  RealNear( pd->nextunit.x,-pd->prevunit.x ) &&
376  RealNear( pd->nextunit.y,pd->prevunit.y ) && !pd->nextzero)
377  pd->symetrical_h = true;
378  else if (( pd->x_corner || pd->x_extr ) &&
379  RealNear( pd->nextunit.y,-pd->prevunit.y ) &&
380  RealNear( pd->nextunit.x,pd->prevunit.x ) && !pd->nextzero)
381  pd->symetrical_v = true;
382  }
383 }
384 
386  double t,x,y;
387  DBounds b;
388 
389  b.minx = b.maxx = s->from->me.x;
390  b.miny = b.maxy = s->from->me.y;
391  if ( s->to->me.x<b.minx ) b.minx = s->to->me.x;
392  else if ( s->to->me.x>b.maxx ) b.maxx = s->to->me.x;
393  if ( s->to->me.y<b.miny ) b.miny = s->to->me.y;
394  else if ( s->to->me.y>b.maxy ) b.maxy = s->to->me.y;
395  if ( s->to->prevcp.x<b.minx ) b.minx = s->to->prevcp.x;
396  else if ( s->to->prevcp.x>b.maxx ) b.maxx = s->to->prevcp.x;
397  if ( s->to->prevcp.y<b.miny ) b.miny = s->to->prevcp.y;
398  else if ( s->to->prevcp.y>b.maxy ) b.maxy = s->to->prevcp.y;
399  if ( s->from->nextcp.x<b.minx ) b.minx = s->from->nextcp.x;
400  else if ( s->from->nextcp.x>b.maxx ) b.maxx = s->from->nextcp.x;
401  if ( s->from->nextcp.y<b.miny ) b.miny = s->from->nextcp.y;
402  else if ( s->from->nextcp.y>b.maxy ) b.maxy = s->from->nextcp.y;
403 
404  if ( line->splines[0].c!=0 ) {
405  t = (b.minx-line->splines[0].d)/line->splines[0].c;
406  y = line->splines[1].c*t+line->splines[1].d;
407  if ( y>=b.miny && y<=b.maxy )
408 return( true );
409  t = (b.maxx-line->splines[0].d)/line->splines[0].c;
410  y = line->splines[1].c*t+line->splines[1].d;
411  if ( y>=b.miny && y<=b.maxy )
412 return( true );
413  }
414  if ( line->splines[1].c!=0 ) {
415  t = (b.miny-line->splines[1].d)/line->splines[1].c;
416  x = line->splines[0].c*t+line->splines[0].d;
417  if ( x>=b.minx && x<=b.maxx )
418 return( true );
419  t = (b.maxy-line->splines[1].d)/line->splines[1].c;
420  x = line->splines[0].c*t+line->splines[0].d;
421  if ( x>=b.minx && x<=b.maxx )
422 return( true );
423  }
424 return( false );
425 }
426 
427 static int stcmp(const void *_p1, const void *_p2) {
428  const struct st *stpt1 = _p1, *stpt2 = _p2;
429  if ( stpt1->lt>stpt2->lt )
430 return( 1 );
431  else if ( stpt1->lt<stpt2->lt )
432 return( -1 );
433 
434 return( 0 );
435 }
436 
437 static int line_pt_cmp( const void *_p1, const void *_p2 ) {
438  struct pointdata * const *pd1 = _p1, * const *pd2 = _p2;
439  struct linedata *line;
440  double ppos1=0,ppos2=0;
441 
442  if ( (*pd1)->prevline != NULL &&
443  ( (*pd1)->prevline == (*pd2)->prevline || (*pd1)->prevline == (*pd2)->nextline ))
444  line = (*pd1)->prevline;
445  else if ( (*pd1)->nextline != NULL &&
446  ( (*pd1)->nextline == (*pd2)->prevline || (*pd1)->nextline == (*pd2)->nextline ))
447  line = (*pd1)->nextline;
448  else
449 return( 0 );
450 
451  ppos1 = ( (*pd1)->sp->me.x - line->online.x ) * line->unit.x +
452  ( (*pd1)->sp->me.y - line->online.y ) * line->unit.y;
453  ppos2 = ( (*pd2)->sp->me.x - line->online.x ) * line->unit.x +
454  ( (*pd2)->sp->me.y - line->online.y ) * line->unit.y;
455 
456  if ( ppos1>ppos2 )
457 return( 1 );
458  else if ( ppos1<ppos2 )
459 return( -1 );
460  else
461 return( 0 );
462 }
463 
464 static int segment_cmp(const void *_s1, const void *_s2) {
465  const struct segment *s1 = _s1, *s2 = _s2;
466  if ( s1->start<s2->start )
467 return( -1 );
468  else if ( s1->start>s2->start )
469 return( 1 );
470 
471 return( 0 );
472 }
473 
474 static int proj_cmp(const void *_p1, const void *_p2) {
475  struct pointdata * const *p1 = _p1, * const *p2 = _p2;
476  if ( (*p1)->projection<(*p2)->projection )
477 return( -1 );
478  else if ( (*p1)->projection>(*p2)->projection )
479 return( 1 );
480 
481 return( 0 );
482 }
483 
484 static void AssignStemToPoint( struct pointdata *pd,struct stemdata *stem,int is_next, int left ) {
485  struct stemdata ***stems;
486  int i, *stemcnt, **is_l;
487 
488  stems = ( is_next ) ? &pd->nextstems : &pd->prevstems;
489  stemcnt = ( is_next ) ? &pd->nextcnt : &pd->prevcnt;
490  is_l = ( is_next ) ? &pd->next_is_l : &pd->prev_is_l;
491  for ( i=0; i<*stemcnt; i++ ) {
492  if ((*stems)[i] == stem )
493 return;
494  }
495 
496  *stems = realloc( *stems,( *stemcnt+1 )*sizeof( struct stemdata *));
497  *is_l = realloc( *is_l, ( *stemcnt+1 )*sizeof( int ));
498  (*stems)[*stemcnt] = stem;
499  (*is_l )[*stemcnt] = left;
500  (*stemcnt)++;
501 }
502 
503 int IsStemAssignedToPoint( struct pointdata *pd,struct stemdata *stem,int is_next ) {
504  struct stemdata **stems;
505  int i, stemcnt;
506 
507  stems = ( is_next ) ? pd->nextstems : pd->prevstems;
508  stemcnt = ( is_next ) ? pd->nextcnt : pd->prevcnt;
509 
510  for ( i=0; i<stemcnt; i++ ) {
511  if ( stems[i] == stem )
512 return( i );
513  }
514 return( -1 );
515 }
516 
518  struct stemdata *stem ) {
519 
520  struct pointdata *tpd;
521 
522  if ( sp == NULL )
523 return( -1 );
524  if ( sp->ttfindex < gd->realcnt )
525 return( sp->ttfindex );
526  if ( !sp->nonextcp && sp->nextcpindex < gd->realcnt ) {
527  tpd = &gd->points[sp->nextcpindex];
528  if ( IsStemAssignedToPoint( tpd,stem,false ) != -1 )
529 return( sp->nextcpindex );
530  }
531  if ( !sp->noprevcp && sp->prev != NULL &&
532  sp->prev->from->nextcpindex < gd->realcnt ) {
533  tpd = &gd->points[sp->prev->from->nextcpindex];
534  if ( IsStemAssignedToPoint( tpd,stem,true ) != -1 )
535 return( sp->prev->from->nextcpindex );
536  }
537 return( -1 );
538 }
539 
540 static int LineType(struct st *st,int i, int cnt,Spline *line) {
541  SplinePoint *sp;
542  BasePoint nextcp, prevcp, here;
543  double dn, dp;
544 
545  if ( st[i].st>.01 && st[i].st<.99 )
546 return( 0 ); /* Not near an end-point, just a normal line */
547  if ( i+1>=cnt )
548 return( 0 ); /* No following spline */
549  if ( st[i+1].st>.01 && st[i+1].st<.99 )
550 return( 0 ); /* Following spline not near an end-point, can't */
551  /* match to this one, just a normal line */
552  if ( st[i].st<.5 && st[i+1].st>.5 ) {
553  if ( st[i+1].s->to->next!=st[i].s )
554 return( 0 );
555  sp = st[i].s->from;
556  } else if ( st[i].st>.5 && st[i+1].st<.5 ) {
557  if ( st[i].s->to->next!=st[i+1].s )
558 return( 0 );
559  sp = st[i].s->to;
560  } else
561 return( 0 );
562 
563  if ( !sp->nonextcp )
564  nextcp = sp->nextcp;
565  else
566  nextcp = sp->next->to->me;
567  if ( !sp->noprevcp )
568  prevcp = sp->prevcp;
569  else
570  prevcp = sp->prev->from->me;
571  here.x = line->splines[0].c*(st[i].st+st[i+1].st)/2 + line->splines[0].d;
572  here.y = line->splines[1].c*(st[i].st+st[i+1].st)/2 + line->splines[1].d;
573 
574  nextcp.x -= here.x; nextcp.y -= here.y;
575  prevcp.x -= here.x; prevcp.y -= here.y;
576 
577  dn = nextcp.x*line->splines[1].c - nextcp.y*line->splines[0].c;
578  dp = prevcp.x*line->splines[1].c - prevcp.y*line->splines[0].c;
579  if ( dn*dp<0 ) /* splines away move on opposite sides of the line */
580 return( 1 ); /* Treat this line and the next as one */
581  /* We assume that a rounding error gave us one erroneous intersection (or we went directly through the endpoint) */
582  else
583 return( 2 ); /* Ignore both this line and the next */
584  /* Intersects both in a normal fashion */
585 }
586 
587 static int MonotonicOrder(Spline **sspace,Spline *line,struct st *stspace) {
588  Spline *s;
589  int i,j,k,cnt;
590  BasePoint pts[9];
591  extended lts[10], sts[10];
592 
593  for ( i=j=0; (s=sspace[j])!=NULL; ++j ) {
594  if ( BBoxIntersectsLine(s,line) ) {
595  /* Lines parallel to the direction we are testing just get in the */
596  /* way and don't add any useful info */
597  if ( s->islinear &&
598  RealNear(line->splines[0].c*s->splines[1].c,
599  line->splines[1].c*s->splines[0].c))
600  continue;
601  if ( SplinesIntersect(line,s,pts,lts,sts)<=0 )
602  continue;
603  for ( k=0; sts[k]!=-1; ++k ) {
604  if ( sts[k]>=0 && sts[k]<=1 ) {
605  stspace[i].s = s;
606  stspace[i].lt = lts[k];
607  stspace[i++].st = sts[k];
608  }
609  }
610  }
611  }
612  stspace[i].s = NULL;
613  cnt = i;
614  qsort(stspace,cnt,sizeof(struct st),stcmp);
615 return( cnt );
616 }
617 
618 static Spline *MonotonicFindAlong(Spline *line,struct st *stspace,int cnt,
619  Spline *findme, double *other_t) {
620  Spline *s;
621  int i;
622  int eo; /* I do horizontal/vertical by winding number */
623  /* But figuring winding number with respect to a */
624  /* diagonal line is hard. So I use even-odd */
625  /* instead. */
626 
627  eo = 0;
628  for ( i=0; i<cnt; ++i ) {
629  s = stspace[i].s;
630  if ( s==findme ) {
631  if ( (eo&1) && i>0 ) {
632  *other_t = stspace[i-1].st;
633 return( stspace[i-1].s );
634  } else if ( !(eo&1) && i+1<cnt ) {
635  *other_t = stspace[i+1].st;
636 return( stspace[i+1].s );
637  }
638  fprintf( stderr, "MonotonicFindAlong: Ran out of intersections.\n" );
639 return( NULL );
640  }
641  if ( i+1<cnt && stspace[i+1].s==findme )
642  ++eo;
643  else switch ( LineType(stspace,i,cnt,line) ) {
644  case 0: /* Normal spline */
645  ++eo;
646  break;
647  case 1: /* Intersects at end-point & next entry is other side */
648  ++eo; /* And the two sides continue in approximately the */
649  ++i; /* same direction */
650  break;
651  case 2: /* Intersects at end-point & next entry is other side */
652  ++i; /* And the two sides go in opposite directions */
653  break;
654  default:
655  break;
656 }
657  }
658  fprintf( stderr, "MonotonicFindAlong: Never found our spline.\n" );
659 return( NULL );
660 }
661 
662 static int MonotonicFindStemBounds(Spline *line,struct st *stspace,int cnt,
663  double fudge,struct stemdata *stem ) {
664  int i,j;
665  int eo; /* I do horizontal/vertical by winding number */
666  /* But figuring winding number with respect to a */
667  /* diagonal line is hard. So I use even-odd */
668  /* instead. */
669  double pos, npos;
670  double lmin = ( stem->lmin < -fudge ) ? stem->lmin : -fudge;
671  double lmax = ( stem->lmax > fudge ) ? stem->lmax : fudge;
672  double rmin = ( stem->rmin < -fudge ) ? stem->rmin : -fudge;
673  double rmax = ( stem->rmax > fudge ) ? stem->rmax : fudge;
674  lmin -= .0001; lmax += .0001; rmin -= .0001; rmax += .0001;
675 
676  eo = 0;
677  for ( i=0; i<cnt; ++i ) {
678  pos = (line->splines[0].c*stspace[i].lt + line->splines[0].d - stem->left.x)*stem->l_to_r.x +
679  (line->splines[1].c*stspace[i].lt + line->splines[1].d - stem->left.y)*stem->l_to_r.y;
680  npos = 1e4;
681  if ( i+1<cnt )
682  npos = (line->splines[0].c*stspace[i+1].lt + line->splines[0].d - stem->left.x)*stem->l_to_r.x +
683  (line->splines[1].c*stspace[i+1].lt + line->splines[1].d - stem->left.y)*stem->l_to_r.y;
684 
685  if ( pos>=lmin && pos<=lmax ) {
686  if ( (eo&1) && i>0 )
687  j = i-1;
688  else if ( !(eo&1) && i+1<cnt )
689  j = i+1;
690  else
691 return( false );
692  pos = (line->splines[0].c*stspace[j].lt + line->splines[0].d - stem->right.x)*stem->l_to_r.x +
693  (line->splines[1].c*stspace[j].lt + line->splines[1].d - stem->right.y)*stem->l_to_r.y;
694  if ( pos >= rmin && pos <= rmax )
695 return( true );
696  }
697  if ( i+1 < cnt && npos >= lmin && npos <= lmax )
698  ++eo;
699  else switch ( LineType(stspace,i,cnt,line) ) {
700  case 0: /* Normal spline */
701  ++eo;
702  break;
703  case 1: /* Intersects at end-point & next entry is other side */
704  ++eo; /* And the two sides continue in approximately the */
705  ++i; /* same direction */
706  break;
707  case 2: /* Intersects at end-point & next entry is other side */
708  ++i; /* And the two sides go in opposite directions */
709  break;
710  default:
711  break;
712  }
713  }
714 return( false );
715 }
716 
717 static int MatchWinding(struct monotonic ** space,int i,int nw,int winding,int which,int idx) {
718  struct monotonic *m;
719  int j,cnt=0;
720 
721  if (( nw<0 && winding>0 ) || (nw>0 && winding<0)) {
722  winding = nw;
723  for ( j=i-1; j>=0; --j ) {
724  m = space[j];
725  winding += ((&m->xup)[which] ? 1 : -1 );
726  if ( winding==0 ) {
727  if ( cnt == idx )
728 return( j );
729  cnt++;
730  }
731  }
732  } else {
733  winding = nw;
734  for ( j=i+1; space[j]!=NULL; ++j ) {
735  m = space[j];
736  winding += ((&m->xup)[which] ? 1 : -1 );
737  if ( winding==0 ) {
738  if ( cnt == idx )
739 return( j );
740  cnt++;
741  }
742  }
743  }
744 return( -1 );
745 }
746 
747 static int FindMatchingHVEdge( struct glyphdata *gd,struct pointdata *pd,
748  int is_next,Spline **edges,double *other_t,double *dist ) {
749 
750  double test, t, start, end;
751  int which;
752  Spline *s;
753  Monotonic *m;
754  int winding, nw, i, j, ret=0;
755  struct monotonic **space;
756  BasePoint *dir, d, hv;
757 
758  /* Things are difficult if we go exactly through the point. Move off */
759  /* to the side a tiny bit and hope that doesn't matter */
760  if ( is_next==2 ) {
761  /* Consider the case of the bottom of the circumflex (or a chevron) */
762  /* Think of it as a flattend breve. It is symetrical and we want to */
763  /* note the vertical distance between the two points that define */
764  /* the bottom, so treat them as a funky stem */
765  /* \ \ / / */
766  /* \ \ / / */
767  /* \ \ / / */
768  /* \ + / */
769  /* \ / */
770  /* + */
771  hv.x = pd->symetrical_h ? 1.0 : 0.0;
772  hv.y = pd->symetrical_v ? 1.0 : 0.0;
773  dir = &hv;
774  t = .001;
775  s = pd->sp->next; /* Could just as easily be prev */
776  } else if ( is_next ) {
777  s = pd->sp->next;
778  t = .001;
779  dir = &pd->nextunit;
780  } else {
781  s = pd->sp->prev;
782  t = .999;
783  dir = &pd->prevunit;
784  }
785  if (( d.x = dir->x )<0 ) d.x = -d.x;
786  if (( d.y = dir->y )<0 ) d.y = -d.y;
787  which = d.x<d.y; /* closer to vertical */
788 
789  if ( s==NULL ) /* Somehow we got an open contour? */
790 return( 0 );
791 
792  test = ((s->splines[which].a*t+s->splines[which].b)*t+s->splines[which].c)*t+s->splines[which].d;
793  MonotonicFindAt(gd->ms,which,test,space = gd->space);
794 
795  winding = 0;
796  for ( i=0; space[i]!=NULL; ++i ) {
797  m = space[i];
798  nw = ((&m->xup)[which] ? 1 : -1 );
799  if ( m->s == s && t>=m->tstart && t<=m->tend ) {
800  start = m->other;
801  break;
802  }
803  winding += nw;
804  }
805  if ( space[i]==NULL ) {
806  fprintf( stderr, "FindMatchinHVEdge didn't\n" );
807 return( 0 );
808  }
809 
810  j = MatchWinding(space,i,nw,winding,which,0);
811  if ( j!=-1 ) {
812  other_t[0] = space[j]->t;
813  end = space[j]->other;
814  dist[0] = end - start;
815  if ( dist[0] < 0 ) dist[0] = -dist[0];
816  edges[0] = space[j]->s;
817  ret++;
818  }
819  if ( ret > 0 && is_next != 2 && ( pd->x_extr == 1 || pd->y_extr == 1 )) {
820  j = MatchWinding(space,i,nw,winding,which,1);
821  if ( j!=-1 ) {
822  other_t[ret] = space[j]->t;
823  end = space[j]->other;
824  dist[ret] = end - start;
825  if ( dist[ret] < 0 ) dist[ret] = -dist[ret];
826  edges[ret] = space[j]->s;
827  ret++;
828  }
829  }
830 return( ret );
831 }
832 
834  BasePoint perturbed;
835 
836  for (;;) {
837  perturbed.x = ((s->splines[0].a*t+s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
838  perturbed.y = ((s->splines[1].a*t+s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
839  if ( !RealWithin( perturbed.x,bp->x,.01 ) || !RealWithin( perturbed.y,bp->y,.01 ))
840  break;
841  if ( t<.5 ) {
842  t *= 2;
843  if ( t>.5 )
844  break;
845  } else {
846  t = 1- 2*(1-t);
847  if ( t<.5 )
848  break;
849  }
850  }
851 return( perturbed );
852 }
853 
854 static void MakeVirtualLine(struct glyphdata *gd,BasePoint *perturbed,
855  BasePoint *dir,Spline *myline,SplinePoint *end1, SplinePoint *end2) {
856 
857  BasePoint norm, absnorm;
858  SplineSet *spl;
859  Spline *s, *first;
860  double t1, t2;
861  int i, cnt;
862 
863  if ( gd->stspace==NULL ) {
864  for ( i=0; i<2; ++i ) {
865  cnt = 0;
866  for ( spl=gd->sc->layers[gd->layer].splines; spl!=NULL; spl=spl->next ) {
867  first = NULL;
868  if ( spl->first->prev!=NULL ) {
869  for ( s=spl->first->next; s!=first; s=s->to->next ) {
870  if ( first==NULL ) first = s;
871  if ( i )
872  gd->sspace[cnt] = s;
873  ++cnt;
874  }
875  }
876  }
877  if ( !i ) {
878  gd->scnt = cnt;
879  gd->sspace = malloc((cnt+1)*sizeof(Spline *));
880  } else
881  gd->sspace[cnt] = NULL;
882  }
883  gd->stspace = malloc((3*cnt+2)*sizeof(struct st));
884  SplineCharFindBounds(gd->sc,&gd->size);
885  gd->size.minx -= 10; gd->size.miny -= 10;
886  gd->size.maxx += 10; gd->size.maxy += 10;
887  }
888 
889  norm.x = -dir->y;
890  norm.y = dir->x;
891  absnorm = norm;
892  if ( absnorm.x<0 ) absnorm.x = -absnorm.x;
893  if ( absnorm.y<0 ) absnorm.y = -absnorm.y;
894 
895  memset(myline,0,sizeof(*myline));
896  memset(end1,0,sizeof(*end1));
897  memset(end2,0,sizeof(*end2));
898  myline->knownlinear = myline->islinear = true;
899 
900  if ( absnorm.x > absnorm.y ) {
901  /* Greater change in x than in y */
902  t1 = (gd->size.minx-perturbed->x)/norm.x;
903  t2 = (gd->size.maxx-perturbed->x)/norm.x;
904  myline->splines[0].d = gd->size.minx;
905  myline->splines[0].c = gd->size.maxx-gd->size.minx;
906  myline->splines[1].d = perturbed->y+t1*norm.y;
907  myline->splines[1].c = (t2-t1)*norm.y;
908  } else {
909  t1 = (gd->size.miny-perturbed->y)/norm.y;
910  t2 = (gd->size.maxy-perturbed->y)/norm.y;
911  myline->splines[1].d = gd->size.miny;
912  myline->splines[1].c = gd->size.maxy-gd->size.miny;
913  myline->splines[0].d = perturbed->x+t1*norm.x;
914  myline->splines[0].c = (t2-t1)*norm.x;
915  }
916  end1->me.x = myline->splines[0].d;
917  end2->me.x = myline->splines[0].d + myline->splines[0].c;
918  end1->me.y = myline->splines[1].d;
919  end2->me.y = myline->splines[1].d + myline->splines[1].c;
920  end1->nextcp = end1->prevcp = end1->me;
921  end2->nextcp = end2->prevcp = end2->me;
922  end1->nonextcp = end1->noprevcp = end2->nonextcp = end2->noprevcp = true;
923  end1->next = myline; end2->prev = myline;
924  myline->from = end1; myline->to = end2;
925 }
926 
927 static int FindMatchingEdge( struct glyphdata *gd, struct pointdata *pd,
928  int is_next,Spline **edges ) {
929 
930  BasePoint *dir, vert, perturbed, diff;
931  Spline myline;
932  SplinePoint end1, end2;
933  double *other_t = is_next==2 ? &pd->both_e_t : is_next ? pd->next_e_t : pd->prev_e_t;
934  double *dist = is_next ? pd->next_dist : pd->prev_dist;
935  double t ;
936  Spline *s;
937  int cnt;
938 
939  dist[0] = 0; dist[1] = 0;
940  if (( is_next && ( pd->next_hor || pd->next_ver )) ||
941  ( !is_next && ( pd->prev_hor || pd->prev_ver )) ||
942  is_next == 2 )
943 return( FindMatchingHVEdge(gd,pd,is_next,edges,other_t,dist));
944 
945  if ( is_next ) {
946  dir = &pd->nextunit;
947  t = .001;
948  s = pd->sp->next;
949  } else {
950  dir = &pd->prevunit;
951  t = .999;
952  s = pd->sp->prev;
953  }
954  /* For spline segments which have slope close enough to the font's italic */
955  /* slant look for an opposite edge along the horizontal direction, rather */
956  /* than along the normal for the point's next/previous unit. This allows */
957  /* us e. g. to detect serifs in italic fonts */
958  if ( gd->has_slant ) {
959  if ( UnitsParallel( dir,&gd->slant_unit,true )) {
960  vert.x = 0; vert.y = 1;
961  dir = &vert;
962  }
963  }
964 
965  if ( s==NULL || ( gd->only_hv && !IsUnitHV( dir,false )))
966 return( 0 );
967 
968  diff.x = s->to->me.x-s->from->me.x; diff.y = s->to->me.y-s->from->me.y;
969  if ( diff.x<.03 && diff.x>-.03 && diff.y<.03 && diff.y>-.03 )
970 return( 0 );
971 
972  /* Don't base the line on the current point, we run into rounding errors */
973  /* where lines that should intersect it don't. Instead perturb it a tiny*/
974  /* bit in the direction along the spline */
975  perturbed = PerturbAlongSpline( s,&pd->sp->me,t );
976 
977  MakeVirtualLine(gd,&perturbed,dir,&myline,&end1,&end2);
978  /* prev_e_t = next_e_t = both_e_t =. This is where these guys are set */
979  cnt = MonotonicOrder(gd->sspace,&myline,gd->stspace);
980  edges[0] = MonotonicFindAlong(&myline,gd->stspace,cnt,s,other_t);
981 return( edges[0] != NULL );
982 }
983 
984 static int StillStem(struct glyphdata *gd,double fudge,BasePoint *pos,struct stemdata *stem ) {
985  Spline myline;
986  SplinePoint end1, end2;
987  int cnt, ret;
988 
989  MakeVirtualLine( gd,pos,&stem->unit,&myline,&end1,&end2 );
990  cnt = MonotonicOrder( gd->sspace,&myline,gd->stspace );
991  ret = MonotonicFindStemBounds( &myline,gd->stspace,cnt,fudge,stem );
992 return( ret );
993 }
994 
995 static int CornerCorrectSide( struct pointdata *pd,int x_dir,int is_l ) {
996  int corner = ( x_dir ) ? pd->x_corner : pd->y_corner;
997  int start = (( x_dir && is_l ) || ( !x_dir && !is_l ));
998  double unit_p, unit_n;
999 
1000  unit_p = (&pd->prevunit.x)[!x_dir];
1001  unit_n = (&pd->nextunit.x)[!x_dir];
1002 return( ( start && (
1003  ( corner == 1 && unit_p > 0 && unit_n > 0 ) ||
1004  ( corner == 2 && unit_p < 0 && unit_n < 0 ))) ||
1005  ( !start && (
1006  ( corner == 1 && unit_p < 0 && unit_n < 0 ) ||
1007  ( corner == 2 && unit_p > 0 && unit_n > 0 ))));
1008 }
1009 
1010 static int IsCorrectSide( struct glyphdata *gd,struct pointdata *pd,
1011  int is_next,int is_l,BasePoint *dir ) {
1012 
1013  Spline *sbase, myline;
1014  SplinePoint *sp = pd->sp, end1, end2;
1015  BasePoint perturbed;
1016  int i, hv, is_x, ret = false, winding = 0, cnt, eo;
1017  double t, test;
1018  struct monotonic **space, *m;
1019 
1020  hv = IsUnitHV( dir,true );
1021  if (( hv == 2 && pd->x_corner ) || ( hv == 1 && pd->y_corner ))
1022 return( CornerCorrectSide( pd,( hv == 2 ),is_l ));
1023 
1024  sbase = ( is_next ) ? sp->next : sp->prev;
1025  t = ( is_next ) ? 0.001 : 0.999;
1026  perturbed = PerturbAlongSpline( sbase,&sp->me,t );
1027 
1028  if ( hv ) {
1029  is_x = ( hv == 2 );
1030  test = ( is_x ) ? perturbed.y : perturbed.x;
1031  MonotonicFindAt( gd->ms,is_x,test,space = gd->space );
1032  for ( i=0; space[i]!=NULL; ++i ) {
1033  m = space[i];
1034  winding = ((&m->xup)[is_x] ? 1 : -1 );
1035  if ( m->s == sbase )
1036  break;
1037  }
1038  if ( space[i]!=NULL )
1039  ret = (( is_l && winding == 1 ) || ( !is_l && winding == -1 ));
1040  } else {
1041  MakeVirtualLine( gd,&perturbed,dir,&myline,&end1,&end2 );
1042  cnt = MonotonicOrder( gd->sspace,&myline,gd->stspace );
1043  eo = -1;
1044  is_x = fabs( dir->y ) > fabs( dir->x );
1045  /* If a diagonal stem is more vertical than horizontal, then our */
1046  /* virtual line will go from left to right. It will first intersect */
1047  /* the left side of the stem, if the stem also points north-east. */
1048  /* In any other case the virtual line will first intersect the right */
1049  /* side. */
1050  i = ( is_x && dir->y > 0 ) ? 0 : cnt-1;
1051  while ( i >= 0 && i <= cnt-1 ) {
1052  eo = ( eo != 1 ) ? 1 : 0;
1053  if ( gd->stspace[i].s == sbase )
1054  break;
1055  if ( is_x && dir->y > 0 ) i++;
1056  else i--;
1057  }
1058  ret = ( is_l == eo );
1059  }
1060 return( ret );
1061 }
1062 
1063 /* In TrueType I want to make sure that everything on a diagonal line remains */
1064 /* on the same line. Hence we compute the line. Also we are interested in */
1065 /* points that are on the intersection of two lines */
1066 static struct linedata *BuildLine(struct glyphdata *gd,struct pointdata *pd,int is_next ) {
1067  int i;
1068  BasePoint *dir, *base, *start, *end;
1069  struct pointdata **pspace = gd->pspace, *pd2;
1070  int pcnt=0, is_l, hv;
1071  double dist_error;
1072  struct linedata *line;
1073  double off, firstoff, lastoff, lmin=0, lmax=0;
1074 
1075  dir = is_next ? &pd->nextunit : &pd->prevunit;
1076  is_l = IsCorrectSide( gd,pd,is_next,true,dir );
1077  dist_error = ( IsUnitHV( dir,true )) ? dist_error_hv : dist_error_diag ; /* Diagonals are harder to align */
1078  if ( dir->x==0 && dir->y==0 )
1079 return( NULL );
1080  base = &pd->sp->me;
1081 
1082  for ( i= (pd - gd->points)+1; i<gd->pcnt; ++i ) if ( gd->points[i].sp!=NULL ) {
1083  pd2 = &gd->points[i];
1084  off = ( pd2->sp->me.x - base->x )*dir->y -
1085  ( pd2->sp->me.y - base->y )*dir->x;
1086  if ( off <= lmax - 2*dist_error || off >= lmin + 2*dist_error )
1087  continue;
1088  if ( off < 0 && off < lmin ) lmin = off;
1089  else if ( off > 0 && off > lmax ) lmax = off;
1090 
1091  if ((( UnitsParallel( dir,&pd2->nextunit,true ) && pd2->nextline==NULL ) &&
1092  IsCorrectSide( gd,pd2,true,is_l,dir )) ||
1093  (( UnitsParallel( dir,&pd2->prevunit,true ) && pd2->prevline==NULL ) &&
1094  IsCorrectSide( gd,pd2,false,is_l,dir )))
1095  pspace[pcnt++] = pd2;
1096  }
1097 
1098  if ( pcnt==0 )
1099 return( NULL );
1100  if ( pcnt==1 ) {
1101  /* if the line consists of just these two points, only count it as */
1102  /* a true line if the two immediately follow each other */
1103  if (( pd->sp->next->to != pspace[0]->sp || !pd->sp->next->knownlinear ) &&
1104  ( pd->sp->prev->from != pspace[0]->sp || !pd->sp->prev->knownlinear ))
1105 return( NULL );
1106  }
1107 
1108  line = &gd->lines[gd->linecnt++];
1109  line->pcnt = pcnt+1;
1110  line->points = malloc((pcnt+1)*sizeof(struct pointdata *));
1111  line->points[0] = pd;
1112  line->unit = *dir;
1113  line->is_left = is_l;
1114  if ( dir->x < 0 || dir->y == -1 ) {
1115  line->unit.x = -line->unit.x;
1116  line->unit.y = -line->unit.y;
1117  }
1118  line->online = *base;
1119  if ( is_next ) {
1120  pd->nextline = line;
1121  if ( pd->colinear ) pd->prevline = line;
1122  } else {
1123  pd->prevline = line;
1124  if ( pd->colinear ) pd->nextline = line;
1125  }
1126  for ( i=0; i<pcnt; ++i ) {
1127  if ( UnitsParallel( dir,&pspace[i]->nextunit,true ) && pspace[i]->nextline==NULL ) {
1128  pspace[i]->nextline = line;
1129  if ( pspace[i]->colinear )
1130  pspace[i]->prevline = line;
1131  }
1132  if ( UnitsParallel( dir,&pspace[i]->prevunit,true ) && pspace[i]->prevline==NULL ) {
1133  pspace[i]->prevline = line;
1134  if ( pspace[i]->colinear )
1135  pspace[i]->nextline = line;
1136  }
1137  line->points[i+1] = pspace[i];
1138  }
1139  qsort( line->points,line->pcnt,sizeof( struct pointdata * ),line_pt_cmp );
1140  start = &line->points[0]->sp->me;
1141  end = &line->points[pcnt]->sp->me;
1142  /* Now recalculate the line unit vector basing on its starting and */
1143  /* terminal points */
1144  line->unit.x = ( end->x - start->x );
1145  line->unit.y = ( end->y - start->y );
1146  line->length = sqrt( pow( line->unit.x,2 ) + pow( line->unit.y,2 ));
1147  line->unit.x /= line->length;
1148  line->unit.y /= line->length;
1149  hv = IsUnitHV( &line->unit,true );
1150  if ( hv == 2 ) {
1151  line->unit.x = 0; line->unit.y = 1;
1152  } else if ( hv == 1 ) {
1153  line->unit.x = 1; line->unit.y = 0;
1154  } else if ( gd->has_slant && UnitsParallel( &line->unit,&gd->slant_unit,true )) {
1155  firstoff = ( start->x - base->x )*gd->slant_unit.y -
1156  ( start->y - base->y )*gd->slant_unit.x;
1157  lastoff = ( end->x - base->x )*gd->slant_unit.y -
1158  ( end->y - base->y )*gd->slant_unit.x;
1159  if ( fabs( firstoff ) < 2*dist_error && fabs( lastoff ) < 2*dist_error )
1160  line->unit = gd->slant_unit;
1161  }
1162 return( line );
1163 }
1164 
1165 static BasePoint MiddleUnit( BasePoint *unit1, BasePoint *unit2 ) {
1166  BasePoint u1, u2, ret;
1167  double hyp;
1168  int hv;
1169 
1170  u1 = *unit1; u2 = *unit2;
1171  if ( u1.x*u2.x + u1.y*u2.y < 0 ) {
1172  u2.x = -u2.x; u2.y = -u2.y;
1173  }
1174  ret.x = ( u1.x + u2.x )/2;
1175  ret.y = ( u1.y + u2.y )/2;
1176  hyp = sqrt( pow( ret.x,2 ) + pow( ret.y,2 ));
1177  ret.x /= hyp;
1178  ret.y /= hyp;
1179 
1180  hv = IsUnitHV( &ret,true );
1181  if ( hv ) {
1182  ret.x = ( hv == 1 ) ? 1 : 0;
1183  ret.y = ( hv == 1 ) ? 0 : 1;
1184  }
1185 return( ret );
1186 }
1187 
1188 static uint8 IsStubOrIntersection( struct glyphdata *gd, BasePoint *dir1,
1189  struct pointdata *pd1, struct pointdata *pd2, int is_next1, int is_next2 ) {
1190  int i;
1191  int exc=0;
1192  double dist, off, ext, norm1, norm2, opp, angle;
1193  double mid_err = ( stem_slope_error + stub_slope_error )/2;
1194  SplinePoint *sp1, *sp2, *nsp;
1195  BasePoint hvdir, *dir2, *odir1, *odir2;
1196  struct pointdata *npd;
1197  struct linedata *line;
1198 
1199  sp1 = pd1->sp; sp2 = pd2->sp;
1200  dir2 = ( is_next2 ) ? &pd2->nextunit : &pd2->prevunit;
1201  hvdir.x = ( int ) rint( dir1->x );
1202  hvdir.y = ( int ) rint( dir1->y );
1203 
1204  line = is_next2 ? pd2->nextline : pd2->prevline;
1205  if ( !IsUnitHV( dir2,true ) && line != NULL )
1206  dir2 = &line->unit;
1207 
1208  odir1 = ( is_next1 ) ? &pd1->prevunit : &pd1->nextunit;
1209  odir2 = ( is_next2 ) ? &pd2->prevunit : &pd2->nextunit;
1210 
1211  angle = fabs( GetUnitAngle( dir1,dir2 ));
1212  if ( angle > (double)stub_slope_error*1.5 && angle < PI - (double)stub_slope_error*1.5 )
1213 return( 0 );
1214 
1215  /* First check if it is a slightly slanted line or a curve which joins */
1216  /* a straight line under an angle close to 90 degrees. There are many */
1217  /* glyphs where circles or curved features are intersected by or */
1218  /* connected to vertical or horizontal straight stems (the most obvious */
1219  /* cases are Greek Psi and Cyrillic Yu), and usually it is highly desired to */
1220  /* mark such an intersection with a hint */
1221  norm1 = ( sp1->me.x - sp2->me.x ) * odir2->x +
1222  ( sp1->me.y - sp2->me.y ) * odir2->y;
1223  norm2 = ( sp2->me.x - sp1->me.x ) * odir1->x +
1224  ( sp2->me.y - sp1->me.y ) * odir1->y;
1225  /* if this is a real stub or intersection, then vectors on both sides */
1226  /* of out going-to-be stem should point in the same direction. So */
1227  /* the following value should be positive */
1228  opp = dir1->x * dir2->x + dir1->y * dir2->y;
1229  if (( angle <= mid_err || angle >= PI - mid_err ) &&
1230  opp > 0 && norm1 < 0 && norm2 < 0 && UnitsParallel( odir1,odir2,true ) &&
1231  ( UnitsOrthogonal( dir1,odir1,false ) || UnitsOrthogonal( dir2,odir1,false )))
1232 return( 2 );
1233  if (( angle <= mid_err || angle >= PI - mid_err ) &&
1234  opp > 0 && (( norm1 < 0 && pd1->colinear &&
1235  IsUnitHV( dir1,true ) && UnitsOrthogonal( dir1,odir2,false )) ||
1236  ( norm2 < 0 && pd2->colinear &&
1237  IsUnitHV( dir2,true ) && UnitsOrthogonal( dir2,odir1,false ))))
1238 return( 4 );
1239 
1240  /* Now check if our 2 points form a serif termination or a feature stub */
1241  /* The check is pretty dumb: it returns 'true' if all the following */
1242  /* conditions are met: */
1243  /* - both the points belong to the same contour; */
1244  /* - there are no more than 3 other points between them; */
1245  /* - anyone of those intermediate points is positioned by such a way */
1246  /* that it falls inside the stem formed by our 2 base point and */
1247  /* the vector we are checking and its distance from the first point */
1248  /* along that vector is not larger than the stem width; */
1249  /* - none of the intermediate points is parallel to the vector direction */
1250  /* (otherwise we should have checked against that point instead) */
1251  if ( !UnitsParallel( dir1,&hvdir,false ))
1252 return( 0 );
1253 
1254  dist = ( sp1->me.x - sp2->me.x ) * dir1->y -
1255  ( sp1->me.y - sp2->me.y ) * dir1->x;
1256  nsp = sp1;
1257 
1258  for ( i=0; i<4; i++ ) {
1259  if (( is_next1 && nsp->prev == NULL ) || ( !is_next1 && nsp->next == NULL ))
1260 return( 0 );
1261 
1262  nsp = ( is_next1 ) ? nsp->prev->from : nsp->next->to;
1263  if ( ( i>0 && nsp == sp1 ) || nsp == sp2 )
1264  break;
1265 
1266  npd = &gd->points[nsp->ptindex];
1267  if (UnitsParallel( &npd->nextunit,&hvdir,false ) ||
1268  UnitsParallel( &npd->prevunit,&hvdir,false ))
1269  break;
1270 
1271  ext = ( sp1->me.x - nsp->me.x ) * hvdir.x +
1272  ( sp1->me.y - nsp->me.y ) * hvdir.y;
1273  if ( ext < 0 ) ext = -ext;
1274  if (( dist > 0 && ext > dist ) || ( dist < 0 && ext < dist ))
1275  break;
1276 
1277  off = ( sp1->me.x - nsp->me.x ) * hvdir.y -
1278  ( sp1->me.y - nsp->me.y ) * hvdir.x;
1279  if (( dist > 0 && ( off <= 0 || off >= dist )) ||
1280  ( dist < 0 && ( off >= 0 || off <= dist )))
1281  exc++;
1282  }
1283 
1284  if ( nsp == sp2 && exc == 0 )
1285 return( 1 );
1286 
1287 return( 0 );
1288 }
1289 
1290 /* We normalize all stem unit vectors so that they point between 90 and 270 */
1291 /* degrees, as this range is optimal for sorting diagonal stems. This means */
1292 /* that vertical stems will normally point top to bottom, but for diagonal */
1293 /* stems (even if their angle is actually very close to vertical) the opposite */
1294 /* direction is also possible. Sometimes we "normalize" such stems converting */
1295 /* them to vertical. In such a case we have to swap their edges too. */
1296 static void SwapEdges( struct glyphdata *gd,struct stemdata *stem ) {
1297  BasePoint tpos;
1298  struct pointdata *tpd;
1299  struct linedata *tl;
1300  struct stem_chunk *chunk;
1301  double toff;
1302  int i, j, temp;
1303 
1304  tpos = stem->left; stem->left = stem->right; stem->right = tpos;
1305  toff = stem->lmin; stem->lmin = stem->rmax; stem->rmax = toff;
1306  toff = stem->rmin; stem->rmin = stem->lmax; stem->lmax = toff;
1307  tl = stem->leftline; stem->leftline = stem->rightline; stem->rightline = tl;
1308 
1309  for ( i=0; i<stem->chunk_cnt; ++i ) {
1310  chunk = &stem->chunks[i];
1311  tpd = chunk->l; chunk->l = chunk->r; chunk->r = tpd;
1312  temp = chunk->lpotential; chunk->lpotential = chunk->rpotential; chunk->rpotential = temp;
1313  temp = chunk->lnext; chunk->lnext = chunk->rnext; chunk->rnext = temp;
1314  temp = chunk->ltick; chunk->ltick = chunk->rtick; chunk->rtick = temp;
1315 
1316  tpd = chunk->l;
1317  if ( tpd != NULL ) {
1318  for ( j=0; j<tpd->nextcnt; j++ )
1319  if ( tpd->nextstems[j] == stem )
1320  tpd->next_is_l[j] = true;
1321  for ( j=0; j<tpd->prevcnt; j++ )
1322  if ( tpd->prevstems[j] == stem )
1323  tpd->prev_is_l[j] = true;
1324  }
1325 
1326  tpd = chunk->r;
1327  if ( tpd != NULL ) {
1328  for ( j=0; j<tpd->nextcnt; j++ )
1329  if ( tpd->nextstems[j] == stem )
1330  tpd->next_is_l[j] = false;
1331  for ( j=0; j<tpd->prevcnt; j++ )
1332  if ( tpd->prevstems[j] == stem )
1333  tpd->prev_is_l[j] = false;
1334  }
1335  }
1336 
1337  /* In case of a quadratic contour invert assignments to stem sides */
1338  /* also for off-curve points */
1339  if ( gd->order2 ) {
1340  for ( i=0; i<gd->realcnt; i++ ) if ( gd->points[i].sp == NULL ) {
1341  tpd = &gd->points[i];
1342  for ( j=0; j<tpd->nextcnt; j++ )
1343  if ( tpd->nextstems[j] == stem )
1344  tpd->next_is_l[j] = !tpd->next_is_l[j];
1345  for ( j=0; j<tpd->prevcnt; j++ )
1346  if ( tpd->prevstems[j] == stem )
1347  tpd->prev_is_l[j] = !tpd->prev_is_l[j];
1348  }
1349  }
1350 }
1351 
1352 static int StemFitsHV( struct stemdata *stem,int is_x,uint8 mask ) {
1353  int i,cnt;
1354  double loff,roff;
1355  double lmin=0,lmax=0,rmin=0,rmax=0;
1356  struct stem_chunk *chunk;
1357 
1358  cnt = stem->chunk_cnt;
1359 
1360  for ( i=0 ; i<stem->chunk_cnt; i++ ) {
1361  if( stem->chunks[i].stub & mask )
1362  break;
1363  }
1364  if ( i == stem->chunk_cnt )
1365 return( false );
1366  if ( stem->chunk_cnt == 1 )
1367 return( true );
1368 
1369  for ( i=0;i<cnt;i++ ) {
1370  chunk = &stem->chunks[i];
1371 
1372  if ( chunk->l != NULL ) {
1373  loff = ( chunk->l->sp->me.x - stem->left.x ) * !is_x -
1374  ( chunk->l->sp->me.y - stem->left.y ) * is_x;
1375  if ( loff < lmin ) lmin = loff;
1376  else if ( loff > lmax ) lmax = loff;
1377  }
1378  if ( chunk->r != NULL ) {
1379  roff = ( chunk->r->sp->me.x - stem->right.x ) * !is_x -
1380  ( chunk->r->sp->me.y - stem->right.y ) * is_x;
1381  if ( roff < rmin ) rmin = roff;
1382  else if ( roff > rmax ) rmax = roff;
1383  }
1384  }
1385  if ((( lmax - lmin ) < 2*dist_error_hv ) && (( rmax - rmin ) < 2*dist_error_hv ))
1386 return( true );
1387 return( false );
1388 }
1389 
1390 static int LineFitsHV( struct linedata *line ) {
1391  int i,cnt,is_x,hv;
1392  double off,min=0,max=0;
1393  struct pointdata *pd;
1394 
1395  cnt = line->pcnt;
1396  hv = IsUnitHV( &line->unit,true );
1397  if ( hv )
1398 return( true );
1399 
1400  hv = IsUnitHV( &line->unit,false );
1401  if ( !hv )
1402 return( false );
1403 
1404  is_x = ( hv == 1 ) ? 1 : 0;
1405  for ( i=0;i<cnt;i++ ) {
1406  pd = line->points[i];
1407 
1408  off = ( pd->base.x - line->online.x ) * !is_x -
1409  ( pd->base.y - line->online.y ) * is_x;
1410  if ( off < min ) min = off;
1411  else if ( off > max ) max = off;
1412  }
1413  if (( max - min ) < 2*dist_error_hv )
1414 return( true );
1415 return( false );
1416 }
1417 
1418 static int OnStem( struct stemdata *stem,BasePoint *test,int left ) {
1419  double dist_error, off;
1420  BasePoint *dir = &stem->unit;
1421  double max=0, min=0;
1422 
1423  /* Diagonals are harder to align */
1424  dist_error = IsUnitHV( dir,true ) ? dist_error_hv : dist_error_diag;
1425  if ( !stem->positioned ) dist_error = dist_error * 2;
1426  if ( dist_error > stem->width/2 ) dist_error = stem->width/2;
1427  if ( left ) {
1428  off = (test->x - stem->left.x)*dir->y - (test->y - stem->left.y)*dir->x;
1429  max = stem->lmax; min = stem->lmin;
1430  } else {
1431  off = (test->x - stem->right.x)*dir->y - (test->y - stem->right.y)*dir->x;
1432  max = stem->rmax; min = stem->rmin;
1433  }
1434 
1435  if ( off > ( max - dist_error ) && off < ( min + dist_error ) )
1436 return( true );
1437 
1438 return( false );
1439 }
1440 
1442  int force_hv,int strict,int cove ) {
1443  double dist_error, off1, off2;
1444  BasePoint dir = stem->unit;
1445  int hv, hv_strict;
1446  double lmax=0, lmin=0, rmax=0, rmin=0;
1447 
1448  hv = ( force_hv ) ? IsUnitHV( &dir,false ) : IsUnitHV( &dir,true );
1449  hv_strict = ( force_hv ) ? IsUnitHV( &dir,true ) : hv;
1450  if ( force_hv ) {
1451  if ( force_hv != hv )
1452 return( false );
1453  if ( !hv_strict && !StemFitsHV( stem,( hv == 1 ),7 ))
1454 return( false );
1455  if ( !hv_strict ) {
1456  dir.x = ( force_hv == 2 ) ? 0 : 1;
1457  dir.y = ( force_hv == 2 ) ? 1 : 0;
1458  }
1459  }
1460  /* Diagonals are harder to align */
1461  dist_error = ( hv ) ? dist_error_hv : dist_error_diag;
1462  if ( !strict ) {
1463  dist_error = dist_error * 2;
1464  lmax = stem->lmax; lmin = stem->lmin;
1465  rmax = stem->rmax; rmin = stem->rmin;
1466  }
1467  if ( dist_error > stem->width/2 ) dist_error = stem->width/2;
1468 
1469  off1 = (test1->x-stem->left.x)*dir.y - (test1->y-stem->left.y)*dir.x;
1470  off2 = (test2->x-stem->right.x)*dir.y - (test2->y-stem->right.y)*dir.x;
1471  if (off1 > ( lmax - dist_error ) && off1 < ( lmin + dist_error ) &&
1472  off2 > ( rmax - dist_error ) && off2 < ( rmin + dist_error )) {
1473  /* For some reasons in my patch from Feb 24 2008 I prohibited snapping */
1474  /* to stems point pairs which together form a bend, if at least */
1475  /* one point from the pair doesn't have exactly the same position as */
1476  /* the stem edge. Unfortunately I don't remember why I did this, but */
1477  /* this behavior has at least one obviously negative effect: it */
1478  /* prevents building a stem from chunks which describe an ark */
1479  /* intersected by some straight lines, even if the intersections lie */
1480  /* closely enough to the ark extremum. So don't apply this test */
1481  /* at least if the force_hv flag is on (which means either the */
1482  /* chunk or the stem itself is not exactly horizontal/vertical) */
1483  if ( !cove || force_hv || off1 == 0 || off2 == 0 )
1484 return( true );
1485  }
1486 
1487  off2 = (test2->x-stem->left.x)*dir.y - (test2->y-stem->left.y)*dir.x;
1488  off1 = (test1->x-stem->right.x)*dir.y - (test1->y-stem->right.y)*dir.x;
1489  if (off2 > ( lmax - dist_error ) && off2 < ( lmin + dist_error ) &&
1490  off1 > ( rmax - dist_error ) && off1 < ( rmin + dist_error )) {
1491  if ( !cove || force_hv || off1 == 0 || off2 == 0 )
1492 return( true );
1493  }
1494 
1495 return( false );
1496 }
1497 
1498 static int RecalcStemOffsets( struct stemdata *stem,BasePoint *dir,int left,int right ) {
1499  double off, err;
1500  double lmin=0, lmax=0, rmin=0, rmax=0;
1501  struct stem_chunk *chunk;
1502  int i;
1503 
1504  if ( !left && !right )
1505 return( false );
1506  err = ( IsUnitHV( dir,true )) ? dist_error_hv : dist_error_diag;
1507 
1508  if ( stem->chunk_cnt > 1 ) for ( i=0; i<stem->chunk_cnt; i++ ) {
1509  chunk = &stem->chunks[i];
1510  if ( left && chunk->l != NULL ) {
1511  off = ( chunk->l->sp->me.x - stem->left.x )*dir->y -
1512  ( chunk->l->sp->me.y - stem->left.y )*dir->x;
1513  if ( off < lmin ) lmin = off;
1514  else if ( off > lmax ) lmax = off;
1515  }
1516  if ( right && chunk->r != NULL ) {
1517  off = ( chunk->r->sp->me.x - stem->right.x )*dir->y +
1518  ( chunk->r->sp->me.y - stem->right.y )*dir->x;
1519  if ( off < rmin ) rmin = off;
1520  else if ( off > rmax ) rmax = off;
1521  }
1522  }
1523  if ( lmax - lmin < 2*err && rmax - rmin < 2*err ) {
1524  stem->lmin = lmin; stem->lmax = lmax;
1525  stem->rmin = rmin; stem->rmax = rmax;
1526 return( true );
1527  }
1528 return( false );
1529 }
1530 
1531 static void SetStemUnit( struct stemdata *stem,BasePoint dir ) {
1532  double width;
1533 
1534  width = ( stem->right.x - stem->left.x ) * dir.y -
1535  ( stem->right.y - stem->left.y ) * dir.x;
1536  if ( width < 0 ) {
1537  width = -width;
1538  dir.x = -dir.x;
1539  dir.y = -dir.y;
1540  }
1541  stem->unit = dir;
1542  stem->width = width;
1543 
1544  /* Guess at which normal we want */
1545  stem->l_to_r.x = dir.y; stem->l_to_r.y = -dir.x;
1546  /* If we guessed wrong, use the other */
1547  if (( stem->right.x-stem->left.x )*stem->l_to_r.x +
1548  ( stem->right.y-stem->left.y )*stem->l_to_r.y < 0 ) {
1549  stem->l_to_r.x = -stem->l_to_r.x;
1550  stem->l_to_r.y = -stem->l_to_r.y;
1551  }
1552 
1553  /* Recalculate left/right offsets relatively to new vectors */
1554  RecalcStemOffsets( stem,&dir,true,true );
1555 }
1556 
1557 static struct stem_chunk *AddToStem( struct glyphdata *gd,struct stemdata *stem,
1558  struct pointdata *pd1,struct pointdata *pd2,int is_next1, int is_next2, int cheat ) {
1559 
1560  int is_potential1 = false, is_potential2 = true;
1561  struct stem_chunk *chunk=NULL;
1562  BasePoint *dir = &stem->unit;
1563  BasePoint *test;
1564  int lincr = 1, rincr = 1;
1565  double off, dist_error;
1566  double loff = 0, roff = 0;
1567  double min = 0, max = 0;
1568  int i, in, ip, cpidx;
1569  struct pointdata *pd, *npd, *ppd;
1570 
1571  if ( cheat || stem->positioned ) is_potential2 = false;
1572  /* Diagonals are harder to align */
1573  dist_error = IsUnitHV( dir,true ) ? 2*dist_error_hv : 2*dist_error_diag;
1574  if ( dist_error > stem->width/2 ) dist_error = stem->width/2;
1575  max = stem->lmax;
1576  min = stem->lmin;
1577 
1578  /* The following swaps "left" and "right" points in case we have */
1579  /* started checking relatively to a wrong edge */
1580  if ( pd1 != NULL ) {
1581  test = &pd1->base;
1582  off = ( test->x - stem->left.x )*dir->y -
1583  ( test->y - stem->left.y )*dir->x;
1584  if (( !stem->ghost &&
1585  ( off < ( max - dist_error ) || off > ( min + dist_error ))) ||
1586  ( RealNear( stem->unit.x, 1) && stem->ghost && stem->width == 21 ) ||
1587  ( RealNear( stem->unit.x,0 ) && stem->ghost && stem->width == 20 )) {
1588  pd = pd1; pd1 = pd2; pd2 = pd;
1589  in = is_next1; is_next1 = is_next2; is_next2 = in;
1590  ip = is_potential1; is_potential1 = is_potential2; is_potential2 = ip;
1591  }
1592  }
1593 
1594  if ( pd1 == NULL ) lincr = 0;
1595  if ( pd2 == NULL ) rincr = 0;
1596  /* Now run through existing stem chunks and see if the chunk we are */
1597  /* going to add doesn't duplicate an existing one.*/
1598  for ( i=stem->chunk_cnt-1; i>=0; --i ) {
1599  chunk = &stem->chunks[i];
1600  if ( chunk->l == pd1 ) lincr = 0;
1601  if ( chunk->r == pd2 ) rincr = 0;
1602 
1603  if (( chunk->l == pd1 || pd1 == NULL ) && ( chunk->r == pd2 || pd2 == NULL )) {
1604  if ( !is_potential1 ) chunk->lpotential = false;
1605  if ( !is_potential2 ) chunk->rpotential = false;
1606  break;
1607  } else if (( chunk->l == pd1 && chunk->r == NULL ) || ( chunk->r == pd2 && chunk->l == NULL )) {
1608  if ( chunk->l == NULL ) {
1609  chunk->l = pd1;
1610  chunk->lpotential = is_potential1;
1611  chunk->lnext = is_next1;
1612  chunk->ltick = lincr;
1613  } else if ( chunk->r == NULL ) {
1614  chunk->r = pd2;
1615  chunk->rpotential = is_potential2;
1616  chunk->rnext = is_next2;
1617  chunk->rtick = rincr;
1618  }
1619  break;
1620  }
1621  }
1622 
1623  if ( i<0 ) {
1624  stem->chunks = realloc(stem->chunks,(stem->chunk_cnt+1)*sizeof(struct stem_chunk));
1625  chunk = &stem->chunks[stem->chunk_cnt++];
1626  chunk->parent = stem;
1627 
1628  chunk->l = pd1; chunk->lpotential = is_potential1;
1629  chunk->r = pd2; chunk->rpotential = is_potential2;
1630  chunk->ltick = lincr; chunk->rtick = rincr;
1631 
1632  chunk->lnext = is_next1;
1633  chunk->rnext = is_next2;
1634  chunk->stemcheat = cheat;
1635  chunk->stub = chunk->is_ball = false;
1636  chunk->l_e_idx = chunk->r_e_idx = 0;
1637  }
1638 
1639  if ( pd1!=NULL ) {
1640  loff = ( pd1->base.x - stem->left.x ) * stem->l_to_r.x +
1641  ( pd1->base.y - stem->left.y ) * stem->l_to_r.y;
1642  if ( is_next1==1 || is_next1==2 || pd1->colinear ) {
1643  AssignStemToPoint( pd1,stem,true,true );
1644  /* For quadratic layers assign the stem not only to */
1645  /* spline points, but to their control points as well */
1646  /* (this may be important for TTF instructions */
1647  if ( gd->order2 && !pd1->sp->nonextcp && pd1->sp->nextcpindex < gd->realcnt ) {
1648  cpidx = pd1->sp->nextcpindex;
1649  npd = &gd->points[cpidx];
1650  if ( OnStem( stem,&npd->base,true ))
1651  AssignStemToPoint( npd,stem,false,true );
1652  }
1653  }
1654  if ( is_next1==0 || is_next1==2 || pd1->colinear ) {
1655  AssignStemToPoint( pd1,stem,false,true );
1656  if ( gd->order2 && !pd1->sp->noprevcp && pd1->sp->prev != NULL &&
1657  pd1->sp->prev->from->nextcpindex < gd->realcnt ) {
1658  cpidx = pd1->sp->prev->from->nextcpindex;
1659  ppd = &gd->points[cpidx];
1660  if ( OnStem( stem,&ppd->base,true ))
1661  AssignStemToPoint( ppd,stem,true,true );
1662  }
1663  }
1664  }
1665  if ( pd2!=NULL ) {
1666  roff = ( pd2->base.x - stem->right.x ) * stem->l_to_r.x +
1667  ( pd2->base.y - stem->right.y ) * stem->l_to_r.y;
1668  if ( is_next2==1 || is_next2==2 || pd2->colinear ) {
1669  AssignStemToPoint( pd2,stem,true,false );
1670  if ( gd->order2 && !pd2->sp->nonextcp && pd2->sp->nextcpindex < gd->realcnt ) {
1671  cpidx = pd2->sp->nextcpindex;
1672  npd = &gd->points[cpidx];
1673  if ( OnStem( stem,&npd->base,false ))
1674  AssignStemToPoint( npd,stem,false,false );
1675  }
1676  }
1677  if ( is_next2==0 || is_next2==2 || pd2->colinear ) {
1678  AssignStemToPoint( pd2,stem,false,false );
1679  if ( gd->order2 && !pd2->sp->noprevcp && pd2->sp->prev != NULL &&
1680  pd2->sp->prev->from->nextcpindex < gd->realcnt ) {
1681  cpidx = pd2->sp->prev->from->nextcpindex;
1682  ppd = &gd->points[cpidx];
1683  if ( OnStem( stem,&ppd->base,false ))
1684  AssignStemToPoint( ppd,stem,true,false );
1685  }
1686  }
1687  }
1688  if ( loff < stem->lmin ) stem->lmin = loff;
1689  else if ( loff > stem->lmax ) stem->lmax = loff;
1690  if ( roff < stem->rmin ) stem->rmin = roff;
1691  else if ( roff > stem->rmax ) stem->rmax = roff;
1692  stem->lpcnt += lincr; stem->rpcnt += rincr;
1693 return( chunk );
1694 }
1695 
1696 static struct stemdata *FindStem( struct glyphdata *gd,struct pointdata *pd,
1697  struct pointdata *pd2,BasePoint *dir,int is_next2,int de ) {
1698 
1699  int i, cove, test_left, hv, stemcnt;
1700  struct stemdata *stem;
1701  BasePoint newdir;
1702 
1703  stemcnt = ( is_next2 ) ? pd2->nextcnt : pd2->prevcnt;
1704 
1705  for ( i=0; i<stemcnt; i++ ) {
1706  stem = ( is_next2 ) ? pd2->nextstems[i] : pd2->prevstems[i];
1707  test_left = ( is_next2 ) ? !pd2->next_is_l[i] : !pd2->prev_is_l[i];
1708 
1709  if (UnitsParallel( &stem->unit,dir,true ) &&
1710  OnStem( stem,&pd->sp->me,test_left ))
1711 return( stem );
1712  }
1713 
1714  cove = ( dir->x == 0 && pd->x_extr + pd2->x_extr == 3 ) ||
1715  ( dir->y == 0 && pd->y_extr + pd2->y_extr == 3 );
1716 
1717  /* First pass to check for strict matches */
1718  for ( i=0; i<gd->stemcnt; ++i ) {
1719  stem = &gd->stems[i];
1720  /* Ghost hints and BBox hits are usually generated after all other */
1721  /* hint types, but we can get them here in case we are generating */
1722  /* glyph data for a predefined hint layout. In this case they should */
1723  /* be excluded from the following tests */
1724  if ( stem->ghost || stem->bbox )
1725  continue;
1726 
1727  if ( UnitsParallel( &stem->unit,dir,true ) &&
1728  BothOnStem( stem,&pd->sp->me,&pd2->sp->me,false,true,cove )) {
1729  return( stem );
1730  }
1731  }
1732  /* One more pass. At this stage larger deviations are allowed */
1733  for ( i=0; i<gd->stemcnt; ++i ) {
1734  stem = &gd->stems[i];
1735  if ( stem->ghost || stem->bbox )
1736  continue;
1737 
1738  if ( UnitsParallel( &stem->unit,dir,true ) &&
1739  BothOnStem( stem,&pd->sp->me,&pd2->sp->me,false,false,cove )) {
1740 return( stem );
1741  }
1742  }
1743  if ( de )
1744 return( NULL );
1745 
1746  hv = IsUnitHV( dir,false );
1747  if ( !hv )
1748 return( NULL );
1749 
1750  for ( i=0; i<gd->stemcnt; ++i ) {
1751  stem = &gd->stems[i];
1752  if ( stem->ghost || stem->bbox )
1753  continue;
1754  if ( hv && BothOnStem( stem,&pd->base,&pd2->base,hv,false,cove )) {
1755  newdir.x = ( hv == 2 ) ? 0 : 1;
1756  newdir.y = ( hv == 2 ) ? 1 : 0;
1757  if ( hv == 2 && stem->unit.y < 0 )
1758  SwapEdges( gd,stem );
1759  if ( stem->unit.x != newdir.x )
1760  SetStemUnit( stem,newdir );
1761 return( stem );
1762  }
1763  }
1764 return( NULL );
1765 }
1766 
1767 static struct stemdata *NewStem( struct glyphdata *gd,BasePoint *dir,
1768  BasePoint *pos1, BasePoint *pos2 ) {
1769 
1770  struct stemdata * stem = &gd->stems[gd->stemcnt++];
1771  double width;
1772 
1773  stem->unit = *dir;
1774  if ( dir->x < 0 || dir->y == -1 ) {
1775  stem->unit.x = -stem->unit.x;
1776  stem->unit.y = -stem->unit.y;
1777  }
1778  width = ( pos2->x - pos1->x ) * stem->unit.y -
1779  ( pos2->y - pos1->y ) * stem->unit.x;
1780  if ( width > 0 ) {
1781  stem->left = *pos1;
1782  stem->right = *pos2;
1783  stem->width = width;
1784  } else {
1785  stem->left = *pos2;
1786  stem->right = *pos1;
1787  stem->width = -width;
1788  }
1789  /* Guess at which normal we want */
1790  stem->l_to_r.x = dir->y; stem->l_to_r.y = -dir->x;
1791  /* If we guessed wrong, use the other */
1792  if (( stem->right.x-stem->left.x )*stem->l_to_r.x +
1793  ( stem->right.y-stem->left.y )*stem->l_to_r.y < 0 ) {
1794  stem->l_to_r.x = -stem->l_to_r.x;
1795  stem->l_to_r.y = -stem->l_to_r.y;
1796  }
1797  stem->leftidx = stem->rightidx = -1;
1798  stem->leftline = stem->rightline = NULL;
1799  stem->lmin = stem->lmax = 0;
1800  stem->rmin = stem->rmax = 0;
1801  stem->ldone = stem->rdone = false;
1802  stem->lpcnt = stem->rpcnt = 0;
1803  stem->chunks = NULL;
1804  stem->chunk_cnt = 0;
1805  stem->ghost = stem->bbox = false;
1806  stem->positioned = false;
1807  stem->blue = -1;
1808 return( stem );
1809 }
1810 
1812  BasePoint *opposite,SplinePoint *basesp,uint8 is_stub ) {
1813 
1814  BasePoint n, o, *base = &basesp->me;
1815  SplinePoint *sp;
1816  double angle, mid_err = ( stem_slope_error + stub_slope_error )/2;
1817 
1818  sp = pd->sp;
1819  n = ( checknext ) ? pd->nextunit : pd->prevunit;
1820 
1821  angle = fabs( GetUnitAngle( dir,&n ));
1822  if (( !is_stub && angle > stem_slope_error && angle < PI - stem_slope_error ) ||
1823  ( is_stub & 1 && angle > stub_slope_error*1.5 && angle < PI - stub_slope_error*1.5 ) ||
1824  ( is_stub & 6 && angle > mid_err && angle < PI - mid_err ))
1825 return( false );
1826 
1827  /* Now sp must be on the same side of the spline as opposite */
1828  o.x = opposite->x-base->x; o.y = opposite->y-base->y;
1829  n.x = sp->me.x-base->x; n.y = sp->me.y-base->y;
1830  if ( ( o.x*dir->y - o.y*dir->x )*( n.x*dir->y - n.y*dir->x ) < 0 )
1831 return( false );
1832 
1833 return( true );
1834 }
1835 
1836 static int NearlyParallel( BasePoint *dir,Spline *other, double t ) {
1837  BasePoint odir;
1838  double olen;
1839 
1840  odir.x = (3*other->splines[0].a*t+2*other->splines[0].b)*t+other->splines[0].c;
1841  odir.y = (3*other->splines[1].a*t+2*other->splines[1].b)*t+other->splines[1].c;
1842  olen = sqrt( pow( odir.x,2 ) + pow( odir.y,2 ));
1843  if ( olen==0 )
1844 return( false );
1845  odir.x /= olen; odir.y /= olen;
1846 return( UnitsParallel( dir,&odir,false ));
1847 }
1848 
1849 static double NormalDist( BasePoint *to, BasePoint *from, BasePoint *perp ) {
1850  double len = (to->x-from->x)*perp->y - (to->y-from->y)*perp->x;
1851  if ( len<0 ) len = -len;
1852 return( len );
1853 }
1854 
1855 static struct stemdata *FindOrMakeHVStem( struct glyphdata *gd,
1856  struct pointdata *pd,struct pointdata *pd2,int is_h,int require_existing ) {
1857  int i,cove = false;
1858  struct stemdata *stem;
1859  BasePoint dir;
1860 
1861  dir.x = ( is_h ) ? 1 : 0;
1862  dir.y = ( is_h ) ? 0 : 1;
1863  if ( pd2 != NULL )
1864  cove = ( dir.x == 0 && pd->x_extr + pd2->x_extr == 3 ) ||
1865  ( dir.y == 0 && pd->y_extr + pd2->y_extr == 3 );
1866 
1867  for ( i=0; i<gd->stemcnt; ++i ) {
1868  stem = &gd->stems[i];
1869  if ( IsUnitHV( &stem->unit,true ) &&
1870  ( pd2 != NULL && BothOnStem( stem,&pd->sp->me,&pd2->sp->me,false,false,cove )))
1871  break;
1872  }
1873  if ( i==gd->stemcnt ) stem=NULL;
1874 
1875  if ( stem == NULL && pd2 != NULL && !require_existing )
1876  stem = NewStem( gd,&dir,&pd->sp->me,&pd2->sp->me );
1877 return( stem );
1878 }
1879 
1880 static int IsDiagonalEnd( struct glyphdata *gd,
1881  struct pointdata *pd1,struct pointdata *pd2,int is_next,int require_existing ) {
1882  /* suppose we have something like */
1883  /* *--* */
1884  /* \ \ */
1885  /* \ \ */
1886  /* Then let's create a vertical stem between the two points */
1887  /* (and a horizontal stem if the thing is rotated 90 degrees) */
1888  double width, length1, length2, dist1, dist2;
1889  BasePoint *pt1, *pt2, *dir1, *dir2, *prevdir1, *prevdir2;
1890  SplinePoint *prevsp1, *prevsp2;
1891  struct pointdata *prevpd1, *prevpd2;
1892  int hv;
1893 
1894  if ( pd1->colinear || pd2->colinear )
1895 return( false );
1896  pt1 = &pd1->sp->me; pt2 = &pd2->sp->me;
1897  /* Both key points of a diagonal end stem should have nearly the same */
1898  /* coordinate by x or y (otherwise we can't determine by which axis */
1899  /* it should be hinted) */
1900  if ( pt1->x >= pt2->x - dist_error_hv && pt1->x <= pt2->x + dist_error_hv ) {
1901  width = pd1->sp->me.y - pd2->sp->me.y;
1902  hv = 1;
1903  } else if ( pt1->y >= pt2->y - dist_error_hv && pt1->y <= pt2->y + dist_error_hv ) {
1904  width = pd1->sp->me.x - pd2->sp->me.x;
1905  hv = 2;
1906  } else
1907 return( false );
1908 
1909  dir1 = ( is_next ) ? &pd1->nextunit : &pd1->prevunit;
1910  dir2 = ( is_next ) ? &pd2->prevunit : &pd2->nextunit;
1911  if ( IsUnitHV( dir1,true )) /* Must be diagonal */
1912 return( false );
1913  prevsp1 = ( is_next ) ? pd1->sp->next->to : pd1->sp->prev->from;
1914  prevsp2 = ( is_next ) ? pd2->sp->prev->from : pd2->sp->next->to;
1915  prevpd1 = &gd->points[prevsp1->ptindex];
1916  prevpd2 = &gd->points[prevsp2->ptindex];
1917  prevdir1 = ( is_next ) ? &prevpd1->prevunit : &prevpd1->nextunit;
1918  prevdir2 = ( is_next ) ? &prevpd2->nextunit : &prevpd2->prevunit;
1919  /* Ensure we have got a real diagonal, i. e. its sides are parallel */
1920  if ( !UnitsParallel( dir1,dir2,true ) || !UnitsParallel( prevdir1,prevdir2,true ))
1921 return( false );
1922 
1923  /* Diagonal width should be smaller than its length */
1924  length1 = pow(( prevsp1->me.x - pt1->x ),2 ) + pow(( prevsp1->me.y - pt1->y ),2 );
1925  length2 = pow(( prevsp2->me.x - pt2->x ),2 ) + pow(( prevsp2->me.y - pt2->y ),2 );
1926  if ( length2 < length1 ) length1 = length2;
1927  if ( pow( width,2 ) > length1 )
1928 return( false );
1929 
1930  /* Finally exclude too short diagonals where the distance between key */
1931  /* points of one edge at the direction orthogonal to the unit vector */
1932  /* of the stem we are about to add is smaller than normal HV stem */
1933  /* fudge. Such diagonals may be later turned into HV stems, and we will */
1934  /* result into getting two coincident hints */
1935  dist1 = ( hv == 1 ) ? prevsp1->me.y - pt1->y : prevsp1->me.x - pt1->x;
1936  dist2 = ( hv == 1 ) ? prevsp2->me.y - pt2->y : prevsp2->me.x - pt2->x;
1937  if ( dist1 < 0 ) dist1 = -dist1;
1938  if ( dist2 < 0 ) dist2 = -dist2;
1939  if ( dist1 < 2*dist_error_hv && dist2 < 2*dist_error_hv )
1940 return( false );
1941 
1942 return( hv );
1943 }
1944 
1945 static struct stemdata *TestStem( struct glyphdata *gd,struct pointdata *pd,
1946  BasePoint *dir,SplinePoint *match,int is_next,int is_next2,int require_existing,uint8 is_stub,int eidx ) {
1947  struct pointdata *pd2;
1948  struct stemdata *stem, *destem;
1949  struct stem_chunk *chunk;
1950  struct linedata *otherline;
1951  double width;
1952  struct linedata *line, *line2;
1953  BasePoint *mdir, middle;
1954  int de=false, hv, l_changed;
1955 
1956  width = ( match->me.x - pd->sp->me.x )*dir->y -
1957  ( match->me.y - pd->sp->me.y )*dir->x;
1958  if ( width < 0 ) width = -width;
1959  if ( width < .5 )
1960 return( NULL ); /* Zero width stems aren't interesting */
1961  if (( is_next && pd->sp->next->to==match ) || ( !is_next && pd->sp->prev->from==match ))
1962 return( NULL ); /* Don't want a stem between two splines that intersect */
1963 
1964  pd2 = &gd->points[match->ptindex];
1965 
1966  line = is_next ? pd->nextline : pd->prevline;
1967  mdir = is_next2 ? &pd2->nextunit : &pd2->prevunit;
1968  line2 = is_next2 ? pd2->nextline : pd2->prevline;
1969  if ( !IsUnitHV( mdir,true ) && line2 != NULL )
1970  mdir = &line2->unit;
1971  if ( mdir->x==0 && mdir->y==0 )
1972 return( NULL ); /* cannot determine the opposite point's direction */
1973 
1974  if ( !UnitsParallel( mdir,dir,true ) && !is_stub )
1975 return( NULL ); /* Cannot make a stem if edges are not parallel (unless it is a serif) */
1976 
1977  if ( is_stub & 1 && !IsUnitHV( dir,true )) {
1978  /* For serifs we prefer the vector which is closer to horizontal/vertical */
1979  middle = MiddleUnit( dir,mdir );
1980  if ( UnitCloserToHV( &middle,dir ) == 1 && UnitCloserToHV( &middle,mdir ) == 1 )
1981  dir = &middle;
1982  else if ( UnitCloserToHV( mdir,dir ) == 1 )
1983  dir = mdir;
1984  if ( !IsUnitHV( dir,true ) &&
1985  ( hint_diagonal_ends || require_existing ))
1986  de = IsDiagonalEnd( gd,pd,pd2,is_next,require_existing );
1987  }
1988 
1989  stem = FindStem( gd,pd,pd2,dir,is_next2,de );
1990  destem = NULL;
1991  if ( de )
1992  destem = FindOrMakeHVStem( gd,pd,pd2,( de == 1 ),require_existing );
1993 
1994  if ( stem == NULL && !require_existing )
1995  stem = NewStem( gd,dir,&pd->sp->me,&match->me );
1996  if ( stem != NULL ) {
1997  chunk = AddToStem( gd,stem,pd,pd2,is_next,is_next2,false );
1998  if ( chunk != NULL ) {
1999  chunk->stub = is_stub;
2000  chunk->l_e_idx = chunk->r_e_idx = eidx;
2001  }
2002 
2003  if ( chunk != NULL && gd->linecnt > 0 ) {
2004  hv = IsUnitHV( &stem->unit,true );
2005  /* For HV stems allow assigning a line to a stem edge only */
2006  /* if that line also has an exactly HV vector */
2007  if ( line != NULL && (( !hv &&
2008  UnitsParallel( &stem->unit,&line->unit,true ) &&
2009  RecalcStemOffsets( stem,&line->unit,true,true )) ||
2010  ( hv && line->unit.x == stem->unit.x && line->unit.y == stem->unit.y ))) {
2011 
2012  otherline = NULL; l_changed = false;
2013  if (( stem->leftline == NULL ||
2014  stem->leftline->length < line->length ) && chunk->l == pd ) {
2015 
2016  stem->leftline = line;
2017  l_changed = true;
2018  otherline = stem->rightline;
2019  } else if (( stem->rightline == NULL ||
2020  stem->rightline->length < line->length ) && chunk->r == pd ) {
2021 
2022  stem->rightline = line;
2023  l_changed = true;
2024  otherline = stem->leftline;
2025  }
2026  /* If lines are attached to both sides of a diagonal stem, */
2027  /* then prefer the longer line */
2028  if ( !hv && l_changed && !stem->positioned &&
2029  ( otherline == NULL || ( otherline->length < line->length )))
2030  SetStemUnit( stem,line->unit );
2031  }
2032  if ( line2 != NULL && (( !hv &&
2033  UnitsParallel( &stem->unit,&line2->unit,true ) &&
2034  RecalcStemOffsets( stem,&line2->unit,true,true )) ||
2035  ( hv && line2->unit.x == stem->unit.x && line2->unit.y == stem->unit.y ))) {
2036 
2037  otherline = NULL; l_changed = false;
2038  if (( stem->leftline == NULL ||
2039  stem->leftline->length < line2->length ) && chunk->l == pd2 ) {
2040 
2041  stem->leftline = line2;
2042  l_changed = true;
2043  otherline = stem->rightline;
2044  } else if (( stem->rightline == NULL ||
2045  stem->rightline->length < line2->length ) && chunk->r == pd2 ) {
2046 
2047  stem->rightline = line2;
2048  l_changed = true;
2049  otherline = stem->leftline;
2050  }
2051  if ( !hv && l_changed && !stem->positioned &&
2052  ( otherline == NULL || ( otherline->length < line2->length )))
2053  SetStemUnit( stem,line2->unit );
2054  }
2055  }
2056  }
2057 
2058  if ( destem != NULL )
2059  AddToStem( gd,destem,pd,pd2,is_next,!is_next,1 );
2060 return( stem );
2061 }
2062 
2063 static double FindSameSlope(Spline *s,BasePoint *dir,double close_to) {
2064  double a, b, c, desc;
2065  double t1, t2;
2066  double d1, d2;
2067 
2068  if ( s==NULL )
2069 return( -1e4 );
2070 
2071  a = dir->x*s->splines[1].a*3 - dir->y*s->splines[0].a*3;
2072  b = dir->x*s->splines[1].b*2 - dir->y*s->splines[0].b*2;
2073  c = dir->x*s->splines[1].c - dir->y*s->splines[0].c ;
2074  if ( a!=0 ) {
2075  desc = b*b - 4*a*c;
2076  if ( desc<0 )
2077 return( -1e4 );
2078  desc = sqrt(desc);
2079  t1 = (-b+desc)/(2*a);
2080  t2 = (-b-desc)/(2*a);
2081  if ( (d1=t1-close_to)<0 ) d1 = -d1;
2082  if ( (d2=t2-close_to)<0 ) d2 = -d2;
2083  if ( d2<d1 && t2>=-.001 && t2<=1.001 )
2084  t1 = t2;
2085  } else if ( b!=0 )
2086  t1 = -c/b;
2087  else
2088 return( -1e4 );
2089 
2090 return( t1 );
2091 }
2092 
2093 /* This function is used when generating stem data for preexisting */
2094 /* stem hints. If we already know the desired hint position, then we */
2095 /* can safely assign to this hint any points which meet other conditions */
2096 /* but have no corresponding position at the opposite edge. */
2097 static int HalfStemNoOpposite( struct glyphdata *gd,struct pointdata *pd,
2098  struct stemdata *stem,BasePoint *dir,int is_next ) {
2099  int i, ret=0, allowleft, allowright, hv, corner;
2100  struct stemdata *tstem;
2101 
2102  for ( i=0; i<gd->stemcnt; ++i ) {
2103  tstem = &gd->stems[i];
2104  if ( tstem->bbox || !tstem->positioned || tstem == stem )
2105  continue;
2106  allowleft = ( !tstem->ghost || tstem->width == 20 );
2107  allowright = ( !tstem->ghost || tstem->width == 21 );
2108  hv = IsUnitHV( &tstem->unit,true );
2109  corner = (( pd->x_corner && hv == 2 ) || ( pd->y_corner && hv == 1 ));
2110 
2111  if ( UnitsParallel( &tstem->unit,dir,true ) || tstem->ghost || corner ) {
2112  if ( OnStem( tstem,&pd->sp->me,true ) && allowleft ) {
2113  if ( IsCorrectSide( gd,pd,is_next,true,&tstem->unit )) {
2114  AddToStem( gd,tstem,pd,NULL,is_next,false,false );
2115  ret++;
2116  }
2117  } else if ( OnStem( tstem,&pd->sp->me,false ) && allowright ) {
2118  if ( IsCorrectSide( gd,pd,is_next,false,&tstem->unit )) {
2119  AddToStem( gd,tstem,NULL,pd,false,is_next,false );
2120  ret++;
2121  }
2122  }
2123  }
2124  }
2125 return( ret );
2126 }
2127 
2128 static struct stemdata *HalfStem( struct glyphdata *gd,struct pointdata *pd,
2129  BasePoint *dir,Spline *other,double other_t,int is_next,int eidx ) {
2130  /* Find the spot on other where the slope is the same as dir */
2131  double t1;
2132  double width;
2133  BasePoint match;
2134  struct stemdata *stem = NULL, *tstem;
2135  struct pointdata *pd2 = NULL, *tpd;
2136  int i;
2137 
2138  t1 = FindSameSlope( other,dir,other_t );
2139  if ( t1==-1e4 )
2140 return( NULL );
2141  if ( t1<0 && other->from->prev!=NULL && gd->points[other->from->ptindex].colinear ) {
2142  other = other->from->prev;
2143  t1 = FindSameSlope(other,dir,1.0);
2144  } else if ( t1>1 && other->to->next!=NULL && gd->points[other->to->ptindex].colinear ) {
2145  other = other->to->next;
2146  t1 = FindSameSlope(other,dir,0.0);
2147  }
2148 
2149  if ( t1<-.001 || t1>1.001 )
2150 return( NULL );
2151 
2152  /* Ok. the opposite edge has the right slope at t1 */
2153  /* Now see if we can make a one sided stem out of these two */
2154  match.x = ((other->splines[0].a*t1+other->splines[0].b)*t1+other->splines[0].c)*t1+other->splines[0].d;
2155  match.y = ((other->splines[1].a*t1+other->splines[1].b)*t1+other->splines[1].c)*t1+other->splines[1].d;
2156 
2157  width = (match.x-pd->sp->me.x)*dir->y - (match.y-pd->sp->me.y)*dir->x;
2158  /* offset = (match.x-pd->sp->me.x)*dir->x + (match.y-pd->sp->me.y)*dir->y;*/
2159  if ( width<.5 && width>-.5 )
2160 return( NULL ); /* Zero width stems aren't interesting */
2161 
2162  if ( isnan(t1))
2163  IError( "NaN value in HalfStem" );
2164 
2165  if ( is_next ) {
2166  pd->nextedges[eidx] = other;
2167  pd->next_e_t[eidx] = t1;
2168  } else {
2169  pd->prevedges[eidx] = other;
2170  pd->prev_e_t[eidx] = t1;
2171  }
2172 
2173  /* In my experience the only case where this function may be useful */
2174  /* is when it occasionally finds a real spline point which for some */
2175  /* reasons has been neglected by other tests and yet forms a valid */
2176  /* pair for the first point. So run through points and see if we */
2177  /* have actually got just a position on spline midway between to points, */
2178  /* or it is a normal point allowing to make a normal stem chunk */
2179  for ( i=0; i<gd->pcnt; ++i ) {
2180  tpd = &gd->points[i];
2181  if ( tpd->sp != NULL && tpd->sp->me.x == match.x && tpd->sp->me.y == match.y ) {
2182  pd2 = tpd;
2183  break;
2184  }
2185  }
2186  for ( i=0; i<gd->stemcnt; ++i ) {
2187  tstem = &gd->stems[i];
2188  if ( UnitsParallel( &tstem->unit,dir,true ) &&
2189  BothOnStem( tstem,&pd->base,&match,false,false,false )) {
2190  stem = tstem;
2191  break;
2192  }
2193  }
2194  if ( stem == NULL )
2195  stem = NewStem(gd,dir,&pd->sp->me,&match);
2196 
2197  AddToStem( gd,stem,pd,pd2,is_next,false,false );
2198 return( stem );
2199 }
2200 
2201 static int ConnectsAcross( struct glyphdata *gd,SplinePoint *sp,
2202  int is_next,Spline *findme,int eidx ) {
2203  struct pointdata *pd = &gd->points[sp->ptindex];
2204  Spline *other, *test;
2205  BasePoint dir;
2206 
2207  other = ( is_next ) ? pd->nextedges[eidx] : pd->prevedges[eidx];
2208 
2209  if ( other==findme )
2210 return( true );
2211  if ( other==NULL )
2212 return( false );
2213 
2214  dir.x = ( is_next ) ? -pd->nextunit.x : pd->prevunit.x;
2215  dir.y = ( is_next ) ? -pd->nextunit.y : pd->prevunit.y;
2216  test = other->to->next;
2217  while ( test!=NULL && test != other &&
2218  gd->points[test->from->ptindex].nextunit.x * dir.x +
2219  gd->points[test->from->ptindex].nextunit.y * dir.y > 0 ) {
2220  if ( test==findme )
2221 return( true );
2222  test = test->to->next;
2223  }
2224 
2225  dir.x = ( is_next ) ? pd->nextunit.x : -pd->prevunit.x;
2226  dir.y = ( is_next ) ? pd->nextunit.y : -pd->prevunit.y;
2227  test = other->from->prev;
2228  while ( test!=NULL && test != other &&
2229  gd->points[test->to->ptindex].prevunit.x * dir.x +
2230  gd->points[test->to->ptindex].prevunit.y * dir.y > 0 ) {
2231  if ( test==findme )
2232 return( true );
2233  test = test->from->prev;
2234  }
2235 return( false );
2236 }
2237 
2238 static int ConnectsAcrossToStem( struct glyphdata *gd,struct pointdata *pd,
2239  int is_next,struct stemdata *target,int is_l,int eidx ) {
2240 
2241  Spline *other, *test;
2242  BasePoint dir;
2243  struct pointdata *tpd;
2244  int ecnt, stemidx;
2245 
2246  ecnt = ( is_next ) ? pd->next_e_cnt : pd->prev_e_cnt;
2247  if ( ecnt < eidx + 1 )
2248 return( false );
2249  other = ( is_next ) ? pd->nextedges[eidx] : pd->prevedges[eidx];
2250 
2251  test = other;
2252  dir.x = ( is_next ) ? pd->nextunit.x : -pd->prevunit.x;
2253  dir.y = ( is_next ) ? pd->nextunit.y : -pd->prevunit.y;
2254  do {
2255  tpd = &gd->points[test->to->ptindex];
2256  stemidx = IsStemAssignedToPoint( tpd,target,false );
2257  if ( stemidx != -1 && tpd->prev_is_l[stemidx] == !is_l &&
2258  IsSplinePeak( gd,tpd,rint( target->unit.y ),rint( target->unit.y ),7 ))
2259 return( true );
2260 
2261  test = test->to->next;
2262  } while ( test!=NULL && test != other && stemidx == -1 &&
2263  ( tpd->prevunit.x * dir.x + tpd->prevunit.y * dir.y >= 0 ));
2264 
2265  test = other;
2266  dir.x = ( is_next ) ? -pd->nextunit.x : pd->prevunit.x;
2267  dir.y = ( is_next ) ? -pd->nextunit.y : pd->prevunit.y;
2268  do {
2269  tpd = &gd->points[test->from->ptindex];
2270  stemidx = IsStemAssignedToPoint( tpd,target,true );
2271  if ( stemidx != -1 && tpd->next_is_l[stemidx] == !is_l &&
2272  IsSplinePeak( gd,tpd,rint( target->unit.y ),rint( target->unit.y ),7 ))
2273 return( true );
2274 
2275  test = test->from->prev;
2276  } while ( test!=NULL && test != other && stemidx == -1 &&
2277  ( tpd->nextunit.x * dir.x + tpd->nextunit.y * dir.y >= 0 ));
2278 return( false );
2279 }
2280 
2281 static double RecalcT( Spline *base,SplinePoint *from, SplinePoint *to, double curt ) {
2282  double baselen, fromlen, tolen, ret;
2283  Spline *cur;
2284 
2285  baselen = SplineLength( base );
2286  fromlen = baselen * curt;
2287  tolen = baselen * ( 1 - curt );
2288 
2289  cur = base->from->prev;
2290  while ( cur != NULL && cur->to != from ) {
2291  fromlen += SplineLength( cur );
2292  cur = cur->from->prev;
2293  }
2294  cur = base->to->next;
2295  while ( cur!= NULL && cur->from != to ) {
2296  tolen += SplineLength( cur );
2297  cur = cur->to->next;
2298  }
2299  ret = fromlen/( fromlen + tolen );
2300 return( ret );
2301 }
2302 
2303 static int BuildStem( struct glyphdata *gd,struct pointdata *pd,int is_next,
2304  int require_existing,int has_existing,int eidx ) {
2305  BasePoint *dir;
2306  Spline *other, *cur;
2307  double t;
2308  double tod, fromd, dist;
2309  SplinePoint *testpt, *topt, *frompt;
2310  struct linedata *line;
2311  struct pointdata *testpd, *topd, *frompd;
2312  int tp, fp, t_needs_recalc=false, ret=0;
2313  uint8 tstub=0, fstub=0;
2314  BasePoint opposite;
2315  struct stemdata *stem=NULL;
2316 
2317  if ( is_next ) {
2318  dir = &pd->nextunit;
2319  other = pd->nextedges[eidx];
2320  cur = pd->sp->next;
2321  t = pd->next_e_t[eidx];
2322  dist = pd->next_dist[eidx];
2323  } else {
2324  dir = &pd->prevunit;
2325  other = pd->prevedges[eidx];
2326  cur = pd->sp->prev;
2327  t = pd->prev_e_t[eidx];
2328  dist = pd->prev_dist[eidx];
2329  }
2330  topt = other->to; frompt = other->from;
2331  topd = &gd->points[topt->ptindex];
2332  frompd = &gd->points[frompt->ptindex];
2333 
2334  line = is_next ? pd->nextline : pd->prevline;
2335  if ( !IsUnitHV( dir,true ) && line != NULL)
2336  dir = &line->unit;
2337 
2338  if ( other==NULL )
2339 return( 0 );
2340 
2341  opposite.x = ((other->splines[0].a*t+other->splines[0].b)*t+other->splines[0].c)*t+other->splines[0].d;
2342  opposite.y = ((other->splines[1].a*t+other->splines[1].b)*t+other->splines[1].c)*t+other->splines[1].d;
2343 
2344  if ( eidx == 0 ) tstub = IsStubOrIntersection( gd,dir,pd,topd,is_next,false );
2345  if ( eidx == 0 ) fstub = IsStubOrIntersection( gd,dir,pd,frompd,is_next,true );
2346  tp = ParallelToDir( topd,false,dir,&opposite,pd->sp,tstub );
2347  fp = ParallelToDir( frompd,true,dir,&opposite,pd->sp,fstub );
2348 
2349  /* if none of the opposite points is parallel to the needed vector, then */
2350  /* give it one more chance by skipping those points and looking at the next */
2351  /* and previous one. This can be useful in situations where the opposite */
2352  /* edge cannot be correctly detected just because there are too many points */
2353  /* on the spline (which is a very common situation for poorly designed */
2354  /* fonts or fonts with quadratic splines). */
2355  /* But do that only for colinear spline segments and ensure that there are */
2356  /* no bends between two splines. */
2357  if ( !tp && ( !fp || t > 0.5 ) &&
2358  topd->colinear && &other->to->next != NULL ) {
2359  testpt = topt->next->to;
2360  testpd = &gd->points[testpt->ptindex];
2361  BasePoint *initdir = &topd->prevunit;
2362  while ( !tp && topd->colinear && pd->sp != testpt && other->from != testpt && (
2363  testpd->prevunit.x * initdir->x +
2364  testpd->prevunit.y * initdir->y > 0 )) {
2365 
2366  topt = testpt; topd = testpd;
2367  tp = ParallelToDir( topd,false,dir,&opposite,pd->sp,false );
2368  testpt = topt->next->to;
2369  testpd = &gd->points[testpt->ptindex];
2370  }
2371  if ( tp ) t_needs_recalc = true;
2372  }
2373  if ( !fp && ( !fp || t < 0.5 ) &&
2374  frompd->colinear && &other->from->prev != NULL ) {
2375  testpt = frompt->prev->from;
2376  testpd = &gd->points[testpt->ptindex];
2377  BasePoint *initdir = &frompd->prevunit;
2378  while ( !fp && frompd->colinear && pd->sp != testpt && other->to != testpt && (
2379  testpd->prevunit.x * initdir->x +
2380  testpd->prevunit.y * initdir->y > 0 )) {
2381 
2382  frompt = testpt; frompd = testpd;
2383  fp = ParallelToDir( frompd,true,dir,&opposite,pd->sp,false );
2384  testpt = frompt->prev->from;
2385  testpd = &gd->points[testpt->ptindex];
2386  }
2387  if ( fp ) t_needs_recalc = true;
2388  }
2389  if ( t_needs_recalc )
2390  t = RecalcT( other,frompt,topt,t );
2391  if ( !tp && !fp ) {
2392  if ( has_existing )
2393  ret = HalfStemNoOpposite( gd,pd,NULL,dir,is_next );
2394 return( ret );
2395  }
2396 
2397  /* We have several conflicting metrics for getting the "better" stem */
2398  /* Generally we prefer the stem with the smaller width (but not always. See tilde) */
2399  /* Generally we prefer the stem formed by the point closer to the intersection */
2400  tod = (1-t)*NormalDist( &topt->me,&pd->sp->me,dir );
2401  fromd = t*NormalDist( &frompt->me,&pd->sp->me,dir );
2402 
2403  if ( tp && (( tod<fromd ) ||
2404  ( !fp && ( tod<2*fromd || dist < topd->prev_dist[eidx] ||
2405  ConnectsAcross( gd,frompt,true,cur,eidx ) || NearlyParallel( dir,other,t ))))) {
2406  stem = TestStem( gd,pd,dir,topt,is_next,false,require_existing,tstub,eidx );
2407  }
2408  if ( stem == NULL && fp && (( fromd<tod ) ||
2409  ( !tp && ( fromd<2*tod || dist < frompd->next_dist[eidx] ||
2410  ConnectsAcross( gd,topt,false,cur,eidx ) || NearlyParallel( dir,other,t ))))) {
2411  stem = TestStem( gd,pd,dir,frompt,is_next,true,require_existing,fstub,eidx );
2412  }
2413  if ( eidx == 0 && stem == NULL && !require_existing && cur!=NULL &&
2414  !other->knownlinear && !cur->knownlinear )
2415  stem = HalfStem( gd,pd,dir,other,t,is_next,eidx );
2416  if ( stem != NULL ) ret = 1;
2417  if ( has_existing )
2418  ret += HalfStemNoOpposite( gd,pd,stem,dir,is_next );
2419 return( ret );
2420 }
2421 
2422 static void AssignLinePointsToStems( struct glyphdata *gd ) {
2423  struct pointdata *pd;
2424  struct stemdata *stem;
2425  struct linedata *line;
2426  struct stem_chunk *chunk;
2427  int i, j, stem_hv, line_hv, needs_hv=false;
2428 
2429  for ( i=0; i<gd->stemcnt; ++i ) if ( !gd->stems[i].toobig ) {
2430  stem = &gd->stems[i];
2431  stem_hv = IsUnitHV( &stem->unit,true );
2432  needs_hv = ( stem_hv || ( stem->chunk_cnt == 1 &&
2433  stem->chunks[0].stub && IsUnitHV( &stem->unit,false )));
2434 
2435  if ( stem->leftline != NULL ) {
2436  line = stem->leftline;
2437  line_hv = ( needs_hv && LineFitsHV( line ));
2438 
2439  if ( needs_hv && !line_hv )
2440  stem->leftline = NULL;
2441  else {
2442  for ( j=0; j<line->pcnt; j++ ) {
2443  pd = line->points[j];
2444  if ( pd->prevline == line && OnStem( stem,&pd->base,true ) &&
2445  IsStemAssignedToPoint( pd,stem,false ) == -1) {
2446  chunk = AddToStem( gd,stem,pd,NULL,false,false,false );
2447  chunk->lpotential = true;
2448  } if ( pd->nextline == line && OnStem( stem,&pd->base,true ) &&
2449  IsStemAssignedToPoint( pd,stem,true ) == -1 ) {
2450  chunk = AddToStem( gd,stem,pd,NULL,true,false,false );
2451  chunk->lpotential = true;
2452  }
2453  }
2454  }
2455  }
2456  if ( stem->rightline != NULL ) {
2457  line = stem->rightline;
2458  line_hv = ( needs_hv && LineFitsHV( line ));
2459 
2460  if ( needs_hv && !line_hv )
2461  stem->rightline = NULL;
2462  else {
2463  for ( j=0; j<line->pcnt; j++ ) {
2464  pd = line->points[j];
2465  if ( pd->prevline == line && OnStem( stem,&pd->base,false ) &&
2466  IsStemAssignedToPoint( pd,stem,false ) == -1 ) {
2467  chunk = AddToStem( gd,stem,NULL,pd,false,false,false );
2468  chunk->rpotential = true;
2469  } if ( pd->nextline == line && OnStem( stem,&pd->base,false ) &&
2470  IsStemAssignedToPoint( pd,stem,true ) == -1 ) {
2471  chunk = AddToStem( gd,stem,NULL,pd,false,true,false );
2472  chunk->rpotential = true;
2473  }
2474  }
2475  }
2476  }
2477  }
2478 }
2479 
2480 static struct stemdata *DiagonalCornerStem( struct glyphdata *gd,
2481  struct pointdata *pd,int require_existing ) {
2482  Spline *other = pd->bothedge;
2483  struct pointdata *pfrom = NULL, *pto = NULL, *pd2 = NULL;
2484  double width, length;
2485  struct stemdata *stem;
2486 
2487  pfrom = &gd->points[other->from->ptindex];
2488  pto = &gd->points[other->to->ptindex];
2489  if ( pd->symetrical_h && pto->symetrical_h && pd->both_e_t>.9 )
2490  pd2 = pto;
2491  else if ( pd->symetrical_h && pfrom->symetrical_h && pd->both_e_t<.1 )
2492  pd2 = pfrom;
2493  else if ( pd->symetrical_v && pto->symetrical_v && pd->both_e_t>.9 )
2494  pd2 = pto;
2495  else if ( pd->symetrical_v && pfrom->symetrical_v && pd->both_e_t<.1 )
2496  pd2 = pfrom;
2497  else if ( pd->symetrical_h && other->islinear && other->splines[1].c==0 ) {
2498  pd2 = pfrom;
2499  } else if ( pd->symetrical_v && other->islinear && other->splines[0].c==0 ) {
2500  pd2 = pfrom;
2501  } else
2502 return( NULL );
2503 
2504  if ( pd->symetrical_v )
2505  width = (pd->sp->me.x-pd2->sp->me.x);
2506  else
2507  width = (pd->sp->me.y-pd2->sp->me.y);
2508  length = (pd->sp->next->to->me.x-pd->sp->me.x)*(pd->sp->next->to->me.x-pd->sp->me.x) +
2509  (pd->sp->next->to->me.y-pd->sp->me.y)*(pd->sp->next->to->me.y-pd->sp->me.y);
2510  if ( width*width>length )
2511 return( NULL );
2512 
2513  stem = FindOrMakeHVStem(gd,pd,pd2,pd->symetrical_h,require_existing);
2514 return( stem );
2515 }
2516 
2517 static int chunk_cmp( const void *_p1, const void *_p2 ) {
2518  const struct stem_chunk *ch1 = _p1, *ch2 = _p2;
2519 
2520  struct stemdata *stem;
2521  double loff1=0,roff1=0,loff2=0,roff2=0;
2522 
2523  stem = ch1->parent;
2524  if ( stem==NULL )
2525 return( 0 );
2526 
2527  if ( ch1->l != NULL )
2528  loff1 = ( ch1->l->sp->me.x - stem->left.x ) * stem->unit.x +
2529  ( ch1->l->sp->me.y - stem->left.y ) * stem->unit.y;
2530  if ( ch1->r != NULL )
2531  roff1 = ( ch1->r->sp->me.x - stem->right.x ) * stem->unit.x +
2532  ( ch1->r->sp->me.y - stem->right.y ) * stem->unit.y;
2533  if ( ch2->l != NULL )
2534  loff2 = ( ch2->l->sp->me.x - stem->left.x ) * stem->unit.x +
2535  ( ch2->l->sp->me.y - stem->left.y ) * stem->unit.y;
2536  if ( ch2->r != NULL )
2537  roff2 = ( ch2->r->sp->me.x - stem->right.x ) * stem->unit.x +
2538  ( ch2->r->sp->me.y - stem->right.y ) * stem->unit.y;
2539 
2540  if ( loff1>loff2 )
2541 return( 1 );
2542  else if ( loff1<loff2 )
2543 return( -1 );
2544  else {
2545  if ( roff1>roff2 )
2546 return( 1 );
2547  else if ( roff1<roff2 )
2548 return( -1 );
2549  else
2550 return( 0 );
2551  }
2552 }
2553 
2554 static int stem_cmp( const void *_p1, const void *_p2 ) {
2555  struct stemdata * const *st1 = _p1, * const *st2 = _p2;
2556  double start1, end1, start2, end2;
2557 
2558  if ( fabs( (*st1)->unit.x ) > fabs( (*st1)->unit.y )) {
2559  start1 = (*st1)->right.y; end1 = (*st1)->left.y;
2560  start2 = (*st2)->right.y; end2 = (*st2)->left.y;
2561  } else {
2562  start1 = (*st1)->left.x; end1 = (*st1)->right.x;
2563  start2 = (*st2)->left.x; end2 = (*st2)->right.x;
2564  }
2565 
2566  if ( start1 > start2 )
2567 return( 1 );
2568  else if ( start1 < start2 )
2569 return( -1 );
2570  else {
2571  if ( end1 > end2 )
2572 return( 1 );
2573  else if ( end1 < end2 )
2574 return( -1 );
2575  else
2576 return( 0 );
2577  }
2578 }
2579 
2580 static void FixupT( struct pointdata *pd,int stemidx,int isnext, int eidx ) {
2581  /* When we calculated "next/prev_e_t" we deliberately did not use pd1->me */
2582  /* (because things get hard at intersections) so our t is only an approx-*/
2583  /* imation. We can do a lot better now */
2584  Spline *s;
2585  Spline myline;
2586  SplinePoint end1, end2;
2587  double width,t,sign, len, dot;
2588  BasePoint pts[9];
2589  extended lts[10], sts[10];
2590  BasePoint diff;
2591  struct stemdata *stem ;
2592 
2593  if ( pd == NULL || stemidx == -1 )
2594 return;
2595  stem = ( isnext ) ? pd->nextstems[stemidx] : pd->prevstems[stemidx];
2596  width = ( stem->right.x - stem->left.x )*stem->unit.y -
2597  ( stem->right.y-stem->left.y )*stem->unit.x;
2598  s = ( isnext ) ? pd->nextedges[eidx] : pd->prevedges[eidx];
2599  if ( s==NULL )
2600 return;
2601  diff.x = s->to->me.x-s->from->me.x;
2602  diff.y = s->to->me.y-s->from->me.y;
2603  if ( diff.x<.001 && diff.x>-.001 && diff.y<.001 && diff.y>-.001 )
2604 return; /* Zero length splines give us NaNs */
2605  len = sqrt( pow( diff.x,2 ) + pow( diff.y,2 ));
2606  dot = ( diff.x*stem->unit.x + diff.y*stem->unit.y )/len;
2607  if ( dot < .0004 && dot > -.0004 )
2608 return; /* It's orthogonal to our stem */
2609 
2610  if (( stem->unit.x==1 || stem->unit.x==-1 ) && s->knownlinear )
2611  t = (pd->sp->me.x-s->from->me.x)/(s->to->me.x-s->from->me.x);
2612  else if (( stem->unit.y==1 || stem->unit.y==-1 ) && s->knownlinear )
2613  t = (pd->sp->me.y-s->from->me.y)/(s->to->me.y-s->from->me.y);
2614  else {
2615  memset(&myline,0,sizeof(myline));
2616  memset(&end1,0,sizeof(end1));
2617  memset(&end2,0,sizeof(end2));
2618  sign = (( isnext && pd->next_is_l[stemidx] ) || ( !isnext && pd->prev_is_l[stemidx] )) ? 1 : -1;
2619  myline.knownlinear = myline.islinear = true;
2620  end1.me = pd->sp->me;
2621  end2.me.x = pd->sp->me.x+1.1*sign*width*stem->l_to_r.x;
2622  end2.me.y = pd->sp->me.y+1.1*sign*width*stem->l_to_r.y;
2623  end1.nextcp = end1.prevcp = end1.me;
2624  end2.nextcp = end2.prevcp = end2.me;
2625  end1.nonextcp = end1.noprevcp = end2.nonextcp = end2.noprevcp = true;
2626  end1.next = &myline; end2.prev = &myline;
2627  myline.from = &end1; myline.to = &end2;
2628  myline.splines[0].d = end1.me.x;
2629  myline.splines[0].c = end2.me.x-end1.me.x;
2630  myline.splines[1].d = end1.me.y;
2631  myline.splines[1].c = end2.me.y-end1.me.y;
2632  if ( SplinesIntersect(&myline,s,pts,lts,sts)<=0 )
2633 return;
2634  t = sts[0];
2635  }
2636  if ( isnan(t))
2637  IError( "NaN value in FixupT" );
2638  if ( isnext )
2639  pd->next_e_t[eidx] = t;
2640  else
2641  pd->prev_e_t[eidx] = t;
2642 }
2643 
2644 /* flags: 1 -- accept curved extrema, 2 -- accept angles, */
2645 /* 4 -- analyze segments (not just single points) */
2646 static int IsSplinePeak( struct glyphdata *gd,struct pointdata *pd,
2647  int outer,int is_x,int flags ) {
2648 
2649  double base, next, prev, nextctl, prevctl, unit_p, unit_n;
2650  Spline *s, *snext, *sprev;
2651  struct monotonic **space, *m;
2652  int wprev, wnext, i, desired;
2653  SplinePoint *sp = pd->sp;
2654 
2655  base = ((real *) &sp->me.x)[!is_x];
2656  nextctl = sp->nonextcp ? base : ((real *) &sp->nextcp.x)[!is_x];
2657  prevctl = sp->noprevcp ? base : ((real *) &sp->prevcp.x)[!is_x];
2658  next = prev = base;
2659  snext = sp->next; sprev = sp->prev;
2660 
2661  if ( snext->to == NULL || sprev->from == NULL )
2662 return( false );
2663  if (!( flags & 2) && ( sp->nonextcp || sp->noprevcp ))
2664 return( false );
2665  else if (!( flags & 1 ) && ( pd->colinear ))
2666 return( false );
2667 
2668  if ( flags & 4 ) {
2669  while ( snext->to->next != NULL && snext->to != sp && next == base ) {
2670  next = ((real *) &snext->to->me.x)[!is_x];
2671  snext = snext->to->next;
2672  }
2673 
2674  while ( sprev->from->prev != NULL && sprev->from != sp && prev == base ) {
2675  prev = ((real *) &sprev->from->me.x)[!is_x];
2676  sprev = sprev->from->prev;
2677  }
2678  } else {
2679  next = ((real *) &snext->to->me.x)[!is_x];
2680  prev = ((real *) &sprev->from->me.x)[!is_x];
2681  }
2682 
2683  if ( prev<base && next<base && nextctl<=base && prevctl<=base )
2684  desired = ( outer ) ? -1 : 1;
2685  else if ( prev>base && next>base && prevctl>=base && nextctl>=base )
2686  desired = ( outer ) ? 1 : -1;
2687  else
2688 return( false );
2689 
2690  MonotonicFindAt( gd->ms,is_x,((real *) &sp->me.x)[is_x],space = gd->space );
2691  wprev = wnext = 0;
2692  for ( i=0; space[i]!=NULL; ++i ) {
2693  m = space[i];
2694  s = m->s;
2695 
2696  if ( s->from == sp )
2697  wnext = ((&m->xup)[is_x] ? 1 : -1 );
2698  else if ( s->to == sp )
2699  wprev = ((&m->xup)[is_x] ? 1 : -1 );
2700  }
2701 
2702  if ( wnext != 0 && wprev != 0 && wnext != wprev ) {
2703  unit_p = (&pd->prevunit.x)[!is_x];
2704  unit_n = (&pd->nextunit.x)[!is_x];
2705  if ( unit_p < unit_n && (
2706  ( outer && wprev == 1 ) || ( !outer && wprev == -1 )))
2707 return( desired );
2708  else if ( unit_p > unit_n && (
2709  ( outer && wnext == 1 ) || ( !outer && wnext == -1 )))
2710 return( desired );
2711  } else {
2712  if ( wnext == desired || wprev == desired )
2713 return( desired );
2714  }
2715 
2716 return( false );
2717 }
2718 
2720  struct stemdata *stem,struct stem_chunk **chunk,SplinePoint *sp,int *next ) {
2721 
2722  struct pointdata *pd, *ret=NULL;
2723  struct stem_chunk *testchunk;
2724  double test, proj=1e4;
2725  int i, is_l;
2726 
2727  for ( i=0; i<stem->chunk_cnt; ++i ) {
2728  testchunk = &stem->chunks[i];
2729  pd = NULL;
2730  if ( testchunk->l != NULL && testchunk->l->sp==sp ) {
2731  pd = testchunk->r;
2732  is_l = false;
2733  } else if ( testchunk->r != NULL && testchunk->r->sp==sp ) {
2734  pd = testchunk->l;
2735  is_l = true;
2736  }
2737 
2738  if ( pd != NULL ) {
2739  test = ( pd->sp->me.x-sp->me.x ) * stem->unit.x +
2740  ( pd->sp->me.y-sp->me.y ) * stem->unit.y;
2741  if ( test < 0 ) test = -test;
2742  if ( test < proj ) {
2743  ret = pd;
2744  proj = test;
2745  *chunk = testchunk;
2746  }
2747  }
2748  }
2749  if ( ret != NULL )
2750  *next = ( is_l ) ? (*chunk)->lnext : (*chunk)->rnext;
2751 return( ret );
2752 }
2753 
2754 static int ValueChunk( struct glyphdata *gd,struct vchunk *vchunks,
2755  int chcnt,int idx,int l_base ) {
2756 
2757  int peak1=0, peak2=0, val=0;
2758  int i, is_x, base_next, opp_next;
2759  struct pointdata *base, *opp, *frompd, *topd;
2760  struct stem_chunk *chunk = vchunks[idx].chunk, *tchunk;
2761  struct stemdata *stem = chunk->parent;
2762  double norm, dist;
2763  Spline *sbase, *sopp, *other;
2764 
2765  /* If a stem was already present before generating glyph data, */
2766  /* then it should always be preferred in case of a conflict */
2767  if ( stem->positioned || chunk->stemcheat ) val++;
2768 
2769  if ( l_base ) {
2770  base = chunk->l; opp = chunk->r;
2771  base_next = chunk->lnext; opp_next = chunk->rnext;
2772  } else {
2773  base = chunk->r; opp = chunk->l;
2774  base_next = chunk->rnext; opp_next = chunk->lnext;
2775  }
2776  sbase = ( base_next ) ? base->sp->next : base->sp->prev;
2777  sopp = ( opp_next ) ? opp->sp->next : opp->sp->prev;
2778  other = ( opp_next ) ? opp->nextedges[0] : opp->prevedges[0];
2779 
2780  /* If there are 2 conflicting chunks belonging to different stems but */
2781  /* based on the same point, then we have to decide which stem is "better" */
2782  /* for that point. We compare stems (or rather chunks) by assigning a */
2783  /* value to each of them and then prefer the stem whose value is positive. */
2784  /* A chunk gets a +1 value bonus in the following cases: */
2785  /* - The stem is vertical/horizontal and splines are curved in the same */
2786  /* direction at both sides of the chunk; */
2787  /* - A stem has both its width and the distance between the opposite points */
2788  /* smaller than another stem; */
2789  /* - The common side of two stems is a straight line formed by two points */
2790  /* and the opposite point can be projected to line segment between those */
2791  /* two points. */
2792  if ( IsUnitHV( &stem->unit,true ) && !sbase->knownlinear ) {
2793  is_x = (int) rint( stem->unit.y );
2794  peak1 = ( is_x ) ? base->x_extr : base->y_extr;
2795  peak2 = ( is_x ) ? opp->x_extr : opp->y_extr;
2796 
2797  dist = ( base->base.x - opp->base.x )*stem->unit.x +
2798  ( base->base.y - opp->base.y )*stem->unit.y;
2799 
2800  /* Are there any stems attached to the same base point which */
2801  /* are narrower than the distance between two points forming the */
2802  /* given chunk? */
2803  for ( i=0; i<chcnt; i++ ) {
2804  tchunk = vchunks[i].chunk;
2805  if ( tchunk == NULL || tchunk == chunk || chunk->l == NULL || chunk->r == NULL )
2806  continue;
2807  norm = tchunk->parent->width;
2808  if ( norm < fabs( dist ))
2809  break;
2810  }
2811 
2812  /* If both points are curved in the same direction, then check also */
2813  /* the "line of sight" between those points (if there are interventing */
2814  /* splines, then it is not a real feature bend)*/
2815  if ( i == chcnt && peak1 + peak2 == 3 && ConnectsAcross( gd,base->sp,opp_next,sopp,0 ))
2816  val++;
2817  }
2818 
2819  frompd = &gd->points[sbase->from->ptindex];
2820  topd = &gd->points[sbase->to->ptindex];
2821 
2822  if (IsStemAssignedToPoint( frompd,stem,true ) != -1 &&
2823  IsStemAssignedToPoint( topd,stem,false ) != -1 )
2824  if ( other == sbase ) val++;
2825 
2826  dist = vchunks[idx].dist;
2827  for ( i=0; i<chcnt; i++ ) {
2828  tchunk = vchunks[i].chunk;
2829  if ( tchunk == NULL || tchunk == chunk ||
2830  ( vchunks[idx].parallel && !vchunks[i].parallel ))
2831  continue;
2832  if ( vchunks[i].dist <= dist || tchunk->parent->width <= stem->width )
2833  break;
2834  }
2835  if ( i==chcnt ) val++;
2836 
2837  /* If just one of the checked chunks has both its sides parallel */
2838  /* to the stem direction, then we consider it is always worth to be output. */
2839  /* This check was introduced to avoid situations where a stem marking */
2840  /* a feature termination can be preferred to another stem which controls */
2841  /* the main part of the same feature */
2842  if ( vchunks[idx].parallel ) {
2843  for ( i=0; i<chcnt; i++ ) {
2844  if ( vchunks[i].chunk == NULL || vchunks[i].chunk == chunk )
2845  continue;
2846  if ( vchunks[i].parallel )
2847  break;
2848  }
2849  if ( i == chcnt ) val++;
2850  }
2851 
2852 return( val );
2853 }
2854 
2855 static void CheckPotential( struct glyphdata *gd,struct pointdata *pd,int is_next ) {
2856  int i, j, is_l, next1, stemcnt, val;
2857  int val_cnt=0;
2858  BasePoint *lunit, *runit;
2859  struct stemdata **stems;
2860  struct vchunk *vchunks;
2861  struct stem_chunk *cur;
2862 
2863  stemcnt = ( is_next ) ? pd->nextcnt : pd->prevcnt;
2864  stems = ( is_next ) ? pd->nextstems : pd->prevstems;
2865  vchunks = calloc( stemcnt,sizeof( VChunk ));
2866 
2867  for ( i=0; i<stemcnt; i++ ) {
2868  is_l = ( is_next ) ? pd->next_is_l[i] : pd->prev_is_l[i];
2869  FindClosestOpposite( stems[i],&vchunks[i].chunk,pd->sp,&next1 );
2870  if ( vchunks[i].chunk == NULL )
2871  continue;
2872  cur = vchunks[i].chunk;
2873  if ( vchunks[i].value > 0 ) val_cnt++;
2874  vchunks[i].dist = pow( cur->l->base.x - cur->r->base.x,2 ) +
2875  pow( cur->l->base.y - cur->r->base.y,2 );
2876  lunit = ( cur->lnext ) ? &cur->l->nextunit : &cur->l->prevunit;
2877  runit = ( cur->rnext ) ? &cur->r->nextunit : &cur->r->prevunit;
2878  vchunks[i].parallel = UnitsParallel( lunit,&stems[i]->unit,2 ) &&
2879  UnitsParallel( runit,&stems[i]->unit,2 );
2880  }
2881 
2882  for ( i=0; i<stemcnt; i++ ) if ( vchunks[i].chunk != NULL ) {
2883  vchunks[i].value = ValueChunk( gd,vchunks,stemcnt,i,is_l );
2884  if ( vchunks[i].value ) val_cnt++;
2885  }
2886 
2887  /* If we was unable to figure out any reasons for which at least */
2888  /* one of the checked chunks should really be output, then keep */
2889  /* all the 'potential' flags as they are and do nothing */
2890  if ( val_cnt > 0 ) {
2891  for ( i=0; i<stemcnt; i++ ) if ( vchunks[i].chunk != NULL ) {
2892  is_l = ( is_next ) ? pd->next_is_l[i] : pd->prev_is_l[i];
2893  val = vchunks[i].value;
2894  for ( j=0; j<stems[i]->chunk_cnt; j++ ) {
2895  cur = &stems[i]->chunks[j];
2896  if ( is_l && cur->l == pd ) {
2897  if ( val > 0 ) cur->lpotential = false;
2898  else cur->lpotential = true;
2899  } else if ( !is_l && cur->r == pd ) {
2900  if ( val > 0 ) cur->rpotential = false;
2901  else cur->rpotential = true;
2902  }
2903  }
2904  }
2905  }
2906  free( vchunks );
2907 }
2908 
2909 static int StemIsActiveAt( struct glyphdata *gd,struct stemdata *stem,double stempos ) {
2910  BasePoint pos,cpos,mpos;
2911  int which;
2912  double test;
2913  double lmin, lmax, rmin, rmax, loff, roff, minoff, maxoff;
2914  struct monotonic **space, *m;
2915  int winding, nw, closest, i, j;
2916 
2917  pos.x = stem->left.x + stempos*stem->unit.x;
2918  pos.y = stem->left.y + stempos*stem->unit.y;
2919 
2920  if ( IsUnitHV( &stem->unit,true )) {
2921  which = stem->unit.x==0;
2922  MonotonicFindAt(gd->ms,which,((real *) &pos.x)[which],space = gd->space);
2923  test = ((real *) &pos.x)[!which];
2924 
2925  lmin = ( stem->lmax - 2*dist_error_hv < -dist_error_hv ) ?
2926  stem->lmax - 2*dist_error_hv : -dist_error_hv;
2927  lmax = ( stem->lmin + 2*dist_error_hv > dist_error_hv ) ?
2928  stem->lmin + 2*dist_error_hv : dist_error_hv;
2929  rmin = ( stem->rmax - 2*dist_error_hv < -dist_error_hv ) ?
2930  stem->rmax - 2*dist_error_hv : -dist_error_hv;
2931  rmax = ( stem->rmin + 2*dist_error_hv > dist_error_hv ) ?
2932  stem->rmin + 2*dist_error_hv : dist_error_hv;
2933  minoff = test + ( lmin * stem->unit.y - lmax * stem->unit.x );
2934  maxoff = test + ( lmax * stem->unit.y - lmin * stem->unit.x );
2935 
2936  winding = 0; closest = -1;
2937  for ( i=0; space[i]!=NULL; ++i ) {
2938  m = space[i];
2939  nw = ((&m->xup)[which] ? 1 : -1 );
2940  if ( m->other >= minoff && m->other <= maxoff && nw == 1 ) {
2941  closest = i;
2942  break;
2943  } else if ( m->other > maxoff )
2944  break;
2945  winding += nw;
2946  }
2947  if ( closest < 0 )
2948 return( false );
2949 
2950  cpos.x = ( which ) ? m->other : pos.x ;
2951  cpos.y = ( which ) ? pos.y : m->other ;
2952  loff = ( cpos.x - stem->left.x ) * stem->unit.y -
2953  ( cpos.y - stem->left.y ) * stem->unit.x;
2954  if ( loff > lmax || loff < lmin )
2955 return( false );
2956 
2957  j = MatchWinding(space,i,nw,winding,which,0);
2958  if ( j==-1 )
2959 return( false );
2960  m = space[j];
2961 
2962  mpos.x = ( which ) ? m->other : pos.x ;
2963  mpos.y = ( which ) ? pos.y : m->other ;
2964  roff = ( mpos.x - stem->right.x ) * stem->unit.y -
2965  ( mpos.y - stem->right.y ) * stem->unit.x;
2966  if ( roff >= rmin && roff <= rmax )
2967 return( true );
2968 return( false );
2969  } else {
2970 return( StillStem( gd,dist_error_diag,&pos,stem ));
2971  }
2972 }
2973 
2974 /* This function is used to check the distance between a hint's edge */
2975 /* and a spline and determine the extet where this hint can be */
2976 /* considered "active". */
2977 static int WalkSpline( struct glyphdata *gd, struct pointdata *pd,int gonext,
2978  struct stemdata *stem,int is_l,int force_ac,BasePoint *res ) {
2979 
2980  int i, curved;
2981  double off, dist, min, max;
2982  double incr, err;
2983  double t, ratio, width;
2984  Spline *s;
2985  BasePoint *base, *nunit, pos, good;
2986  SplinePoint *sp, *nsp;
2987  struct pointdata *npd;
2988 
2989  err = ( IsUnitHV( &stem->unit,true )) ? dist_error_hv : dist_error_diag;
2990  width = stem->width;
2991  ratio = gd->emsize/( 6 * width );
2992  if ( err > width/2) err = width/2;
2993 
2994  sp = pd->sp;
2995  base = ( is_l ) ? &stem->left : &stem->right;
2996  min = ( is_l ) ? stem->lmax - 2*err : stem->rmax - 2*err;
2997  max = ( is_l ) ? stem->lmin + 2*err : stem->rmin + 2*err;
2998 
2999  s = ( gonext ) ? sp->next : sp->prev;
3000  nsp = ( gonext ) ? s->to : s->from;
3001  npd = &gd->points[nsp->ptindex];
3002  nunit = ( gonext ) ? &npd->prevunit : &npd->nextunit;
3003  good = sp->me;
3004 
3005  off = ( nsp->me.x - base->x )*stem->l_to_r.x +
3006  ( nsp->me.y - base->y )*stem->l_to_r.y;
3007  /* Some splines have tiny control points and are almost flat */
3008  /* think of them as lines then rather than treating them as curves */
3009  /* figure out how long they remain within a few orthoganal units of */
3010  /* the point */
3011  /* We used to check the distance between a control point and a spline */
3012  /* and consider the segment "flat" if this distance is smaller than */
3013  /* the normal allowed "error" value. However this method doesn't produce */
3014  /* consistent results if the spline is not long enough (as usual for */
3015  /* fonts with quadratic splines). So now we consider a spline "flat" */
3016  /* only if it never deviates too far from the hint's edge and both */
3017  /* its terminal points are snappable to the same hint */
3018  curved = ( IsStemAssignedToPoint( npd,stem,gonext ) == -1 &&
3019  ( off < min || off > max || !UnitsParallel( &stem->unit,nunit,true )));
3020 
3021  /* If a spline does deviate from the edge too far to consider it flat, */
3022  /* then we calculate the extent where the spline and the edge are still */
3023  /* close enough to consider the hint active at this zone. If the hint is */
3024  /* still active at the end of the spline, we can check some subsequent splines */
3025  /* too. This method produces better effect than any "magic" manipulations */
3026  /* with control point coordinates, because it takes into account just the */
3027  /* spline configuration rather than point positions */
3028  if ( curved ) {
3029  max = err = dist_error_curve;
3030  min = -dist_error_curve;
3031  /* The following statement forces our code to detect an active zone */
3032  /* even if all checks actually fail. This makes sense for stems */
3033  /* marking arks and bends */
3034  if ( force_ac )
3035  good = ( gonext ) ? sp->nextcp : sp->prevcp;
3036  /* If a spline is closer to the opposite stem edge than to the current edge, then we */
3037  /* can no longer consider the stem active at this point */
3038  if ( err > width/2 ) err = width/2;
3039 
3040  t = ( gonext ) ? 0.9999 : 0.0001;
3041  for ( ; ; s = ( gonext ) ? s->to->next : s->from->prev ) {
3042  pos.x = ((s->splines[0].a*t+s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
3043  pos.y = ((s->splines[1].a*t+s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
3044  off = ( pos.x - base->x )*stem->l_to_r.x +
3045  ( pos.y - base->y )*stem->l_to_r.y;
3046  dist = ( pos.x - sp->me.x )*stem->unit.x +
3047  ( pos.y - sp->me.y )*stem->unit.y;
3048  nsp = ( gonext ) ? s->to : s->from;
3049  npd = &gd->points[nsp->ptindex];
3050  if (fabs( off ) < max && fabs( dist ) <= ( width + width * ratio ) &&
3051  nsp != sp && npd->colinear && !npd->x_extr && !npd->y_extr &&
3052  StillStem( gd,err,&pos,stem ))
3053  good = pos;
3054  else
3055  break;
3056  }
3057  }
3058  t = .5;
3059  incr = ( gonext ) ? .25 : -.25;
3060  for ( i=0; i<6; ++i ) {
3061  pos.x = ((s->splines[0].a*t+s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
3062  pos.y = ((s->splines[1].a*t+s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
3063  off = ( pos.x - base->x )*stem->l_to_r.x +
3064  ( pos.y - base->y )*stem->l_to_r.y;
3065  dist = ( pos.x - sp->me.x )*stem->unit.x +
3066  ( pos.y - sp->me.y )*stem->unit.y;
3067  /* Don't check StillStem for non-curved segments, as they are subject */
3068  /* to further projection-related tests anyway */
3069  if ( off > min && off < max && ( !curved ||
3070  ( fabs( dist ) < ( width + width * ratio ) &&
3071  StillStem( gd,err,&pos,stem )))) {
3072 
3073  good = pos;
3074  t += incr;
3075  } else
3076  t -= incr;
3077  incr/=2;
3078  }
3079  *res = good;
3080 return( curved );
3081 }
3082 
3084  BasePoint *newpos,struct stemdata *stem,int is_l ) {
3085 
3086  double poff, err, min, max;
3087  BasePoint *base;
3088 
3089  base = ( is_l ) ? &stem->left : &stem->right;
3090  err = ( IsUnitHV( &stem->unit,true )) ? dist_error_hv : dist_error_diag;
3091  min = ( is_l ) ? stem->lmax - 2*err : stem->rmax - 2*err;
3092  max = ( is_l ) ? stem->lmin + 2*err : stem->rmin + 2*err;
3093 
3094  /* Possible if the stem unit has been attached to a line. It is */
3095  /* hard to prevent this */
3096  if ( min > max ) {
3097  min = stem->lmin; max = stem->lmax;
3098  }
3099 
3100  poff = ( pos->x - base->x )*stem->l_to_r.x +
3101  ( pos->y - base->y )*stem->l_to_r.y;
3102  if ( poff > min && poff < max ) {
3103  *newpos = *pos;
3104 return( false );
3105  } else if ( poff <= min )
3106  err = fabs( min );
3107  else if ( poff >= max )
3108  err = fabs( max );
3109 
3110  newpos->x = sp->me.x + err*( pos->x - sp->me.x )/fabs( poff );
3111  newpos->y = sp->me.y + err*( pos->y - sp->me.y )/fabs( poff );
3112 return( true );
3113 }
3114 
3115 static int AddLineSegment( struct stemdata *stem,struct segment *space,int cnt,
3116  int is_l,struct pointdata *pd,int base_next,struct glyphdata *gd ) {
3117 
3118  double s, e, t, dot;
3119  BasePoint stemp, etemp;
3120  BasePoint *start, *end, *par_unit;
3121  int same_dir, corner = 0, par;
3122  int scurved = false, ecurved = false, c, hv;
3123  SplinePoint *sp, *psp, *nsp;
3124  double b;
3125  uint8 extr;
3126 
3127  if ( pd==NULL || (sp = pd->sp)==NULL || sp->ticked ||
3128  sp->next==NULL || sp->prev==NULL )
3129 return( cnt );
3130  end = &sp->me;
3131  start = &sp->me;
3132  par_unit = ( base_next ) ? &pd->nextunit : &pd->prevunit;
3133  /* Do the spline and the stem unit point in the same direction ? */
3134  dot = ( stem->unit.x * par_unit->x ) +
3135  ( stem->unit.y * par_unit->y );
3136  same_dir = (( dot > 0 && base_next ) || ( dot < 0 && !base_next ));
3137  if ( stem->unit.x == 1 ) corner = pd->y_corner;
3138  else if ( stem->unit.y == 1 ) corner = pd->x_corner;
3139 
3140  dot = ( stem->unit.x * pd->nextunit.x ) +
3141  ( stem->unit.y * pd->nextunit.y );
3142  /* We used to apply normal checks only if the point's unit vector pointing */
3143  /* in the direction we are going to check is nearly parallel to the stem unit. */
3144  /* But this is not the best method, because a spline, "parallel" to our */
3145  /* stem, may actually have filled space at a wrong side. On the other hand, */
3146  /* sometimes it makes sense to calculate active space even for splines */
3147  /* connected to our base point under an angle which is too large to consider */
3148  /* the direction "parallel". So now we check the units' direction first */
3149  /* and then (just for straight splines) also their parallelity. */
3150  if (( dot > 0 && same_dir ) || ( dot < 0 && !same_dir )) {
3151  /* If the segment sp-start doesn't have exactly the right slope, then */
3152  /* we can only use that bit of it which is less than a standard error */
3153  par = UnitsParallel( &stem->unit,&pd->nextunit,0 );
3154  if ( !sp->next->knownlinear ) {
3155  ecurved = WalkSpline( gd,pd,true,stem,is_l,par,&etemp );
3156  /* Can merge, but treat as curved relatively to projections */
3157  if ( !ecurved ) ecurved = 2;
3158  end = &etemp;
3159  } else if ( par || corner ) {
3160  nsp = sp->next->to;
3161  ecurved = AdjustForImperfectSlopeMatch( sp,&nsp->me,&etemp,stem,is_l );
3162  end = &etemp;
3163  }
3164  }
3165  dot = ( stem->unit.x * pd->prevunit.x ) +
3166  ( stem->unit.y * pd->prevunit.y );
3167  if (( dot < 0 && same_dir ) || ( dot > 0 && !same_dir )) {
3168  par = UnitsParallel( &stem->unit,&pd->prevunit,0 );
3169  if ( !sp->prev->knownlinear ) {
3170  scurved = WalkSpline( gd,pd,false,stem,is_l,par,&stemp );
3171  if ( !scurved ) scurved = 2;
3172  start = &stemp;
3173  } else if ( par || corner ) {
3174  psp = sp->prev->from;
3175  scurved = AdjustForImperfectSlopeMatch( sp,&psp->me,&stemp,stem,is_l );
3176  start = &stemp;
3177  }
3178  }
3179  sp->ticked = true;
3180 
3181  s = (start->x-stem->left.x)*stem->unit.x +
3182  (start->y-stem->left.y)*stem->unit.y;
3183  e = ( end->x-stem->left.x)*stem->unit.x +
3184  ( end->y-stem->left.y)*stem->unit.y;
3185  b = (sp->me.x-stem->left.x)*stem->unit.x +
3186  (sp->me.y-stem->left.y)*stem->unit.y;
3187 
3188  if ( s == e )
3189 return( cnt );
3190  if ( s > e ) {
3191  t = s; c = scurved;
3192  s = e; e = t;
3193  scurved = ecurved; ecurved = c;
3194  }
3195  space[cnt].start = s;
3196  space[cnt].end = e;
3197  space[cnt].sbase = space[cnt].ebase = b;
3198  space[cnt].scurved = scurved;
3199  space[cnt].ecurved = ecurved;
3200 
3201  hv = IsUnitHV( &stem->unit,true );
3202  if ( hv ) {
3203  /* For vertical/horizontal stems we assign a special meaning to */
3204  /* the 'curved' field. It will be non-zero if the key point of */
3205  /* this segment is positioned on a prominent curve: */
3206  /* 1 if the inner side of that curve is inside of the contour */
3207  /* and 2 otherwise. */
3208  /* Later, if we get a pair of "inner" and "outer" curves, then */
3209  /* we are probably dealing with a feature's bend which should be */
3210  /* necessarily marked with a hint. Checks we apply for this type */
3211  /* of curved segments should be less strict than in other cases. */
3212  extr = ( hv == 1 ) ? pd->y_extr : pd->x_extr;
3213  space[cnt].curved = extr;
3214  } else {
3215  /* For diagonal stems we consider a segment "curved" if both its */
3216  /* start and end are curved. Curved segments usually cannot be */
3217  /* merged (unless scurved or ecurved is equal to 2) and are not */
3218  /* checked for "projections". */
3219  space[cnt].curved = scurved && ecurved;
3220  }
3221 return( cnt+1 );
3222 }
3223 
3224 static int InActive(double projection,struct segment *segments, int cnt) {
3225  int i;
3226 
3227  for ( i=0; i<cnt; ++i ) {
3228  if ( projection>=segments[i].start && projection<=segments[i].end )
3229 return( true );
3230  }
3231 return( false );
3232 }
3233 
3234 static int MergeSegments(struct segment *space, int cnt) {
3235  int i,j;
3236  double middle;
3237 
3238  for ( i=j=0; i<cnt; ++i, ++j ) {
3239  if ( i!=j )
3240  space[j] = space[i];
3241  while ( i+1<cnt && space[i+1].start<space[j].end ) {
3242  if ( space[i+1].end >= space[j].end ) {
3243 
3244  /* If there are 2 overlapping segments and neither the */
3245  /* end of the first segment nor the start of the second */
3246  /* one are curved we can merge them. Otherwise we have */
3247  /* to preserve them both, but modify their start/end properties */
3248  /* so that the overlap is removed */
3249  if ( space[j].ecurved != 1 && space[i+1].scurved != 1 ) {
3250  space[j].end = space[i+1].end;
3251  space[j].ebase = space[i+1].ebase;
3252  space[j].ecurved = space[i+1].ecurved;
3253  space[j].curved = false;
3254  } else if ( space[j].ecurved != 1 && space[i+1].scurved == 1 ) {
3255  space[i+1].start = space[j].end;
3256  --i;
3257  } else if ( space[j].ecurved == 1 && space[i+1].scurved != 1 ) {
3258  space[j].end = space[i+1].start;
3259  --i;
3260  } else {
3261  middle = (space[j].end + space[i+1].start)/2;
3262  space[j].end = space[i+1].start = middle;
3263  --i;
3264  }
3265  }
3266  ++i;
3267  }
3268  }
3269 return( j );
3270 }
3271 
3272 static int MergeSegmentsFinal( struct segment *space, int cnt ) {
3273  int i,j;
3274 
3275  for ( i=j=0; i<cnt; ++i, ++j ) {
3276  if ( i!=j )
3277  space[j] = space[i];
3278  while ( i+1<cnt && space[i+1].start<=space[j].end ) {
3279  if ( space[i+1].end>space[j].end ) {
3280  space[j].end = space[i+1].end;
3281  space[j].ebase = space[i+1].ebase;
3282  space[j].ecurved = space[i+1].ecurved;
3283  space[j].curved = false;
3284  }
3285  ++i;
3286  }
3287  }
3288 return( j );
3289 }
3290 
3291 static void FigureStemActive( struct glyphdata *gd, struct stemdata *stem ) {
3292  int i, j, pcnt=0;
3293  struct pointdata *pd, **pspace = gd->pspace;
3294  struct stem_chunk *chunk;
3295  struct segment *lspace = gd->lspace, *rspace = gd->rspace;
3296  struct segment *bothspace = gd->bothspace, *activespace = gd->activespace;
3297  int lcnt, rcnt, bcnt, bpos, acnt, cove, startset, endset;
3298  double middle, width, len, clen, gap, lseg, rseg;
3299  double err, lmin, rmax, loff, roff, last, s, e, sbase, ebase;
3300  double proj, proj2, proj3, orig_proj, ptemp;
3301 
3302  width = stem->width;
3303 
3304  for ( i=0; i<gd->pcnt; ++i ) if ( gd->points[i].sp!=NULL )
3305  gd->points[i].sp->ticked = false;
3306 
3307  lcnt = rcnt = 0;
3308  for ( i=0; i<stem->chunk_cnt; ++i ) {
3309  chunk = &stem->chunks[i];
3310  if ( chunk->stemcheat )
3311  continue;
3312  lcnt = AddLineSegment( stem,lspace,lcnt,true ,chunk->l,chunk->lnext,gd );
3313  rcnt = AddLineSegment( stem,rspace,rcnt,false,chunk->r,chunk->rnext,gd );
3314  }
3315  bcnt = 0;
3316  if ( lcnt!=0 && rcnt!=0 ) {
3317  /* For curved segments we can extend left and right active segments */
3318  /* a bit to ensure that they do overlap and thus can be marked with an */
3319  /* active zone */
3320  if ( rcnt == lcnt && stem->chunk_cnt == lcnt ) {
3321  for ( i=0; i<lcnt; i++ ) {
3322  /* If it's a feature bend, then our tests should be more liberal */
3323  cove = (( rspace[i].curved + lspace[i].curved ) == 3 );
3324  gap = 0;
3325  if ( lspace[i].start>rspace[i].end && lspace[i].scurved && rspace[i].ecurved )
3326  gap = lspace[i].start-rspace[i].end;
3327  else if ( rspace[i].start>lspace[i].end && rspace[i].scurved && lspace[i].ecurved )
3328  gap = rspace[i].start-lspace[i].end;
3329  else if ( !cove )
3330  continue;
3331 
3332  lseg = lspace[i].end - lspace[i].start;
3333  rseg = rspace[i].end - rspace[i].start;
3334  if (( cove && gap < (lseg > rseg ? lseg : rseg )) ||
3335  ( gap < ( lseg + rseg )/2 && !stem->chunks[i].stub )) {
3336  if ( lspace[i].ebase<rspace[i].start )
3337  rspace[i].start = lspace[i].ebase;
3338  else if ( lspace[i].sbase>rspace[i].end )
3339  rspace[i].end = lspace[i].sbase;
3340  if ( rspace[i].ebase<lspace[i].start )
3341  lspace[i].start = rspace[i].ebase;
3342  else if ( rspace[i].sbase>lspace[i].end )
3343  lspace[i].end = rspace[i].sbase;
3344  }
3345  }
3346  }
3347  qsort(lspace,lcnt,sizeof(struct segment),segment_cmp);
3348  qsort(rspace,rcnt,sizeof(struct segment),segment_cmp);
3349  lcnt = MergeSegments( lspace,lcnt );
3350  rcnt = MergeSegments( rspace,rcnt );
3351  for ( i=j=bcnt=0; i<lcnt && j<rcnt; ++i ) {
3352  while ( j<rcnt && rspace[j].end<=lspace[i].start )
3353  ++j;
3354  while ( j<rcnt && rspace[j].start<=lspace[i].end ) {
3355  cove = (( rspace[j].curved + lspace[i].curved ) == 3 );
3356 
3357  s = ( rspace[j].start > lspace[i].start ) ?
3358  rspace[j].start : lspace[i].start;
3359  e = ( rspace[j].end < lspace[i].end ) ?
3360  rspace[j].end : lspace[i].end;
3361  sbase = ( rspace[j].start > lspace[i].start ) ?
3362  lspace[i].sbase : rspace[j].sbase;
3363  ebase = ( rspace[j].end < lspace[i].end ) ?
3364  lspace[i].ebase : rspace[j].ebase;
3365 
3366  middle = ( lspace[i].start + rspace[j].start )/2;
3367  bothspace[bcnt].start = ( cove && middle < s ) ? middle : s;
3368  if ( rspace[j].start > lspace[i].start )
3369  bothspace[bcnt].scurved = ( rspace[j].scurved || sbase < s ) ?
3370  rspace[j].scurved : lspace[i].scurved;
3371  else
3372  bothspace[bcnt].scurved = ( lspace[i].scurved || sbase < s ) ?
3373  lspace[i].scurved : rspace[j].scurved;
3374 
3375  middle = ( lspace[i].end + rspace[j].end )/2;
3376  bothspace[bcnt].end = ( cove && middle > e ) ? middle : e;
3377  if ( rspace[j].end < lspace[i].end )
3378  bothspace[bcnt].ecurved = ( rspace[j].ecurved || ebase > e ) ?
3379  rspace[j].ecurved : lspace[i].ecurved;
3380  else
3381  bothspace[bcnt].ecurved = ( lspace[i].ecurved || ebase > e ) ?
3382  lspace[i].ecurved : rspace[j].ecurved;
3383 
3384  sbase = ( rspace[j].sbase > lspace[i].sbase ) ?
3385  rspace[j].sbase : lspace[i].sbase;
3386  ebase = ( rspace[j].ebase < lspace[i].ebase ) ?
3387  rspace[j].ebase : lspace[i].ebase;
3388  if ( sbase > bothspace[bcnt].end )
3389  sbase = ebase = bothspace[bcnt].end;
3390  else if ( ebase < bothspace[bcnt].start )
3391  sbase = ebase = bothspace[bcnt].start;
3392  else if ( ebase < sbase )
3393  ebase = sbase = ( ebase + sbase )/2;
3394  bothspace[bcnt].sbase = sbase;
3395  bothspace[bcnt].ebase = ebase;
3396 
3397  bothspace[bcnt++].curved = rspace[j].curved || lspace[i].curved;
3398 
3399  if ( rspace[j].end>lspace[i].end )
3400  break;
3401  ++j;
3402  }
3403  }
3404  }
3405 #if GLYPH_DATA_DEBUG
3406  fprintf( stderr, "Active zones for stem l=%.2f,%.2f r=%.2f,%.2f dir=%.2f,%.2f:\n",
3407  stem->left.x,stem->left.y,stem->right.x,stem->right.y,stem->unit.x,stem->unit.y );
3408  for ( i=0; i<lcnt; i++ ) {
3409  fprintf( stderr, "\tleft space curved=%d\n",lspace[i].curved );
3410  fprintf( stderr, "\t\tstart=%.2f,base=%.2f,curved=%d\n",
3412  fprintf( stderr, "\t\tend=%.2f,base=%.2f,curved=%d\n",
3414  }
3415  for ( i=0; i<rcnt; i++ ) {
3416  fprintf( stderr, "\tright space curved=%d\n",rspace[i].curved );
3417  fprintf( stderr, "\t\tstart=%.2f,base=%.2f,curved=%d\n",
3418  rspace[i].start,rspace[i].sbase,rspace[i].scurved );
3419  fprintf( stderr, "\t\tend=%.2f,base=%.2f,curved=%d\n",
3420  rspace[i].end,rspace[i].ebase,rspace[i].ecurved );
3421  }
3422  for ( i=0; i<bcnt; i++ ) {
3423  fprintf( stderr, "\tboth space\n" );
3424  fprintf( stderr, "\t\tstart=%.2f,base=%.2f,curved=%d\n",
3425  bothspace[i].start,bothspace[i].sbase,bothspace[i].scurved );
3426  fprintf( stderr, "\t\tend=%.2f,base=%.2f,curved=%d\n",
3427  bothspace[i].end,bothspace[i].ebase,bothspace[i].ecurved );
3428  }
3429  fprintf( stderr,"\n" );
3430 #endif
3431 
3432  err = ( stem->unit.x == 0 || stem->unit.y == 0 ) ?
3434  lmin = ( stem->lmin < -err ) ? stem->lmin : -err;
3435  rmax = ( stem->rmax > err ) ? stem->rmax : err;
3436  acnt = 0;
3437  if ( bcnt!=0 ) {
3438  for ( i=0; i<gd->pcnt; ++i ) if ( (pd = &gd->points[i])->sp!=NULL ) {
3439  /* Let's say we have a stem. And then inside that stem we have */
3440  /* another rectangle. So our first stem isn't really a stem any */
3441  /* more (because we hit another edge first), yet it's still reasonable*/
3442  /* to align the original stem */
3443  /* Now suppose the rectangle is rotated a bit so we can't make */
3444  /* a stem from it. What do we do here? */
3445  loff = ( pd->sp->me.x - stem->left.x ) * stem->unit.y -
3446  ( pd->sp->me.y - stem->left.y ) * stem->unit.x;
3447  roff = ( pd->sp->me.x - stem->right.x ) * stem->unit.y -
3448  ( pd->sp->me.y - stem->right.y ) * stem->unit.x;
3449 
3450  if ( loff >= lmin && roff <= rmax ) {
3451  pd->projection = (pd->sp->me.x - stem->left.x)*stem->unit.x +
3452  (pd->sp->me.y - stem->left.y)*stem->unit.y;
3453  if ( InActive(pd->projection,bothspace,bcnt) )
3454  pspace[pcnt++] = pd;
3455  }
3456  }
3457  qsort(pspace,pcnt,sizeof(struct pointdata *),proj_cmp);
3458 
3459  bpos = i = 0;
3460  while ( bpos<bcnt ) {
3461  if ( bothspace[bpos].curved || pcnt==0 ) {
3462  activespace[acnt++] = bothspace[bpos++];
3463  } else {
3464  last = bothspace[bpos].start;
3465  startset = false; endset = false;
3466 
3467  if ( bothspace[bpos].scurved ||
3468  StemIsActiveAt( gd,stem,bothspace[bpos].start+0.0015 )) {
3469 
3470  activespace[acnt].scurved = bothspace[bpos].scurved;
3471  activespace[acnt].start = bothspace[bpos].start;
3472  startset = true;
3473  }
3474 
3475  /* If the stem is preceded by a curved segment, then skip */
3476  /* the first point position and start from the next one. */
3477  /* (Otherwise StemIsActiveAt() may consider the stem is */
3478  /* "inactive" at the fragment between the start of the active */
3479  /* space and the first point actually belonging to this stem) */
3480  if ( bothspace[bpos].scurved ) {
3481  while ( pcnt>i && pspace[i]->projection < bothspace[bpos].sbase ) i++;
3482 
3483  if ( pcnt > i && pspace[i]->projection >= bothspace[bpos].sbase ) {
3484  last = activespace[acnt].end = pspace[i]->projection;
3485  activespace[acnt].ecurved = false;
3486  activespace[acnt].curved = false;
3487  endset=true;
3488  }
3489  }
3490 
3491  while ( i<pcnt && (
3492  ( !bothspace[bpos].ecurved && pspace[i]->projection<bothspace[bpos].end ) ||
3493  ( bothspace[bpos].ecurved && pspace[i]->projection<=bothspace[bpos].ebase ))) {
3494  if ( last==activespace[acnt].start && pspace[i]->projection >= last ) {
3495 
3496  if ( !StemIsActiveAt( gd,stem,last+(( 1.001*pspace[i]->projection-last )/2.001 ))) {
3497  last = activespace[acnt].start = pspace[i]->projection;
3498  activespace[acnt].scurved = false;
3499  startset = true; endset = false;
3500  } else {
3501  last = activespace[acnt].end = pspace[i]->projection;
3502  activespace[acnt].ecurved = false;
3503  activespace[acnt].curved = false;
3504  endset = true;
3505  }
3506  } else if (( last==activespace[acnt].end || !startset )
3507  && pspace[i]->projection >= last) {
3508 
3509  if ( !StemIsActiveAt( gd,stem,last+(( 1.001*pspace[i]->projection-last )/2.001 )) ||
3510  !startset ) {
3511 
3512  if ( startset ) acnt++;
3513  last = activespace[acnt].start = pspace[i]->projection;
3514  activespace[acnt].scurved = false;
3515  startset = true; endset = false;
3516  } else {
3517  last = activespace[acnt].end = pspace[i]->projection;
3518  activespace[acnt].ecurved = false;
3519  activespace[acnt].curved = false;
3520  endset = true;
3521  }
3522  }
3523  ++i;
3524  }
3525 
3526  if (( bothspace[bpos].ecurved ||
3527  StemIsActiveAt( gd,stem,bothspace[bpos].end-0.0015 )) &&
3528  startset ) {
3529 
3530  activespace[acnt].end = bothspace[bpos].end;
3531  activespace[acnt].ecurved = bothspace[bpos].ecurved;
3532  activespace[acnt].curved = bothspace[bpos].curved;
3533  endset = true;
3534  }
3535  ++bpos;
3536  if ( endset ) ++acnt;
3537  }
3538  }
3539  }
3540 
3541  for ( i=0; i<stem->chunk_cnt; ++i ) {
3542  chunk = &stem->chunks[i];
3543  /* stemcheat 1 -- diagonal edge stem;
3544  * 2 -- diagonal corner stem with a sharp top;
3545  * 3 -- diagonal corner stem with a flat top;
3546  * 4 -- bounding box hint */
3547  if ( chunk->stemcheat==3 && chunk->l!=NULL && chunk->r!=NULL &&
3548  i+1<stem->chunk_cnt &&
3549  stem->chunks[i+1].stemcheat==3 &&
3550  ( chunk->l==stem->chunks[i+1].l ||
3551  chunk->r==stem->chunks[i+1].r )) {
3552 
3553  SplinePoint *sp = chunk->l==stem->chunks[i+1].l ?
3554  chunk->l->sp : chunk->r->sp;
3555  proj = (sp->me.x - stem->left.x) *stem->unit.x +
3556  (sp->me.y - stem->left.y) *stem->unit.y;
3557 
3558  SplinePoint *sp2 = chunk->l==stem->chunks[i+1].l ?
3559  chunk->r->sp : chunk->l->sp;
3560  SplinePoint *sp3 = chunk->l==stem->chunks[i+1].l ?
3561  stem->chunks[i+1].r->sp : stem->chunks[i+1].l->sp;
3562  proj2 = (sp2->me.x - stem->left.x) *stem->unit.x +
3563  (sp2->me.y - stem->left.y) *stem->unit.y;
3564  proj3 = (sp3->me.x - stem->left.x) *stem->unit.x +
3565  (sp3->me.y - stem->left.y) *stem->unit.y;
3566 
3567  if ( proj2>proj3 ) {
3568  ptemp = proj2; proj2 = proj3; proj3 = ptemp;
3569  }
3570 
3571  if ( (proj3-proj2) < width ) {
3572  activespace[acnt ].curved = true;
3573  proj2 -= width/2;
3574  proj3 += width/2;
3575  } else {
3576  activespace[acnt ].curved = false;
3577  }
3578 
3579  activespace[acnt].start = proj2;
3580  activespace[acnt].end = proj3;
3581  activespace[acnt].sbase = activespace[acnt].ebase = proj;
3582  acnt++;
3583  ++i;
3584  } else if ( chunk->stemcheat && chunk->l!=NULL && chunk->r!=NULL ) {
3585  SplinePoint *sp = chunk->l->sp;
3586  proj = ( sp->me.x - stem->left.x ) * stem->unit.x +
3587  ( sp->me.y - stem->left.y ) * stem->unit.y;
3588  orig_proj = proj;
3589  SplinePoint *other = chunk->lnext ? sp->next->to : sp->prev->from;
3590  len = (other->me.x - sp->me.x) * stem->unit.x +
3591  (other->me.y - sp->me.y) * stem->unit.y;
3592  if ( chunk->stemcheat == 2 )
3593  proj -= width/2;
3594  else if ( len<0 )
3595  proj -= width;
3596  activespace[acnt].curved = true;
3597  activespace[acnt].start = proj;
3598  activespace[acnt].end = proj+width;
3599  activespace[acnt].sbase = activespace[acnt].ebase = orig_proj;
3600  acnt++;
3601  }
3602  }
3603 
3604  if ( acnt!=0 ) {
3605  stem->activecnt = MergeSegmentsFinal( activespace,acnt );
3606  stem->active = malloc(acnt*sizeof(struct segment));
3607  memcpy(stem->active,activespace,acnt*sizeof(struct segment));
3608  }
3609 
3610  len = clen = 0;
3611  for ( i=0; i<acnt; ++i ) {
3612  if ( stem->active[i].curved )
3613  clen += stem->active[i].end-stem->active[i].start;
3614  else
3615  len += stem->active[i].end-stem->active[i].start;
3616  }
3617  stem->len = len; stem->clen = len+clen;
3618 }
3619 
3620 static void GDStemsFixupIntersects(struct glyphdata *gd) {
3621  int i, j, stemidx;
3622  struct stemdata *stem;
3623  struct stem_chunk *chunk;
3624 
3625  for ( i=0; i<gd->stemcnt; ++i ) {
3626  stem = &gd->stems[i];
3627  for ( j=0; j<stem->chunk_cnt; ++j ) {
3628  chunk = &stem->chunks[j];
3629