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
ComputeNumTiles(int max_texture_size,int total_size,int border_texels)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
TilingData()26 TilingData::TilingData()
27 : border_texels_(0) {
28 RecomputeNumTiles();
29 }
30
TilingData(const gfx::Size & max_texture_size,const gfx::Size & tiling_size,bool has_border_texels)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
TilingData(const gfx::Size & max_texture_size,const gfx::Size & tiling_size,int border_texels)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
SetTilingSize(const gfx::Size & tiling_size)49 void TilingData::SetTilingSize(const gfx::Size& tiling_size) {
50 tiling_size_ = tiling_size;
51 RecomputeNumTiles();
52 }
53
SetMaxTextureSize(const gfx::Size & max_texture_size)54 void TilingData::SetMaxTextureSize(const gfx::Size& max_texture_size) {
55 max_texture_size_ = max_texture_size;
56 RecomputeNumTiles();
57 }
58
SetHasBorderTexels(bool has_border_texels)59 void TilingData::SetHasBorderTexels(bool has_border_texels) {
60 border_texels_ = has_border_texels ? 1 : 0;
61 RecomputeNumTiles();
62 }
63
SetBorderTexels(int border_texels)64 void TilingData::SetBorderTexels(int border_texels) {
65 border_texels_ = border_texels;
66 RecomputeNumTiles();
67 }
68
TileXIndexFromSrcCoord(int src_position) const69 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
TileYIndexFromSrcCoord(int src_position) const79 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
FirstBorderTileXIndexFromSrcCoord(int src_position) const89 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
FirstBorderTileYIndexFromSrcCoord(int src_position) const99 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
LastBorderTileXIndexFromSrcCoord(int src_position) const109 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
LastBorderTileYIndexFromSrcCoord(int src_position) const119 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
ExpandRectIgnoringBordersToTileBounds(const gfx::Rect & rect) const129 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
ExpandRectToTileBounds(const gfx::Rect & rect) const146 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
TileBounds(int i,int j) const162 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
TileBoundsWithBorder(int i,int j) const199 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
TilePositionX(int x_index) const226 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
TilePositionY(int y_index) const237 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
TileSizeX(int x_index) const248 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
TileSizeY(int y_index) const265 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
TextureOffset(int x_index,int y_index) const282 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
RecomputeNumTiles()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
BaseIterator(const TilingData * tiling_data)296 TilingData::BaseIterator::BaseIterator(const TilingData* tiling_data)
297 : tiling_data_(tiling_data),
298 index_x_(-1),
299 index_y_(-1) {
300 }
301
Iterator()302 TilingData::Iterator::Iterator() : BaseIterator(NULL) { done(); }
303
Iterator(const TilingData * tiling_data,const gfx::Rect & consider_rect,bool include_borders)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
operator ++()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
DifferenceIterator(const TilingData * tiling_data,const gfx::Rect & consider_rect,const gfx::Rect & ignore_rect)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
operator ++()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
SpiralDifferenceIterator()443 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator()
444 : BaseIterator(NULL) {
445 done();
446 }
447
SpiralDifferenceIterator(const TilingData * tiling_data,const gfx::Rect & consider_rect,const gfx::Rect & ignore_rect,const gfx::Rect & center_rect)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::
operator ++()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
needs_direction_switch() const650 bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
651 return current_step_ >= current_step_count();
652 }
653
switch_direction()654 void TilingData::SpiralDifferenceIterator::switch_direction() {
655 int new_delta_x_ = delta_y_;
656 delta_y_ = -delta_x_;
657 delta_x_ = new_delta_x_;
658
659 current_step_ = 0;
660 direction_ = static_cast<Direction>((direction_ + 1) % 4);
661
662 if (direction_ == RIGHT || direction_ == LEFT) {
663 ++vertical_step_count_;
664 ++horizontal_step_count_;
665 }
666 }
667
668 } // namespace cc
669