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

   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 }