beta-0.89.2

[luatex.git] / source / texk / web2c / luatexdir / luafontloader / fontforge / fontforge / splinestroke.c

/* 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 "splinefont.h"
#include <math.h>

#define PI      3.1415926535897932

typedef struct joininfo {
    SplinePoint *from, *to;
    real tprev;
    real tnext;
    BasePoint inter;
} JointPoint;


static real SplineAngle(Spline *spline,real t) {
    Spline1D *xsp = &spline->splines[0], *ysp = &spline->splines[1];
    real xslope = (3*xsp->a*t+2*xsp->b)*t + xsp->c;
    real yslope = (3*ysp->a*t+2*ysp->b)*t + ysp->c;

    if ( xslope==0 && yslope==0 ) {
        real faket = (t>.5) ? t-.01 : t+.01;
        xslope = (3*xsp->a*faket+2*xsp->b)*faket + xsp->c;
        yslope = (3*ysp->a*faket+2*ysp->b)*faket + ysp->c;
    }
    if ( spline->knownlinear || ( xslope==0 && yslope==0 )) {
        xslope = spline->to->me.x-spline->from->me.x;
        yslope = spline->to->me.y-spline->from->me.y;
    }
return( atan2(yslope,xslope) );
}

static int PenCorner(double lineangle,StrokeInfo *si) {

    if ( ( lineangle>=si->penangle && lineangle<=si->penangle+PI/2 ) ||
         ( lineangle+2*PI>=si->penangle && lineangle+2*PI<=si->penangle+PI/2 ) ||
         ( lineangle-2*PI>=si->penangle && lineangle-2*PI<=si->penangle+PI/2 ) ) {
return( 0 );
    } else if ( ( lineangle>=si->penangle+PI/2 && lineangle<=si->penangle+PI ) ||
                ( lineangle+2*PI>=si->penangle+PI/2 && lineangle+2*PI<=si->penangle+PI ) ||
                ( lineangle-2*PI>=si->penangle+PI/2 && lineangle-2*PI<=si->penangle+PI ) ) {
return( 1 );
    } else if ( ( lineangle>=si->penangle+PI && lineangle<=si->penangle+3*PI/2 ) ||
                ( lineangle+2*PI>=si->penangle+PI && lineangle+2*PI<=si->penangle+3*PI/2 ) ||
                ( lineangle-2*PI>=si->penangle+PI && lineangle-2*PI<=si->penangle+3*PI/2 ) ) {
return( 2 );
    } else {
return( 3 );
    }
}

/* the plus point is where we go when we rotate the line's direction by +90degrees */
/*  and then move radius in that direction. minus is when we rotate -90 and */
/*  then move */        /* counter-clockwise */
static double SplineExpand(Spline *spline,real t,real toff, StrokeInfo *si,
        BasePoint *plus, BasePoint *minus) {
    Spline1D *xsp = &spline->splines[0], *ysp = &spline->splines[1];
    BasePoint base;
    double lineangle, c,s, factor = 1.0;

    if ( si->factor!=NULL )
        factor = (si->factor)(si->data,spline,t);

    base.x = ((xsp->a*t+xsp->b)*t+xsp->c)*t + xsp->d;
    base.y = ((ysp->a*t+ysp->b)*t+ysp->c)*t + ysp->d;

    lineangle = SplineAngle(spline,t+toff);
    if ( si->stroke_type != si_caligraphic ) {
        c = si->radius*factor*cos(lineangle+PI/2);
        s = si->radius*factor*sin(lineangle+PI/2);
        plus->y = base.y+s;
        plus->x = base.x+c;
        minus->y = base.y-s;
        minus->x = base.x-c;
    } else {
        int corner = PenCorner(lineangle,si);
        plus->x = base.x + factor*si->xoff[corner];
        plus->y = base.y + factor*si->yoff[corner];
        corner += 2;
        minus->x = base.x + factor*si->xoff[corner];
        minus->y = base.y + factor*si->yoff[corner];
    }
return( lineangle );
}

static SplinePoint *makequartercircle(real x, real y, real radius,
        real xmul, real ymul,SplinePoint *prev) {
    SplinePoint *here = SplinePointCreate(x,y);

    if ( xmul==0 ) {
        here->nextcp.x = here->prevcp.x = x;
        here->nextcp.y = y + .552*ymul*radius;
        here->prevcp.y = y - .552*ymul*radius;
    } else {
        here->nextcp.y = here->prevcp.y = y;
        here->nextcp.x = x + .552*xmul*radius;
        here->prevcp.x = x - .552*xmul*radius;
    }
    here->nonextcp = here->noprevcp = false;
    if ( prev!=NULL )
        SplineMake3(prev,here);
return( here );
}

static SplinePoint *makeline(SplinePoint *prev, real x, real y) {
    SplinePoint *here = SplinePointCreate(x,y);
    here->pointtype = pt_corner;
    if ( prev!=NULL )
        SplineMake3(prev,here);
return( here );
}

static void SinglePointStroke(SplinePoint *base, StrokeInfo *si, SplinePoint **_plus, SplinePoint **_minus) {
    SplinePoint *plus, *cur;

    /* A single point, is kind of dull.
        For a caligraphic pen, it's just a copy of the pen
        For a linecap of lc_butt it's still a point
        For a linecap of lc_round it's a circle
        For a linecap of lc_square it should be a square...
            but how does one orient that square? probably a circle is best
            here too
    */
    /* We don't have a spline, so don't try guessing factor */
    if ( si->stroke_type == si_caligraphic ) {
        plus = SplinePointCreate(base->me.x+si->xoff[0],base->me.y+si->yoff[0]);
        plus->pointtype = pt_corner;
        cur = makeline(plus,base->me.x+si->xoff[1],base->me.y+si->yoff[1]);
        cur = makeline(cur,base->me.x+si->xoff[2],base->me.y+si->yoff[2]);
        cur = makeline(cur,base->me.x+si->xoff[3],base->me.y+si->yoff[3]);
        SplineMake3(cur,plus);
        *_plus = *_minus = plus;
    } else if ( si->cap!=lc_butt ) {
        plus = makequartercircle(base->me.x-si->radius,base->me.y,si->radius,0,1,NULL);
        cur = makequartercircle(base->me.x,base->me.y+si->radius,si->radius,1,0,plus);
        cur = makequartercircle(base->me.x+si->radius,base->me.y,si->radius,0,-1,cur);
        cur = makequartercircle(base->me.x,base->me.y-si->radius,si->radius,-1,0,cur);
        SplineMake3(cur,plus);
        *_plus = *_minus = plus;
    } else {
        *_plus = *_minus = cur = chunkalloc(sizeof(SplinePoint));
        *cur = *base;
        cur->next = cur->prev = NULL;
        cur->hintmask = NULL;
    }
}

static SplinePoint *StrokeEnd(SplinePoint *base, StrokeInfo *si, int isstart,
        SplinePoint **_to) {
    BasePoint junk;
    SplinePoint *mid1, *mid2, *cur, *from, *to;
    real len;
    real c,s;
    real angle;
    real sign;
    real factor = si->factor==NULL ? 1.0 :
            base->next!=NULL ? (si->factor)(si->data,base->next,0) :
            base->prev!=NULL ? (si->factor)(si->data,base->prev,1) :
            1.0;

    from = chunkalloc(sizeof(SplinePoint));
    to = chunkalloc(sizeof(SplinePoint));
    from->nonextcp = to->nonextcp = from->noprevcp = to->noprevcp = true;
    from->pointtype = pt_corner; to->pointtype = pt_corner;

    if ( isstart )
        angle = SplineExpand(base->next,0,0,si,&from->me,&to->me)+ PI;
    else
        angle = SplineExpand(base->prev,1,0,si,&to->me,&from->me);

    if ( (len = to->me.x-from->me.x)<0 )
        len = -len;
    len += ( to->me.y > from->me.y ) ? (to->me.y - from->me.y) : (from->me.y - to->me.y);

    if ( si->stroke_type == si_caligraphic ) {
        int corner;
        corner = PenCorner(angle,si);
        cur = makeline(from,base->me.x+factor*si->xoff[corner+1],base->me.y+factor*si->yoff[corner+1]);
        SplineMake3(cur,to);
    } else {
        if ( isstart ) {
            SplineIsLinearMake(base->next);
            angle = SplineExpand(base->next,0,0,si,&junk,&junk)+ PI;
            sign = -1;
        } else {
            SplineIsLinearMake(base->prev);
            angle = SplineExpand(base->prev,1,0,si,&junk,&junk);
            sign = -1;
        }
        if ( si->cap==lc_butt ) {
            SplineMake3(from,to);               /* draw a line between */
        } else if ( si->cap==lc_square ) {
            mid1 = SplinePointCreate(
                    from->me.x+ sign*(from->me.y-base->me.y),
                    from->me.y- sign*(from->me.x-base->me.x));
            mid2 = SplinePointCreate(
                    to->me.x+ sign*(from->me.y-base->me.y),
                    to->me.y- sign*(from->me.x-base->me.x));
            mid1->pointtype = pt_corner; mid2->pointtype = pt_corner;
            SplineMake3(from,mid1);
            SplineMake3(mid1,mid2);
            SplineMake3(mid2,to);
        } else if ( si->cap==lc_round ) {
            mid1 = chunkalloc(sizeof(SplinePoint));
            mid1->me.x = base->me.x+ sign*(from->me.y-base->me.y);
            mid1->me.y = base->me.y- sign*(from->me.x-base->me.x);
            mid1->pointtype = pt_curve;
            c = .552*si->radius*factor*cos(angle);
            s = .552*si->radius*factor*sin(angle);
            from->nextcp.x = from->me.x + c;
            from->nextcp.y = from->me.y + s;
            from->nonextcp = false;
            to->prevcp.x = to->me.x +c;
            to->prevcp.y = to->me.y +s;
            to->noprevcp = false;
            mid1->prevcp.x = mid1->me.x - sign*s;
            mid1->prevcp.y = mid1->me.y + sign*c;
            mid1->nextcp.x = mid1->me.x + sign*s;
            mid1->nextcp.y = mid1->me.y - sign*c;
            SplineMake3(from,mid1);
            SplineMake3(mid1,to);
        }
    }
    SplinePointCatagorize(to);
    SplinePointCatagorize(from);
    *_to = to;
return( from );
}

