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

6 files changed, 206 insertions, 5 deletions

diff --git a/gyp/core.gypi b/gyp/core.gypi
index d8f1715d93..4626a726e3 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 0000000000..720d4fa66f
--- /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 0000000000..529cb1f801
--- /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 23223da516..cb68f396a3 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 @@ public:
     }
 };
 
+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 3858f8145f..ec18428252 100644
--- a/tools/PictureRenderer.h
+++ b/tools/PictureRenderer.h
@@ -43,6 +43,7 @@ public:
     enum BBoxHierarchyType {
         kNone_BBoxHierarchyType = 0,
         kRTree_BBoxHierarchyType,
+        kTileGrid_BBoxHierarchyType,
     };
 
     /**
@@ -83,6 +84,11 @@ public:
         fBBoxHierarchyType = bbhType;
     }
 
+    void setGridSize(int width, int height) {
+        fGridWidth = width;
+        fGridHeight = height;
+    }
+
     bool isUsingBitmapDevice() {
         return kBitmap_DeviceType == fDeviceType;
     }
@@ -98,6 +104,8 @@ public:
         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 @@ public:
         : 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 @@ protected:
     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 8b1de3c36a..f0f908dfd0 100644
--- a/tools/bench_pictures_main.cpp
+++ b/tools/bench_pictures_main.cpp
@@ -78,9 +78,12 @@ static void usage(const char* argv0) {
 "                          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 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
     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 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
                 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 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
 
             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 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
 
                 if (0 == strcmp(*argv, "pow2tile")) {
                     isPowerOf2Mode = true;
+                } else {
+                    gridSupported = true;
                 }
 
                 ++argv;
@@ -270,6 +293,7 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
                 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 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
         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 @@ static void parse_commandline(int argc, char* const argv[], SkTArray<SkString>*
     }
 
     renderer->setBBoxHierarchyType(bbhType);
+    renderer->setGridSize(gridWidth, gridHeight);
     benchmark->setRenderer(renderer);
     benchmark->setRepeats(repeats);
     benchmark->setDeviceType(deviceType);