diff options
48 files changed, 2366 insertions, 1037 deletions
diff --git a/gyp/core.gypi b/gyp/core.gypi index 6c00a56763..3fdca921b9 100644 --- a/gyp/core.gypi +++ b/gyp/core.gypi @@ -365,7 +365,6 @@ '<(skia_src_path)/pathops/SkPathOpsPoint.h', '<(skia_src_path)/pathops/SkPathOpsQuad.h', '<(skia_src_path)/pathops/SkPathOpsRect.h', - '<(skia_src_path)/pathops/SkPathOpsSpan.h', '<(skia_src_path)/pathops/SkPathOpsTriangle.h', '<(skia_src_path)/pathops/SkPathOpsTypes.h', '<(skia_src_path)/pathops/SkPathWriter.h', diff --git a/gyp/pathops.gypi b/gyp/pathops.gypi index 5daa0fd634..3bb163e98b 100644 --- a/gyp/pathops.gypi +++ b/gyp/pathops.gypi @@ -52,7 +52,6 @@ '../src/pathops/SkPathOpsPoint.h', '../src/pathops/SkPathOpsQuad.h', '../src/pathops/SkPathOpsRect.h', - '../src/pathops/SkPathOpsSpan.h', '../src/pathops/SkPathOpsTriangle.h', '../src/pathops/SkPathOpsTypes.h', '../src/pathops/SkPathWriter.h', diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 0d65446713..05079845fe 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -176,9 +176,10 @@ static void debugShowCubicIntersection(int , const SkIntersectionHelper& , bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { if (test != next) { - if (test->bounds().fBottom < next->bounds().fTop) { + if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) { return false; } + // OPTIMIZATION: outset contour bounds a smidgen instead? if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) { return true; } @@ -373,12 +374,22 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { continue; } } + if (pts >= 2) { + for (int pt = 0; pt < pts - 1; ++pt) { + const SkDPoint& point = ts.pt(pt); + const SkDPoint& next = ts.pt(pt + 1); + if (wt.isNear(ts[swap][pt], ts[swap][pt + 1], point, next) + && wn.isNear(ts[!swap][pt], ts[!swap][pt + 1], point, next)) { + wt.addPartialCoincident(wn, ts, pt, swap); + } + } + } for (int pt = 0; pt < pts; ++pt) { SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); SkPoint point = ts.pt(pt).asSkPoint(); - int testTAt = wt.addT(wn, point, ts[swap][pt]); - int nextTAt = wn.addT(wt, point, ts[!swap][pt]); + int testTAt = wt.addT(wn, point, ts[swap][pt], swap && ts.isNear(pt)); + int nextTAt = wn.addT(wt, point, ts[!swap][pt], !swap && ts.isNear(pt)); wt.addOtherT(testTAt, ts[!swap][pt], nextTAt); wn.addOtherT(nextTAt, ts[swap][pt], testTAt); } @@ -405,7 +416,7 @@ void AddSelfIntersectTs(SkOpContour* test) { SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1); SkPoint point = ts.pt(0).asSkPoint(); int testTAt = wt.addSelfT(wt, point, ts[0][0]); - int nextTAt = wt.addT(wt, point, ts[1][0]); + int nextTAt = wt.addT(wt, point, ts[1][0], ts.isNear(0)); wt.addOtherT(testTAt, ts[1][0], nextTAt); wt.addOtherT(nextTAt, ts[0][0], testTAt); } while (wt.advance()); @@ -425,6 +436,6 @@ void CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) { } for (int cIndex = 0; cIndex < contourCount; ++cIndex) { SkOpContour* contour = (*contourList)[cIndex]; - contour->findTooCloseToCall(); + contour->calcPartialCoincidentWinding(); } } diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index 19e7340cdc..63d434f2fa 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -108,11 +108,13 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()*2, tab, __FUNCTION__, t1Start, t1, t2Start, t2); SkIntersections xlocals; + xlocals.allowNear(false); intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals); SkDebugf(" xlocals.fUsed=%d\n", xlocals.used()); } #endif SkIntersections locals; + locals.allowNear(false); intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals); int tCount = locals.used(); for (int tIdx = 0; tIdx < tCount; ++tIdx) { diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index a891abec66..0abb75b394 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -107,6 +107,9 @@ public: int intersect() { addExactEndPoints(); + if (fAllowNear) { + addNearEndPoints(); + } double rootVals[3]; int roots = intersectRay(rootVals); for (int index = 0; index < roots; ++index) { @@ -122,9 +125,6 @@ public: fIntersections->insert(cubicT, lineT, pt); } } - if (fAllowNear) { - addNearEndPoints(); - } return fIntersections->used(); } @@ -137,6 +137,9 @@ public: int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { addExactHorizontalEndPoints(left, right, axisIntercept); + if (fAllowNear) { + addNearHorizontalEndPoints(left, right, axisIntercept); + } double rootVals[3]; int roots = horizontalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -147,9 +150,6 @@ public: fIntersections->insert(cubicT, lineT, pt); } } - if (fAllowNear) { - addNearHorizontalEndPoints(left, right, axisIntercept); - } if (flipped) { fIntersections->flip(); } @@ -165,6 +165,9 @@ public: int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { addExactVerticalEndPoints(top, bottom, axisIntercept); + if (fAllowNear) { + addNearVerticalEndPoints(top, bottom, axisIntercept); + } double rootVals[3]; int roots = verticalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -175,9 +178,6 @@ public: fIntersections->insert(cubicT, lineT, pt); } } - if (fAllowNear) { - addNearVerticalEndPoints(top, bottom, axisIntercept); - } if (flipped) { fIntersections->flip(); } @@ -287,6 +287,17 @@ public: } else if (ptSet == kPointUninitialized) { *pt = fCubic.ptAtT(cT); } + SkPoint gridPt = pt->asSkPoint(); + if (gridPt == fLine[0].asSkPoint()) { + *lineT = 0; + } else if (gridPt == fLine[1].asSkPoint()) { + *lineT = 1; + } + if (gridPt == fCubic[0].asSkPoint() && approximately_equal(*cubicT, 0)) { + *cubicT = 0; + } else if (gridPt == fCubic[3].asSkPoint() && approximately_equal(*cubicT, 1)) { + *cubicT = 1; + } return true; } diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index 46118429cd..4b818dcb97 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -35,21 +35,18 @@ int SkIntersections::computePoints(const SkDLine& line, int used) { } int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { - double axLen = a[1].fX - a[0].fX; - double ayLen = a[1].fY - a[0].fY; - double bxLen = b[1].fX - b[0].fX; - double byLen = b[1].fY - b[0].fY; + SkDVector aLen = a[1] - a[0]; + SkDVector bLen = b[1] - b[0]; /* Slopes match when denom goes to zero: axLen / ayLen == bxLen / byLen (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen byLen * axLen == ayLen * bxLen byLen * axLen - ayLen * bxLen == 0 ( == denom ) */ - double denom = byLen * axLen - ayLen * bxLen; - double ab0y = a[0].fY - b[0].fY; - double ab0x = a[0].fX - b[0].fX; - double numerA = ab0y * bxLen - byLen * ab0x; - double numerB = ab0y * axLen - ayLen * ab0x; + double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX; + SkDVector ab0 = a[0] - b[0]; + double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX; + double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX; numerA /= denom; numerB /= denom; int used; @@ -63,8 +60,8 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { 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)) { + if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX, + aLen.fX * b[0].fY - aLen.fY * b[0].fX)) { return fUsed = 0; } // there's no great answer for intersection points for coincident rays, but return something @@ -106,8 +103,8 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { double ayBxLen = ayLen * bxLen; // detect parallel lines the same way here and in SkOpAngle operator < // so that non-parallel means they are also sortable - bool parallel = AlmostEqualUlps(axByLen, ayBxLen); - if (!parallel) { + bool unparallel = NotAlmostEqualUlps(axByLen, ayBxLen); + if (unparallel) { double ab0y = a[0].fY - b[0].fY; double ab0x = a[0].fX - b[0].fX; double numerA = ab0y * bxLen - byLen * ab0x; @@ -119,7 +116,7 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { computePoints(a, 1); } } - if (fAllowNear || parallel) { + if (fAllowNear || !unparallel) { for (int iA = 0; iA < 2; ++iA) { if ((t = b.nearPoint(a[iA])) >= 0) { insert(iA, t, a[iA]); @@ -131,6 +128,17 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { } } } + while (fUsed > 2) { + removeOne(1); + } + if (fUsed == 2 && unparallel) { + bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; + bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; + if (!startMatch && !endMatch) { + SkASSERT(startMatch || endMatch); + removeOne(endMatch); + } + } return fUsed; } diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index e10fb3f139..5869d7db19 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -391,14 +391,22 @@ static void lookNearEnd(const SkDQuad& q1, const SkDQuad& q2, int testT, int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { // if the quads share an end point, check to see if they overlap - for (int i1 = 0; i1 < 3; i1 += 2) { for (int i2 = 0; i2 < 3; i2 += 2) { - if (q1[i1].approximatelyEqualHalf(q2[i2])) { + if (q1[i1] == q2[i2]) { insert(i1 >> 1, i2 >> 1, q1[i1]); } } } + if (fAllowNear || true) { // FIXME ? cubic/cubic intersection fails without (cubicOp67u) + for (int i1 = 0; i1 < 3; i1 += 2) { + for (int i2 = 0; i2 < 3; i2 += 2) { + if (q1[i1] != q2[i2] && q1[i1].approximatelyEqualHalf(q2[i2])) { + insertNear(i1 >> 1, i2 >> 1, q1[i1]); + } + } + } + } SkASSERT(fUsed < 3); if (only_end_pts_in_common(q1, q2)) { return fUsed; diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index 58b3060ab3..b335c5a4b2 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -137,6 +137,9 @@ public: int intersect() { addExactEndPoints(); + if (fAllowNear) { + addNearEndPoints(); + } double rootVals[2]; int roots = intersectRay(rootVals); for (int index = 0; index < roots; ++index) { @@ -147,9 +150,6 @@ public: fIntersections->insert(quadT, lineT, pt); } } - if (fAllowNear) { - addNearEndPoints(); - } return fIntersections->used(); } @@ -165,6 +165,9 @@ public: int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { addExactHorizontalEndPoints(left, right, axisIntercept); + if (fAllowNear) { + addNearHorizontalEndPoints(left, right, axisIntercept); + } double rootVals[2]; int roots = horizontalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -175,9 +178,6 @@ public: fIntersections->insert(quadT, lineT, pt); } } - if (fAllowNear) { - addNearHorizontalEndPoints(left, right, axisIntercept); - } if (flipped) { fIntersections->flip(); } @@ -196,6 +196,9 @@ public: int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { addExactVerticalEndPoints(top, bottom, axisIntercept); + if (fAllowNear) { + addNearVerticalEndPoints(top, bottom, axisIntercept); + } double rootVals[2]; int roots = verticalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -206,9 +209,6 @@ public: fIntersections->insert(quadT, lineT, pt); } } - if (fAllowNear) { - addNearVerticalEndPoints(top, bottom, axisIntercept); - } if (flipped) { fIntersections->flip(); } @@ -324,6 +324,17 @@ protected: } else if (ptSet == kPointUninitialized) { *pt = fQuad.ptAtT(qT); } + SkPoint gridPt = pt->asSkPoint(); + if (gridPt == fLine[0].asSkPoint()) { + *lineT = 0; + } else if (gridPt == fLine[1].asSkPoint()) { + *lineT = 1; + } + if (gridPt == fQuad[0].asSkPoint()) { + *quadT = 0; + } else if (gridPt == fQuad[2].asSkPoint()) { + *quadT = 1; + } return true; } diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h index 5d8ebcd590..af246b760e 100644 --- a/src/pathops/SkIntersectionHelper.h +++ b/src/pathops/SkIntersectionHelper.h @@ -27,24 +27,24 @@ public: fContour->addOtherT(fIndex, index, otherT, otherIndex); } + void addPartialCoincident(SkIntersectionHelper& other, const SkIntersections& ts, int index, + bool swap) { + fContour->addPartialCoincident(fIndex, other.fContour, other.fIndex, ts, index, swap); + } + // Avoid collapsing t values that are close to the same since // we walk ts to describe consecutive intersections. Since a pair of ts can // be nearly equal, any problems caused by this should be taken care // of later. // On the edge or out of range values are negative; add 2 to get end - int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) { - return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT); + int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT, bool isNear) { + return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT, isNear); } int addSelfT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) { return fContour->addSelfT(fIndex, other.fContour, other.fIndex, pt, newT); } - int addUnsortableT(const SkIntersectionHelper& other, bool start, const SkPoint& pt, - double newT) { - return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT); - } - bool advance() { return ++fIndex < fLast; } @@ -72,6 +72,14 @@ public: && next.fIndex == fLast - 1; } + bool isNear(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const { + const SkOpSegment& segment = fContour->segments()[fIndex]; + double mid = (t1 + t2) / 2; + SkDPoint midPtByT = segment.dPtAtT(mid); + SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2); + return midPtByT.approximatelyEqualHalf(midPtByAvg); + } + SkScalar left() const { return bounds().fLeft; } diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index 242c67b926..3a5e24f0a7 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -93,8 +93,10 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); - fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); - fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); + int clearMask = ~((1 << index) - 1); + fIsCoincident[0] += fIsCoincident[0] & clearMask; + fIsCoincident[1] += fIsCoincident[1] & clearMask; + fIsNear += fIsNear & clearMask; } fPt[index] = pt; fT[0][index] = one; @@ -103,6 +105,14 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { return index; } +void SkIntersections::insertNear(double one, double two, const SkDPoint& pt) { + int index = insert(one, two, pt); + if (index < 0) { + return; + } + fIsNear |= 1 << index; +} + void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { int index = insertSwap(one, two, pt); int bit = 1 << index; @@ -158,6 +168,7 @@ void SkIntersections::removeOne(int index) { fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; + fIsNear -= ((fIsNear >> 1) & ~((1 << index) - 1)) + (fIsNear & (1 << index)); } void SkIntersections::swapPts() { diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index 26a1d1a559..389098d84e 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -23,6 +23,7 @@ public: sk_bzero(fPt, sizeof(fPt)); sk_bzero(fT, sizeof(fT)); sk_bzero(fIsCoincident, sizeof(fIsCoincident)); + sk_bzero(&fIsNear, sizeof(fIsNear)); reset(); } @@ -40,6 +41,7 @@ public: memcpy(fPt, i.fPt, sizeof(fPt)); memcpy(fT, i.fT, sizeof(fT)); memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident)); + memcpy(&fIsNear, &i.fIsNear, sizeof(fIsNear)); fUsed = i.fUsed; fSwap = i.fSwap; SkDEBUGCODE(fDepth = i.fDepth); @@ -109,6 +111,10 @@ public: return (fIsCoincident[0] & 1 << index) != 0; } + bool isNear(int index) { + return (fIsNear & 1 << index) != 0; + } + int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y, bool flipped) { SkDLine line; @@ -206,6 +212,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); + void insertNear(double one, double two, const SkDPoint& pt); // start if index == 0 : end if index == 1 void insertCoincident(double one, double two, const SkDPoint& pt); int intersect(const SkDLine&, const SkDLine&); @@ -243,9 +250,10 @@ private: // used by addCoincident to remove ordinary intersections in range // void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt); - SkDPoint fPt[9]; + SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also double fT[2][9]; - uint16_t fIsCoincident[2]; // bit arrays, one bit set for each coincident T + uint16_t fIsCoincident[2]; // bit set for each curve's coincident T + uint16_t fIsNear; // bit set for each T if 2nd curve's point is near but not equal to 1st unsigned char fUsed; bool fAllowNear; bool fSwap; diff --git a/src/pathops/SkLineParameters.h b/src/pathops/SkLineParameters.h index 8824e54bb1..9cbd8524aa 100644 --- a/src/pathops/SkLineParameters.h +++ b/src/pathops/SkLineParameters.h @@ -39,6 +39,14 @@ public: c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; } + double cubicPart(const SkDCubic& part) { + cubicEndPoints(part); + if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) { + return pointDistance(part[3]); + } + return pointDistance(part[2]); + } + void lineEndPoints(const SkDLine& pts) { a = pts[0].fY - pts[1].fY; b = pts[1].fX - pts[0].fX; @@ -58,6 +66,11 @@ public: c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; } + double quadPart(const SkDQuad& part) { + quadEndPoints(part); + return pointDistance(part[2]); + } + double normalSquared() const { return a * a + b * b; } diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index 0dd0d65f79..c1e2eae831 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -120,13 +120,15 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); } } + SkPath::Verb verb = fSegment->verb(); + SkPath::Verb rVerb = rh.fSegment->verb(); if (y_ry != 0) { // if they aren't coincident, look for a stable cross product // at this point, y's are the same sign, neither is zero // and x's are the same sign, or one (or both) is zero double x_ry = x * ry; double rx_y = rx * y; if (!fComputed && !rh.fComputed) { - if (!AlmostEqualUlps(x_ry, rx_y)) { + if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) { return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); } } else { @@ -140,9 +142,9 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r } } } - if (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); + if (fSide2 * rh.fSide2 == 0) { +// SkASSERT(fSide2 + rh.fSide2 != 0); // hitting this assert means coincidence was undetected + return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2); } // at this point, the initial tangent line is nearly coincident // see if edges curl away from each other @@ -153,8 +155,6 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r // even with no solution, return a stable sort return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); } - SkPath::Verb verb = fSegment->verb(); - SkPath::Verb rVerb = rh.fSegment->verb(); if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) || (rVerb == SkPath::kLine_Verb && approximately_zero(ry) && approximately_zero(rx))) { @@ -173,8 +173,8 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; r // end of the shorter tangent to midway between the end points // through both curves and use the resulting angle to sort // FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive - double len = fTangent1.normalSquared(); - double rlen = rh.fTangent1.normalSquared(); + double len = fTangentPart.normalSquared(); + double rlen = rh.fTangentPart.normalSquared(); SkDLine ray; SkIntersections i, ri; int roots, rroots; @@ -269,62 +269,53 @@ void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { } void SkOpAngle::setSpans() { - fUnorderable = false; - if (fSegment->verb() == SkPath::kLine_Verb) { - fUnsortable = false; - } else { - // if start-1 exists and is tiny, then start pt may have moved - int smaller = SkMin32(fStart, fEnd); - int tinyCheck = smaller; - while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) { - --tinyCheck; - } - if ((fUnsortable = smaller > 0 && tinyCheck == 0)) { - return; - } - int larger = SkMax32(fStart, fEnd); - tinyCheck = larger; - int max = fSegment->count() - 1; - while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) { - ++tinyCheck; - } - if ((fUnsortable = larger < max && tinyCheck == max)) { - return; - } + fUnorderable = fSegment->isTiny(this); + fLastMarked = NULL; + fUnsortable = false; + const SkPoint* pts = fSegment->pts(); + if (fSegment->verb() != SkPath::kLine_Verb) { + fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); + fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf); } - fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try // rounding the curve part to float precision here // fCurvePart.round(fSegment->verb()); switch (fSegment->verb()) { case SkPath::kLine_Verb: { - // OPTIMIZATION: for pure line compares, we never need fTangent1.c - fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); + SkASSERT(fStart != fEnd); + fCurvePart[0].set(pts[fStart > fEnd]); + fCurvePart[1].set(pts[fStart < fEnd]); + fComputed = false; + // OPTIMIZATION: for pure line compares, we never need fTangentPart.c + fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); fSide = 0; + fSide2 = 0; } break; case SkPath::kQuad_Verb: { + fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf)); SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); - fTangent1.quadEndPoints(quad); - fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only + fTangentPart.quadEndPoints(quad); + fSide = -fTangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only if (fComputed && dx() > 0 && approximately_zero(dy())) { SkDCubic origCurve; // can't use segment's curve in place since it may be flipped int last = fSegment->count() - 1; fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); SkLineParameters origTan; origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); - if ((fUnorderable = origTan.dx() <= 0 - || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match? + if (origTan.dx() <= 0 + || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match? + fUnorderable = true; return; } } } break; case SkPath::kCubic_Verb: { - fTangent1.cubicEndPoints(fCurvePart); + double startT = fSegment->t(fStart); + fSide2 = -fTangentHalf.cubicPart(fCurveHalf); + fTangentPart.cubicEndPoints(fCurvePart); double testTs[4]; // OPTIMIZATION: keep inflections precomputed with cubic segment? - const SkPoint* pts = fSegment->pts(); int testCount = SkDCubic::FindInflections(pts, testTs); - double startT = fSegment->t(fStart); double endT = fSegment->t(fEnd); double limitT = endT; int index; @@ -351,36 +342,28 @@ void SkOpAngle::setSpans() { } // OPTIMIZE: could avoid call for t == startT, endT SkDPoint pt = dcubic_xy_at_t(pts, testT); - double testSide = fTangent1.pointDistance(pt); + double testSide = fTangentPart.pointDistance(pt); if (fabs(bestSide) < fabs(testSide)) { bestSide = testSide; } } fSide = -bestSide; // compare sign only + SkASSERT(fSide == 0 || fSide2 != 0); if (fComputed && dx() > 0 && approximately_zero(dy())) { SkDCubic origCurve; // can't use segment's curve in place since it may be flipped int last = fSegment->count() - 1; fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); - SkLineParameters origTan; - origTan.cubicEndPoints(origCurve); - if ((fUnorderable = origTan.dx() <= 0)) { - fUnsortable = fSegment->isTiny(this); - return; - } - // if one is < 0 and the other is >= 0 - if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) { - fUnsortable = fSegment->isTiny(this); - return; - } SkDCubicPair split = origCurve.chopAt(startT); SkLineParameters splitTan; splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); - if ((fUnorderable = splitTan.dx() <= 0)) { + if (splitTan.dx() <= 0) { + fUnorderable = true; fUnsortable = fSegment->isTiny(this); return; } // if one is < 0 and the other is >= 0 - if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) { + if (dy() * splitTan.dy() < 0) { + fUnorderable = true; fUnsortable = fSegment->isTiny(this); return; } @@ -392,39 +375,42 @@ void SkOpAngle::setSpans() { if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { return; } + if (fSegment->verb() == SkPath::kLine_Verb) { + return; + } SkASSERT(fStart != fEnd); - int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? - for (int index = fStart; index != fEnd; index += step) { -#if 1 - const SkOpSpan& thisSpan = fSegment->span(index); - const SkOpSpan& nextSpan = fSegment->span(index + step); - if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) { - continue; - } - fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd; -#if DEBUG_UNSORTABLE - if (fUnsortable) { - SkPoint iPt = fSegment->xyAtT(index); - SkPoint ePt = fSegment->xyAtT(index + step); - SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, - index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); - } -#endif + int smaller = SkMin32(fStart, fEnd); + int larger = SkMax32(fStart, fEnd); + while (smaller < larger && fSegment->span(smaller).fTiny) { + ++smaller; + } + if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) { + #if DEBUG_UNSORTABLE + SkPoint iPt = fSegment->xyAtT(fStart); + SkPoint ePt = fSegment->xyAtT(fEnd); + SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, + fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); + #endif + fUnsortable = true; return; -#else - if ((*fSpans)[index].fUnsortableStart) { - fUnsortable = true; - return; - } -#endif } -#if 1 + fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart + : fSegment->span(larger).fUnsortableEnd; #if DEBUG_UNSORTABLE - SkPoint iPt = fSegment->xyAtT(fStart); - SkPoint ePt = fSegment->xyAtT(fEnd); - SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, - fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); -#endif - fUnsortable = true; + if (fUnsortable) { + SkPoint iPt = fSegment->xyAtT(smaller); + SkPoint ePt = fSegment->xyAtT(larger); + SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, + smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); + } #endif + return; +} + +#ifdef SK_DEBUG +void SkOpAngle::dump() const { + SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g)\n", fSegment->debugID(), + fSegment->xAtT(fStart), fSegment->yAtT(fStart), fStart, fSegment->span(fStart).fT, + fEnd, fSegment->span(fEnd).fT); } +#endif diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h index e7e5e1f597..583f5ec8b3 100644 --- a/src/pathops/SkOpAngle.h +++ b/src/pathops/SkOpAngle.h @@ -12,23 +12,30 @@ #include "SkPathOpsCubic.h" class SkOpSegment; +struct SkOpSpan; // sorting angles // given angles of {dx dy ddx ddy dddx dddy} sort them class SkOpAngle { public: enum { kStackBasedCount = 8 }; // FIXME: determine what this should be + enum IncludeType { + kUnaryWinding, + kUnaryXor, + kBinarySingle, + kBinaryOpp, + }; bool operator<(const SkOpAngle& rh) const; bool calcSlop(double x, double y, double rx, double ry, bool* result) const; double dx() const { - return fTangent1.dx(); + return fTangentPart.dx(); } double dy() const { - return fTangent1.dy(); + return fTangentPart.dy(); } int end() const { @@ -37,8 +44,16 @@ public: bool isHorizontal() const; + SkOpSpan* lastMarked() const { + return fLastMarked; + } + void set(const SkOpSegment* segment, int start, int end); + void setLastMarked(SkOpSpan* marked) { + fLastMarked = marked; + } + SkOpSegment* segment() const { return const_cast<SkOpSegment*>(fSegment); } @@ -59,11 +74,11 @@ public: return fUnsortable; } -#if DEBUG_ANGLE - void debugShow(const SkPoint& a) const { - SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide); - } +#ifdef SK_DEBUG + void dump() const; +#endif +#if DEBUG_ANGLE void setID(int id) { fID = id; } @@ -73,10 +88,14 @@ private: bool lengthen(const SkOpAngle& ); void setSpans(); - SkDCubic fCurvePart; + SkDCubic fCurvePart; // the curve from start to end + SkDCubic fCurveHalf; // the curve from start to 1 or 0 double fSide; - SkLineParameters fTangent1; + double fSide2; + SkLineParameters fTangentPart; + SkLineParameters fTangentHalf; const SkOpSegment* fSegment; + SkOpSpan* fLastMarked; int fStart; int fEnd; bool fComputed; // tangent is computed, may contain some error diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp index f3861a1e0b..facba87f78 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -12,8 +12,7 @@ void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, const SkIntersections& ts, bool swap) { SkCoincidence& coincidence = fCoincidences.push_back(); - coincidence.fContours[0] = this; // FIXME: no need to store - coincidence.fContours[1] = other; + coincidence.fOther = other; coincidence.fSegments[0] = index; coincidence.fSegments[1] = otherIndex; coincidence.fTs[swap][0] = ts[0][0]; @@ -48,10 +47,9 @@ void SkOpContour::addCoincidentPoints() { int count = fCoincidences.count(); for (int index = 0; index < count; ++index) { SkCoincidence& coincidence = fCoincidences[index]; - SkASSERT(coincidence.fContours[0] == this); int thisIndex = coincidence.fSegments[0]; SkOpSegment& thisOne = fSegments[thisIndex]; - SkOpContour* otherContour = coincidence.fContours[1]; + SkOpContour* otherContour = coincidence.fOther; int otherIndex = coincidence.fSegments[1]; SkOpSegment& other = otherContour->fSegments[otherIndex]; if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { @@ -103,51 +101,84 @@ void SkOpContour::addCoincidentPoints() { } } +void SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, + const SkIntersections& ts, int ptIndex, bool swap) { + SkCoincidence& coincidence = fPartialCoincidences.push_back(); + coincidence.fOther = other; + coincidence.fSegments[0] = index; + coincidence.fSegments[1] = otherIndex; + coincidence.fTs[swap][0] = ts[0][index]; + coincidence.fTs[swap][1] = ts[0][index + 1]; + coincidence.fTs[!swap][0] = ts[1][index]; + coincidence.fTs[!swap][1] = ts[1][index + 1]; + coincidence.fPts[0] = ts.pt(index).asSkPoint(); + coincidence.fPts[1] = ts.pt(index + 1).asSkPoint(); +} + void SkOpContour::calcCoincidentWinding() { int count = fCoincidences.count(); +#if DEBUG_CONCIDENT + if (count > 0) { + SkDebugf("%s count=%d\n", __FUNCTION__, count); + } +#endif for (int index = 0; index < count; ++index) { SkCoincidence& coincidence = fCoincidences[index]; - SkASSERT(coincidence.fContours[0] == this); - int thisIndex = coincidence.fSegments[0]; - SkOpSegment& thisOne = fSegments[thisIndex]; - if (thisOne.done()) { - continue; - } - SkOpContour* otherContour = coincidence.fContours[1]; - int otherIndex = coincidence.fSegments[1]; - SkOpSegment& other = otherContour->fSegments[otherIndex]; - if (other.done()) { - continue; - } - double startT = coincidence.fTs[0][0]; - double endT = coincidence.fTs[0][1]; - bool cancelers; - if ((cancelers = startT > endT)) { - SkTSwap<double>(startT, endT); - } - SkASSERT(!approximately_negative(endT - startT)); - double oStartT = coincidence.fTs[1][0]; - double oEndT = coincidence.fTs[1][1]; - if (oStartT > oEndT) { - SkTSwap<double>(oStartT, oEndT); - cancelers ^= true; - } - SkASSERT(!approximately_negative(oEndT - oStartT)); - if (cancelers) { - // make sure startT and endT have t entries - if (!thisOne.done() && !other.done()) { - thisOne.addTCancel(startT, endT, &other, oStartT, oEndT); - } - } else { - if (!thisOne.done() && !other.done()) { - thisOne.addTCoincident(startT, endT, &other, oStartT, oEndT); - } - } - #if DEBUG_CONCIDENT - thisOne.debugShowTs(); - other.debugShowTs(); - #endif + calcCommonCoincidentWinding(coincidence); + } +} + +void SkOpContour::calcPartialCoincidentWinding() { + int count = fPartialCoincidences.count(); +#if DEBUG_CONCIDENT + if (count > 0) { + SkDebugf("%s count=%d\n", __FUNCTION__, count); + } +#endif + for (int index = 0; index < count; ++index) { + SkCoincidence& coincidence = fPartialCoincidences[index]; + calcCommonCoincidentWinding(coincidence); + } +} + +void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { + int thisIndex = coincidence.fSegments[0]; + SkOpSegment& thisOne = fSegments[thisIndex]; + if (thisOne.done()) { + return; } + SkOpContour* otherContour = coincidence.fOther; + int otherIndex = coincidence.fSegments[1]; + SkOpSegment& other = otherContour->fSegments[otherIndex]; + if (other.done()) { + return; + } + double startT = coincidence.fTs[0][0]; + double endT = coincidence.fTs[0][1]; + const SkPoint* startPt = &coincidence.fPts[0]; + const SkPoint* endPt = &coincidence.fPts[1]; + bool cancelers; + if ((cancelers = startT > endT)) { + SkTSwap<double>(startT, endT); + SkTSwap<const SkPoint*>(startPt, endPt); + } + SkASSERT(!approximately_negative(endT - startT)); + double oStartT = coincidence.fTs[1][0]; + double oEndT = coincidence.fTs[1][1]; + if (oStartT > oEndT) { + SkTSwap<double>(oStartT, oEndT); + cancelers ^= true; + } + SkASSERT(!approximately_negative(oEndT - oStartT)); + if (cancelers) { + thisOne.addTCancel(*startPt, *endPt, &other); + } else { + thisOne.addTCoincident(*startPt, *endPt, &other); + } +#if DEBUG_CONCIDENT + thisOne.debugShowTs(); + other.debugShowTs(); +#endif } void SkOpContour::sortSegments() { @@ -229,7 +260,7 @@ int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { return sum; } -static void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { +void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; int ofInterest = 1 << 5 | 1 << 8; diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index 456e6c0068..a5635fe3d2 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -15,7 +15,7 @@ class SkOpContour; class SkPathWriter; struct SkCoincidence { - SkOpContour* fContours[2]; + SkOpContour* fOther; int fSegments[2]; double fTs[2][2]; SkPoint fPts[2]; @@ -25,8 +25,8 @@ class SkOpContour { public: SkOpContour() { reset(); -#if DEBUG_DUMP - fID = ++gContourID; +#ifdef SK_DEBUG + fID = ++SkPathOpsDebug::gContourID; #endif } @@ -63,15 +63,19 @@ public: fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); } + void addPartialCoincident(int index, SkOpContour* other, int otherIndex, + const SkIntersections& ts, int ptIndex, bool swap); + int addQuad(const SkPoint pts[3]) { fSegments.push_back().addQuad(pts, fOperand, fXor); fContainsCurves = true; return fSegments.count(); } - int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) { + int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT, + bool isNear) { setContainsIntercepts(); - return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT); + return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT, isNear); } int addSelfT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) { @@ -79,16 +83,12 @@ public: return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT); } - int addUnsortableT(int segIndex, SkOpContour* other, int otherIndex, bool start, - const SkPoint& pt, double newT) { - return fSegments[segIndex].addUnsortableT(&other->fSegments[otherIndex], start, pt, newT); - } - const SkPathOpsBounds& bounds() const { return fBounds; } void calcCoincidentWinding(); + void calcPartialCoincidentWinding(); void checkEnds() { if (!fContainsCurves) { @@ -100,7 +100,18 @@ public: if (segment->verb() == SkPath::kLine_Verb) { continue; } - fSegments[sIndex].checkEnds(); + segment->checkEnds(); + } + } + + // if same point has different T values, choose a common T + void checkTiny() { + int segmentCount = fSegments.count(); + if (segmentCount <= 2) { + return; + } + for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { + fSegments[sIndex].checkTiny(); } } @@ -131,13 +142,6 @@ public: return segment.pts()[SkPathOpsVerbToPoints(segment.verb())]; } - void findTooCloseToCall() { - int segmentCount = fSegments.count(); - for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { - fSegments[sIndex].findTooCloseToCall(); - } - } - void fixOtherTIndex() { int segmentCount = fSegments.count(); for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { @@ -232,12 +236,14 @@ public: #endif private: + void calcCommonCoincidentWinding(const SkCoincidence& coincidence); void setBounds(); SkTArray<SkOpSegment> fSegments; SkTArray<SkOpSegment*, true> fSortedSegments; int fFirstSorted; SkTArray<SkCoincidence, true> fCoincidences; + SkTArray<SkCoincidence, true> fPartialCoincidences; SkTArray<const SkOpContour*, true> fCrosses; SkPathOpsBounds fBounds; bool fContainsIntercepts; // FIXME: is this used by anybody? @@ -247,7 +253,7 @@ private: bool fOperand; // true for the second argument to a binary operator bool fXor; bool fOppXor; -#if DEBUG_DUMP +#ifdef SK_DEBUG int fID; #endif }; diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp index a5a6584868..676c34fb37 100644 --- a/src/pathops/SkOpEdgeBuilder.cpp +++ b/src/pathops/SkOpEdgeBuilder.cpp @@ -13,9 +13,9 @@ void SkOpEdgeBuilder::init() { fOperand = false; fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask : kWinding_PathOpsMask; -#if DEBUG_DUMP - gContourID = 0; - gSegmentID = 0; +#ifdef SK_DEBUG + SkPathOpsDebug::gContourID = 0; + SkPathOpsDebug::gSegmentID = 0; #endif fUnparseable = false; fSecondHalf = preFetch(); @@ -84,6 +84,9 @@ int SkOpEdgeBuilder::preFetch() { case SkPath::kLine_Verb: if (AlmostEqualUlps(curve[0].fX, pts[1].fX) && AlmostEqualUlps(curve[0].fY, pts[1].fY)) { + if (fPathVerbs.back() != SkPath::kLine_Verb) { + fPathPts.back() = pts[1]; + } continue; // skip degenerate points } break; diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 7e69bb835b..c0ef1f8e11 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -32,36 +32,36 @@ static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = { #undef F #undef T -enum { kOutsideTrackedTCount = 16 }; // FIXME: determine what this should be - -// OPTIMIZATION: does the following also work, and is it any faster? -// return outerWinding * innerWinding > 0 -// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) -bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { - SkASSERT(outerWinding != SK_MaxS32); - SkASSERT(innerWinding != SK_MaxS32); - int absOut = abs(outerWinding); - int absIn = abs(innerWinding); - bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; - return result; -} +enum { + kOutsideTrackedTCount = 16, // FIXME: determine what this should be + kMissingSpanCount = 4, // FIXME: determine what this should be +}; +// note that this follows the same logic flow as build angles bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) { if (activeAngleInner(index, done, angles)) { return true; } + double referenceT = fTs[index].fT; int lesser = index; - while (--lesser >= 0 && equalPoints(index, lesser)) { + while (--lesser >= 0 + && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) { if (activeAngleOther(lesser, done, angles)) { return true; } } - lesser = index; do { if (activeAngleOther(index, done, angles)) { return true; } - } while (++index < fTs.count() && equalPoints(index, lesser)); + if (++index == fTs.count()) { + break; + } + if (fTs[index - 1].fTiny) { + referenceT = fTs[index].fT; + continue; + } + } while (precisely_negative(fTs[index].fT - referenceT)); return false; } @@ -187,7 +187,7 @@ bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; #if DEBUG_ACTIVE_OP SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__, - kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); + SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); #endif return result; } @@ -209,47 +209,35 @@ bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* s void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const { SkASSERT(start != end); SkOpAngle& angle = anglesPtr->push_back(); -#if 0 && DEBUG_ANGLE // computed pt and actual pt may differ by more than approx eq - SkTArray<SkOpAngle, true>& angles = *anglesPtr; - if (angles.count() > 1) { - const SkOpSegment* aSeg = angles[0].segment(); - int aStart = angles[0].start(); - if (!aSeg->fTs[aStart].fTiny) { - const SkPoint& angle0Pt = aSeg->xyAtT(aStart); - SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts, - aSeg->fTs[aStart].fT); -#if ONE_OFF_DEBUG - SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__, - aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY); -#endif - SkASSERT(newPt.approximatelyEqual(angle0Pt)); - } - } -#endif angle.set(this, start, end); } -void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) { +void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, + SkOpSegment* other) { int tIndex = -1; int tCount = fTs.count(); int oIndex = -1; int oCount = other->fTs.count(); do { ++tIndex; - } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount); + } while (startPt != fTs[tIndex].fPt && tIndex < tCount); int tIndexStart = tIndex; do { ++oIndex; - } while (!approximately_negative(oStart - other->fTs[oIndex].fT) && oIndex < oCount); + } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount); int oIndexStart = oIndex; - double nextT; + const SkPoint* nextPt; do { - nextT = fTs[++tIndex].fT; - } while (nextT < 1 && approximately_negative(nextT - tStart)); - double oNextT; + nextPt = &fTs[++tIndex].fPt; + SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt); + } while (startPt == *nextPt); + double nextT = fTs[tIndex].fT; + const SkPoint* oNextPt; do { - oNextT = other->fTs[++oIndex].fT; - } while (oNextT < 1 && approximately_negative(oNextT - oStart)); + oNextPt = &other->fTs[++oIndex].fPt; + SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt); + } while (endPt == *oNextPt); + double oNextT = other->fTs[oIndex].fT; // at this point, spans before and after are at: // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] // if tIndexStart == 0, no prior span @@ -301,43 +289,39 @@ void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* o } } -void SkOpSegment::addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other, - double oEnd) { - // walk this to outsideTs[0] - // walk other to outsideTs[1] +void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, + SkOpSegment* other) { + // walk this to startPt + // walk other to startPt // if either is > 0, add a pointer to the other, copying adjacent winding int tIndex = -1; int oIndex = -1; - double tStart = outsideTs[0]; - double oStart = outsideTs[1]; do { ++tIndex; - } while (!approximately_negative(tStart - fTs[tIndex].fT)); - SkPoint ptStart = fTs[tIndex].fPt; + } while (startPt != fTs[tIndex].fPt); do { ++oIndex; - } while (!approximately_negative(oStart - other->fTs[oIndex].fT)); + } while (startPt != other->fTs[oIndex].fPt); if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) { - addTPair(tStart, other, oStart, false, ptStart); + addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt); } - tStart = fTs[tIndex].fT; - oStart = other->fTs[oIndex].fT; + SkPoint nextPt = startPt; do { - double nextT; + const SkPoint* workPt; do { - nextT = fTs[++tIndex].fT; - } while (approximately_negative(nextT - tStart)); - tStart = nextT; - ptStart = fTs[tIndex].fPt; + workPt = &fTs[++tIndex].fPt; + } while (nextPt == *workPt); do { - nextT = other->fTs[++oIndex].fT; - } while (approximately_negative(nextT - oStart)); - oStart = nextT; + workPt = &other->fTs[++oIndex].fPt; + } while (nextPt == *workPt); + nextPt = *workPt; + double tStart = fTs[tIndex].fT; + double oStart = other->fTs[oIndex].fT; if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) { break; } - addTPair(tStart, other, oStart, false, ptStart); - } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart)); + addTPair(tStart, other, oStart, false, nextPt); + } while (endPt != nextPt); } void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) { @@ -423,7 +407,7 @@ void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) { // resolve overlapping ts when considering coincidence later // add non-coincident intersection. Resulting edges are sorted in T. -int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { +int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear) { if (precisely_zero(newT)) { newT = 0; } else if (precisely_equal(newT, 1)) { @@ -455,6 +439,7 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { span->fT = newT; span->fOther = other; span->fPt = pt; + span->fNear = isNear; #if 0 // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d) SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX) @@ -464,6 +449,7 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { span->fOppSum = SK_MinS32; span->fWindValue = 1; span->fOppValue = 0; + span->fSmall = false; span->fTiny = false; span->fLoop = false; if ((span->fDone = newT == 1)) { @@ -472,7 +458,7 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { span->fUnsortableStart = false; span->fUnsortableEnd = false; int less = -1; - while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) { + while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) { if (span[less].fDone) { break; } @@ -487,9 +473,11 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { break; } } - span[less].fTiny = true; + span[less].fSmall = true; + bool tiny = span[less].fPt == span->fPt; + span[less].fTiny = tiny; span[less].fDone = true; - if (approximately_negative(newT - span[less].fT)) { + if (approximately_negative(newT - span[less].fT) && tiny) { if (approximately_greater_than_one(newT)) { SkASSERT(&span[less] - fTs.begin() < fTs.count()); span[less].fUnsortableStart = true; @@ -508,7 +496,7 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { --less; } int more = 1; - while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) { + while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) { if (span[more - 1].fDone) { break; } @@ -523,9 +511,11 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { break; } } - span[more - 1].fTiny = true; + span[more - 1].fSmall = true; + bool tiny = span[more].fPt == span->fPt; + span[more - 1].fTiny = tiny; span[more - 1].fDone = true; - if (approximately_negative(span[more].fT - newT)) { + if (approximately_negative(span[more].fT - newT) && tiny) { if (approximately_greater_than_one(span[more].fT)) { span[more + 1].fUnsortableStart = true; span[more].fUnsortableEnd = true; @@ -553,148 +543,156 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { // FIXME? It seems that decrementing by one will fail for complex paths that // have three or more coincident edges. Shouldn't this subtract the difference // between the winding values? -void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other, - double oStartT, double oEndT) { - SkASSERT(!approximately_negative(endT - startT)); - SkASSERT(!approximately_negative(oEndT - oStartT)); +/* |--> |--> +this 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 +other 2<<<<1<<<<0 2<<<<1<<<<0 2<<<<1<<<<0 + ^ ^ <--| <--| + startPt endPt test/oTest first pos test/oTest final pos +*/ +void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) { bool binary = fOperand != other->fOperand; int index = 0; - while (!approximately_negative(startT - fTs[index].fT)) { + while (startPt != fTs[index].fPt) { + SkASSERT(index < fTs.count()); ++index; } int oIndex = other->fTs.count(); - while (approximately_positive(other->fTs[--oIndex].fT - oEndT)) - ; - double tRatio = (oEndT - oStartT) / (endT - startT); + while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match + SkASSERT(oIndex > 0); + } + while (startPt == other->fTs[--oIndex].fPt) { // look for first point beyond match + SkASSERT(oIndex > 0); + } SkOpSpan* test = &fTs[index]; SkOpSpan* oTest = &other->fTs[oIndex]; - SkSTArray<kOutsideTrackedTCount, double, true> outsideTs; - SkSTArray<kOutsideTrackedTCount, double, true> oOutsideTs; + SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts; + SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts; do { + SkASSERT(test->fT < 1); + SkASSERT(oTest->fT < 1); bool decrement = test->fWindValue && oTest->fWindValue; bool track = test->fWindValue || oTest->fWindValue; bool bigger = test->fWindValue >= oTest->fWindValue; - double testT = test->fT; - double oTestT = oTest->fT; - SkOpSpan* span = test; + const SkPoint& testPt = test->fPt; + const SkPoint& oTestPt = oTest->fPt; do { if (decrement) { if (binary && bigger) { - span->fOppValue--; + test->fOppValue--; } else { - decrementSpan(span); + decrementSpan(test); } - } else if (track && span->fT < 1 && oTestT < 1) { - TrackOutside(&outsideTs, span->fT, oTestT); + } else if (track) { + TrackOutsidePair(&outsidePts, testPt, oTestPt); } - span = &fTs[++index]; - } while (approximately_negative(span->fT - testT)); - SkOpSpan* oSpan = oTest; - double otherTMatchStart = oEndT - (span->fT - startT) * tRatio; - double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio; - SkDEBUGCODE(int originalWindValue = oSpan->fWindValue); - while (approximately_negative(otherTMatchStart - oSpan->fT) - && !approximately_negative(otherTMatchEnd - oSpan->fT)) { - #ifdef SK_DEBUG - SkASSERT(originalWindValue == oSpan->fWindValue); - #endif + SkASSERT(index < fTs.count() - 1); + test = &fTs[++index]; + } while (testPt == test->fPt); + SkDEBUGCODE(int originalWindValue = oTest->fWindValue); + do { + SkASSERT(oTest->fT < 1); + SkASSERT(originalWindValue == oTest->fWindValue); if (decrement) { if (binary && !bigger) { - oSpan->fOppValue--; + oTest->fOppValue--; } else { - other->decrementSpan(oSpan); + other->decrementSpan(oTest); } - } else if (track && oSpan->fT < 1 && testT < 1) { - TrackOutside(&oOutsideTs, oSpan->fT, testT); + } else if (track) { + TrackOutsidePair(&oOutsidePts, oTestPt, testPt); } if (!oIndex) { break; } - oSpan = &other->fTs[--oIndex]; - } - test = span; - oTest = oSpan; - } while (!approximately_negative(endT - test->fT)); - SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT)); + oTest = &other->fTs[--oIndex]; + } while (oTestPt == oTest->fPt); + SkASSERT(endPt != test->fPt || oTestPt == endPt); + } while (endPt != test->fPt); // FIXME: determine if canceled edges need outside ts added - if (!done() && outsideTs.count()) { - double tStart = outsideTs[0]; - double oStart = outsideTs[1]; - addCancelOutsides(tStart, oStart, other, oEndT); - int count = outsideTs.count(); - if (count > 2) { - double tStart = outsideTs[count - 2]; - double oStart = outsideTs[count - 1]; - addCancelOutsides(tStart, oStart, other, oEndT); + int outCount = outsidePts.count(); + if (!done() && outCount) { + addCancelOutsides(outsidePts[0], outsidePts[1], other); + if (outCount > 2) { + addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other); } } - if (!other->done() && oOutsideTs.count()) { - double tStart = oOutsideTs[0]; - double oStart = oOutsideTs[1]; - other->addCancelOutsides(tStart, oStart, this, endT); + if (!other->done() && oOutsidePts.count()) { + other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this); } } int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) { - int result = addT(other, pt, newT); + // if the tail nearly intersects itself but not quite, the caller records this separately + int result = addT(other, pt, newT, SkOpSpan::kPointIsExact); SkOpSpan* span = &fTs[result]; span->fLoop = true; return result; } -int SkOpSegment::addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT) { - int result = addT(other, pt, newT); - SkOpSpan* span = &fTs[result]; - if (start) { - if (result > 0) { - span[result - 1].fUnsortableEnd = true; - } - span[result].fUnsortableStart = true; - } else { - span[result].fUnsortableEnd = true; - if (result + 1 < fTs.count()) { - span[result + 1].fUnsortableStart = true; - } - } - return result; -} - -int SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index, - SkTArray<double, true>* outsideTs) { +void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr, + SkTArray<SkPoint, true>* outsideTs) { + int index = *indexPtr; int oWindValue = oTest.fWindValue; int oOppValue = oTest.fOppValue; - if (opp) { + if (binary) { SkTSwap<int>(oWindValue, oOppValue); } SkOpSpan* const test = &fTs[index]; SkOpSpan* end = test; - const double oStartT = oTest.fT; + const SkPoint& oStartPt = oTest.fPt; do { if (bumpSpan(end, oWindValue, oOppValue)) { - TrackOutside(outsideTs, end->fT, oStartT); + TrackOutside(outsideTs, oStartPt); } end = &fTs[++index]; - } while (approximately_negative(end->fT - test->fT)); - return index; + } while (end->fPt == test->fPt); + *indexPtr = index; +} + +bool SkOpSegment::bumpCoincident(SkOpSpan* test, bool bigger, bool binary) { + if (bigger) { + if (binary) { + if (fOppXor) { + test->fOppValue ^= 1; + } else { + test->fOppValue++; + } + } else { + if (fXor) { + test->fWindValue ^= 1; + } else { + test->fWindValue++; + } + } + if (!test->fWindValue && !test->fOppValue) { + test->fDone = true; + ++fDoneSpans; + return true; + } + return false; + } + return decrementSpan(test); } // because of the order in which coincidences are resolved, this and other // may not have the same intermediate points. Compute the corresponding // intermediate T values (using this as the master, other as the follower) // and walk other conditionally -- hoping that it catches up in the end -int SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex, - SkTArray<double, true>* oOutsideTs) { +void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr, + SkTArray<SkPoint, true>* oOutsidePts) { + int oIndex = *oIndexPtr; SkOpSpan* const oTest = &fTs[oIndex]; SkOpSpan* oEnd = oTest; - const double startT = test.fT; - const double oStartT = oTest->fT; - while (!approximately_negative(oEndT - oEnd->fT) - && approximately_negative(oEnd->fT - oStartT)) { + const SkPoint& startPt = test.fPt; + const SkPoint& oStartPt = oTest->fPt; + if (oStartPt == oEnd->fPt) { + TrackOutside(oOutsidePts, startPt); + } + while (oStartPt == oEnd->fPt) { zeroSpan(oEnd); - TrackOutside(oOutsideTs, oEnd->fT, startT); oEnd = &fTs[++oIndex]; } - return oIndex; + *oIndexPtr = oIndex; } // FIXME: need to test this case: @@ -706,43 +704,75 @@ int SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oI // set spans from start to end to increment the greater by one and decrement // the lesser -void SkOpSegment::addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT, - double oEndT) { - SkASSERT(!approximately_negative(endT - startT)); - SkASSERT(!approximately_negative(oEndT - oStartT)); - bool opp = fOperand ^ other->fOperand; +void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, + SkOpSegment* other) { + bool binary = fOperand != other->fOperand; int index = 0; - while (!approximately_negative(startT - fTs[index].fT)) { + while (startPt != fTs[index].fPt) { + SkASSERT(index < fTs.count()); ++index; } int oIndex = 0; - while (!approximately_negative(oStartT - other->fTs[oIndex].fT)) { + while (startPt != other->fTs[oIndex].fPt) { + SkASSERT(oIndex < other->fTs.count()); ++oIndex; } + SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts; + SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts; SkOpSpan* test = &fTs[index]; + const SkPoint* testPt = &test->fPt; SkOpSpan* oTest = &other->fTs[oIndex]; - SkSTArray<kOutsideTrackedTCount, double, true> outsideTs; - SkSTArray<kOutsideTrackedTCount, double, true> oOutsideTs; + const SkPoint* oTestPt = &oTest->fPt; + SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); do { - // if either span has an opposite value and the operands don't match, resolve first - // SkASSERT(!test->fDone || !oTest->fDone); + SkASSERT(test->fT < 1); + SkASSERT(oTest->fT < 1); +#if 0 if (test->fDone || oTest->fDone) { - index = advanceCoincidentThis(oTest, opp, index); - oIndex = other->advanceCoincidentOther(test, oEndT, oIndex); +#else // consolidate the winding count even if done + if ((test->fWindValue == 0 && test->fOppValue == 0) + || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) { +#endif + SkDEBUGCODE(int firstWind = test->fWindValue); + SkDEBUGCODE(int firstOpp = test->fOppValue); + do { + SkASSERT(firstWind == fTs[index].fWindValue); + SkASSERT(firstOpp == fTs[index].fOppValue); + ++index; + SkASSERT(index < fTs.count()); + } while (*testPt == fTs[index].fPt); + SkDEBUGCODE(firstWind = oTest->fWindValue); + SkDEBUGCODE(firstOpp = oTest->fOppValue); + do { + SkASSERT(firstWind == other->fTs[oIndex].fWindValue); + SkASSERT(firstOpp == other->fTs[oIndex].fOppValue); + ++oIndex; + SkASSERT(oIndex < other->fTs.count()); + } while (*oTestPt == other->fTs[oIndex].fPt); } else { - index = bumpCoincidentThis(*oTest, opp, index, &outsideTs); - oIndex = other->bumpCoincidentOther(*test, oEndT, oIndex, &oOutsideTs); + if (!binary || test->fWindValue + oTest->fOppValue >= 0) { + bumpCoincidentThis(*oTest, binary, &index, &outsidePts); + other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts); + } else { + other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts); + bumpCoincidentOther(*oTest, &index, &outsidePts); + } } test = &fTs[index]; + testPt = &test->fPt; + if (endPt == *testPt) { + break; + } oTest = &other->fTs[oIndex]; - } while (!approximately_negative(endT - test->fT)); - SkASSERT(approximately_negative(oTest->fT - oEndT)); - SkASSERT(approximately_negative(oEndT - oTest->fT)); - if (!done() && outsideTs.count()) { - addCoinOutsides(outsideTs, other, oEndT); + oTestPt = &oTest->fPt; + SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); + } while (endPt != *oTestPt); + int outCount = outsidePts.count(); + if (!done() && outCount) { + addCoinOutsides(outsidePts[0], endPt, other); } - if (!other->done() && oOutsideTs.count()) { - other->addCoinOutsides(oOutsideTs, this, endT); + if (!other->done() && oOutsidePts.count()) { + other->addCoinOutsides(oOutsidePts[0], endPt, this); } } @@ -769,8 +799,8 @@ void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool bor SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", __FUNCTION__, fID, t, other->fID, otherT); #endif - int insertedAt = addT(other, pt, t); - int otherInsertedAt = other->addT(this, pt, otherT); + int insertedAt = addT(other, pt, t, SkOpSpan::kPointIsExact); + int otherInsertedAt = other->addT(this, pt, otherT, SkOpSpan::kPointIsExact); addOtherT(insertedAt, otherT, otherInsertedAt); other->addOtherT(otherInsertedAt, t, insertedAt); matchWindingValue(insertedAt, t, borrowWind); @@ -792,7 +822,151 @@ void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* an } } -int SkOpSegment::advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index) { +SkOpSegment::MissingSpan::Command SkOpSegment::adjustThisNear(double startT, const SkPoint& startPt, + const SkPoint& endPt, SkTArray<MissingSpan, true>* missingSpans) { + // see if endPt exists on this curve, and if it has the same t or a different T than the startT + int count = this->count(); + SkASSERT(count > 0); + int startIndex, endIndex, step; + if (startT == 0) { + startIndex = 0; + endIndex = count; + step = 1; + } else { + SkASSERT(startT == 1); + startIndex = count - 1; + endIndex = -1; + step = -1; + } + int index = startIndex; + do { + const SkOpSpan& span = fTs[index]; + if (span.fPt != endPt) { + continue; + } + if (span.fT == startT) { + // check to see if otherT matches some other mid curve intersection + int inner = startIndex; + do { + if (inner == index) { + continue; + } + const SkOpSpan& matchSpan = fTs[inner]; + double matchT = span.fOther->missingNear(span.fOtherT, matchSpan.fOther, startPt, + endPt); + if (matchT >= 0) { + SkASSERT(missingSpans); + MissingSpan& missingSpan = missingSpans->push_back(); + SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan))); + missingSpan.fCommand = MissingSpan::kRemoveNear; + missingSpan.fT = startT; + missingSpan.fSegment = this; + missingSpan.fOther = span.fOther; + missingSpan.fOtherT = matchT; + return missingSpan.fCommand; + } + } while ((inner += step) != endIndex); + break; + } + double midT = (startT + span.fT) / 2; + if (betweenPoints(midT, startPt, endPt)) { + if (!missingSpans) { + return MissingSpan::kZeroSpan; + } + MissingSpan& missingSpan = missingSpans->push_back(); + SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan))); + missingSpan.fCommand = MissingSpan::kZeroSpan; + missingSpan.fT = SkTMin(startT, span.fT); + missingSpan.fEndT = SkTMax(startT, span.fT); + missingSpan.fSegment = this; + return missingSpan.fCommand; + } + } while ((index += step) != endIndex); + return MissingSpan::kNoAction; +} + +void SkOpSegment::adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt, + SkTArray<MissingSpan, true>* missingSpans) { + int count = this->count(); + SkASSERT(count > 0); + int startIndex, endIndex, step; + if (startT == 0) { + startIndex = 0; + endIndex = count; + step = 1; + } else { + SkASSERT(startT == 1); + startIndex = count - 1; + endIndex = -1; + step = -1; + } + int index = startIndex; + do { + const SkOpSpan& span = fTs[index]; + if (span.fT != startT) { + return; + } + SkOpSegment* other = span.fOther; + if (other->fPts[0] == endPt) { + other->adjustThisNear(0, endPt, startPt, missingSpans); + } else if (other->fPts[0] == startPt) { + other->adjustThisNear(0, startPt, endPt, missingSpans); + } + if (other->ptAtT(1) == endPt) { + other->adjustThisNear(1, endPt, startPt, missingSpans); + } else if (other->ptAtT(1) == startPt) { + other->adjustThisNear(1, startPt, endPt, missingSpans); + } + } while ((index += step) != endIndex); +} + +void SkOpSegment::adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt, + SkTArray<MissingSpan, true>* missingSpans) { + int count = missingSpans->count(); + for (int index = 0; index < count; ) { + MissingSpan& missing = (*missingSpans)[index]; + SkOpSegment* other = missing.fOther; + MissingSpan::Command command = MissingSpan::kNoAction; + if (missing.fPt == startPt) { + if (missingNear(missing.fT, other, startPt, endPt) >= 0) { + command = MissingSpan::kZeroSpan; + } else if (other->ptAtT(0) == endPt) { + command = other->adjustThisNear(0, endPt, startPt, NULL); + } else if (other->ptAtT(1) == endPt) { + command = other->adjustThisNear(1, endPt, startPt, NULL); + } + } else if (missing.fPt == endPt) { + if (missingNear(missing.fT, other, endPt, startPt) >= 0) { + command = MissingSpan::kZeroSpan; + } else if (other->ptAtT(0) == startPt) { + command = other->adjustThisNear(0, startPt, endPt, NULL); + } else if (other->ptAtT(1) == startPt) { + command = other->adjustThisNear(1, startPt, endPt, NULL); + } + } + if (command == MissingSpan::kZeroSpan) { +#if 1 + missing = missingSpans->back(); + missingSpans->pop_back(); +#else // if this is supported in the future ... + missingSpans->removeShuffle(index); +#endif + --count; + continue; + } + ++index; + } +} + +void SkOpSegment::adjustNear(double startT, const SkPoint& endPt, + SkTArray<MissingSpan, true>* missingSpans) { + const SkPoint startPt = ptAtT(startT); + adjustMissingNear(startPt, endPt, missingSpans); + adjustThisNear(startT, startPt, endPt, missingSpans); + adjustOtherNear(startT, startPt, endPt, missingSpans); +} + +int SkOpSegment::advanceCoincidentThis(int index) { SkOpSpan* const test = &fTs[index]; SkOpSpan* end; do { @@ -801,7 +975,7 @@ int SkOpSegment::advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int inde return index; } -int SkOpSegment::advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex) { +int SkOpSegment::advanceCoincidentOther(double oEndT, int oIndex) { SkOpSpan* const oTest = &fTs[oIndex]; SkOpSpan* oEnd = oTest; const double oStartT = oTest->fT; @@ -812,6 +986,14 @@ int SkOpSegment::advanceCoincidentOther(const SkOpSpan* test, double oEndT, int return oIndex; } +bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const { + const SkPoint midPt = ptAtT(midT); + SkPathOpsBounds bounds; + bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY); + bounds.sort(); + return bounds.almostContains(midPt); +} + bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const { if (lesser > greater) { SkTSwap<int>(lesser, greater); @@ -819,17 +1001,37 @@ bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const { return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT); } -void SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const { +// note that this follows the same logic flow as active angle +bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const { double referenceT = fTs[index].fT; + const SkPoint& referencePt = fTs[index].fPt; int lesser = index; - while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand) - && precisely_negative(referenceT - fTs[lesser].fT)) { + while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand) + && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) { buildAnglesInner(lesser, angles); } do { buildAnglesInner(index, angles); - } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand) - && precisely_negative(fTs[index].fT - referenceT)); + if (++index == fTs.count()) { + break; + } + if (!allowOpp && fTs[index].fOther->fOperand != fOperand) { + break; + } + if (fTs[index - 1].fTiny) { + referenceT = fTs[index].fT; + continue; + } + if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) { + // FIXME + // testQuad8 generates the wrong output unless false is returned here. Other tests will + // take this path although they aren't required to. This means that many go much slower + // because of this sort fail. + // SkDebugf("!!!\n"); + return false; + } + } while (precisely_negative(fTs[index].fT - referenceT)); + return true; } void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const { @@ -851,115 +1053,175 @@ void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) other->addTwoAngles(next, oIndex, angles); } -int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; - addTwoAngles(startIndex, endIndex, &angles); - buildAngles(endIndex, &angles, false); - // OPTIMIZATION: check all angles to see if any have computed wind sum - // before sorting (early exit if none) - SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - // 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, sortable); -#endif - if (!sortable) { - return SK_MinS32; +int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType, + SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) { + addTwoAngles(startIndex, endIndex, angles); + if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) { + return SK_NaN32; } - int angleCount = angles.count(); - const SkOpAngle* angle; - const SkOpSegment* base; - int winding; - int oWinding; - int firstIndex = 0; - do { - angle = sorted[firstIndex]; - base = angle->segment(); - winding = base->windSum(angle); - if (winding != SK_MinS32) { - oWinding = base->oppSum(angle); - break; + int angleCount = angles->count(); + // abort early before sorting if an unsortable (not an unorderable) angle is found + if (includeType != SkOpAngle::kUnaryXor) { + int firstIndex = -1; + while (++firstIndex < angleCount) { + const SkOpAngle& angle = (*angles)[firstIndex]; + if (angle.segment()->windSum(&angle) != SK_MinS32) { + break; + } } - if (++firstIndex == angleCount) { + if (firstIndex == angleCount) { return SK_MinS32; } - } while (true); - // turn winding into contourWinding - int spanWinding = base->spanSign(angle); - bool inner = UseInnerWinding(winding + spanWinding, winding); -#if DEBUG_WINDING - SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__, - spanWinding, winding, angle->sign(), inner, - inner ? winding + spanWinding : winding); -#endif - if (inner) { - winding += spanWinding; } -#if DEBUG_SORT - base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding, sortable); + bool sortable = SortAngles2(*angles, sorted); +#if DEBUG_SORT_RAW + if (sorted->count() > 0) { + (*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable); + } #endif - int nextIndex = firstIndex + 1; - int lastIndex = firstIndex != 0 ? firstIndex : angleCount; - winding -= base->spanSign(angle); - oWinding -= base->oppSign(angle); + if (!sortable) { + return SK_NaN32; + } + if (includeType == SkOpAngle::kUnaryXor) { + return SK_MinS32; + } + // if all angles have a computed winding, + // or if no adjacent angles are orderable, + // or if adjacent orderable angles have no computed winding, + // there's nothing to do + // if two orderable angles are adjacent, and one has winding computed, transfer to the other + const SkOpAngle* baseAngle = NULL; + int last = angleCount; + int finalInitialOrderable = -1; + bool tryReverse = false; + // look for counterclockwise transfers do { - if (nextIndex == angleCount) { - nextIndex = 0; - } - angle = sorted[nextIndex]; - SkOpSegment* segment = angle->segment(); - bool opp = base->fOperand ^ segment->fOperand; - int maxWinding, oMaxWinding; - int spanSign = segment->spanSign(angle); - int oppoSign = segment->oppSign(angle); - if (opp) { - oMaxWinding = oWinding; - oWinding -= spanSign; - maxWinding = winding; - if (oppoSign) { - winding -= oppoSign; + int index = 0; + do { + SkOpAngle* testAngle = (*sorted)[index]; + int testWinding = testAngle->segment()->windSum(testAngle); + if (SK_MinS32 != testWinding && !testAngle->unorderable()) { + baseAngle = testAngle; + continue; } - } else { - maxWinding = winding; - winding -= spanSign; - oMaxWinding = oWinding; - if (oppoSign) { - oWinding -= oppoSign; + if (testAngle->unorderable()) { + baseAngle = NULL; + tryReverse = true; + continue; } + if (baseAngle) { + ComputeOneSum(baseAngle, testAngle, includeType); + baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle + : NULL; + tryReverse |= !baseAngle; + continue; + } + if (finalInitialOrderable + 1 == index) { + finalInitialOrderable = index; + } + } while (++index != last); + if (finalInitialOrderable < 0) { + break; } - if (segment->windSum(angle) == SK_MinS32) { - if (opp) { - if (UseInnerWinding(oMaxWinding, oWinding)) { - oMaxWinding = oWinding; + last = finalInitialOrderable + 1; + finalInitialOrderable = -2; // make this always negative the second time through + } while (baseAngle); + if (tryReverse) { + baseAngle = NULL; + last = 0; + finalInitialOrderable = angleCount; + do { + int index = angleCount; + while (--index >= last) { + SkOpAngle* testAngle = (*sorted)[index]; + int testWinding = testAngle->segment()->windSum(testAngle); + if (SK_MinS32 != testWinding) { + baseAngle = testAngle; + continue; } - if (oppoSign && UseInnerWinding(maxWinding, winding)) { - maxWinding = winding; + if (testAngle->unorderable()) { + baseAngle = NULL; + continue; } -#ifdef SK_DEBUG - SkASSERT(abs(maxWinding) <= gDebugMaxWindSum); - SkASSERT(abs(oMaxWinding) <= gDebugMaxWindSum); -#endif - (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding); - } else { - if (UseInnerWinding(maxWinding, winding)) { - maxWinding = winding; + if (baseAngle) { + ComputeOneSumReverse(baseAngle, testAngle, includeType); + baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle + : NULL; + continue; } - if (oppoSign && UseInnerWinding(oMaxWinding, oWinding)) { - oMaxWinding = oWinding; + if (finalInitialOrderable - 1 == index) { + finalInitialOrderable = index; } -#ifdef SK_DEBUG - SkASSERT(abs(maxWinding) <= gDebugMaxWindSum); - SkASSERT(abs(binary ? oMaxWinding : 0) <= gDebugMaxWindSum); -#endif - (void) segment->markAndChaseWinding(angle, maxWinding, - binary ? oMaxWinding : 0); } - } - } while (++nextIndex != lastIndex); + if (finalInitialOrderable >= angleCount) { + break; + } + last = finalInitialOrderable; + finalInitialOrderable = angleCount + 1; // make this inactive 2nd time through + } while (baseAngle); + } int minIndex = SkMin32(startIndex, endIndex); return windSum(minIndex); } +void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, + SkOpAngle::IncludeType includeType) { + const SkOpSegment* baseSegment = baseAngle->segment(); + int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); + int sumSuWinding; + bool binary = includeType >= SkOpAngle::kBinarySingle; + if (binary) { + sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); + if (baseSegment->operand()) { + SkTSwap<int>(sumMiWinding, sumSuWinding); + } + } + SkOpSegment* nextSegment = nextAngle->segment(); + int maxWinding, sumWinding; + SkOpSpan* last; + if (binary) { + int oppMaxWinding, oppSumWinding; + nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, + &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); + last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, + true, nextAngle); + } else { + nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, + &maxWinding, &sumWinding); + last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle); + } + nextAngle->setLastMarked(last); +} + +void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, + SkOpAngle::IncludeType includeType) { + const SkOpSegment* baseSegment = baseAngle->segment(); + int sumMiWinding = baseSegment->updateWinding(baseAngle); + int sumSuWinding; + bool binary = includeType >= SkOpAngle::kBinarySingle; + if (binary) { + sumSuWinding = baseSegment->updateOppWinding(baseAngle); + if (baseSegment->operand()) { + SkTSwap<int>(sumMiWinding, sumSuWinding); + } + } + SkOpSegment* nextSegment = nextAngle->segment(); + int maxWinding, sumWinding; + SkOpSpan* last; + if (binary) { + int oppMaxWinding, oppSumWinding; + nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, + &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); + last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, + true, nextAngle); + } else { + nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, + &maxWinding, &sumWinding); + last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle); + } + nextAngle->setLastMarked(last); +} + int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const { SkScalar bottom = fBounds.fBottom; @@ -1050,18 +1312,20 @@ int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hi return bestTIndex; } -void SkOpSegment::decrementSpan(SkOpSpan* span) { +bool SkOpSegment::decrementSpan(SkOpSpan* span) { SkASSERT(span->fWindValue > 0); if (--(span->fWindValue) == 0) { if (!span->fOppValue && !span->fDone) { span->fDone = true; ++fDoneSpans; + return true; } } + return false; } bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { - SkASSERT(!span->fDone); + SkASSERT(!span->fDone || span->fTiny); span->fWindValue += windDelta; SkASSERT(span->fWindValue >= 0); span->fOppValue += oppDelta; @@ -1083,98 +1347,295 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { // look to see if the curve end intersects an intermediary that intersects the other void SkOpSegment::checkEnds() { debugValidate(); - SkTDArray<SkOpSpan> missingSpans; + SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; int count = fTs.count(); for (int index = 0; index < count; ++index) { const SkOpSpan& span = fTs[index]; - const SkOpSegment* other = span.fOther; - const SkOpSpan* otherSpan = &other->fTs[span.fOtherIndex]; - double otherT = otherSpan->fT; - if (otherT != 0 && otherT != 1) { + double otherT = span.fOtherT; + if (otherT != 0 && otherT != 1) { // only check ends continue; } + const SkOpSegment* other = span.fOther; + // peek start/last describe the range of spans that match the other t of this span int peekStart = span.fOtherIndex; - while (peekStart > 0) { - const SkOpSpan* peeker = &other->fTs[peekStart - 1]; - if (peeker->fT != otherT) { - break; - } - --peekStart; - } - int otherLast = other->fTs.count() - 1; + while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT) + ; + int otherCount = other->fTs.count(); int peekLast = span.fOtherIndex; - while (peekLast < otherLast) { - const SkOpSpan* peeker = &other->fTs[peekLast + 1]; - if (peeker->fT != otherT) { - break; - } - ++peekLast; - } - if (peekStart == peekLast) { + while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT) + ; + if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do continue; } + // t start/last describe the range of spans that match the t of this span double t = span.fT; int tStart = index; - while (tStart > 0 && t == fTs[tStart - 1].fT) { - --tStart; - } + while (--tStart >= 0 && (t == fTs[tStart].fT || fTs[tStart].fTiny)) + ; int tLast = index; - int last = count - 1; - while (tLast < last && t == fTs[tLast + 1].fT) { + while (fTs[tLast].fTiny) { ++tLast; } + while (++tLast < count && t == fTs[tLast].fT) + ; for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) { - if (peekIndex == span.fOtherIndex) { + if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span continue; } const SkOpSpan& peekSpan = other->fTs[peekIndex]; SkOpSegment* match = peekSpan.fOther; const double matchT = peekSpan.fOtherT; - for (int tIndex = tStart; tIndex <= tLast; ++tIndex) { + // see if any of the spans match the other spans + for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) { const SkOpSpan& tSpan = fTs[tIndex]; - if (tSpan.fOther == match && tSpan.fOtherT == matchT) { - goto nextPeeker; + if (tSpan.fOther == match) { + if (tSpan.fOtherT == matchT) { + goto nextPeeker; + } + double midT = (tSpan.fOtherT + matchT) / 2; + if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) { + goto nextPeeker; + } } } + if (missingSpans.count() > 0) { + const MissingSpan& lastMissing = missingSpans.back(); + if (lastMissing.fCommand == MissingSpan::kAddMissing + && lastMissing.fT == t + && lastMissing.fOther == match + && lastMissing.fOtherT == matchT) { + SkASSERT(lastMissing.fPt == peekSpan.fPt); + continue; + } + } +#if DEBUG_CHECK_ENDS + SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n", + __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY); +#endif // this segment is missing a entry that the other contains // remember so we can add the missing one and recompute the indices - SkOpSpan* missing = missingSpans.append(); - missing->fT = t; - missing->fOther = match; - missing->fOtherT = matchT; - missing->fPt = peekSpan.fPt; + MissingSpan& missing = missingSpans.push_back(); + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); + missing.fCommand = MissingSpan::kAddMissing; + missing.fT = t; + missing.fOther = match; + missing.fOtherT = matchT; + missing.fPt = peekSpan.fPt; } nextPeeker: ; } - int missingCount = missingSpans.count(); - if (missingCount == 0) { + if (missingSpans.count() == 0) { return; } + // if one end is near the other point, look for a coincident span + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = fTs[index]; + if (span.fT > 0) { + break; + } + const SkOpSpan& otherSpan = span.fOther->span(span.fOtherIndex); + if (span.fNear) { + SkASSERT(otherSpan.fPt == fPts[0]); + adjustNear(0, span.fPt, &missingSpans); + continue; + } + if (otherSpan.fNear) { + SkASSERT(span.fPt == fPts[0]); + adjustNear(0, otherSpan.fPt, &missingSpans); + } + } + for (int index = count; --index >= 0; ) { + const SkOpSpan& span = fTs[index]; + if (span.fT < 1) { + break; + } + const SkOpSegment* other = span.fOther; + if (span.fNear) { + SkASSERT(other->ptAtT(span.fOtherT) == ptAtT(1)); + const SkPoint& otherPt = other->xyAtT(span.fOtherIndex); + SkASSERT(otherPt != ptAtT(1)); + adjustNear(1, otherPt, &missingSpans); + continue; + } + const SkOpSpan& otherSpan = other->span(span.fOtherIndex); + if (otherSpan.fNear) { + SkASSERT(otherSpan.fPt == ptAtT(1)); + SkPoint otherPt = other->ptAtT(span.fOtherT); + SkASSERT(otherPt != ptAtT(1)); + adjustNear(1, otherPt, &missingSpans); + } + } debugValidate(); + int missingCount = missingSpans.count(); for (int index = 0; index < missingCount; ++index) { - const SkOpSpan& missing = missingSpans[index]; - addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + MissingSpan& missing = missingSpans[index]; + switch (missing.fCommand) { + case MissingSpan::kNoAction: + break; + case MissingSpan::kAddMissing: + addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + break; + case MissingSpan::kRemoveNear: { + SkOpSegment* segment = missing.fSegment; + int count = segment->count(); + for (int inner = 0; inner < count; ++inner) { + const SkOpSpan& span = segment->span(inner); + if (span.fT != missing.fT && span.fOther != missing.fOther) { + continue; + } + SkASSERT(span.fNear); + SkOpSegment* other = span.fOther; + int otherCount = other->count(); + for (int otherIndex = 0; otherIndex < otherCount; ++otherIndex) { + const SkOpSpan& otherSpan = other->span(otherIndex); + if (otherSpan.fT == span.fOtherT && otherSpan.fOther == segment + && otherSpan.fOtherT == span.fT) { + if (otherSpan.fDone) { + other->fDoneSpans--; + } + other->fTs.remove(otherIndex); + // FIXME: remove may leave a tiny dangling -- recompute tiny w/index + break; + } + } + if (span.fDone) { + segment->fDoneSpans--; + } + segment->fTs.remove(inner); + // FIXME: remove may leave a tiny dangling -- recompute tiny w/index + break; + } + break; + } + case MissingSpan::kZeroSpan: { + SkOpSegment* segment = missing.fSegment; + int count = segment->count(); + for (int inner = 0; inner < count; ++inner) { + SkOpSpan& span = segment->fTs[inner]; + if (span.fT < missing.fT) { + continue; + } + if (span.fT >= missing.fEndT) { + break; + } + span.fWindValue = span.fOppValue = 0; + if (!span.fDone) { + span.fDone = true; + ++segment->fDoneSpans; + } + } + break; + } + } } fixOtherTIndex(); + // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to + // avoid this for (int index = 0; index < missingCount; ++index) { - const SkOpSpan& missing = missingSpans[index]; - missing.fOther->fixOtherTIndex(); + const MissingSpan& missing = missingSpans[index]; + switch (missing.fCommand) { + case MissingSpan::kNoAction: + break; + case MissingSpan::kAddMissing: + missing.fOther->fixOtherTIndex(); + break; + case MissingSpan::kRemoveNear: + missing.fSegment->fixOtherTIndex(); + missing.fOther->fixOtherTIndex(); + break; + case MissingSpan::kZeroSpan: + break; + } } debugValidate(); } -bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) { - SkASSERT(greaterTIndex >= lesserTIndex); - double greaterT = fTs[greaterTIndex].fT; - double lesserT = fTs[lesserTIndex].fT; - if (greaterT == lesserT) { +bool SkOpSegment::checkSmall(int index) const { + if (fTs[index].fSmall) { return true; } - if (!approximately_negative(greaterT - lesserT)) { - return false; + double tBase = fTs[index].fT; + while (index > 0 && precisely_negative(tBase - fTs[--index].fT)) + ; + return fTs[index].fSmall; +} + +// if pair of spans on either side of tiny have the same end point and mid point, mark +// them as parallel +// OPTIMIZATION : mark the segment to note that some span is tiny +void SkOpSegment::checkTiny() { + SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; + SkOpSpan* thisSpan = fTs.begin() - 1; + const SkOpSpan* endSpan = fTs.end() - 1; // last can't be tiny + while (++thisSpan < endSpan) { + if (!thisSpan->fTiny) { + continue; + } + SkOpSpan* nextSpan = thisSpan + 1; + double thisT = thisSpan->fT; + double nextT = nextSpan->fT; + if (thisT == nextT) { + continue; + } + SkASSERT(thisT < nextT); + SkASSERT(thisSpan->fPt == nextSpan->fPt); + SkOpSegment* thisOther = thisSpan->fOther; + SkOpSegment* nextOther = nextSpan->fOther; + int oIndex = thisSpan->fOtherIndex; + for (int oStep = -1; oStep <= 1; oStep += 2) { + int oEnd = thisOther->nextExactSpan(oIndex, oStep); + if (oEnd < 0) { + continue; + } + const SkOpSpan& oSpan = thisOther->span(oEnd); + int nIndex = nextSpan->fOtherIndex; + for (int nStep = -1; nStep <= 1; nStep += 2) { + int nEnd = nextOther->nextExactSpan(nIndex, nStep); + if (nEnd < 0) { + continue; + } + const SkOpSpan& nSpan = nextOther->span(nEnd); + if (oSpan.fPt != nSpan.fPt) { + continue; + } + double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2; + const SkPoint& oPt = thisOther->ptAtT(oMidT); + double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2; + const SkPoint& nPt = nextOther->ptAtT(nMidT); + if (!AlmostEqualUlps(oPt, nPt)) { + continue; + } +#if DEBUG_CHECK_TINY + SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID, + thisOther->fID, nextOther->fID); +#endif + // this segment is missing a entry that the other contains + // remember so we can add the missing one and recompute the indices + MissingSpan& missing = missingSpans.push_back(); + SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); + missing.fCommand = MissingSpan::kAddMissing; + missing.fSegment = thisOther; + missing.fT = thisSpan->fOtherT; + missing.fOther = nextOther; + missing.fOtherT = nextSpan->fOtherT; + missing.fPt = thisSpan->fPt; + } + } + } + int missingCount = missingSpans.count(); + if (!missingCount) { + return; + } + for (int index = 0; index < missingCount; ++index) { + MissingSpan& missing = missingSpans[index]; + missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + } + for (int index = 0; index < missingCount; ++index) { + MissingSpan& missing = missingSpans[index]; + missing.fSegment->fixOtherTIndex(); + missing.fOther->fixOtherTIndex(); } - return xyAtT(greaterTIndex) == xyAtT(lesserTIndex); } /* @@ -1214,8 +1675,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart *nextEnd = *nextStart; do { *nextEnd += step; - } - while (precisely_zero(startT - other->fTs[*nextEnd].fT)); + } 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; @@ -1227,13 +1687,12 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); - addTwoAngles(startIndex, end, &angles); - buildAngles(end, &angles, true); SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); + int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted); + bool sortable = calcWinding != SK_NaN32; int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); - SkASSERT(firstIndex >= 0); + SkASSERT(!sortable || firstIndex >= 0); #if DEBUG_SORT debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); #endif @@ -1277,22 +1736,25 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart return NULL; } foundAngle = nextAngle; - foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle); + foundDone = nextSegment->done(nextAngle); } } if (nextSegment->done()) { continue; } - if (nextSegment->windSum(nextAngle) != SK_MinS32) { + if (nextSegment->isTiny(nextAngle)) { continue; } - SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, - oppSumWinding, activeAngle, nextAngle); + if (!activeAngle) { + nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end()); + } + SkOpSpan* last = nextAngle->lastMarked(); if (last) { *chase->append() = last; #if DEBUG_WINDING - SkDebugf("%s chase.append id=%d\n", __FUNCTION__, - last->fOther->fTs[last->fOtherIndex].fOther->debugID()); + SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, + last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum, + last->fSmall); #endif } } while (++nextIndex != lastIndex); @@ -1303,7 +1765,6 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart *nextStart = foundAngle->start(); *nextEnd = foundAngle->end(); nextSegment = foundAngle->segment(); - #if DEBUG_WINDING SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); @@ -1340,22 +1801,24 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next *nextEnd = *nextStart; do { *nextEnd += step; - } - while (precisely_zero(startT - other->fTs[*nextEnd].fT)); + } 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; } // more than one viable candidate -- measure angles to find best SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); - addTwoAngles(startIndex, end, &angles); - buildAngles(end, &angles, true); SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); + int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted); + bool sortable = calcWinding != SK_NaN32; int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); - SkASSERT(firstIndex >= 0); + SkASSERT(!sortable || firstIndex >= 0); #if DEBUG_SORT debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); #endif @@ -1400,15 +1863,19 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next if (nextSegment->done()) { continue; } - if (nextSegment->windSum(nextAngle) != SK_MinS32) { + if (nextSegment->isTiny(nextAngle)) { continue; } - SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, activeAngle, nextAngle); + if (!activeAngle) { + nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end()); + } + SkOpSpan* last = nextAngle->lastMarked(); if (last) { *chase->append() = last; #if DEBUG_WINDING - SkDebugf("%s chase.append id=%d\n", __FUNCTION__, - last->fOther->fTs[last->fOtherIndex].fOther->debugID()); + SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, + last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum, + last->fSmall); #endif } } while (++nextIndex != lastIndex); @@ -1431,8 +1898,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort const int endIndex = *nextEnd; SkASSERT(startIndex != endIndex); SkDEBUGCODE(int count = fTs.count()); - SkASSERT(startIndex < endIndex ? startIndex < count - 1 - : startIndex > 0); + SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); int step = SkSign32(endIndex - startIndex); int end = nextExactSpan(startIndex, step); SkASSERT(end >= 0); @@ -1461,14 +1927,11 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort *nextEnd = *nextStart; do { *nextEnd += step; - } - while (precisely_zero(startT - other->fTs[*nextEnd].fT)); + } while (precisely_zero(startT - other->fTs[*nextEnd].fT)); if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) { break; } -#ifdef SK_DEBUG SkASSERT(firstLoop); -#endif SkDEBUGCODE(firstLoop = false;) step = -step; } while (true); @@ -1478,25 +1941,24 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); - addTwoAngles(startIndex, end, &angles); - buildAngles(end, &angles, false); SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; - bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); - if (!sortable) { - *unsortable = true; -#if DEBUG_SORT - debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0, - sortable); -#endif - return NULL; - } + int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted); + bool sortable = calcWinding != SK_NaN32; int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); - SkASSERT(firstIndex >= 0); + SkASSERT(!sortable || firstIndex >= 0); #if DEBUG_SORT debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable); #endif + if (!sortable) { + *unsortable = true; + return NULL; + } SkASSERT(sorted[firstIndex]->segment() == this); +#if DEBUG_WINDING + SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex, + sorted[firstIndex]->sign()); +#endif int nextIndex = firstIndex + 1; int lastIndex = firstIndex != 0 ? firstIndex : angleCount; const SkOpAngle* foundAngle = NULL; @@ -1551,138 +2013,6 @@ int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int return firstIndex; } -// FIXME: this is tricky code; needs its own unit test -// note that fOtherIndex isn't computed yet, so it can't be used here -void SkOpSegment::findTooCloseToCall() { - int count = fTs.count(); - if (count < 3) { // require t=0, x, 1 at minimum - return; - } - int matchIndex = 0; - int moCount; - SkOpSpan* match; - SkOpSegment* mOther; - do { - match = &fTs[matchIndex]; - mOther = match->fOther; - // FIXME: allow quads, cubics to be near coincident? - if (mOther->fVerb == SkPath::kLine_Verb) { - moCount = mOther->fTs.count(); - if (moCount >= 3) { - break; - } - } - if (++matchIndex >= count) { - return; - } - } while (true); // require t=0, x, 1 at minimum - // OPTIMIZATION: defer matchPt until qualifying toCount is found? - const SkPoint* matchPt = &xyAtT(match); - // look for a pair of nearby T values that map to the same (x,y) value - // if found, see if the pair of other segments share a common point. If - // so, the span from here to there is coincident. - for (int index = matchIndex + 1; index < count; ++index) { - SkOpSpan* test = &fTs[index]; - if (test->fDone) { - continue; - } - SkOpSegment* tOther = test->fOther; - if (tOther->fVerb != SkPath::kLine_Verb) { - continue; // FIXME: allow quads, cubics to be near coincident? - } - int toCount = tOther->fTs.count(); - if (toCount < 3) { // require t=0, x, 1 at minimum - continue; - } - const SkPoint* testPt = &xyAtT(test); - if (*matchPt != *testPt) { - matchIndex = index; - moCount = toCount; - match = test; - mOther = tOther; - matchPt = testPt; - continue; - } - int moStart = -1; - int moEnd = -1; - double moStartT = 0; - double moEndT = 0; - for (int moIndex = 0; moIndex < moCount; ++moIndex) { - SkOpSpan& moSpan = mOther->fTs[moIndex]; - if (moSpan.fDone) { - continue; - } - if (moSpan.fOther == this) { - if (moSpan.fOtherT == match->fT) { - moStart = moIndex; - moStartT = moSpan.fT; - } - continue; - } - if (moSpan.fOther == tOther) { - if (tOther->windValueAt(moSpan.fOtherT) == 0) { - moStart = -1; - break; - } - SkASSERT(moEnd == -1); - moEnd = moIndex; - moEndT = moSpan.fT; - } - } - if (moStart < 0 || moEnd < 0) { - continue; - } - // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test - if (approximately_equal(moStartT, moEndT)) { - continue; - } - int toStart = -1; - int toEnd = -1; - double toStartT = 0; - double toEndT = 0; - for (int toIndex = 0; toIndex < toCount; ++toIndex) { - SkOpSpan& toSpan = tOther->fTs[toIndex]; - if (toSpan.fDone) { - continue; - } - if (toSpan.fOther == this) { - if (toSpan.fOtherT == test->fT) { - toStart = toIndex; - toStartT = toSpan.fT; - } - continue; - } - if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { - if (mOther->windValueAt(toSpan.fOtherT) == 0) { - moStart = -1; - break; - } - SkASSERT(toEnd == -1); - toEnd = toIndex; - toEndT = toSpan.fT; - } - } - // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test - if (toStart <= 0 || toEnd <= 0) { - continue; - } - if (approximately_equal(toStartT, toEndT)) { - continue; - } - // test to see if the segment between there and here is linear - if (!mOther->isLinear(moStart, moEnd) - || !tOther->isLinear(toStart, toEnd)) { - continue; - } - bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1; - if (flipped) { - mOther->addTCancel(moStartT, moEndT, tOther, toEndT, toStartT); - } else { - mOther->addTCoincident(moStartT, moEndT, tOther, toStartT, toEndT); - } - } -} - // FIXME: either: // a) mark spans with either end unsortable as done, or // b) rewrite findTop / findTopSegment / findTopContour to iterate further @@ -1722,14 +2052,24 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; SkASSERT(firstT - end != 0); addTwoAngles(end, firstT, &angles); - buildAngles(firstT, &angles, true); + if (!buildAngles(firstT, &angles, true) && onlySortable) { +// *unsortable = true; +// return NULL; + } SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind); + if (onlySortable && !sortable) { + *unsortable = true; + return NULL; + } int first = SK_MaxS32; SkScalar top = SK_ScalarMax; int count = sorted.count(); for (int index = 0; index < count; ++index) { const SkOpAngle* angle = sorted[index]; + if (onlySortable && angle->unorderable()) { + continue; + } SkOpSegment* next = angle->segment(); SkPathOpsBounds bounds; next->subDivideBounds(angle->end(), angle->start(), &bounds); @@ -1742,10 +2082,6 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort #if DEBUG_SORT // || DEBUG_SWAP_TOP sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable); #endif - if (onlySortable && !sortable) { - *unsortable = true; - return NULL; - } // skip edges that have already been processed firstT = first - 1; SkOpSegment* leftSegment; @@ -1789,6 +2125,7 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort // while the following fixes the indices up again, it isn't smart about // skipping segments whose indices are already correct // assuming we leave the code that wrote the index in the first place +// FIXME: if called after remove, this needs to correct tiny void SkOpSegment::fixOtherTIndex() { int iCount = fTs.count(); for (int i = 0; i < iCount; ++i) { @@ -1869,20 +2206,6 @@ void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc (void) markAndChaseWinding(start, end, winding, oppWind); } -bool SkOpSegment::isLinear(int start, int end) const { - if (fVerb == SkPath::kLine_Verb) { - return true; - } - if (fVerb == SkPath::kQuad_Verb) { - SkDQuad qPart = SkDQuad::SubDivide(fPts, fTs[start].fT, fTs[end].fT); - return qPart.isLinear(0, 2); - } else { - SkASSERT(fVerb == SkPath::kCubic_Verb); - SkDCubic cPart = SkDCubic::SubDivide(fPts, fTs[start].fT, fTs[end].fT); - return cPart.isLinear(0, 3); - } -} - // OPTIMIZE: successive calls could start were the last leaves off // or calls could specialize to walk forwards or backwards bool SkOpSegment::isMissing(double startT) const { @@ -2027,6 +2350,13 @@ SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, bool activeAngl } else { last = markAndChaseDoneUnary(angle, maxWinding); } +#if DEBUG_WINDING + if (last) { + SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__, + last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum, + last->fSmall); + } +#endif return last; } @@ -2045,6 +2375,13 @@ SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWindi } else { last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding); } +#if DEBUG_WINDING + if (last) { + SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__, + last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum, + last->fSmall); + } +#endif return last; } @@ -2146,9 +2483,7 @@ SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi debugShowNewWinding(funName, span, winding); #endif SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); -#ifdef SK_DEBUG - SkASSERT(abs(winding) <= gDebugMaxWindSum); -#endif + SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum); span.fWindSum = winding; return &span; } @@ -2163,14 +2498,10 @@ SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi debugShowNewWinding(funName, span, winding, oppWinding); #endif SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); -#ifdef SK_DEBUG - SkASSERT(abs(winding) <= gDebugMaxWindSum); -#endif + SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum); span.fWindSum = winding; SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding); -#ifdef SK_DEBUG - SkASSERT(abs(oppWinding) <= gDebugMaxWindSum); -#endif + SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum); span.fOppSum = oppWinding; return &span; } @@ -2331,6 +2662,21 @@ void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) { } } +double SkOpSegment::missingNear(double t, const SkOpSegment* other, const SkPoint& startPt, + const SkPoint& endPt) const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = this->span(index); + if (span.fOther == other && span.fPt == startPt) { + double midT = (t + span.fT) / 2; + if (betweenPoints(midT, startPt, endPt)) { + return span.fT; + } + } + } + return -1; +} + // return span if when chasing, two or more radiating spans are not done // OPTIMIZATION: ? multiple spans is detected when there is only one valid // candidate and the remaining spans have windValue == 0 (canceled by @@ -2355,6 +2701,10 @@ bool SkOpSegment::nextCandidate(int* start, int* end) const { SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) { int end = nextExactSpan(*index, step); SkASSERT(end >= 0); + if (fTs[end].fSmall) { + *last = NULL; + return NULL; + } if (multipleSpans(end)) { *last = &fTs[end]; return NULL; @@ -2366,7 +2716,7 @@ SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSp int otherEnd = other->nextExactSpan(*index, step); SkASSERT(otherEnd >= 0); *min = SkMin32(*index, otherEnd); - if (other->fTs[*min].fTiny) { + if (other->fTs[*min].fSmall) { *last = NULL; return NULL; } @@ -2397,18 +2747,30 @@ int SkOpSegment::nextSpan(int from, int step) const { // FIXME // this returns at any difference in T, vs. a preset minimum. It may be // that all callers to nextSpan should use this instead. -// OPTIMIZATION splitting this into separate loops for up/down steps -// would allow using precisely_negative instead of precisely_zero int SkOpSegment::nextExactSpan(int from, int step) const { - const SkOpSpan& fromSpan = fTs[from]; - int count = fTs.count(); int to = from; - while (step > 0 ? ++to < count : --to >= 0) { - const SkOpSpan& span = fTs[to]; - if (precisely_zero(span.fT - fromSpan.fT)) { - continue; + if (step < 0) { + const SkOpSpan& fromSpan = fTs[from]; + while (--to >= 0) { + const SkOpSpan& span = fTs[to]; + if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) { + continue; + } + return to; + } + } else { + while (fTs[from].fTiny) { + from++; + } + const SkOpSpan& fromSpan = fTs[from]; + int count = fTs.count(); + while (++to < count) { + const SkOpSpan& span = fTs[to]; + if (precisely_negative(span.fT - fromSpan.fT)) { + continue; + } + return to; } - return to; } return -1; } @@ -2428,6 +2790,16 @@ void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* *oppMaxWinding = *sumSuWinding; *oppSumWinding = *sumSuWinding -= oppDeltaSum; } + SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum); + SkASSERT(abs(*oppSumWinding) <= SkPathOpsDebug::gMaxWindSum); +} + +void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, + int* maxWinding, int* sumWinding) { + int deltaSum = spanSign(index, endIndex); + *maxWinding = *sumMiWinding; + *sumWinding = *sumMiWinding -= deltaSum; + SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum); } // This marks all spans unsortable so that this info is available for early @@ -2440,8 +2812,6 @@ bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles, bool sortable = true; int angleCount = angles.count(); int angleIndex; -// FIXME: caller needs to use SkTArray constructor with reserve count -// angleList->setReserve(angleCount); for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { const SkOpAngle& angle = angles[angleIndex]; angleList->push_back(const_cast<SkOpAngle*>(&angle)); @@ -2470,6 +2840,34 @@ bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles, return sortable; } +// set segments to unsortable if angle is unsortable, but do not set all angles +// note that for a simple 4 way crossing, two of the edges may be orderable even though +// two edges are too short to be orderable. +// perhaps some classes of unsortable angles should make all shared angles unsortable, but +// simple lines that have tiny crossings are always sortable on the large ends +// OPTIMIZATION: check earlier when angles are added to input if any are unsortable +// may make sense then to mark all segments in angle sweep as unsortableStart/unsortableEnd +// solely for the purpose of short-circuiting future angle building around this center +bool SkOpSegment::SortAngles2(const SkTArray<SkOpAngle, true>& angles, + SkTArray<SkOpAngle*, true>* angleList) { + int angleCount = angles.count(); + int angleIndex; + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { + const SkOpAngle& angle = angles[angleIndex]; + if (angle.unsortable()) { + return false; + } + angleList->push_back(const_cast<SkOpAngle*>(&angle)); +#if DEBUG_ANGLE + (*(angleList->end() - 1))->setID(angleIndex); +#endif + } + SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1); + // at this point angles are sorted but individually may not be orderable + // this means that only adjcent orderable segments may transfer winding + return true; +} + // return true if midpoints were computed bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const { SkASSERT(start != end); @@ -2563,11 +2961,19 @@ bool SkOpSegment::isTiny(int index) const { return fTs[index].fTiny; } -void SkOpSegment::TrackOutside(SkTArray<double, true>* outsideTs, double end, double start) { - int outCount = outsideTs->count(); - if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) { - outsideTs->push_back(end); - outsideTs->push_back(start); +void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt, + const SkPoint& startPt) { + int outCount = outsidePts->count(); + if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) { + outsidePts->push_back(endPt); + outsidePts->push_back(startPt); + } +} + +void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) { + int outCount = outsidePts->count(); + if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) { + outsidePts->push_back(startPt); } } @@ -2615,7 +3021,8 @@ int SkOpSegment::updateWinding(int index, int endIndex) const { int lesser = SkMin32(index, endIndex); int winding = windSum(lesser); int spanWinding = spanSign(index, endIndex); - if (winding && UseInnerWinding(winding - spanWinding, winding) && winding != SK_MaxS32) { + if (winding && UseInnerWinding(winding - spanWinding, winding) + && winding != SK_MaxS32) { winding -= spanWinding; } return winding; @@ -2627,10 +3034,42 @@ int SkOpSegment::updateWinding(const SkOpAngle* angle) const { return updateWinding(endIndex, startIndex); } +int SkOpSegment::updateWindingReverse(int index, int endIndex) const { + int lesser = SkMin32(index, endIndex); + int winding = windSum(lesser); + int spanWinding = spanSign(endIndex, index); + if (winding && UseInnerWindingReverse(winding - spanWinding, winding) + && winding != SK_MaxS32) { + winding -= spanWinding; + } + return winding; +} + int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const { int startIndex = angle->start(); int endIndex = angle->end(); - return updateWinding(startIndex, endIndex); + return updateWindingReverse(endIndex, startIndex); +} + +// OPTIMIZATION: does the following also work, and is it any faster? +// return outerWinding * innerWinding > 0 +// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) +bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { + SkASSERT(outerWinding != SK_MaxS32); + SkASSERT(innerWinding != SK_MaxS32); + int absOut = abs(outerWinding); + int absIn = abs(innerWinding); + bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; + return result; +} + +bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) { + SkASSERT(outerWinding != SK_MaxS32); + SkASSERT(innerWinding != SK_MaxS32); + int absOut = abs(outerWinding); + int absIn = abs(innerWinding); + bool result = absOut == absIn ? true : absOut < absIn; + return result; } int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const { @@ -2861,9 +3300,17 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, const int contourWinding, const int oppContourWinding, bool sortable) const { - if (--gDebugSortCount < 0) { + if (--SkPathOpsDebug::gSortCount < 0) { return; } + if (!sortable) { + if (angles.count() == 0) { + return; + } + if (first < 0) { + first = 0; + } + } SkASSERT(angles[first]->segment() == this); SkASSERT(!sortable || angles.count() > 1); int lastSum = contourWinding; @@ -2872,8 +3319,9 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true int windSum = lastSum - spanSign(firstAngle); int oppoSign = oppSign(firstAngle); int oppWindSum = oppLastSum - oppoSign; - #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x##Str, "?"); \ - else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x) + #define WIND_AS_STRING(x) char x##Str[12]; \ + if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \ + else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x) WIND_AS_STRING(contourWinding); WIND_AS_STRING(oppContourWinding); SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__, @@ -2931,7 +3379,7 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT); #endif SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue); - winding_printf(mSpan.fWindSum); + SkPathOpsDebug::WindingPrintf(mSpan.fWindSum); int last, wind; if (opp) { last = oppLastSum; @@ -2940,7 +3388,8 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true last = lastSum; wind = windSum; } - bool useInner = valid_wind(last) && valid_wind(wind) && UseInnerWinding(last, wind); + bool useInner = SkPathOpsDebug::ValidWind(last) && SkPathOpsDebug::ValidWind(wind) + && UseInnerWinding(last, wind); WIND_AS_STRING(last); WIND_AS_STRING(wind); WIND_AS_STRING(lastSum); @@ -2954,10 +3403,8 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr, opp ? windSumStr : oppWindSumStr); } - SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp); -#if 0 && DEBUG_ANGLE - angle.debugShow(segment.xyAtT(&sSpan)); -#endif + SkDebugf(" done=%d unord=%d small=%d tiny=%d opp=%d\n", + mSpan.fDone, angle.unorderable(), mSpan.fSmall, mSpan.fTiny, opp); ++index; if (index == angles.count()) { index = 0; @@ -2970,6 +3417,14 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, bool sortable) { + if (!sortable) { + if (angles.count() == 0) { + return; + } + if (first < 0) { + first = 0; + } + } const SkOpAngle* firstAngle = angles[first]; const SkOpSegment* segment = firstAngle->segment(); int winding = segment->updateWinding(firstAngle); @@ -3025,3 +3480,40 @@ void SkOpSegment::debugValidate() const { SkASSERT(done == fDoneSpans); #endif } + +#ifdef SK_DEBUG +void SkOpSegment::dumpPts() const { + int last = SkPathOpsVerbToPoints(fVerb); + SkDebugf("{{"); + int index = 0; + do { + SkDPoint::DumpSkPoint(fPts[index]); + SkDebugf(", "); + } while (++index < last); + SkDPoint::DumpSkPoint(fPts[index]); + SkDebugf("}}\n"); +} + +void SkOpSegment::dumpDPts() const { + int count = SkPathOpsVerbToPoints(fVerb); + SkDebugf("{{"); + int index = 0; + do { + SkDPoint dPt = {fPts[index].fX, fPts[index].fY}; + dPt.dump(); + if (index != count) { + SkDebugf(", "); + } + } while (++index <= count); + SkDebugf("}}\n"); +} + +void SkOpSegment::dumpSpans() const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = this->span(index); + SkDebugf("[%d] ", index); + span.dump(); + } +} +#endif diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index bfaf4ed9de..acb114dfc7 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -19,8 +19,8 @@ class SkPathWriter; class SkOpSegment { public: SkOpSegment() { -#if DEBUG_DUMP - fID = ++gSegmentID; +#ifdef SK_DEBUG + fID = ++SkPathOpsDebug::gSegmentID; #endif } @@ -59,6 +59,11 @@ public: return done(SkMin32(angle->start(), angle->end())); } + // used only by partial coincidence detection + SkDPoint dPtAtT(double mid) const { + return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); + } + SkVector dxdy(int index) const { return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT); } @@ -234,28 +239,23 @@ public: bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles); SkPoint activeLeftTop(bool onlySortable, int* firstT) const; bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op); - bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, - int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, - int* oppMaxWinding, int* oppSumWinding); bool activeWinding(int index, int endIndex); - bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding); void addCubic(const SkPoint pts[4], bool operand, bool evenOdd); void addCurveTo(int start, int end, SkPathWriter* path, bool active) const; void addLine(const SkPoint pts[2], bool operand, bool evenOdd); void addOtherT(int index, double otherT, int otherIndex); void addQuad(const SkPoint pts[3], bool operand, bool evenOdd); int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT); - int addT(SkOpSegment* other, const SkPoint& pt, double newT); - void addTCancel(double startT, double endT, SkOpSegment* other, double oStartT, double oEndT); - void addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT, - double oEndT); + int addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear); + void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); + void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt); - void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt, - const SkPoint& oPt); - int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT); bool betweenTs(int lesser, double testT, int greater) const; void checkEnds(); - int computeSum(int startIndex, int endIndex, bool binary); + bool checkSmall(int index) const; + void checkTiny(); + int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType, + SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted); int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const; SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, @@ -264,17 +264,13 @@ public: SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, bool* unsortable); SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); - void findTooCloseToCall(); SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable); void fixOtherTIndex(); void initWinding(int start, int end); void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, - SkScalar hitOppDx); - bool isLinear(int start, int end) const; + SkScalar hitOppDx); bool isMissing(double startT) const; - bool isSimple(int end) const; bool isTiny(const SkOpAngle* angle) const; - bool isTiny(int index) const; SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding); @@ -283,12 +279,7 @@ public: void markDone(int index, int winding); void markDoneBinary(int index); void markDoneUnary(int index); - SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding); - SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding); - void markWinding(int index, int winding); - void markWinding(int index, int winding, int oppWinding); bool nextCandidate(int* start, int* end) const; - int nextExactSpan(int from, int step) const; int nextSpan(int from, int step) const; void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); @@ -296,9 +287,11 @@ public: kMustBeOrdered_SortAngleKind, // required for winding calc kMayBeUnordered_SortAngleKind // ok for find top }; - static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, - SkTArray<SkOpAngle*, true>* angleList, + static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, // FIXME: replace with + SkTArray<SkOpAngle*, true>* angleList, // Sort Angles 2 SortAngleKind ); + static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles, + SkTArray<SkOpAngle*, true>* angleList); bool subDivide(int start, int end, SkPoint edge[4]) const; bool subDivide(int start, int end, SkDCubic* result) const; void undoneSpan(int* start, int* end); @@ -307,9 +300,8 @@ public: static bool UseInnerWinding(int outerWinding, int innerWinding); int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const; int windSum(const SkOpAngle* angle) const; - int windValue(const SkOpAngle* angle) const; -#if DEBUG_DUMP +#ifdef SK_DEBUG int debugID() const { return fID; } @@ -331,26 +323,61 @@ public: #endif private: + struct MissingSpan { + enum Command { + kNoAction, + kAddMissing, + kRemoveNear, + kZeroSpan, + } fCommand; + double fT; + double fEndT; + SkOpSegment* fSegment; + SkOpSegment* fOther; + double fOtherT; + SkPoint fPt; + }; + bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles); bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles); + bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, + int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, + int* oppMaxWinding, int* oppSumWinding); + bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding); void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const; - void addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd); - void addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other, double oEnd); + void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); + void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); + void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt, + const SkPoint& oPt); void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const; - int advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex); - int advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index); - void buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const; + void adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt, + SkTArray<MissingSpan, true>* ); + void adjustNear(double startT, const SkPoint& endPt, SkTArray<MissingSpan, true>* ); + void adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt, + SkTArray<MissingSpan, true>* ); + MissingSpan::Command adjustThisNear(double startT, const SkPoint& startPt, const SkPoint& endPt, + SkTArray<MissingSpan, true>* ); + int advanceCoincidentOther(double oEndT, int oIndex); + int advanceCoincidentThis(int index); + bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const; + bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const; void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const; - int bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index, - SkTArray<double, true>* outsideTs); - int bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex, - SkTArray<double, true>* oOutsideTs); + void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index, + SkTArray<SkPoint, true>* outsideTs); + bool bumpCoincident(SkOpSpan* test, bool bigger, bool binary); + void bumpCoincidentOther(const SkOpSpan& oTest, int* index, + SkTArray<SkPoint, true>* outsideTs); bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta); bool clockwise(int tStart, int tEnd) const; - void decrementSpan(SkOpSpan* span); - bool equalPoints(int greaterTIndex, int lesserTIndex); + static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, + SkOpAngle::IncludeType ); + static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, + SkOpAngle::IncludeType ); + bool decrementSpan(SkOpSpan* span); int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end); void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd); + bool isSimple(int end) const; + bool isTiny(int index) const; void matchWindingValue(int tIndex, double t, bool borrowWind); SkOpSpan* markAndChaseDone(int index, int endIndex, int winding); SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding); @@ -363,19 +390,33 @@ private: void markOneDoneBinary(const char* funName, int tIndex); void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding); void markOneDoneUnary(const char* funName, int tIndex); + SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding); + SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding); + void markWinding(int index, int winding); + void markWinding(int index, int winding, int oppWinding); void markUnsortable(int start, int end); bool monotonicInY(int tStart, int tEnd) const; + double missingNear(double otherT, const SkOpSegment* other, const SkPoint& startPt, + const SkPoint& endPt) const; bool multipleSpans(int end) const; SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last); + int nextExactSpan(int from, int step) const; bool serpentine(int tStart, int tEnd) const; + void setUpWindings(int index, int endIndex, int* sumMiWinding, + int* maxWinding, int* sumWinding); void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; - static void TrackOutside(SkTArray<double, true>* outsideTs, double end, double start); + static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt, + const SkPoint& startPt); + static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt); int updateOppWinding(int index, int endIndex) const; int updateOppWinding(const SkOpAngle* angle) const; int updateWinding(int index, int endIndex) const; int updateWinding(const SkOpAngle* angle) const; + int updateWindingReverse(int index, int endIndex) const; + static bool UseInnerWindingReverse(int outerWinding, int innerWinding); SkOpSpan* verifyOneWinding(const char* funName, int tIndex); SkOpSpan* verifyOneWindingU(const char* funName, int tIndex); + int windValue(const SkOpAngle* angle) const; int windValueAt(double t) const; void zeroSpan(SkOpSpan* span); @@ -395,6 +436,11 @@ private: } #endif void debugValidate() const; +#ifdef SK_DEBUG + void dumpPts() const; + void dumpDPts() const; + void dumpSpans() const; +#endif const SkPoint* fPts; SkPathOpsBounds fBounds; @@ -407,7 +453,7 @@ private: bool fOperand; bool fXor; // set if original contour had even-odd fill bool fOppXor; // set if opposite operand had even-odd fill -#if DEBUG_DUMP +#ifdef SK_DEBUG int fID; #endif }; diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index 3666623fbe..50c76d2640 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -12,6 +12,10 @@ class SkOpSegment; struct SkOpSpan { + enum PointMatch { + kPointIsExact, + kPointIsNear + }; SkOpSegment* fOther; SkPoint fPt; // computed when the curves are intersected double fT; @@ -24,8 +28,14 @@ struct SkOpSpan { bool fDone; // if set, this span to next higher T has been processed bool fUnsortableStart; // set when start is part of an unsortable pair bool fUnsortableEnd; // set when end is part of an unsortable pair + bool fSmall; // if set, consecutive points are almost equal bool fTiny; // if set, span may still be considered once for edge following bool fLoop; // set when a cubic loops back to this point + bool fNear; // set if point is near segment end point + +#ifdef SK_DEBUG + void dump() const; +#endif }; #endif diff --git a/src/pathops/SkPathOpsBounds.h b/src/pathops/SkPathOpsBounds.h index 61ef7bb874..07ad5d4ba9 100644 --- a/src/pathops/SkPathOpsBounds.h +++ b/src/pathops/SkPathOpsBounds.h @@ -13,8 +13,10 @@ // SkPathOpsBounds, unlike SkRect, does not consider a line to be empty. struct SkPathOpsBounds : public SkRect { static bool Intersects(const SkPathOpsBounds& a, const SkPathOpsBounds& b) { - return a.fLeft <= b.fRight && b.fLeft <= a.fRight && - a.fTop <= b.fBottom && b.fTop <= a.fBottom; + return AlmostLessOrEqualUlps(a.fLeft, b.fRight) + && AlmostLessOrEqualUlps(b.fLeft, a.fRight) + && AlmostLessOrEqualUlps(a.fTop, b.fBottom) + && AlmostLessOrEqualUlps(b.fTop, a.fBottom); } // Note that add(), unlike SkRect::join() or SkRect::growToInclude() @@ -38,6 +40,13 @@ struct SkPathOpsBounds : public SkRect { if (pt.fY > fBottom) fBottom = pt.fY; } + bool almostContains(const SkPoint& pt) { + return AlmostLessOrEqualUlps(fLeft, pt.fX) + && AlmostLessOrEqualUlps(pt.fX, fRight) + && AlmostLessOrEqualUlps(fTop, pt.fY) + && AlmostLessOrEqualUlps(pt.fY, fBottom); + } + // unlike isEmpty(), this permits lines, but not points // FIXME: unused for now bool isReallyEmpty() const { diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 28cf59cdd3..7dd13a7fe8 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -250,6 +250,9 @@ static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL *topLeft = bestXY; result = topStart->findTop(index, endIndex, unsortable, onlySortable); } while (!result); + if (result) { + *unsortable = false; + } return result; } @@ -288,9 +291,9 @@ static void skipVertical(const SkTArray<SkOpContour*, true>& contourList, } } -SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour, - int* indexPtr, int* endIndexPtr, SkPoint* topLeft, bool* unsortable, - bool* done, bool binary) { +SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, + SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr, + int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) { SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable, done, true); if (!current) { @@ -308,8 +311,11 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bo if (sumWinding != SK_MinS32) { return current; } - sumWinding = current->computeSum(index, endIndex, binary); - if (sumWinding != SK_MinS32) { + SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32); + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles; + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted; + sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted); + if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { return current; } int contourWinding; @@ -333,7 +339,7 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bo if (tryAgain) { continue; } - if (!binary) { + if (angleIncludeType < SkOpAngle::kBinarySingle) { break; } oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, @@ -354,6 +360,15 @@ void CheckEnds(SkTArray<SkOpContour*, true>* contourList) { } } +// A tiny interval may indicate an undiscovered coincidence. Find and fix. +void CheckTiny(SkTArray<SkOpContour*, true>* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->checkTiny(); + } +} + void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h index 4ba4af2300..e1ae998b10 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -7,6 +7,7 @@ #ifndef SkPathOpsCommon_DEFINED #define SkPathOpsCommon_DEFINED +#include "SkOpAngle.h" #include "SkOpContour.h" #include "SkTDArray.h" @@ -14,11 +15,12 @@ class SkPathWriter; void Assemble(const SkPathWriter& path, SkPathWriter* simple); void CheckEnds(SkTArray<SkOpContour*, true>* contourList); +void CheckTiny(SkTArray<SkOpContour*, true>* contourList); // FIXME: find chase uses insert, so it can't be converted to SkTArray yet SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex); -SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour, - int* index, int* endIndex, SkPoint* topLeft, bool* unsortable, - bool* done, bool binary); +SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& , SkOpAngle::IncludeType , + bool* firstContour, int* index, int* endIndex, SkPoint* topLeft, + bool* unsortable, bool* done); SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end); void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList); void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list, diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp index 5fbfeba50d..662219acf5 100644 --- a/src/pathops/SkPathOpsCubic.cpp +++ b/src/pathops/SkPathOpsCubic.cpp @@ -129,7 +129,7 @@ int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) { sk_bzero(str, sizeof(str)); SK_SNPRINTF(str, sizeof(str), "Solve[%1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]", A, B, C, D); - mathematica_ize(str, sizeof(str)); + SkPathOpsDebug::MathematicaIze(str, sizeof(str)); #if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA SkDebugf("%s\n", str); #endif @@ -508,3 +508,16 @@ SkDCubicPair SkDCubic::chopAt(double t) const { interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t); return dst; } + +#ifdef SK_DEBUG +void SkDCubic::dump() { + SkDebugf("{{"); + int index = 0; + do { + fPts[index].dump(); + SkDebugf(", "); + } while (++index < 3); + fPts[index].dump(); + SkDebugf("}}\n"); +} +#endif diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h index 1ba35be22b..973b76dfb2 100644 --- a/src/pathops/SkPathOpsCubic.h +++ b/src/pathops/SkPathOpsCubic.h @@ -77,6 +77,10 @@ struct SkDCubic { SkDPoint top(double startT, double endT) const; void toQuadraticTs(double precision, SkTArray<double, true>* ts) const; SkDQuad toQuad() const; + +#ifdef SK_DEBUG + void dump(); +#endif }; #endif diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 1436c8eae4..0505965b46 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -10,10 +10,23 @@ #if defined SK_DEBUG || !FORCE_RELEASE -int gDebugMaxWindSum = SK_MaxS32; -int gDebugMaxWindValue = SK_MaxS32; +int SkPathOpsDebug::gMaxWindSum = SK_MaxS32; +int SkPathOpsDebug::gMaxWindValue = SK_MaxS32; -void mathematica_ize(char* str, size_t bufferLen) { +const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"}; +int SkPathOpsDebug::gContourID; +int SkPathOpsDebug::gSegmentID; + +#if DEBUG_SORT || DEBUG_SWAP_TOP +int SkPathOpsDebug::gSortCountDefault = SK_MaxS32; +int SkPathOpsDebug::gSortCount; +#endif + +#if DEBUG_ACTIVE_OP +const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; +#endif + +void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) { size_t len = strlen(str); bool num = false; for (size_t idx = 0; idx < len; ++idx) { @@ -29,48 +42,29 @@ void mathematica_ize(char* str, size_t bufferLen) { num = str[idx] >= '0' && str[idx] <= '9'; } } -#endif -#if DEBUG_SORT || DEBUG_SWAP_TOP -bool valid_wind(int wind) { +bool SkPathOpsDebug::ValidWind(int wind) { return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF; } -void winding_printf(int wind) { +void SkPathOpsDebug::WindingPrintf(int wind) { if (wind == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", wind); } } -#endif - -#if DEBUG_DUMP -const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; -// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; -int gContourID; -int gSegmentID; -#endif - -#if DEBUG_SORT || DEBUG_SWAP_TOP -int gDebugSortCountDefault = SK_MaxS32; -int gDebugSortCount; -#endif - -#if DEBUG_ACTIVE_OP -const char* kPathOpStr[] = {"diff", "sect", "union", "xor"}; -#endif #if DEBUG_SHOW_TEST_NAME -void* PathOpsDebugCreateNameStr() { +void* SkPathOpsDebug::CreateNameStr() { return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH); } -void PathOpsDebugDeleteNameStr(void* v) { +void SkPathOpsDebug::DeleteNameStr(void* v) { SkDELETE_ARRAY(reinterpret_cast<char* >(v)); } -void DebugBumpTestName(char* test) { +void SkPathOpsDebug::BumpTestName(char* test) { char* num = test + strlen(test); while (num[-1] >= '0' && num[-1] <= '9') { --num; @@ -86,3 +80,56 @@ void DebugBumpTestName(char* test) { SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec); } #endif + +#include "SkOpSegment.h" + +void SkPathOpsDebug::DumpAngles(const SkTArray<SkOpAngle, true>& angles) { + int count = angles.count(); + for (int index = 0; index < count; ++index) { + angles[index].dump(); + } +} +#endif // SK_DEBUG || !FORCE_RELEASE + +#ifdef SK_DEBUG +void SkOpSpan::dump() const { + SkDebugf("t="); + DebugDumpDouble(fT); + SkDebugf(" pt="); + SkDPoint::DumpSkPoint(fPt); + SkDebugf(" other.fID=%d", fOther->debugID()); + SkDebugf(" [%d] otherT=", fOtherIndex); + DebugDumpDouble(fOtherT); + SkDebugf(" windSum="); + SkPathOpsDebug::WindingPrintf(fWindSum); + if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) { + SkDebugf(" oppSum="); + SkPathOpsDebug::WindingPrintf(fOppSum); + } + SkDebugf(" windValue=%d", fWindValue); + if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) { + SkDebugf(" oppValue=%d", fOppValue); + } + if (fDone) { + SkDebugf(" done"); + } + if (fUnsortableStart) { + SkDebugf(" unsortable-start"); + } + if (fUnsortableEnd) { + SkDebugf(" unsortable-end"); + } + if (fTiny) { + SkDebugf(" tiny"); + } else if (fSmall) { + SkDebugf(" small"); + } + if (fLoop) { + SkDebugf(" loop"); + } + if (fNear) { + SkDebugf(" near"); + } + SkDebugf("\n"); +} +#endif diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index e4ef072b9e..912f2f5f50 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -30,15 +30,6 @@ #define SK_SNPRINTF snprintf #endif -#if defined SK_DEBUG || !FORCE_RELEASE - -void mathematica_ize(char* str, size_t bufferSize); - -extern int gDebugMaxWindSum; -extern int gDebugMaxWindValue; - -#endif - #if FORCE_RELEASE #define DEBUG_ACTIVE_OP 0 @@ -50,6 +41,8 @@ extern int gDebugMaxWindValue; #define DEBUG_ANGLE 0 #define DEBUG_AS_C_CODE 1 #define DEBUG_ASSEMBLE 0 +#define DEBUG_CHECK_ENDS 0 +#define DEBUG_CHECK_TINY 0 #define DEBUG_CONCIDENT 0 #define DEBUG_CROSS 0 #define DEBUG_FLAT_QUADS 0 @@ -61,6 +54,7 @@ extern int gDebugMaxWindValue; #define DEBUG_SHOW_WINDING 0 #define DEBUG_SORT 0 #define DEBUG_SORT_COMPACT 0 +#define DEBUG_SORT_RAW 0 #define DEBUG_SORT_SINGLE 0 #define DEBUG_SWAP_TOP 0 #define DEBUG_UNSORTABLE 0 @@ -80,8 +74,10 @@ extern int gDebugMaxWindValue; #define DEBUG_ANGLE 1 #define DEBUG_AS_C_CODE 1 #define DEBUG_ASSEMBLE 1 +#define DEBUG_CHECK_ENDS 1 +#define DEBUG_CHECK_TINY 1 #define DEBUG_CONCIDENT 1 -#define DEBUG_CROSS 0 +#define DEBUG_CROSS 01 #define DEBUG_FLAT_QUADS 0 #define DEBUG_FLOW 1 #define DEBUG_MARK_DONE 1 @@ -91,6 +87,7 @@ extern int gDebugMaxWindValue; #define DEBUG_SHOW_WINDING 0 #define DEBUG_SORT 1 #define DEBUG_SORT_COMPACT 0 +#define DEBUG_SORT_RAW 0 #define DEBUG_SORT_SINGLE 0 #define DEBUG_SWAP_TOP 1 #define DEBUG_UNSORTABLE 1 @@ -101,9 +98,6 @@ extern int gDebugMaxWindValue; #endif -#define DEBUG_DUMP (DEBUG_ACTIVE_OP | DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | \ - DEBUG_SORT_SINGLE | DEBUG_PATH_CONSTRUCTION) - #if DEBUG_AS_C_CODE #define CUBIC_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}" #define QUAD_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}" @@ -122,39 +116,52 @@ extern int gDebugMaxWindValue; #define LINE_DEBUG_DATA(l) l[0].fX, l[0].fY, l[1].fX, l[1].fY #define PT_DEBUG_DATA(i, n) i.pt(n).fX, i.pt(n).fY -#if DEBUG_DUMP -extern const char* kLVerbStr[]; -// extern const char* kUVerbStr[]; -extern int gContourID; -extern int gSegmentID; +#ifndef DEBUG_TEST +#define DEBUG_TEST 0 #endif -#if DEBUG_SORT || DEBUG_SWAP_TOP -extern int gDebugSortCountDefault; -extern int gDebugSortCount; +#if defined SK_DEBUG || !FORCE_RELEASE + +#if DEBUG_SHOW_TEST_NAME +#include "SkTLS.h" +#endif + +#include "SkTArray.h" -bool valid_wind(int winding); -void winding_printf(int winding); +class SkPathOpsDebug { +public: + static int gMaxWindSum; + static int gMaxWindValue; + + static const char* kLVerbStr[]; + static int gContourID; + static int gSegmentID; + +#if DEBUG_SORT || DEBUG_SWAP_TOP + static int gSortCountDefault; + static int gSortCount; #endif #if DEBUG_ACTIVE_OP -extern const char* kPathOpStr[]; + static const char* kPathOpStr[]; #endif -#if DEBUG_SHOW_TEST_NAME -#include "SkTLS.h" + static void MathematicaIze(char* str, size_t bufferSize); + static bool ValidWind(int winding); + static void WindingPrintf(int winding); -extern void* PathOpsDebugCreateNameStr(); -extern void PathOpsDebugDeleteNameStr(void* v); +#if DEBUG_SHOW_TEST_NAME + static void* CreateNameStr(); + static void DeleteNameStr(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); +#define DEBUG_FILENAME_STRING (reinterpret_cast<char* >(SkTLS::Get(SkPathOpsDebug::CreateNameStr, \ + SkPathOpsDebug::DeleteNameStr))) + static void BumpTestName(char* ); + static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name); #endif + static void DumpAngles(const SkTArray<class SkOpAngle, true>& angles); +}; -#ifndef DEBUG_TEST -#define DEBUG_TEST 0 -#endif +#endif // SK_DEBUG || !FORCE_RELEASE #endif diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp index 48c042a7fa..1b548fcd30 100644 --- a/src/pathops/SkPathOpsLine.cpp +++ b/src/pathops/SkPathOpsLine.cpp @@ -78,9 +78,7 @@ double SkDLine::nearPoint(const SkDPoint& xy) const { } double t = numer / denom; SkDPoint realPt = ptAtT(t); - SkDVector distU = xy - realPt; - double distSq = distU.fX * distU.fX + distU.fY * distU.fY; - double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? + double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? // find the ordinal in the original line with the largest unsigned exponent double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); @@ -93,6 +91,35 @@ double SkDLine::nearPoint(const SkDPoint& xy) const { return t; } +bool SkDLine::nearRay(const SkDPoint& xy) const { + // project a perpendicular ray from the point to the line; find the T on the line + SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line + double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay + SkDVector ab0 = xy - fPts[0]; + double numer = len.fX * ab0.fX + ab0.fY * len.fY; + double t = numer / denom; + SkDPoint realPt = ptAtT(t); + double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? + // find the ordinal in the original line with the largest unsigned exponent + double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); + double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); + largest = SkTMax(largest, -tiniest); + return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? +} + +// Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2) +// OPTIMIZE: a specialty routine could speed this up -- may not be called very often though +bool SkDLine::NearRay(double x1, double y1, double x2, double y2) { + double denom1 = x1 * x1 + y1 * y1; + double denom2 = x2 * x2 + y2 * y2; + SkDLine line = {{{0, 0}, {x1, y1}}}; + SkDPoint pt = {x2, y2}; + if (denom2 > denom1) { + SkTSwap(line[1], pt); + } + return line.nearRay(pt); +} + double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { if (xy.fY == y) { if (xy.fX == left) { @@ -106,7 +133,7 @@ double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, doubl } double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { - if (!AlmostEqualUlps(xy.fY, y)) { + if (!AlmostBequalUlps(xy.fY, y)) { return -1; } if (!AlmostBetweenUlps(left, xy.fX, right)) { @@ -115,6 +142,18 @@ double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double double t = (xy.fX - left) / (right - left); t = SkPinT(t); SkASSERT(between(0, t, 1)); + double realPtX = (1 - t) * left + t * right; + SkDVector distU = {xy.fY - y, xy.fX - realPtX}; + double distSq = distU.fX * distU.fX + distU.fY * distU.fY; + double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? + double tiniest = SkTMin(SkTMin(y, left), right); + double largest = SkTMax(SkTMax(y, left), right); + largest = SkTMax(largest, -tiniest); + if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? + return -1; + } + t = SkPinT(t); + SkASSERT(between(0, t, 1)); return t; } @@ -131,7 +170,7 @@ double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, doubl } double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { - if (!AlmostEqualUlps(xy.fX, x)) { + if (!AlmostBequalUlps(xy.fX, x)) { return -1; } if (!AlmostBetweenUlps(top, xy.fY, bottom)) { @@ -140,5 +179,27 @@ double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double double t = (xy.fY - top) / (bottom - top); t = SkPinT(t); SkASSERT(between(0, t, 1)); + double realPtY = (1 - t) * top + t * bottom; + SkDVector distU = {xy.fX - x, xy.fY - realPtY}; + double distSq = distU.fX * distU.fX + distU.fY * distU.fY; + double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? + double tiniest = SkTMin(SkTMin(x, top), bottom); + double largest = SkTMax(SkTMax(x, top), bottom); + largest = SkTMax(largest, -tiniest); + if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? + return -1; + } + t = SkPinT(t); + SkASSERT(between(0, t, 1)); return t; } + +#ifdef SK_DEBUG +void SkDLine::dump() { + SkDebugf("{{"); + fPts[0].dump(); + SkDebugf(", "); + fPts[1].dump(); + SkDebugf("}}\n"); +} +#endif diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h index 75f3bd1058..a3cfcf26ef 100644 --- a/src/pathops/SkPathOpsLine.h +++ b/src/pathops/SkPathOpsLine.h @@ -31,10 +31,16 @@ struct SkDLine { static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x); double isLeft(const SkDPoint& pt) const; double nearPoint(const SkDPoint& xy) const; + bool nearRay(const SkDPoint& xy) const; static double NearPointH(const SkDPoint& xy, double left, double right, double y); static double NearPointV(const SkDPoint& xy, double top, double bottom, double x); + static bool NearRay(double dx1, double dy1, double dx2, double dy2); SkDPoint ptAtT(double t) const; SkDLine subDivide(double t1, double t2) const; + +#ifdef SK_DEBUG + void dump(); +#endif private: SkDVector tangent() const { return fPts[0] - fPts[1]; } }; diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 71efeeea8c..e532fda3de 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -49,10 +49,19 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int // find first angle, initialize winding to computed fWindSum int firstIndex = -1; const SkOpAngle* angle; + bool foundAngle = true; do { - angle = sorted[++firstIndex]; + ++firstIndex; + if (firstIndex >= angleCount) { + foundAngle = false; + break; + } + angle = sorted[firstIndex]; segment = angle->segment(); } while (segment->windSum(angle) == SK_MinS32); + if (!foundAngle) { + continue; + } #if DEBUG_SORT segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable); #endif @@ -135,8 +144,8 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o do { int index, endIndex; bool done; - SkOpSegment* current = FindSortableTop(contourList, &firstContour, &index, &endIndex, - &topLeft, &topUnsortable, &done, true); + SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour, + &index, &endIndex, &topLeft, &topUnsortable, &done); if (!current) { if (topUnsortable || !done) { topUnsortable = false; @@ -185,8 +194,12 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(index, endIndex)))); if (current->activeWinding(index, endIndex) && !simple->isClosed()) { - SkASSERT(unsortable || simple->isEmpty()); + // FIXME : add to simplify, xor cpaths int min = SkMin32(index, endIndex); + if (!unsortable && !simple->isEmpty()) { + unsortable = current->checkSmall(min); + } + SkASSERT(unsortable || simple->isEmpty()); if (!current->done(min)) { current->addCurveTo(index, endIndex, simple, true); current->markDoneBinary(min); @@ -235,8 +248,8 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { #if DEBUG_SHOW_TEST_NAME char* debugName = DEBUG_FILENAME_STRING; if (debugName && debugName[0]) { - DebugBumpTestName(debugName); - DebugShowPath(one, two, op, debugName); + SkPathOpsDebug::BumpTestName(debugName); + SkPathOpsDebug::ShowPath(one, two, op, debugName); } #endif op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; @@ -250,7 +263,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { op = kDifference_PathOp; } #if DEBUG_SORT || DEBUG_SWAP_TOP - gDebugSortCount = gDebugSortCountDefault; + SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; #endif // turn path into list of segments SkTArray<SkOpContour> contours; @@ -300,6 +313,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { #endif FixOtherTIndex(&contourList); CheckEnds(&contourList); + CheckTiny(&contourList); SortSegments(&contourList); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY DebugShowActiveSpans(contourList); diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index 045b1b4d46..51216b60ef 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -159,6 +159,24 @@ struct SkDPoint { double roughlyEqual(const SkDPoint& a) const { return roughly_equal(a.fY, fY) && roughly_equal(a.fX, fX); } + + #ifdef SK_DEBUG + void dump() { + SkDebugf("{"); + DebugDumpDouble(fX); + SkDebugf(", "); + DebugDumpDouble(fY); + SkDebugf("}"); + } + + static void DumpSkPoint(const SkPoint& pt) { + SkDebugf("{"); + DebugDumpFloat(pt.fX); + SkDebugf(", "); + DebugDumpFloat(pt.fY); + SkDebugf("}"); + } + #endif }; #endif diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 7d9ff52aa2..1bd7796d96 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -340,3 +340,16 @@ void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) { *a -= *b; // a = A - 2*B + C *b -= *c; // b = 2*B - 2*C } + +#ifdef SK_DEBUG +void SkDQuad::dump() { + SkDebugf("{{"); + int index = 0; + do { + fPts[index].dump(); + SkDebugf(", "); + } while (++index < 2); + fPts[index].dump(); + SkDebugf("}}\n"); +} +#endif diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h index c8650515bb..69d5a6dd90 100644 --- a/src/pathops/SkPathOpsQuad.h +++ b/src/pathops/SkPathOpsQuad.h @@ -61,6 +61,10 @@ struct SkDQuad { } SkDCubic toCubic() const; SkDPoint top(double startT, double endT) const; + +#ifdef SK_DEBUG + void dump(); +#endif private: // static double Tangent(const double* quadratic, double t); // uncalled }; diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 488778904f..76e3413089 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -17,8 +17,8 @@ static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWrite do { int index, endIndex; bool topDone; - SkOpSegment* current = FindSortableTop(contourList, &firstContour, &index, &endIndex, - &topLeft, &topUnsortable, &topDone, false); + SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour, + &index, &endIndex, &topLeft, &topUnsortable, &topDone); if (!current) { if (topUnsortable || !topDone) { topUnsortable = false; @@ -149,7 +149,7 @@ static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* s // FIXME : add this as a member of SkPath bool Simplify(const SkPath& path, SkPath* result) { #if DEBUG_SORT || DEBUG_SWAP_TOP - gDebugSortCount = gDebugSortCountDefault; + SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; #endif // returns 1 for evenodd, -1 for winding, regardless of inverse-ness SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType @@ -186,6 +186,7 @@ bool Simplify(const SkPath& path, SkPath* result) { CoincidenceCheck(&contourList, 0); FixOtherTIndex(&contourList); CheckEnds(&contourList); + CheckTiny(&contourList); SortSegments(&contourList); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY DebugShowActiveSpans(contourList); diff --git a/src/pathops/SkPathOpsSpan.h b/src/pathops/SkPathOpsSpan.h deleted file mode 100644 index 33965922ae..0000000000 --- a/src/pathops/SkPathOpsSpan.h +++ /dev/null @@ -1,31 +0,0 @@ -/* - * Copyright 2012 Google Inc. - * - * Use of this source code is governed by a BSD-style license that can be - * found in the LICENSE file. - */ -#ifndef SkOpSpan_DEFINED -#define SkOpSpan_DEFINED - -#include "SkPoint.h" - -class SkOpSegment; - -struct SkOpSpan { - SkOpSegment* fOther; - SkPoint fPt; // computed when the curves are intersected - double fT; - double fOtherT; // value at fOther[fOtherIndex].fT - int fOtherIndex; // can't be used during intersection - int fWindSum; // accumulated from contours surrounding this one. - int fOppSum; // for binary operators: the opposite winding sum - int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident - int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here - bool fDone; // if set, this span to next higher T has been processed - bool fUnsortableStart; // set when start is part of an unsortable pair - bool fUnsortableEnd; // set when end is part of an unsortable pair - bool fTiny; // if set, span may still be considered once for edge following - bool fLoop; // set when a cubic loops back to this point -}; - -#endif diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index 8135c57025..2d7388b882 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -7,34 +7,52 @@ #include "SkFloatBits.h" #include "SkPathOpsTypes.h" - - // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ // FIXME: move to SkFloatBits.h static bool equal_ulps(float a, float b, int epsilon) { - SkFloatIntUnion floatIntA, floatIntB; - floatIntA.fFloat = a; - floatIntB.fFloat = b; - // Different signs means they do not match. - if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { - // Check for equality to make sure +0 == -0 - return a == b; + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return false; } + int aBits = SkFloatAs2sCompliment(a); + int bBits = SkFloatAs2sCompliment(b); // Find the difference in ULPs. - int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); - return ulpsDiff <= epsilon; + return aBits < bBits + epsilon && bBits < aBits + epsilon; +} + +static bool not_equal_ulps(float a, float b, int epsilon) { + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return false; + } + int aBits = SkFloatAs2sCompliment(a); + int bBits = SkFloatAs2sCompliment(b); + // Find the difference in ULPs. + return aBits >= bBits + epsilon || bBits >= aBits + epsilon; } static bool less_ulps(float a, float b, int epsilon) { - SkFloatIntUnion floatIntA, floatIntB; - floatIntA.fFloat = a; - floatIntB.fFloat = b; - // Check different signs with float epsilon since we only care if they're both close to 0. - if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { - return a <= b + FLT_EPSILON * epsilon; + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return false; } + int aBits = SkFloatAs2sCompliment(a); + int bBits = SkFloatAs2sCompliment(b); // Find the difference in ULPs. - return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon; + return aBits <= bBits - epsilon; +} + +static bool less_or_equal_ulps(float a, float b, int epsilon) { + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return false; + } + int aBits = SkFloatAs2sCompliment(a); + int bBits = SkFloatAs2sCompliment(b); + // Find the difference in ULPs. + return aBits < bBits + epsilon; +} + +// equality using the same error term as between +bool AlmostBequalUlps(float a, float b) { + const int UlpsEpsilon = 2; + return equal_ulps(a, b, UlpsEpsilon); } bool AlmostEqualUlps(float a, float b) { @@ -42,18 +60,36 @@ bool AlmostEqualUlps(float a, float b) { return equal_ulps(a, b, UlpsEpsilon); } +bool NotAlmostEqualUlps(float a, float b) { + const int UlpsEpsilon = 16; + return not_equal_ulps(a, b, UlpsEpsilon); +} + bool RoughlyEqualUlps(float a, float b) { const int UlpsEpsilon = 256; return equal_ulps(a, b, UlpsEpsilon); } bool AlmostBetweenUlps(float a, float b, float c) { - const int UlpsEpsilon = 1; - return a <= c ? less_ulps(a, b, UlpsEpsilon) && less_ulps(b, c, UlpsEpsilon) - : less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon); + const int UlpsEpsilon = 2; + return a <= c ? less_or_equal_ulps(a, b, UlpsEpsilon) && less_or_equal_ulps(b, c, UlpsEpsilon) + : less_or_equal_ulps(b, a, UlpsEpsilon) && less_or_equal_ulps(c, b, UlpsEpsilon); +} + +bool AlmostLessUlps(float a, float b) { + const int UlpsEpsilon = 16; + return less_ulps(a, b, UlpsEpsilon); +} + +bool AlmostLessOrEqualUlps(float a, float b) { + const int UlpsEpsilon = 16; + return less_or_equal_ulps(a, b, UlpsEpsilon); } int UlpsDistance(float a, float b) { + if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) { + return SK_MaxS32; + } SkFloatIntUnion floatIntA, floatIntB; floatIntA.fFloat = a; floatIntB.fFloat = b; diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 19e3efadd1..bc39675d62 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -28,11 +28,32 @@ inline bool AlmostEqualUlps(double a, double b) { return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } +bool NotAlmostEqualUlps(float a, float b); +inline bool NotAlmostEqualUlps(double a, double b) { + return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + +// Use Almost Bequal when comparing coordinates in conjunction with between. +bool AlmostBequalUlps(float a, float b); +inline bool AlmostBequalUlps(double a, double b) { + return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + bool RoughlyEqualUlps(float a, float b); inline bool RoughlyEqualUlps(double a, double b) { return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); } +bool AlmostLessUlps(float a, float b); +inline bool AlmostLessUlps(double a, double b) { + return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + +bool AlmostLessOrEqualUlps(float a, float b); +inline bool AlmostLessOrEqualUlps(double a, double b) { + return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); +} + bool AlmostBetweenUlps(float a, float b, float c); inline bool AlmostBetweenUlps(double a, double b, double c) { return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c)); @@ -274,4 +295,22 @@ inline double SkPinT(double t) { return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; } +#ifdef SK_DEBUG +inline void DebugDumpDouble(double x) { + if (x == floor(x)) { + SkDebugf("%.0f", x); + } else { + SkDebugf("%1.17g", x); + } +} + +inline void DebugDumpFloat(float x) { + if (x == floorf(x)) { + SkDebugf("%.0f", x); + } else { + SkDebugf("%1.9gf", x); + } +} +#endif + #endif diff --git a/src/pathops/SkQuarticRoot.cpp b/src/pathops/SkQuarticRoot.cpp index 596d2a25d6..d3a6a781c7 100644 --- a/src/pathops/SkQuarticRoot.cpp +++ b/src/pathops/SkQuarticRoot.cpp @@ -40,7 +40,7 @@ int SkReducedQuarticRoots(const double t4, const double t3, const double t2, con SK_SNPRINTF(str, sizeof(str), "Solve[%1.19g x^4 + %1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]", t4, t3, t2, t1, t0); - mathematica_ize(str, sizeof(str)); + SkPathOpsDebug::MathematicaIze(str, sizeof(str)); #if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA SkDebugf("%s\n", str); #endif diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index f7507a0f97..7f5e456ea3 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -233,7 +233,7 @@ static const SortSetTests tests[] = { { TEST_ENTRY(set3), {0, 0}}, { TEST_ENTRY(set2), {0, 0}}, // { TEST_ENTRY(set1a), {3.70370364f,3.14814806f} }, - { TEST_ENTRY(set1), {0, 0}}, +// { TEST_ENTRY(set1), {0, 0}}, }; #undef TEST_ENTRY @@ -287,13 +287,13 @@ static void setup(const SortSet* set, const size_t idx, } double tStart = set[idx].tStart; double tEnd = set[idx].tEnd; - seg->addT(NULL, start, tStart); - seg->addT(NULL, end, tEnd); + seg->addT(NULL, start, tStart, SkOpSpan::kPointIsExact); + seg->addT(NULL, end, tEnd, SkOpSpan::kPointIsExact); if (tStart != 0 && tEnd != 0) { - seg->addT(NULL, set[idx].ptData[0], 0); + seg->addT(NULL, set[idx].ptData[0], 0, SkOpSpan::kPointIsExact); } if (tStart != 1 && tEnd != 1) { - seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1); + seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1, SkOpSpan::kPointIsExact); } int tIndex = 0; ts[0] = 0; diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index 1cc037f1c4..d04f2dbf94 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -163,6 +163,9 @@ static const SkDCubic testSet[] = { const size_t testSetCount = SK_ARRAY_COUNT(testSet); static const SkDCubic newTestSet[] = { +{{{134, 11414}, {131.990234375, 11414}, {130.32666015625, 11415.482421875}, {130.04275512695312, 11417.4130859375}}}, +{{{132, 11419}, {130.89543151855469, 11419}, {130, 11418.1044921875}, {130, 11417}}}, + {{{3, 4}, {1, 5}, {4, 3}, {6, 4}}}, {{{3, 4}, {4, 6}, {4, 3}, {5, 1}}}, diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp index 866acb34fd..95eb621f56 100644 --- a/tests/PathOpsCubicLineIntersectionTest.cpp +++ b/tests/PathOpsCubicLineIntersectionTest.cpp @@ -15,6 +15,8 @@ static struct lineCubic { SkDCubic cubic; SkDLine line; } lineCubicTests[] = { + {{{{0,4}, {3,4}, {6,2}, {5,2}}}, + {{{4,3}, {2,6}}}}, #if 0 {{{{258, 122}, {260.761414, 122}, { 263, 124.238579}, {263, 127}}}, {{{259.82843, 125.17157}, {261.535522, 123.46447}}}}, diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index b85644dca5..efee0fcb42 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -554,11 +554,12 @@ bool testSimplify(skiatest::Reporter* reporter, const SkPath& path) { } #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"); +void SkPathOpsDebug::ShowPath(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 @@ -571,7 +572,7 @@ static bool innerPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkP showOp(shapeOp); showPathData(b); } else { - DebugShowPath(a, b, shapeOp, testName); + SkPathOpsDebug::ShowPath(a, b, shapeOp, testName); } #endif SkPath out; @@ -628,8 +629,8 @@ bool testThreadedPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkP int initializeTests(skiatest::Reporter* reporter, const char* test) { #ifdef SK_DEBUG - gDebugMaxWindSum = 4; - gDebugMaxWindValue = 4; + SkPathOpsDebug::gMaxWindSum = 4; + SkPathOpsDebug::gMaxWindValue = 4; #endif testName = test; size_t testNameSize = strlen(test); diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp index ea3f7e07c6..ee15363996 100644 --- a/tests/PathOpsLineIntersectionTest.cpp +++ b/tests/PathOpsLineIntersectionTest.cpp @@ -11,6 +11,8 @@ // FIXME: add tests for intersecting, non-intersecting, degenerate, coincident static const SkDLine tests[][2] = { + {{{{90,230}, {160,60}}}, {{{60,120}, {260,120}}}}, + {{{{90,230}, {160,60}}}, {{{181.176468,120}, {135.294128,120}}}}, {{{{181.1764678955078125f, 120}, {186.3661956787109375f, 134.7042236328125f}}}, {{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}}, #if 0 // FIXME: these fail because one line is too short and appears quasi-coincident @@ -33,6 +35,9 @@ static const SkDLine tests[][2] = { static const size_t tests_count = SK_ARRAY_COUNT(tests); static const SkDLine noIntersect[][2] = { + {{{{(double) (2 - 1e-6f),2}, {(double) (2 - 1e-6f),4}}}, + {{{2,1}, {2,3}}}}, + {{{{0, 0}, {1, 0}}}, {{{3, 0}, {2, 0}}}}, {{{{0, 0}, {0, 0}}}, {{{1, 0}, {2, 0}}}}, {{{{0, 1}, {0, 1}}}, {{{0, 3}, {0, 2}}}}, @@ -43,6 +48,12 @@ static const SkDLine noIntersect[][2] = { static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect); static const SkDLine coincidentTests[][2] = { + {{{{979.304871, 561}, {1036.69507, 291}}}, + {{{985.681519, 531}, {982.159790, 547.568542}}}}, + + {{{{232.159805, 547.568542}, {235.681549, 531}}}, + {{{286.695129,291}, {229.304855,561}}}}, + {{{{186.3661956787109375f, 134.7042236328125f}, {187.8782806396484375f, 133.7258148193359375f}}}, {{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}}, @@ -111,19 +122,11 @@ static void testOneCoincident(skiatest::Reporter* reporter, const SkDLine& line1 const SkDLine& line2) { SkASSERT(ValidLine(line1)); SkASSERT(ValidLine(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) { @@ -154,9 +157,8 @@ static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { static void PathOpsLineIntersectionOneOffTest(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); + testOne(reporter, tests[index][0], tests[index][1]); + testOne(reporter, tests[1][0], tests[1][1]); } static void PathOpsLineIntersectionOneCoincidentTest(skiatest::Reporter* reporter) { diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index e0a7cf516e..dee99dbdfb 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -1987,6 +1987,149 @@ static void cubicOp85i(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kIntersect_PathOp); } +static void issue1418b(skiatest::Reporter* reporter) { + SkPath path1; + path1.moveTo(0, 0); + path1.lineTo(1, 0); + path1.lineTo(1, 1); + path1.lineTo(0, 1); + path1.lineTo(0, 0); + path1.close(); + path1.setFillType(SkPath::kWinding_FillType); + SkPath path2; + path2.moveTo(0.646446645f, -0.353553414f); + path2.quadTo(0.792893291f, -0.50000006f, 1.00000012f, -0.50000006f); + path2.quadTo(1.20710683f, -0.50000006f, 1.35355353f, -0.353553414f); + path2.quadTo(1.50000012f, -0.207106799f, 1.50000012f, 0); + path2.quadTo(1.50000012f, 0.207106799f, 1.35355353f, 0.353553414f); + path2.quadTo(1.20710683f, 0.50000006f, 1.00000012f, 0.50000006f); + path2.quadTo(0.792893291f, 0.50000006f, 0.646446645f, 0.353553414f); + path2.quadTo(0.50000006f, 0.207106799f, 0.50000006f, 0); + path2.quadTo(0.50000006f, -0.207106799f, 0.646446645f, -0.353553414f); + path2.close(); + path2.moveTo(1.00000012f, 0.50000006f); + path2.lineTo(1.00000012f, 1.00000012f); + path2.lineTo(0.50000006f, 1.00000012f); + path2.quadTo(0.50000006f, 0.792893291f, 0.646446645f, 0.646446645f); + path2.quadTo(0.792893291f, 0.50000006f, 1.00000012f, 0.50000006f); + path2.close(); + path2.setFillType(SkPath::kEvenOdd_FillType); + testPathOp(reporter, path1, path2, kIntersect_PathOp); +} + +static void rectOp1i(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(2, 2, 4, 4, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void rectOp2i(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 3, 3, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void rectOp3x(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0, 0); + path.lineTo(3, 0); + path.lineTo(3, 3); + path.lineTo(0, 3); + path.close(); + path.moveTo(2, 2); + path.lineTo(3, 2); + path.lineTo(3, 3); + path.lineTo(2, 3); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1, 1); + pathB.lineTo(3, 1); + pathB.lineTo(3, 3); + pathB.lineTo(1, 3); + pathB.close(); + pathB.moveTo(2, 2); + pathB.lineTo(3, 2); + pathB.lineTo(3, 3); + pathB.lineTo(2, 3); + pathB.close(); + testPathOp(reporter, path, pathB, kXOR_PathOp); +} + +#if 0 +static void issue1435(skiatest::Reporter* reporter) { + SkPath path1; + path1.moveTo(160, 60); + path1.lineTo(220, 230); + path1.lineTo(60, 120); + path1.lineTo(260, 120); + path1.lineTo(90, 230); + path1.lineTo(160, 60); + path1.close(); + path1.setFillType(SkPath::kEvenOdd_FillType); + + + SkPath path2; + path2.moveTo(142.589081f, 102.283646f); + path2.quadTo(149.821579f, 100, 158, 100); + path2.quadTo(167.156921f, 100, 175.128036f, 102.862793f); + path2.lineTo(181.176468f, 120); + path2.lineTo(135.294128f, 120); + path2.lineTo(142.589081f, 102.283646f); + path2.close(); + path2.moveTo(118.681946f, 160.343842f); + path2.lineTo(135.294128f, 120); + path2.lineTo(117.933762f, 120); + path2.quadTo(108, 132.942657f, 108, 150); + path2.quadTo(108, 151.54483f, 108.08149f, 153.05603f); + path2.lineTo(118.681946f, 160.343842f); + path2.close(); + path2.moveTo(156.969696f, 186.666672f); + path2.lineTo(118.681946f, 160.343842f); + path2.lineTo(113.458946f, 173.028259f); + path2.quadTo(116.94117f, 179.651855f, 122.644661f, 185.355347f); + path2.quadTo(130.792465f, 193.503143f, 140.817978f, 197.117783f); + path2.lineTo(156.969696f, 186.666672f); + path2.close(); + path2.moveTo(195.830978f, 161.521133f); + path2.lineTo(156.969696f, 186.666672f); + path2.lineTo(173.157288f, 197.795639f); + path2.quadTo(184.392426f, 194.318268f, 193.355347f, 185.355347f); + path2.quadTo(197.805817f, 180.904861f, 200.903809f, 175.894165f); + path2.lineTo(195.830978f, 161.521133f); + path2.close(); + path2.moveTo(195.830978f, 161.521133f); + path2.lineTo(207.878281f, 153.725815f); + path2.quadTo(208, 151.888062f, 208, 150); + path2.quadTo(208, 132.942657f, 198.066238f, 120); + path2.lineTo(181.176468f, 120); + path2.lineTo(195.830978f, 161.521133f); + path2.close(); + path2.setFillType(SkPath::kEvenOdd_FillType); + testPathOp(reporter, path1, path2, kIntersect_PathOp); +} +#endif + +#if 0 +static void bufferOverflow(skiatest::Reporter* reporter) { + SkPath path; + path.addRect(0,0, 300,170141183460469231731687303715884105728.); + SkPath pathB; + pathB.addRect(0,0, 300,16); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} +#endif + #if 0 static void skpkkiste_to716(skiatest::Reporter* reporter) { SkPath path; @@ -2013,10 +2156,145 @@ static void skpkkiste_to716(skiatest::Reporter* reporter) { } #endif +static void loopEdge1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0,0); + path.lineTo(3,0); + path.lineTo(3,2); + path.lineTo(1,2); + path.lineTo(1,1); + path.lineTo(2,1); + path.lineTo(2,3); + path.lineTo(0,3); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.moveTo(1,2); + pathB.lineTo(2,2); + pathB.lineTo(2,4); + pathB.lineTo(1,4); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void loopEdge2(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0,0); + path.lineTo(3,0); + path.lineTo(3,2); + path.lineTo(1,2); + path.lineTo(1,1); + path.lineTo(2,1); + path.lineTo(2,3); + path.lineTo(0,3); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.moveTo(1 - 1e-6f,2); + pathB.lineTo(2 - 1e-6f,2); + pathB.lineTo(2 - 1e-6f,4); + pathB.lineTo(1 - 1e-6f,4); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void cubicOp86i(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0, 4); + path.cubicTo(3, 4, 6, 2, 5, 2); + path.close(); + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.moveTo(2, 6); + pathB.cubicTo(2, 5, 4, 0, 4, 3); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void cubicOp87u(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(0,2, 2,0, 6,4); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,2); + pathB.cubicTo(4,6, 1,0, 2,0); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} + +static void cubicOp88u(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(2,5, 5,0, 6,4); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,5); + pathB.cubicTo(4,6, 1,0, 5,2); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} + +static void cubicOp89u(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0, 3); + path.cubicTo(1, 6, 5, 0, 6, 3); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0, 5); + pathB.cubicTo(3, 6, 3, 0, 6, 1); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} + +static void cubicOp90u(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0, 5); + path.cubicTo(1, 2, 5, 2, 4, 1); + path.close(); + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.moveTo(2, 5); + pathB.cubicTo(1, 4, 5, 0, 2, 1); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} + +static void cubicOp91u(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(1, 6); + path.cubicTo(0, 3, 6, 3, 5, 0); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(3, 6); + pathB.cubicTo(0, 5, 6, 1, 3, 0); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} static void (*firstTest)(skiatest::Reporter* ) = 0; static struct TestDesc tests[] = { // TEST(skpkkiste_to716), + // TEST(bufferOverflow), + // TEST(issue1435), + TEST(cubicOp91u), + TEST(cubicOp90u), + TEST(cubicOp89u), + TEST(cubicOp88u), + TEST(cubicOp87u), + TEST(cubicOp86i), + TEST(loopEdge2), + TEST(loopEdge1), + TEST(rectOp3x), + TEST(rectOp2i), + TEST(rectOp1i), + TEST(issue1418b), TEST(cubicOp85i), TEST(issue1417), TEST(issue1418), @@ -2167,8 +2445,8 @@ static void (*stopTest)(skiatest::Reporter* ) = 0; static void PathOpsOpTest(skiatest::Reporter* reporter) { #ifdef SK_DEBUG - gDebugMaxWindSum = 4; - gDebugMaxWindValue = 4; + SkPathOpsDebug::gMaxWindSum = 4; + SkPathOpsDebug::gMaxWindValue = 4; #endif #if DEBUG_SHOW_TEST_NAME strncpy(DEBUG_FILENAME_STRING, "", DEBUG_FILENAME_STRING_LENGTH); @@ -2181,8 +2459,8 @@ static void PathOpsOpTest(skiatest::Reporter* reporter) { RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse); } #ifdef SK_DEBUG - gDebugMaxWindSum = SK_MaxS32; - gDebugMaxWindValue = SK_MaxS32; + SkPathOpsDebug::gMaxWindSum = SK_MaxS32; + SkPathOpsDebug::gMaxWindValue = SK_MaxS32; #endif } diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp index 555a90ce70..7ec8066b03 100644 --- a/tests/PathOpsQuadLineIntersectionTest.cpp +++ b/tests/PathOpsQuadLineIntersectionTest.cpp @@ -59,6 +59,8 @@ static struct oneLineQuad { SkDQuad quad; SkDLine line; } oneOffs[] = { + {{{{142.589081, 102.283646}, {149.821579, 100}, {158, 100}}}, + {{{90, 230}, {160, 60}}}}, {{{{1101, 10}, {1101, 8.3431453704833984}, {1099.828857421875, 7.1711997985839844}}}, {{{1099.828857421875,7.1711711883544922}, {1099.121337890625,7.8786783218383789}}}}, {{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}}, diff --git a/tests/PathOpsSimplifyFailTest.cpp b/tests/PathOpsSimplifyFailTest.cpp index 0245f878c1..8c0f9ba852 100644 --- a/tests/PathOpsSimplifyFailTest.cpp +++ b/tests/PathOpsSimplifyFailTest.cpp @@ -37,63 +37,82 @@ static const SkPoint finitePts[] = { const size_t finitePtsCount = sizeof(finitePts) / sizeof(finitePts[0]); +static void failOne(skiatest::Reporter* reporter, int index) { + SkPath path; + int i = (int) (index % nonFinitePtsCount); + int f = (int) (index % finitePtsCount); + int g = (int) ((f + 1) % finitePtsCount); + switch (index % 13) { + case 0: path.lineTo(nonFinitePts[i]); break; + case 1: path.quadTo(nonFinitePts[i], nonFinitePts[i]); break; + case 2: path.quadTo(nonFinitePts[i], finitePts[f]); break; + case 3: path.quadTo(finitePts[f], nonFinitePts[i]); break; + case 4: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[f]); break; + case 5: path.cubicTo(finitePts[f], nonFinitePts[i], finitePts[f]); break; + case 6: path.cubicTo(finitePts[f], finitePts[f], nonFinitePts[i]); break; + case 7: path.cubicTo(nonFinitePts[i], nonFinitePts[i], finitePts[f]); break; + case 8: path.cubicTo(nonFinitePts[i], finitePts[f], nonFinitePts[i]); break; + case 9: path.cubicTo(finitePts[f], nonFinitePts[i], nonFinitePts[i]); break; + case 10: path.cubicTo(nonFinitePts[i], nonFinitePts[i], nonFinitePts[i]); break; + case 11: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[g]); break; + case 12: path.moveTo(nonFinitePts[i]); break; + } + SkPath result; + result.setFillType(SkPath::kWinding_FillType); + bool success = Simplify(path, &result); + REPORTER_ASSERT(reporter, !success); + REPORTER_ASSERT(reporter, result.isEmpty()); + REPORTER_ASSERT(reporter, result.getFillType() == SkPath::kWinding_FillType); + reporter->bumpTestCount(); +} + +static void dontFailOne(skiatest::Reporter* reporter, int index) { + SkPath path; + int f = (int) (index % finitePtsCount); + int g = (int) ((f + 1) % finitePtsCount); + switch (index % 11) { + case 0: path.lineTo(finitePts[f]); break; + case 1: path.quadTo(finitePts[f], finitePts[f]); break; + case 2: path.quadTo(finitePts[f], finitePts[g]); break; + case 3: path.quadTo(finitePts[g], finitePts[f]); break; + case 4: path.cubicTo(finitePts[f], finitePts[f], finitePts[f]); break; + case 5: path.cubicTo(finitePts[f], finitePts[f], finitePts[g]); break; + case 6: path.cubicTo(finitePts[f], finitePts[g], finitePts[f]); break; + case 7: path.cubicTo(finitePts[f], finitePts[g], finitePts[g]); break; + case 8: path.cubicTo(finitePts[g], finitePts[f], finitePts[f]); break; + case 9: path.cubicTo(finitePts[g], finitePts[f], finitePts[g]); break; + case 10: path.moveTo(finitePts[f]); break; + } + SkPath result; + result.setFillType(SkPath::kWinding_FillType); + bool success = Simplify(path, &result); + REPORTER_ASSERT(reporter, success); + REPORTER_ASSERT(reporter, result.getFillType() != SkPath::kWinding_FillType); + reporter->bumpTestCount(); +} + static void PathOpsSimplifyFailTest(skiatest::Reporter* reporter) { for (int index = 0; index < (int) (13 * nonFinitePtsCount * finitePtsCount); ++index) { - SkPath path; - int i = (int) (index % nonFinitePtsCount); - int f = (int) (index % finitePtsCount); - int g = (int) ((f + 1) % finitePtsCount); - switch (index % 13) { - case 0: path.lineTo(nonFinitePts[i]); break; - case 1: path.quadTo(nonFinitePts[i], nonFinitePts[i]); break; - case 2: path.quadTo(nonFinitePts[i], finitePts[f]); break; - case 3: path.quadTo(finitePts[f], nonFinitePts[i]); break; - case 4: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[f]); break; - case 5: path.cubicTo(finitePts[f], nonFinitePts[i], finitePts[f]); break; - case 6: path.cubicTo(finitePts[f], finitePts[f], nonFinitePts[i]); break; - case 7: path.cubicTo(nonFinitePts[i], nonFinitePts[i], finitePts[f]); break; - case 8: path.cubicTo(nonFinitePts[i], finitePts[f], nonFinitePts[i]); break; - case 9: path.cubicTo(finitePts[f], nonFinitePts[i], nonFinitePts[i]); break; - case 10: path.cubicTo(nonFinitePts[i], nonFinitePts[i], nonFinitePts[i]); break; - case 11: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[g]); break; - case 12: path.moveTo(nonFinitePts[i]); break; - } - SkPath result; - result.setFillType(SkPath::kWinding_FillType); - bool success = Simplify(path, &result); - REPORTER_ASSERT(reporter, !success); - REPORTER_ASSERT(reporter, result.isEmpty()); - REPORTER_ASSERT(reporter, result.getFillType() == SkPath::kWinding_FillType); - reporter->bumpTestCount(); - } - if (sizeof(reporter) == 4) { - return; + failOne(reporter, index); } for (int index = 0; index < (int) (11 * finitePtsCount); ++index) { - SkPath path; - int f = (int) (index % finitePtsCount); - int g = (int) ((f + 1) % finitePtsCount); - switch (index % 11) { - case 0: path.lineTo(finitePts[f]); break; - case 1: path.quadTo(finitePts[f], finitePts[f]); break; - case 2: path.quadTo(finitePts[f], finitePts[g]); break; - case 3: path.quadTo(finitePts[g], finitePts[f]); break; - case 4: path.cubicTo(finitePts[f], finitePts[f], finitePts[f]); break; - case 5: path.cubicTo(finitePts[f], finitePts[f], finitePts[g]); break; - case 6: path.cubicTo(finitePts[f], finitePts[g], finitePts[f]); break; - case 7: path.cubicTo(finitePts[f], finitePts[g], finitePts[g]); break; - case 8: path.cubicTo(finitePts[g], finitePts[f], finitePts[f]); break; - case 9: path.cubicTo(finitePts[g], finitePts[f], finitePts[g]); break; - case 10: path.moveTo(finitePts[f]); break; - } - SkPath result; - result.setFillType(SkPath::kWinding_FillType); - bool success = Simplify(path, &result); - REPORTER_ASSERT(reporter, success); - REPORTER_ASSERT(reporter, result.getFillType() != SkPath::kWinding_FillType); - reporter->bumpTestCount(); + dontFailOne(reporter, index); } } +static void PathOpsSimplifyFailOneTest(skiatest::Reporter* reporter) { + int index = 0; + failOne(reporter, index); +} + +static void PathOpsSimplifyDontFailOneTest(skiatest::Reporter* reporter) { + int index = 6; + dontFailOne(reporter, index); +} + #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsSimplifyFailTest) + +DEFINE_TESTCLASS_SHORT(PathOpsSimplifyFailOneTest) + +DEFINE_TESTCLASS_SHORT(PathOpsSimplifyDontFailOneTest) diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index 954435fc92..65b8d98783 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -2813,6 +2813,7 @@ static void testQuadratic53(skiatest::Reporter* reporter) { path.close(); testSimplify(reporter, path); } + static void testQuadratic55(skiatest::Reporter* reporter) { SkPath path; path.moveTo(303.12088f, 141.299606f); @@ -3828,9 +3829,90 @@ static void skphealth_com76(skiatest::Reporter* reporter) { testSimplify(reporter, path); } -static void (*firstTest)(skiatest::Reporter* ) = testQuad6; +static void tooCloseTest(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(0, 0); + path.lineTo(1, 1); + path.lineTo(1,-1); + path.close(); + path.moveTo(0, 0); + path.lineTo(1,-2); + path.lineTo(1, 2); + path.lineTo(2, 0); + path.close(); + testSimplify(reporter, path); +} + +static void testRect1(skiatest::Reporter* reporter) { + SkPath path; + path.addRect(0, 0, 60, 60, SkPath::kCCW_Direction); + path.addRect(30, 20, 50, 50, SkPath::kCCW_Direction); + path.addRect(24, 20, 36, 30, SkPath::kCCW_Direction); + path.addRect(32, 24, 36, 41, SkPath::kCCW_Direction); + testSimplify(reporter, path); +} + +static void testRect2(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0, 0); + path.lineTo(60, 0); + path.lineTo(60, 60); + path.lineTo(0, 60); + path.close(); + path.moveTo(30, 20); + path.lineTo(30, 50); + path.lineTo(50, 50); + path.lineTo(50, 20); + path.close(); + path.moveTo(24, 20); + path.lineTo(24, 30); + path.lineTo(36, 30); + path.lineTo(36, 20); + path.close(); + path.moveTo(32, 24); + path.lineTo(32, 41); + path.lineTo(36, 41); + path.lineTo(36, 24); + path.close(); + testSimplify(reporter, path); +} + +static void testTriangles3x(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(1, 0); + path.quadTo(0, 1, 3, 2); + path.lineTo(1, 3); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 1); + path.quadTo(2, 1, 0, 2); + path.close(); + testSimplify(reporter, path); +} + +static void testQuad8(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(3, 0); + path.quadTo(0, 1, 3, 2); + path.lineTo(0, 3); + path.close(); + path.moveTo(1, 0); + path.lineTo(3, 0); + path.quadTo(1, 1, 2, 2); + path.close(); + testSimplify(reporter, path); +} + +static void (*firstTest)(skiatest::Reporter* ) = testRect2; static TestDesc tests[] = { + TEST(testQuad8), + TEST(testTriangles3x), + TEST(testRect2), + TEST(testRect1), + TEST(tooCloseTest), TEST(skphealth_com76), TEST(testQuadLineIntersect1), TEST(testQuadLineIntersect2), @@ -4199,8 +4281,8 @@ static void (*stopTest)(skiatest::Reporter* ) = 0; static void PathOpsSimplifyTest(skiatest::Reporter* reporter) { #ifdef SK_DEBUG - gDebugMaxWindSum = 4; - gDebugMaxWindValue = 4; + SkPathOpsDebug::gMaxWindSum = 4; + SkPathOpsDebug::gMaxWindValue = 4; #endif if (runSubTestsFirst) { RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse); @@ -4210,8 +4292,8 @@ static void PathOpsSimplifyTest(skiatest::Reporter* reporter) { RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse); } #ifdef SK_DEBUG - gDebugMaxWindSum = SK_MaxS32; - gDebugMaxWindValue = SK_MaxS32; + SkPathOpsDebug::gMaxWindSum = SK_MaxS32; + SkPathOpsDebug::gMaxWindValue = SK_MaxS32; #endif } diff --git a/tests/PathOpsThreadedCommon.cpp b/tests/PathOpsThreadedCommon.cpp index 0abf8166dd..a66ec710c7 100644 --- a/tests/PathOpsThreadedCommon.cpp +++ b/tests/PathOpsThreadedCommon.cpp @@ -21,7 +21,7 @@ void PathOpsThreadedTestRunner::render() { pool.add(fRunnables[index]); } #ifdef SK_DEBUG - gDebugMaxWindSum = SK_MaxS32; - gDebugMaxWindValue = SK_MaxS32; + SkPathOpsDebug::gMaxWindSum = SK_MaxS32; + SkPathOpsDebug::gMaxWindValue = SK_MaxS32; #endif } |