/* Is this the inner intersection or the outer one (the inner one is on both splines) */
/*  the outer one is beyond both */
static int Intersect_Lines(BasePoint *inter,BasePoint *p1,real sx1, real sy1,
        BasePoint *p2, real sx2, real sy2, real radius) {
    real t1/*,t2*/;
    real denom;

    denom = (sx1*sy2-sx2*sy1);
    if ( denom>-.0001 && denom<.0001 ) {
        /* Lines are parallel. Might be coincident, might not */
        t1 = 10000;
    } else {
        /* t2 = (sy1*(p2->x-p1->x)-sx1*(p2->y-p1->y))/denom;*/
        t1 = (sy2*(p2->x-p1->x)-sx2*(p2->y-p1->y))/denom;
    }
    if ( t1>1000 || t1<-1000 ) {
        denom = sqrt(sx1*sx1 + sy1*sy1)/radius;
        if ( denom==0 ) {
            inter->x = (p1->x+p2->x)/2;
            inter->y = (p1->y+p2->y)/2;
        } else {
            inter->x = (p1->x+p2->x)/2 + sx1/denom;
            inter->y = (p1->y+p2->y)/2 + sy1/denom;
        }
return( -1 );
    } else {
        inter->x = p1->x + t1*sx1;
        inter->y = p1->y + t1*sy1;
return( t1<=0 );        /* if t1 < 0 then the intersection point is actually */
                        /*  on both of the spline segments. if it isn't then */
                        /*  it will be on the continuation of the spline */
                        /*  but beyond its endpoint... */
    }
}

static double CircleCpDist(double angle) {
    /* To draw an arc of length angle on a unit circle, the control points */
    /*  should be this far from their base points. Determined empirically, */
    /*  fit by least squares */

    if ( angle<0 ) angle = -angle;
    while ( angle>2*PI ) angle -= 2*PI;
    if ( angle>PI ) angle = 2*PI-angle;
return( ((0.0115445*angle - 0.0111987)*angle + 0.357114)*angle );
}

static SplinePoint *ChordMid(double angle,BasePoint *center,BasePoint *from,
        double *_cpratio) {
    BasePoint off, new;
    double s,c,cpratio;
    SplinePoint *sp;

    if ( angle<0 ) angle = -angle;
    while ( angle>2*PI ) angle -= 2*PI;
    if ( angle>PI ) angle = 2*PI-angle;
    angle /= 2;

    off.x = from->x-center->x;
    off.y = from->y-center->y;
    s = sin(angle); c = cos(angle);
    new.x = c*off.x - s*off.y;
    new.y = s*off.x + c*off.y;
    sp = SplinePointCreate(new.x+center->x,new.y+center->y);

    *_cpratio = cpratio = CircleCpDist(angle);
    new.x *= cpratio; new.y *= cpratio;         /* new is a vector of length radius pointing perp to the direction of the cps */
                /* We need to multiply by cp ratio and rotate 90 degrees */
    sp->prevcp.x = sp->me.x + new.y;
    sp->prevcp.y = sp->me.y - new.x;
    sp->nextcp.x = sp->me.x - new.y;
    sp->nextcp.y = sp->me.y + new.x;
    sp->nonextcp = sp->noprevcp = false;
return( sp );
}

static int IntersectionTooFar(BasePoint *inter,SplinePoint *from,SplinePoint *to,StrokeInfo *si) {
    /* Things look really ugly when we try to miter acute angles -- we get */
    /* huge spikes. So if mitering is going to give bad results, just bevel */
    double len, xoff, yoff;

    xoff = inter->x-from->me.x; yoff = inter->y-from->me.y;
    len = xoff*xoff + yoff*yoff;
    if ( len > (5*si->radius * 5*si->radius) )
return( true );

    xoff = inter->x-to->me.x; yoff = inter->y-to->me.y;
    len = xoff*xoff + yoff*yoff;
    if ( len > (5*si->radius * 5*si->radius) )
return( true );

return( false );
}

static void MakeJoints(SplinePoint *from,SplinePoint *to,StrokeInfo *si,
        BasePoint *inter, BasePoint *center,
        int incr,double pangle, double nangle, real factor) {
    SplinePoint *mid;
    int cstart, cend, i;

    if ( si->stroke_type == si_caligraphic ) {
        cstart = PenCorner(pangle,si);
        cend = PenCorner(nangle,si);
        if ( cstart==cend ) {
            /* same as a miter join */
            mid = SplinePointCreate(inter->x,inter->y);
            mid->pointtype = pt_corner;
            SplineMake3(from,mid);
            SplineMake3(mid,to);
        } else {
            if ( incr<0 ) {
                if ((cstart += 2)>=4 ) cstart -= 4;
                if ((cend += 2)>=4 ) cend -= 4;
                incr = 1;       /* Why??? */
            }
            if ( incr>0 && cstart>cend )
                cend += 4;
            else if ( incr<0 && cstart<cend )
                cstart += 4;
            i = cstart + incr;          /* First one is from */
            mid = from;
            while ( i!=cend ) {
                mid = makeline(mid,center->x+factor*si->xoff[i],center->y+factor*si->yoff[i]);
                i += incr;
            }
            SplineMake3(mid,to);
        }
    } else if ( si->join == lj_miter && !IntersectionTooFar(inter,from,to,si)) {
        mid = SplinePointCreate(inter->x,inter->y);
        mid->pointtype = pt_corner;
        SplineMake3(from,mid);
        SplineMake3(mid,to);
        if ( from->ptindex == to->ptindex )
            mid->ptindex = from->ptindex;
    } else if ( si->join==lj_bevel ) {
        SplineMake3(from,to);
    } else {
        double cplen = CircleCpDist(nangle-pangle);
        mid = NULL;
        if ( cplen>.6 ) {
            /* If angle of the arc is more than about 90 degrees a cubic */
            /*  spline is noticeably different from a circle's arc */
            /* So add an extra point to help things out */
            mid = ChordMid(nangle-pangle,center,&from->me,&cplen);
        }
        cplen *= si->radius*factor;
        from->pointtype = to->pointtype = pt_curve;
        from->nextcp.x = from->me.x-cplen*cos(nangle);
        from->nextcp.y = from->me.y-cplen*sin(nangle);
        to->prevcp.x = to->me.x+cplen*cos(pangle);
        to->prevcp.y = to->me.y+cplen*sin(pangle);
        from->nonextcp = false; to->noprevcp = false;
        if ( mid==NULL )
            SplineMake3(from,to);
        else {
            SplineMake3(from,mid);
            SplineMake3(mid,to);
        }
    }
}

static int OnEdge(BasePoint *plus,BasePoint *minus,Spline *sp, double t,
        double heret, Spline *hsp,
        StrokeInfo *si, double *_ppt, double *_pmt, double *_mpt, double *_mmt) {
    double rsq = si->radius*si->radius;
    double tt, xdiff, ydiff, loopdiff;
    double pptval= -1, pmtval= -1, mptval= -1, mmtval = -1;
    BasePoint here, test;

    here.x = ((hsp->splines[0].a*heret+hsp->splines[0].b)*heret+hsp->splines[0].c)*heret+hsp->splines[0].d;
    here.y = ((hsp->splines[1].a*heret+hsp->splines[1].b)*heret+hsp->splines[1].c)*heret+hsp->splines[1].d;

    if ( (xdiff = sp->to->me.x-sp->from->me.x)<0 ) xdiff = -xdiff;
    if ( (ydiff = sp->to->me.y-sp->from->me.y)<0 ) ydiff = -ydiff;
    loopdiff = (xdiff+ydiff==0) ? 2 : 1.0/(4*(xdiff+ydiff)/si->radius);

    if ( _ppt!=NULL ) {
        for ( tt = t+loopdiff; tt<=1 ; tt += loopdiff ) {
            test.x = ((sp->splines[0].a*tt+sp->splines[0].b)*tt+sp->splines[0].c)*tt+sp->splines[0].d;
            test.y = ((sp->splines[1].a*tt+sp->splines[1].b)*tt+sp->splines[1].c)*tt+sp->splines[1].d;
            if ( (test.x-here.x)*(test.x-here.x)+(test.y-here.y)*(test.y-here.y)> 2*rsq )
        break;
            if ( (plus->x-test.x)*(plus->x-test.x)+(plus->y-test.y)*(plus->y-test.y)<= rsq )
                pptval = tt;
            if ( (minus->x-test.x)*(minus->x-test.x)+(minus->y-test.y)*(minus->y-test.y)<= rsq )
                pmtval = tt;
        }
        *_ppt = pptval; *_pmt = pmtval;
    }

    if ( _mmt!=NULL ) {
        for ( tt = t-loopdiff; tt>=0 ; tt -= loopdiff ) {
            test.x = ((sp->splines[0].a*tt+sp->splines[0].b)*tt+sp->splines[0].c)*tt+sp->splines[0].d;
            test.y = ((sp->splines[1].a*tt+sp->splines[1].b)*tt+sp->splines[1].c)*tt+sp->splines[1].d;
            if ( (test.x-here.x)*(test.x-here.x)+(test.y-here.y)*(test.y-here.y)> 2*rsq )
        break;
            if ( (plus->x-test.x)*(plus->x-test.x)+(plus->y-test.y)*(plus->y-test.y)< rsq )
                mptval = tt;
            if ( (minus->x-test.x)*(minus->x-test.x)+(minus->y-test.y)*(minus->y-test.y)< rsq )
                mmtval = tt;
        }
        *_mmt = mmtval; *_mpt = mptval;
    }

return( pptval!=-1 || mmtval!=-1 || pmtval!=-1 || mptval==-1 );
}

#define BasePtDistance(pt1, pt2)  sqrt(((pt1)->x-(pt2)->x)*((pt1)->x-(pt2)->x) + ((pt1)->y-(pt2)->y)*((pt1)->y-(pt2)->y))


