1 /* Copyright (C) 2000-2012 by George Williams */
2 /*
3  * Redistribution and use in source and binary forms, with or without
4  * modification, are permitted provided that the following conditions are met:
5 
6  * Redistributions of source code must retain the above copyright notice, this
7  * list of conditions and the following disclaimer.
8 
9  * Redistributions in binary form must reproduce the above copyright notice,
10  * this list of conditions and the following disclaimer in the documentation
11  * and/or other materials provided with the distribution.
12 
13  * The name of the author may not be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15 
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
17  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
19  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 #include <fontforge-config.h>
29 
30 #include "splineorder2.h"
31 
32 #include "chardata.h"
33 #include "fontforge.h"
34 #include "splinerefigure.h"
35 #include "splineutil.h"
36 #include "splineutil2.h"
37 #include "ustring.h"
38 #include "utype.h"
39 
40 #include <locale.h>
41 #include <math.h>
42 #include <time.h>
43 #include <unistd.h>
44 #ifdef HAVE_IEEEFP_H
45 # include <ieeefp.h>		/* Solaris defines isnan in ieeefp rather than math.h */
46 #endif
47 
48 /* This file contains utility routines for second order bezier splines   */
49 /*  (ie. truetype)							 */
50 /* The most interesting thing						 */
51 /*  it does is to figure out a quadratic approximation to the cubic splines */
52 /*  that postscript uses. We do this by looking at each spline and running */
53 /*  from the end toward the beginning, checking approximately every emunit */
54 /*  There is only one quadratic spline possible for any given interval of the */
55 /*  cubic. The start and end points are the interval end points (obviously) */
56 /*  the control point is where the two slopes (at start and end) intersect. */
57 /* If this spline is a close approximation to the cubic spline (doesn't */
58 /*  deviate from it by more than an emunit or so), then we use this interval */
59 /*  as one of our quadratic splines. */
60 /* It may turn out that the "quadratic" spline above is actually linear. Well */
61 /*  that's ok. It may also turn out that we can't find a good approximation. */
62 /*  If that's true then just insert a linear segment for an emunit stretch. */
63 /*  (actually this failure mode may not be possible), but I'm not sure */
64 /* Then we play the same trick for the rest of the cubic spline (if any) */
65 
66 /* Does the quadratic spline in ttf approximate the cubic spline in ps */
67 /*  within one pixel between tmin and tmax (on ps. presumably ttf between 0&1 */
68 /* dim is the dimension in which there is the greatest change */
comparespline(Spline * ps,Spline * ttf,real tmin,real tmax,real err)69 static int comparespline(Spline *ps, Spline *ttf, real tmin, real tmax, real err) {
70     int dim=0, other;
71     real dx, dy, ddim, dt, t;
72     real d, o;
73     real ttf_t, sq, val;
74     DBounds bb;
75     extended ts[3];
76     int i;
77 
78     /* Are all points on ttf near points on ps? */
79     /* This doesn't answer that question, but rules out gross errors */
80     bb.minx = bb.maxx = ps->from->me.x; bb.miny = bb.maxy = ps->from->me.y;
81     if ( ps->from->nextcp.x>bb.maxx ) bb.maxx = ps->from->nextcp.x;
82     else bb.minx = ps->from->nextcp.x;
83     if ( ps->from->nextcp.y>bb.maxy ) bb.maxy = ps->from->nextcp.y;
84     else bb.miny = ps->from->nextcp.y;
85     if ( ps->to->prevcp.x>bb.maxx ) bb.maxx = ps->to->prevcp.x;
86     else if ( ps->to->prevcp.x<bb.minx ) bb.minx = ps->to->prevcp.x;
87     if ( ps->to->prevcp.y>bb.maxy ) bb.maxy = ps->to->prevcp.y;
88     else if ( ps->to->prevcp.y<bb.miny ) bb.miny = ps->to->prevcp.y;
89     if ( ps->to->me.x>bb.maxx ) bb.maxx = ps->to->me.x;
90     else if ( ps->to->me.x<bb.minx ) bb.minx = ps->to->me.x;
91     if ( ps->to->me.y>bb.maxy ) bb.maxy = ps->to->me.y;
92     else if ( ps->to->me.y<bb.miny ) bb.miny = ps->to->me.y;
93     for ( t=.1; t<0.99; t+= .1 ) {
94 	d = (ttf->splines[0].b*t+ttf->splines[0].c)*t+ttf->splines[0].d;
95 	o = (ttf->splines[1].b*t+ttf->splines[1].c)*t+ttf->splines[1].d;
96 	if ( d<bb.minx || d>bb.maxx || o<bb.miny || o>bb.maxy )
97 return( false );
98     }
99 
100     /* Are all points on ps near points on ttf? */
101     dx = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax -
102 	 ((ps->splines[0].a*tmin+ps->splines[0].b)*tmin+ps->splines[0].c)*tmin ;
103     dy = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax -
104 	 ((ps->splines[1].a*tmin+ps->splines[1].b)*tmin+ps->splines[1].c)*tmin ;
105     if ( dx<0 ) dx = -dx;
106     if ( dy<0 ) dy = -dy;
107     if ( dx>dy ) {
108 	dim = 0;
109 	ddim = dx;
110     } else {
111 	dim = 1;
112 	ddim = dy;
113     }
114     other = !dim;
115 
116     t = tmin;
117     dt = (tmax-tmin)/ddim;
118     for ( t=tmin; t<=tmax; t+= dt ) {
119 	if ( t>tmax-dt/8. ) t = tmax;		/* Avoid rounding errors */
120 	d = ((ps->splines[dim].a*t+ps->splines[dim].b)*t+ps->splines[dim].c)*t+ps->splines[dim].d;
121 	o = ((ps->splines[other].a*t+ps->splines[other].b)*t+ps->splines[other].c)*t+ps->splines[other].d;
122 	if ( ttf->splines[dim].b == 0 ) {
123 	    ttf_t = (d-ttf->splines[dim].d)/ttf->splines[dim].c;
124 	} else {
125 	    sq = ttf->splines[dim].c*ttf->splines[dim].c -
126 		    4*ttf->splines[dim].b*(ttf->splines[dim].d-d);
127 	    if ( sq<0 )
128 return( false );
129 	    sq = sqrt(sq);
130 	    ttf_t = (-ttf->splines[dim].c-sq)/(2*ttf->splines[dim].b);
131 	    if ( ttf_t>=-0.1 && ttf_t<=1.1 ) {		/* Optimizer gives us rounding errors */
132 				    /* And tmin/tmax are no longer exact */
133 		val = (ttf->splines[other].b*ttf_t+ttf->splines[other].c)*ttf_t+
134 			    ttf->splines[other].d;
135 		if ( val>o-err && val<o+err )
136     continue;
137 	    }
138 	    ttf_t = (-ttf->splines[dim].c+sq)/(2*ttf->splines[dim].b);
139 	}
140 	if ( ttf_t>=-0.1 && ttf_t<=1.1 ) {
141 	    val = (ttf->splines[other].b*ttf_t+ttf->splines[other].c)*ttf_t+
142 			ttf->splines[other].d;
143 	    if ( val>o-err && val<o+err )
144     continue;
145 	}
146 return( false );
147     }
148 
149     /* Are representative points on ttf near points on ps? */
150     for ( t=.125; t<1; t+= .125 ) {
151 	d = (ttf->splines[dim].b*t+ttf->splines[dim].c)*t+ttf->splines[dim].d;
152 	o = (ttf->splines[other].b*t+ttf->splines[other].c)*t+ttf->splines[other].d;
153 	CubicSolve(&ps->splines[dim],d,ts);
154 	for ( i=0; i<3; ++i ) if ( ts[i]!=-1 ) {
155 	    val = ((ps->splines[other].a*ts[i]+ps->splines[other].b)*ts[i]+ps->splines[other].c)*ts[i]+ps->splines[other].d;
156 	    if ( val>o-err && val<o+err )
157 	break;
158 	}
159 	if ( i==3 )
160 return( false );
161     }
162 
163 return( true );
164 }
165 
MakeQuadSpline(SplinePoint * start,Spline * ttf,real x,real y,real tmax,SplinePoint * oldend)166 static SplinePoint *MakeQuadSpline(SplinePoint *start,Spline *ttf,real x,
167 	real y, real tmax,SplinePoint *oldend) {
168     Spline *new = chunkalloc(sizeof(Spline));
169     SplinePoint *end = chunkalloc(sizeof(SplinePoint));
170 
171     if ( tmax==1 ) {
172 	end->roundx = oldend->roundx; end->roundy = oldend->roundy; end->dontinterpolate = oldend->dontinterpolate;
173 	x = oldend->me.x; y = oldend->me.y;	/* Want it to compare exactly */
174     }
175     end->ttfindex = 0xfffe;
176     end->nextcpindex = 0xfffe;
177     end->me.x = end->nextcp.x = x;
178     end->me.y = end->nextcp.y = y;
179     end->nonextcp = true;
180 
181     *new = *ttf;
182     new->from = start;		start->next = new;
183     new->to = end;		end->prev = new;
184     if ( new->splines[0].b==0 && new->splines[1].b==0 ) {
185 	end->noprevcp = true;
186 	end->prevcp.x = x; end->prevcp.y = y;
187 	new->islinear = new->knownlinear = true;
188     } else {
189 	end->prevcp.x = start->nextcp.x = ttf->splines[0].c/2+ttf->splines[0].d;
190 	end->prevcp.y = start->nextcp.y = ttf->splines[1].c/2+ttf->splines[1].d;
191 	start->nonextcp = end->noprevcp = false;
192 	new->isquadratic = true;
193     }
194     new->order2 = true;
195 return( end );
196 }
197 
buildtestquads(Spline * ttf,real xmin,real ymin,real cx,real cy,real x,real y,real tmin,real t,real err,Spline * ps,DBounds * psbb)198 static int buildtestquads(Spline *ttf,real xmin,real ymin,real cx,real cy,
199 	real x,real y,real tmin,real t,real err,Spline *ps, DBounds *psbb) {
200     real fudge, normal, para;
201     BasePoint segdir, cpdir;
202 
203     /* test the control points are reasonable */
204     fudge = (psbb->maxx-psbb->minx) + (psbb->maxy-psbb->miny);
205     if ( cx<psbb->minx-fudge || cx>psbb->maxx+fudge )
206 return( false );
207     if ( cy<psbb->miny-fudge || cy>psbb->maxy+fudge )
208 return( false );
209 
210     segdir.x = x-xmin; segdir.y = y-ymin;
211     cpdir.x = cx-xmin; cpdir.y = cy-ymin;
212     para = segdir.x*cpdir.x + segdir.y*cpdir.y;
213     if ( (normal = segdir.x*cpdir.y - segdir.y*cpdir.x)<0 )
214 	normal=-normal;
215     if ( para<0 && -para >4*normal )
216 return( false );
217     cpdir.x = x-cx; cpdir.y = y-cy;
218     para = segdir.x*cpdir.x + segdir.y*cpdir.y;
219     if ( (normal = segdir.x*cpdir.y - segdir.y*cpdir.x)<0 )
220 	normal=-normal;
221     if ( para<0 && -para >4*normal )
222 return( false );
223 
224     ttf->splines[0].d = xmin;
225     ttf->splines[0].c = 2*(cx-xmin);
226     ttf->splines[0].b = xmin+x-2*cx;
227     ttf->splines[1].d = ymin;
228     ttf->splines[1].c = 2*(cy-ymin);
229     ttf->splines[1].b = ymin+y-2*cy;
230     if ( comparespline(ps,ttf,tmin,t,err) )
231 return( true );
232 
233 return( false );
234 }
235 
LinearSpline(Spline * ps,SplinePoint * start,real tmax)236 static SplinePoint *LinearSpline(Spline *ps,SplinePoint *start, real tmax) {
237     real x,y;
238     Spline *new = chunkalloc(sizeof(Spline));
239     SplinePoint *end = chunkalloc(sizeof(SplinePoint));
240 
241     x = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax+ps->splines[0].d;
242     y = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax+ps->splines[1].d;
243     if ( tmax==1 ) {
244 	SplinePoint *oldend = ps->to;
245 	end->roundx = oldend->roundx; end->roundy = oldend->roundy; end->dontinterpolate = oldend->dontinterpolate;
246 	x = oldend->me.x; y = oldend->me.y;	/* Want it to compare exactly */
247     }
248     end->ttfindex = 0xfffe;
249     end->nextcpindex = 0xfffe;
250     start->nextcp.x = start->me.x;
251     start->nextcp.y = start->me.y;
252     end->me.x = end->prevcp.x = x;
253     end->me.y = end->prevcp.y = y;
254     end->nonextcp = end->noprevcp = start->nonextcp = true;
255     new->from = start;		start->next = new;
256     new->to = end;		end->prev = new;
257     new->splines[0].d = start->me.x;
258     new->splines[0].c = (x-start->me.x);
259     new->splines[1].d = start->me.y;
260     new->splines[1].c = (y-start->me.y);
261     new->order2 = true;
262     new->islinear = new->knownlinear = true;
263 return( end );
264 }
265 
_ttfapprox(Spline * ps,real tmin,real tmax,SplinePoint * start)266 static SplinePoint *_ttfapprox(Spline *ps,real tmin, real tmax, SplinePoint *start) {
267     int dim=0;
268     real dx, dy, ddim, dt, t, err;
269     real x,y, xmin, ymin;
270     real dxdtmin, dydtmin, dxdt, dydt;
271     SplinePoint *sp;
272     real cx, cy;
273     Spline ttf;
274     int cnt = -1, forceit;
275     BasePoint end, rend, dend;
276     DBounds bb;
277 
278     rend.x = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax + ps->splines[0].d;
279     rend.y = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax + ps->splines[1].d;
280     end.x = rint( rend.x );
281     end.y = rint( rend.y );
282     dend.x = (3*ps->splines[0].a*tmax+2*ps->splines[0].b)*tmax+ps->splines[0].c;
283     dend.y = (3*ps->splines[1].a*tmax+2*ps->splines[1].b)*tmax+ps->splines[1].c;
284     memset(&ttf,'\0',sizeof(ttf));
285 
286     bb.minx = bb.maxx = ps->from->me.x;
287     if ( ps->from->nextcp.x > bb.maxx ) bb.maxx = ps->from->nextcp.x;
288     else if ( ps->from->nextcp.x < bb.minx ) bb.minx = ps->from->nextcp.x;
289     if ( ps->to->prevcp.x > bb.maxx ) bb.maxx = ps->to->prevcp.x;
290     else if ( ps->to->prevcp.x < bb.minx ) bb.minx = ps->to->prevcp.x;
291     if ( ps->to->me.x > bb.maxx ) bb.maxx = ps->to->me.x;
292     else if ( ps->to->me.x < bb.minx ) bb.minx = ps->to->me.x;
293     bb.miny = bb.maxy = ps->from->me.y;
294     if ( ps->from->nextcp.y > bb.maxy ) bb.maxy = ps->from->nextcp.y;
295     else if ( ps->from->nextcp.y < bb.miny ) bb.miny = ps->from->nextcp.y;
296     if ( ps->to->prevcp.y > bb.maxy ) bb.maxy = ps->to->prevcp.y;
297     else if ( ps->to->prevcp.y < bb.miny ) bb.miny = ps->to->prevcp.y;
298     if ( ps->to->me.y > bb.maxy ) bb.maxy = ps->to->me.y;
299     else if ( ps->to->me.y < bb.miny ) bb.miny = ps->to->me.y;
300 
301   tail_recursion:
302     ++cnt;
303 
304     xmin = start->me.x;
305     ymin = start->me.y;
306     dxdtmin = (3*ps->splines[0].a*tmin+2*ps->splines[0].b)*tmin + ps->splines[0].c;
307     dydtmin = (3*ps->splines[1].a*tmin+2*ps->splines[1].b)*tmin + ps->splines[1].c;
308 
309     dx = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax -
310 	 ((ps->splines[0].a*tmin+ps->splines[0].b)*tmin+ps->splines[0].c)*tmin ;
311     dy = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax -
312 	 ((ps->splines[1].a*tmin+ps->splines[1].b)*tmin+ps->splines[1].c)*tmin ;
313     if ( dx<0 ) dx = -dx;
314     if ( dy<0 ) dy = -dy;
315     if ( dx>dy ) {
316 	dim = 0;
317 	ddim = dx;
318     } else {
319 	dim = 1;
320 	ddim = dy;
321     }
322     if (( err = ddim/3000 )<1 ) err = 1;
323 
324     if ( ddim<2 ||
325 	    (dend.x==0 && rint(start->me.x)==end.x && dy<=10 && cnt!=0) ||
326 	    (dend.y==0 && rint(start->me.y)==end.y && dx<=10 && cnt!=0) ) {
327 	if ( cnt==0 || start->noprevcp )
328 return( LinearSpline(ps,start,tmax));
329 	/* If the end point is very close to where we want to be, then just */
330 	/*  pretend it's right */
331 	start->prev->splines[0].b += ps->to->me.x-start->me.x;
332 	start->prev->splines[1].b += ps->to->me.y-start->me.y;
333 	start->prevcp.x += rend.x-start->me.x;
334 	start->prevcp.y += rend.y-start->me.y;
335 	if ( start->prev!=NULL && !start->prev->from->nonextcp )
336 	    start->prev->from->nextcp = start->prevcp;
337 	start->me = rend;
338 return( start );
339     }
340 
341     dt = (tmax-tmin)/ddim;
342     forceit = false;
343 /* force_end: */
344     for ( t=tmax; t>tmin+dt/128; t-= dt ) {		/* dt/128 is a hack to avoid rounding errors */
345 	x = ((ps->splines[0].a*t+ps->splines[0].b)*t+ps->splines[0].c)*t+ps->splines[0].d;
346 	y = ((ps->splines[1].a*t+ps->splines[1].b)*t+ps->splines[1].c)*t+ps->splines[1].d;
347 	dxdt = (3*ps->splines[0].a*t+2*ps->splines[0].b)*t + ps->splines[0].c;
348 	dydt = (3*ps->splines[1].a*t+2*ps->splines[1].b)*t + ps->splines[1].c;
349 	/* if the slopes are parallel at the ends there can be no bezier quadratic */
350 	/*  (control point is where the splines intersect. But if they are */
351 	/*  parallel and colinear then there is a line between 'em */
352 	if ( ( dxdtmin==0 && dxdt==0 ) || (dydtmin==0 && dydt==0) ||
353 		( dxdt!=0 && dxdtmin!=0 &&
354 		    RealNearish(dydt/dxdt,dydtmin/dxdtmin)) )
355     continue;
356 
357 	if ( dxdt==0 )
358 	    cx=x;
359 	else if ( dxdtmin==0 )
360 	    cx=xmin;
361 	else
362 	    cx = -(ymin-(dydtmin/dxdtmin)*xmin-y+(dydt/dxdt)*x)/(dydtmin/dxdtmin-dydt/dxdt);
363 	if ( dydt==0 )
364 	    cy=y;
365 	else if ( dydtmin==0 )
366 	    cy=ymin;
367 	else
368 	    cy = -(xmin-(dxdtmin/dydtmin)*ymin-x+(dxdt/dydt)*y)/(dxdtmin/dydtmin-dxdt/dydt);
369 	/* Make the quadratic spline from (xmin,ymin) through (cx,cy) to (x,y)*/
370 	if ( forceit || buildtestquads(&ttf,xmin,ymin,cx,cy,x,y,tmin,t,err,ps,&bb)) {
371 	    sp = MakeQuadSpline(start,&ttf,x,y,t,ps->to);
372 	    forceit = false;
373 	    if ( t==tmax )
374 return( sp );
375 	    tmin = t;
376 	    start = sp;
377   goto tail_recursion;
378 	}
379 	ttf.splines[0].d = xmin;
380 	ttf.splines[0].c = x-xmin;
381 	ttf.splines[0].b = 0;
382 	ttf.splines[1].d = ymin;
383 	ttf.splines[1].c = y-ymin;
384 	ttf.splines[1].b = 0;
385 	if ( comparespline(ps,&ttf,tmin,t,err) ) {
386 	    sp = LinearSpline(ps,start,t);
387 	    if ( t==tmax )
388 return( sp );
389 	    tmin = t;
390 	    start = sp;
391   goto tail_recursion;
392 	}
393     }
394     tmin += dt;
395     start = LinearSpline(ps,start,tmin);
396   goto tail_recursion;
397 }
398 
__ttfApprox(Spline * ps,real tmin,real tmax,SplinePoint * start)399 static SplinePoint *__ttfApprox(Spline *ps,real tmin, real tmax, SplinePoint *start) {
400     extended inflect[2];
401     int i=0;
402     SplinePoint *end;
403     Spline *s, *next;
404 
405     end = _ttfapprox(ps,tmin,tmax,start);
406     if ( ps->knownlinear )
407 return( end );
408     for ( s=start->next; s!=NULL && !s->islinear; s=s->to->next );
409     if ( s==NULL )
410 return( end );
411     for ( s=start->next; s!=NULL ; s=next ) {
412 	next = s->to->next;
413 	SplinePointFree(s->to);
414 	SplineFree(s);
415     }
416 /* Hmm. With my algorithem, checking for points of inflection actually makes */
417 /*  things worse. It uses more points and the splines don't join as nicely */
418 /* However if we get a bad match (a line) in the normal approx, then check */
419 /*  Err... I was computing POI incorrectly. Above statement might not be correct*/
420     /* no points of inflection in quad splines */
421 
422     i = Spline2DFindPointsOfInflection(ps, inflect);
423     if ( i==2 ) {
424 	if ( RealNearish(inflect[0],inflect[1]) )
425 	    --i;
426 	else if ( inflect[0]>inflect[1] ) {
427 	    real temp = inflect[0];
428 	    inflect[0] = inflect[1];
429 	    inflect[1] = temp;
430 	}
431     }
432     if ( i!=0 ) {
433 	start = _ttfapprox(ps,tmin,inflect[0],start);
434 	tmin = inflect[0];
435 	if ( i==2 ) {
436 	    start = _ttfapprox(ps,tmin,inflect[1],start);
437 	    tmin = inflect[1];
438 	}
439     }
440 return( _ttfapprox(ps,tmin,tmax,start));
441 }
442 
443 #if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION)
444 typedef struct qpoint {
445     BasePoint bp;
446     BasePoint cp;
447     bigreal t;
448 } QPoint;
449 
comparedata(Spline * ps,QPoint * data,int qfirst,int qlast,int round_to_int,int test_level)450 static int comparedata(Spline *ps,QPoint *data,int qfirst,int qlast,
451 	int round_to_int, int test_level ) {
452     Spline ttf;
453     int i;
454     bigreal err = round_to_int ? 1.5 : 1;
455 
456     if ( qfirst==qlast )		/* happened (was a bug) */
457 return( false );
458 
459     err *= (test_level+1);
460 
461     /* Control points diametrically opposed */
462     if ( (data[qlast-2].cp.x-ps->to->me.x)*(ps->to->prevcp.x-ps->to->me.x) +
463 	    (data[qlast-2].cp.y-ps->to->me.y)*(ps->to->prevcp.y-ps->to->me.y)<0 )
464 return( false );
465     if ( (data[qfirst-1].cp.x-ps->from->me.x)*(ps->from->nextcp.x-ps->from->me.x) +
466 	    (data[qfirst-1].cp.y-ps->from->me.y)*(ps->from->nextcp.y-ps->from->me.y)<0 )
467 return( false );
468 
469     memset(&ttf,0,sizeof(ttf));
470     for ( i=qfirst; i<qlast; ++i ) {
471 	ttf.splines[0].d = data[i-1].bp.x;
472 	ttf.splines[0].c = 2*(data[i-1].cp.x-data[i-1].bp.x);
473 	ttf.splines[0].b = data[i-1].bp.x+data[i].bp.x-2*data[i-1].cp.x;
474 	ttf.splines[1].d = data[i-1].bp.y;
475 	ttf.splines[1].c = 2*(data[i-1].cp.y-data[i-1].bp.y);
476 	ttf.splines[1].b = data[i-1].bp.y+data[i].bp.y-2*data[i-1].cp.y;
477 	if ( !comparespline(ps,&ttf,data[i-1].t,data[i].t,err) )
478 return( false );
479     }
480 return( true );
481 }
482 
CvtDataToSplines(QPoint * data,int qfirst,int qlast,SplinePoint * start)483 static SplinePoint *CvtDataToSplines(QPoint *data,int qfirst,int qlast,SplinePoint *start) {
484     SplinePoint *end;
485     int i;
486 
487     for ( i=qfirst; i<qlast; ++i ) {
488 	end = SplinePointCreate(data[i].bp.x,data[i].bp.y);
489 	start->nextcp = end->prevcp = data[i-1].cp;
490 	start->nonextcp = end->noprevcp = false;
491 	if (( data[i-1].cp.x == data[i].bp.x && data[i-1].cp.y == data[i].bp.y ) ||
492 		( data[i-1].cp.x == start->me.x && data[i-1].cp.y == start->me.y ))
493 	    start->nonextcp = end->noprevcp = true;
494 	SplineMake2(start,end);
495 	start = end;
496     }
497 return( start );
498 }
499 
SplineWithWellBehavedControlPoints(Spline * ps)500 static int SplineWithWellBehavedControlPoints(Spline *ps) {
501     BasePoint splineunit;
502     bigreal splinelen, npos, ppos;
503 
504     splineunit.x = ps->to->me.x - ps->from->me.x;
505     splineunit.y = ps->to->me.y - ps->from->me.y;
506     splinelen = sqrt(splineunit.x*splineunit.x + splineunit.y*splineunit.y);
507     if ( splinelen!=0 ) {
508 	splineunit.x /= splinelen;
509 	splineunit.y /= splinelen;
510     }
511 
512     npos = (ps->from->nextcp.x-ps->from->me.x) * splineunit.x +
513 	    (ps->from->nextcp.y-ps->from->me.y) * splineunit.y;
514     ppos = (ps->to->prevcp.x-ps->from->me.x) * splineunit.x +
515 	    (ps->to->prevcp.y-ps->from->me.y) * splineunit.y;
516 return( npos>=0 && /* npos<=ppos &&*/ ppos<=splinelen );
517 }
518 
PrettyApprox(Spline * ps,bigreal tmin,bigreal tmax,QPoint * data,int qcnt,int round_to_int,int test_level)519 static int PrettyApprox(Spline *ps,bigreal tmin, bigreal tmax,
520 	QPoint *data, int qcnt, int round_to_int, int test_level ) {
521     int ptcnt, q, i;
522     bigreal distance, dx, dy, tstart;
523     BasePoint end, mid, slopemin, slopemid, slopeend;
524     BasePoint splineunit, start;
525     bigreal splinelen, midpos, lastpos, lastpos2, cppos;
526     int do_good_spline_check;
527     QPoint data2[12];
528 
529     if ( qcnt==-1 )
530 return( -1 );
531 
532     slopemin.x = (3*ps->splines[0].a*tmin+2*ps->splines[0].b)*tmin+ps->splines[0].c;
533     slopemin.y = (3*ps->splines[1].a*tmin+2*ps->splines[1].b)*tmin+ps->splines[1].c;
534     if ( slopemin.x==0 && slopemin.y==0 ) {
535 	bigreal t = tmin + (tmax-tmin)/256;
536 	/* If there is no control point for this end point, then the slope is */
537 	/*  0/0 at the end point. Which isn't useful, it leads to a quadratic */
538 	/*  control point at the end point, but this one is real because it   */
539 	/*  is used to interpolate the next point, but we get all confused    */
540 	/*  because we don't expect a real cp to be on the base point.        */
541 	slopemin.x = (3*ps->splines[0].a*t+2*ps->splines[0].b)*t+ps->splines[0].c;
542 	slopemin.y = (3*ps->splines[1].a*t+2*ps->splines[1].b)*t+ps->splines[1].c;
543     }
544 
545     end.x = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax+ps->splines[0].d;
546     end.y = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax+ps->splines[1].d;
547     slopeend.x = (3*ps->splines[0].a*tmax+2*ps->splines[0].b)*tmax+ps->splines[0].c;
548     slopeend.y = (3*ps->splines[1].a*tmax+2*ps->splines[1].b)*tmax+ps->splines[1].c;
549     if ( slopemin.x==0 && slopemin.y==0 ) {
550 	bigreal t = tmax - (tmax-tmin)/256;
551 	/* Same problem as above, except at the other end */
552 	slopeend.x = (3*ps->splines[0].a*t+2*ps->splines[0].b)*t+ps->splines[0].c;
553 	slopeend.y = (3*ps->splines[1].a*t+2*ps->splines[1].b)*t+ps->splines[1].c;
554     }
555 
556     start.x = data[qcnt-1].bp.x;
557     start.y = data[qcnt-1].bp.y;
558     splineunit.x = end.x - start.x;
559     splineunit.y = end.y - start.y;
560     splinelen = sqrt(splineunit.x*splineunit.x + splineunit.y*splineunit.y);
561     if ( splinelen!=0 ) {
562 	splineunit.x /= splinelen;
563 	splineunit.y /= splinelen;
564     }
565     do_good_spline_check = SplineWithWellBehavedControlPoints(ps);
566 
567     if ( round_to_int && tmax!=1 ) {
568 	end.x = rint( end.x );
569 	end.y = rint( end.y );
570     }
571 
572     dx = end.x-data[qcnt-1].bp.x; dy = end.y-data[qcnt-1].bp.y;
573     distance = dx*dx + dy*dy;
574 
575     if ( distance<.3 ) {
576 	/* This is meaningless in truetype, use a line */
577 	data[qcnt-1].cp = data[qcnt-1].bp;
578 	data[qcnt].bp = end;
579 	data[qcnt].t = 1;
580 return( qcnt+1 );
581     }
582 
583     for ( ptcnt=0; ptcnt<10; ++ptcnt ) {
584 	if ( ptcnt>1 && distance/(ptcnt*ptcnt)<16 )
585 return( -1 );			/* Points too close for a good approx */
586 	q = qcnt;
587 	data2[ptcnt+1].bp = end;
588 	lastpos=0; lastpos2 = splinelen;
589 	for ( i=0; i<=ptcnt; ++i ) {
590 	    tstart = (tmin*(ptcnt-i) + tmax*(i+1))/(ptcnt+1);
591 	    mid.x = ((ps->splines[0].a*tstart+ps->splines[0].b)*tstart+ps->splines[0].c)*tstart+ps->splines[0].d;
592 	    mid.y = ((ps->splines[1].a*tstart+ps->splines[1].b)*tstart+ps->splines[1].c)*tstart+ps->splines[1].d;
593 	    if ( i==0 ) {
594 		slopemid.x = (3*ps->splines[0].a*tstart+2*ps->splines[0].b)*tstart+ps->splines[0].c;
595 		slopemid.y = (3*ps->splines[1].a*tstart+2*ps->splines[1].b)*tstart+ps->splines[1].c;
596 		if ( slopemid.x==0 )
597 		    data[q-1].cp.x=mid.x;
598 		else if ( slopemin.x==0 )
599 		    data[q-1].cp.x=data[q-1].bp.x;
600 		else if ( RealNear(slopemin.y/slopemin.x,slopemid.y/slopemid.x) )
601 	break;
602 		else
603 		    data[q-1].cp.x = -(data[q-1].bp.y-(slopemin.y/slopemin.x)*data[q-1].bp.x-mid.y+(slopemid.y/slopemid.x)*mid.x)/(slopemin.y/slopemin.x-slopemid.y/slopemid.x);
604 		if ( slopemid.y==0 )
605 		    data[q-1].cp.y=mid.y;
606 		else if ( slopemin.y==0 )
607 		    data[q-1].cp.y=data[q-1].bp.y;
608 		else if ( RealNear(slopemin.x/slopemin.y,slopemid.x/slopemid.y) )
609 	break;
610 		else
611 		    data[q-1].cp.y = -(data[q-1].bp.x-(slopemin.x/slopemin.y)*data[q-1].bp.y-mid.x+(slopemid.x/slopemid.y)*mid.y)/(slopemin.x/slopemin.y-slopemid.x/slopemid.y);
612 	    } else {
613 		data[q-1].cp.x = 2*data[q-1].bp.x - data[q-2].cp.x;
614 		data[q-1].cp.y = 2*data[q-1].bp.y - data[q-2].cp.y;
615 	    }
616 
617 	    midpos = (mid.x-start.x)*splineunit.x + (mid.y-start.y)*splineunit.y;
618 	    cppos  = (data[q-1].cp.x-start.x)*splineunit.x + (data[q-1].cp.y-start.y)*splineunit.y;
619 
620  	    if ( ((do_good_spline_check || i!=0 ) &&  cppos<lastpos) || cppos>midpos ) {
621 		i = 0;		/* Means we failed */
622 	break;
623 	    }
624 	    lastpos = midpos;
625 
626 	    data[q].bp = mid;
627 	    data[q++].t = tstart;
628 
629 	    tstart = (tmax*(ptcnt-i) + tmin*(i+1))/(ptcnt+1);
630 	    mid.x = ((ps->splines[0].a*tstart+ps->splines[0].b)*tstart+ps->splines[0].c)*tstart+ps->splines[0].d;
631 	    mid.y = ((ps->splines[1].a*tstart+ps->splines[1].b)*tstart+ps->splines[1].c)*tstart+ps->splines[1].d;
632 	    if ( i==0 ) {
633 		slopemid.x = (3*ps->splines[0].a*tstart+2*ps->splines[0].b)*tstart+ps->splines[0].c;
634 		slopemid.y = (3*ps->splines[1].a*tstart+2*ps->splines[1].b)*tstart+ps->splines[1].c;
635 		if ( slopemid.x==0 )
636 		    data2[ptcnt-i].cp.x=mid.x;
637 		else if ( slopeend.x==0 )
638 		    data2[ptcnt-i].cp.x=data2[ptcnt-i+1].bp.x;
639 		else if ( RealNear(slopeend.y/slopeend.x,slopemid.y/slopemid.x) )
640 	break;
641 		else
642 		    data2[ptcnt-i].cp.x = -(data2[ptcnt-i+1].bp.y-(slopeend.y/slopeend.x)*data2[ptcnt-i+1].bp.x-mid.y+(slopemid.y/slopemid.x)*mid.x)/(slopeend.y/slopeend.x-slopemid.y/slopemid.x);
643 		if ( slopemid.y==0 )
644 		    data2[ptcnt-i].cp.y=mid.y;
645 		else if ( slopeend.y==0 )
646 		    data2[ptcnt-i].cp.y=data2[ptcnt-i+1].bp.y;
647 		else if ( RealNear(slopeend.x/slopeend.y,slopemid.x/slopemid.y) )
648 	break;
649 		else
650 		    data2[ptcnt-i].cp.y = -(data2[ptcnt-i+1].bp.x-(slopeend.x/slopeend.y)*data2[ptcnt-i+1].bp.y-mid.x+(slopemid.x/slopemid.y)*mid.y)/(slopeend.x/slopeend.y-slopemid.x/slopemid.y);
651 	    } else {
652 		data2[ptcnt-i].cp.x = 2*data2[ptcnt-i+1].bp.x - data2[ptcnt-i+1].cp.x;
653 		data2[ptcnt-i].cp.y = 2*data2[ptcnt-i+1].bp.y - data2[ptcnt-i+1].cp.y;
654 	    }
655 	    data2[ptcnt-i].bp = mid;
656 
657 	    midpos = (mid.x-start.x)*splineunit.x + (mid.y-start.y)*splineunit.y;
658 	    cppos  = (data2[ptcnt-i].cp.x-start.x)*splineunit.x + (data2[ptcnt-i].cp.y-start.y)*splineunit.y;
659 	    if ( ((do_good_spline_check || i!=0 ) && cppos>lastpos2) || cppos<midpos ) {
660 		i = 0;		/* Means we failed */
661 	break;
662 	    }
663 	    lastpos2 = midpos;
664 
665 	}
666 	if ( i==0 )
667     continue;
668 	if ( (data2[ptcnt+1].bp.x-data2[ptcnt].bp.x)*(data2[ptcnt].cp.x-data2[ptcnt].bp.x)<0 ||
669 		(data2[ptcnt+1].bp.y-data2[ptcnt].bp.y)*(data2[ptcnt].cp.y-data2[ptcnt].bp.y)<0 ) {
670 	    /* data2 are bad ... don't use them */;
671 	} else if ( (data[qcnt-1].bp.x-data[qcnt].bp.x)*(data[qcnt-1].cp.x-data[qcnt].bp.x)<0 ||
672 		(data[qcnt-1].bp.y-data[qcnt].bp.y)*(data[qcnt-1].cp.y-data[qcnt].bp.y)<0 ) {
673 	    /* data are bad */;
674 	    for ( i=0; i<=ptcnt; ++i ) {
675 		data[qcnt+i-1].cp = data2[i].cp;
676 		data[qcnt+i-1].bp = data2[i].bp;
677 	    }
678 	} else {
679 	    for ( i=0; i<=ptcnt; ++i ) {
680 		if ( ptcnt!=0 ) {
681 		    data[qcnt+i-1].cp.x = (data[qcnt+i-1].cp.x*(ptcnt-i) + data2[i].cp.x*i)/ptcnt;
682 		    data[qcnt+i-1].cp.y = (data[qcnt+i-1].cp.y*(ptcnt-i) + data2[i].cp.y*i)/ptcnt;
683 		}
684 	    }
685 	}
686 	if ( round_to_int ) {
687 	    for ( i=0; i<=ptcnt; ++i ) {
688 		data[qcnt+i-1].cp.x = rint( data[qcnt+i-1].cp.x );
689 		data[qcnt+i-1].cp.y = rint( data[qcnt+i-1].cp.y );
690 	    }
691 	}
692 	for ( i=0; i<ptcnt; ++i ) {
693 	    data[qcnt+i].bp.x = (data[qcnt+i].cp.x + data[qcnt+i-1].cp.x)/2;
694 	    data[qcnt+i].bp.y = (data[qcnt+i].cp.y + data[qcnt+i-1].cp.y)/2;
695 	}
696 	if ( comparedata(ps,data,qcnt,q,round_to_int,test_level))
697 return( q );
698     }
699 return( -1 );
700 }
701 #endif
702 
AlreadyQuadraticCheck(Spline * ps,SplinePoint * start)703 static SplinePoint *AlreadyQuadraticCheck(Spline *ps, SplinePoint *start) {
704     SplinePoint *sp;
705 
706     if ( (RealNearish(ps->splines[0].a,0) && RealNearish(ps->splines[1].a,0)) ||
707 	    ((ps->splines[0].b!=0 && RealNearish(ps->splines[0].a/ps->splines[0].b,0)) &&
708 	     (ps->splines[1].b!=0 && RealNearish(ps->splines[1].a/ps->splines[1].b,0))) ) {
709 	/* Already Quadratic, just need to find the control point */
710 	/* Or linear, in which case we don't need to do much of anything */
711 	Spline *spline;
712 	sp = chunkalloc(sizeof(SplinePoint));
713 	sp->me.x = ps->to->me.x; sp->me.y = ps->to->me.y;
714 	sp->roundx = ps->to->roundx; sp->roundy = ps->to->roundy; sp->dontinterpolate = ps->to->dontinterpolate;
715 	sp->ttfindex = 0xfffe;
716 	sp->nextcpindex = 0xfffe;
717 	sp->nonextcp = true;
718 	spline = chunkalloc(sizeof(Spline));
719 	spline->order2 = true;
720 	spline->from = start;
721 	spline->to = sp;
722 	spline->splines[0] = ps->splines[0]; spline->splines[1] = ps->splines[1];
723 	start->next = sp->prev = spline;
724 	if ( ps->knownlinear ) {
725 	    spline->islinear = spline->knownlinear = true;
726 	    start->nonextcp = sp->noprevcp = true;
727 	    start->nextcp = start->me;
728 	    sp->prevcp = sp->me;
729 	} else {
730 	    start->nonextcp = sp->noprevcp = false;
731 	    start->nextcp.x = sp->prevcp.x = (ps->splines[0].c+2*ps->splines[0].d)/2;
732 	    start->nextcp.y = sp->prevcp.y = (ps->splines[1].c+2*ps->splines[1].d)/2;
733 	}
734 return( sp );
735     }
736 return( NULL );
737 }
738 
ttfApprox(Spline * ps,SplinePoint * start)739 static SplinePoint *ttfApprox(Spline *ps, SplinePoint *start) {
740 #if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION)
741     extended magicpoints[6], last;
742     int cnt, i, j, qcnt, test_level;
743     QPoint data[8*10];
744     int round_to_int =
745     /* The end points are at integer points, or one coord is at half while */
746     /*  the other is at an integer (ie. condition for ttf interpolated point)*/
747 	    ((ps->from->me.x==rint(ps->from->me.x) &&
748 	      ps->from->me.y==rint(ps->from->me.y)) ||
749 	     (ps->from->me.x==rint(ps->from->me.x) &&
750 	      ps->from->me.x==ps->from->nextcp.x &&
751 	      ps->from->me.y!=ps->from->nextcp.y &&
752 	      2*ps->from->me.y==rint(2*ps->from->me.y)) ||
753 	     (ps->from->me.y==rint(ps->from->me.y) &&
754 	      ps->from->me.y==ps->from->nextcp.y &&
755 	      ps->from->me.x!=ps->from->nextcp.x &&
756 	      2*ps->from->me.x==rint(2*ps->from->me.x)) ) &&
757 	    ((ps->to->me.x == rint(ps->to->me.x) &&
758 	      ps->to->me.y == rint(ps->to->me.y)) ||
759 	     (ps->to->me.x==rint(ps->to->me.x) &&
760 	      ps->to->me.x==ps->to->prevcp.x &&
761 	      ps->to->me.y!=ps->to->prevcp.y &&
762 	      2*ps->to->me.y==rint(2*ps->to->me.y)) ||
763 	     (ps->to->me.y==rint(ps->to->me.y) &&
764 	      ps->to->me.y==ps->to->prevcp.y &&
765 	      ps->to->me.x!=ps->to->prevcp.x &&
766 	      2*ps->to->me.x==rint(2*ps->to->me.x)) );
767 #endif
768     SplinePoint *ret;
769 /* Divide the spline up at extrema and points of inflection. The first	*/
770 /*  because ttf splines should have points at their extrema, the second */
771 /*  because quadratic splines can't have points of inflection.		*/
772 /* Let's not do the first (extrema) AddExtrema does this better and we  */
773 /*  don't want unneeded extrema.					*/
774 /* And sometimes we don't want to look at the points of inflection either*/
775 
776     if (( ret = AlreadyQuadraticCheck(ps,start))!=NULL )
777 return( ret );
778 
779 #if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION)
780     qcnt = 1;
781     data[0].bp = ps->from->me;
782     data[0].t = 0;
783     qcnt = PrettyApprox(ps,0,1,data,qcnt,round_to_int,0);
784     if ( qcnt!=-1 )
785 return( CvtDataToSplines(data,1,qcnt,start));
786 
787     cnt = 0;
788     /* cnt = Spline2DFindExtrema(ps,magicpoints);*/
789 
790     cnt += Spline2DFindPointsOfInflection(ps,magicpoints+cnt);
791 
792     /* remove points outside range */
793     for ( i=0; i<cnt; ++i ) {
794 	if ( magicpoints[i]<=0 || magicpoints[i]>=1 ) {
795 	    for ( j=i+1; j<cnt; ++j )
796 		magicpoints[j-1] = magicpoints[j];
797 	    --cnt;
798 	    --i;
799 	}
800     }
801     /* sort points */
802     for ( i=0; i<cnt; ++i ) for ( j=i+1; j<cnt; ++j ) {
803 	if ( magicpoints[i]>magicpoints[j] ) {
804 	    bigreal temp = magicpoints[i];
805 	    magicpoints[i] = magicpoints[j];
806 	    magicpoints[j] = temp;
807 	}
808     }
809     /* Remove duplicates */
810     for ( i=1; i<cnt; ++i ) {
811 	while ( i<cnt && RealNear(magicpoints[i-1],magicpoints[i])) {
812 	    --cnt;
813 	    for ( j=i ; j<cnt; ++j )
814 		magicpoints[j] = magicpoints[j+1];
815 	    magicpoints[cnt] = -1;
816 	}
817     }
818 
819     for ( test_level=0; test_level<3; ++test_level ) {
820 	qcnt = 1;
821 	last = 0;
822 	for ( i=0; i<cnt; ++i ) {
823 	    qcnt = PrettyApprox(ps,last,magicpoints[i],data,qcnt,round_to_int,test_level);
824 	    last = magicpoints[i];
825 	}
826 	qcnt = PrettyApprox(ps,last,1,data,qcnt,round_to_int,test_level);
827 	if ( qcnt!=-1 )
828     return( CvtDataToSplines(data,1,qcnt,start));
829     }
830 #endif
831 
832 return( __ttfApprox(ps,0,1,start));
833 }
834 
ttfCleanup(SplinePoint * from)835 static void ttfCleanup(SplinePoint *from) {
836     SplinePoint *test, *next;
837 
838     for ( test = from; test->next!=NULL; test = next ) {
839 	next = test->next->to;
840 	/* Too close together to be meaningful when output as ttf */
841 	if ( rint(test->me.x) == rint(next->me.x) &&
842 		rint(test->me.y) == rint(next->me.y) ) {
843 	    if ( next->next==NULL || next==from ) {
844 		if ( test==from )
845     break;
846 		next->prevcp = test->prevcp;
847 		next->noprevcp = test->noprevcp;
848 		next->prev = test->prev;
849 		next->prev->to = next;
850 		SplineFree(test->next);
851 		SplinePointFree(test);
852 	    } else {
853 		test->nextcp = next->nextcp;
854 		test->nonextcp = next->nonextcp;
855 		test->next = next->next;
856 		test->next->from = test;
857 		SplineFree(next->prev);
858 		SplinePointFree(next);
859 		next = test->next->to;
860 	    }
861 	}
862 	if ( next==from )
863     break;
864     }
865 }
866 
SplineTtfApprox(Spline * ps)867 SplinePoint *SplineTtfApprox(Spline *ps) {
868     SplinePoint *from;
869     from = chunkalloc(sizeof(SplinePoint));
870     *from = *ps->from;
871     from->hintmask = NULL;
872     ttfApprox(ps,from);
873 return( from );
874 }
875 
SSttfApprox(SplineSet * ss)876 SplineSet *SSttfApprox(SplineSet *ss) {
877     SplineSet *ret = chunkalloc(sizeof(SplineSet));
878     Spline *spline, *first;
879 
880     ret->first = chunkalloc(sizeof(SplinePoint));
881     *ret->first = *ss->first;
882     if ( ret->first->hintmask != NULL ) {
883 	ret->first->hintmask = chunkalloc(sizeof(HintMask));
884 	memcpy(ret->first->hintmask,ss->first->hintmask,sizeof(HintMask));
885     }
886     ret->last = ret->first;
887 
888     first = NULL;
889     for ( spline=ss->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
890 	ret->last = ttfApprox(spline,ret->last);
891 	ret->last->ptindex = spline->to->ptindex;
892 	ret->last->ttfindex = spline->to->ttfindex;
893 	ret->last->nextcpindex = spline->to->nextcpindex;
894 	if ( spline->to->hintmask != NULL ) {
895 	    ret->last->hintmask = chunkalloc(sizeof(HintMask));
896 	    memcpy(ret->last->hintmask,spline->to->hintmask,sizeof(HintMask));
897 	}
898 	if ( first==NULL ) first = spline;
899     }
900     if ( ss->first==ss->last ) {
901 	if ( ret->last!=ret->first ) {
902 	    ret->first->prevcp = ret->last->prevcp;
903 	    ret->first->noprevcp = ret->last->noprevcp;
904 	    ret->first->prev = ret->last->prev;
905 	    ret->last->prev->to = ret->first;
906 	    SplinePointFree(ret->last);
907 	    ret->last = ret->first;
908 	}
909     }
910     ttfCleanup(ret->first);
911     SPLCategorizePoints(ret);
912 return( ret );
913 }
914 
SplineSetsTTFApprox(SplineSet * ss)915 SplineSet *SplineSetsTTFApprox(SplineSet *ss) {
916     SplineSet *head=NULL, *last, *cur;
917 
918     while ( ss!=NULL ) {
919 	cur = SSttfApprox(ss);
920 	if ( head==NULL )
921 	    head = cur;
922 	else
923 	    last->next = cur;
924 	last = cur;
925 	ss = ss->next;
926     }
927 return( head );
928 }
929 
ImproveB3CPForQuadratic(real from,real * _ncp,real * _pcp,real to)930 static void ImproveB3CPForQuadratic(real from,real *_ncp,real *_pcp,real to) {
931     real ncp = *_ncp, pcp = *_pcp;
932     real noff, poff;
933     real c,b, best;
934     int err, i, besti;
935     real offs[9];
936 
937     if ( (noff=ncp/32768.0)<0 ) noff = -noff;
938     if ( (poff=pcp/32768.0)<0 ) poff = -poff;
939     if ( noff<1.0/32768.0 ) noff = 1.0/32768.0;
940     if ( poff<1.0/32768.0 ) poff = 1.0/32768.0;
941 
942     c = 3*(ncp-from); b = 3*(pcp-ncp)-c; best = to-from-c-b;
943     offs[4] = best;
944     if ( best==0 )
945 return;
946 
947     for ( err=0; err<10; ++err, noff/=2.0, poff/=2.0 ) {
948 	c = 3*(ncp-noff-from); b = 3*(pcp-poff-(ncp-noff))-c; offs[0] = to-from-c-b;
949 	c = 3*(ncp-noff-from); b = 3*(pcp     -(ncp-noff))-c; offs[1] = to-from-c-b;
950 	c = 3*(ncp-noff-from); b = 3*(pcp+poff-(ncp-noff))-c; offs[2] = to-from-c-b;
951 	c = 3*(ncp     -from); b = 3*(pcp-poff-(ncp     ))-c; offs[3] = to-from-c-b;
952 	c = 3*(ncp     -from); b = 3*(pcp+poff-(ncp     ))-c; offs[5] = to-from-c-b;
953 	c = 3*(ncp+noff-from); b = 3*(pcp-poff-(ncp+noff))-c; offs[6] = to-from-c-b;
954 	c = 3*(ncp+noff-from); b = 3*(pcp     -(ncp+noff))-c; offs[7] = to-from-c-b;
955 	c = 3*(ncp+noff-from); b = 3*(pcp+poff-(ncp+noff))-c; offs[8] = to-from-c-b;
956 	besti=4;
957 	for ( i=0; i<9; ++i ) {
958 	    if ( offs[i]<0 ) offs[i]= - offs[i];
959 	    if ( offs[i]<best ) {
960 		besti = i;
961 		best = offs[i];
962 	    }
963 	}
964 	if ( besti!=4 ) {
965 	    if ( besti<3 ) ncp -= noff;
966 	    else if ( besti>=6 ) ncp += noff;
967 	    if ( besti%3==0 ) pcp -= poff;
968 	    else if ( besti%3==2 ) pcp += poff;
969 	    offs[4] = best;
970 	    if ( best==0 )
971     break;
972 	}
973     }
974     *_ncp = ncp;
975     *_pcp = pcp;
976 }
977 
SSPSApprox(SplineSet * ss)978 SplineSet *SSPSApprox(SplineSet *ss) {
979     SplineSet *ret = chunkalloc(sizeof(SplineSet));
980     Spline *spline, *first;
981     SplinePoint *to;
982 
983     ret->first = chunkalloc(sizeof(SplinePoint));
984     *ret->first = *ss->first;
985     if ( ret->first->hintmask != NULL ) {
986 	ret->first->hintmask = chunkalloc(sizeof(HintMask));
987 	memcpy(ret->first->hintmask,ss->first->hintmask,sizeof(HintMask));
988     }
989     ret->last = ret->first;
990 
991     first = NULL;
992     for ( spline=ss->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
993 	to = chunkalloc(sizeof(SplinePoint));
994 	*to = *spline->to;
995 	if ( to->hintmask != NULL ) {
996 	    to->hintmask = chunkalloc(sizeof(HintMask));
997 	    memcpy(to->hintmask,spline->to->hintmask,sizeof(HintMask));
998 	}
999 	if ( !spline->knownlinear ) {
1000 	    ret->last->nextcp.x = ret->last->me.x + 2*(ret->last->nextcp.x-ret->last->me.x)/3;
1001 	    ret->last->nextcp.y = ret->last->me.y + 2*(ret->last->nextcp.y-ret->last->me.y)/3;
1002 	    to->prevcp.x = to->me.x + 2*(to->prevcp.x-to->me.x)/3;
1003 	    to->prevcp.y = to->me.y + 2*(to->prevcp.y-to->me.y)/3;
1004 	    ImproveB3CPForQuadratic(ret->last->me.x,&ret->last->nextcp.x,&to->prevcp.x,to->me.x);
1005 	    ImproveB3CPForQuadratic(ret->last->me.y,&ret->last->nextcp.y,&to->prevcp.y,to->me.y);
1006 	}
1007 	SplineMake3(ret->last,to);
1008 	ret->last = to;
1009 	if ( first==NULL ) first = spline;
1010     }
1011     if ( ss->first==ss->last ) {
1012 	if ( ret->last!=ret->first ) {
1013 	    ret->first->prevcp = ret->last->prevcp;
1014 	    ret->first->noprevcp = ret->last->noprevcp;
1015 	    ret->first->prev = ret->last->prev;
1016 	    ret->last->prev->to = ret->first;
1017 	    SplinePointFree(ret->last);
1018 	    ret->last = ret->first;
1019 	}
1020     }
1021     ret->is_clip_path = ss->is_clip_path;
1022 return( ret );
1023 }
1024 
SplineSetsPSApprox(SplineSet * ss)1025 SplineSet *SplineSetsPSApprox(SplineSet *ss) {
1026     SplineSet *head=NULL, *last, *cur;
1027 
1028     while ( ss!=NULL ) {
1029 	cur = SSPSApprox(ss);
1030 	if ( head==NULL )
1031 	    head = cur;
1032 	else
1033 	    last->next = cur;
1034 	last = cur;
1035 	ss = ss->next;
1036     }
1037 return( head );
1038 }
1039 
SplineSetsConvertOrder(SplineSet * ss,int to_order2)1040 SplineSet *SplineSetsConvertOrder(SplineSet *ss, int to_order2) {
1041     SplineSet *new;
1042 
1043     if ( to_order2 )
1044 	new = SplineSetsTTFApprox(ss);
1045     else
1046 	new = SplineSetsPSApprox(ss);
1047     SplinePointListsFree(ss);
1048 return( new );
1049 }
1050 
SCConvertLayerToOrder2(SplineChar * sc,int layer)1051 void SCConvertLayerToOrder2(SplineChar *sc,int layer) {
1052     SplineSet *new;
1053 
1054     if ( sc==NULL )
1055 return;
1056 
1057     new = SplineSetsTTFApprox(sc->layers[layer].splines);
1058     SplinePointListsFree(sc->layers[layer].splines);
1059     sc->layers[layer].splines = new;
1060 
1061     UndoesFree(sc->layers[layer].undoes);
1062     UndoesFree(sc->layers[layer].redoes);
1063     sc->layers[layer].undoes = NULL;
1064     sc->layers[layer].redoes = NULL;
1065     sc->layers[layer].order2 = true;
1066 
1067     MinimumDistancesFree(sc->md); sc->md = NULL;
1068 }
1069 
SCConvertToOrder2(SplineChar * sc)1070 void SCConvertToOrder2(SplineChar *sc) {
1071     int layer;
1072 
1073     if ( sc==NULL )
1074 return;
1075 
1076     for ( layer=ly_back; layer<sc->layer_cnt; ++layer )
1077 	SCConvertLayerToOrder2(sc,layer);
1078 }
1079 
SCConvertRefs(SplineChar * sc,int layer)1080 static void SCConvertRefs(SplineChar *sc,int layer) {
1081     RefChar *rf;
1082 
1083     sc->ticked = true;
1084     for ( rf=sc->layers[layer].refs; rf!=NULL; rf=rf->next ) {
1085 	if ( !rf->sc->ticked )
1086 	    SCConvertRefs(rf->sc,layer);
1087 	SCReinstanciateRefChar(sc,rf,layer);	/* Conversion is done by reinstanciating */
1088 		/* Since the base thing will have been converted, all we do is copy its data */
1089     }
1090 }
1091 
SFConvertLayerToOrder2(SplineFont * _sf,int layer)1092 void SFConvertLayerToOrder2(SplineFont *_sf,int layer) {
1093     int i, k;
1094     SplineFont *sf;
1095 
1096     if ( _sf->cidmaster!=NULL ) _sf=_sf->cidmaster;
1097     k = 0;
1098     do {
1099 	sf = _sf->subfonts==NULL ? _sf : _sf->subfonts[k];
1100 	for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL ) {
1101 	    SCConvertLayerToOrder2(sf->glyphs[i],layer);
1102 	    sf->glyphs[i]->ticked = false;
1103 	    sf->glyphs[i]->changedsincelasthinted = false;
1104 	}
1105 	for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL && !sf->glyphs[i]->ticked )
1106 	    SCConvertRefs(sf->glyphs[i],layer);
1107 
1108 	if ( layer!=ly_back )
1109 	    for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL )
1110 		SCNumberPoints(sf->glyphs[i],layer);
1111 	++k;
1112     } while ( k<_sf->subfontcnt );
1113     _sf->layers[layer].order2 = true;
1114 }
1115 
SFConvertGridToOrder2(SplineFont * _sf)1116 void SFConvertGridToOrder2(SplineFont *_sf) {
1117     int k;
1118     SplineSet *new;
1119     SplineFont *sf;
1120 
1121     if ( _sf->cidmaster!=NULL ) _sf=_sf->cidmaster;
1122     k = 0;
1123     do {
1124 	sf = _sf->subfonts==NULL ? _sf : _sf->subfonts[k];
1125 
1126 	new = SplineSetsTTFApprox(sf->grid.splines);
1127 	SplinePointListsFree(sf->grid.splines);
1128 	sf->grid.splines = new;
1129 
1130 	UndoesFree(sf->grid.undoes); UndoesFree(sf->grid.redoes);
1131 	sf->grid.undoes = sf->grid.redoes = NULL;
1132 	sf->grid.order2 = true;
1133 	++k;
1134     } while ( k<_sf->subfontcnt );
1135     _sf->grid.order2 = true;
1136 }
1137 
SFConvertToOrder2(SplineFont * _sf)1138 void SFConvertToOrder2(SplineFont *_sf) {
1139     int layer;
1140 
1141     for ( layer=0; layer<_sf->layer_cnt; ++layer )
1142 	SFConvertLayerToOrder2(_sf,layer);
1143     SFConvertGridToOrder2(_sf);
1144 }
1145 
SCConvertLayerToOrder3(SplineChar * sc,int layer)1146 void SCConvertLayerToOrder3(SplineChar *sc,int layer) {
1147     SplineSet *new;
1148     RefChar *ref;
1149     AnchorPoint *ap;
1150     int has_order2_layer_still, i;
1151 
1152     new = SplineSetsPSApprox(sc->layers[layer].splines);
1153     SplinePointListsFree(sc->layers[layer].splines);
1154     sc->layers[layer].splines = new;
1155 
1156     UndoesFree(sc->layers[layer].undoes);
1157     UndoesFree(sc->layers[layer].redoes);
1158     sc->layers[layer].undoes = NULL;
1159     sc->layers[layer].redoes = NULL;
1160     sc->layers[layer].order2 = false;
1161 
1162     MinimumDistancesFree(sc->md); sc->md = NULL;
1163 
1164     /* OpenType/PostScript fonts don't support point matching to position */
1165     /*  references or anchors */
1166     for ( ref = sc->layers[layer].refs; ref!=NULL; ref=ref->next )
1167 	ref->point_match = false;
1168     has_order2_layer_still = false;
1169     for ( i=ly_fore; i<sc->layer_cnt; ++i )
1170 	if ( sc->layers[i].order2 ) {
1171 	    has_order2_layer_still = true;
1172     break;
1173 	}
1174     if ( !has_order2_layer_still ) {
1175 	for ( ap = sc->anchor; ap!=NULL; ap=ap->next )
1176 	    ap->has_ttf_pt = false;
1177 
1178 	free(sc->ttf_instrs);
1179 	sc->ttf_instrs = NULL; sc->ttf_instrs_len = 0;
1180 	/* If this character has any cv's showing instructions then remove the instruction pane!!!!! */
1181     }
1182 }
1183 
SCConvertToOrder3(SplineChar * sc)1184 void SCConvertToOrder3(SplineChar *sc) {
1185     int layer;
1186 
1187     for ( layer=0; layer<sc->layer_cnt; ++layer )
1188 	SCConvertLayerToOrder3(sc,layer);
1189 }
1190 
SCConvertOrder(SplineChar * sc,int to_order2)1191 void SCConvertOrder(SplineChar *sc, int to_order2) {
1192     if ( to_order2 )
1193 	SCConvertToOrder2(sc);
1194     else
1195 	SCConvertToOrder3(sc);
1196 }
1197 
SFConvertLayerToOrder3(SplineFont * _sf,int layer)1198 void SFConvertLayerToOrder3(SplineFont *_sf,int layer) {
1199     int i, k;
1200     SplineFont *sf;
1201 
1202     if ( _sf->cidmaster!=NULL ) _sf=_sf->cidmaster;
1203     k = 0;
1204     do {
1205 	sf = _sf->subfonts==NULL ? _sf : _sf->subfonts[k];
1206 	for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL ) {
1207 	    SCConvertLayerToOrder3(sf->glyphs[i],layer);
1208 	    sf->glyphs[i]->ticked = false;
1209 	    sf->glyphs[i]->changedsincelasthinted = true;
1210 	}
1211 	for ( i=0; i<sf->glyphcnt; ++i ) if ( sf->glyphs[i]!=NULL && !sf->glyphs[i]->ticked )
1212 	    SCConvertRefs(sf->glyphs[i],layer);
1213 
1214 	sf->layers[layer].order2 = false;
1215 	++k;
1216     } while ( k<_sf->subfontcnt );
1217     _sf->layers[layer].order2 = false;
1218 }
1219 
SFConvertGridToOrder3(SplineFont * _sf)1220 void SFConvertGridToOrder3(SplineFont *_sf) {
1221     int k;
1222     SplineSet *new;
1223     SplineFont *sf;
1224 
1225     if ( _sf->cidmaster!=NULL ) _sf=_sf->cidmaster;
1226     k = 0;
1227     do {
1228 	sf = _sf->subfonts==NULL ? _sf : _sf->subfonts[k];
1229 
1230 	new = SplineSetsPSApprox(sf->grid.splines);
1231 	SplinePointListsFree(sf->grid.splines);
1232 	sf->grid.splines = new;
1233 
1234 	UndoesFree(sf->grid.undoes); UndoesFree(sf->grid.redoes);
1235 	sf->grid.undoes = sf->grid.redoes = NULL;
1236 	sf->grid.order2 = false;
1237 	++k;
1238     } while ( k<_sf->subfontcnt );
1239     _sf->grid.order2 = false;
1240 }
1241 
SFConvertToOrder3(SplineFont * _sf)1242 void SFConvertToOrder3(SplineFont *_sf) {
1243     int layer;
1244 
1245     for ( layer=0; layer<_sf->layer_cnt; ++layer )
1246 	SFConvertLayerToOrder3(_sf,layer);
1247     SFConvertGridToOrder3(_sf);
1248 }
1249 
1250 /* ************************************************************************** */
1251 
SplineRefigure2(Spline * spline)1252 void SplineRefigure2(Spline *spline) {
1253     SplinePoint *from = spline->from, *to = spline->to;
1254     Spline1D *xsp = &spline->splines[0], *ysp = &spline->splines[1];
1255     Spline old;
1256 
1257 #ifdef DEBUG
1258     if ( RealNear(from->me.x,to->me.x) && RealNear(from->me.y,to->me.y))
1259 	IError("Zero length spline created");
1260 #endif
1261     if ( spline->acceptableextrema )
1262 	old = *spline;
1263 
1264     if ( from->nonextcp || to->noprevcp ||
1265 	    ( from->nextcp.x==from->me.x && from->nextcp.y == from->me.y && from->nextcpindex>=0xfffe ) ||
1266 	    ( to->prevcp.x==to->me.x && to->prevcp.y == to->me.y && from->nextcpindex>=0xfffe )) {
1267 	from->nonextcp = to->noprevcp = true;
1268 	from->nextcp = from->me;
1269 	to->prevcp = to->me;
1270     }
1271 
1272     if ( from->nonextcp && to->noprevcp )
1273 	/* Ok */;
1274     else if ( from->nonextcp || to->noprevcp || from->nextcp.x!=to->prevcp.x ||
1275 	    from->nextcp.y!=to->prevcp.y ) {
1276 	if ( RealNear(from->nextcp.x,to->prevcp.x) &&
1277 		RealNear(from->nextcp.y,to->prevcp.y)) {
1278 	    from->nextcp.x = to->prevcp.x = (from->nextcp.x+to->prevcp.x)/2;
1279 	    from->nextcp.y = to->prevcp.y = (from->nextcp.y+to->prevcp.y)/2;
1280 	} else {
1281 	    IError("Invalid 2nd order spline in SplineRefigure2" );
1282 #ifndef GWW_TEST
1283 	    /* I don't want these to go away when I'm debugging. I want to */
1284 	    /*  know how I got them */
1285 	    from->nextcp.x = to->prevcp.x = (from->nextcp.x+to->prevcp.x)/2;
1286 	    from->nextcp.y = to->prevcp.y = (from->nextcp.y+to->prevcp.y)/2;
1287 #endif
1288 	}
1289     }
1290 
1291     xsp->d = from->me.x; ysp->d = from->me.y;
1292     if ( from->nonextcp && to->noprevcp ) {
1293 	spline->islinear = true;
1294 	xsp->c = to->me.x-from->me.x;
1295 	ysp->c = to->me.y-from->me.y;
1296 	xsp->a = xsp->b = 0;
1297 	ysp->a = ysp->b = 0;
1298     } else {
1299 	/* from p. 393 (Operator Details, curveto) PostScript Lang. Ref. Man. (Red book) */
1300 	xsp->c = 2*(from->nextcp.x-from->me.x);
1301 	ysp->c = 2*(from->nextcp.y-from->me.y);
1302 	xsp->b = to->me.x-from->me.x-xsp->c;
1303 	ysp->b = to->me.y-from->me.y-ysp->c;
1304 	xsp->a = 0;
1305 	ysp->a = 0;
1306 	if ( RealNear(xsp->c,0)) xsp->c=0;
1307 	if ( RealNear(ysp->c,0)) ysp->c=0;
1308 	if ( RealNear(xsp->b,0)) xsp->b=0;
1309 	if ( RealNear(ysp->b,0)) ysp->b=0;
1310 	spline->islinear = false;
1311 	if ( ysp->b==0 && xsp->b==0 )
1312 	    spline->islinear = true;	/* This seems extremely unlikely... */
1313 	if ( from->nextcpselected || to->prevcpselected ) {
1314             // The convention for tracking selection of quadratic control
1315 	    // points is to use nextcpselected except at the tail of the
1316 	    // list, where it's prevcpselected on the first point.
1317 	    from->nextcpselected = true;
1318 	    to->prevcpselected = false;
1319 	}
1320     }
1321     if ( isnan(ysp->b) || isnan(xsp->b) )
1322 	IError("NaN value in spline creation");
1323     LinearApproxFree(spline->approx);
1324     spline->approx = NULL;
1325     spline->knowncurved = false;
1326     spline->knownlinear = spline->islinear;
1327     SplineIsLinear(spline);
1328     spline->isquadratic = !spline->knownlinear;
1329     spline->order2 = true;
1330 
1331     if ( spline->acceptableextrema ) {
1332 	/* I don't check "d", because changes to that reflect simple */
1333 	/*  translations which will not affect the shape of the spline */
1334 	/* (I don't check "a" because it is always 0 in a quadratic spline) */
1335 	if ( !RealNear(old.splines[0].b,spline->splines[0].b) ||
1336 		!RealNear(old.splines[0].c,spline->splines[0].c) ||
1337 		!RealNear(old.splines[1].b,spline->splines[1].b) ||
1338 		!RealNear(old.splines[1].c,spline->splines[1].c) )
1339 	    spline->acceptableextrema = false;
1340     }
1341 }
1342 
SplineRefigure(Spline * spline)1343 void SplineRefigure(Spline *spline) {
1344     if ( spline==NULL )
1345 return;
1346     if ( spline->order2 )
1347 	SplineRefigure2(spline);
1348     else
1349 	SplineRefigure3(spline);
1350 }
1351 
IsHV(Spline * spline,int isfrom)1352 static int IsHV(Spline *spline, int isfrom) {
1353     SplinePoint *sp;
1354 
1355     if ( spline==NULL )
1356 return( false );
1357 
1358     if ( !isfrom ) {
1359 	sp = spline->to;
1360 	if ( sp->noprevcp )
1361 return( false );
1362 	if ( sp->me.x == sp->prevcp.x )
1363 return( 2 );	/* Vertical */
1364 	else if ( sp->me.y == sp->prevcp.y )
1365 return( 1 );	/* Horizontal */
1366 	else
1367 return( 0 );	/* Neither */
1368     } else {
1369 	sp = spline->from;
1370 	if ( sp->nonextcp )
1371 return( false );
1372 	if ( sp->me.x == sp->nextcp.x )
1373 return( 2 );	/* Vertical */
1374 	else if ( sp->me.y == sp->nextcp.y )
1375 return( 1 );	/* Horizontal */
1376 	else
1377 return( 0 );	/* Neither */
1378     }
1379 }
1380 
SplineRefigureFixup(Spline * spline)1381 void SplineRefigureFixup(Spline *spline) {
1382     SplinePoint *from, *to, *prev, *next;
1383     BasePoint foff, toff, unit, new;
1384     bigreal len;
1385     enum pointtype fpt, tpt;
1386     int done = false;
1387     extern int snaptoint;
1388 
1389     if ( !spline->order2 ) {
1390 	SplineRefigure3(spline);
1391 return;
1392     }
1393     from = spline->from; to = spline->to;
1394     if ( from->pointtype==pt_hvcurve && to->pointtype==pt_hvcurve ) {
1395 	done = true;
1396 	if ( !IsHV(from->prev,0) && !IsHV(to->next,1) ) {
1397 	    if ( to->me.x == from->me.x ) {
1398 		from->nextcp.x = to->prevcp.x = to->me.x;
1399 		from->nextcp.y = to->prevcp.y = (from->me.y+from->me.y)/2;
1400 	    } else if ( to->me.y==from->me.y ) {
1401 		from->nextcp.y = to->prevcp.y = to->me.y;
1402 		from->nextcp.x = to->prevcp.x = (from->me.x+from->me.x)/2;
1403 	    /* Assume they are drawing clockwise */
1404 	    } else if (( to->me.x>from->me.x && to->me.y>=from->me.y ) ||
1405 			(to->me.x<from->me.x && to->me.y<=from->me.y )) {
1406 		from->nextcp.x = to->prevcp.x = from->me.x;
1407 		from->nextcp.y = to->prevcp.y = to->me.y;
1408 	    } else {
1409 		from->nextcp.x = to->prevcp.x = to->me.x;
1410 		from->nextcp.y = to->prevcp.y = from->me.y;
1411 	    }
1412 	} else if ( !IsHV(to->next,1)) {
1413 	    if ( IsHV(from->prev,0)==1 ) {
1414 		from->nextcp.x = to->prevcp.x = to->me.x;
1415 		from->nextcp.y = to->prevcp.y = from->me.y;
1416 	    } else {
1417 		from->nextcp.x = to->prevcp.x = from->me.x;
1418 		from->nextcp.y = to->prevcp.y = to->me.y;
1419 	    }
1420 	} else if ( !IsHV(from->prev,0)) {
1421 	    if ( IsHV(to->next,1)==1 ) {
1422 		from->nextcp.x = to->prevcp.x = from->me.x;
1423 		from->nextcp.y = to->prevcp.y = to->me.y;
1424 	    } else {
1425 		from->nextcp.x = to->prevcp.x = to->me.x;
1426 		from->nextcp.y = to->prevcp.y = from->me.y;
1427 	    }
1428 	} else {
1429 	    if ( IsHV(from->prev,0)==1 && IsHV(to->next,1)==2 ) {
1430 		from->nextcp.x = to->prevcp.x = to->me.x;
1431 		from->nextcp.y = to->prevcp.y = from->me.y;
1432 	    } else if ( IsHV(from->prev,0)==2 && IsHV(to->next,1)==1 ) {
1433 		from->nextcp.x = to->prevcp.x = from->me.x;
1434 		from->nextcp.y = to->prevcp.y = to->me.y;
1435 	    } else
1436 		done = false;
1437 	}
1438 	if ( done )
1439 	    to->noprevcp = from->nonextcp = false;
1440     }
1441 
1442   if ( !done ) {
1443     unit.x = from->nextcp.x-from->me.x;
1444     unit.y = from->nextcp.y-from->me.y;
1445     len = sqrt(unit.x*unit.x + unit.y*unit.y);
1446     if ( len!=0 ) {
1447         unit.x /= len;
1448         unit.y /= len;
1449     }
1450 
1451     if ( (fpt = from->pointtype)==pt_hvcurve ) fpt = pt_curve;
1452     if ( (tpt =   to->pointtype)==pt_hvcurve ) tpt = pt_curve;
1453     if ( from->nextcpdef && to->prevcpdef ) switch ( fpt*3+tpt ) {
1454       case pt_corner*3+pt_corner:
1455       case pt_corner*3+pt_tangent:
1456       case pt_tangent*3+pt_corner:
1457       case pt_tangent*3+pt_tangent:
1458 	from->nonextcp = to->noprevcp = true;
1459 	from->nextcp = from->me;
1460 	to->prevcp = to->me;
1461       break;
1462       case pt_curve*3+pt_curve:
1463       case pt_curve*3+pt_corner:
1464       case pt_corner*3+pt_curve:
1465       case pt_tangent*3+pt_curve:
1466       case pt_curve*3+pt_tangent:
1467 	if ( from->prev!=NULL && (from->pointtype==pt_tangent || from->pointtype==pt_hvcurve)) {
1468 	    prev = from->prev->from;
1469 	    foff.x = prev->me.x;
1470 	    foff.y = prev->me.y;
1471 	} else if ( from->prev!=NULL ) {
1472 	    prev = from->prev->from;
1473 	    foff.x = to->me.x-prev->me.x  + from->me.x;
1474 	    foff.y = to->me.y-prev->me.y  + from->me.y;
1475 	} else {
1476 	    foff.x = from->me.x + (to->me.x-from->me.x)-(to->me.y-from->me.y);
1477 	    foff.y = from->me.y + (to->me.x-from->me.x)+(to->me.y-from->me.y);
1478 	    prev = NULL;
1479 	}
1480 	if ( to->next!=NULL && (to->pointtype==pt_tangent || to->pointtype==pt_hvcurve)) {
1481 	    next = to->next->to;
1482 	    toff.x = next->me.x;
1483 	    toff.y = next->me.y;
1484 	} else if ( to->next!=NULL ) {
1485 	    next = to->next->to;
1486 	    toff.x = next->me.x-from->me.x  + to->me.x;
1487 	    toff.y = next->me.y-from->me.y  + to->me.y;
1488 	} else {
1489 	    toff.x = to->me.x + (to->me.x-from->me.x)+(to->me.y-from->me.y);
1490 	    toff.y = to->me.y - (to->me.x-from->me.x)+(to->me.y-from->me.y);
1491 	    next = NULL;
1492 	}
1493 	if (( from->pointtype==pt_hvcurve && foff.x!=from->me.x && foff.y!=from->me.y ) ||
1494 		( to->pointtype==pt_hvcurve && toff.x!=to->me.x && toff.y!=to->me.y )) {
1495 	    if ( from->me.x == to->me.x ) {
1496 		if ( from->pointtype==pt_hvcurve )
1497 		    foff.x = from->me.x;
1498 		if ( to->pointtype==pt_hvcurve )
1499 		    toff.x = to->me.x;
1500 	    } else if ( from->me.y == to->me.y ) {
1501 		if ( from->pointtype==pt_hvcurve )
1502 		    foff.y = from->me.y;
1503 		if ( to->pointtype==pt_hvcurve )
1504 		    toff.y = to->me.y;
1505 	    } else {
1506 		if ( from->pointtype==pt_hvcurve && foff.x!=from->me.x && foff.y!=from->me.y ) {
1507 		    if ( fabs(foff.x-from->me.x) > fabs(foff.y-from->me.y) )
1508 			foff.y = from->me.y;
1509 		    else
1510 			foff.x = from->me.x;
1511 		}
1512 		if ( to->pointtype==pt_hvcurve && toff.x!=to->me.x && toff.y!=to->me.y ) {
1513 		    if ( from->pointtype==pt_hvcurve ) {
1514 			if ( from->me.x==foff.x )
1515 			    toff.y = to->me.y;
1516 			else
1517 			    toff.x = to->me.x;
1518 		    } else if ( fabs(toff.x-to->me.x) > fabs(toff.y-to->me.y) )
1519 			toff.y = to->me.y;
1520 		    else
1521 			toff.x = to->me.x;
1522 		}
1523 	    }
1524 	}
1525 	if ( IntersectLinesClip(&from->nextcp,&foff,&from->me,&toff,&to->me)) {
1526 	    from->nonextcp = to->noprevcp = false;
1527 	    to->prevcp = from->nextcp;
1528 	    if ( (from->pointtype==pt_curve || from->pointtype==pt_hvcurve ) &&
1529 		    !from->noprevcp && from->prev!=NULL ) {
1530 		prev = from->prev->from;
1531 		if ( IntersectLinesClip(&from->prevcp,&from->nextcp,&from->me,&prev->nextcp,&prev->me)) {
1532 		    prev->nextcp = from->prevcp;
1533 		    SplineRefigure2(from->prev);
1534 		}
1535 	    }
1536 	    if ( (to->pointtype==pt_curve || to->pointtype==pt_hvcurve) &&
1537 		    !to->nonextcp && to->next!=NULL ) {
1538 		next = to->next->to;
1539 		if ( IntersectLinesClip(&to->nextcp,&to->prevcp,&to->me,&next->prevcp,&next->me)) {
1540 		    next->prevcp = to->nextcp;
1541 		    SplineRefigure(to->next);
1542 		}
1543 	    }
1544 	}
1545       break;
1546     } else {
1547 	/* Can't set things arbetrarily here, but make sure they are consistant */
1548 	if ( (from->pointtype==pt_curve || from->pointtype==pt_hvcurve ) &&
1549 		!from->noprevcp && !from->nonextcp ) {
1550 	    unit.x = from->nextcp.x-from->me.x;
1551 	    unit.y = from->nextcp.y-from->me.y;
1552 	    len = sqrt(unit.x*unit.x + unit.y*unit.y);
1553 	    if ( len!=0 ) {
1554 		unit.x /= len; unit.y /= len;
1555 		len = sqrt((from->prevcp.x-from->me.x)*(from->prevcp.x-from->me.x) + (from->prevcp.y-from->me.y)*(from->prevcp.y-from->me.y));
1556 		new.x = -len*unit.x + from->me.x; new.y = -len*unit.y + from->me.y;
1557 		if ( new.x-from->prevcp.x<-1 || new.x-from->prevcp.x>1 ||
1558 			 new.y-from->prevcp.y<-1 || new.y-from->prevcp.y>1 ) {
1559 		    prev = NULL;
1560 		    if ( from->prev!=NULL && (prev = from->prev->from)!=NULL &&
1561 			    IntersectLinesClip(&from->prevcp,&new,&from->me,&prev->nextcp,&prev->me)) {
1562 			prev->nextcp = from->prevcp;
1563 			SplineRefigure2(from->prev);
1564 		    } else {
1565 			from->prevcp = new;
1566 			if ( prev!=NULL )
1567 			    prev->nextcp = new;
1568 		    }
1569 		}
1570 	    }
1571 	} else if ( from->pointtype==pt_tangent ) {
1572 	    if ( from->prev!=NULL ) {
1573 		prev = from->prev->from;
1574 		if ( !from->noprevcp && !prev->nonextcp &&
1575 			IntersectLinesClip(&from->prevcp,&to->me,&from->me,&prev->nextcp,&prev->me)) {
1576 		    prev->nextcp = from->prevcp;
1577 		    SplineRefigure2(from->prev);
1578 		}
1579 		if ( !from->nonextcp && !to->noprevcp &&
1580 			IntersectLinesClip(&from->nextcp,&prev->me,&from->me,&to->prevcp,&to->me))
1581 		    to->prevcp = from->nextcp;
1582 	    }
1583 	}
1584 	if ( (to->pointtype==pt_curve || to->pointtype==pt_hvcurve ) &&
1585 		!to->noprevcp && !to->nonextcp ) {
1586 	    unit.x = to->prevcp.x-to->nextcp.x;
1587 	    unit.y = to->prevcp.y-to->nextcp.y;
1588 	    len = sqrt(unit.x*unit.x + unit.y*unit.y);
1589 	    if ( len!=0 ) {
1590 		unit.x /= len; unit.y /= len;
1591 		len = sqrt((to->nextcp.x-to->me.x)*(to->nextcp.x-to->me.x) + (to->nextcp.y-to->me.y)*(to->nextcp.y-to->me.y));
1592 		new.x = -len*unit.x + to->me.x; new.y = -len*unit.y + to->me.y;
1593 		if ( new.x-to->nextcp.x<-1 || new.x-to->nextcp.x>1 ||
1594 			new.y-to->nextcp.y<-1 || new.y-to->nextcp.y>1 ) {
1595 		    if ( to->next!=NULL && (next = to->next->to)!=NULL &&
1596 			    IntersectLinesClip(&to->nextcp,&new,&to->me,&next->prevcp,&next->me)) {
1597 			next->prevcp = to->nextcp;
1598 			SplineRefigure2(to->next);
1599 		    } else {
1600 			to->nextcp = new;
1601 			if ( to->next!=NULL ) {
1602 			    to->next->to->prevcp = new;
1603 			    SplineRefigure(to->next);
1604 			}
1605 		    }
1606 		}
1607 	    }
1608 	} else if ( to->pointtype==pt_tangent ) {
1609 	    if ( to->next!=NULL ) {
1610 		next = to->next->to;
1611 		if ( !to->nonextcp && !next->noprevcp &&
1612 			IntersectLinesClip(&to->nextcp,&from->me,&to->me,&next->prevcp,&next->me)) {
1613 		    next->prevcp = to->nextcp;
1614 		    SplineRefigure2(to->next);
1615 		}
1616 		if ( !from->nonextcp && !to->noprevcp &&
1617 			IntersectLinesClip(&from->nextcp,&next->me,&to->me,&from->nextcp,&from->me))
1618 		    to->prevcp = from->nextcp;
1619 	    }
1620 	}
1621     }
1622     if ( from->nonextcp && to->noprevcp )
1623 	/* Ok */;
1624     else if ( from->nonextcp || to->noprevcp ) {
1625 	from->nonextcp = to->noprevcp = true;
1626     } else if (( from->nextcp.x==from->me.x && from->nextcp.y==from->me.y ) ||
1627 		( to->prevcp.x==to->me.x && to->prevcp.y==to->me.y ) ) {
1628 	from->nonextcp = to->noprevcp = true;
1629     } else if ( from->nonextcp || to->noprevcp || from->nextcp.x!=to->prevcp.x ||
1630 	    from->nextcp.y!=to->prevcp.y ) {
1631 	if ( !IntersectLinesClip(&from->nextcp,
1632 		(from->pointtype==pt_tangent && from->prev!=NULL)?&from->prev->from->me:&from->nextcp, &from->me,
1633 		(to->pointtype==pt_tangent && to->next!=NULL)?&to->next->to->me:&to->prevcp, &to->me)) {
1634 	    from->nextcp.x = (from->me.x+to->me.x)/2;
1635 	    from->nextcp.y = (from->me.y+to->me.y)/2;
1636 	}
1637 	to->prevcp = from->nextcp;
1638 	if (( from->nextcp.x==from->me.x && from->nextcp.y==from->me.y ) ||
1639 		( to->prevcp.x==to->me.x && to->prevcp.y==to->me.y ) ) {
1640 	    from->nonextcp = to->noprevcp = true;
1641 	    from->nextcp = from->me;
1642 	    to->prevcp = to->me;
1643 	}
1644     }
1645   }
1646     if ( snaptoint && !from->nonextcp ) {
1647 	from->nextcp.x = to->prevcp.x = rint(from->nextcp.x);
1648 	from->nextcp.y = to->prevcp.y = rint(from->nextcp.y);
1649     }
1650     SplineRefigure2(spline);
1651 
1652     /* Now in order2 splines it is possible to request combinations that are */
1653     /*  mathematically impossible -- two adjacent hv points often don't work */
1654     if ( to->pointtype==pt_hvcurve &&
1655 		!(to->prevcp.x == to->me.x && to->prevcp.y != to->me.y ) &&
1656 		!(to->prevcp.y == to->me.y && to->prevcp.x != to->me.x ) )
1657 	to->pointtype = pt_curve;
1658     if ( from->pointtype==pt_hvcurve &&
1659 		!(from->nextcp.x == from->me.x && from->nextcp.y != from->me.y ) &&
1660 		!(from->nextcp.y == from->me.y && from->nextcp.x != from->me.x ) )
1661 	from->pointtype = pt_curve;
1662 }
1663 
SplineMake2(SplinePoint * from,SplinePoint * to)1664 Spline *SplineMake2(SplinePoint *from, SplinePoint *to) {
1665     Spline *spline = chunkalloc(sizeof(Spline));
1666 
1667     spline->from = from; spline->to = to;
1668     from->next = to->prev = spline;
1669     spline->order2 = true;
1670     SplineRefigure2(spline);
1671 return( spline );
1672 }
1673 
SplineMake(SplinePoint * from,SplinePoint * to,int order2)1674 Spline *SplineMake(SplinePoint *from, SplinePoint *to, int order2) {
1675     if (order2 > 0)
1676 return( SplineMake2(from,to));
1677     else
1678 return( SplineMake3(from,to));
1679 }
1680 
SplinePointPrevCPChanged2(SplinePoint * sp)1681 void SplinePointPrevCPChanged2(SplinePoint *sp) {
1682     SplinePoint *p, *pp;
1683     BasePoint p_pcp;
1684 
1685     if ( sp->prev!=NULL ) {
1686 	p = sp->prev->from;
1687 	if ( SPInterpolate(p) && !sp->noprevcp ) {
1688 	    p->nextcp = sp->prevcp;
1689 	    p->me.x = ( p->prevcp.x+p->nextcp.x)/2;
1690 	    p->me.y = ( p->prevcp.y+p->nextcp.y)/2;
1691 	    SplineRefigure2(sp->prev);
1692 	    if (p->prev != NULL) SplineRefigure2(p->prev);
1693 	} else {
1694 	    p->nextcp = sp->prevcp;
1695 	    p->nonextcp = sp->noprevcp;
1696 	    if ( sp->noprevcp ) {
1697 		p->nonextcp = true;
1698 		p->nextcp = p->me;
1699 		SplineRefigure2(sp->prev);
1700 	    } else if (( p->pointtype==pt_curve || p->pointtype==pt_hvcurve ) &&
1701 		    !p->noprevcp ) {
1702 		SplineRefigure2(sp->prev);
1703 		if ( p->prev==NULL ) {
1704 		    bigreal len1, len2;
1705 		    len1 = sqrt((p->nextcp.x-p->me.x)*(p->nextcp.x-p->me.x) +
1706 				(p->nextcp.y-p->me.y)*(p->nextcp.y-p->me.y));
1707 		    len2 = sqrt((p->prevcp.x-p->me.x)*(p->prevcp.x-p->me.x) +
1708 				(p->prevcp.y-p->me.y)*(p->prevcp.y-p->me.y));
1709 		    len2 /= len1;
1710 		    p->prevcp.x = rint(len2 * (p->me.x-p->prevcp.x) + p->me.x);
1711 		    p->prevcp.y = rint(len2 * (p->me.y-p->prevcp.y) + p->me.y);
1712 		} else {
1713 		    pp = p->prev->from;
1714 		    /* Find the intersection (if any) of the lines between */
1715 		    /*  pp->nextcp&pp->me with p->prevcp&p->me */
1716 		    if ( IntersectLines(&p_pcp,&pp->nextcp,&pp->me,&p->nextcp,&p->me)) {
1717 			bigreal len = (pp->me.x-p->me.x)*(pp->me.x-p->me.x) + (pp->me.y-p->me.y)*(pp->me.y-p->me.y);
1718 			bigreal d1 = (p_pcp.x-p->me.x)*(pp->me.x-p->me.x) + (p_pcp.y-p->me.y)*(pp->me.y-p->me.y);
1719 			bigreal d2 = (p_pcp.x-pp->me.x)*(p->me.x-pp->me.x) + (p_pcp.y-pp->me.y)*(p->me.y-pp->me.y);
1720 			if ( d1>=0 && d1<=len && d2>=0 && d2<=len ) {
1721 			    if ( rint(2*p->me.x)==2*p->me.x && rint(2*pp->me.x)==2*pp->me.x )
1722 				p_pcp.x = rint( p_pcp.x );
1723 			    if ( rint(2*p->me.y)==2*p->me.y && rint(2*pp->me.y)==2*pp->me.y )
1724 				p_pcp.y = rint( p_pcp.y );
1725 			    p->prevcp = pp->nextcp = p_pcp;
1726 			    SplineRefigure2(p->prev);
1727 			}
1728 		    }
1729 		}
1730 	    }
1731 	}
1732     }
1733 }
1734 
SplinePointNextCPChanged2(SplinePoint * sp)1735 void SplinePointNextCPChanged2(SplinePoint *sp) {
1736     SplinePoint *n, *nn;
1737     BasePoint n_ncp;
1738 
1739     if ( sp->next!=NULL ) {
1740 	n = sp->next->to;
1741 	if ( SPInterpolate(n) && !sp->nonextcp ) {
1742 	    n->prevcp = sp->nextcp;
1743 	    n->me.x = ( n->prevcp.x+n->nextcp.x)/2;
1744 	    n->me.y = ( n->prevcp.y+n->nextcp.y)/2;
1745 	    SplineRefigure2(sp->next);
1746 	    if (n->next != NULL) SplineRefigure2(n->next);
1747 	} else {
1748 	    n->prevcp = sp->nextcp;
1749 	    n->noprevcp = sp->nonextcp;
1750 	    if ( sp->nonextcp ) {
1751 		n->noprevcp = true;
1752 		n->prevcp = n->me;
1753 		SplineRefigure2(sp->next);
1754 	    } else if (( n->pointtype==pt_curve || n->pointtype==pt_hvcurve ) &&
1755 		    !n->nonextcp ) {
1756 		SplineRefigure2(sp->next);
1757 		if ( n->next==NULL ) {
1758 		    bigreal len1, len2;
1759 		    len1 = sqrt((n->prevcp.x-n->me.x)*(n->prevcp.x-n->me.x) +
1760 				(n->prevcp.y-n->me.y)*(n->prevcp.y-n->me.y));
1761 		    len2 = sqrt((n->nextcp.x-n->me.x)*(n->nextcp.x-n->me.x) +
1762 				(n->nextcp.y-n->me.y)*(n->nextcp.y-n->me.y));
1763 		    len2 /= len1;
1764 		    n->nextcp.x = rint(len2 * (n->me.x-n->nextcp.x) + n->me.x);
1765 		    n->nextcp.y = rint(len2 * (n->me.y-n->nextcp.y) + n->me.y);
1766 		} else {
1767 		    nn = n->next->to;
1768 		    /* Find the intersection (if any) of the lines between */
1769 		    /*  nn->prevcp&nn->me with n->nextcp&.->me */
1770 		    if ( IntersectLines(&n_ncp,&nn->prevcp,&nn->me,&n->prevcp,&n->me)) {
1771 			bigreal len = (nn->me.x-n->me.x)*(nn->me.x-n->me.x) + (nn->me.y-n->me.y)*(nn->me.y-n->me.y);
1772 			bigreal d1 = (n_ncp.x-n->me.x)*(nn->me.x-n->me.x) + (n_ncp.y-n->me.y)*(nn->me.y-n->me.y);
1773 			bigreal d2 = (n_ncp.x-nn->me.x)*(n->me.x-nn->me.x) + (n_ncp.y-nn->me.y)*(n->me.y-nn->me.y);
1774 			if ( d1>=0 && d1<=len && d2>=0 && d2<=len ) {
1775 			    if ( rint(2*n->me.x)==2*n->me.x && rint(2*nn->me.x)==2*nn->me.x )
1776 				n_ncp.x = rint( n_ncp.x);
1777 			    if ( rint(2*n->me.y)==2*n->me.y && rint(2*nn->me.y)==2*nn->me.y )
1778 				n_ncp.y = rint( n_ncp.y);
1779 			    n->nextcp = nn->prevcp = n_ncp;
1780 			    SplineRefigure2(n->next);
1781 			}
1782 		    }
1783 		}
1784 	    }
1785 	}
1786     }
1787 }
1788