diff options
Diffstat (limited to 'Build/source/libs/xpdf/xpdf-src/splash/SplashXPathScanner.cc')
-rw-r--r-- | Build/source/libs/xpdf/xpdf-src/splash/SplashXPathScanner.cc | 567 |
1 files changed, 567 insertions, 0 deletions
diff --git a/Build/source/libs/xpdf/xpdf-src/splash/SplashXPathScanner.cc b/Build/source/libs/xpdf/xpdf-src/splash/SplashXPathScanner.cc new file mode 100644 index 00000000000..aee60cce61e --- /dev/null +++ b/Build/source/libs/xpdf/xpdf-src/splash/SplashXPathScanner.cc @@ -0,0 +1,567 @@ +//======================================================================== +// +// SplashXPathScanner.cc +// +// Copyright 2003-2013 Glyph & Cog, LLC +// +//======================================================================== + +#include <aconf.h> + +#ifdef USE_GCC_PRAGMAS +#pragma implementation +#endif + +#include <stdlib.h> +#include <string.h> +#if HAVE_STD_SORT +#include <algorithm> +#endif +#include "gmem.h" +#include "GList.h" +#include "SplashMath.h" +#include "SplashXPath.h" +#include "SplashXPathScanner.h" + +//------------------------------------------------------------------------ + +#define minVertStep 0.05 + +//------------------------------------------------------------------------ + +SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA, + int yMinA, int yMaxA) { + xPath = xPathA; + eo = eoA; + yMin = yMinA; + yMax = yMaxA; + + activeSegs = new GList(); + nextSeg = 0; + yNext = xPath->yMin; +} + +SplashXPathScanner::~SplashXPathScanner() { + delete activeSegs; +} + +void SplashXPathScanner::getSpan(Guchar *line, int y, int x0, int x1) { + SplashXPathSeg *seg, *seg0; + SplashCoord y0, y1, y1p; + GBool intersect, last; + int eoMask, state0, state1, count, i; + + //--- clear the scan line buffer + memset(line + x0, 0, x1 - x0 + 1); + + //--- reset the path + if (yNext != y) { + delete activeSegs; + activeSegs = new GList(); + nextSeg = 0; + while (nextSeg < xPath->length) { + seg = &xPath->segs[nextSeg]; + if (seg->y0 >= y) { + break; + } + if (seg->y0 != seg->y1 && seg->y1 > y) { + if (seg->y0 == y) { + seg->xCur0 = seg->x0; + } else { + seg->xCur0 = seg->x0 + ((SplashCoord)y - seg->y0) * seg->dxdy; + } + activeSegs->append(seg); + } + ++nextSeg; + } + activeSegs->sort(&SplashXPathSeg::cmpXi); + } + + //--- process the scan line + y0 = y; + while (y0 < y + 1) { + + //--- delete finished segs + i = 0; + while (i < activeSegs->getLength()) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (seg->y1 <= y0) { + activeSegs->del(i); + } else { + ++i; + } + } + + //--- check for bottom of path + if (!activeSegs->getLength() && nextSeg >= xPath->length) { + break; + } + + //--- sort activeSegs + sortActiveSegs(); + + //--- add waiting segs + while (nextSeg < xPath->length) { + seg = &xPath->segs[nextSeg]; + if (seg->y0 > y0) { + break; + } + if (seg->y0 != seg->y1) { + seg->xCur0 = seg->x0; + insertActiveSeg(seg); + } + ++nextSeg; + } + + //--- get the next "interesting" y value + y1 = y + 1; + if (nextSeg < xPath->length && xPath->segs[nextSeg].y0 < y1) { + y1 = xPath->segs[nextSeg].y0; + } + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (seg->y1 < y1) { + y1 = seg->y1; + } + } + + //--- compute xCur1 values, check for intersections + seg0 = NULL; + intersect = gFalse; + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (seg->y1 == y1) { + seg->xCur1 = seg->x1; + } else { + seg->xCur1 = seg->x0 + (y1 - seg->y0) * seg->dxdy; + } + if (seg0 && seg0->xCur1 > seg->xCur1) { + intersect = gTrue; + } + seg0 = seg; + } + + //--- draw rectangles + if (intersect) { + for (; y0 < y1; y0 += minVertStep) { + if ((y1p = y0 + minVertStep) >= y1) { + y1p = y1; + last = gTrue; + } else { + last = gFalse; + } + state0 = state1 = count = 0; + seg0 = NULL; + eoMask = eo ? 1 : 0xffffffff; + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (last && seg->y1 == y1) { + seg->xCur1 = seg->x1; + } else { + seg->xCur1 = seg->x0 + (y1p - seg->y0) * seg->dxdy; + } + count += seg->count; + state1 = count & eoMask; + if (!state0 && state1) { + seg0 = seg; + } else if (state0 && !state1) { + drawRectangle(line, x0, x1, y0, y1p, seg0->xCur0, seg->xCur0); + } + state0 = state1; + } + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + seg->xCur0 = seg->xCur1; + } + sortActiveSegs(); + } + + //--- draw trapezoids + } else { + state0 = state1 = count = 0; + seg0 = NULL; + eoMask = eo ? 1 : 0xffffffff; + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + count += seg->count; + state1 = count & eoMask; + if (!state0 && state1) { + seg0 = seg; + } else if (state0 && !state1) { + drawTrapezoid(line, x0, x1, y0, y1, + seg0->xCur0, seg0->xCur1, seg0->dydx, + seg->xCur0, seg->xCur1, seg->dydx); + } + state0 = state1; + } + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + seg->xCur0 = seg->xCur1; + } + } + + //--- next slice + y0 = y1; + } + + yNext = y + 1; +} + +void SplashXPathScanner::getSpanBinary(Guchar *line, int y, int x0, int x1) { + SplashXPathSeg *seg; + int xx0, xx1, xx; + int eoMask, state0, state1, count, i; + + //--- clear the scan line buffer + memset(line + x0, 0, x1 - x0 + 1); + + //--- reset the path + if (yNext != y) { + delete activeSegs; + activeSegs = new GList(); + nextSeg = 0; + while (nextSeg < xPath->length) { + seg = &xPath->segs[nextSeg]; + if (seg->y0 >= y) { + break; + } + if (seg->y1 > y) { + if (seg->y0 == y) { + seg->xCur0 = seg->x0; + } else { + seg->xCur0 = seg->x0 + ((SplashCoord)y - seg->y0) * seg->dxdy; + } + activeSegs->append(seg); + } + ++nextSeg; + } + activeSegs->sort(&SplashXPathSeg::cmpXi); + } + + //--- delete finished segs + i = 0; + while (i < activeSegs->getLength()) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (seg->y1 <= y) { + activeSegs->del(i); + } else { + ++i; + } + } + + //--- sort activeSegs + sortActiveSegs(); + + //--- add waiting segs + while (nextSeg < xPath->length) { + seg = &xPath->segs[nextSeg]; + if (seg->y0 >= y + 1) { + break; + } + seg->xCur0 = seg->x0; + insertActiveSeg(seg); + ++nextSeg; + } + + //--- compute xCur1 values + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (seg->y1 <= y + 1) { + seg->xCur1 = seg->x1; + } else { + seg->xCur1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy; + } + } + + //--- draw spans + state0 = state1 = count = 0; + eoMask = eo ? 1 : 0xffffffff; + xx0 = xx1 = 0; // make gcc happy + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + if (seg->y0 <= y && seg->y0 < seg->y1) { + count += seg->count; + state1 = count & eoMask; + } + if (state0) { + xx = splashCeil(seg->xCur0) - 1; + if (xx > xx1) { + xx1 = xx; + } + xx = splashFloor(seg->xCur1); + if (xx < xx0) { + xx0 = xx; + } + xx = splashCeil(seg->xCur1) - 1; + if (xx > xx1) { + xx1 = xx; + } + } else { + if (seg->xCur0 < seg->xCur1) { + xx0 = splashFloor(seg->xCur0); + xx1 = splashCeil(seg->xCur1) - 1; + } else { + xx0 = splashFloor(seg->xCur1); + xx1 = splashCeil(seg->xCur0) - 1; + } + } + if (!state1) { + if (xx0 < x0) { + xx0 = x0; + } + if (xx1 > x1) { + xx1 = x1; + } + for (xx = xx0; xx <= xx1; ++xx) { + line[xx] = 0xff; + } + } + state0 = state1; + } + + //--- update xCur0 values + for (i = 0; i < activeSegs->getLength(); ++i) { + seg = (SplashXPathSeg *)activeSegs->get(i); + seg->xCur0 = seg->xCur1; + } + + yNext = y + 1; +} + +inline void SplashXPathScanner::addArea(Guchar *line, int x, SplashCoord a) { + int a2, t; + + a2 = splashRound(a * 255); + if (a2 <= 0) { + return; + } + t = line[x] + a2; + if (t > 255) { + t = 255; + } + line[x] = t; +} + +// Draw a trapezoid with edges: +// top: (xa0, y0) - (xb0, y0) +// left: (xa0, y0) - (xa1, y1) +// right: (xb0, y0) - (xb1, y1) +// bottom: (xa1, y1) - (xb1, y1) +void SplashXPathScanner::drawTrapezoid(Guchar *line, int xMin, int xMax, + SplashCoord y0, SplashCoord y1, + SplashCoord xa0, SplashCoord xa1, + SplashCoord dydxa, + SplashCoord xb0, SplashCoord xb1, + SplashCoord dydxb) { + SplashCoord a, dy; + int x0, x1, x2, x3, x; + + // check for a rectangle + if (dydxa == 0 && dydxb == 0 && xa0 >= xMin && xb0 <= xMax) { + x0 = splashFloor(xa0); + x3 = splashFloor(xb0); + dy = y1 - y0; + if (x0 == x3) { + addArea(line, x0, (xb0 - xa0) * dy); + } else { + addArea(line, x0, ((SplashCoord)1 - (xa0 - x0)) * dy); + for (x = x0 + 1; x <= x3 - 1; ++x) { + addArea(line, x, y1 - y0); + } + addArea(line, x3, (xb0 - x3) * (y1 - y0)); + } + return; + } + + if (dydxa > 0) { + x0 = splashFloor(xa0); + x1 = splashFloor(xa1); + } else { + x0 = splashFloor(xa1); + x1 = splashFloor(xa0); + } + if (x0 < xMin) { + x0 = xMin; + } + if (dydxb > 0) { + x2 = splashFloor(xb0); + x3 = splashFloor(xb1); + } else { + x2 = splashFloor(xb1); + x3 = splashFloor(xb0); + } + if (x3 > xMax) { + x3 = xMax; + } + for (x = x0; x <= x3; ++x) { + a = y1 - y0; + if (x <= x1) { + a -= areaLeft(x, xa0, y0, xa1, y1, dydxa); + } + if (x >= x2) { + a -= areaRight(x, xb0, y0, xb1, y1, dydxb); + } + addArea(line, x, a); + } +} + +// Compute area within a pixel slice ((xp,y0)-(xp+1,y1)) to the left +// of a trapezoid edge ((x0,y0)-(x1,y1)). +SplashCoord SplashXPathScanner::areaLeft(int xp, + SplashCoord x0, SplashCoord y0, + SplashCoord x1, SplashCoord y1, + SplashCoord dydx) { + SplashCoord a, ya, yb; + + if (dydx >= 0) { + if (x0 >= xp) { + if (x1 <= xp + 1) { + a = ((x0 + x1) * 0.5 - xp) * (y1 - y0); + } else { + yb = y0 + ((SplashCoord)(xp + 1) - x0) * dydx; + a = (y1 - y0) - ((SplashCoord)(xp + 1) - x0) * (yb - y0) * 0.5; + } + } else { + if (x1 <= xp + 1) { + ya = y0 + ((SplashCoord)xp - x0) * dydx; + a = (x1 - xp) * (y1 - ya) * 0.5; + } else { + // ya = y1 - (x1 - xp - 0.5) * dydx; + // a = y1 - ya; + a = (x1 - xp - 0.5) * dydx; + } + } + } else { + if (x0 <= xp + 1) { + if (x1 >= xp) { + a = ((x0 + x1) * 0.5 - xp) * (y1 - y0); + } else { + ya = y0 + ((SplashCoord)xp - x0) * dydx; + a = (x0 - xp) * (ya - y0) * 0.5; + } + } else { + if (x1 >= xp) { + yb = y0 + ((SplashCoord)(xp + 1) - x0) * dydx; + a = (y1 - y0) - ((SplashCoord)(xp + 1) - x1) * (y1 - yb) * 0.5; + } else { + // ya = y0 + (xp - x0 + 0.5) * dydx; + // a = ya - y0; + a = ((SplashCoord)xp - x0 + 0.5) * dydx; + } + } + } + return a; +} + +// Compute area within a pixel slice ((xp,y0)-(xp+1,y1)) to the left +// of a trapezoid edge ((x0,y0)-(x1,y1)). +SplashCoord SplashXPathScanner::areaRight(int xp, + SplashCoord x0, SplashCoord y0, + SplashCoord x1, SplashCoord y1, + SplashCoord dydx) { + SplashCoord a, ya, yb; + + if (dydx >= 0) { + if (x0 >= xp) { + if (x1 <= xp + 1) { + a = ((SplashCoord)(xp + 1) - (x0 + x1) * 0.5) * (y1 - y0); + } else { + yb = y0 + ((SplashCoord)(xp + 1) - x0) * dydx; + a = ((SplashCoord)(xp + 1) - x0) * (yb - y0) * 0.5; + } + } else { + if (x1 <= xp + 1) { + ya = y0 + ((SplashCoord)xp - x0) * dydx; + a = (y1 - y0) - (x1 - xp) * (y1 - ya) * 0.5; + } else { + // ya = y0 + (xp - x0 + 0.5) * dydx; + // a = ya - y0; + a = ((SplashCoord)xp + 0.5 - x0) * dydx; + } + } + } else { + if (x0 <= xp + 1) { + if (x1 >= xp) { + a = ((SplashCoord)(xp + 1) - (x0 + x1) * 0.5) * (y1 - y0); + } else { + ya = y0 + ((SplashCoord)xp - x0) * dydx; + a = (y1 - y0) - (x0 - xp) * (ya - y0) * 0.5; + } + } else { + if (x1 >= xp) { + yb = y0 + ((SplashCoord)(xp + 1) - x0) * dydx; + a = ((SplashCoord)(xp + 1) - x1) * (y1 - yb) * 0.5; + } else { + // ya = y1 - (x1 - xp - 0.5) * dydx; + // a = y1 - ya; + a = (x1 - xp - 0.5) * dydx; + } + } + } + return a; +} + +void SplashXPathScanner::drawRectangle(Guchar *line, int xMin, int xMax, + SplashCoord y0, SplashCoord y1, + SplashCoord x0, SplashCoord x1) { + SplashCoord dy, a; + int xx0, xx1, x; + + xx0 = splashFloor(x0); + if (xx0 < xMin) { + xx0 = xMin; + } + xx1 = splashFloor(x1); + if (xx1 > xMax) { + xx1 = xMax; + } + dy = y1 - y0; + for (x = xx0; x <= xx1; ++x) { + a = dy; + if ((SplashCoord)x < x0) { + a -= (x0 - x) * dy; + } + if ((SplashCoord)(x + 1) > x1) { + a -= ((SplashCoord)(x + 1) - x1) * dy; + } + addArea(line, x, a); + } +} + +void SplashXPathScanner::sortActiveSegs() { + SplashXPathSeg *seg0, *seg1; + int i, j, k; + + if (activeSegs->getLength() < 2) { + return; + } + seg0 = (SplashXPathSeg *)activeSegs->get(0); + for (i = 1; i < activeSegs->getLength(); ++i) { + seg1 = (SplashXPathSeg *)activeSegs->get(i); + if (SplashXPathSeg::cmpX(seg0, seg1) > 0) { + for (j = i - 1; j > 0; --j) { + if (SplashXPathSeg::cmpX((SplashXPathSeg *)activeSegs->get(j - 1), + seg1) <= 0) { + break; + } + } + for (k = i; k > j; --k) { + activeSegs->put(k, activeSegs->get(k-1)); + } + activeSegs->put(j, seg1); + } else { + seg0 = seg1; + } + } +} + +void SplashXPathScanner::insertActiveSeg(SplashXPathSeg *seg) { + int i; + + for (i = 0; i < activeSegs->getLength(); ++i) { + if (SplashXPathSeg::cmpX(seg, (SplashXPathSeg *)activeSegs->get(i)) < 0) { + break; + } + } + activeSegs->insert(i, seg); +} |