cubicline intersection binary search

src/pathops/SkDCubicLineIntersection.cpp

Index: src/pathops/SkDCubicLineIntersection.cpp
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index da4b983d457049b4a82f7975187acbf30881d910..41828bb7141f27beef0aadc4d6fc9cb9044f80de 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -97,13 +97,27 @@ public:
     int intersectRay(double roots[3]) {
         double adj = fLine[1].fX - fLine[0].fX;
         double opp = fLine[1].fY - fLine[0].fY;
-        SkDCubic r;
+        SkDCubic c;
         for (int n = 0; n < 4; ++n) {
-            r[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp;
+            c[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine[0].fX) * opp;
         }
         double A, B, C, D;
-        SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D);
-        return SkDCubic::RootsValidT(A, B, C, D, roots);
+        SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
+        int count = SkDCubic::RootsValidT(A, B, C, D, roots);
+        for (int index = 0; index < count; ++index) {
+            SkDPoint calcPt = c.ptAtT(roots[index]);
+            if (!approximately_zero(calcPt.fX)) {
+                for (int n = 0; n < 4; ++n) {
+                    c[n].fY = (fCubic[n].fY - fLine[0].fY) * opp
+                            + (fCubic[n].fX - fLine[0].fX) * adj;
+                }
+                double extremeTs[6];
+                int extrema = SkDCubic::FindExtrema(c[0].fX, c[1].fX, c[2].fX, c[3].fX, extremeTs);
+                count = c.searchRoots(extremeTs, extrema, 0, SkDCubic::kXAxis, roots);
+                break;
+            }
+        }
+        return count;
     }
 
     int intersect() {
@@ -146,11 +160,21 @@ public:
         return fIntersections->used();
     }
 
-    int horizontalIntersect(double axisIntercept, double roots[3]) {
+    static int HorizontalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) {
         double A, B, C, D;
-        SkDCubic::Coefficients(&fCubic[0].fY, &A, &B, &C, &D);
+        SkDCubic::Coefficients(&c[0].fY, &A, &B, &C, &D);
         D -= axisIntercept;
-        return SkDCubic::RootsValidT(A, B, C, D, roots);
+        int count = SkDCubic::RootsValidT(A, B, C, D, roots);
+        for (int index = 0; index < count; ++index) {
+            SkDPoint calcPt = c.ptAtT(roots[index]);
+            if (!approximately_equal(calcPt.fY, axisIntercept)) {
+                double extremeTs[6];
+                int extrema = SkDCubic::FindExtrema(c[0].fY, c[1].fY, c[2].fY, c[3].fY, extremeTs);
+                count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kYAxis, roots);
+                break;
+            }
+        }
+        return count;
     }
 
     int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
@@ -158,11 +182,13 @@ public:
         if (fAllowNear) {
             addNearHorizontalEndPoints(left, right, axisIntercept);
         }
-        double rootVals[3];
-        int roots = horizontalIntersect(axisIntercept, rootVals);
-        for (int index = 0; index < roots; ++index) {
-            double cubicT = rootVals[index];
-            SkDPoint pt = fCubic.ptAtT(cubicT);
+        double roots[3];
+        int count = HorizontalIntersect(fCubic, axisIntercept, roots);
+        for (int index = 0; index < count; ++index) {
+            double cubicT = roots[index];
+            SkDPoint pt;
+            pt.fX = fCubic.ptAtT(cubicT).fX;
+            pt.fY = axisIntercept;
             double lineT = (pt.fX - left) / (right - left);
             if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
                 fIntersections->insert(cubicT, lineT, pt);
@@ -174,11 +200,21 @@ public:
         return fIntersections->used();
     }
 
-    int verticalIntersect(double axisIntercept, double roots[3]) {
+    static int VerticalIntersect(const SkDCubic& c, double axisIntercept, double roots[3]) {
         double A, B, C, D;
-        SkDCubic::Coefficients(&fCubic[0].fX, &A, &B, &C, &D);
+        SkDCubic::Coefficients(&c[0].fX, &A, &B, &C, &D);
         D -= axisIntercept;
-        return SkDCubic::RootsValidT(A, B, C, D, roots);
+        int count = SkDCubic::RootsValidT(A, B, C, D, roots);
+        for (int index = 0; index < count; ++index) {
+            SkDPoint calcPt = c.ptAtT(roots[index]);
+            if (!approximately_equal(calcPt.fX, axisIntercept)) {
+                double extremeTs[6];
+                int extrema = SkDCubic::FindExtrema(c[0].fX, c[1].fX, c[2].fX, c[3].fX, extremeTs);
+                count = c.searchRoots(extremeTs, extrema, axisIntercept, SkDCubic::kXAxis, roots);
+                break;
+            }
+        }
+        return count;
     }
 
     int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
@@ -186,11 +222,13 @@ public:
         if (fAllowNear) {
             addNearVerticalEndPoints(top, bottom, axisIntercept);
         }
-        double rootVals[3];
-        int roots = verticalIntersect(axisIntercept, rootVals);
-        for (int index = 0; index < roots; ++index) {
-            double cubicT = rootVals[index];
-            SkDPoint pt = fCubic.ptAtT(cubicT);
+        double roots[3];
+        int count = VerticalIntersect(fCubic, axisIntercept, roots);
+        for (int index = 0; index < count; ++index) {
+            double cubicT = roots[index];
+            SkDPoint pt;
+            pt.fX = axisIntercept;
+            pt.fY = fCubic.ptAtT(cubicT).fY;
             double lineT = (pt.fY - top) / (bottom - top);
             if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) {
                 fIntersections->insert(cubicT, lineT, pt);