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