cc/tiles/picture_layer_tiling.cc

   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/tiles/picture_layer_tiling.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9 #include <limits>
  10 #include <set>
  11
  12 #include "base/containers/hash_tables.h"
  13 #include "base/containers/small_map.h"
  14 #include "base/logging.h"
  15 #include "base/numerics/safe_conversions.h"
  16 #include "base/trace_event/trace_event.h"
  17 #include "base/trace_event/trace_event_argument.h"
  18 #include "cc/base/math_util.h"
  19 #include "cc/playback/raster_source.h"
  20 #include "cc/tiles/prioritized_tile.h"
  21 #include "cc/tiles/tile.h"
  22 #include "cc/tiles/tile_priority.h"
  23 #include "ui/gfx/geometry/point_conversions.h"
  24 #include "ui/gfx/geometry/rect_conversions.h"
  25 #include "ui/gfx/geometry/safe_integer_conversions.h"
  26 #include "ui/gfx/geometry/size_conversions.h"
  27
  28 namespace cc {
  29 namespace {
  30
  31 const float kSoonBorderDistanceViewportPercentage = 0.15f;
  32 const float kMaxSoonBorderDistanceInScreenPixels = 312.f;
  33
  34 }  // namespace
  35
  36 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
  37     WhichTree tree,
  38     float contents_scale,
  39     scoped_refptr<RasterSource> raster_source,
  40     PictureLayerTilingClient* client,
  41     size_t tiling_interest_area_padding,
  42     float skewport_target_time_in_seconds,
  43     int skewport_extrapolation_limit_in_content_pixels) {
  44   return make_scoped_ptr(new PictureLayerTiling(
  45       tree, contents_scale, raster_source, client, tiling_interest_area_padding,
  46       skewport_target_time_in_seconds,
  47       skewport_extrapolation_limit_in_content_pixels));
  48 }
  49
  50 PictureLayerTiling::PictureLayerTiling(
  51     WhichTree tree,
  52     float contents_scale,
  53     scoped_refptr<RasterSource> raster_source,
  54     PictureLayerTilingClient* client,
  55     size_t tiling_interest_area_padding,
  56     float skewport_target_time_in_seconds,
  57     int skewport_extrapolation_limit_in_content_pixels)
  58     : tiling_interest_area_padding_(tiling_interest_area_padding),
  59       skewport_target_time_in_seconds_(skewport_target_time_in_seconds),
  60       skewport_extrapolation_limit_in_content_pixels_(
  61           skewport_extrapolation_limit_in_content_pixels),
  62       contents_scale_(contents_scale),
  63       client_(client),
  64       tree_(tree),
  65       raster_source_(raster_source),
  66       resolution_(NON_IDEAL_RESOLUTION),
  67       may_contain_low_resolution_tiles_(false),
  68       tiling_data_(gfx::Size(), gfx::Size(), kBorderTexels),
  69       can_require_tiles_for_activation_(false),
  70       current_content_to_screen_scale_(0.f),
  71       has_visible_rect_tiles_(false),
  72       has_skewport_rect_tiles_(false),
  73       has_soon_border_rect_tiles_(false),
  74       has_eventually_rect_tiles_(false),
  75       all_tiles_done_(true) {
  76   DCHECK(!raster_source->IsSolidColor());
  77   gfx::Size content_bounds = gfx::ToCeiledSize(
  78       gfx::ScaleSize(raster_source_->GetSize(), contents_scale));
  79   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
  80
  81   DCHECK(!gfx::ToFlooredSize(gfx::ScaleSize(raster_source_->GetSize(),
  82                                             contents_scale)).IsEmpty())
  83       << "Tiling created with scale too small as contents become empty."
  84       << " Layer bounds: " << raster_source_->GetSize().ToString()
  85       << " Contents scale: " << contents_scale;
  86
  87   tiling_data_.SetTilingSize(content_bounds);
  88   tiling_data_.SetMaxTextureSize(tile_size);
  89 }
  90
  91 PictureLayerTiling::~PictureLayerTiling() {
  92 }
  93
  94 // static
  95 float PictureLayerTiling::CalculateSoonBorderDistance(
  96     const gfx::Rect& visible_rect_in_content_space,
  97     float content_to_screen_scale) {
  98   float max_dimension = std::max(visible_rect_in_content_space.width(),
  99                                  visible_rect_in_content_space.height());
 100   return std::min(
 101       kMaxSoonBorderDistanceInScreenPixels / content_to_screen_scale,
 102       max_dimension * kSoonBorderDistanceViewportPercentage);
 103 }
 104
 105 Tile* PictureLayerTiling::CreateTile(int i, int j) {
 106   TileMapKey key(i, j);
 107   DCHECK(tiles_.find(key) == tiles_.end());
 108
 109   gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
 110   gfx::Rect tile_rect = paint_rect;
 111   tile_rect.set_size(tiling_data_.max_texture_size());
 112
 113   if (!raster_source_->CoversRect(tile_rect, contents_scale_))
 114     return nullptr;
 115
 116   all_tiles_done_ = false;
 117   ScopedTilePtr tile = client_->CreateTile(contents_scale_, tile_rect);
 118   Tile* raw_ptr = tile.get();
 119   tile->set_tiling_index(i, j);
 120   tiles_.add(key, tile.Pass());
 121   return raw_ptr;
 122 }
 123
 124 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
 125   const PictureLayerTiling* active_twin =
 126       tree_ == PENDING_TREE ? client_->GetPendingOrActiveTwinTiling(this)
 127                             : nullptr;
 128   const Region* invalidation =
 129       active_twin ? client_->GetPendingInvalidation() : nullptr;
 130
 131   bool include_borders = false;
 132   for (TilingData::Iterator iter(&tiling_data_, live_tiles_rect_,
 133                                  include_borders);
 134        iter; ++iter) {
 135     TileMapKey key(iter.index());
 136     TileMap::iterator find = tiles_.find(key);
 137     if (find != tiles_.end())
 138       continue;
 139
 140     if (ShouldCreateTileAt(key.index_x, key.index_y)) {
 141       Tile* tile = CreateTile(key.index_x, key.index_y);
 142
 143       // If this is the pending tree, then the active twin tiling may contain
 144       // the previous content ID of these tiles. In that case, we need only
 145       // partially raster the tile content.
 146       if (tile && invalidation && TilingMatchesTileIndices(active_twin)) {
 147         if (const Tile* old_tile =
 148                 active_twin->TileAt(key.index_x, key.index_y)) {
 149           gfx::Rect tile_rect = tile->content_rect();
 150           gfx::Rect invalidated;
 151           for (Region::Iterator iter(*invalidation); iter.has_rect();
 152                iter.next()) {
 153             gfx::Rect invalid_content_rect =
 154                 gfx::ScaleToEnclosingRect(iter.rect(), contents_scale_);
 155             invalid_content_rect.Intersect(tile_rect);
 156             invalidated.Union(invalid_content_rect);
 157           }
 158           tile->SetInvalidated(invalidated, old_tile->id());
 159         }
 160       }
 161     }
 162   }
 163   VerifyLiveTilesRect(false);
 164 }
 165
 166 void PictureLayerTiling::TakeTilesAndPropertiesFrom(
 167     PictureLayerTiling* pending_twin,
 168     const Region& layer_invalidation) {
 169   TRACE_EVENT0("cc", "TakeTilesAndPropertiesFrom");
 170   SetRasterSourceAndResize(pending_twin->raster_source_);
 171
 172   RemoveTilesInRegion(layer_invalidation, false /* recreate tiles */);
 173
 174   resolution_ = pending_twin->resolution_;
 175   bool create_missing_tiles = false;
 176   if (live_tiles_rect_.IsEmpty()) {
 177     live_tiles_rect_ = pending_twin->live_tiles_rect();
 178     create_missing_tiles = true;
 179   } else {
 180     SetLiveTilesRect(pending_twin->live_tiles_rect());
 181   }
 182
 183   if (tiles_.empty()) {
 184     tiles_.swap(pending_twin->tiles_);
 185     all_tiles_done_ = pending_twin->all_tiles_done_;
 186   } else {
 187     while (!pending_twin->tiles_.empty()) {
 188       TileMapKey key = pending_twin->tiles_.begin()->first;
 189       tiles_.set(key, pending_twin->tiles_.take_and_erase(key));
 190     }
 191     all_tiles_done_ &= pending_twin->all_tiles_done_;
 192   }
 193   DCHECK(pending_twin->tiles_.empty());
 194   pending_twin->all_tiles_done_ = true;
 195
 196   if (create_missing_tiles)
 197     CreateMissingTilesInLiveTilesRect();
 198
 199   VerifyLiveTilesRect(false);
 200
 201   SetTilePriorityRects(pending_twin->current_content_to_screen_scale_,
 202                        pending_twin->current_visible_rect_,
 203                        pending_twin->current_skewport_rect_,
 204                        pending_twin->current_soon_border_rect_,
 205                        pending_twin->current_eventually_rect_,
 206                        pending_twin->current_occlusion_in_layer_space_);
 207 }
 208
 209 void PictureLayerTiling::SetRasterSourceAndResize(
 210     scoped_refptr<RasterSource> raster_source) {
 211   DCHECK(!raster_source->IsSolidColor());
 212   gfx::Size old_layer_bounds = raster_source_->GetSize();
 213   raster_source_.swap(raster_source);
 214   gfx::Size new_layer_bounds = raster_source_->GetSize();
 215   gfx::Size content_bounds =
 216       gfx::ToCeiledSize(gfx::ScaleSize(new_layer_bounds, contents_scale_));
 217   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
 218
 219   if (tile_size != tiling_data_.max_texture_size()) {
 220     tiling_data_.SetTilingSize(content_bounds);
 221     tiling_data_.SetMaxTextureSize(tile_size);
 222     // When the tile size changes, the TilingData positions no longer work
 223     // as valid keys to the TileMap, so just drop all tiles and clear the live
 224     // tiles rect.
 225     Reset();
 226     return;
 227   }
 228
 229   if (old_layer_bounds == new_layer_bounds)
 230     return;
 231
 232   // The SetLiveTilesRect() method would drop tiles outside the new bounds,
 233   // but may do so incorrectly if resizing the tiling causes the number of
 234   // tiles in the tiling_data_ to change.
 235   gfx::Rect content_rect(content_bounds);
 236   int before_left = tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.x());
 237   int before_top = tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.y());
 238   int before_right =
 239       tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 240   int before_bottom =
 241       tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 242
 243   // The live_tiles_rect_ is clamped to stay within the tiling size as we
 244   // change it.
 245   live_tiles_rect_.Intersect(content_rect);
 246   tiling_data_.SetTilingSize(content_bounds);
 247
 248   int after_right = -1;
 249   int after_bottom = -1;
 250   if (!live_tiles_rect_.IsEmpty()) {
 251     after_right =
 252         tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 253     after_bottom =
 254         tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 255   }
 256
 257   // There is no recycled twin since this is run on the pending tiling
 258   // during commit, and on the active tree during activate.
 259   // Drop tiles outside the new layer bounds if the layer shrank.
 260   for (int i = after_right + 1; i <= before_right; ++i) {
 261     for (int j = before_top; j <= before_bottom; ++j)
 262       RemoveTileAt(i, j);
 263   }
 264   for (int i = before_left; i <= after_right; ++i) {
 265     for (int j = after_bottom + 1; j <= before_bottom; ++j)
 266       RemoveTileAt(i, j);
 267   }
 268
 269   if (after_right > before_right) {
 270     DCHECK_EQ(after_right, before_right + 1);
 271     for (int j = before_top; j <= after_bottom; ++j) {
 272       if (ShouldCreateTileAt(after_right, j))
 273         CreateTile(after_right, j);
 274     }
 275   }
 276   if (after_bottom > before_bottom) {
 277     DCHECK_EQ(after_bottom, before_bottom + 1);
 278     for (int i = before_left; i <= before_right; ++i) {
 279       if (ShouldCreateTileAt(i, after_bottom))
 280         CreateTile(i, after_bottom);
 281     }
 282   }
 283 }
 284
 285 void PictureLayerTiling::Invalidate(const Region& layer_invalidation) {
 286   DCHECK_IMPLIES(tree_ == ACTIVE_TREE,
 287                  !client_->GetPendingOrActiveTwinTiling(this));
 288   RemoveTilesInRegion(layer_invalidation, true /* recreate tiles */);
 289 }
 290
 291 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_invalidation,
 292                                              bool recreate_tiles) {
 293   // We only invalidate the active tiling when it's orphaned: it has no pending
 294   // twin, so it's slated for removal in the future.
 295   if (live_tiles_rect_.IsEmpty())
 296     return;
 297   // Pick 16 for the size of the SmallMap before it promotes to a hash_map.
 298   // 4x4 tiles should cover most small invalidations, and walking a vector of
 299   // 16 is fast enough. If an invalidation is huge we will fall back to a
 300   // hash_map instead of a vector in the SmallMap.
 301   base::SmallMap<base::hash_map<TileMapKey, gfx::Rect>, 16> remove_tiles;
 302   gfx::Rect expanded_live_tiles_rect =
 303       tiling_data_.ExpandRectIgnoringBordersToTileBounds(live_tiles_rect_);
 304   for (Region::Iterator iter(layer_invalidation); iter.has_rect();
 305        iter.next()) {
 306     gfx::Rect layer_rect = iter.rect();
 307     // The pixels which are invalid in content space.
 308     gfx::Rect invalid_content_rect =
 309         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
 310     // Consider tiles inside the live tiles rect even if only their border
 311     // pixels intersect the invalidation. But don't consider tiles outside
 312     // the live tiles rect with the same conditions, as they won't exist.
 313     gfx::Rect coverage_content_rect = invalid_content_rect;
 314     int border_pixels = tiling_data_.border_texels();
 315     coverage_content_rect.Inset(-border_pixels, -border_pixels);
 316     // Avoid needless work by not bothering to invalidate where there aren't
 317     // tiles.
 318     coverage_content_rect.Intersect(expanded_live_tiles_rect);
 319     if (coverage_content_rect.IsEmpty())
 320       continue;
 321     // Since the content_rect includes border pixels already, don't include
 322     // borders when iterating to avoid double counting them.
 323     bool include_borders = false;
 324     for (TilingData::Iterator iter(&tiling_data_, coverage_content_rect,
 325                                    include_borders);
 326          iter; ++iter) {
 327       // This also adds the TileMapKey to the map.
 328       remove_tiles[TileMapKey(iter.index())].Union(invalid_content_rect);
 329     }
 330   }
 331
 332   for (const auto& pair : remove_tiles) {
 333     const TileMapKey& key = pair.first;
 334     const gfx::Rect& invalid_content_rect = pair.second;
 335     // TODO(danakj): This old_tile will not exist if we are committing to a
 336     // pending tree since there is no tile there to remove, which prevents
 337     // tiles from knowing the invalidation rect and content id. crbug.com/490847
 338     ScopedTilePtr old_tile = TakeTileAt(key.index_x, key.index_y);
 339     if (recreate_tiles && old_tile) {
 340       if (Tile* tile = CreateTile(key.index_x, key.index_y))
 341         tile->SetInvalidated(invalid_content_rect, old_tile->id());
 342     }
 343   }
 344 }
 345
 346 bool PictureLayerTiling::ShouldCreateTileAt(int i, int j) const {
 347   // Active tree should always create a tile. The reason for this is that active
 348   // tree represents content that we draw on screen, which means that whenever
 349   // we check whether a tile should exist somewhere, the answer is yes. This
 350   // doesn't mean it will actually be created (if raster source doesn't cover
 351   // the tile for instance). Pending tree, on the other hand, should only be
 352   // creating tiles that are different from the current active tree, which is
 353   // represented by the logic in the rest of the function.
 354   if (tree_ == ACTIVE_TREE)
 355     return true;
 356
 357   // If the pending tree has no active twin, then it needs to create all tiles.
 358   const PictureLayerTiling* active_twin =
 359       client_->GetPendingOrActiveTwinTiling(this);
 360   if (!active_twin)
 361     return true;
 362
 363   // Pending tree will override the entire active tree if indices don't match.
 364   if (!TilingMatchesTileIndices(active_twin))
 365     return true;
 366
 367   gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
 368   gfx::Rect tile_rect = paint_rect;
 369   tile_rect.set_size(tiling_data_.max_texture_size());
 370
 371   // If the active tree can't create a tile, because of its raster source, then
 372   // the pending tree should create one.
 373   if (!active_twin->raster_source()->CoversRect(tile_rect, contents_scale()))
 374     return true;
 375
 376   const Region* layer_invalidation = client_->GetPendingInvalidation();
 377   gfx::Rect layer_rect =
 378       gfx::ScaleToEnclosingRect(tile_rect, 1.f / contents_scale());
 379
 380   // If this tile is invalidated, then the pending tree should create one.
 381   if (layer_invalidation && layer_invalidation->Intersects(layer_rect))
 382     return true;
 383
 384   // If the active tree doesn't have a tile here, but it's in the pending tree's
 385   // visible rect, then the pending tree should create a tile. This can happen
 386   // if the pending visible rect is outside of the active tree's live tiles
 387   // rect. In those situations, we need to block activation until we're ready to
 388   // display content, which will have to come from the pending tree.
 389   if (!active_twin->TileAt(i, j) && current_visible_rect_.Intersects(tile_rect))
 390     return true;
 391
 392   // In all other cases, the pending tree doesn't need to create a tile.
 393   return false;
 394 }
 395
 396 bool PictureLayerTiling::TilingMatchesTileIndices(
 397     const PictureLayerTiling* twin) const {
 398   return tiling_data_.max_texture_size() ==
 399          twin->tiling_data_.max_texture_size();
 400 }
 401
 402 PictureLayerTiling::CoverageIterator::CoverageIterator()
 403     : tiling_(NULL),
 404       current_tile_(NULL),
 405       tile_i_(0),
 406       tile_j_(0),
 407       left_(0),
 408       top_(0),
 409       right_(-1),
 410       bottom_(-1) {
 411 }
 412
 413 PictureLayerTiling::CoverageIterator::CoverageIterator(
 414     const PictureLayerTiling* tiling,
 415     float dest_scale,
 416     const gfx::Rect& dest_rect)
 417     : tiling_(tiling),
 418       dest_rect_(dest_rect),
 419       dest_to_content_scale_(0),
 420       current_tile_(NULL),
 421       tile_i_(0),
 422       tile_j_(0),
 423       left_(0),
 424       top_(0),
 425       right_(-1),
 426       bottom_(-1) {
 427   DCHECK(tiling_);
 428   if (dest_rect_.IsEmpty())
 429     return;
 430
 431   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 432
 433   gfx::Rect content_rect =
 434       gfx::ScaleToEnclosingRect(dest_rect_,
 435                                 dest_to_content_scale_,
 436                                 dest_to_content_scale_);
 437   // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
 438   // check for non-intersection first.
 439   content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 440   if (content_rect.IsEmpty())
 441     return;
 442
 443   left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
 444   top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
 445   right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
 446       content_rect.right() - 1);
 447   bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
 448       content_rect.bottom() - 1);
 449
 450   tile_i_ = left_ - 1;
 451   tile_j_ = top_;
 452   ++(*this);
 453 }
 454
 455 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 456 }
 457
 458 PictureLayerTiling::CoverageIterator&
 459 PictureLayerTiling::CoverageIterator::operator++() {
 460   if (tile_j_ > bottom_)
 461     return *this;
 462
 463   bool first_time = tile_i_ < left_;
 464   bool new_row = false;
 465   tile_i_++;
 466   if (tile_i_ > right_) {
 467     tile_i_ = left_;
 468     tile_j_++;
 469     new_row = true;
 470     if (tile_j_ > bottom_) {
 471       current_tile_ = NULL;
 472       return *this;
 473     }
 474   }
 475
 476   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 477
 478   // Calculate the current geometry rect.  Due to floating point rounding
 479   // and ToEnclosingRect, tiles might overlap in destination space on the
 480   // edges.
 481   gfx::Rect last_geometry_rect = current_geometry_rect_;
 482
 483   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 484
 485   current_geometry_rect_ =
 486       gfx::ScaleToEnclosingRect(content_rect, 1 / dest_to_content_scale_);
 487
 488   current_geometry_rect_.Intersect(dest_rect_);
 489   DCHECK(!current_geometry_rect_.IsEmpty());
 490
 491   if (first_time)
 492     return *this;
 493
 494   // Iteration happens left->right, top->bottom.  Running off the bottom-right
 495   // edge is handled by the intersection above with dest_rect_.  Here we make
 496   // sure that the new current geometry rect doesn't overlap with the last.
 497   int min_left;
 498   int min_top;
 499   if (new_row) {
 500     min_left = dest_rect_.x();
 501     min_top = last_geometry_rect.bottom();
 502   } else {
 503     min_left = last_geometry_rect.right();
 504     min_top = last_geometry_rect.y();
 505   }
 506
 507   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 508   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 509   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 510
 511   if (!new_row) {
 512     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 513     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 514     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 515   }
 516
 517   return *this;
 518 }
 519
 520 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 521   return current_geometry_rect_;
 522 }
 523
 524 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 525   gfx::PointF tex_origin =
 526       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 527
 528   // Convert from dest space => content space => texture space.
 529   gfx::RectF texture_rect(current_geometry_rect_);
 530   texture_rect.Scale(dest_to_content_scale_,
 531                      dest_to_content_scale_);
 532   texture_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 533   if (texture_rect.IsEmpty())
 534     return texture_rect;
 535   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 536
 537   return texture_rect;
 538 }
 539
 540 ScopedTilePtr PictureLayerTiling::TakeTileAt(int i, int j) {
 541   TileMap::iterator found = tiles_.find(TileMapKey(i, j));
 542   if (found == tiles_.end())
 543     return nullptr;
 544   return tiles_.take_and_erase(found);
 545 }
 546
 547 bool PictureLayerTiling::RemoveTileAt(int i, int j) {
 548   TileMap::iterator found = tiles_.find(TileMapKey(i, j));
 549   if (found == tiles_.end())
 550     return false;
 551   tiles_.erase(found);
 552   return true;
 553 }
 554
 555 void PictureLayerTiling::Reset() {
 556   live_tiles_rect_ = gfx::Rect();
 557   tiles_.clear();
 558   all_tiles_done_ = true;
 559 }
 560
 561 gfx::Rect PictureLayerTiling::ComputeSkewport(
 562     double current_frame_time_in_seconds,
 563     const gfx::Rect& visible_rect_in_content_space) const {
 564   gfx::Rect skewport = visible_rect_in_content_space;
 565   if (skewport.IsEmpty())
 566     return skewport;
 567
 568   if (visible_rect_history_[1].frame_time_in_seconds == 0.0)
 569     return skewport;
 570
 571   double time_delta = current_frame_time_in_seconds -
 572                       visible_rect_history_[1].frame_time_in_seconds;
 573   if (time_delta == 0.0)
 574     return skewport;
 575
 576   double extrapolation_multiplier =
 577       skewport_target_time_in_seconds_ / time_delta;
 578
 579   int old_x = visible_rect_history_[1].visible_rect_in_content_space.x();
 580   int old_y = visible_rect_history_[1].visible_rect_in_content_space.y();
 581   int old_right =
 582       visible_rect_history_[1].visible_rect_in_content_space.right();
 583   int old_bottom =
 584       visible_rect_history_[1].visible_rect_in_content_space.bottom();
 585
 586   int new_x = visible_rect_in_content_space.x();
 587   int new_y = visible_rect_in_content_space.y();
 588   int new_right = visible_rect_in_content_space.right();
 589   int new_bottom = visible_rect_in_content_space.bottom();
 590
 591   // Compute the maximum skewport based on
 592   // |skewport_extrapolation_limit_in_content_pixels_|.
 593   gfx::Rect max_skewport = skewport;
 594   max_skewport.Inset(-skewport_extrapolation_limit_in_content_pixels_,
 595                      -skewport_extrapolation_limit_in_content_pixels_);
 596
 597   // Inset the skewport by the needed adjustment.
 598   skewport.Inset(extrapolation_multiplier * (new_x - old_x),
 599                  extrapolation_multiplier * (new_y - old_y),
 600                  extrapolation_multiplier * (old_right - new_right),
 601                  extrapolation_multiplier * (old_bottom - new_bottom));
 602
 603   // Ensure that visible rect is contained in the skewport.
 604   skewport.Union(visible_rect_in_content_space);
 605
 606   // Clip the skewport to |max_skewport|. This needs to happen after the
 607   // union in case intersecting would have left the empty rect.
 608   skewport.Intersect(max_skewport);
 609
 610   // Due to limits in int's representation, it is possible that the two
 611   // operations above (union and intersect) result in an empty skewport. To
 612   // avoid any unpleasant situations like that, union the visible rect again to
 613   // ensure that skewport.Contains(visible_rect_in_content_space) is always
 614   // true.
 615   skewport.Union(visible_rect_in_content_space);
 616
 617   return skewport;
 618 }
 619
 620 bool PictureLayerTiling::ComputeTilePriorityRects(
 621     const gfx::Rect& viewport_in_layer_space,
 622     float ideal_contents_scale,
 623     double current_frame_time_in_seconds,
 624     const Occlusion& occlusion_in_layer_space) {
 625   // If we have, or had occlusions, mark the tiles as 'not done' to ensure that
 626   // we reiterate the tiles for rasterization.
 627   if (occlusion_in_layer_space.HasOcclusion() ||
 628       current_occlusion_in_layer_space_.HasOcclusion()) {
 629     set_all_tiles_done(false);
 630   }
 631
 632   if (!NeedsUpdateForFrameAtTimeAndViewport(current_frame_time_in_seconds,
 633                                             viewport_in_layer_space)) {
 634     // This should never be zero for the purposes of has_ever_been_updated().
 635     DCHECK_NE(current_frame_time_in_seconds, 0.0);
 636     return false;
 637   }
 638   gfx::Rect visible_rect_in_content_space =
 639       gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
 640
 641   if (tiling_size().IsEmpty()) {
 642     UpdateVisibleRectHistory(current_frame_time_in_seconds,
 643                              visible_rect_in_content_space);
 644     last_viewport_in_layer_space_ = viewport_in_layer_space;
 645     return false;
 646   }
 647
 648   // Calculate the skewport.
 649   gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
 650                                        visible_rect_in_content_space);
 651   DCHECK(skewport.Contains(visible_rect_in_content_space));
 652
 653   // Calculate the eventually/live tiles rect.
 654   gfx::Size tile_size = tiling_data_.max_texture_size();
 655
 656   float content_to_screen_scale = ideal_contents_scale / contents_scale_;
 657   int pad_in_content_space =
 658       static_cast<int>(tiling_interest_area_padding_ / content_to_screen_scale);
 659   gfx::Rect eventually_rect = visible_rect_in_content_space;
 660   // If the visible rect is empty, keep the eventually rect as empty.
 661   if (!eventually_rect.IsEmpty()) {
 662     eventually_rect.Inset(-pad_in_content_space, -pad_in_content_space);
 663     eventually_rect =
 664         tiling_data_.ExpandRectIgnoringBordersToTileBounds(eventually_rect);
 665   }
 666
 667   DCHECK_IMPLIES(!eventually_rect.IsEmpty(),
 668                  gfx::Rect(tiling_size()).Contains(eventually_rect))
 669       << "tiling_size: " << tiling_size().ToString()
 670       << " eventually_rect: " << eventually_rect.ToString();
 671
 672   // Calculate the soon border rect.
 673   gfx::Rect soon_border_rect = visible_rect_in_content_space;
 674   float border = CalculateSoonBorderDistance(visible_rect_in_content_space,
 675                                              content_to_screen_scale);
 676   soon_border_rect.Inset(-border, -border, -border, -border);
 677
 678   UpdateVisibleRectHistory(current_frame_time_in_seconds,
 679                            visible_rect_in_content_space);
 680   last_viewport_in_layer_space_ = viewport_in_layer_space;
 681
 682   SetTilePriorityRects(content_to_screen_scale, visible_rect_in_content_space,
 683                        skewport, soon_border_rect, eventually_rect,
 684                        occlusion_in_layer_space);
 685   SetLiveTilesRect(eventually_rect);
 686   return true;
 687 }
 688
 689 void PictureLayerTiling::SetTilePriorityRects(
 690     float content_to_screen_scale,
 691     const gfx::Rect& visible_rect_in_content_space,
 692     const gfx::Rect& skewport,
 693     const gfx::Rect& soon_border_rect,
 694     const gfx::Rect& eventually_rect,
 695     const Occlusion& occlusion_in_layer_space) {
 696   current_visible_rect_ = visible_rect_in_content_space;
 697   current_skewport_rect_ = skewport;
 698   current_soon_border_rect_ = soon_border_rect;
 699   current_eventually_rect_ = eventually_rect;
 700   current_occlusion_in_layer_space_ = occlusion_in_layer_space;
 701   current_content_to_screen_scale_ = content_to_screen_scale;
 702
 703   gfx::Rect tiling_rect(tiling_size());
 704   has_visible_rect_tiles_ = tiling_rect.Intersects(current_visible_rect_);
 705   has_skewport_rect_tiles_ = tiling_rect.Intersects(current_skewport_rect_);
 706   has_soon_border_rect_tiles_ =
 707       tiling_rect.Intersects(current_soon_border_rect_);
 708   has_eventually_rect_tiles_ = tiling_rect.Intersects(current_eventually_rect_);
 709 }
 710
 711 void PictureLayerTiling::SetLiveTilesRect(
 712     const gfx::Rect& new_live_tiles_rect) {
 713   DCHECK(new_live_tiles_rect.IsEmpty() ||
 714          gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
 715       << "tiling_size: " << tiling_size().ToString()
 716       << " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
 717   if (live_tiles_rect_ == new_live_tiles_rect)
 718     return;
 719
 720   // Iterate to delete all tiles outside of our new live_tiles rect.
 721   for (TilingData::DifferenceIterator iter(&tiling_data_, live_tiles_rect_,
 722                                            new_live_tiles_rect);
 723        iter; ++iter) {
 724     RemoveTileAt(iter.index_x(), iter.index_y());
 725   }
 726
 727   // We don't rasterize non ideal resolution tiles, so there is no need to
 728   // create any new tiles.
 729   if (resolution_ == NON_IDEAL_RESOLUTION) {
 730     live_tiles_rect_.Intersect(new_live_tiles_rect);
 731     VerifyLiveTilesRect(false);
 732     return;
 733   }
 734
 735   // Iterate to allocate new tiles for all regions with newly exposed area.
 736   for (TilingData::DifferenceIterator iter(&tiling_data_, new_live_tiles_rect,
 737                                            live_tiles_rect_);
 738        iter; ++iter) {
 739     TileMapKey key(iter.index());
 740     if (ShouldCreateTileAt(key.index_x, key.index_y))
 741       CreateTile(key.index_x, key.index_y);
 742   }
 743
 744   live_tiles_rect_ = new_live_tiles_rect;
 745   VerifyLiveTilesRect(false);
 746 }
 747
 748 void PictureLayerTiling::VerifyLiveTilesRect(bool is_on_recycle_tree) const {
 749 #if DCHECK_IS_ON()
 750   for (auto it = tiles_.begin(); it != tiles_.end(); ++it) {
 751     if (!it->second)
 752       continue;
 753     TileMapKey key = it->first;
 754     DCHECK(key.index_x < tiling_data_.num_tiles_x())
 755         << this << " " << key.index_x << "," << key.index_y << " num_tiles_x "
 756         << tiling_data_.num_tiles_x() << " live_tiles_rect "
 757         << live_tiles_rect_.ToString();
 758     DCHECK(key.index_y < tiling_data_.num_tiles_y())
 759         << this << " " << key.index_x << "," << key.index_y << " num_tiles_y "
 760         << tiling_data_.num_tiles_y() << " live_tiles_rect "
 761         << live_tiles_rect_.ToString();
 762     DCHECK(tiling_data_.TileBounds(key.index_x, key.index_y)
 763                .Intersects(live_tiles_rect_))
 764         << this << " " << key.index_x << "," << key.index_y << " tile bounds "
 765         << tiling_data_.TileBounds(key.index_x, key.index_y).ToString()
 766         << " live_tiles_rect " << live_tiles_rect_.ToString();
 767   }
 768 #endif
 769 }
 770
 771 bool PictureLayerTiling::IsTileOccluded(const Tile* tile) const {
 772   // If this tile is not occluded on this tree, then it is not occluded.
 773   if (!IsTileOccludedOnCurrentTree(tile))
 774     return false;
 775
 776   // Otherwise, if this is the pending tree, we're done and the tile is
 777   // occluded.
 778   if (tree_ == PENDING_TREE)
 779     return true;
 780
 781   // On the active tree however, we need to check if this tile will be
 782   // unoccluded upon activation, in which case it has to be considered
 783   // unoccluded.
 784   const PictureLayerTiling* pending_twin =
 785       client_->GetPendingOrActiveTwinTiling(this);
 786   if (pending_twin) {
 787     // If there's a pending tile in the same position. Or if the pending twin
 788     // would have to be creating all tiles, then we don't need to worry about
 789     // occlusion on the twin.
 790     if (!TilingMatchesTileIndices(pending_twin) ||
 791         pending_twin->TileAt(tile->tiling_i_index(), tile->tiling_j_index())) {
 792       return true;
 793     }
 794     return pending_twin->IsTileOccludedOnCurrentTree(tile);
 795   }
 796   return true;
 797 }
 798
 799 bool PictureLayerTiling::IsTileOccludedOnCurrentTree(const Tile* tile) const {
 800   if (!current_occlusion_in_layer_space_.HasOcclusion())
 801     return false;
 802   gfx::Rect tile_query_rect =
 803       gfx::IntersectRects(tile->content_rect(), current_visible_rect_);
 804   // Explicitly check if the tile is outside the viewport. If so, we need to
 805   // return false, since occlusion for this tile is unknown.
 806   if (tile_query_rect.IsEmpty())
 807     return false;
 808
 809   if (contents_scale_ != 1.f) {
 810     tile_query_rect =
 811         gfx::ScaleToEnclosingRect(tile_query_rect, 1.f / contents_scale_);
 812   }
 813   return current_occlusion_in_layer_space_.IsOccluded(tile_query_rect);
 814 }
 815
 816 bool PictureLayerTiling::IsTileRequiredForActivation(const Tile* tile) const {
 817   if (tree_ == PENDING_TREE) {
 818     if (!can_require_tiles_for_activation_)
 819       return false;
 820
 821     if (resolution_ != HIGH_RESOLUTION)
 822       return false;
 823
 824     if (IsTileOccluded(tile))
 825       return false;
 826
 827     bool tile_is_visible =
 828         tile->content_rect().Intersects(current_visible_rect_);
 829     if (!tile_is_visible)
 830       return false;
 831
 832     if (client_->RequiresHighResToDraw())
 833       return true;
 834
 835     const PictureLayerTiling* active_twin =
 836         client_->GetPendingOrActiveTwinTiling(this);
 837     if (!active_twin || !TilingMatchesTileIndices(active_twin))
 838       return true;
 839
 840     if (active_twin->raster_source()->GetSize() != raster_source()->GetSize())
 841       return true;
 842
 843     if (active_twin->current_visible_rect_ != current_visible_rect_)
 844       return true;
 845
 846     Tile* twin_tile =
 847         active_twin->TileAt(tile->tiling_i_index(), tile->tiling_j_index());
 848     if (!twin_tile)
 849       return false;
 850     return true;
 851   }
 852
 853   DCHECK_EQ(tree_, ACTIVE_TREE);
 854   const PictureLayerTiling* pending_twin =
 855       client_->GetPendingOrActiveTwinTiling(this);
 856   // If we don't have a pending tree, or the pending tree will overwrite the
 857   // given tile, then it is not required for activation.
 858   if (!pending_twin || !TilingMatchesTileIndices(pending_twin) ||
 859       pending_twin->TileAt(tile->tiling_i_index(), tile->tiling_j_index())) {
 860     return false;
 861   }
 862   // Otherwise, ask the pending twin if this tile is required for activation.
 863   return pending_twin->IsTileRequiredForActivation(tile);
 864 }
 865
 866 bool PictureLayerTiling::IsTileRequiredForDraw(const Tile* tile) const {
 867   if (tree_ == PENDING_TREE)
 868     return false;
 869
 870   if (resolution_ != HIGH_RESOLUTION)
 871     return false;
 872
 873   bool tile_is_visible = current_visible_rect_.Intersects(tile->content_rect());
 874   if (!tile_is_visible)
 875     return false;
 876
 877   if (IsTileOccludedOnCurrentTree(tile))
 878     return false;
 879   return true;
 880 }
 881
 882 void PictureLayerTiling::UpdateRequiredStatesOnTile(Tile* tile) const {
 883   DCHECK(tile);
 884   tile->set_required_for_activation(IsTileRequiredForActivation(tile));
 885   tile->set_required_for_draw(IsTileRequiredForDraw(tile));
 886 }
 887
 888 PrioritizedTile PictureLayerTiling::MakePrioritizedTile(
 889     Tile* tile,
 890     PriorityRectType priority_rect_type) const {
 891   DCHECK(tile);
 892   DCHECK(
 893       raster_source()->CoversRect(tile->content_rect(), tile->contents_scale()))
 894       << "Recording rect: "
 895       << gfx::ScaleToEnclosingRect(tile->content_rect(),
 896                                    1.f / tile->contents_scale()).ToString();
 897
 898   return PrioritizedTile(tile, raster_source(),
 899                          ComputePriorityForTile(tile, priority_rect_type),
 900                          IsTileOccluded(tile));
 901 }
 902
 903 std::map<const Tile*, PrioritizedTile>
 904 PictureLayerTiling::UpdateAndGetAllPrioritizedTilesForTesting() const {
 905   std::map<const Tile*, PrioritizedTile> result;
 906   for (const auto& key_tile_pair : tiles_) {
 907     Tile* tile = key_tile_pair.second;
 908     UpdateRequiredStatesOnTile(tile);
 909     PrioritizedTile prioritized_tile =
 910         MakePrioritizedTile(tile, ComputePriorityRectTypeForTile(tile));
 911     result.insert(std::make_pair(prioritized_tile.tile(), prioritized_tile));
 912   }
 913   return result;
 914 }
 915
 916 TilePriority PictureLayerTiling::ComputePriorityForTile(
 917     const Tile* tile,
 918     PriorityRectType priority_rect_type) const {
 919   // TODO(vmpstr): See if this can be moved to iterators.
 920   DCHECK_EQ(ComputePriorityRectTypeForTile(tile), priority_rect_type);
 921   DCHECK_EQ(TileAt(tile->tiling_i_index(), tile->tiling_j_index()), tile);
 922
 923   TilePriority::PriorityBin priority_bin = client_->HasValidTilePriorities()
 924                                                ? TilePriority::NOW
 925                                                : TilePriority::EVENTUALLY;
 926   switch (priority_rect_type) {
 927     case VISIBLE_RECT:
 928       return TilePriority(resolution_, priority_bin, 0);
 929     case PENDING_VISIBLE_RECT:
 930       if (priority_bin < TilePriority::SOON)
 931         priority_bin = TilePriority::SOON;
 932       return TilePriority(resolution_, priority_bin, 0);
 933     case SKEWPORT_RECT:
 934     case SOON_BORDER_RECT:
 935       if (priority_bin < TilePriority::SOON)
 936         priority_bin = TilePriority::SOON;
 937       break;
 938     case EVENTUALLY_RECT:
 939       priority_bin = TilePriority::EVENTUALLY;
 940       break;
 941   }
 942
 943   gfx::Rect tile_bounds =
 944       tiling_data_.TileBounds(tile->tiling_i_index(), tile->tiling_j_index());
 945   DCHECK_GT(current_content_to_screen_scale_, 0.f);
 946   float distance_to_visible =
 947       current_visible_rect_.ManhattanInternalDistance(tile_bounds) *
 948       current_content_to_screen_scale_;
 949
 950   return TilePriority(resolution_, priority_bin, distance_to_visible);
 951 }
 952
 953 PictureLayerTiling::PriorityRectType
 954 PictureLayerTiling::ComputePriorityRectTypeForTile(const Tile* tile) const {
 955   DCHECK_EQ(TileAt(tile->tiling_i_index(), tile->tiling_j_index()), tile);
 956   gfx::Rect tile_bounds =
 957       tiling_data_.TileBounds(tile->tiling_i_index(), tile->tiling_j_index());
 958
 959   if (current_visible_rect_.Intersects(tile_bounds))
 960     return VISIBLE_RECT;
 961
 962   if (pending_visible_rect().Intersects(tile_bounds))
 963     return PENDING_VISIBLE_RECT;
 964
 965   if (current_skewport_rect_.Intersects(tile_bounds))
 966     return SKEWPORT_RECT;
 967
 968   if (current_soon_border_rect_.Intersects(tile_bounds))
 969     return SOON_BORDER_RECT;
 970
 971   DCHECK(current_eventually_rect_.Intersects(tile_bounds));
 972   return EVENTUALLY_RECT;
 973 }
 974
 975 void PictureLayerTiling::GetAllPrioritizedTilesForTracing(
 976     std::vector<PrioritizedTile>* prioritized_tiles) const {
 977   for (const auto& tile_pair : tiles_) {
 978     Tile* tile = tile_pair.second;
 979     prioritized_tiles->push_back(
 980         MakePrioritizedTile(tile, ComputePriorityRectTypeForTile(tile)));
 981   }
 982 }
 983
 984 void PictureLayerTiling::AsValueInto(
 985     base::trace_event::TracedValue* state) const {
 986   state->SetInteger("num_tiles", base::saturated_cast<int>(tiles_.size()));
 987   state->SetDouble("content_scale", contents_scale_);
 988   MathUtil::AddToTracedValue("visible_rect", current_visible_rect_, state);
 989   MathUtil::AddToTracedValue("skewport_rect", current_skewport_rect_, state);
 990   MathUtil::AddToTracedValue("soon_rect", current_soon_border_rect_, state);
 991   MathUtil::AddToTracedValue("eventually_rect", current_eventually_rect_,
 992                              state);
 993   MathUtil::AddToTracedValue("tiling_size", tiling_size(), state);
 994 }
 995
 996 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 997   size_t amount = 0;
 998   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 999     const Tile* tile = it->second;
1000     amount += tile->GPUMemoryUsageInBytes();
1001   }
1002   return amount;
1003 }
1004
1005 }  // namespace cc