interpolation of coincidence must be local to a single span

src/pathops/SkPathOpsDebug.cpp

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkMutex.h"
 #include "SkOpCoincidence.h"
 #include "SkOpContour.h"
@@ skipping 45 matching lines @@
     }
     return false;
 }
 #endif
 
 #if DEBUG_COINCIDENCE_VERBOSE
 enum GlitchType {
     kAddCorruptCoin_Glitch,
     kAddExpandedCoin_Glitch,
     kAddExpandedFail_Glitch,
+    kAddIfCollapsed_Glitch,
     kAddIfMissingCoin_Glitch,
     kAddMissingCoin_Glitch,
     kAddMissingExtend_Glitch,
     kAddOrOverlap_Glitch,
     kCollapsedCoin_Glitch,
     kCollapsedDone_Glitch,
     kCollapsedOppValue_Glitch,
     kCollapsedSpan_Glitch,
     kCollapsedWindValue_Glitch,
     kDeletedCoin_Glitch,
@@ skipping 203 matching lines @@
         mask |= 1 << glitch.fType;
     }
     for (int index = 0; index < kGlitchType_Count; ++index) {
         SkDebugf(mask & (1 << index) ? "x" : "-");
     }
     SkDebugf("  %s\n", id);
     for (int index = 0; index < glitches.fGlitches.count(); ++index) {
         const SpanGlitch& glitch = glitches.fGlitches[index];
         SkDebugf("%02d: ", index);
         if (glitch.fBase) {
-            SkDebugf(" base=%d", glitch.fBase->debugID());
+            SkDebugf(" seg/base=%d/%d", glitch.fBase->segment()->debugID(),
+                    glitch.fBase->debugID());
         }
         if (glitch.fSuspect) {
-            SkDebugf(" base=%d", glitch.fSuspect->debugID());
+            SkDebugf(" seg/base=%d/%d", glitch.fSuspect->segment()->debugID(),
+                    glitch.fSuspect->debugID());
         }
         if (glitch.fSegment) {
             SkDebugf(" segment=%d", glitch.fSegment->debugID());
         }
         if (glitch.fCoinSpan) {
-            SkDebugf(" coinSpan=%d", glitch.fCoinSpan->debugID());
+            SkDebugf(" coinSeg/Span/PtT=%d/%d/%d", glitch.fCoinSpan->segment()->debugID(),
+                    glitch.fCoinSpan->span()->debugID(), glitch.fCoinSpan->debugID());
         }
         if (glitch.fEndSpan) {
             SkDebugf(" endSpan=%d", glitch.fEndSpan->debugID());
         }
         if (glitch.fOppSpan) {
-            SkDebugf(" oppSpan=%d", glitch.fOppSpan->debugID());
+            SkDebugf(" oppSeg/Span/PtT=%d/%d/%d", glitch.fOppSpan->segment()->debugID(),
+                    glitch.fOppSpan->span()->debugID(), glitch.fOppSpan->debugID());
         }
         if (glitch.fOppEndSpan) {
             SkDebugf(" oppEndSpan=%d", glitch.fOppEndSpan->debugID());
         }
         if (!SkScalarIsNaN(glitch.fStartT)) {
             SkDebugf(" startT=%g", glitch.fStartT);
         }
         if (!SkScalarIsNaN(glitch.fEndT)) {
             SkDebugf(" endT=%g", glitch.fEndT);
         }
         if (glitch.fOppSegment) {
             SkDebugf(" segment=%d", glitch.fOppSegment->debugID());
         }
         if (!SkScalarIsNaN(glitch.fOppStartT)) {
             SkDebugf(" oppStartT=%g", glitch.fOppStartT);
         }
         if (!SkScalarIsNaN(glitch.fOppEndT)) {
             SkDebugf(" oppEndT=%g", glitch.fOppEndT);
         }
         if (!SkScalarIsNaN(glitch.fPt.fX) || !SkScalarIsNaN(glitch.fPt.fY)) {
             SkDebugf(" pt=%g,%g", glitch.fPt.fX, glitch.fPt.fY);
         }
         switch (glitch.fType) {
             case kAddCorruptCoin_Glitch: SkDebugf(" AddCorruptCoin"); break;
             case kAddExpandedCoin_Glitch: SkDebugf(" AddExpandedCoin"); break;
             case kAddExpandedFail_Glitch: SkDebugf(" AddExpandedFail"); break;
+            case kAddIfCollapsed_Glitch: SkDebugf(" AddIfCollapsed"); break;; break;
             case kAddIfMissingCoin_Glitch: SkDebugf(" AddIfMissingCoin"); break;
             case kAddMissingCoin_Glitch: SkDebugf(" AddMissingCoin"); break;
             case kAddMissingExtend_Glitch: SkDebugf(" AddMissingExtend"); break;
             case kAddOrOverlap_Glitch: SkDebugf(" AAddOrOverlap"); break;
             case kCollapsedCoin_Glitch: SkDebugf(" CollapsedCoin"); break;
             case kCollapsedDone_Glitch: SkDebugf(" CollapsedDone"); break;
             case kCollapsedOppValue_Glitch: SkDebugf(" CollapsedOppValue"); break;
             case kCollapsedSpan_Glitch: SkDebugf(" CollapsedSpan"); break;
             case kCollapsedWindValue_Glitch: SkDebugf(" CollapsedWindValue"); break;
             case kDeletedCoin_Glitch: SkDebugf(" DeletedCoin"); break;
@@ skipping 16 matching lines @@
             case kMoveNearbyReleaseFinal_Glitch: SkDebugf(" MoveNearbyReleaseFinal"); break;
             case kReleasedSpan_Glitch: SkDebugf(" ReleasedSpan"); break;
             case kUnaligned_Glitch: SkDebugf(" Unaligned"); break;
             case kUnalignedHead_Glitch: SkDebugf(" UnalignedHead"); break;
             case kUnalignedTail_Glitch: SkDebugf(" UnalignedTail"); break;
             default: SkASSERT(0);
         }
         SkDebugf("\n");
     }
     contourList->globalState()->debugSetCheckHealth(false);
