1 /* -*- coding: utf-8 -*- */
2 /* Copyright (C) 2000-2012 by George Williams */
3 /*
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6
7 * Redistributions of source code must retain the above copyright notice, this
8 * list of conditions and the following disclaimer.
9
10 * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13
14 * The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
18 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
20 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
23 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
25 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
26 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <fontforge-config.h>
30
31 #include "splineutil2.h"
32
33 #include "autohint.h"
34 #include "chardata.h"
35 #include "cvundoes.h"
36 #include "edgelist.h"
37 #include "fontforge.h"
38 #include "gutils.h"
39 #include "namelist.h"
40 #include "psread.h"
41 #include "spiro.h"
42 #include "splinefill.h"
43 #include "splinefit.h"
44 #include "splineorder2.h"
45 #include "splineoverlap.h"
46 #include "splineutil.h"
47 #include "ustring.h"
48 #include "views.h" /* For SCCharChangedUpdate */
49
50 #include <math.h>
51 #include <stdlib.h>
52 #include <time.h>
53 #include <unistd.h>
54
55 int new_em_size = 1000;
56 int new_fonts_are_order2 = false;
57 int loaded_fonts_same_as_new = false;
58 int default_fv_row_count = 4;
59 int default_fv_col_count = 16;
60 int default_fv_font_size = 48;
61 int default_fv_antialias=true;
62 int default_fv_bbsized=false;
63 int snaptoint=0;
64
65 /*#define DEBUG 1*/
66
67 #if defined( FONTFORGE_CONFIG_USE_DOUBLE )
68 # define RE_NearZero .00000001
69 # define RE_Factor (1024.0*1024.0*1024.0*1024.0*1024.0*2.0) /* 52 bits => divide by 2^51 */
70 #else
71 # define RE_NearZero .00001
72 # define RE_Factor (1024.0*1024.0*4.0) /* 23 bits => divide by 2^22 */
73 #endif
74
Within4RoundingErrors(bigreal v1,bigreal v2)75 int Within4RoundingErrors(bigreal v1, bigreal v2) {
76 bigreal temp=v1*v2;
77 bigreal re;
78
79 if ( temp<0 ) /* Ok, if the two values are on different sides of 0 there */
80 return( false ); /* is no way they can be within a rounding error of each other */
81 else if ( temp==0 ) {
82 if ( v1==0 )
83 return( v2<RE_NearZero && v2>-RE_NearZero );
84 else
85 return( v1<RE_NearZero && v1>-RE_NearZero );
86 } else if ( v1>0 ) {
87 if ( v1>v2 ) { /* Rounding error from the biggest absolute value */
88 re = v1/ (RE_Factor/4);
89 return( v1-v2 < re );
90 } else {
91 re = v2/ (RE_Factor/4);
92 return( v2-v1 < re );
93 }
94 } else {
95 if ( v1<v2 ) {
96 re = v1/ (RE_Factor/4); /* This will be a negative number */
97 return( v1-v2 > re );
98 } else {
99 re = v2/ (RE_Factor/4);
100 return( v2-v1 > re );
101 }
102 }
103 }
104
Within16RoundingErrors(bigreal v1,bigreal v2)105 int Within16RoundingErrors(bigreal v1, bigreal v2) {
106 bigreal temp=v1*v2;
107 bigreal re;
108
109 if ( temp<0 ) /* Ok, if the two values are on different sides of 0 there */
110 return( false ); /* is no way they can be within a rounding error of each other */
111 else if ( temp==0 ) {
112 if ( v1==0 )
113 return( v2<RE_NearZero && v2>-RE_NearZero );
114 else
115 return( v1<RE_NearZero && v1>-RE_NearZero );
116 } else if ( v1>0 ) {
117 if ( v1>v2 ) { /* Rounding error from the biggest absolute value */
118 re = v1/ (RE_Factor/16);
119 return( v1-v2 < re );
120 } else {
121 re = v2/ (RE_Factor/16);
122 return( v2-v1 < re );
123 }
124 } else {
125 if ( v1<v2 ) {
126 re = v1/ (RE_Factor/16); /* This will be a negative number */
127 return( v1-v2 > re );
128 } else {
129 re = v2/ (RE_Factor/16);
130 return( v2-v1 > re );
131 }
132 }
133 }
134
Within64RoundingErrors(bigreal v1,bigreal v2)135 int Within64RoundingErrors(bigreal v1, bigreal v2) {
136 bigreal temp=v1*v2;
137 bigreal re;
138
139 if ( temp<0 ) /* Ok, if the two values are on different sides of 0 there */
140 return( false ); /* is no way they can be within a rounding error of each other */
141 else if ( temp==0 ) {
142 if ( v1==0 )
143 return( v2<RE_NearZero && v2>-RE_NearZero );
144 else
145 return( v1<RE_NearZero && v1>-RE_NearZero );
146 } else if ( v1>0 ) {
147 if ( v1>v2 ) { /* Rounding error from the biggest absolute value */
148 re = v1/ (RE_Factor/64);
149 return( v1-v2 < re );
150 } else {
151 re = v2/ (RE_Factor/64);
152 return( v2-v1 < re );
153 }
154 } else {
155 if ( v1<v2 ) {
156 re = v1/ (RE_Factor/64); /* This will be a negative number */
157 return( v1-v2 > re );
158 } else {
159 re = v2/ (RE_Factor/64);
160 return( v2-v1 > re );
161 }
162 }
163 }
164
RealNear(real a,real b)165 bool RealNear(real a,real b) {
166 real d = a-b;
167 #ifdef FONTFORGE_CONFIG_USE_DOUBLE
168 // These tighter equals-zero tests are retained for code tuned when
169 // passing zero as a constant
170 if ( a==0 )
171 return b>-1e-8 && b<1e-8;
172 if ( b==0 )
173 return a>-1e-8 && a<1e-8;
174
175 return d>-1e-6 && d<1e-6;
176 #else /* For floats */
177 return d>-1e-5 && d<1e-5
178 #endif
179 }
180
181 int RealNearish(real a,real b) {
182
183 a-=b;
184 return( a<.001 && a>-.001 );
185 }
186
187 int RealApprox(real a,real b) {
188
189 if ( a==0 ) {
190 if ( b<.0001 && b>-.0001 )
191 return( true );
192 } else if ( b==0 ) {
193 if ( a<.0001 && a>-.0001 )
194 return( true );
195 } else {
196 a /= b;
197 if ( a>=.95 && a<=1.05 )
198 return( true );
199 }
200 return( false );
201 }
202
203 int RealWithin(real a,real b,real fudge) {
204
205 return( b>=a-fudge && b<=a+fudge );
206 }
207
208 int RealRatio(real a,real b,real fudge) {
209
210 if ( b==0 )
211 return( RealWithin(a,b,fudge));
212
213 return( RealWithin(a/b,1.0,fudge));
214 }
215
216 static int MinMaxWithin(Spline *spline) {
217 extended dx, dy;
218 int which;
219 extended t1, t2;
220 extended w;
221 /* We know that this "spline" is basically one dimensional. As long as its*/
222 /* extrema are between the start and end points on that line then we can */
223 /* treat it as a line. If the extrema are way outside the line segment */
224 /* then it's a line that backtracks on itself */
225
226 if ( (dx = spline->to->me.x - spline->from->me.x)<0 ) dx = -dx;
227 if ( (dy = spline->to->me.y - spline->from->me.y)<0 ) dy = -dy;
228 which = dx<dy;
229 SplineFindExtrema(&spline->splines[which],&t1,&t2);
230 if ( t1==-1 )
231 return( true );
232 w = ((spline->splines[which].a*t1 + spline->splines[which].b)*t1
233 + spline->splines[which].c)*t1 + spline->splines[which].d;
234 if ( RealNear(w, (&spline->to->me.x)[which]) || RealNear(w, (&spline->from->me.x)[which]) )
235 /* Close enough */;
236 else if ( (w<(&spline->to->me.x)[which] && w<(&spline->from->me.x)[which]) ||
237 (w>(&spline->to->me.x)[which] && w>(&spline->from->me.x)[which]) )
238 return( false ); /* Outside */
239
240 w = ((spline->splines[which].a*t2 + spline->splines[which].b)*t2
241 + spline->splines[which].c)*t2 + spline->splines[which].d;
242 if ( RealNear(w, (&spline->to->me.x)[which]) || RealNear(w, (&spline->from->me.x)[which]) )
243 /* Close enough */;
244 else if ( (w<(&spline->to->me.x)[which] && w<(&spline->from->me.x)[which]) ||
245 (w>(&spline->to->me.x)[which] && w>(&spline->from->me.x)[which]) )
246 return( false ); /* Outside */
247
248 return( true );
249 }
250
251 int SplineIsLinear(Spline *spline) {
252 bigreal t1,t2, t3,t4;
253 int ret;
254
255 if ( spline->knownlinear )
256 return( true );
257 if ( spline->knowncurved )
258 return( false );
259
260 if ( spline->splines[0].a==0 && spline->splines[0].b==0 &&
261 spline->splines[1].a==0 && spline->splines[1].b==0 )
262 return( true );
263
264 /* Something is linear if the control points lie on the line between the */
265 /* two base points */
266
267 /* Vertical lines */
268 if ( RealNear(spline->from->me.x,spline->to->me.x) ) {
269 ret = RealNear(spline->from->me.x,spline->from->nextcp.x) &&
270 RealNear(spline->from->me.x,spline->to->prevcp.x);
271 if ( ret && ! ((spline->from->nextcp.y >= spline->from->me.y &&
272 spline->from->nextcp.y <= spline->to->me.y &&
273 spline->to->prevcp.y >= spline->from->me.y &&
274 spline->to->prevcp.y <= spline->to->me.y ) ||
275 (spline->from->nextcp.y <= spline->from->me.y &&
276 spline->from->nextcp.y >= spline->to->me.y &&
277 spline->to->prevcp.y <= spline->from->me.y &&
278 spline->to->prevcp.y >= spline->to->me.y )) )
279 ret = MinMaxWithin(spline);
280 /* Horizontal lines */
281 } else if ( RealNear(spline->from->me.y,spline->to->me.y) ) {
282 ret = RealNear(spline->from->me.y,spline->from->nextcp.y) &&
283 RealNear(spline->from->me.y,spline->to->prevcp.y);
284 if ( ret && ! ((spline->from->nextcp.x >= spline->from->me.x &&
285 spline->from->nextcp.x <= spline->to->me.x &&
286 spline->to->prevcp.x >= spline->from->me.x &&
287 spline->to->prevcp.x <= spline->to->me.x) ||
288 (spline->from->nextcp.x <= spline->from->me.x &&
289 spline->from->nextcp.x >= spline->to->me.x &&
290 spline->to->prevcp.x <= spline->from->me.x &&
291 spline->to->prevcp.x >= spline->to->me.x)) )
292 ret = MinMaxWithin(spline);
293 } else {
294 ret = true;
295 t1 = (spline->from->nextcp.y-spline->from->me.y)/(spline->to->me.y-spline->from->me.y);
296 t2 = (spline->from->nextcp.x-spline->from->me.x)/(spline->to->me.x-spline->from->me.x);
297 t3 = (spline->to->me.y-spline->to->prevcp.y)/(spline->to->me.y-spline->from->me.y);
298 t4 = (spline->to->me.x-spline->to->prevcp.x)/(spline->to->me.x-spline->from->me.x);
299 ret = (Within16RoundingErrors(t1,t2) || (RealApprox(t1,0) && RealApprox(t2,0))) &&
300 (Within16RoundingErrors(t3,t4) || (RealApprox(t3,0) && RealApprox(t4,0)));
301 if ( ret ) {
302 if ( t1<0 || t2<0 || t3<0 || t4<0 ||
303 t1>1 || t2>1 || t3>1 || t4>1 )
304 ret = MinMaxWithin(spline);
305 }
306 }
307 spline->knowncurved = !ret;
308 spline->knownlinear = ret;
309 if ( ret ) {
310 /* A few places that if the spline is knownlinear then its splines[?] */
311 /* are linear. So give the linear version and not that suggested by */
312 /* the control points */
313 spline->splines[0].a = spline->splines[0].b = 0;
314 spline->splines[0].d = spline->from->me.x;
315 spline->splines[0].c = spline->to->me.x-spline->from->me.x;
316 spline->splines[1].a = spline->splines[1].b = 0;
317 spline->splines[1].d = spline->from->me.y;
318 spline->splines[1].c = spline->to->me.y-spline->from->me.y;
319 }
320 return( ret );
321 }
322
323 int SplineIsLinearMake(Spline *spline) {
324
325 if ( spline->islinear )
326 return( true );
327 if ( SplineIsLinear(spline)) {
328 spline->islinear = spline->from->nonextcp = spline->to->noprevcp = true;
329 spline->from->nextcp = spline->from->me;
330 if ( spline->from->nonextcp && spline->from->noprevcp )
331 spline->from->pointtype = pt_corner;
332 else if ( spline->from->pointtype == pt_curve || spline->from->pointtype == pt_hvcurve )
333 spline->from->pointtype = pt_tangent;
334 spline->to->prevcp = spline->to->me;
335 if ( spline->to->nonextcp && spline->to->noprevcp )
336 spline->to->pointtype = pt_corner;
337 else if ( spline->to->pointtype == pt_curve || spline->to->pointtype == pt_hvcurve )
338 spline->to->pointtype = pt_tangent;
339 SplineRefigure(spline);
340 }
341 return( spline->islinear );
342 }
343
344 int GoodCurve(SplinePoint *sp, int check_prev ) {
345 bigreal dx, dy, lenx, leny;
346
347 if ( sp->pointtype!=pt_curve && sp->pointtype!=pt_hvcurve )
348 return( false );
349 if ( check_prev ) {
350 dx = sp->me.x - sp->prevcp.x;
351 dy = sp->me.y - sp->prevcp.y;
352 } else {
353 dx = sp->me.x - sp->nextcp.x;
354 dy = sp->me.y - sp->nextcp.y;
355 }
356 /* If the cp is very close to the base point the point might as well be a corner */
357 if ( dx<0 ) dx = -dx;
358 if ( dy<0 ) dy = -dy;
359 if ( dx+dy<1 )
360 return( false );
361
362 if ( check_prev ) {
363 if ( sp->prev==NULL )
364 return( true );
365 lenx = sp->me.x - sp->prev->from->me.x;
366 leny = sp->me.y - sp->prev->from->me.y;
367 } else {
368 if ( sp->next==NULL )
369 return( true );
370 lenx = sp->me.x - sp->next->to->me.x;
371 leny = sp->me.y - sp->next->to->me.y;
372 }
373 if ( lenx<0 ) lenx = -lenx;
374 if ( leny<0 ) leny = -leny;
375 if ( 50*(dx+dy) < lenx+leny )
376 return( false );
377
378 return( true );
379 }
380
381 /* calculating the actual length of a spline is hard, this gives a very */
382 /* rough (but quick) approximation */
383 static bigreal SplineLenApprox(Spline *spline) {
384 bigreal len, slen, temp;
385
386 if ( (temp = spline->to->me.x-spline->from->me.x)<0 ) temp = -temp;
387 len = temp;
388 if ( (temp = spline->to->me.y-spline->from->me.y)<0 ) temp = -temp;
389 len += temp;
390 if ( !spline->to->noprevcp || !spline->from->nonextcp ) {
391 if ( (temp = spline->from->nextcp.x-spline->from->me.x)<0 ) temp = -temp;
392 slen = temp;
393 if ( (temp = spline->from->nextcp.y-spline->from->me.y)<0 ) temp = -temp;
394 slen += temp;
395 if ( (temp = spline->to->prevcp.x-spline->from->nextcp.x)<0 ) temp = -temp;
396 slen += temp;
397 if ( (temp = spline->to->prevcp.y-spline->from->nextcp.y)<0 ) temp = -temp;
398 slen += temp;
399 if ( (temp = spline->to->me.x-spline->to->prevcp.x)<0 ) temp = -temp;
400 slen += temp;
401 if ( (temp = spline->to->me.y-spline->to->prevcp.y)<0 ) temp = -temp;
402 slen += temp;
403 len = (len + slen)/2;
404 }
405 return( len );
406 }
407
408 bigreal SplineLength(Spline *spline) {
409 /* I ignore the constant term. It's just an unneeded addition */
410 bigreal len, t;
411 bigreal lastx = 0, lasty = 0;
412 bigreal curx, cury;
413
414 len = 0;
415 for ( t=1.0/128; t<=1.0001 ; t+=1.0/128 ) {
416 curx = ((spline->splines[0].a*t+spline->splines[0].b)*t+spline->splines[0].c)*t;
417 cury = ((spline->splines[1].a*t+spline->splines[1].b)*t+spline->splines[1].c)*t;
418 len += sqrt( (curx-lastx)*(curx-lastx) + (cury-lasty)*(cury-lasty) );
419 lastx = curx; lasty = cury;
420 }
421 return( len );
422 }
423
424 bigreal SplineLengthRange(Spline *spline,real from_t, real to_t) {
425 /* I ignore the constant term. It's just an unneeded addition */
426 bigreal len, t;
427 bigreal lastx = 0, lasty = 0;
428 bigreal curx, cury;
429
430 if ( from_t>to_t ) {
431 real fubble = to_t;
432 to_t = from_t;
433 from_t = fubble;
434 }
435
436 lastx = ((spline->splines[0].a*from_t+spline->splines[0].b)*from_t+spline->splines[0].c)*from_t;
437 lasty = ((spline->splines[1].a*from_t+spline->splines[1].b)*from_t+spline->splines[1].c)*from_t;
438 len = 0;
439 for ( t=from_t; t<to_t + 1.0/128 ; t+=1.0/128 ) {
440 if ( t>to_t ) t = to_t;
441 curx = ((spline->splines[0].a*t+spline->splines[0].b)*t+spline->splines[0].c)*t;
442 cury = ((spline->splines[1].a*t+spline->splines[1].b)*t+spline->splines[1].c)*t;
443 len += sqrt( (curx-lastx)*(curx-lastx) + (cury-lasty)*(cury-lasty) );
444 lastx = curx; lasty = cury;
445 if ( t==to_t )
446 break;
447 }
448 return( len );
449 }
450
451 bigreal PathLength(SplineSet *ss) {
452 Spline *s, *first=NULL;
453 bigreal len=0;
454
455 for ( s=ss->first->next; s!=NULL && s!=first; s=s->to->next ) {
456 len += SplineLength(s);
457 if ( first==NULL )
458 first = s;
459 }
460 return( len );
461 }
462
463 Spline *PathFindDistance(SplineSet *path,bigreal d,bigreal *_t) {
464 Spline *s, *first=NULL, *last=NULL;
465 bigreal len=0, diff;
466 bigreal curx, cury;
467 bigreal t;
468
469 for ( s=path->first->next; s!=NULL && s!=first; s=s->to->next ) {
470 bigreal lastx = 0, lasty = 0;
471 for ( t=1.0/128; t<=1.0001 ; t+=1.0/128 ) {
472 curx = ((s->splines[0].a*t+s->splines[0].b)*t+s->splines[0].c)*t;
473 cury = ((s->splines[1].a*t+s->splines[1].b)*t+s->splines[1].c)*t;
474 diff = sqrt( (curx-lastx)*(curx-lastx) + (cury-lasty)*(cury-lasty) );
475 lastx = curx; lasty = cury;
476 if ( len+diff>=d ) {
477 d -= len;
478 *_t = t - (diff-d)/diff * (1.0/128);
479 if ( *_t<0 ) *_t=0;
480 if ( *_t>1 ) *_t = 1;
481 return( s );
482 }
483 len += diff;
484 }
485 if ( first==NULL )
486 first = s;
487 last = s;
488 }
489 *_t = 1;
490 return( last );
491 }
492
493 static void SplinePointBindToPath(SplinePoint *sp,SplineSet *path) {
494 Spline *s;
495 bigreal t;
496 BasePoint pos, slope, ntemp, ptemp;
497 bigreal len;
498
499 s = PathFindDistance(path,sp->me.x,&t);
500 pos.x = ((s->splines[0].a*t + s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
501 pos.y = ((s->splines[1].a*t + s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
502 slope.x = (3*s->splines[0].a*t + 2*s->splines[0].b)*t+s->splines[0].c;
503 slope.y = (3*s->splines[1].a*t + 2*s->splines[1].b)*t+s->splines[1].c;
504 len = sqrt(slope.x*slope.x + slope.y*slope.y);
505 if ( len!=0 ) {
506 slope.x /= len;
507 slope.y /= len;
508 }
509
510 /* Now I could find a separate transformation matrix for the control points*/
511 /* but I think that would look odd (formerly smooth joints could become */
512 /* discontiguous) so I use the same transformation for all */
513 /* Except that doesn't work for order2 (I'll fix that later) */
514
515 ntemp.x = (sp->nextcp.x-sp->me.x)*slope.x - (sp->nextcp.y-sp->me.y)*slope.y;
516 ntemp.y = (sp->nextcp.x-sp->me.x)*slope.y + (sp->nextcp.y-sp->me.y)*slope.x;
517 ptemp.x = (sp->prevcp.x-sp->me.x)*slope.x - (sp->prevcp.y-sp->me.y)*slope.y;
518 ptemp.y = (sp->prevcp.x-sp->me.x)*slope.y + (sp->prevcp.y-sp->me.y)*slope.x;
519 sp->me.x = pos.x - sp->me.y*slope.y;
520 sp->me.y = pos.y + sp->me.y*slope.x;
521 sp->nextcp.x = sp->me.x + ntemp.x;
522 sp->nextcp.y = sp->me.y + ntemp.y;
523 sp->prevcp.x = sp->me.x + ptemp.x;
524 sp->prevcp.y = sp->me.y + ptemp.y;
525 }
526
527 static Spline *SplineBindToPath(Spline *s,SplineSet *path) {
528 /* OK. The endpoints and the control points have already been moved. */
529 /* But the transformation is potentially non-linear, so figure some */
530 /* intermediate values, and then approximate a new spline based on them */
531 FitPoint mids[3];
532 bigreal t, pt,len;
533 int i;
534 BasePoint spos, pos;
535 Spline *ps, *ret;
536
537 for ( i=0, t=.25; i<3 ; t += .25, ++i ) {
538 spos.x = ((s->splines[0].a*t + s->splines[0].b)*t+s->splines[0].c)*t+s->splines[0].d;
539 spos.y = ((s->splines[1].a*t + s->splines[1].b)*t+s->splines[1].c)*t+s->splines[1].d;
540 ps = PathFindDistance(path,spos.x,&pt);
541 pos.x = ((ps->splines[0].a*pt + ps->splines[0].b)*pt+ps->splines[0].c)*pt+ps->splines[0].d;
542 pos.y = ((ps->splines[1].a*pt + ps->splines[1].b)*pt+ps->splines[1].c)*pt+ps->splines[1].d;
543 mids[i].ut.x = (3*ps->splines[0].a*pt + 2*ps->splines[0].b)*pt+ps->splines[0].c;
544 mids[i].ut.y = (3*ps->splines[1].a*pt + 2*ps->splines[1].b)*pt+ps->splines[1].c;
545 len = sqrt(mids[i].ut.x*mids[i].ut.x + mids[i].ut.y*mids[i].ut.y);
546 if ( len!=0 ) {
547 mids[i].ut.x /= len;
548 mids[i].ut.y /= len;
549 }
550 mids[i].t = t;
551 mids[i].p.x = pos.x - spos.y*mids[i].ut.y;
552 mids[i].p.y = pos.y + spos.y*mids[i].ut.x;
553 }
554 ret = ApproximateSplineFromPointsSlopes(s->from,s->to,mids,i,false);
555 SplineFree(s);
556 return( ret );
557 }
558
559 static void GlyphBindToPath(SplineSet *glyph,SplineSet *path) {
560 /* Find the transformation for the middle of the glyph, and then rotate */
561 /* the entire thing by that */
562 bigreal pt,len;
563 BasePoint pos, slope;
564 Spline *ps;
565 DBounds b;
566 real transform[6], offset[6], mid;
567
568 SplineSetFindBounds(glyph,&b);
569 mid = (b.minx+b.maxx)/2;
570 ps = PathFindDistance(path,mid,&pt);
571 pos.x = ((ps->splines[0].a*pt + ps->splines[0].b)*pt+ps->splines[0].c)*pt+ps->splines[0].d;
572 pos.y = ((ps->splines[1].a*pt + ps->splines[1].b)*pt+ps->splines[1].c)*pt+ps->splines[1].d;
573 slope.x = (3*ps->splines[0].a*pt + 2*ps->splines[0].b)*pt+ps->splines[0].c;
574 slope.y = (3*ps->splines[1].a*pt + 2*ps->splines[1].b)*pt+ps->splines[1].c;
575 len = sqrt(slope.x*slope.x + slope.y*slope.y);
576 if ( len!=0 ) {
577 slope.x /= len;
578 slope.y /= len;
579 }
580
581 memset(offset,0,sizeof(offset));
582 offset[0] = offset[3] = 1;
583 offset[4] = -mid;
584
585 transform[0] = transform[3] = slope.x;
586 transform[1] = slope.y; transform[2] = -slope.y;
587 transform[4] = pos.x;
588 transform[5] = pos.y;
589 MatMultiply(offset,transform,transform);
590 SplinePointListTransform(glyph,transform,tpt_AllPoints);
591 }
592
593
594 SplineSet *SplineSetBindToPath(SplineSet *ss,int doscale, int glyph_as_unit,
595 int align,real offset, SplineSet *path) {
596 DBounds b;
597 real transform[6];
598 bigreal pathlength = PathLength(path);
599 SplineSet *spl, *eog, *nextglyph;
600 SplinePoint *sp;
601 Spline *s, *first;
602 int order2 = -1;
603 BasePoint cp;
604
605 memset(transform,0,sizeof(transform));
606 transform[0] = transform[3] = 1;
607 SplineSetFindBounds(ss,&b);
608
609 if ( doscale && b.maxx-b.minx!=0 ) {
610 transform[0] = transform[3] = pathlength/(b.maxx-b.minx);
611 transform[4] = -b.minx;
612 } else if ( align == 0 ) { /* At start */
613 transform[4] = -b.minx;
614 } else if ( align == 1 ) { /* Centered */
615 transform[4] = (pathlength-(b.maxx-b.minx))/2 - b.minx;
616 } else { /* At end */
617 transform[4] = pathlength - b.maxx;
618 }
619 if ( pathlength==0 ) {
620 transform[4] += path->first->me.x;
621 transform[5] += path->first->me.y;
622 }
623 transform[5] += offset;
624 SplinePointListTransform(ss,transform,tpt_AllPoints);
625 if ( pathlength==0 )
626 return( ss );
627
628 if ( glyph_as_unit ) {
629 for ( spl = ss; spl!=NULL ; spl=nextglyph ) {
630 for ( eog=spl; eog!=NULL && !eog->ticked; eog=eog->next );
631 if ( eog==NULL )
632 nextglyph = NULL;
633 else {
634 nextglyph = eog->next;
635 eog->next = NULL;
636 }
637 GlyphBindToPath(spl,path);
638 if ( eog!=NULL )
639 eog->next = nextglyph;
640 }
641 } else {
642 for ( spl = ss; spl!=NULL ; spl=spl->next ) {
643 for ( sp = spl->first; ; ) {
644 SplinePointBindToPath(sp,path);
645 if ( sp->next==NULL )
646 break;
647 order2 = sp->next->order2;
648 sp = sp->next->to;
649 if ( sp==spl->first )
650 break;
651 }
652 }
653 if ( order2==1 ) {
654 for ( spl = ss; spl!=NULL ; spl=spl->next ) {
655 for ( sp = spl->first; ; ) {
656 if ( !sp->noprevcp && sp->prev!=NULL ) {
657 if ( !IntersectLines(&cp,&sp->me,&sp->prevcp,&sp->prev->from->nextcp,&sp->prev->from->me)) {
658 cp.x = (sp->prevcp.x+sp->prev->from->nextcp.x)/2;
659 cp.y = (sp->prevcp.y+sp->prev->from->nextcp.y)/2;
660 }
661 sp->prevcp = sp->prev->from->nextcp = cp;
662 }
663 if ( sp->next==NULL )
664 break;
665 sp = sp->next->to;
666 if ( sp==spl->first )
667 break;
668 }
669 }
670 }
671
672 for ( spl = ss; spl!=NULL ; spl=spl->next ) {
673 first = NULL;
674 for ( s=spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
675 if ( s->order2 )
676 SplineRefigure2(s);
677 else
678 s = SplineBindToPath(s,path);
679 if ( first==NULL )
680 first = s;
681 }
682 }
683 }
684 return( ss );
685 }
686
687 static FitPoint *SplinesFigureFPsBetween(SplinePoint *from, SplinePoint *to,
688 int *tot) {
689 int cnt, i, j, pcnt;
690 bigreal len, slen, lbase;
691 SplinePoint *np;
692 FitPoint *fp;
693 bigreal _lens[10], *lens = _lens;
694 int _cnts[10], *cnts = _cnts;
695 /* I used just to give every spline 10 points. But that gave much more */
696 /* weight to small splines than to big ones */
697
698 cnt = 0;
699 for ( np = from->next->to; ; np = np->next->to ) {
700 ++cnt;
701 if ( np==to )
702 break;
703 }
704 if ( cnt>10 ) {
705 lens = malloc(cnt*sizeof(bigreal));
706 cnts = malloc(cnt*sizeof(int));
707 }
708 cnt = 0; len = 0;
709 for ( np = from->next->to; ; np = np->next->to ) {
710 lens[cnt] = SplineLenApprox(np->prev);
711 len += lens[cnt];
712 ++cnt;
713 if ( np==to )
714 break;
715 }
716 if ( len!=0 ) {
717 pcnt = 0;
718 for ( i=0; i<cnt; ++i ) {
719 int pnts = rint( (10*cnt*lens[i])/len );
720 if ( pnts<2 ) pnts = 2;
721 cnts[i] = pnts;
722 pcnt += pnts;
723 }
724 } else
725 pcnt = 2*cnt;
726
727 fp = malloc((pcnt+1)*sizeof(FitPoint)); i = 0;
728 if ( len==0 ) {
729 for ( i=0; i<=pcnt; ++i ) {
730 fp[i].t = i/(pcnt);
731 fp[i].p.x = from->me.x;
732 fp[i].p.y = from->me.y;
733 }
734 } else {
735 lbase = 0;
736 for ( i=cnt=0, np = from->next->to; ; np = np->next->to, ++cnt ) {
737 slen = SplineLenApprox(np->prev);
738 for ( j=0; j<cnts[cnt]; ++j ) {
739 bigreal t = j/(bigreal) cnts[cnt];
740 fp[i].t = (lbase+ t*slen)/len;
741 fp[i].p.x = ((np->prev->splines[0].a*t+np->prev->splines[0].b)*t+np->prev->splines[0].c)*t + np->prev->splines[0].d;
742 fp[i++].p.y = ((np->prev->splines[1].a*t+np->prev->splines[1].b)*t+np->prev->splines[1].c)*t + np->prev->splines[1].d;
743 }
744 lbase += slen;
745 if ( np==to )
746 break;
747 }
748 }
749 if ( cnts!=_cnts ) free(cnts);
750 if ( lens!=_lens ) free(lens);
751
752 *tot = i;
753
754 return( fp );
755 }
756
757 static void SplinePointReCategorize(SplinePoint *sp,int oldpt) {
758 SplinePointCategorize(sp);
759 if ( sp->pointtype!=oldpt ) {
760 if ( sp->pointtype==pt_curve && oldpt==pt_hvcurve &&
761 ((sp->nextcp.x == sp->me.x && sp->nextcp.y != sp->me.y ) ||
762 (sp->nextcp.y == sp->me.y && sp->nextcp.x != sp->me.x )))
763 sp->pointtype = pt_hvcurve;
764 }
765 }
766
767 void SplinesRemoveBetween(SplineChar *sc, SplinePoint *from, SplinePoint *to,int type) {
768 int tot;
769 FitPoint *fp;
770 SplinePoint *np, oldfrom;
771 int oldfpt = from->pointtype, oldtpt = to->pointtype;
772 Spline *sp;
773 int order2 = from->next->order2;
774
775 oldfrom = *from;
776 fp = SplinesFigureFPsBetween(from,to,&tot);
777
778 if ( type==1 )
779 ApproximateSplineFromPointsSlopes(from,to,fp,tot-1,order2);
780 else
781 ApproximateSplineFromPoints(from,to,fp,tot-1,order2);
782
783 /* Have to do the frees after the approximation because the approx */
784 /* uses the splines to determine slopes */
785 for ( sp = oldfrom.next; ; ) {
786 np = sp->to;
787 SplineFree(sp);
788 if ( np==to )
789 break;
790 sp = np->next;
791 SplinePointMDFree(sc,np);
792 }
793
794 free(fp);
795
796 SplinePointReCategorize(from,oldfpt);
797 SplinePointReCategorize(to,oldtpt);
798 }
799
800 static void RemoveZeroLengthSplines(SplineSet *spl, int onlyselected, bigreal bound) {
801 SplinePoint *curp, *next, *prev;
802 bigreal plen, nlen;
803
804 bound *= bound;
805
806 for ( curp = spl->first, prev=NULL; curp!=NULL ; curp=next ) {
807 next = NULL;
808 if ( curp->next!=NULL )
809 next = curp->next->to;
810 if ( curp==next ) /* Once we've worked a contour down to a single point we can't do anything more here. Someone else will have to free the contour */
811 return;
812 /* Zero length splines give us NaNs */
813 if ( curp!=NULL && (curp->selected || !onlyselected) ) {
814 plen = nlen = 1e10;
815 if ( curp->prev!=NULL ) {
816 plen = (curp->me.x-curp->prev->from->me.x)*(curp->me.x-curp->prev->from->me.x) +
817 (curp->me.y-curp->prev->from->me.y)*(curp->me.y-curp->prev->from->me.y);
818 if ( plen<=bound ) {
819 plen =
820 sqrt( (curp->me.x-curp->prevcp.x)*(curp->me.x-curp->prevcp.x) +
821 (curp->me.y-curp->prevcp.y)*(curp->me.y-curp->prevcp.y)) +
822 sqrt( (curp->prevcp.x-curp->prev->from->nextcp.x)*(curp->prevcp.x-curp->prev->from->nextcp.x) +
823 (curp->prevcp.y-curp->prev->from->nextcp.y)*(curp->prevcp.y-curp->prev->from->nextcp.y)) +
824 sqrt( (curp->prev->from->nextcp.x-curp->prev->from->me.x)*(curp->prev->from->nextcp.x-curp->prev->from->me.x) +
825 (curp->prev->from->nextcp.y-curp->prev->from->me.y)*(curp->prev->from->nextcp.y-curp->prev->from->me.y));
826 plen *= plen;
827 }
828 }
829 if ( curp->next!=NULL ) {
830 nlen = (curp->me.x-next->me.x)*(curp->me.x-next->me.x) +
831 (curp->me.y-next->me.y)*(curp->me.y-next->me.y);
832 if ( nlen<=bound ) {
833 nlen =
834 sqrt( (curp->me.x-curp->nextcp.x)*(curp->me.x-curp->nextcp.x) +
835 (curp->me.y-curp->nextcp.y)*(curp->me.y-curp->nextcp.y)) +
836 sqrt( (curp->nextcp.x-curp->next->to->prevcp.x)*(curp->nextcp.x-curp->next->to->prevcp.x) +
837 (curp->nextcp.y-curp->next->to->prevcp.y)*(curp->nextcp.y-curp->next->to->prevcp.y)) +
838 sqrt( (curp->next->to->prevcp.x-curp->next->to->me.x)*(curp->next->to->prevcp.x-curp->next->to->me.x) +
839 (curp->next->to->prevcp.y-curp->next->to->me.y)*(curp->next->to->prevcp.y-curp->next->to->me.y));
840 nlen *= nlen;
841 }
842 }
843 if (( curp->prev!=NULL && plen<=bound && plen<nlen ) ||
844 (curp->next!=NULL && nlen<=bound && nlen<=plen )) {
845 if ( curp->prev!=NULL && plen<=bound && plen<nlen ) {
846 SplinePoint *other = curp->prev->from;
847 other->nextcp = curp->nextcp;
848 other->nonextcp = curp->nonextcp;
849 other->nextcpdef = curp->nextcpdef;
850 other->next = curp->next;
851 if ( curp->next!=NULL ) other->next->from = other;
852 SplineFree(curp->prev);
853 } else {
854 SplinePoint *other = next;
855 other->prevcp = curp->prevcp;
856 other->noprevcp = curp->noprevcp;
857 other->prevcpdef = curp->prevcpdef;
858 other->prev = curp->prev;
859 if ( curp->prev!=NULL ) other->prev->to = other;
860 SplineFree(curp->next);
861 }
862 SplinePointFree(curp);
863 if ( spl->first==curp ) {
864 spl->first = next;
865 spl->start_offset = 0;
866 if ( spl->last==curp )
867 spl->last = next;
868 } else if ( spl->last==curp )
869 spl->last = prev;
870 } else
871 prev = curp;
872 } else
873 prev = curp;
874 if ( next==spl->first )
875 break;
876 }
877 }
878
879 SplineSet *SSRemoveZeroLengthSplines(SplineSet *base) {
880 SplineSet *spl;
881
882 for ( spl=base; spl!=NULL; spl=spl->next ) {
883 RemoveZeroLengthSplines(spl,false,0);
884 if ( spl->first->next!=NULL && spl->first->next->to==spl->first &&
885 spl->first->nonextcp && spl->first->noprevcp ) {
886 /* Turn it into a single point, rather than a zero length contour */
887 chunkfree(spl->first->next,sizeof(Spline));
888 spl->first->next = spl->first->prev = NULL;
889 }
890 }
891 return( base );
892 }
893
894 static void RemoveStupidControlPoints(SplineSet *spl) {
895 bigreal len, normal, dir;
896 Spline *s, *first;
897 BasePoint unit, off;
898
899 /* Also remove really stupid control points: Tiny offsets pointing in */
900 /* totally the wrong direction. Some of the TeX fonts we get have these */
901 /* We get equally bad results with a control point that points beyond the */
902 /* other end point */
903 first = NULL;
904 for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
905 unit.x = s->to->me.x-s->from->me.x;
906 unit.y = s->to->me.y-s->from->me.y;
907 len = sqrt(unit.x*unit.x+unit.y*unit.y);
908 if ( len!=0 ) {
909 int refigure = false;
910 unit.x /= len; unit.y /= len;
911 if ( !s->from->nonextcp ) {
912 off.x = s->from->nextcp.x-s->from->me.x;
913 off.y = s->from->nextcp.y-s->from->me.y;
914 if ((normal = off.x*unit.y - off.y*unit.x)<0 ) normal = -normal;
915 dir = off.x*unit.x + off.y*unit.y;
916 if (( normal<dir && normal<1 && dir<0 ) || (normal<.5 && dir<-.5) ||
917 (normal<.1 && dir>len)) {
918 s->from->nextcp = s->from->me;
919 s->from->nonextcp = true;
920 refigure = true;
921 }
922 }
923 if ( !s->to->noprevcp ) {
924 off.x = s->to->me.x - s->to->prevcp.x;
925 off.y = s->to->me.y - s->to->prevcp.y;
926 if ((normal = off.x*unit.y - off.y*unit.x)<0 ) normal = -normal;
927 dir = off.x*unit.x + off.y*unit.y;
928 if (( normal<-dir && normal<1 && dir<0 ) || (normal<.5 && dir>-.5 && dir<0) ||
929 (normal<.1 && dir>len)) {
930 s->to->prevcp = s->to->me;
931 s->to->noprevcp = true;
932 refigure = true;
933 }
934 }
935 if ( refigure )
936 SplineRefigure(s);
937 }
938 if ( first==NULL ) first = s;
939 }
940 }
941
942 void SSRemoveStupidControlPoints(SplineSet *base) {
943 SplineSet *spl;
944
945 for (spl=base; spl!=NULL; spl=spl->next )
946 RemoveStupidControlPoints(spl);
947 }
948
949 static void OverlapClusterCpAngles(SplineSet *spl,bigreal within) {
950 bigreal len, nlen, plen;
951 bigreal startoff, endoff;
952 SplinePoint *sp, *nsp, *psp;
953 BasePoint *nbp, *pbp;
954 BasePoint pdir, ndir, fpdir, fndir;
955 int nbad, pbad;
956
957 /* Does this even work? Why do we dot ndir with the normal of pdir? !!!! */
958
959 /* If we have a junction point (right mid of 3) where the two splines */
960 /* are almost, but not quite moving in the same direction as they go */
961 /* away from the point, and if there is a tiny overlap because of this */
962 /* "almost" same, then we will probably get a bit confused in remove */
963 /* overlap */
964
965 if ( spl->first->next!=NULL && spl->first->next->order2 )
966 return;
967
968 for ( sp = spl->first; ; ) {
969 if ( sp->next==NULL )
970 break;
971 nsp = sp->next->to;
972 if (( !sp->nonextcp || !sp->noprevcp ) && sp->prev!=NULL ) {
973 psp = sp->prev->from;
974 nbp = !sp->nonextcp ? &sp->nextcp : !nsp->noprevcp ? &nsp->prevcp : &nsp->me;
975 pbp = !sp->noprevcp ? &sp->prevcp : !psp->nonextcp ? &psp->nextcp : &psp->me;
976
977 pdir.x = pbp->x-sp->me.x; pdir.y = pbp->y-sp->me.y;
978 ndir.x = nbp->x-sp->me.x; ndir.y = nbp->y-sp->me.y;
979 fpdir.x = psp->me.x-sp->me.x; fpdir.y = psp->me.y-sp->me.y;
980 fndir.x = nsp->me.x-sp->me.x; fndir.y = nsp->me.y-sp->me.y;
981
982 plen = sqrt(pdir.x*pdir.x+pdir.y*pdir.y);
983 if ( plen!=0 ) {
984 pdir.x /= plen; pdir.y /= plen;
985 }
986
987 nlen = sqrt(ndir.x*ndir.x+ndir.y*ndir.y);
988 if ( nlen!=0 ) {
989 ndir.x /= nlen; ndir.y /= nlen;
990 }
991
992 nbad = pbad = false;
993 if ( !sp->nonextcp && plen!=0 && nlen!=0 ) {
994 len = sqrt(fndir.x*fndir.x+fndir.y*fndir.y);
995 if ( len!=0 ) {
996 fndir.x /= len; fndir.y /= len;
997 startoff = ndir.x*pdir.y - ndir.y*pdir.x;
998 endoff = fndir.x*pdir.y - fndir.y*pdir.x;
999 if (( (startoff<0 && endoff>0) || (startoff>0 && endoff<0)) &&
1000 startoff > -within && startoff < within )
1001 nbad = true;
1002 }
1003 }
1004 if ( !sp->noprevcp && plen!=0 && nlen!=0 ) {
1005 len = sqrt(fpdir.x*fpdir.x+fpdir.y*fpdir.y);
1006 if ( len!=0 ) {
1007 fpdir.x /= len; fpdir.y /= len;
1008 startoff = pdir.x*ndir.y - pdir.y*ndir.x;
1009 endoff = fpdir.x*ndir.y - fpdir.y*ndir.x;
1010 if (( (startoff<0 && endoff>0) || (startoff>0 && endoff<0)) &&
1011 startoff > -within && startoff < within )
1012 pbad = true;
1013 }
1014 }
1015 if ( nbad && pbad ) {
1016 if ( ndir.x==0 || ndir.y==0 )
1017 nbad = false;
1018 else if ( pdir.x==0 || pdir.y==0 )
1019 pbad = false;
1020 }
1021 if ( nbad && pbad ) {
1022 if ( ndir.x*pdir.x + ndir.y*pdir.y > 0 ) {
1023 ndir.x = pdir.x = (ndir.x + pdir.x)/2;
1024 ndir.y = pdir.y = (ndir.x + pdir.x)/2;
1025 } else {
1026 ndir.x = (ndir.x - pdir.x)/2;
1027 ndir.y = (ndir.y - pdir.y)/2;
1028 pdir.x = -ndir.x; pdir.y = -ndir.y;
1029 }
1030 sp->nextcp.x = sp->me.x + nlen*ndir.x;
1031 sp->nextcp.y = sp->me.y + nlen*ndir.y;
1032 sp->prevcp.x = sp->me.x + plen*pdir.x;
1033 sp->prevcp.y = sp->me.y + plen*pdir.y;
1034 SplineRefigure(sp->next); SplineRefigure(sp->prev);
1035 } else if ( nbad ) {
1036 if ( ndir.x*pdir.x + ndir.y*pdir.y < 0 ) {
1037 pdir.x = -pdir.x;
1038 pdir.y = -pdir.y;
1039 }
1040 sp->nextcp.x = sp->me.x + nlen*pdir.x;
1041 sp->nextcp.y = sp->me.y + nlen*pdir.y;
1042 SplineRefigure(sp->next);
1043 } else if ( pbad ) {
1044 if ( ndir.x*pdir.x + ndir.y*pdir.y < 0 ) {
1045 ndir.x = -ndir.x;
1046 ndir.y = -ndir.y;
1047 }
1048 sp->prevcp.x = sp->me.x + plen*ndir.x;
1049 sp->prevcp.y = sp->me.y + plen*ndir.y;
1050 SplineRefigure(sp->prev);
1051 }
1052 }
1053 if ( nsp==spl->first )
1054 break;
1055 sp = nsp;
1056 }
1057 }
1058
1059 void SSOverlapClusterCpAngles(SplineSet *base,bigreal within) {
1060 SplineSet *spl;
1061
1062 for (spl=base; spl!=NULL; spl=spl->next )
1063 OverlapClusterCpAngles(spl,within);
1064 }
1065
1066 static SplinePointList *SplinePointListMerge(SplineChar *sc, SplinePointList *spl,int type) {
1067 Spline *spline, *first;
1068 SplinePoint *nextp, *curp, *selectme;
1069 int all, any;
1070
1071
1072 /* If the entire splineset is selected, it should merge into oblivion */
1073 first = NULL;
1074 /* The python contour merge code calls with NULL, but that interface
1075 currently only works for bezier contours */
1076 if ( sc!=NULL && sc->inspiro && hasspiro() ) {
1077 int i,j;
1078 any = false; all = true;
1079 for ( i=0; i<spl->spiro_cnt-1; ++i )
1080 if ( SPIRO_SELECTED(&spl->spiros[i]))
1081 any = true;
1082 else
1083 all = false;
1084 if ( all )
1085 return( NULL );
1086 else if ( any ) {
1087 for ( i=0; i<spl->spiro_cnt-1; ++i )
1088 if ( SPIRO_SELECTED(&spl->spiros[i])) {
1089 for ( j=i+1; j<spl->spiro_cnt ; ++j )
1090 spl->spiros[j-1] = spl->spiros[j];
1091 --spl->spiro_cnt;
1092 }
1093 SSRegenerateFromSpiros(spl);
1094 }
1095 return( spl );
1096 }
1097
1098 any = all = spl->first->selected;
1099 for ( spline = spl->first->next; spline!=NULL && spline!=first && all; spline=spline->to->next ) {
1100 if ( spline->to->selected ) any = true;
1101 else all = false;
1102 if ( first==NULL ) first = spline;
1103 }
1104 if ( spl->first->next!=NULL && spl->first->next->to==spl->first &&
1105 spl->first->nonextcp && spl->first->noprevcp )
1106 all = true; /* Merge away any splines which are just dots */
1107 if ( all )
1108 return( NULL ); /* Some one else should free it and reorder the spline set list */
1109 RemoveZeroLengthSplines(spl,true,.3);
1110
1111 if ( spl->first!=spl->last ) {
1112 /* If the spline isn't closed, then any selected points at the ends */
1113 /* get deleted */
1114 while ( spl->first->selected ) {
1115 nextp = spl->first->next->to;
1116 SplineFree(spl->first->next);
1117 SplinePointMDFree(sc,spl->first);
1118 spl->first = nextp;
1119 spl->start_offset = 0;
1120 nextp->prev = NULL;
1121 }
1122 while ( spl->last->selected ) {
1123 nextp = spl->last->prev->from;
1124 SplineFree(spl->last->prev);
1125 SplinePointMDFree(sc,spl->last);
1126 spl->last = nextp;
1127 nextp->next = NULL;
1128 }
1129 } else {
1130 while ( spl->first->selected ) {
1131 spl->first = spl->first->next->to;
1132 spl->start_offset = 0;
1133 spl->last = spl->first;
1134 }
1135 }
1136
1137 /* when we get here spl->first is not selected */
1138 if ( spl->first->selected ) IError( "spl->first is selected in SplinePointListMerge");
1139 curp = spl->first;
1140 selectme = NULL;
1141 while ( 1 ) {
1142 while ( !curp->selected ) {
1143 if ( curp->next==NULL )
1144 curp = NULL;
1145 else
1146 curp = curp->next->to;
1147 if ( curp==spl->first || curp==NULL )
1148 break;
1149 }
1150 if ( curp==NULL || !curp->selected )
1151 break;
1152 for ( nextp=curp->next->to; nextp->selected; nextp = nextp->next->to );
1153 /* we don't need to check for the end of the splineset here because */
1154 /* we know that spl->last is not selected */
1155 SplinesRemoveBetween(sc,curp->prev->from,nextp,type);
1156 curp = nextp;
1157 selectme = nextp;
1158 }
1159 if ( selectme!=NULL ) selectme->selected = true;
1160 if ( any )
1161 SplineSetSpirosClear(spl);
1162 return( spl );
1163 }
1164
1165 void SplineCharMerge(SplineChar *sc,SplineSet **head,int type) {
1166 SplineSet *spl, *prev=NULL, *next;
1167
1168 for ( spl = *head; spl!=NULL; spl = next ) {
1169 next = spl->next;
1170 if ( SplinePointListMerge(sc,spl,type)==NULL ) {
1171 if ( prev==NULL )
1172 *head = next;
1173 else
1174 prev->next = next;
1175 chunkfree(spl,sizeof(*spl));
1176 } else
1177 prev = spl;
1178 }
1179 }
1180
1181 static int SPisExtremum(SplinePoint *sp) {
1182 BasePoint *prev, *next;
1183 SplinePoint *psp, *nsp;
1184
1185 if ( sp->prev==NULL || sp->next==NULL )
1186 return( true );
1187
1188 nsp = sp->next->to;
1189 psp = sp->prev->from;
1190
1191 /* A point that changes from curved to straight horizontal/vertical should*/
1192 /* be treated as an extremum */
1193 if (( !sp->next->knownlinear && sp->prev->knownlinear &&
1194 (RealWithin(sp->me.x,sp->prev->from->me.x,.02) ||
1195 RealWithin(sp->me.y,sp->prev->from->me.y,.02))) ||
1196 ( !sp->prev->knownlinear && sp->next->knownlinear &&
1197 (RealWithin(sp->me.x,sp->next->to->me.x,.02) ||
1198 RealWithin(sp->me.y,sp->next->to->me.y,.02))))
1199 return( true );
1200
1201 if ( sp->prev->knownlinear )
1202 prev = &psp->me;
1203 else if ( !sp->noprevcp )
1204 prev = &sp->prevcp;
1205 else
1206 prev = &psp->nextcp;
1207 if ( sp->next->knownlinear )
1208 next = &nsp->me;
1209 else if ( !sp->nonextcp )
1210 next = &sp->nextcp;
1211 else
1212 next = &nsp->prevcp;
1213
1214 if ( sp->next->knownlinear && sp->prev->knownlinear &&
1215 ((sp->me.x==nsp->me.x && sp->me.x==psp->me.x &&
1216 ((sp->me.y<=nsp->me.y && psp->me.y<=sp->me.y) ||
1217 (sp->me.y>=nsp->me.y && psp->me.y>=sp->me.y))) ||
1218 (sp->me.y==nsp->me.y && sp->me.y==psp->me.y &&
1219 ((sp->me.x<=nsp->me.x && psp->me.x<=sp->me.x) ||
1220 (sp->me.x>=nsp->me.x && psp->me.x>=sp->me.x)))) )
1221 return( false ); /* A point in the middle of a horizontal/vertical line */
1222 /* is not an extrema and can be removed */
1223
1224 if ( prev->x==sp->me.x && next->x==sp->me.x ) {
1225 if ( prev->y==sp->me.y && next->y==sp->me.y )
1226 return( false ); /* this should be caught above */
1227 /* no matter what the control points look like this guy is either an */
1228 /* an extremum or a point of inflection, so we don't need to check */
1229 return( true );
1230 } else if ( prev->y==sp->me.y && next->y==sp->me.y ) {
1231 return( true );
1232 } else if (( prev->x<=sp->me.x && next->x<=sp->me.x ) ||
1233 (prev->x>=sp->me.x && next->x>=sp->me.x ))
1234 return( true );
1235 else if (( prev->y<=sp->me.y && next->y<=sp->me.y ) ||
1236 (prev->y>=sp->me.y && next->y>=sp->me.y ))
1237 return( true );
1238
1239 return( false );
1240 }
1241
1242 static bigreal SecondDerivative(Spline *s,bigreal t) {
1243 /* That is d2y/dx2, not d2y/dt2 */
1244
1245 /* dy/dx = (dy/dt) / (dx/dt) */
1246 /* d2 y/dx2 = d(dy/dx)/dt / (dx/dt) */
1247 /* d2 y/dx2 = ((d2y/dt2)*(dx/dt) - (dy/dt)*(d2x/dt2))/ (dx/dt)^2 */
1248
1249 /* dy/dt = 3 ay *t^2 + 2 by * t + cy */
1250 /* dx/dt = 3 ax *t^2 + 2 bx * t + cx */
1251 /* d2y/dt2 = 6 ay *t + 2 by */
1252 /* d2x/dt2 = 6 ax *t + 2 bx */
1253 bigreal dydt = (3*s->splines[1].a*t + 2*s->splines[1].b)*t + s->splines[1].c;
1254 bigreal dxdt = (3*s->splines[0].a*t + 2*s->splines[0].b)*t + s->splines[0].c;
1255 bigreal d2ydt2 = 6*s->splines[1].a*t + 2*s->splines[1].b;
1256 bigreal d2xdt2 = 6*s->splines[0].a*t + 2*s->splines[0].b;
1257 bigreal top = (d2ydt2*dxdt - dydt*d2xdt2);
1258 if ( dxdt==0 ) {
1259 if ( top==0 )
1260 return( 0 );
1261 if ( top>0 )
1262 return( 1e10 );
1263 return( -1e10 );
1264 }
1265
1266 return( top/(dxdt*dxdt) );
1267 }
1268
1269
1270 /* Does the second derivative change sign around this point? If so we should */
1271 /* retain it for truetype */
1272 static int SPisD2Change( SplinePoint *sp ) {
1273 bigreal d2next = SecondDerivative(sp->next,0);
1274 bigreal d2prev = SecondDerivative(sp->prev,1);
1275
1276 if ( d2next>=0 && d2prev>=0 )
1277 return( false );
1278 if ( d2next<=0 && d2prev<=0 )
1279 return( false );
1280
1281 return( true );
1282 }
1283
1284 /* Almost exactly the same as SplinesRemoveBetween, but this one is conditional */
1285 /* the intermediate points/splines are removed only if we have a good match */
1286 /* used for simplify */
1287 static int SplinesRemoveBetweenMaybe(SplineChar *sc,
1288 SplinePoint *from, SplinePoint *to, int flags, bigreal err) {
1289 int i,tot;
1290 SplinePoint *afterfrom, *sp, *next;
1291 FitPoint *fp, *fp2;
1292 BasePoint test;
1293 int good;
1294 BasePoint fncp, tpcp;
1295 int fpt, tpt;
1296 int order2 = from->next->order2;
1297
1298 afterfrom = from->next->to;
1299 fncp = from->nextcp; tpcp = to->prevcp;
1300 fpt = from->pointtype; tpt = to->pointtype;
1301
1302 if ( afterfrom==to || from==to )
1303 return( false );
1304
1305 fp = SplinesFigureFPsBetween(from,to,&tot);
1306 fp2 = malloc((tot+1)*sizeof(FitPoint));
1307 memcpy(fp2,fp,tot*sizeof(FitPoint));
1308
1309 if ( !(flags&sf_ignoreslopes) )
1310 ApproximateSplineFromPointsSlopes(from,to,fp,tot-1,order2);
1311 else {
1312 ApproximateSplineFromPoints(from,to,fp,tot-1,order2);
1313 }
1314
1315 i = tot;
1316
1317 good = true;
1318 while ( --i>0 && good ) {
1319 /* fp[0] is the same as from (easier to include it), but the SplineNear*/
1320 /* routine will sometimes reject the end-points of the spline */
1321 /* so just don't check it */
1322 test.x = fp2[i].p.x; test.y = fp2[i].p.y;
1323 good = SplineNearPoint(from->next,&test,err)!= -1;
1324 }
1325
1326 free(fp);
1327 free(fp2);
1328 if ( good ) {
1329 SplineFree(afterfrom->prev);
1330 for ( sp=afterfrom; sp!=to; sp=next ) {
1331 next = sp->next->to;
1332 SplineFree(sp->next);
1333 SplinePointMDFree(sc,sp);
1334 }
1335 SplinePointCategorize(from);
1336 SplinePointCategorize(to);
1337 } else {
1338 SplineFree(from->next);
1339 from->next = afterfrom->prev;
1340 from->nextcp = fncp;
1341 from->nonextcp = ( fncp.x==from->me.x && fncp.y==from->me.y);
1342 from->pointtype = fpt;
1343 for ( sp=afterfrom; sp->next->to!=to; sp=sp->next->to );
1344 to->prev = sp->next;
1345 to->prevcp = tpcp;
1346 to->noprevcp = ( tpcp.x==to->me.x && tpcp.y==to->me.y);
1347 to->pointtype = tpt;
1348 }
1349 return( good );
1350 }
1351
1352 /* In truetype we can interpolate away an on curve point. Try this */
1353 static int Spline2Interpolate(SplinePoint *mid, bigreal err) {
1354 SplinePoint *from, *to;
1355 BasePoint midme, test;
1356 int i,tot, good;
1357 FitPoint *fp;
1358
1359 midme = mid->me;
1360 from = mid->prev->from; to = mid->next->to;
1361 fp = SplinesFigureFPsBetween(from,to,&tot);
1362
1363 mid->me.x = (mid->prevcp.x + mid->nextcp.x)/2;
1364 mid->me.y = (mid->prevcp.y + mid->nextcp.y)/2;
1365 SplineRefigure(mid->next);
1366 SplineRefigure(mid->prev);
1367
1368 i = tot;
1369 good = true;
1370 while ( --i>0 && good ) {
1371 /* fp[0] is the same as from (easier to include it), but the SplineNear*/
1372 /* routine will sometimes reject the end-points of the spline */
1373 /* so just don't check it */
1374 test.x = fp[i].p.x; test.y = fp[i].p.y;
1375 if ( i>tot/2 )
1376 good = SplineNearPoint(mid->next,&test,err)!= -1 ||
1377 SplineNearPoint(mid->prev,&test,err)!= -1;
1378 else
1379 good = SplineNearPoint(mid->prev,&test,err)!= -1 ||
1380 SplineNearPoint(mid->next,&test,err)!= -1;
1381 }
1382 if ( !good ) {
1383 mid->me = midme;
1384 SplineRefigure(mid->next);
1385 SplineRefigure(mid->prev);
1386 }
1387 free(fp);
1388 return( good );
1389 }
1390
1391 int SPInterpolate(const SplinePoint *sp) {
1392 /* Using truetype rules, can we interpolate this point? */
1393 return( !sp->dontinterpolate && !sp->nonextcp && !sp->noprevcp &&
1394 !sp->roundx && !sp->roundy &&
1395 (RealWithin(sp->me.x,(sp->nextcp.x+sp->prevcp.x)/2,.1) &&
1396 RealWithin(sp->me.y,(sp->nextcp.y+sp->prevcp.y)/2,.1)) );
1397 }
1398
1399 static int _SplinesRemoveMidMaybe(SplineChar *sc,SplinePoint *mid, int flags,
1400 bigreal err, bigreal lenmax2) {
1401 SplinePoint *from, *to;
1402
1403 if ( mid->prev==NULL || mid->next==NULL )
1404 return( false );
1405
1406 from = mid->prev->from; to = mid->next->to;
1407
1408 /* Retain points which are horizontal or vertical, because postscript says*/
1409 /* type1 fonts should always have a point at the extrema (except for small*/
1410 /* things like serifs), and the extrema occur at horizontal/vertical points*/
1411 /* tt says something similar */
1412 if ( !(flags&sf_ignoreextremum) && SPisExtremum(mid) )
1413 return( false );
1414
1415 /* In truetype fonts we also want to retain points where the second */
1416 /* derivative changes sign */
1417 if ( !(flags&sf_ignoreextremum) && mid->prev->order2 && SPisD2Change(mid) )
1418 return( false );
1419
1420 if ( !(flags&sf_mergelines) && (mid->pointtype==pt_corner ||
1421 mid->prev->knownlinear || mid->next->knownlinear) ) {
1422 /* Be very careful about merging straight lines. Generally they should*/
1423 /* remain straight... */
1424 /* Actually it's not that the lines are straight, the significant thing */
1425 /* is that if there is a abrupt change in direction at this point */
1426 /* (a corner) we don't want to get rid of it */
1427 BasePoint prevu, nextu;
1428 bigreal plen, nlen;
1429
1430 if ( mid->next->knownlinear || mid->nonextcp ) {
1431 nextu.x = to->me.x-mid->me.x;
1432 nextu.y = to->me.y-mid->me.y;
1433 } else {
1434 nextu.x = mid->nextcp.x-mid->me.x;
1435 nextu.y = mid->nextcp.y-mid->me.y;
1436 }
1437 if ( mid->prev->knownlinear || mid->noprevcp ) {
1438 prevu.x = from->me.x-mid->me.x;
1439 prevu.y = from->me.y-mid->me.y;
1440 } else {
1441 prevu.x = mid->prevcp.x-mid->me.x;
1442 prevu.y = mid->prevcp.y-mid->me.y;
1443 }
1444 nlen = sqrt(nextu.x*nextu.x + nextu.y*nextu.y);
1445 plen = sqrt(prevu.x*prevu.x + prevu.y*prevu.y);
1446 if ( nlen==0 || plen==0 )
1447 /* Not a real corner */;
1448 else if ( (nextu.x*prevu.x + nextu.y*prevu.y)/(nlen*plen)>((nlen+plen>20)?-.98:-.95) ) {
1449 /* If the cos if the angle between the two segments is too far */
1450 /* from parallel then don't try to smooth the point into oblivion */
1451 bigreal flen, tlen;
1452 flen = (from->me.x-mid->me.x)*(from->me.x-mid->me.x) +
1453 (from->me.y-mid->me.y)*(from->me.y-mid->me.y);
1454 tlen = (to->me.x-mid->me.x)*(to->me.x-mid->me.x) +
1455 (to->me.y-mid->me.y)*(to->me.y-mid->me.y);
1456 if ( (flen<.7 && tlen<.7) || flen<.25 || tlen<.25 )
1457 /* Too short to matter */;
1458 else
1459 return( false );
1460 }
1461
1462 if ( mid->prev->knownlinear && mid->next->knownlinear ) {
1463 /* Special checks for horizontal/vertical lines */
1464 /* don't let the smoothing distort them */
1465 if ( from->me.x==to->me.x ) {
1466 if ( mid->me.x!=to->me.x )
1467 return( false );
1468 } else if ( from->me.y==to->me.y ) {
1469 if ( mid->me.y!=to->me.y )
1470 return( false );
1471 } else if ( !RealRatio((from->me.y-to->me.y)/(from->me.x-to->me.x),
1472 (mid->me.y-to->me.y)/(mid->me.x-to->me.x),
1473 .05) ) {
1474 return( false );
1475 }
1476 } else if ( mid->prev->knownlinear ) {
1477 if ( (mid->me.x-from->me.x)*(mid->me.x-from->me.x) + (mid->me.y-from->me.y)*(mid->me.y-from->me.y)
1478 > lenmax2 )
1479 return( false );
1480 } else {
1481 if ( (mid->me.x-to->me.x)*(mid->me.x-to->me.x) + (mid->me.y-to->me.y)*(mid->me.y-to->me.y)
1482 > lenmax2 )
1483 return( false );
1484 }
1485 }
1486
1487 if ( mid->next->order2 ) {
1488 if ( SPInterpolate(from) && SPInterpolate(to) && SPInterpolate(mid))
1489 return( false );
1490 }
1491
1492 return ( SplinesRemoveBetweenMaybe(sc,from,to,flags,err));
1493 }
1494
1495 /* A wrapper to SplinesRemoveBetweenMaybe to handle some extra checking for a */
1496 /* common case */
1497 static int SplinesRemoveMidMaybe(SplineChar *sc,SplinePoint *mid, int flags,
1498 bigreal err, bigreal lenmax2) {
1499 int changed1 = false;
1500 if ( mid->next->order2 ) {
1501 if ( !mid->dontinterpolate && !mid->nonextcp && !mid->noprevcp &&
1502 !(RealWithin(mid->me.x,(mid->nextcp.x+mid->prevcp.x)/2,.1) &&
1503 RealWithin(mid->me.y,(mid->nextcp.y+mid->prevcp.y)/2,.1)) )
1504 changed1 = Spline2Interpolate(mid,err);
1505 }
1506 return( _SplinesRemoveMidMaybe(sc,mid,flags,err,lenmax2) || changed1 );
1507 }
1508
1509 void SPLNearlyHvCps(SplineChar *sc,SplineSet *ss,bigreal err) {
1510 Spline *s, *first=NULL;
1511 int refresh;
1512 SplinePoint *from, *to;
1513
1514 for ( s = ss->first->next; s!=NULL && s!=first; s=s->to->next ) {
1515 if ( first==NULL ) first = s;
1516 refresh = false;
1517 from = s->from; to = s->to;
1518 if ( !from->nonextcp && from->nextcp.x-from->me.x<err && from->nextcp.x-from->me.x>-err ) {
1519 from->nextcp.x = from->me.x;
1520 if ( s->order2 ) to->prevcp = from->nextcp;
1521 if ( from->nextcp.y==from->me.y ) from->nonextcp = true;
1522 refresh = true;
1523 } else if ( !from->nonextcp && from->nextcp.y-from->me.y<err && from->nextcp.y-from->me.y>-err ) {
1524 from->nextcp.y = from->me.y;
1525 if ( s->order2 ) to->prevcp = from->nextcp;
1526 if ( from->nextcp.x==from->me.x ) from->nonextcp = true;
1527 refresh = true;
1528 }
1529 if ( !to->noprevcp && to->prevcp.x-to->me.x<err && to->prevcp.x-to->me.x>-err ) {
1530 to->prevcp.x = to->me.x;
1531 if ( s->order2 ) from->nextcp = to->prevcp;
1532 if ( to->prevcp.y==to->me.y ) to->noprevcp = true;
1533 refresh = true;
1534 } else if ( !to->noprevcp && to->prevcp.y-to->me.y<err && to->prevcp.y-to->me.y>-err ) {
1535 to->prevcp.y = to->me.y;
1536 if ( s->order2 ) from->nextcp = to->prevcp;
1537 if ( to->prevcp.x==to->me.x ) to->noprevcp = true;
1538 refresh = true;
1539 }
1540 if ( refresh )
1541 SplineRefigure(s);
1542 }
1543 }
1544
1545 void SPLNearlyHvLines(SplineChar *sc,SplineSet *ss,bigreal err) {
1546 Spline *s, *first=NULL;
1547
1548 for ( s = ss->first->next; s!=NULL && s!=first; s=s->to->next ) {
1549 if ( first==NULL ) first = s;
1550 if ( s->knownlinear ) {
1551 if ( s->to->me.x-s->from->me.x<err && s->to->me.x-s->from->me.x>-err ) {
1552 s->to->nextcp.x += (s->from->me.x-s->to->me.x);
1553 if ( s->order2 && s->to->next!=NULL )
1554 s->to->next->to->prevcp.x = s->to->nextcp.x;
1555 s->to->me.x = s->from->me.x;
1556 s->to->prevcp = s->to->me;
1557 s->from->nextcp = s->from->me;
1558 s->from->nonextcp = s->to->noprevcp = true;
1559 SplineRefigure(s);
1560 if ( s->to->next != NULL )
1561 SplineRefigure(s->to->next);
1562 } else if ( s->to->me.y-s->from->me.y<err && s->to->me.y-s->from->me.y>-err ) {
1563 s->to->nextcp.y += (s->from->me.y-s->to->me.y);
1564 if ( s->order2 && s->to->next!=NULL )
1565 s->to->next->to->prevcp.y = s->to->nextcp.y;
1566 s->to->me.y = s->from->me.y;
1567 s->to->prevcp = s->to->me;
1568 s->from->nextcp = s->from->me;
1569 s->from->nonextcp = s->to->noprevcp = true;
1570 SplineRefigure(s);
1571 if ( s->to->next != NULL )
1572 SplineRefigure(s->to->next);
1573 }
1574 }
1575 }
1576 }
1577
1578 /* The older check below is based on an absolute distance
1579 * and is therefore magnification-relative. This one is
1580 * (more or less) hull-based with a ratio of 1000 visually
1581 * verified at multiple magnifications.
1582 */
1583 int SplineIsLinearish(Spline *spline) {
1584 int i;
1585 real dmax = 0, dtmp, ldx, ldy, ln;
1586 BasePoint *sp, *ep, *cp;
1587
1588 if ( SplineIsLinear(spline) )
1589 return 1;
1590
1591 sp = &spline->from->me;
1592 ep = &spline->to->me;
1593 ldx = ep->x - sp->x;
1594 ldy = ep->y - sp->y;
1595 ln = sqrt(ldy*ldy + ldx*ldx);
1596
1597 for (i = 0; i < 2; ++i) {
1598 if ( i==0 )
1599 cp = &spline->from->nextcp;
1600 else
1601 cp = &spline->to->prevcp;
1602 dtmp = fabs(ldy*cp->x - ldx*cp->y + ep->x*sp->y - ep->y*sp->x)/ln;
1603 if (dtmp > dmax)
1604 dmax = dtmp;
1605 }
1606 return ( ln/dmax >= 1000 );
1607 }
1608
1609 /* Does this spline deviate from a straight line between its endpoints by more*/
1610 /* than err? */
1611 /* Rotate the spline so that the line between the endpoints is horizontal, */
1612 /* then find the maxima/minima of the y spline (this is the deviation) */
1613 /* check that that is less than err */
1614 static int SplineCloseToLinear(Spline *s, bigreal err) {
1615 bigreal angle;
1616 extended co,si, t1, t2, y;
1617 SplinePoint from, to;
1618 Spline sp;
1619 BasePoint bp;
1620
1621 from = *s->from; to = *s->to;
1622 to.me.x -= from.me.x; to.me.y -= from.me.y;
1623 to.prevcp.x -= from.me.x; to.prevcp.y -= from.me.y;
1624 from.nextcp.x -= from.me.x ; from.nextcp.y -= from.me.y;
1625 from.me.x = from.me.y = 0;
1626 angle = atan2(to.me.y, to.me.x);
1627
1628 si = sin(angle); co = cos(angle);
1629 bp.x = to.me.x*co + to.me.y*si;
1630 bp.y = -to.me.x*si + to.me.y*co;
1631 to.me = bp;
1632
1633 bp.x = to.prevcp.x*co + to.prevcp.y*si;
1634 bp.y = -to.prevcp.x*si + to.prevcp.y*co;
1635 to.prevcp = bp;
1636
1637 bp.x = from.nextcp.x*co + from.nextcp.y*si;
1638 bp.y = -from.nextcp.x*si + from.nextcp.y*co;
1639 from.nextcp = bp;
1640
1641 memset(&sp,0,sizeof(Spline));
1642 sp.from = &from; sp.to = &to;
1643 sp.order2 = s->order2;
1644 SplineRefigure(&sp);
1645 SplineFindExtrema(&sp.splines[1],&t1,&t2);
1646
1647 if ( t1==-1 )
1648 return( true );
1649
1650 y = ((sp.splines[1].a*t1 + sp.splines[1].b)*t1 + sp.splines[1].c)*t1 + sp.splines[1].d;
1651 if ( y>err || y<-err )
1652 return( false );
1653
1654 if ( t2==-1 )
1655 return( true );
1656 y = ((sp.splines[1].a*t2 + sp.splines[1].b)*t2 + sp.splines[1].c)*t2 + sp.splines[1].d;
1657 return( y<=err && y>=-err );
1658 }
1659
1660 int SPLNearlyLines(SplineChar *sc,SplineSet *ss,bigreal err) {
1661 Spline *s, *first=NULL;
1662 int changed = false;
1663
1664 for ( s = ss->first->next; s!=NULL && s!=first; s=s->to->next ) {
1665 if ( first==NULL ) first = s;
1666 if ( s->islinear )
1667 /* Nothing to be done */;
1668 else if ( s->knownlinear || SplineCloseToLinear(s,err)) {
1669 s->from->nextcp = s->from->me;
1670 s->from->nonextcp = true;
1671 s->to->prevcp = s->to->me;
1672 s->to->noprevcp = true;
1673 SplineRefigure(s);
1674 changed = true;
1675 }
1676 }
1677 return( changed );
1678 }
1679
1680 static void SPLForceLines(SplineChar *sc,SplineSet *ss,bigreal bump_size) {
1681 Spline *s, *first=NULL;
1682 SplinePoint *sp;
1683 int any;
1684 BasePoint unit;
1685 bigreal len, minlen = sc==NULL ? 50.0 : (sc->parent->ascent+sc->parent->descent)/20.0;
1686 bigreal diff, xoff, yoff, len2;
1687 int order2=false;
1688
1689 if ( ss->first->next!=NULL && ss->first->next->order2 )
1690 order2 = true;
1691
1692 for ( s = ss->first->next; s!=NULL && s!=first; s=s->to->next ) {
1693 if ( first==NULL ) first = s;
1694 if ( s->knownlinear ) {
1695 unit.x = s->to->me.x-s->from->me.x;
1696 unit.y = s->to->me.y-s->from->me.y;
1697 len = sqrt(unit.x*unit.x + unit.y*unit.y);
1698 if ( len<minlen )
1699 continue;
1700 unit.x /= len; unit.y /= len;
1701 do {
1702 any = false;
1703 if ( s->from->prev!=NULL && s->from->prev!=s ) {
1704 sp = s->from->prev->from;
1705 len2 = sqrt((sp->me.x-s->from->me.x)*(sp->me.x-s->from->me.x) + (sp->me.y-s->from->me.y)*(sp->me.y-s->from->me.y));
1706 diff = (sp->me.x-s->from->me.x)*unit.y - (sp->me.y-s->from->me.y)*unit.x;
1707 if ( len2<len && fabs(diff)<=bump_size ) {
1708 xoff = diff*unit.y; yoff = -diff*unit.x;
1709 sp->me.x -= xoff; sp->me.y -= yoff;
1710 sp->prevcp.x -= xoff; sp->prevcp.y -= yoff;
1711 if ( order2 && sp->prev!=NULL && !sp->noprevcp )
1712 sp->prev->from->nextcp = sp->prevcp;
1713 sp->nextcp = sp->me; sp->nonextcp = true;
1714 if ( sp->next==first ) first = NULL;
1715 SplineFree(sp->next);
1716 if ( s->from==ss->first ) {
1717 if ( ss->first==ss->last ) ss->last = sp;
1718 ss->first = sp;
1719 ss->start_offset = 0;
1720 }
1721 SplinePointMDFree(sc,s->from);
1722 sp->next = s; s->from = sp;
1723 SplineRefigure(s);
1724 if ( sp->prev!=NULL )
1725 SplineRefigure(sp->prev);
1726 sp->pointtype = pt_corner;
1727 any = true;
1728
1729 /* We must recalculate the length each time, we */
1730 /* might have shortened it. */
1731 unit.x = s->to->me.x-s->from->me.x;
1732 unit.y = s->to->me.y-s->from->me.y;
1733 len = sqrt(unit.x*unit.x + unit.y*unit.y);
1734 if ( len<minlen )
1735 break;
1736 unit.x /= len; unit.y /= len;
1737 }
1738 }
1739 if ( s->to->next!=NULL && s->to->next!=s ) {
1740 sp = s->to->next->to;
1741 /* If the next spline is a longer line than we are, then don't */
1742 /* merge it to us, rather merge us into it next time through the loop */
1743 /* Hmm. Don't merge out the bump in general if the "bump" is longer than we are */
1744 len2 = sqrt((sp->me.x-s->to->me.x)*(sp->me.x-s->to->me.x) + (sp->me.y-s->to->me.y)*(sp->me.y-s->to->me.y));
1745 diff = (sp->me.x-s->to->me.x)*unit.y - (sp->me.y-s->to->me.y)*unit.x;
1746 if ( len2<len && fabs(diff)<=bump_size ) {
1747 xoff = diff*unit.y; yoff = -diff*unit.x;
1748 sp->me.x -= xoff; sp->me.y -= yoff;
1749 sp->nextcp.x -= xoff; sp->nextcp.y -= yoff;
1750 if ( order2 && sp->next!=NULL && !sp->nonextcp )
1751 sp->next->to->prevcp = sp->nextcp;
1752 sp->prevcp = sp->me; sp->noprevcp = true;
1753 if ( sp->prev==first ) first = NULL;
1754 SplineFree(sp->prev);
1755 if ( s->to==ss->last ) {
1756 if ( ss->first==ss->last ) {
1757 ss->first = sp;
1758 ss->start_offset = 0;
1759 }
1760 ss->last = sp;
1761 }
1762 SplinePointMDFree(sc,s->to);
1763 sp->prev = s; s->to = sp;
1764 SplineRefigure(s);
1765 if ( sp->next!=NULL )
1766 SplineRefigure(sp->next);
1767 sp->pointtype = pt_corner;
1768 any = true;
1769
1770 unit.x = s->to->me.x-s->from->me.x;
1771 unit.y = s->to->me.y-s->from->me.y;
1772 len = sqrt(unit.x*unit.x + unit.y*unit.y);
1773 if ( len<minlen )
1774 break;
1775 unit.x /= len; unit.y /= len;
1776 }
1777 }
1778 } while ( any );
1779 }
1780 }
1781 }
1782
1783 static int SPLSmoothControlPoints(SplineSet *ss,bigreal tan_bounds,int vert_check) {
1784 SplinePoint *sp;
1785 /* If a point has control points, and if those cps are in nearly the same */
1786 /* direction (within tan_bounds) then adjust them so that they are in the*/
1787 /* same direction */
1788 BasePoint unit, unit2;
1789 bigreal len, len2, para, norm, tn;
1790 int changed=false, found;
1791
1792 if ( ss->first->next!=NULL && ss->first->next->order2 )
1793 return( false );
1794
1795 for ( sp = ss->first; ; ) {
1796 if (( !sp->nonextcp && !sp->noprevcp && sp->pointtype==pt_corner ) ||
1797 ((sp->pointtype==pt_corner || sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve) &&
1798 (( !sp->nonextcp && sp->noprevcp && sp->prev!=NULL && sp->prev->knownlinear ) ||
1799 ( !sp->noprevcp && sp->nonextcp && sp->next!=NULL && sp->next->knownlinear )))) {
1800 BasePoint *next = sp->nonextcp ? &sp->next->to->me : &sp->nextcp;
1801 BasePoint *prev = sp->noprevcp ? &sp->prev->to->me : &sp->prevcp;
1802 unit.x = next->x-sp->me.x;
1803 unit.y = next->y-sp->me.y;
1804 len = sqrt(unit.x*unit.x + unit.y*unit.y);
1805 unit.x /= len; unit.y /= len;
1806 para = (sp->me.x-prev->x)*unit.x + (sp->me.y-prev->y)*unit.y;
1807 norm = (sp->me.x-prev->x)*unit.y - (sp->me.y-prev->y)*unit.x;
1808 if ( para==0 )
1809 tn = 1000;
1810 else
1811 tn = norm/para;
1812 if ( tn<0 ) tn = -tn;
1813 if ( tn<tan_bounds && para>0 ) {
1814 found = 0;
1815 unit2.x = sp->me.x-sp->prevcp.x;
1816 unit2.y = sp->me.y-sp->prevcp.y;
1817 len2 = sqrt(unit2.x*unit2.x + unit2.y*unit2.y);
1818 unit2.x /= len2; unit2.y /= len2;
1819 if ( vert_check ) {
1820 if ( fabs(unit.x)>fabs(unit.y) ) {
1821 /* Closer to horizontal */
1822 if ( (unit.y<=0 && unit2.y>=0) || (unit.y>=0 && unit2.y<=0) ) {
1823 unit2.x = unit2.x<0 ? -1 : 1; unit2.y = 0;
1824 found = 1;
1825 }
1826 } else {
1827 if ( (unit.x<=0 && unit2.x>=0) || (unit.x>=0 && unit2.x<=0) ) {
1828 unit2.y = unit2.y<0 ? -1 : 1; unit2.x = 0;
1829 found = 1;
1830 }
1831 }
1832 }
1833 /* If we're next to a line, we must extend the line. No choice */
1834 if ( sp->nonextcp ) {
1835 if ( len<len2 )
1836 goto nextpt;
1837 found = true;
1838 unit2 = unit;
1839 } else if ( sp->noprevcp ) {
1840 if ( len2<len )
1841 goto nextpt;
1842 found = true;
1843 } else if ( !found ) {
1844 unit2.x = (unit.x*len + unit2.x*len2)/(len+len2);
1845 unit2.y = (unit.y*len + unit2.y*len2)/(len+len2);
1846 }
1847 sp->nextcp.x = sp->me.x + len*unit2.x;
1848 sp->nextcp.y = sp->me.y + len*unit2.y;
1849 sp->prevcp.x = sp->me.x - len2*unit2.x;
1850 sp->prevcp.y = sp->me.y - len2*unit2.y;
1851 sp->pointtype = pt_curve;
1852 if ( sp->prev )
1853 SplineRefigure(sp->prev);
1854 if ( sp->next )
1855 SplineRefigure(sp->next);
1856 changed = true;
1857 }
1858 }
1859 nextpt:
1860 if ( sp->next==NULL )
1861 break;
1862 sp = sp->next->to;
1863 if ( sp==ss->first )
1864 break;
1865 }
1866 return( changed );
1867 }
1868
1869 static void GetNextUnitVector(SplinePoint *sp,BasePoint *uv) {
1870 bigreal len;
1871
1872 if ( sp->next==NULL ) {
1873 uv->x = uv->y = 0;
1874 } else if ( sp->next->knownlinear ) {
1875 uv->x = sp->next->to->me.x - sp->me.x;
1876 uv->y = sp->next->to->me.y - sp->me.y;
1877 } else if ( sp->nonextcp ) {
1878 uv->x = sp->next->to->prevcp.x - sp->me.x;
1879 uv->y = sp->next->to->prevcp.y - sp->me.y;
1880 } else {
1881 uv->x = sp->nextcp.x - sp->me.x;
1882 uv->y = sp->nextcp.y - sp->me.y;
1883 }
1884 len = sqrt(uv->x*uv->x + uv->y*uv->y );
1885 if ( len!= 0 ) {
1886 uv->x /= len;
1887 uv->y /= len;
1888 }
1889 }
1890
1891 static int isExtreme(SplinePoint *sp) {
1892 if ( sp->next==NULL || sp->prev==NULL )
1893 return( 2 ); /* End point. Always extreme */
1894 if ( sp->nonextcp ) {
1895 if ( !sp->next->knownlinear )
1896 return( false );
1897 if ( sp->next->to->me.x == sp->me.x || sp->next->to->me.y == sp->me.y )
1898 /* Ok, horizontal or vertical line, that'll do */;
1899 else
1900 return( false );
1901 } else {
1902 if ( sp->nextcp.x != sp->me.x && sp->nextcp.y != sp->me.y )
1903 return( false );
1904 }
1905 if ( sp->noprevcp ) {
1906 if ( !sp->prev->knownlinear )
1907 return( false );
1908 if ( sp->prev->from->me.x == sp->me.x || sp->prev->from->me.y == sp->me.y )
1909 /* Ok, horizontal or vertical line, that'll do */;
1910 else
1911 return( false );
1912 } else {
1913 if ( sp->prevcp.x != sp->me.x && sp->prevcp.y != sp->me.y )
1914 return( false );
1915 }
1916 return( true );
1917 }
1918
1919 /* If the start point of a contour is not at an extremum, and the contour has */
1920 /* a point which is at an extremum, then make the start point be that point */
1921 /* leave it unchanged if start point is already extreme, or no extreme point */
1922 /* could be found */
1923 static void SPLStartToExtremum(SplineChar *sc,SplinePointList *spl) {
1924 SplinePoint *sp;
1925
1926 while ( spl!=NULL ) {
1927 if ( spl->first==spl->last ) { /* It's closed */
1928 for ( sp=spl->first; !isExtreme(sp); ) {
1929 sp = sp->next->to;
1930 if ( sp==spl->first )
1931 break;
1932 }
1933 if ( sp!=spl->first ) {
1934 spl->first = spl->last = sp;
1935 spl->start_offset = 0;
1936 }
1937 }
1938 spl = spl->next;
1939 }
1940 }
1941
1942 /* Cleanup just turns splines with control points which happen to trace out */
1943 /* lines into simple lines */
1944 /* it also checks for really nasty control points which point in the wrong */
1945 /* direction but are very close to the base point. We get these from some */
1946 /* TeX fonts. I assume they are due to rounding errors (or just errors) in*/
1947 /* some autotracer */
1948 void SplinePointListSimplify(SplineChar *sc,SplinePointList *spl,
1949 struct simplifyinfo *smpl) {
1950 SplinePoint *first, *next, *sp, *nsp;
1951 BasePoint suv, nuv;
1952 bigreal lenmax2 = smpl->linelenmax*smpl->linelenmax;
1953
1954 if ( spl==NULL )
1955 return;
1956
1957 RemoveZeroLengthSplines(spl,false,0.1);
1958 RemoveStupidControlPoints(spl);
1959 SSRemoveBacktracks(spl);
1960 if ( smpl->flags!=sf_cleanup && (smpl->flags&sf_setstart2extremum))
1961 SPLStartToExtremum(sc,spl);
1962 if ( spl->first->next!=NULL && spl->first->next->to==spl->first &&
1963 spl->first->nonextcp && spl->first->noprevcp )
1964 return; /* Ignore any splines which are just dots */
1965
1966 if ( smpl->flags!=sf_cleanup && (smpl->flags&sf_forcelines)) {
1967 SPLNearlyHvLines(sc,spl,smpl->linefixup);
1968 SPLForceLines(sc,spl,smpl->linefixup);
1969 }
1970
1971 if ( smpl->flags!=sf_cleanup && spl->first->prev!=NULL && spl->first->prev!=spl->first->next ) {
1972 /* first thing to try is to remove everything between two extrema */
1973 /* We do this even if they checked ignore extrema. After this pass */
1974 /* we'll come back and check every point individually */
1975 /* However, if we turn through more than 90 degrees we can't approximate */
1976 /* a good match, and it takes us forever to make the attempt and fail*/
1977 /* We take a dot product to prevent that */
1978 for ( sp = spl->first; ; ) {
1979 if ( sp->next==NULL )
1980 break;
1981 if ( SPisExtremum(sp) ) {
1982 GetNextUnitVector(sp,&suv);
1983 for ( nsp=sp->next->to; nsp!=sp; nsp = nsp->next->to ) {
1984 if ( nsp->next==NULL )
1985 break;
1986 if ( nsp->prev->knownlinear &&
1987 (nsp->me.x-nsp->prev->from->me.x)*(nsp->me.x-nsp->prev->from->me.x) +
1988 (nsp->me.y-nsp->prev->from->me.y)*(nsp->me.y-nsp->prev->from->me.y)
1989 >= lenmax2 )
1990 goto nogood;
1991 GetNextUnitVector(nsp,&nuv);
1992 if ( suv.x*nuv.x + suv.y*nuv.y < 0 ) {
1993 if ( suv.x*nuv.x + suv.y*nuv.y > -.1 )
1994 break;
1995 goto nogood;
1996 }
1997 if ( SPisExtremum(nsp) || nsp==spl->first)
1998 break;
1999 }
2000 /* nsp is something we don't want to remove */
2001 if ( nsp==sp )
2002 break;
2003 else if ( sp->next->to == nsp )
2004 goto nogood; /* Nothing to remove */
2005 if ( SplinesRemoveBetweenMaybe(sc,sp,nsp,smpl->flags,smpl->err)) {
2006 if ( spl->last==spl->first ) {
2007 spl->last = spl->first = sp; /* We know this point didn't get removed */
2008 spl->start_offset = 0;
2009 }
2010 }
2011 nogood:
2012 sp = nsp;
2013 } else
2014 sp = sp->next->to;
2015 if ( sp == spl->first )
2016 break;
2017 }
2018
2019 while ( 1 ) {
2020 first = spl->first->prev->from;
2021 if ( first->prev == first->next )
2022 return;
2023 if ( !SplinesRemoveMidMaybe(sc,spl->first,smpl->flags,smpl->err,lenmax2))
2024 break;
2025 if ( spl->first==spl->last )
2026 spl->last = first;
2027 spl->first = first;
2028 spl->start_offset = 0;
2029 }
2030 }
2031
2032 /* Special case checks for paths containing only one point */
2033 /* else we get lots of nans (or only two points) */
2034 if ( spl->first->next == NULL )
2035 return;
2036 for ( sp = spl->first->next->to; sp->next!=NULL; sp = next ) {
2037 SplineIsLinearMake(sp->prev); /* First see if we can turn it*/
2038 /* into a line, then try to merge two splines */
2039 next = sp->next->to;
2040 if ( sp->prev == sp->next ||
2041 (sp->next!=NULL && sp->next->to->next!=NULL &&
2042 sp->next->to->next->to == sp ))
2043 return;
2044 if ( smpl->flags!=sf_cleanup ) {
2045 if ( SplinesRemoveMidMaybe(sc,sp,smpl->flags,smpl->err,lenmax2) ) {
2046 if ( spl->first==sp ) {
2047 spl->first = next;
2048 spl->start_offset = 0;
2049 }
2050 if ( spl->last==sp )
2051 spl->last = next;
2052 continue;
2053 }
2054 } else {
2055 while ( sp->me.x==next->me.x && sp->me.y==next->me.y &&
2056 sp->nextcp.x>sp->me.x-1 && sp->nextcp.x<sp->me.x+1 &&
2057 sp->nextcp.y>sp->me.y-1 && sp->nextcp.y<sp->me.y+1 &&
2058 next->prevcp.x>next->me.x-1 && next->prevcp.x<next->me.x+1 &&
2059 next->prevcp.y>next->me.y-1 && next->prevcp.y<next->me.y+1 ) {
2060 SplineFree(sp->next);
2061 sp->next = next->next;
2062 if ( sp->next!=NULL )
2063 sp->next->from = sp;
2064 sp->nextcp = next->nextcp;
2065 sp->nonextcp = next->nonextcp;
2066 sp->nextcpdef = next->nextcpdef;
2067 SplinePointMDFree(sc,next);
2068 if ( sp->next!=NULL )
2069 next = sp->next->to;
2070 else {
2071 next = NULL;
2072 break;
2073 }
2074 }
2075 if ( next==NULL )
2076 break;
2077 }
2078 if ( next->prev!=NULL && next->prev->from==spl->last )
2079 break;
2080 }
2081 if ( smpl->flags!=sf_cleanup && (smpl->flags&sf_smoothcurves))
2082 SPLSmoothControlPoints(spl,smpl->tan_bounds,smpl->flags&sf_choosehv);
2083 }
2084
2085 /* cleanup may be: -1 => lines become lines, 0 => simplify & retain slopes, 1=> simplify and discard slopes, 2=>discard extrema */
2086 SplineSet *SplineCharSimplify(SplineChar *sc,SplineSet *head,
2087 struct simplifyinfo *smpl) {
2088 SplineSet *spl, *prev, *snext;
2089 int anysel=0, wassingleton;
2090
2091 if ( smpl->check_selected_contours ) {
2092 for ( spl = head; spl!=NULL && !anysel; spl = spl->next ) {
2093 anysel = PointListIsSelected(spl);
2094 }
2095 }
2096
2097 prev = NULL;
2098 for ( spl = head; spl!=NULL; spl = snext ) {
2099 snext = spl->next;
2100 if ( !anysel || PointListIsSelected(spl)) {
2101 wassingleton = spl->first->prev==spl->first->next &&
2102 (spl->first->prev==NULL ||
2103 (spl->first->noprevcp && spl->first->nonextcp));
2104 SplinePointListSimplify(sc,spl,smpl);
2105 /* remove any singleton points */
2106 if (( !wassingleton ||
2107 (smpl->flags!=sf_cleanup && (smpl->flags&sf_rmsingletonpoints))) &&
2108 spl->first->prev==spl->first->next &&
2109 (spl->first->prev==NULL ||
2110 (spl->first->noprevcp && spl->first->nonextcp))) {
2111 if ( prev==NULL )
2112 head = snext;
2113 else
2114 prev->next = snext;
2115 spl->next = NULL;
2116 SplinePointListMDFree(sc,spl);
2117 } else
2118 prev = spl;
2119 }
2120 }
2121 SplineSetsRemoveAnnoyingExtrema(head,.3);
2122 SPLCategorizePoints(head);
2123 /* printf( "nocnt=%d totcnt=%d curdif=%d incr=%d\n", nocnt_cnt, totcnt_cnt, curdiff_cnt, incr_cnt ); */ /* Debug!!! */
2124 return( head );
2125 }
2126
2127 /* If the start point of a contour to be the left most point on it. If there */
2128 /* are several points with that same value, use the one closest to the base */
2129 /* line */
2130 void SPLStartToLeftmost(SplineChar *sc,SplinePointList *spl, int *changed) {
2131 SplinePoint *sp;
2132 SplinePoint *best;
2133
2134 if ( spl->first==spl->last ) { /* It's closed */
2135 best = spl->first;
2136 for ( sp=spl->first; ; ) {
2137 if ( sp->me.x < best->me.x ||
2138 (sp->me.x==best->me.x && (fabs(sp->me.y)<fabs(best->me.y))) )
2139 best = sp;
2140 if ( sp->next==NULL )
2141 break;
2142 sp = sp->next->to;
2143 if ( sp==spl->first )
2144 break;
2145 }
2146 if ( best!=spl->first ) {
2147 if ( !*changed ) {
2148 SCPreserveState(sc,false);
2149 *changed = true;
2150 }
2151 SplineSetSpirosClear(spl);
2152 spl->first = spl->last = best;
2153 spl->start_offset = 0;
2154 }
2155 }
2156 }
2157
2158 void SPLsStartToLeftmost(SplineChar *sc,int layer) {
2159 int changed = 0;
2160 SplineSet *ss;
2161
2162 if ( sc==NULL )
2163 return;
2164
2165 if ( sc->parent->multilayer ) {
2166 for ( layer=ly_fore; layer<sc->layer_cnt; ++layer ) {
2167 for ( ss = sc->layers[layer].splines; ss!=NULL; ss=ss->next )
2168 SPLStartToLeftmost(sc,ss,&changed);
2169 }
2170 if ( changed )
2171 SCCharChangedUpdate(sc,ly_all);
2172 } else {
2173 for ( ss = sc->layers[layer].splines; ss!=NULL; ss=ss->next )
2174 SPLStartToLeftmost(sc,ss,&changed);
2175 if ( changed )
2176 SCCharChangedUpdate(sc,layer);
2177 }
2178 }
2179
2180 struct contourinfo {
2181 SplineSet *ss;
2182 BasePoint *min;
2183 };
2184
2185 static int order_contours(const void *_c1, const void *_c2) {
2186 const struct contourinfo *c1 = _c1, *c2 = _c2;
2187
2188 if ( c1->min->x<c2->min->x )
2189 return( -1 );
2190 else if ( c1->min->x>c2->min->x )
2191 return( 1 );
2192 else if ( fabs(c1->min->y)<fabs(c2->min->y) )
2193 return( -1 );
2194 else if ( fabs(c1->min->y)>fabs(c2->min->y) )
2195 return( 1 );
2196 else
2197 return( 0 );
2198 }
2199
2200 void CanonicalContours(SplineChar *sc,int layer) {
2201 int changed;
2202 SplineSet *ss;
2203 SplinePoint *sp, *best;
2204 int contour_cnt, contour_max=0, i, diff;
2205 struct contourinfo *ci;
2206
2207 if ( sc==NULL )
2208 return;
2209
2210 for ( layer=ly_fore; layer<sc->layer_cnt; ++layer ) {
2211 contour_cnt = 0;
2212 for ( ss = sc->layers[layer].splines; ss!=NULL; ss=ss->next )
2213 ++contour_cnt;
2214 if ( contour_cnt>contour_max )
2215 contour_max = contour_cnt;
2216 }
2217
2218 if ( contour_max<=1 ) /* Can't be out of order */
2219 return;
2220
2221 changed = 0;
2222 ci = calloc(contour_max,sizeof(struct contourinfo));
2223 for ( layer=ly_fore; layer<sc->layer_cnt; ++layer ) {
2224 contour_cnt = 0;
2225 for ( ss = sc->layers[layer].splines; ss!=NULL; ss=ss->next ) {
2226 best = ss->first;
2227 for ( sp=ss->first; ; ) {
2228 if ( sp->me.x < best->me.x ||
2229 (sp->me.x==best->me.x && (fabs(sp->me.y)<fabs(best->me.y))) )
2230 best = sp;
2231 if ( sp->next==NULL )
2232 break;
2233 sp = sp->next->to;
2234 if ( sp==ss->first )
2235 break;
2236 }
2237 ci[contour_cnt].ss = ss;
2238 ci[contour_cnt++].min = &best->me;
2239 }
2240 qsort(ci,contour_cnt,sizeof(struct contourinfo),order_contours);
2241 diff = 0;
2242 for ( i=0, ss = sc->layers[layer].splines; ss!=NULL; ss=ss->next ) {
2243 if ( ci[i].ss != ss ) {
2244 diff = true;
2245 break;
2246 }
2247 }
2248 if ( diff && !changed ) {
2249 SCPreserveLayer(sc,layer,false);
2250 changed = true;
2251 }
2252 if ( diff ) {
2253 sc->layers[layer].splines = ci[0].ss;
2254 for ( i=1; i<contour_cnt; ++i )
2255 ci[i-1].ss->next = ci[i].ss;
2256 ci[contour_cnt-1].ss->next = NULL;
2257 }
2258 }
2259 free(ci);
2260 if ( changed )
2261 SCCharChangedUpdate(sc,ly_all);
2262 }
2263
2264 void SplineSetJoinCpFixup(SplinePoint *sp) {
2265 BasePoint ndir, pdir;
2266 bigreal nlen, plen;
2267 int fixprev=0, fixnext=0;
2268
2269 if ( sp->pointtype == pt_corner )
2270 /* Leave control points as they are */;
2271 else if ( sp->pointtype == pt_tangent ) {
2272 SplineCharTangentNextCP(sp);
2273 SplineCharTangentPrevCP(sp);
2274 fixprev = fixnext = 1;
2275 } else if ( !BpColinear(&sp->prevcp,&sp->me,&sp->nextcp)) {
2276 ndir.x = sp->nextcp.x - sp->me.x;
2277 ndir.y = sp->nextcp.y - sp->me.y;
2278 nlen = sqrt( ndir.x*ndir.x + ndir.y*ndir.y );
2279 if ( nlen!=0 ) { ndir.x /= nlen; ndir.y/=nlen; }
2280 pdir.x = sp->prevcp.x - sp->me.x;
2281 pdir.y = sp->prevcp.y - sp->me.y;
2282 plen = sqrt( pdir.x*pdir.x + pdir.y*pdir.y );
2283 if ( plen!=0 ) { pdir.x /= plen; pdir.y/=plen; }
2284 if ( !sp->nextcpdef && sp->prevcpdef ) {
2285 sp->prevcp.x = sp->me.x - plen * ndir.x;
2286 sp->prevcp.y = sp->me.y - plen * ndir.y;
2287 fixprev = true;
2288 } else if ( sp->nextcpdef && !sp->prevcpdef ) {
2289 sp->nextcp.x = sp->me.x - nlen * pdir.x;
2290 sp->nextcp.y = sp->me.y - nlen * pdir.y;
2291 fixnext = true;
2292 } else {
2293 SplineCharDefaultNextCP(sp);
2294 SplineCharDefaultPrevCP(sp);
2295 fixprev = fixnext = 1;
2296 }
2297 }
2298 if ( sp->next!=NULL && sp->next->to->pointtype==pt_tangent && sp->next->to->next!=NULL ) {
2299 SplineCharTangentNextCP(sp->next->to);
2300 SplineRefigure(sp->next->to->next);
2301 }
2302 if ( sp->prev!=NULL && sp->prev->from->pointtype==pt_tangent && sp->prev->from->prev!=NULL ) {
2303 SplineCharTangentPrevCP(sp->prev->from);
2304 SplineRefigure(sp->prev->from->prev);
2305 }
2306 if ( fixprev && sp->prev!=NULL )
2307 SplineRefigure(sp->prev);
2308 if ( fixnext && sp->next!=NULL )
2309 SplineRefigure(sp->next);
2310 }
2311
2312 static int SplineSetMakeLoop(SplineSet *spl,real fudge) {
2313 if ( spl->first!=spl->last &&
2314 (spl->first->me.x >= spl->last->me.x-fudge &&
2315 spl->first->me.x <= spl->last->me.x+fudge &&
2316 spl->first->me.y >= spl->last->me.y-fudge &&
2317 spl->first->me.y <= spl->last->me.y+fudge )) {
2318 spl->first->prev = spl->last->prev;
2319 spl->first->prev->to = spl->first;
2320 spl->first->prevcp = spl->last->prevcp;
2321 spl->first->noprevcp = spl->last->noprevcp;
2322 spl->first->prevcpdef = spl->last->prevcpdef;
2323 SplinePointFree(spl->last);
2324 spl->last = spl->first;
2325 if ( spl->spiros!=NULL ) {
2326 spl->spiros[0].ty = spl->spiros[spl->spiro_cnt-2].ty;
2327 spl->spiros[spl->spiro_cnt-2] = spl->spiros[spl->spiro_cnt-1];
2328 --spl->spiro_cnt;
2329 } else {
2330 SplineSetJoinCpFixup(spl->first);
2331 }
2332 return( true );
2333 }
2334 return( false );
2335 }
2336
2337 SplineSet *SplineSetJoin(SplineSet *start,int doall,real fudge,int *changed) {
2338 SplineSet *spl, *spl2, *prev;
2339 /* Few special cases for spiros here because the start and end points */
2340 /* will be the same for spiros and beziers. We just need to fixup spiros */
2341 /* at the end */
2342
2343 *changed = false;
2344 for ( spl=start; spl!=NULL; spl=spl->next ) {
2345 if ( spl->first->prev==NULL &&
2346 (doall || PointListIsSelected(spl)) ) {
2347 if ( SplineSetMakeLoop(spl,fudge) ) {
2348 *changed = true;
2349 } else {
2350 prev = NULL;
2351 for ( spl2=start ; spl2!=NULL; prev = spl2, spl2=spl2->next ) if ( spl2!=spl ) {
2352 if (!( spl->first->me.x >= spl2->last->me.x-fudge &&
2353 spl->first->me.x <= spl2->last->me.x+fudge &&
2354 spl->first->me.y >= spl2->last->me.y-fudge &&
2355 spl->first->me.y <= spl2->last->me.y+fudge )) {
2356 if (( spl->last->me.x >= spl2->last->me.x-fudge &&
2357 spl->last->me.x <= spl2->last->me.x+fudge &&
2358 spl->last->me.y >= spl2->last->me.y-fudge &&
2359 spl->last->me.y <= spl2->last->me.y+fudge ) ||
2360 ( spl->last->me.x >= spl2->first->me.x-fudge &&
2361 spl->last->me.x <= spl2->first->me.x+fudge &&
2362 spl->last->me.y >= spl2->first->me.y-fudge &&
2363 spl->last->me.y <= spl2->first->me.y+fudge ))
2364 SplineSetReverse(spl);
2365 }
2366 if ( spl->first->me.x >= spl2->first->me.x-fudge &&
2367 spl->first->me.x <= spl2->first->me.x+fudge &&
2368 spl->first->me.y >= spl2->first->me.y-fudge &&
2369 spl->first->me.y <= spl2->first->me.y+fudge )
2370 SplineSetReverse(spl2);
2371 if ( spl->first->me.x >= spl2->last->me.x-fudge &&
2372 spl->first->me.x <= spl2->last->me.x+fudge &&
2373 spl->first->me.y >= spl2->last->me.y-fudge &&
2374 spl->first->me.y <= spl2->last->me.y+fudge ) {
2375 spl->first->prev = spl2->last->prev;
2376 spl->first->prev->to = spl->first;
2377 spl->first->prevcp = spl2->last->prevcp;
2378 spl->first->noprevcp = spl2->last->noprevcp;
2379 spl->first->prevcpdef = spl2->last->prevcpdef;
2380 SplinePointFree(spl2->last);
2381 SplineSetJoinCpFixup(spl->first);
2382 spl->first = spl2->first;
2383 spl2->first = spl2->last = NULL;
2384 spl->start_offset = 0;
2385 spl2->start_offset = 0;
2386 if ( prev!=NULL )
2387 prev->next = spl2->next;
2388 else
2389 start = spl2->next;
2390 if ( spl->spiros && spl2->spiros ) {
2391 if ( spl->spiro_cnt+spl2->spiro_cnt > spl->spiro_max )
2392 spl->spiros = realloc(spl->spiros,
2393 (spl->spiro_max = spl->spiro_cnt+spl2->spiro_cnt)*sizeof(spiro_cp));
2394 memcpy(spl->spiros+spl->spiro_cnt-1,
2395 spl2->spiros+1, (spl2->spiro_cnt-1)*sizeof(spiro_cp));
2396 spl->spiro_cnt += spl2->spiro_cnt-2;
2397 } else
2398 SplineSetSpirosClear(spl);
2399 spl2->last = spl2->first = NULL;
2400 spl2->start_offset = 0;
2401 SplinePointListFree(spl2);
2402 SplineSetMakeLoop(spl,fudge);
2403 *changed = true;
2404 break;
2405 }
2406 }
2407 }
2408 }
2409 }
2410 return(start);
2411 }
2412
2413 SplineSet *SplineCharRemoveTiny(SplineChar *sc,SplineSet *head) {
2414 SplineSet *spl, *snext, *pr;
2415 Spline *spline, *next, *first;
2416 const bigreal err = 1.0/64.0;
2417
2418 for ( spl = head, pr=NULL; spl!=NULL; spl = snext ) {
2419 first = NULL;
2420 for ( spline=spl->first->next; spline!=NULL && spline!=first; spline=next ) {
2421 next = spline->to->next;
2422 if ( spline->from->me.x-spline->to->me.x>-err && spline->from->me.x-spline->to->me.x<err &&
2423 spline->from->me.y-spline->to->me.y>-err && spline->from->me.y-spline->to->me.y<err &&
2424 (spline->from->nonextcp || spline->to->noprevcp) &&
2425 spline->from->prev!=NULL ) {
2426 if ( spline->from==spline->to )
2427 break;
2428 if ( spl->last==spline->from ) spl->last = NULL;
2429 if ( spl->first==spline->from ) {
2430 spl->first = NULL;
2431 spl->start_offset = 0;
2432 }
2433 if ( first==spline->from->prev ) first=NULL;
2434 /*SplinesRemoveBetween(sc,spline->from->prev->from,spline->to);*/
2435 spline->to->prevcp = spline->from->prevcp;
2436 spline->to->noprevcp = spline->from->noprevcp;
2437 spline->to->prevcpdef = spline->from->prevcpdef;
2438 spline->from->prev->to = spline->to;
2439 spline->to->prev = spline->from->prev;
2440 SplineRefigure(spline->from->prev);
2441 SplinePointFree(spline->from);
2442 SplineFree(spline);
2443 if ( first==NULL ) first = next->from->prev;
2444 if ( spl->first==NULL ) {
2445 spl->first = next->from;
2446 spl->start_offset = 0;
2447 }
2448 if ( spl->last==NULL ) spl->last = next->from;
2449 } else {
2450 if ( first==NULL ) first = spline;
2451 }
2452 }
2453 snext = spl->next;
2454 if ( spl->first->next==spl->first->prev ) {
2455 spl->next = NULL;
2456 SplinePointListMDFree(sc,spl);
2457 if ( pr==NULL )
2458 head = snext;
2459 else
2460 pr->next = snext;
2461 } else
2462 pr = spl;
2463 }
2464 return( head );
2465 }
2466
2467 int SpIsExtremum(SplinePoint *sp) {
2468 BasePoint *ncp, *pcp;
2469 BasePoint *nncp, *ppcp;
2470 if ( sp->next==NULL || sp->prev==NULL )
2471 return( true );
2472 nncp = &sp->next->to->me;
2473 if ( !sp->nonextcp ) {
2474 ncp = &sp->nextcp;
2475 if ( !sp->next->to->noprevcp )
2476 nncp = &sp->next->to->prevcp;
2477 } else if ( !sp->next->to->noprevcp )
2478 ncp = &sp->next->to->prevcp;
2479 else
2480 ncp = nncp;
2481 ppcp = &sp->prev->from->me;
2482 if ( !sp->noprevcp ) {
2483 pcp = &sp->prevcp;
2484 if ( !sp->prev->from->nonextcp )
2485 ppcp = &sp->prev->from->nextcp;
2486 } else if ( !sp->prev->from->nonextcp )
2487 pcp = &sp->prev->from->nextcp;
2488 else
2489 pcp = ppcp;
2490 if ((( ncp->x<sp->me.x || (ncp->x==sp->me.x && nncp->x<sp->me.x)) &&
2491 (pcp->x<sp->me.x || (pcp->x==sp->me.x && ppcp->x<sp->me.x))) ||
2492 ((ncp->x>sp->me.x || (ncp->x==sp->me.x && nncp->x>sp->me.x)) &&
2493 (pcp->x>sp->me.x || (pcp->x==sp->me.x && ppcp->x>sp->me.x))) ||
2494 (( ncp->y<sp->me.y || (ncp->y==sp->me.y && nncp->y<sp->me.y)) &&
2495 (pcp->y<sp->me.y || (pcp->y==sp->me.y && ppcp->y<sp->me.y))) ||
2496 ((ncp->y>sp->me.y || (ncp->y==sp->me.y && nncp->y>sp->me.y)) &&
2497 (pcp->y>sp->me.y || (pcp->y==sp->me.y && ppcp->y>sp->me.y))))
2498 return( true );
2499
2500 /* These aren't true points of extrema, but they probably should be treated */
2501 /* as if they were */
2502 if ( !sp->nonextcp && !sp->noprevcp &&
2503 ((sp->me.x==sp->nextcp.x && sp->me.x==sp->prevcp.x) ||
2504 (sp->me.y==sp->nextcp.y && sp->me.y==sp->prevcp.y)) )
2505 return( true );
2506
2507 return( false );
2508 }
2509
2510 /* An extremum is very close to the end-point. So close that we don't want */
2511 /* to add a new point. Instead try moving the control points around */
2512 /* Options: */
2513 /* o if the control point is very close to the base point then remove it */
2514 /* o if the slope at the endpoint is in the opposite direction from */
2515 /* what we expect, then subtract off the components we don't like */
2516 /* o make the slope at the end point horizontal/vertical */
2517 static int ForceEndPointExtrema(Spline *s,int isto) {
2518 SplinePoint *end;
2519 BasePoint *cp, oldcp, to, unitslope, othercpunit, myslope;
2520 bigreal xdiff, ydiff, mylen, cplen, mydot, cpdot, len;
2521 /* To get here we know that the extremum is extremely close to the end */
2522 /* point, and adjusting the slope at the end-point may be all we need */
2523 /* to do. We won't need to adjust it by much, because it is so close. */
2524
2525 if ( isto ) {
2526 end = s->to; cp = &end->prevcp;
2527 othercpunit.x = s->from->nextcp.x - s->from->me.x;
2528 othercpunit.y = s->from->nextcp.y - s->from->me.y;
2529 } else {
2530 end = s->from; cp = &end->nextcp;
2531 othercpunit.x = s->to->prevcp.x-s->to->me.x;
2532 othercpunit.y = s->to->prevcp.y-s->to->me.y;
2533 }
2534 cplen = othercpunit.x*othercpunit.x + othercpunit.y*othercpunit.y;
2535 cplen = sqrt(cplen);
2536 myslope.x = cp->x - end->me.x;
2537 myslope.y = cp->y - end->me.y;
2538 mylen = sqrt(myslope.x*myslope.x + myslope.y*myslope.y);
2539
2540 unitslope.x = s->to->me.x - s->from->me.x;
2541 unitslope.y = s->to->me.y - s->from->me.y;
2542 len = unitslope.x*unitslope.x + unitslope.y*unitslope.y;
2543 if ( len==0 )
2544 return( -1 );
2545 len = sqrt(len);
2546 if ( mylen<30*len && mylen<cplen && mylen<1 ) {
2547 if ( mylen==0 )
2548 return -1;
2549 if ( isto ) {
2550 s->to->noprevcp = true;
2551 s->to->prevcp = s->to->me;
2552 } else {
2553 s->from->nonextcp = true;
2554 s->from->nextcp = s->from->me;
2555 }
2556 end->pointtype = pt_corner;
2557 SplineRefigure(s);
2558 return( true ); /* We changed the slope */
2559 }
2560 unitslope.x /= len; unitslope.y /= len;
2561
2562 mydot = myslope.x*unitslope.y - myslope.y*unitslope.x;
2563 cpdot = othercpunit.x*unitslope.y - othercpunit.y*unitslope.y;
2564 if ( mydot*cpdot<0 && mylen<cplen ) {
2565 /* The two control points are in opposite directions with respect to */
2566 /* the main spline, and ours isn't very big, so make it point along */
2567 /* the spline */
2568 end->pointtype = pt_corner;
2569 if ( isto ) {
2570 s->to->prevcp.x = s->to->me.x - mydot*unitslope.x;
2571 s->to->prevcp.y = s->to->me.y - mydot*unitslope.y;
2572 } else {
2573 s->from->nextcp.x = s->from->me.x + mydot*unitslope.x;
2574 s->from->nextcp.y = s->from->me.y + mydot*unitslope.y;
2575 }
2576 SplineRefigure(s);
2577 return( true ); /* We changed the slope */
2578 }
2579
2580 if ( (xdiff = cp->x - end->me.x)<0 ) xdiff = -xdiff;
2581 if ( (ydiff = cp->y - end->me.y)<0 ) ydiff = -ydiff;
2582
2583 oldcp = to = *cp;
2584 if ( xdiff<ydiff/10.0 && xdiff>0 ) {
2585 to.x = end->me.x;
2586 end->pointtype = pt_corner;
2587 SPAdjustControl(end,cp,&to,s->order2);
2588 return( (cp->x!=oldcp.x || cp->y!=oldcp.y) ? 1 : -1 );
2589 } else if ( ydiff<xdiff/10 && ydiff>0 ) {
2590 to.y = end->me.y;
2591 end->pointtype = pt_corner;
2592 SPAdjustControl(end,cp,&to,s->order2);
2593 return( (cp->x!=oldcp.x || cp->y!=oldcp.y) ? 1 : -1 );
2594 }
2595
2596 return( -1 ); /* Didn't do anything */
2597 }
2598
2599 int Spline1DCantExtremeX(const Spline *s) {
2600 /* Sometimes we get rounding errors when converting from control points */
2601 /* to spline coordinates. These rounding errors can give us false */
2602 /* extrema. So do a sanity check to make sure it is possible to get */
2603 /* any extrema before actually looking for them */
2604
2605 if ( s->from->me.x>=s->from->nextcp.x &&
2606 s->from->nextcp.x>=s->to->prevcp.x &&
2607 s->to->prevcp.x>=s->to->me.x )
2608 return( true );
2609 if ( s->from->me.x<=s->from->nextcp.x &&
2610 s->from->nextcp.x<=s->to->prevcp.x &&
2611 s->to->prevcp.x<=s->to->me.x )
2612 return( true );
2613
2614 return( false );
2615 }
2616
2617 int Spline1DCantExtremeY(const Spline *s) {
2618 /* Sometimes we get rounding errors when converting from control points */
2619 /* to spline coordinates. These rounding errors can give us false */
2620 /* extrema. So do a sanity check to make sure it is possible to get */
2621 /* any extrema before actually looking for them */
2622
2623 if ( s->from->me.y>=s->from->nextcp.y &&
2624 s->from->nextcp.y>=s->to->prevcp.y &&
2625 s->to->prevcp.y>=s->to->me.y )
2626 return( true );
2627 if ( s->from->me.y<=s->from->nextcp.y &&
2628 s->from->nextcp.y<=s->to->prevcp.y &&
2629 s->to->prevcp.y<=s->to->me.y )
2630 return( true );
2631
2632 return( false );
2633 }
2634
2635 Spline *SplineAddExtrema(Spline *s,int always,real lenbound, real offsetbound,
2636 DBounds *b) {
2637 /* First find the extrema, if any */
2638 bigreal t[4], min;
2639 uint8 rmfrom[4], rmto[4];
2640 int p, i,j, p_s, mini, restart, forced;
2641 SplinePoint *sp;
2642 real len;
2643
2644 if ( !always ) {
2645 real xlen, ylen;
2646 xlen = (s->from->me.x-s->to->me.x);
2647 ylen = (s->from->me.y-s->to->me.y);
2648 len = xlen*xlen + ylen*ylen;
2649 lenbound *= lenbound;
2650 if ( len < lenbound ) {
2651 len = SplineLength(s);
2652 len *= len;
2653 }
2654 }
2655
2656 memset(rmfrom,0,sizeof(rmfrom));
2657 memset(rmto,0,sizeof(rmto));
2658
2659 for (;;) {
2660 if ( s->knownlinear )
2661 return(s);
2662 p = 0;
2663 if ( Spline1DCantExtremeX(s) ) {
2664 /* If the control points are at the end-points then this (1D) spline is */
2665 /* basically a line. But rounding errors can give us very faint extrema */
2666 /* if we look for them */
2667 } else if ( s->splines[0].a!=0 ) {
2668 bigreal d = 4*s->splines[0].b*s->splines[0].b-4*3*s->splines[0].a*s->splines[0].c;
2669 if ( d>0 ) {
2670 extended t1, t2;
2671 d = sqrt(d);
2672 t1 = (-2*s->splines[0].b+d)/(2*3*s->splines[0].a);
2673 t2 = (-2*s->splines[0].b-d)/(2*3*s->splines[0].a);
2674 t[p++] = CheckExtremaForSingleBitErrors(&s->splines[0],t1,t2);
2675 t[p++] = CheckExtremaForSingleBitErrors(&s->splines[0],t2,t1);
2676 }
2677 } else if ( s->splines[0].b!=0 )
2678 t[p++] = -s->splines[0].c/(2*s->splines[0].b);
2679 if ( !always ) {
2680 /* Generally we are only interested in extrema on long splines, or */
2681 /* extrema which are extrema for the entire contour, not just this */
2682 /* spline */
2683 /* Also extrema which are very close to one of the end-points can */
2684 /* be ignored. */
2685 /* No they can't. But we need to remove the original point in this*/
2686 /* case */
2687 for ( i=0; i<p; ++i ) {
2688 real x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d;
2689 real y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d;
2690 int close_from = ( x-s->from->me.x<offsetbound && x-s->from->me.x>-offsetbound) &&
2691 ( y-s->from->me.y<10*offsetbound && y-s->from->me.y>-10*offsetbound );
2692 int close_to = ( x-s->to->me.x<offsetbound && x-s->to->me.x>-offsetbound) &&
2693 ( y-s->to->me.y<10*offsetbound && y-s->to->me.y>-10*offsetbound );
2694 int remove_from = close_from && GoodCurve(s->from,true) && !SpIsExtremum(s->from);
2695 int remove_to = close_to && GoodCurve(s->to,false) && !SpIsExtremum(s->to);
2696 if (( x>b->minx && x<b->maxx && len<lenbound ) ||
2697 (close_from && !remove_from) || (close_to && !remove_to) ) {
2698 --p;
2699 for ( j=i; j<p; ++j )
2700 t[j] = t[j+1];
2701 --i;
2702 } else {
2703 rmfrom[i] = remove_from;
2704 rmto[i] = remove_to;
2705 }
2706 }
2707 }
2708
2709 p_s = p;
2710 if ( Spline1DCantExtremeY(s) ) {
2711 /* If the control points are at the end-points then this (1D) spline is */
2712 /* basically a line. But rounding errors can give us very faint extrema */
2713 /* if we look for them */
2714 } else if ( s->splines[1].a!=0 ) {
2715 bigreal d = 4*s->splines[1].b*s->splines[1].b-4*3*s->splines[1].a*s->splines[1].c;
2716 if ( d>0 ) {
2717 extended t1,t2;
2718 d = sqrt(d);
2719 t1 = (-2*s->splines[1].b+d)/(2*3*s->splines[1].a);
2720 t2 = (-2*s->splines[1].b-d)/(2*3*s->splines[1].a);
2721 t[p++] = CheckExtremaForSingleBitErrors(&s->splines[1],t1,t2);
2722 t[p++] = CheckExtremaForSingleBitErrors(&s->splines[1],t2,t1);
2723 }
2724 } else if ( s->splines[1].b!=0 )
2725 t[p++] = -s->splines[1].c/(2*s->splines[1].b);
2726 if ( !always ) {
2727 for ( i=p_s; i<p; ++i ) {
2728 real x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d;
2729 real y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d;
2730 int close_from =( y-s->from->me.y<offsetbound && y-s->from->me.y>-offsetbound ) &&
2731 ( x-s->from->me.x<offsetbound && x-s->from->me.x>-offsetbound);
2732 int close_to = ( y-s->to->me.y<offsetbound && y-s->to->me.y>-offsetbound ) &&
2733 ( x-s->to->me.x<offsetbound && x-s->to->me.x>-offsetbound);
2734 int remove_from = close_from && GoodCurve(s->from,true) && !SpIsExtremum(s->from);
2735 int remove_to = close_to && GoodCurve(s->to,false) && !SpIsExtremum(s->to);
2736 if (( y>b->miny && y<b->maxy && len<lenbound ) ||
2737 (close_from && !remove_from) || (close_to && !remove_to) ) {
2738 --p;
2739 for ( j=i; j<p; ++j )
2740 t[j] = t[j+1];
2741 --i;
2742 } else {
2743 rmfrom[i] = remove_from;
2744 rmto[i] = remove_to;
2745 }
2746 }
2747 }
2748
2749 /* Throw out any t values which are not between 0 and 1 */
2750 /* (we do a little fudging near the endpoints so we don't get confused */
2751 /* by rounding errors) */
2752 restart = false;
2753 for ( i=0; i<p; ++i ) {
2754 if ( t[i]>0 && t[i]<.05 ) {
2755 BasePoint test;
2756 /* Expand stroke gets very confused on zero-length splines so */
2757 /* don't let that happen */
2758 test.x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d - s->from->me.x;
2759 test.y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d - s->from->me.y;
2760 if (( test.x*test.x + test.y*test.y<1e-7 ) && ( test.x*test.x + test.y*test.y>0.0 )) {
2761 if ( (forced = ForceEndPointExtrema(s,0))>=0 ) {
2762 if ( forced && s->from->prev!=NULL )
2763 SplineAddExtrema(s->from->prev,always,lenbound,offsetbound,b);
2764 restart = true;
2765 break;
2766 }
2767 }
2768 }
2769 if ( t[i]<1 && t[i]>.95 ) {
2770 BasePoint test;
2771 test.x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d - s->to->me.x;
2772 test.y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d - s->to->me.y;
2773 if (( test.x*test.x + test.y*test.y < 1e-7 ) && ( test.x*test.x + test.y*test.y>0.0 )) {
2774 if ( ForceEndPointExtrema(s,1)>=0 ) {
2775 /* don't need to fix up next, because splinesetaddextrema will do that soon */
2776 restart = true;
2777 break;
2778 }
2779 }
2780 }
2781
2782 if ( t[i]<=0 || t[i]>=1.0 ) {
2783 --p;
2784 for ( j=i; j<p; ++j ) {
2785 t[j] = t[j+1];
2786 rmfrom[j] = rmfrom[j+1];
2787 rmto[j] = rmto[j+1];
2788 }
2789 --i;
2790 }
2791 }
2792 if ( restart )
2793 continue;
2794
2795 if ( p==0 )
2796 return(s);
2797
2798 /* Find the smallest of all the interesting points */
2799 min = t[0]; mini = 0;
2800 for ( i=1; i<p; ++i ) {
2801 if ( t[i]<min ) {
2802 min=t[i];
2803 mini = i;
2804 }
2805 }
2806 sp = SplineBisect(s,min);
2807 /* On the mac we get rounding errors in the bisect routine */
2808 { bigreal dx, dy;
2809 if ( (dx = sp->me.x - sp->prevcp.x)<0 ) dx=-dx;
2810 if ( (dy = sp->me.y - sp->prevcp.y)<0 ) dy=-dy;
2811 if ( dx!=0 && dy!=0 ) {
2812 if ( dx<dy )
2813 sp->prevcp.x = sp->me.x;
2814 else
2815 sp->prevcp.y = sp->me.y;
2816 }
2817 if ( (dx = sp->me.x - sp->nextcp.x)<0 ) dx=-dx;
2818 if ( (dy = sp->me.y - sp->nextcp.y)<0 ) dy=-dy;
2819 if ( dx!=0 && dy!=0 ) {
2820 if ( dx<dy )
2821 sp->nextcp.x = sp->me.x;
2822 else
2823 sp->nextcp.y = sp->me.y;
2824 }
2825 }
2826
2827 if ( rmfrom[mini] ) sp->prev->from->ticked = true;
2828 if ( rmto[mini] ) sp->next->to->ticked = true;
2829 s = sp->next;
2830 if ( p==1 )
2831 return( s );
2832 /* Don't try to use any other computed t values, it is easier to */
2833 /* recompute them than to try and figure out what they map to on the */
2834 /* new spline */
2835 }
2836 }
2837
2838 void SplineSetAddExtrema(SplineChar *sc, SplineSet *ss,enum ae_type between_selected, int emsize) {
2839 Spline *s, *first;
2840 DBounds b;
2841 int always = true;
2842 real lenbound = 0;
2843 real offsetbound=0;
2844 SplinePoint *sp, *nextp;
2845
2846 if ( between_selected==ae_only_good ) {
2847 SplineSetQuickBounds(ss,&b);
2848 lenbound = (emsize)/32.0;
2849 always = false;
2850 offsetbound = .5;
2851 between_selected = ae_only_good_rm_later;
2852 for ( sp = ss->first; ; ) {
2853 sp->ticked = false;
2854 if ( sp->next==NULL )
2855 break;
2856 sp = sp->next->to;
2857 if ( sp==ss->first )
2858 break;
2859 }
2860 }
2861
2862 first = NULL;
2863 for ( s = ss->first->next; s!=NULL && s!=first; s = s->to->next ) {
2864 if ( between_selected!=ae_between_selected ||
2865 (s->from->selected && s->to->selected))
2866 s = SplineAddExtrema(s,always,lenbound,offsetbound,&b);
2867 if ( first==NULL ) first = s;
2868 }
2869 if ( between_selected == ae_only_good_rm_later ) {
2870 for ( sp = ss->first; ; ) {
2871 if ( sp->next==NULL )
2872 break;
2873 nextp = sp->next->to;
2874 if ( sp->ticked ) {
2875 if ( sp==ss->first ) {
2876 ss->first = ss->last = nextp;
2877 ss->start_offset = 0;
2878 }
2879 SplinesRemoveBetween(sc,sp->prev->from,nextp,1);
2880 }
2881 sp = nextp;
2882 if ( sp==ss->first )
2883 break;
2884 }
2885 }
2886 }
2887
2888 void SplineCharAddExtrema(SplineChar *sc, SplineSet *head,enum ae_type between_selected,int emsize) {
2889 SplineSet *ss;
2890
2891 for ( ss=head; ss!=NULL; ss=ss->next )
2892 SplineSetAddExtrema(sc,ss,between_selected,emsize);
2893 }
2894
2895 char *GetNextUntitledName(void) {
2896 static int untitled_cnt=1;
2897 char buffer[80];
2898
2899 sprintf( buffer, "Untitled%d", untitled_cnt++ );
2900 return( copy(buffer));
2901 }
2902
2903 SplineFont *SplineFontEmpty(void) {
2904 extern int default_fv_row_count, default_fv_col_count;
2905 SplineFont *sf;
2906
2907 sf = calloc(1,sizeof(SplineFont));
2908 sf->pfminfo.fstype = -1;
2909 sf->pfminfo.stylemap = -1;
2910 sf->top_enc = -1;
2911 sf->macstyle = -1;
2912 sf->desired_row_cnt = default_fv_row_count; sf->desired_col_cnt = default_fv_col_count;
2913 sf->display_antialias = default_fv_antialias;
2914 sf->display_bbsized = default_fv_bbsized;
2915 sf->display_size = -default_fv_font_size;
2916 sf->display_layer = ly_fore;
2917 sf->sfntRevision = sfntRevisionUnset;
2918 sf->woffMajor = woffUnset;
2919 sf->woffMinor = woffUnset;
2920 sf->pfminfo.winascent_add = sf->pfminfo.windescent_add = true;
2921 sf->pfminfo.hheadascent_add = sf->pfminfo.hheaddescent_add = true;
2922 sf->pfminfo.typoascent_add = sf->pfminfo.typodescent_add = true;
2923 if ( TTFFoundry!=NULL )
2924 strncpy(sf->pfminfo.os2_vendor,TTFFoundry,4);
2925 else
2926 memcpy(sf->pfminfo.os2_vendor,"PfEd",4);
2927 sf->for_new_glyphs = DefaultNameListForNewFonts();
2928 sf->creationtime = sf->modificationtime = GetTime();
2929
2930 sf->layer_cnt = 2;
2931 sf->layers = calloc(2,sizeof(LayerInfo));
2932 sf->layers[ly_back].name = copy(_("Back"));
2933 sf->layers[ly_back].background = true;
2934 sf->layers[ly_fore].name = copy(_("Fore"));
2935 sf->layers[ly_fore].background = false;
2936 sf->grid.background = true;
2937
2938 return( sf );
2939 }
2940
2941 SplineFont *SplineFontBlank(int charcnt) {
2942 SplineFont *sf;
2943 char buffer[200];
2944 time_t now;
2945 struct tm *tm;
2946 const char *author = GetAuthor();
2947
2948 sf = SplineFontEmpty();
2949 sf->fontname = GetNextUntitledName();
2950 sf->fullname = copy(sf->fontname);
2951 sf->familyname = copy(sf->fontname);
2952 sprintf( buffer, "%s.sfd", sf->fontname);
2953 sf->origname = ToAbsolute(buffer);
2954 sf->weight = copy("Regular");
2955 now = GetTime();
2956 if (!getenv("SOURCE_DATE_EPOCH")) {
2957 tm = localtime(&now);
2958 } else {
2959 tm = gmtime(&now);
2960 }
2961 if ( author!=NULL )
2962 sprintf( buffer, "Copyright (c) %d, %.50s", tm->tm_year+1900, author );
2963 else
2964 sprintf( buffer, "Copyright (c) %d, Anonymous", tm->tm_year+1900 );
2965 sf->copyright = copy(buffer);
2966 if ( xuid!=NULL ) {
2967 sf->xuid = malloc(strlen(xuid)+20);
2968 sprintf(sf->xuid,"[%s %d]", xuid, (rand()&0xffffff));
2969 }
2970 sprintf( buffer, "%d-%d-%d: Created with FontForge (http://fontforge.org)", tm->tm_year+1900, tm->tm_mon+1, tm->tm_mday );
2971 sf->comments = copy(buffer);
2972 sf->version = copy("001.000");
2973 sf->ascent = rint(new_em_size*.8); sf->descent = new_em_size-sf->ascent;
2974 sf->upos = -rint(new_em_size*.1); sf->uwidth = rint(new_em_size*.05); /* defaults for cff */
2975 sf->glyphcnt = 0;
2976 sf->glyphmax = charcnt;
2977 sf->glyphs = calloc(charcnt,sizeof(SplineChar *));
2978 sf->pfminfo.fstype = -1;
2979 sf->pfminfo.stylemap = -1;
2980 sf->use_typo_metrics = true;
2981 return( sf );
2982 }
2983
2984 SplineFont *SplineFontNew(void) {
2985 SplineFont *sf;
2986 int enclen = default_encoding->char_cnt;
2987
2988 sf = SplineFontBlank(enclen);
2989 sf->onlybitmaps = true;
2990 sf->new = true;
2991 sf->layers[ly_back].order2 = new_fonts_are_order2;
2992 sf->layers[ly_fore].order2 = new_fonts_are_order2;
2993 sf->grid.order2 = new_fonts_are_order2;
2994
2995 sf->map = EncMapNew(enclen,enclen,default_encoding);
2996 return( sf );
2997 }
2998
2999 static void SFChangeXUID(SplineFont *sf, int random) {
3000 char *pt, *new, *npt;
3001 int val;
3002
3003 if ( sf->xuid==NULL )
3004 return;
3005 pt = strrchr(sf->xuid,' ');
3006 if ( pt==NULL )
3007 pt = strchr(sf->xuid,'[');
3008 if ( pt==NULL )
3009 pt = sf->xuid;
3010 else
3011 ++pt;
3012 if ( random )
3013 val = rand()&0xffffff;
3014 else {
3015 val = strtol(pt,NULL,10);
3016 val = (val+1)&0xffffff;
3017 }
3018
3019 new = malloc(pt-sf->xuid+12);
3020 strncpy(new,sf->xuid,pt-sf->xuid);
3021 npt = new + (pt-sf->xuid);
3022 if ( npt==new ) *npt++ = '[';
3023 sprintf(npt, "%d]", val );
3024 free(sf->xuid); sf->xuid = new;
3025 sf->changed = true;
3026 sf->changed_since_xuidchanged = false;
3027 }
3028
3029 void SFIncrementXUID(SplineFont *sf) {
3030 SFChangeXUID(sf,false);
3031 }
3032
3033 void SFRandomChangeXUID(SplineFont *sf) {
3034 SFChangeXUID(sf,true);
3035 }
3036
3037 void SPWeightedAverageCps(SplinePoint *sp) {
3038 bigreal pangle, nangle, angle, plen, nlen, c, s;
3039 if ( sp->noprevcp || sp->nonextcp )
3040 /*SPAverageCps(sp)*/; /* Expand Stroke wants this case to hold still */
3041 else if (( sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve) &&
3042 sp->prev && sp->next ) {
3043 pangle = atan2(sp->me.y-sp->prevcp.y,sp->me.x-sp->prevcp.x);
3044 nangle = atan2(sp->nextcp.y-sp->me.y,sp->nextcp.x-sp->me.x);
3045 if ( pangle<0 && nangle>0 && nangle-pangle>=(FF_PI-6e-8) )
3046 pangle += 2*FF_PI;
3047 else if ( pangle>0 && nangle<0 && pangle-nangle>=(FF_PI-6e-8) )
3048 nangle += 2*FF_PI;
3049 plen = sqrt((sp->me.y-sp->prevcp.y)*(sp->me.y-sp->prevcp.y) +
3050 (sp->me.x-sp->prevcp.x)*(sp->me.x-sp->prevcp.x));
3051 nlen = sqrt((sp->nextcp.y-sp->me.y)*(sp->nextcp.y-sp->me.y) +
3052 (sp->nextcp.x-sp->me.x)*(sp->nextcp.x-sp->me.x));
3053 if ( plen+nlen==0 )
3054 angle = (nangle+pangle)/2;
3055 else
3056 angle = (plen*pangle + nlen*nangle)/(plen+nlen);
3057 plen = -plen;
3058 c = cos(angle); s=sin(angle);
3059 sp->nextcp.x = c*nlen + sp->me.x;
3060 sp->nextcp.y = s*nlen + sp->me.y;
3061 sp->prevcp.x = c*plen + sp->me.x;
3062 sp->prevcp.y = s*plen + sp->me.y;
3063 SplineRefigure(sp->prev);
3064 SplineRefigure(sp->next);
3065 } else
3066 SPAverageCps(sp);
3067 }
3068
3069 void SPAverageCps(SplinePoint *sp) {
3070 bigreal pangle, nangle, angle, plen, nlen, c, s;
3071 if (( sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve) &&
3072 sp->prev && sp->next ) {
3073 if ( sp->noprevcp )
3074 pangle = atan2(sp->me.y-sp->prev->from->me.y,sp->me.x-sp->prev->from->me.x);
3075 else
3076 pangle = atan2(sp->me.y-sp->prevcp.y,sp->me.x-sp->prevcp.x);
3077 if ( sp->nonextcp )
3078 nangle = atan2(sp->next->to->me.y-sp->me.y,sp->next->to->me.x-sp->me.x);
3079 else
3080 nangle = atan2(sp->nextcp.y-sp->me.y,sp->nextcp.x-sp->me.x);
3081 if ( pangle<0 && nangle>0 && nangle-pangle>=(FF_PI-6e-8) )
3082 pangle += 2*FF_PI;
3083 else if ( pangle>0 && nangle<0 && pangle-nangle>=(FF_PI-6e-8) )
3084 nangle += 2*FF_PI;
3085 angle = (nangle+pangle)/2;
3086 plen = -sqrt((sp->me.y-sp->prevcp.y)*(sp->me.y-sp->prevcp.y) +
3087 (sp->me.x-sp->prevcp.x)*(sp->me.x-sp->prevcp.x));
3088 nlen = sqrt((sp->nextcp.y-sp->me.y)*(sp->nextcp.y-sp->me.y) +
3089 (sp->nextcp.x-sp->me.x)*(sp->nextcp.x-sp->me.x));
3090 c = cos(angle); s=sin(angle);
3091 sp->nextcp.x = c*nlen + sp->me.x;
3092 sp->nextcp.y = s*nlen + sp->me.y;
3093 sp->prevcp.x = c*plen + sp->me.x;
3094 sp->prevcp.y = s*plen + sp->me.y;
3095 SplineRefigure(sp->prev);
3096 SplineRefigure(sp->next);
3097 } else if ( sp->pointtype==pt_tangent && sp->prev && sp->next ) {
3098 if ( !sp->noprevcp ) {
3099 nangle = atan2(sp->next->to->me.y-sp->me.y,sp->next->to->me.x-sp->me.x);
3100 plen = -sqrt((sp->me.y-sp->prevcp.y)*(sp->me.y-sp->prevcp.y) +
3101 (sp->me.x-sp->prevcp.x)*(sp->me.x-sp->prevcp.x));
3102 c = cos(nangle); s=sin(nangle);
3103 sp->prevcp.x = c*plen + sp->me.x;
3104 sp->prevcp.y = s*plen + sp->me.y;
3105 SplineRefigure(sp->prev);
3106 }
3107 if ( !sp->nonextcp ) {
3108 pangle = atan2(sp->me.y-sp->prev->from->me.y,sp->me.x-sp->prev->from->me.x);
3109 nlen = sqrt((sp->nextcp.y-sp->me.y)*(sp->nextcp.y-sp->me.y) +
3110 (sp->nextcp.x-sp->me.x)*(sp->nextcp.x-sp->me.x));
3111 c = cos(pangle); s=sin(pangle);
3112 sp->nextcp.x = c*nlen + sp->me.x;
3113 sp->nextcp.y = s*nlen + sp->me.y;
3114 SplineRefigure(sp->next);
3115 }
3116 }
3117 }
3118
3119 void SPLAverageCps(SplinePointList *spl) {
3120 SplinePoint *sp;
3121
3122 while ( spl!=NULL ) {
3123 for ( sp=spl->first ; ; ) {
3124 SPAverageCps(sp);
3125 if ( sp->next==NULL )
3126 break;
3127 sp = sp->next->to;
3128 if ( sp==spl->first )
3129 break;
3130 }
3131 spl = spl->next;
3132 }
3133 }
3134
3135 void SplineCharTangentNextCP(SplinePoint *sp) {
3136 bigreal len;
3137 BasePoint *bp, unit;
3138 extern int snaptoint;
3139
3140 if ( sp->prev==NULL )
3141 return;
3142 bp = &sp->prev->from->me;
3143
3144 unit.y = sp->me.y-bp->y; unit.x = sp->me.x-bp->x;
3145 len = sqrt( unit.x*unit.x + unit.y*unit.y );
3146 if ( len!=0 ) {
3147 unit.x /= len;
3148 unit.y /= len;
3149 }
3150 len = sqrt((sp->nextcp.y-sp->me.y)*(sp->nextcp.y-sp->me.y) + (sp->nextcp.x-sp->me.x)*(sp->nextcp.x-sp->me.x));
3151 sp->nextcp.x = sp->me.x + len*unit.x;
3152 sp->nextcp.y = sp->me.y + len*unit.y;
3153 if ( snaptoint ) {
3154 sp->nextcp.x = rint(sp->nextcp.x);
3155 sp->nextcp.y = rint(sp->nextcp.y);
3156 } else {
3157 sp->nextcp.x = rint(sp->nextcp.x*1024)/1024;
3158 sp->nextcp.y = rint(sp->nextcp.y*1024)/1024;
3159 }
3160 if ( sp->next!=NULL && sp->next->order2 )
3161 sp->next->to->prevcp = sp->nextcp;
3162 }
3163
3164 void SplineCharTangentPrevCP(SplinePoint *sp) {
3165 bigreal len;
3166 BasePoint *bp, unit;
3167 extern int snaptoint;
3168
3169 if ( sp->next==NULL )
3170 return;
3171 bp = &sp->next->to->me;
3172
3173 unit.y = sp->me.y-bp->y; unit.x = sp->me.x-bp->x;
3174 len = sqrt( unit.x*unit.x + unit.y*unit.y );
3175 if ( len!=0 ) {
3176 unit.x /= len;
3177 unit.y /= len;
3178 }
3179 len = sqrt((sp->prevcp.y-sp->me.y)*(sp->prevcp.y-sp->me.y) + (sp->prevcp.x-sp->me.x)*(sp->prevcp.x-sp->me.x));
3180 sp->prevcp.x = sp->me.x + len*unit.x;
3181 sp->prevcp.y = sp->me.y + len*unit.y;
3182 if ( snaptoint ) {
3183 sp->prevcp.x = rint(sp->prevcp.x);
3184 sp->prevcp.y = rint(sp->prevcp.y);
3185 } else {
3186 sp->prevcp.x = rint(sp->prevcp.x*1024)/1024;
3187 sp->prevcp.y = rint(sp->prevcp.y*1024)/1024;
3188 }
3189 if ( sp->prev!=NULL && sp->prev->order2 )
3190 sp->prev->from->nextcp = sp->prevcp;
3191 }
3192
3193 void BP_HVForce(BasePoint *vector) {
3194 /* Force vector to be horizontal/vertical */
3195 bigreal dx, dy, len;
3196
3197 if ( (dx= vector->x)<0 ) dx = -dx;
3198 if ( (dy= vector->y)<0 ) dy = -dy;
3199 if ( dx==0 || dy==0 )
3200 return;
3201 len = sqrt(dx*dx + dy*dy);
3202 if ( dx>dy ) {
3203 vector->x = vector->x<0 ? -len : len;
3204 vector->y = 0;
3205 } else {
3206 vector->y = vector->y<0 ? -len : len;
3207 vector->x = 0;
3208 }
3209 }
3210
3211 #define NICE_PROPORTION .39
3212 void SplineCharDefaultNextCP(SplinePoint *base) {
3213 SplinePoint *prev=NULL, *next;
3214 bigreal len, plen, ulen;
3215 BasePoint unit;
3216 extern int snaptoint;
3217
3218 if ( base->next==NULL )
3219 return;
3220 if ( base->next->order2 ) {
3221 SplineRefigureFixup(base->next);
3222 return;
3223 }
3224 if ( !base->nextcpdef ) {
3225 if ( base->pointtype==pt_tangent )
3226 SplineCharTangentNextCP(base);
3227 return;
3228 }
3229 next = base->next->to;
3230 if ( base->prev!=NULL )
3231 prev = base->prev->from;
3232
3233 len = NICE_PROPORTION * sqrt((base->me.x-next->me.x)*(base->me.x-next->me.x) +
3234 (base->me.y-next->me.y)*(base->me.y-next->me.y));
3235 unit.x = next->me.x - base->me.x;
3236 unit.y = next->me.y - base->me.y;
3237 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3238 if ( ulen!=0 )
3239 unit.x /= ulen, unit.y /= ulen;
3240 base->nonextcp = false;
3241
3242 if ( base->pointtype == pt_curve || base->pointtype == pt_hvcurve ) {
3243 if ( prev!=NULL && (base->prevcpdef || base->noprevcp)) {
3244 unit.x = next->me.x - prev->me.x;
3245 unit.y = next->me.y - prev->me.y;
3246 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3247 if ( ulen!=0 )
3248 unit.x /= ulen, unit.y /= ulen;
3249 if ( base->pointtype == pt_hvcurve )
3250 BP_HVForce(&unit);
3251 plen = sqrt((base->prevcp.x-base->me.x)*(base->prevcp.x-base->me.x) +
3252 (base->prevcp.y-base->me.y)*(base->prevcp.y-base->me.y));
3253 base->prevcp.x = base->me.x - plen*unit.x;
3254 base->prevcp.y = base->me.y - plen*unit.y;
3255 if ( snaptoint ) {
3256 base->prevcp.x = rint(base->prevcp.x);
3257 base->prevcp.y = rint(base->prevcp.y);
3258 }
3259 SplineRefigureFixup(base->prev);
3260 } else if ( prev!=NULL ) {
3261 /* The prev control point is fixed. So we've got to use the same */
3262 /* angle it uses */
3263 unit.x = base->me.x-base->prevcp.x;
3264 unit.y = base->me.y-base->prevcp.y;
3265 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3266 if ( ulen!=0 )
3267 unit.x /= ulen, unit.y /= ulen;
3268 } else {
3269 base->prevcp = base->me;
3270 base->noprevcp = true;
3271 base->prevcpdef = true;
3272 }
3273 if ( base->pointtype == pt_hvcurve )
3274 BP_HVForce(&unit);
3275 } else if ( base->pointtype == pt_corner ) {
3276 if ( next->pointtype != pt_curve && next->pointtype != pt_hvcurve ) {
3277 base->nonextcp = true;
3278 }
3279 } else /* tangent */ {
3280 if ( next->pointtype != pt_curve ) {
3281 base->nonextcp = true;
3282 } else {
3283 if ( prev!=NULL ) {
3284 if ( !base->noprevcp ) {
3285 plen = sqrt((base->prevcp.x-base->me.x)*(base->prevcp.x-base->me.x) +
3286 (base->prevcp.y-base->me.y)*(base->prevcp.y-base->me.y));
3287 base->prevcp.x = base->me.x - plen*unit.x;
3288 base->prevcp.y = base->me.y - plen*unit.y;
3289 SplineRefigureFixup(base->prev);
3290 }
3291 unit.x = base->me.x-prev->me.x;
3292 unit.y = base->me.y-prev->me.y;
3293 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3294 if ( ulen!=0 )
3295 unit.x /= ulen, unit.y /= ulen;
3296 }
3297 }
3298 }
3299 if ( base->nonextcp )
3300 base->nextcp = base->me;
3301 else {
3302 base->nextcp.x = base->me.x + len*unit.x;
3303 base->nextcp.y = base->me.y + len*unit.y;
3304 if ( snaptoint ) {
3305 base->nextcp.x = rint(base->nextcp.x);
3306 base->nextcp.y = rint(base->nextcp.y);
3307 } else {
3308 base->nextcp.x = rint(base->nextcp.x*1024)/1024;
3309 base->nextcp.y = rint(base->nextcp.y*1024)/1024;
3310 }
3311 if ( base->next != NULL )
3312 SplineRefigureFixup(base->next);
3313 }
3314 }
3315
3316 void SplineCharDefaultPrevCP(SplinePoint *base) {
3317 SplinePoint *next=NULL, *prev;
3318 bigreal len, nlen, ulen;
3319 BasePoint unit;
3320 extern int snaptoint;
3321
3322 if ( base->prev==NULL )
3323 return;
3324 if ( base->prev->order2 ) {
3325 SplineRefigureFixup(base->prev);
3326 return;
3327 }
3328 if ( !base->prevcpdef ) {
3329 if ( base->pointtype==pt_tangent )
3330 SplineCharTangentPrevCP(base);
3331 return;
3332 }
3333 prev = base->prev->from;
3334 if ( base->next!=NULL )
3335 next = base->next->to;
3336
3337 len = NICE_PROPORTION * sqrt((base->me.x-prev->me.x)*(base->me.x-prev->me.x) +
3338 (base->me.y-prev->me.y)*(base->me.y-prev->me.y));
3339 unit.x = prev->me.x - base->me.x;
3340 unit.y = prev->me.y - base->me.y;
3341 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3342 if ( ulen!=0 )
3343 unit.x /= ulen, unit.y /= ulen;
3344 base->noprevcp = false;
3345
3346 if ( base->pointtype == pt_curve || base->pointtype == pt_hvcurve ) {
3347 if ( next!=NULL && (base->nextcpdef || base->nonextcp)) {
3348 unit.x = prev->me.x - next->me.x;
3349 unit.y = prev->me.y - next->me.y;
3350 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3351 if ( ulen!=0 )
3352 unit.x /= ulen, unit.y /= ulen;
3353 if ( base->pointtype == pt_hvcurve )
3354 BP_HVForce(&unit);
3355 nlen = sqrt((base->nextcp.x-base->me.x)*(base->nextcp.x-base->me.x) +
3356 (base->nextcp.y-base->me.y)*(base->nextcp.y-base->me.y));
3357 base->nextcp.x = base->me.x - nlen*unit.x;
3358 base->nextcp.y = base->me.y - nlen*unit.y;
3359 if ( snaptoint ) {
3360 base->nextcp.x = rint(base->nextcp.x);
3361 base->nextcp.y = rint(base->nextcp.y);
3362 }
3363 SplineRefigureFixup(base->next);
3364 } else if ( next!=NULL ) {
3365 /* The next control point is fixed. So we got to use the same */
3366 /* angle it uses */
3367 unit.x = base->me.x-base->nextcp.x;
3368 unit.y = base->me.y-base->nextcp.y;
3369 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3370 if ( ulen!=0 )
3371 unit.x /= ulen, unit.y /= ulen;
3372 } else {
3373 base->nextcp = base->me;
3374 base->nonextcp = true;
3375 base->nextcpdef = true;
3376 }
3377 if ( base->pointtype == pt_hvcurve )
3378 BP_HVForce(&unit);
3379 } else if ( base->pointtype == pt_corner ) {
3380 if ( prev->pointtype != pt_curve && prev->pointtype != pt_hvcurve ) {
3381 base->noprevcp = true;
3382 }
3383 } else /* tangent */ {
3384 if ( prev->pointtype != pt_curve ) {
3385 base->noprevcp = true;
3386 } else {
3387 if ( next!=NULL ) {
3388 if ( !base->nonextcp ) {
3389 nlen = sqrt((base->nextcp.x-base->me.x)*(base->nextcp.x-base->me.x) +
3390 (base->nextcp.y-base->me.y)*(base->nextcp.y-base->me.y));
3391 base->nextcp.x = base->me.x - nlen*unit.x;
3392 base->nextcp.y = base->me.y - nlen*unit.y;
3393 SplineRefigureFixup(base->next);
3394 }
3395 unit.x = base->me.x-next->me.x;
3396 unit.y = base->me.y-next->me.y;
3397 ulen = sqrt(unit.x*unit.x + unit.y*unit.y);
3398 if ( ulen!=0 )
3399 unit.x /= ulen, unit.y /= ulen;
3400 }
3401 }
3402 }
3403 if ( base->noprevcp )
3404 base->prevcp = base->me;
3405 else {
3406 base->prevcp.x = base->me.x + len*unit.x;
3407 base->prevcp.y = base->me.y + len*unit.y;
3408 if ( snaptoint ) {
3409 base->prevcp.x = rint(base->prevcp.x);
3410 base->prevcp.y = rint(base->prevcp.y);
3411 } else {
3412 base->prevcp.x = rint(base->prevcp.x*1024)/1024;
3413 base->prevcp.y = rint(base->prevcp.y*1024)/1024;
3414 }
3415 if ( base->prev!=NULL )
3416 SplineRefigureFixup(base->prev);
3417 }
3418 }
3419
3420 void SPHVCurveForce(SplinePoint *sp) {
3421 BasePoint unit;
3422 bigreal len, dot;
3423 if ( sp->prev==NULL || sp->next==NULL || sp->pointtype==pt_corner )
3424 return;
3425
3426 if ( sp->pointtype==pt_hvcurve &&
3427 !sp->nonextcp && !sp->noprevcp ) {
3428 if ( sp->prev!=NULL && sp->prev->order2 ) {
3429 SplineRefigureFixup(sp->prev);
3430 SplineRefigureFixup(sp->next);
3431 return;
3432 }
3433
3434 unit.x = sp->nextcp.x-sp->prevcp.x;
3435 unit.y = sp->nextcp.y-sp->prevcp.y;
3436 len = sqrt(unit.x*unit.x + unit.y*unit.y);
3437 if ( len==0 )
3438 return;
3439 unit.x /= len; unit.y /= len;
3440 BP_HVForce(&unit);
3441 dot = (sp->nextcp.x-sp->me.x)*unit.x + (sp->nextcp.y-sp->me.y)*unit.y;
3442 sp->nextcp.x = dot * unit.x + sp->me.x;
3443 sp->nextcp.y = dot * unit.y + sp->me.y;
3444 dot = (sp->prevcp.x-sp->me.x)*unit.x + (sp->prevcp.y-sp->me.y)*unit.y;
3445 sp->prevcp.x = dot * unit.x + sp->me.x;
3446 sp->prevcp.y = dot * unit.y + sp->me.y;
3447 SplineRefigure(sp->prev); SplineRefigure(sp->next);
3448 }
3449 }
3450
3451 void SPSmoothJoint(SplinePoint *sp) {
3452 BasePoint unitn, unitp;
3453 bigreal len, dot, dotn, dotp;
3454 if ( sp->prev==NULL || sp->next==NULL || sp->pointtype==pt_corner )
3455 return;
3456
3457 if ( (sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve ) &&
3458 !sp->nonextcp && !sp->noprevcp ) {
3459 unitn.x = sp->nextcp.x-sp->me.x;
3460 unitn.y = sp->nextcp.y-sp->me.y;
3461 len = sqrt(unitn.x*unitn.x + unitn.y*unitn.y);
3462 if ( len==0 )
3463 return;
3464 unitn.x /= len; unitn.y /= len;
3465 unitp.x = sp->me.x - sp->prevcp.x;
3466 unitp.y = sp->me.y - sp->prevcp.y;
3467 len = sqrt(unitp.x*unitp.x + unitp.y*unitp.y);
3468 if ( len==0 )
3469 return;
3470 unitp.x /= len; unitp.y /= len;
3471 dotn = unitp.y*(sp->nextcp.x-sp->me.x) - unitp.x*(sp->nextcp.y-sp->me.y);
3472 dotp = unitn.y*(sp->me.x - sp->prevcp.x) - unitn.x*(sp->me.y - sp->prevcp.y);
3473 sp->nextcp.x -= dotn*unitp.y/2;
3474 sp->nextcp.y -= -dotn*unitp.x/2;
3475 sp->prevcp.x += dotp*unitn.y/2;
3476 sp->prevcp.y += -dotp*unitn.x/2;
3477 SplineRefigure(sp->prev); SplineRefigure(sp->next);
3478 }
3479 if ( sp->pointtype==pt_tangent && !sp->nonextcp ) {
3480 unitp.x = sp->me.x - sp->prev->from->me.x;
3481 unitp.y = sp->me.y - sp->prev->from->me.y;
3482 len = sqrt(unitp.x*unitp.x + unitp.y*unitp.y);
3483 if ( len!=0 ) {
3484 unitp.x /= len; unitp.y /= len;
3485 dot = unitp.y*(sp->nextcp.x-sp->me.x) - unitp.x*(sp->nextcp.y-sp->me.y);
3486 sp->nextcp.x -= dot*unitp.y;
3487 sp->nextcp.y -= -dot*unitp.x;
3488 SplineRefigure(sp->next);
3489 }
3490 }
3491 if ( sp->pointtype==pt_tangent && !sp->noprevcp ) {
3492 unitn.x = sp->nextcp.x-sp->me.x;
3493 unitn.y = sp->nextcp.y-sp->me.y;
3494 len = sqrt(unitn.x*unitn.x + unitn.y*unitn.y);
3495 if ( len!=0 ) {
3496 unitn.x /= len; unitn.y /= len;
3497 dot = unitn.y*(sp->me.x-sp->prevcp.x) - unitn.x*(sp->me.y-sp->prevcp.y);
3498 sp->prevcp.x += dot*unitn.y;
3499 sp->prevcp.y += -dot*unitn.x;
3500 SplineRefigure(sp->prev);
3501 }
3502 }
3503 }
3504
3505 void SPTouchControl(SplinePoint *sp,BasePoint *which, int order2)
3506 {
3507 BasePoint to = *which;
3508 SPAdjustControl( sp, which, &to, order2 );
3509 }
3510
3511
3512 void SPAdjustControl(SplinePoint *sp,BasePoint *cp, BasePoint *to,int order2) {
3513 BasePoint *othercp = cp==&sp->nextcp?&sp->prevcp:&sp->nextcp;
3514 int refig = false, otherchanged = false;
3515
3516 if ( sp->ttfindex==0xffff && order2 ) {
3517 /* If the point itself is implied, then it's the control points that */
3518 /* are fixed. Moving a CP should move the implied point so that it */
3519 /* continues to be in the right place */
3520 sp->me.x = (to->x+othercp->x)/2;
3521 sp->me.y = (to->y+othercp->y)/2;
3522 *cp = *to;
3523 refig = true;
3524 } else if ( sp->pointtype==pt_corner ) {
3525 *cp = *to;
3526 } else if ( sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve ) {
3527 if ( sp->pointtype==pt_hvcurve ) {
3528 BasePoint diff;
3529 diff.x = to->x - sp->me.x;
3530 diff.y = to->y - sp->me.y;
3531 BP_HVForce(&diff);
3532 cp->x = sp->me.x + diff.x;
3533 cp->y = sp->me.y + diff.y;
3534 } else {
3535 *cp = *to;
3536 }
3537 if (( cp->x!=sp->me.x || cp->y!=sp->me.y ) &&
3538 (!order2 ||
3539 (cp==&sp->nextcp && sp->next!=NULL && sp->next->to->ttfindex==0xffff) ||
3540 (cp==&sp->prevcp && sp->prev!=NULL && sp->prev->from->ttfindex==0xffff)) ) {
3541 bigreal len1, len2;
3542 len1 = sqrt((cp->x-sp->me.x)*(cp->x-sp->me.x) +
3543 (cp->y-sp->me.y)*(cp->y-sp->me.y));
3544 len2 = sqrt((othercp->x-sp->me.x)*(othercp->x-sp->me.x) +
3545 (othercp->y-sp->me.y)*(othercp->y-sp->me.y));
3546 len2 /= len1;
3547 othercp->x = len2 * (sp->me.x-cp->x) + sp->me.x;
3548 othercp->y = len2 * (sp->me.y-cp->y) + sp->me.y;
3549 otherchanged = true;
3550 if ( sp->next!=NULL && othercp==&sp->nextcp ) {
3551 if ( order2 ) sp->next->to->prevcp = *othercp;
3552 SplineRefigure(sp->next);
3553 } else if ( sp->prev!=NULL && othercp==&sp->prevcp ) {
3554 if ( order2 ) sp->prev->from->nextcp = *othercp;
3555 SplineRefigure(sp->prev);
3556 }
3557 }
3558 if ( cp==&sp->nextcp ) sp->prevcpdef = false;
3559 else sp->nextcpdef = false;
3560 } else {
3561 BasePoint *bp;
3562 if ( cp==&sp->prevcp && sp->next!=NULL )
3563 bp = &sp->next->to->me;
3564 else if ( cp==&sp->nextcp && sp->prev!=NULL )
3565 bp = &sp->prev->from->me;
3566 else
3567 bp = NULL;
3568 if ( bp!=NULL ) {
3569 real angle = atan2(bp->y-sp->me.y,bp->x-sp->me.x);
3570 real len = sqrt((bp->x-sp->me.x)*(bp->x-sp->me.x) + (bp->y-sp->me.y)*(bp->y-sp->me.y));
3571 real dotprod =
3572 ((to->x-sp->me.x)*(bp->x-sp->me.x) +
3573 (to->y-sp->me.y)*(bp->y-sp->me.y));
3574 if ( len!=0 ) {
3575 dotprod /= len;
3576 if ( dotprod>0 ) dotprod = 0;
3577 cp->x = sp->me.x + dotprod*cos(angle);
3578 cp->y = sp->me.y + dotprod*sin(angle);
3579 }
3580 }
3581 }
3582
3583 if ( order2 ) {
3584 if ( (cp==&sp->nextcp || otherchanged) && sp->next!=NULL ) {
3585 SplinePoint *osp = sp->next->to;
3586 if ( osp->ttfindex==0xffff ) {
3587 osp->prevcp = sp->nextcp;
3588 osp->me.x = (osp->prevcp.x+osp->nextcp.x)/2;
3589 osp->me.y = (osp->prevcp.y+osp->nextcp.y)/2;
3590 SplineRefigure(osp->next);
3591 }
3592 }
3593 if ( (cp==&sp->prevcp || otherchanged) && sp->prev!=NULL ) {
3594 SplinePoint *osp = sp->prev->from;
3595 if ( osp->ttfindex==0xffff ) {
3596 osp->nextcp = sp->prevcp;
3597 osp->me.x = (osp->prevcp.x+osp->nextcp.x)/2;
3598 osp->me.y = (osp->prevcp.y+osp->nextcp.y)/2;
3599 SplineRefigure(osp->prev);
3600 }
3601 }
3602 }
3603
3604 if ( cp->x==sp->me.x && cp->y==sp->me.y ) {
3605 if ( cp==&sp->nextcp ) sp->nonextcp = true;
3606 else sp->noprevcp = true;
3607 } else {
3608 if ( cp==&sp->nextcp ) sp->nonextcp = false;
3609 else sp->noprevcp = false;
3610 }
3611 if ( cp==&sp->nextcp ) sp->nextcpdef = false;
3612 else sp->prevcpdef = false;
3613
3614 if ( sp->next!=NULL && cp==&sp->nextcp ) {
3615 if ( order2 && !sp->nonextcp ) {
3616 sp->next->to->prevcp = *cp;
3617 sp->next->to->noprevcp = false;
3618 }
3619 SplineRefigureFixup(sp->next);
3620 }
3621 if ( sp->prev!=NULL && cp==&sp->prevcp ) {
3622 if ( order2 && !sp->noprevcp ) {
3623 sp->prev->from->nextcp = *cp;
3624 sp->prev->from->nonextcp = false;
3625 }
3626 SplineRefigureFixup(sp->prev);
3627 }
3628 if ( refig ) {
3629 SplineRefigure(sp->prev);
3630 SplineRefigure(sp->next);
3631 }
3632 }
3633
3634 int PointListIsSelected(SplinePointList *spl) {
3635 int anypoints = 0;
3636 Spline *spline, *first;
3637 int i;
3638
3639 first = NULL;
3640 if ( spl->first->selected ) anypoints = true;
3641 for ( spline=spl->first->next; spline!=NULL && spline!=first && !anypoints; spline = spline->to->next ) {
3642 if ( spline->to->selected ) anypoints = true;
3643 if ( first == NULL ) first = spline;
3644 }
3645 if ( !anypoints && spl->spiro_cnt!=0 ) {
3646 for ( i=0; i<spl->spiro_cnt-1; ++i )
3647 if ( SPIRO_SELECTED(&spl->spiros[i]))
3648 return( true );
3649 }
3650 return( anypoints );
3651 }
3652
3653 SplineSet *SplineSetReverse(SplineSet *spl) {
3654 Spline *spline, *first, *next;
3655 BasePoint tp;
3656 SplinePoint *temp;
3657 int flag;
3658 int i;
3659 /* reverse the splineset so that what was the start point becomes the end */
3660 /* and vice versa. This entails reversing every individual spline, and */
3661 /* each point */
3662
3663 first = NULL;
3664 spline = spl->first->next;
3665 if ( spline==NULL )
3666 return( spl ); /* Only one point, reversal is meaningless */
3667
3668 tp = spline->from->nextcp;
3669 spline->from->nextcp = spline->from->prevcp;
3670 spline->from->prevcp = tp;
3671 flag = spline->from->nonextcp;
3672 spline->from->nonextcp = spline->from->noprevcp;
3673 spline->from->noprevcp = flag;
3674 flag = spline->from->nextcpdef;
3675 spline->from->nextcpdef = spline->from->prevcpdef;
3676 spline->from->prevcpdef = flag;
3677 flag = spline->from->nextcpselected;
3678 spline->from->nextcpselected = spline->from->prevcpselected;
3679 spline->from->prevcpselected = flag;
3680
3681 for ( ; spline!=NULL && spline!=first; spline=next ) {
3682 next = spline->to->next;
3683
3684 if ( spline->to!=spl->first ) { /* On a closed spline don't want to reverse the first point twice */
3685 tp = spline->to->nextcp;
3686 spline->to->nextcp = spline->to->prevcp;
3687 spline->to->prevcp = tp;
3688 flag = spline->to->nonextcp;
3689 spline->to->nonextcp = spline->to->noprevcp;
3690 spline->to->noprevcp = flag;
3691 flag = spline->to->nextcpdef;
3692 spline->to->nextcpdef = spline->to->prevcpdef;
3693 spline->to->prevcpdef = flag;
3694 flag = spline->to->nextcpselected;
3695 spline->to->nextcpselected = spline->to->prevcpselected;
3696 spline->to->prevcpselected = flag;
3697 }
3698
3699 temp = spline->to;
3700 spline->to = spline->from;
3701 spline->from = temp;
3702 spline->from->next = spline;
3703 spline->to->prev = spline;
3704 SplineRefigure(spline);
3705 if ( first==NULL ) first = spline;
3706 }
3707
3708 if ( spl->first!=spl->last ) {
3709 temp = spl->first;
3710 spl->first = spl->last;
3711 spl->start_offset = 0;
3712 spl->last = temp;
3713 spl->first->prev = NULL;
3714 spl->last->next = NULL;
3715 }
3716
3717 if ( spl->spiro_cnt>2 ) {
3718 for ( i=(spl->spiro_cnt-1)/2-1; i>=0; --i ) {
3719 spiro_cp temp_cp = spl->spiros[i];
3720 spl->spiros[i] = spl->spiros[spl->spiro_cnt-2-i];
3721 spl->spiros[spl->spiro_cnt-2-i] = temp_cp;
3722 }
3723 if ( (spl->spiros[spl->spiro_cnt-2].ty&0x7f)==SPIRO_OPEN_CONTOUR ) {
3724 spl->spiros[spl->spiro_cnt-2].ty = (spl->spiros[0].ty&0x7f) | (spl->spiros[spl->spiro_cnt-2].ty&0x80);
3725 spl->spiros[0].ty = SPIRO_OPEN_CONTOUR | (spl->spiros[0].ty&0x80);
3726 }
3727 for ( i=spl->spiro_cnt-2; i>=0; --i ) {
3728 if ( (spl->spiros[i].ty&0x7f) == SPIRO_LEFT )
3729 spl->spiros[i].ty = SPIRO_RIGHT | (spl->spiros[i].ty&0x80);
3730 else if ( (spl->spiros[i].ty&0x7f) == SPIRO_RIGHT )
3731 spl->spiros[i].ty = SPIRO_LEFT | (spl->spiros[i].ty&0x80);
3732 }
3733 }
3734 return( spl );
3735 }
3736
3737 void SplineSetsUntick(SplineSet *spl) {
3738 Spline *spline, *first;
3739
3740 while ( spl!=NULL ) {
3741 first = NULL;
3742 spl->first->isintersection = false;
3743 for ( spline=spl->first->next; spline!=first && spline!=NULL; spline = spline->to->next ) {
3744 spline->isticked = false;
3745 spline->isneeded = false;
3746 spline->isunneeded = false;
3747 spline->ishorvert = false;
3748 spline->to->isintersection = false;
3749 if ( first==NULL ) first = spline;
3750 }
3751 spl = spl->next;
3752 }
3753 }
3754
3755 static void SplineSetTick(SplineSet *spl) {
3756 Spline *spline, *first;
3757
3758 first = NULL;
3759 for ( spline=spl->first->next; spline!=first && spline!=NULL; spline = spline->to->next ) {
3760 spline->isticked = true;
3761 if ( first==NULL ) first = spline;
3762 }
3763 }
3764
3765 static SplineSet *SplineSetOfSpline(SplineSet *spl,Spline *search) {
3766 Spline *spline, *first;
3767
3768 while ( spl!=NULL ) {
3769 first = NULL;
3770 for ( spline=spl->first->next; spline!=first && spline!=NULL; spline = spline->to->next ) {
3771 if ( spline==search )
3772 return( spl );
3773 if ( first==NULL ) first = spline;
3774 }
3775 spl = spl->next;
3776 }
3777 return( NULL );
3778 }
3779
3780 int SplineInSplineSet(Spline *spline, SplineSet *spl) {
3781 Spline *first, *s;
3782
3783 first = NULL;
3784 for ( s = spl->first->next; s!=NULL && s!=first; s = s->to->next ) {
3785 if ( s==spline )
3786 return( true );
3787 if ( first==NULL ) first = s;
3788 }
3789 return( false );
3790 }
3791
3792 static void EdgeListReverse(EdgeList *es, SplineSet *spl) {
3793 int i;
3794
3795 if ( es->edges!=NULL ) {
3796 for ( i=0; i<es->cnt; ++i ) {
3797 Edge *e;
3798 for ( e = es->edges[i]; e!=NULL; e = e->esnext ) {
3799 if ( SplineInSplineSet(e->spline,spl)) {
3800 e->up = !e->up;
3801 e->t_mmin = 1-e->t_mmin;
3802 e->t_mmax = 1-e->t_mmax;
3803 e->t_cur = 1-e->t_cur;
3804 }
3805 }
3806 }
3807 }
3808 }
3809
3810 static int SSCheck(SplineSet *base,Edge *active, int up, EdgeList *es,int *changed) {
3811 SplineSet *spl;
3812 if ( active->spline->isticked )
3813 return( 0 );
3814 spl = SplineSetOfSpline(base,active->spline);
3815 if ( active->up!=up ) {
3816 SplineSetReverse(spl);
3817 *changed = true;
3818 EdgeListReverse(es,spl);
3819 }
3820 SplineSetTick(spl);
3821 return( 1 );
3822 }
3823
3824 SplineSet *SplineSetsExtractOpen(SplineSet **tbase) {
3825 SplineSet *spl, *openhead=NULL, *openlast=NULL, *prev=NULL, *snext;
3826
3827 for ( spl= *tbase; spl!=NULL; spl = snext ) {
3828 snext = spl->next;
3829 if ( spl->first->prev==NULL ) {
3830 if ( prev==NULL )
3831 *tbase = snext;
3832 else
3833 prev->next = snext;
3834 if ( openhead==NULL )
3835 openhead = spl;
3836 else
3837 openlast->next = spl;
3838 openlast = spl;
3839 spl->next = NULL;
3840 } else
3841 prev = spl;
3842 }
3843 return( openhead );
3844 }
3845
3846 void SplineSetsInsertOpen(SplineSet **tbase,SplineSet *open) {
3847 SplineSet *e, *p, *spl, *next;
3848
3849 for ( p=NULL, spl=*tbase, e=open; e!=NULL; e = next ) {
3850 next = e->next;
3851 while ( spl!=NULL && spl->first->ttfindex<e->first->ttfindex ) {
3852 p = spl;
3853 spl = spl->next;
3854 }
3855 if ( p==NULL )
3856 *tbase = e;
3857 else
3858 p->next = e;
3859 e->next = spl;
3860 p = e;
3861 }
3862 }
3863
3864 /* The idea behind SplineSetsCorrect is simple. However there are many splinesets */
3865 /* where it is impossible, so bear in mind that this only works for nice */
3866 /* splines. Figure 8's, interesecting splines all cause problems */
3867 /* The outermost spline should be clockwise (up), the next splineset we find */
3868 /* should be down, if it isn't reverse it (if it's already been dealt with */
3869 /* then ignore it) */
3870 SplineSet *SplineSetsCorrect(SplineSet *base,int *changed) {
3871 SplineSet *spl;
3872 int sscnt, check_cnt;
3873 EdgeList es;
3874 DBounds b;
3875 Edge *active=NULL, *apt, *pr, *e;
3876 int i, winding;
3877
3878 *changed = false;
3879
3880 SplineSetsUntick(base);
3881 for (sscnt=0,spl=base; spl!=NULL; spl=spl->next, ++sscnt );
3882
3883 SplineSetFindBounds(base,&b);
3884 memset(&es,'\0',sizeof(es));
3885 es.scale = 1.0;
3886 es.mmin = floor(b.miny*es.scale);
3887 es.mmax = ceil(b.maxy*es.scale);
3888 es.omin = b.minx*es.scale;
3889 es.omax = b.maxx*es.scale;
3890 es.layer = ly_fore; /* Not meaningful */
3891
3892 /* Give up if we are given unreasonable values (ie. if rounding errors might screw us up) */
3893 if ( es.mmin<1e5 && es.mmax>-1e5 && es.omin<1e5 && es.omax>-1e5 ) {
3894 es.cnt = (int) (es.mmax-es.mmin) + 1;
3895 es.edges = calloc(es.cnt,sizeof(Edge *));
3896 es.interesting = calloc(es.cnt,sizeof(char));
3897 es.sc = NULL;
3898 es.major = 1; es.other = 0;
3899 FindEdgesSplineSet(base,&es,false);
3900
3901 check_cnt = 0;
3902 for ( i=0; i<es.cnt && check_cnt<sscnt; ++i ) {
3903 active = ActiveEdgesRefigure(&es,active,i);
3904 if ( es.edges[i]!=NULL )
3905 continue; /* Just too hard to get the edges sorted when we are at a start vertex */
3906 if ( /*es.edges[i]==NULL &&*/ !es.interesting[i] &&
3907 !(i>0 && es.interesting[i-1]) && !(i>0 && es.edges[i-1]!=NULL) &&
3908 !(i<es.cnt-1 && es.edges[i+1]!=NULL) &&
3909 !(i<es.cnt-1 && es.interesting[i+1])) /* interesting things happen when we add (or remove) entries */
3910 continue; /* and where we have extrema */
3911 for ( apt=active; apt!=NULL; apt = e) {
3912 check_cnt += SSCheck(base,apt,true,&es,changed);
3913 winding = apt->up?1:-1;
3914 for ( pr=apt, e=apt->aenext; e!=NULL && winding!=0; pr=e, e=e->aenext ) {
3915 if ( !e->spline->isticked )
3916 check_cnt += SSCheck(base,e,winding<0,&es,changed);
3917 if ( pr->up!=e->up )
3918 winding += (e->up?1:-1);
3919 else if ( (pr->before==e || pr->after==e ) &&
3920 (( pr->mmax==i && e->mmin==i ) ||
3921 ( pr->mmin==i && e->mmax==i )) )
3922 /* This just continues the line and doesn't change count */;
3923 else
3924 winding += (e->up?1:-1);
3925 }
3926 /* color a horizontal line that comes out of the last vertex */
3927 if ( e!=NULL && (e->before==pr || e->after==pr) &&
3928 (( pr->mmax==i && e->mmin==i ) ||
3929 ( pr->mmin==i && e->mmax==i )) ) {
3930 pr = e;
3931 e = e->aenext;
3932 }
3933 }
3934 }
3935 FreeEdges(&es);
3936 }
3937 return( base );
3938 }
3939
3940 SplineSet *SplineSetsAntiCorrect(SplineSet *base) {
3941 int changed;
3942 SplineSet *spl;
3943
3944 SplineSetsCorrect(base,&changed);
3945 for ( spl = base; spl!=NULL; spl = spl->next )
3946 SplineSetReverse(spl);
3947 return( base );
3948 }
3949
3950 /* This is exactly the same as SplineSetsCorrect, but instead of correcting */
3951 /* problems we merely search for them and if we find any return the first */
3952 SplineSet *SplineSetsDetectDir(SplineSet **_base,int *_lastscan) {
3953 SplineSet *ret, *base;
3954 EIList el;
3955 EI *active=NULL, *apt, *pr, *e;
3956 int i, winding,change,waschange;
3957 int lastscan = *_lastscan;
3958 SplineChar dummy;
3959 Layer layers[2];
3960 int cnt;
3961
3962 base = *_base;
3963
3964 memset(&el,'\0',sizeof(el));
3965 memset(&dummy,'\0',sizeof(dummy));
3966 memset(layers,0,sizeof(layers));
3967 el.layer = ly_fore;
3968 dummy.layers = layers;
3969 dummy.layer_cnt = 2;
3970 dummy.layers[ly_fore].splines = base;
3971 ELFindEdges(&dummy,&el);
3972 if ( el.coordmax[1]-el.coordmin[1] > 1.e6 ) {
3973 LogError( _("Warning: Unreasonably big splines. They will be ignored.\n") );
3974 return( NULL );
3975 }
3976 el.major = 1;
3977 ELOrder(&el,el.major);
3978
3979 ret = NULL;
3980 waschange = false;
3981 for ( i=0; i<el.cnt && ret==NULL; ++i ) {
3982 active = EIActiveEdgesRefigure(&el,active,i,1,&change);
3983 if ( i<=lastscan )
3984 continue;
3985 for ( apt=active, cnt=0; apt!=NULL; apt = apt->aenext , ++cnt );
3986 if ( el.ordered[i]!=NULL || el.ends[i] || cnt&1 ) {
3987 waschange = change;
3988 continue; /* Just too hard to get the edges sorted when we are at a start vertex */
3989 }
3990 if ( !( waschange || change || el.ends[i] || el.ordered[i]!=NULL ||
3991 (i!=el.cnt-1 && (el.ends[i+1] || el.ordered[i+1]!=NULL)) ))
3992 continue;
3993 waschange = change;
3994 for ( apt=active; apt!=NULL && ret==NULL; apt = e) {
3995 if ( EISkipExtremum(apt,i+el.low,1)) {
3996 e = apt->aenext->aenext;
3997 continue;
3998 }
3999 if ( !apt->up ) {
4000 ret = SplineSetOfSpline(base,apt->spline);
4001 break;
4002 }
4003 winding = apt->up?1:-1;
4004 for ( pr=apt, e=apt->aenext; e!=NULL && winding!=0; pr=e, e=e->aenext ) {
4005 if ( EISkipExtremum(e,i+el.low,1)) {
4006 e = e->aenext;
4007 continue;
4008 }
4009 if ( pr->up!=e->up ) {
4010 if ( (winding<=0 && !e->up) || (winding>0 && e->up )) {
4011 ret = SplineSetOfSpline(base,active->spline);
4012 break;
4013 }
4014 winding += (e->up?1:-1);
4015 } else if ( EISameLine(pr,e,i+el.low,1) )
4016 /* This just continues the line and doesn't change count */;
4017 else {
4018 if ( (winding<=0 && !e->up) || (winding>0 && e->up )) {
4019 ret = SplineSetOfSpline(base,active->spline);
4020 break;
4021 }
4022 winding += (e->up?1:-1);
4023 }
4024 }
4025 }
4026 }
4027 free(el.ordered);
4028 free(el.ends);
4029 ElFreeEI(&el);
4030 *_base = base;
4031 *_lastscan = i;
4032 return( ret );
4033 }
4034
4035 static int _SplinePointListIsClockwise(const SplineSet *spl, int max_depth) {
4036 EIList el;
4037 EI *active=NULL, *apt, *pr, *e;
4038 int i, winding,change,waschange, cnt;
4039 SplineChar dummy;
4040 SplineSet *next;
4041 Layer layers[2];
4042 int cw_cnt=0, ccw_cnt=0, l_cw_cnt, l_ccw_cnt, lines_processed = 0;
4043
4044 memset(&el,'\0',sizeof(el));
4045 memset(&dummy,'\0',sizeof(dummy));
4046 memset(layers,0,sizeof(layers));
4047 el.layer = ly_fore;
4048 dummy.layers = layers;
4049 dummy.layer_cnt = 2;
4050 dummy.layers[ly_fore].splines = (SplineSet *) spl;
4051 dummy.name = "Clockwise Test";
4052 next = spl->next; ((SplineSet *) spl)->next = NULL;
4053 ELFindEdges(&dummy,&el);
4054 if ( el.coordmax[1]-el.coordmin[1] > 1.e6 ) {
4055 LogError( _("Warning: Unreasonably big splines. They will be ignored.\n") );
4056 ((SplineSet *) spl)->next = next;
4057 return( -1 );
4058 }
4059 el.major = 1;
4060 ELOrder(&el,el.major);
4061
4062 waschange = false;
4063 for ( i=0; i<el.cnt ; ++i ) {
4064 l_cw_cnt = l_ccw_cnt = 0;
4065 active = EIActiveEdgesRefigure(&el,active,i,1,&change);
4066 for ( apt=active, cnt=0; apt!=NULL; apt = apt->aenext , ++cnt );
4067 // "Scan line" skip conditions:
4068 // Edge starts or ends on this line
4069 // Edge starts or ends on the following line
4070 // Odd number of edges on this line
4071 // On or immediately after a line marked "change" by EIAER
4072 if ( el.ordered[i]!=NULL || el.ends[i] || cnt&1 ||
4073 waschange || change ||
4074 (i!=el.cnt-1 && (el.ends[i+1] || el.ordered[i+1])) ) {
4075 waschange = change;
4076 continue;
4077 }
4078 waschange = change;
4079 for ( apt=active; apt!=NULL; apt = e) {
4080 if ( EISkipExtremum(apt,i+el.low,1)) {
4081 e = apt->aenext->aenext;
4082 continue;
4083 }
4084 if ( apt->up )
4085 ++l_cw_cnt;
4086 else
4087 ++l_ccw_cnt;
4088 if ( (cw_cnt + l_cw_cnt)!=0 && (ccw_cnt + l_ccw_cnt)!=0 ) {
4089 ((SplineSet *) spl)->next = next;
4090 return( -1 );
4091 }
4092 winding = apt->up?1:-1;
4093 for ( pr=apt, e=apt->aenext; e!=NULL && winding!=0; pr=e, e=e->aenext ) {
4094 if ( EISkipExtremum(e,i+el.low,1)) {
4095 e = e->aenext;
4096 continue;
4097 }
4098 if ( pr->up!=e->up ) {
4099 if ( (winding<=0 && !e->up) || (winding>0 && e->up )) {
4100 // This is an erroneous condition... but I don't think
4101 // it can actually happen with a single contour. I
4102 // think it is more likely this means a rounding error
4103 // and a problem in my algorithm
4104 l_cw_cnt = l_ccw_cnt = 0;
4105 break;
4106 }
4107 winding += (e->up?1:-1);
4108 } else if ( EISameLine(pr,e,i+el.low,1) )
4109 // This just continues the line and doesn't change count
4110 ;
4111 else {
4112 if ( (winding<=0 && !e->up) || (winding>0 && e->up )) {
4113 l_cw_cnt = l_ccw_cnt = 0;
4114 break;
4115 }
4116 winding += (e->up?1:-1);
4117 }
4118 }
4119 }
4120 cw_cnt += l_cw_cnt;
4121 ccw_cnt += l_ccw_cnt;
4122 if ( l_cw_cnt!=0 || l_ccw_cnt!=0 )
4123 ++lines_processed;
4124 }
4125 free(el.ordered);
4126 free(el.ends);
4127 ElFreeEI(&el);
4128
4129 ((SplineSet *) spl)->next = next;
4130
4131 if ( ( lines_processed > 4 && ((float) lines_processed / el.cnt) > .33 )
4132 || ( max_depth && lines_processed > 0 ) ) {
4133 if ( cw_cnt!=0 && ccw_cnt==0 )
4134 return true;
4135 else if ( cw_cnt==0 && ccw_cnt!=0 )
4136 return false;
4137 else
4138 return -1;
4139 }
4140
4141 return -2;
4142 }
4143
4144 int SplinePointListIsClockwise(const SplineSet *spl) {
4145 SplineSet *cpy;
4146 const SplineSet *pass;
4147 SplinePoint *sp;
4148 int r, depth=0, mag=1, y, ymin=INT_MAX, ymax=INT_MIN, pt_cnt=0;
4149
4150 while ( depth<3 ) {
4151 if ( mag!=1 ) {
4152 cpy = SplinePointListCopy1(spl);
4153 real trans[6] = { mag, 0.0, 0.0, mag, 0.0, 0.0 };
4154 SplinePointListTransformExtended(cpy,trans,tpt_AllPoints,
4155 tpmask_dontTrimValues);
4156 pass = cpy;
4157 } else {
4158 cpy = NULL;
4159 pass = spl;
4160 }
4161 r = _SplinePointListIsClockwise(pass, depth==2);
4162 if ( cpy!=NULL )
4163 SplinePointListFree(cpy);
4164 if ( r>=-1 )
4165 return r;
4166 // Bad run, prepare for next
4167 if ( depth==0 ) {
4168 // Check for open or single-point splines and
4169 // further magnify small splines
4170 for ( sp = spl->first; ; ) {
4171 if ( sp->next==NULL )
4172 return -1; // Open Spline
4173 ++pt_cnt;
4174 y = floor(sp->me.y);
4175 if ( y < ymin )
4176 ymin = y;
4177 y = ceil(sp->me.y);
4178 if ( y > ymax )
4179 ymax = y;
4180 sp = sp->next->to;
4181 if ( sp==spl->first )
4182 break;
4183 }
4184 if ( pt_cnt==1 )
4185 return -1; // Single point spline
4186 y = ymax - ymin + 1;
4187 if ( y < pt_cnt + 7 )
4188 mag = (int) (7 + pt_cnt)/y;
4189 }
4190 mag *= 3;
4191 ++depth;
4192 }
4193 mag /= 3;
4194 LogError( _("Warning: SplinePointListIsClockwise found no usable line even at %dx magnification.\n"), mag );
4195 return -1;
4196 }
4197
4198 /* Since this function now deals with 4 arbitrarily selected points, */
4199 /* it has to try to combine them by different ways in order to see */
4200 /* if they actually can specify a diagonal stem. The reordered points */
4201 /* are placed back to array passed to the function.*/
4202 int PointsDiagonalable( SplineFont *sf,BasePoint **bp,BasePoint *unit ) {
4203 BasePoint *line1[2], *line2[2], *temp, *base;
4204 BasePoint unit1, unit2;
4205 int i, j, k;
4206 bigreal dist_error_diag, len1, len2, width, dot;
4207 bigreal off1, off2;
4208
4209 for ( i=0; i<4; i++ ) {
4210 if ( bp[i] == NULL )
4211 return( false );
4212 }
4213
4214 dist_error_diag = 0.0065 * ( sf->ascent + sf->descent );
4215 /* Assume that the first point passed to the function is the starting */
4216 /* point of the first of two vectors. Then try all possible combinations */
4217 /* (there are 3), ensure the vectors are consistantly ordered, and */
4218 /* check if they are parallel.*/
4219 base = bp[0];
4220 for ( i=1; i<4; i++ ) {
4221 line1[0] = base; line1[1] = bp[i];
4222
4223 k=0;
4224 for ( j=1; j<4; j++ ) {
4225 if ( j != i )
4226 line2[k++] = bp[j];
4227 }
4228 unit1.x = line1[1]->x - line1[0]->x;
4229 unit1.y = line1[1]->y - line1[0]->y;
4230 unit2.x = line2[1]->x - line2[0]->x;
4231 unit2.y = line2[1]->y - line2[0]->y;
4232 /* No horizontal, vertical edges */
4233 if ( unit1.x == 0 || unit1.y == 0 || unit2.x == 0 || unit2.y == 0 )
4234 continue;
4235 len1 = sqrt( pow( unit1.x,2 ) + pow( unit1.y,2 ));
4236 len2 = sqrt( pow( unit2.x,2 ) + pow( unit2.y,2 ));
4237 unit1.x /= len1; unit1.y /= len1;
4238 unit2.x /= len2; unit2.y /= len2;
4239 dot = unit1.x * unit2.y - unit1.y * unit2.x;
4240 /* Units parallel */
4241 if ( dot <= -.05 || dot >= .05 )
4242 continue;
4243 /* Ensure vectors point by such a way that the angle is between 90 and 270 degrees */
4244 if ( unit1.x < 0 ) {
4245 temp = line1[0]; line1[0] = line1[1]; line1[1] = temp;
4246 unit1.x = -unit1.x; unit1.y = -unit1.y;
4247 }
4248 if ( unit2.x < 0 ) {
4249 temp = line2[0]; line2[0] = line2[1]; line2[1] = temp;
4250 unit2.x = -unit2.x; unit2.y = -unit2.y;
4251 }
4252 off1 = ( line1[1]->x - line1[0]->x ) * unit2.y -
4253 ( line1[1]->y - line1[0]->y ) * unit2.x;
4254 off2 = ( line2[1]->x - line2[0]->x ) * unit1.y -
4255 ( line2[1]->y - line2[0]->y ) * unit1.x;
4256 if ( len1 > len2 && fabs( off2 ) < 2*dist_error_diag ) *unit = unit1;
4257 else if ( fabs( off1 ) < 2*dist_error_diag ) *unit = unit2;
4258 else
4259 continue;
4260 width = ( line2[0]->x - line1[0]->x ) * unit->y -
4261 ( line2[0]->y - line1[0]->y ) * unit->x;
4262 /* Make sure this is a real line, rather than just two */
4263 /* short spline segments which occasionally have happened to be */
4264 /* parallel. This is necessary to correctly handle things which may */
4265 /* be "diagonalable" in 2 different directions (like slash in some */
4266 /* designs). */
4267 if ( fabs( width ) > len1 || fabs( width ) > len2 )
4268 continue;
4269 /* Make sure line2 is further right than line1 */
4270 if ( width < 0 ) {
4271 temp = line1[0]; line1[0] = line2[0]; line2[0] = temp;
4272 temp = line1[1]; line1[1] = line2[1]; line2[1] = temp;
4273 }
4274 bp[0] = line1[0];
4275 bp[1] = line2[0];
4276 bp[2] = line1[1];
4277 bp[3] = line2[1];
4278 return( true );
4279 }
4280 return( false );
4281 }
4282
4283 int SplineTurningCCWAt(Spline *s, bigreal t) {
4284 bigreal tmp = SecondDerivative(s, t);
4285 // For missing curvatures take a very small step away and try again.
4286 if ( RealWithin(tmp,0,1e-9) ) {
4287 tmp = SecondDerivative(s, (t+1e-8 <= 1.0) ? t+1e-8 : t-1e-8 );
4288 }
4289 return tmp > 0;
4290 }
4291