src/third_party/skia/src/core/SkTileGrid.cpp

   1
   2 /*
   3  * Copyright 2012 Google Inc.
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9 #include "SkTileGrid.h"
  10
  11 SkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory::TileGridInfo& info,
  12                        SkTileGridNextDatumFunctionPtr nextDatumFunction) {
  13     fXTileCount = xTileCount;
  14     fYTileCount = yTileCount;
  15     fInfo = info;
  16     // Margin is offset by 1 as a provision for AA and
  17     // to cancel-out the outset applied by getClipDeviceBounds.
  18     fInfo.fMargin.fHeight++;
  19     fInfo.fMargin.fWidth++;
  20     fTileCount = fXTileCount * fYTileCount;
  21     fInsertionCount = 0;
  22     fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCount,
  23         fInfo.fTileInterval.height() * fYTileCount);
  24     fNextDatumFunction = nextDatumFunction;
  25     fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
  26 }
  27
  28 SkTileGrid::~SkTileGrid() {
  29     SkDELETE_ARRAY(fTileData);
  30 }
  31
  32 int SkTileGrid::tileCount(int x, int y) {
  33     return this->tile(x, y).count();
  34 }
  35
  36 SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
  37     return fTileData[y * fXTileCount + x];
  38 }
  39
  40 void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
  41     SkASSERT(!bounds.isEmpty());
  42     SkIRect dilatedBounds = bounds;
  43     dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
  44     dilatedBounds.offset(fInfo.fOffset);
  45     if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) {
  46         return;
  47     }
  48
  49     // Note: SkIRects are non-inclusive of the right() column and bottom() row,
  50     // hence the "-1"s in the computations of maxTileX and maxTileY.
  51     int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(),
  52         fXTileCount - 1), 0);
  53     int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(),
  54         fXTileCount - 1), 0);
  55     int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(),
  56         fYTileCount -1), 0);
  57     int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(),
  58         fYTileCount -1), 0);
  59
  60     for (int x = minTileX; x <= maxTileX; x++) {
  61         for (int y = minTileY; y <= maxTileY; y++) {
  62             this->tile(x, y).push(data);
  63         }
  64     }
  65     fInsertionCount++;
  66 }
  67
  68 void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) {
  69     SkIRect adjustedQuery = query;
  70     // The inset is to counteract the outset that was applied in 'insert'
  71     // The outset/inset is to optimize for lookups of size
  72     // 'tileInterval + 2 * margin' that are aligned with the tile grid.
  73     adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height());
  74     adjustedQuery.offset(fInfo.fOffset);
  75     adjustedQuery.sort();  // in case the inset inverted the rectangle
  76     // Convert the query rectangle from device coordinates to tile coordinates
  77     // by rounding outwards to the nearest tile boundary so that the resulting tile
  78     // region includes the query rectangle. (using truncating division to "floor")
  79     int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width();
  80     int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) /
  81         fInfo.fTileInterval.width();
  82     int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height();
  83     int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) /
  84         fInfo.fTileInterval.height();
  85
  86     tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1);
  87     tileEndX = SkPin32(tileEndX, tileStartX+1, fXTileCount);
  88     tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1);
  89     tileEndY = SkPin32(tileEndY, tileStartY+1, fYTileCount);
  90
  91     int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
  92     SkASSERT(queryTileCount);
  93     if (queryTileCount == 1) {
  94         *results = this->tile(tileStartX, tileStartY);
  95     } else {
  96         results->reset();
  97         SkAutoSTArray<kStackAllocationTileCount, int> curPositions(queryTileCount);
  98         SkAutoSTArray<kStackAllocationTileCount, SkTDArray<void *>*> storage(queryTileCount);
  99         SkTDArray<void *>** tileRange = storage.get();
 100         int tile = 0;
 101         for (int x = tileStartX; x < tileEndX; ++x) {
 102             for (int y = tileStartY; y < tileEndY; ++y) {
 103                 tileRange[tile] = &this->tile(x, y);
 104                 curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
 105                 ++tile;
 106             }
 107         }
 108         void *nextElement;
 109         while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
 110             results->push(nextElement);
 111         }
 112     }
 113 }
 114
 115 void SkTileGrid::clear() {
 116     for (int i = 0; i < fTileCount; i++) {
 117         fTileData[i].reset();
 118     }
 119 }
 120
 121 int SkTileGrid::getCount() const {
 122     return fInsertionCount;
 123 }
 124
 125 void SkTileGrid::rewindInserts() {
 126     SkASSERT(fClient);
 127     for (int i = 0; i < fTileCount; ++i) {
 128         while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {
 129             fTileData[i].pop();
 130         }
 131     }
 132 }