aboutsummaryrefslogtreecommitdiffhomepage
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/pathops/SkAddIntersections.cpp21
-rw-r--r--src/pathops/SkOpAngle.cpp4
-rw-r--r--src/pathops/SkOpAngle.h2
-rwxr-xr-xsrc/pathops/SkOpCoincidence.cpp84
-rw-r--r--src/pathops/SkOpCoincidence.h12
-rw-r--r--src/pathops/SkOpContour.h2
-rw-r--r--src/pathops/SkOpSegment.cpp26
-rw-r--r--src/pathops/SkOpSegment.h7
-rwxr-xr-xsrc/pathops/SkOpSpan.cpp161
-rw-r--r--src/pathops/SkOpSpan.h38
-rw-r--r--src/pathops/SkPathOpsCommon.cpp3
-rw-r--r--src/pathops/SkPathOpsDebug.cpp268
-rw-r--r--src/pathops/SkPathOpsDebug.h4
-rw-r--r--src/pathops/SkPathOpsPoint.h29
-rw-r--r--src/pathops/SkPathOpsTypes.h16
15 files changed, 471 insertions, 206 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index bdc7ae2565..04f5bc384c 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -508,16 +508,19 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc
SkOpPtT* testTAt = wt.segment()->addT(ts[swap][pt]);
wn.segment()->debugValidate();
SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt]);
- SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt);
- if (oppPrev) {
- testTAt->addOpp(nextTAt, oppPrev);
- }
- if (testTAt->fPt != nextTAt->fPt) {
- testTAt->span()->unaligned();
- nextTAt->span()->unaligned();
+ if (!testTAt->contains(nextTAt)) {
+ SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair
+ if (oppPrev) { // already shares a pt-t loop.
+ testTAt->span()->mergeMatches(nextTAt->span());
+ testTAt->addOpp(nextTAt, oppPrev);
+ }
+ if (testTAt->fPt != nextTAt->fPt) {
+ testTAt->span()->unaligned();
+ nextTAt->span()->unaligned();
+ }
+ wt.segment()->debugValidate();
+ wn.segment()->debugValidate();
}
- wt.segment()->debugValidate();
- wn.segment()->debugValidate();
if (!ts.isCoincident(pt)) {
continue;
}
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 2da8357add..6bc510e5ee 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -905,8 +905,10 @@ void SkOpAngle::setSpans() {
if (verb != SkPath::kLine_Verb
&& !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) {
SkDLine lineHalf;
+ fCurvePart[1] = fCurvePart[SkPathOpsVerbToPoints(verb)];
+ fOriginalCurvePart[1] = fCurvePart[1];
lineHalf[0].set(fCurvePart[0].asSkPoint());
- lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint());
+ lineHalf[1].set(fCurvePart[1].asSkPoint());
fTangentHalf.lineEndPoints(lineHalf);
fSide = 0;
}
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index a1ead1ecfd..4099c4a90b 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -30,7 +30,7 @@ public:
const SkOpAngle* debugAngle(int id) const;
const SkOpCoincidence* debugCoincidence() const;
- SkOpContour* debugContour(int id);
+ SkOpContour* debugContour(int id) const;
int debugID() const {
return SkDEBUGRELEASE(fID, -1);
diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 1c8ab5f524..831ce71190 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -250,10 +250,10 @@ void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* o
oppPtTEnd = oppPtTEnd->span()->ptT();
SkASSERT(coinPtTStart->fT < coinPtTEnd->fT);
SkASSERT(oppPtTStart->fT != oppPtTEnd->fT);
- SkASSERT(!coinPtTStart->deleted());
- SkASSERT(!coinPtTEnd->deleted());
- SkASSERT(!oppPtTStart->deleted());
- SkASSERT(!oppPtTEnd->deleted());
+ SkOPASSERT(!coinPtTStart->deleted());
+ SkOPASSERT(!coinPtTEnd->deleted());
+ SkOPASSERT(!oppPtTStart->deleted());
+ SkOPASSERT(!oppPtTEnd->deleted());
DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(
@@ -301,7 +301,7 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase*
SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
SkOpPtT* oppStart = writableSeg->addT(t);
SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
- oppStart->span()->addOppAndMerge(writableBase);
+ oppStart->span()->addOpp(writableBase);
if (oppStart->deleted()) {
continue;
}
@@ -426,9 +426,7 @@ bool SkOpCoincidence::addExpanded() {
FAIL_IF(!start->upCastable());
const SkOpSpanBase* test = start->upCast()->next();
const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
- if (!oTest) {
- return false;
- }
+ FAIL_IF(!oTest);
while (test != end || oTest != oEnd) {
if (!test->ptT()->contains(oStart->segment())
|| !oTest->ptT()->contains(start->segment())) {
@@ -446,26 +444,21 @@ bool SkOpCoincidence::addExpanded() {
oStartPtT->fT + oStartRange * startPart, test, &startOver)
: start->segment()->addExpanded(
startPtT->fT + startRange * oStartPart, oTest, &startOver);
- if (!success) {
- SkOPASSERT(false);
- return false;
- }
+ FAIL_IF(!success);
if (startOver) {
test = start;
oTest = oStart;
}
+ end = coin->coinPtTEnd()->span();
+ oEnd = coin->oppPtTEnd()->span();
}
if (test != end) {
- if (!test->upCastable()) {
- return false;
- }
+ FAIL_IF(!test->upCastable());
test = test->upCast()->next();
}
if (oTest != oEnd) {
oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
- if (!oTest) {
- return false;
- }
+ FAIL_IF(!oTest);
}
}
} while ((coin = coin->next()));
@@ -579,9 +572,20 @@ bool SkOpCoincidence::addIfMissing(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) {
+ SkOpSegment* coinSeg = coinPtTStart->segment();
+ SkOpSegment* oppSeg = oppPtTStart->segment();
+ if (coinSeg == oppSeg) {
+ return false;
+ }
double coinTs, coinTe, oppTs, oppTe;
TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
+ if (coinSeg->collapsed(coinTs, coinTe)) {
+ return false;
+ }
TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+ if (oppSeg->collapsed(oppTs, oppTe)) {
+ return false;
+ }
bool swap = coinTs > coinTe;
if (swap) {
SkTSwap(coinTs, coinTe);
@@ -592,11 +596,6 @@ bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
if (swap) {
SkTSwap(oppTs, oppTe);
}
- SkOpSegment* coinSeg = coinPtTStart->segment();
- SkOpSegment* oppSeg = oppPtTStart->segment();
- if (coinSeg == oppSeg) {
- return false;
- }
return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ );
}
@@ -672,9 +671,9 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
: oppSeg->addT(oppTs);
RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable);
- csWritable->span()->addOppAndMerge(osWritable->span());
+ csWritable->span()->addOpp(osWritable->span());
cs = csWritable;
- os = osWritable;
+ os = osWritable->active();
RETURN_FALSE_IF(callerAborts, (ce && ce->deleted()) || (oe && oe->deleted()));
}
if (!ce || !oe) {
@@ -682,7 +681,7 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
: coinSeg->addT(coinTe);
SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
: oppSeg->addT(oppTe);
- ceWritable->span()->addOppAndMerge(oeWritable->span());
+ ceWritable->span()->addOpp(oeWritable->span());
ce = ceWritable;
oe = oeWritable;
}
@@ -1141,6 +1140,38 @@ bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove
return coin != nullptr;
}
+void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) {
+ if (!coin) {
+ return;
+ }
+ SkCoincidentSpans* head = coin;
+ SkCoincidentSpans* prev = nullptr;
+ SkCoincidentSpans* next;
+ do {
+ next = coin->next();
+ if (coin->coinPtTStart()->deleted()) {
+ SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() :
+ coin->oppPtTStart()->deleted());
+ if (prev) {
+ prev->setNext(next);
+ } else if (head == fHead) {
+ fHead = next;
+ } else {
+ fTop = next;
+ }
+ } else {
+ SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() :
+ !coin->oppPtTStart()->deleted());
+ prev = coin;
+ }
+ } while ((coin = next));
+}
+
+void SkOpCoincidence::releaseDeleted() {
+ this->releaseDeleted(fHead);
+ this->releaseDeleted(fTop);
+}
+
// Please keep this in sync with debugReorder()
// iterate through all coincident pairs, looking for ranges greater than 1
// if found, see if the opposite pair can match it -- which may require
@@ -1196,6 +1227,7 @@ void SkOpCoincidence::restoreHead() {
}
// Please keep this in sync with debugExpand()
+// expand the range by checking adjacent spans for coincidence
bool SkOpCoincidence::expand() {
SkCoincidentSpans* coin = fHead;
if (!coin) {
diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h
index 436fa82527..eeeb7344dc 100644
--- a/src/pathops/SkOpCoincidence.h
+++ b/src/pathops/SkOpCoincidence.h
@@ -156,9 +156,9 @@ public:
#if DEBUG_COINCIDENCE_VERBOSE
void debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* ) const;
void debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* ) const;
- void debugAddOrOverlap(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
- double coinTs, double coinTe, double oppTs, double oppTe,
- const char* id, SkPathOpsDebug::GlitchLog* log) const;
+ void debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLog* log,
+ const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
+ double coinTs, double coinTe, double oppTs, double oppTe) const;
#endif
const SkOpAngle* debugAngle(int id) const {
@@ -170,7 +170,7 @@ public:
void debugCheckValid(const char* id, SkPathOpsDebug::GlitchLog* log) const;
#endif
- SkOpContour* debugContour(int id) {
+ SkOpContour* debugContour(int id) const {
return SkDEBUGRELEASE(fGlobalState->debugContour(id), nullptr);
}
@@ -193,6 +193,8 @@ public:
#if DEBUG_COINCIDENCE_VERBOSE
void debugRemoveCollapsed(const char* id, SkPathOpsDebug::GlitchLog* ) const;
void debugReorder(const char* id, SkPathOpsDebug::GlitchLog* ) const;
+ void debugRelease(const char* id, SkPathOpsDebug::GlitchLog* , const SkCoincidentSpans* ,
+ const SkCoincidentSpans* ) const;
void debugRelease(const char* id, SkPathOpsDebug::GlitchLog* , const SkOpSegment* ) const;
#endif
void debugShowCoincidence() const;
@@ -227,6 +229,7 @@ public:
static bool Ordered(const SkOpSegment* coin, const SkOpSegment* opp);
void release(const SkOpSegment* );
+ void releaseDeleted();
bool removeCollapsed();
bool reorder();
@@ -294,6 +297,7 @@ private:
const SkOpPtT* coinStart2, const SkOpPtT* coinEnd2,
double* overS, double* overE) const;
bool release(SkCoincidentSpans* coin, SkCoincidentSpans* );
+ void releaseDeleted(SkCoincidentSpans* );
void restoreHead();
bool testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
const SkOpPtT* testE) const;
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index fa90c45bb6..412fecd73f 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -124,7 +124,7 @@ public:
void debugCheckHealth(const char* id, SkPathOpsDebug::GlitchLog* ) const;
#endif
- SkOpContour* debugContour(int id) {
+ SkOpContour* debugContour(int id) const {
return SkDEBUGRELEASE(this->globalState()->debugContour(id), nullptr);
}
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 3c63683285..6a62175032 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -262,6 +262,7 @@ bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* start
SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT);
if (oppPrev) {
SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
+ writableTest->mergeMatches(newPtT->span());
writableTest->ptT()->addOpp(newPtT, oppPrev);
writableTest->checkForCollapsedCoincidence();
}
@@ -355,6 +356,16 @@ bool SkOpSegment::collapsed() const {
return fVerb < SkPath::kCubic_Verb && fHead.pt() == fTail.pt();
}
+bool SkOpSegment::collapsed(double s, double e) const {
+ const SkOpSpanBase* span = &fHead;
+ do {
+ if (span->collapsed(s, e)) {
+ return true;
+ }
+ } while (span->upCastable() && (span = span->upCast()->next()));
+ return false;
+}
+
void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType includeType) {
SkOpSegment* baseSegment = baseAngle->segment();
@@ -1300,13 +1311,8 @@ bool SkOpSegment::moveMultiples() {
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);
- oppTest->merge(oppSpan->upCast());
- } else {
- oppSpan->merge(oppTest->upCast());
- }
+ oppTest->mergeMatches(oppSpan);
+ oppTest->addOpp(oppSpan);
oppSegment->debugValidate();
goto checkNextSpan;
}
@@ -1326,14 +1332,14 @@ bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* c
const SkOpPtT* refHead = refSpan->ptT();
const SkOpPtT* checkHead = checkSpan->ptT();
// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
- if (!SkDPoint::RoughlyEqual(refHead->fPt, checkHead->fPt)) {
+ if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) {
#if DEBUG_COINCIDENCE
// verify that no combination of points are close
const SkOpPtT* dBugRef = refHead;
do {
const SkOpPtT* dBugCheck = checkHead;
do {
- SkASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
+ SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
dBugCheck = dBugCheck->next();
} while (dBugCheck != checkHead);
dBugRef = dBugRef->next();
@@ -1684,7 +1690,7 @@ bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT
continue;
}
SkDPoint oppPt = i.pt(index);
- if (oppPt.approximatelyEqual(midPt)) {
+ if (oppPt.approximatelyDEqual(midPt)) {
// the coincidence can occur at almost any angle
coincident = true;
}
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 1b7aad199c..a1b5477a4e 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -108,6 +108,7 @@ public:
void calcAngles();
bool collapsed() const;
+ bool collapsed(double startT, double endT) const;
static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType );
static void ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
@@ -128,7 +129,9 @@ public:
}
void debugAddAngle(double startT, double endT);
- const SkOpPtT* debugAddT(double t) const;
+#if DEBUG_COINCIDENCE_VERBOSE
+ const SkOpPtT* debugAddT(double t, const char* id, SkPathOpsDebug::GlitchLog* ) const;
+#endif
const SkOpAngle* debugAngle(int id) const;
#if DEBUG_ANGLE
void debugCheckAngleCoin() const;
@@ -139,7 +142,7 @@ public:
void debugClearOne(const SkOpSpan* span, const char* id, SkPathOpsDebug::GlitchLog* glitches) const;
#endif
const SkOpCoincidence* debugCoincidence() const;
- SkOpContour* debugContour(int id);
+ SkOpContour* debugContour(int id) const;
int debugID() const {
return SkDEBUGRELEASE(fID, -1);
diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp
index 98165fcfc5..162bcad293 100755
--- a/src/pathops/SkOpSpan.cpp
+++ b/src/pathops/SkOpSpan.cpp
@@ -13,6 +13,21 @@ bool SkOpPtT::alias() const {
return this->span()->ptT() != this;
}
+const SkOpPtT* SkOpPtT::active() const {
+ if (!fDeleted) {
+ return this;
+ }
+ const SkOpPtT* ptT = this;
+ const SkOpPtT* stopPtT = ptT;
+ while ((ptT = ptT->next()) != stopPtT) {
+ if (ptT->fSpan == fSpan && !ptT->fDeleted) {
+ return ptT;
+ }
+ }
+ SkASSERT(0); // should never return deleted
+ return this;
+}
+
bool SkOpPtT::collapsed(const SkOpPtT* check) const {
if (fPt != check->fPt) {
return false;
@@ -177,27 +192,14 @@ void SkOpPtT::setDeleted() {
fDeleted = true;
}
-// please keep this in sync with debugAddOppAndMerge
-// If the added points envelop adjacent spans, merge them in.
-void SkOpSpanBase::addOppAndMerge(SkOpSpanBase* opp) {
+void SkOpSpanBase::addOpp(SkOpSpanBase* opp) {
SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
- if (oppPrev) {
- this->ptT()->addOpp(opp->ptT(), oppPrev);
- this->checkForCollapsedCoincidence();
- }
- // 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()) {
+ if (!oppPrev) {
return;
}
- this->mergeContained(bounds);
- opp->mergeContained(bounds);
+ this->mergeMatches(opp);
+ this->ptT()->addOpp(opp->ptT(), oppPrev);
+ this->checkForCollapsedCoincidence();
}
// Please keep this in sync with debugMergeContained()
@@ -206,37 +208,39 @@ void SkOpSpanBase::mergeContained(const SkPathOpsBounds& bounds) {
SkOpSpanBase* prev = this;
SkOpSegment* seg = this->segment();
while ((prev = prev->prev()) && bounds.contains(prev->pt()) && !seg->ptsDisjoint(prev, this)) {
- if (prev->prev()) {
- this->merge(prev->upCast());
- prev = this;
- } else if (this->final()) {
- seg->clearAll();
- return;
- } else {
- prev->merge(this->upCast());
- }
+ this->mergeMatches(prev);
+ this->addOpp(prev);
}
- SkOpSpanBase* current = this;
SkOpSpanBase* next = this;
while (next->upCastable() && (next = next->upCast()->next())
&& bounds.contains(next->pt()) && !seg->ptsDisjoint(this, next)) {
- if (!current->prev() && next->final()) {
- seg->clearAll();
- return;
- }
- if (current->prev()) {
- next->merge(current->upCast());
- current = next;
- } else {
- current->merge(next->upCast());
- // extra line in debug version
- }
+ this->mergeMatches(next);
+ this->addOpp(next);
}
#if DEBUG_COINCIDENCE
this->globalState()->coincidence()->debugValidate();
#endif
}
+bool SkOpSpanBase::collapsed(double s, double e) const {
+ const SkOpPtT* start = &fPtT;
+ const SkOpPtT* walk = start;
+ double min = walk->fT;
+ double max = min;
+ const SkOpSegment* segment = this->segment();
+ while ((walk = walk->next()) != start) {
+ if (walk->segment() != segment) {
+ continue;
+ }
+ min = SkTMin(min, walk->fT);
+ max = SkTMax(max, walk->fT);
+ if (between(min, s, max) && between(min, e, max)) {
+ return true;
+ }
+ }
+ return false;
+}
+
bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
const SkOpPtT* start = &fPtT;
const SkOpPtT* check = &span->fPtT;
@@ -294,7 +298,7 @@ void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, cons
fChased = false;
SkDEBUGCODE(fCount = 1);
SkDEBUGCODE(fID = globalState()->nextSpanID());
- SkDEBUGCODE(fDeleted = false);
+ SkDEBUGCODE(fDebugDeleted = false);
}
// this pair of spans share a common t value or point; merge them and eliminate duplicates
@@ -305,6 +309,7 @@ void SkOpSpanBase::merge(SkOpSpan* span) {
SkASSERT(!zero_or_one(spanPtT->fT));
span->release(this->ptT());
if (this->contains(span)) {
+ SkOPASSERT(0); // check to see if this ever happens -- should have been found earlier
return; // merge is already in the ptT loop
}
SkOpPtT* remainder = spanPtT->next();
@@ -324,7 +329,12 @@ tryNextRemainder:
remainder = next;
}
fSpanAdds += span->fSpanAdds;
- this->checkForCollapsedCoincidence();
+}
+
+SkOpSpanBase* SkOpSpanBase::active() {
+ SkOpSpanBase* result = fPrev ? fPrev->next() : upCast()->next()->prev();
+ SkASSERT(this == result || fDebugDeleted);
+ return result;
}
// please keep in sync with debugCheckForCollapsedCoincidence()
@@ -344,6 +354,73 @@ void SkOpSpanBase::checkForCollapsedCoincidence() {
}
coins->markCollapsed(test);
} while ((test = test->next()) != head);
+ coins->releaseDeleted();
+}
+
+// please keep in sync with debugMergeMatches()
+// Look to see if pt-t linked list contains same segment more than once
+// if so, and if each pt-t is directly pointed to by spans in that segment,
+// merge them
+// keep the points, but remove spans so that the segment doesn't have 2 or more
+// spans pointing to the same pt-t loop at different loop elements
+void SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) {
+ SkOpPtT* test = &fPtT;
+ SkOpPtT* testNext;
+ const SkOpPtT* stop = test;
+ do {
+ testNext = test->next();
+ if (test->deleted()) {
+ continue;
+ }
+ SkOpSpanBase* testBase = test->span();
+ SkASSERT(testBase->ptT() == test);
+ SkOpSegment* segment = test->segment();
+ if (segment->done()) {
+ continue;
+ }
+ SkOpPtT* inner = opp->ptT();
+ const SkOpPtT* innerStop = inner;
+ do {
+ if (inner->segment() != segment) {
+ continue;
+ }
+ if (inner->deleted()) {
+ continue;
+ }
+ SkOpSpanBase* innerBase = inner->span();
+ SkASSERT(innerBase->ptT() == inner);
+ // when the intersection is first detected, the span base is marked if there are
+ // more than one point in the intersection.
+ if (!zero_or_one(inner->fT)) {
+ innerBase->upCast()->release(test);
+ } else {
+ SkASSERT(inner->fT != test->fT);
+ if (!zero_or_one(test->fT)) {
+ testBase->upCast()->release(inner);
+ } else {
+ segment->markAllDone(); // mark segment as collapsed
+ SkDEBUGCODE(testBase->debugSetDeleted());
+ test->setDeleted();
+ SkDEBUGCODE(innerBase->debugSetDeleted());
+ inner->setDeleted();
+ }
+ }
+#ifdef SK_DEBUG // assert if another undeleted entry points to segment
+ const SkOpPtT* debugInner = inner;
+ while ((debugInner = debugInner->next()) != innerStop) {
+ if (debugInner->segment() != segment) {
+ continue;
+ }
+ if (debugInner->deleted()) {
+ continue;
+ }
+ SkOPASSERT(0);
+ }
+#endif
+ break;
+ } while ((inner = inner->next()) != innerStop);
+ } while ((test = testNext) != stop);
+ this->checkForCollapsedCoincidence();
}
int SkOpSpan::computeWindSum() {
@@ -413,7 +490,7 @@ bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped) {
}
void SkOpSpan::release(const SkOpPtT* kept) {
- SkDEBUGCODE(fDeleted = true);
+ SkDEBUGCODE(fDebugDeleted = true);
SkASSERT(kept->span() != this);
SkASSERT(!final());
SkOpSpan* prev = this->prev();
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index 96a97e0732..7c7bf7c186 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -28,6 +28,8 @@ public:
kIsDuplicate = 1
};
+ const SkOpPtT* active() const;
+
// please keep in sync with debugAddOpp()
void addOpp(SkOpPtT* opp, SkOpPtT* oppPrev) {
SkOpPtT* oldNext = this->fNext;
@@ -55,7 +57,7 @@ public:
const SkOpCoincidence* debugCoincidence() const;
bool debugContains(const SkOpPtT* ) const;
const SkOpPtT* debugContains(const SkOpSegment* check) const;
- SkOpContour* debugContour(int id);
+ SkOpContour* debugContour(int id) const;
int debugLoopLimit(bool report) const;
bool debugMatchID(int id) const;
const SkOpPtT* debugOppPrev(const SkOpPtT* opp) const;
@@ -98,7 +100,8 @@ public:
bool onEnd() const;
- SkOpPtT* oppPrev(SkOpPtT* opp) const {
+ // returns nullptr if this is already in the opp ptT loop
+ SkOpPtT* oppPrev(const SkOpPtT* opp) const {
// find the fOpp ptr to opp
SkOpPtT* oppPrev = opp->fNext;
if (oppPrev == this) {
@@ -176,7 +179,8 @@ protected:
class SkOpSpanBase {
public:
- void addOppAndMerge(SkOpSpanBase* );
+ SkOpSpanBase* active();
+ void addOpp(SkOpSpanBase* opp);
void bumpSpanAdds() {
++fSpanAdds;
@@ -192,6 +196,7 @@ public:
return fCoinEnd;
}
+ bool collapsed(double s, double e) const;
bool contains(const SkOpSpanBase* ) const;
const SkOpPtT* contains(const SkOpSegment* ) const;
@@ -209,11 +214,6 @@ public:
bool containsCoinEnd(const SkOpSegment* ) const;
SkOpContour* contour() const;
-#if DEBUG_COINCIDENCE_VERBOSE
- void debugAddOppAndMerge(const char* id, SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* ,
- bool* del1, bool* del2) const;
-#endif
-
int debugBumpCount() {
return SkDEBUGRELEASE(++fCount, -1);
}
@@ -222,6 +222,9 @@ public:
return SkDEBUGRELEASE(fID, -1);
}
+#if DEBUG_COINCIDENCE_VERBOSE
+ void debugAddOpp(const char* id, SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* opp) const;
+#endif
bool debugAlignedEnd(double t, const SkPoint& pt) const;
bool debugAlignedInner() const;
const SkOpAngle* debugAngle(int id) const;
@@ -230,20 +233,25 @@ public:
#endif
const SkOpCoincidence* debugCoincidence() const;
bool debugCoinEndLoopCheck() const;
- SkOpContour* debugContour(int id);
+ SkOpContour* debugContour(int id) const;
#ifdef SK_DEBUG
- bool debugDeleted() const { return fDeleted; }
+ bool debugDeleted() const { return fDebugDeleted; }
#endif
#if DEBUG_COINCIDENCE_VERBOSE
void debugInsertCoinEnd(const char* id, SkPathOpsDebug::GlitchLog* ,
const SkOpSpanBase* ) const;
void debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog* ,
const SkPathOpsBounds& bounds, bool* deleted) const;
+ void debugMergeMatches(const char* id, SkPathOpsDebug::GlitchLog* log,
+ const SkOpSpanBase* opp) const;
#endif
const SkOpPtT* debugPtT(int id) const;
void debugResetCoinT() const;
const SkOpSegment* debugSegment(int id) const;
void debugSetCoinT(int ) const;
+#ifdef SK_DEBUG
+ void debugSetDeleted() { fDebugDeleted = true; }
+#endif
const SkOpSpanBase* debugSpan(int id) const;
const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const;
SkOpGlobalState* globalState() const;
@@ -285,6 +293,7 @@ public:
void merge(SkOpSpan* span);
void mergeContained(const SkPathOpsBounds& bounds);
+ void mergeMatches(SkOpSpanBase* opp);
const SkOpSpan* prev() const {
return fPrev;
@@ -403,7 +412,7 @@ protected: // no direct access to internals to avoid treating a span base as a
bool fChased; // set after span has been added to chase array
SkDEBUGCODE(int fCount); // number of pt/t pairs added
SkDEBUGCODE(int fID);
- SkDEBUGCODE(bool fDeleted); // set when span was merged with another span
+ SkDEBUGCODE(bool fDebugDeleted); // set when span was merged with another span
};
class SkOpSpan : public SkOpSpanBase {
@@ -445,15 +454,14 @@ public:
void debugInsertCoincidence(const char* , SkPathOpsDebug::GlitchLog* ,
const SkOpSegment* , bool flipped) const;
#endif
- void release(const SkOpPtT* );
+ void dumpCoin() const;
+ bool dumpSpan() const;
bool done() const {
SkASSERT(!final());
return fDone;
}
- void dumpCoin() const;
- bool dumpSpan() const;
void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
bool insertCoincidence(const SkOpSegment* , bool flipped);
@@ -496,6 +504,8 @@ public:
return fOppValue;
}
+ void release(const SkOpPtT* );
+
SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
void setDone(bool done) {
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 82b93f4072..c8ee84c54a 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -485,7 +485,7 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc
// look for coincidence present in A-B and A-C but missing in B-C
while (coincidence->addMissing()) {
if (!--safetyHatch) {
- SkASSERT(0); // FIXME: take this out after verifying std tests don't trigger
+ SkASSERT(globalState->debugSkipAssert());
return false;
}
DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing");
@@ -517,7 +517,6 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc
DEBUG_COINCIDENCE_HEALTH(contourList, "expand2");
// the expanded ranges may not align -- add the missing spans
if (!coincidence->addExpanded()) {
- SkASSERT(globalState->debugSkipAssert());
return false;
}
DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded3");
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 212e2bcc79..d099c4a985 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -12,6 +12,18 @@
#include "SkPathOpsDebug.h"
#include "SkString.h"
+#undef FAIL_IF
+#define FAIL_IF(cond, coin) \
+ do { if (cond) log->record(kAddExpandedFail_Glitch, id, coin); } while (false)
+
+#undef FAIL_WITH_NULL_IF
+#define FAIL_WITH_NULL_IF(cond, span) \
+ do { if (cond) log->record(kAddExpandedFail_Glitch, id, span); } while (false)
+
+#undef RETURN_FALSE_IF
+#define RETURN_FALSE_IF(cond, span) \
+ do { if (cond) log->record(kAddExpandedFail_Glitch, id, span); } while (false)
+
class SkCoincidentSpans;
#if DEBUG_VALIDATE
@@ -67,6 +79,7 @@ enum GlitchType {
kMarkCoinMissing_Glitch,
kMarkCoinStart_Glitch,
kMergeContained_Glitch,
+ kMergeMatches_Glitch,
kMissingCoin_Glitch,
kMissingDone_Glitch,
kMissingIntersection_Glitch,
@@ -331,6 +344,7 @@ void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) {
case kMarkCoinMissing_Glitch: SkDebugf(" MarkCoinMissing"); break;
case kMarkCoinStart_Glitch: SkDebugf(" MarkCoinStart"); break;
case kMergeContained_Glitch: SkDebugf(" MergeContained"); break;
+ case kMergeMatches_Glitch: SkDebugf(" MergeMatches"); break;
case kMissingCoin_Glitch: SkDebugf(" MissingCoin"); break;
case kMissingDone_Glitch: SkDebugf(" MissingDone"); break;
case kMissingIntersection_Glitch: SkDebugf(" MissingIntersection"); break;
@@ -580,9 +594,9 @@ void SkDRect::debugInit() {
#include "SkOpAngle.h"
#include "SkOpSegment.h"
-#if DEBUG_COINCIDENCE
+#if DEBUG_COINCIDENCE_VERBOSE
// commented-out lines keep this in sync with addT()
- const SkOpPtT* SkOpSegment::debugAddT(double t) const {
+ const SkOpPtT* SkOpSegment::debugAddT(double t, const char* id, SkPathOpsDebug::GlitchLog* log) const {
debugValidate();
SkPoint pt = this->ptAtT(t);
const SkOpSpanBase* span = &fHead;
@@ -594,7 +608,7 @@ void SkDRect::debugInit() {
}
if (t < result->fT) {
const SkOpSpan* prev = result->span()->prev();
- FAIL_WITH_NULL_IF(!prev);
+ FAIL_WITH_NULL_IF(!prev, span);
// marks in global state that new op span has been allocated
this->globalState()->setAllocatedOpSpan();
// span->init(this, prev, t, pt);
@@ -606,7 +620,7 @@ void SkDRect::debugInit() {
// span->bumpSpanAdds();
return nullptr;
}
- FAIL_WITH_NULL_IF(span != &fTail);
+ FAIL_WITH_NULL_IF(span != &fTail, span);
} while ((span = span->upCast()->next()));
SkASSERT(0);
return nullptr; // we never get here, but need this to satisfy compiler
@@ -776,7 +790,7 @@ void SkOpSegment::debugMissingCoincidence(const char* id, SkPathOpsDebug::Glitch
}
if (testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
// mark coincidence
-#if DEBUG_COINCIDENCE
+#if DEBUG_COINCIDENCE_VERBOSE
// SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
// rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
// rootOppEnd->debugID());
@@ -879,13 +893,8 @@ void SkOpSegment::debugMoveMultiples(const char* id, SkPathOpsDebug::GlitchLog*
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);
- glitches->record(kMoveMultiple_Glitch, id, oppTest, oppSpan);
- } else {
- glitches->record(kMoveMultiple_Glitch, id, oppSpan, oppTest);
- }
+ oppTest->debugMergeMatches(id, glitches, oppSpan);
+ oppTest->debugAddOpp(id, glitches, oppSpan);
oppSegment->debugValidate();
goto checkNextSpan;
}
@@ -1254,6 +1263,7 @@ void SkCoincidentSpans::debugStartCheck(const SkOpSpanBase* outer, const SkOpSpa
#if DEBUG_COINCIDENCE_VERBOSE
/* Commented-out lines keep this in sync with expand */
+// expand the range by checking adjacent spans for coincidence
bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* log) const {
bool expanded = false;
const SkOpSegment* segment = coinPtTStart()->segment();
@@ -1275,6 +1285,9 @@ bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* l
do {
const SkOpSpanBase* end = coinPtTEnd()->span();
SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
+ if (next && next->deleted()) {
+ break;
+ }
const SkOpPtT* oppPtT;
if (!next || !(oppPtT = next->contains(oppSegment))) {
break;
@@ -1289,9 +1302,6 @@ bool SkCoincidentSpans::debugExpand(const char* id, SkPathOpsDebug::GlitchLog* l
return expanded;
}
-#undef FAIL_IF
-#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
@@ -1309,7 +1319,8 @@ void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog
const SkOpSpanBase* oStart = oStartPtT->span();
const SkOpSpanBase* end = coin->coinPtTEnd()->span();
const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
- FAIL_IF(oEnd->deleted());
+ FAIL_IF(oEnd->deleted(), coin);
+ FAIL_IF(!start->upCastable(), coin);
const SkOpSpanBase* test = start->upCast()->next();
const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
if (!oTest) {
@@ -1320,12 +1331,12 @@ void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog
|| !oTest->ptT()->contains(start->segment())) {
// use t ranges to guess which one is missing
double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
- FAIL_IF(!startRange);
+ FAIL_IF(!startRange, coin);
double startPart = (test->t() - startPtT->fT) / startRange;
double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
- FAIL_IF(!oStartRange);
+ FAIL_IF(!oStartRange, coin);
double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
- FAIL_IF(startPart == oStartPart);
+ FAIL_IF(startPart == oStartPart, coin);
bool startOver = false;
if (startPart < oStartPart)
log->record(kAddExpandedCoin_Glitch, id, // strange debug formatting lines up with original
@@ -1342,6 +1353,9 @@ void SkOpCoincidence::debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog
}
}
if (test != end) {
+ if (!test->upCastable()) {
+ return;
+ }
test = test->upCast()->next();
}
if (oTest != oEnd) {
@@ -1393,12 +1407,15 @@ void SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* ov
if (coinSeg == oppSeg) {
return;
}
- return this->debugAddOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, id, log);
+ return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe);
}
/* 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 {
+// If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
+// If this is called by AddIfMissing(), a returned false indicates there was nothing to add
+void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLog* log,
+ const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
+ double coinTs, double coinTe, double oppTs, double oppTe) const {
SkTDArray<SkCoincidentSpans*> overlaps;
SkASSERT(!fTop); // this is (correctly) reversed in addifMissing()
if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
@@ -1427,77 +1444,63 @@ void SkOpCoincidence::debugAddOrOverlap(const SkOpSegment* coinSeg, const SkOpSe
: overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
log->record(kAddOrOverlap_Glitch, id, overlap, test->oppPtTEnd());
}
- if (!fHead) {
- SkAssertResult(true);
+ if (!fHead) { this->debugRelease(id, log, fHead, test);
+ this->debugRelease(id, log, fTop, test);
}
}
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);
+ RETURN_FALSE_IF(overlap && cs && ce && overlap->contains(cs, ce), coinSeg);
+ RETURN_FALSE_IF(cs != ce || !cs, coinSeg);
const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
- if (overlap && os && oe && overlap->contains(os, oe)) {
- return;
- }
+ RETURN_FALSE_IF(overlap && os && oe && overlap->contains(os, oe), oppSeg);
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;
- }
+ RETURN_FALSE_IF(csExisting && csExisting == ceExisting, coinSeg);
+ RETURN_FALSE_IF(csExisting && (csExisting == ce ||
+ csExisting->contains(ceExisting ? ceExisting : ce)), coinSeg);
+ RETURN_FALSE_IF(ceExisting && (ceExisting == cs ||
+ ceExisting->contains(csExisting ? csExisting : cs)), coinSeg);
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;
- }
+ RETURN_FALSE_IF(osExisting && osExisting == oeExisting, oppSeg);
+ RETURN_FALSE_IF(osExisting && (osExisting == oe ||
+ osExisting->contains(oeExisting ? oeExisting : oe)), oppSeg);
+ RETURN_FALSE_IF(oeExisting && (oeExisting == os ||
+ oeExisting->contains(osExisting ? osExisting : os)), oppSeg);
bool csDeleted = false, osDeleted = false, ceDeleted = false, oeDeleted = false;
this->debugValidate();
if (!cs || !os) {
if (!cs)
- cs = coinSeg->debugAddT(coinTs);
+ cs = coinSeg->debugAddT(coinTs, id, log);
if (!os)
- os = oppSeg->debugAddT(oppTs);
- if (cs && os) cs->span()->debugAddOppAndMerge(id, log, os->span(), &csDeleted, &osDeleted);
+ os = oppSeg->debugAddT(oppTs, id, log);
+// RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable);
+ if (cs && os) cs->span()->debugAddOpp(id, log, os->span());
// cs = csWritable;
-// os = osWritable;
- if ((ce && ce->deleted()) || (oe && oe->deleted())) {
- return;
- }
+// os = osWritable->active();
+ RETURN_FALSE_IF((ce && ce->deleted()) || (oe && oe->deleted()), coinSeg);
}
if (!ce || !oe) {
if (!ce)
- ce = coinSeg->debugAddT(coinTe);
+ ce = coinSeg->debugAddT(coinTe, id, log);
if (!oe)
- oe = oppSeg->debugAddT(oppTe);
- if (ce && oe) ce->span()->debugAddOppAndMerge(id, log, oe->span(), &ceDeleted, &oeDeleted);
+ oe = oppSeg->debugAddT(oppTe, id, log);
+ if (ce && oe) ce->span()->debugAddOpp(id, log, oe->span());
// ce = ceWritable;
// oe = oeWritable;
}
this->debugValidate();
- if (csDeleted || osDeleted || ceDeleted || oeDeleted) {
- return;
- }
- if (!cs || !ce || cs->contains(ce) || !os || !oe || os->contains(oe)) {
- return;
- }
+ RETURN_FALSE_IF(csDeleted, coinSeg);
+ RETURN_FALSE_IF(osDeleted, oppSeg);
+ RETURN_FALSE_IF(ceDeleted, coinSeg);
+ RETURN_FALSE_IF(oeDeleted, oppSeg);
+ RETURN_FALSE_IF(!cs || !ce || cs->contains(ce) || !os || !oe || os->contains(oe), coinSeg);
// bool result = true;
if (overlap) {
if (overlap->coinPtTStart()->segment() == coinSeg) {
@@ -1599,6 +1602,27 @@ void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog*
}
// Commented-out lines keep this in sync with release()
+void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* coin, const SkCoincidentSpans* remove) const {
+ const SkCoincidentSpans* head = coin;
+ const SkCoincidentSpans* prev = nullptr;
+ const SkCoincidentSpans* next;
+ do {
+ next = coin->next();
+ if (coin == remove) {
+ if (prev) {
+// prev->setNext(next);
+ } else if (head == fHead) {
+// fHead = next;
+ } else {
+// fTop = next;
+ }
+ log->record(kReleasedSpan_Glitch, id, coin);
+ }
+ prev = coin;
+ } while ((coin = next));
+ return;
+}
+
void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* deleted) const {
const SkCoincidentSpans* coin = fHead;
if (!coin) {
@@ -1614,6 +1638,7 @@ void SkOpCoincidence::debugRelease(const char* id, SkPathOpsDebug::GlitchLog* lo
} 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
@@ -1626,7 +1651,10 @@ void SkOpCoincidence::debugReorder(const char* id, SkPathOpsDebug::GlitchLog* lo
do {
// most commonly, concidence are one span long; check for that first
int intervals = coin->spanCount();
- if (intervals = 1) {
+ if (intervals <= 0) {
+ return;
+ }
+ if (1 == intervals) {
#if DEBUG_COINCIDENCE_VERBOSE
// SkASSERT(!coin->debugExpand(nullptr, nullptr));
#endif
@@ -1709,6 +1737,9 @@ void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log)
return;
}
do {
+ if (!coin->coinPtTStartWritable()->span()->upCastable()) {
+ return;
+ }
const SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
// SkASSERT(start->deleted());
const SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
@@ -1730,11 +1761,17 @@ void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log)
const SkOpSpanBase* next = start;
const SkOpSpanBase* oNext = oStart;
while ((next = next->upCast()->next()) != end) {
+ if (!next->upCastable()) {
+ return;
+ }
if (next->upCast()->debugInsertCoincidence(id, log, oSegment, flipped), false) {
return;
}
}
while ((oNext = oNext->upCast()->next()) != oEnd) {
+ if (!oNext->upCastable()) {
+ return;
+ }
if (oNext->upCast()->debugInsertCoincidence(id, log, segment, flipped), false) {
return;
}
@@ -1747,6 +1784,7 @@ void SkOpCoincidence::debugMark(const char* id, SkPathOpsDebug::GlitchLog* log)
#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 {
+ const SkCoincidentSpans* head = coin;
while (coin) {
if (coin->collapsed(test)) {
if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
@@ -1755,6 +1793,7 @@ void SkOpCoincidence::debugMarkCollapsed(const char* id, SkPathOpsDebug::GlitchL
if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
log->record(kCollapsedCoin_Glitch, id, coin);
}
+ this->debugRelease(id, log, head, coin);
}
coin = coin->next();
}
@@ -2035,27 +2074,16 @@ void SkOpSegment::debugValidate() const {
}
#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 {
- const SkOpPtT* oppPrev = this->ptT()->debugOppPrev(opp->ptT());
- if (oppPrev) {
- this->ptT()->debugAddOpp(opp->ptT(), oppPrev);
- this->debugCheckForCollapsedCoincidence(id, log);
- }
- // 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()) {
+
+// Commented-out lines keep this in sync with addOpp()
+void SkOpSpanBase::debugAddOpp(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
+ const SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
+ if (!oppPrev) {
return;
}
- this->debugMergeContained(id, log, bounds, spanDeleted);
- opp->debugMergeContained(id, log, bounds, oppDeleted);
+ this->debugMergeMatches(id, log, opp);
+ this->ptT()->debugAddOpp(opp->ptT(), oppPrev);
+ this->debugCheckForCollapsedCoincidence(id, log);
}
// Commented-out lines keep this in sync with checkForCollapsedCoincidence()
@@ -2151,6 +2179,76 @@ void SkOpSpanBase::debugMergeContained(const char* id, SkPathOpsDebug::GlitchLog
// this->globalState()->coincidence()->debugValidate();
#endif
}
+
+// Commented-out lines keep this in sync with mergeMatches()
+// Look to see if pt-t linked list contains same segment more than once
+// if so, and if each pt-t is directly pointed to by spans in that segment,
+// merge them
+// keep the points, but remove spans so that the segment doesn't have 2 or more
+// spans pointing to the same pt-t loop at different loop elements
+void SkOpSpanBase::debugMergeMatches(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSpanBase* opp) const {
+ const SkOpPtT* test = &fPtT;
+ const SkOpPtT* testNext;
+ const SkOpPtT* stop = test;
+ do {
+ testNext = test->next();
+ if (test->deleted()) {
+ continue;
+ }
+ const SkOpSpanBase* testBase = test->span();
+ SkASSERT(testBase->ptT() == test);
+ const SkOpSegment* segment = test->segment();
+ if (segment->done()) {
+ continue;
+ }
+ const SkOpPtT* inner = opp->ptT();
+ const SkOpPtT* innerStop = inner;
+ do {
+ if (inner->segment() != segment) {
+ continue;
+ }
+ if (inner->deleted()) {
+ continue;
+ }
+ const SkOpSpanBase* innerBase = inner->span();
+ SkASSERT(innerBase->ptT() == inner);
+ // when the intersection is first detected, the span base is marked if there are
+ // more than one point in the intersection.
+// if (!innerBase->hasMultipleHint() && !testBase->hasMultipleHint()) {
+ if (!zero_or_one(inner->fT)) {
+ log->record(kMergeMatches_Glitch, id, innerBase, test);
+ } else {
+ SkASSERT(inner->fT != test->fT);
+ if (!zero_or_one(test->fT)) {
+ log->record(kMergeMatches_Glitch, id, testBase, inner);
+ } else {
+ log->record(kMergeMatches_Glitch, id, segment);
+// SkDEBUGCODE(testBase->debugSetDeleted());
+// test->setDeleted();
+// SkDEBUGCODE(innerBase->debugSetDeleted());
+// inner->setDeleted();
+ }
+ }
+#ifdef SK_DEBUG // assert if another undeleted entry points to segment
+ const SkOpPtT* debugInner = inner;
+ while ((debugInner = debugInner->next()) != innerStop) {
+ if (debugInner->segment() != segment) {
+ continue;
+ }
+ if (debugInner->deleted()) {
+ continue;
+ }
+ SkOPASSERT(0);
+ }
+#endif
+ break;
+// }
+ break;
+ } while ((inner = inner->next()) != innerStop);
+ } while ((test = testNext) != stop);
+ this->debugCheckForCollapsedCoincidence(id, log);
+}
+
#endif
void SkOpSpanBase::debugResetCoinT() const {
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 5ea1dd8b26..bdfd3a43a1 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -37,7 +37,7 @@
if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
-#define DEBUG_UNDER_DEVELOPMENT 01
+#define DEBUG_UNDER_DEVELOPMENT 1
#if FORCE_RELEASE
@@ -78,7 +78,7 @@
#define DEBUG_ANGLE 1
#define DEBUG_ASSEMBLE 1
#define DEBUG_COINCIDENCE 01
-#define DEBUG_COINCIDENCE_ORDER 0
+#define DEBUG_COINCIDENCE_ORDER 01
#define DEBUG_COINCIDENCE_VERBOSE 01
#define DEBUG_CUBIC_BINARY_SEARCH 0
#define DEBUG_CUBIC_SPLIT 1
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index f30f155e8f..f314f69d0e 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -144,6 +144,26 @@ struct SkDPoint {
// note: this can not be implemented with
// return approximately_equal(a.fY, fY) && approximately_equal(a.fX, fX);
// because that will not take the magnitude of the values into account
+ bool approximatelyDEqual(const SkDPoint& a) const {
+ if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) {
+ return true;
+ }
+ if (!RoughlyEqualUlps(fX, a.fX) || !RoughlyEqualUlps(fY, a.fY)) {
+ return false;
+ }
+ double dist = distance(a); // OPTIMIZATION: can we compare against distSq instead ?
+ double tiniest = SkTMin(SkTMin(SkTMin(fX, a.fX), fY), a.fY);
+ double largest = SkTMax(SkTMax(SkTMax(fX, a.fX), fY), a.fY);
+ largest = SkTMax(largest, -tiniest);
+ return AlmostDequalUlps(largest, largest + dist); // is the dist within ULPS tolerance?
+ }
+
+ bool approximatelyDEqual(const SkPoint& a) const {
+ SkDPoint dA;
+ dA.set(a);
+ return approximatelyDEqual(dA);
+ }
+
bool approximatelyEqual(const SkDPoint& a) const {
if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) {
return true;
@@ -233,6 +253,15 @@ struct SkDPoint {
return RoughlyEqualUlps((double) largest, largest + dist); // is dist within ULPS tolerance?
}
+ // very light weight check, should only be used for inequality check
+ static bool WayRoughlyEqual(const SkPoint& a, const SkPoint& b) {
+ float largestNumber = SkTMax(SkTAbs(a.fX), SkTMax(SkTAbs(a.fY),
+ SkTMax(SkTAbs(b.fX), SkTAbs(b.fY))));
+ SkVector diffs = a - b;
+ float largestDiff = SkTMax(diffs.fX, diffs.fY);
+ return roughly_zero_when_compared_to(largestDiff, largestNumber);
+ }
+
// utilities callable by the user from the debugger when the implementation code is linked in
void dump() const;
static void Dump(const SkPoint& pt);
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index a645771634..aac32b2087 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -76,7 +76,7 @@ public:
#ifdef SK_DEBUG
const class SkOpAngle* debugAngle(int id) const;
const SkOpCoincidence* debugCoincidence() const;
- SkOpContour* debugContour(int id);
+ SkOpContour* debugContour(int id) const;
const class SkOpPtT* debugPtT(int id) const;
bool debugRunFail() const;
const class SkOpSegment* debugSegment(int id) const;
@@ -197,10 +197,16 @@ private:
};
#ifdef SK_DEBUG
+#if DEBUG_COINCIDENCE
+#define SkOPASSERT(cond) SkASSERT((this->globalState() && \
+ (this->globalState()->debugCheckHealth() || \
+ this->globalState()->debugSkipAssert())) || (cond))
+#else
#define SkOPASSERT(cond) SkASSERT((this->globalState() && \
- this->globalState()->debugSkipAssert()) || cond)
+ this->globalState()->debugSkipAssert()) || (cond))
+#endif
#define SkOPOBJASSERT(obj, cond) SkASSERT((obj->debugGlobalState() && \
- obj->debugGlobalState()->debugSkipAssert()) || cond)
+ obj->debugGlobalState()->debugSkipAssert()) || (cond))
#else
#define SkOPASSERT(cond)
#define SkOPOBJASSERT(obj, cond)
@@ -529,10 +535,6 @@ inline bool more_roughly_equal(double x, double y) {
return fabs(x - y) < MORE_ROUGH_EPSILON;
}
-inline bool way_roughly_equal(double x, double y) {
- return fabs(x - y) < WAY_ROUGH_EPSILON;
-}
-
struct SkDPoint;
struct SkDVector;
struct SkDLine;
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-01 20:49:17 +0000