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-2008 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 <math.h>
29 #include "psfont.h"
30 #include "ustring.h"
31 #include "utype.h"
32 #ifdef HAVE_IEEEFP_H
33 # include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */
34 #endif
35 
36 /*#define DEBUG 1*/
37 
38 typedef struct quartic {
39  double a,b,c,d,e;
41 
42 
43 #ifdef HAVE_FABS
44 #define FABS(x) fabs((x))
45 #else
46 #define FABS(x) ((x)>=0?(x):(-(x)))
47 #endif
48 
49 
50 /* In an attempt to make allocation more efficient I just keep preallocated */
51 /* lists of certain common sizes. It doesn't seem to make much difference */
52 /* when allocating stuff, but does when freeing. If the extra complexity */
53 /* is bad then put: */
54 /* #define chunkalloc(size) gcalloc(1,size) */
55 /* #define chunkfree(item,size) free(item) */
56 /* into splinefont.h after (or instead of) the definition of chunkalloc()*/
57 
58 #ifndef chunkalloc
59 #define ALLOC_CHUNK 100 /* Number of small chunks to malloc at a time */
60 #if !defined(FONTFORGE_CONFIG_USE_LONGDOUBLE) && !defined(FONTFORGE_CONFIG_USE_DOUBLE)
61 # define CHUNK_MAX 100 /* Maximum size (in chunk units) that we are prepared to allocate */
62  /* The size of our data structures */
63 #else
64 # define CHUNK_MAX 129
65 #endif
66 # define CHUNK_UNIT sizeof(void *) /* will vary with the word size of */
67  /* the machine. if pointers are 64 bits*/
68  /* we may need twice as much space as for 32 bits */
69 
70 #ifdef FLAG
71 #undef FLAG
72 #define FLAG 0xbadcafe
73 #endif
74 
75 #ifdef CHUNKDEBUG
76 static int chunkdebug = 0; /* When this is set we never free anything, insuring that each chunk is unique */
77 #endif
78 
79 #if ALLOC_CHUNK>1
80 struct chunk { struct chunk *next; };
81 struct chunk2 { struct chunk2 *next; int flag; };
82 static struct chunk *chunklists[CHUNK_MAX] = { 0 };
83 #endif
84 
85 #if defined(FLAG) && ALLOC_CHUNK>1
86 void chunktest(void) {
87  int i;
88  struct chunk2 *c;
89 
90  for ( i=2; i<CHUNK_MAX; ++i )
91  for ( c=(struct chunk2 *) chunklists[i]; c!=NULL; c=c->next )
92  if ( c->flag!=FLAG ) {
93  fprintf( stderr, "Chunk memory list has been corrupted\n" );
94  abort();
95  }
96 }
97 #endif
98 
99 
100 
101 void *chunkalloc(int size) {
102 # if ALLOC_CHUNK<=1
103 return( gcalloc(1,size));
104 # else
105  struct chunk *item;
106  int index;
107 
108  if ( size&(CHUNK_UNIT-1) )
109  size = (size+CHUNK_UNIT-1)&~(CHUNK_UNIT-1);
110 
111  if ( (size&(CHUNK_UNIT-1)) || size>=(int)(CHUNK_MAX*CHUNK_UNIT) || size<=(int)sizeof(struct chunk)) {
112  fprintf( stderr, "Attempt to allocate something of size %d\n", size );
113 return( gcalloc(1,size));
114  }
115 #ifdef FLAG
116  chunktest();
117 #endif
119  if ( chunklists[index]==NULL ) {
120  char *pt, *end;
122  chunklists[index] = (struct chunk *) pt;
123  end = pt+(ALLOC_CHUNK-1)*size;
124  while ( pt<end ) {
125  ((struct chunk *) pt)->next = (struct chunk *) (pt + size);
126 #ifdef FLAG
127  ((struct chunk2 *) pt)->flag = FLAG;
128 #endif
129  pt += size;
130  }
131  ((struct chunk *) pt)->next = NULL;
132 #ifdef FLAG
133  ((struct chunk2 *) pt)->flag = FLAG;
134 #endif
135  }
136  item = chunklists[index];
137  chunklists[index] = item->next;
138  memset(item,'\0',size);
139 return( item );
140 # endif
141 }
142 
143 void chunkfree(void *item,int size) {
144  int index = (size+CHUNK_UNIT-1)/CHUNK_UNIT;
145 #ifdef CHUNKDEBUG
146  if ( chunkdebug )
147 return;
148 #endif
149 # if ALLOC_CHUNK<=1
150  free(item);
151 # else
152  if ( item==NULL )
153 return;
154 
155  if ( size&(CHUNK_UNIT-1) )
156  size = (size+CHUNK_UNIT-1)&~(CHUNK_UNIT-1);
157 
158  if ( (size&(CHUNK_UNIT-1)) || size>=(int)(CHUNK_MAX*CHUNK_UNIT) || size<=(int)sizeof(struct chunk)) {
159  fprintf( stderr, "Attempt to free something of size %d\n", size );
160  free(item);
161  } else {
162 #ifdef LOCAL_DEBUG
163  if ( (char *) (chunklists[index]) == (char *) item ||
164  ( ((char *) (chunklists[index]))<(char *) item &&
165  ((char *) (chunklists[index]))+size>(char *) item) ||
166  ( ((char *) (chunklists[index]))>(char *) item &&
167  ((char *) (chunklists[index]))<((char *) item)+size))
168  IError( "Memory mixup. Chunk list is wrong!!!" );
169 #endif
170  ((struct chunk *) item)->next = chunklists[index];
171 # ifdef FLAG
172  if ( size>=sizeof(struct chunk2))
173  ((struct chunk2 *) item)->flag = FLAG;
174 # endif
175  chunklists[index] = (struct chunk *) item;
176  }
177 # ifdef FLAG
178  chunktest();
179 # endif
180 # endif
181 }
182 #endif
183 
184 
185 
186 
187 char *strconcat(const char *str1,const char *str2) {
188  int len1 = strlen(str1);
189  char *ret = galloc(len1+strlen(str2)+1);
190  strcpy(ret,str1);
191  strcpy(ret+len1,str2);
192 return( ret );
193 }
194 
195 char *strconcat3(const char *str1,const char *str2, const char *str3) {
196  int len1 = strlen(str1), len2 = strlen(str2);
197  char *ret = galloc(len1+len2+strlen(str3)+1);
198  strcpy(ret,str1);
199  strcpy(ret+len1,str2);
200  strcpy(ret+len1+len2,str3);
201 return( ret );
202 }
203 
205  LineList *next;
206 
207  while ( ll!=NULL ) {
208  next = ll->next;
209  chunkfree(ll,sizeof(LineList));
210  ll = next;
211  }
212 }
213 
216 
217  while ( la!=NULL ) {
218  next = la->next;
219  LineListFree(la->lines);
220  chunkfree(la,sizeof(LinearApprox));
221  la = next;
222  }
223 }
224 
227  chunkfree(spline,sizeof(Spline));
228 }
229 
231  SplinePoint *sp = chunkalloc(sizeof(SplinePoint));
232  sp->me.x = x; sp->me.y = y;
233  sp->nextcp = sp->prevcp = sp->me;
234  sp->nonextcp = sp->noprevcp = true;
235  sp->nextcpdef = sp->prevcpdef = false;
236  sp->ttfindex = sp->nextcpindex = 0xfffe;
237 return( sp );
238 }
239 
241  Spline *spline = chunkalloc(sizeof(Spline));
242 
243  spline->from = from; spline->to = to;
244  from->next = to->prev = spline;
246 return( spline );
247 }
248 
250  chunkfree(sp->hintmask,sizeof(HintMask));
251  chunkfree(sp,sizeof(SplinePoint));
252 }
253 
255  MinimumDistance *md, *prev, *next;
256 
257  if ( sc!=NULL ) {
258  prev = NULL;
259  for ( md = sc->md; md!=NULL; md = next ) {
260  next = md->next;
261  if ( md->sp1==sp || md->sp2==sp ) {
262  if ( prev==NULL )
263  sc->md = next;
264  else
265  prev->next = next;
266  chunkfree(md,sizeof(MinimumDistance));
267  } else
268  prev = md;
269  }
270  }
271 
272  chunkfree(sp->hintmask,sizeof(HintMask));
273  chunkfree(sp,sizeof(SplinePoint));
274 }
275 
277  Spline *first, *spline, *next;
278  int nonext;
279 
280  if ( spl==NULL )
281 return;
282  nonext = spl->first->next==NULL;
283  if ( spl->first!=NULL ) {
284  first = NULL;
285  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline = next ) {
286  next = spline->to->next;
289  if ( first==NULL ) first = spline;
290  }
291  if ( spl->last!=spl->first || nonext )
292  SplinePointFree(spl->first);
293  }
294 }
295 
297  Spline *first, *spline, *next;
298  int nonext;
299 
300  if ( spl==NULL )
301 return;
302  if ( spl->first!=NULL ) {
303  nonext = spl->first->next==NULL;
304  first = NULL;
305  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline = next ) {
306  next = spline->to->next;
309  if ( first==NULL ) first = spline;
310  }
311  if ( spl->last!=spl->first || nonext )
312  SplinePointFree(spl->first);
313  }
314  spl->first = spl->last = NULL;
315 }
316 
318  Spline *first, *spline, *next;
319  int nonext;
320 
321  if ( spl==NULL )
322 return;
323  if ( spl->first!=NULL ) {
324  nonext = spl->first->next==NULL;
325  first = NULL;
326  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline = next ) {
327  next = spline->to->next;
330  if ( first==NULL ) first = spline;
331  }
332  if ( spl->last!=spl->first || nonext )
333  SplinePointFree(spl->first);
334  }
335  free(spl->contour_name);
336  chunkfree(spl,sizeof(SplinePointList));
337 }
338 
340  Spline *first, *spline, *next;
341  int freefirst;
342 
343  if ( spl==NULL )
344 return;
345  if ( spl->first!=NULL ) {
346  first = NULL;
347  freefirst = ( spl->last!=spl->first || spl->first->next==NULL );
348  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline = next ) {
349  next = spline->to->next;
352  if ( first==NULL ) first = spline;
353  }
354  if ( freefirst )
355  SplinePointMDFree(sc,spl->first);
356  }
357  free(spl->contour_name);
358  chunkfree(spl,sizeof(SplinePointList));
359 }
360 
363 
364  while ( spl!=NULL ) {
365  next = spl->next;
367  spl = next;
368  }
369 }
370 
372  SplinePointList *spl, *next;
373 
374  for ( spl=head; spl!=NULL; spl=next ) {
375  next = spl->next;
376  SplinePointListFree(spl);
377  }
378 }
379 
381  ImageList *inext;
382 
383  while ( imgs!=NULL ) {
384  inext = imgs->next;
385  chunkfree(imgs,sizeof(ImageList));
386  imgs = inext;
387  }
388 }
389 
391  int i;
392 
393  if ( ref==NULL )
394 return;
395  for ( i=0; i<ref->layer_cnt; ++i ) {
396  SplinePointListsFree(ref->layers[i].splines);
397  ImageListsFree(ref->layers[i].images);
398  }
399  free(ref->layers);
400  chunkfree(ref,sizeof(RefChar));
401 }
402 
404  RefChar *ref = chunkalloc(sizeof(RefChar));
405  ref->layer_cnt = 1;
406  ref->layers = gcalloc(1,sizeof(struct reflayer));
407  ref->round_translation_to_grid = true;
408 return( ref );
409 }
410 
412  RefChar *rnext;
413 
414  while ( ref!=NULL ) {
415  rnext = ref->next;
416  RefCharFree(ref);
417  ref = rnext;
418  }
419 }
420 
421 
422 typedef struct spline1 {
423  Spline1D sp;
427 
429  bigreal s = (t1-t0);
430  if ( sp->a==0 && sp->b==0 ) {
431  sp1->sp.d = sp->d + t0*sp->c;
432  sp1->sp.c = s*sp->c;
433  sp1->sp.b = sp1->sp.a = 0;
434  } else {
435  sp1->sp.d = sp->d + t0*(sp->c + t0*(sp->b + t0*sp->a));
436  sp1->sp.c = s*(sp->c + t0*(2*sp->b + 3*sp->a*t0));
437  sp1->sp.b = s*s*(sp->b+3*sp->a*t0);
438  sp1->sp.a = s*s*s*sp->a;
439 #if 0 /* Got invoked once on a perfectly good spline */
440  sp1->s1 = sp1->sp.a+sp1->sp.b+sp1->sp.c+sp1->sp.d;
441  if ( ((sp1->s1>.001 || sp1->s1<-.001) && !RealNear((double) sp1->sp.a+sp1->sp.b+sp1->sp.c+sp1->sp.d,sp1->s1)) ||
442  !RealNear(sp1->sp.d,sp1->s0))
443  IError( "Created spline does not work in FigureSpline1");
444 #endif
445  }
446  sp1->c0 = sp1->sp.c/3 + sp1->sp.d;
447  sp1->c1 = sp1->c0 + (sp1->sp.b+sp1->sp.c)/3;
448 }
449 
450 
451 static void SplineFindBounds(const Spline *sp, DBounds *bounds) {
452  real t, b2_fourac, v;
453  real min, max;
454  const Spline1D *sp1;
455  int i;
456 
457  /* first try the end points */
458  for ( i=0; i<2; ++i ) {
459  sp1 = &sp->splines[i];
460  if ( i==0 ) {
461  if ( sp->to->me.x<bounds->minx ) bounds->minx = sp->to->me.x;
462  if ( sp->to->me.x>bounds->maxx ) bounds->maxx = sp->to->me.x;
463  min = bounds->minx; max = bounds->maxx;
464  } else {
465  if ( sp->to->me.y<bounds->miny ) bounds->miny = sp->to->me.y;
466  if ( sp->to->me.y>bounds->maxy ) bounds->maxy = sp->to->me.y;
467  min = bounds->miny; max = bounds->maxy;
468  }
469 
470  /* then try the extrema of the spline (assuming they are between t=(0,1) */
471  /* (I don't bother fixing up for tiny rounding errors here. they don't matter */
472  /* But we could call CheckExtremaForSingleBitErrors */
473  if ( sp1->a!=0 ) {
474  b2_fourac = 4*sp1->b*sp1->b - 12*sp1->a*sp1->c;
475  if ( b2_fourac>=0 ) {
476  b2_fourac = sqrt(b2_fourac);
477  t = (-2*sp1->b + b2_fourac) / (6*sp1->a);
478  if ( t>0 && t<1 ) {
479  v = ((sp1->a*t+sp1->b)*t+sp1->c)*t + sp1->d;
480  if ( v<min ) min = v;
481  if ( v>max ) max = v;
482  }
483  t = (-2*sp1->b - b2_fourac) / (6*sp1->a);
484  if ( t>0 && t<1 ) {
485  v = ((sp1->a*t+sp1->b)*t+sp1->c)*t + sp1->d;
486  if ( v<min ) min = v;
487  if ( v>max ) max = v;
488  }
489  }
490  } else if ( sp1->b!=0 ) {
491  t = -sp1->c/(2.0*sp1->b);
492  if ( t>0 && t<1 ) {
493  v = (sp1->b*t+sp1->c)*t + sp1->d;
494  if ( v<min ) min = v;
495  if ( v>max ) max = v;
496  }
497  }
498  if ( i==0 ) {
499  bounds->minx = min; bounds->maxx = max;
500  } else {
501  bounds->miny = min; bounds->maxy = max;
502  }
503  }
504 }
505 
506 static void _SplineSetFindBounds(const SplinePointList *spl, DBounds *bounds) {
507  Spline *spline, *first;
508  /* Ignore contours consisting of a single point (used for hinting, anchors */
509  /* for mark to base, etc. */
510 
511  for ( ; spl!=NULL; spl = spl->next ) if ( spl->first->next!=NULL && spl->first->next->to != spl->first ) {
512  first = NULL;
513  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 ) {
514  bounds->minx = bounds->maxx = spl->first->me.x;
515  bounds->miny = bounds->maxy = spl->first->me.y;
516  } else {
517  if ( spl->first->me.x<bounds->minx ) bounds->minx = spl->first->me.x;
518  if ( spl->first->me.x>bounds->maxx ) bounds->maxx = spl->first->me.x;
519  if ( spl->first->me.y<bounds->miny ) bounds->miny = spl->first->me.y;
520  if ( spl->first->me.y>bounds->maxy ) bounds->maxy = spl->first->me.y;
521  }
522  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
523  SplineFindBounds(spline,bounds);
524  if ( first==NULL ) first = spline;
525  }
526  }
527 }
528 
529 
530 void SplineSetFindBounds(const SplinePointList *spl, DBounds *bounds) {
531  memset(bounds,'\0',sizeof(*bounds));
532  _SplineSetFindBounds(spl,bounds);
533 }
534 
536  RefChar *rf;
537 
538  for ( rf=sc->layers[layer].refs; rf!=NULL; rf = rf->next ) {
539  if ( bounds->minx==0 && bounds->maxx==0 && bounds->miny==0 && bounds->maxy == 0 )
540  *bounds = rf->bb;
541  else if ( rf->bb.minx!=0 || rf->bb.maxx != 0 || rf->bb.maxy != 0 || rf->bb.miny!=0 ) {
542  if ( rf->bb.minx < bounds->minx ) bounds->minx = rf->bb.minx;
543  if ( rf->bb.miny < bounds->miny ) bounds->miny = rf->bb.miny;
544  if ( rf->bb.maxx > bounds->maxx ) bounds->maxx = rf->bb.maxx;
545  if ( rf->bb.maxy > bounds->maxy ) bounds->maxy = rf->bb.maxy;
546  }
547  }
548  _SplineSetFindBounds(sc->layers[layer].splines,bounds);
549 
550  if ( sc->parent!=NULL && sc->parent->strokedfont &&
551  (bounds->minx!=bounds->maxx || bounds->miny!=bounds->maxy)) {
552  real sw = sc->parent->strokewidth;
553  bounds->minx -= sw; bounds->miny -= sw;
554  bounds->maxx += sw; bounds->maxy += sw;
555  }
556 }
557 
559 
560  if ( sc->parent!=NULL && sc->parent->multilayer ) {
561  SplineCharFindBounds(sc,bounds);
562 return;
563  }
564 
565  /* a char with no splines (ie. a space) must have an lbearing of 0 */
566  bounds->minx = bounds->maxx = 0;
567  bounds->miny = bounds->maxy = 0;
568 
570 }
571 
573  int i;
574  int first,last;
575 
576  /* a char with no splines (ie. a space) must have an lbearing of 0 */
577  bounds->minx = bounds->maxx = 0;
578  bounds->miny = bounds->maxy = 0;
579 
580  first = last = ly_fore;
581  if ( sc->parent!=NULL && sc->parent->multilayer )
582  last = sc->layer_cnt-1;
583  for ( i=first; i<=last; ++i )
585 }
586 
588  int i, k, first, last;
589  (void)layer;
590  if ( sf->multilayer ) {
591  SplineFontFindBounds(sf,bounds);
592 return;
593  }
594 
595  bounds->minx = bounds->maxx = 0;
596  bounds->miny = bounds->maxy = 0;
597 
598  for ( i = 0; i<sf->glyphcnt; ++i ) {
599  SplineChar *sc = sf->glyphs[i];
600  if ( sc!=NULL ) {
601  first = last = ly_fore;
602  if ( sc->parent != NULL && sc->parent->multilayer )
603  last = sc->layer_cnt-1;
604  for ( k=first; k<=last; ++k )
606  }
607  }
608 }
609 
611  int i, k, first, last;
612 
613  bounds->minx = bounds->maxx = 0;
614  bounds->miny = bounds->maxy = 0;
615 
616  for ( i = 0; i<sf->glyphcnt; ++i ) {
617  SplineChar *sc = sf->glyphs[i];
618  if ( sc!=NULL ) {
619  first = last = ly_fore;
620  if ( sf->multilayer )
621  last = sc->layer_cnt-1;
622  for ( k=first; k<=last; ++k )
624  }
625  }
626 }
627 
628 void CIDLayerFindBounds(SplineFont *cidmaster,int layer,DBounds *bounds) {
629  SplineFont *sf;
630  int i;
631  DBounds b;
632  real factor;
633 
634  if ( cidmaster->cidmaster )
635  cidmaster = cidmaster->cidmaster;
636  if ( cidmaster->subfonts==NULL ) {
637  SplineFontLayerFindBounds(cidmaster,layer,bounds);
638 return;
639  }
640 
641  sf = cidmaster->subfonts[0];
643  factor = 1000.0/(sf->ascent+sf->descent);
644  bounds->maxx *= factor; bounds->minx *= factor; bounds->miny *= factor; bounds->maxy *= factor;
645  for ( i=1; i<cidmaster->subfontcnt; ++i ) {
646  sf = cidmaster->subfonts[i];
648  factor = 1000.0/(sf->ascent+sf->descent);
649  b.maxx *= factor; b.minx *= factor; b.miny *= factor; b.maxy *= factor;
650  if ( b.maxx>bounds->maxx ) bounds->maxx = b.maxx;
651  if ( b.maxy>bounds->maxy ) bounds->maxy = b.maxy;
652  if ( b.miny<bounds->miny ) bounds->miny = b.miny;
653  if ( b.minx<bounds->minx ) bounds->minx = b.minx;
654  }
655 }
656 
658  SplinePoint *sp;
659 
660  for ( ; ss!=NULL; ss=ss->next ) {
661  for ( sp=ss->first; ; ) {
662  if ( sp->me.y > top->y ) *top = sp->me;
663  if ( sp->next==NULL )
664  break;
665  sp = sp->next->to;
666  if ( sp==ss->first )
667  break;
668  }
669  }
670 }
671 
673 
674  top->y = -1e10;
676  if ( top->y < -65536 ) top->y = top->x = 0;
677 }
678 
680  SplinePoint *sp;
681 
682  b->minx = b->miny = 1e10;
683  b->maxx = b->maxy = -1e10;
684  for ( ; ss!=NULL; ss=ss->next ) {
685  for ( sp=ss->first; ; ) {
686  if ( sp->me.y < b->miny ) b->miny = sp->me.y;
687  if ( sp->me.x < b->minx ) b->minx = sp->me.x;
688  if ( sp->me.y > b->maxy ) b->maxy = sp->me.y;
689  if ( sp->me.x > b->maxx ) b->maxx = sp->me.x;
690  if ( sp->next==NULL )
691  break;
692  sp = sp->next->to;
693  if ( sp==ss->first )
694  break;
695  }
696  }
697  if ( b->minx>65536 ) b->minx = 0;
698  if ( b->miny>65536 ) b->miny = 0;
699  if ( b->maxx<-65536 ) b->maxx = 0;
700  if ( b->maxy<-65536 ) b->maxy = 0;
701 }
702 
704  RefChar *ref;
705  int i,first, last;
706  DBounds temp;
707 
708  memset(b,0,sizeof(*b));
709  first = last = ly_fore;
710  if ( sc->parent!=NULL && sc->parent->multilayer )
711  last = sc->layer_cnt-1;
712  for ( i=first; i<=last; ++i ) {
713  SplineSetQuickBounds(sc->layers[i].splines,&temp);
714  if ( temp.minx!=0 || temp.maxx != 0 || temp.maxy != 0 || temp.miny!=0 ) {
715  if ( temp.minx < b->minx ) b->minx = temp.minx;
716  if ( temp.miny < b->miny ) b->miny = temp.miny;
717  if ( temp.maxx > b->maxx ) b->maxx = temp.maxx;
718  if ( temp.maxy > b->maxy ) b->maxy = temp.maxy;
719  }
720  for ( ref = sc->layers[i].refs; ref!=NULL; ref = ref->next ) {
721  /*SplineSetQuickBounds(ref->layers[0].splines,&temp);*/
722  if ( b->minx==0 && b->maxx==0 && b->miny==0 && b->maxy == 0 )
723  *b = ref->bb;
724  else if ( ref->bb.minx!=0 || ref->bb.maxx != 0 || ref->bb.maxy != 0 || ref->bb.miny!=0 ) {
725  if ( ref->bb.minx < b->minx ) b->minx = ref->bb.minx;
726  if ( ref->bb.miny < b->miny ) b->miny = ref->bb.miny;
727  if ( ref->bb.maxx > b->maxx ) b->maxx = ref->bb.maxx;
728  if ( ref->bb.maxy > b->maxy ) b->maxy = ref->bb.maxy;
729  }
730  }
731  }
732  if ( sc->parent!=NULL && sc->parent->strokedfont &&
733  (b->minx!=b->maxx || b->miny!=b->maxy)) {
734  real sw = sc->parent->strokewidth;
735  b->minx -= sw; b->miny -= sw;
736  b->maxx += sw; b->maxy += sw;
737  }
738 }
739 
741  SplinePoint *sp;
742 
743  b->minx = b->miny = 1e10;
744  b->maxx = b->maxy = -1e10;
745  for ( ; ss!=NULL; ss=ss->next ) {
746  for ( sp=ss->first; ; ) {
747  if ( sp->me.y < b->miny ) b->miny = sp->me.y;
748  if ( sp->me.x < b->minx ) b->minx = sp->me.x;
749  if ( sp->me.y > b->maxy ) b->maxy = sp->me.y;
750  if ( sp->me.x > b->maxx ) b->maxx = sp->me.x;
751  if ( sp->nextcp.y < b->miny ) b->miny = sp->nextcp.y;
752  if ( sp->nextcp.x < b->minx ) b->minx = sp->nextcp.x;
753  if ( sp->nextcp.y > b->maxy ) b->maxy = sp->nextcp.y;
754  if ( sp->nextcp.x > b->maxx ) b->maxx = sp->nextcp.x;
755  if ( sp->prevcp.y < b->miny ) b->miny = sp->prevcp.y;
756  if ( sp->prevcp.x < b->minx ) b->minx = sp->prevcp.x;
757  if ( sp->prevcp.y > b->maxy ) b->maxy = sp->prevcp.y;
758  if ( sp->prevcp.x > b->maxx ) b->maxx = sp->prevcp.x;
759  if ( sp->next==NULL )
760  break;
761  sp = sp->next->to;
762  if ( sp==ss->first )
763  break;
764  }
765  }
766  if ( b->minx>65536 ) b->minx = 0;
767  if ( b->miny>65536 ) b->miny = 0;
768  if ( b->maxx<-65536 ) b->maxx = 0;
769  if ( b->maxy<-65536 ) b->maxy = 0;
770 }
771 
773  RefChar *ref;
774  int i, first,last;
775  DBounds temp;
776 
777  memset(b,0,sizeof(*b));
778  first = last = ly_fore;
779  if ( sc->parent!=NULL && sc->parent->multilayer )
780  last = sc->layer_cnt-1;
781  for ( i=first; i<=last; ++i ) {
782  SplineSetQuickConservativeBounds(sc->layers[i].splines,&temp);
783  if ( temp.minx!=0 || temp.maxx != 0 || temp.maxy != 0 || temp.miny!=0 ) {
784  if ( temp.minx < b->minx ) b->minx = temp.minx;
785  if ( temp.miny < b->miny ) b->miny = temp.miny;
786  if ( temp.maxx > b->maxx ) b->maxx = temp.maxx;
787  if ( temp.maxy > b->maxy ) b->maxy = temp.maxy;
788  }
789  for ( ref = sc->layers[i].refs; ref!=NULL; ref = ref->next ) {
790  /*SplineSetQuickConservativeBounds(ref->layers[0].splines,&temp);*/
791  if ( b->minx==0 && b->maxx==0 && b->miny==0 && b->maxy == 0 )
792  *b = ref->bb;
793  else if ( ref->bb.minx!=0 || ref->bb.maxx != 0 || ref->bb.maxy != 0 || ref->bb.miny!=0 ) {
794  if ( ref->bb.minx < b->minx ) b->minx = ref->bb.minx;
795  if ( ref->bb.miny < b->miny ) b->miny = ref->bb.miny;
796  if ( ref->bb.maxx > b->maxx ) b->maxx = ref->bb.maxx;
797  if ( ref->bb.maxy > b->maxy ) b->maxy = ref->bb.maxy;
798  }
799  }
800  }
801  if ( sc->parent->strokedfont && (b->minx!=b->maxx || b->miny!=b->maxy)) {
802  real sw = sc->parent->strokewidth;
803  b->minx -= sw; b->miny -= sw;
804  b->maxx += sw; b->maxy += sw;
805  }
806 }
807 
809  DBounds bb;
810  int i;
811 
812  b->minx = b->miny = 1e10;
813  b->maxx = b->maxy = -1e10;
814  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL ) {
815  SplineCharQuickConservativeBounds(sf->glyphs[i],&bb);
816  if ( bb.minx < b->minx ) b->minx = bb.minx;
817  if ( bb.miny < b->miny ) b->miny = bb.miny;
818  if ( bb.maxx > b->maxx ) b->maxx = bb.maxx;
819  if ( bb.maxy > b->maxy ) b->maxy = bb.maxy;
820  }
821  if ( b->minx>65536 ) b->minx = 0;
822  if ( b->miny>65536 ) b->miny = 0;
823  if ( b->maxx<-65536 ) b->maxx = 0;
824  if ( b->maxy<-65536 ) b->maxy = 0;
825 }
826 
828  int oldpointtype = sp->pointtype;
829 
830  sp->pointtype = pt_corner;
831  if ( sp->next==NULL && sp->prev==NULL )
832  ;
833  else if ( (sp->next!=NULL && sp->next->to->me.x==sp->me.x && sp->next->to->me.y==sp->me.y) ||
834  (sp->prev!=NULL && sp->prev->from->me.x==sp->me.x && sp->prev->from->me.y==sp->me.y ))
835  ;
836  else if ( sp->next==NULL ) {
837  sp->pointtype = sp->noprevcp ? pt_corner : pt_curve;
838  } else if ( sp->prev==NULL ) {
839  sp->pointtype = sp->nonextcp ? pt_corner : pt_curve;
840  } else if ( sp->nonextcp && sp->noprevcp ) {
841  ;
842  } else {
843  BasePoint ndir, ncdir, ncunit, pdir, pcdir, pcunit;
844  double nlen, nclen, plen, pclen;
845  double dot;
846 
847  ncdir.x = sp->nextcp.x - sp->me.x; ncdir.y = sp->nextcp.y - sp->me.y;
848  pcdir.x = sp->prevcp.x - sp->me.x; pcdir.y = sp->prevcp.y - sp->me.y;
849  ndir.x = ndir.y = pdir.x = pdir.y = 0;
850  if ( sp->next!=NULL ) {
851  ndir.x = sp->next->to->me.x - sp->me.x; ndir.y = sp->next->to->me.y - sp->me.y;
852  }
853  if ( sp->prev!=NULL ) {
854  pdir.x = sp->prev->from->me.x - sp->me.x; pdir.y = sp->prev->from->me.y - sp->me.y;
855  }
856  nclen = sqrt(ncdir.x*ncdir.x + ncdir.y*ncdir.y);
857  pclen = sqrt(pcdir.x*pcdir.x + pcdir.y*pcdir.y);
858  nlen = sqrt(ndir.x*ndir.x + ndir.y*ndir.y);
859  plen = sqrt(pdir.x*pdir.x + pdir.y*pdir.y);
860  ncunit = ncdir; pcunit = pcdir;
861  if ( nclen!=0 ) { ncunit.x /= nclen; ncunit.y /= nclen; }
862  if ( pclen!=0 ) { pcunit.x /= pclen; pcunit.y /= pclen; }
863  if ( nlen!=0 ) { ndir.x /= nlen; ndir.y /= nlen; }
864  if ( plen!=0 ) { pdir.x /= plen; pdir.y /= plen; }
865 
866  /* find out which side has the shorter control vector. Dot that vector */
867  /* with the normal of the unit vector on the other side. If the */
868  /* result is less than 1 em-unit then we've got colinear control points */
869  /* (within the resolution of the integer grid) */
870  if ( nclen!=0 && pclen!=0 &&
871  ((nclen>=pclen && (dot = pcdir.x*ncunit.y - pcdir.y*ncunit.x)<1.0 && dot>-1.0 ) ||
872  (pclen>nclen && (dot = ncdir.x*pcunit.y - ncdir.y*pcunit.x)<1.0 && dot>-1.0 )))
873  sp->pointtype = pt_curve;
874  /* Dot product of control point with unit vector normal to line in */
875  /* opposite direction should be less than an em-unit for a tangent */
876  else if (( nclen==0 && pclen!=0 && (dot = pcdir.x*ndir.y-pcdir.y*ndir.x)<1.0 && dot>-1.0 ) ||
877  ( pclen==0 && nclen!=0 && (dot = ncdir.x*pdir.y-ncdir.y*pdir.x)<1.0 && dot>-1.0 ))
878  sp->pointtype = pt_tangent;
879 
880  /* If a point started out hv, and could still be hv, them make it so */
881  /* but don't make hv points de novo, Alexey doesn't like change */
882  /* (this only works because hv isn't a default setting, so if it's */
883  /* there it was done intentionally) */
884  if ( sp->pointtype == pt_curve && oldpointtype == pt_hvcurve &&
885  ((sp->nextcp.x==sp->me.x && sp->prevcp.x==sp->me.x && sp->nextcp.y!=sp->me.y) ||
886  (sp->nextcp.y==sp->me.y && sp->prevcp.y==sp->me.y && sp->nextcp.x!=sp->me.x)))
887  sp->pointtype = pt_hvcurve;
888  }
889 }
890 
892  enum pointtype old = sp->pointtype, new;
893 
895  new = sp->pointtype;
896  sp->pointtype = old;
897 return( new==pt_corner );
898 }
899 
901  Spline *spline, *first, *last=NULL;
902 
903  for ( ; spl!=NULL; spl = spl->next ) {
904  first = NULL;
905  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
907  last = spline;
908  if ( first==NULL ) first = spline;
909  }
910  if ( spline==NULL && last!=NULL )
912  }
913 }
914 
916  SPLCatagorizePoints(sc->layers[ly_fore].splines);
917 }
918 
919 static int CharsNotInEncoding(FontDict *fd) {
920  int i, cnt, j;
921 
922  for ( i=cnt=0; i<fd->chars->cnt; ++i ) {
923  if ( fd->chars->keys[i]!=NULL ) {
924  for ( j=0; j<256; ++j )
925  if ( fd->encoding[j]!=NULL &&
926  strcmp(fd->encoding[j],fd->chars->keys[i])==0 )
927  break;
928  if ( j==256 )
929  ++cnt;
930  }
931  }
932  /* And for type 3 fonts... */
933  if ( fd->charprocs!=NULL ) for ( i=0; i<fd->charprocs->cnt; ++i ) {
934  if ( fd->charprocs->keys[i]!=NULL ) {
935  for ( j=0; j<256; ++j )
936  if ( fd->encoding[j]!=NULL &&
937  strcmp(fd->encoding[j],fd->charprocs->keys[i])==0 )
938  break;
939  if ( j==256 )
940  ++cnt;
941  }
942  }
943 return( cnt );
944 }
945 
946 static int LookupCharString(char *encname,struct pschars *chars) {
947  int k;
948 
949  if ( encname==NULL ) encname = ".notdef"; /* In case of an incomplete encoding array */
950 
951  for ( k=0; k<chars->cnt; ++k ) {
952  if ( chars->keys[k]!=NULL )
953  if ( strcmp(encname,chars->keys[k])==0 )
954 return( k );
955  }
956 return( -1 );
957 }
958 
961  const SplinePoint *pt; SplinePoint *cpt;
962  Spline *spline;
963 
964  cur = chunkalloc(sizeof(SplinePointList));
965  cur->is_clip_path = spl->is_clip_path;
966 
967  for ( pt=spl->first; ; ) {
968  cpt = chunkalloc(sizeof(SplinePoint));
969  *cpt = *pt;
970  if ( pt->hintmask!=NULL ) {
971  cpt->hintmask = chunkalloc(sizeof(HintMask));
972  memcpy(cpt->hintmask,pt->hintmask,sizeof(HintMask));
973  }
974  cpt->next = cpt->prev = NULL;
975  if ( cur->first==NULL )
976  cur->first = cur->last = cpt;
977  else {
978  spline = chunkalloc(sizeof(Spline));
979  *spline = *pt->prev;
980  spline->from = cur->last;
981  cur->last->next = spline;
982  cpt->prev = spline;
983  spline->to = cpt;
984  spline->approx = NULL;
985  cur->last = cpt;
986  }
987  if ( pt->next==NULL )
988  break;
989  pt = pt->next->to;
990  if ( pt==spl->first )
991  break;
992  }
993  if ( spl->first->prev!=NULL ) {
994  cpt = cur->first;
995  spline = chunkalloc(sizeof(Spline));
996  *spline = *pt->prev;
997  spline->from = cur->last;
998  cur->last->next = spline;
999  cpt->prev = spline;
1000  spline->to = cpt;
1001  spline->approx = NULL;
1002  cur->last = cpt;
1003  }
1004 return( cur );
1005 }
1006 
1007 /* If this routine is called we are guarenteed that:
1008  at least one point on the splineset is selected
1009  not all points on the splineset are selected
1010 */
1013  SplinePoint *cpt, *first, *start;
1014  Spline *spline;
1015 
1016  start = spl->first;
1017  if ( spl->first==spl->last ) {
1018  /* If it's a closed contour and the start point is selected then we */
1019  /* don't know where that selection began (and we have to keep it with */
1020  /* the things that precede it when we make the new splinesets), so */
1021  /* loop until we find something unselected */
1022  while ( start->selected )
1023  start = start->next->to;
1024  }
1025  first = NULL;
1026  while ( start != NULL && start!=first ) {
1027  while ( start!=NULL && start!=first && !start->selected ) {
1028  if ( first==NULL ) first = start;
1029  if ( start->next==NULL ) {
1030  start = NULL;
1031  break;
1032  }
1033  start = start->next->to;
1034  }
1035  if ( start==NULL || start==first )
1036  break;
1037  cur = chunkalloc(sizeof(SplinePointList));
1038  if ( head==NULL )
1039  head = cur;
1040  else
1041  last->next = cur;
1042  last = cur;
1043 
1044  while ( start!=NULL && start->selected && start!=first ) {
1045  cpt = chunkalloc(sizeof(SplinePoint));
1046  *cpt = *start;
1047  cpt->hintmask = NULL;
1048  cpt->next = cpt->prev = NULL;
1049  if ( cur->first==NULL )
1050  cur->first = cur->last = cpt;
1051  else {
1052  spline = chunkalloc(sizeof(Spline));
1053  *spline = *start->prev;
1054  spline->from = cur->last;
1055  cur->last->next = spline;
1056  cpt->prev = spline;
1057  spline->to = cpt;
1058  spline->approx = NULL;
1059  cur->last = cpt;
1060  }
1061  if ( first==NULL ) first = start;
1062  if ( start->next==NULL ) {
1063  start = NULL;
1064  break;
1065  }
1066  start = start->next->to;
1067  }
1068  }
1069 return( head );
1070 }
1071 
1072 
1075 
1076  for ( ; base!=NULL; base = base->next ) {
1078  if ( head==NULL )
1079  head = cur;
1080  else
1081  last->next = cur;
1082  last = cur;
1083  }
1084 return( head );
1085 }
1086 
1089  SplinePoint *pt, *first;
1090  int anysel, allsel;
1091 
1092  for ( ; base!=NULL; base = base->next ) {
1093  anysel = false; allsel = true;
1094  first = NULL;
1095  for ( pt=base->first; pt!=NULL && pt!=first; pt = pt->next->to ) {
1096  if ( pt->selected ) anysel = true;
1097  else allsel = false;
1098  if ( first==NULL ) first = pt;
1099  if ( pt->next==NULL )
1100  break;
1101  }
1102  if ( allsel )
1104  else if ( anysel )
1106  if ( anysel ) {
1107  if ( head==NULL )
1108  head = cur;
1109  else
1110  last->next = cur;
1111  for ( last = cur; last->next ; last = last->next );
1112  }
1113  }
1114 return( head );
1115 }
1116 
1117 
1118 
1121  SplinePoint *first, *start, *next;
1122 
1123  start = spl->first;
1124  if ( spl->first==spl->last ) {
1125  /* If it's a closed contour and the start point is selected then we */
1126  /* don't know where that selection began (and we have to keep it with */
1127  /* the things that precede it when we make the new splinesets), so */
1128  /* loop until we find something unselected */
1129  while ( !start->selected )
1130  start = start->next->to;
1131  }
1132  first = NULL;
1133  while ( start != NULL && start!=first ) {
1134  while ( start!=NULL && start!=first && start->selected ) {
1135  if ( first==NULL ) first = start;
1136  if ( start->prev!=NULL ) {
1137  start->prev->from->next = NULL;
1138  SplineFree(start->prev);
1139  }
1140  if ( start->next!=NULL ) {
1141  next = start->next->to;
1142  next->prev = NULL;
1143  SplineFree(start->next);
1144  } else
1145  next = NULL;
1147  start = next;
1148  }
1149  if ( start==NULL || start==first )
1150  break;
1151  if ( head==NULL ) {
1152  head = cur = spl;
1153  spl->first = spl->last = NULL;
1154  } else {
1155  cur = chunkalloc(sizeof(SplinePointList));
1156  last->next = cur;
1157  }
1158  last = cur;
1159 
1160  while ( start!=NULL && !start->selected && start!=first ) {
1161  if ( cur->first==NULL )
1162  cur->first = start;
1163  cur->last = start;
1164  if ( start->next!=NULL ) {
1165  next = start->next->to;
1166  if ( next->selected ) {
1167  SplineFree(start->next);
1168  start->next = NULL;
1169  next->prev = NULL;
1170  }
1171  } else
1172  next = NULL;
1173  if ( first==NULL ) first = start;
1174  start = next;
1175  }
1176  }
1177 return( last );
1178 }
1179 
1182  SplinePoint *pt, *first;
1183  int anysel, allsel;
1184 
1185  for ( ; base!=NULL; base = next ) {
1186  next = base->next;
1187  anysel = false; allsel = true;
1188  first = NULL;
1189  for ( pt=base->first; pt!=NULL && pt!=first; pt = pt->next->to ) {
1190  if ( pt->selected ) anysel = true;
1191  else allsel = false;
1192  if ( first==NULL ) first = pt;
1193  if ( pt->next==NULL )
1194  break;
1195  }
1196  if ( allsel ) {
1198  continue;
1199  }
1200  if ( !anysel ) {
1201  if ( head==NULL )
1202  head = base;
1203  else
1204  last->next = base;
1205  last = base;
1206  if ( anysel )
1208  }
1209  }
1210  if ( last!=NULL ) last->next = NULL;
1211 return( head );
1212 }
1213 
1215  ImageList *head=NULL, *last=NULL, *new;
1216 
1217  for ( ; cimg!=NULL; cimg=cimg->next ) {
1218  new = chunkalloc(sizeof(ImageList));
1219  *new = *cimg;
1220  new->next = NULL;
1221  if ( last==NULL )
1222  head = last = new;
1223  else {
1224  last->next = new;
1225  last = new;
1226  }
1227  }
1228 return( head );
1229 }
1230 
1231 
1233  BasePoint p;
1234  p.x = transform[0]*ap->me.x + transform[2]*ap->me.y + transform[4];
1235  p.y = transform[1]*ap->me.x + transform[3]*ap->me.y + transform[5];
1236  ap->me.x = rint(1024*p.x)/1024;
1237  ap->me.y = rint(1024*p.y)/1024;
1238 }
1239 
1241  BasePoint p;
1242  p.x = transform[0]*sp->me.x + transform[2]*sp->me.y + transform[4];
1243  p.y = transform[1]*sp->me.x + transform[3]*sp->me.y + transform[5];
1244  p.x = rint(1024*p.x)/1024;
1245  p.y = rint(1024*p.y)/1024;
1246  sp->me = p;
1247  if ( !sp->nonextcp ) {
1248  p.x = transform[0]*sp->nextcp.x + transform[2]*sp->nextcp.y + transform[4];
1249  p.y = transform[1]*sp->nextcp.x + transform[3]*sp->nextcp.y + transform[5];
1250  p.x = rint(1024*p.x)/1024;
1251  p.y = rint(1024*p.y)/1024;
1252  sp->nextcp = p;
1253  } else
1254  sp->nextcp = sp->me;
1255  if ( !sp->noprevcp ) {
1256  p.x = transform[0]*sp->prevcp.x + transform[2]*sp->prevcp.y + transform[4];
1257  p.y = transform[1]*sp->prevcp.x + transform[3]*sp->prevcp.y + transform[5];
1258  p.x = rint(1024*p.x)/1024;
1259  p.y = rint(1024*p.y)/1024;
1260  sp->prevcp = p;
1261  } else
1262  sp->prevcp = sp->me;
1263  if ( sp->pointtype == pt_hvcurve ) {
1264  if (
1265  ((sp->nextcp.x==sp->me.x && sp->prevcp.x==sp->me.x && sp->nextcp.y!=sp->me.y) ||
1266  (sp->nextcp.y==sp->me.y && sp->prevcp.y==sp->me.y && sp->nextcp.x!=sp->me.x)))
1267  /* Do Nothing */;
1268  else
1269  sp->pointtype = pt_curve;
1270  }
1271 }
1272 
1274  Spline *spline, *first;
1275  SplinePointList *spl;
1276  SplinePoint *spt, *pfirst;
1277  int allsel, anysel, alldone=true;
1278 
1279  for ( spl = base; spl!=NULL; spl = spl->next ) {
1280  pfirst = NULL;
1281  allsel = true; anysel=false;
1282  for ( spt = spl->first ; spt!=pfirst; spt = spt->next->to ) {
1283  if ( pfirst==NULL ) pfirst = spt;
1284  if ( allpoints || spt->selected ) {
1286  if ( !allpoints ) {
1287  if ( spt->next!=NULL && spt->next->order2 && !spt->next->to->selected && spt->next->to->ttfindex==0xffff ) {
1288  SplinePoint *to = spt->next->to;
1289  to->prevcp = spt->nextcp;
1290  to->me.x = (to->prevcp.x+to->nextcp.x)/2;
1291  to->me.y = (to->prevcp.y+to->nextcp.y)/2;
1292  }
1293  if ( spt->prev!=NULL && spt->prev->order2 && !spt->prev->from->selected && spt->prev->from->ttfindex==0xffff ) {
1294  SplinePoint *from = spt->prev->from;
1295  from->nextcp = spt->prevcp;
1296  from->me.x = (from->prevcp.x+from->nextcp.x)/2;
1297  from->me.y = (from->prevcp.y+from->nextcp.y)/2;
1298  }
1299  }
1300  anysel = true;
1301  } else
1302  allsel = alldone = false;
1303  if ( spt->next==NULL )
1304  break;
1305  }
1306  if ( !anysel ) /* This splineset had no selected points it's unchanged */
1307  continue;
1308 
1309  /* if we changed all the points then the control points are right */
1310  /* otherwise those near the edges may be wonky, fix 'em up */
1311  /* Figuring out where the edges of the selection are is difficult */
1312  /* so let's just tweak all points, it shouldn't matter */
1313  /* It does matter. Let's tweak all default points */
1314  if ( !allpoints && !allsel && spl->first->next!=NULL && !spl->first->next->order2 ) {
1315  pfirst = NULL;
1316  for ( spt = spl->first ; spt!=pfirst; spt = spt->next->to ) {
1317  if ( pfirst==NULL ) pfirst = spt;
1318  if ( spt->selected && spt->prev!=NULL && !spt->prev->from->selected &&
1319  spt->prev->from->pointtype == pt_tangent )
1321  if ( spt->selected && spt->next!=NULL && !spt->next->to->selected &&
1322  spt->next->to->pointtype == pt_tangent )
1324  if ( spt->prev!=NULL && spt->prevcpdef )
1326  if ( spt->next==NULL )
1327  break;
1328  if ( spt->nextcpdef )
1330  }
1331  }
1332  first = NULL;
1333  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
1334  if ( !alldone ) SplineRefigureFixup(spline); else SplineRefigure(spline);
1335  if ( first==NULL ) first = spline;
1336  }
1337  }
1338 return( base );
1339 }
1340 
1341 
1343  real transform[6];
1344  if ( xoff==0 )
1345 return( base );
1346  transform[0] = transform[3] = 1;
1347  transform[1] = transform[2] = transform[5] = 0;
1348  transform[4] = xoff;
1349 return( SplinePointListTransform(base,transform,allpoints));
1350 }
1351 
1353  SplineChar *basesc,HintMask *hm) {
1354  StemInfo *st, *st2;
1355  int hst_cnt, bcnt;
1356  real start, width;
1357  int i;
1358 
1359  if ( ref->transform[1]!=0 || ref->transform[2]!=0 )
1360 return(NULL);
1361 
1362  memset(hm,0,sizeof(HintMask));
1363  for ( st = ref->sc->hstem; st!=NULL; st=st->next ) {
1364  start = st->start*ref->transform[3] + ref->transform[5] + trans->y;
1365  width = st->width*ref->transform[3];
1366  for ( st2=basesc->hstem,bcnt=0; st2!=NULL; st2=st2->next, bcnt++ )
1367  if ( st2->start == start && st2->width == width )
1368  break;
1369  if ( st2!=NULL )
1370  (*hm)[bcnt>>3] |= (0x80>>(bcnt&7));
1371  }
1372  for ( st2=basesc->hstem,hst_cnt=0; st2!=NULL; st2=st2->next, hst_cnt++ );
1373 
1374  for ( st = ref->sc->vstem; st!=NULL; st=st->next ) {
1375  start = st->start*ref->transform[0] + ref->transform[4] + trans->x;
1376  width = st->width*ref->transform[0];
1377  for ( st2=basesc->vstem,bcnt=hst_cnt; st2!=NULL; st2=st2->next, bcnt++ )
1378  if ( st2->start == start && st2->width == width )
1379  break;
1380  if ( st2!=NULL )
1381  (*hm)[bcnt>>3] |= (0x80>>(bcnt&7));
1382  }
1383  for ( i=0; i<HntMax/8; ++i )
1384  if ( (*hm)[i]!=0 )
1385 return( hm );
1386 
1387 return( NULL );
1388 }
1389 
1391  SplineChar *basesc,SplineChar *subsc) {
1392  HintMask *newhm;
1393  StemInfo *st, *st2;
1394  int cnt, hst_cnt, bcnt;
1395  real start, width;
1396 
1397  if ( transform[1]!=0 || transform[2]!=0 )
1398 return( NULL );
1399 
1400  newhm = chunkalloc(sizeof(HintMask));
1401  for ( st = subsc->hstem,cnt = 0; st!=NULL; st=st->next, cnt++ ) {
1402  if ( (*oldhm)[cnt>>3]&(0x80>>(cnt&7)) ) {
1403  start = st->start*transform[3] + transform[5];
1404  width = st->width*transform[3];
1405  for ( st2=basesc->hstem,bcnt=0; st2!=NULL; st2=st2->next, bcnt++ )
1406  if ( st2->start == start && st2->width == width )
1407  break;
1408  if ( st2!=NULL )
1409  (*newhm)[bcnt>>3] |= (0x80>>(bcnt&7));
1410  }
1411  }
1412  for ( st2=basesc->hstem,hst_cnt=0; st2!=NULL; st2=st2->next, hst_cnt++ );
1413 
1414  for ( st = subsc->vstem; st!=NULL; st=st->next, cnt++ ) {
1415  if ( (*oldhm)[cnt>>3]&(0x80>>(cnt&7)) ) {
1416  start = st->start*transform[0] + transform[4];
1417  width = st->width*transform[0];
1418  for ( st2=basesc->vstem,bcnt=hst_cnt; st2!=NULL; st2=st2->next, bcnt++ )
1419  if ( st2->start == start && st2->width == width )
1420  break;
1421  if ( st2!=NULL )
1422  (*newhm)[bcnt>>3] |= (0x80>>(bcnt&7));
1423  }
1424  }
1425 return( newhm );
1426 }
1427 
1429  SplineChar *basesc, SplineChar *subsc, BasePoint *trans ) {
1430  SplinePointList *spl, *spl2, *head;
1431  SplinePoint *spt, *spt2, *pfirst;
1432  real transform[6];
1433  Spline *s, *first;
1434 
1436 
1437  transform[0] = transform[3] = 1; transform[1] = transform[2] = 0;
1438  transform[4] = trans->x; transform[5] = trans->y;
1439 
1440  for ( spl = head, spl2=base; spl!=NULL; spl = spl->next, spl2 = spl2->next ) {
1441  pfirst = NULL;
1442  for ( spt = spl->first, spt2 = spl2->first ; spt!=pfirst; spt = spt->next->to, spt2 = spt2->next->to ) {
1443  if ( pfirst==NULL ) pfirst = spt;
1445  if ( spt2->hintmask ) {
1446  chunkfree(spt->hintmask,sizeof(HintMask));
1447  spt->hintmask = HintMaskTransform(spt2->hintmask,transform,basesc,subsc);
1448  }
1449  if ( spt->next==NULL )
1450  break;
1451  }
1452  first = NULL;
1453  for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
1454  SplineRefigure(s);
1455  if ( first==NULL ) first = s;
1456  }
1457  }
1458 return( head );
1459 }
1460 
1462  real transform[6], SplineChar *basesc ) {
1463  SplinePointList *spl, *spl2, *head, *last=NULL, *cur, *base;
1464  SplinePoint *spt, *spt2, *pfirst;
1465  Spline *s, *first;
1466  real trans[6];
1467  RefChar *rf;
1468 
1469  base = subsc->layers[layer].splines;
1471  if ( head!=NULL )
1472  for ( last = head; last->next!=NULL; last=last->next );
1473 
1474  for ( spl = head, spl2=base; spl!=NULL; spl = spl->next, spl2=spl2->next ) {
1475  pfirst = NULL;
1476  for ( spt = spl->first, spt2 = spl2->first ; spt!=pfirst; spt = spt->next->to, spt2 = spt2->next->to ) {
1477  if ( pfirst==NULL ) pfirst = spt;
1479  if ( spt2->hintmask ) {
1480  chunkfree(spt->hintmask,sizeof(HintMask));
1481  spt->hintmask = HintMaskTransform(spt2->hintmask,transform,basesc,subsc);
1482  }
1483  if ( spt->next==NULL )
1484  break;
1485  }
1486  first = NULL;
1487  for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
1488  SplineRefigure(s);
1489  if ( first==NULL ) first = s;
1490  }
1491  }
1492  for ( rf=subsc->layers[layer].refs; rf!=NULL; rf=rf->next ) {
1493  trans[0] = rf->transform[0]*transform[0] +
1494  rf->transform[1]*transform[2];
1495  trans[1] = rf->transform[0]*transform[1] +
1496  rf->transform[1]*transform[3];
1497  trans[2] = rf->transform[2]*transform[0] +
1498  rf->transform[3]*transform[2];
1499  trans[3] = rf->transform[2]*transform[1] +
1500  rf->transform[3]*transform[3];
1501  trans[4] = rf->transform[4]*transform[0] +
1502  rf->transform[5]*transform[2] +
1503  transform[4];
1504  trans[5] = rf->transform[4]*transform[1] +
1505  rf->transform[5]*transform[3] +
1506  transform[5];
1508  if ( head==NULL )
1509  head = cur;
1510  else
1511  last->next = cur;
1512  if ( cur!=NULL ) {
1513  while ( cur->next!=NULL ) cur = cur->next;
1514  last = cur;
1515  }
1516  }
1517 return( head );
1518 }
1519 
1521  SplineChar *basesc, BasePoint *trans,int layer ) {
1522  real transform[6];
1523 
1524  memcpy(transform,r->transform,sizeof(transform));
1525  transform[4] += trans->x; transform[5] += trans->y;
1526 return( _SPLCopyTransformedHintMasks(r->sc,layer,transform,basesc));
1527 }
1528 
1530  Spline *spline, *first;
1531 
1532  for ( ; spl!=NULL; spl = spl->next ) {
1533  first = NULL;
1534  spl->first->selected = sel;
1535  for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
1536  spline->to->selected = sel;
1537  if ( first==NULL ) first = spline;
1538  }
1539  }
1540 }
1541 
1543  struct splinecharlist *dlist;
1544 
1545  if ( dependent->searcherdummy )
1546 return;
1547 
1548  for ( dlist=base->dependents; dlist!=NULL && dlist->sc!=dependent; dlist = dlist->next);
1549  if ( dlist==NULL ) {
1550  dlist = chunkalloc(sizeof(struct splinecharlist));
1551  dlist->sc = dependent;
1552  dlist->next = base->dependents;
1553  base->dependents = dlist;
1554  }
1555 }
1556 
1557 static void InstanciateReference(SplineFont *sf, RefChar *topref, RefChar *refs,
1558  real transform[6], SplineChar *dsc, int layer) {
1559  real trans[6];
1560  RefChar *rf;
1561  SplineChar *rsc;
1562  SplinePointList *spl, *new;
1563  int i;
1564 
1565  if ( !refs->checked ) {
1566  if ( refs->sc!=NULL )
1567  i = refs->sc->orig_pos; /* Can happen in type3 fonts */
1568  else for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
1569  if ( strcmp(sf->glyphs[i]->name,AdobeStandardEncoding[refs->adobe_enc])==0 )
1570  break;
1571  if ( i!=sf->glyphcnt && !sf->glyphs[i]->ticked ) {
1572  refs->checked = true;
1573  refs->sc = rsc = sf->glyphs[i];
1574  refs->orig_pos = rsc->orig_pos;
1575  refs->unicode_enc = rsc->unicodeenc;
1576  SCMakeDependent(dsc,rsc);
1577  } else {
1578  LogError( _("Couldn't find referenced character \"%s\" in %s\n"),
1579  AdobeStandardEncoding[refs->adobe_enc], dsc->name);
1580 return;
1581  }
1582  } else if ( refs->sc->ticked )
1583 return;
1584 
1585  rsc = refs->sc;
1586  rsc->ticked = true;
1587 
1588  for ( rf=rsc->layers[ly_fore].refs; rf!=NULL; rf = rf->next ) {
1589  trans[0] = rf->transform[0]*transform[0] +
1590  rf->transform[1]*transform[2];
1591  trans[1] = rf->transform[0]*transform[1] +
1592  rf->transform[1]*transform[3];
1593  trans[2] = rf->transform[2]*transform[0] +
1594  rf->transform[3]*transform[2];
1595  trans[3] = rf->transform[2]*transform[1] +
1596  rf->transform[3]*transform[3];
1597  trans[4] = rf->transform[4]*transform[0] +
1598  rf->transform[5]*transform[2] +
1599  transform[4];
1600  trans[5] = rf->transform[4]*transform[1] +
1601  rf->transform[5]*transform[3] +
1602  transform[5];
1603  InstanciateReference(sf,topref,rf,trans,rsc,layer);
1604  }
1605  rsc->ticked = false;
1606 
1607  {
1609  if ( new!=NULL ) {
1610  for ( spl = new; spl->next!=NULL; spl = spl->next );
1611  spl->next = topref->layers[0].splines;
1612  topref->layers[0].splines = new;
1613  }
1614  }
1615 }
1616 
1617 static char *copyparse(char *str) {
1618  char *ret, *rpt;
1619  int ch,i;
1620 
1621  if ( str==NULL )
1622 return( str );
1623 
1624  rpt=ret=galloc(strlen(str)+1);
1625  while ( *str ) {
1626  if ( *str=='\\' ) {
1627  ++str;
1628  if ( *str=='n' ) ch = '\n';
1629  else if ( *str=='r' ) ch = '\r';
1630  else if ( *str=='t' ) ch = '\t';
1631  else if ( *str=='b' ) ch = '\b';
1632  else if ( *str=='f' ) ch = '\f';
1633  else if ( *str=='\\' ) ch = '\\';
1634  else if ( *str=='(' ) ch = '(';
1635  else if ( *str==')' ) ch = ')';
1636  else if ( *str>='0' && *str<='7' ) {
1637  for ( i=ch = 0; i<3 && *str>='0' && *str<='7'; ++i )
1638  ch = (ch<<3) + *str++-'0';
1639  --str;
1640  } else
1641  ch = *str;
1642  ++str;
1643  *rpt++ = ch;
1644  } else
1645  *rpt++ = *str++;
1646  }
1647  *rpt = '\0';
1648  if ( !utf8_valid(ret)) {
1649  /* Assume latin1, convert to utf8 */
1650  rpt = latin1_2_utf8_copy(ret);
1651  free(ret);
1652  ret = rpt;
1653  }
1654 return(ret);
1655 }
1656 
1657 char *XUIDFromFD(int xuid[20]) {
1658  int i;
1659  char *ret=NULL;
1660 
1661  for ( i=19; i>=0 && xuid[i]==0; --i );
1662  if ( i>=0 ) {
1663  int j; char *pt;
1664  ret = galloc(2+20*(i+1));
1665  pt = ret;
1666  *pt++ = '[';
1667  for ( j=0; j<=i; ++j ) {
1668  sprintf(pt,"%d ", xuid[j]);
1669  pt += strlen(pt);
1670  }
1671  pt[-1] = ']';
1672  }
1673 return( ret );
1674 }
1675 
1676 static void SplineFontMetaData(SplineFont *sf,struct fontdict *fd) {
1677  int em;
1678 
1679  sf->fontname = utf8_verify_copy(fd->cidfontname?fd->cidfontname:fd->fontname);
1680  sf->display_size = -default_fv_font_size;
1681  sf->display_antialias = default_fv_antialias;
1682  if ( fd->fontinfo!=NULL ) {
1683  if ( sf->fontname==NULL && fd->fontinfo->fullname!=NULL ) {
1684  sf->fontname = EnforcePostScriptName(fd->fontinfo->fullname);
1685  }
1686  if ( sf->fontname==NULL ) sf->fontname = EnforcePostScriptName(fd->fontinfo->familyname);
1687  sf->fullname = copyparse(fd->fontinfo->fullname);
1688  sf->familyname = copyparse(fd->fontinfo->familyname);
1689  sf->weight = copyparse(fd->fontinfo->weight);
1690  sf->version = copyparse(fd->fontinfo->version);
1691  sf->copyright = copyparse(fd->fontinfo->notice);
1692  sf->italicangle = fd->fontinfo->italicangle;
1693  sf->upos = fd->fontinfo->underlineposition;
1694  sf->uwidth = fd->fontinfo->underlinethickness;
1695  sf->strokedfont = fd->painttype==2;
1696  sf->strokewidth = fd->strokewidth;
1697  sf->ascent = fd->fontinfo->ascent;
1698  sf->descent = fd->fontinfo->descent;
1699  }
1700  if ( sf->uniqueid==0 ) sf->uniqueid = fd->uniqueid;
1701  if ( sf->fontname==NULL ) sf->fontname = GetNextUntitledName();
1702  if ( sf->fullname==NULL ) sf->fullname = copy(sf->fontname);
1703  if ( sf->familyname==NULL ) sf->familyname = copy(sf->fontname);
1704  if ( sf->weight==NULL ) sf->weight = copy("");
1705  if ( fd->modificationtime!=0 ) {
1706  sf->modificationtime = fd->modificationtime;
1707  sf->creationtime = fd->creationtime;
1708  }
1709  sf->cidversion = fd->cidversion;
1710  sf->xuid = XUIDFromFD(fd->xuid);
1711  /*sf->wasbinary = fd->wasbinary;*/
1712  if ( fd->fontmatrix[0]==0 )
1713  em = 1000;
1714  else
1715  em = rint(1/fd->fontmatrix[0]);
1716  if ( sf->ascent==0 && sf->descent!=0 )
1717  sf->ascent = em-sf->descent;
1718  else if ( fd->fontbb[3]-fd->fontbb[1]==em ) {
1719  if ( sf->ascent==0 ) sf->ascent = fd->fontbb[3];
1720  if ( sf->descent==0 ) sf->descent = fd->fontbb[1];
1721  } else if ( sf->ascent==0 )
1722  sf->ascent = 8*em/10;
1723  sf->descent = em-sf->ascent;
1724 
1725  sf->private = fd->private->private; fd->private->private = NULL;
1726  PSDictRemoveEntry(sf->private, "OtherSubrs");
1727 
1728  sf->cidregistry = copy(fd->registry);
1729  sf->ordering = copy(fd->ordering);
1730  sf->supplement = fd->supplement;
1731  sf->pfminfo.fstype = fd->fontinfo->fstype;
1732  if ( sf->ordering!=NULL ) {
1733  if ( strnmatch(sf->ordering,"Japan",5)==0 )
1734  sf->uni_interp = ui_japanese;
1735  else if ( strnmatch(sf->ordering,"Korea",5)==0 )
1736  sf->uni_interp = ui_korean;
1737  else if ( strnmatch(sf->ordering,"CNS",3)==0 )
1738  sf->uni_interp = ui_trad_chinese;
1739  else if ( strnmatch(sf->ordering,"GB",2)==0 )
1740  sf->uni_interp = ui_simp_chinese;
1741  }
1742 }
1743 
1744 static void TransByFontMatrix(SplineFont *sf,real fontmatrix[6]) {
1745  real trans[6];
1746  int em = sf->ascent+sf->descent, i;
1747  SplineChar *sc;
1748  RefChar *refs;
1749 
1750  if ( fontmatrix[0]==fontmatrix[3] &&
1751  fontmatrix[1]==0 && fontmatrix[2]==0 &&
1752  fontmatrix[4]==0 && fontmatrix[5]==0 )
1753 return; /* It's just the expected matrix */
1754 
1755  trans[0] = 1;
1756  if ( fontmatrix[0]==fontmatrix[3] ) trans[3] = 1;
1757  else trans[3] = rint(fontmatrix[3]*em);
1758  trans[1] = fontmatrix[1]*em;
1759  trans[2] = fontmatrix[2]*em;
1760  trans[4] = rint(fontmatrix[4]*em);
1761  trans[5] = rint(fontmatrix[5]*em);
1762 
1763  for ( i=0; i<sf->glyphcnt; ++i ) if ( (sc=sf->glyphs[i])!=NULL ) {
1764  SplinePointListTransform(sc->layers[ly_fore].splines,trans,true);
1765  for ( refs=sc->layers[ly_fore].refs; refs!=NULL; refs=refs->next ) {
1766  /* Just scale the offsets. we'll do all the base characters */
1767  real temp = refs->transform[4]*trans[0] +
1768  refs->transform[5]*trans[2] +
1769  /*transform[4]*/0;
1770  refs->transform[5] = refs->transform[4]*trans[1] +
1771  refs->transform[5]*trans[3] +
1772  /*transform[5]*/0;
1773  refs->transform[4] = temp;
1774  }
1775  sc->changedsincelasthinted = true;
1776  sc->manualhints = false;
1777  }
1778  for ( i=0; i<sf->glyphcnt; ++i ) if ( (sc=sf->glyphs[i])!=NULL ) {
1779  for ( refs=sc->layers[ly_fore].refs; refs!=NULL; refs=refs->next )
1781  }
1782 }
1783 
1785  int i, layer;
1786  RefChar *refs, *next, *pr;
1787 
1788  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
1789  sf->glyphs[i]->ticked = false;
1790 
1791  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL ) {
1792  SplineChar *sc = sf->glyphs[i];
1793 
1794  for ( layer=ly_back; layer<sc->layer_cnt; ++layer ) {
1795  for ( pr=NULL, refs = sc->layers[layer].refs; refs!=NULL; refs=next ) {
1796  next = refs->next;
1797  sc->ticked = true;
1798  InstanciateReference(sf, refs, refs, refs->transform,sc,layer);
1799  if ( refs->sc!=NULL ) {
1800  SplineSetFindBounds(refs->layers[0].splines,&refs->bb);
1801  sc->ticked = false;
1802  pr = refs;
1803  } else {
1804  /* In some mal-formed postscript fonts we can have a reference */
1805  /* to a character that is not actually in the font. I even */
1806  /* generated one by mistake once... */
1807  if ( pr==NULL )
1808  sc->layers[layer].refs = next;
1809  else
1810  pr->next = next;
1811  refs->next = NULL;
1812  RefCharsFree(refs);
1813  }
1814  }
1815  }
1816  }
1817 }
1818 
1819 /* Also handles type3s */
1821  int i, j, notdefpos;
1822  RefChar *refs, *next;
1823  int istype2 = fd->fonttype==2; /* Easy enough to deal with even though it will never happen... */
1824  int istype3 = fd->charprocs->next!=0;
1825  EncMap *map;
1826 
1827  if ( istype2 )
1828  fd->private->subrs->bias = fd->private->subrs->cnt<1240 ? 107 :
1829  fd->private->subrs->cnt<33900 ? 1131 : 32768;
1830  sf->glyphmax = sf->glyphcnt = istype3 ? fd->charprocs->next : fd->chars->next;
1831  if ( sf->map==NULL ) {
1832  sf->map = map = EncMapNew(256+CharsNotInEncoding(fd),sf->glyphcnt,fd->encoding_name);
1833  } else
1834  map = sf->map;
1835  sf->glyphs = gcalloc(map->backmax,sizeof(SplineChar *));
1836  if ( istype3 )
1837  notdefpos = LookupCharString(".notdef",(struct pschars *) (fd->charprocs));
1838  else
1839  notdefpos = LookupCharString(".notdef",fd->chars);
1840  for ( i=0; i<256; ++i ) {
1841  int k;
1842  if ( istype3 ) {
1843  k = LookupCharString(fd->encoding[i],(struct pschars *) (fd->charprocs));
1844  } else {
1845  k = LookupCharString(fd->encoding[i],fd->chars);
1846  }
1847  if ( k==-1 ) k = notdefpos;
1848  map->map[i] = k;
1849  if ( k!=-1 && map->backmap[k]==-1 )
1850  map->backmap[k] = i;
1851  }
1852  if ( map->enccount>256 ) {
1853  int k, j;
1854  for ( k=0; k<fd->chars->cnt; ++k ) {
1855  if ( fd->chars->keys[k]!=NULL ) {
1856  for ( j=0; j<256; ++j )
1857  if ( fd->encoding[j]!=NULL &&
1858  strcmp(fd->encoding[j],fd->chars->keys[k])==0 )
1859  break;
1860  if ( j==256 ) {
1861  map->map[i] = k;
1862  if ( map->backmap[k]==-1 )
1863  map->backmap[k] = i;
1864  ++i;
1865  }
1866  }
1867  }
1868  /* And for type3s */
1869  for ( k=0; k<fd->charprocs->cnt; ++k ) {
1870  if ( fd->charprocs->keys[k]!=NULL ) {
1871  for ( j=0; j<256; ++j )
1872  if ( fd->encoding[j]!=NULL &&
1873  strcmp(fd->encoding[j],fd->charprocs->keys[k])==0 )
1874  break;
1875  if ( j==256 ) {
1876  map->map[i] = k;
1877  if ( map->backmap[k]==-1 )
1878  map->backmap[k] = i;
1879  ++i;
1880  }
1881  }
1882  }
1883  }
1884  for ( i=0; i<map->enccount; ++i ) if ( map->map[i]==-1 )
1885  map->map[i] = notdefpos;
1886 
1887  for ( i=0; i<sf->glyphcnt; ++i ) {
1888  if ( !istype3 )
1889  sf->glyphs[i] = PSCharStringToSplines(fd->chars->values[i],fd->chars->lens[i],
1890  pscontext,fd->private->subrs,NULL,fd->chars->keys[i]);
1891  else
1892  sf->glyphs[i] = fd->charprocs->values[i];
1893  if ( sf->glyphs[i]!=NULL ) {
1894  sf->glyphs[i]->orig_pos = i;
1895  sf->glyphs[i]->vwidth = sf->ascent+sf->descent;
1896  sf->glyphs[i]->unicodeenc = UniFromName(sf->glyphs[i]->name,sf->uni_interp,map->enc);
1897  sf->glyphs[i]->parent = sf;
1898  /* SCLigDefault(sf->glyphs[i]);*/ /* Also reads from AFM file, but it probably doesn't exist */
1899  }
1900  ff_progress_next();
1901  }
1903  if ( fd->metrics!=NULL ) {
1904  for ( i=0; i<fd->metrics->next; ++i ) {
1905  int width = strtol(fd->metrics->values[i],NULL,10);
1906  for ( j=sf->glyphcnt-1; j>=0; --j ) {
1907  if ( sf->glyphs[j]!=NULL && sf->glyphs[j]->name!=NULL &&
1908  strcmp(fd->metrics->keys[i],sf->glyphs[j]->name)==0 ) {
1909  sf->glyphs[j]->width = width;
1910  break;
1911  }
1912  }
1913  }
1914  }
1915  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
1916  for ( refs = sf->glyphs[i]->layers[ly_fore].refs; refs!=NULL; refs=next ) {
1917  next = refs->next;
1918  if ( refs->adobe_enc==' ' && refs->layers[0].splines==NULL ) {
1919  /* When I have a link to a single character I will save out a */
1920  /* seac to that character and a space (since I can only make */
1921  /* real char links), so if we find a space link, get rid of*/
1922  /* it. It's an artifact */
1923  SCRefToSplines(sf->glyphs[i],refs,ly_fore);
1924  }
1925  }
1926  /* sometimes (some apple oblique fonts) the fontmatrix is not just a */
1927  /* formality, it acutally contains a skew. So be ready */
1928  if ( fd->fontmatrix[0]!=0 )
1930 }
1931 
1933  int i;
1934  SplineChar *sc;
1935 
1937 
1938  /* Clean up the hint masks, We create an initial hintmask whether we need */
1939  /* it or not */
1940  for ( i=0; i<sf->glyphcnt; ++i ) {
1941  if ( (sc = sf->glyphs[i])!=NULL && !sc->hconflicts && !sc->vconflicts &&
1942  sc->layers[ly_fore].splines!=NULL ) {
1943  chunkfree( sc->layers[ly_fore].splines->first->hintmask,sizeof(HintMask) );
1944  sc->layers[ly_fore].splines->first->hintmask = NULL;
1945  }
1946  }
1947 }
1948 
1950  char *pt, *end, *origweight;
1951  MMSet *mm;
1952  int ipos, apos, ppos, item, i;
1953  real blends[12]; /* At most twelve points/axis in a blenddesignmap */
1954  real designs[12];
1955  EncMap *map;
1956 
1957  if ( fd->weightvector==NULL || fd->fontinfo->blenddesignpositions==NULL ||
1959  ff_post_error(_("Bad Multiple Master Font"),_("Bad Multiple Master Font"));
1960  SplineFontFree(sf);
1961 return( NULL );
1962  }
1963 
1964  mm = chunkalloc(sizeof(MMSet));
1965 
1966  pt = fd->weightvector;
1967  while ( *pt==' ' || *pt=='[' ) ++pt;
1968  while ( *pt!=']' && *pt!='\0' ) {
1970  strtod(pt,&end);
1971  if ( pt==end )
1972  break;
1974  if ( pscontext->instance_count>=(int)(sizeof(pscontext->blend_values)/sizeof(pscontext->blend_values[0]))) {
1975  LogError( _("Multiple master font with more than 16 instances\n") );
1976  break;
1977  }
1978  for ( pt = end; *pt==' '; ++pt );
1979  }
1980 
1983  mm->defweights = galloc(mm->instance_count*sizeof(real));
1985  mm->normal = sf;
1987  map = sf->map;
1988  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
1989  sf->glyphs[i]->blended = true;
1990  sf->mm = mm;
1991 
1992  pt = fd->fontinfo->blendaxistypes;
1993  while ( *pt==' ' || *pt=='[' ) ++pt;
1994  while ( *pt!=']' && *pt!='\0' ) {
1995  if ( *pt=='/' ) ++pt;
1996  for ( end=pt; *end!=' ' && *end!=']' && *end!='\0'; ++end );
1997  if ( pt==end )
1998  break;
1999  if ( mm->axis_count>=(int)(sizeof(mm->axes)/sizeof(mm->axes[0]))) {
2000  LogError( _("Multiple master font with more than 4 axes\n") );
2001  break;
2002  }
2003  mm->axes[ mm->axis_count++ ] = copyn( pt,end-pt );
2004  for ( pt = end; *pt==' '; ++pt );
2005  }
2006 
2007  if ( mm->instance_count < (1<<mm->axis_count) )
2008  ff_post_error(_("Bad Multiple Master Font"),_("This multiple master font has %1$d instance fonts, but it needs at least %2$d master fonts for %3$d axes. FontForge will not be able to edit this correctly"),mm->instance_count,1<<mm->axis_count,mm->axis_count);
2009  else if ( mm->instance_count > (1<<mm->axis_count) )
2010  ff_post_error(_("Bad Multiple Master Font"),_("This multiple master font has %1$d instance fonts, but FontForge can only handle %2$d master fonts for %3$d axes. FontForge will not be able to edit this correctly"),mm->instance_count,1<<mm->axis_count,mm->axis_count);
2011  mm->positions = gcalloc(mm->axis_count*mm->instance_count,sizeof(real));
2013  while ( *pt==' ' ) ++pt;
2014  if ( *pt=='[' ) ++pt;
2015  ipos = 0;
2016  while ( *pt!=']' && *pt!='\0' ) {
2017  while ( *pt==' ' ) ++pt;
2018  if ( *pt==']' || *pt=='\0' )
2019  break;
2020  if ( ipos>=mm->instance_count )
2021  break;
2022  if ( *pt=='[' ) {
2023  ++pt;
2024  apos=0;
2025  while ( *pt!=']' && *pt!='\0' ) {
2026  if ( apos>=mm->axis_count ) {
2027  LogError( _("Too many axis positions specified in /BlendDesignPositions.\n") );
2028  break;
2029  }
2030  mm->positions[ipos*mm->axis_count+apos] =
2031  strtod(pt,&end);
2032  if ( pt==end )
2033  break;
2034  ++apos;
2035  for ( pt = end; *pt==' '; ++pt );
2036  }
2037  if ( *pt==']' ) ++pt;
2038  ++ipos;
2039  } else
2040  ++pt;
2041  }
2042 
2043  mm->axismaps = gcalloc(mm->axis_count,sizeof(struct axismap));
2044  pt = fd->fontinfo->blenddesignmap;
2045  while ( *pt==' ' ) ++pt;
2046  if ( *pt=='[' ) ++pt;
2047  apos = 0;
2048  while ( *pt!=']' && *pt!='\0' ) {
2049  while ( *pt==' ' ) ++pt;
2050  if ( *pt==']' || *pt=='\0' )
2051  break;
2052  if ( apos>=mm->axis_count )
2053  break;
2054  if ( *pt=='[' ) {
2055  ++pt;
2056  ppos=0;
2057  while ( *pt!=']' && *pt!='\0' ) {
2058  if ( ppos>=12 ) {
2059  LogError( _("Too many mapping data points specified in /BlendDesignMap for axis %s.\n"), mm->axes[apos] );
2060  break;
2061  }
2062  while ( *pt==' ' ) ++pt;
2063  if ( *pt=='[' ) {
2064  ++pt;
2065  designs[ppos] = strtod(pt,&end);
2066  blends[ppos] = strtod(end,&end);
2067  if ( blends[ppos]<0 || blends[ppos]>1 ) {
2068  LogError( _("Bad value for blend in /BlendDesignMap for axis %s.\n"), mm->axes[apos] );
2069  if ( blends[ppos]<0 ) blends[ppos] = 0;
2070  if ( blends[ppos]>1 ) blends[ppos] = 1;
2071  }
2072  pt = end;
2073  while ( *pt!=']' && *pt!='\0' ) ++pt;
2074  ppos ++;
2075  }
2076  ++pt;
2077  while ( *pt==' ' ) ++pt;
2078  }
2079  if ( *pt==']' ) ++pt;
2080  if ( ppos<2 )
2081  LogError( _("Bad few values in /BlendDesignMap for axis %s.\n"), mm->axes[apos] );
2082  mm->axismaps[apos].points = ppos;
2083  mm->axismaps[apos].blends = galloc(ppos*sizeof(real));
2084  mm->axismaps[apos].designs = galloc(ppos*sizeof(real));
2085  memcpy(mm->axismaps[apos].blends,blends,ppos*sizeof(real));
2086  memcpy(mm->axismaps[apos].designs,designs,ppos*sizeof(real));
2087  ++apos;
2088  } else
2089  ++pt;
2090  }
2091 
2092  mm->cdv = copy(fd->cdv);
2093  mm->ndv = copy(fd->ndv);
2094 
2095  origweight = fd->fontinfo->weight;
2096 
2097  /* Now figure out the master designs, being careful to interpolate */
2098  /* BlueValues, ForceBold, UnderlinePosition etc. We need to copy private */
2099  /* generate a font name */
2100  for ( ipos = 0; ipos<mm->instance_count; ++ipos ) {
2101  free(fd->fontname);
2102  free(fd->fontinfo->fullname);
2103  fd->fontname = MMMakeMasterFontname(mm,ipos,&fd->fontinfo->fullname);
2104  fd->fontinfo->weight = MMGuessWeight(mm,ipos,copy(origweight));
2105  if ( fd->blendfontinfo!=NULL ) {
2106  for ( item=0; item<3; ++item ) {
2107  static char *names[] = { "ItalicAngle", "UnderlinePosition", "UnderlineThickness" };
2109  if ( pt!=NULL ) {
2110  pt = MMExtractNth(pt,ipos);
2111  if ( pt!=NULL ) {
2112  double val = strtod(pt,NULL);
2113  free(pt);
2114  switch ( item ) {
2115  case 0: fd->fontinfo->italicangle = val; break;
2116  case 1: fd->fontinfo->underlineposition = val; break;
2117  case 2: fd->fontinfo->underlinethickness = val; break;
2118  }
2119  }
2120  }
2121  }
2122  }
2123  fd->private->private = PSDictCopy(sf->private);
2124  if ( fd->blendprivate!=NULL ) {
2125  static char *arrnames[] = { "BlueValues", "OtherBlues", "FamilyBlues", "FamilyOtherBlues", "StdHW", "StdVW", "StemSnapH", "StemSnapV", NULL };
2126  static char *scalarnames[] = { "ForceBold", "BlueFuzz", "BlueScale", "BlueShift", NULL };
2127  for ( item=0; scalarnames[item]!=NULL; ++item ) {
2128  pt = PSDictHasEntry(fd->blendprivate,scalarnames[item]);
2129  if ( pt!=NULL ) {
2130  pt = MMExtractNth(pt,ipos);
2131  PSDictChangeEntry(fd->private->private,scalarnames[item],pt);
2132  free(pt);
2133  }
2134  }
2135  for ( item=0; arrnames[item]!=NULL; ++item ) {
2136  pt = PSDictHasEntry(fd->blendprivate,arrnames[item]);
2137  if ( pt!=NULL ) {
2138  pt = MMExtractArrayNth(pt,ipos);
2139  PSDictChangeEntry(fd->private->private,arrnames[item],pt);
2140  free(pt);
2141  }
2142  }
2143  }
2144  for ( item=0; item<mm->instance_count; ++item )
2145  pscontext->blend_values[item] = 0;
2146  pscontext->blend_values[ipos] = 1;
2147 
2148  mm->instances[ipos] = SplineFontEmpty();
2149  SplineFontMetaData(mm->instances[ipos],fd);
2150  free(fd->fontinfo->weight);
2151  mm->instances[ipos]->map = map;
2153  mm->instances[ipos]->mm = mm;
2154  }
2155  fd->fontinfo->weight = origweight;
2156 
2157  /* Clean up hintmasks. We always create a hintmask on the first point */
2158  /* only keep them if we actually have conflicts. */
2159  for ( i=0; i<mm->normal->glyphcnt; ++i )
2160  if ( mm->normal->glyphs[i]!=NULL &&
2161  mm->normal->glyphs[i]->layers[ly_fore].splines != NULL ) {
2162  for ( item=0; item<mm->instance_count; ++item )
2163  if ( mm->instances[item]->glyphs[i]->vconflicts ||
2164  mm->instances[item]->glyphs[i]->hconflicts )
2165  break;
2166  if ( item==mm->instance_count ) { /* No conflicts */
2167  for ( item=0; item<mm->instance_count; ++item ) {
2170  }
2173  }
2174  }
2175 
2176 return( sf );
2177 }
2178 
2180  struct pscontext *pscontext) {
2181  int i,j,k, uni;
2182  unsigned bad;
2183  SplineChar **chars;
2184  char buffer[100];
2185  struct cidmap *map;
2186  SplineFont *_sf;
2187  SplineChar *sc;
2188  EncMap *encmap;
2189 
2190  bad = 0x80000000;
2191  for ( i=0; i<fd->fdcnt; ++i )
2192  if ( fd->fds[i]->fonttype!=1 && fd->fds[i]->fonttype!=2 )
2193  bad = fd->fds[i]->fonttype;
2194  if ( bad!=0x80000000 || fd->cidfonttype!=0 ) {
2195  LogError( _("Could not parse a CID font, %sCIDFontType %d, %sfonttype %d\n"),
2196  ( fd->cidfonttype!=0 ) ? "unexpected " : "",
2197  ( bad!=0x80000000 ) ? "unexpected " : "",
2198  fd->cidfonttype, bad );
2199  SplineFontFree(sf);
2200 return( NULL );
2201  }
2202  if ( fd->cidstrs==NULL || fd->cidcnt==0 ) {
2203  LogError( _("CID format doesn't contain what we expected it to.\n") );
2204  SplineFontFree(sf);
2205 return( NULL );
2206  }
2207 
2208  encmap = EncMap1to1(fd->cidcnt);
2209 
2210  sf->subfontcnt = fd->fdcnt;
2211  sf->subfonts = galloc((sf->subfontcnt+1)*sizeof(SplineFont *));
2212  for ( i=0; i<fd->fdcnt; ++i ) {
2213  if ( fd->fontmatrix[0]!=0 ) {
2214  MatMultiply(fd->fontmatrix,fd->fds[i]->fontmatrix,fd->fds[i]->fontmatrix);
2215  }
2216  sf->subfonts[i] = SplineFontEmpty();
2217  SplineFontMetaData(sf->subfonts[i],fd->fds[i]);
2218  sf->subfonts[i]->cidmaster = sf;
2219  sf->subfonts[i]->uni_interp = sf->uni_interp;
2220  sf->subfonts[i]->map = encmap;
2221  if ( fd->fds[i]->fonttype==2 )
2222  fd->fds[i]->private->subrs->bias =
2223  fd->fds[i]->private->subrs->cnt<1240 ? 107 :
2224  fd->fds[i]->private->subrs->cnt<33900 ? 1131 : 32768;
2225  }
2226 
2227  map = FindCidMap(sf->cidregistry,sf->ordering,sf->supplement,sf);
2228 
2229  chars = gcalloc(fd->cidcnt,sizeof(SplineChar *));
2230  for ( i=0; i<fd->cidcnt; ++i ) if ( fd->cidlens[i]>0 ) {
2231  j = fd->cidfds[i]; /* We get font indexes of 255 for non-existant chars */
2232  uni = CID2NameUni(map,i,buffer,sizeof(buffer));
2233  pscontext->is_type2 = fd->fds[j]->fonttype==2;
2235  pscontext,fd->fds[j]->private->subrs,
2236  NULL,buffer);
2237  chars[i]->vwidth = sf->subfonts[j]->ascent+sf->subfonts[j]->descent;
2238  chars[i]->unicodeenc = uni;
2239  chars[i]->orig_pos = i;
2240  /* There better not be any references (seac's) because we have no */
2241  /* encoding on which to base any fixups */
2242  if ( chars[i]->layers[ly_fore].refs!=NULL )
2243  IError( "Reference found in CID font. Can't fix it up");
2244  sf->subfonts[j]->glyphcnt = sf->subfonts[j]->glyphmax = i+1;
2245  ff_progress_next();
2246  }
2247  for ( i=0; i<fd->fdcnt; ++i )
2248  sf->subfonts[i]->glyphs = gcalloc(sf->subfonts[i]->glyphcnt,sizeof(SplineChar *));
2249  for ( i=0; i<fd->cidcnt; ++i ) if ( chars[i]!=NULL ) {
2250  j = fd->cidfds[i];
2251  if ( j<sf->subfontcnt ) {
2252  sf->subfonts[j]->glyphs[i] = chars[i];
2253  chars[i]->parent = sf->subfonts[j];
2254  }
2255  }
2256  free(chars);
2257 
2258  /* Clean up the hint masks, We create an initial hintmask whether we */
2259  /* need it or not */
2260  k=0;
2261  do {
2262  _sf = k<sf->subfontcnt?sf->subfonts[k]:sf;
2263  for ( i=0; i<_sf->glyphcnt; ++i ) {
2264  if ( (sc = _sf->glyphs[i])!=NULL && !sc->hconflicts && !sc->vconflicts &&
2265  sc->layers[ly_fore].splines!=NULL ) {
2266  chunkfree( sc->layers[ly_fore].splines->first->hintmask,sizeof(HintMask) );
2267  sc->layers[ly_fore].splines->first->hintmask = NULL;
2268  }
2269  }
2270  ++k;
2271  } while ( k<sf->subfontcnt );
2272 return( sf );
2273 }
2274 
2276  SplineFont *sf;
2277  struct pscontext pscontext;
2278 
2279  if ( fd->sf!=NULL )
2280  sf = fd->sf;
2281  else {
2282  memset(&pscontext,0,sizeof(pscontext));
2283  pscontext.is_type2 = fd->fonttype==2;
2285 
2286  sf = SplineFontEmpty();
2287  SplineFontMetaData(sf,fd);
2288  if ( fd->wascff ) {
2289  SplineFontFree(sf);
2290  sf = fd->sf;
2291  } else if ( fd->fdcnt!=0 )
2293  else if ( fd->weightvector!=NULL )
2295  else
2297  }
2298 return( sf );
2299 }
2300 
2302  SplineSetFindBounds(rf->layers[0].splines,&rf->bb);
2303  SplineSetFindTop(rf->layers[0].splines,&rf->top);
2304 }
2305 
2307  SplinePointList *new, *last;
2308  RefChar *refs;
2309  (void)sc;
2310  {
2311  if ( rf->layer_cnt>0 ) {
2313  rf->layers[0].splines = NULL;
2314  }
2315  rf->layers = gcalloc(1,sizeof(struct reflayer));
2316  rf->layer_cnt = 1;
2318  rf->layers[0].splines = new;
2319  last = NULL;
2320  if ( new!=NULL )
2321  for ( last = new; last->next!=NULL; last = last->next );
2322  for ( refs = rf->sc->layers[layer].refs; refs!=NULL; refs = refs->next ) {
2324  if ( last!=NULL )
2325  last->next = new;
2326  else
2327  rf->layers[0].splines = new;
2328  if ( new!=NULL )
2329  for ( last = new; last->next!=NULL; last = last->next );
2330  }
2331  }
2332  RefCharFindBounds(rf);
2333 }
2334 
2336  int i, undone, undoable, j, cnt;
2337  RefChar *ref;
2338 
2339  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
2340  sf->glyphs[i]->ticked = false;
2341 
2342  undone = true;
2343  cnt = 0;
2344  while ( undone && cnt<200) {
2345  undone = false;
2346  for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL && !sf->glyphs[i]->ticked ) {
2347  undoable = false;
2348  for ( j=0; j<sf->glyphs[i]->layer_cnt; ++j ) {
2349  for ( ref=sf->glyphs[i]->layers[j].refs; ref!=NULL; ref=ref->next ) {
2350  if ( !ref->sc->ticked )
2351  undoable = true;
2352  }
2353  }
2354  if ( undoable )
2355  undone = true;
2356  else {
2357  for ( j=0; j<sf->glyphs[i]->layer_cnt; ++j ) {
2358  for ( ref=sf->glyphs[i]->layers[j].refs; ref!=NULL; ref=ref->next )
2359  SCReinstanciateRefChar(sf->glyphs[i],ref,j);
2360  }
2361  sf->glyphs[i]->ticked = true;
2362  }
2363  }
2364  ++cnt;
2365  }
2366 }
2367 
2369  int i;
2370 
2371  if ( sf->cidmaster!=NULL || sf->subfontcnt!=0 ) {
2372  if ( sf->cidmaster!=NULL ) sf = sf->cidmaster;
2373  for ( i=0; i<sf->subfontcnt; ++i )
2374  _SFReinstanciateRefs(sf->subfonts[i]);
2375  } else
2377 }
2378 
2380  RefChar *rf;
2381 
2382  for ( rf=sc->layers[layer].refs; rf!=NULL; rf=rf->next ) if ( rf->sc==rsc ) {
2384  }
2385 }
2386 
2387 void SCRemoveDependent(SplineChar *dependent,RefChar *rf,int layer) {
2388  struct splinecharlist *dlist, *pd;
2389  RefChar *prev;
2390 
2391  if ( dependent->layers[layer].refs==rf )
2392  dependent->layers[layer].refs = rf->next;
2393  else {
2394  for ( prev = dependent->layers[layer].refs; prev->next!=rf; prev=prev->next );
2395  prev->next = rf->next;
2396  }
2397  /* Check for multiple dependencies (colon has two refs to period) */
2398  /* if there are none, then remove dependent from ref->sc's dependents list */
2399  for ( prev = dependent->layers[ly_fore].refs; prev!=NULL && (prev==rf || prev->sc!=rf->sc); prev = prev->next );
2400  if ( prev==NULL ) {
2401  dlist = rf->sc->dependents;
2402  if ( dlist==NULL )
2403  /* Do nothing */;
2404  else if ( dlist->sc==dependent ) {
2405  rf->sc->dependents = dlist->next;
2406  } else {
2407  for ( pd=dlist, dlist = pd->next; dlist!=NULL && dlist->sc!=dependent; pd=dlist, dlist = pd->next );
2408  if ( dlist!=NULL )
2409  pd->next = dlist->next;
2410  }
2411  chunkfree(dlist,sizeof(struct splinecharlist));
2412  }
2413  RefCharFree(rf);
2414 }
2415 
2417  RefChar *rf, *next;
2418 
2419  for ( rf=dependent->layers[layer].refs; rf!=NULL; rf=next ) {
2420  next = rf->next;
2421  SCRemoveDependent(dependent,rf,layer);
2422  }
2423  dependent->layers[layer].refs = NULL;
2424 }
2425 
2426 void SCRemoveDependents(SplineChar *dependent) {
2427  int layer;
2428 
2429  for ( layer=ly_fore; layer<dependent->layer_cnt; ++layer )
2430  SCRemoveLayerDependents(dependent,layer);
2431 }
2432 
2434  SplineSet *spl;
2435  {
2436  if ( (spl = rf->layers[0].splines)!=NULL ) {
2437  while ( spl->next!=NULL )
2438  spl = spl->next;
2439  spl->next = sc->layers[layer].splines;
2440  sc->layers[layer].splines = rf->layers[0].splines;
2441  rf->layers[0].splines = NULL;
2442  }
2443  }
2445 }
2446 
2447 /* This returns all real solutions, even those out of bounds */
2448 /* I use -999999 as an error flag, since we're really only interested in */
2449 /* solns near 0 and 1 that should be ok. -1 is perhaps a little too close */
2450 static int _CubicSolve(const Spline1D *sp,extended ts[3]) {
2451  extended d, xN, yN, delta2, temp, delta, h, t2, t3, theta;
2452  int i=0;
2453 
2454  ts[0] = ts[1] = ts[2] = -999999;
2455  if ( sp->d==0 && sp->a!=0 ) {
2456  /* one of the roots is 0, the other two are the soln of a quadratic */
2457  ts[0] = 0;
2458  if ( sp->c==0 ) {
2459  ts[1] = -sp->b/(extended) sp->a; /* two zero roots */
2460  } else {
2461  temp = sp->b*(extended) sp->b-4*(extended) sp->a*sp->c;
2462  if ( RealNear(temp,0))
2463  ts[1] = -sp->b/(2*(extended) sp->a);
2464  else if ( temp>=0 ) {
2465  temp = sqrt(temp);
2466  ts[1] = (-sp->b+temp)/(2*(extended) sp->a);
2467  ts[2] = (-sp->b-temp)/(2*(extended) sp->a);
2468  }
2469  }
2470  } else if ( sp->a!=0 ) {
2471  /* http://www.m-a.org.uk/eb/mg/mg077ch.pdf */
2472  /* this nifty solution to the cubic neatly avoids complex arithmatic */
2473  xN = -sp->b/(3*(extended) sp->a);
2474  yN = ((sp->a*xN + sp->b)*xN+sp->c)*xN + sp->d;
2475 
2476  delta2 = (sp->b*(extended) sp->b-3*(extended) sp->a*sp->c)/(9*(extended) sp->a*sp->a);
2477  if ( RealNear(delta2,0) ) delta2 = 0;
2478 
2479  /* the descriminant is yN^2-h^2, but delta might be <0 so avoid using h */
2480  d = yN*yN - 4*sp->a*sp->a*delta2*delta2*delta2;
2481  if ( ((yN>.01 || yN<-.01) && RealNear(d/yN,0)) || ((yN<=.01 && yN>=-.01) && RealNear(d,0)) )
2482  d = 0;
2483  if ( d>0 ) {
2484  temp = sqrt(d);
2485  t2 = (-yN-temp)/(2*sp->a);
2486  t2 = (t2==0) ? 0 : (t2<0) ? -pow(-t2,1./3.) : pow(t2,1./3.);
2487  t3 = (-yN+temp)/(2*sp->a);
2488  t3 = t3==0 ? 0 : (t3<0) ? -pow(-t3,1./3.) : pow(t3,1./3.);
2489  ts[0] = xN + t2 + t3;
2490  } else if ( d<0 ) {
2491  if ( delta2>=0 ) {
2492  delta = sqrt(delta2);
2493  h = 2*sp->a*delta2*delta;
2494  temp = -yN/h;
2495  if ( temp>=-1.0001 && temp<=1.0001 ) {
2496  if ( temp<-1 ) temp = -1; else if ( temp>1 ) temp = 1;
2497  theta = acos(temp)/3;
2498  ts[i++] = xN+2*delta*cos(theta);
2499  ts[i++] = xN+2*delta*cos(2.0943951+theta);
2500  ts[i++] = xN+2*delta*cos(4.1887902+theta);
2501  }
2502  }
2503  } else if ( /* d==0 && */ delta2!=0 ) {
2504  delta = yN/(2*sp->a);
2505  delta = delta==0 ? 0 : delta>0 ? pow(delta,1./3.) : -pow(-delta,1./3.);
2506  ts[i++] = xN + delta; /* this root twice, but that's irrelevant to me */
2507  ts[i++] = xN - 2*delta;
2508  } else if ( /* d==0 && */ delta2==0 ) {
2509  if ( xN>=-0.0001 && xN<=1.0001 ) ts[0] = xN;
2510  }
2511  } else if ( sp->b!=0 ) {
2512  extended d = sp->c*(extended) sp->c-4*(extended) sp->b*sp->d;
2513  if ( RealNear(d,0)) d=0;
2514  if ( d<0 )
2515 return(false); /* All roots imaginary */
2516  d = sqrt(d);
2517  ts[0] = (-sp->c-d)/(2*(extended) sp->b);
2518  ts[1] = (-sp->c+d)/(2*(extended) sp->b);
2519  } else if ( sp->c!=0 ) {
2520  ts[0] = -sp->d/(extended) sp->c;
2521  } else {
2522  /* If it's a point then either everything is a solution, or nothing */
2523  }
2524 return( ts[0]!=-999999 );
2525 }
2526 
2527 int CubicSolve(const Spline1D *sp,extended ts[3]) {
2528  extended t;
2529  int i;
2530  /* This routine gives us all solutions between [0,1] with -1 as an error flag */
2531  /* http://mathforum.org/dr.math/faq/faq.cubic.equations.html */
2532 
2533  if ( !_CubicSolve(sp,ts)) {
2534  ts[0] = ts[1] = ts[2] = -1;
2535 return( false );
2536  }
2537 
2538  for ( i=0; i<3; ++i )
2539  if ( ts[i]==-999999 ) ts[i] = -1;
2540  if (ts[0]>1.0001 || ts[0]<-.0001 ) ts[0] = -1;
2541  else if ( ts[0]<0 ) ts[0] = 0; else if ( ts[0]>1 ) ts[0] = 1;
2542  if (ts[1]>1.0001 || ts[1]<-.0001 ) ts[1] = -1;
2543  else if ( ts[1]<0 ) ts[1] = 0; else if ( ts[1]>1 ) ts[1] = 1;
2544  if (ts[2]>1.0001 || ts[2]<-.0001 ) ts[2] = -1;
2545  else if ( ts[2]<0 ) ts[2] = 0; else if ( ts[2]>1 ) ts[2] = 1;
2546  if ( ts[1]==-1 ) { ts[1] = ts[2]; ts[2] = -1;}
2547  if ( ts[0]==-1 ) { ts[0] = ts[1]; ts[1] = ts[2]; ts[2] = -1; }
2548  if ( ts[0]==-1 )
2549 return( false );
2550  if ( ts[0]>ts[2] && ts[2]!=-1 ) {
2551  t = ts[0]; ts[0] = ts[2]; ts[2] = t;
2552  }
2553  if ( ts[0]>ts[1] && ts[1]!=-1 ) {
2554  t = ts[0]; ts[0] = ts[1]; ts[1] = t;
2555  }
2556  if ( ts[1]>ts[2] && ts[2]!=-1 ) {
2557  t = ts[1]; ts[1] = ts[2]; ts[2] = t;
2558  }
2559 return( true );
2560 }
2561 
2562 
2563 extended SplineSolve(const Spline1D *sp, real tmin, real tmax, extended sought,real err) {
2564  /* We want to find t so that spline(t) = sought */
2565  /* the curve must be monotonic */
2566  /* returns t which is near sought or -1 */
2567  Spline1D temp;
2568  extended ts[3];
2569  int i;
2570  extended t;
2571  (void)err;
2572  temp = *sp;
2573  temp.d -= sought;
2574  CubicSolve(&temp,ts);
2575  if ( tmax<tmin ) { t = tmax; tmax = tmin; tmin = t; }
2576  for ( i=0; i<3; ++i )
2577  if ( ts[i]>=tmin && ts[i]<=tmax )
2578 return( ts[i] );
2579 
2580 return( -1 );
2581 }
2582 
2583 #ifndef EXTENDED_IS_LONG_DOUBLE
2585  union { double dval; int32 ival[2]; } u1, um1, temp;
2586  double slope, slope1, slopem1;
2587 #ifdef WORDS_BIGENDIAN
2588  const int index = 1;
2589 #else
2590  const int index = 0;
2591 #endif
2592 
2593  slope = (3*(double) sp->a*t+2*sp->b)*t+sp->c;
2594 
2595  u1.dval = t;
2596  u1.ival[index] += 1;
2597  slope1 = (3*(double) sp->a*u1.dval+2*sp->b)*u1.dval+sp->c;
2598 
2599  um1.dval = t;
2600  um1.ival[index] -= 1;
2601  slopem1 = (3*(double) sp->a*um1.dval+2*sp->b)*um1.dval+sp->c;
2602 
2603  if ( slope<0 ) slope = -slope;
2604  if ( slope1<0 ) slope1 = -slope1;
2605  if ( slopem1<0 ) slopem1 = -slopem1;
2606 
2607  if ( slope1<slope && slope1<=slopem1 ) {
2608  /* Ok, things got better when we added 1. */
2609  /* Do they improve further if we add 1 more? */
2610  temp = u1;
2611  temp.ival[index] += 1;
2612  slope = (3*(double) sp->a*temp.dval+2*sp->b)*temp.dval+sp->c;
2613  if ( slope<0 ) slope = -slope;
2614  if ( slope<slope1 )
2615 return( temp.dval );
2616  else
2617 return( u1.dval );
2618  } else if ( slopem1<slope && slopem1<=slope ) {
2619  /* Ok, things got better when we subtracted 1. */
2620  /* Do they improve further if we subtract 1 more? */
2621  temp = um1;
2622  temp.ival[index] -= 1;
2623  slope = (3*(double) sp->a*temp.dval+2*sp->b)*temp.dval+sp->c;
2624  if ( slope<0 ) slope = -slope;
2625  if ( slope<slopem1 )
2626 return( temp.dval );
2627  else
2628 return( um1.dval );
2629  }
2630  /* that seems as good as it gets */
2631 
2632 return( t );
2633 }
2634 #else
2636  extended rt, temp;
2637 
2638  rt = sqrt( (double) e );
2639  if ( e<=0 )
2640 return( rt );
2641 
2642  temp = e/rt;
2643  rt = (rt+temp)/2;
2644  temp = e/rt;
2645  rt = (rt+temp)/2;
2646 return( rt );
2647 }
2648 #endif
2649 
2650 static void _SplineFindExtrema(const Spline1D *sp, extended *_t1, extended *_t2 ) {
2651  extended t1= -1, t2= -1;
2652  extended b2_fourac;
2653 
2654  /* Find the extreme points on the curve */
2655  /* Set to -1 if there are none or if they are outside the range [0,1] */
2656  /* Order them so that t1<t2 */
2657  /* If only one valid extremum it will be t1 */
2658  /* (Does not check the end points unless they have derivative==0) */
2659  /* (Does not check to see if d/dt==0 points are inflection points (rather than extrema) */
2660  if ( sp->a!=0 ) {
2661  /* cubic, possibly 2 extrema (possibly none) */
2662  b2_fourac = 4*(extended)sp->b*sp->b - 12*(extended)sp->a*sp->c;
2663  if ( b2_fourac>=0 ) {
2664  b2_fourac = esqrt(b2_fourac);
2665  t1 = (-2*sp->b - b2_fourac) / (6*sp->a);
2666  t2 = (-2*sp->b + b2_fourac) / (6*sp->a);
2669  if ( t1>t2 ) { extended temp = t1; t1 = t2; t2 = temp; }
2670  else if ( t1==t2 ) t2 = -1;
2671  if ( RealNear(t1,0)) t1=0; else if ( RealNear(t1,1)) t1=1;
2672  if ( RealNear(t2,0)) t2=0; else if ( RealNear(t2,1)) t2=1;
2673  }
2674  } else if ( sp->b!=0 ) {
2675  /* Quadratic, at most one extremum */
2676  t1 = -sp->c/(2.0*(extended) sp->b);
2677  } else /*if ( sp->c!=0 )*/ {
2678  /* linear, no extrema */
2679  }
2680  *_t1 = t1; *_t2 = t2;
2681 }
2682 
2683 void SplineFindExtrema(const Spline1D *sp, extended *_t1, extended *_t2 ) {
2684  extended t1= -1, t2= -1;
2685  extended b2_fourac;
2686 
2687  /* Find the extreme points on the curve */
2688  /* Set to -1 if there are none or if they are outside the range [0,1] */
2689  /* Order them so that t1<t2 */
2690  /* If only one valid extremum it will be t1 */
2691  /* (Does not check the end points unless they have derivative==0) */
2692  /* (Does not check to see if d/dt==0 points are inflection points (rather than extrema) */
2693  if ( sp->a!=0 ) {
2694  /* cubic, possibly 2 extrema (possibly none) */
2695  b2_fourac = 4*(extended) sp->b*sp->b - 12*(extended) sp->a*sp->c;
2696  if ( b2_fourac>=0 ) {
2697  b2_fourac = esqrt(b2_fourac);
2698  t1 = (-2*sp->b - b2_fourac) / (6*sp->a);
2699  t2 = (-2*sp->b + b2_fourac) / (6*sp->a);
2702  if ( t1>t2 ) { extended temp = t1; t1 = t2; t2 = temp; }
2703  else if ( t1==t2 ) t2 = -1;
2704  if ( RealNear(t1,0)) t1=0; else if ( RealNear(t1,1)) t1=1;
2705  if ( RealNear(t2,0)) t2=0; else if ( RealNear(t2,1)) t2=1;
2706  if ( t2<=0 || t2>=1 ) t2 = -1;
2707  if ( t1<=0 || t1>=1 ) { t1 = t2; t2 = -1; }
2708  }
2709  } else if ( sp->b!=0 ) {
2710  /* Quadratic, at most one extremum */
2711  t1 = -sp->c/(2.0*(extended) sp->b);
2712  if ( t1<=0 || t1>=1 ) t1 = -1;
2713  } else /*if ( sp->c!=0 )*/ {
2714  /* linear, no extrema */
2715  }
2716  *_t1 = t1; *_t2 = t2;
2717 }
2718 
2719 double SplineCurvature(Spline *s, double t) {
2720  /* Kappa = (x'y'' - y'x'') / (x'^2 + y'^2)^(3/2) */
2721  double dxdt, dydt, d2xdt2, d2ydt2, denom, numer;
2722 
2723  if ( s==NULL )
2724 return( CURVATURE_ERROR );
2725 
2726  dxdt = (3*s->splines[0].a*t+2*s->splines[0].b)*t+s->splines[0].c;
2727  dydt = (3*s->splines[1].a*t+2*s->splines[1].b)*t+s->splines[1].c;
2728  d2xdt2 = 6*s->splines[0].a*t + 2*s->splines[0].b;
2729  d2ydt2 = 6*s->splines[1].a*t + 2*s->splines[1].b;
2730  denom = pow( dxdt*dxdt + dydt*dydt, 3.0/2.0 );
2731  numer = dxdt*d2ydt2 - dydt*d2xdt2;
2732 
2733  if ( numer==0 )
2734 return( 0 );
2735  if ( denom==0 )
2736 return( CURVATURE_ERROR );
2737 
2738 return( numer/denom );
2739 }
2740 
2742  /* It's a point of inflection if d sp/dt==0 and d2 sp/dt^2==0 */
2743 return ( RealNear( (3*sp->a*t + 2*sp->b)*t + sp->c,0) &&
2744  RealNear( 6*sp->a*t + 2*sp->b, 0));
2745 }
2746 
2747 int SplineAtMinMax(Spline1D *sp, double t ) {
2748  /* It's a point of inflection if d sp/dt==0 and d2 sp/dt^2!=0 */
2749 return ( RealNear( (3*sp->a*t + 2*sp->b)*t + sp->c,0) &&
2750  !RealNear( 6*sp->a*t + 2*sp->b, 0));
2751 }
2752 
2753 int Spline2DFindExtrema(const Spline *sp, extended extrema[4] ) {
2754  int i,j;
2755  BasePoint last, cur, mid;
2756 
2757  SplineFindExtrema(&sp->splines[0],&extrema[0],&extrema[1]);
2758  SplineFindExtrema(&sp->splines[1],&extrema[2],&extrema[3]);
2759 
2760  for ( i=0; i<3; ++i ) for ( j=i+1; j<4; ++j ) {
2761  if ( (extrema[i]==-1 && extrema[j]!=-1) || (extrema[i]>extrema[j] && extrema[j]!=-1) ) {
2762  extended temp = extrema[i];
2763  extrema[i] = extrema[j];
2764  extrema[j] = temp;
2765  }
2766  }
2767  for ( i=j=0; i<3 && extrema[i]!=-1; ++i ) {
2768  if ( extrema[i]==extrema[i+1] ) {
2769  for ( j=i+1; j<3; ++j )
2770  extrema[j] = extrema[j+1];
2771  extrema[3] = -1;
2772  }
2773  }
2774 
2775  /* Extrema which are too close together are not interesting */
2776  last = sp->from->me;
2777  for ( i=0; i<4 && extrema[i]!=-1; ++i ) {
2778  cur.x = ((sp->splines[0].a*extrema[i]+sp->splines[0].b)*extrema[i]+
2779  sp->splines[0].c)*extrema[i]+sp->splines[0].d;
2780  cur.y = ((sp->splines[1].a*extrema[i]+sp->splines[1].b)*extrema[i]+
2781  sp->splines[1].c)*extrema[i]+sp->splines[1].d;
2782  mid.x = (last.x+cur.x)/2; mid.y = (last.y+cur.y)/2;
2783  if ( (mid.x==last.x || mid.x==cur.x) &&
2784  (mid.y==last.y || mid.y==cur.y)) {
2785  for ( j=i+1; j<3; ++j )
2786  extrema[j] = extrema[j+1];
2787  } else
2788  last = cur;
2789  }
2790  for ( i=0; i<4 && extrema[i]!=-1; ++i );
2791  if ( i!=0 ) {
2792  cur = sp->to->me;
2793  mid.x = (last.x+cur.x)/2; mid.y = (last.y+cur.y)/2;
2794  if ( (mid.x==last.x || mid.x==cur.x) &&
2795  (mid.y==last.y || mid.y==cur.y))
2796  extrema[--i] = -1;
2797  }
2798 
2799 return( i );
2800 }
2801 
2803  int cnt=0;
2804  extended a, b, c, b2_fourac, t;
2805  /* A POI happens when d2 y/dx2 is zero. This is not the same as d2y/dt2 / d2x/dt2 */
2806  /* d2 y/dx^2 = d/dt ( dy/dt / dx/dt ) / dx/dt */
2807  /* = ( (dx/dt) * d2 y/dt2 - ((dy/dt) * d2 x/dt2) )/ (dx/dt)^3 */
2808  /* (3ax*t^2+2bx*t+cx) * (6ay*t+2by) - (3ay*t^2+2by*t+cy) * (6ax*t+2bx) == 0 */
2809  /* (3ax*t^2+2bx*t+cx) * (3ay*t+by) - (3ay*t^2+2by*t+cy) * (3ax*t+bx) == 0 */
2810  /* 9*ax*ay*t^3 + (3ax*by+6bx*ay)*t^2 + (2bx*by+3cx*ay)*t + cx*by */
2811  /* -(9*ax*ay*t^3 + (3ay*bx+6by*ax)*t^2 + (2by*bx+3cy*ax)*t + cy*bx)==0 */
2812  /* 3*(ax*by-ay*bx)*t^2 + 3*(cx*ay-cy*ax)*t+ (cx*by-cy*bx) == 0 */
2813 
2814  a = 3*((extended) sp->splines[1].a*sp->splines[0].b-(extended) sp->splines[0].a*sp->splines[1].b);
2815  b = 3*((extended) sp->splines[0].c*sp->splines[1].a - (extended) sp->splines[1].c*sp->splines[0].a);
2816  c = (extended) sp->splines[0].c*sp->splines[1].b-(extended) sp->splines[1].c*sp->splines[0].b;
2817  if ( !RealNear(a,0) ) {
2818  b2_fourac = b*b - 4*a*c;
2819  poi[0] = poi[1] = -1;
2820  if ( b2_fourac<0 )
2821 return( 0 );
2822  b2_fourac = esqrt( b2_fourac );
2823  t = (-b+b2_fourac)/(2*a);
2824  if ( t>=0 && t<=1.0 )
2825  poi[cnt++] = t;
2826  t = (-b-b2_fourac)/(2*a);
2827  if ( t>=0 && t<=1.0 ) {
2828  if ( cnt==1 && poi[0]>t ) {
2829  poi[1] = poi[0];
2830  poi[0] = t;
2831  ++cnt;
2832  } else
2833  poi[cnt++] = t;
2834  }
2835  } else if ( !RealNear(b,0) ) {
2836  t = -c/b;
2837  if ( t>=0 && t<=1.0 )
2838  poi[cnt++] = t;
2839  }
2840  if ( cnt<2 )
2841  poi[cnt] = -1;
2842 
2843 return( cnt );
2844 }
2845 
2846 /* Ok, if the above routine finds an extremum that less than 1 unit */
2847 /* from an endpoint or another extremum, then many things are */
2848 /* just going to skip over it, and other things will be confused by this */
2849 /* so just remove it. It should be so close the difference won't matter */
2851  extended last, test;
2852  extended t1= *_t1, t2 = *_t2;
2853 
2854  if ( t1>t2 && t2!=-1 ) {
2855  t1 = t2;
2856  t2 = *_t1;
2857  }
2858  last = sp->d;
2859  if ( t1!=-1 ) {
2860  test = ((sp->a*t1+sp->b)*t1+sp->c)*t1+sp->d;
2861  if ( (test-last)*(test-last)<1 )
2862  t1 = -1;
2863  else
2864  last = test;
2865  }
2866  if ( t2!=-1 ) {
2867  test = ((sp->a*t2+sp->b)*t2+sp->c)*t2+sp->d;
2868  if ( (test-last)*(test-last)<1 )
2869  t2 = -1;
2870  else
2871  last = test;
2872  }
2873  test = sp->a+sp->b+sp->c+sp->d;
2874  if ( (test-last)*(test-last)<1 ) {
2875  if ( t2!=-1 )
2876  t2 = -1;
2877  else if ( t1!=-1 )
2878  t1 = -1;
2879  else {
2880  /* Well we should just remove the whole spline? */;
2881  }
2882  }
2883  *_t1 = t1; *_t2 = t2;
2884 }
2885 
2887  Spline1D temp;
2888 
2889  temp = *sp;
2890  temp.d -= val;
2891  CubicSolve(&temp,ts);
2892 return( ts[0]!=-1 );
2893 }
2894 
2896  extended t1s[3],extended t2s[3], int soln) {
2897  int i;
2898 
2899  for ( i=0; i<soln; ++i )
2900  if ( x==pts[i].x && y==pts[i].y )
2901 return( soln );
2902  if ( soln>=9 )
2903  IError( "Too many solutions!\n" );
2904  t1s[soln] = t;
2905  t2s[soln] = s;
2906  pts[soln].x = x;
2907  pts[soln].y = y;
2908 return( soln+1 );
2909 }
2910 
2911 static void IterateSolve(const Spline1D *sp,extended ts[3]) {
2912  /* The closed form solution has too many rounding errors for my taste... */
2913  int i,j;
2914 
2915  ts[0] = ts[1] = ts[2] = -1;
2916 
2917  if ( sp->a!=0 ) {
2918  extended e[4];
2919  e[0] = 0; e[1] = e[2] = e[3] = 1.0;
2920  SplineFindExtrema(sp,&e[1],&e[2]);
2921  if ( e[1]==-1 ) e[1] = 1;
2922  if ( e[2]==-1 ) e[2] = 1;
2923  for ( i=j=0; i<3; ++i ) {
2924  ts[j] = IterateSplineSolve(sp,e[i],e[i+1],0,.0001);
2925  if ( ts[j]!=-1 ) ++j;
2926  if ( e[i+1]==1.0 )
2927  break;
2928  }
2929  } else if ( sp->b!=0 ) {
2930  extended b2_4ac = sp->c*(extended) sp->c - 4*sp->b*(extended) sp->d;
2931  if ( b2_4ac>=0 ) {
2932  b2_4ac = esqrt(b2_4ac);
2933  ts[0] = (-sp->c-b2_4ac)/(2*sp->b);
2934  ts[1] = (-sp->c+b2_4ac)/(2*sp->b);
2935  if ( ts[0]>ts[1] ) { bigreal t = ts[0]; ts[0] = ts[1]; ts[1] = t; }
2936  }
2937  } else if ( sp->c!=0 ) {
2938  ts[0] = -sp->d/(extended) sp->c;
2939  } else {
2940  /* No solutions, or all solutions */;
2941  }
2942  for ( i=j=0; i<3; ++i )
2943  if ( ts[i]>=0 && ts[i]<=1 )
2944  ts[j++] = ts[i];
2945  for ( i=0; i<j-1; ++i )
2946  if ( ts[i]+.0000001>ts[i+1]) {
2947  ts[i] = (ts[i]+ts[i+1])/2;
2948  --j;
2949  for ( ++i; i<j; ++i )
2950  ts[i] = ts[i+1];
2951  }
2952  if ( j!=0 ) {
2953  if ( ts[0]!=0 ) {
2954  extended d0 = sp->d;
2955  extended dt = ((sp->a*ts[0]+sp->b)*ts[0]+sp->c)*ts[0]+sp->d;
2956  if ( d0<0 ) d0=-d0;
2957  if ( dt<0 ) dt=-dt;
2958  if ( d0<dt )
2959  ts[0] = 0;
2960  }
2961  if ( ts[j-1]!=1.0 ) {
2962  extended d1 = sp->a+(extended) sp->b+sp->c+sp->d;
2963  extended dt = ((sp->a*ts[j-1]+sp->b)*ts[j-1]+sp->c)*ts[j-1]+sp->d;
2964  if ( d1<0 ) d1=-d1;
2965  if ( dt<0 ) dt=-dt;
2966  if ( d1<dt )
2967  ts[j-1] = 1;
2968  }
2969  }
2970  for ( ; j<3; ++j )
2971  ts[j] = -1;
2972 }
2973 
2975  Spline1D temp;
2976  extended ts[3];
2977  int i;
2978 
2979  temp = *sp;
2980  temp.d -= val;
2981  IterateSolve(&temp,ts);
2982  if ( tlow<thigh ) {
2983  for ( i=0; i<3; ++i )
2984  if ( ts[i]>=tlow && ts[i]<=thigh )
2985 return( ts[i] );
2986  for ( i=0; i<3; ++i ) {
2987  if ( ts[i]>=tlow-1./1024. && ts[i]<=tlow )
2988 return( tlow );
2989  if ( ts[i]>=thigh && ts[i]<=thigh+1./1024 )
2990 return( thigh );
2991  }
2992  } else {
2993  for ( i=0; i<3; ++i )
2994  if ( ts[i]>=thigh && ts[i]<=tlow )
2995 return( ts[i] );
2996  for ( i=0; i<3; ++i ) {
2997  if ( ts[i]>=thigh-1./1024. && ts[i]<=thigh )
2998 return( thigh );
2999  if ( ts[i]>=tlow && ts[i]<=tlow+1./1024 )
3000 return( tlow );
3001  }
3002  }
3003 return( -1 );
3004 }
3005 
3006 static int ICAddInter(int cnt,BasePoint *foundpos,extended *foundt1,extended *foundt2,
3007  const Spline *s1,const Spline *s2,extended t1,extended t2, int maxcnt) {
3008  (void)s2;
3009  if ( cnt>=maxcnt )
3010 return( cnt );
3011 
3012  foundt1[cnt] = t1;
3013  foundt2[cnt] = t2;
3014  foundpos[cnt].x = ((s1->splines[0].a*t1+s1->splines[0].b)*t1+
3015  s1->splines[0].c)*t1+s1->splines[0].d;
3016  foundpos[cnt].y = ((s1->splines[1].a*t1+s1->splines[1].b)*t1+
3017  s1->splines[1].c)*t1+s1->splines[1].d;
3018 return( cnt+1 );
3019 }
3020 
3021 static int ICBinarySearch(int cnt,BasePoint *foundpos,extended *foundt1,extended *foundt2,
3022  int other,
3023  const Spline *s1,const Spline *s2,extended t1low,extended t1high,extended t2low,extended t2high,
3024  int maxcnt) {
3025  int major;
3026  extended t1, t2;
3027  extended o1o, o2o, o1n, o2n, m;
3028 
3029  major = !other;
3030  o1o = ((s1->splines[other].a*t1low+s1->splines[other].b)*t1low+
3031  s1->splines[other].c)*t1low+s1->splines[other].d;
3032  o2o = ((s2->splines[other].a*t2low+s2->splines[other].b)*t2low+
3033  s2->splines[other].c)*t2low+s2->splines[other].d;
3034  forever {
3035  t1 = (t1low+t1high)/2;
3036  m = ((s1->splines[major].a*t1+s1->splines[major].b)*t1+
3037  s1->splines[major].c)*t1+s1->splines[major].d;
3038  t2 = ISolveWithin(&s2->splines[major],m,t2low,t2high);
3039  if ( t2==-1 )
3040 return( cnt );
3041 
3042  o1n = ((s1->splines[other].a*t1+s1->splines[other].b)*t1+
3043  s1->splines[other].c)*t1+s1->splines[other].d;
3044  o2n = ((s2->splines[other].a*t2+s2->splines[other].b)*t2+
3045  s2->splines[other].c)*t2+s2->splines[other].d;
3046  if (( o1n-o2n<.001 && o1n-o2n>-.001) ||
3047  (t1-t1low<.0001 && t1-t1low>-.0001))
3048 return( ICAddInter(cnt,foundpos,foundt1,foundt2,s1,s2,t1,t2,maxcnt));
3049  if ( (o1o>o2o && o1n<o2n) || (o1o<o2o && o1n>o2n)) {
3050  t1high = t1;
3051  t2high = t2;
3052  } else {
3053  t1low = t1;
3054  t2low = t2;
3055  }
3056  }
3057 }
3058 
3059 static int CubicsIntersect(const Spline *s1,extended lowt1,extended hight1,BasePoint *min1,BasePoint *max1,
3060  const Spline *s2,extended lowt2,extended hight2,BasePoint *min2,BasePoint *max2,
3061  BasePoint *foundpos,extended *foundt1,extended *foundt2,
3062  int maxcnt) {
3063  int major, other;
3064  BasePoint max, min;
3065  extended t1max, t1min, t2max, t2min, t1, t2, t1diff, oldt2;
3066  extended o1o, o2o, o1n, o2n, m;
3067  int cnt=0;
3068 
3069  if ( (min.x = min1->x)<min2->x ) min.x = min2->x;
3070  if ( (min.y = min1->y)<min2->y ) min.y = min2->y;
3071  if ( (max.x = max1->x)>max2->x ) max.x = max2->x;
3072  if ( (max.y = max1->y)>max2->y ) max.y = max2->y;
3073  if ( max.x<min.x || max.y<min.y )
3074 return( 0 );
3075  if ( max.x-min.x > max.y-min.y )
3076  major = 0;
3077  else
3078  major = 1;
3079  other = 1-major;
3080 
3081  t1max = ISolveWithin(&s1->splines[major],(&max.x)[major],lowt1,hight1);
3082  t1min = ISolveWithin(&s1->splines[major],(&min.x)[major],lowt1,hight1);
3083  t2max = ISolveWithin(&s2->splines[major],(&max.x)[major],lowt2,hight2);
3084  t2min = ISolveWithin(&s2->splines[major],(&min.x)[major],lowt2,hight2);
3085  if ( t1max==-1 || t1min==-1 || t2max==-1 || t1min==-1 )
3086 return( 0 );
3087  t1diff = (t1max-t1min)/64.0;
3088  if ( t1diff==0 )
3089 return( 0 );
3090 
3091  t1 = t1min; t2 = t2min;
3092  o1o = ((s1->splines[other].a*t1+s1->splines[other].b)*t1+
3093  s1->splines[other].c)*t1+s1->splines[other].d;
3094  o2o = ((s2->splines[other].a*t2+s2->splines[other].b)*t2+
3095  s2->splines[other].c)*t2+s2->splines[other].d;
3096  if ( o1o==o2o )
3097  cnt = ICAddInter(cnt,foundpos,foundt1,foundt2,s1,s2,t1,t2,maxcnt);
3098  forever {
3099  if ( cnt>=maxcnt )
3100  break;
3101  t1 += t1diff;
3102  if (( t1max>t1min && t1>t1max ) || (t1max<t1min && t1<t1max) || cnt>3 )
3103  break;
3104  m = ((s1->splines[major].a*t1+s1->splines[major].b)*t1+
3105  s1->splines[major].c)*t1+s1->splines[major].d;
3106  oldt2 = t2;
3107  t2 = ISolveWithin(&s2->splines[major],m,lowt2,hight2);
3108  if ( t2==-1 )
3109  continue;
3110 
3111  o1n = ((s1->splines[other].a*t1+s1->splines[other].b)*t1+
3112  s1->splines[other].c)*t1+s1->splines[other].d;
3113  o2n = ((s2->splines[other].a*t2+s2->splines[other].b)*t2+
3114  s2->splines[other].c)*t2+s2->splines[other].d;
3115  if ( o1n==o2n )
3116  cnt = ICAddInter(cnt,foundpos,foundt1,foundt2,s1,s2,t1,t2,maxcnt);
3117  if ( (o1o>o2o && o1n<o2n) || (o1o<o2o && o1n>o2n))
3118  cnt = ICBinarySearch(cnt,foundpos,foundt1,foundt2,other,
3119  s1,s2,t1-t1diff,t1,oldt2,t2,maxcnt);
3120  o1o = o1n; o2o = o2n;
3121  }
3122 return( cnt );
3123 }
3124 
3125 
3126 
3127 
3128 static int Closer(const Spline *s1,const Spline *s2,extended t1,extended t2,extended t1p,extended t2p) {
3129  double dx,dy;
3130  double x1 = ((s1->splines[0].a*t1+s1->splines[0].b)*t1+s1->splines[0].c)*t1+s1->splines[0].c;
3131  double y1 = ((s1->splines[1].a*t1+s1->splines[1].b)*t1+s1->splines[1].c)*t1+s1->splines[1].c;
3132  double x2 = ((s2->splines[0].a*t2+s2->splines[0].b)*t2+s2->splines[0].c)*t2+s2->splines[0].c;
3133  double y2 = ((s2->splines[1].a*t2+s2->splines[1].b)*t2+s2->splines[1].c)*t2+s2->splines[1].c;
3134  double diff = FABS(x1-x2) + FABS(y1-y2);
3135  double x1p = ((s1->splines[0].a*t1p+s1->splines[0].b)*t1p+s1->splines[0].c)*t1p+s1->splines[0].c;
3136  double y1p = ((s1->splines[1].a*t1p+s1->splines[1].b)*t1p+s1->splines[1].c)*t1p+s1->splines[1].c;
3137  double x2p = ((s2->splines[0].a*t2p+s2->splines[0].b)*t2p+s2->splines[0].c)*t2p+s2->splines[0].c;
3138  double y2p = ((s2->splines[1].a*t2p+s2->splines[1].b)*t2p+s2->splines[1].c)*t2p+s2->splines[1].c;
3139  double diffp = FABS(x1p-x2p) + FABS(y1p-y2p);
3140  if ( diff<diffp )
3141 return( false );
3142 
3143 return( true );
3144 }
3145 
3146 /* returns 0=>no intersection, 1=>at least one, location in pts, t1s, t2s */
3147 /* -1 => We couldn't figure it out in a closed form, have to do a numerical */
3148 /* approximation */
3149 int SplinesIntersect(const Spline *s1, const Spline *s2, BasePoint pts[9],
3150  extended t1s[10], extended t2s[10]) { /* One extra for a trailing -1 */
3151  BasePoint min1, max1, min2, max2;
3152  int soln = 0;
3153  extended x,y,t, ac0, ac1;
3154  int i,j,found;
3155  Spline1D spline;
3156  extended tempts[4]; /* 3 solns for cubics, 4 for quartics */
3157  extended extrema1[6], extrema2[6];
3158  int ecnt1, ecnt2;
3159 
3160  t1s[0] = t1s[1] = t1s[2] = t1s[3] = -1;
3161  t2s[0] = t2s[1] = t2s[2] = t2s[3] = -1;
3162 
3163  if ( s1==s2 && !s1->knownlinear && !s1->isquadratic )
3164  /* Special case see if it doubles back on itself anywhere */;
3165  else if ( s1==s2 )
3166 return( 0 ); /* Linear and quadratics can't double back, can't self-intersect */
3167  else if ( s1->splines[0].a == s2->splines[0].a &&
3168  s1->splines[0].b == s2->splines[0].b &&
3169  s1->splines[0].c == s2->splines[0].c &&
3170  s1->splines[0].d == s2->splines[0].d &&
3171  s1->splines[1].a == s2->splines[1].a &&
3172  s1->splines[1].b == s2->splines[1].b &&
3173  s1->splines[1].c == s2->splines[1].c &&
3174  s1->splines[1].d == s2->splines[1].d )
3175 return( -1 ); /* Same spline. Intersects everywhere */
3176 
3177  /* Ignore splines which are just a point */
3178  if ( s1->knownlinear && s1->splines[0].c==0 && s1->splines[1].c==0 )
3179 return( 0 );
3180  if ( s2->knownlinear && s2->splines[0].c==0 && s2->splines[1].c==0 )
3181 return( 0 );
3182 
3183  if ( s1->knownlinear )
3184  /* Do Nothing */;
3185  else if ( s2->knownlinear || (!s1->isquadratic && s2->isquadratic)) {
3186  const Spline *stemp = s1;
3187  extended *ts = t1s;
3188  t1s = t2s; t2s = ts;
3189  s1 = s2; s2 = stemp;
3190  }
3191 
3192  min1 = s1->from->me; max1 = min1;
3193  min2 = s2->from->me; max2 = min2;
3194  if ( s1->from->nextcp.x>max1.x ) max1.x = s1->from->nextcp.x;
3195  else if ( s1->from->nextcp.x<min1.x ) min1.x = s1->from->nextcp.x;
3196  if ( s1->from->nextcp.y>max1.y ) max1.y = s1->from->nextcp.y;
3197  else if ( s1->from->nextcp.y<min1.y ) min1.y = s1->from->nextcp.y;
3198  if ( s1->to->prevcp.x>max1.x ) max1.x = s1->to->prevcp.x;
3199  else if ( s1->to->prevcp.x<min1.x ) min1.x = s1->to->prevcp.x;
3200  if ( s1->to->prevcp.y>max1.y ) max1.y = s1->to->prevcp.y;
3201  else if ( s1->to->prevcp.y<min1.y ) min1.y = s1->to->prevcp.y;
3202  if ( s1->to->me.x>max1.x ) max1.x = s1->to->me.x;
3203  else if ( s1->to->me.x<min1.x ) min1.x = s1->to->me.x;
3204  if ( s1->to->me.y>max1.y ) max1.y = s1->to->me.y;
3205  else if ( s1->to->me.y<min1.y ) min1.y = s1->to->me.y;
3206 
3207  if ( s2->from->nextcp.x>max2.x ) max2.x = s2->from->nextcp.x;
3208  else if ( s2->from->nextcp.x<min2.x ) min2.x = s2->from->nextcp.x;
3209  if ( s2->from->nextcp.y>max2.y ) max2.y = s2->from->nextcp.y;
3210  else if ( s2->from->nextcp.y<min2.y ) min2.y = s2->from->nextcp.y;
3211  if ( s2->to->prevcp.x>max2.x ) max2.x = s2->to->prevcp.x;
3212  else if ( s2->to->prevcp.x<min2.x ) min2.x = s2->to->prevcp.x;
3213  if ( s2->to->prevcp.y>max2.y ) max2.y = s2->to->prevcp.y;
3214  else if ( s2->to->prevcp.y<min2.y ) min2.y = s2->to->prevcp.y;
3215  if ( s2->to->me.x>max2.x ) max2.x = s2->to->me.x;
3216  else if ( s2->to->me.x<min2.x ) min2.x = s2->to->me.x;
3217  if ( s2->to->me.y>max2.y ) max2.y = s2->to->me.y;
3218  else if ( s2->to->me.y<min2.y ) min2.y = s2->to->me.y;
3219  if ( min1.x>max2.x || min2.x>max1.x || min1.y>max2.y || min2.y>max1.y )
3220 return( false ); /* no intersection of bounding boxes */
3221 
3222 #if 0
3223  soln = CheckEndpoint(&s1->from->me,s2,0,pts,t1s,t2s,soln);
3224  soln = CheckEndpoint(&s1->to->me,s2,1,pts,t1s,t2s,soln);
3225  soln = CheckEndpoint(&s2->from->me,s1,0,pts,t2s,t1s,soln);
3226  soln = CheckEndpoint(&s2->to->me,s1,1,pts,t2s,t1s,soln);
3227 #endif
3228 
3229  if ( s1->knownlinear ) {
3230  spline.d = s1->splines[1].c*((bigreal) s2->splines[0].d-(bigreal) s1->splines[0].d)-
3231  s1->splines[0].c*((bigreal) s2->splines[1].d-(bigreal) s1->splines[1].d);
3232  spline.c = s1->splines[1].c*(bigreal) s2->splines[0].c - s1->splines[0].c*(bigreal) s2->splines[1].c;
3233  spline.b = s1->splines[1].c*(bigreal) s2->splines[0].b - s1->splines[0].c*(bigreal) s2->splines[1].b;
3234  spline.a = s1->splines[1].c*(bigreal) s2->splines[0].a - s1->splines[0].c*(bigreal) s2->splines[1].a;
3235  IterateSolve(&spline,tempts);
3236  if ( tempts[0]==-1 )
3237 return( false );
3238  for ( i = 0; i<3 && tempts[i]!=-1; ++i ) {
3239  x = ((s2->splines[0].a*tempts[i]+s2->splines[0].b)*tempts[i]+
3240  s2->splines[0].c)*tempts[i]+s2->splines[0].d;
3241  y = ((s2->splines[1].a*tempts[i]+s2->splines[1].b)*tempts[i]+
3242  s2->splines[1].c)*tempts[i]+s2->splines[1].d;
3243  if ( (ac0 = s1->splines[0].c)<0 ) ac0 = -ac0;
3244  if ( (ac1 = s1->splines[1].c)<0 ) ac1 = -ac1;
3245  if ( ac0>ac1 )
3246  t = (x-s1->splines[0].d)/s1->splines[0].c;
3247  else
3248  t = (y-s1->splines[1].d)/s1->splines[1].c;
3249  if ( tempts[i]>.999 && Closer(s1,s2,tempts[i],t,1,t))
3250  tempts[i] = 1;
3251  else if ( tempts[i]<.001 && Closer(s1,s2,tempts[i],t,0,t))
3252  tempts[i] = 0;
3253  if ( t>.999 && Closer(s1,s2,tempts[i],t,tempts[i],1))
3254  t = 1;
3255  else if ( t<.001 && Closer(s1,s2,tempts[i],t,tempts[i],0))
3256  t = 0;
3257  if ( t<-.001 || t>1.001 || x<min1.x-.01 || y<min1.y-.01 || x>max1.x+.01 || y>max1.y+.01 )
3258  continue;
3259  if ( t<=0 ) {t=0; x=s1->from->me.x; y = s1->from->me.y; }
3260  else if ( t>=1 ) { t=1; x=s1->to->me.x; y = s1->to->me.y; }
3261  if ( s1->from->me.x==s1->to->me.x ) /* Avoid rounding errors */
3262  x = s1->from->me.x; /* on hor/vert lines */
3263  else if ( s1->from->me.y==s1->to->me.y )
3264  y = s1->from->me.y;
3265  if ( s2->knownlinear ) {
3266  if ( s2->from->me.x==s2->to->me.x )
3267  x = s2->from->me.x;
3268  else if ( s2->from->me.y==s2->to->me.y )
3269  y = s2->from->me.y;
3270  }
3271  soln = AddPoint(x,y,t,tempts[i],pts,t1s,t2s,soln);
3272  }
3273 return( soln!=0 );
3274 #if 0 /* This doesn't work. */
3275  } else if ( s1->isquadratic && s2->isquadratic ) {
3276  temp.a = 0;
3277  temp.b = s1->splines[1].b*s2->splines[0].b - s1->splines[0].b*s2->splines[1].b;
3278  temp.c = s1->splines[1].b*s2->splines[0].c - s1->splines[0].b*s2->splines[1].c;
3279  temp.d = s1->splines[1].b*(s2->splines[0].d-s1->splines[0].d) -
3280  s1->splines[0].b*(s2->splines[1].d-s1->splines[1].d);
3281  d = s1->splines[1].b*s1->splines[0].c - s1->splines[0].b*s1->splines[1].c;
3282  if ( RealNear(d,0)) d=0;
3283  if ( d!=0 ) {
3284  temp.b /= d; temp.c /= d; temp.d /= d;
3285  /* At this point t= temp.b*s^2 + temp.c*s + temp.d */
3286  /* We substitute this back into one of our equations and get a */
3287  /* quartic in s */
3288  quad.a = s1->splines[0].b*temp.b*temp.b;
3289  quad.b = s1->splines[0].b*2*temp.b*temp.c;
3290  quad.c = s1->splines[0].b*(2*temp.b*temp.d+temp.c*temp.c);
3291  quad.d = s1->splines[0].b*2*temp.d*temp.c;
3292  quad.e = s1->splines[0].b*temp.d*temp.d;
3293  quad.b+= s1->splines[0].c*temp.b;
3294  quad.c+= s1->splines[0].c*temp.c;
3295  quad.d+= s1->splines[0].c*temp.d;
3296  quad.e+= s1->splines[0].d;
3297  quad.e-= s2->splines[0].d;
3298  quad.d-= s2->splines[0].c;
3299  quad.c-= s2->splines[0].b;
3300  if ( QuarticSolve(&quad,tempts)==-1 )
3301 return( -1 );
3302  for ( i=0; i<4 && tempts[i]!=-999999; ++i )
3303  soln = AddQuadraticSoln(tempts[i],s1,s2,pts,t1s,t2s,soln);
3304  } else {
3305  d = temp.c*temp.c-4*temp.b*temp.c;
3306  if ( RealNear(d,0)) d = 0;
3307  if ( d<0 )
3308 return( soln!=0 );
3309  d = sqrt(d);
3310  s = (-temp.c-d)/(2*temp.b);
3311  soln = AddQuadraticSoln(s,s1,s2,pts,t1s,t2s,soln);
3312  s = (-temp.c+d)/(2*temp.b);
3313  soln = AddQuadraticSoln(s,s1,s2,pts,t1s,t2s,soln);
3314  }
3315 return( soln!=0 );
3316 #endif
3317  }
3318  /* if one of the splines is quadratic then we can get an expression */
3319  /* relating c*t+d to poly(s^3), and substituting this back we get */
3320  /* a poly of degree 6 in s which could be solved iteratively */
3321  /* however mixed quadratics and cubics are unlikely */
3322 
3323  /* but if both splines are degree 3, the t is expressed as the sqrt of */
3324  /* a third degree poly, which must be substituted into a cubic, and */
3325  /* then squared to get rid of the sqrts leaving us with an ?18? degree */
3326  /* poly. Ick. */
3327 
3328  /* So let's do it the hard way... we break the splines into little bits */
3329  /* where they are monotonic in both dimensions, then check these for */
3330  /* possible intersections */
3331  extrema1[0] = extrema2[0] = 0;
3332  ecnt1 = Spline2DFindExtrema(s1,extrema1+1);
3333  ecnt2 = Spline2DFindExtrema(s2,extrema2+1);
3334  extrema1[++ecnt1] = 1.0;
3335  extrema2[++ecnt2] = 1.0;
3336  found=0;
3337  for ( i=0; i<ecnt1; ++i ) {
3338  min1.x = ((s1->splines[0].a*extrema1[i]+s1->splines[0].b)*extrema1[i]+
3339  s1->splines[0].c)*extrema1[i]+s1->splines[0].d;
3340  min1.y = ((s1->splines[1].a*extrema1[i]+s1->splines[1].b)*extrema1[i]+
3341  s1->splines[1].c)*extrema1[i]+s1->splines[1].d;
3342  max1.x = ((s1->splines[0].a*extrema1[i+1]+s1->splines[0].b)*extrema1[i+1]+
3343  s1->splines[0].c)*extrema1[i+1]+s1->splines[0].d;
3344  max1.y = ((s1->splines[1].a*extrema1[i+1]+s1->splines[1].b)*extrema1[i+1]+