Skip to content

Instantly share code, notes, and snippets.

@dnfield

dnfield/polyline_opt.diff

Last active October 13, 2022 23:00
Show Gist options
  • Save dnfield/182fed97bf5dd092a0e6ef43af1d3207 to your computer and use it in GitHub Desktop.
Save dnfield/182fed97bf5dd092a0e6ef43af1d3207 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
polyline_opt.diff
diff --git a/impeller/entity/contents/clip_contents.cc b/impeller/entity/contents/clip_contents.cc
index 2497e4daa9..a7ba8e6ec7 100644
--- a/impeller/entity/contents/clip_contents.cc
+++ b/impeller/entity/contents/clip_contents.cc
@@ -121,7 +121,8 @@ bool ClipContents::Render(const ContentContext& renderer,
auto allocator = renderer.GetContext()->GetResourceAllocator();
auto geometry_result = geometry_->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.BindVertices(geometry_result.vertex_buffer);
cmd.primitive_type = geometry_result.type;
info.mvp = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
diff --git a/impeller/entity/contents/linear_gradient_contents.cc b/impeller/entity/contents/linear_gradient_contents.cc
index eef7c5d42f..1b4d3a77e4 100644
--- a/impeller/entity/contents/linear_gradient_contents.cc
+++ b/impeller/entity/contents/linear_gradient_contents.cc
@@ -80,7 +80,8 @@ bool LinearGradientContents::Render(const ContentContext& renderer,
auto allocator = renderer.GetContext()->GetResourceAllocator();
auto geometry_result = GetGeometry()->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.BindVertices(geometry_result.vertex_buffer);
cmd.primitive_type = geometry_result.type;
FS::BindGradientInfo(
diff --git a/impeller/entity/contents/radial_gradient_contents.cc b/impeller/entity/contents/radial_gradient_contents.cc
index e674ebce19..65352a56ce 100644
--- a/impeller/entity/contents/radial_gradient_contents.cc
+++ b/impeller/entity/contents/radial_gradient_contents.cc
@@ -79,7 +79,8 @@ bool RadialGradientContents::Render(const ContentContext& renderer,
auto allocator = renderer.GetContext()->GetResourceAllocator();
auto geometry_result = GetGeometry()->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.BindVertices(geometry_result.vertex_buffer);
cmd.primitive_type = geometry_result.type;
FS::BindGradientInfo(
diff --git a/impeller/entity/contents/solid_color_contents.cc b/impeller/entity/contents/solid_color_contents.cc
index bae283cb42..e16dc54b8d 100644
--- a/impeller/entity/contents/solid_color_contents.cc
+++ b/impeller/entity/contents/solid_color_contents.cc
@@ -63,7 +63,8 @@ bool SolidColorContents::Render(const ContentContext& renderer,
auto allocator = renderer.GetContext()->GetResourceAllocator();
auto geometry_result = geometry_->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.BindVertices(geometry_result.vertex_buffer);
cmd.primitive_type = geometry_result.type;
diff --git a/impeller/entity/contents/solid_stroke_contents.cc b/impeller/entity/contents/solid_stroke_contents.cc
index 8ff982c667..bf66c5e2a5 100644
--- a/impeller/entity/contents/solid_stroke_contents.cc
+++ b/impeller/entity/contents/solid_stroke_contents.cc
@@ -72,7 +72,7 @@ static VertexBuffer CreateSolidStrokeVertices(
const SolidStrokeContents::CapProc& cap_proc,
const SolidStrokeContents::JoinProc& join_proc,
Scalar miter_limit,
- const SmoothingApproximation& smoothing) {
+ Scalar tolerance) {
using VS = SolidFillVertexShader;
VertexBufferBuilder<VS::PerVertexData> vtx_builder;
@@ -101,8 +101,8 @@ static VertexBuffer CreateSolidStrokeVertices(
switch (contour_end_point_i - contour_start_point_i) {
case 1: {
Point p = polyline.points[contour_start_point_i];
- cap_proc(vtx_builder, p, {-stroke_width * 0.5f, 0}, smoothing);
- cap_proc(vtx_builder, p, {stroke_width * 0.5f, 0}, smoothing);
+ cap_proc(vtx_builder, p, {-stroke_width * 0.5f, 0}, tolerance);
+ cap_proc(vtx_builder, p, {stroke_width * 0.5f, 0}, tolerance);
continue;
}
case 0:
@@ -140,7 +140,7 @@ static VertexBuffer CreateSolidStrokeVertices(
// Generate start cap.
if (!polyline.contours[contour_i].is_closed) {
cap_proc(vtx_builder, polyline.points[contour_start_point_i], -offset,
- smoothing);
+ tolerance);
}
// Generate contour geometry.
@@ -162,7 +162,7 @@ static VertexBuffer CreateSolidStrokeVertices(
// Generate join from the current line to the next line.
join_proc(vtx_builder, polyline.points[point_i], previous_offset,
- offset, miter_limit, smoothing);
+ offset, miter_limit, tolerance);
}
}
}
@@ -170,10 +170,10 @@ static VertexBuffer CreateSolidStrokeVertices(
// Generate end cap or join.
if (!polyline.contours[contour_i].is_closed) {
cap_proc(vtx_builder, polyline.points[contour_end_point_i - 1], offset,
- smoothing);
+ tolerance);
} else {
join_proc(vtx_builder, polyline.points[contour_start_point_i], offset,
- contour_first_offset, miter_limit, smoothing);
+ contour_first_offset, miter_limit, tolerance);
}
}
@@ -209,15 +209,15 @@ bool SolidStrokeContents::Render(const ContentContext& renderer,
cmd.pipeline = renderer.GetSolidFillPipeline(options);
cmd.stencil_reference = entity.GetStencilDepth();
- auto smoothing = SmoothingApproximation(
- 60.0 / (stroke_size_ * entity.GetTransformation().GetMaxBasisLength()),
- 0.0, 0.0);
+ auto tolerance =
+ kDefaultCurveTolerance /
+ (stroke_size_ * entity.GetTransformation().GetMaxBasisLength());
Scalar min_size = 1.0f / sqrt(std::abs(determinant));
Scalar stroke_width = std::max(stroke_size_, min_size);
cmd.BindVertices(CreateSolidStrokeVertices(
path_, pass.GetTransientsBuffer(), stroke_width, cap_proc_, join_proc_,
- miter_limit_ * stroke_width * 0.5, smoothing));
+ miter_limit_ * stroke_width * 0.5, tolerance));
VS::BindVertInfo(cmd, pass.GetTransientsBuffer().EmplaceUniform(vert_info));
FS::BindFragInfo(cmd, pass.GetTransientsBuffer().EmplaceUniform(frag_info));
@@ -256,12 +256,12 @@ void SolidStrokeContents::SetStrokeCap(Cap cap) {
case Cap::kButt:
cap_proc_ = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position, const Point& offset,
- const SmoothingApproximation& smoothing) {};
+ Scalar tolerance) {};
break;
case Cap::kRound:
cap_proc_ = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position, const Point& offset,
- const SmoothingApproximation& smoothing) {
+ Scalar tolerance) {
VS::PerVertexData vtx;
Point forward(offset.y, -offset.x);
@@ -271,7 +271,7 @@ void SolidStrokeContents::SetStrokeCap(Cap cap) {
CubicPathComponent(
offset, offset + forward * PathBuilder::kArcApproximationMagic,
forward + offset * PathBuilder::kArcApproximationMagic, forward)
- .CreatePolyline(smoothing);
+ .CreatePolyline(tolerance);
vtx.position = position + offset;
vtx_builder.AppendVertex(vtx);
@@ -288,7 +288,7 @@ void SolidStrokeContents::SetStrokeCap(Cap cap) {
case Cap::kSquare:
cap_proc_ = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position, const Point& offset,
- const SmoothingApproximation& smoothing) {
+ Scalar tolerance) {
VS::PerVertexData vtx;
vtx.position = position;
@@ -337,7 +337,7 @@ void SolidStrokeContents::SetStrokeJoin(Join join) {
join_proc_ = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position, const Point& start_offset,
const Point& end_offset, Scalar miter_limit,
- const SmoothingApproximation& smoothing) {
+ Scalar tolerance) {
CreateBevelAndGetDirection(vtx_builder, position, start_offset,
end_offset);
};
@@ -346,7 +346,7 @@ void SolidStrokeContents::SetStrokeJoin(Join join) {
join_proc_ = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position, const Point& start_offset,
const Point& end_offset, Scalar miter_limit,
- const SmoothingApproximation& smoothing) {
+ Scalar tolerance) {
Point start_normal = start_offset.Normalize();
Point end_normal = end_offset.Normalize();
@@ -375,7 +375,7 @@ void SolidStrokeContents::SetStrokeJoin(Join join) {
join_proc_ = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position, const Point& start_offset,
const Point& end_offset, Scalar miter_limit,
- const SmoothingApproximation& smoothing) {
+ Scalar tolerance) {
Point start_normal = start_offset.Normalize();
Point end_normal = end_offset.Normalize();
@@ -402,7 +402,7 @@ void SolidStrokeContents::SetStrokeJoin(Join join) {
auto arc_points = CubicPathComponent(start_offset, start_handle,
middle_handle, middle)
- .CreatePolyline(smoothing);
+ .CreatePolyline(tolerance);
VS::PerVertexData vtx;
for (const auto& point : arc_points) {
diff --git a/impeller/entity/contents/solid_stroke_contents.h b/impeller/entity/contents/solid_stroke_contents.h
index 526d0d3c7d..101daf616e 100644
--- a/impeller/entity/contents/solid_stroke_contents.h
+++ b/impeller/entity/contents/solid_stroke_contents.h
@@ -40,14 +40,14 @@ class SolidStrokeContents final : public Contents {
std::function<void(VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position,
const Point& offset,
- const SmoothingApproximation& smoothing)>;
+ Scalar tolerance)>;
using JoinProc =
std::function<void(VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
const Point& position,
const Point& start_offset,
const Point& end_offset,
Scalar miter_limit,
- const SmoothingApproximation& smoothing)>;
+ Scalar tolerance)>;
SolidStrokeContents();
diff --git a/impeller/entity/contents/sweep_gradient_contents.cc b/impeller/entity/contents/sweep_gradient_contents.cc
index 2371b6ecfc..921c8fc967 100644
--- a/impeller/entity/contents/sweep_gradient_contents.cc
+++ b/impeller/entity/contents/sweep_gradient_contents.cc
@@ -85,7 +85,8 @@ bool SweepGradientContents::Render(const ContentContext& renderer,
auto allocator = renderer.GetContext()->GetResourceAllocator();
auto geometry_result = GetGeometry()->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.BindVertices(geometry_result.vertex_buffer);
cmd.primitive_type = geometry_result.type;
FS::BindGradientInfo(
diff --git a/impeller/entity/contents/tiled_texture_contents.cc b/impeller/entity/contents/tiled_texture_contents.cc
index 58a535f7c3..18c4691dac 100644
--- a/impeller/entity/contents/tiled_texture_contents.cc
+++ b/impeller/entity/contents/tiled_texture_contents.cc
@@ -70,7 +70,8 @@ bool TiledTextureContents::Render(const ContentContext& renderer,
auto allocator = renderer.GetContext()->GetResourceAllocator();
auto geometry_result = GetGeometry()->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.BindVertices(geometry_result.vertex_buffer);
cmd.primitive_type = geometry_result.type;
VS::BindVertInfo(cmd, host_buffer.EmplaceUniform(vert_info));
diff --git a/impeller/entity/contents/vertices_contents.cc b/impeller/entity/contents/vertices_contents.cc
index 31f1f48c53..e1a2f50fe9 100644
--- a/impeller/entity/contents/vertices_contents.cc
+++ b/impeller/entity/contents/vertices_contents.cc
@@ -72,7 +72,8 @@ bool VerticesContents::Render(const ContentContext& renderer,
auto geometry_result = geometry_->GetPositionBuffer(
allocator, host_buffer, renderer.GetTessellator(),
- pass.GetRenderTargetSize());
+ pass.GetRenderTargetSize(),
+ entity.GetTransformation().GetMaxBasisLength());
cmd.pipeline = renderer.GetGeometryPositionPipeline(
OptionsFromPassAndEntity(pass, entity));
cmd.primitive_type = geometry_result.type;
diff --git a/impeller/entity/geometry.cc b/impeller/entity/geometry.cc
index 5cbaf2707e..000872f30b 100644
--- a/impeller/entity/geometry.cc
+++ b/impeller/entity/geometry.cc
@@ -48,7 +48,8 @@ GeometryResult VerticesGeometry::GetPositionBuffer(
std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) {
+ ISize render_target_size,
+ Scalar max_basis_length) {
if (!vertices_.IsValid()) {
return {};
}
@@ -182,10 +183,12 @@ GeometryResult PathGeometry::GetPositionBuffer(
std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) {
+ ISize render_target_size,
+ Scalar max_basis_length) {
VertexBuffer vertex_buffer;
auto tesselation_result = tessellator->TessellateBuilder(
- path_.GetFillType(), path_.CreatePolyline(),
+ path_.GetFillType(),
+ path_.CreatePolyline(kDefaultCurveTolerance / max_basis_length),
[&vertex_buffer, &host_buffer](
const float* vertices, size_t vertices_count, const uint16_t* indices,
size_t indices_count) {
@@ -244,7 +247,8 @@ GeometryResult CoverGeometry::GetPositionBuffer(
std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) {
+ ISize render_target_size,
+ Scalar max_basis_length) {
auto rect = Rect(Size(render_target_size));
constexpr uint16_t kRectIndicies[4] = {0, 1, 2, 3};
return GeometryResult{
diff --git a/impeller/entity/geometry.h b/impeller/entity/geometry.h
index 293140d2a2..666da614f6 100644
--- a/impeller/entity/geometry.h
+++ b/impeller/entity/geometry.h
@@ -43,7 +43,8 @@ class Geometry {
std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) = 0;
+ ISize render_target_size,
+ Scalar max_basis_length) = 0;
virtual GeometryResult GetPositionColorBuffer(
std::shared_ptr<Allocator> device_allocator,
@@ -75,7 +76,8 @@ class VerticesGeometry : public Geometry {
GeometryResult GetPositionBuffer(std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) override;
+ ISize render_target_size,
+ Scalar max_basis_length) override;
// |Geometry|
GeometryResult GetPositionColorBuffer(
@@ -115,7 +117,8 @@ class PathGeometry : public Geometry {
GeometryResult GetPositionBuffer(std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) override;
+ ISize render_target_size,
+ Scalar max_basis_length) override;
// |Geometry|
GeometryResult GetPositionColorBuffer(
@@ -156,7 +159,8 @@ class CoverGeometry : public Geometry {
GeometryResult GetPositionBuffer(std::shared_ptr<Allocator> device_allocator,
HostBuffer& host_buffer,
std::shared_ptr<Tessellator> tessellator,
- ISize render_target_size) override;
+ ISize render_target_size,
+ Scalar max_basis_length) override;
// |Geometry|
GeometryResult GetPositionColorBuffer(
diff --git a/impeller/geometry/BUILD.gn b/impeller/geometry/BUILD.gn
index f3bdf11b26..e8d518950b 100644
--- a/impeller/geometry/BUILD.gn
+++ b/impeller/geometry/BUILD.gn
@@ -63,6 +63,7 @@ executable("geometry_benchmarks") {
sources = [ "geometry_benchmarks.cc" ]
deps = [
":geometry",
+ "../tessellator",
"//flutter/benchmarking",
]
}
diff --git a/impeller/geometry/geometry_benchmarks.cc b/impeller/geometry/geometry_benchmarks.cc
index 8d612d9d05..622847ae1b 100644
--- a/impeller/geometry/geometry_benchmarks.cc
+++ b/impeller/geometry/geometry_benchmarks.cc
@@ -6,6 +6,7 @@
#include "impeller/geometry/path.h"
#include "impeller/geometry/path_builder.h"
+#include "impeller/tessellator/tessellator.h"
namespace impeller {
@@ -232,9 +233,18 @@ static void BM_ManyCubicPolyline(benchmark::State& state) {
.TakePath();
size_t point_count = 0u;
size_t single_point_count = 0u;
+<<<<<<< HEAD
+ Tessellator tess;
+ while (state.KeepRunning()) {
+ auto polyline = path.CreatePolyline();
+ single_point_count = polyline.points.size();
+ point_count += single_point_count;
+ tess.Tessellate(FillType::kNonZero, polyline, [](Point) {});
+=======
while (state.KeepRunning()) {
single_point_count = path.CreatePolyline().points.size();
point_count += single_point_count;
+>>>>>>> upstream/main
}
state.counters["SinglePointCount"] = single_point_count;
state.counters["TotalPointCount"] = point_count;
@@ -373,9 +383,18 @@ static void BM_ManyQuadPolyline(benchmark::State& state) {
.TakePath();
size_t point_count = 0u;
size_t single_point_count = 0u;
+<<<<<<< HEAD
+ Tessellator tess;
+ while (state.KeepRunning()) {
+ auto polyline = path.CreatePolyline();
+ single_point_count = polyline.points.size();
+ point_count += single_point_count;
+ tess.Tessellate(FillType::kNonZero, polyline, [](Point) {});
+=======
while (state.KeepRunning()) {
single_point_count = path.CreatePolyline().points.size();
point_count += single_point_count;
+>>>>>>> upstream/main
}
state.counters["SinglePointCount"] = single_point_count;
state.counters["TotalPointCount"] = point_count;
diff --git a/impeller/geometry/geometry_unittests.cc b/impeller/geometry/geometry_unittests.cc
index a199c689d7..0a227cb2e9 100644
--- a/impeller/geometry/geometry_unittests.cc
+++ b/impeller/geometry/geometry_unittests.cc
@@ -17,6 +17,7 @@
#include "impeller/geometry/rect.h"
#include "impeller/geometry/scalar.h"
#include "impeller/geometry/size.h"
+#include "path_component.h"
namespace impeller {
namespace testing {
@@ -1426,8 +1427,7 @@ TEST(GeometryTest, RectGetPositive) {
TEST(GeometryTest, CubicPathComponentPolylineDoesNotIncludePointOne) {
CubicPathComponent component({10, 10}, {20, 35}, {35, 20}, {40, 40});
- SmoothingApproximation approximation;
- auto polyline = component.CreatePolyline(approximation);
+ auto polyline = component.CreatePolyline();
ASSERT_NE(polyline.front().x, 10);
ASSERT_NE(polyline.front().y, 10);
ASSERT_EQ(polyline.back().x, 40);
@@ -1713,5 +1713,135 @@ TEST(GeometryTest, Gradient) {
}
}
+static void LogPoint(Point p, bool comma) {
+ if (comma) {
+ std::cout << "{x: " << p.x << ", y: " << p.y << "}," << std::endl;
+ } else {
+ std::cout << "{x: " << p.x << ", y: " << p.y << "}" << std::endl;
+ }
+}
+
+static Scalar ApproximateParabolaIntegral(Scalar x) {
+ constexpr Scalar d = 0.67;
+ return x / (1.0 - d + sqrt(sqrt(pow(d, 4) + 0.25 * x * x)));
+}
+
+static std::vector<Point> CreateQuadPolyline(
+ const QuadraticPathComponent& component) {
+ auto tolerance = .1f;
+ auto sqrt_tol = sqrt(tolerance);
+
+ auto d01 = component.cp - component.p1;
+ auto d12 = component.p2 - component.cp;
+ auto dd = d01 - d12;
+ auto cross = (component.p2 - component.p1).Cross(dd);
+ auto x0 = d01.Dot(dd) * 1 / cross;
+ auto x2 = d12.Dot(dd) * 1 / cross;
+ auto scale = abs(cross / (hypot(dd.x, dd.y) * (x2 - x0)));
+
+ auto a0 = ApproximateParabolaIntegral(x0);
+ auto a2 = ApproximateParabolaIntegral(x2);
+ Scalar val = 0.f;
+ if (isfinite(scale)) {
+ auto da = abs(a2 - a0);
+ auto sqrt_scale = sqrt(scale);
+ if ((x0 < 0 && x2 < 0) || (x0 >= 0 && x2 >= 0)) {
+ val = da * sqrt_scale;
+ } else {
+ // cusp case
+ auto xmin = sqrt_tol / sqrt_scale;
+ val = sqrt_tol * da / ApproximateParabolaIntegral(xmin);
+ }
+ }
+ auto u0 = ApproximateParabolaIntegral(a0);
+ auto u2 = ApproximateParabolaIntegral(a2);
+ auto uscale = 1 / (u2 - u0);
+
+ auto line_count = ceil(0.5 * val / sqrt_tol);
+ auto step = 1 / line_count;
+ FML_LOG(ERROR) << "Line count: " << line_count;
+ for (size_t i = 1; i < line_count; i += 1) {
+ auto u = i * step;
+ auto a = a0 + (a2 - a0) * u;
+ auto t = (ApproximateParabolaIntegral(a) - u0) * uscale;
+ LogPoint(component.Solve(t), true);
+ }
+ LogPoint(component.p2, false);
+
+ return {};
+}
+
+static std::vector<Point> CreateCubicPolyline(
+ const CubicPathComponent& component) {
+ FML_LOG(ERROR) << "New";
+
+ Scalar t = 0;
+
+ CubicPathComponent current_component = component;
+ int count = 0;
+ while (t < 1.0) {
+ count += 1;
+
+ auto v1 = current_component.cp1 - current_component.p1;
+ auto v2 = current_component.cp2 - current_component.p1;
+
+ auto s = abs(v2.Cross(v1) / hypot(v1.x, v1.y));
+
+ if (s < kEhCloseEnough) {
+ break;
+ }
+
+ constexpr Scalar f = 0.005;
+ t = 2 * sqrt(f / (3.f * s));
+
+ // P'1
+ auto ab = current_component.p1 +
+ t * (current_component.cp1 - current_component.p1);
+ // P'2
+ auto bc = current_component.cp1 +
+ t * (current_component.cp2 - current_component.cp1);
+ // P'3
+ auto cd = current_component.cp2 +
+ t * (current_component.p2 - current_component.cp2);
+
+ // P''1
+ auto abc = ab + t * (bc - ab);
+ // P''2
+ auto bcd = bc + t * (cd - bc);
+
+ // P'''1
+ auto abcd = abc + t * (bcd - abc);
+
+ current_component = {abcd, bcd, cd, current_component.p2};
+ LogPoint(abcd, true);
+ }
+ LogPoint(component.p2, false);
+ FML_LOG(ERROR) << count;
+ return {};
+}
+
+TEST(GeometryTest, NewPolylineAlgo) {
+ // CubicPathComponent component({10, 10}, {25, 12}, {40, 15}, {38, 24});
+ CubicPathComponent component({100, 100}, {300, 200}, {200, 200}, {200, 100});
+ auto points = component.CreatePolyline();
+ LogPoint({100, 100}, true);
+ for (auto point : points) {
+ LogPoint(point, point != points.back());
+ }
+ FML_LOG(ERROR) << points.size();
+ CreateCubicPolyline(component);
+}
+
+TEST(GeometryTest, NewQuadPolylineAlgo) {
+ QuadraticPathComponent component({100, 100}, {300, 200}, {200, 100});
+ auto points = component.CreatePolyline();
+ // LogPoint({100, 100}, true);
+ for (auto point : points) {
+ LogPoint(point, point != points.back());
+ }
+ FML_LOG(ERROR) << points.size();
+ CreateQuadPolyline(component);
+}
+
} // namespace testing
} // namespace impeller
diff --git a/impeller/geometry/path.cc b/impeller/geometry/path.cc
index 7e632d7287..6b2ecf847b 100644
--- a/impeller/geometry/path.cc
+++ b/impeller/geometry/path.cc
@@ -221,8 +221,7 @@ bool Path::UpdateContourComponentAtIndex(size_t index,
return true;
}
-Path::Polyline Path::CreatePolyline(
- const SmoothingApproximation& approximation) const {
+Path::Polyline Path::CreatePolyline(Scalar tolerance) const {
Polyline polyline;
std::optional<Point> previous_contour_point;
@@ -251,10 +250,10 @@ Path::Polyline Path::CreatePolyline(
collect_points(linears_[component.index].CreatePolyline());
break;
case ComponentType::kQuadratic:
- collect_points(quads_[component.index].CreatePolyline(approximation));
+ collect_points(quads_[component.index].CreatePolyline(tolerance));
break;
case ComponentType::kCubic:
- collect_points(cubics_[component.index].CreatePolyline(approximation));
+ collect_points(cubics_[component.index].CreatePolyline(tolerance));
break;
case ComponentType::kContour:
if (component_i == components_.size() - 1) {
diff --git a/impeller/geometry/path.h b/impeller/geometry/path.h
index 77a20fda0e..22879e5de3 100644
--- a/impeller/geometry/path.h
+++ b/impeller/geometry/path.h
@@ -117,8 +117,7 @@ class Path {
bool UpdateContourComponentAtIndex(size_t index,
const ContourComponent& contour);
- Polyline CreatePolyline(
- const SmoothingApproximation& approximation = {}) const;
+ Polyline CreatePolyline(Scalar tolerance = kDefaultCurveTolerance) const;
std::optional<Rect> GetBoundingBox() const;
diff --git a/impeller/geometry/path_component.cc b/impeller/geometry/path_component.cc
index f9c208386e..92eb1f6d1d 100644
--- a/impeller/geometry/path_component.cc
+++ b/impeller/geometry/path_component.cc
@@ -8,10 +8,6 @@
namespace impeller {
-static const size_t kRecursionLimit = 32;
-static const Scalar kCurveCollinearityEpsilon = 1e-30;
-static const Scalar kCurveAngleToleranceEpsilon = 0.01;
-
/*
* Based on: https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Specific_cases
*/
@@ -85,10 +81,57 @@ Point QuadraticPathComponent::SolveDerivative(Scalar time) const {
};
}
+static Scalar ApproximateParabolaIntegral(Scalar x) {
+ constexpr Scalar d = 0.67;
+ return x / (1.0 - d + sqrt(sqrt(pow(d, 4) + 0.25 * x * x)));
+}
+
std::vector<Point> QuadraticPathComponent::CreatePolyline(
- const SmoothingApproximation& approximation) const {
- CubicPathComponent elevated(*this);
- return elevated.CreatePolyline(approximation);
+ Scalar tolerance) const {
+ std::vector<Point> points;
+ FillPointsForPolyline(points, tolerance);
+ return points;
+}
+
+void QuadraticPathComponent::FillPointsForPolyline(std::vector<Point>& points,
+ Scalar tolerance) const {
+ auto sqrt_tolerance = sqrt(tolerance);
+
+ auto d01 = cp - p1;
+ auto d12 = p2 - cp;
+ auto dd = d01 - d12;
+ auto cross = (p2 - p1).Cross(dd);
+ auto x0 = d01.Dot(dd) * 1 / cross;
+ auto x2 = d12.Dot(dd) * 1 / cross;
+ auto scale = abs(cross / (hypot(dd.x, dd.y) * (x2 - x0)));
+
+ auto a0 = ApproximateParabolaIntegral(x0);
+ auto a2 = ApproximateParabolaIntegral(x2);
+ Scalar val = 0.f;
+ if (isfinite(scale)) {
+ auto da = abs(a2 - a0);
+ auto sqrt_scale = sqrt(scale);
+ if ((x0 < 0 && x2 < 0) || (x0 >= 0 && x2 >= 0)) {
+ val = da * sqrt_scale;
+ } else {
+ // cusp case
+ auto xmin = sqrt_tolerance / sqrt_scale;
+ val = sqrt_tolerance * da / ApproximateParabolaIntegral(xmin);
+ }
+ }
+ auto u0 = ApproximateParabolaIntegral(a0);
+ auto u2 = ApproximateParabolaIntegral(a2);
+ auto uscale = 1 / (u2 - u0);
+
+ auto line_count = std::max(1., ceil(0.5 * val / sqrt_tolerance));
+ auto step = 1 / line_count;
+ for (size_t i = 1; i < line_count; i += 1) {
+ auto u = i * step;
+ auto a = a0 + (a2 - a0) * u;
+ auto t = (ApproximateParabolaIntegral(a) - u0) * uscale;
+ points.emplace_back(Solve(t));
+ }
+ points.emplace_back(p2);
}
std::vector<Point> QuadraticPathComponent::Extrema() const {
@@ -110,238 +153,61 @@ Point CubicPathComponent::SolveDerivative(Scalar time) const {
};
}
-/*
- * Paul de Casteljau's subdivision with modifications as described in
- * http://agg.sourceforge.net/antigrain.com/research/adaptive_bezier/index.html.
- * Refer to the diagram on that page for a description of the points.
- */
-static void CubicPathSmoothenRecursive(const SmoothingApproximation& approx,
- std::vector<Point>& points,
- Point p1,
- Point p2,
- Point p3,
- Point p4,
- size_t level) {
- if (level >= kRecursionLimit) {
- return;
+std::vector<Point> CubicPathComponent::CreatePolyline(Scalar tolerance) const {
+ auto quads = ToQuadratics(.1);
+ std::vector<Point> points;
+ for (const auto& quad : quads) {
+ quad.FillPointsForPolyline(points, tolerance);
}
+ return points;
+}
- /*
- * Find all midpoints.
- */
- auto p12 = (p1 + p2) / 2.0;
- auto p23 = (p2 + p3) / 2.0;
- auto p34 = (p3 + p4) / 2.0;
-
- auto p123 = (p12 + p23) / 2.0;
- auto p234 = (p23 + p34) / 2.0;
-
- auto p1234 = (p123 + p234) / 2.0;
-
- /*
- * Attempt approximation using single straight line.
- */
- auto d = p4 - p1;
- Scalar d2 = fabs(((p2.x - p4.x) * d.y - (p2.y - p4.y) * d.x));
- Scalar d3 = fabs(((p3.x - p4.x) * d.y - (p3.y - p4.y) * d.x));
-
- Scalar da1 = 0;
- Scalar da2 = 0;
- Scalar k = 0;
-
- switch ((static_cast<int>(d2 > kCurveCollinearityEpsilon) << 1) +
- static_cast<int>(d3 > kCurveCollinearityEpsilon)) {
- case 0:
- /*
- * All collinear OR p1 == p4.
- */
- k = d.x * d.x + d.y * d.y;
- if (k == 0) {
- d2 = p1.GetDistanceSquared(p2);
- d3 = p4.GetDistanceSquared(p3);
- } else {
- k = 1.0 / k;
- da1 = p2.x - p1.x;
- da2 = p2.y - p1.y;
- d2 = k * (da1 * d.x + da2 * d.y);
- da1 = p3.x - p1.x;
- da2 = p3.y - p1.y;
- d3 = k * (da1 * d.x + da2 * d.y);
-
- if (d2 > 0 && d2 < 1 && d3 > 0 && d3 < 1) {
- /*
- * Simple collinear case, 1---2---3---4. Leave just two endpoints.
- */
- return;
- }
-
- if (d2 <= 0) {
- d2 = p2.GetDistanceSquared(p1);
- } else if (d2 >= 1) {
- d2 = p2.GetDistanceSquared(p4);
- } else {
- d2 = p2.GetDistanceSquared({p1.x + d2 * d.x, p1.y + d2 * d.y});
- }
-
- if (d3 <= 0) {
- d3 = p3.GetDistanceSquared(p1);
- } else if (d3 >= 1) {
- d3 = p3.GetDistanceSquared(p4);
- } else {
- d3 = p3.GetDistanceSquared({p1.x + d3 * d.x, p1.y + d3 * d.y});
- }
- }
-
- if (d2 > d3) {
- if (d2 < approx.distance_tolerance_square) {
- points.emplace_back(p2);
- return;
- }
- } else {
- if (d3 < approx.distance_tolerance_square) {
- points.emplace_back(p3);
- return;
- }
- }
- break;
- case 1:
- /*
- * p1, p2, p4 are collinear, p3 is significant.
- */
- if (d3 * d3 <=
- approx.distance_tolerance_square * (d.x * d.x + d.y * d.y)) {
- if (approx.angle_tolerance < kCurveAngleToleranceEpsilon) {
- points.emplace_back(p23);
- return;
- }
-
- /*
- * Angle Condition.
- */
- da1 = ::fabs(::atan2(p4.y - p3.y, p4.x - p3.x) -
- ::atan2(p3.y - p2.y, p3.x - p2.x));
-
- if (da1 >= kPi) {
- da1 = 2.0 * kPi - da1;
- }
-
- if (da1 < approx.angle_tolerance) {
- points.emplace_back(p2);
- points.emplace_back(p3);
- return;
- }
-
- if (approx.cusp_limit != 0.0) {
- if (da1 > approx.cusp_limit) {
- points.emplace_back(p3);
- return;
- }
- }
- }
- break;
-
- case 2:
- /*
- * p1,p3,p4 are collinear, p2 is significant.
- */
- if (d2 * d2 <=
- approx.distance_tolerance_square * (d.x * d.x + d.y * d.y)) {
- if (approx.angle_tolerance < kCurveAngleToleranceEpsilon) {
- points.emplace_back(p23);
- return;
- }
-
- /*
- * Angle Condition.
- */
- da1 = ::fabs(::atan2(p3.y - p2.y, p3.x - p2.x) -
- ::atan2(p2.y - p1.y, p2.x - p1.x));
-
- if (da1 >= kPi) {
- da1 = 2.0 * kPi - da1;
- }
-
- if (da1 < approx.angle_tolerance) {
- points.emplace_back(p2);
- points.emplace_back(p3);
- return;
- }
-
- if (approx.cusp_limit != 0.0) {
- if (da1 > approx.cusp_limit) {
- points.emplace_back(p2);
- return;
- }
- }
- }
- break;
-
- case 3:
- /*
- * Regular case.
- */
- if ((d2 + d3) * (d2 + d3) <=
- approx.distance_tolerance_square * (d.x * d.x + d.y * d.y)) {
- /*
- * If the curvature doesn't exceed the distance_tolerance value
- * we tend to finish subdivisions.
- */
- if (approx.angle_tolerance < kCurveAngleToleranceEpsilon) {
- points.emplace_back(p23);
- return;
- }
-
- /*
- * Angle & Cusp Condition.
- */
- k = ::atan2(p3.y - p2.y, p3.x - p2.x);
- da1 = ::fabs(k - ::atan2(p2.y - p1.y, p2.x - p1.x));
- da2 = ::fabs(::atan2(p4.y - p3.y, p4.x - p3.x) - k);
-
- if (da1 >= kPi) {
- da1 = 2.0 * kPi - da1;
- }
-
- if (da2 >= kPi) {
- da2 = 2.0 * kPi - da2;
- }
-
- if (da1 + da2 < approx.angle_tolerance) {
- /*
- * Finally we can stop the recursion.
- */
- points.emplace_back(p23);
- return;
- }
-
- if (approx.cusp_limit != 0.0) {
- if (da1 > approx.cusp_limit) {
- points.emplace_back(p2);
- return;
- }
-
- if (da2 > approx.cusp_limit) {
- points.emplace_back(p3);
- return;
- }
- }
- }
- break;
- }
+inline QuadraticPathComponent CubicPathComponent::Lower() const {
+ return QuadraticPathComponent(3.0 * (cp1 - p1), 3.0 * (cp2 - cp1),
+ 3.0 * (p2 - cp2));
+}
- /*
- * Continue subdivision.
- */
- CubicPathSmoothenRecursive(approx, points, p1, p12, p123, p1234, level + 1);
- CubicPathSmoothenRecursive(approx, points, p1234, p234, p34, p4, level + 1);
+CubicPathComponent CubicPathComponent::Subsegment(Scalar t0, Scalar t1) const {
+ auto p0 = Solve(t0);
+ auto p3 = Solve(t1);
+ auto d = Lower();
+ auto scale = (t1 - t0) * (1.0 / 3.0);
+ auto p1 = p0 + scale * d.Solve(t0);
+ auto p2 = p3 - scale * d.Solve(t1);
+ return CubicPathComponent(p0, p1, p2, p3);
}
-std::vector<Point> CubicPathComponent::CreatePolyline(
- const SmoothingApproximation& approximation) const {
- std::vector<Point> points;
- CubicPathSmoothenRecursive(approximation, points, p1, cp1, cp2, p2, 0);
- points.emplace_back(p2);
- return points;
+std::vector<QuadraticPathComponent> CubicPathComponent::ToQuadratics(
+ Scalar accuracy) const {
+ std::vector<QuadraticPathComponent> quads;
+ // The maximum error, as a vector from the cubic to the best approximating
+ // quadratic, is proportional to the third derivative, which is constant
+ // across the segment. Thus, the error scales down as the third power of
+ // the number of subdivisions. Our strategy then is to subdivide `t` evenly.
+ //
+ // This is an overestimate of the error because only the component
+ // perpendicular to the first derivative is important. But the simplicity is
+ // appealing.
+
+ // This magic number is the square of 36 / sqrt(3).
+ // See: http://caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
+ auto max_hypot2 = 432.0 * accuracy * accuracy;
+ auto p1x2 = 3.0 * cp1 - p1;
+ auto p2x2 = 3.0 * cp2 - p2;
+ auto p = p2x2 - p1x2;
+ auto err = p.Dot(p);
+ auto quad_count = std::max(1., ceil(pow(err / max_hypot2, 1. / 6.0)));
+
+ for (size_t i = 0; i < quad_count; i++) {
+ auto t0 = i / quad_count;
+ auto t1 = (i + 1) / quad_count;
+ auto seg = Subsegment(t0, t1);
+ auto p1x2 = 3.0 * seg.cp1 - seg.p1;
+ auto p2x2 = 3.0 * seg.cp2 - seg.p2;
+ quads.emplace_back(
+ QuadraticPathComponent(seg.p1, ((p1x2 + p2x2) / 4.0), seg.p2));
+ }
+ return quads;
}
static inline bool NearEqual(Scalar a, Scalar b, Scalar epsilon) {
diff --git a/impeller/geometry/path_component.h b/impeller/geometry/path_component.h
index d1cdf3a0b0..cf7b275581 100644
--- a/impeller/geometry/path_component.h
+++ b/impeller/geometry/path_component.h
@@ -12,46 +12,15 @@
namespace impeller {
-/// Information about how to approximate points on a curved path segment.
-///
-/// In particular, the values in this object control how many vertices to
-/// generate when approximating curves, and what tolerances to use when
-/// calculating the sharpness of curves.
-struct SmoothingApproximation {
- /// The scaling coefficient to use when translating to screen coordinates.
- ///
- /// Values approaching 0.0 will generate smoother looking curves with a
- /// greater number of vertices, and will be more expensive to calculate.
- Scalar scale;
-
- /// The tolerance value in radians for calculating sharp angles.
- ///
- /// Values approaching 0.0 will provide more accurate approximation of sharp
- /// turns. A 0.0 value means angle conditions are not considered at all.
- Scalar angle_tolerance;
-
- /// An angle in radians at which to introduce bevel cuts.
- ///
- /// Values greater than zero will restirct the sharpness of bevel cuts on
- /// turns.
- Scalar cusp_limit;
-
- /// Used to more quickly detect colinear cases.
- Scalar distance_tolerance_square;
-
- SmoothingApproximation(/* default */)
- : SmoothingApproximation(1.0 /* scale */,
- 0.0 /* angle tolerance */,
- 0.0 /* cusp limit */) {}
-
- SmoothingApproximation(Scalar p_scale,
- Scalar p_angle_tolerance,
- Scalar p_cusp_limit)
- : scale(p_scale),
- angle_tolerance(p_angle_tolerance),
- cusp_limit(p_cusp_limit),
- distance_tolerance_square(0.5 * p_scale * 0.5 * p_scale) {}
-};
+// The default tolerance value for QuadraticCurveComponent::CreatePolyline and
+// CubicCurveComponent::CreatePolyline. It also impacts the number of quadratics
+// created when flattening a cubic curve to a polyline.
+//
+// Smaller numbers mean more points. This number seems suitable for particularly
+// curvy curves at scales close to 1.0. As the scale increases, this number
+// should be divided by Matrix::GetMaxBasisLength to avoid generating too few
+// points for the given scale.
+static constexpr Scalar kDefaultCurveTolerance = .1f;
struct LinearPathComponent {
Point p1;
@@ -86,8 +55,21 @@ struct QuadraticPathComponent {
Point SolveDerivative(Scalar time) const;
+ // Uses the algorithm described by Raph Levien in
+ // https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html.
+ //
+ // The algorithm has several benefits:
+ // - It does not require elevation to cubics for processing.
+ // - It generates fewer and more accurate points than recursive subdivision.
+ // - Each turn of the core iteration loop has no dependencies on other turns,
+ // making it trivially parallelizable.
+ //
+ // See also the implementation in kurbo: https://github.com/linebender/kurbo.
std::vector<Point> CreatePolyline(
- const SmoothingApproximation& approximation) const;
+ Scalar tolerance = kDefaultCurveTolerance) const;
+
+ void FillPointsForPolyline(std::vector<Point>& points,
+ Scalar tolerance = kDefaultCurveTolerance) const;
std::vector<Point> Extrema() const;
@@ -117,15 +99,26 @@ struct CubicPathComponent {
Point SolveDerivative(Scalar time) const;
+ // This method approximates the cubic component with quadratics, and then
+ // generates a polyline from those quadratics.
+ //
+ // See the note on QuadraticPathComponent::CreatePolyline for references.
std::vector<Point> CreatePolyline(
- const SmoothingApproximation& approximation) const;
+ Scalar tolerance = kDefaultCurveTolerance) const;
std::vector<Point> Extrema() const;
+ std::vector<QuadraticPathComponent> ToQuadratics(Scalar accuracy) const;
+
+ CubicPathComponent Subsegment(Scalar t0, Scalar t1) const;
+
bool operator==(const CubicPathComponent& other) const {
return p1 == other.p1 && cp1 == other.cp1 && cp2 == other.cp2 &&
p2 == other.p2;
}
+
+ private:
+ QuadraticPathComponent Lower() const;
};
struct ContourComponent {
diff --git a/impeller/tessellator/c/tessellator.cc b/impeller/tessellator/c/tessellator.cc
index 7a53d9cede..09b44b5014 100644
--- a/impeller/tessellator/c/tessellator.cc
+++ b/impeller/tessellator/c/tessellator.cc
@@ -39,12 +39,11 @@ void Close(PathBuilder* builder) {
struct Vertices* Tessellate(PathBuilder* builder,
int fill_type,
- Scalar scale,
+ Scalar tolerance,
Scalar angle_tolerance,
Scalar cusp_limit) {
auto path = builder->CopyPath(static_cast<FillType>(fill_type));
- auto smoothing = SmoothingApproximation(scale, angle_tolerance, cusp_limit);
- auto polyline = path.CreatePolyline(smoothing);
+ auto polyline = path.CreatePolyline(tolerance);
std::vector<float> points;
if (Tessellator{}.Tessellate(path.GetFillType(), polyline,
[&points](Point vertex) {
diff --git a/impeller/tessellator/c/tessellator.h b/impeller/tessellator/c/tessellator.h
index 23a24e1f96..0cb01d68f6 100644
--- a/impeller/tessellator/c/tessellator.h
+++ b/impeller/tessellator/c/tessellator.h
@@ -42,7 +42,8 @@ IMPELLER_API void Close(PathBuilder* builder);
IMPELLER_API struct Vertices* Tessellate(PathBuilder* builder,
int fill_type,
- Scalar scale,
+ Scalar tolerance,
+ // Unused, remaining for ABI stability.
Scalar angle_tolerance,
Scalar cusp_limit);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment