summaryrefslogtreecommitdiff
path: root/Build/source/texk/dvisvgm/dvisvgm-src/libs/ff-woff/fontforge/splineoverlap.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-src/libs/ff-woff/fontforge/splineoverlap.c')
-rw-r--r--Build/source/texk/dvisvgm/dvisvgm-src/libs/ff-woff/fontforge/splineoverlap.c442
1 files changed, 0 insertions, 442 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-src/libs/ff-woff/fontforge/splineoverlap.c b/Build/source/texk/dvisvgm/dvisvgm-src/libs/ff-woff/fontforge/splineoverlap.c
deleted file mode 100644
index 1c1a430b52a..00000000000
--- a/Build/source/texk/dvisvgm/dvisvgm-src/libs/ff-woff/fontforge/splineoverlap.c
+++ /dev/null
@@ -1,442 +0,0 @@
-/* Copyright (C) 2000-2012 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 "fontforge.h"
-#include "edgelist2.h"
-
-#ifdef HAVE_IEEEFP_H
-# include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */
-#endif
-
-/* First thing we do is divide each spline into a set of sub-splines each of */
-/* which is monotonic in both x and y (always increasing or decreasing) */
-/* Then we compare each monotonic spline with every other one and see if they*/
-/* intersect. If they do, split each up into sub-sub-segments and create an*/
-/* intersection point (note we need to be a little careful if an intersec- */
-/* tion happens at an end point. We don't need to create a intersection for */
-/* two adjacent splines, there isn't a real intersection... but if a third */
-/* spline crosses that point (or ends there) then all three (four) splines */
-/* need to be joined into an intersection point) */
-/* Nasty things happen if splines are coincident. They will almost never be */
-/* perfectly coincident and will keep crossing and recrossing as rounding */
-/* errors suggest one is before the other. Look for coincident splines and */
-/* treat the places they start and stop being coincident as intersections */
-/* then when we find needed splines below look for these guys and ignore */
-/* recrossings of splines which are close together */
-/* Figure out if each monotonic sub-spline is needed or not */
-/* (Note: It was tempting to split the bits up into real splines rather */
-/* than keeping them as sub-sections of the original. Unfortunately this */
-/* splitting introduced rounding errors which meant that we got more */
-/* intersections, which meant that splines could be both needed and un. */
-/* so I don't do that until later) */
-/* if the spline hasn't been tagged yet: */
-/* does the spline change greater in x or y? */
-/* draw a line parallel to the OTHER axis which hits our spline and doesn't*/
-/* hit any endpoints (or intersections, which are end points too now) */
-/* count the winding number (as we do this we can mark other splines as */
-/* needed or not) and figure out if our spline is needed */
-/* So run through the list of intersections */
-/* At an intersection there should be an even number of needed monos. */
-/* Use this as the basis of a new splineset, trace it around until */
-/* we get back to the start intersection (should happen) */
-/* (Note: We may need to reverse a monotonic sub-spline or two) */
-/* As we go, mark each monotonic as having been used */
-/* Keep doing this until all needed exits from all intersections have been */
-/* used. */
-/* The free up our temporary data structures, merge in any open splinesets */
-/* free the old closed splinesets */
-
-// Frank recommends using the following macro whenever making changes
-// to this code and capturing and diffing output in order to track changes
-// in errors and reports.
-// (The pointers tend to clutter the diff a bit.)
-// #define FF_OVERLAP_VERBOSE
-
-static char *glyphname=NULL;
-
-static void SOError(const char *format,...) {
- va_list ap;
- va_start(ap,format);
- if ( glyphname==NULL )
- fprintf(stderr, "Internal Error (overlap): " );
- else
- fprintf(stderr, "Internal Error (overlap) in %s: ", glyphname );
- vfprintf(stderr,format,ap);
- va_end(ap);
-}
-
-#ifdef FF_OVERLAP_VERBOSE
-#define ValidateMListTs_IF_VERBOSE(input) ValidateMListTs(input);
-#else
-#define ValidateMListTs_IF_VERBOSE(input)
-#endif
-
-static void Validate(Monotonic *ms, Intersection *ilist) {
- MList *ml;
- int mcnt;
-
- while ( ilist!=NULL ) {
- // For each listed intersection, verify that each connected monotonic
- // starts or ends at the intersection (identified by pointer, not geography).
- for ( mcnt=0, ml=ilist->monos; ml!=NULL; ml=ml->next ) {
- if ( ml->m->isneeded ) ++mcnt;
- if ( ml->m->start!=ilist && ml->m->end!=ilist )
- SOError( "Intersection (%g,%g) not on a monotonic which should contain it.\n",
- (double) ilist->inter.x, (double) ilist->inter.y );
- }
- if ( mcnt&1 )
- SOError( "Odd number of needed monotonic sections at intersection. (%g,%g)\n",
- (double) ilist->inter.x,(double) ilist->inter.y );
- ilist = ilist->next;
- }
-
- while ( ms!=NULL ) {
- if ( ms->prev == NULL )
- SOError( "Open monotonic loop.\n" );
- else if ( ms->prev->end!=ms->start )
- SOError( "Mismatched intersection.\n (%g,%g)->(%g,%g) ends at (%g,%g) while (%g,%g)->(%g,%g) starts at (%g,%g)\n",
- (double) ms->prev->s->from->me.x,(double) ms->prev->s->from->me.y,
- (double) ms->prev->s->to->me.x,(double) ms->prev->s->to->me.y,
- (double) (ms->prev->end!=NULL?ms->prev->end->inter.x:-999999), (double) (ms->prev->end!=NULL?ms->prev->end->inter.y:-999999),
- (double) ms->s->from->me.x,(double) ms->s->from->me.y,
- (double) ms->s->to->me.x,(double) ms->s->to->me.y,
- (double) (ms->start!=NULL?ms->start->inter.x:-999999), (double) (ms->start!=NULL?ms->start->inter.y:-999999) );
- ms = ms->linked;
- }
-}
-
-static Monotonic *SplineToMonotonic(Spline *s,extended startt,extended endt,
- Monotonic *last,int exclude) {
- Monotonic *m;
- BasePoint start, end;
-
- if ( startt==0 )
- start = s->from->me;
- else {
- start.x = ((s->splines[0].a*startt+s->splines[0].b)*startt+s->splines[0].c)*startt
- + s->splines[0].d;
- start.y = ((s->splines[1].a*startt+s->splines[1].b)*startt+s->splines[1].c)*startt
- + s->splines[1].d;
- }
- if ( endt==1.0 )
- end = s->to->me;
- else {
- end.x = ((s->splines[0].a*endt+s->splines[0].b)*endt+s->splines[0].c)*endt
- + s->splines[0].d;
- end.y = ((s->splines[1].a*endt+s->splines[1].b)*endt+s->splines[1].c)*endt
- + s->splines[1].d;
- }
- if ( ( (real) (((start.x+end.x)/2)==start.x || (real) ((start.x+end.x)/2)==end.x) &&
- (real) (((start.y+end.y)/2)==start.y || (real) ((start.y+end.y)/2)==end.y) ) ||
- (endt <= startt) || Within4RoundingErrors(startt, endt)) {
- /* The distance between the two extrema is so small */
- /* as to be unobservable. In other words we'd end up with a zero*/
- /* length spline */
- if ( endt==1.0 && last!=NULL && last->s==s )
- last->tend = endt;
-return( last );
- }
-
- m = chunkalloc(sizeof(Monotonic));
- m->s = s;
- m->tstart = startt;
- m->tend = endt;
-#ifdef FF_RELATIONAL_GEOM
- m->otstart = startt;
- m->otend = endt;
-#endif
- m->exclude = exclude;
-
- if ( end.x>start.x ) {
- m->xup = true;
- m->b.minx = start.x;
- m->b.maxx = end.x;
- } else {
- m->b.minx = end.x;
- m->b.maxx = start.x;
- }
- if ( end.y>start.y ) {
- m->yup = true;
- m->b.miny = start.y;
- m->b.maxy = end.y;
- } else {
- m->b.miny = end.y;
- m->b.maxy = start.y;
- }
-
- if ( last!=NULL ) {
- // Validate(last, NULL);
- last->next = m;
- last->linked = m;
- m->prev = last;
- // Validate(last, NULL);
- }
-return( m );
-}
-
-
-static int BpSame(BasePoint *bp1, BasePoint *bp2) {
- BasePoint mid;
-
- mid.x = (bp1->x+bp2->x)/2; mid.y = (bp1->y+bp2->y)/2;
- if ( (bp1->x==mid.x || bp2->x==mid.x) &&
- (bp1->y==mid.y || bp2->y==mid.y))
-return( true );
-
-return( false );
-}
-
-static int SSRmNullSplines(SplineSet *spl) {
- Spline *s, *first, *next;
-
- first = NULL;
- for ( s=spl->first->next ; s!=first; s=next ) {
- next = s->to->next;
- if ( ((s->splines[0].a>-.01 && s->splines[0].a<.01 &&
- s->splines[0].b>-.01 && s->splines[0].b<.01 &&
- s->splines[1].a>-.01 && s->splines[1].a<.01 &&
- s->splines[1].b>-.01 && s->splines[1].b<.01) ||
- /* That describes a null spline (a line between the same end-point) */
- RealNear((s->from->nextcp.x-s->from->me.x)*(s->to->me.y-s->to->prevcp.y)-
- (s->from->nextcp.y-s->from->me.y)*(s->to->me.x-s->to->prevcp.x),0)) &&
- /* And the above describes a point with a spline between it */
- /* and itself where the spline covers no area (the two cps */
- /* point in the same direction) */
- BpSame(&s->from->me,&s->to->me)) {
- if ( next==s )
-return( true );
- if ( next->from->selected ) s->from->selected = true;
- s->from->next = next;
- s->from->nextcp = next->from->nextcp;
- s->from->nonextcp = next->from->nonextcp;
- s->from->nextcpdef = next->from->nextcpdef;
- SplinePointFree(next->from);
- if ( spl->first==next->from )
- spl->last = spl->first = s->from;
- next->from = s->from;
- SplineFree(s);
- } else {
- if ( first==NULL )
- first = s;
- }
- }
-return( false );
-}
-
-static Monotonic *SSToMContour(SplineSet *spl, Monotonic *start,
- Monotonic **end, enum overlap_type ot) {
- extended ts[4];
- Spline *first, *s;
- Monotonic *head=NULL, *last=NULL;
- int cnt, i, selected = false;
- extended lastt;
-
- if ( spl->first->prev==NULL )
-return( start ); /* Open contours have no interior, ignore 'em */
- if ( spl->first->prev->from==spl->first &&
- spl->first->noprevcp && spl->first->nonextcp )
-return( start ); /* Let's just remove single points */
-
- if ( ot==over_rmselected || ot==over_intersel || ot==over_fisel ) {
- if ( !selected )
- return( start );
- }
-
- /* We blow up on zero length splines. And a zero length contour is nasty */
- if ( SSRmNullSplines(spl))
-return( start );
-
- first = NULL;
- for ( s=spl->first->next; s!=first; s=s->to->next ) {
- if ( first==NULL ) first = s;
- cnt = Spline2DFindExtrema(s,ts);
- lastt = 0;
- for ( i=0; i<cnt; ++i ) {
- last = SplineToMonotonic(s,lastt,ts[i],last,selected);
- if ( head==NULL ) head = last;
- lastt=ts[i];
- }
- if ( lastt!=1.0 ) {
- last = SplineToMonotonic(s,lastt,1.0,last,selected);
- if ( head==NULL ) head = last;
- }
- }
- head->prev = last;
- last->next = head;
- if ( start==NULL )
- start = head;
- else
- (*end)->linked = head;
- *end = last;
- Validate(start, NULL);
-return( start );
-}
-
-Monotonic *SSsToMContours(SplineSet *spl, enum overlap_type ot) {
- Monotonic *head=NULL, *last = NULL;
-
- while ( spl!=NULL ) {
- if ( spl->first->prev!=NULL )
- head = SSToMContour(spl,head,&last,ot);
- spl = spl->next;
- }
-return( head );
-}
-
-/* An IEEE double has 52 bits of precision. So one unit of rounding error will be */
-/* the number divided by 2^51 */
-# define BR_RE_Factor (1024.0*1024.0*1024.0*1024.0*1024.0*2.0)
-/* But that's not going to work near 0, so, since the t values we care about */
-/* are [0,1], let's use 1.0/D_RE_Factor */
-
-#ifdef FF_OVERLAP_VERBOSE
-#define FF_DUMP_MONOTONIC_IF_VERBOSE(m) DumpMonotonic(m);
-#else
-#define FF_DUMP_MONOTONIC_IF_VERBOSE(m)
-#endif
-
-static int mcmp(const void *_p1, const void *_p2) {
- const Monotonic * const *mpt1 = _p1, * const *mpt2 = _p2;
- if ( (*mpt1)->other>(*mpt2)->other )
-return( 1 );
- else if ( (*mpt1)->other<(*mpt2)->other )
-return( -1 );
-
-return( 0 );
-}
-
-int CheckMonotonicClosed(struct monotonic *ms) {
- struct monotonic * current;
- if (ms == NULL) return 0;
- current = ms->next;
- while (current != ms && current != NULL) {
- current = current->next;
- }
- if (current == NULL) return 0;
- return 1;
-}
-
-int MonotonicFindAt(Monotonic *ms,int which, extended test, Monotonic **space ) {
- /* Find all monotonic sections which intersect the line (x,y)[which] == test */
- /* find the value of the other coord on that line */
- /* Order them (by the other coord) */
- /* then run along that line figuring out which monotonics are needed */
- extended t;
- Monotonic *m, *mm;
- int i, j, k, cnt;
- int nw = !which;
-
- for ( m=ms, i=0; m!=NULL; m=m->linked ) {
- if (CheckMonotonicClosed(m) == 0) continue; // Open monotonics break things.
- if (( which==0 && test >= m->b.minx && test <= m->b.maxx ) ||
- ( which==1 && test >= m->b.miny && test <= m->b.maxy )) {
- /* Lines parallel to the direction we are testing just get in the */
- /* way and don't add any useful info */
- if ( m->s->knownlinear &&
- (( which==1 && m->s->from->me.y==m->s->to->me.y ) ||
- (which==0 && m->s->from->me.x==m->s->to->me.x)))
- continue;
- t = IterateSplineSolveFixup(&m->s->splines[which],m->tstart,m->tend,test);
- if ( t==-1 ) {
- if ( which==0 ) {
- if (( test-m->b.minx > m->b.maxx-test && m->xup ) ||
- ( test-m->b.minx < m->b.maxx-test && !m->xup ))
- t = m->tstart;
- else
- t = m->tend;
- } else {
- if (( test-m->b.miny > m->b.maxy-test && m->yup ) ||
- ( test-m->b.miny < m->b.maxy-test && !m->yup ))
- t = m->tstart;
- else
- t = m->tend;
- }
- }
- m->t = t;
- if ( t==m->tend ) t -= (m->tend-m->tstart)/100;
- else if ( t==m->tstart ) t += (m->tend-m->tstart)/100;
- m->other = ((m->s->splines[nw].a*t+m->s->splines[nw].b)*t+
- m->s->splines[nw].c)*t+m->s->splines[nw].d;
- space[i++] = m;
- }
- }
- cnt = i;
-
- /* Things get a little tricky at end-points */
- for ( i=0; i<cnt; ++i ) {
- m = space[i];
- if ( m->t==m->tend ) {
- /* Ignore horizontal/vertical lines (as appropriate) */
- for ( mm=m->next; mm!=m && mm !=NULL; mm=mm->next ) {
- if ( !mm->s->knownlinear )
- break;
- if (( which==1 && mm->s->from->me.y!=m->s->to->me.y ) ||
- (which==0 && mm->s->from->me.x!=m->s->to->me.x))
- break;
- }
- } else if ( m->t==m->tstart ) {
- for ( mm=m->prev; mm!=m && mm !=NULL; mm=mm->prev ) {
- if ( !mm->s->knownlinear )
- break;
- if (( which==1 && mm->s->from->me.y!=m->s->to->me.y ) ||
- (which==0 && mm->s->from->me.x!=m->s->to->me.x))
- break;
- }
- } else
- break;
- /* If the next monotonic continues in the same direction, and we found*/
- /* it too, then don't count both. They represent the same intersect */
- /* If they are in oposite directions then they cancel each other out */
- /* and that is correct */
- if ( mm!=m && /* Should always be true */
- (&mm->xup)[which]==(&m->xup)[which] ) {
- for ( j=cnt-1; j>=0; --j )
- if ( space[j]==mm )
- break;
- if ( j!=-1 ) {
- /* remove mm */
- for ( k=j+1; k<cnt; ++k )
- space[k-1] = space[k];
- --cnt;
- if ( i>j ) --i;
- }
- }
- }
-
- space[cnt] = NULL; space[cnt+1] = NULL;
- qsort(space,cnt,sizeof(Monotonic *),mcmp);
-return(cnt);
-}
-
-void FreeMonotonics(Monotonic *m) {
- Monotonic *next;
-
- while ( m!=NULL ) {
- next = m->linked;
- chunkfree(m,sizeof(*m));
- m = next;
- }
-}