| 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 namespace impeller {
10
11 /*
12 * Based on: https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Specific_cases
13 */
14
15 static inline Scalar LinearSolve(Scalar t, Scalar p0, Scalar p1) {
16 return p0 + t * (p1 - p0);
17 }
18
19 static inline Scalar QuadraticSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2) {
20 return (1 - t) * (1 - t) * p0 + //
21 2 * (1 - t) * t * p1 + //
22 t * t * p2;
23 }
24
25 static inline Scalar QuadraticSolveDerivative(Scalar t,
26 Scalar p0,
27 Scalar p1,
28 Scalar p2) {
29 return 2 * (1 - t) * (p1 - p0) + //
30 2 * t * (p2 - p1);
31 }
32
33 static inline Scalar CubicSolve(Scalar t,
34 Scalar p0,
35 Scalar p1,
36 Scalar p2,
37 Scalar p3) {
38 return (1 - t) * (1 - t) * (1 - t) * p0 + //
39 3 * (1 - t) * (1 - t) * t * p1 + //
40 3 * (1 - t) * t * t * p2 + //
41 t * t * t * p3;
42 }
43
44 static inline Scalar CubicSolveDerivative(Scalar t,
45 Scalar p0,
46 Scalar p1,
47 Scalar p2,
48 Scalar p3) {
49 return -3 * p0 * (1 - t) * (1 - t) + //
50 p1 * (3 * (1 - t) * (1 - t) - 6 * (1 - t) * t) +
51 p2 * (6 * (1 - t) * t - 3 * t * t) + //
52 3 * p3 * t * t;
53 }
54
55 Point LinearPathComponent::Solve(Scalar time) const {
56 return {
57 LinearSolve(time, p1.x, p2.x), // x
58 LinearSolve(time, p1.y, p2.y), // y
59 };
60 }
61
62 std::vector<Point> LinearPathComponent::CreatePolyline() const {
63 return {p2};
64 }
65
66 std::vector<Point> LinearPathComponent::Extrema() const {
67 return {p1, p2};
68 }
69
70 std::optional<Vector2> LinearPathComponent::GetStartDirection() const {
71 if (p1 == p2) {
72 return std::nullopt;
73 }
74 return (p1 - p2).Normalize();
75 }
76
77 std::optional<Vector2> LinearPathComponent::GetEndDirection() const {
78 if (p1 == p2) {
79 return std::nullopt;
80 }
81 return (p2 - p1).Normalize();
82 }
83
84 Point QuadraticPathComponent::Solve(Scalar time) const {
85 return {
86 QuadraticSolve(time, p1.x, cp.x, p2.x), // x
87 QuadraticSolve(time, p1.y, cp.y, p2.y), // y
88 };
89 }
90
91 Point QuadraticPathComponent::SolveDerivative(Scalar time) const {
92 return {
93 QuadraticSolveDerivative(time, p1.x, cp.x, p2.x), // x
94 QuadraticSolveDerivative(time, p1.y, cp.y, p2.y), // y
95 };
96 }
97
98 static Scalar ApproximateParabolaIntegral(Scalar x) {
99 constexpr Scalar d = 0.67;
100 return x / (1.0 - d + sqrt(sqrt(pow(d, 4) + 0.25 * x * x)));
101 }
102
103 std::vector<Point> QuadraticPathComponent::CreatePolyline(Scalar scale) const {
104 std::vector<Point> points;
105 FillPointsForPolyline(points, scale);
106 return points;
107 }
108
109 void QuadraticPathComponent::FillPointsForPolyline(std::vector<Point>& points,
110 Scalar scale_factor) const {
111 auto tolerance = kDefaultCurveTolerance / scale_factor;
112 auto sqrt_tolerance = sqrt(tolerance);
113
114 auto d01 = cp - p1;
115 auto d12 = p2 - cp;
116 auto dd = d01 - d12;
117 auto cross = (p2 - p1).Cross(dd);
118 auto x0 = d01.Dot(dd) * 1 / cross;
119 auto x2 = d12.Dot(dd) * 1 / cross;
120 auto scale = std::abs(cross / (hypot(dd.x, dd.y) * (x2 - x0)));
121
122 auto a0 = ApproximateParabolaIntegral(x0);
123 auto a2 = ApproximateParabolaIntegral(x2);
124 Scalar val = 0.f;
125 if (std::isfinite(scale)) {
126 auto da = std::abs(a2 - a0);
127 auto sqrt_scale = sqrt(scale);
128 if ((x0 < 0 && x2 < 0) || (x0 >= 0 && x2 >= 0)) {
129 val = da * sqrt_scale;
130 } else {
131 // cusp case
132 auto xmin = sqrt_tolerance / sqrt_scale;
133 val = sqrt_tolerance * da / ApproximateParabolaIntegral(xmin);
134 }
135 }
136 auto u0 = ApproximateParabolaIntegral(a0);
137 auto u2 = ApproximateParabolaIntegral(a2);
138 auto uscale = 1 / (u2 - u0);
139
140 auto line_count = std::max(1., ceil(0.5 * val / sqrt_tolerance));
141 auto step = 1 / line_count;
142 for (size_t i = 1; i < line_count; i += 1) {
143 auto u = i * step;
144 auto a = a0 + (a2 - a0) * u;
145 auto t = (ApproximateParabolaIntegral(a) - u0) * uscale;
146 points.emplace_back(Solve(t));
147 }
148 points.emplace_back(p2);
149 }
150
151 std::vector<Point> QuadraticPathComponent::Extrema() const {
152 CubicPathComponent elevated(*this);
153 return elevated.Extrema();
154 }
155
156 std::optional<Vector2> QuadraticPathComponent::GetStartDirection() const {
157 if (p1 != cp) {
158 return (p1 - cp).Normalize();
159 }
160 if (p1 != p2) {
161 return (p1 - p2).Normalize();
162 }
163 return std::nullopt;
164 }
165
166 std::optional<Vector2> QuadraticPathComponent::GetEndDirection() const {
167 if (p2 != cp) {
168 return (p2 - cp).Normalize();
169 }
170 if (p2 != p1) {
171 return (p2 - p1).Normalize();
172 }
173 return std::nullopt;
174 }
175
176 Point CubicPathComponent::Solve(Scalar time) const {
177 return {
178 CubicSolve(time, p1.x, cp1.x, cp2.x, p2.x), // x
179 CubicSolve(time, p1.y, cp1.y, cp2.y, p2.y), // y
180 };
181 }
182
183 Point CubicPathComponent::SolveDerivative(Scalar time) const {
184 return {
185 CubicSolveDerivative(time, p1.x, cp1.x, cp2.x, p2.x), // x
186 CubicSolveDerivative(time, p1.y, cp1.y, cp2.y, p2.y), // y
187 };
188 }
189
190 std::vector<Point> CubicPathComponent::CreatePolyline(Scalar scale) const {
191 auto quads = ToQuadraticPathComponents(.1);
192 std::vector<Point> points;
193 for (const auto& quad : quads) {
194 quad.FillPointsForPolyline(points, scale);
195 }
196 return points;
197 }
198
199 inline QuadraticPathComponent CubicPathComponent::Lower() const {
200 return QuadraticPathComponent(3.0 * (cp1 - p1), 3.0 * (cp2 - cp1),
201 3.0 * (p2 - cp2));
202 }
203
204 CubicPathComponent CubicPathComponent::Subsegment(Scalar t0, Scalar t1) const {
205 auto p0 = Solve(t0);
206 auto p3 = Solve(t1);
207 auto d = Lower();
208 auto scale = (t1 - t0) * (1.0 / 3.0);
209 auto p1 = p0 + scale * d.Solve(t0);
210 auto p2 = p3 - scale * d.Solve(t1);
211 return CubicPathComponent(p0, p1, p2, p3);
212 }
213
214 std::vector<QuadraticPathComponent>
215 CubicPathComponent::ToQuadraticPathComponents(Scalar accuracy) const {
216 std::vector<QuadraticPathComponent> quads;
217 // The maximum error, as a vector from the cubic to the best approximating
218 // quadratic, is proportional to the third derivative, which is constant
219 // across the segment. Thus, the error scales down as the third power of
220 // the number of subdivisions. Our strategy then is to subdivide `t` evenly.
221 //
222 // This is an overestimate of the error because only the component
223 // perpendicular to the first derivative is important. But the simplicity is
224 // appealing.
225
226 // This magic number is the square of 36 / sqrt(3).
227 // See: http://caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
228 auto max_hypot2 = 432.0 * accuracy * accuracy;
229 auto p1x2 = 3.0 * cp1 - p1;
230 auto p2x2 = 3.0 * cp2 - p2;
231 auto p = p2x2 - p1x2;
232 auto err = p.Dot(p);
233 auto quad_count = std::max(1., ceil(pow(err / max_hypot2, 1. / 6.0)));
234
235 for (size_t i = 0; i < quad_count; i++) {
236 auto t0 = i / quad_count;
237 auto t1 = (i + 1) / quad_count;
238 auto seg = Subsegment(t0, t1);
239 auto p1x2 = 3.0 * seg.cp1 - seg.p1;
240 auto p2x2 = 3.0 * seg.cp2 - seg.p2;
241 quads.emplace_back(
242 QuadraticPathComponent(seg.p1, ((p1x2 + p2x2) / 4.0), seg.p2));
243 }
244 return quads;
245 }
246
247 static inline bool NearEqual(Scalar a, Scalar b, Scalar epsilon) {
248 return (a > (b - epsilon)) && (a < (b + epsilon));
249 }
250
251 static inline bool NearZero(Scalar a) {
252 return NearEqual(a, 0.0, 1e-12);
253 }
254
255 static void CubicPathBoundingPopulateValues(std::vector<Scalar>& values,
256 Scalar p1,
257 Scalar p2,
258 Scalar p3,
259 Scalar p4) {
260 const Scalar a = 3.0 * (-p1 + 3.0 * p2 - 3.0 * p3 + p4);
261 const Scalar b = 6.0 * (p1 - 2.0 * p2 + p3);
262 const Scalar c = 3.0 * (p2 - p1);
263
264 /*
265 * Boundary conditions.
266 */
267 if (NearZero(a)) {
268 if (NearZero(b)) {
269 return;
270 }
271
272 Scalar t = -c / b;
273 if (t >= 0.0 && t <= 1.0) {
274 values.emplace_back(t);
275 }
276 return;
277 }
278
279 Scalar b2Minus4AC = (b * b) - (4.0 * a * c);
280
281 if (b2Minus4AC < 0.0) {
282 return;
283 }
284
285 Scalar rootB2Minus4AC = ::sqrt(b2Minus4AC);
286
287 /* From Numerical Recipes in C.
288 *
289 * q = -1/2 (b + sign(b) sqrt[b^2 - 4ac])
290 * x1 = q / a
291 * x2 = c / q
292 */
293 Scalar q = (b < 0) ? -(b - rootB2Minus4AC) / 2 : -(b + rootB2Minus4AC) / 2;
294
295 {
296 Scalar t = q / a;
297 if (t >= 0.0 && t <= 1.0) {
298 values.emplace_back(t);
299 }
300 }
301
302 {
303 Scalar t = c / q;
304 if (t >= 0.0 && t <= 1.0) {
305 values.emplace_back(t);
306 }
307 }
308 }
309
310 std::vector<Point> CubicPathComponent::Extrema() const {
311 /*
312 * As described in: https://pomax.github.io/bezierinfo/#extremities
313 */
314 std::vector<Scalar> values;
315
316 CubicPathBoundingPopulateValues(values, p1.x, cp1.x, cp2.x, p2.x);
317 CubicPathBoundingPopulateValues(values, p1.y, cp1.y, cp2.y, p2.y);
318
319 std::vector<Point> points = {p1, p2};
320
321 for (const auto& value : values) {
322 points.emplace_back(Solve(value));
323 }
324
325 return points;
326 }
327
328 std::optional<Vector2> CubicPathComponent::GetStartDirection() const {
329 if (p1 != cp1) {
330 return (p1 - cp1).Normalize();
331 }
332 if (p1 != cp2) {
333 return (p1 - cp2).Normalize();
334 }
335 if (p1 != p2) {
336 return (p1 - p2).Normalize();
337 }
338 return std::nullopt;
339 }
340
341 std::optional<Vector2> CubicPathComponent::GetEndDirection() const {
342 if (p2 != cp2) {
343 return (p2 - cp2).Normalize();
344 }
345 if (p2 != cp1) {
346 return (p2 - cp1).Normalize();
347 }
348 if (p2 != p1) {
349 return (p2 - p1).Normalize();
350 }
351 return std::nullopt;
352 }
353
354 std::optional<Vector2> PathComponentStartDirectionVisitor::operator()(
355 const LinearPathComponent* component) {
356 if (!component) {
357 return std::nullopt;
358 }
359 return component->GetStartDirection();
360 }
361
362 std::optional<Vector2> PathComponentStartDirectionVisitor::operator()(
363 const QuadraticPathComponent* component) {
364 if (!component) {
365 return std::nullopt;
366 }
367 return component->GetStartDirection();
368 }
369
370 std::optional<Vector2> PathComponentStartDirectionVisitor::operator()(
371 const CubicPathComponent* component) {
372 if (!component) {
373 return std::nullopt;
374 }
375 return component->GetStartDirection();
376 }
377
378 std::optional<Vector2> PathComponentEndDirectionVisitor::operator()(
379 const LinearPathComponent* component) {
380 if (!component) {
381 return std::nullopt;
382 }
383 return component->GetEndDirection();
384 }
385
386 std::optional<Vector2> PathComponentEndDirectionVisitor::operator()(
387 const QuadraticPathComponent* component) {
388 if (!component) {
389 return std::nullopt;
390 }
391 return component->GetEndDirection();
392 }
393
394 std::optional<Vector2> PathComponentEndDirectionVisitor::operator()(
395 const CubicPathComponent* component) {
396 if (!component) {
397 return std::nullopt;
398 }
399 return component->GetEndDirection();
400 }
401
402 } // 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
impeller::LinearPathComponent
Definition: path_component.h:27
impeller::TPoint::y
Type y
Definition: point.h:24
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::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::NearZero
static bool NearZero(Scalar a)
Definition: path_component.cc:251
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::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::CubicPathBoundingPopulateValues
static void CubicPathBoundingPopulateValues(std::vector< Scalar > &values, Scalar p1, Scalar p2, Scalar p3, Scalar p4)
Definition: path_component.cc:255
impeller::QuadraticPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:166
impeller::QuadraticSolve
static Scalar QuadraticSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2)
Definition: path_component.cc:19
impeller::TPoint::Dot
constexpr Type Dot(const TPoint &p) const
Definition: point.h:213
impeller::CubicSolveDerivative
static Scalar CubicSolveDerivative(Scalar t, Scalar p0, Scalar p1, Scalar p2, Scalar p3)
Definition: path_component.cc:44
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::CubicSolve
static Scalar CubicSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2, Scalar p3)
Definition: path_component.cc:33
impeller::LinearPathComponent::GetStartDirection
std::optional< Vector2 > GetStartDirection() const
Definition: path_component.cc:70
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::CubicPathComponent::SolveDerivative
Point SolveDerivative(Scalar time) const
Definition: path_component.cc:183
impeller::QuadraticPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:151
impeller::CubicPathComponent::GetEndDirection
std::optional< Vector2 > GetEndDirection() const
Definition: path_component.cc:341
impeller::TPoint::x
Type x
Definition: point.h:23
impeller::CubicPathComponent::CubicPathComponent
CubicPathComponent()
Definition: path_component.h:96
impeller::CubicPathComponent
Definition: path_component.h:90
impeller::NearEqual
static bool NearEqual(Scalar a, Scalar b, Scalar epsilon)
Definition: path_component.cc:247
impeller::QuadraticSolveDerivative
static Scalar QuadraticSolveDerivative(Scalar t, Scalar p0, Scalar p1, Scalar p2)
Definition: path_component.cc:25
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::CubicPathComponent::p2
Point p2
Definition: path_component.h:94
impeller::CubicPathComponent::Extrema
std::vector< Point > Extrema() const
Definition: path_component.cc:310
path_component.h
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::ApproximateParabolaIntegral
static Scalar ApproximateParabolaIntegral(Scalar x)
Definition: path_component.cc:98
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::LinearSolve
static Scalar LinearSolve(Scalar t, Scalar p0, Scalar p1)
Definition: path_component.cc:15