1/*
2 Copyright (C) 2010-2012 Nokia Corporation and/or its subsidiary(-ies)
3
4 This library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Library General Public
6 License as published by the Free Software Foundation; either
7 version 2 of the License, or (at your option) any later version.
8
9 This library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Library General Public License for more details.
13
14 You should have received a copy of the GNU Library General Public License
15 along with this library; see the file COPYING.LIB. If not, write to
16 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 Boston, MA 02110-1301, USA.
18 */
19
20#include "config.h"
21#include "TiledBackingStore.h"
22
23#if USE(COORDINATED_GRAPHICS)
24#include "GraphicsContext.h"
25#include "TiledBackingStoreClient.h"
26#include <wtf/CheckedArithmetic.h>
27#include <wtf/MemoryPressureHandler.h>
28
29namespace WebCore {
30
31static const int defaultTileDimension = 512;
32
33static IntPoint innerBottomRight(const IntRect& rect)
34{
35 // Actually, the rect does not contain rect.maxX(). Refer to IntRect::contain.
36 return IntPoint(rect.maxX() - 1, rect.maxY() - 1);
37}
38
39TiledBackingStore::TiledBackingStore(TiledBackingStoreClient& client, float contentsScale)
40 : m_client(client)
41 , m_tileSize(defaultTileDimension, defaultTileDimension)
42 , m_coverAreaMultiplier(2.0f)
43 , m_contentsScale(contentsScale)
44 , m_pendingTileCreation(false)
45{
46}
47
48TiledBackingStore::~TiledBackingStore() = default;
49
50void TiledBackingStore::setTrajectoryVector(const FloatPoint& trajectoryVector)
51{
52 m_pendingTrajectoryVector = trajectoryVector;
53 m_pendingTrajectoryVector.normalize();
54}
55
56void TiledBackingStore::createTilesIfNeeded(const IntRect& unscaledVisibleRect, const IntRect& contentsRect)
57{
58 IntRect scaledContentsRect = mapFromContents(contentsRect);
59 IntRect visibleRect = mapFromContents(unscaledVisibleRect);
60 float coverAreaMultiplier = MemoryPressureHandler::singleton().isUnderMemoryPressure() ? 1.0f : 2.0f;
61
62 bool didChange = m_trajectoryVector != m_pendingTrajectoryVector || m_visibleRect != visibleRect || m_rect != scaledContentsRect || m_coverAreaMultiplier != coverAreaMultiplier;
63 if (didChange || m_pendingTileCreation)
64 createTiles(visibleRect, scaledContentsRect, coverAreaMultiplier);
65}
66
67void TiledBackingStore::invalidate(const IntRect& contentsDirtyRect)
68{
69 IntRect dirtyRect(mapFromContents(contentsDirtyRect));
70 IntRect keepRectFitToTileSize = tileRectForCoordinate(tileCoordinateForPoint(m_keepRect.location()));
71 keepRectFitToTileSize.unite(tileRectForCoordinate(tileCoordinateForPoint(innerBottomRight(m_keepRect))));
72
73 // Only iterate on the part of the rect that we know we might have tiles.
74 IntRect coveredDirtyRect = intersection(dirtyRect, keepRectFitToTileSize);
75 Tile::Coordinate topLeft = tileCoordinateForPoint(coveredDirtyRect.location());
76 Tile::Coordinate bottomRight = tileCoordinateForPoint(innerBottomRight(coveredDirtyRect));
77
78 for (int yCoordinate = topLeft.y(); yCoordinate <= bottomRight.y(); ++yCoordinate) {
79 for (int xCoordinate = topLeft.x(); xCoordinate <= bottomRight.x(); ++xCoordinate) {
80 Tile* currentTile = m_tiles.get(Tile::Coordinate(xCoordinate, yCoordinate));
81 if (!currentTile)
82 continue;
83 // Pass the full rect to each tile as coveredDirtyRect might not
84 // contain them completely and we don't want partial tile redraws.
85 currentTile->invalidate(dirtyRect);
86 }
87 }
88}
89
90Vector<std::reference_wrapper<Tile>> TiledBackingStore::dirtyTiles()
91{
92 Vector<std::reference_wrapper<Tile>> tiles;
93 for (auto& tile : m_tiles.values()) {
94 if (tile->isDirty())
95 tiles.append(*tile);
96 }
97
98 return tiles;
99}
100
101double TiledBackingStore::tileDistance(const IntRect& viewport, const Tile::Coordinate& tileCoordinate) const
102{
103 if (viewport.intersects(tileRectForCoordinate(tileCoordinate)))
104 return 0;
105
106 IntPoint viewCenter = viewport.location() + IntSize(viewport.width() / 2, viewport.height() / 2);
107 Tile::Coordinate centerCoordinate = tileCoordinateForPoint(viewCenter);
108
109 return std::max(abs(centerCoordinate.y() - tileCoordinate.y()), abs(centerCoordinate.x() - tileCoordinate.x()));
110}
111
112// Returns a ratio between 0.0f and 1.0f of the surface covered by rendered tiles.
113float TiledBackingStore::coverageRatio(const WebCore::IntRect& dirtyRect) const
114{
115 float rectArea = dirtyRect.width() * dirtyRect.height();
116 float coverArea = 0.0f;
117
118 Tile::Coordinate topLeft = tileCoordinateForPoint(dirtyRect.location());
119 Tile::Coordinate bottomRight = tileCoordinateForPoint(innerBottomRight(dirtyRect));
120
121 for (int yCoordinate = topLeft.y(); yCoordinate <= bottomRight.y(); ++yCoordinate) {
122 for (int xCoordinate = topLeft.x(); xCoordinate <= bottomRight.x(); ++xCoordinate) {
123 Tile::Coordinate currentCoordinate(xCoordinate, yCoordinate);
124 Tile* currentTile = m_tiles.get(currentCoordinate);
125 if (currentTile && currentTile->isReadyToPaint()) {
126 IntRect coverRect = intersection(dirtyRect, currentTile->rect());
127 coverArea += coverRect.width() * coverRect.height();
128 }
129 }
130 }
131 return coverArea / rectArea;
132}
133
134bool TiledBackingStore::visibleAreaIsCovered() const
135{
136 return coverageRatio(intersection(m_visibleRect, m_rect)) == 1.0f;
137}
138
139void TiledBackingStore::createTiles(const IntRect& visibleRect, const IntRect& scaledContentsRect, float coverAreaMultiplier)
140{
141 // Update our backing store geometry.
142 m_rect = scaledContentsRect;
143 m_trajectoryVector = m_pendingTrajectoryVector;
144 m_visibleRect = visibleRect;
145 m_coverAreaMultiplier = coverAreaMultiplier;
146
147 if (m_rect.isEmpty()) {
148 setCoverRect(IntRect());
149 setKeepRect(IntRect());
150 return;
151 }
152
153 /* We must compute cover and keep rects using the visibleRect, instead of the rect intersecting the visibleRect with m_rect,
154 * because TBS can be used as a backing store of GraphicsLayer and the visible rect usually does not intersect with m_rect.
155 * In the below case, the intersecting rect is an empty.
156 *
157 * +---------------+
158 * | |
159 * | m_rect |
160 * | +-------|-----------------------+
161 * | | HERE | cover or keep |
162 * +---------------+ rect |
163 * | +---------+ |
164 * | | visible | |
165 * | | rect | |
166 * | +---------+ |
167 * | |
168 * | |
169 * +-------------------------------+
170 *
171 * We must create or keep the tiles in the HERE region.
172 */
173
174 IntRect coverRect;
175 IntRect keepRect;
176 computeCoverAndKeepRect(m_visibleRect, coverRect, keepRect);
177
178 setCoverRect(coverRect);
179 setKeepRect(keepRect);
180
181 if (coverRect.isEmpty())
182 return;
183
184 // Resize tiles at the edge in case the contents size has changed, but only do so
185 // after having dropped tiles outside the keep rect.
186 if (m_previousRect != m_rect) {
187 m_previousRect = m_rect;
188 resizeEdgeTiles();
189 }
190
191 // Search for the tile position closest to the viewport center that does not yet contain a tile.
192 // Which position is considered the closest depends on the tileDistance function.
193 double shortestDistance = std::numeric_limits<double>::infinity();
194 Vector<Tile::Coordinate> tilesToCreate;
195 unsigned requiredTileCount = 0;
196
197 // Cover areas (in tiles) with minimum distance from the visible rect. If the visible rect is
198 // not covered already it will be covered first in one go, due to the distance being 0 for tiles
199 // inside the visible rect.
200 Tile::Coordinate topLeft = tileCoordinateForPoint(coverRect.location());
201 Tile::Coordinate bottomRight = tileCoordinateForPoint(innerBottomRight(coverRect));
202 for (int yCoordinate = topLeft.y(); yCoordinate <= bottomRight.y(); ++yCoordinate) {
203 for (int xCoordinate = topLeft.x(); xCoordinate <= bottomRight.x(); ++xCoordinate) {
204 Tile::Coordinate currentCoordinate(xCoordinate, yCoordinate);
205 if (m_tiles.contains(currentCoordinate))
206 continue;
207 ++requiredTileCount;
208 double distance = tileDistance(m_visibleRect, currentCoordinate);
209 if (distance > shortestDistance)
210 continue;
211 if (distance < shortestDistance) {
212 tilesToCreate.clear();
213 shortestDistance = distance;
214 }
215 tilesToCreate.append(currentCoordinate);
216 }
217 }
218
219 // Now construct the tile(s) within the shortest distance.
220 unsigned tilesToCreateCount = tilesToCreate.size();
221 for (unsigned n = 0; n < tilesToCreateCount; ++n) {
222 Tile::Coordinate coordinate = tilesToCreate[n];
223 m_tiles.add(coordinate, std::make_unique<Tile>(*this, coordinate));
224 }
225 requiredTileCount -= tilesToCreateCount;
226
227 // Re-call createTiles on a timer to cover the visible area with the newest shortest distance.
228 m_pendingTileCreation = requiredTileCount;
229 if (m_pendingTileCreation)
230 m_client.tiledBackingStoreHasPendingTileCreation();
231}
232
233void TiledBackingStore::adjustForContentsRect(IntRect& rect) const
234{
235 IntRect bounds = m_rect;
236 IntSize candidateSize = rect.size();
237
238 rect.intersect(bounds);
239
240 if (rect.size() == candidateSize)
241 return;
242
243 /*
244 * In the following case, there is no intersection of the contents rect and the cover rect.
245 * Thus the latter should not be inflated.
246 *
247 * +---------------+
248 * | m_rect |
249 * +---------------+
250 *
251 * +-------------------------------+
252 * | cover rect |
253 * | +---------+ |
254 * | | visible | |
255 * | | rect | |
256 * | +---------+ |
257 * +-------------------------------+
258 */
259 if (rect.isEmpty())
260 return;
261
262 // Try to create a cover rect of the same size as the candidate, but within content bounds.
263 int pixelsCovered = 0;
264 if (!WTF::safeMultiply(candidateSize.width(), candidateSize.height(), pixelsCovered))
265 pixelsCovered = std::numeric_limits<int>::max();
266
267 if (rect.width() < candidateSize.width())
268 rect.inflateY(((pixelsCovered / rect.width()) - rect.height()) / 2);
269 if (rect.height() < candidateSize.height())
270 rect.inflateX(((pixelsCovered / rect.height()) - rect.width()) / 2);
271
272 rect.intersect(bounds);
273}
274
275void TiledBackingStore::computeCoverAndKeepRect(const IntRect& visibleRect, IntRect& coverRect, IntRect& keepRect) const
276{
277 coverRect = visibleRect;
278 keepRect = visibleRect;
279
280 // If we cover more that the actual viewport we can be smart about which tiles we choose to render.
281 if (m_coverAreaMultiplier > 1) {
282 // The initial cover area covers equally in each direction, according to the coverAreaMultiplier.
283 coverRect.inflateX(visibleRect.width() * (m_coverAreaMultiplier - 1) / 2);
284 coverRect.inflateY(visibleRect.height() * (m_coverAreaMultiplier - 1) / 2);
285 keepRect = coverRect;
286
287 if (m_trajectoryVector != FloatPoint::zero()) {
288 // A null trajectory vector (no motion) means that tiles for the coverArea will be created.
289 // A non-null trajectory vector will shrink the covered rect to visibleRect plus its expansion from its
290 // center toward the cover area edges in the direction of the given vector.
291
292 // E.g. if visibleRect == (10,10)5x5 and coverAreaMultiplier == 3.0:
293 // a (0,0) trajectory vector will create tiles intersecting (5,5)15x15,
294 // a (1,0) trajectory vector will create tiles intersecting (10,10)10x5,
295 // and a (1,1) trajectory vector will create tiles intersecting (10,10)10x10.
296
297 // Multiply the vector by the distance to the edge of the cover area.
298 float trajectoryVectorMultiplier = (m_coverAreaMultiplier - 1) / 2;
299
300 // Unite the visible rect with a "ghost" of the visible rect moved in the direction of the trajectory vector.
301 coverRect = visibleRect;
302 coverRect.move(coverRect.width() * m_trajectoryVector.x() * trajectoryVectorMultiplier, coverRect.height() * m_trajectoryVector.y() * trajectoryVectorMultiplier);
303
304 coverRect.unite(visibleRect);
305 }
306 ASSERT(keepRect.contains(coverRect));
307 }
308
309 adjustForContentsRect(coverRect);
310
311 // The keep rect is an inflated version of the cover rect, inflated in tile dimensions.
312 keepRect.unite(coverRect);
313 keepRect.inflateX(m_tileSize.width() / 2);
314 keepRect.inflateY(m_tileSize.height() / 2);
315 keepRect.intersect(m_rect);
316
317 ASSERT(coverRect.isEmpty() || keepRect.contains(coverRect));
318}
319
320void TiledBackingStore::resizeEdgeTiles()
321{
322 Vector<Tile::Coordinate> tilesToRemove;
323 for (auto& tile : m_tiles.values()) {
324 Tile::Coordinate tileCoordinate = tile->coordinate();
325 IntRect tileRect = tile->rect();
326 IntRect expectedTileRect = tileRectForCoordinate(tileCoordinate);
327 if (expectedTileRect.isEmpty())
328 tilesToRemove.append(tileCoordinate);
329 else if (expectedTileRect != tileRect)
330 tile->resize(expectedTileRect.size());
331 }
332
333 for (auto& coordinateToRemove : tilesToRemove)
334 m_tiles.remove(coordinateToRemove);
335}
336
337void TiledBackingStore::setKeepRect(const IntRect& keepRect)
338{
339 // Drop tiles outside the new keepRect.
340
341 FloatRect keepRectF = keepRect;
342
343 Vector<Tile::Coordinate> toRemove;
344 for (auto& tile : m_tiles.values()) {
345 Tile::Coordinate coordinate = tile->coordinate();
346 FloatRect tileRect = tile->rect();
347 if (!tileRect.intersects(keepRectF))
348 toRemove.append(coordinate);
349 }
350
351 for (auto& coordinateToRemove : toRemove)
352 m_tiles.remove(coordinateToRemove);
353
354 m_keepRect = keepRect;
355}
356
357void TiledBackingStore::removeAllNonVisibleTiles(const IntRect& unscaledVisibleRect, const IntRect& contentsRect)
358{
359 IntRect boundedVisibleRect = mapFromContents(intersection(unscaledVisibleRect, contentsRect));
360 setKeepRect(boundedVisibleRect);
361}
362
363IntRect TiledBackingStore::mapToContents(const IntRect& rect) const
364{
365 return enclosingIntRect(FloatRect(rect.x() / m_contentsScale,
366 rect.y() / m_contentsScale,
367 rect.width() / m_contentsScale,
368 rect.height() / m_contentsScale));
369}
370
371IntRect TiledBackingStore::mapFromContents(const IntRect& rect) const
372{
373 return enclosingIntRect(FloatRect(rect.x() * m_contentsScale,
374 rect.y() * m_contentsScale,
375 rect.width() * m_contentsScale,
376 rect.height() * m_contentsScale));
377}
378
379IntRect TiledBackingStore::tileRectForCoordinate(const Tile::Coordinate& coordinate) const
380{
381 IntRect rect(coordinate.x() * m_tileSize.width(),
382 coordinate.y() * m_tileSize.height(),
383 m_tileSize.width(),
384 m_tileSize.height());
385
386 rect.intersect(m_rect);
387 return rect;
388}
389
390Tile::Coordinate TiledBackingStore::tileCoordinateForPoint(const IntPoint& point) const
391{
392 int x = point.x() / m_tileSize.width();
393 int y = point.y() / m_tileSize.height();
394 return Tile::Coordinate(std::max(x, 0), std::max(y, 0));
395}
396
397}
398
399#endif
400