Modifying SkTileGrid to support arbitrary query rectangles.
Exposing SkTileGrid functionality in the public API through SkTileGridPicture.
This patch also makes TileGrid and Rtree testable in gm, which revealed errors.
TEST=gm with '--tileGrid'
BUG=http://code.google.com/p/chromium/issues/detail?id=164636
Review URL: https://codereview.appspot.com/6933044
git-svn-id: http://skia.googlecode.com/svn/trunk@6783 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gm/gm.h b/gm/gm.h
index 9460ec0..58dda63 100644
--- a/gm/gm.h
+++ b/gm/gm.h
@@ -39,6 +39,8 @@
kSkipPipe_Flag = 1 << 2,
kSkipTiled_Flag = 1 << 3,
kSkip565_Flag = 1 << 4,
+ kRTree_Flag = 1 << 5,
+ kTileGrid_Flag = 1 << 6,
};
void draw(SkCanvas*);
diff --git a/gm/gmmain.cpp b/gm/gmmain.cpp
index 316251e..b2cc8d8 100644
--- a/gm/gmmain.cpp
+++ b/gm/gmmain.cpp
@@ -29,6 +29,7 @@
#include "SkRefCnt.h"
#include "SkStream.h"
#include "SkTArray.h"
+#include "SkTileGridPicture.h"
#include "SamplePipeControllers.h"
#if SK_SUPPORT_GPU
@@ -129,10 +130,16 @@
};
enum Backend {
- kRaster_Backend,
- kGPU_Backend,
- kPDF_Backend,
- kXPS_Backend,
+ kRaster_Backend,
+ kGPU_Backend,
+ kPDF_Backend,
+ kXPS_Backend,
+};
+
+enum BbhType {
+ kNone_BbhType,
+ kRTree_BbhType,
+ kTileGrid_BbhType,
};
enum ConfigFlags {
@@ -176,7 +183,6 @@
| SkGPipeWriter::kSharedAddressSpace_Flag }
};
-
class GMMain {
public:
GMMain() {
@@ -618,11 +624,18 @@
return retval;
}
- static SkPicture* generate_new_picture(GM* gm) {
+ static SkPicture* generate_new_picture(GM* gm, BbhType bbhType) {
// Pictures are refcounted so must be on heap
- SkPicture* pict = new SkPicture;
+ SkPicture* pict;
SkISize size = gm->getISize();
- SkCanvas* cv = pict->beginRecording(size.width(), size.height());
+ if (kTileGrid_BbhType == bbhType) {
+ pict = new SkTileGridPicture(16, 16, size.width(), size.height());
+ } else {
+ pict = new SkPicture;
+ }
+ uint32_t recordFlags = (kNone_BbhType == bbhType) ?
+ 0 : SkPicture::kOptimizeForClippedPlayback_RecordingFlag;
+ SkCanvas* cv = pict->beginRecording(size.width(), size.height(), recordFlags);
invokeGM(gm, cv, false, false);
pict->endRecording();
@@ -856,9 +869,11 @@
" any differences between those and the newly generated ones\n"
" [--noreplay]: do not exercise SkPicture replay\n"
" [--resourcePath|-i <path>]: directory that stores image resources\n"
+" [--rtree]: use an rtree structure for SkPicture testing\n"
" [--noserialize]: do not exercise SkPicture serialization & deserialization\n"
" [--notexturecache]: disable the gpu texture cache\n"
" [--tiledPipe]: Exercise tiled SkGPipe replay\n"
+" [--tileGrid]: use a tileGrid structure for SkPicture testing\n"
" [--writePath|-w <path>]: write rendered images into this directory\n"
" [--writePicturePath|-wp <path>]: write .skp files into this directory\n"
);
@@ -959,6 +974,7 @@
bool disableTextureCache = false;
SkTDArray<size_t> configs;
bool userConfig = false;
+ BbhType bbhType = kNone_BbhType;
int moduloRemainder = -1;
int moduloDivisor = -1;
@@ -995,6 +1011,10 @@
}
} else if (strcmp(*argv, "--disable-missing-warning") == 0) {
gmmain.fNotifyMissingReadReference = false;
+ } else if (strcmp(*argv, "--rtree") == 0) {
+ bbhType = kRTree_BbhType;
+ } else if (strcmp(*argv, "--tileGrid") == 0) {
+ bbhType = kTileGrid_BbhType;
} else if (strcmp(*argv, "--enable-missing-warning") == 0) {
gmmain.fNotifyMissingReadReference = true;
} else if (strcmp(*argv, "--forceBWtext") == 0) {
@@ -1246,7 +1266,7 @@
ErrorBitfield pictErrors = ERROR_NONE;
//SkAutoTUnref<SkPicture> pict(generate_new_picture(gm));
- SkPicture* pict = gmmain.generate_new_picture(gm);
+ SkPicture* pict = gmmain.generate_new_picture(gm, bbhType);
SkAutoUnref aur(pict);
if ((ERROR_NONE == testErrors) && doReplay) {
diff --git a/gyp/core.gypi b/gyp/core.gypi
index f3402b1..7a67224 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -164,6 +164,7 @@
'<(skia_src_path)/core/SkTextFormatParams.h',
'<(skia_src_path)/core/SkTileGrid.cpp',
'<(skia_src_path)/core/SkTileGrid.h',
+ '<(skia_src_path)/core/SkTileGridPicture.cpp',
'<(skia_src_path)/core/SkTLList.h',
'<(skia_src_path)/core/SkTLS.cpp',
'<(skia_src_path)/core/SkTSearch.cpp',
@@ -255,6 +256,7 @@
'<(skia_include_path)/core/SkTDStack.h',
'<(skia_include_path)/core/SkTDict.h',
'<(skia_include_path)/core/SkTInternalLList.h',
+ '<(skia_include_path)/core/SkTileGridPicture.h',
'<(skia_include_path)/core/SkTRegistry.h',
'<(skia_include_path)/core/SkTScopedPtr.h',
'<(skia_include_path)/core/SkTSearch.h',
diff --git a/include/core/SkTileGridPicture.h b/include/core/SkTileGridPicture.h
new file mode 100644
index 0000000..ef42f8c
--- /dev/null
+++ b/include/core/SkTileGridPicture.h
@@ -0,0 +1,29 @@
+/*
+ * 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 SkTileGridPicture_DEFINED
+#define SkTileGridPicture_DEFINED
+
+#include "SkPicture.h"
+
+/**
+ * Subclass of SkPicture that override the behavior of the
+ * kOptimizeForClippedPlayback_RecordingFlag by creating an SkTileGrid
+ * structure rather than an R-Tree. The tile grid has lower recording
+ * and playback costs, but is less effective at eliminating extraneous
+ * primitives for arbitrary query rectangles. It is most effective for
+ * tiled playback when the tile structure is known at record time.
+ */
+class SkTileGridPicture : public SkPicture {
+public:
+ SkTileGridPicture(int tileWidth, int tileHeight, int width, int height);
+ virtual SkBBoxHierarchy* createBBoxHierarchy() const SK_OVERRIDE;
+private:
+ int fTileWidth, fTileHeight, fXTileCount, fYTileCount;
+};
+
+#endif
\ No newline at end of file
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index f038716..ce40be7 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -8,7 +8,7 @@
#include "SkTileGrid.h"
-SkTileGrid::SkTileGrid(int tileWidth, int tileHeight, int xTileCount, int yTileCount)
+SkTileGrid::SkTileGrid(int tileWidth, int tileHeight, int xTileCount, int yTileCount, SkTileGridNextDatumFunctionPtr nextDatumFunction)
{
fTileWidth = tileWidth;
fTileHeight = tileHeight;
@@ -17,7 +17,7 @@
fTileCount = fXTileCount * fYTileCount;
fInsertionCount = 0;
fGridBounds = SkIRect::MakeXYWH(0, 0, fTileWidth * fXTileCount, fTileHeight * fYTileCount);
-
+ fNextDatumFunction = nextDatumFunction;
fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
}
@@ -52,12 +52,42 @@
}
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);
+ // The +1/-1 is to compensate for the outset in applied SkCanvas::getClipBounds
+ int tileStartX = (query.left() + 1) / fTileWidth;
+ int tileEndX = (query.right() + fTileWidth - 1) / fTileWidth;
+ int tileStartY = (query.top() + 1) / fTileHeight;
+ int tileEndY = (query.bottom() + fTileHeight - 1) / fTileHeight;
+ if (tileStartX >= fXTileCount || tileStartY >= fYTileCount || tileEndX <= 0 || tileEndY <= 0) {
+ return; // query does not intersect the grid
+ }
+ // clamp to grid
+ if (tileStartX < 0) tileStartX = 0;
+ if (tileStartY < 0) tileStartY = 0;
+ if (tileEndX > fXTileCount) tileEndX = fXTileCount;
+ if (tileEndY > fYTileCount) tileEndY = fYTileCount;
+
+ int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
+ if (queryTileCount == 1) {
+ *results = this->tile(tileStartX, tileStartY);
+ } else {
+ results->reset();
+ SkTDArray<int> curPositions;
+ curPositions.setCount(queryTileCount);
+ SkTDArray<void *>** tileRange =
+ (SkTDArray<void *>**)alloca(queryTileCount * sizeof(SkTDArray<void *>*));
+ int tile = 0;
+ for (int x = tileStartX; x < tileEndX; ++x) {
+ for (int y = tileStartY; y < tileEndY; ++y) {
+ tileRange[tile] = &this->tile(x, y);
+ curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
+ ++tile;
+ }
+ }
+ void *nextElement;
+ while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
+ results->push(nextElement);
+ }
+ }
}
void SkTileGrid::clear() {
@@ -68,6 +98,4 @@
int SkTileGrid::getCount() const {
return fInsertionCount;
-}
-
-
+}
\ No newline at end of file
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index 53136bc..7c4bd74 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -10,6 +10,7 @@
#define SkTileGrid_DEFINED
#include "SkBBoxHierarchy.h"
+#include "SkPictureStateTree.h"
/**
* Subclass of SkBBoxHierarchy that stores elements in buckets that correspond
@@ -23,7 +24,10 @@
*/
class SkTileGrid : public SkBBoxHierarchy {
public:
- SkTileGrid(int tileWidth, int tileHeight, int xTileCount, int yTileCount);
+ typedef void* (*SkTileGridNextDatumFunctionPtr)(SkTDArray<void*>** tileData, SkTDArray<int>& tileIndices);
+
+ SkTileGrid(int tileWidth, int tileHeight, int xTileCount, int yTileCount,
+ SkTileGridNextDatumFunctionPtr nextDatumFunction);
virtual ~SkTileGrid();
@@ -50,17 +54,67 @@
*/
virtual int getCount() const SK_OVERRIDE;
+ // Used by search() and in SkTileGridHelper implementations
+ enum {
+ kTileFinished = -1,
+ };
private:
- SkTDArray<void *>& tile(int x, int y);
+ SkTDArray<void*>& tile(int x, int y);
int fTileWidth, fTileHeight, fXTileCount, fYTileCount, fTileCount;
- SkTDArray<void *> *fTileData;
+ SkTDArray<void*>* fTileData;
int fInsertionCount;
SkIRect fGridBounds;
+ SkTileGridNextDatumFunctionPtr fNextDatumFunction;
friend class TileGridTest;
typedef SkBBoxHierarchy INHERITED;
};
-#endif
+/**
+ * Generic implementation for SkTileGridNextDatumFunctionPtr. user code may instantiate
+ * this template to get a valid SkTileGridNextDatumFunction implementation
+ *
+ * Returns the next element of tileData[i][tileIndices[i]] for all i and advances
+ * tileIndices[] past them. The order in which data are returned by successive
+ * calls to this method must reflect the order in which the were originally
+ * recorded into the tile grid.
+ *
+ * \param tileData array of pointers to arrays of tile data
+ * \param tileIndices per-tile data indices, indices are incremented for tiles that contain
+ * the next datum.
+ * \tparam T a type to which it is safe to cast a datum and that has an operator <
+ * such that 'a < b' is true if 'a' was inserted into the tile grid before 'b'.
+ */
+template <typename T>
+void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkTDArray<int>& tileIndices) {
+ bool haveVal = false;
+ T* minVal;
+ int tileCount = tileIndices.count();
+ // Find the next Datum
+ for (int tile = 0; tile < tileCount; ++tile) {
+ int pos = tileIndices[tile];
+ if (pos != SkTileGrid::kTileFinished) {
+ T* candidate = (T*)(*tileData[tile])[pos];
+ if (!haveVal || (*candidate) < (*minVal)) {
+ minVal = candidate;
+ haveVal = true;
+ }
+ }
+ }
+ // Increment indices past the next datum
+ if (haveVal) {
+ for (int tile = 0; tile < tileCount; ++tile) {
+ int pos = tileIndices[tile];
+ if (pos != SkTileGrid::kTileFinished && (*tileData[tile])[pos] == minVal) {
+ if (++(tileIndices[tile]) >= tileData[tile]->count()) {
+ tileIndices[tile] = SkTileGrid::kTileFinished;
+ }
+ }
+ }
+ return minVal;
+ }
+ return NULL;
+}
+#endif
\ No newline at end of file
diff --git a/src/core/SkTileGridPicture.cpp b/src/core/SkTileGridPicture.cpp
new file mode 100644
index 0000000..212e3b6
--- /dev/null
+++ b/src/core/SkTileGridPicture.cpp
@@ -0,0 +1,24 @@
+/*
+ * 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 "SkTileGridPicture.h"
+
+#include "SkPictureStateTree.h"
+#include "SkTileGrid.h"
+
+
+SkTileGridPicture::SkTileGridPicture(int tileWidth, int tileHeight, int width, int height) {
+ fTileWidth = tileWidth;
+ fTileHeight = tileHeight;
+ fXTileCount = (width + tileWidth - 1) / tileWidth;
+ fYTileCount = (height + tileHeight - 1) / tileHeight;
+}
+
+SkBBoxHierarchy* SkTileGridPicture::createBBoxHierarchy() const {
+ return SkNEW_ARGS(SkTileGrid, (fTileWidth, fTileHeight, fXTileCount, fYTileCount,
+ SkTileGridNextDatum<SkPictureStateTree::Draw>));
+}
diff --git a/tests/TileGridTest.cpp b/tests/TileGridTest.cpp
index e0c855c..d5ca52b 100644
--- a/tests/TileGridTest.cpp
+++ b/tests/TileGridTest.cpp
@@ -8,6 +8,9 @@
#include "Test.h"
#include "SkTileGrid.h"
+#include "SkTileGridPicture.h"
+#include "SkCanvas.h"
+#include "SkDevice.h"
enum Tile {
kTopLeft_Tile = 0x1,
@@ -18,10 +21,26 @@
kAll_Tile = kTopLeft_Tile | kTopRight_Tile | kBottomLeft_Tile | kBottomRight_Tile,
};
+namespace {
+class MockCanvas : public SkCanvas {
+public:
+ MockCanvas(SkDevice* device) : SkCanvas(device)
+ {}
+
+ virtual void drawRect(const SkRect& rect, const SkPaint& paint)
+ {
+ // This capture occurs before quick reject.
+ fRects.push(rect);
+ }
+
+ SkTDArray<SkRect> fRects;
+};
+}
+
class TileGridTest {
public:
static void verifyTileHits(skiatest::Reporter* reporter, SkIRect rect, uint32_t tileMask) {
- SkTileGrid grid(10, 10, 2, 2);
+ SkTileGrid grid(10, 10, 2, 2, NULL);
grid.insert(NULL, rect, false);
REPORTER_ASSERT(reporter, grid.tile(0,0).count() ==
((tileMask & kTopLeft_Tile)? 1 : 0));
@@ -33,6 +52,60 @@
((tileMask & kBottomRight_Tile)? 1 : 0));
}
+ static void TestUnalignedQuery(skiatest::Reporter* reporter) {
+ // Use SkTileGridPicture to generate a SkTileGrid with a helper
+ SkTileGridPicture picture(10, 10, 20, 20);
+ SkRect rect1 = SkRect::MakeXYWH(SkIntToScalar(0), SkIntToScalar(0),
+ SkIntToScalar(8), SkIntToScalar(8));
+ SkRect rect2 = SkRect::MakeXYWH(SkIntToScalar(11), SkIntToScalar(11),
+ SkIntToScalar(1), SkIntToScalar(1));
+ SkCanvas* canvas = picture.beginRecording(20, 20, SkPicture::kOptimizeForClippedPlayback_RecordingFlag);
+ SkPaint paint;
+ canvas->drawRect(rect1, paint);
+ canvas->drawRect(rect2, paint);
+ picture.endRecording();
+
+ SkBitmap store;
+ store.setConfig(SkBitmap::kARGB_8888_Config, 1, 1);
+ store.allocPixels();
+
+ // Test parts of top-left tile
+ {
+ SkDevice device(store);
+ MockCanvas mockCanvas(&device);
+ picture.draw(&mockCanvas);
+ REPORTER_ASSERT(reporter, 1 == mockCanvas.fRects.count());
+ REPORTER_ASSERT(reporter, rect1 == mockCanvas.fRects[0]);
+ }
+ {
+ SkDevice device(store);
+ MockCanvas mockCanvas(&device);
+ mockCanvas.translate(SkFloatToScalar(-7.99f), SkFloatToScalar(-7.99f));
+ picture.draw(&mockCanvas);
+ REPORTER_ASSERT(reporter, 1 == mockCanvas.fRects.count());
+ REPORTER_ASSERT(reporter, rect1 == mockCanvas.fRects[0]);
+ }
+ // Corner overlap
+ {
+ SkDevice device(store);
+ MockCanvas mockCanvas(&device);
+ mockCanvas.translate(SkFloatToScalar(-9.5f), SkFloatToScalar(-9.5f));
+ picture.draw(&mockCanvas);
+ REPORTER_ASSERT(reporter, 2 == mockCanvas.fRects.count());
+ REPORTER_ASSERT(reporter, rect1 == mockCanvas.fRects[0]);
+ REPORTER_ASSERT(reporter, rect2 == mockCanvas.fRects[1]);
+ }
+ // Intersect bottom right tile, but does not overlap rect 2
+ {
+ SkDevice device(store);
+ MockCanvas mockCanvas(&device);
+ mockCanvas.translate(SkFloatToScalar(-16.0f), SkFloatToScalar(-16.0f));
+ picture.draw(&mockCanvas);
+ REPORTER_ASSERT(reporter, 1 == mockCanvas.fRects.count());
+ REPORTER_ASSERT(reporter, rect2 == mockCanvas.fRects[0]);
+ }
+ }
+
static void Test(skiatest::Reporter* reporter) {
// Out of bounds
verifyTileHits(reporter, SkIRect::MakeXYWH(30, 0, 1, 1), 0);
@@ -52,6 +125,8 @@
kBottomLeft_Tile);
verifyTileHits(reporter, SkIRect::MakeXYWH(5, 5, 10, 10), kAll_Tile);
verifyTileHits(reporter, SkIRect::MakeXYWH(-10, -10, 40, 40), kAll_Tile);
+
+ TestUnalignedQuery(reporter);
}
};
diff --git a/tools/PictureRenderer.cpp b/tools/PictureRenderer.cpp
index 1f975cf..034e8fc 100644
--- a/tools/PictureRenderer.cpp
+++ b/tools/PictureRenderer.cpp
@@ -24,7 +24,7 @@
#include "SkStream.h"
#include "SkString.h"
#include "SkTemplates.h"
-#include "SkTileGrid.h"
+#include "SkTileGridPicture.h"
#include "SkTDArray.h"
#include "SkThreadUtils.h"
#include "SkTypes.h"
@@ -624,22 +624,6 @@
}
};
-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:
@@ -647,14 +631,8 @@
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));
- }
+ return SkNEW_ARGS(SkTileGridPicture, (fGridWidth, fGridHeight, fPicture->width(),
+ fPicture->height()));
}
SkASSERT(0); // invalid bbhType
return NULL;