Implement intra-frame cacheing in image filters.
When image filters are processed within Skia, they simply do
a blind recursion. This has the side-effect of turning the
DAG into a tree. I.e., nodes visited more than once during
the traversal will be processed more than once.
This change implements a very simple cacheing scheme: a
cache is created before traversing the DAG, and handed
into the processing traversal. Before recursing into a child
in SkImageFilter::filterImage(), the cache is checked for a
hit, and early-out is performed. Otherwise, the node is
processed, and its result bitmap and location (offset) are
cached, but only if it contains two or more children and
thus will be visited again during the traversal.
Currently, the child count is approximated with the
refcount. This is good enough in most cases (and exactly
correct for the Chrome use case). We could add an exact
child count to the image filter, but this will require
violating the immutability of image filters slightly in
order to bump the child count as nodes are connected. I
leave it up to the reviewer to decide which is better.
R=reed@google.com
Author: senorblanco@chromium.org
Review URL: https://codereview.chromium.org/230653005
git-svn-id: http://skia.googlecode.com/svn/trunk@14160 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gm/imagefiltersbase.cpp b/gm/imagefiltersbase.cpp
index b31fbeb..2970ff2 100644
--- a/gm/imagefiltersbase.cpp
+++ b/gm/imagefiltersbase.cpp
@@ -26,7 +26,7 @@
protected:
FailImageFilter() : INHERITED(0) {}
virtual bool onFilterImage(Proxy*, const SkBitmap& src, const Context&,
- SkBitmap* result, SkIPoint* offset) const {
+ SkBitmap* result, SkIPoint* offset) const SK_OVERRIDE {
return false;
}
@@ -52,8 +52,9 @@
protected:
IdentityImageFilter() : INHERITED(0) {}
virtual bool onFilterImage(Proxy*, const SkBitmap& src, const Context&,
- SkBitmap* result, SkIPoint* offset) const {
+ SkBitmap* result, SkIPoint* offset) const SK_OVERRIDE {
*result = src;
+ offset->set(0, 0);
return true;
}
diff --git a/include/core/SkImageFilter.h b/include/core/SkImageFilter.h
index 0f52b69..7a65f53 100644
--- a/include/core/SkImageFilter.h
+++ b/include/core/SkImageFilter.h
@@ -16,7 +16,6 @@
class SkColorFilter;
class SkBaseDevice;
struct SkIPoint;
-class SkShader;
class GrEffectRef;
class GrTexture;
@@ -49,16 +48,28 @@
uint32_t fFlags;
};
+ class Cache : public SkRefCnt {
+ public:
+ // By default, we cache only image filters with 2 or more children.
+ static Cache* Create(int minChildren = 2);
+ virtual ~Cache() {}
+ virtual bool get(const SkImageFilter* key, SkBitmap* result, SkIPoint* offset) = 0;
+ virtual void set(const SkImageFilter* key,
+ const SkBitmap& result, const SkIPoint& offset) = 0;
+ };
+
class Context {
public:
- Context(const SkMatrix& ctm, const SkIRect& clipBounds) :
- fCTM(ctm), fClipBounds(clipBounds) {
+ Context(const SkMatrix& ctm, const SkIRect& clipBounds, Cache* cache) :
+ fCTM(ctm), fClipBounds(clipBounds), fCache(cache) {
}
const SkMatrix& ctm() const { return fCTM; }
const SkIRect& clipBounds() const { return fClipBounds; }
+ Cache* cache() const { return fCache; }
private:
SkMatrix fCTM;
SkIRect fClipBounds;
+ Cache* fCache;
};
class Proxy {
diff --git a/src/core/SkCanvas.cpp b/src/core/SkCanvas.cpp
index b67a657..a3e2969 100644
--- a/src/core/SkCanvas.cpp
+++ b/src/core/SkCanvas.cpp
@@ -1258,7 +1258,9 @@
SkMatrix matrix = *iter.fMatrix;
matrix.postTranslate(SkIntToScalar(-pos.x()), SkIntToScalar(-pos.y()));
SkIRect clipBounds = SkIRect::MakeWH(srcDev->width(), srcDev->height());
- SkImageFilter::Context ctx(matrix, clipBounds);
+ SkImageFilter::Cache* cache = SkImageFilter::Cache::Create();
+ SkAutoUnref aur(cache);
+ SkImageFilter::Context ctx(matrix, clipBounds, cache);
if (filter->filterImage(&proxy, src, ctx, &dst, &offset)) {
SkPaint tmpUnfiltered(*paint);
tmpUnfiltered.setImageFilter(NULL);
@@ -1298,7 +1300,9 @@
SkMatrix matrix = *iter.fMatrix;
matrix.postTranslate(SkIntToScalar(-pos.x()), SkIntToScalar(-pos.y()));
SkIRect clipBounds = SkIRect::MakeWH(bitmap.width(), bitmap.height());
- SkImageFilter::Context ctx(matrix, clipBounds);
+ SkImageFilter::Cache* cache = SkImageFilter::Cache::Create();
+ SkAutoUnref aur(cache);
+ SkImageFilter::Context ctx(matrix, clipBounds, cache);
if (filter->filterImage(&proxy, bitmap, ctx, &dst, &offset)) {
SkPaint tmpUnfiltered(*paint);
tmpUnfiltered.setImageFilter(NULL);
diff --git a/src/core/SkImageFilter.cpp b/src/core/SkImageFilter.cpp
index 2be66e7..8d0c22d 100644
--- a/src/core/SkImageFilter.cpp
+++ b/src/core/SkImageFilter.cpp
@@ -12,6 +12,7 @@
#include "SkReadBuffer.h"
#include "SkWriteBuffer.h"
#include "SkRect.h"
+#include "SkTDynamicHash.h"
#include "SkValidationUtils.h"
#if SK_SUPPORT_GPU
#include "GrContext.h"
@@ -96,14 +97,23 @@
bool SkImageFilter::filterImage(Proxy* proxy, const SkBitmap& src,
const Context& context,
SkBitmap* result, SkIPoint* offset) const {
+ Cache* cache = context.cache();
SkASSERT(result);
SkASSERT(offset);
+ SkASSERT(cache);
+ if (cache->get(this, result, offset)) {
+ return true;
+ }
/*
* Give the proxy first shot at the filter. If it returns false, ask
* the filter to do it.
*/
- return (proxy && proxy->filterImage(this, src, context, result, offset)) ||
- this->onFilterImage(proxy, src, context, result, offset);
+ if ((proxy && proxy->filterImage(this, src, context, result, offset)) ||
+ this->onFilterImage(proxy, src, context, result, offset)) {
+ cache->set(this, *result, *offset);
+ return true;
+ }
+ return false;
}
bool SkImageFilter::filterBounds(const SkIRect& src, const SkMatrix& ctm,
@@ -321,3 +331,83 @@
}
}
#endif
+
+static uint32_t compute_hash(const uint32_t* data, int count) {
+ uint32_t hash = 0;
+
+ for (int i = 0; i < count; ++i) {
+ uint32_t k = data[i];
+ k *= 0xcc9e2d51;
+ k = (k << 15) | (k >> 17);
+ k *= 0x1b873593;
+
+ hash ^= k;
+ hash = (hash << 13) | (hash >> 19);
+ hash *= 5;
+ hash += 0xe6546b64;
+ }
+
+ // hash ^= size;
+ hash ^= hash >> 16;
+ hash *= 0x85ebca6b;
+ hash ^= hash >> 13;
+ hash *= 0xc2b2ae35;
+ hash ^= hash >> 16;
+
+ return hash;
+}
+
+class CacheImpl : public SkImageFilter::Cache {
+public:
+ explicit CacheImpl(int minChildren) : fMinChildren(minChildren) {}
+ virtual ~CacheImpl();
+ bool get(const SkImageFilter* key, SkBitmap* result, SkIPoint* offset) SK_OVERRIDE;
+ void set(const SkImageFilter* key, const SkBitmap& result, const SkIPoint& offset) SK_OVERRIDE;
+private:
+ typedef const SkImageFilter* Key;
+ struct Value {
+ Value(Key key, const SkBitmap& bitmap, const SkIPoint& offset)
+ : fKey(key), fBitmap(bitmap), fOffset(offset) {}
+ Key fKey;
+ SkBitmap fBitmap;
+ SkIPoint fOffset;
+ static const Key& GetKey(const Value& v) {
+ return v.fKey;
+ }
+ static uint32_t Hash(Key key) {
+ return compute_hash(reinterpret_cast<const uint32_t*>(&key), sizeof(Key) / sizeof(uint32_t));
+ }
+ };
+ SkTDynamicHash<Value, Key> fData;
+ int fMinChildren;
+};
+
+bool CacheImpl::get(const SkImageFilter* key, SkBitmap* result, SkIPoint* offset) {
+ Value* v = fData.find(key);
+ if (v) {
+ *result = v->fBitmap;
+ *offset = v->fOffset;
+ return true;
+ }
+ return false;
+}
+
+void CacheImpl::set(const SkImageFilter* key, const SkBitmap& result, const SkIPoint& offset) {
+ if (key->getRefCnt() >= fMinChildren) {
+ fData.add(new Value(key, result, offset));
+ }
+}
+
+SkImageFilter::Cache* SkImageFilter::Cache::Create(int minChildren) {
+ return new CacheImpl(minChildren);
+}
+
+CacheImpl::~CacheImpl() {
+ SkTDynamicHash<Value, Key>::Iter iter(&fData);
+
+ while (!iter.done()) {
+ Value* v = &*iter;
+ ++iter;
+ delete v;
+ }
+}
diff --git a/src/effects/SkDropShadowImageFilter.cpp b/src/effects/SkDropShadowImageFilter.cpp
index 40ab8cf..66a4e8b 100644
--- a/src/effects/SkDropShadowImageFilter.cpp
+++ b/src/effects/SkDropShadowImageFilter.cpp
@@ -15,7 +15,8 @@
#include "SkReadBuffer.h"
#include "SkWriteBuffer.h"
-SkDropShadowImageFilter::SkDropShadowImageFilter(SkScalar dx, SkScalar dy, SkScalar sigma, SkColor color, SkImageFilter* input)
+SkDropShadowImageFilter::SkDropShadowImageFilter(SkScalar dx, SkScalar dy, SkScalar sigma,
+ SkColor color, SkImageFilter* input)
: INHERITED(input)
, fDx(dx)
, fDy(dy)
@@ -25,7 +26,9 @@
{
}
-SkDropShadowImageFilter::SkDropShadowImageFilter(SkScalar dx, SkScalar dy, SkScalar sigmaX, SkScalar sigmaY, SkColor color, SkImageFilter* input, const CropRect* cropRect)
+SkDropShadowImageFilter::SkDropShadowImageFilter(SkScalar dx, SkScalar dy,
+ SkScalar sigmaX, SkScalar sigmaY, SkColor color,
+ SkImageFilter* input, const CropRect* cropRect)
: INHERITED(input, cropRect)
, fDx(dx)
, fDy(dy)
@@ -58,7 +61,9 @@
buffer.writeColor(fColor);
}
-bool SkDropShadowImageFilter::onFilterImage(Proxy* proxy, const SkBitmap& source, const Context& ctx, SkBitmap* result, SkIPoint* offset) const
+bool SkDropShadowImageFilter::onFilterImage(Proxy* proxy, const SkBitmap& source,
+ const Context& ctx,
+ SkBitmap* result, SkIPoint* offset) const
{
SkBitmap src = source;
SkIPoint srcOffset = SkIPoint::Make(0, 0);
@@ -81,7 +86,8 @@
sigma.fX = SkMaxScalar(0, sigma.fX);
sigma.fY = SkMaxScalar(0, sigma.fY);
SkAutoTUnref<SkImageFilter> blurFilter(SkBlurImageFilter::Create(sigma.fX, sigma.fY));
- SkAutoTUnref<SkColorFilter> colorFilter(SkColorFilter::CreateModeFilter(fColor, SkXfermode::kSrcIn_Mode));
+ SkAutoTUnref<SkColorFilter> colorFilter(
+ SkColorFilter::CreateModeFilter(fColor, SkXfermode::kSrcIn_Mode));
SkPaint paint;
paint.setImageFilter(blurFilter.get());
paint.setColorFilter(colorFilter.get());
diff --git a/src/effects/SkTileImageFilter.cpp b/src/effects/SkTileImageFilter.cpp
index b35d852..5496f30 100644
--- a/src/effects/SkTileImageFilter.cpp
+++ b/src/effects/SkTileImageFilter.cpp
@@ -16,7 +16,8 @@
#include "SkShader.h"
#include "SkValidationUtils.h"
-bool SkTileImageFilter::onFilterImage(Proxy* proxy, const SkBitmap& src, const SkImageFilter::Context& ctx,
+bool SkTileImageFilter::onFilterImage(Proxy* proxy, const SkBitmap& src,
+ const Context& ctx,
SkBitmap* dst, SkIPoint* offset) const {
SkBitmap source = src;
SkImageFilter* input = getInput(0);
diff --git a/src/gpu/SkGpuDevice.cpp b/src/gpu/SkGpuDevice.cpp
index 08d4411..58dd030 100644
--- a/src/gpu/SkGpuDevice.cpp
+++ b/src/gpu/SkGpuDevice.cpp
@@ -1536,7 +1536,9 @@
SkMatrix matrix(*draw.fMatrix);
matrix.postTranslate(SkIntToScalar(-left), SkIntToScalar(-top));
SkIRect clipBounds = SkIRect::MakeWH(bitmap.width(), bitmap.height());
- SkImageFilter::Context ctx(matrix, clipBounds);
+ SkImageFilter::Cache* cache = SkImageFilter::Cache::Create();
+ SkAutoUnref aur(cache);
+ SkImageFilter::Context ctx(matrix, clipBounds, cache);
if (filter_texture(this, fContext, texture, filter, w, h, ctx, &filteredBitmap,
&offset)) {
texture = (GrTexture*) filteredBitmap.getTexture();
@@ -1644,7 +1646,9 @@
SkMatrix matrix(*draw.fMatrix);
matrix.postTranslate(SkIntToScalar(-x), SkIntToScalar(-y));
SkIRect clipBounds = SkIRect::MakeWH(devTex->width(), devTex->height());
- SkImageFilter::Context ctx(matrix, clipBounds);
+ SkImageFilter::Cache* cache = SkImageFilter::Cache::Create();
+ SkAutoUnref aur(cache);
+ SkImageFilter::Context ctx(matrix, clipBounds, cache);
if (filter_texture(this, fContext, devTex, filter, w, h, ctx, &filteredBitmap,
&offset)) {
devTex = filteredBitmap.getTexture();
diff --git a/tests/ImageFilterTest.cpp b/tests/ImageFilterTest.cpp
index 4c8ddc6..d2a5843 100644
--- a/tests/ImageFilterTest.cpp
+++ b/tests/ImageFilterTest.cpp
@@ -191,7 +191,8 @@
SkDeviceImageFilterProxy proxy(&device);
SkIPoint loc = SkIPoint::Make(0, 0);
// An empty input should early return and return false
- SkImageFilter::Context ctx(SkMatrix::I(), SkIRect::MakeEmpty());
+ SkAutoTUnref<SkImageFilter::Cache> cache(SkImageFilter::Cache::Create(2));
+ SkImageFilter::Context ctx(SkMatrix::I(), SkIRect::MakeEmpty(), cache.get());
REPORTER_ASSERT(reporter,
!bicubic->filterImage(&proxy, bitmap, ctx, &result, &loc));
}
@@ -247,8 +248,10 @@
SkIPoint offset;
SkString str;
str.printf("filter %d", static_cast<int>(i));
- SkImageFilter::Context ctx(SkMatrix::I(), SkIRect::MakeLargest());
- REPORTER_ASSERT_MESSAGE(reporter, filter->filterImage(&proxy, bitmap, ctx, &result, &offset), str.c_str());
+ SkAutoTUnref<SkImageFilter::Cache> cache(SkImageFilter::Cache::Create(2));
+ SkImageFilter::Context ctx(SkMatrix::I(), SkIRect::MakeLargest(), cache.get());
+ REPORTER_ASSERT_MESSAGE(reporter, filter->filterImage(&proxy, bitmap, ctx,
+ &result, &offset), str.c_str());
REPORTER_ASSERT_MESSAGE(reporter, offset.fX == 20 && offset.fY == 30, str.c_str());
}