Adding SkTileGrid: a new subclass of BBoxHierarchy, optimized for tiled playback.
Review URL: https://codereview.appspot.com/6820093
git-svn-id: http://skia.googlecode.com/svn/trunk@6314 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gyp/core.gypi b/gyp/core.gypi
index d8f1715..4626a72 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -159,11 +159,13 @@
'<(skia_src_path)/core/SkStroke.cpp',
'<(skia_src_path)/core/SkStrokerPriv.cpp',
'<(skia_src_path)/core/SkStrokerPriv.h',
+ '<(skia_src_path)/core/SkTemplatesPriv.h',
'<(skia_src_path)/core/SkTextFormatParams.h',
+ '<(skia_src_path)/core/SkTileGrid.cpp',
+ '<(skia_src_path)/core/SkTileGrid.h',
'<(skia_src_path)/core/SkTLS.cpp',
'<(skia_src_path)/core/SkTSearch.cpp',
'<(skia_src_path)/core/SkTSort.h',
- '<(skia_src_path)/core/SkTemplatesPriv.h',
'<(skia_src_path)/core/SkTypeface.cpp',
'<(skia_src_path)/core/SkTypefaceCache.cpp',
'<(skia_src_path)/core/SkTypefaceCache.h',
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
new file mode 100644
index 0000000..720d4fa
--- /dev/null
+++ b/src/core/SkTileGrid.cpp
@@ -0,0 +1,68 @@
+
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkTileGrid.h"
+
+SkTileGrid::SkTileGrid(int tileWidth, int tileHeight, int xTileCount, int yTileCount)
+{
+ fTileWidth = tileWidth;
+ fTileHeight = tileHeight;
+ fXTileCount = xTileCount;
+ fYTileCount = yTileCount;
+ fTileCount = fXTileCount * fYTileCount;
+ fInsertionCount = 0;
+
+ fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
+}
+
+SkTileGrid::~SkTileGrid() {
+ SkDELETE_ARRAY(fTileData);
+}
+
+SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
+ return fTileData[y * fXTileCount + x];
+}
+
+void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
+ SkASSERT(!bounds.isEmpty());
+ SkIRect dilatedBounds = bounds;
+ dilatedBounds.outset(1,1); // Consideration for filtering and AA
+
+ int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fTileWidth, fXTileCount - 1), 0);
+ int maxTileX = SkMax32(SkMin32(dilatedBounds.right() / fTileWidth, fXTileCount - 1), 0);
+ int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fTileHeight, fYTileCount -1), 0);
+ int maxTileY = SkMax32(SkMin32(dilatedBounds.bottom() / fTileHeight, fYTileCount -1), 0);
+
+ for (int x = minTileX; x <= maxTileX; x++) {
+ for (int y = minTileY; y <= maxTileY; y++) {
+ this->tile(x, y).push(data);
+ }
+ }
+ fInsertionCount++;
+}
+
+void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) {
+ SkASSERT(query.width() == fTileWidth + 2 && query.height() == fTileHeight + 2);
+ SkASSERT((query.left() + 1) % fTileWidth == 0);
+ SkASSERT((query.top() + 1) % fTileHeight == 0);
+ SkASSERT(results);
+ // The +1 is to compensate for the outset in applied SkCanvas::getClipBounds
+ *results = this->tile((query.left() + 1) / fTileWidth, (query.top() + 1) / fTileHeight);
+}
+
+void SkTileGrid::clear() {
+ for (int i = 0; i < fTileCount; i++) {
+ fTileData[i].reset();
+ }
+}
+
+int SkTileGrid::getCount() const {
+ return fInsertionCount;
+}
+
+
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
new file mode 100644
index 0000000..529cb1f
--- /dev/null
+++ b/src/core/SkTileGrid.h
@@ -0,0 +1,64 @@
+
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTileGrid_DEFINED
+#define SkTileGrid_DEFINED
+
+#include "SkBBoxHierarchy.h"
+
+/**
+ * Subclass of SkBBoxHierarchy that stores elements in buckets that correspond
+ * to tile regions, disposed in a regular grid. This is useful when the tile
+ * structure that will be use in search() calls is known prior to insertion.
+ * Calls to search will return in constant time.
+ *
+ * Note: Current implementation of search() only supports looking-up regions
+ * that are an exact match to a single tile. Implementation could be augmented
+ * to support arbitrary rectangles, but performance would be sub-optimal.
+ */
+class SkTileGrid : public SkBBoxHierarchy {
+public:
+ SkTileGrid(int tileWidth, int tileHeight, int xTileCount, int yTileCount);
+
+ virtual ~SkTileGrid();
+
+ /**
+ * Insert a data pointer and corresponding bounding box
+ * @param data The data pointer, may be NULL
+ * @param bounds The bounding box, should not be empty
+ * @param defer Ignored, TileArray does not defer insertions
+ */
+ virtual void insert(void* data, const SkIRect& bounds, bool) SK_OVERRIDE;
+
+ virtual void flushDeferredInserts() SK_OVERRIDE {};
+
+ /**
+ * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
+ * The query argument is expected to be an exact match to a tile of the grid
+ */
+ virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
+
+ virtual void clear() SK_OVERRIDE;
+
+ /**
+ * Gets the number of insertions
+ */
+ virtual int getCount() const SK_OVERRIDE;
+
+private:
+ SkTDArray<void *>& tile(int x, int y);
+
+ int fTileWidth, fTileHeight, fXTileCount, fYTileCount, fTileCount;
+ SkTDArray<void *> *fTileData;
+ int fInsertionCount;
+
+ typedef SkBBoxHierarchy INHERITED;
+};
+
+#endif
+
diff --git a/tools/PictureRenderer.cpp b/tools/PictureRenderer.cpp
index 23223da..cb68f39 100644
--- a/tools/PictureRenderer.cpp
+++ b/tools/PictureRenderer.cpp
@@ -22,6 +22,7 @@
#include "SkScalar.h"
#include "SkString.h"
#include "SkTemplates.h"
+#include "SkTileGrid.h"
#include "SkTDArray.h"
#include "SkThreadUtils.h"
#include "SkTypes.h"
@@ -564,12 +565,37 @@
}
};
+class TileGridPicture : public SkPicture {
+public:
+ TileGridPicture(int tileWidth, int tileHeight, int xTileCount, int yTileCount) {
+ fTileWidth = tileWidth;
+ fTileHeight = tileHeight;
+ fXTileCount = xTileCount;
+ fYTileCount = yTileCount;
+ }
+
+ virtual SkBBoxHierarchy* createBBoxHierarchy() const SK_OVERRIDE{
+ return SkNEW_ARGS(SkTileGrid, (fTileWidth, fTileHeight, fXTileCount, fYTileCount));
+ }
+private:
+ int fTileWidth, fTileHeight, fXTileCount, fYTileCount;
+};
+
SkPicture* PictureRenderer::createPicture() {
switch (fBBoxHierarchyType) {
case kNone_BBoxHierarchyType:
return SkNEW(SkPicture);
case kRTree_BBoxHierarchyType:
return SkNEW(RTreePicture);
+ case kTileGrid_BBoxHierarchyType:
+ {
+ int xTileCount = fPicture->width() / fGridWidth +
+ ((fPicture->width() % fGridWidth) ? 1 : 0);
+ int yTileCount = fPicture->height() / fGridHeight +
+ ((fPicture->height() % fGridHeight) ? 1 : 0);
+ return SkNEW_ARGS(TileGridPicture, (fGridWidth, fGridHeight, xTileCount,
+ yTileCount));
+ }
}
SkASSERT(0); // invalid bbhType
return NULL;
diff --git a/tools/PictureRenderer.h b/tools/PictureRenderer.h
index 3858f81..ec18428 100644
--- a/tools/PictureRenderer.h
+++ b/tools/PictureRenderer.h
@@ -43,6 +43,7 @@
enum BBoxHierarchyType {
kNone_BBoxHierarchyType = 0,
kRTree_BBoxHierarchyType,
+ kTileGrid_BBoxHierarchyType,
};
/**
@@ -83,6 +84,11 @@
fBBoxHierarchyType = bbhType;
}
+ void setGridSize(int width, int height) {
+ fGridWidth = width;
+ fGridHeight = height;
+ }
+
bool isUsingBitmapDevice() {
return kBitmap_DeviceType == fDeviceType;
}
@@ -98,6 +104,8 @@
SkString config = this->getConfigNameInternal();
if (kRTree_BBoxHierarchyType == fBBoxHierarchyType) {
config.append("_rtree");
+ } else if (kTileGrid_BBoxHierarchyType == fBBoxHierarchyType) {
+ config.append("_grid");
}
#if SK_SUPPORT_GPU
if (this->isUsingGpuDevice()) {
@@ -129,6 +137,8 @@
: fPicture(NULL)
, fDeviceType(kBitmap_DeviceType)
, fBBoxHierarchyType(kNone_BBoxHierarchyType)
+ , fGridWidth(0)
+ , fGridHeight(0)
#if SK_SUPPORT_GPU
, fGrContext(fGrContextFactory.get(GrContextFactory::kNative_GLContextType))
#endif
@@ -145,7 +155,7 @@
SkPicture* fPicture;
SkDeviceTypes fDeviceType;
BBoxHierarchyType fBBoxHierarchyType;
-
+ int fGridWidth, fGridHeight; // used when fBBoxHierarchyType is TileGrid
#if SK_SUPPORT_GPU
GrContextFactory fGrContextFactory;
diff --git a/tools/bench_pictures_main.cpp b/tools/bench_pictures_main.cpp
index 8b1de3c..f0f908d 100644
--- a/tools/bench_pictures_main.cpp
+++ b/tools/bench_pictures_main.cpp
@@ -78,9 +78,12 @@
" than 1. Only works with tiled rendering.\n"
" --pipe: Benchmark SkGPipe rendering. Currently incompatible with \"mode\".\n");
SkDebugf(
-" --bbh bbhType: Set the bounding box hierarchy type to be used. Accepted\n"
-" values are: none, rtree. Default value is none.\n"
-" Not compatible with --pipe.\n");
+" --bbh bbhType [width height]: Set the bounding box hierarchy type to\n"
+" be used. Accepted values are: none, rtree, grid. Default\n"
+" value is none. Not compatible with --pipe. With value\n"
+" 'grid', width and height must be specified. 'grid' can\n"
+" only be used with modes tile, record, and\n"
+" playbackCreation.");
SkDebugf(
" --device bitmap"
#if SK_SUPPORT_GPU
@@ -165,8 +168,11 @@
bool useTiles = false;
const char* widthString = NULL;
const char* heightString = NULL;
+ int gridWidth = 0;
+ int gridHeight = 0;
bool isPowerOf2Mode = false;
const char* mode = NULL;
+ bool gridSupported = false;
sk_tools::PictureRenderer::BBoxHierarchyType bbhType =
sk_tools::PictureRenderer::kNone_BBoxHierarchyType;
for (++argv; argv < stop; ++argv) {
@@ -222,6 +228,20 @@
bbhType = sk_tools::PictureRenderer::kNone_BBoxHierarchyType;
} else if (0 == strcmp(*argv, "rtree")) {
bbhType = sk_tools::PictureRenderer::kRTree_BBoxHierarchyType;
+ } else if (0 == strcmp(*argv, "grid")) {
+ bbhType = sk_tools::PictureRenderer::kTileGrid_BBoxHierarchyType;
+ ++argv;
+ if (argv >= stop) {
+ gLogger.logError("Missing width for --bbh grid\n");
+ PRINT_USAGE_AND_EXIT;
+ }
+ gridWidth = atoi(*argv);
+ ++argv;
+ if (argv >= stop) {
+ gLogger.logError("Missing height for --bbh grid\n");
+ PRINT_USAGE_AND_EXIT;
+ }
+ gridHeight = atoi(*argv);
} else {
SkString err;
err.printf("%s is not a valid value for --bbhType\n", *argv);
@@ -243,6 +263,7 @@
if (0 == strcmp(*argv, "record")) {
renderer.reset(SkNEW(sk_tools::RecordPictureRenderer));
+ gridSupported = true;
} else if (0 == strcmp(*argv, "simple")) {
renderer.reset(SkNEW(sk_tools::SimplePictureRenderer));
} else if ((0 == strcmp(*argv, "tile")) || (0 == strcmp(*argv, "pow2tile"))) {
@@ -251,6 +272,8 @@
if (0 == strcmp(*argv, "pow2tile")) {
isPowerOf2Mode = true;
+ } else {
+ gridSupported = true;
}
++argv;
@@ -270,6 +293,7 @@
heightString = *argv;
} else if (0 == strcmp(*argv, "playbackCreation")) {
renderer.reset(SkNEW(sk_tools::PlaybackCreationRenderer));
+ gridSupported = true;
} else {
SkString err;
err.printf("%s is not a valid mode for --mode\n", *argv);
@@ -361,6 +385,12 @@
PRINT_USAGE_AND_EXIT;
}
+ if (sk_tools::PictureRenderer::kTileGrid_BBoxHierarchyType == bbhType &&
+ !gridSupported) {
+ gLogger.logError("'--bbh grid' is not compatible with specified --mode.\n");
+ PRINT_USAGE_AND_EXIT;
+ }
+
if (useTiles) {
SkASSERT(NULL == renderer);
sk_tools::TiledPictureRenderer* tiledRenderer;
@@ -441,6 +471,7 @@
}
renderer->setBBoxHierarchyType(bbhType);
+ renderer->setGridSize(gridWidth, gridHeight);
benchmark->setRenderer(renderer);
benchmark->setRepeats(repeats);
benchmark->setDeviceType(deviceType);