diff options
author | Sean Harmer <sean.harmer@kdab.com> | 2017-01-17 18:29:45 +0000 |
---|---|---|
committer | Sean Harmer <sean.harmer@kdab.com> | 2017-01-26 19:55:51 +0000 |
commit | 4f054fd5ea50bb2874468653ce6de46217dfc054 (patch) | |
tree | 288dc579c3289d9d9aba66575fc4f5a2d6ccee36 /src/animation/backend | |
parent | af21ba22d9e03d5a6d0e840da9dfcb86adf06a68 (diff) |
Implement FCurve evaluation
Uses a couple of helper classes to do the tricky mathematics.
Change-Id: I3245c0e282a5eeede3d596ca99ac2c78e34f23ef
Reviewed-by: Sean Harmer <sean.harmer@kdab.com>
Diffstat (limited to 'src/animation/backend')
-rw-r--r-- | src/animation/backend/backend.pri | 11 | ||||
-rw-r--r-- | src/animation/backend/bezierevaluator.cpp | 238 | ||||
-rw-r--r-- | src/animation/backend/bezierevaluator_p.h | 92 | ||||
-rw-r--r-- | src/animation/backend/fcurve.cpp | 83 | ||||
-rw-r--r-- | src/animation/backend/fcurve_p.h | 91 | ||||
-rw-r--r-- | src/animation/backend/functionrangefinder.cpp | 173 | ||||
-rw-r--r-- | src/animation/backend/functionrangefinder_p.h | 97 | ||||
-rw-r--r-- | src/animation/backend/keyframe_p.h | 86 |
8 files changed, 869 insertions, 2 deletions
diff --git a/src/animation/backend/backend.pri b/src/animation/backend/backend.pri index 41857c253..4a38a0d45 100644 --- a/src/animation/backend/backend.pri +++ b/src/animation/backend/backend.pri @@ -6,8 +6,15 @@ HEADERS += \ $$PWD/handle_types_p.h \ $$PWD/handler_p.h \ $$PWD/nodefunctor_p.h \ - $$PWD/managers_p.h + $$PWD/managers_p.h \ + $$PWD/keyframe_p.h \ + $$PWD/fcurve_p.h \ + $$PWD/bezierevaluator_p.h \ + $$PWD/functionrangefinder_p.h SOURCES += \ $$PWD/animationclip.cpp \ - $$PWD/handler.cpp + $$PWD/handler.cpp \ + $$PWD/fcurve.cpp \ + $$PWD/bezierevaluator.cpp \ + $$PWD/functionrangefinder.cpp diff --git a/src/animation/backend/bezierevaluator.cpp b/src/animation/backend/bezierevaluator.cpp new file mode 100644 index 000000000..6ed8b1aa2 --- /dev/null +++ b/src/animation/backend/bezierevaluator.cpp @@ -0,0 +1,238 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "bezierevaluator_p.h" +#include <private/keyframe_p.h> +#include <QtCore/qglobal.h> +#include <QtCore/qdebug.h> + +#include <cmath> + +QT_BEGIN_NAMESPACE + +namespace { + +inline double qCbrt(double x) +{ + // Android is just broken and doesn't define cbrt in std namespace +#if defined(Q_OS_ANDROID) + if (x > 0.0) + return std::pow(x, 1.0 / 3.0); + else if (x < 0.0) + return -std::pow(-x, 1.0 / 3.0); + else + return 0.0; +#else + return std::cbrt(x); +#endif +} + +} // anonymous + +namespace Qt3DAnimation { +namespace Animation { + +/*! + \internal + + Evaluates the value of the cubic bezier at time \a time. + This requires first finding the value of the bezier parameter, u, + corresponding to the requested time which should itself be + sandwiched by the provided times and keyframes. + + Once u is found, substitute this back into the cubic Bezier + equation using the y components of the keyframe control points. + */ +float BezierEvaluator::valueForTime(float time) const +{ + const float u = parameterForTime(time); + + // Calulate powers of u and (1-u) that we need + const float u2 = u * u; + const float u3 = u2 * u; + const float mu = 1.0f - u; + const float mu2 = mu * mu; + const float mu3 = mu2 * mu; + + // The cubic Bezier control points + const float p0 = m_keyframe0.value; + const float p1 = m_keyframe0.rightControlPoint.y(); + const float p2 = m_keyframe1.leftControlPoint.y(); + const float p3 = m_keyframe1.value; + + // Evaluate the cubic Bezier function + return p0 * mu3 + 3.0f * p1 * mu2 * u + 3.0f * p2 * mu * u2 + p3 * u3; +} + +/*! + Calculates the value of the Bezier parameter, u, for the + requested time which is the x coordinate of the Keyframes. + + Given 4 ordered control points p0, p1, p2, and p3, the cubic + Bezier equation is: + + x(u) = (1-u)^3 p0 + 3 (1-u)^2 u p1 + 3 (1-u) u^2 p2 + u^3 p3 + + To find the value of u that corresponds with a given x + value (time in the case of keyframes), we can expand the + above equation, and then collect terms to arrive at: + + 0 = a u^3 + b u^2 + c u + d + + where + + a = p3 - p0 + 3 (p1 - p2) + b = 3 (p0 - 2 p1 + p2) + c = 3 (p1 - p0) + d = p0 - x(u) + + We can then use findCubicRoots to locate the single root of + this cubic equation found in the range [0,1] used for this + section of the FCurve. This works because the FCurve ensures + that the function it represents via the Bezier control points + in the Keyframes is single valued. (as a function of time). + Time, therefore must be single valued on the interval and + therefore have a single root for any given time in the interval + covered by the Keyframes. + */ +float BezierEvaluator::parameterForTime(float time) const +{ + Q_ASSERT(time >= m_time0); + Q_ASSERT(time <= m_time1); + + const float p0 = m_time0; + const float p1 = m_keyframe0.rightControlPoint.x(); + const float p2 = m_keyframe1.leftControlPoint.x(); + const float p3 = m_time1; + + const float coeffs[4] = { + p0 - time, // d + 3.0f * (p1 - p0), // c + 3.0f * (p0 - 2.0f * p1 + p2), // b + p3 - p0 + 3.0f * (p1 - p2) // a + }; + + float roots[3]; + const int numberOfRoots = findCubicRoots(coeffs, roots); + for (int i = 0; i < numberOfRoots; ++i) { + if (roots[i] >= 0 && roots[i] <= 1) + return roots[i]; + } + + qWarning() << "Failed to find root of cubic bezier at time" << time + << "with coeffs: a =" << coeffs[3] << "b =" << coeffs[2] + << "c =" << coeffs[1] << "d =" << coeffs[0]; + return 0.0f; +} + +/*! + \internal + + Finds the roots of the cubic equation ax^3 + bx^2 + cx + d = 0 for + real coefficients and returns the number of roots. The roots are + put into the \a roots array. The coefficients should be passed in + as coeffs[0] = d, coeffs[1] = c, coeffs[2] = b, coeffs[3] = a. + */ +int BezierEvaluator::findCubicRoots(const float coeffs[4], float roots[3]) +{ + // See https://en.wikipedia.org/wiki/Cubic_function#General_solution_to_the_cubic_equation_with_real_coefficients + // for a description. We depress the general cubic to a form that can more easily be solved. Solve it and then + // substitue the results back to get the roots of the original cubic. + int numberOfRoots; + const double oneThird = 1.0 / 3.0; + const double piByThree = M_PI / 3.0; + + // Put cubic into normal format: x^3 + Ax^2 + Bx + C = 0 + const double A = coeffs[ 2 ] / coeffs[ 3 ]; + const double B = coeffs[ 1 ] / coeffs[ 3 ]; + const double C = coeffs[ 0 ] / coeffs[ 3 ]; + + // Substitute x = y - A/3 to eliminate quadratic term (depressed form): + // x^3 + px + q = 0 + const double Asq = A * A; + const double p = oneThird * (-oneThird * Asq + B); + const double q = 1.0 / 2.0 * (2.0 / 27.0 * A * Asq - oneThird * A * B + C); + + // Use Cardano's formula + const double pCubed = p * p * p; + const double discriminant = q * q + pCubed; + + if (qIsNull(discriminant)) { + if (qIsNull(q)) { + // One repeated triple root + roots[0] = 0.0; + numberOfRoots = 1; + } else { + // One single and one double root + double u = qCbrt(-q); + roots[0] = 2.0 * u; + roots[1] = -u; + numberOfRoots = 2; + } + } else if (discriminant < 0) { + // Three real solutions + double phi = oneThird * std::acos(-q / std::sqrt(-pCubed)); + double t = 2.0 * std::sqrt(-p); + + roots[0] = t * std::cos(phi); + roots[1] = -t * std::cos(phi + piByThree); + roots[2] = -t * std::cos(phi - piByThree); + numberOfRoots = 3; + } else { + // One real solution + double sqrtDisc = std::sqrt(discriminant); + double u = qCbrt(sqrtDisc - q); + double v = -qCbrt(sqrtDisc + q); + + roots[0] = u + v; + numberOfRoots = 1; + } + + // Substitute back in + const double sub = oneThird * A; + for (int i = 0; i < numberOfRoots; ++i) + roots[i] -= sub; + + return numberOfRoots; +} + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE diff --git a/src/animation/backend/bezierevaluator_p.h b/src/animation/backend/bezierevaluator_p.h new file mode 100644 index 000000000..5291405b3 --- /dev/null +++ b/src/animation/backend/bezierevaluator_p.h @@ -0,0 +1,92 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef BEZIEREVALUATOR_P_H +#define BEZIEREVALUATOR_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qglobal.h> + +QT_BEGIN_NAMESPACE + +namespace Qt3DAnimation { +namespace Animation { + +struct Keyframe; + +class Q_AUTOTEST_EXPORT BezierEvaluator +{ +public: + explicit BezierEvaluator(float time0, const Keyframe &keyframe0, + float time1, const Keyframe &keyframe1) + : m_time0(time0) + , m_time1(time1) + , m_keyframe0(keyframe0) + , m_keyframe1(keyframe1) + { + } + + float valueForTime(float time) const; + float parameterForTime(float time) const; + + static int findCubicRoots(const float coefficients[], float roots[3]); + +private: + float m_time0; + float m_time1; + const Keyframe &m_keyframe0; + const Keyframe &m_keyframe1; +}; + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE + +#endif // BEZIEREVALUATOR_P_H diff --git a/src/animation/backend/fcurve.cpp b/src/animation/backend/fcurve.cpp new file mode 100644 index 000000000..95e3d1568 --- /dev/null +++ b/src/animation/backend/fcurve.cpp @@ -0,0 +1,83 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL3$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see http://www.qt.io/terms-conditions. For further +** information use the contact form at http://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPLv3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or later as published by the Free +** Software Foundation and appearing in the file LICENSE.GPL included in +** the packaging of this file. Please review the following information to +** ensure the GNU General Public License version 2.0 requirements will be +** met: http://www.gnu.org/licenses/gpl-2.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "fcurve_p.h" +#include <private/bezierevaluator_p.h> + +QT_BEGIN_NAMESPACE + +namespace Qt3DAnimation { +namespace Animation { + +FCurve::FCurve() + : m_rangeFinder(m_localTimes) +{ +} + +float FCurve::evaluateAtTime(float localTime) const +{ + // Find keyframes that sandwich the requested localTime + int keyframe0 = m_rangeFinder.findLowerBound(localTime); + + BezierEvaluator evaluator(m_localTimes[keyframe0], m_keyframes[keyframe0], + m_localTimes[keyframe0 + 1], m_keyframes[keyframe0 + 1]); + return evaluator.valueForTime(localTime); +} + +float FCurve::startTime() const +{ + if (!m_localTimes.isEmpty()) + return m_localTimes.first(); + return 0.0f; +} + +float FCurve::endTime() const +{ + if (!m_localTimes.isEmpty()) + return m_localTimes.last(); + return 0.0f; +} + +void FCurve::appendKeyframe(float localTime, const Keyframe &keyframe) +{ + m_localTimes.append(localTime); + m_keyframes.append(keyframe); +} + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE diff --git a/src/animation/backend/fcurve_p.h b/src/animation/backend/fcurve_p.h new file mode 100644 index 000000000..88990fb81 --- /dev/null +++ b/src/animation/backend/fcurve_p.h @@ -0,0 +1,91 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL3$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see http://www.qt.io/terms-conditions. For further +** information use the contact form at http://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPLv3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or later as published by the Free +** Software Foundation and appearing in the file LICENSE.GPL included in +** the packaging of this file. Please review the following information to +** ensure the GNU General Public License version 2.0 requirements will be +** met: http://www.gnu.org/licenses/gpl-2.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QT3DANIMATION_ANIMATION_FCURVE_P_H +#define QT3DANIMATION_ANIMATION_FCURVE_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "keyframe_p.h" +#include "functionrangefinder_p.h" +#include <QtCore/qvector.h> + +QT_BEGIN_NAMESPACE + +namespace Qt3DAnimation { +namespace Animation { + +class Q_AUTOTEST_EXPORT FCurve +{ +public: + FCurve(); + + int keyframeCount() const { return m_localTimes.size(); } + void appendKeyframe(float localTime, const Keyframe &keyframe); + void clearKeyframes() { m_localTimes.clear(); m_keyframes.clear(); } + + const float &localTime(int index) const { return m_localTimes[index]; } + float &localTime(int index) { return m_localTimes[index]; } + const Keyframe &keyframe(int index) const { return m_keyframes[index]; } + Keyframe &keyframe(int index) { return m_keyframes[index]; } + + float startTime() const; + float endTime() const; + + float evaluateAtTime(float localTime) const; + +private: + QVector<float> m_localTimes; + QVector<Keyframe> m_keyframes; + + FunctionRangeFinder m_rangeFinder; +}; + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE + +#endif // QT3DANIMATION_ANIMATION_FCURVE_P_H diff --git a/src/animation/backend/functionrangefinder.cpp b/src/animation/backend/functionrangefinder.cpp new file mode 100644 index 000000000..168b835ad --- /dev/null +++ b/src/animation/backend/functionrangefinder.cpp @@ -0,0 +1,173 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL3$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see http://www.qt.io/terms-conditions. For further +** information use the contact form at http://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPLv3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or later as published by the Free +** Software Foundation and appearing in the file LICENSE.GPL included in +** the packaging of this file. Please review the following information to +** ensure the GNU General Public License version 2.0 requirements will be +** met: http://www.gnu.org/licenses/gpl-2.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "functionrangefinder_p.h" + +QT_BEGIN_NAMESPACE + +namespace Qt3DAnimation { +namespace Animation { + +/*! + \internal + \class FunctionRangeFinder finds the lower bound index of a range that encloses a function value + + Given a vector of function values (typically abscissa values of some other function), this + class can find the lower bound index of a range that encloses the requested value. This is + very useful for finding the two points that sandwich a value to which you later wish to + interpolate for example. + */ + +/*! + \internal + \fn findLowerBound + + Finds the lower bound index of a range that encloses the requested value. + + We use a technique which tries to be better than a simple bisection. Often when + performing interpolations, subsequent points are correlated with earlier calls. + This is especially true with time based lookups. If two calls are determined to + be correlated, then the next subsequent call will use the hunt function to search + close to the last returned value first. The hunt algorithms searches outward in + increasing step sizes until a sandwiching range is found. Traditional bisection + is then used to refine this result. + + If the previous results are uncorrelated, a simple bisection is used. + */ + +FunctionRangeFinder::FunctionRangeFinder(const QVector<float> &x) + : m_x(x) + , m_previousLowerBound(0) + , m_correlated(0) + , m_rangeSize(2) + , m_correlationThreshold(1) + , m_ascending(true) +{ + updateAutomaticCorrelationThreshold(); + if (!m_x.isEmpty()) + m_ascending = (m_x.last() >= m_x.first()); +} + +/*! + \internal + Locates the lower bound of a range that encloses \a x by a bisection method. +*/ +int FunctionRangeFinder::locate(float x) const +{ + if (m_x.size() < 2 || m_rangeSize < 2 || m_rangeSize > m_x.size()) + return -1; + + int jLower = 0; + int jUpper = m_x.size() - 1; + while (jUpper - jLower > 1) { + int jMid = (jUpper + jLower) >> 1; + if ((x >= m_x[jMid]) == m_ascending) + jLower = jMid; + else + jUpper = jMid; + } + + m_correlated = std::abs(jLower - m_previousLowerBound) <= m_correlationThreshold; + m_previousLowerBound = jLower; + + return std::max(0, std::min(m_x.size() - m_rangeSize, jLower - ((m_rangeSize - 2) >> 1))); +} + +/*! + \internal + Hunts outward from the previous result in increasing step sizes then refines via bisection. + */ +int FunctionRangeFinder::hunt(float x) const +{ + if (m_x.size() < 2 || m_rangeSize < 2 || m_rangeSize > m_x.size()) + return -1; + + int jLower = m_previousLowerBound; + int jMid; + int jUpper; + if (jLower < 0 || jLower > (m_x.size() - 1)) { + jLower = 0; + jUpper = m_x.size() - 1; + } else { + int increment = 1; + if ((x >= m_x[jLower]) == m_ascending) { + for (;;) { + jUpper = jLower + increment; + if (jUpper >= m_x.size() - 1) { + jUpper = m_x.size() - 1; + break; + } else if ((x < m_x[jUpper]) == m_ascending) { + break; + } else { + jLower = jUpper; + increment += increment; + } + } + } else { + jUpper = jLower; + for (;;) { + jLower = jLower - increment; + if (jLower <= 0) { + jLower = 0; + break; + } else if ((x >= m_x[jLower]) == m_ascending) { + break; + } else { + jUpper = jLower; + increment += increment; + } + } + } + } + + while (jUpper - jLower > 1) { + jMid = (jUpper + jLower) >> 1; + if ((x >= m_x[jMid]) == m_ascending) + jLower = jMid; + else + jUpper = jMid; + } + + m_correlated = std::abs(jLower - m_previousLowerBound) <= m_correlationThreshold; + m_previousLowerBound = jLower; + + return std::max(0, std::min(m_x.size() - m_rangeSize, jLower - ((m_rangeSize - 2) >> 1))); +} + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE diff --git a/src/animation/backend/functionrangefinder_p.h b/src/animation/backend/functionrangefinder_p.h new file mode 100644 index 000000000..bea9a2e2f --- /dev/null +++ b/src/animation/backend/functionrangefinder_p.h @@ -0,0 +1,97 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL3$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see http://www.qt.io/terms-conditions. For further +** information use the contact form at http://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPLv3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or later as published by the Free +** Software Foundation and appearing in the file LICENSE.GPL included in +** the packaging of this file. Please review the following information to +** ensure the GNU General Public License version 2.0 requirements will be +** met: http://www.gnu.org/licenses/gpl-2.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QT3DANIMATION_ANIMATION_FUNCTIONRANGEFINDER_P_H +#define QT3DANIMATION_ANIMATION_FUNCTIONRANGEFINDER_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qvector.h> + +#include <cmath> +#include <cstdlib> + +QT_BEGIN_NAMESPACE + +namespace Qt3DAnimation { +namespace Animation { + +class Q_AUTOTEST_EXPORT FunctionRangeFinder +{ +public: + FunctionRangeFinder(const QVector<float> &x); + + inline int findLowerBound(float x) const { return m_correlated ? hunt(x) : locate(x); } + + int rangeSize() const { return m_rangeSize; } + void setRangeSize(int rangeSize) { m_rangeSize = rangeSize; } + + bool isAscending() const { return m_ascending; } + void setAscending(bool ascending) { m_ascending = ascending; } + + int correlationThreshold() const { return m_correlationThreshold; } + void updateAutomaticCorrelationThreshold() + { + m_correlationThreshold = std::max(1, int(std::pow(float(m_x.size()), 0.25))); + } + +private: + int locate(float x) const; + int hunt(float x) const; + + const QVector<float> &m_x; + mutable int m_previousLowerBound; + mutable bool m_correlated; + int m_rangeSize; + int m_correlationThreshold; + bool m_ascending; +}; + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE + +#endif // QT3DANIMATION_ANIMATION_FUNCTIONRANGEFINDER_P_H diff --git a/src/animation/backend/keyframe_p.h b/src/animation/backend/keyframe_p.h new file mode 100644 index 000000000..550c9fde0 --- /dev/null +++ b/src/animation/backend/keyframe_p.h @@ -0,0 +1,86 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Klaralvdalens Datakonsult AB (KDAB). +** Contact: http://www.qt-project.org/legal +** +** This file is part of the Qt3D module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL3$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see http://www.qt.io/terms-conditions. For further +** information use the contact form at http://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPLv3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or later as published by the Free +** Software Foundation and appearing in the file LICENSE.GPL included in +** the packaging of this file. Please review the following information to +** ensure the GNU General Public License version 2.0 requirements will be +** met: http://www.gnu.org/licenses/gpl-2.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QT3DANIMATION_ANIMATION_KEYFRAME_P_H +#define QT3DANIMATION_ANIMATION_KEYFRAME_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtGui/qvector2d.h> + +QT_BEGIN_NAMESPACE + +namespace Qt3DAnimation { +namespace Animation { + +struct Keyframe +{ + enum Interpolation { + Constant, + Linear, + Bezier + // TODO: Add other easing types + }; + + inline bool operator==(const Keyframe &rhs) const + { + return value == rhs.value + && leftControlPoint == rhs.leftControlPoint + && rightControlPoint == rhs.rightControlPoint + && interpolation == rhs.interpolation; + } + + float value; // Value (time is stored separately in FCurve) + QVector2D leftControlPoint; // Bezier control point (time, value) + QVector2D rightControlPoint; // Bezier control point (time, value) + Interpolation interpolation; // Method to use for evaluation between this Keyframe and the next +}; + +} // namespace Animation +} // namespace Qt3DAnimation + +QT_END_NAMESPACE + +#endif // QT3DANIMATION_ANIMATION_KEYFRAME_P_H |