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>

1 files changed, 87 insertions, 52 deletions

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;