static SplinePoint *MergeSplinePoint(SplinePoint *sp1,SplinePoint *sp2) {
    /* sp1 and sp2 should be close together, use their average for the */
    /*  new position, get rid of one, and add its spline to the other */
    /* sp1->next==NULL, sp2->prev==NULL */
    double offx, offy;

    offx = (sp1->me.x-sp2->me.x)/2;
    offy = (sp1->me.y-sp2->me.y)/2;
    sp1->me.x -= offx; sp1->prevcp.x -= offx;
    sp1->me.y -= offy; sp1->prevcp.y -= offy;
    sp1->nextcp.x = sp2->nextcp.x + offx;
    sp1->nextcp.y = sp2->nextcp.y + offy;
    sp1->nonextcp = sp2->nonextcp;
    sp1->next = sp2->next;
    SplinePointFree(sp2);
    if ( sp1->next!=NULL )
        sp1->next->from = sp1;
    SplinePointCatagorize(sp1);
    if ( sp1->prev!=NULL )
        SplineRefigure(sp1->prev);
    if ( sp1->next!=NULL )
        SplineRefigure(sp1->next);
return( sp1 );
}

static void MSP(SplinePoint *sp1,SplinePoint **sp2, SplinePoint **sp2alt) {
    int same2 = *sp2==*sp2alt;

    *sp2 = MergeSplinePoint(sp1,*sp2);
    if ( same2 )
        *sp2alt = *sp2;
}

static SplinePoint *SplineMaybeBisect(Spline *s,double t) {
    /* Things get very confused if I have a splineset with just a single point */
    SplinePoint *temp, *sp;

    if ( t<.0001 ) {
        temp = chunkalloc(sizeof(SplinePoint));
        sp = s->from;
        *temp = *sp;
        temp->hintmask = NULL;
        temp->next->from = temp;
        sp->next = NULL;
        sp->nextcp = sp->me;
        sp->nonextcp = true;
        temp->prevcp = temp->me;
        temp->noprevcp = true;
        SplineMake3(sp,temp);
return( temp );
    } else if ( t>.9999 ) {
        temp = chunkalloc(sizeof(SplinePoint));
        sp = s->to;
        *temp = *sp;
        temp->hintmask = NULL;
        temp->prev->to = temp;
        sp->prev = NULL;
        sp->prevcp = sp->me;
        sp->noprevcp = true;
        temp->nextcp = temp->me;
        temp->nonextcp = true;
        SplineMake3(temp,sp);
return( temp );
    }

return( SplineBisect(s,t));
}

static void SplineFreeBetween(SplinePoint *from,SplinePoint *to,int freefrom,int freeto) {
    Spline *s;

    if ( from==to ) {
        if ( freefrom && freeto )
            SplinePointFree(from);
return;
    }

    while ( from!=to && from!=NULL ) {
        s = from->next;
        if ( freefrom )
            SplinePointFree(from);
        else
            from->next = NULL;
        if ( s==NULL )
return;
        freefrom = true;
        from = s->to;
        SplineFree(s);
    }
    if ( freeto )
        SplinePointFree(to);
    else
        to->prev = NULL;
}

static void SplineFreeForeward(SplinePoint *from) {
    Spline *s;

    while ( from!=NULL ) {
        s = from->next;
        SplinePointFree(from);
        if ( s==NULL )
return;
        from = s->to;
        SplineFree(s);
    }
}

static void SplineFreeBackward(SplinePoint *to) {
    Spline *s;

    while ( to!=NULL ) {
        s = to->prev;
        SplinePointFree(to);
        if ( s==NULL )
return;
        to = s->from;
        SplineFree(s);
    }
}

static SplinePoint *SplineCopyAfter(SplinePoint *from,SplinePoint **end) {
    SplinePoint *head, *last;

    last = head = chunkalloc(sizeof(SplinePoint));
    *head = *from;
    head->hintmask = NULL;
    head->prev = NULL;
    while ( from->next!=NULL ) {
        last->next = chunkalloc(sizeof(Spline));
        *last->next = *from->next;
        last->next->from = last;
        last->next->to = chunkalloc(sizeof(SplinePoint));
        *last->next->to = *from->next->to;
        last->next->to->hintmask = NULL;
        last->next->to->prev = last->next;
        last = last->next->to;
        from = from->next->to;
    }
    *end = last;
return( head );
}

static SplinePoint *SplineCopyBefore(SplinePoint *to,SplinePoint **end) {
    SplinePoint *head, *last;

    last = head = chunkalloc(sizeof(SplinePoint));
    *head = *to;
    head->hintmask = NULL;
    head->next = NULL;
    while ( to->prev!=NULL ) {
        last->prev = chunkalloc(sizeof(Spline));
        *last->prev = *to->prev;
        last->prev->to = last;
        last->prev->from = chunkalloc(sizeof(SplinePoint));
        *last->prev->from = *to->prev->from;
        last->prev->from->hintmask = NULL;
        last->prev->from->next = last->prev;
        last = last->prev->from;
        to = to->prev->from;
    }
    *end = last;
return( head );
}

static SplinePoint *Intersect_Splines(SplinePoint *from,SplinePoint *to,
        SplinePoint **ret) {
    Spline *test1, *test2;
    BasePoint pts[9];
    extended t1s[9], t2s[9];

    for ( test1=from->next; test1!=NULL; test1=test1->to->next ) {
        for ( test2=to->prev; test2!=NULL; test2=test2->from->prev ) {
            if ( SplinesIntersect(test1,test2,pts,t1s,t2s)>0 ) {
                *ret = SplineMaybeBisect(test2,t2s[0]);
return( SplineMaybeBisect(test1,t1s[0]));
            }
        }
    }
    *ret = NULL;
return( NULL );
}

struct strokedspline {
    Spline *s;
    SplinePoint *plusfrom, *plusto, *origplusfrom;
    SplinePoint *minusfrom, *minusto, *origminusto;
    int8 plusskip, minusskip;           /* If this spline is so small that it is totally within the region stroked by an adjacent spline */
    int8 pinnerto, minnerto;            /* to and from as defined on original spline s */
    BasePoint minterto, pinterto;
    double nangle, pangle;
    struct strokedspline *next, *prev;
};

static void StrokeEndComplete(struct strokedspline *cur,StrokeInfo *si,int isstart) {
    SplinePoint *edgestart, *edgeend, *curat, *edgeat;
    struct strokedspline *lastp, *lastm;

    if ( isstart ) {
        edgestart = StrokeEnd(cur->s->from,si,true,&edgeend);
        for ( lastp=cur; lastp!=NULL && lastp->plusskip ; lastp=lastp->next );
        for ( lastm=cur; lastm!=NULL && lastm->minusskip ; lastm=lastm->next );
        if ( lastm==cur )
            MSP(edgeend,&cur->minusfrom,&cur->minusto);
        else {
            curat = Intersect_Splines(lastm->minusfrom,edgeend,&edgeat);
            if ( curat!=NULL ) {
                SplineFreeBetween(lastm->minusfrom,curat,true,false);
                SplineFreeBetween(edgeat,edgeend,false,true);
            } else
                MSP(edgeend,&lastm->minusfrom,&lastm->minusto);
        }
        if ( lastp==cur )
            MergeSplinePoint(cur->plusto,edgestart);
        else {
            edgeat = Intersect_Splines(edgestart,lastp->plusto,&curat);
            if ( curat!=NULL ) {
                SplineFreeBetween(curat,lastp->plusto,false,true);
                SplineFreeBetween(edgestart,edgeat,true,false);
            } else
                MergeSplinePoint(lastp->plusto,edgestart);
        }
    } else {
        edgestart = StrokeEnd(cur->s->to,si,false,&edgeend);
        for ( lastp=cur; lastp!=NULL && lastp->plusskip ; lastp=lastp->prev );
        for ( lastm=cur; lastm!=NULL && lastm->minusskip ; lastm=lastm->prev );
        if ( lastp==cur )
            MSP(edgeend,&cur->plusfrom,&cur->plusto);
        else {
            curat = Intersect_Splines(lastp->plusfrom,edgeend,&edgeat);
            if ( curat!=NULL ) {
                SplineFreeBetween(lastp->plusfrom,curat,true,false);
                lastp->plusfrom = curat;
                SplineFreeBetween(edgeat,edgeend,false,true);
                lastp->plusfrom = MergeSplinePoint(edgeat,curat);
            } else
                MSP(edgeend,&lastp->plusfrom,&lastp->plusto);
        }
        if ( lastm==cur )
            MergeSplinePoint(cur->minusto,edgestart);
        else {
            edgeat = Intersect_Splines(edgestart,lastm->minusto,&curat);
            if ( curat!=NULL ) {
                SplineFreeBetween(curat,lastm->minusto,false,true);
                lastm->minusto = curat;
                SplineFreeBetween(edgestart,edgeat,true,false);
                MergeSplinePoint(lastm->minusto,edgeat);
            } else
                MergeSplinePoint(lastm->minusto,edgestart);
        }
    }
}

static void StrokedSplineFree(struct strokedspline *head) {
    struct strokedspline *next, *cur=head;

    while ( cur!=NULL ) {
        next = cur->next;
        chunkfree(cur,sizeof(*cur));
        cur = next;
        if ( cur==head )
    break;
    }
}

static void FreeOrigStuff(struct strokedspline *before) {

    if ( before->origminusto!=NULL )
        SplineFreeBackward(before->origminusto);
    before->origminusto = NULL;
    if ( before->origplusfrom!=NULL )
        SplineFreeForeward(before->origplusfrom);
    before->origplusfrom = NULL;
}

