tight bounds optimization

Add support for tight bounds to detect and return moveTo
followed by close or zero-length lineTo.

Also short circuit so that hard work is avoided when
the path bounds is also the tight bounds.

Avoid doing work if the bounds can be trivially computed.
Include naked moveTo coordinates in the tight bounds.

R=fmalita@chromium.org
BUG=skia:5555, skia:5553
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2394443004

Review-Url: https://codereview.chromium.org/2394443004

2 files changed, 111 insertions, 1 deletions

diff --git a/src/pathops/SkPathOpsTightBounds.cpp b/src/pathops/SkPathOpsTightBounds.cpp
index 60f18cfbbc..d748ff538a 100644
--- a/src/pathops/SkPathOpsTightBounds.cpp
+++ b/src/pathops/SkPathOpsTightBounds.cpp
@@ -8,6 +8,45 @@
 #include "SkPathOpsCommon.h"
 
 bool TightBounds(const SkPath& path, SkRect* result) {
+    SkPath::RawIter iter(path);
+    SkRect moveBounds = { SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin };
+    bool wellBehaved = true;
+    SkPath::Verb verb;
+    do {
+        SkPoint pts[4];
+        verb = iter.next(pts);
+        switch (verb) {
+            case SkPath::kMove_Verb:
+                moveBounds.fLeft = SkTMin(moveBounds.fLeft, pts[0].fX);
+                moveBounds.fTop = SkTMin(moveBounds.fTop, pts[0].fY);
+                moveBounds.fRight = SkTMax(moveBounds.fRight, pts[0].fX);
+                moveBounds.fBottom = SkTMax(moveBounds.fBottom, pts[0].fY);
+                break;
+            case SkPath::kQuad_Verb:
+            case SkPath::kConic_Verb:
+                if (!wellBehaved) {
+                    break;
+                }
+                wellBehaved &= between(pts[0].fX, pts[1].fX, pts[2].fX);
+                wellBehaved &= between(pts[0].fY, pts[1].fY, pts[2].fY);
+                break;
+            case SkPath::kCubic_Verb:
+                if (!wellBehaved) {
+                    break;
+                }
+                wellBehaved &= between(pts[0].fX, pts[1].fX, pts[3].fX);
+                wellBehaved &= between(pts[0].fY, pts[1].fY, pts[3].fY);
+                wellBehaved &= between(pts[0].fX, pts[2].fX, pts[3].fX);
+                wellBehaved &= between(pts[0].fY, pts[2].fY, pts[3].fY);
+                break;
+            default:
+                break;
+        }
+    } while (verb != SkPath::kDone_Verb);
+    if (wellBehaved) {
+        *result = path.getBounds();
+        return true;
+    }
     SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
     SkOpContour contour;
     SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
@@ -28,7 +67,7 @@ bool TightBounds(const SkPath& path, SkRect* result) {
         return false;
     }
     if (!SortContourList(&contourList, false, false)) {
-        result->setEmpty();
+        *result = moveBounds;
         return true;
     }
     SkOpContour* current = contourList;
@@ -37,5 +76,8 @@ bool TightBounds(const SkPath& path, SkRect* result) {
         bounds.add(current->bounds());
     }
     *result = bounds;
+    if (!moveBounds.isEmpty()) {
+        result->join(moveBounds);
+    }
     return true;
 }
diff --git a/tests/PathOpsTightBoundsTest.cpp b/tests/PathOpsTightBoundsTest.cpp
index 953756170b..8fd0fdb453 100644
--- a/tests/PathOpsTightBoundsTest.cpp
+++ b/tests/PathOpsTightBoundsTest.cpp
@@ -120,3 +120,71 @@ DEF_TEST(PathOpsTightBoundsQuads, reporter) {
     }
     testRunner.render();
 }
+
+DEF_TEST(PathOpsTightBoundsMove, reporter) {
+    SkPath path;
+    path.moveTo(10, 10);
+    path.close();
+    path.moveTo(20, 20);
+    path.lineTo(20, 20);
+    path.close();
+    path.moveTo(15, 15);
+    path.lineTo(15, 15);
+    path.close();
+    const SkRect& bounds = path.getBounds();
+    SkRect tight;
+    REPORTER_ASSERT(reporter, TightBounds(path, &tight));
+    REPORTER_ASSERT(reporter, bounds == tight);
+}
+
+DEF_TEST(PathOpsTightBoundsMoveOne, reporter) {
+    SkPath path;
+    path.moveTo(20, 20);
+    const SkRect& bounds = path.getBounds();
+    SkRect tight;
+    REPORTER_ASSERT(reporter, TightBounds(path, &tight));
+    REPORTER_ASSERT(reporter, bounds == tight);
+}
+
+DEF_TEST(PathOpsTightBoundsMoveTwo, reporter) {
+    SkPath path;
+    path.moveTo(20, 20);
+    path.moveTo(40, 40);
+    const SkRect& bounds = path.getBounds();
+    SkRect tight;
+    REPORTER_ASSERT(reporter, TightBounds(path, &tight));
+    REPORTER_ASSERT(reporter, bounds == tight);
+}
+
+DEF_TEST(PathOpsTightBoundsTiny, reporter) {
+    SkPath path;
+    path.moveTo(1, 1);
+    path.quadTo(1.000001f, 1, 1, 1);
+    const SkRect& bounds = path.getBounds();
+    SkRect tight;
+    REPORTER_ASSERT(reporter, TightBounds(path, &tight));
+    SkRect moveBounds = {1, 1, 1, 1};
+    REPORTER_ASSERT(reporter, bounds != tight);
+    REPORTER_ASSERT(reporter, moveBounds == tight);
+}
+
+DEF_TEST(PathOpsTightBoundsWellBehaved, reporter) {
+    SkPath path;
+    path.moveTo(1, 1);
+    path.quadTo(2, 3, 4, 5);
+    const SkRect& bounds = path.getBounds();
+    SkRect tight;
+    REPORTER_ASSERT(reporter, TightBounds(path, &tight));
+    REPORTER_ASSERT(reporter, bounds == tight);
+}
+
+DEF_TEST(PathOpsTightBoundsIllBehaved, reporter) {
+    SkPath path;
+    path.moveTo(1, 1);
+    path.quadTo(4, 3, 2, 2);
+    const SkRect& bounds = path.getBounds();
+    SkRect tight;
+    REPORTER_ASSERT(reporter, TightBounds(path, &tight));
+    REPORTER_ASSERT(reporter, bounds != tight);
+}
+