diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c | 535 |
1 files changed, 535 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c new file mode 100644 index 00000000000..c8f55197d6e --- /dev/null +++ b/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c @@ -0,0 +1,535 @@ +/* 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 <stdio.h> +#include <string.h> +#include <ustring.h> +#include <math.h> +#include "gdraw.h" +#include "splinefont.h" +#include "edgelist.h" + +Color default_background = 0xffffff; /* white */ + +static void HintsFree(Hints *h) { + Hints *hnext; + for ( ; h!=NULL; h = hnext ) { + hnext = h->next; + free(h); + } +} + +static void _FreeEdgeList(EdgeList *es) { + int i; + + /* edges will be NULL if the user tries to make an enormous bitmap */ + /* if the linear size is bigger than several thousand, we just */ + /* ignore the request */ + if ( es->edges!=NULL ) { + for ( i=0; i<es->cnt; ++i ) { + Edge *e, *next; + for ( e = es->edges[i]; e!=NULL; e = next ) { + next = e->esnext; + free(e); + } + es->edges[i] = NULL; + } + } +} + +void FreeEdges(EdgeList *es) { + _FreeEdgeList(es); + free(es->edges); + free(es->interesting); + HintsFree(es->hhints); + HintsFree(es->vhints); +} + +extended IterateSplineSolve(const Spline1D *sp, extended tmin, extended tmax, + extended sought,double err) { + extended t, low, high, test; + Spline1D temp; + int cnt; + + /* Now the closed form CubicSolver can have rounding errors so if we know */ + /* the spline to be monotonic, an iterative approach is more accurate */ + + temp = *sp; + temp.d -= sought; + + if ( temp.a==0 && temp.b==0 && temp.c!=0 ) { + t = -temp.d/(extended) temp.c; + if ( t<0 || t>1 ) +return( -1 ); +return( t ); + } + + low = ((temp.a*tmin+temp.b)*tmin+temp.c)*tmin+temp.d; + high = ((temp.a*tmax+temp.b)*tmax+temp.c)*tmax+temp.d; + if ( low<err && low>-err ) +return(tmin); + if ( high<err && high>-err ) +return(tmax); + if (( low<0 && high>0 ) || + ( low>0 && high<0 )) { + + for ( cnt=0; cnt<1000; ++cnt ) { /* Avoid impossible error limits */ + t = (tmax+tmin)/2; + test = ((temp.a*t+temp.b)*t+temp.c)*t+temp.d; + if ( test>-err && test<err ) +return( t ); + if ( (low<0 && test<0) || (low>0 && test>0) ) + tmin=t; + else + tmax = t; + } +return( (tmax+tmin)/2 ); + } +return( -1 ); +} + +double TOfNextMajor(Edge *e, EdgeList *es, double sought_m ) { + /* We want to find t so that Mspline(t) = sought_m */ + /* the curve is monotonic */ + Spline1D *msp = &e->spline->splines[es->major]; + double new_t; + + if ( es->is_overlap ) { + + /* if we've adjusted the height then we won't be able to find it restricting */ + /* t between [0,1] as we do. So it's a special case. (this is to handle */ + /* hstem hints) */ + if ( e->max_adjusted && sought_m==e->mmax ) { + e->m_cur = sought_m; +return( e->up?1.0:0.0 ); + } + + new_t = IterateSplineSolve(msp,e->t_mmin,e->t_mmax,(sought_m+es->mmin)/es->scale,.001); + if ( new_t==-1 ) + IError( "No Solution"); + e->m_cur = (((msp->a*new_t + msp->b)*new_t+msp->c)*new_t + msp->d)*es->scale - es->mmin; +return( new_t ); + } else { + Spline *sp = e->spline; + + if ( sp->islinear ) { + new_t = e->t_cur + (sought_m-e->m_cur)/(es->scale * msp->c); + e->m_cur = (msp->c*new_t + msp->d)*es->scale - es->mmin; +return( new_t ); + } + /* if we have a spline that is nearly horizontal at its max. endpoint */ + /* then finding A value of t for which y has the right value isn't good */ + /* enough (at least not when finding intersections) */ + if ( sought_m+1>e->mmax ) { + e->m_cur = e->mmax; +return( e->t_mmax ); + } + + /* if we've adjusted the height then we won't be able to find it restricting */ + /* t between [0,1] as we do. So it's a special case. (this is to handle */ + /* hstem hints) */ + if ( e->max_adjusted && sought_m==e->mmax ) { + e->m_cur = sought_m; +return( e->up?1.0:0.0 ); + } + new_t = IterateSplineSolve(msp,e->t_mmin,e->t_mmax,(sought_m+es->mmin)/es->scale,.001); + if ( new_t==-1 ) + IError( "No Solution"); + e->m_cur = (((msp->a*new_t + msp->b)*new_t+msp->c)*new_t + msp->d)*es->scale - es->mmin; +return( new_t ); + } +} + +static int SlopeLess(Edge *e, Edge *p, int other) { + Spline1D *osp = &e->spline->splines[other]; + Spline1D *psp = &p->spline->splines[other]; + Spline1D *msp = &e->spline->splines[!other]; + Spline1D *qsp = &p->spline->splines[!other]; + real os = (3*osp->a*e->t_cur+2*osp->b)*e->t_cur+osp->c, + ps = (3*psp->a*p->t_cur+2*psp->b)*p->t_cur+psp->c; + real ms = (3*msp->a*e->t_cur+2*msp->b)*e->t_cur+msp->c, + qs = (3*qsp->a*p->t_cur+2*qsp->b)*p->t_cur+qsp->c; + if ( ms<.0001 && ms>-.0001 ) ms = 0; + if ( qs<.0001 && qs>-.0001 ) qs = 0; + if ( qs==0 ) { + if ( p->t_cur==1 ) { + qs = (3*qsp->a*.9999+2*qsp->b)*.9999+qsp->c; + ps = (3*psp->a*.9999+2*psp->b)*.9999+psp->c; + } else { + qs = (3*qsp->a*(p->t_cur+.0001)+2*qsp->b)*(p->t_cur+.0001)+qsp->c; + ps = (3*psp->a*(p->t_cur+.0001)+2*psp->b)*(p->t_cur+.0001)+psp->c; + } + } + if ( ms==0 ) { + if ( e->t_cur==1 ) { + ms = (3*msp->a*.9999+2*msp->b)*.9999+msp->c; + os = (3*osp->a*.9999+2*osp->b)*.9999+osp->c; + } else { + ms = (3*msp->a*(e->t_cur+.0001)+2*msp->b)*(e->t_cur+.0001)+msp->c; + os = (3*osp->a*(e->t_cur+.0001)+2*osp->b)*(e->t_cur+.0001)+osp->c; + } + } + if ( e->t_cur-e->tmin > e->tmax-e->t_cur ) { os = -os; ms = -ms; } + if ( p->t_cur-p->tmin > p->tmax-p->t_cur ) { ps = -ps; qs = -qs; } + if ( ms!=0 && qs!=0 ) { os /= ms; ps /= qs; } + else if ( ms==0 && qs==0 ) /* Do Nothing */; + else if ( (ms==0 && os>0) || (qs==0 && ps<0) ) /* Does this make sense? */ +return( false ); + else if ( (ms==0 && os<0) || (qs==0 && ps>0) ) /* Does this make sense? */ +return( true ); + + if ( os==ps || ms==0 || qs==0 ) +return( e->o_mmax<p->o_mmax ); + +return( os<ps ); +} + +static void AddEdge(EdgeList *es, Spline *sp, real tmin, real tmax ) { + Edge *e, *pr; + real m1, m2; + int mpos; + Hints *hint; + Spline1D *msp = &sp->splines[es->major], *osp = &sp->splines[es->other]; + + e = gcalloc(1,sizeof(Edge)); + e->spline = sp; + + m1 = ( ((msp->a*tmin+msp->b)*tmin+msp->c)*tmin + msp->d ) * es->scale; + m2 = ( ((msp->a*tmax+msp->b)*tmax+msp->c)*tmax + msp->d ) * es->scale; + if ( m1>m2 ) { + e->mmin = m2; + e->t_mmin = tmax; + e->mmax = m1; + e->t_mmax = tmin; + e->up = false; + } else { + e->mmax = m2; + e->t_mmax = tmax; + e->mmin = m1; + e->t_mmin = tmin; + e->up = true; + } + if ( RealNear(e->mmin,es->mmin)) e->mmin = es->mmin; + e->o_mmin = ( ((osp->a*e->t_mmin+osp->b)*e->t_mmin+osp->c)*e->t_mmin + osp->d ) * es->scale; + e->o_mmax = ( ((osp->a*e->t_mmax+osp->b)*e->t_mmax+osp->c)*e->t_mmax + osp->d ) * es->scale; + e->mmin -= es->mmin; e->mmax -= es->mmin; + e->t_cur = e->t_mmin; + e->o_cur = e->o_mmin; + e->m_cur = e->mmin; + e->last_opos = e->last_mpos = -2; + e->tmin = tmin; e->tmax = tmax; + + if ( e->mmin<0 || e->mmin>=e->mmax ) { + /*IError("Probably not serious, but we've got a zero length spline in AddEdge in %s",es->sc==NULL?<nameless>:es->sc->name);*/ + free(e); +return; + } + + if ( es->sc!=NULL ) for ( hint=es->hhints; hint!=NULL; hint=hint->next ) { + if ( hint->adjustb ) { + if ( e->m_cur>hint->b1 && e->m_cur<hint->b2 ) { + e->m_cur = e->mmin = hint->ab; + e->min_adjusted = true; + } else if ( e->mmax>hint->b1 && e->mmax<hint->b2 ) { + e->mmax = hint->ab; + e->max_adjusted = true; + } + } else if ( hint->adjuste ) { + if ( e->m_cur>hint->e1 && e->m_cur<hint->e2 ) { + e->m_cur = e->mmin = hint->ae; + e->min_adjusted = true; + } else if ( e->mmax>hint->e1 && e->mmax<hint->e2 ) { + e->mmax = hint->ae; + e->max_adjusted = true; + } + } + } + + mpos = (int) ceil(e->m_cur); + if ( mpos>e->mmax || mpos>=es->cnt ) { + free(e); +return; + } + + if ( e->m_cur!=ceil(e->m_cur) ) { + /* bring the new edge up to its first scan line */ + e->t_cur = TOfNextMajor(e,es,ceil(e->m_cur)); + e->o_cur = ( ((osp->a*e->t_cur+osp->b)*e->t_cur+osp->c)*e->t_cur + osp->d ) * es->scale; + } + + e->before = es->last; + if ( es->last!=NULL ) + es->last->after = e; + if ( es->last==NULL ) + es->splinesetfirst = e; + es->last = e; + + if ( es->edges[mpos]==NULL || e->o_cur<es->edges[mpos]->o_cur || + (e->o_cur==es->edges[mpos]->o_cur && SlopeLess(e,es->edges[mpos],es->other))) { + e->esnext = es->edges[mpos]; + es->edges[mpos] = e; + } else { + for ( pr=es->edges[mpos]; pr->esnext!=NULL && pr->esnext->o_cur<e->o_cur ; + pr = pr->esnext ); + /* When two splines share a vertex which is a local minimum, then */ + /* o_cur will be equal for both (to the vertex's o value) and so */ + /* the above code randomly picked one to go first. That screws up */ + /* the overlap code, which wants them properly ordered from the */ + /* start. so look at the end point, nope the end point isn't always */ + /* meaningful, look at the slope... */ + if ( pr->esnext!=NULL && pr->esnext->o_cur==e->o_cur && + SlopeLess(e,pr->esnext,es->other)) { + pr = pr->esnext; + } + e->esnext = pr->esnext; + pr->esnext = e; + } + if ( es->interesting ) { + /* Mark the other end of the spline as interesting */ + es->interesting[(int) ceil(e->mmax)]=1; + } +} + +static void AddMajorEdge(EdgeList *es, Spline *sp) { + Edge *e, *pr; + real m1; + Spline1D *msp = &sp->splines[es->major], *osp = &sp->splines[es->other]; + + e = gcalloc(1,sizeof(Edge)); + e->spline = sp; + + e->mmin = e->mmax = m1 = msp->d * es->scale - es->mmin; + e->t_mmin = 0; + e->t_mmax = 1; + e->up = false; + e->o_mmin = osp->d * es->scale; + e->o_mmax = ( osp->a + osp->b + osp->c + osp->d ) * es->scale; + if ( e->o_mmin == e->o_mmax ) { /* Just a point? */ + free(e); +return; + } + if ( e->mmin<0 ) + IError("Grg!"); + + if ( ceil(e->m_cur)>e->mmax ) { + free(e); +return; + } + + if ( es->majors==NULL || es->majors->mmin>=m1 ) { + e->esnext = es->majors; + es->majors = e; + } else { + for ( pr=es->majors; pr->esnext!=NULL && pr->esnext->mmin<m1; pr = pr->esnext ); + e->esnext = pr->esnext; + pr->esnext = e; + } +} + +static void AddSpline(EdgeList *es, Spline *sp ) { + real t1=2, t2=2, t; + real b2_fourac; + real fm, tm; + Spline1D *msp = &sp->splines[es->major], *osp = &sp->splines[es->other]; + + /* Find the points of extrema on the curve discribing y behavior */ + if ( !RealNear(msp->a,0) ) { + /* cubic, possibly 2 extrema (possibly none) */ + b2_fourac = 4*msp->b*msp->b - 12*msp->a*msp->c; + if ( b2_fourac>=0 ) { + b2_fourac = sqrt(b2_fourac); + t1 = CheckExtremaForSingleBitErrors(msp,(-2*msp->b - b2_fourac) / (6*msp->a)); + t2 = CheckExtremaForSingleBitErrors(msp,(-2*msp->b + b2_fourac) / (6*msp->a)); + if ( t1>t2 ) { real temp = t1; t1 = t2; t2 = temp; } + else if ( t1==t2 ) t2 = 2.0; + + /* check for curves which have such a small slope they might */ + /* as well be horizontal */ + fm = es->major==1?sp->from->me.y:sp->from->me.x; + tm = es->major==1?sp->to->me.y:sp->to->me.x; + if ( fm==tm ) { + real m1, m2, d1, d2; + m1 = m2 = fm; + if ( t1>0 && t1<1 ) + m1 = ((msp->a*t1+msp->b)*t1+msp->c)*t1 + msp->d; + if ( t2>0 && t2<1 ) + m2 = ((msp->a*t2+msp->b)*t2+msp->c)*t2 + msp->d; + d1 = (m1-fm)*es->scale; + d2 = (m2-fm)*es->scale; + if ( d1>-.5 && d1<.5 && d2>-.5 && d2<.5 ) { + sp->ishorvert = true; + if ( es->genmajoredges ) + AddMajorEdge(es,sp); +return; /* Pretend it's horizontal, ignore it */ + } + } + } + } else if ( !RealNear(msp->b,0) ) { + /* Quadratic, at most one extremum */ + t1 = -msp->c/(2.0*msp->b); + } else if ( !RealNear(msp->c,0) ) { + /* linear, no points of extrema */ + } else { + sp->ishorvert = true; + if ( es->genmajoredges ) + AddMajorEdge(es,sp); +return; /* Horizontal line, ignore it */ + } + + if ( RealNear(t1,0)) t1=0; + if ( RealNear(t1,1)) t1=1; + if ( RealNear(t2,0)) t2=0; + if ( RealNear(t2,1)) t2=1; + if ( RealNear(t1,t2)) t2=2; + t=0; + if ( t1>0 && t1<1 ) { + AddEdge(es,sp,0,t1); + t = t1; + } + if ( t2>0 && t2<1 ) { + AddEdge(es,sp,t,t2); + t = t2; + } + AddEdge(es,sp,t,1.0); + if ( es->interesting ) { + /* Also store up points of extrema in X as interesting (we got the endpoints, just internals now)*/ + extended ot1, ot2; + int mpos; + SplineFindExtrema(osp,&ot1,&ot2); + if ( ot1>0 && ot1<1 ) { + mpos = (int) ceil( ( ((msp->a*ot1+msp->b)*ot1+msp->c)*ot1+msp->d )*es->scale-es->mmin ); + es->interesting[mpos] = 1; + } + if ( ot2>0 && ot2<1 ) { + mpos = (int) ceil( ( ((msp->a*ot2+msp->b)*ot2+msp->c)*ot2+msp->d )*es->scale-es->mmin ); + es->interesting[mpos] = 1; + } + } +} + +void FindEdgesSplineSet(SplinePointList *spl, EdgeList *es, int ignore_clip) { + Spline *spline, *first; + + for ( ; spl!=NULL; spl = spl->next ) { + if ( spl->first->prev!=NULL && spl->first->prev->from!=spl->first && + (!ignore_clip || (ignore_clip==1 && !spl->is_clip_path) || (ignore_clip==2 && spl->is_clip_path))) { + first = NULL; + es->last = es->splinesetfirst = NULL; + /* Set so there is no previous point!!! */ + for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) { + AddSpline(es,spline); + if ( first==NULL ) first = spline; + } + if ( es->last!=NULL ) { + es->splinesetfirst->before = es->last; + es->last->after = es->splinesetfirst; + } + } + } +} + +Edge *ActiveEdgesInsertNew(EdgeList *es, Edge *active,int i) { + Edge *apt, *pr, *npt; + + for ( pr=NULL, apt=active, npt=es->edges[(int) i]; apt!=NULL && npt!=NULL; ) { + if ( npt->o_cur<apt->o_cur ) { + npt->aenext = apt; + if ( pr==NULL ) + active = npt; + else + pr->aenext = npt; + pr = npt; + npt = npt->esnext; + } else { + pr = apt; + apt = apt->aenext; + } + } + while ( npt!=NULL ) { + npt->aenext = NULL; + if ( pr==NULL ) + active = npt; + else + pr->aenext = npt; + pr = npt; + npt = npt->esnext; + } +return( active ); +} + +Edge *ActiveEdgesRefigure(EdgeList *es, Edge *active,real i) { + Edge *apt, *pr; + int any; + + /* first remove any entry which doesn't intersect the new scan line */ + /* (ie. stopped on last line) */ + for ( pr=NULL, apt=active; apt!=NULL; apt = apt->aenext ) { + if ( apt->mmax<i ) { + if ( pr==NULL ) + active = apt->aenext; + else + pr->aenext = apt->aenext; + } else + pr = apt; + } + /* then move the active list to the next line */ + for ( apt=active; apt!=NULL; apt = apt->aenext ) { + Spline1D *osp = &apt->spline->splines[es->other]; + apt->t_cur = TOfNextMajor(apt,es,i); + apt->o_cur = ( ((osp->a*apt->t_cur+osp->b)*apt->t_cur+osp->c)*apt->t_cur + osp->d ) * es->scale; + } + /* reorder list */ + if ( active!=NULL ) { + any = true; + while ( any ) { + any = false; + for ( pr=NULL, apt=active; apt->aenext!=NULL; ) { + if ( apt->o_cur <= apt->aenext->o_cur ) { + /* still ordered */; + pr = apt; + apt = apt->aenext; + } else if ( pr==NULL ) { + active = apt->aenext; + apt->aenext = apt->aenext->aenext; + active->aenext = apt; + /* don't need to set any, since this reorder can't disorder the list */ + pr = active; + } else { + pr->aenext = apt->aenext; + apt->aenext = apt->aenext->aenext; + pr->aenext->aenext = apt; + any = true; + pr = pr->aenext; + } + } + } + } + /* Insert new nodes */ + active = ActiveEdgesInsertNew(es,active,i); +return( active ); +} + |