path ops work in progress

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"
@@ skipping 121 matching lines @@
     if (roots == 0) {
         if (subDivide) {
             *subDivide = true;
         }
         return true;
     }
     if (roots == 2) {
         return false;
     }
     SkDPoint pt2 = q1.ptAtT(rootTs[0][0]);
-    if (!pt2.approximatelyEqualHalf(mid)) {
+    if (!pt2.approximatelyEqual(mid)) {
         return false;
     }
     i->insertSwap(rootTs[0][0], tMid, pt2);
     return true;
 }
 
 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkDQuad& q2,
                             double t2s, double t2e, SkIntersections* i, bool* subDivide) {
     SkDQuad hull = q1.subDivide(t1s, t1e);
     SkDLine line = {{hull[2], hull[0]}};
@@ skipping 89 matching lines @@
 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;
     }
     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
-static void relaxed_is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i) {
-    double m1 = flat_measure(q1);
-    double m2 = flat_measure(q2);
-#if DEBUG_FLAT_QUADS
-    double min = SkTMin(m1, m2);
-    if (min > 5) {
-        SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min);
+// 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);
+    i->reset();
+    const SkDQuad* rounder, *flatter;
+    double sf, midf, ef, sr, er;
+    if (m2 < m1) {
+        rounder = q1;
+        sr = s1;
+        er = e1;
+        flatter = q2;
+        sf = s2;
+        midf = (s2 + e2) / 2;
+        ef = e2;
+    } else {
+        rounder = q2;
+        sr = s2;
+        er = e2;
+        flatter = q1;
+        sf = s1;
+        midf = (s1 + e1) / 2;
+        ef = e1;
     }
-#endif
-    i->reset();
-    const SkDQuad& rounder = m2 < m1 ? q1 : q2;
-    const SkDQuad& flatter = m2 < m1 ? q2 : q1;
     bool subDivide = false;
-    is_linear_inner(flatter, 0, 1, rounder, 0, 1, i, &subDivide);
+    is_linear_inner(*flatter, sf, ef, *rounder, sr, er, i, &subDivide);
     if (subDivide) {
-        SkDQuadPair pair = flatter.chopAt(0.5);
-        SkIntersections firstI, secondI;
-        relaxed_is_linear(pair.first(), rounder, &firstI);
-        for (int index = 0; index < firstI.used(); ++index) {
-            i->insert(firstI[0][index] * 0.5, firstI[1][index], firstI.pt(index));
-        }
-        relaxed_is_linear(pair.second(), rounder, &secondI);
-        for (int index = 0; index < secondI.used(); ++index) {
-            i->insert(0.5 + secondI[0][index] * 0.5, secondI[1][index], secondI.pt(index));
-        }
+        relaxed_is_linear(flatter, sf, midf, rounder, sr, er, i);
+        relaxed_is_linear(flatter, midf, ef, rounder, sr, er, i);
     }
     if (m2 < m1) {
         i->swapPts();
     }
 }
 
 // each time through the loop, this computes values it had from the last loop
 // if i == j == 1, the center values are still good
 // otherwise, for i != 1 or j != 1, four of the values are still good
 // and if i == 1 ^ j == 1, an additional value is good
@@ skipping 84 matching lines @@
     }
     SkDLine tmpLine;
     int testTIndex = testT << 1;
     tmpLine[0] = tmpLine[1] = q2[testTIndex];
     tmpLine[1].fX += q2[1].fY - q2[testTIndex].fY;
     tmpLine[1].fY -= q2[1].fX - q2[testTIndex].fX;
     SkIntersections impTs;
     impTs.intersectRay(q1, tmpLine);
     for (int index = 0; index < impTs.used(); ++index) {
         SkDPoint realPt = impTs.pt(index);
-        if (!tmpLine[0].approximatelyEqualHalf(realPt)) {
+        if (!tmpLine[0].approximatelyEqual(realPt)) {
             continue;
         }
         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;
     // 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] == q2[i2]) {
                 insert(i1 >> 1, i2 >> 1, q1[i1]);
             }
         }
     }
     if (fAllowNear || true) {   // FIXME ? cubic/cubic intersection fails without (cubicOp67u)
         for (int i1 = 0; i1 < 3; i1 += 2) {
             for (int i2 = 0; i2 < 3; i2 += 2) {
-                if (q1[i1] != q2[i2] && q1[i1].approximatelyEqualHalf(q2[i2])) {
+                if (q1[i1] != q2[i2] && q1[i1].approximatelyEqual(q2[i2])) {
                     insertNear(i1 >> 1, i2 >> 1, q1[i1]);
                 }
             }
         }
     }
     SkASSERT(fUsed < 3);
     if (only_end_pts_in_common(q1, q2)) {
         return fUsed;
     }
     if (only_end_pts_in_common(q2, q1)) {
         return fUsed;
     }
     // see if either quad is really a line
     // FIXME: figure out why reduce step didn't find this earlier
     if (is_linear(q1, q2, this)) {
         return fUsed;
     }
     SkIntersections swapped;
+    swapped.setMax(fMax);
     if (is_linear(q2, q1, &swapped)) {
         swapped.swapPts();
         set(swapped);
         return fUsed;
     }
     SkIntersections copyI(*this);
     lookNearEnd(q1, q2, 0, *this, false, &copyI);
     lookNearEnd(q1, q2, 1, *this, false, &copyI);
     lookNearEnd(q2, q1, 0, *this, true, &copyI);
     lookNearEnd(q2, q1, 1, *this, true, &copyI);
@@ skipping 44 matching lines @@
     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]);
     }
     if (r1Count == r2Count && r1Count <= 1) {
         if (r1Count == 1) {
-            if (pts1[0].approximatelyEqualHalf(pts2[0])) {
+            if (pts1[0].approximatelyEqual(pts2[0])) {
                 insert(roots1Copy[0], roots2Copy[0], pts1[0]);
             } else if (pts1[0].moreRoughlyEqual(pts2[0])) {
                 // experiment: try to find intersection by chasing t
                 rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
                 (void) addValidRoots(roots1, rootCount, roots1Copy);
                 rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
                 (void) addValidRoots(roots2, rootCount2, roots2Copy);
                 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;
     for (index = 0; index < r1Count; ++index) {
         dist[index] = DBL_MAX;
         closest[index] = -1;
         for (int ndex2 = 0; ndex2 < r2Count; ++ndex2) {
-            if (!pts2[ndex2].approximatelyEqualHalf(pts1[index])) {
+            if (!pts2[ndex2].approximatelyEqual(pts1[index])) {
                 continue;
             }
             double dx = pts2[ndex2].fX - pts1[index].fX;
             double dy = pts2[ndex2].fY - pts1[index].fY;
             double distance = dx * dx + dy * dy;
             if (dist[index] <= distance) {
                 continue;
             }
             for (int outer = 0; outer < index; ++outer) {
                 if (closest[outer] != ndex2) {
                     continue;
                 }
                 if (dist[outer] < distance) {
                     goto next;
                 }
                 closest[outer] = -1;
             }
             dist[index] = distance;
             closest[index] = ndex2;
             foundSomething = true;
         next:
             ;
         }
     }
     if (r1Count && r2Count && !foundSomething) {
-        relaxed_is_linear(q1, q2, this);
+        relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this);
         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;
 }