diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineutil2.c')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineutil2.c | 2329 |
1 files changed, 2329 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineutil2.c b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineutil2.c new file mode 100644 index 00000000000..43626aec6dc --- /dev/null +++ b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineutil2.c @@ -0,0 +1,2329 @@ +/* Copyright (C) 2000-2008 by George Williams */ +/* + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + + * The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO + * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "pfaedit.h" +#include <math.h> +#include "ustring.h" +#include "chardata.h" +#include <unistd.h> +#include <time.h> +#include <stdlib.h> +#include "views.h" /* For SCCharChangedUpdate */ + +int new_em_size = 1000; +int new_fonts_are_order2 = false; +int loaded_fonts_same_as_new = false; +int default_fv_row_count = 4; +int default_fv_col_count = 16; +int default_fv_font_size = 24; +int default_fv_antialias=true; +int default_fv_bbsized=true; +int snaptoint=0; + +/*#define DEBUG 1*/ + +int RealNear(real a,real b) { + real d; + +#if 0 /* def FONTFORGE_CONFIG_USE_DOUBLE*/ + if ( a==0 ) +return( b>-1e-8 && b<1e-8 ); + if ( b==0 ) +return( a>-1e-8 && a<1e-8 ); + + d = a/(1024*1024.); + if ( d<0 ) d = -d; +return( b>a-d && b<a+d ); +#else /* For floats */ + if ( a==0 ) +return( b>-1e-5 && b<1e-5 ); + if ( b==0 ) +return( a>-1e-5 && a<1e-5 ); + + d = a/(1024*64.); + if ( d<0 ) d = -d; +return( b>a-d && b<a+d ); +#endif +} + +int RealNearish(real a,real b) { + + if ( a-b<.001 && a-b>-.001 ) +return( true ); +return( false ); +} + +int RealApprox(real a,real b) { + + if ( a==0 ) { + if ( b<.0001 && b>-.0001 ) +return( true ); + } else if ( b==0 ) { + if ( a<.0001 && a>-.0001 ) +return( true ); + } else { + a /= b; + if ( a>=.95 && a<=1.05 ) +return( true ); + } +return( false ); +} + +int RealWithin(real a,real b,real fudge) { + +return( b>=a-fudge && b<=a+fudge ); +} + +int RealRatio(real a,real b,real fudge) { + + if ( b==0 ) +return( RealWithin(a,b,fudge)); + +return( RealWithin(a/b,1.0,fudge)); +} + +static int MinMaxWithin(Spline *spline) { + extended dx, dy; + int which; + extended t1, t2; + extended w; + /* We know that this "spline" is basically one dimensional. As long as its*/ + /* extrema are between the start and end points on that line then we can */ + /* treat it as a line. If the extrema are way outside the line segment */ + /* then it's a line that backtracks on itself */ + + if ( (dx = spline->to->me.x - spline->from->me.x)<0 ) dx = -dx; + if ( (dy = spline->to->me.y - spline->from->me.y)<0 ) dy = -dy; + which = dx<dy; + SplineFindExtrema(&spline->splines[which],&t1,&t2); + if ( t1==-1 ) +return( true ); + w = ((spline->splines[which].a*t1 + spline->splines[which].b)*t1 + + spline->splines[which].c)*t1 + spline->splines[which].d; + if ( RealNear(w, (&spline->to->me.x)[which]) || RealNear(w, (&spline->from->me.x)[which]) ) + /* Close enough */; + else if ( (w<(&spline->to->me.x)[which] && w<(&spline->from->me.x)[which]) || + (w>(&spline->to->me.x)[which] && w>(&spline->from->me.x)[which]) ) +return( false ); /* Outside */ + + w = ((spline->splines[which].a*t2 + spline->splines[which].b)*t2 + + spline->splines[which].c)*t2 + spline->splines[which].d; + if ( RealNear(w, (&spline->to->me.x)[which]) || RealNear(w, (&spline->from->me.x)[which]) ) + /* Close enough */; + else if ( (w<(&spline->to->me.x)[which] && w<(&spline->from->me.x)[which]) || + (w>(&spline->to->me.x)[which] && w>(&spline->from->me.x)[which]) ) +return( false ); /* Outside */ + +return( true ); +} + +int SplineIsLinear(Spline *spline) { + double t1,t2, t3,t4; + int ret; + + if ( spline->knownlinear ) +return( true ); + if ( spline->knowncurved ) +return( false ); + + if ( spline->splines[0].a==0 && spline->splines[0].b==0 && + spline->splines[1].a==0 && spline->splines[1].b==0 ) +return( true ); + + /* Something is linear if the control points lie on the line between the */ + /* two base points */ + + /* Vertical lines */ + if ( RealNear(spline->from->me.x,spline->to->me.x) ) { + ret = RealNear(spline->from->me.x,spline->from->nextcp.x) && + RealNear(spline->from->me.x,spline->to->prevcp.x); + if ( ! ((spline->from->nextcp.y >= spline->from->me.y && + spline->from->nextcp.y <= spline->to->me.y && + spline->to->prevcp.y >= spline->from->me.y && + spline->to->prevcp.y <= spline->to->me.y ) || + (spline->from->nextcp.y <= spline->from->me.y && + spline->from->nextcp.y >= spline->to->me.y && + spline->to->prevcp.y <= spline->from->me.y && + spline->to->prevcp.y >= spline->to->me.y )) ) + ret = MinMaxWithin(spline); + /* Horizontal lines */ + } else if ( RealNear(spline->from->me.y,spline->to->me.y) ) { + ret = RealNear(spline->from->me.y,spline->from->nextcp.y) && + RealNear(spline->from->me.y,spline->to->prevcp.y); + if ( ! ((spline->from->nextcp.x >= spline->from->me.x && + spline->from->nextcp.x <= spline->to->me.x && + spline->to->prevcp.x >= spline->from->me.x && + spline->to->prevcp.x <= spline->to->me.x) || + (spline->from->nextcp.x <= spline->from->me.x && + spline->from->nextcp.x >= spline->to->me.x && + spline->to->prevcp.x <= spline->from->me.x && + spline->to->prevcp.x >= spline->to->me.x)) ) + ret = MinMaxWithin(spline); + } else { + ret = true; + t1 = (spline->from->nextcp.y-spline->from->me.y)/(spline->to->me.y-spline->from->me.y); + t2 = (spline->from->nextcp.x-spline->from->me.x)/(spline->to->me.x-spline->from->me.x); + t3 = (spline->to->me.y-spline->to->prevcp.y)/(spline->to->me.y-spline->from->me.y); + t4 = (spline->to->me.x-spline->to->prevcp.x)/(spline->to->me.x-spline->from->me.x); + ret = (RealApprox(t1,t2) || (RealApprox(t1,0) && RealApprox(t2,0))) && + (RealApprox(t3,t4) || (RealApprox(t3,0) && RealApprox(t4,0))); + if ( ret ) { + if ( t1<0 || t2<0 || t3<0 || t4<0 || + t1>1 || t2>1 || t3>1 || t4>1 ) + ret = MinMaxWithin(spline); + } + } + spline->knowncurved = !ret; + spline->knownlinear = ret; + if ( ret ) { + /* A few places that if the spline is knownlinear then its splines[?] */ + /* are linear. So give the linear version and not that suggested by */ + /* the control points */ + spline->splines[0].a = spline->splines[0].b = 0; + spline->splines[0].d = spline->from->me.x; + spline->splines[0].c = spline->to->me.x-spline->from->me.x; + spline->splines[1].a = spline->splines[1].b = 0; + spline->splines[1].d = spline->from->me.y; + spline->splines[1].c = spline->to->me.y-spline->from->me.y; + } +return( ret ); +} + +int SplineIsLinearMake(Spline *spline) { + + if ( spline->islinear ) +return( true ); + if ( SplineIsLinear(spline)) { + spline->islinear = spline->from->nonextcp = spline->to->noprevcp = true; + spline->from->nextcp = spline->from->me; + if ( spline->from->nonextcp && spline->from->noprevcp ) + spline->from->pointtype = pt_corner; + else if ( spline->from->pointtype == pt_curve || spline->from->pointtype == pt_hvcurve ) + spline->from->pointtype = pt_tangent; + spline->to->prevcp = spline->to->me; + if ( spline->to->nonextcp && spline->to->noprevcp ) + spline->to->pointtype = pt_corner; + else if ( spline->to->pointtype == pt_curve || spline->to->pointtype == pt_hvcurve ) + spline->to->pointtype = pt_tangent; + SplineRefigure(spline); + } +return( spline->islinear ); +} + +static Spline *IsLinearApprox(SplinePoint *from, SplinePoint *to, + TPoint *mid, int cnt, int order2) { + double vx, vy, slope; + int i; + + vx = to->me.x-from->me.x; vy = to->me.y-from->me.y; + if ( vx==0 && vy==0 ) { + for ( i=0; i<cnt; ++i ) + if ( mid[i].x != from->me.x || mid[i].y != from->me.y ) +return( NULL ); + } else if ( fabs(vx)>fabs(vy) ) { + slope = vy/vx; + for ( i=0; i<cnt; ++i ) + if ( !RealWithin(mid[i].y,from->me.y+slope*(mid[i].x-from->me.x),.7) ) +return( NULL ); + } else { + slope = vx/vy; + for ( i=0; i<cnt; ++i ) + if ( !RealWithin(mid[i].x,from->me.x+slope*(mid[i].y-from->me.y),.7) ) +return( NULL ); + } + from->nonextcp = to->noprevcp = true; +return( SplineMake(from,to,order2) ); +} + +/* Least squares tells us that: + | S(xi*ti^3) | | S(ti^6) S(ti^5) S(ti^4) S(ti^3) | | a | + | S(xi*ti^2) | = | S(ti^5) S(ti^4) S(ti^3) S(ti^2) | * | b | + | S(xi*ti) | | S(ti^4) S(ti^3) S(ti^2) S(ti) | | c | + | S(xi) | | S(ti^3) S(ti^2) S(ti) n | | d | + and the definition of a spline tells us: + | x1 | = | 1 1 1 1 | * (a b c d) + | x0 | = | 0 0 0 1 | * (a b c d) +So we're a bit over specified. Let's use the last two lines of least squares +and the 2 from the spline defn. So d==x0. Now we've got three unknowns +and only three equations... + +For order2 splines we've got + | S(xi*ti^2) | | S(ti^4) S(ti^3) S(ti^2) | | b | + | S(xi*ti) | = | S(ti^3) S(ti^2) S(ti) | * | c | + | S(xi) | | S(ti^2) S(ti) n | | d | + and the definition of a spline tells us: + | x1 | = | 1 1 1 | * (b c d) + | x0 | = | 0 0 1 | * (b c d) +=> + d = x0 + b+c = x1-x0 + S(ti^2)*b + S(ti)*c = S(xi)-n*x0 + S(ti^2)*b + S(ti)*(x1-x0-b) = S(xi)-n*x0 + [ S(ti^2)-S(ti) ]*b = S(xi)-S(ti)*(x1-x0) - n*x0 +*/ +static int _ApproximateSplineFromPoints(SplinePoint *from, SplinePoint *to, + TPoint *mid, int cnt, BasePoint *nextcp, BasePoint *prevcp, + int order2) { + double tt, ttn; + int i, j, ret; + double vx[3], vy[3], m[3][3]; + double ts[7], xts[4], yts[4]; + BasePoint nres, pres; + int nrescnt=0, prescnt=0; + double nmin, nmax, pmin, pmax, test, ptest; + double bx, by, cx, cy; + + memset(&nres,0,sizeof(nres)); memset(&pres,0,sizeof(pres)); + + /* Add the initial and end points */ + ts[0] = 2; for ( i=1; i<7; ++i ) ts[i] = 1; + xts[0] = from->me.x+to->me.x; yts[0] = from->me.y+to->me.y; + xts[3] = xts[2] = xts[1] = to->me.x; yts[3] = yts[2] = yts[1] = to->me.y; + nmin = pmin = 0; nmax = pmax = (to->me.x-from->me.x)*(to->me.x-from->me.x)+(to->me.y-from->me.y)*(to->me.y-from->me.y); + for ( i=0; i<cnt; ++i ) { + xts[0] += mid[i].x; + yts[0] += mid[i].y; + ++ts[0]; + tt = mid[i].t; + xts[1] += tt*mid[i].x; + yts[1] += tt*mid[i].y; + ts[1] += tt; + ts[2] += (ttn=tt*tt); + xts[2] += ttn*mid[i].x; + yts[2] += ttn*mid[i].y; + ts[3] += (ttn*=tt); + xts[3] += ttn*mid[i].x; + yts[3] += ttn*mid[i].y; + ts[4] += (ttn*=tt); + ts[5] += (ttn*=tt); + ts[6] += (ttn*=tt); + + test = (mid[i].x-from->me.x)*(to->me.x-from->me.x) + (mid[i].y-from->me.y)*(to->me.y-from->me.y); + if ( test<nmin ) nmin=test; + if ( test>nmax ) nmax=test; + test = (mid[i].x-to->me.x)*(from->me.x-to->me.x) + (mid[i].y-to->me.y)*(from->me.y-to->me.y); + if ( test<pmin ) pmin=test; + if ( test>pmax ) pmax=test; + } + pmin *= 1.2; pmax *= 1.2; nmin *= 1.2; nmax *= 1.2; + + for ( j=0; j<3; ++j ) { + if ( order2 ) { + if ( RealNear(ts[j+2],ts[j+1]) ) + continue; + /* This produces really bad results!!!! But I don't see what I can do to improve it */ + bx = (xts[j]-ts[j+1]*(to->me.x-from->me.x) - ts[j]*from->me.x) / (ts[j+2]-ts[j+1]); + by = (yts[j]-ts[j+1]*(to->me.y-from->me.y) - ts[j]*from->me.y) / (ts[j+2]-ts[j+1]); + cx = to->me.x-from->me.x-bx; + cy = to->me.y-from->me.y-by; + + nextcp->x = from->me.x + cx/2; + nextcp->y = from->me.y + cy/2; + *prevcp = *nextcp; + } else { + vx[0] = xts[j+1]-ts[j+1]*from->me.x; + vx[1] = xts[j]-ts[j]*from->me.x; + vx[2] = to->me.x-from->me.x; /* always use the defn of spline */ + + vy[0] = yts[j+1]-ts[j+1]*from->me.y; + vy[1] = yts[j]-ts[j]*from->me.y; + vy[2] = to->me.y-from->me.y; + + m[0][0] = ts[j+4]; m[0][1] = ts[j+3]; m[0][2] = ts[j+2]; + m[1][0] = ts[j+3]; m[1][1] = ts[j+2]; m[1][2] = ts[j+1]; + m[2][0] = 1; m[2][1] = 1; m[2][2] = 1; + + /* Remove a terms from rows 0 and 1 */ + vx[0] -= ts[j+4]*vx[2]; + vy[0] -= ts[j+4]*vy[2]; + m[0][0] = 0; m[0][1] -= ts[j+4]; m[0][2] -= ts[j+4]; + vx[1] -= ts[j+3]*vx[2]; + vy[1] -= ts[j+3]*vy[2]; + m[1][0] = 0; m[1][1] -= ts[j+3]; m[1][2] -= ts[j+3]; + + if ( fabs(m[1][1])<fabs(m[0][1]) ) { + double temp; + temp = vx[1]; vx[1] = vx[0]; vx[0] = temp; + temp = vy[1]; vy[1] = vy[0]; vy[0] = temp; + temp = m[1][1]; m[1][1] = m[0][1]; m[0][1] = temp; + temp = m[1][2]; m[1][2] = m[0][2]; m[0][2] = temp; + } + /* remove b terms from rows 0 and 2 (first normalize row 1 so m[1][1] is 1*/ + vx[1] /= m[1][1]; + vy[1] /= m[1][1]; + m[1][2] /= m[1][1]; + m[1][1] = 1; + vx[0] -= m[0][1]*vx[1]; + vy[0] -= m[0][1]*vy[1]; + m[0][2] -= m[0][1]*m[1][2]; m[0][1] = 0; + vx[2] -= m[2][1]*vx[1]; + vy[2] -= m[2][1]*vy[1]; + m[2][2] -= m[2][1]*m[1][2]; m[2][1] = 0; + + vx[0] /= m[0][2]; /* This is cx */ + vy[0] /= m[0][2]; /* This is cy */ + /*m[0][2] = 1;*/ + + vx[1] -= m[1][2]*vx[0]; /* This is bx */ + vy[1] -= m[1][2]*vy[0]; /* This is by */ + /* m[1][2] = 0; */ + vx[2] -= m[2][2]*vx[0]; /* This is ax */ + vy[2] -= m[2][2]*vy[0]; /* This is ay */ + /* m[2][2] = 0; */ + + nextcp->x = from->me.x + vx[0]/3; + nextcp->y = from->me.y + vy[0]/3; + prevcp->x = nextcp->x + (vx[0]+vx[1])/3; + prevcp->y = nextcp->y + (vy[0]+vy[1])/3; + } + + test = (nextcp->x-from->me.x)*(to->me.x-from->me.x) + + (nextcp->y-from->me.y)*(to->me.y-from->me.y); + ptest = (prevcp->x-to->me.x)*(from->me.x-to->me.x) + + (prevcp->y-to->me.y)*(from->me.y-to->me.y); + if ( order2 && + (test<nmin || test>nmax || ptest<pmin || ptest>pmax)) + continue; + if ( test>=nmin && test<=nmax ) { + nres.x += nextcp->x; nres.y += nextcp->y; + ++nrescnt; + } + if ( test>=pmin && test<=pmax ) { + pres.x += prevcp->x; pres.y += prevcp->y; + ++prescnt; + } + if ( nrescnt==1 && prescnt==1 ) + break; + } + + ret = 0; + if ( nrescnt>0 ) { + ret |= 1; + nextcp->x = nres.x/nrescnt; + nextcp->y = nres.y/nrescnt; + } else + *nextcp = from->nextcp; + if ( prescnt>0 ) { + ret |= 2; + prevcp->x = pres.x/prescnt; + prevcp->y = pres.y/prescnt; + } else + *prevcp = to->prevcp; + if ( order2 && ret!=3 ) { + nextcp->x = (nextcp->x + prevcp->x)/2; + nextcp->y = (nextcp->y + prevcp->y)/2; + } + if ( order2 ) + *prevcp = *nextcp; +return( ret ); +} + +static void TestForLinear(SplinePoint *from,SplinePoint *to) { + BasePoint off, cpoff, cpoff2; + double len, co, co2; + + /* Did we make a line? */ + off.x = to->me.x-from->me.x; off.y = to->me.y-from->me.y; + len = sqrt(off.x*off.x + off.y*off.y); + if ( len!=0 ) { + off.x /= len; off.y /= len; + cpoff.x = from->nextcp.x-from->me.x; cpoff.y = from->nextcp.y-from->me.y; + len = sqrt(cpoff.x*cpoff.x + cpoff.y*cpoff.y); + if ( len!=0 ) { + cpoff.x /= len; cpoff.y /= len; + } + cpoff2.x = to->prevcp.x-from->me.x; cpoff2.y = to->prevcp.y-from->me.y; + len = sqrt(cpoff2.x*cpoff2.x + cpoff2.y*cpoff2.y); + if ( len!=0 ) { + cpoff2.x /= len; cpoff2.y /= len; + } + co = cpoff.x*off.y - cpoff.y*off.x; co2 = cpoff2.x*off.y - cpoff2.y*off.x; + if ( co<.05 && co>-.05 && co2<.05 && co2>-.05 ) { + from->nextcp = from->me; from->nonextcp = true; + to->prevcp = to->me; to->noprevcp = true; + } else { + Spline temp; + memset(&temp,0,sizeof(temp)); + temp.from = from; temp.to = to; + SplineRefigure(&temp); + if ( SplineIsLinear(&temp)) { + from->nextcp = from->me; from->nonextcp = true; + to->prevcp = to->me; to->noprevcp = true; + } + } + } +} + +/* Find a spline which best approximates the list of intermediate points we */ +/* are given. No attempt is made to fix the slopes */ +Spline *ApproximateSplineFromPoints(SplinePoint *from, SplinePoint *to, + TPoint *mid, int cnt, int order2) { + int ret; + Spline *spline; + BasePoint nextcp, prevcp; + + if ( (spline = IsLinearApprox(from,to,mid,cnt,order2))!=NULL ) +return( spline ); + + ret = _ApproximateSplineFromPoints(from,to,mid,cnt,&nextcp,&prevcp,order2); + + if ( ret&1 ) { + from->nextcp = nextcp; + from->nonextcp = false; + } else { + from->nextcp = from->me; + from->nonextcp = true; + } + if ( ret&2 ) { + to->prevcp = prevcp; + to->noprevcp = false; + } else { + to->prevcp = to->me; + to->noprevcp = true; + } + TestForLinear(from,to); + spline = SplineMake(from,to,order2); +return( spline ); +} + +static double ClosestSplineSolve(Spline1D *sp,double sought,double close_to_t) { + /* We want to find t so that spline(t) = sought */ + /* find the value which is closest to close_to_t */ + /* on error return closetot */ + Spline1D temp; + extended ts[3]; + int i; + double t, best, test; + + temp = *sp; + temp.d -= sought; + CubicSolve(&temp,ts); + best = 9e20; t= close_to_t; + for ( i=0; i<3; ++i ) if ( ts[i]!=-1 ) { + if ( (test=ts[i]-close_to_t)<0 ) test = -test; + if ( test<best ) { + best = test; + t = ts[i]; + } + } + +return( t ); +} + +struct dotbounds { + BasePoint unit; + BasePoint base; + double len; + double min,max; /* If min<0 || max>len the spline extends beyond its endpoints */ +}; + +static double SigmaDeltas(Spline *spline,TPoint *mid, int cnt, DBounds *b, struct dotbounds *db) { + int i, lasti; + double xdiff, ydiff, sum, temp, t, lastt; + SplinePoint *to = spline->to, *from = spline->from; + extended ts[2], x,y; + struct dotbounds db2; + double dot; + + if ( (xdiff = to->me.x-from->me.x)<0 ) xdiff = -xdiff; + if ( (ydiff = to->me.y-from->me.y)<0 ) ydiff = -ydiff; + + sum = 0; lastt = -1; lasti = -1; + for ( i=0; i<cnt; ++i ) { + if ( ydiff>2*xdiff ) { + t = ClosestSplineSolve(&spline->splines[1],mid[i].y,mid[i].t); + } else if ( xdiff>2*ydiff ) { + t = ClosestSplineSolve(&spline->splines[0],mid[i].x,mid[i].t); + } else { + t = (ClosestSplineSolve(&spline->splines[1],mid[i].y,mid[i].t) + + ClosestSplineSolve(&spline->splines[0],mid[i].x,mid[i].t))/2; + } + if ( t==lastt ) /* These last* values appear to be debugging */ + t = lastt + (mid[i].t - mid[lasti].t); + else { + lastt = t; + lasti = i; + } + temp = mid[i].x - ( ((spline->splines[0].a*t+spline->splines[0].b)*t+spline->splines[0].c)*t + spline->splines[0].d ); + sum += temp*temp; + temp = mid[i].y - ( ((spline->splines[1].a*t+spline->splines[1].b)*t+spline->splines[1].c)*t + spline->splines[1].d ); + sum += temp*temp; + } + + /* Ok, we've got distances from a set of points on the old spline to the */ + /* new one. Let's do the reverse: find the extrema of the new and see how*/ + /* close they get to the bounding box of the old */ + /* And get really unhappy if the spline extends beyond the end-points */ + db2.min = 0; db2.max = db->len; + SplineFindExtrema(&spline->splines[0],&ts[0],&ts[1]); + for ( i=0; i<2; ++i ) { + if ( ts[i]!=-1 ) { + x = ((spline->splines[0].a*ts[i]+spline->splines[0].b)*ts[i]+spline->splines[0].c)*ts[i] + spline->splines[0].d; + y = ((spline->splines[1].a*ts[i]+spline->splines[1].b)*ts[i]+spline->splines[1].c)*ts[i] + spline->splines[1].d; + if ( x<b->minx ) + sum += (x-b->minx)*(x-b->minx); + else if ( x>b->maxx ) + sum += (x-b->maxx)*(x-b->maxx); + dot = (x-db->base.x)*db->unit.x + (y-db->base.y)*db->unit.y; + if ( dot<db2.min ) db2.min = dot; + if ( dot>db2.max ) db2.max = dot; + } + } + SplineFindExtrema(&spline->splines[1],&ts[0],&ts[1]); + for ( i=0; i<2; ++i ) { + if ( ts[i]!=-1 ) { + x = ((spline->splines[0].a*ts[i]+spline->splines[0].b)*ts[i]+spline->splines[0].c)*ts[i] + spline->splines[0].d; + y = ((spline->splines[1].a*ts[i]+spline->splines[1].b)*ts[i]+spline->splines[1].c)*ts[i] + spline->splines[1].d; + if ( y<b->miny ) + sum += (y-b->miny)*(y-b->miny); + else if ( y>b->maxy ) + sum += (y-b->maxy)*(y-b->maxy); + dot = (x-db->base.x)*db->unit.x + (y-db->base.y)*db->unit.y; + if ( dot<db2.min ) db2.min = dot; + if ( dot>db2.max ) db2.max = dot; + } + } + + /* Big penalty for going beyond the range of the desired spline */ + if ( db->min==0 && db2.min<0 ) + sum += 10000 + db2.min*db2.min; + else if ( db2.min<db->min ) + sum += 100 + (db2.min-db->min)*(db2.min-db->min); + if ( db->max==db->len && db2.max>db->len ) + sum += 10000 + (db2.max-db->max)*(db2.max-db->max); + else if ( db2.max>db->max ) + sum += 100 + (db2.max-db->max)*(db2.max-db->max); + +return( sum ); +} + +static void ApproxBounds(DBounds *b,TPoint *mid, int cnt, struct dotbounds *db) { + int i; + double dot; + + b->minx = b->maxx = mid[0].x; + b->miny = b->maxy = mid[0].y; + db->min = 0; db->max = db->len; + for ( i=1; i<cnt; ++i ) { + if ( mid[i].x>b->maxx ) b->maxx = mid[i].x; + if ( mid[i].x<b->minx ) b->minx = mid[i].x; + if ( mid[i].y>b->maxy ) b->maxy = mid[i].y; + if ( mid[i].y<b->miny ) b->miny = mid[i].y; + dot = (mid[i].x-db->base.x)*db->unit.x + (mid[i].y-db->base.y)*db->unit.y; + if ( dot<db->min ) db->min = dot; + if ( dot>db->max ) db->max = dot; + } +} + +static int GoodCurve(SplinePoint *sp, int check_prev ) { + double dx, dy, lenx, leny; + + if ( sp->pointtype!=pt_curve && sp->pointtype!=pt_hvcurve ) +return( false ); + if ( check_prev ) { + dx = sp->me.x - sp->prevcp.x; + dy = sp->me.y - sp->prevcp.y; + } else { + dx = sp->me.x - sp->nextcp.x; + dy = sp->me.y - sp->nextcp.y; + } + /* If the cp is very close to the base point the point might as well be a corner */ + if ( dx<0 ) dx = -dx; + if ( dy<0 ) dy = -dy; + if ( dx+dy<1 ) +return( false ); + + if ( check_prev ) { + if ( sp->prev==NULL ) +return( true ); + lenx = sp->me.x - sp->prev->from->me.x; + leny = sp->me.y - sp->prev->from->me.y; + } else { + if ( sp->next==NULL ) +return( true ); + lenx = sp->me.x - sp->next->to->me.x; + leny = sp->me.y - sp->next->to->me.y; + } + if ( lenx<0 ) lenx = -lenx; + if ( leny<0 ) leny = -leny; + if ( 50*(dx+dy) < lenx+leny ) +return( false ); + +return( true ); +} + +#if 0 +static int totcnt_cnt, nocnt_cnt, incr_cnt, curdiff_cnt; +#endif + +/* I used to do a least squares aproach adding two more to the above set of equations */ +/* which held the slopes constant. But that didn't work very well. So instead*/ +/* Then I tried doing the approximation, and then forcing the control points */ +/* to be in line (witht the original slopes), getting a better approximation */ +/* to "t" for each data point and then calculating an error array, approximating*/ +/* it, and using that to fix up the final result */ +/* Then I tried checking various possible cp lengths in the desired directions*/ +/* finding the best one or two, and doing a 2D binary search using that as a */ +/* starting point. */ +/* And sometimes a least squares approach will give us the right answer, so */ +/* try that too. */ +/* This still isn't as good as I'd like it... But I haven't been able to */ +/* improve it further yet */ +#define TRY_CNT 2 +#define DECIMATION 5 +Spline *ApproximateSplineFromPointsSlopes(SplinePoint *from, SplinePoint *to, + TPoint *mid, int cnt, int order2) { + BasePoint tounit, fromunit, ftunit; + double flen,tlen,ftlen; + Spline *spline, temp; + BasePoint nextcp; + int bettern, betterp; + double offn, offp, incrn, incrp, trylen; + int nocnt = 0, totcnt; + double curdiff, bestdiff[TRY_CNT]; + int i,j,besti[TRY_CNT],bestj[TRY_CNT],k,l; + double fdiff, tdiff, fmax, tmax, fdotft, tdotft; + DBounds b; + struct dotbounds db; + double offn_, offp_, finaldiff; + + /* If all the selected points are at the same spot, and one of the */ + /* end-points is also at that spot, then just copy the control point */ + /* But our caller seems to have done that for us */ + + /* If the two end-points are corner points then allow the slope to vary */ + /* Or if one end-point is a tangent but the point defining the tangent's */ + /* slope is being removed then allow the slope to vary */ + /* Except if the slope is horizontal or vertical then keep it fixed */ + if ( ( !from->nonextcp && ( from->nextcp.x==from->me.x || from->nextcp.y==from->me.y)) || + (!to->noprevcp && ( to->prevcp.x==to->me.x || to->prevcp.y==to->me.y)) ) + /* Preserve the slope */; + else if ( ((from->pointtype == pt_corner && from->nonextcp) || + (from->pointtype == pt_tangent && + ((from->nonextcp && from->noprevcp) || !from->noprevcp))) && + ((to->pointtype == pt_corner && to->noprevcp) || + (to->pointtype == pt_tangent && + ((to->nonextcp && to->noprevcp) || !to->nonextcp))) ) { + from->pointtype = to->pointtype = pt_corner; +return( ApproximateSplineFromPoints(from,to,mid,cnt,order2) ); + } + + /* If we are going to honour the slopes of a quadratic spline, there is */ + /* only one possibility */ + if ( order2 ) { + if ( from->nonextcp ) + from->nextcp = from->next->to->me; + if ( to->noprevcp ) + to->prevcp = to->prev->from->me; + from->nonextcp = to->noprevcp = false; + fromunit.x = from->nextcp.x-from->me.x; fromunit.y = from->nextcp.y-from->me.y; + tounit.x = to->prevcp.x-to->me.x; tounit.y = to->prevcp.y-to->me.y; + + if ( !IntersectLines(&nextcp,&from->nextcp,&from->me,&to->prevcp,&to->me) || + (nextcp.x-from->me.x)*fromunit.x + (nextcp.y-from->me.y)*fromunit.y < 0 || + (nextcp.x-to->me.x)*tounit.x + (nextcp.y-to->me.y)*tounit.y < 0 ) { + /* If the slopes don't intersect then use a line */ + /* (or if the intersection is patently absurd) */ + from->nonextcp = to->noprevcp = true; + from->nextcp = from->me; + to->prevcp = to->me; + TestForLinear(from,to); + } else { + from->nextcp = to->prevcp = nextcp; + from->nonextcp = to->noprevcp = false; + } +return( SplineMake2(from,to)); + } + /* From here down we are only working with cubic splines */ + + if ( cnt==0 ) { + /* Just use what we've got, no data to improve it */ + /* But we do sometimes get some cps which are too big */ + double len = sqrt((to->me.x-from->me.x)*(to->me.x-from->me.x) + (to->me.y-from->me.y)*(to->me.y-from->me.y)); + if ( len==0 ) { + from->nonextcp = to->noprevcp = true; + from->nextcp = from->me; + to->prevcp = to->me; + } else { + BasePoint noff, poff; + double nlen, plen; + noff.x = from->nextcp.x-from->me.x; noff.y = from->nextcp.y-from->me.y; + poff.x = to->me.x-to->prevcp.x; poff.y = to->me.y-to->prevcp.y; + nlen = sqrt(noff.x*noff.x + noff.y+noff.y); + plen = sqrt(poff.x*poff.x + poff.y+poff.y); + if ( nlen>len/3 ) { + noff.x *= len/3/nlen; noff.y *= len/3/nlen; + from->nextcp.x = from->me.x + noff.x; + from->nextcp.y = from->me.y + noff.y; + } + if ( plen>len/3 ) { + poff.x *= len/3/plen; poff.y *= len/3/plen; + to->prevcp.x = to->me.x + poff.x; + to->prevcp.y = to->me.y + poff.y; + } + } +return( SplineMake3(from,to)); + } + + if ( to->prev!=NULL && (( to->noprevcp && to->nonextcp ) || to->prev->knownlinear )) { + tounit.x = to->prev->from->me.x-to->me.x; tounit.y = to->prev->from->me.y-to->me.y; + } else if ( !to->noprevcp || to->pointtype == pt_corner ) { + tounit.x = to->prevcp.x-to->me.x; tounit.y = to->prevcp.y-to->me.y; + } else { + tounit.x = to->me.x-to->nextcp.x; tounit.y = to->me.y-to->nextcp.y; + } + tlen = sqrt(tounit.x*tounit.x + tounit.y*tounit.y); + if ( from->next!=NULL && (( from->noprevcp && from->nonextcp ) || from->next->knownlinear) ) { + fromunit.x = from->next->to->me.x-from->me.x; fromunit.y = from->next->to->me.y-from->me.y; + } else if ( !from->nonextcp || from->pointtype == pt_corner ) { + fromunit.x = from->nextcp.x-from->me.x; fromunit.y = from->nextcp.y-from->me.y; + } else { + fromunit.x = from->me.x-from->prevcp.x; fromunit.y = from->me.y-from->prevcp.y; + } + flen = sqrt(fromunit.x*fromunit.x + fromunit.y*fromunit.y); + if ( tlen==0 || flen==0 ) { + if ( from->next!=NULL ) + temp = *from->next; + else { + memset(&temp,0,sizeof(temp)); + temp.from = from; temp.to = to; + SplineRefigure(&temp); + from->next = to->prev = NULL; + } + } + if ( tlen==0 ) { + if ( (to->pointtype==pt_curve || to->pointtype==pt_hvcurve) && + to->next && !to->nonextcp ) { + tounit.x = to->me.x-to->nextcp.x; tounit.y = to->me.y-to->nextcp.y; +/* Doesn't work + } else if ( to->pointtype==pt_tangent && to->next ) { + tounit.x = to->me.x-to->next->to->me.x; tounit.y = to->me.y-to->next->to->me.y; +*/ + } else { + tounit.x = -( (3*temp.splines[0].a*.9999+2*temp.splines[0].b)*.9999+temp.splines[0].c ); + tounit.y = -( (3*temp.splines[1].a*.9999+2*temp.splines[1].b)*.9999+temp.splines[1].c ); + } + tlen = sqrt(tounit.x*tounit.x + tounit.y*tounit.y); + } + tounit.x /= tlen; tounit.y /= tlen; + + if ( flen==0 ) { + if ( (from->pointtype==pt_curve || from->pointtype==pt_hvcurve) && + from->prev && !from->noprevcp ) { + fromunit.x = from->me.x-from->prevcp.x; fromunit.y = from->me.y-from->prevcp.y; +/* + } else if ( from->pointtype==pt_tangent && from->prev ) { + fromunit.x = from->me.x-from->prev->from->me.x; fromunit.y = from->me.y-from->prev->from->me.y; +*/ + } else { + fromunit.x = ( (3*temp.splines[0].a*.0001+2*temp.splines[0].b)*.0001+temp.splines[0].c ); + fromunit.y = ( (3*temp.splines[1].a*.0001+2*temp.splines[1].b)*.0001+temp.splines[1].c ); + } + flen = sqrt(fromunit.x*fromunit.x + fromunit.y*fromunit.y); + } + fromunit.x /= flen; fromunit.y /= flen; + + trylen = (to->me.x-from->me.x)*fromunit.x + (to->me.y-from->me.y)*fromunit.y; + if ( trylen>flen ) flen = trylen; + + trylen = (from->me.x-to->me.x)*tounit.x + (from->me.y-to->me.y)*tounit.y; + if ( trylen>tlen ) tlen = trylen; + + ftunit.x = (to->me.x-from->me.x); ftunit.y = (to->me.y-from->me.y); + ftlen = sqrt(ftunit.x*ftunit.x + ftunit.y*ftunit.y); + if ( ftlen!=0 ) { + ftunit.x /= ftlen; ftunit.y /= ftlen; + } + fdotft = fromunit.x*ftunit.x + fromunit.y*ftunit.y; + fmax = fdotft>0 ? ftlen/fdotft : 1e10; + tdotft = -tounit.x*ftunit.x - tounit.y*ftunit.y; + tmax = tdotft>0 ? ftlen/tdotft : 1e10; + /* At fmax, tmax the control points will stretch beyond the other endpoint*/ + /* when projected along the line between the two endpoints */ + + db.base = from->me; + db.unit.x = (to->me.x-from->me.x); db.unit.y = (to->me.y-from->me.y); + db.len = sqrt(db.unit.x*db.unit.x + db.unit.y*db.unit.y); + if ( db.len!=0 ) { + db.unit.x /= db.len; + db.unit.y /= db.len; + } + ApproxBounds(&b,mid,cnt,&db); + + for ( k=0; k<TRY_CNT; ++k ) { + bestdiff[k] = 1e20; + besti[k] = -1; bestj[k] = -1; + } + fdiff = flen/DECIMATION; + tdiff = tlen/DECIMATION; + from->nextcp = from->me; + from->nonextcp = false; + to->noprevcp = false; + memset(&temp,0,sizeof(Spline)); + temp.from = from; temp.to = to; + for ( i=1; i<DECIMATION; ++i ) { + from->nextcp.x += fdiff*fromunit.x; from->nextcp.y += fdiff*fromunit.y; + to->prevcp = to->me; + for ( j=1; j<DECIMATION; ++j ) { + to->prevcp.x += tdiff*tounit.x; to->prevcp.y += tdiff*tounit.y; + SplineRefigure(&temp); + curdiff = SigmaDeltas(&temp,mid,cnt,&b,&db); + for ( k=0; k<TRY_CNT; ++k ) { + if ( curdiff<bestdiff[k] ) { + for ( l=TRY_CNT-1; l>k; --l ) { + bestdiff[l] = bestdiff[l-1]; + besti[l] = besti[l-1]; + bestj[l] = bestj[l-1]; + } + bestdiff[k] = curdiff; + besti[k] = i; bestj[k]=j; + break; + } + } + } + } + + finaldiff = 1e20; + offn_ = offp_ = -1; + spline = SplineMake(from,to,false); + for ( k=-1; k<TRY_CNT; ++k ) { + if ( k<0 ) { + BasePoint nextcp, prevcp; + double temp1, temp2; + int ret = _ApproximateSplineFromPoints(from,to,mid,cnt,&nextcp,&prevcp,false); + /* sometimes least squares gives us the right answer */ + if ( !(ret&1) || !(ret&2)) + continue; + temp1 = (prevcp.x-to->me.x)*tounit.x + (prevcp.y-to->me.y)*tounit.y; + temp2 = (nextcp.x-from->me.x)*fromunit.x + (nextcp.y-from->me.y)*fromunit.y; + if ( temp1<=0 || temp2<=0 ) /* A nice solution... but the control points are diametrically opposed to what they should be */ + continue; + tlen = temp1; flen = temp2; + } else { + if ( bestj[k]<0 || besti[k]<0 ) + continue; + tlen = bestj[k]*tdiff; flen = besti[k]*fdiff; + } + to->prevcp.x = to->me.x + tlen*tounit.x; to->prevcp.y = to->me.y + tlen*tounit.y; + from->nextcp.x = from->me.x + flen*fromunit.x; from->nextcp.y = from->me.y + flen*fromunit.y; + SplineRefigure(spline); + + bettern = betterp = false; + incrn = tdiff/2.0; incrp = fdiff/2.0; + offn = flen; offp = tlen; + nocnt = 0; + curdiff = SigmaDeltas(spline,mid,cnt,&b,&db); + totcnt = 0; + forever { + double fadiff, fsdiff; + double tadiff, tsdiff; + + from->nextcp.x = from->me.x + (offn+incrn)*fromunit.x; from->nextcp.y = from->me.y + (offn+incrn)*fromunit.y; + to->prevcp.x = to->me.x + offp*tounit.x; to->prevcp.y = to->me.y + offp*tounit.y; + SplineRefigure(spline); + fadiff = SigmaDeltas(spline,mid,cnt,&b,&db); + from->nextcp.x = from->me.x + (offn-incrn)*fromunit.x; from->nextcp.y = from->me.y + (offn-incrn)*fromunit.y; + SplineRefigure(spline); + fsdiff = SigmaDeltas(spline,mid,cnt,&b,&db); + from->nextcp.x = from->me.x + offn*fromunit.x; from->nextcp.y = from->me.y + offn*fromunit.y; + if ( offn-incrn<=0 ) + fsdiff += 1e10; + + to->prevcp.x = to->me.x + (offp+incrp)*tounit.x; to->prevcp.y = to->me.y + (offp+incrp)*tounit.y; + SplineRefigure(spline); + tadiff = SigmaDeltas(spline,mid,cnt,&b,&db); + to->prevcp.x = to->me.x + (offp-incrp)*tounit.x; to->prevcp.y = to->me.y + (offp-incrp)*tounit.y; + SplineRefigure(spline); + tsdiff = SigmaDeltas(spline,mid,cnt,&b,&db); + to->prevcp.x = to->me.x + offp*tounit.x; to->prevcp.y = to->me.y + offp*tounit.y; + if ( offp-incrp<=0 ) + tsdiff += 1e10; + + if ( offn>=incrn && fsdiff<curdiff && + (fsdiff<fadiff && fsdiff<tsdiff && fsdiff<tadiff)) { + offn -= incrn; + if ( bettern>0 ) + incrn /= 2; + bettern = -1; + nocnt = 0; + curdiff = fsdiff; + } else if ( offn+incrn<fmax && fadiff<curdiff && + (fadiff<=fsdiff && fadiff<tsdiff && fadiff<tadiff)) { + offn += incrn; + if ( bettern<0 ) + incrn /= 2; + bettern = 1; + nocnt = 0; + curdiff = fadiff; + } else if ( offp>=incrp && tsdiff<curdiff && + (tsdiff<=fsdiff && tsdiff<=fadiff && tsdiff<tadiff)) { + offp -= incrp; + if ( betterp>0 ) + incrp /= 2; + betterp = -1; + nocnt = 0; + curdiff = tsdiff; + } else if ( offp+incrp<tmax && tadiff<curdiff && + (tadiff<=fsdiff && tadiff<=fadiff && tadiff<=tsdiff)) { + offp += incrp; + if ( betterp<0 ) + incrp /= 2; + betterp = 1; + nocnt = 0; + curdiff = tadiff; + } else { + if ( ++nocnt > 6 ) + break; + incrn /= 2; + incrp /= 2; + } + if ( curdiff<1 ) + break; + if ( incrp<tdiff/1024 || incrn<fdiff/1024 ) + break; + if ( ++totcnt>200 ) + break; + if ( offn<0 || offp<0 ) { + IError("Approximation got inverse control points"); + break; + } + } +#if 0 + if ( nocnt>6 ) + nocnt_cnt++; + else if ( curdiff<1 ) + curdiff_cnt++; + else if ( totcnt>200 ) + totcnt_cnt++; + else + incr_cnt++; +#endif + if ( curdiff<finaldiff ) { + finaldiff = curdiff; + offn_ = offn; + offp_ = offp; + } + } + + to->noprevcp = offp_==0; + from->nonextcp = offn_==0; + to->prevcp.x = to->me.x + offp_*tounit.x; to->prevcp.y = to->me.y + offp_*tounit.y; + from->nextcp.x = from->me.x + offn_*fromunit.x; from->nextcp.y = from->me.y + offn_*fromunit.y; + /* I used to check for a spline very close to linear (and if so, make it */ + /* linear). But in when stroking a path with an eliptical pen we transform*/ + /* the coordinate system and our normal definitions of "close to linear" */ + /* don't apply */ + /*TestForLinear(from,to);*/ + SplineRefigure(spline); + +return( spline ); +} +#undef TRY_CNT +#undef DECIMATION + + /* calculating the actual length of a spline is hard, this gives a very */ + /* rough (but quick) approximation */ +static double SplineLenApprox(Spline *spline) { + double len, slen, temp; + + if ( (temp = spline->to->me.x-spline->from->me.x)<0 ) temp = -temp; + len = temp; + if ( (temp = spline->to->me.y-spline->from->me.y)<0 ) temp = -temp; + len += temp; + if ( !spline->to->noprevcp || !spline->from->nonextcp ) { + if ( (temp = spline->from->nextcp.x-spline->from->me.x)<0 ) temp = -temp; + slen = temp; + if ( (temp = spline->from->nextcp.y-spline->from->me.y)<0 ) temp = -temp; + slen += temp; + if ( (temp = spline->to->prevcp.x-spline->from->nextcp.x)<0 ) temp = -temp; + slen += temp; + if ( (temp = spline->to->prevcp.y-spline->from->nextcp.y)<0 ) temp = -temp; + slen += temp; + if ( (temp = spline->to->me.x-spline->to->prevcp.x)<0 ) temp = -temp; + slen += temp; + if ( (temp = spline->to->me.y-spline->to->prevcp.y)<0 ) temp = -temp; + slen += temp; + len = (len + slen)/2; + } +return( len ); +} + +double SplineLength(Spline *spline) { + /* I ignore the constant term. It's just an unneeded addition */ + double len, t; + double lastx = 0, lasty = 0; + double curx, cury; + + len = 0; + for ( t=1.0/128; t<=1.0001 ; t+=1.0/128 ) { + curx = ((spline->splines[0].a*t+spline->splines[0].b)*t+spline->splines[0].c)*t; + cury = ((spline->splines[1].a*t+spline->splines[1].b)*t+spline->splines[1].c)*t; + len += sqrt( (curx-lastx)*(curx-lastx) + (cury-lasty)*(cury-lasty) ); + lastx = curx; lasty = cury; + } +return( len ); +} + + +static TPoint *SplinesFigureTPsBetween(SplinePoint *from, SplinePoint *to, + int *tot) { + int cnt, i, j, pcnt; + double len, slen, lbase; + SplinePoint *np; + TPoint *tp; + double _lens[10], *lens = _lens; + int _cnts[10], *cnts = _cnts; + /* I used just to give every spline 10 points. But that gave much more */ + /* weight to small splines than to big ones */ + + cnt = 0; + for ( np = from->next->to; ; np = np->next->to ) { + ++cnt; + if ( np==to ) + break; + } + if ( cnt>10 ) { + lens = galloc(cnt*sizeof(double)); + cnts = galloc(cnt*sizeof(int)); + } + cnt = 0; len = 0; + for ( np = from->next->to; ; np = np->next->to ) { + lens[cnt] = SplineLenApprox(np->prev); + len += lens[cnt]; + ++cnt; + if ( np==to ) + break; + } + if ( len!=0 ) { + pcnt = 0; + for ( i=0; i<cnt; ++i ) { + int pnts = rint( (10*cnt*lens[i])/len ); + if ( pnts<2 ) pnts = 2; + cnts[i] = pnts; + pcnt += pnts; + } + } else + pcnt = 2*cnt; + + tp = galloc((pcnt+1)*sizeof(TPoint)); i = 0; + if ( len==0 ) { + for ( i=0; i<=pcnt; ++i ) { + tp[i].t = i/(pcnt); + tp[i].x = from->me.x; + tp[i].y = from->me.y; + } + } else { + lbase = 0; + for ( i=cnt=0, np = from->next->to; ; np = np->next->to, ++cnt ) { + slen = SplineLenApprox(np->prev); + for ( j=0; j<cnts[cnt]; ++j ) { + double t = j/(double) cnts[cnt]; + tp[i].t = (lbase+ t*slen)/len; + tp[i].x = ((np->prev->splines[0].a*t+np->prev->splines[0].b)*t+np->prev->splines[0].c)*t + np->prev->splines[0].d; + tp[i++].y = ((np->prev->splines[1].a*t+np->prev->splines[1].b)*t+np->prev->splines[1].c)*t + np->prev->splines[1].d; + } + lbase += slen; + if ( np==to ) + break; + } + } + if ( cnts!=_cnts ) free(cnts); + if ( lens!=_lens ) free(lens); + + *tot = i; + +return( tp ); +} + +static void SplinePointReCatagorize(SplinePoint *sp,int oldpt) { + SplinePointCatagorize(sp); + if ( sp->pointtype!=oldpt ) { + if ( sp->pointtype==pt_curve && oldpt==pt_hvcurve && + ((sp->nextcp.x == sp->me.x && sp->nextcp.y != sp->me.y ) || + (sp->nextcp.y == sp->me.y && sp->nextcp.x != sp->me.x ))) + sp->pointtype = pt_hvcurve; + } +} + +void SplinesRemoveBetween(SplineChar *sc, SplinePoint *from, SplinePoint *to,int type) { + int tot; + TPoint *tp; + SplinePoint *np, oldfrom; + int oldfpt = from->pointtype, oldtpt = to->pointtype; + Spline *sp; + int order2 = from->next->order2; + + oldfrom = *from; + tp = SplinesFigureTPsBetween(from,to,&tot); + + if ( type==1 ) + ApproximateSplineFromPointsSlopes(from,to,tp,tot-1,order2); + else + ApproximateSplineFromPoints(from,to,tp,tot-1,order2); + + /* Have to do the frees after the approximation because the approx */ + /* uses the splines to determine slopes */ + for ( sp = oldfrom.next; ; ) { + np = sp->to; + SplineFree(sp); + if ( np==to ) + break; + sp = np->next; + SplinePointMDFree(sc,np); + } + + free(tp); + + SplinePointReCatagorize(from,oldfpt); + SplinePointReCatagorize(to,oldtpt); +} + + +static void RemoveStupidControlPoints(SplineSet *spl) { + double len, normal, dir; + Spline *s, *first; + BasePoint unit, off; + + /* Also remove really stupid control points: Tiny offsets pointing in */ + /* totally the wrong direction. Some of the TeX fonts we get have these */ + /* We get equally bad results with a control point that points beyond the */ + /* other end point */ + first = NULL; + for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) { + unit.x = s->to->me.x-s->from->me.x; + unit.y = s->to->me.y-s->from->me.y; + len = sqrt(unit.x*unit.x+unit.y*unit.y); + if ( len!=0 ) { + int refigure = false; + unit.x /= len; unit.y /= len; + if ( !s->from->nonextcp ) { + off.x = s->from->nextcp.x-s->from->me.x; + off.y = s->from->nextcp.y-s->from->me.y; + if ((normal = off.x*unit.y - off.y*unit.x)<0 ) normal = -normal; + dir = off.x*unit.x + off.y*unit.y; + if (( normal<dir && normal<1 && dir<0 ) || (normal<.5 && dir<-.5) || + (normal<.1 && dir>len)) { + s->from->nextcp = s->from->me; + s->from->nonextcp = true; + refigure = true; + } + } + if ( !s->to->noprevcp ) { + off.x = s->to->me.x - s->to->prevcp.x; + off.y = s->to->me.y - s->to->prevcp.y; + if ((normal = off.x*unit.y - off.y*unit.x)<0 ) normal = -normal; + dir = off.x*unit.x + off.y*unit.y; + if (( normal<-dir && normal<1 && dir<0 ) || (normal<.5 && dir>-.5 && dir<0) || + (normal<.1 && dir>len)) { + s->to->prevcp = s->to->me; + s->to->noprevcp = true; + refigure = true; + } + } + if ( refigure ) + SplineRefigure(s); + } + if ( first==NULL ) first = s; + } +} + +void SSRemoveStupidControlPoints(SplineSet *base) { + SplineSet *spl; + + for (spl=base; spl!=NULL; spl=spl->next ) + RemoveStupidControlPoints(spl); +} + +static void OverlapClusterCpAngles(SplineSet *spl,double within) { + double len, nlen, plen; + double startoff, endoff; + SplinePoint *sp, *nsp, *psp; + BasePoint *nbp, *pbp; + BasePoint pdir, ndir, fpdir, fndir; + int nbad, pbad; + + /* If we have a junction point (right mid of 3) where the two splines */ + /* are almost, but not quite moving in the same direction as they go */ + /* away from the point, and if there is a tiny overlap because of this */ + /* "almost" same, then we will probably get a bit confused in remove */ + /* overlap */ + + for ( sp = spl->first; ; ) { + if ( sp->next==NULL ) + break; + nsp = sp->next->to; + if (( !sp->nonextcp || !sp->noprevcp ) && sp->prev!=NULL ) { + psp = sp->prev->from; + nbp = !sp->nonextcp ? &sp->nextcp : !nsp->noprevcp ? &nsp->prevcp : &nsp->me; + pbp = !sp->noprevcp ? &sp->prevcp : !psp->nonextcp ? &psp->nextcp : &psp->me; + + pdir.x = pbp->x-sp->me.x; pdir.y = pbp->y-sp->me.y; + ndir.x = nbp->x-sp->me.x; ndir.y = nbp->y-sp->me.y; + fpdir.x = psp->me.x-sp->me.x; fpdir.y = psp->me.y-sp->me.y; + fndir.x = nsp->me.x-sp->me.x; fndir.y = nsp->me.y-sp->me.y; + + plen = sqrt(pdir.x*pdir.x+pdir.y*pdir.y); + if ( plen!=0 ) { + pdir.x /= plen; pdir.y /= plen; + } + + nlen = sqrt(ndir.x*ndir.x+ndir.y*ndir.y); + if ( nlen!=0 ) { + ndir.x /= nlen; ndir.y /= nlen; + } + + nbad = pbad = false; + if ( !sp->nonextcp && plen!=0 && nlen!=0 ) { + len = sqrt(fndir.x*fndir.x+fndir.y*fndir.y); + if ( len!=0 ) { + fndir.x /= len; fndir.y /= len; + startoff = ndir.x*pdir.y - ndir.y*pdir.x; + endoff = fndir.x*pdir.y - fndir.y*pdir.x; + if (( (startoff<0 && endoff>0) || (startoff>0 && endoff<0)) && + startoff > -within && startoff < within ) + nbad = true; + } + } + if ( !sp->noprevcp && plen!=0 && nlen!=0 ) { + len = sqrt(fpdir.x*fpdir.x+fpdir.y*fpdir.y); + if ( len!=0 ) { + fpdir.x /= len; fpdir.y /= len; + startoff = pdir.x*ndir.y - pdir.y*ndir.x; + endoff = fpdir.x*ndir.y - fpdir.y*ndir.x; + if (( (startoff<0 && endoff>0) || (startoff>0 && endoff<0)) && + startoff > -within && startoff < within ) + pbad = true; + } + } + if ( nbad && pbad ) { + if ( ndir.x==0 || ndir.y==0 ) + nbad = false; + else if ( pdir.x==0 || pdir.y==0 ) + pbad = false; + } + if ( nbad && pbad ) { + if ( ndir.x*pdir.x + ndir.y*pdir.y > 0 ) { + ndir.x = pdir.x = (ndir.x + pdir.x)/2; + ndir.y = pdir.y = (ndir.x + pdir.x)/2; + } else { + ndir.x = (ndir.x - pdir.x)/2; + ndir.y = (ndir.y - pdir.y)/2; + pdir.x = -ndir.x; pdir.y = -ndir.y; + } + sp->nextcp.x = sp->me.x + nlen*ndir.x; + sp->nextcp.y = sp->me.y + nlen*ndir.y; + sp->prevcp.x = sp->me.x + plen*pdir.x; + sp->prevcp.y = sp->me.y + plen*pdir.y; + SplineRefigure(sp->next); SplineRefigure(sp->prev); + } else if ( nbad ) { + if ( ndir.x*pdir.x + ndir.y*pdir.y < 0 ) { + pdir.x = -pdir.x; + pdir.y = -pdir.y; + } + sp->nextcp.x = sp->me.x + nlen*pdir.x; + sp->nextcp.y = sp->me.y + nlen*pdir.y; + SplineRefigure(sp->next); + } else if ( pbad ) { + if ( ndir.x*pdir.x + ndir.y*pdir.y < 0 ) { + ndir.x = -ndir.x; + ndir.y = -ndir.y; + } + sp->prevcp.x = sp->me.x + plen*ndir.x; + sp->prevcp.y = sp->me.y + plen*ndir.y; + SplineRefigure(sp->prev); + } + } + if ( nsp==spl->first ) + break; + sp = nsp; + } +} + +void SSOverlapClusterCpAngles(SplineSet *base,double within) { + SplineSet *spl; + + for (spl=base; spl!=NULL; spl=spl->next ) + OverlapClusterCpAngles(spl,within); +} + + +Spline *SplineAddExtrema(Spline *s,int always,real lenbound, real offsetbound, + DBounds *b) { + /* First find the extrema, if any */ + bigreal t[4], min; + uint8 rmfrom[4], rmto[4]; + int p, i,j, p_s, mini; + SplinePoint *sp; + real len; + + if ( !always ) { + real xlen, ylen; + xlen = (s->from->me.x-s->to->me.x); + ylen = (s->from->me.y-s->to->me.y); + len = xlen*xlen + ylen*ylen; + lenbound *= lenbound; + if ( len < lenbound ) { + len = SplineLength(s); + len *= len; + } + } + + memset(rmfrom,0,sizeof(rmfrom)); + memset(rmto,0,sizeof(rmto)); + + forever { + if ( s->knownlinear ) +return(s); + p = 0; + if ( s->splines[0].a!=0 ) { + double d = 4*s->splines[0].b*s->splines[0].b-4*3*s->splines[0].a*s->splines[0].c; + if ( d>0 ) { + d = sqrt(d); + t[p++] = CheckExtremaForSingleBitErrors(&s->splines[0],(-2*s->splines[0].b+d)/(2*3*s->splines[0].a)); + t[p++] = CheckExtremaForSingleBitErrors(&s->splines[0],(-2*s->splines[0].b-d)/(2*3*s->splines[0].a)); + } + } else if ( s->splines[0].b!=0 ) + t[p++] = -s->splines[0].c/(2*s->splines[0].b); + if ( !always ) { + /* Generally we are only interested in extrema on long splines, or */ + /* extrema which are extrema for the entire contour, not just this */ + /* spline */ + /* Also extrema which are very close to one of the end-points can */ + /* be ignored. */ + /* No they can't. But we need to remove the original point in this*/ + /* case */ + for ( i=0; i<p; ++i ) { + real x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d; + real y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d; + int close_from = ( x-s->from->me.x<offsetbound && x-s->from->me.x>-offsetbound) && + ( y-s->from->me.y<10*offsetbound && y-s->from->me.y>-10*offsetbound ); + int close_to = ( x-s->to->me.x<offsetbound && x-s->to->me.x>-offsetbound) && + ( y-s->to->me.y<10*offsetbound && y-s->to->me.y>-10*offsetbound ); + int remove_from = close_from && GoodCurve(s->from,true); + int remove_to = close_to && GoodCurve(s->to,false); + if (( x>b->minx && x<b->maxx && len<lenbound ) || + (close_from && !remove_from) || (close_to && !remove_to) ) { + --p; + for ( j=i; j<p; ++j ) + t[j] = t[j+1]; + --i; + } else { + rmfrom[i] = remove_from; + rmto[i] = remove_to; + } + } + } + + p_s = p; + if ( s->splines[1].a!=0 ) { + double d = 4*s->splines[1].b*s->splines[1].b-4*3*s->splines[1].a*s->splines[1].c; + if ( d>0 ) { + d = sqrt(d); + t[p++] = CheckExtremaForSingleBitErrors(&s->splines[1],(-2*s->splines[1].b+d)/(2*3*s->splines[1].a)); + t[p++] = CheckExtremaForSingleBitErrors(&s->splines[1],(-2*s->splines[1].b-d)/(2*3*s->splines[1].a)); + } + } else if ( s->splines[1].b!=0 ) + t[p++] = -s->splines[1].c/(2*s->splines[1].b); + if ( !always ) { + for ( i=p_s; i<p; ++i ) { + real x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d; + real y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d; + int close_from =( y-s->from->me.y<offsetbound && y-s->from->me.y>-offsetbound ) && + ( x-s->from->me.x<offsetbound && x-s->from->me.x>-offsetbound); + int close_to = ( y-s->to->me.y<offsetbound && y-s->to->me.y>-offsetbound ) && + ( x-s->to->me.x<offsetbound && x-s->to->me.x>-offsetbound); + int remove_from = close_from && GoodCurve(s->from,true); + int remove_to = close_to && GoodCurve(s->to,false); + if (( y>b->miny && y<b->maxy && len<lenbound ) || + (close_from && !remove_from) || (close_to && !remove_to) ) { + --p; + for ( j=i; j<p; ++j ) + t[j] = t[j+1]; + --i; + } else { + rmfrom[i] = remove_from; + rmto[i] = remove_to; + } + } + } + + /* Throw out any t values which are not between 0 and 1 */ + /* (we do a little fudging near the endpoints so we don't get confused */ + /* by rounding errors) */ + for ( i=0; i<p; ++i ) { + if ( t[i]>0 && t[i]<.05 ) { + BasePoint test; + /* Expand strong gets very confused on zero-length splines so */ + /* don't let that happen */ + test.x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d; + test.y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d; + if ( test.x== s->from->me.x && test.y==s->from->me.y ) + t[i] = 0; /* Throw it out */ + } + if ( t[i]<1 && t[i]>.95 ) { + BasePoint test; + test.x = ((s->splines[0].a*t[i]+s->splines[0].b)*t[i]+s->splines[0].c)*t[i]+s->splines[0].d; + test.y = ((s->splines[1].a*t[i]+s->splines[1].b)*t[i]+s->splines[1].c)*t[i]+s->splines[1].d; + if ( test.x== s->to->me.x && test.y==s->to->me.y ) + t[i] = 1.0; /* Throw it out */ + } + + if ( t[i]<.0001 || t[i]>.9999 ) { + --p; + for ( j=i; j<p; ++j ) { + t[j] = t[j+1]; + rmfrom[j] = rmfrom[j+1]; + rmto[j] = rmto[j+1]; + } + --i; + } + } + + if ( p==0 ) +return(s); + + /* Find the smallest of all the interesting points */ + min = t[0]; mini = 0; + for ( i=1; i<p; ++i ) { + if ( t[i]<min ) { + min=t[i]; + mini = i; + } + } + sp = SplineBisect(s,min); +/* On the mac we get rounding errors in the bisect routine */ + { double dx, dy; + if ( (dx = sp->me.x - sp->prevcp.x)<0 ) dx=-dx; + if ( (dy = sp->me.y - sp->prevcp.y)<0 ) dy=-dy; + if ( dx!=0 && dy!=0 ) { + if ( dx<dy ) + sp->prevcp.x = sp->me.x; + else + sp->prevcp.y = sp->me.y; + } + if ( (dx = sp->me.x - sp->nextcp.x)<0 ) dx=-dx; + if ( (dy = sp->me.y - sp->nextcp.y)<0 ) dy=-dy; + if ( dx!=0 && dy!=0 ) { + if ( dx<dy ) + sp->nextcp.x = sp->me.x; + else + sp->nextcp.y = sp->me.y; + } + } + + if ( rmfrom[mini] ) sp->prev->from->ticked = true; + if ( rmto[mini] ) sp->next->to->ticked = true; + s = sp->next; + if ( p==1 ) +return( s ); + /* Don't try to use any other computed t values, it is easier to */ + /* recompute them than to try and figure out what they map to on the */ + /* new spline */ + } +} + +void SplineSetAddExtrema(SplineChar *sc, SplineSet *ss,enum ae_type between_selected, int emsize) { + Spline *s, *first; + DBounds b; + int always = true; + real lenbound = 0; + real offsetbound=0; + SplinePoint *sp, *nextp; + + if ( between_selected==ae_only_good ) { + SplineSetQuickBounds(ss,&b); + lenbound = (emsize)/32.0; + always = false; + offsetbound = .5; + between_selected = ae_only_good_rm_later; + for ( sp = ss->first; ; ) { + sp->ticked = false; + if ( sp->next==NULL ) + break; + sp = sp->next->to; + if ( sp==ss->first ) + break; + } + } + + first = NULL; + for ( s = ss->first->next; s!=NULL && s!=first; s = s->to->next ) { + if ( between_selected!=ae_between_selected || + (s->from->selected && s->to->selected)) + s = SplineAddExtrema(s,always,lenbound,offsetbound,&b); + if ( first==NULL ) first = s; + } + if ( between_selected == ae_only_good_rm_later ) { + for ( sp = ss->first; ; ) { + if ( sp->next==NULL ) + break; + nextp = sp->next->to; + if ( sp->ticked ) { + if ( sp==ss->first ) + ss->first = ss->last = nextp; + SplinesRemoveBetween(sc,sp->prev->from,nextp,1); + } + sp = nextp; + if ( sp==ss->first ) + break; + } + } +} + + +char *GetNextUntitledName(void) { + static int untitled_cnt=1; + char buffer[80]; + + sprintf( buffer, "Untitled%d", untitled_cnt++ ); +return( copy(buffer)); +} + +SplineFont *SplineFontEmpty(void) { + extern int default_fv_row_count, default_fv_col_count; + time_t now; + SplineFont *sf; + + sf = gcalloc(1,sizeof(SplineFont)); + sf->pfminfo.fstype = -1; + sf->top_enc = -1; + sf->macstyle = -1; + sf->desired_row_cnt = default_fv_row_count; sf->desired_col_cnt = default_fv_col_count; + sf->display_antialias = default_fv_antialias; + sf->display_bbsized = default_fv_bbsized; + sf->display_size = -default_fv_font_size; + sf->display_layer = ly_fore; + sf->pfminfo.winascent_add = sf->pfminfo.windescent_add = true; + sf->pfminfo.hheadascent_add = sf->pfminfo.hheaddescent_add = true; + sf->pfminfo.typoascent_add = sf->pfminfo.typodescent_add = true; + if ( TTFFoundry!=NULL ) + strncpy(sf->pfminfo.os2_vendor,TTFFoundry,4); + else + memcpy(sf->pfminfo.os2_vendor,"PfEd",4); + sf->for_new_glyphs = DefaultNameListForNewFonts(); + time(&now); + sf->creationtime = sf->modificationtime = now; + + sf->layer_cnt = 2; + sf->layers = gcalloc(2,sizeof(LayerInfo)); + sf->layers[0].name = copy(_("Back")); + sf->layers[0].background = true; + sf->layers[1].name = copy(_("Fore")); + sf->layers[1].background = false; + sf->grid.background = true; + +return( sf ); +} + + +static void SFChangeXUID(SplineFont *sf, int random) { + char *pt, *new, *npt; + int val; + + if ( sf->xuid==NULL ) +return; + pt = strrchr(sf->xuid,' '); + if ( pt==NULL ) + pt = strchr(sf->xuid,'['); + if ( pt==NULL ) + pt = sf->xuid; + else + ++pt; + if ( random ) + val = rand()&0xffffff; + else { + val = strtol(pt,NULL,10); + val = (val+1)&0xffffff; + } + + new = galloc(pt-sf->xuid+12); + strncpy(new,sf->xuid,pt-sf->xuid); + npt = new + (pt-sf->xuid); + if ( npt==new ) *npt++ = '['; + sprintf(npt, "%d]", val ); + free(sf->xuid); sf->xuid = new; + sf->changed = true; + sf->changed_since_xuidchanged = false; +} + +void SFIncrementXUID(SplineFont *sf) { + SFChangeXUID(sf,false); +} + +void SFRandomChangeXUID(SplineFont *sf) { + SFChangeXUID(sf,true); +} + +void SPWeightedAverageCps(SplinePoint *sp) { + double pangle, nangle, angle, plen, nlen, c, s; + if ( sp->noprevcp || sp->nonextcp ) + /*SPAverageCps(sp)*/; /* Expand Stroke wants this case to hold still */ + else if (( sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve) && + sp->prev && sp->next ) { + pangle = atan2(sp->me.y-sp->prevcp.y,sp->me.x-sp->prevcp.x); + nangle = atan2(sp->nextcp.y-sp->me.y,sp->nextcp.x-sp->me.x); + if ( pangle<0 && nangle>0 && nangle-pangle>=3.1415926 ) + pangle += 2*3.1415926535897932; + else if ( pangle>0 && nangle<0 && pangle-nangle>=3.1415926 ) + nangle += 2*3.1415926535897932; + plen = sqrt((sp->me.y-sp->prevcp.y)*(sp->me.y-sp->prevcp.y) + + (sp->me.x-sp->prevcp.x)*(sp->me.x-sp->prevcp.x)); + nlen = 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)); + if ( plen+nlen==0 ) + angle = (nangle+pangle)/2; + else + angle = (plen*pangle + nlen*nangle)/(plen+nlen); + plen = -plen; + c = cos(angle); s=sin(angle); + sp->nextcp.x = c*nlen + sp->me.x; + sp->nextcp.y = s*nlen + sp->me.y; + sp->prevcp.x = c*plen + sp->me.x; + sp->prevcp.y = s*plen + sp->me.y; + SplineRefigure(sp->prev); + SplineRefigure(sp->next); + } else + SPAverageCps(sp); +} + +void SPAverageCps(SplinePoint *sp) { + double pangle, nangle, angle, plen, nlen, c, s; + if (( sp->pointtype==pt_curve || sp->pointtype==pt_hvcurve) && + sp->prev && sp->next ) { + if ( sp->noprevcp ) + pangle = atan2(sp->me.y-sp->prev->from->me.y,sp->me.x-sp->prev->from->me.x); + else + pangle = atan2(sp->me.y-sp->prevcp.y,sp->me.x-sp->prevcp.x); + if ( sp->nonextcp ) + nangle = atan2(sp->next->to->me.y-sp->me.y,sp->next->to->me.x-sp->me.x); + else + nangle = atan2(sp->nextcp.y-sp->me.y,sp->nextcp.x-sp->me.x); + if ( pangle<0 && nangle>0 && nangle-pangle>=3.1415926 ) + pangle += 2*3.1415926535897932; + else if ( pangle>0 && nangle<0 && pangle-nangle>=3.1415926 ) + nangle += 2*3.1415926535897932; + angle = (nangle+pangle)/2; + plen = -sqrt((sp->me.y-sp->prevcp.y)*(sp->me.y-sp->prevcp.y) + + (sp->me.x-sp->prevcp.x)*(sp->me.x-sp->prevcp.x)); + nlen = 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)); + c = cos(angle); s=sin(angle); + sp->nextcp.x = c*nlen + sp->me.x; + sp->nextcp.y = s*nlen + sp->me.y; + sp->prevcp.x = c*plen + sp->me.x; + sp->prevcp.y = s*plen + sp->me.y; + SplineRefigure(sp->prev); + SplineRefigure(sp->next); + } else if ( sp->pointtype==pt_tangent && sp->prev && sp->next ) { + if ( !sp->noprevcp ) { + nangle = atan2(sp->next->to->me.y-sp->me.y,sp->next->to->me.x-sp->me.x); + plen = -sqrt((sp->me.y-sp->prevcp.y)*(sp->me.y-sp->prevcp.y) + + (sp->me.x-sp->prevcp.x)*(sp->me.x-sp->prevcp.x)); + c = cos(nangle); s=sin(nangle); + sp->prevcp.x = c*plen + sp->me.x; + sp->prevcp.y = s*plen + sp->me.y; + SplineRefigure(sp->prev); + } + if ( !sp->nonextcp ) { + pangle = atan2(sp->me.y-sp->prev->from->me.y,sp->me.x-sp->prev->from->me.x); + nlen = 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)); + c = cos(pangle); s=sin(pangle); + sp->nextcp.x = c*nlen + sp->me.x; + sp->nextcp.y = s*nlen + sp->me.y; + SplineRefigure(sp->next); + } + } +} + + +void SplineCharTangentNextCP(SplinePoint *sp) { + double len; + BasePoint *bp, unit; + extern int snaptoint; + + if ( sp->prev==NULL ) +return; + bp = &sp->prev->from->me; + + unit.y = sp->me.y-bp->y; unit.x = sp->me.x-bp->x; + len = sqrt( unit.x*unit.x + unit.y*unit.y ); + if ( len!=0 ) { + unit.x /= len; + unit.y /= len; + } + 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)); + sp->nextcp.x = sp->me.x + len*unit.x; + sp->nextcp.y = sp->me.y + len*unit.y; + if ( snaptoint ) { + sp->nextcp.x = rint(sp->nextcp.x); + sp->nextcp.y = rint(sp->nextcp.y); + } else { + sp->nextcp.x = rint(sp->nextcp.x*1024)/1024; + sp->nextcp.y = rint(sp->nextcp.y*1024)/1024; + } + if ( sp->next!=NULL && sp->next->order2 ) + sp->next->to->prevcp = sp->nextcp; +} + +void SplineCharTangentPrevCP(SplinePoint *sp) { + double len; + BasePoint *bp, unit; + extern int snaptoint; + + if ( sp->next==NULL ) +return; + bp = &sp->next->to->me; + + unit.y = sp->me.y-bp->y; unit.x = sp->me.x-bp->x; + len = sqrt( unit.x*unit.x + unit.y*unit.y ); + if ( len!=0 ) { + unit.x /= len; + unit.y /= len; + } + 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)); + sp->prevcp.x = sp->me.x + len*unit.x; + sp->prevcp.y = sp->me.y + len*unit.y; + if ( snaptoint ) { + sp->prevcp.x = rint(sp->prevcp.x); + sp->prevcp.y = rint(sp->prevcp.y); + } else { + sp->prevcp.x = rint(sp->prevcp.x*1024)/1024; + sp->prevcp.y = rint(sp->prevcp.y*1024)/1024; + } + if ( sp->prev!=NULL && sp->prev->order2 ) + sp->prev->from->nextcp = sp->prevcp; +} + +static void BP_HVForce(BasePoint *vector) { + /* Force vector to be horizontal/vertical */ + double dx, dy, len; + + if ( (dx= vector->x)<0 ) dx = -dx; + if ( (dy= vector->y)<0 ) dy = -dy; + if ( dx==0 || dy==0 ) +return; + len = sqrt(dx*dx + dy*dy); + if ( dx>dy ) { + vector->x = vector->x<0 ? -len : len; + vector->y = 0; + } else { + vector->y = vector->y<0 ? -len : len; + vector->x = 0; + } +} + +#define NICE_PROPORTION .39 +void SplineCharDefaultNextCP(SplinePoint *base) { + SplinePoint *prev=NULL, *next; + double len, plen, ulen; + BasePoint unit; + extern int snaptoint; + + if ( base->next==NULL ) +return; + if ( base->next->order2 ) { + SplineRefigureFixup(base->next); +return; + } + if ( !base->nextcpdef ) { + if ( base->pointtype==pt_tangent ) + SplineCharTangentNextCP(base); +return; + } + next = base->next->to; + if ( base->prev!=NULL ) + prev = base->prev->from; + + len = NICE_PROPORTION * sqrt((base->me.x-next->me.x)*(base->me.x-next->me.x) + + (base->me.y-next->me.y)*(base->me.y-next->me.y)); + unit.x = next->me.x - base->me.x; + unit.y = next->me.y - base->me.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + base->nonextcp = false; + + if ( base->pointtype == pt_curve || base->pointtype == pt_hvcurve ) { + if ( prev!=NULL && (base->prevcpdef || base->noprevcp)) { + unit.x = next->me.x - prev->me.x; + unit.y = next->me.y - prev->me.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + if ( base->pointtype == pt_hvcurve ) + BP_HVForce(&unit); + plen = sqrt((base->prevcp.x-base->me.x)*(base->prevcp.x-base->me.x) + + (base->prevcp.y-base->me.y)*(base->prevcp.y-base->me.y)); + base->prevcp.x = base->me.x - plen*unit.x; + base->prevcp.y = base->me.y - plen*unit.y; + if ( snaptoint ) { + base->prevcp.x = rint(base->prevcp.x); + base->prevcp.y = rint(base->prevcp.y); + } + SplineRefigureFixup(base->prev); + } else if ( prev!=NULL ) { + /* The prev control point is fixed. So we've got to use the same */ + /* angle it uses */ + unit.x = base->me.x-base->prevcp.x; + unit.y = base->me.y-base->prevcp.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + } else { + base->prevcp = base->me; + base->noprevcp = true; + base->prevcpdef = true; + } + if ( base->pointtype == pt_hvcurve ) + BP_HVForce(&unit); + } else if ( base->pointtype == pt_corner ) { + if ( next->pointtype != pt_curve && next->pointtype != pt_hvcurve ) { + base->nonextcp = true; + } + } else /* tangent */ { + if ( next->pointtype != pt_curve ) { + base->nonextcp = true; + } else { + if ( prev!=NULL ) { + if ( !base->noprevcp ) { + plen = sqrt((base->prevcp.x-base->me.x)*(base->prevcp.x-base->me.x) + + (base->prevcp.y-base->me.y)*(base->prevcp.y-base->me.y)); + base->prevcp.x = base->me.x - plen*unit.x; + base->prevcp.y = base->me.y - plen*unit.y; + SplineRefigureFixup(base->prev); + } + unit.x = base->me.x-prev->me.x; + unit.y = base->me.y-prev->me.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + } + } + } + if ( base->nonextcp ) + base->nextcp = base->me; + else { + base->nextcp.x = base->me.x + len*unit.x; + base->nextcp.y = base->me.y + len*unit.y; + if ( snaptoint ) { + base->nextcp.x = rint(base->nextcp.x); + base->nextcp.y = rint(base->nextcp.y); + } else { + base->nextcp.x = rint(base->nextcp.x*1024)/1024; + base->nextcp.y = rint(base->nextcp.y*1024)/1024; + } + if ( base->next != NULL ) + SplineRefigureFixup(base->next); + } +} + +void SplineCharDefaultPrevCP(SplinePoint *base) { + SplinePoint *next=NULL, *prev; + double len, nlen, ulen; + BasePoint unit; + extern int snaptoint; + + if ( base->prev==NULL ) +return; + if ( base->prev->order2 ) { + SplineRefigureFixup(base->prev); +return; + } + if ( !base->prevcpdef ) { + if ( base->pointtype==pt_tangent ) + SplineCharTangentPrevCP(base); +return; + } + prev = base->prev->from; + if ( base->next!=NULL ) + next = base->next->to; + + len = NICE_PROPORTION * sqrt((base->me.x-prev->me.x)*(base->me.x-prev->me.x) + + (base->me.y-prev->me.y)*(base->me.y-prev->me.y)); + unit.x = prev->me.x - base->me.x; + unit.y = prev->me.y - base->me.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + base->noprevcp = false; + + if ( base->pointtype == pt_curve || base->pointtype == pt_hvcurve ) { + if ( next!=NULL && (base->nextcpdef || base->nonextcp)) { + unit.x = prev->me.x - next->me.x; + unit.y = prev->me.y - next->me.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + if ( base->pointtype == pt_hvcurve ) + BP_HVForce(&unit); + nlen = sqrt((base->nextcp.x-base->me.x)*(base->nextcp.x-base->me.x) + + (base->nextcp.y-base->me.y)*(base->nextcp.y-base->me.y)); + base->nextcp.x = base->me.x - nlen*unit.x; + base->nextcp.y = base->me.y - nlen*unit.y; + if ( snaptoint ) { + base->nextcp.x = rint(base->nextcp.x); + base->nextcp.y = rint(base->nextcp.y); + } + SplineRefigureFixup(base->next); + } else if ( next!=NULL ) { + /* The next control point is fixed. So we got to use the same */ + /* angle it uses */ + unit.x = base->me.x-base->nextcp.x; + unit.y = base->me.y-base->nextcp.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + } else { + base->nextcp = base->me; + base->nonextcp = true; + base->nextcpdef = true; + } + if ( base->pointtype == pt_hvcurve ) + BP_HVForce(&unit); + } else if ( base->pointtype == pt_corner ) { + if ( prev->pointtype != pt_curve && prev->pointtype != pt_hvcurve ) { + base->noprevcp = true; + } + } else /* tangent */ { + if ( prev->pointtype != pt_curve ) { + base->noprevcp = true; + } else { + if ( next!=NULL ) { + if ( !base->nonextcp ) { + nlen = sqrt((base->nextcp.x-base->me.x)*(base->nextcp.x-base->me.x) + + (base->nextcp.y-base->me.y)*(base->nextcp.y-base->me.y)); + base->nextcp.x = base->me.x - nlen*unit.x; + base->nextcp.y = base->me.y - nlen*unit.y; + SplineRefigureFixup(base->next); + } + unit.x = base->me.x-next->me.x; + unit.y = base->me.y-next->me.y; + ulen = sqrt(unit.x*unit.x + unit.y*unit.y); + if ( ulen!=0 ) + unit.x /= ulen, unit.y /= ulen; + } + } + } + if ( base->noprevcp ) + base->prevcp = base->me; + else { + base->prevcp.x = base->me.x + len*unit.x; + base->prevcp.y = base->me.y + len*unit.y; + if ( snaptoint ) { + base->prevcp.x = rint(base->prevcp.x); + base->prevcp.y = rint(base->prevcp.y); + } else { + base->prevcp.x = rint(base->prevcp.x*1024)/1024; + base->prevcp.y = rint(base->prevcp.y*1024)/1024; + } + if ( base->prev!=NULL ) + SplineRefigureFixup(base->prev); + } +} + + +SplineSet *SplineSetReverse(SplineSet *spl) { + Spline *spline, *first, *next; + BasePoint tp; + SplinePoint *temp; + int bool; + /* reverse the splineset so that what was the start point becomes the end */ + /* and vice versa. This entails reversing every individual spline, and */ + /* each point */ + + first = NULL; + spline = spl->first->next; + if ( spline==NULL ) +return( spl ); /* Only one point, reversal is meaningless */ + + tp = spline->from->nextcp; + spline->from->nextcp = spline->from->prevcp; + spline->from->prevcp = tp; + bool = spline->from->nonextcp; + spline->from->nonextcp = spline->from->noprevcp; + spline->from->noprevcp = bool; + bool = spline->from->nextcpdef; + spline->from->nextcpdef = spline->from->prevcpdef; + spline->from->prevcpdef = bool; + + for ( ; spline!=NULL && spline!=first; spline=next ) { + next = spline->to->next; + + if ( spline->to!=spl->first ) { /* On a closed spline don't want to reverse the first point twice */ + tp = spline->to->nextcp; + spline->to->nextcp = spline->to->prevcp; + spline->to->prevcp = tp; + bool = spline->to->nonextcp; + spline->to->nonextcp = spline->to->noprevcp; + spline->to->noprevcp = bool; + bool = spline->to->nextcpdef; + spline->to->nextcpdef = spline->to->prevcpdef; + spline->to->prevcpdef = bool; + } + + temp = spline->to; + spline->to = spline->from; + spline->from = temp; + spline->from->next = spline; + spline->to->prev = spline; + SplineRefigure(spline); + if ( first==NULL ) first = spline; + } + + if ( spl->first!=spl->last ) { + temp = spl->first; + spl->first = spl->last; + spl->last = temp; + spl->first->prev = NULL; + spl->last->next = NULL; + } + +return( spl ); +} + +static void SplineSetsUntick(SplineSet *spl) { + Spline *spline, *first; + + while ( spl!=NULL ) { + first = NULL; + spl->first->isintersection = false; + for ( spline=spl->first->next; spline!=first && spline!=NULL; spline = spline->to->next ) { + spline->isticked = false; + spline->isneeded = false; + spline->isunneeded = false; + spline->ishorvert = false; + spline->to->isintersection = false; + if ( first==NULL ) first = spline; + } + spl = spl->next; + } +} + +static void SplineSetTick(SplineSet *spl) { + Spline *spline, *first; + + first = NULL; + for ( spline=spl->first->next; spline!=first && spline!=NULL; spline = spline->to->next ) { + spline->isticked = true; + if ( first==NULL ) first = spline; + } +} + +static SplineSet *SplineSetOfSpline(SplineSet *spl,Spline *search) { + Spline *spline, *first; + + while ( spl!=NULL ) { + first = NULL; + for ( spline=spl->first->next; spline!=first && spline!=NULL; spline = spline->to->next ) { + if ( spline==search ) +return( spl ); + if ( first==NULL ) first = spline; + } + spl = spl->next; + } +return( NULL ); +} + +static int SplineInSplineSet(Spline *spline, SplineSet *spl) { + Spline *first, *s; + + first = NULL; + for ( s = spl->first->next; s!=NULL && s!=first; s = s->to->next ) { + if ( s==spline ) +return( true ); + if ( first==NULL ) first = s; + } +return( false ); +} + +#include "edgelist.h" + +static void EdgeListReverse(EdgeList *es, SplineSet *spl) { + int i; + + if ( es->edges!=NULL ) { + for ( i=0; i<es->cnt; ++i ) { + Edge *e; + for ( e = es->edges[i]; e!=NULL; e = e->esnext ) { + if ( SplineInSplineSet(e->spline,spl)) { + e->up = !e->up; + e->t_mmin = 1-e->t_mmin; + e->t_mmax = 1-e->t_mmax; + e->t_cur = 1-e->t_cur; + } + } + } + } +} + +static int SSCheck(SplineSet *base,Edge *active, int up, EdgeList *es,int *changed) { + SplineSet *spl; + if ( active->spline->isticked ) +return( 0 ); + spl = SplineSetOfSpline(base,active->spline); + if ( active->up!=up ) { + SplineSetReverse(spl); + *changed = true; + EdgeListReverse(es,spl); + } + SplineSetTick(spl); +return( 1 ); +} + + +/* The idea behind SplineSetsCorrect is simple. However there are many splinesets */ +/* where it is impossible, so bear in mind that this only works for nice */ +/* splines. Figure 8's, interesecting splines all cause problems */ +/* The outermost spline should be clockwise (up), the next splineset we find */ +/* should be down, if it isn't reverse it (if it's already been dealt with */ +/* then ignore it) */ +SplineSet *SplineSetsCorrect(SplineSet *base,int *changed) { + SplineSet *spl; + int sscnt, check_cnt; + EdgeList es; + DBounds b; + Edge *active=NULL, *apt, *pr, *e; + int i, winding; + + *changed = false; + + SplineSetsUntick(base); + for (sscnt=0,spl=base; spl!=NULL; spl=spl->next, ++sscnt ); + + SplineSetFindBounds(base,&b); + memset(&es,'\0',sizeof(es)); + es.scale = 1.0; + es.mmin = floor(b.miny*es.scale); + es.mmax = ceil(b.maxy*es.scale); + es.omin = b.minx*es.scale; + es.omax = b.maxx*es.scale; + es.layer = ly_fore; /* Not meaningful */ + +/* Give up if we are given unreasonable values (ie. if rounding errors might screw us up) */ + if ( es.mmin<1e5 && es.mmax>-1e5 && es.omin<1e5 && es.omax>-1e5 ) { + es.cnt = (int) (es.mmax-es.mmin) + 1; + es.edges = gcalloc(es.cnt,sizeof(Edge *)); + es.interesting = gcalloc(es.cnt,sizeof(char)); + es.sc = NULL; + es.major = 1; es.other = 0; + FindEdgesSplineSet(base,&es,false); + + check_cnt = 0; + for ( i=0; i<es.cnt && check_cnt<sscnt; ++i ) { + active = ActiveEdgesRefigure(&es,active,i); + if ( es.edges[i]!=NULL ) + continue; /* Just too hard to get the edges sorted when we are at a start vertex */ + if ( /*es.edges[i]==NULL &&*/ !es.interesting[i] && + !(i>0 && es.interesting[i-1]) && !(i>0 && es.edges[i-1]!=NULL) && + !(i<es.cnt-1 && es.edges[i+1]!=NULL) && + !(i<es.cnt-1 && es.interesting[i+1])) /* interesting things happen when we add (or remove) entries */ + continue; /* and where we have extrema */ + for ( apt=active; apt!=NULL; apt = e) { + check_cnt += SSCheck(base,apt,true,&es,changed); + winding = apt->up?1:-1; + for ( pr=apt, e=apt->aenext; e!=NULL && winding!=0; pr=e, e=e->aenext ) { + if ( !e->spline->isticked ) + check_cnt += SSCheck(base,e,winding<0,&es,changed); + if ( pr->up!=e->up ) + winding += (e->up?1:-1); + else if ( (pr->before==e || pr->after==e ) && + (( pr->mmax==i && e->mmin==i ) || + ( pr->mmin==i && e->mmax==i )) ) + /* This just continues the line and doesn't change count */; + else + winding += (e->up?1:-1); + } + /* color a horizontal line that comes out of the last vertex */ + if ( e!=NULL && (e->before==pr || e->after==pr) && + (( pr->mmax==i && e->mmin==i ) || + ( pr->mmin==i && e->mmax==i )) ) { + pr = e; + e = e->aenext; + } + } + } + FreeEdges(&es); + } +return( base ); +} + + +int SplinePointListIsClockwise(const SplineSet *spl) { + EIList el; + EI *active=NULL, *apt, *e; + int i, change,waschange; + SplineChar dummy; + SplineSet *next; + int ret = -1, maybe=-1; + Layer layers[2]; + + if ( spl->first!=spl->last || spl->first->next == NULL ) +return( -1 ); /* Open paths, (open paths with only one point are a special case) */ + + memset(&el,'\0',sizeof(el)); + memset(&dummy,'\0',sizeof(dummy)); + memset(layers,0,sizeof(layers)); + el.layer = ly_fore; + dummy.layers = layers; + dummy.layer_cnt = 2; + dummy.layers[ly_fore].splines = (SplineSet *) spl; + next = spl->next; ((SplineSet *) spl)->next = NULL; + ELFindEdges(&dummy,&el); + if ( el.coordmax[1]-el.coordmin[1] > 1.e6 ) { + LogError( _("Warning: Unreasonably big splines. They will be ignored.\n") ); +return( -1 ); + } + el.major = 1; + ELOrder(&el,el.major); + + waschange = false; + for ( i=0; i<el.cnt && ret==-1; ++i ) { + active = EIActiveEdgesRefigure(&el,active,i,1,&change); + if ( el.ordered[i]!=NULL || el.ends[i] || waschange || change ) { + waschange = change; + if ( active!=NULL ) + maybe = active->up; + continue; /* Just too hard to get the edges sorted when we are at a start vertex */ + } + waschange = change; + for ( apt=active; apt!=NULL && ret==-1; apt = e) { + if ( EISkipExtremum(apt,i+el.low,1)) { + e = apt->aenext->aenext; + continue; + } + ret = apt->up; + break; + } + } + free(el.ordered); + free(el.ends); + ElFreeEI(&el); + ((SplineSet *) spl)->next = next; + if ( ret==-1 ) + ret = maybe; +return( ret ); +} |