harden pathops for pathological test

src/pathops/SkDQuadIntersection.cpp

 // Another approach is to start with the implicit form of one curve and solve
 // (seek implicit coefficients in QuadraticParameter.cpp
 // by substituting in the parametric form of the other.
 // The downside of this approach is that early rejects are difficult to come by.
 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step
 
 #include "SkDQuadImplicit.h"
 #include "SkIntersections.h"
 #include "SkPathOpsLine.h"
 #include "SkQuarticRoot.h"
@@ skipping 55 matching lines @@
     for (index = 0; index < count; ++index) {
         if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) {
             continue;
         }
         double t = 1 - roots[index];
         if (approximately_less_than_zero(t)) {
             t = 0;
         } else if (approximately_greater_than_one(t)) {
             t = 1;
         }
+        SkASSERT(t >= 0 && t <= 1);
         valid[result++] = t;
     }
     return result;
 }
 
 static bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) {
 // the idea here is to see at minimum do a quick reject by rotating all points
 // to either side of the line formed by connecting the endpoints
 // if the opposite curves points are on the line or on the other side, the
 // curves at most intersect at the endpoints
@@ skipping 149 matching lines @@
 
 static double flat_measure(const SkDQuad& q) {
     SkDVector mid = q[1] - q[0];
     SkDVector dxy = q[2] - q[0];
     double length = dxy.length();  // OPTIMIZE: get rid of sqrt
     return fabs(mid.cross(dxy) / length);
 }
 
 // FIXME ? should this measure both and then use the quad that is the flattest as the line?
 static bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) {
-    double measure = flat_measure(q1);
-    // OPTIMIZE: (get rid of sqrt) use approximately_zero
-    if (!approximately_zero_sqrt(measure)) {
-        return false;
+    if (i->flatMeasure()) {
+        // for backward compatibility, use the old method when called from cubics
+        // FIXME: figure out how to fix cubics when it calls the new path
+        double measure = flat_measure(q1);
+        // OPTIMIZE: (get rid of sqrt) use approximately_zero
+        if (!approximately_zero_sqrt(measure)) {  // approximately_zero_sqrt
+            return false;
+        }
+     } else {
+        if (!q1.isLinear(0, 2)) {
+            return false;
+        }
     }
     return is_linear_inner(q1, 0, 1, q2, 0, 1, i, NULL);
 }
 
 // FIXME: if flat measure is sufficiently large, then probably the quartic solution failed
 // avoid imprecision incurred with chopAt
 static void relaxed_is_linear(const SkDQuad* q1, double s1, double e1, const SkDQuad* q2,
         double s2, double e2, SkIntersections* i) {
     double m1 = flat_measure(*q1);
     double m2 = flat_measure(*q2);
@@ skipping 39 matching lines @@
     int calcMask = ~0;
     do {
         if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed);
         if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed);
         if (t1[1].approximatelyEqual(t2[1])) {
             *pt = t1[1];
     #if ONE_OFF_DEBUG
             SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __FUNCTION__,
                     t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY);
     #endif
+            if (*t1Seed < 0) {
+                *t1Seed = 0;
+            } else if (*t1Seed > 1) {
+                *t1Seed = 1;
+            }
+            if (*t2Seed < 0) {
+                *t2Seed = 0;
+            } else if (*t2Seed > 1) {
+                *t2Seed = 1;
+            }
             return true;
         }
         if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(SkTMax(0., *t1Seed - tStep));
         if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(SkTMin(1., *t1Seed + tStep));
         if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(SkTMax(0., *t2Seed - tStep));
         if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(SkTMin(1., *t2Seed + tStep));
         double dist[3][3];
         // OPTIMIZE: using calcMask value permits skipping some distance calcuations
         //   if prior loop's results are moved to correct slot for reuse
         dist[1][1] = t1[1].distanceSquared(t2[1]);
@@ skipping 73 matching lines @@
         if (swap) {
             i->insert(testT, impTs[0][index], tmpLine[0]);
         } else {
             i->insert(impTs[0][index], testT, tmpLine[0]);
         }
     }
 }
 
 int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
     fMax = 4;
