check bounds of each cubic segment against clip

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"
@@ skipping 300 matching lines @@
     Sk2s C = Sk2s::Load(&coeff[2].fX);
     Sk2s D = Sk2s::Load(&coeff[3].fX);
     for (int i = 1; i < lines; ++i) {
         t = t + dt;
         (((A * t + B) * t + C) * t + D).store(&tmp[i].fX);
     }
     tmp[lines] = pts[3];
     lineproc(tmp, lines + 1, clip, blitter);
 }
 
-static inline void haircubic(const SkPoint pts[4], const SkRegion* clip,
+static SkRect compute_nocheck_cubic_bounds(const SkPoint pts[4]) {
+    SkASSERT(SkScalarsAreFinite(&pts[0].fX, 8));
+
+    Sk2s min = Sk2s::Load(&pts[0].fX);

[mtklein, 2015/12/17 14:58:15]

This might be slightly faster to do as a tree of min(min(0,1), min(2,3)).  The
critical path is one op shorter.

+    Sk2s max = min;
+    for (int i = 1; i < 4; ++i) {
+        Sk2s pair = Sk2s::Load(&pts[i].fX);
+        min = Sk2s::Min(min, pair);
+        max = Sk2s::Max(max, pair);
+    }
+    return { min.kth<0>(), min.kth<1>(), max.kth<0>(), max.kth<1>() };

[mtklein, 2015/12/17 14:58:15]

We might want to double check this is the same as
  SkRect bounds;
  min.store(&bounds.fLeft);
  max.store(&bounds.fRight);
  return bounds;

+}
+
+static bool is_inverted(const SkRect& r) {
+    return r.fLeft > r.fRight || r.fTop > r.fBottom;
+}
+
+// Can't call SkRect::intersects, since it cares about empty, and we don't (since we tracking
+// something to be stroked, so empty can still draw something (e.g. horizontal line)
+static bool geometric_overlap(const SkRect& a, const SkRect& b) {
+    SkASSERT(!is_inverted(a) && !is_inverted(b));
+    return a.fLeft < b.fRight && b.fLeft < a.fRight &&
+           a.fTop < b.fBottom && b.fTop < a.fBottom;
+}
+
+// Can't call SkRect::contains, since it cares about empty, and we don't (since we tracking
+// something to be stroked, so empty can still draw something (e.g. horizontal line)
+static bool geometric_contains(const SkRect& outer, const SkRect& inner) {
+    SkASSERT(!is_inverted(outer) && !is_inverted(inner));
+    return inner.fRight <= outer.fRight && inner.fLeft >= outer.fLeft &&
+           inner.fBottom <= outer.fBottom && inner.fTop >= outer.fTop;
+}
+
+//#define SK_SHOW_HAIRCLIP_STATS
+#ifdef SK_SHOW_HAIRCLIP_STATS
+static int gKillClip, gRejectClip, gClipCount;
+#endif
+
+static inline void haircubic(const SkPoint pts[4], const SkRegion* clip, const SkRect* insetClip, const SkRect* outsetClip,
                       SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) {
+    if (insetClip) {
+        SkASSERT(outsetClip);
+#ifdef SK_SHOW_HAIRCLIP_STATS
+        gClipCount += 1;
+#endif
+        SkRect bounds = compute_nocheck_cubic_bounds(pts);
+        if (!geometric_overlap(*outsetClip, bounds)) {
+#ifdef SK_SHOW_HAIRCLIP_STATS
+            gRejectClip += 1;
+#endif
+            return;
+        } else if (geometric_contains(*insetClip, bounds)) {
+            clip = nullptr;
+#ifdef SK_SHOW_HAIRCLIP_STATS
+            gKillClip += 1;
+#endif
+        }
+#ifdef SK_SHOW_HAIRCLIP_STATS
+        if (0 == gClipCount % 256)
+            SkDebugf("kill %g reject %g total %d\n", 1.0*gKillClip / gClipCount, 1.0*gRejectClip/gClipCount, gClipCount);
+#endif
+    }
+
     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);
         }
