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