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
  11 #include "base/debug/trace_event.h"
  12 #include "cc/base/math_util.h"
  13 #include "cc/resources/tile.h"
  14 #include "cc/resources/tile_priority.h"
  15 #include "cc/trees/occlusion_tracker.h"
  16 #include "ui/gfx/point_conversions.h"
  17 #include "ui/gfx/rect_conversions.h"
  18 #include "ui/gfx/safe_integer_conversions.h"
  19 #include "ui/gfx/size_conversions.h"
  20
  21 namespace cc {
  22 namespace {
  23
  24 const float kSoonBorderDistanceInScreenPixels = 312.f;
  25
  26 class TileEvictionOrder {
  27  public:
  28   explicit TileEvictionOrder(TreePriority tree_priority)
  29       : tree_priority_(tree_priority) {}
  30   ~TileEvictionOrder() {}
  31
  32   bool operator()(const Tile* a, const Tile* b) {
  33     const TilePriority& a_priority =
  34         a->priority_for_tree_priority(tree_priority_);
  35     const TilePriority& b_priority =
  36         b->priority_for_tree_priority(tree_priority_);
  37
  38     // Evict a before b if their priority bins differ and a has the higher
  39     // priority bin.
  40     if (a_priority.priority_bin != b_priority.priority_bin)
  41       return a_priority.priority_bin > b_priority.priority_bin;
  42
  43     // Or if a is not required and b is required.
  44     if (a->required_for_activation() != b->required_for_activation())
  45       return b->required_for_activation();
  46
  47     // Or if a is occluded and b is unoccluded.
  48     bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
  49     bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
  50     if (a_is_occluded != b_is_occluded)
  51       return a_is_occluded;
  52
  53     // Or if a is farther away from visible.
  54     return a_priority.distance_to_visible > b_priority.distance_to_visible;
  55   }
  56
  57  private:
  58   TreePriority tree_priority_;
  59 };
  60 }  // namespace
  61
  62 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
  63     float contents_scale,
  64     const gfx::Size& layer_bounds,
  65     PictureLayerTilingClient* client) {
  66   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
  67                                                 layer_bounds,
  68                                                 client));
  69 }
  70
  71 PictureLayerTiling::PictureLayerTiling(float contents_scale,
  72                                        const gfx::Size& layer_bounds,
  73                                        PictureLayerTilingClient* client)
  74     : contents_scale_(contents_scale),
  75       layer_bounds_(layer_bounds),
  76       resolution_(NON_IDEAL_RESOLUTION),
  77       client_(client),
  78       tiling_data_(gfx::Size(), gfx::Size(), true),
  79       last_impl_frame_time_in_seconds_(0.0),
  80       eviction_tiles_cache_valid_(false),
  81       eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
  82   gfx::Size content_bounds =
  83       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
  84   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
  85
  86   DCHECK(!gfx::ToFlooredSize(
  87       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
  88       "Tiling created with scale too small as contents become empty." <<
  89       " Layer bounds: " << layer_bounds.ToString() <<
  90       " Contents scale: " << contents_scale;
  91
  92   tiling_data_.SetTilingSize(content_bounds);
  93   tiling_data_.SetMaxTextureSize(tile_size);
  94 }
  95
  96 PictureLayerTiling::~PictureLayerTiling() {
  97 }
  98
  99 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
 100   client_ = client;
 101 }
 102
 103 Tile* PictureLayerTiling::CreateTile(int i,
 104                                      int j,
 105                                      const PictureLayerTiling* twin_tiling) {
 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   // Check our twin for a valid tile.
 114   if (twin_tiling &&
 115       tiling_data_.max_texture_size() ==
 116       twin_tiling->tiling_data_.max_texture_size()) {
 117     if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
 118       gfx::Rect rect =
 119           gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
 120       if (!client_->GetInvalidation()->Intersects(rect)) {
 121         tiles_[key] = candidate_tile;
 122         return candidate_tile;
 123       }
 124     }
 125   }
 126
 127   // Create a new tile because our twin didn't have a valid one.
 128   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
 129   if (tile.get())
 130     tiles_[key] = tile;
 131   return tile.get();
 132 }
 133
 134 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
 135   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 136   bool include_borders = true;
 137   for (TilingData::Iterator iter(
 138            &tiling_data_, live_tiles_rect_, include_borders);
 139        iter;
 140        ++iter) {
 141     TileMapKey key = iter.index();
 142     TileMap::iterator find = tiles_.find(key);
 143     if (find != tiles_.end())
 144       continue;
 145     CreateTile(key.first, key.second, twin_tiling);
 146   }
 147 }
 148
 149 void PictureLayerTiling::UpdateTilesToCurrentPile(
 150     const Region& layer_invalidation,
 151     const gfx::Size& new_layer_bounds) {
 152   DCHECK(!new_layer_bounds.IsEmpty());
 153
 154   gfx::Size old_layer_bounds = layer_bounds_;
 155   layer_bounds_ = new_layer_bounds;
 156
 157   gfx::Size content_bounds =
 158       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
 159   gfx::Size tile_size = tiling_data_.max_texture_size();
 160
 161   if (layer_bounds_ != old_layer_bounds) {
 162     // Drop tiles outside the new layer bounds if the layer shrank.
 163     SetLiveTilesRect(
 164         gfx::IntersectRects(live_tiles_rect_, gfx::Rect(content_bounds)));
 165     tiling_data_.SetTilingSize(content_bounds);
 166     tile_size = client_->CalculateTileSize(content_bounds);
 167   }
 168
 169   if (tile_size != tiling_data_.max_texture_size()) {
 170     tiling_data_.SetMaxTextureSize(tile_size);
 171     // When the tile size changes, the TilingData positions no longer work
 172     // as valid keys to the TileMap, so just drop all tiles.
 173     Reset();
 174   } else {
 175     Invalidate(layer_invalidation);
 176   }
 177
 178   PicturePileImpl* pile = client_->GetPile();
 179   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 180     it->second->set_picture_pile(pile);
 181 }
 182
 183 void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) {
 184   bool recreate_invalidated_tiles = false;
 185   DoInvalidate(layer_region, recreate_invalidated_tiles);
 186 }
 187
 188 void PictureLayerTiling::Invalidate(const Region& layer_region) {
 189   bool recreate_invalidated_tiles = true;
 190   DoInvalidate(layer_region, recreate_invalidated_tiles);
 191 }
 192
 193 void PictureLayerTiling::DoInvalidate(const Region& layer_region,
 194                                       bool recreate_invalidated_tiles) {
 195   std::vector<TileMapKey> new_tile_keys;
 196   gfx::Rect expanded_live_tiles_rect =
 197       tiling_data_.ExpandRectIgnoringBordersToTileBoundsWithBorders(
 198           live_tiles_rect_);
 199   for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
 200     gfx::Rect layer_rect = iter.rect();
 201     gfx::Rect content_rect =
 202         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
 203     // Avoid needless work by not bothering to invalidate where there aren't
 204     // tiles.
 205     content_rect.Intersect(expanded_live_tiles_rect);
 206     if (content_rect.IsEmpty())
 207       continue;
 208     bool include_borders = true;
 209     for (TilingData::Iterator iter(
 210              &tiling_data_, content_rect, include_borders);
 211          iter;
 212          ++iter) {
 213       TileMapKey key(iter.index());
 214       TileMap::iterator find = tiles_.find(key);
 215       if (find == tiles_.end())
 216         continue;
 217       tiles_.erase(find);
 218       new_tile_keys.push_back(key);
 219     }
 220   }
 221
 222   if (recreate_invalidated_tiles && !new_tile_keys.empty()) {
 223     for (size_t i = 0; i < new_tile_keys.size(); ++i) {
 224       // Don't try to share a tile with the twin layer, it's been invalidated so
 225       // we have to make our own tile here.
 226       const PictureLayerTiling* twin_tiling = NULL;
 227       CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
 228     }
 229   }
 230 }
 231
 232 PictureLayerTiling::CoverageIterator::CoverageIterator()
 233     : tiling_(NULL),
 234       current_tile_(NULL),
 235       tile_i_(0),
 236       tile_j_(0),
 237       left_(0),
 238       top_(0),
 239       right_(-1),
 240       bottom_(-1) {
 241 }
 242
 243 PictureLayerTiling::CoverageIterator::CoverageIterator(
 244     const PictureLayerTiling* tiling,
 245     float dest_scale,
 246     const gfx::Rect& dest_rect)
 247     : tiling_(tiling),
 248       dest_rect_(dest_rect),
 249       dest_to_content_scale_(0),
 250       current_tile_(NULL),
 251       tile_i_(0),
 252       tile_j_(0),
 253       left_(0),
 254       top_(0),
 255       right_(-1),
 256       bottom_(-1) {
 257   DCHECK(tiling_);
 258   if (dest_rect_.IsEmpty())
 259     return;
 260
 261   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 262
 263   gfx::Rect content_rect =
 264       gfx::ScaleToEnclosingRect(dest_rect_,
 265                                 dest_to_content_scale_,
 266                                 dest_to_content_scale_);
 267   // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
 268   // check for non-intersection first.
 269   content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 270   if (content_rect.IsEmpty())
 271     return;
 272
 273   left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
 274   top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
 275   right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
 276       content_rect.right() - 1);
 277   bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
 278       content_rect.bottom() - 1);
 279
 280   tile_i_ = left_ - 1;
 281   tile_j_ = top_;
 282   ++(*this);
 283 }
 284
 285 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 286 }
 287
 288 PictureLayerTiling::CoverageIterator&
 289 PictureLayerTiling::CoverageIterator::operator++() {
 290   if (tile_j_ > bottom_)
 291     return *this;
 292
 293   bool first_time = tile_i_ < left_;
 294   bool new_row = false;
 295   tile_i_++;
 296   if (tile_i_ > right_) {
 297     tile_i_ = left_;
 298     tile_j_++;
 299     new_row = true;
 300     if (tile_j_ > bottom_) {
 301       current_tile_ = NULL;
 302       return *this;
 303     }
 304   }
 305
 306   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 307
 308   // Calculate the current geometry rect.  Due to floating point rounding
 309   // and ToEnclosingRect, tiles might overlap in destination space on the
 310   // edges.
 311   gfx::Rect last_geometry_rect = current_geometry_rect_;
 312
 313   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 314
 315   current_geometry_rect_ =
 316       gfx::ScaleToEnclosingRect(content_rect,
 317                                 1 / dest_to_content_scale_,
 318                                 1 / dest_to_content_scale_);
 319
 320   current_geometry_rect_.Intersect(dest_rect_);
 321
 322   if (first_time)
 323     return *this;
 324
 325   // Iteration happens left->right, top->bottom.  Running off the bottom-right
 326   // edge is handled by the intersection above with dest_rect_.  Here we make
 327   // sure that the new current geometry rect doesn't overlap with the last.
 328   int min_left;
 329   int min_top;
 330   if (new_row) {
 331     min_left = dest_rect_.x();
 332     min_top = last_geometry_rect.bottom();
 333   } else {
 334     min_left = last_geometry_rect.right();
 335     min_top = last_geometry_rect.y();
 336   }
 337
 338   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 339   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 340   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 341
 342   if (!new_row) {
 343     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 344     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 345     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 346   }
 347
 348   return *this;
 349 }
 350
 351 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 352   return current_geometry_rect_;
 353 }
 354
 355 gfx::Rect
 356 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
 357   gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
 358   rect.set_size(tiling_->tiling_data_.max_texture_size());
 359   return rect;
 360 }
 361
 362 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 363   gfx::PointF tex_origin =
 364       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 365
 366   // Convert from dest space => content space => texture space.
 367   gfx::RectF texture_rect(current_geometry_rect_);
 368   texture_rect.Scale(dest_to_content_scale_,
 369                      dest_to_content_scale_);
 370   texture_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
 371   if (texture_rect.IsEmpty())
 372     return texture_rect;
 373   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 374
 375   return texture_rect;
 376 }
 377
 378 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
 379   return tiling_->tiling_data_.max_texture_size();
 380 }
 381
 382 void PictureLayerTiling::Reset() {
 383   live_tiles_rect_ = gfx::Rect();
 384   tiles_.clear();
 385 }
 386
 387 gfx::Rect PictureLayerTiling::ComputeSkewport(
 388     double current_frame_time_in_seconds,
 389     const gfx::Rect& visible_rect_in_content_space) const {
 390   gfx::Rect skewport = visible_rect_in_content_space;
 391   if (last_impl_frame_time_in_seconds_ == 0.0)
 392     return skewport;
 393
 394   double time_delta =
 395       current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
 396   if (time_delta == 0.0)
 397     return skewport;
 398
 399   float skewport_target_time_in_seconds =
 400       client_->GetSkewportTargetTimeInSeconds();
 401   double extrapolation_multiplier =
 402       skewport_target_time_in_seconds / time_delta;
 403
 404   int old_x = last_visible_rect_in_content_space_.x();
 405   int old_y = last_visible_rect_in_content_space_.y();
 406   int old_right = last_visible_rect_in_content_space_.right();
 407   int old_bottom = last_visible_rect_in_content_space_.bottom();
 408
 409   int new_x = visible_rect_in_content_space.x();
 410   int new_y = visible_rect_in_content_space.y();
 411   int new_right = visible_rect_in_content_space.right();
 412   int new_bottom = visible_rect_in_content_space.bottom();
 413
 414   int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels();
 415
 416   // Compute the maximum skewport based on |skewport_limit|.
 417   gfx::Rect max_skewport = skewport;
 418   max_skewport.Inset(
 419       -skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit);
 420
 421   // Inset the skewport by the needed adjustment.
 422   skewport.Inset(extrapolation_multiplier * (new_x - old_x),
 423                  extrapolation_multiplier * (new_y - old_y),
 424                  extrapolation_multiplier * (old_right - new_right),
 425                  extrapolation_multiplier * (old_bottom - new_bottom));
 426
 427   // Clip the skewport to |max_skewport|.
 428   skewport.Intersect(max_skewport);
 429
 430   // Finally, ensure that visible rect is contained in the skewport.
 431   skewport.Union(visible_rect_in_content_space);
 432   return skewport;
 433 }
 434
 435 void PictureLayerTiling::UpdateTilePriorities(
 436     WhichTree tree,
 437     const gfx::Rect& visible_layer_rect,
 438     float ideal_contents_scale,
 439     double current_frame_time_in_seconds,
 440     const OcclusionTracker<LayerImpl>* occlusion_tracker,
 441     const LayerImpl* render_target,
 442     const gfx::Transform& draw_transform) {
 443   if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
 444     // This should never be zero for the purposes of has_ever_been_updated().
 445     DCHECK_NE(current_frame_time_in_seconds, 0.0);
 446     return;
 447   }
 448
 449   gfx::Rect visible_rect_in_content_space =
 450       gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
 451
 452   if (tiling_size().IsEmpty()) {
 453     last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 454     last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 455     return;
 456   }
 457
 458   size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea();
 459
 460   gfx::Size tile_size = tiling_data_.max_texture_size();
 461   int64 eventually_rect_area =
 462       max_tiles_for_interest_area * tile_size.width() * tile_size.height();
 463
 464   gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
 465                                        visible_rect_in_content_space);
 466   DCHECK(skewport.Contains(visible_rect_in_content_space));
 467
 468   gfx::Rect eventually_rect =
 469       ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space,
 470                                        eventually_rect_area,
 471                                        gfx::Rect(tiling_size()),
 472                                        &expansion_cache_);
 473
 474   DCHECK(eventually_rect.IsEmpty() ||
 475          gfx::Rect(tiling_size()).Contains(eventually_rect))
 476       << "tiling_size: " << tiling_size().ToString()
 477       << " eventually_rect: " << eventually_rect.ToString();
 478
 479   SetLiveTilesRect(eventually_rect);
 480
 481   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 482   last_visible_rect_in_content_space_ = visible_rect_in_content_space;
 483
 484   eviction_tiles_cache_valid_ = false;
 485
 486   TilePriority now_priority(resolution_, TilePriority::NOW, 0);
 487   float content_to_screen_scale =
 488       1.0f / (contents_scale_ * ideal_contents_scale);
 489
 490   // Assign now priority to all visible tiles.
 491   bool include_borders = true;
 492   for (TilingData::Iterator iter(
 493            &tiling_data_, visible_rect_in_content_space, include_borders);
 494        iter;
 495        ++iter) {
 496     TileMap::iterator find = tiles_.find(iter.index());
 497     if (find == tiles_.end())
 498       continue;
 499     Tile* tile = find->second.get();
 500
 501     tile->SetPriority(tree, now_priority);
 502
 503     // Set whether tile is occluded or not.
 504     bool is_occluded = false;
 505     if (occlusion_tracker) {
 506       gfx::Rect tile_query_rect = ScaleToEnclosingRect(
 507           IntersectRects(tile->content_rect(), visible_rect_in_content_space),
 508           1.0f / contents_scale_);
 509       // TODO(vmpstr): Remove render_target and draw_transform from the
 510       // parameters so they can be hidden from the tiling.
 511       is_occluded = occlusion_tracker->Occluded(
 512           render_target, tile_query_rect, draw_transform);
 513     }
 514     tile->set_is_occluded(tree, is_occluded);
 515   }
 516
 517   // Assign soon priority to skewport tiles.
 518   for (TilingData::DifferenceIterator iter(
 519            &tiling_data_, skewport, visible_rect_in_content_space);
 520        iter;
 521        ++iter) {
 522     TileMap::iterator find = tiles_.find(iter.index());
 523     if (find == tiles_.end())
 524       continue;
 525     Tile* tile = find->second.get();
 526
 527     gfx::Rect tile_bounds =
 528         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 529
 530     float distance_to_visible =
 531         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
 532         content_to_screen_scale;
 533
 534     TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible);
 535     tile->SetPriority(tree, priority);
 536   }
 537
 538   // Assign eventually priority to interest rect tiles.
 539   for (TilingData::DifferenceIterator iter(
 540            &tiling_data_, eventually_rect, skewport);
 541        iter;
 542        ++iter) {
 543     TileMap::iterator find = tiles_.find(iter.index());
 544     if (find == tiles_.end())
 545       continue;
 546     Tile* tile = find->second.get();
 547
 548     gfx::Rect tile_bounds =
 549         tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 550
 551     float distance_to_visible =
 552         visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
 553         content_to_screen_scale;
 554     TilePriority priority(
 555         resolution_, TilePriority::EVENTUALLY, distance_to_visible);
 556     tile->SetPriority(tree, priority);
 557   }
 558
 559   // Upgrade the priority on border tiles to be SOON.
 560   gfx::Rect soon_border_rect = visible_rect_in_content_space;
 561   float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale;
 562   soon_border_rect.Inset(-border, -border, -border, -border);
 563   for (TilingData::DifferenceIterator iter(
 564            &tiling_data_, soon_border_rect, skewport);
 565        iter;
 566        ++iter) {
 567     TileMap::iterator find = tiles_.find(iter.index());
 568     if (find == tiles_.end())
 569       continue;
 570     Tile* tile = find->second.get();
 571
 572     TilePriority priority(resolution_,
 573                           TilePriority::SOON,
 574                           tile->priority(tree).distance_to_visible);
 575     tile->SetPriority(tree, priority);
 576   }
 577
 578   // Update iteration rects.
 579   current_visible_rect_ = visible_rect_in_content_space;
 580   current_skewport_rect_ = skewport;
 581   current_soon_border_rect_ = soon_border_rect;
 582   current_eventually_rect_ = eventually_rect;
 583 }
 584
 585 void PictureLayerTiling::SetLiveTilesRect(
 586     const gfx::Rect& new_live_tiles_rect) {
 587   DCHECK(new_live_tiles_rect.IsEmpty() ||
 588          gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
 589       << "tiling_size: " << tiling_size().ToString()
 590       << " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
 591   if (live_tiles_rect_ == new_live_tiles_rect)
 592     return;
 593
 594   // Iterate to delete all tiles outside of our new live_tiles rect.
 595   for (TilingData::DifferenceIterator iter(&tiling_data_,
 596                                            live_tiles_rect_,
 597                                            new_live_tiles_rect);
 598        iter;
 599        ++iter) {
 600     TileMapKey key(iter.index());
 601     TileMap::iterator found = tiles_.find(key);
 602     // If the tile was outside of the recorded region, it won't exist even
 603     // though it was in the live rect.
 604     if (found != tiles_.end())
 605       tiles_.erase(found);
 606   }
 607
 608   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 609
 610   // Iterate to allocate new tiles for all regions with newly exposed area.
 611   for (TilingData::DifferenceIterator iter(&tiling_data_,
 612                                            new_live_tiles_rect,
 613                                            live_tiles_rect_);
 614        iter;
 615        ++iter) {
 616     TileMapKey key(iter.index());
 617     CreateTile(key.first, key.second, twin_tiling);
 618   }
 619
 620   live_tiles_rect_ = new_live_tiles_rect;
 621 }
 622
 623 void PictureLayerTiling::DidBecomeRecycled() {
 624   // DidBecomeActive below will set the active priority for tiles that are
 625   // still in the tree. Calling this first on an active tiling that is becoming
 626   // recycled takes care of tiles that are no longer in the active tree (eg.
 627   // due to a pending invalidation).
 628   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 629     it->second->SetPriority(ACTIVE_TREE, TilePriority());
 630   }
 631 }
 632
 633 void PictureLayerTiling::DidBecomeActive() {
 634   PicturePileImpl* active_pile = client_->GetPile();
 635   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 636     it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
 637     it->second->SetPriority(PENDING_TREE, TilePriority());
 638
 639     // Tile holds a ref onto a picture pile. If the tile never gets invalidated
 640     // and recreated, then that picture pile ref could exist indefinitely.  To
 641     // prevent this, ask the client to update the pile to its own ref.  This
 642     // will cause PicturePileImpls and their clones to get deleted once the
 643     // corresponding PictureLayerImpl and any in flight raster jobs go out of
 644     // scope.
 645     it->second->set_picture_pile(active_pile);
 646   }
 647 }
 648
 649 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
 650   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
 651   state->SetInteger("num_tiles", tiles_.size());
 652   state->SetDouble("content_scale", contents_scale_);
 653   state->Set("tiling_size", MathUtil::AsValue(tiling_size()).release());
 654   return state.PassAs<base::Value>();
 655 }
 656
 657 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 658   size_t amount = 0;
 659   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 660     const Tile* tile = it->second.get();
 661     amount += tile->GPUMemoryUsageInBytes();
 662   }
 663   return amount;
 664 }
 665
 666 PictureLayerTiling::RectExpansionCache::RectExpansionCache()
 667   : previous_target(0) {
 668 }
 669
 670 namespace {
 671
 672 // This struct represents an event at which the expending rect intersects
 673 // one of its boundaries.  4 intersection events will occur during expansion.
 674 struct EdgeEvent {
 675   enum { BOTTOM, TOP, LEFT, RIGHT } edge;
 676   int* num_edges;
 677   int distance;
 678 };
 679
 680 // Compute the delta to expand from edges to cover target_area.
 681 int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
 682                           int width, int height,
 683                           int64 target_area) {
 684   // Compute coefficients for the quadratic equation:
 685   //   a*x^2 + b*x + c = 0
 686   int a = num_y_edges * num_x_edges;
 687   int b = num_y_edges * width + num_x_edges * height;
 688   int64 c = static_cast<int64>(width) * height - target_area;
 689
 690   // Compute the delta for our edges using the quadratic equation.
 691   return a == 0 ? -c / b :
 692      (-b + static_cast<int>(
 693          std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
 694 }
 695
 696 }  // namespace
 697
 698 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
 699     const gfx::Rect& starting_rect,
 700     int64 target_area,
 701     const gfx::Rect& bounding_rect,
 702     RectExpansionCache* cache) {
 703   if (starting_rect.IsEmpty())
 704     return starting_rect;
 705
 706   if (cache &&
 707       cache->previous_start == starting_rect &&
 708       cache->previous_bounds == bounding_rect &&
 709       cache->previous_target == target_area)
 710     return cache->previous_result;
 711
 712   if (cache) {
 713     cache->previous_start = starting_rect;
 714     cache->previous_bounds = bounding_rect;
 715     cache->previous_target = target_area;
 716   }
 717
 718   DCHECK(!bounding_rect.IsEmpty());
 719   DCHECK_GT(target_area, 0);
 720
 721   // Expand the starting rect to cover target_area, if it is smaller than it.
 722   int delta = ComputeExpansionDelta(
 723       2, 2, starting_rect.width(), starting_rect.height(), target_area);
 724   gfx::Rect expanded_starting_rect = starting_rect;
 725   if (delta > 0)
 726     expanded_starting_rect.Inset(-delta, -delta);
 727
 728   gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
 729   if (rect.IsEmpty()) {
 730     // The starting_rect and bounding_rect are far away.
 731     if (cache)
 732       cache->previous_result = rect;
 733     return rect;
 734   }
 735   if (delta >= 0 && rect == expanded_starting_rect) {
 736     // The starting rect already covers the entire bounding_rect and isn't too
 737     // large for the target_area.
 738     if (cache)
 739       cache->previous_result = rect;
 740     return rect;
 741   }
 742
 743   // Continue to expand/shrink rect to let it cover target_area.
 744
 745   // These values will be updated by the loop and uses as the output.
 746   int origin_x = rect.x();
 747   int origin_y = rect.y();
 748   int width = rect.width();
 749   int height = rect.height();
 750
 751   // In the beginning we will consider 2 edges in each dimension.
 752   int num_y_edges = 2;
 753   int num_x_edges = 2;
 754
 755   // Create an event list.
 756   EdgeEvent events[] = {
 757     { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
 758     { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
 759     { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
 760     { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
 761   };
 762
 763   // Sort the events by distance (closest first).
 764   if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
 765   if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
 766   if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
 767   if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
 768   if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
 769
 770   for (int event_index = 0; event_index < 4; event_index++) {
 771     const EdgeEvent& event = events[event_index];
 772
 773     int delta = ComputeExpansionDelta(
 774         num_x_edges, num_y_edges, width, height, target_area);
 775
 776     // Clamp delta to our event distance.
 777     if (delta > event.distance)
 778       delta = event.distance;
 779
 780     // Adjust the edge count for this kind of edge.
 781     --*event.num_edges;
 782
 783     // Apply the delta to the edges and edge events.
 784     for (int i = event_index; i < 4; i++) {
 785       switch (events[i].edge) {
 786         case EdgeEvent::BOTTOM:
 787             origin_y -= delta;
 788             height += delta;
 789             break;
 790         case EdgeEvent::TOP:
 791             height += delta;
 792             break;
 793         case EdgeEvent::LEFT:
 794             origin_x -= delta;
 795             width += delta;
 796             break;
 797         case EdgeEvent::RIGHT:
 798             width += delta;
 799             break;
 800       }
 801       events[i].distance -= delta;
 802     }
 803
 804     // If our delta is less then our event distance, we're done.
 805     if (delta < event.distance)
 806       break;
 807   }
 808
 809   gfx::Rect result(origin_x, origin_y, width, height);
 810   if (cache)
 811     cache->previous_result = result;
 812   return result;
 813 }
 814
 815 void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
 816     TreePriority tree_priority) {
 817   if (eviction_tiles_cache_valid_ &&
 818       eviction_cache_tree_priority_ == tree_priority)
 819     return;
 820
 821   eviction_tiles_cache_.clear();
 822   eviction_tiles_cache_.reserve(tiles_.size());
 823   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 824     // TODO(vmpstr): This should update the priority if UpdateTilePriorities
 825     // changes not to do this.
 826     eviction_tiles_cache_.push_back(it->second);
 827   }
 828
 829   std::sort(eviction_tiles_cache_.begin(),
 830             eviction_tiles_cache_.end(),
 831             TileEvictionOrder(tree_priority));
 832   eviction_tiles_cache_valid_ = true;
 833   eviction_cache_tree_priority_ = tree_priority;
 834 }
 835
 836 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
 837     : tiling_(NULL), current_tile_(NULL) {}
 838
 839 PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
 840     PictureLayerTiling* tiling,
 841     WhichTree tree)
 842     : tiling_(tiling),
 843       type_(TilePriority::NOW),
 844       visible_rect_in_content_space_(tiling_->current_visible_rect_),
 845       skewport_in_content_space_(tiling_->current_skewport_rect_),
 846       eventually_rect_in_content_space_(tiling_->current_eventually_rect_),
 847       soon_border_rect_in_content_space_(tiling_->current_soon_border_rect_),
 848       tree_(tree),
 849       current_tile_(NULL),
 850       visible_iterator_(&tiling->tiling_data_,
 851                         visible_rect_in_content_space_,
 852                         true /* include_borders */),
 853       spiral_iterator_(&tiling->tiling_data_,
 854                        skewport_in_content_space_,
 855                        visible_rect_in_content_space_,
 856                        visible_rect_in_content_space_),
 857       skewport_processed_(false) {
 858   if (!visible_iterator_) {
 859     AdvancePhase();
 860     return;
 861   }
 862
 863   current_tile_ =
 864       tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y());
 865   if (!current_tile_ || !TileNeedsRaster(current_tile_))
 866     ++(*this);
 867 }
 868
 869 PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
 870
 871 void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() {
 872   DCHECK_LT(type_, TilePriority::EVENTUALLY);
 873
 874   do {
 875     type_ = static_cast<TilePriority::PriorityBin>(type_ + 1);
 876     if (type_ == TilePriority::EVENTUALLY) {
 877       spiral_iterator_ = TilingData::SpiralDifferenceIterator(
 878           &tiling_->tiling_data_,
 879           eventually_rect_in_content_space_,
 880           skewport_in_content_space_,
 881           visible_rect_in_content_space_);
 882     }
 883
 884     while (spiral_iterator_) {
 885       current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(),
 886                                       spiral_iterator_.index_y());
 887       if (current_tile_ && TileNeedsRaster(current_tile_))
 888         break;
 889       ++spiral_iterator_;
 890     }
 891
 892     if (!spiral_iterator_ && type_ == TilePriority::EVENTUALLY) {
 893       current_tile_ = NULL;
 894       break;
 895     }
 896   } while (!spiral_iterator_);
 897 }
 898
 899 PictureLayerTiling::TilingRasterTileIterator&
 900 PictureLayerTiling::TilingRasterTileIterator::
 901 operator++() {
 902   current_tile_ = NULL;
 903   while (!current_tile_ || !TileNeedsRaster(current_tile_)) {
 904     std::pair<int, int> next_index;
 905     switch (type_) {
 906       case TilePriority::NOW:
 907         ++visible_iterator_;
 908         if (!visible_iterator_) {
 909           AdvancePhase();
 910           return *this;
 911         }
 912         next_index = visible_iterator_.index();
 913         break;
 914       case TilePriority::SOON:
 915         ++spiral_iterator_;
 916         if (!spiral_iterator_) {
 917           if (skewport_processed_) {
 918             AdvancePhase();
 919             return *this;
 920           }
 921           skewport_processed_ = true;
 922           spiral_iterator_ = TilingData::SpiralDifferenceIterator(
 923               &tiling_->tiling_data_,
 924               soon_border_rect_in_content_space_,
 925               skewport_in_content_space_,
 926               visible_rect_in_content_space_);
 927           if (!spiral_iterator_) {
 928             AdvancePhase();
 929             return *this;
 930           }
 931         }
 932         next_index = spiral_iterator_.index();
 933         break;
 934       case TilePriority::EVENTUALLY:
 935         ++spiral_iterator_;
 936         if (!spiral_iterator_) {
 937           current_tile_ = NULL;
 938           return *this;
 939         }
 940         next_index = spiral_iterator_.index();
 941         break;
 942     }
 943     current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
 944   }
 945   return *this;
 946 }
 947
 948 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
 949     : tiling_(NULL) {
 950 }
 951
 952 PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
 953     PictureLayerTiling* tiling,
 954     TreePriority tree_priority)
 955     : tiling_(tiling), tree_priority_(tree_priority) {
 956   tiling_->UpdateEvictionCacheIfNeeded(tree_priority_);
 957   tile_iterator_ = tiling_->eviction_tiles_cache_.begin();
 958   if (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
 959       !(*tile_iterator_)->HasResources()) {
 960     ++(*this);
 961   }
 962 }
 963
 964 PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {}
 965
 966 PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
 967   return tiling_ && tile_iterator_ != tiling_->eviction_tiles_cache_.end();
 968 }
 969
 970 Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
 971   DCHECK(*this);
 972   return *tile_iterator_;
 973 }
 974
 975 const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
 976   DCHECK(*this);
 977   return *tile_iterator_;
 978 }
 979
 980 PictureLayerTiling::TilingEvictionTileIterator&
 981 PictureLayerTiling::TilingEvictionTileIterator::
 982 operator++() {
 983   DCHECK(*this);
 984   do {
 985     ++tile_iterator_;
 986   } while (tile_iterator_ != tiling_->eviction_tiles_cache_.end() &&
 987            (!(*tile_iterator_)->HasResources()));
 988
 989   return *this;
 990 }
 991
 992 }  // namespace cc