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