From dac1d17027dcaa5596885a9f333979418b35001c Mon Sep 17 00:00:00 2001 From: caryclark Date: Tue, 17 Jun 2014 05:15:38 -0700 Subject: [PATCH] Enabling the canvas bit to turn the clip stack into a flat replace exposed around 100 failures when testing the 800K skp set generated from the top 1M web sites. This fixes all but one of those failures. Major changes include: - Replace angle indices with angle pointers. This was motivated by the need to add angles later but not renumber existing angles. - Aggressive segment chase. When the winding is known on a segment, more aggressively passing that winding to adjacent segments allows fragmented data sets to succeed. - Line segments with ends nearly the same are treated as coincident first. - Transfer partial coincidence by observing that if segment A is partially coincident to B and C then B and C may be partially coincident. TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/272153002 --- src/pathops/SkAddIntersections.cpp | 5 + src/pathops/SkDCubicIntersection.cpp | 41 +- src/pathops/SkDCubicLineIntersection.cpp | 2 +- src/pathops/SkDLineIntersection.cpp | 59 +- src/pathops/SkDQuadIntersection.cpp | 2 +- src/pathops/SkDQuadLineIntersection.cpp | 6 +- src/pathops/SkIntersectionHelper.h | 5 + src/pathops/SkIntersections.cpp | 11 + src/pathops/SkIntersections.h | 33 +- src/pathops/SkOpAngle.cpp | 49 +- src/pathops/SkOpAngle.h | 30 +- src/pathops/SkOpContour.cpp | 375 ++- src/pathops/SkOpContour.h | 44 +- src/pathops/SkOpSegment.cpp | 1096 ++++++--- src/pathops/SkOpSegment.h | 81 +- src/pathops/SkOpSpan.h | 10 +- src/pathops/SkPathOpsCommon.cpp | 110 +- src/pathops/SkPathOpsCommon.h | 2 +- src/pathops/SkPathOpsDebug.cpp | 111 +- src/pathops/SkPathOpsDebug.h | 36 +- src/pathops/SkPathOpsLine.cpp | 5 +- src/pathops/SkPathOpsLine.h | 2 +- src/pathops/SkPathOpsOp.cpp | 34 +- src/pathops/SkPathOpsPoint.h | 2 - src/pathops/SkPathOpsSimplify.cpp | 28 +- src/pathops/SkPathOpsTriangle.cpp | 2 +- src/pathops/SkPathOpsTypes.h | 13 +- tests/PathOpsAngleIdeas.cpp | 6 +- tests/PathOpsAngleTest.cpp | 8 +- tests/PathOpsCubicIntersectionTest.cpp | 3 + tests/PathOpsDebug.cpp | 304 ++- tests/PathOpsExtendedTest.cpp | 11 +- tests/PathOpsLineIntersectionTest.cpp | 10 +- tests/PathOpsOpTest.cpp | 114 + tests/PathOpsSimplifyTest.cpp | 19 +- tests/PathOpsSkpClipTest.cpp | 548 ++++- tests/PathOpsSkpTest.cpp | 701 +++++- tools/pathops_sorter.htm | 59 +- tools/pathops_visualizer.htm | 3925 ++++++++++++++++++++++++++++++ 39 files changed, 7093 insertions(+), 809 deletions(-) create mode 100644 tools/pathops_visualizer.htm diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 620842b..52e751b 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -397,6 +397,7 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); SkPoint point = ts.pt(pt).asSkPoint(); + wt.alignTPt(wn, swap, pt, &ts, &point); int testTAt = wt.addT(wn, point, ts[swap][pt]); int nextTAt = wn.addT(wt, point, ts[!swap][pt]); wt.addOtherT(testTAt, ts[!swap][pt], nextTAt); @@ -437,6 +438,10 @@ void CoincidenceCheck(SkTArray* contourList, int total) { int contourCount = (*contourList).count(); for (int cIndex = 0; cIndex < contourCount; ++cIndex) { SkOpContour* contour = (*contourList)[cIndex]; + contour->resolveNearCoincidence(); + } + for (int cIndex = 0; cIndex < contourCount; ++cIndex) { + SkOpContour* contour = (*contourList)[cIndex]; contour->addCoincidentPoints(); } for (int cIndex = 0; cIndex < contourCount; ++cIndex) { diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index dd51195..1c237d9 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -303,15 +303,39 @@ bool SkIntersections::cubicExactEnd(const SkDCubic& cubic1, bool start, const Sk continue; } if (swap) { - insert(testT, impTs[0][index], tmpLine[0]); + cubicInsert(testT, impTs[0][index], tmpLine[0], cubic2, cubic1); } else { - insert(impTs[0][index], testT, tmpLine[0]); + cubicInsert(impTs[0][index], testT, tmpLine[0], cubic1, cubic2); } return true; } return false; } + +void SkIntersections::cubicInsert(double one, double two, const SkDPoint& pt, + const SkDCubic& cubic1, const SkDCubic& cubic2) { + for (int index = 0; index < fUsed; ++index) { + if (fT[0][index] == one) { + double oldTwo = fT[1][index]; + if (oldTwo == two) { + return; + } + SkDPoint mid = cubic2.ptAtT((oldTwo + two) / 2); + if (mid.approximatelyEqual(fPt[index])) { + return; + } + } + if (fT[1][index] == two) { + SkDPoint mid = cubic1.ptAtT((fT[0][index] + two) / 2); + if (mid.approximatelyEqual(fPt[index])) { + return; + } + } + } + insert(one, two, pt); +} + void SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& bounds2) { SkDLine line; @@ -371,11 +395,15 @@ void SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkD double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0); double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0); int lastUsed = used(); - ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); + if (start ? tMax1 < tMin2 : tMax2 < tMin1) { + ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); + } if (lastUsed == used()) { tMin2 = SkTMax(tVals[tIdx] - (1.0 / SkDCubic::gPrecisionUnit), 0.0); tMax2 = SkTMin(tVals[tLast] + (1.0 / SkDCubic::gPrecisionUnit), 1.0); - ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); + if (start ? tMax1 < tMin2 : tMax2 < tMin1) { + ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this); + } } tIdx = tLast + 1; } while (tIdx < tVals.count()); @@ -421,6 +449,9 @@ static bool only_end_pts_in_common(const SkDCubic& c1, const SkDCubic& c2) { } double adj = endPt[oppTest]->fX - origX; double opp = endPt[oppTest]->fY - origY; + if (adj == 0 && opp == 0) { // if the other point equals the test point, ignore it + continue; + } double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp; if (approximately_zero(sign)) { goto tryNextHalfPlane; @@ -531,7 +562,7 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { if (compCount) { int exactCount = used(); if (exactCount == 0) { - set(i); + *this = i; } else { // at least one is exact or near, and at least one was computed. Eliminate duplicates for (int exIdx = 0; exIdx < exactCount; ++exIdx) { diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index 41828bb..696c42e 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -261,7 +261,7 @@ public: if (fIntersections->hasT(cubicT)) { continue; } - double lineT = fLine.nearPoint(fCubic[cIndex]); + double lineT = fLine.nearPoint(fCubic[cIndex], NULL); if (lineT < 0) { continue; } diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index 8969539..9ae0107 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -154,15 +154,52 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { computePoints(a, 1); } } +/* Allow tracking that both sets of end points are near each other -- the lines are entirely + coincident -- even when the end points are not exactly the same. + Mark this as a 'wild card' for the end points, so that either point is considered totally + coincident. Then, avoid folding the lines over each other, but allow either end to mate + to the next set of lines. + */ if (fAllowNear || !unparallel) { - for (int iA = 0; iA < 2; ++iA) { - if ((t = b.nearPoint(a[iA])) >= 0) { - insert(iA, t, a[iA]); - } + double aNearB[2]; + double bNearA[2]; + bool aNotB[2] = {false, false}; + bool bNotA[2] = {false, false}; + int nearCount = 0; + for (int index = 0; index < 2; ++index) { + aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]); + nearCount += t >= 0; + bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]); + nearCount += t >= 0; } - for (int iB = 0; iB < 2; ++iB) { - if ((t = a.nearPoint(b[iB])) >= 0) { - insert(t, iB, b[iB]); + if (nearCount > 0) { + for (int iA = 0; iA < 2; ++iA) { + if (!aNotB[iA]) { + continue; + } + int nearer = aNearB[iA] > 0.5; + if (!bNotA[nearer]) { + continue; + } + SkASSERT(a[iA] != b[nearer]); + SkASSERT(iA == (bNearA[nearer] > 0.5)); + fNearlySame[iA] = true; + insertNear(iA, nearer, a[iA], b[nearer]); + aNearB[iA] = -1; + bNearA[nearer] = -1; + nearCount -= 2; + } + if (nearCount > 0) { + for (int iA = 0; iA < 2; ++iA) { + if (aNearB[iA] >= 0) { + insert(iA, aNearB[iA], a[iA]); + } + } + for (int iB = 0; iB < 2; ++iB) { + if (bNearA[iB] >= 0) { + insert(bNearA[iB], iB, b[iB]); + } + } } } } @@ -240,12 +277,12 @@ int SkIntersections::horizontal(const SkDLine& line, double left, double right, } } if (fAllowNear || result == 2) { - if ((t = line.nearPoint(leftPt)) >= 0) { + if ((t = line.nearPoint(leftPt, NULL)) >= 0) { insert(t, (double) flipped, leftPt); } if (left != right) { const SkDPoint rightPt = { right, y }; - if ((t = line.nearPoint(rightPt)) >= 0) { + if ((t = line.nearPoint(rightPt, NULL)) >= 0) { insert(t, (double) !flipped, rightPt); } for (int index = 0; index < 2; ++index) { @@ -328,12 +365,12 @@ int SkIntersections::vertical(const SkDLine& line, double top, double bottom, } } if (fAllowNear || result == 2) { - if ((t = line.nearPoint(topPt)) >= 0) { + if ((t = line.nearPoint(topPt, NULL)) >= 0) { insert(t, (double) flipped, topPt); } if (top != bottom) { SkDPoint bottomPt = { x, bottom }; - if ((t = line.nearPoint(bottomPt)) >= 0) { + if ((t = line.nearPoint(bottomPt, NULL)) >= 0) { insert(t, (double) !flipped, bottomPt); } for (int index = 0; index < 2; ++index) { diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 14ccac6..5a8bafc 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -422,7 +422,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { swapped.setMax(fMax); if (is_linear(q2, q1, &swapped)) { swapped.swapPts(); - set(swapped); + *this = swapped; return fUsed; } SkIntersections copyI(*this); diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index 1b9d8cc..ef8edb0 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -238,7 +238,7 @@ protected: if (fIntersections->hasT(quadT)) { continue; } - double lineT = fLine.nearPoint(fQuad[qIndex]); + double lineT = fLine.nearPoint(fQuad[qIndex], NULL); if (lineT < 0) { continue; } @@ -324,10 +324,10 @@ protected: *pt = fQuad.ptAtT(qT); } SkPoint gridPt = pt->asSkPoint(); - if (gridPt == fLine[0].asSkPoint()) { + if (SkDPoint::ApproximatelyEqual(gridPt, fLine[0].asSkPoint())) { *pt = fLine[0]; *lineT = 0; - } else if (gridPt == fLine[1].asSkPoint()) { + } else if (SkDPoint::ApproximatelyEqual(gridPt, fLine[1].asSkPoint())) { *pt = fLine[1]; *lineT = 1; } diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h index 4e8c658..3569c93 100644 --- a/src/pathops/SkIntersectionHelper.h +++ b/src/pathops/SkIntersectionHelper.h @@ -54,6 +54,11 @@ public: return ++fIndex < fLast; } + void alignTPt(SkIntersectionHelper& other, bool swap, int index, + SkIntersections* ts, SkPoint* point) { + fContour->alignTPt(fIndex, other.fContour, other.fIndex, swap, index, ts, point); + } + SkScalar bottom() const { return bounds().fBottom; } diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index c8b4b83..56eba27 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -103,6 +103,7 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { int remaining = fUsed - index; if (remaining > 0) { memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); + memmove(&fPt2[index + 1], &fPt2[index], sizeof(fPt2[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); int clearMask = ~((1 << index) - 1); @@ -116,6 +117,15 @@ int SkIntersections::insert(double one, double two, const SkDPoint& pt) { return index; } +void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { + SkASSERT(one == 0 || one == 1); + SkASSERT(two == 0 || two == 1); + SkASSERT(pt1 != pt2); + SkASSERT(fNearlySame[(int) one]); + (void) insert(one, two, pt1); + fPt2[one ? fUsed - 1 : 0] = pt2; +} + 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) { return; } memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); + memmove(&fPt2[index], &fPt2[index + 1], sizeof(fPt2[0]) * remaining); memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); SkASSERT(fIsCoincident[0] == 0); diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index eced4dd..0186b37 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -21,8 +21,10 @@ public: #endif { sk_bzero(fPt, sizeof(fPt)); + sk_bzero(fPt2, sizeof(fPt2)); sk_bzero(fT, sizeof(fT)); sk_bzero(fIsCoincident, sizeof(fIsCoincident)); + sk_bzero(fNearlySame, sizeof(fNearlySame)); reset(); fMax = 0; // require that the caller set the max } @@ -37,16 +39,6 @@ public: }; TArray operator[](int n) const { return TArray(fT[n]); } - void set(const SkIntersections& i) { - memcpy(fPt, i.fPt, sizeof(fPt)); - memcpy(fT, i.fT, sizeof(fT)); - memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident)); - fUsed = i.fUsed; - fMax = i.fMax; - fSwap = i.fSwap; - SkDEBUGCODE(fDepth = i.fDepth); - } - void allowNear(bool nearAllowed) { fAllowNear = nearAllowed; } @@ -140,10 +132,19 @@ public: return intersect(aLine, bLine); } + bool nearlySame(int index) const { + SkASSERT(index == 0 || index == 1); + return fNearlySame[index]; + } + const SkDPoint& pt(int index) const { return fPt[index]; } + const SkDPoint& pt2(int index) const { + return fPt2[index]; + } + int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y, bool flipped) { SkDQuad quad; @@ -177,12 +178,16 @@ public: return intersect(aQuad, bQuad); } - // leaves flip, swap, max alone + // leaves swap, max alone void reset() { fAllowNear = true; fUsed = 0; } + void set(bool swap, int tIndex, double t) { + fT[(int) swap][tIndex] = t; + } + void setMax(int max) { fMax = max; } @@ -212,6 +217,8 @@ public: void append(const SkIntersections& ); void cleanUpCoincidence(); int coincidentUsed() const; + void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1, + const SkDCubic& c2); int cubicRay(const SkPoint pts[4], const SkDLine& line); void flip(); int horizontal(const SkDLine&, double y); @@ -223,7 +230,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); + void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2); // start if index == 0 : end if index == 1 void insertCoincident(double one, double two, const SkDPoint& pt); int intersect(const SkDLine&, const SkDLine&); @@ -267,8 +274,10 @@ private: void computePoints(const SkDLine& line, int used); SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also + SkDPoint fPt2[9]; // used by nearly same to store alternate intersection point double fT[2][9]; uint16_t fIsCoincident[2]; // bit set for each curve's coincident T + bool fNearlySame[2]; // true if end points nearly match unsigned char fUsed; unsigned char fMax; bool fAllowNear; diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index 094b22c..894758c 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -289,7 +289,7 @@ bool SkOpAngle::computeSector() { // FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51 // -- but in general, this code may not work so this may be the least of problems // adding the bang fixes testQuads46x in release, however - return fUnorderable; + return !fUnorderable; } SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small()); fComputedSector = true; @@ -322,7 +322,7 @@ recomputeSector: return false; } int saveEnd = fEnd; - fEnd = checkEnd - step; + fComputedEnd = fEnd = checkEnd - step; setSpans(); setSector(); fEnd = saveEnd; @@ -414,12 +414,12 @@ bool SkOpAngle::endsIntersect(const SkOpAngle& rh) const { SkIntersections i; (*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i); // SkASSERT(i.used() >= 1); - if (i.used() <= 1) { - continue; - } +// if (i.used() <= 1) { +// continue; +// } double tStart = segment.t(index ? rh.fStart : fStart); - double tEnd = segment.t(index ? rh.fEnd : fEnd); - bool testAscends = index ? rh.fStart < rh.fEnd : fStart < fEnd; + double tEnd = segment.t(index ? rh.fComputedEnd : fComputedEnd); + bool testAscends = index ? rh.fStart < rh.fComputedEnd : fStart < fComputedEnd; double t = testAscends ? 0 : 1; for (int idx2 = 0; idx2 < i.used(); ++idx2) { double testT = i[0][idx2]; @@ -879,12 +879,9 @@ SkOpAngle* SkOpAngle::previous() const { } void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { -#if DEBUG_ANGLE - fID = 0; -#endif fSegment = segment; fStart = start; - fEnd = end; + fComputedEnd = fEnd = end; fNext = NULL; fComputeSector = fComputedSector = false; fStop = false; @@ -1097,3 +1094,33 @@ bool SkOpAngle::tangentsDiverge(const SkOpAngle& rh, double s0xt0) const { double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist)); return mFactor < 5000; // empirically found limit } + +SkOpAngleSet::SkOpAngleSet() + : fAngles(NULL) +#if DEBUG_ANGLE + , fCount(0) +#endif +{ +} + +SkOpAngleSet::~SkOpAngleSet() { + SkDELETE(fAngles); +} + +SkOpAngle& SkOpAngleSet::push_back() { + if (!fAngles) { + fAngles = SkNEW_ARGS(SkChunkAlloc, (2)); + } + void* ptr = fAngles->allocThrow(sizeof(SkOpAngle)); + SkOpAngle* angle = (SkOpAngle*) ptr; +#if DEBUG_ANGLE + angle->setID(++fCount); +#endif + return *angle; +} + +void SkOpAngleSet::reset() { + if (fAngles) { + fAngles->reset(); + } +} diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h index e566913..63d378d 100644 --- a/src/pathops/SkOpAngle.h +++ b/src/pathops/SkOpAngle.h @@ -7,6 +7,7 @@ #ifndef SkOpAngle_DEFINED #define SkOpAngle_DEFINED +#include "SkChunkAlloc.h" #include "SkLineParameters.h" class SkOpSegment; @@ -81,13 +82,19 @@ public: void debugSameAs(const SkOpAngle* compare) const; #endif void dump() const; - void dumpFromTo(const SkOpSegment* fromSeg, int from, int to) const; + void dumpLoop() const; + void dumpTo(const SkOpSegment* fromSeg, const SkOpAngle* ) const; #if DEBUG_ANGLE + int debugID() const { return fID; } + void setID(int id) { fID = id; } +#else + int debugID() const { return 0; } #endif + #if DEBUG_VALIDATE void debugValidateLoop() const; #endif @@ -121,6 +128,7 @@ private: SkDVector fSweep[2]; int fStart; int fEnd; + int fComputedEnd; int fSectorMask; int8_t fSectorStart; // in 32nds of a circle int8_t fSectorEnd; @@ -131,11 +139,7 @@ private: bool fComputeSector; bool fComputedSector; -#if DEBUG_SORT - void debugOne(bool showFunc) const; // available to testing only -#endif #if DEBUG_ANGLE - int debugID() const { return fID; } int fID; #endif #if DEBUG_VALIDATE @@ -143,9 +147,23 @@ private: #else void debugValidateNext() const {} #endif - void dumpLoop() const; // utility to be called by user from debugger + void dumpOne(bool showFunc) const; // available to testing only void dumpPartials() const; // utility to be called by user from debugger friend class PathOpsAngleTester; }; +class SkOpAngleSet { +public: + SkOpAngleSet(); + ~SkOpAngleSet(); + SkOpAngle& push_back(); + void reset(); +private: + void dump() const; // utility to be called by user from debugger +#if DEBUG_ANGLE + int fCount; +#endif + SkChunkAlloc* fAngles; +}; + #endif diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp index e3137b7..5ef702d 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -28,8 +28,14 @@ bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, coincidence.fTs[swap][1] = ts[0][1]; coincidence.fTs[!swap][0] = ts[1][0]; coincidence.fTs[!swap][1] = ts[1][1]; - coincidence.fPts[0] = pt0; - coincidence.fPts[1] = pt1; + coincidence.fPts[swap][0] = pt0; + coincidence.fPts[swap][1] = pt1; + bool nearStart = ts.nearlySame(0); + bool nearEnd = ts.nearlySame(1); + coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0; + coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1; + coincidence.fNearly[0] = nearStart; + coincidence.fNearly[1] = nearEnd; return true; } @@ -93,28 +99,31 @@ void SkOpContour::addCoincidentPoints() { cancelers ^= true; } SkASSERT(!approximately_negative(oEndT - oStartT)); + const SkPoint& startPt = coincidence.fPts[0][startSwapped]; if (cancelers) { // make sure startT and endT have t entries - const SkPoint& startPt = coincidence.fPts[startSwapped]; if (startT > 0 || oEndT < 1 || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) { - thisOne.addTPair(startT, &other, oEndT, true, startPt); + thisOne.addTPair(startT, &other, oEndT, true, startPt, + coincidence.fPts[1][startSwapped]); } - const SkPoint& oStartPt = coincidence.fPts[oStartSwapped]; + const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped]; if (oStartT > 0 || endT < 1 || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) { - other.addTPair(oStartT, &thisOne, endT, true, oStartPt); + other.addTPair(oStartT, &thisOne, endT, true, oStartPt, + coincidence.fPts[0][oStartSwapped]); } } else { - const SkPoint& startPt = coincidence.fPts[startSwapped]; if (startT > 0 || oStartT > 0 || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) { - thisOne.addTPair(startT, &other, oStartT, true, startPt); + thisOne.addTPair(startT, &other, oStartT, true, startPt, + coincidence.fPts[1][startSwapped]); } - const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped]; + const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped]; if (endT < 1 || oEndT < 1 || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) { - other.addTPair(oEndT, &thisOne, endT, true, oEndPt); + other.addTPair(oEndT, &thisOne, endT, true, oEndPt, + coincidence.fPts[0][!oStartSwapped]); } } #if DEBUG_CONCIDENT @@ -122,6 +131,32 @@ void SkOpContour::addCoincidentPoints() { other.debugShowTs("o"); #endif } + // if there are multiple pairs of coincidence that share an edge, see if the opposite + // are also coincident + for (int index = 0; index < count - 1; ++index) { + const SkCoincidence& coincidence = fCoincidences[index]; + int thisIndex = coincidence.fSegments[0]; + SkOpContour* otherContour = coincidence.fOther; + int otherIndex = coincidence.fSegments[1]; + for (int idx2 = 1; idx2 < count; ++idx2) { + const SkCoincidence& innerCoin = fCoincidences[idx2]; + int innerThisIndex = innerCoin.fSegments[0]; + if (thisIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 1, innerCoin, 1, false); + } + if (this == otherContour && otherIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 0, innerCoin, 1, false); + } + SkOpContour* innerOtherContour = innerCoin.fOther; + innerThisIndex = innerCoin.fSegments[1]; + if (this == innerOtherContour && thisIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 1, innerCoin, 0, false); + } + if (otherContour == innerOtherContour && otherIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 0, innerCoin, 0, false); + } + } + } } bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, @@ -143,11 +178,77 @@ bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherI coincidence.fTs[swap][1] = ts[0][ptIndex + 1]; coincidence.fTs[!swap][0] = ts[1][ptIndex]; coincidence.fTs[!swap][1] = ts[1][ptIndex + 1]; - coincidence.fPts[0] = pt0; - coincidence.fPts[1] = pt1; + coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0; + coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1; + coincidence.fNearly[0] = 0; + coincidence.fNearly[1] = 0; return true; } +void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap, + SkCoincidence* coincidence) { + for (int idx2 = 0; idx2 < 2; ++idx2) { + if (coincidence->fPts[0][idx2] == aligned.fOldPt + && coincidence->fTs[swap][idx2] == aligned.fOldT) { + SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt)); + coincidence->fPts[0][idx2] = aligned.fPt; + SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT)); + coincidence->fTs[swap][idx2] = aligned.fT; + } + } +} + +void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned, + SkTArray* coincidences) { + int count = coincidences->count(); + for (int index = 0; index < count; ++index) { + SkCoincidence& coincidence = (*coincidences)[index]; + int thisIndex = coincidence.fSegments[0]; + const SkOpSegment* thisOne = &fSegments[thisIndex]; + const SkOpContour* otherContour = coincidence.fOther; + int otherIndex = coincidence.fSegments[1]; + const SkOpSegment* other = &otherContour->fSegments[otherIndex]; + if (thisOne == aligned.fOther1 && other == aligned.fOther2) { + align(aligned, false, &coincidence); + } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) { + align(aligned, true, &coincidence); + } + } +} + +void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex, + bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const { + int zeroPt; + if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) { + alignPt(segmentIndex, point, zeroPt); + } + if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) { + other->alignPt(otherIndex, point, zeroPt); + } +} + +void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const { + const SkOpSegment& segment = fSegments[index]; + if (0 == zeroPt) { + *point = segment.pts()[0]; + } else { + *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())]; + } +} + +int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const { + double tVal = (*ts)[swap][tIndex]; + if (tVal != 0 && precisely_zero(tVal)) { + ts->set(swap, tIndex, 0); + return 0; + } + if (tVal != 1 && precisely_equal(tVal, 1)) { + ts->set(swap, tIndex, 1); + return 1; + } + return -1; +} + bool SkOpContour::calcAngles() { int segmentCount = fSegments.count(); for (int test = 0; test < segmentCount; ++test) { @@ -180,7 +281,187 @@ void SkOpContour::calcPartialCoincidentWinding() { #endif for (int index = 0; index < count; ++index) { SkCoincidence& coincidence = fPartialCoincidences[index]; - calcCommonCoincidentWinding(coincidence); + calcCommonCoincidentWinding(coincidence); + } + // if there are multiple pairs of partial coincidence that share an edge, see if the opposite + // are also coincident + for (int index = 0; index < count - 1; ++index) { + const SkCoincidence& coincidence = fPartialCoincidences[index]; + int thisIndex = coincidence.fSegments[0]; + SkOpContour* otherContour = coincidence.fOther; + int otherIndex = coincidence.fSegments[1]; + for (int idx2 = 1; idx2 < count; ++idx2) { + const SkCoincidence& innerCoin = fPartialCoincidences[idx2]; + int innerThisIndex = innerCoin.fSegments[0]; + if (thisIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 1, innerCoin, 1, true); + } + if (this == otherContour && otherIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 0, innerCoin, 1, true); + } + SkOpContour* innerOtherContour = innerCoin.fOther; + innerThisIndex = innerCoin.fSegments[1]; + if (this == innerOtherContour && thisIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 1, innerCoin, 0, true); + } + if (otherContour == innerOtherContour && otherIndex == innerThisIndex) { + checkCoincidentPair(coincidence, 0, innerCoin, 0, true); + } + } + } +} + +void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx, + const SkCoincidence& twoCoin, int twoIdx, bool partial) { + SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther)); + SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]); + // look for common overlap + double min = SK_ScalarMax; + double max = SK_ScalarMin; + double min1 = oneCoin.fTs[!oneIdx][0]; + double max1 = oneCoin.fTs[!oneIdx][1]; + double min2 = twoCoin.fTs[!twoIdx][0]; + double max2 = twoCoin.fTs[!twoIdx][1]; + bool cancelers = (min1 < max1) != (min2 < max2); + if (min1 > max1) { + SkTSwap(min1, max1); + } + if (min2 > max2) { + SkTSwap(min2, max2); + } + if (between(min1, min2, max1)) { + min = min2; + } + if (between(min1, max2, max1)) { + max = max2; + } + if (between(min2, min1, max2)) { + min = SkTMin(min, min1); + } + if (between(min2, max1, max2)) { + max = SkTMax(max, max1); + } + if (min >= max) { + return; // no overlap + } + // look to see if opposite are different segments + int seg1Index = oneCoin.fSegments[oneIdx]; + int seg2Index = twoCoin.fSegments[twoIdx]; + if (seg1Index == seg2Index) { + return; + } + SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this; + SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this; + SkOpSegment* segment1 = &contour1->fSegments[seg1Index]; + SkOpSegment* segment2 = &contour2->fSegments[seg2Index]; + // find opposite t value ranges corresponding to reference min/max range + const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther; + const int refSegIndex = oneCoin.fSegments[!oneIdx]; + const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex]; + int seg1Start = segment1->findOtherT(min, refSegment); + int seg1End = segment1->findOtherT(max, refSegment); + int seg2Start = segment2->findOtherT(min, refSegment); + int seg2End = segment2->findOtherT(max, refSegment); + // if the opposite pairs already contain min/max, we're done + if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) { + return; + } + double loEnd = SkTMin(min1, min2); + double hiEnd = SkTMax(max1, max2); + // insert the missing coincident point(s) + double missingT1 = -1; + double otherT1 = -1; + if (seg1Start < 0) { + if (seg2Start < 0) { + return; + } + missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd, + segment2, seg1End); + if (missingT1 < 0) { + return; + } + const SkOpSpan* missingSpan = &segment2->span(seg2Start); + otherT1 = missingSpan->fT; + } else if (seg2Start < 0) { + SkASSERT(seg1Start >= 0); + missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd, + segment1, seg2End); + if (missingT1 < 0) { + return; + } + const SkOpSpan* missingSpan = &segment1->span(seg1Start); + otherT1 = missingSpan->fT; + } + SkPoint missingPt1; + SkOpSegment* addTo1 = NULL; + SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1; + int minTIndex = refSegment->findExactT(min, addOther1); + SkASSERT(minTIndex >= 0); + if (missingT1 >= 0) { + missingPt1 = refSegment->span(minTIndex).fPt; + addTo1 = seg1Start < 0 ? segment1 : segment2; + } + double missingT2 = -1; + double otherT2 = -1; + if (seg1End < 0) { + if (seg2End < 0) { + return; + } + missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd, + segment2, seg1Start); + if (missingT2 < 0) { + return; + } + const SkOpSpan* missingSpan = &segment2->span(seg2End); + otherT2 = missingSpan->fT; + } else if (seg2End < 0) { + SkASSERT(seg1End >= 0); + missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd, + segment1, seg2Start); + if (missingT2 < 0) { + return; + } + const SkOpSpan* missingSpan = &segment1->span(seg1End); + otherT2 = missingSpan->fT; + } + SkPoint missingPt2; + SkOpSegment* addTo2 = NULL; + SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1; + int maxTIndex = refSegment->findExactT(max, addOther2); + SkASSERT(maxTIndex >= 0); + if (missingT2 >= 0) { + missingPt2 = refSegment->span(maxTIndex).fPt; + addTo2 = seg1End < 0 ? segment1 : segment2; + } + if (missingT1 >= 0) { + addTo1->pinT(missingPt1, &missingT1); + addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1); + } else { + SkASSERT(minTIndex >= 0); + missingPt1 = refSegment->span(minTIndex).fPt; + } + if (missingT2 >= 0) { + addTo2->pinT(missingPt2, &missingT2); + addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2); + } else { + SkASSERT(minTIndex >= 0); + missingPt2 = refSegment->span(maxTIndex).fPt; + } + if (!partial) { + return; + } + if (cancelers) { + if (missingT1 >= 0) { + addTo1->addTCancel(missingPt1, missingPt2, addOther1); + } else { + addTo2->addTCancel(missingPt1, missingPt2, addOther2); + } + } else if (missingT1 >= 0) { + addTo1->addTCoincident(missingPt1, missingPt2, addTo1 == addTo2 ? missingT2 : otherT2, + addOther1); + } else { + addTo2->addTCoincident(missingPt2, missingPt1, addTo2 == addTo1 ? missingT1 : otherT1, + addOther2); } } @@ -196,9 +477,15 @@ void SkOpContour::joinCoincidence(const SkTArray& coinciden const SkCoincidence& coincidence = coincidences[index]; int thisIndex = coincidence.fSegments[0]; SkOpSegment& thisOne = fSegments[thisIndex]; + if (thisOne.done()) { + continue; + } SkOpContour* otherContour = coincidence.fOther; 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]; if (startT == endT) { // this can happen in very large compares @@ -211,8 +498,8 @@ void SkOpContour::joinCoincidence(const SkTArray& coinciden } bool swapStart = startT > endT; bool swapOther = oStartT > oEndT; - const SkPoint* startPt = &coincidence.fPts[0]; - const SkPoint* endPt = &coincidence.fPts[1]; + const SkPoint* startPt = &coincidence.fPts[0][0]; + const SkPoint* endPt = &coincidence.fPts[0][1]; if (swapStart) { SkTSwap(startT, endT); SkTSwap(oStartT, oEndT); @@ -243,6 +530,9 @@ void SkOpContour::joinCoincidence(const SkTArray& coinciden } void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { + if (coincidence.fNearly[0] && coincidence.fNearly[1]) { + return; + } int thisIndex = coincidence.fSegments[0]; SkOpSegment& thisOne = fSegments[thisIndex]; if (thisOne.done()) { @@ -256,8 +546,8 @@ void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) } double startT = coincidence.fTs[0][0]; double endT = coincidence.fTs[0][1]; - const SkPoint* startPt = &coincidence.fPts[0]; - const SkPoint* endPt = &coincidence.fPts[1]; + const SkPoint* startPt = &coincidence.fPts[0][0]; + const SkPoint* endPt = &coincidence.fPts[0][1]; bool cancelers; if ((cancelers = startT > endT)) { SkTSwap(startT, endT); @@ -291,6 +581,57 @@ void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) #endif } +void SkOpContour::resolveNearCoincidence() { + int count = fCoincidences.count(); + for (int index = 0; index < count; ++index) { + SkCoincidence& coincidence = fCoincidences[index]; + if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) { + continue; + } + int thisIndex = coincidence.fSegments[0]; + SkOpSegment& thisOne = fSegments[thisIndex]; + SkOpContour* otherContour = coincidence.fOther; + int otherIndex = coincidence.fSegments[1]; + SkOpSegment& other = otherContour->fSegments[otherIndex]; + if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { + // OPTIMIZATION: remove from coincidence array + continue; + } + #if DEBUG_CONCIDENT + thisOne.debugShowTs("-"); + other.debugShowTs("o"); + #endif + double startT = coincidence.fTs[0][0]; + double endT = coincidence.fTs[0][1]; + bool cancelers; + if ((cancelers = startT > endT)) { + SkTSwap(startT, endT); + } + if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing + if (endT <= 1 - FLT_EPSILON) { + endT += FLT_EPSILON; + SkASSERT(endT <= 1); + } else { + startT -= FLT_EPSILON; + SkASSERT(startT >= 0); + } + } + SkASSERT(!approximately_negative(endT - startT)); + double oStartT = coincidence.fTs[1][0]; + double oEndT = coincidence.fTs[1][1]; + if (oStartT > oEndT) { + SkTSwap(oStartT, oEndT); + cancelers ^= true; + } + SkASSERT(!approximately_negative(oEndT - oStartT)); + if (cancelers) { + thisOne.blindCancel(coincidence, &other); + } else { + thisOne.blindCoincident(coincidence, &other); + } + } +} + void SkOpContour::sortAngles() { int segmentCount = fSegments.count(); for (int test = 0; test < segmentCount; ++test) { diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index 7fad7a4..d1b3cd0 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -22,7 +22,8 @@ struct SkCoincidence { SkOpContour* fOther; int fSegments[2]; double fTs[2][2]; - SkPoint fPts[2]; + SkPoint fPts[2][2]; + int fNearly[2]; }; class SkOpContour { @@ -86,6 +87,28 @@ public: return fSegments[segIndex].addSelfT(pt, newT); } + void align(const SkOpSegment::AlignedSpan& aligned, bool swap, SkCoincidence* coincidence); + void alignCoincidence(const SkOpSegment::AlignedSpan& aligned, + SkTArray* coincidences); + + void alignCoincidence(const SkOpSegment::AlignedSpan& aligned) { + alignCoincidence(aligned, &fCoincidences); + alignCoincidence(aligned, &fPartialCoincidences); + } + + void alignMultiples(SkTDArray* aligned) { + int segmentCount = fSegments.count(); + for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { + SkOpSegment& segment = fSegments[sIndex]; + if (segment.hasMultiples()) { + segment.alignMultiples(aligned); + } + } + } + + void alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex, + bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const; + const SkPathOpsBounds& bounds() const { return fBounds; } @@ -127,6 +150,7 @@ public: SkOpSegment& segment = fSegments[sIndex]; if (segment.count() > 2) { segment.checkMultiples(); + fMultiples |= segment.hasMultiples(); } } } @@ -135,6 +159,7 @@ public: int segmentCount = fSegments.count(); for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { SkOpSegment& segment = fSegments[sIndex]; + // OPTIMIZATION : skip segments that are done? if (segment.hasSmall()) { segment.checkSmall(); } @@ -189,6 +214,10 @@ public: } } + bool hasMultiples() const { + return fMultiples; + } + void joinCoincidence() { joinCoincidence(fCoincidences, false); joinCoincidence(fPartialCoincidences, true); @@ -203,9 +232,11 @@ public: void reset() { fSegments.reset(); fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); - fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false; + fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = fMultiples = false; } + void resolveNearCoincidence(); + SkTArray& segments() { return fSegments; } @@ -284,11 +315,19 @@ public: // available to test routines only void dump() const; void dumpAngles() const; + void dumpCoincidence(const SkCoincidence& ) const; + void dumpCoincidences() const; + void dumpPt(int ) const; void dumpPts() const; + void dumpSpan(int ) const; void dumpSpans() const; private: + void alignPt(int index, SkPoint* point, int zeroPt) const; + int alignT(bool swap, int tIndex, SkIntersections* ts) const; void calcCommonCoincidentWinding(const SkCoincidence& ); + void checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx, + const SkCoincidence& twoCoin, int twoIdx, bool partial); void joinCoincidence(const SkTArray& , bool partial); void setBounds(); @@ -303,6 +342,7 @@ private: bool fContainsCubics; bool fContainsCurves; bool fDone; + bool fMultiples; // set if some segment has multiple identical intersections with other curves bool fOperand; // true for the second argument to a binary operator bool fXor; bool fOppXor; diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 0e48b3f..59e6d34 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -5,6 +5,7 @@ * found in the LICENSE file. */ #include "SkIntersections.h" +#include "SkOpContour.h" #include "SkOpSegment.h" #include "SkPathWriter.h" #include "SkTSort.h" @@ -187,7 +188,8 @@ 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__, + SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", + __FUNCTION__, debugID(), span(index).fT, span(endIndex).fT, SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); #endif return result; @@ -404,25 +406,24 @@ void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active void SkOpSegment::addEndSpan(int endIndex) { int spanCount = fTs.count(); - int angleIndex = fAngles.count(); int startIndex = endIndex - 1; while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) { ++startIndex; SkASSERT(startIndex < spanCount - 1); ++endIndex; } - fAngles.push_back().set(this, spanCount - 1, startIndex); + SkOpAngle& angle = fAngles.push_back(); + angle.set(this, spanCount - 1, startIndex); #if DEBUG_ANGLE - fAngles.back().setID(angleIndex); debugCheckPointsEqualish(endIndex, spanCount); #endif - setFromAngleIndex(endIndex, angleIndex); + setFromAngle(endIndex, &angle); } -void SkOpSegment::setFromAngleIndex(int endIndex, int angleIndex) { +void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) { int spanCount = fTs.count(); do { - fTs[endIndex].fFromAngleIndex = angleIndex; + fTs[endIndex].fFromAngle = angle; } while (++endIndex < spanCount); } @@ -448,89 +449,92 @@ void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) { fBounds.setQuadBounds(pts); } -int SkOpSegment::addSingletonAngleDown(int endIndex, SkOpSegment** otherPtr) { - int startIndex = findEndSpan(endIndex); - SkASSERT(startIndex > 0); - int spanIndex = endIndex - 1; - fSingletonAngles.push_back().set(this, spanIndex, startIndex - 1); - setFromAngleIndex(startIndex, fAngles.count() + fSingletonAngles.count() - 1); +SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr) { + int spanIndex = count() - 1; + int startIndex = nextExactSpan(spanIndex, -1); + SkASSERT(startIndex >= 0); + SkOpAngle& angle = fAngles.push_back(); + *anglePtr = ∠ + angle.set(this, spanIndex, startIndex); + setFromAngle(spanIndex, &angle); SkOpSegment* other; + int oStartIndex, oEndIndex; do { - other = fTs[spanIndex].fOther; - if (other->fTs[0].fWindValue) { + const SkOpSpan& span = fTs[spanIndex]; + SkASSERT(span.fT > 0); + other = span.fOther; + oStartIndex = span.fOtherIndex; + oEndIndex = other->nextExactSpan(oStartIndex, 1); + if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) { break; } + oEndIndex = oStartIndex; + oStartIndex = other->nextExactSpan(oEndIndex, -1); --spanIndex; - SkASSERT(fTs[spanIndex].fT == 1); - } while (true); - int oEndIndex = other->findStartSpan(0); - SkASSERT(oEndIndex > 0); - int otherIndex = other->fSingletonAngles.count(); - other->fSingletonAngles.push_back().set(other, 0, oEndIndex); - other->setToAngleIndex(oEndIndex, other->fAngles.count() + otherIndex); + } while (oStartIndex < 0 || !other->span(oStartIndex).fWindSum); + SkOpAngle& oAngle = other->fAngles.push_back(); + oAngle.set(other, oStartIndex, oEndIndex); + other->setToAngle(oEndIndex, &oAngle); *otherPtr = other; - return otherIndex; + return &oAngle; } -int SkOpSegment::addSingletonAngleUp(int start, SkOpSegment** otherPtr) { - int endIndex = findStartSpan(start); +SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) { + int endIndex = nextExactSpan(0, 1); SkASSERT(endIndex > 0); - int thisIndex = fSingletonAngles.count(); - fSingletonAngles.push_back().set(this, start, endIndex); - setToAngleIndex(endIndex, fAngles.count() + thisIndex); - int spanIndex = start; + SkOpAngle& angle = fAngles.push_back(); + *anglePtr = ∠ + angle.set(this, 0, endIndex); + setToAngle(endIndex, &angle); + int spanIndex = 0; SkOpSegment* other; - int oCount, oStartIndex; + int oStartIndex, oEndIndex; do { - other = fTs[spanIndex].fOther; - oCount = other->count(); - oStartIndex = other->findEndSpan(oCount); - SkASSERT(oStartIndex > 0); - if (other->fTs[oStartIndex - 1].fWindValue) { + const SkOpSpan& span = fTs[spanIndex]; + SkASSERT(span.fT < 1); + other = span.fOther; + oEndIndex = span.fOtherIndex; + oStartIndex = other->nextExactSpan(oEndIndex, -1); + if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) { break; } + oStartIndex = oEndIndex; + oEndIndex = other->nextExactSpan(oStartIndex, 1); ++spanIndex; - SkASSERT(fTs[spanIndex].fT == 0); - } while (true); - int otherIndex = other->fSingletonAngles.count(); - other->fSingletonAngles.push_back().set(other, oCount - 1, oStartIndex - 1); - other->setFromAngleIndex(oStartIndex, other->fAngles.count() + otherIndex); + } while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue); + SkOpAngle& oAngle = other->fAngles.push_back(); + oAngle.set(other, oEndIndex, oStartIndex); + other->setFromAngle(oEndIndex, &oAngle); *otherPtr = other; - return otherIndex; + return &oAngle; } -SkOpAngle* SkOpSegment::addSingletonAngles(int start, int step) { - int thisIndex = fSingletonAngles.count(); +SkOpAngle* SkOpSegment::addSingletonAngles(int step) { SkOpSegment* other; - int otherIndex; + SkOpAngle* angle, * otherAngle; if (step > 0) { - otherIndex = addSingletonAngleUp(start, &other); + otherAngle = addSingletonAngleUp(&other, &angle); } else { - otherIndex = addSingletonAngleDown(start + 1, &other); + otherAngle = addSingletonAngleDown(&other, &angle); } - fSingletonAngles[thisIndex].insert(&other->fSingletonAngles[otherIndex]); -#if DEBUG_ANGLE - fSingletonAngles[thisIndex].setID(fAngles.count() + thisIndex); - other->fSingletonAngles[otherIndex].setID(other->fAngles.count() + otherIndex); -#endif - return &fSingletonAngles[thisIndex]; + angle->insert(otherAngle); + return angle; } void SkOpSegment::addStartSpan(int endIndex) { - int angleIndex = fAngles.count(); int index = 0; - fAngles.push_back().set(this, index, endIndex); + SkOpAngle& angle = fAngles.push_back(); + angle.set(this, index, endIndex); #if DEBUG_ANGLE - fAngles.back().setID(angleIndex); debugCheckPointsEqualish(index, endIndex); #endif - setToAngleIndex(endIndex, angleIndex); + setToAngle(endIndex, &angle); } -void SkOpSegment::setToAngleIndex(int endIndex, int angleIndex) { +void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) { int index = 0; do { - fTs[index].fToAngleIndex = angleIndex; + fTs[index].fToAngle = angle; } while (++index < endIndex); } @@ -546,17 +550,14 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { #if 0 // this needs an even rougher association to be useful SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt)); #endif - if (precisely_zero(newT)) { - newT = 0; - } else if (precisely_equal(newT, 1)) { - newT = 1; - } + const SkPoint& firstPt = fPts[0]; + const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)]; + SkASSERT(newT == 0 || !precisely_zero(newT)); + SkASSERT(newT == 1 || !precisely_equal(newT, 1)); // FIXME: in the pathological case where there is a ton of intercepts, // binary search? int insertedAt = -1; int tCount = fTs.count(); - const SkPoint& firstPt = fPts[0]; - const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)]; for (int index = 0; index < tCount; ++index) { // OPTIMIZATION: if there are three or more identical Ts, then // the fourth and following could be further insertion-sorted so @@ -588,6 +589,9 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { span = fTs.append(); } span->fT = newT; +#if SK_DEBUG + span->fOtherT = -1; +#endif span->fOther = other; span->fPt = pt; #if 0 @@ -595,20 +599,24 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX) && approximately_equal(xyAtT(newT).fY, pt.fY)); #endif - span->fFromAngleIndex = -1; - span->fToAngleIndex = -1; + span->fFromAngle = NULL; + span->fToAngle = NULL; span->fWindSum = SK_MinS32; span->fOppSum = SK_MinS32; span->fWindValue = 1; span->fOppValue = 0; span->fChased = false; - if ((span->fDone = newT == 1)) { - ++fDoneSpans; - } + span->fCoincident = false; span->fLoop = false; + span->fNear = false; + span->fMultiple = false; span->fSmall = false; span->fTiny = false; + if ((span->fDone = newT == 1)) { + ++fDoneSpans; + } int less = -1; +// FIXME: note that this relies on spans being a continguous array // find range of spans with nearly the same point as this one while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) { if (fVerb == SkPath::kCubic_Verb) { @@ -687,6 +695,7 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS while (index > 0 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) { --index; } + bool oFoundEnd = false; int oIndex = other->fTs.count(); while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match SkASSERT(oIndex > 0); @@ -700,15 +709,19 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS SkOpSpan* oTest = &other->fTs[oIndex]; SkSTArray outsidePts; SkSTArray oOutsidePts; + bool decrement, track, bigger; + int originalWindValue; + const SkPoint* testPt; + const SkPoint* oTestPt; 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; - const SkPoint& testPt = test->fPt; + decrement = test->fWindValue && oTest->fWindValue; + track = test->fWindValue || oTest->fWindValue; + bigger = test->fWindValue >= oTest->fWindValue; + testPt = &test->fPt; double testT = test->fT; - const SkPoint& oTestPt = oTest->fPt; + oTestPt = &oTest->fPt; double oTestT = oTest->fT; do { if (decrement) { @@ -718,12 +731,12 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS decrementSpan(test); } } else if (track) { - TrackOutsidePair(&outsidePts, testPt, oTestPt); + TrackOutsidePair(&outsidePts, *testPt, *oTestPt); } SkASSERT(index < fTs.count() - 1); test = &fTs[++index]; - } while (testPt == test->fPt || precisely_equal(testT, test->fT)); - SkDEBUGCODE(int originalWindValue = oTest->fWindValue); + } while (*testPt == test->fPt || precisely_equal(testT, test->fT)); + originalWindValue = oTest->fWindValue; do { SkASSERT(oTest->fT < 1); SkASSERT(originalWindValue == oTest->fWindValue); @@ -734,15 +747,48 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS other->decrementSpan(oTest); } } else if (track) { - TrackOutsidePair(&oOutsidePts, oTestPt, testPt); + TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt); } if (!oIndex) { break; } + oFoundEnd |= endPt == oTest->fPt; oTest = &other->fTs[--oIndex]; - } while (oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT)); + } while (*oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT)); } while (endPt != test->fPt && test->fT < 1); // FIXME: determine if canceled edges need outside ts added + if (!oFoundEnd) { + for (int oIdx2 = oIndex; oIdx2 >= 0; --oIdx2) { + SkOpSpan* oTst2 = &other->fTs[oIdx2]; + if (originalWindValue != oTst2->fWindValue) { + goto skipAdvanceOtherCancel; + } + if (!oTst2->fWindValue) { + goto skipAdvanceOtherCancel; + } + if (endPt == other->fTs[oIdx2].fPt) { + break; + } + } + do { + SkASSERT(originalWindValue == oTest->fWindValue); + if (decrement) { + if (binary && !bigger) { + oTest->fOppValue--; + } else { + other->decrementSpan(oTest); + } + } else if (track) { + TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt); + } + if (!oIndex) { + break; + } + oTest = &other->fTs[--oIndex]; + oFoundEnd |= endPt == oTest->fPt; + } while (!oFoundEnd || endPt == oTest->fPt); + } +skipAdvanceOtherCancel: int outCount = outsidePts.count(); if (!done() && outCount) { addCancelOutsides(outsidePts[0], outsidePts[1], other); @@ -753,6 +799,8 @@ void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpS if (!other->done() && oOutsidePts.count()) { other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this); } + setCoincidentRange(startPt, endPt, other); + other->setCoincidentRange(startPt, endPt, this); } int SkOpSegment::addSelfT(const SkPoint& pt, double newT) { @@ -763,48 +811,153 @@ int SkOpSegment::addSelfT(const SkPoint& pt, double newT) { return result; } +// find the starting or ending span with an existing loop of angles +// FIXME? replicate for all identical starting/ending spans? +// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier? +// FIXME? assert that only one other span has a valid windValue or oppValue void SkOpSegment::addSimpleAngle(int index) { + SkOpSpan* span = &fTs[index]; if (index == 0) { - SkASSERT(!fTs[index].fTiny && fTs[index + 1].fT > 0); + do { + if (span->fToAngle) { + SkASSERT(span->fToAngle->loopCount() == 2); + SkASSERT(!span->fFromAngle); + span->fFromAngle = span->fToAngle->next(); + return; + } + span = &fTs[++index]; + } while (span->fT == 0); + SkASSERT(index == 1); + index = 0; + SkASSERT(!fTs[0].fTiny && fTs[1].fT > 0); addStartSpan(1); } else { + do { + if (span->fFromAngle) { + SkASSERT(span->fFromAngle->loopCount() == 2); + SkASSERT(!span->fToAngle); + span->fToAngle = span->fFromAngle->next(); + return; + } + span = &fTs[--index]; + } while (span->fT == 1); + SkASSERT(index == count() - 2); + index = count() - 1; SkASSERT(!fTs[index - 1].fTiny && fTs[index - 1].fT < 1); addEndSpan(index); } - SkOpSpan& span = fTs[index]; - SkOpSegment* other = span.fOther; - SkOpSpan& oSpan = other->fTs[span.fOtherIndex]; + span = &fTs[index]; + SkOpSegment* other = span->fOther; + SkOpSpan& oSpan = other->fTs[span->fOtherIndex]; SkOpAngle* angle, * oAngle; if (index == 0) { - SkASSERT(span.fOtherIndex - 1 >= 0); - SkASSERT(span.fOtherT == 1); - SkDEBUGCODE(SkOpSpan& oPrior = other->fTs[span.fOtherIndex - 1]); + SkASSERT(span->fOtherIndex - 1 >= 0); + SkASSERT(span->fOtherT == 1); + SkDEBUGCODE(SkOpSpan& oPrior = other->fTs[span->fOtherIndex - 1]); SkASSERT(!oPrior.fTiny && oPrior.fT < 1); - other->addEndSpan(span.fOtherIndex); - angle = &this->angle(span.fToAngleIndex); - oAngle = &other->angle(oSpan.fFromAngleIndex); + other->addEndSpan(span->fOtherIndex); + angle = span->fToAngle; + oAngle = oSpan.fFromAngle; } else { - SkASSERT(span.fOtherIndex + 1 < other->count()); - SkASSERT(span.fOtherT == 0); - SkASSERT(!oSpan.fTiny && (other->fTs[span.fOtherIndex + 1].fT > 0 - || (other->fTs[span.fOtherIndex + 1].fFromAngleIndex < 0 - && other->fTs[span.fOtherIndex + 1].fToAngleIndex < 0))); + SkASSERT(span->fOtherIndex + 1 < other->count()); + SkASSERT(span->fOtherT == 0); + SkASSERT(!oSpan.fTiny && (other->fTs[span->fOtherIndex + 1].fT > 0 + || (other->fTs[span->fOtherIndex + 1].fFromAngle == NULL + && other->fTs[span->fOtherIndex + 1].fToAngle == NULL))); int oIndex = 1; do { const SkOpSpan& osSpan = other->span(oIndex); - if (osSpan.fFromAngleIndex >= 0 || osSpan.fT > 0) { + if (osSpan.fFromAngle || osSpan.fT > 0) { break; } ++oIndex; SkASSERT(oIndex < other->count()); } while (true); other->addStartSpan(oIndex); - angle = &this->angle(span.fFromAngleIndex); - oAngle = &other->angle(oSpan.fToAngleIndex); + angle = span->fFromAngle; + oAngle = oSpan.fToAngle; } angle->insert(oAngle); } +void SkOpSegment::alignMultiples(SkTDArray* alignedArray) { + debugValidate(); + int count = this->count(); + for (int index = 0; index < count; ++index) { + SkOpSpan& span = fTs[index]; + if (!span.fMultiple) { + continue; + } + int end = nextExactSpan(index, 1); + SkASSERT(end > index + 1); + const SkPoint& thisPt = span.fPt; + while (index < end - 1) { + SkOpSegment* other1 = span.fOther; + int oCnt = other1->count(); + for (int idx2 = index + 1; idx2 < end; ++idx2) { + SkOpSpan& span2 = fTs[idx2]; + SkOpSegment* other2 = span2.fOther; + for (int oIdx = 0; oIdx < oCnt; ++oIdx) { + SkOpSpan& oSpan = other1->fTs[oIdx]; + if (oSpan.fOther != other2) { + continue; + } + if (oSpan.fPt == thisPt) { + goto skipExactMatches; + } + } + for (int oIdx = 0; oIdx < oCnt; ++oIdx) { + SkOpSpan& oSpan = other1->fTs[oIdx]; + if (oSpan.fOther != other2) { + continue; + } + if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) { + SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex]; + if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT) + || zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) { + return; + } + if (!way_roughly_equal(span.fOtherT, oSpan.fT) + || !way_roughly_equal(span2.fOtherT, oSpan2.fT) + || !way_roughly_equal(span2.fOtherT, oSpan.fOtherT) + || !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) { + return; + } + alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT, + other2, &oSpan, alignedArray); + alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT, + other1, &oSpan2, alignedArray); + break; + } + } + skipExactMatches: + ; + } + ++index; + } + } + debugValidate(); +} + +void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other, + double otherT, const SkOpSegment* other2, SkOpSpan* oSpan, + SkTDArray* alignedArray) { + AlignedSpan* aligned = alignedArray->append(); + aligned->fOldPt = oSpan->fPt; + aligned->fPt = newPt; + aligned->fOldT = oSpan->fT; + aligned->fT = newT; + aligned->fSegment = this; // OPTIMIZE: may be unused, can remove + aligned->fOther1 = other; + aligned->fOther2 = other2; + SkASSERT(SkDPoint::RoughlyEqual(oSpan->fPt, newPt)); + oSpan->fPt = newPt; +// SkASSERT(way_roughly_equal(oSpan->fT, newT)); + oSpan->fT = newT; +// SkASSERT(way_roughly_equal(oSpan->fOtherT, otherT)); + oSpan->fOtherT = otherT; +} + bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) { bool aligned = false; SkOpSpan* span = &fTs[index]; @@ -877,6 +1030,156 @@ void SkOpSegment::alignSpanState(int start, int end) { } } +void SkOpSegment::blindCancel(const SkCoincidence& coincidence, SkOpSegment* other) { + bool binary = fOperand != other->fOperand; + int index = 0; + int last = this->count(); + do { + SkOpSpan& span = this->fTs[--last]; + if (span.fT != 1 && !span.fSmall) { + break; + } + span.fCoincident = true; + } while (true); + int oIndex = other->count(); + do { + SkOpSpan& oSpan = other->fTs[--oIndex]; + if (oSpan.fT != 1 && !oSpan.fSmall) { + break; + } + oSpan.fCoincident = true; + } while (true); + do { + SkOpSpan* test = &this->fTs[index]; + int baseWind = test->fWindValue; + int baseOpp = test->fOppValue; + int endIndex = index; + while (++endIndex <= last) { + SkOpSpan* endSpan = &this->fTs[endIndex]; + SkASSERT(endSpan->fT < 1); + if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) { + break; + } + endSpan->fCoincident = true; + } + SkOpSpan* oTest = &other->fTs[oIndex]; + int oBaseWind = oTest->fWindValue; + int oBaseOpp = oTest->fOppValue; + int oStartIndex = oIndex; + while (--oStartIndex >= 0) { + SkOpSpan* oStartSpan = &other->fTs[oStartIndex]; + if (oStartSpan->fWindValue != oBaseWind || oStartSpan->fOppValue != oBaseOpp) { + break; + } + oStartSpan->fCoincident = true; + } + bool decrement = baseWind && oBaseWind; + bool bigger = baseWind >= oBaseWind; + do { + SkASSERT(test->fT < 1); + if (decrement) { + if (binary && bigger) { + test->fOppValue--; + } else { + decrementSpan(test); + } + } + test->fCoincident = true; + test = &fTs[++index]; + } while (index < endIndex); + do { + SkASSERT(oTest->fT < 1); + if (decrement) { + if (binary && !bigger) { + oTest->fOppValue--; + } else { + other->decrementSpan(oTest); + } + } + oTest->fCoincident = true; + oTest = &other->fTs[--oIndex]; + } while (oIndex > oStartIndex); + } while (index <= last && oIndex >= 0); + SkASSERT(index > last); + SkASSERT(oIndex < 0); +} + +void SkOpSegment::blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other) { + bool binary = fOperand != other->fOperand; + int index = 0; + int last = this->count(); + do { + SkOpSpan& span = this->fTs[--last]; + if (span.fT != 1 && !span.fSmall) { + break; + } + span.fCoincident = true; + } while (true); + int oIndex = 0; + int oLast = other->count(); + do { + SkOpSpan& oSpan = other->fTs[--oLast]; + if (oSpan.fT != 1 && !oSpan.fSmall) { + break; + } + oSpan.fCoincident = true; + } while (true); + do { + SkOpSpan* test = &this->fTs[index]; + int baseWind = test->fWindValue; + int baseOpp = test->fOppValue; + int endIndex = index; + SkOpSpan* endSpan; + while (++endIndex <= last) { + endSpan = &this->fTs[endIndex]; + SkASSERT(endSpan->fT < 1); + if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) { + break; + } + endSpan->fCoincident = true; + } + SkOpSpan* oTest = &other->fTs[oIndex]; + int oBaseWind = oTest->fWindValue; + int oBaseOpp = oTest->fOppValue; + int oEndIndex = oIndex; + SkOpSpan* oEndSpan; + while (++oEndIndex <= oLast) { + oEndSpan = &this->fTs[oEndIndex]; + SkASSERT(oEndSpan->fT < 1); + if (oEndSpan->fWindValue != oBaseWind || oEndSpan->fOppValue != oBaseOpp) { + break; + } + oEndSpan->fCoincident = true; + } + // consolidate the winding count even if done + if ((test->fWindValue || test->fOppValue) && (oTest->fWindValue || oTest->fOppValue)) { + if (!binary || test->fWindValue + oTest->fOppValue >= 0) { + bumpCoincidentBlind(binary, index, endIndex); + other->bumpCoincidentOBlind(oIndex, oEndIndex); + } else { + other->bumpCoincidentBlind(binary, oIndex, oEndIndex); + bumpCoincidentOBlind(index, endIndex); + } + } + index = endIndex; + oIndex = oEndIndex; + } while (index <= last && oIndex <= oLast); + SkASSERT(index > last); + SkASSERT(oIndex > oLast); +} + +void SkOpSegment::bumpCoincidentBlind(bool binary, int index, int endIndex) { + const SkOpSpan& oTest = fTs[index]; + int oWindValue = oTest.fWindValue; + int oOppValue = oTest.fOppValue; + if (binary) { + SkTSwap(oWindValue, oOppValue); + } + do { + (void) bumpSpan(&fTs[index], oWindValue, oOppValue); + } while (++index < endIndex); +} + void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr, SkTArray* outsideTs) { int index = *indexPtr; @@ -897,6 +1200,12 @@ void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* in *indexPtr = index; } +void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) { + do { + zeroSpan(&fTs[index]); + } while (++index < endIndex); +} + // 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) @@ -1025,13 +1334,13 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d int oPeekIndex = oIndex; bool success = true; SkOpSpan* oPeek; + int oCount = other->count(); do { oPeek = &other->fTs[oPeekIndex]; - if (oPeek->fT == 1) { + if (++oPeekIndex == oCount) { success = false; break; } - ++oPeekIndex; } while (endPt != oPeek->fPt); if (success) { // make sure the matching point completes the coincidence span @@ -1063,12 +1372,14 @@ void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, d if (!other->done() && oOutsidePts.count()) { other->addCoinOutsides(oOutsidePts[0], endPt, this); } + setCoincidentRange(startPt, endPt, other); + other->setCoincidentRange(startPt, endPt, this); } // FIXME: this doesn't prevent the same span from being added twice // fix in caller, SkASSERT here? const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, - const SkPoint& pt) { + const SkPoint& pt, const SkPoint& pt2) { int tCount = fTs.count(); for (int tIndex = 0; tIndex < tCount; ++tIndex) { const SkOpSpan& span = fTs[tIndex]; @@ -1089,24 +1400,23 @@ const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double other __FUNCTION__, fID, t, other->fID, otherT); #endif int insertedAt = addT(other, pt, t); - int otherInsertedAt = other->addT(this, pt, otherT); + int otherInsertedAt = other->addT(this, pt2, otherT); addOtherT(insertedAt, otherT, otherInsertedAt); other->addOtherT(otherInsertedAt, t, insertedAt); matchWindingValue(insertedAt, t, borrowWind); other->matchWindingValue(otherInsertedAt, otherT, borrowWind); - return &span(insertedAt); + SkOpSpan& span = this->fTs[insertedAt]; + if (pt != pt2) { + span.fNear = true; + SkOpSpan& oSpan = other->fTs[otherInsertedAt]; + oSpan.fNear = true; + } + return &span; } -const SkOpAngle& SkOpSegment::angle(int index) const { - SkASSERT(index >= 0); - int count = fAngles.count(); - if (index < count) { - return fAngles[index]; - } - index -= count; - count = fSingletonAngles.count(); - SkASSERT(index < count); - return fSingletonAngles[index]; +const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, + const SkPoint& pt) { + return addTPair(t, other, otherT, borrowWind, pt, pt); } bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const { @@ -1138,9 +1448,7 @@ bool SkOpSegment::calcAngles() { const SkOpSpan* span = &fTs[0]; if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) { index = findStartSpan(0); // curve start intersects - if (index < 0) { - return false; - } + SkASSERT(index > 0); if (activePrior >= 0) { addStartSpan(index); } @@ -1150,9 +1458,7 @@ bool SkOpSegment::calcAngles() { span = &fTs[endIndex - 1]; if ((addEnd = span->fT == 1 || span->fTiny)) { // if curve end intersects endIndex = findEndSpan(endIndex); - if (endIndex < 0) { - return false; - } + SkASSERT(endIndex > 0); } else { addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts(); } @@ -1174,24 +1480,19 @@ bool SkOpSegment::calcAngles() { return false; } } while (true); - int angleIndex = fAngles.count(); - int priorAngleIndex; + SkOpAngle* angle = NULL; + SkOpAngle* priorAngle; if (activePrior >= 0) { int pActive = firstActive(prior); SkASSERT(pActive < start); - fAngles.push_back().set(this, start, pActive); - priorAngleIndex = angleIndex++; - #if DEBUG_ANGLE - fAngles.back().setID(priorAngleIndex); - #endif + priorAngle = &fAngles.push_back(); + priorAngle->set(this, start, pActive); } int active = checkSetAngle(start); if (active >= 0) { SkASSERT(active < index); - fAngles.push_back().set(this, active, index); - #if DEBUG_ANGLE - fAngles.back().setID(angleIndex); - #endif + angle = &fAngles.push_back(); + angle->set(this, active, index); } #if DEBUG_ANGLE debugCheckPointsEqualish(start, index); @@ -1199,20 +1500,20 @@ bool SkOpSegment::calcAngles() { prior = start; do { const SkOpSpan* startSpan = &fTs[start - 1]; - if (!startSpan->fSmall || startSpan->fFromAngleIndex >= 0 - || startSpan->fToAngleIndex >= 0) { + if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle + || startSpan->fToAngle) { break; } --start; } while (start > 0); do { if (activePrior >= 0) { - SkASSERT(fTs[start].fFromAngleIndex == -1); - fTs[start].fFromAngleIndex = priorAngleIndex; + SkASSERT(fTs[start].fFromAngle == NULL); + fTs[start].fFromAngle = priorAngle; } if (active >= 0) { - SkASSERT(fTs[start].fToAngleIndex == -1); - fTs[start].fToAngleIndex = angleIndex; + SkASSERT(fTs[start].fToAngle == NULL); + fTs[start].fToAngle = angle; } } while (++start < index); activePrior = active; @@ -1231,7 +1532,7 @@ int SkOpSegment::checkSetAngle(int tIndex) const { return isCanceled(tIndex) ? -1 : tIndex; } -// at this point, the span is already ordered, or unorderable, or unsortable +// at this point, the span is already ordered, or unorderable int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) { SkASSERT(includeType != SkOpAngle::kUnaryXor); SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex); @@ -1242,50 +1543,61 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType // 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 + // if two orderable angles are adjacent, and both are next to orderable angles, + // and one has winding computed, transfer to the other SkOpAngle* baseAngle = NULL; bool tryReverse = false; // look for counterclockwise transfers - SkOpAngle* angle = firstAngle; + SkOpAngle* angle = firstAngle->previous(); + SkOpAngle* next = angle->next(); + firstAngle = next; do { - int testWinding = angle->segment()->windSum(angle); - if (SK_MinS32 != testWinding && !angle->unorderable()) { - baseAngle = angle; + SkOpAngle* prior = angle; + angle = next; + next = angle->next(); + SkASSERT(prior->next() == angle); + SkASSERT(angle->next() == next); + if (prior->unorderable() || angle->unorderable() || next->unorderable()) { + baseAngle = NULL; continue; } - if (angle->unorderable()) { - baseAngle = NULL; + int testWinding = angle->segment()->windSum(angle); + if (SK_MinS32 != testWinding) { + baseAngle = angle; tryReverse = true; continue; } if (baseAngle) { ComputeOneSum(baseAngle, angle, includeType); baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL; - tryReverse |= !baseAngle; } - } while ((angle = angle->next()) != firstAngle); - if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(angle)) { + } while (next != firstAngle); + if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) { firstAngle = baseAngle; tryReverse = true; } if (tryReverse) { baseAngle = NULL; - angle = firstAngle; + SkOpAngle* prior = firstAngle; do { + angle = prior; + prior = angle->previous(); + SkASSERT(prior->next() == angle); + next = angle->next(); + if (prior->unorderable() || angle->unorderable() || next->unorderable()) { + baseAngle = NULL; + continue; + } int testWinding = angle->segment()->windSum(angle); if (SK_MinS32 != testWinding) { baseAngle = angle; continue; } - if (angle->unorderable()) { - baseAngle = NULL; - continue; - } if (baseAngle) { ComputeOneSumReverse(baseAngle, angle, includeType); baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL; } - } while ((angle = angle->previous()) != firstAngle); + } while (prior != firstAngle); } int minIndex = SkMin32(startIndex, endIndex); return windSum(minIndex); @@ -1362,6 +1674,31 @@ bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const { return false; } +bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = fTs[index]; + if (t < span.fT) { + return false; + } + if (t == span.fT) { + if (other != span.fOther) { + continue; + } + if (other->fVerb != SkPath::kCubic_Verb) { + return true; + } + if (!other->fLoop) { + return true; + } + double otherMidT = (otherT + span.fOtherT) / 2; + SkPoint otherPt = other->ptAtT(otherMidT); + return SkDPoint::ApproximatelyEqual(span.fPt, otherPt); + } + } + return false; +} + int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const { SkScalar bottom = fBounds.fBottom; @@ -1542,6 +1879,58 @@ bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) return true; } +double SkOpSegment::calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max, + double hiEnd, const SkOpSegment* other, int thisStart) { + if (max >= hiEnd) { + return -1; + } + int end = findOtherT(hiEnd, ref); + if (end < 0) { + return -1; + } + double tHi = span(end).fT; + double tLo, refLo; + if (thisStart >= 0) { + tLo = span(thisStart).fT; + refLo = min; + } else { + int start1 = findOtherT(loEnd, ref); + SkASSERT(start1 >= 0); + tLo = span(start1).fT; + refLo = loEnd; + } + double missingT = (max - refLo) / (hiEnd - refLo); + missingT = tLo + missingT * (tHi - tLo); + return missingT; +} + +double SkOpSegment::calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max, + double hiEnd, const SkOpSegment* other, int thisEnd) { + if (min <= loEnd) { + return -1; + } + int start = findOtherT(loEnd, ref); + if (start < 0) { + return -1; + } + double tLo = span(start).fT; + double tHi, refHi; + if (thisEnd >= 0) { + tHi = span(thisEnd).fT; + refHi = max; + } else { + int end1 = findOtherT(hiEnd, ref); + if (end1 < 0) { + return -1; + } + tHi = span(end1).fT; + refHi = hiEnd; + } + double missingT = (min - loEnd) / (refHi - loEnd); + missingT = tLo + missingT * (tHi - tLo); + return missingT; +} + // see if spans with two or more intersections have the same number on the other end void SkOpSegment::checkDuplicates() { debugValidate(); @@ -1561,6 +1950,9 @@ void SkOpSegment::checkDuplicates() { } do { const SkOpSpan* thisSpan = &fTs[index]; + if (thisSpan->fNear) { + continue; + } SkOpSegment* other = thisSpan->fOther; int oIndex = thisSpan->fOtherIndex; int oStart = other->nextExactSpan(oIndex, -1) + 1; @@ -1602,6 +1994,33 @@ void SkOpSegment::checkDuplicates() { if (missing.fSegment == missing.fOther) { continue; } +#if 0 // FIXME: this eliminates spurious data from skpwww_argus_presse_fr_41 but breaks + // skpwww_fashionscandal_com_94 -- calcAngles complains, but I don't understand why + if (missing.fSegment->containsT(missing.fT, missing.fOther, missing.fOtherT)) { +#if DEBUG_DUPLICATES + SkDebugf("skip 1 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fSegment->fID, + missing.fT, missing.fOther->fID, missing.fOtherT); +#endif + continue; + } + if (missing.fOther->containsT(missing.fOtherT, missing.fSegment, missing.fT)) { +#if DEBUG_DUPLICATES + SkDebugf("skip 2 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fOther->fID, + missing.fOtherT, missing.fSegment->fID, missing.fT); +#endif + continue; + } +#endif + // skip if adding would insert point into an existing coincindent span + if (missing.fSegment->inCoincidentSpan(missing.fT, missingOther) + && missingOther->inCoincidentSpan(missing.fOtherT, this)) { + continue; + } + // skip if the created coincident spans are small + if (missing.fSegment->coincidentSmall(missing.fPt, missing.fT, missingOther) + && missingOther->coincidentSmall(missing.fPt, missing.fOtherT, missing.fSegment)) { + continue; + } const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther, missing.fOtherT, false, missing.fPt); if (added && added->fSmall) { @@ -1777,8 +2196,10 @@ void SkOpSegment::checkMultiples() { continue; } // force the duplicates to agree on t and pt if not on the end - double thisT = fTs[index].fT; - const SkPoint& thisPt = fTs[index].fPt; + SkOpSpan& span = fTs[index]; + double thisT = span.fT; + const SkPoint& thisPt = span.fPt; + span.fMultiple = true; bool aligned = false; while (++index < end) { aligned |= alignSpan(index, thisT, thisPt); @@ -1786,6 +2207,7 @@ void SkOpSegment::checkMultiples() { if (aligned) { alignSpanState(start, end); } + fMultiples = true; } debugValidate(); } @@ -2146,6 +2568,30 @@ void SkOpSegment::checkTiny() { } } +bool SkOpSegment::coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = this->span(index); + if (span.fOther != other) { + continue; + } + if (span.fPt == pt) { + continue; + } + if (!AlmostEqualUlps(span.fPt, pt)) { + continue; + } + if (fVerb != SkPath::kCubic_Verb) { + return true; + } + double tInterval = t - span.fT; + double tMid = t - tInterval / 2; + SkDPoint midPt = dcubic_xy_at_t(fPts, tMid); + return midPt.approximatelyEqual(xyAtT(t)); + } + return false; +} + bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const { SkASSERT(span->fT == 0 || span->fT == 1); @@ -2235,12 +2681,11 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray* chase, int* nextStart SkASSERT(startIndex != endIndex); SkDEBUGCODE(const int count = fTs.count()); SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); - const int step = SkSign32(endIndex - startIndex); - const int end = nextExactSpan(startIndex, step); - SkASSERT(end >= 0); - SkOpSpan* endSpan = &fTs[end]; - SkOpSegment* other; - if (isSimple(end)) { + int step = SkSign32(endIndex - startIndex); + *nextStart = startIndex; + SkOpSegment* other = isSimple(nextStart, &step); + if (other) + { // mark the smaller of startIndex, endIndex done, and all adjacent // spans with the same T value (but not 'other' spans) #if DEBUG_WINDING @@ -2251,8 +2696,6 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray* chase, int* nextStart return NULL; } markDoneBinary(min); - other = endSpan->fOther; - *nextStart = endSpan->fOtherIndex; double startT = other->fTs[*nextStart].fT; *nextEnd = *nextStart; do { @@ -2265,6 +2708,8 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray* chase, int* nextStart } return other; } + const int end = nextExactSpan(startIndex, step); + SkASSERT(end >= 0); SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); // more than one viable candidate -- measure angles to find best @@ -2325,7 +2770,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray* chase, int* nextStart continue; } if (!activeAngle) { - nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end()); + (void) nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end()); } SkOpSpan* last = nextAngle->lastMarked(); if (last) { @@ -2365,12 +2810,11 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray* chase, int* next SkASSERT(startIndex != endIndex); SkDEBUGCODE(const int count = fTs.count()); SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); - const int step = SkSign32(endIndex - startIndex); - const int end = nextExactSpan(startIndex, step); - SkASSERT(end >= 0); - SkOpSpan* endSpan = &fTs[end]; - SkOpSegment* other; - if (isSimple(end)) { + int step = SkSign32(endIndex - startIndex); + *nextStart = startIndex; + SkOpSegment* other = isSimple(nextStart, &step); + if (other) + { // mark the smaller of startIndex, endIndex done, and all adjacent // spans with the same T value (but not 'other' spans) #if DEBUG_WINDING @@ -2381,8 +2825,6 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray* chase, int* next return NULL; } markDoneUnary(min); - other = endSpan->fOther; - *nextStart = endSpan->fOtherIndex; double startT = other->fTs[*nextStart].fT; *nextEnd = *nextStart; do { @@ -2395,6 +2837,8 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray* chase, int* next } return other; } + const int end = nextExactSpan(startIndex, step); + SkASSERT(end >= 0); SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); // more than one viable candidate -- measure angles to find best @@ -2474,13 +2918,12 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort SkDEBUGCODE(int count = fTs.count()); SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0); int step = SkSign32(endIndex - startIndex); - int end = nextExactSpan(startIndex, step); - SkASSERT(end >= 0); - SkOpSpan* endSpan = &fTs[end]; - SkOpSegment* other; // Detect cases where all the ends canceled out (e.g., -// there is no angle) and therefore there's only one valid connection - if (isSimple(end) || !spanToAngle(end, startIndex)) { +// there is no angle) and therefore there's only one valid connection + *nextStart = startIndex; + SkOpSegment* other = isSimple(nextStart, &step); + if (other) + { #if DEBUG_WINDING SkDebugf("%s simple\n", __FUNCTION__); #endif @@ -2489,8 +2932,6 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort return NULL; } markDone(min, 1); - other = endSpan->fOther; - *nextStart = endSpan->fOtherIndex; double startT = other->fTs[*nextStart].fT; // FIXME: I don't know why the logic here is difference from the winding case SkDEBUGCODE(bool firstLoop = true;) @@ -2517,6 +2958,8 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort SkASSERT(startIndex - endIndex != 0); SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); // parallel block above with presorted version + int end = nextExactSpan(startIndex, step); + SkASSERT(end >= 0); SkOpAngle* angle = spanToAngle(end, startIndex); SkASSERT(angle); #if DEBUG_SORT @@ -2562,24 +3005,12 @@ int SkOpSegment::findStartSpan(int startIndex) const { const SkOpSpan* span = &fTs[index]; const SkPoint& firstPt = span->fPt; double firstT = span->fT; + const SkOpSpan* prior; do { - if (index > 0) { - if (span->fT != firstT) { - break; - } - if (!SkDPoint::ApproximatelyEqual(firstPt, fTs[index].fPt)) { - return -1; - } - } - ++index; - if (span->fTiny) { - if (!SkDPoint::ApproximatelyEqual(firstPt, fTs[index].fPt)) { - return -1; - } - firstT = fTs[index++].fT; - } - span = &fTs[index]; - } while (true); + prior = span; + span = &fTs[++index]; + } while (SkDPoint::ApproximatelyEqual(span->fPt, firstPt) + && (span->fT == firstT || prior->fTiny)); return index; } @@ -2595,6 +3026,17 @@ int SkOpSegment::findExactT(double t, const SkOpSegment* match) const { return -1; } +int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const { + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = fTs[index]; + if (span.fOtherT == t && span.fOther == match) { + return index; + } + } + return -1; +} + int SkOpSegment::findT(double t, const SkPoint& pt, const SkOpSegment* match) const { int count = this->count(); for (int index = 0; index < count; ++index) { @@ -2647,7 +3089,7 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort SkASSERT(firstT - end != 0); SkOpAngle* markAngle = spanToAngle(firstT, end); if (!markAngle) { - markAngle = addSingletonAngles(firstT, step); + markAngle = addSingletonAngles(step); } markAngle->markStops(); const SkOpAngle* baseAngle = markAngle->findFirst(); @@ -2754,13 +3196,26 @@ void SkOpSegment::fixOtherTIndex() { } } +bool SkOpSegment::inCoincidentSpan(double t, const SkOpSegment* other) const { + int foundEnds = 0; + int count = this->count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = this->span(index); + if (span.fCoincident) { + foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.fT)); + } + } + SkASSERT(foundEnds != 7); + return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6; // two bits set +} + void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) { fDoneSpans = 0; fOperand = operand; fXor = evenOdd; fPts = pts; fVerb = verb; - fLoop = fSmall = fTiny = false; + fLoop = fMultiples = fSmall = fTiny = false; } void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) { @@ -2793,16 +3248,13 @@ void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc SkASSERT(dx); int windVal = windValue(SkMin32(start, end)); #if DEBUG_WINDING_AT_T - SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding, + SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding, hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); #endif int sideWind = winding + (dx < 0 ? windVal : -windVal); if (abs(winding) < abs(sideWind)) { winding = sideWind; } -#if DEBUG_WINDING_AT_T - SkDebugf(" winding=%d\n", winding); -#endif SkDEBUGCODE(int oppLocal = oppSign(start, end)); SkASSERT(hitOppDx || !oppWind || !oppLocal); int oppWindVal = oppValue(SkMin32(start, end)); @@ -2814,6 +3266,9 @@ void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc oppWind = oppSideWind; } } +#if DEBUG_WINDING_AT_T + SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind); +#endif (void) markAndChaseWinding(start, end, winding, oppWind); // OPTIMIZATION: the reverse mark and chase could skip the first marking (void) markAndChaseWinding(end, start, winding, oppWind); @@ -2824,12 +3279,12 @@ bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPt return false; } int index = *indexPtr; - int froIndex = fTs[index].fFromAngleIndex; - int toIndex = fTs[index].fToAngleIndex; + SkOpAngle* from = fTs[index].fFromAngle; + SkOpAngle* to = fTs[index].fToAngle; while (++index < spanCount) { - int nextFro = fTs[index].fFromAngleIndex; - int nextTo = fTs[index].fToAngleIndex; - if (froIndex != nextFro || toIndex != nextTo) { + SkOpAngle* nextFrom = fTs[index].fFromAngle; + SkOpAngle* nextTo = fTs[index].fToAngle; + if (from != nextFrom || to != nextTo) { break; } } @@ -2850,26 +3305,9 @@ bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const { return true; } -bool SkOpSegment::isSimple(int end) const { -#if 1 - int count = fTs.count(); - if (count == 2) { - return true; - } - double t = fTs[end].fT; - if (approximately_less_than_zero(t)) { - return !approximately_less_than_zero(fTs[1].fT); - } - if (approximately_greater_than_one(t)) { - return !approximately_greater_than_one(fTs[count - 2].fT); - } - return false; -#else - // OPTIMIZE: code could be rejiggered to use this simpler test. To make this work, a little - // more logic is required to ignore the dangling canceled out spans - const SkOpSpan& span = fTs[end]; - return span.fFromAngleIndex < 0 && span.fToAngleIndex < 0; -#endif + +SkOpSegment* SkOpSegment::isSimple(int* end, int* step) { + return nextChase(end, step, NULL, NULL); } bool SkOpSegment::isTiny(const SkOpAngle* angle) const { @@ -2928,11 +3366,12 @@ SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) { int step = SkSign32(endIndex - index); int min = SkMin32(index, endIndex); markDoneBinary(min); - SkOpSpan* last; + SkOpSpan* last = NULL; SkOpSegment* other = this; - while ((other = other->nextChase(&index, step, &min, &last))) { + while ((other = other->nextChase(&index, &step, &min, &last))) { if (other->done()) { - return NULL; + SkASSERT(!last); + break; } other->markDoneBinary(min); } @@ -2943,11 +3382,12 @@ SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) { int step = SkSign32(endIndex - index); int min = SkMin32(index, endIndex); markDoneUnary(min); - SkOpSpan* last; + SkOpSpan* last = NULL; SkOpSegment* other = this; - while ((other = other->nextChase(&index, step, &min, &last))) { + while ((other = other->nextChase(&index, &step, &min, &last))) { if (other->done()) { - return NULL; + SkASSERT(!last); + break; } other->markDoneUnary(min); } @@ -2960,12 +3400,13 @@ SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding) int step = SkSign32(endIndex - index); int min = SkMin32(index, endIndex); markWinding(min, winding); - SkOpSpan* last; + SkOpSpan* last = NULL; SkOpSegment* other = this; - while ((other = other->nextChase(&index, step, &min, &last))) { + while ((other = other->nextChase(&index, &step, &min, &last))) { if (other->fTs[min].fWindSum != SK_MinS32) { SkASSERT(other->fTs[min].fWindSum == winding); - return NULL; + SkASSERT(!last); + break; } other->markWinding(min, winding); } @@ -2976,12 +3417,13 @@ SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding) int min = SkMin32(index, endIndex); int step = SkSign32(endIndex - index); markWinding(min, winding); - SkOpSpan* last; + SkOpSpan* last = NULL; SkOpSegment* other = this; - while ((other = other->nextChase(&index, step, &min, &last))) { + while ((other = other->nextChase(&index, &step, &min, &last))) { if (other->fTs[min].fWindSum != SK_MinS32) { SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop); - return NULL; + SkASSERT(!last); + break; } other->markWinding(min, winding); } @@ -2992,14 +3434,32 @@ SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int min = SkMin32(index, endIndex); int step = SkSign32(endIndex - index); markWinding(min, winding, oppWinding); - SkOpSpan* last; + SkOpSpan* last = NULL; SkOpSegment* other = this; - while ((other = other->nextChase(&index, step, &min, &last))) { + while ((other = other->nextChase(&index, &step, &min, &last))) { if (other->fTs[min].fWindSum != SK_MinS32) { - SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop); - return NULL; +#if SK_DEBUG + if (!other->fTs[min].fLoop) { + if (fOperand == other->fOperand) { +// FIXME: this is probably a bug -- rects4 asserts here +// SkASSERT(other->fTs[min].fWindSum == winding); +// FIXME: this is probably a bug -- rects3 asserts here +// SkASSERT(other->fTs[min].fOppSum == oppWinding); + } else { + SkASSERT(other->fTs[min].fWindSum == oppWinding); +// FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here +// SkASSERT(other->fTs[min].fOppSum == winding); + } + } + SkASSERT(!last); +#endif + break; + } + if (fOperand == other->fOperand) { + other->markWinding(min, winding, oppWinding); + } else { + other->markWinding(min, oppWinding, winding); } - other->markWinding(min, winding, oppWinding); } return last; } @@ -3316,15 +3776,6 @@ void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) { } } -// 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 -// coincidence). The coincident edges could either be removed altogether, -// or this code could be more complicated in detecting this case. Worth it? -bool SkOpSegment::multipleSpans(int end) const { - return end > 0 && end < fTs.count() - 1; -} - bool SkOpSegment::nextCandidate(int* start, int* end) const { while (fTs[*end].fDone) { if (fTs[*end].fT == 1) { @@ -3337,27 +3788,67 @@ bool SkOpSegment::nextCandidate(int* start, int* end) const { return true; } -SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) { - int end = nextExactSpan(*index, step); +static SkOpSegment* set_last(SkOpSpan** last, SkOpSpan* endSpan) { + if (last && !endSpan->fSmall) { + *last = endSpan; + } + return NULL; +} + +SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, SkOpSpan** last) { + int origIndex = *indexPtr; + int step = *stepPtr; + int end = nextExactSpan(origIndex, step); SkASSERT(end >= 0); - if (fTs[end].fSmall) { - *last = NULL; - return NULL; + SkOpSpan& endSpan = fTs[end]; + SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle; + int foundIndex; + int otherEnd; + SkOpSegment* other; + if (angle == NULL) { + if (endSpan.fT != 0 && endSpan.fT != 1) { + return NULL; + } + other = endSpan.fOther; + foundIndex = endSpan.fOtherIndex; + otherEnd = other->nextExactSpan(foundIndex, step); + } else { + int loopCount = angle->loopCount(); + if (loopCount > 2) { + return set_last(last, &endSpan); + } + const SkOpAngle* next = angle->next(); + if (angle->sign() != next->sign()) { +#if DEBUG_WINDING + SkDebugf("%s mismatched signs\n", __FUNCTION__); +#endif + // return set_last(last, &endSpan); + } + other = next->segment(); + foundIndex = end = next->start(); + otherEnd = next->end(); } - if (multipleSpans(end)) { - *last = &fTs[end]; - return NULL; + int foundStep = foundIndex < otherEnd ? 1 : -1; + if (*stepPtr != foundStep) { + return set_last(last, &endSpan); } - const SkOpSpan& endSpan = fTs[end]; - SkOpSegment* other = endSpan.fOther; - *index = endSpan.fOtherIndex; - SkASSERT(*index >= 0); - int otherEnd = other->nextExactSpan(*index, step); + SkASSERT(*indexPtr >= 0); SkASSERT(otherEnd >= 0); - *min = SkMin32(*index, otherEnd); - if (other->fTs[*min].fSmall) { - *last = NULL; - return NULL; +#if 1 + int origMin = origIndex + (step < 0 ? step : 0); + const SkOpSpan& orig = this->span(origMin); +#endif + int foundMin = SkMin32(foundIndex, otherEnd); +#if 1 + const SkOpSpan& found = other->span(foundMin); + if (found.fWindValue != orig.fWindValue || found.fOppValue != orig.fOppValue) { + return set_last(last, &endSpan); + } +#endif + *indexPtr = foundIndex; + *stepPtr = foundStep; + if (minPtr) { + *minPtr = foundMin; } return other; } @@ -3414,6 +3905,27 @@ int SkOpSegment::nextExactSpan(int from, int step) const { return -1; } +void SkOpSegment::pinT(const SkPoint& pt, double* t) { + if (pt == fPts[0]) { + *t = 0; + } + int count = SkPathOpsVerbToPoints(fVerb); + if (pt == fPts[count]) { + *t = 1; + } +} + +void SkOpSegment::setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt, + SkOpSegment* other) { + int count = this->count(); + for (int index = 0; index < count; ++index) { + SkOpSpan &span = fTs[index]; + if ((startPt == span.fPt || endPt == span.fPt) && other == span.fOther) { + span.fCoincident = true; + } + } +} + void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) { int deltaSum = spanSign(index, endIndex); @@ -3452,15 +3964,15 @@ void SkOpSegment::sortAngles() { } int index = 0; do { - int fromIndex = fTs[index].fFromAngleIndex; - int toIndex = fTs[index].fToAngleIndex; - if (fromIndex < 0 && toIndex < 0) { + SkOpAngle* fromAngle = fTs[index].fFromAngle; + SkOpAngle* toAngle = fTs[index].fToAngle; + if (!fromAngle && !toAngle) { index += 1; continue; } SkOpAngle* baseAngle = NULL; - if (fromIndex >= 0) { - baseAngle = &this->angle(fromIndex); + if (fromAngle) { + baseAngle = fromAngle; if (inLoop(baseAngle, spanCount, &index)) { continue; } @@ -3468,8 +3980,7 @@ void SkOpSegment::sortAngles() { #if DEBUG_ANGLE bool wroteAfterHeader = false; #endif - if (toIndex >= 0) { - SkOpAngle* toAngle = &this->angle(toIndex); + if (toAngle) { if (!baseAngle) { baseAngle = toAngle; if (inLoop(baseAngle, spanCount, &index)) { @@ -3486,14 +3997,14 @@ void SkOpSegment::sortAngles() { baseAngle->insert(toAngle); } } - int nextFrom, nextTo; + SkOpAngle* nextFrom, * nextTo; int firstIndex = index; do { SkOpSpan& span = fTs[index]; SkOpSegment* other = span.fOther; SkOpSpan& oSpan = other->fTs[span.fOtherIndex]; - int otherAngleIndex = oSpan.fFromAngleIndex; - if (otherAngleIndex >= 0) { + SkOpAngle* oAngle = oSpan.fFromAngle; + if (oAngle) { #if DEBUG_ANGLE if (!wroteAfterHeader) { SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT, @@ -3501,13 +4012,12 @@ void SkOpSegment::sortAngles() { wroteAfterHeader = true; } #endif - SkOpAngle* oAngle = &other->angle(otherAngleIndex); if (!oAngle->loopContains(*baseAngle)) { baseAngle->insert(oAngle); } } - otherAngleIndex = oSpan.fToAngleIndex; - if (otherAngleIndex >= 0) { + oAngle = oSpan.fToAngle; + if (oAngle) { #if DEBUG_ANGLE if (!wroteAfterHeader) { SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT, @@ -3515,7 +4025,6 @@ void SkOpSegment::sortAngles() { wroteAfterHeader = true; } #endif - SkOpAngle* oAngle = &other->angle(otherAngleIndex); if (!oAngle->loopContains(*baseAngle)) { baseAngle->insert(oAngle); } @@ -3523,20 +4032,20 @@ void SkOpSegment::sortAngles() { if (++index == spanCount) { break; } - nextFrom = fTs[index].fFromAngleIndex; - nextTo = fTs[index].fToAngleIndex; - } while (fromIndex == nextFrom && toIndex == nextTo); + nextFrom = fTs[index].fFromAngle; + nextTo = fTs[index].fToAngle; + } while (fromAngle == nextFrom && toAngle == nextTo); if (baseAngle && baseAngle->loopCount() == 1) { index = firstIndex; do { SkOpSpan& span = fTs[index]; - span.fFromAngleIndex = span.fToAngleIndex = -1; + span.fFromAngle = span.fToAngle = NULL; if (++index == spanCount) { break; } - nextFrom = fTs[index].fFromAngleIndex; - nextTo = fTs[index].fToAngleIndex; - } while (fromIndex == nextFrom && toIndex == nextTo); + nextFrom = fTs[index].fFromAngle; + nextTo = fTs[index].fToAngle; + } while (fromAngle == nextFrom && toAngle == nextTo); baseAngle = NULL; } #if DEBUG_SORT @@ -3749,7 +4258,8 @@ int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx SkASSERT(winding != SK_MinS32); int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex); #if DEBUG_WINDING_AT_T - SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal); + SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__, + debugID(), crossOpp, tHit, t(tIndex), winding, windVal); #endif // see if a + change in T results in a +/- change in X (compute x'(T)) *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX; diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 1eaef69..90ed553 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -18,6 +18,7 @@ #include "SkThread.h" #endif +struct SkCoincidence; class SkPathWriter; class SkOpSegment { @@ -32,11 +33,15 @@ public: return fBounds.fTop < rh.fBounds.fTop; } - // FIXME: add some template or macro to avoid casting - SkOpAngle& angle(int index) { - const SkOpAngle& cAngle = (const_cast(this))->angle(index); - return const_cast(cAngle); - } + struct AlignedSpan { + double fOldT; + double fT; + SkPoint fOldPt; + SkPoint fPt; + const SkOpSegment* fSegment; + const SkOpSegment* fOther1; + const SkOpSegment* fOther2; + }; const SkPathOpsBounds& bounds() const { return fBounds; @@ -81,6 +86,10 @@ public: return dxdy(index).fY; } + bool hasMultiples() const { + return fMultiples; + } + bool hasSmall() const { return fSmall; } @@ -185,8 +194,7 @@ public: const SkOpAngle* spanToAngle(int tStart, int tEnd) const { SkASSERT(tStart != tEnd); const SkOpSpan& span = fTs[tStart]; - int index = tStart < tEnd ? span.fToAngleIndex : span.fFromAngleIndex; - return index >= 0 ? &angle(index) : NULL; + return tStart < tEnd ? span.fToAngle : span.fFromAngle; } // FIXME: create some sort of macro or template that avoids casting @@ -278,11 +286,19 @@ public: SkOpSegment* other); const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt); + const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, + const SkPoint& pt, const SkPoint& oPt); + void alignMultiples(SkTDArray* aligned); bool alignSpan(int index, double thisT, const SkPoint& thisPt); void alignSpanState(int start, int end); - const SkOpAngle& angle(int index) const; bool betweenTs(int lesser, double testT, int greater) const; + void blindCancel(const SkCoincidence& coincidence, SkOpSegment* other); + void blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other); bool calcAngles(); + double calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max, + double hiEnd, const SkOpSegment* other, int thisEnd); + double calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max, + double hiEnd, const SkOpSegment* other, int thisEnd); void checkDuplicates(); void checkEnds(); void checkMultiples(); @@ -301,6 +317,7 @@ public: bool* unsortable); SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); int findExactT(double t, const SkOpSegment* ) const; + int findOtherT(double t, const SkOpSegment* ) const; int findT(double t, const SkPoint& , const SkOpSegment* ) const; SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool firstPass); void fixOtherTIndex(); @@ -321,6 +338,7 @@ public: void markDoneUnary(int index); bool nextCandidate(int* start, int* end) const; int nextSpan(int from, int step) const; + void pinT(const SkPoint& pt, double* t); void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); void sortAngles(); @@ -334,9 +352,6 @@ public: int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const; int windSum(const SkOpAngle* angle) const; // available for testing only -#if DEBUG_VALIDATE - bool debugContains(const SkOpAngle* ) const; -#endif #if defined(SK_DEBUG) || !FORCE_RELEASE int debugID() const { return fID; @@ -358,6 +373,7 @@ public: const SkTDArray& debugSpans() const; void debugValidate() const; // available to testing only + const SkOpAngle* debugLastAngle() const; void dumpAngles() const; void dumpContour(int firstID, int lastID) const; void dumpPts() const; @@ -382,18 +398,22 @@ private: bool activeWinding(int index, int endIndex, int* sumWinding); void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); - int addSingletonAngleDown(int start, SkOpSegment** otherPtr); - int addSingletonAngleUp(int start, SkOpSegment** otherPtr); - SkOpAngle* addSingletonAngles(int start, int step); - void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt, - const SkPoint& oPt); + SkOpAngle* addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** ); + SkOpAngle* addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** ); + SkOpAngle* addSingletonAngles(int step); + void alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other, double otherT, + const SkOpSegment* other2, SkOpSpan* oSpan, SkTDArray* ); bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const; + void bumpCoincidentBlind(bool binary, int index, int last); void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index, SkTArray* outsideTs); + void bumpCoincidentOBlind(int index, int last); void bumpCoincidentOther(const SkOpSpan& oTest, int* index, SkTArray* outsideTs); bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta); bool calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts); + bool checkForSmall(const SkOpSpan* span, const SkPoint& pt, double newT, + int* less, int* more) const; void checkLinks(const SkOpSpan* , SkTArray* missingSpans) const; static void CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan, @@ -402,19 +422,26 @@ private: SkTArray* missingSpans); int checkSetAngle(int tIndex) const; void checkSmallCoincidence(const SkOpSpan& span, SkTArray* ); + bool coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const; bool clockwise(int tStart, int tEnd) const; static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); + bool containsT(double t, const SkOpSegment* other, double otherT) const; bool decrementSpan(SkOpSpan* span); int findEndSpan(int endIndex) const; int findStartSpan(int startIndex) const; int firstActive(int tIndex) const; const SkOpSpan& firstSpan(const SkOpSpan& thisSpan) const; void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd); + bool inCoincidentSpan(double t, const SkOpSegment* other) const; bool inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const; +#if OLD_CHASE bool isSimple(int end) const; +#else + SkOpSegment* isSimple(int* end, int* step); +#endif bool isTiny(int index) const; const SkOpSpan& lastSpan(const SkOpSpan& thisSpan) const; void matchWindingValue(int tIndex, double t, bool borrowWind); @@ -436,20 +463,15 @@ private: void markWinding(int index, int winding, int oppWinding); bool monotonicInY(int tStart, int tEnd) const; - bool multipleEnds() const { - return fTs[count() - 2].fT == 1; - } - - bool multipleStarts() const { - return fTs[1].fT == 0; - } + bool multipleEnds() const { return fTs[count() - 2].fT == 1; } + bool multipleStarts() const { return fTs[1].fT == 0; } - bool multipleSpans(int end) const; - SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last); + SkOpSegment* nextChase(int* index, int* step, int* min, SkOpSpan** last); int nextExactSpan(int from, int step) const; bool serpentine(int tStart, int tEnd) const; - void setFromAngleIndex(int endIndex, int angleIndex); - void setToAngleIndex(int endIndex, int angleIndex); + void setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); + void setFromAngle(int endIndex, SkOpAngle* ); + void setToAngle(int endIndex, SkOpAngle* ); void setUpWindings(int index, int endIndex, int* sumMiWinding, int* maxWinding, int* sumWinding); void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; @@ -509,14 +531,13 @@ private: SkPathOpsBounds fBounds; // FIXME: can't convert to SkTArray because it uses insert SkTDArray fTs; // 2+ (always includes t=0 t=1) -- at least (number of spans) + 1 -// FIXME: replace both with bucket storage that allows direct immovable pointers to angles - SkTArray fSingletonAngles; // 0 or 2 -- allocated for singletons - SkTArray fAngles; // 0 or 2+ -- (number of non-zero spans) * 2 + SkOpAngleSet fAngles; // empty or 2+ -- (number of non-zero spans) * 2 // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value int fDoneSpans; // quick check that segment is finished // OPTIMIZATION: force the following to be byte-sized SkPath::Verb fVerb; bool fLoop; // set if cubic intersects itself + bool fMultiples; // set if curve intersects multiple other curves at one interior point bool fOperand; bool fXor; // set if original contour had even-odd fill bool fOppXor; // set if opposite operand had even-odd fill diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index 1ffdc0e..d9ce44e 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -9,23 +9,27 @@ #include "SkPoint.h" +class SkOpAngle; class SkOpSegment; struct SkOpSpan { - SkOpSegment* fOther; SkPoint fPt; // computed when the curves are intersected double fT; double fOtherT; // value at fOther[fOtherIndex].fT + SkOpSegment* fOther; + SkOpAngle* fFromAngle; // (if t > 0) index into segment's angle array going negative in t + SkOpAngle* fToAngle; // (if t < 1) index into segment's angle array going positive in t int fOtherIndex; // can't be used during intersection - int fFromAngleIndex; // (if t > 0) index into segment's angle array going negative in t - int fToAngleIndex; // (if t < 1) index into segment's angle array going positive in t 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 fChased; // set after span has been added to chase array + bool fCoincident; // set if span is bumped -- if set additional points aren't inserted bool fDone; // if set, this span to next higher T has been processed bool fLoop; // set when a cubic loops back to this point + bool fMultiple; // set if this is one of mutiple spans with identical t and pt values + bool fNear; // set if opposite end point is near but not equal to this one bool fSmall; // if set, consecutive points are almost equal bool fTiny; // if set, consecutive points are equal but consecutive ts are not precisely equal diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 0e9e1be..9a8a2cf 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -10,6 +10,29 @@ #include "SkPathWriter.h" #include "SkTSort.h" +static void alignMultiples(SkTArray* contourList, + SkTDArray* aligned) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + if (contour->hasMultiples()) { + contour->alignMultiples(aligned); + } + } +} + +static void alignCoincidence(SkTArray* contourList, + const SkTDArray& aligned) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + int count = aligned.count(); + for (int index = 0; index < count; ++index) { + contour->alignCoincidence(aligned[index]); + } + } +} + static int contourRangeCheckY(const SkTArray& contourList, SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) { @@ -185,7 +208,7 @@ SkOpSegment* FindChase(SkTDArray* chase, int* tIndex, int* endIndex) if (SkOpSegment::UseInnerWinding(maxWinding, winding)) { maxWinding = winding; } - segment->markAndChaseWinding(angle, maxWinding, 0); + (void) segment->markAndChaseWinding(angle, maxWinding, 0); break; } } @@ -204,9 +227,8 @@ void DebugShowActiveSpans(SkTArray& contourList) { } #endif -static SkOpSegment* findSortableTop(const SkTArray& contourList, - int* index, int* endIndex, SkPoint* topLeft, bool* unsortable, - bool* done, bool firstPass) { +static SkOpSegment* findTopSegment(const SkTArray& contourList, int* index, + int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) { SkOpSegment* result; const SkOpSegment* lastTopStart = NULL; int lastIndex = -1, lastEndIndex = -1; @@ -249,28 +271,27 @@ static SkOpSegment* findSortableTop(const SkTArray& contourL lastEndIndex = *endIndex; } } while (!result); -#if 0 - if (result) { - *unsortable = false; - } -#endif return result; } static int rightAngleWinding(const SkTArray& contourList, - SkOpSegment** current, int* index, int* endIndex, double* tHit, - SkScalar* hitDx, bool* tryAgain, bool opp) { + SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit, + SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) { double test = 0.9; int contourWinding; do { - contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx, - tryAgain, &test, opp); + contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr, + tHit, hitDx, tryAgain, &test, opp); if (contourWinding != SK_MinS32 || *tryAgain) { return contourWinding; } + if (*currentPtr && (*currentPtr)->isVertical()) { + *onlyVertical = true; + return contourWinding; + } test /= 2; } while (!approximately_negative(test)); - SkASSERT(0); // should be OK to comment out, but interested when this hits + SkASSERT(0); // FIXME: incomplete functionality return contourWinding; } @@ -296,30 +317,34 @@ static void skipVertical(const SkTArray& contourList, SkOpSegment* FindSortableTop(const SkTArray& contourList, SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr, - int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) { - SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable, + int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, + bool firstPass) { + SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable, done, firstPass); if (!current) { return NULL; } - const int index = *indexPtr; + const int startIndex = *indexPtr; const int endIndex = *endIndexPtr; if (*firstContour) { - current->initWinding(index, endIndex, angleIncludeType); + current->initWinding(startIndex, endIndex, angleIncludeType); *firstContour = false; return current; } - int minIndex = SkMin32(index, endIndex); + int minIndex = SkMin32(startIndex, endIndex); int sumWinding = current->windSum(minIndex); - if (sumWinding != SK_MinS32) { - return current; - } - SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32); - const SkOpSpan& span = current->span(endIndex); - if ((index < endIndex ? span.fFromAngleIndex : span.fToAngleIndex) < 0) { - current->addSimpleAngle(endIndex); + if (sumWinding == SK_MinS32) { + int index = endIndex; + int oIndex = startIndex; + do { + const SkOpSpan& span = current->span(index); + if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) { + current->addSimpleAngle(index); + } + sumWinding = current->computeSum(oIndex, index, angleIncludeType); + SkTSwap(index, oIndex); + } while (sumWinding == SK_MinS32 && index == startIndex); } - sumWinding = current->computeSum(index, endIndex, angleIncludeType); if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { return current; } @@ -340,7 +365,10 @@ SkOpSegment* FindSortableTop(const SkTArray& contourList, SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); tryAgain = false; contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, - &hitDx, &tryAgain, false); + &hitDx, &tryAgain, onlyVertical, false); + if (*onlyVertical) { + return current; + } if (tryAgain) { continue; } @@ -348,7 +376,7 @@ SkOpSegment* FindSortableTop(const SkTArray& contourList, break; } oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, - &hitOppDx, &tryAgain, true); + &hitOppDx, &tryAgain, NULL, true); } while (tryAgain); current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding, hitOppDx); @@ -387,14 +415,15 @@ static void checkEnds(SkTArray* contourList) { } } -static void checkMultiples(SkTArray* contourList) { - // it's hard to determine if the end of a cubic or conic nearly intersects another curve. - // instead, look to see if the connecting curve intersected at that same end. +static bool checkMultiples(SkTArray* contourList) { + bool hasMultiples = false; int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { SkOpContour* contour = (*contourList)[cTest]; contour->checkMultiples(); + hasMultiples |= contour->hasMultiples(); } + return hasMultiples; } // A small interval of a pair of curves may collapse to lines for each, triggering coincidence @@ -675,12 +704,17 @@ bool HandleCoincidence(SkTArray* contourList, int total) { SkOpContour::debugShowWindingValues(contourList); #endif fixOtherTIndex(contourList); - checkEnds(contourList); - checkMultiples(contourList); - checkDuplicates(contourList); - checkTiny(contourList); - checkSmall(contourList); - joinCoincidence(contourList); + checkEnds(contourList); // check if connecting curve intersected at the same end + bool hasM = checkMultiples(contourList); // check if intersections agree on t and point values + SkTDArray aligned; + if (hasM) { + alignMultiples(contourList, &aligned); // align pairs of identical points + alignCoincidence(contourList, aligned); + } + checkDuplicates(contourList); // check if spans have the same number on the other end + checkTiny(contourList); // if pair have the same end points, mark them as parallel + checkSmall(contourList); // a pair of curves with a small span may turn into coincident lines + joinCoincidence(contourList); // join curves that connect to a coincident pair sortSegments(contourList); if (!calcAngles(contourList)) { return false; diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h index 6a7bb72..0d8cfc4 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -18,7 +18,7 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple); SkOpSegment* FindChase(SkTDArray* chase, int* tIndex, int* endIndex); SkOpSegment* FindSortableTop(const SkTArray& , SkOpAngle::IncludeType , bool* firstContour, int* index, int* endIndex, SkPoint* topLeft, - bool* unsortable, bool* done, bool firstPass); + bool* unsortable, bool* done, bool* onlyVertical, bool firstPass); SkOpSegment* FindUndone(SkTArray& contourList, int* start, int* end); void MakeContourList(SkTArray& contours, SkTArray& list, bool evenOdd, bool oppEvenOdd); diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 56813b8..9d82dff 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -104,68 +104,7 @@ void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, #if DEBUG_SORT void SkOpAngle::debugLoop() const { - const SkOpAngle* first = this; - const SkOpAngle* next = this; - do { - next->debugOne(true); - SkDebugf("\n"); - next = next->fNext; - } while (next && next != first); -} - -void SkOpAngle::debugOne(bool functionHeader) const { -// fSegment->debugValidate(); - const SkOpSpan& mSpan = fSegment->span(SkMin32(fStart, fEnd)); - if (functionHeader) { - SkDebugf("%s ", __FUNCTION__); - } - SkDebugf("[%d", fSegment->debugID()); -#if DEBUG_ANGLE - SkDebugf("/%d", fID); -#endif - SkDebugf("] next="); - if (fNext) { - SkDebugf("%d", fNext->fSegment->debugID()); -#if DEBUG_ANGLE - SkDebugf("/%d", fNext->fID); -#endif - } else { - SkDebugf("?"); - } - SkDebugf(" sect=%d/%d ", fSectorStart, fSectorEnd); - SkDebugf(" s=%1.9g [%d] e=%1.9g [%d]", fSegment->span(fStart).fT, fStart, - fSegment->span(fEnd).fT, fEnd); - SkDebugf(" sgn=%d windVal=%d", sign(), mSpan.fWindValue); - -#if DEBUG_WINDING - SkDebugf(" windSum="); - SkPathOpsDebug::WindingPrintf(mSpan.fWindSum); -#endif - if (mSpan.fOppValue != 0 || mSpan.fOppSum != SK_MinS32) { - SkDebugf(" oppVal=%d", mSpan.fOppValue); -#if DEBUG_WINDING - SkDebugf(" oppSum="); - SkPathOpsDebug::WindingPrintf(mSpan.fOppSum); -#endif - } - if (mSpan.fDone) { - SkDebugf(" done"); - } - if (unorderable()) { - SkDebugf(" unorderable"); - } - if (small()) { - SkDebugf(" small"); - } - if (mSpan.fTiny) { - SkDebugf(" tiny"); - } - if (fSegment->operand()) { - SkDebugf(" operand"); - } - if (fStop) { - SkDebugf(" stop"); - } + dumpLoop(); } #endif @@ -174,12 +113,12 @@ void SkOpAngle::debugSameAs(const SkOpAngle* compare) const { SK_ALWAYSBREAK(fSegment == compare->fSegment); const SkOpSpan& startSpan = fSegment->span(fStart); const SkOpSpan& oStartSpan = fSegment->span(compare->fStart); - SK_ALWAYSBREAK(startSpan.fToAngleIndex == oStartSpan.fToAngleIndex); - SK_ALWAYSBREAK(startSpan.fFromAngleIndex == oStartSpan.fFromAngleIndex); + SK_ALWAYSBREAK(startSpan.fToAngle == oStartSpan.fToAngle); + SK_ALWAYSBREAK(startSpan.fFromAngle == oStartSpan.fFromAngle); const SkOpSpan& endSpan = fSegment->span(fEnd); const SkOpSpan& oEndSpan = fSegment->span(compare->fEnd); - SK_ALWAYSBREAK(endSpan.fToAngleIndex == oEndSpan.fToAngleIndex); - SK_ALWAYSBREAK(endSpan.fFromAngleIndex == oEndSpan.fFromAngleIndex); + SK_ALWAYSBREAK(endSpan.fToAngle == oEndSpan.fToAngle); + SK_ALWAYSBREAK(endSpan.fFromAngle == oEndSpan.fFromAngle); } #endif @@ -189,7 +128,7 @@ void SkOpAngle::debugValidateNext() const { const SkOpAngle* next = first; SkTDArray(angles); do { - SK_ALWAYSBREAK(next->fSegment->debugContains(next)); +// SK_ALWAYSBREAK(next->fSegment->debugContains(next)); angles.push(next); next = next->next(); if (next == first) { @@ -377,22 +316,6 @@ void SkOpSegment::debugCheckPointsEqualish(int tStart, int tEnd) const { } #endif -#if DEBUG_VALIDATE -bool SkOpSegment::debugContains(const SkOpAngle* angle) const { - for (int index = 0; index < fAngles.count(); ++index) { - if (&fAngles[index] == angle) { - return true; - } - } - for (int index = 0; index < fSingletonAngles.count(); ++index) { - if (&fSingletonAngles[index] == angle) { - return true; - } - } - return false; -} -#endif - #if DEBUG_SWAP_TOP int SkOpSegment::debugInflections(int tStart, int tEnd) const { if (fVerb != SkPath::kCubic_Verb) { @@ -404,6 +327,19 @@ int SkOpSegment::debugInflections(int tStart, int tEnd) const { } #endif +const SkOpAngle* SkOpSegment::debugLastAngle() const { + const SkOpAngle* result = NULL; + for (int index = 0; index < count(); ++index) { + const SkOpSpan& span = this->span(index); + if (span.fToAngle) { + SkASSERT(!result); + result = span.fToAngle; + } + } + SkASSERT(result); + return result; +} + void SkOpSegment::debugReset() { fTs.reset(); fAngles.reset(); @@ -539,7 +475,7 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int } else { SkDebugf("%d", span.fWindSum); } - SkDebugf(" windValue=%d\n", span.fWindValue); + SkDebugf(" windValue=%d oppValue=%d\n", span.fWindValue, span.fOppValue); } #endif @@ -590,6 +526,7 @@ void SkOpSegment::debugValidate() const { SK_ALWAYSBREAK(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]); done += span.fDone; if (last) { + SK_ALWAYSBREAK(last->fT != span.fT || last->fOther != span.fOther); bool tsEqual = last->fT == span.fT; bool tsPreciselyEqual = precisely_equal(last->fT, span.fT); SK_ALWAYSBREAK(!tsEqual || tsPreciselyEqual); @@ -616,8 +553,8 @@ void SkOpSegment::debugValidate() const { hasLoop |= last->fLoop; } SK_ALWAYSBREAK(done == fDoneSpans); - if (fAngles.count() ) { - fAngles.begin()->debugValidateLoop(); - } +// if (fAngles.count() ) { +// fAngles.begin()->debugValidateLoop(); +// } #endif } diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index bb54039..9dc562f 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -51,6 +51,7 @@ #define DEBUG_CONCIDENT 0 #define DEBUG_CROSS 0 #define DEBUG_CUBIC_BINARY_SEARCH 0 +#define DEBUG_DUPLICATES 0 #define DEBUG_FLAT_QUADS 0 #define DEBUG_FLOW 0 #define DEBUG_LIMIT_WIND_SUM 0 @@ -86,6 +87,7 @@ #define DEBUG_CONCIDENT 1 #define DEBUG_CROSS 01 #define DEBUG_CUBIC_BINARY_SEARCH 1 +#define DEBUG_DUPLICATES 1 #define DEBUG_FLAT_QUADS 0 #define DEBUG_FLOW 1 #define DEBUG_LIMIT_WIND_SUM 4 @@ -123,7 +125,7 @@ #define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY #define QUAD_DEBUG_DATA(q) q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY #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 +#define PT_DEBUG_DATA(i, n) i.pt(n).asSkPoint().fX, i.pt(n).asSkPoint().fY #ifndef DEBUG_TEST #define DEBUG_TEST 0 @@ -168,14 +170,18 @@ public: static void BumpTestName(char* ); #endif static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name); - static void DumpAngles(const SkTArray& angles); - static void DumpAngles(const SkTArray& angles); + static void DumpCoincidence(const SkTArray& contours); + static void DumpCoincidence(const SkTArray& contours); static void DumpContours(const SkTArray& contours); static void DumpContours(const SkTArray& contours); static void DumpContourAngles(const SkTArray& contours); static void DumpContourAngles(const SkTArray& contours); + static void DumpContourPt(const SkTArray& contours, int id); + static void DumpContourPt(const SkTArray& contours, int id); static void DumpContourPts(const SkTArray& contours); static void DumpContourPts(const SkTArray& contours); + static void DumpContourSpan(const SkTArray& contours, int id); + static void DumpContourSpan(const SkTArray& contours, int id); static void DumpContourSpans(const SkTArray& contours); static void DumpContourSpans(const SkTArray& contours); static void DumpSpans(const SkTDArray& ); @@ -183,34 +189,44 @@ public: }; // shorthand for calling from debugger -void Dump(const SkTArray& angles); -void Dump(const SkTArray& angles); -void Dump(const SkTArray* angles); -void Dump(const SkTArray* angles); - void Dump(const SkTArray& contours); void Dump(const SkTArray& contours); void Dump(const SkTArray* contours); void Dump(const SkTArray* contours); -void Dump(const SkTDArray& chaseArray); -void Dump(const SkTDArray* chaseArray); +void Dump(const SkTDArray& chase); +void Dump(const SkTDArray* chase); void DumpAngles(const SkTArray& contours); void DumpAngles(const SkTArray& contours); void DumpAngles(const SkTArray* contours); void DumpAngles(const SkTArray* contours); +void DumpCoin(const SkTArray& contours); +void DumpCoin(const SkTArray& contours); +void DumpCoin(const SkTArray* contours); +void DumpCoin(const SkTArray* contours); + void DumpPts(const SkTArray& contours); void DumpPts(const SkTArray& contours); void DumpPts(const SkTArray* contours); void DumpPts(const SkTArray* contours); +void DumpPt(const SkTArray& contours, int segmentID); +void DumpPt(const SkTArray& contours, int segmentID); +void DumpPt(const SkTArray* contours, int segmentID); +void DumpPt(const SkTArray* contours, int segmentID); + void DumpSpans(const SkTArray& contours); void DumpSpans(const SkTArray& contours); void DumpSpans(const SkTArray* contours); void DumpSpans(const SkTArray* contours); +void DumpSpan(const SkTArray& contours, int segmentID); +void DumpSpan(const SkTArray& contours, int segmentID); +void DumpSpan(const SkTArray* contours, int segmentID); +void DumpSpan(const SkTArray* contours, int segmentID); + // generates tools/path_sorter.htm and path_visualizer.htm compatible data void DumpQ(const struct SkDQuad& quad1, const struct SkDQuad& quad2, int testNo); diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp index 7587fda..6229619 100644 --- a/src/pathops/SkPathOpsLine.cpp +++ b/src/pathops/SkPathOpsLine.cpp @@ -63,7 +63,7 @@ double SkDLine::exactPoint(const SkDPoint& xy) const { return -1; } -double SkDLine::nearPoint(const SkDPoint& xy) const { +double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const { if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { return -1; @@ -86,6 +86,9 @@ double SkDLine::nearPoint(const SkDPoint& xy) const { if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? return -1; } + if (unequal) { + *unequal = (float) largest != (float) (largest + dist); + } t = SkPinT(t); SkASSERT(between(0, t, 1)); return t; diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h index e4ed0c9..74eb615 100644 --- a/src/pathops/SkPathOpsLine.h +++ b/src/pathops/SkPathOpsLine.h @@ -30,7 +30,7 @@ struct SkDLine { static double ExactPointH(const SkDPoint& xy, double left, double right, double y); static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x); double isLeft(const SkDPoint& pt) const; - double nearPoint(const SkDPoint& xy) const; + double nearPoint(const SkDPoint& xy, bool* unequal) 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); diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 5af4753..4c6923a 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -41,6 +41,9 @@ static SkOpSegment* findChaseOp(SkTDArray& chase, int* tIndex, int* e } // find first angle, initialize winding to computed fWindSum const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex); + if (!angle) { + continue; + } const SkOpAngle* firstAngle = angle; SkDEBUGCODE(bool loop = false); int winding; @@ -70,6 +73,7 @@ static SkOpSegment* findChaseOp(SkTDArray& chase, int* tIndex, int* e *tIndex = start; *endIndex = end; } + // OPTIMIZATION: should this also add to the chase? (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, angle); } @@ -125,9 +129,10 @@ static bool bridgeOp(SkTArray& contourList, const SkPathOp o do { int index, endIndex; bool topDone; + bool onlyVertical = false; lastTopLeft = topLeft; SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour, - &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass); + &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass); if (!current) { if ((!topUnsortable || firstPass) && !topDone) { SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); @@ -142,29 +147,33 @@ static bool bridgeOp(SkTArray& contourList, const SkPathOp o continue; } break; + } else if (onlyVertical) { + break; } firstPass = !topUnsortable || lastTopLeft != topLeft; - SkTDArray chaseArray; + SkTDArray chase; do { if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) { do { if (!unsortable && current->done()) { - if (simple->isEmpty()) { - simple->init(); - } break; } SkASSERT(unsortable || !current->done()); int nextStart = index; int nextEnd = endIndex; - SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd, + SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, &unsortable, op, xorMask, xorOpMask); if (!next) { if (!unsortable && simple->hasMove() && current->verb() != SkPath::kLine_Verb && !simple->isClosed()) { current->addCurveTo(index, endIndex, simple, true); - SkASSERT(simple->isClosed()); + #if DEBUG_ACTIVE_SPANS + if (!simple->isClosed()) { + DebugShowActiveSpans(contourList); + } + #endif +// SkASSERT(simple->isClosed()); } break; } @@ -195,11 +204,16 @@ static bool bridgeOp(SkTArray& contourList, const SkPathOp o SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex); if (last && !last->fChased && !last->fLoop) { last->fChased = true; - SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last)); - *chaseArray.append() = last; + SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); + *chase.append() = last; +#if DEBUG_WINDING + SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, + last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum, + last->fSmall); +#endif } } - current = findChaseOp(chaseArray, &index, &endIndex); + current = findChaseOp(chase, &index, &endIndex); #if DEBUG_ACTIVE_SPANS DebugShowActiveSpans(contourList); #endif diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index 336fb62..5c2e3a5 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -148,14 +148,12 @@ struct SkDPoint { return AlmostBequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance? } -#ifdef SK_DEBUG static bool RoughlyEqual(const SkPoint& a, const SkPoint& b) { if (approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY)) { return true; } return RoughlyEqualUlps(a.fX, b.fX) && RoughlyEqualUlps(a.fY, b.fY); } -#endif bool approximatelyPEqual(const SkDPoint& a) const { if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 0917b69..57090ac 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -19,9 +19,10 @@ static bool bridgeWinding(SkTArray& contourList, SkPathWrite do { int index, endIndex; bool topDone; + bool onlyVertical = false; lastTopLeft = topLeft; SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour, - &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass); + &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass); if (!current) { if ((!topUnsortable || firstPass) && !topDone) { SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin); @@ -29,22 +30,21 @@ static bool bridgeWinding(SkTArray& contourList, SkPathWrite continue; } break; + } else if (onlyVertical) { + break; } firstPass = !topUnsortable || lastTopLeft != topLeft; - SkTDArray chaseArray; + SkTDArray chase; do { if (current->activeWinding(index, endIndex)) { do { if (!unsortable && current->done()) { - if (simple->isEmpty()) { - simple->init(); - break; - } + break; } SkASSERT(unsortable || !current->done()); int nextStart = index; int nextEnd = endIndex; - SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd, + SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd, &unsortable); if (!next) { if (!unsortable && simple->hasMove() @@ -67,7 +67,7 @@ static bool bridgeWinding(SkTArray& contourList, SkPathWrite } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(index, endIndex)))); if (current->activeWinding(index, endIndex) && !simple->isClosed()) { - SkASSERT(unsortable || simple->isEmpty()); +// SkASSERT(unsortable || simple->isEmpty()); int min = SkMin32(index, endIndex); if (!current->done(min)) { current->addCurveTo(index, endIndex, simple, true); @@ -79,13 +79,17 @@ static bool bridgeWinding(SkTArray& contourList, SkPathWrite SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex); if (last && !last->fChased && !last->fLoop) { last->fChased = true; - SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last)); + SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last)); // assert that last isn't already in array - *chaseArray.append() = last; + *chase.append() = last; +#if DEBUG_WINDING + SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__, + last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum, + last->fSmall); +#endif } } - SkTDArray* chaseArrayPtr = &chaseArray; - current = FindChase(chaseArrayPtr, &index, &endIndex); + current = FindChase(&chase, &index, &endIndex); #if DEBUG_ACTIVE_SPANS DebugShowActiveSpans(contourList); #endif diff --git a/src/pathops/SkPathOpsTriangle.cpp b/src/pathops/SkPathOpsTriangle.cpp index 7db4831..77845e0 100644 --- a/src/pathops/SkPathOpsTriangle.cpp +++ b/src/pathops/SkPathOpsTriangle.cpp @@ -23,7 +23,7 @@ bool SkDTriangle::contains(const SkDPoint& pt) const { double dot12 = v1.dot(v2); // original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts; -// introduces necessary error with divide; doesn't short circuit on early answer +// introduces error with divide; doesn't short circuit on early answer #if 0 // Compute barycentric coordinates double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 4f8bd15..9662784 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -91,6 +91,11 @@ const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few b const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; const double ROUGH_EPSILON = FLT_EPSILON * 64; const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; +const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; + +inline bool zero_or_one(double x) { + return x == 0 || x == 1; +} inline bool approximately_zero(double x) { return fabs(x) < FLT_EPSILON; @@ -297,12 +302,16 @@ inline bool between(double a, double b, double c) { return (a - b) * (c - b) <= 0; } +inline bool roughly_equal(double x, double y) { + return fabs(x - y) < ROUGH_EPSILON; +} + inline bool more_roughly_equal(double x, double y) { return fabs(x - y) < MORE_ROUGH_EPSILON; } -inline bool roughly_equal(double x, double y) { - return fabs(x - y) < ROUGH_EPSILON; +inline bool way_roughly_equal(double x, double y) { + return fabs(x - y) < WAY_ROUGH_EPSILON; } struct SkDPoint; diff --git a/tests/PathOpsAngleIdeas.cpp b/tests/PathOpsAngleIdeas.cpp index 2887b28..901cab2 100755 --- a/tests/PathOpsAngleIdeas.cpp +++ b/tests/PathOpsAngleIdeas.cpp @@ -426,7 +426,8 @@ static void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, c SkOpSegment seg[2]; makeSegment(quad1, shortQuads[0], &seg[0]); makeSegment(quad2, shortQuads[1], &seg[1]); - int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(seg[0].angle(0), seg[1].angle(0)); + int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(*seg[0].debugLastAngle(), + *seg[1].debugLastAngle()); const SkDPoint& origin = quad1[0]; REPORTER_ASSERT(reporter, origin == quad2[0]); double a1s = atan2(origin.fY - quad1[1].fY, quad1[1].fX - origin.fX); @@ -544,7 +545,8 @@ static void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, c } if (overlap < 0) { SkDEBUGCODE(int realEnds =) - PathOpsAngleTester::EndsIntersect(seg[0].angle(0), seg[1].angle(0)); + PathOpsAngleTester::EndsIntersect(*seg[0].debugLastAngle(), + *seg[1].debugLastAngle()); SkASSERT(realEnds == (firstInside ? 1 : 0)); } bruteForce(reporter, quad1, quad2, firstInside); diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index 1aae27a..faf6158 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -264,7 +264,7 @@ DEF_TEST(PathOpsAngleCircle, reporter) { break; } } - PathOpsAngleTester::Orderable(segment[0].angle(0), segment[1].angle(0)); + PathOpsAngleTester::Orderable(*segment[0].debugLastAngle(), *segment[1].debugLastAngle()); } struct IntersectData { @@ -438,9 +438,9 @@ DEF_TEST(PathOpsAngleAfter, reporter) { } break; } } - SkOpAngle& angle1 = const_cast(segment[0].angle(0)); - SkOpAngle& angle2 = const_cast(segment[1].angle(0)); - SkOpAngle& angle3 = const_cast(segment[2].angle(0)); + SkOpAngle& angle1 = *const_cast(segment[0].debugLastAngle()); + SkOpAngle& angle2 = *const_cast(segment[1].debugLastAngle()); + SkOpAngle& angle3 = *const_cast(segment[2].debugLastAngle()); PathOpsAngleTester::SetNext(angle1, angle3); // These data sets are seeded when the set itself fails, so likely the dataset does not // match the expected result. The tests above return 1 when first added, but diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index 17b3f07..b6a9e59 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -162,6 +162,9 @@ static const SkDCubic testSet[] = { const int testSetCount = (int) SK_ARRAY_COUNT(testSet); static const SkDCubic newTestSet[] = { +{{{980.9000244140625, 1474.3280029296875}, {980.9000244140625, 1474.3280029296875}, {978.89300537109375, 1471.95703125}, {981.791015625, 1469.487060546875}}}, +{{{981.791015625, 1469.487060546875}, {981.791015625, 1469.4859619140625}, {983.3580322265625, 1472.72900390625}, {980.9000244140625, 1474.3280029296875}}}, + {{{275,532}, {277.209137,532}, {279,530.209106}, {279,528}}}, {{{278,529}, {278,530.65686}, {276.65686,532}, {275,532}}}, diff --git a/tests/PathOpsDebug.cpp b/tests/PathOpsDebug.cpp index d53271a..a2b48ac 100755 --- a/tests/PathOpsDebug.cpp +++ b/tests/PathOpsDebug.cpp @@ -34,25 +34,69 @@ void SkPathOpsDebug::WindingPrintf(int wind) { #endif void SkOpAngle::dump() const { -#if DEBUG_SORT - debugOne(false); -#endif + dumpOne(true); SkDebugf("\n"); } -void SkOpAngle::dumpFromTo(const SkOpSegment* segment, int from, int to) const { -#if DEBUG_SORT && DEBUG_ANGLE +void SkOpAngle::dumpOne(bool functionHeader) const { +// fSegment->debugValidate(); + const SkOpSpan& mSpan = fSegment->span(SkMin32(fStart, fEnd)); + if (functionHeader) { + SkDebugf("%s ", __FUNCTION__); + } + SkDebugf("[%d", fSegment->debugID()); + SkDebugf("/%d", debugID()); + SkDebugf("] next="); + if (fNext) { + SkDebugf("%d", fNext->fSegment->debugID()); + SkDebugf("/%d", fNext->debugID()); + } else { + SkDebugf("?"); + } + SkDebugf(" sect=%d/%d ", fSectorStart, fSectorEnd); + SkDebugf(" s=%1.9g [%d] e=%1.9g [%d]", fSegment->span(fStart).fT, fStart, + fSegment->span(fEnd).fT, fEnd); + SkDebugf(" sgn=%d windVal=%d", sign(), mSpan.fWindValue); + + SkDebugf(" windSum="); + SkPathOpsDebug::WindingPrintf(mSpan.fWindSum); + if (mSpan.fOppValue != 0 || mSpan.fOppSum != SK_MinS32) { + SkDebugf(" oppVal=%d", mSpan.fOppValue); + SkDebugf(" oppSum="); + SkPathOpsDebug::WindingPrintf(mSpan.fOppSum); + } + if (mSpan.fDone) { + SkDebugf(" done"); + } + if (unorderable()) { + SkDebugf(" unorderable"); + } + if (small()) { + SkDebugf(" small"); + } + if (mSpan.fTiny) { + SkDebugf(" tiny"); + } + if (fSegment->operand()) { + SkDebugf(" operand"); + } + if (fStop) { + SkDebugf(" stop"); + } +} + +void SkOpAngle::dumpTo(const SkOpSegment* segment, const SkOpAngle* to) const { const SkOpAngle* first = this; const SkOpAngle* next = this; const char* indent = ""; do { SkDebugf("%s", indent); - next->debugOne(false); + next->dumpOne(false); if (segment == next->fSegment) { - if (fNext && from == fNext->debugID()) { + if (this == fNext) { SkDebugf(" << from"); } - if (fNext && to == fNext->debugID()) { + if (to == fNext) { SkDebugf(" << to"); } } @@ -60,7 +104,6 @@ void SkOpAngle::dumpFromTo(const SkOpSegment* segment, int from, int to) const { indent = " "; next = next->fNext; } while (next && next != first); -#endif } void SkOpAngle::dumpLoop() const { @@ -81,6 +124,14 @@ void SkOpAngle::dumpPartials() const { } while (next && next != first); } +void SkOpAngleSet::dump() const { + // FIXME: unimplemented +/* This requires access to the internal SkChunkAlloc data + Defer implementing this until it is needed for debugging +*/ + SkASSERT(0); +} + void SkOpContour::dump() const { int segmentCount = fSegments.count(); SkDebugf("((SkOpContour*) 0x%p) [%d]\n", this, debugID()); @@ -99,6 +150,50 @@ void SkOpContour::dumpAngles() const { } } +void SkOpContour::dumpCoincidence(const SkCoincidence& coin) const { + int thisIndex = coin.fSegments[0]; + const SkOpSegment& s1 = fSegments[thisIndex]; + int otherIndex = coin.fSegments[1]; + const SkOpSegment& s2 = coin.fOther->fSegments[otherIndex]; + SkDebugf("((SkOpSegment*) 0x%p) [%d] ((SkOpSegment*) 0x%p) [%d]\n", &s1, s1.debugID(), + &s2, s2.debugID()); + for (int index = 0; index < 2; ++index) { + SkDebugf(" {%1.9gf, %1.9gf}", coin.fPts[0][index].fX, coin.fPts[0][index].fY); + if (coin.fNearly[index]) { + SkDebugf(" {%1.9gf, %1.9gf}", coin.fPts[1][index].fX, coin.fPts[1][index].fY); + } + SkDebugf(" seg1t=%1.9g seg2t=%1.9g\n", coin.fTs[0][index], coin.fTs[1][index]); + } +} + +void SkOpContour::dumpCoincidences() const { + int count = fCoincidences.count(); + if (count > 0) { + SkDebugf("fCoincidences count=%d\n", count); + for (int test = 0; test < count; ++test) { + dumpCoincidence(fCoincidences[test]); + } + } + count = fPartialCoincidences.count(); + if (count == 0) { + return; + } + SkDebugf("fPartialCoincidences count=%d\n", count); + for (int test = 0; test < count; ++test) { + dumpCoincidence(fPartialCoincidences[test]); + } +} + +void SkOpContour::dumpPt(int index) const { + int segmentCount = fSegments.count(); + for (int test = 0; test < segmentCount; ++test) { + const SkOpSegment& segment = fSegments[test]; + if (segment.debugID() == index) { + fSegments[test].dumpPts(); + } + } +} + void SkOpContour::dumpPts() const { int segmentCount = fSegments.count(); SkDebugf("((SkOpContour*) 0x%p) [%d]\n", this, debugID()); @@ -108,6 +203,16 @@ void SkOpContour::dumpPts() const { } } +void SkOpContour::dumpSpan(int index) const { + int segmentCount = fSegments.count(); + for (int test = 0; test < segmentCount; ++test) { + const SkOpSegment& segment = fSegments[test]; + if (segment.debugID() == index) { + fSegments[test].dumpSpans(); + } + } +} + void SkOpContour::dumpSpans() const { int segmentCount = fSegments.count(); SkDebugf("((SkOpContour*) 0x%p) [%d]\n", this, debugID()); @@ -208,25 +313,24 @@ const SkTDArray& SkOpSegment::debugSpans() const { void SkOpSegment::dumpAngles() const { SkDebugf("((SkOpSegment*) 0x%p) [%d]\n", this, debugID()); - int fromIndex = -1, toIndex = -1; + const SkOpAngle* fromAngle = NULL; + const SkOpAngle* toAngle = NULL; for (int index = 0; index < count(); ++index) { - int fIndex = fTs[index].fFromAngleIndex; - int tIndex = fTs[index].fToAngleIndex; - if (fromIndex == fIndex && tIndex == toIndex) { + const SkOpAngle* fAngle = fTs[index].fFromAngle; + const SkOpAngle* tAngle = fTs[index].fToAngle; + if (fromAngle == fAngle && toAngle == tAngle) { continue; } - if (fIndex >= 0) { - SkDebugf(" [%d] from=%d ", index, fIndex); - const SkOpAngle& angle = this->angle(fIndex); - angle.dumpFromTo(this, fIndex, tIndex); + if (fAngle) { + SkDebugf(" [%d] from=%d ", index, fAngle->debugID()); + fAngle->dumpTo(this, tAngle); } - if (tIndex >= 0) { - SkDebugf(" [%d] to=%d ", index, tIndex); - const SkOpAngle& angle = this->angle(tIndex); - angle.dumpFromTo(this, fIndex, tIndex); + if (tAngle) { + SkDebugf(" [%d] to=%d ", index, tAngle->debugID()); + tAngle->dumpTo(this, fAngle); } - fromIndex = fIndex; - toIndex = tIndex; + fromAngle = fAngle; + toAngle = tAngle; } } @@ -279,17 +383,17 @@ void SkOpSegment::dumpSpans() const { } } -void SkPathOpsDebug::DumpAngles(const SkTArray& angles) { - int count = angles.count(); +void SkPathOpsDebug::DumpCoincidence(const SkTArray& contours) { + int count = contours.count(); for (int index = 0; index < count; ++index) { - angles[index].dump(); + contours[index].dumpCoincidences(); } } -void SkPathOpsDebug::DumpAngles(const SkTArray& angles) { - int count = angles.count(); +void SkPathOpsDebug::DumpCoincidence(const SkTArray& contours) { + int count = contours.count(); for (int index = 0; index < count; ++index) { - angles[index]->dump(); + contours[index]->dumpCoincidences(); } } @@ -335,6 +439,20 @@ void SkPathOpsDebug::DumpContourPts(const SkTArray& contour } } +void SkPathOpsDebug::DumpContourPt(const SkTArray& contours, int segmentID) { + int count = contours.count(); + for (int index = 0; index < count; ++index) { + contours[index].dumpPt(segmentID); + } +} + +void SkPathOpsDebug::DumpContourPt(const SkTArray& contours, int segmentID) { + int count = contours.count(); + for (int index = 0; index < count; ++index) { + contours[index]->dumpPt(segmentID); + } +} + void SkPathOpsDebug::DumpContourSpans(const SkTArray& contours) { int count = contours.count(); for (int index = 0; index < count; ++index) { @@ -349,6 +467,20 @@ void SkPathOpsDebug::DumpContourSpans(const SkTArray& conto } } +void SkPathOpsDebug::DumpContourSpan(const SkTArray& contours, int segmentID) { + int count = contours.count(); + for (int index = 0; index < count; ++index) { + contours[index].dumpSpan(segmentID); + } +} + +void SkPathOpsDebug::DumpContourSpan(const SkTArray& contours, int segmentID) { + int count = contours.count(); + for (int index = 0; index < count; ++index) { + contours[index]->dumpSpan(segmentID); + } +} + void SkPathOpsDebug::DumpSpans(const SkTDArray& spans) { int count = spans.count(); for (int index = 0; index < count; ++index) { @@ -400,33 +532,45 @@ void SkOpSpan::dumpOne() const { } else { SkDebugf(" other.fID=? [?] otherT=?"); } -#if DEBUG_WINDING - SkDebugf(" windSum="); - SkPathOpsDebug::WindingPrintf(fWindSum); -#endif - if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) { -#if DEBUG_WINDING - SkDebugf(" oppSum="); - SkPathOpsDebug::WindingPrintf(fOppSum); -#endif + if (fWindSum != SK_MinS32) { + SkDebugf(" windSum=%d", fWindSum); + } + if (fOppSum != SK_MinS32 && (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0)) { + SkDebugf(" oppSum=%d", fOppSum); } SkDebugf(" windValue=%d", fWindValue); if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) { SkDebugf(" oppValue=%d", fOppValue); } - SkDebugf(" from=%d", fFromAngleIndex); - SkDebugf(" to=%d", fToAngleIndex); + if (fFromAngle && fFromAngle->debugID()) { + SkDebugf(" from=%d", fFromAngle->debugID()); + } + if (fToAngle && fToAngle->debugID()) { + SkDebugf(" to=%d", fToAngle->debugID()); + } + if (fChased) { + SkDebugf(" chased"); + } + if (fCoincident) { + SkDebugf(" coincident"); + } if (fDone) { SkDebugf(" done"); } - if (fTiny) { - SkDebugf(" tiny"); + if (fLoop) { + SkDebugf(" loop"); + } + if (fMultiple) { + SkDebugf(" multiple"); + } + if (fNear) { + SkDebugf(" near"); } if (fSmall) { SkDebugf(" small"); } - if (fLoop) { - SkDebugf(" loop"); + if (fTiny) { + SkDebugf(" tiny"); } SkDebugf("\n"); } @@ -444,22 +588,6 @@ void SkOpSpan::dump() const { dumpOne(); } -void Dump(const SkTArray& angles) { - SkPathOpsDebug::DumpAngles(angles); -} - -void Dump(const SkTArray& angles) { - SkPathOpsDebug::DumpAngles(angles); -} - -void Dump(const SkTArray* angles) { - SkPathOpsDebug::DumpAngles(*angles); -} - -void Dump(const SkTArray* angles) { - SkPathOpsDebug::DumpAngles(*angles); -} - void Dump(const SkTArray& contours) { SkPathOpsDebug::DumpContours(contours); } @@ -476,12 +604,12 @@ void Dump(const SkTArray* contours) { SkPathOpsDebug::DumpContours(*contours); } -void Dump(const SkTDArray& chaseArray) { - SkPathOpsDebug::DumpSpans(chaseArray); +void Dump(const SkTDArray& chase) { + SkPathOpsDebug::DumpSpans(chase); } -void Dump(const SkTDArray* chaseArray) { - SkPathOpsDebug::DumpSpans(*chaseArray); +void Dump(const SkTDArray* chase) { + SkPathOpsDebug::DumpSpans(*chase); } void DumpAngles(const SkTArray& contours) { @@ -500,6 +628,22 @@ void DumpAngles(const SkTArray* contours) { SkPathOpsDebug::DumpContourAngles(*contours); } +void DumpCoin(const SkTArray& contours) { + SkPathOpsDebug::DumpCoincidence(contours); +} + +void DumpCoin(const SkTArray& contours) { + SkPathOpsDebug::DumpCoincidence(contours); +} + +void DumpCoin(const SkTArray* contours) { + SkPathOpsDebug::DumpCoincidence(*contours); +} + +void DumpCoin(const SkTArray* contours) { + SkPathOpsDebug::DumpCoincidence(*contours); +} + void DumpSpans(const SkTArray& contours) { SkPathOpsDebug::DumpContourSpans(contours); } @@ -516,6 +660,22 @@ void DumpSpans(const SkTArray* contours) { SkPathOpsDebug::DumpContourSpans(*contours); } +void DumpSpan(const SkTArray& contours, int segmentID) { + SkPathOpsDebug::DumpContourSpan(contours, segmentID); +} + +void DumpSpan(const SkTArray& contours, int segmentID) { + SkPathOpsDebug::DumpContourSpan(contours, segmentID); +} + +void DumpSpan(const SkTArray* contours, int segmentID) { + SkPathOpsDebug::DumpContourSpan(*contours, segmentID); +} + +void DumpSpan(const SkTArray* contours, int segmentID) { + SkPathOpsDebug::DumpContourSpan(*contours, segmentID); +} + void DumpPts(const SkTArray& contours) { SkPathOpsDebug::DumpContourPts(contours); } @@ -532,6 +692,22 @@ void DumpPts(const SkTArray* contours) { SkPathOpsDebug::DumpContourPts(*contours); } +void DumpPt(const SkTArray& contours, int segmentID) { + SkPathOpsDebug::DumpContourPt(contours, segmentID); +} + +void DumpPt(const SkTArray& contours, int segmentID) { + SkPathOpsDebug::DumpContourPt(contours, segmentID); +} + +void DumpPt(const SkTArray* contours, int segmentID) { + SkPathOpsDebug::DumpContourPt(*contours, segmentID); +} + +void DumpPt(const SkTArray* contours, int segmentID) { + SkPathOpsDebug::DumpContourPt(*contours, segmentID); +} + static void dumpTestCase(const SkDQuad& quad1, const SkDQuad& quad2, int testNo) { SkDebugf("
\n", testNo); quad1.dumpComma(","); diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index 280307a..fe3d24d 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -156,6 +156,11 @@ static void showPathData(const SkPath& path) { while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: + if (firstPtSet && lastPtSet && firstPt != lastPt) { + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", lastPt.fX, lastPt.fY, + firstPt.fX, firstPt.fY); + lastPtSet = false; + } firstPt = pts[0]; firstPtSet = true; continue; @@ -190,6 +195,10 @@ static void showPathData(const SkPath& path) { return; } } + if (firstPtSet && lastPtSet && firstPt != lastPt) { + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", lastPt.fX, lastPt.fY, + firstPt.fX, firstPt.fY); + } } #endif @@ -410,7 +419,6 @@ static void showPathOpPath(const char* testName, const SkPath& one, const SkPath SkDebugf("static void %s(skiatest::Reporter* reporter, const char* filename) {\n", testName); *gTestOp.append() = shapeOp; ++gTestNo; - SkDebugf("\n*** this test fails ***\n"); SkDebugf(" SkPath path, pathB;\n"); showPath(a, "path", false); showPath(b, "pathB", false); @@ -440,6 +448,7 @@ static int comparePaths(skiatest::Reporter* reporter, const char* testName, cons if (errors2x2 > MAX_ERRORS && gComparePathsAssert) { SK_DECLARE_STATIC_MUTEX(compareDebugOut3); SkAutoMutexAcquire autoM(compareDebugOut3); + SkDebugf("\n*** this test fails ***\n"); showPathOpPath(testName, one, two, a, b, scaledOne, scaledTwo, shapeOp, scale); REPORTER_ASSERT(reporter, 0); } else if (gShowPath || errors2x2 == MAX_ERRORS || errors2x2 == MAX_ERRORS - 1) { diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp index 9885178..379c2f1 100644 --- a/tests/PathOpsLineIntersectionTest.cpp +++ b/tests/PathOpsLineIntersectionTest.cpp @@ -50,7 +50,10 @@ static const SkDLine noIntersect[][2] = { static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect); static const SkDLine coincidentTests[][2] = { - {{{{0,482.5}, {-4.4408921e-016,682.5}}}, + {{{ { 10105, 2510 }, { 10123, 2509.98999f } }}, + {{{10105, 2509.98999f}, { 10123, 2510 } }}}, + + {{ { { 0, 482.5 }, { -4.4408921e-016, 682.5 } } }, {{{0,683}, {0,482}}}}, {{{{1.77635684e-015,312}, {-1.24344979e-014,348}}}, @@ -76,9 +79,12 @@ static void check_results(skiatest::Reporter* reporter, const SkDLine& line1, co for (int i = 0; i < ts.used(); ++i) { SkDPoint result1 = line1.ptAtT(ts[0][i]); SkDPoint result2 = line2.ptAtT(ts[1][i]); - if (!result1.approximatelyEqual(result2)) { + if (!result1.approximatelyEqual(result2) && !ts.nearlySame(i)) { REPORTER_ASSERT(reporter, ts.used() != 1); result2 = line2.ptAtT(ts[1][i ^ 1]); + if (!result1.approximatelyEqual(result2)) { + SkDebugf("."); + } REPORTER_ASSERT(reporter, result1.approximatelyEqual(result2)); REPORTER_ASSERT(reporter, result1.approximatelyEqual(ts.pt(i).asSkPoint())); } diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 75b6030..5317792 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -2065,6 +2065,11 @@ static void rectOp3x(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path, pathB, kXOR_PathOp, filename); } +#define ISSUE_1435_FIXED 0 +#if ISSUE_1435_FIXED +// this fails to generate two interior line segments +// an earlier pathops succeeded, but still failed to generate one interior line segment +// (but was saved by assemble, which works around a single line missing segment) static void issue1435(skiatest::Reporter* reporter, const char* filename) { SkPath path1; path1.moveTo(160, 60); @@ -2115,6 +2120,7 @@ static void issue1435(skiatest::Reporter* reporter, const char* filename) { path2.setFillType(SkPath::kEvenOdd_FillType); testPathOp(reporter, path1, path2, kIntersect_PathOp, filename); } +#endif static void skpkkiste_to716(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -3348,10 +3354,116 @@ static void issue2504(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path1, path2, kUnion_PathOp, filename); } +#define TEST_2540 0 +#if TEST_2540 // FIXME: extends cubic arm for sorting, marks extension with wrong winding? +static void issue2540(skiatest::Reporter* reporter, const char* filename) { + SkPath path1; + path1.moveTo(26.5054988861083984375, 85.73960113525390625); + path1.cubicTo(84.19739532470703125, 17.77140045166015625, 16.93920135498046875, 101.86199951171875, 12.631000518798828125, 105.24700164794921875); + path1.cubicTo(11.0819997787475585937500000, 106.46399688720703125, 11.5260000228881835937500000, 104.464996337890625, 11.5260000228881835937500000, 104.464996337890625); + path1.lineTo(23.1654987335205078125, 89.72879791259765625); + path1.cubicTo(23.1654987335205078125, 89.72879791259765625, -10.1713008880615234375, 119.9160003662109375, -17.1620006561279296875, 120.8249969482421875); + path1.cubicTo(-19.1149997711181640625, 121.07900238037109375, -18.0380001068115234375, 119.79299163818359375, -18.0380001068115234375, 119.79299163818359375); + path1.cubicTo(-18.0380001068115234375, 119.79299163818359375, 14.22100067138671875, 90.60700225830078125, 26.5054988861083984375, 85.73960113525390625); + path1.close(); + + SkPath path2; + path2.moveTo(-25.077999114990234375, 124.9120025634765625); + path2.cubicTo(-25.077999114990234375, 124.9120025634765625, -25.9509983062744140625, 125.95400238037109375, -24.368999481201171875, 125.7480010986328125); + path2.cubicTo(-16.06999969482421875, 124.66899871826171875, 1.2680000066757202148437500, 91.23999786376953125, 37.264003753662109375, 95.35400390625); + path2.cubicTo(37.264003753662109375, 95.35400390625, 11.3710002899169921875, 83.7339935302734375, -25.077999114990234375, 124.9120025634765625); + path2.close(); + testPathOp(reporter, path1, path2, kUnion_PathOp, filename); +} +#endif + +static void rects1(skiatest::Reporter* reporter, const char* filename) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.lineTo(1, 1); + path.lineTo(0, 1); + path.close(); + path.moveTo(0, 0); + path.lineTo(6, 0); + path.lineTo(6, 6); + path.lineTo(0, 6); + path.close(); + pathB.setFillType(SkPath::kEvenOdd_FillType); + pathB.moveTo(0, 0); + pathB.lineTo(1, 0); + pathB.lineTo(1, 1); + pathB.lineTo(0, 1); + pathB.close(); + pathB.moveTo(0, 0); + pathB.lineTo(2, 0); + pathB.lineTo(2, 2); + pathB.lineTo(0, 2); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp, filename); +} + +static void rects2(skiatest::Reporter* reporter, const char* filename) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(0, 0); + path.lineTo(4, 0); + path.lineTo(4, 4); + path.lineTo(0, 4); + path.close(); + path.moveTo(3, 3); + path.lineTo(4, 3); + path.lineTo(4, 4); + path.lineTo(3, 4); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(3, 3); + pathB.lineTo(6, 3); + pathB.lineTo(6, 6); + pathB.lineTo(3, 6); + pathB.close(); + pathB.moveTo(3, 3); + pathB.lineTo(4, 3); + pathB.lineTo(4, 4); + pathB.lineTo(3, 4); + pathB.close(); + testPathOp(reporter, path, pathB, kDifference_PathOp, filename); +} + +static void rects3(skiatest::Reporter* reporter, const char* filename) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 4, 4, 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, kDifference_PathOp, filename); +} + +static void rects4(skiatest::Reporter* reporter, const char* filename) { + SkPath path, pathB; + path.setFillType(SkPath::kEvenOdd_FillType); + path.addRect(0, 0, 1, 1, SkPath::kCW_Direction); + path.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction); + pathB.addRect(0, 0, 3, 3, SkPath::kCW_Direction); + testPathOp(reporter, path, pathB, kDifference_PathOp, filename); +} + static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; static struct TestDesc tests[] = { + TEST(rects4), + TEST(rects3), + TEST(rects2), + TEST(rects1), +#if TEST_2540 // FIXME: extends cubic arm for sorting, marks extension with wrong winding? + TEST(issue2540), +#endif TEST(issue2504), TEST(kari1), TEST(quadOp10i), @@ -3390,7 +3502,9 @@ static struct TestDesc tests[] = { TEST(cubicOp101), TEST(cubicOp100), TEST(cubicOp99), +#if ISSUE_1435_FIXED TEST(issue1435), +#endif TEST(cubicOp98x), TEST(cubicOp97x), TEST(skpcarpetplanet_ru22), // cubic/cubic intersect detects unwanted coincidence diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index 7b5128c..4bfab14 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -4653,9 +4653,26 @@ static void testQuads61(skiatest::Reporter* reporter, const char* filename) { testSimplify(reporter, path, filename); } -static void (*firstTest)(skiatest::Reporter* , const char* filename) = testQuadratic56; +static void testQuadralateral10(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0, 0); + path.lineTo(0, 0); + path.lineTo(0, 0); + path.lineTo(2, 2); + path.close(); + path.moveTo(1, 0); + path.lineTo(1, 1); + path.lineTo(2, 2); + path.lineTo(1, 3); + path.close(); + testSimplify(reporter, path, filename); +} + +static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static TestDesc tests[] = { + TEST(testQuadralateral10), TEST(testQuads61), TEST(testQuads60), TEST(testQuads59), diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp index c0f028c..da50545 100755 --- a/tests/PathOpsSkpClipTest.cpp +++ b/tests/PathOpsSkpClipTest.cpp @@ -27,87 +27,197 @@ #else #define PATH_SLASH "/" #define IN_DIR "/skp/2311328-7fc2228/slave" - #define OUT_DIR "/skpOut/2/" + #define OUT_DIR "/skpOut/4/" #endif const struct { int directory; const char* filename; } skipOverSept[] = { - { 9, "http___www_catingueiraonline_com_.skp"}, // infinite loop - {13, "http___www_galaxystwo_com_.skp"}, // infinite loop - {15, "http___www_giffingtool_com_.skp"}, // joinCoincidence / findT / assert - {15, "http___www_thaienews_blogspot_com_.skp"}, // infinite loop - {17, "http___www_gruposejaumdivulgador_com_br_.skp"}, // calcCoincidentWinding asserts zeroSpan + { 3, "http___www_americascup_com_.skp"}, // !simple->closed() {18, "http___www_argus_presse_fr_.skp"}, // can't find winding of remaining vertical edge - {21, "http___www_fashionscandal_com_.skp"}, // infinite loop - {21, "http___www_kenlevine_blogspot_com_.skp"}, // infinite loop - {25, "http___www_defense_studies_blogspot_com_.skp"}, // infinite loop - {27, "http___www_brokeroutpost_com_.skp"}, // suspect infinite loop - {28, "http___www_jaimebatistadasilva_blogspot_com_br_.skp"}, // suspect infinite loop - {28, "http___www_odia_com_br_.skp"}, // !simple->isClosed() - {29, "http___www_hubbyscook_com_.skp"}, // joinCoincidence / findT / assert - {30, "http___www_spankystokes_com_.skp"}, // suspect infinite loop - {32, "http___www_adalbertoday_blogspot_com_br_.skp"}, // suspect infinite loop - {32, "http___www_galery_annisa_com_.skp"}, // suspect infinite loop - {33, "http___www_pindosiya_com_.skp"}, // line quad intersection SkIntersections::assert - {36, "http___www_educationalcraft_com_.skp"}, // cubic / cubic near end / assert in SkIntersections::insert (missing skp test) - {36, "http___www_shaam_org_.skp"}, // suspect infinite loop - {36, "http___www_my_pillow_book_blogspot_gr_.skp"}, // suspect infinite loop - {39, "http___www_opbeat_com_.skp"}, // suspect infinite loop - {40, "http___www_phototransferapp_com_.skp"}, // !simple->isClosed() - {41, "http___www_freeismylife_com_.skp"}, // suspect infinite loop - {41, "http___www_accordidelmomento_com_.skp"}, // suspect infinite loop - {41, "http___www_evolvehq_com_.skp"}, // joinCoincidence / findT / assert - {44, "http___www_contextualnewsfeeds_com_.skp"}, // !simple->isClosed() + {31, "http___www_narayana_verlag_de_.skp"}, // !simple->closed() + {36, "http___www_educationalcraft_com_.skp"}, // cubic / cubic near end / assert in SkIntersections::insert {44, "http___www_cooksnaps_com_.skp"}, // !simple->isClosed() - {44, "http___www_helha_be_.skp"}, // !simple->isClosed() - {45, "http___www_blondesmakemoney_blogspot_com_.skp"}, // suspect infinite loop - {46, "http___www_cheaphealthygood_blogspot_com_.skp"}, // suspect infinite loop - {47, "http___www_ajitvadakayil_blogspot_in_.skp"}, // suspect infinite loop - {49, "http___www_karnivool_com_au_.skp"}, // SkOpAngle::setSector SkASSERT(fSectorStart >= 0); - {49, "http___www_tunero_de_.skp"}, // computeonesumreverse calls markwinding with 0 winding - {49, "http___www_thaienews_blogspot_sg_.skp"}, // suspect infinite loop - {50, "http___www_docgelo_com_.skp"}, // rightAngleWinding (probably same as argus_presse) + {48, "http___www_narayana_publishers_com_.skp"}, // !simple->isClosed() + {51, "http___www_freedominthe50states_org_.skp"}, // corrupt dash data + {52, "http___www_aceinfographics_com_.skp"}, // right angle winding assert {53, "http___www_lojaanabotafogo_com_br_.skp"}, // rrect validate assert - {54, "http___www_odecktestanswer2013_blogspot_in_.skp"}, // suspect infinite loop - {54, "http___www_cleristonsilva_com_br_.skp"}, // suspect infinite loop - {56, "http___www_simplysaru_com_.skp"}, // joinCoincidence / findT / assert - {57, "http___www_koukfamily_blogspot_gr_.skp"}, // suspect infinite loop - {57, "http___www_dinar2010_blogspot_com_.skp"}, // suspect infinite loop - {58, "http___www_artblart_com_.skp"}, // rightAngleWinding - {59, "http___www_accrispin_blogspot_com_.skp"}, // suspect infinite loop - {59, "http___www_vicisitudysordidez_blogspot_com_es_.skp"}, // suspect infinite loop - {60, "http___www_thehousingbubbleblog_com_.skp"}, // suspect infinite loop - {61, "http___www_jessicaslens_wordpress_com_.skp"}, // joinCoincidence / findT / assert - {61, "http___www_partsdata_de_.skp"}, // cubic-cubic intersection reduce checkLinear assert - {62, "http___www_blondesmakemoney_blogspot_com_au_.skp"}, // suspect infinite loop - {62, "http___www_intellibriefs_blogspot_in_.skp"}, // suspect infinite loop - {63, "http___www_tankerenemy_com_.skp"}, // suspect infinite loop - {65, "http___www_kpopexplorer_net_.skp"}, // joinCoincidence / findT / assert - {65, "http___www_bestthingsinbeauty_blogspot_com_.skp"}, // suspect infinite loop - {65, "http___www_wartepop_blogspot_com_br_.skp"}, // !simple->isClosed() - {65, "http___www_eolake_blogspot_com_.skp"}, // suspect infinite loop - {67, "http___www_cacadordemisterio_blogspot_com_br_.skp"}, // suspect infinite loop - {69, "http___www_misnotasyapuntes_blogspot_mx_.skp"}, // suspect infinite loop - {69, "http___www_awalkintheparknyc_blogspot_com_.skp"}, // suspect infinite loop - {71, "http___www_lokado_de_.skp"}, // joinCoincidence / findT / assert - {72, "http___www_karlosdesanjuan_blogspot_com_.skp"}, // suspect infinite loop - {73, "http___www_cyberlawsinindia_blogspot_in_.skp"}, // suspect infinite loop - {73, "http___www_taxiemmovimento_blogspot_com_br_.skp"}, // suspect infinite loop - {74, "http___www_giveusliberty1776_blogspot_com_.skp"}, // suspect infinite loop - {75, "http___www_e_cynical_blogspot_gr_.skp"}, // suspect infinite loop - {76, "http___www_seopack_blogspot_com_.skp"}, // SkOpAngle::setSector SkASSERT(fSectorStart >= 0); - {77, "http___www_sunsky_russia_com_.skp"}, // joinCoincidence / findT / assert (no op test, already fixed hopefully) - {78, "http___www_bisnisonlineinfo_com_.skp"}, // suspect infinite loop - {79, "http___www_danielsgroupcpa_com_.skp"}, // joinCoincidence / findT / assert (no op test, already fixed hopefully) - {80, "http___www_clinique_portugal_com_.skp"}, // suspect infinite loop - {81, "http___www_europebusines_blogspot_com_.skp"}, // suspect infinite loop - {82, "http___www_apopsignomi_blogspot_gr_.skp"}, // suspect infinite loop - {85, "http___www_ajitvadakayil_blogspot_com_.skp"}, // suspect infinite loop - {86, "http___www_madhousefamilyreviews_blogspot_co_uk_.skp"}, // suspect infinite loop + {57, "http___www_vantageproduction_com_.skp"}, // !isClosed() + {64, "http___www_etiqadd_com_.skp"}, // !simple->closed() + {84, "http___www_swapspacesystems_com_.skp"}, // !simple->closed() + {90, "http___www_tcmevents_org_.skp"}, // !simple->closed() + {96, "http___www_paseoitaigara_com_br_.skp"}, // !simple->closed() + {98, "http___www_mortgagemarketguide_com_.skp"}, // !simple->closed() + {99, "http___www_kitcheninspirations_wordpress_com_.skp"}, // checkSmall / bumpSpan }; +/* stats +97 http___www_brandyandvinca_com_.skp pixelError=3 +95 http___www_into_asia_com_.skp pixelError=12 +93 http___www_lunarplanner_com_.skp pixelError=14 +98 http___www_lovelyitalia_com_.skp pixelError=17 +90 http___www_inter_partner_blogspot_com_.skp pixelError=18 +99 http___www_maxarea_com_.skp pixelError=26 +98 http___www_maroonsnet_org_.skp pixelError=33 +92 http___www_belinaart_ru_.skp pixelError=50 +100 http___www_chroot_ro_.skp pixelError=62 +99 http___www_hsbrands_com_.skp pixelError=98 +95 http___www_tournamentindicator_com_.skp pixelError=122 +93 http___www_businesses_com_au_.skp pixelError=162 +90 http___www_regenesys_net_.skp pixelError=182 +88 http___www_1863544208148625103_c18eac63985503fa85b06358959c1ba27fc36f82_blogspot_com_.skp pixelError=186 +97 http___www_pregacoesevangelica_com_br_.skp pixelError=240 +77 http___www_zhenggang_org_.skp pixelError=284 +96 http___slidesharemailer_com_.skp pixelError=522 +94 http___www_gensteel_com_.skp pixelError=555 +68 http___www_jf_eti_br_.skp pixelError=610 +83 http___www_swishiat_com_.skp pixelError=706 +96 http___www_matusikmissive_com_au_.skp pixelError=2580 +95 http___www_momentumnation_com_.skp pixelError=3938 +92 http___www_rssowl_com_.skp pixelError=5113 +96 http___www_sexxygirl_tv_.skp pixelError=7605 +99 http___www_georgevalah_wordpress_com_.skp pixelError=8386 +78 http___www_furbo_org_.skp pixelError=8656 +78 http___www_djxhemary_wordpress_com_.skp pixelError=8976 +100 http___www_mindcontrolblackassassins_com_.skp pixelError=31950 +98 http___bababillgates_free_fr_.skp pixelError=40237 +98 http___hepatite_ro_.skp pixelError=44370 +86 http___www_somethingwagging_com_.skp pixelError=47794 +84 http___www_beverageuniverse_com_.skp pixelError=65450 +50 http___www_aveksa_com_.skp pixelError=68194 +10 http___www_publiker_pl_.skp pixelError=89997 +61 http___www_dominos_co_id_.skp pixelError=476868 +87 http___www_du_edu_om_.skp time=46 +87 http___www_bigload_de_.skp time=46 +100 http___www_home_forum_com_.skp time=48 +97 http___www_hotamateurchat_com_.skp time=48 +97 http___www_myrsky_com_cn_.skp time=48 +98 http___www_techiegeex_com_.skp time=49 +82 http___www_fashionoutletsofchicago_com_.skp time=50 +77 http___www_dynamischbureau_nl_.skp time=50 +82 http___www_mayihelpu_co_in_.skp time=50 +84 http___www_vbox7_com_user_history_viewers_.skp time=50 +85 http___www_ktokogda_com_.skp time=50 +85 http___www_propertyturkeysale_com_.skp time=50 +85 http___www_51play_com_.skp time=50 +86 http___www_bayalarm_com_.skp time=50 +87 http___www_eaglepictures_com_.skp time=50 +88 http___www_atlasakvaryum_com_.skp time=50 +91 http___www_pioneerchryslerjeep_com_.skp time=50 +94 http___www_thepulsemag_com_.skp time=50 +95 http___www_dcshoes_com_ph_.skp time=50 +96 http___www_montrealmassage_ca_.skp time=50 +96 http___www_jkshahclasses_com_.skp time=50 +96 http___www_webcamconsult_com_.skp time=51 +100 http___www_bsoscblog_com_.skp time=52 +95 http___www_flaktwoods_com_.skp time=53 +91 http___www_qivivo_com_.skp time=54 +90 http___www_unitender_com_.skp time=56 +97 http___www_casinogaming_com_.skp time=56 +97 http___www_rootdownload_com_.skp time=56 +94 http___www_aspa_ev_de_.skp time=57 +98 http___www_tenpieknyswiat_pl_.skp time=57 +93 http___www_transocean_de_.skp time=58 +94 http___www_vdo2_blogspot_com_.skp time=58 +94 http___www_asmaissexy_com_br_.skp time=58 +100 http___www_prefeiturasjm_com_br_.skp time=60 +100 http___www_eduinsuranceclick_blogspot_com_.skp time=60 +96 http___www_bobdunsire_com_.skp time=61 +96 http___www_omgkettlecorn_com_.skp time=61 +85 http___www_fbbsessions_com_.skp time=62 +86 http___www_hector_ru_.skp time=62 +87 http___www_wereldsupporter_nl_.skp time=62 +90 http___www_arello_com_.skp time=62 +93 http___www_bayerplastics_com_.skp time=62 +93 http___www_superandolamovida_com_ar_.skp time=62 +96 http___www_med_rbf_ru_.skp time=62 +81 http___www_carnegiescience_edu_.skp time=65 +87 http___www_asanewengland_com_.skp time=65 +92 http___www_turkce_karakter_appspot_com_.skp time=65 +94 http___www_k3a_org_.skp time=65 +96 http___www_powermaccenter_com_.skp time=65 +98 http___www_avto49_ru_.skp time=67 +100 http___www_hetoldeambaecht_nl_.skp time=68 +95 http___www_marine_ie_.skp time=69 +96 http___www_quebecvapeboutique_com_.skp time=69 +95 http___www_brays_ingles_com_.skp time=70 +100 http___www_lacondesa_com_.skp time=72 +95 http___www_timbarrathai_com_au_.skp time=76 +95 http___www_cuissedegrenouille_com_.skp time=76 +95 http___www_iwama51_ru_.skp time=76 +99 http___www_fotoantologia_it_.skp time=76 +92 http___www_indian_architects_com_.skp time=78 +92 http___www_totalwomanspa_com_.skp time=78 +100 http___www_fachverband_spielhallen_de_.skp time=83 +93 http___www_golshanemehr_ir_.skp time=84 +95 http___www_maryesses_com_.skp time=84 +99 http___www_ddcorp_ca_.skp time=89 +90 http___www_brontops_com_.skp time=89 +94 http___www_robgolding_com_.skp time=89 +91 http___www_tecban_com_br_.skp time=91 +98 http___www_costamesakarate_com_.skp time=100 +95 http___www_monsexyblog_com_.skp time=103 +97 http___www_stornowaygazette_co_uk_.skp time=103 +93 http___www_fitforaframe_com_.skp time=104 +98 http___www_intentionoftheday_com_.skp time=113 +100 http___www_tailgateclothing_com_.skp time=117 +95 http___www_senbros_com_.skp time=118 +93 http___www_lettoblog_com_.skp time=121 +94 http___www_maxineschallenge_com_au_.skp time=125 +95 http___www_savvycard_net_.skp time=127 +95 http___www_open_ac_mu_.skp time=129 +96 http___www_avgindia_in_.skp time=135 +97 http___www_stocktonseaview_com_.skp time=135 +96 http___www_distroller_com_.skp time=142 +94 http___www_travoggalop_dk_.skp time=144 +100 http___www_history_im_.skp time=144 +94 http___www_playradio_sk_.skp time=145 +92 http___www_linglongglass_com_.skp time=151 +97 http___www_bizzna_com_.skp time=151 +96 http___www_spiros_ws_.skp time=154 +91 http___www_rosen_meents_co_il_.skp time=156 +81 http___www_hoteldeluxeportland_com_.skp time=158 +92 http___www_freetennis_org_.skp time=161 +93 http___www_aircharternetwork_com_au_.skp time=161 +94 http___www_austinparks_org_.skp time=165 +89 http___www_bevvy_co_.skp time=168 +91 http___www_sosyalhile_net_.skp time=168 +98 http___www_minvih_gob_ve_.skp time=171 +89 http___www_streetfoodmtl_com_.skp time=172 +92 http___www_loveslatinas_tumblr_com_.skp time=178 +93 http___www_madbites_co_in_.skp time=180 +94 http___www_rocktarah_ir_.skp time=185 +97 http___www_penthouselife_com_.skp time=185 +96 http___www_appymonkey_com_.skp time=196 +92 http___www_pasargadhotels_com_.skp time=203 +99 http___www_marina_mil_pe_.skp time=203 +89 http___www_kays_co_uk_.skp time=205 +77 http___www_334588_com_.skp time=211 +83 http___www_trendbad24_de_.skp time=211 +81 http___www_cdnetworks_co_kr_.skp time=216 +94 http___www_schellgames_com_.skp time=223 +95 http___www_juliaweddingnews_cn_.skp time=230 +92 http___www_xcrafters_pl_.skp time=253 +93 http___www_pondoo_com_.skp time=253 +96 http___www_helsinkicapitalpartners_fi_.skp time=255 +88 http___www_nadtexican_com_.skp time=259 +85 http___www_canstockphoto_hu_.skp time=266 +78 http___www_ecovacs_com_cn_.skp time=271 +93 http___www_brookfieldplaceny_com_.skp time=334 +93 http___www_fmastrengthtraining_com_.skp time=337 +94 http___www_turtleonthebeach_com_.skp time=394 +90 http___www_temptationthemovie_com_.skp time=413 +95 http___www_patongsawaddi_com_.skp time=491 +91 http___www_online_radio_appspot_com_.skp time=511 +68 http___www_richardmiller_co_uk_.skp time=528 +63 http___www_eschrade_com_.skp time=543 +55 http___www_interaction_inf_br_.skp time=625 +38 http___www_huskyliners_com_.skp time=632 +86 http___granda_net_.skp time=1067 +24 http___www_cocacolafm_com_br_.skp time=1081 +*/ + size_t skipOverSeptCount = sizeof(skipOverSept) / sizeof(skipOverSept[0]); enum TestStep { @@ -116,7 +226,7 @@ enum TestStep { }; enum { - kMaxLength = 128, + kMaxLength = 256, kMaxFiles = 128, kSmallLimit = 1000, }; @@ -190,6 +300,13 @@ public: } }; +class SortByName : public TestResult { +public: + bool operator<(const SortByName& rh) const { + return strcmp(fFilename, rh.fFilename) < 0; + } +}; + struct TestState { void init(int dirNo, skiatest::Reporter* reporter) { fReporter = reporter; @@ -217,11 +334,6 @@ struct TestRunner { class TestRunnable : public SkRunnable { public: - TestRunnable(void (*testFun)(TestState*), int dirNo, TestRunner* runner) { - fState.init(dirNo, runner->fReporter); - fTestFun = testFun; - } - virtual void run() SK_OVERRIDE { SkGraphics::SetTLSFontCacheLimit(1 * 1024 * 1024); (*fTestFun)(&fState); @@ -231,6 +343,33 @@ public: void (*fTestFun)(TestState*); }; + +class TestRunnableDir : public TestRunnable { +public: + TestRunnableDir(void (*testFun)(TestState*), int dirNo, TestRunner* runner) { + fState.init(dirNo, runner->fReporter); + fTestFun = testFun; + } + +}; + +class TestRunnableFile : public TestRunnable { +public: + TestRunnableFile(void (*testFun)(TestState*), int dirNo, const char* name, TestRunner* runner) { + fState.init(dirNo, runner->fReporter); + strcpy(fState.fResult.fFilename, name); + fTestFun = testFun; + } +}; + +class TestRunnableEncode : public TestRunnableFile { +public: + TestRunnableEncode(void (*testFun)(TestState*), int dirNo, const char* name, TestRunner* runner) + : TestRunnableFile(testFun, dirNo, name, runner) { + fState.fResult.fTestStep = kEncodeFiles; + } +}; + TestRunner::~TestRunner() { for (int index = 0; index < fRunnables.count(); index++) { SkDELETE(fRunnables[index]); @@ -272,6 +411,16 @@ static SkString make_in_dir_name(int dirNo) { return dirName; } +static SkString make_stat_dir_name(int dirNo) { + SkString dirName(outStatusDir); + dirName.appendf("%d", dirNo); + if (!sk_exists(dirName.c_str())) { + SkDebugf("could not read dir %s\n", dirName.c_str()); + return SkString(); + } + return dirName; +} + static bool make_one_out_dir(const char* outDirStr) { SkString outDir = make_filepath(0, outDirStr, ""); if (!sk_exists(outDir.c_str())) { @@ -675,32 +824,79 @@ static bool initTest() { return make_out_dirs(); } +static bool initUberTest(int firstDirNo, int lastDirNo) { + if (!initTest()) { + return false; + } + for (int index = firstDirNo; index <= lastDirNo; ++index) { + SkString statusDir(outStatusDir); + statusDir.appendf("%d", index); + if (!make_one_out_dir(statusDir.c_str())) { + return false; + } + } + return true; +} + + +static void testSkpClipEncode(TestState* data) { + data->fResult.testOne(); + if (data->fReporter->verbose()) { + SkDebugf("+"); + } +} + static void encodeFound(skiatest::Reporter* reporter, TestState& state) { if (reporter->verbose()) { - SkTDArray worst; - for (int index = 0; index < state.fPixelWorst.count(); ++index) { - *worst.append() = &state.fPixelWorst[index]; - } - SkTQSort(worst.begin(), worst.end() - 1); - for (int index = 0; index < state.fPixelWorst.count(); ++index) { - const TestResult& result = *worst[index]; - SkDebugf("%d %s pixelError=%d\n", result.fDirNo, result.fFilename, result.fPixelError); + if (state.fPixelWorst.count()) { + SkTDArray worst; + for (int index = 0; index < state.fPixelWorst.count(); ++index) { + *worst.append() = &state.fPixelWorst[index]; + } + SkTQSort(worst.begin(), worst.end() - 1); + for (int index = 0; index < state.fPixelWorst.count(); ++index) { + const TestResult& result = *worst[index]; + SkDebugf("%d %s pixelError=%d\n", result.fDirNo, result.fFilename, result.fPixelError); + } } - SkTDArray slowest; - for (int index = 0; index < state.fSlowest.count(); ++index) { - *slowest.append() = &state.fSlowest[index]; + if (state.fSlowest.count()) { + SkTDArray slowest; + for (int index = 0; index < state.fSlowest.count(); ++index) { + *slowest.append() = &state.fSlowest[index]; + } + if (slowest.count() > 0) { + SkTQSort(slowest.begin(), slowest.end() - 1); + for (int index = 0; index < slowest.count(); ++index) { + const TestResult& result = *slowest[index]; + SkDebugf("%d %s time=%d\n", result.fDirNo, result.fFilename, result.fTime); + } + } } - SkTQSort(slowest.begin(), slowest.end() - 1); - for (int index = 0; index < slowest.count(); ++index) { - const TestResult& result = *slowest[index]; - SkDebugf("%d %s time=%d\n", result.fDirNo, result.fFilename, result.fTime); + } + + int threadCount = reporter->allowThreaded() ? SkThreadPool::kThreadPerCore : 1; + TestRunner testRunner(reporter, threadCount); + for (int index = 0; index < state.fPixelWorst.count(); ++index) { + const TestResult& result = state.fPixelWorst[index]; + SkString filename(result.fFilename); + if (!filename.endsWith(".skp")) { + filename.append(".skp"); } + *testRunner.fRunnables.append() = SkNEW_ARGS(TestRunnableEncode, + (&testSkpClipEncode, result.fDirNo, filename.c_str(), &testRunner)); } + testRunner.render(); +#if 0 for (int index = 0; index < state.fPixelWorst.count(); ++index) { const TestResult& result = state.fPixelWorst[index]; - TestResult::Test(result.fDirNo, result.fFilename, kEncodeFiles); - if (state.fReporter->verbose()) SkDebugf("+"); + SkString filename(result.fFilename); + if (!filename.endsWith(".skp")) { + filename.append(".skp"); + } + TestResult::Test(result.fDirNo, filename.c_str(), kEncodeFiles); + if (reporter->verbose()) SkDebugf("+"); } +#endif } DEF_TEST(PathOpsSkpClip, reporter) { @@ -732,19 +928,177 @@ DEF_TEST(PathOpsSkpClipThreaded, reporter) { } int threadCount = reporter->allowThreaded() ? SkThreadPool::kThreadPerCore : 1; TestRunner testRunner(reporter, threadCount); - for (int dirNo = 1; dirNo <= 100; ++dirNo) { - *testRunner.fRunnables.append() = SkNEW_ARGS(TestRunnable, + const int firstDirNo = 1; + for (int dirNo = firstDirNo; dirNo <= 100; ++dirNo) { + *testRunner.fRunnables.append() = SkNEW_ARGS(TestRunnableDir, (&testSkpClipMain, dirNo, &testRunner)); } testRunner.render(); TestState state; state.init(0, reporter); - for (int dirNo = 1; dirNo <= 100; ++dirNo) { + for (int dirNo = firstDirNo; dirNo <= 100; ++dirNo) { TestState& testState = testRunner.fRunnables[dirNo - 1]->fState; + SkASSERT(testState.fResult.fDirNo == dirNo); for (int inner = 0; inner < testState.fPixelWorst.count(); ++inner) { - SkASSERT(testState.fResult.fDirNo == dirNo); addError(&state, testState.fPixelWorst[inner]); } + for (int inner = 0; inner < testState.fSlowest.count(); ++inner) { + addError(&state, testState.fSlowest[inner]); + } + } + encodeFound(reporter, state); +} + +static void testSkpClipUber(TestState* data) { + data->fResult.testOne(); + SkString dirName = make_stat_dir_name(data->fResult.fDirNo); + if (!dirName.size()) { + return; + } + SkString statName(data->fResult.fFilename); + SkASSERT(statName.endsWith(".skp")); + statName.remove(statName.size() - 4, 4); + statName.appendf(".%d.%d.skp", data->fResult.fPixelError, data->fResult.fTime); + SkString statusFile = make_filepath(data->fResult.fDirNo, outStatusDir, statName.c_str()); + SkFILE* file = sk_fopen(statusFile.c_str(), kWrite_SkFILE_Flag); + if (!file) { + SkDebugf("failed to create %s", statusFile.c_str()); + return; + } + sk_fclose(file); + if (data->fReporter->verbose()) { + if (data->fResult.fPixelError || data->fResult.fTime) { + SkDebugf("%s", data->fResult.progress().c_str()); + } else { + SkDebugf("."); + } + } +} + +static bool buildTests(skiatest::Reporter* reporter, int firstDirNo, int lastDirNo, SkTDArray* tests, + SkTDArray* sorted) { + for (int dirNo = firstDirNo; dirNo <= lastDirNo; ++dirNo) { + SkString dirName = make_stat_dir_name(dirNo); + if (!dirName.size()) { + return false; + } + SkOSFile::Iter iter(dirName.c_str(), "skp"); + SkString filename; + while (iter.next(&filename)) { + TestResult test; + test.init(dirNo); + SkString spaceFile(filename); + char* spaces = spaceFile.writable_str(); + int spaceSize = (int) spaceFile.size(); + for (int index = 0; index < spaceSize; ++index) { + if (spaces[index] == '.') { + spaces[index] = ' '; + } + } + int success = sscanf(spaces, "%s %d %d skp", test.fFilename, + &test.fPixelError, &test.fTime); + if (success < 3) { + SkDebugf("failed to scan %s matched=%d\n", filename.c_str(), success); + return false; + } + *tests[dirNo - firstDirNo].append() = test; + } + if (!sorted) { + continue; + } + SkTDArray& testSet = tests[dirNo - firstDirNo]; + int count = testSet.count(); + for (int index = 0; index < count; ++index) { + *sorted[dirNo - firstDirNo].append() = (SortByName*) &testSet[index]; + } + if (sorted[dirNo - firstDirNo].count()) { + SkTQSort(sorted[dirNo - firstDirNo].begin(), + sorted[dirNo - firstDirNo].end() - 1); + if (reporter->verbose()) { + SkDebugf("+"); + } + } + } + return true; +} + +bool Less(const SortByName& a, const SortByName& b); +bool Less(const SortByName& a, const SortByName& b) { + return a < b; +} + +DEF_TEST(PathOpsSkpClipUberThreaded, reporter) { + const int firstDirNo = 1; + const int lastDirNo = 100; + if (!initUberTest(firstDirNo, lastDirNo)) { + return; + } + const int dirCount = lastDirNo - firstDirNo + 1; + SkTDArray tests[dirCount]; + SkTDArray sorted[dirCount]; + if (!buildTests(reporter, firstDirNo, lastDirNo, tests, sorted)) { + return; + } + int threadCount = reporter->allowThreaded() ? SkThreadPool::kThreadPerCore : 1; + TestRunner testRunner(reporter, threadCount); + for (int dirNo = firstDirNo; dirNo <= lastDirNo; ++dirNo) { + SkString dirName = make_in_dir_name(dirNo); + if (!dirName.size()) { + continue; + } + SkOSFile::Iter iter(dirName.c_str(), "skp"); + SkString filename; + while (iter.next(&filename)) { + int count; + SortByName name; + for (size_t index = 0; index < skipOverSeptCount; ++index) { + if (skipOverSept[index].directory == dirNo + && strcmp(filename.c_str(), skipOverSept[index].filename) == 0) { + goto checkEarlyExit; + } + } + name.init(dirNo); + strncpy(name.fFilename, filename.c_str(), filename.size() - 4); // drop .skp + count = sorted[dirNo - firstDirNo].count(); + if (SkTSearch(sorted[dirNo - firstDirNo].begin(), + count, &name, sizeof(&name)) < 0) { + *testRunner.fRunnables.append() = SkNEW_ARGS(TestRunnableFile, + (&testSkpClipUber, dirNo, filename.c_str(), &testRunner)); + } + checkEarlyExit: + ; + } + + } + testRunner.render(); + SkTDArray results[dirCount]; + if (!buildTests(reporter, firstDirNo, lastDirNo, results, NULL)) { + return; + } + SkTDArray allResults; + for (int dirNo = firstDirNo; dirNo <= lastDirNo; ++dirNo) { + SkTDArray& array = results[dirNo - firstDirNo]; + allResults.append(array.count(), array.begin()); + } + int allCount = allResults.count(); + SkTDArray pixels; + SkTDArray times; + for (int index = 0; index < allCount; ++index) { + *pixels.append() = (SortByPixel*) &allResults[index]; + *times.append() = (SortByTime*) &allResults[index]; + } + TestState state; + if (pixels.count()) { + SkTQSort(pixels.begin(), pixels.end() - 1); + for (int inner = 0; inner < kMaxFiles; ++inner) { + *state.fPixelWorst.append() = *pixels[allCount - inner - 1]; + } + } + if (times.count()) { + SkTQSort(times.begin(), times.end() - 1); + for (int inner = 0; inner < kMaxFiles; ++inner) { + *state.fSlowest.append() = *times[allCount - inner - 1]; + } } encodeFound(reporter, state); } diff --git a/tests/PathOpsSkpTest.cpp b/tests/PathOpsSkpTest.cpp index 5b10a1f..3cfe4e2 100755 --- a/tests/PathOpsSkpTest.cpp +++ b/tests/PathOpsSkpTest.cpp @@ -9,7 +9,6 @@ #define TEST(name) { name, #name } #define TRY_NEW_TESTS 0 -#define TRY_NEW_TESTS_IS_CLOSED 0 static void skpcheeseandburger_com225(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -1809,15 +1808,6 @@ static void skpwww_heartiste_wordpress_com_86(skiatest::Reporter* reporter, cons testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -/* - * 125 SkASSERT(index < fCount); -(gdb) bt -#0 0x000000000041094b in SkTDArray::operator[] (this=0x18, index=2) at ../../include/core/SkTDArray.h:125 -#1 0x00000000005ad2ce in SkOpSegment::tAtMid (this=0x0, start=2, end=5, mid=0.90000000000000002) at ../../src/pathops/SkOpSegment.h:219 -#2 0x00000000005aadea in contourRangeCheckY (contourList=..., currentPtr=0x7fffd77f4ec0, indexPtr=0x7fffd77f4f88, endIndexPtr=0x7fffd77f4f8c, bestHit=0x7fffd77f4ec8, - bestDx=0x7fffd77f4edc, tryAgain=0x7fffd77f4eff, midPtr=0x7fffd77f4e60, opp=false) at ../../src/pathops/SkPathOpsCommon.cpp:20 -#3 0x00000000005ab8ee in rightAngleWinding (contourList=..., current=0x7fffd77f4ec0, index=0x7fffd77f4f88, endIndex=0x7fffd77f4f8c, tHit=0x7fffd77f4ec8, hitDx=0x7fffd77f4edc, - */ #if TRY_NEW_TESTS static void skpwww_argus_presse_fr_41(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -1988,8 +1978,6 @@ static void skpwww_hubbyscook_com_22(skiatest::Reporter* reporter, const char* f testPathOp(reporter, path, pathB, kDifference_PathOp, filename); } -// calcCoincidentWinding asserts in zeroSpan -#if TRY_NEW_TESTS static void skpwww_gruposejaumdivulgador_com_br_4(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2008,10 +1996,8 @@ static void skpwww_gruposejaumdivulgador_com_br_4(skiatest::Reporter* reporter, pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif // asserts in bridgeOp simple->isClosed() -#if TRY_NEW_TESTS_IS_CLOSED static void skpwww_phototransferapp_com_24(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2036,10 +2022,32 @@ static void skpwww_phototransferapp_com_24(skiatest::Reporter* reporter, const c pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif -// !simple->isClosed() -#if TRY_NEW_TESTS_IS_CLOSED +static void skpwww_phototransferapp_com_24x(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(85.6091843f, 5.92893219f); + path.quadTo(89.6041641f, 3, 93.7462997f, 3); + path.lineTo(112.74634f, 3); + path.quadTo(116.88843f, 3, 118.75134f, 5.92893219f); + path.quadTo(120.61414f, 8.85775471f, 119.10669f, 12.9996767f); + path.quadTo(120.46338f, 9.27196693f, 118.4939f, 6.63603878f); + path.quadTo(116.52441f, 4, 112.38232f, 4); + path.lineTo(93.3823318f, 4); + path.quadTo(89.2401962f, 4, 85.3518219f, 6.63603878f); + path.quadTo(81.4634476f, 9.27207756f, 80.1065979f, 13); + path.quadTo(81.614212f, 8.85786438f, 85.6091843f, 5.92893219f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(83.7462997f, 3); + pathB.lineTo(122.74634f, 3); + pathB.lineTo(119.10657f, 13); + pathB.lineTo(80.1065979f, 13); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + static void skpwww_helha_be_109(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2061,9 +2069,7 @@ static void skpwww_helha_be_109(skiatest::Reporter* reporter, const char* filena pathB.lineTo(104.291214f, 3359.87891f); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif -// !simple->isClosed() static void skpwww_cooksnaps_com_32(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2116,6 +2122,22 @@ static void skpwww_cooksnaps_com_32(skiatest::Reporter* reporter, const char* fi testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } +static void skpwww_cooksnaps_com_32a(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(497.299988f, 176.896912f); + path.quadTo(493.678162f, 177.952286f, 490.183014f, 179.9702f); + path.lineTo(489.316986f, 180.4702f); + path.quadTo(485.175385f, 182.861359f, 482.115265f, 186.082397f); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(474.873322f, 199.293594f); + pathB.quadTo(478.196686f, 186.890503f, 489.316986f, 180.4702f); + pathB.lineTo(490.183014f, 179.9702f); + pathB.quadTo(501.303345f, 173.549896f, 513.706421f, 176.873276f); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + // !simple->isClosed() static void skpwww_contextualnewsfeeds_com_346(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -2182,8 +2204,6 @@ static void skpwww_karnivool_com_au_11(skiatest::Reporter* reporter, const char* testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -// computeonesumreverse calls markwinding with 0 winding -#if TRY_NEW_TESTS static void skpwww_tunero_de_24(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2222,10 +2242,7 @@ static void skpwww_tunero_de_24(skiatest::Reporter* reporter, const char* filena pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif -// rightAngleWinding (probably same as argus_presse) -#if TRY_NEW_TESTS static void skpwww_docgelo_com_66(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2243,9 +2260,7 @@ static void skpwww_docgelo_com_66(skiatest::Reporter* reporter, const char* file pathB.lineTo(185.5f, 24174.75f); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif -// joinCoincidence / findT / assert static void skpwww_kpopexplorer_net_22(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2274,8 +2289,6 @@ static void skpwww_kpopexplorer_net_22(skiatest::Reporter* reporter, const char* testPathOp(reporter, path, pathB, kDifference_PathOp, filename); } -// rightAngleWinding -#if TRY_NEW_TESTS static void skpwww_artblart_com_8(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2293,7 +2306,6 @@ static void skpwww_artblart_com_8(skiatest::Reporter* reporter, const char* file pathB.lineTo(45, 24527.5f); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif // joinCoincidence / findT / assert static void skpwww_jessicaslens_wordpress_com_222(skiatest::Reporter* reporter, const char* filename) { @@ -2746,6 +2758,38 @@ static void skpwww_wartepop_blogspot_com_br_6(skiatest::Reporter* reporter, cons testPathOp(reporter, path, pathB, kDifference_PathOp, filename); } +static void skpwww_wartepop_blogspot_com_br_6a(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(90.9763107f, 153.309662f); + path.quadTo(91.9526215f, 152.333344f, 93.3333359f, 152.333344f); + path.lineTo(124.666672f, 152.333344f); + path.quadTo(126.047379f, 152.333344f, 127.023689f, 153.309662f); + path.quadTo(128, 154.285965f, 128, 155.666672f); + path.lineTo(128, 163.666672f); + path.lineTo(90, 163.666672f); + path.lineTo(90, 155.666672f); + path.quadTo(90, 154.285965f, 90.9763107f, 153.309662f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(90, 163.666672f); + pathB.lineTo(90, 155.666672f); + pathB.quadTo(90, 154.285965f, 90.9763107f, 153.309662f); + pathB.quadTo(91.9526215f, 152.333344f, 93.3333359f, 152.333344f); + pathB.lineTo(124.666672f, 152.333344f); + pathB.quadTo(125.909309f, 152.333344f, 126.787994f, 153.309662f); + pathB.quadTo(127.666672f, 154.285965f, 127.666672f, 155.666672f); + pathB.lineTo(127.666672f, 163.666672f); + pathB.lineTo(127.666672f, 163.666672f); + pathB.lineTo(127.666672f, 163.666672f); + pathB.lineTo(90, 163.666672f); + pathB.lineTo(90, 163.666672f); + pathB.lineTo(90, 163.666672f); + pathB.close(); + testPathOp(reporter, path, pathB, kDifference_PathOp, filename); +} + // !simple->isClosed() static void skpwww_odia_com_br_26(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -2868,8 +2912,6 @@ static void skpwww_galaxystwo_com_4(skiatest::Reporter* reporter, const char* fi testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -// hangs in find top -#if TRY_NEW_TESTS static void skpwww_thaienews_blogspot_com_36(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2887,9 +2929,7 @@ static void skpwww_thaienews_blogspot_com_36(skiatest::Reporter* reporter, const pathB.lineTo(430.5f, 6268); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif -// hangs static void skpwww_fashionscandal_com_94(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2962,8 +3002,6 @@ static void skpwww_defense_studies_blogspot_com_64(skiatest::Reporter* reporter, testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -// checkSmall / addTPair / addT assert -#if TRY_NEW_TESTS static void skpwww_uniquefx_net_442(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -2981,10 +3019,7 @@ static void skpwww_uniquefx_net_442(skiatest::Reporter* reporter, const char* fi pathB.lineTo(1019, 305); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif -// rightAngleWinding -#if TRY_NEW_TESTS static void skpwww_kitcheninspirations_wordpress_com_32(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -3002,58 +3037,570 @@ static void skpwww_kitcheninspirations_wordpress_com_32(skiatest::Reporter* repo pathB.lineTo(65.8333359f, 19651.5f); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif + +static void skpwww_educationalcraft_com_4(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(941, 1494); + path.lineTo(941, 1464); + path.lineTo(985, 1464); + path.lineTo(985, 1494); + path.lineTo(941, 1494); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(979.211975f, 1480.45496f); + pathB.cubicTo(979.211975f, 1480.45496f, 976.348999f, 1479.68506f, 977.495972f, 1475.59497f); + pathB.cubicTo(977.497009f, 1475.59497f, 981.072021f, 1477.88501f, 979.211975f, 1480.45496f); + pathB.close(); + pathB.moveTo(977.854004f, 1484.453f); + pathB.cubicTo(977.854004f, 1484.453f, 975.265991f, 1483.26099f, 976.713989f, 1479.35205f); + pathB.cubicTo(976.713989f, 1479.35303f, 979.84198f, 1482.23499f, 977.854004f, 1484.453f); + pathB.close(); + pathB.moveTo(980.226013f, 1476.229f); + pathB.cubicTo(980.226013f, 1476.229f, 977.078003f, 1476.349f, 977.234985f, 1471.97095f); + pathB.cubicTo(977.234985f, 1471.97095f, 980.666992f, 1473.12903f, 980.226013f, 1476.229f); + pathB.close(); + pathB.moveTo(984.546021f, 1478.31494f); + pathB.cubicTo(984.546021f, 1478.31494f, 983.187988f, 1481.93396f, 980.026001f, 1481.276f); + pathB.cubicTo(980.026978f, 1481.276f, 979.554993f, 1478.38904f, 984.546021f, 1478.31494f); + pathB.close(); + pathB.moveTo(978.989014f, 1484.198f); + pathB.cubicTo(978.989014f, 1484.198f, 979.094971f, 1481.33496f, 983.786011f, 1481.823f); + pathB.cubicTo(983.786011f, 1481.823f, 982.070007f, 1485.49805f, 978.989014f, 1484.198f); + pathB.close(); + pathB.moveTo(976.393005f, 1486.86804f); + pathB.cubicTo(976.393005f, 1486.86804f, 976.719971f, 1484.06494f, 981.679016f, 1485.37f); + pathB.cubicTo(981.679016f, 1485.37f, 979.169983f, 1488.40796f, 976.393005f, 1486.86804f); + pathB.close(); + pathB.moveTo(969.156982f, 1490.40002f); + pathB.cubicTo(969.156982f, 1490.40002f, 971.478027f, 1488.23596f, 974.869995f, 1491.21399f); + pathB.cubicTo(974.869995f, 1491.21497f, 970.828003f, 1493.026f, 969.156982f, 1490.40002f); + pathB.close(); + pathB.moveTo(972.825012f, 1483.93701f); + pathB.cubicTo(972.825012f, 1483.93701f, 973.971985f, 1487.98401f, 971.161987f, 1488.94604f); + pathB.cubicTo(971.161987f, 1488.94495f, 969.278015f, 1486.37097f, 972.825012f, 1483.93701f); + pathB.close(); + pathB.moveTo(965.60199f, 1489.98499f); + pathB.cubicTo(965.60199f, 1489.98499f, 964.879028f, 1487.19202f, 969.864014f, 1486.75f); + pathB.cubicTo(969.864014f, 1486.75f, 968.749023f, 1490.672f, 965.60199f, 1489.98499f); + pathB.close(); + pathB.moveTo(970.666992f, 1492.81604f); + pathB.cubicTo(970.666992f, 1492.81604f, 967.327026f, 1494.49695f, 964.999023f, 1491.56299f); + pathB.cubicTo(964.999023f, 1491.56299f, 967.304016f, 1489.43896f, 970.666992f, 1492.81604f); + pathB.close(); + pathB.moveTo(968.343994f, 1481.53796f); + pathB.cubicTo(971.573975f, 1479.94995f, 971.687988f, 1476.78601f, 971.687988f, 1476.78601f); + pathB.lineTo(971.393982f, 1466.83398f); + pathB.lineTo(954.960999f, 1466.83398f); + pathB.lineTo(954.666016f, 1476.78601f); + pathB.cubicTo(954.666016f, 1476.78601f, 954.780029f, 1479.94995f, 958.008972f, 1481.53796f); + pathB.cubicTo(960.781006f, 1482.90295f, 962.166992f, 1484.77698f, 962.166992f, 1484.77698f); + pathB.cubicTo(962.166992f, 1484.77698f, 962.747986f, 1485.70105f, 963.177979f, 1485.70105f); + pathB.cubicTo(963.606995f, 1485.70105f, 964.185974f, 1484.77698f, 964.185974f, 1484.77698f); + pathB.cubicTo(964.185974f, 1484.77698f, 965.573975f, 1482.90295f, 968.343994f, 1481.53796f); + pathB.close(); + pathB.moveTo(963.215027f, 1486.67004f); + pathB.cubicTo(962.744995f, 1486.67004f, 962.106995f, 1485.65405f, 962.106995f, 1485.65405f); + pathB.cubicTo(962.106995f, 1485.65405f, 960.585022f, 1483.59595f, 957.539001f, 1482.09705f); + pathB.cubicTo(953.991028f, 1480.35205f, 953.867004f, 1476.87598f, 953.867004f, 1476.87598f); + pathB.lineTo(954.190002f, 1465.94397f); + pathB.lineTo(972.23999f, 1465.94397f); + pathB.lineTo(972.565002f, 1476.87695f); + pathB.cubicTo(972.565002f, 1476.87695f, 972.440979f, 1480.35303f, 968.891968f, 1482.09802f); + pathB.cubicTo(965.846008f, 1483.59705f, 964.325012f, 1485.65503f, 964.325012f, 1485.65503f); + pathB.cubicTo(964.325012f, 1485.65503f, 963.687012f, 1486.67004f, 963.215027f, 1486.67004f); + pathB.close(); + pathB.moveTo(960.68103f, 1489.98499f); + pathB.cubicTo(957.533997f, 1490.672f, 956.417969f, 1486.75f, 956.417969f, 1486.75f); + pathB.cubicTo(961.403015f, 1487.19202f, 960.68103f, 1489.98499f, 960.68103f, 1489.98499f); + pathB.close(); + pathB.moveTo(963.143005f, 1489.59802f); + pathB.cubicTo(963.763f, 1489.59802f, 964.265015f, 1490.09998f, 964.265015f, 1490.72095f); + pathB.cubicTo(964.265015f, 1491.34204f, 963.763f, 1491.84399f, 963.143005f, 1491.84399f); + pathB.cubicTo(962.521973f, 1491.84399f, 962.02002f, 1491.34204f, 962.02002f, 1490.72095f); + pathB.cubicTo(962.02002f, 1490.09998f, 962.521973f, 1489.59802f, 963.143005f, 1489.59802f); + pathB.close(); + pathB.moveTo(961.283997f, 1491.56299f); + pathB.cubicTo(958.953979f, 1494.49695f, 955.61499f, 1492.81604f, 955.61499f, 1492.81604f); + pathB.cubicTo(958.97699f, 1489.43896f, 961.283997f, 1491.56299f, 961.283997f, 1491.56299f); + pathB.close(); + pathB.moveTo(957.127014f, 1490.40002f); + pathB.cubicTo(955.455017f, 1493.026f, 951.414001f, 1491.21399f, 951.414001f, 1491.21399f); + pathB.cubicTo(954.802979f, 1488.23596f, 957.127014f, 1490.40002f, 957.127014f, 1490.40002f); + pathB.close(); + pathB.moveTo(949.890991f, 1486.86804f); + pathB.cubicTo(947.112976f, 1488.40796f, 944.604004f, 1485.37f, 944.604004f, 1485.37f); + pathB.cubicTo(949.562012f, 1484.06494f, 949.890991f, 1486.86804f, 949.890991f, 1486.86804f); + pathB.close(); + pathB.moveTo(947.070984f, 1480.45496f); + pathB.cubicTo(945.211975f, 1477.88501f, 948.786011f, 1475.59497f, 948.786011f, 1475.59497f); + pathB.cubicTo(949.934021f, 1479.68506f, 947.070984f, 1480.45496f, 947.070984f, 1480.45496f); + pathB.close(); + pathB.moveTo(946.054016f, 1476.229f); + pathB.cubicTo(945.61499f, 1473.12903f, 949.046997f, 1471.97095f, 949.046997f, 1471.97095f); + pathB.cubicTo(949.205994f, 1476.349f, 946.054016f, 1476.229f, 946.054016f, 1476.229f); + pathB.close(); + pathB.moveTo(948.427002f, 1484.453f); + pathB.cubicTo(946.440002f, 1482.23499f, 949.567993f, 1479.35205f, 949.567993f, 1479.35205f); + pathB.cubicTo(951.015991f, 1483.26099f, 948.427002f, 1484.453f, 948.427002f, 1484.453f); + pathB.close(); + pathB.moveTo(947.294006f, 1484.198f); + pathB.cubicTo(944.210999f, 1485.49805f, 942.495972f, 1481.823f, 942.495972f, 1481.823f); + pathB.cubicTo(947.187988f, 1481.33496f, 947.294006f, 1484.198f, 947.294006f, 1484.198f); + pathB.close(); + pathB.moveTo(946.255005f, 1481.276f); + pathB.cubicTo(943.094971f, 1481.93396f, 941.736023f, 1478.31494f, 941.736023f, 1478.31494f); + pathB.cubicTo(946.728027f, 1478.38904f, 946.255005f, 1481.276f, 946.255005f, 1481.276f); + pathB.close(); + pathB.moveTo(945.312988f, 1478.18005f); + pathB.cubicTo(942.052979f, 1477.80103f, 942.651001f, 1473.87805f, 942.651001f, 1473.87805f); + pathB.cubicTo(946.562988f, 1475.66199f, 945.312988f, 1478.18005f, 945.312988f, 1478.18005f); + pathB.close(); + pathB.moveTo(945.382019f, 1474.328f); + pathB.cubicTo(942.924011f, 1472.729f, 944.492004f, 1469.48706f, 944.492004f, 1469.48706f); + pathB.cubicTo(947.388977f, 1471.95703f, 945.382019f, 1474.328f, 945.382019f, 1474.328f); + pathB.close(); + pathB.moveTo(946.797974f, 1470.27405f); + pathB.cubicTo(944.664978f, 1467.90198f, 947.083984f, 1465.50598f, 947.083984f, 1465.50598f); + pathB.cubicTo(949.145996f, 1468.82605f, 946.797974f, 1470.27405f, 946.797974f, 1470.27405f); + pathB.close(); + pathB.moveTo(947.392029f, 1471.64197f); + pathB.cubicTo(947.624023f, 1468.56299f, 951.361023f, 1468.29199f, 951.361023f, 1468.29199f); + pathB.cubicTo(950.554016f, 1471.98499f, 947.392029f, 1471.64197f, 947.392029f, 1471.64197f); + pathB.close(); + pathB.moveTo(948.64801f, 1468.15002f); + pathB.cubicTo(948.638977f, 1465.22095f, 952.265991f, 1464.46399f, 952.265991f, 1464.46399f); + pathB.cubicTo(951.672974f, 1468.53101f, 948.64801f, 1468.15002f, 948.64801f, 1468.15002f); + pathB.close(); + pathB.moveTo(951.176025f, 1486.97803f); + pathB.cubicTo(948.963013f, 1484.62f, 951.361023f, 1481.77698f, 951.361023f, 1481.77698f); + pathB.cubicTo(953.734985f, 1485.48596f, 951.176025f, 1486.97803f, 951.176025f, 1486.97803f); + pathB.close(); + pathB.moveTo(947.51001f, 1488.53101f); + pathB.cubicTo(947.51001f, 1488.53101f, 951.596985f, 1486.32202f, 953.234009f, 1489.08997f); + pathB.cubicTo(953.234009f, 1489.08997f, 951.158997f, 1491.03601f, 947.51001f, 1488.53101f); + pathB.close(); + pathB.moveTo(955.120972f, 1488.94495f); + pathB.cubicTo(952.309021f, 1487.98303f, 953.458984f, 1483.93604f, 953.458984f, 1483.93604f); + pathB.cubicTo(957.004028f, 1486.37097f, 955.120972f, 1488.94495f, 955.120972f, 1488.94495f); + pathB.close(); + pathB.moveTo(978.770996f, 1488.53101f); + pathB.cubicTo(975.122986f, 1491.03601f, 973.047974f, 1489.08997f, 973.047974f, 1489.08997f); + pathB.cubicTo(974.684998f, 1486.32202f, 978.770996f, 1488.53101f, 978.770996f, 1488.53101f); + pathB.close(); + pathB.moveTo(975.106995f, 1486.97803f); + pathB.cubicTo(975.106995f, 1486.97803f, 972.546997f, 1485.48706f, 974.919983f, 1481.77698f); + pathB.cubicTo(974.919983f, 1481.776f, 977.31897f, 1484.61902f, 975.106995f, 1486.97803f); + pathB.close(); + pathB.moveTo(974.016968f, 1464.46399f); + pathB.cubicTo(974.016968f, 1464.46399f, 977.643982f, 1465.22095f, 977.633972f, 1468.15002f); + pathB.cubicTo(977.633972f, 1468.15002f, 974.611023f, 1468.53101f, 974.016968f, 1464.46399f); + pathB.close(); + pathB.moveTo(974.919983f, 1468.29199f); + pathB.cubicTo(974.919983f, 1468.29199f, 978.658997f, 1468.56299f, 978.890015f, 1471.64197f); + pathB.cubicTo(978.890015f, 1471.64197f, 975.72699f, 1471.98499f, 974.919983f, 1468.29199f); + pathB.close(); + pathB.moveTo(979.197998f, 1465.50598f); + pathB.cubicTo(979.197998f, 1465.50598f, 981.619019f, 1467.90198f, 979.481995f, 1470.27405f); + pathB.cubicTo(979.481995f, 1470.27405f, 977.138f, 1468.82605f, 979.197998f, 1465.50598f); + pathB.close(); + pathB.moveTo(980.900024f, 1474.328f); + pathB.cubicTo(980.900024f, 1474.328f, 978.893005f, 1471.95703f, 981.791016f, 1469.48706f); + pathB.cubicTo(981.791016f, 1469.48596f, 983.358032f, 1472.729f, 980.900024f, 1474.328f); + pathB.close(); + pathB.moveTo(980.968994f, 1478.18005f); + pathB.cubicTo(980.968994f, 1478.18005f, 979.718018f, 1475.66199f, 983.632019f, 1473.87805f); + pathB.cubicTo(983.632019f, 1473.87805f, 984.229004f, 1477.80103f, 980.968994f, 1478.18005f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_narayana_publishers_com_194(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(1083.34314f, 445.65686f); + path.quadTo(1081, 443.313721f, 1081, 440); + path.lineTo(1257, 440); + path.quadTo(1257, 443.313721f, 1254.65686f, 445.65686f); + path.quadTo(1252.31372f, 448, 1249, 448); + path.lineTo(1089, 448); + path.quadTo(1085.68628f, 448, 1083.34314f, 445.65686f); + path.close(); + path.moveTo(1083, 441); + path.lineTo(1255, 441); + path.quadTo(1255, 443.071075f, 1253.53552f, 444.535522f); + path.quadTo(1252.07104f, 446, 1250, 446); + path.lineTo(1088, 446); + path.quadTo(1085.92896f, 446, 1084.46448f, 444.535522f); + path.quadTo(1083, 443.071075f, 1083, 441); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1081, 440); + pathB.lineTo(1082, 440); + pathB.lineTo(1090.01001f, 448); + pathB.lineTo(1081, 448); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_cooksnaps_com_17(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(170.340179f, 176); + path.lineTo(166, 176); + path.quadTo(161.964188f, 176, 158.299957f, 176.896912f); + path.quadTo(154.678162f, 177.952271f, 151.183014f, 179.9702f); + path.lineTo(150.316986f, 180.4702f); + path.quadTo(146.175812f, 182.861099f, 143.115921f, 186.081696f); + path.quadTo(140.693939f, 188.70134f, 138.99472f, 191.620407f); + path.quadTo(137.316833f, 194.550888f, 136.259338f, 197.957367f); + path.quadTo(135, 202.217865f, 135, 207); + path.lineTo(135, 208); + path.quadTo(135, 212.035751f, 135.896912f, 215.699997f); + path.quadTo(136.952286f, 219.321869f, 138.9702f, 222.816986f); + path.lineTo(139.4702f, 223.683014f); + path.quadTo(141.861099f, 227.824188f, 145.081696f, 230.884079f); + path.quadTo(147.70134f, 233.306061f, 150.620407f, 235.00528f); + path.quadTo(153.550888f, 236.683167f, 156.957367f, 237.740662f); + path.quadTo(161.217865f, 239, 166, 239); + path.lineTo(170.482162f, 239); + path.quadTo(176.307037f, 238.210968f, 181.816986f, 235.0298f); + path.lineTo(182.683014f, 234.5298f); + path.quadTo(182.686462f, 234.527817f, 182.689896f, 234.525818f); + path.quadTo(193.804352f, 228.105652f, 197.126709f, 215.70639f); + path.quadTo(200.450104f, 203.303314f, 194.0298f, 192.183014f); + path.lineTo(193.5298f, 191.316986f); + path.quadTo(187.109497f, 180.196686f, 174.706406f, 176.873276f); + path.quadTo(172.503067f, 176.282898f, 170.340179f, 176); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(139.4702f, 223.683014f); + pathB.lineTo(138.9702f, 222.816986f); + pathB.quadTo(132.549896f, 211.696686f, 135.873291f, 199.293594f); + pathB.quadTo(139.196686f, 186.890503f, 150.316986f, 180.4702f); + pathB.lineTo(151.183014f, 179.9702f); + pathB.quadTo(162.303314f, 173.549896f, 174.706406f, 176.873276f); + pathB.quadTo(187.109497f, 180.196686f, 193.5298f, 191.316986f); + pathB.lineTo(194.0298f, 192.183014f); + pathB.quadTo(200.450104f, 203.303314f, 197.126709f, 215.70639f); + pathB.quadTo(193.803314f, 228.109497f, 182.683014f, 234.5298f); + pathB.lineTo(181.816986f, 235.0298f); + pathB.quadTo(170.696686f, 241.450104f, 158.293594f, 238.126709f); + pathB.quadTo(145.890503f, 234.803314f, 139.4702f, 223.683014f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_swapspacesystems_com_5(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(819.050781f, 5539.72412f); + path.quadTo(819.651672f, 5539.1543f, 820.479858f, 5539.17578f); + path.lineTo(1191.35278f, 5548.8877f); + path.quadTo(1192.18091f, 5548.90918f, 1192.7511f, 5549.50977f); + path.quadTo(1193.32141f, 5550.11133f, 1193.29968f, 5550.93945f); + path.lineTo(1186.57214f, 5807.85107f); + path.quadTo(1186.55054f, 5808.6792f, 1185.94958f, 5809.24951f); + path.quadTo(1185.34863f, 5809.81982f, 1184.52051f, 5809.79834f); + path.lineTo(813.647705f, 5800.08643f); + path.quadTo(812.819519f, 5800.06494f, 812.249268f, 5799.46387f); + path.quadTo(811.679016f, 5798.86279f, 811.700684f, 5798.03467f); + path.lineTo(818.428162f, 5541.12305f); + path.quadTo(818.44989f, 5540.29492f, 819.050781f, 5539.72412f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(818.48053f, 5539.12354f); + pathB.lineTo(1193.35205f, 5548.93994f); + pathB.lineTo(1186.5199f, 5809.85059f); + pathB.lineTo(811.648376f, 5800.03418f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_kitcheninspirations_wordpress_com_66(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(47.1666679f, 27820.668f); + path.lineTo(60.8333359f, 27820.668f); + path.lineTo(60.8333359f, 27820.498f); + path.lineTo(47.1666679f, 27820.5f); + path.lineTo(47.1666679f, 27820.668f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(47.1666679f, 27820.668f); + pathB.lineTo(47.1666679f, 27820.498f); + pathB.lineTo(60.8333359f, 27820.5f); + pathB.lineTo(60.8333359f, 27820.668f); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_etiqadd_com_2464(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(630.378662f, 1293.42896f); + path.quadTo(631.257385f, 1292.55029f, 632.5f, 1292.55029f); + path.quadTo(633.742615f, 1292.55029f, 634.621338f, 1293.42896f); + path.lineTo(639.571045f, 1298.37866f); + path.quadTo(640.449768f, 1299.25732f, 640.449707f, 1300.5f); + path.quadTo(640.449768f, 1301.74268f, 639.571045f, 1302.62134f); + path.lineTo(634.621338f, 1307.57104f); + path.quadTo(633.742615f, 1308.44971f, 632.5f, 1308.44971f); + path.quadTo(631.257385f, 1308.44971f, 630.378662f, 1307.57104f); + path.lineTo(625.428955f, 1302.62134f); + path.quadTo(624.550232f, 1301.74268f, 624.550293f, 1300.5f); + path.quadTo(624.550232f, 1299.25732f, 625.428955f, 1298.37866f); + path.lineTo(630.378662f, 1293.42896f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(632.5f, 1291.30762f); + pathB.lineTo(641.692383f, 1300.5f); + pathB.lineTo(632.5f, 1309.69238f); + pathB.lineTo(623.307617f, 1300.5f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_narayana_verlag_de_194(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(1083.34314f, 513.65686f); + path.quadTo(1081, 511.313721f, 1081, 508); + path.lineTo(1257, 508); + path.quadTo(1257, 511.313721f, 1254.65686f, 513.65686f); + path.quadTo(1252.31372f, 516, 1249, 516); + path.lineTo(1089, 516); + path.quadTo(1085.68628f, 516, 1083.34314f, 513.65686f); + path.close(); + path.moveTo(1083, 509); + path.lineTo(1255, 509); + path.quadTo(1255, 511.071075f, 1253.53552f, 512.535522f); + path.quadTo(1252.07104f, 514, 1250, 514); + path.lineTo(1088, 514); + path.quadTo(1085.92896f, 514, 1084.46448f, 512.535522f); + path.quadTo(1083, 511.071075f, 1083, 509); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1081, 508); + pathB.lineTo(1082, 508); + pathB.lineTo(1090.01001f, 516); + pathB.lineTo(1081, 516); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_americascup_com_108(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(999.454102f, 689.17157f); + path.quadTo(1001.172f, 688, 1002.82886f, 688); + path.lineTo(1013.82886f, 688); + path.lineTo(1002.17114f, 713); + path.lineTo(991.171143f, 713); + path.quadTo(989.514282f, 713, 988.889038f, 711.82843f); + path.quadTo(988.263794f, 710.65686f, 989.036377f, 709); + path.lineTo(996.963623f, 692); + path.quadTo(997.736206f, 690.34314f, 999.454102f, 689.17157f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(998.828857f, 688); + pathB.lineTo(1013.82886f, 688); + pathB.lineTo(1002.17114f, 713); + pathB.lineTo(987.171143f, 713); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_vantageproduction_com_109(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(794.514709f, 759.485291f); + path.quadTo(791, 755.970581f, 791, 751); + path.lineTo(1133, 751); + path.quadTo(1133, 755.970581f, 1129.48523f, 759.485291f); + path.quadTo(1125.97058f, 763, 1121, 763); + path.lineTo(803, 763); + path.quadTo(798.029419f, 763, 794.514709f, 759.485291f); + path.close(); + path.moveTo(793, 752); + path.lineTo(1131, 752); + path.quadTo(1131, 755.727905f, 1128.36401f, 758.363953f); + path.quadTo(1125.72791f, 761, 1122, 761); + path.lineTo(802, 761); + path.quadTo(798.272095f, 761, 795.636047f, 758.363953f); + path.quadTo(793, 755.727905f, 793, 752); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(791, 751); + pathB.lineTo(792, 751); + pathB.lineTo(804.01001f, 763); + pathB.lineTo(791, 763); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_aceinfographics_com_106(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(166.878677f, 7638.87891f); + path.quadTo(166, 7639.75732f, 166, 7641); + path.lineTo(166, 11577); + path.quadTo(166, 11578.2422f, 166.878677f, 11579.1211f); + path.quadTo(167.388f, 11579.6309f, 168.019989f, 11579.8447f); + path.lineTo(168.019974f, 11576.2979f); + path.quadTo(168, 11576.1533f, 168, 11576); + path.lineTo(168, 7642); + path.lineTo(168.000015f, 7641.99316f); + path.lineTo(168, 7640); + path.lineTo(166.878677f, 7638.87891f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(166, 7638); + pathB.lineTo(168.020004f, 7635.97998f); + pathB.lineTo(168, 11578); + pathB.lineTo(166, 11580); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_tcmevents_org_13(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(465.951904f, 547.960144f); + path.quadTo(465.66571f, 546.867371f, 465.404938f, 546); + path.lineTo(465.504089f, 546); + path.quadTo(465.670349f, 546.601257f, 465.84668f, 547.288391f); + path.quadTo(467.274506f, 552.852356f, 468.506836f, 560.718567f); + path.quadTo(467.336121f, 553.24585f, 465.951904f, 547.960144f); + path.close(); + path.moveTo(470.591064f, 574.024353f); + path.quadTo(474.844055f, 601.176025f, 471.728271f, 620.364502f); + path.quadTo(470.567017f, 627.515991f, 468.635742f, 632); + path.lineTo(469.106812f, 632); + path.quadTo(470.791504f, 627.638672f, 471.833496f, 621.036255f); + path.quadTo(474.905701f, 601.569519f, 470.591064f, 574.024353f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(322.992462f, 541.475708f); + pathB.lineTo(465.531616f, 541.724426f); + pathB.lineTo(468.507751f, 560.724426f); + pathB.lineTo(325.968597f, 560.475708f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_paseoitaigara_com_br_56(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(633.147217f, 1247); + path.lineTo(718, 1162.14722f); + path.lineTo(802.852783f, 1247); + path.lineTo(718, 1331.85278f); + path.lineTo(633.147217f, 1247); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(635.268494f, 1244.87866f); + pathB.lineTo(715.878662f, 1164.26855f); + pathB.quadTo(716.757385f, 1163.38989f, 718, 1163.38989f); + pathB.quadTo(719.242615f, 1163.38989f, 720.121338f, 1164.26855f); + pathB.lineTo(800.731506f, 1244.87866f); + pathB.quadTo(801.610168f, 1245.75732f, 801.610168f, 1247); + pathB.quadTo(801.610229f, 1248.24268f, 800.731445f, 1249.12134f); + pathB.lineTo(720.121338f, 1329.73145f); + pathB.quadTo(719.242676f, 1330.61011f, 718, 1330.61011f); + pathB.quadTo(716.757385f, 1330.61011f, 715.878723f, 1329.73145f); + pathB.lineTo(635.268555f, 1249.12134f); + pathB.quadTo(634.389832f, 1248.24268f, 634.389832f, 1247); + pathB.quadTo(634.389832f, 1245.75732f, 635.268494f, 1244.87866f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} + +static void skpwww_mortgagemarketguide_com_109(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(816.514709f, 781.485291f); + path.quadTo(813, 777.970581f, 813, 773); + path.lineTo(1133, 773); + path.quadTo(1133, 777.970581f, 1129.48523f, 781.485291f); + path.quadTo(1125.97058f, 785, 1121, 785); + path.lineTo(825, 785); + path.quadTo(820.029419f, 785, 816.514709f, 781.485291f); + path.close(); + path.moveTo(815, 774); + path.lineTo(1131, 774); + path.quadTo(1131, 777.727905f, 1128.36401f, 780.363953f); + path.quadTo(1125.72791f, 783, 1122, 783); + path.lineTo(824, 783); + path.quadTo(820.272095f, 783, 817.636047f, 780.363953f); + path.quadTo(815, 777.727905f, 815, 774); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(813, 773); + pathB.lineTo(814, 773); + pathB.lineTo(826.01001f, 785); + pathB.lineTo(813, 785); + testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); +} static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static struct TestDesc tests[] = { + TEST(skpwww_wartepop_blogspot_com_br_6), + TEST(skpwww_wartepop_blogspot_com_br_6a), + TEST(skpwww_cooksnaps_com_32a), #if TRY_NEW_TESTS - TEST(skpwww_kitcheninspirations_wordpress_com_32), // rightanglewinding -#endif -#if TRY_NEW_TESTS - TEST(skpwww_uniquefx_net_442), // checkSmall / addTPair / addT assert + TEST(skpwww_argus_presse_fr_41), #endif + TEST(skpwww_cooksnaps_com_17), + TEST(skpwww_cooksnaps_com_32), + TEST(skpwww_kitcheninspirations_wordpress_com_66), + TEST(skpwww_tcmevents_org_13), + TEST(skpwww_narayana_publishers_com_194), + TEST(skpwww_swapspacesystems_com_5), + TEST(skpwww_vantageproduction_com_109), + TEST(skpwww_americascup_com_108), + TEST(skpwww_narayana_verlag_de_194), + TEST(skpwww_etiqadd_com_2464), + TEST(skpwww_paseoitaigara_com_br_56), + TEST(skpwww_mortgagemarketguide_com_109), + TEST(skpwww_aceinfographics_com_106), + TEST(skpwww_educationalcraft_com_4), + TEST(skpwww_kitcheninspirations_wordpress_com_32), + TEST(skpwww_artblart_com_8), + TEST(skpwww_docgelo_com_66), + TEST(skpwww_uniquefx_net_442), TEST(skpwww_defense_studies_blogspot_com_64), TEST(skpwww_kenlevine_blogspot_com_28), TEST(skpwww_fashionscandal_com_94), -#if TRY_NEW_TESTS - TEST(skpwww_thaienews_blogspot_com_36), // completes but fails to produce correct output -#endif + TEST(skpwww_thaienews_blogspot_com_36), TEST(skpwww_galaxystwo_com_4), TEST(skpwww_catingueiraonline_com_352), TEST(skpwww_evolvehq_com_210), - TEST(skpwww_odia_com_br_26), // asserts expecting isClosed - TEST(skpwww_wartepop_blogspot_com_br_6), // asserts expecting isClosed + TEST(skpwww_odia_com_br_26), TEST(skpwww_lokado_de_173), TEST(skpwww_seopack_blogspot_com_2153), TEST(skpwww_partsdata_de_53), TEST(skpwww_simplysaru_com_40), TEST(skpwww_jessicaslens_wordpress_com_222), -#if TRY_NEW_TESTS - TEST(skpwww_artblart_com_8), // rightanglewinding -#endif TEST(skpwww_kpopexplorer_net_22), -#if TRY_NEW_TESTS - TEST(skpwww_docgelo_com_66), // rightanglewinding -#endif -#if TRY_NEW_TESTS // nearly coincident curves -- maybe angle is written before coincidence detected? - TEST(skpwww_tunero_de_24), // has both winding and oppWinding set to zero in markWinding -#endif + TEST(skpwww_tunero_de_24), TEST(skpwww_karnivool_com_au_11), TEST(skpwww_pindosiya_com_99), - TEST(skpwww_contextualnewsfeeds_com_346), // asserts expecting isClosed - TEST(skpwww_cooksnaps_com_32), // asserts expecting isClosed -#if TRY_NEW_TESTS_IS_CLOSED - TEST(skpwww_helha_be_109), // asserts expecting isClosed - TEST(skpwww_phototransferapp_com_24), // asserts expecting isClosed -#endif -#if TRY_NEW_TESTS - TEST(skpwww_gruposejaumdivulgador_com_br_4), // span already marked done is futher marked coin -#endif + TEST(skpwww_contextualnewsfeeds_com_346), + TEST(skpwww_helha_be_109), + TEST(skpwww_phototransferapp_com_24), + TEST(skpwww_phototransferapp_com_24x), + TEST(skpwww_gruposejaumdivulgador_com_br_4), TEST(skpwww_hubbyscook_com_22), -#if TRY_NEW_TESTS - TEST(skpwww_argus_presse_fr_41), // rightanglewinding -#endif TEST(skpwww_maturesupertube_com_21), TEST(skpwww_getgold_jp_731), TEST(skpwww_trashness_com_36), @@ -3072,17 +3619,17 @@ static struct TestDesc tests[] = { TEST(skpskpicture15), TEST(skpwww_meb_gov_tr_6), TEST(skpwww_sciality_com_101), - TEST(skpwww_booking_com_68), // similar to lavoixdunord - TEST(skpwww_despegar_com_mx_272), // similar to lavoixdunord - TEST(skpwww_lavoixdunord_fr_11), // not quite coincident, sorting line/cubic fails - TEST(skppptv_com_62), // cubic have nearly identical tangents, sort incorrectly + TEST(skpwww_booking_com_68), + TEST(skpwww_despegar_com_mx_272), + TEST(skpwww_lavoixdunord_fr_11), + TEST(skppptv_com_62), TEST(skppchappy_com_au102), TEST(skpsciality_com161), TEST(skpi_gino_com16), - TEST(skpnaoxrane_ru23), // see test for failure evaluation - TEST(skptcmevents_org23), // see test for (partial) failure evaluation - TEST(skpredbullskatearcade_es16), // cubic have nearly identical tangents, sort incorrectly - TEST(skpfinanzasdigital_com9), // cubic/quad tangents too close to sort + TEST(skpnaoxrane_ru23), + TEST(skptcmevents_org23), + TEST(skpredbullskatearcade_es16), + TEST(skpfinanzasdigital_com9), TEST(skpgithub_io_26), TEST(skpgithub_io_25), TEST(skpwww_meb_gov_tr_5), diff --git a/tools/pathops_sorter.htm b/tools/pathops_sorter.htm index 41314f6..865cbbf 100644 --- a/tools/pathops_sorter.htm +++ b/tools/pathops_sorter.htm @@ -1,4 +1,4 @@ - + @@ -899,12 +899,69 @@ op intersect {{{-308.65463091760211, -549.4520029924679} -308.65463091760211, -569.4520029924679
+
+{{{974.91998291015625, 1481.7769775390625}, {974.91998291015625, 1481.7760009765625}, {977.3189697265625, 1484.6190185546875}, {975.10699462890625, 1486.97802734375}}} +{{fX=974.91998291015625 fY=1481.7769775390625 }, {fX=974.92071342468262 fY=1481.7972941398621 }} } +
+ +
+{{{962.10699462890625, 1485.654052734375}, {962.10699462890625, 1485.654052734375}, {960.58502197265625, 1483.595947265625}, {957.53900146484375, 1482.0970458984375}}} +{{{963.21502685546875, 1486.6700439453125}, {962.7449951171875, 1486.6700439453125}, {962.10699462890625, 1485.654052734375}, {962.10699462890625, 1485.654052734375}}} +
+ +
+{{{980.9000244140625, 1474.3280029296875}, {980.9000244140625, 1474.3280029296875}, {978.89300537109375, 1471.95703125}, {981.791015625, 1469.487060546875}}} +{{{981.791015625, 1469.487060546875}, {981.791015625, 1469.4859619140625}, {983.3580322265625, 1472.72900390625}, {980.9000244140625, 1474.3280029296875}}} +
+ +
+{{{168, 29.6722088f}, {166, 29.6773338f}}} +{{{166.878677f, 29.6750813f}, {167.388f, 29.6763878f}, {168.019989f, 29.6769352f}}} +
+ +
+{{{465.84668f, 547.288391f}, {467.274506f, 552.852356f}, {468.506836f, 560.718567f}}} +{{{468.506836f, 560.718567f}, {467.336121f, 553.24585f}, {465.951904f, 547.960144f}} +
+ +
+{{{60.8333359f, 27820.498f}, {47.1666679f, 27820.5f}}} +{{{60.8333359f, 27820.668f}, {60.8333359f, 27820.498f}}} +{{{47.1666679f, 27820.498f}, {60.8333359f, 27820.5f}}} +{{{60.8333359f, 27820.5f}, {60.8333359f, 27820.668f}}} +
+ +
+{{{10105, 2510}, {10123, 2509.98999f}}} +{{{10105, 2509.98999f}, {10123, 2510}}} +
+ +
+{{{124.666672f, 152.333344f}, {125.909309f, 152.333344f}, {126.787994f, 153.309662f}}} +{{fX=124.66666412353516 fY=152.33334350585937 }, {fX=126.78799438476562 fY=153.30966186523437 }} } +{{fX=124.66666412353516 fY=152.33334350585937 }, {fX=127.02368927001953 fY=153.30966186523437 }} } +
+ +
+{{{124.666672f, 152.333344f}, {125.909309f, 152.333344f}, {126.787994f, 153.309662f}}} +{{fX=124.66667175292969 fY=152.33334350585937 }, {fX=126.78799438476562 fY=153.30966186523437 }} } +{{fX=124.66667175292969 fY=152.33334350585937 }, {fX=127.02368927001953 fY=153.30966186523437 }} } +
+ + + + + + -- 2.7.4