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 #include "Sk4x.h" | |
10 | 9 |
11 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid
Info& info) | 10 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid
Info& info) |
12 : fXTiles(xTiles) | 11 : fXTiles(xTiles) |
13 , fNumTiles(xTiles * yTiles) | 12 , fYTiles(yTiles) |
| 13 , fInvWidth( SkScalarInvert(info.fTileInterval.width())) |
| 14 , fInvHeight(SkScalarInvert(info.fTileInterval.height())) |
| 15 , fMarginWidth (info.fMargin.fWidth +1) // Margin is offset by 1 as a provi
sion for AA and |
| 16 , fMarginHeight(info.fMargin.fHeight+1) // to cancel the outset applied by
getClipDeviceBounds. |
| 17 , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY)) |
14 , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(), | 18 , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(), |
15 yTiles * info.fTileInterval.height())) | 19 yTiles * info.fTileInterval.height())) |
16 , fMargin(-info.fMargin.fWidth - 1, // Outset margin by 1 as a provision f
or AA and to | 20 , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {} |
17 -info.fMargin.fHeight - 1, // cancel the outset applied by getCli
pDeviceBounds(). | |
18 +info.fMargin.fWidth + 1, | |
19 +info.fMargin.fHeight + 1) | |
20 , fOffset(info.fOffset.fX, | |
21 info.fOffset.fY, | |
22 info.fOffset.fX - SK_ScalarNearlyZero, // We scrunch user-provide
d bounds in a little | |
23 info.fOffset.fY - SK_ScalarNearlyZero) // to make right and botto
m edges exclusive. | |
24 , fUserToGrid(SkScalarInvert(info.fTileInterval.width()), | |
25 SkScalarInvert(info.fTileInterval.height()), | |
26 SkScalarInvert(info.fTileInterval.width()), | |
27 SkScalarInvert(info.fTileInterval.height())) | |
28 , fGridHigh(fXTiles - 1, yTiles - 1, fXTiles - 1, yTiles - 1) | |
29 , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, fNumTiles)) {} | |
30 | 21 |
31 SkTileGrid::~SkTileGrid() { | 22 SkTileGrid::~SkTileGrid() { |
32 SkDELETE_ARRAY(fTiles); | 23 SkDELETE_ARRAY(fTiles); |
33 } | 24 } |
34 | 25 |
35 void SkTileGrid::reserve(unsigned opCount) { | 26 void SkTileGrid::reserve(unsigned opCount) { |
36 if (fNumTiles == 0) { | 27 if (fXTiles * fYTiles == 0) { |
37 return; // A tileless tile grid is nonsensical, but happens in at least
cc_unittests. | 28 return; // A tileless tile grid is nonsensical, but happens in at least
cc_unittests. |
38 } | 29 } |
39 | 30 |
40 // If we assume every op we're about to try to insert() falls within our gri
d bounds, | 31 // If we assume every op we're about to try to insert() falls within our gri
d bounds, |
41 // then every op has to hit at least one tile. In fact, a quick scan over o
ur small | 32 // then every op has to hit at least one tile. In fact, a quick scan over o
ur small |
42 // SKP set shows that in the average SKP, each op hits two 256x256 tiles. | 33 // SKP set shows that in the average SKP, each op hits two 256x256 tiles. |
43 | 34 |
44 // If we take those observations and further assume the ops are distributed
evenly | 35 // If we take those observations and further assume the ops are distributed
evenly |
45 // across the picture, we get this guess for number of ops per tile: | 36 // across the picture, we get this guess for number of ops per tile: |
46 const int opsPerTileGuess = (2 * opCount) / fNumTiles; | 37 const int opsPerTileGuess = (2 * opCount) / (fXTiles * fYTiles); |
47 | 38 |
48 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; tile++)
{ | 39 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles
); tile++) { |
49 tile->setReserve(opsPerTileGuess); | 40 tile->setReserve(opsPerTileGuess); |
50 } | 41 } |
51 | 42 |
52 // In practice, this heuristic means we'll temporarily allocate about 30% mo
re bytes | 43 // In practice, this heuristic means we'll temporarily allocate about 30% mo
re bytes |
53 // than if we made no setReserve() calls, but time spent in insert() drops b
y about 50%. | 44 // than if we made no setReserve() calls, but time spent in insert() drops b
y about 50%. |
54 } | 45 } |
55 | 46 |
56 void SkTileGrid::flushDeferredInserts() { | 47 void SkTileGrid::flushDeferredInserts() { |
57 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; tile++)
{ | 48 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles
); tile++) { |
58 tile->shrinkToFit(); | 49 tile->shrinkToFit(); |
59 } | 50 } |
60 } | 51 } |
61 | 52 |
62 // Convert user-space bounds to grid tiles they cover (LT+RB both inclusive). | 53 // Adjustments to user-provided bounds common to both insert() and search(). |
63 // Out of bounds queries are clamped to the single nearest tile. | 54 // Call this after making insert- or search- specific adjustments. |
64 void SkTileGrid::userToGrid(const Sk4f& user, SkIRect* out) const { | 55 void SkTileGrid::commonAdjust(SkRect* rect) const { |
65 // Map from user coordinates to grid tile coordinates. | 56 // Apply our offset. |
66 Sk4f grid = user.multiply(fUserToGrid); | 57 rect->offset(fOffset); |
67 | 58 |
68 // Now that we're in grid coordinates, clamp to the grid bounds. | 59 // Scrunch the bounds in just a little to make the right and bottom edges |
69 grid = Sk4f::Max(grid, Sk4f(0,0,0,0)); | 60 // exclusive. We want bounds of exactly one tile to hit exactly one tile. |
70 grid = Sk4f::Min(grid, fGridHigh); | 61 rect->fRight -= SK_ScalarNearlyZero; |
71 | 62 rect->fBottom -= SK_ScalarNearlyZero; |
72 // Truncate to integers. | |
73 grid.cast<Sk4i>().store(&out->fLeft); | |
74 } | 63 } |
75 | 64 |
76 // If the rect is inverted, sort it. | 65 // Convert user-space bounds to grid tiles they cover (LT and RB both inclusive)
. |
77 static Sk4f sorted(const Sk4f& ltrb) { | 66 void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const { |
78 // To sort: | 67 grid->fLeft = SkPin32(user.left() * fInvWidth , 0, fXTiles - 1); |
79 // left, right = minmax(left, right) | 68 grid->fTop = SkPin32(user.top() * fInvHeight, 0, fYTiles - 1); |
80 // top, bottom = minmax(top, bottom) | 69 grid->fRight = SkPin32(user.right() * fInvWidth , 0, fXTiles - 1); |
81 Sk4f rblt = ltrb.zwxy(), | 70 grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1); |
82 ltlt = Sk4f::Min(ltrb, rblt), // Holds (2 copies of) new left and top. | |
83 rbrb = Sk4f::Max(ltrb, rblt), // Holds (2 copies of) new right and bot
tom. | |
84 sort = Sk4f::XYAB(ltlt, rbrb); | |
85 return sort; | |
86 } | |
87 | |
88 // Does this rect intersect the grid? | |
89 bool SkTileGrid::intersectsGrid(const Sk4f& ltrb) const { | |
90 SkRect bounds; | |
91 ltrb.store(&bounds.fLeft); | |
92 return SkRect::Intersects(bounds, fGridBounds); | |
93 // TODO: If we can get it fast enough, write intersect using Sk4f. | |
94 } | 71 } |
95 | 72 |
96 void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) { | 73 void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) { |
97 Sk4f bounds = Sk4f(&originalBounds.fLeft).add(fMargin).add(fOffset); | 74 SkRect bounds = originalBounds; |
98 SkASSERT(sorted(bounds).equal(bounds).allTrue()); | 75 bounds.outset(fMarginWidth, fMarginHeight); |
| 76 this->commonAdjust(&bounds); |
99 | 77 |
100 // TODO(mtklein): skip this check and just let out-of-bounds rects insert in
to nearest tile? | 78 // TODO(mtklein): can we assert this instead to save an intersection in Rele
ase mode, |
101 if (!this->intersectsGrid(bounds)) { | 79 // or just allow out-of-bound insertions to insert anyway (clamped to neares
t tile)? |
| 80 if (!SkRect::Intersects(bounds, fGridBounds)) { |
102 return; | 81 return; |
103 } | 82 } |
104 | 83 |
105 SkIRect grid; | 84 SkIRect grid; |
106 this->userToGrid(bounds, &grid); | 85 this->userToGrid(bounds, &grid); |
107 | 86 |
108 // This is just a loop over y then x. This compiles to a slightly faster an
d | 87 // This is just a loop over y then x. This compiles to a slightly faster an
d |
109 // more compact loop than if we just did fTiles[y * fXTiles + x].push(opInde
x). | 88 // more compact loop than if we just did fTiles[y * fXTiles + x].push(opInde
x). |
110 SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft]; | 89 SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft]; |
111 for (int y = 0; y <= grid.fBottom - grid.fTop; y++) { | 90 for (int y = 0; y <= grid.fBottom - grid.fTop; y++) { |
112 SkTDArray<unsigned>* tile = row; | 91 SkTDArray<unsigned>* tile = row; |
113 for (int x = 0; x <= grid.fRight - grid.fLeft; x++) { | 92 for (int x = 0; x <= grid.fRight - grid.fLeft; x++) { |
114 (tile++)->push(opIndex); | 93 (tile++)->push(opIndex); |
115 } | 94 } |
116 row += fXTiles; | 95 row += fXTiles; |
117 } | 96 } |
118 } | 97 } |
119 | 98 |
120 // Number of tiles for which data is allocated on the stack in | 99 // Number of tiles for which data is allocated on the stack in |
121 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider | 100 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider |
122 // increasing this number. Typical large web page, say 2k x 16k, would | 101 // increasing this number. Typical large web page, say 2k x 16k, would |
123 // require 512 tiles of size 256 x 256 pixels. | 102 // require 512 tiles of size 256 x 256 pixels. |
124 static const int kStackAllocationTileCount = 1024; | 103 static const int kStackAllocationTileCount = 1024; |
125 | 104 |
126 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { | 105 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { |
127 // The .subtract(fMargin) counteracts the .add(fMargin) applied in insert(), | 106 // The inset counteracts the outset that applied in 'insert', which optimize
s |
128 // which optimizes for lookups of size tileInterval + 2 * margin (aligned wi
th the tile grid). | 107 // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile gr
id). |
129 // That .subtract(fMargin) may have inverted the rect, so we sort it. | 108 SkRect query = originalQuery; |
130 Sk4f query = sorted(Sk4f(&originalQuery.fLeft).subtract(fMargin).add(fOffset
)); | 109 query.inset(fMarginWidth, fMarginHeight); |
| 110 this->commonAdjust(&query); |
131 | 111 |
| 112 // The inset may have inverted the rectangle, so sort(). |
| 113 // TODO(mtklein): It looks like we only end up with inverted bounds in unit
tests |
| 114 // that make explicitly inverted queries, not from insetting. If we can dro
p support for |
| 115 // unsorted bounds (i.e. we don't see them outside unit tests), I think we c
an drop this. |
| 116 query.sort(); |
| 117 |
| 118 // No intersection check. We optimize for queries that are in bounds. |
| 119 // We're safe anyway: userToGrid() will clamp out-of-bounds queries to neare
st tile. |
132 SkIRect grid; | 120 SkIRect grid; |
133 this->userToGrid(query, &grid); | 121 this->userToGrid(query, &grid); |
134 | 122 |
135 const int tilesHit = (grid.fRight - grid.fLeft + 1) * (grid.fBottom - grid.f
Top + 1); | 123 const int tilesHit = (grid.fRight - grid.fLeft + 1) * (grid.fBottom - grid.f
Top + 1); |
136 SkASSERT(tilesHit > 0); | 124 SkASSERT(tilesHit > 0); |
137 | 125 |
138 if (tilesHit == 1) { | 126 if (tilesHit == 1) { |
139 // A performance shortcut. The merging code below would work fine here
too. | 127 // A performance shortcut. The merging code below would work fine here
too. |
140 *results = fTiles[grid.fTop * fXTiles + grid.fLeft]; | 128 *results = fTiles[grid.fTop * fXTiles + grid.fLeft]; |
141 return; | 129 return; |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
175 // We did find an earliest op. Output it, and step forward every tile th
at contains it. | 163 // We did find an earliest op. Output it, and step forward every tile th
at contains it. |
176 results->push(earliest); | 164 results->push(earliest); |
177 for (int i = 0; i < starts.count(); i++) { | 165 for (int i = 0; i < starts.count(); i++) { |
178 if (starts[i] < ends[i] && *starts[i] == earliest) { | 166 if (starts[i] < ends[i] && *starts[i] == earliest) { |
179 starts[i]++; | 167 starts[i]++; |
180 } | 168 } |
181 } | 169 } |
182 } | 170 } |
183 } | 171 } |
184 | 172 |
OLD | NEW |