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 , fInvWidth( SkScalarInvert(info.fTileInterval.width())) | 13 , fInvWidth( SkScalarInvert(info.fTileInterval.width())) |
14 , fInvHeight(SkScalarInvert(info.fTileInterval.height())) | 14 , fInvHeight(SkScalarInvert(info.fTileInterval.height())) |
15 , fMarginWidth (info.fMargin.fWidth +1) // Margin is offset by 1 as a provi
sion for AA and | 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. | 16 , fMarginHeight(info.fMargin.fHeight+1) // to cancel the outset applied by
getClipDeviceBounds. |
17 , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY)) | 17 , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY)) |
18 , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(), | 18 , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(), |
19 yTiles * info.fTileInterval.height())) | 19 yTiles * info.fTileInterval.height())) |
20 , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {} | 20 , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {} |
21 | 21 |
22 SkTileGrid::~SkTileGrid() { | 22 SkTileGrid::~SkTileGrid() { |
23 SkDELETE_ARRAY(fTiles); | 23 SkDELETE_ARRAY(fTiles); |
24 } | 24 } |
25 | 25 |
26 void SkTileGrid::reserve(unsigned opCount) { | 26 void SkTileGrid::reserve(int opCount) { |
27 if (fXTiles * fYTiles == 0) { | 27 if (fXTiles * fYTiles == 0) { |
28 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. |
29 } | 29 } |
30 | 30 |
31 // 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, |
32 // 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 |
33 // 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. |
34 | 34 |
35 // 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 |
36 // 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: |
37 const int opsPerTileGuess = (2 * opCount) / (fXTiles * fYTiles); | 37 const int opsPerTileGuess = (2 * opCount) / (fXTiles * fYTiles); |
38 | 38 |
39 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles
); tile++) { | 39 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles
); tile++) { |
40 tile->setReserve(opsPerTileGuess); | 40 tile->setReserve(opsPerTileGuess); |
41 } | 41 } |
42 | 42 |
43 // 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 |
44 // 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%. |
45 } | 45 } |
46 | 46 |
47 void SkTileGrid::flushDeferredInserts() { | 47 void SkTileGrid::shrinkToFit() { |
48 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles
); tile++) { | 48 for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles
); tile++) { |
49 tile->shrinkToFit(); | 49 tile->shrinkToFit(); |
50 } | 50 } |
51 } | 51 } |
52 | 52 |
53 // Adjustments to user-provided bounds common to both insert() and search(). | 53 // Adjustments to user-provided bounds common to both insert() and search(). |
54 // Call this after making insert- or search- specific adjustments. | 54 // Call this after making insert- or search- specific adjustments. |
55 void SkTileGrid::commonAdjust(SkRect* rect) const { | 55 void SkTileGrid::commonAdjust(SkRect* rect) const { |
56 // Apply our offset. | 56 // Apply our offset. |
57 rect->offset(fOffset); | 57 rect->offset(fOffset); |
58 | 58 |
59 // Scrunch the bounds in just a little to make the right and bottom edges | 59 // Scrunch the bounds in just a little to make the right and bottom edges |
60 // exclusive. We want bounds of exactly one tile to hit exactly one tile. | 60 // exclusive. We want bounds of exactly one tile to hit exactly one tile. |
61 rect->fRight -= SK_ScalarNearlyZero; | 61 rect->fRight -= SK_ScalarNearlyZero; |
62 rect->fBottom -= SK_ScalarNearlyZero; | 62 rect->fBottom -= SK_ScalarNearlyZero; |
63 } | 63 } |
64 | 64 |
65 // Convert user-space bounds to grid tiles they cover (LT and RB both inclusive)
. | 65 // Convert user-space bounds to grid tiles they cover (LT and RB both inclusive)
. |
66 void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const { | 66 void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const { |
67 grid->fLeft = SkPin32(user.left() * fInvWidth , 0, fXTiles - 1); | 67 grid->fLeft = SkPin32(user.left() * fInvWidth , 0, fXTiles - 1); |
68 grid->fTop = SkPin32(user.top() * fInvHeight, 0, fYTiles - 1); | 68 grid->fTop = SkPin32(user.top() * fInvHeight, 0, fYTiles - 1); |
69 grid->fRight = SkPin32(user.right() * fInvWidth , 0, fXTiles - 1); | 69 grid->fRight = SkPin32(user.right() * fInvWidth , 0, fXTiles - 1); |
70 grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1); | 70 grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1); |
71 } | 71 } |
72 | 72 |
73 void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) { | 73 void SkTileGrid::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) { |
74 SkRect bounds = originalBounds; | 74 this->reserve(N); |
75 bounds.outset(fMarginWidth, fMarginHeight); | |
76 this->commonAdjust(&bounds); | |
77 | 75 |
78 // TODO(mtklein): can we assert this instead to save an intersection in Rele
ase mode, | 76 for (int i = 0; i < N; i++) { |
79 // or just allow out-of-bound insertions to insert anyway (clamped to neares
t tile)? | 77 SkRect bounds = (*boundsArray)[i]; |
80 if (!SkRect::Intersects(bounds, fGridBounds)) { | 78 bounds.outset(fMarginWidth, fMarginHeight); |
81 return; | 79 this->commonAdjust(&bounds); |
| 80 |
| 81 // TODO(mtklein): can we assert this instead to save an intersection in
Release mode, |
| 82 // or just allow out-of-bound insertions to insert anyway (clamped to ne
arest tile)? |
| 83 if (!SkRect::Intersects(bounds, fGridBounds)) { |
| 84 continue; |
| 85 } |
| 86 |
| 87 SkIRect grid; |
| 88 this->userToGrid(bounds, &grid); |
| 89 |
| 90 // This is just a loop over y then x. This compiles to a slightly faste
r and |
| 91 // more compact loop than if we just did fTiles[y * fXTiles + x].push(i)
. |
| 92 SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft]; |
| 93 for (int y = 0; y <= grid.fBottom - grid.fTop; y++) { |
| 94 SkTDArray<unsigned>* tile = row; |
| 95 for (int x = 0; x <= grid.fRight - grid.fLeft; x++) { |
| 96 (tile++)->push(i); |
| 97 } |
| 98 row += fXTiles; |
| 99 } |
82 } | 100 } |
83 | 101 this->shrinkToFit(); |
84 SkIRect grid; | |
85 this->userToGrid(bounds, &grid); | |
86 | |
87 // 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). | |
89 SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft]; | |
90 for (int y = 0; y <= grid.fBottom - grid.fTop; y++) { | |
91 SkTDArray<unsigned>* tile = row; | |
92 for (int x = 0; x <= grid.fRight - grid.fLeft; x++) { | |
93 (tile++)->push(opIndex); | |
94 } | |
95 row += fXTiles; | |
96 } | |
97 } | 102 } |
98 | 103 |
99 // Number of tiles for which data is allocated on the stack in | 104 // Number of tiles for which data is allocated on the stack in |
100 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider | 105 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider |
101 // increasing this number. Typical large web page, say 2k x 16k, would | 106 // increasing this number. Typical large web page, say 2k x 16k, would |
102 // require 512 tiles of size 256 x 256 pixels. | 107 // require 512 tiles of size 256 x 256 pixels. |
103 static const int kStackAllocationTileCount = 1024; | 108 static const int kStackAllocationTileCount = 1024; |
104 | 109 |
105 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { | 110 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { |
106 // The inset counteracts the outset that applied in 'insert', which optimize
s | 111 // The inset counteracts the outset that applied in 'insert', which optimize
s |
(...skipping 56 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. | 168 // We did find an earliest op. Output it, and step forward every tile th
at contains it. |
164 results->push(earliest); | 169 results->push(earliest); |
165 for (int i = 0; i < starts.count(); i++) { | 170 for (int i = 0; i < starts.count(); i++) { |
166 if (starts[i] < ends[i] && *starts[i] == earliest) { | 171 if (starts[i] < ends[i] && *starts[i] == earliest) { |
167 starts[i]++; | 172 starts[i]++; |
168 } | 173 } |
169 } | 174 } |
170 } | 175 } |
171 } | 176 } |
172 | 177 |
OLD | NEW |