Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2012 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #include "SkTileGrid.h"
      9 
     10 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info)
     11     : fXTiles(xTiles)
     12     , fYTiles(yTiles)
     13     , fInfo(info)
     14     , fCount(0)
     15     , fTiles(SkNEW_ARRAY(SkTDArray<Entry>, xTiles * yTiles)) {
     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 }
     21 
     22 SkTileGrid::~SkTileGrid() {
     23     SkDELETE_ARRAY(fTiles);
     24 }
     25 
     26 void SkTileGrid::insert(void* data, const SkRect& fbounds, bool) {
     27     SkASSERT(!fbounds.isEmpty());
     28     SkIRect dilatedBounds;
     29     if (fbounds.isLargest()) {
     30         // Dilating the largest SkIRect will overflow.  Other nearly-largest rects may overflow too,
     31         // but we don't make active use of them like we do the largest.
     32         dilatedBounds.setLargest();
     33     } else {
     34         fbounds.roundOut(&dilatedBounds);
     35         dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
     36         dilatedBounds.offset(fInfo.fOffset);
     37     }
     38 
     39     const SkIRect gridBounds =
     40         { 0, 0, fInfo.fTileInterval.width() * fXTiles, fInfo.fTileInterval.height() * fYTiles };
     41     if (!SkIRect::Intersects(dilatedBounds, gridBounds)) {
     42         return;
     43     }
     44 
     45     // Note: SkIRects are non-inclusive of the right() column and bottom() row,
     46     // hence the "-1"s in the computations of maxX and maxY.
     47     int minX = SkMax32(0, SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(), fXTiles - 1));
     48     int minY = SkMax32(0, SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(), fYTiles - 1));
     49     int maxX = SkMax32(0, SkMin32((dilatedBounds.right()  - 1) / fInfo.fTileInterval.width(),
     50                                   fXTiles - 1));
     51     int maxY = SkMax32(0, SkMin32((dilatedBounds.bottom() - 1) / fInfo.fTileInterval.height(),
     52                                   fYTiles - 1));
     53 
     54     Entry entry = { fCount++, data };
     55     for (int y = minY; y <= maxY; y++) {
     56         for (int x = minX; x <= maxX; x++) {
     57             fTiles[y * fXTiles + x].push(entry);
     58         }
     59     }
     60 }
     61 
     62 static int divide_ceil(int x, int y) {
     63     return (x + y - 1) / y;
     64 }
     65 
     66 // Number of tiles for which data is allocated on the stack in
     67 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider
     68 // increasing this number. Typical large web page, say 2k x 16k, would
     69 // require 512 tiles of size 256 x 256 pixels.
     70 static const int kStackAllocationTileCount = 1024;
     71 
     72 void SkTileGrid::search(const SkRect& query, SkTDArray<void*>* results) const {
     73     SkIRect adjusted;
     74     query.roundOut(&adjusted);
     75 
     76     // The inset is to counteract the outset that was applied in 'insert'
     77     // The outset/inset is to optimize for lookups of size
     78     // 'tileInterval + 2 * margin' that are aligned with the tile grid.
     79     adjusted.inset(fInfo.fMargin.width(), fInfo.fMargin.height());
     80     adjusted.offset(fInfo.fOffset);
     81     adjusted.sort();  // in case the inset inverted the rectangle
     82 
     83     // Convert the query rectangle from device coordinates to tile coordinates
     84     // by rounding outwards to the nearest tile boundary so that the resulting tile
     85     // region includes the query rectangle.
     86     int startX = adjusted.left() / fInfo.fTileInterval.width(),
     87         startY = adjusted.top()  / fInfo.fTileInterval.height();
     88     int endX = divide_ceil(adjusted.right(),  fInfo.fTileInterval.width()),
     89         endY = divide_ceil(adjusted.bottom(), fInfo.fTileInterval.height());
     90 
     91     // Logically, we could pin endX to [startX, fXTiles], but we force it
     92     // up to (startX, fXTiles] to make sure we hit at least one tile.
     93     // This snaps just-out-of-bounds queries to the neighboring border tile.
     94     // I don't know if this is an important feature outside of unit tests.
     95     startX = SkPin32(startX, 0, fXTiles - 1);
     96     startY = SkPin32(startY, 0, fYTiles - 1);
     97     endX   = SkPin32(endX, startX + 1, fXTiles);
     98     endY   = SkPin32(endY, startY + 1, fYTiles);
     99 
    100     const int tilesHit = (endX - startX) * (endY - startY);
    101     SkASSERT(tilesHit > 0);
    102 
    103     if (tilesHit == 1) {
    104         // A performance shortcut.  The merging code below would work fine here too.
    105         const SkTDArray<Entry>& tile = fTiles[startY * fXTiles + startX];
    106         results->setCount(tile.count());
    107         for (int i = 0; i < tile.count(); i++) {
    108             (*results)[i] = tile[i].data;
    109         }
    110         return;
    111     }
    112 
    113     // We've got to merge the data in many tiles into a single sorted and deduplicated stream.
    114     // We do a simple k-way merge based on the order the data was inserted.
    115 
    116     // Gather pointers to the starts and ends of the tiles to merge.
    117     SkAutoSTArray<kStackAllocationTileCount, const Entry*> starts(tilesHit), ends(tilesHit);
    118     int i = 0;
    119     for (int x = startX; x < endX; x++) {
    120         for (int y = startY; y < endY; y++) {
    121             starts[i] = fTiles[y * fXTiles + x].begin();
    122             ends[i]  = fTiles[y * fXTiles + x].end();
    123             i++;
    124         }
    125     }
    126 
    127     // Merge tiles into results until they're fully consumed.
    128     results->reset();
    129     while (true) {
    130         // The tiles themselves are already ordered, so the earliest is at the front of some tile.
    131         // It may be at the front of several, even all, tiles.
    132         const Entry* earliest = NULL;
    133         for (int i = 0; i < starts.count(); i++) {
    134             if (starts[i] < ends[i]) {
    135                 if (NULL == earliest || starts[i]->order < earliest->order) {
    136                     earliest = starts[i];
    137                 }
    138             }
    139         }
    140 
    141         // If we didn't find an earliest entry, there isn't anything left to merge.
    142         if (NULL == earliest) {
    143             return;
    144         }
    145 
    146         // We did find an earliest entry. Output it, and step forward every tile that contains it.
    147         results->push(earliest->data);
    148         for (int i = 0; i < starts.count(); i++) {
    149             if (starts[i] < ends[i] && starts[i]->order == earliest->order) {
    150                 starts[i]++;
    151             }
    152         }
    153     }
    154 }
    155 
    156 void SkTileGrid::clear() {
    157     for (int i = 0; i < fXTiles * fYTiles; i++) {
    158         fTiles[i].reset();
    159     }
    160 }
    161 
    162 void SkTileGrid::rewindInserts() {
    163     SkASSERT(fClient);
    164     for (int i = 0; i < fXTiles * fYTiles; i++) {
    165         while (!fTiles[i].isEmpty() && fClient->shouldRewind(fTiles[i].top().data)) {
    166             fTiles[i].pop();
    167         }
    168     }
    169 }
    170