cc: Implement tile iteration order based on pyramid sequence. [old]

cc/base/tiling_data.cc

 // Copyright 2010 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/base/tiling_data.h"
 
 #include <algorithm>
 
 #include "ui/gfx/geometry/rect.h"
 #include "ui/gfx/geometry/vector2d.h"
@@ skipping 108 matching lines @@
 int TilingData::LastBorderTileYIndexFromSrcCoord(int src_position) const {
   if (num_tiles_y_ <= 1)
     return 0;
 
   DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0);
   int inner_tile_size = max_texture_size_.height() - 2 * border_texels_;
   int y = src_position / inner_tile_size;
   return std::min(std::max(y, 0), num_tiles_y_ - 1);
 }
 
+int TilingData::TileVirtualXIndexFromSrcCoord(int src_position) const {
+  int inner_tile_width = max_texture_size_.width() - 2 * border_texels_;
+  if (src_position < 0)
+    src_position -= inner_tile_width;
+
+  return (src_position - border_texels_) / inner_tile_width;
+}
+
+int TilingData::TileVirtualYIndexFromSrcCoord(int src_position) const {
+  int inner_tile_height = max_texture_size_.height() - 2 * border_texels_;
+  if (src_position < 0)
+    src_position -= inner_tile_height;
+
+  return (src_position - border_texels_) / inner_tile_height;
+}
+
+// TODO(prashant.n): Implement IndexRect for encapsulating indices.
+// crbug.com/624792
+void TilingData::TileVirtualAroundIndices(const gfx::Rect& center_rect,
+                                          int* around_left,
+                                          int* around_right,
+                                          int* around_top,
+                                          int* around_bottom) const {
+  if (center_rect.IsEmpty()) {
+    // Default around rect is assumed to be at top-left corner of tile at
+    // (0, 0).
+    *around_left = -2;
+    *around_top = -2;
+    *around_right = 0;
+    *around_bottom = 0;
+    return;
+  }
+
+  gfx::Rect tiling_rect(tiling_size());
+
+  *around_left = TileVirtualXIndexFromSrcCoord(center_rect.x());
+  *around_top = TileVirtualYIndexFromSrcCoord(center_rect.y());
+  int right_src_coord = center_rect.right() - 1;
+  *around_right = TileVirtualXIndexFromSrcCoord(right_src_coord) + 1;
+  int bottom_src_coord = center_rect.bottom() - 1;
+  *around_bottom = TileVirtualYIndexFromSrcCoord(bottom_src_coord) + 1;
+
+  // For left and top indices check if tiling size is smaller than tile size. In
+  // such case if center rect is not intersecting the tiling rect and if center
+  // rect is right (or below) to the tiling rect, then around tile index is same
+  // as the index returned by TileVirtual(X|Y)IndexFromSrcCoord().
+  if (!(num_tiles_x() == 1 && *around_left == 0 &&
+        !tiling_rect.Intersects(center_rect) &&
+        tiling_rect.right() < center_rect.x())) {
+    *around_left -= 1;
+  }
+  if (!(num_tiles_y() == 1 && *around_top == 0 &&
+        !tiling_rect.Intersects(center_rect) &&
+        tiling_rect.bottom() < center_rect.y())) {
+    *around_top -= 1;
+  }
+}
+
 gfx::Rect TilingData::ExpandRectIgnoringBordersToTileBounds(
     const gfx::Rect& rect) const {
   if (rect.IsEmpty() || has_empty_bounds())
     return gfx::Rect();
   if (rect.x() > tiling_size_.width() || rect.y() > tiling_size_.height())
     return gfx::Rect();
   int index_x = TileXIndexFromSrcCoord(rect.x());
   int index_y = TileYIndexFromSrcCoord(rect.y());
   int index_right = TileXIndexFromSrcCoord(rect.right() - 1);
   int index_bottom = TileYIndexFromSrcCoord(rect.bottom() - 1);
@@ skipping 330 matching lines @@
 
 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator() {
   done();
 }
 
 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
     const TilingData* tiling_data,
     const gfx::Rect& consider_rect,
     const gfx::Rect& ignore_rect,
     const gfx::Rect& center_rect)
