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