speedup haircubics

src/core/SkScan_Hairline.cpp

Index: src/core/SkScan_Hairline.cpp
diff --git a/src/core/SkScan_Hairline.cpp b/src/core/SkScan_Hairline.cpp
index 0f2308b1f79df7279c5bde4c11585e0430a68e63..65a8ba5b6a49d516059060ade46c284f7ff90284 100644
--- a/src/core/SkScan_Hairline.cpp
+++ b/src/core/SkScan_Hairline.cpp
@@ -1,4 +1,3 @@
-
 /*
  * Copyright 2006 The Android Open Source Project
  *
@@ -6,13 +5,14 @@
  * found in the LICENSE file.
  */
 
-
 #include "SkScan.h"
 #include "SkBlitter.h"
 #include "SkRasterClip.h"
 #include "SkFDot6.h"
 #include "SkLineClipper.h"
 
+//#define SK_SUPPORT_LEGACY_HAIRCUBIC
+
 static void horiline(int x, int stopx, SkFixed fy, SkFixed dy,
                      SkBlitter* blitter) {
     SkASSERT(x < stopx);
@@ -193,6 +193,9 @@ void SkScan::HairRect(const SkRect& rect, const SkRasterClip& clip,
 #include "SkPath.h"
 #include "SkGeometry.h"
 
+#define kMaxCubicSubdivideLevel 6
+#define kMaxQuadSubdivideLevel  5
+
 static int compute_int_quad_dist(const SkPoint pts[3]) {
     // compute the vector between the control point ([1]) and the middle of the
     // line connecting the start and end ([0] and [2])
@@ -226,8 +229,84 @@ static void hairquad(const SkPoint pts[3], const SkRegion* clip,
     }
 }
 
-static void haircubic(const SkPoint pts[4], const SkRegion* clip,
+#ifndef SK_SUPPORT_LEGACY_HAIRCUBIC
+static inline Sk2s abs(const Sk2s& value) {
+    return Sk2s::Max(value, -value);
+}
+
+static inline SkScalar max_component(const Sk2s& value) {
+    SkScalar components[2];
+    value.store(components);
+    return SkTMax(components[0], components[1]);
+}
+
+static inline int compute_cubic_segs(const SkPoint pts[4]) {
+    Sk2s p0 = from_point(pts[0]);
+    Sk2s p1 = from_point(pts[1]);
+    Sk2s p2 = from_point(pts[2]);
+    Sk2s p3 = from_point(pts[3]);
+
+    const Sk2s oneThird(1.0f / 3.0f);
+    const Sk2s twoThird(2.0f / 3.0f);
+
+    Sk2s p13 = oneThird * p3 + twoThird * p0;
+    Sk2s p23 = oneThird * p0 + twoThird * p3;
+
+    SkScalar diff = max_component(Sk2s::Max(abs(p1 - p13), abs(p2 - p23)));
+    SkScalar tol = SK_Scalar1 / 8;
+
+    for (int i = 0; i < kMaxCubicSubdivideLevel; ++i) {
+        if (diff < tol) {
+            return 1 << i;
+        }
+        tol *= 4;
+    }
+    return 1 << kMaxCubicSubdivideLevel;
+}
+
+static bool lt_90(SkPoint p0, SkPoint pivot, SkPoint p2) {
+    return SkVector::DotProduct(p0 - pivot, p2 - pivot) >= 0;
+}
+
+// The off-curve points are "inside" the limits of the on-curve pts
+static bool quick_cubic_niceness_check(const SkPoint pts[4]) {
+    return lt_90(pts[1], pts[0], pts[3]) &&
+           lt_90(pts[2], pts[0], pts[3]) &&
+           lt_90(pts[1], pts[3], pts[0]) &&
+           lt_90(pts[2], pts[3], pts[0]);
+}
+
+static void hair_cubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter,
+                       LineProc lineproc) {
+    const int nLines = compute_cubic_segs(pts);
+    SkASSERT(nLines > 0);
+    if (1 == nLines) {
+        lineproc(pts[0], pts[3], clip, blitter);
+        return;
+    }
+
+    SkPoint coeff[4];
+    SkCubicToPoly(pts, coeff);
+    
+    const SkScalar deltaT = SK_Scalar1 / nLines;
+    SkScalar currT = deltaT;
+    
+    SkPoint startPt = pts[0];
+    // to ensure we exactly end at the last cubic pt, we don't rely on the stepper
+    // which could accumulate error in currT += deltaT...
+    for (int i = 0; i < nLines - 1; ++i) {
+        SkPoint endPt = SkEvalCubicPolyAt(coeff, currT);
+        lineproc(startPt, endPt, clip, blitter);
+        startPt = endPt;
+        currT += deltaT;
+    }
+    lineproc(startPt, pts[3], clip, blitter);
+}
+#endif
+
+static inline void haircubic(const SkPoint pts[4], const SkRegion* clip,
                       SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) {
+#ifdef SK_SUPPORT_LEGACY_HAIRCUBIC
     if (level > 0) {
         SkPoint tmp[7];
 
@@ -238,10 +317,20 @@ static void haircubic(const SkPoint pts[4], const SkRegion* clip,
         SkPoint tmp[] = { pts[0], pts[3] };
         lineproc(tmp, 2, clip, blitter);
     }
-}
+#else
+    if (quick_cubic_niceness_check(pts)) {
+        hair_cubic(pts, clip, blitter, lineproc);
+    } else {
+        SkPoint  tmp[13];
+        SkScalar tValues[3];
 
-#define kMaxCubicSubdivideLevel 6
-#define kMaxQuadSubdivideLevel  5
+        int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
+        for (int i = 0; i < count; i++) {
+            hair_cubic(&tmp[i * 3], clip, blitter, lineproc);
+        }
+    }
+#endif
+}
 
 static int compute_quad_level(const SkPoint pts[3]) {
     int d = compute_int_quad_dist(pts);
@@ -311,9 +400,9 @@ static void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter*
                 }
                 break;
             }
-            case SkPath::kCubic_Verb:
+            case SkPath::kCubic_Verb: {
                 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
-                break;
+            } break;
             case SkPath::kClose_Verb:
                 break;
             case SkPath::kDone_Verb: