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