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 "cc/base/math_util.h" 14 #include "cc/resources/tile.h" 15 #include "cc/resources/tile_priority.h" 16 #include "ui/gfx/point_conversions.h" 17 #include "ui/gfx/rect_conversions.h" 18 #include "ui/gfx/safe_integer_conversions.h" 19 #include "ui/gfx/size_conversions.h" 20 21 namespace cc { 22 namespace { 23 24 const float kSoonBorderDistanceInScreenPixels = 312.f; 25 26 class TileEvictionOrder { 27 public: 28 explicit TileEvictionOrder(TreePriority tree_priority) 29 : tree_priority_(tree_priority) {} 30 ~TileEvictionOrder() {} 31 32 bool operator()(const Tile* a, const Tile* b) { 33 const TilePriority& a_priority = 34 a->priority_for_tree_priority(tree_priority_); 35 const TilePriority& b_priority = 36 b->priority_for_tree_priority(tree_priority_); 37 38 if (a_priority.priority_bin == b_priority.priority_bin && 39 a->required_for_activation() != b->required_for_activation()) { 40 return b->required_for_activation(); 41 } 42 return b_priority.IsHigherPriorityThan(a_priority); 43 } 44 45 private: 46 TreePriority tree_priority_; 47 }; 48 } // namespace 49 50 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create( 51 float contents_scale, 52 const gfx::Size& layer_bounds, 53 PictureLayerTilingClient* client) { 54 return make_scoped_ptr(new PictureLayerTiling(contents_scale, 55 layer_bounds, 56 client)); 57 } 58 59 PictureLayerTiling::PictureLayerTiling(float contents_scale, 60 const gfx::Size& layer_bounds, 61 PictureLayerTilingClient* client) 62 : contents_scale_(contents_scale), 63 layer_bounds_(layer_bounds), 64 resolution_(NON_IDEAL_RESOLUTION), 65 client_(client), 66 tiling_data_(gfx::Size(), gfx::Rect(), true), 67 last_impl_frame_time_in_seconds_(0.0), 68 eviction_tiles_cache_valid_(false), 69 eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) { 70 gfx::Size content_bounds = 71 gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale)); 72 gfx::Size tile_size = client_->CalculateTileSize(content_bounds); 73 74 DCHECK(!gfx::ToFlooredSize( 75 gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) << 76 "Tiling created with scale too small as contents become empty." << 77 " Layer bounds: " << layer_bounds.ToString() << 78 " Contents scale: " << contents_scale; 79 80 tiling_data_.SetTilingRect(gfx::Rect(content_bounds)); 81 tiling_data_.SetMaxTextureSize(tile_size); 82 } 83 84 PictureLayerTiling::~PictureLayerTiling() { 85 } 86 87 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) { 88 client_ = client; 89 } 90 91 gfx::Rect PictureLayerTiling::TilingRect() const { 92 return tiling_data_.tiling_rect(); 93 } 94 95 Tile* PictureLayerTiling::CreateTile(int i, 96 int j, 97 const PictureLayerTiling* twin_tiling) { 98 TileMapKey key(i, j); 99 DCHECK(tiles_.find(key) == tiles_.end()); 100 101 gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j); 102 gfx::Rect tile_rect = paint_rect; 103 tile_rect.set_size(tiling_data_.max_texture_size()); 104 105 // Check our twin for a valid tile. 106 if (twin_tiling && 107 tiling_data_.max_texture_size() == 108 twin_tiling->tiling_data_.max_texture_size()) { 109 if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) { 110 gfx::Rect rect = 111 gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_); 112 if (!client_->GetInvalidation()->Intersects(rect)) { 113 tiles_[key] = candidate_tile; 114 return candidate_tile; 115 } 116 } 117 } 118 119 // Create a new tile because our twin didn't have a valid one. 120 scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect); 121 if (tile.get()) 122 tiles_[key] = tile; 123 return tile.get(); 124 } 125 126 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() { 127 const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this); 128 bool include_borders = true; 129 for (TilingData::Iterator iter( 130 &tiling_data_, live_tiles_rect_, include_borders); 131 iter; 132 ++iter) { 133 TileMapKey key = iter.index(); 134 TileMap::iterator find = tiles_.find(key); 135 if (find != tiles_.end()) 136 continue; 137 CreateTile(key.first, key.second, twin_tiling); 138 } 139 } 140 141 void PictureLayerTiling::SetLayerBounds(const gfx::Size& layer_bounds) { 142 if (layer_bounds_ == layer_bounds) 143 return; 144 145 DCHECK(!layer_bounds.IsEmpty()); 146 147 gfx::Size old_layer_bounds = layer_bounds_; 148 layer_bounds_ = layer_bounds; 149 gfx::Size content_bounds = 150 gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_)); 151 152 gfx::Size tile_size = client_->CalculateTileSize(content_bounds); 153 if (tile_size != tiling_data_.max_texture_size()) { 154 tiling_data_.SetTilingRect(gfx::Rect(content_bounds)); 155 tiling_data_.SetMaxTextureSize(tile_size); 156 Reset(); 157 return; 158 } 159 160 // Any tiles outside our new bounds are invalid and should be dropped. 161 gfx::Rect bounded_live_tiles_rect(live_tiles_rect_); 162 bounded_live_tiles_rect.Intersect(gfx::Rect(content_bounds)); 163 SetLiveTilesRect(bounded_live_tiles_rect); 164 tiling_data_.SetTilingRect(gfx::Rect(content_bounds)); 165 166 // Create tiles for newly exposed areas. 167 Region layer_region((gfx::Rect(layer_bounds_))); 168 layer_region.Subtract(gfx::Rect(old_layer_bounds)); 169 Invalidate(layer_region); 170 } 171 172 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) { 173 DoInvalidate(layer_region, false /* recreate_tiles */); 174 } 175 176 void PictureLayerTiling::Invalidate(const Region& layer_region) { 177 DoInvalidate(layer_region, true /* recreate_tiles */); 178 } 179 180 void PictureLayerTiling::DoInvalidate(const Region& layer_region, 181 bool recreate_tiles) { 182 std::vector<TileMapKey> new_tile_keys; 183 gfx::Rect expanded_live_tiles_rect( 184 tiling_data_.ExpandRectToTileBoundsWithBorders(live_tiles_rect_)); 185 for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) { 186 gfx::Rect layer_rect = iter.rect(); 187 gfx::Rect content_rect = 188 gfx::ScaleToEnclosingRect(layer_rect, contents_scale_); 189 // Avoid needless work by not bothering to invalidate where there aren't 190 // tiles. 191 content_rect.Intersect(expanded_live_tiles_rect); 192 if (content_rect.IsEmpty()) 193 continue; 194 bool include_borders = true; 195 for (TilingData::Iterator iter( 196 &tiling_data_, content_rect, include_borders); 197 iter; 198 ++iter) { 199 TileMapKey key(iter.index()); 200 TileMap::iterator find = tiles_.find(key); 201 if (find == tiles_.end()) 202 continue; 203 tiles_.erase(find); 204 if (recreate_tiles) 205 new_tile_keys.push_back(key); 206 } 207 } 208 209 if (recreate_tiles) { 210 const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this); 211 for (size_t i = 0; i < new_tile_keys.size(); ++i) 212 CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling); 213 } 214 } 215 216 PictureLayerTiling::CoverageIterator::CoverageIterator() 217 : tiling_(NULL), 218 current_tile_(NULL), 219 tile_i_(0), 220 tile_j_(0), 221 left_(0), 222 top_(0), 223 right_(-1), 224 bottom_(-1) { 225 } 226 227 PictureLayerTiling::CoverageIterator::CoverageIterator( 228 const PictureLayerTiling* tiling, 229 float dest_scale, 230 const gfx::Rect& dest_rect) 231 : tiling_(tiling), 232 dest_rect_(dest_rect), 233 dest_to_content_scale_(0), 234 current_tile_(NULL), 235 tile_i_(0), 236 tile_j_(0), 237 left_(0), 238 top_(0), 239 right_(-1), 240 bottom_(-1) { 241 DCHECK(tiling_); 242 if (dest_rect_.IsEmpty()) 243 return; 244 245 dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale; 246 247 gfx::Rect content_rect = 248 gfx::ScaleToEnclosingRect(dest_rect_, 249 dest_to_content_scale_, 250 dest_to_content_scale_); 251 // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to 252 // check for non-intersection first. 253 content_rect.Intersect(tiling_->TilingRect()); 254 if (content_rect.IsEmpty()) 255 return; 256 257 left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x()); 258 top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y()); 259 right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord( 260 content_rect.right() - 1); 261 bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord( 262 content_rect.bottom() - 1); 263 264 tile_i_ = left_ - 1; 265 tile_j_ = top_; 266 ++(*this); 267 } 268 269 PictureLayerTiling::CoverageIterator::~CoverageIterator() { 270 } 271 272 PictureLayerTiling::CoverageIterator& 273 PictureLayerTiling::CoverageIterator::operator++() { 274 if (tile_j_ > bottom_) 275 return *this; 276 277 bool first_time = tile_i_ < left_; 278 bool new_row = false; 279 tile_i_++; 280 if (tile_i_ > right_) { 281 tile_i_ = left_; 282 tile_j_++; 283 new_row = true; 284 if (tile_j_ > bottom_) { 285 current_tile_ = NULL; 286 return *this; 287 } 288 } 289 290 current_tile_ = tiling_->TileAt(tile_i_, tile_j_); 291 292 // Calculate the current geometry rect. Due to floating point rounding 293 // and ToEnclosingRect, tiles might overlap in destination space on the 294 // edges. 295 gfx::Rect last_geometry_rect = current_geometry_rect_; 296 297 gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_); 298 299 current_geometry_rect_ = 300 gfx::ScaleToEnclosingRect(content_rect, 301 1 / dest_to_content_scale_, 302 1 / dest_to_content_scale_); 303 304 current_geometry_rect_.Intersect(dest_rect_); 305 306 if (first_time) 307 return *this; 308 309 // Iteration happens left->right, top->bottom. Running off the bottom-right 310 // edge is handled by the intersection above with dest_rect_. Here we make 311 // sure that the new current geometry rect doesn't overlap with the last. 312 int min_left; 313 int min_top; 314 if (new_row) { 315 min_left = dest_rect_.x(); 316 min_top = last_geometry_rect.bottom(); 317 } else { 318 min_left = last_geometry_rect.right(); 319 min_top = last_geometry_rect.y(); 320 } 321 322 int inset_left = std::max(0, min_left - current_geometry_rect_.x()); 323 int inset_top = std::max(0, min_top - current_geometry_rect_.y()); 324 current_geometry_rect_.Inset(inset_left, inset_top, 0, 0); 325 326 if (!new_row) { 327 DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x()); 328 DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom()); 329 DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y()); 330 } 331 332 return *this; 333 } 334 335 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const { 336 return current_geometry_rect_; 337 } 338 339 gfx::Rect 340 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const { 341 gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_); 342 rect.set_size(tiling_->tiling_data_.max_texture_size()); 343 return rect; 344 } 345 346 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const { 347 gfx::PointF tex_origin = 348 tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin(); 349 350 // Convert from dest space => content space => texture space. 351 gfx::RectF texture_rect(current_geometry_rect_); 352 texture_rect.Scale(dest_to_content_scale_, 353 dest_to_content_scale_); 354 texture_rect.Intersect(tiling_->TilingRect()); 355 if (texture_rect.IsEmpty()) 356 return texture_rect; 357 texture_rect.Offset(-tex_origin.OffsetFromOrigin()); 358 359 return texture_rect; 360 } 361 362 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const { 363 return tiling_->tiling_data_.max_texture_size(); 364 } 365 366 void PictureLayerTiling::Reset() { 367 live_tiles_rect_ = gfx::Rect(); 368 tiles_.clear(); 369 } 370 371 gfx::Rect PictureLayerTiling::ComputeSkewport( 372 double current_frame_time_in_seconds, 373 const gfx::Rect& visible_rect_in_content_space) const { 374 gfx::Rect skewport = visible_rect_in_content_space; 375 if (last_impl_frame_time_in_seconds_ == 0.0) 376 return skewport; 377 378 double time_delta = 379 current_frame_time_in_seconds - last_impl_frame_time_in_seconds_; 380 if (time_delta == 0.0) 381 return skewport; 382 383 float skewport_target_time_in_seconds = 384 client_->GetSkewportTargetTimeInSeconds(); 385 double extrapolation_multiplier = 386 skewport_target_time_in_seconds / time_delta; 387 388 int old_x = last_visible_rect_in_content_space_.x(); 389 int old_y = last_visible_rect_in_content_space_.y(); 390 int old_right = last_visible_rect_in_content_space_.right(); 391 int old_bottom = last_visible_rect_in_content_space_.bottom(); 392 393 int new_x = visible_rect_in_content_space.x(); 394 int new_y = visible_rect_in_content_space.y(); 395 int new_right = visible_rect_in_content_space.right(); 396 int new_bottom = visible_rect_in_content_space.bottom(); 397 398 int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels(); 399 400 // Compute the maximum skewport based on |skewport_limit|. 401 gfx::Rect max_skewport = skewport; 402 max_skewport.Inset( 403 -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit); 404 405 // Inset the skewport by the needed adjustment. 406 skewport.Inset(extrapolation_multiplier * (new_x - old_x), 407 extrapolation_multiplier * (new_y - old_y), 408 extrapolation_multiplier * (old_right - new_right), 409 extrapolation_multiplier * (old_bottom - new_bottom)); 410 411 // Clip the skewport to |max_skewport|. 412 skewport.Intersect(max_skewport); 413 414 // Finally, ensure that visible rect is contained in the skewport. 415 skewport.Union(visible_rect_in_content_space); 416 return skewport; 417 } 418 419 void PictureLayerTiling::UpdateTilePriorities( 420 WhichTree tree, 421 const gfx::Rect& visible_layer_rect, 422 float layer_contents_scale, 423 double current_frame_time_in_seconds) { 424 if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) { 425 // This should never be zero for the purposes of has_ever_been_updated(). 426 DCHECK_NE(current_frame_time_in_seconds, 0.0); 427 return; 428 } 429 430 gfx::Rect visible_rect_in_content_space = 431 gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_); 432 433 if (TilingRect().IsEmpty()) { 434 last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds; 435 last_visible_rect_in_content_space_ = visible_rect_in_content_space; 436 return; 437 } 438 439 size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea(); 440 441 gfx::Size tile_size = tiling_data_.max_texture_size(); 442 int64 eventually_rect_area = 443 max_tiles_for_interest_area * tile_size.width() * tile_size.height(); 444 445 gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds, 446 visible_rect_in_content_space); 447 DCHECK(skewport.Contains(visible_rect_in_content_space)); 448 449 gfx::Rect eventually_rect = 450 ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space, 451 eventually_rect_area, 452 TilingRect(), 453 &expansion_cache_); 454 455 DCHECK(eventually_rect.IsEmpty() || TilingRect().Contains(eventually_rect)); 456 457 SetLiveTilesRect(eventually_rect); 458 459 last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds; 460 last_visible_rect_in_content_space_ = visible_rect_in_content_space; 461 462 current_visible_rect_in_content_space_ = visible_rect_in_content_space; 463 current_skewport_ = skewport; 464 current_eventually_rect_ = eventually_rect; 465 eviction_tiles_cache_valid_ = false; 466 467 TilePriority now_priority(resolution_, TilePriority::NOW, 0); 468 float content_to_screen_scale = layer_contents_scale / contents_scale_; 469 470 // Assign now priority to all visible tiles. 471 bool include_borders = true; 472 for (TilingData::Iterator iter( 473 &tiling_data_, visible_rect_in_content_space, include_borders); 474 iter; 475 ++iter) { 476 TileMap::iterator find = tiles_.find(iter.index()); 477 if (find == tiles_.end()) 478 continue; 479 Tile* tile = find->second.get(); 480 481 tile->SetPriority(tree, now_priority); 482 } 483 484 // Assign soon priority to skewport tiles. 485 for (TilingData::DifferenceIterator iter( 486 &tiling_data_, skewport, visible_rect_in_content_space); 487 iter; 488 ++iter) { 489 TileMap::iterator find = tiles_.find(iter.index()); 490 if (find == tiles_.end()) 491 continue; 492 Tile* tile = find->second.get(); 493 494 gfx::Rect tile_bounds = 495 tiling_data_.TileBounds(iter.index_x(), iter.index_y()); 496 497 float distance_to_visible = 498 visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) * 499 content_to_screen_scale; 500 501 TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible); 502 tile->SetPriority(tree, priority); 503 } 504 505 // Assign eventually priority to interest rect tiles. 506 for (TilingData::DifferenceIterator iter( 507 &tiling_data_, eventually_rect, skewport); 508 iter; 509 ++iter) { 510 TileMap::iterator find = tiles_.find(iter.index()); 511 if (find == tiles_.end()) 512 continue; 513 Tile* tile = find->second.get(); 514 515 gfx::Rect tile_bounds = 516 tiling_data_.TileBounds(iter.index_x(), iter.index_y()); 517 518 float distance_to_visible = 519 visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) * 520 content_to_screen_scale; 521 TilePriority priority( 522 resolution_, TilePriority::EVENTUALLY, distance_to_visible); 523 tile->SetPriority(tree, priority); 524 } 525 526 // Upgrade the priority on border tiles to be SOON. 527 current_soon_border_rect_ = visible_rect_in_content_space; 528 float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale; 529 current_soon_border_rect_.Inset(-border, -border, -border, -border); 530 for (TilingData::DifferenceIterator iter( 531 &tiling_data_, current_soon_border_rect_, skewport); 532 iter; 533 ++iter) { 534 TileMap::iterator find = tiles_.find(iter.index()); 535 if (find == tiles_.end()) 536 continue; 537 Tile* tile = find->second.get(); 538 539 TilePriority priority(resolution_, 540 TilePriority::SOON, 541 tile->priority(tree).distance_to_visible); 542 tile->SetPriority(tree, priority); 543 } 544 } 545 546 void PictureLayerTiling::RemoveTileAt(int i, int j) { 547 TileMapKey key(i, j); 548 TileMap::iterator found = tiles_.find(key); 549 if (found == tiles_.end()) 550 return; 551 tiles_.erase(found); 552 } 553 554 void PictureLayerTiling::SetLiveTilesRect( 555 const gfx::Rect& new_live_tiles_rect) { 556 DCHECK(new_live_tiles_rect.IsEmpty() || 557 TilingRect().Contains(new_live_tiles_rect)); 558 if (live_tiles_rect_ == new_live_tiles_rect) 559 return; 560 561 // Iterate to delete all tiles outside of our new live_tiles rect. 562 PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this); 563 for (TilingData::DifferenceIterator iter(&tiling_data_, 564 live_tiles_rect_, 565 new_live_tiles_rect); 566 iter; 567 ++iter) { 568 TileMapKey key(iter.index()); 569 TileMap::iterator found = tiles_.find(key); 570 // If the tile was outside of the recorded region, it won't exist even 571 // though it was in the live rect. 572 if (found != tiles_.end()) { 573 tiles_.erase(found); 574 if (recycled_twin) 575 recycled_twin->RemoveTileAt(iter.index_x(), iter.index_y()); 576 } 577 } 578 579 const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this); 580 581 // Iterate to allocate new tiles for all regions with newly exposed area. 582 for (TilingData::DifferenceIterator iter(&tiling_data_, 583 new_live_tiles_rect, 584 live_tiles_rect_); 585 iter; 586 ++iter) { 587 TileMapKey key(iter.index()); 588 CreateTile(key.first, key.second, twin_tiling); 589 } 590 591 live_tiles_rect_ = new_live_tiles_rect; 592 } 593 594 void PictureLayerTiling::DidBecomeRecycled() { 595 // DidBecomeActive below will set the active priority for tiles that are 596 // still in the tree. Calling this first on an active tiling that is becoming 597 // recycled takes care of tiles that are no longer in the active tree (eg. 598 // due to a pending invalidation). 599 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 600 it->second->SetPriority(ACTIVE_TREE, TilePriority()); 601 } 602 } 603 604 void PictureLayerTiling::DidBecomeActive() { 605 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 606 it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE)); 607 it->second->SetPriority(PENDING_TREE, TilePriority()); 608 609 // Tile holds a ref onto a picture pile. If the tile never gets invalidated 610 // and recreated, then that picture pile ref could exist indefinitely. To 611 // prevent this, ask the client to update the pile to its own ref. This 612 // will cause PicturePileImpls and their clones to get deleted once the 613 // corresponding PictureLayerImpl and any in flight raster jobs go out of 614 // scope. 615 client_->UpdatePile(it->second.get()); 616 } 617 } 618 619 void PictureLayerTiling::UpdateTilesToCurrentPile() { 620 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 621 client_->UpdatePile(it->second.get()); 622 } 623 } 624 625 void PictureLayerTiling::GetAllTilesForTracing( 626 std::set<const Tile*>* tiles) const { 627 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) 628 tiles->insert(it->second.get()); 629 } 630 631 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const { 632 scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue()); 633 state->SetInteger("num_tiles", tiles_.size()); 634 state->SetDouble("content_scale", contents_scale_); 635 state->Set("tiling_rect", MathUtil::AsValue(TilingRect()).release()); 636 return state.PassAs<base::Value>(); 637 } 638 639 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const { 640 size_t amount = 0; 641 for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 642 const Tile* tile = it->second.get(); 643 amount += tile->GPUMemoryUsageInBytes(); 644 } 645 return amount; 646 } 647 648 PictureLayerTiling::RectExpansionCache::RectExpansionCache() 649 : previous_target(0) { 650 } 651 652 namespace { 653 654 // This struct represents an event at which the expending rect intersects 655 // one of its boundaries. 4 intersection events will occur during expansion. 656 struct EdgeEvent { 657 enum { BOTTOM, TOP, LEFT, RIGHT } edge; 658 int* num_edges; 659 int distance; 660 }; 661 662 // Compute the delta to expand from edges to cover target_area. 663 int ComputeExpansionDelta(int num_x_edges, int num_y_edges, 664 int width, int height, 665 int64 target_area) { 666 // Compute coefficients for the quadratic equation: 667 // a*x^2 + b*x + c = 0 668 int a = num_y_edges * num_x_edges; 669 int b = num_y_edges * width + num_x_edges * height; 670 int64 c = static_cast<int64>(width) * height - target_area; 671 672 // Compute the delta for our edges using the quadratic equation. 673 return a == 0 ? -c / b : 674 (-b + static_cast<int>( 675 std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a); 676 } 677 678 } // namespace 679 680 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy( 681 const gfx::Rect& starting_rect, 682 int64 target_area, 683 const gfx::Rect& bounding_rect, 684 RectExpansionCache* cache) { 685 if (starting_rect.IsEmpty()) 686 return starting_rect; 687 688 if (cache && 689 cache->previous_start == starting_rect && 690 cache->previous_bounds == bounding_rect && 691 cache->previous_target == target_area) 692 return cache->previous_result; 693 694 if (cache) { 695 cache->previous_start = starting_rect; 696 cache->previous_bounds = bounding_rect; 697 cache->previous_target = target_area; 698 } 699 700 DCHECK(!bounding_rect.IsEmpty()); 701 DCHECK_GT(target_area, 0); 702 703 // Expand the starting rect to cover target_area, if it is smaller than it. 704 int delta = ComputeExpansionDelta( 705 2, 2, starting_rect.width(), starting_rect.height(), target_area); 706 gfx::Rect expanded_starting_rect = starting_rect; 707 if (delta > 0) 708 expanded_starting_rect.Inset(-delta, -delta); 709 710 gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect); 711 if (rect.IsEmpty()) { 712 // The starting_rect and bounding_rect are far away. 713 if (cache) 714 cache->previous_result = rect; 715 return rect; 716 } 717 if (delta >= 0 && rect == expanded_starting_rect) { 718 // The starting rect already covers the entire bounding_rect and isn't too 719 // large for the target_area. 720 if (cache) 721 cache->previous_result = rect; 722 return rect; 723 } 724 725 // Continue to expand/shrink rect to let it cover target_area. 726 727 // These values will be updated by the loop and uses as the output. 728 int origin_x = rect.x(); 729 int origin_y = rect.y(); 730 int width = rect.width(); 731 int height = rect.height(); 732 733 // In the beginning we will consider 2 edges in each dimension. 734 int num_y_edges = 2; 735 int num_x_edges = 2; 736 737 // Create an event list. 738 EdgeEvent events[] = { 739 { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() }, 740 { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() }, 741 { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() }, 742 { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() } 743 }; 744 745 // Sort the events by distance (closest first). 746 if (events[0].distance > events[1].distance) std::swap(events[0], events[1]); 747 if (events[2].distance > events[3].distance) std::swap(events[2], events[3]); 748 if (events[0].distance > events[2].distance) std::swap(events[0], events[2]); 749 if (events[1].distance > events[3].distance) std::swap(events[1], events[3]); 750 if (events[1].distance > events[2].distance) std::swap(events[1], events[2]); 751 752 for (int event_index = 0; event_index < 4; event_index++) { 753 const EdgeEvent& event = events[event_index]; 754 755 int delta = ComputeExpansionDelta( 756 num_x_edges, num_y_edges, width, height, target_area); 757 758 // Clamp delta to our event distance. 759 if (delta > event.distance) 760 delta = event.distance; 761 762 // Adjust the edge count for this kind of edge. 763 --*event.num_edges; 764 765 // Apply the delta to the edges and edge events. 766 for (int i = event_index; i < 4; i++) { 767 switch (events[i].edge) { 768 case EdgeEvent::BOTTOM: 769 origin_y -= delta; 770 height += delta; 771 break; 772 case EdgeEvent::TOP: 773 height += delta; 774 break; 775 case EdgeEvent::LEFT: 776 origin_x -= delta; 777 width += delta; 778 break; 779 case EdgeEvent::RIGHT: 780 width += delta; 781 break; 782 } 783 events[i].distance -= delta; 784 } 785 786 // If our delta is less then our event distance, we're done. 787 if (delta < event.distance) 788 break; 789 } 790 791 gfx::Rect result(origin_x, origin_y, width, height); 792 if (cache) 793 cache->previous_result = result; 794 return result; 795 } 796 797 void PictureLayerTiling::UpdateEvictionCacheIfNeeded( 798 TreePriority tree_priority) { 799 if (eviction_tiles_cache_valid_ && 800 eviction_cache_tree_priority_ == tree_priority) 801 return; 802 803 eviction_tiles_cache_.clear(); 804 eviction_tiles_cache_.reserve(tiles_.size()); 805 for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) { 806 // TODO(vmpstr): This should update the priority if UpdateTilePriorities 807 // changes not to do this. 808 eviction_tiles_cache_.push_back(it->second); 809 } 810 811 std::sort(eviction_tiles_cache_.begin(), 812 eviction_tiles_cache_.end(), 813 TileEvictionOrder(tree_priority)); 814 eviction_tiles_cache_valid_ = true; 815 eviction_cache_tree_priority_ = tree_priority; 816 } 817 818 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator() 819 : tiling_(NULL), current_tile_(NULL) {} 820 821 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator( 822 PictureLayerTiling* tiling, 823 WhichTree tree) 824 : tiling_(tiling), 825 type_(TilePriority::NOW), 826 visible_rect_in_content_space_( 827 tiling_->current_visible_rect_in_content_space_), 828 skewport_in_content_space_(tiling_->current_skewport_), 829 eventually_rect_in_content_space_(tiling_->current_eventually_rect_), 830 soon_border_rect_in_content_space_(tiling_->current_soon_border_rect_), 831 tree_(tree), 832 current_tile_(NULL), 833 visible_iterator_(&tiling->tiling_data_, 834 visible_rect_in_content_space_, 835 true /* include_borders */), 836 spiral_iterator_(&tiling->tiling_data_, 837 skewport_in_content_space_, 838 visible_rect_in_content_space_, 839 visible_rect_in_content_space_), 840 skewport_processed_(false) { 841 if (!visible_iterator_) { 842 AdvancePhase(); 843 return; 844 } 845 846 current_tile_ = 847 tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y()); 848 if (!current_tile_ || !TileNeedsRaster(current_tile_)) 849 ++(*this); 850 } 851 852 PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {} 853 854 void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() { 855 DCHECK_LT(type_, TilePriority::EVENTUALLY); 856 857 do { 858 type_ = static_cast<TilePriority::PriorityBin>(type_ + 1); 859 if (type_ == TilePriority::EVENTUALLY) { 860 spiral_iterator_ = TilingData::SpiralDifferenceIterator( 861 &tiling_->tiling_data_, 862 eventually_rect_in_content_space_, 863 skewport_in_content_space_, 864 visible_rect_in_content_space_); 865 } 866 867 while (spiral_iterator_) { 868 current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(), 869 spiral_iterator_.index_y()); 870 if (current_tile_ && TileNeedsRaster(current_tile_)) 871 break; 872 ++spiral_iterator_; 873 } 874 875 if (!spiral_iterator_ && type_ == TilePriority::EVENTUALLY) { 876 current_tile_ = NULL; 877 break; 878 } 879 } while (!spiral_iterator_); 880 } 881 882 PictureLayerTiling::TilingRasterTileIterator& 883 PictureLayerTiling::TilingRasterTileIterator:: 884 operator++() { 885 current_tile_ = NULL; 886 while (!current_tile_ || !TileNeedsRaster(current_tile_)) { 887 std::pair<int, int> next_index; 888 switch (type_) { 889 case TilePriority::NOW: 890 ++visible_iterator_; 891 if (!visible_iterator_) { 892 AdvancePhase(); 893 return *this; 894 } 895 next_index = visible_iterator_.index(); 896 break; 897 case TilePriority::SOON: 898 ++spiral_iterator_; 899 if (!spiral_iterator_) { 900 if (skewport_processed_) { 901 AdvancePhase(); 902 return *this; 903 } 904 skewport_processed_ = true; 905 spiral_iterator_ = TilingData::SpiralDifferenceIterator( 906 &tiling_->tiling_data_, 907 soon_border_rect_in_content_space_, 908 skewport_in_content_space_, 909 visible_rect_in_content_space_); 910 if (!spiral_iterator_) { 911 AdvancePhase(); 912 return *this; 913 } 914 } 915 next_index = spiral_iterator_.index(); 916 break; 917 case TilePriority::EVENTUALLY: 918 ++spiral_iterator_; 919 if (!spiral_iterator_) { 920 current_tile_ = NULL; 921 return *this; 922 } 923 next_index = spiral_iterator_.index(); 924 break; 925 } 926 current_tile_ = tiling_->TileAt(next_index.first, next_index.second); 927 } 928 return *this; 929 } 930 931 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator() 932 : is_valid_(false), tiling_(NULL) {} 933 934 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator( 935 PictureLayerTiling* tiling, 936 TreePriority tree_priority) 937 : is_valid_(false), tiling_(tiling), tree_priority_(tree_priority) {} 938 939 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {} 940 941 PictureLayerTiling::TilingEvictionTileIterator::operator bool() { 942 if (!IsValid()) 943 Initialize(); 944 945 return IsValid() && tile_iterator_ != tiling_->eviction_tiles_cache_.end(); 946 } 947 948 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() { 949 if (!IsValid()) 950 Initialize(); 951 952 DCHECK(*this); 953 return *tile_iterator_; 954 } 955 956 PictureLayerTiling::TilingEvictionTileIterator& 957 PictureLayerTiling::TilingEvictionTileIterator:: 958 operator++() { 959 DCHECK(*this); 960 do { 961 ++tile_iterator_; 962 } while (tile_iterator_ != tiling_->eviction_tiles_cache_.end() && 963 (!(*tile_iterator_)->HasResources())); 964 965 return *this; 966 } 967 968 void PictureLayerTiling::TilingEvictionTileIterator::Initialize() { 969 if (!tiling_) 970 return; 971 972 tiling_->UpdateEvictionCacheIfNeeded(tree_priority_); 973 tile_iterator_ = tiling_->eviction_tiles_cache_.begin(); 974 is_valid_ = true; 975 if (tile_iterator_ != tiling_->eviction_tiles_cache_.end() && 976 !(*tile_iterator_)->HasResources()) { 977 ++(*this); 978 } 979 } 980 981 } // namespace cc 982
