| Flutter Impeller |

round_superellipse_geometry.cc
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 #include <cmath>
6 #include <variant>
7
8 #include "flutter/impeller/entity/geometry/round_superellipse_geometry.h"
9 #include "flutter/impeller/geometry/round_superellipse_param.h"
10
11 #include "impeller/geometry/constants.h"
12
13 namespace impeller {
14
15 namespace {
16
17 constexpr auto kGapFactor = RoundSuperellipseParam::kGapFactor;
18
19 // An interface for classes that arranges a point list that forms a convex
20 // contour into a triangle strip.
21 class ConvexRearranger {
22 public:
23 ConvexRearranger() {}
24
25 virtual ~ConvexRearranger() {}
26
27 virtual size_t ContourLength() const = 0;
28
29 virtual Point GetPoint(size_t i) const = 0;
30
31 void RearrangeIntoTriangleStrip(Point* output) {
32 size_t index_count = 0;
33
34 output[index_count++] = GetPoint(0);
35
36 size_t a = 1;
37 size_t contour_length = ContourLength();
38 size_t b = contour_length - 1;
39 while (a < b) {
40 output[index_count++] = GetPoint(a);
41 output[index_count++] = GetPoint(b);
42 a++;
43 b--;
44 }
45 if (a == b) {
46 output[index_count++] = GetPoint(b);
47 }
48 }
49
50 private:
51 ConvexRearranger(const ConvexRearranger&) = delete;
52 ConvexRearranger& operator=(const ConvexRearranger&) = delete;
53 };
54
55 // A convex rearranger whose contour is concatenated from 4 quadrant segments.
56 //
57 // The input quadrant curves must travel from the Y axis to the X axis, and
58 // include both ends. This means that the points on the axes are duplicate
59 // between segments, and will be omitted by this class.
60 class UnevenQuadrantsRearranger : public ConvexRearranger {
61 public:
62 UnevenQuadrantsRearranger(Point* cache, size_t segment_capacity)
63 : cache_(cache), segment_capacity_(segment_capacity) {}
64
65 Point* QuadCache(size_t i) { return cache_ + segment_capacity_ * i; }
66
67 const Point* QuadCache(size_t i) const {
68 return cache_ + segment_capacity_ * i;
69 }
70
71 size_t& QuadSize(size_t i) { return lengths_[i]; }
72
73 size_t ContourLength() const override {
74 return lengths_[0] + lengths_[1] + lengths_[2] + lengths_[3] - 4;
75 }
76
77 Point GetPoint(size_t i) const override {
78 // output from index
79 // 0 ... l0-2 quads[0] 0 ... l0-2
80 // next 0 ... l1-2 quads[1] l1-1 ... 1
81 // next 0 ... l2-2 quads[2] 0 ... l2-2
82 // next 0 ... l3-2 quads[3] l3-1 ... 1
83 size_t high = lengths_[0] - 1;
84 if (i < high) {
85 return QuadCache(0)[i];
86 }
87 high += lengths_[1] - 1;
88 if (i < high) {
89 return QuadCache(1)[high - i];
90 }
91 size_t low = high;
92 high += lengths_[2] - 1;
93 if (i < high) {
94 return QuadCache(2)[i - low];
95 }
96 high += lengths_[3] - 1;
97 if (i < high) {
98 return QuadCache(3)[high - i];
99 } else {
100 // Unreachable
101 return Point();
102 }
103 }
104
105 private:
106 Point* cache_;
107 size_t segment_capacity_;
108 size_t lengths_[4];
109 };
110
111 // A convex rearranger whose contour is concatenated from 4 identical quadrant
112 // segments.
113 //
114 // The input curve must travel from the Y axis to the X axis and include both
115 // ends. This means that the points on the axes are duplicate between segments,
116 // and will be omitted by this class.
117 class MirroredQuadrantRearranger : public ConvexRearranger {
118 public:
119 MirroredQuadrantRearranger(Point center, Point* cache)
120 : center_(center), cache_(cache) {}
121
122 size_t& QuadSize() { return l_; }
123
124 size_t ContourLength() const override { return l_ * 4 - 4; }
125
126 Point GetPoint(size_t i) const override {
127 // output from index
128 // 0 ... l-2 quad 0 ... l-2
129 // next 0 ... l-2 quad l-1 ... 1
130 // next 0 ... l-2 quad 0 ... l-2
131 // next 0 ... l-2 quad l-1 ... 1
132 size_t high = l_ - 1;
133 if (i < high) {
134 return cache_[i] + center_;
135 }
136 high += l_ - 1;
137 if (i < high) {
138 return cache_[high - i] * Point{1, -1} + center_;
139 }
140 size_t low = high;
141 high += l_ - 1;
142 if (i < high) {
143 return cache_[i - low] * Point{-1, -1} + center_;
144 }
145 high += l_ - 1;
146 if (i < high) {
147 return cache_[high - i] * Point{-1, 1} + center_;
148 } else {
149 // Unreachable
150 return Point();
151 }
152 }
153
154 private:
155 Point center_;
156 Point* cache_;
157 size_t l_ = 0;
158 };
159
160 // A matrix that swaps the coordinates of a point.
161 // clang-format off
162 constexpr Matrix kFlip = Matrix(
163 0.0f, 1.0f, 0.0f, 0.0f,
164 1.0f, 0.0f, 0.0f, 0.0f,
165 0.0f, 0.0f, 1.0f, 0.0f,
166 0.0f, 0.0f, 0.0f, 1.0f);
167 // clang-format on
168
169 // The max angular step that the algorithm will traverse a quadrant of the
170 // curve.
171 //
172 // This limits the max number of points of the curve.
173 constexpr Scalar kMaxQuadrantSteps = 40;
174
175 // Calculates the angular step size for a smooth curve.
176 //
177 // Returns the angular step needed to ensure a curve appears smooth
178 // based on the smallest dimension of a shape. Smaller dimensions require
179 // larger steps as less detail is needed for smoothness.
180 //
181 // The `minDimension` is the smallest dimension (e.g., width or height) of the
182 // shape.
183 //
184 // The `fullAngle` is the total angular range to traverse.
185 Scalar CalculateStep(Scalar minDimension, Scalar fullAngle) {
186 constexpr Scalar kMinAngleStep = kPiOver2 / kMaxQuadrantSteps;
187
188 // Assumes at least 1 point is needed per pixel to achieve sufficient
189 // smoothness.
190 constexpr Scalar pointsPerPixel = 1.0;
191 size_t pointsByDimension =
192 static_cast<size_t>(std::ceil(minDimension * pointsPerPixel));
193 Scalar angleByDimension = fullAngle / pointsByDimension;
194
195 return std::min(kMinAngleStep, angleByDimension);
196 }
197
198 // Draw a superellipsoid arc.
199 //
200 // The superellipse is centered at the origin and has degree `n` and both
201 // semi-axes equal to `a`. The arc starts from positive Y axis and spans from 0
202 // to `max_theta` radiance clockwise if `reverse` is false, or from `max_theta`
203 // to 0 otherwise.
204 //
205 // The resulting points, transformed by `transform`, are appended to `output`.
206 // The starting point is included, but the ending point is excluded.
207 //
208 // Returns the number of points generated.
209 size_t DrawSuperellipsoidArc(Point* output,
210 Scalar a,
211 Scalar n,
212 Scalar max_theta,
213 bool reverse,
214 const Matrix& transform) {
215 Point* next = output;
216 Scalar angle = reverse ? max_theta : 0.0f;
217 Scalar step =
218 (reverse ? -1 : 1) *
219 CalculateStep(a - a * pow(abs(cosf(max_theta)), 2 / n), max_theta);
220 Scalar end = reverse ? 0.0f : max_theta;
221 while ((angle < end) != reverse) {
222 Scalar x = a * pow(abs(sinf(angle)), 2 / n);
223 Scalar y = a * pow(abs(cosf(angle)), 2 / n);
224 *(next++) = transform * Point(x, y);
225 angle += step;
226 }
227 return next - output;
228 }
229
230 // Draws a circular arc centered at the origin with a radius of `r`, starting at
231 // `start`, and spanning `max_angle` clockwise.
232 //
233 // If `reverse` is false, points are generated from `start` to `start +
234 // max_angle`. If `reverse` is true, points are generated from `start +
235 // max_angle` back to `start`.
236 //
237 // The generated points, transformed by `transform`, are appended to `output`.
238 // The starting point is included, but the ending point is excluded.
239 //
240 // Returns the number of points generated.
241 size_t DrawCircularArc(Point* output,
242 Point start,
243 Scalar max_angle,
244 bool reverse,
245 const Matrix& transform) {
246 /* Denote the middle point of S and E as M. The key is to find the center of
247 * the circle.
248 * S --__
249 * / ⟍ `、
250 * / M ⟍\
251 * / ⟋ E
252 * / ⟋ ↗
253 * / ⟋
254 * / ⟋ r
255 * C ᜱ ↙
256 */
257
258 Point end = start.Rotate(Radians(-max_angle));
259
260 Point* next = output;
261 Scalar angle = reverse ? max_angle : 0.0f;
262 Scalar step =
263 (reverse ? -1 : 1) * CalculateStep(std::abs(start.y - end.y), max_angle);
264 Scalar end_angle = reverse ? 0.0f : max_angle;
265
266 while ((angle < end_angle) != reverse) {
267 *(next++) = transform * start.Rotate(Radians(-angle));
268 angle += step;
269 }
270 return next - output;
271 }
272
273 // Draws an arc representing the top 1/8 segment of a square-like rounded
274 // superellipse centered at the origin.
275 //
276 // If `reverse_and_flip` is false, the resulting arc spans from 0 (inclusive) to
277 // pi/4 (exclusive), moving clockwise starting from the positive Y-axis. If
278 // `reverse` is true, the curve spans from pi/4 (inclusive) to 0 (inclusive)
279 // counterclockwise instead, and all points have their x and y coordinates
280 // flipped.
281 //
282 // Either way, each point is then transformed by `external_transform` and
283 // appended to `output`.
284 //
285 // Returns the number of points generated.
286 size_t DrawOctantSquareLikeSquircle(Point* output,
287 const RoundSuperellipseParam::Octant& param,
288 bool reverse_and_flip,
289 const Matrix& external_transform) {
290 Matrix transform = external_transform * Matrix::MakeTranslation(param.offset);
291 if (reverse_and_flip) {
292 transform = transform * kFlip;
293 }
294 if (param.se_n < 2) {
295 // It's a square.
296 *output = transform * Point(param.se_a, param.se_a);
297 return 1;
298 }
299
300 /* The following figure shows the first quadrant of a square-like rounded
301 * superellipse. The target arc consists a superellipsoid arc (AJ) and a
302 * circular arc (JM).
303 *
304 * superelipse
305 * A ↓ circular arc
306 * ---------...._J ↙
307 * | / `⟍ M (where x=y)
308 * | / ⟋ ⟍
309 * | / ⟋ \
310 * | / ⟋ |
311 * | ᜱD |
312 * | ⟋ |
313 * | ⟋ |
314 * |⟋ |
315 * +--------------------| A'
316 * O
317 * ←-------- a ---------→
318 */
319
320 Point* next = output;
321 if (!reverse_and_flip) {
322 // Arc [A, J)
323 next +=
324 DrawSuperellipsoidArc(next, param.se_a, param.se_n, param.se_max_theta,
325 reverse_and_flip, transform);
326 // Arc [J, M)
327 next += DrawCircularArc(
328 next, param.circle_start - param.circle_center,
329 param.circle_max_angle.radians, reverse_and_flip,
330 transform * Matrix::MakeTranslation(param.circle_center));
331 } else {
332 // Arc [M, J)
333 next += DrawCircularArc(
334 next, param.circle_start - param.circle_center,
335 param.circle_max_angle.radians, reverse_and_flip,
336 transform * Matrix::MakeTranslation(param.circle_center));
337 // Arc [J, A)
338 next +=
339 DrawSuperellipsoidArc(next, param.se_a, param.se_n, param.se_max_theta,
340 reverse_and_flip, transform);
341 // Point A
342 *(next++) = transform * Point(0, param.se_a);
343 }
344 return next - output;
345 }
346
347 // Draw a quadrant curve, both ends included.
348 //
349 // Returns the number of points.
350 static size_t DrawQuadrant(Point* output,
351 const RoundSuperellipseParam::Quadrant& param) {
352 Point* next = output;
353 auto transform = Matrix::MakeTranslateScale(param.signed_scale, param.offset);
354
355 next += DrawOctantSquareLikeSquircle(next, param.top,
356 /*reverse_and_flip=*/false, transform);
357
358 next += DrawOctantSquareLikeSquircle(next, param.right,
359 /*reverse_and_flip=*/true, transform);
360
361 return next - output;
362 }
363
364 } // namespace
365
366 RoundSuperellipseGeometry::RoundSuperellipseGeometry(const Rect& bounds,
367 const RoundingRadii& radii)
368 : bounds_(bounds.GetPositive()), radii_(radii.Scaled(bounds_)) {}
369
370 RoundSuperellipseGeometry::RoundSuperellipseGeometry(const Rect& bounds,
371 float corner_radius)
372 : RoundSuperellipseGeometry(bounds,
373 RoundingRadii::MakeRadius(corner_radius)) {}
374
375 RoundSuperellipseGeometry::~RoundSuperellipseGeometry() {}
376
377 GeometryResult RoundSuperellipseGeometry::GetPositionBuffer(
378 const ContentContext& renderer,
379 const Entity& entity,
380 RenderPass& pass) const {
381 Point* cache = renderer.GetTessellator().GetStrokePointCache().data();
382
383 // The memory size (in units of Points) allocated to store each quadrants.
384 constexpr size_t kMaxQuadSize = kPointArenaSize / 4;
385 // Since the curve is traversed in steps bounded by kMaxQuadrantSteps, the
386 // curving part will have fewer points than kMaxQuadrantSteps. Multiply it by
387 // 2 for storing other sporatic points (an extremely conservative estimate).
388 static_assert(kMaxQuadSize > 2 * kMaxQuadrantSteps);
389
390 ConvexRearranger* rearranger;
391 std::variant<std::monostate, MirroredQuadrantRearranger,
392 UnevenQuadrantsRearranger>
393 rearranger_holder;
394
395 auto param = RoundSuperellipseParam::MakeBoundsRadii(bounds_, radii_);
396
397 if (param.all_corners_same) {
398 rearranger_holder.emplace<MirroredQuadrantRearranger>(bounds_.GetCenter(),
399 cache);
400 auto& t = std::get<MirroredQuadrantRearranger>(rearranger_holder);
401 rearranger = &t;
402
403 // The quadrant must be drawn at the origin so that it can be rotated later.
404 param.top_right.offset = Point();
405 t.QuadSize() = DrawQuadrant(cache, param.top_right);
406 } else {
407 rearranger_holder.emplace<UnevenQuadrantsRearranger>(cache, kMaxQuadSize);
408 auto& t = std::get<UnevenQuadrantsRearranger>(rearranger_holder);
409 rearranger = &t;
410
411 t.QuadSize(0) = DrawQuadrant(t.QuadCache(0), param.top_right);
412 t.QuadSize(1) = DrawQuadrant(t.QuadCache(1), param.bottom_right);
413 t.QuadSize(2) = DrawQuadrant(t.QuadCache(2), param.bottom_left);
414 t.QuadSize(3) = DrawQuadrant(t.QuadCache(3), param.top_left);
415 }
416
417 size_t contour_length = rearranger->ContourLength();
418 BufferView vertex_buffer = renderer.GetTransientsBuffer().Emplace(
419 nullptr, sizeof(Point) * contour_length, alignof(Point));
420 Point* vertex_data =
421 reinterpret_cast<Point*>(vertex_buffer.GetBuffer()->OnGetContents() +
422 vertex_buffer.GetRange().offset);
423 rearranger->RearrangeIntoTriangleStrip(vertex_data);
424
425 return GeometryResult{
426 .type = PrimitiveType::kTriangleStrip,
427 .vertex_buffer =
428 {
429 .vertex_buffer = vertex_buffer,
430 .vertex_count = contour_length,
431 .index_type = IndexType::kNone,
432 },
433 .transform = entity.GetShaderTransform(pass),
434 };
435 }
436
437 std::optional<Rect> RoundSuperellipseGeometry::GetCoverage(
438 const Matrix& transform) const {
439 return bounds_.TransformBounds(transform);
440 }
441
442 bool RoundSuperellipseGeometry::CoversArea(const Matrix& transform,
443 const Rect& rect) const {
444 if (!transform.IsTranslationScaleOnly()) {
445 return false;
446 }
447 Scalar left_inset = std::max(radii_.top_left.width, radii_.bottom_left.width);
448 Scalar right_inset =
449 std::max(radii_.top_right.width, radii_.bottom_right.width);
450 Scalar top_inset = std::max(radii_.top_left.height, radii_.top_right.height);
451 Scalar bottom_inset =
452 std::max(radii_.bottom_left.height, radii_.bottom_right.height);
453 Rect coverage =
454 Rect::MakeLTRB(bounds_.GetLeft() + left_inset * kGapFactor,
455 bounds_.GetTop() + top_inset * kGapFactor,
456 bounds_.GetRight() - right_inset * kGapFactor,
457 bounds_.GetBottom() - bottom_inset * kGapFactor);
458 return coverage.TransformBounds(transform).Contains(rect);
459 }
460
461 bool RoundSuperellipseGeometry::IsAxisAlignedRect() const {
462 return false;
463 }
464
465 } // namespace impeller
impeller::ContentContext
Definition: content_context.h:138
impeller::ContentContext::GetTransientsBuffer
HostBuffer & GetTransientsBuffer() const
Retrieve the currnent host buffer for transient storage.
Definition: content_context.h:296
impeller::ContentContext::GetTessellator
Tessellator & GetTessellator() const
Definition: content_context.cc:909
impeller::Entity
Definition: entity.h:20
impeller::Entity::GetShaderTransform
Matrix GetShaderTransform(const RenderPass &pass) const
Get the vertex shader transform used for drawing this Entity.
Definition: entity.cc:48
impeller::HostBuffer::Emplace
BufferView Emplace(const BufferType &buffer, size_t alignment=0)
Emplace non-uniform data (like contiguous vertices) onto the host buffer.
Definition: host_buffer.h:93
impeller::RenderPass
Render passes encode render commands directed as one specific render target into an underlying comman...
Definition: render_pass.h:30
impeller::RoundSuperellipseGeometry
Definition: round_superellipse_geometry.h:25
impeller::RoundSuperellipseGeometry::~RoundSuperellipseGeometry
~RoundSuperellipseGeometry() override
Definition: round_superellipse_geometry.cc:375
impeller::RoundSuperellipseGeometry::CoversArea
bool CoversArea(const Matrix &transform, const Rect &rect) const override
Determines if this geometry, transformed by the given transform, will completely cover all surface ar...
Definition: round_superellipse_geometry.cc:442
impeller::RoundSuperellipseGeometry::IsAxisAlignedRect
bool IsAxisAlignedRect() const override
Definition: round_superellipse_geometry.cc:461
impeller::RoundSuperellipseGeometry::RoundSuperellipseGeometry
RoundSuperellipseGeometry(const Rect &bounds, const RoundingRadii &radii)
Definition: round_superellipse_geometry.cc:366
impeller::Tessellator::GetStrokePointCache
std::vector< Point > & GetStrokePointCache()
Retrieve a pre-allocated arena of kPointArenaSize points.
Definition: tessellator.cc:24
x
int32_t x
Definition: dl_golden_unittests.cc:458
transform
Matrix transform
Definition: gaussian_blur_filter_contents.cc:214
constants.h
impeller::saturated::b
SI b
Definition: saturated_math.h:87
impeller
Definition: allocation.cc:12
impeller::IndexType::kNone
@ kNone
Does not use the index buffer.
impeller::PrimitiveType::kTriangleStrip
@ kTriangleStrip
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::Point
TPoint< Scalar > Point
Definition: point.h:327
impeller::kPiOver2
constexpr float kPiOver2
Definition: constants.h:32
impeller::kPointArenaSize
static constexpr size_t kPointArenaSize
The size of the point arena buffer stored on the tessellator.
Definition: tessellator.h:22
round_superellipse_geometry.h
round_superellipse_param.h
impeller::GeometryResult
Definition: geometry.h:21
impeller::Matrix
A 4x4 matrix using column-major storage.
Definition: matrix.h:37
impeller::Matrix::MakeTranslation
static constexpr Matrix MakeTranslation(const Vector3 &t)
Definition: matrix.h:95
impeller::Matrix::MakeTranslateScale
static constexpr Matrix MakeTranslateScale(const Vector3 &s, const Vector3 &t)
Definition: matrix.h:113
impeller::RoundSuperellipseParam::MakeBoundsRadii
static RoundSuperellipseParam MakeBoundsRadii(const Rect &bounds, const RoundingRadii &radii)
Definition: round_superellipse_param.cc:463
impeller::RoundSuperellipseParam::kGapFactor
static constexpr Scalar kGapFactor
Definition: round_superellipse_param.h:123
impeller::RoundingRadii
Definition: rounding_radii.h:14
impeller::RoundingRadii::top_right
Size top_right
Definition: rounding_radii.h:16
impeller::RoundingRadii::bottom_left
Size bottom_left
Definition: rounding_radii.h:17
impeller::RoundingRadii::bottom_right
Size bottom_right
Definition: rounding_radii.h:18
impeller::RoundingRadii::top_left
Size top_left
Definition: rounding_radii.h:15
impeller::TPoint< Scalar >
impeller::TPoint::Rotate
constexpr TPoint Rotate(const Radians &angle) const
Definition: point.h:226
impeller::TRect< Scalar >
impeller::TRect::GetBottom
constexpr auto GetBottom() const
Definition: rect.h:361
impeller::TRect::TransformBounds
constexpr TRect TransformBounds(const Matrix &transform) const
Creates a new bounding box that contains this transformed rectangle.
Definition: rect.h:476
impeller::TRect::GetTop
constexpr auto GetTop() const
Definition: rect.h:357
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:235
impeller::TRect::GetLeft
constexpr auto GetLeft() const
Definition: rect.h:355
impeller::TRect::GetRight
constexpr auto GetRight() const
Definition: rect.h:359
impeller::TRect::GetCenter
constexpr Point GetCenter() const
Get the center point as a |Point|.
Definition: rect.h:386
impeller::TRect< Scalar >::MakeLTRB
constexpr static TRect MakeLTRB(Type left, Type top, Type right, Type bottom)
Definition: rect.h:129
impeller::TSize::height
Type height
Definition: size.h:29
impeller::TSize::width
Type width
Definition: size.h:28