1 //========================================================================
5 //========================================================================
10 #pragma implementation
16 #include "SplashMath.h"
17 #include "SplashPath.h"
18 #include "SplashXPath.h"
20 //------------------------------------------------------------------------
22 #define maxCurveSplits (1 << 10)
24 //------------------------------------------------------------------------
26 //------------------------------------------------------------------------
28 SplashXPath::SplashXPath() {
33 SplashXPath::SplashXPath(SplashPath
*path
, SplashCoord flatness
,
34 GBool closeSubpaths
) {
35 SplashCoord xc
, yc
, dx
, dy
, r
, x0
, y0
, x1
, y1
;
36 int quad0
, quad1
, quad
;
37 int curSubpath
, n
, i
, j
;
44 while (i
< path
->length
) {
46 // first point in subpath - skip it
47 if (path
->flags
[i
] & splashPathFirst
) {
54 if (path
->flags
[i
] & splashPathCurve
) {
55 addCurve(path
->pts
[i
-1].x
, path
->pts
[i
-1].y
,
56 path
->pts
[i
].x
, path
->pts
[i
].y
,
57 path
->pts
[i
+1].x
, path
->pts
[i
+1].y
,
58 path
->pts
[i
+2].x
, path
->pts
[i
+2].y
,
60 (path
->flags
[i
-1] & splashPathFirst
),
61 (path
->flags
[i
+2] & splashPathLast
),
63 (path
->flags
[i
-1] & splashPathFirst
) &&
64 !(path
->flags
[i
-1] & splashPathClosed
),
66 (path
->flags
[i
+2] & splashPathLast
) &&
67 !(path
->flags
[i
+2] & splashPathClosed
));
70 // clockwise circular arc
71 } else if (path
->flags
[i
] & splashPathArcCW
) {
74 dx
= path
->pts
[i
+1].x
- xc
;
75 dy
= path
->pts
[i
+1].y
- yc
;
76 r
= splashSqrt(dx
* dx
+ dy
* dy
);
77 if (path
->pts
[i
-1].x
< xc
&& path
->pts
[i
-1].y
<= yc
) {
79 } else if (path
->pts
[i
-1].x
>= xc
&& path
->pts
[i
-1].y
< yc
) {
81 } else if (path
->pts
[i
-1].x
> xc
&& path
->pts
[i
-1].y
>= yc
) {
86 if (path
->pts
[i
+1].x
<= xc
&& path
->pts
[i
+1].y
< yc
) {
88 } else if (path
->pts
[i
+1].x
> xc
&& path
->pts
[i
+1].y
<= yc
) {
90 } else if (path
->pts
[i
+1].x
>= xc
&& path
->pts
[i
+1].y
> yc
) {
95 n
= 0; // make gcc happy
99 case 1: n
= path
->pts
[i
-1].x
< path
->pts
[i
+1].x
? 0 : 4; break;
101 case 3: n
= path
->pts
[i
-1].x
> path
->pts
[i
+1].x
? 0 : 4; break;
104 n
= (quad1
- quad0
) & 3;
106 x0
= path
->pts
[i
-1].x
;
107 y0
= path
->pts
[i
-1].y
;
108 x1
= y1
= 0; // make gcc happy
110 for (j
= 0; j
< n
; ++j
) {
112 case 0: x1
= xc
; y1
= yc
- r
; break;
113 case 1: x1
= xc
+ r
; y1
= yc
; break;
114 case 2: x1
= xc
; y1
= yc
+ r
; break;
115 case 3: x1
= xc
- r
; y1
= yc
; break;
117 addArc(x0
, y0
, x1
, y1
,
118 xc
, yc
, r
, quad
, flatness
,
119 quad
== quad0
&& (path
->flags
[i
-1] & splashPathFirst
),
121 quad
== quad0
&& !closeSubpaths
&&
122 (path
->flags
[i
-1] & splashPathFirst
) &&
123 !(path
->flags
[i
-1] & splashPathClosed
),
127 quad
= (quad
+ 1) & 3;
129 addArc(x0
, y0
, path
->pts
[i
+1].x
, path
->pts
[i
+1].y
,
130 xc
, yc
, r
, quad
, flatness
,
131 quad
== quad0
&& (path
->flags
[i
-1] & splashPathFirst
),
132 (path
->flags
[i
+1] & splashPathLast
),
133 quad
== quad0
&& !closeSubpaths
&&
134 (path
->flags
[i
-1] & splashPathFirst
) &&
135 !(path
->flags
[i
-1] & splashPathClosed
),
137 (path
->flags
[i
+1] & splashPathLast
) &&
138 !(path
->flags
[i
+1] & splashPathClosed
));
143 addSegment(path
->pts
[i
-1].x
, path
->pts
[i
-1].y
,
144 path
->pts
[i
].x
, path
->pts
[i
].y
,
145 path
->flags
[i
-1] & splashPathFirst
,
146 path
->flags
[i
] & splashPathLast
,
148 (path
->flags
[i
-1] & splashPathFirst
) &&
149 !(path
->flags
[i
-1] & splashPathClosed
),
151 (path
->flags
[i
] & splashPathLast
) &&
152 !(path
->flags
[i
] & splashPathClosed
));
158 (path
->flags
[i
-1] & splashPathLast
) &&
159 (path
->pts
[i
-1].x
!= path
->pts
[curSubpath
].x
||
160 path
->pts
[i
-1].y
!= path
->pts
[curSubpath
]. y
)) {
161 addSegment(path
->pts
[i
-1].x
, path
->pts
[i
-1].y
,
162 path
->pts
[curSubpath
].x
, path
->pts
[curSubpath
].y
,
163 gFalse
, gTrue
, gFalse
, gFalse
);
169 SplashXPath::SplashXPath(SplashXPath
*xPath
) {
170 length
= xPath
->length
;
172 segs
= (SplashXPathSeg
*)gmallocn(size
, sizeof(SplashXPathSeg
));
173 memcpy(segs
, xPath
->segs
, length
* sizeof(SplashXPathSeg
));
176 SplashXPath::~SplashXPath() {
180 // Add space for <nSegs> more segments
181 void SplashXPath::grow(int nSegs
) {
182 if (length
+ nSegs
> size
) {
186 while (size
< length
+ nSegs
) {
189 segs
= (SplashXPathSeg
*)greallocn(segs
, size
, sizeof(SplashXPathSeg
));
193 void SplashXPath::addCurve(SplashCoord x0
, SplashCoord y0
,
194 SplashCoord x1
, SplashCoord y1
,
195 SplashCoord x2
, SplashCoord y2
,
196 SplashCoord x3
, SplashCoord y3
,
197 SplashCoord flatness
,
198 GBool first
, GBool last
, GBool end0
, GBool end1
) {
199 SplashCoord cx
[maxCurveSplits
+ 1][3];
200 SplashCoord cy
[maxCurveSplits
+ 1][3];
201 int cNext
[maxCurveSplits
+ 1];
202 SplashCoord xl0
, xl1
, xl2
, xr0
, xr1
, xr2
, xr3
, xx1
, xx2
, xh
;
203 SplashCoord yl0
, yl1
, yl2
, yr0
, yr1
, yr2
, yr3
, yy1
, yy2
, yh
;
204 SplashCoord dx
, dy
, mx
, my
, d1
, d2
, flatness2
;
207 flatness2
= flatness
* flatness
;
212 cx
[p1
][0] = x0
; cy
[p1
][0] = y0
;
213 cx
[p1
][1] = x1
; cy
[p1
][1] = y1
;
214 cx
[p1
][2] = x2
; cy
[p1
][2] = y2
;
215 cx
[p2
][0] = x3
; cy
[p2
][0] = y3
;
218 while (p1
< maxCurveSplits
) {
220 // get the next segment
221 xl0
= cx
[p1
][0]; yl0
= cy
[p1
][0];
222 xx1
= cx
[p1
][1]; yy1
= cy
[p1
][1];
223 xx2
= cx
[p1
][2]; yy2
= cy
[p1
][2];
225 xr3
= cx
[p2
][0]; yr3
= cy
[p2
][0];
227 // compute the distances from the control points to the
228 // midpoint of the straight line (this is a bit of a hack, but
229 // it's much faster than computing the actual distances to the
231 mx
= (xl0
+ xr3
) * 0.5;
232 my
= (yl0
+ yr3
) * 0.5;
240 // if the curve is flat enough, or no more subdivisions are
241 // allowed, add the straight line segment
242 if (p2
- p1
== 1 || (d1
<= flatness2
&& d2
<= flatness2
)) {
243 addSegment(xl0
, yl0
, xr3
, yr3
,
245 p2
== maxCurveSplits
&& last
,
247 p2
== maxCurveSplits
&& end1
);
250 // otherwise, subdivide the curve
252 xl1
= (xl0
+ xx1
) * 0.5;
253 yl1
= (yl0
+ yy1
) * 0.5;
254 xh
= (xx1
+ xx2
) * 0.5;
255 yh
= (yy1
+ yy2
) * 0.5;
256 xl2
= (xl1
+ xh
) * 0.5;
257 yl2
= (yl1
+ yh
) * 0.5;
258 xr2
= (xx2
+ xr3
) * 0.5;
259 yr2
= (yy2
+ yr3
) * 0.5;
260 xr1
= (xh
+ xr2
) * 0.5;
261 yr1
= (yh
+ yr2
) * 0.5;
262 xr0
= (xl2
+ xr1
) * 0.5;
263 yr0
= (yl2
+ yr1
) * 0.5;
264 // add the new subdivision points
266 cx
[p1
][1] = xl1
; cy
[p1
][1] = yl1
;
267 cx
[p1
][2] = xl2
; cy
[p1
][2] = yl2
;
269 cx
[p3
][0] = xr0
; cy
[p3
][0] = yr0
;
270 cx
[p3
][1] = xr1
; cy
[p3
][1] = yr1
;
271 cx
[p3
][2] = xr2
; cy
[p3
][2] = yr2
;
277 void SplashXPath::addArc(SplashCoord x0
, SplashCoord y0
,
278 SplashCoord x1
, SplashCoord y1
,
279 SplashCoord xc
, SplashCoord yc
,
280 SplashCoord r
, int quad
,
281 SplashCoord flatness
,
282 GBool first
, GBool last
, GBool end0
, GBool end1
) {
283 SplashCoord px
[maxCurveSplits
+ 1];
284 SplashCoord py
[maxCurveSplits
+ 1];
285 int pNext
[maxCurveSplits
+ 1];
286 SplashCoord r2
, flatness2
;
287 SplashCoord xx0
, yy0
, xx1
, yy1
, xm
, ym
, t
, dx
, dy
;
291 flatness2
= flatness
* flatness
;
296 px
[p1
] = x0
; py
[p1
] = y0
;
297 px
[p2
] = x1
; py
[p2
] = y1
;
300 while (p1
< maxCurveSplits
) {
302 // get the next segment
303 xx0
= px
[p1
]; yy0
= py
[p1
];
305 xx1
= px
[p2
]; yy1
= py
[p2
];
307 // compute the arc midpoint
308 t
= (xx0
- xc
) * (xx1
- xc
) - (yy0
- yc
) * (yy1
- yc
);
309 xm
= splashSqrt((SplashCoord
)0.5 * (r2
+ t
));
310 ym
= splashSqrt((SplashCoord
)0.5 * (r2
- t
));
312 case 0: xm
= xc
- xm
; ym
= yc
- ym
; break;
313 case 1: xm
= xc
+ xm
; ym
= yc
- ym
; break;
314 case 2: xm
= xc
+ xm
; ym
= yc
+ ym
; break;
315 case 3: xm
= xc
- xm
; ym
= yc
+ ym
; break;
318 // compute distance from midpoint of straight segment to midpoint
320 dx
= (SplashCoord
)0.5 * (xx0
+ xx1
) - xm
;
321 dy
= (SplashCoord
)0.5 * (yy0
+ yy1
) - ym
;
323 // if the arc is flat enough, or no more subdivisions are allowed,
324 // add the straight line segment
325 if (p2
- p1
== 1 || dx
* dx
+ dy
* dy
<= flatness2
) {
326 addSegment(xx0
, yy0
, xx1
, yy1
,
328 p2
== maxCurveSplits
&& last
,
330 p2
== maxCurveSplits
&& end1
);
333 // otherwise, subdivide the arc
344 void SplashXPath::addSegment(SplashCoord x0
, SplashCoord y0
,
345 SplashCoord x1
, SplashCoord y1
,
346 GBool first
, GBool last
, GBool end0
, GBool end1
) {
348 segs
[length
].x0
= x0
;
349 segs
[length
].y0
= y0
;
350 segs
[length
].x1
= x1
;
351 segs
[length
].y1
= y1
;
352 segs
[length
].flags
= 0;
354 segs
[length
].flags
|= splashXPathFirst
;
357 segs
[length
].flags
|= splashXPathLast
;
360 segs
[length
].flags
|= splashXPathEnd0
;
363 segs
[length
].flags
|= splashXPathEnd1
;
366 segs
[length
].dxdy
= segs
[length
].dydx
= 0;
367 segs
[length
].flags
|= splashXPathHoriz
;
369 segs
[length
].flags
|= splashXPathVert
;
371 } else if (x1
== x0
) {
372 segs
[length
].dxdy
= segs
[length
].dydx
= 0;
373 segs
[length
].flags
|= splashXPathVert
;
375 segs
[length
].dxdy
= (x1
- x0
) / (y1
- y0
);
376 segs
[length
].dydx
= (SplashCoord
)1 / segs
[length
].dxdy
;
379 segs
[length
].flags
|= splashXPathFlip
;
384 static int cmpXPathSegs(const void *arg0
, const void *arg1
) {
385 SplashXPathSeg
*seg0
= (SplashXPathSeg
*)arg0
;
386 SplashXPathSeg
*seg1
= (SplashXPathSeg
*)arg1
;
387 SplashCoord x0
, y0
, x1
, y1
;
389 if (seg0
->flags
& splashXPathFlip
) {
396 if (seg1
->flags
& splashXPathFlip
) {
404 return (y0
> y1
) ? 1 : -1;
407 return (x0
> x1
) ? 1 : -1;
412 void SplashXPath::sort() {
413 qsort(segs
, length
, sizeof(SplashXPathSeg
), &cmpXPathSegs
);