static void SplineMakeRound(SplinePoint *from,SplinePoint *to, real radius) {
    /* I believe this only gets called when we have a line join where the */
    /*  contour makes a U-Turn (opposite of being colinear) */
    BasePoint dir;
    SplinePoint *center;

    dir.x = (to->me.y-from->me.y)/2;
    dir.y = -(to->me.x-from->me.x)/2;
    center = SplinePointCreate((to->me.x+from->me.x)/2+dir.x,
            (to->me.y+from->me.y)/2+dir.y);
    from->nextcp.x = from->me.x + .552*dir.x;
    from->nextcp.y = from->me.y + .552*dir.y;
    to->prevcp.x = to->me.x + .552*dir.x;
    to->prevcp.y = to->me.y + .552*dir.y;
    from->nonextcp = to->noprevcp = false;
    center->prevcp.x = center->me.x + .552*dir.y;
    center->nextcp.x = center->me.x - .552*dir.y;
    center->prevcp.y = center->me.y - .552*dir.x;
    center->nextcp.y = center->me.y + .552*dir.x;
    center->nonextcp = center->noprevcp = false;
    SplineMake3(from,center);
    SplineMake3(center,to);
}

static int DoIntersect_Splines(struct strokedspline *before,
        struct strokedspline *after, int doplus,StrokeInfo *si,SplineChar *sc,
        int force_connect ) {
    SplinePoint *beforeat, *afterat;
    int ret = true;
    int toobig = false;

    if ( doplus ) {
        beforeat = Intersect_Splines(before->plusfrom,after->plusto,&afterat);
        if ( beforeat!=NULL ) {
            after->origplusfrom = after->plusfrom;
            after->plusto = SplineCopyBefore(afterat,&after->plusfrom);
            SplineFreeBetween(before->plusfrom,beforeat,true/*free before->plusfrom*/,false/* keep beforeat */);
            before->plusfrom = beforeat;
        } else if ( before->origplusfrom!=NULL &&
                (beforeat = Intersect_Splines(before->origplusfrom,after->plusto,&afterat))!=NULL ) {
            toobig = true;
            after->origplusfrom = after->plusfrom;
            after->plusto = SplineCopyBefore(afterat,&after->plusfrom);
            SplineFreeBetween(before->plusfrom,before->plusto,true/*free plusfrom*/,false);
            before->plusfrom = SplinePointCreate(afterat->me.x,afterat->me.y);
            before->plusfrom->nextcp = before->plusfrom->me;
            before->plusfrom->nonextcp = true;
            SplineMake3(before->plusfrom,before->plusto);       /* This line goes backwards */
#if 0           /* This introduces lots of bugs, it gets invoked when it */
                /*  shouldn't, and I can't figure out how to distinguish */
        } else if ( EntirelyWithin(before->plusfrom,after->s,true,si->radius) ) {
            /* the splines at before are all within radius units of the original */
            /*  after spline. This means that they will make no contribution */
            /*  to the outline. */
            if ( before->prev!=NULL && before->prev!=after )
                ret = DoIntersect_Splines(before->prev,after,doplus,si,sc);
            before->plusskip = true;
            toobig = ret;
        } else if ( EntirelyWithin(after->plusto,before->s,false,si->radius) ) {
            /* the splines at after are entirely within radius units of the original */
            if ( after->next!=NULL && after->next!=before )
                ret = DoIntersect_Splines(before,after->next,doplus,si,sc);
            after->plusskip = true;
            toobig = ret;
#endif
        } else {
            /* No intersection everything can stay as it is */
            if ( force_connect && BasePtDistance(&after->plusto->me,&before->plusfrom->me)>3 ) {
                beforeat = SplinePointCreate(after->plusto->me.x,after->plusto->me.y);
                if ( si->join==lj_round )
                    SplineMakeRound(beforeat,before->plusfrom,si->radius);
                else
                    SplineMake3(beforeat,before->plusfrom);
                before->plusfrom = beforeat;
                toobig = true;
            }
            ret = false;
        }
    } else {
        afterat = Intersect_Splines(after->minusfrom,before->minusto,&beforeat);
        if ( afterat!=NULL ) {
            after->origminusto = after->minusto;
            after->minusfrom = SplineCopyAfter(afterat,&after->minusto);
            SplineFreeBetween(beforeat,before->minusto,false/*keep beforeat*/,true);
            before->minusto = beforeat;
        } else if ( before->origminusto!=NULL &&
                (afterat = Intersect_Splines(after->minusfrom,before->origminusto,&beforeat))!=NULL ) {
            toobig = true;
            after->origminusto = after->minusto;
            after->minusfrom = SplineCopyAfter(afterat,&after->minusto);
            SplineFreeBetween(before->minusfrom,before->minusto,false/*keep minusfrom*/,true);
            before->minusto = SplinePointCreate(afterat->me.x,afterat->me.y);
            before->minusto->ptindex = afterat->ptindex;
            before->minusfrom->nextcp = before->minusfrom->me;
            before->minusfrom->nonextcp = true;
            SplineMake3(before->minusfrom,before->minusto);     /* This line goes backwards */
#if 0           /* This introduces lots of bugs, it gets invoked when it */
                /*  shouldn't, and I can't figure out how to distinguish */
        } else if ( EntirelyWithin(before->minusto,after->s,false,si->radius) ) {
            /* the splines at before are all within radius units of the original */
            /*  after spline. This means that they will make no contribution */
            /*  to the outline. */
            ret = false;
            if ( before->prev!=NULL && before->prev!=after && before->prev!=after->next )
                ret = DoIntersect_Splines(before->prev,after,doplus,si,sc);
            before->minusskip = true;
            toobig = ret;
        } else if ( EntirelyWithin(after->minusfrom,before->s,true,si->radius) ) {
            /* the splines at after are entirely within radius units of the original */
            ret = false;
            if ( after->next!=NULL && after->next!=before && before->prev!=after->next )
                ret = DoIntersect_Splines(before,after->next,doplus,si,sc);
            after->minusskip = true;
            toobig = ret;
#endif
        } else {
            /* No intersection everything can stay as it is */
            if ( force_connect && BasePtDistance(&after->minusfrom->me,&before->minusto->me)>3 ) {
                beforeat = SplinePointCreate(after->minusfrom->me.x,after->minusfrom->me.y);
                beforeat->ptindex = after->minusfrom->ptindex;
                if ( si->join==lj_round )
                    SplineMakeRound(before->minusto,beforeat,si->radius);
                else
                    SplineMake3(before->minusto,beforeat);
                before->minusto = beforeat;
                toobig = true;
            }
            ret = false;
        }
    }

    if ( toobig ) {
        si->gottoobig = si->gottoobiglocal = true;
        if ( !si->toobigwarn ) {
            si->toobigwarn = true;
            ff_post_error( _("Bad Stroke"), _("The stroke width is so big that the generated path\nmay intersect itself in %.100s"),
                    sc==NULL?"<nameless char>": sc->name );
        }
    }
return( ret );
}

/* Plus joins run from prev to next, minus joins run from next to prev */
/* This makes plus joins clockwise and minus joins counter */
static void StrokeJoint(SplinePoint *base,StrokeInfo *si,
        struct strokedspline *before,struct strokedspline *after,
        SplineChar *sc) {
    BasePoint nplus, nminus, pplus,pminus;
    double nangle, pangle;
    int pinner, minner;
#if 0
    double pt, mt;
    double tt, xdiff, ydiff;
#endif

    before->pangle = pangle = SplineExpand(base->prev,1,0,si,&pplus,&pminus);
    before->nangle = nangle = SplineExpand(base->next,0,0,si,&nplus,&nminus);

    if ( RealWithin(pangle,nangle,.1) || RealWithin(pangle+2*PI,nangle,.1) ||
            RealWithin(pangle,nangle+2*PI,.1)) {
        /* If the two splines are tangent at the base, then everything is */
        /*  simple, there is no join, things match up perfectly */
        /* Um. No. If there is a sharp bend or a corner nearby then it may */
        /*  have the same effect as a corner, in extreme cases the entire */
        /*  spline may be eaten up */
        /* Actually, that's probably done best in Remove Overlap. If we try */
        /*  to do it here, we unlease lots of potentials for bugs in other */
        /*  cases */

#if 0
        if ( (xdiff = base->me.x-base->prev->from->me.x)<0 ) xdiff = -xdiff;
        if ( (ydiff = base->me.y-base->prev->from->me.y)<0 ) ydiff = -ydiff;
        if ( xdiff+ydiff==0 ) xdiff = 1;
        tt = si->radius/(2*(xdiff+ydiff));
        if ( tt>.2 ) tt = .2;
        OnEdge(&pplus,&pminus,base->next,0,1.0-tt,base->prev,
                si,&pt,&mt,NULL,NULL);
        if ( pt!=-1 )
            DoIntersect_Splines(before,after,true,si,sc,true);
        else {
            if ( (xdiff = base->me.x-base->next->to->me.x)<0 ) xdiff = -xdiff;
            if ( (ydiff = base->me.y-base->next->to->me.y)<0 ) ydiff = -ydiff;
            tt = si->radius/(2*(xdiff+ydiff));
            if ( tt>.2 ) tt = .2;
            OnEdge(&nplus,&nminus,base->prev,1.,tt,base->next,
                    si,NULL,NULL,&pt,&mt);
            if ( mt!=-1 )
                DoIntersect_Splines(before,after,false,si,sc,true);
        }
#endif
        before->pinnerto = before->minnerto = -1;
    } else {
        pinner = Intersect_Lines(&before->pinterto,&pplus,
                 3*base->prev->splines[0].a+2*base->prev->splines[0].b+base->prev->splines[0].c,
                 3*base->prev->splines[1].a+2*base->prev->splines[1].b+base->prev->splines[1].c,
                &nplus,
                 base->next->splines[0].c,
                 base->next->splines[1].c,si->radius);
        minner = Intersect_Lines(&before->minterto,&pminus,
                 3*base->prev->splines[0].a+2*base->prev->splines[0].b+base->prev->splines[0].c,
                 3*base->prev->splines[1].a+2*base->prev->splines[1].b+base->prev->splines[1].c,
                &nminus,
                 base->next->splines[0].c,
                 base->next->splines[1].c,si->radius);
        if ( pinner==-1 && minner!=-1 )
            pinner = !minner;
        before->pinnerto = pinner; before->minnerto = (pinner!=-1?!pinner:-1);
        if ( pinner==1 ) {
            DoIntersect_Splines(before,after,true,si,sc,true);
        } else if ( pinner==0 ) {
            DoIntersect_Splines(before,after,false,si,sc,true);
        } else {        /* splines are parallel, but moving in same dir */
            if ( DoIntersect_Splines(before,after,true,si,sc,false)) {
                before->pinnerto = 1;
                before->minnerto = 0;
            } else {
                if ( DoIntersect_Splines(before,after,false,si,sc,true)) {
                    before->pinnerto = 0;
                    before->minnerto = 1;
                } else
                    DoIntersect_Splines(before,after,true,si,sc,true);
            }
        }
    }
}

