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