speedup haircubics

src/core/SkScan_Hairline.cpp

-
 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * 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);
 
     do {
         blitter->blitH(x, fy >> 16, 1);
         fy += dy;
     } while (++x < stopx);
 }
 
@@ skipping 160 matching lines @@
     blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2);      // left
     blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right
     blitter->blitH(r.fLeft, r.fBottom - 1, width);              // bottom
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 #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])
     SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
     SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
     // we want everyone to be positive
     dx = SkScalarAbs(dx);
     dy = SkScalarAbs(dy);
     // convert to whole pixel values (use ceiling to be conservative)
     int idx = SkScalarCeilToInt(dx);
@@ skipping 13 matching lines @@
 
         SkChopQuadAtHalf(pts, tmp);
         hairquad(tmp, clip, blitter, level - 1, lineproc);
         hairquad(&tmp[2], clip, blitter, level - 1, lineproc);
     } else {
         SkPoint tmp[] = { pts[0], pts[2] };
         lineproc(tmp, 2, clip, blitter);
     }
 }
 
-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];
 
         SkChopCubicAt(pts, tmp, SK_Scalar1/2);
         haircubic(tmp, clip, blitter, level - 1, lineproc);
         haircubic(&tmp[3], clip, blitter, level - 1, lineproc);
     } else {
         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];
+
+        int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
+        for (int i = 0; i < count; i++) {
+            hair_cubic(&tmp[i * 3], clip, blitter, lineproc);
+        }
+    }
+#endif
 }
 
-#define kMaxCubicSubdivideLevel 6
-#define kMaxQuadSubdivideLevel  5
-
 static int compute_quad_level(const SkPoint pts[3]) {
     int d = compute_int_quad_dist(pts);
     /*  quadratics approach the line connecting their start and end points
      4x closer with each subdivision, so we compute the number of
      subdivisions to be the minimum need to get that distance to be less
      than a pixel.
      */
     int level = (33 - SkCLZ(d)) >> 1;
     // sanity check on level (from the previous version)
     if (level > kMaxQuadSubdivideLevel) {
@@ skipping 48 matching lines @@
                 const SkScalar tol = SK_Scalar1 / 4;
                 const SkPoint* quadPts = converter.computeQuads(pts,
                                                        iter.conicWeight(), tol);
                 for (int i = 0; i < converter.countQuads(); ++i) {
                     int level = compute_quad_level(quadPts);
                     hairquad(quadPts, clip, blitter, level, lineproc);
                     quadPts += 2;
                 }
                 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:
                 break;
         }
     }
 }
 
 void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
     hair_path(path, clip, blitter, SkScan::HairLineRgn);
@@ skipping 73 matching lines @@
 
         SkAAClipBlitterWrapper wrap;
         if (!clip.quickContains(r.roundOut().makeOutset(1, 1))) {
             wrap.init(clip, blitter);
             blitter = wrap.getBlitter();
             clipRgn = &wrap.getRgn();
         }
         AntiHairLineRgn(pts, count, clipRgn, blitter);
     }
 }