static int SplineSolveForPen(Spline *s,StrokeInfo *si,double *ts,int *pinners,
        double tstart,double tend) {
    /* Find all the places at which the spline has the same slope as one of the */
    /*  edges of the pen. There can be at most 8 (we get four quadratics) */
    double a, b, c, sq, t1, t2;
    int i, cnt=0, j;
    Spline1D *xsp = &s->splines[0], *ysp = &s->splines[1];
    BasePoint pp, pm, np, nm, testp, testm;

    ts[cnt++] = tstart;
    for ( i=0; i<2; ++i ) {
        if ( i==0 ) {
            a = 3*(ysp->a*si->c-xsp->a*si->s);
            b = 2*(ysp->b*si->c-xsp->b*si->s);
            c = ysp->c*si->c-xsp->c*si->s;
        } else if ( i==1 ) {
            a = 3*(-ysp->a*si->c-xsp->a*si->s);
            b = 2*(-ysp->b*si->c-xsp->b*si->s);
            c = -ysp->c*si->c-xsp->c*si->s;
#if 0   /* These two are just the negatives of the first two and as such have the same roots */
        } else if ( i==2 ) {
            a = 3*(-ysp->a*si->c+xsp->a*si->s);
            b = 2*(-ysp->b*si->c+xsp->b*si->s);
            c = -ysp->c*si->c+xsp->c*si->s;
        } else {
            a = 3*(ysp->a*si->c+xsp->a*si->s);
            b = 2*(ysp->b*si->c+xsp->b*si->s);
            c = ysp->c*si->c+xsp->c*si->s;
#endif
        }
        sq = b*b-4*a*c;
        if ( sq==0 ) {
            t1 = -b/(2*a);
            t2 = -1;
        } else if ( sq>0 ) {
            sq = sqrt(sq);
            t1 = (-b+sq)/(2*a);
            t2 = (-b-sq)/(2*a);
        } else
            t1 = t2 = -1;
        if ( t1>tstart && t1<tend )
            ts[cnt++] = t1;
        if ( t2>tstart && t2<tend )
            ts[cnt++] = t2;
    }
    ts[cnt++] = tend;
    if ( cnt<=2 )
return(cnt);
    /* Order them */
    for ( i=1; i<cnt-1; ++i ) for ( j=i+1; j<cnt; ++j )
        if ( ts[i]>ts[j] ) {
            double temp = ts[i];
            ts[i] = ts[j];
            ts[j] = temp;
        }
    /* Figure which side is inner */
    for ( i=1; i<cnt-1; ++i ) {
        SplineExpand(s,ts[i],-(ts[i]-ts[i-1])/20.,si,&pp,&pm);
        SplineExpand(s,ts[i],(ts[i+1]-ts[i])/20.,si,&np,&nm);
        SplineExpand(s,ts[i]+(ts[i+1]-ts[i])/20.,0,si,&testp,&testm);
        pinners[i] = ( (testp.x-np.x)*(pp.x-np.x)+(testp.y-np.y)*(pp.y-np.y)> 0 );
    }
return( cnt );
}


static void SplineSetFixCPs(SplineSet *ss) {
    SplinePoint *sp;

    for ( sp=ss->first; ; ) {
        SPWeightedAverageCps(sp);
        if ( sp->next==NULL )
    break;
        sp = sp->next->to;
        if ( sp==ss->first )
    break;
    }
    SPLCatagorizePoints(ss);
}

static SplinePoint *SPNew(SplinePoint *base,BasePoint *pos,BasePoint *cp,int isnext) {
    SplinePoint *sp = SplinePointCreate(pos->x,pos->y);

    sp->pointtype = base->pointtype;
    /* Embolden wants these three preserved */
    sp->ptindex = base->ptindex;
    sp->ttfindex = base->ttfindex;
    sp->nextcpindex = base->nextcpindex;
    if ( isnext ) {
        sp->nextcp.x = pos->x + (cp->x-base->me.x);
        sp->nextcp.y = pos->y + (cp->y-base->me.y);
        sp->nonextcp = (sp->nextcp.x==pos->x) && (sp->nextcp.y==pos->y);
    } else {
        sp->prevcp.x = pos->x + (cp->x-base->me.x);
        sp->prevcp.y = pos->y + (cp->y-base->me.y);
        sp->noprevcp = (sp->prevcp.x==pos->x) && (sp->prevcp.y==pos->y);
    }
return( sp );
}

static void NormalizeT(TPoint *mids,int cnt,double tbase,double tend) {
    int i;

    for ( i=0; i<cnt; ++i )
        mids[i].t = (mids[i].t - tbase)/(tend - tbase);
}

static void SPFigureCP(SplinePoint *sp,double t,Spline *spline,int isnext) {
    Spline temp;
    double tn;
    Spline1D *s1;
    BasePoint off;

    s1 = &spline->splines[0];
    off.x = sp->me.x - ( ((s1->a*t+s1->b)*t+s1->c)*t+s1->d );
    s1 = &spline->splines[1];
    off.y = sp->me.y - ( ((s1->a*t+s1->b)*t+s1->c)*t+s1->d );

    if ( isnext ) {
        double s = (1.0-t);
        /* We want to renormalize the spline so that it runs from [t,1] and */
        /*  then figure what the control point at t should be */
        s1 = &spline->splines[0];
        temp.splines[0].d = s1->d + t*(s1->c + t*(s1->b + t*s1->a));
        temp.splines[0].c = s*(s1->c + t*(2*s1->b + 3*s1->a*t));
        temp.splines[0].b = s*s*(s1->b+3*s1->a*t);
#if 0
        temp.splines[0].a = s*s*s*s1->a;
#endif
        s1 = &spline->splines[1];
        temp.splines[1].d = s1->d + t*(s1->c + t*(s1->b + t*s1->a));
        temp.splines[1].c = s*(s1->c + t*(2*s1->b + 3*s1->a*t));
        temp.splines[1].b = s*s*(s1->b+3*s1->a*t);
#if 0
        temp.splines[1].a = s*s*s*s1->a;
#endif
        if ( spline->order2 ) {
            sp->nextcp.x = temp.splines[0].d + temp.splines[0].c/2 + off.x;
            sp->nextcp.y = temp.splines[1].d + temp.splines[1].c/2 + off.y;
        } else {
            sp->nextcp.x = temp.splines[0].d + temp.splines[0].c/3 + off.x;
            sp->nextcp.y = temp.splines[1].d + temp.splines[1].c/3 + off.y;
        }
        sp->nonextcp = false;
    } else {
        /* We want to renormalize the spline so that it runs from [0,t] and */
        /*  then figure what the control point at t should be */
        temp = *spline;
        temp.splines[0].c *= t;         temp.splines[1].c *= t;
        tn = t*t;
        temp.splines[0].b *= tn;        temp.splines[1].b *= tn;
#if 0
        tn *= t;
        temp.splines[0].a *= tn;        temp.splines[1].a *= tn;
#endif
        if ( spline->order2 ) {
            sp->prevcp.x = temp.splines[0].d + temp.splines[0].c/2 + off.x;
            sp->prevcp.y = temp.splines[1].d + temp.splines[1].c/2 + off.y;
        } else {
            sp->prevcp.x = temp.splines[0].d + (2*temp.splines[0].c+temp.splines[0].b)/3 + off.x;
            sp->prevcp.y = temp.splines[1].d + (2*temp.splines[1].c+temp.splines[1].b)/3 + off.y;
        }
        sp->noprevcp = false;
    }
}

static void SPFigurePlusCP(SplinePoint *sp,double t,Spline *spline,int isnext) {
    SplinePoint dummy;

    /* Plus splines run in the oposite direction */
    dummy = *sp;
    SPFigureCP(&dummy,t,spline,!isnext);
    if ( isnext ) {
        sp->nextcp = dummy.prevcp;
        sp->nonextcp = false;
    } else {
        sp->prevcp = dummy.nextcp;
        sp->noprevcp = false;
    }
}

static int Overlaps(TPoint *expanded,TPoint *inner,double rsq) {
    double len;
    BasePoint dir;
    
    dir.x = (expanded->x-inner->x); dir.y = (expanded->y-inner->y);
    len = (dir.x*dir.x) + (dir.y*dir.y);
    if ( len>=rsq )
return( false );
    len = sqrt(rsq/len);
    expanded->x = inner->x + len*dir.x;
    expanded->y = inner->y + len*dir.y;
return( true );
}

#define Approx  10

static struct strokedspline *_SplineSetApprox(SplineSet *spl,StrokeInfo *si,SplineChar *sc) {
    struct strokedspline *head=NULL, *last=NULL, *cur;
    int max=Approx;
    TPoint *pmids=galloc(max*sizeof(TPoint)),
            *mmids=galloc(max*sizeof(TPoint)),
            *mids=galloc(max*sizeof(TPoint));
    uint8 *knots=galloc(max);
    BasePoint pto, mto, pfrom, mfrom;
    double approx, xdiff, ydiff, loopdiff;
    Spline *spline, *first;
    int i,j,k;
    SplinePoint *p_to, *m_to, *p_from, *m_from;
    int cnt, anyknots;
    double ts[9];
    BasePoint m,p,temp;
    double mt1, pt1, mt2, pt2, rsq;
    int pinners[10];
    int mwascovered, pwascovered;
    enum knot_type { kt_knot=1, kt_pgood=2, kt_mgood=4 };
    int toobig;

