pathops coincident work

src/pathops/SkOpCoincidence.cpp

 /*
  * Copyright 2015 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 "SkOpSegment.h"
 #include "SkPathOpsTSect.h"
 
@@ skipping 232 matching lines @@
         return;
     }
     SkASSERT(Ordered(coinPtTStart, oppPtTStart));
     // choose the ptT at the front of the list to track
     coinPtTStart = coinPtTStart->span()->ptT();
     coinPtTEnd = coinPtTEnd->span()->ptT();
     oppPtTStart = oppPtTStart->span()->ptT();
     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(
             this->globalState()->allocator());
     coinRec->init(SkDEBUGCODE(fGlobalState));
     coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd
             SkDEBUGPARAMS(fGlobalState->nextCoinID()));
     fHead = coinRec;
 }
 
@@ skipping 27 matching lines @@
             if (!between(0, t, 1)) {
                 continue;
             }
             SkDPoint oppPt = i.pt(index);
             if (!oppPt.approximatelyEqual(pt)) {
                 continue;
             }
             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;
             }
             SkOpSegment* coinSeg = base->segment();
             SkOpSegment* oppSeg = oppStart->segment();
             double coinTs, coinTe, oppTs, oppTe;
             if (coinSeg < oppSeg) {
                 coinTs = base->t();
                 coinTe = testSpan->t();
                 oppTs = oppStart->fT;
@@ skipping 104 matching lines @@
         SkASSERT(startPtT->contains(oStartPtT));
         SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
         const SkOpSpanBase* start = startPtT->span();
         const SkOpSpanBase* oStart = oStartPtT->span();
         const SkOpSpanBase* end = coin->coinPtTEnd()->span();
         const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
         FAIL_IF(oEnd->deleted());
         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())) {
                 // use t ranges to guess which one is missing
                 double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
                 FAIL_IF(!startRange);
                 double startPart = (test->t() - startPtT->fT) / startRange;
                 double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
                 FAIL_IF(!oStartRange);
                 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
                 FAIL_IF(startPart == oStartPart);
                 bool startOver = false;
                 bool success = startPart < oStartPart
                         ? oStart->segment()->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()));
     return true;
 }
 
 // checks to see if coincidence has already been found
 bool SkOpCoincidence::alreadyAdded(const SkCoincidentSpans* check, const SkCoincidentSpans* outer,
         const SkOpPtT* over1s, const SkOpPtT* over1e) const {
     do {
@@ skipping 93 matching lines @@
         *overlaps->append() = check; // partial overlap, extend existing entry
     } while ((check = check->next()));
     return true;
 }
 
 /* Please keep this in sync with debugAddIfMissing() */
 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);
     }
     if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
         SkTSwap(oppTs, oppTe);
     }
     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 */ );
 }
 
 /* Please keep this in sync with debugAddOrOverlap() */
 // 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
 bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
         double coinTs, double coinTe, double oppTs, double oppTe
         SkDEBUGPARAMS(bool callerAborts)) {
@@ skipping 55 matching lines @@
     RETURN_FALSE_IF(callerAborts, oeExisting && (oeExisting == os ||
             oeExisting->contains(osExisting ? osExisting : os)));
     // extra line in debug code
     this->debugValidate();
     if (!cs || !os) {
         SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
             : coinSeg->addT(coinTs);
         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) {
         SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
             : 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;
     }
     this->debugValidate();
     RETURN_FALSE_IF(callerAborts, cs->deleted());
     RETURN_FALSE_IF(callerAborts, os->deleted());
     RETURN_FALSE_IF(callerAborts, ce->deleted());
     RETURN_FALSE_IF(callerAborts, oe->deleted());
     RETURN_FALSE_IF(callerAborts, cs->contains(ce) || os->contains(oe));
     bool result = true;
@@ skipping 438 matching lines @@
             } else {
                 fTop = next;
             }
             break;
         }
         prev = coin;
     } while ((coin = next));
     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
 // reordering the ptT pairs
 bool SkOpCoincidence::reorder() {
     SkCoincidentSpans* coin = fHead;
     if (!coin) {
         return true;
     }
     do {
@@ skipping 35 matching lines @@
         SkCoincidentSpans* test = *headPtr;
         if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) {
             *headPtr = test->next();
             continue;
         }
         headPtr = (*headPtr)->nextPtr();
     }
 }
 
 // Please keep this in sync with debugExpand()
+// expand the range by checking adjacent spans for coincidence
 bool SkOpCoincidence::expand() {
     SkCoincidentSpans* coin = fHead;
     if (!coin) {
         return false;
     }
     bool expanded = false;
     do {
         if (coin->expand()) {
             // check to see if multiple spans expanded so they are now identical
             SkCoincidentSpans* test = fHead;
@@ skipping 238 matching lines @@
             this->release(fHead, coin);
         }
     } while ((coin = coin->next()));
 }
 
 bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
         const SkOpPtT* testE) const {
     return testS->segment()->testForCoincidence(testS, testE, testS->span(),
             testE->span(), outer->coinPtTStart()->segment());
 }