OLD | NEW |
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 Loading... |
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 } |
OLD | NEW |