Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1920)

Unified Diff: src/pathops/SkPathOpsDebug.cpp

Issue 2128633003: pathops coincidence and security rewrite (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: require resulting t to be between 0 and 1 Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: src/pathops/SkPathOpsDebug.cpp
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 546771e84c6be240e75837dd83f1707bd799e6ec..93743f3d6cfc3f8a18ab75ac0f5332e10d9bc206 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -12,7 +12,7 @@
#include "SkPathOpsDebug.h"
#include "SkString.h"
-struct SkCoincidentSpans;
+class SkCoincidentSpans;
#if DEBUG_VALIDATE
extern bool FLAGS_runFail;
@@ -46,11 +46,15 @@ bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpanBase* >& chaseArray,
}
#endif
-#if DEBUG_COINCIDENCE
+#if DEBUG_COINCIDENCE_VERBOSE
enum GlitchType {
kAddCorruptCoin_Glitch,
kAddExpandedCoin_Glitch,
+ kAddExpandedFail_Glitch,
+ kAddIfMissingCoin_Glitch,
kAddMissingCoin_Glitch,
+ kAddMissingExtend_Glitch,
+ kAddOrOverlap_Glitch,
kCollapsedCoin_Glitch,
kCollapsedDone_Glitch,
kCollapsedOppValue_Glitch,
@@ -60,30 +64,41 @@ enum GlitchType {
kExpandCoin_Glitch,
kMarkCoinEnd_Glitch,
kMarkCoinInsert_Glitch,
+ kMarkCoinMissing_Glitch,
+ kMarkCoinStart_Glitch,
+ kMergeContained_Glitch,
kMissingCoin_Glitch,
kMissingDone_Glitch,
kMissingIntersection_Glitch,
kMoveMultiple_Glitch,
+ kMoveNearbyClearAll_Glitch,
+ kMoveNearbyClearAll2_Glitch,
+ kMoveNearbyMerge_Glitch,
+ kMoveNearbyMergeFinal_Glitch,
+ kMoveNearbyRelease_Glitch,
+ kMoveNearbyReleaseFinal_Glitch,
+ kReleasedSpan_Glitch,
kUnaligned_Glitch,
kUnalignedHead_Glitch,
kUnalignedTail_Glitch,
- kUndetachedSpan_Glitch,
- kUnmergedSpan_Glitch,
};
-static const int kGlitchType_Count = kUnmergedSpan_Glitch + 1;
+static const int kGlitchType_Count = kUnalignedTail_Glitch + 1;
struct SpanGlitch {
const char* fStage;
const SkOpSpanBase* fBase;
const SkOpSpanBase* fSuspect;
- const SkCoincidentSpans* fCoin;
const SkOpSegment* fSegment;
+ const SkOpSegment* fOppSegment;
const SkOpPtT* fCoinSpan;
const SkOpPtT* fEndSpan;
const SkOpPtT* fOppSpan;
const SkOpPtT* fOppEndSpan;
- double fT;
+ double fStartT;
+ double fEndT;
+ double fOppStartT;
+ double fOppEndT;
SkPoint fPt;
GlitchType fType;
};
@@ -94,13 +109,16 @@ struct SkPathOpsDebug::GlitchLog {
glitch->fStage = stage;
glitch->fBase = nullptr;
glitch->fSuspect = nullptr;
- glitch->fCoin = nullptr;
glitch->fSegment = nullptr;
+ glitch->fOppSegment = nullptr;
glitch->fCoinSpan = nullptr;
glitch->fEndSpan = nullptr;
glitch->fOppSpan = nullptr;
glitch->fOppEndSpan = nullptr;
- glitch->fT = SK_ScalarNaN;
+ glitch->fStartT = SK_ScalarNaN;
+ glitch->fEndT = SK_ScalarNaN;
+ glitch->fOppStartT = SK_ScalarNaN;
+ glitch->fOppEndT = SK_ScalarNaN;
glitch->fPt = { SK_ScalarNaN, SK_ScalarNaN };
glitch->fType = type;
return glitch;
@@ -113,11 +131,22 @@ struct SkPathOpsDebug::GlitchLog {
glitch->fSuspect = suspect;
}
+ void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
+ const SkOpPtT* ptT) {
+ SpanGlitch* glitch = recordCommon(type, stage);
+ glitch->fBase = base;
+ glitch->fCoinSpan = ptT;
+ }
+
void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
- const SkOpPtT* coinSpan) {
+ const SkCoincidentSpans* opp = NULL) {
SpanGlitch* glitch = recordCommon(type, stage);
- glitch->fCoin = coin;
- glitch->fCoinSpan = coinSpan;
+ glitch->fCoinSpan = coin->coinPtTStart();
+ glitch->fEndSpan = coin->coinPtTEnd();
+ if (opp) {
+ glitch->fOppSpan = opp->coinPtTStart();
+ glitch->fOppEndSpan = opp->coinPtTEnd();
+ }
}
void record(GlitchType type, const char* stage, const SkOpSpanBase* base,
@@ -125,7 +154,7 @@ struct SkPathOpsDebug::GlitchLog {
SpanGlitch* glitch = recordCommon(type, stage);
glitch->fBase = base;
glitch->fSegment = seg;
- glitch->fT = t;
+ glitch->fStartT = t;
glitch->fPt = pt;
}
@@ -133,23 +162,26 @@ struct SkPathOpsDebug::GlitchLog {
SkPoint pt) {
SpanGlitch* glitch = recordCommon(type, stage);
glitch->fBase = base;
- glitch->fT = t;
+ glitch->fStartT = 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->fCoinSpan = coin->coinPtTStart();
+ glitch->fEndSpan = coin->coinPtTEnd();
glitch->fEndSpan = endSpan;
+ glitch->fOppSpan = coinSpan;
+ glitch->fOppEndSpan = endSpan;
}
void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
- const SkOpSpanBase* suspect) {
+ const SkOpSpanBase* base) {
SpanGlitch* glitch = recordCommon(type, stage);
- glitch->fSuspect = suspect;
- glitch->fCoin = coin;
+ glitch->fBase = base;
+ glitch->fCoinSpan = coin->coinPtTStart();
+ glitch->fEndSpan = coin->coinPtTEnd();
}
void record(GlitchType type, const char* stage, const SkOpPtT* ptTS, const SkOpPtT* ptTE,
@@ -161,22 +193,73 @@ struct SkPathOpsDebug::GlitchLog {
glitch->fOppEndSpan = oPtTE;
}
+ void record(GlitchType type, const char* stage, const SkOpSegment* seg, double startT,
+ double endT, const SkOpSegment* oppSeg, double oppStartT, double oppEndT) {
+ SpanGlitch* glitch = recordCommon(type, stage);
+ glitch->fSegment = seg;
+ glitch->fStartT = startT;
+ glitch->fEndT = endT;
+ glitch->fOppSegment = oppSeg;
+ glitch->fOppStartT = oppStartT;
+ glitch->fOppEndT = oppEndT;
+ }
+
+ void record(GlitchType type, const char* stage, const SkOpSegment* seg,
+ const SkOpSpan* span) {
+ SpanGlitch* glitch = recordCommon(type, stage);
+ glitch->fSegment = seg;
+ glitch->fBase = span;
+ }
+
+ void record(GlitchType type, const char* stage, double t, const SkOpSpanBase* span) {
+ SpanGlitch* glitch = recordCommon(type, stage);
+ glitch->fStartT = t;
+ glitch->fBase = span;
+ }
+
+ void record(GlitchType type, const char* stage, const SkOpSegment* seg) {
+ SpanGlitch* glitch = recordCommon(type, stage);
+ glitch->fSegment = seg;
+ }
+
+ void record(GlitchType type, const char* stage, const SkCoincidentSpans* coin,
+ const SkOpPtT* ptT) {
+ SpanGlitch* glitch = recordCommon(type, stage);
+ glitch->fCoinSpan = coin->coinPtTStart();
+ glitch->fEndSpan = ptT;
+ }
+
SkTDArray<SpanGlitch> fGlitches;
};
+#endif
+void SkPathOpsDebug::ShowActiveSpans(SkOpContourHead* contourList) {
+#if DEBUG_ACTIVE_SPANS
+ SkOpContour* contour = contourList;
+ do {
+ contour->debugShowActiveSpans();
+ } while ((contour = contour->next()));
+#endif
+}
+
+#if DEBUG_COINCIDENCE
void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
+ contourList->globalState()->debugSetCheckHealth(true);
+#if DEBUG_COINCIDENCE_VERBOSE
GlitchLog glitches;
const SkOpContour* contour = contourList;
const SkOpCoincidence* coincidence = contour->globalState()->coincidence();
+ coincidence->debugCheckValid(id, &glitches); // don't call validate; spans may be inconsistent
do {
contour->debugCheckHealth(id, &glitches);
- contour->debugMissingCoincidence(id, &glitches, coincidence);
+ contour->debugMissingCoincidence(id, &glitches);
} while ((contour = contour->next()));
- coincidence->debugFixAligned(id, &glitches);
+ coincidence->debugRemoveCollapsed(id, &glitches);
coincidence->debugAddMissing(id, &glitches);
coincidence->debugExpand(id, &glitches);
coincidence->debugAddExpanded(id, &glitches);
coincidence->debugMark(id, &glitches);
+ coincidence->debugReorder(id, &glitches);
unsigned mask = 0;
for (int index = 0; index < glitches.fGlitches.count(); ++index) {
const SpanGlitch& glitch = glitches.fGlitches[index];
@@ -186,6 +269,92 @@ void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
SkDebugf(mask & (1 << index) ? "x" : "-");
}
SkDebugf(" %s\n", id);
+ for (int index = 0; index < glitches.fGlitches.count(); ++index) {
+ const SpanGlitch& glitch = glitches.fGlitches[index];
+ SkDebugf("%02d: ", index);
+ if (glitch.fBase) {
+ SkDebugf(" base=%d", glitch.fBase->debugID());
+ }
+ if (glitch.fSuspect) {
+ SkDebugf(" base=%d", glitch.fSuspect->debugID());
+ }
+ if (glitch.fSegment) {
+ SkDebugf(" segment=%d", glitch.fSegment->debugID());
+ }
+ if (glitch.fCoinSpan) {
+ SkDebugf(" coinSpan=%d", glitch.fCoinSpan->debugID());
+ }
+ if (glitch.fEndSpan) {
+ SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
+ }
+ if (glitch.fOppSpan) {
+ SkDebugf(" oppSpan=%d", glitch.fOppSpan->debugID());
+ }
+ if (glitch.fOppEndSpan) {
+ SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
+ }
+ if (!SkScalarIsNaN(glitch.fStartT)) {
+ SkDebugf(" startT=%g", glitch.fStartT);
+ }
+ if (!SkScalarIsNaN(glitch.fEndT)) {
+ SkDebugf(" endT=%g", glitch.fEndT);
+ }
+ if (glitch.fOppSegment) {
+ SkDebugf(" segment=%d", glitch.fOppSegment->debugID());
+ }
+ if (!SkScalarIsNaN(glitch.fOppStartT)) {
+ SkDebugf(" oppStartT=%g", glitch.fOppStartT);
+ }
+ if (!SkScalarIsNaN(glitch.fOppEndT)) {
+ SkDebugf(" oppEndT=%g", glitch.fOppEndT);
+ }
+ if (!SkScalarIsNaN(glitch.fPt.fX) || !SkScalarIsNaN(glitch.fPt.fY)) {
+ SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY);
+ }
+ switch (glitch.fType) {
+ case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
+ case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
+ case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
+ case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
+ case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
+ case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
+ case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break;
+ case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break;
+ case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break;
+ case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break;
+ case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break;
+ case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break;
+ case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break;
+ case kExpandCoin_Glitch: SkDebugf(" ExpandCoin"); break;
+ case kMarkCoinEnd_Glitch: SkDebugf(" MarkCoinEnd"); break;
+ case kMarkCoinInsert_Glitch: SkDebugf(" MarkCoinInsert"); break;
+ case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break;
+ case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break;
+ case kMergeContained_Glitch: SkDebugf(" MergeContained"); break;
+ case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break;
+ case kMissingDone_Glitch: SkDebugf(" MissingDone"); break;
+ case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break;
+ case kMoveMultiple_Glitch: SkDebugf(" MoveMultiple"); break;
+ case kMoveNearbyClearAll_Glitch: SkDebugf(" MoveNearbyClearAll"); break;
+ case kMoveNearbyClearAll2_Glitch: SkDebugf(" MoveNearbyClearAll2"); break;
+ case kMoveNearbyMerge_Glitch: SkDebugf(" MoveNearbyMerge"); break;
+ case kMoveNearbyMergeFinal_Glitch: SkDebugf(" MoveNearbyMergeFinal"); break;
+ case kMoveNearbyRelease_Glitch: SkDebugf(" MoveNearbyRelease"); break;
+ case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break;
+ case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break;
+ case kUnaligned_Glitch: SkDebugf(" Unaligned"); break;
+ case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break;
+ case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break;
+ default: SkASSERT(0);
+ }
+ SkDebugf("\n");
+ }
+ contourList->globalState()->debugSetCheckHealth(false);
+#if DEBUG_ACTIVE_SPANS
+ SkDebugf("active after %s:\n", id);
+ ShowActiveSpans(contourList);
+#endif
+#endif
}
#endif
@@ -254,7 +423,7 @@ static const char* gOpStrs[] = {
"kDifference_SkPathOp",
"kIntersect_SkPathOp",
"kUnion_SkPathOp",
- "kXor_PathOp",
+ "kXOR_PathOp",
"kReverseDifference_SkPathOp",
};
@@ -412,132 +581,72 @@ void SkDRect::debugInit() {
#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;
+// commented-out lines keep this in sync with addT()
+ const SkOpPtT* SkOpSegment::debugAddT(double t, AliasMatch allowAlias, bool* allocated) const {
+ debugValidate();
+ SkPoint pt = this->ptAtT(t);
+ const SkOpSpanBase* span = &fHead;
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();
+ const SkOpPtT* result = span->ptT();
+ const SkOpPtT* loop;
+ bool duplicatePt;
+ if (t == result->fT) {
+ goto bumpSpan;
+ }
+ if (this->match(result, this, t, pt, allowAlias)) {
+ // see if any existing alias matches segment, pt, and t
+ loop = result->next();
+ duplicatePt = false;
+ while (loop != result) {
+ bool ptMatch = loop->fPt == pt;
+ if (loop->segment() == this && loop->fT == t && ptMatch) {
+ goto bumpSpan;
}
- log->record(kMissingIntersection_Glitch, id, checkSpan, segment, i[0][0], newPt);
+ duplicatePt |= ptMatch;
+ loop = loop->next();
}
- 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;
+ if (kNoAliasMatch == allowAlias) {
+ bumpSpan:
+// span->bumpSpanAdds();
+ return result;
}
- 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);
+// SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator);
+// alias->init(result->span(), t, pt, duplicatePt);
+// result->insert(alias);
+// result->span()->unaligned();
+ this->debugValidate();
+// #if DEBUG_ADD_T
+// SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
+// alias->segment()->debugID(), alias->span()->debugID());
+// #endif
+// span->bumpSpanAdds();
+ if (allocated) {
+ *allocated = true;
}
- if (span->oppValue()) {
- glitches->record(kCollapsedOppValue_Glitch, id, span);
+ return nullptr;
+ }
+ if (t < result->fT) {
+ const SkOpSpan* prev = result->span()->prev();
+ if (!prev) {
+ return nullptr; // FIXME: this is a fail case; nullptr return elsewhere means result was allocated in non-const version
}
- if (!span->done()) {
- glitches->record(kCollapsedDone_Glitch, id, span);
+// SkOpSpan* span = insert(prev, allocator);
+// span->init(this, prev, t, pt);
+ this->debugValidate();
+// #if DEBUG_ADD_T
+// SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
+// span->segment()->debugID(), span->debugID());
+// #endif
+// span->bumpSpanAdds();
+ if (allocated) {
+ *allocated = true;
}
- } while ((span = span->next()->upCastable()));
- }
+ return nullptr;
+ }
+ SkASSERT(span != &fTail);
+ } while ((span = span->upCast()->next()));
+ SkASSERT(0);
+ return nullptr;
}
#endif
@@ -547,7 +656,7 @@ void SkOpSegment::debugCheckAngleCoin() const {
const SkOpSpan* span;
do {
const SkOpAngle* angle = base->fromAngle();
- if (angle && angle->fCheckCoincidence) {
+ if (angle && angle->debugCheckCoincidence()) {
angle->debugCheckNearCoincidence();
}
if (base->final()) {
@@ -555,41 +664,35 @@ void SkOpSegment::debugCheckAngleCoin() const {
}
span = base->upCast();
angle = span->toAngle();
- if (angle && angle->fCheckCoincidence) {
+ if (angle && angle->debugCheckCoincidence()) {
angle->debugCheckNearCoincidence();
}
} while ((base = span->next()));
}
#endif
-#if DEBUG_COINCIDENCE
+#if DEBUG_COINCIDENCE_VERBOSE
// 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());
+ debugMissingCoincidence(id, glitches);
+}
+// commented-out lines keep this in sync with clearAll()
+void SkOpSegment::debugClearAll(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+ const SkOpSpan* span = &fHead;
+ do {
+ this->debugClearOne(span, id, glitches);
+ } while ((span = span->next()->upCastable()));
+ this->globalState()->coincidence()->debugRelease(id, glitches, this);
}
-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);
- }
- }
+// commented-out lines keep this in sync with clearOne()
+void SkOpSegment::debugClearOne(const SkOpSpan* span, const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+ 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);
}
#endif
@@ -607,16 +710,37 @@ SkOpAngle* SkOpSegment::debugLastAngle() {
}
#if DEBUG_COINCIDENCE
-void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
- const SkOpCoincidence* coincidences) const {
- if (this->verb() != SkPath::kLine_Verb) {
- return;
- }
+// commented-out lines keep this in sync with ClearVisited
+void SkOpSegment::DebugClearVisited(const SkOpSpanBase* span) {
+ // reset visited flag back to false
+ do {
+ const SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
+ while ((ptT = ptT->next()) != stopPtT) {
+ const SkOpSegment* opp = ptT->segment();
+ opp->resetDebugVisited();
+ }
+ } while (!span->final() && (span = span->upCast()->next()));
+}
+#endif
+
+#if DEBUG_COINCIDENCE_VERBOSE
+// commented-out lines keep this in sync with missingCoincidence()
+// look for pairs of undetected coincident curves
+// assumes that segments going in have visited flag clear
+// Even though pairs of curves correct detect coincident runs, a run may be missed
+// if the coincidence is a product of multiple intersections. For instance, given
+// curves A, B, and C:
+// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
+// the end of C that the intersection is replaced with the end of C.
+// Even though A-B correctly do not detect an intersection at point 2,
+// the resulting run from point 1 to point 2 is coincident on A and B.
+void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
if (this->done()) {
return;
}
const SkOpSpan* prior = nullptr;
const SkOpSpanBase* spanBase = &fHead;
+// bool result = false;
do {
const SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
SkASSERT(ptT->span() == spanBase);
@@ -624,29 +748,29 @@ void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::Glitch
if (ptT->deleted()) {
continue;
}
- SkOpSegment* opp = ptT->span()->segment();
-// if (opp->verb() == SkPath::kLine_Verb) {
-// continue;
-// }
+ const SkOpSegment* opp = ptT->span()->segment();
if (opp->done()) {
continue;
}
// when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
- if (!opp->visited()) {
+ if (!opp->debugVisited()) {
continue;
}
if (spanBase == &fHead) {
continue;
}
+ if (ptT->segment() == this) {
+ 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)) {
+ if (span && span->segment() != opp && span->containsCoincidence(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted
herb_g 2016/07/18 15:13:39 Comments on next line?
caryclark 2016/07/18 15:55:49 The crazy formatting here is so that SkOpSegment::
continue;
}
- if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) {
+ if (spanBase->segment() != opp && spanBase->containsCoinEnd(opp)) { // debug has additional condition since it may be called before inner duplicate points have been deleted
continue;
- }
+ }
const SkOpPtT* priorPtT = nullptr, * priorStopPtT;
// find prior span containing opp segment
const SkOpSegment* priorOpp = nullptr;
@@ -669,6 +793,9 @@ void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::Glitch
if (!priorOpp) {
continue;
}
+ if (priorPtT == ptT) {
+ continue;
+ }
const SkOpPtT* oppStart = prior->ptT();
const SkOpPtT* oppEnd = spanBase->ptT();
bool swapped = priorPtT->fT > ptT->fT;
@@ -676,22 +803,28 @@ void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::Glitch
SkTSwap(priorPtT, ptT);
SkTSwap(oppStart, oppEnd);
}
- bool flipped = oppStart->fT > oppEnd->fT;
- bool coincident = false;
- if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
+ const SkOpCoincidence* coincidence = this->globalState()->coincidence();
+ const SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
+ const SkOpPtT* rootPtT = ptT->span()->ptT();
+ const SkOpPtT* rootOppStart = oppStart->span()->ptT();
+ const SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
+ if (coincidence->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
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) {
+ if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
+ // mark coincidence
+#if DEBUG_COINCIDENCE
+// SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
herb_g 2016/07/18 15:13:39 Remove commented out code.
caryclark 2016/07/18 15:55:49 See above
+// rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
+// rootOppEnd->debugID());
+#endif
log->record(kMissingCoin_Glitch, id, priorPtT, ptT, oppStart, oppEnd);
+ // coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
+ // }
+#if DEBUG_COINCIDENCE
+// SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)
+#endif
+ // result = true;
}
swapBack:
if (swapped) {
@@ -699,9 +832,14 @@ void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::Glitch
}
}
} while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
+ DebugClearVisited(&fHead);
+ return;
}
+// commented-out lines keep this in sync with moveMultiples()
+// if a span has more than one intersection, merge the other segments' span as needed
void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
+ debugValidate();
const SkOpSpanBase* test = &fHead;
do {
int addCount = test->spanAddsCount();
@@ -777,6 +915,7 @@ void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog*
} while ((matchPtT = matchPtT->next()) != startPtT);
goto tryNextSpan;
foundMatch: // merge oppTest and oppSpan
+ oppSegment->debugValidate();
if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
SkASSERT(oppSpan != &oppSegment->fTail);
@@ -784,60 +923,67 @@ void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog*
} else {
glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
}
+ oppSegment->debugValidate();
goto checkNextSpan;
}
- tryNextSpan:
+ tryNextSpan:
;
} while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
} while ((testPtT = testPtT->next()) != startPtT);
-checkNextSpan:
+checkNextSpan:
;
} while ((test = test->final() ? nullptr : test->upCast()->next()));
+ debugValidate();
+ return;
}
+// commented-out lines keep this in sync with moveNearby()
+// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
void SkOpSegment::debugMoveNearby(const char* id, SkPathOpsDebug::GlitchLog* glitches) const {
- const SkOpSpanBase* spanS = &fHead;
+ debugValidate();
+ // release undeleted spans pointing to this seg that are linked to the primary span
+ const SkOpSpanBase* spanBase = &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);
+ const SkOpPtT* ptT = spanBase->ptT();
+ const SkOpPtT* headPtT = ptT;
+ while ((ptT = ptT->next()) != headPtT) {
+ const SkOpSpanBase* test = ptT->span();
+ if (ptT->segment() == this && !ptT->deleted() && test != spanBase
+ && test->ptT() == ptT) {
+ if (test->final()) {
+ if (spanBase == &fHead) {
+ glitches->record(kMoveNearbyClearAll_Glitch, id, this);
+// return;
herb_g 2016/07/18 15:13:39 Remove commented out code.
caryclark 2016/07/18 15:55:49 See comment above.
+ }
+ glitches->record(kMoveNearbyReleaseFinal_Glitch, id, spanBase, ptT);
+ } else if (test->prev()) {
+ glitches->record(kMoveNearbyRelease_Glitch, id, test, headPtT);
+ }
+// break;
}
}
- 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());
+ spanBase = spanBase->upCast()->next();
+ } while (!spanBase->final());
+
+ // This loop looks for adjacent spans which are near by
+ spanBase = &fHead;
+ do { // iterate through all spans associated with start
+ const SkOpSpanBase* test = spanBase->upCast()->next();
+ if (this->spansNearby(spanBase, test)) {
+ if (test->final()) {
+ if (spanBase->prev()) {
+ glitches->record(kMoveNearbyMergeFinal_Glitch, id, test);
+ } else {
+ glitches->record(kMoveNearbyClearAll2_Glitch, id, this);
+ // return
+ }
+ } else {
+ glitches->record(kMoveNearbyMerge_Glitch, id, spanBase);
+ }
+ }
+ spanBase = test;
+ } while (!spanBase->final());
+ debugValidate();
}
#endif
@@ -864,16 +1010,18 @@ void SkOpSegment::debugShowActiveSpans() const {
lastId = this->debugID();
lastT = span->t();
SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
- SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
+ // since endpoints may have be adjusted, show actual computed curves
+ SkDCurve curvePart;
+ this->subDivide(span, span->next(), &curvePart);
+ const SkDPoint* pts = curvePart.fCubic.fPts;
+ SkDebugf(" (%1.9g,%1.9g", pts[0].fX, pts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
- SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
+ SkDebugf(" %1.9g,%1.9g", pts[vIndex].fX, pts[vIndex].fY);
}
if (SkPath::kConic_Verb == fVerb) {
- SkDebugf(" %1.9gf", fWeight);
+ SkDebugf(" %1.9gf", curvePart.fConic.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());
+ SkDebugf(") t=%1.9g tEnd=%1.9g", span->t(), span->next()->t());
if (span->windSum() == SK_MinS32) {
SkDebugf(" windSum=?");
} else {
@@ -958,7 +1106,7 @@ void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int
// 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
+ This checks the distance between start points; the distance between
*/
#if DEBUG_ANGLE
void SkOpAngle::debugCheckNearCoincidence() const {
@@ -996,7 +1144,7 @@ void SkOpAngle::debugCheckNearCoincidence() const {
SkDebugf("\n");
}
test = test->fNext;
- } while (test->fNext != this);
+ } while (test->fNext != this);
}
#endif
@@ -1046,6 +1194,11 @@ void SkOpAngle::debugLoop() const {
#endif
void SkOpAngle::debugValidate() const {
+#if DEBUG_COINCIDENCE
+ if (this->globalState()->debugCheckHealth()) {
+ return;
+ }
+#endif
#if DEBUG_VALIDATE
const SkOpAngle* first = this;
const SkOpAngle* next = this;
@@ -1108,243 +1261,409 @@ void SkOpAngle::debugValidateNext() const {
#endif
}
+#ifdef SK_DEBUG
+void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
+ const SkOpGlobalState* debugState) const {
+ SkASSERT(coinPtTEnd()->span() == over || !debugState->debugRunFail());
+ SkASSERT(oppPtTEnd()->span() == outer || !debugState->debugRunFail());
+}
+#endif
-#if DEBUG_COINCIDENCE
+#if DEBUG_COINCIDENCE_VERBOSE
+/* Commented-out lines keep this in sync with expand */
+bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+ bool expanded = false;
+ const SkOpSegment* segment = coinPtTStart()->segment();
+ const SkOpSegment* oppSegment = oppPtTStart()->segment();
+ do {
+ const SkOpSpan* start = coinPtTStart()->span()->upCast();
+ const SkOpSpan* prev = start->prev();
+ const SkOpPtT* oppPtT;
+ if (!prev || !(oppPtT = prev->contains(oppSegment))) {
+ break;
+ }
+ double midT = (prev->t() + start->t()) / 2;
+ if (!segment->isClose(midT, oppSegment)) {
+ break;
+ }
+ if (log) log->record(kExpandCoin_Glitch, id, this, prev->ptT(), oppPtT);
+ expanded = true;
+ } while (false); // actual continues while expansion is possible
+ do {
+ const SkOpSpanBase* end = coinPtTEnd()->span();
+ SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
+ const SkOpPtT* oppPtT;
+ if (!next || !(oppPtT = next->contains(oppSegment))) {
+ break;
+ }
+ double midT = (end->t() + next->t()) / 2;
+ if (!segment->isClose(midT, oppSegment)) {
+ break;
+ }
+ if (log) log->record(kExpandCoin_Glitch, id, this, next->ptT(), oppPtT);
+ expanded = true;
+ } while (false); // actual continues while expansion is possible
+ return expanded;
+}
+
+#define FAIL_IF(cond) do { if (cond) log->record(kAddExpandedFail_Glitch, id, coin); } while (false)
+
+/* Commented-out lines keep this in sync with addExpanded */
+// 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
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;
+ const SkOpPtT* startPtT = coin->coinPtTStart();
+ const SkOpPtT* oStartPtT = coin->oppPtTStart();
SkASSERT(startPtT->contains(oStartPtT));
- SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
+ SkASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
const SkOpSpanBase* start = startPtT->span();
const SkOpSpanBase* oStart = oStartPtT->span();
- const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
- const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
+ const SkOpSpanBase* end = coin->coinPtTEnd()->span();
+ const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
+ FAIL_IF(oEnd->deleted());
const SkOpSpanBase* test = start->upCast()->next();
- const SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
+ const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
+ if (!oTest) {
+ return;
+ }
while (test != end || oTest != oEnd) {
- bool bumpTest = true;
- bool bumpOTest = true;
- if (!test->ptT()->contains(oTest->ptT())) {
+ if (!test->ptT()->contains(oTest->segment())
+ || !oTest->ptT()->contains(start->segment())) {
// use t ranges to guess which one is missing
- double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
+ double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
+ FAIL_IF(!startRange);
double startPart = (test->t() - startPtT->fT) / startRange;
- double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
+ double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
+ FAIL_IF(!oStartRange);
double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
- if (startPart == oStartPart) {
- // data is corrupt
- log->record(kAddCorruptCoin_Glitch, id, start, oStart);
- break;
+ FAIL_IF(startPart == oStartPart);
+ bool startOver = false;
+ if (startPart < oStartPart)
+ log->record(kAddExpandedCoin_Glitch, id, // strange debug formatting lines up with original
+ oStartPtT->fT + oStartRange * startPart, test);
+ else log->record(kAddExpandedCoin_Glitch, id,
+ startPtT->fT + startRange * oStartPart, oTest);
+ if (false) {
+ SkASSERT(0);
+ return;
}
- 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 (startOver) {
+ test = start;
+ oTest = oStart;
}
}
- if (bumpTest && test != end) {
+ if (test != end) {
test = test->upCast()->next();
}
- if (bumpOTest && oTest != oEnd) {
- oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
+ if (oTest != oEnd) {
+ oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
+ if (!oTest) {
+ return;
+ }
}
}
- } 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;
+ } while ((coin = coin->next()));
+ return;
+}
+
+/* Commented-out lines keep this in sync with addIfMissing() */
+void SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
+ const SkOpPtT* over1e, const char* id, SkPathOpsDebug::GlitchLog* log) const {
+// SkASSERT(fTop);
+ if (fTop && alreadyAdded(fTop, outer, over1s, over1e)) { // in debug, fTop may be null
+ return;
}
- return true;
+ if (fHead && alreadyAdded(fHead, outer, over1s, over1e)) {
+ return;
+ }
+ log->record(kAddIfMissingCoin_Glitch, id, outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e);
+ this->debugValidate();
+ return;
}
-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 {
+/* Commented-out lines keep this in sync addIfMissing() */
+void SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
+ const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
+ const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
+ const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, const char* id, SkPathOpsDebug::GlitchLog* log) 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;
+ TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
+ TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+ bool swap = coinTs > coinTe;
+ if (swap) {
+ SkTSwap(coinTs, coinTe);
}
if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
SkTSwap(oppTs, oppTe);
}
- if (coinTs > coinTe) {
- SkTSwap(coinTs, coinTe);
+ if (swap) {
SkTSwap(oppTs, oppTe);
}
- bool cs = coinSeg->debugAddMissing(coinTs, oppSeg);
- bool ce = coinSeg->debugAddMissing(coinTe, oppSeg);
- if (cs == ce) {
- return false;
+ const SkOpSegment* coinSeg = coinPtTStart->segment();
+ const SkOpSegment* oppSeg = oppPtTStart->segment();
+ if (coinSeg == oppSeg) {
+ return;
}
- return true;
+ return this->debugAddOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, id, log);
+}
+
+/* Commented-out lines keep this in sync addOrOverlap() */
+void SkOpCoincidence::debugAddOrOverlap(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
+ double coinTs, double coinTe, double oppTs, double oppTe, const char* id, SkPathOpsDebug::GlitchLog* log) const {
+ SkTDArray<SkCoincidentSpans*> overlaps;
+ SkASSERT(!fTop); // this is (correctly) reversed in addifMissing()
+ if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
+ return;
+ }
+ if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
+ coinTe, oppTs, oppTe, &overlaps)) {
+ return;
+ }
+ const SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
+ for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
+ const SkCoincidentSpans* test = overlaps[index];
+ if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
+ log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTStart());
+ }
+ if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
+ log->record(kAddOrOverlap_Glitch, id, overlap, test->coinPtTEnd());
+ }
+ if (overlap->flipped()
+ ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
+ : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
+ log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTStart());
+ }
+ if (overlap->flipped()
+ ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
+ : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
+ log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTEnd());
+ }
+ if (!fHead) {
+ SkAssertResult(true);
+ }
+ }
+ const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
+ const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
+ if (overlap && cs && ce && overlap->contains(cs, ce)) {
+ return;
+ }
+ SkASSERT(cs != ce || !cs);
+ const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
+ const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
+ if (overlap && os && oe && overlap->contains(os, oe)) {
+ return;
+ }
+ SkASSERT(true || !cs || !cs->deleted());
+ SkASSERT(true || !os || !os->deleted());
+ SkASSERT(true || !ce || !ce->deleted());
+ SkASSERT(true || !oe || !oe->deleted());
+ const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
+ const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
+ if (csExisting && csExisting == ceExisting) {
+ return;
+ }
+ if (csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceExisting : ce))) {
+ return;
+ }
+ if (ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csExisting : cs))) {
+ return;
+ }
+ const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
+ const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
+ if (osExisting && osExisting == oeExisting) {
+ return;
+ }
+ if (osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeExisting : oe))) {
+ return;
+ }
+ if (oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osExisting : os))) {
+ return;
+ }
+ bool csDeleted = false, osDeleted = false, ceDeleted = false, oeDeleted = false;
+ this->debugValidate();
+ if (!cs || !os) {
+ if (!cs)
+ cs = coinSeg->debugAddT(coinTs, SkOpSegment::kNoAliasMatch, nullptr);
+ if (!os)
+ os = oppSeg->debugAddT(oppTs, SkOpSegment::kNoAliasMatch, nullptr);
+ if (cs && os) cs->span()->debugAddOppAndMerge(id, log, os->span(), &csDeleted, &osDeleted);
+// cs = csWritable;
herb_g 2016/07/18 15:13:39 You have a bunch of commented out code in this rou
caryclark 2016/07/18 15:55:49 See reply above.
+// os = osWritable;
+ if ((ce && ce->deleted()) || (oe && oe->deleted())) {
+ return;
+ }
+ }
+ if (!ce || !oe) {
+ if (!ce)
+ ce = coinSeg->debugAddT(coinTe, SkOpSegment::kNoAliasMatch, nullptr);
+ if (!oe)
+ oe = oppSeg->debugAddT(oppTe, SkOpSegment::kNoAliasMatch, nullptr);
+ if (ce && oe) ce->span()->debugAddOppAndMerge(id, log, oe->span(), &ceDeleted, &oeDeleted);
+// ce = ceWritable;
+// oe = oeWritable;
+ }
+ this->debugValidate();
+ if (csDeleted || osDeleted || ceDeleted || oeDeleted) {
+ return;
+ }
+ if (!cs || !ce || cs->contains(ce) || !os || !oe || os->contains(oe)) {
+ return;
+ }
+// bool result = true;
+ if (overlap) {
+ if (overlap->coinPtTStart()->segment() == coinSeg) {
+ log->record(kAddMissingExtend_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
+ } else {
+ if (oppTs > oppTe) {
+ SkTSwap(coinTs, coinTe);
+ SkTSwap(oppTs, oppTe);
+ }
+ log->record(kAddMissingExtend_Glitch, id, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
+ }
+#if DEBUG_COINCIDENCE_VERBOSE
+// if (result) {
+// overlap->debugShow();
+// }
+#endif
+ } else {
+ log->record(kAddMissingCoin_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
+#if DEBUG_COINCIDENCE_VERBOSE
+// fHead->debugShow();
+#endif
+ }
+ this->debugValidate();
+ return;
}
+// Extra commented-out lines keep this in sync with addMissing()
+/* detects overlaps of different coincident runs on same segment */
+/* does not detect overlaps for pairs without any segments in common */
+// returns true if caller should loop again
void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
const SkCoincidentSpans* outer = fHead;
if (!outer) {
return;
}
+ // bool added = false;
+ // fTop = outer;
+ // fHead = nullptr;
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 SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
+ const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
+ if (outerCoin->done() || outerOpp->done()) {
+ continue;
+ }
const SkCoincidentSpans* inner = outer;
- while ((inner = inner->fNext)) {
+ while ((inner = inner->next())) {
+ this->debugValidate();
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);
+ const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
+ const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
+ if (innerCoin->done() || innerOpp->done()) {
+ continue;
+ }
+ if (outerCoin == innerCoin) {
+ if (outerOpp != innerOpp
+ && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
+ this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
+ outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
}
- } 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 (outerCoin == innerOpp) {
+ if (outerOpp != innerCoin
+ && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
+ this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
+ outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
}
- } 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 == innerCoin) {
+ SkASSERT(outerCoin != innerOpp);
+ if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
+ this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
+ outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
}
- } 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);
- }
- }
+ } else if (outerOpp == innerOpp) {
+ SkASSERT(outerCoin != innerCoin);
+ if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
+ this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
+ outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
}
}
+ this->debugValidate();
+ }
+ } while ((outer = outer->next()));
+ // this->restoreHead();
+ return;
+}
+
+// Commented-out lines keep this in sync with release()
+void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const {
+ const SkCoincidentSpans* coin = fHead;
+ if (!coin) {
+ return;
+ }
+ do {
+ if (coin->coinPtTStart()->segment() == deleted
+ || coin->coinPtTEnd()->segment() == deleted
+ || coin->oppPtTStart()->segment() == deleted
+ || coin->oppPtTEnd()->segment() == deleted) {
+ log->record(kReleasedSpan_Glitch, id, coin);
+ }
+ } while ((coin = coin->next()));
+}
+
+// Commented-out lines keep this in sync with reorder()
+// iterate through all coincident pairs, looking for ranges greater than 1
+// if found, see if the opposite pair can match it -- which may require
+// reordering the ptT pairs
+void SkOpCoincidence::debugReorder(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+ const SkCoincidentSpans* coin = fHead;
+ if (!coin) {
+ return;
+ }
+ do {
+ // most commonly, concidence are one span long; check for that first
+ int intervals = coin->spanCount();
+ if (intervals = 1) {
+#if DEBUG_COINCIDENCE_VERBOSE
+ // SkASSERT(!coin->debugExpand(nullptr, nullptr));
+#endif
+ continue;
+ }
+ coin->debugExpand(id, log);
+ if (coin->spanCount() <= 0) {
+ return;
}
- } while ((outer = outer->fNext));
+ // check to see if every span in coin has a mate in opp
+ const SkOpSpan* start = coin->coinPtTStart()->span()->upCast();
+ bool flipped = coin->flipped();
+ const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span();
+ const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast();
+ SkDebugf("", start, oppStart);
+ } while ((coin = coin->next()));
+ return;
}
+// Commented-out lines keep this in sync with expand()
+// expand the range by checking adjacent spans for coincidence
bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
const SkCoincidentSpans* coin = fHead;
if (!coin) {
@@ -1352,109 +1671,296 @@ bool SkOpCoincidence::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log
}
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);
- }
+ if (coin->debugExpand(id, log)) {
+ // check to see if multiple spans expanded so they are now identical
+ const SkCoincidentSpans* test = fHead;
+ do {
+ if (coin == test) {
+ continue;
+ }
+ if (coin->coinPtTStart() == test->coinPtTStart()
+ && coin->oppPtTStart() == test->oppPtTStart()) {
+ if (log) log->record(kExpandCoin_Glitch, id, fHead, test->coinPtTStart());
+ break;
+ }
+ } while ((test = test->next()));
+ expanded = true;
}
- } while ((coin = coin->fNext));
+ } while ((coin = coin->next()));
return expanded;
}
-void SkOpCoincidence::debugFixAligned(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+// Commented-out lines keep this in sync with removeCollapsed()
+void SkOpCoincidence::debugRemoveCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log) const {
const SkCoincidentSpans* coin = fHead;
if (!coin) {
return;
}
+ // SkCoincidentSpans** priorPtr = &fHead;
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->coinPtTStart() == coin->coinPtTEnd()) {
+ return;
}
- if (coin->fOppPtTEnd->deleted()) {
- log->record(kDeletedCoin_Glitch, id, coin, coin->fOppPtTEnd);
+ if (coin->oppPtTStart() == coin->oppPtTEnd()) {
+ return;
}
- } while ((coin = coin->fNext));
- coin = fHead;
- do {
- if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)) {
- log->record(kCollapsedCoin_Glitch, id, coin, coin->fCoinPtTStart);
+ if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) {
+ log->record(kCollapsedCoin_Glitch, id, coin);
+// continue;
}
- if (coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
- log->record(kCollapsedCoin_Glitch, id, coin, coin->fOppPtTStart);
+ if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) {
+ log->record(kCollapsedCoin_Glitch, id, coin, coin);
+// continue;
}
- } while ((coin = coin->fNext));
+ // priorPtr = &coin->nextPtr();
+ } while ((coin = coin->next()));
+ return;
}
+// Commented-out lines keep this in sync with mark()
+/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
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);
+ const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
+// SkASSERT(start->deleted());
+ const SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
+// SkASSERT(end->deleted());
+ const SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
+// SkASSERT(oStart->deleted());
+ const SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
+// SkASSERT(oEnd->deleted());
+ bool flipped = coin->flipped();
if (flipped) {
SkTSwap(oStart, oEnd);
}
+ /* coin and opp spans may not match up. Mark the ends, and then let the interior
+ get marked as many times as the spans allow */
+ start->debugInsertCoincidence(id, log, oStart->upCast());
+ end->debugInsertCoinEnd(id, log, oEnd);
+ const SkOpSegment* segment = start->segment();
+ const SkOpSegment* oSegment = oStart->segment();
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;
+ while ((next = next->upCast()->next()) != end) {
+ if (next->upCast()->debugInsertCoincidence(id, log, oSegment, flipped), false) {
+ return;
}
- if (!next->containsCoinEnd(oNext)) {
- log->record(kMarkCoinEnd_Glitch, id, next, oNext);
+ }
+ while ((oNext = oNext->upCast()->next()) != oEnd) {
+ if (oNext->upCast()->debugInsertCoincidence(id, log, segment, flipped), false) {
+ return;
}
- const SkOpSpan* nextSpan = next->upCast();
- const SkOpSpan* oNextSpan = oNext->upCast();
- if (!nextSpan->containsCoincidence(oNextSpan)) {
- log->record(kMarkCoinInsert_Glitch, id, nextSpan, oNextSpan);
+ }
+ } while ((coin = coin->next()));
+ return;
+}
+#endif
+
+#if DEBUG_COINCIDENCE_VERBOSE
+// Commented-out lines keep this in sync with markCollapsed()
+void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkOpPtT* test) const {
+ while (coin) {
+ if (coin->collapsed(test)) {
+ if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
+ log->record(kCollapsedCoin_Glitch, id, coin);
}
- } while (true);
- } while ((coin = coin->fNext));
+ if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
+ log->record(kCollapsedCoin_Glitch, id, coin);
+ }
+ }
+ coin = coin->next();
+ }
+}
+
+// Commented-out lines keep this in sync with markCollapsed()
+void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* test) const {
+ this->debugMarkCollapsed(id, log, fHead, test);
+ this->debugMarkCollapsed(id, log, fTop, test);
}
#endif
+void SkCoincidentSpans::debugShow() const {
+ SkDebugf("%s - id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
+ coinPtTStart()->segment()->debugID(),
+ coinPtTStart()->fT, coinPtTEnd()->fT);
+ SkDebugf("%s + id=%d t=%1.9g tEnd=%1.9g\n", __FUNCTION__,
+ oppPtTStart()->segment()->debugID(),
+ oppPtTStart()->fT, oppPtTEnd()->fT);
+}
+
void SkOpCoincidence::debugShowCoincidence() const {
- SkCoincidentSpans* span = fHead;
+#if DEBUG_COINCIDENCE
+ 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;
+ span->debugShow();
+ span = span->next();
}
+#endif
}
#if DEBUG_COINCIDENCE
+static void DebugValidate(const SkOpSpanBase* next, const SkOpSpanBase* end,
+ double oStart, double oEnd, const SkOpSegment* oSegment,
+ const char* id, SkPathOpsDebug::GlitchLog* log) {
+ SkASSERT(next != end);
+ SkASSERT(!next->contains(end) || log);
+ if (next->t() > end->t()) {
+ SkTSwap(next, end);
+ }
+ do {
+ const SkOpPtT* ptT = next->ptT();
+ int index = 0;
+ bool somethingBetween;
+ do {
+ ++index;
+ ptT = ptT->next();
+ const SkOpPtT* checkPtT = next->ptT();
+ if (ptT == checkPtT) {
+ break;
+ }
+ bool looped = false;
+ for (int check = 0; check < index; ++check) {
+ if ((looped = checkPtT == ptT)) {
+ break;
+ }
+ checkPtT = checkPtT->next();
+ }
+ if (looped) {
+ SkASSERT(0);
+ break;
+ }
+ if (ptT->deleted()) {
+ continue;
+ }
+ if (ptT->segment() != oSegment) {
+ continue;
+ }
+ somethingBetween |= between(oStart, ptT->fT, oEnd);
+ } while (true);
+ SkASSERT(somethingBetween);
+ } while (next != end && (next = next->upCast()->next()));
+}
+
+static void DebugCheckOverlap(const SkCoincidentSpans* test, const SkCoincidentSpans* list,
+ const char* id, SkPathOpsDebug::GlitchLog* log) {
+ if (!list) {
+ return;
+ }
+ const SkOpSegment* coinSeg = test->coinPtTStart()->segment();
+ SkASSERT(coinSeg == test->coinPtTEnd()->segment());
+ const SkOpSegment* oppSeg = test->oppPtTStart()->segment();
+ SkASSERT(oppSeg == test->oppPtTEnd()->segment());
+ SkASSERT(coinSeg != test->oppPtTStart()->segment());
+ SkDEBUGCODE(double tcs = test->coinPtTStart()->fT);
+ SkASSERT(between(0, tcs, 1));
+ SkDEBUGCODE(double tce = test->coinPtTEnd()->fT);
+ SkASSERT(between(0, tce, 1));
+ SkASSERT(tcs < tce);
+ double tos = test->oppPtTStart()->fT;
+ SkASSERT(between(0, tos, 1));
+ double toe = test->oppPtTEnd()->fT;
+ SkASSERT(between(0, toe, 1));
+ SkASSERT(tos != toe);
+ if (tos > toe) {
+ SkTSwap(tos, toe);
+ }
+ do {
+ double lcs, lce, los, loe;
+ if (coinSeg == list->coinPtTStart()->segment()) {
+ if (oppSeg != list->oppPtTStart()->segment()) {
+ continue;
+ }
+ lcs = list->coinPtTStart()->fT;
+ lce = list->coinPtTEnd()->fT;
+ los = list->oppPtTStart()->fT;
+ loe = list->oppPtTEnd()->fT;
+ if (los > loe) {
+ SkTSwap(los, loe);
+ }
+ } else if (coinSeg == list->oppPtTStart()->segment()) {
+ if (oppSeg != list->coinPtTStart()->segment()) {
+ continue;
+ }
+ lcs = list->oppPtTStart()->fT;
+ lce = list->oppPtTEnd()->fT;
+ if (lcs > lce) {
+ SkTSwap(lcs, lce);
+ }
+ los = list->coinPtTStart()->fT;
+ loe = list->coinPtTEnd()->fT;
+ } else {
+ continue;
+ }
+ SkASSERT(tce < lcs || lce < tcs);
+ SkASSERT(toe < los || loe < tos);
+ } while ((list = list->next()));
+}
+
+
+static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
+ const char* id, SkPathOpsDebug::GlitchLog* log) {
+ // check for overlapping coincident spans
+ const SkCoincidentSpans* test = head;
+ while (test) {
+ const SkCoincidentSpans* next = test->next();
+ DebugCheckOverlap(test, next, id, log);
+ DebugCheckOverlap(test, opt, id, log);
+ test = next;
+ }
+}
+
+#if DEBUG_COINCIDENCE_VERBOSE
+void SkOpCoincidence::debugCheckOverlap(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+ DebugCheckOverlapTop(fHead, fTop, id, log);
+ DebugCheckOverlapTop(fTop, nullptr, id, log);
+}
+#endif
+
+static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt,
+ const char* id, SkPathOpsDebug::GlitchLog* log) {
+ // look for pts inside coincident spans that are not inside the opposite spans
+ const SkCoincidentSpans* coin = head;
+ while (coin) {
+ SkASSERT(SkOpCoincidence::Ordered(coin->coinPtTStart()->segment(),
+ coin->oppPtTStart()->segment()));
+ SkASSERT(coin->coinPtTStart()->span()->ptT() == coin->coinPtTStart());
+ SkASSERT(coin->coinPtTEnd()->span()->ptT() == coin->coinPtTEnd());
+ SkASSERT(coin->oppPtTStart()->span()->ptT() == coin->oppPtTStart());
+ SkASSERT(coin->oppPtTEnd()->span()->ptT() == coin->oppPtTEnd());
+ DebugValidate(coin->coinPtTStart()->span(), coin->coinPtTEnd()->span(),
+ coin->oppPtTStart()->fT, coin->oppPtTEnd()->fT, coin->oppPtTStart()->segment(),
+ id, log);
+ DebugValidate(coin->oppPtTStart()->span(), coin->oppPtTEnd()->span(),
+ coin->coinPtTStart()->fT, coin->coinPtTEnd()->fT, coin->coinPtTStart()->segment(),
+ id, log);
+ coin = coin->next();
+ }
+ DebugCheckOverlapTop(head, opt, id, log);
+}
+#endif
+
+void SkOpCoincidence::debugValidate() const {
+#if DEBUG_COINCIDENCE
+ // if (fGlobalState->debugCheckHealth()) {
+// return;
+// }
+ DebugValidate(fHead, fTop, nullptr, nullptr);
+ DebugValidate(fTop, nullptr, nullptr, nullptr);
+#endif
+}
+
+#if DEBUG_COINCIDENCE_VERBOSE
+void SkOpCoincidence::debugCheckValid(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+ DebugValidate(fHead, fTop, id, log);
+ DebugValidate(fTop, nullptr, id, log);
+}
+#endif
+
+#if DEBUG_COINCIDENCE_VERBOSE
void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* log) const {
const SkOpSegment* segment = &fHead;
do {
@@ -1462,16 +1968,36 @@ void SkOpContour::debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* lo
} while ((segment = segment->next()));
}
-void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log,
- const SkOpCoincidence* coincidence) const {
+// commmented-out lines keep this aligned with missingCoincidence()
+void SkOpContour::debugMissingCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+// SkASSERT(fCount > 0);
const SkOpSegment* segment = &fHead;
+// bool result = false;
do {
- segment->debugMissingCoincidence(id, log, coincidence);
- } while ((segment = segment->next()));
+ if (fState->angleCoincidence()) {
+// #if DEBUG_ANGLE
+// segment->debugCheckAngleCoin();
+// #endif
+ } else if (segment->debugMissingCoincidence(id, log), false) {
+// result = true;
+// see FIXME in missingCoincidence()
+//
+//
+//
+ // continue;
+ }
+ segment = segment->next();
+ } while (segment);
+ return;
}
#endif
void SkOpSegment::debugValidate() const {
+#if DEBUG_COINCIDENCE
+ if (this->globalState()->debugCheckHealth()) {
+ return;
+ }
+#endif
#if DEBUG_VALIDATE
const SkOpSpanBase* span = &fHead;
double lastT = -1;
@@ -1500,56 +2026,47 @@ 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;
+#if DEBUG_COINCIDENCE_VERBOSE
+// Commented-out lines keep this in sync with addOppAndMerge()
+// If the added points envelop adjacent spans, merge them in.
+void SkOpSpanBase::debugAddOppAndMerge(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp, bool* spanDeleted, bool* oppDeleted) const {
+ if (this->ptT()->debugAddOpp(opp->ptT())) {
+ this->debugCheckForCollapsedCoincidence(id, log);
}
- 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;
- }
+ // compute bounds of points in span
+ SkPathOpsBounds bounds;
+ bounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin);
+ const SkOpPtT* head = this->ptT();
+ const SkOpPtT* nextPt = head;
+ do {
+ bounds.add(nextPt->fPt);
+ } while ((nextPt = nextPt->next()) != head);
+ if (!bounds.width() && !bounds.height()) {
+ return;
}
- return this->fAligned;
+ this->debugMergeContained(id, log, bounds, spanDeleted);
+ opp->debugMergeContained(id, log, bounds, oppDeleted);
}
-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;
+// Commented-out lines keep this in sync with checkForCollapsedCoincidence()
+void SkOpSpanBase::debugCheckForCollapsedCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log) const {
+ const SkOpCoincidence* coins = this->globalState()->coincidence();
+ if (coins->isEmpty()) {
+ return;
+ }
+// the insert above may have put both ends of a coincident run in the same span
+// for each coincident ptT in loop; see if its opposite in is also in the loop
+// this implementation is the motivation for marking that a ptT is referenced by a coincident span
+ const SkOpPtT* head = this->ptT();
+ const SkOpPtT* test = head;
do {
- if (ptT->fPt != pt) {
- return false;
+ if (!test->coincident()) {
+ continue;
}
- 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;
+ coins->debugMarkCollapsed(id, log, test);
+ } while ((test = test->next()) != head);
}
+#endif
bool SkOpSpanBase::debugCoinEndLoopCheck() const {
int loop = 0;
@@ -1574,16 +2091,57 @@ 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;
+#if DEBUG_COINCIDENCE_VERBOSE
+// Commented-out lines keep this in sync with insertCoinEnd()
+void SkOpSpanBase::debugInsertCoinEnd(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* coin) const {
+ if (containsCoinEnd(coin)) {
+// SkASSERT(coin->containsCoinEnd(this));
+ return;
+ }
+ debugValidate();
+// SkASSERT(this != coin);
+ log->record(kMarkCoinEnd_Glitch, id, this, coin);
+// coin->fCoinEnd = this->fCoinEnd;
+// this->fCoinEnd = coinNext;
+ debugValidate();
+}
+
+// Commented-out lines keep this in sync with mergeContained()
+void SkOpSpanBase::debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog* log, const SkPathOpsBounds& bounds, bool* deleted) const {
+ // while adjacent spans' points are contained by the bounds, merge them
+ const SkOpSpanBase* prev = this;
+ const SkOpSegment* seg = this->segment();
+ while ((prev = prev->prev()) && bounds.contains(prev->pt()) && !seg->ptsDisjoint(prev, this)) {
+ if (prev->prev()) {
+ log->record(kMergeContained_Glitch, id, this, prev);
+ } else if (this->final()) {
+ log->record(kMergeContained_Glitch, id, this, prev);
+ // return;
+ } else {
+ log->record(kMergeContained_Glitch, id, prev, this);
}
}
- return false;
+ const SkOpSpanBase* current = this;
+ const SkOpSpanBase* next = this;
+ while (next->upCastable() && (next = next->upCast()->next())
+ && bounds.contains(next->pt()) && !seg->ptsDisjoint(this, next)) {
+ if (!current->prev() && next->final()) {
+ log->record(kMergeContained_Glitch, id, next, current);
+ current = next;
+ }
+ if (current->prev()) {
+ log->record(kMergeContained_Glitch, id, next, current);
+ current = next;
+ } else {
+ log->record(kMergeContained_Glitch, id, next, current);
+ current = next;
+ }
+ }
+#if DEBUG_COINCIDENCE
+ // this->globalState()->coincidence()->debugValidate();
+#endif
}
+#endif
const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
const SkOpSpanBase* end = *endPtr;
@@ -1599,6 +2157,11 @@ const SkOpSpan* SkOpSpanBase::debugStarter(SkOpSpanBase const** endPtr) const {
}
void SkOpSpanBase::debugValidate() const {
+#if DEBUG_COINCIDENCE
+ if (this->globalState()->debugCheckHealth()) {
+ return;
+ }
+#endif
#if DEBUG_VALIDATE
const SkOpPtT* ptT = &fPtT;
SkASSERT(ptT->span() == this);
@@ -1643,6 +2206,39 @@ bool SkOpSpan::debugCoinLoopCheck() const {
return true;
}
+#if DEBUG_COINCIDENCE_VERBOSE
+// Commented-out lines keep this in sync with insertCoincidence() in header
+void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpan* coin) const {
+ if (containsCoincidence(coin)) {
+// SkASSERT(coin->containsCoincidence(this));
+ return;
+ }
+ debugValidate();
+// SkASSERT(this != coin);
+ log->record(kMarkCoinStart_Glitch, id, this, coin);
+// coin->fCoincident = this->fCoincident;
+// this->fCoincident = coinNext;
+ debugValidate();
+}
+
+// Commented-out lines keep this in sync with insertCoincidence()
+void SkOpSpan::debugInsertCoincidence(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* segment, bool flipped) const {
+ if (this->containsCoincidence(segment)) {
+ return;
+ }
+ const SkOpPtT* next = &fPtT;
+ while ((next = next->next()) != &fPtT) {
+ if (next->segment() == segment) {
+ log->record(kMarkCoinInsert_Glitch, id, flipped ? next->span()->prev() : next->span());
+ return;
+ }
+ }
+#if DEBUG_COINCIDENCE
+ log->record(kMarkCoinMissing_Glitch, id, segment, this);
+#endif
+}
+#endif
+
// called only by test code
int SkIntersections::debugCoincidentUsed() const {
if (!fIsCoincident[0]) {
@@ -1667,6 +2263,27 @@ int SkIntersections::debugCoincidentUsed() const {
#include "SkOpContour.h"
+// Commented-out lines keep this in sync with addOpp()
+bool SkOpPtT::debugAddOpp(const SkOpPtT* opp) const {
+ // find the fOpp ptr to opp
+ const SkOpPtT* oppPrev = opp->fNext;
+ if (oppPrev == this) {
+ return false;
+ }
+ while (oppPrev->fNext != opp) {
+ oppPrev = oppPrev->fNext;
+ if (oppPrev == this) {
+ return false;
+ }
+ }
+// const SkOpPtT* oldNext = this->fNext;
+ SkASSERT(this != opp);
+// this->fNext = opp;
+// SkASSERT(oppPrev != oldNext);
+// oppPrev->fNext = oldNext;
+ return true;
+}
+
bool SkOpPtT::debugContains(const SkOpPtT* check) const {
SkASSERT(this != check);
const SkOpPtT* ptT = this;
@@ -1736,6 +2353,11 @@ int SkOpPtT::debugLoopLimit(bool report) const {
}
void SkOpPtT::debugValidate() const {
+#if DEBUG_COINCIDENCE
+ if (this->globalState()->debugCheckHealth()) {
+ return;
+ }
+#endif
#if DEBUG_VALIDATE
SkOpGlobalState::Phase phase = contour()->globalState()->phase();
if (phase == SkOpGlobalState::kIntersecting

Powered by Google App Engine
This is Rietveld 408576698