add conservative bounds to raster tiling

This allows the tiler to optimally visit only the tiles that might intersect
the drawing. Not all call-sites can cheaply compute their bounds, so for those
we just pass nullptr, which tells the tiler to visit all of the tiles.

Bug: 818693
Bug: 820245
Bug: 820470
Change-Id: I8bda668a99bcdb2a9a74a8278ec0cf1004acba6e
Reviewed-on: https://skia-review.googlesource.com/119570
Commit-Queue: Mike Reed <reed@google.com>
Reviewed-by: Florin Malita <fmalita@chromium.org>

2 files changed, 116 insertions, 16 deletions

diff --git a/bench/ClipMaskBench.cpp b/bench/ClipMaskBench.cpp
index fc3cc16705..b3b98f2fed 100644
--- a/bench/ClipMaskBench.cpp
+++ b/bench/ClipMaskBench.cpp
@@ -66,3 +66,40 @@ DEF_BENCH(return new ClipMaskBench("picture", [](int size) -> sk_sp<SkImage> {
                                     SkColorSpace::MakeSRGB());
 });)
 
+/////////
+#include "SkSurface.h"
+#include "SkPath.h"
+
+class RasterTileBench : public Benchmark {
+    sk_sp<SkSurface> fSurf;
+    SkPath           fPath;
+    SkString       fName;
+public:
+    RasterTileBench() : fName("rastertile") {
+        int W = 2014 * 20;
+        int H = 20;
+        fSurf = SkSurface::MakeRasterN32Premul(W, H);
+
+        fPath.moveTo(0, 0);
+        fPath.cubicTo(20, 10, 10, 15, 30, 5);
+    }
+
+protected:
+    const char* onGetName() override { return fName.c_str(); }
+
+    void onDraw(int loops, SkCanvas* canvas) override {
+        SkPaint paint;
+        paint.setStyle(SkPaint::kStroke_Style);
+        paint.setStrokeWidth(1.1f);
+        paint.setAntiAlias(true);
+
+        for (int i = 0; i < loops; ++i) {
+            for (int j = 0; j < 1000; ++j) {
+                fSurf->getCanvas()->drawPath(fPath, paint);
+            }
+        }
+    }
+
+private:
+};
+DEF_BENCH(return new RasterTileBench;)
diff --git a/src/core/SkBitmapDevice.cpp b/src/core/SkBitmapDevice.cpp
index 0e456e771c..9d52334685 100644
--- a/src/core/SkBitmapDevice.cpp
+++ b/src/core/SkBitmapDevice.cpp
@@ -23,6 +23,21 @@
 #include "SkTLazy.h"
 #include "SkVertices.h"
 
