diff options
31 files changed, 2454 insertions, 378 deletions
diff --git a/gyp/pathops_unittest.gypi b/gyp/pathops_unittest.gypi index d8eac0134e..923a25a5b8 100644 --- a/gyp/pathops_unittest.gypi +++ b/gyp/pathops_unittest.gypi @@ -28,6 +28,7 @@ '../tests/PathOpsBuildUseTest.cpp', '../tests/PathOpsConicIntersectionTest.cpp', '../tests/PathOpsConicLineIntersectionTest.cpp', + '../tests/PathOpsCubicConicIntersectionTest.cpp', '../tests/PathOpsCubicIntersectionTest.cpp', '../tests/PathOpsCubicIntersectionTestData.cpp', '../tests/PathOpsCubicLineIntersectionTest.cpp', diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 8bdb70be88..43d29d93e0 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -497,6 +497,9 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc default: SkASSERT(0); } +#if DEBUG_T_SECT_LOOP_COUNT + test->globalState()->debugAddLoopCount(&ts, wt, wn); +#endif int coinIndex = -1; SkOpPtT* coinPtT[2]; for (int pt = 0; pt < pts; ++pt) { diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index ac9276beec..b733ed0ea7 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -25,6 +25,9 @@ public: sk_bzero(fPt2, sizeof(fPt2)); sk_bzero(fT, sizeof(fT)); sk_bzero(fNearlySame, sizeof(fNearlySame)); +#if DEBUG_T_SECT_LOOP_COUNT + sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); +#endif reset(); fMax = 0; // require that the caller set the max } @@ -277,7 +280,16 @@ public: #endif } + enum DebugLoop { + kIterations_DebugLoop, + kCoinCheck_DebugLoop, + kComputePerp_DebugLoop, + }; + + void debugBumpLoopCount(DebugLoop ); int debugCoincidentUsed() const; + int debugLoopCount(DebugLoop ) const; + void debugResetLoopCount(); void dump() const; // implemented for testing only private: @@ -299,6 +311,9 @@ private: #ifdef SK_DEBUG int fDepth; #endif +#if DEBUG_T_SECT_LOOP_COUNT + int fDebugLoopCount[3]; +#endif }; #endif diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index bb10e53b8b..655df45b15 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -222,53 +222,6 @@ bool SkOpAngle::checkCrossesZero() const { return crossesZero; } -// loop looking for a pair of angle parts that are too close to be sorted -/* This is called after other more simple intersection and angle sorting tests have been exhausted. - This should be rarely called -- the test below is thorough and time consuming. - This checks the distance between start points; the distance between -*/ -void SkOpAngle::checkNearCoincidence() { - SkOpAngle* test = this; - do { - SkOpSegment* testSegment = test->segment(); - double testStartT = test->start()->t(); - SkDPoint testStartPt = testSegment->dPtAtT(testStartT); - double testEndT = test->end()->t(); - SkDPoint testEndPt = testSegment->dPtAtT(testEndT); - double testLenSq = testStartPt.distanceSquared(testEndPt); - if (0) { - SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID()); - } - double testMidT = (testStartT + testEndT) / 2; - SkOpAngle* next = test; - while ((next = next->fNext) != this) { - SkOpSegment* nextSegment = next->segment(); - double testMidDistSq = testSegment->distSq(testMidT, next); - double testEndDistSq = testSegment->distSq(testEndT, next); - double nextStartT = next->start()->t(); - SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT); - double distSq = testStartPt.distanceSquared(nextStartPt); - double nextEndT = next->end()->t(); - double nextMidT = (nextStartT + nextEndT) / 2; - double nextMidDistSq = nextSegment->distSq(nextMidT, test); - double nextEndDistSq = nextSegment->distSq(nextEndT, test); - if (0) { - SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq, - testSegment->debugID(), nextSegment->debugID()); - SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq); - SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq); - SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq); - SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq); - SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT); - double nextLenSq = nextStartPt.distanceSquared(nextEndPt); - SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq); - SkDebugf("\n"); - } - } - test = test->fNext; - } while (test->fNext != this); -} - bool SkOpAngle::checkParallel(SkOpAngle* rh) { SkDVector scratch[2]; const SkDVector* sweep, * tweep; diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h index dba3f3ffac..4b209de32d 100644 --- a/src/pathops/SkOpAngle.h +++ b/src/pathops/SkOpAngle.h @@ -30,7 +30,6 @@ struct SkOpAngle { bool after(SkOpAngle* test); int allOnOneSide(const SkOpAngle* test); bool checkCrossesZero() const; - void checkNearCoincidence(); bool checkParallel(SkOpAngle* ); bool computeSector(); int convexHullOverlaps(const SkOpAngle* ) const; @@ -47,6 +46,7 @@ struct SkOpAngle { #endif #if DEBUG_ANGLE + void debugCheckNearCoincidence() const; SkString debugPart() const; #endif const SkOpPtT* debugPtT(int id) const; diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp index fb2de5ac60..a22cfc6deb 100755 --- a/src/pathops/SkOpCoincidence.cpp +++ b/src/pathops/SkOpCoincidence.cpp @@ -51,6 +51,8 @@ void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* o coinRec->fOppPtTStart = oppPtTStart; coinRec->fOppPtTEnd = oppPtTEnd; coinRec->fFlipped = flipped; + SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID()); + this->fHead = coinRec; } @@ -65,7 +67,7 @@ static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, d *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; } -void SkOpCoincidence::addExpanded(SkChunkAlloc* allocator +bool SkOpCoincidence::addExpanded(SkChunkAlloc* allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) { #if DEBUG_VALIDATE globalState->setPhase(SkOpGlobalState::kIntersecting); @@ -92,7 +94,9 @@ void SkOpCoincidence::addExpanded(SkChunkAlloc* allocator double startPart = (test->t() - startPtT->fT) / startRange; double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT; double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; - SkASSERT(startPart != oStartPart); + if (startPart == oStartPart) { + return false; + } SkOpPtT* newPt; if (startPart < oStartPart) { double newT = oStartPtT->fT + oStartRange * startPart; @@ -112,7 +116,7 @@ void SkOpCoincidence::addExpanded(SkChunkAlloc* allocator if (test != end) { test = test->upCast()->next(); } - if (oStart != oEnd) { + if (oTest != oEnd) { oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next(); } } @@ -120,9 +124,10 @@ void SkOpCoincidence::addExpanded(SkChunkAlloc* allocator #if DEBUG_VALIDATE globalState->setPhase(SkOpGlobalState::kWalking); #endif + return true; } -void SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, +bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, SkOpPtT* over1e, SkChunkAlloc* allocator) { SkCoincidentSpans* check = this->fTop; do { @@ -132,7 +137,7 @@ void SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over || !fDebugState->debugRunFail()); SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span() || !fDebugState->debugRunFail()); - return; + return false; } if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span() && check->fOppPtTStart->span() == over1s->span()) { @@ -140,13 +145,14 @@ void SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over || !fDebugState->debugRunFail()); SkASSERT(check->fOppPtTEnd->span() == over1e->span() || !fDebugState->debugRunFail()); - return; + return false; } } while ((check = check->fNext)); this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator); #if 0 // FIXME: up to four flavors could be added -- do we need only one? #endif + return true; } bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, @@ -184,7 +190,7 @@ bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); // SkASSERT(tweenCount == 0 || tweenCount == 4); if (tweenCount) { - return true; + return false; } } while ((check = check->fNext)); if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { @@ -196,9 +202,7 @@ bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, } SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator); SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator); - if (cs == ce) { - return false; - } + SkASSERT(cs != ce); SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); SkASSERT(os != oe); @@ -215,13 +219,13 @@ bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { if (!outer) { return true; } - bool result; + bool added = false; fTop = outer; fHead = nullptr; do { // addifmissing can modify the list that this is walking - // maybe save head so that walker can iterate over old data unperturbed - // and addifmissing can add to head freely then add saved head in the end + // save head so that walker can iterate over old data unperturbed + // addifmissing adds to head freely then add saved head in the end const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); SkASSERT(outerCoin == outer->fCoinPtTEnd->segment()); const SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); @@ -236,43 +240,31 @@ bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { if (outerCoin == innerCoin && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { - if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, + added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, outer->fOppPtTStart, outer->fOppPtTEnd, - inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { - result = false; - goto returnResult; - } + inner->fOppPtTStart, inner->fOppPtTEnd, allocator); } else if (outerCoin == innerOpp && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { - if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, + added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, outer->fOppPtTStart, outer->fOppPtTEnd, - inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { - result = false; - goto returnResult; - } + inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator); } else if (outerOpp == innerCoin && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { - if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, + added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, outer->fCoinPtTStart, outer->fCoinPtTEnd, - inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { - result = false; - goto returnResult; - } + inner->fOppPtTStart, inner->fOppPtTEnd, allocator); } else if (outerOpp == innerOpp && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { - if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, + added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, outer->fCoinPtTStart, outer->fCoinPtTEnd, - inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { - result = false; - goto returnResult; - } + inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator); } else if (outerCoin != innerCoin) { // check to see if outer span overlaps the inner span // look for inner segment in pt-t list @@ -283,21 +275,24 @@ bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { if (testS && testS->fT >= inner->fCoinPtTStart->fT && testE && testE->fT <= inner->fCoinPtTEnd->fT && this->testForCoincidence(outer, testS, testE)) { - this->addIfMissing(outer, testS, testE, allocator); + added |= this->addIfMissing(outer, testS, testE, allocator); } else { testS = inner->fCoinPtTStart->contains(outerCoin); testE = inner->fCoinPtTEnd->contains(outerCoin); if (testS && testS->fT >= outer->fCoinPtTStart->fT && testE && testE->fT <= outer->fCoinPtTEnd->fT && this->testForCoincidence(inner, testS, testE)) { - this->addIfMissing(inner, testS, testE, allocator); + added |= this->addIfMissing(inner, testS, testE, allocator); } } } +#if 0 && DEBUG_COINCIDENCE + SkString miss; + miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID()); + DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str()); +#endif } } while ((outer = outer->fNext)); - result = true; -returnResult: SkCoincidentSpans** headPtr = &fHead; while (*headPtr) { SkCoincidentSpans** headNext = &(*headPtr)->fNext; @@ -307,7 +302,7 @@ returnResult: headPtr = headNext; } *headPtr = fTop; - return result; + return added; } void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2, @@ -340,9 +335,9 @@ void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegm this->add(s1, e1, s2, e2, allocator); } -bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, - SkOpPtT* oppPtTEnd, bool flipped) { - SkCoincidentSpans* coin = fHead; +bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, + const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const { + const SkCoincidentSpans* coin = fHead; if (!coin) { return false; } @@ -454,6 +449,9 @@ bool SkOpCoincidence::apply() { if (next == end) { break; } + if (!next->upCastable()) { + return false; + } start = next->upCast(); // if the opposite ran out too soon, just reuse the last span if (!oNext || !oNext->upCastable()) { @@ -662,8 +660,8 @@ bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, return *overS < *overE; } -bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, SkOpPtT* testS, - SkOpPtT* testE) const { +bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS, + const SkOpPtT* testE) const { return testS->segment()->testForCoincidence(testS, testE, testS->span(), testE->span(), outer->fCoinPtTStart->segment(), 120000); // FIXME: replace with tuned } diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h index 86c6577739..91da2e16bf 100644 --- a/src/pathops/SkOpCoincidence.h +++ b/src/pathops/SkOpCoincidence.h @@ -20,6 +20,11 @@ struct SkCoincidentSpans { SkOpPtT* fOppPtTStart; SkOpPtT* fOppPtTEnd; bool fFlipped; + SkDEBUGCODE(int fID); + + int debugID() const { + return SkDEBUGRELEASE(fID, -1); + } void dump() const; }; @@ -35,12 +40,14 @@ public: void add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator); - void addExpanded(SkChunkAlloc* allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* )); + bool addExpanded(SkChunkAlloc* allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* )); bool addMissing(SkChunkAlloc* allocator); - void addMissing(SkCoincidentSpans* check, SkChunkAlloc* allocator); bool apply(); - bool contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, - SkOpPtT* oppPtTEnd, bool flipped); + bool contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, + const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const; + + void debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* ) const; + void debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* ) const; const SkOpAngle* debugAngle(int id) const { return SkDEBUGRELEASE(fDebugState->debugAngle(id), nullptr); @@ -50,6 +57,9 @@ public: return SkDEBUGRELEASE(fDebugState->debugContour(id), nullptr); } + bool debugExpand(const char* id, SkPathOpsDebug::GlitchLog* ) const; + void debugMark(const char* id, SkPathOpsDebug::GlitchLog* ) const; + const SkOpPtT* debugPtT(int id) const { return SkDEBUGRELEASE(fDebugState->debugPtT(id), nullptr); } @@ -62,6 +72,7 @@ public: SkDEBUGCODE(fDebugState = debugState); } + void debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* ) const; void debugShowCoincidence() const; const SkOpSpanBase* debugSpan(int id) const { @@ -84,7 +95,7 @@ public: void mark(); private: - void addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, SkOpPtT* over1e, + bool addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, SkOpPtT* over1e, SkChunkAlloc* ); bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, const SkOpPtT* over2s, const SkOpPtT* over2e, @@ -94,11 +105,19 @@ private: SkChunkAlloc* ); void addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2, SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* ); + bool debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s, + const SkOpPtT* over1e) const; + bool debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, + const SkOpPtT* over2s, const SkOpPtT* over2e, + double tStart, double tEnd, + SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, + SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const; bool overlap(const SkOpPtT* coinStart1, const SkOpPtT* coinEnd1, const SkOpPtT* coinStart2, const SkOpPtT* coinEnd2, double* overS, double* overE) const; - bool testForCoincidence(const SkCoincidentSpans* outer, SkOpPtT* testS, SkOpPtT* testE) const; + bool testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS, + const SkOpPtT* testE) const; SkCoincidentSpans* fHead; SkCoincidentSpans* fTop; SkDEBUGCODE_(SkOpGlobalState* fDebugState); diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index 974c4ad3c1..c6120089bd 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -132,10 +132,15 @@ public: return SkDEBUGRELEASE(this->globalState()->debugAngle(id), nullptr); } + void debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* ) const; + SkOpContour* debugContour(int id) { return SkDEBUGRELEASE(this->globalState()->debugContour(id), nullptr); } + void debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, + const SkOpCoincidence* coincidence) const; + const SkOpPtT* debugPtT(int id) const { return SkDEBUGRELEASE(this->globalState()->debugPtT(id), nullptr); } @@ -181,10 +186,10 @@ public: void dumpContoursSpan(int segmentID) const; void dumpContoursSpans() const; void dumpPt(int ) const; - void dumpPts() const; - void dumpPtsX() const; + void dumpPts(const char* prefix = "seg") const; + void dumpPtsX(const char* prefix) const; void dumpSegment(int ) const; - void dumpSegments(SkPathOp op) const; + void dumpSegments(const char* prefix = "seg", SkPathOp op = (SkPathOp) -1) const; void dumpSpan(int ) const; void dumpSpans() const; @@ -245,7 +250,9 @@ public: bool result = false; do { if (fState->angleCoincidence()) { - segment->checkAngleCoin(coincidences, allocator); +#if DEBUG_ANGLE + segment->debugCheckAngleCoin(); +#endif } else if (segment->missingCoincidence(coincidences, allocator)) { result = true; // FIXME: trying again loops forever in issue3651_6 diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 5ee775c3c6..76032aaf0c 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -433,25 +433,6 @@ void SkOpSegment::calcAngles(SkChunkAlloc* allocator) { } } -void SkOpSegment::checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) { - SkOpSpanBase* base = &fHead; - SkOpSpan* span; - do { - SkOpAngle* angle = base->fromAngle(); - if (angle && angle->fCheckCoincidence) { - angle->checkNearCoincidence(); - } - if (base->final()) { - break; - } - span = base->upCast(); - angle = span->toAngle(); - if (angle && angle->fCheckCoincidence) { - angle->checkNearCoincidence(); - } - } while ((base = span->next())); -} - bool SkOpSegment::collapsed() const { return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt(); } @@ -593,14 +574,14 @@ void SkOpSegment::detach(const SkOpSpan* span) { SkASSERT(fCount >= fDoneCount); } -double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) { +double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { SkDPoint testPt = this->dPtAtT(t); SkDLine testPerp = {{ testPt, testPt }}; SkDVector slope = this->dSlopeAtT(t); testPerp[1].fX += slope.fY; testPerp[1].fY -= slope.fX; SkIntersections i; - SkOpSegment* oppSegment = oppAngle->segment(); + const SkOpSegment* oppSegment = oppAngle->segment(); (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); double closestDistSq = SK_ScalarInfinity; for (int index = 0; index < i.used(); ++index) { @@ -1220,9 +1201,9 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc continue; } SkOpSegment* opp = ptT->span()->segment(); - if (opp->verb() == SkPath::kLine_Verb) { - continue; - } +// if (opp->verb() == SkPath::kLine_Verb) { +// continue; +// } if (opp->done()) { continue; } @@ -1239,6 +1220,9 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc if (span && span->containsCoincidence(opp)) { continue; } + if (spanBase->segment() == opp) { + continue; + } if (spanBase->containsCoinEnd(opp)) { continue; } @@ -1264,6 +1248,9 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc if (!priorOpp) { continue; } + if (priorPtT == ptT) { + continue; + } SkOpPtT* oppStart = prior->ptT(); SkOpPtT* oppEnd = spanBase->ptT(); bool swapped = priorPtT->fT > ptT->fT; @@ -1272,11 +1259,19 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc SkTSwap(oppStart, oppEnd); } bool flipped = oppStart->fT > oppEnd->fT; - bool coincident; + bool coincident = false; if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) { goto swapBack; } - coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000); + if (opp->verb() == SkPath::kLine_Verb) { + coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) || + SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) && + (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) || + SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt)); + } + if (!coincident) { + coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000); + } if (coincident) { // mark coincidence if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd) diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 6a8ab851ac..98e140cba3 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -115,8 +115,6 @@ public: } void calcAngles(SkChunkAlloc*); - void checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator); - void checkNearCoincidence(SkOpAngle* ); bool collapsed() const; static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); @@ -133,14 +131,35 @@ public: } void debugAddAngle(double startT, double endT, SkChunkAlloc*); + void debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* glitches, + const SkOpPtT& endPtT, const SkPoint& oldPt, + const SkOpContourHead* ) const; + + void debugAddAlignIntersections(const char* id, SkPathOpsDebug::GlitchLog* glitches, + SkOpContourHead* contourList) const { + this->debugAddAlignIntersection(id, glitches, *fHead.ptT(), fOriginal[0], contourList); + this->debugAddAlignIntersection(id, glitches, *fTail.ptT(), fOriginal[1], contourList); + } + + bool debugAddMissing(double t, const SkOpSegment* opp) const; + void debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const; const SkOpAngle* debugAngle(int id) const; +#if DEBUG_ANGLE + void debugCheckAngleCoin() const; +#endif + void debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* ) const; SkOpContour* debugContour(int id); + void debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const; int debugID() const { return SkDEBUGRELEASE(fID, -1); } SkOpAngle* debugLastAngle(); + void debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* glitches, + const SkOpCoincidence* coincidences) const; + void debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const; + void debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const; const SkOpPtT* debugPtT(int id) const; void debugReset(); const SkOpSegment* debugSegment(int id) const; @@ -156,7 +175,7 @@ public: const SkOpSpanBase* debugSpan(int id) const; void debugValidate() const; void detach(const SkOpSpan* ); - double distSq(double t, SkOpAngle* opp); + double distSq(double t, const SkOpAngle* opp) const; bool done() const { SkASSERT(fDoneCount <= fCount); @@ -179,8 +198,8 @@ public: void dumpAll() const; void dumpAngles() const; void dumpCoin() const; - void dumpPts() const; - void dumpPtsInner() const; + void dumpPts(const char* prefix = "seg") const; + void dumpPtsInner(const char* prefix = "seg") const; void findCollapsed(); SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index a2115df4d7..dab0dfaf03 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -58,13 +58,14 @@ public: } const SkOpAngle* debugAngle(int id) const; + bool debugContains(const SkOpPtT* ) const; + const SkOpPtT* debugContains(const SkOpSegment* check) const; SkOpContour* debugContour(int id); int debugLoopLimit(bool report) const; bool debugMatchID(int id) const; const SkOpPtT* debugPtT(int id) const; const SkOpSegment* debugSegment(int id) const; const SkOpSpanBase* debugSpan(int id) const; - SkOpGlobalState* globalState() const; void debugValidate() const; bool deleted() const { @@ -82,6 +83,7 @@ public: void dumpBase() const; SkOpPtT* find(SkOpSegment* ); + SkOpGlobalState* globalState() const; void init(SkOpSpanBase* , double t, const SkPoint& , bool dup); void insert(SkOpPtT* span) { @@ -204,12 +206,16 @@ public: return SkDEBUGRELEASE(fID, -1); } + bool debugAlignedEnd(double t, const SkPoint& pt) const; + bool debugAlignedInner() const; const SkOpAngle* debugAngle(int id) const; bool debugCoinEndLoopCheck() const; + bool debugContains(const SkOpSegment* ) const; SkOpContour* debugContour(int id); const SkOpPtT* debugPtT(int id) const; const SkOpSegment* debugSegment(int id) const; const SkOpSpanBase* debugSpan(int id) const; + const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const; SkOpGlobalState* globalState() const; void debugValidate() const; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 58bcacd2fd..0060db2f30 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -450,42 +450,70 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc SkChunkAlloc* allocator) { SkOpGlobalState* globalState = contourList->globalState(); // combine t values when multiple intersections occur on some segments but not others + DEBUG_COINCIDENCE_HEALTH(contourList, "start"); moveMultiples(contourList); + DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples"); findCollapsed(contourList); + DEBUG_COINCIDENCE_HEALTH(contourList, "findCollapsed"); // move t values and points together to eliminate small/tiny gaps moveNearby(contourList); + DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby"); align(contourList); // give all span members common values + DEBUG_COINCIDENCE_HEALTH(contourList, "align"); coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted + DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned"); #if DEBUG_VALIDATE globalState->setPhase(SkOpGlobalState::kIntersecting); #endif // look for intersections on line segments formed by moving end points addAlignIntersections(contourList, allocator); - coincidence->addMissing(allocator); + DEBUG_COINCIDENCE_HEALTH(contourList, "addAlignIntersections"); + if (coincidence->addMissing(allocator)) { + DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing"); + moveNearby(contourList); + DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2"); + align(contourList); // give all span members common values + DEBUG_COINCIDENCE_HEALTH(contourList, "align2"); + coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted + DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned2"); + } #if DEBUG_VALIDATE globalState->setPhase(SkOpGlobalState::kWalking); #endif // check to see if, loosely, coincident ranges may be expanded if (coincidence->expand()) { - coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState)); + DEBUG_COINCIDENCE_HEALTH(contourList, "expand1"); + if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) { + return false; + } } + DEBUG_COINCIDENCE_HEALTH(contourList, "expand2"); // the expanded ranges may not align -- add the missing spans coincidence->mark(); // mark spans of coincident segments as coincident + DEBUG_COINCIDENCE_HEALTH(contourList, "mark1"); // look for coincidence missed earlier if (missingCoincidence(contourList, coincidence, allocator)) { + DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1"); (void) coincidence->expand(); - coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState)); + DEBUG_COINCIDENCE_HEALTH(contourList, "expand3"); + if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) { + return false; + } + DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2"); coincidence->mark(); } + DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2"); SkOpCoincidence overlaps; do { SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps; if (!pairs->apply()) { // adjust the winding value to account for coincident edges return false; } + DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply"); // For each coincident pair that overlaps another, when the receivers (the 1st of the pair) // are different, construct a new pair to resolve their mutual span pairs->findOverlaps(&overlaps, allocator); + DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps"); } while (!overlaps.isEmpty()); calcAngles(contourList, allocator); sortAngles(contourList); diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 141041ad36..a037d00571 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -6,10 +6,14 @@ */ #include "SkMutex.h" +#include "SkOpCoincidence.h" +#include "SkOpContour.h" #include "SkPath.h" #include "SkPathOpsDebug.h" #include "SkString.h" +struct SkCoincidentSpans; + #if DEBUG_VALIDATE extern bool FLAGS_runFail; #endif @@ -27,10 +31,8 @@ const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"}; -#if defined(SK_DEBUG) || !FORCE_RELEASE int SkPathOpsDebug::gContourID = 0; int SkPathOpsDebug::gSegmentID = 0; -#endif bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray, const SkOpSpanBase* span) { @@ -42,7 +44,152 @@ bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray, } return false; } +#endif + +#if DEBUG_COINCIDENCE +enum GlitchType { + kAddCorruptCoin_Glitch, + kAddExpandedCoin_Glitch, + kAddMissingCoin_Glitch, + kCollapsedCoin_Glitch, + kCollapsedDone_Glitch, + kCollapsedOppValue_Glitch, + kCollapsedSpan_Glitch, + kCollapsedWindValue_Glitch, + kDeletedCoin_Glitch, + kExpandCoin_Glitch, + kMarkCoinEnd_Glitch, + kMarkCoinInsert_Glitch, + kMissingCoin_Glitch, + kMissingDone_Glitch, + kMissingIntersection_Glitch, + kMoveMultiple_Glitch, + kUnaligned_Glitch, + kUnalignedHead_Glitch, + kUnalignedTail_Glitch, + kUndetachedSpan_Glitch, + kUnmergedSpan_Glitch, +}; + +static const int kGlitchType_Count = kUnmergedSpan_Glitch + 1; + +struct SpanGlitch { + const char* fStage; + const SkOpSpanBase* fBase; + const SkOpSpanBase* fSuspect; + const SkCoincidentSpans* fCoin; + const SkOpSegment* fSegment; + const SkOpPtT* fCoinSpan; + const SkOpPtT* fEndSpan; + const SkOpPtT* fOppSpan; + const SkOpPtT* fOppEndSpan; + double fT; + SkPoint fPt; + GlitchType fType; +}; + +struct SkPathOpsDebug::GlitchLog { + SpanGlitch* recordCommon(GlitchType type, const char* stage) { + SpanGlitch* glitch = fGlitches.push(); + glitch->fStage = stage; + glitch->fBase = nullptr; + glitch->fSuspect = nullptr; + glitch->fCoin = nullptr; + glitch->fSegment = nullptr; + glitch->fCoinSpan = nullptr; + glitch->fEndSpan = nullptr; + glitch->fOppSpan = nullptr; + glitch->fOppEndSpan = nullptr; + glitch->fT = SK_ScalarNaN; + glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN }; + glitch->fType = type; + return glitch; + } + + void record(GlitchType type, const char* stage, const SkOpSpanBase* base, + const SkOpSpanBase* suspect = NULL) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fBase = base; + glitch->fSuspect = suspect; + } + + void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, + const SkOpPtT* coinSpan) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fCoin = coin; + glitch->fCoinSpan = coinSpan; + } + + void record(GlitchType type, const char* stage, const SkOpSpanBase* base, + const SkOpSegment* seg, double t, SkPoint pt) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fBase = base; + glitch->fSegment = seg; + glitch->fT = t; + glitch->fPt = pt; + } + + void record(GlitchType type, const char* stage, const SkOpSpanBase* base, double t, + SkPoint pt) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fBase = base; + glitch->fT = t; + glitch->fPt = pt; + } + + void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, + const SkOpPtT* coinSpan, const SkOpPtT* endSpan) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fCoin = coin; + glitch->fCoinSpan = coinSpan; + glitch->fEndSpan = endSpan; + } + + void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin, + const SkOpSpanBase* suspect) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fSuspect = suspect; + glitch->fCoin = coin; + } + + void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE, + const SkOpPtT* oPtTS, const SkOpPtT* oPtTE) { + SpanGlitch* glitch = recordCommon(type, stage); + glitch->fCoinSpan = ptTS; + glitch->fEndSpan = ptTE; + glitch->fOppSpan = oPtTS; + glitch->fOppEndSpan = oPtTE; + } + + SkTDArray<SpanGlitch> fGlitches; +}; + +void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) { + GlitchLog glitches; + const SkOpContour* contour = contourList; + const SkOpCoincidence* coincidence = contour->globalState()->coincidence(); + do { + contour->debugCheckHealth(id, &glitches); + contour->debugMissingCoincidence(id, &glitches, coincidence); + } while ((contour = contour->next())); + coincidence->debugFixAligned(id, &glitches); + coincidence->debugAddMissing(id, &glitches); + coincidence->debugExpand(id, &glitches); + coincidence->debugAddExpanded(id, &glitches); + coincidence->debugMark(id, &glitches); + unsigned mask = 0; + for (int index = 0; index < glitches.fGlitches.count(); ++index) { + const SpanGlitch& glitch = glitches.fGlitches[index]; + mask |= 1 << glitch.fType; + } + for (int index = 0; index < kGlitchType_Count; ++index) { + SkDebugf(mask & (1 << index) ? "x" : "-"); + } + SkDebugf(" %s\n", id); +} +#endif +#if defined SK_DEBUG || !FORCE_RELEASE void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) { size_t len = strlen(str); bool num = false; @@ -132,6 +279,91 @@ void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp } #include "SkPathOpsTypes.h" +#include "SkIntersectionHelper.h" +#include "SkIntersections.h" + +#if DEBUG_T_SECT_LOOP_COUNT +void SkOpGlobalState::debugAddLoopCount(SkIntersections* i, const SkIntersectionHelper& wt, + const SkIntersectionHelper& wn) { + for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { + SkIntersections::DebugLoop looper = (SkIntersections::DebugLoop) index; + if (fDebugLoopCount[index] >= i->debugLoopCount(looper)) { + continue; + } + fDebugLoopCount[index] = i->debugLoopCount(looper); + fDebugWorstVerb[index * 2] = wt.segment()->verb(); + fDebugWorstVerb[index * 2 + 1] = wn.segment()->verb(); + sk_bzero(&fDebugWorstPts[index * 8], sizeof(SkPoint) * 8); + memcpy(&fDebugWorstPts[index * 2 * 4], wt.pts(), + (SkPathOpsVerbToPoints(wt.segment()->verb()) + 1) * sizeof(SkPoint)); + memcpy(&fDebugWorstPts[(index * 2 + 1) * 4], wn.pts(), + (SkPathOpsVerbToPoints(wn.segment()->verb()) + 1) * sizeof(SkPoint)); + fDebugWorstWeight[index * 2] = wt.weight(); + fDebugWorstWeight[index * 2 + 1] = wn.weight(); + } + i->debugResetLoopCount(); +} + +void SkOpGlobalState::debugDoYourWorst(SkOpGlobalState* local) { + for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { + if (fDebugLoopCount[index] >= local->fDebugLoopCount[index]) { + continue; + } + fDebugLoopCount[index] = local->fDebugLoopCount[index]; + fDebugWorstVerb[index * 2] = local->fDebugWorstVerb[index * 2]; + fDebugWorstVerb[index * 2 + 1] = local->fDebugWorstVerb[index * 2 + 1]; + memcpy(&fDebugWorstPts[index * 2 * 4], &local->fDebugWorstPts[index * 2 * 4], + sizeof(SkPoint) * 8); + fDebugWorstWeight[index * 2] = local->fDebugWorstWeight[index * 2]; + fDebugWorstWeight[index * 2 + 1] = local->fDebugWorstWeight[index * 2 + 1]; + } + local->debugResetLoopCounts(); +} + +static void dump_curve(SkPath::Verb verb, const SkPoint& pts, float weight) { + if (!verb) { + return; + } + const char* verbs[] = { "", "line", "quad", "conic", "cubic" }; + SkDebugf("%s: {{", verbs[verb]); + int ptCount = SkPathOpsVerbToPoints(verb); + for (int index = 0; index <= ptCount; ++index) { + SkDPoint::Dump((&pts)[index]); + if (index < ptCount - 1) { + SkDebugf(", "); + } + } + SkDebugf("}"); + if (weight != 1) { + SkDebugf(", "); + if (weight == floorf(weight)) { + SkDebugf("%.0f", weight); + } else { + SkDebugf("%1.9gf", weight); + } + } + SkDebugf("}\n"); +} + +void SkOpGlobalState::debugLoopReport() { + const char* loops[] = { "iterations", "coinChecks", "perpCalcs" }; + SkDebugf("\n"); + for (int index = 0; index < (int) SK_ARRAY_COUNT(fDebugLoopCount); ++index) { + SkDebugf("%s: %d\n", loops[index], fDebugLoopCount[index]); + dump_curve(fDebugWorstVerb[index * 2], fDebugWorstPts[index * 2 * 4], + fDebugWorstWeight[index * 2]); + dump_curve(fDebugWorstVerb[index * 2 + 1], fDebugWorstPts[(index * 2 + 1) * 4], + fDebugWorstWeight[index * 2 + 1]); + } +} + +void SkOpGlobalState::debugResetLoopCounts() { + sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); + sk_bzero(fDebugWorstVerb, sizeof(fDebugWorstVerb)); + sk_bzero(fDebugWorstPts, sizeof(fDebugWorstPts)); + sk_bzero(fDebugWorstWeight, sizeof(fDebugWorstWeight)); +} +#endif #ifdef SK_DEBUG bool SkOpGlobalState::debugRunFail() const { @@ -143,6 +375,20 @@ bool SkOpGlobalState::debugRunFail() const { } #endif +#if DEBUG_T_SECT_LOOP_COUNT +void SkIntersections::debugBumpLoopCount(DebugLoop index) { + fDebugLoopCount[index]++; +} + +int SkIntersections::debugLoopCount(DebugLoop index) const { + return fDebugLoopCount[index]; +} + +void SkIntersections::debugResetLoopCount() { + sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); +} +#endif + #include "SkPathOpsCubic.h" #include "SkPathOpsQuad.h" @@ -159,9 +405,190 @@ SkDCubic SkDQuad::debugToCubic() const { } #include "SkOpAngle.h" -#include "SkOpCoincidence.h" #include "SkOpSegment.h" +#if DEBUG_COINCIDENCE +void SkOpSegment::debugAddAlignIntersection(const char* id, SkPathOpsDebug::GlitchLog* log, + const SkOpPtT& endPtT, const SkPoint& oldPt, const SkOpContourHead* contourList) const { + const SkPoint& newPt = endPtT.fPt; + if (newPt == oldPt) { + return; + } + SkPoint line[2] = { newPt, oldPt }; + SkPathOpsBounds lineBounds; + lineBounds.setBounds(line, 2); + SkDLine aLine; + aLine.set(line); + const SkOpContour* current = contourList; + do { + if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) { + continue; + } + const SkOpSegment* segment = current->first(); + do { + if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) { + continue; + } + if (newPt == segment->fPts[0]) { + continue; + } + if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { + continue; + } + if (oldPt == segment->fPts[0]) { + continue; + } + if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { + continue; + } + if (endPtT.debugContains(segment)) { + continue; + } + SkIntersections i; + switch (segment->fVerb) { + case SkPath::kLine_Verb: { + SkDLine bLine; + bLine.set(segment->fPts); + i.intersect(bLine, aLine); + } break; + case SkPath::kQuad_Verb: { + SkDQuad bQuad; + bQuad.set(segment->fPts); + i.intersect(bQuad, aLine); + } break; + case SkPath::kConic_Verb: { + SkDConic bConic; + bConic.set(segment->fPts, segment->fWeight); + i.intersect(bConic, aLine); + } break; + case SkPath::kCubic_Verb: { + SkDCubic bCubic; + bCubic.set(segment->fPts); + i.intersect(bCubic, aLine); + } break; + default: + SkASSERT(0); + } + if (i.used()) { + SkASSERT(i.used() == 1); + SkASSERT(!zero_or_one(i[0][0])); + SkOpSpanBase* checkSpan = fHead.next(); + while (!checkSpan->final()) { + if (checkSpan->contains(segment)) { + goto nextSegment; + } + checkSpan = checkSpan->upCast()->next(); + } + log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt); + } + nextSegment: + ; + } while ((segment = segment->next())); + } while ((current = current->next())); +} + +bool SkOpSegment::debugAddMissing(double t, const SkOpSegment* opp) const { + const SkOpSpanBase* existing = nullptr; + const SkOpSpanBase* test = &fHead; + double testT; + do { + if ((testT = test->ptT()->fT) >= t) { + if (testT == t) { + existing = test; + } + break; + } + } while ((test = test->upCast()->next())); + return !existing || !existing->debugContains(opp); +} + +void SkOpSegment::debugAlign(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { + const SkOpSpanBase* span = &fHead; + if (!span->aligned()) { + if (!span->debugAlignedEnd(0, fPts[0])) { + glitches->record(kUnalignedHead_Glitch, id, span); + } + } + while ((span = span->upCast()->next())) { + if (span == &fTail) { + break; + } + if (!span->aligned()) { + glitches->record(kUnaligned_Glitch, id, span); + } + } + if (!span->aligned()) { + span->debugAlignedEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]); + } + if (this->collapsed()) { + const SkOpSpan* span = &fHead; + do { + if (span->windValue()) { + glitches->record(kCollapsedWindValue_Glitch, id, span); + } + if (span->oppValue()) { + glitches->record(kCollapsedOppValue_Glitch, id, span); + } + if (!span->done()) { + glitches->record(kCollapsedDone_Glitch, id, span); + } + } while ((span = span->next()->upCastable())); + } +} +#endif + +#if DEBUG_ANGLE +void SkOpSegment::debugCheckAngleCoin() const { + const SkOpSpanBase* base = &fHead; + const SkOpSpan* span; + do { + const SkOpAngle* angle = base->fromAngle(); + if (angle && angle->fCheckCoincidence) { + angle->debugCheckNearCoincidence(); + } + if (base->final()) { + break; + } + span = base->upCast(); + angle = span->toAngle(); + if (angle && angle->fCheckCoincidence) { + angle->debugCheckNearCoincidence(); + } + } while ((base = span->next())); +} +#endif + +#if DEBUG_COINCIDENCE +// this mimics the order of the checks in handle coincidence +void SkOpSegment::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { + debugMoveMultiples(id, glitches); + debugFindCollapsed(id, glitches); + debugMoveNearby(id, glitches); + debugAlign(id, glitches); + debugAddAlignIntersections(id, glitches, this->globalState()->contourHead()); + +} + +void SkOpSegment::debugFindCollapsed(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { + if (fHead.contains(&fTail)) { + const SkOpSpan* span = this->head(); + bool missingDone = false; + do { + missingDone |= !span->done(); + } while ((span = span->next()->upCastable())); + if (missingDone) { + glitches->record(kMissingDone_Glitch, id, &fHead); + } + if (!fHead.debugAlignedEnd(0, fHead.pt())) { + glitches->record(kUnalignedHead_Glitch, id, &fHead); + } + if (!fTail.aligned()) { + glitches->record(kUnalignedTail_Glitch, id, &fTail); + } + } +} +#endif + SkOpAngle* SkOpSegment::debugLastAngle() { SkOpAngle* result = nullptr; SkOpSpan* span = this->head(); @@ -175,6 +602,241 @@ SkOpAngle* SkOpSegment::debugLastAngle() { return result; } +#if DEBUG_COINCIDENCE +void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, + const SkOpCoincidence* coincidences) const { + if (this->verb() != SkPath::kLine_Verb) { + return; + } + if (this->done()) { + return; + } + const SkOpSpan* prior = nullptr; + const SkOpSpanBase* spanBase = &fHead; + do { + const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; + SkASSERT(ptT->span() == spanBase); + while ((ptT = ptT->next()) != spanStopPtT) { + if (ptT->deleted()) { + continue; + } + SkOpSegment* opp = ptT->span()->segment(); +// if (opp->verb() == SkPath::kLine_Verb) { +// continue; +// } + if (opp->done()) { + continue; + } + // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence + if (!opp->visited()) { + continue; + } + if (spanBase == &fHead) { + continue; + } + const SkOpSpan* span = spanBase->upCastable(); + // FIXME?: this assumes that if the opposite segment is coincident then no more + // coincidence needs to be detected. This may not be true. + if (span && span->segment() != opp && span->containsCoincidence(opp)) { + continue; + } + if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) { + continue; + } + const SkOpPtT* priorPtT = nullptr, * priorStopPtT; + // find prior span containing opp segment + const SkOpSegment* priorOpp = nullptr; + const SkOpSpan* priorTest = spanBase->prev(); + while (!priorOpp && priorTest) { + priorStopPtT = priorPtT = priorTest->ptT(); + while ((priorPtT = priorPtT->next()) != priorStopPtT) { + if (priorPtT->deleted()) { + continue; + } + SkOpSegment* segment = priorPtT->span()->segment(); + if (segment == opp) { + prior = priorTest; + priorOpp = opp; + break; + } + } + priorTest = priorTest->prev(); + } + if (!priorOpp) { + continue; + } + const SkOpPtT* oppStart = prior->ptT(); + const SkOpPtT* oppEnd = spanBase->ptT(); + bool swapped = priorPtT->fT > ptT->fT; + if (swapped) { + SkTSwap(priorPtT, ptT); + SkTSwap(oppStart, oppEnd); + } + bool flipped = oppStart->fT > oppEnd->fT; + bool coincident = false; + if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) { + goto swapBack; + } + if (opp->verb() == SkPath::kLine_Verb) { + coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) || + SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) && + (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) || + SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt)); + } + if (!coincident) { + coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000); + } + if (coincident) { + log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd); + } + swapBack: + if (swapped) { + SkTSwap(priorPtT, ptT); + } + } + } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); +} + +void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { + const SkOpSpanBase* test = &fHead; + do { + int addCount = test->spanAddsCount(); + SkASSERT(addCount >= 1); + if (addCount == 1) { + continue; + } + const SkOpPtT* startPtT = test->ptT(); + const SkOpPtT* testPtT = startPtT; + do { // iterate through all spans associated with start + const SkOpSpanBase* oppSpan = testPtT->span(); + if (oppSpan->spanAddsCount() == addCount) { + continue; + } + if (oppSpan->deleted()) { + continue; + } + const SkOpSegment* oppSegment = oppSpan->segment(); + if (oppSegment == this) { + continue; + } + // find range of spans to consider merging + const SkOpSpanBase* oppPrev = oppSpan; + const SkOpSpanBase* oppFirst = oppSpan; + while ((oppPrev = oppPrev->prev())) { + if (!roughly_equal(oppPrev->t(), oppSpan->t())) { + break; + } + if (oppPrev->spanAddsCount() == addCount) { + continue; + } + if (oppPrev->deleted()) { + continue; + } + oppFirst = oppPrev; + } + const SkOpSpanBase* oppNext = oppSpan; + const SkOpSpanBase* oppLast = oppSpan; + while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { + if (!roughly_equal(oppNext->t(), oppSpan->t())) { + break; + } + if (oppNext->spanAddsCount() == addCount) { + continue; + } + if (oppNext->deleted()) { + continue; + } + oppLast = oppNext; + } + if (oppFirst == oppLast) { + continue; + } + const SkOpSpanBase* oppTest = oppFirst; + do { + if (oppTest == oppSpan) { + continue; + } + // check to see if the candidate meets specific criteria: + // it contains spans of segments in test's loop but not including 'this' + const SkOpPtT* oppStartPtT = oppTest->ptT(); + const SkOpPtT* oppPtT = oppStartPtT; + while ((oppPtT = oppPtT->next()) != oppStartPtT) { + const SkOpSegment* oppPtTSegment = oppPtT->segment(); + if (oppPtTSegment == this) { + goto tryNextSpan; + } + const SkOpPtT* matchPtT = startPtT; + do { + if (matchPtT->segment() == oppPtTSegment) { + goto foundMatch; + } + } while ((matchPtT = matchPtT->next()) != startPtT); + goto tryNextSpan; + foundMatch: // merge oppTest and oppSpan + if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) { + SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse + SkASSERT(oppSpan != &oppSegment->fTail); + glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan); + } else { + glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest); + } + goto checkNextSpan; + } + tryNextSpan: + ; + } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); + } while ((testPtT = testPtT->next()) != startPtT); +checkNextSpan: + ; + } while ((test = test->final() ? nullptr : test->upCast()->next())); +} + +void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const { + const SkOpSpanBase* spanS = &fHead; + do { + const SkOpSpanBase* test = spanS->upCast()->next(); + const SkOpSpanBase* next; + if (spanS->contains(test)) { + if (!test->final()) { + glitches->record(kUndetachedSpan_Glitch, id, test, spanS); + } else if (spanS != &fHead) { + glitches->record(kUndetachedSpan_Glitch, id, spanS, test); + } + } + do { // iterate through all spans associated with start + const SkOpPtT* startBase = spanS->ptT(); + next = test->final() ? nullptr : test->upCast()->next(); + do { + const SkOpPtT* testBase = test->ptT(); + do { + if (startBase == testBase) { + goto checkNextSpan; + } + if (testBase->duplicate()) { + continue; + } + if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) { + if (test == &this->fTail) { + if (spanS == &fHead) { + glitches->record(kCollapsedSpan_Glitch, id, spanS); + } else { + glitches->record(kUnmergedSpan_Glitch, id, &this->fTail, spanS); + } + } else { + glitches->record(kUnmergedSpan_Glitch, id, spanS, test); + goto checkNextSpan; + } + } + } while ((testBase = testBase->next()) != test->ptT()); + } while ((startBase = startBase->next()) != spanS->ptT()); + checkNextSpan: + ; + } while ((test = next)); + spanS = spanS->upCast()->next(); + } while (!spanS->final()); +} +#endif + void SkOpSegment::debugReset() { this->init(this->fPts, this->fWeight, this->contour(), this->verb()); } @@ -289,6 +951,51 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int #endif +// loop looking for a pair of angle parts that are too close to be sorted +/* This is called after other more simple intersection and angle sorting tests have been exhausted. + This should be rarely called -- the test below is thorough and time consuming. + This checks the distance between start points; the distance between +*/ +#if DEBUG_ANGLE +void SkOpAngle::debugCheckNearCoincidence() const { + const SkOpAngle* test = this; + do { + const SkOpSegment* testSegment = test->segment(); + double testStartT = test->start()->t(); + SkDPoint testStartPt = testSegment->dPtAtT(testStartT); + double testEndT = test->end()->t(); + SkDPoint testEndPt = testSegment->dPtAtT(testEndT); + double testLenSq = testStartPt.distanceSquared(testEndPt); + SkDebugf("%s testLenSq=%1.9g id=%d\n", __FUNCTION__, testLenSq, testSegment->debugID()); + double testMidT = (testStartT + testEndT) / 2; + const SkOpAngle* next = test; + while ((next = next->fNext) != this) { + SkOpSegment* nextSegment = next->segment(); + double testMidDistSq = testSegment->distSq(testMidT, next); + double testEndDistSq = testSegment->distSq(testEndT, next); + double nextStartT = next->start()->t(); + SkDPoint nextStartPt = nextSegment->dPtAtT(nextStartT); + double distSq = testStartPt.distanceSquared(nextStartPt); + double nextEndT = next->end()->t(); + double nextMidT = (nextStartT + nextEndT) / 2; + double nextMidDistSq = nextSegment->distSq(nextMidT, test); + double nextEndDistSq = nextSegment->distSq(nextEndT, test); + SkDebugf("%s distSq=%1.9g testId=%d nextId=%d\n", __FUNCTION__, distSq, + testSegment->debugID(), nextSegment->debugID()); + SkDebugf("%s testMidDistSq=%1.9g\n", __FUNCTION__, testMidDistSq); + SkDebugf("%s testEndDistSq=%1.9g\n", __FUNCTION__, testEndDistSq); + SkDebugf("%s nextMidDistSq=%1.9g\n", __FUNCTION__, nextMidDistSq); + SkDebugf("%s nextEndDistSq=%1.9g\n", __FUNCTION__, nextEndDistSq); + SkDPoint nextEndPt = nextSegment->dPtAtT(nextEndT); + double nextLenSq = nextStartPt.distanceSquared(nextEndPt); + SkDebugf("%s nextLenSq=%1.9g\n", __FUNCTION__, nextLenSq); + SkDebugf("\n"); + } + test = test->fNext; + } while (test->fNext != this); +} +#endif + #if DEBUG_ANGLE SkString SkOpAngle::debugPart() const { SkString result; @@ -397,6 +1104,337 @@ void SkOpAngle::debugValidateNext() const { #endif } + +#if DEBUG_COINCIDENCE +void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* log) const { + // for each coincident pair, match the spans + // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span + const SkCoincidentSpans* coin = this->fHead; + if (!coin) { + coin = this->fTop; + } + SkASSERT(coin); + do { + const SkOpPtT* startPtT = coin->fCoinPtTStart; + const SkOpPtT* oStartPtT = coin->fOppPtTStart; + SkASSERT(startPtT->contains(oStartPtT)); + SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd)); + const SkOpSpanBase* start = startPtT->span(); + const SkOpSpanBase* oStart = oStartPtT->span(); + const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); + const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); + const SkOpSpanBase* test = start->upCast()->next(); + const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next(); + while (test != end || oTest != oEnd) { + bool bumpTest = true; + bool bumpOTest = true; + if (!test->ptT()->contains(oTest->ptT())) { + // use t ranges to guess which one is missing + double startRange = coin->fCoinPtTEnd->fT - startPtT->fT; + double startPart = (test->t() - startPtT->fT) / startRange; + double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT; + double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; + if (startPart == oStartPart) { + // data is corrupt + log->record(kAddCorruptCoin_Glitch, id, start, oStart); + break; + } + if (startPart < oStartPart) { + double newT = oStartPtT->fT + oStartRange * startPart; + log->record(kAddExpandedCoin_Glitch, id, oStart, newT, test->pt()); + bumpOTest = false; + } else { + double newT = startPtT->fT + startRange * oStartPart; + log->record(kAddExpandedCoin_Glitch, id, start, newT, oTest->pt()); + bumpTest = false; + } + } + if (bumpTest && test != end) { + test = test->upCast()->next(); + } + if (bumpOTest && oTest != oEnd) { + oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next(); + } + } + } while ((coin = coin->fNext)); +} + +static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd, + const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) { + double denom = overE->fT - overS->fT; + double start = 0 < denom ? tStart : tEnd; + double end = 0 < denom ? tEnd : tStart; + double sRatio = (start - overS->fT) / denom; + double eRatio = (end - overS->fT) / denom; + *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; + *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; +} + +bool SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s, + const SkOpPtT* over1e) const { + const SkCoincidentSpans* check = this->fTop; + while (check) { + if (check->fCoinPtTStart->span() == over1s->span() + && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) { + SkASSERT(check->fCoinPtTEnd->span() == over1e->span() + || !fDebugState->debugRunFail()); + SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span() + || !fDebugState->debugRunFail()); + return false; + } + if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span() + && check->fOppPtTStart->span() == over1s->span()) { + SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span() + || !fDebugState->debugRunFail()); + SkASSERT(check->fOppPtTEnd->span() == over1e->span() + || !fDebugState->debugRunFail()); + return false; + } + check = check->fNext; + } + return true; +} + +bool SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, + const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, + SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, + SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { + double coinTs, coinTe, oppTs, oppTe; + t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); + t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); + const SkOpSegment* coinSeg = coinPtTStart->segment(); + const SkOpSegment* oppSeg = oppPtTStart->segment(); + SkASSERT(coinSeg != oppSeg); + const SkCoincidentSpans* check = this->fTop; + ; + while (check) { + const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); + const SkOpSegment* checkOppSeg; + if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { + goto next; + } + checkOppSeg = check->fOppPtTStart->segment(); + if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { + goto next; + } + { + int cTs = coinTs; + int cTe = coinTe; + int oTs = oppTs; + int oTe = oppTe; + if (checkCoinSeg != coinSeg) { + SkASSERT(checkOppSeg != oppSeg); + SkTSwap(cTs, oTs); + SkTSwap(cTe, oTe); + } + int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT) + + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT) + + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT) + + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); + // SkASSERT(tweenCount == 0 || tweenCount == 4); + if (tweenCount) { + return true; + } + } +next: + check = check->fNext; + } + if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { + SkTSwap(oppTs, oppTe); + } + if (coinTs > coinTe) { + SkTSwap(coinTs, coinTe); + SkTSwap(oppTs, oppTe); + } + bool cs = coinSeg->debugAddMissing(coinTs, oppSeg); + bool ce = coinSeg->debugAddMissing(coinTe, oppSeg); + if (cs == ce) { + return false; + } + return true; +} + +void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const { + const SkCoincidentSpans* outer = fHead; + if (!outer) { + return; + } + do { + // addifmissing can modify the list that this is walking + // save head so that walker can iterate over old data unperturbed + // addifmissing adds to head freely then add saved head in the end + const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); + SkASSERT(outerCoin == outer->fCoinPtTEnd->segment()); + const SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); + SkASSERT(outerOpp == outer->fOppPtTEnd->segment()); + const SkCoincidentSpans* inner = outer; + while ((inner = inner->fNext)) { + double overS, overE; + const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); + SkASSERT(innerCoin == inner->fCoinPtTEnd->segment()); + const SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); + SkASSERT(innerOpp == inner->fOppPtTEnd->segment()); + if (outerCoin == innerCoin + && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, + inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { + if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, + inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, + outer->fOppPtTStart, outer->fOppPtTEnd, + inner->fOppPtTStart, inner->fOppPtTEnd)) { + log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart); + } + } else if (outerCoin == innerOpp + && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, + inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { + if (this->debugAddIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, + inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, + outer->fOppPtTStart, outer->fOppPtTEnd, + inner->fCoinPtTStart, inner->fCoinPtTEnd)) { + log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart); + } + } else if (outerOpp == innerCoin + && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, + inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { + if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, + inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, + outer->fCoinPtTStart, outer->fCoinPtTEnd, + inner->fOppPtTStart, inner->fOppPtTEnd)) { + log->record(kAddMissingCoin_Glitch, id, outer, inner->fCoinPtTStart); + } + } else if (outerOpp == innerOpp + && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, + inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { + if (this->debugAddIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, + inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, + outer->fCoinPtTStart, outer->fCoinPtTEnd, + inner->fCoinPtTStart, inner->fCoinPtTEnd)) { + log->record(kAddMissingCoin_Glitch, id, outer, inner->fOppPtTStart); + } + } else if (outerCoin != innerCoin) { + // check to see if outer span overlaps the inner span + // look for inner segment in pt-t list + // if present, and if t values are in coincident range + // add two pairs of new coincidence + const SkOpPtT* testS = outer->fCoinPtTStart->debugContains(innerCoin); + const SkOpPtT* testE = outer->fCoinPtTEnd->debugContains(innerCoin); + if (testS && testS->fT >= inner->fCoinPtTStart->fT + && testE && testE->fT <= inner->fCoinPtTEnd->fT + && this->testForCoincidence(outer, testS, testE)) { + if (this->debugAddIfMissing(outer, testS, testE)) { + log->record(kAddMissingCoin_Glitch, id, outer, testS, testE); + } + } else { + testS = inner->fCoinPtTStart->debugContains(outerCoin); + testE = inner->fCoinPtTEnd->debugContains(outerCoin); + if (testS && testS->fT >= outer->fCoinPtTStart->fT + && testE && testE->fT <= outer->fCoinPtTEnd->fT + && this->testForCoincidence(inner, testS, testE)) { + if (this->debugAddIfMissing(inner, testS, testE)) { + log->record(kAddMissingCoin_Glitch, id, inner, testS, testE); + } + } + } + } + } + } while ((outer = outer->fNext)); +} + +bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const { + const SkCoincidentSpans* coin = fHead; + if (!coin) { + return false; + } + bool expanded = false; + do { + const SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); + const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); + const SkOpSegment* segment = coin->fCoinPtTStart->segment(); + const SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); + const SkOpSpan* prev = start->prev(); + if (prev && prev->debugContains(oppSegment)) { + double midT = (prev->t() + start->t()) / 2; + if (segment->isClose(midT, oppSegment)) { + log->record(kExpandCoin_Glitch, id, coin, prev); + } + } + SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); + if (next && next->debugContains(oppSegment)) { + double midT = (end->t() + next->t()) / 2; + if (segment->isClose(midT, oppSegment)) { + log->record(kExpandCoin_Glitch, id, coin, next); + } + } + } while ((coin = coin->fNext)); + return expanded; +} + +void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const { + const SkCoincidentSpans* coin = fHead; + if (!coin) { + return; + } + do { + if (coin->fCoinPtTStart->deleted()) { + log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTStart); + } + if (coin->fCoinPtTEnd->deleted()) { + log->record(kDeletedCoin_Glitch, id, coin, coin->fCoinPtTEnd); + } + if (coin->fOppPtTStart->deleted()) { + log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTStart); + } + if (coin->fOppPtTEnd->deleted()) { + log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd); + } + } while ((coin = coin->fNext)); + coin = fHead; + do { + if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) { + log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart); + } + if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) { + log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart); + } + } while ((coin = coin->fNext)); +} + +void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log) const { + const SkCoincidentSpans* coin = fHead; + if (!coin) { + return; + } + do { + const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); + const SkOpSpanBase* oldEnd = end; + const SkOpSpan* start = coin->fCoinPtTStart->span()->debugStarter(&end); + const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); + const SkOpSpanBase* oOldEnd = oEnd; + const SkOpSpanBase* oStart = coin->fOppPtTStart->span()->debugStarter(&oEnd); + bool flipped = (end == oldEnd) != (oEnd == oOldEnd); + if (flipped) { + SkTSwap(oStart, oEnd); + } + const SkOpSpanBase* next = start; + const SkOpSpanBase* oNext = oStart; + do { + next = next->upCast()->next(); + oNext = flipped ? oNext->prev() : oNext->upCast()->next(); + if (next == end || oNext == oEnd) { + break; + } + if (!next->containsCoinEnd(oNext)) { + log->record(kMarkCoinEnd_Glitch, id, next, oNext); + } + const SkOpSpan* nextSpan = next->upCast(); + const SkOpSpan* oNextSpan = oNext->upCast(); + if (!nextSpan->containsCoincidence(oNextSpan)) { + log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan); + } + } while (true); + } while ((coin = coin->fNext)); +} +#endif + void SkOpCoincidence::debugShowCoincidence() const { SkCoincidentSpans* span = fHead; while (span) { @@ -410,6 +1448,23 @@ void SkOpCoincidence::debugShowCoincidence() const { } } +#if DEBUG_COINCIDENCE +void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const { + const SkOpSegment* segment = &fHead; + do { + segment->debugCheckHealth(id, log); + } while ((segment = segment->next())); +} + +void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, + const SkOpCoincidence* coincidence) const { + const SkOpSegment* segment = &fHead; + do { + segment->debugMissingCoincidence(id, log, coincidence); + } while ((segment = segment->next())); +} +#endif + void SkOpSegment::debugValidate() const { #if DEBUG_VALIDATE const SkOpSpanBase* span = &fHead; @@ -439,6 +1494,57 @@ void SkOpSegment::debugValidate() const { #endif } +bool SkOpSpanBase::debugAlignedEnd(double t, const SkPoint& pt) const { + SkASSERT(zero_or_one(t)); + const SkOpSegment* segment = this->segment(); + SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt); + if (!debugAlignedInner()) { + return false; + } + if ((t ? segment->lastPt() : segment->pts()[0]) != pt) { + return false; + } + const SkOpPtT* ptT = &this->fPtT; + SkASSERT(t == ptT->fT); + SkASSERT(pt == ptT->fPt); + const SkOpPtT* test = ptT, * stopPtT = ptT; + while ((test = test->next()) != stopPtT) { + const SkOpSegment* other = test->segment(); + if (other == this->segment()) { + continue; + } + if (!zero_or_one(test->fT)) { + continue; + } + if ((test->fT ? other->lastPt() : other->pts()[0]) != pt) { + return false; + } + } + return this->fAligned; +} + +bool SkOpSpanBase::debugAlignedInner() const { + // force the spans to share points and t values + const SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT; + const SkPoint& pt = ptT->fPt; + do { + if (ptT->fPt != pt) { + return false; + } + const SkOpSpanBase* span = ptT->span(); + const SkOpPtT* test = ptT; + do { + if ((test = test->next()) == stopPtT) { + break; + } + if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) { + return false; + } + } while (true); + } while ((ptT = ptT->next()) != stopPtT); + return true; +} + bool SkOpSpanBase::debugCoinEndLoopCheck() const { int loop = 0; const SkOpSpanBase* next = this; @@ -462,6 +1568,30 @@ bool SkOpSpanBase::debugCoinEndLoopCheck() const { return true; } +bool SkOpSpanBase::debugContains(const SkOpSegment* segment) const { + const SkOpPtT* start = &fPtT; + const SkOpPtT* walk = start; + while ((walk = walk->next()) != start) { + if (walk->segment() == segment) { + return true; + } + } + return false; +} + +const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const { + const SkOpSpanBase* end = *endPtr; + SkASSERT(this->segment() == end->segment()); + const SkOpSpanBase* result; + if (t() < end->t()) { + result = this; + } else { + result = end; + *endPtr = this; + } + return result->upCast(); +} + void SkOpSpanBase::debugValidate() const { #if DEBUG_VALIDATE const SkOpPtT* ptT = &fPtT; @@ -531,6 +1661,46 @@ int SkIntersections::debugCoincidentUsed() const { #include "SkOpContour.h" +bool SkOpPtT::debugContains(const SkOpPtT* check) const { + SkASSERT(this != check); + const SkOpPtT* ptT = this; + int links = 0; + do { + ptT = ptT->next(); + if (ptT == check) { + return true; + } + ++links; + const SkOpPtT* test = this; + for (int index = 0; index < links; ++index) { + if (ptT == test) { + return false; + } + test = test->next(); + } + } while (true); +} + +const SkOpPtT* SkOpPtT::debugContains(const SkOpSegment* check) const { + SkASSERT(this->segment() != check); + const SkOpPtT* ptT = this; + int links = 0; + do { + ptT = ptT->next(); + if (ptT->segment() == check) { + return ptT; + } + ++links; + const SkOpPtT* test = this; + for (int index = 0; index < links; ++index) { + if (ptT == test) { + return nullptr; + } + test = test->next(); + } + } while (true); +} + int SkOpPtT::debugLoopLimit(bool report) const { int loop = 0; const SkOpPtT* next = this; @@ -548,7 +1718,13 @@ int SkOpPtT::debugLoopLimit(bool report) const { } } } - ++loop; + // there's nothing wrong with extremely large loop counts -- but this may appear to hang + // by taking a very long time to figure out that no loop entry is a duplicate + // -- and it's likely that a large loop count is indicative of a bug somewhere + if (++loop > 1000) { + SkDebugf("*** loop count exceeds 1000 ***\n"); + return 1000; + } } while ((next = next->fNext) && next != this); return 0; } diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index 969a9907d5..cdfddcf254 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -43,8 +43,10 @@ #define DEBUG_ACTIVE_SPANS 0 #define DEBUG_ADD_INTERSECTING_TS 0 #define DEBUG_ADD_T 0 +#define DEBUG_ALIGNMENT 0 #define DEBUG_ANGLE 0 #define DEBUG_ASSEMBLE 0 +#define DEBUG_COINCIDENCE 0 #define DEBUG_CUBIC_BINARY_SEARCH 0 #define DEBUG_CUBIC_SPLIT 0 #define DEBUG_DUMP_SEGMENTS 0 @@ -57,18 +59,22 @@ #define DEBUG_SORT 0 #define DEBUG_T_SECT 0 #define DEBUG_T_SECT_DUMP 0 +#define DEBUG_T_SECT_LOOP_COUNT 0 #define DEBUG_VALIDATE 0 #define DEBUG_WINDING 0 #define DEBUG_WINDING_AT_T 0 + #else #define DEBUG_ACTIVE_OP 1 #define DEBUG_ACTIVE_SPANS 1 #define DEBUG_ADD_INTERSECTING_TS 1 #define DEBUG_ADD_T 1 +#define DEBUG_ALIGNMENT 0 #define DEBUG_ANGLE 1 #define DEBUG_ASSEMBLE 1 +#define DEBUG_COINCIDENCE 1 #define DEBUG_CUBIC_BINARY_SEARCH 0 #define DEBUG_CUBIC_SPLIT 1 #define DEBUG_DUMP_SEGMENTS 1 @@ -79,8 +85,9 @@ #define DEBUG_PERP 1 #define DEBUG_SHOW_TEST_NAME 1 #define DEBUG_SORT 1 -#define DEBUG_T_SECT 0 -#define DEBUG_T_SECT_DUMP 0 +#define DEBUG_T_SECT 1 +#define DEBUG_T_SECT_DUMP 1 +#define DEBUG_T_SECT_LOOP_COUNT 1 #define DEBUG_VALIDATE 1 #define DEBUG_WINDING 1 #define DEBUG_WINDING_AT_T 1 @@ -117,6 +124,13 @@ extern int gDumpTSectNum; #endif +#if DEBUG_COINCIDENCE + #define DEBUG_COINCIDENCE_HEALTH(contourList, id) \ + SkPathOpsDebug::CheckHealth(contourList, id) +#else + #define DEBUG_COINCIDENCE_HEALTH(contourList, id) +#endif + #define CUBIC_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}" #define CONIC_DEBUG_STR "{{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}, %1.9g}" #define QUAD_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}" @@ -142,6 +156,7 @@ class SkPathOpsDebug { public: static const char* kLVerbStr[]; + struct GlitchLog; #if defined(SK_DEBUG) || !FORCE_RELEASE static int gContourID; @@ -157,6 +172,7 @@ public: static const char* kPathOpStr[]; #endif + static void CoincidentHealth(class SkOpContourHead* contourList, const char* id); static void MathematicaIze(char* str, size_t bufferSize); static bool ValidWind(int winding); static void WindingPrintf(int winding); @@ -175,6 +191,8 @@ public: static bool ChaseContains(const SkTDArray<class SkOpSpanBase*>& , const class SkOpSpanBase* ); + static void CheckHealth(class SkOpContourHead* contourList, const char* id); + static const struct SkOpAngle* DebugAngleAngle(const struct SkOpAngle*, int id); static class SkOpContour* DebugAngleContour(struct SkOpAngle*, int id); static const class SkOpPtT* DebugAnglePtT(const struct SkOpAngle*, int id); diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index be7fae7a8f..b5e00908fd 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -222,6 +222,23 @@ static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) { } #endif + +#if DEBUG_T_SECT_LOOP_COUNT + +#include "SkMutex.h" + +SK_DECLARE_STATIC_MUTEX(debugWorstLoop); + +SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(nullptr)); + +void ReportPathOpsDebugging() { + debugWorstState.debugLoopReport(); +} + +extern void (*gVerboseFinalize)(); + +#endif + bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, bool expectSuccess SkDEBUGPARAMS(const char* testName)) { SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune @@ -263,7 +280,7 @@ bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, return false; } #if DEBUG_DUMP_SEGMENTS - contour.dumpSegments(op); + contourList->dumpSegments("seg", op); #endif const int xorOpMask = builder.xorMask(); @@ -287,6 +304,9 @@ bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, if (!HandleCoincidence(contourList, &coincidence, &allocator)) { return false; } +#if DEBUG_ALIGNMENT + contourList->dumpSegments("aligned"); +#endif // construct closed contours result->reset(); result->setFillType(fillType); @@ -300,9 +320,134 @@ bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, *result = *assembled.nativePath(); result->setFillType(fillType); } +#if DEBUG_T_SECT_LOOP_COUNT + { + SkAutoMutexAcquire autoM(debugWorstLoop); + if (!gVerboseFinalize) { + gVerboseFinalize = &ReportPathOpsDebugging; + } + debugWorstState.debugDoYourWorst(&globalState); + } +#endif return true; } +#define DEBUG_VERIFY 0 + +#if DEBUG_VERIFY +#include "SkBitmap.h" +#include "SkCanvas.h" +#include "SkPaint.h" + +const int bitWidth = 64; +const int bitHeight = 64; + +static void debug_scale_matrix(const SkPath& one, const SkPath& two, SkMatrix& scale) { + SkRect larger = one.getBounds(); + larger.join(two.getBounds()); + SkScalar largerWidth = larger.width(); + if (largerWidth < 4) { + largerWidth = 4; + } + SkScalar largerHeight = larger.height(); + if (largerHeight < 4) { + largerHeight = 4; + } + SkScalar hScale = (bitWidth - 2) / largerWidth; + SkScalar vScale = (bitHeight - 2) / largerHeight; + scale.reset(); + scale.preScale(hScale, vScale); + larger.fLeft *= hScale; + larger.fRight *= hScale; + larger.fTop *= vScale; + larger.fBottom *= vScale; + SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft + : 16000 < larger.fRight ? 16000 - larger.fRight : 0; + SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop + : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0; + scale.preTranslate(dx, dy); +} + +static int debug_paths_draw_the_same(const SkPath& one, const SkPath& two, SkBitmap& bits) { + if (bits.width() == 0) { + bits.allocN32Pixels(bitWidth * 2, bitHeight); + } + SkCanvas canvas(bits); + canvas.drawColor(SK_ColorWHITE); + SkPaint paint; + canvas.save(); + const SkRect& bounds1 = one.getBounds(); + canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1); + canvas.drawPath(one, paint); + canvas.restore(); + canvas.save(); + canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1); + canvas.drawPath(two, paint); + canvas.restore(); + int errors = 0; + for (int y = 0; y < bitHeight - 1; ++y) { + uint32_t* addr1 = bits.getAddr32(0, y); + uint32_t* addr2 = bits.getAddr32(0, y + 1); + uint32_t* addr3 = bits.getAddr32(bitWidth, y); + uint32_t* addr4 = bits.getAddr32(bitWidth, y + 1); + for (int x = 0; x < bitWidth - 1; ++x) { + // count 2x2 blocks + bool err = addr1[x] != addr3[x]; + if (err) { + errors += addr1[x + 1] != addr3[x + 1] + && addr2[x] != addr4[x] && addr2[x + 1] != addr4[x + 1]; + } + } + } + return errors; +} + +#endif + bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { +#if DEBUG_VERIFY + if (!OpDebug(one, two, op, result, true SkDEBUGPARAMS(nullptr))) { + SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType()); + one.dumpHex(); + SkDebugf("two: fill=%d\n", two.getFillType()); + two.dumpHex(); + SkASSERT(0); + return false; + } + SkPath pathOut, scaledPathOut; + SkRegion rgnA, rgnB, openClip, rgnOut; + openClip.setRect(-16000, -16000, 16000, 16000); + rgnA.setPath(one, openClip); + rgnB.setPath(two, openClip); + rgnOut.op(rgnA, rgnB, (SkRegion::Op) op); + rgnOut.getBoundaryPath(&pathOut); + SkMatrix scale; + debug_scale_matrix(one, two, scale); + SkRegion scaledRgnA, scaledRgnB, scaledRgnOut; + SkPath scaledA, scaledB; + scaledA.addPath(one, scale); + scaledA.setFillType(one.getFillType()); + scaledB.addPath(two, scale); + scaledB.setFillType(two.getFillType()); + scaledRgnA.setPath(scaledA, openClip); + scaledRgnB.setPath(scaledB, openClip); + scaledRgnOut.op(scaledRgnA, scaledRgnB, (SkRegion::Op) op); + scaledRgnOut.getBoundaryPath(&scaledPathOut); + SkBitmap bitmap; + SkPath scaledOut; + scaledOut.addPath(*result, scale); + scaledOut.setFillType(result->getFillType()); + int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap); + const int MAX_ERRORS = 9; + if (errors > MAX_ERRORS) { + SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType()); + one.dumpHex(); + SkDebugf("two: fill=%d\n", two.getFillType()); + two.dumpHex(); + SkASSERT(0); + } + return true; +#else return OpDebug(one, two, op, result, true SkDEBUGPARAMS(nullptr)); +#endif } diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index 14fde4f9a4..34b19d1fe2 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -176,7 +176,7 @@ bool Simplify(const SkPath& path, SkPath* result) { return false; } #if DEBUG_DUMP_SEGMENTS - contour.dumpSegments((SkPathOp) -1); + contour.dumpSegments(); #endif if (!SortContourList(&contourList, false, false)) { result->reset(); @@ -196,6 +196,9 @@ bool Simplify(const SkPath& path, SkPath* result) { if (!HandleCoincidence(contourList, &coincidence, &allocator)) { return false; } +#if DEBUG_DUMP_ALIGNMENT + contour.dumpSegments("aligned"); +#endif // construct closed contours result->reset(); result->setFillType(fillType); diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h index e8a0fd499b..0da4d7f9f4 100644 --- a/src/pathops/SkPathOpsTSect.h +++ b/src/pathops/SkPathOpsTSect.h @@ -87,6 +87,7 @@ public: bool debugIsBefore(const SkTSpan* span) const; #endif void dump() const; + void dumpAll() const; void dumpBounded(int id) const; void dumpBounds() const; void dumpCoin() const; @@ -244,6 +245,7 @@ private: double* oppT); SkTSpan<TCurve, OppCurve>* boundsMax() const; void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2); + void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e); bool coincidentHasT(double t); int collapsed() const; void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, @@ -385,14 +387,14 @@ void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, doub if (!opp) { opp = this->addFollowing(priorSpan); #if DEBUG_PERP - SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan->debugID(), t, - opp->debugID()); + SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ? + priorSpan->debugID() : -1, t, opp->debugID()); #endif } #if DEBUG_PERP opp->dump(); SkDebugf("\n"); - SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan->debugID(), - opp->debugID()); + SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ? + priorSpan->debugID() : -1, opp->debugID()); #endif opp->addBounded(span, &fHeap); span->addBounded(opp, &fHeap); @@ -792,7 +794,7 @@ void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const { const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; while (testBounded) { const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded; - if (between(overlap->fStartT, oppT, overlap->fEndT)) { + if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) { return; } testBounded = testBounded->fNext; @@ -944,6 +946,39 @@ void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2 } template<typename TCurve, typename OppCurve> +void SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2, + double start1s, double start1e) { + SkTSpan<TCurve, OppCurve>* first = fHead; + SkTSpan<TCurve, OppCurve>* last = this->tail(); + SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead; + SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail(); + bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); + deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); + this->removeSpanRange(first, last); + sect2->removeSpanRange(oppFirst, oppLast); + first->fStartT = start1s; + first->fEndT = start1e; + first->resetBounds(fCurve); + first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve); + first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve); + bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); + double oppStartT = SkTMax(0., first->fCoinStart.perpT()); + double oppEndT = SkTMin(1., first->fCoinEnd.perpT()); + if (!oppMatched) { + SkTSwap(oppStartT, oppEndT); + } + oppFirst->fStartT = oppStartT; + oppFirst->fEndT = oppEndT; + oppFirst->resetBounds(sect2->fCurve); + this->removeCoincident(first, false); + sect2->removeCoincident(oppFirst, true); + if (deleteEmptySpans) { + this->deleteEmptySpans(); + sect2->deleteEmptySpans(); + } +} + +template<typename TCurve, typename OppCurve> bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) { SkTSpan<TCurve, OppCurve>* test = fCoincident; while (test) { @@ -1226,6 +1261,9 @@ int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, if (span->fIsLine && oppSpan->fIsLine) { SkIntersections i; int sects = this->linesIntersect(span, opp, oppSpan, &i); + if (sects == 2) { + return *oppResult = 1; + } if (!sects) { return -1; } @@ -1257,6 +1295,29 @@ int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, if (!oppRayI.intersectRay(this->fCurve, oppLine)) { return 0; } + // if the ends of each line intersect the opposite curve, the lines are coincident + if (thisRayI.used() > 1) { + int ptMatches = 0; + for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) { + for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { + ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]); + } + } + if (ptMatches == 2) { + return 2; + } + } + if (oppRayI.used() > 1) { + int ptMatches = 0; + for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) { + for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { + ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]); + } + } + if (ptMatches == 2) { + return 2; + } + } do { // pick the closest pair of points double closest = DBL_MAX; @@ -1921,6 +1982,10 @@ void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, } span1->addBounded(span2, §1->fHeap); span2->addBounded(span1, §2->fHeap); + const int kMaxCoinLoopCount = 8; + int coinLoopCount = kMaxCoinLoopCount; + double start1s SK_INIT_TO_AVOID_WARNING; + double start1e SK_INIT_TO_AVOID_WARNING; do { // find the largest bounds SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax(); @@ -1955,12 +2020,32 @@ void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, } sect1->validate(); sect2->validate(); +#if DEBUG_T_SECT_LOOP_COUNT + intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop); +#endif // if there are 9 or more continuous spans on both sects, suspect coincidence if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { + if (coinLoopCount == kMaxCoinLoopCount) { + start1s = sect1->fHead->fStartT; + start1e = sect1->tail()->fEndT; + } sect1->coincidentCheck(sect2); sect1->validate(); sect2->validate(); +#if DEBUG_T_SECT_LOOP_COUNT + intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop); +#endif + if (!--coinLoopCount) { + /* All known working cases resolve in two tries. Sadly, cubicConicTests[0] + gets stuck in a loop. It adds an extension to allow a coincident end + perpendicular to track its intersection in the opposite curve. However, + the bounding box of the extension does not intersect the original curve, + so the extension is discarded, only to be added again the next time around. */ + sect1->coincidentForce(sect2, start1s, start1e); + sect1->validate(); + sect2->validate(); + } } if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { @@ -1969,6 +2054,9 @@ void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, sect1->removeByPerpendicular(sect2); sect1->validate(); sect2->validate(); +#if DEBUG_T_SECT_LOOP_COUNT + intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop); +#endif if (sect1->collapsed() > TCurve::kMaxIntersections) { break; } diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index bf43c14659..ca84405aa7 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -210,6 +210,7 @@ SkOpGlobalState::SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* , fPhase(kIntersecting) SkDEBUGPARAMS(fDebugTestName(testName)) SkDEBUGPARAMS(fAngleID(0)) + SkDEBUGPARAMS(fCoinID(0)) SkDEBUGPARAMS(fContourID(0)) SkDEBUGPARAMS(fPtTID(0)) SkDEBUGPARAMS(fSegmentID(0)) @@ -217,5 +218,8 @@ SkOpGlobalState::SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* if (coincidence) { coincidence->debugSetGlobalState(this); } +#if DEBUG_T_SECT_LOOP_COUNT + debugResetLoopCounts(); +#endif } diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 2cd45a5c4d..f85c6653eb 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -25,6 +25,8 @@ enum SkPathOpsMask { class SkOpCoincidence; class SkOpContour; class SkOpContourHead; +class SkIntersections; +class SkIntersectionHelper; class SkOpGlobalState { public: @@ -41,7 +43,7 @@ public: kMaxWindingTries = 10 }; - bool angleCoincidence() { + bool angleCoincidence() const { return fAngleCoincidence; } @@ -71,6 +73,14 @@ public: const char* debugTestName() const { return fDebugTestName; } #endif +#if DEBUG_T_SECT_LOOP_COUNT + void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& , + const SkIntersectionHelper& ); + void debugDoYourWorst(SkOpGlobalState* ); + void debugLoopReport(); + void debugResetLoopCounts(); +#endif + int nested() const { return fNested; } @@ -80,9 +90,14 @@ public: return ++fAngleID; } + int nextCoinID() { + return ++fCoinID; + } + int nextContourID() { return ++fContourID; } + int nextPtTID() { return ++fPtTID; } @@ -132,11 +147,18 @@ private: #ifdef SK_DEBUG const char* fDebugTestName; int fAngleID; + int fCoinID; int fContourID; int fPtTID; int fSegmentID; int fSpanID; #endif +#if DEBUG_T_SECT_LOOP_COUNT + int fDebugLoopCount[3]; + SkPath::Verb fDebugWorstVerb[6]; + SkPoint fDebugWorstPts[24]; + float fDebugWorstWeight[6]; +#endif }; // Use Almost Equal when comparing coordinates. Use epsilon to compare T values. diff --git a/tests/PathOpsCubicConicIntersectionTest.cpp b/tests/PathOpsCubicConicIntersectionTest.cpp new file mode 100644 index 0000000000..fae1233a55 --- /dev/null +++ b/tests/PathOpsCubicConicIntersectionTest.cpp @@ -0,0 +1,73 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "PathOpsTestCommon.h" +#include "SkIntersections.h" +#include "SkPathOpsConic.h" +#include "SkPathOpsCubic.h" +#include "SkReduceOrder.h" +#include "Test.h" + +static struct cubicConic { + SkDCubic cubic; + SkDConic conic; +} cubicConicTests[] = { + {{{{188.60000610351562, 2041.5999755859375}, {188.60000610351562, 2065.39990234375}, + {208, 2084.800048828125}, {231.80000305175781, 2084.800048828125}}}, + {{{{231.80000305175781, 2084.800048828125}, {188.60000610351562, 2084.800048828125}, + {188.60000610351562, 2041.5999755859375}}}, 0.707107008f}}, + + {{{{231.80000305175781, 2084.800048828125}, {255.60000610351562, 2084.800048828125}, + {275, 2065.39990234375}, {275, 2041.5999755859375}}}, + {{{{275, 2041.5999755859375}, {275, 2084.800048828125}, + {231.80000305175781, 2084.800048828125}}}, 0.707107008f}}, +}; + +static const int cubicConicTests_count = (int) SK_ARRAY_COUNT(cubicConicTests); + +static void cubicConicIntersection(skiatest::Reporter* reporter, int index) { + const SkDCubic& cubic = cubicConicTests[index].cubic; + SkASSERT(ValidCubic(cubic)); + const SkDConic& conic = cubicConicTests[index].conic; + SkASSERT(ValidConic(conic)); + SkReduceOrder reduce1; + SkReduceOrder reduce2; + int order1 = reduce1.reduce(cubic, SkReduceOrder::kNo_Quadratics); + int order2 = reduce2.reduce(conic.fPts); + if (order1 != 4) { + SkDebugf("[%d] cubic order=%d\n", index, order1); + REPORTER_ASSERT(reporter, 0); + } + if (order2 != 3) { + SkDebugf("[%d] conic order=%d\n", index, order2); + REPORTER_ASSERT(reporter, 0); + } + SkIntersections i; + int roots = i.intersect(cubic, conic); + for (int pt = 0; pt < roots; ++pt) { + double tt1 = i[0][pt]; + SkDPoint xy1 = cubic.ptAtT(tt1); + double tt2 = i[1][pt]; + SkDPoint xy2 = conic.ptAtT(tt2); + if (!xy1.approximatelyEqual(xy2)) { + SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", + __FUNCTION__, index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); + } + REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); + } + reporter->bumpTestCount(); +} + +DEF_TEST(PathOpsCubicConicIntersection, reporter) { + for (int index = 0; index < cubicConicTests_count; ++index) { + cubicConicIntersection(reporter, index); + reporter->bumpTestCount(); + } +} + +DEF_TEST(PathOpsCubicConicIntersectionOneOff, reporter) { + cubicConicIntersection(reporter, 1); +} diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index 6186ec8170..dd7a7f7e2f 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -437,6 +437,12 @@ static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { oneOff(reporter, cubic1, cubic2, false); } +static void testsOneOff(skiatest::Reporter* reporter, int index) { + const SkDCubic& cubic1 = tests[index][0]; + const SkDCubic& cubic2 = tests[index][1]; + oneOff(reporter, cubic1, cubic2, false); +} + static void oneOffTests(skiatest::Reporter* reporter) { for (int outer = 0; outer < testSetCount - 1; ++outer) { for (int inner = outer + 1; inner < testSetCount; ++inner) { @@ -654,6 +660,11 @@ static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { } static const SkDCubic coinSet[] = { + {{{72.350448608398438, 27.966041564941406}, {72.58441162109375, 27.861515045166016}, + {72.818222045898437, 27.756658554077148}, {73.394996643066406, 27.49799919128418}}}, + {{{73.394996643066406, 27.49799919128418}, {72.818222045898437, 27.756658554077148}, + {72.58441162109375, 27.861515045166016}, {72.350448608398438, 27.966041564941406}}}, + {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.928997039794922}, {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.08599853515625}}}, {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.928997039794922}, @@ -687,7 +698,11 @@ DEF_TEST(PathOpsCubicCoinOneOff, reporter) { } DEF_TEST(PathOpsCubicIntersectionOneOff, reporter) { - newOneOff(reporter, 0, 1); + newOneOff(reporter, 66, 70); +} + +DEF_TEST(PathOpsCubicIntersectionTestsOneOff, reporter) { + testsOneOff(reporter, 10); } DEF_TEST(PathOpsCubicSelfOneOff, reporter) { diff --git a/tests/PathOpsDebug.cpp b/tests/PathOpsDebug.cpp index 263c37b120..0f96ef4f88 100755 --- a/tests/PathOpsDebug.cpp +++ b/tests/PathOpsDebug.cpp @@ -61,14 +61,9 @@ void SkDConic::dumpID(int id) const { } void SkDConic::dumpInner() const { - SkDebugf("{{"); - int index = 0; - do { - fPts[index].dump(); - SkDebugf(", "); - } while (++index < 2); - fPts[index].dump(); - SkDebugf("}, %1.9g", fWeight); + SkDebugf("{"); + fPts.dumpInner(); + SkDebugf("}}, %1.9gf", fWeight); } void SkDCubic::dump() const { @@ -674,6 +669,60 @@ void DontCallDumpTSpan() { // exists to instantiate the templates } template <typename TCurve, typename OppCurve> +void DumpAll(const SkTSpan<TCurve, OppCurve>* span) { + span->dumpAll(); +} + +void DontCallDumpSpanAll(); +void DontCallDumpSpanAll() { // exists to instantiate the templates + SkTSpan<SkDQuad, SkDQuad> q1q2; q1q2.debugInit(); + SkTSpan<SkDQuad, SkDConic> q1k2; q1k2.debugInit(); + SkTSpan<SkDQuad, SkDCubic> q1c2; q1c2.debugInit(); + SkTSpan<SkDConic, SkDQuad> k1q2; k1q2.debugInit(); + SkTSpan<SkDConic, SkDConic> k1k2; k1k2.debugInit(); + SkTSpan<SkDConic, SkDCubic> k1c2; k1c2.debugInit(); + SkTSpan<SkDCubic, SkDQuad> c1q2; c1q2.debugInit(); + SkTSpan<SkDCubic, SkDConic> c1k2; c1k2.debugInit(); + SkTSpan<SkDCubic, SkDCubic> c1c2; c1c2.debugInit(); + DumpAll(&q1q2); + DumpAll(&q1k2); + DumpAll(&q1c2); + DumpAll(&k1q2); + DumpAll(&k1k2); + DumpAll(&k1c2); + DumpAll(&c1q2); + DumpAll(&c1k2); + DumpAll(&c1c2); +} + +template <typename TCurve, typename OppCurve> +void DumpBounded(const SkTSpan<TCurve, OppCurve>* span) { + span->dumpBounded(0); +} + +void DontCallDumpSpanBounded(); +void DontCallDumpSpanBounded() { // exists to instantiate the templates + SkTSpan<SkDQuad, SkDQuad> q1q2; q1q2.debugInit(); + SkTSpan<SkDQuad, SkDConic> q1k2; q1k2.debugInit(); + SkTSpan<SkDQuad, SkDCubic> q1c2; q1c2.debugInit(); + SkTSpan<SkDConic, SkDQuad> k1q2; k1q2.debugInit(); + SkTSpan<SkDConic, SkDConic> k1k2; k1k2.debugInit(); + SkTSpan<SkDConic, SkDCubic> k1c2; k1c2.debugInit(); + SkTSpan<SkDCubic, SkDQuad> c1q2; c1q2.debugInit(); + SkTSpan<SkDCubic, SkDConic> c1k2; c1k2.debugInit(); + SkTSpan<SkDCubic, SkDCubic> c1c2; c1c2.debugInit(); + DumpBounded(&q1q2); + DumpBounded(&q1k2); + DumpBounded(&q1c2); + DumpBounded(&k1q2); + DumpBounded(&k1k2); + DumpBounded(&k1c2); + DumpBounded(&c1q2); + DumpBounded(&c1k2); + DumpBounded(&c1c2); +} + +template <typename TCurve, typename OppCurve> void DumpCoin(const SkTSpan<TCurve, OppCurve>* span) { span->dumpCoin(); } @@ -1085,9 +1134,9 @@ void SkOpSegment::dumpCoin() const { } while ((span = span->next()->upCastable())); } -void SkOpSegment::dumpPtsInner() const { +void SkOpSegment::dumpPtsInner(const char* prefix) const { int last = SkPathOpsVerbToPoints(fVerb); - SkDebugf("seg=%d {{", this->debugID()); + SkDebugf("%s=%d {{", prefix, this->debugID()); if (fVerb == SkPath::kConic_Verb) { SkDebugf("{"); } @@ -1103,8 +1152,8 @@ void SkOpSegment::dumpPtsInner() const { } } -void SkOpSegment::dumpPts() const { - dumpPtsInner(); +void SkOpSegment::dumpPts(const char* prefix) const { + dumpPtsInner(prefix); SkDebugf("\n"); } @@ -1141,11 +1190,15 @@ void SkOpCoincidence::dump() const { span->dump(); span = span->fNext; } - if (!fTop) { + if (!fTop || fHead == fTop) { return; } SkDebugf("top:\n"); span = fTop; + if (fHead) { + span->dump(); + return; + } while (span) { span->dump(); span = span->fNext; @@ -1199,23 +1252,23 @@ void SkOpContour::dumpPt(int index) const { } while ((segment = segment->next())); } -void SkOpContour::dumpPts() const { +void SkOpContour::dumpPts(const char* prefix) const { SkDebugf("contour=%d\n", this->debugID()); const SkOpSegment* segment = &fHead; do { - SkDebugf(" seg=%d ", segment->debugID()); - segment->dumpPts(); + SkDebugf(" %s=%d ", prefix, segment->debugID()); + segment->dumpPts(prefix); } while ((segment = segment->next())); } -void SkOpContour::dumpPtsX() const { +void SkOpContour::dumpPtsX(const char* prefix) const { if (!this->fCount) { SkDebugf("<empty>\n"); return; } const SkOpSegment* segment = &fHead; do { - segment->dumpPts(); + segment->dumpPts(prefix); } while ((segment = segment->next())); } @@ -1223,17 +1276,17 @@ void SkOpContour::dumpSegment(int index) const { debugSegment(index)->dump(); } -void SkOpContour::dumpSegments(SkPathOp op) const { +void SkOpContour::dumpSegments(const char* prefix, SkPathOp op) const { bool firstOp = false; const SkOpContour* c = this; do { - if (!firstOp && c->operand()) { + if (!firstOp && c->operand() && op >= 0) { #if DEBUG_ACTIVE_OP SkDebugf("op %s\n", SkPathOpsDebug::kPathOpStr[op]); #endif firstOp = true; } - c->dumpPtsX(); + c->dumpPtsX(prefix); } while ((c = c->next())); } diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index 7209617985..c96cbcdae5 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -182,6 +182,15 @@ static void scaleMatrix(const SkPath& one, const SkPath& two, SkMatrix& scale) { SkScalar vScale = (bitHeight - 2) / largerHeight; scale.reset(); scale.preScale(hScale, vScale); + larger.fLeft *= hScale; + larger.fRight *= hScale; + larger.fTop *= vScale; + larger.fBottom *= vScale; + SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft + : 16000 < larger.fRight ? 16000 - larger.fRight : 0; + SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop + : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0; + scale.postTranslate(dx, dy); } static int pathsDrawTheSame(SkBitmap& bits, const SkPath& scaledOne, const SkPath& scaledTwo, @@ -310,7 +319,7 @@ static void showPathOpPath(const char* testName, const SkPath& one, const SkPath SkPathOpsDebug::ShowOnePath(b, "pathB", false); SkDebugf(" testPathOp(reporter, path, pathB, %s, filename);\n", opStrs[shapeOp]); SkDebugf("}\n"); - drawAsciiPaths(scaledOne, scaledTwo, false); + drawAsciiPaths(scaledOne, scaledTwo, true); } void ShowTestArray(const char* testName) { diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index a28bae8b15..2f230936ff 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -5658,7 +5658,7 @@ path.lineTo(SkBits2Float(0x432c8000), SkBits2Float(0x42c00000)); path.close(); SkPath path2(path); - testPathOpCheck(reporter, path1, path2, (SkPathOp) 2, filename, FLAGS_runFail); + testPathOpFailCheck(reporter, path1, path2, (SkPathOp) 2, filename); } static void fuzz487b(skiatest::Reporter* reporter, const char* filename) { @@ -5756,10 +5756,10 @@ path.close(); } static struct TestDesc failTests[] = { + TEST(fuzz714), TEST(fuzz487a), TEST(fuzz433), TEST(fuzz1), - TEST(fuzz714), TEST(fuzz487b), TEST(fuzz433b), TEST(bufferOverflow), diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index ea1ffd92f3..622118248d 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -4994,11 +4994,42 @@ path.close(); testSimplify(reporter, path, filename); } +static void fuzz_twister(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType((SkPath::FillType) 0); +path.moveTo(0, 600); +path.lineTo(3.35544e+07f, 600); +path.lineTo(3.35544e+07f, 0); +path.lineTo(0, 0); +path.lineTo(0, 600); +path.close(); +path.moveTo(63, 600); +path.lineTo(3.35545e+07f, 600); +path.lineTo(3.35545e+07f, 0); +path.lineTo(63, 0); +path.lineTo(63, 600); +path.close(); +path.moveTo(93, 600); +path.lineTo(3.35545e+07f, 600); +path.lineTo(3.35545e+07f, 0); +path.lineTo(93, 0); +path.lineTo(93, 600); +path.close(); +path.moveTo(123, 600); +path.lineTo(3.35546e+07f, 600); +path.lineTo(3.35546e+07f, 0); +path.lineTo(123, 0); +path.lineTo(123, 600); +path.close(); + testSimplify(reporter, path, filename); +} + static void (*skipTest)(skiatest::Reporter* , const char* filename) = 0; static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; static TestDesc tests[] = { + TEST(fuzz_twister), TEST(fuzz994s_3414), TEST(fuzz994s_11), TEST(cr514118), diff --git a/tests/PathOpsSkpTest.cpp b/tests/PathOpsSkpTest.cpp index bbf3453b6d..2c5bbfaa3c 100755 --- a/tests/PathOpsSkpTest.cpp +++ b/tests/PathOpsSkpTest.cpp @@ -1087,9 +1087,6 @@ static void skpcyclist_friends_gr52(skiatest::Reporter* reporter, const char* fi pathB.cubicTo(52.238575f, 207, 50, 204.761429f, 50, 202); pathB.lineTo(50, 183); pathB.close(); - // FIXME: this generates quads and cubics that are (correctly) not coincident unlike the old code - // however, somewhere the angles are sorted incorrectly and the winding is computed to be -1/-2 - // but I can't find the error testPathOp(reporter, path, pathB, kIntersect_SkPathOp, filename); } @@ -3768,11 +3765,227 @@ pathB.cubicTo(980.018494f, 1481.22131f, 979.602478f, 1478.38831f, 984.546021f, 1 } +static void skpwww_woothemes_com_1(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType((SkPath::FillType) 1); +path.moveTo(SkBits2Float(0x44472795), SkBits2Float(0x455cdb8d)); // 796.618f, 3533.72f +path.lineTo(SkBits2Float(0x44467c27), SkBits2Float(0x455cdb8d)); // 793.94f, 3533.72f +path.lineTo(SkBits2Float(0x44467c27), SkBits2Float(0x455d055d)); // 793.94f, 3536.34f +path.lineTo(SkBits2Float(0x44472795), SkBits2Float(0x455d055d)); // 796.618f, 3536.34f +path.lineTo(SkBits2Float(0x44472795), SkBits2Float(0x455cdb8d)); // 796.618f, 3533.72f + SkPath path1(path); + path.reset(); + path.setFillType((SkPath::FillType) 0); +path.moveTo(SkBits2Float(0x4446861c), SkBits2Float(0x455cdb8d)); // 794.095f, 3533.72f +path.cubicTo(SkBits2Float(0x4446a0d8), SkBits2Float(0x455cefbb), SkBits2Float(0x444727a5), SkBits2Float(0x455d055d), SkBits2Float(0x444727a5), SkBits2Float(0x455d055d)); // 794.513f, 3534.98f, 796.619f, 3536.34f, 796.619f, 3536.34f +path.cubicTo(SkBits2Float(0x4446c5b0), SkBits2Float(0x455cf8a4), SkBits2Float(0x444693af), SkBits2Float(0x455cedad), SkBits2Float(0x44467c1b), SkBits2Float(0x455ce4b8)); // 795.089f, 3535.54f, 794.308f, 3534.85f, 793.939f, 3534.29f +path.lineTo(SkBits2Float(0x44467d70), SkBits2Float(0x455ce016)); // 793.96f, 3534.01f +path.cubicTo(SkBits2Float(0x44467fa9), SkBits2Float(0x455cde82), SkBits2Float(0x444682b5), SkBits2Float(0x455cdd03), SkBits2Float(0x4446861c), SkBits2Float(0x455cdb8d)); // 793.995f, 3533.91f, 794.042f, 3533.81f, 794.095f, 3533.72f + SkPath path2(path); + testPathOp(reporter, path1, path2, (SkPathOp) 1, filename); +} + +static void skpwww_gorcraft_ru_1(skiatest::Reporter* reporter, const char* filename) { + return; // FIXME : triggers conic/conic sort error + SkPath path; + path.setFillType((SkPath::FillType) 1); +path.moveTo(SkBits2Float(0x44924000), SkBits2Float(0x458e7800)); // 1170, 4559 +path.conicTo(SkBits2Float(0x44930000), SkBits2Float(0x458e7800), SkBits2Float(0x44930000), SkBits2Float(0x458ea800), SkBits2Float(0x3f3504f3)); // 1176, 4559, 1176, 4565, 0.707107f +path.lineTo(SkBits2Float(0x44930000), SkBits2Float(0x458f7000)); // 1176, 4590 +path.conicTo(SkBits2Float(0x44930000), SkBits2Float(0x458f9800), SkBits2Float(0x44926000), SkBits2Float(0x458f9800), SkBits2Float(0x3f3504f3)); // 1176, 4595, 1171, 4595, 0.707107f +path.lineTo(SkBits2Float(0x42a60000), SkBits2Float(0x458f9800)); // 83, 4595 +path.conicTo(SkBits2Float(0x429c0471), SkBits2Float(0x458f9800), SkBits2Float(0x429c0000), SkBits2Float(0x458f700c), SkBits2Float(0x3f352d2d)); // 78.0087f, 4595, 78, 4590.01f, 0.707721f +path.lineTo(SkBits2Float(0x429c0000), SkBits2Float(0x458ea800)); // 78, 4565 +path.conicTo(SkBits2Float(0x429c0000), SkBits2Float(0x458e7800), SkBits2Float(0x42a80000), SkBits2Float(0x458e7800), SkBits2Float(0x3f3504f3)); // 78, 4559, 84, 4559, 0.707107f +path.lineTo(SkBits2Float(0x44924000), SkBits2Float(0x458e7800)); // 1170, 4559 +path.close(); + SkPath path1(path); + path.reset(); + path.setFillType((SkPath::FillType) 0); +path.moveTo(SkBits2Float(0x429c0000), SkBits2Float(0x458f7000)); // 78, 4590 +path.lineTo(SkBits2Float(0x429c0000), SkBits2Float(0x458ea800)); // 78, 4565 +path.conicTo(SkBits2Float(0x429c0000), SkBits2Float(0x458e7800), SkBits2Float(0x42a80000), SkBits2Float(0x458e7800), SkBits2Float(0x3f3504f3)); // 78, 4559, 84, 4559, 0.707107f +path.lineTo(SkBits2Float(0x431e0000), SkBits2Float(0x458e7800)); // 158, 4559 +path.conicTo(SkBits2Float(0x431e0000), SkBits2Float(0x458e7800), SkBits2Float(0x431e0000), SkBits2Float(0x458e7800), SkBits2Float(0x3f3504f3)); // 158, 4559, 158, 4559, 0.707107f +path.lineTo(SkBits2Float(0x431e0000), SkBits2Float(0x458fa000)); // 158, 4596 +path.conicTo(SkBits2Float(0x431e0000), SkBits2Float(0x458fa000), SkBits2Float(0x431e0000), SkBits2Float(0x458fa000), SkBits2Float(0x3f3504f3)); // 158, 4596, 158, 4596, 0.707107f +path.lineTo(SkBits2Float(0x42a80000), SkBits2Float(0x458fa000)); // 84, 4596 +path.conicTo(SkBits2Float(0x429c0000), SkBits2Float(0x458fa000), SkBits2Float(0x429c0000), SkBits2Float(0x458f7000), SkBits2Float(0x3f3504f3)); // 78, 4596, 78, 4590, 0.707107f +path.close(); + + SkPath path2(path); + testPathOp(reporter, path1, path2, (SkPathOp) 2, filename); +} + +static void skpwww_neda_net_1(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType((SkPath::FillType) 1); +path.moveTo(SkBits2Float(0x447a0000), SkBits2Float(0x00000000)); // 1000, 0 +path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000)); // 0, 0 +path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x44b6e000)); // 0, 1463 +path.lineTo(SkBits2Float(0x447a0000), SkBits2Float(0x44b6e000)); // 1000, 1463 +path.lineTo(SkBits2Float(0x447a0000), SkBits2Float(0x00000000)); // 1000, 0 +path.close(); + SkPath path1(path); + path.reset(); + path.setFillType((SkPath::FillType) 0); +path.moveTo(SkBits2Float(0x366a410f), SkBits2Float(0x43a38000)); // 3.49066e-06f, 327 +path.lineTo(SkBits2Float(0x447a0000), SkBits2Float(0x43a38001)); // 1000, 327 +path.lineTo(SkBits2Float(0x447a0000), SkBits2Float(0x4435c000)); // 1000, 727 +path.lineTo(SkBits2Float(0xb66a410d), SkBits2Float(0x4435c000)); // -3.49066e-06f, 727 +path.lineTo(SkBits2Float(0x366a410f), SkBits2Float(0x43a38000)); // 3.49066e-06f, 327 +path.close(); + SkPath path2(path); + testPathOp(reporter, path1, path2, (SkPathOp) 1, filename); +} + +// "http___www_neda_net.skp" dir=87 +static void skpwww_neda_net_2(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType((SkPath::FillType) 1); +path.moveTo(SkBits2Float(0x442fc000), SkBits2Float(0x4546a000)); // 703, 3178 +path.lineTo(SkBits2Float(0x441f4000), SkBits2Float(0x4546a000)); // 637, 3178 +path.lineTo(SkBits2Float(0x441f4000), SkBits2Float(0x454ab000)); // 637, 3243 +path.lineTo(SkBits2Float(0x442fc000), SkBits2Float(0x454ab000)); // 703, 3243 +path.lineTo(SkBits2Float(0x442fc000), SkBits2Float(0x4546a000)); // 703, 3178 +path.close(); + SkPath path1(path); + path.reset(); + path.setFillType((SkPath::FillType) 0); +path.moveTo(SkBits2Float(0x44220e6e), SkBits2Float(0x45469c4c)); // 648.225f, 3177.77f +path.lineTo(SkBits2Float(0x442fc01c), SkBits2Float(0x45475696)); // 703.002f, 3189.41f +path.lineTo(SkBits2Float(0x442cf191), SkBits2Float(0x454aa3b5)); // 691.774f, 3242.23f +path.lineTo(SkBits2Float(0x441f3fe3), SkBits2Float(0x4549e96b)); // 636.998f, 3230.59f +path.lineTo(SkBits2Float(0x44220e6e), SkBits2Float(0x45469c4c)); // 648.225f, 3177.77f +path.close(); + SkPath path2(path); + testPathOp(reporter, path1, path2, (SkPathOp) 1, filename); +} + +static void skpwww_mybuilder_com_1(skiatest::Reporter* reporter, const char* filename) { + SkPath path; +path.setFillType(SkPath::kEvenOdd_FillType); +path.moveTo(1000, 659); +path.lineTo(1000, 377); +path.lineTo(455, 377); +path.lineTo(455, 659); +path.lineTo(1000, 659); +path.close(); + SkPath path1(path); + path.reset(); + path.setFillType(SkPath::kEvenOdd_FillType); +path.moveTo(921.472f, 414.086f); +path.lineTo(968.815f, 386.754f); +path.lineTo(993.069f, 428.761f); +path.lineTo(945.726f, 456.096f); +path.lineTo(921.471f, 414.086f); +path.lineTo(921.472f, 414.086f); +path.close(); +path.moveTo(971.151f, 422.889f); +path.cubicTo(966.509f, 414.848f, 957.649f, 411.727f, 950.181f, 416.038f); +path.lineTo(947.224f, 417.746f); +path.lineTo(946.979f, 417.887f); +path.lineTo(947.838f, 419.371f); +path.lineTo(947.844f, 419.367f); +path.lineTo(947.868f, 419.353f); +path.lineTo(947.945f, 419.309f); +path.cubicTo(947.988f, 419.285f, 947.988f, 419.285f, 948.023f, 419.263f); +path.cubicTo(948.039f, 419.255f, 948.039f, 419.255f, 948.047f, 419.25f); +path.lineTo(948.052f, 419.247f); +path.lineTo(947.196f, 417.762f); +path.lineTo(947.195f, 417.762f); +path.lineTo(946.888f, 417.939f); +path.lineTo(943.39f, 419.959f); +path.lineTo(944.249f, 421.443f); +path.lineTo(947.745f, 419.424f); +path.lineTo(948.05f, 419.247f); +path.lineTo(948.052f, 419.247f); +path.lineTo(947.195f, 417.763f); +path.cubicTo(947.193f, 417.763f, 947.193f, 417.763f, 947.19f, 417.766f); +path.lineTo(947.166f, 417.779f); +path.lineTo(947.087f, 417.825f); +path.lineTo(947.011f, 417.868f); +path.lineTo(946.987f, 417.883f); +path.lineTo(946.982f, 417.886f); +path.lineTo(946.98f, 417.886f); +path.lineTo(947.839f, 419.37f); +path.lineTo(948.083f, 419.229f); +path.lineTo(951.039f, 417.522f); +path.cubicTo(957.631f, 413.716f, 965.471f, 416.477f, 969.669f, 423.746f); +path.lineTo(971.153f, 422.889f); +path.lineTo(971.151f, 422.889f); +path.close(); + SkPath path2(path); + testPathOp(reporter, path1, path2, kIntersect_SkPathOp, filename); +} + +static void skpwww_nimble_com_au_1(skiatest::Reporter* reporter, const char* filename) { + SkPath path; +path.setFillType(SkPath::kEvenOdd_FillType); +path.moveTo(188.6f, 1988.8f); +path.lineTo(188.6f, 2041.6f); +path.cubicTo(188.6f, 2065.4f, 208, 2084.8f, 231.8f, 2084.8f); +path.cubicTo(255.6f, 2084.8f, 275, 2065.4f, 275, 2041.6f); +path.lineTo(275.2f, 2041.6f); +path.lineTo(275.2f, 1988.8f); +path.lineTo(188.6f, 1988.8f); +path.close(); + SkPath path1(path); + path.reset(); +path.setFillType(SkPath::kWinding_FillType); +path.moveTo(275, 2041.6f); +path.conicTo(275, 2084.8f, 231.8f, 2084.8f, 0.707107f); +path.conicTo(188.6f, 2084.8f, 188.6f, 2041.6f, 0.707107f); +path.conicTo(188.6f, 1998.4f, 231.8f, 1998.4f, 0.707107f); +path.conicTo(275, 1998.4f, 275, 2041.6f, 0.707107f); +path.close(); + SkPath path2(path); + testPathOp(reporter, path1, path2, kIntersect_SkPathOp, filename); +} + +static void skpwww_tinytots_com_1(skiatest::Reporter* reporter, const char* filename) { + SkPath path; +path.setFillType(SkPath::kEvenOdd_FillType); +path.moveTo(75.96f, 26.318f); +path.lineTo(70.337f, 26.318f); +path.lineTo(70.337f, 32.376f); +path.lineTo(75.96f, 32.376f); +path.lineTo(75.96f, 26.318f); +path.close(); + SkPath path1(path); + path.reset(); +path.setFillType(SkPath::kWinding_FillType); +path.moveTo(75.88f, 27.873f); +path.cubicTo(75.929f, 28.138f, 75.956f, 29.196f, 75.96f, 31.046f); +path.lineTo(72.766f, 32.376f); +path.cubicTo(72.763f, 30.525f, 72.735f, 29.468f, 72.686f, 29.203f); +path.cubicTo(72.636f, 28.94f, 72.519f, 28.722f, 72.335f, 28.552f); +path.cubicTo(72.248f, 28.472f, 72.058f, 28.364f, 71.763f, 28.228f); +path.cubicTo(72.425f, 27.933f, 72.425f, 27.933f, 73.395f, 27.498f); +path.cubicTo(72.425f, 27.933f, 72.425f, 27.933f, 71.763f, 28.228f); +path.cubicTo(71.425f, 28.072f, 70.95f, 27.878f, 70.337f, 27.647f); +path.lineTo(73.531f, 26.317f); +path.cubicTo(74.144f, 26.547f, 74.619f, 26.741f, 74.957f, 26.898f); +path.cubicTo(74.475f, 27.113f, 73.993f, 27.329f, 73.511f, 27.544f); +path.cubicTo(73.993f, 27.329f, 74.475f, 27.114f, 74.957f, 26.898f); +path.cubicTo(75.252f, 27.034f, 75.442f, 27.142f, 75.529f, 27.222f); +path.cubicTo(75.713f, 27.393f, 75.83f, 27.61f, 75.88f, 27.873f); + SkPath path2(path); + testPathOp(reporter, path1, path2, kIntersect_SkPathOp, filename); +} + static void (*skipTest)(skiatest::Reporter* , const char* filename) = 0; -static void (*firstTest)(skiatest::Reporter* , const char* filename) = skpwww_cooksnaps_com_32; +static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; static struct TestDesc tests[] = { + TEST(skpwww_gorcraft_ru_1), + TEST(skpwww_nimble_com_au_1), + TEST(skpwww_mybuilder_com_1), + TEST(skpwww_neda_net_2), // small coincident line segments (fixed) + TEST(skpwww_woothemes_com_1), + TEST(skpwww_neda_net_1), + TEST(skpwww_tinytots_com_1), // completely coincident reversed cubics (dup) TEST(skpwww_educationalcraft_com_4a), TEST(skpwww_lptemp_com_3), TEST(skpwww_shinydemos_com_5), diff --git a/tests/PathOpsTSectDebug.h b/tests/PathOpsTSectDebug.h index 51532f8476..9db904d06b 100644 --- a/tests/PathOpsTSectDebug.h +++ b/tests/PathOpsTSectDebug.h @@ -83,8 +83,10 @@ void SkTSect<TCurve, OppCurve>::dumpBounded(int id) const { do { if (test->findOppSpan(bounded)) { test->dump(); + SkDebugf(" "); } } while ((test = test->next())); + SkDebugf("\n"); } template<typename TCurve, typename OppCurve> @@ -141,6 +143,24 @@ const SkTSpan<TCurve, OppCurve>* SkTSpan<TCurve, OppCurve>::debugT(double t) con } template<typename TCurve, typename OppCurve> +void SkTSpan<TCurve, OppCurve>::dumpAll() const { + dumpID(); + SkDebugf("=(%g,%g) [", fStartT, fEndT); + const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; + while (testBounded) { + const SkTSpan<OppCurve, TCurve>* span = testBounded->fBounded; + const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; + span->dumpID(); + SkDebugf("=(%g,%g)", span->fStartT, span->fEndT); + if (next) { + SkDebugf(" "); + } + testBounded = next; + } + SkDebugf("]\n"); +} + +template<typename TCurve, typename OppCurve> void SkTSpan<TCurve, OppCurve>::dump() const { dumpID(); SkDebugf("=(%g,%g) [", fStartT, fEndT); diff --git a/tests/PathOpsTestCommon.h b/tests/PathOpsTestCommon.h index 3fd79e1a5a..c5ebbd1027 100644 --- a/tests/PathOpsTestCommon.h +++ b/tests/PathOpsTestCommon.h @@ -7,7 +7,7 @@ #ifndef PathOpsTestCommon_DEFINED #define PathOpsTestCommon_DEFINED -#include "SkPathOpsConic.h" +#include "SkPathOpsQuad.h" #include "SkTArray.h" struct SkPathOpsBounds; diff --git a/tests/skia_test.cpp b/tests/skia_test.cpp index dc5ae97c3f..38237e4c02 100644 --- a/tests/skia_test.cpp +++ b/tests/skia_test.cpp @@ -30,6 +30,7 @@ DEFINE_bool2(extendedTest, x, false, "run extended tests for pathOps."); // need to explicitly declare this, or we get some weird infinite loop llist template TestRegistry* TestRegistry::gHead; +void (*gVerboseFinalize)() = nullptr; // The threads report back to this object when they are done. class Status { @@ -214,6 +215,9 @@ int test_main() { "\nFinished %d tests, %d failures, %d skipped. " "(%d internal tests)", toRun, status.failCount(), skipCount, status.testCount()); + if (gVerboseFinalize) { + (*gVerboseFinalize)(); + } } SkDebugf("\n"); diff --git a/tools/pathops_sorter.htm b/tools/pathops_sorter.htm index 7d609e8373..ed93ad687c 100644 --- a/tools/pathops_sorter.htm +++ b/tools/pathops_sorter.htm @@ -6,10 +6,9 @@ <title></title> <div style="height:0"> -<div id="sect1"> -{{{36.756134033203125, 47.42348098754882812}, {40.32709884643554688, 44.65576934814453125}, {43.57402420043945312, 41.4935760498046875}, {46.43517684936523438, 37.99703216552734375}}}, -{{{36.756134033203125, 47.42348098754882812}, {36.75614144085933788, 47.42347524616091903}}}, -{{{36.756134033203125, 47.42348098754882812}, {50.84598541259765625, 65.6024932861328125}}}, +<div id="cubics"> +{{{231.80000305175781, 2084.800048828125}, {255.60000610351562, 2084.800048828125}, {275, 2065.39990234375}, {275, 2041.5999755859375}}}, +{{{275, 2041.5999755859375}, {275, 2084.800048828125}, {231.80000305175781, 2084.800048828125}}, 0.707107008}, </div> </div> @@ -17,7 +16,7 @@ <script type="text/javascript"> var testDivs = [ -sect1, +cubics, ]; var decimal_places = 3; diff --git a/tools/pathops_visualizer.htm b/tools/pathops_visualizer.htm index 194c89980d..3cf835c3ca 100644 --- a/tools/pathops_visualizer.htm +++ b/tools/pathops_visualizer.htm @@ -2,200 +2,314 @@ <head> <div height="0" hidden="true"> -<div id="battleOp183"> -seg=1 {{{6.31801322e-006f, -60}, {0, -83}}} -seg=2 {{{0, -83}, {32.0712242f, -83}, {61.2726326f, -64.5230865f}, {75.0056381f, -35.5408783f}}} -seg=3 {{{75.0056381f, -35.5408783f}, {88.7386475f, -6.55867052f}, {84.545517f, 27.7420006f}, {64.2353287f, 52.562561f}}} -seg=4 {{{64.2353287f, 52.562561f}, {60.2773972f, 57.3994484f}, {55.7858162f, 61.773819f}, {50.8459854f, 65.6024933f}}} -seg=5 {{{50.8459854f, 65.6024933f}, {36.756134f, 47.423481f}}} -seg=6 {{{36.756134f, 47.423481f}, {40.3270988f, 44.6557693f}, {43.5740242f, 41.493576f}, {46.4351768f, 37.9970322f}}} -seg=7 {{{46.4351768f, 37.9970322f}, {61.1172447f, 20.0544662f}, {64.1484222f, -4.74120331f}, {54.2209473f, -25.6921959f}}} -seg=8 {{{54.2209473f, -25.6921959f}, {44.2934723f, -46.6431847f}, {23.1840267f, -60}, {6.31801322e-006f, -60}}} +<div id="skpwww_gorcraft_ru_1"> +seg=1 {{{{1170, 4559}, {1176, 4559}, {1176, 4565}}}, 0.707106769f} +seg=2 {{{1176, 4565}, {1176, 4590}}} +seg=3 {{{{1176, 4590}, {1176, 4595}, {1171, 4595}}}, 0.707106769f} +seg=4 {{{1171, 4595}, {83, 4595}}} +seg=5 {{{{83, 4595}, {78.0086746f, 4595}, {78, 4590.00586f}}}, 0.707720578f} +seg=6 {{{78, 4590.00586f}, {78, 4565}}} +seg=7 {{{{78, 4565}, {78, 4559}, {84, 4559}}}, 0.707106769f} +seg=8 {{{84, 4559}, {1170, 4559}}} op union -seg=9 {{{50.8459854f, 65.6024857f}, {23.334074f, 86.9259186f}, {-14.5602179f, 88.8177719f}, {-44.0591507f, 70.3405457f}}} -seg=10 {{{-44.0591507f, 70.3405457f}, {-73.5580902f, 51.8633156f}, {-88.3942261f, 16.9427452f}, {-81.2158127f, -17.116993f}}} -seg=11 {{{-81.2158127f, -17.116993f}, {-74.0374069f, -51.1767159f}, {-46.3696136f, -77.1391754f}, {-11.9226456f, -82.1392059f}}} -seg=12 {{{-11.9226456f, -82.1392059f}, {-8.61876869f, -59.3777466f}}} -seg=13 {{{-8.61876869f, -59.3777466f}, {-33.5202026f, -55.7632599f}, {-53.5210152f, -36.9952087f}, {-58.7102203f, -12.3737135f}}} -seg=14 {{{-58.7102203f, -12.3737135f}, {-63.8994179f, 12.2477798f}, {-53.1744957f, 37.4915581f}, {-31.849966f, 50.8485832f}}} -seg=15 {{{-31.849966f, 50.8485832f}, {-10.5254354f, 64.2056046f}, {16.8680305f, 62.8380051f}, {36.7561607f, 47.4234695f}}} -seg=16 {{{36.7561607f, 47.4234695f}, {50.8459854f, 65.6024857f}}} -debugShowCubicLineIntersection wtTs[0]=0 {{{0,-83}, {32.0712242,-83}, {61.2726326,-64.5230865}, {75.0056381,-35.5408783}}} {{0,-83}} wnTs[0]=1 {{{6.31801322e-006,-60}, {0,-83}}} -debugShowCubicLineIntersection wtTs[0]=1 {{{54.2209473,-25.6921959}, {44.2934723,-46.6431847}, {23.1840267,-60}, {6.31801322e-006,-60}}} {{6.31801322e-006,-60}} wnTs[0]=0 {{{6.31801322e-006,-60}, {0,-83}}} -debugShowCubicIntersection wtTs[0]=1 {{{0,-83}, {32.0712242,-83}, {61.2726326,-64.5230865}, {75.0056381,-35.5408783}}} {{75.0056381,-35.5408783}} wnTs[0]=0 {{{75.0056381,-35.5408783}, {88.7386475,-6.55867052}, {84.545517,27.7420006}, {64.2353287,52.562561}}} -debugShowCubicIntersection no intersect {{{0,-83}, {32.0712242,-83}, {61.2726326,-64.5230865}, {75.0056381,-35.5408783}}} {{{54.2209473,-25.6921959}, {44.2934723,-46.6431847}, {23.1840267,-60}, {6.31801322e-006,-60}}} -debugShowCubicIntersection wtTs[0]=1 {{{75.0056381,-35.5408783}, {88.7386475,-6.55867052}, {84.545517,27.7420006}, {64.2353287,52.562561}}} {{64.2353287,52.562561}} wnTs[0]=0 {{{64.2353287,52.562561}, {60.2773972,57.3994484}, {55.7858162,61.773819}, {50.8459854,65.6024933}}} -debugShowCubicLineIntersection wtTs[0]=1 {{{64.2353287,52.562561}, {60.2773972,57.3994484}, {55.7858162,61.773819}, {50.8459854,65.6024933}}} {{50.8459854,65.6024933}} wnTs[0]=0 {{{50.8459854,65.6024933}, {36.756134,47.423481}}} -debugShowCubicLineIntersection wtTs[0]=0 {{{36.756134,47.423481}, {40.3270988,44.6557693}, {43.5740242,41.493576}, {46.4351768,37.9970322}}} {{36.756134,47.423481}} wnTs[0]=1 {{{50.8459854,65.6024933}, {36.756134,47.423481}}} -debugShowCubicIntersection wtTs[0]=1 {{{36.756134,47.423481}, {40.3270988,44.6557693}, {43.5740242,41.493576}, {46.4351768,37.9970322}}} {{46.4351768,37.9970322}} wnTs[0]=0 {{{46.4351768,37.9970322}, {61.1172447,20.0544662}, {64.1484222,-4.74120331}, {54.2209473,-25.6921959}}} -debugShowCubicIntersection wtTs[0]=1 {{{46.4351768,37.9970322}, {61.1172447,20.0544662}, {64.1484222,-4.74120331}, {54.2209473,-25.6921959}}} {{54.2209473,-25.6921959}} wnTs[0]=0 {{{54.2209473,-25.6921959}, {44.2934723,-46.6431847}, {23.1840267,-60}, {6.31801322e-006,-60}}} -debugShowCubicIntersection no intersect {{{64.2353287,52.562561}, {60.2773972,57.3994484}, {55.7858162,61.773819}, {50.8459854,65.6024933}}} {{{50.8459854,65.6024857}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} -debugShowCubicLineIntersection no intersect {{{64.2353287,52.562561}, {60.2773972,57.3994484}, {55.7858162,61.773819}, {50.8459854,65.6024933}}} {{{36.7561607,47.4234695}, {50.8459854,65.6024857}}} -debugShowCubicLineIntersection wtTs[0]=0 {{{50.8459854,65.6024857}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} {{50.8459854,65.6024857}} wnTs[0]=2.62183e-007 {{{50.8459854,65.6024933}, {36.756134,47.423481}}} -SkOpSegment::addT alias t=2.62182896e-007 segID=5 spanID=9 -debugShowCubicLineIntersection wtTs[0]=0.999999628 {{{-31.849966,50.8485832}, {-10.5254354,64.2056046}, {16.8680305,62.8380051}, {36.7561607,47.4234695}}} {{36.7561378,47.4234886}} wnTs[0]=1 {{{50.8459854,65.6024933}, {36.756134,47.423481}}} -SkOpSegment::addT alias t=0.999999682 segID=5 spanID=10 -SkOpSegment::addT insert t=0.999999628 segID=15 spanID=33 -debugShowLineIntersection wtTs[0]=2.62182896e-007 {{{50.8459854,65.6024933}, {36.756134,47.423481}}} {{50.8459854,65.6024857}} wnTs[0]=1 {{{36.7561607,47.4234695}, {50.8459854,65.6024857}}} -debugShowCubicIntersection no intersect {{{36.756134,47.423481}, {40.3270988,44.6557693}, {43.5740242,41.493576}, {46.4351768,37.9970322}}} {{{-31.849966,50.8485832}, {-10.5254354,64.2056046}, {16.8680305,62.8380051}, {36.7561607,47.4234695}}} -debugShowCubicLineIntersection no intersect {{{36.756134,47.423481}, {40.3270988,44.6557693}, {43.5740242,41.493576}, {46.4351768,37.9970322}}} {{{36.7561607,47.4234695}, {50.8459854,65.6024857}}} -debugShowCubicIntersection wtTs[0]=1 {{{50.8459854,65.6024857}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} {{-44.0591507,70.3405457}} wnTs[0]=0 {{{-44.0591507,70.3405457}, {-73.5580902,51.8633156}, {-88.3942261,16.9427452}, {-81.2158127,-17.116993}}} -debugShowCubicLineIntersection wtTs[0]=0 {{{50.8459854,65.6024857}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} {{50.8459854,65.6024857}} wnTs[0]=1 {{{36.7561607,47.4234695}, {50.8459854,65.6024857}}} -debugShowCubicIntersection wtTs[0]=1 {{{-44.0591507,70.3405457}, {-73.5580902,51.8633156}, {-88.3942261,16.9427452}, {-81.2158127,-17.116993}}} {{-81.2158127,-17.116993}} wnTs[0]=0 {{{-81.2158127,-17.116993}, {-74.0374069,-51.1767159}, {-46.3696136,-77.1391754}, {-11.9226456,-82.1392059}}} -debugShowCubicIntersection no intersect {{{-44.0591507,70.3405457}, {-73.5580902,51.8633156}, {-88.3942261,16.9427452}, {-81.2158127,-17.116993}}} {{{-8.61876869,-59.3777466}, {-33.5202026,-55.7632599}, {-53.5210152,-36.9952087}, {-58.7102203,-12.3737135}}} -debugShowCubicIntersection no intersect {{{-44.0591507,70.3405457}, {-73.5580902,51.8633156}, {-88.3942261,16.9427452}, {-81.2158127,-17.116993}}} {{{-58.7102203,-12.3737135}, {-63.8994179,12.2477798}, {-53.1744957,37.4915581}, {-31.849966,50.8485832}}} -debugShowCubicLineIntersection wtTs[0]=1 {{{-81.2158127,-17.116993}, {-74.0374069,-51.1767159}, {-46.3696136,-77.1391754}, {-11.9226456,-82.1392059}}} {{-11.9226456,-82.1392059}} wnTs[0]=0 {{{-11.9226456,-82.1392059}, {-8.61876869,-59.3777466}}} -debugShowCubicIntersection no intersect {{{-81.2158127,-17.116993}, {-74.0374069,-51.1767159}, {-46.3696136,-77.1391754}, {-11.9226456,-82.1392059}}} {{{-8.61876869,-59.3777466}, {-33.5202026,-55.7632599}, {-53.5210152,-36.9952087}, {-58.7102203,-12.3737135}}} -debugShowCubicLineIntersection wtTs[0]=0 {{{-8.61876869,-59.3777466}, {-33.5202026,-55.7632599}, {-53.5210152,-36.9952087}, {-58.7102203,-12.3737135}}} {{-8.61876869,-59.3777466}} wnTs[0]=1 {{{-11.9226456,-82.1392059}, {-8.61876869,-59.3777466}}} -debugShowCubicIntersection wtTs[0]=1 {{{-8.61876869,-59.3777466}, {-33.5202026,-55.7632599}, {-53.5210152,-36.9952087}, {-58.7102203,-12.3737135}}} {{-58.7102203,-12.3737135}} wnTs[0]=0 {{{-58.7102203,-12.3737135}, {-63.8994179,12.2477798}, {-53.1744957,37.4915581}, {-31.849966,50.8485832}}} -debugShowCubicIntersection wtTs[0]=1 {{{-58.7102203,-12.3737135}, {-63.8994179,12.2477798}, {-53.1744957,37.4915581}, {-31.849966,50.8485832}}} {{-31.849966,50.8485832}} wnTs[0]=0 {{{-31.849966,50.8485832}, {-10.5254354,64.2056046}, {16.8680305,62.8380051}, {36.7561607,47.4234695}}} -debugShowCubicLineIntersection wtTs[0]=1 {{{-31.849966,50.8485832}, {-10.5254354,64.2056046}, {16.8680305,62.8380051}, {36.7561607,47.4234695}}} {{36.7561607,47.4234695}} wnTs[0]=0 {{{36.7561607,47.4234695}, {50.8459854,65.6024857}}} -SkOpSegment::sortAngles [4] tStart=1 [8] -SkOpAngle::after [4/1] 1/1 tStart=1 tEnd=0 < [16/8] 9/9 tStart=1 tEnd=0 < [5/2] 9/9 tStart=0 tEnd=1 T 7 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {55.7858162,61.773819}, {60.2773972,57.3994484}, {64.2353287,52.562561}}} id=4 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {36.7561607,47.4234695}}} id=16 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {36.756134,47.423481}}} id=5 -SkOpAngle::after [4/1] 1/1 tStart=1 tEnd=0 < [9/5] 17/17 tStart=0 tEnd=1 < [16/8] 9/9 tStart=1 tEnd=0 F 4 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {55.7858162,61.773819}, {60.2773972,57.3994484}, {64.2353287,52.562561}}} id=4 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} id=9 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {36.7561607,47.4234695}}} id=16 -SkOpAngle::after [16/8] 9/9 tStart=1 tEnd=0 < [9/5] 17/17 tStart=0 tEnd=1 < [5/2] 9/9 tStart=0 tEnd=1 F 5 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {36.7561607,47.4234695}}} id=16 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} id=9 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {36.756134,47.423481}}} id=5 -SkOpAngle::after [5/2] 9/9 tStart=0 tEnd=1 < [9/5] 17/17 tStart=0 tEnd=1 < [4/1] 1/1 tStart=1 tEnd=0 T 4 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {36.756134,47.423481}}} id=5 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {23.334074,86.9259186}, {-14.5602179,88.8177719}, {-44.0591507,70.3405457}}} id=9 -SkOpAngle::afterPart {{{50.8459854,65.6024933}, {55.7858162,61.773819}, {60.2773972,57.3994484}, {64.2353287,52.562561}}} id=4 -SkOpSegment::sortAngles [5] tStart=0 [9] -SkOpSegment::sortAngles [5] tStart=1 [10] -SkOpAngle::after [5/3] 25/25 tStart=1 tEnd=0 < [15/7] 1/1 tStart=0.999999628 tEnd=1 < [15/6] 17/17 tStart=0.999999628 tEnd=0 T 4 -SkOpAngle::afterPart {{{36.756134,47.423481}, {50.8459854,65.6024933}}} id=5 -SkOpAngle::afterPart {{{36.756134,47.423481}, {36.7561414,47.4234752}, {36.7561533,47.4234753}, {36.7561607,47.4234695}}} id=15 -SkOpAngle::afterPart {{{36.756134,47.423481}, {16.8680057,62.8380003}, {-10.5254434,64.2055996}, {-31.849966,50.8485832}}} id=15 -SkOpAngle::after [5/3] 25/25 tStart=1 tEnd=0 < [6/4] 1/1 tStart=0 tEnd=1 < [15/7] 1/1 tStart=0.999999628 tEnd=1 T 7 -SkOpAngle::afterPart {{{36.756134,47.423481}, {50.8459854,65.6024933}}} id=5 -SkOpAngle::afterPart {{{36.756134,47.423481}, {40.3270988,44.6557693}, {43.5740242,41.493576}, {46.4351768,37.9970322}}} id=6 -SkOpAngle::afterPart {{{36.756134,47.423481}, {36.7561414,47.4234752}, {36.7561533,47.4234753}, {36.7561607,47.4234695}}} id=15 -SkOpSegment::sortAngles [6] tStart=0 [11] +seg=9 {{{78, 4590}, {78, 4565}}} +seg=10 {{{{78, 4565}, {78, 4559}, {84, 4559}}}, 0.707106769f} +seg=11 {{{84, 4559}, {158, 4559}}} +seg=12 {{{158, 4559}, {158, 4596}}} +seg=13 {{{158, 4596}, {84, 4596}}} +seg=14 {{{{84, 4596}, {78, 4596}, {78, 4590}}}, 0.707106769f} +debugShowConicLineIntersection wtTs[0]=1 {{{{1170,4559}, {1176,4559}, {1176,4565}}}, 0.707106769} {{1176,4565}} wnTs[0]=0 {{{1176,4565}, {1176,4590}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{1170,4559}, {1176,4559}, {1176,4565}}}, 0.707106769} {{1170,4559}} wnTs[0]=1 {{{84,4559}, {1170,4559}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{1176,4590}, {1176,4595}, {1171,4595}}}, 0.707106769} {{1176,4590}} wnTs[0]=1 {{{1176,4565}, {1176,4590}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{1176,4590}, {1176,4595}, {1171,4595}}}, 0.707106769} {{1171,4595}} wnTs[0]=0 {{{1171,4595}, {83,4595}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{83,4595}, {78.0086746,4595}, {78,4590.00586}}}, 0.707720578} {{83,4595}} wnTs[0]=1 {{{1171,4595}, {83,4595}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{83,4595}, {78.0086746,4595}, {78,4590.00586}}}, 0.707720578} {{78,4590.00586}} wnTs[0]=0 {{{78,4590.00586}, {78,4565}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{78,4565}} wnTs[0]=1 {{{78,4590.00586}, {78,4565}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{84,4559}} wnTs[0]=0 {{{84,4559}, {1170,4559}}} +debugShowLineIntersection wtTs[0]=0.972972973 {{{158,4559}, {158,4596}}} {{158,4595}} wnTs[0]=0.931066 {{{1171,4595}, {83,4595}}} +SkOpSegment::addT insert t=0.931066176 segID=4 spanID=29 +SkOpSegment::addT insert t=0.972972973 segID=12 spanID=30 +debugShowConicLineIntersection no intersect {{{{84,4596}, {78,4596}, {78,4590}}}, 0.707106769} {{{1171,4595}, {83,4595}}} +debugShowConicLineIntersection no intersect {{{{83,4595}, {78.0086746,4595}, {78,4590.00586}}}, 0.707720578} {{{78,4590}, {78,4565}}} +id=1 1=(0,1) [4,2] id=2 2=(0,0.5) [1] 4=(0.5,1) [1] +id=1 1=(0,0.5) [4,2] 3=(0.5,1) [4] id=2 2=(0,0.5) [1] 4=(0.5,1) [3,1] +id=1 1=(0,0.5) [2] 3=(0.5,1) [6,4] id=2 2=(0,0.5) [1] 4=(0.5,0.75) [3] 6=(0.75,1) [3] +id=1 3=(0.5,1) [6,4] id=2 4=(0.5,0.75) [3] 6=(0.75,1) [3] +id=1 3=(0.5,0.75) [6,4] 5=(0.75,1) [6] id=2 4=(0.5,0.75) [3] 6=(0.75,1) [5,3] +id=1 3=(0.5,0.75) [4] 5=(0.75,1) [10,6] id=2 4=(0.5,0.75) [3] 6=(0.75,0.875) [5] 10=(0.875,1) [5] +id=1 5=(0.75,1) [10,6] id=2 6=(0.75,0.875) [5] 10=(0.875,1) [5] +id=1 5=(0.75,0.875) [10,6] 7=(0.875,1) [10] id=2 6=(0.75,0.875) [5] 10=(0.875,1) [7,5] +id=1 5=(0.75,0.875) [10] 7=(0.875,1) [10] id=2 10=(0.875,1) [7,5] +id=1 7=(0.875,1) [16,10] id=2 10=(0.875,0.9375) [7] 16=(0.9375,1) [7] +id=1 7=(0.875,0.9375) [16,10] 9=(0.9375,1) [16] id=2 10=(0.875,0.9375) [7] 16=(0.9375,1) [9,7] +id=1 7=(0.875,0.9375) [16] 9=(0.9375,1) [16] id=2 16=(0.9375,1) [9,7] +id=1 9=(0.9375,1) [20,16] id=2 16=(0.9375,0.96875) [9] 20=(0.96875,1) [9] +id=1 9=(0.9375,0.96875) [20,16] 11=(0.96875,1) [20] id=2 16=(0.9375,0.96875) [9] 20=(0.96875,1) [11,9] +id=1 9=(0.9375,0.96875) [20] 11=(0.96875,1) [20] id=2 20=(0.96875,1) [11,9] +id=1 11=(0.96875,1) [24,20] id=2 20=(0.96875,0.984375) [11] 24=(0.984375,1) [11] +id=1 11=(0.96875,0.984375) [24,20] 13=(0.984375,1) [24] id=2 20=(0.96875,0.984375) [11] 24=(0.984375,1) [13,11] +id=1 11=(0.96875,0.984375) [24] 13=(0.984375,1) [24] id=2 24=(0.984375,1) [13,11] +id=1 13=(0.984375,1) [28,24] id=2 24=(0.984375,0.992188) [13] 28=(0.992188,1) [13] +id=1 13=(0.984375,0.992188) [24] 15=(0.992188,1) [28] id=2 24=(0.984375,0.992188) [13] 28=(0.992188,1) [15] +id=1 15=(0.992188,1) [28] id=2 28=(0.992188,1) [15] +id=1 15=(0.992188,1) [32,28] id=2 28=(0.992188,0.996094) [15] 32=(0.996094,1) [15] +id=1 15=(0.992188,0.996094) [28] 17=(0.996094,1) [28,32] id=2 28=(0.992188,0.996094) [17,15] 32=(0.996094,1) [17] +id=1 17=(0.996094,1) [32] id=2 32=(0.996094,1) [17] +id=1 17=(0.996094,1) [36,32] id=2 32=(0.996094,0.998047) [17] 36=(0.998047,1) [17] +id=1 19=(0.998047,1) [36] id=2 36=(0.998047,1) [19] +id=1 19=(0.998047,1) [38,36] id=2 36=(0.998047,0.999023) [19] 38=(0.999023,1) [19] +setPerp t=0.998046875 cPt=(78.0000229,4590.01658) == oppT=0.998483762 fPerpPt=(78.0000301,4590.01658) +setPerp t=0.999023438 cPt=(78.0000057,4590.00829) == oppT=0.99965636 fPerpPt=(78.0000048,4590.00829) +setPerp t=0.999023438 cPt=(78.0000168,4590.01276) == oppT=0.998496341 fPerpPt=(78.0000136,4590.01276) +setPerp t=0.998046875 cPt=(78.0000229,4590.01658) == oppT=0.998483762 fPerpPt=(78.0000301,4590.01658) +setPerp t=0.999023438 cPt=(78.0000057,4590.00829) == oppT=0.99965636 fPerpPt=(78.0000048,4590.00829) +setPerp t=0.999023438 cPt=(78.0000168,4590.01276) == oppT=0.998496341 fPerpPt=(78.0000136,4590.01276) +setPerp t=0.999339899 cPt=(78.0000103,4590.01053) == oppT=0.998759893 fPerpPt=(78.0000092,4590.01053) +id=1 21=(0.99934,0.99934) [36] id=2 36=(0.99876,0.99876) [21] +debugShowConicIntersection wtTs[0]=0.999339899 {{{{83,4595}, {78.0086746,4595}, {78,4590.00586}}}, 0.707720578} {{78.0000076,4590.01074}} wnTs[0]=0.99876 {{{{84,4596}, {78,4596}, {78,4590}}}, 0.707106769} +SkOpSegment::addT insert t=0.999339899 segID=5 spanID=31 +SkOpSegment::addT insert t=0.998759893 segID=14 spanID=32 +debugShowLineIntersection wtTs[0]=0 {{{78,4590}, {78,4565}}} {{78,4590}} wtTs[1]=1 {{78,4565}} wnTs[0]=0.00023432 {{{78,4590.00586}, {78,4565}}} wnTs[1]=1 +SkOpSegment::addT insert t=0.000234320081 segID=6 spanID=33 +debugShowConicLineIntersection wtTs[0]=0 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{78,4565}} wnTs[0]=1 {{{78,4590.00586}, {78,4565}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{84,4596}, {78,4596}, {78,4590}}}, 0.707106769} {{78,4590}} wnTs[0]=0.00023432 {{{78,4590.00586}, {78,4565}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{78,4565}} wnTs[0]=1 {{{78,4590}, {78,4565}}} +id=1 1=(0,1) [4,2] id=2 2=(0,0.5) [1] 4=(0.5,1) [1] +id=1 1=(0,0.5) [4,2] 3=(0.5,1) [2,4] id=2 2=(0,0.5) [3,1] 4=(0.5,1) [3,1] +id=1 1=(0,0.5) [6,4,2] 3=(0.5,1) [6,4] id=2 2=(0,0.25) [1] 6=(0.25,0.5) [1,3] 4=(0.5,1) [3,1] +id=1 1=(0,0.25) [6,2] 5=(0.25,0.5) [2,4,6] 3=(0.5,1) [6,4] id=2 2=(0,0.25) [5,1] 6=(0.25,0.5) [5,1,3] 4=(0.5,1) [5,3] +id=1 1=(0,0.25) [6,2] 5=(0.25,0.5) [2,4,6] 3=(0.5,1) [8,6,4] id=2 2=(0,0.25) [5,1] 6=(0.25,0.5) [5,1,3] 4=(0.5,0.75) [5,3] 8=(0.75,1) [3] +id=1 1=(0,0.25) [6,2] 5=(0.25,0.5) [2,4,6] 3=(0.5,0.75) [8,6,4] 7=(0.75,1) [4,8] id=2 2=(0,0.25) [5,1] 6=(0.25,0.5) [5,1,3] 4=(0.5,0.75) [7,5,3] 8=(0.75,1) [7,3] +id=1 1=(0,0.25) [6,2] 5=(0.25,0.5) [2,4,6] 3=(0.5,0.75) [8,6,4] 7=(0.75,1) [10,4,8] id=2 2=(0,0.25) [5,1] 6=(0.25,0.5) [5,1,3] 4=(0.5,0.75) [7,5,3] 8=(0.75,0.875) [7,3] 10=(0.875,1) [7] +id=1 1=(0,0.25) [6,2] 5=(0.25,0.5) [2,4,6] 3=(0.5,0.75) [8,6,4] 7=(0.75,0.875) [10,4,8] 9=(0.875,1) [8,10] id=2 2=(0,0.25) [5,1] 6=(0.25,0.5) [5,1,3] 4=(0.5,0.75) [7,5,3] 8=(0.75,0.875) [9,7,3] 10=(0.875,1) [9,7] +id=1 1=(0,0.25) [12,6,2] 5=(0.25,0.5) [12,4,6] 3=(0.5,0.75) [8,6,4] 7=(0.75,0.875) [10,4,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [1] 12=(0.125,0.25) [1,5] 6=(0.25,0.5) [5,1,3] 4=(0.5,0.75) [7,5,3] 8=(0.75,0.875) [9,7,3] 10=(0.875,1) [9,7] +id=1 1=(0,0.125) [12,2] 11=(0.125,0.25) [2,6,12] 5=(0.25,0.5) [12,4,6] 3=(0.5,0.75) [8,6,4] 7=(0.75,0.875) [10,4,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [11,1] 12=(0.125,0.25) [11,1,5] 6=(0.25,0.5) [11,5,3] 4=(0.5,0.75) [7,5,3] 8=(0.75,0.875) [9,7,3] 10=(0.875,1) [9,7] +id=1 1=(0,0.125) [12,2] 11=(0.125,0.25) [2,6,12] 5=(0.25,0.5) [14,12,4,6] 3=(0.5,0.75) [14,8,4] 7=(0.75,0.875) [10,4,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [11,1] 12=(0.125,0.25) [11,1,5] 6=(0.25,0.375) [11,5] 14=(0.375,0.5) [3,5] 4=(0.5,0.75) [7,5,3] 8=(0.75,0.875) [9,7,3] 10=(0.875,1) [9,7] +id=1 1=(0,0.125) [12,2] 11=(0.125,0.25) [2,6,12] 5=(0.25,0.375) [14,12,6] 13=(0.375,0.5) [6,4,14] 3=(0.5,0.75) [14,8,4] 7=(0.75,0.875) [10,4,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [11,1] 12=(0.125,0.25) [11,1,5] 6=(0.25,0.375) [13,11,5] 14=(0.375,0.5) [13,3,5] 4=(0.5,0.75) [13,7,3] 8=(0.75,0.875) [9,7,3] 10=(0.875,1) [9,7] +id=1 1=(0,0.125) [12,2] 11=(0.125,0.25) [2,6,12] 5=(0.25,0.375) [14,12,6] 13=(0.375,0.5) [6,4,14] 3=(0.5,0.75) [16,14,8,4] 7=(0.75,0.875) [16,10,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [11,1] 12=(0.125,0.25) [11,1,5] 6=(0.25,0.375) [13,11,5] 14=(0.375,0.5) [13,3,5] 4=(0.5,0.625) [13,3] 16=(0.625,0.75) [3,7] 8=(0.75,0.875) [9,7,3] 10=(0.875,1) [9,7] +id=1 1=(0,0.125) [12,2] 11=(0.125,0.25) [2,6,12] 5=(0.25,0.375) [14,12,6] 13=(0.375,0.5) [6,4,14] 3=(0.5,0.625) [16,14,4] 15=(0.625,0.75) [4,8,16] 7=(0.75,0.875) [16,10,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [11,1] 12=(0.125,0.25) [11,1,5] 6=(0.25,0.375) [13,11,5] 14=(0.375,0.5) [13,3,5] 4=(0.5,0.625) [15,13,3] 16=(0.625,0.75) [15,3,7] 8=(0.75,0.875) [15,9,7] 10=(0.875,1) [9,7] +id=1 1=(0,0.125) [12,2] 11=(0.125,0.25) [18,2,6,12] 5=(0.25,0.375) [18,14,6] 13=(0.375,0.5) [6,4,14] 3=(0.5,0.625) [16,14,4] 15=(0.625,0.75) [4,8,16] 7=(0.75,0.875) [16,10,8] 9=(0.875,1) [8,10] id=2 2=(0,0.125) [11,1] 12=(0.125,0.1875) [11,1] 18=(0.1875,0.25) [5,11] 6=(0.25,0.375) [13,11,5] 14=(0.375,0.5) [13,3,5] 4=(0.5,0.625) [15,13,3] 16=(0.625,0.75) [15,3,7] 8=(0.75,0.875) [15,9,7] 10=(0.875,1) [9,7] +setPerp t=0 cPt=(78,4565) == oppT=0 fPerpPt=(78,4565) +setPerp t=0.125 cPt=(78.1001678,4563.90822) == oppT=0.125 fPerpPt=(78.1001678,4563.90822) +setPerp t=0.1875 cPt=(78.2316063,4563.34905) == oppT=0.1875 fPerpPt=(78.2316063,4563.34905) +setPerp t=0.25 cPt=(78.4212702,4562.79143) == oppT=0.25 fPerpPt=(78.4212702,4562.79143) +setPerp t=0.375 cPt=(78.9780269,4561.71674) == oppT=0.375 fPerpPt=(78.9780269,4561.71674) +setPerp t=0.5 cPt=(79.7573593,4560.75736) == oppT=0.5 fPerpPt=(79.7573593,4560.75736) +setPerp t=0.625 cPt=(80.7167415,4559.97803) == oppT=0.625 fPerpPt=(80.7167415,4559.97803) +setPerp t=0.75 cPt=(81.7914318,4559.42127) == oppT=0.75 fPerpPt=(81.7914318,4559.42127) +setPerp t=0.875 cPt=(82.9082217,4559.10017) == oppT=0.875 fPerpPt=(82.9082217,4559.10017) +setPerp t=1 cPt=(84,4559) == oppT=1 fPerpPt=(84,4559) +setPerp t=0 cPt=(78,4565) == oppT=0 fPerpPt=(78,4565) +setPerp t=1 cPt=(84,4559) == oppT=1 fPerpPt=(84,4559) +id=1 (empty) id=2 (empty) +debugShowConicIntersection wtTs[0]=0 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{78,4565}} wtTs[1]=1 {{84,4559}} wnTs[0]=0 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} wnTs[1]=1 +debugShowConicLineIntersection wtTs[0]=1 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{84,4559}} wnTs[0]=0 {{{84,4559}, {158,4559}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{84,4559}} wnTs[0]=0 {{{84,4559}, {1170,4559}}} +debugShowLineIntersection wtTs[0]=0 {{{84,4559}, {158,4559}}} {{84,4559}} wtTs[1]=1 {{158,4559}} wnTs[0]=0 {{{84,4559}, {1170,4559}}} wnTs[1]=0.0681399632 +SkOpSegment::addT insert t=0.0681399632 segID=8 spanID=34 +debugShowLineIntersection wtTs[0]=0 {{{158,4559}, {158,4596}}} {{158,4559}} wnTs[0]=0.06814 {{{84,4559}, {1170,4559}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{78,4565}} wnTs[0]=1 {{{78,4590}, {78,4565}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{84,4596}, {78,4596}, {78,4590}}}, 0.707106769} {{78,4590}} wnTs[0]=0 {{{78,4590}, {78,4565}}} +debugShowConicLineIntersection wtTs[0]=1 {{{{78,4565}, {78,4559}, {84,4559}}}, 0.707106769} {{84,4559}} wnTs[0]=0 {{{84,4559}, {158,4559}}} +debugShowLineIntersection wtTs[0]=0 {{{158,4559}, {158,4596}}} {{158,4559}} wnTs[0]=1 {{{84,4559}, {158,4559}}} +debugShowLineIntersection wtTs[0]=0 {{{158,4596}, {84,4596}}} {{158,4596}} wnTs[0]=1 {{{158,4559}, {158,4596}}} +debugShowConicLineIntersection wtTs[0]=0 {{{{84,4596}, {78,4596}, {78,4590}}}, 0.707106769} {{84,4596}} wnTs[0]=1 {{{158,4596}, {84,4596}}} +------------x-------- start +------------x-------- moveMultiples +------------x-------- findCollapsed +------------x-------- moveNearby +------------x-------- align +------------x-------- fixAligned +------------x-------- addAlignIntersections +------------x-------- expand2 +------------x-------- mark1 +------------x-------- missingCoincidence1 +------------x-------- expand3 +------------x-------- addExpanded2 +------------x-------- missingCoincidence2 +SkOpSegment::markDone id=8 (84,4559 1170,4559) t=0 [15] (84,4559) tEnd=0.0681399632 newWindSum=? newOppSum=? oppSum=? windSum=? windValue=0 oppValue=0 +SkOpSegment::markDone id=10 (78,4565 78,4559 84,4559) t=0 [19] (78,4565) tEnd=1 newWindSum=? newOppSum=? oppSum=? windSum=? windValue=0 oppValue=0 +SkOpSegment::markDone id=6 (78,4590.00586 78,4565) t=0.000234320081 [33] (78,4590) tEnd=1 newWindSum=? newOppSum=? oppSum=? windSum=? windValue=0 oppValue=0 +------------x-------- pairs->apply +------------x-------- pairs->findOverlaps +SkOpSegment::sortAngles [4] tStart=0.931066176 [29] +SkOpAngle::after [4/1] 31/31 tStart=0.931066176 tEnd=0 < [12/14] 7/7 tStart=0.972972973 tEnd=0 < [4/2] 15/15 tStart=0.931066176 tEnd=1 T 4 +SkOpAngle::afterPart {{{158,4595}, {1171,4595}}} id=4 +SkOpAngle::afterPart {{{158,4595}, {158,4559}}} id=12 +SkOpAngle::afterPart {{{158,4595}, {83,4595}}} id=4 +SkOpAngle::after [4/1] 31/31 tStart=0.931066176 tEnd=0 < [12/15] 23/23 tStart=0.972972973 tEnd=1 < [12/14] 7/7 tStart=0.972972973 tEnd=0 F 4 +SkOpAngle::afterPart {{{158,4595}, {1171,4595}}} id=4 +SkOpAngle::afterPart {{{158,4595}, {158,4596}}} id=12 +SkOpAngle::afterPart {{{158,4595}, {158,4559}}} id=12 +SkOpAngle::after [12/14] 7/7 tStart=0.972972973 tEnd=0 < [12/15] 23/23 tStart=0.972972973 tEnd=1 < [4/2] 15/15 tStart=0.931066176 tEnd=1 F 4 +SkOpAngle::afterPart {{{158,4595}, {158,4559}}} id=12 +SkOpAngle::afterPart {{{158,4595}, {158,4596}}} id=12 +SkOpAngle::afterPart {{{158,4595}, {83,4595}}} id=4 +SkOpAngle::after [4/2] 15/15 tStart=0.931066176 tEnd=1 < [12/15] 23/23 tStart=0.972972973 tEnd=1 < [4/1] 31/31 tStart=0.931066176 tEnd=0 T 4 +SkOpAngle::afterPart {{{158,4595}, {83,4595}}} id=4 +SkOpAngle::afterPart {{{158,4595}, {158,4596}}} id=12 +SkOpAngle::afterPart {{{158,4595}, {1171,4595}}} id=4 +SkOpSegment::sortAngles [5] tStart=0.999339899 [31] +SkOpAngle::after [5/3] 25/29 tStart=0.999339899 tEnd=0 < [14/16] 25/29 tStart=0.998759893 tEnd=0 < [5/4] 9/9 tStart=0.999339899 tEnd=1 F 12 +SkOpAngle::afterPart {{{{78.0000076,4590.01074}, {78.0133288,4595}, {83,4595}}}, 0.877537966} id=5 +SkOpAngle::afterPart {{{{78.0000076,4590.01074}, {78.0105173,4596}, {84,4596}}}, 0.877548993} id=14 +SkOpAngle::afterPart {{{{78.0000076,4590.01074}, {78.0000041,4590.00819}, {78,4590.00586}}}, 0.999999881} id=5 +SkOpAngle::after [5/3] 25/29 tStart=0.999339899 tEnd=0 < [14/17] 9/9 tStart=0.998759893 tEnd=1 < [5/4] 9/9 tStart=0.999339899 tEnd=1 T 11 +SkOpAngle::afterPart {{{{78.0000076,4590.01074}, {78.0133288,4595}, {83,4595}}}, 0.877537966} id=5 +SkOpAngle::afterPart {{{{78.0000076,4590.01074}, {78,4590.00526}, {78,4590}}}, 0.999999642} id=14 +SkOpAngle::afterPart {{{{78.0000076,4590.01074}, {78.0000041,4590.00819}, {78,4590.00586}}}, 0.999999881} id=5 +SkOpSegment::sortAngles [6] tStart=0.000234320081 [33] +SkOpAngle::after [6/5] 23/23 tStart=0.000234320081 tEnd=0 < [9/9] 7/7 tStart=0 tEnd=1 < [14/18] 21/21 tStart=1 tEnd=0.998759893 T 4 +SkOpAngle::afterPart {{{78,4590}, {78,4590.00586}}} id=6 +SkOpAngle::afterPart {{{78,4590}, {78,4565}}} id=9 +SkOpAngle::afterPart {{{{78,4590}, {78,4590.00526}, {78.0000076,4590.01074}}}, 0.999999642} id=14 +SkOpSegment::sortAngles [7] tStart=0 [13] +SkOpSegment::sortAngles [7] tStart=1 [14] +SkOpSegment::sortAngles [8] tStart=0.0681399632 [34] +SkOpAngle::after [8/8] 31/31 tStart=0.0681399632 tEnd=1 < [11/12] 15/15 tStart=1 tEnd=0 < [12/13] 23/23 tStart=0 tEnd=0.972972973 T 4 +SkOpAngle::afterPart {{{158,4559}, {1170,4559}}} id=8 +SkOpAngle::afterPart {{{158,4559}, {84,4559}}} id=11 +SkOpAngle::afterPart {{{158,4559}, {158,4595}}} id=12 SkOpSegment::sortAngles [9] tStart=0 [17] -SkOpSegment::sortAngles [15] tStart=0.999999628 [33] -SkOpSegment::sortAngles [16] tStart=1 [32] -SkOpSegment::debugShowActiveSpans id=1 (6.31801322e-006,-60 0,-83) t=0 (6.31801322e-006,-60) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=2 (0,-83 32.0712242,-83 61.2726326,-64.5230865 75.0056381,-35.5408783) t=0 (0,-83) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=3 (75.0056381,-35.5408783 88.7386475,-6.55867052 84.545517,27.7420006 64.2353287,52.562561) t=0 (75.0056381,-35.5408783) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=4 (64.2353287,52.562561 60.2773972,57.3994484 55.7858162,61.773819 50.8459854,65.6024933) t=0 (64.2353287,52.562561) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=5 (50.8459854,65.6024933 36.756134,47.423481) t=0 (50.8459854,65.6024933) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=6 (36.756134,47.423481 40.3270988,44.6557693 43.5740242,41.493576 46.4351768,37.9970322) t=0 (36.756134,47.423481) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=7 (46.4351768,37.9970322 61.1172447,20.0544662 64.1484222,-4.74120331 54.2209473,-25.6921959) t=0 (46.4351768,37.9970322) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=8 (54.2209473,-25.6921959 44.2934723,-46.6431847 23.1840267,-60 6.31801322e-006,-60) t=0 (54.2209473,-25.6921959) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=9 (50.8459854,65.6024933 23.334074,86.9259186 -14.5602179,88.8177719 -44.0591507,70.3405457) t=0 (50.8459854,65.6024933) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=10 (-44.0591507,70.3405457 -73.5580902,51.8633156 -88.3942261,16.9427452 -81.2158127,-17.116993) t=0 (-44.0591507,70.3405457) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=11 (-81.2158127,-17.116993 -74.0374069,-51.1767159 -46.3696136,-77.1391754 -11.9226456,-82.1392059) t=0 (-81.2158127,-17.116993) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=12 (-11.9226456,-82.1392059 -8.61876869,-59.3777466) t=0 (-11.9226456,-82.1392059) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=13 (-8.61876869,-59.3777466 -33.5202026,-55.7632599 -53.5210152,-36.9952087 -58.7102203,-12.3737135) t=0 (-8.61876869,-59.3777466) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=14 (-58.7102203,-12.3737135 -63.8994179,12.2477798 -53.1744957,37.4915581 -31.849966,50.8485832) t=0 (-58.7102203,-12.3737135) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=15 (-31.849966,50.8485832 -10.5254354,64.2056046 16.8680305,62.8380051 36.7561607,47.4234695) t=0 (-31.849966,50.8485832) tEnd=0.999999628 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=15 (-31.849966,50.8485832 -10.5254354,64.2056046 16.8680305,62.8380051 36.7561607,47.4234695) t=0.999999628 (36.756134,47.423481) tEnd=1 windSum=? windValue=1 -SkOpSegment::debugShowActiveSpans id=16 (36.7561607,47.4234695 50.8459854,65.6024933) t=0 (36.7561607,47.4234695) tEnd=1 windSum=? windValue=1 -SkOpSpan::sortableTop dir=kLeft seg=1 t=0.5 pt=(3.15900661e-006,-71.5) -SkOpSpan::sortableTop [0] valid=1 operand=1 span=21 ccw=1 seg=11 {{{-81.2158127f, -17.116993f}, {-74.0374069f, -51.1767159f}, {-46.3696136f, -77.1391754f}, {-11.9226456f, -82.1392059f}}} t=0.683500004 pt=(-42.1581116,-71.5) slope=(86.347103,-50.9415461) -SkOpSpan::sortableTop [1] valid=1 operand=1 span=23 ccw=0 seg=12 {{{-11.9226456f, -82.1392059f}, {-8.61876869f, -59.3777466f}}} t=0.46742196 pt=(-10.3783407,-71.5) slope=(3.30387688,22.7614594) -SkOpSpan::sortableTop [2] valid=1 operand=0 span=1 ccw=1 seg=1 {{{6.31801322e-006f, -60}, {0, -83}}} t=0.5 pt=(3.15900661e-006,-71.5) slope=(-6.31801322e-006,-23) -SkOpSegment::markWinding id=11 (-81.2158127,-17.116993 -74.0374069,-51.1767159 -46.3696136,-77.1391754 -11.9226456,-82.1392059) t=0 [21] (-81.2158127,-17.116993) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markWinding id=12 (-11.9226456,-82.1392059 -8.61876869,-59.3777466) t=0 [23] (-11.9226456,-82.1392059) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=13 (-8.61876869,-59.3777466 -33.5202026,-55.7632599 -53.5210152,-36.9952087 -58.7102203,-12.3737135) t=0 [25] (-8.61876869,-59.3777466) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=14 (-58.7102203,-12.3737135 -63.8994179,12.2477798 -53.1744957,37.4915581 -31.849966,50.8485832) t=0 [27] (-58.7102203,-12.3737135) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=15 (-31.849966,50.8485832 -10.5254354,64.2056046 16.8680305,62.8380051 36.7561607,47.4234695) t=0 [29] (-31.849966,50.8485832) tEnd=0.999999628 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=11 (-81.2158127,-17.116993 -74.0374069,-51.1767159 -46.3696136,-77.1391754 -11.9226456,-82.1392059) t=0 [21] (-81.2158127,-17.116993) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markWinding id=10 (-44.0591507,70.3405457 -73.5580902,51.8633156 -88.3942261,16.9427452 -81.2158127,-17.116993) t=0 [19] (-44.0591507,70.3405457) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=9 (50.8459854,65.6024933 23.334074,86.9259186 -14.5602179,88.8177719 -44.0591507,70.3405457) t=0 [17] (50.8459854,65.6024933) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=1 (6.31801322e-006,-60 0,-83) t=0 [1] (6.31801322e-006,-60) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markWinding id=2 (0,-83 32.0712242,-83 61.2726326,-64.5230865 75.0056381,-35.5408783) t=0 [3] (0,-83) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=3 (75.0056381,-35.5408783 88.7386475,-6.55867052 84.545517,27.7420006 64.2353287,52.562561) t=0 [5] (75.0056381,-35.5408783) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=4 (64.2353287,52.562561 60.2773972,57.3994484 55.7858162,61.773819 50.8459854,65.6024933) t=0 [7] (64.2353287,52.562561) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=1 (6.31801322e-006,-60 0,-83) t=0 [1] (6.31801322e-006,-60) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markWinding id=8 (54.2209473,-25.6921959 44.2934723,-46.6431847 23.1840267,-60 6.31801322e-006,-60) t=0 [15] (54.2209473,-25.6921959) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=7 (46.4351768,37.9970322 61.1172447,20.0544662 64.1484222,-4.74120331 54.2209473,-25.6921959) t=0 [13] (46.4351768,37.9970322) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=6 (36.756134,47.423481 40.3270988,44.6557693 43.5740242,41.493576 46.4351768,37.9970322) t=0 [11] (36.756134,47.423481) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::sortAngles [9] tStart=1 [18] +SkOpSegment::sortAngles [11] tStart=0 [21] +SkOpSegment::sortAngles [11] tStart=1 [22] +SkOpSegment::sortAngles [12] tStart=0 [23] +SkOpSegment::sortAngles [12] tStart=0.972972973 [30] +SkOpSegment::sortAngles [14] tStart=0.998759893 [32] +SkOpSegment::sortAngles [14] tStart=1 [28] +SkOpCoincidence::debugShowCoincidence - id=11 t=0 tEnd=1 +SkOpCoincidence::debugShowCoincidence + id=8 t=0 tEnd=0.0681399632 +SkOpCoincidence::debugShowCoincidence - id=7 t=0 tEnd=1 +SkOpCoincidence::debugShowCoincidence + id=10 t=0 tEnd=1 +SkOpCoincidence::debugShowCoincidence - id=9 t=0 tEnd=1 +SkOpCoincidence::debugShowCoincidence + id=6 t=0.000234320081 tEnd=1 +SkOpSegment::debugShowActiveSpans id=1 (1170,4559 1176,4559 1176,4565 0.707106769f) t=0 (1170,4559) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=2 (1176,4565 1176,4590) t=0 (1176,4565) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=3 (1176,4590 1176,4595 1171,4595 0.707106769f) t=0 (1176,4590) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=4 (1171,4595 83,4595) t=0 (1171,4595) tEnd=0.931066176 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=4 (1171,4595 83,4595) t=0.931066176 (158,4595) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=5 (83,4595 78.0086746,4595 78,4590.00586 0.707720578f) t=0 (83,4595) tEnd=0.999339899 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=5 (83,4595 78.0086746,4595 78,4590.00586 0.707720578f) t=0.999339899 (78.0000076,4590.01074) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=6 (78,4590.00586 78,4565) t=0 (78,4590.00586) tEnd=0.000234320081 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=7 (78,4565 78,4559 84,4559 0.707106769f) t=0 (78,4565) tEnd=1 windSum=? oppSum=? windValue=1 oppValue=1 +SkOpSegment::debugShowActiveSpans id=8 (84,4559 1170,4559) t=0.0681399632 (158,4559) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=9 (78,4590 78,4565) t=0 (78,4590) tEnd=1 windSum=? oppSum=? windValue=1 oppValue=1 +SkOpSegment::debugShowActiveSpans id=11 (84,4559 158,4559) t=0 (84,4559) tEnd=1 windSum=? oppSum=? windValue=1 oppValue=1 +SkOpSegment::debugShowActiveSpans id=12 (158,4559 158,4596) t=0 (158,4559) tEnd=0.972972973 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=12 (158,4559 158,4596) t=0.972972973 (158,4595) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=13 (158,4596 84,4596) t=0 (158,4596) tEnd=1 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=14 (84,4596 78,4596 78,4590 0.707106769f) t=0 (84,4596) tEnd=0.998759893 windSum=? windValue=1 +SkOpSegment::debugShowActiveSpans id=14 (84,4596 78,4596 78,4590 0.707106769f) t=0.998759893 (78.0000076,4590.01074) tEnd=1 windSum=? windValue=1 +SkOpSpan::sortableTop dir=kTop seg=1 t=0.5 pt=(1174.24268,4560.75732) +SkOpSpan::sortableTop [0] valid=1 operand=0 span=1 ccw=1 seg=1 {{{{1170, 4559}, {1176, 4559}, {1176, 4565}}}, 0.707106769f} t=0.5 pt=(1174.24268,4560.75732) slope=(2.56066015,2.56066015) +SkOpSegment::markWinding id=1 (1170,4559 1176,4559 1176,4565) t=0 [1] (1170,4559) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::markWinding id=2 (1176,4565 1176,4590) t=0 [3] (1176,4565) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=3 (1176,4590 1176,4595 1171,4595) t=0 [5] (1176,4590) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=4 (1171,4595 83,4595) t=0 [7] (1171,4595) tEnd=0.931066176 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=1 (1170,4559 1176,4559 1176,4565) t=0 [1] (1170,4559) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::markWinding id=8 (84,4559 1170,4559) t=0.0681399632 [34] (158,4559) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 SkOpSegment::activeOp id=1 t=1 tEnd=0 op=union miFrom=0 miTo=1 suFrom=0 suTo=0 result=1 SkOpSegment::findNextOp simple -SkOpSegment::markDone id=1 (6.31801322e-006,-60 0,-83) t=0 [1] (6.31801322e-006,-60) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -bridgeOp current id=1 from=(0,-83) to=(6.31801322e-006,-60) -SkOpSegment::findNextOp simple -SkOpSegment::markDone id=8 (54.2209473,-25.6921959 44.2934723,-46.6431847 23.1840267,-60 6.31801322e-006,-60) t=0 [15] (54.2209473,-25.6921959) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -bridgeOp current id=8 from=(6.31801322e-006,-60) to=(54.2209473,-25.6921959) -path.moveTo(0,-83); -path.lineTo(6.31801322e-006,-60); -path.cubicTo(23.1840267,-60, 44.2934723,-46.6431847, 54.2209473,-25.6921959); -SkOpSegment::findNextOp simple -SkOpSegment::markDone id=7 (46.4351768,37.9970322 61.1172447,20.0544662 64.1484222,-4.74120331 54.2209473,-25.6921959) t=0 [13] (46.4351768,37.9970322) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -bridgeOp current id=7 from=(54.2209473,-25.6921959) to=(46.4351768,37.9970322) -path.cubicTo(64.1484222,-4.74120331, 61.1172447,20.0544662, 46.4351768,37.9970322); -SkOpSegment::markWinding id=15 (-31.849966,50.8485832 -10.5254354,64.2056046 16.8680305,62.8380051 36.7561607,47.4234695) t=0.999999628 [33] (36.756134,47.423481) tEnd=1 newWindSum=1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markWinding id=16 (36.7561607,47.4234695 50.8459854,65.6024933) t=0 [31] (36.7561607,47.4234695) tEnd=1 newWindSum=1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markAngle last segment=16 span=32 -SkOpSegment::markWinding id=5 (50.8459854,65.6024933 36.756134,47.423481) t=0 [9] (50.8459854,65.6024933) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=0 -SkOpSegment::markAngle last segment=5 span=9 windSum=-1 +SkOpSegment::markDone id=1 (1170,4559 1176,4559 1176,4565) t=0 [1] (1170,4559) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +bridgeOp current id=1 from=(1176,4565) to=(1170,4559) +path.moveTo(1176,4565); +path.conicTo(1176,4559, 1170,4559, 0.707106769); +SkOpSegment::markWinding id=11 (84,4559 158,4559) t=0 [21] (84,4559) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=1 +SkOpSegment::markWinding id=7 (78,4565 78,4559 84,4559) t=0 [13] (78,4565) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=1 +SkOpSegment::markWinding id=9 (78,4590 78,4565) t=0 [17] (78,4590) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=1 +SkOpSegment::markAngle last segment=9 span=17 windSum=-1 +SkOpSegment::markWinding id=12 (158,4559 158,4596) t=0 [23] (158,4559) tEnd=0.972972973 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markAngle last segment=12 span=30 windSum=? SkOpSegment::findNextOp -SkOpAngle::dumpOne [6/4] next=15/7 sect=1/1 s=0 [11] e=1 [12] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=0 -SkOpAngle::dumpOne [15/7] next=15/6 sect=1/1 s=0.999999628 [33] e=1 [30] sgn=-1 windVal=1 windSum=1 oppVal=0 oppSum=0 operand -SkOpAngle::dumpOne [15/6] next=5/3 sect=17/17 s=0.999999628 [33] e=0 [29] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=0 operand -SkOpAngle::dumpOne [5/3] next=6/4 sect=25/25 s=1 [10] e=0 [9] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=-1 -SkOpSegment::activeOp id=15 t=0.999999628 tEnd=1 op=union miFrom=0 miTo=0 suFrom=0 suTo=1 result=1 -SkOpSegment::findNextOp chase.append segment=16 span=32 -SkOpSegment::activeOp id=15 t=0.999999628 tEnd=0 op=union miFrom=0 miTo=0 suFrom=1 suTo=0 result=1 -SkOpSegment::activeOp id=5 t=1 tEnd=0 op=union miFrom=0 miTo=1 suFrom=0 suTo=0 result=1 -SkOpSegment::findNextOp chase.append segment=5 span=9 windSum=-1 -SkOpSegment::markDone id=6 (36.756134,47.423481 40.3270988,44.6557693 43.5740242,41.493576 46.4351768,37.9970322) t=0 [11] (36.756134,47.423481) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::findNextOp from:[6] to:[15] start=13585868 end=13585412 -bridgeOp current id=6 from=(46.4351768,37.9970322) to=(36.756134,47.423481) -path.cubicTo(43.5740242,41.493576, 40.3270988,44.6557693, 36.756134,47.423481); +SkOpAngle::dumpOne [8/8] next=11/12 sect=31/31 s=0.0681399632 [34] e=1 [16] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=0 +SkOpAngle::dumpOne [11/12] next=12/13 sect=15/15 s=1 [22] e=0 [21] sgn=1 windVal=1 windSum=-1 oppVal=1 oppSum=-1 operand +SkOpAngle::dumpOne [12/13] next=8/8 sect=23/23 s=0 [23] e=0.972972973 [30] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=-1 operand +SkOpSegment::activeOp id=11 t=1 tEnd=0 op=union miFrom=0 miTo=1 suFrom=0 suTo=1 result=1 +SkOpSegment::findNextOp chase.append segment=9 span=17 windSum=-1 +SkOpSegment::activeOp id=12 t=0 tEnd=0.972972973 op=union miFrom=1 miTo=1 suFrom=1 suTo=0 result=0 +SkOpSegment::markDone id=12 (158,4559 158,4596) t=0 [23] (158,4559) tEnd=0.972972973 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::findNextOp chase.append segment=12 span=30 windSum=-2147483647 +SkOpSegment::markDone id=8 (84,4559 1170,4559) t=0.0681399632 [34] (158,4559) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::findNextOp from:[8] to:[11] start=8985900 end=8985796 +bridgeOp current id=8 from=(1170,4559) to=(158,4559) SkOpSegment::findNextOp simple -SkOpSegment::markDone id=15 (-31.849966,50.8485832 -10.5254354,64.2056046 16.8680305,62.8380051 36.7561607,47.4234695) t=0.999999628 [33] (36.756134,47.423481) tEnd=1 newWindSum=1 newOppSum=0 oppSum=0 windSum=1 windValue=1 oppValue=0 -bridgeOp current id=15 from=(36.756134,47.423481) to=(36.7561607,47.4234695) -path.cubicTo(36.7561417,47.4234734, 36.7561531,47.4234772, 36.7561607,47.4234695); +SkOpSegment::markDone id=11 (84,4559 158,4559) t=0 [21] (84,4559) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=1 +bridgeOp current id=11 from=(158,4559) to=(84,4559) +SkOpSegment::findNextOp simple +SkOpSegment::markDone id=7 (78,4565 78,4559 84,4559) t=0 [13] (78,4565) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=1 +bridgeOp current id=7 from=(84,4559) to=(78,4565) +path.lineTo(84,4559); +path.conicTo(78,4559, 78,4565, 0.707106769); +SkOpSegment::markWinding id=14 (84,4596 78,4596 78,4590) t=0.998759893 [32] (78.0000076,4590.01074) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markAngle last segment=14 span=32 windSum=-1 +SkOpSegment::markWinding id=6 (78,4590.00586 78,4565) t=0 [11] (78,4590.00586) tEnd=0.000234320081 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=5 (83,4595 78.0086746,4595 78,4590.00586) t=0.999339899 [31] (78.0000076,4590.01074) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markAngle last segment=5 span=31 windSum=-1 SkOpSegment::findNextOp -SkOpAngle::dumpOne [16/8] next=5/2 sect=9/9 s=1 [32] e=0 [31] sgn=1 windVal=1 windSum=1 oppVal=0 oppSum=0 operand -SkOpAngle::dumpOne [5/2] next=9/5 sect=9/9 s=0 [9] e=1 [10] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=-1 -SkOpAngle::dumpOne [9/5] next=4/1 sect=17/17 s=0 [17] e=1 [18] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=0 operand -SkOpAngle::dumpOne [4/1] next=16/8 sect=1/1 s=1 [8] e=0 [7] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=0 -SkOpSegment::activeOp id=5 t=0 tEnd=1 op=union miFrom=0 miTo=1 suFrom=0 suTo=0 result=1 -SkOpSegment::activeOp id=9 t=0 tEnd=1 op=union miFrom=1 miTo=1 suFrom=0 suTo=1 result=0 -SkOpSegment::markDone id=9 (50.8459854,65.6024933 23.334074,86.9259186 -14.5602179,88.8177719 -44.0591507,70.3405457) t=0 [17] (50.8459854,65.6024933) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=10 (-44.0591507,70.3405457 -73.5580902,51.8633156 -88.3942261,16.9427452 -81.2158127,-17.116993) t=0 [19] (-44.0591507,70.3405457) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=11 (-81.2158127,-17.116993 -74.0374069,-51.1767159 -46.3696136,-77.1391754 -11.9226456,-82.1392059) t=0 [21] (-81.2158127,-17.116993) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=12 (-11.9226456,-82.1392059 -8.61876869,-59.3777466) t=0 [23] (-11.9226456,-82.1392059) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=13 (-8.61876869,-59.3777466 -33.5202026,-55.7632599 -53.5210152,-36.9952087 -58.7102203,-12.3737135) t=0 [25] (-8.61876869,-59.3777466) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=14 (-58.7102203,-12.3737135 -63.8994179,12.2477798 -53.1744957,37.4915581 -31.849966,50.8485832) t=0 [27] (-58.7102203,-12.3737135) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=15 (-31.849966,50.8485832 -10.5254354,64.2056046 16.8680305,62.8380051 36.7561607,47.4234695) t=0 [29] (-31.849966,50.8485832) tEnd=0.999999628 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::activeOp id=4 t=1 tEnd=0 op=union miFrom=1 miTo=0 suFrom=1 suTo=1 result=0 -SkOpSegment::markDone id=4 (64.2353287,52.562561 60.2773972,57.3994484 55.7858162,61.773819 50.8459854,65.6024933) t=0 [7] (64.2353287,52.562561) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=3 (75.0056381,-35.5408783 88.7386475,-6.55867052 84.545517,27.7420006 64.2353287,52.562561) t=0 [5] (75.0056381,-35.5408783) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=2 (0,-83 32.0712242,-83 61.2726326,-64.5230865 75.0056381,-35.5408783) t=0 [3] (0,-83) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::markDone id=16 (36.7561607,47.4234695 50.8459854,65.6024933) t=0 [31] (36.7561607,47.4234695) tEnd=1 newWindSum=1 newOppSum=0 oppSum=0 windSum=1 windValue=1 oppValue=0 -SkOpSegment::findNextOp from:[16] to:[5] start=13582764 end=13582868 -bridgeOp current id=16 from=(36.7561607,47.4234695) to=(50.8459854,65.6024933) +SkOpAngle::dumpOne [9/9] next=14/18 sect=7/7 s=0 [17] e=1 [18] sgn=-1 windVal=1 windSum=-1 oppVal=1 oppSum=-1 operand +SkOpAngle::dumpOne [14/18] next=6/5 sect=21/21 s=1 [28] e=0.998759893 [32] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=0 operand +SkOpAngle::dumpOne [6/5] next=9/9 sect=23/23 s=0.000234320081 [33] e=0 [11] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=-1 +SkOpSegment::activeOp id=14 t=1 tEnd=0.998759893 op=union miFrom=0 miTo=0 suFrom=0 suTo=1 result=1 +SkOpSegment::findNextOp chase.append segment=14 span=32 windSum=-1 +SkOpSegment::activeOp id=6 t=0.000234320081 tEnd=0 op=union miFrom=0 miTo=1 suFrom=1 suTo=1 result=0 +SkOpSegment::markDone id=6 (78,4590.00586 78,4565) t=0 [11] (78,4590.00586) tEnd=0.000234320081 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::markDone id=5 (83,4595 78.0086746,4595 78,4590.00586) t=0.999339899 [31] (78.0000076,4590.01074) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::findNextOp chase.append segment=5 span=31 windSum=-1 +SkOpSegment::markDone id=9 (78,4590 78,4565) t=0 [17] (78,4590) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=1 +SkOpSegment::findNextOp from:[9] to:[14] start=8986620 end=8987068 +bridgeOp current id=9 from=(78,4565) to=(78,4590) +SkOpSegment::markWinding id=14 (84,4596 78,4596 78,4590) t=0 [27] (84,4596) tEnd=0.998759893 newWindSum=-2 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=13 (158,4596 84,4596) t=0 [25] (158,4596) tEnd=1 newWindSum=-2 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=12 (158,4559 158,4596) t=0.972972973 [30] (158,4595) tEnd=1 newWindSum=-2 newOppSum=0 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markAngle last segment=12 span=30 windSum=-2 +SkOpSegment::markWinding id=5 (83,4595 78.0086746,4595 78,4590.00586) t=0 [9] (83,4595) tEnd=0.999339899 newWindSum=-1 newOppSum=-2 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markWinding id=4 (1171,4595 83,4595) t=0.931066176 [29] (158,4595) tEnd=1 newWindSum=-1 newOppSum=-2 oppSum=? windSum=? windValue=1 oppValue=0 +SkOpSegment::markAngle last segment=4 span=29 windSum=-1 SkOpSegment::findNextOp -SkOpAngle::dumpOne [5/3] next=6/4 sect=25/25 s=1 [10] e=0 [9] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=-1 -SkOpAngle::dumpOne [6/4] next=15/7 sect=1/1 s=0 [11] e=1 [12] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=0 done -SkOpAngle::dumpOne [15/7] next=15/6 sect=1/1 s=0.999999628 [33] e=1 [30] sgn=-1 windVal=1 windSum=1 oppVal=0 oppSum=0 done operand -SkOpAngle::dumpOne [15/6] next=5/3 sect=17/17 s=0.999999628 [33] e=0 [29] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=0 done operand -SkOpSegment::activeOp id=6 t=0 tEnd=1 op=union miFrom=1 miTo=0 suFrom=1 suTo=1 result=0 -SkOpSegment::activeOp id=15 t=0.999999628 tEnd=1 op=union miFrom=0 miTo=0 suFrom=1 suTo=0 result=1 -SkOpSegment::activeOp id=15 t=0.999999628 tEnd=0 op=union miFrom=0 miTo=0 suFrom=0 suTo=1 result=1 -SkOpSegment::markDone id=5 (50.8459854,65.6024933 36.756134,47.423481) t=0 [9] (50.8459854,65.6024933) tEnd=1 newWindSum=-1 newOppSum=-1 oppSum=-1 windSum=-1 windValue=1 oppValue=0 -SkOpSegment::findNextOp from:[5] to:[15] start=13585868 end=13585412 -bridgeOp current id=5 from=(50.8459854,65.6024933) to=(36.756134,47.423481) -path.lineTo(50.8459854,65.6024933); -path.lineTo(36.756134,47.423481); +SkOpAngle::dumpOne [14/17] next=5/4 sect=9/9 s=0.998759893 [32] e=1 [28] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=0 operand +SkOpAngle::dumpOne [5/4] next=14/16 sect=9/9 s=0.999339899 [31] e=1 [10] sgn=-1 windVal=1 windSum=-1 oppVal=0 oppSum=-1 done +SkOpAngle::dumpOne [14/16] next=5/3 sect=25/29 s=0.998759893 [32] e=0 [27] sgn=1 windVal=1 windSum=-2 oppVal=0 oppSum=0 operand +SkOpAngle::dumpOne [5/3] next=14/17 sect=25/29 s=0.999339899 [31] e=0 [9] sgn=1 windVal=1 windSum=-1 oppVal=0 oppSum=-2 +SkOpSegment::activeOp id=5 t=0.999339899 tEnd=1 op=union miFrom=0 miTo=1 suFrom=0 suTo=0 result=1 +SkOpSegment::activeOp id=14 t=0.998759893 tEnd=0 op=union miFrom=1 miTo=1 suFrom=0 suTo=1 result=0 +SkOpSegment::markDone id=14 (84,4596 78,4596 78,4590) t=0 [27] (84,4596) tEnd=0.998759893 newWindSum=-2 newOppSum=0 oppSum=0 windSum=-2 windValue=1 oppValue=0 +SkOpSegment::markDone id=13 (158,4596 84,4596) t=0 [25] (158,4596) tEnd=1 newWindSum=-2 newOppSum=0 oppSum=0 windSum=-2 windValue=1 oppValue=0 +SkOpSegment::markDone id=12 (158,4559 158,4596) t=0.972972973 [30] (158,4595) tEnd=1 newWindSum=-2 newOppSum=0 oppSum=0 windSum=-2 windValue=1 oppValue=0 +SkOpSegment::activeOp id=5 t=0.999339899 tEnd=0 op=union miFrom=1 miTo=0 suFrom=1 suTo=1 result=0 +SkOpSegment::markDone id=5 (83,4595 78.0086746,4595 78,4590.00586) t=0 [9] (83,4595) tEnd=0.999339899 newWindSum=-1 newOppSum=-2 oppSum=-2 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::markDone id=4 (1171,4595 83,4595) t=0.931066176 [29] (158,4595) tEnd=1 newWindSum=-1 newOppSum=-2 oppSum=-2 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::findNextOp chase.append segment=4 span=29 windSum=-1 +SkOpSegment::markDone id=14 (84,4596 78,4596 78,4590) t=0.998759893 [32] (78.0000076,4590.01074) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +SkOpSegment::findNextOp from:[14] to:[5] start=8986964 end=8984396 +bridgeOp current id=14 from=(78,4590) to=(78.0000076,4590.01074) +path.lineTo(78,4590); +path.conicTo(78,4590.00537, 78.0000076,4590.01074, 0.999999642); +SkOpSegment::debugShowActiveSpans id=2 (1176,4565 1176,4590) t=0 (1176,4565) tEnd=1 windSum=-1 oppSum=0 windValue=1 oppValue=0 +SkOpSegment::debugShowActiveSpans id=3 (1176,4590 1176,4595 1171,4595 0.707106769f) t=0 (1176,4590) tEnd=1 windSum=-1 oppSum=0 windValue=1 oppValue=0 +SkOpSegment::debugShowActiveSpans id=4 (1171,4595 83,4595) t=0 (1171,4595) tEnd=0.931066176 windSum=-1 oppSum=0 windValue=1 oppValue=0 +SkOpSegment::activeOp id=4 t=0.931066176 tEnd=0 op=union miFrom=0 miTo=1 suFrom=0 suTo=0 result=1 +SkOpSegment::findNextOp simple +SkOpSegment::markDone id=4 (1171,4595 83,4595) t=0 [7] (1171,4595) tEnd=0.931066176 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +bridgeOp current id=4 from=(158,4595) to=(1171,4595) +SkOpSegment::findNextOp simple +SkOpSegment::markDone id=3 (1176,4590 1176,4595 1171,4595) t=0 [5] (1176,4590) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +bridgeOp current id=3 from=(1171,4595) to=(1176,4590) +path.moveTo(158,4595); +path.lineTo(1171,4595); +path.conicTo(1176,4595, 1176,4590, 0.707106769); +SkOpSegment::findNextOp simple +SkOpSegment::markDone id=2 (1176,4565 1176,4590) t=0 [3] (1176,4565) tEnd=1 newWindSum=-1 newOppSum=0 oppSum=0 windSum=-1 windValue=1 oppValue=0 +bridgeOp current id=2 from=(1176,4590) to=(1176,4565) +path.lineTo(1176,4565); </div> + </div> <script type="text/javascript"> var testDivs = [ - battleOp183, + skpwww_gorcraft_ru_1, ]; var decimal_places = 3; // make this 3 to show more precision @@ -266,6 +380,7 @@ var opMax = 0; var stepMax = 0; var lastIndex = 0; var hasPath = false; +var hasAlignedPath = false; var hasComputedPath = false; var angleBetween = false; var afterIndex = 0; @@ -445,7 +560,8 @@ var REC_TYPE_ACTIVE_OP = 11; var REC_TYPE_AFTERPART = 12; var REC_TYPE_TOP = 13; var REC_TYPE_COINCIDENCE = 14; -var REC_TYPE_LAST = REC_TYPE_COINCIDENCE; +var REC_TYPE_ALIGNED = 15; +var REC_TYPE_LAST = REC_TYPE_ALIGNED; function strs_to_nums(strs) { var result = []; @@ -560,6 +676,7 @@ function parse_all(test) { : line.lastIndexOf("activeOp", 0) === 0 ? REC_TYPE_ACTIVE_OP : line.lastIndexOf("computed", 0) === 0 ? REC_TYPE_COMPUTED : line.lastIndexOf("debugOne", 0) === 0 ? REC_TYPE_SORT + : line.lastIndexOf("aligned=", 0) === 0 ? REC_TYPE_ALIGNED : line.lastIndexOf("dumpOne", 0) === 0 ? REC_TYPE_SORT : line.lastIndexOf("findTop", 0) === 0 ? REC_TYPE_TOP : line.lastIndexOf("pathB.", 0) === 0 ? REC_TYPE_ADD @@ -649,6 +766,13 @@ function parse_all(test) { || match_regexp(line, lineNo, record, PATH_CONIC, "afterPart CONIC_VAL") || match_regexp(line, lineNo, record, PATH_CUBIC, "afterPart CUBIC_VAL") break; + case REC_TYPE_ALIGNED: + found = match_regexp(line, lineNo, record, PATH_LINE, "aligned=IDX LINE_VAL" + ) || match_regexp(line, lineNo, record, PATH_QUAD, "aligned=IDX QUAD_VAL" + ) || match_regexp(line, lineNo, record, PATH_CONIC, "aligned=IDX CONIC_VAL" + ) || match_regexp(line, lineNo, record, PATH_CUBIC, "aligned=IDX CUBIC_VAL" + ); + break; case REC_TYPE_ANGLE: found = match_regexp(line, lineNo, record, ANGLE_AFTER, "after " + "[IDX/IDX] NUM/NUM tStart=T_VAL tEnd=T_VAL < [IDX/IDX] NUM/NUM tStart=T_VAL tEnd=T_VAL < [IDX/IDX] NUM/NUM tStart=T_VAL tEnd=T_VAL T_F IDX"); @@ -868,7 +992,7 @@ function init(test) { xmax = -Infinity; ymin = Infinity; ymax = -Infinity; - hasPath = hasComputedPath = false; + hasPath = hasAlignedPath = hasComputedPath = false; firstActiveSpan = -1; for (var tIndex = 0; tIndex < test.length; tIndex += 3) { var recType = test[tIndex]; @@ -889,11 +1013,15 @@ function init(test) { var first2 = 0; var last2 = 0; switch (recType) { + case REC_TYPE_ALIGNED: + hasAlignedPath = true; case REC_TYPE_COMPUTED: if (fragType == COMPUTED_SET_1 || fragType == COMPUTED_SET_2) { break; } - hasComputedPath = true; + if (REC_TYPE_COMPUTED == recType) { + hasComputedPath = true; + } case REC_TYPE_PATH: first = 1; switch (fragType) { @@ -1187,14 +1315,14 @@ function init(test) { } } -function curveByID(test, id) { +function curveByIDMatch(test, id, recMatch) { var tIndex = -3; while ((tIndex += 3) < test.length) { var recType = test[tIndex]; if (recType == REC_TYPE_OP) { continue; } - if (recType != REC_TYPE_PATH) { + if (recType != recMatch) { return []; } var records = test[tIndex + 2]; @@ -1221,14 +1349,22 @@ function curveByID(test, id) { return []; } -function curvePartialByID(test, id, t0, t1) { +function curveByID(test, id) { + var result = draw_path >= 4 ? curveByIDMatch(test, id, REC_TYPE_ALIGNED) : []; + if (!result.length) { + result = curveByIDMatch(test, id, REC_TYPE_PATH); + } + return result; +} + +function curvePartialByIDMatch(test, id, t0, t1, recMatch) { var tIndex = -3; while ((tIndex += 3) < test.length) { var recType = test[tIndex]; if (recType == REC_TYPE_OP) { continue; } - if (recType != REC_TYPE_PATH) { + if (recType != recMatch) { return []; } var records = test[tIndex + 2]; @@ -1255,11 +1391,19 @@ function curvePartialByID(test, id, t0, t1) { return []; } -function idByCurve(test, frag, type) { +function curvePartialByID(test, id, t0, t1) { + var result = draw_path >= 4 ? curvePartialByIDMatch(test, id, t0, t1, REC_TYPE_ALIGNED) : []; + if (!result.length) { + result = curvePartialByIDMatch(test, id, t0, t1, REC_TYPE_PATH); + } + return result; +} + +function idByCurveIDMatch(test, frag, type, recMatch) { var tIndex = 0; while (tIndex < test.length) { var recType = test[tIndex]; - if (recType != REC_TYPE_PATH) { + if (recType != recMatch) { ++tIndex; continue; } @@ -1307,6 +1451,14 @@ function idByCurve(test, frag, type) { return -1; } +function idByCurve(test, frag, type) { + var result = draw_path >= 4 ? idByCurveIDMatch(test, frag, type, REC_TYPE_ALIGNED) : []; + if (!result.length) { + result = idByCurveIDMatch(test, frag, type, REC_TYPE_PATH); + } + return result; +} + function curve_extremes(curve, bounds) { var length = curve.length == 7 ? 6 : curve.length; for (var index = 0; index < curve.length; index += 2) { @@ -2708,8 +2860,15 @@ function draw(test, lines, title) { } drawCurveSpecials(test, frags, fragType); break; + case REC_TYPE_ALIGNED: + if (draw_path < 4) { + continue; + } case REC_TYPE_PATH: case REC_TYPE_PATH2: + if (REC_TYPE_ALIGNED != recType && draw_path >= 4) { + continue; + } if (!draw_path) { continue; } @@ -2742,7 +2901,7 @@ function draw(test, lines, title) { frags2[4], frags2[5], frags2[6], frags2[7]); break; default: - console.log("unknown REC_TYPE_PATH2 frag type: " + fragType); + console.log("unknown " + recType + " frag type: " + fragType); throw "stop execution"; } if (collect_bounds) { @@ -3407,7 +3566,7 @@ function draw(test, lines, title) { drawBox(pos++, "rgba(127,127,0, 0.3)", "black", draw_top ? topCount : topMax, draw_top, topKey); drawBox(pos++, "rgba(127,0,127, 0.3)", "black", draw_mark ? markCount : markMax, draw_mark, markKey); drawBox(pos++, "black", "white", - (new Array('P', 'P1', 'P2', 'P'))[draw_path], draw_path != 0, pathKey); + (new Array('P', 'P1', 'P2', 'P', 'p', 'p1', 'p2'))[draw_path], draw_path != 0, pathKey); drawBox(pos++, "rgba(0,63,0, 0.7)", "white", (new Array('Q', 'Q', 'C', 'QC', 'Qc', 'Cq'))[draw_computed], draw_computed != 0, computedKey); @@ -3734,11 +3893,11 @@ function doKeyPress(evt) { redraw(); break; case pathKey: - draw_path = (draw_path + 1) % 4; + draw_path = (draw_path + 1) % (4 + (hasAlignedPath ? 3 : 0)); redraw(); break; case pathBackKey: - draw_path = (draw_path + 3) % 4; + draw_path = (draw_path + 3 + (hasAlignedPath ? 3 : 0)) % (4 + (hasAlignedPath ? 3 : 0)); redraw(); break; case ptsKey: |