summaryrefslogtreecommitdiff
path: root/Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc
diff options
context:
space:
mode:
authorAkira Kakuto <kakuto@fuk.kindai.ac.jp>2017-08-13 07:14:48 +0000
committerAkira Kakuto <kakuto@fuk.kindai.ac.jp>2017-08-13 07:14:48 +0000
commit4b4995cda35627e06c43e25ecbe07c1bc1859bb5 (patch)
tree143ed02a389bab62f44043a54cbc70f69e312e2f /Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc
parent00d00899c484b81967558f43c4fe4a896ffdf610 (diff)
xpdf 4.00
git-svn-id: svn://tug.org/texlive/trunk@45031 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc')
-rw-r--r--Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc377
1 files changed, 302 insertions, 75 deletions
diff --git a/Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc b/Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc
index a1599885e2b..f0164a85bd4 100644
--- a/Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc
+++ b/Build/source/libs/xpdf/xpdf-src/splash/SplashXPath.cc
@@ -18,12 +18,18 @@
#include <algorithm>
#endif
#include "gmem.h"
+#include "gmempp.h"
#include "SplashMath.h"
#include "SplashPath.h"
#include "SplashXPath.h"
//------------------------------------------------------------------------
+#define minCosSquaredJoinAngle 0.75
+#define maxPointToLineDistanceSquared 0.04
+
+//------------------------------------------------------------------------
+
struct SplashXPathPoint {
SplashCoord x, y;
};
@@ -54,29 +60,58 @@ inline void SplashXPath::transform(SplashCoord *matrix,
// SplashXPath
//------------------------------------------------------------------------
+// SplashXPath segment coords are clipped to +/-maxCoord to avoid
+// problems. The xMin/yMin/xMax/yMax fields are 32-bit integers, so
+// coords need to be < 2^31 / aa{Horiz,Vert}.
+#define maxCoord 100000000.0
+
+void SplashXPath::clampCoords(SplashCoord *x, SplashCoord *y) {
+#if !USE_FIXEDPOINT
+ if (*x > maxCoord) {
+ *x = maxCoord;
+ } else if (*x < -maxCoord) {
+ *x = -maxCoord;
+ }
+ if (*y > maxCoord) {
+ *y = maxCoord;
+ } else if (*y < -maxCoord) {
+ *y = -maxCoord;
+ }
+#endif
+}
+
SplashXPath::SplashXPath(SplashPath *path, SplashCoord *matrix,
- SplashCoord flatness, GBool closeSubpaths) {
+ SplashCoord flatness, GBool closeSubpaths,
+ GBool simplify,
+ SplashStrokeAdjustMode strokeAdjMode) {
SplashXPathPoint *pts;
- SplashCoord x0, y0, x1, y1, x2, y2, x3, y3, xsp, ysp;
- SplashCoord xMinFP, xMaxFP, yMinFP, yMaxFP;
- int curSubpath, i;
+ SplashCoord x0, y0, x1, y1, x2, y2, x3, y3, xsp, ysp, t;
+ int curSubpath, firstSegInSubpath, i;
+ GBool adjusted;
- // transform the points
+ //--- 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);
+ clampCoords(&pts[i].x, &pts[i].y);
}
- // do stroke adjustment
+ //--- do stroke adjustment
if (path->hints) {
- strokeAdjust(pts, path->hints, path->hintsLength);
+ adjusted = strokeAdjust(pts, path->hints, path->hintsLength,
+ strokeAdjMode);
+ } else {
+ adjusted = gFalse;
}
+ //--- construct the segments
+
segs = NULL;
length = size = 0;
x0 = y0 = xsp = ysp = 0; // make gcc happy
curSubpath = 0;
+ firstSegInSubpath = 0;
i = 0;
while (i < path->length) {
@@ -123,66 +158,85 @@ SplashXPath::SplashXPath(SplashPath *path, SplashCoord *matrix,
++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);
+ // end a subpath
+ if (path->flags[i-1] & splashPathLast) {
+ if (closeSubpaths &&
+ (pts[i-1].x != pts[curSubpath].x ||
+ pts[i-1].y != pts[curSubpath].y)) {
+ addSegment(x0, y0, xsp, ysp);
+ }
+ if (simplify && !adjusted) {
+ mergeSegments(firstSegInSubpath);
+ }
+ firstSegInSubpath = length;
}
}
}
gfree(pts);
+ finishSegments();
+
+ //--- check for a rectangle
+ isRect = gFalse;
+ rectX0 = rectY0 = rectX1 = rectY1 = 0;
+ if (length == 4) {
#if HAVE_STD_SORT
- std::sort(segs, segs + length, SplashXPathSeg::cmpY);
+ std::sort(segs, segs + length, SplashXPathSeg::cmpY);
#else
- qsort(segs, length, sizeof(SplashXPathSeg), &SplashXPathSeg::cmpY);
+ qsort(segs, length, sizeof(SplashXPathSeg), &SplashXPathSeg::cmpY);
#endif
-
- if (length == 0) {
- xMin = yMin = xMax = yMax = 0;
- } else {
- if (segs[0].x0 < segs[0].x1) {
- xMinFP = segs[0].x0;
- xMaxFP = segs[0].x1;
- } else {
- xMinFP = segs[0].x1;
- xMaxFP = segs[0].x0;
+ if (segs[0].y0 == segs[0].y1 &&
+ segs[1].x0 == segs[1].x1 &&
+ segs[2].x0 == segs[2].x1 &&
+ segs[3].y0 == segs[3].y1) {
+ isRect = gTrue;
+ rectX0 = segs[1].x0;
+ rectX1 = segs[2].x0;
+ rectY0 = segs[0].y0;
+ rectY1 = segs[3].y0;
+ } else if (segs[0].x0 == segs[0].x1 &&
+ segs[1].y0 == segs[1].y1 &&
+ segs[2].x0 == segs[2].x1 &&
+ segs[3].y0 == segs[3].y1) {
+ isRect = gTrue;
+ rectX0 = segs[0].x0;
+ rectX1 = segs[2].x0;
+ rectY0 = segs[1].y0;
+ rectY1 = segs[3].y0;
+ } else if (segs[0].x0 == segs[0].x1 &&
+ segs[1].x0 == segs[1].x1 &&
+ segs[2].y0 == segs[2].y1 &&
+ segs[3].y0 == segs[3].y1) {
+ isRect = gTrue;
+ rectX0 = segs[0].x0;
+ rectX1 = segs[1].x0;
+ rectY0 = segs[2].y0;
+ rectY1 = segs[3].y0;
}
- yMinFP = segs[0].y0;
- yMaxFP = segs[0].y1;
- for (i = 1; i < length; ++i) {
- if (segs[i].x0 < xMinFP) {
- xMinFP = segs[i].x0;
- } else if (segs[i].x0 > xMaxFP) {
- xMaxFP = segs[i].x0;
- }
- if (segs[i].x1 < xMinFP) {
- xMinFP = segs[i].x1;
- } else if (segs[i].x1 > xMaxFP) {
- xMaxFP = segs[i].x1;
+ if (isRect) {
+ if (rectX0 > rectX1) {
+ t = rectX0; rectX0 = rectX1; rectX1 = t;
}
- if (segs[i].y1 > yMaxFP) {
- yMaxFP = segs[i].y1;
+ if (rectY0 > rectY1) {
+ t = rectY0; rectY0 = rectY1; rectY1 = t;
}
}
- xMin = splashFloor(xMinFP);
- yMin = splashFloor(yMinFP);
- xMax = splashFloor(xMaxFP);
- yMax = splashFloor(yMaxFP);
}
}
-void SplashXPath::strokeAdjust(SplashXPathPoint *pts,
- SplashPathHint *hints, int nHints) {
+GBool SplashXPath::strokeAdjust(SplashXPathPoint *pts,
+ SplashPathHint *hints, int nHints,
+ SplashStrokeAdjustMode strokeAdjMode) {
SplashXPathAdjust *adjusts, *adjust;
SplashPathHint *hint;
SplashCoord x0, y0, x1, y1, x2, y2, x3, y3;
- SplashCoord adj0, adj1, d;
+ SplashCoord adj0, adj1, w, d;
int xi0, xi1;
int i, j;
+ GBool adjusted;
+
+ adjusted = gFalse;
// set up the stroke adjustment hints
adjusts = (SplashXPathAdjust *)gmallocn(nHints, sizeof(SplashXPathAdjust));
@@ -192,14 +246,21 @@ void SplashXPath::strokeAdjust(SplashXPathPoint *pts,
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;
+ w = -1;
if (x0 == x1 && x2 == x3) {
adjusts[i].vert = gTrue;
adj0 = x0;
adj1 = x2;
+ if (hint->projectingCap) {
+ w = splashAbs(y1 - y0);
+ }
} else if (y0 == y1 && y2 == y3) {
adjusts[i].vert = gFalse;
adj0 = y0;
adj1 = y2;
+ if (hint->projectingCap) {
+ w = splashAbs(x1 - x0);
+ }
} else {
goto done;
}
@@ -220,7 +281,7 @@ void SplashXPath::strokeAdjust(SplashXPathPoint *pts,
adjusts[i].xmb = (SplashCoord)0.5 * (adj0 + adj1) + d;
adjusts[i].x1a = adj1 - d;
adjusts[i].x1b = adj1 + d;
- splashStrokeAdjust(adj0, adj1, &xi0, &xi1);
+ splashStrokeAdjust(adj0, adj1, &xi0, &xi1, strokeAdjMode, w);
adjusts[i].x0 = (SplashCoord)xi0;
// the "minus epsilon" thing here is needed when vector
// antialiasing is turned off -- otherwise stroke adjusted lines
@@ -255,9 +316,11 @@ void SplashXPath::strokeAdjust(SplashXPathPoint *pts,
}
}
}
+ adjusted = gTrue;
done:
gfree(adjusts);
+ return adjusted;
}
SplashXPath::SplashXPath(SplashXPath *xPath) {
@@ -380,38 +443,202 @@ void SplashXPath::addCurve(SplashCoord x0, SplashCoord y0,
void SplashXPath::addSegment(SplashCoord x0, SplashCoord y0,
SplashCoord x1, SplashCoord y1) {
grow(1);
- if (y0 <= y1) {
- segs[length].x0 = x0;
- segs[length].y0 = y0;
- segs[length].x1 = x1;
- segs[length].y1 = y1;
- segs[length].count = 1;
- } else {
- segs[length].x0 = x1;
- segs[length].y0 = y1;
- segs[length].x1 = x0;
- segs[length].y1 = y0;
- segs[length].count = -1;
+ segs[length].x0 = x0;
+ segs[length].y0 = y0;
+ segs[length].x1 = x1;
+ segs[length].y1 = y1;
+ ++length;
+}
+
+// Returns true if the angle between (x0,y0)-(x1,y1) and
+// (x1,y1)-(x2,y2) is close to 180 degrees.
+static GBool joinAngleIsFlat(SplashCoord x0, SplashCoord y0,
+ SplashCoord x1, SplashCoord y1,
+ SplashCoord x2, SplashCoord y2) {
+ SplashCoord dx1, dy1, dx2, dy2, d, len1, len2;
+
+ dx1 = x1 - x0;
+ dy1 = y1 - y0;
+ dx2 = x2 - x1;
+ dy2 = y2 - y1;
+ d = dx1 * dx2 + dy1 * dy2;
+ len1 = dx1 * dx1 + dy1 * dy1;
+ len2 = dx2 * dx2 + dy2 * dy2;
+ return d > 0 && d * d > len1 * len2 * minCosSquaredJoinAngle;
+}
+
+// Returns true if (x1,y1) is sufficiently close to the segment
+// (x0,y0)-(x2,y2), looking at the perpendicular point-to-line
+// distance.
+static GBool pointCloseToSegment(SplashCoord x0, SplashCoord y0,
+ SplashCoord x1, SplashCoord y1,
+ SplashCoord x2, SplashCoord y2) {
+ SplashCoord t1, t2, dx, dy;
+
+ // compute the perpendicular distance from the point to the segment,
+ // i.e., the projection of (x0,y0)-(x1,y1) onto a unit normal to the
+ // segment (this actually computes the square of the distance)
+ dx = x2 - x0;
+ dy = y2 - y0;
+ t1 = dx*dx + dy*dy;
+ if (t1 < 0.0001) {
+ // degenerate case: (x0,y0) and (x2,y2) are (nearly) identical --
+ // just compute the distance to (x1,y1)
+ dx = x0 - x1;
+ dy = y0 - y1;
+ t2 = dx*dx + dy*dy;
+ return t2 < maxPointToLineDistanceSquared;
}
-#if USE_FIXEDPOINT
- if (y0 == y1 || x0 == x1 ||
- !FixedPoint::divCheck(x1 - x0, y1 - y0, &segs[length].dxdy) ||
- !FixedPoint::divCheck(y1 - y0, x1 - x0, &segs[length].dydx)) {
- segs[length].dxdy = 0;
- segs[length].dydx = 0;
+ t2 = x1 * dy - dx * y1 - x0 * y2 + x2 * y0;
+ // actual distance = t2 / sqrt(t1)
+ return t2 * t2 < t1 * maxPointToLineDistanceSquared;
+}
+
+// Attempt to simplify the path by merging sequences of consecutive
+// segments in [first] .. [length]-1.
+void SplashXPath::mergeSegments(int first) {
+ GBool horiz, vert;
+ int in, out, prev, i, j;
+
+ in = out = first;
+ while (in < length) {
+
+ // skip zero-length segments
+ if (segs[in].x0 == segs[in].x1 && segs[in].y0 == segs[in].y1) {
+ ++in;
+ continue;
+ }
+
+ horiz = segs[in].y0 == segs[in].y1;
+ vert = segs[in].x0 == segs[in].x1;
+
+ // check for a sequence of mergeable segments: in .. i
+ prev = in;
+ for (i = in + 1; i < length; ++i) {
+
+ // skip zero-length segments
+ if (segs[i].x0 == segs[i].x1 && segs[i].y0 == segs[i].y1) {
+ continue;
+ }
+
+ // check for a horizontal or vertical segment
+ if ((horiz && segs[in].y0 != segs[in].y1) ||
+ (vert && segs[in].x0 != segs[in].x1)) {
+ break;
+ }
+
+ // check the angle between segs i-1 and i
+ // (actually, we compare seg i to the previous non-zero-length
+ // segment, which may not be i-1)
+ if (!joinAngleIsFlat(segs[prev].x0, segs[prev].y0,
+ segs[i].x0, segs[i].y0,
+ segs[i].x1, segs[i].y1)) {
+ break;
+ }
+
+ // check the distances from the ends of segs in .. i-1 to the
+ // proposed new segment
+ for (j = in; j < i; ++j) {
+ if (!pointCloseToSegment(segs[in].x0, segs[in].y0,
+ segs[j].x1, segs[j].y1,
+ segs[i].x1, segs[i].y1)) {
+ break;
+ }
+ }
+ if (j < i) {
+ break;
+ }
+
+ prev = i;
+ }
+
+ // we can merge segs: in .. i-1
+ // (this may be the single segment: in)
+ segs[out].x0 = segs[in].x0;
+ segs[out].y0 = segs[in].y0;
+ segs[out].x1 = segs[i-1].x1;
+ segs[out].y1 = segs[i-1].y1;
+ in = i;
+ ++out;
}
+
+ length = out;
+}
+
+void SplashXPath::finishSegments() {
+ SplashXPathSeg *seg;
+ SplashCoord xMinFP, xMaxFP, yMinFP, yMaxFP, t;
+ int i;
+
+ xMinFP = yMinFP = xMaxFP = yMaxFP = 0;
+
+ for (i = 0; i < length; ++i) {
+ seg = &segs[i];
+
+ //--- compute the slopes
+ if (seg->y0 <= seg->y1) {
+ seg->count = 1;
+ } else {
+ t = seg->x0; seg->x0 = seg->x1; seg->x1 = t;
+ t = seg->y0; seg->y0 = seg->y1; seg->y1 = t;
+ seg->count = -1;
+ }
+#if USE_FIXEDPOINT
+ if (seg->y0 == seg->y1 || seg->x0 == seg->x1 ||
+ !FixedPoint::divCheck(seg->x1 - seg->x0, seg->y1 - seg->y0,
+ &seg->dxdy) ||
+ !FixedPoint::divCheck(seg->y1 - seg->y0, seg->x1 - seg->x0,
+ &seg->dydx)) {
+ seg->dxdy = 0;
+ seg->dydx = 0;
+ }
#else
- if (y0 == y1 || x0 == x1) {
- segs[length].dxdy = 0;
- segs[length].dydx = 0;
- } else {
- segs[length].dxdy = (x1 - x0) / (y1 - y0);
- if (segs[length].dxdy == 0) {
- segs[length].dydx = 0;
+ if (seg->y0 == seg->y1 || seg->x0 == seg->x1) {
+ seg->dxdy = 0;
+ seg->dydx = 0;
} else {
- segs[length].dydx = 1 / segs[length].dxdy;
+ seg->dxdy = (seg->x1 - seg->x0) / (seg->y1 - seg->y0);
+ if (seg->dxdy == 0) {
+ seg->dydx = 0;
+ } else {
+ seg->dydx = 1 / seg->dxdy;
+ }
}
- }
#endif
- ++length;
+
+ //--- update bbox
+ if (i == 0) {
+ if (seg->x0 <= seg->x1) {
+ xMinFP = seg->x0;
+ xMaxFP = seg->x1;
+ } else {
+ xMinFP = seg->x1;
+ xMaxFP = seg->x0;
+ }
+ yMinFP = seg->y0;
+ yMaxFP = seg->y1;
+ } else {
+ if (seg->x0 < xMinFP) {
+ xMinFP = seg->x0;
+ } else if (seg->x0 > xMaxFP) {
+ xMaxFP = seg->x0;
+ }
+ if (seg->x1 < xMinFP) {
+ xMinFP = seg->x1;
+ } else if (seg->x1 > xMaxFP) {
+ xMaxFP = seg->x1;
+ }
+ if (seg->y0 < yMinFP) {
+ yMinFP = seg->y0;
+ }
+ if (seg->y1 > yMaxFP) {
+ yMaxFP = seg->y1;
+ }
+ }
+ }
+
+ xMin = splashFloor(xMinFP);
+ yMin = splashFloor(yMinFP);
+ xMax = splashFloor(xMaxFP);
+ yMax = splashFloor(yMaxFP);
}