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   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 namespace {
    343 
    344 bool NearlyOne(SkMScalar lhs) {
    345   return std::abs(lhs-1.0) < std::numeric_limits<float>::epsilon();
    346 }
    347 
    348 bool NearlyZero(SkMScalar lhs) {
    349   return std::abs(lhs) < std::numeric_limits<float>::epsilon();
    350 }
    351 
    352 bool ApproximatelyTranslation(const SkMatrix44& matrix) {
    353   return
    354       NearlyOne(matrix.get(0, 0)) &&
    355       NearlyZero(matrix.get(1, 0)) &&
    356       NearlyZero(matrix.get(2, 0)) &&
    357       matrix.get(3, 0) == 0 &&
    358       NearlyZero(matrix.get(0, 1)) &&
    359       NearlyOne(matrix.get(1, 1)) &&
    360       NearlyZero(matrix.get(2, 1)) &&
    361       matrix.get(3, 1) == 0 &&
    362       NearlyZero(matrix.get(0, 2)) &&
    363       NearlyZero(matrix.get(1, 2)) &&
    364       NearlyOne(matrix.get(2, 2)) &&
    365       matrix.get(3, 2) == 0 &&
    366       matrix.get(3, 3) == 1;
    367 }
    368 
    369 }  // namespace
    370 
    371 void PictureLayerTiling::UpdateTilePriorities(
    372     WhichTree tree,
    373     gfx::Size device_viewport,
    374     gfx::Rect viewport_in_layer_space,
    375     gfx::Rect visible_layer_rect,
    376     gfx::Size last_layer_bounds,
    377     gfx::Size current_layer_bounds,
    378     float last_layer_contents_scale,
    379     float current_layer_contents_scale,
    380     const gfx::Transform& last_screen_transform,
    381     const gfx::Transform& current_screen_transform,
    382     double current_frame_time_in_seconds,
    383     size_t max_tiles_for_interest_area) {
    384   if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
    385     // This should never be zero for the purposes of has_ever_been_updated().
    386     DCHECK_NE(current_frame_time_in_seconds, 0.0);
    387     return;
    388   }
    389   if (ContentRect().IsEmpty()) {
    390     last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
    391     return;
    392   }
    393 
    394   gfx::Rect viewport_in_content_space =
    395       gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
    396   gfx::Rect visible_content_rect =
    397       gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
    398 
    399   gfx::Size tile_size = tiling_data_.max_texture_size();
    400   int64 interest_rect_area =
    401       max_tiles_for_interest_area * tile_size.width() * tile_size.height();
    402 
    403   gfx::Rect starting_rect = visible_content_rect.IsEmpty()
    404                             ? viewport_in_content_space
    405                             : visible_content_rect;
    406   gfx::Rect interest_rect = ExpandRectEquallyToAreaBoundedBy(
    407       starting_rect,
    408       interest_rect_area,
    409       ContentRect());
    410   DCHECK(interest_rect.IsEmpty() ||
    411          ContentRect().Contains(interest_rect));
    412 
    413   SetLiveTilesRect(interest_rect);
    414 
    415   double time_delta = 0;
    416   if (last_impl_frame_time_in_seconds_ != 0.0 &&
    417       last_layer_bounds == current_layer_bounds) {
    418     time_delta =
    419         current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
    420   }
    421 
    422   gfx::Rect view_rect(device_viewport);
    423   float current_scale = current_layer_contents_scale / contents_scale_;
    424   float last_scale = last_layer_contents_scale / contents_scale_;
    425 
    426   bool store_screen_space_quads_on_tiles;
    427   TRACE_EVENT_CATEGORY_GROUP_ENABLED(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
    428                                      &store_screen_space_quads_on_tiles);
    429 
    430   // Fast path tile priority calculation when both transforms are translations.
    431   if (ApproximatelyTranslation(last_screen_transform.matrix()) &&
    432       ApproximatelyTranslation(current_screen_transform.matrix())) {
    433     gfx::Vector2dF current_offset(
    434         current_screen_transform.matrix().get(0, 3),
    435         current_screen_transform.matrix().get(1, 3));
    436     gfx::Vector2dF last_offset(
    437         last_screen_transform.matrix().get(0, 3),
    438         last_screen_transform.matrix().get(1, 3));
    439 
    440     for (TilingData::Iterator iter(&tiling_data_, interest_rect);
    441          iter; ++iter) {
    442       TileMap::iterator find = tiles_.find(iter.index());
    443       if (find == tiles_.end())
    444         continue;
    445       Tile* tile = find->second.get();
    446 
    447       gfx::Rect tile_bounds =
    448           tiling_data_.TileBounds(iter.index_x(), iter.index_y());
    449       gfx::RectF current_screen_rect = gfx::ScaleRect(
    450           tile_bounds,
    451           current_scale,
    452           current_scale) + current_offset;
    453       gfx::RectF last_screen_rect = gfx::ScaleRect(
    454           tile_bounds,
    455           last_scale,
    456           last_scale) + last_offset;
    457 
    458       float distance_to_visible_in_pixels =
    459           TilePriority::manhattanDistance(current_screen_rect, view_rect);
    460 
    461       float time_to_visible_in_seconds =
    462           TilePriority::TimeForBoundsToIntersect(
    463               last_screen_rect, current_screen_rect, time_delta, view_rect);
    464       TilePriority priority(
    465           resolution_,
    466           time_to_visible_in_seconds,
    467           distance_to_visible_in_pixels);
    468       if (store_screen_space_quads_on_tiles)
    469         priority.set_current_screen_quad(gfx::QuadF(current_screen_rect));
    470       tile->SetPriority(tree, priority);
    471     }
    472   } else if (!last_screen_transform.HasPerspective() &&
    473              !current_screen_transform.HasPerspective()) {
    474     // Secondary fast path that can be applied for any affine transforms.
    475 
    476     // Initialize the necessary geometry in screen space, so that we can
    477     // iterate over tiles in screen space without needing a costly transform
    478     // mapping for each tile.
    479 
    480     // Apply screen space transform to the local origin point (0, 0); only the
    481     // translation component is needed and can be initialized directly.
    482     gfx::Point current_screen_space_origin(
    483         current_screen_transform.matrix().get(0, 3),
    484         current_screen_transform.matrix().get(1, 3));
    485 
    486     gfx::Point last_screen_space_origin(
    487         last_screen_transform.matrix().get(0, 3),
    488         last_screen_transform.matrix().get(1, 3));
    489 
    490     float current_tile_width = tiling_data_.TileSizeX(0) * current_scale;
    491     float last_tile_width = tiling_data_.TileSizeX(0) * last_scale;
    492     float current_tile_height = tiling_data_.TileSizeY(0) * current_scale;
    493     float last_tile_height = tiling_data_.TileSizeY(0) * last_scale;
    494 
    495     // Apply screen space transform to local basis vectors (tile_width, 0) and
    496     // (0, tile_height); the math simplifies and can be initialized directly.
    497     gfx::Vector2dF current_horizontal(
    498         current_screen_transform.matrix().get(0, 0) * current_tile_width,
    499         current_screen_transform.matrix().get(1, 0) * current_tile_width);
    500     gfx::Vector2dF current_vertical(
    501         current_screen_transform.matrix().get(0, 1) * current_tile_height,
    502         current_screen_transform.matrix().get(1, 1) * current_tile_height);
    503 
    504     gfx::Vector2dF last_horizontal(
    505         last_screen_transform.matrix().get(0, 0) * last_tile_width,
    506         last_screen_transform.matrix().get(1, 0) * last_tile_width);
    507     gfx::Vector2dF last_vertical(
    508         last_screen_transform.matrix().get(0, 1) * last_tile_height,
    509         last_screen_transform.matrix().get(1, 1) * last_tile_height);
    510 
    511     for (TilingData::Iterator iter(&tiling_data_, interest_rect);
    512          iter; ++iter) {
    513       TileMap::iterator find = tiles_.find(iter.index());
    514       if (find == tiles_.end())
    515         continue;
    516 
    517       Tile* tile = find->second.get();
    518 
    519       int i = iter.index_x();
    520       int j = iter.index_y();
    521       gfx::PointF current_tile_origin = current_screen_space_origin +
    522               ScaleVector2d(current_horizontal, i) +
    523               ScaleVector2d(current_vertical, j);
    524       gfx::PointF last_tile_origin = last_screen_space_origin +
    525               ScaleVector2d(last_horizontal, i) +
    526               ScaleVector2d(last_vertical, j);
    527 
    528       gfx::RectF current_screen_rect = gfx::QuadF(
    529           current_tile_origin,
    530           current_tile_origin + current_horizontal,
    531           current_tile_origin + current_horizontal + current_vertical,
    532           current_tile_origin + current_vertical).BoundingBox();
    533 
    534       gfx::RectF last_screen_rect = gfx::QuadF(
    535           last_tile_origin,
    536           last_tile_origin + last_horizontal,
    537           last_tile_origin + last_horizontal + last_vertical,
    538           last_tile_origin + last_vertical).BoundingBox();
    539 
    540       float distance_to_visible_in_pixels =
    541           TilePriority::manhattanDistance(current_screen_rect, view_rect);
    542 
    543       float time_to_visible_in_seconds =
    544           TilePriority::TimeForBoundsToIntersect(
    545               last_screen_rect, current_screen_rect, time_delta, view_rect);
    546       TilePriority priority(
    547           resolution_,
    548           time_to_visible_in_seconds,
    549           distance_to_visible_in_pixels);
    550 
    551       if (store_screen_space_quads_on_tiles) {
    552         // This overhead is only triggered when logging event tracing data.
    553         gfx::Rect tile_bounds =
    554             tiling_data_.TileBounds(iter.index_x(), iter.index_y());
    555         gfx::RectF current_layer_content_rect = gfx::ScaleRect(
    556             tile_bounds,
    557             current_scale,
    558             current_scale);
    559         bool clipped;
    560         priority.set_current_screen_quad(
    561             MathUtil::MapQuad(current_screen_transform,
    562                               gfx::QuadF(current_layer_content_rect),
    563                               &clipped));
    564       }
    565       tile->SetPriority(tree, priority);
    566     }
    567   } else {
    568     for (TilingData::Iterator iter(&tiling_data_, interest_rect);
    569          iter; ++iter) {
    570       TileMap::iterator find = tiles_.find(iter.index());
    571       if (find == tiles_.end())
    572         continue;
    573       Tile* tile = find->second.get();
    574 
    575       gfx::Rect tile_bounds =
    576           tiling_data_.TileBounds(iter.index_x(), iter.index_y());
    577       gfx::RectF current_layer_content_rect = gfx::ScaleRect(
    578           tile_bounds,
    579           current_scale,
    580           current_scale);
    581       gfx::RectF current_screen_rect = MathUtil::MapClippedRect(
    582           current_screen_transform, current_layer_content_rect);
    583       gfx::RectF last_layer_content_rect = gfx::ScaleRect(
    584           tile_bounds,
    585           last_scale,
    586           last_scale);
    587       gfx::RectF last_screen_rect  = MathUtil::MapClippedRect(
    588           last_screen_transform, last_layer_content_rect);
    589 
    590       float distance_to_visible_in_pixels =
    591           TilePriority::manhattanDistance(current_screen_rect, view_rect);
    592 
    593       float time_to_visible_in_seconds =
    594           TilePriority::TimeForBoundsToIntersect(
    595               last_screen_rect, current_screen_rect, time_delta, view_rect);
    596 
    597       TilePriority priority(
    598           resolution_,
    599           time_to_visible_in_seconds,
    600           distance_to_visible_in_pixels);
    601       if (store_screen_space_quads_on_tiles) {
    602         bool clipped;
    603         priority.set_current_screen_quad(
    604             MathUtil::MapQuad(current_screen_transform,
    605                               gfx::QuadF(current_layer_content_rect),
    606                               &clipped));
    607       }
    608       tile->SetPriority(tree, priority);
    609     }
    610   }
    611 
    612   last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
    613 }
    614 
    615 void PictureLayerTiling::SetLiveTilesRect(
    616     gfx::Rect new_live_tiles_rect) {
    617   DCHECK(new_live_tiles_rect.IsEmpty() ||
    618          ContentRect().Contains(new_live_tiles_rect));
    619   if (live_tiles_rect_ == new_live_tiles_rect)
    620     return;
    621 
    622   // Iterate to delete all tiles outside of our new live_tiles rect.
    623   for (TilingData::DifferenceIterator iter(&tiling_data_,
    624                                            live_tiles_rect_,
    625                                            new_live_tiles_rect);
    626        iter;
    627        ++iter) {
    628     TileMapKey key(iter.index());
    629     TileMap::iterator found = tiles_.find(key);
    630     // If the tile was outside of the recorded region, it won't exist even
    631     // though it was in the live rect.
    632     if (found != tiles_.end())
    633       tiles_.erase(found);
    634   }
    635 
    636   const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
    637 
    638   // Iterate to allocate new tiles for all regions with newly exposed area.
    639   for (TilingData::DifferenceIterator iter(&tiling_data_,
    640                                            new_live_tiles_rect,
    641                                            live_tiles_rect_);
    642        iter;
    643        ++iter) {
    644     TileMapKey key(iter.index());
    645     CreateTile(key.first, key.second, twin_tiling);
    646   }
    647 
    648   live_tiles_rect_ = new_live_tiles_rect;
    649 }
    650 
    651 void PictureLayerTiling::DidBecomeActive() {
    652   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
    653     it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
    654     it->second->SetPriority(PENDING_TREE, TilePriority());
    655 
    656     // Tile holds a ref onto a picture pile. If the tile never gets invalidated
    657     // and recreated, then that picture pile ref could exist indefinitely.  To
    658     // prevent this, ask the client to update the pile to its own ref.  This
    659     // will cause PicturePileImpls and their clones to get deleted once the
    660     // corresponding PictureLayerImpl and any in flight raster jobs go out of
    661     // scope.
    662     client_->UpdatePile(it->second.get());
    663   }
    664 }
    665 
    666 void PictureLayerTiling::UpdateTilesToCurrentPile() {
    667   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
    668     client_->UpdatePile(it->second.get());
    669   }
    670 }
    671 
    672 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
    673   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
    674   state->SetInteger("num_tiles", tiles_.size());
    675   state->SetDouble("content_scale", contents_scale_);
    676   state->Set("content_bounds",
    677              MathUtil::AsValue(ContentRect().size()).release());
    678   return state.PassAs<base::Value>();
    679 }
    680 
    681 size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
    682   size_t amount = 0;
    683   for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
    684     const Tile* tile = it->second.get();
    685     amount += tile->GPUMemoryUsageInBytes();
    686   }
    687   return amount;
    688 }
    689 
    690 namespace {
    691 
    692 // This struct represents an event at which the expending rect intersects
    693 // one of its boundaries.  4 intersection events will occur during expansion.
    694 struct EdgeEvent {
    695   enum { BOTTOM, TOP, LEFT, RIGHT } edge;
    696   int* num_edges;
    697   int distance;
    698 };
    699 
    700 // Compute the delta to expand from edges to cover target_area.
    701 int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
    702                           int width, int height,
    703                           int64 target_area) {
    704   // Compute coefficients for the quadratic equation:
    705   //   a*x^2 + b*x + c = 0
    706   int a = num_y_edges * num_x_edges;
    707   int b = num_y_edges * width + num_x_edges * height;
    708   int64 c = static_cast<int64>(width) * height - target_area;
    709 
    710   // Compute the delta for our edges using the quadratic equation.
    711   return a == 0 ? -c / b :
    712      (-b + static_cast<int>(
    713          std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
    714 }
    715 
    716 }  // namespace
    717 
    718 gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
    719     gfx::Rect starting_rect,
    720     int64 target_area,
    721     gfx::Rect bounding_rect) {
    722   if (starting_rect.IsEmpty())
    723     return starting_rect;
    724 
    725   DCHECK(!bounding_rect.IsEmpty());
    726   DCHECK_GT(target_area, 0);
    727 
    728   // Expand the starting rect to cover target_area, if it is smaller than it.
    729   int delta = ComputeExpansionDelta(
    730       2, 2, starting_rect.width(), starting_rect.height(), target_area);
    731   gfx::Rect expanded_starting_rect = starting_rect;
    732   if (delta > 0)
    733     expanded_starting_rect.Inset(-delta, -delta);
    734 
    735   gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
    736   if (rect.IsEmpty()) {
    737     // The starting_rect and bounding_rect are far away.
    738     return rect;
    739   }
    740   if (delta >= 0 && rect == expanded_starting_rect) {
    741     // The starting rect already covers the entire bounding_rect and isn't too
    742     // large for the target_area.
    743     return rect;
    744   }
    745 
    746   // Continue to expand/shrink rect to let it cover target_area.
    747 
    748   // These values will be updated by the loop and uses as the output.
    749   int origin_x = rect.x();
    750   int origin_y = rect.y();
    751   int width = rect.width();
    752   int height = rect.height();
    753 
    754   // In the beginning we will consider 2 edges in each dimension.
    755   int num_y_edges = 2;
    756   int num_x_edges = 2;
    757 
    758   // Create an event list.
    759   EdgeEvent events[] = {
    760     { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
    761     { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
    762     { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
    763     { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
    764   };
    765 
    766   // Sort the events by distance (closest first).
    767   if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
    768   if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
    769   if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
    770   if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
    771   if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
    772 
    773   for (int event_index = 0; event_index < 4; event_index++) {
    774     const EdgeEvent& event = events[event_index];
    775 
    776     int delta = ComputeExpansionDelta(
    777         num_x_edges, num_y_edges, width, height, target_area);
    778 
    779     // Clamp delta to our event distance.
    780     if (delta > event.distance)
    781       delta = event.distance;
    782 
    783     // Adjust the edge count for this kind of edge.
    784     --*event.num_edges;
    785 
    786     // Apply the delta to the edges and edge events.
    787     for (int i = event_index; i < 4; i++) {
    788       switch (events[i].edge) {
    789         case EdgeEvent::BOTTOM:
    790             origin_y -= delta;
    791             height += delta;
    792             break;
    793         case EdgeEvent::TOP:
    794             height += delta;
    795             break;
    796         case EdgeEvent::LEFT:
    797             origin_x -= delta;
    798             width += delta;
    799             break;
    800         case EdgeEvent::RIGHT:
    801             width += delta;
    802             break;
    803       }
    804       events[i].distance -= delta;
    805     }
    806 
    807     // If our delta is less then our event distance, we're done.
    808     if (delta < event.distance)
    809       break;
    810   }
    811 
    812   return gfx::Rect(origin_x, origin_y, width, height);
    813 }
    814 
    815 }  // namespace cc
    816