@@ skipping 60 matching lines @@
 
 template <SkPaint::Cap capStyle>
 void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter* blitter,
                       SkScan::HairRgnProc lineproc) {
     if (path.isEmpty()) {
         return;
     }
 
     SkAAClipBlitterWrapper wrap;
     const SkRegion* clip = nullptr;
+    SkRect insetStorage, outsetStorage;
+    const SkRect* insetClip = nullptr;
+    const SkRect* outsetClip = nullptr;
 
     {
         const SkIRect ibounds = path.getBounds().roundOut().makeOutset(1, 1);
 
         if (rclip.quickReject(ibounds)) {
             return;
         }
         if (!rclip.quickContains(ibounds)) {
             if (rclip.isBW()) {
                 clip = &rclip.bwRgn();
             } else {
                 wrap.init(rclip, blitter);
                 blitter = wrap.getBlitter();
                 clip = &wrap.getRgn();
             }
+
+            /*
+             *  We now cache two scalar rects, to use for culling per-segment (e.g. cubic).
+             *  Since we're hairlining, the "bounds" of the control points isn't necessairly the
+             *  limit of where a segment can draw (it might draw up to 1 pixel beyond in aa-hairs).
+             *
+             *  Compute the pt-bounds per segment is easy, so we do that, and then inversely adjust
+             *  the culling bounds so we can just do a straight compare per segment.
+             *
+             *  insetClip is use for quick-accept (i.e. the segment is not clipped), so we inset
+             *  it from the clip-bounds (since segment bounds can be off by 1).
+             *
+             *  outsetClip is used for quick-reject (i.e. the segment is entirely outside), so we
+             *  outset it from the clip-bounds.
+             */
+            insetStorage.set(clip->getBounds());
+            outsetStorage = insetStorage.makeOutset(1, 1);
+            insetStorage.inset(1, 1);
+            if (is_inverted(insetStorage)) {
+                /*
+                 *  our bounds checks assume the rects are never inverted. If insetting has
+                 *  created that, we assume that the area is too small to safely perform a
+                 *  quick-accept, so we just mark the rect as empty (so the quick-accept check
+                 *  will always fail.
+                 */
+                insetStorage.setEmpty();    // just so we don't pass an inverted rect
+            }
+            insetClip = &insetStorage;
+            outsetClip = &outsetStorage;
         }
     }
 
     SkPath::RawIter     iter(path);
     SkPoint             pts[4], firstPt, lastPt;
     SkPath::Verb        verb, prevVerb;
     SkAutoConicToQuads  converter;
 
     if (SkPaint::kButt_Cap != capStyle) {
         prevVerb = SkPath::kDone_Verb;
@@ skipping 30 matching lines @@
                     hairquad(quadPts, clip, blitter, level, lineproc);
                     quadPts += 2;
                 }
                 lastPt = pts[2];
                 break;
             }
             case SkPath::kCubic_Verb: {
                 if (SkPaint::kButt_Cap != capStyle) {
                     extend_pts<capStyle>(prevVerb, iter.peek(), pts, 4);
                 }
-                haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc);
+                haircubic(pts, clip, insetClip, outsetClip, blitter, kMaxCubicSubdivideLevel, lineproc);
                 lastPt = pts[3];
             } break;
             case SkPath::kClose_Verb:
                 pts[0] = lastPt;
                 pts[1] = firstPt;
                 if (SkPaint::kButt_Cap != capStyle && prevVerb == SkPath::kMove_Verb) {
                     // cap moveTo/close to match svg expectations for degenerate segments
                     extend_pts<capStyle>(prevVerb, iter.peek(), pts, 2);
                 }
                 lineproc(pts, 2, clip, blitter);
@@ skipping 101 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);
     }
 }