+struct Bounder {
+    SkRect  fBounds;
+    bool    fHasBounds;
+
+    Bounder(const SkRect& r, const SkPaint& paint) {
+        if ((fHasBounds = paint.canComputeFastBounds())) {
+            fBounds = paint.computeFastBounds(r, &fBounds);
+        }
+    }
+
+    bool hasBounds() const { return fHasBounds; }
+    const SkRect* bounds() const { return fHasBounds ? &fBounds : nullptr; }
+    operator const SkRect* () const { return this->bounds(); }
+};
+
 class SkDrawTiler {
     enum {
         // 8K is 1 too big, since 8K << supersample == 32768 which is too big for SkFixed
@@ -31,6 +46,7 @@ class SkDrawTiler {
 
     SkBitmapDevice* fDevice;
     SkPixmap        fRootPixmap;
+    SkIRect         fSrcBounds;
 
     // Used for tiling and non-tiling
     SkDraw          fDraw;
@@ -43,14 +59,31 @@ class SkDrawTiler {
     bool            fDone, fNeedsTiling;
 
 public:
-    SkDrawTiler(SkBitmapDevice* dev) : fDevice(dev) {
+    static bool NeedsTiling(SkBitmapDevice* dev) {
+        return dev->width() > kMaxDim || dev->height() > kMaxDim;
+    }
+
+    SkDrawTiler(SkBitmapDevice* dev, const SkRect* bounds) : fDevice(dev) {
+        fDone = false;
+
         // we need fDst to be set, and if we're actually drawing, to dirty the genID
         if (!dev->accessPixels(&fRootPixmap)) {
             // NoDrawDevice uses us (why?) so we have to catch this case w/ no pixels
             fRootPixmap.reset(dev->imageInfo(), nullptr, 0);
         }
 
-        fDone = false;
+        if (bounds) {
+            SkRect devBounds;
+            dev->ctm().mapRect(&devBounds, *bounds);
+            if (devBounds.intersect(SkRect::MakeIWH(fRootPixmap.width(), fRootPixmap.height()))) {
+                fSrcBounds = devBounds.roundOut();
+            } else {
+                fDone = true;
+            }
+        } else {
+            fSrcBounds = SkIRect::MakeWH(fRootPixmap.width(), fRootPixmap.height());
+        }
+
         fNeedsTiling = !fRootPixmap.bounds().isEmpty() &&  // empty pixmap map fail extractSubset?
                         (fRootPixmap.width() > kMaxDim || fRootPixmap.height() > kMaxDim);
 
@@ -58,7 +91,8 @@ public:
             // fDraw.fDst is reset each time in setupTileDraw()
             fDraw.fMatrix = &fTileMatrix;
             fDraw.fRC = &fTileRC;
-            fOrigin.set(-kMaxDim, 0); // we'll step/increase it before using it
+            // we'll step/increase it before using it
+            fOrigin.set(fSrcBounds.fLeft - kMaxDim, fSrcBounds.fTop);
         } else {
             fDraw.fDst = fRootPixmap;
             fDraw.fMatrix = &dev->ctm();
@@ -98,15 +132,15 @@ private:
         SkASSERT(fNeedsTiling);
 
         // We do fRootPixmap.width() - kMaxDim instead of fOrigin.fX + kMaxDim to avoid overflow.
-        if (fOrigin.fX >= fRootPixmap.width() - kMaxDim) {    // too far
-            fOrigin.fX = 0;
+        if (fOrigin.fX >= fSrcBounds.fRight - kMaxDim) {    // too far
+            fOrigin.fX = fSrcBounds.fLeft;
             fOrigin.fY += kMaxDim;
         } else {
             fOrigin.fX += kMaxDim;
         }
         // fDone = next origin will be invalid.
-        fDone = fOrigin.fX >= fRootPixmap.width() - kMaxDim &&
-                fOrigin.fY >= fRootPixmap.height() - kMaxDim;
+        fDone = fOrigin.fX >= fSrcBounds.fRight - kMaxDim &&
+                fOrigin.fY >= fSrcBounds.fBottom - kMaxDim;
 
         SkIRect bounds = SkIRect::MakeXYWH(fOrigin.x(), fOrigin.y(), kMaxDim, kMaxDim);
         SkASSERT(!bounds.isEmpty());
@@ -122,8 +156,12 @@ private:
     }
 };
 
-#define LOOP_TILER(code)                                    \
-    SkDrawTiler priv_tiler(this);                           \
+// Passing a bounds allows the tiler to only visit the dst-tiles that might intersect the
+// drawing. If null is passed, the tiler has to visit everywhere. The bounds is expected to be
+// in local coordinates, as the tiler itself will transform that into device coordinates.
+//
+#define LOOP_TILER(code, boundsPtr)                         \
+    SkDrawTiler priv_tiler(this, boundsPtr);                \
     while (const SkDraw* priv_draw = priv_tiler.next()) {   \
         priv_draw->code;                                    \
     }
@@ -300,11 +338,11 @@ void SkBitmapDevice::drawPaint(const SkPaint& paint) {
 
 void SkBitmapDevice::drawPoints(SkCanvas::PointMode mode, size_t count,
                                 const SkPoint pts[], const SkPaint& paint) {
-    LOOP_TILER( drawPoints(mode, count, pts, paint, nullptr))
+    LOOP_TILER( drawPoints(mode, count, pts, paint, nullptr), nullptr)
 }
 
 void SkBitmapDevice::drawRect(const SkRect& r, const SkPaint& paint) {
-    LOOP_TILER( drawRect(r, paint))
+    LOOP_TILER( drawRect(r, paint), Bounder(r, paint))
 }
 
 void SkBitmapDevice::drawOval(const SkRect& oval, const SkPaint& paint) {
@@ -324,14 +362,26 @@ void SkBitmapDevice::drawRRect(const SkRRect& rrect, const SkPaint& paint) {
     // required to override drawRRect.
     this->drawPath(path, paint, nullptr, true);
 #else
-    LOOP_TILER( drawRRect(rrect, paint))
+    LOOP_TILER( drawRRect(rrect, paint), Bounder(rrect.getBounds(), paint))
 #endif
 }
 
 void SkBitmapDevice::drawPath(const SkPath& path,
                               const SkPaint& paint, const SkMatrix* prePathMatrix,
                               bool pathIsMutable) {
-    SkDrawTiler tiler(this);
+    const SkRect* bounds = nullptr;
+    SkRect storage;
+    if (SkDrawTiler::NeedsTiling(this)) {
+        if (!path.isInverseFillType()) {
+            if (prePathMatrix) {
+                prePathMatrix->mapRect(&storage, path.getBounds());
+                bounds = &storage;
+            } else {
+                bounds = &path.getBounds();
+            }
+        }
+    }
+    SkDrawTiler tiler(this, bounds ? Bounder(*bounds, paint).bounds() : nullptr);
     if (tiler.needsTiling()) {
         pathIsMutable = false;
     }
@@ -349,7 +399,20 @@ void SkBitmapDevice::drawBitmap(const SkBitmap& bitmap, SkScalar x, SkScalar y,
 
 void SkBitmapDevice::drawBitmap(const SkBitmap& bitmap, const SkMatrix& matrix,
                                 const SkRect* dstOrNull, const SkPaint& paint) {
-    LOOP_TILER( drawBitmap(bitmap, matrix, dstOrNull, paint))
+    // are we ever given a dst-rect AND have a maskfilter (which might change the bounds)?
+    SkASSERT(!dstOrNull || !paint.getMaskFilter());
+
+    const SkRect* bounds = dstOrNull;
+    SkRect storage;
+    if (!bounds && SkDrawTiler::NeedsTiling(this)) {
+        matrix.mapRect(&storage, SkRect::MakeIWH(bitmap.width(), bitmap.height()));
+        Bounder b(storage, paint);
+        if (b.hasBounds()) {
+            storage = *b.bounds();
+            bounds = &storage;
+        }
+    }
+    LOOP_TILER(drawBitmap(bitmap, matrix, dstOrNull, paint), bounds);
 }
 
 static inline bool CanApplyDstMatrixAsCTM(const SkMatrix& m, const SkPaint& paint) {
@@ -478,13 +541,13 @@ void SkBitmapDevice::drawSprite(const SkBitmap& bitmap, int x, int y, const SkPa
 
 void SkBitmapDevice::drawText(const void* text, size_t len,
                               SkScalar x, SkScalar y, const SkPaint& paint) {
-    LOOP_TILER( drawText((const char*)text, len, x, y, paint, &fSurfaceProps))
+    LOOP_TILER( drawText((const char*)text, len, x, y, paint, &fSurfaceProps), nullptr)
 }
 
 void SkBitmapDevice::drawPosText(const void* text, size_t len, const SkScalar xpos[],
                                  int scalarsPerPos, const SkPoint& offset, const SkPaint& paint) {
     LOOP_TILER( drawPosText((const char*)text, len, xpos, scalarsPerPos, offset, paint,
-                            &fSurfaceProps))
+                            &fSurfaceProps), nullptr)
 }
 
 void SkBitmapDevice::drawVertices(const SkVertices* vertices, SkBlendMode bmode,