source/texk/web2c/luatexdir/luafontloader/fontforge/fontforge/splinefill.c

   1 /* Copyright (C) 2000-2008 by George Williams */
   2 /*
   3  * Redistribution and use in source and binary forms, with or without
   4  * modification, are permitted provided that the following conditions are met:
   5
   6  * Redistributions of source code must retain the above copyright notice, this
   7  * list of conditions and the following disclaimer.
   8
   9  * Redistributions in binary form must reproduce the above copyright notice,
  10  * this list of conditions and the following disclaimer in the documentation
  11  * and/or other materials provided with the distribution.
  12
  13  * The name of the author may not be used to endorse or promote products
  14  * derived from this software without specific prior written permission.
  15
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
  17  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  18  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
  19  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  20  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27 #include "pfaedit.h"
  28 #include <stdio.h>
  29 #include <string.h>
  30 #include <ustring.h>
  31 #include <math.h>
  32 #include "splinefont.h"
  33 #include "edgelist.h"
  34
  35 static void HintsFree(Hints *h) {
  36     Hints *hnext;
  37     for ( ; h!=NULL; h = hnext ) {
  38         hnext = h->next;
  39         free(h);
  40     }
  41 }
  42
  43 static void _FreeEdgeList(EdgeList *es) {
  44     int i;
  45
  46     /* edges will be NULL if the user tries to make an enormous bitmap */
  47     /*  if the linear size is bigger than several thousand, we just */
  48     /*  ignore the request */
  49     if ( es->edges!=NULL ) {
  50         for ( i=0; i<es->cnt; ++i ) {
  51             Edge *e, *next;
  52             for ( e = es->edges[i]; e!=NULL; e = next ) {
  53                 next = e->esnext;
  54                 free(e);
  55             }
  56             es->edges[i] = NULL;
  57         }
  58     }
  59 }
  60
  61 void FreeEdges(EdgeList *es) {
  62     _FreeEdgeList(es);
  63     free(es->edges);
  64     free(es->interesting);
  65     HintsFree(es->hhints);
  66     HintsFree(es->vhints);
  67 }
  68
  69 extended IterateSplineSolve(const Spline1D *sp, extended tmin, extended tmax,
  70         extended sought,double err) {
  71     extended t, low, high, test;
  72     Spline1D temp;
  73     int cnt;
  74
  75     /* Now the closed form CubicSolver can have rounding errors so if we know */
  76     /*  the spline to be monotonic, an iterative approach is more accurate */
  77
  78     temp = *sp;
  79     temp.d -= sought;
  80
  81     if ( temp.a==0 && temp.b==0 && temp.c!=0 ) {
  82         t = -temp.d/(extended) temp.c;
  83         if ( t<0 || t>1 )
  84 return( -1 );
  85 return( t );
  86     }
  87
  88     low = ((temp.a*tmin+temp.b)*tmin+temp.c)*tmin+temp.d;
  89     high = ((temp.a*tmax+temp.b)*tmax+temp.c)*tmax+temp.d;
  90     if ( low<err && low>-err )
  91 return(tmin);
  92     if ( high<err && high>-err )
  93 return(tmax);
  94     if (( low<0 && high>0 ) ||
  95             ( low>0 && high<0 )) {
  96
  97         for ( cnt=0; cnt<1000; ++cnt ) {        /* Avoid impossible error limits */
  98             t = (tmax+tmin)/2;
  99             test = ((temp.a*t+temp.b)*t+temp.c)*t+temp.d;
 100             if ( test>-err && test<err )
 101 return( t );
 102             if ( (low<0 && test<0) || (low>0 && test>0) )
 103                 tmin=t;
 104             else
 105                 tmax = t;
 106         }
 107 return( (tmax+tmin)/2 );
 108     }
 109 return( -1 );
 110 }
 111
 112 double TOfNextMajor(Edge *e, EdgeList *es, double sought_m ) {
 113     /* We want to find t so that Mspline(t) = sought_m */
 114     /*  the curve is monotonic */
 115     Spline1D *msp = &e->spline->splines[es->major];
 116     double new_t;
 117
 118     if ( es->is_overlap ) {
 119
 120         /* if we've adjusted the height then we won't be able to find it restricting */
 121         /*  t between [0,1] as we do. So it's a special case. (this is to handle */
 122         /*  hstem hints) */
 123         if ( e->max_adjusted && sought_m==e->mmax ) {
 124             e->m_cur = sought_m;
 125 return( e->up?1.0:0.0 );
 126         }
 127
 128         new_t = IterateSplineSolve(msp,e->t_mmin,e->t_mmax,(sought_m+es->mmin)/es->scale,.001);
 129         if ( new_t==-1 )
 130             IError( "No Solution");
 131         e->m_cur = (((msp->a*new_t + msp->b)*new_t+msp->c)*new_t + msp->d)*es->scale - es->mmin;
 132 return( new_t );
 133     } else {
 134         Spline *sp = e->spline;
 135
 136         if ( sp->islinear ) {
 137             new_t = e->t_cur + (sought_m-e->m_cur)/(es->scale * msp->c);
 138             e->m_cur = (msp->c*new_t + msp->d)*es->scale - es->mmin;
 139 return( new_t );
 140         }
 141         /* if we have a spline that is nearly horizontal at its max. endpoint */
 142         /*  then finding A value of t for which y has the right value isn't good */
 143         /*  enough (at least not when finding intersections) */
 144         if ( sought_m+1>e->mmax ) {
 145             e->m_cur = e->mmax;
 146 return( e->t_mmax );
 147         }
 148
 149         /* if we've adjusted the height then we won't be able to find it restricting */
 150         /*  t between [0,1] as we do. So it's a special case. (this is to handle */
 151         /*  hstem hints) */
 152         if ( e->max_adjusted && sought_m==e->mmax ) {
 153             e->m_cur = sought_m;
 154 return( e->up?1.0:0.0 );
 155         }
 156         new_t = IterateSplineSolve(msp,e->t_mmin,e->t_mmax,(sought_m+es->mmin)/es->scale,.001);
 157         if ( new_t==-1 )
 158             IError( "No Solution");
 159         e->m_cur = (((msp->a*new_t + msp->b)*new_t+msp->c)*new_t + msp->d)*es->scale - es->mmin;
 160 return( new_t );
 161     }
 162 }
 163
 164 static int SlopeLess(Edge *e, Edge *p, int other) {
 165     Spline1D *osp = &e->spline->splines[other];
 166     Spline1D *psp = &p->spline->splines[other];
 167     Spline1D *msp = &e->spline->splines[!other];
 168     Spline1D *qsp = &p->spline->splines[!other];
 169     real os = (3*osp->a*e->t_cur+2*osp->b)*e->t_cur+osp->c,
 170            ps = (3*psp->a*p->t_cur+2*psp->b)*p->t_cur+psp->c;
 171     real ms = (3*msp->a*e->t_cur+2*msp->b)*e->t_cur+msp->c,
 172            qs = (3*qsp->a*p->t_cur+2*qsp->b)*p->t_cur+qsp->c;
 173     if ( ms<.0001 && ms>-.0001 ) ms = 0;
 174     if ( qs<.0001 && qs>-.0001 ) qs = 0;
 175     if ( qs==0 ) {
 176         if ( p->t_cur==1 ) {
 177            qs = (3*qsp->a*.9999+2*qsp->b)*.9999+qsp->c;
 178            ps = (3*psp->a*.9999+2*psp->b)*.9999+psp->c;
 179        } else {
 180            qs = (3*qsp->a*(p->t_cur+.0001)+2*qsp->b)*(p->t_cur+.0001)+qsp->c;
 181            ps = (3*psp->a*(p->t_cur+.0001)+2*psp->b)*(p->t_cur+.0001)+psp->c;
 182        }
 183     }
 184     if ( ms==0 ) {
 185         if ( e->t_cur==1 ) {
 186             ms = (3*msp->a*.9999+2*msp->b)*.9999+msp->c;
 187             os = (3*osp->a*.9999+2*osp->b)*.9999+osp->c;
 188         } else {
 189             ms = (3*msp->a*(e->t_cur+.0001)+2*msp->b)*(e->t_cur+.0001)+msp->c;
 190             os = (3*osp->a*(e->t_cur+.0001)+2*osp->b)*(e->t_cur+.0001)+osp->c;
 191         }
 192     }
 193     if ( e->t_cur-e->tmin > e->tmax-e->t_cur ) { os = -os; ms = -ms; }
 194     if ( p->t_cur-p->tmin > p->tmax-p->t_cur ) { ps = -ps; qs = -qs; }
 195     if ( ms!=0 && qs!=0 ) { os /= ms; ps /= qs; }
 196     else if ( ms==0 && qs==0 ) /* Do Nothing */;
 197     else if ( (ms==0 && os>0) || (qs==0 && ps<0) )              /* Does this make sense? */
 198 return( false );
 199     else if ( (ms==0 && os<0) || (qs==0 && ps>0) )              /* Does this make sense? */
 200 return( true );
 201
 202     if ( os==ps || ms==0 || qs==0 )
 203 return( e->o_mmax<p->o_mmax );
 204
 205 return( os<ps );
 206 }
 207
 208 static void AddEdge(EdgeList *es, Spline *sp, real tmin, real tmax ) {
 209     Edge *e, *pr;
 210     real m1, m2;
 211     int mpos;
 212     Hints *hint;
 213     Spline1D *msp = &sp->splines[es->major], *osp = &sp->splines[es->other];
 214
 215     e = gcalloc(1,sizeof(Edge));
 216     e->spline = sp;
 217
 218     m1 = ( ((msp->a*tmin+msp->b)*tmin+msp->c)*tmin + msp->d ) * es->scale;
 219     m2 = ( ((msp->a*tmax+msp->b)*tmax+msp->c)*tmax + msp->d ) * es->scale;
 220     if ( m1>m2 ) {
 221         e->mmin = m2;
 222         e->t_mmin = tmax;
 223         e->mmax = m1;
 224         e->t_mmax = tmin;
 225         e->up = false;
 226     } else {
 227         e->mmax = m2;
 228         e->t_mmax = tmax;
 229         e->mmin = m1;
 230         e->t_mmin = tmin;
 231         e->up = true;
 232     }
 233     if ( RealNear(e->mmin,es->mmin)) e->mmin = es->mmin;
 234     e->o_mmin = ( ((osp->a*e->t_mmin+osp->b)*e->t_mmin+osp->c)*e->t_mmin + osp->d ) * es->scale;
 235     e->o_mmax = ( ((osp->a*e->t_mmax+osp->b)*e->t_mmax+osp->c)*e->t_mmax + osp->d ) * es->scale;
 236     e->mmin -= es->mmin; e->mmax -= es->mmin;
 237     e->t_cur = e->t_mmin;
 238     e->o_cur = e->o_mmin;
 239     e->m_cur = e->mmin;
 240     e->last_opos = e->last_mpos = -2;
 241     e->tmin = tmin; e->tmax = tmax;
 242
 243     if ( e->mmin<0 || e->mmin>=e->mmax ) {
 244         /*IError("Probably not serious, but we've got a zero length spline in AddEdge in %s",es->sc==NULL?<nameless>:es->sc->name);*/
 245         free(e);
 246 return;
 247     }
 248
 249     if ( es->sc!=NULL ) for ( hint=es->hhints; hint!=NULL; hint=hint->next ) {
 250         if ( hint->adjustb ) {
 251             if ( e->m_cur>hint->b1 && e->m_cur<hint->b2 ) {
 252                 e->m_cur = e->mmin = hint->ab;
 253                 e->min_adjusted = true;
 254             } else if ( e->mmax>hint->b1 && e->mmax<hint->b2 ) {
 255                 e->mmax = hint->ab;
 256                 e->max_adjusted = true;
 257             }
 258         } else if ( hint->adjuste ) {
 259             if ( e->m_cur>hint->e1 && e->m_cur<hint->e2 ) {
 260                 e->m_cur = e->mmin = hint->ae;
 261                 e->min_adjusted = true;
 262             } else if ( e->mmax>hint->e1 && e->mmax<hint->e2 ) {
 263                 e->mmax = hint->ae;
 264                 e->max_adjusted = true;
 265             }
 266         }
 267     }
 268
 269     mpos = (int) ceil(e->m_cur);
 270     if ( mpos>e->mmax || mpos>=es->cnt ) {
 271         free(e);
 272 return;
 273     }
 274
 275     if ( e->m_cur!=ceil(e->m_cur) ) {
 276         /* bring the new edge up to its first scan line */
 277         e->t_cur = TOfNextMajor(e,es,ceil(e->m_cur));
 278         e->o_cur = ( ((osp->a*e->t_cur+osp->b)*e->t_cur+osp->c)*e->t_cur + osp->d ) * es->scale;
 279     }
 280
 281     e->before = es->last;
 282     if ( es->last!=NULL )
 283         es->last->after = e;
 284     if ( es->last==NULL )
 285         es->splinesetfirst = e;
 286     es->last = e;
 287
 288     if ( es->edges[mpos]==NULL || e->o_cur<es->edges[mpos]->o_cur ||
 289             (e->o_cur==es->edges[mpos]->o_cur && SlopeLess(e,es->edges[mpos],es->other))) {
 290         e->esnext = es->edges[mpos];
 291         es->edges[mpos] = e;
 292     } else {
 293         for ( pr=es->edges[mpos]; pr->esnext!=NULL && pr->esnext->o_cur<e->o_cur ;
 294                 pr = pr->esnext );
 295         /* When two splines share a vertex which is a local minimum, then */
 296         /*  o_cur will be equal for both (to the vertex's o value) and so */
 297         /*  the above code randomly picked one to go first. That screws up */
 298         /*  the overlap code, which wants them properly ordered from the */
 299         /*  start. so look at the end point, nope the end point isn't always */
 300         /*  meaningful, look at the slope... */
 301         if ( pr->esnext!=NULL && pr->esnext->o_cur==e->o_cur &&
 302                 SlopeLess(e,pr->esnext,es->other)) {
 303             pr = pr->esnext;
 304         }
 305         e->esnext = pr->esnext;
 306         pr->esnext = e;
 307     }
 308     if ( es->interesting ) {
 309         /* Mark the other end of the spline as interesting */
 310         es->interesting[(int) ceil(e->mmax)]=1;
 311     }
 312 }
 313
 314 static void AddMajorEdge(EdgeList *es, Spline *sp) {
 315     Edge *e, *pr;
 316     real m1;
 317     Spline1D *msp = &sp->splines[es->major], *osp = &sp->splines[es->other];
 318
 319     e = gcalloc(1,sizeof(Edge));
 320     e->spline = sp;
 321
 322     e->mmin = e->mmax = m1 = msp->d * es->scale - es->mmin;
 323     e->t_mmin = 0;
 324     e->t_mmax = 1;
 325     e->up = false;
 326     e->o_mmin = osp->d * es->scale;
 327     e->o_mmax = ( osp->a + osp->b + osp->c + osp->d ) * es->scale;
 328     if ( e->o_mmin == e->o_mmax ) {     /* Just a point? */
 329         free(e);
 330 return;
 331     }
 332     if ( e->mmin<0 )
 333         IError("Grg!");
 334
 335     if ( ceil(e->m_cur)>e->mmax ) {
 336         free(e);
 337 return;
 338     }
 339
 340     if ( es->majors==NULL || es->majors->mmin>=m1 ) {
 341         e->esnext = es->majors;
 342         es->majors = e;
 343     } else {
 344         for ( pr=es->majors; pr->esnext!=NULL && pr->esnext->mmin<m1; pr = pr->esnext );
 345         e->esnext = pr->esnext;
 346         pr->esnext = e;
 347     }
 348 }
 349
 350 static void AddSpline(EdgeList *es, Spline *sp ) {
 351     real t1=2, t2=2, t;
 352     real b2_fourac;
 353     real fm, tm;
 354     Spline1D *msp = &sp->splines[es->major], *osp = &sp->splines[es->other];
 355
 356     /* Find the points of extrema on the curve discribing y behavior */
 357     if ( !RealNear(msp->a,0) ) {
 358         /* cubic, possibly 2 extrema (possibly none) */
 359         b2_fourac = 4*msp->b*msp->b - 12*msp->a*msp->c;
 360         if ( b2_fourac>=0 ) {
 361             b2_fourac = sqrt(b2_fourac);
 362             t1 = CheckExtremaForSingleBitErrors(msp,(-2*msp->b - b2_fourac) / (6*msp->a));
 363             t2 = CheckExtremaForSingleBitErrors(msp,(-2*msp->b + b2_fourac) / (6*msp->a));
 364             if ( t1>t2 ) { real temp = t1; t1 = t2; t2 = temp; }
 365             else if ( t1==t2 ) t2 = 2.0;
 366
 367             /* check for curves which have such a small slope they might */
 368             /*  as well be horizontal */
 369             fm = es->major==1?sp->from->me.y:sp->from->me.x;
 370             tm = es->major==1?sp->to->me.y:sp->to->me.x;
 371             if ( fm==tm ) {
 372                 real m1, m2, d1, d2;
 373                 m1 = m2 = fm;
 374                 if ( t1>0 && t1<1 )
 375                     m1 = ((msp->a*t1+msp->b)*t1+msp->c)*t1 + msp->d;
 376                 if ( t2>0 && t2<1 )
 377                     m2 = ((msp->a*t2+msp->b)*t2+msp->c)*t2 + msp->d;
 378                 d1 = (m1-fm)*es->scale;
 379                 d2 = (m2-fm)*es->scale;
 380                 if ( d1>-.5 && d1<.5 && d2>-.5 && d2<.5 ) {
 381                     sp->ishorvert = true;
 382                     if ( es->genmajoredges )
 383                         AddMajorEdge(es,sp);
 384 return;         /* Pretend it's horizontal, ignore it */
 385                 }
 386             }
 387         }
 388     } else if ( !RealNear(msp->b,0) ) {
 389         /* Quadratic, at most one extremum */
 390         t1 = -msp->c/(2.0*msp->b);
 391     } else if ( !RealNear(msp->c,0) ) {
 392         /* linear, no points of extrema */
 393     } else {
 394         sp->ishorvert = true;
 395         if ( es->genmajoredges )
 396             AddMajorEdge(es,sp);
 397 return;         /* Horizontal line, ignore it */
 398     }
 399
 400     if ( RealNear(t1,0)) t1=0;
 401     if ( RealNear(t1,1)) t1=1;
 402     if ( RealNear(t2,0)) t2=0;
 403     if ( RealNear(t2,1)) t2=1;
 404     if ( RealNear(t1,t2)) t2=2;
 405     t=0;
 406     if ( t1>0 && t1<1 ) {
 407         AddEdge(es,sp,0,t1);
 408         t = t1;
 409     }
 410     if ( t2>0 && t2<1 ) {
 411         AddEdge(es,sp,t,t2);
 412         t = t2;
 413     }
 414     AddEdge(es,sp,t,1.0);
 415     if ( es->interesting ) {
 416         /* Also store up points of extrema in X as interesting (we got the endpoints, just internals now)*/
 417         extended ot1, ot2;
 418         int mpos;
 419         SplineFindExtrema(osp,&ot1,&ot2);
 420         if ( ot1>0 && ot1<1 ) {
 421             mpos = (int) ceil( ( ((msp->a*ot1+msp->b)*ot1+msp->c)*ot1+msp->d )*es->scale-es->mmin );
 422             es->interesting[mpos] = 1;
 423         }
 424         if ( ot2>0 && ot2<1 ) {
 425             mpos = (int) ceil( ( ((msp->a*ot2+msp->b)*ot2+msp->c)*ot2+msp->d )*es->scale-es->mmin );
 426             es->interesting[mpos] = 1;
 427         }
 428     }
 429 }
 430
 431 void FindEdgesSplineSet(SplinePointList *spl, EdgeList *es, int ignore_clip) {
 432     Spline *spline, *first;
 433
 434     for ( ; spl!=NULL; spl = spl->next ) {
 435         if ( spl->first->prev!=NULL && spl->first->prev->from!=spl->first &&
 436                 (!ignore_clip || (ignore_clip==1 && !spl->is_clip_path) || (ignore_clip==2 && spl->is_clip_path))) {
 437             first = NULL;
 438             es->last = es->splinesetfirst = NULL;
 439             /* Set so there is no previous point!!! */
 440             for ( spline = spl->first->next; spline!=NULL && spline!=first; spline=spline->to->next ) {
 441                 AddSpline(es,spline);
 442                 if ( first==NULL ) first = spline;
 443             }
 444             if ( es->last!=NULL ) {
 445                 es->splinesetfirst->before = es->last;
 446                 es->last->after = es->splinesetfirst;
 447             }
 448         }
 449     }
 450 }
 451
 452 Edge *ActiveEdgesInsertNew(EdgeList *es, Edge *active,int i) {
 453     Edge *apt, *pr, *npt;
 454
 455     for ( pr=NULL, apt=active, npt=es->edges[(int) i]; apt!=NULL && npt!=NULL; ) {
 456         if ( npt->o_cur<apt->o_cur ) {
 457             npt->aenext = apt;
 458             if ( pr==NULL )
 459                 active = npt;
 460             else
 461                 pr->aenext = npt;
 462             pr = npt;
 463             npt = npt->esnext;
 464         } else {
 465             pr = apt;
 466             apt = apt->aenext;
 467         }
 468     }
 469     while ( npt!=NULL ) {
 470         npt->aenext = NULL;
 471         if ( pr==NULL )
 472             active = npt;
 473         else
 474             pr->aenext = npt;
 475         pr = npt;
 476         npt = npt->esnext;
 477     }
 478 return( active );
 479 }
 480
 481 Edge *ActiveEdgesRefigure(EdgeList *es, Edge *active,real i) {
 482     Edge *apt, *pr;
 483     int any;
 484
 485     /* first remove any entry which doesn't intersect the new scan line */
 486     /*  (ie. stopped on last line) */
 487     for ( pr=NULL, apt=active; apt!=NULL; apt = apt->aenext ) {
 488         if ( apt->mmax<i ) {
 489             if ( pr==NULL )
 490                 active = apt->aenext;
 491             else
 492                 pr->aenext = apt->aenext;
 493         } else
 494             pr = apt;
 495     }
 496     /* then move the active list to the next line */
 497     for ( apt=active; apt!=NULL; apt = apt->aenext ) {
 498         Spline1D *osp = &apt->spline->splines[es->other];
 499         apt->t_cur = TOfNextMajor(apt,es,i);
 500         apt->o_cur = ( ((osp->a*apt->t_cur+osp->b)*apt->t_cur+osp->c)*apt->t_cur + osp->d ) * es->scale;
 501     }
 502     /* reorder list */
 503     if ( active!=NULL ) {
 504         any = true;
 505         while ( any ) {
 506             any = false;
 507             for ( pr=NULL, apt=active; apt->aenext!=NULL; ) {
 508                 if ( apt->o_cur <= apt->aenext->o_cur ) {
 509                     /* still ordered */;
 510                     pr = apt;
 511                     apt = apt->aenext;
 512                 } else if ( pr==NULL ) {
 513                     active = apt->aenext;
 514                     apt->aenext = apt->aenext->aenext;
 515                     active->aenext = apt;
 516                     /* don't need to set any, since this reorder can't disorder the list */
 517                     pr = active;
 518                 } else {
 519                     pr->aenext = apt->aenext;
 520                     apt->aenext = apt->aenext->aenext;
 521                     pr->aenext->aenext = apt;
 522                     any = true;
 523                     pr = pr->aenext;
 524                 }
 525             }
 526         }
 527     }
 528     /* Insert new nodes */
 529     active = ActiveEdgesInsertNew(es,active,i);
 530 return( active );
 531 }
 532