pathops tiger checkpoint

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 128 matching lines @@
     const SkOpSpanBase* oppStart = (flipped() ? oppPtTEnd() : oppPtTStart())->span();
     const SkOpSpanBase* oppEnd = (flipped() ? oppPtTStart() : oppPtTEnd())->span();
     int oppIntervals = 0;
     while (oppStart != oppEnd) {
         oppIntervals++;
         oppStart = oppStart->upCast()->next();
     }
     return coinIntervals == oppIntervals ? coinIntervals : -1;
 }
 
+// A coincident span is unordered if the pairs of points in the main and opposite curves'
+// t values do not ascend or descend. For instance, if a tightly arced quadratic is
+// coincident with another curve, it may intersect it out of order.
+bool SkCoincidentSpans::ordered() const {
+    const SkOpSpanBase* start = this->coinPtTStart()->span();
+    const SkOpSpanBase* end = this->coinPtTEnd()->span();
+    const SkOpSpanBase* next = start->upCast()->next();
+    if (next == end) {
+        return true;
+    }
+    bool flipped = this->flipped();
+    const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
+    double oppLastT = fOppPtTStart->fT;
+    do {
+        const SkOpPtT* opp = next->contains(oppSeg);
+        if (!opp) {
+            SkASSERT(0);  // may assert if coincident span isn't fully processed
+            continue;
+        }
+        if ((oppLastT > opp->fT) != flipped) {
+            return false;
+        }
+        oppLastT = opp->fT;
+        if (next == end) {
+            break;
+        }
+        next = next->upCast()->next();
+    } while (true);
+    return true;
+}
+
 // returns true if the point is on a coincident edge, and if it is the start of that edge
 bool SkOpCoincidence::edge(const SkOpPtT* test, bool* start) const {
     SkCoincidentSpans* coinRec = fHead;
     if (!coinRec) {
         return false;
     }
     do {
         if (coinRec->coinPtTStart() == test) {
             *start = true;
             return true;
@@ skipping 158 matching lines @@
                 SkTSwap(coinSeg, oppSeg);
                 coinTs = oppStart->fT;
                 coinTe = testPtT->fT;
                 oppTs = base->t();
                 oppTe = testSpan->t();
             }
             if (coinTs > coinTe) {
                 SkTSwap(coinTs, coinTe);
                 SkTSwap(oppTs, oppTe);
             }
-            if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
-                    SkDEBUGPARAMS(true) /* do assert if addOrOverlap fails */ )) {
+            bool added;
+            if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) {
                 return false;
             }
         }
     }
     return true;
 }
 
 // description below
 bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
     FAIL_IF(!ptT->span()->upCastable());
@@ skipping 260 matching lines @@
         if (check->oppPtTStart()->segment() != oppSeg) {
             continue;
         }
         double checkTs = check->coinPtTStart()->fT;
         double checkTe = check->coinPtTEnd()->fT;
         bool coinOutside = coinTe < checkTs || coinTs > checkTe;
         double oCheckTs = check->oppPtTStart()->fT;
         double oCheckTe = check->oppPtTEnd()->fT;
         if (swapOpp) {
             if (oCheckTs <= oCheckTe) {
-              return false;
+                return false;
             }
             SkTSwap(oCheckTs, oCheckTe);
         }
         bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe;
         if (coinOutside && oppOutside) {
             continue;
         }
         bool coinInside = coinTe <= checkTe && coinTs >= checkTs;
         bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs;
-        if (coinInside && oppInside) {
-            return false;  // complete overlap, already included, do nothing
+        if (coinInside && oppInside) {  // already included, do nothing
+            return false;
         }
         *overlaps->append() = check; // partial overlap, extend existing entry
     } while ((check = check->next()));
     return true;
 }
 
 /* Please keep this in sync with debugAddIfMissing() */
 // note that over1s, over1e, over2s, over2e are ordered
 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
