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>

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