1/****************************************************************************
2**
3** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB).
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the Qt3D module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "bezierevaluator_p.h"
41#include <private/keyframe_p.h>
42#include <QtCore/qglobal.h>
43#include <QtCore/qdebug.h>
44
45#include <cmath>
46
47QT_BEGIN_NAMESPACE
48
49namespace {
50
51inline double qCbrt(double x)
52{
53 // Android is just broken and doesn't define cbrt in std namespace
54#if defined(Q_OS_ANDROID)
55 if (x > 0.0)
56 return std::pow(x, 1.0 / 3.0);
57 else if (x < 0.0)
58 return -std::pow(-x, 1.0 / 3.0);
59 else
60 return 0.0;
61#else
62 return std::cbrt(x: x);
63#endif
64}
65
66} // anonymous
67
68namespace Qt3DAnimation {
69namespace Animation {
70
71/*!
72 \internal
73
74 Evaluates the value of the cubic bezier at time \a time.
75 This requires first finding the value of the bezier parameter, u,
76 corresponding to the requested time which should itself be
77 sandwiched by the provided times and keyframes.
78
79 Once u is found, substitute this back into the cubic Bezier
80 equation using the y components of the keyframe control points.
81 */
82float BezierEvaluator::valueForTime(float time) const
83{
84 const float u = parameterForTime(time);
85
86 // Calculate powers of u and (1-u) that we need
87 const float u2 = u * u;
88 const float u3 = u2 * u;
89 const float mu = 1.0f - u;
90 const float mu2 = mu * mu;
91 const float mu3 = mu2 * mu;
92
93 // The cubic Bezier control points
94 const float p0 = m_keyframe0.value;
95 const float p1 = m_keyframe0.rightControlPoint.y();
96 const float p2 = m_keyframe1.leftControlPoint.y();
97 const float p3 = m_keyframe1.value;
98
99 // Evaluate the cubic Bezier function
100 return p0 * mu3 + 3.0f * p1 * mu2 * u + 3.0f * p2 * mu * u2 + p3 * u3;
101}
102
103/*!
104 \internal
105
106 Calculates the value of the Bezier parameter, u, for the
107 requested time which is the x coordinate of the Keyframes.
108
109 Given 4 ordered control points p0, p1, p2, and p3, the cubic
110 Bezier equation is:
111
112 x(u) = (1-u)^3 p0 + 3 (1-u)^2 u p1 + 3 (1-u) u^2 p2 + u^3 p3
113
114 To find the value of u that corresponds with a given x
115 value (time in the case of keyframes), we can expand the
116 above equation, and then collect terms to arrive at:
117
118 0 = a u^3 + b u^2 + c u + d
119
120 where
121
122 a = p3 - p0 + 3 (p1 - p2)
123 b = 3 (p0 - 2 p1 + p2)
124 c = 3 (p1 - p0)
125 d = p0 - x(u)
126
127 We can then use findCubicRoots to locate the single root of
128 this cubic equation found in the range [0,1] used for this
129 section of the FCurve. This works because the FCurve ensures
130 that the function it represents via the Bezier control points
131 in the Keyframes is single valued. (as a function of time).
132 Time, therefore must be single valued on the interval and
133 therefore have a single root for any given time in the interval
134 covered by the Keyframes.
135 */
136float BezierEvaluator::parameterForTime(float time) const
137{
138 Q_ASSERT(time >= m_time0);
139 Q_ASSERT(time <= m_time1);
140
141 const float p0 = m_time0;
142 const float p1 = m_keyframe0.rightControlPoint.x();
143 const float p2 = m_keyframe1.leftControlPoint.x();
144 const float p3 = m_time1;
145
146 const float coeffs[4] = {
147 p0 - time, // d
148 3.0f * (p1 - p0), // c
149 3.0f * (p0 - 2.0f * p1 + p2), // b
150 p3 - p0 + 3.0f * (p1 - p2) // a
151 };
152
153 float roots[3];
154 const int numberOfRoots = findCubicRoots(coefficients: coeffs, roots);
155 for (int i = 0; i < numberOfRoots; ++i) {
156 if (roots[i] >= -0.01f && roots[i] <= 1.01f)
157 return qMin(a: qMax(a: roots[i], b: 0.0f), b: 1.0f);
158 }
159
160 qWarning() << "Failed to find root of cubic bezier at time" << time
161 << "with coeffs: a =" << coeffs[3] << "b =" << coeffs[2]
162 << "c =" << coeffs[1] << "d =" << coeffs[0];
163 return 0.0f;
164}
165
166bool almostZero(float value, float threshold=1e-3f)
167{
168 // 1e-3 might seem excessively fuzzy, but any smaller value will make the
169 // factors a, b, and c large enough to knock out the cubic solver.
170 return value > -threshold && value < threshold;
171}
172
173/*!
174 \internal
175
176 Finds the roots of the cubic equation ax^3 + bx^2 + cx + d = 0 for
177 real coefficients and returns the number of roots. The roots are
178 put into the \a roots array. The coefficients should be passed in
179 as coeffs[0] = d, coeffs[1] = c, coeffs[2] = b, coeffs[3] = a.
180 */
181int BezierEvaluator::findCubicRoots(const float coeffs[4], float roots[3])
182{
183 const float a = coeffs[3];
184 const float b = coeffs[2];
185 const float c = coeffs[1];
186 const float d = coeffs[0];
187
188 // Simple cases with linear, quadratic or invalid equations
189 if (almostZero(value: a)) {
190 if (almostZero(value: b)) {
191 if (almostZero(value: c))
192 return 0;
193
194 roots[0] = -d / c;
195 return 1;
196 }
197 const float discriminant = c * c - 4.f * b * d;
198 if (discriminant < 0.f)
199 return 0;
200
201 if (discriminant == 0.f) {
202 roots[0] = -c / (2.f * b);
203 return 1;
204 }
205
206 roots[0] = (-c + std::sqrt(x: discriminant)) / (2.f * b);
207 roots[1] = (-c - std::sqrt(x: discriminant)) / (2.f * b);
208 return 2;
209 }
210
211 // See https://en.wikipedia.org/wiki/Cubic_function#General_solution_to_the_cubic_equation_with_real_coefficients
212 // for a description. We depress the general cubic to a form that can more easily be solved. Solve it and then
213 // substitue the results back to get the roots of the original cubic.
214 int numberOfRoots = 0;
215 const double oneThird = 1.0 / 3.0;
216 const double piByThree = M_PI / 3.0;
217
218 // Put cubic into normal format: x^3 + Ax^2 + Bx + C = 0
219 const double A = double(b / a);
220 const double B = double(c / a);
221 const double C = double(d / a);
222
223 // Substitute x = y - A/3 to eliminate quadratic term (depressed form):
224 // x^3 + px + q = 0
225 const double Asq = A * A;
226 const double p = oneThird * (-oneThird * Asq + B);
227 const double q = 1.0 / 2.0 * (2.0 / 27.0 * A * Asq - oneThird * A * B + C);
228
229 // Use Cardano's formula
230 const double pCubed = p * p * p;
231 const double discriminant = q * q + pCubed;
232
233 if (almostZero(value: discriminant, threshold: 1e-6f)) {
234 if (qIsNull(d: q)) {
235 // One repeated triple root
236 roots[0] = 0.0;
237 numberOfRoots = 1;
238 } else {
239 // One single and one double root
240 double u = qCbrt(x: -q);
241 roots[0] = 2.0 * u;
242 roots[1] = -u;
243 numberOfRoots = 2;
244 }
245 } else if (discriminant < 0) {
246 // Three real solutions
247 double phi = oneThird * std::acos(x: -q / std::sqrt(x: -pCubed));
248 double t = 2.0 * std::sqrt(x: -p);
249
250 roots[0] = t * std::cos(x: phi);
251 roots[1] = -t * std::cos(x: phi + piByThree);
252 roots[2] = -t * std::cos(x: phi - piByThree);
253 numberOfRoots = 3;
254 } else {
255 // One real solution
256 double sqrtDisc = std::sqrt(x: discriminant);
257 double u = qCbrt(x: sqrtDisc - q);
258 double v = -qCbrt(x: sqrtDisc + q);
259
260 roots[0] = u + v;
261 numberOfRoots = 1;
262 }
263
264 // Substitute back in
265 const double sub = oneThird * A;
266 for (int i = 0; i < numberOfRoots; ++i) {
267 roots[i] -= sub;
268 // Take care of cases where we are close to zero or one
269 if (almostZero(value: roots[i], threshold: 1e-6f))
270 roots[i] = 0.f;
271 if (almostZero(value: roots[i] - 1.f, threshold: 1e-6f))
272 roots[i] = 1.f;
273 }
274
275 return numberOfRoots;
276}
277
278} // namespace Animation
279} // namespace Qt3DAnimation
280
281QT_END_NAMESPACE
282

source code of qt3d/src/animation/backend/bezierevaluator.cpp