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 449 matching lines @@
       }
     }
 
     if (index_y_ > consider_bottom_)
       done();
   }
 
   return *this;
 }
 
+TilingData::LDSequence::LDSequence(PyramidSequence traversal_seq,
+                                   PyramidSequence level_seq,
+                                   bool swapped,
+                                   int distance)
+    : traversal_seq_(traversal_seq), swapped_(swapped) {
+  LevelDistance level_distance;
+  level_distance.distance = 0;
+  int coverage = level_seq.GetCoverage();
+  for (int i = 0; i < coverage; ++i, level_distance.distance += distance) {
+    level_distance.level = level_seq.GetCurrent();
+    level_distances_.push_back(level_distance);
+    level_seq.Advance();
+  }
+
+  if (IsValid())
+    Reset();
+}
+
+TilingData::LDSequence::LDSequence(const TilingData::LDSequence& other) =
+    default;
+
+TilingData::LDSequence::~LDSequence() = default;
+
+int TilingData::LDSequence::GetIndexX() const {
+  return swapped_ ? current_level_index_ : current_seq_index_;
+}
+
+int TilingData::LDSequence::GetIndexY() const {
+  return swapped_ ? current_seq_index_ : current_level_index_;
+}
+
+int TilingData::LDSequence::GetTopDistance() {
+  DCHECK(level_distances_.size());
+  return level_distances_.front().distance;
+}
+
+bool TilingData::LDSequence::Advance() {
+  traversal_seq_.Advance();
+  if (!traversal_seq_.within_bounds()) {
+    level_distances_.erase(level_distances_.begin());
+    if (IsValid())
+      Reset();
+
+    return false;
+  }
+
+  current_seq_index_ = traversal_seq_.GetCurrent();
+  return true;
+}
+
+void TilingData::LDSequence::Reset() {
+  DCHECK(level_distances_.size());
+  current_seq_index_ = traversal_seq_.GetCurrent();
+  current_level_index_ = level_distances_.front().level;
+}
+
 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;
   }
 
+  num_tiles_x_ = tiling_data->num_tiles_x();
+  num_tiles_y_ = tiling_data->num_tiles_y();
   // 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.
@@ skipping 20 matching lines @@
   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);
   }
 
-  vertical_step_count_ = around_bottom - around_top + 1;
-  horizontal_step_count_ = around_right - around_left + 1;
-  current_step_ = horizontal_step_count_ - 1;
+  int left_levels = around_left - consider_left_ + 1;
+  int right_levels = consider_right_ - around_right + 1;
+  int top_levels = around_top - consider_top_ + 1;
+  int bottom_levels = consider_bottom_ - around_bottom + 1;
 
-  index_x_ = around_right;
-  index_y_ = around_bottom;
+  int width = tiling_data->max_texture_size().width();
+  int height = tiling_data->max_texture_size().height();
+  int hypotenuse = std::sqrt(width * width + height * height);  // support sp/dp
 
-  // The current index is the bottom right of the around rect, which is also
-  // ignored. So we have to advance.
+  // U
+  int start = around_bottom - 1;
+  int end = around_top + 1;
+  if (right_levels > 0 && valid_row(start) && valid_row(end)) {
+    ld_sequences_.push_back(TilingData::LDSequence(
+        PyramidSequence(PyramidSequence::Type::BACKWARD, start, end,
+                        right_levels),
+        PyramidSequence(PyramidSequence::Type::FORWARD, around_right,
+                        consider_right_, 1),
+        true, width));
+  }
+
+  // UL

[vmpstr, 2016/06/16 18:28:58]

Expand comments please.

