summaryrefslogtreecommitdiffstats
path: root/kpdf/xpdf/splash/SplashXPath.cc
diff options
context:
space:
mode:
Diffstat (limited to 'kpdf/xpdf/splash/SplashXPath.cc')
-rw-r--r--kpdf/xpdf/splash/SplashXPath.cc443
1 files changed, 443 insertions, 0 deletions
diff --git a/kpdf/xpdf/splash/SplashXPath.cc b/kpdf/xpdf/splash/SplashXPath.cc
new file mode 100644
index 00000000..71481eff
--- /dev/null
+++ b/kpdf/xpdf/splash/SplashXPath.cc
@@ -0,0 +1,443 @@
+//========================================================================
+//
+// 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"
+
+//------------------------------------------------------------------------
+
+struct SplashXPathPoint {
+ SplashCoord x, y;
+};
+
+struct SplashXPathAdjust {
+ int firstPt, lastPt; // range of points
+ GBool vert; // vertical or horizontal hint
+ SplashCoord x0a, x0b, // hint boundaries
+ xma, xmb,
+ x1a, x1b;
+ SplashCoord x0, x1, xm; // adjusted coordinates
+};
+
+//------------------------------------------------------------------------
+
+// Transform a point from user space to device space.
+inline void SplashXPath::transform(SplashCoord *matrix,
+ SplashCoord xi, SplashCoord yi,
+ SplashCoord *xo, SplashCoord *yo) {
+ // [ m[0] m[1] 0 ]
+ // [xo yo 1] = [xi yi 1] * [ m[2] m[3] 0 ]
+ // [ m[4] m[5] 1 ]
+ *xo = xi * matrix[0] + yi * matrix[2] + matrix[4];
+ *yo = xi * matrix[1] + yi * matrix[3] + matrix[5];
+}
+
+//------------------------------------------------------------------------
+// SplashXPath
+//------------------------------------------------------------------------
+
+SplashXPath::SplashXPath() {
+ segs = NULL;
+ length = size = 0;
+}
+
+SplashXPath::SplashXPath(SplashPath *path, SplashCoord *matrix,
+ SplashCoord flatness, GBool closeSubpaths) {
+ SplashPathHint *hint;
+ SplashXPathPoint *pts;
+ SplashXPathAdjust *adjusts, *adjust;
+ SplashCoord x0, y0, x1, y1, x2, y2, x3, y3, xsp, ysp;
+ SplashCoord adj0, adj1, w;
+ int ww;
+ int curSubpath, curSubpathX, i, j;
+
+ // transform the points
+ pts = (SplashXPathPoint *)gmallocn(path->length, sizeof(SplashXPathPoint));
+ for (i = 0; i < path->length; ++i) {
+ transform(matrix, path->pts[i].x, path->pts[i].y, &pts[i].x, &pts[i].y);
+ }
+
+ // set up the stroke adjustment hints
+ if (path->hints) {
+ adjusts = (SplashXPathAdjust *)gmallocn(path->hintsLength,
+ sizeof(SplashXPathAdjust));
+ for (i = 0; i < path->hintsLength; ++i) {
+ hint = &path->hints[i];
+ if (hint->ctrl0 + 1 >= path->length || hint->ctrl1 + 1 >= path->length) {
+ gfree(adjusts);
+ adjusts = NULL;
+ break;
+ }
+ x0 = pts[hint->ctrl0 ].x; y0 = pts[hint->ctrl0 ].y;
+ x1 = pts[hint->ctrl0 + 1].x; y1 = pts[hint->ctrl0 + 1].y;
+ x2 = pts[hint->ctrl1 ].x; y2 = pts[hint->ctrl1 ].y;
+ x3 = pts[hint->ctrl1 + 1].x; y3 = pts[hint->ctrl1 + 1].y;
+ if (x0 == x1 && x2 == x3) {
+ adjusts[i].vert = gTrue;
+ adj0 = x0;
+ adj1 = x2;
+ } else if (y0 == y1 && y2 == y3) {
+ adjusts[i].vert = gFalse;
+ adj0 = y0;
+ adj1 = y2;
+ } else {
+ gfree(adjusts);
+ adjusts = NULL;
+ break;
+ }
+ if (adj0 > adj1) {
+ x0 = adj0;
+ adj0 = adj1;
+ adj1 = x0;
+ }
+ w = adj1 - adj0;
+ ww = splashRound(w);
+ if (ww == 0) {
+ ww = 1;
+ }
+ adjusts[i].x0a = adj0 - 0.01;
+ adjusts[i].x0b = adj0 + 0.01;
+ adjusts[i].xma = (SplashCoord)0.5 * (adj0 + adj1) - 0.01;
+ adjusts[i].xmb = (SplashCoord)0.5 * (adj0 + adj1) + 0.01;
+ adjusts[i].x1a = adj1 - 0.01;
+ adjusts[i].x1b = adj1 + 0.01;
+ adjusts[i].x0 = (SplashCoord)splashRound(adj0);
+ adjusts[i].x1 = adjusts[i].x0 + ww - 0.01;
+ adjusts[i].xm = (SplashCoord)0.5 * (adjusts[i].x0 + adjusts[i].x1);
+ adjusts[i].firstPt = hint->firstPt;
+ adjusts[i].lastPt = hint->lastPt;
+ }
+
+ } else {
+ adjusts = NULL;
+ }
+
+ // perform stroke adjustment
+ if (adjusts) {
+ for (i = 0, adjust = adjusts; i < path->hintsLength; ++i, ++adjust) {
+ for (j = adjust->firstPt; j <= adjust->lastPt; ++j) {
+ strokeAdjust(adjust, &pts[j].x, &pts[j].y);
+ }
+ }
+ gfree(adjusts);
+ }
+
+ segs = NULL;
+ length = size = 0;
+
+ x0 = y0 = xsp = ysp = 0; // make gcc happy
+ adj0 = adj1 = 0; // make gcc happy
+ curSubpath = 0;
+ curSubpathX = 0;
+ i = 0;
+ while (i < path->length) {
+
+ // first point in subpath - skip it
+ if (path->flags[i] & splashPathFirst) {
+ x0 = pts[i].x;
+ y0 = pts[i].y;
+ xsp = x0;
+ ysp = y0;
+ curSubpath = i;
+ curSubpathX = length;
+ ++i;
+
+ } else {
+
+ // curve segment
+ if (path->flags[i] & splashPathCurve) {
+ x1 = pts[i].x;
+ y1 = pts[i].y;
+ x2 = pts[i+1].x;
+ y2 = pts[i+1].y;
+ x3 = pts[i+2].x;
+ y3 = pts[i+2].y;
+ addCurve(x0, y0, x1, y1, x2, y2, x3, y3,
+ 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));
+ x0 = x3;
+ y0 = y3;
+ i += 3;
+
+ // line segment
+ } else {
+ x1 = pts[i].x;
+ y1 = pts[i].y;
+ addSegment(x0, y0, x1, y1,
+ 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));
+ x0 = x1;
+ y0 = y1;
+ ++i;
+ }
+
+ // close a subpath
+ if (closeSubpaths &&
+ (path->flags[i-1] & splashPathLast) &&
+ (pts[i-1].x != pts[curSubpath].x ||
+ pts[i-1].y != pts[curSubpath].y)) {
+ addSegment(x0, y0, xsp, ysp,
+ gFalse, gTrue, gFalse, gFalse);
+ }
+ }
+ }
+
+ gfree(pts);
+}
+
+// Apply the stroke adjust hints to point <pt>: (*<xp>, *<yp>).
+void SplashXPath::strokeAdjust(SplashXPathAdjust *adjust,
+ SplashCoord *xp, SplashCoord *yp) {
+ SplashCoord x, y;
+
+ if (adjust->vert) {
+ x = *xp;
+ if (x > adjust->x0a && x < adjust->x0b) {
+ *xp = adjust->x0;
+ } else if (x > adjust->xma && x < adjust->xmb) {
+ *xp = adjust->xm;
+ } else if (x > adjust->x1a && x < adjust->x1b) {
+ *xp = adjust->x1;
+ }
+ } else {
+ y = *yp;
+ if (y > adjust->x0a && y < adjust->x0b) {
+ *yp = adjust->x0;
+ } else if (y > adjust->xma && y < adjust->xmb) {
+ *yp = adjust->xm;
+ } else if (y > adjust->x1a && y < adjust->x1b) {
+ *yp = adjust->x1;
+ }
+ }
+}
+
+SplashXPath::SplashXPath(SplashXPath *xPath) {
+ length = xPath->length;
+ size = xPath->size;
+ segs = (SplashXPathSeg *)gmallocn(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 *)greallocn(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[splashMaxCurveSplits + 1][3];
+ SplashCoord cy[splashMaxCurveSplits + 1][3];
+ int cNext[splashMaxCurveSplits + 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 = splashMaxCurveSplits;
+ 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 < splashMaxCurveSplits) {
+
+ // 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 == splashMaxCurveSplits && last,
+ p1 == 0 && end0,
+ p2 == splashMaxCurveSplits && 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::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 {
+#if USE_FIXEDPOINT
+ if (FixedPoint::divCheck(x1 - x0, y1 - y0, &segs[length].dxdy)) {
+ segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
+ } else {
+ segs[length].dxdy = segs[length].dydx = 0;
+ if (splashAbs(x1 - x0) > splashAbs(y1 - y0)) {
+ segs[length].flags |= splashXPathHoriz;
+ } else {
+ segs[length].flags |= splashXPathVert;
+ }
+ }
+#else
+ segs[length].dxdy = (x1 - x0) / (y1 - y0);
+ segs[length].dydx = (SplashCoord)1 / segs[length].dxdy;
+#endif
+ }
+ 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::aaScale() {
+ SplashXPathSeg *seg;
+ int i;
+
+ for (i = 0, seg = segs; i < length; ++i, ++seg) {
+ seg->x0 *= splashAASize;
+ seg->y0 *= splashAASize;
+ seg->x1 *= splashAASize;
+ seg->y1 *= splashAASize;
+ }
+}
+
+void SplashXPath::sort() {
+ qsort(segs, length, sizeof(SplashXPathSeg), &cmpXPathSegs);
+}