diff options
Diffstat (limited to 'pdf/splash/SplashXPath.cc')
| -rw-r--r-- | pdf/splash/SplashXPath.cc | 417 |
1 files changed, 417 insertions, 0 deletions
diff --git a/pdf/splash/SplashXPath.cc b/pdf/splash/SplashXPath.cc new file mode 100644 index 0000000..e1a3afb --- /dev/null +++ b/pdf/splash/SplashXPath.cc @@ -0,0 +1,417 @@ +//======================================================================== +// +// SplashXPath.cc +// +//======================================================================== + +#include <aconf.h> + +#ifdef USE_GCC_PRAGMAS +#pragma implementation +#endif + +#include <stdlib.h> +#include <string.h> +#include "gmem.h" +#include "SplashMath.h" +#include "SplashPath.h" +#include "SplashXPath.h" + +//------------------------------------------------------------------------ + +#define maxCurveSplits (1 << 10) + +//------------------------------------------------------------------------ +// SplashXPath +//------------------------------------------------------------------------ + +SplashXPath::SplashXPath() { + segs = NULL; + length = size = 0; +} + +SplashXPath::SplashXPath(SplashPath *path, SplashCoord flatness, + GBool closeSubpaths) { + SplashCoord xc, yc, dx, dy, r, x0, y0, x1, y1; + int quad0, quad1, quad; + int i, curSubpath; + GBool last; + + segs = NULL; + length = size = 0; + + i = 0; + curSubpath = 0; + while (i < path->length) { + + // first point in subpath - skip it + if (path->flags[i] & splashPathFirst) { + curSubpath = i; + ++i; + + } else { + + // curve segment + if (path->flags[i] & splashPathCurve) { + addCurve(path->pts[i-1].x, path->pts[i-1].y, + path->pts[i ].x, path->pts[i ].y, + path->pts[i+1].x, path->pts[i+1].y, + path->pts[i+2].x, path->pts[i+2].y, + flatness, + (path->flags[i-1] & splashPathFirst), + (path->flags[i+2] & splashPathLast), + !closeSubpaths && + (path->flags[i-1] & splashPathFirst) && + !(path->flags[i-1] & splashPathClosed), + !closeSubpaths && + (path->flags[i+2] & splashPathLast) && + !(path->flags[i+2] & splashPathClosed)); + i += 3; + + // clockwise circular arc + } else if (path->flags[i] & splashPathArcCW) { + xc = path->pts[i].x; + yc = path->pts[i].y; + dx = path->pts[i+1].x - xc; + dy = path->pts[i+1].y - yc; + r = splashSqrt(dx * dx + dy * dy); + if (path->pts[i-1].x < xc && path->pts[i-1].y <= yc) { + quad0 = 0; + } else if (path->pts[i-1].x >= xc && path->pts[i-1].y < yc) { + quad0 = 1; + } else if (path->pts[i-1].x > xc && path->pts[i-1].y >= yc) { + quad0 = 2; + } else { + quad0 = 3; + } + if (path->pts[i+1].x <= xc && path->pts[i+1].y < yc) { + quad1 = 0; + } else if (path->pts[i+1].x > xc && path->pts[i+1].y <= yc) { + quad1 = 1; + } else if (path->pts[i+1].x >= xc && path->pts[i+1].y > yc) { + quad1 = 2; + } else { + quad1 = 3; + } + x0 = path->pts[i-1].x; + y0 = path->pts[i-1].y; + x1 = y1 = 0; // make gcc happy + quad = quad0; + while (1) { + switch (quad) { + case 0: x1 = xc; y1 = yc - r; break; + case 1: x1 = xc + r; y1 = yc; break; + case 2: x1 = xc; y1 = yc + r; break; + case 3: x1 = xc - r; y1 = yc; break; + } + last = gFalse; + if (quad == quad1) { + switch (quad) { + case 0: + case 1: last = path->pts[i+1].x > x0; break; + case 2: + case 3: last = path->pts[i+1].x < x0; break; + } + } + if (last) { + addArc(x0, y0, path->pts[i+1].x, path->pts[i+1].y, + xc, yc, r, quad, flatness, + quad == quad0 && (path->flags[i-1] & splashPathFirst), + (path->flags[i+1] & splashPathLast), + quad == quad0 && !closeSubpaths && + (path->flags[i-1] & splashPathFirst) && + !(path->flags[i-1] & splashPathClosed), + !closeSubpaths && + (path->flags[i+1] & splashPathLast) && + !(path->flags[i+1] & splashPathClosed)); + break; + } else { + addArc(x0, y0, x1, y1, + xc, yc, r, quad, flatness, + quad == quad0 && (path->flags[i-1] & splashPathFirst), + gFalse, + quad == quad0 && !closeSubpaths && + (path->flags[i-1] & splashPathFirst) && + !(path->flags[i-1] & splashPathClosed), + gFalse); + x0 = x1; + y0 = y1; + quad = (quad + 1) & 3; + } + } + i += 2; + + // line segment + } else { + addSegment(path->pts[i-1].x, path->pts[i-1].y, + path->pts[i].x, path->pts[i].y, + path->flags[i-1] & splashPathFirst, + path->flags[i] & splashPathLast, + !closeSubpaths && + (path->flags[i-1] & splashPathFirst) && + !(path->flags[i-1] & splashPathClosed), + !closeSubpaths && + (path->flags[i] & splashPathLast) && + !(path->flags[i] & splashPathClosed)); + ++i; + } + + // close a subpath + if (closeSubpaths && + (path->flags[i-1] & splashPathLast) && + (path->pts[i-1].x != path->pts[curSubpath].x || + path->pts[i-1].y != path->pts[curSubpath]. y)) { + addSegment(path->pts[i-1].x, path->pts[i-1].y, + path->pts[curSubpath].x, path->pts[curSubpath].y, + gFalse, gTrue, gFalse, gFalse); + } + } + } +} + +SplashXPath::SplashXPath(SplashXPath *xPath) { + length = xPath->length; + size = xPath->size; + segs = (SplashXPathSeg *)gmalloc(size * sizeof(SplashXPathSeg)); + memcpy(segs, xPath->segs, length * sizeof(SplashXPathSeg)); +} + +SplashXPath::~SplashXPath() { + gfree(segs); +} + +// Add space for <nSegs> more segments +void SplashXPath::grow(int nSegs) { + if (length + nSegs > size) { + if (size == 0) { + size = 32; + } + while (size < length + nSegs) { + size *= 2; + } + segs = (SplashXPathSeg *)grealloc(segs, size * sizeof(SplashXPathSeg)); + } +} + +void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0, + SplashCoord x1, SplashCoord y1, + SplashCoord x2, SplashCoord y2, + SplashCoord x3, SplashCoord y3, + SplashCoord flatness, + GBool first, GBool last, GBool end0, GBool end1) { + SplashCoord cx[maxCurveSplits + 1][3]; + SplashCoord cy[maxCurveSplits + 1][3]; + int cNext[maxCurveSplits + 1]; + SplashCoord xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh; + SplashCoord yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh; + SplashCoord dx, dy, mx, my, d1, d2, flatness2; + int p1, p2, p3; + + flatness2 = flatness * flatness; + + // initial segment + p1 = 0; + p2 = maxCurveSplits; + cx[p1][0] = x0; cy[p1][0] = y0; + cx[p1][1] = x1; cy[p1][1] = y1; + cx[p1][2] = x2; cy[p1][2] = y2; + cx[p2][0] = x3; cy[p2][0] = y3; + cNext[p1] = p2; + + while (p1 < maxCurveSplits) { + + // get the next segment + xl0 = cx[p1][0]; yl0 = cy[p1][0]; + xx1 = cx[p1][1]; yy1 = cy[p1][1]; + xx2 = cx[p1][2]; yy2 = cy[p1][2]; + p2 = cNext[p1]; + xr3 = cx[p2][0]; yr3 = cy[p2][0]; + + // compute the distances from the control points to the + // midpoint of the straight line (this is a bit of a hack, but + // it's much faster than computing the actual distances to the + // line) + mx = (xl0 + xr3) * 0.5; + my = (yl0 + yr3) * 0.5; + dx = xx1 - mx; + dy = yy1 - my; + d1 = dx*dx + dy*dy; + dx = xx2 - mx; + dy = yy2 - my; + d2 = dx*dx + dy*dy; + + // if the curve is flat enough, or no more subdivisions are + // allowed, add the straight line segment + if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) { + addSegment(xl0, yl0, xr3, yr3, + p1 == 0 && first, + p2 == maxCurveSplits && last, + p1 == 0 && end0, + p2 == maxCurveSplits && end1); + p1 = p2; + + // otherwise, subdivide the curve + } else { + xl1 = (xl0 + xx1) * 0.5; + yl1 = (yl0 + yy1) * 0.5; + xh = (xx1 + xx2) * 0.5; + yh = (yy1 + yy2) * 0.5; + xl2 = (xl1 + xh) * 0.5; + yl2 = (yl1 + yh) * 0.5; + xr2 = (xx2 + xr3) * 0.5; + yr2 = (yy2 + yr3) * 0.5; + xr1 = (xh + xr2) * 0.5; + yr1 = (yh + yr2) * 0.5; + xr0 = (xl2 + xr1) * 0.5; + yr0 = (yl2 + yr1) * 0.5; + // add the new subdivision points + p3 = (p1 + p2) / 2; + cx[p1][1] = xl1; cy[p1][1] = yl1; + cx[p1][2] = xl2; cy[p1][2] = yl2; + cNext[p1] = p3; + cx[p3][0] = xr0; cy[p3][0] = yr0; + cx[p3][1] = xr1; cy[p3][1] = yr1; + cx[p3][2] = xr2; cy[p3][2] = yr2; + cNext[p3] = p2; + } + } +} + +void SplashXPath::addArc(SplashCoord x0, SplashCoord y0, + SplashCoord x1, SplashCoord y1, + SplashCoord xc, SplashCoord yc, + SplashCoord r, int quad, + SplashCoord flatness, + GBool first, GBool last, GBool end0, GBool end1) { + SplashCoord px[maxCurveSplits + 1]; + SplashCoord py[maxCurveSplits + 1]; + int pNext[maxCurveSplits + 1]; + SplashCoord r2, flatness2; + SplashCoord xx0, yy0, xx1, yy1, xm, ym, t, dx, dy; + int p1, p2, p3; + + r2 = r * r; + flatness2 = flatness * flatness; + + // initial segment + p1 = 0; + p2 = maxCurveSplits; + px[p1] = x0; py[p1] = y0; + px[p2] = x1; py[p2] = y1; + pNext[p1] = p2; + + while (p1 < maxCurveSplits) { + + // get the next segment + xx0 = px[p1]; yy0 = py[p1]; + p2 = pNext[p1]; + xx1 = px[p2]; yy1 = py[p2]; + + // compute the arc midpoint + t = (xx0 - xc) * (xx1 - xc) - (yy0 - yc) * (yy1 - yc); + xm = splashSqrt(0.5 * (r2 + t)); + ym = splashSqrt(0.5 * (r2 - t)); + switch (quad) { + case 0: xm = xc - xm; ym = yc - ym; break; + case 1: xm = xc + xm; ym = yc - ym; break; + case 2: xm = xc + xm; ym = yc + ym; break; + case 3: xm = xc - xm; ym = yc + ym; break; + } + + // compute distance from midpoint of straight segment to midpoint + // of arc + dx = 0.5 * (xx0 + xx1) - xm; + dy = 0.5 * (yy0 + yy1) - ym; + + // if the arc is flat enough, or no more subdivisions are allowed, + // add the straight line segment + if (p2 - p1 == 1 || dx * dx + dy * dy <= flatness2) { + addSegment(xx0, yy0, xx1, yy1, + p1 == 0 && first, + p2 == maxCurveSplits && last, + p1 == 0 && end0, + p2 == maxCurveSplits && end1); + p1 = p2; + + // otherwise, subdivide the arc + } else { + p3 = (p1 + p2) / 2; + px[p3] = xm; + py[p3] = ym; + pNext[p1] = p3; + pNext[p3] = p2; + } + } +} + +void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0, + SplashCoord x1, SplashCoord y1, + GBool first, GBool last, GBool end0, GBool end1) { + grow(1); + segs[length].x0 = x0; + segs[length].y0 = y0; + segs[length].x1 = x1; + segs[length].y1 = y1; + segs[length].flags = 0; + if (first) { + segs[length].flags |= splashXPathFirst; + } + if (last) { + segs[length].flags |= splashXPathLast; + } + if (end0) { + segs[length].flags |= splashXPathEnd0; + } + if (end1) { + segs[length].flags |= splashXPathEnd1; + } + if (y1 == y0) { + segs[length].dxdy = segs[length].dydx = 0; + segs[length].flags |= splashXPathHoriz; + if (x1 == x0) { + segs[length].flags |= splashXPathVert; + } + } else if (x1 == x0) { + segs[length].dxdy = segs[length].dydx = 0; + segs[length].flags |= splashXPathVert; + } else { + segs[length].dxdy = (x1 - x0) / (y1 - y0); + segs[length].dydx = 1 / segs[length].dxdy; + } + if (y0 > y1) { + segs[length].flags |= splashXPathFlip; + } + ++length; +} + +static int cmpXPathSegs(const void *arg0, const void *arg1) { + SplashXPathSeg *seg0 = (SplashXPathSeg *)arg0; + SplashXPathSeg *seg1 = (SplashXPathSeg *)arg1; + SplashCoord x0, y0, x1, y1; + + if (seg0->flags & splashXPathFlip) { + x0 = seg0->x1; + y0 = seg0->y1; + } else { + x0 = seg0->x0; + y0 = seg0->y0; + } + if (seg1->flags & splashXPathFlip) { + x1 = seg1->x1; + y1 = seg1->y1; + } else { + x1 = seg1->x0; + y1 = seg1->y0; + } + if (y0 != y1) { + return (y0 > y1) ? 1 : -1; + } + if (x0 != x1) { + return (x0 > x1) ? 1 : -1; + } + return 0; +} + +void SplashXPath::sort() { + qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs); +} |