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