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