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_pile.h"
      6 
      7 #include <algorithm>
      8 #include <limits>
      9 #include <vector>
     10 
     11 #include "cc/base/region.h"
     12 #include "cc/debug/rendering_stats_instrumentation.h"
     13 #include "cc/resources/picture_pile_impl.h"
     14 #include "cc/resources/tile_priority.h"
     15 
     16 namespace {
     17 // Layout pixel buffer around the visible layer rect to record.  Any base
     18 // picture that intersects the visible layer rect expanded by this distance
     19 // will be recorded.
     20 const int kPixelDistanceToRecord = 8000;
     21 
     22 // TODO(humper): The density threshold here is somewhat arbitrary; need a
     23 // way to set // this from the command line so we can write a benchmark
     24 // script and find a sweet spot.
     25 const float kDensityThreshold = 0.5f;
     26 
     27 bool rect_sort_y(const gfx::Rect &r1, const gfx::Rect &r2) {
     28   return r1.y() < r2.y() || (r1.y() == r2.y() && r1.x() < r2.x());
     29 }
     30 
     31 bool rect_sort_x(const gfx::Rect &r1, const gfx::Rect &r2) {
     32   return r1.x() < r2.x() || (r1.x() == r2.x() && r1.y() < r2.y());
     33 }
     34 
     35 float do_clustering(const std::vector<gfx::Rect>& tiles,
     36                     std::vector<gfx::Rect>* clustered_rects) {
     37   // These variables track the record area and invalid area
     38   // for the entire clustering
     39   int total_record_area = 0;
     40   int total_invalid_area = 0;
     41 
     42   // These variables track the record area and invalid area
     43   // for the current cluster being constructed.
     44   gfx::Rect cur_record_rect;
     45   int cluster_record_area = 0, cluster_invalid_area = 0;
     46 
     47   for (std::vector<gfx::Rect>::const_iterator it = tiles.begin();
     48         it != tiles.end();
     49         it++) {
     50     gfx::Rect invalid_tile = *it;
     51 
     52     // For each tile, we consider adding the invalid tile to the
     53     // current record rectangle.  Only add it if the amount of empty
     54     // space created is below a density threshold.
     55     int tile_area = invalid_tile.width() * invalid_tile.height();
     56 
     57     gfx::Rect proposed_union = cur_record_rect;
     58     proposed_union.Union(invalid_tile);
     59     int proposed_area = proposed_union.width() * proposed_union.height();
     60     float proposed_density =
     61       static_cast<float>(cluster_invalid_area + tile_area) /
     62       static_cast<float>(proposed_area);
     63 
     64     if (proposed_density >= kDensityThreshold) {
     65       // It's okay to add this invalid tile to the
     66       // current recording rectangle.
     67       cur_record_rect = proposed_union;
     68       cluster_record_area = proposed_area;
     69       cluster_invalid_area += tile_area;
     70       total_invalid_area += tile_area;
     71     } else {
     72       // Adding this invalid tile to the current recording rectangle
     73       // would exceed our badness threshold, so put the current rectangle
     74       // in the list of recording rects, and start a new one.
     75       clustered_rects->push_back(cur_record_rect);
     76       total_record_area += cluster_record_area;
     77       cur_record_rect = invalid_tile;
     78       cluster_invalid_area = tile_area;
     79       cluster_record_area = tile_area;
     80     }
     81   }
     82 
     83   DCHECK(!cur_record_rect.IsEmpty());
     84   clustered_rects->push_back(cur_record_rect);
     85   total_record_area += cluster_record_area;;
     86 
     87   DCHECK_NE(total_record_area, 0);
     88 
     89   return static_cast<float>(total_invalid_area) /
     90          static_cast<float>(total_record_area);
     91   }
     92 
     93 float ClusterTiles(const std::vector<gfx::Rect>& invalid_tiles,
     94                    std::vector<gfx::Rect>* record_rects) {
     95   TRACE_EVENT1("cc", "ClusterTiles",
     96                "count",
     97                invalid_tiles.size());
     98 
     99   if (invalid_tiles.size() <= 1) {
    100     // Quickly handle the special case for common
    101     // single-invalidation update, and also the less common
    102     // case of no tiles passed in.
    103     *record_rects = invalid_tiles;
    104     return 1;
    105   }
    106 
    107   // Sort the invalid tiles by y coordinate.
    108   std::vector<gfx::Rect> invalid_tiles_vertical = invalid_tiles;
    109   std::sort(invalid_tiles_vertical.begin(),
    110             invalid_tiles_vertical.end(),
    111             rect_sort_y);
    112 
    113   float vertical_density;
    114   std::vector<gfx::Rect> vertical_clustering;
    115   vertical_density = do_clustering(invalid_tiles_vertical,
    116                                    &vertical_clustering);
    117 
    118   // Now try again with a horizontal sort, see which one is best
    119   // TODO(humper): Heuristics for skipping this step?
    120   std::vector<gfx::Rect> invalid_tiles_horizontal = invalid_tiles;
    121   std::sort(invalid_tiles_vertical.begin(),
    122             invalid_tiles_vertical.end(),
    123             rect_sort_x);
    124 
    125   float horizontal_density;
    126   std::vector<gfx::Rect> horizontal_clustering;
    127   horizontal_density = do_clustering(invalid_tiles_vertical,
    128                                      &horizontal_clustering);
    129 
    130   if (vertical_density < horizontal_density) {
    131     *record_rects = horizontal_clustering;
    132     return horizontal_density;
    133   }
    134 
    135   *record_rects = vertical_clustering;
    136   return vertical_density;
    137 }
    138 
    139 }  // namespace
    140 
    141 namespace cc {
    142 
    143 PicturePile::PicturePile() {
    144 }
    145 
    146 PicturePile::~PicturePile() {
    147 }
    148 
    149 bool PicturePile::Update(
    150     ContentLayerClient* painter,
    151     SkColor background_color,
    152     bool contents_opaque,
    153     const Region& invalidation,
    154     gfx::Rect visible_layer_rect,
    155     int frame_number,
    156     RenderingStatsInstrumentation* stats_instrumentation) {
    157   background_color_ = background_color;
    158   contents_opaque_ = contents_opaque;
    159 
    160   gfx::Rect interest_rect = visible_layer_rect;
    161   interest_rect.Inset(
    162       -kPixelDistanceToRecord,
    163       -kPixelDistanceToRecord,
    164       -kPixelDistanceToRecord,
    165       -kPixelDistanceToRecord);
    166   recorded_viewport_ = interest_rect;
    167   recorded_viewport_.Intersect(gfx::Rect(size()));
    168 
    169   bool invalidated = false;
    170   for (Region::Iterator i(invalidation); i.has_rect(); i.next()) {
    171     gfx::Rect invalidation = i.rect();
    172     // Split this inflated invalidation across tile boundaries and apply it
    173     // to all tiles that it touches.
    174     bool include_borders = true;
    175     for (TilingData::Iterator iter(&tiling_, invalidation, include_borders);
    176          iter;
    177          ++iter) {
    178       const PictureMapKey& key = iter.index();
    179 
    180       PictureMap::iterator picture_it = picture_map_.find(key);
    181       if (picture_it == picture_map_.end())
    182         continue;
    183 
    184       // Inform the grid cell that it has been invalidated in this frame.
    185       invalidated = picture_it->second.Invalidate(frame_number) || invalidated;
    186     }
    187   }
    188 
    189   // Make a list of all invalid tiles; we will attempt to
    190   // cluster these into multiple invalidation regions.
    191   std::vector<gfx::Rect> invalid_tiles;
    192   bool include_borders = true;
    193   for (TilingData::Iterator it(&tiling_, interest_rect, include_borders); it;
    194        ++it) {
    195     const PictureMapKey& key = it.index();
    196     PictureInfo& info = picture_map_[key];
    197 
    198     gfx::Rect rect = PaddedRect(key);
    199     int distance_to_visible =
    200         rect.ManhattanInternalDistance(visible_layer_rect);
    201 
    202     if (info.NeedsRecording(frame_number, distance_to_visible)) {
    203       gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
    204       invalid_tiles.push_back(tile);
    205     } else if (!info.GetPicture() && recorded_viewport_.Intersects(rect)) {
    206       // Recorded viewport is just an optimization for a fully recorded
    207       // interest rect.  In this case, a tile in that rect has declined
    208       // to be recorded (probably due to frequent invalidations).
    209       // TODO(enne): Shrink the recorded_viewport_ rather than clearing.
    210       recorded_viewport_ = gfx::Rect();
    211     }
    212   }
    213 
    214   std::vector<gfx::Rect> record_rects;
    215   ClusterTiles(invalid_tiles, &record_rects);
    216 
    217   if (record_rects.empty())
    218     return invalidated;
    219 
    220   for (std::vector<gfx::Rect>::iterator it = record_rects.begin();
    221        it != record_rects.end();
    222        it++) {
    223     gfx::Rect record_rect = *it;
    224     record_rect = PadRect(record_rect);
    225 
    226     int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
    227     scoped_refptr<Picture> picture = Picture::Create(record_rect);
    228 
    229     {
    230       base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
    231           std::numeric_limits<int64>::max());
    232       for (int i = 0; i < repeat_count; i++) {
    233         base::TimeTicks start_time = stats_instrumentation->StartRecording();
    234         picture->Record(painter, tile_grid_info_);
    235         base::TimeDelta duration =
    236             stats_instrumentation->EndRecording(start_time);
    237         best_duration = std::min(duration, best_duration);
    238       }
    239       int recorded_pixel_count =
    240           picture->LayerRect().width() * picture->LayerRect().height();
    241       stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
    242       if (num_raster_threads_ > 1)
    243         picture->GatherPixelRefs(tile_grid_info_);
    244       picture->CloneForDrawing(num_raster_threads_);
    245     }
    246 
    247     bool found_tile_for_recorded_picture = false;
    248 
    249     bool include_borders = true;
    250     for (TilingData::Iterator it(&tiling_, record_rect, include_borders); it;
    251          ++it) {
    252       const PictureMapKey& key = it.index();
    253       gfx::Rect tile = PaddedRect(key);
    254       if (record_rect.Contains(tile)) {
    255         PictureInfo& info = picture_map_[key];
    256         info.SetPicture(picture);
    257         found_tile_for_recorded_picture = true;
    258       }
    259     }
    260     DCHECK(found_tile_for_recorded_picture);
    261   }
    262 
    263   has_any_recordings_ = true;
    264   DCHECK(CanRasterSlowTileCheck(recorded_viewport_));
    265   return true;
    266 }
    267 
    268 }  // namespace cc
    269