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)  

splineutil.c
Go to the documentation of this file.
1 /* Copyright (C) 2000-2012 by George Williams */
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 "fontforgevw.h"
28 #include "encoding.h"
29 #include <math.h>
30 
31 #ifdef HAVE_IEEEFP_H
32 # include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */
33 #endif
34 
35 #include "sfd1.h" // This has the extended SplineFont type SplineFont1 for old file versions.
36 #ifdef FF_UTHASH_GLIF_NAMES
37 # include "glif_name_hash.h"
38 #endif
39 
40 
41 /*#define DEBUG 1*/
42 
43 typedef struct quartic {
46 
47 /* In an attempt to make allocation more efficient I just keep preallocated */
48 /* lists of certain common sizes. It doesn't seem to make much difference */
49 /* when allocating stuff, but does when freeing. If the extra complexity */
50 /* is bad then put: */
51 /* #define chunkalloc(size) calloc(1,size) */
52 /* #define chunkfree(item,size) free(item) */
53 /* into splinefont.h after (or instead of) the definition of chunkalloc()*/
54 
55 #define ALLOC_CHUNK 100 /* Number of small chunks to malloc at a time */
56 #ifndef FONTFORGE_CONFIG_USE_DOUBLE
57 # define CHUNK_MAX 100 /* Maximum size (in chunk units) that we are prepared to allocate */
58  /* The size of our data structures */
59 #else
60 # define CHUNK_MAX 129
61 #endif
62 # define CHUNK_UNIT sizeof(void *) /* will vary with the word size of */
63  /* the machine. if pointers are 64 bits*/
64  /* we may need twice as much space as for 32 bits */
65 
66 #ifdef FLAG
67 #undef FLAG
68 #define FLAG 0xbadcafe
69 #endif
70 
71 #ifdef CHUNKDEBUG
72 static int chunkdebug = 0; /* When this is set we never free anything, insuring that each chunk is unique */
73 #endif
74 
75 #if ALLOC_CHUNK>1
76 struct chunk { struct chunk *next; };
77 struct chunk2 { struct chunk2 *next; int flag; };
78 #endif
79 
80 #if defined(FLAG) && ALLOC_CHUNK>1
81 void chunktest(void) {
82  int i;
83  struct chunk2 *c;
84 
85  for ( i=2; i<CHUNK_MAX; ++i )
86  for ( c=(struct chunk2 *) chunklists[i]; c!=NULL; c=c->next )
87  if ( c->flag!=FLAG ) {
88  fprintf( stderr, "Chunk memory list has been corrupted\n" );
89  abort();
90  }
91 }
92 #endif
93 
95  LineList *next;
96 
97  while ( ll!=NULL ) {
98  next = ll->next;
99  chunkfree(ll,sizeof(LineList));
100  ll = next;
101  }
102 }
103 
106 
107  while ( la!=NULL ) {
108  next = la->next;
109  LineListFree(la->lines);
110  chunkfree(la,sizeof(LinearApprox));
111  la = next;
112  }
113 }
114 
117  chunkfree(spline,sizeof(Spline));
118 }
119 
121  SplinePoint *sp;
122  if ( (sp=chunkalloc(sizeof(SplinePoint)))!=NULL ) {
123  sp->me.x = x; sp->me.y = y;
124  sp->nextcp = sp->prevcp = sp->me;
125  sp->nonextcp = sp->noprevcp = true;
126  sp->nextcpdef = sp->prevcpdef = false;
127  sp->ttfindex = sp->nextcpindex = 0xfffe;
128  sp->name = NULL;
129  }
130  return( sp );
131 }
132 
134  Spline *spline = chunkalloc(sizeof(Spline));
135 
136  spline->from = from; spline->to = to;
137  from->next = to->prev = spline;
139 return( spline );
140 }
141 
143  chunkfree(sp->hintmask,sizeof(HintMask));
144  free(sp->name);
145  chunkfree(sp,sizeof(SplinePoint));
146 }
147 
149  Spline *first, *spline, *next;
150  int nonext;
151 
152  if ( spl==NULL )
153  return;
154  if ( spl->first!=NULL ) {
155  nonext = spl->first->next==NULL; // If there is no spline, we set a flag.
156  first = NULL;
157  // We start on the first spline if it exists.
158  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline = next ) {
159  next = spline->to->next; // Cache the location of the next spline.
160  SplinePointFree(spline->to); // Free the destination point.
161  SplineFree(spline); // Free the spline.
162  if ( first==NULL ) first = spline; // We want to avoid repeating the circuit.
163  }
164  // If the path is open or has no splines, free the starting point.
165  if ( spl->last!=spl->first || nonext )
166  SplinePointFree(spl->first);
167  }
168 }
169 
171 
172  if ( spl==NULL ) return;
173  SplinePointsFree(spl);
174  free(spl->spiros);
175  free(spl->contour_name);
176  chunkfree(spl,sizeof(SplinePointList));
177 }
178 
181 
182  while ( spl!=NULL ) {
183  next = spl->next;
184  SplinePointListFree(spl);
185  spl = next;
186  }
187 }
188 
190  free(spl->spiros);
191  spl->spiros = NULL;
192  spl->spiro_cnt = spl->spiro_max = 0;
193 }
194 
195 
197  int i;
198 
199  if ( ref==NULL )
200 return;
201  for ( i=0; i<ref->layer_cnt; ++i ) {
202  SplinePointListsFree(ref->layers[i].splines);
203  GradientFree(ref->layers[i].fill_brush.gradient);
204  GradientFree(ref->layers[i].stroke_pen.brush.gradient);
205  PatternFree(ref->layers[i].fill_brush.pattern);
206  PatternFree(ref->layers[i].stroke_pen.brush.pattern);
207  }
208  free(ref->layers);
209  chunkfree(ref,sizeof(RefChar));
210 }
211 
213  RefChar *ref = chunkalloc(sizeof(RefChar));
214  ref->layer_cnt = 1;
215  ref->layers = calloc(1,sizeof(struct reflayer));
216  ref->layers[0].fill_brush.opacity = ref->layers[0].stroke_pen.brush.opacity = 1.0;
217  ref->layers[0].fill_brush.col = ref->layers[0].stroke_pen.brush.col = COLOR_INHERITED;
218  ref->layers[0].stroke_pen.width = WIDTH_INHERITED;
219  ref->layers[0].stroke_pen.linecap = lc_inherited;
220  ref->layers[0].stroke_pen.linejoin = lj_inherited;
221  ref->layers[0].dofill = true;
222  ref->round_translation_to_grid = true;
223 return( ref );
224 }
225 
227  RefChar *rnext;
228 
229  while ( ref!=NULL ) {
230  rnext = ref->next;
231  RefCharFree(ref);
232  ref = rnext;
233  }
234 }
235 
236 typedef struct spline1 {
241 
243  bigreal s = (t1-t0);
244  if ( sp->a==0 && sp->b==0 ) {
245  sp1->sp.d = sp->d + t0*sp->c;
246  sp1->sp.c = s*sp->c;
247  sp1->sp.b = sp1->sp.a = 0;
248  } else {
249  sp1->sp.d = sp->d + t0*(sp->c + t0*(sp->b + t0*sp->a));
250  sp1->sp.c = s*(sp->c + t0*(2*sp->b + 3*sp->a*t0));
251  sp1->sp.b = s*s*(sp->b+3*sp->a*t0);
252  sp1->sp.a = s*s*s*sp->a;
253  }
254  sp1->c0 = sp1->sp.c/3 + sp1->sp.d;
255  sp1->c1 = sp1->c0 + (sp1->sp.b+sp1->sp.c)/3;
256 }
257 
258 static void SplineFindBounds(const Spline *sp, DBounds *bounds) {
259  real t, b2_fourac, v;
260  real min, max;
261  const Spline1D *sp1;
262  int i;
263 
264  /* first try the end points */
265  for ( i=0; i<2; ++i ) {
266  sp1 = &sp->splines[i];
267  if ( i==0 ) {
268  if ( sp->to->me.x<bounds->minx ) bounds->minx = sp->to->me.x;
269  if ( sp->to->me.x>bounds->maxx ) bounds->maxx = sp->to->me.x;
270  min = bounds->minx; max = bounds->maxx;
271  } else {
272  if ( sp->to->me.y<bounds->miny ) bounds->miny = sp->to->me.y;
273  if ( sp->to->me.y>bounds->maxy ) bounds->maxy = sp->to->me.y;
274  min = bounds->miny; max = bounds->maxy;
275  }
276 
277  /* then try the extrema of the spline (assuming they are between t=(0,1) */
278  /* (I don't bother fixing up for tiny rounding errors here. they don't matter */
279  /* But we could call CheckExtremaForSingleBitErrors */
280  if ( sp1->a!=0 ) {
281  b2_fourac = 4*sp1->b*sp1->b - 12*sp1->a*sp1->c;
282  if ( b2_fourac>=0 ) {
283  b2_fourac = sqrt(b2_fourac);
284  t = (-2*sp1->b + b2_fourac) / (6*sp1->a);
285  if ( t>0 && t<1 ) {
286  v = ((sp1->a*t+sp1->b)*t+sp1->c)*t + sp1->d;
287  if ( v<min ) min = v;
288  if ( v>max ) max = v;
289  }
290  t = (-2*sp1->b - b2_fourac) / (6*sp1->a);
291  if ( t>0 && t<1 ) {
292  v = ((sp1->a*t+sp1->b)*t+sp1->c)*t + sp1->d;
293  if ( v<min ) min = v;
294  if ( v>max ) max = v;
295  }
296  }
297  } else if ( sp1->b!=0 ) {
298  t = -sp1->c/(2.0*sp1->b);
299  if ( t>0 && t<1 ) {
300  v = (sp1->b*t+sp1->c)*t + sp1->d;
301  if ( v<min ) min = v;
302  if ( v>max ) max = v;
303  }
304  }
305  if ( i==0 ) {
306  bounds->minx = min; bounds->maxx = max;
307  } else {
308  bounds->miny = min; bounds->maxy = max;
309  }
310  }
311 }
312 
313 static void _SplineSetFindBounds(const SplinePointList *spl, DBounds *bounds) {
314  Spline *spline, *first;
315  /* Ignore contours consisting of a single point (used for hinting, anchors */
316  /* for mark to base, etc. */
317 
318  for ( ; spl!=NULL; spl = spl->next ) if ( spl->first->next!=NULL && spl->first->next->to != spl->first ) {
319  first = NULL;
320  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 ) {
321  bounds->minx = bounds->maxx = spl->first->me.x;
322  bounds->miny = bounds->maxy = spl->first->me.y;
323  } else {
324  if ( spl->first->me.x<bounds->minx ) bounds->minx = spl->first->me.x;
325  if ( spl->first->me.x>bounds->maxx ) bounds->maxx = spl->first->me.x;
326  if ( spl->first->me.y<bounds->miny ) bounds->miny = spl->first->me.y;
327  if ( spl->first->me.y>bounds->maxy ) bounds->maxy = spl->first->me.y;
328  }
329  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
330  SplineFindBounds(spline,bounds);
331  if ( first==NULL ) first = spline;
332  }
333  }
334 }
335 
336 static void _SplineSetFindClippedBounds(const SplinePointList *spl, DBounds *bounds,DBounds *clipb) {
337  Spline *spline, *first;
338  /* Ignore contours consisting of a single point (used for hinting, anchors */
339  /* for mark to base, etc. */
340 
341  for ( ; spl!=NULL; spl = spl->next ) if ( spl->first->next!=NULL && spl->first->next->to != spl->first ) {
342  first = NULL;
343  if ( !spl->is_clip_path ) {
344  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 ) {
345  bounds->minx = bounds->maxx = spl->first->me.x;
346  bounds->miny = bounds->maxy = spl->first->me.y;
347  } else {
348  if ( spl->first->me.x<bounds->minx ) bounds->minx = spl->first->me.x;
349  if ( spl->first->me.x>bounds->maxx ) bounds->maxx = spl->first->me.x;
350  if ( spl->first->me.y<bounds->miny ) bounds->miny = spl->first->me.y;
351  if ( spl->first->me.y>bounds->maxy ) bounds->maxy = spl->first->me.y;
352  }
353  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
354  SplineFindBounds(spline,bounds);
355  if ( first==NULL ) first = spline;
356  }
357  } else {
358  if ( clipb->minx==0 && clipb->maxx==0 && clipb->miny==0 && clipb->maxy == 0 ) {
359  clipb->minx = clipb->maxx = spl->first->me.x;
360  clipb->miny = clipb->maxy = spl->first->me.y;
361  } else {
362  if ( spl->first->me.x<clipb->minx ) clipb->minx = spl->first->me.x;
363  if ( spl->first->me.x>clipb->maxx ) clipb->maxx = spl->first->me.x;
364  if ( spl->first->me.y<clipb->miny ) clipb->miny = spl->first->me.y;
365  if ( spl->first->me.y>clipb->maxy ) clipb->maxy = spl->first->me.y;
366  }
367  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
368  SplineFindBounds(spline,clipb);
369  if ( first==NULL ) first = spline;
370  }
371  }
372  }
373 }
374 
376  RefChar *rf;
377  real e;
378  DBounds b, clipb;
379 
380  for ( rf=sc->layers[layer].refs; rf!=NULL; rf = rf->next ) {
381  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 )
382  *bounds = rf->bb;
383  else if ( rf->bb.minx!=0 || rf->bb.maxx != 0 || rf->bb.maxy != 0 || rf->bb.miny!=0 ) {
384  if ( rf->bb.minx < bounds->minx ) bounds->minx = rf->bb.minx;
385  if ( rf->bb.miny < bounds->miny ) bounds->miny = rf->bb.miny;
386  if ( rf->bb.maxx > bounds->maxx ) bounds->maxx = rf->bb.maxx;
387  if ( rf->bb.maxy > bounds->maxy ) bounds->maxy = rf->bb.maxy;
388  }
389  }
390  memset(&b,0,sizeof(b));
391  memset(&clipb,0,sizeof(clipb));
392  _SplineSetFindClippedBounds(sc->layers[layer].splines,&b,&clipb);
393  if ( sc->layers[layer].dostroke ) {
394  if ( sc->layers[layer].stroke_pen.width!=WIDTH_INHERITED )
395  e = sc->layers[layer].stroke_pen.width*sc->layers[layer].stroke_pen.trans[0];
396  else
397  e = sc->layers[layer].stroke_pen.trans[0];
398  b.minx -= e; b.maxx += e;
399  b.miny -= e; b.maxy += e;
400  }
401  if ( clipb.minx!=0 || clipb.miny!=0 || clipb.maxx!=0 || clipb.maxy!=0 ) {
402  if ( b.minx<clipb.minx ) b.minx = clipb.minx;
403  if ( b.miny<clipb.miny ) b.miny = clipb.miny;
404  if ( b.maxx>clipb.maxx ) b.maxx = clipb.maxx;
405  if ( b.maxy>clipb.maxy ) b.maxy = clipb.maxy;
406  }
407  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 )
408  *bounds = b;
409  else if ( b.minx!=0 || b.maxx != 0 || b.maxy != 0 || b.miny!=0 ) {
410  if ( b.minx < bounds->minx ) bounds->minx = b.minx;
411  if ( b.miny < bounds->miny ) bounds->miny = b.miny;
412  if ( b.maxx > bounds->maxx ) bounds->maxx = b.maxx;
413  if ( b.maxy > bounds->maxy ) bounds->maxy = b.maxy;
414  }
415 
416  if ( sc->parent!=NULL && sc->parent->strokedfont &&
417  (bounds->minx!=bounds->maxx || bounds->miny!=bounds->maxy)) {
418  real sw = sc->parent->strokewidth;
419  bounds->minx -= sw; bounds->miny -= sw;
420  bounds->maxx += sw; bounds->maxy += sw;
421  }
422 }
423 
425 
426  if ( sc->parent!=NULL && sc->parent->multilayer ) {
427  SplineCharFindBounds(sc,bounds);
428 return;
429  }
430 
431  /* a char with no splines (ie. a space) must have an lbearing of 0 */
432  bounds->minx = bounds->maxx = 0;
433  bounds->miny = bounds->maxy = 0;
434 
436 }
437 
439  int i;
440  int first,last;
441 
442  /* a char with no splines (ie. a space) must have an lbearing of 0 */
443  bounds->minx = bounds->maxx = 0;
444  bounds->miny = bounds->maxy = 0;
445 
446  first = last = ly_fore;
447  if ( sc->parent!=NULL && sc->parent->multilayer )
448  last = sc->layer_cnt-1;
449  for ( i=first; i<=last; ++i )
451 }
452 
454  int i, k, first, last;
455 
456  if ( sf->multilayer ) {
457  SplineFontFindBounds(sf,bounds);
458 return;
459  }
460 
461  bounds->minx = bounds->maxx = 0;
462  bounds->miny = bounds->maxy = 0;
463 
464  for ( i = 0; i<sf->glyphcnt; ++i ) {
465  SplineChar *sc = sf->glyphs[i];
466  if ( sc!=NULL ) {
467  first = last = ly_fore;
468  if ( sc->parent != NULL && sc->parent->multilayer )
469  last = sc->layer_cnt-1;
470  for ( k=first; k<=last; ++k )
472  }
473  }
474 }
475 
477  int i, k, first, last;
478 
479  bounds->minx = bounds->maxx = 0;
480  bounds->miny = bounds->maxy = 0;
481 
482  for ( i = 0; i<sf->glyphcnt; ++i ) {
483  SplineChar *sc = sf->glyphs[i];
484  if ( sc!=NULL ) {
485  first = last = ly_fore;
486  if ( sf->multilayer )
487  last = sc->layer_cnt-1;
488  for ( k=first; k<=last; ++k )
490  }
491  }
492 }
493 
494 void CIDLayerFindBounds(SplineFont *cidmaster,int layer,DBounds *bounds) {
495  SplineFont *sf;
496  int i;
497  DBounds b;
498  real factor;
499 
500  if ( cidmaster->cidmaster )
501  cidmaster = cidmaster->cidmaster;
502  if ( cidmaster->subfonts==NULL ) {
503  SplineFontLayerFindBounds(cidmaster,layer,bounds);
504 return;
505  }
506 
507  sf = cidmaster->subfonts[0];
509  factor = 1000.0/(sf->ascent+sf->descent);
510  bounds->maxx *= factor; bounds->minx *= factor; bounds->miny *= factor; bounds->maxy *= factor;
511  for ( i=1; i<cidmaster->subfontcnt; ++i ) {
512  sf = cidmaster->subfonts[i];
514  factor = 1000.0/(sf->ascent+sf->descent);
515  b.maxx *= factor; b.minx *= factor; b.miny *= factor; b.maxy *= factor;
516  if ( b.maxx>bounds->maxx ) bounds->maxx = b.maxx;
517  if ( b.maxy>bounds->maxy ) bounds->maxy = b.maxy;
518  if ( b.miny<bounds->miny ) bounds->miny = b.miny;
519  if ( b.minx<bounds->minx ) bounds->minx = b.minx;
520  }
521 }
522 
524  SplinePoint *sp;
525 
526  for ( ; ss!=NULL; ss=ss->next ) {
527  for ( sp=ss->first; ; ) {
528  if ( sp->me.y > top->y ) *top = sp->me;
529  if ( sp->next==NULL )
530  break;
531  sp = sp->next->to;
532  if ( sp==ss->first )
533  break;
534  }
535  }
536 }
537 
539  SplinePoint *sp;
540 
541  b->minx = b->miny = 1e10;
542  b->maxx = b->maxy = -1e10;
543  for ( ; ss!=NULL; ss=ss->next ) {
544  for ( sp=ss->first; ; ) {
545  if ( sp->me.y < b->miny ) b->miny = sp->me.y;
546  if ( sp->me.x < b->minx ) b->minx = sp->me.x;
547  if ( sp->me.y > b->maxy ) b->maxy = sp->me.y;
548  if ( sp->me.x > b->maxx ) b->maxx = sp->me.x;
549  // Frank added the control points to the calculation since,
550  // according to Adam Twardoch,
551  // the OpenType values that rely upon this function
552  // expect control points to be included.
553  if ( !sp->noprevcp ) {
554  if ( sp->prevcp.y < b->miny ) b->miny = sp->prevcp.y;
555  if ( sp->prevcp.x < b->minx ) b->minx = sp->prevcp.x;
556  if ( sp->prevcp.y > b->maxy ) b->maxy = sp->prevcp.y;
557  if ( sp->prevcp.x > b->maxx ) b->maxx = sp->prevcp.x;
558  }
559  if ( !sp->nonextcp ) {
560  if ( sp->nextcp.y < b->miny ) b->miny = sp->nextcp.y;
561  if ( sp->nextcp.x < b->minx ) b->minx = sp->nextcp.x;
562  if ( sp->nextcp.y > b->maxy ) b->maxy = sp->nextcp.y;
563  if ( sp->nextcp.x > b->maxx ) b->maxx = sp->nextcp.x;
564  }
565  if ( sp->next==NULL )
566  break;
567  sp = sp->next->to;
568  if ( sp==ss->first )
569  break;
570  }
571  }
572  if ( b->minx>65536 ) b->minx = 0;
573  if ( b->miny>65536 ) b->miny = 0;
574  if ( b->maxx<-65536 ) b->maxx = 0;
575  if ( b->maxy<-65536 ) b->maxy = 0;
576 }
577 
579  RefChar *ref;
580  int i,first, last;
581  DBounds temp;
582  real e;
583 
584  b->minx = b->miny = 1e10;
585  b->maxx = b->maxy = -1e10;
586  first = last = ly_fore;
587  if ( sc->parent!=NULL && sc->parent->multilayer )
588  last = sc->layer_cnt-1;
589  for ( i=first; i<=last; ++i ) {
590  SplineSetQuickBounds(sc->layers[i].splines,&temp);
591  if ( sc->layers[i].dostroke && sc->layers[i].splines!=NULL ) {
592  if ( sc->layers[i].stroke_pen.width!=WIDTH_INHERITED )
593  e = sc->layers[i].stroke_pen.width*sc->layers[i].stroke_pen.trans[0];
594  else
595  e = sc->layers[i].stroke_pen.trans[0];
596  temp.minx -= e; temp.maxx += e;
597  temp.miny -= e; temp.maxy += e;
598  }
599  if ( temp.minx!=0 || temp.maxx != 0 || temp.maxy != 0 || temp.miny!=0 ) {
600  if ( temp.minx < b->minx ) b->minx = temp.minx;
601  if ( temp.miny < b->miny ) b->miny = temp.miny;
602  if ( temp.maxx > b->maxx ) b->maxx = temp.maxx;
603  if ( temp.maxy > b->maxy ) b->maxy = temp.maxy;
604  }
605  for ( ref = sc->layers[i].refs; ref!=NULL; ref = ref->next ) {
606  /*SplineSetQuickBounds(ref->layers[0].splines,&temp);*/
607  if ( b->minx==0 && b->maxx==0 && b->miny==0 && b->maxy == 0 )
608  *b = ref->bb;
609  else if ( ref->bb.minx!=0 || ref->bb.maxx != 0 || ref->bb.maxy != 0 || ref->bb.miny!=0 ) {
610  if ( ref->bb.minx < b->minx ) b->minx = ref->bb.minx;
611  if ( ref->bb.miny < b->miny ) b->miny = ref->bb.miny;
612  if ( ref->bb.maxx > b->maxx ) b->maxx = ref->bb.maxx;
613  if ( ref->bb.maxy > b->maxy ) b->maxy = ref->bb.maxy;
614  }
615  }
616  }
617  if ( sc->parent!=NULL && sc->parent->strokedfont &&
618  (b->minx!=b->maxx || b->miny!=b->maxy)) {
619  real sw = sc->parent->strokewidth;
620  b->minx -= sw; b->miny -= sw;
621  b->maxx += sw; b->maxy += sw;
622  }
623  if ( b->minx>1e9 )
624  memset(b,0,sizeof(*b));
625 }
626 
628  RefChar *ref;
629  DBounds temp;
630 
631  if ( sc->parent!=NULL && sc->parent->multilayer ) {
632  SplineCharQuickBounds(sc,bounds);
633 return;
634  }
635 
636  bounds->minx = bounds->miny = 1e10;
637  bounds->maxx = bounds->maxy = -1e10;
638 
639  SplineSetQuickBounds(sc->layers[layer].splines,bounds);
640 
641  for ( ref = sc->layers[layer].refs; ref!=NULL; ref = ref->next ) {
642  SplineSetQuickBounds(ref->layers[0].splines,&temp);
643  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 )
644  *bounds = temp;
645  else if ( temp.minx!=0 || temp.maxx != 0 || temp.maxy != 0 || temp.miny!=0 ) {
646  if ( temp.minx < bounds->minx ) bounds->minx = temp.minx;
647  if ( temp.miny < bounds->miny ) bounds->miny = temp.miny;
648  if ( temp.maxx > bounds->maxx ) bounds->maxx = temp.maxx;
649  if ( temp.maxy > bounds->maxy ) bounds->maxy = temp.maxy;
650  }
651  }
652  /* a char with no splines (ie. a space) must have an lbearing of 0 */
653  if ( bounds->minx>1e9 )
654  memset(bounds,0,sizeof(*bounds));
655 }
656 
658  int oldpointtype = sp->pointtype;
659 
660  sp->pointtype = pt_corner;
661  if ( sp->next==NULL && sp->prev==NULL )
662  ;
663  else if ( (sp->next!=NULL && sp->next->to->me.x==sp->me.x && sp->next->to->me.y==sp->me.y) ||
664  (sp->prev!=NULL && sp->prev->from->me.x==sp->me.x && sp->prev->from->me.y==sp->me.y ))
665  ;
666  else if ( sp->next==NULL ) {
667  sp->pointtype = sp->noprevcp ? pt_corner : pt_curve;
668  } else if ( sp->prev==NULL ) {
669  sp->pointtype = sp->nonextcp ? pt_corner : pt_curve;
670  } else if ( sp->nonextcp && sp->noprevcp ) {
671  ;
672  } else {
673  BasePoint ndir, ncdir, ncunit, pdir, pcdir, pcunit;
674  bigreal nlen, nclen, plen, pclen;
675  bigreal cross, bounds;
676 
677  ncdir.x = sp->nextcp.x - sp->me.x; ncdir.y = sp->nextcp.y - sp->me.y;
678  pcdir.x = sp->prevcp.x - sp->me.x; pcdir.y = sp->prevcp.y - sp->me.y;
679  ndir.x = ndir.y = pdir.x = pdir.y = 0;
680  if ( sp->next!=NULL ) {
681  ndir.x = sp->next->to->me.x - sp->me.x; ndir.y = sp->next->to->me.y - sp->me.y;
682  }
683  if ( sp->prev!=NULL ) {
684  pdir.x = sp->prev->from->me.x - sp->me.x; pdir.y = sp->prev->from->me.y - sp->me.y;
685  }
686  nclen = sqrt(ncdir.x*ncdir.x + ncdir.y*ncdir.y);
687  pclen = sqrt(pcdir.x*pcdir.x + pcdir.y*pcdir.y);
688  nlen = sqrt(ndir.x*ndir.x + ndir.y*ndir.y);
689  plen = sqrt(pdir.x*pdir.x + pdir.y*pdir.y);
690  ncunit = ncdir; pcunit = pcdir;
691  if ( nclen!=0 ) { ncunit.x /= nclen; ncunit.y /= nclen; }
692  if ( pclen!=0 ) { pcunit.x /= pclen; pcunit.y /= pclen; }
693  if ( nlen!=0 ) { ndir.x /= nlen; ndir.y /= nlen; }
694  if ( plen!=0 ) { pdir.x /= plen; pdir.y /= plen; }
695 
696  /* find out which side has the shorter control vector. Cross that vector */
697  /* with the normal of the unit vector on the other side. If the */
698  /* result is less than 1 em-unit then we've got colinear control points */
699  /* (within the resolution of the integer grid) */
700  /* Not quite... they could point in the same direction */
701  if ( oldpointtype==pt_curve )
702  bounds = 4.0;
703  else
704  bounds = 1.0;
705  if ( nclen!=0 && pclen!=0 &&
706  ((nclen>=pclen && (cross = pcdir.x*ncunit.y - pcdir.y*ncunit.x)<bounds && cross>-bounds ) ||
707  (pclen>nclen && (cross = ncdir.x*pcunit.y - ncdir.y*pcunit.x)<bounds && cross>-bounds )) &&
708  ncdir.x*pcdir.x + ncdir.y*pcdir.y < 0 )
709  sp->pointtype = pt_curve;
710  /* Cross product of control point with unit vector normal to line in */
711  /* opposite direction should be less than an em-unit for a tangent */
712  else if (( nclen==0 && pclen!=0 && (cross = pcdir.x*ndir.y-pcdir.y*ndir.x)<bounds && cross>-bounds ) ||
713  ( pclen==0 && nclen!=0 && (cross = ncdir.x*pdir.y-ncdir.y*pdir.x)<bounds && cross>-bounds ))
714  sp->pointtype = pt_tangent;
715 
716  /* If a point started out hv, and could still be hv, them make it so */
717  /* but don't make hv points de novo, Alexey doesn't like change */
718  /* (this only works because hv isn't a default setting, so if it's */
719  /* there it was done intentionally) */
720  if ( sp->pointtype == pt_curve && oldpointtype == pt_hvcurve &&
721  ((sp->nextcp.x==sp->me.x && sp->prevcp.x==sp->me.x && sp->nextcp.y!=sp->me.y) ||
722  (sp->nextcp.y==sp->me.y && sp->prevcp.y==sp->me.y && sp->nextcp.x!=sp->me.x)))
723  sp->pointtype = pt_hvcurve;
724  }
725 }
726 
728  Spline *spline, *first, *last=NULL;
729 
730  for ( ; spl!=NULL; spl = spl->next ) {
731  first = NULL;
732  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
734  last = spline;
735  if ( first==NULL ) first = spline;
736  }
737  if ( spline==NULL && last!=NULL )
739  }
740 }
741 
744  const SplinePoint *pt; SplinePoint *cpt;
745  Spline *spline;
746 
747  cur = chunkalloc(sizeof(SplinePointList));
748  cur->is_clip_path = spl->is_clip_path;
749  cur->spiro_cnt = cur->spiro_max = 0;
750  cur->spiros = 0;
751  if (spl->contour_name != NULL) cur->contour_name = copy(spl->contour_name);
752  for ( pt=spl->first; ; ) {
753  cpt = SplinePointCreate( 0, 0 );
754  *cpt = *pt;
755  if ( pt->hintmask!=NULL ) {
756  cpt->hintmask = chunkalloc(sizeof(HintMask));
757  memcpy(cpt->hintmask,pt->hintmask,sizeof(HintMask));
758  }
759  if ( pt->name!=NULL ) {
760  cpt->name = copy(pt->name);
761  }
762  cpt->next = cpt->prev = NULL;
763  if ( cur->first==NULL ) {
764  cur->first = cur->last = cpt;
765  cur->start_offset = 0;
766  } else {
767  spline = chunkalloc(sizeof(Spline));
768  *spline = *pt->prev;
769  spline->from = cur->last;
770  cur->last->next = spline;
771  cpt->prev = spline;
772  spline->to = cpt;
773  spline->approx = NULL;
774  cur->last = cpt;
775  }
776  if ( pt->next==NULL )
777  break;
778  pt = pt->next->to;
779  if ( pt==spl->first )
780  break;
781  }
782  if ( spl->first->prev!=NULL ) {
783  cpt = cur->first;
784  spline = chunkalloc(sizeof(Spline));
785  *spline = *pt->prev;
786  spline->from = cur->last;
787  cur->last->next = spline;
788  cpt->prev = spline;
789  spline->to = cpt;
790  spline->approx = NULL;
791  cur->last = cpt;
792  }
793  if ( spl->spiro_cnt!=0 ) {
794  cur->spiro_cnt = cur->spiro_max = spl->spiro_cnt;
795  cur->spiros = malloc(cur->spiro_cnt*sizeof(spiro_cp));
796  memcpy(cur->spiros,spl->spiros,cur->spiro_cnt*sizeof(spiro_cp));
797  }
798 return( cur );
799 }
800 
803 
804  for ( ; base!=NULL; base = base->next ) {
806  if ( head==NULL )
807  head = cur;
808  else
809  last->next = cur;
810  last = cur;
811  }
812 return( head );
813 }
814 
816  BasePoint p;
817  p.x = transform[0]*from->x + transform[2]*from->y + transform[4];
818  p.y = transform[1]*from->x + transform[3]*from->y + transform[5];
819  to->x = rint(1024*p.x)/1024;
820  to->y = rint(1024*p.y)/1024;
821 }
822 
824 {
825  /**
826  * If we are to transform selected BCP instead of their base splinepoint
827  * then lets do that.
828  */
829  if( tpmask & tpmask_operateOnSelectedBCP
830  && (sp->nextcpselected || sp->prevcpselected ))
831  {
832  if( sp->nextcpselected )
833  {
834  int order2 = sp->next ? sp->next->order2 : 0;
835  BpTransform(&sp->nextcp,&sp->nextcp,transform);
836  SPTouchControl( sp, &sp->nextcp, order2 );
837  }
838  else if( sp->prevcpselected )
839  {
840  int order2 = sp->next ? sp->next->order2 : 0;
841  BpTransform(&sp->prevcp,&sp->prevcp,transform);
842  SPTouchControl( sp, &sp->prevcp, order2 );
843  }
844  }
845  else
846  {
847  /**
848  * Transform the base splinepoints.
849  */
850  BpTransform(&sp->me,&sp->me,transform);
851 
852  if ( !sp->nonextcp )
853  {
854  BpTransform(&sp->nextcp,&sp->nextcp,transform);
855  }
856  else
857  {
858  sp->nextcp = sp->me;
859  }
860 
861  if ( !sp->noprevcp )
862  {
863  BpTransform(&sp->prevcp,&sp->prevcp,transform);
864  }
865  else
866  {
867  sp->prevcp = sp->me;
868  }
869  }
870 
871 
872 
873  if ( sp->pointtype == pt_hvcurve )
874  {
875  if(
876  ((sp->nextcp.x==sp->me.x && sp->prevcp.x==sp->me.x && sp->nextcp.y!=sp->me.y) ||
877  (sp->nextcp.y==sp->me.y && sp->prevcp.y==sp->me.y && sp->nextcp.x!=sp->me.x)))
878  {
879  /* Do Nothing */;
880  }
881  else
882  {
883  sp->pointtype = pt_curve;
884  }
885  }
886 }
887 
889 {
891 }
892 
894  bigreal x;
895 
896  x = transform[0]*cp->x + transform[2]*cp->y + transform[4];
897  cp->y = transform[1]*cp->x + transform[3]*cp->y + transform[5];
898  cp->x = x;
899 }
900 
902  BasePoint *toorig,real transform[6] ) {
903  BasePoint totrans, temp;
904  bigreal fraction;
905 
906  /* Normally the "from" point will already have been translated, and the "to" */
907  /* point will need to be. But if we have a closed contour then on the */
908  /* last spline both from and to will have been transform. We can detect */
909  /* this because toorig will be different from &spline->to->me */
910  if ( spline->to->selected && toorig==&spline->to->me )
911  BpTransform(&totrans,&spline->to->me,transform);
912  else
913  totrans = spline->to->me;
914 
915  /* None of the control points will have been transformed yet */
916  if ( fromorig->x!=toorig->x ) {
917  fraction = (spline->from->nextcp.x-fromorig->x)/( toorig->x-fromorig->x );
918  spline->from->nextcp.x = spline->from->me.x + fraction*( totrans.x-spline->from->me.x );
919  fraction = (spline->to->prevcp.x-fromorig->x)/( toorig->x-fromorig->x );
920  spline->to->prevcp.x = spline->from->me.x + fraction*( totrans.x-spline->from->me.x );
921  } else {
923  spline->from->nextcp.x = temp.x;
925  spline->to->prevcp.x = temp.x;
926  }
927  if ( fromorig->y!=toorig->y ) {
928  fraction = (spline->from->nextcp.y-fromorig->y)/( toorig->y-fromorig->y );
929  spline->from->nextcp.y = spline->from->me.y + fraction*( totrans.y-spline->from->me.y );
930  fraction = (spline->to->prevcp.y-fromorig->y)/( toorig->y-fromorig->y );
931  spline->to->prevcp.y = spline->from->me.y + fraction*( totrans.y-spline->from->me.y );
932  } else {
934  spline->from->nextcp.y = temp.y;
936  spline->to->prevcp.y = temp.y;
937  }
938 
939  if ( spline->to->selected )
940  spline->to->me = totrans;
941 }
942 
943 
945  enum transformPointType tpt, enum transformPointMask tpmask ) {
946  Spline *spline, *first;
947  SplinePointList *spl;
948  SplinePoint *spt, *pfirst;
949  int allsel, anysel, alldone=true;
950  BasePoint lastpointorig, firstpointorig, orig;
951 
952  for ( spl = base; spl!=NULL; spl = spl->next ) {
953  pfirst = NULL; first = NULL;
954  allsel = true; anysel=false;
955  if ( tpt==tpt_OnlySelectedInterpCPs && spl->first->next!=NULL && !spl->first->next->order2 ) {
956  lastpointorig = firstpointorig = spl->first->me;
957  printf("SplinePointListTransformExtended() spl->first->selected %d\n", spl->first->selected );
958  if ( spl->first->selected ) {
959  anysel = true;
960  BpTransform(&spl->first->me,&spl->first->me,transform);
961  } else
962  allsel = false;
963  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
964  if ( first==NULL ) first = spline;
965  orig = spline->to->me;
966  if ( spline->from->selected || spline->to->selected )
967  {
968  TransformPTsInterpolateCPs( &lastpointorig, spline,
969  spl->first==spline->to? &firstpointorig : &spline->to->me,
970  transform );
971  }
972  lastpointorig = orig;
973  if ( spline->to->selected ) anysel = true; else allsel = false;
974  }
975 
976  } else {
977  for ( spt = spl->first ; spt!=pfirst; spt = spt->next->to ) {
978  if ( pfirst==NULL ) pfirst = spt;
979  if ( tpt==tpt_AllPoints || spt->selected ) {
980  TransformPointExtended(spt,transform,tpmask);
981  if ( tpt!=tpt_AllPoints ) {
982  if ( spt->next!=NULL && spt->next->order2 && !spt->next->to->selected && spt->next->to->ttfindex==0xffff ) {
983  SplinePoint *to = spt->next->to;
984  to->prevcp = spt->nextcp;
985  to->me.x = (to->prevcp.x+to->nextcp.x)/2;
986  to->me.y = (to->prevcp.y+to->nextcp.y)/2;
987  }
988  if ( spt->prev!=NULL && spt->prev->order2 && !spt->prev->from->selected && spt->prev->from->ttfindex==0xffff ) {
989  SplinePoint *from = spt->prev->from;
990  from->nextcp = spt->prevcp;
991  from->me.x = (from->prevcp.x+from->nextcp.x)/2;
992  from->me.y = (from->prevcp.y+from->nextcp.y)/2;
993  }
994  }
995  anysel = true;
996  } else
997  allsel = alldone = false;
998  if ( spt->next==NULL )
999  break;
1000  }
1001  }
1002  if ( !anysel ) /* This splineset had no selected points it's unchanged */
1003  continue;
1004 
1005  /* If we changed all the points, then transform the spiro version too */
1006  /* otherwise if we just changed some points, throw away the spiro */
1007  if ( allsel ) {
1008  int i;
1009  for ( i=0; i<spl->spiro_cnt-1; ++i )
1010  TransformSpiro(&spl->spiros[i], transform);
1011  } else
1012  SplineSetSpirosClear(spl);
1013 
1014  /* if we changed all the points then the control points are right */
1015  /* otherwise those near the edges may be wonky, fix 'em up */
1016  /* Figuring out where the edges of the selection are is difficult */
1017  /* so let's just tweak all points, it shouldn't matter */
1018  /* It does matter. Let's tweak all default points */
1019  if( !(tpmask & tpmask_dontFixControlPoints))
1020  {
1021  if ( tpt!=tpt_AllPoints && !allsel && spl->first->next!=NULL && !spl->first->next->order2 )
1022  {
1023  pfirst = NULL;
1024  for ( spt = spl->first ; spt!=pfirst; spt = spt->next->to )
1025  {
1026  if ( pfirst==NULL ) pfirst = spt;
1027  if ( spt->selected && spt->prev!=NULL && !spt->prev->from->selected &&
1028  spt->prev->from->pointtype == pt_tangent )
1030  if ( spt->selected && spt->next!=NULL && !spt->next->to->selected &&
1031  spt->next->to->pointtype == pt_tangent )
1033  if ( spt->prev!=NULL && spt->prevcpdef && tpt==tpt_OnlySelected )
1035  if ( spt->next==NULL )
1036  break;
1037  if ( spt->nextcpdef && tpt==tpt_OnlySelected )
1039  }
1040  }
1041  }
1042  first = NULL;
1043  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
1044  if ( !alldone ) SplineRefigureFixup(spline); else SplineRefigure(spline);
1045  if ( first==NULL ) first = spline;
1046  }
1047  }
1048 return( base );
1049 }
1050 
1052  enum transformPointType tpt )
1053 {
1054  enum transformPointMask tpmask = 0;
1055  return SplinePointListTransformExtended( base, transform, tpt, tpmask );
1056 }
1057 
1059  SplineChar *basesc,HintMask *hm) {
1060  StemInfo *st, *st2;
1061  int hst_cnt, bcnt;
1062  real start, width;
1063  int i;
1064 
1065  if ( ref->transform[1]!=0 || ref->transform[2]!=0 )
1066 return(NULL);
1067 
1068  memset(hm,0,sizeof(HintMask));
1069  for ( st = ref->sc->hstem; st!=NULL; st=st->next ) {
1070  start = st->start*ref->transform[3] + ref->transform[5] + trans->y;
1071  width = st->width*ref->transform[3];
1072  for ( st2=basesc->hstem,bcnt=0; st2!=NULL; st2=st2->next, bcnt++ )
1073  if ( st2->start == start && st2->width == width )
1074  break;
1075  if ( st2!=NULL )
1076  (*hm)[bcnt>>3] |= (0x80>>(bcnt&7));
1077  }
1078  for ( st2=basesc->hstem,hst_cnt=0; st2!=NULL; st2=st2->next, hst_cnt++ );
1079 
1080  for ( st = ref->sc->vstem; st!=NULL; st=st->next ) {
1081  start = st->start*ref->transform[0] + ref->transform[4] + trans->x;
1082  width = st->width*ref->transform[0];
1083  for ( st2=basesc->vstem,bcnt=hst_cnt; st2!=NULL; st2=st2->next, bcnt++ )
1084  if ( st2->start == start && st2->width == width )
1085  break;
1086  if ( st2!=NULL )
1087  (*hm)[bcnt>>3] |= (0x80>>(bcnt&7));
1088  }
1089  for ( i=0; i<HntMax/8; ++i )
1090  if ( (*hm)[i]!=0 )
1091 return( hm );
1092 
1093 return( NULL );
1094 }
1095 
1097  SplineChar *basesc,SplineChar *subsc) {
1098  HintMask *newhm;
1099  StemInfo *st, *st2;
1100  int cnt, hst_cnt, bcnt;
1101  real start, width;
1102 
1103  if ( transform[1]!=0 || transform[2]!=0 )
1104 return( NULL );
1105 
1106  newhm = chunkalloc(sizeof(HintMask));
1107  for ( st = subsc->hstem,cnt = 0; st!=NULL; st=st->next, cnt++ ) {
1108  if ( (*oldhm)[cnt>>3]&(0x80>>(cnt&7)) ) {
1109  start = st->start*transform[3] + transform[5];
1110  width = st->width*transform[3];
1111  for ( st2=basesc->hstem,bcnt=0; st2!=NULL; st2=st2->next, bcnt++ )
1112  if ( st2->start == start && st2->width == width )
1113  break;
1114  if ( st2!=NULL )
1115  (*newhm)[bcnt>>3] |= (0x80>>(bcnt&7));
1116  }
1117  }
1118  for ( st2=basesc->hstem,hst_cnt=0; st2!=NULL; st2=st2->next, hst_cnt++ );
1119 
1120  for ( st = subsc->vstem; st!=NULL; st=st->next, cnt++ ) {
1121  if ( (*oldhm)[cnt>>3]&(0x80>>(cnt&7)) ) {
1122  start = st->start*transform[0] + transform[4];
1123  width = st->width*transform[0];
1124  for ( st2=basesc->vstem,bcnt=hst_cnt; st2!=NULL; st2=st2->next, bcnt++ )
1125  if ( st2->start == start && st2->width == width )
1126  break;
1127  if ( st2!=NULL )
1128  (*newhm)[bcnt>>3] |= (0x80>>(bcnt&7));
1129  }
1130  }
1131 return( newhm );
1132 }
1133 
1135  SplineChar *basesc, SplineChar *subsc, BasePoint *trans ) {
1136  SplinePointList *spl, *spl2, *head;
1137  SplinePoint *spt, *spt2, *pfirst;
1138  real transform[6];
1139  Spline *s, *first;
1140 
1142 
1143  transform[0] = transform[3] = 1; transform[1] = transform[2] = 0;
1144  transform[4] = trans->x; transform[5] = trans->y;
1145 
1146  for ( spl = head, spl2=base; spl!=NULL; spl = spl->next, spl2 = spl2->next ) {
1147  pfirst = NULL;
1148  for ( spt = spl->first, spt2 = spl2->first ; spt!=pfirst; spt = spt->next->to, spt2 = spt2->next->to ) {
1149  if ( pfirst==NULL ) pfirst = spt;
1151  if ( spt2->hintmask ) {
1152  chunkfree(spt->hintmask,sizeof(HintMask));
1153  spt->hintmask = HintMaskTransform(spt2->hintmask,transform,basesc,subsc);
1154  }
1155  if ( spt->next==NULL )
1156  break;
1157  }
1158  first = NULL;
1159  for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
1160  SplineRefigure(s);
1161  if ( first==NULL ) first = s;
1162  }
1163  }
1164 return( head );
1165 }
1166 
1168  real transform[6], SplineChar *basesc ) {
1169  SplinePointList *spl, *spl2, *head, *last=NULL, *cur, *base;
1170  SplinePoint *spt, *spt2, *pfirst;
1171  Spline *s, *first;
1172  real trans[6];
1173  RefChar *rf;
1174 
1175  base = subsc->layers[layer].splines;
1177  if ( head!=NULL )
1178  for ( last = head; last->next!=NULL; last=last->next );
1179 
1180  for ( spl = head, spl2=base; spl!=NULL; spl = spl->next, spl2=spl2->next ) {
1181  pfirst = NULL;
1182  for ( spt = spl->first, spt2 = spl2->first ; spt!=pfirst; spt = spt->next->to, spt2 = spt2->next->to ) {
1183  if ( pfirst==NULL ) pfirst = spt;
1185  if ( spt2->hintmask ) {
1186  chunkfree(spt->hintmask,sizeof(HintMask));
1187  spt->hintmask = HintMaskTransform(spt2->hintmask,transform,basesc,subsc);
1188  }
1189  if ( spt->next==NULL )
1190  break;
1191  }
1192  first = NULL;
1193  for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
1194  SplineRefigure(s);
1195  if ( first==NULL ) first = s;
1196  }
1197  }
1198  for ( rf=subsc->layers[layer].refs; rf!=NULL; rf=rf->next ) {
1199  trans[0] = rf->transform[0]*transform[0] +
1200  rf->transform[1]*transform[2];
1201  trans[1] = rf->transform[0]*transform[1] +
1202  rf->transform[1]*transform[3];
1203  trans[2] = rf->transform[2]*transform[0] +
1204  rf->transform[3]*transform[2];
1205  trans[3] = rf->transform[2]*transform[1] +
1206  rf->transform[3]*transform[3];
1207  trans[4] = rf->transform[4]*transform[0] +
1208  rf->transform[5]*transform[2] +
1209  transform[4];
1210  trans[5] = rf->transform[4]*transform[1] +
1211  rf->transform[5]*transform[3] +
1212  transform[5];
1214  if ( head==NULL )
1215  head = cur;
1216  else
1217  last->next = cur;
1218  if ( cur!=NULL ) {
1219  while ( cur->next!=NULL ) cur = cur->next;
1220  last = cur;
1221  }
1222  }
1223 return( head );
1224 }
1225 
1227  SplineChar *basesc, BasePoint *trans,int layer ) {
1228  real transform[6];
1229 
1230  memcpy(transform,r->transform,sizeof(transform));
1231  transform[4] += trans->x; transform[5] += trans->y;
1232 return( _SPLCopyTransformedHintMasks(r->sc,layer,transform,basesc));
1233 }
1234 
1236  struct splinecharlist *dlist;
1237 
1238  if ( dependent->searcherdummy )
1239 return;
1240 
1241  for ( dlist=base->dependents; dlist!=NULL && dlist->sc!=dependent; dlist = dlist->next);
1242  if ( dlist==NULL ) {
1243  dlist = chunkalloc(sizeof(struct splinecharlist));
1244  dlist->sc = dependent;
1245  dlist->next = base->dependents;
1246  base->dependents = dlist;
1247  }
1248 }
1249 
1250 static void LayerToRefLayer(struct reflayer *rl,Layer *layer, real transform[6]) {
1251  BrushCopy(&rl->fill_brush, &layer->fill_brush,transform);
1252  PenCopy(&rl->stroke_pen, &layer->stroke_pen,transform);
1253  rl->dofill = layer->dofill;
1254  rl->dostroke = layer->dostroke;
1255  rl->fillfirst = layer->fillfirst;
1256 }
1257 
1259  // Note that most of the logic below is copied and lightly modified from SCReinstanciateRefChar.
1260  SplineChar *rsc = rf->sc;
1261  int i = 0, j = 0, cnt = 0;
1262  RefChar *subref;
1263  for ( i=ly_fore; i<rsc->layer_cnt; ++i ) {
1264  if ( rsc->layers[i].splines!=NULL) {
1265  if (cnt == layer) return i;
1266  ++cnt;
1267  }
1268  for ( subref=rsc->layers[i].refs; subref!=NULL; subref=subref->next ) {
1269  for ( j=0; j<subref->layer_cnt; ++j ) if ( subref->layers[j].splines!=NULL ) {
1270  if (cnt == layer) return i;
1271  ++cnt;
1272  }
1273  }
1274  }
1275  return -1;
1276 }
1277 
1279  int i;
1280  SplineChar *rsc = rf->sc;
1281  real extra=0,e;
1282 
1283  memset(&rf->bb,'\0',sizeof(rf->bb));
1284  rf->top.y = -1e10;
1285  for ( i=0; i<rf->layer_cnt; ++i ) {
1286  _SplineSetFindBounds(rf->layers[i].splines,&rf->bb);
1287  _SplineSetFindTop(rf->layers[i].splines,&rf->top);
1288  int baselayer = RefLayerFindBaseLayerIndex(rf, i);
1289  if ( baselayer >= 0 && rsc->layers[baselayer].dostroke ) {
1290  if ( rf->layers[i].stroke_pen.width!=WIDTH_INHERITED )
1291  e = rf->layers[i].stroke_pen.width*rf->layers[i].stroke_pen.trans[0];
1292  else
1293  e = rf->layers[i].stroke_pen.trans[0];
1294  if ( e>extra ) extra = e;
1295  }
1296  }
1297  if ( rf->top.y < -65536 ) rf->top.y = rf->top.x = 0;
1298  rf->bb.minx -= extra; rf->bb.miny -= extra;
1299  rf->bb.maxx += extra; rf->bb.maxy += extra;
1300 }
1301 
1303  SplinePointList *new, *last;
1304  RefChar *refs;
1305  int i,j;
1306  SplineChar *rsc = rf->sc;
1307  real extra=0,e;
1308 
1309  for ( i=0; i<rf->layer_cnt; ++i ) {
1311  GradientFree(rf->layers[i].fill_brush.gradient);
1312  PatternFree(rf->layers[i].fill_brush.pattern);
1313  GradientFree(rf->layers[i].stroke_pen.brush.gradient);
1314  PatternFree(rf->layers[i].stroke_pen.brush.pattern);
1315  }
1316  free( rf->layers );
1317  rf->layers = NULL;
1318  rf->layer_cnt = 0;
1319  if ( rsc==NULL )
1320 return;
1321  /* Can be called before sc->parent is set, but only when reading a ttf */
1322  /* file which won't be multilayer */
1323  if ( sc->parent!=NULL && sc->parent->multilayer ) {
1324  int cnt = 0;
1325  RefChar *subref;
1326  for ( i=ly_fore; i<rsc->layer_cnt; ++i ) {
1327  if ( rsc->layers[i].splines!=NULL)
1328  ++cnt;
1329  for ( subref=rsc->layers[i].refs; subref!=NULL; subref=subref->next )
1330  cnt += subref->layer_cnt;
1331  }
1332 
1333  rf->layer_cnt = cnt;
1334  rf->layers = calloc(cnt,sizeof(struct reflayer));
1335  cnt = 0;
1336  for ( i=ly_fore; i<rsc->layer_cnt; ++i ) {
1337  if ( rsc->layers[i].splines!=NULL ) {
1338  rf->layers[cnt].splines =
1341  LayerToRefLayer(&rf->layers[cnt],&rsc->layers[i],rf->transform);
1342  ++cnt;
1343  }
1344  for ( subref=rsc->layers[i].refs; subref!=NULL; subref=subref->next ) {
1345  for ( j=0; j<subref->layer_cnt; ++j ) if ( subref->layers[j].splines!=NULL ) {
1346  rf->layers[cnt] = subref->layers[j];
1347  rf->layers[cnt].splines =
1350  ++cnt;
1351  }
1352  }
1353  }
1354 
1355  memset(&rf->bb,'\0',sizeof(rf->bb));
1356  rf->top.y = -1e10;
1357  for ( i=0; i<rf->layer_cnt; ++i ) {
1358  _SplineSetFindBounds(rf->layers[i].splines,&rf->bb);
1359  _SplineSetFindTop(rf->layers[i].splines,&rf->top);
1360  int baselayer = RefLayerFindBaseLayerIndex(rf, i);
1361  if ( baselayer >= 0 && rsc->layers[baselayer].dostroke ) {
1362  if ( rf->layers[i].stroke_pen.width!=WIDTH_INHERITED )
1363  e = rf->layers[i].stroke_pen.width*rf->layers[i].stroke_pen.trans[0];
1364  else
1365  e = rf->layers[i].stroke_pen.trans[0];
1366  if ( e>extra ) extra = e;
1367  }
1368  }
1369  if ( rf->top.y < -65536 ) rf->top.y = rf->top.x = 0;
1370  rf->bb.minx -= extra; rf->bb.miny -= extra;
1371  rf->bb.maxx += extra; rf->bb.maxy += extra;
1372  } else {
1373  if ( rf->layer_cnt>0 ) {
1375  rf->layers[0].splines = NULL;
1376  }
1377  rf->layers = calloc(1,sizeof(struct reflayer));
1378  rf->layer_cnt = 1;
1379  rf->layers[0].dofill = true;
1381  rf->layers[0].splines = new;
1382  last = NULL;
1383  if ( new!=NULL )
1384  for ( last = new; last->next!=NULL; last = last->next );
1385  for ( refs = rf->sc->layers[layer].refs; refs!=NULL; refs = refs->next ) {
1387  if ( last!=NULL )
1388  last->next = new;
1389  else
1390  rf->layers[0].splines = new;
1391  if ( new!=NULL )
1392  for ( last = new; last->next!=NULL; last = last->next );
1393  }
1394  }
1395  RefCharFindBounds(rf);
1396 }
1397 
1398 /* This returns all real solutions, even those out of bounds */
1399 /* I use -999999 as an error flag, since we're really only interested in */
1400 /* solns near 0 and 1 that should be ok. -1 is perhaps a little too close */
1401 /* Sigh. When solutions are near 0, the rounding errors are appalling. */
1402 int _CubicSolve(const Spline1D *sp,bigreal sought, extended ts[3]) {
1403  extended d, xN, yN, delta2, temp, delta, h, t2, t3, theta;
1404  extended sa=sp->a, sb=sp->b, sc=sp->c, sd=sp->d-sought;
1405  int i=0;
1406 
1407  ts[0] = ts[1] = ts[2] = -999999;
1408  if ( sd==0 && sa!=0 ) {
1409  /* one of the roots is 0, the other two are the soln of a quadratic */
1410  ts[0] = 0;
1411  if ( sc==0 ) {
1412  ts[1] = -sb/(extended) sa; /* two zero roots */
1413  } else {
1414  temp = sb*(extended) sb-4*(extended) sa*sc;
1415  if ( RealNear(temp,0))
1416  ts[1] = -sb/(2*(extended) sa);
1417  else if ( temp>=0 ) {
1418  temp = sqrt(temp);
1419  ts[1] = (-sb+temp)/(2*(extended) sa);
1420  ts[2] = (-sb-temp)/(2*(extended) sa);
1421  }
1422  }
1423  } else if ( sa!=0 ) {
1424  /* http://www.m-a.org.uk/eb/mg/mg077ch.pdf */
1425  /* this nifty solution to the cubic neatly avoids complex arithmatic */
1426  xN = -sb/(3*(extended) sa);
1427  yN = ((sa*xN + sb)*xN+sc)*xN + sd;
1428 
1429  delta2 = (sb*(extended) sb-3*(extended) sa*sc)/(9*(extended) sa*sa);
1430  /*if ( RealWithin(delta2,0,.00000001) ) delta2 = 0;*/
1431 
1432  /* the descriminant is yN^2-h^2, but delta might be <0 so avoid using h */
1433  d = yN*yN - 4*sa*sa*delta2*delta2*delta2;
1434  if ( ((yN>.01 || yN<-.01) && RealNear(d/yN,0)) || ((yN<=.01 && yN>=-.01) && RealNear(d,0)) )
1435  d = 0;
1436  if ( d>0 ) {
1437  temp = sqrt(d);
1438  t2 = (-yN-temp)/(2*sa);
1439  t2 = (t2==0) ? 0 : (t2<0) ? -pow(-t2,1./3.) : pow(t2,1./3.);
1440  t3 = (-yN+temp)/(2*sa);
1441  t3 = t3==0 ? 0 : (t3<0) ? -pow(-t3,1./3.) : pow(t3,1./3.);
1442  ts[0] = xN + t2 + t3;
1443  } else if ( d<0 ) {
1444  if ( delta2>=0 ) {
1445  delta = sqrt(delta2);
1446  h = 2*sa*delta2*delta;
1447  temp = -yN/h;
1448  if ( temp>=-1.0001 && temp<=1.0001 ) {
1449  if ( temp<-1 ) temp = -1; else if ( temp>1 ) temp = 1;
1450  theta = acos(temp)/3;
1451  ts[i++] = xN+2*delta*cos(theta);
1452  ts[i++] = xN+2*delta*cos(2.0943951+theta); /* 2*pi/3 */
1453  ts[i++] = xN+2*delta*cos(4.1887902+theta); /* 4*pi/3 */
1454  }
1455  }
1456  } else if ( /* d==0 && */ delta2!=0 ) {
1457  delta = yN/(2*sa);
1458  delta = delta==0 ? 0 : delta>0 ? pow(delta,1./3.) : -pow(-delta,1./3.);
1459  ts[i++] = xN + delta; /* this root twice, but that's irrelevant to me */
1460  ts[i++] = xN - 2*delta;
1461  } else if ( /* d==0 && */ delta2==0 ) {
1462  if ( xN>=-0.0001 && xN<=1.0001 ) ts[0] = xN;
1463  }
1464  } else if ( sb!=0 ) {
1465  extended d = sc*(extended) sc-4*(extended) sb*sd;
1466  if ( d<0 && RealNear(d,0)) d=0;
1467  if ( d<0 )
1468 return(false); /* All roots imaginary */
1469  d = sqrt(d);
1470  ts[0] = (-sc-d)/(2*(extended) sb);
1471  ts[1] = (-sc+d)/(2*(extended) sb);
1472  } else if ( sc!=0 ) {
1473  ts[0] = -sd/(extended) sc;
1474  } else {
1475  /* If it's a point then either everything is a solution, or nothing */
1476  }
1477 return( ts[0]!=-999999 );
1478 }
1479 
1480 int CubicSolve(const Spline1D *sp,bigreal sought, extended ts[3]) {
1481  extended t;
1482  extended ts2[3];
1483  int i,j;
1484  /* This routine gives us all solutions between [0,1] with -1 as an error flag */
1485  /* http://mathforum.org/dr.math/faq/faq.cubic.equations.html */
1486 
1487  ts[0] = ts[1] = ts[2] = -1;
1488  if ( !_CubicSolve(sp,sought,ts2)) {
1489 return( false );
1490  }
1491 
1492  for ( i=j=0; i<3; ++i ) {
1493  if ( ts2[i]>-.0001 && ts2[i]<1.0001 ) {
1494  if ( ts2[i]<0 ) ts[j++] = 0;
1495  else if ( ts2[i]>1 ) ts[j++] = 1;
1496  else
1497  ts[j++] = ts2[i];
1498  }
1499  }
1500  if ( j==0 )
1501 return( false );
1502 
1503  if ( ts[0]>ts[2] && ts[2]!=-1 ) {
1504  t = ts[0]; ts[0] = ts[2]; ts[2] = t;
1505  }
1506  if ( ts[0]>ts[1] && ts[1]!=-1 ) {
1507  t = ts[0]; ts[0] = ts[1]; ts[1] = t;
1508  }
1509  if ( ts[1]>ts[2] && ts[2]!=-1 ) {
1510  t = ts[1]; ts[1] = ts[2]; ts[2] = t;
1511  }
1512 return( true );
1513 }
1514 
1515 /* An IEEE double has 52 bits of precision. So one unit of rounding error will be */
1516 /* the number divided by 2^51 */
1517 # define D_RE_Factor (1024.0*1024.0*1024.0*1024.0*1024.0*2.0)
1518 /* But that's not going to work near 0, so, since the t values we care about */
1519 /* are [0,1], let's use 1.0/D_RE_Factor */
1520 
1522  extended sought) {
1523  extended t, low, high, test;
1524  Spline1D temp;
1525  /* Now the closed form CubicSolver can have rounding errors so if we know */
1526  /* the spline to be monotonic, an iterative approach is more accurate */
1527 
1528  if ( tmin>tmax ) {
1529  t=tmin; tmin=tmax; tmax=t;
1530  }
1531 
1532  temp = *sp;
1533  temp.d -= sought;
1534 
1535  if ( temp.a==0 && temp.b==0 && temp.c!=0 ) {
1536  t = -temp.d/(extended) temp.c;
1537  if ( t<tmin || t>tmax )
1538 return( -1 );
1539 return( t );
1540  }
1541 
1542  low = ((temp.a*tmin+temp.b)*tmin+temp.c)*tmin+temp.d;
1543  high = ((temp.a*tmax+temp.b)*tmax+temp.c)*tmax+temp.d;
1544  if ( low==0 )
1545 return(tmin);
1546  if ( high==0 )
1547 return(tmax);
1548  if (( low<0 && high>0 ) ||
1549  ( low>0 && high<0 )) {
1550 
1551  for (;;) {
1552  t = (tmax+tmin)/2;
1553  if ( t==tmax || t==tmin )
1554 return( t );
1555  test = ((temp.a*t+temp.b)*t+temp.c)*t+temp.d;
1556  if ( test==0 ) /* someone complained that this test relied on exact arithmetic. In fact this test will almost never be hit, the real exit test is the line above, when tmin/tmax are so close that there is no space between them in the floating representation */
1557 return( t );
1558  if ( (low<0 && test<0) || (low>0 && test>0) )
1559  tmin=t;
1560  else
1561  tmax = t;
1562  }
1563  } else if ( low<.0001 && low>-.0001 )
1564 return( tmin ); /* Rounding errors */
1565  else if ( high<.0001 && high>-.0001 )
1566 return( tmax );
1567 
1568 return( -1 );
1569 }
1570 
1572  extended sought) {
1573  // Search between tmin and tmax for a t-value at which the spline outputs sought.
1574  extended t;
1575  bigreal factor;
1576  extended val, valp, valm;
1577 
1578  if ( tmin>tmax ) {
1579  t=tmin; tmin=tmax; tmax=t;
1580  }
1581 
1582  t = IterateSplineSolve(sp,tmin,tmax,sought);
1583 
1584  if ( t==-1 )
1585 return( -1 );
1586 
1587  if ((val = (((sp->a*t+sp->b)*t+sp->c)*t+sp->d) - sought)<0 )
1588  val=-val;
1589  if ( val!=0 ) {
1590  for ( factor=1024.0*1024.0*1024.0*1024.0*1024.0; factor>.5; factor/=2.0 ) {
1591  extended tp = t + (factor*t)/D_RE_Factor;
1592  extended tm = t - (factor*t)/D_RE_Factor;
1593  if ( tp>tmax ) tp=tmax;
1594  if ( tm<tmin ) tm=tmin;
1595  if ( (valp = (((sp->a*tp+sp->b)*tp+sp->c)*tp+sp->d) - sought)<0 )
1596  valp = -valp;
1597  if ( (valm = (((sp->a*tm+sp->b)*tm+sp->c)*tm+sp->d) - sought)<0 )
1598  valm = -valm;
1599  if ( valp<val && valp<valm ) {
1600  t = tp;
1601  val = valp;
1602  } else if ( valm<val ) {
1603  t = tm;
1604  val = valm;
1605  }
1606  }
1607  }
1608  if ( t==0 && !Within16RoundingErrors(sought,sought+val))
1609 return( -1 );
1610  /* if t!=0 then we we get the chance of far worse rounding errors */
1611  else if ( t==tmax || t==tmin ) {
1612  if ( Within16RoundingErrors(sought,sought+val) ||
1613  Within16RoundingErrors(sp->a,sp->a+val) ||
1614  Within16RoundingErrors(sp->b,sp->b+val) ||
1615  Within16RoundingErrors(sp->c,sp->c+val) ||
1616  Within16RoundingErrors(sp->c,sp->c+val) ||
1618 return( t );
1619  else
1620 return( -1 );
1621  }
1622 
1623  if ( t>=tmin && t<=tmax )
1624 return( t );
1625 
1626  /* I don't think this can happen... */
1627 return( -1 );
1628 }
1629 
1630 double CheckExtremaForSingleBitErrors(const Spline1D *sp, double t, double othert) {
1631  double u1, um1;
1632  double slope, slope1, slopem1;
1633  int err;
1634  double diff, factor;
1635 
1636  if ( t<0 || t>1 )
1637 return( t );
1638 
1639  factor = t*0x40000/D_RE_Factor;
1640  if ( (diff = t-othert)<0 ) diff= -diff;
1641  if ( factor>diff/4 && diff!=0 ) /* This little check is to insure we don't skip beyond the well of this extremum into the next */
1642  factor = diff/4;
1643 
1644  slope = (3*(double) sp->a*t+2*sp->b)*t+sp->c;
1645  if ( slope<0 ) slope = -slope;
1646 
1647  for ( err = 0x40000; err!=0; err>>=1 ) {
1648  u1 = t+factor;
1649  slope1 = (3*(double) sp->a*u1+2*sp->b)*u1+sp->c;
1650  if ( slope1<0 ) slope1 = -slope1;
1651 
1652  um1 = t-factor;
1653  slopem1 = (3*(double) sp->a*um1+2*sp->b)*um1+sp->c;
1654  if ( slopem1<0 ) slopem1 = -slopem1;
1655 
1656  if ( slope1<slope && slope1<=slopem1 && u1<=1.0 ) {
1657  t = u1;
1658  } else if ( slopem1<slope && slopem1<=slope1 && um1>=0.0 ) {
1659  t = um1;
1660  }
1661  factor /= 2.0;
1662  }
1663  /* that seems as good as it gets */
1664 
1665 return( t );
1666 }
1667 
1668 void SplineFindExtrema(const Spline1D *sp, extended *_t1, extended *_t2 ) {
1669  extended t1= -1, t2= -1;
1670  extended b2_fourac;
1671 
1672  /* Find the extreme points on the curve */
1673  /* Set to -1 if there are none or if they are outside the range [0,1] */
1674  /* Order them so that t1<t2 */
1675  /* If only one valid extremum it will be t1 */
1676  /* (Does not check the end points unless they have derivative==0) */
1677  /* (Does not check to see if d/dt==0 points are inflection points (rather than extrema) */
1678  if ( sp->a!=0 ) {
1679  /* cubic, possibly 2 extrema (possibly none) */
1680  b2_fourac = 4*(extended) sp->b*sp->b - 12*(extended) sp->a*sp->c;
1681  if ( b2_fourac>=0 ) {
1682  b2_fourac = sqrt(b2_fourac);
1683  t1 = (-2*sp->b - b2_fourac) / (6*sp->a);
1684  t2 = (-2*sp->b + b2_fourac) / (6*sp->a);
1687  if ( t1>t2 ) { extended temp = t1; t1 = t2; t2 = temp; }
1688  else if ( t1==t2 ) t2 = -1;
1689  if ( RealNear(t1,0)) t1=0; else if ( RealNear(t1,1)) t1=1;
1690  if ( RealNear(t2,0)) t2=0; else if ( RealNear(t2,1)) t2=1;
1691  if ( t2<=0 || t2>=1 ) t2 = -1;
1692  if ( t1<=0 || t1>=1 ) { t1 = t2; t2 = -1; }
1693  }
1694  } else if ( sp->b!=0 ) {
1695  /* Quadratic, at most one extremum */
1696  t1 = -sp->c/(2.0*(extended) sp->b);
1697  if ( t1<=0 || t1>=1 ) t1 = -1;
1698  } else /*if ( sp->c!=0 )*/ {
1699  /* linear, no extrema */
1700  }
1701  *_t1 = t1; *_t2 = t2;
1702 }
1703 
1705  /* Kappa = (x'y'' - y'x'') / (x'^2 + y'^2)^(3/2) */
1706  bigreal dxdt, dydt, d2xdt2, d2ydt2, denom, numer;
1707 
1708  if ( s==NULL )
1709 return( CURVATURE_ERROR );
1710 
1711  dxdt = (3*s->splines[0].a*t+2*s->splines[0].b)*t+s->splines[0].c;
1712  dydt = (3*s->splines[1].a*t+2*s->splines[1].b)*t+s->splines[1].c;
1713  d2xdt2 = 6*s->splines[0].a*t + 2*s->splines[0].b;
1714  d2ydt2 = 6*s->splines[1].a*t + 2*s->splines[1].b;
1715  denom = pow( dxdt*dxdt + dydt*dydt, 3.0/2.0 );
1716  numer = dxdt*d2ydt2 - dydt*d2xdt2;
1717 
1718  if ( numer==0 )
1719 return( 0 );
1720  if ( denom==0 )
1721 return( CURVATURE_ERROR );
1722 
1723 return( numer/denom );
1724 }
1725 
1726 int Spline2DFindExtrema(const Spline *sp, extended extrema[4] ) {
1727  int i,j;
1728  BasePoint last, cur, mid;
1729 
1730  /* If the control points are at the end-points then this (1D) spline is */
1731  /* basically a line. But rounding errors can give us very faint extrema */
1732  /* if we look for them */
1733  if ( !Spline1DCantExtremeX(sp) )
1734  SplineFindExtrema(&sp->splines[0],&extrema[0],&extrema[1]);
1735  else
1736  extrema[0] = extrema[1] = -1;
1737  if ( !Spline1DCantExtremeY(sp) )
1738  SplineFindExtrema(&sp->splines[1],&extrema[2],&extrema[3]);
1739  else
1740  extrema[2] = extrema[3] = -1;
1741 
1742  for ( i=0; i<3; ++i ) for ( j=i+1; j<4; ++j ) {
1743  if ( (extrema[i]==-1 && extrema[j]!=-1) || (extrema[i]>extrema[j] && extrema[j]!=-1) ) {
1744  extended temp = extrema[i];
1745  extrema[i] = extrema[j];
1746  extrema[j] = temp;
1747  }
1748  }
1749  for ( i=j=0; i<3 && extrema[i]!=-1; ++i ) {
1750  if ( extrema[i]==extrema[i+1] ) {
1751  for ( j=i+1; j<3; ++j )
1752  extrema[j] = extrema[j+1];
1753  extrema[3] = -1;
1754  }
1755  }
1756 
1757  /* Extrema which are too close together are not interesting */
1758  last = sp->from->me;
1759  for ( i=0; i<4 && extrema[i]!=-1; ++i ) {
1760  cur.x = ((sp->splines[0].a*extrema[i]+sp->splines[0].b)*extrema[i]+
1761  sp->splines[0].c)*extrema[i]+sp->splines[0].d;
1762  cur.y = ((sp->splines[1].a*extrema[i]+sp->splines[1].b)*extrema[i]+
1763  sp->splines[1].c)*extrema[i]+sp->splines[1].d;
1764  mid.x = (last.x+cur.x)/2; mid.y = (last.y+cur.y)/2;
1765  if ( (mid.x==last.x || mid.x==cur.x) &&
1766  (mid.y==last.y || mid.y==cur.y)) {
1767  for ( j=i; j<3; ++j )
1768  extrema[j] = extrema[j+1];
1769  extrema[3] = -1;
1770  --i;
1771  } else
1772  last = cur;
1773  }
1774  if ( extrema[0]!=-1 ) {
1775  mid.x = (last.x+sp->to->me.x)/2; mid.y = (last.y+sp->to->me.y)/2;
1776  if ( (mid.x==last.x || mid.x==cur.x) &&
1777  (mid.y==last.y || mid.y==cur.y))
1778  extrema[i-1] = -1;
1779  }
1780  for ( i=0; i<4 && extrema[i]!=-1; ++i );
1781  if ( i!=0 ) {
1782  cur = sp->to->me;
1783  mid.x = (last.x+cur.x)/2; mid.y = (last.y+cur.y)/2;
1784  if ( (mid.x==last.x || mid.x==cur.x) &&
1785  (mid.y==last.y || mid.y==cur.y))
1786  extrema[--i] = -1;
1787  }
1788 
1789 return( i );
1790 }
1791 
1793  int cnt=0;
1794  extended a, b, c, b2_fourac, t;
1795  /* A POI happens when d2 y/dx2 is zero. This is not the same as d2y/dt2 / d2x/dt2 */
1796  /* d2 y/dx^2 = d/dt ( dy/dt / dx/dt ) / dx/dt */
1797  /* = ( (dx/dt) * d2 y/dt2 - ((dy/dt) * d2 x/dt2) )/ (dx/dt)^3 */
1798  /* (3ax*t^2+2bx*t+cx) * (6ay*t+2by) - (3ay*t^2+2by*t+cy) * (6ax*t+2bx) == 0 */
1799  /* (3ax*t^2+2bx*t+cx) * (3ay*t+by) - (3ay*t^2+2by*t+cy) * (3ax*t+bx) == 0 */
1800  /* 9*ax*ay*t^3 + (3ax*by+6bx*ay)*t^2 + (2bx*by+3cx*ay)*t + cx*by */
1801  /* -(9*ax*ay*t^3 + (3ay*bx+6by*ax)*t^2 + (2by*bx+3cy*ax)*t + cy*bx)==0 */
1802  /* 3*(ax*by-ay*bx)*t^2 + 3*(cx*ay-cy*ax)*t+ (cx*by-cy*bx) == 0 */
1803 
1804  a = 3*((extended) sp->splines[1].a*sp->splines[0].b-(extended) sp->splines[0].a*sp->splines[1].b);
1805  b = 3*((extended) sp->splines[0].c*sp->splines[1].a - (extended) sp->splines[1].c*sp->splines[0].a);
1806  c = (extended) sp->splines[0].c*sp->splines[1].b-(extended) sp->splines[1].c*sp->splines[0].b;
1807  if ( !RealNear(a,0) ) {
1808  b2_fourac = b*b - 4*a*c;
1809  poi[0] = poi[1] = -1;
1810  if ( b2_fourac<0 )
1811 return( 0 );
1812  b2_fourac = sqrt( b2_fourac );
1813  t = (-b+b2_fourac)/(2*a);
1814  if ( t>=0 && t<=1.0 )
1815  poi[cnt++] = t;
1816  t = (-b-b2_fourac)/(2*a);
1817  if ( t>=0 && t<=1.0 ) {
1818  if ( cnt==1 && poi[0]>t ) {
1819  poi[1] = poi[0];
1820  poi[0] = t;
1821  ++cnt;
1822  } else
1823  poi[cnt++] = t;
1824  }
1825  } else if ( !RealNear(b,0) ) {
1826  t = -c/b;
1827  if ( t>=0 && t<=1.0 )
1828  poi[cnt++] = t;
1829  }
1830  if ( cnt<2 )
1831  poi[cnt] = -1;
1832 
1833 return( cnt );
1834 }
1835 
1836 /* Ok, if the above routine finds an extremum that less than 1 unit */
1837 /* from an endpoint or another extremum, then many things are */
1838 /* just going to skip over it, and other things will be confused by this */
1839 /* so just remove it. It should be so close the difference won't matter */
1841  extended last, test;
1842  extended t1= *_t1, t2 = *_t2;
1843 
1844  if ( t1>t2 && t2!=-1 ) {
1845  t1 = t2;
1846  t2 = *_t1;
1847  }
1848  last = sp->d;
1849  if ( t1!=-1 ) {
1850  test = ((sp->a*t1+sp->b)*t1+sp->c)*t1+sp->d;
1851  if ( (test-last)*(test-last)<1 )
1852  t1 = -1;
1853  else
1854  last = test;
1855  }
1856  if ( t2!=-1 ) {
1857  test = ((sp->a*t2+sp->b)*t2+sp->c)*t2+sp->d;
1858  if ( (test-last)*(test-last)<1 )
1859  t2 = -1;
1860  else
1861  last = test;
1862  }
1863  test = sp->a+sp->b+sp->c+sp->d;
1864  if ( (test-last)*(test-last)<1 ) {
1865  if ( t2!=-1 )
1866  t2 = -1;
1867  else if ( t1!=-1 )
1868  t1 = -1;
1869  else {
1870  /* Well we should just remove the whole spline? */
1871  ;
1872  }
1873  }
1874  *_t1 = t1; *_t2 = t2;
1875 }
1876 
1878  BasePoint *line1_1, BasePoint *line1_2,
1879  BasePoint *line2_1, BasePoint *line2_2) {
1880  // A lot of functions call this with the same address as an input and the output.
1881  // In order to avoid unexpected behavior, we delay writing to the output until the end.
1882  bigreal s1, s2;
1883  BasePoint _output;
1884  BasePoint * output = &_output;
1885  if ( line1_1->x == line1_2->x ) {
1886  // Line 1 is vertical.
1887  output->x = line1_1->x;
1888  if ( line2_1->x == line2_2->x ) {
1889  // Line 2 is vertical.
1890  if ( line2_1->x!=line1_1->x )
1891  return( false ); /* Parallel vertical lines */
1892  output->y = (line1_1->y+line2_1->y)/2;
1893  } else {
1894  output->y = line2_1->y + (output->x-line2_1->x) * (line2_2->y - line2_1->y)/(line2_2->x - line2_1->x);
1895  }
1896  *inter = *output;
1897  return( true );
1898  } else if ( line2_1->x == line2_2->x ) {
1899  // Line 2 is vertical, but we know that line 1 is not.
1900  output->x = line2_1->x;
1901  output->y = line1_1->y + (output->x-line1_1->x) * (line1_2->y - line1_1->y)/(line1_2->x - line1_1->x);
1902  *inter = *output;
1903  return( true );
1904  } else {
1905  // Both lines are oblique.
1906  s1 = (line1_2->y - line1_1->y)/(line1_2->x - line1_1->x);
1907  s2 = (line2_2->y - line2_1->y)/(line2_2->x - line2_1->x);
1908  if ( RealNear(s1,s2)) {
1909  if ( !RealNear(line1_1->y + (line2_1->x-line1_1->x) * s1,line2_1->y))
1910  return( false );
1911  output->x = (line1_2->x+line2_2->x)/2;
1912  output->y = (line1_2->y+line2_2->y)/2;
1913  } else {
1914  output->x = (s1*line1_1->x - s2*line2_1->x - line1_1->y + line2_1->y)/(s1-s2);
1915  output->y = line1_1->y + (output->x-line1_1->x) * s1;
1916  }
1917  *inter = *output;
1918  return( true );
1919  }
1920 }
1921 
1923  BasePoint *line1_1, BasePoint *line1_2,
1924  BasePoint *line2_1, BasePoint *line2_2) {
1925  BasePoint old = *inter, unit;
1926  bigreal len, val;
1927 
1928  if ( !IntersectLines(inter,line1_1,line1_2,line2_1,line2_2))
1929 return( false );
1930  else {
1931  unit.x = line2_2->x-line1_2->x;
1932  unit.y = line2_2->y-line1_2->y;
1933  len = sqrt(unit.x*unit.x + unit.y*unit.y);
1934  if ( len==0 )
1935 return( false );
1936  else {
1937  unit.x /= len; unit.y /= len;
1938  val = unit.x*(inter->x-line1_2->x) + unit.y*(inter->y-line1_2->y);
1939  if ( val<=0 || val>=len ) {
1940  *inter = old;
1941 return( false );
1942  }
1943  }
1944  }
1945 return( true );
1946 }
1947 
1949  extended t1s[3],extended t2s[3], int soln) {
1950  int i;
1951 
1952  for ( i=0; i<soln; ++i )
1953  if ( x==pts[i].x && y==pts[i].y )
1954 return( soln );
1955  if ( soln>=9 )
1956  IError( "Too many solutions!\n" );
1957  t1s[soln] = t;
1958  t2s[soln] = s;
1959  pts[soln].x = x;
1960  pts[soln].y = y;
1961 return( soln+1 );
1962 }
1963 
1964 static void IterateSolve(const Spline1D *sp,extended ts[3]) {
1965  /* The closed form solution has too many rounding errors for my taste... */
1966  int i,j;
1967 
1968  ts[0] = ts[1] = ts[2] = -1;
1969 
1970  if ( sp->a!=0 ) {
1971  extended e[4];
1972  e[0] = 0; e[1] = e[2] = e[3] = 1.0;
1973  SplineFindExtrema(sp,&e[1],&e[2]);
1974  if ( e[1]==-1 ) e[1] = 1;
1975  if ( e[2]==-1 ) e[2] = 1;
1976  for ( i=j=0; i<3; ++i ) {
1977  ts[j] = IterateSplineSolve(sp,e[i],e[i+1],0);
1978  if ( ts[j]!=-1 ) ++j;
1979  if ( e[i+1]==1.0 )
1980  break;
1981  }
1982  } else if ( sp->b!=0 ) {
1983  extended b2_4ac = sp->c*(extended) sp->c - 4*sp->b*(extended) sp->d;
1984  if ( b2_4ac>=0 ) {
1985  b2_4ac = sqrt(b2_4ac);
1986  ts[0] = (-sp->c-b2_4ac)/(2*sp->b);
1987  ts[1] = (-sp->c+b2_4ac)/(2*sp->b);
1988  if ( ts[0]>ts[1] ) { bigreal t = ts[0]; ts[0] = ts[1]; ts[1] = t; }
1989  }
1990  } else if ( sp->c!=0 ) {
1991  ts[0] = -sp->d/(extended) sp->c;
1992  } else {
1993  /* No solutions, or all solutions */
1994  ;
1995  }
1996 
1997  for ( i=j=0; i<3; ++i )
1998  if ( ts[i]>=0 && ts[i]<=1 )
1999  ts[j++] = ts[i];
2000  for ( i=0; i<j-1; ++i )
2001  if ( ts[i]+.0000001>ts[i+1]) {
2002  ts[i] = (ts[i]+ts[i+1])/2;
2003  --j;
2004  for ( ++i; i<j; ++i )
2005  ts[i] = ts[i+1];
2006  }
2007  if ( j!=0 ) {
2008  if ( ts[0]!=0 ) {
2009  extended d0 = sp->d;
2010  extended dt = ((sp->a*ts[0]+sp->b)*ts[0]+sp->c)*ts[0]+sp->d;
2011  if ( d0<0 ) d0=-d0;
2012  if ( dt<0 ) dt=-dt;
2013  if ( d0<dt )
2014  ts[0] = 0;
2015  }
2016  if ( ts[j-1]!=1.0 ) {
2017  extended d1 = sp->a+(extended) sp->b+sp->c+sp->d;
2018  extended dt = ((sp->a*ts[j-1]+sp->b)*ts[j-1]+sp->c)*ts[j-1]+sp->d;
2019  if ( d1<0 ) d1=-d1;
2020  if ( dt<0 ) dt=-dt;
2021  if ( d1<dt )
2022  ts[j-1] = 1;
2023  }
2024  }
2025  for ( ; j<3; ++j )
2026  ts[j] = -1;
2027 }
2028 
2030  extended val,extended tlow, extended thigh) {
2031  Spline1D temp;
2032  extended ts[3];
2033  const Spline1D *sp = &spline->splines[major];
2034  int i;
2035 
2036  /* Calculation for t=1 can yield rounding errors. Insist on the endpoints */
2037  /* (the Spline1D is not a perfectly accurate description of the spline, */
2038  /* but the control points are right -- at least that's my defn.) */
2039  if ( tlow==0 && val==(&spline->from->me.x)[major] )
2040 return( 0 );
2041  if ( thigh==1.0 && val==(&spline->to->me.x)[major] )
2042 return( 1.0 );
2043 
2044  temp = *sp;
2045  temp.d -= val;
2046  IterateSolve(&temp,ts);
2047  if ( tlow<thigh ) {
2048  for ( i=0; i<3; ++i )
2049  if ( ts[i]>=tlow && ts[i]<=thigh )
2050 return( ts[i] );
2051  for ( i=0; i<3; ++i ) {
2052  if ( ts[i]>=tlow-1./1024. && ts[i]<=tlow )
2053 return( tlow );
2054  if ( ts[i]>=thigh && ts[i]<=thigh+1./1024 )
2055 return( thigh );
2056  }
2057  } else {
2058  for ( i=0; i<3; ++i )
2059  if ( ts[i]>=thigh && ts[i]<=tlow )
2060 return( ts[i] );
2061  for ( i=0; i<3; ++i ) {
2062  if ( ts[i]>=thigh-1./1024. && ts[i]<=thigh )
2063 return( thigh );
2064  if ( ts[i]>=tlow && ts[i]<=tlow+1./1024 )
2065 return( tlow );
2066  }
2067  }
2068 return( -1 );
2069 }
2070 
2071 static int ICAddInter(int cnt,BasePoint *foundpos,extended *foundt1,extended *foundt2,
2072  const Spline *s1,const Spline *s2,extended t1,extended t2, int maxcnt) {
2073 
2074  if ( cnt>=maxcnt )
2075 return( cnt );
2076 
2077  foundt1[cnt] = t1;
2078  foundt2[cnt] = t2;
2079  foundpos[cnt].x = ((s1->splines[0].a*t1+s1->splines[0].b)*t1+
2080  s1->splines[0].c)*t1+s1->splines[0].d;
2081  foundpos[cnt].y = ((s1->splines[1].a*t1+s1->splines[1].b)*t1+
2082  s1->splines[1].c)*t1+s1->splines[1].d;
2083 return( cnt+1 );
2084 }
2085 
2086 static int ICBinarySearch(int cnt,BasePoint *foundpos,extended *foundt1,extended *foundt2,
2087  int other,
2088  const Spline *s1,const Spline *s2,extended t1low,extended t1high,extended t2low,extended t2high,
2089  int maxcnt) {
2090  int major;
2091  extended t1, t2;
2092  extended o1o, o2o, o1n, o2n, m;
2093 
2094  major = !other;
2095  o1o = ((s1->splines[other].a*t1low+s1->splines[other].b)*t1low+
2096  s1->splines[other].c)*t1low+s1->splines[other].d;
2097  o2o = ((s2->splines[other].a*t2low+s2->splines[other].b)*t2low+
2098  s2->splines[other].c)*t2low+s2->splines[other].d;
2099  for (;;) {
2100  t1 = (t1low+t1high)/2;
2101  m = ((s1->splines[major].a*t1+s1->splines[major].b)*t1+
2102  s1->splines[major].c)*t1+s1->splines[major].d;
2103  t2 = ISolveWithin(s2,major,m,t2low,t2high);
2104  if ( t2==-1 )
2105 return( cnt );
2106 
2107  o1n = ((s1->splines[other].a*t1+s1->splines[other].b)*t1+
2108  s1->splines[other].c)*t1+s1->splines[other].d;
2109  o2n = ((s2->splines[other].a*t2+s2->splines[other].b)*t2+
2110  s2->splines[other].c)*t2+s2->splines[other].d;
2111  if (( o1n-o2n<.001 && o1n-o2n>-.001) ||
2112  (t1-t1low<.0001 && t1-t1low>-.0001))
2113 return( ICAddInter(cnt,foundpos,foundt1,foundt2,s1,s2,t1,t2,maxcnt));
2114  if ( (o1o>o2o && o1n<o2n) || (o1o<o2o && o1n>o2n)) {
2115  t1high = t1;
2116  t2high = t2;
2117  } else {
2118  t1low = t1;
2119  t2low = t2;
2120  }
2121  }
2122 }
2123 
2124 static int CubicsIntersect(const Spline *s1,extended lowt1,extended hight1,BasePoint *min1,BasePoint *max1,
2125  const Spline *s2,extended lowt2,extended hight2,BasePoint *min2,BasePoint *max2,
2126  BasePoint *foundpos,extended *foundt1,extended *foundt2,
2127  int maxcnt) {
2128  int major, other;
2129  BasePoint max, min;
2130  extended t1max, t1min, t2max, t2min, t1, t2, t1diff, oldt2;
2131  extended o1o, o2o, o1n, o2n, m;
2132  int cnt=0;
2133 
2134  if ( (min.x = min1->x)<min2->x ) min.x = min2->x;
2135  if ( (min.y = min1->y)<min2->y ) min.y = min2->y;
2136  if ( (max.x = max1->x)>max2->x ) max.x = max2->x;
2137  if ( (max.y = max1->y)>max2->y ) max.y = max2->y;
2138  if ( max.x<min.x || max.y<min.y )
2139 return( 0 );
2140  if ( max.x-min.x > max.y-min.y )
2141  major = 0;
2142  else
2143  major = 1;
2144  other = 1-major;
2145 
2146  t1max = ISolveWithin(s1,major,(&max.x)[major],lowt1,hight1);
2147  t1min = ISolveWithin(s1,major,(&min.x)[major],lowt1,hight1);
2148  t2max = ISolveWithin(s2,major,(&max.x)[major],lowt2,hight2);
2149  t2min = ISolveWithin(s2,major,(&min.x)[major],lowt2,hight2);
2150  if ( t1max==-1 || t1min==-1 || t2max==-1 || t2min==-1 )
2151 return( 0 );
2152  t1diff = (t1max-t1min)/64.0;
2153  if (RealNear(t1diff,0))
2154 return( 0 );
2155 
2156  t1 = t1min; t2 = t2min;
2157  o1o = t1==0 ? (&s1->from->me.x)[other] :
2158  t1==1.0 ? (&s1->to->me.x)[other] :
2159  ((s1->splines[other].a*t1+s1->splines[other].b)*t1+
2160  s1->splines[other].c)*t1+s1->splines[other].d;
2161  o2o = t2==0 ? (&s2->from->me.x)[other] :
2162  t2==1.0 ? (&s2->to->me.x)[other] :
2163  ((s2->splines[other].a*t2+s2->splines[other].b)*t2+
2164  s2->splines[other].c)*t2+s2->splines[other].d;
2165  if ( o1o==o2o )
2166  cnt = ICAddInter(cnt,foundpos,foundt1,foundt2,s1,s2,t1,t2,maxcnt);
2167  for (;;) {
2168  if ( cnt>=maxcnt )
2169  break;
2170  t1 += t1diff;
2171  if (( t1max>t1min && t1>t1max ) || (t1max<t1min && t1<t1max) || cnt>3 )
2172  break;
2173  m = t1==0 ? (&s1->from->me.x)[major] :
2174  t1==1.0 ? (&s1->to->me.x)[major] :
2175  ((s1->splines[major].a*t1+s1->splines[major].b)*t1+
2176  s1->splines[major].c)*t1+s1->splines[major].d;
2177  oldt2 = t2;
2178  t2 = ISolveWithin(s2,major,m,lowt2,hight2);
2179  if ( t2==-1 )
2180  continue;
2181 
2182  o1n = t1==0 ? (&s1->from->me.x)[other] :
2183  t1==1.0 ? (&s1->to->me.x)[other] :
2184  ((s1->splines[other].a*t1+s1->splines[other].b)*t1+
2185  s1->splines[other].c)*t1+s1->splines[other].d;
2186  o2n = t2==0 ? (&s2->from->me.x)[other] :
2187  t2==1.0 ? (&s2->to->me.x)[other] :
2188  ((s2->splines[other].a*t2+s2->splines[other].b)*t2+
2189  s2->splines[other].c)*t2+s2->splines[other].d;
2190  if ( o1n==o2n )
2191  cnt = ICAddInter(cnt,foundpos,foundt1,foundt2,s1,s2,t1,t2,maxcnt);
2192  if ( (o1o>o2o && o1n<o2n) || (o1o<o2o && o1n>o2n))
2193  cnt = ICBinarySearch(cnt,foundpos,foundt1,foundt2,other,
2194  s1,s2,t1-t1diff,t1,oldt2,t2,maxcnt);
2195  o1o = o1n; o2o = o2n;
2196  }
2197 return( cnt );
2198 }
2199 
2200 static int Closer(const Spline *s1,const Spline *s2,extended t1,extended t2,extended t1p,extended t2p) {
2201  bigreal x1 = ((s1->splines[0].a*t1+s1->splines[0].b)*t1+s1->splines[0].c)*t1+s1->splines[0].d;
2202  bigreal y1 = ((s1->splines[1].a*t1+s1->splines[1].b)*t1+s1->splines[1].c)*t1+s1->splines[1].d;
2203  bigreal x2 = ((s2->splines[0].a*t2+s2->splines[0].b)*t2+s2->splines[0].c)*t2+s2->splines[0].d;
2204  bigreal y2 = ((s2->splines[1].a*t2+s2->splines[1].b)*t2+s2->splines[1].c)*t2+s2->splines[1].d;
2205  bigreal diff = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
2206  bigreal x1p = ((s1->splines[0].a*t1p+s1->splines[0].b)*t1p+s1->splines[0].c)*t1p+s1->splines[0].d;
2207  bigreal y1p = ((s1->splines[1].a*t1p+s1->splines[1].b)*t1p+s1->splines[1].c)*t1p+s1->splines[1].d;
2208  bigreal x2p = ((s2->splines[0].a*t2p+s2->splines[0].b)*t2p+s2->splines[0].c)*t2p+s2->splines[0].d;
2209  bigreal y2p = ((s2->splines[1].a*t2p+s2->splines[1].b)*t2p+s2->splines[1].c)*t2p+s2->splines[1].d;
2210  bigreal diffp = (x1p-x2p)*(x1p-x2p) + (y1p-y2p)*(y1p-y2p);
2211 
2212  if ( diff<diffp )
2213 return( false );
2214 
2215 return( true );
2216 }
2217 
2218 /* returns 0=>no intersection, 1=>at least one, location in pts, t1s, t2s */
2219 /* -1 => We couldn't figure it out in a closed form, have to do a numerical */
2220 /* approximation */
2221 int SplinesIntersect(const Spline *s1, const Spline *s2, BasePoint pts[9],
2222  extended t1s[10], extended t2s[10]) { /* One extra for a trailing -1 */
2223  BasePoint min1, max1, min2, max2;
2224  int soln = 0;
2225  extended x,y,t, ac0, ac1;
2226  int i,j,found;
2227  Spline1D spline;
2228  extended tempts[4]; /* 3 solns for cubics, 4 for quartics */
2229  extended extrema1[6], extrema2[6];
2230  int ecnt1, ecnt2;
2231 
2232  t1s[0] = t1s[1] = t1s[2] = t1s[3] = -1;
2233  t2s[0] = t2s[1] = t2s[2] = t2s[3] = -1;
2234 
2235  if ( s1==s2 && !s1->knownlinear && !s1->isquadratic )
2236  /* Special case see if it doubles back on itself anywhere */;
2237  else if ( s1==s2 )
2238 return( 0 ); /* Linear and quadratics can't double back, can't self-intersect */
2239  else if ( s1->splines[0].a == s2->splines[0].a &&
2240  s1->splines[0].b == s2->splines[0].b &&
2241  s1->splines[0].c == s2->splines[0].c &&
2242  s1->splines[0].d == s2->splines[0].d &&
2243  s1->splines[1].a == s2->splines[1].a &&
2244  s1->splines[1].b == s2->splines[1].b &&
2245  s1->splines[1].c == s2->splines[1].c &&
2246  s1->splines[1].d == s2->splines[1].d )
2247 return( -1 ); /* Same spline. Intersects everywhere */
2248 
2249  /* Ignore splines which are just a point */
2250  if ( s1->knownlinear && s1->splines[0].c==0 && s1->splines[1].c==0 )
2251 return( 0 );
2252  if ( s2->knownlinear && s2->splines[0].c==0 && s2->splines[1].c==0 )
2253 return( 0 );
2254 
2255  if ( s1->knownlinear )
2256  /* Do Nothing */;
2257  else if ( s2->knownlinear || (!s1->isquadratic && s2->isquadratic)) {
2258  const Spline *stemp = s1;
2259  extended *ts = t1s;
2260  t1s = t2s; t2s = ts;
2261  s1 = s2; s2 = stemp;
2262  }
2263 
2264  min1 = s1->from->me; max1 = min1;
2265  min2 = s2->from->me; max2 = min2;
2266  if ( s1->from->nextcp.x>max1.x ) max1.x = s1->from->nextcp.x;
2267  else if ( s1->from->nextcp.x<min1.x ) min1.x = s1->from->nextcp.x;
2268  if ( s1->from->nextcp.y>max1.y ) max1.y = s1->from->nextcp.y;
2269  else if ( s1->from->nextcp.y<min1.y ) min1.y = s1->from->nextcp.y;
2270  if ( s1->to->prevcp.x>max1.x ) max1.x = s1->to->prevcp.x;
2271  else if ( s1->to->prevcp.x<min1.x ) min1.x = s1->to->prevcp.x;
2272  if ( s1->to->prevcp.y>max1.y ) max1.y = s1->to->prevcp.y;
2273  else if ( s1->to->prevcp.y<min1.y ) min1.y = s1->to->prevcp.y;
2274  if ( s1->to->me.x>max1.x ) max1.x = s1->to->me.x;
2275  else if ( s1->to->me.x<min1.x ) min1.x = s1->to->me.x;
2276  if ( s1->to->me.y>max1.y ) max1.y = s1->to->me.y;
2277  else if ( s1->to->me.y<min1.y ) min1.y = s1->to->me.y;
2278 
2279  if ( s2->from->nextcp.x>max2.x ) max2.x = s2->from->nextcp.x;
2280  else if ( s2->from->nextcp.x<min2.x ) min2.x = s2->from->nextcp.x;
2281  if ( s2->from->nextcp.y>max2.y ) max2.y = s2->from->nextcp.y;
2282  else if ( s2->from->nextcp.y<min2.y ) min2.y = s2->from->nextcp.y;
2283  if ( s2->to->prevcp.x>max2.x ) max2.x = s2->to->prevcp.x;
2284  else if ( s2->to->prevcp.x<min2.x ) min2.x = s2->to->prevcp.x;
2285  if ( s2->to->prevcp.y>max2.y ) max2.y = s2->to->prevcp.y;
2286  else if ( s2->to->prevcp.y<min2.y ) min2.y = s2->to->prevcp.y;
2287  if ( s2->to->me.x>max2.x ) max2.x = s2->to->me.x;
2288  else if ( s2->to->me.x<min2.x ) min2.x = s2->to->me.x;
2289  if ( s2->to->me.y>max2.y ) max2.y = s2->to->me.y;
2290  else if ( s2->to->me.y<min2.y ) min2.y = s2->to->me.y;
2291  if ( min1.x>max2.x || min2.x>max1.x || min1.y>max2.y || min2.y>max1.y )
2292 return( false ); /* no intersection of bounding boxes */
2293 
2294  if ( s1->knownlinear ) {
2295  spline.d = s1->splines[1].c*((bigreal) s2->splines[0].d-(bigreal) s1->splines[0].d)-
2296  s1->splines[0].c*((bigreal) s2->splines[1].d-(bigreal) s1->splines[1].d);
2297  spline.c = s1->splines[1].c*(bigreal) s2->splines[0].c - s1->splines[0].c*(bigreal) s2->splines[1].c;
2298  spline.b = s1->splines[1].c*(bigreal) s2->splines[0].b - s1->splines[0].c*(bigreal) s2->splines[1].b;
2299  spline.a = s1->splines[1].c*(bigreal) s2->splines[0].a - s1->splines[0].c*(bigreal) s2->splines[1].a;
2300  IterateSolve(&spline,tempts);
2301  if ( tempts[0]==-1 )
2302 return( false );
2303  for ( i = 0; i<3 && tempts[i]!=-1; ++i ) {
2304  x = ((s2->splines[0].a*tempts[i]+s2->splines[0].b)*tempts[i]+
2305  s2->splines[0].c)*tempts[i]+s2->splines[0].d;
2306  y = ((s2->splines[1].a*tempts[i]+s2->splines[1].b)*tempts[i]+
2307  s2->splines[1].c)*tempts[i]+s2->splines[1].d;
2308  if ( s1->splines[0].c==0 )
2309  x = s1->splines[0].d;
2310  if ( s1->splines[1].c==0 )
2311  y = s1->splines[1].d;
2312  if ( (ac0 = s1->splines[0].c)<0 ) ac0 = -ac0;
2313  if ( (ac1 = s1->splines[1].c)<0 ) ac1 = -ac1;
2314  if ( ac0>ac1 )
2315  t = (x-s1->splines[0].d)/s1->splines[0].c;
2316  else
2317  t = (y-s1->splines[1].d)/s1->splines[1].c;
2318  if ( tempts[i]>.99996 && Closer(s1,s2,t,tempts[i],t,1)) {
2319  tempts[i] = 1;
2320  x = s2->to->me.x; y = s2->to->me.y;
2321  } else if ( tempts[i]<.00001 && Closer(s1,s2,t,tempts[i],t,0)) {
2322  tempts[i] = 0;
2323  x = s2->from->me.x; y = s2->from->me.y;
2324  }
2325  /* I know we just did this, but we might have changed x,y so redo */
2326  if ( ac0>ac1 )
2327  t = (x-s1->splines[0].d)/s1->splines[0].c;
2328  else
2329  t = (y-s1->splines[1].d)/s1->splines[1].c;
2330  if ( t>.99996 && t<1.001 && Closer(s1,s2,t,tempts[i],1,tempts[i])) {
2331  t = 1;
2332  x = s1->to->me.x; y = s1->to->me.y;
2333  } else if ( t<.00001 && t>-.001 && Closer(s1,s2,t,tempts[i],0,tempts[i])) {
2334  t = 0;
2335  x = s1->from->me.x; y = s1->from->me.y;
2336  }
2337  if ( t<-.001 || t>1.001 || x<min1.x-.01 || y<min1.y-.01 || x>max1.x+.01 || y>max1.y+.01 )
2338  continue;
2339  if ( t<=0 ) {t=0; x=s1->from->me.x; y = s1->from->me.y; }
2340  else if ( t>=1 ) { t=1; x=s1->to->me.x; y = s1->to->me.y; }
2341  if ( s1->from->me.x==s1->to->me.x ) /* Avoid rounding errors */
2342  x = s1->from->me.x; /* on hor/vert lines */
2343  else if ( s1->from->me.y==s1->to->me.y )
2344  y = s1->from->me.y;
2345  if ( s2->knownlinear ) {
2346  if ( s2->from->me.x==s2->to->me.x )
2347  x = s2->from->me.x;
2348  else if ( s2->from->me.y==s2->to->me.y )
2349  y = s2->from->me.y;
2350  }
2351  soln = AddPoint(x,y,t,tempts[i],pts,t1s,t2s,soln);
2352  }
2353 return( soln!=0 );
2354  }
2355  /* if one of the splines is quadratic then we can get an expression */
2356  /* relating c*t+d to poly(s^3), and substituting this back we get */
2357  /* a poly of degree 6 in s which could be solved iteratively */
2358  /* however mixed quadratics and cubics are unlikely */
2359 
2360  /* but if both splines are degree 3, the t is expressed as the sqrt of */
2361  /* a third degree poly, which must be substituted into a cubic, and */
2362  /* then squared to get rid of the sqrts leaving us with an ?18? degree */
2363  /* poly. Ick. */
2364 
2365  /* So let's do it the hard way... we break the splines into little bits */
2366  /* where they are monotonic in both dimensions, then check these for */
2367  /* possible intersections */
2368  extrema1[0] = extrema2[0] = 0;
2369  ecnt1 = Spline2DFindExtrema(s1,extrema1+1);
2370  ecnt2 = Spline2DFindExtrema(s2,extrema2+1);
2371  extrema1[++ecnt1] = 1.0;
2372  extrema2[++ecnt2] = 1.0;
2373  found=0;
2374  for ( i=0; i<ecnt1; ++i ) {
2375  min1.x = ((s1->splines[0].a*extrema1[i]+s1->splines[0].b)*extrema1[i]+
2376  s1->splines[0].c)*extrema1[i]+s1->splines[0].d;
2377  min1.y = ((s1->splines[1].a*extrema1[i]+s1->splines[1].b)*extrema1[i]+
2378  s1->splines[1].c)*extrema1[i]+s1->splines[1].d;
2379  max1.x = ((s1->splines[0].a*extrema1[i+1]+s1->splines[0].b)*extrema1[i+1]+
2380  s1->splines[0].c)*extrema1[i+1]+s1->splines[0].d;
2381  max1.y = ((s1->splines[1].a*extrema1[i+1]+s1->splines[1].b)*extrema1[i+1]+
2382  s1->splines[1].c)*extrema1[i+1]+s1->splines[1].d;
2383  if ( max1.x<min1.x ) { extended temp = max1.x; max1.x = min1.x; min1.x = temp; }
2384  if ( max1.y<min1.y ) { extended temp = max1.y; max1.y = min1.y; min1.y = temp; }
2385  for ( j=(s1==s2)?i+1:0; j<ecnt2; ++j ) {
2386  min2.x = ((s2->splines[0].a*extrema2[j]+s2->splines[0].b)*extrema2[j]+
2387  s2->splines[0].c)*extrema2[j]+s2->splines[0].d;
2388  min2.y = ((s2->splines[1].a*extrema2[j]+s2->splines[1].b)*extrema2[j]+
2389  s2->splines[1].c)*extrema2[j]+s2->splines[1].d;
2390  max2.x = ((s2->splines[0].a*extrema2[j+1]+s2->splines[0].b)*extrema2[j+1]+
2391  s2->splines[0].c)*extrema2[j+1]+s2->splines[0].d;
2392  max2.y = ((s2->splines[1].a*extrema2[j+1]+s2->splines[1].b)*extrema2[j+1]+
2393  s2->splines[1].c)*extrema2[j+1]+s2->splines[1].d;
2394  if ( max2.x<min2.x ) { extended temp = max2.x; max2.x = min2.x; min2.x = temp; }
2395  if ( max2.y<min2.y ) { extended temp = max2.y; max2.y = min2.y; min2.y = temp; }
2396  if ( min1.x>max2.x || min2.x>max1.x || min1.y>max2.y || min2.y>max1.y )
2397  /* No possible intersection */;
2398  else if ( s1!=s2 )
2399  found += CubicsIntersect(s1,extrema1[i],extrema1[i+1],&min1,&max1,
2400  s2,extrema2[j],extrema2[j+1],&min2,&max2,
2401  &pts[found],&t1s[found],&t2s[found],9-found);
2402  else {
2403  int k,l;
2404  int cnt = CubicsIntersect(s1,extrema1[i],extrema1[i+1],&min1,&max1,
2405  s2,extrema2[j],extrema2[j+1],&min2,&max2,
2406  &pts[found],&t1s[found],&t2s[found],9-found);
2407  for ( k=0; k<cnt; ++k ) {
2408  if ( RealNear(t1s[found+k],t2s[found+k]) ) {
2409  for ( l=k+1; l<cnt; ++l ) {
2410  pts[found+l-1] = pts[found+l];
2411  t1s[found+l-1] = t1s[found+l];
2412  t2s[found+l-1] = t2s[found+l];
2413  }
2414  --cnt; --k;
2415  }
2416  }
2417  found += cnt;
2418  }
2419  if ( found>=8 ) {
2420  /* If the splines are colinear then we might get an unbounded */
2421  /* number of intersections */
2422  break;
2423  }
2424  }
2425  }
2426  t1s[found] = t2s[found] = -1;
2427 return( found!=0 );
2428 }
2429 
2431  HintInstance *hi, *n;
2432 
2433  for ( hi=h->where; hi!=NULL; hi=n ) {
2434  n = hi->next;
2435  chunkfree(hi,sizeof(HintInstance));
2436  }
2437  chunkfree(h,sizeof(StemInfo));
2438 }
2439 
2441  StemInfo *hnext;
2442  HintInstance *hi, *n;
2443 
2444  for ( ; h!=NULL; h = hnext ) {
2445  for ( hi=h->where; hi!=NULL; hi=n ) {
2446  n = hi->next;
2447  chunkfree(hi,sizeof(HintInstance));
2448  }
2449  hnext = h->next;
2450  chunkfree(h,sizeof(StemInfo));
2451  }
2452 }
2453 
2455  HintInstance *hi, *n;
2456 
2457  for ( hi=h->where; hi!=NULL; hi=n ) {
2458  n = hi->next;
2459  chunkfree(hi,sizeof(HintInstance));
2460  }
2461  chunkfree(h,sizeof(DStemInfo));
2462 }
2463 
2465  DStemInfo *hnext;
2466  HintInstance *hi, *n;
2467 
2468  for ( ; h!=NULL; h = hnext ) {
2469  for ( hi=h->where; hi!=NULL; hi=n ) {
2470  n = hi->next;
2471  chunkfree(hi,sizeof(HintInstance));
2472  }
2473  hnext = h->next;
2474  chunkfree(h,sizeof(DStemInfo));
2475  }
2476 }
2477 
2479  KernPair *knext;
2480  for ( ; kp!=NULL; kp = knext ) {
2481  knext = kp->next;
2482  if ( kp->adjust!=NULL ) {
2483  free(kp->adjust->corrections);
2484  chunkfree(kp->adjust,sizeof(DeviceTable));
2485  }
2486  chunkfree(kp,sizeof(KernPair));
2487  }
2488 }
2489 
2491  AnchorPoint *anext;
2492  for ( ; ap!=NULL; ap = anext ) {
2493  anext = ap->next;
2494  free(ap->xadjust.corrections);
2495  free(ap->yadjust.corrections);
2496  chunkfree(ap,sizeof(AnchorPoint));
2497  }
2498 }
2499 
2501  if ( adjust==NULL )
2502 return;
2503  free( adjust->xadjust.corrections );
2504  free( adjust->yadjust.corrections );
2505  free( adjust->xadv.corrections );
2506  free( adjust->yadv.corrections );
2507  chunkfree(adjust,sizeof(ValDevTab));
2508 }
2509 
2511 
2512  if ( dt==NULL )
2513 return;
2514 
2515  free(dt->corrections);
2516  chunkfree(dt,sizeof(DeviceTable));
2517 }
2518 
2519 void PSTFree(PST *pst) {
2520  PST *pnext;
2521  for ( ; pst!=NULL; pst = pnext ) {
2522  pnext = pst->next;
2523  if ( pst->type==pst_lcaret )
2524  free(pst->u.lcaret.carets);
2525  else if ( pst->type==pst_pair ) {
2526  free(pst->u.pair.paired);
2527  ValDevFree(pst->u.pair.vr[0].adjust);
2528  ValDevFree(pst->u.pair.vr[1].adjust);
2529  chunkfree(pst->u.pair.vr,sizeof(struct vr [2]));
2530  } else if ( pst->type!=pst_position ) {
2531  free(pst->u.subs.variant);
2532  } else if ( pst->type==pst_position ) {
2533  ValDevFree(pst->u.pos.adjust);
2534  }
2535  chunkfree(pst,sizeof(PST));
2536  }
2537 }
2538 
2540  int j;
2541 
2542  switch ( format ) {
2543  case pst_glyphs:
2544  free(r->u.glyph.names);
2545  free(r->u.glyph.back);
2546  free(r->u.glyph.fore);
2547  break;
2548  case pst_class:
2549  free(r->u.class.nclasses);
2550  free(r->u.class.bclasses);
2551  free(r->u.class.fclasses);
2552  break;
2553  case pst_reversecoverage:
2554  free(r->u.rcoverage.replacements);
2555  case pst_coverage:
2556  for ( j=0 ; j<r->u.coverage.ncnt ; ++j )
2557  free(r->u.coverage.ncovers[j]);
2558  free(r->u.coverage.ncovers);
2559  for ( j=0 ; j<r->u.coverage.bcnt ; ++j )
2560  free(r->u.coverage.bcovers[j]);
2561  free(r->u.coverage.bcovers);
2562  for ( j=0 ; j<r->u.coverage.fcnt ; ++j )
2563  free(r->u.coverage.fcovers[j]);
2564  free(r->u.coverage.fcovers);
2565  break;
2566  default:;
2567  }
2568  free(r->lookups);
2569 }
2570 
2571 void FPSTClassesFree(FPST *fpst) {
2572  int i;
2573 
2574  for ( i=0; i<fpst->nccnt; ++i ) {
2575  free(fpst->nclass[i]);
2576  free(fpst->nclassnames[i]);
2577  }
2578  for ( i=0; i<fpst->bccnt; ++i ) {
2579  free(fpst->bclass[i]);
2580  free(fpst->bclassnames[i]);
2581  }
2582  for ( i=0; i<fpst->fccnt; ++i ) {
2583  free(fpst->fclass[i]);
2584  free(fpst->fclassnames[i]);
2585  }
2586  free(fpst->nclass); free(fpst->bclass); free(fpst->fclass);
2587  free(fpst->nclassnames); free(fpst->bclassnames); free(fpst->fclassnames);
2588 
2589  fpst->nccnt = fpst->bccnt = fpst->fccnt = 0;
2590  fpst->nclass = fpst->bclass = fpst->fclass = NULL;
2591  fpst->nclassnames = fpst->bclassnames = fpst->fclassnames = NULL;
2592 }
2593 
2594 void FPSTFree(FPST *fpst) {
2595  FPST *next;
2596  int i;
2597 
2598  while ( fpst!=NULL ) {
2599  next = fpst->next;
2600  FPSTClassesFree(fpst);
2601  for ( i=0; i<fpst->rule_cnt; ++i ) {
2602  FPSTRuleContentsFree( &fpst->rules[i],fpst->format );
2603  }
2604  free(fpst->rules);
2605  chunkfree(fpst,sizeof(FPST));
2606  fpst = next;
2607  }
2608 }
2609 
2612 
2613  while ( md!=NULL ) {
2614  next = md->next;
2615  chunkfree(md,sizeof(MinimumDistance));
2616  md = next;
2617  }
2618 }
2619 
2621  struct ttflangname *next;
2622  int i;
2623 
2624  while ( l!=NULL ) {
2625  next = l->next;
2626  for ( i=0; i<ttf_namemax; ++i )
2627  free(l->names[i]);
2628  chunkfree(l,sizeof(*l));
2629  l = next;
2630  }
2631 }
2632 
2633 void AltUniFree(struct altuni *altuni) {
2634  struct altuni *next;
2635 
2636  while ( altuni ) {
2637  next = altuni->next;
2638  chunkfree(altuni,sizeof(struct altuni));
2639  altuni = next;
2640  }
2641 }
2642 
2644  memset(layer,0,sizeof(Layer));
2647  layer->stroke_pen.width = 10;
2650  layer->dofill = true;
2651  layer->fillfirst = true;
2652  layer->stroke_pen.trans[0] = layer->stroke_pen.trans[3] = 1.0;
2653  layer->stroke_pen.trans[1] = layer->stroke_pen.trans[2] = 0.0;
2654  /* Dashes default to an unbroken line */
2655 }
2656 
2657 SplineChar *SplineCharCreate(int layer_cnt) {
2658  SplineChar *sc = chunkalloc(sizeof(SplineChar));
2659  int i;
2660 
2661  sc->color = COLOR_DEFAULT;
2662  sc->orig_pos = 0xffff;
2663  sc->unicodeenc = -1;
2664  sc->layer_cnt = layer_cnt;
2665  sc->layers = calloc(layer_cnt,sizeof(Layer));
2666  for ( i=0; i<layer_cnt; ++i )
2667  LayerDefault(&sc->layers[i]);
2668  sc->tex_height = sc->tex_depth = sc->italic_correction = sc->top_accent_horiz =
2669  TEX_UNDEF;
2670 return( sc );
2671 }
2672 
2674  SplineChar *sc = SplineCharCreate(sf==NULL?2:sf->layer_cnt);
2675  int i;
2676 
2677  if ( sf==NULL ) {
2678  sc->layers[ly_back].background = true;
2679  sc->layers[ly_fore].background = false;
2680  } else {
2681  for ( i=0; i<sf->layer_cnt; ++i ) {
2682  sc->layers[i].background = sf->layers[i].background;
2683  sc->layers[i].order2 = sf->layers[i].order2;
2684  }
2685  sc->parent = sf;
2686  }
2687 return( sc );
2688 }
2689 
2691  int i;
2692 
2693  if ( gv==NULL )
2694 return;
2695  free(gv->variants);
2697  for ( i=0; i<gv->part_cnt; ++i )
2698  free( gv->parts[i].component );
2699  free(gv->parts);
2700  chunkfree(gv,sizeof(*gv));
2701 }
2702 
2704  int i;
2705  for ( i=0; i<mk->cnt; ++i ) {
2706  DeviceTableFree(mk->mkd[i].height_adjusts);
2707  DeviceTableFree(mk->mkd[i].kern_adjusts);
2708  }
2709  free(mk->mkd);
2710 }
2711 
2712 void MathKernFree(struct mathkern *mk) {
2713  int i;
2714 
2715  if ( mk==NULL )
2716 return;
2717  for ( i=0; i<4; ++i )
2718  MathKernVContentsFree( &(&mk->top_right)[i] );
2719  chunkfree(mk,sizeof(*mk));
2720 }
2721 
2723  struct splinecharlist *dnext;
2724  for ( ; dlist!=NULL; dlist = dnext ) {
2725  dnext = dlist->next;
2726  chunkfree(dlist,sizeof(struct splinecharlist));
2727  }
2728 }
2729 
2730 struct pattern *PatternCopy(struct pattern *old, real transform[6]) {
2731  struct pattern *pat;
2732 
2733  if ( old==NULL )
2734 return( NULL );
2735 
2736  pat = chunkalloc(sizeof(struct pattern));
2737 
2738  *pat = *old;
2739  pat->pattern = copy( old->pattern );
2740  if ( transform!=NULL )
2741  MatMultiply(pat->transform,transform,pat->transform);
2742 return( pat );
2743 }
2744 
2745 void PatternFree(struct pattern *pat) {
2746  if ( pat==NULL )
2747 return;
2748  free(pat->pattern);
2749  chunkfree(pat,sizeof(struct pattern));
2750 }
2751 
2752 struct gradient *GradientCopy(struct gradient *old,real transform[6]) {
2753  struct gradient *grad;
2754 
2755  if ( old==NULL )
2756 return( NULL );
2757 
2758  grad = chunkalloc(sizeof(struct gradient));
2759 
2760  *grad = *old;
2761  grad->grad_stops = malloc(old->stop_cnt*sizeof(struct grad_stops));
2762  memcpy(grad->grad_stops,old->grad_stops,old->stop_cnt*sizeof(struct grad_stops));
2763  if ( transform!=NULL ) {
2764  BpTransform(&grad->start,&grad->start,transform);
2765  BpTransform(&grad->stop,&grad->stop,transform);
2766  }
2767 return( grad );
2768 }
2769 
2770 void GradientFree(struct gradient *grad) {
2771  if ( grad==NULL )
2772 return;
2773  free(grad->grad_stops);
2774  chunkfree(grad,sizeof(struct gradient));
2775 }
2776 
2777 void BrushCopy(struct brush *into, struct brush *from, real transform[6]) {
2778  *into = *from;
2779  into->gradient = GradientCopy(from->gradient,transform);
2780  into->pattern = PatternCopy(from->pattern,transform);
2781 }
2782 
2783 void PenCopy(struct pen *into, struct pen *from,real transform[6]) {
2784  *into = *from;
2787 }
2788 
2790  SplinePointListsFree(sc->layers[layer].splines);
2791  GradientFree(sc->layers[layer].fill_brush.gradient);
2792  PatternFree(sc->layers[layer].fill_brush.pattern);
2793  GradientFree(sc->layers[layer].stroke_pen.brush.gradient);
2794  PatternFree(sc->layers[layer].stroke_pen.brush.pattern);
2795  RefCharsFree(sc->layers[layer].refs);
2796  /* image garbage collection????!!!! */
2797 }
2798 
2800  int i;
2801 
2802  if ( sc==NULL )
2803 return;
2804  if (sc->name != NULL) free(sc->name);
2805  if (sc->comment != NULL) free(sc->comment);
2806  for ( i=0; i<sc->layer_cnt; ++i ) {
2807 #if defined(_NO_PYTHON)
2808  if (sc->layers[i].python_persistent != NULL) free( sc->layers[i].python_persistent ); /* It's a string of pickled data which we leave as a string */
2809 #else
2810  PyFF_FreeSCLayer(sc, i);
2811 #endif
2813  }
2814  StemInfosFree(sc->hstem);
2815  StemInfosFree(sc->vstem);
2816  DStemInfosFree(sc->dstem);
2817  MinimumDistancesFree(sc->md);
2818  KernPairsFree(sc->kerns);
2819  KernPairsFree(sc->vkerns);
2820  AnchorPointsFree(sc->anchor);
2821  SplineCharListsFree(sc->dependents);
2822  PSTFree(sc->possub);
2823  if (sc->ttf_instrs != NULL) free(sc->ttf_instrs);
2824  if (sc->countermasks != NULL) free(sc->countermasks);
2825  if (sc->layers != NULL) free(sc->layers);
2826  AltUniFree(sc->altuni);
2827  GlyphVariantsFree(sc->horiz_variants);
2828  GlyphVariantsFree(sc->vert_variants);
2829  DeviceTableFree(sc->italic_adjusts);
2830  DeviceTableFree(sc->top_accent_adjusts);
2831  MathKernFree(sc->mathkern);
2832  if (sc->glif_name != NULL) { free(sc->glif_name); sc->glif_name = NULL; }
2833 }
2834 
2836 
2837  if ( sc==NULL )
2838 return;
2840  chunkfree(sc,sizeof(SplineChar));
2841 }
2842 
2844  AnchorClass *anext;
2845  for ( ; an!=NULL; an = anext ) {
2846  anext = an->next;
2847  free(an->name);
2848  chunkfree(an,sizeof(AnchorClass));
2849  }
2850 }
2851 
2852 void TtfTablesFree(struct ttf_table *tab) {
2853  struct ttf_table *next;
2854 
2855  for ( ; tab!=NULL; tab = next ) {
2856  next = tab->next;
2857  free(tab->data);
2858  chunkfree(tab,sizeof(struct ttf_table));
2859  }
2860 }
2861 
2863  struct scriptlanglist *next;
2864 
2865  while ( sl!=NULL ) {
2866  next = sl->next;
2867  free(sl->morelangs);
2868  chunkfree(sl,sizeof(*sl));
2869  sl = next;
2870  }
2871 }
2872 
2875 
2876  while ( fl!=NULL ) {
2877  next = fl->next;
2879  chunkfree(fl,sizeof(*fl));
2880  fl = next;
2881  }
2882 }
2883 
2885  struct lookup_subtable *st, *stnext;
2886 
2887  free(lookup->lookup_name);
2888  FeatureScriptLangListFree(lookup->features);
2889  for ( st=lookup->subtables; st!=NULL; st=stnext ) {
2890  stnext = st->next;
2891  free(st->subtable_name);
2892  free(st->suffix);
2893  chunkfree(st,sizeof(struct lookup_subtable));
2894  }
2895  chunkfree( lookup,sizeof(OTLookup) );
2896 }
2897 
2899  OTLookup *next;
2900 
2901  for ( ; lookup!=NULL; lookup = next ) {
2902  next = lookup->next;
2904  }
2905 }
2906 
2908  int i;
2909  for ( i=1; i<kc->first_cnt; ++i )
2910  free(kc->firsts[i]);
2911  for ( i=1; i<kc->second_cnt; ++i )
2912  free(kc->seconds[i]);
2913  free(kc->firsts);
2914  free(kc->seconds);
2915  free(kc->offsets);
2916  for ( i=kc->first_cnt*kc->second_cnt-1; i>=0 ; --i )
2918  free(kc->adjusts);
2922  if (kc->firsts_names) {
2923  for ( i=kc->first_cnt-1; i>=0 ; --i )
2924  free(kc->firsts_names[i]);
2925  free(kc->firsts_names);
2926  }
2927  if (kc->seconds_names) {
2928  for ( i=kc->second_cnt-1; i>=0 ; --i )
2929  free(kc->seconds_names[i]);
2930  free(kc->seconds_names);
2931  }
2932 }
2933 
2935  // This frees and zeros special data not handled by the FontForge GUI,
2936  // most of which comes from U. F. O..
2937  int i;
2941  if (kc->firsts_names) {
2942  for ( i=kc->first_cnt-1; i>=0 ; --i )
2943  free(kc->firsts_names[i]);
2944  free(kc->firsts_names);
2945  kc->firsts_names = NULL;
2946  }
2947  if (kc->seconds_names) {
2948  for ( i=kc->second_cnt-1; i>=0 ; --i )
2949  free(kc->seconds_names[i]);
2950  free(kc->seconds_names);
2951  kc->seconds_names = NULL;
2952  }
2953 }
2954 
2956  KernClass *n;
2957 
2958  while ( kc ) {
2960  n = kc->next;
2961  chunkfree(kc,sizeof(KernClass));
2962  kc = n;
2963  }
2964 }
2965 
2967  KernClass *n;
2968 
2969  while ( kc ) {
2971  n = kc->next;
2972  kc = n;
2973  }
2974 }
2975 
2976 void MacNameListFree(struct macname *mn) {
2977  struct macname *next;
2978 
2979  while ( mn!=NULL ) {
2980  next = mn->next;
2981  free(mn->name);
2982  chunkfree(mn,sizeof(struct macname));
2983  mn = next;
2984  }
2985 }
2986 
2987 void MacSettingListFree(struct macsetting *ms) {
2988  struct macsetting *next;
2989 
2990  while ( ms!=NULL ) {
2991  next = ms->next;
2992  MacNameListFree(ms->setname);
2993  chunkfree(ms,sizeof(struct macsetting));
2994  ms = next;
2995  }
2996 }
2997 
2999  MacFeat *next;
3000 
3001  while ( mf!=NULL ) {
3002  next = mf->next;
3003  MacNameListFree(mf->featname);
3004  MacSettingListFree(mf->settings);
3005  chunkfree(mf,sizeof(MacFeat));
3006  mf = next;
3007  }
3008 }
3009 
3010 void ASMFree(ASM *sm) {
3011  ASM *next;
3012  int i;
3013 
3014  while ( sm!=NULL ) {
3015  next = sm->next;
3016  if ( sm->type==asm_insert ) {
3017  for ( i=0; i<sm->class_cnt*sm->state_cnt; ++i ) {
3018  free( sm->state[i].u.insert.mark_ins );
3019  free( sm->state[i].u.insert.cur_ins );
3020  }
3021  } else if ( sm->type==asm_kern ) {
3022  for ( i=0; i<sm->class_cnt*sm->state_cnt; ++i ) {
3023  free( sm->state[i].u.kern.kerns );
3024  }
3025  }
3026  for ( i=4; i<sm->class_cnt; ++i )
3027  free(sm->classes[i]);
3028  free(sm->state);
3029  free(sm->classes);
3030  chunkfree(sm,sizeof(ASM));
3031  sm = next;
3032  }
3033 }
3034 
3035 void OtfNameListFree(struct otfname *on) {
3036  struct otfname *on_next;
3037 
3038  for ( ; on!=NULL; on = on_next ) {
3039  on_next = on->next;
3040  free(on->name);
3041  chunkfree(on,sizeof(*on));
3042  }
3043 }
3044 
3046  struct otffeatname *fn_next;
3047 
3048  for ( ; fn!=NULL; fn = fn_next ) {
3049  fn_next = fn->next;
3050  OtfNameListFree(fn->names);
3051  chunkfree(fn,sizeof(*fn));
3052  }
3053 }
3054 
3055 EncMap *EncMapNew(int enccount,int backmax,Encoding *enc) {
3056 /* NOTE: 'enccount' and 'backmax' can sometimes be different map sizes */
3057  EncMap *map;
3058 
3059  /* Ensure all memory available, otherwise cleanup and exit as NULL */
3060  if ( (map=chunkalloc(sizeof(EncMap)))!=NULL ) {
3061  if ( (map->map=malloc(enccount*sizeof(int32)))!=NULL ) {
3062  if ( (map->backmap=malloc(backmax*sizeof(int32)))!=NULL ) {
3063  map->enccount = map->encmax = enccount;
3064  map->backmax = backmax;
3065  memset(map->map,-1,enccount*sizeof(int32));
3066  memset(map->backmap,-1,backmax*sizeof(int32));
3067  map->enc = enc;
3068  return( map );
3069  }
3070  free(map->map);
3071  }
3072  free(map);
3073  }
3074  return( NULL );
3075 }
3076 
3077 EncMap *EncMap1to1(int enccount) {
3078 /* Used for CID fonts where CID is same as orig_pos */
3079 /* NOTE: map-enc point to a global variable custom. */
3080 /* TODO: avoid global custom and use passed pointer */
3081  EncMap *map;
3082  int i;
3083 
3084  if ( (map=EncMapNew(enccount,enccount,&custom))!=NULL ) {
3085  for ( i=0; i<enccount; ++i )
3086  map->map[i] = map->backmap[i] = i;
3087  }
3088  return( map );
3089 }
3090 
3092  if ( map==NULL )
3093 return;
3094 
3095  if ( map->enc->is_temporary )
3096  EncodingFree(map->enc);
3097  free(map->map);
3098  free(map->backmap);
3099  free(map->remap);
3100  chunkfree(map,sizeof(EncMap));
3101 }
3102 
3103 void MarkClassFree(int cnt,char **classes,char **names) {
3104  int i;
3105 
3106  for ( i=1; i<cnt; ++i ) {
3107  free( classes[i] );
3108  free( names[i] );
3109  }
3110  free( classes );
3111  free( names );
3112 }
3113 
3114 void MarkSetFree(int cnt,char **classes,char **names) {
3115  int i;
3116 
3117  for ( i=0; i<cnt; ++i ) {
3118  free( classes[i] );
3119  free( names[i] );
3120  }
3121  free( classes );
3122  free( names );
3123 }
3124 
3126  struct baselangextent *head, *last, *cur;
3127 
3128  last = head = NULL;
3129  for ( ; extent!=NULL; extent = extent->next ) {
3130  cur = chunkalloc(sizeof(struct baselangextent));
3131  *cur = *extent;
3132  cur->features = BaseLangCopy(cur->features);
3133  if ( head==NULL )
3134  head = cur;
3135  else
3136  last->next = cur;
3137  last = cur;
3138  }
3139 return( head );
3140 }
3141 
3143  struct baselangextent *next;
3144 
3145  while ( extent!=NULL ) {
3146  next = extent->next;
3147  BaseLangFree(extent->features);
3148  chunkfree(extent,sizeof(struct baselangextent));
3149  extent = next;
3150  }
3151 }
3152 
3153 void BaseScriptFree(struct basescript *bs) {
3154  struct basescript *next;
3155 
3156  while ( bs!=NULL ) {
3157  next = bs->next;
3158  if ( bs->baseline_pos )
3159  free(bs->baseline_pos);
3160  BaseLangFree(bs->langs);
3161  chunkfree(bs,sizeof(struct basescript));
3162  bs = next;
3163  }
3164 }
3165 
3166 void BaseFree(struct Base *base) {
3167  if ( base==NULL )
3168 return;
3169 
3170  free(base->baseline_tags);
3171  BaseScriptFree(base->scripts);
3172  chunkfree(base,sizeof(struct Base));
3173 }
3174 
3175 void JstfLangFree(struct jstf_lang *jl) {
3176  struct jstf_lang *next;
3177  int i;
3178 
3179  while ( jl!=NULL ) {
3180  next = jl->next;
3181  for ( i=0; i<jl->cnt; ++i ) {
3182  struct jstf_prio *jp = &jl->prios[i];
3183  free(jp->enableShrink);
3184  free(jp->disableShrink);
3185  free(jp->maxShrink);
3186  free(jp->enableExtend);
3187  free(jp->disableExtend);
3188  free(jp->maxExtend);
3189  }
3190  free(jl->prios);
3191  chunkfree(jl,sizeof(*jl));
3192  jl = next;
3193  }
3194 }
3195 
3196 void JustifyFree(Justify *just) {
3197  Justify *next;
3198 
3199  while ( just!=NULL ) {
3200  next = just->next;
3201  free(just->extenders);
3202  JstfLangFree(just->langs);
3203  chunkfree(just,sizeof(*just));
3204  just = next;
3205  }
3206 }
3207 
3209  int i;
3210 
3211  if ( sf==NULL )
3212 return;
3213  if ( sf->mm!=NULL ) {
3214  MMSetFree(sf->mm);
3215 return;
3216  }
3217  if ( sf->sfd_version>0 && sf->sfd_version<2 ) {
3218  // Free special data.
3219  SplineFont1* oldsf = (SplineFont1*)sf;
3220  // First the script language lists.
3221  if (oldsf->script_lang != NULL) {
3222  int scripti;
3223  for (scripti = 0; oldsf->script_lang[scripti] != NULL; scripti ++) {
3224  int scriptj;
3225  for (scriptj = 0; oldsf->script_lang[scripti][scriptj].script != 0; scriptj ++) {
3226  if (oldsf->script_lang[scripti][scriptj].langs != NULL) free(oldsf->script_lang[scripti][scriptj].langs);
3227  }
3228  free(oldsf->script_lang[scripti]); oldsf->script_lang[scripti] = NULL;
3229  }
3230  free(oldsf->script_lang); oldsf->script_lang = NULL;
3231  }
3232  // Then the table orderings.
3233  {
3234  struct table_ordering *ord = oldsf->orders;
3235  while (ord != NULL) {
3236  struct table_ordering *ordtofree = ord;
3237  if (ord->ordered_features != NULL) free(ord->ordered_features);
3238  ord = ord->next;
3239  chunkfree(ordtofree, sizeof(struct table_ordering));
3240  }
3241  oldsf->orders = NULL;
3242  }
3243  }
3244  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
3245  SplineCharFree(sf->glyphs[i]);
3246  free(sf->glyphs);
3247  free(sf->fontname);
3248  free(sf->fullname);
3249  free(sf->familyname);
3250  free(sf->weight);
3251  free(sf->copyright);
3252  free(sf->comments);
3253  free(sf->filename);
3254  free(sf->origname);
3255  free(sf->autosavename);
3256  free(sf->version);
3257  free(sf->xuid);
3258  free(sf->cidregistry);
3259  free(sf->ordering);
3260  if (sf->map != 0)
3261  EncMapFree(sf->map);
3262  if (sf->MATH)
3263  free(sf->MATH);
3264  if ( sf->styleMapFamilyName && sf->styleMapFamilyName[0]!='\0' ) { free(sf->styleMapFamilyName); sf->styleMapFamilyName = NULL; }
3265  MacFeatListFree(sf->features);
3266  /* We don't free the EncMap. That field is only a temporary pointer. Let the FontViewBase free it, that's where it really lives */
3267  // TODO: But that doesn't always get freed. The statement below causes double-frees, so we need to come up with better conditions.
3268  #if 0
3269  if (sf->cidmaster == NULL || sf->cidmaster == sf)
3270  if (sf->map != NULL) { free(sf->map); sf->map = NULL; }
3271  #endif // 0
3272  SplinePointListsFree(sf->grid.splines);
3273  AnchorClassesFree(sf->anchor);
3274  TtfTablesFree(sf->ttf_tables);
3275  TtfTablesFree(sf->ttf_tab_saved);
3276  PSDictFree(sf->private);
3277  TTFLangNamesFree(sf->names);
3278  for ( i=0; i<sf->subfontcnt; ++i )
3279  SplineFontFree(sf->subfonts[i]);
3280  free(sf->subfonts);
3281  GlyphHashFree(sf);
3282  OTLookupListFree(sf->gpos_lookups);
3283  OTLookupListFree(sf->gsub_lookups);
3284  KernClassListFree(sf->kerns);
3285  KernClassListFree(sf->vkerns);
3286  FPSTFree(sf->possub);
3287  ASMFree(sf->sm);
3288  OtfNameListFree(sf->fontstyle_name);
3289  OtfFeatNameListFree(sf->feat_names);
3290  MarkClassFree(sf->mark_class_cnt,sf->mark_classes,sf->mark_class_names);
3291  MarkSetFree(sf->mark_set_cnt,sf->mark_sets,sf->mark_set_names);
3292  GlyphGroupsFree(sf->groups);
3293  GlyphGroupKernsFree(sf->groupkerns);
3294  GlyphGroupKernsFree(sf->groupvkerns);
3295  free( sf->gasp );
3296 #if defined(_NO_PYTHON)
3297  free( sf->python_persistent ); /* It's a string of pickled data which we leave as a string */
3298 #else
3299  PyFF_FreeSF(sf);
3300 #endif
3301  BaseFree(sf->horiz_base);
3302  BaseFree(sf->vert_base);
3303  JustifyFree(sf->justify);
3304  if (sf->layers != NULL) {
3305  int layer;
3306  for (layer = 0; layer < sf->layer_cnt; layer ++) {
3307  if (sf->layers[layer].name != NULL) {
3308  free(sf->layers[layer].name);
3309  sf->layers[layer].name = NULL;
3310  }
3311  if (sf->layers[layer].ufo_path != NULL) {
3312  free(sf->layers[layer].ufo_path);
3313  sf->layers[layer].ufo_path = NULL;
3314  }
3315  }
3316  free(sf->layers); sf->layers = NULL;
3317  }
3318  free(sf);
3319 }
3320 
3322  int i;
3323 
3324  if ( sf==NULL )
3325 return;
3326  if ( sf->mm!=NULL ) {
3327  MMSetClearSpecial(sf->mm);
3328 return;
3329  }
3330  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL ) {
3331  struct splinechar *sc = sf->glyphs[i];
3332  if (sc->glif_name != NULL) { free(sc->glif_name); sc->glif_name = NULL; }
3333  }
3334  for ( i=0; i<sf->subfontcnt; ++i )
3335  SplineFontClearSpecial(sf->subfonts[i]);
3338  if (sf->groups) { GlyphGroupsFree(sf->groups); sf->groups = NULL; }
3339  if (sf->groupkerns) { GlyphGroupKernsFree(sf->groupkerns); sf->groupkerns = NULL; }
3340  if (sf->groupvkerns) { GlyphGroupKernsFree(sf->groupvkerns); sf->groupvkerns = NULL; }
3341  if (sf->python_persistent) {
3342 #if defined(_NO_PYTHON)
3343  free( sf->python_persistent ); /* It's a string of pickled data which we leave as a string */
3344 #else
3345  PyFF_FreeSF(sf);
3346 #endif
3347  sf->python_persistent = NULL;
3348  }
3349  if (sf->layers != NULL) {
3350  int layer;
3351  for (layer = 0; layer < sf->layer_cnt; layer ++) {
3352  if (sf->layers[layer].ufo_path != NULL) {
3353  free(sf->layers[layer].ufo_path);
3354  sf->layers[layer].ufo_path = NULL;
3355  }
3356  }
3357  }
3358 }
3359 
3360 #if 0
3361 // These are in splinefont.h.
3362 #define GROUP_NAME_KERNING_UFO 1
3363 #define GROUP_NAME_KERNING_FEATURE 2
3364 #define GROUP_NAME_VERTICAL 4 // Otherwise horizontal.
3365 #define GROUP_NAME_RIGHT 8 // Otherwise left (or above).
3366 #endif // 0
3367 
3368 
3370  if (group->classname != NULL) free(group->classname);
3371  if (group->glyphs != NULL) free(group->glyphs);
3372  free(group);
3373 }
3374 
3376  struct ff_glyphclasses* current = root;
3377  struct ff_glyphclasses* next;
3378  while (current != NULL) {
3379  next = current->next;
3381  current = next;
3382  }
3383 }
3384 
3385 void GlyphGroupKernFree(struct ff_rawoffsets* groupkern) {
3386  if (groupkern->left != NULL) free(groupkern->left);
3387  if (groupkern->right != NULL) free(groupkern->right);
3388  free(groupkern);
3389 }
3390 
3392  struct ff_rawoffsets* current = root;
3393  struct ff_rawoffsets* next;
3394  while (current != NULL) {
3395  next = current->next;
3397  current = next;
3398  }
3399 }
3400 
3401 
3402 #ifdef FF_UTHASH_GLIF_NAMES
3403 int HashKerningClassNamesFlex(SplineFont *sf, struct glif_name_index * class_name_hash, int capitalize) {
3404  struct kernclass *current_kernclass;
3405  int isv;
3406  int isr;
3407  int i;
3408  int absolute_index = 0; // This gives us a unique index for each kerning class.
3409  // First we catch the existing names.
3410  absolute_index = 0;
3411  for (isv = 0; isv < 2; isv++)
3412  for (current_kernclass = (isv ? sf->vkerns : sf->kerns); current_kernclass !=