    first = NULL;
    for ( spline = spl->first->next; spline!=NULL && spline!=first; spline = spline->to->next ) {
        cur = chunkalloc(sizeof(struct strokedspline));
        if ( last==NULL )
            head = cur;
        else {
            last->next = cur;
            cur->prev = last;
        }
        last = cur;
        cur->s = spline;
        SplineIsLinearMake(spline);
        SplineExpand(spline,0,0,si,&pto,&mfrom);
        SplineExpand(spline,1,0,si,&pfrom,&mto);
        cur->minusfrom = SPNew(spline->from,&mfrom,&spline->from->nextcp,true);
        cur->plusto = SPNew(spline->from,&pto,&spline->from->nextcp,false);
        cur->minusto = SPNew(spline->to,&mto,&spline->to->prevcp,false);
        cur->plusfrom = SPNew(spline->to,&pfrom,&spline->to->prevcp,true);

        if ( si->stroke_type == si_caligraphic ) {
            /* At each t where the spline is tangent to one of the pen-angles */
            /*  we need to figure out which side is inner and which is outer */
            /*  the outer side gets a copy of the appropriate pen side (with corner points tangent) */
            /*  the inner side is going to be a single corner point at the */
            /*  intersection of the splines from the two corners */
            /* And if (god help us) we've got a point of inflection here then */
            /*  we get half the pen on each side */
            /* I ignore the case of a point of inflection, and I don't */
            /*  find the real intersection point, I just guess that it is */
            /*  near the mid point of the pen */
            cnt = SplineSolveForPen(spline,si,ts,pinners+1,0,1);
            p_to = m_to = NULL;
            p_from = NULL;              /* Make gcc happy */
            for ( j=1; j<cnt; ++j ) {
                for ( i=0; i<Approx; ++i ) {
                    real t = ts[j-1] + (i+1)*(ts[j]-ts[j-1])/(Approx+1);
                    mmids[i].t = (i+1)/(double) (Approx+1); pmids[i].t = 1-mmids[i].t;
                    SplineExpand(spline,t,0,si,&p,&m);
                    pmids[i].x = p.x; pmids[i].y = p.y;
                    mmids[i].x = m.x; mmids[i].y = m.y;
                }
                if ( j==1 ) {
                    p_to = cur->plusto; m_from = cur->minusfrom;
                } else if ( pinners[j-1] ) {
                    p_to = p_from;
                    SplineExpand(spline,ts[j-1],(ts[j-1]-ts[j-2])/20.,si,&p,&m);
                    m_from = SplinePointCreate(m.x,m.y);
                    m_from->pointtype = pt_tangent;
                    SplineMake3(m_to,m_from);
                } else {
                    m_from = m_to;
                    SplineExpand(spline,ts[j-1],(ts[j-1]-ts[j-2])/20.,si,&p,&m);
                    p_to = SplinePointCreate(p.x,p.y);
                    p_to->pointtype = pt_tangent;
                    SplineMake3(p_to,p_from);
                }
                if ( j==cnt-1 ) {
                    p_from = cur->plusfrom;
                    m_to = cur->minusto;
                } else if ( pinners[j] ) {
                    SplineExpand(spline,ts[j],(ts[j+1]-ts[j-1])/20.,si,&p,&m);
                    SplineExpand(spline,ts[j],-(ts[j+1]-ts[j-1])/20.,si,&temp,&m);
                    p_from = SplinePointCreate((p.x+temp.x)/2,(p.y+temp.y)/2);
                    p_from->pointtype = pt_corner;
                    m_to = SplinePointCreate(m.x,m.y);
                    m_to->pointtype = pt_tangent;
                } else {
                    SplineExpand(spline,ts[j],(ts[j+1]-ts[j-1])/20.,si,&p,&m);
                    SplineExpand(spline,ts[j],-(ts[j+1]-ts[j-1])/20.,si,&p,&temp);
                    p_from = SplinePointCreate(p.x,p.y);
                    p_from->pointtype = pt_tangent;
                    m_to = SplinePointCreate((m.x+temp.x)/2,(m.y+temp.y)/2);
                    m_to->pointtype = pt_corner;
                }
                ApproximateSplineFromPoints(p_from,p_to,pmids,Approx,false);
                ApproximateSplineFromPoints(m_from,m_to,mmids,Approx,false);
                if ( m_from!=cur->minusfrom && m_from->pointtype!=pt_corner )
                    m_from->pointtype = pt_tangent;
            }
        } else {
            /* Figure out where the curve starts to bend sharply, and add */
            /* New points there. I used to strip out the curve where it */
            /*  overlapped itself, but I think that's better done by remove */
            /*  overlap rather than here */
            if ( (xdiff = spline->to->me.x-spline->from->me.x)<0 ) xdiff = -xdiff;
            if ( (ydiff = spline->to->me.y-spline->from->me.y)<0 ) ydiff = -ydiff;
            loopdiff = (xdiff+ydiff==0) ? .1 : 1.0/(4*(xdiff+ydiff)/si->radius);
            approx = rint(1.0/loopdiff);
            if ( approx<0 || approx>3000 ) approx=3000;
            if ( approx>max ) {
                max = approx+10;
                pmids = grealloc(pmids,max*sizeof(TPoint));
                mmids = grealloc(mmids,max*sizeof(TPoint));
                mids = grealloc(mids,max*sizeof(TPoint));
                knots = grealloc(knots,max);
            }

            mwascovered = pwascovered = false;
            toobig = false;
            for ( i=0; i<approx; ++i ) {
                real t = (i+1)/(approx+1);
                SplineExpand(spline,t,0,si,&p,&m);
                OnEdge(&p,&m,spline,t,t,spline,si,&pt1,&mt1,&pt2,&mt2);
                knots[i] = 0;
                if ( ((pt1!=-1 || pt2!=-1) && !pwascovered && i!=0) ||
                        ((mt1!=-1 || mt2!=-1) && !mwascovered && i!=0))
                    knots[i] = kt_knot;
                if ( ((pt1==-1 && pt2==-1) && pwascovered && i!=0 ) ||
                        ((mt1==-1 && mt2==-1) && mwascovered && i!=0 )) {
                    if ( knots[i-1]&kt_knot )
                        knots[i] = kt_knot;
                    else
                        knots[i-1] |= kt_knot;
                }
                pwascovered = pt1!=-1 || pt2!=-1;
                mwascovered = mt1!=-1 || mt2!=-1;
                pmids[i].t = 1-(i+1)/(approx+1);
                pmids[i].x = p.x; pmids[i].y = p.y;
                mmids[i].t = (i+1)/(approx+1);
                mmids[i].x = m.x; mmids[i].y = m.y;
                mids[i].x = (m.x+p.x)/2; mids[i].y = (m.y+p.y)/2;
                /*if ( !pwascovered )*/ knots[i] |= kt_pgood;
                /*if ( !mwascovered )*/ knots[i] |= kt_mgood;
                if ( pwascovered || mwascovered )
                    toobig = true;
            }
            rsq = si->radius*si->radius;
            for ( i=0; i<approx; ++i ) {
                for ( j=1; j<approx/2; ++j ) {
                    if ( i+j<approx ) {
                        Overlaps(&mmids[i],&mids[i+j],rsq);
                        Overlaps(&pmids[i],&mids[i+j],rsq);
                    }
                    if ( i-j>0 ) {
                        Overlaps(&mmids[i],&mids[i-j],rsq);
                        Overlaps(&pmids[i],&mids[i-j],rsq);
                    }
                }
            }
            anyknots = false;
            for ( i=0; i<approx; ++i ) if ( knots[i]&kt_knot ) { anyknots=true; break; }
            if ( toobig ) {
                si->gottoobig = si->gottoobiglocal = true;
                if ( !si->toobigwarn ) {
                    si->toobigwarn = true;
                    ff_post_error( _("Bad Stroke"), _("The stroke width is so big that the generated path\nmay intersect itself in %.100s"),
                            sc==NULL?"<nameless char>": sc->name );
                }
            }

            /* Look for any sharp bends, they give us problems which are */
            /*  eased by creating a new point. */
            if ( !anyknots ) {
                double radius = si->radius;
                si->radius *= 2;
                mwascovered = pwascovered = false;
                for ( i=0; i<approx; ++i ) {
                    real t = (i+1)/(approx+1);
                    SplineExpand(spline,t,0,si,&p,&m);
                    OnEdge(&p,&m,spline,t,t,spline,si,&pt1,&mt1,&pt2,&mt2);
                    if ( ((pt1!=-1 || pt2!=-1) && !pwascovered && i!=0) ||
                            ((mt1!=-1 || mt2!=-1) && !mwascovered && i!=0))
                        knots[i] |= kt_knot;
                    if ( ((pt1==-1 && pt2==-1) && pwascovered && i!=0 ) ||
                            ((mt1==-1 && mt2==-1) && mwascovered && i!=0 )) {
                        if ( knots[i-1]&kt_knot )
                            knots[i] |= kt_knot;
                        else
                            knots[i-1] |= kt_knot;
                    }
                    pwascovered = pt1!=-1 || pt2!=-1;
                    mwascovered = mt1!=-1 || mt2!=-1;
                }
                si->radius = radius;
            }

            p_to = cur->plusto;
            m_from = cur->minusfrom;
            for ( i=0, j=1; i<approx; ++i ) {
                if ( knots[i]&kt_knot ) {
                    for ( k=i+1; k<approx && !(knots[k]&kt_knot); ++k );
                    if ( i>0 && (knots[i-1]&kt_mgood) ) {
                        if ( i+1<approx && !(knots[i+1]&kt_mgood) && k<approx )
                            m_to = SplinePointCreate((mmids[i].x+mmids[k].x)/2,(mmids[i].y+mmids[k].y)/2);
                        else
                            m_to = SplinePointCreate(mmids[i].x,mmids[i].y);
                        m_to->pointtype = pt_corner;
                        SPFigureCP(m_from,(j)/(approx+1),spline,true);
                        SPFigureCP(m_to,(i+1)/(approx+1),spline,false);
                        NormalizeT(mmids+j,i-j,mmids[j-1].t,mmids[i].t);
                        ApproximateSplineFromPointsSlopes(m_from,m_to,mmids+j,i-j,false);
                        m_from = m_to;
                    }

                    if ( i>0 && (knots[i-1]&kt_pgood) ) {
                        if ( i+1<approx && !(knots[i+1]&kt_pgood) && k<approx )
                            p_from = SplinePointCreate((pmids[i].x+pmids[k].x)/2,(pmids[i].y+pmids[k].y)/2);
                        else
                            p_from = SplinePointCreate(pmids[i].x,pmids[i].y);
                        p_from->pointtype = pt_corner;
                        SPFigurePlusCP(p_to,j/(approx+1),spline,false);
                        SPFigurePlusCP(p_from,(i+1)/(approx+1),spline,true);
                        NormalizeT(pmids+j,i-j,pmids[i].t,pmids[j-1].t);
                        ApproximateSplineFromPointsSlopes(p_from,p_to,pmids+j,i-j,false);
                        p_to = p_from;
                    }

                    j=i+1;
                }
            }

            if ( j!=1 ) {
                NormalizeT(pmids+j,i-j,0.0,pmids[j-1].t);
                NormalizeT(mmids+j,i-j,mmids[j-1].t,1.0);
                SPFigureCP(m_from,(j)/(approx+1),spline,true);
                SPFigurePlusCP(p_to,(j)/(approx+1),spline,false);
            }
            ApproximateSplineFromPointsSlopes(cur->plusfrom,p_to,pmids+j,i-j,false);
            ApproximateSplineFromPointsSlopes(m_from,cur->minusto,mmids+j,i-j,false);
        }
        if ( spline->to->next==NULL ) {
            /* Done */
    break;
        }
        if ( first==NULL ) first = spline;
    }
    if ( spline==first ) {
        head->prev = last;
        last->next = head;
    }
    free(mmids); free(pmids); free(knots); free(mids);
return( head );
}

