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::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) {
40 TilingData::TilingData(const gfx::Size& max_texture_size,
41 const gfx::Size& tiling_size,
43 : max_texture_size_(max_texture_size),
44 tiling_size_(tiling_size),
45 border_texels_(border_texels) {
49 void TilingData::SetTilingSize(const gfx::Size& tiling_size) {
50 tiling_size_ = tiling_size;
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 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);
79 int TilingData::TileYIndexFromSrcCoord(int src_position) const {
80 if (num_tiles_y_ <= 1)
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);
89 int TilingData::FirstBorderTileXIndexFromSrcCoord(int src_position) const {
90 if (num_tiles_x_ <= 1)
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);
99 int TilingData::FirstBorderTileYIndexFromSrcCoord(int src_position) const {
100 if (num_tiles_y_ <= 1)
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);
109 int TilingData::LastBorderTileXIndexFromSrcCoord(int src_position) const {
110 if (num_tiles_x_ <= 1)
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);
119 int TilingData::LastBorderTileYIndexFromSrcCoord(int src_position) const {
120 if (num_tiles_y_ <= 1)
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);
129 gfx::Rect TilingData::ExpandRectIgnoringBordersToTileBoundsWithBorders(
130 const gfx::Rect& rect) const {
131 if (rect.IsEmpty() || has_empty_bounds())
133 if (rect.x() > tiling_size_.width() || rect.y() > tiling_size_.height())
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);
140 gfx::Rect rect_top_left(TileBoundsWithBorder(index_x, index_y));
141 gfx::Rect rect_bottom_right(TileBoundsWithBorder(index_right, index_bottom));
143 return gfx::UnionRects(rect_top_left, rect_bottom_right);
146 gfx::Rect TilingData::ExpandRectToTileBounds(const gfx::Rect& rect) const {
147 if (rect.IsEmpty() || has_empty_bounds())
149 if (rect.x() > tiling_size_.width() || rect.y() > tiling_size_.height())
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);
156 gfx::Rect rect_top_left(TileBounds(index_x, index_y));
157 gfx::Rect rect_bottom_right(TileBounds(index_right, index_bottom));
159 return gfx::UnionRects(rect_top_left, rect_bottom_right);
162 gfx::Rect TilingData::TileBounds(int i, int j) const {
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_;
167 int lo_x = max_texture_size_x * i;
169 lo_x += border_texels_;
171 int lo_y = max_texture_size_y * j;
173 lo_y += border_texels_;
175 int hi_x = max_texture_size_x * (i + 1) + border_texels_;
176 if (i + 1 == num_tiles_x_)
177 hi_x += border_texels_;
179 int hi_y = max_texture_size_y * (j + 1) + border_texels_;
180 if (j + 1 == num_tiles_y_)
181 hi_y += border_texels_;
183 hi_x = std::min(hi_x, tiling_size_.width());
184 hi_y = std::min(hi_y, tiling_size_.height());
188 int width = hi_x - lo_x;
189 int height = hi_y - lo_y;
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);
199 gfx::Rect TilingData::TileBoundsWithBorder(int i, int j) const {
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_;
204 int lo_x = max_texture_size_x * i;
205 int lo_y = max_texture_size_y * j;
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_;
210 hi_x = std::min(hi_x, tiling_size_.width());
211 hi_y = std::min(hi_y, tiling_size_.height());
215 int width = hi_x - lo_x;
216 int height = hi_y - lo_y;
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);
226 int TilingData::TilePositionX(int x_index) const {
227 DCHECK_GE(x_index, 0);
228 DCHECK_LT(x_index, num_tiles_x_);
230 int pos = (max_texture_size_.width() - 2 * border_texels_) * x_index;
232 pos += border_texels_;
237 int TilingData::TilePositionY(int y_index) const {
238 DCHECK_GE(y_index, 0);
239 DCHECK_LT(y_index, num_tiles_y_);
241 int pos = (max_texture_size_.height() - 2 * border_texels_) * y_index;
243 pos += border_texels_;
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_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);
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_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);
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_size_.width(), border_texels_);
292 num_tiles_y_ = ComputeNumTiles(
293 max_texture_size_.height(), tiling_size_.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& 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) {
313 gfx::Rect tiling_bounds_rect(tiling_data_->tiling_size());
314 gfx::Rect rect(consider_rect);
315 rect.Intersect(tiling_bounds_rect);
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_);
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_);
333 // Index functions always return valid indices, so explicitly check
334 // for non-intersecting rects.
335 if (!top_left_tile.Intersects(rect))
339 TilingData::Iterator& TilingData::Iterator::operator++() {
344 if (index_x_ > right_) {
347 if (index_y_ > bottom_)
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),
362 consider_bottom_(-1),
367 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
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()) {
383 tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x());
385 tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y());
387 tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1);
389 tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1);
391 if (!ignore.IsEmpty()) {
393 tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x());
395 tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y());
397 tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1);
399 tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1);
401 // Clamp ignore indices to consider indices.
402 ignore_left_ = std::max(ignore_left_, consider_left_);
403 ignore_top_ = std::max(ignore_top_, consider_top_);
404 ignore_right_ = std::min(ignore_right_, consider_right_);
405 ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
408 if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
409 ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
414 index_x_ = consider_left_;
415 index_y_ = consider_top_;
417 if (in_ignore_rect())
421 TilingData::DifferenceIterator& TilingData::DifferenceIterator::operator++() {
426 if (in_ignore_rect())
427 index_x_ = ignore_right_ + 1;
429 if (index_x_ > consider_right_) {
430 index_x_ = consider_left_;
433 if (in_ignore_rect()) {
434 index_x_ = ignore_right_ + 1;
435 // If the ignore rect spans the whole consider rect horizontally, then
436 // ignore_right + 1 will be out of bounds.
437 if (in_ignore_rect() || index_x_ > consider_right_) {
438 index_y_ = ignore_bottom_ + 1;
439 index_x_ = consider_left_;
443 if (index_y_ > consider_bottom_)
450 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator()
451 : BaseIterator(NULL) {
455 TilingData::SpiralDifferenceIterator::SpiralDifferenceIterator(
456 const TilingData* tiling_data,
457 const gfx::Rect& consider_rect,
458 const gfx::Rect& ignore_rect,
459 const gfx::Rect& center_rect)
460 : BaseIterator(tiling_data),
464 consider_bottom_(-1),
473 horizontal_step_count_(0),
474 vertical_step_count_(0) {
475 if (tiling_data_->num_tiles_x() <= 0 || tiling_data_->num_tiles_y() <= 0) {
480 gfx::Rect tiling_bounds_rect(tiling_data_->tiling_size());
481 gfx::Rect consider(consider_rect);
482 gfx::Rect ignore(ignore_rect);
483 gfx::Rect center(center_rect);
484 consider.Intersect(tiling_bounds_rect);
485 ignore.Intersect(tiling_bounds_rect);
486 if (consider.IsEmpty()) {
492 tiling_data_->FirstBorderTileXIndexFromSrcCoord(consider.x());
493 consider_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(consider.y());
495 tiling_data_->LastBorderTileXIndexFromSrcCoord(consider.right() - 1);
497 tiling_data_->LastBorderTileYIndexFromSrcCoord(consider.bottom() - 1);
499 if (!ignore.IsEmpty()) {
500 ignore_left_ = tiling_data_->FirstBorderTileXIndexFromSrcCoord(ignore.x());
501 ignore_top_ = tiling_data_->FirstBorderTileYIndexFromSrcCoord(ignore.y());
503 tiling_data_->LastBorderTileXIndexFromSrcCoord(ignore.right() - 1);
505 tiling_data_->LastBorderTileYIndexFromSrcCoord(ignore.bottom() - 1);
507 // Clamp ignore indices to consider indices.
508 ignore_left_ = std::max(ignore_left_, consider_left_);
509 ignore_top_ = std::max(ignore_top_, consider_top_);
510 ignore_right_ = std::min(ignore_right_, consider_right_);
511 ignore_bottom_ = std::min(ignore_bottom_, consider_bottom_);
514 if (ignore_left_ == consider_left_ && ignore_right_ == consider_right_ &&
515 ignore_top_ == consider_top_ && ignore_bottom_ == consider_bottom_) {
520 // Determine around left, such that it is between -1 and num_tiles_x.
522 if (center.x() < 0 || center.IsEmpty())
524 else if (center.x() > tiling_data->tiling_size().width())
525 around_left = tiling_data->num_tiles_x();
527 around_left = tiling_data->FirstBorderTileXIndexFromSrcCoord(center.x());
529 // Determine around top, such that it is between -1 and num_tiles_y.
531 if (center.y() < 0 || center.IsEmpty())
533 else if (center.y() > tiling_data->tiling_size().height())
534 around_top = tiling_data->num_tiles_y();
536 around_top = tiling_data->FirstBorderTileYIndexFromSrcCoord(center.y());
538 // Determine around right, such that it is between -1 and num_tiles_x.
539 int right_src_coord = center.right() - 1;
540 int around_right = 0;
541 if (right_src_coord < 0 || center.IsEmpty()) {
543 } else if (right_src_coord > tiling_data->tiling_size().width()) {
544 around_right = tiling_data->num_tiles_x();
547 tiling_data->LastBorderTileXIndexFromSrcCoord(right_src_coord);
550 // Determine around bottom, such that it is between -1 and num_tiles_y.
551 int bottom_src_coord = center.bottom() - 1;
552 int around_bottom = 0;
553 if (bottom_src_coord < 0 || center.IsEmpty()) {
555 } else if (bottom_src_coord > tiling_data->tiling_size().height()) {
556 around_bottom = tiling_data->num_tiles_y();
559 tiling_data->LastBorderTileYIndexFromSrcCoord(bottom_src_coord);
562 vertical_step_count_ = around_bottom - around_top + 1;
563 horizontal_step_count_ = around_right - around_left + 1;
564 current_step_ = horizontal_step_count_ - 1;
566 index_x_ = around_right;
567 index_y_ = around_bottom;
569 // The current index is the bottom right of the around rect, which is also
570 // ignored. So we have to advance.
574 TilingData::SpiralDifferenceIterator& TilingData::SpiralDifferenceIterator::
576 int cannot_hit_consider_count = 0;
577 while (cannot_hit_consider_count < 4) {
578 if (needs_direction_switch())
581 index_x_ += delta_x_;
582 index_y_ += delta_y_;
585 if (in_consider_rect()) {
586 cannot_hit_consider_count = 0;
588 if (!in_ignore_rect())
591 // Steps needed to reach the very edge of the ignore rect, while remaining
592 // inside (so that the continue would take us outside).
593 int steps_to_edge = 0;
594 switch (direction_) {
596 steps_to_edge = index_y_ - ignore_top_;
599 steps_to_edge = index_x_ - ignore_left_;
602 steps_to_edge = ignore_bottom_ - index_y_;
605 steps_to_edge = ignore_right_ - index_x_;
609 // We need to switch directions in |max_steps|.
610 int max_steps = current_step_count() - current_step_;
612 int steps_to_take = std::min(steps_to_edge, max_steps);
613 DCHECK_GE(steps_to_take, 0);
615 index_x_ += steps_to_take * delta_x_;
616 index_y_ += steps_to_take * delta_y_;
617 current_step_ += steps_to_take;
619 int max_steps = current_step_count() - current_step_;
620 int steps_to_take = max_steps;
621 bool can_hit_consider_rect = false;
622 switch (direction_) {
624 if (valid_column() && consider_bottom_ < index_y_)
625 steps_to_take = index_y_ - consider_bottom_ - 1;
626 can_hit_consider_rect |= consider_right_ >= index_x_;
629 if (valid_row() && consider_right_ < index_x_)
630 steps_to_take = index_x_ - consider_right_ - 1;
631 can_hit_consider_rect |= consider_top_ <= index_y_;
634 if (valid_column() && consider_top_ > index_y_)
635 steps_to_take = consider_top_ - index_y_ - 1;
636 can_hit_consider_rect |= consider_left_ <= index_x_;
639 if (valid_row() && consider_left_ > index_x_)
640 steps_to_take = consider_left_ - index_x_ - 1;
641 can_hit_consider_rect |= consider_bottom_ >= index_y_;
644 steps_to_take = std::min(steps_to_take, max_steps);
645 DCHECK_GE(steps_to_take, 0);
647 index_x_ += steps_to_take * delta_x_;
648 index_y_ += steps_to_take * delta_y_;
649 current_step_ += steps_to_take;
651 if (can_hit_consider_rect)
652 cannot_hit_consider_count = 0;
654 ++cannot_hit_consider_count;
658 if (cannot_hit_consider_count >= 4)
663 bool TilingData::SpiralDifferenceIterator::needs_direction_switch() const {
664 return current_step_ >= current_step_count();
667 void TilingData::SpiralDifferenceIterator::switch_direction() {
668 int new_delta_x_ = delta_y_;
669 delta_y_ = -delta_x_;
670 delta_x_ = new_delta_x_;
673 direction_ = static_cast<Direction>((direction_ + 1) % 4);
675 if (direction_ == RIGHT || direction_ == LEFT) {
676 ++vertical_step_count_;
677 ++horizontal_step_count_;