cc: Compute the inflated rect to cover a fixed number of tiles.

cc/picture_layer_tiling.cc

 // 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/picture_layer_tiling.h"
 
+#include <cmath>
+
 #include "base/debug/trace_event.h"
 #include "cc/math_util.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 {
 
 scoped_ptr<PictureLayerTiling> PictureLayerTiling::Create(
@@ skipping 367 matching lines @@
   if (last_impl_frame_time_ != 0 &&
       last_layer_bounds == current_layer_bounds &&
       last_layer_content_bounds == current_layer_content_bounds &&
       last_layer_contents_scale == current_layer_contents_scale) {
     time_delta = current_frame_time - last_impl_frame_time_;
   }
 
   gfx::Rect viewport_in_content_space =
       gfx::ToEnclosingRect(gfx::ScaleRect(viewport_in_layer_space,
                                           contents_scale_));
-  gfx::Rect inflated_rect = viewport_in_content_space;
-  float adjusted_inset = TilePriority::kMaxDistanceInContentSpace /
-                         std::max(contents_scale_, 1.f);
-  inflated_rect.Inset(
-      -adjusted_inset,
-      -adjusted_inset,
-      -adjusted_inset,
-      -adjusted_inset);
-  inflated_rect.Intersect(ContentRect());
+
+  static const int64 kMaxTilesForPrioritizedRect = 80;

[nduca, 2013/02/16 22:30:59]

Should we put this by where the old constant lived? Or at least, up at the top
of the file? Finding these constants when we want to tweak them is tricky. :)

[danakj, 2013/02/18 19:26:20]

Right, I feel like asking 3 people would get you 3 different answers about where
this should go, I dunno what's best. Perk of putting it here is it's right where
it's used so when you find the code that uses it you also find the constant.
Perk of putting it out in tile_priority.h is its grouped with other constants
that are somewhat related. I stuck it here cuz I couldn't figure out what I like
more, if you like it more there I'll happily move it :) 

I think to move it, it needs a more descriptive name so you can tell what it is
from out of context over in the header. Maybe like
kNumTilesToCoverWithInflatedViewportRectForPrioritization.

+
+  gfx::Size tile_size = tiling_data_.max_texture_size();
+  int64 prioritized_rect_area = kMaxTilesForPrioritizedRect *
+                                tile_size.width() * tile_size.height();
+
+  gfx::Rect prioritized_rect = ExpandRectEquallyToAreaBoundedBy(
+      viewport_in_content_space,
+      prioritized_rect_area,
+      ContentRect());
+  DCHECK(ContentRect().Contains(prioritized_rect));
 
   // Iterate through all of the tiles that were live last frame but will
   // not be live this frame, and mark them as being dead.
   for (TilingData::DifferenceIterator iter(&tiling_data_,
                                            last_prioritized_rect_,
-                                           inflated_rect);
+                                           prioritized_rect);
        iter;
        ++iter) {
     TileMap::iterator find = tiles_.find(iter.index());
     if (find == tiles_.end())
       continue;
 
     TilePriority priority;
     DCHECK(!priority.is_live);
     Tile* tile = find->second.get();
     tile->set_priority(tree, priority);
   }
