| Flutter Impeller |

path_component.cc
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 #include "path_component.h"
6
7 #include <cmath>
8 #include <utility>
9
10 #include "impeller/geometry/scalar.h"
11 #include "impeller/geometry/wangs_formula.h"
12
13 namespace impeller {
14
15 /////////// FanVertexWriter ///////////
16
17 FanVertexWriter::FanVertexWriter(Point* point_buffer, uint16_t* index_buffer)
18 : point_buffer_(point_buffer), index_buffer_(index_buffer) {}
19
20 FanVertexWriter::~FanVertexWriter() = default;
21
22 size_t FanVertexWriter::GetIndexCount() const {
23 return index_count_;
24 }
25
26 void FanVertexWriter::EndContour() {
27 if (count_ == 0) {
28 return;
29 }
30 index_buffer_[index_count_++] = 0xFFFF;
31 }
32
33 void FanVertexWriter::Write(Point point) {
34 index_buffer_[index_count_++] = count_;
35 point_buffer_[count_++] = point;
36 }
37
38 /////////// StripVertexWriter ///////////
39
40 StripVertexWriter::StripVertexWriter(Point* point_buffer,
41 uint16_t* index_buffer)
42 : point_buffer_(point_buffer), index_buffer_(index_buffer) {}
43
44 StripVertexWriter::~StripVertexWriter() = default;
45
46 size_t StripVertexWriter::GetIndexCount() const {
47 return index_count_;
48 }
49
50 void StripVertexWriter::EndContour() {
51 if (count_ == 0u || contour_start_ == count_ - 1) {
52 // Empty or first contour.
53 return;
54 }
55
56 size_t start = contour_start_;
57 size_t end = count_ - 1;
58
59 index_buffer_[index_count_++] = start;
60
61 size_t a = start + 1;
62 size_t b = end;
63 while (a < b) {
64 index_buffer_[index_count_++] = a;
65 index_buffer_[index_count_++] = b;
66 a++;
67 b--;
68 }
69 if (a == b) {
70 index_buffer_[index_count_++] = a;
71 }
72
73 contour_start_ = count_;
74 index_buffer_[index_count_++] = 0xFFFF;
75 }
76
77 void StripVertexWriter::Write(Point point) {
78 point_buffer_[count_++] = point;
79 }
80
81 /////////// LineStripVertexWriter ////////
82
83 LineStripVertexWriter::LineStripVertexWriter(std::vector<Point>& points)
84 : points_(points) {}
85
86 void LineStripVertexWriter::EndContour() {}
87
88 void LineStripVertexWriter::Write(Point point) {
89 if (offset_ >= points_.size()) {
90 overflow_.push_back(point);
91 } else {
92 points_[offset_++] = point;
93 }
94 }
95
96 const std::vector<Point>& LineStripVertexWriter::GetOversizedBuffer() const {
97 return overflow_;
98 }
99
100 std::pair<size_t, size_t> LineStripVertexWriter::GetVertexCount() const {
101 return std::make_pair(offset_, overflow_.size());
102 }
103
104 /////////// GLESVertexWriter ///////////
105
106 GLESVertexWriter::GLESVertexWriter(std::vector<Point>& points,
107 std::vector<uint16_t>& indices)
108 : points_(points), indices_(indices) {}
109
110 void GLESVertexWriter::EndContour() {
111 if (points_.size() == 0u || contour_start_ == points_.size() - 1) {
112 // Empty or first contour.
113 return;
114 }
115
116 auto start = contour_start_;
117 auto end = points_.size() - 1;
118 // All filled paths are drawn as if they are closed, but if
119 // there is an explicit close then a lineTo to the origin
120 // is inserted. This point isn't strictly necesary to
121 // correctly render the shape and can be dropped.
122 if (points_[end] == points_[start]) {
123 end--;
124 }
125
126 // Triangle strip break for subsequent contours
127 if (contour_start_ != 0) {
128 auto back = indices_.back();
129 indices_.push_back(back);
130 indices_.push_back(start);
131 indices_.push_back(start);
132
133 // If the contour has an odd number of points, insert an extra point when
134 // bridging to the next contour to preserve the correct triangle winding
135 // order.
136 if (previous_contour_odd_points_) {
137 indices_.push_back(start);
138 }
139 } else {
140 indices_.push_back(start);
141 }
142
143 size_t a = start + 1;
144 size_t b = end;
145 while (a < b) {
146 indices_.push_back(a);
147 indices_.push_back(b);
148 a++;
149 b--;
150 }
151 if (a == b) {
152 indices_.push_back(a);
153 previous_contour_odd_points_ = false;
154 } else {
155 previous_contour_odd_points_ = true;
156 }
157 contour_start_ = points_.size();
158 }
159
160 void GLESVertexWriter::Write(Point point) {
161 points_.push_back(point);
162 }
163
164 /*
165 * Based on: https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Specific_cases
166 */
167
168 static inline Scalar LinearSolve(Scalar t, Scalar p0, Scalar p1) {
169 return p0 + t * (p1 - p0);
170 }
171
172 static inline Scalar QuadraticSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2) {
173 return (1 - t) * (1 - t) * p0 + //
174 2 * (1 - t) * t * p1 + //
175 t * t * p2;
176 }
177
178 static inline Scalar QuadraticSolveDerivative(Scalar t,
179 Scalar p0,
180 Scalar p1,
181 Scalar p2) {
182 return 2 * (1 - t) * (p1 - p0) + //
183 2 * t * (p2 - p1);
184 }
185
186 static inline Scalar CubicSolve(Scalar t,
187 Scalar p0,
188 Scalar p1,
189 Scalar p2,
190 Scalar p3) {
191 return (1 - t) * (1 - t) * (1 - t) * p0 + //
192 3 * (1 - t) * (1 - t) * t * p1 + //
193 3 * (1 - t) * t * t * p2 + //
194 t * t * t * p3;
195 }
196
197 static inline Scalar CubicSolveDerivative(Scalar t,
198 Scalar p0,
199 Scalar p1,
200 Scalar p2,
201 Scalar p3) {
202 return -3 * p0 * (1 - t) * (1 - t) + //
203 p1 * (3 * (1 - t) * (1 - t) - 6 * (1 - t) * t) +
204 p2 * (6 * (1 - t) * t - 3 * t * t) + //
205 3 * p3 * t * t;
206 }
207
208 Point LinearPathComponent::Solve(Scalar time) const {
209 return {
210 LinearSolve(time, p1.x, p2.x), // x
211 LinearSolve(time, p1.y, p2.y), // y
212 };
213 }
214
215 void LinearPathComponent::AppendPolylinePoints(
216 std::vector<Point>& points) const {
217 if (points.size() == 0 || points.back() != p2) {
218 points.push_back(p2);
219 }
220 }
221
222 std::vector<Point> LinearPathComponent::Extrema() const {
223 return {p1, p2};
224 }
225
226 std::optional<Vector2> LinearPathComponent::GetStartDirection() const {
227 if (p1 == p2) {
228 return std::nullopt;
229 }
230 return (p1 - p2).Normalize();
231 }
232
233 std::optional<Vector2> LinearPathComponent::GetEndDirection() const {
234 if (p1 == p2) {
235 return std::nullopt;
236 }
237 return (p2 - p1).Normalize();
238 }
239
240 Point QuadraticPathComponent::Solve(Scalar time) const {
241 return {
242 QuadraticSolve(time, p1.x, cp.x, p2.x), // x
243 QuadraticSolve(time, p1.y, cp.y, p2.y), // y
244 };
245 }
246
247 Point QuadraticPathComponent::SolveDerivative(Scalar time) const {
248 return {
249 QuadraticSolveDerivative(time, p1.x, cp.x, p2.x), // x
250 QuadraticSolveDerivative(time, p1.y, cp.y, p2.y), // y
251 };
252 }
253
254 void QuadraticPathComponent::ToLinearPathComponents(
255 Scalar scale,
256 VertexWriter& writer) const {
257 Scalar line_count = std::ceilf(ComputeQuadradicSubdivisions(scale, *this));
258 for (size_t i = 1; i < line_count; i += 1) {
259 writer.Write(Solve(i / line_count));
260 }
261 writer.Write(p2);
262 }
263
264 void QuadraticPathComponent::AppendPolylinePoints(
265 Scalar scale_factor,
266 std::vector<Point>& points) const {
267 ToLinearPathComponents(scale_factor, [&points](const Point& point) {
268 points.emplace_back(point);
269 });
270 }
271
272 void QuadraticPathComponent::ToLinearPathComponents(
273 Scalar scale_factor,
274 const PointProc& proc) const {
275 Scalar line_count =
276 std::ceilf(ComputeQuadradicSubdivisions(scale_factor, *this));
277 for (size_t i = 1; i < line_count; i += 1) {
278 proc(Solve(i / line_count));
279 }
280 proc(p2);
281 }
282
283 size_t QuadraticPathComponent::CountLinearPathComponents(Scalar scale) const {
284 return std::ceilf(ComputeQuadradicSubdivisions(scale, *this)) + 2;
285 }
286
287 std::vector<Point> QuadraticPathComponent::Extrema() const {
288 CubicPathComponent elevated(*this);
289 return elevated.Extrema();
290 }
291
292 std::optional<Vector2> QuadraticPathComponent::GetStartDirection() const {
293 if (p1 != cp) {
294 return (p1 - cp).Normalize();
295 }
296 if (p1 != p2) {
297 return (p1 - p2).Normalize();
298 }
299 return std::nullopt;
300 }
301
302 std::optional<Vector2> QuadraticPathComponent::GetEndDirection() const {
303 if (p2 != cp) {
304 return (p2 - cp).Normalize();
305 }
306 if (p2 != p1) {
307 return (p2 - p1).Normalize();
308 }
309 return std::nullopt;
310 }
311
312 Point CubicPathComponent::Solve(Scalar time) const {
313 return {
314 CubicSolve(time, p1.x, cp1.x, cp2.x, p2.x), // x
315 CubicSolve(time, p1.y, cp1.y, cp2.y, p2.y), // y
316 };
317 }
318
319 Point CubicPathComponent::SolveDerivative(Scalar time) const {
320 return {
321 CubicSolveDerivative(time, p1.x, cp1.x, cp2.x, p2.x), // x
322 CubicSolveDerivative(time, p1.y, cp1.y, cp2.y, p2.y), // y
323 };
324 }
325
326 void CubicPathComponent::AppendPolylinePoints(
327 Scalar scale,
328 std::vector<Point>& points) const {
329 ToLinearPathComponents(
330 scale, [&points](const Point& point) { points.emplace_back(point); });
331 }
332
333 void CubicPathComponent::ToLinearPathComponents(Scalar scale,
334 VertexWriter& writer) const {
335 Scalar line_count = std::ceilf(ComputeCubicSubdivisions(scale, *this));
336 for (size_t i = 1; i < line_count; i++) {
337 writer.Write(Solve(i / line_count));
338 }
339 writer.Write(p2);
340 }
341
342 size_t CubicPathComponent::CountLinearPathComponents(Scalar scale) const {
343 return std::ceilf(ComputeCubicSubdivisions(scale, *this)) + 2;
344 }
345
346 inline QuadraticPathComponent CubicPathComponent::Lower() const {
347 return QuadraticPathComponent(3.0 * (cp1 - p1), 3.0 * (cp2 - cp1),
348 3.0 * (p2 - cp2));
349 }
350
351 CubicPathComponent CubicPathComponent::Subsegment(Scalar t0, Scalar t1) const {
352 auto p0 = Solve(t0);
353 auto p3 = Solve(t1);
354 auto d = Lower();
355 auto scale = (t1 - t0) * (1.0 / 3.0);
356 auto p1 = p0 + scale * d.Solve(t0);
357 auto p2 = p3 - scale * d.Solve(t1);
358 return CubicPathComponent(p0, p1, p2, p3);
359 }
360
361 void CubicPathComponent::ToLinearPathComponents(Scalar scale,
362 const PointProc& proc) const {
363 Scalar line_count = std::ceilf(ComputeCubicSubdivisions(scale, *this));
364 for (size_t i = 1; i < line_count; i++) {
365 proc(Solve(i / line_count));
366 }
367 proc(p2);
368 }
369
370 static inline bool NearEqual(Scalar a, Scalar b, Scalar epsilon) {
371 return (a > (b - epsilon)) && (a < (b + epsilon));
372 }
373
374 static inline bool NearZero(Scalar a) {
375 return NearEqual(a, 0.0, 1e-12);
376 }
377
378 static void CubicPathBoundingPopulateValues(std::vector<Scalar>& values,
379 Scalar p1,
380 Scalar p2,
381 Scalar p3,
382 Scalar p4) {
383 const Scalar a = 3.0 * (-p1 + 3.0 * p2 - 3.0 * p3 + p4);
384 const Scalar b = 6.0 * (p1 - 2.0 * p2 + p3);
385 const Scalar c = 3.0 * (p2 - p1);
386
387 /*
388 * Boundary conditions.
389 */
390 if (NearZero(a)) {
391 if (NearZero(b)) {
392 return;
393 }
394
395 Scalar t = -c / b;
396 if (t >= 0.0 && t <= 1.0) {
397 values.emplace_back(t);
398 }
399 return;
400 }
401
402 Scalar b2Minus4AC = (b * b) - (4.0 * a * c);
403
404 if (b2Minus4AC < 0.0) {
405 return;
406 }
407
408 Scalar rootB2Minus4AC = ::sqrt(b2Minus4AC);
409
410 /* From Numerical Recipes in C.
411 *
412 * q = -1/2 (b + sign(b) sqrt[b^2 - 4ac])
413 * x1 = q / a
414 * x2 = c / q
415 */
416 Scalar q = (b < 0) ? -(b - rootB2Minus4AC) / 2 : -(b + rootB2Minus4AC) / 2;
417
418 {
419 Scalar t = q / a;
420 if (t >= 0.0 && t <= 1.0) {
421 values.emplace_back(t);
422 }
423 }
424
425 {
426 Scalar t = c / q;
427 if (t >= 0.0 && t <= 1.0) {
428 values.emplace_back(t);
429 }
430 }
431 }
432
433 std::vector<Point> CubicPathComponent::Extrema() const {
434 /*
435 * As described in: https://pomax.github.io/bezierinfo/#extremities
436 */
437 std::vector<Scalar> values;
438
439 CubicPathBoundingPopulateValues(values, p1.x, cp1.x, cp2.x, p2.x);
440 CubicPathBoundingPopulateValues(values, p1.y, cp1.y, cp2.y, p2.y);
441
442 std::vector<Point> points = {p1, p2};
443
444 for (const auto& value : values) {
445 points.emplace_back(Solve(value));
446 }
447
448 return points;
449 }
450
451 std::optional<Vector2> CubicPathComponent::GetStartDirection() const {
452 if (p1 != cp1) {
453 return (p1 - cp1).Normalize();
454 }
455 if (p1 != cp2) {
456 return (p1 - cp2).Normalize();
457 }
458 if (p1 != p2) {
459 return (p1 - p2).Normalize();
460 }
461 return std::nullopt;
462 }
463
464 std::optional<Vector2> CubicPathComponent::GetEndDirection() const {
465 if (p2 != cp2) {
466 return (p2 - cp2).Normalize();
467 }
468 if (p2 != cp1) {
469 return (p2 - cp1).Normalize();
470 }
471 if (p2 != p1) {
472 return (p2 - p1).Normalize();
473 }
474 return std::nullopt;
475 }
476
477 } // namespace impeller
impeller::GLESVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:160
impeller::ComputeQuadradicSubdivisions
Scalar ComputeQuadradicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2)
Definition: wangs_formula.cc:34
impeller::TPoint::y
Type y
Definition: point.h:31
impeller::FanVertexWriter::GetIndexCount
size_t GetIndexCount() const
Definition: path_component.cc:22
impeller::Scalar
float Scalar
Definition: scalar.h:18
impeller::CubicPathComponent::Subsegment
CubicPathComponent Subsegment(Scalar t0, Scalar t1) const
Definition: path_component.cc:351
impeller::VertexWriter::Write
virtual void Write(Point point)=0
impeller::CubicPathComponent::p1
Point p1
Definition: path_component.h:176
impeller::NearZero
static bool NearZero(Scalar a)
Definition: path_component.cc:374
impeller::LinearPathComponent::p2
Point p2
Definition: path_component.h:112
impeller::QuadraticPathComponent::p1
Point p1
Definition: path_component.h:136
impeller::CubicPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:451
value
int32_t value
Definition: dl_golden_unittests.cc:444
impeller::CubicPathComponent::cp2
Point cp2
Definition: path_component.h:180
impeller::CubicPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale, std::vector< Point > &points) const
Definition: path_component.cc:326
impeller::LinearPathComponent::AppendPolylinePoints
void AppendPolylinePoints(std::vector< Point > &points) const
Definition: path_component.cc:215
impeller::QuadraticPathComponent::cp
Point cp
Definition: path_component.h:138
impeller::StripVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:77
impeller::QuadraticPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:292
impeller::CubicPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:312
impeller::QuadraticPathComponent::CountLinearPathComponents
size_t CountLinearPathComponents(Scalar scale) const
Definition: path_component.cc:283
impeller::CubicPathBoundingPopulateValues
static void CubicPathBoundingPopulateValues(std::vector< Scalar > &values, Scalar p1, Scalar p2, Scalar p3, Scalar p4)
Definition: path_component.cc:378
impeller::QuadraticPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:302
impeller::StripVertexWriter::~StripVertexWriter
~StripVertexWriter()
impeller::QuadraticSolve
static Scalar QuadraticSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2)
Definition: path_component.cc:172
impeller::CubicSolveDerivative
static Scalar CubicSolveDerivative(Scalar t, Scalar p0, Scalar p1, Scalar p2, Scalar p3)
Definition: path_component.cc:197
impeller::LineStripVertexWriter::GetOversizedBuffer
const std::vector< Point > & GetOversizedBuffer() const
Definition: path_component.cc:96
impeller::QuadraticPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale_factor, const PointProc &proc) const
Definition: path_component.cc:272
impeller::QuadraticPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:154
impeller::FanVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:33
impeller::QuadraticPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:247
impeller::CubicPathComponent::cp1
Point cp1
Definition: path_component.h:178
impeller::LinearPathComponent::p1
Point p1
Definition: path_component.h:111
impeller::CubicSolve
static Scalar CubicSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2, Scalar p3)
Definition: path_component.cc:186
impeller::FanVertexWriter::FanVertexWriter
FanVertexWriter(Point *point_buffer, uint16_t *index_buffer)
Definition: path_component.cc:17
impeller::LinearPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:226
impeller::QuadraticPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:240
impeller::GLESVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:110
impeller::StripVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:50
impeller::CubicPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:319
impeller::LineStripVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:86
impeller::StripVertexWriter::StripVertexWriter
StripVertexWriter(Point *point_buffer, uint16_t *index_buffer)
Definition: path_component.cc:40
impeller::QuadraticPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:287
impeller::FanVertexWriter::~FanVertexWriter
~FanVertexWriter()
impeller::CubicPathComponent::CountLinearPathComponents
size_t CountLinearPathComponents(Scalar scale) const
Definition: path_component.cc:342
impeller::CubicPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:464
impeller::TPoint::x
Type x
Definition: point.h:30
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent()
Definition: path_component.h:184
impeller::CubicPathComponent
Definition: path_component.h:174
scalar.h
impeller::CubicPathComponent::ToLinearPathComponents
void ToLinearPathComponents(Scalar scale, const PointProc &proc) const
Definition: path_component.cc:361
impeller::NearEqual
static bool NearEqual(Scalar a, Scalar b, Scalar epsilon)
Definition: path_component.cc:370
impeller::QuadraticPathComponent::AppendPolylinePoints
void AppendPolylinePoints(Scalar scale_factor, std::vector< Point > &points) const
Definition: path_component.cc:264
impeller::VertexWriter
An interface for generating a multi contour polyline as a triangle strip.
Definition: path_component.h:20
impeller::ComputeCubicSubdivisions
Scalar ComputeCubicSubdivisions(Scalar scale_factor, Point p0, Point p1, Point p2, Point p3)
Definition: wangs_formula.cc:23
impeller::QuadraticSolveDerivative
static Scalar QuadraticSolveDerivative(Scalar t, Scalar p0, Scalar p1, Scalar p2)
Definition: path_component.cc:178
impeller::QuadraticPathComponent::p2
Point p2
Definition: path_component.h:140
impeller::TPoint< Scalar >
impeller::saturated::b
SI b
Definition: saturated_math.h:87
impeller::FanVertexWriter::EndContour
void EndContour() override
Definition: path_component.cc:26
scale
const Scalar scale
Definition: stroke_path_geometry.cc:316
impeller::LineStripVertexWriter::LineStripVertexWriter
LineStripVertexWriter(std::vector< Point > &points)
Definition: path_component.cc:83
impeller::LineStripVertexWriter::Write
void Write(Point point) override
Definition: path_component.cc:88
impeller::CubicPathComponent::PointProc
std::function< void(const Point &point)> PointProc
Definition: path_component.h:203
impeller::CubicPathComponent::p2
Point p2
Definition: path_component.h:182
impeller::CubicPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:433
impeller::StripVertexWriter::GetIndexCount
size_t GetIndexCount() const
Definition: path_component.cc:46
impeller::GLESVertexWriter::GLESVertexWriter
GLESVertexWriter(std::vector< Point > &points, std::vector< uint16_t > &indices)
Definition: path_component.cc:106
path_component.h
impeller::LinearPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:233
impeller
Definition: allocation.cc:12
impeller::QuadraticPathComponent
Definition: path_component.h:134
impeller::LineStripVertexWriter::GetVertexCount
std::pair< size_t, size_t > GetVertexCount() const
Definition: path_component.cc:100
wangs_formula.h
impeller::LinearPathComponent::Solve
Point Solve(Scalar time) const
Definition: path_component.cc:208
impeller::LinearPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:222
impeller::LinearSolve
static Scalar LinearSolve(Scalar t, Scalar p0, Scalar p1)
Definition: path_component.cc:168