fix some pathops bugs found in 1M skps

src/pathops/SkPathOpsTSect.h

 /*
  * 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 "SkChunkAlloc.h"
 #include "SkPathOpsBounds.h"
 #include "SkPathOpsRect.h"
@@ skipping 69 matching lines @@
         fCoinEnd.init();
     }
 
     const SkTSect<OppCurve, TCurve>* debugOpp() const;
     const SkTSpan* debugSpan(int ) const;
     const SkTSpan* debugT(double t) const;
 #ifdef SK_DEBUG
     bool debugIsBefore(const SkTSpan* span) const;
 #endif
     void dump() const;
+    void dumpAll() const;
     void dumpBounded(int id) const;
     void dumpBounds() const;
     void dumpCoin() const;
 
     double endT() const {
         return fEndT;
     }
 
     SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const;
 
@@ skipping 137 matching lines @@
         result->splitAt(span, t, &fHeap);
         result->initBounds(fCurve);
         span->initBounds(fCurve);
         return result;
     }
 
     bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t,
                           double* oppT);
     SkTSpan<TCurve, OppCurve>* boundsMax() const;
     void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
+    void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e);
     bool coincidentHasT(double t);
     int collapsed() const;
     void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
                                SkTSpan<TCurve, OppCurve>* last);
     int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
                               SkTSpan<TCurve, OppCurve>** last) const;
 
     int debugID() const {
         return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
     }
@@ skipping 121 matching lines @@
 }
 
 template<typename TCurve, typename OppCurve>
 void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) {
     if (!span->hasOppT(t)) {
         SkTSpan<TCurve, OppCurve>* priorSpan;
         SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan);
         if (!opp) {
             opp = this->addFollowing(priorSpan);
 #if DEBUG_PERP
-            SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan->debugID(), t,
-                    opp->debugID());
+            SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
+                    priorSpan->debugID() : -1, t, opp->debugID());
 #endif
         }
 #if DEBUG_PERP
         opp->dump(); SkDebugf("\n");
-        SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan->debugID(),
-                opp->debugID());
+        SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
+                priorSpan->debugID() : -1, opp->debugID());
 #endif
         opp->addBounded(span, &fHeap);
         span->addBounded(opp, &fHeap);
     }
     this->validate();
 #if DEBUG_T_SECT
     span->validatePerpT(t);
 #endif
 }
 
@@ skipping 379 matching lines @@
         testBounded = testBounded->fNext;
     }
 #endif
 }
 
 template<typename TCurve, typename OppCurve>
 void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const {
     const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
     while (testBounded) {
         const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded;
-        if (between(overlap->fStartT, oppT, overlap->fEndT)) {
+        if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) {
             return;
         }
         testBounded = testBounded->fNext;
     }
     SkASSERT(0);
 }
 
 template<typename TCurve, typename OppCurve>
 void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const {
     SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
@@ skipping 131 matching lines @@
         sect2->validate();
         // check to see if a range of points are on the curve
         SkTSpan<TCurve, OppCurve>* coinStart = first;
         do {
             coinStart = this->extractCoincident(sect2, coinStart, last);
         } while (coinStart && !last->fDeleted);
     } while ((first = next));
 }
 
 template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2,
+        double start1s, double start1e) {
+    SkTSpan<TCurve, OppCurve>* first = fHead;
+    SkTSpan<TCurve, OppCurve>* last = this->tail();
+    SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead;
+    SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail();
+    bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
+    deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
+    this->removeSpanRange(first, last);
+    sect2->removeSpanRange(oppFirst, oppLast);
+    first->fStartT = start1s;
+    first->fEndT = start1e;
+    first->resetBounds(fCurve);
+    first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
+    first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve);
+    bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
+    double oppStartT = SkTMax(0., first->fCoinStart.perpT());
+    double oppEndT = SkTMin(1., first->fCoinEnd.perpT());
+    if (!oppMatched) {
+        SkTSwap(oppStartT, oppEndT);
+    }
+    oppFirst->fStartT = oppStartT;
+    oppFirst->fEndT = oppEndT;
+    oppFirst->resetBounds(sect2->fCurve);
+    this->removeCoincident(first, false);
+    sect2->removeCoincident(oppFirst, true);
+    if (deleteEmptySpans) {
+        this->deleteEmptySpans();
+        sect2->deleteEmptySpans();
+    }
+}
+
+template<typename TCurve, typename OppCurve>
 bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) {
     SkTSpan<TCurve, OppCurve>* test = fCoincident;
     while (test) {
         if (between(test->fStartT, t, test->fEndT)) {
             return true;
         }
         test = test->fNext;
     }
     return false;
 }
@@ skipping 262 matching lines @@
                 *oppResult = 1;
             }
         } else {
             *oppResult = 1;
         }
         return hullResult;
     }
     if (span->fIsLine && oppSpan->fIsLine) {
         SkIntersections i;
         int sects = this->linesIntersect(span, opp, oppSpan, &i);
+        if (sects == 2) {
+            return *oppResult = 1;
+        }
         if (!sects) {
             return -1;
         }
         span->fStartT = span->fEndT = i[0][0];
         oppSpan->fStartT = oppSpan->fEndT = i[1][0];
         return *oppResult = 2;
     }
     if (span->fIsLinear || oppSpan->fIsLinear) {
         return *oppResult = (int) span->linearsIntersect(oppSpan);
     }
@@ skipping 11 matching lines @@
     SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }};
     SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }};
     int loopCount = 0;
     double bestDistSq = DBL_MAX;
     if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
         return 0;
     }
     if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
         return 0;
     }
+    // if the ends of each line intersect the opposite curve, the lines are coincident
+    if (thisRayI.used() > 1) {
+        int ptMatches = 0;
+        for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
+            for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
+                ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
+            }
+        }
+        if (ptMatches == 2) {
+            return 2;
+        }
+    }
+    if (oppRayI.used() > 1) {
+        int ptMatches = 0;
+        for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
+            for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
+                ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
+            }
+        }
+        if (ptMatches == 2) {
+            return 2;
+        }
+    }
     do {
         // pick the closest pair of points
         double closest = DBL_MAX;
         int closeIndex SK_INIT_TO_AVOID_WARNING;
         int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
         for (int index = 0; index < oppRayI.used(); ++index) {
             if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
                 continue;
             }
             for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
@@ skipping 644 matching lines @@
 //    SkASSERT(between(0, sect, 2));
     if (!sect) {
         return;
     }
     if (sect == 2 && oppSect == 2) {
         (void) EndsEqual(sect1, sect2, intersections);
         return;
     }
     span1->addBounded(span2, &sect1->fHeap);
     span2->addBounded(span1, &sect2->fHeap);
+    const int kMaxCoinLoopCount = 8;
+    int coinLoopCount = kMaxCoinLoopCount;
+    double start1s SK_INIT_TO_AVOID_WARNING;
+    double start1e SK_INIT_TO_AVOID_WARNING;
     do {
         // find the largest bounds
         SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax();
         if (!largest1) {
             break;
         }
         SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax();
         // split it
         if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
                 || (!largest1->fCollapsed && largest2->fCollapsed)))) {
@@ skipping 14 matching lines @@
             // trim parts that don't intersect the opposite
             SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne();
             if (!half2->split(largest2, &sect2->fHeap)) {
                 break;
             }
             sect2->trim(largest2, sect1);
             sect2->trim(half2, sect1);
         }
         sect1->validate();
         sect2->validate();
+#if DEBUG_T_SECT_LOOP_COUNT
+        intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
+#endif
         // if there are 9 or more continuous spans on both sects, suspect coincidence
         if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
                 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
+            if (coinLoopCount == kMaxCoinLoopCount) {
+                start1s = sect1->fHead->fStartT;
+                start1e = sect1->tail()->fEndT;
+            }
             sect1->coincidentCheck(sect2);
             sect1->validate();
             sect2->validate();
+#if DEBUG_T_SECT_LOOP_COUNT
+            intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
+#endif
+            if (!--coinLoopCount) {
+                /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
+                   gets stuck in a loop. It adds an extension to allow a coincident end
+                   perpendicular to track its intersection in the opposite curve. However,
+                   the bounding box of the extension does not intersect the original curve,
+                   so the extension is discarded, only to be added again the next time around. */ 
+                sect1->coincidentForce(sect2, start1s, start1e);
+                sect1->validate();
+                sect2->validate();
+            }
         }
         if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
                 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
             sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
             sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
             sect1->removeByPerpendicular(sect2);
             sect1->validate();
             sect2->validate();
+#if DEBUG_T_SECT_LOOP_COUNT
+            intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
+#endif
             if (sect1->collapsed() > TCurve::kMaxIntersections) {
                 break;
             }
         }
 #if DEBUG_T_SECT_DUMP
         sect1->dumpBoth(sect2);
 #endif
         if (!sect1->fHead || !sect2->fHead) {
             break;
         }
@@ skipping 104 matching lines @@
         } else if (intersections->isCoincident(index + 1)) {
             intersections->removeOne(index + 1);
             --last;
         } else {
             intersections->setCoincident(index++);
         }
         intersections->setCoincident(index);
     }
     SkASSERT(intersections->used() <= TCurve::kMaxIntersections);
 }