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

cc/base/tiling_data.cc

Index: cc/base/tiling_data.cc
diff --git a/cc/base/tiling_data.cc b/cc/base/tiling_data.cc
index edfecc9a4f64b8794fa976dc0f1163defaa491b0..bcc4cc24a7a4d9eb0c5f9a001e7c2c0972f6936c 100644
--- a/cc/base/tiling_data.cc
+++ b/cc/base/tiling_data.cc
@@ -6,6 +6,8 @@
 
 #include <algorithm>
 
+#include "base/command_line.h"
+#include "cc/base/switches.h"
 #include "ui/gfx/geometry/rect.h"
 #include "ui/gfx/geometry/rect_f.h"
 #include "ui/gfx/geometry/vector2d.h"
@@ -92,6 +94,36 @@ int TilingData::TileYIndexFromSrcCoord(int src_position) const {
   return std::min(std::max(y, 0), num_tiles_y_ - 1);
 }
 
+int TilingData::TileAbsoluteXIndexFromSrcCoord(int src_position) const {
+  int inner_tile_width = max_texture_size_.width() - 2 * border_texels_;
+  if (inner_tile_width <= 0)
+    return 0;
+
+  int max_width = inner_tile_width * num_tiles_x_ + 2 * border_texels_;
+  if (src_position >= 0 && src_position < max_width)
+    return TileXIndexFromSrcCoord(src_position);
+
+  if (src_position >= max_width)
+    return num_tiles_x_ + (src_position - max_width) / inner_tile_width;
+
+  return (src_position + 1) / inner_tile_width - 1;
+}
+
+int TilingData::TileAbsoluteYIndexFromSrcCoord(int src_position) const {
+  int inner_tile_height = max_texture_size_.height() - 2 * border_texels_;
+  if (inner_tile_height <= 0)
+    return 0;
+
+  int max_height = inner_tile_height * num_tiles_y_ + 2 * border_texels_;
+  if (src_position >= 0 && src_position < max_height)
+    return TileYIndexFromSrcCoord(src_position);
+
+  if (src_position >= max_height)
+    return num_tiles_y_ + (src_position - max_height) / inner_tile_height;
+
+  return (src_position + 1) / inner_tile_height - 1;
+}
+
 int TilingData::FirstBorderTileXIndexFromSrcCoord(int src_position) const {
   if (num_tiles_x_ <= 1)
     return 0;
@@ -176,6 +208,41 @@ IndexRect TilingData::TileAroundIndexRect(const gfx::Rect& center_rect) const {
   return IndexRect(around_left, around_right, around_top, around_bottom);
 }
 
+IndexRect TilingData::TileAroundAbsoluteIndexRect(
+    const gfx::Rect& center_rect) const {
+  if (center_rect.IsEmpty()) {
+    // Default around rect is assumed to be at top-left corner of tile at
+    // (0, 0).
+    return IndexRect(-2, 0, -2, 0);
+  }
+
+  gfx::Rect tiling_rect(tiling_size());
+
+  int around_left = TileAbsoluteXIndexFromSrcCoord(center_rect.x());
+  int around_top = TileAbsoluteYIndexFromSrcCoord(center_rect.y());
+  int right_src_coord = center_rect.right() - 1;
+  int around_right = TileAbsoluteXIndexFromSrcCoord(right_src_coord) + 1;
+  int bottom_src_coord = center_rect.bottom() - 1;
+  int around_bottom = TileAbsoluteYIndexFromSrcCoord(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 TileAbsolute(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;
+  }
+
+  return IndexRect(around_left, around_right, around_top, around_bottom);
+}
+
 gfx::Rect TilingData::ExpandRectIgnoringBordersToTileBounds(
     const gfx::Rect& rect) const {
   if (rect.IsEmpty() || has_empty_bounds())
@@ -349,6 +416,10 @@ void TilingData::RecomputeNumTiles() {
       max_texture_size_.height(), tiling_size_.height(), border_texels_);
 }
 
+bool TilingData::IsPyramidSequenceEnabled() {
+  return true;
+}
+
 TilingData::BaseIterator::BaseIterator() : index_x_(-1), index_y_(-1) {
 }
 
@@ -535,39 +606,90 @@ 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) {
+    const gfx::Rect& center_rect,
+    const bool use_pyramid_sequence)
+    : BaseDifferenceIterator(tiling_data, consider_rect, ignore_rect),
+      use_pyramid_sequence_(use_pyramid_sequence) {
   if (!HasConsiderRect()) {
     done();
     return;
   }
 
-  IndexRect around_index_rect = tiling_data->TileAroundIndexRect(center_rect);
-  DCHECK(around_index_rect.is_valid());
+  if (use_pyramid_sequence_) {
+    IndexRect around_index_rect =
+        tiling_data->TileAroundAbsoluteIndexRect(center_rect);
 
-  spiral_iterator_ = SpiralIterator(around_index_rect, consider_index_rect_,
-                                    ignore_index_rect_);
+    DCHECK(around_index_rect.is_valid());
+    pyramid_sequence_ = PyramidSequence(
+        around_index_rect, consider_index_rect_, ignore_index_rect_,
+        tiling_data->max_texture_size().width(),
+        tiling_data->max_texture_size().height());
 
-  if (!spiral_iterator_) {
-    done();
-    return;
-  }
+    iterator_ = pyramid_sequence_.Begin();
+
+    if (!iterator_) {
+      done();
+      return;
+    }
+
+    index_x_ = iterator_.index_x();
+    index_y_ = iterator_.index_y();
+    DCHECK(consider_index_rect_.Contains(index_x_, index_y_) &&
+           !ignore_index_rect_.Contains(index_x_, index_y_));
+  } else {
+    IndexRect around_index_rect = tiling_data->TileAroundIndexRect(center_rect);
+    DCHECK(around_index_rect.is_valid());
+
+    spiral_iterator_ = SpiralIterator(around_index_rect, consider_index_rect_,
+                                      ignore_index_rect_);
 
-  index_x_ = spiral_iterator_.index_x();
-  index_y_ = spiral_iterator_.index_y();
+    if (!spiral_iterator_) {
+      done();
+      return;
+    }
+
+    index_x_ = spiral_iterator_.index_x();
+    index_y_ = spiral_iterator_.index_y();
+  }
 }
 
+TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
+    const TilingData::SpiralDifferenceIterator& other) = default;
+
+TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
+    TilingData::SpiralDifferenceIterator&& other) = default;
+
+TilingData::SpiralDifferenceIterator::~SpiralDifferenceIterator() {}
+
+TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
+operator=(const TilingData::SpiralDifferenceIterator& other) = default;
+
+TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
+operator=(TilingData::SpiralDifferenceIterator&& other) = default;
+
 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
 operator++() {
-  ++spiral_iterator_;
+  if (use_pyramid_sequence_) {
+    ++iterator_;
 
-  if (!spiral_iterator_) {
-    done();
-    return *this;
-  }
+    if (!iterator_) {
+      done();
+      return *this;
+    }
+
+    index_x_ = iterator_.index_x();
+    index_y_ = iterator_.index_y();
+  } else {
+    ++spiral_iterator_;
+
+    if (!spiral_iterator_) {
+      done();
+      return *this;
+    }
 
-  index_x_ = spiral_iterator_.index_x();
-  index_y_ = spiral_iterator_.index_y();
+    index_x_ = spiral_iterator_.index_x();
+    index_y_ = spiral_iterator_.index_y();
+  }
 
   return *this;
 }
@@ -580,40 +702,93 @@ 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) {
+    const gfx::Rect& center_rect,
+    const bool use_pyramid_sequence)
+    : BaseDifferenceIterator(tiling_data, consider_rect, ignore_rect),
+      use_pyramid_sequence_(use_pyramid_sequence) {
   if (!HasConsiderRect()) {
     done();
     return;
   }
 
-  IndexRect around_index_rect = tiling_data->TileAroundIndexRect(center_rect);
-  DCHECK(around_index_rect.is_valid());
+  if (use_pyramid_sequence_) {
+    IndexRect around_index_rect =
+        tiling_data->TileAroundAbsoluteIndexRect(center_rect);
+    DCHECK(around_index_rect.is_valid());
+    pyramid_sequence_ = PyramidSequence(
+        around_index_rect, consider_index_rect_, ignore_index_rect_,
+        tiling_data->max_texture_size().width(),
+        tiling_data->max_texture_size().height());
 
-  reverse_spiral_iterator_ = ReverseSpiralIterator(
-      around_index_rect, consider_index_rect_, ignore_index_rect_);
+    reverse_iterator_ = pyramid_sequence_.ReverseBegin();
 
-  if (!reverse_spiral_iterator_) {
-    done();
-    return;
-  }
+    if (!reverse_iterator_) {
+      done();
+      return;
+    }
+
+    index_x_ = reverse_iterator_.index_x();
+    index_y_ = reverse_iterator_.index_y();
+    DCHECK(consider_index_rect_.Contains(index_x_, index_y_) &&
+           !ignore_index_rect_.Contains(index_x_, index_y_));
+  } else {
+    IndexRect around_index_rect = tiling_data->TileAroundIndexRect(center_rect);
+    DCHECK(around_index_rect.is_valid());
+
+    reverse_spiral_iterator_ = ReverseSpiralIterator(
+        around_index_rect, consider_index_rect_, ignore_index_rect_);
+
+    if (!reverse_spiral_iterator_) {
+      done();
+      return;
+    }
 
-  index_x_ = reverse_spiral_iterator_.index_x();
-  index_y_ = reverse_spiral_iterator_.index_y();
+    index_x_ = reverse_spiral_iterator_.index_x();
+    index_y_ = reverse_spiral_iterator_.index_y();
+  }
 }
 
+TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
+    const TilingData::ReverseSpiralDifferenceIterator& other) = default;
+
+TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
+    TilingData::ReverseSpiralDifferenceIterator&& other) = default;
+
+TilingData::ReverseSpiralDifferenceIterator::
+    ~ReverseSpiralDifferenceIterator() {}
+
+TilingData::ReverseSpiralDifferenceIterator&
+TilingData::ReverseSpiralDifferenceIterator::operator=(
+    const TilingData::ReverseSpiralDifferenceIterator& other) = default;
+
+TilingData::ReverseSpiralDifferenceIterator&
+TilingData::ReverseSpiralDifferenceIterator::operator=(
+    TilingData::ReverseSpiralDifferenceIterator&& other) = default;
+
 TilingData::ReverseSpiralDifferenceIterator&
     TilingData::ReverseSpiralDifferenceIterator::
     operator++() {
-  ++reverse_spiral_iterator_;
+  if (use_pyramid_sequence_) {
+    ++reverse_iterator_;
 
-  if (!reverse_spiral_iterator_) {
-    done();
-    return *this;
-  }
+    if (!reverse_iterator_) {
+      done();
+      return *this;
+    }
 
-  index_x_ = reverse_spiral_iterator_.index_x();
-  index_y_ = reverse_spiral_iterator_.index_y();
+    index_x_ = reverse_iterator_.index_x();
+    index_y_ = reverse_iterator_.index_y();
+  } else {
+    ++reverse_spiral_iterator_;
+
+    if (!reverse_spiral_iterator_) {
+      done();
+      return *this;
+    }
+
+    index_x_ = reverse_spiral_iterator_.index_x();
+    index_y_ = reverse_spiral_iterator_.index_y();
+  }
 
   return *this;
 }