| 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"
14 #include "impeller/geometry/matrix.h"
15 #include "impeller/geometry/point.h"
16 #include "impeller/geometry/saturated_math.h"
17 #include "impeller/geometry/scalar.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 TRect Scale(Type scale) const {
203 return TRect(left_ * scale, //
204 top_ * scale, //
205 right_ * scale, //
206 bottom_ * scale);
207 }
208
209 [[nodiscard]] constexpr TRect Scale(Type scale_x, Type scale_y) const {
210 return TRect(left_ * scale_x, //
211 top_ * scale_y, //
212 right_ * scale_x, //
213 bottom_ * scale_y);
214 }
215
216 [[nodiscard]] constexpr TRect Scale(TPoint<T> scale) const {
217 return Scale(scale.x, scale.y);
218 }
219
220 [[nodiscard]] constexpr TRect Scale(TSize<T> scale) const {
221 return Scale(scale.width, scale.height);
222 }
223
224 /// @brief Returns true iff the provided point |p| is inside the
225 /// half-open interior of this rectangle.
226 ///
227 /// For purposes of containment, a rectangle contains points
228 /// along the top and left edges but not points along the
229 /// right and bottom edges so that a point is only ever
230 /// considered inside one of two abutting rectangles.
231 [[nodiscard]] constexpr bool Contains(const TPoint<Type>& p) const {
232 return !this->IsEmpty() && //
233 p.x >= left_ && //
234 p.y >= top_ && //
235 p.x < right_ && //
236 p.y < bottom_;
237 }
238
239 /// @brief Returns true iff the provided point |p| is inside the
240 /// closed-range interior of this rectangle.
241 ///
242 /// Unlike the regular |Contains(TPoint)| method, this method
243 /// considers all points along the boundary of the rectangle
244 /// to be contained within the rectangle - useful for testing
245 /// if vertices that define a filled shape would carry the
246 /// interior of that shape outside the bounds of the rectangle.
247 /// Since both geometries are defining half-open spaces, their
248 /// defining geometry needs to consider their boundaries to
249 /// be equivalent with respect to interior and exterior.
250 [[nodiscard]] constexpr bool ContainsInclusive(const TPoint<Type>& p) const {
251 return !this->IsEmpty() && //
252 p.x >= left_ && //
253 p.y >= top_ && //
254 p.x <= right_ && //
255 p.y <= bottom_;
256 }
257
258 /// @brief Returns true iff this rectangle is not empty and it also
259 /// contains every point considered inside the provided
260 /// rectangle |o| (as determined by |Contains(TPoint)|).
261 ///
262 /// This is similar to a definition where the result is true iff
263 /// the union of the two rectangles is equal to this rectangle,
264 /// ignoring precision issues with performing those operations
265 /// and assuming that empty rectangles are never equal.
266 ///
267 /// An empty rectangle can contain no other rectangle.
268 ///
269 /// An empty rectangle is, however, contained within any
270 /// other non-empy rectangle as the set of points it contains
271 /// is an empty set and so there are no points to fail the
272 /// containment criteria.
273 [[nodiscard]] constexpr bool Contains(const TRect& o) const {
274 return !this->IsEmpty() && //
275 (o.IsEmpty() || (o.left_ >= left_ && //
276 o.top_ >= top_ && //
277 o.right_ <= right_ && //
278 o.bottom_ <= bottom_));
279 }
280
281 /// @brief Returns true if all of the fields of this floating point
282 /// rectangle are finite.
283 ///
284 /// Note that the results of |GetWidth()| and |GetHeight()| may
285 /// still be infinite due to overflow even if the fields themselves
286 /// are finite.
287 ONLY_ON_FLOAT_M([[nodiscard]] constexpr, bool)
288 IsFinite() const {
289 return std::isfinite(left_) && //
290 std::isfinite(top_) && //
291 std::isfinite(right_) && //
292 std::isfinite(bottom_);
293 }
294
295 /// @brief Returns true if either of the width or height are 0, negative,
296 /// or NaN.
297 [[nodiscard]] constexpr bool IsEmpty() const {
298 // Computing the non-empty condition and negating the result causes any
299 // NaN value to return true - i.e. is considered empty.
300 return !(left_ < right_ && top_ < bottom_);
301 }
302
303 /// @brief Returns true if width and height are equal and neither is NaN.
304 [[nodiscard]] constexpr bool IsSquare() const {
305 // empty rectangles can technically be "square", but would be
306 // misleading to most callers. Using |IsEmpty| also prevents
307 // "non-empty and non-overflowing" computations from happening
308 // to be equal to "empty and overflowing" results.
309 // (Consider LTRB(10, 15, MAX-2, MIN+2) which is empty, but both
310 // w/h subtractions equal "5").
311 return !IsEmpty() && (right_ - left_) == (bottom_ - top_);
312 }
313
314 [[nodiscard]] constexpr bool IsMaximum() const {
315 return *this == MakeMaximum();
316 }
317
318 /// @brief Returns the upper left corner of the rectangle as specified
319 /// by the left/top or x/y values when it was constructed.
320 [[nodiscard]] constexpr TPoint<Type> GetOrigin() const {
321 return {left_, top_};
322 }
323
324 /// @brief Returns the size of the rectangle which may be negative in
325 /// either width or height and may have been clipped to the
326 /// maximum integer values for integer rects whose size overflows.
327 [[nodiscard]] constexpr TSize<Type> GetSize() const {
328 return {GetWidth(), GetHeight()};
329 }
330
331 /// @brief Returns the X coordinate of the upper left corner, equivalent
332 /// to |GetOrigin().x|
333 [[nodiscard]] constexpr Type GetX() const { return left_; }
334
335 /// @brief Returns the Y coordinate of the upper left corner, equivalent
336 /// to |GetOrigin().y|
337 [[nodiscard]] constexpr Type GetY() const { return top_; }
338
339 /// @brief Returns the width of the rectangle, equivalent to
340 /// |GetSize().width|
341 [[nodiscard]] constexpr Type GetWidth() const {
342 return saturated::Sub(right_, left_);
343 }
344
345 /// @brief Returns the height of the rectangle, equivalent to
346 /// |GetSize().height|
347 [[nodiscard]] constexpr Type GetHeight() const {
348 return saturated::Sub(bottom_, top_);
349 }
350
351 [[nodiscard]] constexpr auto GetLeft() const { return left_; }
352
353 [[nodiscard]] constexpr auto GetTop() const { return top_; }
354
355 [[nodiscard]] constexpr auto GetRight() const { return right_; }
356
357 [[nodiscard]] constexpr auto GetBottom() const { return bottom_; }
358
359 [[nodiscard]] constexpr TPoint<T> GetLeftTop() const { //
360 return {left_, top_};
361 }
362
363 [[nodiscard]] constexpr TPoint<T> GetRightTop() const {
364 return {right_, top_};
365 }
366
367 [[nodiscard]] constexpr TPoint<T> GetLeftBottom() const {
368 return {left_, bottom_};
369 }
370
371 [[nodiscard]] constexpr TPoint<T> GetRightBottom() const {
372 return {right_, bottom_};
373 }
374
375 /// @brief Get the area of the rectangle, equivalent to |GetSize().Area()|
376 [[nodiscard]] constexpr T Area() const {
377 // TODO(141710): Use saturated math to avoid overflow.
378 return IsEmpty() ? 0 : (right_ - left_) * (bottom_ - top_);
379 }
380
381 /// @brief Get the center point as a |Point|.
382 [[nodiscard]] constexpr Point GetCenter() const {
383 return {saturated::AverageScalar(left_, right_),
384 saturated::AverageScalar(top_, bottom_)};
385 }
386
387 [[nodiscard]] constexpr std::array<T, 4> GetLTRB() const {
388 return {left_, top_, right_, bottom_};
389 }
390
391 /// @brief Get the x, y coordinates of the origin and the width and
392 /// height of the rectangle in an array.
393 [[nodiscard]] constexpr std::array<T, 4> GetXYWH() const {
394 return {left_, top_, GetWidth(), GetHeight()};
395 }
396
397 /// @brief Get a version of this rectangle that has a non-negative size.
398 [[nodiscard]] constexpr TRect GetPositive() const {
399 if (!IsEmpty()) {
400 return *this;
401 }
402 return {
403 std::min(left_, right_),
404 std::min(top_, bottom_),
405 std::max(left_, right_),
406 std::max(top_, bottom_),
407 };
408 }
409
410 /// @brief Get the points that represent the 4 corners of this rectangle
411 /// in a Z order that is compatible with triangle strips or a set
412 /// of all zero points if the rectangle is empty.
413 /// The order is: Top left, top right, bottom left, bottom right.
414 [[nodiscard]] constexpr std::array<TPoint<T>, 4> GetPoints() const {
415 if (IsEmpty()) {
416 return {};
417 }
418 return {
419 TPoint{left_, top_},
420 TPoint{right_, top_},
421 TPoint{left_, bottom_},
422 TPoint{right_, bottom_},
423 };
424 }
425
426 [[nodiscard]] constexpr std::array<TPoint<T>, 4> GetTransformedPoints(
427 const Matrix& transform) const {
428 auto points = GetPoints();
429 for (size_t i = 0; i < points.size(); i++) {
430 points[i] = transform * points[i];
431 }
432 return points;
433 }
434
435 /// @brief Creates a new bounding box that contains this transformed
436 /// rectangle, clipped against the near clipping plane if
437 /// necessary.
438 [[nodiscard]] constexpr TRect TransformAndClipBounds(
439 const Matrix& transform) const {
440 if (!transform.HasPerspective2D()) {
441 return TransformBounds(transform);
442 }
443
444 if (IsEmpty()) {
445 return {};
446 }
447
448 auto ul = transform.TransformHomogenous({left_, top_});
449 auto ur = transform.TransformHomogenous({right_, top_});
450 auto ll = transform.TransformHomogenous({left_, bottom_});
451 auto lr = transform.TransformHomogenous({right_, bottom_});
452
453 // It can probably be proven that we only ever have 5 points at most
454 // which happens when only 1 corner is clipped and we get 2 points
455 // in return for it as we interpolate against its neighbors.
456 Point points[8];
457 int index = 0;
458
459 // Process (clip and interpolate) each point against its 2 neighbors:
460 // left, pt, right
461 index = ClipAndInsert(points, index, ll, ul, ur);
462 index = ClipAndInsert(points, index, ul, ur, lr);
463 index = ClipAndInsert(points, index, ur, lr, ll);
464 index = ClipAndInsert(points, index, lr, ll, ul);
465
466 auto bounds = TRect::MakePointBounds(points, points + index);
467 return bounds.value_or(TRect{});
468 }
469
470 /// @brief Creates a new bounding box that contains this transformed
471 /// rectangle.
472 [[nodiscard]] constexpr TRect TransformBounds(const Matrix& transform) const {
473 if (IsEmpty()) {
474 return {};
475 }
476 auto points = GetTransformedPoints(transform);
477 auto bounds = TRect::MakePointBounds(points.begin(), points.end());
478 if (bounds.has_value()) {
479 return bounds.value();
480 }
481 FML_UNREACHABLE();
482 }
483
484 /// @brief Constructs a Matrix that will map all points in the coordinate
485 /// space of the rectangle into a new normalized coordinate space
486 /// where the upper left corner of the rectangle maps to (0, 0)
487 /// and the lower right corner of the rectangle maps to (1, 1).
488 ///
489 /// Empty and non-finite rectangles will return a zero-scaling
490 /// transform that maps all points to (0, 0).
491 [[nodiscard]] constexpr Matrix GetNormalizingTransform() const {
492 if (!IsEmpty()) {
493 Scalar sx = 1.0 / GetWidth();
494 Scalar sy = 1.0 / GetHeight();
495 Scalar tx = left_ * -sx;
496 Scalar ty = top_ * -sy;
497
498 // Exclude NaN and infinities and either scale underflowing to zero
499 if (sx != 0.0 && sy != 0.0 && 0.0 * sx * sy * tx * ty == 0.0) {
500 // clang-format off
501 return Matrix( sx, 0.0f, 0.0f, 0.0f,
502 0.0f, sy, 0.0f, 0.0f,
503 0.0f, 0.0f, 1.0f, 0.0f,
504 tx, ty, 0.0f, 1.0f);
505 // clang-format on
506 }
507 }
508
509 // Map all coordinates to the origin.
510 return Matrix::MakeScale({0.0f, 0.0f, 1.0f});
511 }
512
513 [[nodiscard]] constexpr TRect Union(const TRect& o) const {
514 if (IsEmpty()) {
515 return o;
516 }
517 if (o.IsEmpty()) {
518 return *this;
519 }
520 return {
521 std::min(left_, o.left_),
522 std::min(top_, o.top_),
523 std::max(right_, o.right_),
524 std::max(bottom_, o.bottom_),
525 };
526 }
527
528 [[nodiscard]] constexpr std::optional<TRect> Intersection(
529 const TRect& o) const {
530 if (IntersectsWithRect(o)) {
531 return TRect{
532 std::max(left_, o.left_),
533 std::max(top_, o.top_),
534 std::min(right_, o.right_),
535 std::min(bottom_, o.bottom_),
536 };
537 } else {
538 return std::nullopt;
539 }
540 }
541
542 [[nodiscard]] constexpr TRect IntersectionOrEmpty(const TRect& o) const {
543 return Intersection(o).value_or(TRect());
544 }
545
546 [[nodiscard]] constexpr bool IntersectsWithRect(const TRect& o) const {
547 return !IsEmpty() && //
548 !o.IsEmpty() && //
549 left_ < o.right_ && //
550 top_ < o.bottom_ && //
551 right_ > o.left_ && //
552 bottom_ > o.top_;
553 }
554
555 /// @brief Returns the new boundary rectangle that would result from this
556 /// rectangle being cut out by the specified rectangle.
557 [[nodiscard]] constexpr std::optional<TRect<T>> Cutout(const TRect& o) const {
558 if (IsEmpty()) {
559 // This test isn't just a short-circuit, it also prevents the concise
560 // math below from returning the wrong answer on empty rects.
561 // Once we know that this rectangle is not empty, the math below can
562 // only succeed in computing a value if o is also non-empty and non-nan.
563 // Otherwise, the method returns *this by default.
564 return std::nullopt;
565 }
566
567 const auto& [a_left, a_top, a_right, a_bottom] = GetLTRB(); // Source rect.
568 const auto& [b_left, b_top, b_right, b_bottom] = o.GetLTRB(); // Cutout.
569 if (b_left <= a_left && b_right >= a_right) {
570 if (b_top <= a_top && b_bottom >= a_bottom) {
571 // Full cutout.
572 return std::nullopt;
573 }
574 if (b_top <= a_top && b_bottom > a_top) {
575 // Cuts off the top.
576 return TRect::MakeLTRB(a_left, b_bottom, a_right, a_bottom);
577 }
578 if (b_bottom >= a_bottom && b_top < a_bottom) {
579 // Cuts off the bottom.
580 return TRect::MakeLTRB(a_left, a_top, a_right, b_top);
581 }
582 }
583 if (b_top <= a_top && b_bottom >= a_bottom) {
584 if (b_left <= a_left && b_right > a_left) {
585 // Cuts off the left.
586 return TRect::MakeLTRB(b_right, a_top, a_right, a_bottom);
587 }
588 if (b_right >= a_right && b_left < a_right) {
589 // Cuts off the right.
590 return TRect::MakeLTRB(a_left, a_top, b_left, a_bottom);
591 }
592 }
593
594 return *this;
595 }
596
597 [[nodiscard]] constexpr TRect CutoutOrEmpty(const TRect& o) const {
598 return Cutout(o).value_or(TRect());
599 }
600
601 /// @brief Returns a new rectangle translated by the given offset.
602 [[nodiscard]] constexpr TRect<T> Shift(T dx, T dy) const {
603 return {
604 saturated::Add(left_, dx), //
605 saturated::Add(top_, dy), //
606 saturated::Add(right_, dx), //
607 saturated::Add(bottom_, dy), //
608 };
609 }
610
611 /// @brief Returns a new rectangle translated by the given offset.
612 [[nodiscard]] constexpr TRect<T> Shift(TPoint<T> offset) const {
613 return Shift(offset.x, offset.y);
614 }
615
616 /// @brief Returns a rectangle with expanded edges. Negative expansion
617 /// results in shrinking.
618 [[nodiscard]] constexpr TRect<T> Expand(T left,
619 T top,
620 T right,
621 T bottom) const {
622 return {
623 saturated::Sub(left_, left), //
624 saturated::Sub(top_, top), //
625 saturated::Add(right_, right), //
626 saturated::Add(bottom_, bottom), //
627 };
628 }
629
630 /// @brief Returns a rectangle with expanded edges in all directions.
631 /// Negative expansion results in shrinking.
632 [[nodiscard]] constexpr TRect<T> Expand(T amount) const {
633 return {
634 saturated::Sub(left_, amount), //
635 saturated::Sub(top_, amount), //
636 saturated::Add(right_, amount), //
637 saturated::Add(bottom_, amount), //
638 };
639 }
640
641 /// @brief Returns a rectangle with expanded edges in all directions.
642 /// Negative expansion results in shrinking.
643 [[nodiscard]] constexpr TRect<T> Expand(T horizontal_amount,
644 T vertical_amount) const {
645 return {
646 saturated::Sub(left_, horizontal_amount), //
647 saturated::Sub(top_, vertical_amount), //
648 saturated::Add(right_, horizontal_amount), //
649 saturated::Add(bottom_, vertical_amount), //
650 };
651 }
652
653 /// @brief Returns a rectangle with expanded edges in all directions.
654 /// Negative expansion results in shrinking.
655 [[nodiscard]] constexpr TRect<T> Expand(TPoint<T> amount) const {
656 return Expand(amount.x, amount.y);
657 }
658
659 /// @brief Returns a rectangle with expanded edges in all directions.
660 /// Negative expansion results in shrinking.
661 [[nodiscard]] constexpr TRect<T> Expand(TSize<T> amount) const {
662 return Expand(amount.width, amount.height);
663 }
664
665 /// @brief Returns a new rectangle that represents the projection of the
666 /// source rectangle onto this rectangle. In other words, the source
667 /// rectangle is redefined in terms of the coordinate space of this
668 /// rectangle.
669 [[nodiscard]] constexpr TRect<T> Project(TRect<T> source) const {
670 if (IsEmpty()) {
671 return {};
672 }
673 return source.Shift(-left_, -top_)
674 .Scale(1.0 / static_cast<Scalar>(GetWidth()),
675 1.0 / static_cast<Scalar>(GetHeight()));
676 }
677
678 ONLY_ON_FLOAT_M([[nodiscard]] constexpr static, TRect)
679 RoundOut(const TRect<U>& r) {
680 return TRect::MakeLTRB(saturated::Cast<U, Type>(floor(r.GetLeft())),
681 saturated::Cast<U, Type>(floor(r.GetTop())),
682 saturated::Cast<U, Type>(ceil(r.GetRight())),
683 saturated::Cast<U, Type>(ceil(r.GetBottom())));
684 }
685
686 ONLY_ON_FLOAT_M([[nodiscard]] constexpr static, TRect)
687 RoundIn(const TRect<U>& r) {
688 return TRect::MakeLTRB(saturated::Cast<U, Type>(ceil(r.GetLeft())),
689 saturated::Cast<U, Type>(ceil(r.GetTop())),
690 saturated::Cast<U, Type>(floor(r.GetRight())),
691 saturated::Cast<U, Type>(floor(r.GetBottom())));
692 }
693
694 ONLY_ON_FLOAT_M([[nodiscard]] constexpr static, TRect)
695 Round(const TRect<U>& r) {
696 return TRect::MakeLTRB(saturated::Cast<U, Type>(round(r.GetLeft())),
697 saturated::Cast<U, Type>(round(r.GetTop())),
698 saturated::Cast<U, Type>(round(r.GetRight())),
699 saturated::Cast<U, Type>(round(r.GetBottom())));
700 }
701
702 [[nodiscard]] constexpr static TRect Union(const TRect& a,
703 const std::optional<TRect> b) {
704 return b.has_value() ? a.Union(b.value()) : a;
705 }
706
707 [[nodiscard]] constexpr static TRect Union(const std::optional<TRect> a,
708 const TRect& b) {
709 return a.has_value() ? a->Union(b) : b;
710 }
711
712 [[nodiscard]] constexpr static std::optional<TRect> Union(
713 const std::optional<TRect> a,
714 const std::optional<TRect> b) {
715 return a.has_value() ? Union(a.value(), b) : b;
716 }
717
718 [[nodiscard]] constexpr static std::optional<TRect> Intersection(
719 const TRect& a,
720 const std::optional<TRect> b) {
721 return b.has_value() ? a.Intersection(b.value()) : a;
722 }
723
724 [[nodiscard]] constexpr static std::optional<TRect> Intersection(
725 const std::optional<TRect> a,
726 const TRect& b) {
727 return a.has_value() ? a->Intersection(b) : b;
728 }
729
730 [[nodiscard]] constexpr static std::optional<TRect> Intersection(
731 const std::optional<TRect> a,
732 const std::optional<TRect> b) {
733 return a.has_value() ? Intersection(a.value(), b) : b;
734 }
735
736 private:
737 constexpr TRect(Type left, Type top, Type right, Type bottom)
738 : left_(left), top_(top), right_(right), bottom_(bottom) {}
739
740 Type left_;
741 Type top_;
742 Type right_;
743 Type bottom_;
744
745 static constexpr Scalar kMinimumHomogenous = 1.0f / (1 << 14);
746
747 // Clip p against the near clipping plane (W = kMinimumHomogenous)
748 // and interpolate a crossing point against the nearby neighbors
749 // left and right if p is clipped and either of them is not.
750 // This method can produce 0, 1, or 2 points per call depending on
751 // how many of the points are clipped.
752 // 0 - all points are clipped
753 // 1 - p is unclipped OR
754 // p is clipped and exactly one of the neighbors is not
755 // 2 - p is clipped and both neighbors are not
756 static constexpr int ClipAndInsert(Point clipped[],
757 int index,
758 const Vector3& left,
759 const Vector3& p,
760 const Vector3& right) {
761 if (p.z >= kMinimumHomogenous) {
762 clipped[index++] = {p.x / p.z, p.y / p.z};
763 } else {
764 index = InterpolateAndInsert(clipped, index, p, left);
765 index = InterpolateAndInsert(clipped, index, p, right);
766 }
767 return index;
768 }
769
770 // Interpolate (a clipped) point p against one of its neighbors
771 // and insert the point into the array where the line between them
772 // veers from clipped space to unclipped, if such a point exists.
773 static constexpr int InterpolateAndInsert(Point clipped[],
774 int index,
775 const Vector3& p,
776 const Vector3& neighbor) {
777 if (neighbor.z >= kMinimumHomogenous) {
778 auto t = (kMinimumHomogenous - p.z) / (neighbor.z - p.z);
779 clipped[index++] = {
780 (t * p.x + (1.0f - t) * neighbor.x) / kMinimumHomogenous,
781 (t * p.y + (1.0f - t) * neighbor.y) / kMinimumHomogenous,
782 };
783 }
784 return index;
785 }
786 };
787
788 using Rect = TRect<Scalar>;
789 using IRect32 = TRect<int32_t>;
790 using IRect64 = TRect<int64_t>;
791 using IRect = IRect64;
792
793 #undef ONLY_ON_FLOAT
794 #undef ONLY_ON_FLOAT_M
795
796 } // namespace impeller
797
798 namespace std {
799
800 template <class T>
801 inline std::ostream& operator<<(std::ostream& out,
802 const impeller::TRect<T>& r) {
803 out << "(" << r.GetLeftTop() << " => " << r.GetRightBottom() << ")";
804 return out;
805 }
806
807 } // namespace std
808
809 #endif // FLUTTER_IMPELLER_GEOMETRY_RECT_H_
value
int32_t value
Definition: dl_golden_unittests.cc:459
x
int32_t x
Definition: dl_golden_unittests.cc:458
transform
Matrix transform
Definition: gaussian_blur_filter_contents.cc:214
matrix.h
impeller::saturated::b
SI b
Definition: saturated_math.h:87
impeller
Definition: allocation.cc:12
impeller::Scalar
float Scalar
Definition: scalar.h:19
impeller::Point
TPoint< Scalar > Point
Definition: point.h:327
impeller::IRect64
TRect< int64_t > IRect64
Definition: rect.h:790
std
Definition: comparable.h:95
std::operator<<
std::ostream & operator<<(std::ostream &out, const impeller::Arc &a)
Definition: arc.h:141
point.h
ONLY_ON_FLOAT_M
#define ONLY_ON_FLOAT_M(Modifiers, Return)
Definition: rect.h:22
saturated_math.h
scalar.h
size.h
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
impeller::Matrix::MakeScale
static constexpr Matrix MakeScale(const Vector3 &s)
Definition: matrix.h:104
impeller::TPoint
Definition: point.h:27
impeller::TPoint::y
Type y
Definition: point.h:31
impeller::TPoint::x
Type x
Definition: point.h:30
impeller::TRect
Definition: rect.h:122
impeller::TRect::Expand
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:618
impeller::TRect::GetBottom
constexpr auto GetBottom() const
Definition: rect.h:357
impeller::TRect::GetY
constexpr Type GetY() const
Returns the Y coordinate of the upper left corner, equivalent to |GetOrigin().y|.
Definition: rect.h:337
impeller::TRect::TransformBounds
constexpr TRect TransformBounds(const Matrix &transform) const
Creates a new bounding box that contains this transformed rectangle.
Definition: rect.h:472
impeller::TRect::Project
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:669
impeller::TRect::ContainsInclusive
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:250
impeller::TRect::GetTop
constexpr auto GetTop() const
Definition: rect.h:353
impeller::TRect::GetHeight
constexpr Type GetHeight() const
Returns the height of the rectangle, equivalent to |GetSize().height|.
Definition: rect.h:347
impeller::TRect::GetOrigin
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:320
impeller::TRect::Scale
constexpr TRect Scale(TPoint< T > scale) const
Definition: rect.h:216
impeller::TRect::Expand
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:655
impeller::TRect::IsMaximum
constexpr bool IsMaximum() const
Definition: rect.h:314
impeller::TRect::Intersection
constexpr std::optional< TRect > Intersection(const TRect &o) const
Definition: rect.h:528
impeller::TRect::IsEmpty
constexpr bool IsEmpty() const
Returns true if either of the width or height are 0, negative, or NaN.
Definition: rect.h:297
impeller::TRect::Area
constexpr T Area() const
Get the area of the rectangle, equivalent to |GetSize().Area()|.
Definition: rect.h:376
impeller::TRect::MakeOriginSize
constexpr static TRect MakeOriginSize(const TPoint< Type > &origin, const TSize< Type > &size)
Definition: rect.h:144
impeller::TRect::Contains
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:231
impeller::TRect::Union
constexpr static TRect Union(const TRect &a, const std::optional< TRect > b)
Definition: rect.h:702
impeller::TRect::Union
constexpr TRect Union(const TRect &o) const
Definition: rect.h:513
impeller::TRect::Scale
constexpr TRect Scale(Type scale_x, Type scale_y) const
Definition: rect.h:209
impeller::TRect::GetPoints
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:414
impeller::TRect::IntersectsWithRect
constexpr bool IntersectsWithRect(const TRect &o) const
Definition: rect.h:546
impeller::TRect::GetLeft
constexpr auto GetLeft() const
Definition: rect.h:351
impeller::TRect::RoundIn
RoundIn(const TRect< U > &r)
Definition: rect.h:687
impeller::TRect::CutoutOrEmpty
constexpr TRect CutoutOrEmpty(const TRect &o) const
Definition: rect.h:597
impeller::TRect::MakeWH
constexpr static TRect MakeWH(Type width, Type height)
Definition: rect.h:140
impeller::TRect::MakePointBounds
constexpr static std::optional< TRect > MakePointBounds(const U &value)
Definition: rect.h:165
impeller::TRect::GetSize
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:327
impeller::TRect::Expand
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:643
impeller::TRect::Round
Round(const TRect< U > &r)
Definition: rect.h:695
impeller::TRect::RoundOut
RoundOut(const TRect< U > &r)
Definition: rect.h:679
impeller::TRect::GetPositive
constexpr TRect GetPositive() const
Get a version of this rectangle that has a non-negative size.
Definition: rect.h:398
impeller::TRect::Scale
constexpr TRect Scale(TSize< T > scale) const
Definition: rect.h:220
impeller::TRect::GetX
constexpr Type GetX() const
Returns the X coordinate of the upper left corner, equivalent to |GetOrigin().x|.
Definition: rect.h:333
impeller::TRect::GetRight
constexpr auto GetRight() const
Definition: rect.h:355
impeller::TRect::IsSquare
constexpr bool IsSquare() const
Returns true if width and height are equal and neither is NaN.
Definition: rect.h:304
impeller::TRect::Intersection
constexpr static std::optional< TRect > Intersection(const std::optional< TRect > a, const std::optional< TRect > b)
Definition: rect.h:730
impeller::TRect::Contains
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:273
impeller::TRect::IsFinite
IsFinite() const
Returns true if all of the fields of this floating point rectangle are finite.
Definition: rect.h:288
impeller::TRect::GetNormalizingTransform
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:491
impeller::TRect::Union
constexpr static std::optional< TRect > Union(const std::optional< TRect > a, const std::optional< TRect > b)
Definition: rect.h:712
impeller::TRect::Scale
constexpr TRect Scale(Type scale) const
Definition: rect.h:202
impeller::TRect::MakeXYWH
constexpr static TRect MakeXYWH(Type x, Type y, Type width, Type height)
Definition: rect.h:136
impeller::TRect::GetLeftBottom
constexpr TPoint< T > GetLeftBottom() const
Definition: rect.h:367
impeller::TRect::GetTransformedPoints
constexpr std::array< TPoint< T >, 4 > GetTransformedPoints(const Matrix &transform) const
Definition: rect.h:426
impeller::TRect::TransformAndClipBounds
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:438
impeller::TRect::Union
constexpr static TRect Union(const std::optional< TRect > a, const TRect &b)
Definition: rect.h:707
impeller::TRect::Shift
constexpr TRect< T > Shift(TPoint< T > offset) const
Returns a new rectangle translated by the given offset.
Definition: rect.h:612
impeller::TRect::GetRightTop
constexpr TPoint< T > GetRightTop() const
Definition: rect.h:363
impeller::TRect::Expand
constexpr TRect< T > Expand(T amount) const
Returns a rectangle with expanded edges in all directions. Negative expansion results in shrinking.
Definition: rect.h:632
impeller::TRect::MakePointBounds
constexpr static std::optional< TRect > MakePointBounds(const PointIter first, const PointIter last)
Definition: rect.h:170
impeller::TRect::Shift
constexpr TRect< T > Shift(T dx, T dy) const
Returns a new rectangle translated by the given offset.
Definition: rect.h:602
impeller::TRect::MakeSize
constexpr static TRect MakeSize(const TSize< U > &size)
Definition: rect.h:150
impeller::TRect::GetWidth
constexpr Type GetWidth() const
Returns the width of the rectangle, equivalent to |GetSize().width|.
Definition: rect.h:341
impeller::TRect::GetRightBottom
constexpr TPoint< T > GetRightBottom() const
Definition: rect.h:371
impeller::TRect::GetLTRB
constexpr std::array< T, 4 > GetLTRB() const
Definition: rect.h:387
impeller::TRect::Make
constexpr static std::enable_if_t< std::is_floating_point_v< FT >, TRect > Make(const TRect< U > &rect)
Definition: rect.h:157
impeller::TRect::Expand
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:661
impeller::TRect::Intersection
constexpr static std::optional< TRect > Intersection(const TRect &a, const std::optional< TRect > b)
Definition: rect.h:718
impeller::TRect::GetCenter
constexpr Point GetCenter() const
Get the center point as a |Point|.
Definition: rect.h:382
impeller::TRect::IntersectionOrEmpty
constexpr TRect IntersectionOrEmpty(const TRect &o) const
Definition: rect.h:542
impeller::TRect::TRect
constexpr TRect()
Definition: rect.h:127
impeller::TRect::Intersection
constexpr static std::optional< TRect > Intersection(const std::optional< TRect > a, const TRect &b)
Definition: rect.h:724
impeller::TRect::Cutout
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:557
impeller::TRect::GetLeftTop
constexpr TPoint< T > GetLeftTop() const
Definition: rect.h:359
impeller::TRect::operator==
constexpr bool operator==(const TRect &r) const
Definition: rect.h:195
impeller::TRect::GetXYWH
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:393
impeller::TRect::MakeLTRB
constexpr static TRect MakeLTRB(Type left, Type top, Type right, Type bottom)
Definition: rect.h:129
impeller::TRect::MakeMaximum
constexpr static TRect MakeMaximum()
Definition: rect.h:188
impeller::TSize
Definition: size.h:25
impeller::TSize::height
Type height
Definition: size.h:29
impeller::TSize::width
Type width
Definition: size.h:28
points
std::vector< Point > points
Definition: tessellator_libtess.cc:76