OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * 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 |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "SkTileGrid.h" | 8 #include "SkTileGrid.h" |
9 | 9 |
10 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid
Info& info) | 10 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid
Info& info) |
11 : fXTiles(xTiles) | 11 : fXTiles(xTiles) |
12 , fYTiles(yTiles) | 12 , fYTiles(yTiles) |
13 , fInfo(info) | 13 , fInvWidth( SkScalarInvert(info.fTileInterval.width())) |
14 , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) { | 14 , fInvHeight(SkScalarInvert(info.fTileInterval.height())) |
15 // Margin is offset by 1 as a provision for AA and | 15 , fMarginWidth (info.fMargin.fWidth +1) // Margin is offset by 1 as a provi
sion for AA and |
16 // to cancel-out the outset applied by getClipDeviceBounds. | 16 , fMarginHeight(info.fMargin.fHeight+1) // to cancel the outset applied by
getClipDeviceBounds. |
17 fInfo.fMargin.fHeight++; | 17 , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY)) |
18 fInfo.fMargin.fWidth++; | 18 , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(), |
19 } | 19 yTiles * info.fTileInterval.height())) |
| 20 , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {} |
20 | 21 |
21 SkTileGrid::~SkTileGrid() { | 22 SkTileGrid::~SkTileGrid() { |
22 SkDELETE_ARRAY(fTiles); | 23 SkDELETE_ARRAY(fTiles); |
23 } | 24 } |
24 | 25 |
25 void SkTileGrid::insert(unsigned opIndex, const SkRect& fbounds, bool) { | 26 // Adjustments to user-provided bounds common to both insert() and search(). |
26 SkASSERT(!fbounds.isEmpty()); | 27 // Call this after making insert- or search- specific adjustments. |
| 28 void SkTileGrid::commonAdjust(SkRect* rect) const { |
| 29 // Apply our offset. |
| 30 rect->offset(fOffset); |
27 | 31 |
28 SkIRect dilatedBounds; | 32 // Scrunch the bounds in just a little to make the right and bottom edges |
29 fbounds.roundOut(&dilatedBounds); | 33 // exclusive. We want bounds of exactly one tile to hit exactly one tile. |
30 dilatedBounds.outset(fInfo.fMargin.width(), fInfo.fMargin.height()); | 34 rect->fRight -= SK_ScalarNearlyZero; |
31 dilatedBounds.offset(fInfo.fOffset); | 35 rect->fBottom -= SK_ScalarNearlyZero; |
| 36 } |
32 | 37 |
33 const SkIRect gridBounds = | 38 // Convert user-space bounds to grid tiles they cover (LT inclusive, RB exclusiv
e). |
34 { 0, 0, fInfo.fTileInterval.width() * fXTiles, fInfo.fTileInterval.heigh
t() * fYTiles }; | 39 void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const { |
35 if (!SkIRect::Intersects(dilatedBounds, gridBounds)) { | 40 grid->fLeft = SkPin32(user.left() * fInvWidth , 0, fXTiles - 1); |
| 41 grid->fTop = SkPin32(user.top() * fInvHeight, 0, fYTiles - 1); |
| 42 grid->fRight = SkPin32(user.right() * fInvWidth , 0, fXTiles - 1) + 1; |
| 43 grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1) + 1; |
| 44 } |
| 45 |
| 46 void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) { |
| 47 SkRect bounds = originalBounds; |
| 48 bounds.outset(fMarginWidth, fMarginHeight); |
| 49 this->commonAdjust(&bounds); |
| 50 |
| 51 // TODO(mtklein): can we assert this instead to save an intersection in Rele
ase mode, |
| 52 // or just allow out-of-bound insertions to insert anyway (clamped to neares
t tile)? |
| 53 if (!SkRect::Intersects(bounds, fGridBounds)) { |
36 return; | 54 return; |
37 } | 55 } |
38 | 56 |
39 // Note: SkIRects are non-inclusive of the right() column and bottom() row, | 57 SkIRect grid; |
40 // hence the "-1"s in the computations of maxX and maxY. | 58 this->userToGrid(bounds, &grid); |
41 int minX = SkMax32(0, SkMin32(dilatedBounds.left() / fInfo.fTileInterval.wid
th(), fXTiles - 1)); | |
42 int minY = SkMax32(0, SkMin32(dilatedBounds.top() / fInfo.fTileInterval.heig
ht(), fYTiles - 1)); | |
43 int maxX = SkMax32(0, SkMin32((dilatedBounds.right() - 1) / fInfo.fTileInte
rval.width(), | |
44 fXTiles - 1)); | |
45 int maxY = SkMax32(0, SkMin32((dilatedBounds.bottom() - 1) / fInfo.fTileInte
rval.height(), | |
46 fYTiles - 1)); | |
47 | 59 |
48 for (int y = minY; y <= maxY; y++) { | 60 for (int y = grid.fTop; y < grid.fBottom; y++) { |
49 for (int x = minX; x <= maxX; x++) { | 61 for (int x = grid.fLeft; x < grid.fRight; x++) { |
50 fTiles[y * fXTiles + x].push(opIndex); | 62 fTiles[y * fXTiles + x].push(opIndex); |
51 } | 63 } |
52 } | 64 } |
53 } | 65 } |
54 | 66 |
55 static int divide_ceil(int x, int y) { | |
56 return (x + y - 1) / y; | |
57 } | |
58 | |
59 // Number of tiles for which data is allocated on the stack in | 67 // Number of tiles for which data is allocated on the stack in |
60 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider | 68 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider |
61 // increasing this number. Typical large web page, say 2k x 16k, would | 69 // increasing this number. Typical large web page, say 2k x 16k, would |
62 // require 512 tiles of size 256 x 256 pixels. | 70 // require 512 tiles of size 256 x 256 pixels. |
63 static const int kStackAllocationTileCount = 1024; | 71 static const int kStackAllocationTileCount = 1024; |
64 | 72 |
65 void SkTileGrid::search(const SkRect& query, SkTDArray<unsigned>* results) const
{ | 73 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { |
66 SkIRect adjusted; | 74 // The inset counteracts the outset that applied in 'insert', which optimize
s |
67 query.roundOut(&adjusted); | 75 // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile gr
id). |
| 76 SkRect query = originalQuery; |
| 77 query.inset(fMarginWidth, fMarginHeight); |
| 78 this->commonAdjust(&query); |
68 | 79 |
69 // The inset is to counteract the outset that was applied in 'insert' | 80 // The inset may have inverted the rectangle, so sort(). |
70 // The outset/inset is to optimize for lookups of size | 81 // TODO(mtklein): It looks like we only end up with inverted bounds in unit
tests |
71 // 'tileInterval + 2 * margin' that are aligned with the tile grid. | 82 // that make explicitly inverted queries, not from insetting. If we can dro
p support for |
72 adjusted.inset(fInfo.fMargin.width(), fInfo.fMargin.height()); | 83 // unsorted bounds (i.e. we don't see them outside unit tests), I think we c
an drop this. |
73 adjusted.offset(fInfo.fOffset); | 84 query.sort(); |
74 adjusted.sort(); // in case the inset inverted the rectangle | |
75 | 85 |
76 // Convert the query rectangle from device coordinates to tile coordinates | 86 // No intersection check. We optimize for queries that are in bounds. |
77 // by rounding outwards to the nearest tile boundary so that the resulting t
ile | 87 // We're safe anyway: userToGrid() will clamp out-of-bounds queries to neare
st tile. |
78 // region includes the query rectangle. | 88 SkIRect grid; |
79 int startX = adjusted.left() / fInfo.fTileInterval.width(), | 89 this->userToGrid(query, &grid); |
80 startY = adjusted.top() / fInfo.fTileInterval.height(); | |
81 int endX = divide_ceil(adjusted.right(), fInfo.fTileInterval.width()), | |
82 endY = divide_ceil(adjusted.bottom(), fInfo.fTileInterval.height()); | |
83 | 90 |
84 // Logically, we could pin endX to [startX, fXTiles], but we force it | 91 const int tilesHit = (grid.fRight - grid.fLeft) * (grid.fBottom - grid.fTop)
; |
85 // up to (startX, fXTiles] to make sure we hit at least one tile. | |
86 // This snaps just-out-of-bounds queries to the neighboring border tile. | |
87 // I don't know if this is an important feature outside of unit tests. | |
88 startX = SkPin32(startX, 0, fXTiles - 1); | |
89 startY = SkPin32(startY, 0, fYTiles - 1); | |
90 endX = SkPin32(endX, startX + 1, fXTiles); | |
91 endY = SkPin32(endY, startY + 1, fYTiles); | |
92 | |
93 const int tilesHit = (endX - startX) * (endY - startY); | |
94 SkASSERT(tilesHit > 0); | 92 SkASSERT(tilesHit > 0); |
95 | 93 |
96 if (tilesHit == 1) { | 94 if (tilesHit == 1) { |
97 // A performance shortcut. The merging code below would work fine here
too. | 95 // A performance shortcut. The merging code below would work fine here
too. |
98 *results = fTiles[startY * fXTiles + startX]; | 96 *results = fTiles[grid.fTop * fXTiles + grid.fLeft]; |
99 return; | 97 return; |
100 } | 98 } |
101 | 99 |
102 // We've got to merge the data in many tiles into a single sorted and dedupl
icated stream. | 100 // We've got to merge the data in many tiles into a single sorted and dedupl
icated stream. |
103 // We do a simple k-way merge based on the value of opIndex. | 101 // We do a simple k-way merge based on the value of opIndex. |
104 | 102 |
105 // Gather pointers to the starts and ends of the tiles to merge. | 103 // Gather pointers to the starts and ends of the tiles to merge. |
106 SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit),
ends(tilesHit); | 104 SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit),
ends(tilesHit); |
107 int i = 0; | 105 int i = 0; |
108 for (int x = startX; x < endX; x++) { | 106 for (int y = grid.fTop; y < grid.fBottom; y++) { |
109 for (int y = startY; y < endY; y++) { | 107 for (int x = grid.fLeft; x < grid.fRight; x++) { |
110 starts[i] = fTiles[y * fXTiles + x].begin(); | 108 starts[i] = fTiles[y * fXTiles + x].begin(); |
111 ends[i] = fTiles[y * fXTiles + x].end(); | 109 ends[i] = fTiles[y * fXTiles + x].end(); |
112 i++; | 110 i++; |
113 } | 111 } |
114 } | 112 } |
115 | 113 |
116 // Merge tiles into results until they're fully consumed. | 114 // Merge tiles into results until they're fully consumed. |
117 results->reset(); | 115 results->reset(); |
118 while (true) { | 116 while (true) { |
119 // The tiles themselves are already ordered, so the earliest op is at th
e front of some | 117 // The tiles themselves are already ordered, so the earliest op is at th
e front of some |
(...skipping 13 matching lines...) Expand all Loading... |
133 // We did find an earliest op. Output it, and step forward every tile th
at contains it. | 131 // We did find an earliest op. Output it, and step forward every tile th
at contains it. |
134 results->push(earliest); | 132 results->push(earliest); |
135 for (int i = 0; i < starts.count(); i++) { | 133 for (int i = 0; i < starts.count(); i++) { |
136 if (starts[i] < ends[i] && *starts[i] == earliest) { | 134 if (starts[i] < ends[i] && *starts[i] == earliest) { |
137 starts[i]++; | 135 starts[i]++; |
138 } | 136 } |
139 } | 137 } |
140 } | 138 } |
141 } | 139 } |
142 | 140 |
OLD | NEW |