| Flutter Impeller |

path_component.h
Go to the documentation of this file.
1 // Copyright 2013 The Flutter Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef FLUTTER_IMPELLER_GEOMETRY_PATH_COMPONENT_H_
6 #define FLUTTER_IMPELLER_GEOMETRY_PATH_COMPONENT_H_
7
8 #include <functional>
9 #include <type_traits>
10 #include <variant>
11 #include <vector>
12
13 #include "impeller/geometry/point.h"
14 #include "impeller/geometry/rect.h"
15 #include "impeller/geometry/scalar.h"
16
17 namespace impeller {
18
19 // The default tolerance value for QuadraticCurveComponent::AppendPolylinePoints
20 // and CubicCurveComponent::AppendPolylinePoints. It also impacts the number of
21 // quadratics created when flattening a cubic curve to a polyline.
22 //
23 // Smaller numbers mean more points. This number seems suitable for particularly
24 // curvy curves at scales close to 1.0. As the scale increases, this number
25 // should be divided by Matrix::GetMaxBasisLength to avoid generating too few
26 // points for the given scale.
27 static constexpr Scalar kDefaultCurveTolerance = .1f;
28
29 struct LinearPathComponent {
30 Point p1;
31 Point p2;
32
33 LinearPathComponent() {}
34
35 LinearPathComponent(Point ap1, Point ap2) : p1(ap1), p2(ap2) {}
36
37 Point Solve(Scalar time) const;
38
39 void AppendPolylinePoints(std::vector<Point>& points) const;
40
41 std::vector<Point> Extrema() const;
42
43 bool operator==(const LinearPathComponent& other) const {
44 return p1 == other.p1 && p2 == other.p2;
45 }
46
47 std::optional<Vector2> GetStartDirection() const;
48
49 std::optional<Vector2> GetEndDirection() const;
50 };
51
52 // A component that represets a Quadratic Bézier curve.
53 struct QuadraticPathComponent {
54 // Start point.
55 Point p1;
56 // Control point.
57 Point cp;
58 // End point.
59 Point p2;
60
61 QuadraticPathComponent() {}
62
63 QuadraticPathComponent(Point ap1, Point acp, Point ap2)
64 : p1(ap1), cp(acp), p2(ap2) {}
65
66 Point Solve(Scalar time) const;
67
68 Point SolveDerivative(Scalar time) const;
69
70 // Uses the algorithm described by Raph Levien in
71 // https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html.
72 //
73 // The algorithm has several benefits:
74 // - It does not require elevation to cubics for processing.
75 // - It generates fewer and more accurate points than recursive subdivision.
76 // - Each turn of the core iteration loop has no dependencies on other turns,
77 // making it trivially parallelizable.
78 //
79 // See also the implementation in kurbo: https://github.com/linebender/kurbo.
80 void AppendPolylinePoints(Scalar scale_factor,
81 std::vector<Point>& points) const;
82
83 using PointProc = std::function<void(const Point& point)>;
84
85 void ToLinearPathComponents(Scalar scale_factor, const PointProc& proc) const;
86
87 std::vector<Point> Extrema() const;
88
89 bool operator==(const QuadraticPathComponent& other) const {
90 return p1 == other.p1 && cp == other.cp && p2 == other.p2;
91 }
92
93 std::optional<Vector2> GetStartDirection() const;
94
95 std::optional<Vector2> GetEndDirection() const;
96 };
97
98 // A component that represets a Cubic Bézier curve.
99 struct CubicPathComponent {
100 // Start point.
101 Point p1;
102 // The first control point.
103 Point cp1;
104 // The second control point.
105 Point cp2;
106 // End point.
107 Point p2;
108
109 CubicPathComponent() {}
110
111 explicit CubicPathComponent(const QuadraticPathComponent& q)
112 : p1(q.p1),
113 cp1(q.p1 + (q.cp - q.p1) * (2.0 / 3.0)),
114 cp2(q.p2 + (q.cp - q.p2) * (2.0 / 3.0)),
115 p2(q.p2) {}
116
117 CubicPathComponent(Point ap1, Point acp1, Point acp2, Point ap2)
118 : p1(ap1), cp1(acp1), cp2(acp2), p2(ap2) {}
119
120 Point Solve(Scalar time) const;
121
122 Point SolveDerivative(Scalar time) const;
123
124 // This method approximates the cubic component with quadratics, and then
125 // generates a polyline from those quadratics.
126 //
127 // See the note on QuadraticPathComponent::AppendPolylinePoints for
128 // references.
129 void AppendPolylinePoints(Scalar scale, std::vector<Point>& points) const;
130
131 std::vector<Point> Extrema() const;
132
133 using PointProc = std::function<void(const Point& point)>;
134
135 void ToLinearPathComponents(Scalar scale, const PointProc& proc) const;
136
137 CubicPathComponent Subsegment(Scalar t0, Scalar t1) const;
138
139 bool operator==(const CubicPathComponent& other) const {
140 return p1 == other.p1 && cp1 == other.cp1 && cp2 == other.cp2 &&
141 p2 == other.p2;
142 }
143
144 std::optional<Vector2> GetStartDirection() const;
145
146 std::optional<Vector2> GetEndDirection() const;
147
148 private:
149 QuadraticPathComponent Lower() const;
150 };
151
152 struct ContourComponent {
153 Point destination;
154 bool is_closed = false;
155
156 ContourComponent() {}
157
158 explicit ContourComponent(Point p, bool is_closed = false)
159 : destination(p), is_closed(is_closed) {}
160
161 bool operator==(const ContourComponent& other) const {
162 return destination == other.destination && is_closed == other.is_closed;
163 }
164 };
165
166 using PathComponentVariant = std::variant<std::monostate,
167 const LinearPathComponent*,
168 const QuadraticPathComponent*,
169 const CubicPathComponent*>;
170
171 struct PathComponentStartDirectionVisitor {
172 std::optional<Vector2> operator()(const LinearPathComponent* component);
173 std::optional<Vector2> operator()(const QuadraticPathComponent* component);
174 std::optional<Vector2> operator()(const CubicPathComponent* component);
175 std::optional<Vector2> operator()(std::monostate monostate) {
176 return std::nullopt;
177 }
178 };
179
180 struct PathComponentEndDirectionVisitor {
181 std::optional<Vector2> operator()(const LinearPathComponent* component);
182 std::optional<Vector2> operator()(const QuadraticPathComponent* component);
183 std::optional<Vector2> operator()(const CubicPathComponent* component);
184 std::optional<Vector2> operator()(std::monostate monostate) {
185 return std::nullopt;
186 }
187 };
188
189 static_assert(!std::is_polymorphic<LinearPathComponent>::value);
190 static_assert(!std::is_polymorphic<QuadraticPathComponent>::value);
191 static_assert(!std::is_polymorphic<CubicPathComponent>::value);
192
193 } // namespace impeller
194
195 #endif // FLUTTER_IMPELLER_GEOMETRY_PATH_COMPONENT_H_
point.h
impeller::LinearPathComponent
Definition: path_component.h:29
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::kDefaultCurveTolerance
static constexpr Scalar kDefaultCurveTolerance
Definition: path_component.h:27
impeller::PathComponentStartDirectionVisitor::operator()
std::optional< Vector2 > operator()(std::monostate monostate)
Definition: path_component.h:175
impeller::CubicPathComponent::Subsegment
CubicPathComponent Subsegment(Scalar t0, Scalar t1) const
Definition: path_component.cc:208
impeller::CubicPathComponent::p1
Point p1
Definition: path_component.h:101
impeller::QuadraticPathComponent::operator==
bool operator==(const QuadraticPathComponent &other) const
Definition: path_component.h:89
impeller::LinearPathComponent::p2
Point p2
Definition: path_component.h:31
impeller::QuadraticPathComponent::p1
Point p1
Definition: path_component.h:55
impeller::CubicPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:330
impeller::CubicPathComponent::cp2
Point cp2
Definition: path_component.h:105
impeller::CubicPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale, std::vector< Point > &points) const
Definition: path_component.cc:196
impeller::LinearPathComponent::AppendPolylinePoints
void AppendPolylinePoints(std::vector< Point > &points) const
Definition: path_component.cc:62
impeller::QuadraticPathComponent::cp
Point cp
Definition: path_component.h:57
impeller::QuadraticPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:162
impeller::PathComponentEndDirectionVisitor
Definition: path_component.h:180
impeller::ContourComponent::ContourComponent
ContourComponent(Point p, bool is_closed=false)
Definition: path_component.h:158
impeller::CubicPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:182
impeller::PathComponentStartDirectionVisitor::operator()
std::optional< Vector2 > operator()(const LinearPathComponent *component)
Definition: path_component.cc:356
impeller::QuadraticPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:172
impeller::ContourComponent::operator==
bool operator==(const ContourComponent &other) const
Definition: path_component.h:161
impeller::QuadraticPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale_factor, const PointProc &proc) const
Definition: path_component.cc:114
impeller::LinearPathComponent::LinearPathComponent
LinearPathComponent()
Definition: path_component.h:33
impeller::QuadraticPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:83
impeller::QuadraticPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:94
impeller::CubicPathComponent::cp1
Point cp1
Definition: path_component.h:103
impeller::LinearPathComponent::p1
Point p1
Definition: path_component.h:30
impeller::QuadraticPathComponent::QuadraticPathComponent
QuadraticPathComponent(Point ap1, Point acp, Point ap2)
Definition: path_component.h:63
impeller::LinearPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:73
impeller::ContourComponent::is_closed
bool is_closed
Definition: path_component.h:154
impeller::QuadraticPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:87
impeller::LinearPathComponent::operator==
bool operator==(const LinearPathComponent &other) const
Definition: path_component.h:43
impeller::CubicPathComponent::operator==
bool operator==(const CubicPathComponent &other) const
Definition: path_component.h:139
impeller::CubicPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:189
impeller::LinearPathComponent::LinearPathComponent
LinearPathComponent(Point ap1, Point ap2)
Definition: path_component.h:35
impeller::PathComponentStartDirectionVisitor
Definition: path_component.h:171
impeller::QuadraticPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:157
impeller::ContourComponent::destination
Point destination
Definition: path_component.h:153
impeller::CubicPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:343
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent(const QuadraticPathComponent &q)
Definition: path_component.h:111
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent()
Definition: path_component.h:109
impeller::CubicPathComponent
Definition: path_component.h:99
scalar.h
impeller::ContourComponent::ContourComponent
ContourComponent()
Definition: path_component.h:156
impeller::CubicPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale, const PointProc &proc) const
Definition: path_component.cc:218
impeller::QuadraticPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale_factor, std::vector< Point > &points) const
Definition: path_component.cc:106
rect.h
impeller::QuadraticPathComponent::p2
Point p2
Definition: path_component.h:59
impeller::TPoint< Scalar >
impeller::PathComponentEndDirectionVisitor::operator()
std::optional< Vector2 > operator()(const LinearPathComponent *component)
Definition: path_component.cc:380
impeller::QuadraticPathComponent::QuadraticPathComponent
QuadraticPathComponent()
Definition: path_component.h:61
scale
const Scalar scale
Definition: stroke_path_geometry.cc:297
impeller::CubicPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:133
impeller::CubicPathComponent::p2
Point p2
Definition: path_component.h:107
impeller::CubicPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:312
impeller::PathComponentVariant
std::variant< std::monostate, const LinearPathComponent *, const QuadraticPathComponent *, const CubicPathComponent * > PathComponentVariant
Definition: path_component.h:169
impeller::PathComponentEndDirectionVisitor::operator()
std::optional< Vector2 > operator()(std::monostate monostate)
Definition: path_component.h:184
impeller::ContourComponent
Definition: path_component.h:152
impeller::LinearPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:80
impeller
Definition: aiks_blur_unittests.cc:20
impeller::QuadraticPathComponent
Definition: path_component.h:53
impeller::LinearPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:55
impeller::LinearPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:69
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent(Point ap1, Point acp1, Point acp2, Point ap2)
Definition: path_component.h:117