Home | History | Annotate | Download | only in core 
      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 }
    133