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;
45 while (i < path->length) {
47 // first point in subpath - skip it
48 if (path->flags[i] & splashPathFirst) {
55 if (path->flags[i] & splashPathCurve) {
56 addCurve(path->pts[i-1].x, path->pts[i-1].y,
57 path->pts[i ].x, path->pts[i ].y,
58 path->pts[i+1].x, path->pts[i+1].y,
59 path->pts[i+2].x, path->pts[i+2].y,
61 (path->flags[i-1] & splashPathFirst),
62 (path->flags[i+2] & splashPathLast),
64 (path->flags[i-1] & splashPathFirst) &&
65 !(path->flags[i-1] & splashPathClosed),
67 (path->flags[i+2] & splashPathLast) &&
68 !(path->flags[i+2] & splashPathClosed));
71 // clockwise circular arc
72 } else if (path->flags[i] & splashPathArcCW) {
75 dx = path->pts[i+1].x - xc;
76 dy = path->pts[i+1].y - yc;
77 r = splashSqrt(dx * dx + dy * dy);
78 if (path->pts[i-1].x < xc && path->pts[i-1].y <= yc) {
80 } else if (path->pts[i-1].x >= xc && path->pts[i-1].y < yc) {
82 } else if (path->pts[i-1].x > xc && path->pts[i-1].y >= yc) {
87 if (path->pts[i+1].x <= xc && path->pts[i+1].y < yc) {
89 } else if (path->pts[i+1].x > xc && path->pts[i+1].y <= yc) {
91 } else if (path->pts[i+1].x >= xc && path->pts[i+1].y > yc) {
96 x0 = path->pts[i-1].x;
97 y0 = path->pts[i-1].y;
98 x1 = y1 = 0; // make gcc happy
102 case 0: x1 = xc; y1 = yc - r; break;
103 case 1: x1 = xc + r; y1 = yc; break;
104 case 2: x1 = xc; y1 = yc + r; break;
105 case 3: x1 = xc - r; y1 = yc; break;
111 case 1: last = path->pts[i+1].x > x0; break;
113 case 3: last = path->pts[i+1].x < x0; break;
117 addArc(x0, y0, path->pts[i+1].x, path->pts[i+1].y,
118 xc, yc, r, quad, flatness,
119 quad == quad0 && (path->flags[i-1] & splashPathFirst),
120 (path->flags[i+1] & splashPathLast),
121 quad == quad0 && !closeSubpaths &&
122 (path->flags[i-1] & splashPathFirst) &&
123 !(path->flags[i-1] & splashPathClosed),
125 (path->flags[i+1] & splashPathLast) &&
126 !(path->flags[i+1] & splashPathClosed));
129 addArc(x0, y0, x1, y1,
130 xc, yc, r, quad, flatness,
131 quad == quad0 && (path->flags[i-1] & splashPathFirst),
133 quad == quad0 && !closeSubpaths &&
134 (path->flags[i-1] & splashPathFirst) &&
135 !(path->flags[i-1] & splashPathClosed),
139 quad = (quad + 1) & 3;
146 addSegment(path->pts[i-1].x, path->pts[i-1].y,
147 path->pts[i].x, path->pts[i].y,
148 path->flags[i-1] & splashPathFirst,
149 path->flags[i] & splashPathLast,
151 (path->flags[i-1] & splashPathFirst) &&
152 !(path->flags[i-1] & splashPathClosed),
154 (path->flags[i] & splashPathLast) &&
155 !(path->flags[i] & splashPathClosed));
161 (path->flags[i-1] & splashPathLast) &&
162 (path->pts[i-1].x != path->pts[curSubpath].x ||
163 path->pts[i-1].y != path->pts[curSubpath]. y)) {
164 addSegment(path->pts[i-1].x, path->pts[i-1].y,
165 path->pts[curSubpath].x, path->pts[curSubpath].y,
166 gFalse, gTrue, gFalse, gFalse);
172 SplashXPath::SplashXPath(SplashXPath *xPath) {
173 length = xPath->length;
175 segs = (SplashXPathSeg *)gmalloc(size * sizeof(SplashXPathSeg));
176 memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg));
179 SplashXPath::~SplashXPath() {
183 // Add space for <nSegs> more segments
184 void SplashXPath::grow(int nSegs) {
185 if (length + nSegs > size) {
189 while (size < length + nSegs) {
192 segs = (SplashXPathSeg *)grealloc(segs, size * sizeof(SplashXPathSeg));
196 void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0,
197 SplashCoord x1, SplashCoord y1,
198 SplashCoord x2, SplashCoord y2,
199 SplashCoord x3, SplashCoord y3,
200 SplashCoord flatness,
201 GBool first, GBool last, GBool end0, GBool end1) {
202 SplashCoord cx[maxCurveSplits + 1][3];
203 SplashCoord cy[maxCurveSplits + 1][3];
204 int cNext[maxCurveSplits + 1];
205 SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;
206 SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;
207 SplashCoord dx, dy, mx, my, d1, d2, flatness2;
210 flatness2 = flatness * flatness;
215 cx[p1][0] = x0; cy[p1][0] = y0;
216 cx[p1][1] = x1; cy[p1][1] = y1;
217 cx[p1][2] = x2; cy[p1][2] = y2;
218 cx[p2][0] = x3; cy[p2][0] = y3;
221 while (p1 < maxCurveSplits) {
223 // get the next segment
224 xl0 = cx[p1][0]; yl0 = cy[p1][0];
225 xx1 = cx[p1][1]; yy1 = cy[p1][1];
226 xx2 = cx[p1][2]; yy2 = cy[p1][2];
228 xr3 = cx[p2][0]; yr3 = cy[p2][0];
230 // compute the distances from the control points to the
231 // midpoint of the straight line (this is a bit of a hack, but
232 // it's much faster than computing the actual distances to the
234 mx = (xl0 + xr3) * 0.5;
235 my = (yl0 + yr3) * 0.5;
243 // if the curve is flat enough, or no more subdivisions are
244 // allowed, add the straight line segment
245 if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {
246 addSegment(xl0, yl0, xr3, yr3,
248 p2 == maxCurveSplits && last,
250 p2 == maxCurveSplits && end1);
253 // otherwise, subdivide the curve
255 xl1 = (xl0 + xx1) * 0.5;
256 yl1 = (yl0 + yy1) * 0.5;
257 xh = (xx1 + xx2) * 0.5;
258 yh = (yy1 + yy2) * 0.5;
259 xl2 = (xl1 + xh) * 0.5;
260 yl2 = (yl1 + yh) * 0.5;
261 xr2 = (xx2 + xr3) * 0.5;
262 yr2 = (yy2 + yr3) * 0.5;
263 xr1 = (xh + xr2) * 0.5;
264 yr1 = (yh + yr2) * 0.5;
265 xr0 = (xl2 + xr1) * 0.5;
266 yr0 = (yl2 + yr1) * 0.5;
267 // add the new subdivision points
269 cx[p1][1] = xl1; cy[p1][1] = yl1;
270 cx[p1][2] = xl2; cy[p1][2] = yl2;
272 cx[p3][0] = xr0; cy[p3][0] = yr0;
273 cx[p3][1] = xr1; cy[p3][1] = yr1;
274 cx[p3][2] = xr2; cy[p3][2] = yr2;
280 void SplashXPath::addArc(SplashCoord x0, SplashCoord y0,
281 SplashCoord x1, SplashCoord y1,
282 SplashCoord xc, SplashCoord yc,
283 SplashCoord r, int quad,
284 SplashCoord flatness,
285 GBool first, GBool last, GBool end0, GBool end1) {
286 SplashCoord px[maxCurveSplits + 1];
287 SplashCoord py[maxCurveSplits + 1];
288 int pNext[maxCurveSplits + 1];
289 SplashCoord r2, flatness2;
290 SplashCoord xx0, yy0, xx1, yy1, xm, ym, t, dx, dy;
294 flatness2 = flatness * flatness;
299 px[p1] = x0; py[p1] = y0;
300 px[p2] = x1; py[p2] = y1;
303 while (p1 < maxCurveSplits) {
305 // get the next segment
306 xx0 = px[p1]; yy0 = py[p1];
308 xx1 = px[p2]; yy1 = py[p2];
310 // compute the arc midpoint
311 t = (xx0 - xc) * (xx1 - xc) - (yy0 - yc) * (yy1 - yc);
312 xm = splashSqrt(0.5 * (r2 + t));
313 ym = splashSqrt(0.5 * (r2 - t));
315 case 0: xm = xc - xm; ym = yc - ym; break;
316 case 1: xm = xc + xm; ym = yc - ym; break;
317 case 2: xm = xc + xm; ym = yc + ym; break;
318 case 3: xm = xc - xm; ym = yc + ym; break;
321 // compute distance from midpoint of straight segment to midpoint
323 dx = 0.5 * (xx0 + xx1) - xm;
324 dy = 0.5 * (yy0 + yy1) - ym;
326 // if the arc is flat enough, or no more subdivisions are allowed,
327 // add the straight line segment
328 if (p2 - p1 == 1 || dx * dx + dy * dy <= flatness2) {
329 addSegment(xx0, yy0, xx1, yy1,
331 p2 == maxCurveSplits && last,
333 p2 == maxCurveSplits && end1);
336 // otherwise, subdivide the arc
347 void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
348 SplashCoord x1, SplashCoord y1,
349 GBool first, GBool last, GBool end0, GBool end1) {
351 segs[length].x0 = x0;
352 segs[length].y0 = y0;
353 segs[length].x1 = x1;
354 segs[length].y1 = y1;
355 segs[length].flags = 0;
357 segs[length].flags |= splashXPathFirst;
360 segs[length].flags |= splashXPathLast;
363 segs[length].flags |= splashXPathEnd0;
366 segs[length].flags |= splashXPathEnd1;
369 segs[length].dxdy = segs[length].dydx = 0;
370 segs[length].flags |= splashXPathHoriz;
372 segs[length].flags |= splashXPathVert;
374 } else if (x1 == x0) {
375 segs[length].dxdy = segs[length].dydx = 0;
376 segs[length].flags |= splashXPathVert;
378 segs[length].dxdy = (x1 - x0) / (y1 - y0);
379 segs[length].dydx = 1 / segs[length].dxdy;
382 segs[length].flags |= splashXPathFlip;
387 static int cmpXPathSegs(const void *arg0, const void *arg1) {
388 SplashXPathSeg *seg0 = (SplashXPathSeg *)arg0;
389 SplashXPathSeg *seg1 = (SplashXPathSeg *)arg1;
390 SplashCoord x0, y0, x1, y1;
392 if (seg0->flags & splashXPathFlip) {
399 if (seg1->flags & splashXPathFlip) {
407 return (y0 > y1) ? 1 : -1;
410 return (x0 > x1) ? 1 : -1;
415 void SplashXPath::sort() {
416 qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);