Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(288)

Side by Side Diff: src/core/SkTileGrid.cpp

Issue 466503002: SkTileGrid: store insertion order, return results sorted by that. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: comments Created 6 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/core/SkTileGrid.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1
2 /* 1 /*
3 * Copyright 2012 Google Inc. 2 * Copyright 2012 Google Inc.
4 * 3 *
5 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file. 5 * found in the LICENSE file.
7 */ 6 */
8 7
9 #include "SkTileGrid.h" 8 #include "SkTileGrid.h"
10 #include "SkPictureStateTree.h"
11 9
12 SkTileGrid::SkTileGrid(int xTileCount, int yTileCount, const SkTileGridFactory:: TileGridInfo& info) { 10 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid Info& info)
13 fXTileCount = xTileCount; 11 : fXTiles(xTiles)
14 fYTileCount = yTileCount; 12 , fYTiles(yTiles)
15 fInfo = info; 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 16 // Margin is offset by 1 as a provision for AA and
17 // to cancel-out the outset applied by getClipDeviceBounds. 17 // to cancel-out the outset applied by getClipDeviceBounds.
18 fInfo.fMargin.fHeight++; 18 fInfo.fMargin.fHeight++;
19 fInfo.fMargin.fWidth++; 19 fInfo.fMargin.fWidth++;
20 fTileCount = fXTileCount * fYTileCount;
21 fInsertionCount = 0;
22 fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCo unt,
23 fInfo.fTileInterval.height() * fYTileCount);
24 fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
25 } 20 }
26 21
27 SkTileGrid::~SkTileGrid() { 22 SkTileGrid::~SkTileGrid() {
28 SkDELETE_ARRAY(fTileData); 23 SkDELETE_ARRAY(fTiles);
29 }
30
31 int SkTileGrid::tileCount(int x, int y) {
32 return this->tile(x, y).count();
33 }
34
35 const SkTDArray<void *>& SkTileGrid::tile(int x, int y) const {
36 return fTileData[y * fXTileCount + x];
37 }
38
39 SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
40 return fTileData[y * fXTileCount + x];
41 } 24 }
42 25
43 void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) { 26 void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
44 SkASSERT(!bounds.isEmpty()); 27 SkASSERT(!bounds.isEmpty());
45 SkIRect dilatedBounds = bounds; 28 SkIRect dilatedBounds = bounds;
46 dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height()); 29
47 dilatedBounds.offset(fInfo.fOffset); 30 // Dilating the largest SkIRect will overflow. Other nearly-largest rects m ay overflow too,
48 if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) { 31 // but we don't make active use of them like we do the largest.
32 if (!bounds.isLargest()) {
33 dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
34 dilatedBounds.offset(fInfo.fOffset);
35 }
36
37 const SkIRect gridBounds =
38 { 0, 0, fInfo.fTileInterval.width() * fXTiles, fInfo.fTileInterval.heigh t() * fYTiles };
39 if (!SkIRect::Intersects(dilatedBounds, gridBounds)) {
49 return; 40 return;
50 } 41 }
51 42
52 // Note: SkIRects are non-inclusive of the right() column and bottom() row, 43 // Note: SkIRects are non-inclusive of the right() column and bottom() row,
53 // hence the "-1"s in the computations of maxTileX and maxTileY. 44 // hence the "-1"s in the computations of maxX and maxY.
54 int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.wi dth(), 45 int minX = SkMax32(0, SkMin32(dilatedBounds.left() / fInfo.fTileInterval.wid th(), fXTiles - 1));
55 fXTileCount - 1), 0); 46 int minY = SkMax32(0, SkMin32(dilatedBounds.top() / fInfo.fTileInterval.heig ht(), fYTiles - 1));
56 int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInte rval.width(), 47 int maxX = SkMax32(0, SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInte rval.width(),
57 fXTileCount - 1), 0); 48 fXTiles - 1));
58 int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.hei ght(), 49 int maxY = SkMax32(0, SkMin32((dilatedBounds.bottom() - 1) / fInfo.fTileInte rval.height(),
59 fYTileCount -1), 0); 50 fYTiles - 1));
60 int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInte rval.height(),
61 fYTileCount -1), 0);
62 51
63 for (int x = minTileX; x <= maxTileX; x++) { 52 Entry entry = { fCount++, data };
64 for (int y = minTileY; y <= maxTileY; y++) { 53 for (int x = minX; x <= maxX; x++) {
65 this->tile(x, y).push(data); 54 for (int y = minY; y <= maxY; y++) {
55 fTiles[y * fXTiles + x].push(entry);
66 } 56 }
67 } 57 }
68 fInsertionCount++;
69 } 58 }
70 59
71 static int divide_ceil(int x, int y) { 60 static int divide_ceil(int x, int y) {
72 return (x + y - 1) / y; 61 return (x + y - 1) / y;
73 } 62 }
74 63
75 // Number of tiles for which data is allocated on the stack in 64 // Number of tiles for which data is allocated on the stack in
76 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider 65 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider
77 // increasing this number. Typical large web page, say 2k x 16k, would 66 // increasing this number. Typical large web page, say 2k x 16k, would
78 // require 512 tiles of size 256 x 256 pixels. 67 // require 512 tiles of size 256 x 256 pixels.
(...skipping 10 matching lines...) Expand all
89 adjusted.sort(); // in case the inset inverted the rectangle 78 adjusted.sort(); // in case the inset inverted the rectangle
90 79
91 // Convert the query rectangle from device coordinates to tile coordinates 80 // Convert the query rectangle from device coordinates to tile coordinates
92 // by rounding outwards to the nearest tile boundary so that the resulting t ile 81 // by rounding outwards to the nearest tile boundary so that the resulting t ile
93 // region includes the query rectangle. 82 // region includes the query rectangle.
94 int startX = adjusted.left() / fInfo.fTileInterval.width(), 83 int startX = adjusted.left() / fInfo.fTileInterval.width(),
95 startY = adjusted.top() / fInfo.fTileInterval.height(); 84 startY = adjusted.top() / fInfo.fTileInterval.height();
96 int endX = divide_ceil(adjusted.right(), fInfo.fTileInterval.width()), 85 int endX = divide_ceil(adjusted.right(), fInfo.fTileInterval.width()),
97 endY = divide_ceil(adjusted.bottom(), fInfo.fTileInterval.height()); 86 endY = divide_ceil(adjusted.bottom(), fInfo.fTileInterval.height());
98 87
99 // Logically, we could pin endX to [startX, fXTileCount], but we force it 88 // Logically, we could pin endX to [startX, fXTiles], but we force it
100 // up to (startX, fXTileCount] to make sure we hit at least one tile. 89 // up to (startX, fXTiles] to make sure we hit at least one tile.
101 // This snaps just-out-of-bounds queries to the neighboring border tile. 90 // This snaps just-out-of-bounds queries to the neighboring border tile.
102 // I don't know if this is an important feature outside of unit tests. 91 // I don't know if this is an important feature outside of unit tests.
103 startX = SkPin32(startX, 0, fXTileCount - 1); 92 startX = SkPin32(startX, 0, fXTiles - 1);
104 startY = SkPin32(startY, 0, fYTileCount - 1); 93 startY = SkPin32(startY, 0, fYTiles - 1);
105 endX = SkPin32(endX, startX + 1, fXTileCount); 94 endX = SkPin32(endX, startX + 1, fXTiles);
106 endY = SkPin32(endY, startY + 1, fYTileCount); 95 endY = SkPin32(endY, startY + 1, fYTiles);
107 96
108 const int tilesHit = (endX - startX) * (endY - startY); 97 const int tilesHit = (endX - startX) * (endY - startY);
109 SkASSERT(tilesHit > 0); 98 SkASSERT(tilesHit > 0);
110 99
111 if (tilesHit == 1) { 100 if (tilesHit == 1) {
112 // A performance shortcut. The merging code below would work fine here too. 101 // A performance shortcut. The merging code below would work fine here too.
113 *results = this->tile(startX, startY); 102 const SkTDArray<Entry>& tile = fTiles[startY * fXTiles + startX];
103 results->setCount(tile.count());
104 for (int i = 0; i < tile.count(); i++) {
105 (*results)[i] = tile[i].data;
106 }
114 return; 107 return;
115 } 108 }
116 109
117 // We've got to merge the data in many tiles into a single sorted and dedupl icated stream. 110 // We've got to merge the data in many tiles into a single sorted and dedupl icated stream.
118 // Each tile itself is already sorted (TODO: assert this while building) so we just need to do 111 // We do a simple k-way merge based on the order the data was inserted.
119 // a simple k-way merge.
120 112
121 // Gather pointers to the starts and ends of the tiles to merge. 113 // Gather pointers to the starts and ends of the tiles to merge.
122 SkAutoSTArray<kStackAllocationTileCount, void**> tiles(tilesHit), ends(tiles Hit); 114 SkAutoSTArray<kStackAllocationTileCount, const Entry*> starts(tilesHit), end s(tilesHit);
123 int i = 0; 115 int i = 0;
124 for (int x = startX; x < endX; x++) { 116 for (int x = startX; x < endX; x++) {
125 for (int y = startY; y < endY; y++) { 117 for (int y = startY; y < endY; y++) {
126 tiles[i] = fTileData[y * fXTileCount + x].begin(); 118 starts[i] = fTiles[y * fXTiles + x].begin();
127 ends[i] = fTileData[y * fXTileCount + x].end(); 119 ends[i] = fTiles[y * fXTiles + x].end();
128 i++; 120 i++;
129 } 121 }
130 } 122 }
131 123
132 // Merge tiles into results until they're fully consumed. 124 // Merge tiles into results until they're fully consumed.
133 results->reset(); 125 results->reset();
134 while (true) { 126 while (true) {
135 // The tiles themselves are already sorted, so the smallest datum is the front of some tile. 127 // The tiles themselves are already ordered, so the earliest is at the f ront of some tile.
136 // It may be at the front of several, even all, tiles. 128 // It may be at the front of several, even all, tiles.
137 SkPictureStateTree::Draw* smallest = NULL; 129 const Entry* earliest = NULL;
138 for (int i = 0; i < tiles.count(); i++) { 130 for (int i = 0; i < starts.count(); i++) {
139 if (tiles[i] < ends[i]) { 131 if (starts[i] < ends[i]) {
140 SkPictureStateTree::Draw* candidate = 132 if (NULL == earliest || starts[i]->order < earliest->order) {
141 static_cast<SkPictureStateTree::Draw*>(*tiles[i]); 133 earliest = starts[i];
142 if (NULL == smallest || (*candidate) < (*smallest)) {
143 smallest = candidate;
144 } 134 }
145 } 135 }
146 } 136 }
147 137
148 // If we didn't find a smallest datum, there's nothing left to merge. 138 // If we didn't find an earliest entry, there isn't anything left to mer ge.
149 if (NULL == smallest) { 139 if (NULL == earliest) {
150 return; 140 return;
151 } 141 }
152 142
153 // We did find a smallest datum. Output it, and step forward in every ti le that contains it. 143 // We did find an earliest entry. Output it, and step forward every tile that contains it.
154 results->push(smallest); 144 results->push(earliest->data);
155 for (int i = 0; i < tiles.count(); i++) { 145 for (int i = 0; i < starts.count(); i++) {
156 if (tiles[i] < ends[i] && *tiles[i] == smallest) { 146 if (starts[i] < ends[i] && starts[i]->order == earliest->order) {
157 tiles[i]++; 147 starts[i]++;
158 } 148 }
159 } 149 }
160 } 150 }
161 } 151 }
162 152
163 void SkTileGrid::clear() { 153 void SkTileGrid::clear() {
164 for (int i = 0; i < fTileCount; i++) { 154 for (int i = 0; i < fXTiles * fYTiles; i++) {
165 fTileData[i].reset(); 155 fTiles[i].reset();
166 } 156 }
167 } 157 }
168 158
169 int SkTileGrid::getCount() const {
170 return fInsertionCount;
171 }
172
173 void SkTileGrid::rewindInserts() { 159 void SkTileGrid::rewindInserts() {
174 SkASSERT(fClient); 160 SkASSERT(fClient);
175 for (int i = 0; i < fTileCount; ++i) { 161 for (int i = 0; i < fXTiles * fYTiles; i++) {
176 while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top ())) { 162 while (!fTiles[i].isEmpty() && fClient->shouldRewind(fTiles[i].top().dat a)) {
177 fTileData[i].pop(); 163 fTiles[i].pop();
178 } 164 }
179 } 165 }
180 } 166 }
OLDNEW
« no previous file with comments | « src/core/SkTileGrid.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698