1 /* Copyright (C) 2000-2008 by George Williams */
3 * Redistribution and use in source and binary forms, with or without
4 * modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright notice, this
7 * list of conditions and the following disclaimer.
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.
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.
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.
28 #include "splinefont.h"
29 #include "edgelist2.h"
32 # include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */
36 /* First thing we do is divide each spline into a set of sub-splines each of */
37 /* which is monotonic in both x and y (always increasing or decreasing) */
38 /* Then we compare each monotonic spline with every other one and see if they*/
39 /* intersect. If they do, split each up into sub-sub-segments and create an*/
40 /* intersection point (note we need to be a little careful if an intersec- */
41 /* tion happens at an end point. We don't need to create a intersection for */
42 /* two adjacent splines, there isn't a real intersection... but if a third */
43 /* spline crosses that point (or ends there) then all three (four) splines */
44 /* need to be joined into an intersection point) */
45 /* Nasty things happen if splines are coincident. They will almost never be */
46 /* perfectly coincident and will keep crossing and recrossing as rounding */
47 /* errors suggest one is before the other. Look for coincident splines and */
48 /* treat the places they start and stop being coincident as intersections */
49 /* then when we find needed splines below look for these guys and ignore */
50 /* recrossings of splines which are close together */
51 /* Figure out if each monotonic sub-spline is needed or not */
52 /* (Note: It was tempting to split the bits up into real splines rather */
53 /* than keeping them as sub-sections of the original. Unfortunately this */
54 /* splitting introduced rounding errors which meant that we got more */
55 /* intersections, which meant that splines could be both needed and un. */
56 /* so I don't do that until later) */
57 /* if the spline hasn't been tagged yet: */
58 /* does the spline change greater in x or y? */
59 /* draw a line parallel to the OTHER axis which hits our spline and doesn't*/
60 /* hit any endpoints (or intersections, which are end points too now) */
61 /* count the winding number (as we do this we can mark other splines as */
62 /* needed or not) and figure out if our spline is needed */
63 /* So run through the list of intersections */
64 /* At an intersection there should be an even number of needed monos. */
65 /* Use this as the basis of a new splineset, trace it around until */
66 /* we get back to the start intersection (should happen) */
67 /* (Note: We may need to reverse a monotonic sub-spline or two) */
68 /* As we go, mark each monotonic as having been used */
69 /* Keep doing this until all needed exits from all intersections have been */
71 /* The free up our temporary data structures, merge in any open splinesets */
72 /* free the old closed splinesets */
74 typedef struct mlist
{
76 Monotonic
*m
; /* May get slightly munched but will */
77 /* always have right spline. we fix when we need it */
84 typedef struct intersection
{
87 struct intersection
*next
;
90 static char *glyphname
=NULL
;
92 static void SOError(char *format
,...) {
95 if ( glyphname
==NULL
)
96 fprintf(stderr
, "Internal Error: " );
98 fprintf(stderr
, "Internal Error in %s: ", glyphname
);
99 vfprintf(stderr
,format
,ap
);
102 static Monotonic
*SplineToMonotonic(Spline
*s
,extended startt
,extended endt
,
103 Monotonic
*last
,int exclude
) {
105 BasePoint start
, end
;
107 start
.x
= ((s
->splines
[0].a
*startt
+s
->splines
[0].b
)*startt
+s
->splines
[0].c
)*startt
109 start
.y
= ((s
->splines
[1].a
*startt
+s
->splines
[1].b
)*startt
+s
->splines
[1].c
)*startt
111 end
.x
= ((s
->splines
[0].a
*endt
+s
->splines
[0].b
)*endt
+s
->splines
[0].c
)*endt
113 end
.y
= ((s
->splines
[1].a
*endt
+s
->splines
[1].b
)*endt
+s
->splines
[1].c
)*endt
115 if ( (real
) (((start
.x
+end
.x
)/2)==start
.x
|| (real
) ((start
.x
+end
.x
)/2)==end
.x
) &&
116 (real
) (((start
.y
+end
.y
)/2)==start
.y
|| (real
) ((start
.y
+end
.y
)/2)==end
.y
) ) {
117 /* The distance between the two extrema is so small */
118 /* as to be unobservable. In other words we'd end up with a zero*/
120 if ( endt
==1.0 && last
!=NULL
&& last
->s
==s
)
125 m
= chunkalloc(sizeof(Monotonic
));
129 m
->exclude
= exclude
;
131 if ( end
.x
>start
.x
) {
139 if ( end
.y
>start
.y
) {
156 static int SSIsSelected(SplineSet
*spl
) {
159 for ( sp
=spl
->first
; ; ) {
162 if ( sp
->next
==NULL
)
165 if ( sp
==spl
->first
)
170 static int BpSame(BasePoint
*bp1
, BasePoint
*bp2
) {
173 mid
.x
= (bp1
->x
+bp2
->x
)/2; mid
.y
= (bp1
->y
+bp2
->y
)/2;
174 if ( (bp1
->x
==mid
.x
|| bp2
->x
==mid
.x
) &&
175 (bp1
->y
==mid
.y
|| bp2
->y
==mid
.y
))
181 static int SSRmNullSplines(SplineSet
*spl
) {
182 Spline
*s
, *first
, *next
;
185 for ( s
=spl
->first
->next
; s
!=first
; s
=next
) {
187 if ( ((s
->splines
[0].a
>-.01 && s
->splines
[0].a
<.01 &&
188 s
->splines
[0].b
>-.01 && s
->splines
[0].b
<.01 &&
189 s
->splines
[1].a
>-.01 && s
->splines
[1].a
<.01 &&
190 s
->splines
[1].b
>-.01 && s
->splines
[1].b
<.01) ||
191 /* That describes a null spline (a line between the same end-point) */
192 RealNear((s
->from
->nextcp
.x
-s
->from
->me
.x
)*(s
->to
->me
.y
-s
->to
->prevcp
.y
)-
193 (s
->from
->nextcp
.y
-s
->from
->me
.y
)*(s
->to
->me
.x
-s
->to
->prevcp
.x
),0)) &&
194 /* And the above describes a point with a spline between it */
195 /* and itself where the spline covers no area (the two cps */
196 /* point in the same direction) */
197 BpSame(&s
->from
->me
,&s
->to
->me
)) {
200 if ( next
->from
->selected
) s
->from
->selected
= true;
201 s
->from
->next
= next
;
202 s
->from
->nextcp
= next
->from
->nextcp
;
203 s
->from
->nonextcp
= next
->from
->nonextcp
;
204 s
->from
->nextcpdef
= next
->from
->nextcpdef
;
205 SplinePointFree(next
->from
);
206 if ( spl
->first
==next
->from
)
207 spl
->last
= spl
->first
= s
->from
;
208 next
->from
= s
->from
;
218 static Monotonic
*SSToMContour(SplineSet
*spl
, Monotonic
*start
,
219 Monotonic
**end
, enum overlap_type ot
) {
222 Monotonic
*head
=NULL
, *last
=NULL
;
223 int cnt
, i
, selected
= false;
226 if ( spl
->first
->prev
==NULL
)
227 return( start
); /* Open contours have no interior, ignore 'em */
228 if ( spl
->first
->prev
->from
==spl
->first
&&
229 spl
->first
->noprevcp
&& spl
->first
->nonextcp
)
230 return( start
); /* Let's just remove single points */
232 if ( ot
==over_rmselected
|| ot
==over_intersel
|| ot
==over_fisel
|| ot
==over_exclude
) {
233 selected
= SSIsSelected(spl
);
234 if ( ot
==over_rmselected
|| ot
==over_intersel
|| ot
==over_fisel
) {
241 /* We blow up on zero length splines. And a zero length contour is nasty */
242 if ( SSRmNullSplines(spl
))
246 for ( s
=spl
->first
->next
; s
!=first
; s
=s
->to
->next
) {
247 if ( first
==NULL
) first
= s
;
248 cnt
= Spline2DFindExtrema(s
,ts
);
250 for ( i
=0; i
<cnt
; ++i
) {
251 last
= SplineToMonotonic(s
,lastt
,ts
[i
],last
,selected
);
252 if ( head
==NULL
) head
= last
;
256 last
= SplineToMonotonic(s
,lastt
,1.0,last
,selected
);
257 if ( head
==NULL
) head
= last
;
265 (*end
)->linked
= head
;
270 static Monotonic
*SSsToMContours(SplineSet
*spl
, enum overlap_type ot
) {
271 Monotonic
*head
=NULL
, *last
= NULL
;
273 while ( spl
!=NULL
) {
274 if ( spl
->first
->prev
!=NULL
)
275 head
= SSToMContour(spl
,head
,&last
,ot
);
281 static void _AddSpline(Intersection
*il
,Monotonic
*m
,extended t
,int isend
) {
284 for ( ml
=il
->monos
; ml
!=NULL
; ml
=ml
->next
) {
285 if ( ml
->s
==m
->s
&& RealNear( ml
->t
,t
) && ml
->isend
==isend
)
289 ml
= chunkalloc(sizeof(MList
));
290 ml
->next
= il
->monos
;
293 ml
->m
= m
; /* This may change. We'll fix it up later */
297 if ( m
->end
!=NULL
&& m
->end
!=il
)
298 SOError("Resetting end.\n");
301 if ( m
->start
!=NULL
&& m
->start
!=il
)
302 SOError("Resetting start.\n");
308 static void AddSpline(Intersection
*il
,Monotonic
*m
,extended t
) {
311 if ( m
->start
==il
|| m
->end
==il
)
314 for ( ml
=il
->monos
; ml
!=NULL
; ml
=ml
->next
) {
315 if ( ml
->s
==m
->s
&& RealWithin( ml
->t
,t
,.0001 ))
319 ml
= chunkalloc(sizeof(MList
));
320 ml
->next
= il
->monos
;
323 ml
->m
= m
; /* This may change. We'll fix it up later */
326 if ( t
-m
->tstart
< m
->tend
-t
&& RealNear(m
->tstart
,t
) ) {
327 if ( m
->start
!=NULL
&& m
->start
!=il
)
328 SOError("Resetting start.\n");
332 _AddSpline(il
,m
->prev
,m
->prev
->tend
,true);
333 } else if ( RealNear(m
->tend
,t
)) {
334 if ( m
->end
!=NULL
&& m
->end
!=il
)
335 SOError("Resetting end.\n");
338 _AddSpline(il
,m
->next
,m
->next
->tstart
,false);
340 /* Ok, if we've got a new intersection on this spline then break up */
341 /* the monotonic into two bits which end and start at this inter */
342 if ( t
<m
->tstart
|| t
>m
->tend
)
343 SOError( "Attempt to subset monotonic rejoin inappropriately: %g should be [%g,%g]\n",
344 t
, m
->tstart
, m
->tend
);
346 /* It is monotonic, so a subset of it must also be */
347 Monotonic
*m2
= chunkalloc(sizeof(Monotonic
));
358 pt
.x
= ((m
->s
->splines
[0].a
*m
->tstart
+m
->s
->splines
[0].b
)*m
->tstart
+
359 m
->s
->splines
[0].c
)*m
->tstart
+m
->s
->splines
[0].d
;
360 pt
.y
= ((m
->s
->splines
[1].a
*m
->tstart
+m
->s
->splines
[1].b
)*m
->tstart
+
361 m
->s
->splines
[1].c
)*m
->tstart
+m
->s
->splines
[1].d
;
362 if ( pt
.x
>il
->inter
.x
) {
363 m
->b
.minx
= il
->inter
.x
;
367 m
->b
.maxx
= il
->inter
.x
;
369 if ( pt
.y
>il
->inter
.y
) {
370 m
->b
.miny
= il
->inter
.y
;
374 m
->b
.maxy
= il
->inter
.y
;
376 pt
.x
= ((m2
->s
->splines
[0].a
*m2
->tend
+m2
->s
->splines
[0].b
)*m2
->tend
+
377 m2
->s
->splines
[0].c
)*m2
->tend
+m2
->s
->splines
[0].d
;
378 pt
.y
= ((m2
->s
->splines
[1].a
*m2
->tend
+m2
->s
->splines
[1].b
)*m2
->tend
+
379 m2
->s
->splines
[1].c
)*m2
->tend
+m2
->s
->splines
[1].d
;
380 if ( pt
.x
>il
->inter
.x
) {
381 m2
->b
.minx
= il
->inter
.x
;
385 m2
->b
.maxx
= il
->inter
.x
;
387 if ( pt
.y
>il
->inter
.y
) {
388 m2
->b
.miny
= il
->inter
.y
;
392 m2
->b
.maxy
= il
->inter
.y
;
394 _AddSpline(il
,m2
,t
,false);
399 static void SetStartPoint(BasePoint
*pt
,Monotonic
*m
) {
401 *pt
= m
->s
->from
->me
;
402 else if ( m
->start
!=NULL
)
403 *pt
= m
->start
->inter
;
405 pt
->x
= ((m
->s
->splines
[0].a
*m
->tstart
+m
->s
->splines
[0].b
)*m
->tstart
+
406 m
->s
->splines
[0].c
)*m
->tstart
+ m
->s
->splines
[0].d
;
407 pt
->y
= ((m
->s
->splines
[1].a
*m
->tstart
+m
->s
->splines
[1].b
)*m
->tstart
+
408 m
->s
->splines
[1].c
)*m
->tstart
+ m
->s
->splines
[1].d
;
412 static void SetEndPoint(BasePoint
*pt
,Monotonic
*m
) {
415 else if ( m
->end
!=NULL
)
418 pt
->x
= ((m
->s
->splines
[0].a
*m
->tend
+m
->s
->splines
[0].b
)*m
->tend
+
419 m
->s
->splines
[0].c
)*m
->tend
+ m
->s
->splines
[0].d
;
420 pt
->y
= ((m
->s
->splines
[1].a
*m
->tend
+m
->s
->splines
[1].b
)*m
->tend
+
421 m
->s
->splines
[1].c
)*m
->tend
+ m
->s
->splines
[1].d
;
425 static extended
RoundToEndpoints(Monotonic
*m
,extended t
,BasePoint
*inter
) {
429 if ( t
==0 || t
==1 ) {
431 *inter
= m
->s
->from
->me
;
433 *inter
= m
->s
->to
->me
;
437 if ( t
-m
->tstart
< m
->tend
-t
) {
439 SetStartPoint(&end
,m
);
444 if ( BpSame(&end
,inter
) || RealWithin(t
,bound
,.00001)) {
452 static extended
Grad1(Spline1D
*s1
, Spline1D
*s2
,
453 extended t1
,extended t2
) {
454 /* d/dt[12] (m1(t1).x-m2(t2).x)^2 + (m1(t1).y-m2(t2).y)^2 */
455 /* d/dt[12] (m1(t1).x^2 -2m1(t1).x*m2(t2).x + m2(t2).x^2) + (m1(t1).y^2 -2m1(t1).y*m2(t2).y + m2(t2).y^2) */
456 extended val2
= ((s2
->a
*t2
+s2
->b
)*t2
+s2
->c
)*t2
+s2
->d
;
458 return( ((((6*(extended
)s1
->a
*s1
->a
*t1
+
459 5*2*(extended
)s1
->a
*s1
->b
)*t1
+
460 4*(s1
->b
*(extended
)s1
->b
+2*s1
->a
*(extended
)s1
->c
))*t1
+
461 3*2*(s1
->a
*(extended
)s1
->d
+s1
->b
*(extended
)s1
->c
))*t1
+
462 2*(s1
->c
*(extended
)s1
->c
+2*s1
->b
*(extended
)s1
->d
))*t1
+
463 2*s1
->c
*(extended
)s1
->d
-
464 2*val2
* ((3*s1
->a
*t1
+ 2*s1
->b
)*t1
+ s1
->c
) );
467 static void GradImproveInter(Monotonic
*m1
, Monotonic
*m2
,
468 extended
*_t1
,extended
*_t2
,BasePoint
*inter
) {
469 Spline
*s1
= m1
->s
, *s2
= m2
->s
;
470 extended x1
, x2
, y1
, y2
;
471 extended gt1
=0, gt2
=0, glen
=1;
472 extended error
, olderr
=1e10
;
473 extended factor
= 4096;
474 extended t1
=*_t1
, t2
=*_t2
;
475 extended off
, off2
, yoff
;
477 /* We want to find (t1,t2) so that (m1(t1)-m2(t2))^2==0 */
478 /* Find the gradiant and move in the reverse direction */
479 /* We know that the current values of (t1,t2) are close to an intersection*/
480 /* so the grad should point correctly */
481 /* d/dt[12] (m1(t1).x-m2(t2).x)^2 + (m1(t1).y-m2(t2).y)^2 */
482 /* d/dt[12] (m1(t1).x^2 -2m1(t1).x*m2(t2).x + m2(t2).x^2) + (m1(t1).y^2 -2m1(t1).y*m2(t2).y + m2(t2).y^2) */
485 x1
= ((s1
->splines
[0].a
*t1
+ s1
->splines
[0].b
)*t1
+ s1
->splines
[0].c
)*t1
+ s1
->splines
[0].d
;
486 x2
= ((s2
->splines
[0].a
*t2
+ s2
->splines
[0].b
)*t2
+ s2
->splines
[0].c
)*t2
+ s2
->splines
[0].d
;
487 y1
= ((s1
->splines
[1].a
*t1
+ s1
->splines
[1].b
)*t1
+ s1
->splines
[1].c
)*t1
+ s1
->splines
[1].d
;
488 y2
= ((s2
->splines
[1].a
*t2
+ s2
->splines
[1].b
)*t2
+ s2
->splines
[1].c
)*t2
+ s2
->splines
[1].d
;
489 error
= (x1
-x2
)*(x1
-x2
) + (y1
-y2
)*(y1
-y2
);
490 if ( error
>olderr
) {
494 if ( factor
>4096*4096 )
502 if ( error
<1e-11 ) /* Error is actually the square of the error */
503 break; /* So this isn't as constraining as it looks */
505 gt1
= Grad1(&s1
->splines
[0],&s2
->splines
[0],t1
,t2
) + Grad1(&s1
->splines
[1],&s2
->splines
[1],t1
,t2
);
506 gt2
= Grad1(&s2
->splines
[0],&s1
->splines
[0],t2
,t1
) + Grad1(&s2
->splines
[1],&s1
->splines
[1],t2
,t1
);
507 glen
= esqrt(gt1
*gt1
+ gt2
*gt2
) * factor
;
510 *_t1
= t1
; *_t2
= t2
;
513 if ( isnan(t1
) || isnan(t2
)) {
514 IError( "Nan in grad" );
523 if ( cnt
<=1 && error
>=1e-11 )
524 fprintf(stderr
,"No Improvement\n" );
526 fprintf(stderr
,"Improvement\n" );
528 t1
= *_t1
; t2
= *_t2
;
529 if ( t1
<0 && t1
>-.00001 ) *_t1
= t1
= 0;
530 else if ( t1
>1 && t1
<1.00001 ) *_t1
= t1
= 1.0;
531 if ( t2
<0 && t2
>-.00001 ) *_t2
= t2
= 0;
532 else if ( t2
>1 && t2
<1.00001 ) *_t2
= t2
= 1.0;
533 x1
= ((s1
->splines
[0].a
*t1
+ s1
->splines
[0].b
)*t1
+ s1
->splines
[0].c
)*t1
+ s1
->splines
[0].d
;
534 x2
= ((s2
->splines
[0].a
*t2
+ s2
->splines
[0].b
)*t2
+ s2
->splines
[0].c
)*t2
+ s2
->splines
[0].d
;
535 y1
= ((s1
->splines
[1].a
*t1
+ s1
->splines
[1].b
)*t1
+ s1
->splines
[1].c
)*t1
+ s1
->splines
[1].d
;
536 y2
= ((s2
->splines
[1].a
*t2
+ s2
->splines
[1].b
)*t2
+ s2
->splines
[1].c
)*t2
+ s2
->splines
[1].d
;
537 inter
->x
= (x1
+x2
)/2; inter
->y
= (y1
+y2
)/2;
539 if ( (off
=x1
-x2
)<0 ) off
= -off
;
540 if ( (yoff
=y1
-y2
)<0 ) yoff
= -yoff
;
545 x1
= s1
->splines
[0].d
;
546 y1
= s1
->splines
[1].d
;
547 } else if ( t1
>.9999 ) {
549 x1
= s1
->splines
[0].a
+s1
->splines
[0].b
+s1
->splines
[0].c
+s1
->splines
[0].d
;
550 y1
= s1
->splines
[1].a
+s1
->splines
[1].b
+s1
->splines
[1].c
+s1
->splines
[1].d
;
554 x2
= s2
->splines
[0].d
;
555 y2
= s2
->splines
[1].d
;
556 } else if ( t2
>.9999 ) {
558 x2
= s2
->splines
[0].a
+s2
->splines
[0].b
+s2
->splines
[0].c
+s2
->splines
[0].d
;
559 y2
= s2
->splines
[1].a
+s2
->splines
[1].b
+s2
->splines
[1].c
+s2
->splines
[1].d
;
561 if ( (off2
=x1
-x2
)<0 ) off2
= -off2
;
562 if ( (yoff
=y1
-y2
)<0 ) yoff
= -yoff
;
565 *_t1
= t1
; *_t2
= t2
;
566 inter
->x
= (x1
+x2
)/2; inter
->y
= (y1
+y2
)/2;
570 static Intersection
*AddIntersection(Intersection
*ilist
,Monotonic
*m1
,
571 Monotonic
*m2
,extended t1
,extended t2
,BasePoint
*inter
) {
573 extended ot1
= t1
, ot2
= t2
;
575 /* Fixup some rounding errors */
576 GradImproveInter(m1
,m2
,&t1
,&t2
,inter
);
577 if ( t1
<m1
->tstart
|| t1
>m1
->tend
|| t2
<m2
->tstart
|| t2
>m2
->tend
)
580 t1
= RoundToEndpoints(m1
,t1
,inter
);
581 t2
= RoundToEndpoints(m2
,t2
,inter
);
582 t1
= RoundToEndpoints(m1
,t1
,inter
); /* Do it twice. rounding t2 can mean we now need to round t1 */
584 if (( m1
->s
->to
== m2
->s
->from
&& RealWithin(t1
,1.0,.01) && RealWithin(t2
,0,.01)) ||
585 ( m1
->s
->from
== m2
->s
->to
&& RealWithin(t1
,0,.01) && RealWithin(t2
,1.0,.01)))
588 if (( t1
==m1
->tstart
&& m1
->start
!=NULL
&&
589 (inter
->x
!=m1
->start
->inter
.x
|| inter
->y
!=m1
->start
->inter
.y
)) ||
590 ( t1
==m1
->tend
&& m1
->end
!=NULL
&&
591 (inter
->x
!=m1
->end
->inter
.x
|| inter
->y
!=m1
->end
->inter
.y
)))
593 if (( t2
==m2
->tstart
&& m2
->start
!=NULL
&&
594 (inter
->x
!=m2
->start
->inter
.x
|| inter
->y
!=m2
->start
->inter
.y
)) ||
595 ( t2
==m2
->tend
&& m2
->end
!=NULL
&&
596 (inter
->x
!=m2
->end
->inter
.x
|| inter
->y
!=m2
->end
->inter
.y
)))
599 /* The ordinary join of one spline to the next doesn't really count */
600 /* Or one monotonic sub-spline to the next either */
601 if (( m1
->next
==m2
&& RealNear(t1
,m1
->tend
) && RealNear(t2
,m2
->tstart
)) ||
602 (m2
->next
==m1
&& RealNear(t1
,m1
->tstart
) && RealNear(t2
,m2
->tend
)) )
605 if ( RealWithin(m1
->tstart
,t1
,.01) )
607 else if ( RealWithin(m1
->tend
,t1
,.01) )
612 ((RealWithin(m2
->tstart
,t2
,.01) && m2
->start
==il
) ||
613 (RealWithin(m2
->tend
,t2
,.01) && m2
->end
==il
)) )
616 for ( il
= ilist
; il
!=NULL
; il
=il
->next
) {
617 if ( RealWithin(il
->inter
.x
,inter
->x
,.01) && RealWithin(il
->inter
.y
,inter
->y
,.01)) {
624 il
= chunkalloc(sizeof(Intersection
));
632 static extended
BoundIterateSplineSolve(Spline1D
*sp
, extended tmin
, extended tmax
,
633 extended sought
,double err
) {
634 extended t
= IterateSplineSolve(sp
,tmin
,tmax
,sought
,err
);
635 if ( t
<tmin
|| t
>tmax
)
641 static Intersection
*FindMonotonicIntersection(Intersection
*ilist
,Monotonic
*m1
,Monotonic
*m2
) {
642 /* I believe that two monotonic cubics can still intersect in two points */
643 /* so we can't just check if the splines are on oposite sides of each */
644 /* other at top and bottom */
646 const double error
= .0001;
650 b
.minx
= m1
->b
.minx
>m2
->b
.minx
? m1
->b
.minx
: m2
->b
.minx
;
651 b
.maxx
= m1
->b
.maxx
<m2
->b
.maxx
? m1
->b
.maxx
: m2
->b
.maxx
;
652 b
.miny
= m1
->b
.miny
>m2
->b
.miny
? m1
->b
.miny
: m2
->b
.miny
;
653 b
.maxy
= m1
->b
.maxy
<m2
->b
.maxy
? m1
->b
.maxy
: m2
->b
.maxy
;
655 if ( b
.maxy
==b
.miny
&& b
.minx
==b
.maxx
) {
656 extended x1
,y1
, x2
,y2
;
657 if ( m1
->next
==m2
|| m2
->next
==m1
)
658 return( ilist
); /* Not interesting. Only intersection is at an endpoint */
659 if ( ((m1
->start
==m2
->start
|| m1
->end
==m2
->start
) && m2
->start
!=NULL
) ||
660 ((m1
->start
==m2
->end
|| m1
->end
==m2
->end
) && m2
->end
!=NULL
))
662 pt
.x
= b
.minx
; pt
.y
= b
.miny
;
663 if ( m1
->b
.maxx
-m1
->b
.minx
> m1
->b
.maxy
-m1
->b
.miny
)
664 t1
= BoundIterateSplineSolve(&m1
->s
->splines
[0],m1
->tstart
,m1
->tend
,b
.minx
,error
);
666 t1
= BoundIterateSplineSolve(&m1
->s
->splines
[1],m1
->tstart
,m1
->tend
,b
.miny
,error
);
667 if ( m2
->b
.maxx
-m2
->b
.minx
> m2
->b
.maxy
-m2
->b
.miny
)
668 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[0],m2
->tstart
,m2
->tend
,b
.minx
,error
);
670 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[1],m2
->tstart
,m2
->tend
,b
.miny
,error
);
671 if ( t1
!=-1 && t2
!=-1 ) {
672 x1
= ((m1
->s
->splines
[0].a
*t1
+m1
->s
->splines
[0].b
)*t1
+m1
->s
->splines
[0].c
)*t1
+m1
->s
->splines
[0].d
;
673 y1
= ((m1
->s
->splines
[1].a
*t1
+m1
->s
->splines
[1].b
)*t1
+m1
->s
->splines
[1].c
)*t1
+m1
->s
->splines
[1].d
;
674 x2
= ((m2
->s
->splines
[0].a
*t2
+m2
->s
->splines
[0].b
)*t2
+m2
->s
->splines
[0].c
)*t2
+m2
->s
->splines
[0].d
;
675 y2
= ((m2
->s
->splines
[1].a
*t2
+m2
->s
->splines
[1].b
)*t2
+m2
->s
->splines
[1].c
)*t2
+m2
->s
->splines
[1].d
;
676 if ( x1
-x2
>-.01 && x1
-x2
<.01 && y1
-y2
>-.01 && y1
-y2
<.01 )
677 ilist
= AddIntersection(ilist
,m1
,m2
,t1
,t2
,&pt
);
679 } else if ( b
.maxy
==b
.miny
) {
681 if ( m1
->next
==m2
|| m2
->next
==m1
)
682 return( ilist
); /* Not interesting. Only intersection is at an endpoint */
683 t1
= BoundIterateSplineSolve(&m1
->s
->splines
[1],m1
->tstart
,m1
->tend
,b
.miny
,error
);
684 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[1],m2
->tstart
,m2
->tend
,b
.miny
,error
);
685 if ( t1
!=-1 && t2
!=-1 ) {
686 x1
= ((m1
->s
->splines
[0].a
*t1
+m1
->s
->splines
[0].b
)*t1
+m1
->s
->splines
[0].c
)*t1
+m1
->s
->splines
[0].d
;
687 x2
= ((m2
->s
->splines
[0].a
*t2
+m2
->s
->splines
[0].b
)*t2
+m2
->s
->splines
[0].c
)*t2
+m2
->s
->splines
[0].d
;
688 if ( x1
-x2
>-.01 && x1
-x2
<.01 ) {
689 pt
.x
= (x1
+x2
)/2; pt
.y
= b
.miny
;
690 ilist
= AddIntersection(ilist
,m1
,m2
,t1
,t2
,&pt
);
693 } else if ( b
.maxx
==b
.minx
) {
695 if ( m1
->next
==m2
|| m2
->next
==m1
)
696 return( ilist
); /* Not interesting. Only intersection is at an endpoint */
697 t1
= BoundIterateSplineSolve(&m1
->s
->splines
[0],m1
->tstart
,m1
->tend
,b
.minx
,error
);
698 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[0],m2
->tstart
,m2
->tend
,b
.minx
,error
);
699 if ( t1
!=-1 && t2
!=-1 ) {
700 y1
= ((m1
->s
->splines
[1].a
*t1
+m1
->s
->splines
[1].b
)*t1
+m1
->s
->splines
[1].c
)*t1
+m1
->s
->splines
[1].d
;
701 y2
= ((m2
->s
->splines
[1].a
*t2
+m2
->s
->splines
[1].b
)*t2
+m2
->s
->splines
[1].c
)*t2
+m2
->s
->splines
[1].d
;
702 if ( y1
-y2
>-.01 && y1
-y2
<.01 ) {
703 pt
.x
= b
.minx
; pt
.y
= (y1
+y2
)/2;
704 ilist
= AddIntersection(ilist
,m1
,m2
,t1
,t2
,&pt
);
707 } else if ( b
.maxy
-b
.miny
> b
.maxx
-b
.minx
) {
708 extended diff
, y
, x1
,x2
, x1o
,x2o
;
709 extended t1
,t2
, t1o
,t2o
;
711 diff
= (b
.maxy
-b
.miny
)/32;
716 t1o
= BoundIterateSplineSolve(&m1
->s
->splines
[1],m1
->tstart
,m1
->tend
,b
.miny
,error
);
717 t2o
= BoundIterateSplineSolve(&m2
->s
->splines
[1],m2
->tstart
,m2
->tend
,b
.miny
,error
);
718 if ( t1o
!=-1 && t2o
!=-1 )
722 x1o
= ((m1
->s
->splines
[0].a
*t1o
+m1
->s
->splines
[0].b
)*t1o
+m1
->s
->splines
[0].c
)*t1o
+m1
->s
->splines
[0].d
;
723 x2o
= ((m2
->s
->splines
[0].a
*t2o
+m2
->s
->splines
[0].b
)*t2o
+m2
->s
->splines
[0].c
)*t2o
+m2
->s
->splines
[0].d
;
728 for ( y
+=diff
; ; y
+= diff
) {
729 /* I used to say y<=b.maxy in the above for statement. */
730 /* that seemed to get rounding errors on the mac, so we do it */
733 if ( y
<b
.maxy
+diff
/4 ) y
= b
.maxy
;
737 t1
= BoundIterateSplineSolve(&m1
->s
->splines
[1],m1
->tstart
,m1
->tend
,y
,error
);
738 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[1],m2
->tstart
,m2
->tend
,y
,error
);
739 if ( t1
==-1 || t2
==-1 )
741 x1
= ((m1
->s
->splines
[0].a
*t1
+m1
->s
->splines
[0].b
)*t1
+m1
->s
->splines
[0].c
)*t1
+m1
->s
->splines
[0].d
;
742 x2
= ((m2
->s
->splines
[0].a
*t2
+m2
->s
->splines
[0].b
)*t2
+m2
->s
->splines
[0].c
)*t2
+m2
->s
->splines
[0].d
;
743 if ( x1o
!=x2o
&& (x1o
>x2o
) != ( x1
>x2
) ) {
744 /* A cross over has occured. (assume we have a small enough */
745 /* region that three cross-overs can't have occurred) */
746 /* Use a binary search to track it down */
750 while ( ytop
!=ybot
) {
751 extended ytest
= (ytop
+ybot
)/2;
753 t1t
= BoundIterateSplineSolve(&m1
->s
->splines
[1],m1
->tstart
,m1
->tend
,ytest
,error
);
754 t2t
= BoundIterateSplineSolve(&m2
->s
->splines
[1],m2
->tstart
,m2
->tend
,ytest
,error
);
755 x1
= ((m1
->s
->splines
[0].a
*t1t
+m1
->s
->splines
[0].b
)*t1t
+m1
->s
->splines
[0].c
)*t1t
+m1
->s
->splines
[0].d
;
756 x2
= ((m2
->s
->splines
[0].a
*t2t
+m2
->s
->splines
[0].b
)*t2t
+m2
->s
->splines
[0].c
)*t2t
+m2
->s
->splines
[0].d
;
757 if ( t1t
==-1 || t2t
==-1 ) {
758 SOError( "Can't find something in range.\n" );
760 } else if (( x1
-x2
<error
&& x1
-x2
>-error
) || ytop
==ytest
|| ybot
==ytest
) {
761 pt
.y
= ytest
; pt
.x
= (x1
+x2
)/2;
762 ilist
= AddIntersection(ilist
,m1
,m2
,t1t
,t2t
,&pt
);
763 b
.maxy
= m1
->b
.maxy
<m2
->b
.maxy
? m1
->b
.maxy
: m2
->b
.maxy
;
765 } else if ( (x1o
>x2o
) != ( x1
>x2
) ) {
771 x1
= x1o
; x1o
= x2o
; x2o
= x1
;
777 extended diff
, x
, y1
,y2
, y1o
,y2o
;
778 extended t1
,t2
, t1o
,t2o
;
780 diff
= (b
.maxx
-b
.minx
)/32;
785 t1o
= BoundIterateSplineSolve(&m1
->s
->splines
[0],m1
->tstart
,m1
->tend
,b
.minx
,error
);
786 t2o
= BoundIterateSplineSolve(&m2
->s
->splines
[0],m2
->tstart
,m2
->tend
,b
.minx
,error
);
787 if ( t1o
!=-1 && t2o
!=-1 )
791 y1o
= ((m1
->s
->splines
[1].a
*t1o
+m1
->s
->splines
[1].b
)*t1o
+m1
->s
->splines
[1].c
)*t1o
+m1
->s
->splines
[1].d
;
792 y2o
= ((m2
->s
->splines
[1].a
*t2o
+m2
->s
->splines
[1].b
)*t2o
+m2
->s
->splines
[1].c
)*t2o
+m2
->s
->splines
[1].d
;
798 for ( x
+=diff
; ; x
+= diff
) {
800 if ( x
<b
.maxx
+diff
/4 ) x
= b
.maxx
;
804 t1
= BoundIterateSplineSolve(&m1
->s
->splines
[0],m1
->tstart
,m1
->tend
,x
,error
);
805 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[0],m2
->tstart
,m2
->tend
,x
,error
);
806 if ( t1
==-1 || t2
==-1 )
808 y1
= ((m1
->s
->splines
[1].a
*t1
+m1
->s
->splines
[1].b
)*t1
+m1
->s
->splines
[1].c
)*t1
+m1
->s
->splines
[1].d
;
809 y2
= ((m2
->s
->splines
[1].a
*t2
+m2
->s
->splines
[1].b
)*t2
+m2
->s
->splines
[1].c
)*t2
+m2
->s
->splines
[1].d
;
810 if ( (y1o
>y2o
) != ( y1
>y2
) ) {
811 /* A cross over has occured. (assume we have a small enough */
812 /* region that three cross-overs can't have occurred) */
813 /* Use a binary search to track it down */
817 while ( xtop
!=xbot
) {
818 extended xtest
= (xtop
+xbot
)/2;
820 t1t
= BoundIterateSplineSolve(&m1
->s
->splines
[0],m1
->tstart
,m1
->tend
,xtest
,error
);
821 t2t
= BoundIterateSplineSolve(&m2
->s
->splines
[0],m2
->tstart
,m2
->tend
,xtest
,error
);
822 y1
= ((m1
->s
->splines
[1].a
*t1t
+m1
->s
->splines
[1].b
)*t1t
+m1
->s
->splines
[1].c
)*t1t
+m1
->s
->splines
[1].d
;
823 y2
= ((m2
->s
->splines
[1].a
*t2t
+m2
->s
->splines
[1].b
)*t2t
+m2
->s
->splines
[1].c
)*t2t
+m2
->s
->splines
[1].d
;
824 if ( t1t
==-1 || t2t
==-1 ) {
825 SOError( "Can't find something in range.\n" );
827 } else if (( y1
-y2
<error
&& y1
-y2
>-error
) || xtop
==xtest
|| xbot
==xtest
) {
828 pt
.x
= xtest
; pt
.y
= (y1
+y2
)/2;
829 ilist
= AddIntersection(ilist
,m1
,m2
,t1t
,t2t
,&pt
);
830 b
.maxx
= m1
->b
.maxx
<m2
->b
.maxx
? m1
->b
.maxx
: m2
->b
.maxx
;
832 } else if ( (y1o
>y2o
) != ( y1
>y2
) ) {
838 y1
= y1o
; y1o
= y2o
; y2o
= y1
;
848 static extended
SplineContainsPoint(Monotonic
*m
,BasePoint
*pt
) {
852 const double error
= .0001;
854 which
= ( m
->b
.maxx
-m
->b
.minx
> m
->b
.maxy
-m
->b
.miny
)? 0 : 1;
856 t
= BoundIterateSplineSolve(&m
->s
->splines
[which
],m
->tstart
,m
->tend
,(&pt
->x
)[which
],error
);
857 if ( (slope
.x
= (3*m
->s
->splines
[0].a
*t
+2*m
->s
->splines
[0].b
)*t
+m
->s
->splines
[0].c
)<0 )
859 if ( (slope
.y
= (3*m
->s
->splines
[1].a
*t
+2*m
->s
->splines
[1].b
)*t
+m
->s
->splines
[1].c
)<0 )
861 if ( t
==-1 || (slope
.y
>slope
.x
)!=which
) {
864 t
= BoundIterateSplineSolve(&m
->s
->splines
[which
],m
->tstart
,m
->tend
,(&pt
->x
)[which
],error
);
866 if ( t
!=-1 && RealWithin((&pt
->x
)[nw
],
867 ((m
->s
->splines
[nw
].a
*t
+m
->s
->splines
[nw
].b
)*t
+
868 m
->s
->splines
[nw
].c
)*t
+ m
->s
->splines
[nw
].d
,.1 ))
874 /* If two splines are coincident, then pretend they intersect at both */
875 /* end-points and nowhere else */
876 static int CoincidentIntersect(Monotonic
*m1
,Monotonic
*m2
,BasePoint
*pts
,
877 extended
*t1s
,extended
*t2s
) {
878 const double error
= .0001;
880 extended t
, t2
, diff
;
882 if ( m1
==m2
|| m1
->next
==m2
|| m1
->prev
==m2
)
883 return( false ); /* Can't be coincident. Adjacent */
884 /* Actually adjacent splines can double back on themselves */
886 if ( (m1
->xup
==m2
->xup
&& m1
->yup
==m2
->yup
) ||
887 ((m1
->xup
!=m2
->xup
|| (m1
->b
.minx
==m1
->b
.maxx
&& m2
->b
.minx
==m2
->b
.maxx
)) ||
888 (m1
->yup
!=m2
->yup
|| (m1
->b
.miny
==m1
->b
.maxy
&& m2
->b
.miny
==m2
->b
.maxy
))))
889 /* A match is possible */;
893 SetStartPoint(&pts
[cnt
],m1
);
894 t1s
[cnt
] = m1
->tstart
;
895 if ( (t2s
[cnt
] = SplineContainsPoint(m2
,&pts
[cnt
]))!=-1 )
898 SetEndPoint(&pts
[cnt
],m1
);
900 if ( (t2s
[cnt
] = SplineContainsPoint(m2
,&pts
[cnt
]))!=-1 )
904 SetStartPoint(&pts
[cnt
],m2
);
905 t2s
[cnt
] = m2
->tstart
;
906 if ( (t1s
[cnt
] = SplineContainsPoint(m1
,&pts
[cnt
]))!=-1 )
911 SetEndPoint(&pts
[cnt
],m2
);
913 if ( (t1s
[cnt
] = SplineContainsPoint(m1
,&pts
[cnt
]))!=-1 )
920 if ( RealWithin(t1s
[0],t1s
[1],.01) )
923 /* Ok, if we've gotten this far we know that two of the end points are */
924 /* on both splines. */
925 t1s
[2] = t2s
[2] = -1;
926 if ( !m1
->s
->knownlinear
|| !m1
->s
->knownlinear
) {
927 if ( t1s
[1]<t1s
[0] ) {
928 extended temp
= t1s
[1]; t1s
[1] = t1s
[0]; t1s
[0] = temp
;
929 temp
= t2s
[1]; t2s
[1] = t2s
[0]; t2s
[0] = temp
;
931 diff
= (t1s
[1]-t1s
[0])/16;
932 for ( t
=t1s
[0]+diff
; t
<t1s
[1]-diff
/4; t
+= diff
) {
933 BasePoint here
, slope
;
934 here
.x
= ((m1
->s
->splines
[0].a
*t
+m1
->s
->splines
[0].b
)*t
+m1
->s
->splines
[0].c
)*t
+m1
->s
->splines
[0].d
;
935 here
.y
= ((m1
->s
->splines
[1].a
*t
+m1
->s
->splines
[1].b
)*t
+m1
->s
->splines
[1].c
)*t
+m1
->s
->splines
[1].d
;
936 if ( (slope
.x
= (3*m1
->s
->splines
[0].a
*t
+2*m1
->s
->splines
[0].b
)*t
+m1
->s
->splines
[0].c
)<0 )
938 if ( (slope
.y
= (3*m1
->s
->splines
[1].a
*t
+2*m1
->s
->splines
[1].b
)*t
+m1
->s
->splines
[1].c
)<0 )
940 if ( slope
.y
>slope
.x
) {
941 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[1],t2s
[0],t2s
[1],here
.y
,error
);
942 if ( t2
==-1 || !RealWithin(here
.x
,((m2
->s
->splines
[0].a
*t2
+m2
->s
->splines
[0].b
)*t2
+m2
->s
->splines
[0].c
)*t2
+m2
->s
->splines
[0].d
,.1))
945 t2
= BoundIterateSplineSolve(&m2
->s
->splines
[0],t2s
[0],t2s
[1],here
.x
,error
);
946 if ( t2
==-1 || !RealWithin(here
.y
,((m2
->s
->splines
[1].a
*t2
+m2
->s
->splines
[1].b
)*t2
+m2
->s
->splines
[1].c
)*t2
+m2
->s
->splines
[1].d
,.1))
955 static void FigureProperMonotonicsAtIntersections(Intersection
*ilist
) {
956 MList
*ml
, *ml2
, *mlnext
, *prev
, *p2
;
958 while ( ilist
!=NULL
) {
959 for ( ml
=ilist
->monos
; ml
!=NULL
; ml
=ml
->next
) {
960 if ( (ml
->t
==ml
->m
->tstart
&& !ml
->isend
) ||
961 (ml
->t
==ml
->m
->tend
&& ml
->isend
))
963 else if ( ml
->t
>ml
->m
->tstart
) {
964 while ( ml
->t
>ml
->m
->tend
) {
966 if ( ml
->m
->s
!=ml
->s
) {
967 SOError("we could not find a matching monotonic\n" );
972 while ( ml
->t
<ml
->m
->tstart
) {
974 if ( ml
->m
->s
!=ml
->s
) {
975 SOError( "we could not find a matching monotonic\n" );
980 if ( ml
->t
==ml
->m
->tstart
&& ml
->isend
)
982 else if ( ml
->t
==ml
->m
->tend
&& !ml
->isend
)
984 if ( ml
->t
!=ml
->m
->tstart
&& ml
->t
!=ml
->m
->tend
)
985 SOError( "we could not find a matching monotonic time\n" );
987 for ( prev
=NULL
, ml
=ilist
->monos
; ml
!=NULL
; ml
= mlnext
) {
989 if ( ml
->m
->start
==ml
->m
->end
) {
990 for ( p2
= ml
, ml2
=ml
->next
; ml2
!=NULL
; p2
=ml2
, ml2
= ml2
->next
) {
995 if ( ml2
==mlnext
) mlnext
= ml2
->next
;
996 p2
->next
= ml2
->next
;
997 chunkfree(ml2
,sizeof(*ml2
));
1000 ilist
->monos
= mlnext
;
1002 prev
->next
= mlnext
;
1003 chunkfree(ml
,sizeof(*ml
));
1007 for ( ml
=ilist
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1011 if ( ml
->m
->start
== ilist
) {
1012 search
= ml
->m
->prev
;
1013 t
= ( ml
->m
->tstart
==0 ) ? 1.0 : ml
->m
->tstart
;
1015 search
= ml
->m
->next
;
1016 t
= ( ml
->m
->tend
==1.0 ) ? 0.0 : ml
->m
->tend
;
1018 for ( ml2
=ilist
->monos
; ml2
!=NULL
&& ml2
->m
!=search
; ml2
=ml2
->next
);
1020 ml2
= chunkalloc(sizeof(MList
));
1024 ml2
->next
= ml
->next
;
1030 ilist
= ilist
->next
;
1034 static void Validate(Monotonic
*ms
, Intersection
*ilist
) {
1038 while ( ilist
!=NULL
) {
1039 for ( mcnt
=0, ml
=ilist
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1040 if ( ml
->m
->isneeded
) ++mcnt
;
1041 if ( ml
->m
->start
!=ilist
&& ml
->m
->end
!=ilist
)
1042 SOError( "Intersection (%g,%g) not on a monotonic which should contain it.\n",
1043 ilist
->inter
.x
, ilist
->inter
.y
);
1046 SOError( "Odd number of needed monotonic sections at intersection. (%g,%g)\n",
1047 ilist
->inter
.x
,ilist
->inter
.y
);
1048 ilist
= ilist
->next
;
1051 while ( ms
!=NULL
) {
1052 if ( ms
->prev
->end
!=ms
->start
)
1053 SOError( "Mismatched intersection.\n");
1058 static Intersection
*FindIntersections(Monotonic
*ms
, enum overlap_type ot
) {
1061 extended t1s
[10], t2s
[10];
1062 Intersection
*ilist
=NULL
;
1066 for ( m1
=ms
; m1
!=NULL
; m1
=m1
->linked
) {
1067 for ( m2
=m1
->linked
; m2
!=NULL
; m2
=m2
->linked
) {
1068 if ( m2
->b
.minx
> m1
->b
.maxx
||
1069 m2
->b
.maxx
< m1
->b
.minx
||
1070 m2
->b
.miny
> m1
->b
.maxy
||
1071 m2
->b
.maxy
< m1
->b
.miny
)
1072 continue; /* Can't intersect */;
1073 wasc
= CoincidentIntersect(m1
,m2
,pts
,t1s
,t2s
);
1074 if ( wasc
|| m1
->s
->knownlinear
|| m2
->s
->knownlinear
||
1075 (m1
->s
->splines
[0].a
==0 && m1
->s
->splines
[1].a
==0 &&
1076 m2
->s
->splines
[0].a
==0 && m2
->s
->splines
[1].a
==0 )) {
1077 if ( !wasc
&& SplinesIntersect(m1
->s
,m2
->s
,pts
,t1s
,t2s
)<=0 )
1079 for ( i
=0; i
<4 && t1s
[i
]!=-1; ++i
) {
1080 if ( t1s
[i
]>=m1
->tstart
&& t1s
[i
]<=m1
->tend
&&
1081 t2s
[i
]>=m2
->tstart
&& t2s
[i
]<=m2
->tend
) {
1082 ilist
= AddIntersection(ilist
,m1
,m2
,t1s
[i
],t2s
[i
],&pts
[i
]);
1087 ilist
= FindMonotonicIntersection(ilist
,m1
,m2
);
1091 FigureProperMonotonicsAtIntersections(ilist
);
1093 /* Now suppose we have a contour which intersects nothing? */
1094 /* with no intersections we lose track of it and it will vanish */
1095 /* That's not a good idea. Make sure each contour has at least one inter */
1096 if ( ot
!=over_findinter
&& ot
!=over_fisel
) {
1097 for ( m1
=ms
; m1
!=NULL
; m1
=m2
->linked
) {
1098 if ( m1
->start
==NULL
&& m1
->end
==NULL
) {
1100 il
= chunkalloc(sizeof(Intersection
));
1101 il
->inter
= m1
->s
->from
->me
;
1104 AddSpline(il
,m1
->prev
,1.0);
1107 for ( m2
=m1
; m2
->linked
==m2
->next
; m2
=m2
->linked
);
1114 static int dcmp(const void *_p1
, const void *_p2
) {
1115 const extended
*dpt1
= _p1
, *dpt2
= _p2
;
1118 else if ( *dpt1
<*dpt2
)
1124 static extended
*FindOrderedEndpoints(Monotonic
*ms
,int which
) {
1130 for ( m
=ms
, cnt
=0; m
!=NULL
; m
=m
->linked
, ++cnt
);
1131 ends
= galloc((2*cnt
+1)*sizeof(extended
));
1132 for ( m
=ms
, cnt
=0; m
!=NULL
; m
=m
->linked
, cnt
+=2 ) {
1133 if ( m
->start
!=NULL
)
1134 ends
[cnt
] = (&m
->start
->inter
.x
)[which
];
1135 else if ( m
->tstart
==0 )
1136 ends
[cnt
] = (&m
->s
->from
->me
.x
)[which
];
1138 ends
[cnt
] = ((m
->s
->splines
[which
].a
*m
->tstart
+m
->s
->splines
[which
].b
)*m
->tstart
+
1139 m
->s
->splines
[which
].c
)*m
->tstart
+m
->s
->splines
[which
].d
;
1141 ends
[cnt
+1] = (&m
->end
->inter
.x
)[which
];
1142 else if ( m
->tend
==1.0 )
1143 ends
[cnt
+1] = (&m
->s
->to
->me
.x
)[which
];
1145 ends
[cnt
+1] = ((m
->s
->splines
[which
].a
*m
->tend
+m
->s
->splines
[which
].b
)*m
->tend
+
1146 m
->s
->splines
[which
].c
)*m
->tend
+m
->s
->splines
[which
].d
;
1149 qsort(ends
,cnt
,sizeof(extended
),dcmp
);
1150 for ( i
=0; i
<cnt
; ++i
) {
1151 for ( j
=i
; j
<cnt
&& ends
[i
]==ends
[j
]; ++j
);
1153 for ( k
=i
+1; j
<cnt
; ends
[k
++] = ends
[j
++]);
1161 static int mcmp(const void *_p1
, const void *_p2
) {
1162 const Monotonic
* const *mpt1
= _p1
, * const *mpt2
= _p2
;
1163 if ( (*mpt1
)->other
>(*mpt2
)->other
)
1165 else if ( (*mpt1
)->other
<(*mpt2
)->other
)
1171 static int MonotonicFindAt(Monotonic
*ms
,int which
, extended test
, Monotonic
**space
) {
1172 /* Find all monotonic sections which intersect the line (x,y)[which] == test */
1173 /* find the value of the other coord on that line */
1174 /* Order them (by the other coord) */
1175 /* then run along that line figuring out which monotonics are needed */
1179 const double error
= .0001;
1182 for ( m
=ms
, i
=0; m
!=NULL
; m
=m
->linked
) {
1183 if (( which
==0 && test
>= m
->b
.minx
&& test
<= m
->b
.maxx
) ||
1184 ( which
==1 && test
>= m
->b
.miny
&& test
<= m
->b
.maxy
)) {
1185 /* Lines parallel to the direction we are testing just get in the */
1186 /* way and don't add any useful info */
1187 if ( m
->s
->knownlinear
&&
1188 (( which
==1 && m
->s
->from
->me
.y
==m
->s
->to
->me
.y
) ||
1189 (which
==0 && m
->s
->from
->me
.x
==m
->s
->to
->me
.x
)))
1191 t
= BoundIterateSplineSolve(&m
->s
->splines
[which
],m
->tstart
,m
->tend
,test
,error
);
1195 if ( t
==m
->tend
) t
-= (m
->tend
-m
->tstart
)/100;
1196 else if ( t
==m
->tstart
) t
+= (m
->tend
-m
->tstart
)/100;
1197 m
->other
= ((m
->s
->splines
[nw
].a
*t
+m
->s
->splines
[nw
].b
)*t
+
1198 m
->s
->splines
[nw
].c
)*t
+m
->s
->splines
[nw
].d
;
1204 /* Things get a little tricky at end-points */
1205 for ( i
=0; i
<cnt
; ++i
) {
1207 if ( m
->t
==m
->tend
) {
1208 /* Ignore horizontal/vertical lines (as appropriate) */
1209 for ( mm
=m
->next
; mm
!=m
; mm
=mm
->next
) {
1210 if ( !mm
->s
->knownlinear
)
1212 if (( which
==1 && mm
->s
->from
->me
.y
!=m
->s
->to
->me
.y
) ||
1213 (which
==0 && mm
->s
->from
->me
.x
!=m
->s
->to
->me
.x
))
1216 } else if ( m
->t
==m
->tstart
) {
1217 for ( mm
=m
->prev
; mm
!=m
; mm
=mm
->prev
) {
1218 if ( !mm
->s
->knownlinear
)
1220 if (( which
==1 && mm
->s
->from
->me
.y
!=m
->s
->to
->me
.y
) ||
1221 (which
==0 && mm
->s
->from
->me
.x
!=m
->s
->to
->me
.x
))
1226 /* If the next monotonic continues in the same direction, and we found*/
1227 /* it too, then don't count both. They represent the same intersect */
1228 /* If they are in oposite directions then they cancel each other out */
1229 /* and that is correct */
1230 if ( mm
!=m
&& /* Should always be true */
1231 (&mm
->xup
)[which
]==(&m
->xup
)[which
] ) {
1232 for ( j
=cnt
-1; j
>=0; --j
)
1237 for ( k
=j
+1; k
<cnt
; ++k
)
1238 space
[k
-1] = space
[k
];
1245 space
[cnt
] = NULL
; space
[cnt
+1] = NULL
;
1246 qsort(space
,cnt
,sizeof(Monotonic
*),mcmp
);
1250 static void FigureNeeds(Monotonic
*ms
,int which
, extended test
, Monotonic
**space
,
1251 enum overlap_type ot
, int ignore_close
) {
1252 /* Find all monotonic sections which intersect the line (x,y)[which] == test */
1253 /* find the value of the other coord on that line */
1254 /* Order them (by the other coord) */
1255 /* then run along that line figuring out which monotonics are needed */
1256 int i
, j
, winding
, ew
, was_close
, close
;
1258 MonotonicFindAt(ms
,which
,test
,space
);
1260 winding
= 0; ew
= 0; was_close
= false;
1261 for ( i
=0; space
[i
]!=NULL
; ++i
) {
1262 int needed
, unneeded
, inverted
=false;
1267 needed
= false, unneeded
= false;
1272 new += ( (&m
->xup
)[which
] ? 1 : -1 );
1274 nwinding
+= ( (&m
->xup
)[which
] ? 1 : -1 );
1275 if ( ot
==over_remove
|| ot
==over_rmselected
) {
1276 if ( winding
==0 || nwinding
==0 )
1280 } else if ( ot
==over_intersect
|| ot
==over_intersel
) {
1281 if ( (winding
>-2 && winding
<2 && nwinding
>-2 && nwinding
<2) ||
1282 ((winding
<=-2 || winding
>=2) && (nwinding
<=-2 && nwinding
>=2)))
1286 } else if ( ot
== over_exclude
) {
1287 if ( (( winding
==0 || nwinding
==0 ) && ew
==0 && new==0 ) ||
1288 (winding
!=0 && (( ew
!=0 && new==0 ) || ( ew
==0 && new!=0))) )
1293 if ( space
[i
+1]!=NULL
)
1294 close
= space
[i
+1]->other
-space
[i
]->other
< 1;
1297 if (( !close
&& !was_close
) || ignore_close
) {
1298 if (( m
->isneeded
|| m
->isunneeded
) && m
->isneeded
!=needed
) {
1299 for ( j
=i
+1; space
[j
]!=NULL
&& space
[j
]->other
-m
->other
<.5; ++j
) {
1300 if ( space
[j
]->start
==m
->start
&& space
[j
]->end
==m
->end
&&
1301 (space
[j
]->isneeded
== needed
||
1302 (!space
[j
]->isneeded
&& !space
[j
]->isunneeded
))) {
1303 space
[i
] = space
[j
];
1307 } else if ( !inverted
&& space
[j
]->other
-m
->other
<.001 &&
1308 (((&space
[j
]->xup
)[which
] == (&m
->xup
)[which
] &&
1309 (space
[j
]->isneeded
== needed
||
1310 (!space
[j
]->isneeded
&& !space
[j
]->isunneeded
))) ||
1311 ((&space
[j
]->xup
)[which
] != (&m
->xup
)[which
] &&
1312 (space
[j
]->isneeded
!= needed
||
1313 (!space
[j
]->isneeded
&& !space
[j
]->isunneeded
)))) ) {
1314 space
[i
] = space
[j
];
1321 if ( !m
->isneeded
&& !m
->isunneeded
) {
1322 m
->isneeded
= needed
; m
->isunneeded
= unneeded
;
1323 m
->when_set
= test
; /* Debugging */
1324 } else if ( m
->isneeded
!=needed
|| m
->isunneeded
!=unneeded
)
1325 SOError( "monotonic is both needed and unneeded.\n" );
1332 SOError( "Winding number did not return to 0 when %s=%g\n",
1333 which
? "y" : "x", test
);
1336 struct gaps
{ extended test
, len
; int which
; };
1338 static int gcmp(const void *_p1
, const void *_p2
) {
1339 const struct gaps
*gpt1
= _p1
, *gpt2
= _p2
;
1340 if ( gpt1
->len
> gpt2
->len
)
1342 else if ( gpt1
->len
< gpt2
->len
)
1348 static void FindNeeded(Monotonic
*ms
,enum overlap_type ot
) {
1350 Monotonic
*m
, **space
;
1351 extended top
, bottom
, test
;
1352 int t
,b
,i
,j
,k
,cnt
,which
;
1359 ends
[0] = FindOrderedEndpoints(ms
,0);
1360 ends
[1] = FindOrderedEndpoints(ms
,1);
1362 for ( m
=ms
, cnt
=0; m
!=NULL
; m
=m
->linked
, ++cnt
);
1363 space
= galloc((cnt
+2)*sizeof(Monotonic
*));
1364 gaps
= galloc(2*cnt
*sizeof(struct gaps
));
1366 /* Look for the longest splines without interruptions first. These are */
1367 /* least likely to cause problems and will give us a good basis from which*/
1368 /* to make guesses should rounding errors occur later */
1369 for ( j
=k
=0; j
<2; ++j
)
1370 for ( i
=0; ends
[j
][i
+1]!=1e10
; ++i
) {
1372 gaps
[k
].len
= (ends
[j
][i
+1]-ends
[j
][i
]);
1373 gaps
[k
++].test
= (ends
[j
][i
+1]+ends
[j
][i
])/2;
1375 qsort(gaps
,k
,sizeof(struct gaps
),gcmp
);
1377 for ( m
=ms
; m
!=NULL
; m
=m
->linked
) {
1378 if ( m
->b
.maxx
-m
->b
.minx
> m
->b
.maxy
-m
->b
.miny
) {
1379 if ( min_gap
> m
->b
.maxx
-m
->b
.minx
) min_gap
= m
->b
.maxx
-m
->b
.minx
;
1381 if ( m
->b
.maxy
-m
->b
.miny
==0 )
1382 fprintf( stderr
, "Foo\n");
1383 if ( min_gap
> m
->b
.maxy
-m
->b
.miny
) min_gap
= m
->b
.maxy
-m
->b
.miny
;
1386 if ( min_gap
<.5 ) min_gap
= .5;
1387 for ( i
=0; i
<k
&& gaps
[i
].len
>=min_gap
; ++i
)
1388 FigureNeeds(ms
,gaps
[i
].which
,gaps
[i
].test
,space
,ot
,0);
1390 for ( m
=ms
; m
!=NULL
; m
=m
->linked
) if ( !m
->isneeded
&& !m
->isunneeded
) {
1391 if ( m
->b
.maxx
-m
->b
.minx
> m
->b
.maxy
-m
->b
.miny
) {
1400 for ( b
=0; ends
[which
][b
]<=bottom
; ++b
);
1401 for ( t
=b
; ends
[which
][t
]<top
; ++t
);
1403 /* b points to an endpoint which is greater than bottom */
1404 /* t points to an endpoint which is less than top */
1405 test
= (top
+bottom
)/2;
1406 for ( i
=b
; i
<=t
; ++i
) {
1407 if ( RealNearish(test
,ends
[which
][i
]) ) {
1409 test
= (bottom
+ends
[which
][i
])/2;
1411 test
= (ends
[which
][i
-1]+ends
[which
][i
])/2;
1415 FigureNeeds(ms
,which
,test
,space
,ot
,1);
1423 static void FindUnitVectors(Intersection
*ilist
) {
1429 for ( il
=ilist
; il
!=NULL
; il
=il
->next
) {
1430 for ( ml
=il
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1431 if ( ml
->m
->isneeded
) {
1432 Spline
*s
= ml
->m
->s
;
1436 t2
= ml
->t
- (ml
->t
-ml
->m
->tstart
)/20.0;
1438 t2
= ml
->t
+ (ml
->m
->tend
-ml
->t
)/20.0;
1439 u
.x
= ((s
->splines
[0].a
*t1
+ s
->splines
[0].b
)*t1
+ s
->splines
[0].c
)*t1
-
1440 ((s
->splines
[0].a
*t2
+ s
->splines
[0].b
)*t2
+ s
->splines
[0].c
)*t2
;
1441 u
.y
= ((s
->splines
[1].a
*t1
+ s
->splines
[1].b
)*t1
+ s
->splines
[1].c
)*t1
-
1442 ((s
->splines
[1].a
*t2
+ s
->splines
[1].b
)*t2
+ s
->splines
[1].c
)*t2
;
1443 len
= u
.x
*u
.x
+ u
.y
*u
.y
;
1455 static void TestForBadDirections(Intersection
*ilist
) {
1456 /* If we have a glyph with at least two contours one drawn clockwise, */
1457 /* one counter, and these two intersect, then our algorithm will */
1458 /* not remove what appears to the user to be an overlap. Warn about */
1460 /* I think it happens iff all exits from an intersection are needed */
1465 /* If we have two splines one going from a->b and the other from b->a */
1466 /* tracing exactly the same route, then they should cancel each other */
1467 /* out. But depending on the order we hit them they may both be marked */
1468 /* needed */ /* OverlapBugs.sfd: asciicircumflex */
1469 for ( il
=ilist
; il
!=NULL
; il
=il
->next
) {
1470 for ( ml
=il
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1471 if ( ml
->m
->isneeded
&& ml
->m
->s
->knownlinear
&&
1472 ml
->m
->start
!=NULL
&& ml
->m
->end
!=NULL
) {
1473 for ( ml2
= ml
->next
; ml2
!=NULL
; ml2
=ml2
->next
) {
1474 if ( ml2
->m
->isneeded
&& ml2
->m
->s
->knownlinear
&&
1475 ml2
->m
->start
== ml
->m
->end
&&
1476 ml2
->m
->end
== ml
->m
->start
) {
1477 ml2
->m
->isneeded
= false;
1478 ml
->m
->isneeded
= false;
1479 ml2
->m
->isunneeded
= true;
1480 ml
->m
->isunneeded
= true;
1488 while ( ilist
!=NULL
) {
1490 for ( ml
= ilist
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1492 if ( ml
->m
->isneeded
) ++ncnt
;
1494 ilist
= ilist
->next
;
1498 static void MonoFigure(Spline
*s
,extended firstt
,extended endt
, SplinePoint
*first
,
1504 /*temp.d = first->me.x;*/
1505 /*temp.a = s->splines[0].a*f*f*f;*/
1506 temp
.b
= (s
->splines
[0].b
+ 3*s
->splines
[0].a
*firstt
) *f
*f
;
1507 temp
.c
= (s
->splines
[0].c
+ 2*s
->splines
[0].b
*firstt
+ 3*s
->splines
[0].a
*firstt
*firstt
) * f
;
1508 first
->nextcp
.x
= first
->me
.x
+ temp
.c
/3;
1509 end
->prevcp
.x
= first
->nextcp
.x
+ (temp
.b
+temp
.c
)/3;
1510 if ( temp
.c
>-.01 && temp
.c
<.01 ) first
->nextcp
.x
= first
->me
.x
;
1511 if ( (temp
.b
+temp
.c
)>-.01 && (temp
.b
+temp
.c
)<.01 ) end
->prevcp
.x
= end
->me
.x
;
1513 temp
.b
= (s
->splines
[1].b
+ 3*s
->splines
[1].a
*firstt
) *f
*f
;
1514 temp
.c
= (s
->splines
[1].c
+ 2*s
->splines
[1].b
*firstt
+ 3*s
->splines
[1].a
*firstt
*firstt
) * f
;
1515 first
->nextcp
.y
= first
->me
.y
+ temp
.c
/3;
1516 end
->prevcp
.y
= first
->nextcp
.y
+ (temp
.b
+temp
.c
)/3;
1517 if ( temp
.c
>-.01 && temp
.c
<.01 ) first
->nextcp
.y
= first
->me
.y
;
1518 if ( (temp
.b
+temp
.c
)>-.01 && (temp
.b
+temp
.c
)<.01 ) end
->prevcp
.y
= end
->me
.y
;
1519 first
->nonextcp
= false; end
->noprevcp
= false;
1520 SplineMake3(first
,end
);
1521 if ( SplineIsLinear(first
->next
)) {
1522 first
->nextcp
= first
->me
;
1523 end
->prevcp
= end
->me
;
1524 first
->nonextcp
= end
->noprevcp
= true;
1525 SplineRefigure(first
->next
);
1529 static Intersection
*MonoFollow(Intersection
*curil
, Monotonic
*m
) {
1530 Monotonic
*mstart
=m
;
1532 if ( m
->start
==curil
) {
1533 while ( m
!=NULL
&& m
->end
==NULL
) {
1543 while ( m
!=NULL
&& m
->start
==NULL
) {
1555 static int MonoGoesSomewhereUseful(Intersection
*curil
, Monotonic
*m
) {
1556 Intersection
*nextil
= MonoFollow(curil
,m
);
1563 for ( ml
=nextil
->monos
; ml
!=NULL
; ml
=ml
->next
)
1564 if ( ml
->m
->isneeded
)
1566 if ( cnt
>=2 ) /* One for the mono that one in, one for another going out... */
1572 static MList
*FindMLOfM(Intersection
*curil
,Monotonic
*finalm
) {
1575 for ( ml
=curil
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1576 if ( ml
->m
==finalm
)
1582 static SplinePoint
*MonoFollowForward(Intersection
**curil
, MList
*ml
,
1583 SplinePoint
*last
, Monotonic
**finalm
) {
1585 Monotonic
*m
= ml
->m
, *mstart
;
1588 for ( mstart
= m
; m
->s
==mstart
->s
; m
=m
->next
) {
1590 SOError( "Expected needed monotonic.\n" );
1591 m
->isneeded
= false; /* Mark as used */
1595 if ( m
->s
==mstart
->s
) {
1596 if ( m
->end
==NULL
) SOError( "Invariant condition does not hold.\n" );
1597 mid
= SplinePointCreate(m
->end
->inter
.x
,m
->end
->inter
.y
);
1600 mid
= SplinePointCreate(m
->s
->to
->me
.x
,m
->s
->to
->me
.y
);
1602 if ( mstart
->tstart
==0 && m
->tend
==1.0 ) {
1603 /* I check for this special case to avoid rounding errors */
1604 last
->nextcp
= m
->s
->from
->nextcp
;
1605 last
->nonextcp
= m
->s
->from
->nonextcp
;
1606 mid
->prevcp
= m
->s
->to
->prevcp
;
1607 mid
->noprevcp
= m
->s
->to
->noprevcp
;
1608 SplineMake3(last
,mid
);
1610 MonoFigure(m
->s
,mstart
->tstart
,m
->tend
,last
,mid
);
1613 if ( m
->end
!=NULL
) {
1622 static SplinePoint
*MonoFollowBackward(Intersection
**curil
, MList
*ml
,
1623 SplinePoint
*last
, Monotonic
**finalm
) {
1625 Monotonic
*m
= ml
->m
, *mstart
;
1628 for ( mstart
=m
; m
->s
==mstart
->s
; m
=m
->prev
) {
1630 SOError( "Expected needed monotonic.\n" );
1631 m
->isneeded
= false; /* Mark as used */
1632 if ( m
->start
!=NULL
)
1635 if ( m
->s
==mstart
->s
) {
1636 if ( m
->start
==NULL
) SOError( "Invariant condition does not hold.\n" );
1637 mid
= SplinePointCreate(m
->start
->inter
.x
,m
->start
->inter
.y
);
1640 mid
= SplinePointCreate(m
->s
->from
->me
.x
,m
->s
->from
->me
.y
);
1642 if ( m
->s
->knownlinear
) mid
->pointtype
= pt_corner
;
1643 if ( mstart
->tend
==1.0 && m
->tstart
==0 ) {
1644 /* I check for this special case to avoid rounding errors */
1645 last
->nextcp
= m
->s
->to
->prevcp
;
1646 last
->nonextcp
= m
->s
->to
->noprevcp
;
1647 mid
->prevcp
= m
->s
->from
->nextcp
;
1648 mid
->noprevcp
= m
->s
->from
->nonextcp
;
1649 SplineMake3(last
,mid
);
1651 MonoFigure(m
->s
,mstart
->tend
,m
->tstart
,last
,mid
);
1654 if ( m
->start
!=NULL
) {
1663 static SplineSet
*JoinAContour(Intersection
*startil
,MList
*ml
) {
1664 SplineSet
*ss
= chunkalloc(sizeof(SplineSet
));
1666 Intersection
*curil
;
1667 int allexclude
= ml
->m
->exclude
;
1671 ss
->first
= last
= SplinePointCreate(startil
->inter
.x
,startil
->inter
.y
);
1674 if ( allexclude
&& !ml
->m
->exclude
) allexclude
= false;
1676 if ( ml
->m
->start
==curil
) {
1677 last
= MonoFollowForward(&curil
,ml
,last
,&finalm
);
1678 } else if ( ml
->m
->end
==curil
) {
1679 last
= MonoFollowBackward(&curil
,ml
,last
,&finalm
);
1681 SOError( "Couldn't find endpoint (%g,%g).\n",
1682 curil
->inter
.x
, curil
->inter
.y
);
1683 ml
->m
->isneeded
= false; /* Prevent infinite loops */
1687 if ( curil
==startil
) {
1688 ss
->first
->prev
= last
->prev
;
1689 ss
->first
->prevcp
= last
->prevcp
;
1690 ss
->first
->noprevcp
= last
->noprevcp
;
1691 last
->prev
->to
= ss
->first
;
1692 SplinePointFree(last
);
1693 ss
->last
= ss
->first
;
1696 lastml
= FindMLOfM(curil
,finalm
);
1697 if ( lastml
==NULL
) {
1698 IError("Could not find finalm");
1699 /* Try to preserve direction */
1700 for ( ml
=curil
->monos
; ml
!=NULL
&& (!ml
->m
->isneeded
|| ml
->m
->end
==curil
); ml
=ml
->next
);
1702 for ( ml
=curil
->monos
; ml
!=NULL
&& !ml
->m
->isneeded
; ml
=ml
->next
);
1704 int k
; MList
*bestml
; double bestdot
;
1705 for ( k
=0; k
<2; ++k
) {
1706 bestml
= NULL
; bestdot
= -2;
1707 for ( ml
=curil
->monos
; ml
!=NULL
; ml
=ml
->next
) {
1708 if ( ml
->m
->isneeded
&& (ml
->m
->start
==curil
|| k
) ) {
1709 double dot
= lastml
->unit
.x
*ml
->unit
.x
+ lastml
->unit
.y
*ml
->unit
.y
;
1710 if ( dot
>bestdot
) {
1722 for ( ml
=curil
->monos
; ml
!=NULL
; ml
=ml
->next
)
1723 if ( ml
->m
->isunneeded
&& ml
->m
->start
==curil
&&
1724 MonoFollow(curil
,ml
->m
)==startil
)
1727 for ( ml
=curil
->monos
; ml
!=NULL
; ml
=ml
->next
)
1728 if ( ml
->m
->isunneeded
&& ml
->m
->end
==curil
&&
1729 MonoFollow(curil
,ml
->m
)==startil
)
1732 SOError("Closing contour with unneeded path\n" );
1733 ml
->m
->isneeded
= true;
1737 SOError( "couldn't find a needed exit from an intersection\n" );
1742 SPLCatagorizePoints(ss
);
1743 if ( allexclude
&& SplinePointListIsClockwise(ss
))
1744 SplineSetReverse(ss
);
1748 static SplineSet
*FindMatchingContour(SplineSet
*head
,SplineSet
*cur
) {
1751 for ( test
=head
; test
!=NULL
; test
=test
->next
) {
1752 if ( test
->first
->prev
==NULL
&&
1753 test
->first
->me
.x
==cur
->last
->me
.x
&& test
->first
->me
.y
==cur
->last
->me
.y
&&
1754 test
->last
->me
.x
==cur
->first
->me
.x
&& test
->last
->me
.y
==cur
->first
->me
.y
)
1758 for ( test
=head
; test
!=NULL
; test
=test
->next
) {
1759 if ( test
->first
->prev
==NULL
&&
1760 test
->last
->me
.x
==cur
->last
->me
.x
&& test
->last
->me
.y
==cur
->last
->me
.y
&&
1761 test
->first
->me
.x
==cur
->first
->me
.x
&& test
->first
->me
.y
==cur
->first
->me
.y
) {
1762 SplineSetReverse(cur
);
1768 for ( test
=head
; test
!=NULL
; test
=test
->next
) {
1769 if ( test
->first
->prev
==NULL
&&
1770 ((test
->first
->me
.x
==cur
->last
->me
.x
&& test
->first
->me
.y
==cur
->last
->me
.y
) ||
1771 (test
->last
->me
.x
==cur
->first
->me
.x
&& test
->last
->me
.y
==cur
->first
->me
.y
)))
1776 for ( test
=head
; test
!=NULL
; test
=test
->next
) {
1777 if ( test
->first
->prev
==NULL
&&
1778 ((test
->last
->me
.x
==cur
->last
->me
.x
&& test
->last
->me
.y
==cur
->last
->me
.y
) ||
1779 (test
->first
->me
.x
==cur
->first
->me
.x
&& test
->first
->me
.y
==cur
->first
->me
.y
))) {
1780 SplineSetReverse(cur
);
1788 static SplineSet
*JoinAllNeeded(Intersection
*ilist
) {
1790 SplineSet
*head
=NULL
, *last
=NULL
, *cur
, *test
;
1793 for ( il
=ilist
; il
!=NULL
; il
=il
->next
) {
1794 /* Try to preserve direction */
1796 for ( ml
=il
->monos
; ml
!=NULL
&& (!ml
->m
->isneeded
|| ml
->m
->end
==il
); ml
=ml
->next
);
1798 for ( ml
=il
->monos
; ml
!=NULL
&& !ml
->m
->isneeded
; ml
=ml
->next
);
1801 if ( !MonoGoesSomewhereUseful(il
,ml
->m
)) {
1802 SOError("Humph. This monotonic leads nowhere.\n" );
1805 cur
= JoinAContour(il
,ml
);
1809 if ( cur
->first
->prev
==NULL
) {
1810 /* Open contours are errors. See if we had an earlier error */
1811 /* to which we can join this */
1812 test
= FindMatchingContour(head
,cur
);
1814 if ( test
->first
->me
.x
==cur
->last
->me
.x
&& test
->first
->me
.y
==cur
->last
->me
.y
) {
1815 test
->first
->prev
= cur
->last
->prev
;
1816 cur
->last
->prev
->to
= test
->first
;
1817 SplinePointFree(cur
->last
);
1818 if ( test
->last
->me
.x
==cur
->first
->me
.x
&& test
->last
->me
.y
==cur
->first
->me
.y
) {
1819 test
->last
->next
= cur
->first
->next
;
1820 cur
->first
->next
->from
= test
->last
;
1821 SplinePointFree(cur
->first
);
1822 test
->last
= test
->first
;
1824 test
->first
= cur
->first
;
1826 if ( test
->last
->me
.x
!=cur
->first
->me
.x
|| test
->last
->me
.y
!=cur
->first
->me
.y
)
1827 SOError( "Join failed");
1829 test
->last
->next
= cur
->first
->next
;
1830 cur
->first
->next
->from
= test
->last
;
1831 SplinePointFree(cur
->first
);
1832 test
->last
= test
->first
;
1835 cur
->first
= cur
->last
= NULL
;
1836 SplinePointListFree(cur
);
1850 static SplineSet
*MergeOpenAndFreeClosed(SplineSet
*new,SplineSet
*old
,
1851 enum overlap_type ot
) {
1854 while ( old
!=NULL
) {
1856 if ( old
->first
->prev
==NULL
||
1857 (( ot
==over_rmselected
|| ot
==over_intersel
|| ot
==over_fisel
) &&
1858 !SSIsSelected(old
)) ) {
1863 SplinePointListFree(old
);
1870 static void FreeMonotonics(Monotonic
*m
) {
1875 chunkfree(m
,sizeof(*m
));
1880 static void FreeMList(MList
*ml
) {
1883 while ( ml
!=NULL
) {
1885 chunkfree(ml
,sizeof(*ml
));
1890 static void FreeIntersections(Intersection
*ilist
) {
1893 while ( ilist
!=NULL
) {
1895 FreeMList(ilist
->monos
);
1896 chunkfree(ilist
,sizeof(*ilist
));
1901 static void MonoSplit(Monotonic
*m
) {
1903 SplinePoint
*last
= s
->from
;
1904 SplinePoint
*final
= s
->to
;
1909 while ( m
!=NULL
&& m
->s
==s
&& m
->tend
<1 ) {
1910 if ( m
->end
!=NULL
) {
1911 SplinePoint
*mid
= SplinePointCreate(m
->end
->inter
.x
,m
->end
->inter
.y
);
1912 if ( m
->s
->knownlinear
) mid
->pointtype
= pt_corner
;
1913 MonoFigure(s
,lastt
,m
->tend
,last
,mid
);
1919 MonoFigure(s
,lastt
,1.0,last
,final
);
1923 static void FixupIntersectedSplines(Monotonic
*ms
) {
1924 /* If all we want is intersections, then the contours are already correct */
1925 /* all we need to do is run through the Monotonic list and when we find */
1926 /* an intersection, make sure it has real splines around it */
1930 while ( ms
!=NULL
) {
1931 needs_split
= false;
1932 for ( m
=ms
; m
!=NULL
&& m
->s
==ms
->s
; m
=m
->linked
) {
1933 if ( (m
->tstart
!=0 && m
->start
!=NULL
) || (m
->tend
!=1 && m
->end
!=NULL
))
1942 static int BpClose(BasePoint
*here
, BasePoint
*there
, double error
) {
1945 if ( (dx
= here
->x
-there
->x
)<0 ) dx
= -dx
;
1946 if ( (dy
= here
->y
-there
->y
)<0 ) dy
= -dy
;
1947 if ( dx
<error
&& dy
<error
)
1953 static SplineSet
*SSRemoveTiny(SplineSet
*base
) {
1956 extended test
, dx
, dy
;
1957 SplineSet
*prev
= NULL
, *head
= base
, *ssnext
;
1958 SplinePoint
*sp
, *nsp
;
1960 SplineSetQuickBounds(base
,&b
);
1961 error
= b
.maxy
-b
.miny
;
1962 test
= b
.maxx
-b
.minx
;
1963 if ( test
>error
) error
= test
;
1964 if ( (test
= b
.maxy
)<0 ) test
= -test
;
1965 if ( test
>error
) error
= test
;
1966 if ( (test
= b
.maxx
)<0 ) test
= -test
;
1967 if ( test
>error
) error
= test
;
1970 while ( base
!=NULL
) {
1971 ssnext
= base
->next
;
1972 for ( sp
=base
->first
; ; ) {
1973 if ( sp
->next
==NULL
)
1976 if ( BpClose(&sp
->me
,&nsp
->me
,error
) ) {
1977 if ( BpClose(&sp
->me
,&sp
->nextcp
,2*error
) &&
1978 BpClose(&nsp
->me
,&nsp
->prevcp
,2*error
)) {
1979 /* Remove the spline */
1981 /* Only this spline in the contour, so remove the contour */
1983 SplinePointListFree(base
);
1987 prev
->next
= ssnext
;
1991 SplineFree(sp
->next
);
1992 if ( nsp
->nonextcp
) {
1993 sp
->nextcp
= sp
->me
;
1994 sp
->nonextcp
= true;
1996 sp
->nextcp
= nsp
->nextcp
;
1997 sp
->nonextcp
= false;
1999 sp
->nextcpdef
= nsp
->nextcpdef
;
2000 sp
->next
= nsp
->next
;
2001 if ( nsp
->next
!=NULL
) {
2002 nsp
->next
->from
= sp
;
2003 SplineRefigure(sp
->next
);
2005 if ( nsp
==base
->last
)
2007 if ( nsp
==base
->first
)
2009 SplinePointFree(nsp
);
2010 if ( sp
->next
==NULL
)
2014 /* Leave the spline, but move the two points together */
2016 new.x
= (sp
->me
.x
+nsp
->me
.x
)/2;
2017 new.y
= (sp
->me
.y
+nsp
->me
.y
)/2;
2018 dx
= new.x
-sp
->me
.x
; dy
= new.y
-sp
->me
.y
;
2020 sp
->nextcp
.x
+= dx
; sp
->nextcp
.y
+= dy
;
2021 sp
->prevcp
.x
+= dx
; sp
->prevcp
.y
+= dy
;
2022 dx
= new.x
-nsp
->me
.x
; dy
= new.y
-nsp
->me
.y
;
2024 nsp
->nextcp
.x
+= dx
; nsp
->nextcp
.y
+= dy
;
2025 nsp
->prevcp
.x
+= dx
; nsp
->prevcp
.y
+= dy
;
2026 SplineRefigure(sp
->next
);
2027 if ( sp
->prev
) SplineRefigure(sp
->prev
);
2028 if ( nsp
->next
) SplineRefigure(nsp
->next
);
2032 if ( sp
==base
->first
)
2035 if ( sp
->prev
!=NULL
&& !sp
->noprevcp
) {
2036 int refigure
= false;
2037 if ( sp
->me
.x
-sp
->prevcp
.x
>-error
&& sp
->me
.x
-sp
->prevcp
.x
<error
) {
2038 sp
->prevcp
.x
= sp
->me
.x
;
2041 if ( sp
->me
.y
-sp
->prevcp
.y
>-error
&& sp
->me
.y
-sp
->prevcp
.y
<error
) {
2042 sp
->prevcp
.y
= sp
->me
.y
;
2045 if ( sp
->me
.x
==sp
->prevcp
.x
&& sp
->me
.y
==sp
->prevcp
.y
)
2046 sp
->noprevcp
= true;
2048 SplineRefigure(sp
->prev
);
2050 if ( sp
->next
!=NULL
&& !sp
->nonextcp
) {
2051 int refigure
= false;
2052 if ( sp
->me
.x
-sp
->nextcp
.x
>-error
&& sp
->me
.x
-sp
->nextcp
.x
<error
) {
2053 sp
->nextcp
.x
= sp
->me
.x
;
2056 if ( sp
->me
.y
-sp
->nextcp
.y
>-error
&& sp
->me
.y
-sp
->nextcp
.y
<error
) {
2057 sp
->nextcp
.y
= sp
->me
.y
;
2060 if ( sp
->me
.x
==sp
->nextcp
.x
&& sp
->me
.y
==sp
->nextcp
.y
)
2061 sp
->nonextcp
= true;
2063 SplineRefigure(sp
->next
);
2073 static void RemoveNextSP(SplinePoint
*psp
,SplinePoint
*sp
,SplinePoint
*nsp
,
2076 SplineFree(psp
->next
);
2077 psp
->next
= psp
->prev
;
2078 psp
->next
->from
= psp
;
2079 SplinePointFree(sp
);
2080 SplineRefigure(psp
->prev
);
2082 psp
->next
= nsp
->next
;
2083 psp
->next
->from
= psp
;
2084 psp
->nextcp
= nsp
->nextcp
;
2085 psp
->nonextcp
= nsp
->nonextcp
;
2086 psp
->nextcpdef
= nsp
->nextcpdef
;
2087 SplineFree(sp
->prev
);
2088 SplineFree(sp
->next
);
2089 SplinePointFree(sp
);
2090 SplinePointFree(nsp
);
2091 SplineRefigure(psp
->next
);
2093 if ( base
->first
==sp
|| base
->first
==nsp
)
2095 if ( base
->last
==sp
|| base
->last
==nsp
)
2099 static void RemovePrevSP(SplinePoint
*psp
,SplinePoint
*sp
,SplinePoint
*nsp
,
2102 SplineFree(nsp
->prev
);
2103 nsp
->prev
= nsp
->next
;
2104 nsp
->prev
->to
= nsp
;
2105 SplinePointFree(sp
);
2106 SplineRefigure(nsp
->next
);
2108 nsp
->prev
= psp
->prev
;
2109 nsp
->prev
->to
= nsp
;
2110 nsp
->prevcp
= nsp
->me
;
2111 nsp
->noprevcp
= true;
2112 nsp
->prevcpdef
= psp
->prevcpdef
;
2113 SplineFree(sp
->prev
);
2114 SplineFree(sp
->next
);
2115 SplinePointFree(sp
);
2116 SplinePointFree(psp
);
2117 SplineRefigure(nsp
->prev
);
2119 if ( base
->first
==sp
|| base
->first
==psp
)
2121 if ( base
->last
==sp
|| base
->last
==psp
)
2125 static SplinePoint
*SameLine(SplinePoint
*psp
, SplinePoint
*sp
, SplinePoint
*nsp
) {
2126 BasePoint noff
, poff
;
2127 real nlen
, plen
, normal
;
2129 noff
.x
= nsp
->me
.x
-sp
->me
.x
; noff
.y
= nsp
->me
.y
-sp
->me
.y
;
2130 poff
.x
= psp
->me
.x
-sp
->me
.x
; poff
.y
= psp
->me
.y
-sp
->me
.y
;
2131 nlen
= esqrt(noff
.x
*noff
.x
+ noff
.y
*noff
.y
);
2132 plen
= esqrt(poff
.x
*poff
.x
+ poff
.y
*poff
.y
);
2137 normal
= (noff
.x
*poff
.y
- noff
.y
*poff
.x
)/nlen
/plen
;
2138 if ( normal
<-.0001 || normal
>.0001 )
2141 if ( noff
.x
*poff
.x
< 0 || noff
.y
*poff
.y
< 0 )
2142 return( NULL
); /* Same line, but different directions */
2143 if ( (noff
.x
>0 && noff
.x
>poff
.x
) ||
2144 (noff
.x
<0 && noff
.x
<poff
.x
) ||
2145 (noff
.y
>0 && noff
.y
>poff
.y
) ||
2146 (noff
.y
<0 && noff
.y
<poff
.y
))
2152 static double AdjacentSplinesMatch(Spline
*s1
,Spline
*s2
,int s2forward
) {
2153 /* Is every point on s2 close to a point on s1 */
2154 double t
, tdiff
, t1
= -1;
2156 double t1start
, t1end
;
2160 if ( (xoff
= s2
->to
->me
.x
-s2
->from
->me
.x
)<0 ) xoff
= -xoff
;
2161 if ( (yoff
= s2
->to
->me
.y
-s2
->from
->me
.y
)<0 ) yoff
= -yoff
;
2163 SplineFindExtrema(&s1
->splines
[0],&ts
[0],&ts
[1]);
2165 SplineFindExtrema(&s1
->splines
[1],&ts
[0],&ts
[1]);
2170 for ( i
=1; i
>=0 && ts
[i
]==-1; --i
);
2171 t1start
= i
<0 ? 0 : ts
[i
];
2176 t1end
= ( ts
[0]==-1 ) ? 1.0 : ts
[0];
2179 for ( ; (s2forward
&& t
<=1) || (!s2forward
&& t
>=0 ); t
+= tdiff
) {
2180 double x1
, y1
, xo
, yo
;
2181 double x
= ((s2
->splines
[0].a
*t
+s2
->splines
[0].b
)*t
+s2
->splines
[0].c
)*t
+s2
->splines
[0].d
;
2182 double y
= ((s2
->splines
[1].a
*t
+s2
->splines
[1].b
)*t
+s2
->splines
[1].c
)*t
+s2
->splines
[1].d
;
2184 t1
= IterateSplineSolve(&s1
->splines
[0],t1start
,t1end
,x
,.001);
2186 t1
= IterateSplineSolve(&s1
->splines
[1],t1start
,t1end
,y
,.001);
2189 x1
= ((s1
->splines
[0].a
*t1
+s1
->splines
[0].b
)*t1
+s1
->splines
[0].c
)*t1
+s1
->splines
[0].d
;
2190 y1
= ((s1
->splines
[1].a
*t1
+s1
->splines
[1].b
)*t1
+s1
->splines
[1].c
)*t1
+s1
->splines
[1].d
;
2191 if ( (xo
= (x
-x1
))<0 ) xo
= -xo
;
2192 if ( (yo
= (y
-y1
))<0 ) yo
= -yo
;
2199 static void SSRemoveBacktracks(SplineSet
*ss
) {
2204 for ( sp
=ss
->first
; ; ) {
2205 if ( sp
->next
!=NULL
&& sp
->prev
!=NULL
) {
2206 SplinePoint
*nsp
= sp
->next
->to
, *psp
= sp
->prev
->from
, *isp
;
2207 BasePoint ndir
, pdir
;
2208 double dot
, pdot
, nlen
, plen
, t
= -1;
2210 ndir
.x
= (nsp
->me
.x
- sp
->me
.x
); ndir
.y
= (nsp
->me
.y
- sp
->me
.y
);
2211 pdir
.x
= (psp
->me
.x
- sp
->me
.x
); pdir
.y
= (psp
->me
.y
- sp
->me
.y
);
2212 nlen
= ndir
.x
*ndir
.x
+ ndir
.y
*ndir
.y
; plen
= pdir
.x
*pdir
.x
+ pdir
.y
*pdir
.y
;
2213 dot
= ndir
.x
*pdir
.x
+ ndir
.y
*pdir
.y
;
2214 if ( (pdot
= ndir
.x
*pdir
.y
- ndir
.y
*pdir
.x
)<0 ) pdot
= -pdot
;
2215 if ( dot
>0 && dot
>pdot
) {
2216 if ( nlen
>plen
&& (t
=AdjacentSplinesMatch(sp
->next
,sp
->prev
,false))!=-1 ) {
2217 isp
= SplineBisect(sp
->next
,t
);
2218 psp
->nextcp
.x
= psp
->me
.x
+ (isp
->nextcp
.x
-isp
->me
.x
);
2219 psp
->nextcp
.y
= psp
->me
.y
+ (isp
->nextcp
.y
-isp
->me
.y
);
2220 psp
->nonextcp
= isp
->nonextcp
;
2221 psp
->next
= isp
->next
;
2222 isp
->next
->from
= psp
;
2223 SplineFree(isp
->prev
);
2224 SplineFree(sp
->prev
);
2225 SplinePointFree(isp
);
2226 SplinePointFree(sp
);
2227 if ( psp
->next
->order2
) {
2228 psp
->nextcp
.x
= nsp
->prevcp
.x
= (psp
->nextcp
.x
+nsp
->prevcp
.x
)/2;
2229 psp
->nextcp
.y
= nsp
->prevcp
.y
= (psp
->nextcp
.y
+nsp
->prevcp
.y
)/2;
2230 if ( psp
->nonextcp
|| nsp
->noprevcp
)
2231 psp
->nonextcp
= nsp
->noprevcp
= true;
2233 SplineRefigure(psp
->next
);
2234 if ( ss
->first
==sp
)
2239 } else if ( nlen
<plen
&& (t
=AdjacentSplinesMatch(sp
->prev
,sp
->next
,true))!=-1 ) {
2240 isp
= SplineBisect(sp
->prev
,t
);
2241 nsp
->prevcp
.x
= nsp
->me
.x
+ (isp
->prevcp
.x
-isp
->me
.x
);
2242 nsp
->prevcp
.y
= nsp
->me
.y
+ (isp
->prevcp
.y
-isp
->me
.y
);
2243 nsp
->noprevcp
= isp
->noprevcp
;
2244 nsp
->prev
= isp
->prev
;
2245 isp
->prev
->to
= nsp
;
2246 SplineFree(isp
->next
);
2247 SplineFree(sp
->next
);
2248 SplinePointFree(isp
);
2249 SplinePointFree(sp
);
2250 if ( psp
->next
->order2
) {
2251 psp
->nextcp
.x
= nsp
->prevcp
.x
= (psp
->nextcp
.x
+nsp
->prevcp
.x
)/2;
2252 psp
->nextcp
.y
= nsp
->prevcp
.y
= (psp
->nextcp
.y
+nsp
->prevcp
.y
)/2;
2253 if ( psp
->nonextcp
|| nsp
->noprevcp
)
2254 psp
->nonextcp
= nsp
->noprevcp
= true;
2256 SplineRefigure(nsp
->prev
);
2257 if ( ss
->first
==sp
)
2265 if ( sp
->next
==NULL
)
2268 if ( sp
==ss
->first
)
2273 /* If we have a contour with no width, say a line from A to B and then from B */
2274 /* to A, then it will be ambiguous, depending on how we hit the contour, as */
2275 /* to whether it is needed or not. Which will cause us to complain. Since */
2276 /* they contain no area, they achieve nothing, so we might as well say they */
2277 /* overlap themselves and remove them here */
2278 static SplineSet
*SSRemoveReversals(SplineSet
*base
) {
2279 SplineSet
*head
= base
, *prev
=NULL
, *next
;
2283 while ( base
!=NULL
) {
2288 if ( base
->first
->next
==NULL
||
2289 (base
->first
->next
->to
==base
->first
&&
2290 base
->first
->nextcp
.x
==base
->first
->prevcp
.x
&&
2291 base
->first
->nextcp
.y
==base
->first
->prevcp
.y
)) {
2292 /* remove single points */
2298 SplinePointListFree(base
);
2302 for ( sp
=base
->first
; ; ) {
2303 if ( sp
->next
!=NULL
&& sp
->prev
!=NULL
&&
2304 sp
->nextcp
.x
==sp
->prevcp
.x
&& sp
->nextcp
.y
==sp
->prevcp
.y
) {
2305 SplinePoint
*nsp
= sp
->next
->to
, *psp
= sp
->prev
->from
, *isp
;
2306 if ( psp
->me
.x
==nsp
->me
.x
&& psp
->me
.y
==nsp
->me
.y
&&
2307 psp
->nextcp
.x
==nsp
->prevcp
.x
&& psp
->nextcp
.y
==nsp
->prevcp
.y
) {
2308 /* We wish to remove sp, sp->next, sp->prev & one of nsp/psp */
2309 RemoveNextSP(psp
,sp
,nsp
,base
);
2312 } else if ( sp
->nonextcp
/* which implies sp->noprevcp */ &&
2313 psp
->nonextcp
&& nsp
->noprevcp
&&
2314 (isp
= SameLine(psp
,sp
,nsp
))!=NULL
) {
2315 /* We have a line that backtracks, but doesn't cover */
2316 /* the entire spline, so we intersect */
2317 /* We want to remove sp, the shorter of sp->next, sp->prev */
2318 /* and a bit of the other one. Also reomve one of nsp,psp */
2320 RemoveNextSP(psp
,sp
,nsp
,base
);
2321 psp
->nextcp
= psp
->me
;
2322 psp
->nonextcp
= true;
2324 RemovePrevSP(psp
,sp
,nsp
,base
);
2330 if ( sp
->next
==NULL
)
2333 if ( sp
==base
->first
)
2337 SSRemoveBacktracks(base
);
2344 SplineSet
*SplineSetRemoveOverlap(SplineChar
*sc
, SplineSet
*base
,enum overlap_type ot
) {
2346 Intersection
*ilist
;
2348 SplineSet
*order3
= NULL
;
2352 for ( ss
=base
; ss
!=NULL
; ss
=ss
->next
)
2353 if ( ss
->first
->next
!=NULL
) {
2354 is_o2
= ss
->first
->next
->order2
;
2358 order3
= SplineSetsPSApprox(base
);
2359 SplinePointListsFree(base
);
2364 glyphname
= sc
->name
;
2366 base
= SSRemoveTiny(base
);
2367 SSRemoveStupidControlPoints(base
);
2368 SplineSetsRemoveAnnoyingExtrema(base
,.3);
2369 SSOverlapClusterCpAngles(base
,.01);
2370 base
= SSRemoveReversals(base
);
2371 ms
= SSsToMContours(base
,ot
);
2372 ilist
= FindIntersections(ms
,ot
);
2374 if ( ot
==over_findinter
|| ot
==over_fisel
) {
2375 FixupIntersectedSplines(ms
);
2379 FindUnitVectors(ilist
);
2380 if ( ot
==over_remove
|| ot
== over_rmselected
)
2381 TestForBadDirections(ilist
);
2382 ret
= JoinAllNeeded(ilist
);
2383 ret
= MergeOpenAndFreeClosed(ret
,base
,ot
);
2386 FreeIntersections(ilist
);
2388 if ( order3
!=NULL
) {
2389 ss
= SplineSetsTTFApprox(ret
);
2390 SplinePointListsFree(ret
);