cc/base/tiling_data.cc

   1 // Copyright 2010 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "cc/base/tiling_data.h"
   6
   7 #include <algorithm>
   8
   9 #include "ui/gfx/geometry/rect.h"
  10 #include "ui/gfx/geometry/vector2d.h"
  11
  12 namespace cc {
  13
  14 static int ComputeNumTiles(int max_texture_size,
  15                            int total_size,
  16                            int border_texels) {
  17   if (max_texture_size - 2 * border_texels <= 0)
  18     return total_size > 0 && max_texture_size >= total_size ? 1 : 0;
  19
  20   int num_tiles = std::max(1,
  21                            1 + (total_size - 1 - 2 * border_texels) /
  22                            (max_texture_size - 2 * border_texels));
  23   return total_size > 0 ? num_tiles : 0;
  24 }
  25
  26 TilingData::TilingData()
  27     : border_texels_(0) {
  28   RecomputeNumTiles();
  29 }
  30
  31 TilingData::TilingData(const gfx::Size& max_texture_size,
  32                        const gfx::Size& tiling_size,
  33                        bool has_border_texels)
  34     : max_texture_size_(max_texture_size),
  35       tiling_size_(tiling_size),
  36       border_texels_(has_border_texels ? 1 : 0) {
  37   RecomputeNumTiles();
  38 }
  39
  40 TilingData::TilingData(const gfx::Size& max_texture_size,
  41                        const gfx::Size& tiling_size,
  42                        int border_texels)
  43     : max_texture_size_(max_texture_size),
  44       tiling_size_(tiling_size),
  45       border_texels_(border_texels) {
  46   RecomputeNumTiles();
  47 }
  48
  49 void TilingData::SetTilingSize(const gfx::Size& tiling_size) {
  50   tiling_size_ = tiling_size;
  51   RecomputeNumTiles();
  52 }
  53
  54 void TilingData::SetMaxTextureSize(const gfx::Size& max_texture_size) {
  55   max_texture_size_ = max_texture_size;
  56   RecomputeNumTiles();
  57 }
  58
  59 void TilingData::SetHasBorderTexels(bool has_border_texels) {
  60   border_texels_ = has_border_texels ? 1 : 0;
  61   RecomputeNumTiles();
  62 }
  63
  64 void TilingData::SetBorderTexels(int border_texels) {
  65   border_texels_ = border_texels;
  66   RecomputeNumTiles();
  67 }
  68
  69 int TilingData::TileXIndexFromSrcCoord(int src_position) const {
  70   if (num_tiles_x_ <= 1)
  71     return 0;
  72
  73   DCHECK_GT(max_texture_size_.width() - 2 * border_texels_, 0);
  74   int x = (src_position - border_texels_) /
  75       (max_texture_size_.width() - 2 * border_texels_);
  76   return std::min(std::max(x, 0), num_tiles_x_ - 1);
  77 }
  78
  79 int TilingData::TileYIndexFromSrcCoord(int src_position) const {
  80   if (num_tiles_y_ <= 1)
  81     return 0;
  82
  83   DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0);
  84   int y = (src_position - border_texels_) /
  85       (max_texture_size_.height() - 2 * border_texels_);
  86   return std::min(std::max(y, 0), num_tiles_y_ - 1);
  87 }
  88
  89 int TilingData::FirstBorderTileXIndexFromSrcCoord(int src_position) const {
  90   if (num_tiles_x_ <= 1)
  91     return 0;
  92
  93   DCHECK_GT(max_texture_size_.width() - 2 * border_texels_, 0);
  94   int inner_tile_size = max_texture_size_.width() - 2 * border_texels_;
  95   int x = (src_position - 2 * border_texels_) / inner_tile_size;
  96   return std::min(std::max(x, 0), num_tiles_x_ - 1);
  97 }
  98
  99 int TilingData::FirstBorderTileYIndexFromSrcCoord(int src_position) const {
 100   if (num_tiles_y_ <= 1)
 101     return 0;
 102
 103   DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0);
 104   int inner_tile_size = max_texture_size_.height() - 2 * border_texels_;
 105   int y = (src_position - 2 * border_texels_) / inner_tile_size;
 106   return std::min(std::max(y, 0), num_tiles_y_ - 1);
 107 }
 108
 109 int TilingData::LastBorderTileXIndexFromSrcCoord(int src_position) const {
 110   if (num_tiles_x_ <= 1)
 111     return 0;
 112
 113   DCHECK_GT(max_texture_size_.width() - 2 * border_texels_, 0);
 114   int inner_tile_size = max_texture_size_.width() - 2 * border_texels_;
 115   int x = src_position / inner_tile_size;
 116   return std::min(std::max(x, 0), num_tiles_x_ - 1);
 117 }
 118
 119 int TilingData::LastBorderTileYIndexFromSrcCoord(int src_position) const {
 120   if (num_tiles_y_ <= 1)
 121     return 0;
 122
 123   DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0);
 124   int inner_tile_size = max_texture_size_.height() - 2 * border_texels_;
 125   int y = src_position / inner_tile_size;
 126   return std::min(std::max(y, 0), num_tiles_y_ - 1);
 127 }
 128
 129 gfx::Rect TilingData::ExpandRectIgnoringBordersToTileBounds(
 130     const gfx::Rect& rect) const {
 131   if (rect.IsEmpty() || has_empty_bounds())
 132     return gfx::Rect();
 133   if (rect.x() > tiling_size_.width() || rect.y() > tiling_size_.height())
 134     return gfx::Rect();
 135   int index_x = TileXIndexFromSrcCoord(rect.x());
 136   int index_y = TileYIndexFromSrcCoord(rect.y());
 137   int index_right = TileXIndexFromSrcCoord(rect.right() - 1);
 138   int index_bottom = TileYIndexFromSrcCoord(rect.bottom() - 1);
 139
 140   gfx::Rect rect_top_left(TileBounds(index_x, index_y));
 141   gfx::Rect rect_bottom_right(TileBounds(index_right, index_bottom));
 142
 143   return gfx::UnionRects(rect_top_left, rect_bottom_right);
 144 }
 145
 146 gfx::Rect TilingData::ExpandRectToTileBounds(const gfx::Rect& rect) const {
 147   if (rect.IsEmpty() || has_empty_bounds())
 148     return gfx::Rect();
 149   if (rect.x() > tiling_size_.width() || rect.y() > tiling_size_.height())
 150     return gfx::Rect();
 151   int index_x = FirstBorderTileXIndexFromSrcCoord(rect.x());
 152   int index_y = FirstBorderTileYIndexFromSrcCoord(rect.y());
 153   int index_right = LastBorderTileXIndexFromSrcCoord(rect.right() - 1);
 154   int index_bottom = LastBorderTileYIndexFromSrcCoord(rect.bottom() - 1);
 155
 156   gfx::Rect rect_top_left(TileBounds(index_x, index_y));
 157   gfx::Rect rect_bottom_right(TileBounds(index_right, index_bottom));
 158
 159   return gfx::UnionRects(rect_top_left, rect_bottom_right);
 160 }
 161
 162 gfx::Rect TilingData::TileBounds(int i, int j) const {
 163   AssertTile(i, j);
 164   int max_texture_size_x = max_texture_size_.width() - 2 * border_texels_;
 165   int max_texture_size_y = max_texture_size_.height() - 2 * border_texels_;
 166
 167   int lo_x = max_texture_size_x * i;
 168   if (i != 0)
 169     lo_x += border_texels_;
 170
 171   int lo_y = max_texture_size_y * j;
 172   if (j != 0)
 173     lo_y += border_texels_;
 174
 175   int hi_x = max_texture_size_x * (i + 1) + border_texels_;
 176   if (i + 1 == num_tiles_x_)
 177     hi_x += border_texels_;
 178
 179   int hi_y = max_texture_size_y * (j + 1) + border_texels_;
 180   if (j + 1 == num_tiles_y_)
 181     hi_y += border_texels_;
 182
 183   hi_x = std::min(hi_x, tiling_size_.width());
 184   hi_y = std::min(hi_y, tiling_size_.height());
 185
 186   int x = lo_x;
 187   int y = lo_y;
 188   int width = hi_x - lo_x;
 189   int height = hi_y - lo_y;
 190   DCHECK_GE(x, 0);
 191   DCHECK_GE(y, 0);
 192   DCHECK_GE(width, 0);
 193   DCHECK_GE(height, 0);
 194   DCHECK_LE(x, tiling_size_.width());
 195   DCHECK_LE(y, tiling_size_.height());
 196   return gfx::Rect(x, y, width, height);
 197 }
 198
 199 gfx::Rect TilingData::TileBoundsWithBorder(int i, int j) const {
 200   AssertTile(i, j);
 201   int max_texture_size_x = max_texture_size_.width() - 2 * border_texels_;
 202   int max_texture_size_y = max_texture_size_.height() - 2 * border_texels_;
 203
 204   int lo_x = max_texture_size_x * i;
 205   int lo_y = max_texture_size_y * j;
 206
 207   int hi_x = lo_x + max_texture_size_x + 2 * border_texels_;
 208   int hi_y = lo_y + max_texture_size_y + 2 * border_texels_;
 209
 210   hi_x = std::min(hi_x, tiling_size_.width());
 211   hi_y = std::min(hi_y, tiling_size_.height());
 212
 213   int x = lo_x;
 214   int y = lo_y;
 215   int width = hi_x - lo_x;
 216   int height = hi_y - lo_y;
 217   DCHECK_GE(x, 0);
 218   DCHECK_GE(y, 0);
 219   DCHECK_GE(width, 0);
 220   DCHECK_GE(height, 0);
 221   DCHECK_LE(x, tiling_size_.width());
 222   DCHECK_LE(y, tiling_size_.height());
 223   return gfx::Rect(x, y, width, height);
 224 }
 225
 226 int TilingData::TilePositionX(int x_index) const {
 227   DCHECK_GE(x_index, 0);
 228   DCHECK_LT(x_index, num_tiles_x_);
 229
 230   int pos = (max_texture_size_.width() - 2 * border_texels_) * x_index;
 231   if (x_index != 0)
 232     pos += border_texels_;
 233
 234   return pos;
 235 }
 236
 237 int TilingData::TilePositionY(int y_index) const {
 238   DCHECK_GE(y_index, 0);
 239   DCHECK_LT(y_index, num_tiles_y_);
 240
 241   int pos = (max_texture_size_.height() - 2 * border_texels_) * y_index;
 242   if (y_index != 0)
 243     pos += border_texels_;
 244
 245   return pos;
 246 }
 247
 248 int TilingData::TileSizeX(int x_index) const {
 249   DCHECK_GE(x_index, 0);
 250   DCHECK_LT(x_index, num_tiles_x_);
 251
 252   if (!x_index && num_tiles_x_ == 1)
 253     return tiling_size_.width();
 254   if (!x_index && num_tiles_x_ > 1)
 255     return max_texture_size_.width() - border_texels_;
 256   if (x_index < num_tiles_x_ - 1)
 257     return max_texture_size_.width() - 2 * border_texels_;
 258   if (x_index == num_tiles_x_ - 1)
 259     return tiling_size_.width() - TilePositionX(x_index);
 260
 261   NOTREACHED();
 262   return 0;
 263 }
 264
 265 int TilingData::TileSizeY(int y_index) const {
 266   DCHECK_GE(y_index, 0);
 267   DCHECK_LT(y_index, num_tiles_y_);
 268
 269   if (!y_index && num_tiles_y_ == 1)
 270     return tiling_size_.height();
 271   if (!y_index && num_tiles_y_ > 1)
 272     return max_texture_size_.height() - border_texels_;
 273   if (y_index < num_tiles_y_ - 1)
 274     return max_texture_size_.height() - 2 * border_texels_;
 275   if (y_index == num_tiles_y_ - 1)
 276     return tiling_size_.height() - TilePositionY(y_index);
 277
 278   NOTREACHED();
 279   return 0;
 280 }
 281
 282 gfx::Vector2d TilingData::TextureOffset(int x_index, int y_index) const {
 283   int left = (!x_index || num_tiles_x_ == 1) ? 0 : border_texels_;
 284   int top = (!y_index || num_tiles_y_ == 1) ? 0 : border_texels_;
 285
 286   return gfx::Vector2d(left, top);
 287 }
 288
 289 void TilingData::RecomputeNumTiles() {
 290   num_tiles_x_ = ComputeNumTiles(
 291       max_texture_size_.width(), tiling_size_.width(), border_texels_);
 292   num_tiles_y_ = ComputeNumTiles(
 293       max_texture_size_.height(), tiling_size_.height(), border_texels_);
 294 }
 295
 296 TilingData::BaseIterator::BaseIterator(const TilingData* tiling_data)
 297     : tiling_data_(tiling_data),
 298       index_x_(-1),
 299       index_y_(-1) {
 300 }
 301
 302 TilingData::Iterator::Iterator() : BaseIterator(nullptr) { done(); }
 303
 304 TilingData::Iterator::Iterator(const TilingData* tiling_data,
 305                                const gfx::Rect& consider_rect,
 306                                bool include_borders)
 307     : BaseIterator(tiling_data), left_(-1), right_(-1), bottom_(-1) {
 308   if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
 309     done();
 310     return;
 311   }
 312
 313   gfx::Rect tiling_bounds_rect(tiling_data_->tiling_size());
 314   gfx::Rect rect(consider_rect);
 315   rect.Intersect(tiling_bounds_rect);
 316
 317   gfx::Rect top_left_tile;
 318   if (include_borders) {
 319     index_x_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(rect.x());
 320     index_y_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(rect.y());
 321     right_ = tiling_data_->LastBorderTileXIndexFromSrcCoord(rect.right() - 1);
 322     bottom_ = tiling_data_->LastBorderTileYIndexFromSrcCoord(rect.bottom() - 1);
 323     top_left_tile = tiling_data_->TileBoundsWithBorder(index_x_, index_y_);
 324   } else {
 325     index_x_ = tiling_data_->TileXIndexFromSrcCoord(rect.x());
 326     index_y_ = tiling_data_->TileYIndexFromSrcCoord(rect.y());
 327     right_ = tiling_data_->TileXIndexFromSrcCoord(rect.right() - 1);
 328     bottom_ = tiling_data_->TileYIndexFromSrcCoord(rect.bottom() - 1);
 329     top_left_tile = tiling_data_->TileBounds(index_x_, index_y_);
 330   }
 331   left_ = index_x_;
 332
 333   // Index functions always return valid indices, so explicitly check
 334   // for non-intersecting rects.
 335   if (!top_left_tile.Intersects(rect))
 336     done();
 337 }
 338
 339 TilingData::Iterator& TilingData::Iterator::operator++() {
 340   if (!*this)
 341     return *this;
 342
 343   index_x_++;
 344   if (index_x_ > right_) {
 345     index_x_ = left_;
 346     index_y_++;
 347     if (index_y_ > bottom_)
 348       done();
 349   }
 350
 351   return *this;
 352 }
 353
 354 TilingData::DifferenceIterator::DifferenceIterator(
 355     const TilingData* tiling_data,
 356     const gfx::Rect& consider_rect,
 357     const gfx::Rect& ignore_rect)
 358     : BaseIterator(tiling_data),
 359       consider_left_(-1),
 360       consider_top_(-1),
 361       consider_right_(-1),
 362       consider_bottom_(-1),
 363       ignore_left_(-1),
 364       ignore_top_(-1),
 365       ignore_right_(-1),
 366       ignore_bottom_(-1) {
 367   if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
 368     done();
 369     return;
 370   }
 371
 372   gfx::Rect tiling_bounds_rect(tiling_data_->tiling_size());
 373   gfx::Rect consider(consider_rect);
 374   gfx::Rect ignore(ignore_rect);
 375   consider.Intersect(tiling_bounds_rect);
 376   ignore.Intersect(tiling_bounds_rect);
 377   if (consider.IsEmpty()) {
 378     done();
 379     return;
 380   }
 381
 382   consider_left_ = tiling_data_->TileXIndexFromSrcCoord(consider.x());
 383   consider_top_ = tiling_data_->TileYIndexFromSrcCoord(consider.y());
 384   consider_right_ = tiling_data_->TileXIndexFromSrcCoord(consider.right() - 1);
 385   consider_bottom_ =
 386       tiling_data_->TileYIndexFromSrcCoord(consider.bottom() - 1);
 387
 388   if (!ignore.IsEmpty()) {
 389     ignore_left_ = tiling_data_->TileXIndexFromSrcCoord(ignore.x());
 390     ignore_top_ = tiling_data_->TileYIndexFromSrcCoord(ignore.y());
 391     ignore_right_ = tiling_data_->TileXIndexFromSrcCoord(ignore.right() - 1);
 392     ignore_bottom_ = tiling_data_->TileYIndexFromSrcCoord(ignore.bottom() - 1);
 393
 394     // Clamp ignore indices to consider indices.
 395     ignore_left_ = std::max(ignore_left_, consider_left_);
 396     ignore_top_ = std::max(ignore_top_, consider_top_);
 397     ignore_right_ = std::min(ignore_right_, consider_right_);
 398     ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
 399   }
 400
 401   if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
 402       ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
 403     done();
 404     return;
 405   }
 406
 407   index_x_ = consider_left_;
 408   index_y_ = consider_top_;
 409
 410   if (in_ignore_rect())
 411     ++(*this);
 412 }
 413
 414 TilingData::DifferenceIterator& TilingData::DifferenceIterator::operator++() {
 415   if (!*this)
 416     return *this;
 417
 418   index_x_++;
 419   if (in_ignore_rect())
 420     index_x_ = ignore_right_ + 1;
 421
 422   if (index_x_ > consider_right_) {
 423     index_x_ = consider_left_;
 424     index_y_++;
 425
 426     if (in_ignore_rect()) {
 427       index_x_ = ignore_right_ + 1;
 428       // If the ignore rect spans the whole consider rect horizontally, then
 429       // ignore_right + 1 will be out of bounds.
 430       if (in_ignore_rect() || index_x_ > consider_right_) {
 431         index_y_ = ignore_bottom_ + 1;
 432         index_x_ = consider_left_;
 433       }
 434     }
 435
 436     if (index_y_ > consider_bottom_)
 437       done();
 438   }
 439
 440   return *this;
 441 }
 442
 443 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator()
 444     : BaseIterator(nullptr) {
 445   done();
 446 }
 447
 448 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
 449     const TilingData* tiling_data,
 450     const gfx::Rect& consider_rect,
 451     const gfx::Rect& ignore_rect,
 452     const gfx::Rect& center_rect)
 453     : BaseIterator(tiling_data),
 454       consider_left_(-1),
 455       consider_top_(-1),
 456       consider_right_(-1),
 457       consider_bottom_(-1),
 458       ignore_left_(-1),
 459       ignore_top_(-1),
 460       ignore_right_(-1),
 461       ignore_bottom_(-1),
 462       direction_(RIGHT),
 463       delta_x_(1),
 464       delta_y_(0),
 465       current_step_(0),
 466       horizontal_step_count_(0),
 467       vertical_step_count_(0) {
 468   if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
 469     done();
 470     return;
 471   }
 472
 473   gfx::Rect tiling_bounds_rect(tiling_data_->tiling_size());
 474   gfx::Rect consider(consider_rect);
 475   gfx::Rect ignore(ignore_rect);
 476   gfx::Rect center(center_rect);
 477   consider.Intersect(tiling_bounds_rect);
 478   ignore.Intersect(tiling_bounds_rect);
 479   if (consider.IsEmpty()) {
 480     done();
 481     return;
 482   }
 483
 484   consider_left_ = tiling_data_->TileXIndexFromSrcCoord(consider.x());
 485   consider_top_ = tiling_data_->TileYIndexFromSrcCoord(consider.y());
 486   consider_right_ = tiling_data_->TileXIndexFromSrcCoord(consider.right() - 1);
 487   consider_bottom_ =
 488       tiling_data_->TileYIndexFromSrcCoord(consider.bottom() - 1);
 489
 490   if (!ignore.IsEmpty()) {
 491     ignore_left_ = tiling_data_->TileXIndexFromSrcCoord(ignore.x());
 492     ignore_top_ = tiling_data_->TileYIndexFromSrcCoord(ignore.y());
 493     ignore_right_ = tiling_data_->TileXIndexFromSrcCoord(ignore.right() - 1);
 494     ignore_bottom_ = tiling_data_->TileYIndexFromSrcCoord(ignore.bottom() - 1);
 495
 496     // Clamp ignore indices to consider indices.
 497     ignore_left_ = std::max(ignore_left_, consider_left_);
 498     ignore_top_ = std::max(ignore_top_, consider_top_);
 499     ignore_right_ = std::min(ignore_right_, consider_right_);
 500     ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
 501   }
 502
 503   if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
 504       ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
 505     done();
 506     return;
 507   }
 508
 509   // Determine around left, such that it is between -1 and num_tiles_x.
 510   int around_left = 0;
 511   if (center.x() < 0 || center.IsEmpty())
 512     around_left = -1;
 513   else if (center.x() >= tiling_data->tiling_size().width())
 514     around_left = tiling_data->num_tiles_x();
 515   else
 516     around_left = tiling_data->TileXIndexFromSrcCoord(center.x());
 517
 518   // Determine around top, such that it is between -1 and num_tiles_y.
 519   int around_top = 0;
 520   if (center.y() < 0 || center.IsEmpty())
 521     around_top = -1;
 522   else if (center.y() >= tiling_data->tiling_size().height())
 523     around_top = tiling_data->num_tiles_y();
 524   else
 525     around_top = tiling_data->TileYIndexFromSrcCoord(center.y());
 526
 527   // Determine around right, such that it is between -1 and num_tiles_x.
 528   int right_src_coord = center.right() - 1;
 529   int around_right = 0;
 530   if (right_src_coord < 0 || center.IsEmpty()) {
 531     around_right = -1;
 532   } else if (right_src_coord >= tiling_data->tiling_size().width()) {
 533     around_right = tiling_data->num_tiles_x();
 534   } else {
 535     around_right = tiling_data->TileXIndexFromSrcCoord(right_src_coord);
 536   }
 537
 538   // Determine around bottom, such that it is between -1 and num_tiles_y.
 539   int bottom_src_coord = center.bottom() - 1;
 540   int around_bottom = 0;
 541   if (bottom_src_coord < 0 || center.IsEmpty()) {
 542     around_bottom = -1;
 543   } else if (bottom_src_coord >= tiling_data->tiling_size().height()) {
 544     around_bottom = tiling_data->num_tiles_y();
 545   } else {
 546     around_bottom = tiling_data->TileYIndexFromSrcCoord(bottom_src_coord);
 547   }
 548
 549   vertical_step_count_ = around_bottom - around_top + 1;
 550   horizontal_step_count_ = around_right - around_left + 1;
 551   current_step_ = horizontal_step_count_ - 1;
 552
 553   index_x_ = around_right;
 554   index_y_ = around_bottom;
 555
 556   // The current index is the bottom right of the around rect, which is also
 557   // ignored. So we have to advance.
 558   ++(*this);
 559 }
 560
 561 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
 562 operator++() {
 563   int cannot_hit_consider_count = 0;
 564   while (cannot_hit_consider_count < 4) {
 565     if (needs_direction_switch())
 566       switch_direction();
 567
 568     index_x_ += delta_x_;
 569     index_y_ += delta_y_;
 570     ++current_step_;
 571
 572     if (in_consider_rect()) {
 573       cannot_hit_consider_count = 0;
 574
 575       if (!in_ignore_rect())
 576         break;
 577
 578       // Steps needed to reach the very edge of the ignore rect, while remaining
 579       // inside (so that the continue would take us outside).
 580       int steps_to_edge = 0;
 581       switch (direction_) {
 582         case UP:
 583           steps_to_edge = index_y_ - ignore_top_;
 584           break;
 585         case LEFT:
 586           steps_to_edge = index_x_ - ignore_left_;
 587           break;
 588         case DOWN:
 589           steps_to_edge = ignore_bottom_ - index_y_;
 590           break;
 591         case RIGHT:
 592           steps_to_edge = ignore_right_ - index_x_;
 593           break;
 594       }
 595
 596       // We need to switch directions in |max_steps|.
 597       int max_steps = current_step_count() - current_step_;
 598
 599       int steps_to_take = std::min(steps_to_edge, max_steps);
 600       DCHECK_GE(steps_to_take, 0);
 601
 602       index_x_ += steps_to_take * delta_x_;
 603       index_y_ += steps_to_take * delta_y_;
 604       current_step_ += steps_to_take;
 605     } else {
 606       int max_steps = current_step_count() - current_step_;
 607       int steps_to_take = max_steps;
 608       bool can_hit_consider_rect = false;
 609       switch (direction_) {
 610         case UP:
 611           if (valid_column() && consider_bottom_ < index_y_)
 612             steps_to_take = index_y_ - consider_bottom_ - 1;
 613           can_hit_consider_rect |= consider_right_ >= index_x_;
 614           break;
 615         case LEFT:
 616           if (valid_row() && consider_right_ < index_x_)
 617             steps_to_take = index_x_ - consider_right_ - 1;
 618           can_hit_consider_rect |= consider_top_ <= index_y_;
 619           break;
 620         case DOWN:
 621           if (valid_column() && consider_top_ > index_y_)
 622             steps_to_take = consider_top_ - index_y_ - 1;
 623           can_hit_consider_rect |= consider_left_ <= index_x_;
 624           break;
 625         case RIGHT:
 626           if (valid_row() && consider_left_ > index_x_)
 627             steps_to_take = consider_left_ - index_x_ - 1;
 628           can_hit_consider_rect |= consider_bottom_ >= index_y_;
 629           break;
 630       }
 631       steps_to_take = std::min(steps_to_take, max_steps);
 632       DCHECK_GE(steps_to_take, 0);
 633
 634       index_x_ += steps_to_take * delta_x_;
 635       index_y_ += steps_to_take * delta_y_;
 636       current_step_ += steps_to_take;
 637
 638       if (can_hit_consider_rect)
 639         cannot_hit_consider_count = 0;
 640       else
 641         ++cannot_hit_consider_count;
 642     }
 643   }
 644
 645   if (cannot_hit_consider_count >= 4)
 646     done();
 647   return *this;
 648 }
 649
 650 bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
 651   return current_step_ >= current_step_count();
 652 }
 653
 654 void TilingData::SpiralDifferenceIterator::switch_direction() {
 655   // Note that delta_x_ and delta_y_ always remain between -1 and 1.
 656   int new_delta_x_ = delta_y_;
 657   delta_y_ = -delta_x_;
 658   delta_x_ = new_delta_x_;
 659
 660   current_step_ = 0;
 661   direction_ = static_cast<Direction>((direction_ + 1) % 4);
 662
 663   if (direction_ == RIGHT || direction_ == LEFT) {
 664     ++vertical_step_count_;
 665     ++horizontal_step_count_;
 666   }
 667 }
 668
 669 TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator()
 670     : BaseIterator(nullptr) {
 671   done();
 672 }
 673
 674 TilingData::ReverseSpiralDifferenceIterator::ReverseSpiralDifferenceIterator(
 675     const TilingData* tiling_data,
 676     const gfx::Rect& consider_rect,
 677     const gfx::Rect& ignore_rect,
 678     const gfx::Rect& center_rect)
 679     : BaseIterator(tiling_data),
 680       consider_left_(-1),
 681       consider_top_(-1),
 682       consider_right_(-1),
 683       consider_bottom_(-1),
 684       around_left_(-1),
 685       around_top_(-1),
 686       around_right_(-1),
 687       around_bottom_(-1),
 688       ignore_left_(-1),
 689       ignore_top_(-1),
 690       ignore_right_(-1),
 691       ignore_bottom_(-1),
 692       direction_(LEFT),
 693       delta_x_(-1),
 694       delta_y_(0),
 695       current_step_(0),
 696       horizontal_step_count_(0),
 697       vertical_step_count_(0) {
 698   if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
 699     done();
 700     return;
 701   }
 702
 703   gfx::Rect tiling_bounds_rect(tiling_data_->tiling_size());
 704   gfx::Rect consider(consider_rect);
 705   gfx::Rect ignore(ignore_rect);
 706   gfx::Rect center(center_rect);
 707   consider.Intersect(tiling_bounds_rect);
 708   ignore.Intersect(tiling_bounds_rect);
 709   if (consider.IsEmpty()) {
 710     done();
 711     return;
 712   }
 713
 714   consider_left_ = tiling_data_->TileXIndexFromSrcCoord(consider.x());
 715   consider_top_ = tiling_data_->TileYIndexFromSrcCoord(consider.y());
 716   consider_right_ = tiling_data_->TileXIndexFromSrcCoord(consider.right() - 1);
 717   consider_bottom_ =
 718       tiling_data_->TileYIndexFromSrcCoord(consider.bottom() - 1);
 719
 720   if (!ignore.IsEmpty()) {
 721     ignore_left_ = tiling_data_->TileXIndexFromSrcCoord(ignore.x());
 722     ignore_top_ = tiling_data_->TileYIndexFromSrcCoord(ignore.y());
 723     ignore_right_ = tiling_data_->TileXIndexFromSrcCoord(ignore.right() - 1);
 724     ignore_bottom_ = tiling_data_->TileYIndexFromSrcCoord(ignore.bottom() - 1);
 725
 726     // Clamp ignore indices to consider indices.
 727     ignore_left_ = std::max(ignore_left_, consider_left_);
 728     ignore_top_ = std::max(ignore_top_, consider_top_);
 729     ignore_right_ = std::min(ignore_right_, consider_right_);
 730     ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
 731   }
 732
 733   if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
 734       ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
 735     done();
 736     return;
 737   }
 738
 739   // Determine around left, such that it is between -1 and num_tiles_x.
 740   if (center.x() < 0 || center.IsEmpty())
 741     around_left_ = -1;
 742   else if (center.x() >= tiling_data->tiling_size().width())
 743     around_left_ = tiling_data->num_tiles_x();
 744   else
 745     around_left_ = tiling_data->TileXIndexFromSrcCoord(center.x());
 746
 747   // Determine around top, such that it is between -1 and num_tiles_y.
 748   if (center.y() < 0 || center.IsEmpty())
 749     around_top_ = -1;
 750   else if (center.y() >= tiling_data->tiling_size().height())
 751     around_top_ = tiling_data->num_tiles_y();
 752   else
 753     around_top_ = tiling_data->TileYIndexFromSrcCoord(center.y());
 754
 755   // Determine around right, such that it is between -1 and num_tiles_x.
 756   int right_src_coord = center.right() - 1;
 757   if (right_src_coord < 0 || center.IsEmpty()) {
 758     around_right_ = -1;
 759   } else if (right_src_coord >= tiling_data->tiling_size().width()) {
 760     around_right_ = tiling_data->num_tiles_x();
 761   } else {
 762     around_right_ = tiling_data->TileXIndexFromSrcCoord(right_src_coord);
 763   }
 764
 765   // Determine around bottom, such that it is between -1 and num_tiles_y.
 766   int bottom_src_coord = center.bottom() - 1;
 767   if (bottom_src_coord < 0 || center.IsEmpty()) {
 768     around_bottom_ = -1;
 769   } else if (bottom_src_coord >= tiling_data->tiling_size().height()) {
 770     around_bottom_ = tiling_data->num_tiles_y();
 771   } else {
 772     around_bottom_ = tiling_data->TileYIndexFromSrcCoord(bottom_src_coord);
 773   }
 774
 775   // Figure out the maximum distance from the around edge to consider edge.
 776   int max_distance = 0;
 777   max_distance = std::max(max_distance, around_top_ - consider_top_);
 778   max_distance = std::max(max_distance, around_left_ - consider_left_);
 779   max_distance = std::max(max_distance, consider_bottom_ - around_bottom_);
 780   max_distance = std::max(max_distance, consider_right_ - around_right_);
 781
 782   // The step count is the length of the edge (around_right_ - around_left_ + 1)
 783   // plus twice the max distance to pad (to the right and to the left). This way
 784   // the initial rect is the size proportional to the center, but big enough
 785   // to cover the consider rect.
 786   //
 787   // C = consider rect
 788   // A = around rect
 789   // . = area of the padded around rect
 790   // md = max distance (note in the picture below, there's md written vertically
 791   //      as well).
 792   // I = initial starting position
 793   //
 794   //       |md|  |md|
 795   //
 796   //     - ..........
 797   //     m ..........
 798   //     d ..........
 799   //     - CCCCCCC...
 800   //       CCCCAAC...
 801   //       CCCCAAC...
 802   //     - ..........
 803   //     m ..........
 804   //     d ..........
 805   //     - ..........I
 806   vertical_step_count_ = around_bottom_ - around_top_ + 1 + 2 * max_distance;
 807   horizontal_step_count_ = around_right_ - around_left_ + 1 + 2 * max_distance;
 808
 809   // Start with one to the right of the padded around rect.
 810   index_x_ = around_right_ + max_distance + 1;
 811   index_y_ = around_bottom_ + max_distance;
 812
 813   // The current index is outside a valid tile, so advance immediately.
 814   ++(*this);
 815 }
 816
 817 TilingData::ReverseSpiralDifferenceIterator&
 818     TilingData::ReverseSpiralDifferenceIterator::
 819     operator++() {
 820   while (!in_around_rect()) {
 821     if (needs_direction_switch())
 822       switch_direction();
 823
 824     index_x_ += delta_x_;
 825     index_y_ += delta_y_;
 826     ++current_step_;
 827
 828     if (in_around_rect()) {
 829       break;
 830     } else if (in_consider_rect()) {
 831       // If the tile is in the consider rect but not in ignore rect, then it's a
 832       // valid tile to visit.
 833       if (!in_ignore_rect())
 834         break;
 835
 836       // Steps needed to reach the very edge of the ignore rect, while remaining
 837       // inside it (so that the continue would take us outside).
 838       int steps_to_edge = 0;
 839       switch (direction_) {
 840         case UP:
 841           steps_to_edge = index_y_ - ignore_top_;
 842           break;
 843         case LEFT:
 844           steps_to_edge = index_x_ - ignore_left_;
 845           break;
 846         case DOWN:
 847           steps_to_edge = ignore_bottom_ - index_y_;
 848           break;
 849         case RIGHT:
 850           steps_to_edge = ignore_right_ - index_x_;
 851           break;
 852       }
 853
 854       // We need to switch directions in |max_steps|.
 855       int max_steps = current_step_count() - current_step_;
 856
 857       int steps_to_take = std::min(steps_to_edge, max_steps);
 858       DCHECK_GE(steps_to_take, 0);
 859
 860       index_x_ += steps_to_take * delta_x_;
 861       index_y_ += steps_to_take * delta_y_;
 862       current_step_ += steps_to_take;
 863     } else {
 864       // We're not in the consider rect.
 865
 866       int max_steps = current_step_count() - current_step_;
 867       int steps_to_take = max_steps;
 868
 869       // We might hit the consider rect before needing to switch directions:
 870       // update steps to take.
 871       switch (direction_) {
 872         case UP:
 873           if (valid_column() && consider_bottom_ < index_y_)
 874             steps_to_take = index_y_ - consider_bottom_ - 1;
 875           break;
 876         case LEFT:
 877           if (valid_row() && consider_right_ < index_x_)
 878             steps_to_take = index_x_ - consider_right_ - 1;
 879           break;
 880         case DOWN:
 881           if (valid_column() && consider_top_ > index_y_)
 882             steps_to_take = consider_top_ - index_y_ - 1;
 883           break;
 884         case RIGHT:
 885           if (valid_row() && consider_left_ > index_x_)
 886             steps_to_take = consider_left_ - index_x_ - 1;
 887           break;
 888       }
 889       steps_to_take = std::min(steps_to_take, max_steps);
 890       DCHECK_GE(steps_to_take, 0);
 891
 892       index_x_ += steps_to_take * delta_x_;
 893       index_y_ += steps_to_take * delta_y_;
 894       current_step_ += steps_to_take;
 895     }
 896   }
 897
 898   // Once we enter the around rect, we're done.
 899   if (in_around_rect())
 900     done();
 901   return *this;
 902 }
 903
 904 bool TilingData::ReverseSpiralDifferenceIterator::needs_direction_switch()
 905     const {
 906   return current_step_ >= current_step_count();
 907 }
 908
 909 void TilingData::ReverseSpiralDifferenceIterator::switch_direction() {
 910   // Note that delta_x_ and delta_y_ always remain between -1 and 1.
 911   int new_delta_y_ = delta_x_;
 912   delta_x_ = -delta_y_;
 913   delta_y_ = new_delta_y_;
 914
 915   current_step_ = 0;
 916   direction_ = static_cast<Direction>((direction_ + 1) % 4);
 917
 918   if (direction_ == UP || direction_ == DOWN) {
 919     --vertical_step_count_;
 920     --horizontal_step_count_;
 921
 922     // We should always end up in an around rect at some point.
 923     // Since the direction is now vertical, we have to ensure that we will
 924     // advance.
 925     DCHECK_GE(horizontal_step_count_, 1);
 926     DCHECK_GE(vertical_step_count_, 1);
 927   }
 928 }
 929
 930 }  // namespace cc