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