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.
5 #include "cc/base/tiling_data.h"
9 #include "ui/gfx/rect.h"
10 #include "ui/gfx/vector2d.h"
14 static int ComputeNumTiles(int max_texture_size,
17 if (max_texture_size - 2 * border_texels <= 0)
18 return total_size > 0 && max_texture_size >= total_size ? 1 : 0;
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;
26 TilingData::TilingData()
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) {
40 TilingData::TilingData(const gfx::Size& max_texture_size,
41 const gfx::Rect& tiling_rect,
43 : max_texture_size_(max_texture_size),
44 tiling_rect_(tiling_rect),
45 border_texels_(border_texels) {
49 void TilingData::SetTilingRect(const gfx::Rect& tiling_rect) {
50 tiling_rect_ = tiling_rect;
54 void TilingData::SetMaxTextureSize(const gfx::Size& max_texture_size) {
55 max_texture_size_ = max_texture_size;
59 void TilingData::SetHasBorderTexels(bool has_border_texels) {
60 border_texels_ = has_border_texels ? 1 : 0;
64 void TilingData::SetBorderTexels(int border_texels) {
65 border_texels_ = border_texels;
69 int TilingData::TileXIndexFromSrcCoord(int src_position) const {
70 if (num_tiles_x_ <= 1)
73 src_position -= tiling_rect_.x();
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);
81 int TilingData::TileYIndexFromSrcCoord(int src_position) const {
82 if (num_tiles_y_ <= 1)
85 src_position -= tiling_rect_.y();
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);
93 int TilingData::FirstBorderTileXIndexFromSrcCoord(int src_position) const {
94 if (num_tiles_x_ <= 1)
97 src_position -= tiling_rect_.x();
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);
105 int TilingData::FirstBorderTileYIndexFromSrcCoord(int src_position) const {
106 if (num_tiles_y_ <= 1)
109 src_position -= tiling_rect_.y();
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);
117 int TilingData::LastBorderTileXIndexFromSrcCoord(int src_position) const {
118 if (num_tiles_x_ <= 1)
121 src_position -= tiling_rect_.x();
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);
129 int TilingData::LastBorderTileYIndexFromSrcCoord(int src_position) const {
130 if (num_tiles_y_ <= 1)
133 src_position -= tiling_rect_.y();
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);
141 gfx::Rect TilingData::ExpandRectToTileBoundsWithBorders(
142 const gfx::Rect rect) const {
143 if (!rect.Intersects(tiling_rect_) || has_empty_bounds())
145 int index_x = FirstBorderTileXIndexFromSrcCoord(rect.x());
146 int index_y = FirstBorderTileYIndexFromSrcCoord(rect.y());
147 int index_right = LastBorderTileXIndexFromSrcCoord(rect.right());
148 int index_bottom = LastBorderTileYIndexFromSrcCoord(rect.bottom());
150 gfx::Rect rect_top_left(TileBoundsWithBorder(index_x, index_y));
151 gfx::Rect rect_bottom_right(TileBoundsWithBorder(index_right, index_bottom));
153 gfx::Rect expanded(rect_top_left);
154 expanded.Union(rect_bottom_right);
158 gfx::Rect TilingData::TileBounds(int i, int j) const {
160 int max_texture_size_x = max_texture_size_.width() - 2 * border_texels_;
161 int max_texture_size_y = max_texture_size_.height() - 2 * border_texels_;
163 int lo_x = tiling_rect_.x() + max_texture_size_x * i;
165 lo_x += border_texels_;
167 int lo_y = tiling_rect_.y() + max_texture_size_y * j;
169 lo_y += border_texels_;
171 int hi_x = tiling_rect_.x() + max_texture_size_x * (i + 1) + border_texels_;
172 if (i + 1 == num_tiles_x_)
173 hi_x += border_texels_;
175 int hi_y = tiling_rect_.y() + max_texture_size_y * (j + 1) + border_texels_;
176 if (j + 1 == num_tiles_y_)
177 hi_y += border_texels_;
179 hi_x = std::min(hi_x, tiling_rect_.right());
180 hi_y = std::min(hi_y, tiling_rect_.bottom());
184 int width = hi_x - lo_x;
185 int height = hi_y - lo_y;
186 DCHECK_GE(x, tiling_rect_.x());
187 DCHECK_GE(y, tiling_rect_.y());
189 DCHECK_GE(height, 0);
190 DCHECK_LE(x, tiling_rect_.right());
191 DCHECK_LE(y, tiling_rect_.bottom());
192 return gfx::Rect(x, y, width, height);
195 gfx::Rect TilingData::TileBoundsWithBorder(int i, int j) const {
197 int max_texture_size_x = max_texture_size_.width() - 2 * border_texels_;
198 int max_texture_size_y = max_texture_size_.height() - 2 * border_texels_;
200 int lo_x = tiling_rect_.x() + max_texture_size_x * i;
201 int lo_y = tiling_rect_.y() + max_texture_size_y * j;
203 int hi_x = lo_x + max_texture_size_x + 2 * border_texels_;
204 int hi_y = lo_y + max_texture_size_y + 2 * border_texels_;
206 hi_x = std::min(hi_x, tiling_rect_.right());
207 hi_y = std::min(hi_y, tiling_rect_.bottom());
211 int width = hi_x - lo_x;
212 int height = hi_y - lo_y;
213 DCHECK_GE(x, tiling_rect_.x());
214 DCHECK_GE(y, tiling_rect_.y());
216 DCHECK_GE(height, 0);
217 DCHECK_LE(x, tiling_rect_.right());
218 DCHECK_LE(y, tiling_rect_.bottom());
219 return gfx::Rect(x, y, width, height);
222 int TilingData::TilePositionX(int x_index) const {
223 DCHECK_GE(x_index, 0);
224 DCHECK_LT(x_index, num_tiles_x_);
226 int pos = (max_texture_size_.width() - 2 * border_texels_) * x_index;
228 pos += border_texels_;
230 pos += tiling_rect_.x();
235 int TilingData::TilePositionY(int y_index) const {
236 DCHECK_GE(y_index, 0);
237 DCHECK_LT(y_index, num_tiles_y_);
239 int pos = (max_texture_size_.height() - 2 * border_texels_) * y_index;
241 pos += border_texels_;
243 pos += tiling_rect_.y();
248 int TilingData::TileSizeX(int x_index) const {
249 DCHECK_GE(x_index, 0);
250 DCHECK_LT(x_index, num_tiles_x_);
252 if (!x_index && num_tiles_x_ == 1)
253 return tiling_rect_.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_rect_.right() - TilePositionX(x_index);
265 int TilingData::TileSizeY(int y_index) const {
266 DCHECK_GE(y_index, 0);
267 DCHECK_LT(y_index, num_tiles_y_);
269 if (!y_index && num_tiles_y_ == 1)
270 return tiling_rect_.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_rect_.bottom() - TilePositionY(y_index);
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_;
286 return gfx::Vector2d(left, top);
289 void TilingData::RecomputeNumTiles() {
290 num_tiles_x_ = ComputeNumTiles(
291 max_texture_size_.width(), tiling_rect_.width(), border_texels_);
292 num_tiles_y_ = ComputeNumTiles(
293 max_texture_size_.height(), tiling_rect_.height(), border_texels_);
296 TilingData::BaseIterator::BaseIterator(const TilingData* tiling_data)
297 : tiling_data_(tiling_data),
302 TilingData::Iterator::Iterator() : BaseIterator(NULL) { done(); }
304 TilingData::Iterator::Iterator(const TilingData* tiling_data,
305 const gfx::Rect& tiling_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) {
313 gfx::Rect rect(tiling_rect);
314 rect.Intersect(tiling_data_->tiling_rect());
316 gfx::Rect top_left_tile;
317 if (include_borders) {
318 index_x_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(rect.x());
319 index_y_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(rect.y());
320 right_ = tiling_data_->LastBorderTileXIndexFromSrcCoord(rect.right() - 1);
321 bottom_ = tiling_data_->LastBorderTileYIndexFromSrcCoord(rect.bottom() - 1);
322 top_left_tile = tiling_data_->TileBoundsWithBorder(index_x_, index_y_);
324 index_x_ = tiling_data_->TileXIndexFromSrcCoord(rect.x());
325 index_y_ = tiling_data_->TileYIndexFromSrcCoord(rect.y());
326 right_ = tiling_data_->TileXIndexFromSrcCoord(rect.right() - 1);
327 bottom_ = tiling_data_->TileYIndexFromSrcCoord(rect.bottom() - 1);
328 top_left_tile = tiling_data_->TileBounds(index_x_, index_y_);
332 // Index functions always return valid indices, so explicitly check
333 // for non-intersecting rects.
334 if (!top_left_tile.Intersects(rect))
338 TilingData::Iterator& TilingData::Iterator::operator++() {
343 if (index_x_ > right_) {
346 if (index_y_ > bottom_)
353 TilingData::DifferenceIterator::DifferenceIterator(
354 const TilingData* tiling_data,
355 const gfx::Rect& consider_rect,
356 const gfx::Rect& ignore_rect)
357 : BaseIterator(tiling_data),
361 consider_bottom_(-1),
366 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
371 gfx::Rect consider(consider_rect);
372 gfx::Rect ignore(ignore_rect);
373 consider.Intersect(tiling_data_->tiling_rect());
374 ignore.Intersect(tiling_data_->tiling_rect());
375 if (consider.IsEmpty()) {
381 tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x());
383 tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y());
385 tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1);
387 tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1);
389 if (!ignore.IsEmpty()) {
391 tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x());
393 tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y());
395 tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1);
397 tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1);
399 // Clamp ignore indices to consider indices.
400 ignore_left_ = std::max(ignore_left_, consider_left_);
401 ignore_top_ = std::max(ignore_top_, consider_top_);
402 ignore_right_ = std::min(ignore_right_, consider_right_);
403 ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
406 if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
407 ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
412 index_x_ = consider_left_;
413 index_y_ = consider_top_;
415 if (in_ignore_rect())
419 TilingData::DifferenceIterator& TilingData::DifferenceIterator::operator++() {
424 if (in_ignore_rect())
425 index_x_ = ignore_right_ + 1;
427 if (index_x_ > consider_right_) {
428 index_x_ = consider_left_;
431 if (in_ignore_rect()) {
432 index_x_ = ignore_right_ + 1;
433 // If the ignore rect spans the whole consider rect horizontally, then
434 // ignore_right + 1 will be out of bounds.
435 if (in_ignore_rect() || index_x_ > consider_right_) {
436 index_y_ = ignore_bottom_ + 1;
437 index_x_ = consider_left_;
441 if (index_y_ > consider_bottom_)
448 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator()
449 : BaseIterator(NULL) {
453 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
454 const TilingData* tiling_data,
455 const gfx::Rect& consider_rect,
456 const gfx::Rect& ignore_rect,
457 const gfx::Rect& center_rect)
458 : BaseIterator(tiling_data),
462 consider_bottom_(-1),
471 horizontal_step_count_(0),
472 vertical_step_count_(0) {
473 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
478 gfx::Rect consider(consider_rect);
479 gfx::Rect ignore(ignore_rect);
480 gfx::Rect center(center_rect);
481 consider.Intersect(tiling_data_->tiling_rect());
482 ignore.Intersect(tiling_data_->tiling_rect());
483 if (consider.IsEmpty()) {
489 tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x());
490 consider_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y());
492 tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1);
494 tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1);
496 if (!ignore.IsEmpty()) {
497 ignore_left_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x());
498 ignore_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y());
500 tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1);
502 tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1);
504 // Clamp ignore indices to consider indices.
505 ignore_left_ = std::max(ignore_left_, consider_left_);
506 ignore_top_ = std::max(ignore_top_, consider_top_);
507 ignore_right_ = std::min(ignore_right_, consider_right_);
508 ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
511 if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
512 ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
517 // Determine around left, such that it is between -1 and num_tiles_x.
519 if (center.x() < tiling_data->tiling_rect().x() || center.IsEmpty())
521 else if (center.x() > tiling_data->tiling_rect().right())
522 around_left = tiling_data->num_tiles_x();
524 around_left = tiling_data->FirstBorderTileXIndexFromSrcCoord(center.x());
526 // Determine around top, such that it is between -1 and num_tiles_y.
528 if (center.y() < tiling_data->tiling_rect().y() || center.IsEmpty())
530 else if (center.y() > tiling_data->tiling_rect().bottom())
531 around_top = tiling_data->num_tiles_y();
533 around_top = tiling_data->FirstBorderTileYIndexFromSrcCoord(center.y());
535 // Determine around right, such that it is between -1 and num_tiles_x.
536 int right_src_coord = center.right() - 1;
537 int around_right = 0;
538 if (right_src_coord < tiling_data->tiling_rect().x() || center.IsEmpty()) {
540 } else if (right_src_coord > tiling_data->tiling_rect().right()) {
541 around_right = tiling_data->num_tiles_x();
544 tiling_data->LastBorderTileXIndexFromSrcCoord(right_src_coord);
547 // Determine around bottom, such that it is between -1 and num_tiles_y.
548 int bottom_src_coord = center.bottom() - 1;
549 int around_bottom = 0;
550 if (bottom_src_coord < tiling_data->tiling_rect().y() || center.IsEmpty()) {
552 } else if (bottom_src_coord > tiling_data->tiling_rect().bottom()) {
553 around_bottom = tiling_data->num_tiles_y();
556 tiling_data->LastBorderTileYIndexFromSrcCoord(bottom_src_coord);
559 vertical_step_count_ = around_bottom - around_top + 1;
560 horizontal_step_count_ = around_right - around_left + 1;
561 current_step_ = horizontal_step_count_ - 1;
563 index_x_ = around_right;
564 index_y_ = around_bottom;
566 // The current index is the bottom right of the around rect, which is also
567 // ignored. So we have to advance.
571 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
573 int cannot_hit_consider_count = 0;
574 while (cannot_hit_consider_count < 4) {
575 if (needs_direction_switch())
578 index_x_ += delta_x_;
579 index_y_ += delta_y_;
582 if (in_consider_rect()) {
583 cannot_hit_consider_count = 0;
585 if (!in_ignore_rect())
588 // Steps needed to reach the very edge of the ignore rect, while remaining
589 // inside (so that the continue would take us outside).
590 int steps_to_edge = 0;
591 switch (direction_) {
593 steps_to_edge = index_y_ - ignore_top_;
596 steps_to_edge = index_x_ - ignore_left_;
599 steps_to_edge = ignore_bottom_ - index_y_;
602 steps_to_edge = ignore_right_ - index_x_;
606 // We need to switch directions in |max_steps|.
607 int max_steps = current_step_count() - current_step_;
609 int steps_to_take = std::min(steps_to_edge, max_steps);
610 DCHECK_GE(steps_to_take, 0);
612 index_x_ += steps_to_take * delta_x_;
613 index_y_ += steps_to_take * delta_y_;
614 current_step_ += steps_to_take;
616 int max_steps = current_step_count() - current_step_;
617 int steps_to_take = max_steps;
618 bool can_hit_consider_rect = false;
619 switch (direction_) {
621 if (valid_column() && consider_bottom_ < index_y_)
622 steps_to_take = index_y_ - consider_bottom_ - 1;
623 can_hit_consider_rect |= consider_right_ >= index_x_;
626 if (valid_row() && consider_right_ < index_x_)
627 steps_to_take = index_x_ - consider_right_ - 1;
628 can_hit_consider_rect |= consider_top_ <= index_y_;
631 if (valid_column() && consider_top_ > index_y_)
632 steps_to_take = consider_top_ - index_y_ - 1;
633 can_hit_consider_rect |= consider_left_ <= index_x_;
636 if (valid_row() && consider_left_ > index_x_)
637 steps_to_take = consider_left_ - index_x_ - 1;
638 can_hit_consider_rect |= consider_bottom_ >= index_y_;
641 steps_to_take = std::min(steps_to_take, max_steps);
642 DCHECK_GE(steps_to_take, 0);
644 index_x_ += steps_to_take * delta_x_;
645 index_y_ += steps_to_take * delta_y_;
646 current_step_ += steps_to_take;
648 if (can_hit_consider_rect)
649 cannot_hit_consider_count = 0;
651 ++cannot_hit_consider_count;
655 if (cannot_hit_consider_count >= 4)
660 bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
661 return current_step_ >= current_step_count();
664 void TilingData::SpiralDifferenceIterator::switch_direction() {
665 int new_delta_x_ = delta_y_;
666 delta_y_ = -delta_x_;
667 delta_x_ = new_delta_x_;
670 direction_ = static_cast<Direction>((direction_ + 1) % 4);
672 if (direction_ == RIGHT || direction_ == LEFT) {
673 ++vertical_step_count_;
674 ++horizontal_step_count_;