-    : BaseDifferenceIterator(tiling_data, consider_rect, ignore_rect),
-      direction_(RIGHT),
-      delta_x_(1),
-      delta_y_(0),
-      current_step_(0),
-      horizontal_step_count_(0),
-      vertical_step_count_(0) {
+    : BaseDifferenceIterator(tiling_data, consider_rect, ignore_rect) {
   if (!HasConsiderRect()) {
     done();
     return;
   }
 
-  // Determine around left, such that it is between -1 and num_tiles_x.
-  int around_left = 0;
-  if (center_rect.x() < 0 || center_rect.IsEmpty())
-    around_left = -1;
-  else if (center_rect.x() >= tiling_data->tiling_size().width())
-    around_left = tiling_data->num_tiles_x();
-  else
-    around_left = tiling_data->TileXIndexFromSrcCoord(center_rect.x());
-
-  // Determine around top, such that it is between -1 and num_tiles_y.
-  int around_top = 0;
-  if (center_rect.y() < 0 || center_rect.IsEmpty())
-    around_top = -1;
-  else if (center_rect.y() >= tiling_data->tiling_size().height())
-    around_top = tiling_data->num_tiles_y();
-  else
-    around_top = tiling_data->TileYIndexFromSrcCoord(center_rect.y());
-
-  // Determine around right, such that it is between -1 and num_tiles_x.
-  int right_src_coord = center_rect.right() - 1;
-  int around_right = 0;
-  if (right_src_coord < 0 || center_rect.IsEmpty()) {
-    around_right = -1;
-  } else if (right_src_coord >= tiling_data->tiling_size().width()) {
-    around_right = tiling_data->num_tiles_x();
-  } else {
-    around_right = tiling_data->TileXIndexFromSrcCoord(right_src_coord);
+  if (tiling_data->max_texture_size().IsEmpty()) {
+    done();
+    return;
   }
 
-  // Determine around bottom, such that it is between -1 and num_tiles_y.
-  int bottom_src_coord = center_rect.bottom() - 1;
-  int around_bottom = 0;
-  if (bottom_src_coord < 0 || center_rect.IsEmpty()) {
-    around_bottom = -1;
-  } else if (bottom_src_coord >= tiling_data->tiling_size().height()) {
-    around_bottom = tiling_data->num_tiles_y();
-  } else {
-    around_bottom = tiling_data->TileYIndexFromSrcCoord(bottom_src_coord);
+  int around_left;
+  int around_top;
+  int around_right;
+  int around_bottom;
+
+  tiling_data->TileVirtualAroundIndices(
+      center_rect, &around_left, &around_right, &around_top, &around_bottom);
+
+  pyramid_sequence_.Init(around_left, around_right, around_top, around_bottom,
+                         consider_left_, consider_right_, consider_top_,
+                         consider_bottom_, ignore_left_, ignore_right_,
+                         ignore_top_, ignore_bottom_,
+                         tiling_data->max_texture_size().width(),
+                         tiling_data->max_texture_size().height());
+
+  if (!pyramid_sequence_) {
+    done();
+    return;
   }
 
-  vertical_step_count_ = around_bottom - around_top + 1;
-  horizontal_step_count_ = around_right - around_left + 1;
-  current_step_ = horizontal_step_count_ - 1;
+  index_x_ = pyramid_sequence_.index_x();
+  index_y_ = pyramid_sequence_.index_y();
+  DCHECK(in_consider_rect() && !in_ignore_rect());
+}
 
-  index_x_ = around_right;
-  index_y_ = around_bottom;
+TilingData::SpiralDifferenceIterator::~SpiralDifferenceIterator() {}
 
-  // The current index is the bottom right of the around rect, which is also
-  // ignored. So we have to advance.
-  ++(*this);
-}
+TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
+    const TilingData::SpiralDifferenceIterator& other) = default;
+
+TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
+    TilingData::SpiralDifferenceIterator&& other) = default;
+
+TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
+operator=(const TilingData::SpiralDifferenceIterator& other) = default;
+
+TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
+operator=(TilingData::SpiralDifferenceIterator&& other) = default;
 
 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
 operator++() {
-  int cannot_hit_consider_count = 0;
-  while (cannot_hit_consider_count < 4) {
-    if (needs_direction_switch())
-      switch_direction();
+  ++pyramid_sequence_;
 
-    index_x_ += delta_x_;
-    index_y_ += delta_y_;
-    ++current_step_;
-
-    if (in_consider_rect()) {
-      cannot_hit_consider_count = 0;
-
-      if (!in_ignore_rect())
-        break;
-
-      // Steps needed to reach the very edge of the ignore rect, while remaining
-      // inside (so that the continue would take us outside).
-      int steps_to_edge = 0;
-      switch (direction_) {
-        case UP:
-          steps_to_edge = index_y_ - ignore_top_;
-          break;
-        case LEFT:
-          steps_to_edge = index_x_ - ignore_left_;
-          break;
-        case DOWN:
-          steps_to_edge = ignore_bottom_ - index_y_;
-          break;
-        case RIGHT:
-          steps_to_edge = ignore_right_ - index_x_;
-          break;
-      }
-
-      // We need to switch directions in |max_steps|.
-      int max_steps = current_step_count() - current_step_;
-
-      int steps_to_take = std::min(steps_to_edge, max_steps);
-      DCHECK_GE(steps_to_take, 0);
-
-      index_x_ += steps_to_take * delta_x_;
-      index_y_ += steps_to_take * delta_y_;
-      current_step_ += steps_to_take;
-    } else {
-      int max_steps = current_step_count() - current_step_;
-      int steps_to_take = max_steps;
-      bool can_hit_consider_rect = false;
-      switch (direction_) {
-        case UP:
-          if (valid_column() && consider_bottom_ < index_y_)
-            steps_to_take = index_y_ - consider_bottom_ - 1;
-          can_hit_consider_rect |= consider_right_ >= index_x_;
-          break;
-        case LEFT:
-          if (valid_row() && consider_right_ < index_x_)
-            steps_to_take = index_x_ - consider_right_ - 1;
-          can_hit_consider_rect |= consider_top_ <= index_y_;
-          break;
-        case DOWN:
-          if (valid_column() && consider_top_ > index_y_)
-            steps_to_take = consider_top_ - index_y_ - 1;
-          can_hit_consider_rect |= consider_left_ <= index_x_;
-          break;
-        case RIGHT:
-          if (valid_row() && consider_left_ > index_x_)
-            steps_to_take = consider_left_ - index_x_ - 1;
-          can_hit_consider_rect |= consider_bottom_ >= index_y_;
-          break;
-      }
-      steps_to_take = std::min(steps_to_take, max_steps);
-      DCHECK_GE(steps_to_take, 0);
-
-      index_x_ += steps_to_take * delta_x_;
-      index_y_ += steps_to_take * delta_y_;
-      current_step_ += steps_to_take;
-
-      if (can_hit_consider_rect)
-        cannot_hit_consider_count = 0;
-      else
-        ++cannot_hit_consider_count;
-    }
+  if (!pyramid_sequence_) {
+    done();
+    return *this;
   }
 
-  if (cannot_hit_consider_count >= 4)
-    done();
+  index_x_ = pyramid_sequence_.index_x();
+  index_y_ = pyramid_sequence_.index_y();
+
+  DCHECK(in_consider_rect() && !in_ignore_rect());
   return *this;
 }
 
-bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
-  return current_step_ >= current_step_count();
-}
-
-void TilingData::SpiralDifferenceIterator::switch_direction() {
-  // Note that delta_x_ and delta_y_ always remain between -1 and 1.
-  int new_delta_x_ = delta_y_;
-  delta_y_ = -delta_x_;
-  delta_x_ = new_delta_x_;
-
-  current_step_ = 0;
-  direction_ = static_cast<Direction>((direction_ + 1) % 4);
-
-  if (direction_ == RIGHT || direction_ == LEFT) {
-    ++vertical_step_count_;
-    ++horizontal_step_count_;
-  }
-}
-
 TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator() {
   done();
 }
 
 TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
     const TilingData* tiling_data,
     const gfx::Rect& consider_rect,
     const gfx::Rect& ignore_rect,
     const gfx::Rect& center_rect)
