blob: f9c208386e4a9397cdb8494daf0bc9335ac0a987 [file] [log] [blame] [edit]
// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "path_component.h"
#include <cmath>
namespace impeller {
static const size_t kRecursionLimit = 32;
static const Scalar kCurveCollinearityEpsilon = 1e-30;
static const Scalar kCurveAngleToleranceEpsilon = 0.01;
/*
* Based on: https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Specific_cases
*/
static inline Scalar LinearSolve(Scalar t, Scalar p0, Scalar p1) {
return p0 + t * (p1 - p0);
}
static inline Scalar QuadraticSolve(Scalar t, Scalar p0, Scalar p1, Scalar p2) {
return (1 - t) * (1 - t) * p0 + //
2 * (1 - t) * t * p1 + //
t * t * p2;
}
static inline Scalar QuadraticSolveDerivative(Scalar t,
Scalar p0,
Scalar p1,
Scalar p2) {
return 2 * (1 - t) * (p1 - p0) + //
2 * t * (p2 - p1);
}
static inline Scalar CubicSolve(Scalar t,
Scalar p0,
Scalar p1,
Scalar p2,
Scalar p3) {
return (1 - t) * (1 - t) * (1 - t) * p0 + //
3 * (1 - t) * (1 - t) * t * p1 + //
3 * (1 - t) * t * t * p2 + //
t * t * t * p3;
}
static inline Scalar CubicSolveDerivative(Scalar t,
Scalar p0,
Scalar p1,
Scalar p2,
Scalar p3) {
return -3 * p0 * (1 - t) * (1 - t) + //
p1 * (3 * (1 - t) * (1 - t) - 6 * (1 - t) * t) +
p2 * (6 * (1 - t) * t - 3 * t * t) + //
3 * p3 * t * t;
}
Point LinearPathComponent::Solve(Scalar time) const {
return {
LinearSolve(time, p1.x, p2.x), // x
LinearSolve(time, p1.y, p2.y), // y
};
}
std::vector<Point> LinearPathComponent::CreatePolyline() const {
return {p2};
}
std::vector<Point> LinearPathComponent::Extrema() const {
return {p1, p2};
}
Point QuadraticPathComponent::Solve(Scalar time) const {
return {
QuadraticSolve(time, p1.x, cp.x, p2.x), // x
QuadraticSolve(time, p1.y, cp.y, p2.y), // y
};
}
Point QuadraticPathComponent::SolveDerivative(Scalar time) const {
return {
QuadraticSolveDerivative(time, p1.x, cp.x, p2.x), // x
QuadraticSolveDerivative(time, p1.y, cp.y, p2.y), // y
};
}
std::vector<Point> QuadraticPathComponent::CreatePolyline(
const SmoothingApproximation& approximation) const {
CubicPathComponent elevated(*this);
return elevated.CreatePolyline(approximation);
}
std::vector<Point> QuadraticPathComponent::Extrema() const {
CubicPathComponent elevated(*this);
return elevated.Extrema();
}
Point CubicPathComponent::Solve(Scalar time) const {
return {
CubicSolve(time, p1.x, cp1.x, cp2.x, p2.x), // x
CubicSolve(time, p1.y, cp1.y, cp2.y, p2.y), // y
};
}
Point CubicPathComponent::SolveDerivative(Scalar time) const {
return {
CubicSolveDerivative(time, p1.x, cp1.x, cp2.x, p2.x), // x
CubicSolveDerivative(time, p1.y, cp1.y, cp2.y, p2.y), // y
};
}
/*
* Paul de Casteljau's subdivision with modifications as described in
* http://agg.sourceforge.net/antigrain.com/research/adaptive_bezier/index.html.
* Refer to the diagram on that page for a description of the points.
*/
static void CubicPathSmoothenRecursive(const SmoothingApproximation& approx,
std::vector<Point>& points,
Point p1,
Point p2,
Point p3,
Point p4,
size_t level) {
if (level >= kRecursionLimit) {
return;
}
/*
* Find all midpoints.
*/
auto p12 = (p1 + p2) / 2.0;
auto p23 = (p2 + p3) / 2.0;
auto p34 = (p3 + p4) / 2.0;
auto p123 = (p12 + p23) / 2.0;
auto p234 = (p23 + p34) / 2.0;
auto p1234 = (p123 + p234) / 2.0;
/*
* Attempt approximation using single straight line.
*/
auto d = p4 - p1;
Scalar d2 = fabs(((p2.x - p4.x) * d.y - (p2.y - p4.y) * d.x));
Scalar d3 = fabs(((p3.x - p4.x) * d.y - (p3.y - p4.y) * d.x));
Scalar da1 = 0;
Scalar da2 = 0;
Scalar k = 0;
switch ((static_cast<int>(d2 > kCurveCollinearityEpsilon) << 1) +
static_cast<int>(d3 > kCurveCollinearityEpsilon)) {
case 0:
/*
* All collinear OR p1 == p4.
*/
k = d.x * d.x + d.y * d.y;
if (k == 0) {
d2 = p1.GetDistanceSquared(p2);
d3 = p4.GetDistanceSquared(p3);
} else {
k = 1.0 / k;
da1 = p2.x - p1.x;
da2 = p2.y - p1.y;
d2 = k * (da1 * d.x + da2 * d.y);
da1 = p3.x - p1.x;
da2 = p3.y - p1.y;
d3 = k * (da1 * d.x + da2 * d.y);
if (d2 > 0 && d2 < 1 && d3 > 0 && d3 < 1) {
/*
* Simple collinear case, 1---2---3---4. Leave just two endpoints.
*/
return;
}
if (d2 <= 0) {
d2 = p2.GetDistanceSquared(p1);
} else if (d2 >= 1) {
d2 = p2.GetDistanceSquared(p4);
} else {
d2 = p2.GetDistanceSquared({p1.x + d2 * d.x, p1.y + d2 * d.y});
}
if (d3 <= 0) {
d3 = p3.GetDistanceSquared(p1);
} else if (d3 >= 1) {
d3 = p3.GetDistanceSquared(p4);
} else {
d3 = p3.GetDistanceSquared({p1.x + d3 * d.x, p1.y + d3 * d.y});
}
}
if (d2 > d3) {
if (d2 < approx.distance_tolerance_square) {
points.emplace_back(p2);
return;
}
} else {
if (d3 < approx.distance_tolerance_square) {
points.emplace_back(p3);
return;
}
}
break;
case 1:
/*
* p1, p2, p4 are collinear, p3 is significant.
*/
if (d3 * d3 <=
approx.distance_tolerance_square * (d.x * d.x + d.y * d.y)) {
if (approx.angle_tolerance < kCurveAngleToleranceEpsilon) {
points.emplace_back(p23);
return;
}
/*
* Angle Condition.
*/
da1 = ::fabs(::atan2(p4.y - p3.y, p4.x - p3.x) -
::atan2(p3.y - p2.y, p3.x - p2.x));
if (da1 >= kPi) {
da1 = 2.0 * kPi - da1;
}
if (da1 < approx.angle_tolerance) {
points.emplace_back(p2);
points.emplace_back(p3);
return;
}
if (approx.cusp_limit != 0.0) {
if (da1 > approx.cusp_limit) {
points.emplace_back(p3);
return;
}
}
}
break;
case 2:
/*
* p1,p3,p4 are collinear, p2 is significant.
*/
if (d2 * d2 <=
approx.distance_tolerance_square * (d.x * d.x + d.y * d.y)) {
if (approx.angle_tolerance < kCurveAngleToleranceEpsilon) {
points.emplace_back(p23);
return;
}
/*
* Angle Condition.
*/
da1 = ::fabs(::atan2(p3.y - p2.y, p3.x - p2.x) -
::atan2(p2.y - p1.y, p2.x - p1.x));
if (da1 >= kPi) {
da1 = 2.0 * kPi - da1;
}
if (da1 < approx.angle_tolerance) {
points.emplace_back(p2);
points.emplace_back(p3);
return;
}
if (approx.cusp_limit != 0.0) {
if (da1 > approx.cusp_limit) {
points.emplace_back(p2);
return;
}
}
}
break;
case 3:
/*
* Regular case.
*/
if ((d2 + d3) * (d2 + d3) <=
approx.distance_tolerance_square * (d.x * d.x + d.y * d.y)) {
/*
* If the curvature doesn't exceed the distance_tolerance value
* we tend to finish subdivisions.
*/
if (approx.angle_tolerance < kCurveAngleToleranceEpsilon) {
points.emplace_back(p23);
return;
}
/*
* Angle & Cusp Condition.
*/
k = ::atan2(p3.y - p2.y, p3.x - p2.x);
da1 = ::fabs(k - ::atan2(p2.y - p1.y, p2.x - p1.x));
da2 = ::fabs(::atan2(p4.y - p3.y, p4.x - p3.x) - k);
if (da1 >= kPi) {
da1 = 2.0 * kPi - da1;
}
if (da2 >= kPi) {
da2 = 2.0 * kPi - da2;
}
if (da1 + da2 < approx.angle_tolerance) {
/*
* Finally we can stop the recursion.
*/
points.emplace_back(p23);
return;
}
if (approx.cusp_limit != 0.0) {
if (da1 > approx.cusp_limit) {
points.emplace_back(p2);
return;
}
if (da2 > approx.cusp_limit) {
points.emplace_back(p3);
return;
}
}
}
break;
}
/*
* Continue subdivision.
*/
CubicPathSmoothenRecursive(approx, points, p1, p12, p123, p1234, level + 1);
CubicPathSmoothenRecursive(approx, points, p1234, p234, p34, p4, level + 1);
}
std::vector<Point> CubicPathComponent::CreatePolyline(
const SmoothingApproximation& approximation) const {
std::vector<Point> points;
CubicPathSmoothenRecursive(approximation, points, p1, cp1, cp2, p2, 0);
points.emplace_back(p2);
return points;
}
static inline bool NearEqual(Scalar a, Scalar b, Scalar epsilon) {
return (a > (b - epsilon)) && (a < (b + epsilon));
}
static inline bool NearZero(Scalar a) {
return NearEqual(a, 0.0, 1e-12);
}
static void CubicPathBoundingPopulateValues(std::vector<Scalar>& values,
Scalar p1,
Scalar p2,
Scalar p3,
Scalar p4) {
const Scalar a = 3.0 * (-p1 + 3.0 * p2 - 3.0 * p3 + p4);
const Scalar b = 6.0 * (p1 - 2.0 * p2 + p3);
const Scalar c = 3.0 * (p2 - p1);
/*
* Boundary conditions.
*/
if (NearZero(a)) {
if (NearZero(b)) {
return;
}
Scalar t = -c / b;
if (t >= 0.0 && t <= 1.0) {
values.emplace_back(t);
}
return;
}
Scalar b2Minus4AC = (b * b) - (4.0 * a * c);
if (b2Minus4AC < 0.0) {
return;
}
Scalar rootB2Minus4AC = ::sqrt(b2Minus4AC);
{
Scalar t = (-b + rootB2Minus4AC) / (2.0 * a);
if (t >= 0.0 && t <= 1.0) {
values.emplace_back(t);
}
}
{
Scalar t = (-b - rootB2Minus4AC) / (2.0 * a);
if (t >= 0.0 && t <= 1.0) {
values.emplace_back(t);
}
}
}
std::vector<Point> CubicPathComponent::Extrema() const {
/*
* As described in: https://pomax.github.io/bezierinfo/#extremities
*/
std::vector<Scalar> values;
CubicPathBoundingPopulateValues(values, p1.x, cp1.x, cp2.x, p2.x);
CubicPathBoundingPopulateValues(values, p1.y, cp1.y, cp2.y, p2.y);
std::vector<Point> points = {p1, p2};
for (const auto& value : values) {
points.emplace_back(Solve(value));
}
return points;
}
} // namespace impeller