+  if (right_levels > 0 && top_levels > 0 && valid_column(around_right)) {
+    ld_sequences_.push_back(TilingData::LDSequence(
+        PyramidSequence(PyramidSequence::Type::DIAGONAL_FORWARD, around_right,
+                        around_right, std::min(right_levels, top_levels)),
+        PyramidSequence(PyramidSequence::Type::BACKWARD, around_top,
+                        consider_top_, 1),
+        false, hypotenuse));
+  }
+
+  // L
+  start = around_right - 1;
+  end = around_left + 1;
+  if (top_levels > 0 && valid_column(start) && valid_column(end)) {
+    ld_sequences_.push_back(
+        TilingData::LDSequence(PyramidSequence(PyramidSequence::Type::BACKWARD,
+                                               start, end, top_levels),
+                               PyramidSequence(PyramidSequence::Type::BACKWARD,
+                                               around_top, consider_top_, 1),
+                               false, height));
+  }
+
+  // LD
+  if (top_levels > 0 && left_levels > 0 && valid_column(around_left)) {
+    ld_sequences_.push_back(TilingData::LDSequence(
+        PyramidSequence(PyramidSequence::Type::DIAGONAL_BACKWARD, around_left,
+                        around_left, std::min(top_levels, left_levels)),
+        PyramidSequence(PyramidSequence::Type::BACKWARD, around_top,
+                        consider_top_, 1),
+        false, hypotenuse));
+  }
+
+  // D
+  start = around_top + 1;
+  end = around_bottom - 1;
+  if (left_levels > 0 && valid_row(start) && valid_row(end)) {
+    ld_sequences_.push_back(
+        TilingData::LDSequence(PyramidSequence(PyramidSequence::Type::FORWARD,
+                                               start, end, left_levels),
+                               PyramidSequence(PyramidSequence::Type::BACKWARD,
+                                               around_left, consider_left_, 1),
+                               true, width));
+  }
+
+  // DR
+  if (left_levels > 0 && bottom_levels > 0 && valid_column(around_left)) {
+    ld_sequences_.push_back(TilingData::LDSequence(
+        PyramidSequence(PyramidSequence::Type::DIAGONAL_BACKWARD, around_left,
+                        around_left, std::min(left_levels, bottom_levels)),
+        PyramidSequence(PyramidSequence::Type::FORWARD, around_bottom,
+                        consider_bottom_, 1),
+        false, hypotenuse));
+  }
+
+  // R
+  start = around_left + 1;
+  end = around_right - 1;
+  if (bottom_levels > 0 && valid_column(start) && valid_column(end)) {
+    ld_sequences_.push_back(TilingData::LDSequence(
+        PyramidSequence(PyramidSequence::Type::FORWARD, start, end,
+                        bottom_levels),
+        PyramidSequence(PyramidSequence::Type::FORWARD, around_bottom,
+                        consider_bottom_, 1),
+        false, height));
+  }
+
+  // RU
+  if (bottom_levels > 0 && right_levels > 0 && valid_column(around_right)) {
+    ld_sequences_.push_back(TilingData::LDSequence(
+        PyramidSequence(PyramidSequence::Type::DIAGONAL_FORWARD, around_right,
+                        around_right, std::min(bottom_levels, right_levels)),
+        PyramidSequence(PyramidSequence::Type::FORWARD, around_bottom,
+                        consider_bottom_, 1),
+        false, hypotenuse));
+  }
+
+  // Point to valid ld sequence.
+  current_ld_seq = GetNextLDSequence();
+
+  if (current_ld_seq == ld_sequences_.end()) {
+    done();
+    return;
+  }
+
+  // Point to valid indices or finish.
   ++(*this);
 }
 
+TilingData::SpiralDifferenceIterator::~SpiralDifferenceIterator() = default;
+
 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
 operator++() {
-  int cannot_hit_consider_count = 0;
-  while (cannot_hit_consider_count < 4) {
-    if (needs_direction_switch())
-      switch_direction();
+  while (true) {
+    if (current_ld_seq == ld_sequences_.end()) {
+      done();
+      break;  // Finished.
+    }
 
-    index_x_ += delta_x_;
-    index_y_ += delta_y_;
-    ++current_step_;
+    DCHECK(current_ld_seq->IsValid());
+    index_x_ = current_ld_seq->GetIndexX();
+    index_y_ = current_ld_seq->GetIndexY();
 
-    if (in_consider_rect()) {
-      cannot_hit_consider_count = 0;
+    if (in_consider_rect() && !in_ignore_rect())
+      break;  // Got it.
 
-      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 (!current_ld_seq->Advance())
+      current_ld_seq = GetNextLDSequence();
   }
-
-  if (cannot_hit_consider_count >= 4)
-    done();
   return *this;
 }
 
-bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
-  return current_step_ >= current_step_count();
-}
+TilingData::LDSequence::List::iterator
+TilingData::SpiralDifferenceIterator::GetNextLDSequence() {
+  ld_sequences_.erase(std::remove_if(ld_sequences_.begin(), ld_sequences_.end(),
+                                     [](const TilingData::LDSequence& path) {
+                                       return !path.IsValid();
+                                     }),
+                      ld_sequences_.end());
 
-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_;
+  if (!ld_sequences_.size())
+    return ld_sequences_.end();
 
-  current_step_ = 0;
-  direction_ = static_cast<Direction>((direction_ + 1) % 4);
+  TilingData::LDSequence::List::iterator min_distance_ld_seq_it =
+      ld_sequences_.begin();
 
-  if (direction_ == RIGHT || direction_ == LEFT) {
-    ++vertical_step_count_;
-    ++horizontal_step_count_;
+  for (TilingData::LDSequence::List::iterator it = ld_sequences_.begin();
+       it != ld_sequences_.end(); ++it) {
+    int distance = it->GetTopDistance();
+    if (distance == 0)
+      return it;
+
+    if (min_distance_ld_seq_it->GetTopDistance() > distance)
+      min_distance_ld_seq_it = it;
   }
+
+  return min_distance_ld_seq_it;
 }
 
 TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator() {
   done();
 }
 
 TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
     const TilingData* tiling_data,
     const gfx::Rect& consider_rect,
     const gfx::Rect& ignore_rect,
@@ skipping 199 matching lines @@
 
     // 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