pathops coincident work

src/pathops/SkOpSpan.cpp

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkOpCoincidence.h"
 #include "SkOpContour.h"
 #include "SkOpSegment.h"
 #include "SkPathWriter.h"
 
 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;
     }
     SkASSERT(this != check);
     const SkOpSegment* segment = this->segment();
     SkASSERT(segment == check->segment());
     return segment->collapsed();
 }
 
@@ skipping 144 matching lines @@
 SkOpSegment* SkOpPtT::segment() {
     return span()->segment();
 }
 
 void SkOpPtT::setDeleted() {
     SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this);
     SkOPASSERT(!fDeleted);
     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()
 void SkOpSpanBase::mergeContained(const SkPathOpsBounds& bounds) {
     // while adjacent spans' points are contained by the bounds, merge them
     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;
     SkOPASSERT(start != check);
     const SkOpPtT* walk = start;
     while ((walk = walk->next()) != start) {
         if (walk == check) {
             return true;
         }
     }
@@ skipping 37 matching lines @@
     fSegment = segment;
     fPtT.init(this, t, pt, false);
     fCoinEnd = this;
     fFromAngle = nullptr;
     fPrev = prev;
     fSpanAdds = 0;
     fAligned = true;
     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
 // this does not compute the best t or pt value; this merely moves all data into a single list
 void SkOpSpanBase::merge(SkOpSpan* span) {
     SkOpPtT* spanPtT = span->ptT();
     SkASSERT(this->t() != spanPtT->fT);
     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();
     this->ptT()->insert(spanPtT);
     while (remainder != spanPtT) {
         SkOpPtT* next = remainder->next();
         SkOpPtT* compare = spanPtT->next();
         while (compare != spanPtT) {
             SkOpPtT* nextC = compare->next();
             if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
                 goto tryNextRemainder;
             }
             compare = nextC;
         }
         spanPtT->insert(remainder);
 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()
 void SkOpSpanBase::checkForCollapsedCoincidence() {
     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
     SkOpPtT* head = this->ptT();
     SkOpPtT* test = head;
     do {
         if (!test->coincident()) {
             continue;
         }
         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() {
     SkOpGlobalState* globals = this->globalState();
     SkOpContour* contourHead = globals->contourHead();
     int windTry = 0;
     while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
         ;
     }
     return this->windSum();
@@ skipping 49 matching lines @@
             return true;
         }
     }
 #if DEBUG_COINCIDENCE
     SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment...
 #endif
     return true;
 }
 
 void SkOpSpan::release(const SkOpPtT* kept) {
-    SkDEBUGCODE(fDeleted = true);
+    SkDEBUGCODE(fDebugDeleted = true);
     SkASSERT(kept->span() != this);
     SkASSERT(!final());
     SkOpSpan* prev = this->prev();
     SkASSERT(prev);
     SkOpSpanBase* next = this->next();
     SkASSERT(next);
     prev->setNext(next);
     next->setPrev(prev);
     this->segment()->release(this);
     SkOpCoincidence* coincidence = this->globalState()->coincidence();
@@ skipping 23 matching lines @@
 
 void SkOpSpan::setWindSum(int windSum) {
     SkASSERT(!final());
     if (fWindSum != SK_MinS32 && fWindSum != windSum) {
         this->globalState()->setWindingFailed();
         return;
     }
     SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM);
     fWindSum = windSum;
 }