Optimize filterBounds() of SkArithmeticImageFilter/SkXfermodeImageFilter

This brings the optimization in blink's FEComposit::MapRect() [1]
into skia.

Previously for these classes we used the default SkImageFilter::
onFilterBounds() which returns the union of the bounds of input filters.
However, this was not optimized if some input filters don't contribute
to the output. When we switch blink SPv2 paint invalidation from using
blink's FilterOperations to cc/skia's filter classes, the non-
optimization caused over-raster-invalidations.

Now override SkImageFilter::onFilterBounds() in these classes to make
their filterBounds() return the same results as the blink counterparts.

Also fix a bug of SkArithmeticImageFilter when k4 is non-zero by
overriding affectsTransparentBlack() to return true in the case, so
that we will use the crop as the final bounds.

[1] https://cs.chromium.org/chromium/src/third_party/WebKit/Source/platform/graphics/filters/FEComposite.cpp?l=115

Change-Id: I91d4cadc267e6262ee3f050a0ddac90154419775
Reviewed-on: https://skia-review.googlesource.com/38921
Reviewed-by: Mike Reed <reed@google.com>
Commit-Queue: Stephen White <senorblanco@chromium.org>

3 files changed, 240 insertions, 0 deletions

diff --git a/src/effects/SkArithmeticImageFilter.cpp b/src/effects/SkArithmeticImageFilter.cpp
index dde38b78d5..8c0f1ef4c9 100644
--- a/src/effects/SkArithmeticImageFilter.cpp
+++ b/src/effects/SkArithmeticImageFilter.cpp
@@ -41,6 +41,8 @@ protected:
     sk_sp<SkSpecialImage> onFilterImage(SkSpecialImage* source, const Context&,
                                         SkIPoint* offset) const override;
 
