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