-  last_prioritized_rect_ = inflated_rect;
+  last_prioritized_rect_ = prioritized_rect;
 
   gfx::Rect view_rect(device_viewport);
   float current_scale = current_layer_contents_scale / contents_scale_;
   float last_scale = last_layer_contents_scale / contents_scale_;
 
   // Fast path tile priority calculation when both transforms are translations.
   if (last_screen_transform.IsIdentityOrTranslation() &&
       current_screen_transform.IsIdentityOrTranslation())
   {
     gfx::Vector2dF current_offset(
         current_screen_transform.matrix().get(0, 3),
         current_screen_transform.matrix().get(1, 3));
     gfx::Vector2dF last_offset(
         last_screen_transform.matrix().get(0, 3),
         last_screen_transform.matrix().get(1, 3));
 
-    for (TilingData::Iterator iter(&tiling_data_, inflated_rect);
+    for (TilingData::Iterator iter(&tiling_data_, prioritized_rect);
          iter; ++iter) {
       TileMap::iterator find = tiles_.find(iter.index());
       if (find == tiles_.end())
         continue;
       Tile* tile = find->second.get();
 
       gfx::Rect tile_bounds =
           tiling_data_.TileBounds(iter.index_x(), iter.index_y());
       gfx::RectF current_screen_rect = gfx::ScaleRect(
           tile_bounds,
@@ skipping 12 matching lines @@
               last_screen_rect, current_screen_rect, time_delta, view_rect);
       TilePriority priority(
           resolution_,
           time_to_visible_in_seconds,
           distance_to_visible_in_pixels);
       if (store_screen_space_quads_on_tiles)
         priority.set_current_screen_quad(gfx::QuadF(current_screen_rect));
       tile->set_priority(tree, priority);
     }
   } else {
-    for (TilingData::Iterator iter(&tiling_data_, inflated_rect);
+    for (TilingData::Iterator iter(&tiling_data_, prioritized_rect);
          iter; ++iter) {
       TileMap::iterator find = tiles_.find(iter.index());
       if (find == tiles_.end())
         continue;
       Tile* tile = find->second.get();
 
       gfx::Rect tile_bounds =
           tiling_data_.TileBounds(iter.index_x(), iter.index_y());
       gfx::RectF current_layer_content_rect = gfx::ScaleRect(
           tile_bounds,
@@ skipping 51 matching lines @@
 
 scoped_ptr<base::Value> PictureLayerTiling::AsValue() const {
   scoped_ptr<base::DictionaryValue> state(new base::DictionaryValue());
   state->SetInteger("num_tiles", tiles_.size());
   state->SetDouble("content_scale", contents_scale_);
   state->Set("content_bounds",
              MathUtil::asValue(ContentRect().size()).release());
   return state.PassAs<base::Value>();
 }
 
+namespace {
+
+int ComputeOffsetToExpand4EdgesEqually(int old_width,
+                                       int old_height,
+                                       int64 target_area) {
+  // We need to expand the rect in 4 directions, we can compute the
+  // amount to expand along each axis with a quadratic equation:
+  //   (old_w + add) * (old_h + add) = target_area
+  //   old_w * old_h + old_w * add + add * old_h + add * add = target_area
+  //   add^2 + add * (old_w + old_h) - target_area + old_w * old_h = 0
+  // Therefore, we solve the quadratic equation with:
+  // a = 1
+  // b = old_w + old_h
+  // c = -target_area + old_w * old_h
+  int a = 1;
+  int64 b = old_width + old_height;
+  int64 c = -target_area + old_width * old_height;
+  int sqrt_part = std::sqrt(b * b - 4.0 * a * c);
+  int add_each_axis = (-b + sqrt_part) / 2 / a;
+  return add_each_axis / 2;
+}
+
+int ComputeOffsetToExpand3EdgesEqually(int old_width,
+                                       int old_height,
+                                       int64 target_area,
+                                       bool left_complete,
+                                       bool top_complete,
+                                       bool right_complete,
+                                       bool bottom_complete) {
+  // We need to expand the rect in three directions, so we will have to
+  // expand along one axis twice as much as the other. Otherwise, this
+  // is very similar to the case where we expand in all 4 directions.
+
+  if (left_complete || right_complete) {
+    // Expanding twice as much vertically as horizontally.
+    //   (old_w + add) * (old_h + add*2) = target_area
+    //   old_w * old_h + old_w * add*2 + add * old_h + add * add*2 = target_area
+    //   (add^2)*2 + add * (old_w*2 + old_h) - target_area + old_w * old_h = 0
+    // Therefore, we solve the quadratic equation with:
+    // a = 2
+    // b = old_w*2 + old_h
+    // c = -target_area + old_w * old_h
+    int a = 2;
+    int64 b = old_width * 2 + old_height;
+    int64 c = -target_area + old_width * old_height;
+    int sqrt_part = std::sqrt(b * b - 4.0 * a * c);
+    int add_each_direction = (-b + sqrt_part) / 2 / a;
+    return add_each_direction;
+  } else {
+    // Expanding twice as much horizontally as vertically.
+    //   (old_w + add*2) * (old_h + add) = target_area
+    //   old_w * old_h + old_w * add + add*2 * old_h + add*2 * add = target_area
+    //   (add^2)*2 + add * (old_w + old_h*2) - target_area + old_w * old_h = 0
+    // Therefore, we solve the quadratic equation with:
+    // a = 2
+    // b = old_w + old_h*2
+    // c = -target_area + old_w * old_h
+    int a = 2;
+    int64 b = old_width + old_height * 2;
+    int64 c = -target_area + old_width * old_height;
+    int sqrt_part = std::sqrt(b * b - 4.0 * a * c);
+    int add_each_direction = (-b + sqrt_part) / 2 / a;
+    return add_each_direction;
+  }
+}
+
+int ComputeOffsetToExpand2EdgesEqually(int old_width,
+                                       int old_height,
+                                       int64 target_area,
+                                       bool left_complete,
+                                       bool top_complete,
+                                       bool right_complete,
+                                       bool bottom_complete) {
+  // We need to expand the rect along two directions. If the two directions
+  // are opposite from each other then we only need to compute a distance
+  // along a single axis.
+  if (left_complete && right_complete) {
+    // Expanding along the vertical axis only:
+    //   old_w * (old_h + add) = target_area
+    //   old_w * old_h + old_w * add = target_area
+    //   add_vertically = (target_area - old_w * old_h) / old_w
+    int add_vertically = target_area / old_width - old_height;
+    return add_vertically / 2;
+  } else if (top_complete && bottom_complete) {
+    // Expanding along the horizontal axis only:
+    //   (old_w + add) * old_h = target_area
+    //   old_w * old_h + add * old_h = target_area
+    //   add_horizontally = (target_area - old_w * old_h) / old_h
+    int add_horizontally = target_area / old_height - old_width;
+    return add_horizontally / 2;
+  } else {
+    // If we need to expand along both horizontal and vertical axes, we can use
+    // the same result as if we were expanding all four edges. But we apply the
+    // offset computed for opposing edges to a single edge.
+    int add_each_direction = ComputeOffsetToExpand4EdgesEqually(
+        old_width, old_height, target_area);
+    return add_each_direction * 2;
+  }
+}
+
+int ComputeOffsetToExpand1Edge(int old_width,
+                               int old_height,
+                               int64 target_area,
+                               bool left_complete,
+                               bool top_complete,
+                               bool right_complete,
+                               bool bottom_complete) {
+  // We need to expand the rect in a single direction, so we are either
+  // moving just a verical edge, or just a horizontal edge.
+  if (!top_complete || !bottom_complete) {
+    // Moving a vertical edge:
+    //   old_w * (old_h + add) = target_area
+    //   old_w * old_h + old_w * add = target_area
+    //   add_vertically = (target_area - old_w * old_h) / old_w
+    int add_vertically = target_area / old_width - old_height;
+    return add_vertically;
+  } else {
+    // Moving a horizontal edge:
+    //   (old_w + add) * old_h = target_area
+    //   old_w * old_h + add * old_h = target_area
+    //   add_horizontally = (target_area - old_w * old_h) / old_h
+    int add_horizontally = target_area / old_height - old_width;
+    return add_horizontally;
+  }
+}
+
+}  // namespace
+
+// static
+gfx::Rect PictureLayerTiling::ExpandRectEquallyToAreaBoundedBy(
+    gfx::Rect starting_rect,
+    int64 target_area,
+    gfx::Rect bounding_rect) {
+
+  bool left_complete = false;
+  bool top_complete = false;
+  bool right_complete = false;
+  bool bottom_complete = false;
+  int num_edges_complete = 0;
+
+  gfx::Rect working_rect = starting_rect;
+  for (int i = 0; i < 4; ++i) {
+    if (num_edges_complete != i)
+      continue;
+    int offset_for_each_edge = 0;
+    switch (num_edges_complete) {
+      case 0:
+        offset_for_each_edge = ComputeOffsetToExpand4EdgesEqually(
+            working_rect.width(),
+            working_rect.height(),
+            target_area);
+        break;
+      case 1:
+        offset_for_each_edge = ComputeOffsetToExpand3EdgesEqually(
+            working_rect.width(),
+            working_rect.height(),
+            target_area,
+            left_complete,
+            top_complete,
+            right_complete,
+            bottom_complete);
+        break;
+      case 2:
+        offset_for_each_edge = ComputeOffsetToExpand2EdgesEqually(
+            working_rect.width(),
+            working_rect.height(),
+            target_area,
+            left_complete,
+            top_complete,
+            right_complete,
+            bottom_complete);
+        break;
+      case 3:
+        offset_for_each_edge = ComputeOffsetToExpand1Edge(
+            working_rect.width(),
+            working_rect.height(),
+            target_area,
+            left_complete,
+            top_complete,
+            right_complete,
+            bottom_complete);
+    }
+
+    working_rect.Inset((left_complete ? 0 : -offset_for_each_edge),
+                       (top_complete ? 0 : -offset_for_each_edge),
+                       (right_complete ? 0 : -offset_for_each_edge),
+                       (bottom_complete ? 0 : -offset_for_each_edge));
+
+    if (bounding_rect.Contains(working_rect))
+      return working_rect;
+    working_rect.Intersect(bounding_rect);
+
+    if (working_rect.x() == bounding_rect.x()) left_complete = true;
+    if (working_rect.y() == bounding_rect.y()) top_complete = true;
+    if (working_rect.right() == bounding_rect.right()) right_complete = true;
+    if (working_rect.bottom() == bounding_rect.bottom()) bottom_complete = true;
+
+    num_edges_complete = (left_complete ? 1 : 0) +
+                         (top_complete ? 1 : 0) +
+                         (right_complete ? 1 : 0) +
+                         (bottom_complete ? 1 : 0);
+    if (num_edges_complete == 4)
+      return working_rect;
+  }
+
+  NOTREACHED();
+  return starting_rect;
+}
+
 }  // namespace cc