-#if DEBUG_ACTIVE_SPANS
+#if 0 && DEBUG_ACTIVE_SPANS
     SkDebugf("active after %s:\n", id);
     ShowActiveSpans(contourList);
 #endif
 #endif
 }
 #endif
 
 #if defined SK_DEBUG || !FORCE_RELEASE
 void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
     size_t len = strlen(str);
@@ skipping 985 matching lines @@
                 if (!oTest) {
                     return;
                 }
             }
         }
     } while ((coin = coin->next()));
     return;
 }
 
 /* Commented-out lines keep this in sync with addIfMissing() */
-void SkOpCoincidence::debugAddIfMissing(const SkCoincidentSpans* outer, const SkOpPtT* over1s,
-            const SkOpPtT* over1e, const char* id, SkPathOpsDebug::GlitchLog* log) const {
+void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkCoincidentSpans* outer, const SkOpPtT* over1s,
+            const SkOpPtT* over1e) const {
 //     SkASSERT(fTop);
     if (fTop && alreadyAdded(fTop, outer, over1s, over1e)) {  // in debug, fTop may be null
         return;
     }
     if (fHead && alreadyAdded(fHead, outer, over1s, over1e)) {
         return;
     }
     log->record(kAddIfMissingCoin_Glitch, id, outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e);
     this->debugValidate();
     return;
 }
 
 /* Commented-out lines keep this in sync addIfMissing() */
-void SkOpCoincidence::debugAddIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
-        const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
-        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
-        const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, const char* id, SkPathOpsDebug::GlitchLog* log) const {
+// note that over1s, over1e, over2s, over2e are ordered
+void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s,
+        double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
+        const SkOpPtT* over1e, const SkOpPtT* over2e) const {
+    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;
-    TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
-    TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
-    bool swap = coinTs > coinTe;
-    if (swap) {
+    coinTs = TRange(over1s, tStart, coinSeg  SkDEBUGPARAMS(over1e));
+    coinTe = TRange(over1s, tEnd, coinSeg  SkDEBUGPARAMS(over1e));
+    if (coinSeg->collapsed(coinTs, coinTe)) {
+        return log->record(kAddIfCollapsed_Glitch, id, coinSeg);
+    }
+    oppTs = TRange(over2s, tStart, oppSeg  SkDEBUGPARAMS(over2e));
+    oppTe = TRange(over2s, tEnd, oppSeg  SkDEBUGPARAMS(over2e));
+    if (oppSeg->collapsed(oppTs, oppTe)) {
+        return log->record(kAddIfCollapsed_Glitch, id, oppSeg);
+    }
+    if (coinTs > coinTe) {
         SkTSwap(coinTs, coinTe);
-    }
-    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
         SkTSwap(oppTs, oppTe);
     }
-    if (swap) {
-        SkTSwap(oppTs, oppTe);
-    }
-    const SkOpSegment* coinSeg = coinPtTStart->segment();
-    const SkOpSegment* oppSeg = oppPtTStart->segment();
-    if (coinSeg == oppSeg) {
-        return;
-    }
-    return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe);
+    return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe
+            );
 }
 
 /* Commented-out lines keep this in sync addOrOverlap() */
 // 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()
@@ skipping 72 matching lines @@
             oe = oppSeg->debugAddT(oppTe, id, log);
         if (ce && oe) ce->span()->debugAddOpp(id, log, oe->span());
 //         ce = ceWritable;
 //         oe = oeWritable;
     }
     this->debugValidate();
     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;
