simplify bug

The path contains a cubic with a very tight curve.
Split the cubic into pieces so that the individual
curves are better behaved.

Use both inflections and max curvature to 
potentially split cubics. Since this may require
a bit of work, preflight to ignore cubics that
monotonically change in x and y.

Only one of the three tests referred to by the bug
below repro'd. Use path.dumpHex() instead of 
path.dump() to capture the crashing data.

TBR=reed@google.com
BUG=skia:6041

Change-Id: I29a264f87242cacc7c421e7685b90aca81621c74
Reviewed-on: https://skia-review.googlesource.com/5702
Reviewed-by: Cary Clark <caryclark@google.com>
Commit-Queue: Cary Clark <caryclark@google.com>

4 files changed, 108 insertions, 70 deletions

diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index c546477bb1..e46f08f240 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -263,26 +263,28 @@ bool SkOpEdgeBuilder::walk() {
                     // Split complex cubics (such as self-intersecting curves or
                     // ones with difficult curvature) in two before proceeding.
                     // This can be required for intersection to succeed.
-                    SkScalar splitT;
-                    if (SkDCubic::ComplexBreak(pointsPtr, &splitT)) {
-                        SkPoint pair[7];
-                        SkChopCubicAt(pointsPtr, pair, splitT);
-                        if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
+                    SkScalar splitT[3];
+                    int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
+                    if (!breaks) {
+                        fCurrentContour->addCubic(pointsPtr);
+                        break;
+                    }
+                    for (int index = 0; index <= breaks; ++index) {
+                        double t1 = index ? splitT[index - 1] : 0;
+                        double t2 = index < breaks ? splitT[index] : 1;
+                        SkDCubic part = SkDCubic::SubDivide(pointsPtr, t1, t2);
+                        SkPoint pts[4];
+                        if (!part.toFloatPoints(pts)) {
                             return false;
                         }
-                        SkPoint cStorage[2][4];
-                        SkPath::Verb v1 = SkReduceOrder::Cubic(&pair[0], cStorage[0]);
-                        SkPath::Verb v2 = SkReduceOrder::Cubic(&pair[3], cStorage[1]);
-                        SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &pair[0] : cStorage[0];
-                        SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &pair[3] : cStorage[1];
-                        if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
-                            fCurrentContour->addCurve(v1, curve1);
-                            fCurrentContour->addCurve(v2, curve2);
-                            break;
+                        SkPoint reduced[4];
+                        SkPath::Verb verb = SkReduceOrder::Cubic(pts, reduced);
+                        SkPoint* curve = verb == SkPath::kCubic_Verb ? pts : reduced;
+                        if (can_add_curve(verb, curve)) {
+                            fCurrentContour->addCurve(verb, curve);
                         } 
                     }
                 }
-                fCurrentContour->addCubic(pointsPtr);
                 break;
             case SkPath::kClose_Verb:
                 SkASSERT(fCurrentContour);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index a1818d36cd..95f4a983f2 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -1211,8 +1211,8 @@ bool SkOpSegment::moveMultiples() {
     SkOpSpanBase* test = &fHead;
     do {
         int addCount = test->spanAddsCount();
-        FAIL_IF(addCount < 1);
-        if (addCount == 1) {
+//        FAIL_IF(addCount < 1);
+        if (addCount <= 1) {
             continue;
         }
         SkOpPtT* startPtT = test->ptT();
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index eaf9062476..d842e2cc0c 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -75,16 +75,13 @@ double SkDCubic::binarySearch(double min, double max, double axisIntercept,
     return t;
 }
 
-// FIXME: cache keep the bounds and/or precision with the caller?
+// get the rough scale of the cubic; used to determine if curvature is extreme
 double SkDCubic::calcPrecision() const {
-    SkDRect dRect;
-    dRect.setBounds(*this);  // OPTIMIZATION: just use setRawBounds ?
-    double width = dRect.fRight - dRect.fLeft;
-    double height = dRect.fBottom - dRect.fTop;
-    return (width > height ? width : height) / gPrecisionUnit;
+    return ((fPts[1] - fPts[0]).length()
+            + (fPts[2] - fPts[1]).length()
+            + (fPts[3] - fPts[2]).length()) / gPrecisionUnit;
 }
 
-
 /* classic one t subdivision */
 static void interp_cubic_coords(const double* src, double* dst, double t) {
     double ab = SkDInterp(src[0], src[2], t);
@@ -232,34 +229,53 @@ bool SkDCubic::isLinear(int startIndex, int endIndex) const {
     return approximately_zero_when_compared_to(distance, largest);
 }
 
-bool SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) {
+// from http://www.cs.sunysb.edu/~qin/courses/geometry/4.pdf
+// c(t)  = a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3
+// c'(t) = -3a(1-t)^2 + 3b((1-t)^2 - 2t(1-t)) + 3c(2t(1-t) - t^2) + 3dt^2
+//       = 3(b-a)(1-t)^2 + 6(c-b)t(1-t) + 3(d-c)t^2
+static double derivative_at_t(const double* src, double t) {
+    double one_t = 1 - t;
+    double a = src[0];
+    double b = src[2];
+    double c = src[4];
+    double d = src[6];
+    return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t);
+}
+
+int SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) {
+    SkDCubic cubic;
+    cubic.set(pointsPtr);
+    if (cubic.monotonicInX() && cubic.monotonicInY()) {
+        return 0;
+    }
     SkScalar d[3];
     SkCubicType cubicType = SkClassifyCubic(pointsPtr, d);
-    if (cubicType == kLoop_SkCubicType) {
-        // crib code from gpu path utils that finds t values where loop self-intersects
-        // use it to find mid of t values which should be a friendly place to chop
-        SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
-        SkScalar ls = d[1] - tempSqrt;
-        SkScalar lt = 2.f * d[0];
-        SkScalar ms = d[1] + tempSqrt;
-        SkScalar mt = 2.f * d[0];
-        if (roughly_between(0, ls, lt) && roughly_between(0, ms, mt)) {
-            ls = ls / lt;
-            ms = ms / mt;
-            SkASSERT(roughly_between(0, ls, 1) && roughly_between(0, ms, 1));
-            *t = (ls + ms) / 2;
-            SkASSERT(roughly_between(0, *t, 1));
-            return *t > 0 && *t < 1;
+    switch (cubicType) {
+        case kLoop_SkCubicType: {
+            // crib code from gpu path utils that finds t values where loop self-intersects
+            // use it to find mid of t values which should be a friendly place to chop
+            SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
+            SkScalar ls = d[1] - tempSqrt;
+            SkScalar lt = 2.f * d[0];
+            SkScalar ms = d[1] + tempSqrt;
+            SkScalar mt = 2.f * d[0];
+            if (roughly_between(0, ls, lt) && roughly_between(0, ms, mt)) {
+                ls = ls / lt;
+                ms = ms / mt;
+                SkASSERT(roughly_between(0, ls, 1) && roughly_between(0, ms, 1));
+                t[0] = (ls + ms) / 2;
+                SkASSERT(roughly_between(0, *t, 1));
+                return (int) (t[0] > 0 && t[0] < 1);
+            }
         }
-    } else if (kSerpentine_SkCubicType == cubicType || kCusp_SkCubicType == cubicType) {
-        SkDCubic cubic;
-        cubic.set(pointsPtr);
-        double inflectionTs[2];
-        int infTCount = cubic.findInflections(inflectionTs);
-        if (infTCount == 2) {
+        // fall through if no t value found
+        case kSerpentine_SkCubicType:
+        case kCusp_SkCubicType: {
+            double inflectionTs[2];
+            int infTCount = cubic.findInflections(inflectionTs);
             double maxCurvature[3];
             int roots = cubic.findMaxCurvature(maxCurvature);
-#if DEBUG_CUBIC_SPLIT
+    #if DEBUG_CUBIC_SPLIT
             SkDebugf("%s\n", __FUNCTION__);
             cubic.dump();
             for (int index = 0; index < infTCount; ++index) {
@@ -276,19 +292,42 @@ bool SkDCubic::ComplexBreak(const SkPoint pointsPtr[4], SkScalar* t) {
                 SkDLine perp = {{pt - dPt, pt + dPt}};
                 perp.dump();
             }
-#endif
-            for (int index = 0; index < roots; ++index) {
-                if (between(inflectionTs[0], maxCurvature[index], inflectionTs[1])) {
-                    *t = maxCurvature[index];
-                    return *t > 0 && *t < 1;
+    #endif
+            if (infTCount == 2) {
+                for (int index = 0; index < roots; ++index) {
+                    if (between(inflectionTs[0], maxCurvature[index], inflectionTs[1])) {
+                        t[0] = maxCurvature[index];
+                        return (int) (t[0] > 0 && t[0] < 1);
+                    }
                 }
+            } else {
+                int resultCount = 0;
+                // FIXME: constant found through experimentation -- maybe there's a better way....
+                double precision = cubic.calcPrecision() * 2;
+                for (int index = 0; index < roots; ++index) {
+                    double testT = maxCurvature[index];
+                    if (0 >= testT || testT >= 1) {
+                        continue;
+                    }
+                    // don't call dxdyAtT since we want (0,0) results
+                    SkDVector dPt = { derivative_at_t(&cubic.fPts[0].fX, testT),
+                            derivative_at_t(&cubic.fPts[0].fY, testT) };
+                    double dPtLen = dPt.length();
+                    if (dPtLen < precision) {
+                        t[resultCount++] = testT;
+                    }
+                }
+                if (!resultCount && infTCount == 1) {
+                    t[0] = inflectionTs[0];
+                    resultCount = (int) (t[0] > 0 && t[0] < 1);
+                }
+                return resultCount;
             }
-        } else if (infTCount == 1) {
-            *t = inflectionTs[0];
-            return *t > 0 && *t < 1;
         }
+        default:
+            ;
     }
-    return false;
+    return 0;
 }
 
 bool SkDCubic::monotonicInX() const {
@@ -463,19 +502,6 @@ int SkDCubic::RootsReal(double A, double B, double C, double D, double s[3]) {
     return static_cast<int>(roots - s);
 }
 
-// from http://www.cs.sunysb.edu/~qin/courses/geometry/4.pdf
-// c(t)  = a(1-t)^3 + 3bt(1-t)^2 + 3c(1-t)t^2 + dt^3
-// c'(t) = -3a(1-t)^2 + 3b((1-t)^2 - 2t(1-t)) + 3c(2t(1-t) - t^2) + 3dt^2
-//       = 3(b-a)(1-t)^2 + 6(c-b)t(1-t) + 3(d-c)t^2
-static double derivative_at_t(const double* src, double t) {
-    double one_t = 1 - t;
-    double a = src[0];
-    double b = src[2];
-    double c = src[4];
-    double d = src[6];
-    return 3 * ((b - a) * one_t * one_t + 2 * (c - b) * t * one_t + (d - c) * t * t);
-}
-
 // OPTIMIZE? compute t^2, t(1-t), and (1-t)^2 and pass them to another version of derivative at t?
 SkDVector SkDCubic::dxdyAtT(double t) const {
     SkDVector result = { derivative_at_t(&fPts[0].fX, t), derivative_at_t(&fPts[0].fY, t) };
@@ -690,6 +716,15 @@ void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d,
     }
 }
 
+bool SkDCubic::toFloatPoints(SkPoint* pts) const {
+    const double* dCubic = &fPts[0].fX;
+    SkScalar* cubic = &pts[0].fX;
+    for (int index = 0; index < kPointCount * 2; ++index) {
+        *cubic++ = SkDoubleToScalar(*dCubic++);
+    }
+    return SkScalarsAreFinite(&pts->fX, kPointCount * 2);
+}
+
 double SkDCubic::top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const {
     double extremeTs[2];
     double topT = -1;
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index 61de48d19c..2e8a5db3f7 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -47,7 +47,7 @@ struct SkDCubic {
     double calcPrecision() const;
     SkDCubicPair chopAt(double t) const;
     static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D);
-    static bool ComplexBreak(const SkPoint pts[4], SkScalar* t);
+    static int ComplexBreak(const SkPoint pts[4], SkScalar* t);
     int convexHull(char order[kPointCount]) const;
 
     void debugInit() {
@@ -90,6 +90,7 @@ struct SkDCubic {
     int searchRoots(double extremes[6], int extrema, double axisIntercept,
                     SearchAxis xAxis, double* validRoots) const;
 
+    bool toFloatPoints(SkPoint* ) const;
     /**
      *  Return the number of valid roots (0 < root < 1) for this cubic intersecting the
      *  specified horizontal line.