/* * Copyright 2013 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #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 #if DEBUG_SORT int SkPathOpsDebug::gSortCountDefault = SK_MaxS32; int SkPathOpsDebug::gSortCount; #endif #if DEBUG_ACTIVE_OP const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"}; #endif #if defined SK_DEBUG || !FORCE_RELEASE const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"}; int SkPathOpsDebug::gContourID = 0; int SkPathOpsDebug::gSegmentID = 0; bool SkPathOpsDebug::ChaseContains(const SkTDArray& chaseArray, const SkOpSpanBase* span) { for (int index = 0; index < chaseArray.count(); ++index) { const SkOpSpanBase* entry = chaseArray[index]; if (entry == span) { return true; } } 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 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; for (size_t idx = 0; idx < len; ++idx) { if (num && str[idx] == 'e') { if (len + 2 >= bufferLen) { return; } memmove(&str[idx + 2], &str[idx + 1], len - idx); str[idx] = '*'; str[idx + 1] = '^'; ++len; } num = str[idx] >= '0' && str[idx] <= '9'; } } bool SkPathOpsDebug::ValidWind(int wind) { return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF; } void SkPathOpsDebug::WindingPrintf(int wind) { if (wind == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", wind); } } #endif // defined SK_DEBUG || !FORCE_RELEASE #if DEBUG_SHOW_TEST_NAME void* SkPathOpsDebug::CreateNameStr() { return new char[DEBUG_FILENAME_STRING_LENGTH]; } void SkPathOpsDebug::DeleteNameStr(void* v) { delete[] reinterpret_cast(v); } void SkPathOpsDebug::BumpTestName(char* test) { char* num = test + strlen(test); while (num[-1] >= '0' && num[-1] <= '9') { --num; } if (num[0] == '\0') { return; } int dec = atoi(num); if (dec == 0) { return; } ++dec; SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec); } #endif static void show_function_header(const char* functionName) { SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName); if (strcmp("skphealth_com76", functionName) == 0) { SkDebugf("found it\n"); } } static const char* gOpStrs[] = { "kDifference_SkPathOp", "kIntersect_SkPathOp", "kUnion_SkPathOp", "kXor_PathOp", "kReverseDifference_SkPathOp", }; const char* SkPathOpsDebug::OpStr(SkPathOp op) { return gOpStrs[op]; } static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) { SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]); SkDebugf("}\n"); } SK_DECLARE_STATIC_MUTEX(gTestMutex); void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp, const char* testName) { SkAutoMutexAcquire ac(gTestMutex); show_function_header(testName); ShowOnePath(a, "path", true); ShowOnePath(b, "pathB", true); show_op(shapeOp, "path", "pathB"); } #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 { #if DEBUG_VALIDATE return FLAGS_runFail; #else return false; #endif } #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" SkDCubic SkDQuad::debugToCubic() const { SkDCubic cubic; cubic[0] = fPts[0]; cubic[2] = fPts[1]; cubic[3] = fPts[2]; cubic[1].fX = (cubic[0].fX + cubic[2].fX * 2) / 3; cubic[1].fY = (cubic[0].fY + cubic[2].fY * 2) / 3; cubic[2].fX = (cubic[3].fX + cubic[2].fX * 2) / 3; cubic[2].fY = (cubic[3].fY + cubic[2].fY * 2) / 3; return cubic; } void SkDRect::debugInit() { fLeft = fTop = fRight = fBottom = SK_ScalarNaN; } #include "SkOpAngle.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(); do { if (span->toAngle()) { SkASSERT(!result); result = span->toAngle(); } } while ((span = span->next()->upCastable())); SkASSERT(result); 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()); } #if DEBUG_ACTIVE_SPANS void SkOpSegment::debugShowActiveSpans() const { debugValidate(); if (done()) { return; } int lastId = -1; double lastT = -1; const SkOpSpan* span = &fHead; do { if (span->done()) { continue; } if (lastId == this->debugID() && lastT == span->t()) { continue; } lastId = this->debugID(); lastT = span->t(); SkDebugf("%s id=%d", __FUNCTION__, this->debugID()); SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); } if (SkPath::kConic_Verb == fVerb) { SkDebugf(" %1.9gf", fWeight); } const SkOpPtT* ptT = span->ptT(); SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY); SkDebugf(" tEnd=%1.9g", span->next()->t()); if (span->windSum() == SK_MinS32) { SkDebugf(" windSum=?"); } else { SkDebugf(" windSum=%d", span->windSum()); } if (span->oppValue() && span->oppSum() == SK_MinS32) { SkDebugf(" oppSum=?"); } else if (span->oppValue() || span->oppSum() != SK_MinS32) { SkDebugf(" oppSum=%d", span->oppSum()); } SkDebugf(" windValue=%d", span->windValue()); if (span->oppValue() || span->oppSum() != SK_MinS32) { SkDebugf(" oppValue=%d", span->oppValue()); } SkDebugf("\n"); } while ((span = span->next()->upCastable())); } #endif #if DEBUG_MARK_DONE void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) { const SkPoint& pt = span->ptT()->fPt; SkDebugf("%s id=%d", fun, this->debugID()); SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); } SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=", span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t()); if (winding == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", winding); } SkDebugf(" windSum="); if (span->windSum() == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", span->windSum()); } SkDebugf(" windValue=%d\n", span->windValue()); } void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding) { const SkPoint& pt = span->ptT()->fPt; SkDebugf("%s id=%d", fun, this->debugID()); SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) { SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); } SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=", span->t(), span->debugID(), pt.fX, pt.fY, span->next()->t(), winding, oppWinding); if (winding == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", winding); } SkDebugf(" newOppSum="); if (oppWinding == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", oppWinding); } SkDebugf(" oppSum="); if (span->oppSum() == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", span->oppSum()); } SkDebugf(" windSum="); if (span->windSum() == SK_MinS32) { SkDebugf("?"); } else { SkDebugf("%d", span->windSum()); } SkDebugf(" windValue=%d oppValue=%d\n", span->windValue(), span->oppValue()); } #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; switch (this->segment()->verb()) { case SkPath::kLine_Verb: result.printf(LINE_DEBUG_STR " id=%d", LINE_DEBUG_DATA(fCurvePart), this->segment()->debugID()); break; case SkPath::kQuad_Verb: result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart), this->segment()->debugID()); break; case SkPath::kConic_Verb: result.printf(CONIC_DEBUG_STR " id=%d", CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight), this->segment()->debugID()); break; case SkPath::kCubic_Verb: result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart), this->segment()->debugID()); break; default: SkASSERT(0); } return result; } #endif #if DEBUG_SORT void SkOpAngle::debugLoop() const { const SkOpAngle* first = this; const SkOpAngle* next = this; do { next->dumpOne(true); SkDebugf("\n"); next = next->fNext; } while (next && next != first); next = first; do { next->debugValidate(); next = next->fNext; } while (next && next != first); } #endif void SkOpAngle::debugValidate() const { #if DEBUG_VALIDATE const SkOpAngle* first = this; const SkOpAngle* next = this; int wind = 0; int opp = 0; int lastXor = -1; int lastOppXor = -1; do { if (next->unorderable()) { return; } const SkOpSpan* minSpan = next->start()->starter(next->end()); if (minSpan->windValue() == SK_MinS32) { return; } bool op = next->segment()->operand(); bool isXor = next->segment()->isXor(); bool oppXor = next->segment()->oppXor(); SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(0, minSpan->windValue(), DEBUG_LIMIT_WIND_SUM)); SkASSERT(!DEBUG_LIMIT_WIND_SUM || between(-DEBUG_LIMIT_WIND_SUM, minSpan->oppValue(), DEBUG_LIMIT_WIND_SUM)); bool useXor = op ? oppXor : isXor; SkASSERT(lastXor == -1 || lastXor == (int) useXor); lastXor = (int) useXor; wind += next->debugSign() * (op ? minSpan->oppValue() : minSpan->windValue()); if (useXor) { wind &= 1; } useXor = op ? isXor : oppXor; SkASSERT(lastOppXor == -1 || lastOppXor == (int) useXor); lastOppXor = (int) useXor; opp += next->debugSign() * (op ? minSpan->windValue() : minSpan->oppValue()); if (useXor) { opp &= 1; } next = next->fNext; } while (next && next != first); SkASSERT(wind == 0 || !FLAGS_runFail); SkASSERT(opp == 0 || !FLAGS_runFail); #endif } void SkOpAngle::debugValidateNext() const { #if !FORCE_RELEASE const SkOpAngle* first = this; const SkOpAngle* next = first; SkTDArray(angles); do { // SK_ALWAYSBREAK(next->fSegment->debugContains(next)); angles.push(next); next = next->next(); if (next == first) { break; } SK_ALWAYSBREAK(!angles.contains(next)); if (!next) { return; } } while (true); #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; } if (!coin) { return; } 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) { SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, span->fCoinPtTStart->segment()->debugID(), span->fCoinPtTStart->fT, span->fCoinPtTEnd->fT); SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__, span->fOppPtTStart->segment()->debugID(), span->fOppPtTStart->fT, span->fOppPtTEnd->fT); span = span->fNext; } } #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; double lastT = -1; const SkOpSpanBase* prev = nullptr; int count = 0; int done = 0; do { if (!span->final()) { ++count; done += span->upCast()->done() ? 1 : 0; } SkASSERT(span->segment() == this); SkASSERT(!prev || prev->upCast()->next() == span); SkASSERT(!prev || prev == span->prev()); prev = span; double t = span->ptT()->fT; SkASSERT(lastT < t); lastT = t; span->debugValidate(); } while (!span->final() && (span = span->upCast()->next())); SkASSERT(count == fCount); SkASSERT(done == fDoneCount); SkASSERT(count >= fDoneCount); SkASSERT(span->final()); span->debugValidate(); #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; SkOpSpanBase* nextCoin; do { nextCoin = next->fCoinEnd; SkASSERT(nextCoin == this || nextCoin->fCoinEnd != nextCoin); for (int check = 1; check < loop - 1; ++check) { const SkOpSpanBase* checkCoin = this->fCoinEnd; const SkOpSpanBase* innerCoin = checkCoin; for (int inner = check + 1; inner < loop; ++inner) { innerCoin = innerCoin->fCoinEnd; if (checkCoin == innerCoin) { SkDebugf("*** bad coincident end loop ***\n"); return false; } } } ++loop; } while ((next = nextCoin) && next != this); 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; SkASSERT(ptT->span() == this); do { // SkASSERT(SkDPoint::RoughlyEqual(fPtT.fPt, ptT->fPt)); ptT->debugValidate(); ptT = ptT->next(); } while (ptT != &fPtT); SkASSERT(this->debugCoinEndLoopCheck()); if (!this->final()) { SkASSERT(this->upCast()->debugCoinLoopCheck()); } if (fFromAngle) { fFromAngle->debugValidate(); } if (!this->final() && this->upCast()->toAngle()) { this->upCast()->toAngle()->debugValidate(); } #endif } bool SkOpSpan::debugCoinLoopCheck() const { int loop = 0; const SkOpSpan* next = this; SkOpSpan* nextCoin; do { nextCoin = next->fCoincident; SkASSERT(nextCoin == this || nextCoin->fCoincident != nextCoin); for (int check = 1; check < loop - 1; ++check) { const SkOpSpan* checkCoin = this->fCoincident; const SkOpSpan* innerCoin = checkCoin; for (int inner = check + 1; inner < loop; ++inner) { innerCoin = innerCoin->fCoincident; if (checkCoin == innerCoin) { SkDebugf("*** bad coincident loop ***\n"); return false; } } } ++loop; } while ((next = nextCoin) && next != this); return true; } // called only by test code int SkIntersections::debugCoincidentUsed() const { if (!fIsCoincident[0]) { SkASSERT(!fIsCoincident[1]); return 0; } int count = 0; SkDEBUGCODE(int count2 = 0;) for (int index = 0; index < fUsed; ++index) { if (fIsCoincident[0] & (1 << index)) { ++count; } #ifdef SK_DEBUG if (fIsCoincident[1] & (1 << index)) { ++count2; } #endif } SkASSERT(count == count2); return count; } #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; do { for (int check = 1; check < loop - 1; ++check) { const SkOpPtT* checkPtT = this->fNext; const SkOpPtT* innerPtT = checkPtT; for (int inner = check + 1; inner < loop; ++inner) { innerPtT = innerPtT->fNext; if (checkPtT == innerPtT) { if (report) { SkDebugf("*** bad ptT loop ***\n"); } return 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; } void SkOpPtT::debugValidate() const { #if DEBUG_VALIDATE SkOpGlobalState::Phase phase = contour()->globalState()->phase(); if (phase == SkOpGlobalState::kIntersecting || phase == SkOpGlobalState::kFixWinding) { return; } SkASSERT(fNext); SkASSERT(fNext != this); SkASSERT(fNext->fNext); SkASSERT(debugLoopLimit(false) == 0); #endif } static void output_scalar(SkScalar num) { if (num == (int) num) { SkDebugf("%d", (int) num); } else { SkString str; str.printf("%1.9g", num); int width = (int) str.size(); const char* cStr = str.c_str(); while (cStr[width - 1] == '0') { --width; } str.resize(width); SkDebugf("%sf", str.c_str()); } } static void output_points(const SkPoint* pts, int count) { for (int index = 0; index < count; ++index) { output_scalar(pts[index].fX); SkDebugf(", "); output_scalar(pts[index].fY); if (index + 1 < count) { SkDebugf(", "); } } } static void showPathContours(SkPath::RawIter& iter, const char* pathName) { uint8_t verb; SkPoint pts[4]; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: SkDebugf(" %s.moveTo(", pathName); output_points(&pts[0], 1); SkDebugf(");\n"); continue; case SkPath::kLine_Verb: SkDebugf(" %s.lineTo(", pathName); output_points(&pts[1], 1); SkDebugf(");\n"); break; case SkPath::kQuad_Verb: SkDebugf(" %s.quadTo(", pathName); output_points(&pts[1], 2); SkDebugf(");\n"); break; case SkPath::kConic_Verb: SkDebugf(" %s.conicTo(", pathName); output_points(&pts[1], 2); SkDebugf(", %1.9gf);\n", iter.conicWeight()); break; case SkPath::kCubic_Verb: SkDebugf(" %s.cubicTo(", pathName); output_points(&pts[1], 3); SkDebugf(");\n"); break; case SkPath::kClose_Verb: SkDebugf(" %s.close();\n", pathName); break; default: SkDEBUGFAIL("bad verb"); return; } } } static const char* gFillTypeStr[] = { "kWinding_FillType", "kEvenOdd_FillType", "kInverseWinding_FillType", "kInverseEvenOdd_FillType" }; void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) { SkPath::RawIter iter(path); #define SUPPORT_RECT_CONTOUR_DETECTION 0 #if SUPPORT_RECT_CONTOUR_DETECTION int rectCount = path.isRectContours() ? path.rectContours(nullptr, nullptr) : 0; if (rectCount > 0) { SkTDArray rects; SkTDArray directions; rects.setCount(rectCount); directions.setCount(rectCount); path.rectContours(rects.begin(), directions.begin()); for (int contour = 0; contour < rectCount; ++contour) { const SkRect& rect = rects[contour]; SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction"); } return; } #endif SkPath::FillType fillType = path.getFillType(); SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType); if (includeDeclaration) { SkDebugf(" SkPath %s;\n", name); } SkDebugf(" %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]); iter.setPath(path); showPathContours(iter, name); }