diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineorder2.c')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineorder2.c | 1508 |
1 files changed, 0 insertions, 1508 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineorder2.c b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineorder2.c deleted file mode 100644 index e807b105e38..00000000000 --- a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splineorder2.c +++ /dev/null @@ -1,1508 +0,0 @@ -/* 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 <unistd.h> -#include <time.h> -#include <locale.h> -#include <utype.h> -#include <ustring.h> -#include <chardata.h> -#ifdef HAVE_IEEEFP_H -# include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */ -#endif - -/* This file contains utility routines for second order bezier splines */ -/* (ie. truetype) */ -/* The most interesting thing */ -/* it does is to figure out a quadratic approximation to the cubic splines */ -/* that postscript uses. We do this by looking at each spline and running */ -/* from the end toward the beginning, checking approximately every emunit */ -/* There is only one quadratic spline possible for any given interval of the */ -/* cubic. The start and end points are the interval end points (obviously) */ -/* the control point is where the two slopes (at start and end) intersect. */ -/* If this spline is a close approximation to the cubic spline (doesn't */ -/* deviate from it by more than an emunit or so), then we use this interval */ -/* as one of our quadratic splines. */ -/* It may turn out that the "quadratic" spline above is actually linear. Well */ -/* that's ok. It may also turn out that we can't find a good approximation. */ -/* If that's true then just insert a linear segment for an emunit stretch. */ -/* (actually this failure mode may not be possible), but I'm not sure */ -/* Then we play the same trick for the rest of the cubic spline (if any) */ - -/* Does the quadratic spline in ttf approximate the cubic spline in ps */ -/* within one pixel between tmin and tmax (on ps. presumably ttf between 0&1 */ -/* dim is the dimension in which there is the greatest change */ -static int comparespline(Spline *ps, Spline *ttf, real tmin, real tmax, real err) { - int dim=0, other; - real dx, dy, ddim, dt, t; - real d, o; - real ttf_t, sq, val; - DBounds bb; - extended ts[3]; - int i; - - /* Are all points on ttf near points on ps? */ - /* This doesn't answer that question, but rules out gross errors */ - bb.minx = bb.maxx = ps->from->me.x; bb.miny = bb.maxy = ps->from->me.y; - if ( ps->from->nextcp.x>bb.maxx ) bb.maxx = ps->from->nextcp.x; - else bb.minx = ps->from->nextcp.x; - if ( ps->from->nextcp.y>bb.maxy ) bb.maxy = ps->from->nextcp.y; - else bb.miny = ps->from->nextcp.y; - if ( ps->to->prevcp.x>bb.maxx ) bb.maxx = ps->to->prevcp.x; - else if ( ps->to->prevcp.x<bb.minx ) bb.minx = ps->to->prevcp.x; - if ( ps->to->prevcp.y>bb.maxy ) bb.maxy = ps->to->prevcp.y; - else if ( ps->to->prevcp.y<bb.miny ) bb.miny = ps->to->prevcp.y; - if ( ps->to->me.x>bb.maxx ) bb.maxx = ps->to->me.x; - else if ( ps->to->me.x<bb.minx ) bb.minx = ps->to->me.x; - if ( ps->to->me.y>bb.maxy ) bb.maxy = ps->to->me.y; - else if ( ps->to->me.y<bb.miny ) bb.miny = ps->to->me.y; - for ( t=.1; t<1; t+= .1 ) { - d = (ttf->splines[0].b*t+ttf->splines[0].c)*t+ttf->splines[0].d; - o = (ttf->splines[1].b*t+ttf->splines[1].c)*t+ttf->splines[1].d; - if ( d<bb.minx || d>bb.maxx || o<bb.miny || o>bb.maxy ) -return( false ); - } - - /* Are all points on ps near points on ttf? */ - dx = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax - - ((ps->splines[0].a*tmin+ps->splines[0].b)*tmin+ps->splines[0].c)*tmin ; - dy = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax - - ((ps->splines[1].a*tmin+ps->splines[1].b)*tmin+ps->splines[1].c)*tmin ; - if ( dx<0 ) dx = -dx; - if ( dy<0 ) dy = -dy; - if ( dx>dy ) { - dim = 0; - ddim = dx; - } else { - dim = 1; - ddim = dy; - } - other = !dim; - - t = tmin; - dt = (tmax-tmin)/ddim; - for ( t=tmin; t<=tmax; t+= dt ) { - if ( t>tmax-dt/8. ) t = tmax; /* Avoid rounding errors */ - d = ((ps->splines[dim].a*t+ps->splines[dim].b)*t+ps->splines[dim].c)*t+ps->splines[dim].d; - o = ((ps->splines[other].a*t+ps->splines[other].b)*t+ps->splines[other].c)*t+ps->splines[other].d; - if ( ttf->splines[dim].b == 0 ) { - ttf_t = (d-ttf->splines[dim].d)/ttf->splines[dim].c; - } else { - sq = ttf->splines[dim].c*ttf->splines[dim].c - - 4*ttf->splines[dim].b*(ttf->splines[dim].d-d); - if ( sq<0 ) -return( false ); - sq = sqrt(sq); - ttf_t = (-ttf->splines[dim].c-sq)/(2*ttf->splines[dim].b); - if ( ttf_t>=-0.1 && ttf_t<=1.1 ) { /* Optimizer gives us rounding errors */ - /* And tmin/tmax are no longer exact */ - val = (ttf->splines[other].b*ttf_t+ttf->splines[other].c)*ttf_t+ - ttf->splines[other].d; - if ( val>o-err && val<o+err ) - continue; - } - ttf_t = (-ttf->splines[dim].c+sq)/(2*ttf->splines[dim].b); - } - if ( ttf_t>=-0.1 && ttf_t<=1.1 ) { - val = (ttf->splines[other].b*ttf_t+ttf->splines[other].c)*ttf_t+ - ttf->splines[other].d; - if ( val>o-err && val<o+err ) - continue; - } -return( false ); - } - - /* Are representative points on ttf near points on ps? */ - for ( t=.125; t<1; t+= .125 ) { - d = (ttf->splines[dim].b*t+ttf->splines[dim].c)*t+ttf->splines[dim].d; - o = (ttf->splines[other].b*t+ttf->splines[other].c)*t+ttf->splines[other].d; - SplineSolveFull(&ps->splines[dim],d,ts); - for ( i=0; i<3; ++i ) if ( ts[i]!=-1 ) { - val = ((ps->splines[other].a*ts[i]+ps->splines[other].b)*ts[i]+ps->splines[other].c)*ts[i]+ps->splines[other].d; - if ( val>o-err && val<o+err ) - break; - } - if ( i==3 ) -return( false ); - } - -return( true ); -} - -static SplinePoint *MakeQuadSpline(SplinePoint *start,Spline *ttf,real x, - real y, real tmax,SplinePoint *oldend) { - Spline *new = chunkalloc(sizeof(Spline)); - SplinePoint *end = chunkalloc(sizeof(SplinePoint)); - - if ( tmax==1 ) { - end->roundx = oldend->roundx; end->roundy = oldend->roundy; end->dontinterpolate = oldend->dontinterpolate; - x = oldend->me.x; y = oldend->me.y; /* Want it to compare exactly */ - } - end->ttfindex = 0xfffe; - end->nextcpindex = 0xfffe; - end->me.x = end->nextcp.x = x; - end->me.y = end->nextcp.y = y; - end->nonextcp = true; - - *new = *ttf; - new->from = start; start->next = new; - new->to = end; end->prev = new; - if ( new->splines[0].b==0 && new->splines[1].b==0 ) { - end->noprevcp = true; - end->prevcp.x = x; end->prevcp.y = y; - new->islinear = new->knownlinear = true; - } else { - end->prevcp.x = start->nextcp.x = ttf->splines[0].c/2+ttf->splines[0].d; - end->prevcp.y = start->nextcp.y = ttf->splines[1].c/2+ttf->splines[1].d; - start->nonextcp = end->noprevcp = false; - new->isquadratic = true; - } - new->order2 = true; -return( end ); -} - -static int buildtestquads(Spline *ttf,real xmin,real ymin,real cx,real cy, - real x,real y,real tmin,real t,real err,Spline *ps, DBounds *psbb) { - real fudge; - - /* test the control points are reasonable */ - fudge = (psbb->maxx-psbb->minx) + (psbb->maxy-psbb->miny); - if ( cx<psbb->minx-fudge || cx>psbb->maxx+fudge ) -return( false ); - if ( cy<psbb->miny-fudge || cy>psbb->maxy+fudge ) -return( false ); - - ttf->splines[0].d = xmin; - ttf->splines[0].c = 2*(cx-xmin); - ttf->splines[0].b = xmin+x-2*cx; - ttf->splines[1].d = ymin; - ttf->splines[1].c = 2*(cy-ymin); - ttf->splines[1].b = ymin+y-2*cy; - if ( comparespline(ps,ttf,tmin,t,err) ) -return( true ); - -#if 0 - /* In a few cases, the following code will find a match when the above */ - /* would not. We move the control point slightly along a vector normal */ - /* to the vector between the end-points. What I really want is along */ - /* a vector midway between the two slopes, but that's too hard to figure */ - sq = sqrt((x-xmin)*(x-xmin) + (y-ymin)*(y-ymin)); - norm.x = (ymin-y)/sq; norm.y = (x-xmin)/sq; - - ttf->splines[0].c += err*norm.x; - ttf->splines[0].b -= err*norm.x; - ttf->splines[1].c += err*norm.y; - ttf->splines[1].b -= err*norm.y; - if ( comparespline(ps,ttf,tmin,t,err) ) -return( true ); - - ttf->splines[0].c -= 2*err*norm.x; - ttf->splines[0].b += 2*err*norm.x; - ttf->splines[1].c -= 2*err*norm.y; - ttf->splines[1].b += 2*err*norm.y; - if ( comparespline(ps,ttf,tmin,t,err) ) -return( true ); - - ttf->splines[0].c = 2*(cx-xmin); - ttf->splines[0].b = xmin+x-2*cx; - ttf->splines[1].c = 2*(cy-ymin); - ttf->splines[1].b = ymin+y-2*cy; -#endif -return( false ); -} - -static SplinePoint *LinearSpline(Spline *ps,SplinePoint *start, real tmax) { - real x,y; - Spline *new = chunkalloc(sizeof(Spline)); - SplinePoint *end = chunkalloc(sizeof(SplinePoint)); - - x = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax+ps->splines[0].d; - y = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax+ps->splines[1].d; - if ( tmax==1 ) { - SplinePoint *oldend = ps->to; - end->roundx = oldend->roundx; end->roundy = oldend->roundy; end->dontinterpolate = oldend->dontinterpolate; - x = oldend->me.x; y = oldend->me.y; /* Want it to compare exactly */ - } - end->ttfindex = 0xfffe; - end->nextcpindex = 0xfffe; - end->me.x = end->nextcp.x = end->prevcp.x = x; - end->me.y = end->nextcp.y = end->prevcp.y = y; - end->nonextcp = end->noprevcp = start->nonextcp = true; - new->from = start; start->next = new; - new->to = end; end->prev = new; - new->splines[0].d = start->me.x; - new->splines[0].c = (x-start->me.x); - new->splines[1].d = start->me.y; - new->splines[1].c = (y-start->me.y); - new->order2 = true; - new->islinear = new->knownlinear = true; -return( end ); -} - -static SplinePoint *_ttfapprox(Spline *ps,real tmin, real tmax, SplinePoint *start) { - int dim=0; - real dx, dy, ddim, dt, t, err; - real x,y, xmin, ymin; - real dxdtmin, dydtmin, dxdt, dydt; - SplinePoint *sp; - real cx, cy; - Spline ttf; - int cnt = -1, forceit, unforceable; - BasePoint end, rend, dend; - DBounds bb; - - rend.x = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax + ps->splines[0].d; - rend.y = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax + ps->splines[1].d; - end.x = rint( rend.x ); - end.y = rint( rend.y ); - dend.x = (3*ps->splines[0].a*tmax+2*ps->splines[0].b)*tmax+ps->splines[0].c; - dend.y = (3*ps->splines[1].a*tmax+2*ps->splines[1].b)*tmax+ps->splines[1].c; - memset(&ttf,'\0',sizeof(ttf)); - - bb.minx = bb.maxx = ps->from->me.x; - if ( ps->from->nextcp.x > bb.maxx ) bb.maxx = ps->from->nextcp.x; - else if ( ps->from->nextcp.x < bb.minx ) bb.minx = ps->from->nextcp.x; - if ( ps->to->prevcp.x > bb.maxx ) bb.maxx = ps->to->prevcp.x; - else if ( ps->to->prevcp.x < bb.minx ) bb.minx = ps->to->prevcp.x; - if ( ps->to->me.x > bb.maxx ) bb.maxx = ps->to->me.x; - else if ( ps->to->me.x < bb.minx ) bb.minx = ps->to->me.x; - bb.miny = bb.maxy = ps->from->me.y; - if ( ps->from->nextcp.y > bb.maxy ) bb.maxy = ps->from->nextcp.y; - else if ( ps->from->nextcp.y < bb.miny ) bb.miny = ps->from->nextcp.y; - if ( ps->to->prevcp.y > bb.maxy ) bb.maxy = ps->to->prevcp.y; - else if ( ps->to->prevcp.y < bb.miny ) bb.miny = ps->to->prevcp.y; - if ( ps->to->me.y > bb.maxy ) bb.maxy = ps->to->me.y; - else if ( ps->to->me.y < bb.miny ) bb.miny = ps->to->me.y; - - tail_recursion: - ++cnt; - - xmin = start->me.x; - ymin = start->me.y; - dxdtmin = (3*ps->splines[0].a*tmin+2*ps->splines[0].b)*tmin + ps->splines[0].c; - dydtmin = (3*ps->splines[1].a*tmin+2*ps->splines[1].b)*tmin + ps->splines[1].c; - - dx = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax - - ((ps->splines[0].a*tmin+ps->splines[0].b)*tmin+ps->splines[0].c)*tmin ; - dy = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax - - ((ps->splines[1].a*tmin+ps->splines[1].b)*tmin+ps->splines[1].c)*tmin ; - if ( dx<0 ) dx = -dx; - if ( dy<0 ) dy = -dy; - if ( dx>dy ) { - dim = 0; - ddim = dx; - } else { - dim = 1; - ddim = dy; - } - if (( err = ddim/3000 )<1 ) err = 1; - - if ( ddim<2 || - (dend.x==0 && rint(start->me.x)==end.x && dy<=10 && cnt!=0) || - (dend.y==0 && rint(start->me.y)==end.y && dx<=10 && cnt!=0) ) { - if ( cnt==0 || start->noprevcp ) -return( LinearSpline(ps,start,tmax)); - /* If the end point is very close to where we want to be, then just */ - /* pretend it's right */ - start->prev->splines[0].b += ps->to->me.x-start->me.x; - start->prev->splines[1].b += ps->to->me.y-start->me.y; - start->prevcp.x += rend.x-start->me.x; - start->prevcp.y += rend.y-start->me.y; - if ( start->prev!=NULL && !start->prev->from->nonextcp ) - start->prev->from->nextcp = start->prevcp; - start->me = rend; -return( start ); - } - - dt = (tmax-tmin)/ddim; - forceit = false; - force_end: - unforceable = false; - for ( t=tmax; t>tmin+dt/128; t-= dt ) { /* dt/128 is a hack to avoid rounding errors */ - x = ((ps->splines[0].a*t+ps->splines[0].b)*t+ps->splines[0].c)*t+ps->splines[0].d; - y = ((ps->splines[1].a*t+ps->splines[1].b)*t+ps->splines[1].c)*t+ps->splines[1].d; - dxdt = (3*ps->splines[0].a*t+2*ps->splines[0].b)*t + ps->splines[0].c; - dydt = (3*ps->splines[1].a*t+2*ps->splines[1].b)*t + ps->splines[1].c; - /* if the slopes are parallel at the ends there can be no bezier quadratic */ - /* (control point is where the splines intersect. But if they are */ - /* parallel and colinear then there is a line between 'em */ - if ( ( dxdtmin==0 && dxdt==0 ) || (dydtmin==0 && dydt==0) || - ( dxdt!=0 && dxdtmin!=0 && - RealNearish(dydt/dxdt,dydtmin/dxdtmin)) ) - continue; - - if ( dxdt==0 ) - cx=x; - else if ( dxdtmin==0 ) - cx=xmin; - else - cx = -(ymin-(dydtmin/dxdtmin)*xmin-y+(dydt/dxdt)*x)/(dydtmin/dxdtmin-dydt/dxdt); - if ( dydt==0 ) - cy=y; - else if ( dydtmin==0 ) - cy=ymin; - else - cy = -(xmin-(dxdtmin/dydtmin)*ymin-x+(dxdt/dydt)*y)/(dxdtmin/dydtmin-dxdt/dydt); - if ( t==tmax && ((cy==y && cx==x) || (cy==ymin && cx==xmin)) ) - unforceable = true; - /* Make the quadratic spline from (xmin,ymin) through (cx,cy) to (x,y)*/ - if ( forceit || buildtestquads(&ttf,xmin,ymin,cx,cy,x,y,tmin,t,err,ps,&bb)) { - if ( !forceit && !unforceable && (rend.x-x)*(rend.x-x)+(rend.y-y)*(rend.y-y)<4*4 ) { - forceit = true; - goto force_end; - } - sp = MakeQuadSpline(start,&ttf,x,y,t,ps->to); - forceit = false; - if ( t==tmax ) -return( sp ); - tmin = t; - start = sp; - goto tail_recursion; - } - ttf.splines[0].d = xmin; - ttf.splines[0].c = x-xmin; - ttf.splines[0].b = 0; - ttf.splines[1].d = ymin; - ttf.splines[1].c = y-ymin; - ttf.splines[1].b = 0; - if ( comparespline(ps,&ttf,tmin,t,err) ) { - sp = LinearSpline(ps,start,t); - if ( t==tmax ) -return( sp ); - tmin = t; - start = sp; - goto tail_recursion; - } - } - tmin += dt; - start = LinearSpline(ps,start,tmin); - goto tail_recursion; -} - -static SplinePoint *__ttfApprox(Spline *ps,real tmin, real tmax, SplinePoint *start) { - extended inflect[2]; - int i=0; -#if 1 - SplinePoint *end; - Spline *s, *next; - - end = _ttfapprox(ps,tmin,tmax,start); - if ( ps->knownlinear ) -return( end ); - for ( s=start->next; s!=NULL && !s->islinear; s=s->to->next ); - if ( s==NULL ) -return( end ); - for ( s=start->next; s!=NULL ; s=next ) { - next = s->to->next; - SplinePointFree(s->to); - SplineFree(s); - } -#endif -/* Hmm. With my algorithem, checking for points of inflection actually makes */ -/* things worse. It uses more points and the splines don't join as nicely */ -/* However if we get a bad match (a line) in the normal approx, then check */ -/* Err... I was computing POI incorrectly. Above statement might not be correct*/ - /* no points of inflection in quad splines */ - - i = Spline2DFindPointsOfInflection(ps, inflect); - if ( i==2 ) { - if ( RealNearish(inflect[0],inflect[1]) ) - --i; - else if ( inflect[0]>inflect[1] ) { - real temp = inflect[0]; - inflect[0] = inflect[1]; - inflect[1] = temp; - } - } - if ( i!=0 ) { - start = _ttfapprox(ps,tmin,inflect[0],start); - tmin = inflect[0]; - if ( i==2 ) { - start = _ttfapprox(ps,tmin,inflect[1],start); - tmin = inflect[1]; - } - } -return( _ttfapprox(ps,tmin,tmax,start)); -} - -#if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION) -typedef struct qpoint { - BasePoint bp; - BasePoint cp; - double t; -} QPoint; - -static int comparedata(Spline *ps,QPoint *data,int qfirst,int qlast, - int round_to_int ) { - Spline ttf; - int i; - double err = round_to_int ? 1.5 : 1; - - if ( qfirst==qlast ) /* happened (was a bug) */ -return( false ); - - /* Control points diametrically opposed */ - if ( (data[qlast-2].cp.x-ps->to->me.x)*(ps->to->prevcp.x-ps->to->me.x) + - (data[qlast-2].cp.y-ps->to->me.y)*(ps->to->prevcp.y-ps->to->me.y)<0 ) -return( false ); - if ( (data[qfirst-1].cp.x-ps->from->me.x)*(ps->from->nextcp.x-ps->from->me.x) + - (data[qfirst-1].cp.y-ps->from->me.y)*(ps->from->nextcp.y-ps->from->me.y)<0 ) -return( false ); - - memset(&ttf,0,sizeof(ttf)); - for ( i=qfirst; i<qlast; ++i ) { - ttf.splines[0].d = data[i-1].bp.x; - ttf.splines[0].c = 2*(data[i-1].cp.x-data[i-1].bp.x); - ttf.splines[0].b = data[i-1].bp.x+data[i].bp.x-2*data[i-1].cp.x; - ttf.splines[1].d = data[i-1].bp.y; - ttf.splines[1].c = 2*(data[i-1].cp.y-data[i-1].bp.y); - ttf.splines[1].b = data[i-1].bp.y+data[i].bp.y-2*data[i-1].cp.y; - if ( !comparespline(ps,&ttf,data[i-1].t,data[i].t,err) ) -return( false ); - } -return( true ); -} - -static SplinePoint *CvtDataToSplines(QPoint *data,int qfirst,int qlast,SplinePoint *start) { - SplinePoint *end; - int i; - - for ( i=qfirst; i<qlast; ++i ) { - end = SplinePointCreate(data[i].bp.x,data[i].bp.y); - start->nextcp = end->prevcp = data[i-1].cp; - start->nonextcp = end->noprevcp = false; - if (( data[i-1].cp.x == data[i].bp.x && data[i-1].cp.y == data[i].bp.y ) || - ( data[i-1].cp.x == start->me.x && data[i-1].cp.y == start->me.y )) - start->nonextcp = end->noprevcp = true; - SplineMake2(start,end); - start = end; - } -return( start ); -} - -static int SplineWithWellBehavedControlPoints(Spline *ps) { - BasePoint splineunit; - double splinelen, npos, ppos; - - splineunit.x = ps->to->me.x - ps->from->me.x; - splineunit.y = ps->to->me.y - ps->from->me.y; - splinelen = sqrt(splineunit.x*splineunit.x + splineunit.y*splineunit.y); - if ( splinelen!=0 ) { - splineunit.x /= splinelen; - splineunit.y /= splinelen; - } - - npos = (ps->from->nextcp.x-ps->from->me.x) * splineunit.x + - (ps->from->nextcp.y-ps->from->me.y) * splineunit.y; - ppos = (ps->to->prevcp.x-ps->from->me.x) * splineunit.x + - (ps->to->prevcp.y-ps->from->me.y) * splineunit.y; -return( npos>=0 && /* npos<=ppos &&*/ ppos<=splinelen ); -} - -static int PrettyApprox(Spline *ps,double tmin, double tmax, - QPoint *data, int qcnt, int round_to_int ) { - int ptcnt, q, i; - double distance, dx, dy, tstart; - BasePoint end, mid, slopemin, slopemid, slopeend; - BasePoint splineunit, start; - double splinelen, midpos, lastpos, lastpos2, cppos; - int do_good_spline_check; - QPoint data2[12]; - - if ( qcnt==-1 ) -return( -1 ); - - slopemin.x = (3*ps->splines[0].a*tmin+2*ps->splines[0].b)*tmin+ps->splines[0].c; - slopemin.y = (3*ps->splines[1].a*tmin+2*ps->splines[1].b)*tmin+ps->splines[1].c; - if ( slopemin.x==0 && slopemin.y==0 ) { - double t = tmin + (tmax-tmin)/256; - /* If there is no control point for this end point, then the slope is */ - /* 0/0 at the end point. Which isn't useful, it leads to a quadratic */ - /* control point at the end point, but this one is real because it */ - /* is used to interpolate the next point, but we get all confused */ - /* because we don't expect a real cp to be on the base point. */ - slopemin.x = (3*ps->splines[0].a*t+2*ps->splines[0].b)*t+ps->splines[0].c; - slopemin.y = (3*ps->splines[1].a*t+2*ps->splines[1].b)*t+ps->splines[1].c; - } - - end.x = ((ps->splines[0].a*tmax+ps->splines[0].b)*tmax+ps->splines[0].c)*tmax+ps->splines[0].d; - end.y = ((ps->splines[1].a*tmax+ps->splines[1].b)*tmax+ps->splines[1].c)*tmax+ps->splines[1].d; - slopeend.x = (3*ps->splines[0].a*tmax+2*ps->splines[0].b)*tmax+ps->splines[0].c; - slopeend.y = (3*ps->splines[1].a*tmax+2*ps->splines[1].b)*tmax+ps->splines[1].c; - if ( slopemin.x==0 && slopemin.y==0 ) { - double t = tmax - (tmax-tmin)/256; - /* Same problem as above, except at the other end */ - slopeend.x = (3*ps->splines[0].a*t+2*ps->splines[0].b)*t+ps->splines[0].c; - slopeend.y = (3*ps->splines[1].a*t+2*ps->splines[1].b)*t+ps->splines[1].c; - } - - start.x = data[qcnt-1].bp.x; - start.y = data[qcnt-1].bp.y; - splineunit.x = end.x - start.x; - splineunit.y = end.y - start.y; - splinelen = sqrt(splineunit.x*splineunit.x + splineunit.y*splineunit.y); - if ( splinelen!=0 ) { - splineunit.x /= splinelen; - splineunit.y /= splinelen; - } - do_good_spline_check = SplineWithWellBehavedControlPoints(ps); - - if ( round_to_int && tmax!=1 ) { - end.x = rint( end.x ); - end.y = rint( end.y ); - } - - dx = end.x-data[qcnt-1].bp.x; dy = end.y-data[qcnt-1].bp.y; - distance = dx*dx + dy*dy; - - if ( distance<.3 ) { - /* This is meaningless in truetype, use a line */ - data[qcnt-1].cp = data[qcnt-1].bp; - data[qcnt].bp = end; - data[qcnt].t = 1; -return( qcnt+1 ); - } - - for ( ptcnt=0; ptcnt<10; ++ptcnt ) { - if ( ptcnt>1 && distance/(ptcnt*ptcnt)<100 ) -return( -1 ); /* Points too close for a good approx */ - q = qcnt; - data2[ptcnt+1].bp = end; - lastpos=0; lastpos2 = splinelen; - for ( i=0; i<=ptcnt; ++i ) { - tstart = (tmin*(ptcnt-i) + tmax*(i+1))/(ptcnt+1); - mid.x = ((ps->splines[0].a*tstart+ps->splines[0].b)*tstart+ps->splines[0].c)*tstart+ps->splines[0].d; - mid.y = ((ps->splines[1].a*tstart+ps->splines[1].b)*tstart+ps->splines[1].c)*tstart+ps->splines[1].d; - if ( i==0 ) { - slopemid.x = (3*ps->splines[0].a*tstart+2*ps->splines[0].b)*tstart+ps->splines[0].c; - slopemid.y = (3*ps->splines[1].a*tstart+2*ps->splines[1].b)*tstart+ps->splines[1].c; - if ( slopemid.x==0 ) - data[q-1].cp.x=mid.x; - else if ( slopemin.x==0 ) - data[q-1].cp.x=data[q-1].bp.x; - else if ( RealNear(slopemin.y/slopemin.x,slopemid.y/slopemid.x) ) - break; - else - data[q-1].cp.x = -(data[q-1].bp.y-(slopemin.y/slopemin.x)*data[q-1].bp.x-mid.y+(slopemid.y/slopemid.x)*mid.x)/(slopemin.y/slopemin.x-slopemid.y/slopemid.x); - if ( slopemid.y==0 ) - data[q-1].cp.y=mid.y; - else if ( slopemin.y==0 ) - data[q-1].cp.y=data[q-1].bp.y; - else if ( RealNear(slopemin.x/slopemin.y,slopemid.x/slopemid.y) ) - break; - else - data[q-1].cp.y = -(data[q-1].bp.x-(slopemin.x/slopemin.y)*data[q-1].bp.y-mid.x+(slopemid.x/slopemid.y)*mid.y)/(slopemin.x/slopemin.y-slopemid.x/slopemid.y); - } else { - data[q-1].cp.x = 2*data[q-1].bp.x - data[q-2].cp.x; - data[q-1].cp.y = 2*data[q-1].bp.y - data[q-2].cp.y; - } - - midpos = (mid.x-start.x)*splineunit.x + (mid.y-start.y)*splineunit.y; - cppos = (data[q-1].cp.x-start.x)*splineunit.x + (data[q-1].cp.y-start.y)*splineunit.y; - - if ( ((do_good_spline_check || i!=0 ) && cppos<lastpos) || cppos>midpos ) { - i = 0; /* Means we failed */ - break; - } - lastpos = midpos; - - data[q].bp = mid; - data[q++].t = tstart; - - tstart = (tmax*(ptcnt-i) + tmin*(i+1))/(ptcnt+1); - mid.x = ((ps->splines[0].a*tstart+ps->splines[0].b)*tstart+ps->splines[0].c)*tstart+ps->splines[0].d; - mid.y = ((ps->splines[1].a*tstart+ps->splines[1].b)*tstart+ps->splines[1].c)*tstart+ps->splines[1].d; - if ( i==0 ) { - slopemid.x = (3*ps->splines[0].a*tstart+2*ps->splines[0].b)*tstart+ps->splines[0].c; - slopemid.y = (3*ps->splines[1].a*tstart+2*ps->splines[1].b)*tstart+ps->splines[1].c; - if ( slopemid.x==0 ) - data2[ptcnt-i].cp.x=mid.x; - else if ( slopeend.x==0 ) - data2[ptcnt-i].cp.x=data2[ptcnt-i+1].bp.x; - else if ( RealNear(slopeend.y/slopeend.x,slopemid.y/slopemid.x) ) - break; - else - data2[ptcnt-i].cp.x = -(data2[ptcnt-i+1].bp.y-(slopeend.y/slopeend.x)*data2[ptcnt-i+1].bp.x-mid.y+(slopemid.y/slopemid.x)*mid.x)/(slopeend.y/slopeend.x-slopemid.y/slopemid.x); - if ( slopemid.y==0 ) - data2[ptcnt-i].cp.y=mid.y; - else if ( slopeend.y==0 ) - data2[ptcnt-i].cp.y=data2[ptcnt-i+1].bp.y; - else if ( RealNear(slopeend.x/slopeend.y,slopemid.x/slopemid.y) ) - break; - else - data2[ptcnt-i].cp.y = -(data2[ptcnt-i+1].bp.x-(slopeend.x/slopeend.y)*data2[ptcnt-i+1].bp.y-mid.x+(slopemid.x/slopemid.y)*mid.y)/(slopeend.x/slopeend.y-slopemid.x/slopemid.y); - } else { - data2[ptcnt-i].cp.x = 2*data2[ptcnt-i+1].bp.x - data2[ptcnt-i+1].cp.x; - data2[ptcnt-i].cp.y = 2*data2[ptcnt-i+1].bp.y - data2[ptcnt-i+1].cp.y; - } - data2[ptcnt-i].bp = mid; - - midpos = (mid.x-start.x)*splineunit.x + (mid.y-start.y)*splineunit.y; - cppos = (data2[ptcnt-i].cp.x-start.x)*splineunit.x + (data2[ptcnt-i].cp.y-start.y)*splineunit.y; - if ( ((do_good_spline_check || i!=0 ) && cppos>lastpos2) || cppos<midpos ) { - i = 0; /* Means we failed */ - break; - } - lastpos2 = midpos; - - } - if ( i==0 ) - continue; - if ( (data2[ptcnt+1].bp.x-data2[ptcnt].bp.x)*(data2[ptcnt].cp.x-data2[ptcnt].bp.x)<0 || - (data2[ptcnt+1].bp.y-data2[ptcnt].bp.y)*(data2[ptcnt].cp.y-data2[ptcnt].bp.y)<0 ) { - /* data2 are bad ... don't use them */; - } else if ( (data[qcnt-1].bp.x-data[qcnt].bp.x)*(data[qcnt-1].cp.x-data[qcnt].bp.x)<0 || - (data[qcnt-1].bp.y-data[qcnt].bp.y)*(data[qcnt-1].cp.y-data[qcnt].bp.y)<0 ) { - /* data are bad */; - for ( i=0; i<=ptcnt; ++i ) { - data[qcnt+i-1].cp = data2[i].cp; - data[qcnt+i-1].bp = data2[i].bp; - } - } else { - for ( i=0; i<=ptcnt; ++i ) { - if ( ptcnt!=0 ) { - data[qcnt+i-1].cp.x = (data[qcnt+i-1].cp.x*(ptcnt-i) + data2[i].cp.x*i)/ptcnt; - data[qcnt+i-1].cp.y = (data[qcnt+i-1].cp.y*(ptcnt-i) + data2[i].cp.y*i)/ptcnt; - } - } - } - if ( round_to_int ) { - for ( i=0; i<=ptcnt; ++i ) { - data[qcnt+i-1].cp.x = rint( data[qcnt+i-1].cp.x ); - data[qcnt+i-1].cp.y = rint( data[qcnt+i-1].cp.y ); - } - } - for ( i=0; i<ptcnt; ++i ) { - data[qcnt+i].bp.x = (data[qcnt+i].cp.x + data[qcnt+i-1].cp.x)/2; - data[qcnt+i].bp.y = (data[qcnt+i].cp.y + data[qcnt+i-1].cp.y)/2; - } - if ( comparedata(ps,data,qcnt,q,round_to_int)) -return( q ); - } -return( -1 ); -} -#endif - -static SplinePoint *AlreadyQuadraticCheck(Spline *ps, SplinePoint *start) { - SplinePoint *sp; - - if ( (RealNearish(ps->splines[0].a,0) && RealNearish(ps->splines[1].a,0)) || - ((ps->splines[0].b!=0 && RealNearish(ps->splines[0].a/ps->splines[0].b,0)) && - (ps->splines[1].b!=0 && RealNearish(ps->splines[1].a/ps->splines[1].b,0))) ) { - /* Already Quadratic, just need to find the control point */ - /* Or linear, in which case we don't need to do much of anything */ - Spline *spline; - sp = chunkalloc(sizeof(SplinePoint)); - sp->me.x = ps->to->me.x; sp->me.y = ps->to->me.y; - sp->roundx = ps->to->roundx; sp->roundy = ps->to->roundy; sp->dontinterpolate = ps->to->dontinterpolate; - sp->ttfindex = 0xfffe; - sp->nextcpindex = 0xfffe; - sp->nonextcp = true; - spline = chunkalloc(sizeof(Spline)); - spline->order2 = true; - spline->from = start; - spline->to = sp; - spline->splines[0] = ps->splines[0]; spline->splines[1] = ps->splines[1]; - start->next = sp->prev = spline; - if ( ps->knownlinear ) { - spline->islinear = spline->knownlinear = true; - start->nonextcp = sp->noprevcp = true; - start->nextcp = start->me; - sp->prevcp = sp->me; - } else { - start->nonextcp = sp->noprevcp = false; - start->nextcp.x = sp->prevcp.x = (ps->splines[0].c+2*ps->splines[0].d)/2; - start->nextcp.y = sp->prevcp.y = (ps->splines[1].c+2*ps->splines[1].d)/2; - } -return( sp ); - } -return( NULL ); -} - -static SplinePoint *ttfApprox(Spline *ps, SplinePoint *start) { -#if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION) - extended magicpoints[6], last; - int cnt, i, j, qcnt; - QPoint data[8*10]; - int round_to_int = - /* The end points are at integer points, or one coord is at half while */ - /* the other is at an integer (ie. condition for ttf interpolated point)*/ - ((ps->from->me.x==rint(ps->from->me.x) && - ps->from->me.y==rint(ps->from->me.y)) || - (ps->from->me.x==rint(ps->from->me.x) && - ps->from->me.x==ps->from->nextcp.x && - ps->from->me.y!=ps->from->nextcp.y && - 2*ps->from->me.y==rint(2*ps->from->me.y)) || - (ps->from->me.y==rint(ps->from->me.y) && - ps->from->me.y==ps->from->nextcp.y && - ps->from->me.x!=ps->from->nextcp.x && - 2*ps->from->me.x==rint(2*ps->from->me.x)) ) && - ((ps->to->me.x == rint(ps->to->me.x) && - ps->to->me.y == rint(ps->to->me.y)) || - (ps->to->me.x==rint(ps->to->me.x) && - ps->to->me.x==ps->to->prevcp.x && - ps->to->me.y!=ps->to->prevcp.y && - 2*ps->to->me.y==rint(2*ps->to->me.y)) || - (ps->to->me.y==rint(ps->to->me.y) && - ps->to->me.y==ps->to->prevcp.y && - ps->to->me.x!=ps->to->prevcp.x && - 2*ps->to->me.x==rint(2*ps->to->me.x)) ); -#endif - SplinePoint *ret; -/* Divide the spline up at extrema and points of inflection. The first */ -/* because ttf splines should have points at their extrema, the second */ -/* because quadratic splines can't have points of inflection. */ -/* Let's not do the first (extrema) AddExtrema does this better and we */ -/* don't want unneeded extrema. */ -/* And sometimes we don't want to look at the points of inflection either*/ - - if (( ret = AlreadyQuadraticCheck(ps,start))!=NULL ) -return( ret ); - -#if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION) - qcnt = 1; - data[0].bp = ps->from->me; - data[0].t = 0; - qcnt = PrettyApprox(ps,0,1,data,qcnt,round_to_int); - if ( qcnt!=-1 ) -return( CvtDataToSplines(data,1,qcnt,start)); - - cnt = 0; - /* cnt = Spline2DFindExtrema(ps,magicpoints);*/ - - cnt += Spline2DFindPointsOfInflection(ps,magicpoints+cnt); - - /* remove points outside range */ - for ( i=0; i<cnt; ++i ) { - if ( magicpoints[i]<=0 || magicpoints[i]>=1 ) { - for ( j=i+1; j<cnt; ++j ) - magicpoints[j-1] = magicpoints[j]; - --cnt; - --i; - } - } - /* sort points */ - for ( i=0; i<cnt; ++i ) for ( j=i+1; j<cnt; ++j ) { - if ( magicpoints[i]>magicpoints[j] ) { - double temp = magicpoints[i]; - magicpoints[i] = magicpoints[j]; - magicpoints[j] = temp; - } - } - /* Remove duplicates */ - for ( i=1; i<cnt; ++i ) { - while ( i<cnt && RealNear(magicpoints[i-1],magicpoints[i])) { - --cnt; - for ( j=i ; j<cnt; ++j ) - magicpoints[j] = magicpoints[j+1]; - magicpoints[cnt] = -1; - } - } - - qcnt = 1; - last = 0; - for ( i=0; i<cnt; ++i ) { - qcnt = PrettyApprox(ps,last,magicpoints[i],data,qcnt,round_to_int); - last = magicpoints[i]; - } - qcnt = PrettyApprox(ps,last,1,data,qcnt,round_to_int); - if ( qcnt!=-1 ) -return( CvtDataToSplines(data,1,qcnt,start)); -#endif - -return( __ttfApprox(ps,0,1,start)); -} - -static void ttfCleanup(SplinePoint *from) { - SplinePoint *test, *next; - - for ( test = from; test->next!=NULL; test = next ) { - next = test->next->to; - /* Too close together to be meaningful when output as ttf */ - if ( rint(test->me.x) == rint(next->me.x) && - rint(test->me.y) == rint(next->me.y) ) { - if ( next->next==NULL || next==from ) { - if ( test==from ) - break; - next->prevcp = test->prevcp; - next->noprevcp = test->noprevcp; - next->prev = test->prev; - next->prev->to = next; - SplineFree(test->next); - SplinePointFree(test); - } else { - test->nextcp = next->nextcp; - test->nonextcp = next->nonextcp; - test->next = next->next; - test->next->from = test; - SplineFree(next->prev); - SplinePointFree(next); - next = test->next->to; - } - } - if ( next==from ) - break; - } -} - -SplinePoint *SplineTtfApprox(Spline *ps) { - SplinePoint *from; - from = chunkalloc(sizeof(SplinePoint)); - *from = *ps->from; - from->hintmask = NULL; - ttfApprox(ps,from); -return( from ); -} - -SplineSet *SSttfApprox(SplineSet *ss) { - SplineSet *ret = chunkalloc(sizeof(SplineSet)); - Spline *spline, *first; - - ret->first = chunkalloc(sizeof(SplinePoint)); - *ret->first = *ss->first; - if ( ret->first->hintmask != NULL ) { - ret->first->hintmask = chunkalloc(sizeof(HintMask)); - memcpy(ret->first->hintmask,ss->first->hintmask,sizeof(HintMask)); - } - ret->last = ret->first; - - first = NULL; - for ( spline=ss->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) { - ret->last = ttfApprox(spline,ret->last); - ret->last->ptindex = spline->to->ptindex; - ret->last->ttfindex = spline->to->ttfindex; - ret->last->nextcpindex = spline->to->nextcpindex; - if ( spline->to->hintmask != NULL ) { - ret->last->hintmask = chunkalloc(sizeof(HintMask)); - memcpy(ret->last->hintmask,spline->to->hintmask,sizeof(HintMask)); - } - if ( first==NULL ) first = spline; - } - if ( ss->first==ss->last ) { - if ( ret->last!=ret->first ) { - ret->first->prevcp = ret->last->prevcp; - ret->first->noprevcp = ret->last->noprevcp; - ret->first->prev = ret->last->prev; - ret->last->prev->to = ret->first; - SplinePointFree(ret->last); - ret->last = ret->first; - } - } - ttfCleanup(ret->first); - SPLCatagorizePoints(ret); -return( ret ); -} - -SplineSet *SplineSetsTTFApprox(SplineSet *ss) { - SplineSet *head=NULL, *last, *cur; - - while ( ss!=NULL ) { - cur = SSttfApprox(ss); - if ( head==NULL ) - head = cur; - else - last->next = cur; - last = cur; - ss = ss->next; - } -return( head ); -} - -SplineSet *SSPSApprox(SplineSet *ss) { - SplineSet *ret = chunkalloc(sizeof(SplineSet)); - Spline *spline, *first; - SplinePoint *to; - - ret->first = chunkalloc(sizeof(SplinePoint)); - *ret->first = *ss->first; - if ( ret->first->hintmask != NULL ) { - ret->first->hintmask = chunkalloc(sizeof(HintMask)); - memcpy(ret->first->hintmask,ss->first->hintmask,sizeof(HintMask)); - } - ret->last = ret->first; - - first = NULL; - for ( spline=ss->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) { - to = chunkalloc(sizeof(SplinePoint)); - *to = *spline->to; - if ( to->hintmask != NULL ) { - to->hintmask = chunkalloc(sizeof(HintMask)); - memcpy(to->hintmask,spline->to->hintmask,sizeof(HintMask)); - } - if ( !spline->knownlinear ) { - ret->last->nextcp.x = spline->splines[0].c/3 + ret->last->me.x; - ret->last->nextcp.y = spline->splines[1].c/3 + ret->last->me.y; - to->prevcp.x = ret->last->nextcp.x+ (spline->splines[0].b+spline->splines[0].c)/3; - to->prevcp.y = ret->last->nextcp.y+ (spline->splines[1].b+spline->splines[1].c)/3; - } - SplineMake3(ret->last,to); - ret->last = to; - if ( first==NULL ) first = spline; - } - if ( ss->first==ss->last ) { - if ( ret->last!=ret->first ) { - ret->first->prevcp = ret->last->prevcp; - ret->first->noprevcp = ret->last->noprevcp; - ret->first->prev = ret->last->prev; - ret->last->prev->to = ret->first; - SplinePointFree(ret->last); - ret->last = ret->first; - } - } - ret->is_clip_path = ss->is_clip_path; -return( ret ); -} - -SplineSet *SplineSetsPSApprox(SplineSet *ss) { - SplineSet *head=NULL, *last, *cur; - - while ( ss!=NULL ) { - cur = SSPSApprox(ss); - if ( head==NULL ) - head = cur; - else - last->next = cur; - last = cur; - ss = ss->next; - } -return( head ); -} - -void SCConvertLayerToOrder2(SplineChar *sc,int layer) { - SplineSet *new; - - if ( sc==NULL ) -return; - - new = SplineSetsTTFApprox(sc->layers[layer].splines); - SplinePointListsFree(sc->layers[layer].splines); - sc->layers[layer].splines = new; - - UndoesFree(sc->layers[layer].undoes); - UndoesFree(sc->layers[layer].redoes); - sc->layers[layer].undoes = NULL; - sc->layers[layer].redoes = NULL; - sc->layers[layer].order2 = true; - - MinimumDistancesFree(sc->md); sc->md = NULL; -} - -void SCConvertToOrder2(SplineChar *sc) { - int layer; - - if ( sc==NULL ) -return; - - for ( layer=ly_back; layer<sc->layer_cnt; ++layer ) - SCConvertLayerToOrder2(sc,layer); -} - - -/* ************************************************************************** */ - -void SplineRefigure2(Spline *spline) { - SplinePoint *from = spline->from, *to = spline->to; - Spline1D *xsp = &spline->splines[0], *ysp = &spline->splines[1]; - Spline old; - -#ifdef DEBUG - if ( RealNear(from->me.x,to->me.x) && RealNear(from->me.y,to->me.y)) - IError("Zero length spline created"); -#endif - if ( spline->acceptableextrema ) - old = *spline; - - if ( from->nonextcp || to->noprevcp || - ( from->nextcp.x==from->me.x && from->nextcp.y == from->me.y ) || - ( to->prevcp.x==to->me.x && to->prevcp.y == to->me.y )) { - from->nonextcp = to->noprevcp = true; - from->nextcp = from->me; - to->prevcp = to->me; - } - - if ( from->nonextcp && to->noprevcp ) - /* Ok */; - else if ( from->nonextcp || to->noprevcp || from->nextcp.x!=to->prevcp.x || - from->nextcp.y!=to->prevcp.y ) { - if ( RealNear(from->nextcp.x,to->prevcp.x) && - RealNear(from->nextcp.y,to->prevcp.y)) { - from->nextcp.x = to->prevcp.x = (from->nextcp.x+to->prevcp.x)/2; - from->nextcp.y = to->prevcp.y = (from->nextcp.y+to->prevcp.y)/2; - } else { - IError("Invalid 2nd order spline in SplineRefigure2" ); -#ifndef GWW_TEST - /* I don't want these to go away when I'm debugging. I want to */ - /* know how I got them */ - from->nextcp.x = to->prevcp.x = (from->nextcp.x+to->prevcp.x)/2; - from->nextcp.y = to->prevcp.y = (from->nextcp.y+to->prevcp.y)/2; -#endif - } - } - - xsp->d = from->me.x; ysp->d = from->me.y; - if ( from->nonextcp && to->noprevcp ) { - spline->islinear = true; - xsp->c = to->me.x-from->me.x; - ysp->c = to->me.y-from->me.y; - xsp->a = xsp->b = 0; - ysp->a = ysp->b = 0; - } else { - /* from p. 393 (Operator Details, curveto) Postscript Lang. Ref. Man. (Red book) */ - xsp->c = 2*(from->nextcp.x-from->me.x); - ysp->c = 2*(from->nextcp.y-from->me.y); - xsp->b = to->me.x-from->me.x-xsp->c; - ysp->b = to->me.y-from->me.y-ysp->c; - xsp->a = 0; - ysp->a = 0; - if ( RealNear(xsp->c,0)) xsp->c=0; - if ( RealNear(ysp->c,0)) ysp->c=0; - if ( RealNear(xsp->b,0)) xsp->b=0; - if ( RealNear(ysp->b,0)) ysp->b=0; - spline->islinear = false; - if ( ysp->b==0 && xsp->b==0 ) - spline->islinear = true; /* This seems extremely unlikely... */ - } - if ( isnan(ysp->b) || isnan(xsp->b) ) - IError("NaN value in spline creation"); - LinearApproxFree(spline->approx); - spline->approx = NULL; - spline->knowncurved = false; - spline->knownlinear = spline->islinear; - SplineIsLinear(spline); - spline->isquadratic = !spline->knownlinear; - spline->order2 = true; - - if ( spline->acceptableextrema ) { - /* I don't check "d", because changes to that reflect simple */ - /* translations which will not affect the shape of the spline */ - /* (I don't check "a" because it is always 0 in a quadratic spline) */ - if ( !RealNear(old.splines[0].b,spline->splines[0].b) || - !RealNear(old.splines[0].c,spline->splines[0].c) || - !RealNear(old.splines[1].b,spline->splines[1].b) || - !RealNear(old.splines[1].c,spline->splines[1].c) ) - spline->acceptableextrema = false; - } -} - -void SplineRefigure(Spline *spline) { - if ( spline==NULL ) -return; - if ( spline->order2 ) - SplineRefigure2(spline); - else - SplineRefigure3(spline); -} - -static int IsHV(Spline *spline, int isfrom) { - SplinePoint *sp; - - if ( spline==NULL ) -return( false ); - - if ( !isfrom ) { - sp = spline->to; - if ( sp->noprevcp ) -return( false ); - if ( sp->me.x == sp->prevcp.x ) -return( 2 ); /* Vertical */ - else if ( sp->me.y == sp->prevcp.y ) -return( 1 ); /* Horizontal */ - else -return( 0 ); /* Neither */ - } else { - sp = spline->from; - if ( sp->nonextcp ) -return( false ); - if ( sp->me.x == sp->nextcp.x ) -return( 2 ); /* Vertical */ - else if ( sp->me.y == sp->nextcp.y ) -return( 1 ); /* Horizontal */ - else -return( 0 ); /* Neither */ - } -} - -void SplineRefigureFixup(Spline *spline) { - SplinePoint *from, *to, *prev, *next; - BasePoint foff, toff, unit, new; - double len; - enum pointtype fpt, tpt; - int done = false; - extern int snaptoint; - - if ( !spline->order2 ) { - SplineRefigure3(spline); -return; - } - from = spline->from; to = spline->to; - if ( from->pointtype==pt_hvcurve && to->pointtype==pt_hvcurve ) { - done = true; - if ( !IsHV(from->prev,0) && !IsHV(to->next,1) ) { - if ( to->me.x == from->me.x ) { - from->nextcp.x = to->prevcp.x = to->me.x; - from->nextcp.y = to->prevcp.y = (from->me.y+from->me.y)/2; - } else if ( to->me.y==from->me.y ) { - from->nextcp.y = to->prevcp.y = to->me.y; - from->nextcp.x = to->prevcp.x = (from->me.x+from->me.x)/2; - /* Assume they are drawing clockwise */ - } else if (( to->me.x>from->me.x && to->me.y>=from->me.y ) || - (to->me.x<from->me.x && to->me.y<=from->me.y )) { - from->nextcp.x = to->prevcp.x = from->me.x; - from->nextcp.y = to->prevcp.y = to->me.y; - } else { - from->nextcp.x = to->prevcp.x = to->me.x; - from->nextcp.y = to->prevcp.y = from->me.y; - } - } else if ( !IsHV(to->next,1)) { - if ( IsHV(from->prev,0)==1 ) { - from->nextcp.x = to->prevcp.x = to->me.x; - from->nextcp.y = to->prevcp.y = from->me.y; - } else { - from->nextcp.x = to->prevcp.x = from->me.x; - from->nextcp.y = to->prevcp.y = to->me.y; - } - } else if ( !IsHV(from->prev,0)) { - if ( IsHV(to->next,1)==1 ) { - from->nextcp.x = to->prevcp.x = from->me.x; - from->nextcp.y = to->prevcp.y = to->me.y; - } else { - from->nextcp.x = to->prevcp.x = to->me.x; - from->nextcp.y = to->prevcp.y = from->me.y; - } - } else { - if ( IsHV(from->prev,0)==1 && IsHV(to->next,1)==2 ) { - from->nextcp.x = to->prevcp.x = to->me.x; - from->nextcp.y = to->prevcp.y = from->me.y; - } else if ( IsHV(from->prev,0)==2 && IsHV(to->next,1)==1 ) { - from->nextcp.x = to->prevcp.x = from->me.x; - from->nextcp.y = to->prevcp.y = to->me.y; - } else - done = false; - } - if ( done ) - to->noprevcp = from->nonextcp = false; - } - - if ( !done ) { - unit.x = from->nextcp.x-from->me.x; - unit.y = from->nextcp.y-from->me.y; - len = sqrt(unit.x*unit.x + unit.y*unit.y); - if ( len!=0 ) - unit.x /= len; unit.y /= len; - - if ( (fpt = from->pointtype)==pt_hvcurve ) fpt = pt_curve; - if ( (tpt = to->pointtype)==pt_hvcurve ) tpt = pt_curve; - if ( from->nextcpdef && to->prevcpdef ) switch ( fpt*3+tpt ) { - case pt_corner*3+pt_corner: - case pt_corner*3+pt_tangent: - case pt_tangent*3+pt_corner: - case pt_tangent*3+pt_tangent: - from->nonextcp = to->noprevcp = true; - from->nextcp = from->me; - to->prevcp = to->me; - break; - case pt_curve*3+pt_curve: - case pt_curve*3+pt_corner: - case pt_corner*3+pt_curve: - case pt_tangent*3+pt_curve: - case pt_curve*3+pt_tangent: - if ( from->prev!=NULL && (from->pointtype==pt_tangent || from->pointtype==pt_hvcurve)) { - prev = from->prev->from; - foff.x = prev->me.x; - foff.y = prev->me.y; - } else if ( from->prev!=NULL ) { - prev = from->prev->from; - foff.x = to->me.x-prev->me.x + from->me.x; - foff.y = to->me.y-prev->me.y + from->me.y; - } else { - foff.x = from->me.x + (to->me.x-from->me.x)-(to->me.y-from->me.y); - foff.y = from->me.y + (to->me.x-from->me.x)+(to->me.y-from->me.y); - prev = NULL; - } - if ( to->next!=NULL && (to->pointtype==pt_tangent || to->pointtype==pt_hvcurve)) { - next = to->next->to; - toff.x = next->me.x; - toff.y = next->me.y; - } else if ( to->next!=NULL ) { - next = to->next->to; - toff.x = next->me.x-from->me.x + to->me.x; - toff.y = next->me.y-from->me.y + to->me.y; - } else { - toff.x = to->me.x + (to->me.x-from->me.x)+(to->me.y-from->me.y); - toff.y = to->me.y - (to->me.x-from->me.x)+(to->me.y-from->me.y); - next = NULL; - } - if (( from->pointtype==pt_hvcurve && foff.x!=from->me.x && foff.y!=from->me.y ) || - ( to->pointtype==pt_hvcurve && toff.x!=to->me.x && toff.y!=to->me.y )) { - if ( from->me.x == to->me.x ) { - if ( from->pointtype==pt_hvcurve ) - foff.x = from->me.x; - if ( to->pointtype==pt_hvcurve ) - toff.x = to->me.x; - } else if ( from->me.y == to->me.y ) { - if ( from->pointtype==pt_hvcurve ) - foff.y = from->me.y; - if ( to->pointtype==pt_hvcurve ) - toff.y = to->me.y; - } else { - if ( from->pointtype==pt_hvcurve && foff.x!=from->me.x && foff.y!=from->me.y ) { - if ( fabs(foff.x-from->me.x) > fabs(foff.y-from->me.y) ) - foff.y = from->me.y; - else - foff.x = from->me.x; - } - if ( to->pointtype==pt_hvcurve && toff.x!=to->me.x && toff.y!=to->me.y ) { - if ( from->pointtype==pt_hvcurve ) { - if ( from->me.x==foff.x ) - toff.y = to->me.y; - else - toff.x = to->me.x; - } else if ( fabs(toff.x-to->me.x) > fabs(toff.y-to->me.y) ) - toff.y = to->me.y; - else - toff.x = to->me.x; - } - } - } - if ( IntersectLinesClip(&from->nextcp,&foff,&from->me,&toff,&to->me)) { - from->nonextcp = to->noprevcp = false; - to->prevcp = from->nextcp; - if ( (from->pointtype==pt_curve || from->pointtype==pt_hvcurve ) && - !from->noprevcp && from->prev!=NULL ) { - prev = from->prev->from; - if ( IntersectLinesClip(&from->prevcp,&from->nextcp,&from->me,&prev->nextcp,&prev->me)) { - prev->nextcp = from->prevcp; - SplineRefigure2(from->prev); - } - } - if ( (to->pointtype==pt_curve || to->pointtype==pt_hvcurve) && - !to->nonextcp && to->next!=NULL ) { - next = to->next->to; - if ( IntersectLinesClip(&to->nextcp,&to->prevcp,&to->me,&next->prevcp,&next->me)) { - next->prevcp = to->nextcp; - SplineRefigure(to->next); - } - } - } - break; - } else { - /* Can't set things arbetrarily here, but make sure they are consistant */ - if ( (from->pointtype==pt_curve || from->pointtype==pt_hvcurve ) && - !from->noprevcp && !from->nonextcp ) { - unit.x = from->nextcp.x-from->me.x; - unit.y = from->nextcp.y-from->me.y; - len = sqrt(unit.x*unit.x + unit.y*unit.y); - if ( len!=0 ) { - unit.x /= len; unit.y /= len; - len = sqrt((from->prevcp.x-from->me.x)*(from->prevcp.x-from->me.x) + (from->prevcp.y-from->me.y)*(from->prevcp.y-from->me.y)); - new.x = -len*unit.x + from->me.x; new.y = -len*unit.y + from->me.y; - if ( new.x-from->prevcp.x<-1 || new.x-from->prevcp.x>1 || - new.y-from->prevcp.y<-1 || new.y-from->prevcp.y>1 ) { - prev = NULL; - if ( from->prev!=NULL && (prev = from->prev->from)!=NULL && - IntersectLinesClip(&from->prevcp,&new,&from->me,&prev->nextcp,&prev->me)) { - prev->nextcp = from->prevcp; - SplineRefigure2(from->prev); - } else { - from->prevcp = new; - if ( prev!=NULL ) - prev->nextcp = new; - } - } - } - } else if ( from->pointtype==pt_tangent ) { - if ( from->prev!=NULL ) { - prev = from->prev->from; - if ( !from->noprevcp && !prev->nonextcp && - IntersectLinesClip(&from->prevcp,&to->me,&from->me,&prev->nextcp,&prev->me)) { - prev->nextcp = from->prevcp; - SplineRefigure2(from->prev); - } - if ( !from->nonextcp && !to->noprevcp && - IntersectLinesClip(&from->nextcp,&prev->me,&from->me,&to->prevcp,&to->me)) - to->prevcp = from->nextcp; - } - } - if ( (to->pointtype==pt_curve || to->pointtype==pt_hvcurve ) && - !to->noprevcp && !to->nonextcp ) { - unit.x = to->prevcp.x-to->nextcp.x; - unit.y = to->prevcp.y-to->nextcp.y; - len = sqrt(unit.x*unit.x + unit.y*unit.y); - if ( len!=0 ) { - unit.x /= len; unit.y /= len; - len = sqrt((to->nextcp.x-to->me.x)*(to->nextcp.x-to->me.x) + (to->nextcp.y-to->me.y)*(to->nextcp.y-to->me.y)); - new.x = -len*unit.x + to->me.x; new.y = -len*unit.y + to->me.y; - if ( new.x-to->nextcp.x<-1 || new.x-to->nextcp.x>1 || - new.y-to->nextcp.y<-1 || new.y-to->nextcp.y>1 ) { - if ( to->next!=NULL && (next = to->next->to)!=NULL && - IntersectLinesClip(&to->nextcp,&new,&to->me,&next->prevcp,&next->me)) { - next->prevcp = to->nextcp; - SplineRefigure2(to->next); - } else { - to->nextcp = new; - if ( to->next!=NULL ) { - to->next->to->prevcp = new; - SplineRefigure(to->next); - } - } - } - } - } else if ( to->pointtype==pt_tangent ) { - if ( to->next!=NULL ) { - next = to->next->to; - if ( !to->nonextcp && !next->noprevcp && - IntersectLinesClip(&to->nextcp,&from->me,&to->me,&next->prevcp,&next->me)) { - next->prevcp = to->nextcp; - SplineRefigure2(to->next); - } - if ( !from->nonextcp && !to->noprevcp && - IntersectLinesClip(&from->nextcp,&next->me,&to->me,&from->nextcp,&from->me)) - to->prevcp = from->nextcp; - } - } - } - if ( from->nonextcp && to->noprevcp ) - /* Ok */; - else if ( from->nonextcp || to->noprevcp ) { - from->nonextcp = to->noprevcp = true; - } else if (( from->nextcp.x==from->me.x && from->nextcp.y==from->me.y ) || - ( to->prevcp.x==to->me.x && to->prevcp.y==to->me.y ) ) { - from->nonextcp = to->noprevcp = true; - } else if ( from->nonextcp || to->noprevcp || from->nextcp.x!=to->prevcp.x || - from->nextcp.y!=to->prevcp.y ) { - if ( !IntersectLinesClip(&from->nextcp, - (from->pointtype==pt_tangent && from->prev!=NULL)?&from->prev->from->me:&from->nextcp, &from->me, - (to->pointtype==pt_tangent && to->next!=NULL)?&to->next->to->me:&to->prevcp, &to->me)) { - from->nextcp.x = (from->me.x+to->me.x)/2; - from->nextcp.y = (from->me.y+to->me.y)/2; - } - to->prevcp = from->nextcp; - if (( from->nextcp.x==from->me.x && from->nextcp.y==from->me.y ) || - ( to->prevcp.x==to->me.x && to->prevcp.y==to->me.y ) ) { - from->nonextcp = to->noprevcp = true; - from->nextcp = from->me; - to->prevcp = to->me; - } - } - } - if ( snaptoint && !from->nonextcp ) { - from->nextcp.x = to->prevcp.x = rint(from->nextcp.x); - from->nextcp.y = to->prevcp.y = rint(from->nextcp.y); - } - SplineRefigure2(spline); - - /* Now in order2 splines it is possible to request combinations that are */ - /* mathematically impossible -- two adjacent hv points often don't work */ - if ( to->pointtype==pt_hvcurve && - !(to->prevcp.x == to->me.x && to->prevcp.y != to->me.y ) && - !(to->prevcp.y == to->me.y && to->prevcp.x != to->me.x ) ) - to->pointtype = pt_curve; - if ( from->pointtype==pt_hvcurve && - !(from->nextcp.x == from->me.x && from->nextcp.y != from->me.y ) && - !(from->nextcp.y == from->me.y && from->nextcp.x != from->me.x ) ) - from->pointtype = pt_curve; -} - -Spline *SplineMake2(SplinePoint *from, SplinePoint *to) { - Spline *spline = chunkalloc(sizeof(Spline)); - - spline->from = from; spline->to = to; - from->next = to->prev = spline; - spline->order2 = true; - SplineRefigure2(spline); -return( spline ); -} - -Spline *SplineMake(SplinePoint *from, SplinePoint *to, int order2) { - if ( order2 ) -return( SplineMake2(from,to)); - else -return( SplineMake3(from,to)); -} - -int IntersectLines(BasePoint *inter, - BasePoint *line1_1, BasePoint *line1_2, - BasePoint *line2_1, BasePoint *line2_2) { - double s1, s2; - - if ( line1_1->x == line1_2->x ) { - inter->x = line1_1->x; - if ( line2_1->x == line2_2->x ) { - if ( line2_1->x!=line1_1->x ) -return( false ); /* Parallel vertical lines */ - inter->y = (line1_1->y+line2_1->y)/2; - } else - inter->y = line2_1->y + (inter->x-line2_1->x) * (line2_2->y - line2_1->y)/(line2_2->x - line2_1->x); -return( true ); - } else if ( line2_1->x == line2_2->x ) { - inter->x = line2_1->x; - inter->y = line1_1->y + (inter->x-line1_1->x) * (line1_2->y - line1_1->y)/(line1_2->x - line1_1->x); -return( true ); - } else { - s1 = (line1_2->y - line1_1->y)/(line1_2->x - line1_1->x); - s2 = (line2_2->y - line2_1->y)/(line2_2->x - line2_1->x); - if ( RealNear(s1,s2)) { - if ( !RealNear(line1_1->y + (line2_1->x-line1_1->x) * s1,line2_1->y)) -return( false ); - inter->x = (line1_2->x+line2_2->x)/2; - inter->y = (line1_2->y+line2_2->y)/2; - } else { - inter->x = (s1*line1_1->x - s2*line2_1->x - line1_1->y + line2_1->y)/(s1-s2); - inter->y = line1_1->y + (inter->x-line1_1->x) * s1; - } -return( true ); - } -} - -int IntersectLinesClip(BasePoint *inter, - BasePoint *line1_1, BasePoint *line1_2, - BasePoint *line2_1, BasePoint *line2_2) { - BasePoint old = *inter, unit; - double len, val; - - if ( !IntersectLines(inter,line1_1,line1_2,line2_1,line2_2)) -return( false ); - else { - unit.x = line2_2->x-line1_2->x; - unit.y = line2_2->y-line1_2->y; - len = sqrt(unit.x*unit.x + unit.y*unit.y); - if ( len==0 ) -return( false ); - else { - unit.x /= len; unit.y /= len; - val = unit.x*(inter->x-line1_2->x) + unit.y*(inter->y-line1_2->y); - if ( val<=0 || val>=len ) { - *inter = old; -return( false ); - } - } - } -return( true ); -} - - |