static void SPLCheckValidity(SplineSet *ss) {
    SplinePoint *sp, *nsp;

    for ( sp=ss->first; ; sp = nsp ) {
        if ( sp->next==NULL )
    break;
        nsp = sp->next->to;
        if ( nsp->prev != sp->next || sp->next->from!=sp )
            IError("Bad SPL");
        if ( nsp==ss->first )
    break;
    }

    for ( sp=ss->last; ; sp = nsp ) {
        if ( sp->prev==NULL )
    break;
        nsp = sp->prev->from;
        if ( nsp->next != sp->prev || sp->prev->to!=sp )
            IError("Bad SPL");
        if ( nsp==ss->last )
    break;
    }
}

static SplineSet *_SplineSetStroke(SplineSet *spl,StrokeInfo *si,SplineChar *sc) {
    SplineSet *ssplus, *ssminus;
    int reversed = false;
    struct strokedspline *head, *cur, *first, *lastp, *lastm;
    Spline *s1, *s2;

    si->gottoobiglocal = false;

    if ( spl->first->next==NULL || spl->first->next->to==spl->first ) {
        /* Only one point in the SplineSet. */
        ssplus = chunkalloc(sizeof(SplineSet));
        SinglePointStroke(spl->first,si,&ssplus->first,&ssplus->last);
return( ssplus );
    }

    SplineSetAddExtrema(NULL,spl,ae_all,1000/* Not used*/);

    if ( spl->first==spl->last && spl->first->next!=NULL ) {
        /* My routine gets screwed up by counter-clockwise triangles */
        if ( !SplinePointListIsClockwise(spl)) {
            reversed = true;
            SplineSetReverse(spl);
        }
    }

    head = cur = _SplineSetApprox(spl,si,sc);

    first = NULL;
    for ( cur=head; cur!=NULL && cur!=first; cur=cur->next ) {
        if ( first==NULL ) first = cur;
        if ( cur->s->to->next!=NULL )
            StrokeJoint(cur->s->to,si,cur,cur->next,sc);
        FreeOrigStuff(cur);
    }
    FreeOrigStuff(head);        /* normally gets freed when we look at the next item on list. But we did that for head first */

    /* Finish off intersections, before doing joins */
    if ( spl->first->prev==NULL ) {
        StrokeEndComplete(head,si,true);
        for ( cur=head; cur->next!=NULL; cur=cur->next );
        StrokeEndComplete(cur,si,false);
    }

    lastp = lastm = head;
    if ( lastp->plusskip ) lastp = NULL;
    if ( lastm->minusskip ) lastm = NULL;

    first = NULL;
    for ( cur=head; cur!=NULL && cur!=first; cur=cur->next ) {
        real factor = si->factor==NULL ? 1.0 : (si->factor)(si->data,cur->s,1.0);
        if ( first==NULL ) first = cur;
        
        if ( cur->s->to->next!=NULL ) {
            if ( !cur->plusskip ) lastp = cur;
            if ( lastp!=NULL && !cur->next->plusskip ) {
                if ( cur->pinnerto==-1 )
                    MSP(cur->next->plusto,&lastp->plusfrom,&lastp->plusto);
                else if ( cur->pinnerto )
                    MSP(cur->next->plusto,&lastp->plusfrom,&lastp->plusto);
                else if ( cur==lastp )
                    MakeJoints(cur->next->plusto,cur->plusfrom,si,&cur->pinterto,
                            &cur->s->to->me,-1,cur->pangle,cur->nangle,factor);
                else
                    IError("Lastp not cur" );
            }
            if ( !cur->minusskip ) lastm = cur;
            if ( lastm!=NULL && !cur->next->minusskip ) {
                if ( cur->minnerto==-1 )
                    MSP(lastm->minusto,&cur->next->minusfrom,&cur->next->minusto);
                else if ( cur->minnerto )
                    MSP(lastm->minusto,&cur->next->minusfrom,&cur->next->minusto);
                else if ( cur==lastm )
                    MakeJoints(lastm->minusto,cur->next->minusfrom,si,&cur->minterto,
                            &cur->s->to->me,1,PI+cur->nangle,PI+cur->pangle,factor);
                else
                    IError("Lastm not cur");
            }
        }
    }

    for ( cur=head; cur!=NULL && cur->plusskip; ) { cur=cur->next; if ( cur==head ) cur=NULL; }
    if ( cur!=NULL ) {
        ssplus = chunkalloc(sizeof(SplineSet));
        ssplus->first = ssplus->last = cur->plusfrom;
        SplineSetFixCPs(ssplus);
        SPLCheckValidity(ssplus);
    } else
        /* It is possible to have a contour completely swallowed by the pen */
        ssplus = NULL;
    for ( cur=head; cur!=NULL && cur->minusskip; ) { cur=cur->next; if ( cur==head ) cur=NULL; }
    if ( spl->first==spl->last && cur!=NULL ) {
        ssminus = chunkalloc(sizeof(SplineSet));
        ssminus->first = ssminus->last = cur->minusfrom;
        SPLCheckValidity(ssminus);
        /*SplineSetFixRidiculous(ssplus); SplineSetFixRidiculous(ssminus);*/
        SplineSetFixCPs(ssminus);
        if ( reversed ) {
            SplineSet *temp = ssplus;
            ssplus = ssminus;
            ssminus = temp;
        }
        SplineSetReverse(ssminus);
        if ( ssplus != NULL )
            SplineSetReverse(ssplus);
        if ( si->removeinternal && ssplus!=NULL ) {
            SplinePointListFree(ssminus);
        } else if ( si->removeexternal ) {
            SplinePointListFree(ssplus);
            SplineSetReverse(ssminus);
            ssplus = ssminus;
        } else {
            if ( ssplus != NULL )
                ssplus->next = ssminus;
            else
                ssplus = ssminus;
            /* I used to do a splineset correct dir here on both, but */
            /*  that doesn't work always if a contour self intersects */
            /* I think it should always be correct */
        }
        /* I can't always detect an overlap, so let's always do the remove */
                /* Sigh, no. That is still too dangerous */
        if ( si->removeoverlapifneeded && ssplus!=NULL && SplineSetIntersect(ssplus,&s1,&s2))
            ssplus = SplineSetRemoveOverlap(sc,ssplus,over_remove);
        if ( reversed )         /* restore original, just in case we want it */
            SplineSetReverse(spl);
    } else if ( si->stroke_type==si_std || si->stroke_type==si_elipse )
        SplineSetReverse(ssplus);
    StrokedSplineFree(head);
return( ssplus );
}

