summaryrefslogtreecommitdiff
path: root/splash/SplashXPathScanner.cc
diff options
context:
space:
mode:
Diffstat (limited to 'splash/SplashXPathScanner.cc')
-rw-r--r--splash/SplashXPathScanner.cc899
1 files changed, 464 insertions, 435 deletions
diff --git a/splash/SplashXPathScanner.cc b/splash/SplashXPathScanner.cc
index abe4593..aee60cc 100644
--- a/splash/SplashXPathScanner.cc
+++ b/splash/SplashXPathScanner.cc
@@ -2,6 +2,8 @@
//
// SplashXPathScanner.cc
//
+// Copyright 2003-2013 Glyph & Cog, LLC
+//
//========================================================================
#include <aconf.h>
@@ -16,523 +18,550 @@
#include <algorithm>
#endif
#include "gmem.h"
+#include "GList.h"
#include "SplashMath.h"
#include "SplashXPath.h"
-#include "SplashBitmap.h"
#include "SplashXPathScanner.h"
//------------------------------------------------------------------------
-struct SplashIntersect {
- int y;
- int x0, x1; // intersection of segment with [y, y+1)
- int count; // EO/NZWN counter increment
-};
-
-#if HAVE_STD_SORT
-
-struct cmpIntersectFunctor {
- bool operator()(const SplashIntersect &i0, const SplashIntersect &i1) {
- return (i0.y != i1.y) ? (i0.y < i1.y) : (i0.x0 < i1.x0);
- }
-};
-
-#else // HAVE_STD_SORT
+#define minVertStep 0.05
-static int cmpIntersect(const void *p0, const void *p1) {
- SplashIntersect *i0 = (SplashIntersect *)p0;
- SplashIntersect *i1 = (SplashIntersect *)p1;
- int cmp;
-
- if ((cmp = i0->y - i1->y) == 0) {
- cmp = i0->x0 - i1->x0;
- }
- return cmp;
-}
-
-#endif // HAVE_STD_SORT
-
-//------------------------------------------------------------------------
-// SplashXPathScanner
//------------------------------------------------------------------------
SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA,
- int clipYMin, int clipYMax) {
- SplashXPathSeg *seg;
- SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
- int i;
-
+ int yMinA, int yMaxA) {
xPath = xPathA;
eo = eoA;
- partialClip = gFalse;
+ yMin = yMinA;
+ yMax = yMaxA;
- // compute the bbox
- if (xPath->length == 0) {
- xMin = yMin = 1;
- xMax = yMax = 0;
- } else {
- seg = &xPath->segs[0];
- if (seg->x0 <= seg->x1) {
- xMinFP = seg->x0;
- xMaxFP = seg->x1;
- } else {
- xMinFP = seg->x1;
- xMaxFP = seg->x0;
- }
- if (seg->flags & splashXPathFlip) {
- yMinFP = seg->y1;
- yMaxFP = seg->y0;
- } else {
- yMinFP = seg->y0;
- yMaxFP = seg->y1;
- }
- for (i = 1; i < xPath->length; ++i) {
- seg = &xPath->segs[i];
- 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;
+ 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->flags & splashXPathFlip) {
- if (seg->y0 > yMaxFP) {
- yMaxFP = seg->y0;
- }
- } else {
- if (seg->y1 > yMaxFP) {
- yMaxFP = seg->y1;
+ 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;
}
- xMin = splashFloor(xMinFP);
- xMax = splashFloor(xMaxFP);
- yMin = splashFloor(yMinFP);
- yMax = splashFloor(yMaxFP);
- if (clipYMin > yMin) {
- yMin = clipYMin;
- partialClip = gTrue;
- }
- if (clipYMax < yMax) {
- yMax = clipYMax;
- partialClip = gTrue;
- }
+ activeSegs->sort(&SplashXPathSeg::cmpXi);
}
- allInter = NULL;
- inter = NULL;
- computeIntersections();
- interY = yMin - 1;
-}
+ //--- process the scan line
+ y0 = y;
+ while (y0 < y + 1) {
-SplashXPathScanner::~SplashXPathScanner() {
- gfree(inter);
- gfree(allInter);
-}
+ //--- delete finished segs
+ i = 0;
+ while (i < activeSegs->getLength()) {
+ seg = (SplashXPathSeg *)activeSegs->get(i);
+ if (seg->y1 <= y0) {
+ activeSegs->del(i);
+ } else {
+ ++i;
+ }
+ }
-void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA,
- int *xMaxA, int *yMaxA) {
- *xMinA = xMin / splashAASize;
- *yMinA = yMin / splashAASize;
- *xMaxA = xMax / splashAASize;
- *yMaxA = yMax / splashAASize;
-}
+ //--- check for bottom of path
+ if (!activeSegs->getLength() && nextSeg >= xPath->length) {
+ break;
+ }
-void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
- int interBegin, interEnd, xx, i;
+ //--- sort activeSegs
+ sortActiveSegs();
- if (y < yMin || y > yMax) {
- interBegin = interEnd = 0;
- } else {
- interBegin = inter[y - yMin];
- interEnd = inter[y - yMin + 1];
- }
- if (interBegin < interEnd) {
- *spanXMin = allInter[interBegin].x0;
- xx = allInter[interBegin].x1;
- for (i = interBegin + 1; i < interEnd; ++i) {
- if (allInter[i].x1 > xx) {
- xx = allInter[i].x1;
+ //--- 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;
}
- *spanXMax = xx;
- } else {
- *spanXMin = xMax + 1;
- *spanXMax = xMax;
- }
-}
-GBool SplashXPathScanner::test(int x, int y) {
- int interBegin, interEnd, count, i;
-
- if (y < yMin || y > yMax) {
- return gFalse;
- }
- interBegin = inter[y - yMin];
- interEnd = inter[y - yMin + 1];
- count = 0;
- for (i = interBegin; i < interEnd && allInter[i].x0 <= x; ++i) {
- if (x <= allInter[i].x1) {
- return gTrue;
+ //--- 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;
+ }
}
- count += allInter[i].count;
- }
- return eo ? (count & 1) : (count != 0);
-}
-GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
- int interBegin, interEnd, count, xx1, i;
+ //--- 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;
+ }
- if (y < yMin || y > yMax) {
- return gFalse;
- }
- interBegin = inter[y - yMin];
- interEnd = inter[y - yMin + 1];
- count = 0;
- for (i = interBegin; i < interEnd && allInter[i].x1 < x0; ++i) {
- count += allInter[i].count;
- }
+ //--- 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();
+ }
- // invariant: the subspan [x0,xx1] is inside the path
- xx1 = x0 - 1;
- while (xx1 < x1) {
- if (i >= interEnd) {
- return gFalse;
- }
- if (allInter[i].x0 > xx1 + 1 &&
- !(eo ? (count & 1) : (count != 0))) {
- return gFalse;
- }
- if (allInter[i].x1 > xx1) {
- xx1 = allInter[i].x1;
+ //--- 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;
+ }
}
- count += allInter[i].count;
- ++i;
+
+ //--- next slice
+ y0 = y1;
}
- return gTrue;
+ yNext = y + 1;
}
-GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
- int interEnd, xx0, xx1;
-
- if (y < yMin || y > yMax) {
- return gFalse;
- }
- if (interY != y) {
- interY = y;
- interIdx = inter[y - yMin];
- interCount = 0;
- }
- interEnd = inter[y - yMin + 1];
- if (interIdx >= interEnd) {
- return gFalse;
+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);
}
- xx0 = allInter[interIdx].x0;
- xx1 = allInter[interIdx].x1;
- interCount += allInter[interIdx].count;
- ++interIdx;
- while (interIdx < interEnd &&
- (allInter[interIdx].x0 <= xx1 ||
- (eo ? (interCount & 1) : (interCount != 0)))) {
- if (allInter[interIdx].x1 > xx1) {
- xx1 = allInter[interIdx].x1;
+
+ //--- delete finished segs
+ i = 0;
+ while (i < activeSegs->getLength()) {
+ seg = (SplashXPathSeg *)activeSegs->get(i);
+ if (seg->y1 <= y) {
+ activeSegs->del(i);
+ } else {
+ ++i;
}
- interCount += allInter[interIdx].count;
- ++interIdx;
}
- *x0 = xx0;
- *x1 = xx1;
- return gTrue;
-}
-void SplashXPathScanner::computeIntersections() {
- SplashXPathSeg *seg;
- SplashCoord segXMin, segXMax, segYMin, segYMax, xx0, xx1;
- int x, y, y0, y1, i;
+ //--- sort activeSegs
+ sortActiveSegs();
- if (yMin > yMax) {
- return;
+ //--- add waiting segs
+ while (nextSeg < xPath->length) {
+ seg = &xPath->segs[nextSeg];
+ if (seg->y0 >= y + 1) {
+ break;
+ }
+ seg->xCur0 = seg->x0;
+ insertActiveSeg(seg);
+ ++nextSeg;
}
- // build the list of all intersections
- allInterLen = 0;
- allInterSize = 16;
- allInter = (SplashIntersect *)gmallocn(allInterSize,
- sizeof(SplashIntersect));
- for (i = 0; i < xPath->length; ++i) {
- seg = &xPath->segs[i];
- if (seg->flags & splashXPathFlip) {
- segYMin = seg->y1;
- segYMax = seg->y0;
+ //--- 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 {
- segYMin = seg->y0;
- segYMax = seg->y1;
+ seg->xCur1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
}
- if (seg->flags & splashXPathHoriz) {
- y = splashFloor(seg->y0);
- if (y >= yMin && y <= yMax) {
- addIntersection(segYMin, segYMax, seg->flags,
- y, splashFloor(seg->x0), splashFloor(seg->x1));
- }
- } else if (seg->flags & splashXPathVert) {
- y0 = splashFloor(segYMin);
- if (y0 < yMin) {
- y0 = yMin;
+ }
+
+ //--- 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;
}
- y1 = splashFloor(segYMax);
- if (y1 > yMax) {
- y1 = yMax;
+ xx = splashFloor(seg->xCur1);
+ if (xx < xx0) {
+ xx0 = xx;
}
- x = splashFloor(seg->x0);
- for (y = y0; y <= y1; ++y) {
- addIntersection(segYMin, segYMax, seg->flags, y, x, x);
+ xx = splashCeil(seg->xCur1) - 1;
+ if (xx > xx1) {
+ xx1 = xx;
}
} else {
- if (seg->x0 < seg->x1) {
- segXMin = seg->x0;
- segXMax = seg->x1;
+ if (seg->xCur0 < seg->xCur1) {
+ xx0 = splashFloor(seg->xCur0);
+ xx1 = splashCeil(seg->xCur1) - 1;
} else {
- segXMin = seg->x1;
- segXMax = seg->x0;
+ xx0 = splashFloor(seg->xCur1);
+ xx1 = splashCeil(seg->xCur0) - 1;
}
- y0 = splashFloor(segYMin);
- if (y0 < yMin) {
- y0 = yMin;
+ }
+ if (!state1) {
+ if (xx0 < x0) {
+ xx0 = x0;
}
- y1 = splashFloor(segYMax);
- if (y1 > yMax) {
- y1 = yMax;
+ if (xx1 > x1) {
+ xx1 = x1;
}
- // this loop could just add seg->dxdy to xx1 on each iteration,
- // but that introduces numerical accuracy problems
- xx1 = seg->x0 + ((SplashCoord)y0 - seg->y0) * seg->dxdy;
- for (y = y0; y <= y1; ++y) {
- xx0 = xx1;
- xx1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
- // the segment may not actually extend to the top and/or bottom edges
- if (xx0 < segXMin) {
- xx0 = segXMin;
- } else if (xx0 > segXMax) {
- xx0 = segXMax;
- }
- if (xx1 < segXMin) {
- xx1 = segXMin;
- } else if (xx1 > segXMax) {
- xx1 = segXMax;
- }
- addIntersection(segYMin, segYMax, seg->flags, y,
- splashFloor(xx0), splashFloor(xx1));
+ for (xx = xx0; xx <= xx1; ++xx) {
+ line[xx] = 0xff;
}
}
+ state0 = state1;
}
-#if HAVE_STD_SORT
- std::sort(allInter, allInter + allInterLen, cmpIntersectFunctor());
-#else
- qsort(allInter, allInterLen, sizeof(SplashIntersect), cmpIntersect);
-#endif
- // build the list of y pointers
- inter = (int *)gmallocn(yMax - yMin + 2, sizeof(int));
- i = 0;
- for (y = yMin; y <= yMax; ++y) {
- inter[y - yMin] = i;
- while (i < allInterLen && allInter[i].y <= y) {
- ++i;
- }
+ //--- update xCur0 values
+ for (i = 0; i < activeSegs->getLength(); ++i) {
+ seg = (SplashXPathSeg *)activeSegs->get(i);
+ seg->xCur0 = seg->xCur1;
}
- inter[yMax - yMin + 1] = i;
+
+ yNext = y + 1;
}
-void SplashXPathScanner::addIntersection(double segYMin, double segYMax,
- Guint segFlags,
- int y, int x0, int x1) {
- if (allInterLen == allInterSize) {
- allInterSize *= 2;
- allInter = (SplashIntersect *)greallocn(allInter, allInterSize,
- sizeof(SplashIntersect));
+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;
}
- allInter[allInterLen].y = y;
- if (x0 < x1) {
- allInter[allInterLen].x0 = x0;
- allInter[allInterLen].x1 = x1;
+
+ if (dydxa > 0) {
+ x0 = splashFloor(xa0);
+ x1 = splashFloor(xa1);
} else {
- allInter[allInterLen].x0 = x1;
- allInter[allInterLen].x1 = x0;
+ x0 = splashFloor(xa1);
+ x1 = splashFloor(xa0);
+ }
+ if (x0 < xMin) {
+ x0 = xMin;
}
- if (segYMin <= y &&
- (SplashCoord)y < segYMax &&
- !(segFlags & splashXPathHoriz)) {
- allInter[allInterLen].count = eo ? 1
- : (segFlags & splashXPathFlip) ? 1 : -1;
+ if (dydxb > 0) {
+ x2 = splashFloor(xb0);
+ x3 = splashFloor(xb1);
} else {
- allInter[allInterLen].count = 0;
+ 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);
}
- ++allInterLen;
}
-void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
- int *x0, int *x1, int y) {
- int xx0, xx1, xx, xxMin, xxMax, yy, interEnd;
- Guchar mask;
- SplashColorPtr p;
-
- memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
- xxMin = aaBuf->getWidth();
- xxMax = -1;
- if (yMin <= yMax) {
- if (splashAASize * y < yMin) {
- interIdx = inter[0];
- } else if (splashAASize * y > yMax) {
- interIdx = inter[yMax - yMin + 1];
+// 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 {
- interIdx = inter[splashAASize * y - yMin];
+ 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;
+ }
}
- for (yy = 0; yy < splashAASize; ++yy) {
- if (splashAASize * y + yy < yMin) {
- interEnd = inter[0];
- } else if (splashAASize * y + yy > yMax) {
- interEnd = inter[yMax - yMin + 1];
+ } else {
+ if (x0 <= xp + 1) {
+ if (x1 >= xp) {
+ a = ((x0 + x1) * 0.5 - xp) * (y1 - y0);
} else {
- interEnd = inter[splashAASize * y + yy - yMin + 1];
+ ya = y0 + ((SplashCoord)xp - x0) * dydx;
+ a = (x0 - xp) * (ya - y0) * 0.5;
}
- interCount = 0;
- while (interIdx < interEnd) {
- xx0 = allInter[interIdx].x0;
- xx1 = allInter[interIdx].x1;
- interCount += allInter[interIdx].count;
- ++interIdx;
- while (interIdx < interEnd &&
- (allInter[interIdx].x0 <= xx1 ||
- (eo ? (interCount & 1) : (interCount != 0)))) {
- if (allInter[interIdx].x1 > xx1) {
- xx1 = allInter[interIdx].x1;
- }
- interCount += allInter[interIdx].count;
- ++interIdx;
- }
- if (xx0 < 0) {
- xx0 = 0;
- }
- ++xx1;
- if (xx1 > aaBuf->getWidth()) {
- xx1 = aaBuf->getWidth();
- }
- // set [xx0, xx1) to 1
- if (xx0 < xx1) {
- xx = xx0;
- p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
- if (xx & 7) {
- mask = 0xff >> (xx & 7);
- if ((xx & ~7) == (xx1 & ~7)) {
- mask &= (Guchar)(0xff00 >> (xx1 & 7));
- }
- *p++ |= mask;
- xx = (xx & ~7) + 8;
- }
- for (; xx + 7 < xx1; xx += 8) {
- *p++ |= 0xff;
- }
- if (xx < xx1) {
- *p |= (Guchar)(0xff00 >> (xx1 & 7));
- }
- }
- if (xx0 < xxMin) {
- xxMin = xx0;
- }
- if (xx1 > xxMax) {
- xxMax = xx1;
- }
+ } 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;
}
}
}
- *x0 = xxMin / splashAASize;
- *x1 = (xxMax - 1) / splashAASize;
+ return a;
}
-void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
- int *x0, int *x1, int y) {
- int xx0, xx1, xx, yy, interEnd;
- Guchar mask;
- SplashColorPtr p;
-
- for (yy = 0; yy < splashAASize; ++yy) {
- xx = *x0 * splashAASize;
- if (yMin <= yMax) {
- if (splashAASize * y + yy < yMin) {
- interIdx = interEnd = inter[0];
- } else if (splashAASize * y + yy > yMax) {
- interIdx = interEnd = inter[yMax - yMin + 1];
+// 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 {
- interIdx = inter[splashAASize * y + yy - yMin];
- if (splashAASize * y + yy > yMax) {
- interEnd = inter[yMax - yMin + 1];
- } else {
- interEnd = inter[splashAASize * y + yy - yMin + 1];
- }
+ yb = y0 + ((SplashCoord)(xp + 1) - x0) * dydx;
+ a = ((SplashCoord)(xp + 1) - x0) * (yb - y0) * 0.5;
}
- interCount = 0;
- while (interIdx < interEnd && xx < (*x1 + 1) * splashAASize) {
- xx0 = allInter[interIdx].x0;
- xx1 = allInter[interIdx].x1;
- interCount += allInter[interIdx].count;
- ++interIdx;
- while (interIdx < interEnd &&
- (allInter[interIdx].x0 <= xx1 ||
- (eo ? (interCount & 1) : (interCount != 0)))) {
- if (allInter[interIdx].x1 > xx1) {
- xx1 = allInter[interIdx].x1;
- }
- interCount += allInter[interIdx].count;
- ++interIdx;
- }
- if (xx0 > aaBuf->getWidth()) {
- xx0 = aaBuf->getWidth();
- }
- // set [xx, xx0) to 0
- if (xx < xx0) {
- p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
- if (xx & 7) {
- mask = (Guchar)(0xff00 >> (xx & 7));
- if ((xx & ~7) == (xx0 & ~7)) {
- mask |= 0xff >> (xx0 & 7);
- }
- *p++ &= mask;
- xx = (xx & ~7) + 8;
- }
- for (; xx + 7 < xx0; xx += 8) {
- *p++ = 0x00;
- }
- if (xx < xx0) {
- *p &= 0xff >> (xx0 & 7);
- }
- }
- if (xx1 >= xx) {
- xx = xx1 + 1;
- }
+ } 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;
}
}
- xx0 = (*x1 + 1) * splashAASize;
- // set [xx, xx0) to 0
- if (xx < xx0) {
- p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
- if (xx & 7) {
- mask = (Guchar)(0xff00 >> (xx & 7));
- if ((xx & ~7) == (xx0 & ~7)) {
- mask &= 0xff >> (xx0 & 7);
- }
- *p++ &= mask;
- xx = (xx & ~7) + 8;
+ } 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;
}
- for (; xx + 7 < xx0; xx += 8) {
- *p++ = 0x00;
+ } 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;
}
- if (xx < xx0) {
- *p &= 0xff >> (xx0 & 7);
+ }
+ }
+ 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);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-23 23:22:25 +0000