Fix infinite recursion in cubic->quad conversion, also attempt to detect nearly flat cubics early.

Review URL: http://codereview.appspot.com/6448100/

THIS WILL REQUIRE REBASELINING OF CONVEXPATHS GM.



git-svn-id: http://skia.googlecode.com/svn/trunk@4917 2bbb7eff-a529-9590-31e7-b0007b416f81

2 files changed, 87 insertions, 17 deletions

diff --git a/gm/convexpaths.cpp b/gm/convexpaths.cpp
index d1c6aeeff0..f6c3383396 100644
--- a/gm/convexpaths.cpp
+++ b/gm/convexpaths.cpp
@@ -40,7 +40,7 @@ protected:
 
 
     virtual SkISize onISize() {
-        return make_isize(1200, 900);
+        return make_isize(1200, 1100);
     }
 
     void makePaths() {
@@ -48,7 +48,6 @@ protected:
             return;
         }
         fOnce.accomplished();
-
         // CW
         fPaths.push_back().moveTo(0, 0);
         fPaths.back().quadTo(50 * SK_Scalar1, 100 * SK_Scalar1,
@@ -126,14 +125,14 @@ protected:
         fPaths.back().lineTo(98 * SK_Scalar1, 100 * SK_Scalar1);
         fPaths.back().lineTo(3 * SK_Scalar1, 96 * SK_Scalar1);
 
-        /*
-        It turns out arcTos are not automatically marked as convex and they
-        may in fact be ever so slightly concave.
-        fPaths.push_back().arcTo(SkRect::MakeXYWH(0, 0,
-                                                  50 * SK_Scalar1,
-                                                  100 * SK_Scalar1),
-                                 25 * SK_Scalar1,  130 * SK_Scalar1, false);
-        */
+        
+        //It turns out arcTos are not automatically marked as convex and they
+        //may in fact be ever so slightly concave.
+        //fPaths.push_back().arcTo(SkRect::MakeXYWH(0, 0,
+        //                                          50 * SK_Scalar1,
+        //                                          100 * SK_Scalar1),
+        //                         25 * SK_Scalar1,  130 * SK_Scalar1, false);
+        
         // cubics
         fPaths.push_back().cubicTo( 1 * SK_Scalar1,  1 * SK_Scalar1,
                                    10 * SK_Scalar1,  90 * SK_Scalar1,
@@ -141,7 +140,7 @@ protected:
         fPaths.push_back().cubicTo(100 * SK_Scalar1,  50 * SK_Scalar1,
                                     20 * SK_Scalar1, 100 * SK_Scalar1,
                                      0 * SK_Scalar1,   0 * SK_Scalar1);
-
+        
         // path that has a cubic with a repeated first control point and
         // a repeated last control point.
         fPaths.push_back().moveTo(SK_Scalar1 * 10, SK_Scalar1 * 10);
@@ -163,6 +162,30 @@ protected:
                               50 * SK_Scalar1, 0,
                               50 * SK_Scalar1, 10 * SK_Scalar1);
 
+        // cubic where last three points are almost a line
+        fPaths.push_back().moveTo(0, 228 * SK_Scalar1 / 8);
+        fPaths.back().cubicTo(628 * SK_Scalar1 / 8, 82 * SK_Scalar1 / 8,
+                              1255 * SK_Scalar1 / 8, 141 * SK_Scalar1 / 8,
+                              1883 * SK_Scalar1 / 8, 202 * SK_Scalar1 / 8);
+
+        // flat cubic where the at end point tangents both point outward.
+        fPaths.push_back().moveTo(10 * SK_Scalar1, 0);
+        fPaths.back().cubicTo(0, SK_Scalar1,
+                              30 * SK_Scalar1, SK_Scalar1,
+                              20 * SK_Scalar1, 0);
+
+        // flat cubic where initial tangent is in, end tangent out
+        fPaths.push_back().moveTo(0, 0 * SK_Scalar1);
+        fPaths.back().cubicTo(10 * SK_Scalar1, SK_Scalar1,
+                              30 * SK_Scalar1, SK_Scalar1,
+                              20 * SK_Scalar1, 0);
+
+        // flat cubic where initial tangent is out, end tangent in
+        fPaths.push_back().moveTo(10 * SK_Scalar1, 0);
+        fPaths.back().cubicTo(0, SK_Scalar1,
+                              20 * SK_Scalar1, SK_Scalar1,
+                              30 * SK_Scalar1, 0);
+
         // triangle where one edge is a degenerate quad
         fPaths.push_back().moveTo(SkFloatToScalar(8.59375f), 45 * SK_Scalar1);
         fPaths.back().quadTo(SkFloatToScalar(16.9921875f),   45 * SK_Scalar1,
diff --git a/src/gpu/GrPathUtils.cpp b/src/gpu/GrPathUtils.cpp
index 53e5e13b4d..2d4abe0610 100644
--- a/src/gpu/GrPathUtils.cpp
+++ b/src/gpu/GrPathUtils.cpp
@@ -324,6 +324,10 @@ void convert_noninflect_cubic_to_quads(const SkPoint p[4],
                                        SkPath::Direction dir,
                                        SkTArray<SkPoint, true>* quads,
                                        int sublevel = 0) {
+
+    // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
+    // p[2]. Point d is always p[3]. Point c is p[2] unless p[2] == p[3], in which case it is p[1].
+
     SkVector ab = p[1] - p[0];
     SkVector dc = p[2] - p[3];
 
@@ -341,6 +345,51 @@ void convert_noninflect_cubic_to_quads(const SkPoint p[4],
         dc = p[1] - p[3];
     }
 
+    // When the ab and cd tangents are nearly parallel with vector from d to a the constraint that
+    // the quad point falls between the tangents becomes hard to enforce and we are likely to hit
+    // the max subdivision count. However, in this case the cubic is approaching a line and the
+    // accuracy of the quad point isn't so important. We check if the two middle cubic control 
+    // points are very close to the baseline vector. If so then we just pick quadratic points on the
+    // control polygon.
+
+    if (constrainWithinTangents) {
+        SkVector da = p[0] - p[3];
+        SkScalar invDALengthSqd = da.lengthSqd();
+        if (invDALengthSqd > SK_ScalarNearlyZero) {
+            invDALengthSqd = SkScalarInvert(invDALengthSqd);
+            // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a.
+            // same goed for point c using vector cd.
+            SkScalar detABSqd = ab.cross(da);
+            detABSqd = SkScalarSquare(detABSqd);
+            SkScalar detDCSqd = dc.cross(da);
+            detDCSqd = SkScalarSquare(detDCSqd);
+            if (SkScalarMul(detABSqd, invDALengthSqd) < toleranceSqd &&
+                SkScalarMul(detDCSqd, invDALengthSqd) < toleranceSqd) {
+                SkPoint b = p[0] + ab;
+                SkPoint c = p[3] + dc;
+                SkPoint mid = b + c;
+                mid.scale(SK_ScalarHalf);
+                // Insert two quadratics to cover the case when ab points away from d and/or dc
+                // points away from a.
+                if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) {
+                    SkPoint* qpts = quads->push_back_n(6);
+                    qpts[0] = p[0];
+                    qpts[1] = b;
+                    qpts[2] = mid;
+                    qpts[3] = mid;
+                    qpts[4] = c;
+                    qpts[5] = p[3];
+                } else {
+                    SkPoint* qpts = quads->push_back_n(3);
+                    qpts[0] = p[0];
+                    qpts[1] = mid;
+                    qpts[2] = p[3];
+                }
+                return;
+            }
+        }
+    }
+
     static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
     static const int kMaxSubdivs = 10;
 
@@ -353,7 +402,7 @@ void convert_noninflect_cubic_to_quads(const SkPoint p[4],
     SkVector c1 = p[3];
     c1 += dc;
 
-    SkScalar dSqd = sublevel > kMaxSubdivs ? toleranceSqd : c0.distanceToSqd(c1);
+    SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1);
     if (dSqd < toleranceSqd) {
         SkPoint cAvg = c0;
         cAvg += c1;
@@ -363,8 +412,7 @@ void convert_noninflect_cubic_to_quads(const SkPoint p[4],
 
         if (constrainWithinTangents &&
             !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
-            // choose a new cAvg that is the intersection of the two tangent
-            // lines.
+            // choose a new cAvg that is the intersection of the two tangent lines.
             ab.setOrthog(ab);
             SkScalar z0 = -ab.dot(p[0]);
             dc.setOrthog(dc);
@@ -378,9 +426,8 @@ void convert_noninflect_cubic_to_quads(const SkPoint p[4],
             if (sublevel <= kMaxSubdivs) {
                 SkScalar d0Sqd = c0.distanceToSqd(cAvg);
                 SkScalar d1Sqd = c1.distanceToSqd(cAvg);
-                // We need to subdivide if d0 + d1 > tolerance but we have the
-                // sqd values. We know the distances and tolerance can't be
-                // negative.
+                // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know
+                // the distances and tolerance can't be negative.
                 // (d0 + d1)^2 > toleranceSqd
                 // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
                 SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd));