#include "cc/base/region.h"
#include "cc/debug/rendering_stats_instrumentation.h"
#include "cc/resources/picture_pile_impl.h"
+#include "cc/resources/raster_worker_pool.h"
+#include "cc/resources/tile_priority.h"
namespace {
// Layout pixel buffer around the visible layer rect to record. Any base
// picture that intersects the visible layer rect expanded by this distance
// will be recorded.
const int kPixelDistanceToRecord = 8000;
+
+// TODO(humper): The density threshold here is somewhat arbitrary; need a
+// way to set // this from the command line so we can write a benchmark
+// script and find a sweet spot.
+const float kDensityThreshold = 0.5f;
+
+bool rect_sort_y(const gfx::Rect& r1, const gfx::Rect& r2) {
+ return r1.y() < r2.y() || (r1.y() == r2.y() && r1.x() < r2.x());
+}
+
+bool rect_sort_x(const gfx::Rect& r1, const gfx::Rect& r2) {
+ return r1.x() < r2.x() || (r1.x() == r2.x() && r1.y() < r2.y());
+}
+
+float PerformClustering(const std::vector<gfx::Rect>& tiles,
+ std::vector<gfx::Rect>* clustered_rects) {
+ // These variables track the record area and invalid area
+ // for the entire clustering
+ int total_record_area = 0;
+ int total_invalid_area = 0;
+
+ // These variables track the record area and invalid area
+ // for the current cluster being constructed.
+ gfx::Rect cur_record_rect;
+ int cluster_record_area = 0, cluster_invalid_area = 0;
+
+ for (std::vector<gfx::Rect>::const_iterator it = tiles.begin();
+ it != tiles.end();
+ it++) {
+ gfx::Rect invalid_tile = *it;
+
+ // For each tile, we consider adding the invalid tile to the
+ // current record rectangle. Only add it if the amount of empty
+ // space created is below a density threshold.
+ int tile_area = invalid_tile.width() * invalid_tile.height();
+
+ gfx::Rect proposed_union = cur_record_rect;
+ proposed_union.Union(invalid_tile);
+ int proposed_area = proposed_union.width() * proposed_union.height();
+ float proposed_density =
+ static_cast<float>(cluster_invalid_area + tile_area) /
+ static_cast<float>(proposed_area);
+
+ if (proposed_density >= kDensityThreshold) {
+ // It's okay to add this invalid tile to the
+ // current recording rectangle.
+ cur_record_rect = proposed_union;
+ cluster_record_area = proposed_area;
+ cluster_invalid_area += tile_area;
+ total_invalid_area += tile_area;
+ } else {
+ // Adding this invalid tile to the current recording rectangle
+ // would exceed our badness threshold, so put the current rectangle
+ // in the list of recording rects, and start a new one.
+ clustered_rects->push_back(cur_record_rect);
+ total_record_area += cluster_record_area;
+ cur_record_rect = invalid_tile;
+ cluster_invalid_area = tile_area;
+ cluster_record_area = tile_area;
+ }
+ }
+
+ DCHECK(!cur_record_rect.IsEmpty());
+ clustered_rects->push_back(cur_record_rect);
+ total_record_area += cluster_record_area;;
+
+ DCHECK_NE(total_record_area, 0);
+
+ return static_cast<float>(total_invalid_area) /
+ static_cast<float>(total_record_area);
+}
+
+float ClusterTiles(const std::vector<gfx::Rect>& invalid_tiles,
+ std::vector<gfx::Rect>* record_rects) {
+ TRACE_EVENT1("cc", "ClusterTiles",
+ "count",
+ invalid_tiles.size());
+
+ if (invalid_tiles.size() <= 1) {
+ // Quickly handle the special case for common
+ // single-invalidation update, and also the less common
+ // case of no tiles passed in.
+ *record_rects = invalid_tiles;
+ return 1;
+ }
+
+ // Sort the invalid tiles by y coordinate.
+ std::vector<gfx::Rect> invalid_tiles_vertical = invalid_tiles;
+ std::sort(invalid_tiles_vertical.begin(),
+ invalid_tiles_vertical.end(),
+ rect_sort_y);
+
+ float vertical_density;
+ std::vector<gfx::Rect> vertical_clustering;
+ vertical_density = PerformClustering(invalid_tiles_vertical,
+ &vertical_clustering);
+
+ // If vertical density is optimal, then we can return early.
+ if (vertical_density == 1.f) {
+ *record_rects = vertical_clustering;
+ return vertical_density;
+ }
+
+ // Now try again with a horizontal sort, see which one is best
+ std::vector<gfx::Rect> invalid_tiles_horizontal = invalid_tiles;
+ std::sort(invalid_tiles_horizontal.begin(),
+ invalid_tiles_horizontal.end(),
+ rect_sort_x);
+
+ float horizontal_density;
+ std::vector<gfx::Rect> horizontal_clustering;
+ horizontal_density = PerformClustering(invalid_tiles_horizontal,
+ &horizontal_clustering);
+
+ if (vertical_density < horizontal_density) {
+ *record_rects = horizontal_clustering;
+ return horizontal_density;
+ }
+
+ *record_rects = vertical_clustering;
+ return vertical_density;
+}
+
} // namespace
namespace cc {
-PicturePile::PicturePile() {
-}
+PicturePile::PicturePile() : is_suitable_for_gpu_rasterization_(true) {}
PicturePile::~PicturePile() {
}
-bool PicturePile::Update(
+bool PicturePile::UpdateAndExpandInvalidation(
ContentLayerClient* painter,
+ Region* invalidation,
SkColor background_color,
bool contents_opaque,
- const Region& invalidation,
- gfx::Rect visible_layer_rect,
+ bool contents_fill_bounds_completely,
+ const gfx::Size& layer_size,
+ const gfx::Rect& visible_layer_rect,
+ int frame_number,
+ Picture::RecordingMode recording_mode,
RenderingStatsInstrumentation* stats_instrumentation) {
background_color_ = background_color;
contents_opaque_ = contents_opaque;
+ contents_fill_bounds_completely_ = contents_fill_bounds_completely;
+
+ bool updated = false;
+
+ Region resize_invalidation;
+ gfx::Size old_tiling_size = tiling_size();
+ if (old_tiling_size != layer_size) {
+ tiling_.SetTilingSize(layer_size);
+ updated = true;
+ }
gfx::Rect interest_rect = visible_layer_rect;
interest_rect.Inset(
-kPixelDistanceToRecord,
-kPixelDistanceToRecord,
-kPixelDistanceToRecord);
+ recorded_viewport_ = interest_rect;
+ recorded_viewport_.Intersect(gfx::Rect(tiling_size()));
+
+ gfx::Rect interest_rect_over_tiles =
+ tiling_.ExpandRectToTileBounds(interest_rect);
+
+ if (old_tiling_size != layer_size) {
+ has_any_recordings_ = false;
+
+ // Drop recordings that are outside the new layer bounds or that changed
+ // size.
+ std::vector<PictureMapKey> to_erase;
+ int min_toss_x = tiling_.num_tiles_x();
+ if (tiling_size().width() > old_tiling_size.width()) {
+ min_toss_x =
+ tiling_.FirstBorderTileXIndexFromSrcCoord(old_tiling_size.width());
+ }
+ int min_toss_y = tiling_.num_tiles_y();
+ if (tiling_size().height() > old_tiling_size.height()) {
+ min_toss_y =
+ tiling_.FirstBorderTileYIndexFromSrcCoord(old_tiling_size.height());
+ }
+ for (PictureMap::const_iterator it = picture_map_.begin();
+ it != picture_map_.end();
+ ++it) {
+ const PictureMapKey& key = it->first;
+ if (key.first < min_toss_x && key.second < min_toss_y) {
+ has_any_recordings_ |= !!it->second.GetPicture();
+ continue;
+ }
+ to_erase.push_back(key);
+ }
+
+ for (size_t i = 0; i < to_erase.size(); ++i)
+ picture_map_.erase(to_erase[i]);
+
+ // If a recording is dropped and not re-recorded below, invalidate that
+ // full recording to cause any raster tiles that would use it to be
+ // dropped.
+ // If the recording will be replaced below, just invalidate newly exposed
+ // areas to force raster tiles that include the old recording to know
+ // there is new recording to display.
+ gfx::Rect old_tiling_rect_over_tiles =
+ tiling_.ExpandRectToTileBounds(gfx::Rect(old_tiling_size));
+ if (min_toss_x < tiling_.num_tiles_x()) {
+ // The bounds which we want to invalidate are the tiles along the old
+ // edge of the pile. We'll call this bounding box the OLD EDGE RECT.
+ //
+ // In the picture below, the old edge rect would be the bounding box
+ // of tiles {h,i,j}. |min_toss_x| would be equal to the horizontal index
+ // of the same tiles.
+ //
+ // old pile edge-v new pile edge-v
+ // ---------------+ - - - - - - - -+
+ // mmppssvvyybbeeh|h .
+ // mmppssvvyybbeeh|h .
+ // nnqqttwwzzccffi|i .
+ // nnqqttwwzzccffi|i .
+ // oorruuxxaaddggj|j .
+ // oorruuxxaaddggj|j .
+ // ---------------+ - - - - - - - -+ <- old pile edge
+ // .
+ // - - - - - - - - - - - - - - - -+ <- new pile edge
+ //
+ // If you were to slide a vertical beam from the left edge of the
+ // old edge rect toward the right, it would either hit the right edge
+ // of the old edge rect, or the interest rect (expanded to the bounds
+ // of the tiles it touches). The same is true for a beam parallel to
+ // any of the four edges, sliding accross the old edge rect. We use
+ // the union of these four rectangles generated by these beams to
+ // determine which part of the old edge rect is outside of the expanded
+ // interest rect.
+ //
+ // Case 1: Intersect rect is outside the old edge rect. It can be
+ // either on the left or the right. The |left_rect| and |right_rect|,
+ // cover this case, one will be empty and one will cover the full
+ // old edge rect. In the picture below, |left_rect| would cover the
+ // old edge rect, and |right_rect| would be empty.
+ // +----------------------+ |^^^^^^^^^^^^^^^|
+ // |===> OLD EDGE RECT | | |
+ // |===> | | INTEREST RECT |
+ // |===> | | |
+ // |===> | | |
+ // +----------------------+ |vvvvvvvvvvvvvvv|
+ //
+ // Case 2: Interest rect is inside the old edge rect. It will always
+ // fill the entire old edge rect horizontally since the old edge rect
+ // is a single tile wide, and the interest rect has been expanded to the
+ // bounds of the tiles it touches. In this case the |left_rect| and
+ // |right_rect| will be empty, but the case is handled by the |top_rect|
+ // and |bottom_rect|. In the picture below, neither the |top_rect| nor
+ // |bottom_rect| would empty, they would each cover the area of the old
+ // edge rect outside the expanded interest rect.
+ // +-----------------+
+ // |:::::::::::::::::|
+ // |:::::::::::::::::|
+ // |vvvvvvvvvvvvvvvvv|
+ // | |
+ // +-----------------+
+ // | INTEREST RECT |
+ // | |
+ // +-----------------+
+ // | |
+ // | OLD EDGE RECT |
+ // +-----------------+
+ //
+ // Lastly, we need to consider tiles inside the expanded interest rect.
+ // For those tiles, we want to invalidate exactly the newly exposed
+ // pixels. In the picture below the tiles in the old edge rect have been
+ // resized and the area covered by periods must be invalidated. The
+ // |exposed_rect| will cover exactly that area.
+ // v-old pile edge
+ // +---------+-------+
+ // | ........|
+ // | ........|
+ // | OLD EDGE.RECT..|
+ // | ........|
+ // | ........|
+ // | ........|
+ // | ........|
+ // | ........|
+ // | ........|
+ // +---------+-------+
+
+ int left = tiling_.TilePositionX(min_toss_x);
+ int right = left + tiling_.TileSizeX(min_toss_x);
+ int top = old_tiling_rect_over_tiles.y();
+ int bottom = old_tiling_rect_over_tiles.bottom();
+
+ int left_until = std::min(interest_rect_over_tiles.x(), right);
+ int right_until = std::max(interest_rect_over_tiles.right(), left);
+ int top_until = std::min(interest_rect_over_tiles.y(), bottom);
+ int bottom_until = std::max(interest_rect_over_tiles.bottom(), top);
+
+ int exposed_left = old_tiling_size.width();
+ int exposed_left_until = tiling_size().width();
+ int exposed_top = top;
+ int exposed_bottom = tiling_size().height();
+ DCHECK_GE(exposed_left, left);
+
+ gfx::Rect left_rect(left, top, left_until - left, bottom - top);
+ gfx::Rect right_rect(right_until, top, right - right_until, bottom - top);
+ gfx::Rect top_rect(left, top, right - left, top_until - top);
+ gfx::Rect bottom_rect(
+ left, bottom_until, right - left, bottom - bottom_until);
+ gfx::Rect exposed_rect(exposed_left,
+ exposed_top,
+ exposed_left_until - exposed_left,
+ exposed_bottom - exposed_top);
+ resize_invalidation.Union(left_rect);
+ resize_invalidation.Union(right_rect);
+ resize_invalidation.Union(top_rect);
+ resize_invalidation.Union(bottom_rect);
+ resize_invalidation.Union(exposed_rect);
+ }
+ if (min_toss_y < tiling_.num_tiles_y()) {
+ // The same thing occurs here as in the case above, but the invalidation
+ // rect is the bounding box around the bottom row of tiles in the old
+ // pile. This would be tiles {o,r,u,x,a,d,g,j} in the above picture.
+
+ int top = tiling_.TilePositionY(min_toss_y);
+ int bottom = top + tiling_.TileSizeY(min_toss_y);
+ int left = old_tiling_rect_over_tiles.x();
+ int right = old_tiling_rect_over_tiles.right();
+
+ int top_until = std::min(interest_rect_over_tiles.y(), bottom);
+ int bottom_until = std::max(interest_rect_over_tiles.bottom(), top);
+ int left_until = std::min(interest_rect_over_tiles.x(), right);
+ int right_until = std::max(interest_rect_over_tiles.right(), left);
+
+ int exposed_top = old_tiling_size.height();
+ int exposed_top_until = tiling_size().height();
+ int exposed_left = left;
+ int exposed_right = tiling_size().width();
+ DCHECK_GE(exposed_top, top);
+
+ gfx::Rect left_rect(left, top, left_until - left, bottom - top);
+ gfx::Rect right_rect(right_until, top, right - right_until, bottom - top);
+ gfx::Rect top_rect(left, top, right - left, top_until - top);
+ gfx::Rect bottom_rect(
+ left, bottom_until, right - left, bottom - bottom_until);
+ gfx::Rect exposed_rect(exposed_left,
+ exposed_top,
+ exposed_right - exposed_left,
+ exposed_top_until - exposed_top);
+ resize_invalidation.Union(left_rect);
+ resize_invalidation.Union(right_rect);
+ resize_invalidation.Union(top_rect);
+ resize_invalidation.Union(bottom_rect);
+ resize_invalidation.Union(exposed_rect);
+ }
+ }
+
+ Region invalidation_expanded_to_full_tiles;
+ for (Region::Iterator i(*invalidation); i.has_rect(); i.next()) {
+ gfx::Rect invalid_rect = i.rect();
+
+ // Expand invalidation that is outside tiles that intersect the interest
+ // rect. These tiles are no longer valid and should be considerered fully
+ // invalid, so we can know to not keep around raster tiles that intersect
+ // with these recording tiles.
+ gfx::Rect invalid_rect_outside_interest_rect_tiles = invalid_rect;
+ // TODO(danakj): We should have a Rect-subtract-Rect-to-2-rects operator
+ // instead of using Rect::Subtract which gives you the bounding box of the
+ // subtraction.
+ invalid_rect_outside_interest_rect_tiles.Subtract(interest_rect_over_tiles);
+ invalidation_expanded_to_full_tiles.Union(tiling_.ExpandRectToTileBounds(
+ invalid_rect_outside_interest_rect_tiles));
- bool invalidated = false;
- for (Region::Iterator i(invalidation); i.has_rect(); i.next()) {
- gfx::Rect invalidation = i.rect();
// Split this inflated invalidation across tile boundaries and apply it
// to all tiles that it touches.
- for (TilingData::Iterator iter(&tiling_, invalidation);
- iter; ++iter) {
+ bool include_borders = true;
+ for (TilingData::Iterator iter(&tiling_, invalid_rect, include_borders);
+ iter;
+ ++iter) {
const PictureMapKey& key = iter.index();
PictureMap::iterator picture_it = picture_map_.find(key);
if (picture_it == picture_map_.end())
continue;
- invalidated = picture_it->second.Invalidate() || invalidated;
+ // Inform the grid cell that it has been invalidated in this frame.
+ updated = picture_it->second.Invalidate(frame_number) || updated;
+ // Invalidate drops the picture so the whole tile better be invalidated if
+ // it won't be re-recorded below.
+ DCHECK(
+ tiling_.TileBounds(key.first, key.second).Intersects(interest_rect) ||
+ invalidation_expanded_to_full_tiles.Contains(
+ tiling_.TileBounds(key.first, key.second)));
}
}
- gfx::Rect record_rect;
- for (TilingData::Iterator it(&tiling_, interest_rect);
- it; ++it) {
+ invalidation->Union(invalidation_expanded_to_full_tiles);
+ invalidation->Union(resize_invalidation);
+
+ // Make a list of all invalid tiles; we will attempt to
+ // cluster these into multiple invalidation regions.
+ std::vector<gfx::Rect> invalid_tiles;
+ bool include_borders = true;
+ for (TilingData::Iterator it(&tiling_, interest_rect, include_borders); it;
+ ++it) {
const PictureMapKey& key = it.index();
- const PictureInfo& info = picture_map_[key];
- if (!info.picture.get()) {
- gfx::Rect tile = PaddedRect(key);
- record_rect.Union(tile);
+ PictureInfo& info = picture_map_[key];
+
+ gfx::Rect rect = PaddedRect(key);
+ int distance_to_visible =
+ rect.ManhattanInternalDistance(visible_layer_rect);
+
+ if (info.NeedsRecording(frame_number, distance_to_visible)) {
+ gfx::Rect tile = tiling_.TileBounds(key.first, key.second);
+ invalid_tiles.push_back(tile);
+ } else if (!info.GetPicture()) {
+ if (recorded_viewport_.Intersects(rect)) {
+ // Recorded viewport is just an optimization for a fully recorded
+ // interest rect. In this case, a tile in that rect has declined
+ // to be recorded (probably due to frequent invalidations).
+ // TODO(enne): Shrink the recorded_viewport_ rather than clearing.
+ recorded_viewport_ = gfx::Rect();
+ }
+
+ // If a tile in the interest rect is not recorded, the entire tile needs
+ // to be considered invalid, so that we know not to keep around raster
+ // tiles that intersect this recording tile.
+ invalidation->Union(tiling_.TileBounds(it.index_x(), it.index_y()));
}
}
- if (record_rect.IsEmpty()) {
- if (invalidated)
- UpdateRecordedRegion();
- return invalidated;
- }
+ std::vector<gfx::Rect> record_rects;
+ ClusterTiles(invalid_tiles, &record_rects);
+
+ if (record_rects.empty())
+ return updated;
- int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
- scoped_refptr<Picture> picture = Picture::Create(record_rect);
-
- {
- base::TimeDelta best_duration = base::TimeDelta::FromInternalValue(
- std::numeric_limits<int64>::max());
- for (int i = 0; i < repeat_count; i++) {
- base::TimeTicks start_time = stats_instrumentation->StartRecording();
- picture->Record(painter, tile_grid_info_);
- base::TimeDelta duration =
- stats_instrumentation->EndRecording(start_time);
- best_duration = std::min(duration, best_duration);
+ for (std::vector<gfx::Rect>::iterator it = record_rects.begin();
+ it != record_rects.end();
+ it++) {
+ gfx::Rect record_rect = *it;
+ record_rect = PadRect(record_rect);
+
+ int repeat_count = std::max(1, slow_down_raster_scale_factor_for_debug_);
+ scoped_refptr<Picture> picture;
+ int num_raster_threads = RasterWorkerPool::GetNumRasterThreads();
+
+ // Note: Currently, gathering of pixel refs when using a single
+ // raster thread doesn't provide any benefit. This might change
+ // in the future but we avoid it for now to reduce the cost of
+ // Picture::Create.
+ bool gather_pixel_refs = num_raster_threads > 1;
+
+ {
+ base::TimeDelta best_duration = base::TimeDelta::Max();
+ for (int i = 0; i < repeat_count; i++) {
+ base::TimeTicks start_time = stats_instrumentation->StartRecording();
+ picture = Picture::Create(record_rect,
+ painter,
+ tile_grid_info_,
+ gather_pixel_refs,
+ num_raster_threads,
+ recording_mode);
+ // Note the '&&' with previous is-suitable state.
+ // This means that once a picture-pile becomes unsuitable for gpu
+ // rasterization due to some content, it will continue to be unsuitable
+ // even if that content is replaced by gpu-friendly content.
+ // This is an optimization to avoid iterating though all pictures in
+ // the pile after each invalidation.
+ is_suitable_for_gpu_rasterization_ &=
+ picture->IsSuitableForGpuRasterization();
+ base::TimeDelta duration =
+ stats_instrumentation->EndRecording(start_time);
+ best_duration = std::min(duration, best_duration);
+ }
+ int recorded_pixel_count =
+ picture->LayerRect().width() * picture->LayerRect().height();
+ stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
}
- int recorded_pixel_count =
- picture->LayerRect().width() * picture->LayerRect().height();
- stats_instrumentation->AddRecord(best_duration, recorded_pixel_count);
- if (num_raster_threads_ > 1)
- picture->GatherPixelRefs(tile_grid_info_);
- picture->CloneForDrawing(num_raster_threads_);
- }
- for (TilingData::Iterator it(&tiling_, record_rect);
- it; ++it) {
- const PictureMapKey& key = it.index();
- gfx::Rect tile = PaddedRect(key);
- if (record_rect.Contains(tile)) {
- PictureInfo& info = picture_map_[key];
- info.picture = picture;
+ bool found_tile_for_recorded_picture = false;
+
+ bool include_borders = true;
+ for (TilingData::Iterator it(&tiling_, record_rect, include_borders); it;
+ ++it) {
+ const PictureMapKey& key = it.index();
+ gfx::Rect tile = PaddedRect(key);
+ if (record_rect.Contains(tile)) {
+ PictureInfo& info = picture_map_[key];
+ info.SetPicture(picture);
+ found_tile_for_recorded_picture = true;
+ }
}
+ DCHECK(found_tile_for_recorded_picture);
}
- UpdateRecordedRegion();
+ has_any_recordings_ = true;
+ DCHECK(CanRasterSlowTileCheck(recorded_viewport_));
return true;
}
+void PicturePile::SetEmptyBounds() {
+ tiling_.SetTilingSize(gfx::Size());
+ picture_map_.clear();
+ has_any_recordings_ = false;
+ recorded_viewport_ = gfx::Rect();
+}
+
} // namespace cc