diff options
author | mtklein <mtklein@chromium.org> | 2014-08-11 12:05:59 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2014-08-11 12:05:59 -0700 |
commit | a7f7b168ae6c4658efe2a7acd1b22f2dd989bb35 (patch) | |
tree | d729f8c861f690d32b52ec71fc8868bd18ef8383 | |
parent | 0d154eeaebc640b7bd83e0b212fac22587610a4b (diff) |
More SkTileGrid refactoring.
I've rearranged the code a bit more and added more notes.
BUG=skia:
R=robertphillips@google.com, mtklein@google.com
Author: mtklein@chromium.org
Review URL: https://codereview.chromium.org/463593003
-rw-r--r-- | src/core/SkTileGrid.cpp | 147 | ||||
-rw-r--r-- | src/core/SkTileGrid.h | 23 |
2 files changed, 83 insertions, 87 deletions
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp index 2d6f3b1209..21788c1f01 100644 --- a/src/core/SkTileGrid.cpp +++ b/src/core/SkTileGrid.cpp @@ -68,85 +68,94 @@ void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) { fInsertionCount++; } -static void* next_datum(const SkTDArray<void*>** tileData, - SkAutoSTArray<SkTileGrid::kStackAllocationTileCount, int>& tileIndices) { - SkPictureStateTree::Draw* minVal = NULL; - int tileCount = tileIndices.count(); - int minIndex = tileCount; - int maxIndex = 0; - // Find the next Datum; track where it's found so we reduce the size of the second loop. - for (int tile = 0; tile < tileCount; ++tile) { - int pos = tileIndices[tile]; - if (pos != SkTileGrid::kTileFinished) { - SkPictureStateTree::Draw* candidate = (SkPictureStateTree::Draw*)(*tileData[tile])[pos]; - if (NULL == minVal || (*candidate) < (*minVal)) { - minVal = candidate; - minIndex = tile; - maxIndex = tile; - } else if (!((*minVal) < (*candidate))) { - // We don't require operator==; if !(candidate<minVal) && !(minVal<candidate), - // candidate==minVal and we have to add this tile to the range searched. - maxIndex = tile; - } - } - } - // Increment indices past the next datum - if (minVal != NULL) { - for (int tile = minIndex; tile <= maxIndex; ++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; +static int divide_ceil(int x, int y) { + return (x + y - 1) / y; } +// Number of tiles for which data is allocated on the stack in +// SkTileGrid::search. If malloc becomes a bottleneck, we may consider +// increasing this number. Typical large web page, say 2k x 16k, would +// require 512 tiles of size 256 x 256 pixels. +static const int kStackAllocationTileCount = 1024; + void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) const { - SkIRect adjustedQuery = query; + SkIRect adjusted = query; + // The inset is to counteract the outset that was applied in 'insert' // The outset/inset is to optimize for lookups of size // 'tileInterval + 2 * margin' that are aligned with the tile grid. - adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height()); - adjustedQuery.offset(fInfo.fOffset); - adjustedQuery.sort(); // in case the inset inverted the rectangle + adjusted.inset(fInfo.fMargin.width(), fInfo.fMargin.height()); + adjusted.offset(fInfo.fOffset); + adjusted.sort(); // in case the inset inverted the rectangle + // Convert the query rectangle from device coordinates to tile coordinates // by rounding outwards to the nearest tile boundary so that the resulting tile - // region includes the query rectangle. (using truncating division to "floor") - int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width(); - int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) / - fInfo.fTileInterval.width(); - int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height(); - int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) / - fInfo.fTileInterval.height(); - - tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1); - tileEndX = SkPin32(tileEndX, tileStartX+1, fXTileCount); - tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1); - tileEndY = SkPin32(tileEndY, tileStartY+1, fYTileCount); - - int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY); - SkASSERT(queryTileCount); - if (queryTileCount == 1) { - *results = this->tile(tileStartX, tileStartY); - } else { - results->reset(); - SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount); - SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount); - const SkTDArray<void *>** tileRange = const_cast<const SkTDArray<void*>**>(storage.get()); - 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; + // region includes the query rectangle. + int startX = adjusted.left() / fInfo.fTileInterval.width(), + startY = adjusted.top() / fInfo.fTileInterval.height(); + int endX = divide_ceil(adjusted.right(), fInfo.fTileInterval.width()), + endY = divide_ceil(adjusted.bottom(), fInfo.fTileInterval.height()); + + // Logically, we could pin endX to [startX, fXTileCount], but we force it + // up to (startX, fXTileCount] to make sure we hit at least one tile. + // This snaps just-out-of-bounds queries to the neighboring border tile. + // I don't know if this is an important feature outside of unit tests. + startX = SkPin32(startX, 0, fXTileCount - 1); + startY = SkPin32(startY, 0, fYTileCount - 1); + endX = SkPin32(endX, startX + 1, fXTileCount); + endY = SkPin32(endY, startY + 1, fYTileCount); + + const int tilesHit = (endX - startX) * (endY - startY); + SkASSERT(tilesHit > 0); + + if (tilesHit == 1) { + // A performance shortcut. The merging code below would work fine here too. + *results = this->tile(startX, startY); + return; + } + + // We've got to merge the data in many tiles into a single sorted and deduplicated stream. + // Each tile itself is already sorted (TODO: assert this while building) so we just need to do + // a simple k-way merge. + + // Gather pointers to the starts and ends of the tiles to merge. + SkAutoSTArray<kStackAllocationTileCount, void**> tiles(tilesHit), ends(tilesHit); + int i = 0; + for (int x = startX; x < endX; x++) { + for (int y = startY; y < endY; y++) { + tiles[i] = fTileData[y * fXTileCount + x].begin(); + ends[i] = fTileData[y * fXTileCount + x].end(); + i++; + } + } + + // Merge tiles into results until they're fully consumed. + results->reset(); + while (true) { + // The tiles themselves are already sorted, so the smallest datum is the front of some tile. + // It may be at the front of several, even all, tiles. + SkPictureStateTree::Draw* smallest = NULL; + for (int i = 0; i < tiles.count(); i++) { + if (tiles[i] < ends[i]) { + SkPictureStateTree::Draw* candidate = + static_cast<SkPictureStateTree::Draw*>(*tiles[i]); + if (NULL == smallest || (*candidate) < (*smallest)) { + smallest = candidate; + } } } - while(void* nextElement = next_datum(tileRange, curPositions)) { - results->push(nextElement); + + // If we didn't find a smallest datum, there's nothing left to merge. + if (NULL == smallest) { + return; + } + + // We did find a smallest datum. Output it, and step forward in every tile that contains it. + results->push(smallest); + for (int i = 0; i < tiles.count(); i++) { + if (tiles[i] < ends[i] && *tiles[i] == smallest) { + tiles[i]++; + } } } } diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h index 163efa5571..c02235a123 100644 --- a/src/core/SkTileGrid.h +++ b/src/core/SkTileGrid.h @@ -25,31 +25,23 @@ */ class SkTileGrid : public SkBBoxHierarchy { public: - enum { - // Number of tiles for which data is allocated on the stack in - // SkTileGrid::search. If malloc becomes a bottleneck, we may consider - // increasing this number. Typical large web page, say 2k x 16k, would - // require 512 tiles of size 256 x 256 pixels. - kStackAllocationTileCount = 1024 - }; - SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info); 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 + * @param data The data pointer, may _NOT_ be NULL. + * @param bounds The bounding box, should not be empty. + * @param defer Ignored; SkTileGrid 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 + * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'. + * This will be fastest if the query is an exact match to a single grid tile. */ virtual void search(const SkIRect& query, SkTDArray<void*>* results) const SK_OVERRIDE; @@ -64,11 +56,6 @@ public: virtual void rewindInserts() SK_OVERRIDE; - // Used by search() and in SkTileGridHelper implementations - enum { - kTileFinished = -1, - }; - int tileCount(int x, int y); // For testing only. private: |