+    SkIRect onFilterBounds(const SkIRect&, const SkMatrix&, MapDirection) const override;
+
 #if SK_SUPPORT_GPU
     sk_sp<SkSpecialImage> filterImageGPU(SkSpecialImage* source,
                                          sk_sp<SkSpecialImage> background,
@@ -64,6 +66,8 @@ protected:
     sk_sp<SkImageFilter> onMakeColorSpace(SkColorSpaceXformer*) const override;
 
 private:
+    bool affectsTransparentBlack() const override { return !SkScalarNearlyZero(fK[3]); }
+
     const float fK[4];
     const bool fEnforcePMColor;
 
@@ -202,6 +206,59 @@ sk_sp<SkSpecialImage> ArithmeticImageFilterImpl::onFilterImage(SkSpecialImage* s
     return surf->makeImageSnapshot();
 }
 
+SkIRect ArithmeticImageFilterImpl::onFilterBounds(const SkIRect& src,
+                                                  const SkMatrix& ctm,
+                                                  MapDirection direction) const {
+    if (kReverse_MapDirection == direction) {
+        return SkImageFilter::onFilterBounds(src, ctm, direction);
+    }
+
+    SkASSERT(2 == this->countInputs());
+
+    // result(i1,i2) = k1*i1*i2 + k2*i1 + k3*i2 + k4
+    // Note that background (getInput(0)) is i2, and foreground (getInput(1)) is i1.
+    auto i2 = this->getInput(0) ? this->getInput(0)->filterBounds(src, ctm, direction) : src;
+    auto i1 = this->getInput(1) ? this->getInput(1)->filterBounds(src, ctm, direction) : src;
+
+    // Arithmetic with non-zero k4 may influence the complete filter primitive
+    // region. [k4 > 0 => result(0,0) = k4 => result(i1,i2) >= k4]
+    if (!SkScalarNearlyZero(fK[3])) {
+        i1.join(i2);
+        return i1;
+    }
+
+    // If both K2 or K3 are non-zero, both i1 and i2 appear.
+    if (!SkScalarNearlyZero(fK[1]) && !SkScalarNearlyZero(fK[2])) {
+        i1.join(i2);
+        return i1;
+    }
+
+    // If k2 is non-zero, output can be produced whenever i1 is non-transparent.
+    // [k3 = k4 = 0 => result(i1,i2) = k1*i1*i2 + k2*i1 = (k1*i2 + k2)*i1]
+    if (!SkScalarNearlyZero(fK[1])) {
+        return i1;
+    }
+
+    // If k3 is non-zero, output can be produced whenever i2 is non-transparent.
+    // [k2 = k4 = 0 => result(i1,i2) = k1*i1*i2 + k3*i2 = (k1*i1 + k3)*i2]
+    if (!SkScalarNearlyZero(fK[2])) {
+        return i2;
+    }
+
+    // If just k1 is non-zero, output will only be produce where both inputs
+    // are non-transparent. Use intersection.
+    // [k1 > 0 and k2 = k3 = k4 = 0 => result(i1,i2) = k1*i1*i2]
+    if (!SkScalarNearlyZero(fK[0])) {
+        if (!i1.intersect(i2)) {
+            return SkIRect::MakeEmpty();
+        }
+        return i1;
+    }
+
+    // [k1 = k2 = k3 = k4 = 0 => result(i1,i2) = 0]
+    return SkIRect::MakeEmpty();
+}
+
 #if SK_SUPPORT_GPU
 
 namespace {
diff --git a/src/effects/SkXfermodeImageFilter.cpp b/src/effects/SkXfermodeImageFilter.cpp
index f7ce0a3027..ddc5d99b5e 100644
--- a/src/effects/SkXfermodeImageFilter.cpp
+++ b/src/effects/SkXfermodeImageFilter.cpp
@@ -40,6 +40,8 @@ protected:
                                         SkIPoint* offset) const override;
     sk_sp<SkImageFilter> onMakeColorSpace(SkColorSpaceXformer*) const override;
 
+    SkIRect onFilterBounds(const SkIRect&, const SkMatrix&, MapDirection) const override;
+
 #if SK_SUPPORT_GPU
     sk_sp<SkSpecialImage> filterImageGPU(SkSpecialImage* source,
                                          sk_sp<SkSpecialImage> background,
@@ -173,6 +175,49 @@ sk_sp<SkSpecialImage> SkXfermodeImageFilter_Base::onFilterImage(SkSpecialImage*
     return surf->makeImageSnapshot();
 }
 
+SkIRect SkXfermodeImageFilter_Base::onFilterBounds(const SkIRect& src,
+                                                   const SkMatrix& ctm,
+                                                   MapDirection direction) const {
+    if (kReverse_MapDirection == direction) {
+        return SkImageFilter::onFilterBounds(src, ctm, direction);
+    }
+
+    SkASSERT(2 == this->countInputs());
+    auto getBackground = [&]() {
+        return this->getInput(0) ? this->getInput(0)->filterBounds(src, ctm, direction) : src;
+    };
+    auto getForeground = [&]() {
+        return this->getInput(1) ? this->getInput(1)->filterBounds(src, ctm, direction) : src;
+    };
+    switch (fMode) {
+        case SkBlendMode::kClear:
+            return SkIRect::MakeEmpty();
+
+        case SkBlendMode::kSrc:
+        case SkBlendMode::kDstATop:
+            return getForeground();
+
+        case SkBlendMode::kDst:
+        case SkBlendMode::kSrcATop:
+            return getBackground();
+
+        case SkBlendMode::kSrcIn:
+        case SkBlendMode::kDstIn: {
+            auto result = getBackground();
+            if (!result.intersect(getForeground())) {
+                return SkIRect::MakeEmpty();
+            }
+            return result;
+        }
+
+        default: {
+            auto result = getBackground();
+            result.join(getForeground());
+            return result;
+        }
+    }
+}
+
 sk_sp<SkImageFilter> SkXfermodeImageFilter_Base::onMakeColorSpace(SkColorSpaceXformer* xformer)
 const {
     SkASSERT(2 == this->countInputs());
diff --git a/tests/ImageFilterTest.cpp b/tests/ImageFilterTest.cpp
index a0618e5893..05c0bffbea 100644
--- a/tests/ImageFilterTest.cpp
+++ b/tests/ImageFilterTest.cpp
@@ -5,6 +5,7 @@
  * found in the LICENSE file.
  */
 
+#include "SkArithmeticImageFilter.h"
 #include "SkBitmap.h"
 #include "SkBlurImageFilter.h"
 #include "SkCanvas.h"
@@ -288,6 +289,29 @@ private:
     SkTArray<Filter> fFilters;
 };
 
+class FixedBoundsImageFilter : public SkImageFilter {
+public:
+    FixedBoundsImageFilter(const SkIRect& bounds)
+            : SkImageFilter(nullptr, 0, nullptr), fBounds(bounds) {}
+
+private:
+#ifndef SK_IGNORE_TO_STRING
+    void toString(SkString*) const override {}
+#endif
+    Factory getFactory() const override { return nullptr; }
+
+    sk_sp<SkSpecialImage> onFilterImage(SkSpecialImage* src, const Context&,
+                                        SkIPoint* offset) const override {
+        return nullptr;
+    }
+    sk_sp<SkImageFilter> onMakeColorSpace(SkColorSpaceXformer*) const override { return nullptr; }
+
+    SkIRect onFilterBounds(const SkIRect&, const SkMatrix&, MapDirection) const override {
+        return fBounds;
+    }
+
+    SkIRect fBounds;
+};
 }
 
 sk_sp<SkFlattenable> MatrixTestImageFilter::CreateProc(SkReadBuffer& buffer) {
@@ -1916,3 +1940,117 @@ DEF_TEST(ImageFilterColorSpaceDAG, reporter) {
 
     REPORTER_ASSERT(reporter, filter->cloneCount() == 1u);
 }
+
+// Test XfermodeimageFilter::onFilterBounds with different blending modes.
+DEF_TEST(XfermodeImageFilterBounds, reporter) {
+    SkIRect background_rect = SkIRect::MakeXYWH(0, 0, 100, 100);
+    SkIRect foreground_rect = SkIRect::MakeXYWH(50, 50, 100, 100);
+    sk_sp<SkImageFilter> background(new FixedBoundsImageFilter(background_rect));
+    sk_sp<SkImageFilter> foreground(new FixedBoundsImageFilter(foreground_rect));
+
+    const int kModeCount = static_cast<int>(SkBlendMode::kLastMode) + 1;
+    SkIRect expectedBounds[kModeCount];
+    // Expect union of input rects by default.
+    for (int i = 0; i < kModeCount; ++i) {
+        expectedBounds[i] = background_rect;
+        expectedBounds[i].join(foreground_rect);
+    }
+
+    SkIRect intersection = background_rect;
+    intersection.intersect(foreground_rect);
+    expectedBounds[static_cast<int>(SkBlendMode::kClear)] = SkIRect::MakeEmpty();
+    expectedBounds[static_cast<int>(SkBlendMode::kSrc)] = foreground_rect;
+    expectedBounds[static_cast<int>(SkBlendMode::kDst)] = background_rect;
+    expectedBounds[static_cast<int>(SkBlendMode::kSrcIn)] = intersection;
+    expectedBounds[static_cast<int>(SkBlendMode::kDstIn)] = intersection;
+    expectedBounds[static_cast<int>(SkBlendMode::kSrcATop)] = background_rect;
+    expectedBounds[static_cast<int>(SkBlendMode::kDstATop)] = foreground_rect;
+
+    // The value of this variable doesn't matter because we use inputs with fixed bounds.
+    SkIRect src = SkIRect::MakeXYWH(11, 22, 33, 44);
+    for (int i = 0; i < kModeCount; ++i) {
+        sk_sp<SkImageFilter> xfermode(SkXfermodeImageFilter::Make(static_cast<SkBlendMode>(i),
+                                                                  background, foreground, nullptr));
+        auto bounds =
+                xfermode->filterBounds(src, SkMatrix::I(), SkImageFilter::kForward_MapDirection);
+        REPORTER_ASSERT(reporter, bounds == expectedBounds[i]);
+    }
+
+    // Test empty intersection.
+    sk_sp<SkImageFilter> background2(new FixedBoundsImageFilter(SkIRect::MakeXYWH(0, 0, 20, 20)));
+    sk_sp<SkImageFilter> foreground2(new FixedBoundsImageFilter(SkIRect::MakeXYWH(40, 40, 50, 50)));
+    sk_sp<SkImageFilter> xfermode(SkXfermodeImageFilter::Make(
+            SkBlendMode::kSrcIn, std::move(background2), std::move(foreground2), nullptr));
+    auto bounds = xfermode->filterBounds(src, SkMatrix::I(), SkImageFilter::kForward_MapDirection);
+    REPORTER_ASSERT(reporter, bounds.isEmpty());
+}
+
+static void test_arithmetic_bounds(skiatest::Reporter* reporter, float k1, float k2, float k3,
+                                   float k4, sk_sp<SkImageFilter> background,
+                                   sk_sp<SkImageFilter> foreground,
+                                   const SkImageFilter::CropRect* crop, const SkIRect& expected) {
+    sk_sp<SkImageFilter> arithmetic(
+            SkArithmeticImageFilter::Make(k1, k2, k3, k4, false, background, foreground, crop));
+    // The value of the input rect doesn't matter because we use inputs with fixed bounds.
+    SkIRect bounds = arithmetic->filterBounds(SkIRect::MakeXYWH(11, 22, 33, 44), SkMatrix::I(),
+                                              SkImageFilter::kForward_MapDirection);
+    REPORTER_ASSERT(reporter, expected == bounds);
+}
+
+static void test_arithmetic_combinations(skiatest::Reporter* reporter, float v) {
+    SkIRect background_rect = SkIRect::MakeXYWH(0, 0, 100, 100);
+    SkIRect foreground_rect = SkIRect::MakeXYWH(50, 50, 100, 100);
+    sk_sp<SkImageFilter> background(new FixedBoundsImageFilter(background_rect));
+    sk_sp<SkImageFilter> foreground(new FixedBoundsImageFilter(foreground_rect));
+
+    SkIRect union_rect = background_rect;
+    union_rect.join(foreground_rect);
+    SkIRect intersection = background_rect;
+    intersection.intersect(foreground_rect);
+
+    test_arithmetic_bounds(reporter, 0, 0, 0, 0, background, foreground, nullptr,
+                           SkIRect::MakeEmpty());
+    test_arithmetic_bounds(reporter, 0, 0, 0, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, 0, 0, v, 0, background, foreground, nullptr, background_rect);
+    test_arithmetic_bounds(reporter, 0, 0, v, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, 0, v, 0, 0, background, foreground, nullptr, foreground_rect);
+    test_arithmetic_bounds(reporter, 0, v, 0, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, 0, v, v, 0, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, 0, v, v, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, v, 0, 0, 0, background, foreground, nullptr, intersection);
+    test_arithmetic_bounds(reporter, v, 0, 0, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, v, 0, v, 0, background, foreground, nullptr, background_rect);
+    test_arithmetic_bounds(reporter, v, 0, v, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, v, v, 0, 0, background, foreground, nullptr, foreground_rect);
+    test_arithmetic_bounds(reporter, v, v, 0, v, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, v, v, v, 0, background, foreground, nullptr, union_rect);
+    test_arithmetic_bounds(reporter, v, v, v, v, background, foreground, nullptr, union_rect);
+
+    // Test with crop. When k4 is non-zero, the result is expected to be crop_rect
+    // regardless of inputs because the filter affects the whole crop area.
+    SkIRect crop_rect = SkIRect::MakeXYWH(-111, -222, 333, 444);
+    SkImageFilter::CropRect crop(SkRect::Make(crop_rect));
+    test_arithmetic_bounds(reporter, 0, 0, 0, 0, background, foreground, &crop,
+                           SkIRect::MakeEmpty());
+    test_arithmetic_bounds(reporter, 0, 0, 0, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, 0, 0, v, 0, background, foreground, &crop, background_rect);
+    test_arithmetic_bounds(reporter, 0, 0, v, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, 0, v, 0, 0, background, foreground, &crop, foreground_rect);
+    test_arithmetic_bounds(reporter, 0, v, 0, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, 0, v, v, 0, background, foreground, &crop, union_rect);
+    test_arithmetic_bounds(reporter, 0, v, v, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, v, 0, 0, 0, background, foreground, &crop, intersection);
+    test_arithmetic_bounds(reporter, v, 0, 0, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, v, 0, v, 0, background, foreground, &crop, background_rect);
+    test_arithmetic_bounds(reporter, v, 0, v, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, v, v, 0, 0, background, foreground, &crop, foreground_rect);
+    test_arithmetic_bounds(reporter, v, v, 0, v, background, foreground, &crop, crop_rect);
+    test_arithmetic_bounds(reporter, v, v, v, 0, background, foreground, &crop, union_rect);
+    test_arithmetic_bounds(reporter, v, v, v, v, background, foreground, &crop, crop_rect);
+}
+
+// Test ArithmeticImageFilter::onFilterBounds with different blending modes.
+DEF_TEST(ArithmeticImageFilterBounds, reporter) {
+    test_arithmetic_combinations(reporter, 1);
+    test_arithmetic_combinations(reporter, 0.5);
+}