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_layer_tiling.h"
6
7#include <algorithm>
8#include <cmath>
9#include <limits>
10
11#include "base/debug/trace_event.h"
12#include "cc/base/math_util.h"
13#include "ui/gfx/point_conversions.h"
14#include "ui/gfx/rect_conversions.h"
15#include "ui/gfx/safe_integer_conversions.h"
16#include "ui/gfx/size_conversions.h"
17
18namespace cc {
19
20scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
21    float contents_scale,
22    gfx::Size layer_bounds,
23    PictureLayerTilingClient* client) {
24  return make_scoped_ptr(new PictureLayerTiling(contents_scale,
25                                                layer_bounds,
26                                                client));
27}
28
29PictureLayerTiling::PictureLayerTiling(float contents_scale,
30                                       gfx::Size layer_bounds,
31                                       PictureLayerTilingClient* client)
32    : contents_scale_(contents_scale),
33      layer_bounds_(layer_bounds),
34      resolution_(NON_IDEAL_RESOLUTION),
35      client_(client),
36      tiling_data_(gfx::Size(), gfx::Size(), true),
37      last_impl_frame_time_in_seconds_(0.0) {
38  gfx::Size content_bounds =
39      gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds, contents_scale));
40  gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
41
42  DCHECK(!gfx::ToFlooredSize(
43      gfx::ScaleSize(layer_bounds, contents_scale)).IsEmpty()) <<
44      "Tiling created with scale too small as contents become empty." <<
45      " Layer bounds: " << layer_bounds.ToString() <<
46      " Contents scale: " << contents_scale;
47
48  tiling_data_.SetTotalSize(content_bounds);
49  tiling_data_.SetMaxTextureSize(tile_size);
50}
51
52PictureLayerTiling::~PictureLayerTiling() {
53}
54
55void PictureLayerTiling::SetClient(PictureLayerTilingClient* client) {
56  client_ = client;
57}
58
59gfx::Rect PictureLayerTiling::ContentRect() const {
60  return gfx::Rect(tiling_data_.total_size());
61}
62
63gfx::SizeF PictureLayerTiling::ContentSizeF() const {
64  return gfx::ScaleSize(layer_bounds_, contents_scale_);
65}
66
67Tile* PictureLayerTiling::TileAt(int i, int j) const {
68  TileMap::const_iterator iter = tiles_.find(TileMapKey(i, j));
69  if (iter == tiles_.end())
70    return NULL;
71  return iter->second.get();
72}
73
74void PictureLayerTiling::CreateTile(int i,
75                                    int j,
76                                    const PictureLayerTiling* twin_tiling) {
77  TileMapKey key(i, j);
78  DCHECK(tiles_.find(key) == tiles_.end());
79
80  gfx::Rect paint_rect = tiling_data_.TileBoundsWithBorder(i, j);
81  gfx::Rect tile_rect = paint_rect;
82  tile_rect.set_size(tiling_data_.max_texture_size());
83
84  // Check our twin for a valid tile.
85  if (twin_tiling &&
86      tiling_data_.max_texture_size() ==
87      twin_tiling->tiling_data_.max_texture_size()) {
88    if (Tile* candidate_tile = twin_tiling->TileAt(i, j)) {
89      gfx::Rect rect =
90          gfx::ScaleToEnclosingRect(paint_rect, 1.0f / contents_scale_);
91      if (!client_->GetInvalidation()->Intersects(rect)) {
92        tiles_[key] = candidate_tile;
93        return;
94      }
95    }
96  }
97
98  // Create a new tile because our twin didn't have a valid one.
99  scoped_refptr<Tile> tile = client_->CreateTile(this, tile_rect);
100  if (tile.get())
101    tiles_[key] = tile;
102}
103
104Region PictureLayerTiling::OpaqueRegionInContentRect(
105    gfx::Rect content_rect) const {
106  Region opaque_region;
107  // TODO(enne): implement me
108  return opaque_region;
109}
110
111void PictureLayerTiling::SetCanUseLCDText(bool can_use_lcd_text) {
112  for (TileMap::iterator it = tiles_.begin(); it != tiles_.end(); ++it)
113    it->second->set_can_use_lcd_text(can_use_lcd_text);
114}
115
116void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
117  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
118  for (TilingData::Iterator iter(&tiling_data_, live_tiles_rect_); iter;
119       ++iter) {
120    TileMapKey key = iter.index();
121    TileMap::iterator find = tiles_.find(key);
122    if (find != tiles_.end())
123      continue;
124    CreateTile(key.first, key.second, twin_tiling);
125  }
126}
127
128void PictureLayerTiling::SetLayerBounds(gfx::Size layer_bounds) {
129  if (layer_bounds_ == layer_bounds)
130    return;
131
132  DCHECK(!layer_bounds.IsEmpty());
133
134  gfx::Size old_layer_bounds = layer_bounds_;
135  layer_bounds_ = layer_bounds;
136  gfx::Size old_content_bounds = tiling_data_.total_size();
137  gfx::Size content_bounds =
138      gfx::ToCeiledSize(gfx::ScaleSize(layer_bounds_, contents_scale_));
139
140  gfx::Size tile_size = client_->CalculateTileSize(content_bounds);
141  if (tile_size != tiling_data_.max_texture_size()) {
142    tiling_data_.SetTotalSize(content_bounds);
143    tiling_data_.SetMaxTextureSize(tile_size);
144    Reset();
145    return;
146  }
147
148  // Any tiles outside our new bounds are invalid and should be dropped.
149  gfx::Rect bounded_live_tiles_rect(live_tiles_rect_);
150  bounded_live_tiles_rect.Intersect(gfx::Rect(content_bounds));
151  SetLiveTilesRect(bounded_live_tiles_rect);
152  tiling_data_.SetTotalSize(content_bounds);
153
154  // Create tiles for newly exposed areas.
155  Region layer_region((gfx::Rect(layer_bounds_)));
156  layer_region.Subtract(gfx::Rect(old_layer_bounds));
157  Invalidate(layer_region);
158}
159
160void PictureLayerTiling::Invalidate(const Region& layer_region) {
161  std::vector<TileMapKey> new_tile_keys;
162  for (Region::Iterator iter(layer_region); iter.has_rect(); iter.next()) {
163    gfx::Rect layer_rect = iter.rect();
164    gfx::Rect content_rect =
165        gfx::ScaleToEnclosingRect(layer_rect, contents_scale_);
166    content_rect.Intersect(live_tiles_rect_);
167    if (content_rect.IsEmpty())
168      continue;
169    for (TilingData::Iterator iter(&tiling_data_, content_rect); iter; ++iter) {
170      TileMapKey key(iter.index());
171      TileMap::iterator find = tiles_.find(key);
172      if (find == tiles_.end())
173        continue;
174      tiles_.erase(find);
175      new_tile_keys.push_back(key);
176    }
177  }
178
179  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
180  for (size_t i = 0; i < new_tile_keys.size(); ++i)
181    CreateTile(new_tile_keys[i].first, new_tile_keys[i].second, twin_tiling);
182}
183
184PictureLayerTiling::CoverageIterator::CoverageIterator()
185    : tiling_(NULL),
186      current_tile_(NULL),
187      tile_i_(0),
188      tile_j_(0),
189      left_(0),
190      top_(0),
191      right_(-1),
192      bottom_(-1) {
193}
194
195PictureLayerTiling::CoverageIterator::CoverageIterator(
196    const PictureLayerTiling* tiling,
197    float dest_scale,
198    gfx::Rect dest_rect)
199    : tiling_(tiling),
200      dest_rect_(dest_rect),
201      dest_to_content_scale_(0),
202      current_tile_(NULL),
203      tile_i_(0),
204      tile_j_(0),
205      left_(0),
206      top_(0),
207      right_(-1),
208      bottom_(-1) {
209  DCHECK(tiling_);
210  if (dest_rect_.IsEmpty())
211    return;
212
213  dest_to_content_scale_ = tiling_->contents_scale_ / dest_scale;
214  // This is the maximum size that the dest rect can be, given the content size.
215  gfx::Size dest_content_size = gfx::ToCeiledSize(gfx::ScaleSize(
216      tiling_->ContentRect().size(),
217      1 / dest_to_content_scale_,
218      1 / dest_to_content_scale_));
219
220  gfx::Rect content_rect =
221      gfx::ScaleToEnclosingRect(dest_rect_,
222                                dest_to_content_scale_,
223                                dest_to_content_scale_);
224  // IndexFromSrcCoord clamps to valid tile ranges, so it's necessary to
225  // check for non-intersection first.
226  content_rect.Intersect(gfx::Rect(tiling_->tiling_data_.total_size()));
227  if (content_rect.IsEmpty())
228    return;
229
230  left_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(content_rect.x());
231  top_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(content_rect.y());
232  right_ = tiling_->tiling_data_.TileXIndexFromSrcCoord(
233      content_rect.right() - 1);
234  bottom_ = tiling_->tiling_data_.TileYIndexFromSrcCoord(
235      content_rect.bottom() - 1);
236
237  tile_i_ = left_ - 1;
238  tile_j_ = top_;
239  ++(*this);
240}
241
242PictureLayerTiling::CoverageIterator::~CoverageIterator() {
243}
244
245PictureLayerTiling::CoverageIterator&
246PictureLayerTiling::CoverageIterator::operator++() {
247  if (tile_j_ > bottom_)
248    return *this;
249
250  bool first_time = tile_i_ < left_;
251  bool new_row = false;
252  tile_i_++;
253  if (tile_i_ > right_) {
254    tile_i_ = left_;
255    tile_j_++;
256    new_row = true;
257    if (tile_j_ > bottom_) {
258      current_tile_ = NULL;
259      return *this;
260    }
261  }
262
263  current_tile_ = tiling_->TileAt(tile_i_, tile_j_);
264
265  // Calculate the current geometry rect.  Due to floating point rounding
266  // and ToEnclosingRect, tiles might overlap in destination space on the
267  // edges.
268  gfx::Rect last_geometry_rect = current_geometry_rect_;
269
270  gfx::Rect content_rect = tiling_->tiling_data_.TileBounds(tile_i_, tile_j_);
271
272  current_geometry_rect_ =
273      gfx::ScaleToEnclosingRect(content_rect,
274                                1 / dest_to_content_scale_,
275                                1 / dest_to_content_scale_);
276
277  current_geometry_rect_.Intersect(dest_rect_);
278
279  if (first_time)
280    return *this;
281
282  // Iteration happens left->right, top->bottom.  Running off the bottom-right
283  // edge is handled by the intersection above with dest_rect_.  Here we make
284  // sure that the new current geometry rect doesn't overlap with the last.
285  int min_left;
286  int min_top;
287  if (new_row) {
288    min_left = dest_rect_.x();
289    min_top = last_geometry_rect.bottom();
290  } else {
291    min_left = last_geometry_rect.right();
292    min_top = last_geometry_rect.y();
293  }
294
295  int inset_left = std::max(0, min_left - current_geometry_rect_.x());
296  int inset_top = std::max(0, min_top - current_geometry_rect_.y());
297  current_geometry_rect_.Inset(inset_left, inset_top, 0, 0);
298
299  if (!new_row) {
300    DCHECK_EQ(last_geometry_rect.right(), current_geometry_rect_.x());
301    DCHECK_EQ(last_geometry_rect.bottom(), current_geometry_rect_.bottom());
302    DCHECK_EQ(last_geometry_rect.y(), current_geometry_rect_.y());
303  }
304
305  return *this;
306}
307
308gfx::Rect PictureLayerTiling::CoverageIterator::geometry_rect() const {
309  return current_geometry_rect_;
310}
311
312gfx::Rect
313PictureLayerTiling::CoverageIterator::full_tile_geometry_rect() const {
314  gfx::Rect rect = tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_);
315  rect.set_size(tiling_->tiling_data_.max_texture_size());
316  return rect;
317}
318
319gfx::RectF PictureLayerTiling::CoverageIterator::texture_rect() const {
320  gfx::PointF tex_origin =
321      tiling_->tiling_data_.TileBoundsWithBorder(tile_i_, tile_j_).origin();
322
323  // Convert from dest space => content space => texture space.
324  gfx::RectF texture_rect(current_geometry_rect_);
325  texture_rect.Scale(dest_to_content_scale_,
326                     dest_to_content_scale_);
327  texture_rect.Offset(-tex_origin.OffsetFromOrigin());
328  texture_rect.Intersect(tiling_->ContentRect());
329
330  return texture_rect;
331}
332
333gfx::Size PictureLayerTiling::CoverageIterator::texture_size() const {
334  return tiling_->tiling_data_.max_texture_size();
335}
336
337void PictureLayerTiling::Reset() {
338  live_tiles_rect_ = gfx::Rect();
339  tiles_.clear();
340}
341
342namespace {
343
344bool NearlyOne(SkMScalar lhs) {
345  return std::abs(lhs-1.0) < std::numeric_limits<float>::epsilon();
346}
347
348bool NearlyZero(SkMScalar lhs) {
349  return std::abs(lhs) < std::numeric_limits<float>::epsilon();
350}
351
352bool ApproximatelyTranslation(const SkMatrix44& matrix) {
353  return
354      NearlyOne(matrix.get(0, 0)) &&
355      NearlyZero(matrix.get(1, 0)) &&
356      NearlyZero(matrix.get(2, 0)) &&
357      matrix.get(3, 0) == 0 &&
358      NearlyZero(matrix.get(0, 1)) &&
359      NearlyOne(matrix.get(1, 1)) &&
360      NearlyZero(matrix.get(2, 1)) &&
361      matrix.get(3, 1) == 0 &&
362      NearlyZero(matrix.get(0, 2)) &&
363      NearlyZero(matrix.get(1, 2)) &&
364      NearlyOne(matrix.get(2, 2)) &&
365      matrix.get(3, 2) == 0 &&
366      matrix.get(3, 3) == 1;
367}
368
369}  // namespace
370
371void PictureLayerTiling::UpdateTilePriorities(
372    WhichTree tree,
373    gfx::Size device_viewport,
374    gfx::Rect viewport_in_layer_space,
375    gfx::Rect visible_layer_rect,
376    gfx::Size last_layer_bounds,
377    gfx::Size current_layer_bounds,
378    float last_layer_contents_scale,
379    float current_layer_contents_scale,
380    const gfx::Transform& last_screen_transform,
381    const gfx::Transform& current_screen_transform,
382    double current_frame_time_in_seconds,
383    size_t max_tiles_for_interest_area) {
384  if (!NeedsUpdateForFrameAtTime(current_frame_time_in_seconds)) {
385    // This should never be zero for the purposes of has_ever_been_updated().
386    DCHECK_NE(current_frame_time_in_seconds, 0.0);
387    return;
388  }
389  if (ContentRect().IsEmpty()) {
390    last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
391    return;
392  }
393
394  gfx::Rect viewport_in_content_space =
395      gfx::ScaleToEnclosingRect(viewport_in_layer_space, contents_scale_);
396  gfx::Rect visible_content_rect =
397      gfx::ScaleToEnclosingRect(visible_layer_rect, contents_scale_);
398
399  gfx::Size tile_size = tiling_data_.max_texture_size();
400  int64 interest_rect_area =
401      max_tiles_for_interest_area * tile_size.width() * tile_size.height();
402
403  gfx::Rect starting_rect = visible_content_rect.IsEmpty()
404                            ? viewport_in_content_space
405                            : visible_content_rect;
406  gfx::Rect interest_rect = ExpandRectEquallyToAreaBoundedBy(
407      starting_rect,
408      interest_rect_area,
409      ContentRect());
410  DCHECK(interest_rect.IsEmpty() ||
411         ContentRect().Contains(interest_rect));
412
413  SetLiveTilesRect(interest_rect);
414
415  double time_delta = 0;
416  if (last_impl_frame_time_in_seconds_ != 0.0 &&
417      last_layer_bounds == current_layer_bounds) {
418    time_delta =
419        current_frame_time_in_seconds - last_impl_frame_time_in_seconds_;
420  }
421
422  gfx::Rect view_rect(device_viewport);
423  float current_scale = current_layer_contents_scale / contents_scale_;
424  float last_scale = last_layer_contents_scale / contents_scale_;
425
426  bool store_screen_space_quads_on_tiles;
427  TRACE_EVENT_CATEGORY_GROUP_ENABLED(TRACE_DISABLED_BY_DEFAULT("cc.debug"),
428                                     &store_screen_space_quads_on_tiles);
429
430  // Fast path tile priority calculation when both transforms are translations.
431  if (ApproximatelyTranslation(last_screen_transform.matrix()) &&
432      ApproximatelyTranslation(current_screen_transform.matrix())) {
433    gfx::Vector2dF current_offset(
434        current_screen_transform.matrix().get(0, 3),
435        current_screen_transform.matrix().get(1, 3));
436    gfx::Vector2dF last_offset(
437        last_screen_transform.matrix().get(0, 3),
438        last_screen_transform.matrix().get(1, 3));
439
440    for (TilingData::Iterator iter(&tiling_data_, interest_rect);
441         iter; ++iter) {
442      TileMap::iterator find = tiles_.find(iter.index());
443      if (find == tiles_.end())
444        continue;
445      Tile* tile = find->second.get();
446
447      gfx::Rect tile_bounds =
448          tiling_data_.TileBounds(iter.index_x(), iter.index_y());
449      gfx::RectF current_screen_rect = gfx::ScaleRect(
450          tile_bounds,
451          current_scale,
452          current_scale) + current_offset;
453      gfx::RectF last_screen_rect = gfx::ScaleRect(
454          tile_bounds,
455          last_scale,
456          last_scale) + last_offset;
457
458      float distance_to_visible_in_pixels =
459          TilePriority::manhattanDistance(current_screen_rect, view_rect);
460
461      float time_to_visible_in_seconds =
462          TilePriority::TimeForBoundsToIntersect(
463              last_screen_rect, current_screen_rect, time_delta, view_rect);
464      TilePriority priority(
465          resolution_,
466          time_to_visible_in_seconds,
467          distance_to_visible_in_pixels);
468      if (store_screen_space_quads_on_tiles)
469        priority.set_current_screen_quad(gfx::QuadF(current_screen_rect));
470      tile->SetPriority(tree, priority);
471    }
472  } else if (!last_screen_transform.HasPerspective() &&
473             !current_screen_transform.HasPerspective()) {
474    // Secondary fast path that can be applied for any affine transforms.
475
476    // Initialize the necessary geometry in screen space, so that we can
477    // iterate over tiles in screen space without needing a costly transform
478    // mapping for each tile.
479
480    // Apply screen space transform to the local origin point (0, 0); only the
481    // translation component is needed and can be initialized directly.
482    gfx::Point current_screen_space_origin(
483        current_screen_transform.matrix().get(0, 3),
484        current_screen_transform.matrix().get(1, 3));
485
486    gfx::Point last_screen_space_origin(
487        last_screen_transform.matrix().get(0, 3),
488        last_screen_transform.matrix().get(1, 3));
489
490    float current_tile_width = tiling_data_.TileSizeX(0) * current_scale;
491    float last_tile_width = tiling_data_.TileSizeX(0) * last_scale;
492    float current_tile_height = tiling_data_.TileSizeY(0) * current_scale;
493    float last_tile_height = tiling_data_.TileSizeY(0) * last_scale;
494
495    // Apply screen space transform to local basis vectors (tile_width, 0) and
496    // (0, tile_height); the math simplifies and can be initialized directly.
497    gfx::Vector2dF current_horizontal(
498        current_screen_transform.matrix().get(0, 0) * current_tile_width,
499        current_screen_transform.matrix().get(1, 0) * current_tile_width);
500    gfx::Vector2dF current_vertical(
501        current_screen_transform.matrix().get(0, 1) * current_tile_height,
502        current_screen_transform.matrix().get(1, 1) * current_tile_height);
503
504    gfx::Vector2dF last_horizontal(
505        last_screen_transform.matrix().get(0, 0) * last_tile_width,
506        last_screen_transform.matrix().get(1, 0) * last_tile_width);
507    gfx::Vector2dF last_vertical(
508        last_screen_transform.matrix().get(0, 1) * last_tile_height,
509        last_screen_transform.matrix().get(1, 1) * last_tile_height);
510
511    for (TilingData::Iterator iter(&tiling_data_, interest_rect);
512         iter; ++iter) {
513      TileMap::iterator find = tiles_.find(iter.index());
514      if (find == tiles_.end())
515        continue;
516
517      Tile* tile = find->second.get();
518
519      int i = iter.index_x();
520      int j = iter.index_y();
521      gfx::PointF current_tile_origin = current_screen_space_origin +
522              ScaleVector2d(current_horizontal, i) +
523              ScaleVector2d(current_vertical, j);
524      gfx::PointF last_tile_origin = last_screen_space_origin +
525              ScaleVector2d(last_horizontal, i) +
526              ScaleVector2d(last_vertical, j);
527
528      gfx::RectF current_screen_rect = gfx::QuadF(
529          current_tile_origin,
530          current_tile_origin + current_horizontal,
531          current_tile_origin + current_horizontal + current_vertical,
532          current_tile_origin + current_vertical).BoundingBox();
533
534      gfx::RectF last_screen_rect = gfx::QuadF(
535          last_tile_origin,
536          last_tile_origin + last_horizontal,
537          last_tile_origin + last_horizontal + last_vertical,
538          last_tile_origin + last_vertical).BoundingBox();
539
540      float distance_to_visible_in_pixels =
541          TilePriority::manhattanDistance(current_screen_rect, view_rect);
542
543      float time_to_visible_in_seconds =
544          TilePriority::TimeForBoundsToIntersect(
545              last_screen_rect, current_screen_rect, time_delta, view_rect);
546      TilePriority priority(
547          resolution_,
548          time_to_visible_in_seconds,
549          distance_to_visible_in_pixels);
550
551      if (store_screen_space_quads_on_tiles) {
552        // This overhead is only triggered when logging event tracing data.
553        gfx::Rect tile_bounds =
554            tiling_data_.TileBounds(iter.index_x(), iter.index_y());
555        gfx::RectF current_layer_content_rect = gfx::ScaleRect(
556            tile_bounds,
557            current_scale,
558            current_scale);
559        bool clipped;
560        priority.set_current_screen_quad(
561            MathUtil::MapQuad(current_screen_transform,
562                              gfx::QuadF(current_layer_content_rect),
563                              &clipped));
564      }
565      tile->SetPriority(tree, priority);
566    }
567  } else {
568    for (TilingData::Iterator iter(&tiling_data_, interest_rect);
569         iter; ++iter) {
570      TileMap::iterator find = tiles_.find(iter.index());
571      if (find == tiles_.end())
572        continue;
573      Tile* tile = find->second.get();
574
575      gfx::Rect tile_bounds =
576          tiling_data_.TileBounds(iter.index_x(), iter.index_y());
577      gfx::RectF current_layer_content_rect = gfx::ScaleRect(
578          tile_bounds,
579          current_scale,
580          current_scale);
581      gfx::RectF current_screen_rect = MathUtil::MapClippedRect(
582          current_screen_transform, current_layer_content_rect);
583      gfx::RectF last_layer_content_rect = gfx::ScaleRect(
584          tile_bounds,
585          last_scale,
586          last_scale);
587      gfx::RectF last_screen_rect  = MathUtil::MapClippedRect(
588          last_screen_transform, last_layer_content_rect);
589
590      float distance_to_visible_in_pixels =
591          TilePriority::manhattanDistance(current_screen_rect, view_rect);
592
593      float time_to_visible_in_seconds =
594          TilePriority::TimeForBoundsToIntersect(
595              last_screen_rect, current_screen_rect, time_delta, view_rect);
596
597      TilePriority priority(
598          resolution_,
599          time_to_visible_in_seconds,
600          distance_to_visible_in_pixels);
601      if (store_screen_space_quads_on_tiles) {
602        bool clipped;
603        priority.set_current_screen_quad(
604            MathUtil::MapQuad(current_screen_transform,
605                              gfx::QuadF(current_layer_content_rect),
606                              &clipped));
607      }
608      tile->SetPriority(tree, priority);
609    }
610  }
611
612  last_impl_frame_time_in_seconds_ = current_frame_time_in_seconds;
613}
614
615void PictureLayerTiling::SetLiveTilesRect(
616    gfx::Rect new_live_tiles_rect) {
617  DCHECK(new_live_tiles_rect.IsEmpty() ||
618         ContentRect().Contains(new_live_tiles_rect));
619  if (live_tiles_rect_ == new_live_tiles_rect)
620    return;
621
622  // Iterate to delete all tiles outside of our new live_tiles rect.
623  for (TilingData::DifferenceIterator iter(&tiling_data_,
624                                           live_tiles_rect_,
625                                           new_live_tiles_rect);
626       iter;
627       ++iter) {
628    TileMapKey key(iter.index());
629    TileMap::iterator found = tiles_.find(key);
630    // If the tile was outside of the recorded region, it won't exist even
631    // though it was in the live rect.
632    if (found != tiles_.end())
633      tiles_.erase(found);
634  }
635
636  const PictureLayerTiling* twin_tiling = client_->GetTwinTiling(this);
637
638  // Iterate to allocate new tiles for all regions with newly exposed area.
639  for (TilingData::DifferenceIterator iter(&tiling_data_,
640                                           new_live_tiles_rect,
641                                           live_tiles_rect_);
642       iter;
643       ++iter) {
644    TileMapKey key(iter.index());
645    CreateTile(key.first, key.second, twin_tiling);
646  }
647
648  live_tiles_rect_ = new_live_tiles_rect;
649}
650
651void PictureLayerTiling::DidBecomeRecycled() {
652  // DidBecomeActive below will set the active priority for tiles that are
653  // still in the tree. Calling this first on an active tiling that is becoming
654  // recycled takes care of tiles that are no longer in the active tree (eg.
655  // due to a pending invalidation).
656  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
657    it->second->SetPriority(ACTIVE_TREE, TilePriority());
658  }
659}
660
661void PictureLayerTiling::DidBecomeActive() {
662  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
663    it->second->SetPriority(ACTIVE_TREE, it->second->priority(PENDING_TREE));
664    it->second->SetPriority(PENDING_TREE, TilePriority());
665
666    // Tile holds a ref onto a picture pile. If the tile never gets invalidated
667    // and recreated, then that picture pile ref could exist indefinitely.  To
668    // prevent this, ask the client to update the pile to its own ref.  This
669    // will cause PicturePileImpls and their clones to get deleted once the
670    // corresponding PictureLayerImpl and any in flight raster jobs go out of
671    // scope.
672    client_->UpdatePile(it->second.get());
673  }
674}
675
676void PictureLayerTiling::UpdateTilesToCurrentPile() {
677  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
678    client_->UpdatePile(it->second.get());
679  }
680}
681
682scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
683  scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
684  state->SetInteger("num_tiles", tiles_.size());
685  state->SetDouble("content_scale", contents_scale_);
686  state->Set("content_bounds",
687             MathUtil::AsValue(ContentRect().size()).release());
688  return state.PassAs<base::Value>();
689}
690
691size_t PictureLayerTiling::GPUMemoryUsageInBytes() const {
692  size_t amount = 0;
693  for (TileMap::const_iterator it = tiles_.begin(); it != tiles_.end(); ++it) {
694    const Tile* tile = it->second.get();
695    amount += tile->GPUMemoryUsageInBytes();
696  }
697  return amount;
698}
699
700namespace {
701
702// This struct represents an event at which the expending rect intersects
703// one of its boundaries.  4 intersection events will occur during expansion.
704struct EdgeEvent {
705  enum { BOTTOM, TOP, LEFT, RIGHT } edge;
706  int* num_edges;
707  int distance;
708};
709
710// Compute the delta to expand from edges to cover target_area.
711int ComputeExpansionDelta(int num_x_edges, int num_y_edges,
712                          int width, int height,
713                          int64 target_area) {
714  // Compute coefficients for the quadratic equation:
715  //   a*x^2 + b*x + c = 0
716  int a = num_y_edges * num_x_edges;
717  int b = num_y_edges * width + num_x_edges * height;
718  int64 c = static_cast<int64>(width) * height - target_area;
719
720  // Compute the delta for our edges using the quadratic equation.
721  return a == 0 ? -c / b :
722     (-b + static_cast<int>(
723         std::sqrt(static_cast<int64>(b) * b - 4.0 * a * c))) / (2 * a);
724}
725
726}  // namespace
727
728gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
729    gfx::Rect starting_rect,
730    int64 target_area,
731    gfx::Rect bounding_rect) {
732  if (starting_rect.IsEmpty())
733    return starting_rect;
734
735  DCHECK(!bounding_rect.IsEmpty());
736  DCHECK_GT(target_area, 0);
737
738  // Expand the starting rect to cover target_area, if it is smaller than it.
739  int delta = ComputeExpansionDelta(
740      2, 2, starting_rect.width(), starting_rect.height(), target_area);
741  gfx::Rect expanded_starting_rect = starting_rect;
742  if (delta > 0)
743    expanded_starting_rect.Inset(-delta, -delta);
744
745  gfx::Rect rect = IntersectRects(expanded_starting_rect, bounding_rect);
746  if (rect.IsEmpty()) {
747    // The starting_rect and bounding_rect are far away.
748    return rect;
749  }
750  if (delta >= 0 && rect == expanded_starting_rect) {
751    // The starting rect already covers the entire bounding_rect and isn't too
752    // large for the target_area.
753    return rect;
754  }
755
756  // Continue to expand/shrink rect to let it cover target_area.
757
758  // These values will be updated by the loop and uses as the output.
759  int origin_x = rect.x();
760  int origin_y = rect.y();
761  int width = rect.width();
762  int height = rect.height();
763
764  // In the beginning we will consider 2 edges in each dimension.
765  int num_y_edges = 2;
766  int num_x_edges = 2;
767
768  // Create an event list.
769  EdgeEvent events[] = {
770    { EdgeEvent::BOTTOM, &num_y_edges, rect.y() - bounding_rect.y() },
771    { EdgeEvent::TOP, &num_y_edges, bounding_rect.bottom() - rect.bottom() },
772    { EdgeEvent::LEFT, &num_x_edges, rect.x() - bounding_rect.x() },
773    { EdgeEvent::RIGHT, &num_x_edges, bounding_rect.right() - rect.right() }
774  };
775
776  // Sort the events by distance (closest first).
777  if (events[0].distance > events[1].distance) std::swap(events[0], events[1]);
778  if (events[2].distance > events[3].distance) std::swap(events[2], events[3]);
779  if (events[0].distance > events[2].distance) std::swap(events[0], events[2]);
780  if (events[1].distance > events[3].distance) std::swap(events[1], events[3]);
781  if (events[1].distance > events[2].distance) std::swap(events[1], events[2]);
782
783  for (int event_index = 0; event_index < 4; event_index++) {
784    const EdgeEvent& event = events[event_index];
785
786    int delta = ComputeExpansionDelta(
787        num_x_edges, num_y_edges, width, height, target_area);
788
789    // Clamp delta to our event distance.
790    if (delta > event.distance)
791      delta = event.distance;
792
793    // Adjust the edge count for this kind of edge.
794    --*event.num_edges;
795
796    // Apply the delta to the edges and edge events.
797    for (int i = event_index; i < 4; i++) {
798      switch (events[i].edge) {
799        case EdgeEvent::BOTTOM:
800            origin_y -= delta;
801            height += delta;
802            break;
803        case EdgeEvent::TOP:
804            height += delta;
805            break;
806        case EdgeEvent::LEFT:
807            origin_x -= delta;
808            width += delta;
809            break;
810        case EdgeEvent::RIGHT:
811            width += delta;
812            break;
813      }
814      events[i].distance -= delta;
815    }
816
817    // If our delta is less then our event distance, we're done.
818    if (delta < event.distance)
819      break;
820  }
821
822  return gfx::Rect(origin_x, origin_y, width, height);
823}
824
825}  // namespace cc
826