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