summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c
diff options
context:
space:
mode:
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.c532
1 files changed, 0 insertions, 532 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
deleted file mode 100644
index b9e52fb9fbd..00000000000
--- a/Build/source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c
+++ /dev/null
@@ -1,532 +0,0 @@
-/* Copyright (C) 2000-2008 by George Williams */
-/*
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
-
- * Redistributions of source code must retain the above copyright notice, this
- * list of conditions and the following disclaimer.
-
- * Redistributions in binary form must reproduce the above copyright notice,
- * this list of conditions and the following disclaimer in the documentation
- * and/or other materials provided with the distribution.
-
- * The name of the author may not be used to endorse or promote products
- * derived from this software without specific prior written permission.
-
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
- * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
- * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
- * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-#include "pfaedit.h"
-#include <stdio.h>
-#include <string.h>
-#include <ustring.h>
-#include <math.h>
-#include "splinefont.h"
-#include "edgelist.h"
-
-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 );
-}
-