Flutter Impeller
rect.h
Go to the documentation of this file.
1 // Copyright 2013 The Flutter 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 #ifndef FLUTTER_IMPELLER_GEOMETRY_RECT_H_
6 #define FLUTTER_IMPELLER_GEOMETRY_RECT_H_
7 
8 #include <array>
9 #include <optional>
10 #include <ostream>
11 #include <vector>
12 
13 #include "fml/logging.h"
18 #include "impeller/geometry/size.h"
19 
20 namespace impeller {
21 
22 #define ONLY_ON_FLOAT_M(Modifiers, Return) \
23  template <typename U = T> \
24  Modifiers std::enable_if_t<std::is_floating_point_v<U>, Return>
25 #define ONLY_ON_FLOAT(Return) DL_ONLY_ON_FLOAT_M(, Return)
26 
27 /// Templated struct for holding an axis-aligned rectangle.
28 ///
29 /// Rectangles are defined as 4 axis-aligned edges that might contain
30 /// space. They can be viewed as 2 X coordinates that define the
31 /// left and right edges and 2 Y coordinates that define the top and
32 /// bottom edges; or they can be viewed as an origin and horizontal
33 /// and vertical dimensions (width and height).
34 ///
35 /// When the left and right edges are equal or reversed (right <= left)
36 /// or the top and bottom edges are equal or reversed (bottom <= top),
37 /// the rectangle is considered empty. Considering the rectangle in XYWH
38 /// form, the width and/or the height would be negative or zero. Such
39 /// reversed/empty rectangles contain no space and act as such in the
40 /// methods that operate on them (Intersection, Union, IntersectsWithRect,
41 /// Contains, Cutout, etc.)
42 ///
43 /// Rectangles cannot be modified by any method and a new value can only
44 /// be stored into an existing rect using assignment. This keeps the API
45 /// clean compared to implementations that might have similar methods
46 /// that produce the answer in place, or construct a new object with
47 /// the answer, or place the result in an indicated result object.
48 ///
49 /// Methods that might fail to produce an answer will use |std::optional|
50 /// to indicate that success or failure (see |Intersection| and |CutOut|).
51 /// For convenience, |Intersection| and |Union| both have overloaded
52 /// variants that take |std::optional| arguments and treat them as if
53 /// the argument was an empty rect to allow chaining multiple such methods
54 /// and only needing to check the optional condition of the final result.
55 /// The primary methods also provide |...OrEmpty| overloaded variants that
56 /// translate an empty optional answer into a simple empty rectangle of the
57 /// same type.
58 ///
59 /// Rounding instance methods are not provided as the return value might
60 /// be wanted as another floating point rectangle or sometimes as an integer
61 /// rectangle. Instead a |RoundOut| factory, defined only for floating point
62 /// input rectangles, is provided to provide control over the result type.
63 ///
64 /// NaN and Infinity values
65 ///
66 /// Constructing an LTRB rectangle using Infinity values should work as
67 /// expected with either 0 or +Infinity returned as dimensions depending on
68 /// which side the Infinity values are on and the sign.
69 ///
70 /// Constructing an XYWH rectangle using Infinity values will usually
71 /// not work if the math requires the object to compute a right or bottom
72 /// edge from ([xy] -Infinity + [wh] +Infinity). Other combinations might
73 /// work.
74 ///
75 /// The special factory |MakeMaximum| is provided to construct a rectangle
76 /// of the indicated coordinate type that covers all finite coordinates.
77 /// It does not use infinity values, but rather the largest finite values
78 /// to avoid math that might produce a NaN value from various getters.
79 ///
80 /// Any rectangle that is constructed with, or computed to have a NaN value
81 /// will be considered the same as any empty rectangle.
82 ///
83 /// Empty Rectangle canonical results summary:
84 ///
85 /// Union will ignore any empty rects and return the other rect
86 /// Intersection will return nullopt if either rect is empty
87 /// IntersectsWithRect will return false if either rect is empty
88 /// Cutout will return the source rect if the argument is empty
89 /// Cutout will return nullopt if the source rectangle is empty
90 /// Contains(Point) will return false if the source rectangle is empty
91 /// Contains(Rect) will return false if the source rectangle is empty
92 /// Contains(Rect) will otherwise return true if the argument is empty
93 /// Specifically, EmptyRect.Contains(EmptyRect) returns false
94 ///
95 /// ---------------
96 /// Special notes on problems using the XYWH form of specifying rectangles:
97 ///
98 /// It is possible to have integer rectangles whose dimensions exceed
99 /// the maximum number that their coordinates can represent since
100 /// (MAX_INT - MIN_INT) overflows the representable positive numbers.
101 /// Floating point rectangles technically have a similar issue in that
102 /// overflow can occur, but it will be automatically converted into
103 /// either an infinity, or a finite-overflow value and still be
104 /// representable, just with little to no precision.
105 ///
106 /// Secondly, specifying a rectangle using XYWH leads to cases where the
107 /// math for (x+w) and/or (y+h) are also beyond the maximum representable
108 /// coordinates. For N-bit integer rectangles declared as XYWH, the
109 /// maximum right coordinate will require N+1 signed bits which cannot be
110 /// stored in storage that uses N-bit integers.
111 ///
112 /// Saturated math is used when constructing a rectangle from XYWH values
113 /// and when returning the dimensions of the rectangle. Constructing an
114 /// integer rectangle from values such that xy + wh is beyond the range
115 /// of the integer type will place the right or bottom edges at the maximum
116 /// value for the integer type. Similarly, constructing an integer rectangle
117 /// such that the distance from the left to the right (or top to bottom) is
118 /// greater than the range of the integer type will simply return the
119 /// maximum integer value as the dimension. Floating point rectangles are
120 /// naturally saturated by the rules of IEEE arithmetic.
121 template <class T>
122 struct TRect {
123  private:
124  using Type = T;
125 
126  public:
127  constexpr TRect() : left_(0), top_(0), right_(0), bottom_(0) {}
128 
129  constexpr static TRect MakeLTRB(Type left,
130  Type top,
131  Type right,
132  Type bottom) {
133  return TRect(left, top, right, bottom);
134  }
135 
136  constexpr static TRect MakeXYWH(Type x, Type y, Type width, Type height) {
137  return TRect(x, y, saturated::Add(x, width), saturated::Add(y, height));
138  }
139 
140  constexpr static TRect MakeWH(Type width, Type height) {
141  return TRect(0, 0, width, height);
142  }
143 
144  constexpr static TRect MakeOriginSize(const TPoint<Type>& origin,
145  const TSize<Type>& size) {
146  return MakeXYWH(origin.x, origin.y, size.width, size.height);
147  }
148 
149  template <class U>
150  constexpr static TRect MakeSize(const TSize<U>& size) {
151  return TRect(0.0, 0.0, size.width, size.height);
152  }
153 
154  /// Construct a floating point rect |Rect| from another Rect of a
155  /// potentially different storage type (eg. |IRect|).
156  template <class U, class FT = T>
157  constexpr static std::enable_if_t<std::is_floating_point_v<FT>, TRect> Make(
158  const TRect<U>& rect) {
159  return MakeLTRB(
160  static_cast<FT>(rect.GetLeft()), static_cast<FT>(rect.GetTop()),
161  static_cast<FT>(rect.GetRight()), static_cast<FT>(rect.GetBottom()));
162  }
163 
164  template <typename U>
165  constexpr static std::optional<TRect> MakePointBounds(const U& value) {
166  return MakePointBounds(value.begin(), value.end());
167  }
168 
169  template <typename PointIter>
170  constexpr static std::optional<TRect> MakePointBounds(const PointIter first,
171  const PointIter last) {
172  if (first == last) {
173  return std::nullopt;
174  }
175  auto left = first->x;
176  auto top = first->y;
177  auto right = first->x;
178  auto bottom = first->y;
179  for (auto it = first + 1; it < last; ++it) {
180  left = std::min(left, it->x);
181  top = std::min(top, it->y);
182  right = std::max(right, it->x);
183  bottom = std::max(bottom, it->y);
184  }
185  return TRect::MakeLTRB(left, top, right, bottom);
186  }
187 
188  [[nodiscard]] constexpr static TRect MakeMaximum() {
189  return TRect::MakeLTRB(std::numeric_limits<Type>::lowest(),
190  std::numeric_limits<Type>::lowest(),
191  std::numeric_limits<Type>::max(),
192  std::numeric_limits<Type>::max());
193  }
194 
195  [[nodiscard]] constexpr bool operator==(const TRect& r) const {
196  return left_ == r.left_ && //
197  top_ == r.top_ && //
198  right_ == r.right_ && //
199  bottom_ == r.bottom_;
200  }
201 
202  [[nodiscard]] constexpr bool operator!=(const TRect& r) const {
203  return !(*this == r);
204  }
205 
206  [[nodiscard]] constexpr TRect Scale(Type scale) const {
207  return TRect(left_ * scale, //
208  top_ * scale, //
209  right_ * scale, //
210  bottom_ * scale);
211  }
212 
213  [[nodiscard]] constexpr TRect Scale(Type scale_x, Type scale_y) const {
214  return TRect(left_ * scale_x, //
215  top_ * scale_y, //
216  right_ * scale_x, //
217  bottom_ * scale_y);
218  }
219 
220  [[nodiscard]] constexpr TRect Scale(TPoint<T> scale) const {
221  return Scale(scale.x, scale.y);
222  }
223 
224  [[nodiscard]] constexpr TRect Scale(TSize<T> scale) const {
225  return Scale(scale.width, scale.height);
226  }
227 
228  /// @brief Returns true iff the provided point |p| is inside the
229  /// half-open interior of this rectangle.
230  ///
231  /// For purposes of containment, a rectangle contains points
232  /// along the top and left edges but not points along the
233  /// right and bottom edges so that a point is only ever
234  /// considered inside one of two abutting rectangles.
235  [[nodiscard]] constexpr bool Contains(const TPoint<Type>& p) const {
236  return !this->IsEmpty() && //
237  p.x >= left_ && //
238  p.y >= top_ && //
239  p.x < right_ && //
240  p.y < bottom_;
241  }
242 
243  /// @brief Returns true iff the provided point |p| is inside the
244  /// closed-range interior of this rectangle.
245  ///
246  /// Unlike the regular |Contains(TPoint)| method, this method
247  /// considers all points along the boundary of the rectangle
248  /// to be contained within the rectangle - useful for testing
249  /// if vertices that define a filled shape would carry the
250  /// interior of that shape outside the bounds of the rectangle.
251  /// Since both geometries are defining half-open spaces, their
252  /// defining geometry needs to consider their boundaries to
253  /// be equivalent with respect to interior and exterior.
254  [[nodiscard]] constexpr bool ContainsInclusive(const TPoint<Type>& p) const {
255  return !this->IsEmpty() && //
256  p.x >= left_ && //
257  p.y >= top_ && //
258  p.x <= right_ && //
259  p.y <= bottom_;
260  }
261 
262  /// @brief Returns true iff this rectangle is not empty and it also
263  /// contains every point considered inside the provided
264  /// rectangle |o| (as determined by |Contains(TPoint)|).
265  ///
266  /// This is similar to a definition where the result is true iff
267  /// the union of the two rectangles is equal to this rectangle,
268  /// ignoring precision issues with performing those operations
269  /// and assuming that empty rectangles are never equal.
270  ///
271  /// An empty rectangle can contain no other rectangle.
272  ///
273  /// An empty rectangle is, however, contained within any
274  /// other non-empy rectangle as the set of points it contains
275  /// is an empty set and so there are no points to fail the
276  /// containment criteria.
277  [[nodiscard]] constexpr bool Contains(const TRect& o) const {
278  return !this->IsEmpty() && //
279  (o.IsEmpty() || (o.left_ >= left_ && //
280  o.top_ >= top_ && //
281  o.right_ <= right_ && //
282  o.bottom_ <= bottom_));
283  }
284 
285  /// @brief Returns true if all of the fields of this floating point
286  /// rectangle are finite.
287  ///
288  /// Note that the results of |GetWidth()| and |GetHeight()| may
289  /// still be infinite due to overflow even if the fields themselves
290  /// are finite.
291  ONLY_ON_FLOAT_M([[nodiscard]] constexpr, bool)
292  IsFinite() const {
293  return std::isfinite(left_) && //
294  std::isfinite(top_) && //
295  std::isfinite(right_) && //
296  std::isfinite(bottom_);
297  }
298 
299  /// @brief Returns true if either of the width or height are 0, negative,
300  /// or NaN.
301  [[nodiscard]] constexpr bool IsEmpty() const {
302  // Computing the non-empty condition and negating the result causes any
303  // NaN value to return true - i.e. is considered empty.
304  return !(left_ < right_ && top_ < bottom_);
305  }
306 
307  /// @brief Returns true if width and height are equal and neither is NaN.
308  [[nodiscard]] constexpr bool IsSquare() const {
309  // empty rectangles can technically be "square", but would be
310  // misleading to most callers. Using |IsEmpty| also prevents
311  // "non-empty and non-overflowing" computations from happening
312  // to be equal to "empty and overflowing" results.
313  // (Consider LTRB(10, 15, MAX-2, MIN+2) which is empty, but both
314  // w/h subtractions equal "5").
315  return !IsEmpty() && (right_ - left_) == (bottom_ - top_);
316  }
317 
318  [[nodiscard]] constexpr bool IsMaximum() const {
319  return *this == MakeMaximum();
320  }
321 
322  /// @brief Returns the upper left corner of the rectangle as specified
323  /// by the left/top or x/y values when it was constructed.
324  [[nodiscard]] constexpr TPoint<Type> GetOrigin() const {
325  return {left_, top_};
326  }
327 
328  /// @brief Returns the size of the rectangle which may be negative in
329  /// either width or height and may have been clipped to the
330  /// maximum integer values for integer rects whose size overflows.
331  [[nodiscard]] constexpr TSize<Type> GetSize() const {
332  return {GetWidth(), GetHeight()};
333  }
334 
335  /// @brief Returns the X coordinate of the upper left corner, equivalent
336  /// to |GetOrigin().x|
337  [[nodiscard]] constexpr Type GetX() const { return left_; }
338 
339  /// @brief Returns the Y coordinate of the upper left corner, equivalent
340  /// to |GetOrigin().y|
341  [[nodiscard]] constexpr Type GetY() const { return top_; }
342 
343  /// @brief Returns the width of the rectangle, equivalent to
344  /// |GetSize().width|
345  [[nodiscard]] constexpr Type GetWidth() const {
346  return saturated::Sub(right_, left_);
347  }
348 
349  /// @brief Returns the height of the rectangle, equivalent to
350  /// |GetSize().height|
351  [[nodiscard]] constexpr Type GetHeight() const {
352  return saturated::Sub(bottom_, top_);
353  }
354 
355  [[nodiscard]] constexpr auto GetLeft() const { return left_; }
356 
357  [[nodiscard]] constexpr auto GetTop() const { return top_; }
358 
359  [[nodiscard]] constexpr auto GetRight() const { return right_; }
360 
361  [[nodiscard]] constexpr auto GetBottom() const { return bottom_; }
362 
363  [[nodiscard]] constexpr TPoint<T> GetLeftTop() const { //
364  return {left_, top_};
365  }
366 
367  [[nodiscard]] constexpr TPoint<T> GetRightTop() const {
368  return {right_, top_};
369  }
370 
371  [[nodiscard]] constexpr TPoint<T> GetLeftBottom() const {
372  return {left_, bottom_};
373  }
374 
375  [[nodiscard]] constexpr TPoint<T> GetRightBottom() const {
376  return {right_, bottom_};
377  }
378 
379  /// @brief Get the area of the rectangle, equivalent to |GetSize().Area()|
380  [[nodiscard]] constexpr T Area() const {
381  // TODO(141710): Use saturated math to avoid overflow.
382  return IsEmpty() ? 0 : (right_ - left_) * (bottom_ - top_);
383  }
384 
385  /// @brief Get the center point as a |Point|.
386  [[nodiscard]] constexpr Point GetCenter() const {
387  return {saturated::AverageScalar(left_, right_),
388  saturated::AverageScalar(top_, bottom_)};
389  }
390 
391  [[nodiscard]] constexpr std::array<T, 4> GetLTRB() const {
392  return {left_, top_, right_, bottom_};
393  }
394 
395  /// @brief Get the x, y coordinates of the origin and the width and
396  /// height of the rectangle in an array.
397  [[nodiscard]] constexpr std::array<T, 4> GetXYWH() const {
398  return {left_, top_, GetWidth(), GetHeight()};
399  }
400 
401  /// @brief Get a version of this rectangle that has a non-negative size.
402  [[nodiscard]] constexpr TRect GetPositive() const {
403  if (!IsEmpty()) {
404  return *this;
405  }
406  return {
407  std::min(left_, right_),
408  std::min(top_, bottom_),
409  std::max(left_, right_),
410  std::max(top_, bottom_),
411  };
412  }
413 
414  /// @brief Get the points that represent the 4 corners of this rectangle
415  /// in a Z order that is compatible with triangle strips or a set
416  /// of all zero points if the rectangle is empty.
417  /// The order is: Top left, top right, bottom left, bottom right.
418  [[nodiscard]] constexpr std::array<TPoint<T>, 4> GetPoints() const {
419  if (IsEmpty()) {
420  return {};
421  }
422  return {
423  TPoint{left_, top_},
424  TPoint{right_, top_},
425  TPoint{left_, bottom_},
426  TPoint{right_, bottom_},
427  };
428  }
429 
430  [[nodiscard]] constexpr std::array<TPoint<T>, 4> GetTransformedPoints(
431  const Matrix& transform) const {
432  auto points = GetPoints();
433  for (size_t i = 0; i < points.size(); i++) {
434  points[i] = transform * points[i];
435  }
436  return points;
437  }
438 
439  /// @brief Creates a new bounding box that contains this transformed
440  /// rectangle, clipped against the near clipping plane if
441  /// necessary.
442  [[nodiscard]] constexpr TRect TransformAndClipBounds(
443  const Matrix& transform) const {
444  if (!transform.HasPerspective2D()) {
445  return TransformBounds(transform);
446  }
447 
448  if (IsEmpty()) {
449  return {};
450  }
451 
452  auto ul = transform.TransformHomogenous({left_, top_});
453  auto ur = transform.TransformHomogenous({right_, top_});
454  auto ll = transform.TransformHomogenous({left_, bottom_});
455  auto lr = transform.TransformHomogenous({right_, bottom_});
456 
457  // It can probably be proven that we only ever have 5 points at most
458  // which happens when only 1 corner is clipped and we get 2 points
459  // in return for it as we interpolate against its neighbors.
460  Point points[8];
461  int index = 0;
462 
463  // Process (clip and interpolate) each point against its 2 neighbors:
464  // left, pt, right
465  index = ClipAndInsert(points, index, ll, ul, ur);
466  index = ClipAndInsert(points, index, ul, ur, lr);
467  index = ClipAndInsert(points, index, ur, lr, ll);
468  index = ClipAndInsert(points, index, lr, ll, ul);
469 
470  auto bounds = TRect::MakePointBounds(points, points + index);
471  return bounds.value_or(TRect{});
472  }
473 
474  /// @brief Creates a new bounding box that contains this transformed
475  /// rectangle.
476  [[nodiscard]] constexpr TRect TransformBounds(const Matrix& transform) const {
477  if (IsEmpty()) {
478  return {};
479  }
481  auto bounds = TRect::MakePointBounds(points.begin(), points.end());
482  if (bounds.has_value()) {
483  return bounds.value();
484  }
485  FML_UNREACHABLE();
486  }
487 
488  /// @brief Constructs a Matrix that will map all points in the coordinate
489  /// space of the rectangle into a new normalized coordinate space
490  /// where the upper left corner of the rectangle maps to (0, 0)
491  /// and the lower right corner of the rectangle maps to (1, 1).
492  ///
493  /// Empty and non-finite rectangles will return a zero-scaling
494  /// transform that maps all points to (0, 0).
495  [[nodiscard]] constexpr Matrix GetNormalizingTransform() const {
496  if (!IsEmpty()) {
497  Scalar sx = 1.0 / GetWidth();
498  Scalar sy = 1.0 / GetHeight();
499  Scalar tx = left_ * -sx;
500  Scalar ty = top_ * -sy;
501 
502  // Exclude NaN and infinities and either scale underflowing to zero
503  if (sx != 0.0 && sy != 0.0 && 0.0 * sx * sy * tx * ty == 0.0) {
504  // clang-format off
505  return Matrix( sx, 0.0f, 0.0f, 0.0f,
506  0.0f, sy, 0.0f, 0.0f,
507  0.0f, 0.0f, 1.0f, 0.0f,
508  tx, ty, 0.0f, 1.0f);
509  // clang-format on
510  }
511  }
512 
513  // Map all coordinates to the origin.
514  return Matrix::MakeScale({0.0f, 0.0f, 1.0f});
515  }
516 
517  [[nodiscard]] constexpr TRect Union(const TRect& o) const {
518  if (IsEmpty()) {
519  return o;
520  }
521  if (o.IsEmpty()) {
522  return *this;
523  }
524  return {
525  std::min(left_, o.left_),
526  std::min(top_, o.top_),
527  std::max(right_, o.right_),
528  std::max(bottom_, o.bottom_),
529  };
530  }
531 
532  [[nodiscard]] constexpr std::optional<TRect> Intersection(
533  const TRect& o) const {
534  if (IntersectsWithRect(o)) {
535  return TRect{
536  std::max(left_, o.left_),
537  std::max(top_, o.top_),
538  std::min(right_, o.right_),
539  std::min(bottom_, o.bottom_),
540  };
541  } else {
542  return std::nullopt;
543  }
544  }
545 
546  [[nodiscard]] constexpr TRect IntersectionOrEmpty(const TRect& o) const {
547  return Intersection(o).value_or(TRect());
548  }
549 
550  [[nodiscard]] constexpr bool IntersectsWithRect(const TRect& o) const {
551  return !IsEmpty() && //
552  !o.IsEmpty() && //
553  left_ < o.right_ && //
554  top_ < o.bottom_ && //
555  right_ > o.left_ && //
556  bottom_ > o.top_;
557  }
558 
559  /// @brief Returns the new boundary rectangle that would result from this
560  /// rectangle being cut out by the specified rectangle.
561  [[nodiscard]] constexpr std::optional<TRect<T>> Cutout(const TRect& o) const {
562  if (IsEmpty()) {
563  // This test isn't just a short-circuit, it also prevents the concise
564  // math below from returning the wrong answer on empty rects.
565  // Once we know that this rectangle is not empty, the math below can
566  // only succeed in computing a value if o is also non-empty and non-nan.
567  // Otherwise, the method returns *this by default.
568  return std::nullopt;
569  }
570 
571  const auto& [a_left, a_top, a_right, a_bottom] = GetLTRB(); // Source rect.
572  const auto& [b_left, b_top, b_right, b_bottom] = o.GetLTRB(); // Cutout.
573  if (b_left <= a_left && b_right >= a_right) {
574  if (b_top <= a_top && b_bottom >= a_bottom) {
575  // Full cutout.
576  return std::nullopt;
577  }
578  if (b_top <= a_top && b_bottom > a_top) {
579  // Cuts off the top.
580  return TRect::MakeLTRB(a_left, b_bottom, a_right, a_bottom);
581  }
582  if (b_bottom >= a_bottom && b_top < a_bottom) {
583  // Cuts off the bottom.
584  return TRect::MakeLTRB(a_left, a_top, a_right, b_top);
585  }
586  }
587  if (b_top <= a_top && b_bottom >= a_bottom) {
588  if (b_left <= a_left && b_right > a_left) {
589  // Cuts off the left.
590  return TRect::MakeLTRB(b_right, a_top, a_right, a_bottom);
591  }
592  if (b_right >= a_right && b_left < a_right) {
593  // Cuts off the right.
594  return TRect::MakeLTRB(a_left, a_top, b_left, a_bottom);
595  }
596  }
597 
598  return *this;
599  }
600 
601  [[nodiscard]] constexpr TRect CutoutOrEmpty(const TRect& o) const {
602  return Cutout(o).value_or(TRect());
603  }
604 
605  /// @brief Returns a new rectangle translated by the given offset.
606  [[nodiscard]] constexpr TRect<T> Shift(T dx, T dy) const {
607  return {
608  saturated::Add(left_, dx), //
609  saturated::Add(top_, dy), //
610  saturated::Add(right_, dx), //
611  saturated::Add(bottom_, dy), //
612  };
613  }
614 
615  /// @brief Returns a new rectangle translated by the given offset.
616  [[nodiscard]] constexpr TRect<T> Shift(TPoint<T> offset) const {
617  return Shift(offset.x, offset.y);
618  }
619 
620  /// @brief Returns a rectangle with expanded edges. Negative expansion
621  /// results in shrinking.
622  [[nodiscard]] constexpr TRect<T> Expand(T left,
623  T top,
624  T right,
625  T bottom) const {
626  return {
627  saturated::Sub(left_, left), //
628  saturated::Sub(top_, top), //
629  saturated::Add(right_, right), //
630  saturated::Add(bottom_, bottom), //
631  };
632  }
633 
634  /// @brief Returns a rectangle with expanded edges in all directions.
635  /// Negative expansion results in shrinking.
636  [[nodiscard]] constexpr TRect<T> Expand(T amount) const {
637  return {
638  saturated::Sub(left_, amount), //
639  saturated::Sub(top_, amount), //
640  saturated::Add(right_, amount), //
641  saturated::Add(bottom_, amount), //
642  };
643  }
644 
645  /// @brief Returns a rectangle with expanded edges in all directions.
646  /// Negative expansion results in shrinking.
647  [[nodiscard]] constexpr TRect<T> Expand(T horizontal_amount,
648  T vertical_amount) const {
649  return {
650  saturated::Sub(left_, horizontal_amount), //
651  saturated::Sub(top_, vertical_amount), //
652  saturated::Add(right_, horizontal_amount), //
653  saturated::Add(bottom_, vertical_amount), //
654  };
655  }
656 
657  /// @brief Returns a rectangle with expanded edges in all directions.
658  /// Negative expansion results in shrinking.
659  [[nodiscard]] constexpr TRect<T> Expand(TPoint<T> amount) const {
660  return Expand(amount.x, amount.y);
661  }
662 
663  /// @brief Returns a rectangle with expanded edges in all directions.
664  /// Negative expansion results in shrinking.
665  [[nodiscard]] constexpr TRect<T> Expand(TSize<T> amount) const {
666  return Expand(amount.width, amount.height);
667  }
668 
669  /// @brief Returns a new rectangle that represents the projection of the
670  /// source rectangle onto this rectangle. In other words, the source
671  /// rectangle is redefined in terms of the coordinate space of this
672  /// rectangle.
673  [[nodiscard]] constexpr TRect<T> Project(TRect<T> source) const {
674  if (IsEmpty()) {
675  return {};
676  }
677  return source.Shift(-left_, -top_)
678  .Scale(1.0 / static_cast<Scalar>(GetWidth()),
679  1.0 / static_cast<Scalar>(GetHeight()));
680  }
681 
682  ONLY_ON_FLOAT_M([[nodiscard]] constexpr static, TRect)
683  RoundOut(const TRect<U>& r) {
684  return TRect::MakeLTRB(saturated::Cast<U, Type>(floor(r.GetLeft())),
685  saturated::Cast<U, Type>(floor(r.GetTop())),
686  saturated::Cast<U, Type>(ceil(r.GetRight())),
687  saturated::Cast<U, Type>(ceil(r.GetBottom())));
688  }
689 
690  ONLY_ON_FLOAT_M([[nodiscard]] constexpr static, TRect)
691  RoundIn(const TRect<U>& r) {
692  return TRect::MakeLTRB(saturated::Cast<U, Type>(ceil(r.GetLeft())),
693  saturated::Cast<U, Type>(ceil(r.GetTop())),
694  saturated::Cast<U, Type>(floor(r.GetRight())),
695  saturated::Cast<U, Type>(floor(r.GetBottom())));
696  }
697 
698  ONLY_ON_FLOAT_M([[nodiscard]] constexpr static, TRect)
699  Round(const TRect<U>& r) {
700  return TRect::MakeLTRB(saturated::Cast<U, Type>(round(r.GetLeft())),
701  saturated::Cast<U, Type>(round(r.GetTop())),
702  saturated::Cast<U, Type>(round(r.GetRight())),
703  saturated::Cast<U, Type>(round(r.GetBottom())));
704  }
705 
706  [[nodiscard]] constexpr static TRect Union(const TRect& a,
707  const std::optional<TRect> b) {
708  return b.has_value() ? a.Union(b.value()) : a;
709  }
710 
711  [[nodiscard]] constexpr static TRect Union(const std::optional<TRect> a,
712  const TRect& b) {
713  return a.has_value() ? a->Union(b) : b;
714  }
715 
716  [[nodiscard]] constexpr static std::optional<TRect> Union(
717  const std::optional<TRect> a,
718  const std::optional<TRect> b) {
719  return a.has_value() ? Union(a.value(), b) : b;
720  }
721 
722  [[nodiscard]] constexpr static std::optional<TRect> Intersection(
723  const TRect& a,
724  const std::optional<TRect> b) {
725  return b.has_value() ? a.Intersection(b.value()) : a;
726  }
727 
728  [[nodiscard]] constexpr static std::optional<TRect> Intersection(
729  const std::optional<TRect> a,
730  const TRect& b) {
731  return a.has_value() ? a->Intersection(b) : b;
732  }
733 
734  [[nodiscard]] constexpr static std::optional<TRect> Intersection(
735  const std::optional<TRect> a,
736  const std::optional<TRect> b) {
737  return a.has_value() ? Intersection(a.value(), b) : b;
738  }
739 
740  private:
741  constexpr TRect(Type left, Type top, Type right, Type bottom)
742  : left_(left), top_(top), right_(right), bottom_(bottom) {}
743 
744  Type left_;
745  Type top_;
746  Type right_;
747  Type bottom_;
748 
749  static constexpr Scalar kMinimumHomogenous = 1.0f / (1 << 14);
750 
751  // Clip p against the near clipping plane (W = kMinimumHomogenous)
752  // and interpolate a crossing point against the nearby neighbors
753  // left and right if p is clipped and either of them is not.
754  // This method can produce 0, 1, or 2 points per call depending on
755  // how many of the points are clipped.
756  // 0 - all points are clipped
757  // 1 - p is unclipped OR
758  // p is clipped and exactly one of the neighbors is not
759  // 2 - p is clipped and both neighbors are not
760  static constexpr int ClipAndInsert(Point clipped[],
761  int index,
762  const Vector3& left,
763  const Vector3& p,
764  const Vector3& right) {
765  if (p.z >= kMinimumHomogenous) {
766  clipped[index++] = {p.x / p.z, p.y / p.z};
767  } else {
768  index = InterpolateAndInsert(clipped, index, p, left);
769  index = InterpolateAndInsert(clipped, index, p, right);
770  }
771  return index;
772  }
773 
774  // Interpolate (a clipped) point p against one of its neighbors
775  // and insert the point into the array where the line between them
776  // veers from clipped space to unclipped, if such a point exists.
777  static constexpr int InterpolateAndInsert(Point clipped[],
778  int index,
779  const Vector3& p,
780  const Vector3& neighbor) {
781  if (neighbor.z >= kMinimumHomogenous) {
782  auto t = (kMinimumHomogenous - p.z) / (neighbor.z - p.z);
783  clipped[index++] = {
784  (t * p.x + (1.0f - t) * neighbor.x) / kMinimumHomogenous,
785  (t * p.y + (1.0f - t) * neighbor.y) / kMinimumHomogenous,
786  };
787  }
788  return index;
789  }
790 };
791 
795 using IRect = IRect64;
796 
797 #undef ONLY_ON_FLOAT
798 #undef ONLY_ON_FLOAT_M
799 
800 } // namespace impeller
801 
802 namespace std {
803 
804 template <class T>
805 inline std::ostream& operator<<(std::ostream& out,
806  const impeller::TRect<T>& r) {
807  out << "(" << r.GetLeftTop() << " => " << r.GetRightBottom() << ")";
808  return out;
809 }
810 
811 } // namespace std
812 
813 #endif // FLUTTER_IMPELLER_GEOMETRY_RECT_H_
int32_t value
int32_t x
float Scalar
Definition: scalar.h:19
TPoint< Scalar > Point
Definition: point.h:327
TRect< int64_t > IRect64
Definition: rect.h:794
Definition: comparable.h:95
std::ostream & operator<<(std::ostream &out, const impeller::Arc &a)
Definition: arc.h:141
#define ONLY_ON_FLOAT_M(Modifiers, Return)
Definition: rect.h:22
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
static constexpr Matrix MakeScale(const Vector3 &s)
Definition: matrix.h:104
constexpr TRect< T > Expand(T left, T top, T right, T bottom) const
Returns a rectangle with expanded edges. Negative expansion results in shrinking.
Definition: rect.h:622
constexpr auto GetBottom() const
Definition: rect.h:361
constexpr Type GetY() const
Returns the Y coordinate of the upper left corner, equivalent to |GetOrigin().y|.
Definition: rect.h:341
constexpr TRect TransformBounds(const Matrix &transform) const
Creates a new bounding box that contains this transformed rectangle.
Definition: rect.h:476
constexpr TRect< T > Project(TRect< T > source) const
Returns a new rectangle that represents the projection of the source rectangle onto this rectangle....
Definition: rect.h:673
constexpr bool ContainsInclusive(const TPoint< Type > &p) const
Returns true iff the provided point |p| is inside the closed-range interior of this rectangle.
Definition: rect.h:254
constexpr auto GetTop() const
Definition: rect.h:357
constexpr Type GetHeight() const
Returns the height of the rectangle, equivalent to |GetSize().height|.
Definition: rect.h:351
constexpr TPoint< Type > GetOrigin() const
Returns the upper left corner of the rectangle as specified by the left/top or x/y values when it was...
Definition: rect.h:324
constexpr TRect Scale(TPoint< T > scale) const
Definition: rect.h:220
constexpr TRect< T > Expand(TPoint< T > amount) const
Returns a rectangle with expanded edges in all directions. Negative expansion results in shrinking.
Definition: rect.h:659
constexpr bool IsMaximum() const
Definition: rect.h:318
constexpr std::optional< TRect > Intersection(const TRect &o) const
Definition: rect.h:532
constexpr bool IsEmpty() const
Returns true if either of the width or height are 0, negative, or NaN.
Definition: rect.h:301
constexpr T Area() const
Get the area of the rectangle, equivalent to |GetSize().Area()|.
Definition: rect.h:380
constexpr static TRect MakeOriginSize(const TPoint< Type > &origin, const TSize< Type > &size)
Definition: rect.h:144
constexpr bool Contains(const TPoint< Type > &p) const
Returns true iff the provided point |p| is inside the half-open interior of this rectangle.
Definition: rect.h:235
constexpr static TRect Union(const TRect &a, const std::optional< TRect > b)
Definition: rect.h:706
constexpr TRect Union(const TRect &o) const
Definition: rect.h:517
constexpr TRect Scale(Type scale_x, Type scale_y) const
Definition: rect.h:213
constexpr std::array< TPoint< T >, 4 > GetPoints() const
Get the points that represent the 4 corners of this rectangle in a Z order that is compatible with tr...
Definition: rect.h:418
constexpr bool IntersectsWithRect(const TRect &o) const
Definition: rect.h:550
constexpr auto GetLeft() const
Definition: rect.h:355
RoundIn(const TRect< U > &r)
Definition: rect.h:691
constexpr TRect CutoutOrEmpty(const TRect &o) const
Definition: rect.h:601
constexpr static TRect MakeWH(Type width, Type height)
Definition: rect.h:140
constexpr static std::optional< TRect > MakePointBounds(const U &value)
Definition: rect.h:165
constexpr TSize< Type > GetSize() const
Returns the size of the rectangle which may be negative in either width or height and may have been c...
Definition: rect.h:331
constexpr TRect< T > Expand(T horizontal_amount, T vertical_amount) const
Returns a rectangle with expanded edges in all directions. Negative expansion results in shrinking.
Definition: rect.h:647
Round(const TRect< U > &r)
Definition: rect.h:699
RoundOut(const TRect< U > &r)
Definition: rect.h:683
constexpr TRect GetPositive() const
Get a version of this rectangle that has a non-negative size.
Definition: rect.h:402
constexpr TRect Scale(TSize< T > scale) const
Definition: rect.h:224
constexpr Type GetX() const
Returns the X coordinate of the upper left corner, equivalent to |GetOrigin().x|.
Definition: rect.h:337
constexpr auto GetRight() const
Definition: rect.h:359
constexpr bool IsSquare() const
Returns true if width and height are equal and neither is NaN.
Definition: rect.h:308
constexpr static std::optional< TRect > Intersection(const std::optional< TRect > a, const std::optional< TRect > b)
Definition: rect.h:734
constexpr bool Contains(const TRect &o) const
Returns true iff this rectangle is not empty and it also contains every point considered inside the p...
Definition: rect.h:277
IsFinite() const
Returns true if all of the fields of this floating point rectangle are finite.
Definition: rect.h:292
constexpr Matrix GetNormalizingTransform() const
Constructs a Matrix that will map all points in the coordinate space of the rectangle into a new norm...
Definition: rect.h:495
constexpr static std::optional< TRect > Union(const std::optional< TRect > a, const std::optional< TRect > b)
Definition: rect.h:716
constexpr bool operator!=(const TRect &r) const
Definition: rect.h:202
constexpr TRect Scale(Type scale) const
Definition: rect.h:206
constexpr static TRect MakeXYWH(Type x, Type y, Type width, Type height)
Definition: rect.h:136
constexpr TPoint< T > GetLeftBottom() const
Definition: rect.h:371
constexpr std::array< TPoint< T >, 4 > GetTransformedPoints(const Matrix &transform) const
Definition: rect.h:430
constexpr TRect TransformAndClipBounds(const Matrix &transform) const
Creates a new bounding box that contains this transformed rectangle, clipped against the near clippin...
Definition: rect.h:442
constexpr static TRect Union(const std::optional< TRect > a, const TRect &b)
Definition: rect.h:711
constexpr TRect< T > Shift(TPoint< T > offset) const
Returns a new rectangle translated by the given offset.
Definition: rect.h:616
constexpr TPoint< T > GetRightTop() const
Definition: rect.h:367
constexpr TRect< T > Expand(T amount) const
Returns a rectangle with expanded edges in all directions. Negative expansion results in shrinking.
Definition: rect.h:636
constexpr static std::optional< TRect > MakePointBounds(const PointIter first, const PointIter last)
Definition: rect.h:170
constexpr TRect< T > Shift(T dx, T dy) const
Returns a new rectangle translated by the given offset.
Definition: rect.h:606
constexpr static TRect MakeSize(const TSize< U > &size)
Definition: rect.h:150
constexpr Type GetWidth() const
Returns the width of the rectangle, equivalent to |GetSize().width|.
Definition: rect.h:345
constexpr TPoint< T > GetRightBottom() const
Definition: rect.h:375
constexpr std::array< T, 4 > GetLTRB() const
Definition: rect.h:391
constexpr static std::enable_if_t< std::is_floating_point_v< FT >, TRect > Make(const TRect< U > &rect)
Definition: rect.h:157
constexpr TRect< T > Expand(TSize< T > amount) const
Returns a rectangle with expanded edges in all directions. Negative expansion results in shrinking.
Definition: rect.h:665
constexpr static std::optional< TRect > Intersection(const TRect &a, const std::optional< TRect > b)
Definition: rect.h:722
constexpr Point GetCenter() const
Get the center point as a |Point|.
Definition: rect.h:386
constexpr TRect IntersectionOrEmpty(const TRect &o) const
Definition: rect.h:546
constexpr TRect()
Definition: rect.h:127
constexpr static std::optional< TRect > Intersection(const std::optional< TRect > a, const TRect &b)
Definition: rect.h:728
constexpr std::optional< TRect< T > > Cutout(const TRect &o) const
Returns the new boundary rectangle that would result from this rectangle being cut out by the specifi...
Definition: rect.h:561
constexpr TPoint< T > GetLeftTop() const
Definition: rect.h:363
constexpr bool operator==(const TRect &r) const
Definition: rect.h:195
constexpr std::array< T, 4 > GetXYWH() const
Get the x, y coordinates of the origin and the width and height of the rectangle in an array.
Definition: rect.h:397
constexpr static TRect MakeLTRB(Type left, Type top, Type right, Type bottom)
Definition: rect.h:129
constexpr static TRect MakeMaximum()
Definition: rect.h:188
Type height
Definition: size.h:29
Type width
Definition: size.h:28
std::vector< Point > points