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