fcurve.h

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
 
#pragma once
 
#include <utility/dllexport.h>
#include <rtti/rtti.h>
#include <rtti/object.h>
#include <glm/glm.hpp>
#include <nap/resource.h>
 
namespace nap
{
    namespace math
    {
        enum class ECurveInterp : int
        {
            Bezier = 0,             
            Linear,                 
            Stepped                 
        };
 
 
        template<typename T, typename V>
        struct FComplex
        {
            FComplex() = default;
 
            FComplex(const T& t, const V& value) : mTime(t), mValue(value) {}
 
            T mTime;    
            V mValue;   
 
            FComplex operator+(const FComplex& other) const
            {
                return {mTime + other.mTime, mValue + other.mValue};
            }
 
            FComplex operator-(const FComplex& other) const
            {
                return {mTime - other.mTime, mValue - other.mValue};
            }
 
            FComplex operator*(const T& other) const
            {
                return {mTime * other, mValue * other};
            }
        };
 
 
        template<typename T, typename V>
        struct FCurvePoint
        {
            FCurvePoint() = default;
 
            FCurvePoint(const FComplex<T, V>& pos, const FComplex<T, V>& inTan, const FComplex<T, V>& outTan)
                : mPos(pos), mInTan(inTan), mOutTan(outTan) {}
 
            FComplex<T, V> mPos;        
            FComplex<T, V> mInTan;      
            FComplex<T, V> mOutTan;     
            ECurveInterp mInterp = ECurveInterp::Bezier;
 
            bool mTangentsAligned = true;   
        };
 
 
        // 1-D Curve Resource
 
        template<typename T, typename V>
        class FCurve : public Resource
        {
        RTTI_ENABLE(Resource)
        public:
            FCurve();
 
            ~FCurve() override { mSortedPoints.clear(); }
 
 
            V evaluate(const T& t);
 
            void invalidate() { mPointsSorted = false; }
 
            std::vector<FCurvePoint<T, V>> mPoints;
 
        private:
            FComplex<T, V>  bezier(const FComplex<T, V> (& pts)[4], T t);
 
            T tForX(const FComplex<T, V> (& pts)[4], T x, T threshold = 0.0001, int maxIterations = 100);
 
            V lerp(const V& a, const V& b, const T& t);
 
            V evalCurveSegmentBezier(const nap::math::FComplex<T, V> (& pts)[4], T x);
 
            V evalCurveSegmentLinear(const FComplex<T, V> (& pts)[4], T x);
 
            V evalCurveSegmentStepped(const FComplex<T, V>(& pts)[4], T x);
 
            void sortPoints();
 
            int pointIndexAtTime(const T& t) const;
 
            void limitOverhang(const T& x0, T& x1, T& x2, const T& x3);
 
            void limitOverhangPoints(const FComplex<T, V>& pa, FComplex<T, V>& pb, FComplex<T, V>& pc, const FComplex<T, V>& pd);
 
            mutable std::vector<FCurvePoint<T, V>*> mSortedPoints;              
            bool mPointsSorted = false;                                         
        };
 
 
        // Type definitions for all supported curve types
 
        using FloatFComplex     = FComplex<float, float>;
        using Vec2FComplex      = FComplex<float, glm::vec2>;
        using Vec3FComplex      = FComplex<float, glm::vec3>;
        using Vec4FComplex      = FComplex<float, glm::vec4>;
 
        using FloatFCurve       = FCurve<float, float>;
        using Vec2FCurve        = FCurve<float, glm::vec2>;
        using Vec3FCurve        = FCurve<float, glm::vec3>;
        using Vec4FCurve        = FCurve<float, glm::vec4>;
 
        using FloatFCurvePoint  = FCurvePoint<float, float>;
        using Vec2FCurvePoint   = FCurvePoint<float, glm::vec2>;
        using Vec3FCurvePoint   = FCurvePoint<float, glm::vec3>;
        using Vec4FCurvePoint   = FCurvePoint<float, glm::vec4>;
 
 
        // Template Definitions
 
        template<typename T, typename V>
        V nap::math::FCurve<T, V>::evaluate(const T& t)
        {
            if (mPoints.empty())
                return V();
 
            // Ensure points are sorted before evaluation
            if (!mPointsSorted)
            {
                sortPoints();
                mPointsSorted = true;
            }
 
            const FCurvePoint<T, V>* firstPoint = mSortedPoints[0];
            if (t < firstPoint->mPos.mTime)
                return firstPoint->mPos.mValue;
 
            const FCurvePoint<T, V>* lastPoint = mSortedPoints[mSortedPoints.size() - 1];
            if (t >= lastPoint->mPos.mTime)
                return lastPoint->mPos.mValue;
 
            int idx = pointIndexAtTime(t);
            const FCurvePoint<T, V>* curr = mSortedPoints[idx];
            const FCurvePoint<T, V>* next = mSortedPoints[idx + 1];
 
            auto a = curr->mPos;
            auto b = a + curr->mOutTan;
            auto d = next->mPos;
            auto c = d + next->mInTan;
 
            limitOverhangPoints(a, b, c, d);
            switch (curr->mInterp)
            {
            case ECurveInterp::Bezier:
                return evalCurveSegmentBezier({ a, b, c, d }, t);
            case ECurveInterp::Linear:
                return evalCurveSegmentLinear({ a, b, c, d }, t);
            case ECurveInterp::Stepped:
                return evalCurveSegmentStepped({ a, b, c, d }, t);
            default:
                assert(false);
            }
 
            return V();
        }
 