-        double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg  
+        double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added  
         SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
     SkASSERT(tStart < tEnd);
     SkASSERT(over1s->fT < over1e->fT);
     SkASSERT(between(over1s->fT, tStart, over1e->fT));
     SkASSERT(between(over1s->fT, tEnd, over1e->fT));
     SkASSERT(over2s->fT < over2e->fT);
     SkASSERT(between(over2s->fT, tStart, over2e->fT));
     SkASSERT(between(over2s->fT, tEnd, over2e->fT));
     SkASSERT(over1s->segment() == over1e->segment());
     SkASSERT(over2s->segment() == over2e->segment());
     SkASSERT(over1s->segment() == over2s->segment());
     SkASSERT(over1s->segment() != coinSeg);
     SkASSERT(over1s->segment() != oppSeg);
     SkASSERT(coinSeg != oppSeg);
     double coinTs, coinTe, oppTs, oppTe;
     coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
     coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
     if (coinSeg->collapsed(coinTs, coinTe)) {
-        return false;
+        return true;
     }
     oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
     oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
     if (oppSeg->collapsed(oppTs, oppTe)) {
-        return false;
+        return true;
     }
     if (coinTs > coinTe) {
         SkTSwap(coinTs, coinTe);
         SkTSwap(oppTs, oppTe);
     }
-    return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
-            SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ );
+    return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
 }
 
 /* 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)) {
+        double coinTs, double coinTe, double oppTs, double oppTe, bool* added) {
     SkTDArray<SkCoincidentSpans*> overlaps;
-    RETURN_FALSE_IF(callerAborts, !fTop);
+    FAIL_IF(!fTop);
     if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
-        return false;
+        return true;
     }
     if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
             coinTe, oppTs, oppTe, &overlaps)) {
-        return false;
+        return true;
     }
     SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
     for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
         SkCoincidentSpans* test = overlaps[index];
         if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
             overlap->setCoinPtTStart(test->coinPtTStart());
         }
         if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
             overlap->setCoinPtTEnd(test->coinPtTEnd());
         }
         if (overlap->flipped()
                 ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
                 : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
             overlap->setOppPtTStart(test->oppPtTStart());
         }
         if (overlap->flipped()
                 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
                 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
             overlap->setOppPtTEnd(test->oppPtTEnd());
         }
         if (!fHead || !this->release(fHead, test)) {
             SkAssertResult(this->release(fTop, test));
         }
     }
     const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
     const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
-    RETURN_FALSE_IF(callerAborts, overlap && cs && ce && overlap->contains(cs, ce));
-    RETURN_FALSE_IF(callerAborts, cs == ce && cs);
+    if (overlap && cs && ce && overlap->contains(cs, ce)) {
+        return true;
+    }
+    FAIL_IF(cs == ce && cs);
     const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
     const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
-    RETURN_FALSE_IF(callerAborts, overlap && os && oe && overlap->contains(os, oe));
+    if (overlap && os && oe && overlap->contains(os, oe)) {
+        return true;
+    }
     SkASSERT(!cs || !cs->deleted());
     SkASSERT(!os || !os->deleted());
     SkASSERT(!ce || !ce->deleted());
     SkASSERT(!oe || !oe->deleted());
     const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
     const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
-    RETURN_FALSE_IF(callerAborts, csExisting && csExisting == ceExisting);
-    RETURN_FALSE_IF(callerAborts, csExisting && (csExisting == ce ||
+    FAIL_IF(csExisting && csExisting == ceExisting);
+    FAIL_IF(csExisting && (csExisting == ce ||
             csExisting->contains(ceExisting ? ceExisting : ce)));
-    RETURN_FALSE_IF(callerAborts, ceExisting && (ceExisting == cs ||
+    FAIL_IF(ceExisting && (ceExisting == cs ||
             ceExisting->contains(csExisting ? csExisting : cs)));
     const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
     const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
-    RETURN_FALSE_IF(callerAborts, osExisting && osExisting == oeExisting);
-    RETURN_FALSE_IF(callerAborts, osExisting && (osExisting == oe ||
+    FAIL_IF(osExisting && osExisting == oeExisting);
+    FAIL_IF(osExisting && (osExisting == oe ||
             osExisting->contains(oeExisting ? oeExisting : oe)));
-    RETURN_FALSE_IF(callerAborts, oeExisting && (oeExisting == os ||
+    FAIL_IF(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);
+        FAIL_IF(!csWritable || !osWritable);
         csWritable->span()->addOpp(osWritable->span());
         cs = csWritable;
         os = osWritable->active();
-        RETURN_FALSE_IF(callerAborts, (ce && ce->deleted()) || (oe && oe->deleted()));
+        FAIL_IF((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()->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));
+    FAIL_IF(cs->deleted());
+    FAIL_IF(os->deleted());
+    FAIL_IF(ce->deleted());
+    FAIL_IF(oe->deleted());
+    FAIL_IF(cs->contains(ce) || os->contains(oe));
     bool result = true;
     if (overlap) {
         if (overlap->coinPtTStart()->segment() == coinSeg) {
             result = overlap->extend(cs, ce, os, oe);
         } else {
             if (os->fT > oe->fT) {
                 SkTSwap(cs, ce);
                 SkTSwap(os, oe);
             }
             result = overlap->extend(os, oe, cs, ce);
         }
 #if DEBUG_COINCIDENCE_VERBOSE
         if (result) {
             overlaps[0]->debugShow();
         }
 #endif
     } else {
         this->add(cs, ce, os, oe);
 #if DEBUG_COINCIDENCE_VERBOSE
         fHead->debugShow();
 #endif
     }
     this->debugValidate();
-    return result;
+    if (result) {
+        *added = true;
+    }
+    return true;
 }
 
 // Please keep this in sync with debugAddMissing()
 /* 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
-bool SkOpCoincidence::addMissing() {
+bool SkOpCoincidence::addMissing(bool* added) {
     SkCoincidentSpans* outer = fHead;
+    *added = false;
     if (!outer) {
-        return false;
+        return true;
     }
-    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 SkOpPtT* ocs = outer->coinPtTStart();
         SkASSERT(!ocs->deleted());
         const SkOpSegment* outerCoin = ocs->segment();
         SkASSERT(!outerCoin->done());  // if it's done, should have already been removed from list
         const SkOpPtT* oos = outer->oppPtTStart();
         if (oos->deleted()) {
-            return false;
+            return true;
         }
         const SkOpSegment* outerOpp = oos->segment();
         SkASSERT(!outerOpp->done());
         SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
         SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
         SkCoincidentSpans* inner = outer;
         while ((inner = inner->next())) {
             this->debugValidate();
             double overS, overE;
             const SkOpPtT* ics = inner->coinPtTStart();
             SkASSERT(!ics->deleted());
             const SkOpSegment* innerCoin = ics->segment();
             SkASSERT(!innerCoin->done());
             const SkOpPtT* ios = inner->oppPtTStart();
             SkASSERT(!ios->deleted());
             const SkOpSegment* innerOpp = ios->segment();
             SkASSERT(!innerOpp->done());
             SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
             SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
             if (outerCoin == innerCoin) {
                 const SkOpPtT* oce = outer->coinPtTEnd();
                 if (oce->deleted()) {
-                    return false;
+                    return true;
                 }
                 const SkOpPtT* ice = inner->coinPtTEnd();
                 SkASSERT(!ice->deleted());
                 if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
-                    added |= this->addIfMissing(ocs->starter(oce), ics->starter(ice),
-                            overS, overE, outerOppWritable, innerOppWritable
+                    (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice),
+                            overS, overE, outerOppWritable, innerOppWritable, added
                             SkDEBUGPARAMS(ocs->debugEnder(oce))
                             SkDEBUGPARAMS(ics->debugEnder(ice)));
                 }
             } else if (outerCoin == innerOpp) {
                 const SkOpPtT* oce = outer->coinPtTEnd();
                 SkASSERT(!oce->deleted());
                 const SkOpPtT* ioe = inner->oppPtTEnd();
                 SkASSERT(!ioe->deleted());
                 if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
-                    added |= this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
-                            overS, overE, outerOppWritable, innerCoinWritable
+                    (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
+                            overS, overE, outerOppWritable, innerCoinWritable, added
                             SkDEBUGPARAMS(ocs->debugEnder(oce))
                             SkDEBUGPARAMS(ios->debugEnder(ioe)));
                 }
             } else if (outerOpp == innerCoin) {
                 const SkOpPtT* ooe = outer->oppPtTEnd();
                 SkASSERT(!ooe->deleted());
                 const SkOpPtT* ice = inner->coinPtTEnd();
                 SkASSERT(!ice->deleted());
                 SkASSERT(outerCoin != innerOpp);
                 if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
-                    added |= this->addIfMissing(oos->starter(ooe), ics->starter(ice),
-                            overS, overE, outerCoinWritable, innerOppWritable
+                    (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice),
+                            overS, overE, outerCoinWritable, innerOppWritable, added
                             SkDEBUGPARAMS(oos->debugEnder(ooe))
                             SkDEBUGPARAMS(ics->debugEnder(ice)));
                 }
             } else if (outerOpp == innerOpp) {
                 const SkOpPtT* ooe = outer->oppPtTEnd();
                 SkASSERT(!ooe->deleted());
                 const SkOpPtT* ioe = inner->oppPtTEnd();
                 if (ioe->deleted()) {
-                    return false;
+                    return true;
                 }
                 SkASSERT(outerCoin != innerCoin);
                 if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
-                    added |= this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
-                            overS, overE, outerCoinWritable, innerCoinWritable
+                    (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
+                            overS, overE, outerCoinWritable, innerCoinWritable, added
                             SkDEBUGPARAMS(oos->debugEnder(ooe))
                             SkDEBUGPARAMS(ios->debugEnder(ioe)));
                 }
             }
             this->debugValidate();
         }
     } while ((outer = outer->next()));
     this->restoreHead();
-    return added;
+    return true;
 }
 
 bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
         const SkOpSegment* seg2, const SkOpSegment* seg2o,
         const SkOpPtT* overS, const SkOpPtT* overE) {
     const SkOpPtT* s1, * e1, * s2, * e2;
     if (!(s1 = overS->find(seg1))) {
         return true;
     }
     if (!(e1 = overE->find(seg1))) {
@@ skipping 559 matching lines @@
 }
 
 // Please keep this in sync with debugMark()
 /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
 bool SkOpCoincidence::mark() {
     SkCoincidentSpans* coin = fHead;
     if (!coin) {
         return true;
     }
     do {
-        if (!coin->coinPtTStartWritable()->span()->upCastable()) {
-            return false;
-        }
+        FAIL_IF(!coin->coinPtTStartWritable()->span()->upCastable());
         SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
         SkASSERT(!start->deleted());
         SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
         SkASSERT(!end->deleted());
         SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
-        if (oStart->deleted()) {
-            return false;
-        }
+        FAIL_IF(oStart->deleted());
         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->insertCoincidence(oStart->upCast());
         end->insertCoinEnd(oEnd);
         const SkOpSegment* segment = start->segment();
         const SkOpSegment* oSegment = oStart->segment();
         SkOpSpanBase* next = start;
         SkOpSpanBase* oNext = oStart;
+        bool ordered = coin->ordered();
         while ((next = next->upCast()->next()) != end) {
-            if (!next->upCastable()) {
-                return false;
-            }
-            if (!next->upCast()->insertCoincidence(oSegment, flipped)) {
+            FAIL_IF(!next->upCastable());
+            if (!next->upCast()->insertCoincidence(oSegment, flipped, ordered)) {
                 return false;
             }
         }
         while ((oNext = oNext->upCast()->next()) != oEnd) {
-            if (!oNext->upCastable()) {
-                return false;
-            }
-            if (!oNext->upCast()->insertCoincidence(segment, flipped)) {
+            FAIL_IF(!oNext->upCastable());
+            if (!oNext->upCast()->insertCoincidence(segment, flipped, ordered)) {
                 return false;
             }
         }
     } while ((coin = coin->next()));
     return true;
 }
 
 // Please keep in sync with debugMarkCollapsed()
 void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) {
     SkCoincidentSpans* head = coin;
@@ skipping 62 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());
 }