static SplineSet *SSRemoveUTurns(SplineSet *base, StrokeInfo *si) {
    /* All too often in MetaPost output splines have tiny cps which */
    /*  make the slope at the end-points irrelevant when looking at */
    /*  the curve.  Since we assume the slope at the end-points is */
    /*  similar to the slope at t=.01 this confuses us greatly and */
    /*  produces nasty results. In this case try to approximate a new */
    /*  spline with very different cps. Note: We break continuity! */
    /* A special case of this is the following: */
    /* My stroking algorithem gets confused by sharp turns. For example */
    /*  if we have a spline which is all in a line, but the control points */
    /*  are such that it doubles back on itself ( "* +   * +", ie. cps */
    /*  outside of the points) then things get very unhappy */
    SplineSet *spl= base;
    Spline *first, *s, *next, *snew;
    double dx,dy, offx,offy, diff, n,l, slen, len, bound;
    int linear, bad, i, cnt;
    SplinePoint fakefrom, faketo;
    TPoint *tps;

    bound = si->radius*si->radius;
    first = NULL;
  if ( spl->first->next!=NULL && !spl->first->next->order2 )
    for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
        if ( first==NULL ) first = s;

        bad = false;
        dx = s->to->me.x-s->from->me.x;
        dy = s->to->me.y-s->from->me.y;
        slen = dx*dx + dy*dy;

        offx = s->from->nextcp.x-s->from->me.x;
        offy = s->from->nextcp.y-s->from->me.y;
        l= offx*dx + offy*dy;
        if ( l<0 ) {
            l = -l;
            if ( (n= offx*dy - offy*dx)<0 ) n = -n;
            len = offx*offx + offy*offy;
            if ( (n/l>2*len/si->radius || (n>l/3 && s->from->prev==NULL )) && len<bound && len< slen/4 )
                bad = 1;
        }

        offx = s->to->me.x-s->to->prevcp.x;
        offy = s->to->me.y-s->to->prevcp.y;
        l= offx*dx + offy*dy;
        if ( l<0 ) {
            l = -l;
            if ( (n= offx*dy - offy*dx)<0 ) n = -n;
            len = offx*offx + offy*offy;
            if ( (n/l>2*len/si->radius || (n>l/3 && s->to->next==NULL)) && len<bound && len< slen/4 )
                bad |= 2;
        }

        if ( bad ) {
            fakefrom = *s->from; fakefrom.next = fakefrom.prev = NULL;
            faketo   = *s->to;   faketo.next   = faketo.prev   = NULL;

            slen = sqrt(slen);
            dx /= slen; dy/=slen;

            if ( bad&1 ) {              /* from->nextcp is nasty */
                offx = s->from->nextcp.x-s->from->me.x;
                offy = s->from->nextcp.y-s->from->me.y;
                len = sqrt(offx*offx + offy*offy);
                offx /= len; offy/=len;

                n = offx*dy - offy*dx;
                fakefrom.nextcp.x = fakefrom.me.x + slen*dx + 3*len*dy;
                fakefrom.nextcp.y = fakefrom.me.y + slen*dy - 3*len*dx;
            }

            if ( bad&2 ) {              /* from->nextcp is nasty */
                offx = s->to->prevcp.x-s->to->me.x;
                offy = s->to->prevcp.y-s->to->me.y;
                len = sqrt(offx*offx + offy*offy);
                offx /= len; offy/=len;

                n = offx*dy - offy*dx;
                faketo.prevcp.x = faketo.me.x - slen*dx + 3*len*dy;
                faketo.prevcp.y = faketo.me.y - slen*dy - 3*len*dx;
            }

            if (( cnt = slen/2)<10 ) cnt = 10;
            tps = galloc(cnt*sizeof(TPoint));
            for ( i=0; i<cnt; ++i ) {
                double t = ((double) (i+1))/(cnt+1);
                tps[i].t = t;
                tps[i].x = ((s->splines[0].a*t + s->splines[0].b)*t + s->splines[0].c)*t + s->splines[0].d;
                tps[i].y = ((s->splines[1].a*t + s->splines[1].b)*t + s->splines[1].c)*t + s->splines[1].d;
            }
            snew = ApproximateSplineFromPointsSlopes(&fakefrom,&faketo,tps,cnt,false);
            snew->from = s->from;
            snew->to = s->to;
            snew->from->next = snew;
            snew->to->prev = snew;
            snew->from->nextcp = fakefrom.nextcp;
            snew->from->nonextcp = fakefrom.nonextcp;
            if ( bad&1 ) snew->from->pointtype = pt_corner;
            snew->to->prevcp = faketo.prevcp;
            snew->to->noprevcp = faketo.noprevcp;
            if ( bad&2 ) snew->to->pointtype = pt_corner;
            if ( first==s ) first=snew;
            SplineFree(s);
            free(tps);
            s = snew;
        }
    }

    first = NULL;
    for ( s = spl->first->next; s!=NULL && s!=first; s=s->to->next ) {
        if ( first==NULL ) first = s;
        dx = s->to->me.x-s->from->me.x;
        dy = s->to->me.y-s->from->me.y;
        offx = s->from->nextcp.x-s->from->me.x;
        offy = s->from->nextcp.y-s->from->me.y;
        if ( offx*dx + offy*dy<0 ) {
            diff = offx*dy-offy*dx;
            linear = ( diff<1 && diff>-1 );
            if ( offx<0 ) offx = -offx;
            if ( offy<0 ) offy = -offy;
            if ( offx+offy<1 || linear ) {
                s->from->nextcp = s->from->me;
                s->from->nonextcp = true;
                if ( s->from->pointtype == pt_curve || s->from->pointtype == pt_hvcurve )
                    s->from->pointtype = pt_corner;
                if ( s->order2 ) {
                    s->to->prevcp = s->to->me;
                    s->to->noprevcp = true;
                    if ( s->to->pointtype==pt_curve || s->to->pointtype == pt_hvcurve )
                        s->to->pointtype = pt_corner;
                }
                SplineRefigure(s);
            }
        }
        offx = s->to->me.x-s->to->prevcp.x;
        offy = s->to->me.y-s->to->prevcp.y;
        if ( offx*dx + offy*dy<0 ) {
            diff = offx*dy-offy*dx;
            linear = ( diff<1 && diff>-1 );
            if ( offx<0 ) offx = -offx;
            if ( offy<0 ) offy = -offy;
            if ( offx+offy<1 || linear ) {
                s->to->prevcp = s->to->me;
                s->to->noprevcp = true;
                if ( s->to->pointtype==pt_curve || s->to->pointtype == pt_hvcurve )
                    s->to->pointtype = pt_corner;
                if ( s->order2 ) {
                    s->from->nextcp = s->from->me;
                    s->from->nonextcp = true;
                    if ( s->from->pointtype == pt_curve || s->from->pointtype == pt_hvcurve )
                        s->from->pointtype = pt_corner;
                }
                SplineRefigure(s);
            }
        }
    }

    /* Zero length splines are bad too */
    /* As are splines of length .000003 */
    first = NULL;
    for ( s = spl->first->next; s!=NULL && s!=first; s=next ) {
        if ( first==NULL ) first = s;
        next = s->to->next;
        if ( s->from->nonextcp && s->to->noprevcp && s!=next &&
                s->from->me.x >= s->to->me.x-.1 && s->from->me.x <= s->to->me.x+.1 &&
                s->from->me.y >= s->to->me.y-.1 && s->from->me.y <= s->to->me.y+.1 ) {
            s->from->next = next;
            if ( next!=NULL ) {
                s->from->nextcp = next->from->nextcp;
                s->from->nonextcp = next->from->nonextcp;
                s->from->nextcpdef = next->from->nextcpdef;
                next->from = s->from;
            }
            SplinePointCatagorize(s->from);
            if ( spl->last == s->to ) {
                if ( next==NULL )
                    spl->last = s->from;
                else
                    spl->first = spl->last = s->from;
            }
            if ( spl->first==s->to ) spl->first = s->from;
            if ( spl->last==s->to ) spl->last = s->from;
            SplinePointFree(s->to);
            SplineFree(s);
            if ( first==s ) first = NULL;
        }
    }

return( base );
}

static void SSRemoveColinearPoints(SplineSet *ss) {
    SplinePoint *sp, *nsp, *nnsp;
    BasePoint dir, ndir;
    double len;
    int removed;

    sp = ss->first;
    if ( sp->prev==NULL )
return;
    nsp = sp->next->to;
    if ( nsp==sp )
return;
    dir.x = nsp->me.x - sp->me.x; dir.y = nsp->me.y - sp->me.y;
    len = dir.x*dir.x + dir.y*dir.y;
    if ( len!=0 ) {
        len = sqrt(len);
        dir.x /= len; dir.y /= len;
    }
    nnsp = nsp->next->to;
    if ( nnsp==sp )
return;
    memset(&ndir,0,sizeof(ndir));
    forever {
        removed = false;
        if ( nsp->next->islinear ) {
            ndir.x = nnsp->me.x - nsp->me.x; ndir.y = nnsp->me.y - nsp->me.y;
            len = ndir.x*ndir.x + ndir.y*ndir.y;
            if ( len!=0 ) {
                len = sqrt(len);
                ndir.x /= len; ndir.y /= len;
            }
        }
        if ( sp->next->islinear && nsp->next->islinear ) {
            double dot =dir.x*ndir.y - dir.y*ndir.x;
            if ( dot<.001 && dot>-.001 ) {
                sp->next->to = nnsp;
                nnsp->prev = sp->next;
                SplineRefigure(sp->next);
                SplineFree(nsp->next);
                SplinePointFree(nsp);
                if ( ss->first==nsp ) ss->first = sp;
                if ( ss->last ==nsp ) ss->last  = sp;
                removed = true;
            } else
                sp = nsp;
        } else
            sp = nsp;
        dir = ndir;
        nsp = nnsp;
        nnsp = nsp->next->to;
        if ( !removed && sp==ss->first )
    break;
    }
}

static void SSesRemoveColinearPoints(SplineSet *ss) {
    while ( ss!=NULL ) {
        SSRemoveColinearPoints(ss);
        ss = ss->next;
    }
}

SplineSet *SplineSetStroke(SplineSet *spl,StrokeInfo *si,SplineChar *sc) {
    SplineSet *ret, *temp, *temp2;
    SplineSet *order3 = NULL;

    if ( spl->first->next!=NULL && spl->first->next->order2 )
        order3 = spl = SSPSApprox(spl);
    if ( si->radius==0 )
        si->radius=1;
    temp2 = SSRemoveUTurns(SplinePointListCopy(spl),si);
    if ( si->stroke_type == si_elipse ) {
        real trans[6], factor;
        StrokeInfo si2;
        trans[0] = trans[3] = si->c;
        trans[1] = -si->s;
        trans[2] = si->s;
        trans[4] = trans[5] = 0;
        factor = si->radius/si->minorradius;
        trans[0] *= factor; trans[2] *= factor;
        temp = SplinePointListCopy(temp2);
#if 0 
        BisectTurners(temp);
#endif
        temp = SplinePointListTransform(temp,trans,true);
        si2 = *si;
        si2.stroke_type = si_std;
        ret = SplineSetStroke(temp,&si2,sc);
        SplinePointListFree(temp);
        trans[0] = trans[3] = si->c;
        trans[1] = si->s;
        trans[2] = -si->s;
        trans[4] = trans[5] = 0;
        factor = si->minorradius/si->radius;
        trans[0] *= factor; trans[1] *= factor;
        ret = SplinePointListTransform(ret,trans,true);
    } else
        ret = _SplineSetStroke(temp2,si,sc);
    SplinePointListFree(temp2);
    if ( order3!=NULL ) {
        temp = SplineSetsTTFApprox(ret);
        SplinePointListsFree(ret);
        SplinePointListFree(order3);
        ret = temp;
    }
    /* We tend to get (small) rounding errors */
    SplineSetsRound2Int(ret,1024.,false,false);
    /* If we use butt line caps or miter joins then we will likely have */
    /*  some spurious colinear points. If we do, remove them */
    SSesRemoveColinearPoints(ret);
return( ret );
}