diff options
author | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-07-08 17:17:02 +0000 |
---|---|---|
committer | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-07-08 17:17:02 +0000 |
commit | 07e97fccd2d85076cd22ef411b0773ab92a18abe (patch) | |
tree | 0a764160f5eb642f4fe46c06df9fbffe0e9f8eda | |
parent | a95959c3fb4c502b45bc78f15b65cda1f21620e6 (diff) |
path ops work in progress
BUG=
Review URL: https://codereview.chromium.org/18058007
git-svn-id: http://skia.googlecode.com/svn/trunk@9908 2bbb7eff-a529-9590-31e7-b0007b416f81
31 files changed, 1073 insertions, 576 deletions
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index 11876f8d73..418e107e41 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -105,6 +105,11 @@ int intersect() { double lineT = findLineT(cubicT); if (pinTs(&cubicT, &lineT)) { SkDPoint pt = line.xyAtT(lineT); +#if ONE_OFF_DEBUG + SkDPoint cPt = cubic.xyAtT(cubicT); + SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, + cPt.fX, cPt.fY); +#endif intersections.insert(cubicT, lineT, pt); } } @@ -165,11 +170,34 @@ protected: void addEndPoints() { for (int cIndex = 0; cIndex < 4; cIndex += 3) { + bool foundEnd = false; for (int lIndex = 0; lIndex < 2; lIndex++) { if (cubic[cIndex] == line[lIndex]) { intersections.insert(cIndex >> 1, lIndex, line[lIndex]); + foundEnd = true; } } + // for the test case this was written for, the dist / error ratio was 170.6667 + // it looks like the cubic stops short of touching the line, but this fixed it. + if (foundEnd) { + continue; + } + // See if the cubic end touches the line. + double dist = line.isLeft(cubic[cIndex]); // this distance isn't cartesian + SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line + // compute the ULPS of the larger of the x/y deltas + double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY)); + if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance? + continue; + } + double lineT = findLineT(cIndex >> 1); + if (!between(0, lineT, 1)) { + continue; + } + SkDPoint linePt = line.xyAtT(lineT); + if (linePt.approximatelyEqual(cubic[cIndex])) { + intersections.insert(cIndex >> 1, lineT, cubic[cIndex]); + } } } diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index 13c0dbbef4..3b88b88702 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -75,13 +75,51 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { return computePoints(a, used); } -/* - Determine the intersection point of two line segments - Return FALSE if the lines don't intersect - from: http://paulbourke.net/geometry/lineline2d/ - */ +static bool checkEndPoint(double x, double y, const SkDLine& l, double* tPtr, int useX) { + if (!between(l[0].fX, x, l[1].fX) || !between(l[0].fY, y, l[1].fY)) { + return false; + } + double xLen = l[1].fX - l[0].fX; + double yLen = l[1].fY - l[0].fY; + if (useX < 0) { + useX = SkTAbs(xLen) > SkTAbs(yLen); + } + // OPTIMIZATION: do between test before divide + double t = useX ? (x - l[0].fX) / xLen : (y - l[0].fY) / yLen; + if (!between(0, t, 1)) { + return false; + } + double opp = useX ? (1 - t) * l[0].fY + t * l[1].fY : (1 - t) * l[0].fX + t * l[1].fX; + if (!AlmostEqualUlps(opp, useX ? y : x)) { + return false; + } + *tPtr = t; + return true; +} +// note that this only works if both lines are neither horizontal nor vertical int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { + // see if end points intersect the opposite line + double t; + for (int iA = 0; iA < 2; ++iA) { + if (!checkEndPoint(a[iA].fX, a[iA].fY, b, &t, -1)) { + continue; + } + insert(iA, t, a[iA]); + } + for (int iB = 0; iB < 2; ++iB) { + if (!checkEndPoint(b[iB].fX, b[iB].fY, a, &t, -1)) { + continue; + } + insert(t, iB, b[iB]); + } + if (used() > 0) { + SkASSERT(fUsed <= 2); + return used(); // coincident lines are returned here + } + /* Determine the intersection point of two line segments + Return FALSE if the lines don't intersect + from: http://paulbourke.net/geometry/lineline2d/ */ double axLen = a[1].fX - a[0].fX; double ayLen = a[1].fY - a[0].fY; double bxLen = b[1].fX - b[0].fX; @@ -105,64 +143,14 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { && !approximately_zero_inverse(numerB))) && !sk_double_isnan(numerA) && !sk_double_isnan(numerB)) { if (mayNotOverlap) { - return fUsed = 0; + return 0; } fT[0][0] = numerA; fT[1][0] = numerB; fPt[0] = a.xyAtT(numerA); return computePoints(a, 1); } - /* See if the axis intercepts match: - ay - ax * ayLen / axLen == by - bx * ayLen / axLen - axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) - axLen * ay - ax * ayLen == axLen * by - bx * ayLen - */ - if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX, - axLen * b[0].fY - ayLen * b[0].fX)) { - return fUsed = 0; - } - const double* aPtr; - const double* bPtr; - if (fabs(axLen) > fabs(ayLen) || fabs(bxLen) > fabs(byLen)) { - aPtr = &a[0].fX; - bPtr = &b[0].fX; - } else { - aPtr = &a[0].fY; - bPtr = &b[0].fY; - } - double a0 = aPtr[0]; - double a1 = aPtr[2]; - double b0 = bPtr[0]; - double b1 = bPtr[2]; - // OPTIMIZATION: restructure to reject before the divide - // e.g., if ((a0 - b0) * (a0 - a1) < 0 || abs(a0 - b0) > abs(a0 - a1)) - // (except efficient) - double aDenom = a0 - a1; - if (approximately_zero(aDenom)) { - if (!between(b0, a0, b1)) { - return fUsed = 0; - } - fT[0][0] = fT[0][1] = 0; - } else { - double at0 = (a0 - b0) / aDenom; - double at1 = (a0 - b1) / aDenom; - if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { - return fUsed = 0; - } - fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); - fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); - } - double bDenom = b0 - b1; - if (approximately_zero(bDenom)) { - fT[1][0] = fT[1][1] = 0; - } else { - int bIn = aDenom * bDenom < 0; - fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / bDenom, 1.0), 0.0); - fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / bDenom, 1.0), 0.0); - } - bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; - SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); - return computePoints(a, 1 + second); + return 0; } int SkIntersections::horizontal(const SkDLine& line, double y) { @@ -174,7 +162,7 @@ int SkIntersections::horizontal(const SkDLine& line, double y) { if (min > y || max < y) { return fUsed = 0; } - if (AlmostEqualUlps(min, max)) { + if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) { fT[0][0] = 0; fT[0][1] = 1; return fUsed = 2; @@ -183,42 +171,51 @@ int SkIntersections::horizontal(const SkDLine& line, double y) { return fUsed = 1; } +static bool checkEndPointH(const SkDPoint& end, double left, double right, + double y, bool flipped, double* tPtr) { + if (!between(left, end.fX, right) || !AlmostEqualUlps(y, end.fY)) { + return false; + } + double t = (end.fX - left) / (right - left); + SkASSERT(between(0, t, 1)); + *tPtr = flipped ? 1 - t : t; + return true; +} + int SkIntersections::horizontal(const SkDLine& line, double left, double right, double y, bool flipped) { - int result = horizontal(line, y); - switch (result) { - case 0: - break; - case 1: { - double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); - if (!precisely_between(left, xIntercept, right)) { - return fUsed = 0; - } - fT[1][0] = (xIntercept - left) / (right - left); - break; + // see if end points intersect the opposite line + double t; + if (checkEndPoint(left, y, line, &t, true)) { + insert(t, flipped, left, y); + } + if (left != right) { + if (checkEndPoint(right, y, line, &t, true)) { + insert(t, !flipped, right, y); } - case 2: - double a0 = line[0].fX; - double a1 = line[1].fX; - double b0 = flipped ? right : left; - double b1 = flipped ? left : right; - // FIXME: share common code below - double at0 = (a0 - b0) / (a0 - a1); - double at1 = (a0 - b1) / (a0 - a1); - if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { - return fUsed = 0; + for (int index = 0; index < 2; ++index) { + if (!checkEndPointH(line[index], left, right, y, flipped, &t)) { + continue; } - fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); - fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); - int bIn = (a0 - a1) * (b0 - b1) < 0; - fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 1.0), 0.0); - fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 1.0), 0.0); - bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; - SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); - return computePoints(line, 1 + second); + insert(index, t, line[index]); + } + } + if (used() > 0) { + SkASSERT(fUsed <= 2); + return used(); // coincident lines are returned here + } + int result = horizontal(line, y); + if (!result) { + return 0; + } + SkASSERT(result == 1); + double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); + if (!precisely_between(left, xIntercept, right)) { + return fUsed = 0; } + fT[1][0] = (xIntercept - left) / (right - left); if (flipped) { - // OPTIMIZATION: instead of swapping, pass original line, use [1].fX - [0].fX + // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX for (int index = 0; index < result; ++index) { fT[1][index] = 1 - fT[1][index]; } @@ -244,40 +241,49 @@ int SkIntersections::vertical(const SkDLine& line, double x) { return fUsed = 1; } +static bool checkEndPointV(const SkDPoint& end, double top, double bottom, + double x, bool flipped, double* tPtr) { + if (!between(top, end.fY, bottom) || !AlmostEqualUlps(x, end.fX)) { + return false; + } + double t = (end.fY - top) / (bottom - top); + SkASSERT(between(0, t, 1)); + *tPtr = flipped ? 1 - t : t; + return true; +} + int SkIntersections::vertical(const SkDLine& line, double top, double bottom, - double x, bool flipped) { - int result = vertical(line, x); - switch (result) { - case 0: - break; - case 1: { - double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); - if (!precisely_between(top, yIntercept, bottom)) { - return fUsed = 0; - } - fT[1][0] = (yIntercept - top) / (bottom - top); - break; + double x, bool flipped) { + // see if end points intersect the opposite line + double t; + if (checkEndPoint(x, top, line, &t, false)) { + insert(t, flipped, x, top); + } + if (top != bottom) { + if (checkEndPoint(x, bottom,line, &t, false)) { + insert(t, !flipped, x, bottom); } - case 2: - double a0 = line[0].fY; - double a1 = line[1].fY; - double b0 = flipped ? bottom : top; - double b1 = flipped ? top : bottom; - // FIXME: share common code above - double at0 = (a0 - b0) / (a0 - a1); - double at1 = (a0 - b1) / (a0 - a1); - if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { - return fUsed = 0; + for (int index = 0; index < 2; ++index) { + if (!checkEndPointV(line[index], top, bottom, x, flipped, &t)) { + continue; } - fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); - fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); - int bIn = (a0 - a1) * (b0 - b1) < 0; - fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 1.0), 0.0); - fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 1.0), 0.0); - bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; - SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); - return computePoints(line, 1 + second); + insert( index, t, line[index]); + } + } + if (used() > 0) { + SkASSERT(fUsed <= 2); + return used(); // coincident lines are returned here + } + int result = vertical(line, x); + if (!result) { + return 0; + } + SkASSERT(result == 1); + double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); + if (!precisely_between(top, yIntercept, bottom)) { + return fUsed = 0; } + fT[1][0] = (yIntercept - top) / (bottom - top); if (flipped) { // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY for (int index = 0; index < result; ++index) { diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index afaa1552e4..216e31f285 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -200,38 +200,57 @@ protected: // add endpoints first to get zero and one t values exactly void addEndPoints() { for (int qIndex = 0; qIndex < 3; qIndex += 2) { + bool foundEnd = false; for (int lIndex = 0; lIndex < 2; lIndex++) { if (quad[qIndex] == line[lIndex]) { intersections->insert(qIndex >> 1, lIndex, line[lIndex]); + foundEnd = true; } } + if (foundEnd) { + continue; + } + // See if the quad end touches the line. + double dist = line.isLeft(quad[qIndex]); // this distance isn't cartesian + SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line + // compute the ULPS of the larger of the x/y deltas + double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY)); + if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance? + continue; + } + double lineT = findLineT(qIndex >> 1); + if (!between(0, lineT, 1)) { + continue; + } + SkDPoint linePt = line.xyAtT(lineT); + if (linePt.approximatelyEqual(quad[qIndex])) { + intersections->insert(qIndex >> 1, lineT, quad[qIndex]); + } } } void addHorizontalEndPoints(double left, double right, double y) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - if (quad[qIndex].fY != y) { + if (!AlmostEqualUlps(quad[qIndex].fY, y)) { continue; } - if (quad[qIndex].fX == left) { - intersections->insert(qIndex >> 1, 0, quad[qIndex]); - } - if (quad[qIndex].fX == right) { - intersections->insert(qIndex >> 1, 1, quad[qIndex]); + double x = quad[qIndex].fX; + if (between(left, x, right)) { + double t = (x - left) / (right - left); + intersections->insert(qIndex >> 1, t, quad[qIndex]); } } } void addVerticalEndPoints(double top, double bottom, double x) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - if (quad[qIndex].fX != x) { + if (!AlmostEqualUlps(quad[qIndex].fX, x)) { continue; } - if (quad[qIndex].fY == top) { - intersections->insert(qIndex >> 1, 0, quad[qIndex]); - } - if (quad[qIndex].fY == bottom) { - intersections->insert(qIndex >> 1, 1, quad[qIndex]); + double y = quad[qIndex].fY; + if (between(top, y, bottom)) { + double t = (y - top) / (bottom - top); + intersections->insert(qIndex >> 1, t, quad[qIndex]); } } } @@ -240,10 +259,22 @@ protected: SkDPoint xy = quad.xyAtT(t); double dx = line[1].fX - line[0].fX; double dy = line[1].fY - line[0].fY; +#if 0 if (fabs(dx) > fabs(dy)) { return (xy.fX - line[0].fX) / dx; } return (xy.fY - line[0].fY) / dy; +#else + double dxT = (xy.fX - line[0].fX) / dx; + double dyT = (xy.fY - line[0].fY) / dy; + if (!between(FLT_EPSILON, dxT, 1 - FLT_EPSILON) && between(0, dyT, 1)) { + return dyT; + } + if (!between(FLT_EPSILON, dyT, 1 - FLT_EPSILON) && between(0, dxT, 1)) { + return dxT; + } + return fabs(dx) > fabs(dy) ? dxT : dyT; +#endif } static bool PinTs(double* quadT, double* lineT) { diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index ace8474d1d..af6cc080ef 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -56,10 +56,31 @@ void SkIntersections::flip() { void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, double e2, const SkDPoint& startPt, const SkDPoint& endPt) { - if (fSwap) { - remove(s2, e2, startPt, endPt); - } else { - remove(s1, e1, startPt, endPt); + SkASSERT(s1 < e1); + SkASSERT(s2 != e2); + if (coincidentUsed() != fUsed) { // if the curve is partially coincident, treat it as fully so + for (int index = fUsed - 1; index >= 0; --index) { + if (fIsCoincident[0] & (1 << index)) { + continue; + } + double nonCoinT = fT[0][index]; + if (!between(s1, nonCoinT, e1)) { + if (s1 > nonCoinT) { + s1 = nonCoinT; + } else { + e1 = nonCoinT; + } + } + nonCoinT = fT[1][index]; + if (!between(s2, nonCoinT, e2)) { + if ((s2 > nonCoinT) ^ (s2 > e2)) { + s2 = nonCoinT; + } else { + e2 = nonCoinT; + } + } + removeOne(index); + } } SkASSERT(coincidentUsed() == fUsed); SkASSERT((coincidentUsed() & 1) != 1); @@ -135,7 +156,7 @@ void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, doub insertCoincident(e1, e2, endPt); } -int SkIntersections::insert(double one, double two, const SkDPoint& pt) { +int SkIntersections::insert(double one, double two, double x, double y) { if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { // For now, don't allow a mix of coincident and non-coincident intersections return -1; @@ -152,7 +173,8 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) { fT[0][index] = one; fT[1][index] = two; - fPt[index] = pt; + fPt[index].fX = x; + fPt[index].fY = y; } return -1; } @@ -174,13 +196,18 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); } - fPt[index] = pt; + fPt[index].fX = x; + fPt[index].fY = y; fT[0][index] = one; fT[1][index] = two; ++fUsed; return index; } +int SkIntersections::insert(double one, double two, const SkDPoint& pt) { + return insert(one, two, pt.fX, pt.fY); +} + void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { int index = insertSwap(one, two, pt); int bit = 1 << index; @@ -209,6 +236,7 @@ void SkIntersections::quickRemoveOne(int index, int replace) { } } +#if 0 void SkIntersections::remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt) { for (int index = fUsed - 1; index >= 0; --index) { @@ -220,6 +248,7 @@ void SkIntersections::remove(double one, double two, const SkDPoint& startPt, } } } +#endif void SkIntersections::removeOne(int index) { int remaining = --fUsed - index; diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index 23470d7884..c0bb61fef0 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -96,6 +96,14 @@ public: } } + int insertSwap(double one, double two, double x, double y) { + if (fSwap) { + return insert(two, one, x, y); + } else { + return insert(one, two, x, y); + } + } + bool isCoincident(int index) { return (fIsCoincident[0] & 1 << index) != 0; } @@ -196,6 +204,7 @@ public: int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]); // FIXME : does not respect swap int insert(double one, double two, const SkDPoint& pt); + int insert(double one, double two, double x, double y); // start if index == 0 : end if index == 1 void insertCoincident(double one, double two, const SkDPoint& pt); void insertCoincidentPair(double s1, double e1, double s2, double e2, @@ -233,7 +242,7 @@ public: private: int computePoints(const SkDLine& line, int used); // used by addCoincident to remove ordinary intersections in range - void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt); + // void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt); SkDPoint fPt[9]; double fT[2][9]; diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index 0ac5a3da78..0dd0d65f79 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -22,7 +22,7 @@ static const int bugChar = strlen(funcName) + 1; #if DEBUG_ANGLE static bool CompareResult(SkString* bugOut, const char* append, bool compare) { - bugOut->appendf(append); + bugOut->appendf("%s", append); bugOut->writable_str()[bugChar] = "><"[compare]; SkDebugf("%s\n", bugOut->c_str()); return compare; @@ -141,7 +141,7 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r } } if (fSide * rh.fSide == 0) { - SkASSERT(fSide + rh.fSide != 0); + SkASSERT(fSide + rh.fSide != 0); // hitting this assert means coincidence was undetected return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide); } // at this point, the initial tangent line is nearly coincident diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp index d7f52752bf..5187b5f1e6 100644 --- a/src/pathops/SkOpEdgeBuilder.cpp +++ b/src/pathops/SkOpEdgeBuilder.cpp @@ -4,6 +4,7 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ +#include "SkGeometry.h" #include "SkOpEdgeBuilder.h" #include "SkReduceOrder.h" @@ -37,70 +38,114 @@ bool SkOpEdgeBuilder::finish() { if (fCurrentContour && !fCurrentContour->segments().count()) { fContours.pop_back(); } - // correct pointers in contours since fReducePts may have moved as it grew - int cIndex = 0; - int extraCount = fExtra.count(); - SkASSERT(extraCount == 0 || fExtra[0] == -1); - int eIndex = 0; - int rIndex = 0; - while (++eIndex < extraCount) { - int offset = fExtra[eIndex]; - if (offset < 0) { - ++cIndex; - continue; + return true; +} + +void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) { + if ((!AlmostEqualUlps(curveEnd.fX, curveStart.fX) + || !AlmostEqualUlps(curveEnd.fY, curveStart.fY))) { + fPathVerbs.push_back(SkPath::kLine_Verb); + fPathPts.push_back_n(1, &curveStart); + } else { + if (curveEnd.fX != curveStart.fX || curveEnd.fY != curveStart.fY) { + fPathPts[fPathPts.count() - 1] = curveStart; + } else { + fPathPts[fPathPts.count() - 1] = curveStart; } - fCurrentContour = &fContours[cIndex]; - rIndex += fCurrentContour->updateSegment(offset - 1, - &fReducePts[rIndex]); } - fExtra.reset(); // we're done with this - return true; + fPathVerbs.push_back(SkPath::kClose_Verb); } -// Note that copying the points here avoids copying the resulting path later. -// To allow Op() to take one of the input paths as an output parameter, either the source data -// must be copied (as implemented below) or the result must be copied. -// OPTIMIZATION: This copies both sets of input points every time. If the input data was read -// directly, the output path would only need to be copied if it was also one of the input paths. int SkOpEdgeBuilder::preFetch() { if (!fPath->isFinite()) { fUnparseable = true; return 0; } + SkAutoConicToQuads quadder; + const SkScalar quadderTol = SK_Scalar1 / 16; SkPath::RawIter iter(*fPath); + SkPoint curveStart; + SkPoint curve[4]; SkPoint pts[4]; SkPath::Verb verb; + bool lastCurve = false; do { verb = iter.next(pts); - fPathVerbs.push_back(verb); - if (verb == SkPath::kMove_Verb) { - fPathPts.push_back(pts[0]); - } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { - fPathPts.push_back_n(SkPathOpsVerbToPoints(verb), &pts[1]); + switch (verb) { + case SkPath::kMove_Verb: + if (!fAllowOpenContours && lastCurve) { + closeContour(curve[0], curveStart); + } + fPathVerbs.push_back(verb); + fPathPts.push_back(pts[0]); + curveStart = curve[0] = pts[0]; + lastCurve = false; + continue; + case SkPath::kLine_Verb: + if (AlmostEqualUlps(curve[0].fX, pts[1].fX) + && AlmostEqualUlps(curve[0].fY, pts[1].fY)) { + continue; // skip degenerate points + } + break; + case SkPath::kQuad_Verb: + curve[1] = pts[1]; + curve[2] = pts[2]; + verb = SkReduceOrder::Quad(curve, pts); + if (verb == SkPath::kMove_Verb) { + continue; // skip degenerate points + } + break; + case SkPath::kConic_Verb: { + const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(), + quadderTol); + const int nQuads = quadder.countQuads(); + for (int i = 0; i < nQuads; ++i) { + fPathVerbs.push_back(SkPath::kQuad_Verb); + } + fPathPts.push_back_n(nQuads * 2, quadPts); + curve[0] = quadPts[nQuads * 2 - 1]; + lastCurve = true; + } + continue; + case SkPath::kCubic_Verb: + curve[1] = pts[1]; + curve[2] = pts[2]; + curve[3] = pts[3]; + verb = SkReduceOrder::Cubic(curve, pts); + if (verb == SkPath::kMove_Verb) { + continue; // skip degenerate points + } + break; + case SkPath::kClose_Verb: + closeContour(curve[0], curveStart); + lastCurve = false; + continue; + case SkPath::kDone_Verb: + continue; } + fPathVerbs.push_back(verb); + int ptCount = SkPathOpsVerbToPoints(verb); + fPathPts.push_back_n(ptCount, &pts[1]); + curve[0] = pts[ptCount]; + lastCurve = true; } while (verb != SkPath::kDone_Verb); + if (!fAllowOpenContours && lastCurve) { + closeContour(curve[0], curveStart); + } + fPathVerbs.push_back(SkPath::kDone_Verb); return fPathVerbs.count() - 1; } bool SkOpEdgeBuilder::close() { - if (fFinalCurveStart && fFinalCurveEnd && *fFinalCurveStart != *fFinalCurveEnd) { - fReducePts.push_back(*fFinalCurveStart); - fReducePts.push_back(*fFinalCurveEnd); - const SkPoint* lineStart = fReducePts.end() - 2; - fExtra.push_back(fCurrentContour->addLine(lineStart)); - } complete(); return true; } bool SkOpEdgeBuilder::walk() { - SkPath::Verb reducedVerb; uint8_t* verbPtr = fPathVerbs.begin(); uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; - const SkPoint* pointsPtr = fPathPts.begin(); + const SkPoint* pointsPtr = fPathPts.begin() - 1; SkPath::Verb verb; - fFinalCurveStart = NULL; - fFinalCurveEnd = NULL; while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) { if (verbPtr == endOfFirstHalf) { fOperand = true; @@ -119,49 +164,18 @@ bool SkOpEdgeBuilder::walk() { fCurrentContour = fContours.push_back_n(1); fCurrentContour->setOperand(fOperand); fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask); - fExtra.push_back(-1); // start new contour } - fFinalCurveEnd = pointsPtr++; + pointsPtr += 1; continue; - case SkPath::kLine_Verb: { - const SkPoint& lineEnd = pointsPtr[0]; - const SkPoint& lineStart = pointsPtr[-1]; - // skip degenerate points - if (lineStart.fX != lineEnd.fX || lineStart.fY != lineEnd.fY) { - fCurrentContour->addLine(&lineStart); - } - } break; - case SkPath::kQuad_Verb: { - const SkPoint* quadStart = &pointsPtr[-1]; - reducedVerb = SkReduceOrder::Quad(quadStart, &fReducePts); - if (reducedVerb == 0) { - break; // skip degenerate points - } - if (reducedVerb == SkPath::kLine_Verb) { - const SkPoint* lineStart = fReducePts.end() - 2; - fExtra.push_back(fCurrentContour->addLine(lineStart)); - break; - } - fCurrentContour->addQuad(quadStart); - } break; - case SkPath::kCubic_Verb: { - const SkPoint* cubicStart = &pointsPtr[-1]; - reducedVerb = SkReduceOrder::Cubic(cubicStart, &fReducePts); - if (reducedVerb == 0) { - break; // skip degenerate points - } - if (reducedVerb == SkPath::kLine_Verb) { - const SkPoint* lineStart = fReducePts.end() - 2; - fExtra.push_back(fCurrentContour->addLine(lineStart)); - break; - } - if (reducedVerb == SkPath::kQuad_Verb) { - const SkPoint* quadStart = fReducePts.end() - 3; - fExtra.push_back(fCurrentContour->addQuad(quadStart)); - break; - } - fCurrentContour->addCubic(cubicStart); - } break; + case SkPath::kLine_Verb: + fCurrentContour->addLine(pointsPtr); + break; + case SkPath::kQuad_Verb: + fCurrentContour->addQuad(pointsPtr); + break; + case SkPath::kCubic_Verb: + fCurrentContour->addCubic(pointsPtr); + break; case SkPath::kClose_Verb: SkASSERT(fCurrentContour); if (!close()) { @@ -172,7 +186,6 @@ bool SkOpEdgeBuilder::walk() { SkDEBUGFAIL("bad verb"); return false; } - fFinalCurveStart = &pointsPtr[SkPathOpsVerbToPoints(verb) - 1]; pointsPtr += SkPathOpsVerbToPoints(verb); SkASSERT(fCurrentContour); } diff --git a/src/pathops/SkOpEdgeBuilder.h b/src/pathops/SkOpEdgeBuilder.h index 2a2bf034e4..df0795b0c8 100644 --- a/src/pathops/SkOpEdgeBuilder.h +++ b/src/pathops/SkOpEdgeBuilder.h @@ -43,6 +43,7 @@ public: void init(); private: + void closeContour(const SkPoint& curveEnd, const SkPoint& curveStart); bool close(); int preFetch(); bool walk(); @@ -52,11 +53,7 @@ private: SkTArray<uint8_t, true> fPathVerbs; SkOpContour* fCurrentContour; SkTArray<SkOpContour>& fContours; - SkTArray<SkPoint, true> fReducePts; // segments created on the fly - SkTArray<int, true> fExtra; // -1 marks new contour, > 0 offsets into contour SkPathOpsMask fXorMask[2]; - const SkPoint* fFinalCurveStart; - const SkPoint* fFinalCurveEnd; int fSecondHalf; bool fOperand; bool fAllowOpenContours; diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 08f4f7eace..54e44904f4 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -861,7 +861,7 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ... bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); #if DEBUG_SORT - sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable); #endif if (!sortable) { return SK_MinS32; @@ -896,7 +896,7 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { winding += spanWinding; } #if DEBUG_SORT - base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding); + base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding, sortable); #endif int nextIndex = firstIndex + 1; int lastIndex = firstIndex != 0 ? firstIndex : angleCount; @@ -1134,6 +1134,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart while (precisely_zero(startT - other->fTs[*nextEnd].fT)); SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count()); if (other->isTiny(SkMin32(*nextStart, *nextEnd))) { + *unsortable = true; return NULL; } return other; @@ -1150,7 +1151,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); #if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, firstIndex); + debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); #endif if (!sortable) { *unsortable = true; @@ -1272,7 +1273,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); #if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, firstIndex); + debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); #endif if (!sortable) { *unsortable = true; @@ -1400,7 +1401,8 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort if (!sortable) { *unsortable = true; #if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0); + debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0, + sortable); #endif return NULL; } @@ -1408,7 +1410,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); #if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0); + debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable); #endif SkASSERT(sorted[firstIndex]->segment() == this); int nextIndex = firstIndex + 1; @@ -1654,7 +1656,7 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort } SkASSERT(first < SK_MaxS32); #if DEBUG_SORT // || DEBUG_SWAP_TOP - sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0); + sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable); #endif if (onlySortable && !sortable) { *unsortable = true; @@ -2565,6 +2567,9 @@ int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx #endif return SK_MinS32; } + if (windVal < 0) { // reverse sign if opp contour traveled in reverse + *dx = -*dx; + } if (winding * *dx > 0) { // if same signs, result is negative winding += *dx > 0 ? -windVal : windVal; } @@ -2769,12 +2774,12 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int #if DEBUG_SORT || DEBUG_SWAP_TOP void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, const int contourWinding, - const int oppContourWinding) const { + const int oppContourWinding, bool sortable) const { if (--gDebugSortCount < 0) { return; } SkASSERT(angles[first]->segment() == this); - SkASSERT(angles.count() > 1); + SkASSERT(!sortable || angles.count() > 1); int lastSum = contourWinding; int oppLastSum = oppContourWinding; const SkOpAngle* firstAngle = angles[first]; @@ -2878,12 +2883,12 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true } void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, - int first) { + int first, bool sortable) { const SkOpAngle* firstAngle = angles[first]; const SkOpSegment* segment = firstAngle->segment(); int winding = segment->updateWinding(firstAngle); int oppWinding = segment->updateOppWinding(firstAngle); - debugShowSort(fun, angles, first, winding, oppWinding); + debugShowSort(fun, angles, first, winding, oppWinding, sortable); } #endif diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 94efcb53fe..3cbd29e77e 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -318,8 +318,9 @@ public: #endif #if DEBUG_SORT || DEBUG_SWAP_TOP void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, - const int contourWinding, const int oppContourWinding) const; - void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first); + const int contourWinding, const int oppContourWinding, bool sortable) const; + void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, + bool sortable); #endif #if DEBUG_CONCIDENT void debugShowTs() const; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 0fa5ce0c92..5a30c3a98e 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -138,7 +138,7 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) SkOpSegment::kMayBeUnordered_SortAngleKind); int angleCount = sorted.count(); #if DEBUG_SORT - sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable); #endif if (!sortable) { continue; @@ -162,7 +162,7 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) winding += spanWinding; } #if DEBUG_SORT - segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0); + segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable); #endif // we care about first sign and whether wind sum indicates this // edge is inside or outside. Maybe need to pass span winding diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 6c8ca954f1..1071b52050 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -61,68 +61,29 @@ int gDebugSortCount; const char* kPathOpStr[] = {"diff", "sect", "union", "xor"}; #endif -#if DEBUG_SHOW_PATH -static void showPathContours(SkPath::Iter& iter, const char* pathName) { - uint8_t verb; - SkPoint pts[4]; - while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { - switch (verb) { - case SkPath::kMove_Verb: - SkDebugf(" %s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY); - continue; - case SkPath::kLine_Verb: - SkDebugf(" %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY); - break; - case SkPath::kQuad_Verb: - SkDebugf(" %s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName, - pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); - break; - case SkPath::kCubic_Verb: - SkDebugf(" %s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", - pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); - break; - case SkPath::kClose_Verb: - SkDebugf(" %s.close();\n", pathName); - break; - default: - SkDEBUGFAIL("bad verb"); - return; - } - } -} - -static const char* gFillTypeStr[] = { - "kWinding_FillType", - "kEvenOdd_FillType", - "kInverseWinding_FillType", - "kInverseEvenOdd_FillType" -}; - - -void ShowFunctionHeader() { - SkDebugf("\nstatic void test#(skiatest::Reporter* reporter) {\n"); +#if DEBUG_SHOW_TEST_NAME +void* PathOpsDebugCreateNameStr() { + return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH); } -void ShowPath(const SkPath& path, const char* pathName) { - SkPath::Iter iter(path, true); - SkPath::FillType fillType = path.getFillType(); - SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType); - SkDebugf(" SkPath %s;\n", pathName); - SkDebugf(" %s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]); - iter.setPath(path, true); - showPathContours(iter, pathName); +void PathOpsDebugDeleteNameStr(void* v) { + SkDELETE_ARRAY(reinterpret_cast<char* >(v)); } -static const char* gOpStrs[] = { - "kDifference_PathOp", - "kIntersect_PathOp", - "kUnion_PathOp", - "kXor_PathOp", - "kReverseDifference_PathOp", -}; - -void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo) { - SkDebugf(" testPathOp(reporter, %s, %s, %s);\n", pathOne, pathTwo, gOpStrs[op]); - SkDebugf("}\n"); +void DebugBumpTestName(char* test) { + char* num = test + strlen(test); + while (num[-1] >= '0' && num[-1] <= '9') { + --num; + } + if (num[0] == '\0') { + return; + } + int dec = atoi(num); + if (dec == 0) { + return; + } + ++dec; + SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec); } #endif + diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index cc1b8ead95..5484147c3a 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -56,7 +56,6 @@ extern int gDebugMaxWindValue; #define DEBUG_FLOW 0 #define DEBUG_MARK_DONE 0 #define DEBUG_PATH_CONSTRUCTION 0 -#define DEBUG_SHOW_PATH 0 #define DEBUG_SHOW_TEST_NAME 0 #define DEBUG_SHOW_TEST_PROGRESS 0 #define DEBUG_SHOW_WINDING 0 @@ -86,7 +85,6 @@ extern int gDebugMaxWindValue; #define DEBUG_FLOW 1 #define DEBUG_MARK_DONE 1 #define DEBUG_PATH_CONSTRUCTION 1 -#define DEBUG_SHOW_PATH 0 #define DEBUG_SHOW_TEST_NAME 1 #define DEBUG_SHOW_TEST_PROGRESS 1 #define DEBUG_SHOW_WINDING 0 @@ -141,14 +139,20 @@ void winding_printf(int winding); extern const char* kPathOpStr[]; #endif -#ifndef DEBUG_TEST -#define DEBUG_TEST 0 +#if DEBUG_SHOW_TEST_NAME +#include "SkTLS.h" + +extern void* PathOpsDebugCreateNameStr(); +extern void PathOpsDebugDeleteNameStr(void* v); +#define DEBUG_FILENAME_STRING_LENGTH 64 +#define DEBUG_FILENAME_STRING \ + (reinterpret_cast<char* >(SkTLS::Get(PathOpsDebugCreateNameStr, PathOpsDebugDeleteNameStr))) +extern void DebugBumpTestName(char* ); +extern void DebugShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name); #endif -#if DEBUG_SHOW_PATH -void ShowFunctionHeader(); -void ShowPath(const SkPath& path, const char* pathName); -void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo); +#ifndef DEBUG_TEST +#define DEBUG_TEST 0 #endif #endif diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 7e1c772893..0df4859cdf 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -41,7 +41,7 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int SkOpSegment::kMayBeUnordered_SortAngleKind); int angleCount = sorted.count(); #if DEBUG_SORT - sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0); + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable); #endif if (!sortable) { continue; @@ -54,7 +54,7 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int segment = angle->segment(); } while (segment->windSum(angle) == SK_MinS32); #if DEBUG_SORT - segment->debugShowSort(__FUNCTION__, sorted, firstIndex); + segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); #endif int sumMiWinding = segment->updateWindingReverse(angle); int sumSuWinding = segment->updateOppWindingReverse(angle); @@ -232,11 +232,12 @@ static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { }; bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { -#if DEBUG_SHOW_PATH - ShowFunctionHeader(); - ShowPath(one, "path"); - ShowPath(two, "pathB"); - ShowOp(op, "path", "pathB"); +#if DEBUG_SHOW_TEST_NAME + char* debugName = DEBUG_FILENAME_STRING; + if (debugName && debugName[0]) { + DebugBumpTestName(debugName); + DebugShowPath(one, two, op, debugName); + } #endif op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()] diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index 534154f199..ad959b6669 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -111,14 +111,8 @@ struct SkDPoint { } bool approximatelyEqual(const SkPoint& a) const { - double denom = SkTMax(fabs(fX), SkTMax(fabs(fY), - SkScalarToDouble(SkTMax(fabsf(a.fX), fabsf(a.fY))))); - if (denom == 0) { - return true; - } - double inv = 1 / denom; - return approximately_equal_double(fX * inv, a.fX * inv) - && approximately_equal_double(fY * inv, a.fY * inv); + return AlmostEqualUlps(SkDoubleToScalar(fX), a.fX) + && AlmostEqualUlps(SkDoubleToScalar(fY), a.fY); } bool approximatelyEqualHalf(const SkDPoint& a) const { diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index b071ca5371..999e1b215d 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -7,11 +7,11 @@ #include "SkFloatBits.h" #include "SkPathOpsTypes.h" -const int UlpsEpsilon = 16; + // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ // FIXME: move to SkFloatBits.h -bool AlmostEqualUlps(float A, float B) { +static bool equal_ulps(float A, float B, int epsilon) { SkFloatIntUnion floatIntA, floatIntB; floatIntA.fFloat = A; floatIntB.fFloat = B; @@ -23,7 +23,17 @@ bool AlmostEqualUlps(float A, float B) { } // Find the difference in ULPs. int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); - return ulpsDiff <= UlpsEpsilon; + return ulpsDiff <= epsilon; +} + +bool AlmostEqualUlps(float A, float B) { + const int UlpsEpsilon = 16; + return equal_ulps(A, B, UlpsEpsilon); +} + +bool RoughlyEqualUlps(float A, float B) { + const int UlpsEpsilon = 256; + return equal_ulps(A, B, UlpsEpsilon); } // cube root approximation using bit hack for 64-bit float diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 6ead79455c..20641d3345 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -28,6 +28,11 @@ inline bool AlmostEqualUlps(double A, double B) { return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B)); } +bool RoughlyEqualUlps(float A, float B); +inline bool RoughlyEqualUlps(double A, double B) { + return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B)); +} + // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23) // DBL_EPSILON == 2.22045e-16 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; diff --git a/src/pathops/SkReduceOrder.cpp b/src/pathops/SkReduceOrder.cpp index ab85f3dd3e..3dfdc9daee 100644 --- a/src/pathops/SkReduceOrder.cpp +++ b/src/pathops/SkReduceOrder.cpp @@ -425,31 +425,27 @@ int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics, return 4; } -SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkTArray<SkPoint, true>* reducePts) { +SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkPoint* reducePts) { SkDQuad quad; quad.set(a); SkReduceOrder reducer; int order = reducer.reduce(quad, kFill_Style); if (order == 2) { // quad became line for (int index = 0; index < order; ++index) { - SkPoint& pt = reducePts->push_back(); - pt.fX = SkDoubleToScalar(reducer.fLine[index].fX); - pt.fY = SkDoubleToScalar(reducer.fLine[index].fY); + *reducePts++ = reducer.fLine[index].asSkPoint(); } } return SkPathOpsPointsToVerb(order - 1); } -SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkTArray<SkPoint, true>* reducePts) { +SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) { SkDCubic cubic; cubic.set(a); SkReduceOrder reducer; int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style); if (order == 2 || order == 3) { // cubic became line or quad for (int index = 0; index < order; ++index) { - SkPoint& pt = reducePts->push_back(); - pt.fX = SkDoubleToScalar(reducer.fQuad[index].fX); - pt.fY = SkDoubleToScalar(reducer.fQuad[index].fY); + *reducePts++ = reducer.fQuad[index].asSkPoint(); } } return SkPathOpsPointsToVerb(order - 1); diff --git a/src/pathops/SkReduceOrder.h b/src/pathops/SkReduceOrder.h index 82f8ffb143..c167951f8b 100644 --- a/src/pathops/SkReduceOrder.h +++ b/src/pathops/SkReduceOrder.h @@ -27,8 +27,8 @@ union SkReduceOrder { int reduce(const SkDLine& line); int reduce(const SkDQuad& quad, Style); - static SkPath::Verb Cubic(const SkPoint pts[4], SkTArray<SkPoint, true>* reducePts); - static SkPath::Verb Quad(const SkPoint pts[3], SkTArray<SkPoint, true>* reducePts); + static SkPath::Verb Cubic(const SkPoint pts[4], SkPoint* reducePts); + static SkPath::Verb Quad(const SkPoint pts[3], SkPoint* reducePts); SkDLine fLine; SkDQuad fQuad; diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index 1986a506bd..34a77b1fd9 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -28,6 +28,7 @@ static const SkPoint cubics[][4] = { /* 15 */ {{808,11417}, {808,11418.1044921875f}, {807.10455322265625f,11419}, {806,11419}}, /* 16 */ {{132,11419}, {130.89543151855469f,11419}, {130,11418.1044921875f}, {130,11417}}, /* 17 */ {{130.04275512695312f,11417.4130859375f}, {130.23312377929687f,11418.3193359375f}, {131.03707885742187f,11419}, {132,11419}}, +/* 18 */ {{1006.6951293945312f,291}, {1023.263671875f,291}, {1033.8402099609375f,304.43145751953125f}, {1030.318359375f,321}}, }; static const SkPoint quads[][3] = { @@ -49,6 +50,7 @@ static const SkPoint lines[][2] = { /* 8 */ {{4,3}, {0,1}}, /* 9 */ {{3,2}, {1,2}}, /* 10 */ {{6,4}, {3,4}}, +/* 11 */ {{979.30487060546875f,561}, {1036.695068359375f,291}}, }; struct SortSet { @@ -192,6 +194,13 @@ static const SortSet set16[] = { {cubics[17], 4, 0.0682619216, 1, {132,11419}}, }; +static const SortSet set17[] = { + {lines[11], 2, 0.888889581, 1, {0, 0}}, + {cubics[18], 4, 0.999996241, 0, {0, 0}}, + {lines[11], 2, 0.888889581, 0, {0, 0}}, + {cubics[18], 4, 0.999996241, 1, {0, 0}}, +}; + struct SortSetTests { const char* name; const SortSet* set; @@ -202,6 +211,7 @@ struct SortSetTests { #define TEST_ENTRY(name) #name, name, SK_ARRAY_COUNT(name) static const SortSetTests tests[] = { + { TEST_ENTRY(set17), {0, 0}}, { TEST_ENTRY(set16), {130.090179f,11417.5957f} }, // { TEST_ENTRY(set15), {0, 0}}, { TEST_ENTRY(set14), {0, 0}}, @@ -294,90 +304,100 @@ static void setup(const SortSet* set, const size_t idx, } while (++tIndex); } -static void PathOpsAngleTest(skiatest::Reporter* reporter) { - for (size_t index = 0; index < SK_ARRAY_COUNT(tests); ++index) { - const SortSetTests& test = tests[index]; - SkTDArray<SkOpAngle> angles; - bool unsortable = false; - bool unorderable = false; - SkTArray<SkOpSegment> segs; - for (size_t idx = 0; idx < test.count; ++idx) { - int ts[2]; - const SortSet* set = test.set; - SkOpSegment& seg = segs.push_back(); - setup(set, idx, &seg, ts, test.startPt); - SkOpAngle* angle = angles.append(); - angle->set(&seg, ts[0], ts[1]); +static void testOne(skiatest::Reporter* reporter, const SortSetTests& test) { + SkTDArray<SkOpAngle> angles; + bool unsortable = false; + bool unorderable = false; + SkTArray<SkOpSegment> segs; + for (size_t idx = 0; idx < test.count; ++idx) { + int ts[2]; + const SortSet* set = test.set; + SkOpSegment& seg = segs.push_back(); + setup(set, idx, &seg, ts, test.startPt); + SkOpAngle* angle = angles.append(); + angle->set(&seg, ts[0], ts[1]); #if DEBUG_ANGLE - angle->setID(idx); + angle->setID(idx); #endif - if (angle->unsortable()) { + if (angle->unsortable()) { #if DEBUG_ANGLE - SkDebugf("%s test[%s]: angle[%d] unsortable\n", __FUNCTION__, test.name, idx); + SkDebugf("%s test[%s]: angle[%d] unsortable\n", __FUNCTION__, test.name, idx); #endif - unsortable = true; - } - if (angle->unorderable()) { + unsortable = true; + } + if (angle->unorderable()) { #if DEBUG_ANGLE - SkDebugf("%s test[%s]: angle[%d] unorderable\n", __FUNCTION__, test.name, idx); + SkDebugf("%s test[%s]: angle[%d] unorderable\n", __FUNCTION__, test.name, idx); #endif - unorderable = true; - } - reporter->bumpTestCount(); - } - if (unsortable || unorderable) { - continue; + unorderable = true; } + reporter->bumpTestCount(); + } + if (unsortable || unorderable) { + return; + } #if DEBUG_ANGLE - SkDebugf("%s test[%s]\n", __FUNCTION__, test.name); + SkDebugf("%s test[%s]\n", __FUNCTION__, test.name); #endif - for (size_t idxL = 0; idxL < test.count; ++idxL) { - const SkOpAngle& first = angles[idxL]; - for (size_t idxG = 0; idxG < test.count; ++idxG) { - if (idxL == idxG) { - continue; + for (size_t idxL = 0; idxL < test.count; ++idxL) { + const SkOpAngle& first = angles[idxL]; + for (size_t idxG = 0; idxG < test.count; ++idxG) { + if (idxL == idxG) { + continue; + } + const SkOpAngle& second = angles[idxG]; + bool compare = first < second; + if (idxL < idxG) { + if (!compare) { + SkDebugf("%s test[%s]: first[%d] > second[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = first < second; + } + REPORTER_ASSERT(reporter, compare); + } else { + SkASSERT(idxL > idxG); + if (compare) { + SkDebugf("%s test[%s]: first[%d] < second[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = first < second; } - const SkOpAngle& second = angles[idxG]; - bool compare = first < second; - if (idxL < idxG) { - if (!compare) { - SkDebugf("%s test[%s]: first[%d] > second[%d]\n", __FUNCTION__, - test.name, idxL, idxG); - compare = first < second; - } - REPORTER_ASSERT(reporter, compare); - } else { - SkASSERT(idxL > idxG); - if (compare) { - SkDebugf("%s test[%s]: first[%d] < second[%d]\n", __FUNCTION__, - test.name, idxL, idxG); - compare = first < second; - } - REPORTER_ASSERT(reporter, !compare); + REPORTER_ASSERT(reporter, !compare); + } + compare = second < first; + if (idxL < idxG) { + if (compare) { + SkDebugf("%s test[%s]: second[%d] < first[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = second < first; } - compare = second < first; - if (idxL < idxG) { - if (compare) { - SkDebugf("%s test[%s]: second[%d] < first[%d]\n", __FUNCTION__, - test.name, idxL, idxG); - compare = second < first; - } - REPORTER_ASSERT(reporter, !compare); - } else { - SkASSERT(idxL > idxG); - if (!compare) { - SkDebugf("%s test[%s]: second[%d] > first[%d]\n", __FUNCTION__, - test.name, idxL, idxG); - compare = second < first; - } - REPORTER_ASSERT(reporter, compare); + REPORTER_ASSERT(reporter, !compare); + } else { + SkASSERT(idxL > idxG); + if (!compare) { + SkDebugf("%s test[%s]: second[%d] > first[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = second < first; } + REPORTER_ASSERT(reporter, compare); } } + } +} + +static void PathOpsAngleTest(skiatest::Reporter* reporter) { + for (size_t index = 0; index < SK_ARRAY_COUNT(tests); ++index) { + const SortSetTests& test = tests[index]; + testOne(reporter, test); reporter->bumpTestCount(); } } +static void PathOpsAngleTestOne(skiatest::Reporter* reporter) { + size_t index = 0; + const SortSetTests& test = tests[index]; + testOne(reporter, test); +} + #if 0 static int find_slop(double x, double y, double rx, double ry) { int slopBits = 0; @@ -446,4 +466,6 @@ static void PathOpsAngleFindSlop(skiatest::Reporter* reporter) { #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsAngleTest) +DEFINE_TESTCLASS_SHORT(PathOpsAngleTestOne) + // DEFINE_TESTCLASS_SHORT(PathOpsAngleFindSlop) diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index 7f5f4cd040..e00ba1674c 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -490,8 +490,8 @@ static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, max[idx2], cubic.xyAtT(max[idx2]).fX, cubic.xyAtT(max[idx2]).fY); } - SkTDArray<double> ts1; - SkTDArray<SkDQuad> quads1; + SkTArray<double, true> ts1; + SkTArray<SkDQuad, true> quads1; cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); for (idx2 = 0; idx2 < ts1.count(); ++idx2) { SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp index 7af7b26e45..c5f05f6f6d 100644 --- a/tests/PathOpsCubicLineIntersectionTest.cpp +++ b/tests/PathOpsCubicLineIntersectionTest.cpp @@ -14,47 +14,85 @@ static struct lineCubic { SkDCubic cubic; SkDLine line; } lineCubicTests[] = { + {{{{1006.6951293945312,291}, {1023.263671875,291}, {1033.8402099609375,304.43145751953125}, + {1030.318359375,321}}}, + {{{979.30487060546875,561}, {1036.695068359375,291}}}}, + {{{{259.30487060546875,561}, {242.73631286621094,561}, {232.15980529785156,547.56854248046875}, + {235.68154907226562,531}}}, + {{{286.69512939453125,291}, {229.30485534667969,561}}}}, {{{{1, 2}, {2, 6}, {2, 0}, {1, 0}}}, {{{1, 0}, {1, 2}}}}, {{{{0, 0}, {0, 1}, {0, 1}, {1, 1}}}, {{{0, 1}, {1, 0}}}}, }; static const size_t lineCubicTests_count = SK_ARRAY_COUNT(lineCubicTests); +static void testOne(skiatest::Reporter* reporter, int iIndex) { + const SkDCubic& cubic = lineCubicTests[iIndex].cubic; + const SkDLine& line = lineCubicTests[iIndex].line; + SkReduceOrder reduce1; + SkReduceOrder reduce2; + int order1 = reduce1.reduce(cubic, SkReduceOrder::kNo_Quadratics, + SkReduceOrder::kFill_Style); + int order2 = reduce2.reduce(line); + if (order1 < 4) { + SkDebugf("[%d] cubic order=%d\n", iIndex, order1); + REPORTER_ASSERT(reporter, 0); + } + if (order2 < 2) { + SkDebugf("[%d] line order=%d\n", iIndex, order2); + REPORTER_ASSERT(reporter, 0); + } + if (order1 == 4 && order2 == 2) { + SkIntersections i; + int roots = i.intersect(cubic, line); + for (int pt = 0; pt < roots; ++pt) { + double tt1 = i[0][pt]; + SkDPoint xy1 = cubic.xyAtT(tt1); + double tt2 = i[1][pt]; + SkDPoint xy2 = line.xyAtT(tt2); + if (!xy1.approximatelyEqual(xy2)) { + SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", + __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); + } + REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); + } + } +} + static void PathOpsCubicLineIntersectionTest(skiatest::Reporter* reporter) { for (size_t index = 0; index < lineCubicTests_count; ++index) { int iIndex = static_cast<int>(index); - const SkDCubic& cubic = lineCubicTests[index].cubic; - const SkDLine& line = lineCubicTests[index].line; - SkReduceOrder reduce1; - SkReduceOrder reduce2; - int order1 = reduce1.reduce(cubic, SkReduceOrder::kNo_Quadratics, - SkReduceOrder::kFill_Style); - int order2 = reduce2.reduce(line); - if (order1 < 4) { - SkDebugf("[%d] cubic order=%d\n", iIndex, order1); - REPORTER_ASSERT(reporter, 0); - } - if (order2 < 2) { - SkDebugf("[%d] line order=%d\n", iIndex, order2); - REPORTER_ASSERT(reporter, 0); - } - if (order1 == 4 && order2 == 2) { - SkIntersections i; - int roots = i.intersect(cubic, line); - for (int pt = 0; pt < roots; ++pt) { - double tt1 = i[0][pt]; - SkDPoint xy1 = cubic.xyAtT(tt1); - double tt2 = i[1][pt]; - SkDPoint xy2 = line.xyAtT(tt2); - if (!xy1.approximatelyEqual(xy2)) { - SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", - __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); - } - REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); - } - } + testOne(reporter, iIndex); + reporter->bumpTestCount(); } } +static void PathOpsCubicLineIntersectionTestOne(skiatest::Reporter* reporter) { + int iIndex = 0; + testOne(reporter, iIndex); + const SkDCubic& cubic = lineCubicTests[iIndex].cubic; + const SkDLine& line = lineCubicTests[iIndex].line; + SkIntersections i; + i.intersect(cubic, line); + SkASSERT(i.used() == 1); +#if ONE_OFF_DEBUG + double cubicT = i[0][0]; + SkDPoint prev = cubic.xyAtT(cubicT * 2 - 1); + SkDPoint sect = cubic.xyAtT(cubicT); + double left[3] = { line.isLeft(prev), line.isLeft(sect), line.isLeft(cubic[3]) }; + SkDebugf("cubic=(%1.9g, %1.9g, %1.9g)\n", left[0], left[1], left[2]); + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", prev.fX, prev.fY, sect.fX, sect.fY); + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", sect.fX, sect.fY, cubic[3].fX, cubic[3].fY); + SkDPoint prevL = line.xyAtT(i[1][0] - 0.0000007); + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", prevL.fX, prevL.fY, i.pt(0).fX, i.pt(0).fY); + SkDPoint nextL = line.xyAtT(i[1][0] + 0.0000007); + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", i.pt(0).fX, i.pt(0).fY, nextL.fX, nextL.fY); + SkDebugf("prevD=%1.9g dist=%1.9g nextD=%1.9g\n", prev.distance(nextL), + sect.distance(i.pt(0)), cubic[3].distance(prevL)); +#endif +} + #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionTest) + +DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionTestOne) diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index a9ca58b1e9..7a7dcb3759 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -45,27 +45,34 @@ static bool gComparePaths = true; static bool gComparePathsAssert = true; static bool gPathStrAssert = true; -static void showPathContours(SkPath::Iter& iter, const char* suffix) { +static const char* gFillTypeStr[] = { + "kWinding_FillType", + "kEvenOdd_FillType", + "kInverseWinding_FillType", + "kInverseEvenOdd_FillType" +}; + +static void showPathContours(SkPath::RawIter& iter, const char* pathName) { uint8_t verb; SkPoint pts[4]; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: - SkDebugf(" path%s.moveTo(%1.9g,%1.9g);\n", suffix, pts[0].fX, pts[0].fY); + SkDebugf(" %s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY); continue; case SkPath::kLine_Verb: - SkDebugf(" path%s.lineTo(%1.9g,%1.9g);\n", suffix, pts[1].fX, pts[1].fY); + SkDebugf(" %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY); break; case SkPath::kQuad_Verb: - SkDebugf(" path%s.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", suffix, + SkDebugf(" %s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); break; case SkPath::kCubic_Verb: - SkDebugf(" path%s.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", suffix, - pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); + SkDebugf(" %s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", + pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); break; case SkPath::kClose_Verb: - SkDebugf(" path%s.close();\n", suffix); + SkDebugf(" %s.close();\n", pathName); break; default: SkDEBUGFAIL("bad verb"); @@ -74,15 +81,8 @@ static void showPathContours(SkPath::Iter& iter, const char* suffix) { } } -static const char* fillTypeStr[] = { - "kWinding_FillType", - "kEvenOdd_FillType", - "kInverseWinding_FillType", - "kInverseEvenOdd_FillType" -}; - -static void showPath(const SkPath& path, const char* suffix) { - SkPath::Iter iter(path, true); +static void showPath(const SkPath& path, const char* pathName, bool includeDeclaration) { + SkPath::RawIter iter(path); #define SUPPORT_RECT_CONTOUR_DETECTION 0 #if SUPPORT_RECT_CONTOUR_DETECTION int rectCount = path.isRectContours() ? path.rectContours(NULL, NULL) : 0; @@ -103,14 +103,17 @@ static void showPath(const SkPath& path, const char* suffix) { #endif SkPath::FillType fillType = path.getFillType(); SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType); - SkDebugf(" path%s.setFillType(SkPath::%s);\n", suffix, fillTypeStr[fillType]); - iter.setPath(path, true); - showPathContours(iter, suffix); + if (includeDeclaration) { + SkDebugf(" SkPath %s;\n", pathName); + } + SkDebugf(" %s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]); + iter.setPath(path); + showPathContours(iter, pathName); } #if DEBUG_SHOW_TEST_NAME static void showPathData(const SkPath& path) { - SkPath::Iter iter(path, true); + SkPath::RawIter iter(path); uint8_t verb; SkPoint pts[4]; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { @@ -162,16 +165,26 @@ void showOp(const SkPathOp op) { } } -#if 0 -static void showPath(const SkPath& path, const char* str, const SkMatrix& scale) { - SkPath scaled; - SkMatrix inverse; - bool success = scale.invert(&inverse); - if (!success) { - SkASSERT(0); +#if DEBUG_SHOW_TEST_NAME + +void ShowFunctionHeader(const char* functionName) { + SkDebugf("\nstatic void %s(skiatest::Reporter* reporter) {\n", functionName); + if (strcmp("skphealth_com76", functionName) == 0) { + SkDebugf("found it\n"); } - path.transform(inverse, &scaled); - showPath(scaled, str); +} + +static const char* gOpStrs[] = { + "kDifference_PathOp", + "kIntersect_PathOp", + "kUnion_PathOp", + "kXor_PathOp", + "kReverseDifference_PathOp", +}; + +void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo) { + SkDebugf(" testPathOp(reporter, %s, %s, %s);\n", pathOne, pathTwo, gOpStrs[op]); + SkDebugf("}\n"); } #endif @@ -325,8 +338,7 @@ bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths) { static void showSimplifiedPath(const SkPath& one, const SkPath& two, const SkPath& scaledOne, const SkPath& scaledTwo) { - showPath(one, ""); - // showPath(two, "simplified:"); + showPath(one, "path", false); drawAsciiPaths(scaledOne, scaledTwo, true); } @@ -356,13 +368,10 @@ static void showPathOpPath(const SkPath& one, const SkPath& two, const SkPath& a SkASSERT((unsigned) shapeOp < SK_ARRAY_COUNT(opStrs)); SkDebugf("static void xOp#%s(skiatest::Reporter* reporter) {\n", opSuffixes[shapeOp]); SkDebugf(" SkPath path, pathB;\n"); - showPath(a, ""); - showPath(b, "B"); + showPath(a, "path", false); + showPath(b, "pathB", false); SkDebugf(" testPathOp(reporter, path, pathB, %s);\n", opStrs[shapeOp]); SkDebugf("}\n"); - // the region often isn't very helpful since it approximates curves with a lot of line-tos - // if (0) showPath(scaledOne, "region:", scale); - // showPath(two, "op result:"); drawAsciiPaths(scaledOne, scaledTwo, true); } @@ -450,7 +459,7 @@ bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& st SkPath::FillType fillType = useXor ? SkPath::kEvenOdd_FillType : SkPath::kWinding_FillType; path.setFillType(fillType); if (gShowPath) { - showPath(path, ""); + showPath(path, "path", false); } if (!Simplify(path, &out)) { SkDebugf("%s did not expect failure\n", __FUNCTION__); @@ -499,12 +508,25 @@ bool testSimplify(skiatest::Reporter* reporter, const SkPath& path) { return result == 0; } +#if DEBUG_SHOW_TEST_NAME +void DebugShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp, const char* testName) { + ShowFunctionHeader(testName); + showPath(a, "path", true); + showPath(b, "pathB", true); + ShowOp(shapeOp, "path", "pathB"); +} +#endif + bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b, - const SkPathOp shapeOp) { + const SkPathOp shapeOp, const char* testName) { #if DEBUG_SHOW_TEST_NAME - showPathData(a); - showOp(shapeOp); - showPathData(b); + if (testName == NULL) { + showPathData(a); + showOp(shapeOp); + showPathData(b); + } else { + DebugShowPath(a, b, shapeOp, testName); + } #endif SkPath out; if (!Op(a, b, shapeOp, &out) ) { @@ -566,7 +588,7 @@ int initializeTests(skiatest::Reporter* reporter, const char* test) { testNumber = atoi(numLoc) + 1; } } - return reporter->allowThreaded() ? SkThreadPool::kThreadPerCore : 0; + return reporter->allowThreaded() ? SkThreadPool::kThreadPerCore : 1; } void outputProgress(char* ramStr, const char* pathStr, SkPath::FillType pathFillType) { diff --git a/tests/PathOpsExtendedTest.h b/tests/PathOpsExtendedTest.h index 5e91dc1fd3..723135a33b 100644 --- a/tests/PathOpsExtendedTest.h +++ b/tests/PathOpsExtendedTest.h @@ -27,7 +27,7 @@ extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap); extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths); extern void showOp(const SkPathOp op); extern bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b, - const SkPathOp ); + const SkPathOp , const char* testName = NULL); extern bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& state, const char* pathStr); extern bool testSimplify(skiatest::Reporter* reporter, const SkPath& path); @@ -40,5 +40,8 @@ void RunTestSet(skiatest::Reporter* reporter, TestDesc tests[], size_t count, void (*firstTest)(skiatest::Reporter* ), void (*stopTest)(skiatest::Reporter* ), bool reverse); void ShowTestName(PathOpsThreadState* data, int a, int b, int c, int d); +void ShowFunctionHeader(const char* name); +void ShowPath(const SkPath& path, const char* pathName); +void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo); #endif diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp index db6003da9d..be40ae418f 100644 --- a/tests/PathOpsLineIntersectionTest.cpp +++ b/tests/PathOpsLineIntersectionTest.cpp @@ -10,6 +10,11 @@ // FIXME: add tests for intersecting, non-intersecting, degenerate, coincident static const SkDLine tests[][2] = { +#if 0 // FIXME: these fail because one line is too short and appears quasi-coincident + {{{{158.000000, 926.000000}, {1108.00000, 926.000000}}}, + {{{1108.00000, 926.000000}, {1108.00000, 925.999634}}}}, + {{{{1108,926}, {1108,925.9996337890625}}}, {{{158,926}, {1108,926}}}}, +#endif {{{{192, 4}, {243, 4}}}, {{{246, 4}, {189, 4}}}}, {{{{246, 4}, {189, 4}}}, {{{192, 4}, {243, 4}}}}, {{{{5, 0}, {0, 5}}}, {{{5, 4}, {1, 4}}}}, @@ -34,6 +39,13 @@ static const SkDLine noIntersect[][2] = { static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect); +static const SkDLine coincidentTests[][2] = { + {{{{235.681549, 531.000000}, {280.318420, 321.000000}}}, + {{{286.695129, 291.000000}, {229.304855, 561.000000}}}}, +}; + +static const size_t coincidentTests_count = SK_ARRAY_COUNT(coincidentTests); + static void check_results(skiatest::Reporter* reporter, const SkDLine& line1, const SkDLine& line2, const SkIntersections& ts) { for (int i = 0; i < ts.used(); ++i) { @@ -48,43 +60,75 @@ static void check_results(skiatest::Reporter* reporter, const SkDLine& line1, co } } +static void testOne(skiatest::Reporter* reporter, const SkDLine& line1, const SkDLine& line2) { + SkIntersections i; + int pts = i.intersect(line1, line2); + REPORTER_ASSERT(reporter, pts); + REPORTER_ASSERT(reporter, pts == i.used()); + check_results(reporter, line1, line2, i); + if (line1[0] == line1[1] || line2[0] == line2[1]) { + return; + } + if (line1[0].fY == line1[1].fY) { + double left = SkTMin(line1[0].fX, line1[1].fX); + double right = SkTMax(line1[0].fX, line1[1].fX); + SkIntersections ts; + ts.horizontal(line2, left, right, line1[0].fY, line1[0].fX != left); + check_results(reporter, line2, line1, ts); + } + if (line2[0].fY == line2[1].fY) { + double left = SkTMin(line2[0].fX, line2[1].fX); + double right = SkTMax(line2[0].fX, line2[1].fX); + SkIntersections ts; + ts.horizontal(line1, left, right, line2[0].fY, line2[0].fX != left); + check_results(reporter, line1, line2, ts); + } + if (line1[0].fX == line1[1].fX) { + double top = SkTMin(line1[0].fY, line1[1].fY); + double bottom = SkTMax(line1[0].fY, line1[1].fY); + SkIntersections ts; + ts.vertical(line2, top, bottom, line1[0].fX, line1[0].fY != top); + check_results(reporter, line2, line1, ts); + } + if (line2[0].fX == line2[1].fX) { + double top = SkTMin(line2[0].fY, line2[1].fY); + double bottom = SkTMax(line2[0].fY, line2[1].fY); + SkIntersections ts; + ts.vertical(line1, top, bottom, line2[0].fX, line2[0].fY != top); + check_results(reporter, line1, line2, ts); + } +} + +static void testOneCoincident(skiatest::Reporter* reporter, const SkDLine& line1, + const SkDLine& line2) { + SkIntersections ts2; + int pts2 = ts2.intersect(line1, line2); + REPORTER_ASSERT(reporter, pts2 == 2); + REPORTER_ASSERT(reporter, pts2 == ts2.used()); + check_results(reporter, line1, line2, ts2); +#if 0 + SkIntersections ts; + int pts = ts.intersect(line1, line2); + REPORTER_ASSERT(reporter, pts == pts2); + REPORTER_ASSERT(reporter, pts == 2); + REPORTER_ASSERT(reporter, pts == ts.used()); + check_results(reporter, line1, line2, ts); +#endif +} + static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { size_t index; + for (index = 0; index < coincidentTests_count; ++index) { + const SkDLine& line1 = coincidentTests[index][0]; + const SkDLine& line2 = coincidentTests[index][1]; + testOneCoincident(reporter, line1, line2); + reporter->bumpTestCount(); + } for (index = 0; index < tests_count; ++index) { const SkDLine& line1 = tests[index][0]; const SkDLine& line2 = tests[index][1]; - SkIntersections ts; - int pts = ts.intersect(line1, line2); - REPORTER_ASSERT(reporter, pts); - REPORTER_ASSERT(reporter, pts == ts.used()); - check_results(reporter, line1, line2, ts); - if (line1[0] == line1[1] || line2[0] == line2[1]) { - continue; - } - if (line1[0].fY == line1[1].fY) { - double left = SkTMin(line1[0].fX, line1[1].fX); - double right = SkTMax(line1[0].fX, line1[1].fX); - ts.horizontal(line2, left, right, line1[0].fY, line1[0].fX != left); - check_results(reporter, line2, line1, ts); - } - if (line2[0].fY == line2[1].fY) { - double left = SkTMin(line2[0].fX, line2[1].fX); - double right = SkTMax(line2[0].fX, line2[1].fX); - ts.horizontal(line1, left, right, line2[0].fY, line2[0].fX != left); - check_results(reporter, line1, line2, ts); - } - if (line1[0].fX == line1[1].fX) { - double top = SkTMin(line1[0].fY, line1[1].fY); - double bottom = SkTMax(line1[0].fY, line1[1].fY); - ts.vertical(line2, top, bottom, line1[0].fX, line1[0].fY != top); - check_results(reporter, line2, line1, ts); - } - if (line2[0].fX == line2[1].fX) { - double top = SkTMin(line2[0].fY, line2[1].fY); - double bottom = SkTMax(line2[0].fY, line2[1].fY); - ts.vertical(line1, top, bottom, line2[0].fX, line2[0].fY != top); - check_results(reporter, line1, line2, ts); - } + testOne(reporter, line1, line2); + reporter->bumpTestCount(); } for (index = 0; index < noIntersect_count; ++index) { const SkDLine& line1 = noIntersect[index][0]; @@ -93,8 +137,29 @@ static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { int pts = ts.intersect(line1, line2); REPORTER_ASSERT(reporter, !pts); REPORTER_ASSERT(reporter, pts == ts.used()); + reporter->bumpTestCount(); } } +static void PathOpsLineIntersectionTestOne(skiatest::Reporter* reporter) { + int index = 0; + SkASSERT(index < (int) tests_count); + const SkDLine& line1 = tests[index][0]; + const SkDLine& line2 = tests[index][1]; + testOne(reporter, line1, line2); +} + +static void PathOpsLineIntersectionTestOneCoincident(skiatest::Reporter* reporter) { + int index = 0; + SkASSERT(index < (int) coincidentTests_count); + const SkDLine& line1 = coincidentTests[index][0]; + const SkDLine& line2 = coincidentTests[index][1]; + testOneCoincident(reporter, line1, line2); +} + #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionTest) + +DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionTestOne) + +DEFINE_TESTCLASS_SHORT(PathOpsLineIntersectionTestOneCoincident) diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 9a48f7812f..e06bc8f57c 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -1144,7 +1144,6 @@ static void cubicOp69d(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kDifference_PathOp); } - SkPathOp ops[] = { kUnion_PathOp, kXOR_PathOp, @@ -1572,7 +1571,6 @@ static void skpClip1(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kIntersect_PathOp); } -#if 1 // FIXME: work in progress -- coincident cubic undetected static void skpClip2(skiatest::Reporter* reporter) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -1598,14 +1596,152 @@ static void skpClip2(skiatest::Reporter* reporter) { pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp); } + +static void skp96prezzi1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(157.464005f, 670.463989f); + path.quadTo(158.928925f, 669.000000f, 161.000000f, 669.000000f); + path.lineTo(248.000000f, 669.000000f); + path.quadTo(250.071075f, 669.000000f, 251.535995f, 670.463989f); + path.quadTo(253.000000f, 671.928955f, 253.000000f, 674.000000f); + path.lineTo(253.000000f, 706.000000f); + path.lineTo(251.000000f, 706.000000f); + path.lineTo(251.000000f, 675.000000f); + path.cubicTo(251.000000f, 672.790833f, 249.209137f, 671.000000f, 247.000000f, 671.000000f); + path.lineTo(162.000000f, 671.000000f); + path.cubicTo(159.790863f, 671.000000f, 158.000000f, 672.790833f, 158.000000f, 675.000000f); + path.lineTo(158.000000f, 706.000000f); + path.lineTo(156.000000f, 706.000000f); + path.lineTo(156.000000f, 674.000000f); + path.quadTo(156.000000f, 671.928955f, 157.464005f, 670.463989f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(156.000000f, 669.000000f); + pathB.lineTo(178.500000f, 691.500000f); + pathB.lineTo(230.500000f, 691.500000f); + pathB.lineTo(253.000000f, 669.000000f); + pathB.lineTo(156.000000f, 669.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skpancestry_com1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(161.000000f, 925.000000f); + path.cubicTo(159.874390f, 925.000000f, 158.835663f, 925.371948f, 158.000000f, 925.999634f); + path.lineTo(158.000000f, 926.000000f); + path.lineTo(1108.00000f, 926.000000f); + path.lineTo(1108.00000f, 925.999634f); + path.cubicTo(1107.16443f, 925.371948f, 1106.12561f, 925.000000f, 1105.00000f, 925.000000f); + path.lineTo(161.000000f, 925.000000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.moveTo(161.000000f, 926.000000f); + pathB.lineTo(1105.00000f, 926.000000f); + pathB.cubicTo(1107.20911f, 926.000000f, 1109.00000f, 927.790833f, 1109.00000f, 930.000000f); + pathB.lineTo(1109.00000f, 956.000000f); + pathB.cubicTo(1109.00000f, 958.209167f, 1107.20911f, 960.000000f, 1105.00000f, 960.000000f); + pathB.lineTo(161.000000f, 960.000000f); + pathB.cubicTo(158.790863f, 960.000000f, 157.000000f, 958.209167f, 157.000000f, 956.000000f); + pathB.lineTo(157.000000f, 930.000000f); + pathB.cubicTo(157.000000f, 927.790833f, 158.790863f, 926.000000f, 161.000000f, 926.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skpeldorado_com_ua1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(286.695129f, 291.000000f); + path.lineTo(229.304855f, 561.000000f); + path.lineTo(979.304871f, 561.000000f); + path.lineTo(1036.69507f, 291.000000f); + path.lineTo(286.695129f, 291.000000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1006.69513f, 291.000000f); + pathB.cubicTo(1023.26367f, 291.000000f, 1033.84021f, 304.431458f, 1030.31836f, 321.000000f); + pathB.lineTo(985.681519f, 531.000000f); + pathB.cubicTo(982.159790f, 547.568542f, 965.873413f, 561.000000f, 949.304871f, 561.000000f); + pathB.lineTo(259.304871f, 561.000000f); + pathB.cubicTo(242.736313f, 561.000000f, 232.159805f, 547.568542f, 235.681549f, 531.000000f); + pathB.lineTo(280.318420f, 321.000000f); + pathB.cubicTo(283.840179f, 304.431458f, 300.126587f, 291.000000f, 316.695129f, 291.000000f); + pathB.lineTo(1006.69513f, 291.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skpbyte_com1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(968.000000f, 14.0000000f); + path.cubicTo(965.238586f, 14.0000000f, 963.000000f, 16.2385769f, 963.000000f, 19.0000000f); + path.lineTo(963.000000f, 32.0000000f); + path.cubicTo(963.000000f, 34.7614250f, 965.238586f, 37.0000000f, 968.000000f, 37.0000000f); + path.lineTo(1034.00000f, 37.0000000f); + path.cubicTo(1036.76147f, 37.0000000f, 1039.00000f, 34.7614250f, 1039.00000f, 32.0000000f); + path.lineTo(1039.00000f, 19.0000000f); + path.cubicTo(1039.00000f, 16.2385769f, 1036.76147f, 14.0000000f, 1034.00000f, 14.0000000f); + path.lineTo(968.000000f, 14.0000000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kInverseWinding_FillType); + pathB.moveTo(968.000000f, 14.0000000f); + pathB.lineTo(1034.00000f, 14.0000000f); + pathB.cubicTo(1036.76147f, 14.0000000f, 1039.00000f, 16.2385750f, 1039.00000f, 19.0000000f); + pathB.lineTo(1039.00000f, 32.0000000f); + pathB.cubicTo(1039.00000f, 34.2091408f, 1036.76147f, 36.0000000f, 1034.00000f, 36.0000000f); + pathB.lineTo(968.000000f, 36.0000000f); + pathB.cubicTo(965.238586f, 36.0000000f, 963.000000f, 34.2091408f, 963.000000f, 32.0000000f); + pathB.lineTo(963.000000f, 19.0000000f); + pathB.cubicTo(963.000000f, 16.2385750f, 965.238586f, 14.0000000f, 968.000000f, 14.0000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skphealth_com76(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(708.099182f, 7.09919119f); + path.lineTo(708.099182f, 7.09920025f); + path.quadTo(704.000000f, 11.2010098f, 704.000000f, 17.0000000f); + path.lineTo(704.000000f, 33.0000000f); + path.lineTo(705.000000f, 33.0000000f); + path.lineTo(705.000000f, 17.0000000f); + path.cubicTo(705.000000f, 13.4101496f, 706.455078f, 10.1601505f, 708.807617f, 7.80761385f); + path.lineTo(708.099182f, 7.09919119f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(704.000000f, 3.00000000f); +#if 0 + pathB.lineTo(719.500000f, 3.00000000f); + pathB.lineTo(705.000000f, 33.0000000f); + pathB.lineTo(704.000000f, 33.0000000f); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +#else + pathB.lineTo(704.000000f, 33.0000000f); + pathB.lineTo(705.000000f, 33.0000000f); + pathB.lineTo(719.500000f, 3.00000000f); + testPathOp(reporter, path, pathB, kIntersect_PathOp); #endif +} static void (*firstTest)(skiatest::Reporter* ) = 0; static struct TestDesc tests[] = { -#if 1 // FIXME: work in progress -- coincident cubic undetected + TEST(skphealth_com76), + TEST(skpancestry_com1), + TEST(skpbyte_com1), + TEST(skpeldorado_com_ua1), + TEST(skp96prezzi1), TEST(skpClip2), -#endif TEST(skpClip1), TEST(cubicOp84d), TEST(cubicOp83i), @@ -1746,6 +1882,9 @@ static void PathOpsOpTest(skiatest::Reporter* reporter) { gDebugMaxWindSum = 4; gDebugMaxWindValue = 4; #endif +#if DEBUG_SHOW_TEST_NAME + strncpy(DEBUG_FILENAME_STRING, "", DEBUG_FILENAME_STRING_LENGTH); +#endif if (runSubTestsFirst) { RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse); } diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index fe5f4e145d..85f6685c3f 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -2859,33 +2859,33 @@ path.close(); static void testQuadratic58(skiatest::Reporter* reporter) { SkPath path; -path.moveTo(283.714233f, 240); -path.lineTo(283.714233f, 141.299606f); -path.lineTo(303.12088f, 141.299606f); -path.lineTo(330.463562f, 217.659027f); -path.lineTo(358.606506f, 141.299606f); -path.lineTo(362.874634f, 159.705902f); -path.lineTo(335.665344f, 233.397751f); -path.lineTo(322.12738f, 233.397751f); -path.lineTo(295.718353f, 159.505829f); -path.lineTo(295.718353f, 240); -path.lineTo(283.714233f, 240); -path.close(); -path.moveTo(322.935669f, 231.030273f); -path.quadTo(312.832214f, 220.393295f, 312.832214f, 203.454178f); -path.quadTo(312.832214f, 186.981888f, 321.73526f, 176.444946f); -path.quadTo(330.638306f, 165.90802f, 344.509705f, 165.90802f); -path.quadTo(357.647522f, 165.90802f, 364.81665f, 175.244537f); -path.lineTo(371.919067f, 205.854996f); -path.lineTo(326.236786f, 205.854996f); -path.quadTo(329.104431f, 231.663818f, 351.512085f, 231.663818f); -path.lineTo(322.935669f, 231.030273f); -path.close(); -path.moveTo(326.837006f, 195.984955f); -path.lineTo(358.78125f, 195.984955f); -path.quadTo(358.78125f, 175.778046f, 343.709442f, 175.778046f); -path.quadTo(328.570923f, 175.778046f, 326.837006f, 195.984955f); -path.close(); + path.moveTo(283.714233f, 240); + path.lineTo(283.714233f, 141.299606f); + path.lineTo(303.12088f, 141.299606f); + path.lineTo(330.463562f, 217.659027f); + path.lineTo(358.606506f, 141.299606f); + path.lineTo(362.874634f, 159.705902f); + path.lineTo(335.665344f, 233.397751f); + path.lineTo(322.12738f, 233.397751f); + path.lineTo(295.718353f, 159.505829f); + path.lineTo(295.718353f, 240); + path.lineTo(283.714233f, 240); + path.close(); + path.moveTo(322.935669f, 231.030273f); + path.quadTo(312.832214f, 220.393295f, 312.832214f, 203.454178f); + path.quadTo(312.832214f, 186.981888f, 321.73526f, 176.444946f); + path.quadTo(330.638306f, 165.90802f, 344.509705f, 165.90802f); + path.quadTo(357.647522f, 165.90802f, 364.81665f, 175.244537f); + path.lineTo(371.919067f, 205.854996f); + path.lineTo(326.236786f, 205.854996f); + path.quadTo(329.104431f, 231.663818f, 351.512085f, 231.663818f); + path.lineTo(322.935669f, 231.030273f); + path.close(); + path.moveTo(326.837006f, 195.984955f); + path.lineTo(358.78125f, 195.984955f); + path.quadTo(358.78125f, 175.778046f, 343.709442f, 175.778046f); + path.quadTo(328.570923f, 175.778046f, 326.837006f, 195.984955f); + path.close(); testSimplify(reporter, path); } @@ -3557,7 +3557,6 @@ static void testCubic2(skiatest::Reporter* reporter) { testSimplify(reporter, path); } -#if 01 // FIXME: enable and fix static void testQuad1(skiatest::Reporter* reporter) { SkPath path; path.moveTo(0,0); @@ -3569,7 +3568,6 @@ static void testQuad1(skiatest::Reporter* reporter) { path.close(); testSimplify(reporter, path); } -#endif static void testQuadralateral2(skiatest::Reporter* reporter) { SkPath path; @@ -3811,9 +3809,29 @@ static void testQuadLineIntersect3(skiatest::Reporter* reporter) { testSimplify(reporter, path); } +static void skphealth_com76(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(708.099182f, 7.09919119f); + path.lineTo(708.099182f, 7.09920025f); + path.quadTo(704.000000f, 11.2010098f, 704.000000f, 17.0000000f); + path.lineTo(704.000000f, 33.0000000f); + path.lineTo(705.000000f, 33.0000000f); + path.lineTo(705.000000f, 17.0000000f); + path.cubicTo(705.000000f, 13.4101496f, 706.455078f, 10.1601505f, 708.807617f, 7.80761385f); + path.lineTo(708.099182f, 7.09919119f); + path.close(); + path.moveTo(704.000000f, 3.00000000f); + path.lineTo(704.000000f, 33.0000000f); + path.lineTo(705.000000f, 33.0000000f); + path.lineTo(719.500000f, 3.00000000f); + testSimplify(reporter, path); +} + static void (*firstTest)(skiatest::Reporter* ) = 0; static TestDesc tests[] = { + TEST(skphealth_com76), TEST(testQuadLineIntersect1), TEST(testQuadLineIntersect2), TEST(testQuadLineIntersect3), diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp index 98e55539ef..f46ad976d5 100644 --- a/tests/PathOpsSkpClipTest.cpp +++ b/tests/PathOpsSkpClipTest.cpp @@ -1,3 +1,5 @@ +#include "PathOpsExtendedTest.h" +#include "PathOpsThreadedCommon.h" #include "SkBitmap.h" #include "SkDevice.h" #include "SkCanvas.h" @@ -7,60 +9,143 @@ #include "SkOSFile.h" #include "SkPicture.h" #include "SkString.h" -#include "Test.h" + +#ifdef SK_BUILD_FOR_WIN +#define PATH_SLASH "\\" +#define IN_DIR "D:" PATH_SLASH "skp" +#define OUT_DIR "D:" PATH_SLASH +#else +#define PATH_SLASH "/" +#define IN_DIR "/Volumes/Untitled" PATH_SLASH +#define OUT_DIR PATH_SLASH +#endif + +static const char pictDir[] = IN_DIR ; +static const char outSkpClipDir[] = OUT_DIR "skpClip"; +static const char outOldClipDir[] = OUT_DIR "oldClip"; static void make_filepath(SkString* path, const char* dir, const SkString& name) { size_t len = strlen(dir); path->set(dir); - if (len > 0 && dir[len - 1] != '/') { - path->append("\\"); + if (len > 0 && dir[len - 1] != PATH_SLASH[0]) { + path->append(PATH_SLASH); } path->append(name); } +static void testOne(const SkString& filename) { +#if DEBUG_SHOW_TEST_NAME + SkString testName(filename); + const char http[] = "http"; + if (testName.startsWith(http)) { + testName.remove(0, sizeof(http) - 1); + } + while (testName.startsWith("_")) { + testName.remove(0, 1); + } + const char dotSkp[] = ".skp"; + if (testName.endsWith(dotSkp)) { + size_t len = testName.size(); + testName.remove(len - (sizeof(dotSkp) - 1), sizeof(dotSkp) - 1); + } + testName.prepend("skp"); + testName.append("1"); + strncpy(DEBUG_FILENAME_STRING, testName.c_str(), DEBUG_FILENAME_STRING_LENGTH); +#endif + SkString path; + make_filepath(&path, pictDir, filename); + SkFILEStream stream(path.c_str()); + if (!stream.isValid()) { + return; + } + bool success; + SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream, &success, &SkImageDecoder::DecodeMemory)); + if (!success) { + SkDebugf("unable to decode %s\n", filename.c_str()); + return; + } + int width = pic->width(); + int height = pic->height(); + SkBitmap bitmap; + bitmap.setConfig(SkBitmap::kARGB_8888_Config, width, height); + success = bitmap.allocPixels(); + if (!success) { + SkDebugf("unable to allocate bitmap for %s\n", filename.c_str()); + return; + } + SkCanvas canvas(bitmap); + SkString pngName(filename); + pngName.remove(pngName.size() - 3, 3); + pngName.append("png"); + for (int i = 0; i < 2; ++i) { + bool useOp = i ? true : false; + canvas.setAllowSimplifyClip(useOp); + pic->draw(&canvas); + SkString outFile; + make_filepath(&outFile, useOp ? outSkpClipDir : outOldClipDir, pngName); + SkImageEncoder::EncodeFile(outFile.c_str(), bitmap, SkImageEncoder::kPNG_Type, 100); + } + SkDELETE(pic); +} + +const char skipBefore[] = "http___health_com.skp"; + static void PathOpsSkpClipTest(skiatest::Reporter* reporter) { - const char pictDir[] = "D:\\skp"; - const char outSkpClipDir[] = "D:\\skpClip"; - const char outOldClipDir[] = "D:\\oldClip"; SkOSFile::Iter iter(pictDir, "skp"); SkString filename; + int testCount = 0; while (iter.next(&filename)) { -#if 01 - if (strcmp(filename.c_str(), "desk_15min-lt.skp")) { + if (strcmp(filename.c_str(), skipBefore) < 0) { continue; } -#endif - SkString path; - make_filepath(&path, pictDir, filename); - SkFILEStream stream(path.c_str()); - if (!stream.isValid()) { - continue; + testOne(filename); + if (reporter->verbose()) { + SkDebugf("."); + if (++testCount % 100 == 0) { + SkDebugf("\n"); + } } - bool success; - SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream, &success, &SkImageDecoder::DecodeMemory)); - if (!success) { - continue; + reporter->bumpTestCount(); + } +} + +static void testSkpClipMain(PathOpsThreadState* data) { + SkString str(data->fSerialNo); + testOne(str); + if (data->fReporter->verbose()) { + SkDebugf("."); + static int threadTestCount; + sk_atomic_inc(&threadTestCount); + if (threadTestCount % 100 == 0) { + SkDebugf("\n"); + } } - int width = pic->width(); - int height = pic->height(); - SkBitmap bitmap; - bitmap.setConfig(SkBitmap::kARGB_8888_Config, width, height); - bitmap.allocPixels(); - SkCanvas canvas(bitmap); - filename.remove(filename.size() - 3, 3); - filename.append("png"); - for (int i = 0; i < 2; ++i) { - bool useOp = i ? true : false; - canvas.setAllowSimplifyClip(useOp); - pic->draw(&canvas); - SkString outFile; - make_filepath(&outFile, useOp ? outSkpClipDir : outOldClipDir, filename); - SkImageEncoder::EncodeFile(outFile.c_str(), bitmap, SkImageEncoder::kPNG_Type, 100); +} + +static void PathOpsSkpClipThreadedTest(skiatest::Reporter* reporter) { + int threadCount = initializeTests(reporter, "skpClipThreadedTest"); + PathOpsThreadedTestRunner testRunner(reporter, threadCount); + SkOSFile::Iter iter(pictDir, "skp"); + SkString filename; + while (iter.next(&filename)) { + if (strcmp(filename.c_str(), skipBefore) < 0) { + continue; } - SkDELETE(pic); + *testRunner.fRunnables.append() = SkNEW_ARGS(PathOpsThreadedRunnable, + (&testSkpClipMain, filename.c_str(), &testRunner)); reporter->bumpTestCount(); } + testRunner.render(); +} + +static void PathOpsSkpClipTestOne(skiatest::Reporter* reporter) { + SkString filename(skipBefore); + testOne(filename); } #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTest) + +DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTestOne) + +DEFINE_TESTCLASS_SHORT(PathOpsSkpClipThreadedTest) diff --git a/tests/PathOpsThreadedCommon.h b/tests/PathOpsThreadedCommon.h index 833f24fe5d..e6d3bed725 100644 --- a/tests/PathOpsThreadedCommon.h +++ b/tests/PathOpsThreadedCommon.h @@ -25,7 +25,7 @@ struct PathOpsThreadState { unsigned char fD; char* fPathStr; const char* fKey; - char fSerialNo[9]; + char fSerialNo[64]; skiatest::Reporter* fReporter; SkBitmap* fBitmap; }; @@ -59,6 +59,14 @@ public: fTestFun = testFun; } + PathOpsThreadedRunnable(void (*testFun)(PathOpsThreadState*), const char* str, + PathOpsThreadedTestRunner* runner) { + SkASSERT(strlen(str) < sizeof(fState.fSerialNo) - 1); + strcpy(fState.fSerialNo, str); + fState.fReporter = runner->fReporter; + fTestFun = testFun; + } + virtual void run() SK_OVERRIDE { SkBitmap bitmap; fState.fBitmap = &bitmap; diff --git a/tests/Test.h b/tests/Test.h index fa62afeab3..27b31df94d 100644 --- a/tests/Test.h +++ b/tests/Test.h @@ -33,6 +33,7 @@ namespace skiatest { virtual bool allowExtendedTest() const { return false; } virtual bool allowThreaded() const { return false; } + virtual bool verbose() const { return false; } virtual void bumpTestCount() { sk_atomic_inc(&fTestCount); } protected: diff --git a/tests/skia_test.cpp b/tests/skia_test.cpp index 98168c55dd..dc1015d6d5 100644 --- a/tests/skia_test.cpp +++ b/tests/skia_test.cpp @@ -57,12 +57,13 @@ private: class DebugfReporter : public Reporter { public: - DebugfReporter(bool allowExtendedTest, bool allowThreaded) + DebugfReporter(bool allowExtendedTest, bool allowThreaded, bool verbose) : fNextIndex(0) , fPending(0) , fTotal(0) , fAllowExtendedTest(allowExtendedTest) - , fAllowThreaded(allowThreaded) { + , fAllowThreaded(allowThreaded) + , fVerbose(verbose) { } void setTotal(int total) { @@ -77,6 +78,10 @@ public: return fAllowThreaded; } + virtual bool verbose() const SK_OVERRIDE { + return fVerbose; + } + protected: virtual void onStart(Test* test) { const int index = sk_atomic_inc(&fNextIndex); @@ -106,6 +111,7 @@ private: int fTotal; bool fAllowExtendedTest; bool fAllowThreaded; + bool fVerbose; }; DEFINE_string2(match, m, NULL, "[~][^]substring[$] [...] of test name to run.\n" \ @@ -231,7 +237,7 @@ int tool_main(int argc, char** argv) { SkDebugf("%s\n", header.c_str()); } - DebugfReporter reporter(FLAGS_extendedTest, FLAGS_threaded); + DebugfReporter reporter(FLAGS_extendedTest, FLAGS_threaded, FLAGS_verbose); Iter iter(&reporter); // Count tests first. |