cc/tiles/picture_layer_tiling.cc

   1 // Copyright 2012 The Chromium Authors
   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 <stddef.h>
   8
   9 #include <algorithm>
  10 #include <cmath>
  11 #include <limits>
  12 #include <set>
  13
  14 #include "base/check_op.h"
  15 #include "base/containers/flat_map.h"
  16 #include "base/numerics/safe_conversions.h"
  17 #include "base/trace_event/trace_event.h"
  18 #include "base/trace_event/traced_value.h"
  19 #include "cc/base/math_util.h"
  20 #include "cc/layers/picture_layer_impl.h"
  21 #include "cc/raster/raster_source.h"
  22 #include "cc/tiles/prioritized_tile.h"
  23 #include "cc/tiles/tile.h"
  24 #include "cc/tiles/tile_priority.h"
  25 #include "ui/gfx/geometry/point_conversions.h"
  26 #include "ui/gfx/geometry/rect_conversions.h"
  27 #include "ui/gfx/geometry/rect_f.h"
  28 #include "ui/gfx/geometry/size_conversions.h"
  29
  30 namespace cc {
  31
  32 PictureLayerTiling::PictureLayerTiling(
  33     WhichTree tree,
  34     const gfx::AxisTransform2d& raster_transform,
  35     scoped_refptr<RasterSource> raster_source,
  36     PictureLayerTilingClient* client,
  37     float min_preraster_distance,
  38     float max_preraster_distance,
  39     bool can_use_lcd_text)
  40     : raster_transform_(raster_transform),
  41       client_(client),
  42       tree_(tree),
  43       raster_source_(raster_source),
  44       min_preraster_distance_(min_preraster_distance),
  45       max_preraster_distance_(max_preraster_distance),
  46       can_use_lcd_text_(can_use_lcd_text) {
  47   DCHECK(!raster_source->IsSolidColor());
  48   DCHECK_GE(raster_transform.translation().x(), 0.f);
  49   DCHECK_LT(raster_transform.translation().x(), 1.f);
  50   DCHECK_GE(raster_transform.translation().y(), 0.f);
  51   DCHECK_LT(raster_transform.translation().y(), 1.f);
  52
  53 #if DCHECK_IS_ON()
  54   gfx::SizeF scaled_source_size(gfx::ScaleSize(
  55       gfx::SizeF(raster_source_->GetSize()), raster_transform.scale().x(),
  56       raster_transform.scale().y()));
  57   gfx::Size floored_size = gfx::ToFlooredSize(scaled_source_size);
  58   bool is_width_empty =
  59       !floored_size.width() &&
  60       !MathUtil::IsWithinEpsilon(scaled_source_size.width(), 1.f);
  61   bool is_height_empty =
  62       !floored_size.height() &&
  63       !MathUtil::IsWithinEpsilon(scaled_source_size.height(), 1.f);
  64   DCHECK(!is_width_empty && !is_height_empty)
  65       << "Tiling created with scale too small as contents become empty."
  66       << " Layer bounds: " << raster_source_->GetSize().ToString()
  67       << " Raster transform: " << raster_transform_.ToString();
  68 #endif
  69
  70   gfx::Rect content_bounds_rect =
  71       EnclosingContentsRectFromLayerRect(gfx::Rect(raster_source_->GetSize()));
  72   gfx::Size tiling_size = gfx::Size(content_bounds_rect.bottom_right().x(),
  73                                     content_bounds_rect.bottom_right().y());
  74   tiling_data_.SetTilingSize(tiling_size);
  75   gfx::Size tile_size = client_->CalculateTileSize(tiling_size);
  76   tiling_data_.SetMaxTextureSize(tile_size);
  77 }
  78
  79 PictureLayerTiling::~PictureLayerTiling() = default;
  80
  81 Tile* PictureLayerTiling::CreateTile(const Tile::CreateInfo& info) {
  82   const int i = info.tiling_i_index;
  83   const int j = info.tiling_j_index;
  84   TileMapKey key(i, j);
  85   DCHECK(tiles_.find(key) == tiles_.end());
  86
  87   if (!raster_source_->IntersectsRect(info.enclosing_layer_rect, *client_))
  88     return nullptr;
  89
  90   all_tiles_done_ = false;
  91   std::unique_ptr<Tile> tile = client_->CreateTile(info);
  92   Tile* raw_ptr = tile.get();
  93   tiles_[key] = std::move(tile);
  94   return raw_ptr;
  95 }
  96
  97 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
  98   const PictureLayerTiling* active_twin =
  99       tree_ == PENDING_TREE ? client_->GetPendingOrActiveTwinTiling(this)
 100                             : nullptr;
 101   const Region* invalidation =
 102       active_twin ? client_->GetPendingInvalidation() : nullptr;
 103
 104   bool include_borders = false;
 105   for (TilingData::Iterator iter(&tiling_data_, live_tiles_rect_,
 106                                  include_borders);
 107        iter; ++iter) {
 108     TileMapKey key(iter.index());
 109     auto find = tiles_.find(key);
 110     if (find != tiles_.end())
 111       continue;
 112
 113     Tile::CreateInfo info = CreateInfoForTile(key.index_x, key.index_y);
 114     if (ShouldCreateTileAt(info)) {
 115       Tile* tile = CreateTile(info);
 116
 117       // If this is the pending tree, then the active twin tiling may contain
 118       // the previous content ID of these tiles. In that case, we need only
 119       // partially raster the tile content.
 120       if (tile && invalidation && TilingMatchesTileIndices(active_twin)) {
 121         if (const Tile* old_tile =
 122                 active_twin->TileAt(key.index_x, key.index_y)) {
 123           gfx::Rect tile_rect = tile->content_rect();
 124           gfx::Rect invalidated;
 125           for (gfx::Rect rect : *invalidation) {
 126             gfx::Rect invalid_content_rect =
 127                 EnclosingContentsRectFromLayerRect(rect);
 128             invalid_content_rect.Intersect(tile_rect);
 129             invalidated.Union(invalid_content_rect);
 130           }
 131           tile->SetInvalidated(invalidated, old_tile->id());
 132         }
 133       }
 134     }
 135   }
 136   VerifyLiveTilesRect();
 137 }
 138
 139 void PictureLayerTiling::TakeTilesAndPropertiesFrom(
 140     PictureLayerTiling* pending_twin,
 141     const Region& layer_invalidation) {
 142   SetRasterSourceAndResize(pending_twin->raster_source_);
 143
 144   RemoveTilesInRegion(layer_invalidation, false /* recreate tiles */);
 145
 146   resolution_ = pending_twin->resolution_;
 147   bool create_missing_tiles = false;
 148   if (live_tiles_rect_.IsEmpty()) {
 149     live_tiles_rect_ = pending_twin->live_tiles_rect();
 150     create_missing_tiles = true;
 151   } else {
 152     SetLiveTilesRect(pending_twin->live_tiles_rect());
 153   }
 154
 155   while (!pending_twin->tiles_.empty()) {
 156     auto pending_iter = pending_twin->tiles_.begin();
 157     pending_iter->second->set_tiling(this);
 158     tiles_[pending_iter->first] = std::move(pending_iter->second);
 159     pending_twin->tiles_.erase(pending_iter);
 160   }
 161   all_tiles_done_ &= pending_twin->all_tiles_done_;
 162
 163   DCHECK(pending_twin->tiles_.empty());
 164   pending_twin->all_tiles_done_ = true;
 165
 166   if (create_missing_tiles)
 167     CreateMissingTilesInLiveTilesRect();
 168
 169   VerifyLiveTilesRect();
 170
 171   SetTilePriorityRects(pending_twin->current_content_to_screen_scale_,
 172                        pending_twin->current_visible_rect_,
 173                        pending_twin->current_skewport_rect_,
 174                        pending_twin->current_soon_border_rect_,
 175                        pending_twin->current_eventually_rect_,
 176                        pending_twin->current_occlusion_in_layer_space_);
 177 }
 178
 179 void PictureLayerTiling::SetRasterSourceAndResize(
 180     scoped_refptr<RasterSource> raster_source) {
 181   DCHECK(!raster_source->IsSolidColor());
 182   gfx::Size old_layer_bounds = raster_source_->GetSize();
 183   raster_source_ = std::move(raster_source);
 184   gfx::Size new_layer_bounds = raster_source_->GetSize();
 185   gfx::Rect content_rect =
 186       EnclosingContentsRectFromLayerRect(gfx::Rect(new_layer_bounds));
 187   DCHECK(content_rect.origin() == gfx::Point());
 188   gfx::Size tile_size = client_->CalculateTileSize(content_rect.size());
 189
 190   if (tile_size != tiling_data_.max_texture_size()) {
 191     tiling_data_.SetTilingSize(content_rect.size());
 192     tiling_data_.SetMaxTextureSize(tile_size);
 193     // When the tile size changes, the TilingData positions no longer work
 194     // as valid keys to the TileMap, so just drop all tiles and clear the live
 195     // tiles rect.
 196     Reset();
 197     return;
 198   }
 199
 200   if (old_layer_bounds == new_layer_bounds)
 201     return;
 202
 203   // The SetLiveTilesRect() method would drop tiles outside the new bounds,
 204   // but may do so incorrectly if resizing the tiling causes the number of
 205   // tiles in the tiling_data_ to change.
 206   int before_left = tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.x());
 207   int before_top = tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.y());
 208   int before_right =
 209       tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 210   int before_bottom =
 211       tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 212
 213   // The live_tiles_rect_ is clamped to stay within the tiling size as we
 214   // change it.
 215   live_tiles_rect_.Intersect(content_rect);
 216   tiling_data_.SetTilingSize(content_rect.size());
 217
 218   int after_right = -1;
 219   int after_bottom = -1;
 220   if (!live_tiles_rect_.IsEmpty()) {
 221     after_right =
 222         tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
 223     after_bottom =
 224         tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
 225   }
 226
 227   // There is no recycled twin since this is run on the pending tiling
 228   // during commit, and on the active tree during activate.
 229   // Drop tiles outside the new layer bounds if the layer shrank.
 230   for (int i = after_right + 1; i <= before_right; ++i) {
 231     for (int j = before_top; j <= before_bottom; ++j)
 232       TakeTileAt(i, j);
 233   }
 234   for (int i = before_left; i <= after_right; ++i) {
 235     for (int j = after_bottom + 1; j <= before_bottom; ++j)
 236       TakeTileAt(i, j);
 237   }
 238
 239   if (after_right > before_right) {
 240     DCHECK_EQ(after_right, before_right + 1);
 241     for (int j = before_top; j <= after_bottom; ++j) {
 242       Tile::CreateInfo info = CreateInfoForTile(after_right, j);
 243       if (ShouldCreateTileAt(info))
 244         CreateTile(info);
 245     }
 246   }
 247   if (after_bottom > before_bottom) {
 248     // Using the smallest horizontal bound here makes sure we don't
 249     // create tiles twice and don't iterate into deleted tiles.
 250     int boundary_right = std::min(after_right, before_right);
 251     DCHECK_EQ(after_bottom, before_bottom + 1);
 252     for (int i = before_left; i <= boundary_right; ++i) {
 253       Tile::CreateInfo info = CreateInfoForTile(i, after_bottom);
 254       if (ShouldCreateTileAt(info))
 255         CreateTile(info);
 256     }
 257   }
 258 }
 259
 260 void PictureLayerTiling::Invalidate(const Region& layer_invalidation) {
 261   DCHECK(tree_ != ACTIVE_TREE || !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
 272   base::flat_map<TileMapKey, gfx::Rect> remove_tiles;
 273   gfx::Rect expanded_live_tiles_rect =
 274       tiling_data_.ExpandRectToTileBounds(live_tiles_rect_);
 275   for (gfx::Rect layer_rect : layer_invalidation) {
 276     // The pixels which are invalid in content space.
 277     gfx::Rect invalid_content_rect =
 278         EnclosingContentsRectFromLayerRect(layer_rect);
 279     gfx::Rect coverage_content_rect = invalid_content_rect;
 280     // Avoid needless work by not bothering to invalidate where there aren't
 281     // tiles.
 282     coverage_content_rect.Intersect(expanded_live_tiles_rect);
 283     if (coverage_content_rect.IsEmpty())
 284       continue;
 285     // Since the content_rect needs to invalidate things that only touch a
 286     // border of a tile, we need to include the borders while iterating.
 287     bool include_borders = true;
 288     for (TilingData::Iterator iter(&tiling_data_, coverage_content_rect,
 289                                    include_borders);
 290          iter; ++iter) {
 291       // This also adds the TileMapKey to the map.
 292       remove_tiles[TileMapKey(iter.index())].Union(invalid_content_rect);
 293     }
 294   }
 295
 296   for (const auto& pair : remove_tiles) {
 297     const TileMapKey& key = pair.first;
 298     const gfx::Rect& invalid_content_rect = pair.second;
 299     // TODO(danakj): This old_tile will not exist if we are committing to a
 300     // pending tree since there is no tile there to remove, which prevents
 301     // tiles from knowing the invalidation rect and content id. crbug.com/490847
 302     std::unique_ptr<Tile> old_tile = TakeTileAt(key.index_x, key.index_y);
 303     if (recreate_tiles && old_tile) {
 304       Tile::CreateInfo info = CreateInfoForTile(key.index_x, key.index_y);
 305       if (Tile* tile = CreateTile(info))
 306         tile->SetInvalidated(invalid_content_rect, old_tile->id());
 307     }
 308   }
 309 }
 310
 311 Tile::CreateInfo PictureLayerTiling::CreateInfoForTile(int i, int j) const {
 312   gfx::Rect tile_rect = tiling_data_.TileBoundsWithBorder(i, j);
 313   tile_rect.set_size(tiling_data_.max_texture_size());
 314   gfx::Rect enclosing_layer_rect =
 315       EnclosingLayerRectFromContentsRect(tile_rect);
 316   return Tile::CreateInfo{this,
 317                           i,
 318                           j,
 319                           enclosing_layer_rect,
 320                           tile_rect,
 321                           raster_transform_,
 322                           can_use_lcd_text_};
 323 }
 324
 325 bool PictureLayerTiling::ShouldCreateTileAt(
 326     const Tile::CreateInfo& info) const {
 327   const int i = info.tiling_i_index;
 328   const int j = info.tiling_j_index;
 329   // Active tree should always create a tile. The reason for this is that active
 330   // tree represents content that we draw on screen, which means that whenever
 331   // we check whether a tile should exist somewhere, the answer is yes. This
 332   // doesn't mean it will actually be created (if raster source doesn't cover
 333   // the tile for instance). Pending tree, on the other hand, should only be
 334   // creating tiles that are different from the current active tree, which is
 335   // represented by the logic in the rest of the function.
 336   if (tree_ == ACTIVE_TREE)
 337     return true;
 338
 339   // If the pending tree has no active twin, then it needs to create all tiles.
 340   const PictureLayerTiling* active_twin =
 341       client_->GetPendingOrActiveTwinTiling(this);
 342   if (!active_twin)
 343     return true;
 344
 345   // Pending tree will override the entire active tree if indices don't match.
 346   if (!TilingMatchesTileIndices(active_twin))
 347     return true;
 348
 349   // If our settings don't match the active twin, it means that the active
 350   // tiles will all be removed when we activate. So we need all the tiles on the
 351   // pending tree to be created. See
 352   // PictureLayerTilingSet::CopyTilingsAndPropertiesFromPendingTwin.
 353   if (can_use_lcd_text() != active_twin->can_use_lcd_text() ||
 354       raster_transform() != active_twin->raster_transform())
 355     return true;
 356
 357   // If the active tree can't create a tile, because of its raster source, then
 358   // the pending tree should create one.
 359   if (!active_twin->raster_source()->IntersectsRect(info.enclosing_layer_rect,
 360                                                     *active_twin->client()))
 361     return true;
 362
 363   const Region* layer_invalidation = client_->GetPendingInvalidation();
 364
 365   // If this tile is invalidated, then the pending tree should create one.
 366   // Do the intersection test in content space to match the corresponding check
 367   // on the active tree and avoid floating point inconsistencies.
 368   for (gfx::Rect layer_rect : *layer_invalidation) {
 369     gfx::Rect invalid_content_rect =
 370         EnclosingContentsRectFromLayerRect(layer_rect);
 371     if (invalid_content_rect.Intersects(info.content_rect))
 372       return true;
 373   }
 374   // If the active tree doesn't have a tile here, but it's in the pending tree's
 375   // visible rect, then the pending tree should create a tile. This can happen
 376   // if the pending visible rect is outside of the active tree's live tiles
 377   // rect. In those situations, we need to block activation until we're ready to
 378   // display content, which will have to come from the pending tree.
 379   if (!active_twin->TileAt(i, j) &&
 380       current_visible_rect_.Intersects(info.content_rect))
 381     return true;
 382
 383   // In all other cases, the pending tree doesn't need to create a tile.
 384   return false;
 385 }
 386
 387 bool PictureLayerTiling::TilingMatchesTileIndices(
 388     const PictureLayerTiling* twin) const {
 389   return tiling_data_.max_texture_size() ==
 390          twin->tiling_data_.max_texture_size();
 391 }
 392
 393 PictureLayerTiling::CoverageIterator::CoverageIterator() = default;
 394
 395 PictureLayerTiling::CoverageIterator::CoverageIterator(
 396     const PictureLayerTiling* tiling,
 397     float coverage_scale,
 398     const gfx::Rect& coverage_rect)
 399     : tiling_(tiling),
 400       coverage_rect_(coverage_rect),
 401       coverage_to_content_(PreScaleAxisTransform2d(tiling->raster_transform(),
 402                                                    1 / coverage_scale)) {
 403   DCHECK(tiling_);
 404   // In order to avoid artifacts in geometry_rect scaling and clamping to ints,
 405   // the |coverage_scale| should always be at least as big as the tiling's
 406   // raster scales.
 407   DCHECK_GE(coverage_scale, tiling_->contents_scale_key());
 408
 409   // Clamp |coverage_rect| to the bounds of this tiling's raster source.
 410   coverage_rect_max_bounds_ =
 411       gfx::ScaleToCeiledSize(tiling->raster_source_->GetSize(), coverage_scale);
 412   coverage_rect_.Intersect(gfx::Rect(coverage_rect_max_bounds_));
 413   if (coverage_rect_.IsEmpty())
 414     return;
 415
 416   // Find the indices of the texel samples that enclose the rect we want to
 417   // cover.
 418   // Because we don't know the target transform at this point, we have to be
 419   // pessimistic, i.e. assume every point (a pair of real number, not necessary
 420   // snapped to a pixel sample) inside of the content rect may be sampled.
 421   // This code maps the boundary points into contents space, then find out the
 422   // enclosing texture samples. For example, assume we have:
 423   // coverage_scale : content_scale = 1.23 : 1
 424   // coverage_rect = (l:123, t:234, r:345, b:456)
 425   // Then it follows that:
 426   // content_rect = (l:100.00, t:190.24, r:280.49, b:370.73)
 427   // Without MSAA, the sample point of a texel is at the center of that texel,
 428   // thus the sample points we need to cover content_rect are:
 429   // wanted_texels(sample coordinates) = (l:99.5, t:189.5, r:280.5, b:371.5)
 430   // Or in integer index:
 431   // wanted_texels(integer index) = (l:99, t:189, r:280, b:371)
 432   gfx::RectF content_rect =
 433       coverage_to_content_.MapRect(gfx::RectF(coverage_rect_));
 434   content_rect.Offset(-0.5f, -0.5f);
 435   gfx::Rect wanted_texels = gfx::ToEnclosingRect(content_rect);
 436
 437   const TilingData& data = tiling_->tiling_data_;
 438   left_ = data.LastBorderTileXIndexFromSrcCoord(wanted_texels.x());
 439   top_ = data.LastBorderTileYIndexFromSrcCoord(wanted_texels.y());
 440   right_ = std::max(
 441       left_, data.FirstBorderTileXIndexFromSrcCoord(wanted_texels.right()));
 442   bottom_ = std::max(
 443       top_, data.FirstBorderTileYIndexFromSrcCoord(wanted_texels.bottom()));
 444
 445   tile_i_ = left_ - 1;
 446   tile_j_ = top_;
 447   ++(*this);
 448 }
 449
 450 PictureLayerTiling::CoverageIterator::~CoverageIterator() = default;
 451
 452 PictureLayerTiling::CoverageIterator&
 453 PictureLayerTiling::CoverageIterator::operator++() {
 454   if (tile_j_ > bottom_)
 455     return *this;
 456
 457   bool first_time = tile_i_ < left_;
 458   while (true) {
 459     bool new_row = false;
 460     tile_i_++;
 461     if (tile_i_ > right_) {
 462       tile_i_ = left_;
 463       tile_j_++;
 464       new_row = true;
 465       if (tile_j_ > bottom_) {
 466         current_tile_ = nullptr;
 467         break;
 468       }
 469     }
 470
 471     DCHECK_LT(tile_i_, tiling_->tiling_data_.num_tiles_x());
 472     DCHECK_LT(tile_j_, tiling_->tiling_data_.num_tiles_y());
 473     current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 474
 475     gfx::Rect geometry_rect_candidate = ComputeGeometryRect();
 476
 477     // This can happen due to floating point inprecision when calculating the
 478     // |wanted_texels| area in the constructor.
 479     if (geometry_rect_candidate.IsEmpty())
 480       continue;
 481
 482     gfx::Rect last_geometry_rect = current_geometry_rect_;
 483     current_geometry_rect_ = geometry_rect_candidate;
 484
 485     if (first_time)
 486       break;
 487
 488     // Iteration happens left->right, top->bottom.  Running off the bottom-right
 489     // edge is handled by the intersection above with dest_rect_.  Here we make
 490     // sure that the new current geometry rect doesn't overlap with the last.
 491     int min_left;
 492     int min_top;
 493     if (new_row) {
 494       min_left = coverage_rect_.x();
 495       min_top = last_geometry_rect.bottom();
 496     } else {
 497       min_left = last_geometry_rect.right();
 498       min_top = last_geometry_rect.y();
 499     }
 500
 501     int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 502     int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 503     current_geometry_rect_.Inset(
 504         gfx::Insets::TLBR(inset_top, inset_left, 0, 0));
 505
 506 #if DCHECK_IS_ON()
 507     // Sometimes we run into an extreme case where we are at the edge of integer
 508     // precision. When doing so, rect calculations may end up changing values
 509     // unexpectedly. Unfortunately, there isn't much we can do at this point, so
 510     // we just do the correctness checks if both y and x offsets are
 511     // 'reasonable', meaning they are less than the specified value.
 512     static constexpr int kReasonableOffsetForDcheck = 100'000'000;
 513     if (!new_row && current_geometry_rect_.x() <= kReasonableOffsetForDcheck &&
 514         current_geometry_rect_.y() <= kReasonableOffsetForDcheck) {
 515       DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 516       DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 517       DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 518     }
 519 #endif
 520
 521     break;
 522   }
 523   return *this;
 524 }
 525
 526 gfx::Rect PictureLayerTiling::CoverageIterator::ComputeGeometryRect() const {
 527   // Calculate the current geometry rect. As we reserved overlap between tiles
 528   // to accommodate bilinear filtering and rounding errors in destination
 529   // space, the geometry rect might overlap on the edges.
 530   gfx::RectF texel_extent = tiling_->tiling_data_.TexelExtent(tile_i_, tile_j_);
 531   {
 532     // Adjust tile extent to accommodate numerical errors.
 533     //
 534     // Allow the tile to overreach by 1/1024 texels to avoid seams between
 535     // tiles. The constant 1/1024 is picked by the fact that with bilinear
 536     // filtering, the maximum error in color value introduced by clamping
 537     // error in both u/v axis can't exceed
 538     // 255 * (1 - (1 - 1/1024) * (1 - 1/1024)) ~= 0.498
 539     // i.e. The color value can never flip over a rounding threshold.
 540     constexpr float epsilon = 1.f / 1024.f;
 541     texel_extent.Inset(-epsilon);
 542   }
 543
 544   // Convert texel_extent to coverage scale, which is what we have to report
 545   // geometry_rect in.
 546   gfx::Rect candidate =
 547       gfx::ToEnclosedRect(coverage_to_content_.InverseMapRect(texel_extent));
 548   {
 549     // Adjust external edges to cover the whole layer in dest space.
 550     //
 551     // For external edges, extend the tile to scaled layer bounds. This is
 552     // needed to fully cover the coverage space because the sample extent
 553     // doesn't cover the last 0.5 texel to layer edge, and also the coverage
 554     // space can be rounded up for up to 1 pixel. This overhang will never be
 555     // sampled as the AA fragment shader clamps sample coordinate and
 556     // antialiasing itself.
 557     const TilingData& data = tiling_->tiling_data_;
 558     candidate.Inset(gfx::Insets::TLBR(
 559         tile_j_ ? 0 : -candidate.y(), tile_i_ ? 0 : -candidate.x(),
 560         (tile_j_ != data.num_tiles_y() - 1)
 561             ? 0
 562             : candidate.bottom() - coverage_rect_max_bounds_.height(),
 563         (tile_i_ != data.num_tiles_x() - 1)
 564             ? 0
 565             : candidate.right() - coverage_rect_max_bounds_.width()));
 566   }
 567
 568   candidate.Intersect(coverage_rect_);
 569   return candidate;
 570 }
 571
 572 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 573   return current_geometry_rect_;
 574 }
 575
 576 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 577   auto tex_origin = gfx::PointF(
 578       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin());
 579
 580   // Convert from coverage space => content space => texture space.
 581   gfx::RectF texture_rect(current_geometry_rect_);
 582   texture_rect = coverage_to_content_.MapRect(texture_rect);
 583   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 584
 585   return texture_rect;
 586 }
 587
 588 std::unique_ptr<Tile> PictureLayerTiling::TakeTileAt(int i, int j) {
 589   auto found = tiles_.find(TileMapKey(i, j));
 590   if (found == tiles_.end())
 591     return nullptr;
 592   std::unique_ptr<Tile> result = std::move(found->second);
 593   tiles_.erase(found);
 594   return result;
 595 }
 596
 597 void PictureLayerTiling::Reset() {
 598   live_tiles_rect_ = gfx::Rect();
 599   tiles_.clear();
 600   all_tiles_done_ = true;
 601 }
 602
 603 void PictureLayerTiling::ComputeTilePriorityRects(
 604     const gfx::Rect& visible_rect_in_layer_space,
 605     const gfx::Rect& skewport_in_layer_space,
 606     const gfx::Rect& soon_border_rect_in_layer_space,
 607     const gfx::Rect& eventually_rect_in_layer_space,
 608     float ideal_contents_scale,
 609     const Occlusion& occlusion_in_layer_space) {
 610   // If we have, or had occlusions, mark the tiles as 'not done' to ensure that
 611   // we reiterate the tiles for rasterization.
 612   if (occlusion_in_layer_space.HasOcclusion() ||
 613       current_occlusion_in_layer_space_.HasOcclusion()) {
 614     set_all_tiles_done(false);
 615   }
 616
 617   const float content_to_screen_scale =
 618       ideal_contents_scale / contents_scale_key();
 619
 620   const gfx::Rect* input_rects[] = {
 621       &visible_rect_in_layer_space, &skewport_in_layer_space,
 622       &soon_border_rect_in_layer_space, &eventually_rect_in_layer_space};
 623   gfx::Rect output_rects[4];
 624   for (size_t i = 0; i < std::size(input_rects); ++i)
 625     output_rects[i] = EnclosingContentsRectFromLayerRect(*input_rects[i]);
 626   // Make sure the eventually rect is aligned to tile bounds.
 627   output_rects[3] =
 628       tiling_data_.ExpandRectIgnoringBordersToTileBounds(output_rects[3]);
 629
 630   SetTilePriorityRects(content_to_screen_scale, output_rects[0],
 631                        output_rects[1], output_rects[2], output_rects[3],
 632                        occlusion_in_layer_space);
 633   SetLiveTilesRect(output_rects[3]);
 634 }
 635
 636 void PictureLayerTiling::SetTilePriorityRects(
 637     float content_to_screen_scale,
 638     const gfx::Rect& visible_rect_in_content_space,
 639     const gfx::Rect& skewport,
 640     const gfx::Rect& soon_border_rect,
 641     const gfx::Rect& eventually_rect,
 642     const Occlusion& occlusion_in_layer_space) {
 643   current_visible_rect_ = visible_rect_in_content_space;
 644   current_skewport_rect_ = skewport;
 645   current_soon_border_rect_ = soon_border_rect;
 646   current_eventually_rect_ = eventually_rect;
 647   current_occlusion_in_layer_space_ = occlusion_in_layer_space;
 648   current_content_to_screen_scale_ = content_to_screen_scale;
 649
 650   gfx::Rect tiling_rect(tiling_size());
 651   has_visible_rect_tiles_ = tiling_rect.Intersects(current_visible_rect_);
 652   has_skewport_rect_tiles_ = tiling_rect.Intersects(current_skewport_rect_);
 653   has_soon_border_rect_tiles_ =
 654       tiling_rect.Intersects(current_soon_border_rect_);
 655   has_eventually_rect_tiles_ = tiling_rect.Intersects(current_eventually_rect_);
 656
 657   // Note that we use the largest skewport extent from the viewport as the
 658   // "skewport extent". Also note that this math can't produce negative numbers,
 659   // since skewport.Contains(visible_rect) is always true.
 660   max_skewport_extent_in_screen_space_ =
 661       current_content_to_screen_scale_ *
 662       std::max(
 663           {current_visible_rect_.x() - current_skewport_rect_.x(),
 664            current_skewport_rect_.right() - current_visible_rect_.right(),
 665            current_visible_rect_.y() - current_skewport_rect_.y(),
 666            current_skewport_rect_.bottom() - current_visible_rect_.bottom()});
 667 }
 668
 669 void PictureLayerTiling::SetLiveTilesRect(
 670     const gfx::Rect& new_live_tiles_rect) {
 671   DCHECK(new_live_tiles_rect.IsEmpty() ||
 672          gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
 673       << "tiling_size: " << tiling_size().ToString()
 674       << " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
 675   if (live_tiles_rect_ == new_live_tiles_rect)
 676     return;
 677
 678   // Iterate to delete all tiles outside of our new live_tiles rect.
 679   for (TilingData::DifferenceIterator iter(&tiling_data_, live_tiles_rect_,
 680                                            new_live_tiles_rect);
 681        iter; ++iter) {
 682     TakeTileAt(iter.index_x(), iter.index_y());
 683   }
 684
 685   // We don't rasterize non ideal resolution tiles, so there is no need to
 686   // create any new tiles.
 687   if (resolution_ == NON_IDEAL_RESOLUTION) {
 688     live_tiles_rect_.Intersect(new_live_tiles_rect);
 689     VerifyLiveTilesRect();
 690     return;
 691   }
 692
 693   // Iterate to allocate new tiles for all regions with newly exposed area.
 694   for (TilingData::DifferenceIterator iter(&tiling_data_, new_live_tiles_rect,
 695                                            live_tiles_rect_);
 696        iter; ++iter) {
 697     Tile::CreateInfo info = CreateInfoForTile(iter.index_x(), iter.index_y());
 698     if (ShouldCreateTileAt(info))
 699       CreateTile(info);
 700   }
 701
 702   live_tiles_rect_ = new_live_tiles_rect;
 703   VerifyLiveTilesRect();
 704 }
 705
 706 void PictureLayerTiling::VerifyLiveTilesRect() const {
 707 #if DCHECK_IS_ON()
 708   for (auto it = tiles_.begin(); it != tiles_.end(); ++it) {
 709     DCHECK(it->second);
 710     TileMapKey key = it->first;
 711     DCHECK(key.index_x < tiling_data_.num_tiles_x())
 712         << this << " " << key.index_x << "," << key.index_y << " num_tiles_x "
 713         << tiling_data_.num_tiles_x() << " live_tiles_rect "
 714         << live_tiles_rect_.ToString();
 715     DCHECK(key.index_y < tiling_data_.num_tiles_y())
 716         << this << " " << key.index_x << "," << key.index_y << " num_tiles_y "
 717         << tiling_data_.num_tiles_y() << " live_tiles_rect "
 718         << live_tiles_rect_.ToString();
 719     DCHECK(tiling_data_.TileBounds(key.index_x, key.index_y)
 720                .Intersects(live_tiles_rect_))
 721         << this << " " << key.index_x << "," << key.index_y << " tile bounds "
 722         << tiling_data_.TileBounds(key.index_x, key.index_y).ToString()
 723         << " live_tiles_rect " << live_tiles_rect_.ToString();
 724   }
 725 #endif
 726 }
 727
 728 bool PictureLayerTiling::IsTileOccludedOnCurrentTree(const Tile* tile) const {
 729   if (!current_occlusion_in_layer_space_.HasOcclusion())
 730     return false;
 731   gfx::Rect tile_bounds =
 732       tiling_data_.TileBounds(tile->tiling_i_index(), tile->tiling_j_index());
 733   gfx::Rect tile_query_rect =
 734       gfx::IntersectRects(tile_bounds, current_visible_rect_);
 735   // Explicitly check if the tile is outside the viewport. If so, we need to
 736   // return false, since occlusion for this tile is unknown.
 737   if (tile_query_rect.IsEmpty())
 738     return false;
 739
 740   tile_query_rect = EnclosingLayerRectFromContentsRect(tile_query_rect);
 741   return current_occlusion_in_layer_space_.IsOccluded(tile_query_rect);
 742 }
 743
 744 bool PictureLayerTiling::ShouldDecodeCheckeredImagesForTile(
 745     const Tile* tile) const {
 746   // If this is the pending tree and the tile is not occluded, any checkered
 747   // images on this tile should be decoded.
 748   if (tree_ == PENDING_TREE)
 749     return !IsTileOccludedOnCurrentTree(tile);
 750
 751   DCHECK_EQ(tree_, ACTIVE_TREE);
 752   const PictureLayerTiling* pending_twin =
 753       client_->GetPendingOrActiveTwinTiling(this);
 754
 755   // If we don't have a pending twin, then 2 cases are possible. Either we don't
 756   // have a pending tree, in which case we should be decoding images for tiles
 757   // which are unoccluded.
 758   // If we do have a pending tree, then not having a twin implies that this
 759   // tiling will be evicted upon activation. TODO(khushalsagar): Plumb this
 760   // information here and return false for this case.
 761   if (!pending_twin)
 762     return !IsTileOccludedOnCurrentTree(tile);
 763
 764   // If the tile will be replaced upon activation, then we don't need to process
 765   // it for checkered images. Since once the pending tree is activated, it is
 766   // the new active tree's content that we will invalidate and replace once the
 767   // decode finishes.
 768   if (!TilingMatchesTileIndices(pending_twin) ||
 769       pending_twin->TileAt(tile->tiling_i_index(), tile->tiling_j_index())) {
 770     return false;
 771   }
 772
 773   // Ask the pending twin if this tile will become occluded upon activation.
 774   return !pending_twin->IsTileOccludedOnCurrentTree(tile);
 775 }
 776
 777 void PictureLayerTiling::UpdateRequiredStatesOnTile(Tile* tile) const {
 778   tile->set_required_for_activation(IsTileRequiredForActivation(
 779       tile, [this](const Tile* tile) { return IsTileVisible(tile); },
 780       IsTileOccluded(tile)));
 781   tile->set_required_for_draw(IsTileRequiredForDraw(
 782       tile, [this](const Tile* tile) { return IsTileVisible(tile); }));
 783 }
 784
 785 PrioritizedTile PictureLayerTiling::MakePrioritizedTile(
 786     Tile* tile,
 787     PriorityRectType priority_rect_type,
 788     bool is_tile_occluded) const {
 789   DCHECK(tile);
 790   DCHECK(
 791       raster_source()->IntersectsRect(tile->enclosing_layer_rect(), *client_))
 792       << "Recording rect: "
 793       << EnclosingLayerRectFromContentsRect(tile->content_rect()).ToString();
 794
 795   tile->set_required_for_activation(IsTileRequiredForActivation(
 796       tile,
 797       [priority_rect_type](const Tile*) {
 798         return priority_rect_type == VISIBLE_RECT;
 799       },
 800       is_tile_occluded));
 801   tile->set_required_for_draw(
 802       IsTileRequiredForDraw(tile, [priority_rect_type](const Tile*) {
 803         return priority_rect_type == VISIBLE_RECT;
 804       }));
 805
 806   const auto& tile_priority =
 807       ComputePriorityForTile(tile, priority_rect_type, is_tile_occluded);
 808   DCHECK((!tile->required_for_activation() && !tile->required_for_draw()) ||
 809          tile_priority.priority_bin == TilePriority::NOW ||
 810          !client_->HasValidTilePriorities());
 811
 812   // Note that TileManager will consider this flag but may rasterize the tile
 813   // anyway (if tile is required for activation for example). We should process
 814   // the tile for images only if it's further than half of the skewport extent.
 815   bool process_for_images_only =
 816       tile_priority.distance_to_visible > min_preraster_distance_ &&
 817       (tile_priority.distance_to_visible > max_preraster_distance_ ||
 818        tile_priority.distance_to_visible >
 819            0.5f * max_skewport_extent_in_screen_space_);
 820
 821   // If the tile is within max_skewport_extent and a scroll interaction
 822   // experiencing checkerboarding is currently taking place, then
 823   // continue to rasterize the tile right now rather than for images only.
 824   if (tile_priority.distance_to_visible <
 825           max_skewport_extent_in_screen_space_ &&
 826       client_->ScrollInteractionInProgress() &&
 827       client_->CurrentScrollCheckerboardsDueToNoRecording())
 828     process_for_images_only = false;
 829   return PrioritizedTile(tile, this, tile_priority, is_tile_occluded,
 830                          process_for_images_only,
 831                          ShouldDecodeCheckeredImagesForTile(tile));
 832 }
 833
 834 std::map<const Tile*, PrioritizedTile>
 835 PictureLayerTiling::UpdateAndGetAllPrioritizedTilesForTesting() const {
 836   std::map<const Tile*, PrioritizedTile> result;
 837   for (const auto& key_tile_pair : tiles_) {
 838     Tile* tile = key_tile_pair.second.get();
 839     PrioritizedTile prioritized_tile = MakePrioritizedTile(
 840         tile, ComputePriorityRectTypeForTile(tile), IsTileOccluded(tile));
 841     result.insert(std::make_pair(prioritized_tile.tile(), prioritized_tile));
 842   }
 843   return result;
 844 }
 845
 846 TilePriority PictureLayerTiling::ComputePriorityForTile(
 847     const Tile* tile,
 848     PriorityRectType priority_rect_type,
 849     bool is_tile_occluded) const {
 850   // TODO(vmpstr): See if this can be moved to iterators.
 851   DCHECK_EQ(ComputePriorityRectTypeForTile(tile), priority_rect_type);
 852   DCHECK_EQ(TileAt(tile->tiling_i_index(), tile->tiling_j_index()), tile);
 853
 854   TilePriority::PriorityBin priority_bin;
 855   if (client_->HasValidTilePriorities()) {
 856     // Occluded tiles are given a lower PriorityBin to ensure they are evicted
 857     // before non-occluded tiles.
 858     priority_bin = is_tile_occluded ? TilePriority::SOON : TilePriority::NOW;
 859   } else {
 860     priority_bin = TilePriority::EVENTUALLY;
 861   }
 862
 863   switch (priority_rect_type) {
 864     case VISIBLE_RECT:
 865     case PENDING_VISIBLE_RECT:
 866       return TilePriority(resolution_, priority_bin, 0);
 867     case SKEWPORT_RECT:
 868     case SOON_BORDER_RECT:
 869       if (priority_bin < TilePriority::SOON)
 870         priority_bin = TilePriority::SOON;
 871       break;
 872     case EVENTUALLY_RECT:
 873       priority_bin = TilePriority::EVENTUALLY;
 874       break;
 875   }
 876
 877   gfx::Rect tile_bounds =
 878       tiling_data_.TileBounds(tile->tiling_i_index(), tile->tiling_j_index());
 879   DCHECK_GT(current_content_to_screen_scale_, 0.f);
 880   float distance_to_visible =
 881       current_content_to_screen_scale_ *
 882       current_visible_rect_.ManhattanInternalDistance(tile_bounds);
 883
 884   return TilePriority(resolution_, priority_bin, distance_to_visible);
 885 }
 886
 887 PictureLayerTiling::PriorityRectType
 888 PictureLayerTiling::ComputePriorityRectTypeForTile(const Tile* tile) const {
 889   DCHECK_EQ(TileAt(tile->tiling_i_index(), tile->tiling_j_index()), tile);
 890   gfx::Rect tile_bounds =
 891       tiling_data_.TileBounds(tile->tiling_i_index(), tile->tiling_j_index());
 892
 893   if (current_visible_rect_.Intersects(tile_bounds))
 894     return VISIBLE_RECT;
 895
 896   if (pending_visible_rect().Intersects(tile_bounds))
 897     return PENDING_VISIBLE_RECT;
 898
 899   if (current_skewport_rect_.Intersects(tile_bounds))
 900     return SKEWPORT_RECT;
 901
 902   if (current_soon_border_rect_.Intersects(tile_bounds))
 903     return SOON_BORDER_RECT;
 904
 905   DCHECK(current_eventually_rect_.Intersects(tile_bounds));
 906   return EVENTUALLY_RECT;
 907 }
 908
 909 void PictureLayerTiling::GetAllPrioritizedTilesForTracing(
 910     std::vector<PrioritizedTile>* prioritized_tiles) const {
 911   for (const auto& tile_pair : tiles_) {
 912     Tile* tile = tile_pair.second.get();
 913     prioritized_tiles->push_back(MakePrioritizedTile(
 914         tile, ComputePriorityRectTypeForTile(tile), IsTileOccluded(tile)));
 915   }
 916 }
 917
 918 void PictureLayerTiling::AsValueInto(
 919     base::trace_event::TracedValue* state) const {
 920   state->SetInteger("num_tiles", base::saturated_cast<int>(tiles_.size()));
 921   state->SetDouble("content_scale", contents_scale_key());
 922
 923   state->BeginDictionary("raster_transform");
 924   state->BeginArray("scale");
 925   state->AppendDouble(raster_transform_.scale().x());
 926   state->AppendDouble(raster_transform_.scale().y());
 927   state->EndArray();
 928   state->BeginArray("translation");
 929   state->AppendDouble(raster_transform_.translation().x());
 930   state->AppendDouble(raster_transform_.translation().y());
 931   state->EndArray();
 932   state->EndDictionary();
 933
 934   MathUtil::AddToTracedValue("visible_rect", current_visible_rect_, state);
 935   MathUtil::AddToTracedValue("skewport_rect", current_skewport_rect_, state);
 936   MathUtil::AddToTracedValue("soon_rect", current_soon_border_rect_, state);
 937   MathUtil::AddToTracedValue("eventually_rect", current_eventually_rect_,
 938                              state);
 939   MathUtil::AddToTracedValue("tiling_size", tiling_size(), state);
 940 }
 941
 942 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 943   size_t amount = 0;
 944   for (auto it = tiles_.begin(); it != tiles_.end(); ++it) {
 945     const Tile* tile = it->second.get();
 946     amount += tile->GPUMemoryUsageInBytes();
 947   }
 948   return amount;
 949 }
 950
 951 gfx::Rect PictureLayerTiling::EnclosingContentsRectFromLayerRect(
 952     const gfx::Rect& layer_rect) const {
 953   return ToEnclosingRect(raster_transform_.MapRect(gfx::RectF(layer_rect)));
 954 }
 955
 956 gfx::Rect PictureLayerTiling::EnclosingLayerRectFromContentsRect(
 957     const gfx::Rect& contents_rect) const {
 958   return ToEnclosingRect(
 959       raster_transform_.InverseMapRect(gfx::RectF(contents_rect)));
 960 }
 961
 962 PictureLayerTiling::TileIterator::TileIterator(PictureLayerTiling* tiling)
 963     : tiling_(tiling), iter_(tiling->tiles_.begin()) {}
 964
 965 PictureLayerTiling::TileIterator::~TileIterator() = default;
 966
 967 Tile* PictureLayerTiling::TileIterator::GetCurrent() {
 968   return AtEnd() ? nullptr : iter_->second.get();
 969 }
 970
 971 void PictureLayerTiling::TileIterator::Next() {
 972   if (!AtEnd())
 973     ++iter_;
 974 }
 975
 976 bool PictureLayerTiling::TileIterator::AtEnd() const {
 977   return iter_ == tiling_->tiles_.end();
 978 }
 979
 980 }  // namespace cc