1 // Copyright 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "cc/resources/picture_layer_tiling.h" 6 7 #include <algorithm> 8 #include <cmath> 9 #include <limits> 10 #include <set> 11 12 #include "base/debug/trace_event.h" 13 #include "base/debug/trace_event_argument.h" 14 #include "base/logging.h" 15 #include "cc/base/math_util.h" 16 #include "cc/resources/tile.h" 17 #include "cc/resources/tile_priority.h" 18 #include "ui/gfx/point_conversions.h" 19 #include "ui/gfx/rect_conversions.h" 20 #include "ui/gfx/safe_integer_conversions.h" 21 #include "ui/gfx/size_conversions.h" 22 23 namespace cc { 24 namespace { 25 26 const float kSoonBorderDistanceInScreenPixels = 312.f; 27 28 class TileEvictionOrder { 29 public: 30 explicit TileEvictionOrder(TreePriority tree_priority) 31 : tree_priority_(tree_priority) {} 32 ~TileEvictionOrder() {} 33 34 bool operator()(const Tile* a, const Tile* b) { 35 const TilePriority& a_priority = 36 a->priority_for_tree_priority(tree_priority_); 37 const TilePriority& b_priority = 38 b->priority_for_tree_priority(tree_priority_); 39 40 DCHECK(a_priority.priority_bin == b_priority.priority_bin); 41 DCHECK(a->required_for_activation() == b->required_for_activation()); 42 43 // Or if a is occluded and b is unoccluded. 44 bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_); 45 bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_); 46 if (a_is_occluded != b_is_occluded) 47 return a_is_occluded; 48 49 // Or if a is farther away from visible. 50 return a_priority.distance_to_visible > b_priority.distance_to_visible; 51 } 52 53 private: 54 TreePriority tree_priority_; 55 }; 56 57 void ReleaseTile(Tile* tile, WhichTree tree) { 58 // Reset priority as tile is ref-counted and might still be used 59 // even though we no longer hold a reference to it here anymore. 60 tile->SetPriority(tree, TilePriority()); 61 tile->set_shared(false); 62 } 63 64 } // namespace 65 66 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create( 67 float contents_scale, 68 const gfx::Size& layer_bounds, 69 PictureLayerTilingClient* client) { 70 return make_scoped_ptr(new PictureLayerTiling(contents_scale, 71 layer_bounds, 72 client)); 73 } 74 75 PictureLayerTiling::PictureLayerTiling(float contents_scale, 76 const gfx::Size& layer_bounds, 77 PictureLayerTilingClient* client) 78 : contents_scale_(contents_scale), 79 layer_bounds_(layer_bounds), 80 resolution_(NON_IDEAL_RESOLUTION), 81 client_(client), 82 tiling_data_(gfx::Size(), gfx::Size(), true), 83 last_impl_frame_time_in_seconds_(0.0), 84 has_visible_rect_tiles_(false), 85 has_skewport_rect_tiles_(false), 86 has_soon_border_rect_tiles_(false), 87 has_eventually_rect_tiles_(false), 88 eviction_tiles_cache_valid_(false), 89 eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) { 90 gfx::Size content_bounds = 91 gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale)); 92 gfx::Size tile_size = client_->CalculateTileSize(content_bounds); 93 if (tile_size.IsEmpty()) { 94 layer_bounds_ = gfx::Size(); 95 content_bounds = gfx::Size(); 96 } 97 98 DCHECK(!gfx::ToFlooredSize( 99 gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) << 100 "Tiling created with scale too small as contents become empty." << 101 " Layer bounds: " << layer_bounds.ToString() << 102 " Contents scale: " << contents_scale; 103 104 tiling_data_.SetTilingSize(content_bounds); 105 tiling_data_.SetMaxTextureSize(tile_size); 106 } 107 108 PictureLayerTiling::~PictureLayerTiling() { 109 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) 110 ReleaseTile(it->second.get(), client_->GetTree()); 111 } 112 113 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) { 114 client_ = client; 115 } 116 117 Tile* PictureLayerTiling::CreateTile(int i, 118 int j, 119 const PictureLayerTiling* twin_tiling) { 120 TileMapKey key(i, j); 121 DCHECK(tiles_.find(key) == tiles_.end()); 122 123 gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j); 124 gfx::Rect tile_rect = paint_rect; 125 tile_rect.set_size(tiling_data_.max_texture_size()); 126 127 // Check our twin for a valid tile. 128 if (twin_tiling && 129 tiling_data_.max_texture_size() == 130 twin_tiling->tiling_data_.max_texture_size()) { 131 if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) { 132 gfx::Rect rect = 133 gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_); 134 if (!client_->GetInvalidation()->Intersects(rect)) { 135 DCHECK(!candidate_tile->is_shared()); 136 candidate_tile->set_shared(true); 137 tiles_[key] = candidate_tile; 138 return candidate_tile; 139 } 140 } 141 } 142 143 // Create a new tile because our twin didn't have a valid one. 144 scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect); 145 if (tile.get()) { 146 DCHECK(!tile->is_shared()); 147 tiles_[key] = tile; 148 } 149 return tile.get(); 150 } 151 152 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() { 153 const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this); 154 bool include_borders = false; 155 for (TilingData::Iterator iter( 156 &tiling_data_, live_tiles_rect_, include_borders); 157 iter; 158 ++iter) { 159 TileMapKey key = iter.index(); 160 TileMap::iterator find = tiles_.find(key); 161 if (find != tiles_.end()) 162 continue; 163 CreateTile(key.first, key.second, twin_tiling); 164 } 165 166 VerifyLiveTilesRect(); 167 } 168 169 void PictureLayerTiling::UpdateTilesToCurrentPile( 170 const Region& layer_invalidation, 171 const gfx::Size& new_layer_bounds) { 172 DCHECK(!new_layer_bounds.IsEmpty()); 173 174 gfx::Size tile_size = tiling_data_.max_texture_size(); 175 176 if (new_layer_bounds != layer_bounds_) { 177 gfx::Size content_bounds = 178 gfx::ToCeiledSize(gfx::ScaleSize(new_layer_bounds, contents_scale_)); 179 180 tile_size = client_->CalculateTileSize(content_bounds); 181 if (tile_size.IsEmpty()) { 182 layer_bounds_ = gfx::Size(); 183 content_bounds = gfx::Size(); 184 } else { 185 layer_bounds_ = new_layer_bounds; 186 } 187 188 // The SetLiveTilesRect() method would drop tiles outside the new bounds, 189 // but may do so incorrectly if resizing the tiling causes the number of 190 // tiles in the tiling_data_ to change. 191 gfx::Rect content_rect(content_bounds); 192 int before_left = tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.x()); 193 int before_top = tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.y()); 194 int before_right = 195 tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1); 196 int before_bottom = 197 tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1); 198 199 // The live_tiles_rect_ is clamped to stay within the tiling size as we 200 // change it. 201 live_tiles_rect_.Intersect(content_rect); 202 tiling_data_.SetTilingSize(content_bounds); 203 204 int after_right = -1; 205 int after_bottom = -1; 206 if (!live_tiles_rect_.IsEmpty()) { 207 after_right = 208 tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1); 209 after_bottom = 210 tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1); 211 } 212 213 // There is no recycled twin since this is run on the pending tiling. 214 PictureLayerTiling* recycled_twin = NULL; 215 DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this)); 216 DCHECK_EQ(PENDING_TREE, client_->GetTree()); 217 218 // Drop tiles outside the new layer bounds if the layer shrank. 219 for (int i = after_right + 1; i <= before_right; ++i) { 220 for (int j = before_top; j <= before_bottom; ++j) 221 RemoveTileAt(i, j, recycled_twin); 222 } 223 for (int i = before_left; i <= after_right; ++i) { 224 for (int j = after_bottom + 1; j <= before_bottom; ++j) 225 RemoveTileAt(i, j, recycled_twin); 226 } 227 228 // If the layer grew, the live_tiles_rect_ is not changed, but a new row 229 // and/or column of tiles may now exist inside the same live_tiles_rect_. 230 const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this); 231 if (after_right > before_right) { 232 DCHECK_EQ(after_right, before_right + 1); 233 for (int j = before_top; j <= after_bottom; ++j) 234 CreateTile(after_right, j, twin_tiling); 235 } 236 if (after_bottom > before_bottom) { 237 DCHECK_EQ(after_bottom, before_bottom + 1); 238 for (int i = before_left; i <= before_right; ++i) 239 CreateTile(i, after_bottom, twin_tiling); 240 } 241 } 242 243 if (tile_size != tiling_data_.max_texture_size()) { 244 tiling_data_.SetMaxTextureSize(tile_size); 245 // When the tile size changes, the TilingData positions no longer work 246 // as valid keys to the TileMap, so just drop all tiles. 247 Reset(); 248 } else { 249 Invalidate(layer_invalidation); 250 } 251 252 PicturePileImpl* pile = client_->GetPile(); 253 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) 254 it->second->set_picture_pile(pile); 255 VerifyLiveTilesRect(); 256 } 257 258 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) { 259 bool recreate_invalidated_tiles = false; 260 DoInvalidate(layer_region, recreate_invalidated_tiles); 261 } 262 263 void PictureLayerTiling::Invalidate(const Region& layer_region) { 264 bool recreate_invalidated_tiles = true; 265 DoInvalidate(layer_region, recreate_invalidated_tiles); 266 } 267 268 void PictureLayerTiling::DoInvalidate(const Region& layer_region, 269 bool recreate_invalidated_tiles) { 270 std::vector<TileMapKey> new_tile_keys; 271 gfx::Rect expanded_live_tiles_rect = 272 tiling_data_.ExpandRectIgnoringBordersToTileBounds(live_tiles_rect_); 273 for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) { 274 gfx::Rect layer_rect = iter.rect(); 275 gfx::Rect content_rect = 276 gfx::ScaleToEnclosingRect(layer_rect, contents_scale_); 277 // Consider tiles inside the live tiles rect even if only their border 278 // pixels intersect the invalidation. But don't consider tiles outside 279 // the live tiles rect with the same conditions, as they won't exist. 280 int border_pixels = tiling_data_.border_texels(); 281 content_rect.Inset(-border_pixels, -border_pixels); 282 // Avoid needless work by not bothering to invalidate where there aren't 283 // tiles. 284 content_rect.Intersect(expanded_live_tiles_rect); 285 if (content_rect.IsEmpty()) 286 continue; 287 // Since the content_rect includes border pixels already, don't include 288 // borders when iterating to avoid double counting them. 289 bool include_borders = false; 290 for (TilingData::Iterator iter( 291 &tiling_data_, content_rect, include_borders); 292 iter; 293 ++iter) { 294 // There is no recycled twin since this is run on the pending tiling. 295 PictureLayerTiling* recycled_twin = NULL; 296 DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this)); 297 DCHECK_EQ(PENDING_TREE, client_->GetTree()); 298 if (RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin)) 299 new_tile_keys.push_back(iter.index()); 300 } 301 } 302 303 if (recreate_invalidated_tiles && !new_tile_keys.empty()) { 304 for (size_t i = 0; i < new_tile_keys.size(); ++i) { 305 // Don't try to share a tile with the twin layer, it's been invalidated so 306 // we have to make our own tile here. 307 const PictureLayerTiling* twin_tiling = NULL; 308 CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling); 309 } 310 } 311 } 312 313 PictureLayerTiling::CoverageIterator::CoverageIterator() 314 : tiling_(NULL), 315 current_tile_(NULL), 316 tile_i_(0), 317 tile_j_(0), 318 left_(0), 319 top_(0), 320 right_(-1), 321 bottom_(-1) { 322 } 323 324 PictureLayerTiling::CoverageIterator::CoverageIterator( 325 const PictureLayerTiling* tiling, 326 float dest_scale, 327 const gfx::Rect& dest_rect) 328 : tiling_(tiling), 329 dest_rect_(dest_rect), 330 dest_to_content_scale_(0), 331 current_tile_(NULL), 332 tile_i_(0), 333 tile_j_(0), 334 left_(0), 335 top_(0), 336 right_(-1), 337 bottom_(-1) { 338 DCHECK(tiling_); 339 if (dest_rect_.IsEmpty()) 340 return; 341 342 dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale; 343 344 gfx::Rect content_rect = 345 gfx::ScaleToEnclosingRect(dest_rect_, 346 dest_to_content_scale_, 347 dest_to_content_scale_); 348 // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to 349 // check for non-intersection first. 350 content_rect.Intersect(gfx::Rect(tiling_->tiling_size())); 351 if (content_rect.IsEmpty()) 352 return; 353 354 left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x()); 355 top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y()); 356 right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord( 357 content_rect.right() - 1); 358 bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord( 359 content_rect.bottom() - 1); 360 361 tile_i_ = left_ - 1; 362 tile_j_ = top_; 363 ++(*this); 364 } 365 366 PictureLayerTiling::CoverageIterator::~CoverageIterator() { 367 } 368 369 PictureLayerTiling::CoverageIterator& 370 PictureLayerTiling::CoverageIterator::operator++() { 371 if (tile_j_ > bottom_) 372 return *this; 373 374 bool first_time = tile_i_ < left_; 375 bool new_row = false; 376 tile_i_++; 377 if (tile_i_ > right_) { 378 tile_i_ = left_; 379 tile_j_++; 380 new_row = true; 381 if (tile_j_ > bottom_) { 382 current_tile_ = NULL; 383 return *this; 384 } 385 } 386 387 current_tile_ = tiling_->TileAt(tile_i_, tile_j_); 388 389 // Calculate the current geometry rect. Due to floating point rounding 390 // and ToEnclosingRect, tiles might overlap in destination space on the 391 // edges. 392 gfx::Rect last_geometry_rect = current_geometry_rect_; 393 394 gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_); 395 396 current_geometry_rect_ = 397 gfx::ScaleToEnclosingRect(content_rect, 398 1 / dest_to_content_scale_, 399 1 / dest_to_content_scale_); 400 401 current_geometry_rect_.Intersect(dest_rect_); 402 403 if (first_time) 404 return *this; 405 406 // Iteration happens left->right, top->bottom. Running off the bottom-right 407 // edge is handled by the intersection above with dest_rect_. Here we make 408 // sure that the new current geometry rect doesn't overlap with the last. 409 int min_left; 410 int min_top; 411 if (new_row) { 412 min_left = dest_rect_.x(); 413 min_top = last_geometry_rect.bottom(); 414 } else { 415 min_left = last_geometry_rect.right(); 416 min_top = last_geometry_rect.y(); 417 } 418 419 int inset_left = std::max(0, min_left - current_geometry_rect_.x()); 420 int inset_top = std::max(0, min_top - current_geometry_rect_.y()); 421 current_geometry_rect_.Inset(inset_left, inset_top, 0, 0); 422 423 if (!new_row) { 424 DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x()); 425 DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom()); 426 DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y()); 427 } 428 429 return *this; 430 } 431 432 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const { 433 return current_geometry_rect_; 434 } 435 436 gfx::Rect 437 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const { 438 gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_); 439 rect.set_size(tiling_->tiling_data_.max_texture_size()); 440 return rect; 441 } 442 443 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const { 444 gfx::PointF tex_origin = 445 tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin(); 446 447 // Convert from dest space => content space => texture space. 448 gfx::RectF texture_rect(current_geometry_rect_); 449 texture_rect.Scale(dest_to_content_scale_, 450 dest_to_content_scale_); 451 texture_rect.Intersect(gfx::Rect(tiling_->tiling_size())); 452 if (texture_rect.IsEmpty()) 453 return texture_rect; 454 texture_rect.Offset(-tex_origin.OffsetFromOrigin()); 455 456 return texture_rect; 457 } 458 459 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const { 460 return tiling_->tiling_data_.max_texture_size(); 461 } 462 463 bool PictureLayerTiling::RemoveTileAt(int i, 464 int j, 465 PictureLayerTiling* recycled_twin) { 466 TileMap::iterator found = tiles_.find(TileMapKey(i, j)); 467 if (found == tiles_.end()) 468 return false; 469 ReleaseTile(found->second.get(), client_->GetTree()); 470 tiles_.erase(found); 471 if (recycled_twin) { 472 // Recycled twin does not also have a recycled twin, so pass NULL. 473 recycled_twin->RemoveTileAt(i, j, NULL); 474 } 475 return true; 476 } 477 478 void PictureLayerTiling::Reset() { 479 live_tiles_rect_ = gfx::Rect(); 480 PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this); 481 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 482 ReleaseTile(it->second.get(), client_->GetTree()); 483 if (recycled_twin) 484 recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL); 485 } 486 tiles_.clear(); 487 } 488 489 gfx::Rect PictureLayerTiling::ComputeSkewport( 490 double current_frame_time_in_seconds, 491 const gfx::Rect& visible_rect_in_content_space) const { 492 gfx::Rect skewport = visible_rect_in_content_space; 493 if (last_impl_frame_time_in_seconds_ == 0.0) 494 return skewport; 495 496 double time_delta = 497 current_frame_time_in_seconds - last_impl_frame_time_in_seconds_; 498 if (time_delta == 0.0) 499 return skewport; 500 501 float skewport_target_time_in_seconds = 502 client_->GetSkewportTargetTimeInSeconds(); 503 double extrapolation_multiplier = 504 skewport_target_time_in_seconds / time_delta; 505 506 int old_x = last_visible_rect_in_content_space_.x(); 507 int old_y = last_visible_rect_in_content_space_.y(); 508 int old_right = last_visible_rect_in_content_space_.right(); 509 int old_bottom = last_visible_rect_in_content_space_.bottom(); 510 511 int new_x = visible_rect_in_content_space.x(); 512 int new_y = visible_rect_in_content_space.y(); 513 int new_right = visible_rect_in_content_space.right(); 514 int new_bottom = visible_rect_in_content_space.bottom(); 515 516 int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels(); 517 518 // Compute the maximum skewport based on |skewport_limit|. 519 gfx::Rect max_skewport = skewport; 520 max_skewport.Inset( 521 -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit); 522 523 // Inset the skewport by the needed adjustment. 524 skewport.Inset(extrapolation_multiplier * (new_x - old_x), 525 extrapolation_multiplier * (new_y - old_y), 526 extrapolation_multiplier * (old_right - new_right), 527 extrapolation_multiplier * (old_bottom - new_bottom)); 528 529 // Clip the skewport to |max_skewport|. 530 skewport.Intersect(max_skewport); 531 532 // Finally, ensure that visible rect is contained in the skewport. 533 skewport.Union(visible_rect_in_content_space); 534 return skewport; 535 } 536 537 void PictureLayerTiling::UpdateTilePriorities( 538 WhichTree tree, 539 const gfx::Rect& viewport_in_layer_space, 540 float ideal_contents_scale, 541 double current_frame_time_in_seconds, 542 const Occlusion& occlusion_in_layer_space) { 543 if (!NeedsUpdateForFrameAtTimeAndViewport(current_frame_time_in_seconds, 544 viewport_in_layer_space)) { 545 // This should never be zero for the purposes of has_ever_been_updated(). 546 DCHECK_NE(current_frame_time_in_seconds, 0.0); 547 return; 548 } 549 550 gfx::Rect visible_rect_in_content_space = 551 gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_); 552 553 if (tiling_size().IsEmpty()) { 554 last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds; 555 last_viewport_in_layer_space_ = viewport_in_layer_space; 556 last_visible_rect_in_content_space_ = visible_rect_in_content_space; 557 return; 558 } 559 560 size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea(); 561 562 gfx::Size tile_size = tiling_data_.max_texture_size(); 563 int64 eventually_rect_area = 564 max_tiles_for_interest_area * tile_size.width() * tile_size.height(); 565 566 gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds, 567 visible_rect_in_content_space); 568 DCHECK(skewport.Contains(visible_rect_in_content_space)); 569 570 gfx::Rect eventually_rect = 571 ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space, 572 eventually_rect_area, 573 gfx::Rect(tiling_size()), 574 &expansion_cache_); 575 576 DCHECK(eventually_rect.IsEmpty() || 577 gfx::Rect(tiling_size()).Contains(eventually_rect)) 578 << "tiling_size: " << tiling_size().ToString() 579 << " eventually_rect: " << eventually_rect.ToString(); 580 581 SetLiveTilesRect(eventually_rect); 582 583 last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds; 584 last_viewport_in_layer_space_ = viewport_in_layer_space; 585 last_visible_rect_in_content_space_ = visible_rect_in_content_space; 586 587 eviction_tiles_cache_valid_ = false; 588 589 TilePriority now_priority(resolution_, TilePriority::NOW, 0); 590 float content_to_screen_scale = ideal_contents_scale / contents_scale_; 591 592 // Assign now priority to all visible tiles. 593 bool include_borders = false; 594 has_visible_rect_tiles_ = false; 595 for (TilingData::Iterator iter( 596 &tiling_data_, visible_rect_in_content_space, include_borders); 597 iter; 598 ++iter) { 599 TileMap::iterator find = tiles_.find(iter.index()); 600 if (find == tiles_.end()) 601 continue; 602 has_visible_rect_tiles_ = true; 603 Tile* tile = find->second.get(); 604 605 tile->SetPriority(tree, now_priority); 606 607 // Set whether tile is occluded or not. 608 gfx::Rect tile_query_rect = ScaleToEnclosingRect( 609 IntersectRects(tile->content_rect(), visible_rect_in_content_space), 610 1.0f / contents_scale_); 611 bool is_occluded = occlusion_in_layer_space.IsOccluded(tile_query_rect); 612 tile->set_is_occluded(tree, is_occluded); 613 } 614 615 // Assign soon priority to skewport tiles. 616 has_skewport_rect_tiles_ = false; 617 for (TilingData::DifferenceIterator iter( 618 &tiling_data_, skewport, visible_rect_in_content_space); 619 iter; 620 ++iter) { 621 TileMap::iterator find = tiles_.find(iter.index()); 622 if (find == tiles_.end()) 623 continue; 624 has_skewport_rect_tiles_ = true; 625 Tile* tile = find->second.get(); 626 627 gfx::Rect tile_bounds = 628 tiling_data_.TileBounds(iter.index_x(), iter.index_y()); 629 630 float distance_to_visible = 631 visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) * 632 content_to_screen_scale; 633 634 TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible); 635 tile->SetPriority(tree, priority); 636 } 637 638 // Assign eventually priority to interest rect tiles. 639 has_eventually_rect_tiles_ = false; 640 for (TilingData::DifferenceIterator iter( 641 &tiling_data_, eventually_rect, skewport); 642 iter; 643 ++iter) { 644 TileMap::iterator find = tiles_.find(iter.index()); 645 if (find == tiles_.end()) 646 continue; 647 has_eventually_rect_tiles_ = true; 648 Tile* tile = find->second.get(); 649 650 gfx::Rect tile_bounds = 651 tiling_data_.TileBounds(iter.index_x(), iter.index_y()); 652 653 float distance_to_visible = 654 visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) * 655 content_to_screen_scale; 656 TilePriority priority( 657 resolution_, TilePriority::EVENTUALLY, distance_to_visible); 658 tile->SetPriority(tree, priority); 659 } 660 661 // Upgrade the priority on border tiles to be SOON. 662 gfx::Rect soon_border_rect = visible_rect_in_content_space; 663 float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale; 664 soon_border_rect.Inset(-border, -border, -border, -border); 665 has_soon_border_rect_tiles_ = false; 666 for (TilingData::DifferenceIterator iter( 667 &tiling_data_, soon_border_rect, skewport); 668 iter; 669 ++iter) { 670 TileMap::iterator find = tiles_.find(iter.index()); 671 if (find == tiles_.end()) 672 continue; 673 has_soon_border_rect_tiles_ = true; 674 Tile* tile = find->second.get(); 675 676 TilePriority priority(resolution_, 677 TilePriority::SOON, 678 tile->priority(tree).distance_to_visible); 679 tile->SetPriority(tree, priority); 680 } 681 682 // Update iteration rects. 683 current_visible_rect_ = visible_rect_in_content_space; 684 current_skewport_rect_ = skewport; 685 current_soon_border_rect_ = soon_border_rect; 686 current_eventually_rect_ = eventually_rect; 687 } 688 689 void PictureLayerTiling::SetLiveTilesRect( 690 const gfx::Rect& new_live_tiles_rect) { 691 DCHECK(new_live_tiles_rect.IsEmpty() || 692 gfx::Rect(tiling_size()).Contains(new_live_tiles_rect)) 693 << "tiling_size: " << tiling_size().ToString() 694 << " new_live_tiles_rect: " << new_live_tiles_rect.ToString(); 695 if (live_tiles_rect_ == new_live_tiles_rect) 696 return; 697 698 // Iterate to delete all tiles outside of our new live_tiles rect. 699 PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this); 700 for (TilingData::DifferenceIterator iter(&tiling_data_, 701 live_tiles_rect_, 702 new_live_tiles_rect); 703 iter; 704 ++iter) { 705 RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin); 706 } 707 708 const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this); 709 710 // Iterate to allocate new tiles for all regions with newly exposed area. 711 for (TilingData::DifferenceIterator iter(&tiling_data_, 712 new_live_tiles_rect, 713 live_tiles_rect_); 714 iter; 715 ++iter) { 716 TileMapKey key(iter.index()); 717 CreateTile(key.first, key.second, twin_tiling); 718 } 719 720 live_tiles_rect_ = new_live_tiles_rect; 721 VerifyLiveTilesRect(); 722 } 723 724 void PictureLayerTiling::VerifyLiveTilesRect() { 725 #if DCHECK_IS_ON 726 for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 727 if (!it->second.get()) 728 continue; 729 DCHECK(it->first.first < tiling_data_.num_tiles_x()) 730 << this << " " << it->first.first << "," << it->first.second 731 << " num_tiles_x " << tiling_data_.num_tiles_x() << " live_tiles_rect " 732 << live_tiles_rect_.ToString(); 733 DCHECK(it->first.second < tiling_data_.num_tiles_y()) 734 << this << " " << it->first.first << "," << it->first.second 735 << " num_tiles_y " << tiling_data_.num_tiles_y() << " live_tiles_rect " 736 << live_tiles_rect_.ToString(); 737 DCHECK(tiling_data_.TileBounds(it->first.first, it->first.second) 738 .Intersects(live_tiles_rect_)) 739 << this << " " << it->first.first << "," << it->first.second 740 << " tile bounds " 741 << tiling_data_.TileBounds(it->first.first, it->first.second).ToString() 742 << " live_tiles_rect " << live_tiles_rect_.ToString(); 743 } 744 #endif 745 } 746 747 void PictureLayerTiling::DidBecomeRecycled() { 748 // DidBecomeActive below will set the active priority for tiles that are 749 // still in the tree. Calling this first on an active tiling that is becoming 750 // recycled takes care of tiles that are no longer in the active tree (eg. 751 // due to a pending invalidation). 752 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 753 it->second->SetPriority(ACTIVE_TREE, TilePriority()); 754 } 755 } 756 757 void PictureLayerTiling::DidBecomeActive() { 758 PicturePileImpl* active_pile = client_->GetPile(); 759 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 760 it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE)); 761 it->second->SetPriority(PENDING_TREE, TilePriority()); 762 763 // Tile holds a ref onto a picture pile. If the tile never gets invalidated 764 // and recreated, then that picture pile ref could exist indefinitely. To 765 // prevent this, ask the client to update the pile to its own ref. This 766 // will cause PicturePileImpls to get deleted once the corresponding 767 // PictureLayerImpl and any in flight raster jobs go out of scope. 768 it->second->set_picture_pile(active_pile); 769 } 770 } 771 772 void PictureLayerTiling::GetAllTilesForTracing( 773 std::set<const Tile*>* tiles) const { 774 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) 775 tiles->insert(it->second.get()); 776 } 777 778 void PictureLayerTiling::AsValueInto(base::debug::TracedValue* state) const { 779 state->SetInteger("num_tiles", tiles_.size()); 780 state->SetDouble("content_scale", contents_scale_); 781 state->BeginDictionary("tiling_size"); 782 MathUtil::AddToTracedValue(tiling_size(), state); 783 state->EndDictionary(); 784 } 785 786 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const { 787 size_t amount = 0; 788 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 789 const Tile* tile = it->second.get(); 790 amount += tile->GPUMemoryUsageInBytes(); 791 } 792 return amount; 793 } 794 795 PictureLayerTiling::RectExpansionCache::RectExpansionCache() 796 : previous_target(0) { 797 } 798 799 namespace { 800 801 // This struct represents an event at which the expending rect intersects 802 // one of its boundaries. 4 intersection events will occur during expansion. 803 struct EdgeEvent { 804 enum { BOTTOM, TOP, LEFT, RIGHT } edge; 805 int* num_edges; 806 int distance; 807 }; 808 809 // Compute the delta to expand from edges to cover target_area. 810 int ComputeExpansionDelta(int num_x_edges, int num_y_edges, 811 int width, int height, 812 int64 target_area) { 813 // Compute coefficients for the quadratic equation: 814 // a*x^2 + b*x + c = 0 815 int a = num_y_edges * num_x_edges; 816 int b = num_y_edges * width + num_x_edges * height; 817 int64 c = static_cast<int64>(width) * height - target_area; 818 819 // Compute the delta for our edges using the quadratic equation. 820 int delta = 821 (a == 0) ? -c / b : (-b + static_cast<int>(std::sqrt( 822 static_cast<int64>(b) * b - 4.0 * a * c))) / 823 (2 * a); 824 return std::max(0, delta); 825 } 826 827 } // namespace 828 829 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy( 830 const gfx::Rect& starting_rect, 831 int64 target_area, 832 const gfx::Rect& bounding_rect, 833 RectExpansionCache* cache) { 834 if (starting_rect.IsEmpty()) 835 return starting_rect; 836 837 if (cache && 838 cache->previous_start == starting_rect && 839 cache->previous_bounds == bounding_rect && 840 cache->previous_target == target_area) 841 return cache->previous_result; 842 843 if (cache) { 844 cache->previous_start = starting_rect; 845 cache->previous_bounds = bounding_rect; 846 cache->previous_target = target_area; 847 } 848 849 DCHECK(!bounding_rect.IsEmpty()); 850 DCHECK_GT(target_area, 0); 851 852 // Expand the starting rect to cover target_area, if it is smaller than it. 853 int delta = ComputeExpansionDelta( 854 2, 2, starting_rect.width(), starting_rect.height(), target_area); 855 gfx::Rect expanded_starting_rect = starting_rect; 856 if (delta > 0) 857 expanded_starting_rect.Inset(-delta, -delta); 858 859 gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect); 860 if (rect.IsEmpty()) { 861 // The starting_rect and bounding_rect are far away. 862 if (cache) 863 cache->previous_result = rect; 864 return rect; 865 } 866 if (delta >= 0 && rect == expanded_starting_rect) { 867 // The starting rect already covers the entire bounding_rect and isn't too 868 // large for the target_area. 869 if (cache) 870 cache->previous_result = rect; 871 return rect; 872 } 873 874 // Continue to expand/shrink rect to let it cover target_area. 875 876 // These values will be updated by the loop and uses as the output. 877 int origin_x = rect.x(); 878 int origin_y = rect.y(); 879 int width = rect.width(); 880 int height = rect.height(); 881 882 // In the beginning we will consider 2 edges in each dimension. 883 int num_y_edges = 2; 884 int num_x_edges = 2; 885 886 // Create an event list. 887 EdgeEvent events[] = { 888 { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() }, 889 { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() }, 890 { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() }, 891 { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() } 892 }; 893 894 // Sort the events by distance (closest first). 895 if (events[0].distance > events[1].distance) std::swap(events[0], events[1]); 896 if (events[2].distance > events[3].distance) std::swap(events[2], events[3]); 897 if (events[0].distance > events[2].distance) std::swap(events[0], events[2]); 898 if (events[1].distance > events[3].distance) std::swap(events[1], events[3]); 899 if (events[1].distance > events[2].distance) std::swap(events[1], events[2]); 900 901 for (int event_index = 0; event_index < 4; event_index++) { 902 const EdgeEvent& event = events[event_index]; 903 904 int delta = ComputeExpansionDelta( 905 num_x_edges, num_y_edges, width, height, target_area); 906 907 // Clamp delta to our event distance. 908 if (delta > event.distance) 909 delta = event.distance; 910 911 // Adjust the edge count for this kind of edge. 912 --*event.num_edges; 913 914 // Apply the delta to the edges and edge events. 915 for (int i = event_index; i < 4; i++) { 916 switch (events[i].edge) { 917 case EdgeEvent::BOTTOM: 918 origin_y -= delta; 919 height += delta; 920 break; 921 case EdgeEvent::TOP: 922 height += delta; 923 break; 924 case EdgeEvent::LEFT: 925 origin_x -= delta; 926 width += delta; 927 break; 928 case EdgeEvent::RIGHT: 929 width += delta; 930 break; 931 } 932 events[i].distance -= delta; 933 } 934 935 // If our delta is less then our event distance, we're done. 936 if (delta < event.distance) 937 break; 938 } 939 940 gfx::Rect result(origin_x, origin_y, width, height); 941 if (cache) 942 cache->previous_result = result; 943 return result; 944 } 945 946 void PictureLayerTiling::UpdateEvictionCacheIfNeeded( 947 TreePriority tree_priority) { 948 if (eviction_tiles_cache_valid_ && 949 eviction_cache_tree_priority_ == tree_priority) 950 return; 951 952 eviction_tiles_now_.clear(); 953 eviction_tiles_now_and_required_for_activation_.clear(); 954 eviction_tiles_soon_.clear(); 955 eviction_tiles_soon_and_required_for_activation_.clear(); 956 eviction_tiles_eventually_.clear(); 957 eviction_tiles_eventually_and_required_for_activation_.clear(); 958 959 for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 960 // TODO(vmpstr): This should update the priority if UpdateTilePriorities 961 // changes not to do this. 962 Tile* tile = it->second.get(); 963 const TilePriority& priority = 964 tile->priority_for_tree_priority(tree_priority); 965 switch (priority.priority_bin) { 966 case TilePriority::EVENTUALLY: 967 if (tile->required_for_activation()) 968 eviction_tiles_eventually_and_required_for_activation_.push_back( 969 tile); 970 else 971 eviction_tiles_eventually_.push_back(tile); 972 break; 973 case TilePriority::SOON: 974 if (tile->required_for_activation()) 975 eviction_tiles_soon_and_required_for_activation_.push_back(tile); 976 else 977 eviction_tiles_soon_.push_back(tile); 978 break; 979 case TilePriority::NOW: 980 if (tile->required_for_activation()) 981 eviction_tiles_now_and_required_for_activation_.push_back(tile); 982 else 983 eviction_tiles_now_.push_back(tile); 984 break; 985 } 986 } 987 988 // TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that 989 // can be updated for each of the queues. 990 TileEvictionOrder sort_order(tree_priority); 991 std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order); 992 std::sort(eviction_tiles_now_and_required_for_activation_.begin(), 993 eviction_tiles_now_and_required_for_activation_.end(), 994 sort_order); 995 std::sort( 996 eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order); 997 std::sort(eviction_tiles_soon_and_required_for_activation_.begin(), 998 eviction_tiles_soon_and_required_for_activation_.end(), 999 sort_order); 1000 std::sort(eviction_tiles_eventually_.begin(), 1001 eviction_tiles_eventually_.end(), 1002 sort_order); 1003 std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(), 1004 eviction_tiles_eventually_and_required_for_activation_.end(), 1005 sort_order); 1006 1007 eviction_tiles_cache_valid_ = true; 1008 eviction_cache_tree_priority_ = tree_priority; 1009 } 1010 1011 const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles( 1012 TreePriority tree_priority, 1013 EvictionCategory category) { 1014 UpdateEvictionCacheIfNeeded(tree_priority); 1015 switch (category) { 1016 case EVENTUALLY: 1017 return &eviction_tiles_eventually_; 1018 case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION: 1019 return &eviction_tiles_eventually_and_required_for_activation_; 1020 case SOON: 1021 return &eviction_tiles_soon_; 1022 case SOON_AND_REQUIRED_FOR_ACTIVATION: 1023 return &eviction_tiles_soon_and_required_for_activation_; 1024 case NOW: 1025 return &eviction_tiles_now_; 1026 case NOW_AND_REQUIRED_FOR_ACTIVATION: 1027 return &eviction_tiles_now_and_required_for_activation_; 1028 } 1029 NOTREACHED(); 1030 return &eviction_tiles_eventually_; 1031 } 1032 1033 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator() 1034 : tiling_(NULL), current_tile_(NULL) {} 1035 1036 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator( 1037 PictureLayerTiling* tiling, 1038 WhichTree tree) 1039 : tiling_(tiling), phase_(VISIBLE_RECT), tree_(tree), current_tile_(NULL) { 1040 if (!tiling_->has_visible_rect_tiles_) { 1041 AdvancePhase(); 1042 return; 1043 } 1044 1045 visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_, 1046 tiling_->current_visible_rect_, 1047 false /* include_borders */); 1048 if (!visible_iterator_) { 1049 AdvancePhase(); 1050 return; 1051 } 1052 1053 current_tile_ = 1054 tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y()); 1055 if (!current_tile_ || !TileNeedsRaster(current_tile_)) 1056 ++(*this); 1057 } 1058 1059 PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {} 1060 1061 void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() { 1062 DCHECK_LT(phase_, EVENTUALLY_RECT); 1063 1064 do { 1065 phase_ = static_cast<Phase>(phase_ + 1); 1066 switch (phase_) { 1067 case VISIBLE_RECT: 1068 NOTREACHED(); 1069 return; 1070 case SKEWPORT_RECT: 1071 if (!tiling_->has_skewport_rect_tiles_) 1072 continue; 1073 1074 spiral_iterator_ = TilingData::SpiralDifferenceIterator( 1075 &tiling_->tiling_data_, 1076 tiling_->current_skewport_rect_, 1077 tiling_->current_visible_rect_, 1078 tiling_->current_visible_rect_); 1079 break; 1080 case SOON_BORDER_RECT: 1081 if (!tiling_->has_soon_border_rect_tiles_) 1082 continue; 1083 1084 spiral_iterator_ = TilingData::SpiralDifferenceIterator( 1085 &tiling_->tiling_data_, 1086 tiling_->current_soon_border_rect_, 1087 tiling_->current_skewport_rect_, 1088 tiling_->current_visible_rect_); 1089 break; 1090 case EVENTUALLY_RECT: 1091 if (!tiling_->has_eventually_rect_tiles_) { 1092 current_tile_ = NULL; 1093 return; 1094 } 1095 1096 spiral_iterator_ = TilingData::SpiralDifferenceIterator( 1097 &tiling_->tiling_data_, 1098 tiling_->current_eventually_rect_, 1099 tiling_->current_skewport_rect_, 1100 tiling_->current_soon_border_rect_); 1101 break; 1102 } 1103 1104 while (spiral_iterator_) { 1105 current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(), 1106 spiral_iterator_.index_y()); 1107 if (current_tile_ && TileNeedsRaster(current_tile_)) 1108 break; 1109 ++spiral_iterator_; 1110 } 1111 1112 if (!spiral_iterator_ && phase_ == EVENTUALLY_RECT) { 1113 current_tile_ = NULL; 1114 break; 1115 } 1116 } while (!spiral_iterator_); 1117 } 1118 1119 PictureLayerTiling::TilingRasterTileIterator& 1120 PictureLayerTiling::TilingRasterTileIterator:: 1121 operator++() { 1122 current_tile_ = NULL; 1123 while (!current_tile_ || !TileNeedsRaster(current_tile_)) { 1124 std::pair<int, int> next_index; 1125 switch (phase_) { 1126 case VISIBLE_RECT: 1127 ++visible_iterator_; 1128 if (!visible_iterator_) { 1129 AdvancePhase(); 1130 return *this; 1131 } 1132 next_index = visible_iterator_.index(); 1133 break; 1134 case SKEWPORT_RECT: 1135 case SOON_BORDER_RECT: 1136 ++spiral_iterator_; 1137 if (!spiral_iterator_) { 1138 AdvancePhase(); 1139 return *this; 1140 } 1141 next_index = spiral_iterator_.index(); 1142 break; 1143 case EVENTUALLY_RECT: 1144 ++spiral_iterator_; 1145 if (!spiral_iterator_) { 1146 current_tile_ = NULL; 1147 return *this; 1148 } 1149 next_index = spiral_iterator_.index(); 1150 break; 1151 } 1152 current_tile_ = tiling_->TileAt(next_index.first, next_index.second); 1153 } 1154 return *this; 1155 } 1156 1157 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator() 1158 : eviction_tiles_(NULL), current_eviction_tiles_index_(0u) { 1159 } 1160 1161 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator( 1162 PictureLayerTiling* tiling, 1163 TreePriority tree_priority, 1164 EvictionCategory category) 1165 : eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)), 1166 // Note: initializing to "0 - 1" works as overflow is well defined for 1167 // unsigned integers. 1168 current_eviction_tiles_index_(static_cast<size_t>(0) - 1) { 1169 DCHECK(eviction_tiles_); 1170 ++(*this); 1171 } 1172 1173 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() { 1174 } 1175 1176 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const { 1177 return eviction_tiles_ && 1178 current_eviction_tiles_index_ != eviction_tiles_->size(); 1179 } 1180 1181 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() { 1182 DCHECK(*this); 1183 return (*eviction_tiles_)[current_eviction_tiles_index_]; 1184 } 1185 1186 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const { 1187 DCHECK(*this); 1188 return (*eviction_tiles_)[current_eviction_tiles_index_]; 1189 } 1190 1191 PictureLayerTiling::TilingEvictionTileIterator& 1192 PictureLayerTiling::TilingEvictionTileIterator:: 1193 operator++() { 1194 DCHECK(*this); 1195 do { 1196 ++current_eviction_tiles_index_; 1197 } while (current_eviction_tiles_index_ != eviction_tiles_->size() && 1198 !(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources()); 1199 1200 return *this; 1201 } 1202 1203 } // namespace cc 1204