        template<typename T, typename V>
        nap::math::FComplex<T, V> nap::math::FCurve<T, V>::bezier(const FComplex<T, V>(&pts)[4], T t)
        {
            T u = 1 - t;
            T a = u * u * u;
            T b = 3 * u * u * t;
            T c = 3 * u * t * t;
            T d = t * t * t;
            return pts[0] * a + pts[1] * b + pts[2] * c + pts[3] * d;
        }
 
 
        template<typename T, typename V>
        T nap::math::FCurve<T, V>::tForX(const FComplex<T, V>(&pts)[4], T x, T threshold /*= 0.0001*/, int maxIterations /*= 100*/)
        {
            T depth = 0.5;
            T t = 0.5;
            for (int i = 0; i < maxIterations; i++)
            {
                auto dx = x - bezier(pts, t).mTime;
                auto adx = std::abs(dx);
                if (adx <= threshold)
                    break;
 
                depth *= 0.5;
                t += (dx > 0) ? depth : -depth;
            }
            return t;
        }
 
        template<typename T, typename V>
        V nap::math::FCurve<T, V>::lerp(const V& a, const V& b, const T& t)
        {
            return a + t * (b - a);
        }
 
        template<typename T, typename V>
        V nap::math::FCurve<T, V>::evalCurveSegmentBezier(const nap::math::FComplex<T, V>(&pts)[4], T x)
        {
            T t = tForX(pts, x);
            return bezier(pts, t).mValue;
        }
 
        template<typename T, typename V>
        V nap::math::FCurve<T, V>::evalCurveSegmentLinear(const FComplex<T, V>(&pts)[4], T x)
        {
            const auto& a = pts[0];
            const auto& b = pts[3];
            T t = (x - a.mTime) / (b.mTime - a.mTime);
            return lerp(a.mValue, b.mValue, t);
        }
 
 
        template<typename T, typename V>
        V nap::math::FCurve<T, V>::evalCurveSegmentStepped(const FComplex<T, V>(&pts)[4], T x)
        {
            return pts[0].mValue;
        }
 
        template<typename T, typename V>
        void nap::math::FCurve<T, V>::sortPoints()
        {
            mSortedPoints.clear();
            for (int i = 0; i < mPoints.size(); i++)
                mSortedPoints.emplace_back(&mPoints[i]);
 
            std::sort(mSortedPoints.begin(), mSortedPoints.end(),
                [](const FCurvePoint<T, V>* lhs, const FCurvePoint<T, V>* rhs)
            {
                return lhs->mPos.mTime < rhs->mPos.mTime;
            });
        }
 
        template<typename T, typename V>
        int nap::math::FCurve<T, V>::pointIndexAtTime(const T& t) const
        {
            for (size_t i = 0, len = mSortedPoints.size(); i < len; i++)
            {
                if (t < mSortedPoints[i]->mPos.mTime)
                {
                    if (i == 0)
                        return 0;
                    return static_cast<int>(i - 1);
                }
            }
            assert(false);
            return -1;
        }
 
        template<typename T, typename V>
        void nap::math::FCurve<T, V>::limitOverhang(const T& x0, T& x1, T& x2, const T& x3)
        {
            x1 = std::min(x1, x3);
            x2 = std::max(x2, x0);
        }
 
        template<typename T, typename V>
        void nap::math::FCurve<T, V>::limitOverhangPoints(const FComplex<T, V>& pa, FComplex<T, V>& pb, FComplex<T, V>& pc, const FComplex<T, V>& pd)
        {
            auto a = pa.mTime;
            auto b = pb.mTime;
            auto c = pc.mTime;
            auto d = pd.mTime;
            auto bb = b;
            auto cc = c;
 
            limitOverhang(a, b, c, d);
 
            // calculate ratios for both tangents
            auto rb = (b - a) / (bb - a);
            auto rc = (c - d) / (cc - d);
 
            // apply corrected times
            pb.mTime = b;
            pc.mTime = c;
 
            // we limited time, keep the value on the tangent line for c1 continuity
            pb.mValue = ((pb.mValue - pa.mValue) * rb) + pa.mValue;
            pc.mValue = ((pc.mValue - pd.mValue) * rc) + pd.mValue;
        }
 
 
        // Forward Declarations
 
        template<>
        NAPAPI nap::math::FCurve<float, float>::FCurve();
 
        template<>
        NAPAPI nap::math::FCurve<float, glm::vec2>::FCurve();
    }
}