1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
// Copyright 2014 The Chromium 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 "ui/gfx/geometry/cubic_bezier.h"
#include <algorithm>
#include <cmath>
#include "base/logging.h"
namespace gfx {
namespace {
static const double kBezierEpsilon = 1e-7;
static const int MAX_STEPS = 30;
static double eval_bezier(double p1, double p2, double t) {
const double p1_times_3 = 3.0 * p1;
const double p2_times_3 = 3.0 * p2;
const double h3 = p1_times_3;
const double h1 = p1_times_3 - p2_times_3 + 1.0;
const double h2 = p2_times_3 - 6.0 * p1;
return t * (t * (t * h1 + h2) + h3);
}
static double eval_bezier_derivative(double p1, double p2, double t) {
const double h1 = 9.0 * p1 - 9.0 * p2 + 3.0;
const double h2 = 6.0 * p2 - 12.0 * p1;
const double h3 = 3.0 * p1;
return t * (t * h1 + h2) + h3;
}
// Finds t such that eval_bezier(x1, x2, t) = x.
// There is a unique solution if x1 and x2 lie within (0, 1).
static double bezier_interp(double x1,
double x2,
double x) {
DCHECK_GE(1.0, x1);
DCHECK_LE(0.0, x1);
DCHECK_GE(1.0, x2);
DCHECK_LE(0.0, x2);
x1 = std::min(std::max(x1, 0.0), 1.0);
x2 = std::min(std::max(x2, 0.0), 1.0);
x = std::min(std::max(x, 0.0), 1.0);
// We're just going to do bisection for now (for simplicity), but we could
// easily do some newton steps if this turns out to be a bottleneck.
double t = 0.0;
double step = 1.0;
for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) {
const double error = eval_bezier(x1, x2, t) - x;
if (std::abs(error) < kBezierEpsilon)
break;
t += error > 0.0 ? -step : step;
}
// We should have terminated the above loop because we got close to x, not
// because we exceeded MAX_STEPS. Do a DCHECK here to confirm.
DCHECK_GT(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x));
return t;
}
} // namespace
CubicBezier::CubicBezier(double x1, double y1, double x2, double y2)
: x1_(x1),
y1_(y1),
x2_(x2),
y2_(y2) {
InitGradients();
}
CubicBezier::~CubicBezier() {
}
void CubicBezier::InitGradients() {
if (x1_ > 0)
start_gradient_ = y1_ / x1_;
else if (!y1_ && x2_ > 0)
start_gradient_ = y2_ / x2_;
else
start_gradient_ = 0;
if (x2_ < 1)
end_gradient_ = (y2_ - 1) / (x2_ - 1);
else if (x2_ == 1 && x1_ < 1)
end_gradient_ = (y1_ - 1) / (x1_ - 1);
else
end_gradient_ = 0;
}
double CubicBezier::Solve(double x) const {
if (x < 0)
return start_gradient_ * x;
if (x > 1)
return 1.0 + end_gradient_ * (x - 1.0);
return eval_bezier(y1_, y2_, bezier_interp(x1_, x2_, x));
}
double CubicBezier::Slope(double x) const {
double t = bezier_interp(x1_, x2_, x);
double dx_dt = eval_bezier_derivative(x1_, x2_, t);
double dy_dt = eval_bezier_derivative(y1_, y2_, t);
return dy_dt / dx_dt;
}
void CubicBezier::Range(double* min, double* max) const {
*min = 0;
*max = 1;
if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1)
return;
// Represent the function's derivative in the form at^2 + bt + c.
// (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros
// but does not actually give the slope of the curve.)
double a = 3 * (y1_ - y2_) + 1;
double b = 2 * (y2_ - 2 * y1_);
double c = y1_;
// Check if the derivative is constant.
if (std::abs(a) < kBezierEpsilon &&
std::abs(b) < kBezierEpsilon)
return;
// Zeros of the function's derivative.
double t_1 = 0;
double t_2 = 0;
if (std::abs(a) < kBezierEpsilon) {
// The function's derivative is linear.
t_1 = -c / b;
} else {
// The function's derivative is a quadratic. We find the zeros of this
// quadratic using the quadratic formula.
double discriminant = b * b - 4 * a * c;
if (discriminant < 0)
return;
double discriminant_sqrt = sqrt(discriminant);
t_1 = (-b + discriminant_sqrt) / (2 * a);
t_2 = (-b - discriminant_sqrt) / (2 * a);
}
double sol_1 = 0;
double sol_2 = 0;
if (0 < t_1 && t_1 < 1)
sol_1 = eval_bezier(y1_, y2_, t_1);
if (0 < t_2 && t_2 < 1)
sol_2 = eval_bezier(y1_, y2_, t_2);
*min = std::min(std::min(*min, sol_1), sol_2);
*max = std::max(std::max(*max, sol_1), sol_2);
}
} // namespace gfx
|
