pathops coincident work

src/pathops/SkOpSpan.cpp

Index: src/pathops/SkOpSpan.cpp
diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp
index 98165fcfc53c08458d942dfddff78c9a58e468d2..162bcad2937b74aa5e62b0999a499acf6fbee588 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();