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/rect.h" 10 #include "ui/gfx/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::Rect& tiling_rect, 33 bool has_border_texels) 34 : max_texture_size_(max_texture_size), 35 tiling_rect_(tiling_rect), 36 border_texels_(has_border_texels ? 1 : 0) { 37 RecomputeNumTiles(); 38 } 39 40 TilingData::TilingData(const gfx::Size& max_texture_size, 41 const gfx::Rect& tiling_rect, 42 int border_texels) 43 : max_texture_size_(max_texture_size), 44 tiling_rect_(tiling_rect), 45 border_texels_(border_texels) { 46 RecomputeNumTiles(); 47 } 48 49 void TilingData::SetTilingRect(const gfx::Rect& tiling_rect) { 50 tiling_rect_ = tiling_rect; 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 src_position -= tiling_rect_.x(); 74 75 DCHECK_GT(max_texture_size_.width() - 2 * border_texels_, 0); 76 int x = (src_position - border_texels_) / 77 (max_texture_size_.width() - 2 * border_texels_); 78 return std::min(std::max(x, 0), num_tiles_x_ - 1); 79 } 80 81 int TilingData::TileYIndexFromSrcCoord(int src_position) const { 82 if (num_tiles_y_ <= 1) 83 return 0; 84 85 src_position -= tiling_rect_.y(); 86 87 DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0); 88 int y = (src_position - border_texels_) / 89 (max_texture_size_.height() - 2 * border_texels_); 90 return std::min(std::max(y, 0), num_tiles_y_ - 1); 91 } 92 93 int TilingData::FirstBorderTileXIndexFromSrcCoord(int src_position) const { 94 if (num_tiles_x_ <= 1) 95 return 0; 96 97 src_position -= tiling_rect_.x(); 98 99 DCHECK_GT(max_texture_size_.width() - 2 * border_texels_, 0); 100 int inner_tile_size = max_texture_size_.width() - 2 * border_texels_; 101 int x = (src_position - 2 * border_texels_) / inner_tile_size; 102 return std::min(std::max(x, 0), num_tiles_x_ - 1); 103 } 104 105 int TilingData::FirstBorderTileYIndexFromSrcCoord(int src_position) const { 106 if (num_tiles_y_ <= 1) 107 return 0; 108 109 src_position -= tiling_rect_.y(); 110 111 DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0); 112 int inner_tile_size = max_texture_size_.height() - 2 * border_texels_; 113 int y = (src_position - 2 * border_texels_) / inner_tile_size; 114 return std::min(std::max(y, 0), num_tiles_y_ - 1); 115 } 116 117 int TilingData::LastBorderTileXIndexFromSrcCoord(int src_position) const { 118 if (num_tiles_x_ <= 1) 119 return 0; 120 121 src_position -= tiling_rect_.x(); 122 123 DCHECK_GT(max_texture_size_.width() - 2 * border_texels_, 0); 124 int inner_tile_size = max_texture_size_.width() - 2 * border_texels_; 125 int x = src_position / inner_tile_size; 126 return std::min(std::max(x, 0), num_tiles_x_ - 1); 127 } 128 129 int TilingData::LastBorderTileYIndexFromSrcCoord(int src_position) const { 130 if (num_tiles_y_ <= 1) 131 return 0; 132 133 src_position -= tiling_rect_.y(); 134 135 DCHECK_GT(max_texture_size_.height() - 2 * border_texels_, 0); 136 int inner_tile_size = max_texture_size_.height() - 2 * border_texels_; 137 int y = src_position / inner_tile_size; 138 return std::min(std::max(y, 0), num_tiles_y_ - 1); 139 } 140 141 gfx::Rect TilingData::ExpandRectToTileBoundsWithBorders( 142 const gfx::Rect& rect) const { 143 if (!rect.Intersects(tiling_rect_) || has_empty_bounds()) 144 return gfx::Rect(); 145 int index_x = FirstBorderTileXIndexFromSrcCoord(rect.x()); 146 int index_y = FirstBorderTileYIndexFromSrcCoord(rect.y()); 147 int index_right = LastBorderTileXIndexFromSrcCoord(rect.right() - 1); 148 int index_bottom = LastBorderTileYIndexFromSrcCoord(rect.bottom() - 1); 149 150 gfx::Rect rect_top_left(TileBoundsWithBorder(index_x, index_y)); 151 gfx::Rect rect_bottom_right(TileBoundsWithBorder(index_right, index_bottom)); 152 153 return gfx::UnionRects(rect_top_left, rect_bottom_right); 154 } 155 156 gfx::Rect TilingData::ExpandRectToTileBounds(const gfx::Rect& rect) const { 157 if (!rect.Intersects(tiling_rect_) || has_empty_bounds()) 158 return gfx::Rect(); 159 int index_x = FirstBorderTileXIndexFromSrcCoord(rect.x()); 160 int index_y = FirstBorderTileYIndexFromSrcCoord(rect.y()); 161 int index_right = LastBorderTileXIndexFromSrcCoord(rect.right() - 1); 162 int index_bottom = LastBorderTileYIndexFromSrcCoord(rect.bottom() - 1); 163 164 gfx::Rect rect_top_left(TileBounds(index_x, index_y)); 165 gfx::Rect rect_bottom_right(TileBounds(index_right, index_bottom)); 166 167 return gfx::UnionRects(rect_top_left, rect_bottom_right); 168 } 169 170 gfx::Rect TilingData::TileBounds(int i, int j) const { 171 AssertTile(i, j); 172 int max_texture_size_x = max_texture_size_.width() - 2 * border_texels_; 173 int max_texture_size_y = max_texture_size_.height() - 2 * border_texels_; 174 175 int lo_x = tiling_rect_.x() + max_texture_size_x * i; 176 if (i != 0) 177 lo_x += border_texels_; 178 179 int lo_y = tiling_rect_.y() + max_texture_size_y * j; 180 if (j != 0) 181 lo_y += border_texels_; 182 183 int hi_x = tiling_rect_.x() + max_texture_size_x * (i + 1) + border_texels_; 184 if (i + 1 == num_tiles_x_) 185 hi_x += border_texels_; 186 187 int hi_y = tiling_rect_.y() + max_texture_size_y * (j + 1) + border_texels_; 188 if (j + 1 == num_tiles_y_) 189 hi_y += border_texels_; 190 191 hi_x = std::min(hi_x, tiling_rect_.right()); 192 hi_y = std::min(hi_y, tiling_rect_.bottom()); 193 194 int x = lo_x; 195 int y = lo_y; 196 int width = hi_x - lo_x; 197 int height = hi_y - lo_y; 198 DCHECK_GE(x, tiling_rect_.x()); 199 DCHECK_GE(y, tiling_rect_.y()); 200 DCHECK_GE(width, 0); 201 DCHECK_GE(height, 0); 202 DCHECK_LE(x, tiling_rect_.right()); 203 DCHECK_LE(y, tiling_rect_.bottom()); 204 return gfx::Rect(x, y, width, height); 205 } 206 207 gfx::Rect TilingData::TileBoundsWithBorder(int i, int j) const { 208 AssertTile(i, j); 209 int max_texture_size_x = max_texture_size_.width() - 2 * border_texels_; 210 int max_texture_size_y = max_texture_size_.height() - 2 * border_texels_; 211 212 int lo_x = tiling_rect_.x() + max_texture_size_x * i; 213 int lo_y = tiling_rect_.y() + max_texture_size_y * j; 214 215 int hi_x = lo_x + max_texture_size_x + 2 * border_texels_; 216 int hi_y = lo_y + max_texture_size_y + 2 * border_texels_; 217 218 hi_x = std::min(hi_x, tiling_rect_.right()); 219 hi_y = std::min(hi_y, tiling_rect_.bottom()); 220 221 int x = lo_x; 222 int y = lo_y; 223 int width = hi_x - lo_x; 224 int height = hi_y - lo_y; 225 DCHECK_GE(x, tiling_rect_.x()); 226 DCHECK_GE(y, tiling_rect_.y()); 227 DCHECK_GE(width, 0); 228 DCHECK_GE(height, 0); 229 DCHECK_LE(x, tiling_rect_.right()); 230 DCHECK_LE(y, tiling_rect_.bottom()); 231 return gfx::Rect(x, y, width, height); 232 } 233 234 int TilingData::TilePositionX(int x_index) const { 235 DCHECK_GE(x_index, 0); 236 DCHECK_LT(x_index, num_tiles_x_); 237 238 int pos = (max_texture_size_.width() - 2 * border_texels_) * x_index; 239 if (x_index != 0) 240 pos += border_texels_; 241 242 pos += tiling_rect_.x(); 243 244 return pos; 245 } 246 247 int TilingData::TilePositionY(int y_index) const { 248 DCHECK_GE(y_index, 0); 249 DCHECK_LT(y_index, num_tiles_y_); 250 251 int pos = (max_texture_size_.height() - 2 * border_texels_) * y_index; 252 if (y_index != 0) 253 pos += border_texels_; 254 255 pos += tiling_rect_.y(); 256 257 return pos; 258 } 259 260 int TilingData::TileSizeX(int x_index) const { 261 DCHECK_GE(x_index, 0); 262 DCHECK_LT(x_index, num_tiles_x_); 263 264 if (!x_index && num_tiles_x_ == 1) 265 return tiling_rect_.width(); 266 if (!x_index && num_tiles_x_ > 1) 267 return max_texture_size_.width() - border_texels_; 268 if (x_index < num_tiles_x_ - 1) 269 return max_texture_size_.width() - 2 * border_texels_; 270 if (x_index == num_tiles_x_ - 1) 271 return tiling_rect_.right() - TilePositionX(x_index); 272 273 NOTREACHED(); 274 return 0; 275 } 276 277 int TilingData::TileSizeY(int y_index) const { 278 DCHECK_GE(y_index, 0); 279 DCHECK_LT(y_index, num_tiles_y_); 280 281 if (!y_index && num_tiles_y_ == 1) 282 return tiling_rect_.height(); 283 if (!y_index && num_tiles_y_ > 1) 284 return max_texture_size_.height() - border_texels_; 285 if (y_index < num_tiles_y_ - 1) 286 return max_texture_size_.height() - 2 * border_texels_; 287 if (y_index == num_tiles_y_ - 1) 288 return tiling_rect_.bottom() - TilePositionY(y_index); 289 290 NOTREACHED(); 291 return 0; 292 } 293 294 gfx::Vector2d TilingData::TextureOffset(int x_index, int y_index) const { 295 int left = (!x_index || num_tiles_x_ == 1) ? 0 : border_texels_; 296 int top = (!y_index || num_tiles_y_ == 1) ? 0 : border_texels_; 297 298 return gfx::Vector2d(left, top); 299 } 300 301 void TilingData::RecomputeNumTiles() { 302 num_tiles_x_ = ComputeNumTiles( 303 max_texture_size_.width(), tiling_rect_.width(), border_texels_); 304 num_tiles_y_ = ComputeNumTiles( 305 max_texture_size_.height(), tiling_rect_.height(), border_texels_); 306 } 307 308 TilingData::BaseIterator::BaseIterator(const TilingData* tiling_data) 309 : tiling_data_(tiling_data), 310 index_x_(-1), 311 index_y_(-1) { 312 } 313 314 TilingData::Iterator::Iterator() : BaseIterator(NULL) { done(); } 315 316 TilingData::Iterator::Iterator(const TilingData* tiling_data, 317 const gfx::Rect& tiling_rect, 318 bool include_borders) 319 : BaseIterator(tiling_data), left_(-1), right_(-1), bottom_(-1) { 320 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) { 321 done(); 322 return; 323 } 324 325 gfx::Rect rect(tiling_rect); 326 rect.Intersect(tiling_data_->tiling_rect()); 327 328 gfx::Rect top_left_tile; 329 if (include_borders) { 330 index_x_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(rect.x()); 331 index_y_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(rect.y()); 332 right_ = tiling_data_->LastBorderTileXIndexFromSrcCoord(rect.right() - 1); 333 bottom_ = tiling_data_->LastBorderTileYIndexFromSrcCoord(rect.bottom() - 1); 334 top_left_tile = tiling_data_->TileBoundsWithBorder(index_x_, index_y_); 335 } else { 336 index_x_ = tiling_data_->TileXIndexFromSrcCoord(rect.x()); 337 index_y_ = tiling_data_->TileYIndexFromSrcCoord(rect.y()); 338 right_ = tiling_data_->TileXIndexFromSrcCoord(rect.right() - 1); 339 bottom_ = tiling_data_->TileYIndexFromSrcCoord(rect.bottom() - 1); 340 top_left_tile = tiling_data_->TileBounds(index_x_, index_y_); 341 } 342 left_ = index_x_; 343 344 // Index functions always return valid indices, so explicitly check 345 // for non-intersecting rects. 346 if (!top_left_tile.Intersects(rect)) 347 done(); 348 } 349 350 TilingData::Iterator& TilingData::Iterator::operator++() { 351 if (!*this) 352 return *this; 353 354 index_x_++; 355 if (index_x_ > right_) { 356 index_x_ = left_; 357 index_y_++; 358 if (index_y_ > bottom_) 359 done(); 360 } 361 362 return *this; 363 } 364 365 TilingData::DifferenceIterator::DifferenceIterator( 366 const TilingData* tiling_data, 367 const gfx::Rect& consider_rect, 368 const gfx::Rect& ignore_rect) 369 : BaseIterator(tiling_data), 370 consider_left_(-1), 371 consider_top_(-1), 372 consider_right_(-1), 373 consider_bottom_(-1), 374 ignore_left_(-1), 375 ignore_top_(-1), 376 ignore_right_(-1), 377 ignore_bottom_(-1) { 378 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) { 379 done(); 380 return; 381 } 382 383 gfx::Rect consider(consider_rect); 384 gfx::Rect ignore(ignore_rect); 385 consider.Intersect(tiling_data_->tiling_rect()); 386 ignore.Intersect(tiling_data_->tiling_rect()); 387 if (consider.IsEmpty()) { 388 done(); 389 return; 390 } 391 392 consider_left_ = 393 tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x()); 394 consider_top_ = 395 tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y()); 396 consider_right_ = 397 tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1); 398 consider_bottom_ = 399 tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1); 400 401 if (!ignore.IsEmpty()) { 402 ignore_left_ = 403 tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x()); 404 ignore_top_ = 405 tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y()); 406 ignore_right_ = 407 tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1); 408 ignore_bottom_ = 409 tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1); 410 411 // Clamp ignore indices to consider indices. 412 ignore_left_ = std::max(ignore_left_, consider_left_); 413 ignore_top_ = std::max(ignore_top_, consider_top_); 414 ignore_right_ = std::min(ignore_right_, consider_right_); 415 ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_); 416 } 417 418 if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ && 419 ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) { 420 done(); 421 return; 422 } 423 424 index_x_ = consider_left_; 425 index_y_ = consider_top_; 426 427 if (in_ignore_rect()) 428 ++(*this); 429 } 430 431 TilingData::DifferenceIterator& TilingData::DifferenceIterator::operator++() { 432 if (!*this) 433 return *this; 434 435 index_x_++; 436 if (in_ignore_rect()) 437 index_x_ = ignore_right_ + 1; 438 439 if (index_x_ > consider_right_) { 440 index_x_ = consider_left_; 441 index_y_++; 442 443 if (in_ignore_rect()) { 444 index_x_ = ignore_right_ + 1; 445 // If the ignore rect spans the whole consider rect horizontally, then 446 // ignore_right + 1 will be out of bounds. 447 if (in_ignore_rect() || index_x_ > consider_right_) { 448 index_y_ = ignore_bottom_ + 1; 449 index_x_ = consider_left_; 450 } 451 } 452 453 if (index_y_ > consider_bottom_) 454 done(); 455 } 456 457 return *this; 458 } 459 460 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator() 461 : BaseIterator(NULL) { 462 done(); 463 } 464 465 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator( 466 const TilingData* tiling_data, 467 const gfx::Rect& consider_rect, 468 const gfx::Rect& ignore_rect, 469 const gfx::Rect& center_rect) 470 : BaseIterator(tiling_data), 471 consider_left_(-1), 472 consider_top_(-1), 473 consider_right_(-1), 474 consider_bottom_(-1), 475 ignore_left_(-1), 476 ignore_top_(-1), 477 ignore_right_(-1), 478 ignore_bottom_(-1), 479 direction_(RIGHT), 480 delta_x_(1), 481 delta_y_(0), 482 current_step_(0), 483 horizontal_step_count_(0), 484 vertical_step_count_(0) { 485 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) { 486 done(); 487 return; 488 } 489 490 gfx::Rect consider(consider_rect); 491 gfx::Rect ignore(ignore_rect); 492 gfx::Rect center(center_rect); 493 consider.Intersect(tiling_data_->tiling_rect()); 494 ignore.Intersect(tiling_data_->tiling_rect()); 495 if (consider.IsEmpty()) { 496 done(); 497 return; 498 } 499 500 consider_left_ = 501 tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x()); 502 consider_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y()); 503 consider_right_ = 504 tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1); 505 consider_bottom_ = 506 tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1); 507 508 if (!ignore.IsEmpty()) { 509 ignore_left_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x()); 510 ignore_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y()); 511 ignore_right_ = 512 tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1); 513 ignore_bottom_ = 514 tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1); 515 516 // Clamp ignore indices to consider indices. 517 ignore_left_ = std::max(ignore_left_, consider_left_); 518 ignore_top_ = std::max(ignore_top_, consider_top_); 519 ignore_right_ = std::min(ignore_right_, consider_right_); 520 ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_); 521 } 522 523 if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ && 524 ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) { 525 done(); 526 return; 527 } 528 529 // Determine around left, such that it is between -1 and num_tiles_x. 530 int around_left = 0; 531 if (center.x() < tiling_data->tiling_rect().x() || center.IsEmpty()) 532 around_left = -1; 533 else if (center.x() > tiling_data->tiling_rect().right()) 534 around_left = tiling_data->num_tiles_x(); 535 else 536 around_left = tiling_data->FirstBorderTileXIndexFromSrcCoord(center.x()); 537 538 // Determine around top, such that it is between -1 and num_tiles_y. 539 int around_top = 0; 540 if (center.y() < tiling_data->tiling_rect().y() || center.IsEmpty()) 541 around_top = -1; 542 else if (center.y() > tiling_data->tiling_rect().bottom()) 543 around_top = tiling_data->num_tiles_y(); 544 else 545 around_top = tiling_data->FirstBorderTileYIndexFromSrcCoord(center.y()); 546 547 // Determine around right, such that it is between -1 and num_tiles_x. 548 int right_src_coord = center.right() - 1; 549 int around_right = 0; 550 if (right_src_coord < tiling_data->tiling_rect().x() || center.IsEmpty()) { 551 around_right = -1; 552 } else if (right_src_coord > tiling_data->tiling_rect().right()) { 553 around_right = tiling_data->num_tiles_x(); 554 } else { 555 around_right = 556 tiling_data->LastBorderTileXIndexFromSrcCoord(right_src_coord); 557 } 558 559 // Determine around bottom, such that it is between -1 and num_tiles_y. 560 int bottom_src_coord = center.bottom() - 1; 561 int around_bottom = 0; 562 if (bottom_src_coord < tiling_data->tiling_rect().y() || center.IsEmpty()) { 563 around_bottom = -1; 564 } else if (bottom_src_coord > tiling_data->tiling_rect().bottom()) { 565 around_bottom = tiling_data->num_tiles_y(); 566 } else { 567 around_bottom = 568 tiling_data->LastBorderTileYIndexFromSrcCoord(bottom_src_coord); 569 } 570 571 vertical_step_count_ = around_bottom - around_top + 1; 572 horizontal_step_count_ = around_right - around_left + 1; 573 current_step_ = horizontal_step_count_ - 1; 574 575 index_x_ = around_right; 576 index_y_ = around_bottom; 577 578 // The current index is the bottom right of the around rect, which is also 579 // ignored. So we have to advance. 580 ++(*this); 581 } 582 583 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator:: 584 operator++() { 585 int cannot_hit_consider_count = 0; 586 while (cannot_hit_consider_count < 4) { 587 if (needs_direction_switch()) 588 switch_direction(); 589 590 index_x_ += delta_x_; 591 index_y_ += delta_y_; 592 ++current_step_; 593 594 if (in_consider_rect()) { 595 cannot_hit_consider_count = 0; 596 597 if (!in_ignore_rect()) 598 break; 599 600 // Steps needed to reach the very edge of the ignore rect, while remaining 601 // inside (so that the continue would take us outside). 602 int steps_to_edge = 0; 603 switch (direction_) { 604 case UP: 605 steps_to_edge = index_y_ - ignore_top_; 606 break; 607 case LEFT: 608 steps_to_edge = index_x_ - ignore_left_; 609 break; 610 case DOWN: 611 steps_to_edge = ignore_bottom_ - index_y_; 612 break; 613 case RIGHT: 614 steps_to_edge = ignore_right_ - index_x_; 615 break; 616 } 617 618 // We need to switch directions in |max_steps|. 619 int max_steps = current_step_count() - current_step_; 620 621 int steps_to_take = std::min(steps_to_edge, max_steps); 622 DCHECK_GE(steps_to_take, 0); 623 624 index_x_ += steps_to_take * delta_x_; 625 index_y_ += steps_to_take * delta_y_; 626 current_step_ += steps_to_take; 627 } else { 628 int max_steps = current_step_count() - current_step_; 629 int steps_to_take = max_steps; 630 bool can_hit_consider_rect = false; 631 switch (direction_) { 632 case UP: 633 if (valid_column() && consider_bottom_ < index_y_) 634 steps_to_take = index_y_ - consider_bottom_ - 1; 635 can_hit_consider_rect |= consider_right_ >= index_x_; 636 break; 637 case LEFT: 638 if (valid_row() && consider_right_ < index_x_) 639 steps_to_take = index_x_ - consider_right_ - 1; 640 can_hit_consider_rect |= consider_top_ <= index_y_; 641 break; 642 case DOWN: 643 if (valid_column() && consider_top_ > index_y_) 644 steps_to_take = consider_top_ - index_y_ - 1; 645 can_hit_consider_rect |= consider_left_ <= index_x_; 646 break; 647 case RIGHT: 648 if (valid_row() && consider_left_ > index_x_) 649 steps_to_take = consider_left_ - index_x_ - 1; 650 can_hit_consider_rect |= consider_bottom_ >= index_y_; 651 break; 652 } 653 steps_to_take = std::min(steps_to_take, max_steps); 654 DCHECK_GE(steps_to_take, 0); 655 656 index_x_ += steps_to_take * delta_x_; 657 index_y_ += steps_to_take * delta_y_; 658 current_step_ += steps_to_take; 659 660 if (can_hit_consider_rect) 661 cannot_hit_consider_count = 0; 662 else 663 ++cannot_hit_consider_count; 664 } 665 } 666 667 if (cannot_hit_consider_count >= 4) 668 done(); 669 return *this; 670 } 671 672 bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const { 673 return current_step_ >= current_step_count(); 674 } 675 676 void TilingData::SpiralDifferenceIterator::switch_direction() { 677 int new_delta_x_ = delta_y_; 678 delta_y_ = -delta_x_; 679 delta_x_ = new_delta_x_; 680 681 current_step_ = 0; 682 direction_ = static_cast<Direction>((direction_ + 1) % 4); 683 684 if (direction_ == RIGHT || direction_ == LEFT) { 685 ++vertical_step_count_; 686 ++horizontal_step_count_; 687 } 688 } 689 690 } // namespace cc 691