long rect dash with guards

check dash fix back in with
guards against changing
chrome layout test results

original CL: skia-review.googlesource.com/c/skia/+/84862

efficiently dash very large rectangles and very long lines
Speed up dashing when lines and rects are absurdly large.

Prior to this CL, only horizontal lines were detected.

Also folded in a change to handle dashing of zero length lines.

TBR=egdaniel@google.com
Bug: skia:7311
Change-Id: I139b10f676e7ae06ad83aaf2a35d49cf06280a67
Reviewed-on: https://skia-review.googlesource.com/87760
Commit-Queue: Cary Clark <caryclark@skia.org>
Reviewed-by: Cary Clark <caryclark@skia.org>

1 files changed, 131 insertions, 0 deletions

diff --git a/src/utils/SkDashPath.cpp b/src/utils/SkDashPath.cpp
index cbfc8f2168..34953c9465 100644
--- a/src/utils/SkDashPath.cpp
+++ b/src/utils/SkDashPath.cpp
@@ -83,11 +83,95 @@ static void outset_for_stroke(SkRect* rect, const SkStrokeRec& rec) {
     rect->outset(radius, radius);
 }
 
+#ifndef SK_SUPPORT_LEGACY_DASH_CULL_PATH
+// If line is zero-length, bump out the end by a tiny amount
+// to draw endcaps. The bump factor is sized so that
+// SkPoint::Distance() computes a non-zero length.
+// Offsets SK_ScalarNearlyZero or smaller create empty paths when Iter measures length.
+// Large values are scaled by SK_ScalarNearlyZero so significant bits change.
+static void adjust_zero_length_line(SkPoint pts[2]) {
+    SkASSERT(pts[0] == pts[1]);
+    pts[1].fX += SkTMax(1.001f, pts[1].fX) * SK_ScalarNearlyZero;
+}
+
+static bool clip_line(SkPoint pts[2], const SkRect& bounds, SkScalar intervalLength,
+                      SkScalar priorPhase) {
+    SkVector dxy = pts[1] - pts[0];
+
+    // only horizontal or vertical lines
+    if (dxy.fX && dxy.fY) {
+        return false;
+    }
+    int xyOffset = SkToBool(dxy.fY);  // 0 to adjust horizontal, 1 to adjust vertical
+
+    SkScalar minXY = (&pts[0].fX)[xyOffset];
+    SkScalar maxXY = (&pts[1].fX)[xyOffset];
+    bool swapped = maxXY < minXY;
+    if (swapped) {
+        SkTSwap(minXY, maxXY);
+    }
+
+    SkASSERT(minXY <= maxXY);
+    SkScalar leftTop = (&bounds.fLeft)[xyOffset];
+    SkScalar rightBottom = (&bounds.fRight)[xyOffset];
+    if (maxXY < leftTop || minXY > rightBottom) {
+        return false;
+    }
+
+    // Now we actually perform the chop, removing the excess to the left/top and
+    // right/bottom of the bounds (keeping our new line "in phase" with the dash,
+    // hence the (mod intervalLength).
+
+    if (minXY < leftTop) {
+        minXY = leftTop - SkScalarMod(leftTop - minXY, intervalLength);
+        if (!swapped) {
+            minXY -= priorPhase;  // for rectangles, adjust by prior phase
+        }
+    }
+    if (maxXY > rightBottom) {
+        maxXY = rightBottom + SkScalarMod(maxXY - rightBottom, intervalLength);
+        if (swapped) {
+            maxXY += priorPhase;  // for rectangles, adjust by prior phase
+        }
+    }
+
+    SkASSERT(maxXY >= minXY);
+    if (swapped) {
+        SkTSwap(minXY, maxXY);
+    }
+    (&pts[0].fX)[xyOffset] = minXY;
+    (&pts[1].fX)[xyOffset] = maxXY;
+
+    if (minXY == maxXY) {
+        adjust_zero_length_line(pts);
+    }
+    return true;
+}
+
+static bool contains_inclusive(const SkRect& rect, const SkPoint& pt) {
+    return rect.fLeft <= pt.fX && pt.fX <= rect.fRight &&
+            rect.fTop <= pt.fY && pt.fY <= rect.fBottom;
+}
+
+// Returns true is b is between a and c, that is: a <= b <= c, or a >= b >= c.
+// Can perform this test with one branch by observing that, relative to b,
+// the condition is true only if one side is positive and one side is negative.
+// If the numbers are very small, the optimization may return the wrong result
+// because the multiply may generate a zero where the simple compare does not.
+// For this reason the assert does not fire when all three numbers are near zero.
+static bool between(SkScalar a, SkScalar b, SkScalar c) {
+    SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
+            || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
+    return (a - b) * (c - b) <= 0;
+}
+#endif
+
 // Only handles lines for now. If returns true, dstPath is the new (smaller)
 // path. If returns false, then dstPath parameter is ignored.
 static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
                       const SkRect* cullRect, SkScalar intervalLength,
                       SkPath* dstPath) {
+#ifdef SK_SUPPORT_LEGACY_DASH_CULL_PATH
     if (nullptr == cullRect) {
         return false;
     }
@@ -146,6 +230,53 @@ static bool cull_path(const SkPath& srcPath, const SkStrokeRec& rec,
     if (minX == maxX) {
         pts[1].fX += maxX * FLT_EPSILON * 32;  // 16 instead of 32 does not draw; length stays zero
     }
+#else // !SK_SUPPORT_LEGACY_DASH_CULL_PATH
+    SkPoint pts[4];
+    if (nullptr == cullRect) {
+        if (srcPath.isLine(pts) && pts[0] == pts[1]) {
+            adjust_zero_length_line(pts);
+        } else {
+            return false;
+        }
+    } else {
+        SkRect bounds;
+        bool isLine = srcPath.isLine(pts);
+        bool isRect = !isLine && srcPath.isRect(nullptr);
+        if (!isLine && !isRect) {
+            return false;
+        }
+        bounds = *cullRect;
+        outset_for_stroke(&bounds, rec);
+        if (isRect) {
+            // break rect into four lines, and call each one separately
+            SkPath::Iter iter(srcPath, false);
+            SkAssertResult(SkPath::kMove_Verb == iter.next(pts));
+            SkScalar priorLength = 0;
+            while (SkPath::kLine_Verb == iter.next(pts)) {
+                SkVector v = pts[1] - pts[0];
+                // if line is entirely outside clip rect, skip it
+                if (v.fX ? between(cullRect->fTop, pts[0].fY, cullRect->fBottom) :
+                        between(cullRect->fLeft, pts[0].fX, cullRect->fRight)) {
+                    bool skipMoveTo = contains_inclusive(*cullRect, pts[0]);
+                    if (clip_line(pts, bounds, intervalLength,
+                                  SkScalarMod(priorLength, intervalLength))) {
+                        if (0 == priorLength || !skipMoveTo) {
+                            dstPath->moveTo(pts[0]);
+                        }
+                        dstPath->lineTo(pts[1]);
+                    }
+                }
+                // keep track of all prior lengths to set phase of next line
+                priorLength += SkScalarAbs(v.fX ? v.fX : v.fY);
+            }
+            return !dstPath->isEmpty();
+        }
+        SkASSERT(isLine);
+        if (!clip_line(pts, bounds, intervalLength, 0)) {
+            return false;
+        }
+    }
+#endif
     dstPath->moveTo(pts[0]);
     dstPath->lineTo(pts[1]);
     return true;