// Copyright 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "cc/resources/picture_layer_tiling.h"
#include <algorithm>
#include <cmath>
#include <limits>
#include <set>
#include "base/debug/trace_event.h"
#include "base/debug/trace_event_argument.h"
#include "base/logging.h"
#include "cc/base/math_util.h"
#include "cc/resources/tile.h"
#include "cc/resources/tile_priority.h"
#include "ui/gfx/point_conversions.h"
#include "ui/gfx/rect_conversions.h"
#include "ui/gfx/safe_integer_conversions.h"
#include "ui/gfx/size_conversions.h"
namespace cc {
namespace {
const float kSoonBorderDistanceInScreenPixels = 312.f;
class TileEvictionOrder {
public:
explicit TileEvictionOrder(TreePriority tree_priority)
: tree_priority_(tree_priority) {}
~TileEvictionOrder() {}
bool operator()(const Tile* a, const Tile* b) {
const TilePriority& a_priority =
a->priority_for_tree_priority(tree_priority_);
const TilePriority& b_priority =
b->priority_for_tree_priority(tree_priority_);
DCHECK(a_priority.priority_bin == b_priority.priority_bin);
DCHECK(a->required_for_activation() == b->required_for_activation());
// Or if a is occluded and b is unoccluded.
bool a_is_occluded = a->is_occluded_for_tree_priority(tree_priority_);
bool b_is_occluded = b->is_occluded_for_tree_priority(tree_priority_);
if (a_is_occluded != b_is_occluded)
return a_is_occluded;
// Or if a is farther away from visible.
return a_priority.distance_to_visible > b_priority.distance_to_visible;
}
private:
TreePriority tree_priority_;
};
void ReleaseTile(Tile* tile, WhichTree tree) {
// Reset priority as tile is ref-counted and might still be used
// even though we no longer hold a reference to it here anymore.
tile->SetPriority(tree, TilePriority());
tile->set_shared(false);
}
} // namespace
scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
float contents_scale,
const gfx::Size& layer_bounds,
PictureLayerTilingClient* client) {
return make_scoped_ptr(new PictureLayerTiling(contents_scale,
layer_bounds,
client));
}
PictureLayerTiling::PictureLayerTiling(float contents_scale,
const gfx::Size& layer_bounds,
PictureLayerTilingClient* client)
: contents_scale_(contents_scale),
layer_bounds_(layer_bounds),
resolution_(NON_IDEAL_RESOLUTION),
client_(client),
tiling_data_(gfx::Size(), gfx::Size(), true),
last_impl_frame_time_in_seconds_(0.0),
has_visible_rect_tiles_(false),
has_skewport_rect_tiles_(false),
has_soon_border_rect_tiles_(false),
has_eventually_rect_tiles_(false),
eviction_tiles_cache_valid_(false),
eviction_cache_tree_priority_(SAME_PRIORITY_FOR_BOTH_TREES) {
gfx::Size content_bounds =
gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
if (tile_size.IsEmpty()) {
layer_bounds_ = gfx::Size();
content_bounds = gfx::Size();
}
DCHECK(!gfx::ToFlooredSize(
gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
"Tiling created with scale too small as contents become empty." <<
" Layer bounds: " << layer_bounds.ToString() <<
" Contents scale: " << contents_scale;
tiling_data_.SetTilingSize(content_bounds);
tiling_data_.SetMaxTextureSize(tile_size);
}
PictureLayerTiling::~PictureLayerTiling() {
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
ReleaseTile(it->second.get(), client_->GetTree());
}
void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
client_ = client;
}
Tile* PictureLayerTiling::CreateTile(int i,
int j,
const PictureLayerTiling* twin_tiling) {
TileMapKey key(i, j);
DCHECK(tiles_.find(key) == tiles_.end());
gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
gfx::Rect tile_rect = paint_rect;
tile_rect.set_size(tiling_data_.max_texture_size());
// Check our twin for a valid tile.
if (twin_tiling &&
tiling_data_.max_texture_size() ==
twin_tiling->tiling_data_.max_texture_size()) {
if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
gfx::Rect rect =
gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
if (!client_->GetInvalidation()->Intersects(rect)) {
DCHECK(!candidate_tile->is_shared());
candidate_tile->set_shared(true);
tiles_[key] = candidate_tile;
return candidate_tile;
}
}
}
// Create a new tile because our twin didn't have a valid one.
scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
if (tile.get()) {
DCHECK(!tile->is_shared());
tiles_[key] = tile;
}
return tile.get();
}
void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
bool include_borders = false;
for (TilingData::Iterator iter(
&tiling_data_, live_tiles_rect_, include_borders);
iter;
++iter) {
TileMapKey key = iter.index();
TileMap::iterator find = tiles_.find(key);
if (find != tiles_.end())
continue;
CreateTile(key.first, key.second, twin_tiling);
}
VerifyLiveTilesRect();
}
void PictureLayerTiling::UpdateTilesToCurrentPile(
const Region& layer_invalidation,
const gfx::Size& new_layer_bounds) {
DCHECK(!new_layer_bounds.IsEmpty());
gfx::Size tile_size = tiling_data_.max_texture_size();
if (new_layer_bounds != layer_bounds_) {
gfx::Size content_bounds =
gfx::ToCeiledSize(gfx::ScaleSize(new_layer_bounds, contents_scale_));
tile_size = client_->CalculateTileSize(content_bounds);
if (tile_size.IsEmpty()) {
layer_bounds_ = gfx::Size();
content_bounds = gfx::Size();
} else {
layer_bounds_ = new_layer_bounds;
}
// The SetLiveTilesRect() method would drop tiles outside the new bounds,
// but may do so incorrectly if resizing the tiling causes the number of
// tiles in the tiling_data_ to change.
gfx::Rect content_rect(content_bounds);
int before_left = tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.x());
int before_top = tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.y());
int before_right =
tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
int before_bottom =
tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
// The live_tiles_rect_ is clamped to stay within the tiling size as we
// change it.
live_tiles_rect_.Intersect(content_rect);
tiling_data_.SetTilingSize(content_bounds);
int after_right = -1;
int after_bottom = -1;
if (!live_tiles_rect_.IsEmpty()) {
after_right =
tiling_data_.TileXIndexFromSrcCoord(live_tiles_rect_.right() - 1);
after_bottom =
tiling_data_.TileYIndexFromSrcCoord(live_tiles_rect_.bottom() - 1);
}
// There is no recycled twin since this is run on the pending tiling.
PictureLayerTiling* recycled_twin = NULL;
DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this));
DCHECK_EQ(PENDING_TREE, client_->GetTree());
// Drop tiles outside the new layer bounds if the layer shrank.
for (int i = after_right + 1; i <= before_right; ++i) {
for (int j = before_top; j <= before_bottom; ++j)
RemoveTileAt(i, j, recycled_twin);
}
for (int i = before_left; i <= after_right; ++i) {
for (int j = after_bottom + 1; j <= before_bottom; ++j)
RemoveTileAt(i, j, recycled_twin);
}
// If the layer grew, the live_tiles_rect_ is not changed, but a new row
// and/or column of tiles may now exist inside the same live_tiles_rect_.
const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
if (after_right > before_right) {
DCHECK_EQ(after_right, before_right + 1);
for (int j = before_top; j <= after_bottom; ++j)
CreateTile(after_right, j, twin_tiling);
}
if (after_bottom > before_bottom) {
DCHECK_EQ(after_bottom, before_bottom + 1);
for (int i = before_left; i <= before_right; ++i)
CreateTile(i, after_bottom, twin_tiling);
}
}
if (tile_size != tiling_data_.max_texture_size()) {
tiling_data_.SetMaxTextureSize(tile_size);
// When the tile size changes, the TilingData positions no longer work
// as valid keys to the TileMap, so just drop all tiles.
Reset();
} else {
Invalidate(layer_invalidation);
}
PicturePileImpl* pile = client_->GetPile();
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
it->second->set_picture_pile(pile);
VerifyLiveTilesRect();
}
void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_region) {
bool recreate_invalidated_tiles = false;
DoInvalidate(layer_region, recreate_invalidated_tiles);
}
void PictureLayerTiling::Invalidate(const Region& layer_region) {
bool recreate_invalidated_tiles = true;
DoInvalidate(layer_region, recreate_invalidated_tiles);
}
void PictureLayerTiling::DoInvalidate(const Region& layer_region,
bool recreate_invalidated_tiles) {
std::vector<TileMapKey> new_tile_keys;
gfx::Rect expanded_live_tiles_rect =
tiling_data_.ExpandRectIgnoringBordersToTileBounds(live_tiles_rect_);
for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
gfx::Rect layer_rect = iter.rect();
gfx::Rect content_rect =
gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
// Consider tiles inside the live tiles rect even if only their border
// pixels intersect the invalidation. But don't consider tiles outside
// the live tiles rect with the same conditions, as they won't exist.
int border_pixels = tiling_data_.border_texels();
content_rect.Inset(-border_pixels, -border_pixels);
// Avoid needless work by not bothering to invalidate where there aren't
// tiles.
content_rect.Intersect(expanded_live_tiles_rect);
if (content_rect.IsEmpty())
continue;
// Since the content_rect includes border pixels already, don't include
// borders when iterating to avoid double counting them.
bool include_borders = false;
for (TilingData::Iterator iter(
&tiling_data_, content_rect, include_borders);
iter;
++iter) {
// There is no recycled twin since this is run on the pending tiling.
PictureLayerTiling* recycled_twin = NULL;
DCHECK_EQ(recycled_twin, client_->GetRecycledTwinTiling(this));
DCHECK_EQ(PENDING_TREE, client_->GetTree());
if (RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin))
new_tile_keys.push_back(iter.index());
}
}
if (recreate_invalidated_tiles && !new_tile_keys.empty()) {
for (size_t i = 0; i < new_tile_keys.size(); ++i) {
// Don't try to share a tile with the twin layer, it's been invalidated so
// we have to make our own tile here.
const PictureLayerTiling* twin_tiling = NULL;
CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
}
}
}
PictureLayerTiling::CoverageIterator::CoverageIterator()
: tiling_(NULL),
current_tile_(NULL),
tile_i_(0),
tile_j_(0),
left_(0),
top_(0),
right_(-1),
bottom_(-1) {
}
PictureLayerTiling::CoverageIterator::CoverageIterator(
const PictureLayerTiling* tiling,
float dest_scale,
const gfx::Rect& dest_rect)
: tiling_(tiling),
dest_rect_(dest_rect),
dest_to_content_scale_(0),
current_tile_(NULL),
tile_i_(0),
tile_j_(0),
left_(0),
top_(0),
right_(-1),
bottom_(-1) {
DCHECK(tiling_);
if (dest_rect_.IsEmpty())
return;
dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
gfx::Rect content_rect =
gfx::ScaleToEnclosingRect(dest_rect_,
dest_to_content_scale_,
dest_to_content_scale_);
// IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
// check for non-intersection first.
content_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
if (content_rect.IsEmpty())
return;
left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
content_rect.right() - 1);
bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
content_rect.bottom() - 1);
tile_i_ = left_ - 1;
tile_j_ = top_;
++(*this);
}
PictureLayerTiling::CoverageIterator::~CoverageIterator() {
}
PictureLayerTiling::CoverageIterator&
PictureLayerTiling::CoverageIterator::operator++() {
if (tile_j_ > bottom_)
return *this;
bool first_time = tile_i_ < left_;
bool new_row = false;
tile_i_++;
if (tile_i_ > right_) {
tile_i_ = left_;
tile_j_++;
new_row = true;
if (tile_j_ > bottom_) {
current_tile_ = NULL;
return *this;
}
}
current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
// Calculate the current geometry rect. Due to floating point rounding
// and ToEnclosingRect, tiles might overlap in destination space on the
// edges.
gfx::Rect last_geometry_rect = current_geometry_rect_;
gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
current_geometry_rect_ =
gfx::ScaleToEnclosingRect(content_rect,
1 / dest_to_content_scale_,
1 / dest_to_content_scale_);
current_geometry_rect_.Intersect(dest_rect_);
if (first_time)
return *this;
// Iteration happens left->right, top->bottom. Running off the bottom-right
// edge is handled by the intersection above with dest_rect_. Here we make
// sure that the new current geometry rect doesn't overlap with the last.
int min_left;
int min_top;
if (new_row) {
min_left = dest_rect_.x();
min_top = last_geometry_rect.bottom();
} else {
min_left = last_geometry_rect.right();
min_top = last_geometry_rect.y();
}
int inset_left = std::max(0, min_left - current_geometry_rect_.x());
int inset_top = std::max(0, min_top - current_geometry_rect_.y());
current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
if (!new_row) {
DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
}
return *this;
}
gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
return current_geometry_rect_;
}
gfx::Rect
PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
rect.set_size(tiling_->tiling_data_.max_texture_size());
return rect;
}
gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
gfx::PointF tex_origin =
tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
// Convert from dest space => content space => texture space.
gfx::RectF texture_rect(current_geometry_rect_);
texture_rect.Scale(dest_to_content_scale_,
dest_to_content_scale_);
texture_rect.Intersect(gfx::Rect(tiling_->tiling_size()));
if (texture_rect.IsEmpty())
return texture_rect;
texture_rect.Offset(-tex_origin.OffsetFromOrigin());
return texture_rect;
}
gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
return tiling_->tiling_data_.max_texture_size();
}
bool PictureLayerTiling::RemoveTileAt(int i,
int j,
PictureLayerTiling* recycled_twin) {
TileMap::iterator found = tiles_.find(TileMapKey(i, j));
if (found == tiles_.end())
return false;
ReleaseTile(found->second.get(), client_->GetTree());
tiles_.erase(found);
if (recycled_twin) {
// Recycled twin does not also have a recycled twin, so pass NULL.
recycled_twin->RemoveTileAt(i, j, NULL);
}
return true;
}
void PictureLayerTiling::Reset() {
live_tiles_rect_ = gfx::Rect();
PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
ReleaseTile(it->second.get(), client_->GetTree());
if (recycled_twin)
recycled_twin->RemoveTileAt(it->first.first, it->first.second, NULL);
}
tiles_.clear();
}
gfx::Rect PictureLayerTiling::ComputeSkewport(
double current_frame_time_in_seconds,
const gfx::Rect& visible_rect_in_content_space) const {
gfx::Rect skewport = visible_rect_in_content_space;
if (last_impl_frame_time_in_seconds_ == 0.0)
return skewport;
double time_delta =
current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
if (time_delta == 0.0)
return skewport;
float skewport_target_time_in_seconds =
client_->GetSkewportTargetTimeInSeconds();
double extrapolation_multiplier =
skewport_target_time_in_seconds / time_delta;
int old_x = last_visible_rect_in_content_space_.x();
int old_y = last_visible_rect_in_content_space_.y();
int old_right = last_visible_rect_in_content_space_.right();
int old_bottom = last_visible_rect_in_content_space_.bottom();
int new_x = visible_rect_in_content_space.x();
int new_y = visible_rect_in_content_space.y();
int new_right = visible_rect_in_content_space.right();
int new_bottom = visible_rect_in_content_space.bottom();
int skewport_limit = client_->GetSkewportExtrapolationLimitInContentPixels();
// Compute the maximum skewport based on |skewport_limit|.
gfx::Rect max_skewport = skewport;
max_skewport.Inset(
-skewport_limit, -skewport_limit, -skewport_limit, -skewport_limit);
// Inset the skewport by the needed adjustment.
skewport.Inset(extrapolation_multiplier * (new_x - old_x),
extrapolation_multiplier * (new_y - old_y),
extrapolation_multiplier * (old_right - new_right),
extrapolation_multiplier * (old_bottom - new_bottom));
// Clip the skewport to |max_skewport|.
skewport.Intersect(max_skewport);
// Finally, ensure that visible rect is contained in the skewport.
skewport.Union(visible_rect_in_content_space);
return skewport;
}
void PictureLayerTiling::UpdateTilePriorities(
WhichTree tree,
const gfx::Rect& viewport_in_layer_space,
float ideal_contents_scale,
double current_frame_time_in_seconds,
const Occlusion& occlusion_in_layer_space) {
if (!NeedsUpdateForFrameAtTimeAndViewport(current_frame_time_in_seconds,
viewport_in_layer_space)) {
// This should never be zero for the purposes of has_ever_been_updated().
DCHECK_NE(current_frame_time_in_seconds, 0.0);
return;
}
gfx::Rect visible_rect_in_content_space =
gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
if (tiling_size().IsEmpty()) {
last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
last_viewport_in_layer_space_ = viewport_in_layer_space;
last_visible_rect_in_content_space_ = visible_rect_in_content_space;
return;
}
size_t max_tiles_for_interest_area = client_->GetMaxTilesForInterestArea();
gfx::Size tile_size = tiling_data_.max_texture_size();
int64 eventually_rect_area =
max_tiles_for_interest_area * tile_size.width() * tile_size.height();
gfx::Rect skewport = ComputeSkewport(current_frame_time_in_seconds,
visible_rect_in_content_space);
DCHECK(skewport.Contains(visible_rect_in_content_space));
gfx::Rect eventually_rect =
ExpandRectEquallyToAreaBoundedBy(visible_rect_in_content_space,
eventually_rect_area,
gfx::Rect(tiling_size()),
&expansion_cache_);
DCHECK(eventually_rect.IsEmpty() ||
gfx::Rect(tiling_size()).Contains(eventually_rect))
<< "tiling_size: " << tiling_size().ToString()
<< " eventually_rect: " << eventually_rect.ToString();
SetLiveTilesRect(eventually_rect);
last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
last_viewport_in_layer_space_ = viewport_in_layer_space;
last_visible_rect_in_content_space_ = visible_rect_in_content_space;
eviction_tiles_cache_valid_ = false;
TilePriority now_priority(resolution_, TilePriority::NOW, 0);
float content_to_screen_scale = ideal_contents_scale / contents_scale_;
// Assign now priority to all visible tiles.
bool include_borders = false;
has_visible_rect_tiles_ = false;
for (TilingData::Iterator iter(
&tiling_data_, visible_rect_in_content_space, include_borders);
iter;
++iter) {
TileMap::iterator find = tiles_.find(iter.index());
if (find == tiles_.end())
continue;
has_visible_rect_tiles_ = true;
Tile* tile = find->second.get();
tile->SetPriority(tree, now_priority);
// Set whether tile is occluded or not.
gfx::Rect tile_query_rect = ScaleToEnclosingRect(
IntersectRects(tile->content_rect(), visible_rect_in_content_space),
1.0f / contents_scale_);
bool is_occluded = occlusion_in_layer_space.IsOccluded(tile_query_rect);
tile->set_is_occluded(tree, is_occluded);
}
// Assign soon priority to skewport tiles.
has_skewport_rect_tiles_ = false;
for (TilingData::DifferenceIterator iter(
&tiling_data_, skewport, visible_rect_in_content_space);
iter;
++iter) {
TileMap::iterator find = tiles_.find(iter.index());
if (find == tiles_.end())
continue;
has_skewport_rect_tiles_ = true;
Tile* tile = find->second.get();
gfx::Rect tile_bounds =
tiling_data_.TileBounds(iter.index_x(), iter.index_y());
float distance_to_visible =
visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
content_to_screen_scale;
TilePriority priority(resolution_, TilePriority::SOON, distance_to_visible);
tile->SetPriority(tree, priority);
}
// Assign eventually priority to interest rect tiles.
has_eventually_rect_tiles_ = false;
for (TilingData::DifferenceIterator iter(
&tiling_data_, eventually_rect, skewport);
iter;
++iter) {
TileMap::iterator find = tiles_.find(iter.index());
if (find == tiles_.end())
continue;
has_eventually_rect_tiles_ = true;
Tile* tile = find->second.get();
gfx::Rect tile_bounds =
tiling_data_.TileBounds(iter.index_x(), iter.index_y());
float distance_to_visible =
visible_rect_in_content_space.ManhattanInternalDistance(tile_bounds) *
content_to_screen_scale;
TilePriority priority(
resolution_, TilePriority::EVENTUALLY, distance_to_visible);
tile->SetPriority(tree, priority);
}
// Upgrade the priority on border tiles to be SOON.
gfx::Rect soon_border_rect = visible_rect_in_content_space;
float border = kSoonBorderDistanceInScreenPixels / content_to_screen_scale;
soon_border_rect.Inset(-border, -border, -border, -border);
has_soon_border_rect_tiles_ = false;
for (TilingData::DifferenceIterator iter(
&tiling_data_, soon_border_rect, skewport);
iter;
++iter) {
TileMap::iterator find = tiles_.find(iter.index());
if (find == tiles_.end())
continue;
has_soon_border_rect_tiles_ = true;
Tile* tile = find->second.get();
TilePriority priority(resolution_,
TilePriority::SOON,
tile->priority(tree).distance_to_visible);
tile->SetPriority(tree, priority);
}
// Update iteration rects.
current_visible_rect_ = visible_rect_in_content_space;
current_skewport_rect_ = skewport;
current_soon_border_rect_ = soon_border_rect;
current_eventually_rect_ = eventually_rect;
}
void PictureLayerTiling::SetLiveTilesRect(
const gfx::Rect& new_live_tiles_rect) {
DCHECK(new_live_tiles_rect.IsEmpty() ||
gfx::Rect(tiling_size()).Contains(new_live_tiles_rect))
<< "tiling_size: " << tiling_size().ToString()
<< " new_live_tiles_rect: " << new_live_tiles_rect.ToString();
if (live_tiles_rect_ == new_live_tiles_rect)
return;
// Iterate to delete all tiles outside of our new live_tiles rect.
PictureLayerTiling* recycled_twin = client_->GetRecycledTwinTiling(this);
for (TilingData::DifferenceIterator iter(&tiling_data_,
live_tiles_rect_,
new_live_tiles_rect);
iter;
++iter) {
RemoveTileAt(iter.index_x(), iter.index_y(), recycled_twin);
}
const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
// Iterate to allocate new tiles for all regions with newly exposed area.
for (TilingData::DifferenceIterator iter(&tiling_data_,
new_live_tiles_rect,
live_tiles_rect_);
iter;
++iter) {
TileMapKey key(iter.index());
CreateTile(key.first, key.second, twin_tiling);
}
live_tiles_rect_ = new_live_tiles_rect;
VerifyLiveTilesRect();
}
void PictureLayerTiling::VerifyLiveTilesRect() {
#if DCHECK_IS_ON
for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
if (!it->second.get())
continue;
DCHECK(it->first.first < tiling_data_.num_tiles_x())
<< this << " " << it->first.first << "," << it->first.second
<< " num_tiles_x " << tiling_data_.num_tiles_x() << " live_tiles_rect "
<< live_tiles_rect_.ToString();
DCHECK(it->first.second < tiling_data_.num_tiles_y())
<< this << " " << it->first.first << "," << it->first.second
<< " num_tiles_y " << tiling_data_.num_tiles_y() << " live_tiles_rect "
<< live_tiles_rect_.ToString();
DCHECK(tiling_data_.TileBounds(it->first.first, it->first.second)
.Intersects(live_tiles_rect_))
<< this << " " << it->first.first << "," << it->first.second
<< " tile bounds "
<< tiling_data_.TileBounds(it->first.first, it->first.second).ToString()
<< " live_tiles_rect " << live_tiles_rect_.ToString();
}
#endif
}
void PictureLayerTiling::DidBecomeRecycled() {
// DidBecomeActive below will set the active priority for tiles that are
// still in the tree. Calling this first on an active tiling that is becoming
// recycled takes care of tiles that are no longer in the active tree (eg.
// due to a pending invalidation).
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
it->second->SetPriority(ACTIVE_TREE, TilePriority());
}
}
void PictureLayerTiling::DidBecomeActive() {
PicturePileImpl* active_pile = client_->GetPile();
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
it->second->SetPriority(PENDING_TREE, TilePriority());
// Tile holds a ref onto a picture pile. If the tile never gets invalidated
// and recreated, then that picture pile ref could exist indefinitely. To
// prevent this, ask the client to update the pile to its own ref. This
// will cause PicturePileImpls to get deleted once the corresponding
// PictureLayerImpl and any in flight raster jobs go out of scope.
it->second->set_picture_pile(active_pile);
}
}
void PictureLayerTiling::GetAllTilesForTracing(
std::set<const Tile*>* tiles) const {
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it)
tiles->insert(it->second.get());
}
void PictureLayerTiling::AsValueInto(base::debug::TracedValue* state) const {
state->SetInteger("num_tiles", tiles_.size());
state->SetDouble("content_scale", contents_scale_);
state->BeginDictionary("tiling_size");
MathUtil::AddToTracedValue(tiling_size(), state);
state->EndDictionary();
}
size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
size_t amount = 0;
for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
const Tile* tile = it->second.get();
amount += tile->GPUMemoryUsageInBytes();
}
return amount;
}
PictureLayerTiling::RectExpansionCache::RectExpansionCache()
: previous_target(0) {
}
namespace {
// This struct represents an event at which the expending rect intersects
// one of its boundaries. 4 intersection events will occur during expansion.
struct EdgeEvent {
enum { BOTTOM, TOP, LEFT, RIGHT } edge;
int* num_edges;
int distance;
};
// Compute the delta to expand from edges to cover target_area.
int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
int width, int height,
int64 target_area) {
// Compute coefficients for the quadratic equation:
// a*x^2 + b*x + c = 0
int a = num_y_edges * num_x_edges;
int b = num_y_edges * width + num_x_edges * height;
int64 c = static_cast<int64>(width) * height - target_area;
// Compute the delta for our edges using the quadratic equation.
int delta =
(a == 0) ? -c / b : (-b + static_cast<int>(std::sqrt(
static_cast<int64>(b) * b - 4.0 * a * c))) /
(2 * a);
return std::max(0, delta);
}
} // namespace
gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
const gfx::Rect& starting_rect,
int64 target_area,
const gfx::Rect& bounding_rect,
RectExpansionCache* cache) {
if (starting_rect.IsEmpty())
return starting_rect;
if (cache &&
cache->previous_start == starting_rect &&
cache->previous_bounds == bounding_rect &&
cache->previous_target == target_area)
return cache->previous_result;
if (cache) {
cache->previous_start = starting_rect;
cache->previous_bounds = bounding_rect;
cache->previous_target = target_area;
}
DCHECK(!bounding_rect.IsEmpty());
DCHECK_GT(target_area, 0);
// Expand the starting rect to cover target_area, if it is smaller than it.
int delta = ComputeExpansionDelta(
2, 2, starting_rect.width(), starting_rect.height(), target_area);
gfx::Rect expanded_starting_rect = starting_rect;
if (delta > 0)
expanded_starting_rect.Inset(-delta, -delta);
gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
if (rect.IsEmpty()) {
// The starting_rect and bounding_rect are far away.
if (cache)
cache->previous_result = rect;
return rect;
}
if (delta >= 0 && rect == expanded_starting_rect) {
// The starting rect already covers the entire bounding_rect and isn't too
// large for the target_area.
if (cache)
cache->previous_result = rect;
return rect;
}
// Continue to expand/shrink rect to let it cover target_area.
// These values will be updated by the loop and uses as the output.
int origin_x = rect.x();
int origin_y = rect.y();
int width = rect.width();
int height = rect.height();
// In the beginning we will consider 2 edges in each dimension.
int num_y_edges = 2;
int num_x_edges = 2;
// Create an event list.
EdgeEvent events[] = {
{ EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
{ EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
{ EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
{ EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
};
// Sort the events by distance (closest first).
if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
for (int event_index = 0; event_index < 4; event_index++) {
const EdgeEvent& event = events[event_index];
int delta = ComputeExpansionDelta(
num_x_edges, num_y_edges, width, height, target_area);
// Clamp delta to our event distance.
if (delta > event.distance)
delta = event.distance;
// Adjust the edge count for this kind of edge.
--*event.num_edges;
// Apply the delta to the edges and edge events.
for (int i = event_index; i < 4; i++) {
switch (events[i].edge) {
case EdgeEvent::BOTTOM:
origin_y -= delta;
height += delta;
break;
case EdgeEvent::TOP:
height += delta;
break;
case EdgeEvent::LEFT:
origin_x -= delta;
width += delta;
break;
case EdgeEvent::RIGHT:
width += delta;
break;
}
events[i].distance -= delta;
}
// If our delta is less then our event distance, we're done.
if (delta < event.distance)
break;
}
gfx::Rect result(origin_x, origin_y, width, height);
if (cache)
cache->previous_result = result;
return result;
}
void PictureLayerTiling::UpdateEvictionCacheIfNeeded(
TreePriority tree_priority) {
if (eviction_tiles_cache_valid_ &&
eviction_cache_tree_priority_ == tree_priority)
return;
eviction_tiles_now_.clear();
eviction_tiles_now_and_required_for_activation_.clear();
eviction_tiles_soon_.clear();
eviction_tiles_soon_and_required_for_activation_.clear();
eviction_tiles_eventually_.clear();
eviction_tiles_eventually_and_required_for_activation_.clear();
for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
// TODO(vmpstr): This should update the priority if UpdateTilePriorities
// changes not to do this.
Tile* tile = it->second.get();
const TilePriority& priority =
tile->priority_for_tree_priority(tree_priority);
switch (priority.priority_bin) {
case TilePriority::EVENTUALLY:
if (tile->required_for_activation())
eviction_tiles_eventually_and_required_for_activation_.push_back(
tile);
else
eviction_tiles_eventually_.push_back(tile);
break;
case TilePriority::SOON:
if (tile->required_for_activation())
eviction_tiles_soon_and_required_for_activation_.push_back(tile);
else
eviction_tiles_soon_.push_back(tile);
break;
case TilePriority::NOW:
if (tile->required_for_activation())
eviction_tiles_now_and_required_for_activation_.push_back(tile);
else
eviction_tiles_now_.push_back(tile);
break;
}
}
// TODO(vmpstr): Do this lazily. One option is to have a "sorted" flag that
// can be updated for each of the queues.
TileEvictionOrder sort_order(tree_priority);
std::sort(eviction_tiles_now_.begin(), eviction_tiles_now_.end(), sort_order);
std::sort(eviction_tiles_now_and_required_for_activation_.begin(),
eviction_tiles_now_and_required_for_activation_.end(),
sort_order);
std::sort(
eviction_tiles_soon_.begin(), eviction_tiles_soon_.end(), sort_order);
std::sort(eviction_tiles_soon_and_required_for_activation_.begin(),
eviction_tiles_soon_and_required_for_activation_.end(),
sort_order);
std::sort(eviction_tiles_eventually_.begin(),
eviction_tiles_eventually_.end(),
sort_order);
std::sort(eviction_tiles_eventually_and_required_for_activation_.begin(),
eviction_tiles_eventually_and_required_for_activation_.end(),
sort_order);
eviction_tiles_cache_valid_ = true;
eviction_cache_tree_priority_ = tree_priority;
}
const std::vector<Tile*>* PictureLayerTiling::GetEvictionTiles(
TreePriority tree_priority,
EvictionCategory category) {
UpdateEvictionCacheIfNeeded(tree_priority);
switch (category) {
case EVENTUALLY:
return &eviction_tiles_eventually_;
case EVENTUALLY_AND_REQUIRED_FOR_ACTIVATION:
return &eviction_tiles_eventually_and_required_for_activation_;
case SOON:
return &eviction_tiles_soon_;
case SOON_AND_REQUIRED_FOR_ACTIVATION:
return &eviction_tiles_soon_and_required_for_activation_;
case NOW:
return &eviction_tiles_now_;
case NOW_AND_REQUIRED_FOR_ACTIVATION:
return &eviction_tiles_now_and_required_for_activation_;
}
NOTREACHED();
return &eviction_tiles_eventually_;
}
PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator()
: tiling_(NULL), current_tile_(NULL) {}
PictureLayerTiling::TilingRasterTileIterator::TilingRasterTileIterator(
PictureLayerTiling* tiling,
WhichTree tree)
: tiling_(tiling), phase_(VISIBLE_RECT), tree_(tree), current_tile_(NULL) {
if (!tiling_->has_visible_rect_tiles_) {
AdvancePhase();
return;
}
visible_iterator_ = TilingData::Iterator(&tiling_->tiling_data_,
tiling_->current_visible_rect_,
false /* include_borders */);
if (!visible_iterator_) {
AdvancePhase();
return;
}
current_tile_ =
tiling_->TileAt(visible_iterator_.index_x(), visible_iterator_.index_y());
if (!current_tile_ || !TileNeedsRaster(current_tile_))
++(*this);
}
PictureLayerTiling::TilingRasterTileIterator::~TilingRasterTileIterator() {}
void PictureLayerTiling::TilingRasterTileIterator::AdvancePhase() {
DCHECK_LT(phase_, EVENTUALLY_RECT);
do {
phase_ = static_cast<Phase>(phase_ + 1);
switch (phase_) {
case VISIBLE_RECT:
NOTREACHED();
return;
case SKEWPORT_RECT:
if (!tiling_->has_skewport_rect_tiles_)
continue;
spiral_iterator_ = TilingData::SpiralDifferenceIterator(
&tiling_->tiling_data_,
tiling_->current_skewport_rect_,
tiling_->current_visible_rect_,
tiling_->current_visible_rect_);
break;
case SOON_BORDER_RECT:
if (!tiling_->has_soon_border_rect_tiles_)
continue;
spiral_iterator_ = TilingData::SpiralDifferenceIterator(
&tiling_->tiling_data_,
tiling_->current_soon_border_rect_,
tiling_->current_skewport_rect_,
tiling_->current_visible_rect_);
break;
case EVENTUALLY_RECT:
if (!tiling_->has_eventually_rect_tiles_) {
current_tile_ = NULL;
return;
}
spiral_iterator_ = TilingData::SpiralDifferenceIterator(
&tiling_->tiling_data_,
tiling_->current_eventually_rect_,
tiling_->current_skewport_rect_,
tiling_->current_soon_border_rect_);
break;
}
while (spiral_iterator_) {
current_tile_ = tiling_->TileAt(spiral_iterator_.index_x(),
spiral_iterator_.index_y());
if (current_tile_ && TileNeedsRaster(current_tile_))
break;
++spiral_iterator_;
}
if (!spiral_iterator_ && phase_ == EVENTUALLY_RECT) {
current_tile_ = NULL;
break;
}
} while (!spiral_iterator_);
}
PictureLayerTiling::TilingRasterTileIterator&
PictureLayerTiling::TilingRasterTileIterator::
operator++() {
current_tile_ = NULL;
while (!current_tile_ || !TileNeedsRaster(current_tile_)) {
std::pair<int, int> next_index;
switch (phase_) {
case VISIBLE_RECT:
++visible_iterator_;
if (!visible_iterator_) {
AdvancePhase();
return *this;
}
next_index = visible_iterator_.index();
break;
case SKEWPORT_RECT:
case SOON_BORDER_RECT:
++spiral_iterator_;
if (!spiral_iterator_) {
AdvancePhase();
return *this;
}
next_index = spiral_iterator_.index();
break;
case EVENTUALLY_RECT:
++spiral_iterator_;
if (!spiral_iterator_) {
current_tile_ = NULL;
return *this;
}
next_index = spiral_iterator_.index();
break;
}
current_tile_ = tiling_->TileAt(next_index.first, next_index.second);
}
return *this;
}
PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator()
: eviction_tiles_(NULL), current_eviction_tiles_index_(0u) {
}
PictureLayerTiling::TilingEvictionTileIterator::TilingEvictionTileIterator(
PictureLayerTiling* tiling,
TreePriority tree_priority,
EvictionCategory category)
: eviction_tiles_(tiling->GetEvictionTiles(tree_priority, category)),
// Note: initializing to "0 - 1" works as overflow is well defined for
// unsigned integers.
current_eviction_tiles_index_(static_cast<size_t>(0) - 1) {
DCHECK(eviction_tiles_);
++(*this);
}
PictureLayerTiling::TilingEvictionTileIterator::~TilingEvictionTileIterator() {
}
PictureLayerTiling::TilingEvictionTileIterator::operator bool() const {
return eviction_tiles_ &&
current_eviction_tiles_index_ != eviction_tiles_->size();
}
Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() {
DCHECK(*this);
return (*eviction_tiles_)[current_eviction_tiles_index_];
}
const Tile* PictureLayerTiling::TilingEvictionTileIterator::operator*() const {
DCHECK(*this);
return (*eviction_tiles_)[current_eviction_tiles_index_];
}
PictureLayerTiling::TilingEvictionTileIterator&
PictureLayerTiling::TilingEvictionTileIterator::
operator++() {
DCHECK(*this);
do {
++current_eviction_tiles_index_;
} while (current_eviction_tiles_index_ != eviction_tiles_->size() &&
!(*eviction_tiles_)[current_eviction_tiles_index_]->HasResources());
return *this;
}
} // namespace cc