New optimized general convex path shadow algorithm (#178370)
<!--
Thanks for filing a pull request!
Reviewers are typically assigned within a week of filing a request.
To learn more about code review, see our documentation on Tree Hygiene:
https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md
-->
Convex paths will now use an optimized mesh-based algorithm to render
shadows. The algorithm is based on the code in SkShadowTessellator.
Fixes https://github.com/flutter/flutter/issues/170764
## Pre-launch Checklist
- [x] I read the [Contributor Guide] and followed the process outlined
there for submitting PRs.
- [x] I read the [Tree Hygiene] wiki page, which explains my
responsibilities.
- [x] I read and followed the [Flutter Style Guide], including [Features
we expect every widget to implement].
- [x] I signed the [CLA].
- [x] I listed at least one issue that this PR fixes in the description
above.
- [x] I updated/added relevant documentation (doc comments with `///`).
- [x] I added new tests to check the change I am making, or this PR is
[test-exempt].
- [x] I followed the [breaking change policy] and added [Data Driven
Fixes] where supported.
- [x] All existing and new tests are passing.
If you need help, consider asking for advice on the #hackers-new channel
on [Discord].
**Note**: The Flutter team is currently trialing the use of [Gemini Code
Assist for
GitHub](https://developers.google.com/gemini-code-assist/docs/review-github-code).
Comments from the `gemini-code-assist` bot should not be taken as
authoritative feedback from the Flutter team. If you find its comments
useful you can update your code accordingly, but if you are unsure or
disagree with the feedback, please feel free to wait for a Flutter team
member's review for guidance on which automated comments should be
addressed.
diff --git a/engine/src/flutter/impeller/compiler/shader_lib/impeller/gaussian.glsl b/engine/src/flutter/impeller/compiler/shader_lib/impeller/gaussian.glsl
index fef2a39..0468de5 100644
--- a/engine/src/flutter/impeller/compiler/shader_lib/impeller/gaussian.glsl
+++ b/engine/src/flutter/impeller/compiler/shader_lib/impeller/gaussian.glsl
@@ -78,4 +78,17 @@
return 1.03731472073hf / (1.0hf + exp(-4.0hf * x)) - 0.0186573603638hf;
}
+/// Converts a fraction in the range [0,1] to a guassian weighted distribution
+/// over the same range ([0,1]).
+float16_t IPHalfFractionToFastGaussianCDF(float16_t fraction) {
+ // IPErf produces outputs over [0, 1] from an input range of [-2, +2].
+ // We need to convert the fraction to the appropriate range.
+ //
+ // [0, 1] => [-2, +2]
+ // 0 * 4 - 2 == -2
+ // 1 * 4 - 2 == +2
+ float16_t x = fraction * 4.0hf - 2.0hf;
+ return (1.0hf + IPErf(x)) * 0.5hf;
+}
+
#endif
diff --git a/engine/src/flutter/impeller/display_list/BUILD.gn b/engine/src/flutter/impeller/display_list/BUILD.gn
index d3dac49..a7c3cda 100644
--- a/engine/src/flutter/impeller/display_list/BUILD.gn
+++ b/engine/src/flutter/impeller/display_list/BUILD.gn
@@ -78,6 +78,7 @@
"aiks_dl_opacity_unittests.cc",
"aiks_dl_path_unittests.cc",
"aiks_dl_runtime_effect_unittests.cc",
+ "aiks_dl_shadow_unittests.cc",
"aiks_dl_text_unittests.cc",
"aiks_dl_unittests.cc",
"aiks_dl_vertices_unittests.cc",
diff --git a/engine/src/flutter/impeller/display_list/aiks_dl_shadow_unittests.cc b/engine/src/flutter/impeller/display_list/aiks_dl_shadow_unittests.cc
new file mode 100644
index 0000000..65ff1cc
--- /dev/null
+++ b/engine/src/flutter/impeller/display_list/aiks_dl_shadow_unittests.cc
@@ -0,0 +1,934 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "flutter/impeller/display_list/aiks_unittests.h"
+
+#include "flutter/display_list/dl_builder.h"
+#include "flutter/display_list/dl_color.h"
+#include "flutter/display_list/dl_paint.h"
+#include "flutter/display_list/geometry/dl_path_builder.h"
+#include "flutter/impeller/entity/geometry/shadow_path_geometry.h"
+#include "flutter/testing/testing.h"
+
+namespace impeller {
+namespace testing {
+
+using namespace flutter;
+
+namespace {
+/// @brief Reflect the segments of a path around a coordinate using the
+/// PathReceiver interface.
+class PathReflector : public PathReceiver {
+ public:
+ /// Reflect a path horizontally around the given x coordinate.
+ static PathReflector ReflectAroundX(Scalar x_coordinate) {
+ return PathReflector(-1.0f, x_coordinate * 2.0f, 1.0f, 0.0f);
+ }
+
+ /// Reflect a path vertically around the given y coordinate.
+ static PathReflector ReflectAroundY(Scalar y_coordinate) {
+ return PathReflector(1.0f, 0.0f, -1.0f, y_coordinate * 2.0f);
+ }
+
+ /// Reflect a path horizontally and vertically around the given coordinate.
+ static PathReflector ReflectAround(const Point& anchor) {
+ return PathReflector(-1.0f, anchor.x * 2.0f, -1.0f, anchor.y * 2.0f);
+ }
+
+ // |PathReceiver|
+ void MoveTo(const Point& p2, bool will_be_closed) override {
+ path_builder_.MoveTo(reflect(p2));
+ }
+
+ // |PathReceiver|
+ void LineTo(const Point& p2) override { path_builder_.LineTo(reflect(p2)); }
+
+ // |PathReceiver|
+ void QuadTo(const Point& cp, const Point& p2) override {
+ path_builder_.QuadraticCurveTo(reflect(cp), reflect(p2));
+ }
+
+ // |PathReceiver|
+ bool ConicTo(const Point& cp, const Point& p2, Scalar weight) override {
+ path_builder_.ConicCurveTo(reflect(cp), reflect(p2), weight);
+ return true;
+ }
+
+ // |PathReceiver|
+ void CubicTo(const Point& cp1, const Point& cp2, const Point& p2) override {
+ path_builder_.CubicCurveTo(reflect(cp1), reflect(cp2), reflect(p2));
+ }
+
+ // |PathReceiver|
+ void Close() override { path_builder_.Close(); }
+
+ DlPath TakePath() { return path_builder_.TakePath(); }
+
+ private:
+ PathReflector(Scalar scale_x,
+ Scalar translate_x,
+ Scalar scale_y,
+ Scalar translate_y)
+ : scale_x_(scale_x),
+ translate_x_(translate_x),
+ scale_y_(scale_y),
+ translate_y_(translate_y) {}
+
+ const Scalar scale_x_;
+ const Scalar translate_x_;
+ const Scalar scale_y_;
+ const Scalar translate_y_;
+
+ DlPoint reflect(const DlPoint& in_point) {
+ return DlPoint(in_point.x * scale_x_ + translate_x_,
+ in_point.y * scale_y_ + translate_y_);
+ }
+
+ DlPathBuilder path_builder_;
+};
+
+DlPath ReflectPath(const DlPath& path) {
+ PathReflector reflector =
+ PathReflector::ReflectAroundY(path.GetBounds().GetCenter().y);
+ path.Dispatch(reflector);
+ return reflector.TakePath();
+}
+
+void DrawShadowMesh(DisplayListBuilder& builder,
+ const DlPath& path,
+ Scalar elevation,
+ Scalar dpr) {
+ bool should_optimize = path.IsConvex();
+ Matrix matrix = builder.GetMatrix();
+
+ // From dl_dispatcher, making a MaskFilter.
+ Scalar light_radius = 800 / 600;
+ EXPECT_EQ(light_radius, 1.0f); // Value in dl_dispatcher is bad.
+ Scalar occluder_z = elevation * dpr;
+ Radius radius = Radius{light_radius * occluder_z / matrix.GetScale().y};
+ Sigma sigma = radius;
+
+ // From canvas.cc computing the device radius.
+ Scalar device_radius = sigma.sigma * 2.8 * matrix.GetMaxBasisLengthXY();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path,
+ device_radius, matrix);
+ EXPECT_EQ(shadow_vertices != nullptr, should_optimize);
+ Point shadow_translate = Point(0, occluder_z) * matrix.Invert().GetScale().y;
+
+ DlPaint paint;
+ paint.setDrawStyle(DlDrawStyle::kStroke);
+ paint.setColor(DlColor::kDarkGrey());
+
+ if (shadow_vertices) {
+ builder.Save();
+ builder.Translate(shadow_translate.x, shadow_translate.y);
+ auto indices = shadow_vertices->GetIndices();
+ auto vertices = shadow_vertices->GetVertices();
+ DlPathBuilder mesh_builder;
+ for (size_t i = 0; i < shadow_vertices->GetIndexCount(); i += 3) {
+ mesh_builder.MoveTo(vertices[indices[i + 0]]);
+ mesh_builder.LineTo(vertices[indices[i + 1]]);
+ mesh_builder.LineTo(vertices[indices[i + 2]]);
+ mesh_builder.Close();
+ }
+ DlPath mesh_path = mesh_builder.TakePath();
+ builder.DrawPath(mesh_path, paint);
+ builder.Restore();
+ }
+
+ builder.Save();
+ builder.Translate(shadow_translate.x, shadow_translate.y);
+ paint.setColor(DlColor::kPurple());
+ builder.DrawPath(path, paint);
+ builder.Restore();
+}
+
+DlPath MakeComplexPath(const DlPath& path) {
+ DlPathBuilder path_builder;
+ path_builder.AddPath(path);
+ // A single line contour won't make any visible change to the shadow,
+ // but none of the shadow to mesh converters will touch a path that
+ // has multiple contours so this path should always default to the
+ // general shadow code based on a blur filter.
+ path_builder.LineTo(DlPoint(0, 0));
+ return path_builder.TakePath();
+}
+
+void DrawShadowAndCompareMeshes(DisplayListBuilder& builder,
+ const DlPath& path,
+ Scalar elevation,
+ Scalar dpr,
+ const DlPath* simple_path = nullptr) {
+ DlPath complex_path = MakeComplexPath(path);
+
+ builder.Save();
+
+ if (simple_path) {
+ builder.DrawShadow(*simple_path, DlColor::kBlue(), elevation, true, dpr);
+ }
+
+ builder.Translate(300, 0);
+ builder.DrawShadow(path, DlColor::kBlue(), elevation, true, dpr);
+
+ builder.Translate(300, 0);
+ builder.DrawShadow(complex_path, DlColor::kBlue(), elevation, true, dpr);
+
+ builder.Restore();
+ builder.Translate(0, 300);
+ builder.Save();
+
+ // Draw the mesh wireframe underneath the regular path output in the
+ // row above us.
+ builder.Translate(300, 0);
+ builder.DrawShadow(path, DlColor::kBlue(), elevation, true, dpr);
+ DrawShadowMesh(builder, path, elevation, dpr);
+
+ builder.Restore();
+}
+
+// Makes a Round Rect path using conics, but the weights on the corners is
+// off by just a tiny amount so the path will not be recognized.
+DlPath MakeAlmostRoundRectPath(const Rect& bounds,
+ const RoundingRadii& radii,
+ bool clockwise = true) {
+ DlScalar left = bounds.GetLeft();
+ DlScalar top = bounds.GetTop();
+ DlScalar right = bounds.GetRight();
+ DlScalar bottom = bounds.GetBottom();
+
+ // A weight of sqrt(2)/2 is how you really perform conic circular sections,
+ // but by tweaking it slightly the path will not be recognized as an oval
+ // and accelerated.
+ constexpr Scalar kWeight = kSqrt2Over2 - 0.0005f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(right - radii.top_right.width, top));
+ path_builder.ConicCurveTo(DlPoint(right, top),
+ DlPoint(right, top + radii.top_right.height),
+ kWeight);
+ path_builder.LineTo(DlPoint(right, bottom - radii.bottom_right.height));
+ path_builder.ConicCurveTo(DlPoint(right, bottom),
+ DlPoint(right - radii.bottom_right.width, bottom),
+ kWeight);
+ path_builder.LineTo(DlPoint(left + radii.bottom_left.width, bottom));
+ path_builder.ConicCurveTo(DlPoint(left, bottom),
+ DlPoint(left, bottom - radii.bottom_left.height),
+ kWeight);
+ path_builder.LineTo(DlPoint(left, top + radii.top_left.height));
+ path_builder.ConicCurveTo(DlPoint(left, top),
+ DlPoint(left + radii.top_left.width, top), //
+ kWeight);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+ if (!clockwise) {
+ path = ReflectPath(path);
+ }
+ return path;
+}
+} // namespace
+
+TEST_P(AiksTest, DrawShadowDoesNotOptimizeHourglass) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.LineTo(DlPoint(300, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowDoesNotOptimizeInnerOuterSpiral) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+ int step_count = 20;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(300, 200));
+ for (int i = 1; i < step_count * 2; i++) {
+ Scalar angle = (k2Pi * i) / step_count;
+ Scalar radius = 80.0f + std::abs(i - step_count);
+ path_builder.LineTo(DlPoint(200, 200) + DlPoint(std::cos(angle) * radius,
+ std::sin(angle) * radius));
+ }
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowDoesNotOptimizeOuterInnerSpiral) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+ int step_count = 20;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(280, 200));
+ for (int i = 1; i < step_count * 2; i++) {
+ Scalar angle = (k2Pi * i) / step_count;
+ Scalar radius = 100.0f - std::abs(i - step_count);
+ path_builder.LineTo(DlPoint(200, 200) + DlPoint(std::cos(angle) * radius,
+ std::sin(angle) * radius));
+ }
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowDoesNotOptimizeMultipleContours) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(150, 100));
+ path_builder.LineTo(DlPoint(200, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.Close();
+ path_builder.MoveTo(DlPoint(250, 100));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(200, 300));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseTriangle) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseTriangle) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseRect) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ // Tweak one corner by a sub-pixel amount to prevent recognition as
+ // a rectangle, but still generating a rectangular shadow.
+ path_builder.LineTo(DlPoint(299.9, 100));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const DlPath simple_path = DlPath::MakeRectLTRB(100, 100, 300, 300);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseRect) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.LineTo(DlPoint(300, 300));
+ // Tweak one corner by a sub-pixel amount to prevent recognition as
+ // a rectangle, but still generating a rectangular shadow.
+ path_builder.LineTo(DlPoint(299.9, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const DlPath simple_path = DlPath::MakeRectLTRB(100, 100, 300, 300);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseCircle) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ // A weight of sqrt(2) is how you really perform conic circular sections,
+ // but by tweaking it slightly the path will not be recognized as an oval
+ // and accelerated.
+ constexpr Scalar kWeight = kSqrt2Over2 - 0.0005f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.ConicCurveTo(DlPoint(300, 100), DlPoint(300, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(300, 300), DlPoint(200, 300), kWeight);
+ path_builder.ConicCurveTo(DlPoint(100, 300), DlPoint(100, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(100, 100), DlPoint(200, 100), kWeight);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const DlPath simple_path = DlPath::MakeCircle(DlPoint(200, 200), 100);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseCircle) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ // A weight of sqrt(2)/2 is how you really perform conic circular sections,
+ // but by tweaking it slightly the path will not be recognized as an oval
+ // and accelerated.
+ constexpr Scalar kWeight = kSqrt2Over2 - 0.0005f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.ConicCurveTo(DlPoint(100, 100), DlPoint(100, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(100, 300), DlPoint(200, 300), kWeight);
+ path_builder.ConicCurveTo(DlPoint(300, 300), DlPoint(300, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(300, 100), DlPoint(200, 100), kWeight);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const DlPath simple_path = DlPath::MakeCircle(DlPoint(200, 200), 100);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseOval) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ // A weight of sqrt(2) is how you really perform conic circular sections,
+ // but by tweaking it slightly the path will not be recognized as an oval
+ // and accelerated.
+ constexpr Scalar kWeight = kSqrt2Over2 - 0.0005f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 120));
+ path_builder.ConicCurveTo(DlPoint(300, 120), DlPoint(300, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(300, 280), DlPoint(200, 280), kWeight);
+ path_builder.ConicCurveTo(DlPoint(100, 280), DlPoint(100, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(100, 120), DlPoint(200, 120), kWeight);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const DlPath simple_path = DlPath::MakeOvalLTRB(100, 120, 300, 280);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseOval) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ // A weight of sqrt(2)/2 is how you really perform conic circular sections,
+ // but by tweaking it slightly the path will not be recognized as an oval
+ // and accelerated.
+ constexpr Scalar kWeight = kSqrt2Over2 - 0.0005f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 120));
+ path_builder.ConicCurveTo(DlPoint(100, 120), DlPoint(100, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(100, 280), DlPoint(200, 280), kWeight);
+ path_builder.ConicCurveTo(DlPoint(300, 280), DlPoint(300, 200), kWeight);
+ path_builder.ConicCurveTo(DlPoint(300, 120), DlPoint(200, 120), kWeight);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const DlPath simple_path = DlPath::MakeOvalLTRB(100, 120, 300, 280);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseUniformRoundRect) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPath path = MakeAlmostRoundRectPath(DlRect::MakeLTRB(100, 100, 300, 300),
+ DlRoundingRadii::MakeRadius(30), true);
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const RoundRect round_rect =
+ RoundRect::MakeRectRadius(Rect::MakeLTRB(100, 100, 300, 300), 30);
+ const DlPath simple_path = DlPath::MakeRoundRect(round_rect);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseUniformRoundRect) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPath path = MakeAlmostRoundRectPath(DlRect::MakeLTRB(100, 100, 300, 300),
+ DlRoundingRadii::MakeRadius(30), false);
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ const RoundRect round_rect =
+ RoundRect::MakeRectRadius(Rect::MakeLTRB(100, 100, 300, 300), 30);
+ const DlPath simple_path = DlPath::MakeRoundRect(round_rect);
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr, &simple_path);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseMultiRadiiRoundRect) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlRoundingRadii radii = DlRoundingRadii{
+ .top_left = {80, 60},
+ .top_right = {20, 25},
+ .bottom_left = {60, 80},
+ .bottom_right = {25, 20},
+ };
+ DlPath path = MakeAlmostRoundRectPath(DlRect::MakeLTRB(100, 100, 300, 300),
+ radii, true);
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseMultiRadiiRoundRect) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlRoundingRadii radii = DlRoundingRadii{
+ .top_left = {80, 60},
+ .top_right = {20, 25},
+ .bottom_left = {60, 80},
+ .bottom_right = {25, 20},
+ };
+ DlPath path = MakeAlmostRoundRectPath(DlRect::MakeLTRB(100, 100, 300, 300),
+ radii, false);
+
+ // Path must be convex, but unrecognizable as a simple shape.
+ ASSERT_TRUE(path.IsConvex());
+ ASSERT_FALSE(path.IsRect());
+ ASSERT_FALSE(path.IsOval());
+ ASSERT_FALSE(path.IsRoundRect());
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseQuadratic) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.QuadraticCurveTo(DlPoint(300, 100), DlPoint(300, 200));
+ path_builder.QuadraticCurveTo(DlPoint(300, 300), DlPoint(200, 300));
+ path_builder.QuadraticCurveTo(DlPoint(100, 300), DlPoint(100, 200));
+ path_builder.QuadraticCurveTo(DlPoint(100, 100), DlPoint(200, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseQuadratic) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.QuadraticCurveTo(DlPoint(100, 100), DlPoint(100, 200));
+ path_builder.QuadraticCurveTo(DlPoint(100, 300), DlPoint(200, 300));
+ path_builder.QuadraticCurveTo(DlPoint(300, 300), DlPoint(300, 200));
+ path_builder.QuadraticCurveTo(DlPoint(300, 100), DlPoint(200, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseConic) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.ConicCurveTo(DlPoint(300, 100), DlPoint(300, 200), 0.4f);
+ path_builder.ConicCurveTo(DlPoint(300, 300), DlPoint(200, 300), 0.4f);
+ path_builder.ConicCurveTo(DlPoint(100, 300), DlPoint(100, 200), 0.4f);
+ path_builder.ConicCurveTo(DlPoint(100, 100), DlPoint(200, 100), 0.4f);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseConic) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.ConicCurveTo(DlPoint(100, 100), DlPoint(100, 200), 0.4f);
+ path_builder.ConicCurveTo(DlPoint(100, 300), DlPoint(200, 300), 0.4f);
+ path_builder.ConicCurveTo(DlPoint(300, 300), DlPoint(300, 200), 0.4f);
+ path_builder.ConicCurveTo(DlPoint(300, 100), DlPoint(200, 100), 0.4f);
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseCubic) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.CubicCurveTo(DlPoint(280, 100), DlPoint(300, 120),
+ DlPoint(300, 200));
+ path_builder.CubicCurveTo(DlPoint(300, 280), DlPoint(280, 300),
+ DlPoint(200, 300));
+ path_builder.CubicCurveTo(DlPoint(120, 300), DlPoint(100, 280),
+ DlPoint(100, 200));
+ path_builder.CubicCurveTo(DlPoint(100, 120), DlPoint(120, 100),
+ DlPoint(200, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseCubic) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.CubicCurveTo(DlPoint(120, 100), DlPoint(100, 120),
+ DlPoint(100, 200));
+ path_builder.CubicCurveTo(DlPoint(100, 280), DlPoint(120, 300),
+ DlPoint(200, 300));
+ path_builder.CubicCurveTo(DlPoint(280, 300), DlPoint(300, 280),
+ DlPoint(300, 200));
+ path_builder.CubicCurveTo(DlPoint(300, 120), DlPoint(280, 100),
+ DlPoint(200, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseOctagon) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 125));
+ path_builder.LineTo(DlPoint(125, 100));
+ path_builder.LineTo(DlPoint(275, 100));
+ path_builder.LineTo(DlPoint(300, 125));
+ path_builder.LineTo(DlPoint(300, 275));
+ path_builder.LineTo(DlPoint(275, 300));
+ path_builder.LineTo(DlPoint(125, 300));
+ path_builder.LineTo(DlPoint(100, 275));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeCounterClockwiseOctagon) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 125));
+ path_builder.LineTo(DlPoint(100, 275));
+ path_builder.LineTo(DlPoint(125, 300));
+ path_builder.LineTo(DlPoint(275, 300));
+ path_builder.LineTo(DlPoint(300, 275));
+ path_builder.LineTo(DlPoint(300, 125));
+ path_builder.LineTo(DlPoint(275, 100));
+ path_builder.LineTo(DlPoint(125, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeWithExtraneousMoveTos) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.MoveTo(DlPoint(1000, 1000));
+ path_builder.MoveTo(DlPoint(100, 50));
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.Close();
+ path_builder.MoveTo(DlPoint(1000, 1000));
+ path_builder.MoveTo(DlPoint(500, 300));
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest, DrawShadowCanOptimizeClockwiseWithExtraColinearVertices) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(250, 200));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(200, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.LineTo(DlPoint(150, 200));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+TEST_P(AiksTest,
+ DrawShadowCanOptimizeCounterClockwiseWithExtraColinearVertices) {
+ DisplayListBuilder builder;
+ builder.Clear(DlColor::kWhite());
+ builder.Scale(GetContentScale().x, GetContentScale().y);
+ Scalar dpr = std::max(GetContentScale().x, GetContentScale().y);
+ Scalar elevation = 30.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(150, 200));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.LineTo(DlPoint(200, 300));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(250, 200));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ DrawShadowAndCompareMeshes(builder, path, elevation, dpr);
+
+ auto dl = builder.Build();
+ ASSERT_TRUE(OpenPlaygroundHere(dl));
+}
+
+} // namespace testing
+} // namespace impeller
diff --git a/engine/src/flutter/impeller/display_list/canvas.cc b/engine/src/flutter/impeller/display_list/canvas.cc
index 1ec4b2a..e6ffcb0 100644
--- a/engine/src/flutter/impeller/display_list/canvas.cc
+++ b/engine/src/flutter/impeller/display_list/canvas.cc
@@ -9,6 +9,7 @@
#include <unordered_map>
#include <utility>
+#include "display_list/dl_vertices.h"
#include "display_list/effects/color_filters/dl_blend_color_filter.h"
#include "display_list/effects/color_filters/dl_matrix_color_filter.h"
#include "display_list/effects/dl_color_filter.h"
@@ -20,6 +21,7 @@
#include "impeller/base/validation.h"
#include "impeller/core/formats.h"
#include "impeller/display_list/color_filter.h"
+#include "impeller/display_list/dl_vertices_geometry.h"
#include "impeller/display_list/image_filter.h"
#include "impeller/display_list/skia_conversions.h"
#include "impeller/entity/contents/atlas_contents.h"
@@ -30,6 +32,7 @@
#include "impeller/entity/contents/filters/filter_contents.h"
#include "impeller/entity/contents/framebuffer_blend_contents.h"
#include "impeller/entity/contents/line_contents.h"
+#include "impeller/entity/contents/shadow_vertices_contents.h"
#include "impeller/entity/contents/solid_rrect_blur_contents.h"
#include "impeller/entity/contents/solid_rsuperellipse_blur_contents.h"
#include "impeller/entity/contents/text_contents.h"
@@ -45,6 +48,7 @@
#include "impeller/entity/geometry/line_geometry.h"
#include "impeller/entity/geometry/point_field_geometry.h"
#include "impeller/entity/geometry/rect_geometry.h"
+#include "impeller/entity/geometry/shadow_path_geometry.h"
#include "impeller/entity/geometry/stroke_path_geometry.h"
#include "impeller/entity/save_layer_utils.h"
#include "impeller/geometry/color.h"
@@ -177,24 +181,105 @@
} // namespace
-std::shared_ptr<SolidRRectLikeBlurContents>
-Canvas::RRectBlurShape::BuildBlurContent() {
- return std::make_shared<SolidRRectBlurContents>();
-}
+class Canvas::RRectBlurShape : public BlurShape {
+ public:
+ RRectBlurShape(const Rect& rect, Scalar corner_radius)
+ : rect_(rect), corner_radius_(corner_radius) {}
-Geometry& Canvas::RRectBlurShape::BuildGeometry(Rect rect, Scalar radius) {
- return geom_.emplace(rect, Size{radius, radius});
-}
+ Rect GetBounds() const override { return rect_; }
-std::shared_ptr<SolidRRectLikeBlurContents>
-Canvas::RSuperellipseBlurShape::BuildBlurContent() {
- return std::make_shared<SolidRSuperellipseBlurContents>();
-}
+ std::shared_ptr<SolidBlurContents> BuildBlurContent(Sigma sigma) override {
+ auto contents = std::make_shared<SolidRRectBlurContents>();
+ contents->SetSigma(sigma);
+ contents->SetShape(rect_, corner_radius_);
+ return contents;
+ }
-Geometry& Canvas::RSuperellipseBlurShape::BuildGeometry(Rect rect,
- Scalar radius) {
- return geom_.emplace(rect, radius);
-}
+ const Geometry& BuildDrawGeometry() override {
+ return geom_.emplace(rect_, Size(corner_radius_));
+ }
+
+ private:
+ const Rect rect_;
+ const Scalar corner_radius_;
+
+ std::optional<RoundRectGeometry> geom_; // optional stack allocation
+};
+
+class Canvas::RSuperellipseBlurShape : public BlurShape {
+ public:
+ RSuperellipseBlurShape(const Rect& rect, Scalar corner_radius)
+ : rect_(rect), corner_radius_(corner_radius) {}
+
+ Rect GetBounds() const override { return rect_; }
+
+ std::shared_ptr<SolidBlurContents> BuildBlurContent(Sigma sigma) override {
+ auto contents = std::make_shared<SolidRSuperellipseBlurContents>();
+ contents->SetSigma(sigma);
+ contents->SetShape(rect_, corner_radius_);
+ return contents;
+ }
+
+ const Geometry& BuildDrawGeometry() override {
+ return geom_.emplace(rect_, corner_radius_);
+ }
+
+ private:
+ const Rect rect_;
+ const Scalar corner_radius_;
+
+ std::optional<RoundSuperellipseGeometry> geom_; // optional stack allocation
+};
+
+class Canvas::PathBlurShape : public BlurShape {
+ public:
+ /// Construct a PathBlurShape from a path source, a set of shadow vertices
+ /// (typically produced by ShadowPathGeometry) and the sigma that was used
+ /// to generate the vertex mesh.
+ ///
+ /// The sigma was already used to generate the shadow vertices, so it is
+ /// provided here only to make sure it matches the sigma we will see in
+ /// our BuildBlurContent method.
+ ///
+ /// The source was used to generate the mesh and it might be used again
+ /// for the SOLID mask operation so we save it here in case the mask
+ /// rendering code calls our BuildDrawGeometry method. Its lifetime
+ /// must survive the lifetime of this object, typically because the
+ /// source object was stack allocated not long before this object is
+ /// also being stack allocated.
+ PathBlurShape(const PathSource& source [[clang::lifetimebound]],
+ std::shared_ptr<ShadowVertices> shadow_vertices,
+ Sigma sigma)
+ : sigma_(sigma),
+ source_(source),
+ shadow_vertices_(std::move(shadow_vertices)) {}
+
+ Rect GetBounds() const override {
+ return shadow_vertices_->GetBounds().value_or(Rect());
+ }
+
+ std::shared_ptr<SolidBlurContents> BuildBlurContent(Sigma sigma) override {
+ // We have to use the sigma to generate the mesh up front in order to
+ // even know if we can perform the operation, but then the method that
+ // actually uses our contents informs us of the sigma, but it's too
+ // late to make use of it. Instead we remember what sigma we used and
+ // make sure they match.
+ FML_DCHECK(sigma_.sigma == sigma.sigma);
+ return ShadowVerticesContents::Make(shadow_vertices_);
+ }
+
+ const Geometry& BuildDrawGeometry() override {
+ return source_geometry_.emplace(source_);
+ }
+
+ private:
+ const Sigma sigma_;
+ const PathSource& source_;
+ const std::shared_ptr<ShadowVertices> shadow_vertices_;
+
+ // optional stack allocation - for BuildGeometry
+ std::optional<FillPathFromSourceGeometry> source_geometry_;
+};
Canvas::Canvas(ContentContext& renderer,
const RenderTarget& render_target,
@@ -326,6 +411,12 @@
}
void Canvas::DrawPath(const flutter::DlPath& path, const Paint& paint) {
+ if (IsShadowBlurDrawOperation(paint)) {
+ if (AttemptDrawBlurredPathSource(path, paint)) {
+ return;
+ }
+ }
+
Entity entity;
entity.SetTransform(GetCurrentTransform());
entity.SetBlendMode(paint.blend_mode);
@@ -456,25 +547,7 @@
return true;
}
-bool Canvas::AttemptDrawBlurredRRect(const Rect& rect,
- Size corner_radii,
- const Paint& paint) {
- RRectBlurShape rrect_shape;
- return AttemptDrawBlurredRRectLike(rect, corner_radii, paint, rrect_shape);
-}
-
-bool Canvas::AttemptDrawBlurredRSuperellipse(const Rect& rect,
- Size corner_radii,
- const Paint& paint) {
- RSuperellipseBlurShape rsuperellipse_shape;
- return AttemptDrawBlurredRRectLike(rect, corner_radii, paint,
- rsuperellipse_shape);
-}
-
-bool Canvas::AttemptDrawBlurredRRectLike(const Rect& rect,
- Size corner_radii,
- const Paint& paint,
- RRectLikeBlurShape& shape) {
+bool Canvas::IsShadowBlurDrawOperation(const Paint& paint) {
if (paint.style != Paint::Style::kFill) {
return false;
}
@@ -488,15 +561,84 @@
}
// A blur sigma that is not positive enough should not result in a blur.
+ // We test both the sigma value and the converted radius value as the
+ // algorithms might use either and either indicates the blur is too small
+ // to be noticeable.
if (paint.mask_blur_descriptor->sigma.sigma <= kEhCloseEnough) {
return false;
}
-
- // The current rrect blur math doesn't work on ovals.
- if (fabsf(corner_radii.width - corner_radii.height) > kEhCloseEnough) {
+ Radius radius = paint.mask_blur_descriptor->sigma;
+ if (radius.radius <= kEhCloseEnough) {
return false;
}
- Scalar corner_radius = corner_radii.width;
+
+ return true;
+}
+
+bool Canvas::AttemptDrawBlurredPathSource(const PathSource& source,
+ const Paint& paint) {
+ FML_DCHECK(IsShadowBlurDrawOperation);
+
+ // This has_value() test should always succeed as it is checked by the
+ // IsShadowBlurDrawOperation method which should have been called before
+ // this method, but we check again here to avoid warnings from the
+ // following code.
+ if (paint.mask_blur_descriptor.has_value()) {
+ // This value was determined by empirical eyesight tests so that the
+ // shadow mesh results will match the results of the shape-specific
+ // optimized shadow shaders.
+ static constexpr Scalar kSigmaScale = 2.8f;
+
+ Sigma sigma = paint.mask_blur_descriptor->sigma;
+ const Matrix& matrix = GetCurrentTransform();
+ Scalar basis_scale = matrix.GetMaxBasisLengthXY();
+ Scalar device_radius = sigma.sigma * kSigmaScale * basis_scale;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(
+ renderer_.GetTessellator(), source, device_radius, matrix);
+ if (shadow_vertices) {
+ PathBlurShape shape(source, std::move(shadow_vertices), sigma);
+ return AttemptDrawBlur(shape, paint);
+ }
+ }
+ return false;
+}
+
+Scalar Canvas::GetCommonRRectLikeRadius(const RoundingRadii& radii) {
+ if (!radii.AreAllCornersSame()) {
+ return -1;
+ }
+ const Size& corner_radii = radii.top_left;
+ if (ScalarNearlyEqual(corner_radii.width, corner_radii.height)) {
+ return corner_radii.width;
+ }
+ return -1;
+}
+
+bool Canvas::AttemptDrawBlurredRRect(const RoundRect& round_rect,
+ const Paint& paint) {
+ Scalar radius = GetCommonRRectLikeRadius(round_rect.GetRadii());
+ if (radius < 0) {
+ RoundRectPathSource source(round_rect);
+ return AttemptDrawBlurredPathSource(source, paint);
+ }
+ RRectBlurShape shape(round_rect.GetBounds(), radius);
+ return AttemptDrawBlur(shape, paint);
+}
+
+bool Canvas::AttemptDrawBlurredRSuperellipse(const RoundSuperellipse& rse,
+ const Paint& paint) {
+ Scalar radius = GetCommonRRectLikeRadius(rse.GetRadii());
+ if (radius < 0) {
+ RoundSuperellipsePathSource source(rse);
+ return AttemptDrawBlurredPathSource(source, paint);
+ }
+ RSuperellipseBlurShape shape(rse.GetBounds(), radius);
+ return AttemptDrawBlur(shape, paint);
+}
+
+bool Canvas::AttemptDrawBlur(BlurShape& shape, const Paint& paint) {
+ FML_DCHECK(IsShadowBlurDrawOperation(paint));
// For symmetrically mask blurred solid RRects, absorb the mask blur and use
// a faster SDF approximation.
@@ -510,6 +652,14 @@
Paint rrect_paint = {.mask_blur_descriptor = paint.mask_blur_descriptor};
+ if (!rrect_paint.mask_blur_descriptor.has_value()) {
+ // This should never happen in practice because the caller would have
+ // first called |IsShadowBlurDrawOperation| on the paint object, but
+ // we test anyway to make the compiler happy about the dereferences
+ // below.
+ return false;
+ }
+
// In some cases, we need to render the mask blur to a separate layer.
//
// 1. If the blur style is normal, we'll be drawing using one draw call and
@@ -534,7 +684,7 @@
paint.image_filter) ||
(paint.mask_blur_descriptor->style == FilterContents::BlurStyle::kSolid &&
(!rrect_color.IsOpaque() || paint.blend_mode != BlendMode::kSrcOver))) {
- Rect render_bounds = rect;
+ Rect render_bounds = shape.GetBounds();
if (paint.mask_blur_descriptor->style !=
FilterContents::BlurStyle::kInner) {
render_bounds =
@@ -556,13 +706,12 @@
Save(1u);
}
- auto draw_blurred_rrect = [this, &rect, corner_radius, &rrect_paint,
- &shape]() {
- auto contents = shape.BuildBlurContent();
+ auto draw_blurred_rrect = [this, &rrect_paint, &shape]() {
+ std::shared_ptr<SolidBlurContents> contents =
+ shape.BuildBlurContent(rrect_paint.mask_blur_descriptor->sigma);
+ FML_DCHECK(contents);
contents->SetColor(rrect_paint.color);
- contents->SetSigma(rrect_paint.mask_blur_descriptor->sigma);
- contents->SetShape(rect, corner_radius);
Entity blurred_rrect_entity;
blurred_rrect_entity.SetTransform(GetCurrentTransform());
@@ -587,19 +736,19 @@
entity.SetTransform(GetCurrentTransform());
entity.SetBlendMode(rrect_paint.blend_mode);
- Geometry& geom = shape.BuildGeometry(rect, corner_radius);
+ const Geometry& geom = shape.BuildDrawGeometry();
AddRenderEntityWithFiltersToCurrentPass(entity, &geom, rrect_paint,
/*reuse_depth=*/true);
break;
}
case FilterContents::BlurStyle::kOuter: {
- Geometry& geom = shape.BuildGeometry(rect, corner_radius);
+ const Geometry& geom = shape.BuildDrawGeometry();
ClipGeometry(geom, Entity::ClipOperation::kDifference);
draw_blurred_rrect();
break;
}
case FilterContents::BlurStyle::kInner: {
- Geometry& geom = shape.BuildGeometry(rect, corner_radius);
+ const Geometry& geom = shape.BuildDrawGeometry();
ClipGeometry(geom, Entity::ClipOperation::kIntersect);
draw_blurred_rrect();
break;
@@ -660,8 +809,11 @@
}
void Canvas::DrawRect(const Rect& rect, const Paint& paint) {
- if (AttemptDrawBlurredRRect(rect, {}, paint)) {
- return;
+ if (IsShadowBlurDrawOperation(paint)) {
+ RRectBlurShape shape(rect, 0.0f);
+ if (AttemptDrawBlur(shape, paint)) {
+ return;
+ }
}
Entity entity;
@@ -689,8 +841,20 @@
return;
}
- if (AttemptDrawBlurredRRect(rect, rect.GetSize() * 0.5f, paint)) {
- return;
+ if (IsShadowBlurDrawOperation(paint)) {
+ if (rect.IsSquare()) {
+ // RRectBlurShape takes the corner radii which are half of the
+ // overall width and height of the DrawOval bounds rect.
+ RRectBlurShape shape(rect, rect.GetWidth() * 0.5f);
+ if (AttemptDrawBlur(shape, paint)) {
+ return;
+ }
+ } else {
+ EllipsePathSource source(rect);
+ if (AttemptDrawBlurredPathSource(source, paint)) {
+ return;
+ }
+ }
}
Entity entity;
@@ -759,22 +923,22 @@
}
void Canvas::DrawRoundRect(const RoundRect& round_rect, const Paint& paint) {
- auto& rect = round_rect.GetBounds();
- auto& radii = round_rect.GetRadii();
- if (radii.AreAllCornersSame()) {
- if (AttemptDrawBlurredRRect(rect, radii.top_left, paint)) {
+ if (IsShadowBlurDrawOperation(paint)) {
+ if (AttemptDrawBlurredRRect(round_rect, paint)) {
return;
}
+ }
- if (paint.style == Paint::Style::kFill) {
- Entity entity;
- entity.SetTransform(GetCurrentTransform());
- entity.SetBlendMode(paint.blend_mode);
+ if (round_rect.GetRadii().AreAllCornersSame() &&
+ paint.style == Paint::Style::kFill) {
+ Entity entity;
+ entity.SetTransform(GetCurrentTransform());
+ entity.SetBlendMode(paint.blend_mode);
- RoundRectGeometry geom(rect, radii.top_left);
- AddRenderEntityWithFiltersToCurrentPass(entity, &geom, paint);
- return;
- }
+ RoundRectGeometry geom(round_rect.GetBounds(),
+ round_rect.GetRadii().top_left);
+ AddRenderEntityWithFiltersToCurrentPass(entity, &geom, paint);
+ return;
}
Entity entity;
@@ -808,11 +972,10 @@
void Canvas::DrawRoundSuperellipse(const RoundSuperellipse& round_superellipse,
const Paint& paint) {
- auto& rect = round_superellipse.GetBounds();
- auto& radii = round_superellipse.GetRadii();
- if (radii.AreAllCornersSame() &&
- AttemptDrawBlurredRSuperellipse(rect, radii.top_left, paint)) {
- return;
+ if (IsShadowBlurDrawOperation(paint)) {
+ if (AttemptDrawBlurredRSuperellipse(round_superellipse, paint)) {
+ return;
+ }
}
Entity entity;
@@ -820,7 +983,8 @@
entity.SetBlendMode(paint.blend_mode);
if (paint.style == Paint::Style::kFill) {
- RoundSuperellipseGeometry geom(rect, radii);
+ RoundSuperellipseGeometry geom(round_superellipse.GetBounds(),
+ round_superellipse.GetRadii());
AddRenderEntityWithFiltersToCurrentPass(entity, &geom, paint);
} else {
StrokeRoundSuperellipseGeometry geom(round_superellipse, paint.stroke);
@@ -831,11 +995,13 @@
void Canvas::DrawCircle(const Point& center,
Scalar radius,
const Paint& paint) {
- Size half_size(radius, radius);
- if (AttemptDrawBlurredRRect(
- Rect::MakeOriginSize(center - half_size, half_size * 2),
- {radius, radius}, paint)) {
- return;
+ if (IsShadowBlurDrawOperation(paint)) {
+ Rect bounds = Rect::MakeLTRB(center.x - radius, center.y - radius,
+ center.x + radius, center.y + radius);
+ RRectBlurShape shape(bounds, radius);
+ if (AttemptDrawBlur(shape, paint)) {
+ return;
+ }
}
if (AttemptDrawAntialiasedCircle(center, radius, paint)) {
diff --git a/engine/src/flutter/impeller/display_list/canvas.h b/engine/src/flutter/impeller/display_list/canvas.h
index 9126263..f76751d 100644
--- a/engine/src/flutter/impeller/display_list/canvas.h
+++ b/engine/src/flutter/impeller/display_list/canvas.h
@@ -283,31 +283,17 @@
bool EnsureFinalMipmapGeneration() const;
private:
- class RRectLikeBlurShape {
+ class BlurShape {
public:
- virtual ~RRectLikeBlurShape() = default;
- virtual std::shared_ptr<SolidRRectLikeBlurContents> BuildBlurContent() = 0;
- virtual Geometry& BuildGeometry(Rect rect, Scalar radius) = 0;
+ virtual ~BlurShape() = default;
+ virtual Rect GetBounds() const = 0;
+ virtual std::shared_ptr<SolidBlurContents> BuildBlurContent(
+ Sigma sigma) = 0;
+ virtual const Geometry& BuildDrawGeometry() = 0;
};
-
- class RRectBlurShape : public RRectLikeBlurShape {
- public:
- std::shared_ptr<SolidRRectLikeBlurContents> BuildBlurContent() override;
- Geometry& BuildGeometry(Rect rect, Scalar radius) override;
-
- private:
- std::optional<RoundRectGeometry> geom_; // optional stack allocation
- };
-
- class RSuperellipseBlurShape : public RRectLikeBlurShape {
- public:
- std::shared_ptr<SolidRRectLikeBlurContents> BuildBlurContent() override;
- Geometry& BuildGeometry(Rect rect, Scalar radius) override;
-
- private:
- std::optional<RoundSuperellipseGeometry>
- geom_; // optional stack allocation
- };
+ class RRectBlurShape;
+ class RSuperellipseBlurShape;
+ class PathBlurShape;
ContentContext& renderer_;
RenderTarget render_target_;
@@ -395,22 +381,27 @@
void AddRenderEntityToCurrentPass(Entity& entity, bool reuse_depth = false);
+ /// Returns true if this operation is consistent with a DrawShadow-like
+ /// operation.
+ static bool IsShadowBlurDrawOperation(const Paint& paint);
+
bool AttemptDrawAntialiasedCircle(const Point& center,
Scalar radius,
const Paint& paint);
- bool AttemptDrawBlurredRRect(const Rect& rect,
- Size corner_radii,
- const Paint& paint);
+ /// Returns the radius common to both width and height of all corners,
+ /// or -1 if the radii are not uniform.
+ static Scalar GetCommonRRectLikeRadius(const RoundingRadii& radii);
- bool AttemptDrawBlurredRSuperellipse(const Rect& rect,
- Size corner_radii,
+ bool AttemptDrawBlurredPathSource(const PathSource& source,
+ const Paint& paint);
+
+ bool AttemptDrawBlurredRRect(const RoundRect& round_rect, const Paint& paint);
+
+ bool AttemptDrawBlurredRSuperellipse(const RoundSuperellipse& rse,
const Paint& paint);
- bool AttemptDrawBlurredRRectLike(const Rect& rect,
- Size corner_radii,
- const Paint& paint,
- RRectLikeBlurShape& shape);
+ bool AttemptDrawBlur(BlurShape& shape, const Paint& paint);
/// For simple DrawImageRect calls, optimize any draws with a color filter
/// into the corresponding atlas draw.
diff --git a/engine/src/flutter/impeller/entity/BUILD.gn b/engine/src/flutter/impeller/entity/BUILD.gn
index 25435cf..4ea72ab 100644
--- a/engine/src/flutter/impeller/entity/BUILD.gn
+++ b/engine/src/flutter/impeller/entity/BUILD.gn
@@ -43,6 +43,8 @@
"shaders/rrect_like_blur.vert",
"shaders/rsuperellipse_blur.frag",
"shaders/runtime_effect.vert",
+ "shaders/shadow_vertices.frag",
+ "shaders/shadow_vertices.vert",
"shaders/solid_fill.frag",
"shaders/solid_fill.vert",
"shaders/texture_fill.frag",
@@ -178,6 +180,8 @@
"contents/radial_gradient_contents.h",
"contents/runtime_effect_contents.cc",
"contents/runtime_effect_contents.h",
+ "contents/shadow_vertices_contents.cc",
+ "contents/shadow_vertices_contents.h",
"contents/solid_color_contents.cc",
"contents/solid_color_contents.h",
"contents/solid_rrect_blur_contents.cc",
@@ -228,6 +232,8 @@
"geometry/round_rect_geometry.h",
"geometry/round_superellipse_geometry.cc",
"geometry/round_superellipse_geometry.h",
+ "geometry/shadow_path_geometry.cc",
+ "geometry/shadow_path_geometry.h",
"geometry/stroke_path_geometry.cc",
"geometry/stroke_path_geometry.h",
"geometry/superellipse_geometry.cc",
@@ -286,6 +292,7 @@
"entity_playground.h",
"entity_unittests.cc",
"geometry/geometry_unittests.cc",
+ "geometry/shadow_path_geometry_unittests.cc",
"render_target_cache_unittests.cc",
"save_layer_utils_unittests.cc",
]
@@ -298,6 +305,7 @@
"//flutter/display_list/testing:display_list_testing",
"//flutter/impeller/renderer/testing:mocks",
"//flutter/impeller/typographer/backends/skia:typographer_skia_backend",
+ "//flutter/testing",
"//flutter/txt",
]
}
diff --git a/engine/src/flutter/impeller/entity/contents/content_context.cc b/engine/src/flutter/impeller/entity/contents/content_context.cc
index 6aba413..6db866d 100644
--- a/engine/src/flutter/impeller/entity/contents/content_context.cc
+++ b/engine/src/flutter/impeller/entity/contents/content_context.cc
@@ -290,6 +290,7 @@
Variants<RadialGradientUniformFillPipeline> radial_gradient_uniform_fill;
Variants<RRectBlurPipeline> rrect_blur;
Variants<RSuperellipseBlurPipeline> rsuperellipse_blur;
+ Variants<ShadowVerticesShader> shadow_vertices_;
Variants<SolidFillPipeline> solid_fill;
Variants<SrgbToLinearFilterPipeline> srgb_to_linear_filter;
Variants<SweepGradientFillPipeline> sweep_gradient_fill;
@@ -715,6 +716,7 @@
options_trianglestrip);
pipelines_->color_matrix_color_filter.CreateDefault(*context_,
options_trianglestrip);
+ pipelines_->shadow_vertices_.CreateDefault(*context_, options);
pipelines_->vertices_uber_1_.CreateDefault(*context_, options,
{supports_decal});
pipelines_->vertices_uber_2_.CreateDefault(*context_, options,
@@ -1508,6 +1510,11 @@
return GetPipeline(this, pipelines_->framebuffer_blend_softlight, opts);
}
+PipelineRef ContentContext::GetDrawShadowVerticesPipeline(
+ ContentContextOptions opts) const {
+ return GetPipeline(this, pipelines_->shadow_vertices_, opts);
+}
+
PipelineRef ContentContext::GetDrawVerticesUberPipeline(
BlendMode blend_mode,
ContentContextOptions opts) const {
diff --git a/engine/src/flutter/impeller/entity/contents/content_context.h b/engine/src/flutter/impeller/entity/contents/content_context.h
index d3e4129..b121e35 100644
--- a/engine/src/flutter/impeller/entity/contents/content_context.h
+++ b/engine/src/flutter/impeller/entity/contents/content_context.h
@@ -162,6 +162,7 @@
PipelineRef GetDestinationOutBlendPipeline(ContentContextOptions opts) const;
PipelineRef GetDestinationOverBlendPipeline(ContentContextOptions opts) const;
PipelineRef GetDownsamplePipeline(ContentContextOptions opts) const;
+ PipelineRef GetDrawShadowVerticesPipeline(ContentContextOptions opts) const;
PipelineRef GetDownsampleBoundedPipeline(ContentContextOptions opts) const;
PipelineRef GetDrawVerticesUberPipeline(BlendMode blend_mode, ContentContextOptions opts) const;
PipelineRef GetFastGradientPipeline(ContentContextOptions opts) const;
diff --git a/engine/src/flutter/impeller/entity/contents/pipelines.h b/engine/src/flutter/impeller/entity/contents/pipelines.h
index 5856240..25f8253 100644
--- a/engine/src/flutter/impeller/entity/contents/pipelines.h
+++ b/engine/src/flutter/impeller/entity/contents/pipelines.h
@@ -48,6 +48,8 @@
#include "impeller/entity/rrect_blur.frag.h"
#include "impeller/entity/rrect_like_blur.vert.h"
#include "impeller/entity/rsuperellipse_blur.frag.h"
+#include "impeller/entity/shadow_vertices.frag.h"
+#include "impeller/entity/shadow_vertices.vert.h"
#include "impeller/entity/solid_fill.frag.h"
#include "impeller/entity/solid_fill.vert.h"
#include "impeller/entity/srgb_to_linear_filter.frag.h"
@@ -145,6 +147,7 @@
using RadialGradientUniformFillPipeline = GradientPipelineHandle<RadialGradientUniformFillFragmentShader>;
using RRectBlurPipeline = RenderPipelineHandle<RrectLikeBlurVertexShader, RrectBlurFragmentShader>;
using RSuperellipseBlurPipeline = RenderPipelineHandle<RrectLikeBlurVertexShader, RsuperellipseBlurFragmentShader>;
+using ShadowVerticesShader = RenderPipelineHandle<ShadowVerticesVertexShader, ShadowVerticesFragmentShader>;
using SolidFillPipeline = RenderPipelineHandle<SolidFillVertexShader, SolidFillFragmentShader>;
using SrgbToLinearFilterPipeline = RenderPipelineHandle<FilterPositionVertexShader, SrgbToLinearFilterFragmentShader>;
using SweepGradientFillPipeline = GradientPipelineHandle<SweepGradientFillFragmentShader>;
diff --git a/engine/src/flutter/impeller/entity/contents/shadow_vertices_contents.cc b/engine/src/flutter/impeller/entity/contents/shadow_vertices_contents.cc
new file mode 100644
index 0000000..289bc82
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/contents/shadow_vertices_contents.cc
@@ -0,0 +1,83 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "shadow_vertices_contents.h"
+
+#include <format>
+
+#include "fml/logging.h"
+#include "impeller/base/validation.h"
+#include "impeller/core/formats.h"
+#include "impeller/entity/contents/content_context.h"
+#include "impeller/entity/contents/contents.h"
+#include "impeller/entity/contents/filters/blend_filter_contents.h"
+#include "impeller/entity/contents/pipelines.h"
+#include "impeller/entity/geometry/geometry.h"
+#include "impeller/entity/geometry/vertices_geometry.h"
+#include "impeller/geometry/color.h"
+#include "impeller/renderer/render_pass.h"
+
+namespace impeller {
+
+//------------------------------------------------------
+// ShadowVerticesContents
+
+ShadowVerticesContents::ShadowVerticesContents(
+ const std::shared_ptr<ShadowVertices>& geometry)
+ : geometry_(geometry) {}
+
+ShadowVerticesContents::~ShadowVerticesContents() {}
+
+std::shared_ptr<ShadowVerticesContents> ShadowVerticesContents::Make(
+ const std::shared_ptr<ShadowVertices>& geometry) {
+ return std::make_shared<ShadowVerticesContents>(geometry);
+}
+
+std::optional<Rect> ShadowVerticesContents::GetCoverage(
+ const Entity& entity) const {
+ return geometry_->GetBounds();
+}
+
+void ShadowVerticesContents::SetColor(Color color) {
+ shadow_color_ = color;
+}
+
+bool ShadowVerticesContents::Render(const ContentContext& renderer,
+ const Entity& entity,
+ RenderPass& pass) const {
+ using VS = ShadowVerticesVertexShader;
+ using FS = ShadowVerticesFragmentShader;
+
+ GeometryResult geometry_result =
+ geometry_->GetPositionBuffer(renderer, entity, pass);
+ if (geometry_result.vertex_buffer.vertex_count == 0) {
+ return true;
+ }
+ FML_DCHECK(geometry_result.mode == GeometryResult::Mode::kNormal);
+
+#ifdef IMPELLER_DEBUG
+ pass.SetCommandLabel("DrawShadow VertexMesh");
+#endif // IMPELLER_DEBUG
+
+ pass.SetVertexBuffer(std::move(geometry_result.vertex_buffer));
+
+ auto options = OptionsFromPassAndEntity(pass, entity);
+ options.primitive_type = geometry_result.type;
+ pass.SetPipeline(renderer.GetDrawShadowVerticesPipeline(options));
+
+ VS::FrameInfo frame_info;
+ FS::FragInfo frag_info;
+
+ frame_info.mvp = entity.GetShaderTransform(pass);
+
+ frag_info.shadow_color = shadow_color_.Premultiply();
+
+ auto& host_buffer = renderer.GetTransientsDataBuffer();
+ FS::BindFragInfo(pass, host_buffer.EmplaceUniform(frag_info));
+ VS::BindFrameInfo(pass, host_buffer.EmplaceUniform(frame_info));
+
+ return pass.Draw().ok();
+}
+
+} // namespace impeller
diff --git a/engine/src/flutter/impeller/entity/contents/shadow_vertices_contents.h b/engine/src/flutter/impeller/entity/contents/shadow_vertices_contents.h
new file mode 100644
index 0000000..c69827e
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/contents/shadow_vertices_contents.h
@@ -0,0 +1,52 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef FLUTTER_IMPELLER_ENTITY_CONTENTS_SHADOW_VERTICES_CONTENTS_H_
+#define FLUTTER_IMPELLER_ENTITY_CONTENTS_SHADOW_VERTICES_CONTENTS_H_
+
+#include <memory>
+
+#include "impeller/entity/contents/contents.h"
+#include "impeller/entity/contents/solid_rrect_blur_contents.h"
+#include "impeller/entity/entity.h"
+#include "impeller/entity/geometry/shadow_path_geometry.h"
+#include "impeller/geometry/color.h"
+
+namespace impeller {
+
+/// A vertices contents for (optional) per-color vertices + texture and any
+/// blend mode.
+class ShadowVerticesContents final : public SolidBlurContents {
+ public:
+ static std::shared_ptr<ShadowVerticesContents> Make(
+ const std::shared_ptr<ShadowVertices>& geometry);
+
+ // |SolidBlurContents|
+ void SetColor(Color color) override;
+
+ // |Contents|
+ std::optional<Rect> GetCoverage(const Entity& entity) const override;
+
+ // |Contents|
+ bool Render(const ContentContext& renderer,
+ const Entity& entity,
+ RenderPass& pass) const override;
+
+ explicit ShadowVerticesContents(
+ const std::shared_ptr<ShadowVertices>& geometry);
+
+ ~ShadowVerticesContents() override;
+
+ private:
+ const std::shared_ptr<ShadowVertices> geometry_;
+ Color shadow_color_;
+
+ ShadowVerticesContents(const ShadowVerticesContents&) = delete;
+
+ ShadowVerticesContents& operator=(const ShadowVerticesContents&) = delete;
+};
+
+} // namespace impeller
+
+#endif // FLUTTER_IMPELLER_ENTITY_CONTENTS_SHADOW_VERTICES_CONTENTS_H_
diff --git a/engine/src/flutter/impeller/entity/contents/solid_rrect_like_blur_contents.h b/engine/src/flutter/impeller/entity/contents/solid_rrect_like_blur_contents.h
index eb5ca80..a65b721 100644
--- a/engine/src/flutter/impeller/entity/contents/solid_rrect_like_blur_contents.h
+++ b/engine/src/flutter/impeller/entity/contents/solid_rrect_like_blur_contents.h
@@ -15,9 +15,19 @@
namespace impeller {
+/// @brief A base class for any accelerated single color blur Contents
+/// that lets the |Canvas::AttemptDrawBlur| call deliver the
+/// color after the contents has been constructed and the method
+/// has a chance to re-consider the actual color that will be
+/// used to render the shadow.
+class SolidBlurContents : public Contents {
+ public:
+ virtual void SetColor(Color color) = 0;
+};
+
/// @brief A base class for SolidRRectBlurContents and
/// SolidRSuperellipseBlurContents.
-class SolidRRectLikeBlurContents : public Contents {
+class SolidRRectLikeBlurContents : public SolidBlurContents {
public:
~SolidRRectLikeBlurContents() override;
@@ -25,7 +35,8 @@
void SetSigma(Sigma sigma);
- void SetColor(Color color);
+ // |SolidBlurContents|
+ void SetColor(Color color) override;
Color GetColor() const;
diff --git a/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.cc b/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.cc
index 4c0434f..e2af972 100644
--- a/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.cc
+++ b/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.cc
@@ -92,6 +92,13 @@
return coverage.Contains(rect);
}
+FillPathFromSourceGeometry::FillPathFromSourceGeometry(const PathSource& source)
+ : FillPathSourceGeometry(std::nullopt), source_(source) {}
+
+const PathSource& FillPathFromSourceGeometry::GetSource() const {
+ return source_;
+}
+
FillPathGeometry::FillPathGeometry(const flutter::DlPath& path,
std::optional<Rect> inner_rect)
: FillPathSourceGeometry(inner_rect), path_(path) {}
diff --git a/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.h b/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.h
index 5ce6466..3a3346d 100644
--- a/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.h
+++ b/engine/src/flutter/impeller/entity/geometry/fill_path_geometry.h
@@ -49,6 +49,19 @@
FillPathSourceGeometry& operator=(const FillPathSourceGeometry&) = delete;
};
+/// @brief A Geometry that produces fillable vertices from a |PathSource| object
+/// using the |FillPathSourceGeometry|.
+class FillPathFromSourceGeometry final : public FillPathSourceGeometry {
+ public:
+ explicit FillPathFromSourceGeometry(const PathSource& source);
+
+ protected:
+ const PathSource& GetSource() const override;
+
+ private:
+ const PathSource& source_;
+};
+
/// @brief A Geometry that produces fillable vertices from a |DlPath| object
/// using the |FillPathSourceGeometry| base class and the inherent
/// ability for a |DlPath| object to perform path iteration.
diff --git a/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry.cc b/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry.cc
new file mode 100644
index 0000000..e0b97a0
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry.cc
@@ -0,0 +1,1467 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "flutter/impeller/entity/geometry/shadow_path_geometry.h"
+
+#include "flutter/impeller/entity/contents/pipelines.h"
+#include "flutter/impeller/geometry/path_source.h"
+#include "flutter/impeller/tessellator/path_tessellator.h"
+
+namespace {
+
+using impeller::kEhCloseEnough;
+using impeller::Matrix;
+using impeller::PathTessellator;
+using impeller::Point;
+using impeller::Scalar;
+using impeller::ScalarNearlyZero;
+using impeller::ShadowVertices;
+using impeller::Tessellator;
+using impeller::Trig;
+using impeller::Vector2;
+
+/// Each point in the polygon form of the path is turned into a structure
+/// that tracks the gradient of the shadow at that point in the path. The
+/// shape is turned into a sort of pin cushion where each struct acts
+/// like a pin pushed into that cushion in the direction of the shadow
+/// gradient at that location.
+///
+/// Each entry contains the direction of the pin at that location and the
+/// depth to which the pin is inserted, expressed as a fraction of the full
+/// umbra size indicated by the shadow parameters. A depth of 1.0 means
+/// the pin was inserted all the way to the depth of the shadow gradient
+/// and didn't collide with any other pins. A fraction less than 1.0 can
+/// occur if either the shape was too small and the pins intersected with
+/// other pins across the shape from them, or if the curvature in a given
+/// area was so tight that adjacent pins started bumping into their neighbors
+/// even if the overall size of the shape was larger than the shadow.
+///
+/// Different pins will be shortened by different amounts in the same shape
+/// depending on their local geometry (tight curves or narrow cross section).
+struct UmbraPin {
+ /// An initial value for the pin fraction that indicates that we have
+ /// not yet visited this pin during the clipping process.
+ static constexpr Scalar kFractionUninitialized = -1.0f;
+
+ /// The point on the original path that generated this entry into the
+ /// umbra geometry.
+ ///
+ /// AKA the point on the path at which this pin was stabbed.
+ Point path_vertex;
+
+ /// The relative vector from this path segment to the next.
+ Vector2 path_delta;
+
+ /// The vector from the path_vertex to the head of the pin (the part
+ /// outside the shape).
+ Vector2 penumbra_delta;
+
+ /// The location of the end of this pin, taking into account the reduction
+ /// of the umbra_size due to minimum distance to centroid, but ignoring
+ /// clipping against other pins.
+ Point pin_tip;
+
+ /// The location that this pin confers to the umbra polygon. Initially,
+ /// this is the same as the pin_tip, but can be reduced by intersecting
+ /// and clipping against other pins and even eliminated if the other
+ /// nearby pins make it redundant for defining the umbra polygon.
+ ///
+ /// Redundant or "removed" pins are indicated by no longer being a part
+ /// of the linked list formed by the |p_next| and |p_prev| pointers.
+ ///
+ /// Eventually, if this pin's umbra_vertex was eliminated, this location
+ /// will be overwritten by the surviving umbra vertex that best servies
+ /// this pin's path_vertex in a follow-on step.
+ Point umbra_vertex;
+
+ /// The index in the vertices vector where the umbra_vertex is eventually
+ /// inserted. Used to enter triangles into the indices vector.
+ uint16_t umbra_index = 0u;
+
+ /// The interior penetration of the umbra starts out at the full blur
+ /// radius as modified by the global distance of the path segments to
+ /// the centroid, but can be shortened when pins are too crowded and start
+ /// intersecting each other due to tight curvature.
+ ///
+ /// It's initial value is actually the uninitialized constant so that the
+ /// algorithm can treat it specially the first time it is encountered.
+ Scalar umbra_fraction = kFractionUninitialized;
+
+ /// Pointers used to create a circular linked list while pruning the umbra
+ /// polygon. The final list of vertices that remain in the umbra polygon
+ /// are the vertices that remain on this linked list from a "head" pin.
+ UmbraPin* p_next = nullptr;
+ UmbraPin* p_prev = nullptr;
+
+ /// Returns true after the umbra_fraction is first initialized to a real
+ /// value representing its potential intersections with other pins. At
+ /// that point it will be a number from 0 to 1.
+ bool IsFractionInitialized() const {
+ return umbra_fraction > kFractionUninitialized;
+ }
+};
+
+/// Simple cross products of nearby vertices don't catch all cases of
+/// non-convexity so we count the number of times that the sign of the
+/// dx/dy of the edges change. It must be <= 3 times for the path to
+/// be convex. Think of drawing a circle from the top. First you head
+/// to the right, then reverse to the left as you round the bottom of
+/// the circle, then back near the top you head to the right again,
+/// totalling 3 changes in direction.
+struct DirectionDetector {
+ Scalar last_direction_ = 0.0f;
+ size_t change_count = 0u;
+
+ /// Check the coordinate delta for a new polygon edge to see if it
+ /// represents another change in direction for the path on this axis.
+ void AccumulateDirection(Scalar new_direction) {
+ if (last_direction_ == 0.0f || last_direction_ * new_direction < 0.0f) {
+ last_direction_ = std::copysign(1.0f, new_direction);
+ change_count++;
+ }
+ }
+
+ /// Returns true if the path must be concave.
+ bool IsConcave() const {
+ // See comment above on the struct for why 3 changes is the most you
+ // should see in a convex path.
+ return change_count > 3u;
+ }
+};
+
+/// Utility class to receive the vertices of a path and turn them into
+/// a vector of UmbraPins along with a centroid Point.
+///
+/// The class will immediately flag and stop processing any path that
+/// has more than one contour since algorithms of the nature implemented
+/// here won't be able to process such paths.
+///
+/// The class will also flag and stop processing any path that has a
+/// non-convex section because the current algorithm only works for convex
+/// paths. Though it is possible to improve the algorithm to handle
+/// concave single-contour paths in the future as the Skia utilities
+/// provide a solution for those paths.
+class UmbraPinAccumulator : public PathTessellator::VertexWriter {
+ public:
+ /// Parameters that determine the sub-pixel grid we will use to simplify
+ /// the contours to avoid degenerate differences in the vertices.
+ /// These 2 constants are a pair used in the implementation of the
+ /// ToDeviceGrid method and must be reciprocals of each other.
+ ///
+ /// @see ToPixelGrid
+ static constexpr Scalar kSubPixelCount = 16.0f;
+ static constexpr Scalar kSubPixelScale = (1.0f / kSubPixelCount);
+
+ /// The classification status of the path after all of the points are
+ /// accumulated.
+ enum class PathStatus {
+ /// The path was empty either because it contained no points or
+ /// because they enclosed no area.
+ kEmpty,
+
+ /// The path was complete, a single contour, and convex all around.
+ kConvex,
+
+ /// The path violated one of the conditions of convexity. Either it
+ /// had points that turned different ways along its perimeter, or it
+ /// turned more than 360 degrees, or it self-intersected.
+ kNonConvex,
+
+ /// The path had multiple contours.
+ kMultipleContours,
+ };
+
+ UmbraPinAccumulator() = default;
+ ~UmbraPinAccumulator() = default;
+
+ /// Reserve enough pins for the indicated number of path vertices to
+ /// avoid having to grow the vector during processing.
+ void Reserve(size_t vertex_count) { pins_.reserve(vertex_count); }
+
+ /// Return the status properties of the path.
+ /// see |PathStatus|
+ PathStatus GetStatus() { return GetResults().status; }
+
+ /// Returns a reference to the accumulated vector of UmbraPin structs.
+ /// Only valid if the status is kConvex.
+ std::vector<UmbraPin>& GetPins() { return pins_; }
+
+ /// Returns the centroid of the path.
+ /// Only valid if the status is kConvex.
+ Point GetCentroid() { return GetResults().centroid; }
+
+ /// Returns the turning direction of the path.
+ /// Only valid if the status is kConvex.
+ Scalar GetDirection() { return GetResults().path_direction; }
+
+ private:
+ /// The data computed when completing (finalizing) the analysis of the
+ /// path.
+ struct PathResults {
+ /// The type of path determined during the final analysis.
+ PathStatus status;
+
+ /// The centroid ("center of mass") of the path around which we will
+ /// build the shadow mesh.
+ Point centroid;
+
+ /// The direction of the path as determined by cross products. This
+ /// value is important to further processing to know when pins are
+ /// intersecting each other as the calculations for that condition
+ /// depend on the direction of the path.
+ Scalar path_direction = 0.0f;
+ };
+
+ // |VertexWriter|
+ void Write(Point point) override;
+
+ // |VertexWriter|
+ void EndContour() override;
+
+ /// Rounds the device coordinate to the sub-pixel grid.
+ static Point ToDeviceGrid(Point point);
+
+ /// The list of pins being accumulated for further processing by the
+ /// mesh generation code.
+ std::vector<UmbraPin> pins_;
+
+ /// Internal state variable used by the VertexWriter callbacks to know
+ /// if the path contained multiple contours. It is set to true when the
+ /// first contour is ended by a call to EndContour().
+ bool first_contour_ended_ = false;
+
+ /// Internal state variable used by the VertexWriter callbacks to know
+ /// if the path contained multiple contours. It is set to true if additional
+ /// path points are delivered after the first contour is ended.
+ bool has_multiple_contours_ = false;
+
+ /// The results of finalizing the analysis of the path, set only after
+ /// the final analysis method is run.
+ std::optional<PathResults> results_;
+
+ /// Finalize the path analysis if necessary and return the structure with
+ /// the results of the analysis.
+ PathResults& GetResults() {
+ if (results_.has_value()) {
+ return results_.value();
+ }
+ return (results_ = FinalizePath()).value();
+ }
+
+ /// Run through the accumulated, de-duplicated, de-collinearized points
+ /// and check for a convex, non-self-intersecting path.
+ PathResults FinalizePath();
+};
+
+/// The |PolygonInfo| class does most of the work of generating a mesh from
+/// a path, including transforming it into device space, computing new vertices
+/// by applying the inset and outset for the indicated occluder_height, and
+/// then stitching all of those vertices together into a mesh that can be
+/// used to render the shadow complete with gaussian coefficients for the
+/// location of the mesh points within the shadow.
+class PolygonInfo {
+ public:
+ /// Return the radius of the rounded corners of the shadow for the
+ /// indicated occluder_height.
+ static constexpr Scalar GetTrigRadiusForHeight(Scalar occluder_height) {
+ return GetPenumbraSizeForHeight(occluder_height);
+ }
+
+ /// Construct a PolygonInfo that will accept a path and compute a shadow
+ /// mesh at the indicated occluder_height.
+ explicit PolygonInfo(Scalar occluder_height);
+
+ /// Computes a shadow mesh for the indicated path (source) under the
+ /// given matrix with the associated trigs. If the algorithm is successful,
+ /// it will return the resulting mesh (which may be empty if the path
+ /// contained no area) or nullptr if it was unable to process the path.
+ ///
+ /// @param source The PathSource object that delivers the path segments
+ /// that define the path being shadowed.
+ /// @param matrix The transform matrix under which the shadow is being
+ /// viewed.
+ /// @param trigs The Trigs array that contains precomputed sin and cos
+ /// values for a flattened arc at the required radius for
+ /// rounding out the edges of the shadow as we turn corners
+ /// in the path.
+ ///
+ /// @see GetTrigRadiusForHeight
+ const std::shared_ptr<ShadowVertices> CalculateConvexShadowMesh(
+ const impeller::PathSource& source,
+ const impeller::Matrix& matrix,
+ const Tessellator::Trigs& trigs);
+
+ private:
+ /// Compute the size of the penumbra for a given occluder_height which
+ /// can vary depending on the type of shadow. Here we are only processing
+ /// ambient shadows.
+ static constexpr Scalar GetPenumbraSizeForHeight(Scalar occluder_height) {
+ return occluder_height;
+ }
+
+ /// Compute the size of the umbra for a given occluder_height which
+ /// can vary depending on the type of shadow. Here we are only processing
+ /// ambient shadows.
+ static constexpr Scalar GetUmbraSizeForHeight(Scalar occluder_height) {
+ return occluder_height;
+ }
+
+ /// The minimum distance (squared) between points on the mesh before we
+ /// eliminate them as redundant.
+ static constexpr Scalar kMinSubPixelDistanceSquared =
+ UmbraPinAccumulator::kSubPixelScale * UmbraPinAccumulator::kSubPixelScale;
+
+ /// The occluder_height for which we are processing this shadow.
+ const Scalar occluder_height_;
+
+ /// The maximum gaussian of the umbra part of the shadow, usually 1.0f
+ /// but can be reduced if the umbra size was clipped.
+ Scalar umbra_gaussian_ = 1.0f;
+
+ /// The vertex mesh result that represents the shadow, to be rendered
+ /// using a modified indexed variant of DrawVertices that also adjusts
+ /// the alpha of the colors on a per-pixel basis by mapping their linear
+ /// gaussian coefficients into the associated gaussian integral values.
+
+ /// vertices_ stores all of the points in the mesh.
+ std::vector<Point> vertices_;
+
+ /// indices_ stores the indexes of the triangles in the mesh, in a
+ /// raw triangle format (i.e. not a triangle fan or strip).
+ std::vector<uint16_t> indices_;
+
+ /// gaussians_ stores the gaussian values associated with each vertex
+ /// in the mesh, the values being 1:1 with the equivalent vertex in
+ /// the vertices_ vedtor.
+ std::vector<Scalar> gaussians_;
+
+ /// Run through the pins and determine the closest pin to the centroid
+ /// and, in particular, adjust the umbra_gaussian value if the closest pin
+ /// is less than the required umbra distance.
+ void ComputePinDirectionsAndMinDistanceToCentroid(std::vector<UmbraPin>& pins,
+ const Point& centroid,
+ Scalar direction);
+
+ /// The head and count for the list of UmbraPins that contribute to the
+ /// umbra vertex ring.
+ ///
+ /// The forward and backward pointers for the linked list are stored
+ /// in the UmbraPin struct as p_next, p_prev.
+ struct UmbraPinLinkedList {
+ UmbraPin* p_head_pin = nullptr;
+ size_t pin_count = 0u;
+
+ bool IsNull() { return p_head_pin == nullptr; }
+ };
+
+ /// Run through the pins and determine if they intersect each other
+ /// internally, whether they are completely obscured by other pins,
+ /// their new relative lengths if they defer to another pin at some
+ /// depth, and which remaining pins are part of the umbra polygon,
+ /// and then return the pointer to the first pin in the "umbra polygon".
+ UmbraPinLinkedList ResolveUmbraIntersections(std::vector<UmbraPin>& pins,
+ Scalar direction);
+
+ /// Structure to store the result of computing the intersection between
+ /// 2 pins, pin0 and pin1, containing the point of intersection and the
+ /// relative fractions at which the 2 pins intersected (expressed as a
+ /// ratio of 0 to 1 where 0 represents intersecting at the path outline
+ /// and 1 represents intersecting at the tip of the pin where the umbra
+ /// is darkest.
+ struct PinIntersection {
+ // The Point of the intersection between the pins.
+ Point intersection;
+ // The fraction along pin0 of the intersection.
+ Scalar fraction0;
+ // The fraction along pin1 of the intersection
+ Scalar fraction1;
+ };
+
+ /// Return the intersection between the 2 pins pin0 and pin1 if there
+ /// is an intersection, otherwise a nullopt to indicate that there is
+ /// no intersection.
+ static std::optional<PinIntersection> ComputeIntersection(UmbraPin& pin0,
+ UmbraPin& pin1);
+
+ /// Constants used to resolve pin intersections, adopted from the Skia
+ /// version of the algorithm.
+ static constexpr Scalar kCrossTolerance = 1.0f / 2048.0f;
+ static constexpr Scalar kIntersectionTolerance = 1.0e-6f;
+
+ /// Compute the squared length of a vector or a special out of bounds
+ /// value if the vector becomes infinite.
+ static constexpr Scalar FiniteVectorLengthSquared(Vector2 v) {
+ return !v.IsFinite() ? -1.0f : v.Dot(v);
+ }
+
+ /// Determine if the numerator and denominator are outside of the
+ /// interval that makes sense for an umbra intersection.
+ ///
+ /// Note calculation borrowed from Skia's SkPathUtils.
+ static constexpr inline bool OutsideInterval(Scalar numer,
+ Scalar denom,
+ bool denom_positive) {
+ return (denom_positive && (numer < 0 || numer > denom)) ||
+ (!denom_positive && (numer > 0 || numer < denom));
+ }
+
+ /// Remove the pin at p_pin from the linked list of pins when the caller
+ /// determines that it should not contribute to the final umbra polygon.
+ /// The pointer to the head pin at *p_head will also be adjusted if we've
+ /// eliminated the head pin itself and it will be additionally set to
+ /// nullptr if that was the last pin in the list.
+ ///
+ /// @param p_pin The pin to be eliminated from the list.
+ /// @param p_head The pointer to the head of the list which might also
+ /// need adjustment depending on which pin is removed.
+ static void RemovePin(UmbraPin* p_pin, UmbraPin** p_head);
+
+ /// A helper method for resolving pin conflicts, adopted directly from the
+ /// associated Skia algorithm.
+ ///
+ /// Note calculation borrowed from Skia's SkPathUtils.
+ static int ComputeSide(const Point& p0, const Vector2& v, const Point& p);
+
+ /// Run through the path calculating the outset vertices for the penumbra
+ /// and connecting them to the inset vertices of the umbra and then to
+ /// the centroid in a system of triangles with the appropriate alpha values
+ /// representing the intensity of the (non-gamma-adjusted) shadow at those
+ /// points. The resulting mesh should consist of 2 rings of triangles, an
+ /// inner ring connecting the centroid to the umbra polygon, and another
+ /// outer ring connecting vertices in the umbra polygon to vertices on the
+ /// outer edge of the penumbra.
+ ///
+ /// @param pins The list of pins, one for each edge of the polygon.
+ /// @param centroid The centroid ("center of mass") of the polygon.
+ /// @param list The linked list of the subset of pins that have
+ /// umbra vertices which appear in the umbra polygon.
+ /// @param trigs The vector of sin and cos for subdivided arcs that
+ /// can round the penumbra corner at each polygon corner.
+ /// @param direction The overall direction of the path as determined by
+ /// the consistent cross products of each edge turn.
+ void ComputeMesh(std::vector<UmbraPin>& pins,
+ const Point& centroid,
+ UmbraPinLinkedList& list,
+ const impeller::Tessellator::Trigs& trigs,
+ Scalar direction);
+
+ /// After the umbra_vertices of the pins are accumulated and linked into a
+ /// ring using their p_prev/p_next pointers, compute the best surviving umbra
+ /// vertex for each pin and set its location and index into the UmbraPin.
+ ///
+ /// @param pins The list of pins, one for each edge of the polygon.
+ /// @param list The linked list of the subset of pins that have
+ /// umbra vertices which appear in the umbra polygon.
+ /// @param centroid The centroid ("center of mass") of the polygon.
+ void PopulateUmbraVertices(std::vector<UmbraPin>& pins,
+ UmbraPinLinkedList& list,
+ const Point centroid);
+
+ /// Appends a fan of penumbra vertices centered on the path vertex of the
+ /// |p_curr_pin| starting from the absolute point |fan_start| and ending
+ /// at the absolute point |fan_end|, both of which should be equi-distant
+ /// from the path vertex. The index of the vertex at |fan_start| should
+ /// already be in the vector of vertices at an index given by |start_index|.
+ ///
+ /// @param p_curr_pin The pin at the corner around which the penumbra is
+ /// rotating.
+ /// @param fan_start The point on the penumbra where the fan starts.
+ /// @param fan_start The point on the penumbra where the fan ends.
+ /// @param start_index The index in the vector of vertices where the
+ /// fan_start vertex has already been inserted.
+ /// @param trigs The vector of sin and cos for subdivided arcs that
+ /// can round the penumbra corner at each polygon corner.
+ /// @param direction The overall direction of the path as determined by
+ /// the consistent cross products of each edge turn.
+ uint16_t AppendFan(const UmbraPin* p_curr_pin,
+ const Point& fan_start,
+ const Point& fan_end,
+ uint16_t start_index,
+ const impeller::Tessellator::Trigs& trigs,
+ Scalar direction);
+
+ /// Append a vertex and its associated gaussian coefficient to the lists
+ /// of vertices and guassians and return their (shared) index.
+ uint16_t AppendVertex(const Point& vertex, Scalar gaussian);
+
+ /// Append 3 indices to the indices vector to form a new triangle in the mesh.
+ void AddTriangle(uint16_t v0, uint16_t v1, uint16_t v2);
+};
+
+PolygonInfo::PolygonInfo(Scalar occluder_height)
+ : occluder_height_(occluder_height) {}
+
+const std::shared_ptr<ShadowVertices> PolygonInfo::CalculateConvexShadowMesh(
+ const impeller::PathSource& source,
+ const Matrix& matrix,
+ const Tessellator::Trigs& trigs) {
+ if (!matrix.IsInvertible()) {
+ return ShadowVertices::kEmpty;
+ }
+
+ Scalar scale = matrix.GetMaxBasisLengthXY();
+
+ UmbraPinAccumulator pin_accumulator;
+
+ auto [point_count, contour_count] =
+ impeller::PathTessellator::CountFillStorage(source, scale);
+ pin_accumulator.Reserve(point_count);
+
+ PathTessellator::PathToTransformedFilledVertices(source, pin_accumulator,
+ matrix);
+
+ switch (pin_accumulator.GetStatus()) {
+ case UmbraPinAccumulator::PathStatus::kEmpty:
+ return ShadowVertices::kEmpty;
+ case UmbraPinAccumulator::PathStatus::kNonConvex:
+ case UmbraPinAccumulator::PathStatus::kMultipleContours:
+ return nullptr;
+ case UmbraPinAccumulator::PathStatus::kConvex:
+ break;
+ }
+
+ std::vector<UmbraPin>& pins = pin_accumulator.GetPins();
+ const Point& centroid = pin_accumulator.GetCentroid();
+ Scalar direction = pin_accumulator.GetDirection();
+
+ ComputePinDirectionsAndMinDistanceToCentroid(pins, centroid, direction);
+
+ UmbraPinLinkedList list = ResolveUmbraIntersections(pins, direction);
+ if (list.IsNull()) {
+ // Ideally the Resolve algorithm will always be able to create an
+ // inner loop of umbra vertices, but it is not perfect.
+ //
+ // The Skia algorithm from which this was taken tries to fake an
+ // umbra polygon that is 95% from the path polygon to the centroid,
+ // but that result does not resemble a proper shadow. If we run into
+ // this case a lot we should either beef up the ResolveIntersections
+ // algorithm or find a better approximation than "95% to the centroid".
+ return nullptr;
+ }
+
+ ComputeMesh(pins, centroid, list, trigs, direction);
+
+ Matrix inverted_matrix = matrix.Invert();
+ for (Point& vertex : vertices_) {
+ vertex = inverted_matrix * vertex;
+ }
+ return ShadowVertices::Make(std::move(vertices_), std::move(indices_),
+ std::move(gaussians_));
+}
+
+// Enter a new point for the polygon approximation of the shape. Points are
+// normalized to a device subpixel grid based on |kSubPixelCount|, duplicates
+// at that sub-pixel grid are ignored, collinear points are reduced to just
+// the endpoints, and the centroid is updated from the remaining non-duplicate
+// grid points.
+void UmbraPinAccumulator::Write(Point point) {
+ // This type of algorithm will never be able to handle multiple contours.
+ if (first_contour_ended_) {
+ has_multiple_contours_ = true;
+ return;
+ }
+ FML_DCHECK(!has_multiple_contours_);
+
+ point = ToDeviceGrid(point);
+
+ if (!pins_.empty()) {
+ // If this isn't the first point then we need to perform de-duplication
+ // and possibly convexity checking and centroid updates.
+ Point prev = pins_.back().path_vertex;
+
+ // Adjusted points are rounded so == testing is OK here even for floating
+ // point coordinates.
+ if (point == prev) {
+ // Ignore this point as a duplicate
+ return;
+ }
+
+ if (pins_.size() >= 2u) {
+ // A quick collinear check to avoid extra processing later.
+ Point prev_prev = pins_.end()[-2].path_vertex;
+ Vector2 v0 = prev - prev_prev;
+ Vector2 v1 = point - prev_prev;
+ Scalar cross = v0.Cross(v1);
+ if (cross == 0) {
+ // This point is on the same line as the line between the last
+ // 2 points, so skip the intermediate point. Points that are
+ // collinear only contribute to the edge of the shape the vector
+ // from the first to the last of them.
+ pins_.pop_back();
+ if (point == prev_prev) {
+ // Not only do we eliminate the previous point as collinear, but
+ // we also eliminate this point as a duplicate.
+ // This point would tend to be eliminated anyway because it would
+ // automatically be collinear with whatever the next point would
+ // be, but we just avoid inserting it anyway to reduce processing.
+ return;
+ }
+ }
+ }
+ }
+
+ pins_.emplace_back(point);
+}
+
+// Called at the end of every contour of which we hope there is only one.
+// If we detect more than one contour then the shadow tessellation becomes
+// invalid.
+//
+// Each contour will have exactly one point at the beginning and end which
+// are duplicates. The extra repeat of the first point actually helped the
+// centroid accumulation do its math for ever segment in the path, but
+// going forward we don't need the extra pin in the shape so we verify that
+// it is a duplicate and then we delete it.
+void UmbraPinAccumulator::EndContour() {
+ // This type of algorithm will never be able to handle multiple contours.
+ if (first_contour_ended_) {
+ has_multiple_contours_ = true;
+ return;
+ }
+ FML_DCHECK(!has_multiple_contours_);
+
+ // PathTessellator always ensures the path is closed back to the origin
+ // by an extra call to Write(Point).
+ FML_DCHECK(pins_.front().path_vertex == pins_.back().path_vertex);
+ pins_.pop_back();
+ first_contour_ended_ = true;
+}
+
+// Adjust the device point to its nearest sub-pixel grid location.
+Point UmbraPinAccumulator::ToDeviceGrid(Point point) {
+ return (point * kSubPixelCount).Round() * kSubPixelScale;
+}
+
+// This method assumes that the pins have been accumulated by the PathVertex
+// methods which ensure that no adjacent points are identical or collinear.
+// It returns a PathResults that contains all of the relevant information
+// depending on the geometric state of the path itself (ignoring whether
+// the rest of the shadow processing will succeed).
+//
+// It performs 4 functions:
+// - Normalizes empty paths (either too few vertices, or no turning directin)
+// to an empty pins vector.
+// - Accumulates and sets the centroid of the path
+// - Accumulates and sets the overall direction of the path as determined by
+// the sign of the cross products which must all agree.
+// - Checks for convexity, including:
+// - The direction vector determined above.
+// - The turning direction of every triplet of points.
+// - The signs of the area accumulated using cross products.
+// - The number of times that the path edges change sign in X or Y.
+UmbraPinAccumulator::PathResults UmbraPinAccumulator::FinalizePath() {
+ FML_DCHECK(!results_.has_value());
+
+ if (has_multiple_contours_) {
+ return {.status = PathStatus::kMultipleContours};
+ }
+
+ if (pins_.size() < 3u) {
+ return {.status = PathStatus::kEmpty};
+ }
+
+ DirectionDetector x_direction_detector;
+ DirectionDetector y_direction_detector;
+
+ Point relative_centroid;
+ Scalar path_direction = 0.0f;
+ Scalar path_area = 0.0f;
+
+ Point prev = pins_.back().path_vertex;
+ Point prev_prev = pins_.end()[-2].path_vertex;
+ Point first = pins_.front().path_vertex;
+ for (UmbraPin& pin : pins_) {
+ Point new_point = pin.path_vertex;
+
+ // Check for going around more than once in the same direction.
+ {
+ Vector2 delta = new_point - prev;
+ x_direction_detector.AccumulateDirection(delta.x);
+ y_direction_detector.AccumulateDirection(delta.y);
+ if (x_direction_detector.IsConcave() ||
+ y_direction_detector.IsConcave()) {
+ return {.status = PathStatus::kNonConvex};
+ }
+ }
+
+ // Check if the path is locally convex over the most recent 3 vertices.
+ if (path_direction != 0.0f) {
+ Vector2 v0 = prev - prev_prev;
+ Vector2 v1 = new_point - prev_prev;
+ Scalar cross = v0.Cross(v1);
+ // We should have eliminated adjacent collinear points in the first pass.
+ FML_DCHECK(cross != 0.0f);
+ if (cross * path_direction < 0.0f) {
+ return {.status = PathStatus::kNonConvex};
+ }
+ }
+
+ // Check if the path is globally convex with respect to the first vertex.
+ {
+ Vector2 v0 = prev - first;
+ Vector2 v1 = new_point - first;
+ Scalar quad_area = v0.Cross(v1);
+ if (quad_area != 0) {
+ // convexity check for whole path which can detect if we turn more than
+ // 360 degrees and start going the other way wrt the start point, but
+ // does not detect if any pair of points are concave (checked above).
+ if (path_direction == 0) {
+ path_direction = std::copysign(1.0f, quad_area);
+ } else if (quad_area * path_direction < 0) {
+ return {.status = PathStatus::kNonConvex};
+ }
+
+ relative_centroid += (v0 + v1) * quad_area;
+ path_area += quad_area;
+ }
+ }
+
+ prev_prev = prev;
+ prev = new_point;
+ }
+
+ if (path_direction == 0.0f) {
+ // We never changed direction, indicate emptiness.
+ return {.status = PathStatus::kEmpty};
+ }
+
+ // We are computing the centroid using a weighted average of all of the
+ // centroids of the triangles in a tessellation of the polygon, in this
+ // case a triangle fan tessellation relative to the first point in the
+ // polygon. We could use any point, but since we had to compute the cross
+ // product above relative to the initial point in order to detect if the
+ // path turned more than once, we already have values available relative
+ // to that first point here.
+ //
+ // The centroid of each triangle is the 3-way average of the corners of
+ // that triangle. Since the triangles are all relative to the first point,
+ // one of those corners is (0, 0) in this relative triangle and so we can
+ // simply add up the x,y of the two relative points and divide by 3.0.
+ // Since all values in the sum are divided by 3.0, we can save that
+ // constant division until the end when we finalize the average computation.
+ //
+ // We also weight these centroids by the area of the triangle so that we
+ // adjust for the parts of the polygon that are represented more densely
+ // and the parts that span a larger part of its circumference. A simple
+ // average would bias the centroid towards parts of the polygon where the
+ // points are denser. If we are rendering a polygonal representation of
+ // a round rect with only one round corner, all of the many approximating
+ // segments of the flattened round corner would overwhelm the handful of
+ // other simple segments for the flat sides. A weighted average places the
+ // centroid back at the "center of mass" of the polygon.
+ //
+ // Luckily, the same cross product used above that helps us determine the
+ // turning and convexity of the polygon also provides us with the area of
+ // the parallelogram projected from the 3 points in the triangle. That
+ // area is exactly double the area of the triangle itself. We could divide
+ // by 2 here, but since we are also accumulating these cross product values
+ // for the final weighted division, the factors of 2 all cancel out.
+ //
+ // path_area is (2 * triangle area).
+ // relative_centroid is accumulating sum(3 * triangle centroid * quad area).
+ // path_area_ is accumulating sum(quad area).
+ //
+ // The final combined average weight factor will be (3 * sum(quad area)).
+ relative_centroid /= 3.0f * path_area;
+
+ // The centroid accumulation was relative to the first point in the
+ // polygon so we make it absolute here.
+ return {
+ .status = PathStatus::kConvex,
+ .centroid = pins_[0].path_vertex + relative_centroid,
+ .path_direction = path_direction,
+ };
+}
+
+void PolygonInfo::ComputePinDirectionsAndMinDistanceToCentroid(
+ std::vector<UmbraPin>& pins,
+ const Point& centroid,
+ Scalar direction) {
+ Scalar desired_umbra_size = GetUmbraSizeForHeight(occluder_height_);
+ Scalar min_umbra_squared = desired_umbra_size * desired_umbra_size;
+ FML_DCHECK(direction == 1.0f || direction == -1.0f);
+
+ // For simplicity of iteration, we start with the last vertex as the
+ // "previous" pin and then iterate once over the vector of pins,
+ // performing these calculations on the path segment from the previous
+ // pin to the current pin. In the end, all pins and therefore all path
+ // segments are processed once even if we start with the last pin.
+
+ // First pass, compute the smallest distance to the centroid.
+ UmbraPin* p_prev_pin = &pins.back();
+ for (UmbraPin& pin : pins) {
+ UmbraPin* p_curr_pin = &pin;
+
+ // Accumulate (min) the distance from the centroid to "this" segment.
+ Scalar distance_squared = centroid.GetDistanceToSegmentSquared(
+ p_prev_pin->path_vertex, p_curr_pin->path_vertex);
+ min_umbra_squared = std::min(min_umbra_squared, distance_squared);
+
+ p_prev_pin = p_curr_pin;
+ }
+
+ static constexpr auto kTolerance = 1.0e-2f;
+ Scalar umbra_size = std::sqrt(min_umbra_squared);
+ if (umbra_size < desired_umbra_size + kTolerance) {
+ // if the umbra would collapse, we back off a bit on the inner blur and
+ // adjust the alpha
+ auto newInset = umbra_size - kTolerance;
+ auto ratio = 0.5f * (newInset / desired_umbra_size + 1);
+ FML_DCHECK(std::isfinite(ratio));
+
+ umbra_gaussian_ = ratio;
+ umbra_size = newInset;
+ } else {
+ FML_DCHECK(umbra_gaussian_ == 1.0f);
+ }
+
+ // Second pass, fill out the pin data with the final umbra size.
+ //
+ // We also link all of the pins into a circular linked list so they can be
+ // quickly eliminated in the method that resolves intersections of the pins.
+ Scalar penumbra_scale = -GetPenumbraSizeForHeight(occluder_height_);
+ p_prev_pin = &pins.back();
+ for (UmbraPin& pin : pins) {
+ UmbraPin* p_curr_pin = &pin;
+ p_curr_pin->p_prev = p_prev_pin;
+ p_prev_pin->p_next = p_curr_pin;
+
+ // We compute the vector along the path segment from the previous
+ // path vertex to this one as well as the unit direction vector
+ // that points from that pin towards the center of the shape,
+ // perpendicular to that segment.
+ p_prev_pin->path_delta = p_curr_pin->path_vertex - p_prev_pin->path_vertex;
+ Vector2 pin_direction = p_prev_pin
+ ->path_delta //
+ .Normalize()
+ .PerpendicularRight() *
+ direction;
+
+ p_prev_pin->penumbra_delta = pin_direction * penumbra_scale;
+ p_prev_pin->umbra_vertex = //
+ p_prev_pin->pin_tip =
+ p_prev_pin->path_vertex + pin_direction * umbra_size;
+
+ p_prev_pin = p_curr_pin;
+ }
+}
+
+// Compute the intersection 'p' between the two pins pin 0 and pin 1, if any.
+// The intersection structure will contain the fractional distances along the
+// pins of the intersection and the intersection point itself if there is an
+// intersection.
+//
+// The intersection structure will be reset to empty otherwise.
+//
+// This method was converted nearly verbatim from the Skia source files
+// SkShadowTessellator.cpp and SkPolyUtils.cpp, except for variable
+// naming and differences in the methods on Point and Vertex2.
+std::optional<PolygonInfo::PinIntersection> PolygonInfo::ComputeIntersection(
+ UmbraPin& pin0,
+ UmbraPin& pin1) {
+ Vector2 v0 = pin0.path_delta;
+ Vector2 v1 = pin1.path_delta;
+ Vector2 tip_delta = pin1.pin_tip - pin0.pin_tip;
+ Vector2 w = tip_delta;
+ Scalar denom = pin0.path_delta.Cross(pin1.path_delta);
+ bool denom_positive = (denom > 0);
+ Scalar numerator0, numerator1;
+
+ if (ScalarNearlyZero(denom, kCrossTolerance)) {
+ // This code also exists in the Skia version of this method, but it is
+ // not clear that we can ever enter here. In particular, since points
+ // were normalized to a grid (1/16th of a pixel), de-duplicated, and
+ // collinear points eliminated, denom can never be 0. And since the
+ // denom value was computed from a cross product of non-normalized
+ // delta vectors, its magnitude must exceed 1/256 which is far greater
+ // than the tolerance value.
+ //
+ // Note that in the Skia code, this method lived in a general polygon
+ // module that was unaware that it was being fed de-duplicated vertices
+ // from the Shadow module, so this code might be possible to trigger
+ // for "unfiltered" polygons, but not the normalized polygons that our
+ // (and Skia's) shadow code uses.
+ //
+ // Though entering here seems unlikely, we include the code until we can
+ // perform more due diligence in vetting that this is truly dead code.
+
+ // segments are parallel, but not collinear
+ if (!ScalarNearlyZero(tip_delta.Cross(pin0.path_delta), kCrossTolerance) ||
+ !ScalarNearlyZero(tip_delta.Cross(pin1.path_delta), kCrossTolerance)) {
+ return std::nullopt;
+ }
+
+ // Check for zero-length segments
+ Scalar v0_length_squared = FiniteVectorLengthSquared(v0);
+ if (v0_length_squared <= 0.0f) {
+ // Both are zero-length
+ Scalar v1_length_squared = FiniteVectorLengthSquared(v1);
+ if (v1_length_squared <= 0.0f) {
+ // Check if they're the same point
+ if (w.IsFinite() && !w.IsZero()) {
+ return {{
+ .intersection = pin0.pin_tip,
+ .fraction0 = 0.0f,
+ .fraction1 = 0.0f,
+ }};
+ } else {
+ // Intersection is indeterminate
+ return std::nullopt;
+ }
+ }
+ // Otherwise project segment0's origin onto segment1
+ numerator1 = v1.Dot(-w);
+ denom = v1_length_squared;
+ if (OutsideInterval(numerator1, denom, true)) {
+ return std::nullopt;
+ }
+ numerator0 = 0;
+ } else {
+ // Project segment1's endpoints onto segment0
+ numerator0 = v0.Dot(w);
+ denom = v0_length_squared;
+ numerator1 = 0;
+ if (OutsideInterval(numerator0, denom, true)) {
+ // The first endpoint doesn't lie on segment0
+ // If segment1 is degenerate, then there's no collision
+ Scalar v1_length_squared = FiniteVectorLengthSquared(v1);
+ if (v1_length_squared <= 0.0f) {
+ return std::nullopt;
+ }
+
+ // Otherwise try the other one
+ Scalar old_numerator0 = numerator0;
+ numerator0 = v0.Dot(w + v1);
+ numerator1 = denom;
+ if (OutsideInterval(numerator0, denom, true)) {
+ // it's possible that segment1's interval surrounds segment0
+ // this is false if params have the same signs, and in that case
+ // no collision
+ if (numerator0 * old_numerator0 > 0) {
+ return std::nullopt;
+ }
+ // otherwise project segment0's endpoint onto segment1 instead
+ numerator0 = 0;
+ numerator1 = v1.Dot(-w);
+ denom = v1_length_squared;
+ }
+ }
+ }
+ } else {
+ numerator0 = w.Cross(v1);
+ if (OutsideInterval(numerator0, denom, denom_positive)) {
+ return std::nullopt;
+ }
+ numerator1 = w.Cross(v0);
+ if (OutsideInterval(numerator1, denom, denom_positive)) {
+ return std::nullopt;
+ }
+ }
+
+ Scalar fraction0 = numerator0 / denom;
+ Scalar fraction1 = numerator1 / denom;
+
+ return {{
+ .intersection = pin0.pin_tip + v0 * fraction0,
+ .fraction0 = fraction0,
+ .fraction1 = fraction1,
+ }};
+}
+
+void PolygonInfo::RemovePin(UmbraPin* p_pin, UmbraPin** p_head) {
+ UmbraPin* p_next = p_pin->p_next;
+ UmbraPin* p_prev = p_pin->p_prev;
+ p_prev->p_next = p_next;
+ p_next->p_prev = p_prev;
+ if (*p_head == p_pin) {
+ *p_head = (p_next == p_pin) ? nullptr : p_next;
+ }
+}
+
+// Computes the relative direction for point p compared to segment defined
+// by origin p0 and vector v. A positive value means the point is to the
+// left of the segment, negative is to the right, 0 is collinear.
+int PolygonInfo::ComputeSide(const Point& p0,
+ const Vector2& v,
+ const Point& p) {
+ Vector2 w = p - p0;
+ Scalar cross = v.Cross(w);
+ if (!impeller::ScalarNearlyZero(cross, kCrossTolerance)) {
+ return ((cross > 0) ? 1 : -1);
+ }
+
+ return 0;
+}
+
+// This method was converted nearly verbatim from the Skia source files
+// SkShadowTessellator.cpp and SkPolyUtils.cpp, except for variable
+// naming and differences in the methods on Point and Vertex2.
+PolygonInfo::UmbraPinLinkedList PolygonInfo::ResolveUmbraIntersections(
+ std::vector<UmbraPin>& pins,
+ Scalar direction) {
+ UmbraPin* p_head_pin = &pins.front();
+ UmbraPin* p_curr_pin = p_head_pin;
+ UmbraPin* p_prev_pin = p_curr_pin->p_prev;
+ size_t umbra_vertex_count = pins.size();
+
+ // we should check each edge against each other edge at most once
+ size_t allowed_iterations = pins.size() * pins.size() + 1u;
+
+ while (p_head_pin && p_prev_pin != p_curr_pin) {
+ if (--allowed_iterations == 0) {
+ return {};
+ }
+
+ std::optional<PinIntersection> intersection =
+ ComputeIntersection(*p_prev_pin, *p_curr_pin);
+ if (intersection.has_value()) {
+ // If the new intersection is further back on previous inset from the
+ // prior intersection...
+ if (intersection->fraction0 < p_prev_pin->umbra_fraction) {
+ // no point in considering this one again
+ RemovePin(p_prev_pin, &p_head_pin);
+ --umbra_vertex_count;
+ // go back one segment
+ p_prev_pin = p_prev_pin->p_prev;
+ } else if (p_curr_pin->IsFractionInitialized() &&
+ p_curr_pin->umbra_vertex.GetDistanceSquared(
+ intersection->intersection) < kIntersectionTolerance) {
+ // We've already considered this intersection and come to the same
+ // result, we're done.
+ break;
+ } else {
+ // Add intersection.
+ p_curr_pin->umbra_vertex = intersection->intersection;
+ p_curr_pin->umbra_fraction = intersection->fraction1;
+
+ // go to next segment
+ p_prev_pin = p_curr_pin;
+ p_curr_pin = p_curr_pin->p_next;
+ }
+ } else {
+ // if previous pin is to right side of the current pin...
+ int side = direction * ComputeSide(p_curr_pin->pin_tip, //
+ p_curr_pin->path_delta, //
+ p_prev_pin->pin_tip);
+ if (side < 0 &&
+ side == direction * ComputeSide(p_curr_pin->pin_tip, //
+ p_curr_pin->path_delta, //
+ p_prev_pin->pin_tip +
+ p_prev_pin->path_delta)) {
+ // no point in considering this one again
+ RemovePin(p_prev_pin, &p_head_pin);
+ --umbra_vertex_count;
+ // go back one segment
+ p_prev_pin = p_prev_pin->p_prev;
+ } else {
+ // move to next segment
+ RemovePin(p_curr_pin, &p_head_pin);
+ --umbra_vertex_count;
+ p_curr_pin = p_curr_pin->p_next;
+ }
+ }
+ }
+
+ if (!p_head_pin) {
+ return {};
+ }
+
+ // Now remove any duplicates from the umbra polygon. The head pin is
+ // automatically included as the first point of the umbra polygon.
+ p_prev_pin = p_head_pin;
+ p_curr_pin = p_head_pin->p_next;
+ size_t umbra_vertices = 1u;
+ while (p_curr_pin != p_head_pin) {
+ if (p_prev_pin->umbra_vertex.GetDistanceSquared(p_curr_pin->umbra_vertex) <
+ kMinSubPixelDistanceSquared) {
+ RemovePin(p_curr_pin, &p_head_pin);
+ p_curr_pin = p_curr_pin->p_next;
+ } else {
+ umbra_vertices++;
+ p_prev_pin = p_curr_pin;
+ p_curr_pin = p_curr_pin->p_next;
+ }
+ FML_DCHECK(p_curr_pin == p_prev_pin->p_next);
+ FML_DCHECK(p_prev_pin == p_curr_pin->p_prev);
+ }
+
+ if (umbra_vertices < 3u) {
+ return {};
+ }
+
+ return {p_head_pin, umbra_vertices};
+}
+
+// The mesh computed connects all of the points in two rings. The outermost
+// ring represents the point where the shadow disappears and those points
+// are associated with an alpha of 0. The umbra polygon represents the ring
+// where the shadow is its darkest, usually fully "opaque" (potentially
+// modulated by a non-opaque shadow color, but opaque with respect to the
+// shadow's varying intensity). The umbra polygon may not be fully "opaque"
+// with respect to the shadow cast by the shape if the shadows radius is
+// larger than the cross-section of the shape. If the umbra polygon is pulled
+// back from extending the shadow distance inward due to this phenomenon,
+// then the umbra_gaussian will be computed to be less than fully opaque.
+//
+// The mesh will connect the centroid to the umbra (inner) polygon at a
+// constant level as computed in umbra_gaussian, and then the umbra polygon
+// is connected to the nearest points on the penumbra (outer) polygon which
+// is seeded with points that are fully transparent (umbra level 0).
+//
+// This creates 2 rings of triangles that are interspersed in the vertices_
+// and connected into triangles using indices_ both to reuse the vertices
+// as best we can and also because we don't generate the vertices in any
+// kind of useful fan or strip format. The points are reused as such:
+//
+// - The centroid vertex will be used once for each pair of umbra vertices
+// to make triangles for the inner ring.
+// - Each umbra vertex will be used in both the inner and the outer rings.
+// In particular, in 2 of the inner ring triangles and in an arbitrary
+// number of the outer ring vertices (each outer ring vertex is connected
+// to the neariest inner ring vertex so the mapping is not predictable).
+// - Each outer ring vertex is used in at least 2 outer ring triangles, the
+// one that links to the vertex before it and the one that links to the
+// vertex following it, plus we insert extra vertices on the outer ring
+// to turn the corners beteween the projected segments.
+void PolygonInfo::ComputeMesh(std::vector<UmbraPin>& pins,
+ const Point& centroid,
+ UmbraPinLinkedList& list,
+ const impeller::Tessellator::Trigs& trigs,
+ Scalar direction) {
+ // Centroid and umbra polygon...
+ size_t vertex_count = list.pin_count + 1u;
+ size_t triangle_count = list.pin_count;
+
+ // Penumbra corners - likely many more fan vertices than estimated...
+ size_t penumbra_count = pins.size() * 2; // 2 perp at each vertex.
+ penumbra_count += trigs.size() * 4; // total 360 degrees of fans.
+ vertex_count += penumbra_count;
+ triangle_count += penumbra_count;
+
+ vertices_.reserve(vertex_count);
+ gaussians_.reserve(vertex_count);
+ indices_.reserve(triangle_count * 3);
+
+ // First we populate the umbra_vertex and umbra_index of each pin with its
+ // nearest point on the umbra polygon (the linked list computed earlier).
+ //
+ // This step simplifies the following operations because we will always
+ // know which umbra vertex each pin object is associated with and whether
+ // we need to bridge between them as we progress through the pins, without
+ // having to search through the linked list every time.
+ //
+ // This method will also fill in the inner part of the mesh that connects
+ // the centroid to every vertex in the umbra polygon with triangles that
+ // are all at the maximum umbra gaussian coefficient.
+ PopulateUmbraVertices(pins, list, centroid);
+
+ // We now run through the list of all pins and append points and triangles
+ // to our internal vectors to cover the part of the mesh that extends
+ // out from the umbra polygon to the outer penumbra points.
+ //
+ // Each pin assumes that the previous pin contributed some points to the
+ // penumbra polygon that ended with the point that is perpendicular to
+ // the side between that previous path vertex and its own path vertex.
+ // This pin will then contribute any number of the following points to
+ // the penumbra polygon:
+ //
+ // - If this pin uses a different umbra vertex than the previous pin
+ // (common for simple large polygons that have no clipping of their
+ // inner umbra points) then it inserts a bridging quad that connects
+ // from the ending segment of the previous pin to the starting segment
+ // of this pin. If both are based on the same umbra vertex then the
+ // end of the previous pin is identical to the start of this one.
+ // - Possibly a fan of extra vertices to round the corner from the
+ // last segment added, which is perpendicular to the previous path
+ // segment, to the final segmet of this pin, which will be perpendicular
+ // to the following path segment.
+ // - The last penumbra point added will be the penumbra point that is
+ // perpendicular to the following segment, which prepares for the
+ // initial conditions that the next pin will expect.
+ const UmbraPin* p_prev_pin = &pins.back();
+
+ // This point may be duplicated at the end of the path. We can try to
+ // avoid adding it twice with some bookkeeping, but it is simpler to
+ // just add it here for the pre-conditions of the start of the first
+ // pin and allow the duplication to happen naturally as we process the
+ // final pin later. One extra point should not be very noticeable in
+ // the long list of mesh vertices.
+ Point last_penumbra_point =
+ p_prev_pin->path_vertex + p_prev_pin->penumbra_delta;
+ uint16_t last_penumbra_index = AppendVertex(last_penumbra_point, 0.0f);
+
+ for (const UmbraPin& pin : pins) {
+ const UmbraPin* p_curr_pin = &pin;
+
+ // Preconditions:
+ // - last_penumbra_point was the last outer vertex added by the
+ // previous pin
+ // - last_penumbra_index is its index in the vertices to be used
+ // for creating indexed triangles.
+
+ if (p_prev_pin->umbra_index != p_curr_pin->umbra_index) {
+ // We've moved on to a new umbra index to anchor our penumbra triangles.
+ // We need to bridge the gap so that we are now building a new fan from
+ // a point that has the same relative angle from the current pin's
+ // path vertex as the previous penumbra point had from the previous
+ // pin's path vertex.
+ //
+ // Our previous penumbra fan vector would have gone from the previous
+ // pin's umbra point to the previous pen's final penumbra point:
+ // - prev->umbra_vertex
+ // => prev->path_vertex + prev->penumbra_delta
+ // We will connect to a parallel vector that extends from the new
+ // (current pin's) umbra index in the same direction:
+ // - curr->umbra_vertex
+ // => curr->path_vertex + prev->penumbra_delta
+
+ // First we pivot about the old penumbra point to bridge from the old
+ // umbra vertex to our new umbra point.
+ AddTriangle(last_penumbra_index, //
+ p_prev_pin->umbra_index, p_curr_pin->umbra_index);
+ }
+
+ // Then we bridge from the old penumbra point to the new parallel
+ // penumbra point, pivoting around the new umbra index.
+ Point new_penumbra_point =
+ p_curr_pin->path_vertex + p_prev_pin->penumbra_delta;
+ uint16_t new_penumbra_index = AppendVertex(new_penumbra_point, 0.0f);
+
+ if (last_penumbra_index != new_penumbra_index) {
+ AddTriangle(p_curr_pin->umbra_index, last_penumbra_index,
+ new_penumbra_index);
+ }
+
+ last_penumbra_point = new_penumbra_point;
+ last_penumbra_index = new_penumbra_index;
+
+ // Now draw a fan from the current pin's umbra vertex to all of the
+ // penumbra points associated with this pin's path vertex, ending at
+ // our new final penumbra point associated with this pin.
+ new_penumbra_point = p_curr_pin->path_vertex + p_curr_pin->penumbra_delta;
+ new_penumbra_index =
+ AppendFan(p_curr_pin, last_penumbra_point, new_penumbra_point,
+ last_penumbra_index, trigs, direction);
+
+ last_penumbra_point = new_penumbra_point;
+ last_penumbra_index = new_penumbra_index;
+ p_prev_pin = p_curr_pin;
+ }
+}
+
+// Visit each pin and find the nearest umbra_vertex from the linked list of
+// surviving umbra pins so we don't have to constantly find this as we stitch
+// together the mesh.
+void PolygonInfo::PopulateUmbraVertices(std::vector<UmbraPin>& pins,
+ UmbraPinLinkedList& list,
+ const Point centroid) {
+ // We should be having the first crack at the vertex list, filling it with
+ // the centroid, the umbra vertices, and the mesh connecting those into the
+ // central core of the shadow.
+ FML_DCHECK(list.p_head_pin != nullptr);
+ FML_DCHECK(vertices_.empty());
+ FML_DCHECK(gaussians_.empty());
+ FML_DCHECK(indices_.empty());
+
+ // Always start with the centroid.
+ uint16_t last_umbra_index = AppendVertex(centroid, umbra_gaussian_);
+ FML_DCHECK(last_umbra_index == 0u);
+
+ // curr_umbra_pin is the most recently matched umbra vertex pin.
+ // next_umbra_pin is the next umbra vertex pin to consider.
+ // These pointers will always point to one of the pins that is on the
+ // linked list of surviving umbra pins, possibly jumping over many
+ // other umbra pins that were eliminated when we inset the polygon.
+ UmbraPin* p_next_umbra_pin = list.p_head_pin;
+ UmbraPin* p_curr_umbra_pin = p_next_umbra_pin->p_prev;
+ for (UmbraPin& pin : pins) {
+ if (p_next_umbra_pin == &pin ||
+ (pin.path_vertex.GetDistanceSquared(p_curr_umbra_pin->umbra_vertex) >
+ pin.path_vertex.GetDistanceSquared(p_next_umbra_pin->umbra_vertex))) {
+ // We always bump to the next vertex when it was generated from this
+ // pin, and also when it is closer to this path_vertex than the last
+ // matched pin (curr).
+ p_curr_umbra_pin = p_next_umbra_pin;
+ p_next_umbra_pin = p_next_umbra_pin->p_next;
+
+ // New umbra vertex - append it and remember its index.
+ uint16_t new_umbra_index =
+ AppendVertex(p_curr_umbra_pin->umbra_vertex, umbra_gaussian_);
+ p_curr_umbra_pin->umbra_index = new_umbra_index;
+ if (last_umbra_index != 0u) {
+ AddTriangle(0u, last_umbra_index, new_umbra_index);
+ }
+ last_umbra_index = new_umbra_index;
+ }
+ if (p_curr_umbra_pin != &pin) {
+ pin.umbra_vertex = p_curr_umbra_pin->umbra_vertex;
+ pin.umbra_index = last_umbra_index;
+ }
+ FML_DCHECK(pin.umbra_index != 0u);
+ }
+ if (last_umbra_index != pins.front().umbra_index) {
+ AddTriangle(0u, last_umbra_index, pins.front().umbra_index);
+ }
+}
+
+// Appends a fan based on center from the relative point in start_delta to
+// the relative point in end_delta, potentially adding additional relative
+// vectors if the turning rate is faster than the trig values in trigs_.
+uint16_t PolygonInfo::AppendFan(const UmbraPin* p_curr_pin,
+ const Vector2& start,
+ const Vector2& end,
+ uint16_t start_index,
+ const impeller::Tessellator::Trigs& trigs,
+ Scalar direction) {
+ Point center = p_curr_pin->path_vertex;
+ uint16_t center_index = p_curr_pin->umbra_index;
+ uint16_t prev_index = start_index;
+
+ Vector2 start_delta = start - center;
+ Vector2 end_delta = end - center;
+ size_t trig_count = trigs.size();
+ for (size_t i = 1u; i < trig_count; i++) {
+ Trig trig = trigs[i];
+ Point fan_delta = (direction >= 0 ? trig : -trig) * start_delta;
+ if (fan_delta.Cross(end_delta) * direction <= 0) {
+ break;
+ }
+ uint16_t cur_index = AppendVertex(center + fan_delta, 0.0f);
+ if (prev_index != cur_index) {
+ AddTriangle(center_index, prev_index, cur_index);
+ prev_index = cur_index;
+ }
+ if (i == trig_count - 1) {
+ // This corner was >90 degrees so we start the loop over in case there
+ // are more intermediate angles to emit.
+ //
+ // We set the loop variable to 0u which looks like it might apply a
+ // 0 rotation to the new start_delta, but the for loop is about to
+ // auto-incrment the variable to 1u, which will start at the next
+ // non-0 rotation angle.
+ i = 0u;
+ start_delta = fan_delta;
+ }
+ }
+ uint16_t cur_index = AppendVertex(center + end_delta, 0.0f);
+ if (prev_index != cur_index) {
+ AddTriangle(center_index, prev_index, cur_index);
+ }
+ return cur_index;
+}
+
+// Appends a vertex and gaussian value into the associated std::vectors
+// and returns the index at which the point was inserted.
+uint16_t PolygonInfo::AppendVertex(const Point& vertex, Scalar gaussian) {
+ FML_DCHECK(gaussian >= 0.0f && gaussian <= 1.0f);
+ uint16_t index = vertices_.size();
+ FML_DCHECK(index == gaussians_.size());
+ // TODO(jimgraham): Turn this condition into a failure of the tessellation
+ FML_DCHECK(index <= std::numeric_limits<uint16_t>::max());
+ if (gaussian == gaussians_.back() && vertex == vertices_.back()) {
+ return index - 1;
+ }
+ vertices_.push_back(vertex);
+ gaussians_.push_back(gaussian);
+ return index;
+}
+
+// Appends a triangle of the 3 indices into the indices_ vector.
+void PolygonInfo::AddTriangle(uint16_t v0, uint16_t v1, uint16_t v2) {
+ FML_DCHECK(std::max(std::max(v0, v1), v2) < vertices_.size());
+ indices_.push_back(v0);
+ indices_.push_back(v1);
+ indices_.push_back(v2);
+}
+
+} // namespace
+
+namespace impeller {
+
+const std::shared_ptr<ShadowVertices> ShadowVertices::kEmpty =
+ std::make_shared<ShadowVertices>();
+
+std::optional<Rect> ShadowVertices::GetBounds() const {
+ return Rect::MakePointBounds(vertices_);
+}
+
+ShadowPathGeometry::ShadowPathGeometry(Tessellator& tessellator,
+ const Matrix& matrix,
+ const PathSource& source,
+ Scalar occluder_height)
+ : shadow_vertices_(MakeAmbientShadowVertices(tessellator,
+ source,
+ occluder_height,
+ matrix)) {}
+
+bool ShadowPathGeometry::CanRender() const {
+ return shadow_vertices_ != nullptr;
+}
+
+bool ShadowPathGeometry::IsEmpty() const {
+ return shadow_vertices_ != nullptr && shadow_vertices_->IsEmpty();
+}
+
+const std::shared_ptr<ShadowVertices>& ShadowPathGeometry::GetShadowVertices()
+ const {
+ return shadow_vertices_;
+}
+
+const std::shared_ptr<ShadowVertices> ShadowPathGeometry::TakeShadowVertices() {
+ return std::move(shadow_vertices_);
+}
+
+GeometryResult ShadowVertices::GetPositionBuffer(const ContentContext& renderer,
+ const Entity& entity,
+ RenderPass& pass) const {
+ using VS = ShadowVerticesVertexShader;
+
+ size_t vertex_count = GetVertexCount();
+
+ BufferView vertex_buffer = renderer.GetTransientsDataBuffer().Emplace(
+ vertex_count * sizeof(VS::PerVertexData), alignof(VS::PerVertexData),
+ [&](uint8_t* data) {
+ VS::PerVertexData* vtx_contents =
+ reinterpret_cast<VS::PerVertexData*>(data);
+ for (size_t i = 0u; i < vertex_count; i++) {
+ vtx_contents[i] = {
+ .position = vertices_[i],
+ .gaussian = gaussians_[i],
+ };
+ }
+ });
+
+ size_t index_count = GetIndexCount();
+ const uint16_t* indices_data = GetIndices().data();
+ BufferView index_buffer = {};
+ index_buffer = renderer.GetTransientsIndexesBuffer().Emplace(
+ indices_data, index_count * sizeof(uint16_t), alignof(uint16_t));
+
+ return GeometryResult{
+ .type = PrimitiveType::kTriangle,
+ .vertex_buffer =
+ {
+ .vertex_buffer = vertex_buffer,
+ .index_buffer = index_buffer,
+ .vertex_count = index_count,
+ .index_type = IndexType::k16bit,
+ },
+ .transform = entity.GetShaderTransform(pass),
+ };
+}
+
+std::shared_ptr<ShadowVertices> ShadowPathGeometry::MakeAmbientShadowVertices(
+ Tessellator& tessellator,
+ const PathSource& source,
+ Scalar occluder_height,
+ const Matrix& matrix) {
+ Scalar trig_radius = PolygonInfo::GetTrigRadiusForHeight(occluder_height);
+ Tessellator::Trigs trigs = tessellator.GetTrigsForDeviceRadius(trig_radius);
+
+ PolygonInfo polygon(occluder_height);
+
+ return polygon.CalculateConvexShadowMesh(source, matrix, trigs);
+}
+
+} // namespace impeller
diff --git a/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry.h b/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry.h
new file mode 100644
index 0000000..706cf34
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry.h
@@ -0,0 +1,116 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef FLUTTER_IMPELLER_ENTITY_GEOMETRY_SHADOW_PATH_GEOMETRY_H_
+#define FLUTTER_IMPELLER_ENTITY_GEOMETRY_SHADOW_PATH_GEOMETRY_H_
+
+#include "flutter/impeller/entity/geometry/geometry.h"
+#include "flutter/impeller/geometry/path_source.h"
+#include "flutter/impeller/tessellator/tessellator.h"
+
+namespace impeller {
+
+/// A class to hold a vertex mesh for rendering shadows. The vertices are
+/// each associated with a gaussian coefficent that represents where that
+/// vertex lives in the shadow from a value of 1.0 (at the edge of or fully
+/// in the darkest part of the umbra) to 0.0 at the edge of or fully outside
+/// the penumbra).
+///
+/// The vertices are also associated with a vector of indices that assemble
+/// them into a mesh that covers the full umbra and penumbra of the shape.
+///
+/// The mesh is usually intended to be rendered at device (pixel) resolution.
+class ShadowVertices {
+ public:
+ static const std::shared_ptr<ShadowVertices> kEmpty;
+
+ static std::shared_ptr<ShadowVertices> Make(std::vector<Point> vertices,
+ std::vector<uint16_t> indices,
+ std::vector<Scalar> gaussians) {
+ return std::make_shared<ShadowVertices>(
+ std::move(vertices), std::move(indices), std::move(gaussians));
+ }
+
+ constexpr ShadowVertices() {}
+
+ constexpr ShadowVertices(std::vector<Point> vertices,
+ std::vector<uint16_t> indices,
+ std::vector<Scalar> gaussians)
+ : vertices_(std::move(vertices)),
+ indices_(std::move(indices)),
+ gaussians_(std::move(gaussians)) {}
+
+ /// The count of the unique (duplicates minimized) vertices in the mesh.
+ /// This number is also the count of gaussian coefficients in the mesh
+ /// since the two are assigned 1:1.
+ size_t GetVertexCount() const { return vertices_.size(); }
+
+ /// The count of the indices that define the mesh.
+ size_t GetIndexCount() const { return indices_.size(); }
+
+ const std::vector<Point>& GetVertices() const { return vertices_; }
+ const std::vector<uint16_t>& GetIndices() const { return indices_; }
+ const std::vector<Scalar>& GetGaussians() const { return gaussians_; }
+
+ /// True if and only if there was no shadow for the shape and therefore
+ /// no mesh to generate.
+ bool IsEmpty() const { return vertices_.empty(); }
+
+ std::optional<Rect> GetBounds() const;
+
+ GeometryResult GetPositionBuffer(const ContentContext& renderer,
+ const Entity& entity,
+ RenderPass& pass) const;
+
+ private:
+ const std::vector<Point> vertices_;
+ const std::vector<uint16_t> indices_;
+ const std::vector<Scalar> gaussians_;
+};
+
+/// A class to compute and return the |ShadowVertices| for a path source
+/// viewed under a given transform. The |occluder_height| is measured in
+/// device pixels. The geometry of the |PathSource| is transformed by the
+/// indicated matrix to produce a device space set of vertices, and the
+/// shadow mesh is inset and outset by the indicated |occluder_height|
+/// without any adjustment for the matrix. The results are un-transformed
+/// and returned back iin the |ShadowVertices| in the original coordinate
+/// system.
+class ShadowPathGeometry {
+ public:
+ ShadowPathGeometry(Tessellator& tessellator,
+ const Matrix& matrix,
+ const PathSource& source,
+ Scalar occluder_height);
+
+ bool CanRender() const;
+
+ /// Returns true if this shadow has no effect, is not visible.
+ bool IsEmpty() const;
+
+ /// Returns a reference to the generated vertices, or null if the algorithm
+ /// failed to produce a mesh.
+ const std::shared_ptr<ShadowVertices>& GetShadowVertices() const;
+
+ /// Takes (returns the only copy of via std::move) the shadow vertices
+ /// or null if the algorithm failed to produce a mesh.
+ const std::shared_ptr<ShadowVertices> TakeShadowVertices();
+
+ /// Constructs a shadow mesh for the given |PathSource| at the given
+ /// |matrix| and with the indicated device-space |occluder_height|.
+ /// The tessellator is used to get a cached set of |Trigs| for the
+ /// radii associated with the mesh around various corners in the path.
+ static std::shared_ptr<ShadowVertices> MakeAmbientShadowVertices(
+ Tessellator& tessellator,
+ const PathSource& source,
+ Scalar occluder_height,
+ const Matrix& matrix);
+
+ private:
+ std::shared_ptr<ShadowVertices> shadow_vertices_;
+};
+
+} // namespace impeller
+
+#endif // FLUTTER_IMPELLER_ENTITY_GEOMETRY_SHADOW_PATH_GEOMETRY_H_
diff --git a/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry_unittests.cc b/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry_unittests.cc
new file mode 100644
index 0000000..ed7b4b0
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/geometry/shadow_path_geometry_unittests.cc
@@ -0,0 +1,1068 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "flutter/impeller/entity/geometry/shadow_path_geometry.h"
+
+#include "flutter/display_list/geometry/dl_path.h"
+#include "flutter/display_list/geometry/dl_path_builder.h"
+#include "gtest/gtest.h"
+
+#include "flutter/third_party/skia/src/core/SkVerticesPriv.h" // nogncheck
+#include "flutter/third_party/skia/src/utils/SkShadowTessellator.h" // nogncheck
+
+#define SHADOW_UNITTEST_SHOW_VERTICES false
+
+namespace impeller {
+namespace testing {
+
+using flutter::DlPath;
+using flutter::DlPathBuilder;
+using flutter::DlPoint;
+using flutter::DlRect;
+
+namespace {
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+void ShowVertices(const std::string& label,
+ const std::shared_ptr<ShadowVertices>& shadow_vertices) {
+ auto vertices = shadow_vertices->GetVertices();
+ auto alphas = shadow_vertices->GetGaussians();
+ auto indices = shadow_vertices->GetIndices();
+ FML_LOG(ERROR) << label << "[" << indices.size() / 3 << "] = {";
+ for (size_t i = 0u; i < indices.size(); i += 3) {
+ // clang-format off
+ FML_LOG(ERROR)
+ << " (" << vertices[indices[i + 0]] << ", " << alphas[indices[i + 0]] << "), "
+ << " (" << vertices[indices[i + 1]] << ", " << alphas[indices[i + 1]] << "), "
+ << " (" << vertices[indices[i + 2]] << ", " << alphas[indices[i + 2]] << ")";
+ // clang-format on
+ }
+ FML_LOG(ERROR) << "} // " << label;
+}
+#endif
+
+constexpr Scalar kEpsilonSquared =
+ flutter::kEhCloseEnough * flutter::kEhCloseEnough;
+
+bool SimilarPoint(Point p1, Point p2) {
+ return p1.GetDistanceSquared(p2) < kEpsilonSquared;
+}
+
+bool SimilarPointPair(std::array<Point, 2> pair1, std::array<Point, 2> pair2) {
+ if (SimilarPoint(pair1[1], pair2[1]) && SimilarPoint(pair1[2], pair2[2])) {
+ return true;
+ }
+ if (SimilarPoint(pair1[1], pair2[2]) && SimilarPoint(pair1[2], pair2[1])) {
+ return true;
+ }
+ return false;
+}
+
+bool SimilarPointTrio(std::array<Point, 3> trio1, std::array<Point, 3> trio2) {
+ if (SimilarPoint(trio1[1], trio2[1]) &&
+ SimilarPointPair({trio1[2], trio1[3]}, {trio2[2], trio2[3]})) {
+ return true;
+ }
+ if (SimilarPoint(trio1[1], trio2[2]) &&
+ SimilarPointPair({trio1[2], trio1[3]}, {trio2[1], trio2[3]})) {
+ return true;
+ }
+ if (SimilarPoint(trio1[1], trio2[3]) &&
+ SimilarPointPair({trio1[2], trio1[3]}, {trio2[1], trio2[2]})) {
+ return true;
+ }
+ return false;
+}
+
+size_t CountDuplicateVertices(
+ const std::shared_ptr<ShadowVertices>& shadow_vertices) {
+ size_t duplicate_vertices = 0u;
+ auto vertices = shadow_vertices->GetVertices();
+ size_t vertex_count = vertices.size();
+
+ for (size_t i = 1u; i < vertex_count; i++) {
+ Point& vertex = vertices[i];
+ for (size_t j = 0u; j < i; j++) {
+ if (SimilarPoint(vertex, vertices[j])) {
+ duplicate_vertices++;
+ }
+ }
+ }
+
+ return duplicate_vertices;
+}
+
+size_t CountDuplicateTriangles(
+ const std::shared_ptr<ShadowVertices>& shadow_vertices) {
+ size_t duplicate_triangles = 0u;
+ auto vertices = shadow_vertices->GetVertices();
+ auto indices = shadow_vertices->GetIndices();
+ size_t index_count = indices.size();
+
+ for (size_t i = 3u; i < index_count; i += 3) {
+ std::array trio1 = {
+ vertices[indices[i + 0]],
+ vertices[indices[i + 1]],
+ vertices[indices[i + 2]],
+ };
+ for (size_t j = 0; j < i; j += 3) {
+ std::array trio2 = {
+ vertices[indices[j + 0]],
+ vertices[indices[j + 1]],
+ vertices[indices[j + 2]],
+ };
+ if (SimilarPointTrio(trio1, trio2)) {
+ duplicate_triangles++;
+ }
+ }
+ }
+
+ return duplicate_triangles;
+}
+
+bool IsPointInsideTriangle(Point p, std::array<Point, 3> triangle) {
+ if (SimilarPoint(p, triangle[0]) || //
+ SimilarPoint(p, triangle[1]) || //
+ SimilarPoint(p, triangle[2])) {
+ return false;
+ }
+ Scalar direction = Point::Cross(p, triangle[0], triangle[1]);
+ // All 3 cross products must be non-zero and have the same sign.
+ return direction * Point::Cross(p, triangle[1], triangle[2]) > 0 &&
+ direction * Point::Cross(p, triangle[2], triangle[0]) > 0;
+};
+
+// This test verifies a condition that doesn't invalidate the process
+// per se, but we'd have to use overlap prevention to render the mesh
+// if this test returned true. We've carefully planned our meshes to
+// avoid that condition, though, so we're just making sure.
+bool DoTrianglesOverlap(
+ const std::shared_ptr<ShadowVertices>& shadow_vertices) {
+ auto vertices = shadow_vertices->GetVertices();
+ auto indices = shadow_vertices->GetIndices();
+ size_t index_count = indices.size();
+ size_t vertex_count = vertices.size();
+
+ for (size_t i = 0u; i < index_count; i += 3) {
+ std::array triangle = {
+ vertices[indices[i + 0]],
+ vertices[indices[i + 1]],
+ vertices[indices[i + 2]],
+ };
+ // Rather than check each pair of triangles to see if any of their
+ // vertices is inside the other, we just check the list of all vertices
+ // to see if that vertex is inside any triangle in the mesh.
+ for (size_t j = 0; j < vertex_count; j++) {
+ if (IsPointInsideTriangle(vertices[j], triangle)) {
+ FML_LOG(ERROR) << "Point " << vertices[j] << " inside triangle ["
+ << triangle[0] << ", " //
+ << triangle[1] << ", " //
+ << triangle[2] << "]";
+ FML_LOG(ERROR) << "Point - corner[0] == " << vertices[j] - triangle[0];
+ FML_LOG(ERROR) << "Point - corner[1] == " << vertices[j] - triangle[1];
+ FML_LOG(ERROR) << "Point - corner[2] == " << vertices[j] - triangle[2];
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+} // namespace
+
+TEST(ShadowPathGeometryTest, EmptyPathTest) {
+ DlPathBuilder path_builder;
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_TRUE(shadow_vertices->IsEmpty());
+}
+
+TEST(ShadowPathGeometryTest, MoveToOnlyTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_TRUE(shadow_vertices->IsEmpty());
+}
+
+TEST(ShadowPathGeometryTest, OnePathSegmentTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ path_builder.LineTo(DlPoint(200, 100));
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_TRUE(shadow_vertices->IsEmpty());
+}
+
+TEST(ShadowPathGeometryTest, TwoColinearSegmentsTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ path_builder.LineTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(300, 100));
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_TRUE(shadow_vertices->IsEmpty());
+}
+
+TEST(ShadowPathGeometryTest, EmptyRectTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 100));
+ path_builder.LineTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(200, 100));
+ path_builder.LineTo(DlPoint(100, 100));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_TRUE(shadow_vertices->IsEmpty());
+}
+
+TEST(ShadowPathGeometryTest, GetAndTakeVertices) {
+ DlPath path = DlPath::MakeRectLTRB(100, 100, 200, 200);
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ ShadowPathGeometry geometry(tessellator, {}, path, height);
+
+ // Can call Get as many times as you want.
+ for (int i = 0; i < 10; i++) {
+ EXPECT_TRUE(geometry.GetShadowVertices());
+ }
+
+ // Can only call Take once.
+ EXPECT_TRUE(geometry.TakeShadowVertices());
+
+ // Further access wll then fail.
+ EXPECT_FALSE(geometry.GetShadowVertices());
+ EXPECT_FALSE(geometry.TakeShadowVertices());
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseTriangleTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(200, 110));
+ path_builder.LineTo(DlPoint(0, 110));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 33u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 102u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 33u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 33u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 102u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ // There is another duplicate vertex from somewhere else not yet realized.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 2u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseTriangleTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(0, 110));
+ path_builder.LineTo(DlPoint(200, 110));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 33u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 102u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 33u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 33u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 102u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ // There is another duplicate vertex from somewhere else not yet realized.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 2u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseRectTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseRectTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseRectExtraColinearPointsTest) {
+ // This path includes a colinear point to each edge of the rectangle
+ // which should be trimmed out and ignored when generating the mesh
+ // resulting in the same number of vertices and triangles as the mesh
+ // above.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(50, 0));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(100, 40));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(50, 80));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(0, 40));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseRectExtraColinearPointsTest) {
+ // This path includes a colinear point to each edge of the rectangle
+ // which should be trimmed out and ignored when generating the mesh
+ // resulting in the same number of vertices and triangles as the mesh
+ // above.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(0, 40));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(50, 80));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(100, 40));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(50, 0));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseRectTrickyColinearPointsTest) {
+ // This path includes a colinear point added to each edge of the rectangle
+ // which seems to violate convexity, but is eliminated as not contributing
+ // to the path. We should be able to process the path anyway.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(-10, 0));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(100, -10));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(110, 80));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(0, 90));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseRectTrickyColinearPointsTest) {
+ // This path includes a colinear point added to each edge of the rectangle
+ // which seems to violate convexity, but is eliminated as not contributing
+ // to the path. We should be able to process the path anyway.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(0, -10));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(-10, 80));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(100, 90));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(110, 0));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseRectTrickyDupColinearPointsTest) {
+ // This path includes a colinear point added to each edge of the rectangle
+ // which seems to violate convexity, but is eliminated as not contributing
+ // to the path. We should be able to process the path anyway.
+ // It also includes multiple collinear points on the first and last points
+ // that end up back where we started to make sure that in that case we
+ // eliminate all of the collinear points and the duplicate, rather than
+ // just the intermediate collinear points.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(-10, 0));
+ path_builder.LineTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(100, -10));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(110, 80));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(0, 90));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseRectTrickyDupColinearPointsTest) {
+ // This path includes a colinear point added to each edge of the rectangle
+ // which seems to violate convexity, but is eliminated as not contributing
+ // to the path. We should be able to process the path anyway.
+ // It also includes multiple collinear points on the first and last points
+ // that end up back where we started to make sure that in that case we
+ // eliminate all of the collinear points and the duplicate, rather than
+ // just the intermediate collinear points.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(0, -10));
+ path_builder.LineTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(-10, 80));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(100, 90));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(110, 0));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseRectNearlyColinearPointsTest) {
+ // This path includes a bunch of colinear points and one point that
+ // is barely non-colinear but still convex. It should add exactly
+ // one extra set of vertices to the mesh (3 points and 3 triangles)
+ // compared to the regular rects.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(50, -0.065));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(100, 40));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(50, 80));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(0, 40));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 37u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 120u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 37u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 37u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 120u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseRectNearlyColinearPointsTest) {
+ // This path includes a bunch of colinear points and one point that
+ // is barely non-colinear but still convex. It should add exactly
+ // one extra set of vertices to the mesh (3 points and 3 triangles)
+ // compared to the regular rects.
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(-0.065, 40));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(50, 80));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(100, 40));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(50, 0));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 37u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 120u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 37u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 37u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 120u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, ScaledRectTest) {
+ Tessellator tessellator;
+ DlPath path = DlPath::MakeRect(DlRect::MakeLTRB(0, 0, 100, 80));
+ Matrix matrix = Matrix::MakeScale({2, 3, 1});
+ const Scalar height = 10.0f;
+
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 108u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 34u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 108u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+
+#if SHADOW_UNITTEST_SHOW_VERTICES
+ ShowVertices("Impeller Vertices", shadow_vertices);
+#endif
+}
+
+TEST(ShadowPathGeometryTest, EllipseTest) {
+ Tessellator tessellator;
+ DlPath path = DlPath::MakeOval(DlRect::MakeLTRB(0, 0, 100, 80));
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 122u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 480u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 122u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 122u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 480u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 1u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+}
+
+TEST(ShadowPathGeometryTest, RoundRectTest) {
+ Tessellator tessellator;
+ DlPath path = DlPath::MakeRoundRectXY(DlRect::MakeLTRB(0, 0, 100, 80), 5, 4);
+ Matrix matrix;
+ const Scalar height = 10.0f;
+
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 55u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 168u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 55u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 55u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 168u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ // There is another duplicate vertex from somewhere else not yet realized.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 2u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+}
+
+TEST(ShadowPathGeometryTest, HourglassSelfIntersectingTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+TEST(ShadowPathGeometryTest, ReverseHourglassSelfIntersectingTest) {
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(0, 0));
+ path_builder.LineTo(DlPoint(100, 80));
+ path_builder.LineTo(DlPoint(0, 80));
+ path_builder.LineTo(DlPoint(100, 0));
+ path_builder.Close();
+ const DlPath path = path_builder.TakePath();
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+TEST(ShadowPathGeometryTest, InnerToOuterOverturningSpiralTest) {
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+ int step_count = 20;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(300, 200));
+ for (int i = 1; i < step_count * 2; i++) {
+ Scalar angle = (k2Pi * i) / step_count;
+ Scalar radius = 80.0f + std::abs(i - step_count);
+ path_builder.LineTo(DlPoint(200, 200) + DlPoint(std::cos(angle) * radius,
+ std::sin(angle) * radius));
+ }
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+TEST(ShadowPathGeometryTest, ReverseInnerToOuterOverturningSpiralTest) {
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+ int step_count = 20;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(300, 200));
+ for (int i = 1; i < step_count * 2; i++) {
+ Scalar angle = -(k2Pi * i) / step_count;
+ Scalar radius = 80.0f + std::abs(i - step_count);
+ path_builder.LineTo(DlPoint(200, 200) + DlPoint(std::cos(angle) * radius,
+ std::sin(angle) * radius));
+ }
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+TEST(ShadowPathGeometryTest, OuterToInnerOverturningSpiralTest) {
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+ int step_count = 20;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(280, 200));
+ for (int i = 1; i < step_count * 2; i++) {
+ Scalar angle = (k2Pi * i) / step_count;
+ Scalar radius = 100.0f - std::abs(i - step_count);
+ path_builder.LineTo(DlPoint(200, 200) + DlPoint(std::cos(angle) * radius,
+ std::sin(angle) * radius));
+ }
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+TEST(ShadowPathGeometryTest, ReverseOuterToInnerOverturningSpiralTest) {
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+ int step_count = 20;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(280, 200));
+ for (int i = 1; i < step_count * 2; i++) {
+ Scalar angle = -(k2Pi * i) / step_count;
+ Scalar radius = 100.0f - std::abs(i - step_count);
+ path_builder.LineTo(DlPoint(200, 200) + DlPoint(std::cos(angle) * radius,
+ std::sin(angle) * radius));
+ }
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+TEST(ShadowPathGeometryTest, ClockwiseOctagonCollapsedUmbraPolygonTest) {
+ const Matrix matrix = Matrix::MakeScale({2, 2, 1});
+ const Scalar height = 100.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 125));
+ path_builder.LineTo(DlPoint(125, 100));
+ path_builder.LineTo(DlPoint(275, 100));
+ path_builder.LineTo(DlPoint(300, 125));
+ path_builder.LineTo(DlPoint(300, 275));
+ path_builder.LineTo(DlPoint(275, 300));
+ path_builder.LineTo(DlPoint(125, 300));
+ path_builder.LineTo(DlPoint(100, 275));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 87u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 267u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 87u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 87u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 267u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ // There are a couple additional duplicate vertices in this case.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 3u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+}
+
+TEST(ShadowPathGeometryTest, CounterClockwiseOctagonCollapsedUmbraPolygonTest) {
+ const Matrix matrix = Matrix::MakeScale({2, 2, 1});
+ const Scalar height = 100.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(100, 125));
+ path_builder.LineTo(DlPoint(100, 275));
+ path_builder.LineTo(DlPoint(125, 300));
+ path_builder.LineTo(DlPoint(275, 300));
+ path_builder.LineTo(DlPoint(300, 275));
+ path_builder.LineTo(DlPoint(300, 125));
+ path_builder.LineTo(DlPoint(275, 100));
+ path_builder.LineTo(DlPoint(125, 100));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ ASSERT_NE(shadow_vertices, nullptr);
+ EXPECT_FALSE(shadow_vertices->IsEmpty());
+ EXPECT_EQ(shadow_vertices->GetVertexCount(), 88u);
+ EXPECT_EQ(shadow_vertices->GetIndexCount(), 267u);
+ EXPECT_EQ(shadow_vertices->GetVertices().size(), 88u);
+ EXPECT_EQ(shadow_vertices->GetGaussians().size(), 88u);
+ EXPECT_EQ(shadow_vertices->GetIndices().size(), 267u);
+ EXPECT_EQ((shadow_vertices->GetIndices().size() % 3u), 0u);
+ // We repeat the first and last vertex that is on the outer umbra.
+ // There are a couple additional duplicate vertices in this case.
+ EXPECT_LE(CountDuplicateVertices(shadow_vertices), 3u);
+ EXPECT_EQ(CountDuplicateTriangles(shadow_vertices), 0u);
+ EXPECT_FALSE(DoTrianglesOverlap(shadow_vertices));
+}
+
+TEST(ShadowPathGeometryTest, MultipleContoursTest) {
+ const Matrix matrix;
+ const Scalar height = 10.0f;
+
+ DlPathBuilder path_builder;
+ path_builder.MoveTo(DlPoint(150, 100));
+ path_builder.LineTo(DlPoint(200, 300));
+ path_builder.LineTo(DlPoint(100, 300));
+ path_builder.Close();
+ path_builder.MoveTo(DlPoint(250, 100));
+ path_builder.LineTo(DlPoint(300, 300));
+ path_builder.LineTo(DlPoint(200, 300));
+ path_builder.Close();
+ DlPath path = path_builder.TakePath();
+
+ Tessellator tessellator;
+ std::shared_ptr<ShadowVertices> shadow_vertices =
+ ShadowPathGeometry::MakeAmbientShadowVertices(tessellator, path, height,
+ matrix);
+
+ EXPECT_EQ(shadow_vertices, nullptr);
+}
+
+} // namespace testing
+} // namespace impeller
diff --git a/engine/src/flutter/impeller/entity/shaders/shadow_vertices.frag b/engine/src/flutter/impeller/entity/shaders/shadow_vertices.frag
new file mode 100644
index 0000000..8bd5b66
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/shaders/shadow_vertices.frag
@@ -0,0 +1,29 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <impeller/gaussian.glsl>
+#include <impeller/types.glsl>
+
+uniform FragInfo {
+ // shadow_color is the color supplied to DrawShadow. It will be modulated
+ // by the gaussian opacity of the shadow, computed from the coefficient
+ // in the mesh vertex data.
+ f16vec4 shadow_color;
+}
+frag_info;
+
+// v_gaussian will contain the interpolated gaussian coefficient from the
+// mesh per-vertex data. It determines where in the gaussian curve of the
+// umbra and penumbra we are with 0.0 representing the outermost part of
+// the penumbra and 1.0 representing the innermost umbra.
+in float16_t v_gaussian;
+
+out f16vec4 frag_color;
+
+// A shader that modulates the shadow color by the gaussian integral
+// value computed from the interpolated v_gaussian coefficient.
+void main() {
+ frag_color =
+ frag_info.shadow_color * IPHalfFractionToFastGaussianCDF(v_gaussian);
+}
diff --git a/engine/src/flutter/impeller/entity/shaders/shadow_vertices.vert b/engine/src/flutter/impeller/entity/shaders/shadow_vertices.vert
new file mode 100644
index 0000000..aef5738
--- /dev/null
+++ b/engine/src/flutter/impeller/entity/shaders/shadow_vertices.vert
@@ -0,0 +1,20 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <impeller/types.glsl>
+
+uniform FrameInfo {
+ mat4 mvp;
+}
+frame_info;
+
+in vec2 position;
+in float gaussian;
+
+out float16_t v_gaussian;
+
+void main() {
+ gl_Position = frame_info.mvp * vec4(position, 0.0, 1.0);
+ v_gaussian = float16_t(gaussian);
+}
diff --git a/engine/src/flutter/impeller/geometry/BUILD.gn b/engine/src/flutter/impeller/geometry/BUILD.gn
index 50c2fa8..ffebf52 100644
--- a/engine/src/flutter/impeller/geometry/BUILD.gn
+++ b/engine/src/flutter/impeller/geometry/BUILD.gn
@@ -83,6 +83,7 @@
"geometry_unittests.cc",
"matrix_unittests.cc",
"path_source_unittests.cc",
+ "point_unittests.cc",
"rational_unittests.cc",
"rect_unittests.cc",
"round_rect_unittests.cc",
diff --git a/engine/src/flutter/impeller/geometry/geometry_benchmarks.cc b/engine/src/flutter/impeller/geometry/geometry_benchmarks.cc
index 50f4a59..c149432 100644
--- a/engine/src/flutter/impeller/geometry/geometry_benchmarks.cc
+++ b/engine/src/flutter/impeller/geometry/geometry_benchmarks.cc
@@ -6,6 +6,7 @@
#include "flutter/display_list/geometry/dl_path.h"
#include "flutter/display_list/geometry/dl_path_builder.h"
+#include "impeller/entity/geometry/shadow_path_geometry.h"
#include "impeller/entity/geometry/stroke_path_geometry.h"
#include "impeller/tessellator/tessellator_libtess.h"
@@ -33,6 +34,22 @@
flutter::DlPath CreateRRect();
/// Create a rounded superellipse.
flutter::DlPath CreateRSuperellipse();
+/// Create a clockwise triangle path.
+flutter::DlPath CreateClockwiseTriangle();
+/// Create a counter-clockwise triangle path.
+flutter::DlPath CreateCounterClockwiseTriangle();
+/// Create a clockwise rect path.
+flutter::DlPath CreateClockwiseRect();
+/// Create a counter-clockwise rect path.
+flutter::DlPath CreateCounterClockwiseRect();
+/// Create a clockwise multi-radii round rect path.
+flutter::DlPath CreateClockwiseMultiRadiiRoundRect();
+/// Create a counter-clockwise multi-radii round rect path.
+flutter::DlPath CreateCounterClockwiseMultiRadiiRoundRect();
+/// Create a clockwise polygonal path.
+flutter::DlPath CreateClockwisePolygon();
+/// Create a counter-clockwise polygonal path.
+flutter::DlPath CreateCounterClockwisePolygon();
} // namespace
static TessellatorLibtess tess;
@@ -85,6 +102,40 @@
state.counters["TotalPointCount"] = point_count;
}
+template <class... Args>
+static void BM_ShadowPathVerticesImpeller(benchmark::State& state,
+ Args&&... args) {
+ auto args_tuple = std::make_tuple(std::move(args)...);
+ auto path = std::get<flutter::DlPath>(args_tuple);
+ auto height = std::get<Scalar>(args_tuple);
+ auto matrix = std::get<Matrix>(args_tuple);
+
+ Tessellator tessellator;
+
+ while (state.KeepRunning()) {
+ auto result = ShadowPathGeometry::MakeAmbientShadowVertices(
+ tessellator, path, height, matrix);
+ FML_CHECK(result != nullptr);
+ }
+}
+
+#define MAKE_SHADOW_BENCHMARK_CAPTURE(clockwise, shape, backend) \
+ BENCHMARK_CAPTURE(BM_ShadowPathVertices##backend, \
+ shadow_##clockwise##_##shape##_##backend, \
+ Create##clockwise##shape(), 20.0f, Matrix{})
+
+#define MAKE_SHADOW_BENCHMARK_SHAPE_CAPTURE(shape, backend) \
+ MAKE_SHADOW_BENCHMARK_CAPTURE(Clockwise, shape, backend); \
+ MAKE_SHADOW_BENCHMARK_CAPTURE(CounterClockwise, shape, backend)
+
+#define MAKE_SHADOW_BENCHMARK_CAPTURE_ALL_SHAPES(backend) \
+ MAKE_SHADOW_BENCHMARK_SHAPE_CAPTURE(Triangle, backend); \
+ MAKE_SHADOW_BENCHMARK_SHAPE_CAPTURE(Rect, backend); \
+ MAKE_SHADOW_BENCHMARK_SHAPE_CAPTURE(MultiRadiiRoundRect, backend); \
+ MAKE_SHADOW_BENCHMARK_SHAPE_CAPTURE(Polygon, backend)
+
+MAKE_SHADOW_BENCHMARK_CAPTURE_ALL_SHAPES(Impeller);
+
#define MAKE_STROKE_PATH_BENCHMARK_CAPTURE(path, cap, join, closed) \
BENCHMARK_CAPTURE(BM_StrokePath, stroke_##path##_##cap##_##join, \
Create##path(closed), Cap::k##cap, Join::k##join)
@@ -116,6 +167,146 @@
namespace {
+flutter::DlPath CreateClockwiseTriangle() {
+ flutter::DlPathBuilder builder;
+ builder.MoveTo(flutter::DlPoint(100, 100));
+ builder.LineTo(flutter::DlPoint(300, 100));
+ builder.LineTo(flutter::DlPoint(200, 300));
+ builder.Close();
+ return builder.TakePath();
+}
+
+flutter::DlPath CreateCounterClockwiseTriangle() {
+ flutter::DlPathBuilder builder;
+ builder.MoveTo(flutter::DlPoint(100, 100));
+ builder.LineTo(flutter::DlPoint(200, 300));
+ builder.LineTo(flutter::DlPoint(300, 100));
+ builder.Close();
+ return builder.TakePath();
+}
+
+flutter::DlPath CreateClockwiseRect() {
+ flutter::DlPathBuilder builder;
+ builder.MoveTo(flutter::DlPoint(100, 100));
+ builder.LineTo(flutter::DlPoint(300, 100));
+ builder.LineTo(flutter::DlPoint(300, 300));
+ builder.LineTo(flutter::DlPoint(100, 300));
+ builder.Close();
+ return builder.TakePath();
+}
+
+flutter::DlPath CreateCounterClockwiseRect() {
+ flutter::DlPathBuilder builder;
+ builder.MoveTo(flutter::DlPoint(100, 100));
+ builder.LineTo(flutter::DlPoint(100, 300));
+ builder.LineTo(flutter::DlPoint(300, 300));
+ builder.LineTo(flutter::DlPoint(300, 100));
+ builder.Close();
+ return builder.TakePath();
+}
+
+class HorizontalPathFlipper : private flutter::DlPathReceiver {
+ public:
+ HorizontalPathFlipper(const flutter::DlPath& path, Scalar flip_coordinate)
+ : flip_coordinate_(flip_coordinate) {
+ path.Dispatch(*this);
+ }
+
+ flutter::DlPath TakePath() { return builder_.TakePath(); }
+
+ private:
+ const Scalar flip_coordinate_;
+ flutter::DlPathBuilder builder_;
+
+ flutter::DlPoint flip(flutter::DlPoint p) {
+ return flutter::DlPoint(flip_coordinate_ * 2 - p.x, p.y);
+ }
+
+ // |flutter::DlPathReceiver|
+ void MoveTo(const Point& p2, bool will_be_closed) override {
+ builder_.MoveTo(flip(p2));
+ }
+
+ // |flutter::DlPathReceiver|
+ void LineTo(const Point& p2) override { //
+ builder_.LineTo(flip(p2));
+ }
+
+ // |flutter::DlPathReceiver|
+ void QuadTo(const Point& cp, const Point& p2) override {
+ builder_.QuadraticCurveTo(flip(cp), flip(p2));
+ }
+
+ // |flutter::DlPathReceiver|
+ bool ConicTo(const Point& cp, const Point& p2, Scalar weight) override {
+ builder_.ConicCurveTo(flip(cp), flip(p2), weight);
+ return true;
+ }
+
+ // |flutter::DlPathReceiver|
+ void CubicTo(const Point& cp1, const Point& cp2, const Point& p2) override {
+ builder_.CubicCurveTo(flip(cp1), flip(cp2), flip(p2));
+ }
+
+ // |flutter::DlPathReceiver|
+ void Close() override {}
+};
+
+flutter::DlPath CreateClockwiseMultiRadiiRoundRect() {
+ // Upper left corner: 10 x 15
+ // Upper right corner: 15 x 10
+ // Bottom right corner: 16 x 20
+ // Bottom left corner: 20 x 16
+ flutter::DlPathBuilder builder;
+ builder.MoveTo(flutter::DlPoint(110, 100));
+ builder.LineTo(flutter::DlPoint(285, 100));
+ builder.ConicCurveTo(flutter::DlPoint(300, 100), flutter::DlPoint(300, 110),
+ kSqrt2);
+ builder.LineTo(flutter::DlPoint(300, 280));
+ builder.ConicCurveTo(flutter::DlPoint(300, 300), flutter::DlPoint(284, 300),
+ kSqrt2);
+ builder.LineTo(flutter::DlPoint(120, 300));
+ builder.ConicCurveTo(flutter::DlPoint(100, 300), flutter::DlPoint(100, 284),
+ kSqrt2);
+ builder.LineTo(flutter::DlPoint(100, 115));
+ builder.ConicCurveTo(flutter::DlPoint(100, 100), flutter::DlPoint(110, 100),
+ kSqrt2);
+ builder.Close();
+ return builder.TakePath();
+}
+
+flutter::DlPath CreateCounterClockwiseMultiRadiiRoundRect() {
+ flutter::DlPath clockwise_path = CreateClockwiseMultiRadiiRoundRect();
+ return HorizontalPathFlipper(clockwise_path, 200.0f).TakePath();
+}
+
+flutter::DlPath CreatePolygon(bool clockwise) {
+ int vertex_count = 40;
+ Scalar direction = clockwise ? 1.0f : -1.0f;
+
+ auto make_point = [](Scalar angle) {
+ return flutter::DlPoint(200 + 100 * std::cos(angle),
+ 200 + 100 * std::sin(angle));
+ };
+
+ flutter::DlPathBuilder builder;
+ builder.MoveTo(make_point(0.0f));
+ for (int i = 1; i < vertex_count; i++) {
+ Scalar angle = (static_cast<Scalar>(i) / vertex_count) * k2Pi;
+ builder.LineTo(make_point(angle * direction));
+ }
+ builder.Close();
+ return builder.TakePath();
+}
+
+flutter::DlPath CreateClockwisePolygon() {
+ return CreatePolygon(true);
+}
+
+flutter::DlPath CreateCounterClockwisePolygon() {
+ return CreatePolygon(false);
+}
+
flutter::DlPath CreateRRect() {
return flutter::DlPathBuilder{}
.AddRoundRect(
diff --git a/engine/src/flutter/impeller/geometry/path_source.h b/engine/src/flutter/impeller/geometry/path_source.h
index 13511a8..6b02068 100644
--- a/engine/src/flutter/impeller/geometry/path_source.h
+++ b/engine/src/flutter/impeller/geometry/path_source.h
@@ -109,6 +109,39 @@
const Rect bounds_;
};
+/// A utility class to receive path segments from a source, transform them
+/// by a matrix, and pass them along to a subsequent receiver.
+class PathTransformer : public impeller::PathReceiver {
+ public:
+ PathTransformer(PathReceiver& receiver [[clang::lifetimebound]],
+ const impeller::Matrix& matrix [[clang::lifetimebound]])
+ : receiver_(receiver), matrix_(matrix) {}
+
+ void MoveTo(const Point& p2, bool will_be_closed) override {
+ receiver_.MoveTo(matrix_ * p2, will_be_closed);
+ }
+
+ void LineTo(const Point& p2) override { receiver_.LineTo(matrix_ * p2); }
+
+ void QuadTo(const Point& cp, const Point& p2) override {
+ receiver_.QuadTo(matrix_ * cp, matrix_ * p2);
+ }
+
+ bool ConicTo(const Point& cp, const Point& p2, Scalar weight) override {
+ return receiver_.ConicTo(matrix_ * cp, matrix_ * p2, weight);
+ }
+
+ void CubicTo(const Point& cp1, const Point& cp2, const Point& p2) override {
+ receiver_.CubicTo(matrix_ * cp1, matrix_ * cp2, matrix_ * p2);
+ }
+
+ void Close() override { receiver_.Close(); }
+
+ private:
+ PathReceiver& receiver_;
+ const impeller::Matrix& matrix_;
+};
+
} // namespace impeller
#endif // FLUTTER_IMPELLER_GEOMETRY_PATH_SOURCE_H_
diff --git a/engine/src/flutter/impeller/geometry/path_source_unittests.cc b/engine/src/flutter/impeller/geometry/path_source_unittests.cc
index 13b826f..650d12c 100644
--- a/engine/src/flutter/impeller/geometry/path_source_unittests.cc
+++ b/engine/src/flutter/impeller/geometry/path_source_unittests.cc
@@ -16,7 +16,8 @@
namespace impeller {
namespace testing {
-using DlPathReceiverMock = flutter::testing::DlPathReceiverMock;
+using ::flutter::testing::DlPathReceiverMock;
+using ::testing::Return;
TEST(PathSourceTest, RectSourceTest) {
Rect rect = Rect::MakeLTRB(10, 15, 20, 30);
@@ -251,5 +252,71 @@
source.Dispatch(receiver);
}
+TEST(PathSourceTest, PathTransformerRectSourceTest) {
+ Matrix matrix =
+ Matrix::MakeTranslateScale({2.0f, 3.0f, 1.0f}, {1.5f, 4.25f, 0.0f});
+ Rect rect = Rect::MakeLTRB(10, 15, 20, 30);
+ RectPathSource source(rect);
+
+ EXPECT_TRUE(source.IsConvex());
+ EXPECT_EQ(source.GetFillType(), FillType::kNonZero);
+ EXPECT_EQ(source.GetBounds(), Rect::MakeLTRB(10, 15, 20, 30));
+
+ ::testing::StrictMock<DlPathReceiverMock> mock_receiver;
+ PathTransformer receiver = PathTransformer(mock_receiver, matrix);
+
+ {
+ ::testing::Sequence sequence;
+
+ EXPECT_CALL(mock_receiver, MoveTo(Point(21.5f, 49.25f), true));
+ EXPECT_CALL(mock_receiver, LineTo(Point(41.5f, 49.25f)));
+ EXPECT_CALL(mock_receiver, LineTo(Point(41.5f, 94.25f)));
+ EXPECT_CALL(mock_receiver, LineTo(Point(21.5f, 94.25f)));
+ EXPECT_CALL(mock_receiver, LineTo(Point(21.5f, 49.25f)));
+ EXPECT_CALL(mock_receiver, Close());
+ }
+
+ source.Dispatch(receiver);
+}
+
+TEST(PathSourceTest, PathTransformerAllSegmentsTest) {
+ Matrix matrix =
+ Matrix::MakeTranslateScale({2.0f, 3.0f, 1.0f}, {1.5f, 4.25f, 0.0f});
+
+ ::testing::StrictMock<DlPathReceiverMock> mock_receiver;
+ PathTransformer receiver = PathTransformer(mock_receiver, matrix);
+
+ {
+ ::testing::Sequence sequence;
+
+ EXPECT_CALL(mock_receiver, MoveTo(Point(21.5f, 49.25f), false));
+ EXPECT_CALL(mock_receiver, LineTo(Point(41.5f, 49.25f)));
+
+ EXPECT_CALL(mock_receiver, MoveTo(Point(221.5f, 349.25f), true));
+ EXPECT_CALL(mock_receiver,
+ QuadTo(Point(241.5f, 349.25f), Point(241.5f, 394.25f)));
+ EXPECT_CALL(mock_receiver,
+ ConicTo(Point(237.5f, 409.25f), Point(231.5f, 409.25f), 5))
+ .WillOnce(Return(true));
+ EXPECT_CALL(mock_receiver,
+ ConicTo(Point(225.5f, 409.25f), Point(221.5f, 394.25f), 6))
+ .WillOnce(Return(false));
+ EXPECT_CALL(mock_receiver,
+ CubicTo(Point(211.5f, 379.25f), Point(211.5f, 364.25f),
+ Point(221.5f, 349.25f)));
+ EXPECT_CALL(mock_receiver, Close());
+ }
+
+ receiver.MoveTo(Point(10, 15), false);
+ receiver.LineTo(Point(20, 15));
+
+ receiver.MoveTo(Point(110, 115), true);
+ receiver.QuadTo(Point(120, 115), Point(120, 130));
+ EXPECT_TRUE(receiver.ConicTo(Point(118, 135), Point(115, 135), 5));
+ EXPECT_FALSE(receiver.ConicTo(Point(112, 135), Point(110, 130), 6));
+ receiver.CubicTo(Point(105, 125), Point(105, 120), Point(110, 115));
+ receiver.Close();
+}
+
} // namespace testing
} // namespace impeller
diff --git a/engine/src/flutter/impeller/geometry/point.h b/engine/src/flutter/impeller/geometry/point.h
index fc57dd9..8ce4642 100644
--- a/engine/src/flutter/impeller/geometry/point.h
+++ b/engine/src/flutter/impeller/geometry/point.h
@@ -12,6 +12,7 @@
#include <string>
#include <type_traits>
+#include "fml/logging.h"
#include "impeller/geometry/scalar.h"
#include "impeller/geometry/size.h"
#include "impeller/geometry/type_traits.h"
@@ -201,9 +202,85 @@
return sqrt(GetDistanceSquared(p));
}
- constexpr Type GetLengthSquared() const { return GetDistanceSquared({}); }
+ constexpr Type GetLengthSquared() const {
+ return static_cast<double>(x) * x + static_cast<double>(y) * y;
+ }
- constexpr Type GetLength() const { return GetDistance({}); }
+ constexpr Type GetLength() const { return std::sqrt(GetLengthSquared()); }
+
+ /// Returns the distance (squared) from this point to the closest point on
+ /// the line segment p0 -> p1.
+ ///
+ /// If the projection of this point onto the line defined by the two points
+ /// is between them, the distance (squared) to that point is returned.
+ /// Otherwise, we return the distance (squared) to the endpoint that is
+ /// closer to the projected point.
+ Type GetDistanceToSegmentSquared(TPoint p0, TPoint p1) const {
+ // Compute relative vectors to one endpoint of the segment (p0)
+ TPoint u = p1 - p0;
+ TPoint v = *this - p0;
+
+ // Compute the projection of (this point) onto p0->p1.
+ Scalar dot = u.Dot(v);
+ if (dot <= 0) {
+ // The projection lands outside the segment on the p0 side.
+ // The result is the (square of the) distance to p0 (length of v).
+ return v.GetLengthSquared();
+ }
+
+ // The dot product is the product of the length of the two vectors
+ // ||u|| and ||v|| and the cosine of the angle between them. The length
+ // of the v vector times the cosine is the same as the length of
+ // the projection of the v vector onto the u vector (consider a right
+ // triangle [(0,0), v, v_projected], the length of v multipled by the
+ // cosine is the length of v_projected).
+ //
+ // Thus the dot product is also the product of the u vector and the
+ // projected shadow of the v vector onto the u vector.
+ //
+ // So, if the dot product is larger than the square of the length of
+ // the u vector, then the v vector was projected onto the line beyond
+ // the end of the u vector and so we can use the distance formula to
+ // that endpoint as our result.
+ Scalar uLengthSquared = u.GetLengthSquared();
+ if (dot >= uLengthSquared) {
+ // The projection lands outside the segment on the p1 side.
+ // The result is the (square of the) distance to p1.
+ return GetDistanceSquared(p1);
+ }
+
+ // We must now compute the distance from this point to its projection
+ // on to the segment.
+ //
+ // We compute the cross product of the two vectors u and v which
+ // gives us the area of the parallelogram [(0,0), u, u+v, v]. That
+ // parallelogram area is also the product of the length of one of its
+ // sides and the height perpendicular to that side. We have the length
+ // of one side which is the length of the segment itself (squared) as
+ // uLengthSquared, so if we divide the parallelogram area (squared)
+ // by uLengthSquared then we will get its height (squared) relative to u.
+ //
+ // That height is also the distance from this point to the line segment.
+ Scalar cross = u.Cross(v);
+ // The cross product may currently be signed, but we will square it later.
+
+ // To get our height (squared), we want to compute:
+ // result^2 == h^2 == (cross * cross / uLengthSquared)
+ //
+ // We reorder the equation slightly to avoid infinities:
+ return (cross / uLengthSquared) * cross;
+ }
+
+ /// Returns the distance from this point to the closest point on the line
+ /// segment p0 -> p1.
+ ///
+ /// If the projection of this point onto the line defined by the two points
+ /// is between them, the distance to that point is returned. Otherwise,
+ /// we return the distance to the endpoint that is closer to the projected
+ /// point.
+ constexpr Type GetDistanceToSegment(TPoint p0, TPoint p1) const {
+ return std::sqrt(GetDistanceToSegmentSquared(p0, p1));
+ }
constexpr TPoint Normalize() const {
const auto length = GetLength();
@@ -217,6 +294,17 @@
constexpr Type Cross(const TPoint& p) const { return (x * p.y) - (y * p.x); }
+ /// Return the cross product representing the sign (turning direction) and
+ /// magnitude (sin of the angle) of the angle from p1 to p2 as viewed from
+ /// p0.
+ ///
+ /// Equivalent to ((p1 - p0).Cross(p2 - p0)).
+ static constexpr Type Cross(const TPoint& p0,
+ const TPoint& p1,
+ const TPoint& p2) {
+ return (p1 - p0).Cross(p2 - p0);
+ }
+
constexpr Type Dot(const TPoint& p) const { return (x * p.x) + (y * p.y); }
constexpr TPoint Reflect(const TPoint& axis) const {
@@ -229,6 +317,16 @@
return {x * cos_a - y * sin_a, x * sin_a + y * cos_a};
}
+ /// Return the perpendicular vector turning to the right (Clockwise)
+ /// in the logical coordinate system where X increases to the right and Y
+ /// increases downward.
+ constexpr TPoint PerpendicularRight() const { return {-y, x}; }
+
+ /// Return the perpendicular vector turning to the left (Counterclockwise)
+ /// in the logical coordinate system where X increases to the right and Y
+ /// increases downward.
+ constexpr TPoint PerpendicularLeft() const { return {y, -x}; }
+
constexpr Radians AngleTo(const TPoint& p) const {
return Radians{std::atan2(this->Cross(p), this->Dot(p))};
}
diff --git a/engine/src/flutter/impeller/geometry/point_unittests.cc b/engine/src/flutter/impeller/geometry/point_unittests.cc
new file mode 100644
index 0000000..2de17a0
--- /dev/null
+++ b/engine/src/flutter/impeller/geometry/point_unittests.cc
@@ -0,0 +1,385 @@
+// Copyright 2013 The Flutter Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "flutter/impeller/geometry/point.h"
+
+#include "flutter/impeller/geometry/geometry_asserts.h"
+#include "gtest/gtest.h"
+
+namespace impeller {
+namespace testing {
+
+TEST(PointTest, Length) {
+ for (int i = 0; i < 21; i++) {
+ EXPECT_EQ(Point(i, 0).GetLengthSquared(), i * i) << "i: " << i;
+ EXPECT_EQ(Point(0, i).GetLengthSquared(), i * i) << "i: " << i;
+ EXPECT_EQ(Point(-i, 0).GetLengthSquared(), i * i) << "i: " << i;
+ EXPECT_EQ(Point(0, -i).GetLengthSquared(), i * i) << "i: " << i;
+
+ EXPECT_EQ(Point(i, 0).GetLength(), i) << "i: " << i;
+ EXPECT_EQ(Point(0, i).GetLength(), i) << "i: " << i;
+ EXPECT_EQ(Point(-i, 0).GetLength(), i) << "i: " << i;
+ EXPECT_EQ(Point(0, -i).GetLength(), i) << "i: " << i;
+
+ EXPECT_EQ(Point(i, i).GetLengthSquared(), 2 * i * i) << "i: " << i;
+ EXPECT_EQ(Point(-i, i).GetLengthSquared(), 2 * i * i) << "i: " << i;
+ EXPECT_EQ(Point(i, -i).GetLengthSquared(), 2 * i * i) << "i: " << i;
+ EXPECT_EQ(Point(-i, -i).GetLengthSquared(), 2 * i * i) << "i: " << i;
+
+ EXPECT_FLOAT_EQ(Point(i, i).GetLength(), kSqrt2 * i) << "i: " << i;
+ EXPECT_FLOAT_EQ(Point(-i, i).GetLength(), kSqrt2 * i) << "i: " << i;
+ EXPECT_FLOAT_EQ(Point(i, -i).GetLength(), kSqrt2 * i) << "i: " << i;
+ EXPECT_FLOAT_EQ(Point(-i, -i).GetLength(), kSqrt2 * i) << "i: " << i;
+ }
+}
+
+TEST(PointTest, Distance) {
+ for (int j = 0; j < 21; j++) {
+ for (int i = 0; i < 21; i++) {
+ {
+ Scalar d = i - j;
+
+ EXPECT_EQ(Point(i, 0).GetDistanceSquared(Point(j, 0)), d * d)
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(0, i).GetDistanceSquared(Point(0, j)), d * d)
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(j, 0).GetDistanceSquared(Point(i, 0)), d * d)
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(0, j).GetDistanceSquared(Point(0, i)), d * d)
+ << "i: " << i << ", j: " << j;
+
+ EXPECT_EQ(Point(i, 0).GetDistance(Point(j, 0)), std::abs(d))
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(0, i).GetDistance(Point(0, j)), std::abs(d))
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(j, 0).GetDistance(Point(i, 0)), std::abs(d))
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(0, j).GetDistance(Point(0, i)), std::abs(d))
+ << "i: " << i << ", j: " << j;
+ }
+
+ {
+ Scalar d_squared = i * i + j * j;
+
+ EXPECT_EQ(Point(i, 0).GetDistanceSquared(Point(0, j)), d_squared)
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(-i, 0).GetDistanceSquared(Point(0, j)), d_squared)
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(i, 0).GetDistanceSquared(Point(0, -j)), d_squared)
+ << "i: " << i << ", j: " << j;
+ EXPECT_EQ(Point(-i, 0).GetDistanceSquared(Point(0, -j)), d_squared)
+ << "i: " << i << ", j: " << j;
+
+ Scalar d = std::sqrt(d_squared);
+
+ EXPECT_FLOAT_EQ(Point(i, 0).GetDistance(Point(0, j)), d)
+ << "i: " << i << ", j: " << j;
+ EXPECT_FLOAT_EQ(Point(-i, 0).GetDistance(Point(0, j)), d)
+ << "i: " << i << ", j: " << j;
+ EXPECT_FLOAT_EQ(Point(i, 0).GetDistance(Point(0, -j)), d)
+ << "i: " << i << ", j: " << j;
+ EXPECT_FLOAT_EQ(Point(-i, 0).GetDistance(Point(0, -j)), d)
+ << "i: " << i << ", j: " << j;
+ }
+ }
+ }
+}
+
+TEST(PointTest, PerpendicularLeft) {
+ EXPECT_EQ(Point(1, 0).PerpendicularLeft(), Point(0, -1));
+ EXPECT_EQ(Point(0, 1).PerpendicularLeft(), Point(1, 0));
+ EXPECT_EQ(Point(-1, 0).PerpendicularLeft(), Point(0, 1));
+ EXPECT_EQ(Point(0, -1).PerpendicularLeft(), Point(-1, 0));
+
+ EXPECT_EQ(Point(1, 1).PerpendicularLeft(), Point(1, -1));
+ EXPECT_EQ(Point(-1, 1).PerpendicularLeft(), Point(1, 1));
+ EXPECT_EQ(Point(-1, -1).PerpendicularLeft(), Point(-1, 1));
+ EXPECT_EQ(Point(1, -1).PerpendicularLeft(), Point(-1, -1));
+}
+
+TEST(PointTest, PerpendicularRight) {
+ EXPECT_EQ(Point(1, 0).PerpendicularRight(), Point(0, 1));
+ EXPECT_EQ(Point(0, 1).PerpendicularRight(), Point(-1, 0));
+ EXPECT_EQ(Point(-1, 0).PerpendicularRight(), Point(0, -1));
+ EXPECT_EQ(Point(0, -1).PerpendicularRight(), Point(1, 0));
+
+ EXPECT_EQ(Point(1, 1).PerpendicularRight(), Point(-1, 1));
+ EXPECT_EQ(Point(-1, 1).PerpendicularRight(), Point(-1, -1));
+ EXPECT_EQ(Point(-1, -1).PerpendicularRight(), Point(1, -1));
+ EXPECT_EQ(Point(1, -1).PerpendicularRight(), Point(1, 1));
+}
+
+namespace {
+typedef std::pair<Scalar, Scalar> PtSegmentDistanceFunc(Point);
+
+void TestPointToSegmentGroup(Point segment0,
+ Point segment1,
+ Point p0,
+ Point delta,
+ int count,
+ PtSegmentDistanceFunc calc_distance) {
+ for (int i = 0; i < count; i++) {
+ auto [distance, squared] = calc_distance(p0);
+ EXPECT_FLOAT_EQ(p0.GetDistanceToSegmentSquared(segment0, segment1), squared)
+ << p0 << " => [" << segment0 << ", " << segment1 << "]";
+ EXPECT_FLOAT_EQ(p0.GetDistanceToSegmentSquared(segment1, segment0), squared)
+ << p0 << " => [" << segment0 << ", " << segment1 << "]";
+ EXPECT_FLOAT_EQ(p0.GetDistanceToSegment(segment0, segment1), distance)
+ << p0 << " => [" << segment0 << ", " << segment1 << "]";
+ EXPECT_FLOAT_EQ(p0.GetDistanceToSegment(segment1, segment0), distance)
+ << p0 << " => [" << segment0 << ", " << segment1 << "]";
+ p0 += delta;
+ }
+}
+} // namespace
+
+TEST(PointTest, PointToSegment) {
+ // Horizontal segment and points to the left of it on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 10},
+ // Starting point, delta, count ({0,10} through {10,10})
+ {0, 10}, {1, 0}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d = 10 - p.x;
+ return std::make_pair(d, d * d);
+ });
+
+ // Horizontal segment and points on the segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 10},
+ // Starting point, delta, count ({11,10} through {19, 10})
+ {11, 10}, {1, 0}, 9,
+ // Distance computation
+ [](Point p) { //
+ return std::make_pair(0.0f, 0.0f);
+ });
+
+ // Horizontal segment and points to the right of it on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 10},
+ // Starting point, delta, count ({20,10} through {30,10})
+ {20, 10}, {1, 0}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d = p.x - 20;
+ return std::make_pair(d, d * d);
+ });
+
+ // Vertical segment and points above the top of it on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {10, 20},
+ // Starting point, delta, count ({10,0} through {10,10})
+ {10, 0}, {0, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d = 10 - p.y;
+ return std::make_pair(d, d * d);
+ });
+
+ // Vertical segment and points on the segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {10, 20},
+ // Starting point, delta, count ({10,11} through {10, 19})
+ {10, 11}, {0, 1}, 9,
+ // Distance computation
+ [](Point p) { //
+ return std::make_pair(0.0f, 0.0f);
+ });
+
+ // Vertical segment and points below the bottom of it on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {10, 20},
+ // Starting point, delta, count ({10,20} through {10,30})
+ {10, 20}, {0, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d = p.y - 20;
+ return std::make_pair(d, d * d);
+ });
+
+ // Horizontal segment and points 5 pixels above and to the left of it
+ // on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 10},
+ // Starting point, delta, count ({0,5} through {10,5})
+ {0, 5}, {1, 0}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = (10 - p.x) * (10 - p.x) + 25;
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Horizontal segment and points 5 pixels directly above the segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 10},
+ // Starting point, delta, count ({11,5} through {19, 5})
+ {11, 5}, {1, 0}, 9,
+ // Distance computation
+ [](Point p) { //
+ return std::make_pair(5.0f, 25.0f);
+ });
+
+ // Horizontal segment and points 5 pixels above and to the right of it
+ // on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 10},
+ // Starting point, delta, count ({20,5} through {30,5})
+ {20, 5}, {1, 0}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = (p.x - 20) * (p.x - 20) + 25;
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Vertical segment and points 5 pixels to the left and above the segment
+ // on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {10, 20},
+ // Starting point, delta, count ({5,0} through {5,10})
+ {5, 0}, {0, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = 25 + (10 - p.y) * (10 - p.y);
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Vertical segment and points 5 pixels directly to the left of the segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {10, 20},
+ // Starting point, delta, count ({5,11} through {5,19,})
+ {5, 11}, {0, 1}, 9,
+ // Distance computation
+ [](Point p) { //
+ return std::make_pair(5.0f, 25.0f);
+ });
+
+ // Vertical segment and points 5 pixels to the left and below the segment
+ // on the same line.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {10, 20},
+ // Starting point, delta, count ({20,5} through {30,5})
+ {5, 20}, {0, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = 25 + (p.y - 20) * (p.y - 20);
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Diagonal segment and points up and to the right of the top of the segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 20},
+ // Starting point, delta, count ({5,-5} through {15,5})
+ {5, -5}, {1, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = (p.x - 10) * (p.x - 10) + (p.y - 10) * (p.y - 10);
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Diagonal segment and points up and to the right of the segment itself.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 20},
+ // Starting point, delta, count ({15,5} through {24,14})
+ {15, 5}, {1, 1}, 9,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = 50.0f;
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Diagonal segment and points up and to the right of the bottom of the
+ // segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 20},
+ // Starting point, delta, count ({25,15} through {35,25})
+ {25, 15}, {1, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = (p.x - 20) * (p.x - 20) + (p.y - 20) * (p.y - 20);
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Diagonal segment and points down and to the left of the top of the segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 20},
+ // Starting point, delta, count ({-5,5} through {5,15})
+ {-5, 5}, {1, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = (p.x - 10) * (p.x - 10) + (p.y - 10) * (p.y - 10);
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Diagonal segment and points down and to the left of the segment itself.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 20},
+ // Starting point, delta, count ({5,15} through {14,24})
+ {5, 15}, {1, 1}, 9,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = 50.0f;
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+
+ // Diagonal segment and points down and to the left of the bottom of the
+ // segment.
+ TestPointToSegmentGroup(
+ // Segment
+ {10, 10}, {20, 20},
+ // Starting point, delta, count ({15,25} through {25,35})
+ {15, 25}, {1, 1}, 11,
+ // Distance computation
+ [](Point p) {
+ Scalar d_sq = (p.x - 20) * (p.x - 20) + (p.y - 20) * (p.y - 20);
+ return std::make_pair(std::sqrt(d_sq), d_sq);
+ });
+}
+
+TEST(PointTest, CrossProductThreePoints) {
+ // Colinear
+ EXPECT_FLOAT_EQ(Point::Cross(Point(-1, 0), Point(0, 0), Point(1, 0)), 0);
+ EXPECT_FLOAT_EQ(Point::Cross(Point(1, 0), Point(0, 0), Point(-1, 0)), 0);
+
+ // Right turn
+ EXPECT_FLOAT_EQ(Point::Cross(Point(-1, 0), Point(0, 0), Point(0, 1)), 1);
+ EXPECT_FLOAT_EQ(Point::Cross(Point(-2, 0), Point(0, 0), Point(0, 2)), 4);
+
+ // Left turn
+ EXPECT_FLOAT_EQ(Point::Cross(Point(-1, 0), Point(0, 0), Point(0, -1)), -1);
+ EXPECT_FLOAT_EQ(Point::Cross(Point(-2, 0), Point(0, 0), Point(0, -2)), -4);
+
+ // Convenient values for a less obvious left turn.
+ // p1 - p0 == (0, 0) - (3, -4) == (-3, 4)
+ // p2 - p0 == (1, 2) - (3, -4) == (-2, 6)
+ // product of the magnitude of the 2 legs and the sin of their angle
+ // (||(-3, 4)||) * (||(-2, 6)||) * sin(angle)
+ // 5 * sqrt(40) * sin(angle)
+ // angle = arcsin(4 / 5) - arcsin(6 / sqrt(40)) ~= -18.4349
+ // sin(angle) ~= -0.316227766
+ // 5 * sqrt(40) * sin(angle) == -10
+ // The math is cleaner with the cross product:
+ // (-3 * 6) - (-2 * 4) == -18 - -8 == -10
+ EXPECT_FLOAT_EQ(Point::Cross(Point(3, -4), Point(0, 0), Point(1, 2)), -10);
+}
+
+} // namespace testing
+} // namespace impeller
diff --git a/engine/src/flutter/impeller/tessellator/path_tessellator.cc b/engine/src/flutter/impeller/tessellator/path_tessellator.cc
index 0581a16..c67fc94 100644
--- a/engine/src/flutter/impeller/tessellator/path_tessellator.cc
+++ b/engine/src/flutter/impeller/tessellator/path_tessellator.cc
@@ -4,6 +4,7 @@
#include "flutter/impeller/tessellator/path_tessellator.h"
+#include "flutter/impeller/geometry/path_source.h"
#include "flutter/impeller/geometry/wangs_formula.h"
namespace {
@@ -313,4 +314,14 @@
pruner.PathEnd();
}
+void PathTessellator::PathToTransformedFilledVertices(const PathSource& source,
+ VertexWriter& writer,
+ const Matrix& matrix) {
+ PathFillWriter path_writer(writer, matrix.GetMaxBasisLengthXY());
+ PathPruner pruner(path_writer, false);
+ PathTransformer transformer(pruner, matrix);
+ source.Dispatch(transformer);
+ pruner.PathEnd();
+}
+
} // namespace impeller
diff --git a/engine/src/flutter/impeller/tessellator/path_tessellator.h b/engine/src/flutter/impeller/tessellator/path_tessellator.h
index 8b89f42..4c90a12 100644
--- a/engine/src/flutter/impeller/tessellator/path_tessellator.h
+++ b/engine/src/flutter/impeller/tessellator/path_tessellator.h
@@ -197,6 +197,10 @@
static void PathToFilledVertices(const PathSource& source,
VertexWriter& writer,
Scalar scale);
+
+ static void PathToTransformedFilledVertices(const PathSource& source,
+ VertexWriter& writer,
+ const Matrix& matrix);
};
} // namespace impeller
diff --git a/engine/src/flutter/impeller/tools/malioc.json b/engine/src/flutter/impeller/tools/malioc.json
index 7d35688..734fd06 100644
--- a/engine/src/flutter/impeller/tools/malioc.json
+++ b/engine/src/flutter/impeller/tools/malioc.json
@@ -6661,6 +6661,281 @@
}
}
},
+ "flutter/impeller/entity/gles/shadow_vertices.frag.gles": {
+ "Mali-G78": {
+ "core": "Mali-G78",
+ "filename": "flutter/impeller/entity/gles/shadow_vertices.frag.gles",
+ "has_side_effects": false,
+ "has_uniform_computation": false,
+ "modifies_coverage": false,
+ "reads_color_buffer": false,
+ "type": "Fragment",
+ "uses_late_zs_test": false,
+ "uses_late_zs_update": false,
+ "variants": {
+ "Main": {
+ "fp16_arithmetic": 0,
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "arith_total",
+ "arith_fma"
+ ],
+ "longest_path_cycles": [
+ 0.21875,
+ 0.21875,
+ 0.0625,
+ 0.0625,
+ 0.0,
+ 0.125,
+ 0.0
+ ],
+ "pipelines": [
+ "arith_total",
+ "arith_fma",
+ "arith_cvt",
+ "arith_sfu",
+ "load_store",
+ "varying",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "arith_total",
+ "arith_fma"
+ ],
+ "shortest_path_cycles": [
+ 0.21875,
+ 0.21875,
+ 0.03125,
+ 0.0625,
+ 0.0,
+ 0.125,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "arith_total",
+ "arith_fma"
+ ],
+ "total_cycles": [
+ 0.21875,
+ 0.21875,
+ 0.0625,
+ 0.0625,
+ 0.0,
+ 0.125,
+ 0.0
+ ]
+ },
+ "stack_spill_bytes": 0,
+ "thread_occupancy": 100,
+ "uniform_registers_used": 8,
+ "work_registers_used": 19
+ }
+ }
+ },
+ "Mali-T880": {
+ "core": "Mali-T880",
+ "filename": "flutter/impeller/entity/gles/shadow_vertices.frag.gles",
+ "has_uniform_computation": false,
+ "type": "Fragment",
+ "variants": {
+ "Main": {
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "arithmetic"
+ ],
+ "longest_path_cycles": [
+ 3.299999952316284,
+ 1.0,
+ 0.0
+ ],
+ "pipelines": [
+ "arithmetic",
+ "load_store",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "arithmetic"
+ ],
+ "shortest_path_cycles": [
+ 3.299999952316284,
+ 1.0,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "arithmetic"
+ ],
+ "total_cycles": [
+ 3.6666667461395264,
+ 1.0,
+ 0.0
+ ]
+ },
+ "thread_occupancy": 100,
+ "uniform_registers_used": 1,
+ "work_registers_used": 2
+ }
+ }
+ }
+ },
+ "flutter/impeller/entity/gles/shadow_vertices.vert.gles": {
+ "Mali-G78": {
+ "core": "Mali-G78",
+ "filename": "flutter/impeller/entity/gles/shadow_vertices.vert.gles",
+ "has_uniform_computation": false,
+ "type": "Vertex",
+ "variants": {
+ "Position": {
+ "fp16_arithmetic": 0,
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "longest_path_cycles": [
+ 0.140625,
+ 0.140625,
+ 0.0,
+ 0.0,
+ 2.0,
+ 0.0
+ ],
+ "pipelines": [
+ "arith_total",
+ "arith_fma",
+ "arith_cvt",
+ "arith_sfu",
+ "load_store",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "shortest_path_cycles": [
+ 0.140625,
+ 0.140625,
+ 0.0,
+ 0.0,
+ 2.0,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "load_store"
+ ],
+ "total_cycles": [
+ 0.140625,
+ 0.140625,
+ 0.0,
+ 0.0,
+ 2.0,
+ 0.0
+ ]
+ },
+ "stack_spill_bytes": 0,
+ "thread_occupancy": 100,
+ "uniform_registers_used": 20,
+ "work_registers_used": 32
+ },
+ "Varying": {
+ "fp16_arithmetic": null,
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "longest_path_cycles": [
+ 0.0,
+ 0.0,
+ 0.0,
+ 0.0,
+ 3.0,
+ 0.0
+ ],
+ "pipelines": [
+ "arith_total",
+ "arith_fma",
+ "arith_cvt",
+ "arith_sfu",
+ "load_store",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "shortest_path_cycles": [
+ 0.0,
+ 0.0,
+ 0.0,
+ 0.0,
+ 3.0,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "load_store"
+ ],
+ "total_cycles": [
+ 0.0,
+ 0.0,
+ 0.0,
+ 0.0,
+ 3.0,
+ 0.0
+ ]
+ },
+ "stack_spill_bytes": 0,
+ "thread_occupancy": 100,
+ "uniform_registers_used": 8,
+ "work_registers_used": 6
+ }
+ }
+ },
+ "Mali-T880": {
+ "core": "Mali-T880",
+ "filename": "flutter/impeller/entity/gles/shadow_vertices.vert.gles",
+ "has_uniform_computation": false,
+ "type": "Vertex",
+ "variants": {
+ "Main": {
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "longest_path_cycles": [
+ 2.640000104904175,
+ 5.0,
+ 0.0
+ ],
+ "pipelines": [
+ "arithmetic",
+ "load_store",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "shortest_path_cycles": [
+ 2.640000104904175,
+ 5.0,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "load_store"
+ ],
+ "total_cycles": [
+ 2.6666667461395264,
+ 5.0,
+ 0.0
+ ]
+ },
+ "thread_occupancy": 100,
+ "uniform_registers_used": 5,
+ "work_registers_used": 2
+ }
+ }
+ }
+ },
"flutter/impeller/entity/gles/solid_fill.frag.gles": {
"Mali-G78": {
"core": "Mali-G78",
@@ -10343,6 +10618,191 @@
}
}
},
+ "flutter/impeller/entity/shadow_vertices.frag.vkspv": {
+ "Mali-G78": {
+ "core": "Mali-G78",
+ "filename": "flutter/impeller/entity/shadow_vertices.frag.vkspv",
+ "has_side_effects": false,
+ "has_uniform_computation": true,
+ "modifies_coverage": false,
+ "reads_color_buffer": false,
+ "type": "Fragment",
+ "uses_late_zs_test": false,
+ "uses_late_zs_update": false,
+ "variants": {
+ "Main": {
+ "fp16_arithmetic": 0,
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "arith_total",
+ "arith_fma"
+ ],
+ "longest_path_cycles": [
+ 0.21875,
+ 0.21875,
+ 0.03125,
+ 0.0625,
+ 0.0,
+ 0.125,
+ 0.0
+ ],
+ "pipelines": [
+ "arith_total",
+ "arith_fma",
+ "arith_cvt",
+ "arith_sfu",
+ "load_store",
+ "varying",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "arith_total",
+ "arith_fma"
+ ],
+ "shortest_path_cycles": [
+ 0.21875,
+ 0.21875,
+ 0.03125,
+ 0.0625,
+ 0.0,
+ 0.125,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "arith_total",
+ "arith_fma"
+ ],
+ "total_cycles": [
+ 0.21875,
+ 0.21875,
+ 0.03125,
+ 0.0625,
+ 0.0,
+ 0.125,
+ 0.0
+ ]
+ },
+ "stack_spill_bytes": 0,
+ "thread_occupancy": 100,
+ "uniform_registers_used": 8,
+ "work_registers_used": 6
+ }
+ }
+ }
+ },
+ "flutter/impeller/entity/shadow_vertices.vert.vkspv": {
+ "Mali-G78": {
+ "core": "Mali-G78",
+ "filename": "flutter/impeller/entity/shadow_vertices.vert.vkspv",
+ "has_uniform_computation": true,
+ "type": "Vertex",
+ "variants": {
+ "Position": {
+ "fp16_arithmetic": 0,
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "longest_path_cycles": [
+ 0.125,
+ 0.125,
+ 0.0,
+ 0.0,
+ 2.0,
+ 0.0
+ ],
+ "pipelines": [
+ "arith_total",
+ "arith_fma",
+ "arith_cvt",
+ "arith_sfu",
+ "load_store",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "shortest_path_cycles": [
+ 0.125,
+ 0.125,
+ 0.0,
+ 0.0,
+ 2.0,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "load_store"
+ ],
+ "total_cycles": [
+ 0.125,
+ 0.125,
+ 0.0,
+ 0.0,
+ 2.0,
+ 0.0
+ ]
+ },
+ "stack_spill_bytes": 0,
+ "thread_occupancy": 100,
+ "uniform_registers_used": 28,
+ "work_registers_used": 32
+ },
+ "Varying": {
+ "fp16_arithmetic": null,
+ "has_stack_spilling": false,
+ "performance": {
+ "longest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "longest_path_cycles": [
+ 0.0,
+ 0.0,
+ 0.0,
+ 0.0,
+ 3.0,
+ 0.0
+ ],
+ "pipelines": [
+ "arith_total",
+ "arith_fma",
+ "arith_cvt",
+ "arith_sfu",
+ "load_store",
+ "texture"
+ ],
+ "shortest_path_bound_pipelines": [
+ "load_store"
+ ],
+ "shortest_path_cycles": [
+ 0.0,
+ 0.0,
+ 0.0,
+ 0.0,
+ 3.0,
+ 0.0
+ ],
+ "total_bound_pipelines": [
+ "load_store"
+ ],
+ "total_cycles": [
+ 0.0,
+ 0.0,
+ 0.0,
+ 0.0,
+ 3.0,
+ 0.0
+ ]
+ },
+ "stack_spill_bytes": 0,
+ "thread_occupancy": 100,
+ "uniform_registers_used": 20,
+ "work_registers_used": 6
+ }
+ }
+ }
+ },
"flutter/impeller/entity/solid_fill.frag.vkspv": {
"Mali-G78": {
"core": "Mali-G78",