+    RETURN_FALSE_IF(!cs || !ce || cs == ce || cs->contains(ce) || !os || !oe || os == oe || os->contains(oe), coinSeg);
+    bool result = true;
     if (overlap) {
         if (overlap->coinPtTStart()->segment() == coinSeg) {
                 log->record(kAddMissingExtend_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
         } else {
             if (oppTs > oppTe) {
                 SkTSwap(coinTs, coinTe);
                 SkTSwap(oppTs, oppTe);
             }
             log->record(kAddMissingExtend_Glitch, id, oppSeg, oppTs, oppTe, coinSeg, coinTs, coinTe);
         }
-#if DEBUG_COINCIDENCE_VERBOSE
-//         if (result) {
-//             overlap->debugShow();
-//         }
+#if 0 && DEBUG_COINCIDENCE_VERBOSE
+        if (result) {
+             overlap->debugShow();
+        }
 #endif
     } else {
         log->record(kAddMissingCoin_Glitch, id, coinSeg, coinTs, coinTe, oppSeg, oppTs, oppTe);
-#if DEBUG_COINCIDENCE_VERBOSE
-//         fHead->debugShow();
+#if 0 && DEBUG_COINCIDENCE_VERBOSE
+        fHead->debugShow();
 #endif
     }
     this->debugValidate();
-    return;
+    return (void) result;
 }
 
 // Extra commented-out lines keep this in sync with addMissing()
 /* 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
 void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const {
     const SkCoincidentSpans* outer = fHead;
     if (!outer) {
         return;
     }
     // 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 SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
-        const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
-        if (outerCoin->done() || outerOpp->done()) {
-            continue;
-        }
+        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();
+        SkASSERT(!oos->deleted());
+        const SkOpSegment* outerOpp = oos->segment();
+        SkASSERT(!outerOpp->done());
+//        SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
+//        SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
         const SkCoincidentSpans* inner = outer;
         while ((inner = inner->next())) {
             this->debugValidate();
             double overS, overE;
-            const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
-            const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
-            if (innerCoin->done() || innerOpp->done()) {
-                continue;
-            }
+            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) {
-                if (outerOpp != innerOpp
-                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
-                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
-                            outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
+                const SkOpPtT* oce = outer->coinPtTEnd();
+                SkASSERT(!oce->deleted());
+                const SkOpPtT* ice = inner->coinPtTEnd();
+                SkASSERT(!ice->deleted());
+                if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, ocs->starter(oce), ics->starter(ice),
+                            overS, overE, outerOpp, innerOpp,
+                            ocs->debugEnder(oce),
+                            ics->debugEnder(ice));
                 }
             } else if (outerCoin == innerOpp) {
-                if (outerOpp != innerCoin
-                        && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
-                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
-                            outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
+                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)) {
+                    this->debugAddIfMissing(id, log, ocs->starter(oce), ios->starter(ioe),
+                            overS, overE, outerOpp, innerCoin,
+                            ocs->debugEnder(oce),
+                            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(outer->oppPtTStart(), outer->oppPtTEnd(),
-                        inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
-                            outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), id, log);
+                if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, oos->starter(ooe), ics->starter(ice),
+                            overS, overE, outerCoin, innerOpp,
+                            oos->debugEnder(ooe),
+                            ics->debugEnder(ice));
                 }
             } else if (outerOpp == innerOpp) {
+                const SkOpPtT* ooe = outer->oppPtTEnd();
+                SkASSERT(!ooe->deleted());
+                const SkOpPtT* ioe = inner->oppPtTEnd();
+                SkASSERT(!ioe->deleted());
                 SkASSERT(outerCoin != innerCoin);
-                if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
-                        inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
-                    this->debugAddIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
-                            inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
-                            outer->coinPtTStart(), outer->coinPtTEnd(),
-                            inner->coinPtTStart(), inner->coinPtTEnd(), id, log);
+                if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
+                    this->debugAddIfMissing(id, log, oos->starter(ooe), ios->starter(ioe),
+                            overS, overE, outerCoin, innerCoin,
+                            oos->debugEnder(ooe),
+                            ios->debugEnder(ioe));
                 }
             }
             this->debugValidate();
         }
     } while ((outer = outer->next()));
     // this->restoreHead();
     return;
 }
 
 // Commented-out lines keep this in sync with release()
@@ skipping 830 matching lines @@
         const SkOpPtT* test = this;
         for (int index = 0; index < links; ++index) {
             if (ptT == test) {
                 return nullptr;
             }
             test = test->next();
         }
     } while (true);
 }
 
+const SkOpPtT* SkOpPtT::debugEnder(const SkOpPtT* end) const {
+    return fT < end->fT ? end : this;
+}
+
 int SkOpPtT::debugLoopLimit(bool report) const {
     int loop = 0;
     const SkOpPtT* next = this;
     do {
         for (int check = 1; check < loop - 1; ++check) {
             const SkOpPtT* checkPtT = this->fNext;
             const SkOpPtT* innerPtT = checkPtT;
             for (int inner = check + 1; inner < loop; ++inner) {
                 innerPtT = innerPtT->fNext;
                 if (checkPtT == innerPtT) {
@@ skipping 146 matching lines @@
 #endif
     SkPath::FillType fillType = path.getFillType();
     SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
     if (includeDeclaration) {
         SkDebugf("    SkPath %s;\n", name);
     }
     SkDebugf("    %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
     iter.setPath(path);
     showPathContours(iter, name);
 }