-    : BaseDifferenceIterator(tiling_data, consider_rect, ignore_rect),
-      around_left_(-1),
-      around_top_(-1),
-      around_right_(-1),
-      around_bottom_(-1),
-      direction_(LEFT),
-      delta_x_(-1),
-      delta_y_(0),
-      current_step_(0),
-      horizontal_step_count_(0),
-      vertical_step_count_(0) {
+    : BaseDifferenceIterator(tiling_data, consider_rect, ignore_rect) {
   if (!HasConsiderRect()) {
     done();
     return;
   }
 
-  // Determine around left, such that it is between -1 and num_tiles_x.
-  if (center_rect.x() < 0 || center_rect.IsEmpty())
-    around_left_ = -1;
-  else if (center_rect.x() >= tiling_data->tiling_size().width())
-    around_left_ = tiling_data->num_tiles_x();
-  else
-    around_left_ = tiling_data->TileXIndexFromSrcCoord(center_rect.x());
-
-  // Determine around top, such that it is between -1 and num_tiles_y.
-  if (center_rect.y() < 0 || center_rect.IsEmpty())
-    around_top_ = -1;
-  else if (center_rect.y() >= tiling_data->tiling_size().height())
-    around_top_ = tiling_data->num_tiles_y();
-  else
-    around_top_ = tiling_data->TileYIndexFromSrcCoord(center_rect.y());
-
-  // Determine around right, such that it is between -1 and num_tiles_x.
-  int right_src_coord = center_rect.right() - 1;
-  if (right_src_coord < 0 || center_rect.IsEmpty()) {
-    around_right_ = -1;
-  } else if (right_src_coord >= tiling_data->tiling_size().width()) {
-    around_right_ = tiling_data->num_tiles_x();
-  } else {
-    around_right_ = tiling_data->TileXIndexFromSrcCoord(right_src_coord);
+  if (tiling_data->max_texture_size().IsEmpty()) {
+    done();
+    return;
   }
 
-  // Determine around bottom, such that it is between -1 and num_tiles_y.
-  int bottom_src_coord = center_rect.bottom() - 1;
-  if (bottom_src_coord < 0 || center_rect.IsEmpty()) {
-    around_bottom_ = -1;
-  } else if (bottom_src_coord >= tiling_data->tiling_size().height()) {
-    around_bottom_ = tiling_data->num_tiles_y();
-  } else {
-    around_bottom_ = tiling_data->TileYIndexFromSrcCoord(bottom_src_coord);
+  int around_left;
+  int around_top;
+  int around_right;
+  int around_bottom;
+
+  tiling_data->TileVirtualAroundIndices(
+      center_rect, &around_left, &around_right, &around_top, &around_bottom);
+
+  pyramid_sequence_.Init(around_left, around_right, around_top, around_bottom,
+                         consider_left_, consider_right_, consider_top_,
+                         consider_bottom_, ignore_left_, ignore_right_,
+                         ignore_top_, ignore_bottom_,
+                         tiling_data->max_texture_size().width(),
+                         tiling_data->max_texture_size().height());
+
+  if (!pyramid_sequence_) {
+    done();
+    return;
   }
 
-  // Figure out the maximum distance from the around edge to consider edge.
-  int max_distance = 0;
-  max_distance = std::max(max_distance, around_top_ - consider_top_);
-  max_distance = std::max(max_distance, around_left_ - consider_left_);
-  max_distance = std::max(max_distance, consider_bottom_ - around_bottom_);
-  max_distance = std::max(max_distance, consider_right_ - around_right_);
-
-  // The step count is the length of the edge (around_right_ - around_left_ + 1)
-  // plus twice the max distance to pad (to the right and to the left). This way
-  // the initial rect is the size proportional to the center, but big enough
-  // to cover the consider rect.
-  //
-  // C = consider rect
-  // A = around rect
-  // . = area of the padded around rect
-  // md = max distance (note in the picture below, there's md written vertically
-  //      as well).
-  // I = initial starting position
-  //
-  //       |md|  |md|
-  //
-  //     - ..........
-  //     m ..........
-  //     d ..........
-  //     - CCCCCCC...
-  //       CCCCAAC...
-  //       CCCCAAC...
-  //     - ..........
-  //     m ..........
-  //     d ..........
-  //     - ..........I
-  vertical_step_count_ = around_bottom_ - around_top_ + 1 + 2 * max_distance;
-  horizontal_step_count_ = around_right_ - around_left_ + 1 + 2 * max_distance;
-
-  // Start with one to the right of the padded around rect.
-  index_x_ = around_right_ + max_distance + 1;
-  index_y_ = around_bottom_ + max_distance;
-
-  // The current index is outside a valid tile, so advance immediately.
-  ++(*this);
+  index_x_ = pyramid_sequence_.index_x();
+  index_y_ = pyramid_sequence_.index_y();
+  DCHECK(in_consider_rect() && !in_ignore_rect());
 }
 
+TilingData::ReverseSpiralDifferenceIterator::
+    ~ReverseSpiralDifferenceIterator() {}
+
+TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
+    const TilingData::ReverseSpiralDifferenceIterator& other) = default;
+
+TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
+    TilingData::ReverseSpiralDifferenceIterator&& other) = default;
+
 TilingData::ReverseSpiralDifferenceIterator&
-    TilingData::ReverseSpiralDifferenceIterator::
-    operator++() {
-  while (!in_around_rect()) {
-    if (needs_direction_switch())
-      switch_direction();
+TilingData::ReverseSpiralDifferenceIterator::operator=(
+    const TilingData::ReverseSpiralDifferenceIterator& other) = default;
 
-    index_x_ += delta_x_;
-    index_y_ += delta_y_;
-    ++current_step_;
+TilingData::ReverseSpiralDifferenceIterator&
+TilingData::ReverseSpiralDifferenceIterator::operator=(
+    TilingData::ReverseSpiralDifferenceIterator&& other) = default;
 
-    if (in_around_rect()) {
-      break;
-    } else if (in_consider_rect()) {
-      // If the tile is in the consider rect but not in ignore rect, then it's a
-      // valid tile to visit.
-      if (!in_ignore_rect())
-        break;
+TilingData::ReverseSpiralDifferenceIterator&
+    TilingData::ReverseSpiralDifferenceIterator::operator++() {
+  ++pyramid_sequence_;
 
-      // Steps needed to reach the very edge of the ignore rect, while remaining
-      // inside it (so that the continue would take us outside).
-      int steps_to_edge = 0;
-      switch (direction_) {
-        case UP:
-          steps_to_edge = index_y_ - ignore_top_;
-          break;
-        case LEFT:
-          steps_to_edge = index_x_ - ignore_left_;
-          break;
-        case DOWN:
-          steps_to_edge = ignore_bottom_ - index_y_;
-          break;
-        case RIGHT:
-          steps_to_edge = ignore_right_ - index_x_;
-          break;
-      }
-
-      // We need to switch directions in |max_steps|.
-      int max_steps = current_step_count() - current_step_;
-
-      int steps_to_take = std::min(steps_to_edge, max_steps);
-      DCHECK_GE(steps_to_take, 0);
-
-      index_x_ += steps_to_take * delta_x_;
-      index_y_ += steps_to_take * delta_y_;
-      current_step_ += steps_to_take;
-    } else {
-      // We're not in the consider rect.
-
-      int max_steps = current_step_count() - current_step_;
-      int steps_to_take = max_steps;
-
-      // We might hit the consider rect before needing to switch directions:
-      // update steps to take.
-      switch (direction_) {
-        case UP:
-          if (valid_column() && consider_bottom_ < index_y_)
-            steps_to_take = index_y_ - consider_bottom_ - 1;
-          break;
-        case LEFT:
-          if (valid_row() && consider_right_ < index_x_)
-            steps_to_take = index_x_ - consider_right_ - 1;
-          break;
-        case DOWN:
-          if (valid_column() && consider_top_ > index_y_)
-            steps_to_take = consider_top_ - index_y_ - 1;
-          break;
-        case RIGHT:
-          if (valid_row() && consider_left_ > index_x_)
-            steps_to_take = consider_left_ - index_x_ - 1;
-          break;
-      }
-      steps_to_take = std::min(steps_to_take, max_steps);
-      DCHECK_GE(steps_to_take, 0);
-
-      index_x_ += steps_to_take * delta_x_;
-      index_y_ += steps_to_take * delta_y_;
-      current_step_ += steps_to_take;
-    }
+  if (!pyramid_sequence_) {
+    done();
+    return *this;
   }
 
-  // Once we enter the around rect, we're done.
-  if (in_around_rect())
-    done();
+  index_x_ = pyramid_sequence_.index_x();
+  index_y_ = pyramid_sequence_.index_y();
+  DCHECK(in_consider_rect() && !in_ignore_rect());
   return *this;
 }
 
-bool TilingData::ReverseSpiralDifferenceIterator::needs_direction_switch()
-    const {
-  return current_step_ >= current_step_count();
-}
-
-void TilingData::ReverseSpiralDifferenceIterator::switch_direction() {
-  // Note that delta_x_ and delta_y_ always remain between -1 and 1.
-  int new_delta_y_ = delta_x_;
-  delta_x_ = -delta_y_;
-  delta_y_ = new_delta_y_;
-
-  current_step_ = 0;
-  direction_ = static_cast<Direction>((direction_ + 1) % 4);
-
-  if (direction_ == UP || direction_ == DOWN) {
-    --vertical_step_count_;
-    --horizontal_step_count_;
-
-    // We should always end up in an around rect at some point.
-    // Since the direction is now vertical, we have to ensure that we will
-    // advance.
-    DCHECK_GE(horizontal_step_count_, 1);
-    DCHECK_GE(vertical_step_count_, 1);
-  }
-}
-
 }  // namespace cc