From 07e97fccd2d85076cd22ef411b0773ab92a18abe Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Mon, 8 Jul 2013 17:17:02 +0000 Subject: 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 --- src/pathops/SkDCubicLineIntersection.cpp | 28 ++++ src/pathops/SkDLineIntersection.cpp | 242 ++++++++++++++++--------------- src/pathops/SkDQuadLineIntersection.cpp | 55 +++++-- src/pathops/SkIntersections.cpp | 43 +++++- src/pathops/SkIntersections.h | 11 +- src/pathops/SkOpAngle.cpp | 4 +- src/pathops/SkOpEdgeBuilder.cpp | 169 +++++++++++---------- src/pathops/SkOpEdgeBuilder.h | 5 +- src/pathops/SkOpSegment.cpp | 27 ++-- src/pathops/SkOpSegment.h | 5 +- src/pathops/SkPathOpsCommon.cpp | 4 +- src/pathops/SkPathOpsDebug.cpp | 79 +++------- src/pathops/SkPathOpsDebug.h | 20 ++- src/pathops/SkPathOpsOp.cpp | 15 +- src/pathops/SkPathOpsPoint.h | 10 +- src/pathops/SkPathOpsTypes.cpp | 16 +- src/pathops/SkPathOpsTypes.h | 5 + src/pathops/SkReduceOrder.cpp | 12 +- src/pathops/SkReduceOrder.h | 4 +- 19 files changed, 422 insertions(+), 332 deletions(-) (limited to 'src/pathops') 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 fPathVerbs; SkOpContour* fCurrentContour; SkTArray& fContours; - SkTArray fReducePts; // segments created on the fly - SkTArray 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* 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* 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* 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& 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& 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& angles, int first, - const int contourWinding, const int oppContourWinding) const; - void debugShowSort(const char* fun, const SkTArray& angles, int first); + const int contourWinding, const int oppContourWinding, bool sortable) const; + void debugShowSort(const char* fun, const SkTArray& 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& 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& 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(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(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& 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& 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* 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* 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* reducePts); - static SkPath::Verb Quad(const SkPoint pts[3], SkTArray* 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; -- cgit v1.2.3