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