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