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