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
|
/*
* 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 xTileCount, int yTileCount, const SkTileGridPicture::TileGridInfo& info,
SkTileGridNextDatumFunctionPtr nextDatumFunction)
{
fXTileCount = xTileCount;
fYTileCount = yTileCount;
fInfo = info;
// 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++;
fTileCount = fXTileCount * fYTileCount;
fInsertionCount = 0;
fGridBounds = SkIRect::MakeXYWH(0, 0, fInfo.fTileInterval.width() * fXTileCount,
fInfo.fTileInterval.height() * fYTileCount);
fNextDatumFunction = nextDatumFunction;
fTileData = SkNEW_ARRAY(SkTDArray<void *>, fTileCount);
}
SkTileGrid::~SkTileGrid() {
SkDELETE_ARRAY(fTileData);
}
SkTDArray<void *>& SkTileGrid::tile(int x, int y) {
return fTileData[y * fXTileCount + x];
}
void SkTileGrid::insert(void* data, const SkIRect& bounds, bool) {
SkASSERT(!bounds.isEmpty());
SkIRect dilatedBounds = bounds;
dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height());
dilatedBounds.offset(fInfo.fOffset);
if (!SkIRect::Intersects(dilatedBounds, fGridBounds)) {
return;
}
// Note: SkIRects are non-inclusive of the right() column and bottom() row,
// hence the "-1"s in the computations of maxTileX and maxTileY.
int minTileX = SkMax32(SkMin32(dilatedBounds.left() / fInfo.fTileInterval.width(),
fXTileCount - 1), 0);
int maxTileX = SkMax32(SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInterval.width(),
fXTileCount - 1), 0);
int minTileY = SkMax32(SkMin32(dilatedBounds.top() / fInfo.fTileInterval.height(),
fYTileCount -1), 0);
int maxTileY = SkMax32(SkMin32((dilatedBounds.bottom() -1) / fInfo.fTileInterval.height(),
fYTileCount -1), 0);
for (int x = minTileX; x <= maxTileX; x++) {
for (int y = minTileY; y <= maxTileY; y++) {
this->tile(x, y).push(data);
}
}
fInsertionCount++;
}
void SkTileGrid::search(const SkIRect& query, SkTDArray<void*>* results) {
SkIRect adjustedQuery = 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.
adjustedQuery.inset(fInfo.fMargin.width(), fInfo.fMargin.height());
adjustedQuery.offset(fInfo.fOffset);
adjustedQuery.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. (using truncating division to "floor")
int tileStartX = adjustedQuery.left() / fInfo.fTileInterval.width();
int tileEndX = (adjustedQuery.right() + fInfo.fTileInterval.width() - 1) /
fInfo.fTileInterval.width();
int tileStartY = adjustedQuery.top() / fInfo.fTileInterval.height();
int tileEndY = (adjustedQuery.bottom() + fInfo.fTileInterval.height() - 1) /
fInfo.fTileInterval.height();
tileStartX = SkPin32(tileStartX, 0, fXTileCount - 1);
tileEndX = SkPin32(tileEndX, 1, fXTileCount);
tileStartY = SkPin32(tileStartY, 0, fYTileCount - 1);
tileEndY = SkPin32(tileEndY, 1, fYTileCount);
int queryTileCount = (tileEndX - tileStartX) * (tileEndY - tileStartY);
SkASSERT(queryTileCount);
if (queryTileCount == 1) {
*results = this->tile(tileStartX, tileStartY);
} else {
results->reset();
SkTDArray<int> curPositions;
curPositions.setCount(queryTileCount);
// Note: Reserving space for 1024 tile pointers on the stack. If the
// malloc becomes a bottleneck, we may consider increasing that number.
// Typical large web page, say 2k x 16k, would require 512 tiles of
// size 256 x 256 pixels.
SkAutoSTArray<1024, SkTDArray<void *>*> storage(queryTileCount);
SkTDArray<void *>** tileRange = storage.get();
int tile = 0;
for (int x = tileStartX; x < tileEndX; ++x) {
for (int y = tileStartY; y < tileEndY; ++y) {
tileRange[tile] = &this->tile(x, y);
curPositions[tile] = tileRange[tile]->count() ? 0 : kTileFinished;
++tile;
}
}
void *nextElement;
while(NULL != (nextElement = fNextDatumFunction(tileRange, curPositions))) {
results->push(nextElement);
}
}
}
void SkTileGrid::clear() {
for (int i = 0; i < fTileCount; i++) {
fTileData[i].reset();
}
}
int SkTileGrid::getCount() const {
return fInsertionCount;
}
void SkTileGrid::rewindInserts() {
SkASSERT(fClient);
for (int i = 0; i < fTileCount; ++i) {
while (!fTileData[i].isEmpty() && fClient->shouldRewind(fTileData[i].top())) {
fTileData[i].pop();
}
}
}
|
