1 files changed, 80 insertions, 18 deletions

diff --git a/chromium/third_party/skia/src/pathops/SkPathOpsCubic.cpp b/chromium/third_party/skia/src/pathops/SkPathOpsCubic.cpp
index 8e8ec47bf97..9d70d58ec15 100644
--- a/chromium/third_party/skia/src/pathops/SkPathOpsCubic.cpp
+++ b/chromium/third_party/skia/src/pathops/SkPathOpsCubic.cpp
@@ -9,9 +9,58 @@
 #include "SkPathOpsLine.h"
 #include "SkPathOpsQuad.h"
 #include "SkPathOpsRect.h"
+#include "SkTSort.h"
 
 const int SkDCubic::gPrecisionUnit = 256;  // FIXME: test different values in test framework
 
+// give up when changing t no longer moves point
+// also, copy point rather than recompute it when it does change
+double SkDCubic::binarySearch(double min, double max, double axisIntercept,
+        SearchAxis xAxis) const {
+    double t = (min + max) / 2;
+    double step = (t - min) / 2;
+    SkDPoint cubicAtT = ptAtT(t);
+    double calcPos = (&cubicAtT.fX)[xAxis];
+    double calcDist = calcPos - axisIntercept;
+    do {
+        double priorT = t - step;
+        SkASSERT(priorT >= min);
+        SkDPoint lessPt = ptAtT(priorT);
+        if (approximately_equal(lessPt.fX, cubicAtT.fX)
+                && approximately_equal(lessPt.fY, cubicAtT.fY)) {
+            return -1;  // binary search found no point at this axis intercept
+        }
+        double lessDist = (&lessPt.fX)[xAxis] - axisIntercept;
+#if DEBUG_CUBIC_BINARY_SEARCH
+        SkDebugf("t=%1.9g calc=%1.9g dist=%1.9g step=%1.9g less=%1.9g\n", t, calcPos, calcDist,
+                step, lessDist);
+#endif
+        double lastStep = step;
+        step /= 2;
+        if (calcDist > 0 ? calcDist > lessDist : calcDist < lessDist) {
+            t = priorT;
+        } else {
+            double nextT = t + lastStep;
+            SkASSERT(nextT <= max);
+            SkDPoint morePt = ptAtT(nextT);
+            if (approximately_equal(morePt.fX, cubicAtT.fX)
+                    && approximately_equal(morePt.fY, cubicAtT.fY)) {
+                return -1;  // binary search found no point at this axis intercept
+            }
+            double moreDist = (&morePt.fX)[xAxis] - axisIntercept;
+            if (calcDist > 0 ? calcDist <= moreDist : calcDist >= moreDist) {
+                continue;
+            }
+            t = nextT;
+        }
+        SkDPoint testAtT = ptAtT(t);
+        cubicAtT = testAtT;
+        calcPos = (&cubicAtT.fX)[xAxis];
+        calcDist = calcPos - axisIntercept;
+    } while (!approximately_equal(calcPos, axisIntercept));
+    return t;
+}
+
 // FIXME: cache keep the bounds and/or precision with the caller?
 double SkDCubic::calcPrecision() const {
     SkDRect dRect;
@@ -93,7 +142,33 @@ bool SkDCubic::monotonicInY() const {
             && between(fPts[0].fY, fPts[2].fY, fPts[3].fY);
 }
 
+int SkDCubic::searchRoots(double extremeTs[6], int extrema, double axisIntercept,
+        SearchAxis xAxis, double* validRoots) const {
+    extrema += findInflections(&extremeTs[extrema]);
+    extremeTs[extrema++] = 0;
+    extremeTs[extrema] = 1;
+    SkTQSort(extremeTs, extremeTs + extrema);
+    int validCount = 0;
+    for (int index = 0; index < extrema; ) {
+        double min = extremeTs[index];
+        double max = extremeTs[++index];
+        if (min == max) {
+            continue;
+        }
+        double newT = binarySearch(min, max, axisIntercept, xAxis);
+        if (newT >= 0) {
+            validRoots[validCount++] = newT;
+        }
+    }
+    return validCount;
+}
+
 bool SkDCubic::serpentine() const {
+#if 0  // FIXME: enabling this fixes cubicOp114 but breaks cubicOp58d and cubicOp53d
+    double tValues[2];
+    // OPTIMIZATION : another case where caching the present of cubic inflections would be useful
+    return findInflections(tValues) > 1;
+#endif
     if (!controlsContainedByEnds()) {
         return false;
     }
@@ -205,7 +280,7 @@ int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) {
         }
         r = A - adiv3;
         *roots++ = r;
-        if (AlmostDequalUlps(R2, Q3)) {
+        if (AlmostDequalUlps((double) R2, (double) Q3)) {
             r = -A / 2 - adiv3;
             if (!AlmostDequalUlps(s[0], r)) {
                 *roots++ = r;
@@ -455,16 +530,16 @@ void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d,
     if (t1 == 1 || t2 == 1) {
         align(3, 2, t1 == 1 ? &dst[0] : &dst[1]);
     }
-    if (precisely_subdivide_equal(dst[0].fX, a.fX)) {
+    if (AlmostBequalUlps(dst[0].fX, a.fX)) {
         dst[0].fX = a.fX;
     }
-    if (precisely_subdivide_equal(dst[0].fY, a.fY)) {
+    if (AlmostBequalUlps(dst[0].fY, a.fY)) {
         dst[0].fY = a.fY;
     }
-    if (precisely_subdivide_equal(dst[1].fX, d.fX)) {
+    if (AlmostBequalUlps(dst[1].fX, d.fX)) {
         dst[1].fX = d.fX;
     }
-    if (precisely_subdivide_equal(dst[1].fY, d.fY)) {
+    if (AlmostBequalUlps(dst[1].fY, d.fY)) {
         dst[1].fY = d.fY;
     }
 }
@@ -508,16 +583,3 @@ SkDCubicPair SkDCubic::chopAt(double t) const {
     interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t);
     return dst;
 }
-
-#ifdef SK_DEBUG
-void SkDCubic::dump() {
-    SkDebugf("{{");
-    int index = 0;
-    do {
-        fPts[index].dump();
-        SkDebugf(", ");
-    } while (++index < 3);
-    fPts[index].dump();
-    SkDebugf("}}\n");
-}
-#endif