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.
36 # include <ieeefp.h> /* Solaris defines isnan in ieeefp rather than math.h */
39 /* This file contains utility routines for second order bezier splines */
41 /* The most interesting thing */
42 /* it does is to figure out a quadratic approximation to the cubic splines */
43 /* that postscript uses. We do this by looking at each spline and running */
44 /* from the end toward the beginning, checking approximately every emunit */
45 /* There is only one quadratic spline possible for any given interval of the */
46 /* cubic. The start and end points are the interval end points (obviously) */
47 /* the control point is where the two slopes (at start and end) intersect. */
48 /* If this spline is a close approximation to the cubic spline (doesn't */
49 /* deviate from it by more than an emunit or so), then we use this interval */
50 /* as one of our quadratic splines. */
51 /* It may turn out that the "quadratic" spline above is actually linear. Well */
52 /* that's ok. It may also turn out that we can't find a good approximation. */
53 /* If that's true then just insert a linear segment for an emunit stretch. */
54 /* (actually this failure mode may not be possible), but I'm not sure */
55 /* Then we play the same trick for the rest of the cubic spline (if any) */
57 /* Does the quadratic spline in ttf approximate the cubic spline in ps */
58 /* within one pixel between tmin and tmax (on ps. presumably ttf between 0&1 */
59 /* dim is the dimension in which there is the greatest change */
60 static int comparespline(Spline
*ps
, Spline
*ttf
, real tmin
, real tmax
, real err
) {
62 real dx
, dy
, ddim
, dt
, t
;
69 /* Are all points on ttf near points on ps? */
70 /* This doesn't answer that question, but rules out gross errors */
71 bb
.minx
= bb
.maxx
= ps
->from
->me
.x
; bb
.miny
= bb
.maxy
= ps
->from
->me
.y
;
72 if ( ps
->from
->nextcp
.x
>bb
.maxx
) bb
.maxx
= ps
->from
->nextcp
.x
;
73 else bb
.minx
= ps
->from
->nextcp
.x
;
74 if ( ps
->from
->nextcp
.y
>bb
.maxy
) bb
.maxy
= ps
->from
->nextcp
.y
;
75 else bb
.miny
= ps
->from
->nextcp
.y
;
76 if ( ps
->to
->prevcp
.x
>bb
.maxx
) bb
.maxx
= ps
->to
->prevcp
.x
;
77 else if ( ps
->to
->prevcp
.x
<bb
.minx
) bb
.minx
= ps
->to
->prevcp
.x
;
78 if ( ps
->to
->prevcp
.y
>bb
.maxy
) bb
.maxy
= ps
->to
->prevcp
.y
;
79 else if ( ps
->to
->prevcp
.y
<bb
.miny
) bb
.miny
= ps
->to
->prevcp
.y
;
80 if ( ps
->to
->me
.x
>bb
.maxx
) bb
.maxx
= ps
->to
->me
.x
;
81 else if ( ps
->to
->me
.x
<bb
.minx
) bb
.minx
= ps
->to
->me
.x
;
82 if ( ps
->to
->me
.y
>bb
.maxy
) bb
.maxy
= ps
->to
->me
.y
;
83 else if ( ps
->to
->me
.y
<bb
.miny
) bb
.miny
= ps
->to
->me
.y
;
84 for ( t
=.1; t
<1; t
+= .1 ) {
85 d
= (ttf
->splines
[0].b
*t
+ttf
->splines
[0].c
)*t
+ttf
->splines
[0].d
;
86 o
= (ttf
->splines
[1].b
*t
+ttf
->splines
[1].c
)*t
+ttf
->splines
[1].d
;
87 if ( d
<bb
.minx
|| d
>bb
.maxx
|| o
<bb
.miny
|| o
>bb
.maxy
)
91 /* Are all points on ps near points on ttf? */
92 dx
= ((ps
->splines
[0].a
*tmax
+ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
)*tmax
-
93 ((ps
->splines
[0].a
*tmin
+ps
->splines
[0].b
)*tmin
+ps
->splines
[0].c
)*tmin
;
94 dy
= ((ps
->splines
[1].a
*tmax
+ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
)*tmax
-
95 ((ps
->splines
[1].a
*tmin
+ps
->splines
[1].b
)*tmin
+ps
->splines
[1].c
)*tmin
;
108 dt
= (tmax
-tmin
)/ddim
;
109 for ( t
=tmin
; t
<=tmax
; t
+= dt
) {
110 if ( t
>tmax
-dt
/8. ) t
= tmax
; /* Avoid rounding errors */
111 d
= ((ps
->splines
[dim
].a
*t
+ps
->splines
[dim
].b
)*t
+ps
->splines
[dim
].c
)*t
+ps
->splines
[dim
].d
;
112 o
= ((ps
->splines
[other
].a
*t
+ps
->splines
[other
].b
)*t
+ps
->splines
[other
].c
)*t
+ps
->splines
[other
].d
;
113 if ( ttf
->splines
[dim
].b
== 0 ) {
114 ttf_t
= (d
-ttf
->splines
[dim
].d
)/ttf
->splines
[dim
].c
;
116 sq
= ttf
->splines
[dim
].c
*ttf
->splines
[dim
].c
-
117 4*ttf
->splines
[dim
].b
*(ttf
->splines
[dim
].d
-d
);
121 ttf_t
= (-ttf
->splines
[dim
].c
-sq
)/(2*ttf
->splines
[dim
].b
);
122 if ( ttf_t
>=-0.1 && ttf_t
<=1.1 ) { /* Optimizer gives us rounding errors */
123 /* And tmin/tmax are no longer exact */
124 val
= (ttf
->splines
[other
].b
*ttf_t
+ttf
->splines
[other
].c
)*ttf_t
+
125 ttf
->splines
[other
].d
;
126 if ( val
>o
-err
&& val
<o
+err
)
129 ttf_t
= (-ttf
->splines
[dim
].c
+sq
)/(2*ttf
->splines
[dim
].b
);
131 if ( ttf_t
>=-0.1 && ttf_t
<=1.1 ) {
132 val
= (ttf
->splines
[other
].b
*ttf_t
+ttf
->splines
[other
].c
)*ttf_t
+
133 ttf
->splines
[other
].d
;
134 if ( val
>o
-err
&& val
<o
+err
)
140 /* Are representative points on ttf near points on ps? */
141 for ( t
=.125; t
<1; t
+= .125 ) {
142 d
= (ttf
->splines
[dim
].b
*t
+ttf
->splines
[dim
].c
)*t
+ttf
->splines
[dim
].d
;
143 o
= (ttf
->splines
[other
].b
*t
+ttf
->splines
[other
].c
)*t
+ttf
->splines
[other
].d
;
144 SplineSolveFull(&ps
->splines
[dim
],d
,ts
);
145 for ( i
=0; i
<3; ++i
) if ( ts
[i
]!=-1 ) {
146 val
= ((ps
->splines
[other
].a
*ts
[i
]+ps
->splines
[other
].b
)*ts
[i
]+ps
->splines
[other
].c
)*ts
[i
]+ps
->splines
[other
].d
;
147 if ( val
>o
-err
&& val
<o
+err
)
157 static SplinePoint
*MakeQuadSpline(SplinePoint
*start
,Spline
*ttf
,real x
,
158 real y
, real tmax
,SplinePoint
*oldend
) {
159 Spline
*new = chunkalloc(sizeof(Spline
));
160 SplinePoint
*end
= chunkalloc(sizeof(SplinePoint
));
163 end
->roundx
= oldend
->roundx
; end
->roundy
= oldend
->roundy
; end
->dontinterpolate
= oldend
->dontinterpolate
;
164 x
= oldend
->me
.x
; y
= oldend
->me
.y
; /* Want it to compare exactly */
166 end
->ttfindex
= 0xfffe;
167 end
->nextcpindex
= 0xfffe;
168 end
->me
.x
= end
->nextcp
.x
= x
;
169 end
->me
.y
= end
->nextcp
.y
= y
;
170 end
->nonextcp
= true;
173 new->from
= start
; start
->next
= new;
174 new->to
= end
; end
->prev
= new;
175 if ( new->splines
[0].b
==0 && new->splines
[1].b
==0 ) {
176 end
->noprevcp
= true;
177 end
->prevcp
.x
= x
; end
->prevcp
.y
= y
;
178 new->islinear
= new->knownlinear
= true;
180 end
->prevcp
.x
= start
->nextcp
.x
= ttf
->splines
[0].c
/2+ttf
->splines
[0].d
;
181 end
->prevcp
.y
= start
->nextcp
.y
= ttf
->splines
[1].c
/2+ttf
->splines
[1].d
;
182 start
->nonextcp
= end
->noprevcp
= false;
183 new->isquadratic
= true;
189 static int buildtestquads(Spline
*ttf
,real xmin
,real ymin
,real cx
,real cy
,
190 real x
,real y
,real tmin
,real t
,real err
,Spline
*ps
, DBounds
*psbb
) {
193 /* test the control points are reasonable */
194 fudge
= (psbb
->maxx
-psbb
->minx
) + (psbb
->maxy
-psbb
->miny
);
195 if ( cx
<psbb
->minx
-fudge
|| cx
>psbb
->maxx
+fudge
)
197 if ( cy
<psbb
->miny
-fudge
|| cy
>psbb
->maxy
+fudge
)
200 ttf
->splines
[0].d
= xmin
;
201 ttf
->splines
[0].c
= 2*(cx
-xmin
);
202 ttf
->splines
[0].b
= xmin
+x
-2*cx
;
203 ttf
->splines
[1].d
= ymin
;
204 ttf
->splines
[1].c
= 2*(cy
-ymin
);
205 ttf
->splines
[1].b
= ymin
+y
-2*cy
;
206 if ( comparespline(ps
,ttf
,tmin
,t
,err
) )
210 /* In a few cases, the following code will find a match when the above */
211 /* would not. We move the control point slightly along a vector normal */
212 /* to the vector between the end-points. What I really want is along */
213 /* a vector midway between the two slopes, but that's too hard to figure */
214 sq
= sqrt((x
-xmin
)*(x
-xmin
) + (y
-ymin
)*(y
-ymin
));
215 norm
.x
= (ymin
-y
)/sq
; norm
.y
= (x
-xmin
)/sq
;
217 ttf
->splines
[0].c
+= err
*norm
.x
;
218 ttf
->splines
[0].b
-= err
*norm
.x
;
219 ttf
->splines
[1].c
+= err
*norm
.y
;
220 ttf
->splines
[1].b
-= err
*norm
.y
;
221 if ( comparespline(ps
,ttf
,tmin
,t
,err
) )
224 ttf
->splines
[0].c
-= 2*err
*norm
.x
;
225 ttf
->splines
[0].b
+= 2*err
*norm
.x
;
226 ttf
->splines
[1].c
-= 2*err
*norm
.y
;
227 ttf
->splines
[1].b
+= 2*err
*norm
.y
;
228 if ( comparespline(ps
,ttf
,tmin
,t
,err
) )
231 ttf
->splines
[0].c
= 2*(cx
-xmin
);
232 ttf
->splines
[0].b
= xmin
+x
-2*cx
;
233 ttf
->splines
[1].c
= 2*(cy
-ymin
);
234 ttf
->splines
[1].b
= ymin
+y
-2*cy
;
239 static SplinePoint
*LinearSpline(Spline
*ps
,SplinePoint
*start
, real tmax
) {
241 Spline
*new = chunkalloc(sizeof(Spline
));
242 SplinePoint
*end
= chunkalloc(sizeof(SplinePoint
));
244 x
= ((ps
->splines
[0].a
*tmax
+ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
)*tmax
+ps
->splines
[0].d
;
245 y
= ((ps
->splines
[1].a
*tmax
+ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
)*tmax
+ps
->splines
[1].d
;
247 SplinePoint
*oldend
= ps
->to
;
248 end
->roundx
= oldend
->roundx
; end
->roundy
= oldend
->roundy
; end
->dontinterpolate
= oldend
->dontinterpolate
;
249 x
= oldend
->me
.x
; y
= oldend
->me
.y
; /* Want it to compare exactly */
251 end
->ttfindex
= 0xfffe;
252 end
->nextcpindex
= 0xfffe;
253 end
->me
.x
= end
->nextcp
.x
= end
->prevcp
.x
= x
;
254 end
->me
.y
= end
->nextcp
.y
= end
->prevcp
.y
= y
;
255 end
->nonextcp
= end
->noprevcp
= start
->nonextcp
= true;
256 new->from
= start
; start
->next
= new;
257 new->to
= end
; end
->prev
= new;
258 new->splines
[0].d
= start
->me
.x
;
259 new->splines
[0].c
= (x
-start
->me
.x
);
260 new->splines
[1].d
= start
->me
.y
;
261 new->splines
[1].c
= (y
-start
->me
.y
);
263 new->islinear
= new->knownlinear
= true;
267 static SplinePoint
*_ttfapprox(Spline
*ps
,real tmin
, real tmax
, SplinePoint
*start
) {
269 real dx
, dy
, ddim
, dt
, t
, err
;
270 real x
,y
, xmin
, ymin
;
271 real dxdtmin
, dydtmin
, dxdt
, dydt
;
275 int cnt
= -1, forceit
, unforceable
;
276 BasePoint end
, rend
, dend
;
279 rend
.x
= ((ps
->splines
[0].a
*tmax
+ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
)*tmax
+ ps
->splines
[0].d
;
280 rend
.y
= ((ps
->splines
[1].a
*tmax
+ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
)*tmax
+ ps
->splines
[1].d
;
281 end
.x
= rint( rend
.x
);
282 end
.y
= rint( rend
.y
);
283 dend
.x
= (3*ps
->splines
[0].a
*tmax
+2*ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
;
284 dend
.y
= (3*ps
->splines
[1].a
*tmax
+2*ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
;
285 memset(&ttf
,'\0',sizeof(ttf
));
287 bb
.minx
= bb
.maxx
= ps
->from
->me
.x
;
288 if ( ps
->from
->nextcp
.x
> bb
.maxx
) bb
.maxx
= ps
->from
->nextcp
.x
;
289 else if ( ps
->from
->nextcp
.x
< bb
.minx
) bb
.minx
= ps
->from
->nextcp
.x
;
290 if ( ps
->to
->prevcp
.x
> bb
.maxx
) bb
.maxx
= ps
->to
->prevcp
.x
;
291 else if ( ps
->to
->prevcp
.x
< bb
.minx
) bb
.minx
= ps
->to
->prevcp
.x
;
292 if ( ps
->to
->me
.x
> bb
.maxx
) bb
.maxx
= ps
->to
->me
.x
;
293 else if ( ps
->to
->me
.x
< bb
.minx
) bb
.minx
= ps
->to
->me
.x
;
294 bb
.miny
= bb
.maxy
= ps
->from
->me
.y
;
295 if ( ps
->from
->nextcp
.y
> bb
.maxy
) bb
.maxy
= ps
->from
->nextcp
.y
;
296 else if ( ps
->from
->nextcp
.y
< bb
.miny
) bb
.miny
= ps
->from
->nextcp
.y
;
297 if ( ps
->to
->prevcp
.y
> bb
.maxy
) bb
.maxy
= ps
->to
->prevcp
.y
;
298 else if ( ps
->to
->prevcp
.y
< bb
.miny
) bb
.miny
= ps
->to
->prevcp
.y
;
299 if ( ps
->to
->me
.y
> bb
.maxy
) bb
.maxy
= ps
->to
->me
.y
;
300 else if ( ps
->to
->me
.y
< bb
.miny
) bb
.miny
= ps
->to
->me
.y
;
307 dxdtmin
= (3*ps
->splines
[0].a
*tmin
+2*ps
->splines
[0].b
)*tmin
+ ps
->splines
[0].c
;
308 dydtmin
= (3*ps
->splines
[1].a
*tmin
+2*ps
->splines
[1].b
)*tmin
+ ps
->splines
[1].c
;
310 dx
= ((ps
->splines
[0].a
*tmax
+ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
)*tmax
-
311 ((ps
->splines
[0].a
*tmin
+ps
->splines
[0].b
)*tmin
+ps
->splines
[0].c
)*tmin
;
312 dy
= ((ps
->splines
[1].a
*tmax
+ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
)*tmax
-
313 ((ps
->splines
[1].a
*tmin
+ps
->splines
[1].b
)*tmin
+ps
->splines
[1].c
)*tmin
;
314 if ( dx
<0 ) dx
= -dx
;
315 if ( dy
<0 ) dy
= -dy
;
323 if (( err
= ddim
/3000 )<1 ) err
= 1;
326 (dend
.x
==0 && rint(start
->me
.x
)==end
.x
&& dy
<=10 && cnt
!=0) ||
327 (dend
.y
==0 && rint(start
->me
.y
)==end
.y
&& dx
<=10 && cnt
!=0) ) {
328 if ( cnt
==0 || start
->noprevcp
)
329 return( LinearSpline(ps
,start
,tmax
));
330 /* If the end point is very close to where we want to be, then just */
331 /* pretend it's right */
332 start
->prev
->splines
[0].b
+= ps
->to
->me
.x
-start
->me
.x
;
333 start
->prev
->splines
[1].b
+= ps
->to
->me
.y
-start
->me
.y
;
334 start
->prevcp
.x
+= rend
.x
-start
->me
.x
;
335 start
->prevcp
.y
+= rend
.y
-start
->me
.y
;
336 if ( start
->prev
!=NULL
&& !start
->prev
->from
->nonextcp
)
337 start
->prev
->from
->nextcp
= start
->prevcp
;
342 dt
= (tmax
-tmin
)/ddim
;
346 for ( t
=tmax
; t
>tmin
+dt
/128; t
-= dt
) { /* dt/128 is a hack to avoid rounding errors */
347 x
= ((ps
->splines
[0].a
*t
+ps
->splines
[0].b
)*t
+ps
->splines
[0].c
)*t
+ps
->splines
[0].d
;
348 y
= ((ps
->splines
[1].a
*t
+ps
->splines
[1].b
)*t
+ps
->splines
[1].c
)*t
+ps
->splines
[1].d
;
349 dxdt
= (3*ps
->splines
[0].a
*t
+2*ps
->splines
[0].b
)*t
+ ps
->splines
[0].c
;
350 dydt
= (3*ps
->splines
[1].a
*t
+2*ps
->splines
[1].b
)*t
+ ps
->splines
[1].c
;
351 /* if the slopes are parallel at the ends there can be no bezier quadratic */
352 /* (control point is where the splines intersect. But if they are */
353 /* parallel and colinear then there is a line between 'em */
354 if ( ( dxdtmin
==0 && dxdt
==0 ) || (dydtmin
==0 && dydt
==0) ||
355 ( dxdt
!=0 && dxdtmin
!=0 &&
356 RealNearish(dydt
/dxdt
,dydtmin
/dxdtmin
)) )
361 else if ( dxdtmin
==0 )
364 cx
= -(ymin
-(dydtmin
/dxdtmin
)*xmin
-y
+(dydt
/dxdt
)*x
)/(dydtmin
/dxdtmin
-dydt
/dxdt
);
367 else if ( dydtmin
==0 )
370 cy
= -(xmin
-(dxdtmin
/dydtmin
)*ymin
-x
+(dxdt
/dydt
)*y
)/(dxdtmin
/dydtmin
-dxdt
/dydt
);
371 if ( t
==tmax
&& ((cy
==y
&& cx
==x
) || (cy
==ymin
&& cx
==xmin
)) )
373 /* Make the quadratic spline from (xmin,ymin) through (cx,cy) to (x,y)*/
374 if ( forceit
|| buildtestquads(&ttf
,xmin
,ymin
,cx
,cy
,x
,y
,tmin
,t
,err
,ps
,&bb
)) {
375 if ( !forceit
&& !unforceable
&& (rend
.x
-x
)*(rend
.x
-x
)+(rend
.y
-y
)*(rend
.y
-y
)<4*4 ) {
379 sp
= MakeQuadSpline(start
,&ttf
,x
,y
,t
,ps
->to
);
387 ttf
.splines
[0].d
= xmin
;
388 ttf
.splines
[0].c
= x
-xmin
;
389 ttf
.splines
[0].b
= 0;
390 ttf
.splines
[1].d
= ymin
;
391 ttf
.splines
[1].c
= y
-ymin
;
392 ttf
.splines
[1].b
= 0;
393 if ( comparespline(ps
,&ttf
,tmin
,t
,err
) ) {
394 sp
= LinearSpline(ps
,start
,t
);
403 start
= LinearSpline(ps
,start
,tmin
);
407 static SplinePoint
*__ttfApprox(Spline
*ps
,real tmin
, real tmax
, SplinePoint
*start
) {
414 end
= _ttfapprox(ps
,tmin
,tmax
,start
);
415 if ( ps
->knownlinear
)
417 for ( s
=start
->next
; s
!=NULL
&& !s
->islinear
; s
=s
->to
->next
);
420 for ( s
=start
->next
; s
!=NULL
; s
=next
) {
422 SplinePointFree(s
->to
);
426 /* Hmm. With my algorithem, checking for points of inflection actually makes */
427 /* things worse. It uses more points and the splines don't join as nicely */
428 /* However if we get a bad match (a line) in the normal approx, then check */
429 /* Err... I was computing POI incorrectly. Above statement might not be correct*/
430 /* no points of inflection in quad splines */
432 i
= Spline2DFindPointsOfInflection(ps
, inflect
);
434 if ( RealNearish(inflect
[0],inflect
[1]) )
436 else if ( inflect
[0]>inflect
[1] ) {
437 real temp
= inflect
[0];
438 inflect
[0] = inflect
[1];
443 start
= _ttfapprox(ps
,tmin
,inflect
[0],start
);
446 start
= _ttfapprox(ps
,tmin
,inflect
[1],start
);
450 return( _ttfapprox(ps
,tmin
,tmax
,start
));
453 #if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION)
454 typedef struct qpoint
{
460 static int comparedata(Spline
*ps
,QPoint
*data
,int qfirst
,int qlast
,
464 double err
= round_to_int
? 1.5 : 1;
466 if ( qfirst
==qlast
) /* happened (was a bug) */
469 /* Control points diametrically opposed */
470 if ( (data
[qlast
-2].cp
.x
-ps
->to
->me
.x
)*(ps
->to
->prevcp
.x
-ps
->to
->me
.x
) +
471 (data
[qlast
-2].cp
.y
-ps
->to
->me
.y
)*(ps
->to
->prevcp
.y
-ps
->to
->me
.y
)<0 )
473 if ( (data
[qfirst
-1].cp
.x
-ps
->from
->me
.x
)*(ps
->from
->nextcp
.x
-ps
->from
->me
.x
) +
474 (data
[qfirst
-1].cp
.y
-ps
->from
->me
.y
)*(ps
->from
->nextcp
.y
-ps
->from
->me
.y
)<0 )
477 memset(&ttf
,0,sizeof(ttf
));
478 for ( i
=qfirst
; i
<qlast
; ++i
) {
479 ttf
.splines
[0].d
= data
[i
-1].bp
.x
;
480 ttf
.splines
[0].c
= 2*(data
[i
-1].cp
.x
-data
[i
-1].bp
.x
);
481 ttf
.splines
[0].b
= data
[i
-1].bp
.x
+data
[i
].bp
.x
-2*data
[i
-1].cp
.x
;
482 ttf
.splines
[1].d
= data
[i
-1].bp
.y
;
483 ttf
.splines
[1].c
= 2*(data
[i
-1].cp
.y
-data
[i
-1].bp
.y
);
484 ttf
.splines
[1].b
= data
[i
-1].bp
.y
+data
[i
].bp
.y
-2*data
[i
-1].cp
.y
;
485 if ( !comparespline(ps
,&ttf
,data
[i
-1].t
,data
[i
].t
,err
) )
491 static SplinePoint
*CvtDataToSplines(QPoint
*data
,int qfirst
,int qlast
,SplinePoint
*start
) {
495 for ( i
=qfirst
; i
<qlast
; ++i
) {
496 end
= SplinePointCreate(data
[i
].bp
.x
,data
[i
].bp
.y
);
497 start
->nextcp
= end
->prevcp
= data
[i
-1].cp
;
498 start
->nonextcp
= end
->noprevcp
= false;
499 if (( data
[i
-1].cp
.x
== data
[i
].bp
.x
&& data
[i
-1].cp
.y
== data
[i
].bp
.y
) ||
500 ( data
[i
-1].cp
.x
== start
->me
.x
&& data
[i
-1].cp
.y
== start
->me
.y
))
501 start
->nonextcp
= end
->noprevcp
= true;
502 SplineMake2(start
,end
);
508 static int SplineWithWellBehavedControlPoints(Spline
*ps
) {
509 BasePoint splineunit
;
510 double splinelen
, npos
, ppos
;
512 splineunit
.x
= ps
->to
->me
.x
- ps
->from
->me
.x
;
513 splineunit
.y
= ps
->to
->me
.y
- ps
->from
->me
.y
;
514 splinelen
= sqrt(splineunit
.x
*splineunit
.x
+ splineunit
.y
*splineunit
.y
);
515 if ( splinelen
!=0 ) {
516 splineunit
.x
/= splinelen
;
517 splineunit
.y
/= splinelen
;
520 npos
= (ps
->from
->nextcp
.x
-ps
->from
->me
.x
) * splineunit
.x
+
521 (ps
->from
->nextcp
.y
-ps
->from
->me
.y
) * splineunit
.y
;
522 ppos
= (ps
->to
->prevcp
.x
-ps
->from
->me
.x
) * splineunit
.x
+
523 (ps
->to
->prevcp
.y
-ps
->from
->me
.y
) * splineunit
.y
;
524 return( npos
>=0 && /* npos<=ppos &&*/ ppos
<=splinelen
);
527 static int PrettyApprox(Spline
*ps
,double tmin
, double tmax
,
528 QPoint
*data
, int qcnt
, int round_to_int
) {
530 double distance
, dx
, dy
, tstart
;
531 BasePoint end
, mid
, slopemin
, slopemid
, slopeend
;
532 BasePoint splineunit
, start
;
533 double splinelen
, midpos
, lastpos
, lastpos2
, cppos
;
534 int do_good_spline_check
;
540 slopemin
.x
= (3*ps
->splines
[0].a
*tmin
+2*ps
->splines
[0].b
)*tmin
+ps
->splines
[0].c
;
541 slopemin
.y
= (3*ps
->splines
[1].a
*tmin
+2*ps
->splines
[1].b
)*tmin
+ps
->splines
[1].c
;
542 if ( slopemin
.x
==0 && slopemin
.y
==0 ) {
543 double t
= tmin
+ (tmax
-tmin
)/256;
544 /* If there is no control point for this end point, then the slope is */
545 /* 0/0 at the end point. Which isn't useful, it leads to a quadratic */
546 /* control point at the end point, but this one is real because it */
547 /* is used to interpolate the next point, but we get all confused */
548 /* because we don't expect a real cp to be on the base point. */
549 slopemin
.x
= (3*ps
->splines
[0].a
*t
+2*ps
->splines
[0].b
)*t
+ps
->splines
[0].c
;
550 slopemin
.y
= (3*ps
->splines
[1].a
*t
+2*ps
->splines
[1].b
)*t
+ps
->splines
[1].c
;
553 end
.x
= ((ps
->splines
[0].a
*tmax
+ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
)*tmax
+ps
->splines
[0].d
;
554 end
.y
= ((ps
->splines
[1].a
*tmax
+ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
)*tmax
+ps
->splines
[1].d
;
555 slopeend
.x
= (3*ps
->splines
[0].a
*tmax
+2*ps
->splines
[0].b
)*tmax
+ps
->splines
[0].c
;
556 slopeend
.y
= (3*ps
->splines
[1].a
*tmax
+2*ps
->splines
[1].b
)*tmax
+ps
->splines
[1].c
;
557 if ( slopemin
.x
==0 && slopemin
.y
==0 ) {
558 double t
= tmax
- (tmax
-tmin
)/256;
559 /* Same problem as above, except at the other end */
560 slopeend
.x
= (3*ps
->splines
[0].a
*t
+2*ps
->splines
[0].b
)*t
+ps
->splines
[0].c
;
561 slopeend
.y
= (3*ps
->splines
[1].a
*t
+2*ps
->splines
[1].b
)*t
+ps
->splines
[1].c
;
564 start
.x
= data
[qcnt
-1].bp
.x
;
565 start
.y
= data
[qcnt
-1].bp
.y
;
566 splineunit
.x
= end
.x
- start
.x
;
567 splineunit
.y
= end
.y
- start
.y
;
568 splinelen
= sqrt(splineunit
.x
*splineunit
.x
+ splineunit
.y
*splineunit
.y
);
569 if ( splinelen
!=0 ) {
570 splineunit
.x
/= splinelen
;
571 splineunit
.y
/= splinelen
;
573 do_good_spline_check
= SplineWithWellBehavedControlPoints(ps
);
575 if ( round_to_int
&& tmax
!=1 ) {
576 end
.x
= rint( end
.x
);
577 end
.y
= rint( end
.y
);
580 dx
= end
.x
-data
[qcnt
-1].bp
.x
; dy
= end
.y
-data
[qcnt
-1].bp
.y
;
581 distance
= dx
*dx
+ dy
*dy
;
584 /* This is meaningless in truetype, use a line */
585 data
[qcnt
-1].cp
= data
[qcnt
-1].bp
;
591 for ( ptcnt
=0; ptcnt
<10; ++ptcnt
) {
592 if ( ptcnt
>1 && distance
/(ptcnt
*ptcnt
)<100 )
593 return( -1 ); /* Points too close for a good approx */
595 data2
[ptcnt
+1].bp
= end
;
596 lastpos
=0; lastpos2
= splinelen
;
597 for ( i
=0; i
<=ptcnt
; ++i
) {
598 tstart
= (tmin
*(ptcnt
-i
) + tmax
*(i
+1))/(ptcnt
+1);
599 mid
.x
= ((ps
->splines
[0].a
*tstart
+ps
->splines
[0].b
)*tstart
+ps
->splines
[0].c
)*tstart
+ps
->splines
[0].d
;
600 mid
.y
= ((ps
->splines
[1].a
*tstart
+ps
->splines
[1].b
)*tstart
+ps
->splines
[1].c
)*tstart
+ps
->splines
[1].d
;
602 slopemid
.x
= (3*ps
->splines
[0].a
*tstart
+2*ps
->splines
[0].b
)*tstart
+ps
->splines
[0].c
;
603 slopemid
.y
= (3*ps
->splines
[1].a
*tstart
+2*ps
->splines
[1].b
)*tstart
+ps
->splines
[1].c
;
605 data
[q
-1].cp
.x
=mid
.x
;
606 else if ( slopemin
.x
==0 )
607 data
[q
-1].cp
.x
=data
[q
-1].bp
.x
;
608 else if ( RealNear(slopemin
.y
/slopemin
.x
,slopemid
.y
/slopemid
.x
) )
611 data
[q
-1].cp
.x
= -(data
[q
-1].bp
.y
-(slopemin
.y
/slopemin
.x
)*data
[q
-1].bp
.x
-mid
.y
+(slopemid
.y
/slopemid
.x
)*mid
.x
)/(slopemin
.y
/slopemin
.x
-slopemid
.y
/slopemid
.x
);
613 data
[q
-1].cp
.y
=mid
.y
;
614 else if ( slopemin
.y
==0 )
615 data
[q
-1].cp
.y
=data
[q
-1].bp
.y
;
616 else if ( RealNear(slopemin
.x
/slopemin
.y
,slopemid
.x
/slopemid
.y
) )
619 data
[q
-1].cp
.y
= -(data
[q
-1].bp
.x
-(slopemin
.x
/slopemin
.y
)*data
[q
-1].bp
.y
-mid
.x
+(slopemid
.x
/slopemid
.y
)*mid
.y
)/(slopemin
.x
/slopemin
.y
-slopemid
.x
/slopemid
.y
);
621 data
[q
-1].cp
.x
= 2*data
[q
-1].bp
.x
- data
[q
-2].cp
.x
;
622 data
[q
-1].cp
.y
= 2*data
[q
-1].bp
.y
- data
[q
-2].cp
.y
;
625 midpos
= (mid
.x
-start
.x
)*splineunit
.x
+ (mid
.y
-start
.y
)*splineunit
.y
;
626 cppos
= (data
[q
-1].cp
.x
-start
.x
)*splineunit
.x
+ (data
[q
-1].cp
.y
-start
.y
)*splineunit
.y
;
628 if ( ((do_good_spline_check
|| i
!=0 ) && cppos
<lastpos
) || cppos
>midpos
) {
629 i
= 0; /* Means we failed */
635 data
[q
++].t
= tstart
;
637 tstart
= (tmax
*(ptcnt
-i
) + tmin
*(i
+1))/(ptcnt
+1);
638 mid
.x
= ((ps
->splines
[0].a
*tstart
+ps
->splines
[0].b
)*tstart
+ps
->splines
[0].c
)*tstart
+ps
->splines
[0].d
;
639 mid
.y
= ((ps
->splines
[1].a
*tstart
+ps
->splines
[1].b
)*tstart
+ps
->splines
[1].c
)*tstart
+ps
->splines
[1].d
;
641 slopemid
.x
= (3*ps
->splines
[0].a
*tstart
+2*ps
->splines
[0].b
)*tstart
+ps
->splines
[0].c
;
642 slopemid
.y
= (3*ps
->splines
[1].a
*tstart
+2*ps
->splines
[1].b
)*tstart
+ps
->splines
[1].c
;
644 data2
[ptcnt
-i
].cp
.x
=mid
.x
;
645 else if ( slopeend
.x
==0 )
646 data2
[ptcnt
-i
].cp
.x
=data2
[ptcnt
-i
+1].bp
.x
;
647 else if ( RealNear(slopeend
.y
/slopeend
.x
,slopemid
.y
/slopemid
.x
) )
650 data2
[ptcnt
-i
].cp
.x
= -(data2
[ptcnt
-i
+1].bp
.y
-(slopeend
.y
/slopeend
.x
)*data2
[ptcnt
-i
+1].bp
.x
-mid
.y
+(slopemid
.y
/slopemid
.x
)*mid
.x
)/(slopeend
.y
/slopeend
.x
-slopemid
.y
/slopemid
.x
);
652 data2
[ptcnt
-i
].cp
.y
=mid
.y
;
653 else if ( slopeend
.y
==0 )
654 data2
[ptcnt
-i
].cp
.y
=data2
[ptcnt
-i
+1].bp
.y
;
655 else if ( RealNear(slopeend
.x
/slopeend
.y
,slopemid
.x
/slopemid
.y
) )
658 data2
[ptcnt
-i
].cp
.y
= -(data2
[ptcnt
-i
+1].bp
.x
-(slopeend
.x
/slopeend
.y
)*data2
[ptcnt
-i
+1].bp
.y
-mid
.x
+(slopemid
.x
/slopemid
.y
)*mid
.y
)/(slopeend
.x
/slopeend
.y
-slopemid
.x
/slopemid
.y
);
660 data2
[ptcnt
-i
].cp
.x
= 2*data2
[ptcnt
-i
+1].bp
.x
- data2
[ptcnt
-i
+1].cp
.x
;
661 data2
[ptcnt
-i
].cp
.y
= 2*data2
[ptcnt
-i
+1].bp
.y
- data2
[ptcnt
-i
+1].cp
.y
;
663 data2
[ptcnt
-i
].bp
= mid
;
665 midpos
= (mid
.x
-start
.x
)*splineunit
.x
+ (mid
.y
-start
.y
)*splineunit
.y
;
666 cppos
= (data2
[ptcnt
-i
].cp
.x
-start
.x
)*splineunit
.x
+ (data2
[ptcnt
-i
].cp
.y
-start
.y
)*splineunit
.y
;
667 if ( ((do_good_spline_check
|| i
!=0 ) && cppos
>lastpos2
) || cppos
<midpos
) {
668 i
= 0; /* Means we failed */
676 if ( (data2
[ptcnt
+1].bp
.x
-data2
[ptcnt
].bp
.x
)*(data2
[ptcnt
].cp
.x
-data2
[ptcnt
].bp
.x
)<0 ||
677 (data2
[ptcnt
+1].bp
.y
-data2
[ptcnt
].bp
.y
)*(data2
[ptcnt
].cp
.y
-data2
[ptcnt
].bp
.y
)<0 ) {
678 /* data2 are bad ... don't use them */;
679 } else if ( (data
[qcnt
-1].bp
.x
-data
[qcnt
].bp
.x
)*(data
[qcnt
-1].cp
.x
-data
[qcnt
].bp
.x
)<0 ||
680 (data
[qcnt
-1].bp
.y
-data
[qcnt
].bp
.y
)*(data
[qcnt
-1].cp
.y
-data
[qcnt
].bp
.y
)<0 ) {
682 for ( i
=0; i
<=ptcnt
; ++i
) {
683 data
[qcnt
+i
-1].cp
= data2
[i
].cp
;
684 data
[qcnt
+i
-1].bp
= data2
[i
].bp
;
687 for ( i
=0; i
<=ptcnt
; ++i
) {
689 data
[qcnt
+i
-1].cp
.x
= (data
[qcnt
+i
-1].cp
.x
*(ptcnt
-i
) + data2
[i
].cp
.x
*i
)/ptcnt
;
690 data
[qcnt
+i
-1].cp
.y
= (data
[qcnt
+i
-1].cp
.y
*(ptcnt
-i
) + data2
[i
].cp
.y
*i
)/ptcnt
;
694 if ( round_to_int
) {
695 for ( i
=0; i
<=ptcnt
; ++i
) {
696 data
[qcnt
+i
-1].cp
.x
= rint( data
[qcnt
+i
-1].cp
.x
);
697 data
[qcnt
+i
-1].cp
.y
= rint( data
[qcnt
+i
-1].cp
.y
);
700 for ( i
=0; i
<ptcnt
; ++i
) {
701 data
[qcnt
+i
].bp
.x
= (data
[qcnt
+i
].cp
.x
+ data
[qcnt
+i
-1].cp
.x
)/2;
702 data
[qcnt
+i
].bp
.y
= (data
[qcnt
+i
].cp
.y
+ data
[qcnt
+i
-1].cp
.y
)/2;
704 if ( comparedata(ps
,data
,qcnt
,q
,round_to_int
))
711 static SplinePoint
*AlreadyQuadraticCheck(Spline
*ps
, SplinePoint
*start
) {
714 if ( (RealNearish(ps
->splines
[0].a
,0) && RealNearish(ps
->splines
[1].a
,0)) ||
715 ((ps
->splines
[0].b
!=0 && RealNearish(ps
->splines
[0].a
/ps
->splines
[0].b
,0)) &&
716 (ps
->splines
[1].b
!=0 && RealNearish(ps
->splines
[1].a
/ps
->splines
[1].b
,0))) ) {
717 /* Already Quadratic, just need to find the control point */
718 /* Or linear, in which case we don't need to do much of anything */
720 sp
= chunkalloc(sizeof(SplinePoint
));
721 sp
->me
.x
= ps
->to
->me
.x
; sp
->me
.y
= ps
->to
->me
.y
;
722 sp
->roundx
= ps
->to
->roundx
; sp
->roundy
= ps
->to
->roundy
; sp
->dontinterpolate
= ps
->to
->dontinterpolate
;
723 sp
->ttfindex
= 0xfffe;
724 sp
->nextcpindex
= 0xfffe;
726 spline
= chunkalloc(sizeof(Spline
));
727 spline
->order2
= true;
728 spline
->from
= start
;
730 spline
->splines
[0] = ps
->splines
[0]; spline
->splines
[1] = ps
->splines
[1];
731 start
->next
= sp
->prev
= spline
;
732 if ( ps
->knownlinear
) {
733 spline
->islinear
= spline
->knownlinear
= true;
734 start
->nonextcp
= sp
->noprevcp
= true;
735 start
->nextcp
= start
->me
;
738 start
->nonextcp
= sp
->noprevcp
= false;
739 start
->nextcp
.x
= sp
->prevcp
.x
= (ps
->splines
[0].c
+2*ps
->splines
[0].d
)/2;
740 start
->nextcp
.y
= sp
->prevcp
.y
= (ps
->splines
[1].c
+2*ps
->splines
[1].d
)/2;
747 static SplinePoint
*ttfApprox(Spline
*ps
, SplinePoint
*start
) {
748 #if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION)
749 extended magicpoints
[6], last
;
753 /* The end points are at integer points, or one coord is at half while */
754 /* the other is at an integer (ie. condition for ttf interpolated point)*/
755 ((ps
->from
->me
.x
==rint(ps
->from
->me
.x
) &&
756 ps
->from
->me
.y
==rint(ps
->from
->me
.y
)) ||
757 (ps
->from
->me
.x
==rint(ps
->from
->me
.x
) &&
758 ps
->from
->me
.x
==ps
->from
->nextcp
.x
&&
759 ps
->from
->me
.y
!=ps
->from
->nextcp
.y
&&
760 2*ps
->from
->me
.y
==rint(2*ps
->from
->me
.y
)) ||
761 (ps
->from
->me
.y
==rint(ps
->from
->me
.y
) &&
762 ps
->from
->me
.y
==ps
->from
->nextcp
.y
&&
763 ps
->from
->me
.x
!=ps
->from
->nextcp
.x
&&
764 2*ps
->from
->me
.x
==rint(2*ps
->from
->me
.x
)) ) &&
765 ((ps
->to
->me
.x
== rint(ps
->to
->me
.x
) &&
766 ps
->to
->me
.y
== rint(ps
->to
->me
.y
)) ||
767 (ps
->to
->me
.x
==rint(ps
->to
->me
.x
) &&
768 ps
->to
->me
.x
==ps
->to
->prevcp
.x
&&
769 ps
->to
->me
.y
!=ps
->to
->prevcp
.y
&&
770 2*ps
->to
->me
.y
==rint(2*ps
->to
->me
.y
)) ||
771 (ps
->to
->me
.y
==rint(ps
->to
->me
.y
) &&
772 ps
->to
->me
.y
==ps
->to
->prevcp
.y
&&
773 ps
->to
->me
.x
!=ps
->to
->prevcp
.x
&&
774 2*ps
->to
->me
.x
==rint(2*ps
->to
->me
.x
)) );
777 /* Divide the spline up at extrema and points of inflection. The first */
778 /* because ttf splines should have points at their extrema, the second */
779 /* because quadratic splines can't have points of inflection. */
780 /* Let's not do the first (extrema) AddExtrema does this better and we */
781 /* don't want unneeded extrema. */
782 /* And sometimes we don't want to look at the points of inflection either*/
784 if (( ret
= AlreadyQuadraticCheck(ps
,start
))!=NULL
)
787 #if !defined(FONTFORGE_CONFIG_NON_SYMMETRIC_QUADRATIC_CONVERSION)
789 data
[0].bp
= ps
->from
->me
;
791 qcnt
= PrettyApprox(ps
,0,1,data
,qcnt
,round_to_int
);
793 return( CvtDataToSplines(data
,1,qcnt
,start
));
796 /* cnt = Spline2DFindExtrema(ps,magicpoints);*/
798 cnt
+= Spline2DFindPointsOfInflection(ps
,magicpoints
+cnt
);
800 /* remove points outside range */
801 for ( i
=0; i
<cnt
; ++i
) {
802 if ( magicpoints
[i
]<=0 || magicpoints
[i
]>=1 ) {
803 for ( j
=i
+1; j
<cnt
; ++j
)
804 magicpoints
[j
-1] = magicpoints
[j
];
810 for ( i
=0; i
<cnt
; ++i
) for ( j
=i
+1; j
<cnt
; ++j
) {
811 if ( magicpoints
[i
]>magicpoints
[j
] ) {
812 double temp
= magicpoints
[i
];
813 magicpoints
[i
] = magicpoints
[j
];
814 magicpoints
[j
] = temp
;
817 /* Remove duplicates */
818 for ( i
=1; i
<cnt
; ++i
) {
819 while ( i
<cnt
&& RealNear(magicpoints
[i
-1],magicpoints
[i
])) {
821 for ( j
=i
; j
<cnt
; ++j
)
822 magicpoints
[j
] = magicpoints
[j
+1];
823 magicpoints
[cnt
] = -1;
829 for ( i
=0; i
<cnt
; ++i
) {
830 qcnt
= PrettyApprox(ps
,last
,magicpoints
[i
],data
,qcnt
,round_to_int
);
831 last
= magicpoints
[i
];
833 qcnt
= PrettyApprox(ps
,last
,1,data
,qcnt
,round_to_int
);
835 return( CvtDataToSplines(data
,1,qcnt
,start
));
838 return( __ttfApprox(ps
,0,1,start
));
841 static void ttfCleanup(SplinePoint
*from
) {
842 SplinePoint
*test
, *next
;
844 for ( test
= from
; test
->next
!=NULL
; test
= next
) {
845 next
= test
->next
->to
;
846 /* Too close together to be meaningful when output as ttf */
847 if ( rint(test
->me
.x
) == rint(next
->me
.x
) &&
848 rint(test
->me
.y
) == rint(next
->me
.y
) ) {
849 if ( next
->next
==NULL
|| next
==from
) {
852 next
->prevcp
= test
->prevcp
;
853 next
->noprevcp
= test
->noprevcp
;
854 next
->prev
= test
->prev
;
855 next
->prev
->to
= next
;
856 SplineFree(test
->next
);
857 SplinePointFree(test
);
859 test
->nextcp
= next
->nextcp
;
860 test
->nonextcp
= next
->nonextcp
;
861 test
->next
= next
->next
;
862 test
->next
->from
= test
;
863 SplineFree(next
->prev
);
864 SplinePointFree(next
);
865 next
= test
->next
->to
;
873 SplinePoint
*SplineTtfApprox(Spline
*ps
) {
875 from
= chunkalloc(sizeof(SplinePoint
));
877 from
->hintmask
= NULL
;
882 SplineSet
*SSttfApprox(SplineSet
*ss
) {
883 SplineSet
*ret
= chunkalloc(sizeof(SplineSet
));
884 Spline
*spline
, *first
;
886 ret
->first
= chunkalloc(sizeof(SplinePoint
));
887 *ret
->first
= *ss
->first
;
888 if ( ret
->first
->hintmask
!= NULL
) {
889 ret
->first
->hintmask
= chunkalloc(sizeof(HintMask
));
890 memcpy(ret
->first
->hintmask
,ss
->first
->hintmask
,sizeof(HintMask
));
892 ret
->last
= ret
->first
;
895 for ( spline
=ss
->first
->next
; spline
!=NULL
&& spline
!=first
; spline
=spline
->to
->next
) {
896 ret
->last
= ttfApprox(spline
,ret
->last
);
897 ret
->last
->ptindex
= spline
->to
->ptindex
;
898 ret
->last
->ttfindex
= spline
->to
->ttfindex
;
899 ret
->last
->nextcpindex
= spline
->to
->nextcpindex
;
900 if ( spline
->to
->hintmask
!= NULL
) {
901 ret
->last
->hintmask
= chunkalloc(sizeof(HintMask
));
902 memcpy(ret
->last
->hintmask
,spline
->to
->hintmask
,sizeof(HintMask
));
904 if ( first
==NULL
) first
= spline
;
906 if ( ss
->first
==ss
->last
) {
907 if ( ret
->last
!=ret
->first
) {
908 ret
->first
->prevcp
= ret
->last
->prevcp
;
909 ret
->first
->noprevcp
= ret
->last
->noprevcp
;
910 ret
->first
->prev
= ret
->last
->prev
;
911 ret
->last
->prev
->to
= ret
->first
;
912 SplinePointFree(ret
->last
);
913 ret
->last
= ret
->first
;
916 ttfCleanup(ret
->first
);
917 SPLCatagorizePoints(ret
);
921 SplineSet
*SplineSetsTTFApprox(SplineSet
*ss
) {
922 SplineSet
*head
=NULL
, *last
, *cur
;
925 cur
= SSttfApprox(ss
);
936 SplineSet
*SSPSApprox(SplineSet
*ss
) {
937 SplineSet
*ret
= chunkalloc(sizeof(SplineSet
));
938 Spline
*spline
, *first
;
941 ret
->first
= chunkalloc(sizeof(SplinePoint
));
942 *ret
->first
= *ss
->first
;
943 if ( ret
->first
->hintmask
!= NULL
) {
944 ret
->first
->hintmask
= chunkalloc(sizeof(HintMask
));
945 memcpy(ret
->first
->hintmask
,ss
->first
->hintmask
,sizeof(HintMask
));
947 ret
->last
= ret
->first
;
950 for ( spline
=ss
->first
->next
; spline
!=NULL
&& spline
!=first
; spline
=spline
->to
->next
) {
951 to
= chunkalloc(sizeof(SplinePoint
));
953 if ( to
->hintmask
!= NULL
) {
954 to
->hintmask
= chunkalloc(sizeof(HintMask
));
955 memcpy(to
->hintmask
,spline
->to
->hintmask
,sizeof(HintMask
));
957 if ( !spline
->knownlinear
) {
958 ret
->last
->nextcp
.x
= spline
->splines
[0].c
/3 + ret
->last
->me
.x
;
959 ret
->last
->nextcp
.y
= spline
->splines
[1].c
/3 + ret
->last
->me
.y
;
960 to
->prevcp
.x
= ret
->last
->nextcp
.x
+ (spline
->splines
[0].b
+spline
->splines
[0].c
)/3;
961 to
->prevcp
.y
= ret
->last
->nextcp
.y
+ (spline
->splines
[1].b
+spline
->splines
[1].c
)/3;
963 SplineMake3(ret
->last
,to
);
965 if ( first
==NULL
) first
= spline
;
967 if ( ss
->first
==ss
->last
) {
968 if ( ret
->last
!=ret
->first
) {
969 ret
->first
->prevcp
= ret
->last
->prevcp
;
970 ret
->first
->noprevcp
= ret
->last
->noprevcp
;
971 ret
->first
->prev
= ret
->last
->prev
;
972 ret
->last
->prev
->to
= ret
->first
;
973 SplinePointFree(ret
->last
);
974 ret
->last
= ret
->first
;
977 ret
->is_clip_path
= ss
->is_clip_path
;
981 SplineSet
*SplineSetsPSApprox(SplineSet
*ss
) {
982 SplineSet
*head
=NULL
, *last
, *cur
;
985 cur
= SSPSApprox(ss
);
996 void SCConvertLayerToOrder2(SplineChar
*sc
,int layer
) {
1002 new = SplineSetsTTFApprox(sc
->layers
[layer
].splines
);
1003 SplinePointListsFree(sc
->layers
[layer
].splines
);
1004 sc
->layers
[layer
].splines
= new;
1006 UndoesFree(sc
->layers
[layer
].undoes
);
1007 UndoesFree(sc
->layers
[layer
].redoes
);
1008 sc
->layers
[layer
].undoes
= NULL
;
1009 sc
->layers
[layer
].redoes
= NULL
;
1010 sc
->layers
[layer
].order2
= true;
1012 MinimumDistancesFree(sc
->md
); sc
->md
= NULL
;
1015 void SCConvertToOrder2(SplineChar
*sc
) {
1021 for ( layer
=ly_back
; layer
<sc
->layer_cnt
; ++layer
)
1022 SCConvertLayerToOrder2(sc
,layer
);
1026 /* ************************************************************************** */
1028 void SplineRefigure2(Spline
*spline
) {
1029 SplinePoint
*from
= spline
->from
, *to
= spline
->to
;
1030 Spline1D
*xsp
= &spline
->splines
[0], *ysp
= &spline
->splines
[1];
1034 if ( RealNear(from
->me
.x
,to
->me
.x
) && RealNear(from
->me
.y
,to
->me
.y
))
1035 IError("Zero length spline created");
1037 if ( spline
->acceptableextrema
)
1040 if ( from
->nonextcp
|| to
->noprevcp
||
1041 ( from
->nextcp
.x
==from
->me
.x
&& from
->nextcp
.y
== from
->me
.y
) ||
1042 ( to
->prevcp
.x
==to
->me
.x
&& to
->prevcp
.y
== to
->me
.y
)) {
1043 from
->nonextcp
= to
->noprevcp
= true;
1044 from
->nextcp
= from
->me
;
1045 to
->prevcp
= to
->me
;
1048 if ( from
->nonextcp
&& to
->noprevcp
)
1050 else if ( from
->nonextcp
|| to
->noprevcp
|| from
->nextcp
.x
!=to
->prevcp
.x
||
1051 from
->nextcp
.y
!=to
->prevcp
.y
) {
1052 if ( RealNear(from
->nextcp
.x
,to
->prevcp
.x
) &&
1053 RealNear(from
->nextcp
.y
,to
->prevcp
.y
)) {
1054 from
->nextcp
.x
= to
->prevcp
.x
= (from
->nextcp
.x
+to
->prevcp
.x
)/2;
1055 from
->nextcp
.y
= to
->prevcp
.y
= (from
->nextcp
.y
+to
->prevcp
.y
)/2;
1057 IError("Invalid 2nd order spline in SplineRefigure2" );
1059 /* I don't want these to go away when I'm debugging. I want to */
1060 /* know how I got them */
1061 from
->nextcp
.x
= to
->prevcp
.x
= (from
->nextcp
.x
+to
->prevcp
.x
)/2;
1062 from
->nextcp
.y
= to
->prevcp
.y
= (from
->nextcp
.y
+to
->prevcp
.y
)/2;
1067 xsp
->d
= from
->me
.x
; ysp
->d
= from
->me
.y
;
1068 if ( from
->nonextcp
&& to
->noprevcp
) {
1069 spline
->islinear
= true;
1070 xsp
->c
= to
->me
.x
-from
->me
.x
;
1071 ysp
->c
= to
->me
.y
-from
->me
.y
;
1072 xsp
->a
= xsp
->b
= 0;
1073 ysp
->a
= ysp
->b
= 0;
1075 /* from p. 393 (Operator Details, curveto) Postscript Lang. Ref. Man. (Red book) */
1076 xsp
->c
= 2*(from
->nextcp
.x
-from
->me
.x
);
1077 ysp
->c
= 2*(from
->nextcp
.y
-from
->me
.y
);
1078 xsp
->b
= to
->me
.x
-from
->me
.x
-xsp
->c
;
1079 ysp
->b
= to
->me
.y
-from
->me
.y
-ysp
->c
;
1082 if ( RealNear(xsp
->c
,0)) xsp
->c
=0;
1083 if ( RealNear(ysp
->c
,0)) ysp
->c
=0;
1084 if ( RealNear(xsp
->b
,0)) xsp
->b
=0;
1085 if ( RealNear(ysp
->b
,0)) ysp
->b
=0;
1086 spline
->islinear
= false;
1087 if ( ysp
->b
==0 && xsp
->b
==0 )
1088 spline
->islinear
= true; /* This seems extremely unlikely... */
1090 if ( isnan(ysp
->b
) || isnan(xsp
->b
) )
1091 IError("NaN value in spline creation");
1092 LinearApproxFree(spline
->approx
);
1093 spline
->approx
= NULL
;
1094 spline
->knowncurved
= false;
1095 spline
->knownlinear
= spline
->islinear
;
1096 SplineIsLinear(spline
);
1097 spline
->isquadratic
= !spline
->knownlinear
;
1098 spline
->order2
= true;
1100 if ( spline
->acceptableextrema
) {
1101 /* I don't check "d", because changes to that reflect simple */
1102 /* translations which will not affect the shape of the spline */
1103 /* (I don't check "a" because it is always 0 in a quadratic spline) */
1104 if ( !RealNear(old
.splines
[0].b
,spline
->splines
[0].b
) ||
1105 !RealNear(old
.splines
[0].c
,spline
->splines
[0].c
) ||
1106 !RealNear(old
.splines
[1].b
,spline
->splines
[1].b
) ||
1107 !RealNear(old
.splines
[1].c
,spline
->splines
[1].c
) )
1108 spline
->acceptableextrema
= false;
1112 void SplineRefigure(Spline
*spline
) {
1115 if ( spline
->order2
)
1116 SplineRefigure2(spline
);
1118 SplineRefigure3(spline
);
1121 static int IsHV(Spline
*spline
, int isfrom
) {
1131 if ( sp
->me
.x
== sp
->prevcp
.x
)
1132 return( 2 ); /* Vertical */
1133 else if ( sp
->me
.y
== sp
->prevcp
.y
)
1134 return( 1 ); /* Horizontal */
1136 return( 0 ); /* Neither */
1141 if ( sp
->me
.x
== sp
->nextcp
.x
)
1142 return( 2 ); /* Vertical */
1143 else if ( sp
->me
.y
== sp
->nextcp
.y
)
1144 return( 1 ); /* Horizontal */
1146 return( 0 ); /* Neither */
1150 void SplineRefigureFixup(Spline
*spline
) {
1151 SplinePoint
*from
, *to
, *prev
, *next
;
1152 BasePoint foff
, toff
, unit
, new;
1154 enum pointtype fpt
, tpt
;
1156 extern int snaptoint
;
1158 if ( !spline
->order2
) {
1159 SplineRefigure3(spline
);
1162 from
= spline
->from
; to
= spline
->to
;
1163 if ( from
->pointtype
==pt_hvcurve
&& to
->pointtype
==pt_hvcurve
) {
1165 if ( !IsHV(from
->prev
,0) && !IsHV(to
->next
,1) ) {
1166 if ( to
->me
.x
== from
->me
.x
) {
1167 from
->nextcp
.x
= to
->prevcp
.x
= to
->me
.x
;
1168 from
->nextcp
.y
= to
->prevcp
.y
= (from
->me
.y
+from
->me
.y
)/2;
1169 } else if ( to
->me
.y
==from
->me
.y
) {
1170 from
->nextcp
.y
= to
->prevcp
.y
= to
->me
.y
;
1171 from
->nextcp
.x
= to
->prevcp
.x
= (from
->me
.x
+from
->me
.x
)/2;
1172 /* Assume they are drawing clockwise */
1173 } else if (( to
->me
.x
>from
->me
.x
&& to
->me
.y
>=from
->me
.y
) ||
1174 (to
->me
.x
<from
->me
.x
&& to
->me
.y
<=from
->me
.y
)) {
1175 from
->nextcp
.x
= to
->prevcp
.x
= from
->me
.x
;
1176 from
->nextcp
.y
= to
->prevcp
.y
= to
->me
.y
;
1178 from
->nextcp
.x
= to
->prevcp
.x
= to
->me
.x
;
1179 from
->nextcp
.y
= to
->prevcp
.y
= from
->me
.y
;
1181 } else if ( !IsHV(to
->next
,1)) {
1182 if ( IsHV(from
->prev
,0)==1 ) {
1183 from
->nextcp
.x
= to
->prevcp
.x
= to
->me
.x
;
1184 from
->nextcp
.y
= to
->prevcp
.y
= from
->me
.y
;
1186 from
->nextcp
.x
= to
->prevcp
.x
= from
->me
.x
;
1187 from
->nextcp
.y
= to
->prevcp
.y
= to
->me
.y
;
1189 } else if ( !IsHV(from
->prev
,0)) {
1190 if ( IsHV(to
->next
,1)==1 ) {
1191 from
->nextcp
.x
= to
->prevcp
.x
= from
->me
.x
;
1192 from
->nextcp
.y
= to
->prevcp
.y
= to
->me
.y
;
1194 from
->nextcp
.x
= to
->prevcp
.x
= to
->me
.x
;
1195 from
->nextcp
.y
= to
->prevcp
.y
= from
->me
.y
;
1198 if ( IsHV(from
->prev
,0)==1 && IsHV(to
->next
,1)==2 ) {
1199 from
->nextcp
.x
= to
->prevcp
.x
= to
->me
.x
;
1200 from
->nextcp
.y
= to
->prevcp
.y
= from
->me
.y
;
1201 } else if ( IsHV(from
->prev
,0)==2 && IsHV(to
->next
,1)==1 ) {
1202 from
->nextcp
.x
= to
->prevcp
.x
= from
->me
.x
;
1203 from
->nextcp
.y
= to
->prevcp
.y
= to
->me
.y
;
1208 to
->noprevcp
= from
->nonextcp
= false;
1212 unit
.x
= from
->nextcp
.x
-from
->me
.x
;
1213 unit
.y
= from
->nextcp
.y
-from
->me
.y
;
1214 len
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1216 unit
.x
/= len
; unit
.y
/= len
;
1218 if ( (fpt
= from
->pointtype
)==pt_hvcurve
) fpt
= pt_curve
;
1219 if ( (tpt
= to
->pointtype
)==pt_hvcurve
) tpt
= pt_curve
;
1220 if ( from
->nextcpdef
&& to
->prevcpdef
) switch ( fpt
*3+tpt
) {
1221 case pt_corner
*3+pt_corner
:
1222 case pt_corner
*3+pt_tangent
:
1223 case pt_tangent
*3+pt_corner
:
1224 case pt_tangent
*3+pt_tangent
:
1225 from
->nonextcp
= to
->noprevcp
= true;
1226 from
->nextcp
= from
->me
;
1227 to
->prevcp
= to
->me
;
1229 case pt_curve
*3+pt_curve
:
1230 case pt_curve
*3+pt_corner
:
1231 case pt_corner
*3+pt_curve
:
1232 case pt_tangent
*3+pt_curve
:
1233 case pt_curve
*3+pt_tangent
:
1234 if ( from
->prev
!=NULL
&& (from
->pointtype
==pt_tangent
|| from
->pointtype
==pt_hvcurve
)) {
1235 prev
= from
->prev
->from
;
1236 foff
.x
= prev
->me
.x
;
1237 foff
.y
= prev
->me
.y
;
1238 } else if ( from
->prev
!=NULL
) {
1239 prev
= from
->prev
->from
;
1240 foff
.x
= to
->me
.x
-prev
->me
.x
+ from
->me
.x
;
1241 foff
.y
= to
->me
.y
-prev
->me
.y
+ from
->me
.y
;
1243 foff
.x
= from
->me
.x
+ (to
->me
.x
-from
->me
.x
)-(to
->me
.y
-from
->me
.y
);
1244 foff
.y
= from
->me
.y
+ (to
->me
.x
-from
->me
.x
)+(to
->me
.y
-from
->me
.y
);
1247 if ( to
->next
!=NULL
&& (to
->pointtype
==pt_tangent
|| to
->pointtype
==pt_hvcurve
)) {
1248 next
= to
->next
->to
;
1249 toff
.x
= next
->me
.x
;
1250 toff
.y
= next
->me
.y
;
1251 } else if ( to
->next
!=NULL
) {
1252 next
= to
->next
->to
;
1253 toff
.x
= next
->me
.x
-from
->me
.x
+ to
->me
.x
;
1254 toff
.y
= next
->me
.y
-from
->me
.y
+ to
->me
.y
;
1256 toff
.x
= to
->me
.x
+ (to
->me
.x
-from
->me
.x
)+(to
->me
.y
-from
->me
.y
);
1257 toff
.y
= to
->me
.y
- (to
->me
.x
-from
->me
.x
)+(to
->me
.y
-from
->me
.y
);
1260 if (( from
->pointtype
==pt_hvcurve
&& foff
.x
!=from
->me
.x
&& foff
.y
!=from
->me
.y
) ||
1261 ( to
->pointtype
==pt_hvcurve
&& toff
.x
!=to
->me
.x
&& toff
.y
!=to
->me
.y
)) {
1262 if ( from
->me
.x
== to
->me
.x
) {
1263 if ( from
->pointtype
==pt_hvcurve
)
1264 foff
.x
= from
->me
.x
;
1265 if ( to
->pointtype
==pt_hvcurve
)
1267 } else if ( from
->me
.y
== to
->me
.y
) {
1268 if ( from
->pointtype
==pt_hvcurve
)
1269 foff
.y
= from
->me
.y
;
1270 if ( to
->pointtype
==pt_hvcurve
)
1273 if ( from
->pointtype
==pt_hvcurve
&& foff
.x
!=from
->me
.x
&& foff
.y
!=from
->me
.y
) {
1274 if ( fabs(foff
.x
-from
->me
.x
) > fabs(foff
.y
-from
->me
.y
) )
1275 foff
.y
= from
->me
.y
;
1277 foff
.x
= from
->me
.x
;
1279 if ( to
->pointtype
==pt_hvcurve
&& toff
.x
!=to
->me
.x
&& toff
.y
!=to
->me
.y
) {
1280 if ( from
->pointtype
==pt_hvcurve
) {
1281 if ( from
->me
.x
==foff
.x
)
1285 } else if ( fabs(toff
.x
-to
->me
.x
) > fabs(toff
.y
-to
->me
.y
) )
1292 if ( IntersectLinesClip(&from
->nextcp
,&foff
,&from
->me
,&toff
,&to
->me
)) {
1293 from
->nonextcp
= to
->noprevcp
= false;
1294 to
->prevcp
= from
->nextcp
;
1295 if ( (from
->pointtype
==pt_curve
|| from
->pointtype
==pt_hvcurve
) &&
1296 !from
->noprevcp
&& from
->prev
!=NULL
) {
1297 prev
= from
->prev
->from
;
1298 if ( IntersectLinesClip(&from
->prevcp
,&from
->nextcp
,&from
->me
,&prev
->nextcp
,&prev
->me
)) {
1299 prev
->nextcp
= from
->prevcp
;
1300 SplineRefigure2(from
->prev
);
1303 if ( (to
->pointtype
==pt_curve
|| to
->pointtype
==pt_hvcurve
) &&
1304 !to
->nonextcp
&& to
->next
!=NULL
) {
1305 next
= to
->next
->to
;
1306 if ( IntersectLinesClip(&to
->nextcp
,&to
->prevcp
,&to
->me
,&next
->prevcp
,&next
->me
)) {
1307 next
->prevcp
= to
->nextcp
;
1308 SplineRefigure(to
->next
);
1314 /* Can't set things arbetrarily here, but make sure they are consistant */
1315 if ( (from
->pointtype
==pt_curve
|| from
->pointtype
==pt_hvcurve
) &&
1316 !from
->noprevcp
&& !from
->nonextcp
) {
1317 unit
.x
= from
->nextcp
.x
-from
->me
.x
;
1318 unit
.y
= from
->nextcp
.y
-from
->me
.y
;
1319 len
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1321 unit
.x
/= len
; unit
.y
/= len
;
1322 len
= sqrt((from
->prevcp
.x
-from
->me
.x
)*(from
->prevcp
.x
-from
->me
.x
) + (from
->prevcp
.y
-from
->me
.y
)*(from
->prevcp
.y
-from
->me
.y
));
1323 new.x
= -len
*unit
.x
+ from
->me
.x
; new.y
= -len
*unit
.y
+ from
->me
.y
;
1324 if ( new.x
-from
->prevcp
.x
<-1 || new.x
-from
->prevcp
.x
>1 ||
1325 new.y
-from
->prevcp
.y
<-1 || new.y
-from
->prevcp
.y
>1 ) {
1327 if ( from
->prev
!=NULL
&& (prev
= from
->prev
->from
)!=NULL
&&
1328 IntersectLinesClip(&from
->prevcp
,&new,&from
->me
,&prev
->nextcp
,&prev
->me
)) {
1329 prev
->nextcp
= from
->prevcp
;
1330 SplineRefigure2(from
->prev
);
1338 } else if ( from
->pointtype
==pt_tangent
) {
1339 if ( from
->prev
!=NULL
) {
1340 prev
= from
->prev
->from
;
1341 if ( !from
->noprevcp
&& !prev
->nonextcp
&&
1342 IntersectLinesClip(&from
->prevcp
,&to
->me
,&from
->me
,&prev
->nextcp
,&prev
->me
)) {
1343 prev
->nextcp
= from
->prevcp
;
1344 SplineRefigure2(from
->prev
);
1346 if ( !from
->nonextcp
&& !to
->noprevcp
&&
1347 IntersectLinesClip(&from
->nextcp
,&prev
->me
,&from
->me
,&to
->prevcp
,&to
->me
))
1348 to
->prevcp
= from
->nextcp
;
1351 if ( (to
->pointtype
==pt_curve
|| to
->pointtype
==pt_hvcurve
) &&
1352 !to
->noprevcp
&& !to
->nonextcp
) {
1353 unit
.x
= to
->prevcp
.x
-to
->nextcp
.x
;
1354 unit
.y
= to
->prevcp
.y
-to
->nextcp
.y
;
1355 len
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1357 unit
.x
/= len
; unit
.y
/= len
;
1358 len
= sqrt((to
->nextcp
.x
-to
->me
.x
)*(to
->nextcp
.x
-to
->me
.x
) + (to
->nextcp
.y
-to
->me
.y
)*(to
->nextcp
.y
-to
->me
.y
));
1359 new.x
= -len
*unit
.x
+ to
->me
.x
; new.y
= -len
*unit
.y
+ to
->me
.y
;
1360 if ( new.x
-to
->nextcp
.x
<-1 || new.x
-to
->nextcp
.x
>1 ||
1361 new.y
-to
->nextcp
.y
<-1 || new.y
-to
->nextcp
.y
>1 ) {
1362 if ( to
->next
!=NULL
&& (next
= to
->next
->to
)!=NULL
&&
1363 IntersectLinesClip(&to
->nextcp
,&new,&to
->me
,&next
->prevcp
,&next
->me
)) {
1364 next
->prevcp
= to
->nextcp
;
1365 SplineRefigure2(to
->next
);
1368 if ( to
->next
!=NULL
) {
1369 to
->next
->to
->prevcp
= new;
1370 SplineRefigure(to
->next
);
1375 } else if ( to
->pointtype
==pt_tangent
) {
1376 if ( to
->next
!=NULL
) {
1377 next
= to
->next
->to
;
1378 if ( !to
->nonextcp
&& !next
->noprevcp
&&
1379 IntersectLinesClip(&to
->nextcp
,&from
->me
,&to
->me
,&next
->prevcp
,&next
->me
)) {
1380 next
->prevcp
= to
->nextcp
;
1381 SplineRefigure2(to
->next
);
1383 if ( !from
->nonextcp
&& !to
->noprevcp
&&
1384 IntersectLinesClip(&from
->nextcp
,&next
->me
,&to
->me
,&from
->nextcp
,&from
->me
))
1385 to
->prevcp
= from
->nextcp
;
1389 if ( from
->nonextcp
&& to
->noprevcp
)
1391 else if ( from
->nonextcp
|| to
->noprevcp
) {
1392 from
->nonextcp
= to
->noprevcp
= true;
1393 } else if (( from
->nextcp
.x
==from
->me
.x
&& from
->nextcp
.y
==from
->me
.y
) ||
1394 ( to
->prevcp
.x
==to
->me
.x
&& to
->prevcp
.y
==to
->me
.y
) ) {
1395 from
->nonextcp
= to
->noprevcp
= true;
1396 } else if ( from
->nonextcp
|| to
->noprevcp
|| from
->nextcp
.x
!=to
->prevcp
.x
||
1397 from
->nextcp
.y
!=to
->prevcp
.y
) {
1398 if ( !IntersectLinesClip(&from
->nextcp
,
1399 (from
->pointtype
==pt_tangent
&& from
->prev
!=NULL
)?&from
->prev
->from
->me
:&from
->nextcp
, &from
->me
,
1400 (to
->pointtype
==pt_tangent
&& to
->next
!=NULL
)?&to
->next
->to
->me
:&to
->prevcp
, &to
->me
)) {
1401 from
->nextcp
.x
= (from
->me
.x
+to
->me
.x
)/2;
1402 from
->nextcp
.y
= (from
->me
.y
+to
->me
.y
)/2;
1404 to
->prevcp
= from
->nextcp
;
1405 if (( from
->nextcp
.x
==from
->me
.x
&& from
->nextcp
.y
==from
->me
.y
) ||
1406 ( to
->prevcp
.x
==to
->me
.x
&& to
->prevcp
.y
==to
->me
.y
) ) {
1407 from
->nonextcp
= to
->noprevcp
= true;
1408 from
->nextcp
= from
->me
;
1409 to
->prevcp
= to
->me
;
1413 if ( snaptoint
&& !from
->nonextcp
) {
1414 from
->nextcp
.x
= to
->prevcp
.x
= rint(from
->nextcp
.x
);
1415 from
->nextcp
.y
= to
->prevcp
.y
= rint(from
->nextcp
.y
);
1417 SplineRefigure2(spline
);
1419 /* Now in order2 splines it is possible to request combinations that are */
1420 /* mathematically impossible -- two adjacent hv points often don't work */
1421 if ( to
->pointtype
==pt_hvcurve
&&
1422 !(to
->prevcp
.x
== to
->me
.x
&& to
->prevcp
.y
!= to
->me
.y
) &&
1423 !(to
->prevcp
.y
== to
->me
.y
&& to
->prevcp
.x
!= to
->me
.x
) )
1424 to
->pointtype
= pt_curve
;
1425 if ( from
->pointtype
==pt_hvcurve
&&
1426 !(from
->nextcp
.x
== from
->me
.x
&& from
->nextcp
.y
!= from
->me
.y
) &&
1427 !(from
->nextcp
.y
== from
->me
.y
&& from
->nextcp
.x
!= from
->me
.x
) )
1428 from
->pointtype
= pt_curve
;
1431 Spline
*SplineMake2(SplinePoint
*from
, SplinePoint
*to
) {
1432 Spline
*spline
= chunkalloc(sizeof(Spline
));
1434 spline
->from
= from
; spline
->to
= to
;
1435 from
->next
= to
->prev
= spline
;
1436 spline
->order2
= true;
1437 SplineRefigure2(spline
);
1441 Spline
*SplineMake(SplinePoint
*from
, SplinePoint
*to
, int order2
) {
1443 return( SplineMake2(from
,to
));
1445 return( SplineMake3(from
,to
));
1448 int IntersectLines(BasePoint
*inter
,
1449 BasePoint
*line1_1
, BasePoint
*line1_2
,
1450 BasePoint
*line2_1
, BasePoint
*line2_2
) {
1453 if ( line1_1
->x
== line1_2
->x
) {
1454 inter
->x
= line1_1
->x
;
1455 if ( line2_1
->x
== line2_2
->x
) {
1456 if ( line2_1
->x
!=line1_1
->x
)
1457 return( false ); /* Parallel vertical lines */
1458 inter
->y
= (line1_1
->y
+line2_1
->y
)/2;
1460 inter
->y
= line2_1
->y
+ (inter
->x
-line2_1
->x
) * (line2_2
->y
- line2_1
->y
)/(line2_2
->x
- line2_1
->x
);
1462 } else if ( line2_1
->x
== line2_2
->x
) {
1463 inter
->x
= line2_1
->x
;
1464 inter
->y
= line1_1
->y
+ (inter
->x
-line1_1
->x
) * (line1_2
->y
- line1_1
->y
)/(line1_2
->x
- line1_1
->x
);
1467 s1
= (line1_2
->y
- line1_1
->y
)/(line1_2
->x
- line1_1
->x
);
1468 s2
= (line2_2
->y
- line2_1
->y
)/(line2_2
->x
- line2_1
->x
);
1469 if ( RealNear(s1
,s2
)) {
1470 if ( !RealNear(line1_1
->y
+ (line2_1
->x
-line1_1
->x
) * s1
,line2_1
->y
))
1472 inter
->x
= (line1_2
->x
+line2_2
->x
)/2;
1473 inter
->y
= (line1_2
->y
+line2_2
->y
)/2;
1475 inter
->x
= (s1
*line1_1
->x
- s2
*line2_1
->x
- line1_1
->y
+ line2_1
->y
)/(s1
-s2
);
1476 inter
->y
= line1_1
->y
+ (inter
->x
-line1_1
->x
) * s1
;
1482 int IntersectLinesClip(BasePoint
*inter
,
1483 BasePoint
*line1_1
, BasePoint
*line1_2
,
1484 BasePoint
*line2_1
, BasePoint
*line2_2
) {
1485 BasePoint old
= *inter
, unit
;
1488 if ( !IntersectLines(inter
,line1_1
,line1_2
,line2_1
,line2_2
))
1491 unit
.x
= line2_2
->x
-line1_2
->x
;
1492 unit
.y
= line2_2
->y
-line1_2
->y
;
1493 len
= sqrt(unit
.x
*unit
.x
+ unit
.y
*unit
.y
);
1497 unit
.x
/= len
; unit
.y
/= len
;
1498 val
= unit
.x
*(inter
->x
-line1_2
->x
) + unit
.y
*(inter
->y
-line1_2
->y
);
1499 if ( val
<=0 || val
>=len
) {