cc/tiles/tiling_coverage_iterator.h - chromium/src.git - Git at Google

 // Copyright 2024 The Chromium Authors
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #ifndef CC_TILES_TILING_COVERAGE_ITERATOR_H_
 #define CC_TILES_TILING_COVERAGE_ITERATOR_H_

 #include <algorithm>
 #include <concepts>
 #include <utility>

 #include "base/check.h"
 #include "base/memory/raw_ptr_exclusion.h"
 #include "cc/base/tiling_data.h"
 #include "cc/cc_export.h"
 #include "cc/tiles/tile_index.h"
 #include "cc/tiles/tiling_internal.h"
 #include "ui/gfx/geometry/axis_transform2d.h"
 #include "ui/gfx/geometry/rect.h"
 #include "ui/gfx/geometry/rect_conversions.h"
 #include "ui/gfx/geometry/rect_f.h"
 #include "ui/gfx/geometry/size.h"

 namespace cc {

 // TilingCoverageIterator iterates over a generic tiling to expose the minimal
 // set of tiles required to cover a given content rectangle.
 //
 // Iteration terminates once either the content area has been fully covered by
 // by visited tiles, or all applicable tiles in the tiling have been visited.
 template <typename T>
   requires internal::Tiling<T>
 class CC_EXPORT TilingCoverageIterator {
  public:
   using Tile = typename T::Tile;

   TilingCoverageIterator() = default;

   // Constructs an iterable coverage view for `tiling` which attempts to fully
   // cover the content area given by `coverage_rect`, a rectangle that has been
   // pre-scaled by `coverage_scale` relative to layer space.
   TilingCoverageIterator(const T* tiling,
                          float coverage_scale,
                          const gfx::Rect& coverage_rect)
       : tiling_(tiling),
         coverage_rect_max_bounds_(
             ComputeCoverageRectMaxBounds(*tiling,
                                          tiling->raster_size(),
                                          coverage_scale)),
         coverage_rect_(
             gfx::IntersectRects(coverage_rect, coverage_rect_max_bounds_)),
         coverage_to_content_(
             gfx::PreScaleAxisTransform2d(tiling->raster_transform(),
                                          1 / coverage_scale)) {
     if (coverage_rect_.IsEmpty()) {
       return;
     }
     const gfx::Rect wanted_texels =
         ComputeWantedTexels(coverage_to_content_, coverage_rect_);
     const TilingData& data = *tiling->tiling_data();
     top_left_.i = data.LastBorderTileXIndexFromSrcCoord(wanted_texels.x());
     top_left_.j = data.LastBorderTileYIndexFromSrcCoord(wanted_texels.y());
     bottom_right_.i =
         1 +
         std::max(data.FirstBorderTileXIndexFromSrcCoord(wanted_texels.right()),
                  top_left_.i);
     bottom_right_.j =
         1 +
         std::max(data.FirstBorderTileYIndexFromSrcCoord(wanted_texels.bottom()),
                  top_left_.j);
     index_ = top_left_;
     AdvanceUntilTileIsRelevant();
   }

   TilingCoverageIterator(const TilingCoverageIterator&) = default;
   TilingCoverageIterator& operator=(const TilingCoverageIterator&) = default;
   ~TilingCoverageIterator() = default;

   // Returns true if and only if this iterator has been initialized for a
   // specific tiling and has not yet advanced to the end of its coverage. Other
   // methods on this object may only be called when this returns true, and the
   // value returned here may only change after assigning or incrementing the
   // iterator.
   bool IsValid() const { return index_.j < bottom_right_.j; }
   explicit operator bool() const { return IsValid(); }

   // Advances the iterator to the next unvisited tile which covers some portion
   // of the coverage rect.
   TilingCoverageIterator& operator++() {
     if (IsValid()) {
       IncrementIndex();
       AdvanceUntilTileIsRelevant();
     }
     return *this;
   }

   // The index of the current tile.
   const TileIndex& index() const { return index_; }
   int i() const { return index_.i; }
   int j() const { return index_.j; }

   // The current tile.
   Tile* operator*() const { return current_tile_; }
   Tile* operator->() const { return current_tile_; }

   // The rect covered by the current tile within the space of the coverage rect.
   const gfx::Rect& geometry_rect() const { return geometry_rect_; }

   // The rect in texture space of the current tile's intersection with the
   // coverage rect.
   gfx::RectF texture_rect() const {
     auto tex_origin = gfx::PointF(tiling_->tiling_data()
                                       ->TileBoundsWithBorder(index_.i, index_.j)
                                       .origin());

     // Convert from coverage space => content space => texture space.
     gfx::RectF texture_rect =
         coverage_to_content_.MapRect(gfx::RectF(geometry_rect_));
     texture_rect.Offset(-tex_origin.OffsetFromOrigin());
     return texture_rect;
   }

  private:
   static gfx::Rect ComputeCoverageRectMaxBounds(const T& tiling,
                                                 const gfx::Size& layer_bounds,
                                                 float coverage_scale) {
     gfx::Rect tiling_rect_in_layer_space =
         gfx::ToEnclosingRect(tiling.raster_transform().InverseMapRect(
             gfx::RectF(tiling.tiling_data()->tiling_rect())));
     tiling_rect_in_layer_space.Intersect(gfx::Rect(layer_bounds));
     return gfx::ScaleToEnclosingRect(tiling_rect_in_layer_space,
                                      coverage_scale);
   }

   static gfx::Rect ComputeWantedTexels(
       const gfx::AxisTransform2d& coverage_to_content,
       const gfx::Rect& coverage_rect) {
     gfx::RectF content_rect =
         coverage_to_content.MapRect(gfx::RectF(coverage_rect));
     content_rect.Offset(-0.5f, -0.5f);
     return gfx::ToEnclosingRect(content_rect);
   }

   void IncrementIndex() {
     ++index_.i;
     if (index_.i >= bottom_right_.i) {
       index_.i = top_left_.i;
       ++index_.j;
     }
   }

   void AdvanceUntilTileIsRelevant() {
     const TilingData& data = *tiling_->tiling_data();
     gfx::Rect last_geometry_rect;
     Tile* next_tile = nullptr;
     while (IsValid()) {
       // Calculate the current geometry rect. As we reserved overlap between
       // tiles to accommodate bilinear filtering and rounding errors in
       // destination space, the geometry rect might overlap on the edges.
       //
       // We allow the tile to overreach by 1/1024 texels to avoid seams between
       // tiles. The constant 1/1024 is picked by the fact that with bilinear
       // filtering, the maximum error in color value introduced by clamping
       // error in both u/v axis can't exceed
       // 255 * (1 - (1 - 1/1024) * (1 - 1/1024)) ~= 0.498
       // i.e. The color value can never flip over a rounding threshold.
       gfx::RectF texel_extent = data.TexelExtent(index_.i, index_.j);
       constexpr float kEpsilon = 1. / 1024.f;
       texel_extent.Inset(-kEpsilon);

       // Convert texel_extent to coverage scale, which is what we have to report
       // geometry_rect in.
       //
       // We also adjust external edges to cover the whole recorded bounds in
       // dest space if any edge of the tiling rect touches the recorded edge.
       //
       // For external edges, extend the tile to scaled recorded bounds. This is
       // needed to fully cover the coverage space because the sample extent
       // doesn't cover the last 0.5 texel to the recorded edge, and also the
       // coverage space can be rounded up for up to 1 pixel. This overhang will
       // never be sampled as the AA fragment shader clamps sample coordinate and
       // antialiasing itself.
       gfx::Rect geometry_rect = gfx::ToEnclosedRect(
           coverage_to_content_.InverseMapRect(texel_extent));
       geometry_rect.SetByBounds(
           index_.i == 0 ? coverage_rect_max_bounds_.x() : geometry_rect.x(),
           index_.j == 0 ? coverage_rect_max_bounds_.y() : geometry_rect.y(),
           index_.i == data.num_tiles_x() - 1 ? coverage_rect_max_bounds_.right()
                                              : geometry_rect.right(),
           index_.j == data.num_tiles_y() - 1
               ? coverage_rect_max_bounds_.bottom()
               : geometry_rect.bottom());
       geometry_rect.Intersect(coverage_rect_);
       if (!geometry_rect.IsEmpty()) {
         next_tile = tiling_->TileAt(index_);
         last_geometry_rect = std::exchange(geometry_rect_, geometry_rect);
         break;
       }

       IncrementIndex();
     }

     current_tile_ = next_tile;
     if (last_geometry_rect.IsEmpty()) {
       // First tile or end of iteration. Nothing more to do in either case.
       return;
     }

     // Iteration happens left->right, top->bottom.  Running off the bottom-right
     // edge is handled by the intersection above.  Here we make sure that the
     // new current geometry rect doesn't overlap with the previous one.
     int min_left, min_top;
     const bool new_row = index_.i == top_left_.i;
     if (new_row) {
       min_left = coverage_rect_.x();
       min_top = last_geometry_rect.bottom();
     } else {
       min_left = last_geometry_rect.right();
       min_top = last_geometry_rect.y();
     }
     const int inset_left = std::max(0, min_left - geometry_rect_.x());
     const int inset_top = std::max(0, min_top - geometry_rect_.y());
     geometry_rect_.Inset(gfx::Insets::TLBR(inset_top, inset_left, 0, 0));

 #if DCHECK_IS_ON()
     // Sometimes we run into an extreme case where we are at the edge of integer
     // precision. When doing so, rect calculations may end up changing values
     // unexpectedly. Unfortunately, there isn't much we can do at this point, so
     // we just do the correctness checks if both y and x offsets are
     // 'reasonable', meaning they are less than the specified value.
     static constexpr int kReasonableOffsetForDcheck = 100'000'000;
     if (!new_row && geometry_rect_.x() <= kReasonableOffsetForDcheck &&
         geometry_rect_.y() <= kReasonableOffsetForDcheck) {
       DCHECK_EQ(last_geometry_rect.right(), geometry_rect_.x());
       DCHECK_EQ(last_geometry_rect.bottom(), geometry_rect_.bottom());
       DCHECK_EQ(last_geometry_rect.y(), geometry_rect_.y());
     }
 #endif
   }

   RAW_PTR_EXCLUSION const T* tiling_;
   gfx::Rect coverage_rect_max_bounds_;
   gfx::Rect coverage_rect_;
   gfx::AxisTransform2d coverage_to_content_;
   TileIndex top_left_;
   TileIndex bottom_right_;

   TileIndex index_;
   gfx::Rect geometry_rect_;
   RAW_PTR_EXCLUSION Tile* current_tile_ = nullptr;
 };

 }  // namespace cc

 #endif  // CC_TILES_TILING_COVERAGE_ITERATOR_H_
	// Copyright 2024 The Chromium Authors
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#ifndef CC_TILES_TILING_COVERAGE_ITERATOR_H_
	#define CC_TILES_TILING_COVERAGE_ITERATOR_H_

	#include <algorithm>
	#include <concepts>
	#include <utility>

	#include "base/check.h"
	#include "base/memory/raw_ptr_exclusion.h"
	#include "cc/base/tiling_data.h"
	#include "cc/cc_export.h"
	#include "cc/tiles/tile_index.h"
	#include "cc/tiles/tiling_internal.h"
	#include "ui/gfx/geometry/axis_transform2d.h"
	#include "ui/gfx/geometry/rect.h"
	#include "ui/gfx/geometry/rect_conversions.h"
	#include "ui/gfx/geometry/rect_f.h"
	#include "ui/gfx/geometry/size.h"

	namespace cc {

	// TilingCoverageIterator iterates over a generic tiling to expose the minimal
	// set of tiles required to cover a given content rectangle.
	//
	// Iteration terminates once either the content area has been fully covered by
	// by visited tiles, or all applicable tiles in the tiling have been visited.
	template <typename T>
	requires internal::Tiling<T>
	class CC_EXPORT TilingCoverageIterator {
	public:
	using Tile = typename T::Tile;

	TilingCoverageIterator() = default;

	// Constructs an iterable coverage view for `tiling` which attempts to fully
	// cover the content area given by `coverage_rect`, a rectangle that has been
	// pre-scaled by `coverage_scale` relative to layer space.
	TilingCoverageIterator(const T* tiling,
	float coverage_scale,
	const gfx::Rect& coverage_rect)
	: tiling_(tiling),
	coverage_rect_max_bounds_(
	ComputeCoverageRectMaxBounds(*tiling,
	tiling->raster_size(),
	coverage_scale)),
	coverage_rect_(
	gfx::IntersectRects(coverage_rect, coverage_rect_max_bounds_)),
	coverage_to_content_(
	gfx::PreScaleAxisTransform2d(tiling->raster_transform(),
	1 / coverage_scale)) {
	if (coverage_rect_.IsEmpty()) {
	return;
	}
	const gfx::Rect wanted_texels =
	ComputeWantedTexels(coverage_to_content_, coverage_rect_);
	const TilingData& data = *tiling->tiling_data();
	top_left_.i = data.LastBorderTileXIndexFromSrcCoord(wanted_texels.x());
	top_left_.j = data.LastBorderTileYIndexFromSrcCoord(wanted_texels.y());
	bottom_right_.i =
	1 +
	std::max(data.FirstBorderTileXIndexFromSrcCoord(wanted_texels.right()),
	top_left_.i);
	bottom_right_.j =
	1 +
	std::max(data.FirstBorderTileYIndexFromSrcCoord(wanted_texels.bottom()),
	top_left_.j);
	index_ = top_left_;
	AdvanceUntilTileIsRelevant();
	}

	TilingCoverageIterator(const TilingCoverageIterator&) = default;
	TilingCoverageIterator& operator=(const TilingCoverageIterator&) = default;
	~TilingCoverageIterator() = default;

	// Returns true if and only if this iterator has been initialized for a
	// specific tiling and has not yet advanced to the end of its coverage. Other
	// methods on this object may only be called when this returns true, and the
	// value returned here may only change after assigning or incrementing the
	// iterator.
	bool IsValid() const { return index_.j < bottom_right_.j; }
	explicit operator bool() const { return IsValid(); }

	// Advances the iterator to the next unvisited tile which covers some portion
	// of the coverage rect.
	TilingCoverageIterator& operator++() {
	if (IsValid()) {
	IncrementIndex();
	AdvanceUntilTileIsRelevant();
	}
	return *this;
	}

	// The index of the current tile.
	const TileIndex& index() const { return index_; }
	int i() const { return index_.i; }
	int j() const { return index_.j; }

	// The current tile.
	Tile* operator*() const { return current_tile_; }
	Tile* operator->() const { return current_tile_; }

	// The rect covered by the current tile within the space of the coverage rect.
	const gfx::Rect& geometry_rect() const { return geometry_rect_; }

	// The rect in texture space of the current tile's intersection with the
	// coverage rect.
	gfx::RectF texture_rect() const {
	auto tex_origin = gfx::PointF(tiling_->tiling_data()
	->TileBoundsWithBorder(index_.i, index_.j)
	.origin());

	// Convert from coverage space => content space => texture space.
	gfx::RectF texture_rect =
	coverage_to_content_.MapRect(gfx::RectF(geometry_rect_));
	texture_rect.Offset(-tex_origin.OffsetFromOrigin());
	return texture_rect;
	}

	private:
	static gfx::Rect ComputeCoverageRectMaxBounds(const T& tiling,
	const gfx::Size& layer_bounds,
	float coverage_scale) {
	gfx::Rect tiling_rect_in_layer_space =
	gfx::ToEnclosingRect(tiling.raster_transform().InverseMapRect(
	gfx::RectF(tiling.tiling_data()->tiling_rect())));
	tiling_rect_in_layer_space.Intersect(gfx::Rect(layer_bounds));
	return gfx::ScaleToEnclosingRect(tiling_rect_in_layer_space,
	coverage_scale);
	}

	static gfx::Rect ComputeWantedTexels(
	const gfx::AxisTransform2d& coverage_to_content,
	const gfx::Rect& coverage_rect) {
	gfx::RectF content_rect =
	coverage_to_content.MapRect(gfx::RectF(coverage_rect));
	content_rect.Offset(-0.5f, -0.5f);
	return gfx::ToEnclosingRect(content_rect);
	}

	void IncrementIndex() {
	++index_.i;
	if (index_.i >= bottom_right_.i) {
	index_.i = top_left_.i;
	++index_.j;
	}
	}

	void AdvanceUntilTileIsRelevant() {
	const TilingData& data = *tiling_->tiling_data();
	gfx::Rect last_geometry_rect;
	Tile* next_tile = nullptr;
	while (IsValid()) {
	// Calculate the current geometry rect. As we reserved overlap between
	// tiles to accommodate bilinear filtering and rounding errors in
	// destination space, the geometry rect might overlap on the edges.
	//
	// We allow the tile to overreach by 1/1024 texels to avoid seams between
	// tiles. The constant 1/1024 is picked by the fact that with bilinear
	// filtering, the maximum error in color value introduced by clamping
	// error in both u/v axis can't exceed
	// 255 * (1 - (1 - 1/1024) * (1 - 1/1024)) ~= 0.498
	// i.e. The color value can never flip over a rounding threshold.
	gfx::RectF texel_extent = data.TexelExtent(index_.i, index_.j);
	constexpr float kEpsilon = 1. / 1024.f;
	texel_extent.Inset(-kEpsilon);

	// Convert texel_extent to coverage scale, which is what we have to report
	// geometry_rect in.
	//
	// We also adjust external edges to cover the whole recorded bounds in
	// dest space if any edge of the tiling rect touches the recorded edge.
	//
	// For external edges, extend the tile to scaled recorded bounds. This is
	// needed to fully cover the coverage space because the sample extent
	// doesn't cover the last 0.5 texel to the recorded edge, and also the
	// coverage space can be rounded up for up to 1 pixel. This overhang will
	// never be sampled as the AA fragment shader clamps sample coordinate and
	// antialiasing itself.
	gfx::Rect geometry_rect = gfx::ToEnclosedRect(
	coverage_to_content_.InverseMapRect(texel_extent));
	geometry_rect.SetByBounds(
	index_.i == 0 ? coverage_rect_max_bounds_.x() : geometry_rect.x(),
	index_.j == 0 ? coverage_rect_max_bounds_.y() : geometry_rect.y(),
	index_.i == data.num_tiles_x() - 1 ? coverage_rect_max_bounds_.right()
	: geometry_rect.right(),
	index_.j == data.num_tiles_y() - 1
	? coverage_rect_max_bounds_.bottom()
	: geometry_rect.bottom());
	geometry_rect.Intersect(coverage_rect_);
	if (!geometry_rect.IsEmpty()) {
	next_tile = tiling_->TileAt(index_);
	last_geometry_rect = std::exchange(geometry_rect_, geometry_rect);
	break;
	}

	IncrementIndex();
	}

	current_tile_ = next_tile;
	if (last_geometry_rect.IsEmpty()) {
	// First tile or end of iteration. Nothing more to do in either case.
	return;
	}

	// Iteration happens left->right, top->bottom. Running off the bottom-right
	// edge is handled by the intersection above. Here we make sure that the
	// new current geometry rect doesn't overlap with the previous one.
	int min_left, min_top;
	const bool new_row = index_.i == top_left_.i;
	if (new_row) {
	min_left = coverage_rect_.x();
	min_top = last_geometry_rect.bottom();
	} else {
	min_left = last_geometry_rect.right();
	min_top = last_geometry_rect.y();
	}
	const int inset_left = std::max(0, min_left - geometry_rect_.x());
	const int inset_top = std::max(0, min_top - geometry_rect_.y());
	geometry_rect_.Inset(gfx::Insets::TLBR(inset_top, inset_left, 0, 0));

	#if DCHECK_IS_ON()
	// Sometimes we run into an extreme case where we are at the edge of integer
	// precision. When doing so, rect calculations may end up changing values
	// unexpectedly. Unfortunately, there isn't much we can do at this point, so
	// we just do the correctness checks if both y and x offsets are
	// 'reasonable', meaning they are less than the specified value.
	static constexpr int kReasonableOffsetForDcheck = 100'000'000;
	if (!new_row && geometry_rect_.x() <= kReasonableOffsetForDcheck &&
	geometry_rect_.y() <= kReasonableOffsetForDcheck) {
	DCHECK_EQ(last_geometry_rect.right(), geometry_rect_.x());
	DCHECK_EQ(last_geometry_rect.bottom(), geometry_rect_.bottom());
	DCHECK_EQ(last_geometry_rect.y(), geometry_rect_.y());
	}
	#endif
	}

	RAW_PTR_EXCLUSION const T* tiling_;
	gfx::Rect coverage_rect_max_bounds_;
	gfx::Rect coverage_rect_;
	gfx::AxisTransform2d coverage_to_content_;
	TileIndex top_left_;
	TileIndex bottom_right_;

	TileIndex index_;
	gfx::Rect geometry_rect_;
	RAW_PTR_EXCLUSION Tile* current_tile_ = nullptr;
	};

	} // namespace cc

	#endif // CC_TILES_TILING_COVERAGE_ITERATOR_H_