A host of micro-optimizations and a refactor of TimeForBoundsToIntersect

cc/tile_priority.cc

Index: cc/tile_priority.cc
diff --git a/cc/tile_priority.cc b/cc/tile_priority.cc
index 1fde0bcdcae3698603a05bf4579d29a07e0959d4..3028cd0f8e896d31aeed7f22fdd7473670796a8d 100644
--- a/cc/tile_priority.cc
+++ b/cc/tile_priority.cc
@@ -9,96 +9,86 @@ namespace {
 // TODO(qinmin): modify ui/range/Range.h to support template so that we
 // don't need to define this.
 struct Range {
-  Range(double start, double end) : start_(start), end_(end) {}
-  Range Intersects(const Range& other);
+  Range(float start, float end) : start_(start), end_(end) {}
   bool IsEmpty();
-  double start_;
-  double end_;
+  float start_;
+  float end_;
 };
 
-Range Range::Intersects(const Range& other) {
-  start_ = std::max(start_, other.start_);
-  end_ = std::min(end_, other.end_);
-  return Range(start_, end_);
+inline bool Intersects(const Range& a, const Range& b) {
+  return a.start_ < b.end_ && b.start_ < a.end_;
+}
+
+inline Range Intersect(const Range& a, const Range& b) {
+  return Range(std::max(a.start_, b.start_), std::min(a.end_, b.end_));
 }
 
 bool Range::IsEmpty() {
   return start_ >= end_;
 }
 
-// Calculate a time range that |value| will be larger than |threshold|
-// given the velocity of its change.
-Range TimeRangeValueLargerThanThreshold(
-    int value, int threshold, double velocity) {
-  double minimum_time = 0;
-  double maximum_time = cc::TilePriority::kMaxTimeToVisibleInSeconds;
-
-  if (velocity > 0) {
-    if (value < threshold)
-      minimum_time = std::min(cc::TilePriority::kMaxTimeToVisibleInSeconds,
-                              (threshold - value) / velocity);
-  } else if (velocity <= 0) {
-    if (value < threshold)
-      minimum_time = cc::TilePriority::kMaxTimeToVisibleInSeconds;
-    else if (velocity != 0)
-      maximum_time = std::min(maximum_time, (threshold - value) / velocity);
-  }
-
-  return Range(minimum_time, maximum_time);
+inline Range Intersect(const Range& previous, const Range& current, float time_delta, const Range& target)
+{
+  // Calculate the scale factors.
+  float time_per_dist_start = time_delta/(current.start_-previous.start_);
+  float time_per_dist_end   = time_delta/(current.end_  -previous.end_  );
+
+  // Calcuate the 4 times of intersection.
+  float start_hit_start = (target.start_-current.start_)*time_per_dist_start;
+  float start_hit_end   = (target.end_  -current.start_)*time_per_dist_start;
+  float end_hit_start   = (target.start_-current.end_)*time_per_dist_end;
+  float end_hit_end     = (target.end_  -current.end_)*time_per_dist_end;
+
+  // Return the union of the for intersection times.
+  return Range(
+      std::min(
+          std::min(start_hit_start, start_hit_end),
+          std::min(end_hit_start, end_hit_end)),
+      std::max(
+          std::max(start_hit_start, start_hit_end),
+          std::max(end_hit_start, end_hit_end)));
 }
 
 }  // namespace
 
 namespace cc {
 
-const double TilePriority::kMaxTimeToVisibleInSeconds = 1000;
-
-int TilePriority::manhattanDistance(const gfx::RectF& a, const gfx::RectF& b) {
-  gfx::RectF c = gfx::UnionRects(a, b);
-  // Rects touching the edge of the screen should not be considered visible.
-  // So we add 1 pixel here to avoid that situation.
-  int x = static_cast<int>(
-      std::max(0.0f, c.width() - a.width() - b.width() + 1));
-  int y = static_cast<int>(
-      std::max(0.0f, c.height() - a.height() - b.height() + 1));
-  return (x + y);
-}
-
-double TilePriority::TimeForBoundsToIntersect(gfx::RectF previous_bounds,
-                                              gfx::RectF current_bounds,
-                                              double time_delta,
-                                              gfx::RectF target_bounds) {
-  if (current_bounds.Intersects(target_bounds))
-    return 0;
-
-  if (previous_bounds.Intersects(target_bounds) || time_delta == 0)
+const float TilePriority::kMaxTimeToVisibleInSeconds = std::numeric_limits<float>::infinity();
+
+float TilePriority::TimeForBoundsToIntersect(const gfx::RectF& previous_bounds,
+                                             const gfx::RectF& current_bounds,
+                                             float time_delta,
+                                             const gfx::RectF& target_bounds) {
+  // Convert the rects to ranges.
+  Range previous_x_range(previous_bounds.x(), previous_bounds.right());
+  Range previous_y_range(previous_bounds.y(), previous_bounds.bottom());
+  Range current_x_range(current_bounds.x(), current_bounds.right());
+  Range current_y_range(current_bounds.y(), current_bounds.bottom());
+  Range target_x_range(current_bounds.x(), target_bounds.right());
+  Range target_y_range(current_bounds.y(), target_bounds.bottom());
+
+  // Check to see if the tile is visible.
+  if (Intersects(current_x_range, target_x_range) &&
+      Intersects(current_y_range, target_y_range))
+    return 0.0f;
+
+  // Check to see if the tile didn't move.
+  if (time_delta == 0.0f)
     return kMaxTimeToVisibleInSeconds;
 
-  // As we are trying to solve the case of both scaling and scrolling, using
-  // a single coordinate with velocity is not enough. The logic here is to
-  // calculate the velocity for each edge. Then we calculate the time range that
-  // each edge will stay on the same side of the target bounds. If there is an
-  // overlap between these time ranges, the bounds must have intersect with
-  // each other during that period of time.
-  double velocity =
-      (current_bounds.right() - previous_bounds.right()) / time_delta;
-  Range range = TimeRangeValueLargerThanThreshold(
-      current_bounds.right(), target_bounds.x(), velocity);
+  // Calculate the intersection time intervals in X and Y.
+  Range x_range = Intersect(
+      previous_x_range, current_x_range, time_delta, target_x_range);
+  Range y_range = Intersect(
+      previous_y_range, current_y_range, time_delta, target_y_range);
 
-  velocity = (current_bounds.x() - previous_bounds.x()) / time_delta;
-  range = range.Intersects(TimeRangeValueLargerThanThreshold(
-      -current_bounds.x(), -target_bounds.right(), -velocity));
+  // Intersect the X and Y intervals and clamp to positive range.
+  Range range = Intersect(x_range, y_range);
+  range.start_ = std::max(range.start_, 0.0f);
 
-
-  velocity = (current_bounds.y() - previous_bounds.y()) / time_delta;
-  range = range.Intersects(TimeRangeValueLargerThanThreshold(
-      -current_bounds.y(), -target_bounds.bottom(), -velocity));
-
-  velocity = (current_bounds.bottom() - previous_bounds.bottom()) / time_delta;
-  range = range.Intersects(TimeRangeValueLargerThanThreshold(
-      current_bounds.bottom(), target_bounds.y(), velocity));
-
-  return range.IsEmpty() ? kMaxTimeToVisibleInSeconds : range.start_;
+  if (range.IsEmpty())
+    return kMaxTimeToVisibleInSeconds;
+  return range.start_;
 }
 
 }  // namespace cc