Pin max curvature solutions to 0..1

Pins out-of-range solutions for cubic/quad max curvature instead of
throwing them out. Code that wants to know the endpoint(s) closest to
max curvature now has the information. Code not interested in these
values can just ignore 0 and 1.

Bug: skia:
Change-Id: I8e7e2ef236b4ab963865dc049ac3e09d5396757d
Reviewed-on: https://skia-review.googlesource.com/143041
Reviewed-by: Cary Clark <caryclark@google.com>
Reviewed-by: Mike Reed <reed@google.com>
Commit-Queue: Chris Dalton <csmartdalton@google.com>

5 files changed, 43 insertions, 54 deletions

diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index ace8a7d4d8..ddf07b7a9d 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -32,10 +32,6 @@ static int is_not_monotonic(SkScalar a, SkScalar b, SkScalar c) {
 
 ////////////////////////////////////////////////////////////////////////
 
-static bool is_unit_interval(SkScalar x) {
-    return x > 0 && x < SK_Scalar1;
-}
-
 static int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) {
     SkASSERT(ratio);
 
@@ -264,15 +260,27 @@ SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]) {
     SkScalar    Ay = src[1].fY - src[0].fY;
     SkScalar    Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX;
     SkScalar    By = src[0].fY - src[1].fY - src[1].fY + src[2].fY;
-    SkScalar    t = 0;  // 0 means don't chop
 
-    (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t);
+    SkScalar numer = -(Ax * Bx + Ay * By);
+    SkScalar denom = Bx * Bx + By * By;
+    if (denom < 0) {
+        numer = -numer;
+        denom = -denom;
+    }
+    if (numer <= 0) {
+        return 0;
+    }
+    if (numer >= denom) {  // Also catches denom=0.
+        return 1;
+    }
+    SkScalar t = numer / denom;
+    SkASSERT(0 <= t && t < 1);
     return t;
 }
 
 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) {
     SkScalar t = SkFindQuadMaxCurvature(src);
-    if (t == 0) {
+    if (t == 0 || t == 1) {
         memcpy(dst, src, 3 * sizeof(SkPoint));
         return 1;
     } else {
@@ -421,8 +429,8 @@ void SkChopCubicAt(const SkPoint src[4], SkPoint dst[],
     {
         for (int i = 0; i < roots - 1; i++)
         {
-            SkASSERT(is_unit_interval(tValues[i]));
-            SkASSERT(is_unit_interval(tValues[i+1]));
+            SkASSERT(0 < tValues[i] && tValues[i] < 1);
+            SkASSERT(0 < tValues[i+1] && tValues[i+1] < 1);
             SkASSERT(tValues[i] < tValues[i+1]);
         }
     }
@@ -759,34 +767,19 @@ static int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) {
     SkScalar R2MinusQ3 = R * R - Q3;
     SkScalar adiv3 = a / 3;
 
-    SkScalar*   roots = tValues;
-    SkScalar    r;
-
     if (R2MinusQ3 < 0) { // we have 3 real roots
         // the divide/root can, due to finite precisions, be slightly outside of -1...1
         SkScalar theta = SkScalarACos(SkScalarPin(R / SkScalarSqrt(Q3), -1, 1));
         SkScalar neg2RootQ = -2 * SkScalarSqrt(Q);
 
-        r = neg2RootQ * SkScalarCos(theta/3) - adiv3;
-        if (is_unit_interval(r)) {
-            *roots++ = r;
-        }
-        r = neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3;
-        if (is_unit_interval(r)) {
-            *roots++ = r;
-        }
-        r = neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3;
-        if (is_unit_interval(r)) {
-            *roots++ = r;
-        }
+        tValues[0] = SkScalarPin(neg2RootQ * SkScalarCos(theta/3) - adiv3, 0, 1);
+        tValues[1] = SkScalarPin(neg2RootQ * SkScalarCos((theta + 2*SK_ScalarPI)/3) - adiv3, 0, 1);
+        tValues[2] = SkScalarPin(neg2RootQ * SkScalarCos((theta - 2*SK_ScalarPI)/3) - adiv3, 0, 1);
         SkDEBUGCODE(test_collaps_duplicates();)
 
         // now sort the roots
-        int count = (int)(roots - tValues);
-        SkASSERT((unsigned)count <= 3);
-        bubble_sort(tValues, count);
-        count = collaps_duplicates(tValues, count);
-        roots = tValues + count;    // so we compute the proper count below
+        bubble_sort(tValues, 3);
+        return collaps_duplicates(tValues, 3);
     } else {              // we have 1 real root
         SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3);
         A = SkScalarCubeRoot(A);
@@ -796,13 +789,9 @@ static int solve_cubic_poly(const SkScalar coeff[4], SkScalar tValues[3]) {
         if (A != 0) {
             A += Q / A;
         }
-        r = A - adiv3;
-        if (is_unit_interval(r)) {
-            *roots++ = r;
-        }
+        tValues[0] = SkScalarPin(A - adiv3, 0, 1);
+        return 1;
     }
-
-    return (int)(roots - tValues);
 }
 
 /*  Looking for F' dot F'' == 0
@@ -849,19 +838,10 @@ int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) {
         coeffX[i] += coeffY[i];
     }
 
-    SkScalar    t[3];
-    int         count = solve_cubic_poly(coeffX, t);
-    int         maxCount = 0;
-
+    int numRoots = solve_cubic_poly(coeffX, tValues);
     // now remove extrema where the curvature is zero (mins)
     // !!!! need a test for this !!!!
-    for (i = 0; i < count; i++) {
-        // if (not_min_curvature())
-        if (t[i] > 0 && t[i] < SK_Scalar1) {
-            tValues[maxCount++] = t[i];
-        }
-    }
-    return maxCount;
+    return numRoots;
 }
 
 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
@@ -872,7 +852,16 @@ int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
         tValues = t_storage;
     }
 
-    int count = SkFindCubicMaxCurvature(src, tValues);
+    SkScalar roots[3];
+    int rootCount = SkFindCubicMaxCurvature(src, roots);
+
+    // Throw out values not inside 0..1.
+    int count = 0;
+    for (int i = 0; i < rootCount; ++i) {
+        if (0 < roots[i] && roots[i] < 1) {
+            tValues[count++] = roots[i];
+        }
+    }
 
     if (dst) {
         if (count == 0) {
diff --git a/src/core/SkPathMeasure.cpp b/src/core/SkPathMeasure.cpp
index 75e2bdf170..e2fdc180f3 100644
--- a/src/core/SkPathMeasure.cpp
+++ b/src/core/SkPathMeasure.cpp
@@ -182,7 +182,7 @@ static SkScalar quad_folded_len(const SkPoint pts[3]) {
     SkPoint pt = SkEvalQuadAt(pts, t);
     SkVector a = pts[2] - pt;
     SkScalar result = a.length();
-    if (0 != t) {
+    if (0 != t && 1 != t) {
         SkVector b = pts[0] - pt;
         result += b.length();
     }
diff --git a/src/core/SkStroke.cpp b/src/core/SkStroke.cpp
index b880c152da..92390a38dd 100644
--- a/src/core/SkStroke.cpp
+++ b/src/core/SkStroke.cpp
@@ -612,13 +612,13 @@ SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic
     }
     SkScalar tValues[3];
     int count = SkFindCubicMaxCurvature(cubic, tValues);
-    if (count == 0) {
-        return kLine_ReductionType;
-    }
     int rCount = 0;
     // Now loop over the t-values, and reject any that evaluate to either end-point
     for (int index = 0; index < count; ++index) {
         SkScalar t = tValues[index];
+        if (0 >= t || t >= 1) {
+            continue;
+        }
         SkEvalCubicAt(cubic, t, &reduction[rCount], nullptr, nullptr);
         if (reduction[rCount] != cubic[0] && reduction[rCount] != cubic[3]) {
             ++rCount;
@@ -679,7 +679,7 @@ SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3
         return kQuad_ReductionType;
     }
     SkScalar t = SkFindQuadMaxCurvature(quad);
-    if (0 == t) {
+    if (0 == t || 1 == t) {
         return kLine_ReductionType;
     }
     *reduction = SkEvalQuadAt(quad, t);
diff --git a/src/gpu/ops/GrAAHairLinePathRenderer.cpp b/src/gpu/ops/GrAAHairLinePathRenderer.cpp
index d6f3c0664e..05f1fbd684 100644
--- a/src/gpu/ops/GrAAHairLinePathRenderer.cpp
+++ b/src/gpu/ops/GrAAHairLinePathRenderer.cpp
@@ -140,7 +140,7 @@ static int get_float_exp(float x) {
 // and dst[1] are the two new conics.
 static int split_conic(const SkPoint src[3], SkConic dst[2], const SkScalar weight) {
     SkScalar t = SkFindQuadMaxCurvature(src);
-    if (t == 0) {
+    if (t == 0 || t == 1) {
         if (dst) {
             dst[0].set(src, weight);
         }
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index 363933e0c5..2be3fddab7 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -242,7 +242,7 @@ bool SkOpEdgeBuilder::walk() {
                 if (v1.dot(v2) < 0) {
                     // FIXME: max curvature for conics hasn't been implemented; use placeholder
                     SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
-                    if (maxCurvature > 0) {
+                    if (0 < maxCurvature && maxCurvature < 1) {
                         SkConic conic(pointsPtr, weight);
                         SkConic pair[2];
                         if (!conic.chopAt(maxCurvature, pair)) {