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 // We don't perform solid color analysis on images that have more than 10 skia
  23 // operations.
  24 const int kOpCountThatIsOkToAnalyze = 10;
  25
  26 // TODO(humper): The density threshold here is somewhat arbitrary; need a
  27 // way to set // this from the command line so we can write a benchmark
  28 // script and find a sweet spot.
  29 const float kDensityThreshold = 0.5f;
  30
  31 bool rect_sort_y(const gfx::Rect& r1, const gfx::Rect& r2) {
  32   return r1.y() < r2.y() || (r1.y() == r2.y() && r1.x() < r2.x());
  33 }
  34
  35 bool rect_sort_x(const gfx::Rect& r1, const gfx::Rect& r2) {
  36   return r1.x() < r2.x() || (r1.x() == r2.x() && r1.y() < r2.y());
  37 }
  38
  39 float PerformClustering(const std::vector<gfx::Rect>& tiles,
  40                         std::vector<gfx::Rect>* clustered_rects) {
  41   // These variables track the record area and invalid area
  42   // for the entire clustering
  43   int total_record_area = 0;
  44   int total_invalid_area = 0;
  45
  46   // These variables track the record area and invalid area
  47   // for the current cluster being constructed.
  48   gfx::Rect cur_record_rect;
  49   int cluster_record_area = 0, cluster_invalid_area = 0;
  50
  51   for (std::vector<gfx::Rect>::const_iterator it = tiles.begin();
  52         it != tiles.end();
  53         it++) {
  54     gfx::Rect invalid_tile = *it;
  55
  56     // For each tile, we consider adding the invalid tile to the
  57     // current record rectangle.  Only add it if the amount of empty
  58     // space created is below a density threshold.
  59     int tile_area = invalid_tile.width() * invalid_tile.height();
  60
  61     gfx::Rect proposed_union = cur_record_rect;
  62     proposed_union.Union(invalid_tile);
  63     int proposed_area = proposed_union.width() * proposed_union.height();
  64     float proposed_density =
  65       static_cast<float>(cluster_invalid_area + tile_area) /
  66       static_cast<float>(proposed_area);
  67
  68     if (proposed_density >= kDensityThreshold) {
  69       // It's okay to add this invalid tile to the
  70       // current recording rectangle.
  71       cur_record_rect = proposed_union;
  72       cluster_record_area = proposed_area;
  73       cluster_invalid_area += tile_area;
  74       total_invalid_area += tile_area;
  75     } else {
  76       // Adding this invalid tile to the current recording rectangle
  77       // would exceed our badness threshold, so put the current rectangle
  78       // in the list of recording rects, and start a new one.
  79       clustered_rects->push_back(cur_record_rect);
  80       total_record_area += cluster_record_area;
  81       cur_record_rect = invalid_tile;
  82       cluster_invalid_area = tile_area;
  83       cluster_record_area = tile_area;
  84     }
  85   }
  86
  87   DCHECK(!cur_record_rect.IsEmpty());
  88   clustered_rects->push_back(cur_record_rect);
  89   total_record_area += cluster_record_area;;
  90
  91   DCHECK_NE(total_record_area, 0);
  92
  93   return static_cast<float>(total_invalid_area) /
  94          static_cast<float>(total_record_area);
  95 }
  96
  97 float ClusterTiles(const std::vector<gfx::Rect>& invalid_tiles,
  98                    std::vector<gfx::Rect>* record_rects) {
  99   TRACE_EVENT1("cc", "ClusterTiles",
 100                "count",
 101                invalid_tiles.size());
 102
 103   if (invalid_tiles.size() <= 1) {
 104     // Quickly handle the special case for common
 105     // single-invalidation update, and also the less common
 106     // case of no tiles passed in.
 107     *record_rects = invalid_tiles;
 108     return 1;
 109   }
 110
 111   // Sort the invalid tiles by y coordinate.
 112   std::vector<gfx::Rect> invalid_tiles_vertical = invalid_tiles;
 113   std::sort(invalid_tiles_vertical.begin(),
 114             invalid_tiles_vertical.end(),
 115             rect_sort_y);
 116
 117   float vertical_density;
 118   std::vector<gfx::Rect> vertical_clustering;
 119   vertical_density = PerformClustering(invalid_tiles_vertical,
 120                                        &vertical_clustering);
 121
 122   // If vertical density is optimal, then we can return early.
 123   if (vertical_density == 1.f) {
 124     *record_rects = vertical_clustering;
 125     return vertical_density;
 126   }
 127
 128   // Now try again with a horizontal sort, see which one is best
 129   std::vector<gfx::Rect> invalid_tiles_horizontal = invalid_tiles;
 130   std::sort(invalid_tiles_horizontal.begin(),
 131             invalid_tiles_horizontal.end(),
 132             rect_sort_x);
 133
 134   float horizontal_density;
 135   std::vector<gfx::Rect> horizontal_clustering;
 136   horizontal_density = PerformClustering(invalid_tiles_horizontal,
 137                                          &horizontal_clustering);
 138
 139   if (vertical_density < horizontal_density) {
 140     *record_rects = horizontal_clustering;
 141     return horizontal_density;
 142   }
 143
 144   *record_rects = vertical_clustering;
 145   return vertical_density;
 146 }
 147
 148 }  // namespace
 149
 150 namespace cc {
 151
 152 PicturePile::PicturePile() : is_suitable_for_gpu_rasterization_(true) {
 153 }
 154
 155 PicturePile::~PicturePile() {
 156 }
 157
 158 bool PicturePile::UpdateAndExpandInvalidation(
 159     ContentLayerClient* painter,
 160     Region* invalidation,
 161     SkColor background_color,
 162     bool contents_opaque,
 163     bool contents_fill_bounds_completely,
 164     const gfx::Size& layer_size,
 165     const gfx::Rect& visible_layer_rect,
 166     int frame_number,
 167     Picture::RecordingMode recording_mode,
 168     RenderingStatsInstrumentation* stats_instrumentation) {
 169   background_color_ = background_color;
 170   contents_opaque_ = contents_opaque;
 171   contents_fill_bounds_completely_ = contents_fill_bounds_completely;
 172
 173   bool updated = false;
 174
 175   Region resize_invalidation;
 176   gfx::Size old_tiling_size = tiling_size();
 177   if (old_tiling_size != layer_size) {
 178     tiling_.SetTilingSize(layer_size);
 179     updated = true;
 180   }
 181
 182   gfx::Rect interest_rect = visible_layer_rect;
 183   interest_rect.Inset(
 184       -kPixelDistanceToRecord,
 185       -kPixelDistanceToRecord,
 186       -kPixelDistanceToRecord,
 187       -kPixelDistanceToRecord);
 188   recorded_viewport_ = interest_rect;
 189   recorded_viewport_.Intersect(gfx::Rect(tiling_size()));
 190
 191   gfx::Rect interest_rect_over_tiles =
 192       tiling_.ExpandRectToTileBounds(interest_rect);
 193
 194   if (old_tiling_size != layer_size) {
 195     has_any_recordings_ = false;
 196
 197     // Drop recordings that are outside the new layer bounds or that changed
 198     // size.
 199     std::vector<PictureMapKey> to_erase;
 200     int min_toss_x = tiling_.num_tiles_x();
 201     if (tiling_size().width() > old_tiling_size.width()) {
 202       min_toss_x =
 203           tiling_.FirstBorderTileXIndexFromSrcCoord(old_tiling_size.width());
 204     }
 205     int min_toss_y = tiling_.num_tiles_y();
 206     if (tiling_size().height() > old_tiling_size.height()) {
 207       min_toss_y =
 208           tiling_.FirstBorderTileYIndexFromSrcCoord(old_tiling_size.height());
 209     }
 210     for (PictureMap::const_iterator it = picture_map_.begin();
 211          it != picture_map_.end();
 212          ++it) {
 213       const PictureMapKey& key = it->first;
 214       if (key.first < min_toss_x && key.second < min_toss_y) {
 215         has_any_recordings_ |= !!it->second.GetPicture();
 216         continue;
 217       }
 218       to_erase.push_back(key);
 219     }
 220
 221     for (size_t i = 0; i < to_erase.size(); ++i)
 222       picture_map_.erase(to_erase[i]);
 223
 224     // If a recording is dropped and not re-recorded below, invalidate that
 225     // full recording to cause any raster tiles that would use it to be
 226     // dropped.
 227     // If the recording will be replaced below, just invalidate newly exposed
 228     // areas to force raster tiles that include the old recording to know
 229     // there is new recording to display.
 230     gfx::Rect old_tiling_rect_over_tiles =
 231         tiling_.ExpandRectToTileBounds(gfx::Rect(old_tiling_size));
 232     if (min_toss_x < tiling_.num_tiles_x()) {
 233       // The bounds which we want to invalidate are the tiles along the old
 234       // edge of the pile. We'll call this bounding box the OLD EDGE RECT.
 235       //
 236       // In the picture below, the old edge rect would be the bounding box
 237       // of tiles {h,i,j}. |min_toss_x| would be equal to the horizontal index
 238       // of the same tiles.
 239       //
 240       //  old pile edge-v  new pile edge-v
 241       // ---------------+ - - - - - - - -+
 242       // mmppssvvyybbeeh|h               .
 243       // mmppssvvyybbeeh|h               .
 244       // nnqqttwwzzccffi|i               .
 245       // nnqqttwwzzccffi|i               .
 246       // oorruuxxaaddggj|j               .
 247       // oorruuxxaaddggj|j               .
 248       // ---------------+ - - - - - - - -+ <- old pile edge
 249       //                                 .
 250       //  - - - - - - - - - - - - - - - -+ <- new pile edge
 251       //
 252       // If you were to slide a vertical beam from the left edge of the
 253       // old edge rect toward the right, it would either hit the right edge
 254       // of the old edge rect, or the interest rect (expanded to the bounds
 255       // of the tiles it touches). The same is true for a beam parallel to
 256       // any of the four edges, sliding accross the old edge rect. We use
 257       // the union of these four rectangles generated by these beams to
 258       // determine which part of the old edge rect is outside of the expanded
 259       // interest rect.
 260       //
 261       // Case 1: Intersect rect is outside the old edge rect. It can be
 262       // either on the left or the right. The |left_rect| and |right_rect|,
 263       // cover this case, one will be empty and one will cover the full
 264       // old edge rect. In the picture below, |left_rect| would cover the
 265       // old edge rect, and |right_rect| would be empty.
 266       // +----------------------+ |^^^^^^^^^^^^^^^|
 267       // |===>   OLD EDGE RECT  | |               |
 268       // |===>                  | | INTEREST RECT |
 269       // |===>                  | |               |
 270       // |===>                  | |               |
 271       // +----------------------+ |vvvvvvvvvvvvvvv|
 272       //
 273       // Case 2: Interest rect is inside the old edge rect. It will always
 274       // fill the entire old edge rect horizontally since the old edge rect
 275       // is a single tile wide, and the interest rect has been expanded to the
 276       // bounds of the tiles it touches. In this case the |left_rect| and
 277       // |right_rect| will be empty, but the case is handled by the |top_rect|
 278       // and |bottom_rect|. In the picture below, neither the |top_rect| nor
 279       // |bottom_rect| would empty, they would each cover the area of the old
 280       // edge rect outside the expanded interest rect.
 281       // +-----------------+
 282       // |:::::::::::::::::|
 283       // |:::::::::::::::::|
 284       // |vvvvvvvvvvvvvvvvv|
 285       // |                 |
 286       // +-----------------+
 287       // | INTEREST RECT   |
 288       // |                 |
 289       // +-----------------+
 290       // |                 |
 291       // | OLD EDGE RECT   |
 292       // +-----------------+
 293       //
 294       // Lastly, we need to consider tiles inside the expanded interest rect.
 295       // For those tiles, we want to invalidate exactly the newly exposed
 296       // pixels. In the picture below the tiles in the old edge rect have been
 297       // resized and the area covered by periods must be invalidated. The
 298       // |exposed_rect| will cover exactly that area.
 299       //           v-old pile edge
 300       // +---------+-------+
 301       // |         ........|
 302       // |         ........|
 303       // |  OLD EDGE.RECT..|
 304       // |         ........|
 305       // |         ........|
 306       // |         ........|
 307       // |         ........|
 308       // |         ........|
 309       // |         ........|
 310       // +---------+-------+
 311
 312       int left = tiling_.TilePositionX(min_toss_x);
 313       int right = left + tiling_.TileSizeX(min_toss_x);
 314       int top = old_tiling_rect_over_tiles.y();
 315       int bottom = old_tiling_rect_over_tiles.bottom();
 316
 317       int left_until = std::min(interest_rect_over_tiles.x(), right);
 318       int right_until = std::max(interest_rect_over_tiles.right(), left);
 319       int top_until = std::min(interest_rect_over_tiles.y(), bottom);
 320       int bottom_until = std::max(interest_rect_over_tiles.bottom(), top);
 321
 322       int exposed_left = old_tiling_size.width();
 323       int exposed_left_until = tiling_size().width();
 324       int exposed_top = top;
 325       int exposed_bottom = tiling_size().height();
 326       DCHECK_GE(exposed_left, left);
 327
 328       gfx::Rect left_rect(left, top, left_until - left, bottom - top);
 329       gfx::Rect right_rect(right_until, top, right - right_until, bottom - top);
 330       gfx::Rect top_rect(left, top, right - left, top_until - top);
 331       gfx::Rect bottom_rect(
 332           left, bottom_until, right - left, bottom - bottom_until);
 333       gfx::Rect exposed_rect(exposed_left,
 334                              exposed_top,
 335                              exposed_left_until - exposed_left,
 336                              exposed_bottom - exposed_top);
 337       resize_invalidation.Union(left_rect);
 338       resize_invalidation.Union(right_rect);
 339       resize_invalidation.Union(top_rect);
 340       resize_invalidation.Union(bottom_rect);
 341       resize_invalidation.Union(exposed_rect);
 342     }
 343     if (min_toss_y < tiling_.num_tiles_y()) {
 344       // The same thing occurs here as in the case above, but the invalidation
 345       // rect is the bounding box around the bottom row of tiles in the old
 346       // pile. This would be tiles {o,r,u,x,a,d,g,j} in the above picture.
 347
 348       int top = tiling_.TilePositionY(min_toss_y);
 349       int bottom = top + tiling_.TileSizeY(min_toss_y);
 350       int left = old_tiling_rect_over_tiles.x();
 351       int right = old_tiling_rect_over_tiles.right();
 352
 353       int top_until = std::min(interest_rect_over_tiles.y(), bottom);
 354       int bottom_until = std::max(interest_rect_over_tiles.bottom(), top);
 355       int left_until = std::min(interest_rect_over_tiles.x(), right);
 356       int right_until = std::max(interest_rect_over_tiles.right(), left);
 357
 358       int exposed_top = old_tiling_size.height();
 359       int exposed_top_until = tiling_size().height();
 360       int exposed_left = left;
 361       int exposed_right = tiling_size().width();
 362       DCHECK_GE(exposed_top, top);
 363
 364       gfx::Rect left_rect(left, top, left_until - left, bottom - top);
 365       gfx::Rect right_rect(right_until, top, right - right_until, bottom - top);
 366       gfx::Rect top_rect(left, top, right - left, top_until - top);
 367       gfx::Rect bottom_rect(
 368           left, bottom_until, right - left, bottom - bottom_until);
 369       gfx::Rect exposed_rect(exposed_left,
 370                              exposed_top,
 371                              exposed_right - exposed_left,
 372                              exposed_top_until - exposed_top);
 373       resize_invalidation.Union(left_rect);
 374       resize_invalidation.Union(right_rect);
 375       resize_invalidation.Union(top_rect);
 376       resize_invalidation.Union(bottom_rect);
 377       resize_invalidation.Union(exposed_rect);
 378     }
 379   }
 380
 381   Region invalidation_expanded_to_full_tiles;
 382   for (Region::Iterator i(*invalidation); i.has_rect(); i.next()) {
 383     gfx::Rect invalid_rect = i.rect();
 384
 385     // Expand invalidation that is outside tiles that intersect the interest
 386     // rect. These tiles are no longer valid and should be considerered fully
 387     // invalid, so we can know to not keep around raster tiles that intersect
 388     // with these recording tiles.
 389     gfx::Rect invalid_rect_outside_interest_rect_tiles = invalid_rect;
 390     // TODO(danakj): We should have a Rect-subtract-Rect-to-2-rects operator
 391     // instead of using Rect::Subtract which gives you the bounding box of the
 392     // subtraction.
 393     invalid_rect_outside_interest_rect_tiles.Subtract(interest_rect_over_tiles);
 394     invalidation_expanded_to_full_tiles.Union(tiling_.ExpandRectToTileBounds(
 395         invalid_rect_outside_interest_rect_tiles));
 396
 397     // Split this inflated invalidation across tile boundaries and apply it
 398     // to all tiles that it touches.
 399     bool include_borders = true;
 400     for (TilingData::Iterator iter(&tiling_, invalid_rect, include_borders);
 401          iter;
 402          ++iter) {
 403       const PictureMapKey& key = iter.index();
 404
 405       PictureMap::iterator picture_it = picture_map_.find(key);
 406       if (picture_it == picture_map_.end())
 407         continue;
 408
 409       // Inform the grid cell that it has been invalidated in this frame.
 410       updated = picture_it->second.Invalidate(frame_number) || updated;
 411       // Invalidate drops the picture so the whole tile better be invalidated if
 412       // it won't be re-recorded below.
 413       DCHECK(
 414           tiling_.TileBounds(key.first, key.second).Intersects(interest_rect) ||
 415           invalidation_expanded_to_full_tiles.Contains(
 416               tiling_.TileBounds(key.first, key.second)));
 417     }
 418   }
 419
 420   invalidation->Union(invalidation_expanded_to_full_tiles);
 421   invalidation->Union(resize_invalidation);
 422
 423   // Make a list of all invalid tiles; we will attempt to
 424   // cluster these into multiple invalidation regions.
 425   std::vector<gfx::Rect> invalid_tiles;
 426   bool include_borders = true;
 427   for (TilingData::Iterator it(&tiling_, interest_rect, include_borders); it;
 428        ++it) {
 429     const PictureMapKey& key = it.index();
 430     PictureInfo& info = picture_map_[key];
 431
 432     gfx::Rect rect = PaddedRect(key);
 433     int distance_to_visible =
 434         rect.ManhattanInternalDistance(visible_layer_rect);
 435
 436     if (info.NeedsRecording(frame_number, distance_to_visible)) {
 437       gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
 438       invalid_tiles.push_back(tile);
 439     } else if (!info.GetPicture()) {
 440       if (recorded_viewport_.Intersects(rect)) {
 441         // Recorded viewport is just an optimization for a fully recorded
 442         // interest rect.  In this case, a tile in that rect has declined
 443         // to be recorded (probably due to frequent invalidations).
 444         // TODO(enne): Shrink the recorded_viewport_ rather than clearing.
 445         recorded_viewport_ = gfx::Rect();
 446       }
 447
 448       // If a tile in the interest rect is not recorded, the entire tile needs
 449       // to be considered invalid, so that we know not to keep around raster
 450       // tiles that intersect this recording tile.
 451       invalidation->Union(tiling_.TileBounds(it.index_x(), it.index_y()));
 452     }
 453   }
 454
 455   std::vector<gfx::Rect> record_rects;
 456   ClusterTiles(invalid_tiles, &record_rects);
 457
 458   if (record_rects.empty())
 459     return updated;
 460
 461   for (std::vector<gfx::Rect>::iterator it = record_rects.begin();
 462        it != record_rects.end();
 463        it++) {
 464     gfx::Rect record_rect = *it;
 465     record_rect = PadRect(record_rect);
 466
 467     int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
 468     scoped_refptr<Picture> picture;
 469
 470     // Note: Currently, gathering of pixel refs when using a single
 471     // raster thread doesn't provide any benefit. This might change
 472     // in the future but we avoid it for now to reduce the cost of
 473     // Picture::Create.
 474     bool gather_pixel_refs = RasterWorkerPool::GetNumRasterThreads() > 1;
 475
 476     {
 477       base::TimeDelta best_duration = base::TimeDelta::Max();
 478       for (int i = 0; i < repeat_count; i++) {
 479         base::TimeTicks start_time = stats_instrumentation->StartRecording();
 480         picture = Picture::Create(record_rect,
 481                                   painter,
 482                                   tile_grid_info_,
 483                                   gather_pixel_refs,
 484                                   recording_mode);
 485         // Note the '&&' with previous is-suitable state.
 486         // This means that once a picture-pile becomes unsuitable for gpu
 487         // rasterization due to some content, it will continue to be unsuitable
 488         // even if that content is replaced by gpu-friendly content.
 489         // This is an optimization to avoid iterating though all pictures in
 490         // the pile after each invalidation.
 491         is_suitable_for_gpu_rasterization_ &=
 492             picture->IsSuitableForGpuRasterization();
 493         has_text_ |= picture->HasText();
 494         base::TimeDelta duration =
 495             stats_instrumentation->EndRecording(start_time);
 496         best_duration = std::min(duration, best_duration);
 497       }
 498       int recorded_pixel_count =
 499           picture->LayerRect().width() * picture->LayerRect().height();
 500       stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
 501     }
 502
 503     bool found_tile_for_recorded_picture = false;
 504
 505     bool include_borders = true;
 506     for (TilingData::Iterator it(&tiling_, record_rect, include_borders); it;
 507          ++it) {
 508       const PictureMapKey& key = it.index();
 509       gfx::Rect tile = PaddedRect(key);
 510       if (record_rect.Contains(tile)) {
 511         PictureInfo& info = picture_map_[key];
 512         info.SetPicture(picture);
 513         found_tile_for_recorded_picture = true;
 514       }
 515     }
 516     DetermineIfSolidColor();
 517     DCHECK(found_tile_for_recorded_picture);
 518   }
 519
 520   has_any_recordings_ = true;
 521   DCHECK(CanRasterSlowTileCheck(recorded_viewport_));
 522   return true;
 523 }
 524
 525 void PicturePile::SetEmptyBounds() {
 526   tiling_.SetTilingSize(gfx::Size());
 527   picture_map_.clear();
 528   has_any_recordings_ = false;
 529   recorded_viewport_ = gfx::Rect();
 530 }
 531
 532 void PicturePile::DetermineIfSolidColor() {
 533   is_solid_color_ = false;
 534   solid_color_ = SK_ColorTRANSPARENT;
 535
 536   if (picture_map_.empty()) {
 537     return;
 538   }
 539
 540   PictureMap::const_iterator it = picture_map_.begin();
 541   const Picture* picture = it->second.GetPicture();
 542
 543   // Missing recordings due to frequent invalidations or being too far away
 544   // from the interest rect will cause the a null picture to exist.
 545   if (!picture)
 546     return;
 547
 548   // Don't bother doing more work if the first image is too complicated.
 549   if (picture->ApproximateOpCount() > kOpCountThatIsOkToAnalyze)
 550     return;
 551
 552   // Make sure all of the mapped images point to the same picture.
 553   for (++it; it != picture_map_.end(); ++it) {
 554     if (it->second.GetPicture() != picture)
 555       return;
 556   }
 557   skia::AnalysisCanvas canvas(recorded_viewport_.width(),
 558                               recorded_viewport_.height());
 559   picture->Raster(&canvas, NULL, Region(), 1.0f);
 560   is_solid_color_ = canvas.GetColorIfSolid(&solid_color_);
 561 }
 562
 563 }  // namespace cc