src/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 "ui/gfx/point_conversions.h"
  14 #include "ui/gfx/rect_conversions.h"
  15 #include "ui/gfx/safe_integer_conversions.h"
  16 #include "ui/gfx/size_conversions.h"
  17
  18 namespace cc {
  19
  20 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
  21     float contents_scale,
  22     gfx::Size layer_bounds,
  23     PictureLayerTilingClient* client) {
  24   return make_scoped_ptr(new PictureLayerTiling(contents_scale,
  25                                                 layer_bounds,
  26                                                 client));
  27 }
  28
  29 PictureLayerTiling::PictureLayerTiling(float contents_scale,
  30                                        gfx::Size layer_bounds,
  31                                        PictureLayerTilingClient* client)
  32     : contents_scale_(contents_scale),
  33       layer_bounds_(layer_bounds),
  34       resolution_(NON_IDEAL_RESOLUTION),
  35       client_(client),
  36       tiling_data_(gfx::Size(), gfx::Size(), true),
  37       last_impl_frame_time_in_seconds_(0.0) {
  38   gfx::Size content_bounds =
  39       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
  40   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
  41
  42   DCHECK(!gfx::ToFlooredSize(
  43       gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
  44       "Tiling created with scale too small as contents become empty." <<
  45       " Layer bounds: " << layer_bounds.ToString() <<
  46       " Contents scale: " << contents_scale;
  47
  48   tiling_data_.SetTotalSize(content_bounds);
  49   tiling_data_.SetMaxTextureSize(tile_size);
  50 }
  51
  52 PictureLayerTiling::~PictureLayerTiling() {
  53 }
  54
  55 void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
  56   client_ = client;
  57 }
  58
  59 gfx::Rect PictureLayerTiling::ContentRect() const {
  60   return gfx::Rect(tiling_data_.total_size());
  61 }
  62
  63 gfx::SizeF PictureLayerTiling::ContentSizeF() const {
  64   return gfx::ScaleSize(layer_bounds_, contents_scale_);
  65 }
  66
  67 Tile* PictureLayerTiling::TileAt(int i, int j) const {
  68   TileMap::const_iterator iter = tiles_.find(TileMapKey(i, j));
  69   if (iter == tiles_.end())
  70     return NULL;
  71   return iter->second.get();
  72 }
  73
  74 void PictureLayerTiling::CreateTile(int i,
  75                                     int j,
  76                                     const PictureLayerTiling* twin_tiling) {
  77   TileMapKey key(i, j);
  78   DCHECK(tiles_.find(key) == tiles_.end());
  79
  80   gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
  81   gfx::Rect tile_rect = paint_rect;
  82   tile_rect.set_size(tiling_data_.max_texture_size());
  83
  84   // Check our twin for a valid tile.
  85   if (twin_tiling &&
  86       tiling_data_.max_texture_size() ==
  87       twin_tiling->tiling_data_.max_texture_size()) {
  88     if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
  89       gfx::Rect rect =
  90           gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
  91       if (!client_->GetInvalidation()->Intersects(rect)) {
  92         tiles_[key] = candidate_tile;
  93         return;
  94       }
  95     }
  96   }
  97
  98   // Create a new tile because our twin didn't have a valid one.
  99   scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
 100   if (tile.get())
 101     tiles_[key] = tile;
 102 }
 103
 104 Region PictureLayerTiling::OpaqueRegionInContentRect(
 105     gfx::Rect content_rect) const {
 106   Region opaque_region;
 107   // TODO(enne): implement me
 108   return opaque_region;
 109 }
 110
 111 void PictureLayerTiling::SetCanUseLCDText(bool can_use_lcd_text) {
 112   for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it)
 113     it->second->set_can_use_lcd_text(can_use_lcd_text);
 114 }
 115
 116 void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
 117   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 118   for (TilingData::Iterator iter(&tiling_data_, live_tiles_rect_); iter;
 119        ++iter) {
 120     TileMapKey key = iter.index();
 121     TileMap::iterator find = tiles_.find(key);
 122     if (find != tiles_.end())
 123       continue;
 124     CreateTile(key.first, key.second, twin_tiling);
 125   }
 126 }
 127
 128 void PictureLayerTiling::SetLayerBounds(gfx::Size layer_bounds) {
 129   if (layer_bounds_ == layer_bounds)
 130     return;
 131
 132   DCHECK(!layer_bounds.IsEmpty());
 133
 134   gfx::Size old_layer_bounds = layer_bounds_;
 135   layer_bounds_ = layer_bounds;
 136   gfx::Size old_content_bounds = tiling_data_.total_size();
 137   gfx::Size content_bounds =
 138       gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
 139
 140   gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
 141   if (tile_size != tiling_data_.max_texture_size()) {
 142     tiling_data_.SetTotalSize(content_bounds);
 143     tiling_data_.SetMaxTextureSize(tile_size);
 144     Reset();
 145     return;
 146   }
 147
 148   // Any tiles outside our new bounds are invalid and should be dropped.
 149   gfx::Rect bounded_live_tiles_rect(live_tiles_rect_);
 150   bounded_live_tiles_rect.Intersect(gfx::Rect(content_bounds));
 151   SetLiveTilesRect(bounded_live_tiles_rect);
 152   tiling_data_.SetTotalSize(content_bounds);
 153
 154   // Create tiles for newly exposed areas.
 155   Region layer_region((gfx::Rect(layer_bounds_)));
 156   layer_region.Subtract(gfx::Rect(old_layer_bounds));
 157   Invalidate(layer_region);
 158 }
 159
 160 void PictureLayerTiling::Invalidate(const Region& layer_region) {
 161   std::vector<TileMapKey> new_tile_keys;
 162   for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
 163     gfx::Rect layer_rect = iter.rect();
 164     gfx::Rect content_rect =
 165         gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
 166     content_rect.Intersect(live_tiles_rect_);
 167     if (content_rect.IsEmpty())
 168       continue;
 169     for (TilingData::Iterator iter(&tiling_data_, content_rect); iter; ++iter) {
 170       TileMapKey key(iter.index());
 171       TileMap::iterator find = tiles_.find(key);
 172       if (find == tiles_.end())
 173         continue;
 174       tiles_.erase(find);
 175       new_tile_keys.push_back(key);
 176     }
 177   }
 178
 179   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 180   for (size_t i = 0; i < new_tile_keys.size(); ++i)
 181     CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
 182 }
 183
 184 PictureLayerTiling::CoverageIterator::CoverageIterator()
 185     : tiling_(NULL),
 186       current_tile_(NULL),
 187       tile_i_(0),
 188       tile_j_(0),
 189       left_(0),
 190       top_(0),
 191       right_(-1),
 192       bottom_(-1) {
 193 }
 194
 195 PictureLayerTiling::CoverageIterator::CoverageIterator(
 196     const PictureLayerTiling* tiling,
 197     float dest_scale,
 198     gfx::Rect dest_rect)
 199     : tiling_(tiling),
 200       dest_rect_(dest_rect),
 201       dest_to_content_scale_(0),
 202       current_tile_(NULL),
 203       tile_i_(0),
 204       tile_j_(0),
 205       left_(0),
 206       top_(0),
 207       right_(-1),
 208       bottom_(-1) {
 209   DCHECK(tiling_);
 210   if (dest_rect_.IsEmpty())
 211     return;
 212
 213   dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
 214   // This is the maximum size that the dest rect can be, given the content size.
 215   gfx::Size dest_content_size = gfx::ToCeiledSize(gfx::ScaleSize(
 216       tiling_->ContentRect().size(),
 217       1 / dest_to_content_scale_,
 218       1 / dest_to_content_scale_));
 219
 220   gfx::Rect content_rect =
 221       gfx::ScaleToEnclosingRect(dest_rect_,
 222                                 dest_to_content_scale_,
 223                                 dest_to_content_scale_);
 224   // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
 225   // check for non-intersection first.
 226   content_rect.Intersect(gfx::Rect(tiling_->tiling_data_.total_size()));
 227   if (content_rect.IsEmpty())
 228     return;
 229
 230   left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
 231   top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
 232   right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
 233       content_rect.right() - 1);
 234   bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
 235       content_rect.bottom() - 1);
 236
 237   tile_i_ = left_ - 1;
 238   tile_j_ = top_;
 239   ++(*this);
 240 }
 241
 242 PictureLayerTiling::CoverageIterator::~CoverageIterator() {
 243 }
 244
 245 PictureLayerTiling::CoverageIterator&
 246 PictureLayerTiling::CoverageIterator::operator++() {
 247   if (tile_j_ > bottom_)
 248     return *this;
 249
 250   bool first_time = tile_i_ < left_;
 251   bool new_row = false;
 252   tile_i_++;
 253   if (tile_i_ > right_) {
 254     tile_i_ = left_;
 255     tile_j_++;
 256     new_row = true;
 257     if (tile_j_ > bottom_) {
 258       current_tile_ = NULL;
 259       return *this;
 260     }
 261   }
 262
 263   current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
 264
 265   // Calculate the current geometry rect.  Due to floating point rounding
 266   // and ToEnclosingRect, tiles might overlap in destination space on the
 267   // edges.
 268   gfx::Rect last_geometry_rect = current_geometry_rect_;
 269
 270   gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
 271
 272   current_geometry_rect_ =
 273       gfx::ScaleToEnclosingRect(content_rect,
 274                                 1 / dest_to_content_scale_,
 275                                 1 / dest_to_content_scale_);
 276
 277   current_geometry_rect_.Intersect(dest_rect_);
 278
 279   if (first_time)
 280     return *this;
 281
 282   // Iteration happens left->right, top->bottom.  Running off the bottom-right
 283   // edge is handled by the intersection above with dest_rect_.  Here we make
 284   // sure that the new current geometry rect doesn't overlap with the last.
 285   int min_left;
 286   int min_top;
 287   if (new_row) {
 288     min_left = dest_rect_.x();
 289     min_top = last_geometry_rect.bottom();
 290   } else {
 291     min_left = last_geometry_rect.right();
 292     min_top = last_geometry_rect.y();
 293   }
 294
 295   int inset_left = std::max(0, min_left - current_geometry_rect_.x());
 296   int inset_top = std::max(0, min_top - current_geometry_rect_.y());
 297   current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
 298
 299   if (!new_row) {
 300     DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
 301     DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
 302     DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
 303   }
 304
 305   return *this;
 306 }
 307
 308 gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
 309   return current_geometry_rect_;
 310 }
 311
 312 gfx::Rect
 313 PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
 314   gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
 315   rect.set_size(tiling_->tiling_data_.max_texture_size());
 316   return rect;
 317 }
 318
 319 gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
 320   gfx::PointF tex_origin =
 321       tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
 322
 323   // Convert from dest space => content space => texture space.
 324   gfx::RectF texture_rect(current_geometry_rect_);
 325   texture_rect.Scale(dest_to_content_scale_,
 326                      dest_to_content_scale_);
 327   texture_rect.Offset(-tex_origin.OffsetFromOrigin());
 328   texture_rect.Intersect(tiling_->ContentRect());
 329
 330   return texture_rect;
 331 }
 332
 333 gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
 334   return tiling_->tiling_data_.max_texture_size();
 335 }
 336
 337 void PictureLayerTiling::Reset() {
 338   live_tiles_rect_ = gfx::Rect();
 339   tiles_.clear();
 340 }
 341
 342 void PictureLayerTiling::UpdateTilePriorities(
 343     WhichTree tree,
 344     gfx::Size device_viewport,
 345     gfx::Rect viewport_in_layer_space,
 346     gfx::Rect visible_layer_rect,
 347     gfx::Size last_layer_bounds,
 348     gfx::Size current_layer_bounds,
 349     float last_layer_contents_scale,
 350     float current_layer_contents_scale,
 351     const gfx::Transform& last_screen_transform,
 352     const gfx::Transform& current_screen_transform,
 353     double current_frame_time_in_seconds,
 354     size_t max_tiles_for_interest_area) {
 355   if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
 356     // This should never be zero for the purposes of has_ever_been_updated().
 357     DCHECK_NE(current_frame_time_in_seconds, 0.0);
 358     return;
 359   }
 360   if (ContentRect().IsEmpty()) {
 361     last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 362     return;
 363   }
 364
 365   gfx::Rect viewport_in_content_space =
 366       gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
 367   gfx::Rect visible_content_rect =
 368       gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
 369
 370   gfx::Size tile_size = tiling_data_.max_texture_size();
 371   int64 interest_rect_area =
 372       max_tiles_for_interest_area * tile_size.width() * tile_size.height();
 373
 374   gfx::Rect starting_rect = visible_content_rect.IsEmpty()
 375                             ? viewport_in_content_space
 376                             : visible_content_rect;
 377   gfx::Rect interest_rect = ExpandRectEquallyToAreaBoundedBy(
 378       starting_rect,
 379       interest_rect_area,
 380       ContentRect(),
 381       &expansion_cache_);
 382   DCHECK(interest_rect.IsEmpty() ||
 383          ContentRect().Contains(interest_rect));
 384
 385   SetLiveTilesRect(interest_rect);
 386
 387   double time_delta = 0;
 388   if (last_impl_frame_time_in_seconds_ != 0.0 &&
 389       last_layer_bounds == current_layer_bounds) {
 390     time_delta =
 391         current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
 392   }
 393
 394   gfx::Rect view_rect(device_viewport);
 395   float current_scale = current_layer_contents_scale / contents_scale_;
 396   float last_scale = last_layer_contents_scale / contents_scale_;
 397
 398   // Fast path tile priority calculation when both transforms are translations.
 399   if (last_screen_transform.IsApproximatelyIdentityOrTranslation(
 400           std::numeric_limits<float>::epsilon()) &&
 401       current_screen_transform.IsApproximatelyIdentityOrTranslation(
 402           std::numeric_limits<float>::epsilon())) {
 403     gfx::Vector2dF current_offset(
 404         current_screen_transform.matrix().get(0, 3),
 405         current_screen_transform.matrix().get(1, 3));
 406     gfx::Vector2dF last_offset(
 407         last_screen_transform.matrix().get(0, 3),
 408         last_screen_transform.matrix().get(1, 3));
 409
 410     for (TilingData::Iterator iter(&tiling_data_, interest_rect);
 411          iter; ++iter) {
 412       TileMap::iterator find = tiles_.find(iter.index());
 413       if (find == tiles_.end())
 414         continue;
 415       Tile* tile = find->second.get();
 416
 417       gfx::Rect tile_bounds =
 418           tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 419       gfx::RectF current_screen_rect = gfx::ScaleRect(
 420           tile_bounds,
 421           current_scale,
 422           current_scale) + current_offset;
 423       gfx::RectF last_screen_rect = gfx::ScaleRect(
 424           tile_bounds,
 425           last_scale,
 426           last_scale) + last_offset;
 427
 428       float distance_to_visible_in_pixels =
 429           TilePriority::manhattanDistance(current_screen_rect, view_rect);
 430
 431       float time_to_visible_in_seconds =
 432           TilePriority::TimeForBoundsToIntersect(
 433               last_screen_rect, current_screen_rect, time_delta, view_rect);
 434       TilePriority priority(
 435           resolution_,
 436           time_to_visible_in_seconds,
 437           distance_to_visible_in_pixels);
 438       tile->SetPriority(tree, priority);
 439     }
 440   } else if (!last_screen_transform.HasPerspective() &&
 441              !current_screen_transform.HasPerspective()) {
 442     // Secondary fast path that can be applied for any affine transforms.
 443
 444     // Initialize the necessary geometry in screen space, so that we can
 445     // iterate over tiles in screen space without needing a costly transform
 446     // mapping for each tile.
 447
 448     // Apply screen space transform to the local origin point (0, 0); only the
 449     // translation component is needed and can be initialized directly.
 450     gfx::Point current_screen_space_origin(
 451         current_screen_transform.matrix().get(0, 3),
 452         current_screen_transform.matrix().get(1, 3));
 453
 454     gfx::Point last_screen_space_origin(
 455         last_screen_transform.matrix().get(0, 3),
 456         last_screen_transform.matrix().get(1, 3));
 457
 458     float current_tile_width = tiling_data_.TileSizeX(0) * current_scale;
 459     float last_tile_width = tiling_data_.TileSizeX(0) * last_scale;
 460     float current_tile_height = tiling_data_.TileSizeY(0) * current_scale;
 461     float last_tile_height = tiling_data_.TileSizeY(0) * last_scale;
 462
 463     // Apply screen space transform to local basis vectors (tile_width, 0) and
 464     // (0, tile_height); the math simplifies and can be initialized directly.
 465     gfx::Vector2dF current_horizontal(
 466         current_screen_transform.matrix().get(0, 0) * current_tile_width,
 467         current_screen_transform.matrix().get(1, 0) * current_tile_width);
 468     gfx::Vector2dF current_vertical(
 469         current_screen_transform.matrix().get(0, 1) * current_tile_height,
 470         current_screen_transform.matrix().get(1, 1) * current_tile_height);
 471
 472     gfx::Vector2dF last_horizontal(
 473         last_screen_transform.matrix().get(0, 0) * last_tile_width,
 474         last_screen_transform.matrix().get(1, 0) * last_tile_width);
 475     gfx::Vector2dF last_vertical(
 476         last_screen_transform.matrix().get(0, 1) * last_tile_height,
 477         last_screen_transform.matrix().get(1, 1) * last_tile_height);
 478
 479     for (TilingData::Iterator iter(&tiling_data_, interest_rect);
 480          iter; ++iter) {
 481       TileMap::iterator find = tiles_.find(iter.index());
 482       if (find == tiles_.end())
 483         continue;
 484
 485       Tile* tile = find->second.get();
 486
 487       int i = iter.index_x();
 488       int j = iter.index_y();
 489       gfx::PointF current_tile_origin = current_screen_space_origin +
 490               ScaleVector2d(current_horizontal, i) +
 491               ScaleVector2d(current_vertical, j);
 492       gfx::PointF last_tile_origin = last_screen_space_origin +
 493               ScaleVector2d(last_horizontal, i) +
 494               ScaleVector2d(last_vertical, j);
 495
 496       gfx::RectF current_screen_rect = gfx::QuadF(
 497           current_tile_origin,
 498           current_tile_origin + current_horizontal,
 499           current_tile_origin + current_horizontal + current_vertical,
 500           current_tile_origin + current_vertical).BoundingBox();
 501
 502       gfx::RectF last_screen_rect = gfx::QuadF(
 503           last_tile_origin,
 504           last_tile_origin + last_horizontal,
 505           last_tile_origin + last_horizontal + last_vertical,
 506           last_tile_origin + last_vertical).BoundingBox();
 507
 508       float distance_to_visible_in_pixels =
 509           TilePriority::manhattanDistance(current_screen_rect, view_rect);
 510
 511       float time_to_visible_in_seconds =
 512           TilePriority::TimeForBoundsToIntersect(
 513               last_screen_rect, current_screen_rect, time_delta, view_rect);
 514       TilePriority priority(
 515           resolution_,
 516           time_to_visible_in_seconds,
 517           distance_to_visible_in_pixels);
 518       tile->SetPriority(tree, priority);
 519     }
 520   } else {
 521     for (TilingData::Iterator iter(&tiling_data_, interest_rect);
 522          iter; ++iter) {
 523       TileMap::iterator find = tiles_.find(iter.index());
 524       if (find == tiles_.end())
 525         continue;
 526       Tile* tile = find->second.get();
 527
 528       gfx::Rect tile_bounds =
 529           tiling_data_.TileBounds(iter.index_x(), iter.index_y());
 530       gfx::RectF current_layer_content_rect = gfx::ScaleRect(
 531           tile_bounds,
 532           current_scale,
 533           current_scale);
 534       gfx::RectF current_screen_rect = MathUtil::MapClippedRect(
 535           current_screen_transform, current_layer_content_rect);
 536       gfx::RectF last_layer_content_rect = gfx::ScaleRect(
 537           tile_bounds,
 538           last_scale,
 539           last_scale);
 540       gfx::RectF last_screen_rect  = MathUtil::MapClippedRect(
 541           last_screen_transform, last_layer_content_rect);
 542
 543       float distance_to_visible_in_pixels =
 544           TilePriority::manhattanDistance(current_screen_rect, view_rect);
 545
 546       float time_to_visible_in_seconds =
 547           TilePriority::TimeForBoundsToIntersect(
 548               last_screen_rect, current_screen_rect, time_delta, view_rect);
 549
 550       TilePriority priority(
 551           resolution_,
 552           time_to_visible_in_seconds,
 553           distance_to_visible_in_pixels);
 554       tile->SetPriority(tree, priority);
 555     }
 556   }
 557
 558   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
 559 }
 560
 561 void PictureLayerTiling::SetLiveTilesRect(
 562     gfx::Rect new_live_tiles_rect) {
 563   DCHECK(new_live_tiles_rect.IsEmpty() ||
 564          ContentRect().Contains(new_live_tiles_rect));
 565   if (live_tiles_rect_ == new_live_tiles_rect)
 566     return;
 567
 568   // Iterate to delete all tiles outside of our new live_tiles rect.
 569   for (TilingData::DifferenceIterator iter(&tiling_data_,
 570                                            live_tiles_rect_,
 571                                            new_live_tiles_rect);
 572        iter;
 573        ++iter) {
 574     TileMapKey key(iter.index());
 575     TileMap::iterator found = tiles_.find(key);
 576     // If the tile was outside of the recorded region, it won't exist even
 577     // though it was in the live rect.
 578     if (found != tiles_.end())
 579       tiles_.erase(found);
 580   }
 581
 582   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
 583
 584   // Iterate to allocate new tiles for all regions with newly exposed area.
 585   for (TilingData::DifferenceIterator iter(&tiling_data_,
 586                                            new_live_tiles_rect,
 587                                            live_tiles_rect_);
 588        iter;
 589        ++iter) {
 590     TileMapKey key(iter.index());
 591     CreateTile(key.first, key.second, twin_tiling);
 592   }
 593
 594   live_tiles_rect_ = new_live_tiles_rect;
 595 }
 596
 597 void PictureLayerTiling::DidBecomeRecycled() {
 598   // DidBecomeActive below will set the active priority for tiles that are
 599   // still in the tree. Calling this first on an active tiling that is becoming
 600   // recycled takes care of tiles that are no longer in the active tree (eg.
 601   // due to a pending invalidation).
 602   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 603     it->second->SetPriority(ACTIVE_TREE, TilePriority());
 604   }
 605 }
 606
 607 void PictureLayerTiling::DidBecomeActive() {
 608   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 609     it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
 610     it->second->SetPriority(PENDING_TREE, TilePriority());
 611
 612     // Tile holds a ref onto a picture pile. If the tile never gets invalidated
 613     // and recreated, then that picture pile ref could exist indefinitely.  To
 614     // prevent this, ask the client to update the pile to its own ref.  This
 615     // will cause PicturePileImpls and their clones to get deleted once the
 616     // corresponding PictureLayerImpl and any in flight raster jobs go out of
 617     // scope.
 618     client_->UpdatePile(it->second.get());
 619   }
 620 }
 621
 622 void PictureLayerTiling::UpdateTilesToCurrentPile() {
 623   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 624     client_->UpdatePile(it->second.get());
 625   }
 626 }
 627
 628 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
 629   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
 630   state->SetInteger("num_tiles", tiles_.size());
 631   state->SetDouble("content_scale", contents_scale_);
 632   state->Set("content_bounds",
 633              MathUtil::AsValue(ContentRect().size()).release());
 634   return state.PassAs<base::Value>();
 635 }
 636
 637 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
 638   size_t amount = 0;
 639   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
 640     const Tile* tile = it->second.get();
 641     amount += tile->GPUMemoryUsageInBytes();
 642   }
 643   return amount;
 644 }
 645
 646 PictureLayerTiling::RectExpansionCache::RectExpansionCache()
 647   : previous_target(0) {
 648 }
 649
 650 namespace {
 651
 652 // This struct represents an event at which the expending rect intersects
 653 // one of its boundaries.  4 intersection events will occur during expansion.
 654 struct EdgeEvent {
 655   enum { BOTTOM, TOP, LEFT, RIGHT } edge;
 656   int* num_edges;
 657   int distance;
 658 };
 659
 660 // Compute the delta to expand from edges to cover target_area.
 661 int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
 662                           int width, int height,
 663                           int64 target_area) {
 664   // Compute coefficients for the quadratic equation:
 665   //   a*x^2 + b*x + c = 0
 666   int a = num_y_edges * num_x_edges;
 667   int b = num_y_edges * width + num_x_edges * height;
 668   int64 c = static_cast<int64>(width) * height - target_area;
 669
 670   // Compute the delta for our edges using the quadratic equation.
 671   return a == 0 ? -c / b :
 672      (-b + static_cast<int>(
 673          std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
 674 }
 675
 676 }  // namespace
 677
 678 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
 679     gfx::Rect starting_rect,
 680     int64 target_area,
 681     gfx::Rect bounding_rect,
 682     RectExpansionCache* cache) {
 683   if (starting_rect.IsEmpty())
 684     return starting_rect;
 685
 686   if (cache &&
 687       cache->previous_start == starting_rect &&
 688       cache->previous_bounds == bounding_rect &&
 689       cache->previous_target == target_area)
 690     return cache->previous_result;
 691
 692   if (cache) {
 693     cache->previous_start = starting_rect;
 694     cache->previous_bounds = bounding_rect;
 695     cache->previous_target = target_area;
 696   }
 697
 698   DCHECK(!bounding_rect.IsEmpty());
 699   DCHECK_GT(target_area, 0);
 700
 701   // Expand the starting rect to cover target_area, if it is smaller than it.
 702   int delta = ComputeExpansionDelta(
 703       2, 2, starting_rect.width(), starting_rect.height(), target_area);
 704   gfx::Rect expanded_starting_rect = starting_rect;
 705   if (delta > 0)
 706     expanded_starting_rect.Inset(-delta, -delta);
 707
 708   gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
 709   if (rect.IsEmpty()) {
 710     // The starting_rect and bounding_rect are far away.
 711     if (cache)
 712       cache->previous_result = rect;
 713     return rect;
 714   }
 715   if (delta >= 0 && rect == expanded_starting_rect) {
 716     // The starting rect already covers the entire bounding_rect and isn't too
 717     // large for the target_area.
 718     if (cache)
 719       cache->previous_result = rect;
 720     return rect;
 721   }
 722
 723   // Continue to expand/shrink rect to let it cover target_area.
 724
 725   // These values will be updated by the loop and uses as the output.
 726   int origin_x = rect.x();
 727   int origin_y = rect.y();
 728   int width = rect.width();
 729   int height = rect.height();
 730
 731   // In the beginning we will consider 2 edges in each dimension.
 732   int num_y_edges = 2;
 733   int num_x_edges = 2;
 734
 735   // Create an event list.
 736   EdgeEvent events[] = {
 737     { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
 738     { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
 739     { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
 740     { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
 741   };
 742
 743   // Sort the events by distance (closest first).
 744   if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
 745   if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
 746   if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
 747   if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
 748   if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
 749
 750   for (int event_index = 0; event_index < 4; event_index++) {
 751     const EdgeEvent& event = events[event_index];
 752
 753     int delta = ComputeExpansionDelta(
 754         num_x_edges, num_y_edges, width, height, target_area);
 755
 756     // Clamp delta to our event distance.
 757     if (delta > event.distance)
 758       delta = event.distance;
 759
 760     // Adjust the edge count for this kind of edge.
 761     --*event.num_edges;
 762
 763     // Apply the delta to the edges and edge events.
 764     for (int i = event_index; i < 4; i++) {
 765       switch (events[i].edge) {
 766         case EdgeEvent::BOTTOM:
 767             origin_y -= delta;
 768             height += delta;
 769             break;
 770         case EdgeEvent::TOP:
 771             height += delta;
 772             break;
 773         case EdgeEvent::LEFT:
 774             origin_x -= delta;
 775             width += delta;
 776             break;
 777         case EdgeEvent::RIGHT:
 778             width += delta;
 779             break;
 780       }
 781       events[i].distance -= delta;
 782     }
 783
 784     // If our delta is less then our event distance, we're done.
 785     if (delta < event.distance)
 786       break;
 787   }
 788
 789   gfx::Rect result(origin_x, origin_y, width, height);
 790   if (cache)
 791     cache->previous_result = result;
 792   return result;
 793 }
 794
 795 }  // namespace cc