cubicline intersection binary search

src/pathops/SkDCubicLineIntersection.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkIntersections.h"
 #include "SkPathOpsCubic.h"
 #include "SkPathOpsLine.h"
 
@@ skipping 79 matching lines @@
     }
 
     void allowNear(bool allow) {
         fAllowNear = allow;
     }
 
     // see parallel routine in line quadratic intersections
     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() {
         addExactEndPoints();
         if (fAllowNear) {
             addNearEndPoints();
         }
         double rootVals[3];
         int roots = intersectRay(rootVals);
         for (int index = 0; index < roots; ++index) {
@@ skipping 22 matching lines @@
                     }
                 }
                 fIntersections->insert(cubicT, lineT, pt);
         skipInsert:
                 ;
             }
         }
         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) {
         addExactHorizontalEndPoints(left, right, axisIntercept);
         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);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
         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) {
         addExactVerticalEndPoints(top, bottom, axisIntercept);
         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);
             }
         }
         if (flipped) {
             fIntersections->flip();
         }
         return fIntersections->used();
     }
@@ skipping 152 matching lines @@
 }
 
 int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) {
     LineCubicIntersections c(cubic, line, this);
     fUsed = c.intersectRay(fT[0]);
     for (int index = 0; index < fUsed; ++index) {
         fPt[index] = cubic.ptAtT(fT[0][index]);
     }
     return fUsed;
 }