+    bool exactMatch = false;
     // if the quads share an end point, check to see if they overlap
     for (int i1 = 0; i1 < 3; i1 += 2) {
         for (int i2 = 0; i2 < 3; i2 += 2) {
             if (q1[i1].asSkPoint() == q2[i2].asSkPoint()) {
                 insert(i1 >> 1, i2 >> 1, q1[i1]);
+                exactMatch = true;
             }
         }
     }
     SkASSERT(fUsed < 3);
     if (only_end_pts_in_common(q1, q2)) {
         return fUsed;
     }
     if (only_end_pts_in_common(q2, q1)) {
         return fUsed;
     }
@@ skipping 46 matching lines @@
     SkDQuadImplicit i1(q1);
     SkDQuadImplicit i2(q2);
     int index;
     bool flip1 = q1[2] == q2[0];
     bool flip2 = q1[0] == q2[2];
     bool useCubic = q1[0] == q2[0];
     double roots1[4];
     int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
     // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1
     double roots1Copy[4];
+    SkDEBUGCODE(sk_bzero(roots1Copy, sizeof(roots1Copy)));
     int r1Count = addValidRoots(roots1, rootCount, roots1Copy);
     SkDPoint pts1[4];
     for (index = 0; index < r1Count; ++index) {
         pts1[index] = q1.ptAtT(roots1Copy[index]);
     }
     double roots2[4];
     int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
     double roots2Copy[4];
     int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);
     SkDPoint pts2[4];
     for (index = 0; index < r2Count; ++index) {
         pts2[index] = q2.ptAtT(roots2Copy[index]);
     }
+    bool triedBinary = false;
     if (r1Count == r2Count && r1Count <= 1) {
         if (r1Count == 1 && used() == 0) {
             if (pts1[0].approximatelyEqual(pts2[0])) {
                 insert(roots1Copy[0], roots2Copy[0], pts1[0]);
             } else {
                 // find intersection by chasing t
+                triedBinary = true;
                 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {
                     insert(roots1Copy[0], roots2Copy[0], pts1[0]);
                 }
             }
         }
         return fUsed;
     }
     int closest[4];
     double dist[4];
     bool foundSomething = false;
@@ skipping 20 matching lines @@
                 closest[outer] = -1;
             }
             dist[index] = distance;
             closest[index] = ndex2;
             foundSomething = true;
         next:
             ;
         }
     }
     if (r1Count && r2Count && !foundSomething) {
+        if (exactMatch) {
+            SkASSERT(fUsed > 0);
+            return fUsed;
+        }
         relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this);
+        if (fUsed) {
+            return fUsed;
+        }
+        // maybe the curves are nearly coincident
+        if (!triedBinary && binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) {
+            insert(roots1Copy[0], roots2Copy[0], pts1[0]);
+        }
         return fUsed;
     }
     int used = 0;
     do {
         double lowest = DBL_MAX;
         int lowestIndex = -1;
         for (index = 0; index < r1Count; ++index) {
             if (closest[index] < 0) {
                 continue;
             }
             if (roots1Copy[index] < lowest) {
                 lowestIndex = index;
                 lowest = roots1Copy[index];
             }
         }
         if (lowestIndex < 0) {
             break;
         }
         insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]],
                 pts1[lowestIndex]);
         closest[lowestIndex] = -1;
     } while (++used < r1Count);
     return fUsed;
 }
+
+void SkIntersections::alignQuadPts(const SkPoint q1[3], const SkPoint q2[3]) {
+    for (int index = 0; index < used(); ++index) {
+        const SkPoint result = pt(index).asSkPoint();
+        if (q1[0] == result || q1[2] == result || q2[0] == result || q2[2] == result) {
+            continue;
+        }
+        if (SkDPoint::ApproximatelyEqual(q1[0], result)) {
+            fPt[index].set(q1[0]);
+//            SkASSERT(way_roughly_zero(fT[0][index]));  // this value can be bigger than way rough
+            fT[0][index] = 0;
+        } else if (SkDPoint::ApproximatelyEqual(q1[2], result)) {
+            fPt[index].set(q1[2]);
+//            SkASSERT(way_roughly_equal(fT[0][index], 1));
+            fT[0][index] = 1;
+        }
+        if (SkDPoint::ApproximatelyEqual(q2[0], result)) {
+            fPt[index].set(q2[0]);
+//            SkASSERT(way_roughly_zero(fT[1][index]));
+            fT[1][index] = 0;
+        } else if (SkDPoint::ApproximatelyEqual(q2[2], result)) {
+            fPt[index].set(q2[2]);
+//            SkASSERT(way_roughly_equal(fT[1][index], 1));
+            fT[1][index] = 1;
+        }
+    }
+}