summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinestroke.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinestroke.c')
-rw-r--r--Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinestroke.c1875
1 files changed, 1875 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinestroke.c b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinestroke.c
new file mode 100644
index 00000000000..ad73a9194c6
--- /dev/null
+++ b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinestroke.c
@@ -0,0 +1,1875 @@
+/* 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>
+#include <gwidget.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 );
+}
+