| 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 <array>
9 #include <functional>
10 #include <optional>
11 #include <type_traits>
12 #include <vector>
13
14 #include "impeller/geometry/point.h"
15 #include "impeller/geometry/scalar.h"
16
17 namespace impeller {
18
19 /// @brief An interface for generating a multi contour polyline as a triangle
20 /// strip.
21 class VertexWriter {
22 public:
23 virtual void EndContour() = 0;
24
25 virtual void Write(Point point) = 0;
26 };
27
28 /// @brief A vertex writer that generates a triangle fan and requires primitive
29 /// restart.
30 class FanVertexWriter : public VertexWriter {
31 public:
32 explicit FanVertexWriter(Point* point_buffer, uint16_t* index_buffer);
33
34 ~FanVertexWriter();
35
36 size_t GetIndexCount() const;
37
38 void EndContour() override;
39
40 void Write(Point point) override;
41
42 private:
43 size_t count_ = 0;
44 size_t index_count_ = 0;
45 Point* point_buffer_ = nullptr;
46 uint16_t* index_buffer_ = nullptr;
47 };
48
49 /// @brief A vertex writer that generates a triangle strip and requires
50 /// primitive restart.
51 class StripVertexWriter : public VertexWriter {
52 public:
53 explicit StripVertexWriter(Point* point_buffer, uint16_t* index_buffer);
54
55 ~StripVertexWriter();
56
57 size_t GetIndexCount() const;
58
59 void EndContour() override;
60
61 void Write(Point point) override;
62
63 private:
64 size_t count_ = 0;
65 size_t index_count_ = 0;
66 size_t contour_start_ = 0;
67 Point* point_buffer_ = nullptr;
68 uint16_t* index_buffer_ = nullptr;
69 };
70
71 /// @brief A vertex writer that generates a line strip topology.
72 class LineStripVertexWriter : public VertexWriter {
73 public:
74 explicit LineStripVertexWriter(std::vector<Point>& points);
75
76 ~LineStripVertexWriter() = default;
77
78 void EndContour() override;
79
80 void Write(Point point) override;
81
82 std::pair<size_t, size_t> GetVertexCount() const;
83
84 const std::vector<Point>& GetOversizedBuffer() const;
85
86 private:
87 size_t offset_ = 0u;
88 std::vector<Point>& points_;
89 std::vector<Point> overflow_;
90 };
91
92 /// @brief A vertex writer that has no hardware requirements.
93 class GLESVertexWriter : public VertexWriter {
94 public:
95 explicit GLESVertexWriter(std::vector<Point>& points,
96 std::vector<uint16_t>& indices);
97
98 ~GLESVertexWriter() = default;
99
100 void EndContour() override;
101
102 void Write(Point point) override;
103
104 private:
105 bool previous_contour_odd_points_ = false;
106 size_t contour_start_ = 0u;
107 std::vector<Point>& points_;
108 std::vector<uint16_t>& indices_;
109 };
110
111 struct LinearPathComponent {
112 Point p1;
113 Point p2;
114
115 LinearPathComponent() {}
116
117 LinearPathComponent(Point ap1, Point ap2) : p1(ap1), p2(ap2) {}
118
119 Point Solve(Scalar time) const;
120
121 void AppendPolylinePoints(std::vector<Point>& points) const;
122
123 std::vector<Point> Extrema() const;
124
125 bool operator==(const LinearPathComponent& other) const {
126 return p1 == other.p1 && p2 == other.p2;
127 }
128
129 std::optional<Vector2> GetStartDirection() const;
130
131 std::optional<Vector2> GetEndDirection() const;
132 };
133
134 // A component that represets a Quadratic Bézier curve.
135 struct QuadraticPathComponent {
136 // Start point.
137 Point p1;
138 // Control point.
139 Point cp;
140 // End point.
141 Point p2;
142
143 QuadraticPathComponent() {}
144
145 QuadraticPathComponent(Point ap1, Point acp, Point ap2)
146 : p1(ap1), cp(acp), p2(ap2) {}
147
148 Point Solve(Scalar time) const;
149
150 Point SolveDerivative(Scalar time) const;
151
152 void AppendPolylinePoints(Scalar scale_factor,
153 std::vector<Point>& points) const;
154
155 using PointProc = std::function<void(const Point& point)>;
156
157 void ToLinearPathComponents(Scalar scale_factor, const PointProc& proc) const;
158
159 void ToLinearPathComponents(Scalar scale, VertexWriter& writer) const;
160
161 size_t CountLinearPathComponents(Scalar scale) const;
162
163 std::vector<Point> Extrema() const;
164
165 bool operator==(const QuadraticPathComponent& other) const {
166 return p1 == other.p1 && cp == other.cp && p2 == other.p2;
167 }
168
169 std::optional<Vector2> GetStartDirection() const;
170
171 std::optional<Vector2> GetEndDirection() const;
172 };
173
174 // A component that represets a Conic section curve.
175 //
176 // A conic section is basically nearly a quadratic bezier curve, but it
177 // has an additional weight that is applied to the middle term (the control
178 // point term).
179 //
180 // Starting with the equation for a quadratic curve which is:
181 // (A) P1 * (1 - t) * (1 - t)
182 // + CP * 2 * t * (1 - t)
183 // + P2 * t * t
184 // One thing to note is that the quadratic coefficients always sum to 1:
185 // (B) (1-t)(1-t) + 2t(1-t) + tt
186 // == 1 - 2t + tt + 2t - 2tt + tt
187 // == 1
188 // which means that the resulting point is always a weighted average of
189 // the 3 points without having to "divide by the sum of the coefficients"
190 // that is normally done when computing weighted averages.
191 //
192 // The conic equation, though, would then be:
193 // (C) P1 * (1 - t) * (1 - t)
194 // + CP * 2 * t * (1 - t) * w
195 // + P2 * t * t
196 // That would be the final equation, but if we look at the coefficients:
197 // (D) (1-t)(1-t) + 2wt(1-t) + tt
198 // == 1 - 2t + tt + 2wt - 2wtt + tt
199 // == 1 + (2w - 2)t + (2 - 2w)tt
200 // These only sum to 1 if the weight (w) is 1. In order for this math to
201 // produce a point that is the weighted average of the 3 points, we have
202 // to compute both and divide the equation (C) by the equation (D).
203 //
204 // Note that there are important potential optimizations we could apply.
205 // If w is 0,
206 // then this equation devolves into a straight line from P1 to P2.
207 // Note that the "progress" from P1 to P2, as a function of t, is
208 // quadratic if you compute it as the indicated numerator and denominator,
209 // but the actual points generated are all on the line from P1 to P2
210 // If w is (sqrt(2) / 2),
211 // then this math is exactly an elliptical section, provided the 3 points
212 // P1, CP, P2 form a right angle, and a circular section if they are also
213 // of equal length (|P1,CP| == |CP,P2|)
214 // If w is 1,
215 // then we really don't need the division since the denominator will always
216 // be 1 and we could just treat that curve as a quadratic.
217 // If w is (infinity/large enough),
218 // then the equation devolves into 2 straight lines P1->CP->P2, but
219 // the straightforward math may encounter infinity/NaN values in the
220 // intermediate stages. The limit as w approaches infinity are those
221 // two lines.
222 //
223 // Some examples: https://fiddle.skia.org/c/986b521feb3b832f04cbdfeefc9fbc58
224 // Note that the quadratic drawn in red in the center is identical to the
225 // conic with a weight of 1, drawn in green in the lower left.
226 struct ConicPathComponent {
227 // Start point.
228 Point p1;
229 // Control point.
230 Point cp;
231 // End point.
232 Point p2;
233
234 // Weight
235 //
236 // We only need one value, but the underlying storage allocation is always
237 // a multiple of Point objects. To avoid confusion over which field the
238 // weight is stored in, and what the value of the other field may be, we
239 // store it in both x,y components of the |weight| field.
240 //
241 // This may also be an advantage eventually for code that can vectorize
242 // the conic calculations on both X & Y simultaneously.
243 Point weight;
244
245 ConicPathComponent() {}
246
247 ConicPathComponent(Point ap1, Point acp, Point ap2, Scalar weight)
248 : p1(ap1), cp(acp), p2(ap2), weight(weight, weight) {}
249
250 Point Solve(Scalar time) const;
251
252 void AppendPolylinePoints(Scalar scale_factor,
253 std::vector<Point>& points) const;
254
255 using PointProc = std::function<void(const Point& point)>;
256
257 void ToLinearPathComponents(Scalar scale_factor, const PointProc& proc) const;
258
259 void ToLinearPathComponents(Scalar scale, VertexWriter& writer) const;
260
261 size_t CountLinearPathComponents(Scalar scale) const;
262
263 std::vector<Point> Extrema() const;
264
265 bool operator==(const ConicPathComponent& other) const {
266 return p1 == other.p1 && cp == other.cp && p2 == other.p2 &&
267 weight == other.weight;
268 }
269
270 std::optional<Vector2> GetStartDirection() const;
271
272 std::optional<Vector2> GetEndDirection() const;
273
274 std::array<QuadraticPathComponent, 2> ToQuadraticPathComponents() const;
275
276 void SubdivideToQuadraticPoints(std::array<Point, 5>& points) const;
277 };
278
279 // A component that represets a Cubic Bézier curve.
280 struct CubicPathComponent {
281 // Start point.
282 Point p1;
283 // The first control point.
284 Point cp1;
285 // The second control point.
286 Point cp2;
287 // End point.
288 Point p2;
289
290 CubicPathComponent() {}
291
292 explicit CubicPathComponent(const QuadraticPathComponent& q)
293 : p1(q.p1),
294 cp1(q.p1 + (q.cp - q.p1) * (2.0 / 3.0)),
295 cp2(q.p2 + (q.cp - q.p2) * (2.0 / 3.0)),
296 p2(q.p2) {}
297
298 CubicPathComponent(Point ap1, Point acp1, Point acp2, Point ap2)
299 : p1(ap1), cp1(acp1), cp2(acp2), p2(ap2) {}
300
301 Point Solve(Scalar time) const;
302
303 Point SolveDerivative(Scalar time) const;
304
305 void AppendPolylinePoints(Scalar scale, std::vector<Point>& points) const;
306
307 std::vector<Point> Extrema() const;
308
309 using PointProc = std::function<void(const Point& point)>;
310
311 void ToLinearPathComponents(Scalar scale, const PointProc& proc) const;
312
313 void ToLinearPathComponents(Scalar scale, VertexWriter& writer) const;
314
315 size_t CountLinearPathComponents(Scalar scale) const;
316
317 CubicPathComponent Subsegment(Scalar t0, Scalar t1) const;
318
319 bool operator==(const CubicPathComponent& other) const {
320 return p1 == other.p1 && cp1 == other.cp1 && cp2 == other.cp2 &&
321 p2 == other.p2;
322 }
323
324 std::optional<Vector2> GetStartDirection() const;
325
326 std::optional<Vector2> GetEndDirection() const;
327
328 private:
329 QuadraticPathComponent Lower() const;
330 };
331
332 struct ContourComponent {
333 Point destination;
334
335 // 0, 0 for closed, anything else for open.
336 Point closed = Point(1, 1);
337
338 ContourComponent() {}
339
340 constexpr bool IsClosed() const { return closed == Point{0, 0}; }
341
342 explicit ContourComponent(Point p, Point closed)
343 : destination(p), closed(closed) {}
344
345 bool operator==(const ContourComponent& other) const {
346 return destination == other.destination && IsClosed() == other.IsClosed();
347 }
348 };
349
350 static_assert(!std::is_polymorphic<LinearPathComponent>::value);
351 static_assert(!std::is_polymorphic<QuadraticPathComponent>::value);
352 static_assert(!std::is_polymorphic<CubicPathComponent>::value);
353
354 } // namespace impeller
355
356 #endif // FLUTTER_IMPELLER_GEOMETRY_PATH_COMPONENT_H_
impeller::FanVertexWriter
A vertex writer that generates a triangle fan and requires primitive restart.
Definition: path_component.h:30
impeller::FanVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:27
impeller::FanVertexWriter::GetIndexCount
size_t GetIndexCount() const
Definition: path_component.cc:23
impeller::FanVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:34
impeller::FanVertexWriter::~FanVertexWriter
~FanVertexWriter()
impeller::FanVertexWriter::FanVertexWriter
FanVertexWriter(Point *point_buffer, uint16_t *index_buffer)
Definition: path_component.cc:18
impeller::GLESVertexWriter
A vertex writer that has no hardware requirements.
Definition: path_component.h:93
impeller::GLESVertexWriter::GLESVertexWriter
GLESVertexWriter(std::vector< Point > &points, std::vector< uint16_t > &indices)
Definition: path_component.cc:107
impeller::GLESVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:161
impeller::GLESVertexWriter::~GLESVertexWriter
~GLESVertexWriter()=default
impeller::GLESVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:111
impeller::LineStripVertexWriter
A vertex writer that generates a line strip topology.
Definition: path_component.h:72
impeller::LineStripVertexWriter::GetVertexCount
std::pair< size_t, size_t > GetVertexCount() const
Definition: path_component.cc:101
impeller::LineStripVertexWriter::LineStripVertexWriter
LineStripVertexWriter(std::vector< Point > &points)
Definition: path_component.cc:84
impeller::LineStripVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:89
impeller::LineStripVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:87
impeller::LineStripVertexWriter::~LineStripVertexWriter
~LineStripVertexWriter()=default
impeller::LineStripVertexWriter::GetOversizedBuffer
const std::vector< Point > & GetOversizedBuffer() const
Definition: path_component.cc:97
impeller::StripVertexWriter
A vertex writer that generates a triangle strip and requires primitive restart.
Definition: path_component.h:51
impeller::StripVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:78
impeller::StripVertexWriter::~StripVertexWriter
~StripVertexWriter()
impeller::StripVertexWriter::GetIndexCount
size_t GetIndexCount() const
Definition: path_component.cc:47
impeller::StripVertexWriter::StripVertexWriter
StripVertexWriter(Point *point_buffer, uint16_t *index_buffer)
Definition: path_component.cc:41
impeller::StripVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:51
impeller::VertexWriter
An interface for generating a multi contour polyline as a triangle strip.
Definition: path_component.h:21
impeller::VertexWriter::EndContour
virtual void EndContour()=0
impeller::VertexWriter::Write
virtual void Write(Point point)=0
value
int32_t value
Definition: dl_golden_unittests.cc:459
impeller
Definition: allocation.cc:12
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::Point
TPoint< Scalar > Point
Definition: point.h:327
point.h
scalar.h
scale
const Scalar scale
Definition: stroke_path_geometry.cc:319
impeller::ConicPathComponent
Definition: path_component.h:226
impeller::ConicPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:385
impeller::ConicPathComponent::cp
Point cp
Definition: path_component.h:230
impeller::ConicPathComponent::ToQuadraticPathComponents
std::array< QuadraticPathComponent, 2 > ToQuadraticPathComponents() const
Definition: path_component.cc:435
impeller::ConicPathComponent::CountLinearPathComponents
size_t CountLinearPathComponents(Scalar scale) const
Definition: path_component.cc:362
impeller::ConicPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:327
impeller::ConicPathComponent::ConicPathComponent
ConicPathComponent(Point ap1, Point acp, Point ap2, Scalar weight)
Definition: path_component.h:247
impeller::ConicPathComponent::operator==
bool operator==(const ConicPathComponent &other) const
Definition: path_component.h:265
impeller::ConicPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale_factor, const PointProc &proc) const
Definition: path_component.cc:334
impeller::ConicPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:366
impeller::ConicPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:375
impeller::ConicPathComponent::weight
Point weight
Definition: path_component.h:243
impeller::ConicPathComponent::ConicPathComponent
ConicPathComponent()
Definition: path_component.h:245
impeller::ConicPathComponent::SubdivideToQuadraticPoints
void SubdivideToQuadraticPoints(std::array< Point, 5 > &points) const
Definition: path_component.cc:395
impeller::ConicPathComponent::p1
Point p1
Definition: path_component.h:228
impeller::ConicPathComponent::p2
Point p2
Definition: path_component.h:232
impeller::ConicPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:255
impeller::ConicPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale_factor, std::vector< Point > &points) const
Definition: path_component.cc:343
impeller::ContourComponent
Definition: path_component.h:332
impeller::ContourComponent::operator==
bool operator==(const ContourComponent &other) const
Definition: path_component.h:345
impeller::ContourComponent::ContourComponent
ContourComponent()
Definition: path_component.h:338
impeller::ContourComponent::IsClosed
constexpr bool IsClosed() const
Definition: path_component.h:340
impeller::ContourComponent::ContourComponent
ContourComponent(Point p, Point closed)
Definition: path_component.h:342
impeller::ContourComponent::destination
Point destination
Definition: path_component.h:333
impeller::ContourComponent::closed
Point closed
Definition: path_component.h:336
impeller::CubicPathComponent
Definition: path_component.h:280
impeller::CubicPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale, const PointProc &proc) const
Definition: path_component.cc:494
impeller::CubicPathComponent::CountLinearPathComponents
size_t CountLinearPathComponents(Scalar scale) const
Definition: path_component.cc:475
impeller::CubicPathComponent::p1
Point p1
Definition: path_component.h:282
impeller::CubicPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale, std::vector< Point > &points) const
Definition: path_component.cc:459
impeller::CubicPathComponent::cp1
Point cp1
Definition: path_component.h:284
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent(Point ap1, Point acp1, Point acp2, Point ap2)
Definition: path_component.h:298
impeller::CubicPathComponent::operator==
bool operator==(const CubicPathComponent &other) const
Definition: path_component.h:319
impeller::CubicPathComponent::cp2
Point cp2
Definition: path_component.h:286
impeller::CubicPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:309
impeller::CubicPathComponent::Subsegment
CubicPathComponent Subsegment(Scalar t0, Scalar t1) const
Definition: path_component.cc:484
impeller::CubicPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:445
impeller::CubicPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:584
impeller::CubicPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:566
impeller::CubicPathComponent::p2
Point p2
Definition: path_component.h:288
impeller::CubicPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:597
impeller::CubicPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:452
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent()
Definition: path_component.h:290
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent(const QuadraticPathComponent &q)
Definition: path_component.h:292
impeller::LinearPathComponent
Definition: path_component.h:111
impeller::LinearPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:248
impeller::LinearPathComponent::LinearPathComponent
LinearPathComponent(Point ap1, Point ap2)
Definition: path_component.h:117
impeller::LinearPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:241
impeller::LinearPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:237
impeller::LinearPathComponent::p2
Point p2
Definition: path_component.h:113
impeller::LinearPathComponent::p1
Point p1
Definition: path_component.h:112
impeller::LinearPathComponent::operator==
bool operator==(const LinearPathComponent &other) const
Definition: path_component.h:125
impeller::LinearPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:223
impeller::LinearPathComponent::AppendPolylinePoints
void AppendPolylinePoints(std::vector< Point > &points) const
Definition: path_component.cc:230
impeller::LinearPathComponent::LinearPathComponent
LinearPathComponent()
Definition: path_component.h:115
impeller::QuadraticPathComponent
Definition: path_component.h:135
impeller::QuadraticPathComponent::CountLinearPathComponents
size_t CountLinearPathComponents(Scalar scale) const
Definition: path_component.cc:298
impeller::QuadraticPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:317
impeller::QuadraticPathComponent::QuadraticPathComponent
QuadraticPathComponent()
Definition: path_component.h:143
impeller::QuadraticPathComponent::QuadraticPathComponent
QuadraticPathComponent(Point ap1, Point acp, Point ap2)
Definition: path_component.h:145
impeller::QuadraticPathComponent::p2
Point p2
Definition: path_component.h:141
impeller::QuadraticPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale_factor, std::vector< Point > &points) const
Definition: path_component.cc:279
impeller::QuadraticPathComponent::operator==
bool operator==(const QuadraticPathComponent &other) const
Definition: path_component.h:165
impeller::QuadraticPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:155
impeller::QuadraticPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:302
impeller::QuadraticPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:262
impeller::QuadraticPathComponent::cp
Point cp
Definition: path_component.h:139
impeller::QuadraticPathComponent::p1
Point p1
Definition: path_component.h:137
impeller::QuadraticPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:307
impeller::QuadraticPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale_factor, const PointProc &proc) const
Definition: path_component.cc:287
impeller::QuadraticPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:255
impeller::TPoint< Scalar >