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) |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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 inclusive, RB exclusiv
e). | 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) + 1; | 69 grid->fRight = SkPin32(user.right() * fInvWidth , 0, fXTiles - 1); |
70 grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1) + 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(unsigned opIndex, const SkRect& originalBounds, bool) { |
74 SkRect bounds = originalBounds; | 74 SkRect bounds = originalBounds; |
75 bounds.outset(fMarginWidth, fMarginHeight); | 75 bounds.outset(fMarginWidth, fMarginHeight); |
76 this->commonAdjust(&bounds); | 76 this->commonAdjust(&bounds); |
77 | 77 |
78 // TODO(mtklein): can we assert this instead to save an intersection in Rele
ase mode, | 78 // TODO(mtklein): can we assert this instead to save an intersection in Rele
ase mode, |
79 // or just allow out-of-bound insertions to insert anyway (clamped to neares
t tile)? | 79 // or just allow out-of-bound insertions to insert anyway (clamped to neares
t tile)? |
80 if (!SkRect::Intersects(bounds, fGridBounds)) { | 80 if (!SkRect::Intersects(bounds, fGridBounds)) { |
81 return; | 81 return; |
82 } | 82 } |
83 | 83 |
84 SkIRect grid; | 84 SkIRect grid; |
85 this->userToGrid(bounds, &grid); | 85 this->userToGrid(bounds, &grid); |
86 | 86 |
87 for (int y = grid.fTop; y < grid.fBottom; y++) { | 87 for (int y = grid.fTop; y <= grid.fBottom; y++) { |
88 for (int x = grid.fLeft; x < grid.fRight; x++) { | 88 for (int x = grid.fLeft; x <= grid.fRight; x++) { |
89 fTiles[y * fXTiles + x].push(opIndex); | 89 fTiles[y * fXTiles + x].push(opIndex); |
90 } | 90 } |
91 } | 91 } |
92 } | 92 } |
93 | 93 |
94 // Number of tiles for which data is allocated on the stack in | 94 // Number of tiles for which data is allocated on the stack in |
95 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider | 95 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider |
96 // increasing this number. Typical large web page, say 2k x 16k, would | 96 // increasing this number. Typical large web page, say 2k x 16k, would |
97 // require 512 tiles of size 256 x 256 pixels. | 97 // require 512 tiles of size 256 x 256 pixels. |
98 static const int kStackAllocationTileCount = 1024; | 98 static const int kStackAllocationTileCount = 1024; |
99 | 99 |
100 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { | 100 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result
s) const { |
101 // The inset counteracts the outset that applied in 'insert', which optimize
s | 101 // The inset counteracts the outset that applied in 'insert', which optimize
s |
102 // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile gr
id). | 102 // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile gr
id). |
103 SkRect query = originalQuery; | 103 SkRect query = originalQuery; |
104 query.inset(fMarginWidth, fMarginHeight); | 104 query.inset(fMarginWidth, fMarginHeight); |
105 this->commonAdjust(&query); | 105 this->commonAdjust(&query); |
106 | 106 |
107 // The inset may have inverted the rectangle, so sort(). | 107 // The inset may have inverted the rectangle, so sort(). |
108 // TODO(mtklein): It looks like we only end up with inverted bounds in unit
tests | 108 // TODO(mtklein): It looks like we only end up with inverted bounds in unit
tests |
109 // that make explicitly inverted queries, not from insetting. If we can dro
p support for | 109 // that make explicitly inverted queries, not from insetting. If we can dro
p support for |
110 // unsorted bounds (i.e. we don't see them outside unit tests), I think we c
an drop this. | 110 // unsorted bounds (i.e. we don't see them outside unit tests), I think we c
an drop this. |
111 query.sort(); | 111 query.sort(); |
112 | 112 |
113 // No intersection check. We optimize for queries that are in bounds. | 113 // No intersection check. We optimize for queries that are in bounds. |
114 // We're safe anyway: userToGrid() will clamp out-of-bounds queries to neare
st tile. | 114 // We're safe anyway: userToGrid() will clamp out-of-bounds queries to neare
st tile. |
115 SkIRect grid; | 115 SkIRect grid; |
116 this->userToGrid(query, &grid); | 116 this->userToGrid(query, &grid); |
117 | 117 |
118 const int tilesHit = (grid.fRight - grid.fLeft) * (grid.fBottom - grid.fTop)
; | 118 const int tilesHit = (grid.fRight - grid.fLeft + 1) * (grid.fBottom - grid.f
Top + 1); |
119 SkASSERT(tilesHit > 0); | 119 SkASSERT(tilesHit > 0); |
120 | 120 |
121 if (tilesHit == 1) { | 121 if (tilesHit == 1) { |
122 // A performance shortcut. The merging code below would work fine here
too. | 122 // A performance shortcut. The merging code below would work fine here
too. |
123 *results = fTiles[grid.fTop * fXTiles + grid.fLeft]; | 123 *results = fTiles[grid.fTop * fXTiles + grid.fLeft]; |
124 return; | 124 return; |
125 } | 125 } |
126 | 126 |
127 // We've got to merge the data in many tiles into a single sorted and dedupl
icated stream. | 127 // We've got to merge the data in many tiles into a single sorted and dedupl
icated stream. |
128 // We do a simple k-way merge based on the value of opIndex. | 128 // We do a simple k-way merge based on the value of opIndex. |
129 | 129 |
130 // Gather pointers to the starts and ends of the tiles to merge. | 130 // Gather pointers to the starts and ends of the tiles to merge. |
131 SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit),
ends(tilesHit); | 131 SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit),
ends(tilesHit); |
132 int i = 0; | 132 int i = 0; |
133 for (int y = grid.fTop; y < grid.fBottom; y++) { | 133 for (int y = grid.fTop; y <= grid.fBottom; y++) { |
134 for (int x = grid.fLeft; x < grid.fRight; x++) { | 134 for (int x = grid.fLeft; x <= grid.fRight; x++) { |
135 starts[i] = fTiles[y * fXTiles + x].begin(); | 135 starts[i] = fTiles[y * fXTiles + x].begin(); |
136 ends[i] = fTiles[y * fXTiles + x].end(); | 136 ends[i] = fTiles[y * fXTiles + x].end(); |
137 i++; | 137 i++; |
138 } | 138 } |
139 } | 139 } |
140 | 140 |
141 // Merge tiles into results until they're fully consumed. | 141 // Merge tiles into results until they're fully consumed. |
142 results->reset(); | 142 results->reset(); |
143 while (true) { | 143 while (true) { |
144 // The tiles themselves are already ordered, so the earliest op is at th
e front of some | 144 // The tiles themselves are already ordered, so the earliest op is at th
e front of some |
(...skipping 13 matching lines...) Expand all Loading... |
158 // We did find an earliest op. Output it, and step forward every tile th
at contains it. | 158 // We did find an earliest op. Output it, and step forward every tile th
at contains it. |
159 results->push(earliest); | 159 results->push(earliest); |
160 for (int i = 0; i < starts.count(); i++) { | 160 for (int i = 0; i < starts.count(); i++) { |
161 if (starts[i] < ends[i] && *starts[i] == earliest) { | 161 if (starts[i] < ends[i] && *starts[i] == earliest) { |
162 starts[i]++; | 162 starts[i]++; |
163 } | 163 } |
164 } | 164 } |
165 } | 165 } |
166 } | 166 } |
167 | 167 |
OLD | NEW |