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