[Impeller] Simplify convex tessellation (#47957)
Removes usage of index buffer and adds zig-zagging triangle strip. Could also be adapted emplace directly into host
buffer.
Benchmark is https://flutter-engine-perf.skia.org/e/?queries=test%3DBM_Convex_rrect_convex
Umbrella issue: https://github.com/flutter/flutter/issues/138004
diff --git a/impeller/aiks/aiks_unittests.cc b/impeller/aiks/aiks_unittests.cc
index e937cc5..adf90b2 100644
--- a/impeller/aiks/aiks_unittests.cc
+++ b/impeller/aiks/aiks_unittests.cc
@@ -29,6 +29,7 @@
#include "impeller/geometry/constants.h"
#include "impeller/geometry/geometry_asserts.h"
#include "impeller/geometry/matrix.h"
+#include "impeller/geometry/path.h"
#include "impeller/geometry/path_builder.h"
#include "impeller/golden_tests/golden_playground_test.h"
#include "impeller/playground/widgets.h"
@@ -3492,6 +3493,26 @@
ASSERT_TRUE(OpenPlaygroundHere(canvas.EndRecordingAsPicture()));
}
+TEST_P(AiksTest, CanDrawMultiContourConvexPath) {
+ PathBuilder builder = {};
+ for (auto i = 0; i < 10; i++) {
+ if (i % 2 == 0) {
+ builder.AddCircle(Point(100 + 50 * i, 100 + 50 * i), 100);
+ } else {
+ builder.MoveTo({100.f + 50.f * i - 100, 100.f + 50.f * i});
+ builder.LineTo({100.f + 50.f * i, 100.f + 50.f * i - 100});
+ builder.LineTo({100.f + 50.f * i - 100, 100.f + 50.f * i - 100});
+ builder.Close();
+ }
+ }
+ builder.SetConvexity(Convexity::kConvex);
+
+ Canvas canvas;
+ canvas.DrawPath(builder.TakePath(), {.color = Color::Red().WithAlpha(0.4)});
+
+ ASSERT_TRUE(OpenPlaygroundHere(canvas.EndRecordingAsPicture()));
+}
+
TEST_P(AiksTest, CanCanvasDrawPictureWithBackdropFilter) {
Canvas subcanvas;
subcanvas.SaveLayer({}, {},
diff --git a/impeller/entity/geometry/fill_path_geometry.cc b/impeller/entity/geometry/fill_path_geometry.cc
index a734395..1e721cc 100644
--- a/impeller/entity/geometry/fill_path_geometry.cc
+++ b/impeller/entity/geometry/fill_path_geometry.cc
@@ -22,18 +22,16 @@
if (path_.GetFillType() == FillType::kNonZero && //
path_.IsConvex()) {
- auto [points, indices] = renderer.GetTessellator()->TessellateConvex(
+ auto points = renderer.GetTessellator()->TessellateConvex(
path_, entity.GetTransformation().GetMaxBasisLength());
vertex_buffer.vertex_buffer = host_buffer.Emplace(
points.data(), points.size() * sizeof(Point), alignof(Point));
- vertex_buffer.index_buffer = host_buffer.Emplace(
- indices.data(), indices.size() * sizeof(uint16_t), alignof(uint16_t));
- vertex_buffer.vertex_count = indices.size();
- vertex_buffer.index_type = IndexType::k16bit;
+ vertex_buffer.index_buffer = {}, vertex_buffer.vertex_count = points.size();
+ vertex_buffer.index_type = IndexType::kNone;
return GeometryResult{
- .type = PrimitiveType::kTriangle,
+ .type = PrimitiveType::kTriangleStrip,
.vertex_buffer = vertex_buffer,
.transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
entity.GetTransformation(),
@@ -86,24 +84,20 @@
if (path_.GetFillType() == FillType::kNonZero && //
path_.IsConvex()) {
- auto [points, indices] = renderer.GetTessellator()->TessellateConvex(
+ auto points = renderer.GetTessellator()->TessellateConvex(
path_, entity.GetTransformation().GetMaxBasisLength());
VertexBufferBuilder<VS::PerVertexData> vertex_builder;
vertex_builder.Reserve(points.size());
- vertex_builder.ReserveIndices(indices.size());
for (auto i = 0u; i < points.size(); i++) {
VS::PerVertexData data;
data.position = points[i];
data.texture_coords = uv_transform * points[i];
vertex_builder.AppendVertex(data);
}
- for (auto i = 0u; i < indices.size(); i++) {
- vertex_builder.AppendIndex(indices[i]);
- }
return GeometryResult{
- .type = PrimitiveType::kTriangle,
+ .type = PrimitiveType::kTriangleStrip,
.vertex_buffer =
vertex_builder.CreateVertexBuffer(pass.GetTransientsBuffer()),
.transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
diff --git a/impeller/geometry/geometry_benchmarks.cc b/impeller/geometry/geometry_benchmarks.cc
index 7f88021..c4801e0 100644
--- a/impeller/geometry/geometry_benchmarks.cc
+++ b/impeller/geometry/geometry_benchmarks.cc
@@ -74,9 +74,9 @@
auto points = std::make_unique<std::vector<Point>>();
points->reserve(2048);
while (state.KeepRunning()) {
- auto [points, index] = tess.TessellateConvex(path, 1.0f);
- single_point_count = index.size();
- point_count += index.size();
+ auto points = tess.TessellateConvex(path, 1.0f);
+ single_point_count = points.size();
+ point_count += points.size();
}
state.counters["SinglePointCount"] = single_point_count;
state.counters["TotalPointCount"] = point_count;
diff --git a/impeller/tessellator/tessellator.cc b/impeller/tessellator/tessellator.cc
index 15069a6..ec6b519 100644
--- a/impeller/tessellator/tessellator.cc
+++ b/impeller/tessellator/tessellator.cc
@@ -231,10 +231,9 @@
return Result::kSuccess;
}
-std::pair<std::vector<Point>, std::vector<uint16_t>>
-Tessellator::TessellateConvex(const Path& path, Scalar tolerance) {
+std::vector<Point> Tessellator::TessellateConvex(const Path& path,
+ Scalar tolerance) {
std::vector<Point> output;
- std::vector<uint16_t> indices;
point_buffer_->clear();
auto polyline =
@@ -243,29 +242,41 @@
point_buffer_ = std::move(point_buffer);
});
+ output.reserve(polyline.points->size() +
+ (4 * (polyline.contours.size() - 1)));
for (auto j = 0u; j < polyline.contours.size(); j++) {
auto [start, end] = polyline.GetContourPointBounds(j);
- auto center = polyline.GetPoint(start);
+ auto first_point = polyline.GetPoint(start);
// Some polygons will not self close and an additional triangle
// must be inserted, others will self close and we need to avoid
// inserting an extra triangle.
- if (polyline.GetPoint(end - 1) == polyline.GetPoint(start)) {
+ if (polyline.GetPoint(end - 1) == first_point) {
end--;
}
- output.emplace_back(center);
- output.emplace_back(polyline.GetPoint(start + 1));
- for (auto i = start + 2; i < end; i++) {
- const auto& point_b = polyline.GetPoint(i);
- output.emplace_back(point_b);
+ if (j > 0) {
+ // Triangle strip break.
+ output.emplace_back(output.back());
+ output.emplace_back(first_point);
+ output.emplace_back(first_point);
+ } else {
+ output.emplace_back(first_point);
+ }
- indices.emplace_back(0);
- indices.emplace_back(i - 1);
- indices.emplace_back(i);
+ size_t a = start + 1;
+ size_t b = end - 1;
+ while (a < b) {
+ output.emplace_back(polyline.GetPoint(a));
+ output.emplace_back(polyline.GetPoint(b));
+ a++;
+ b--;
+ }
+ if (a == b) {
+ output.emplace_back(polyline.GetPoint(a));
}
}
- return std::make_pair(output, indices);
+ return output;
}
void DestroyTessellator(TESStesselator* tessellator) {
diff --git a/impeller/tessellator/tessellator.h b/impeller/tessellator/tessellator.h
index 7733c25..958659a 100644
--- a/impeller/tessellator/tessellator.h
+++ b/impeller/tessellator/tessellator.h
@@ -84,12 +84,9 @@
/// Matrix::GetMaxBasisLength of the CTM applied to the
/// path for rendering.
///
- /// @return A point vector containing the vertices and a vector of indices
- /// into the point vector.
+ /// @return A point vector containing the vertices in triangle strip format.
///
- std::pair<std::vector<Point>, std::vector<uint16_t>> TessellateConvex(
- const Path& path,
- Scalar tolerance);
+ std::vector<Point> TessellateConvex(const Path& path, Scalar tolerance);
private:
/// Used for polyline generation.
diff --git a/impeller/tessellator/tessellator_unittests.cc b/impeller/tessellator/tessellator_unittests.cc
index 3ef6bd1..02e848e 100644
--- a/impeller/tessellator/tessellator_unittests.cc
+++ b/impeller/tessellator/tessellator_unittests.cc
@@ -129,34 +129,27 @@
{
Tessellator t;
// Sanity check simple rectangle.
- auto [pts, indices] = t.TessellateConvex(
+ auto pts = t.TessellateConvex(
PathBuilder{}.AddRect(Rect::MakeLTRB(0, 0, 10, 10)).TakePath(), 1.0);
std::vector<Point> expected = {
- {0, 0}, {10, 0}, {10, 10}, {0, 10}, //
+ {0, 0}, {10, 0}, {0, 10}, {10, 10}, //
};
- std::vector<uint16_t> expected_indices = {0, 1, 2, 0, 2, 3};
- ASSERT_EQ(pts, expected);
- ASSERT_EQ(indices, expected_indices);
+ EXPECT_EQ(pts, expected);
}
{
Tessellator t;
- auto [pts, indices] =
- t.TessellateConvex(PathBuilder{}
- .AddRect(Rect::MakeLTRB(0, 0, 10, 10))
- .AddRect(Rect::MakeLTRB(20, 20, 30, 30))
- .TakePath(),
- 1.0);
+ auto pts = t.TessellateConvex(PathBuilder{}
+ .AddRect(Rect::MakeLTRB(0, 0, 10, 10))
+ .AddRect(Rect::MakeLTRB(20, 20, 30, 30))
+ .TakePath(),
+ 1.0);
- std::vector<Point> expected = {
- {0, 0}, {10, 0}, {10, 10}, {0, 10}, //
- {20, 20}, {30, 20}, {30, 30}, {20, 30} //
- };
- std::vector<uint16_t> expected_indices = {0, 1, 2, 0, 2, 3,
- 0, 6, 7, 0, 7, 8};
- ASSERT_EQ(pts, expected);
- ASSERT_EQ(indices, expected_indices);
+ std::vector<Point> expected = {{0, 0}, {10, 0}, {0, 10}, {10, 10},
+ {10, 10}, {20, 20}, {20, 20}, {30, 20},
+ {20, 30}, {30, 30}};
+ EXPECT_EQ(pts, expected);
}
}
