gls_keyframe.h

Go to the documentation of this file.

#ifndef INCLUDED_GLS_KEYFRAME_H
#define INCLUDED_GLS_KEYFRAME_H

#include <algorithm>
#include <cfloat>
#include <cmath>
#include <cstring> // for memcmp()
#include <limits>
#include <memory>
#include <string>
#include <utility>
#include <vector>
#if defined(LINUX) && (__GNUC__ >= 4) && !defined(QNX)
#    include <tr1/memory>
#endif

#include "disti_assert.h"
#include "gls_color.h"
#include "util.h"
#include "vertex.h"
#include "gls_quaternion.h" // Must follow "vertex.h" because of include problems

namespace disti
{
  #ifdef GLS_ANIMATION_USE_STD_SHARED_PTR
    namespace stdortr1 = std;      //< Alias for cross-platform portability
  #else
    namespace stdortr1 = std::tr1; //< Alias for cross-platform portability
  #endif    

    class GlsKeyframeCurveBase
    {
    public:
        typedef double             Key;     
        typedef std::size_t        Size;    
        typedef std::pair<Key,Key> KeyPair; 

        virtual ~GlsKeyframeCurveBase() {}

        virtual Size GetKeyframeCount() const = 0;

        virtual KeyPair GetMinMaxKeys() const = 0;

    protected:
        GlsKeyframeCurveBase() {}
    };

    namespace Detail
    {
        typedef unsigned int ID;

        const float g_glsAnimationFloatTolerance = 1e-5f;

        const double g_pi = 3.14159265358979323846;

        template<class T> struct FloatSelector         { typedef GlsKeyframeCurveBase::Key Type;  };
        template<>        struct FloatSelector<Vector> { typedef float                     Type;  }; 

        inline unsigned char ToColorElement( const double d )
        {
            const unsigned int trunc = static_cast<unsigned int>( d + 0.5 );
            // Extra parens avoid the NOMINMAX problems on Windows
            return static_cast<unsigned char>( (std::min)( (std::max)( trunc, 0u ), 255u ) );
        }

        inline bool FloatGreaterThan( const double lhs, const double rhs, const float tolerance = g_glsAnimationFloatTolerance )
        {
            return lhs > rhs && !Equal( lhs, rhs, tolerance );
        }

        inline bool FloatLessThan( const double lhs, const double rhs, const float tolerance = g_glsAnimationFloatTolerance ) 
        { 
            return lhs < rhs && !Equal( lhs, rhs, tolerance ); 
        }

        inline bool FloatGreaterThanOrEqualTo( const double lhs, const double rhs, const float tolerance = g_glsAnimationFloatTolerance )
        {
            return lhs > rhs || Equal( lhs, rhs, tolerance );
        }

        inline bool FloatLessThanOrEqualTo( const double lhs, const double rhs, const float tolerance = g_glsAnimationFloatTolerance )
        {
            return lhs < rhs || Equal( lhs, rhs, tolerance );
        }
    } // namespace Detail

    template<class T>
    struct GlsKeyframeInterpolator
    {
        typedef stdortr1::shared_ptr<      GlsKeyframeInterpolator> Ptr;      
        typedef stdortr1::shared_ptr<const GlsKeyframeInterpolator> PtrConst; 
        typedef GlsKeyframeCurveBase::Key                           Key;      
        typedef T                                                   Value;    
        typedef typename Detail::FloatSelector<Value>::Type         Float;    

        virtual ~GlsKeyframeInterpolator() {}

        virtual Value operator()(
            const Key&   key,  
            const Key&   lowerKey,   const Key&   upperKey, 
            const Value& lowerValue, const Value& upperValue ) const = 0;
    };

    template<class Value>
    struct GlsLinearInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 
        
        Value operator()(
            const Key&   key,  
            const Key&   lowerKey,   const Key&   upperKey, 
            const Value& lowerValue, const Value& upperValue ) const // override
        {
            const Float percent   = static_cast<Float>( (key - lowerKey) / (upperKey - lowerKey) );
            const Value interpVal = (upperValue - lowerValue) * percent + lowerValue;
            return interpVal;
        }
    };

    struct GlsColorInterpolationAdapter : GlsKeyframeInterpolator<glsColor>
    {
        GlsColorInterpolationAdapter()
            : _interpolator( CreateDefaultInterpolator() )
        {}
        
        explicit GlsColorInterpolationAdapter( GlsKeyframeInterpolator<double>* const interpolator )
            : _interpolator( interpolator ? interpolator : CreateDefaultInterpolator() )
        {}

        explicit GlsColorInterpolationAdapter( GlsKeyframeInterpolator<double>::PtrConst interpolator )
            : _interpolator( interpolator ? interpolator : GlsKeyframeInterpolator<double>::PtrConst( CreateDefaultInterpolator() ) )
        {}

        glsColor operator()(
            const Key&      key,  
            const Key&      lowerKey,   const Key&      upperKey, 
            const glsColor& lowerValue, const glsColor& upperValue ) const // override
        {
            // Convert to doubles
            struct { double r, g, b, a; } lower, upper, interpVal;
            lowerValue.GetRGBA4d( lower.r, lower.g, lower.b, lower.a );
            upperValue.GetRGBA4d( upper.r, upper.g, upper.b, upper.a );

            // Interpolate doubles as usual
            interpVal.r = (*_interpolator)( key, lowerKey, upperKey, lower.r, upper.r );
            interpVal.g = (*_interpolator)( key, lowerKey, upperKey, lower.g, upper.g );
            interpVal.b = (*_interpolator)( key, lowerKey, upperKey, lower.b, upper.b );
            interpVal.a = (*_interpolator)( key, lowerKey, upperKey, lower.a, upper.a );

            // Convert back to color (note: values from GetRGBA4d() are 0-1.0, not 0-255, so scale up)
            return glsColor( 
                Detail::ToColorElement( interpVal.r * 255 ), 
                Detail::ToColorElement( interpVal.g * 255 ), 
                Detail::ToColorElement( interpVal.b * 255 ), 
                Detail::ToColorElement( interpVal.a * 255 ) );
        }

    private:
        static GlsKeyframeInterpolator<double>* CreateDefaultInterpolator() { return new GlsLinearInterpolator<double>(); }

        // Data members
        GlsKeyframeInterpolator<double>::PtrConst _interpolator;
    };

    template<class Value>
    struct GlsGatedInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key  Key; 

        Value operator()(
            const Key&   key,  
            const Key&   /*lowerKey*/, const Key&   upperKey, 
            const Value& lowerValue,   const Value& upperValue ) const // override
        {
            // Send the lower value unless we've hit the upper value.
            if( Equal( key, upperKey, Detail::g_glsAnimationFloatTolerance ) )
            {
                return upperValue;
            }
            else
            {
                return lowerValue;
            }
        }
    };

    template<class Value> struct GlsSphericalLinearInterpolator;

    template<>
    struct GlsSphericalLinearInterpolator<GlsQuaternionD> : GlsKeyframeInterpolator<GlsQuaternionD>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef GlsKeyframeInterpolator<GlsQuaternionD>::Value  Value; 
        typedef GlsKeyframeInterpolator<Value>::Key             Key;   

        Value operator()(
            const Key&   key,  
            const Key&   lowerKey,   const Key&   upperKey, 
            const Value& lowerValue, const Value& upperValue ) const // override
        {
            const float interpPercent = static_cast<float>( (key - lowerKey) / (upperKey - lowerKey) );
            Value interpVal;
            interpVal.SetFromSlerp( interpPercent, lowerValue, upperValue );
            return interpVal;
        }
    };

    template<>
    struct GlsSphericalLinearInterpolator<Vector> : GlsKeyframeInterpolator<Vector>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef GlsKeyframeInterpolator<Vector>::Value  Value; 
        typedef GlsKeyframeInterpolator<Value>::Key     Key;   
        typedef GlsKeyframeCurveBase::Size              Size;  

        GlsSphericalLinearInterpolator()
        {
            for( Size n = 0; n < s_cacheSize; ++n )
            {
                _cache[n].second = GlsQuaternionD( _cache[n].first );
            }
        }

        Value operator()(
            const Key&   key,  
            const Key&   lowerKey,   const Key&   upperKey, 
            const Value& lowerValue, const Value& upperValue ) const // override
        {
            const LowerUpperQuaternions quaternions   = GetQuaternionsFromCache( lowerValue, upperValue );
            const float                 interpPercent = static_cast<float>( (key - lowerKey) / (upperKey - lowerKey) );
            GlsQuaternionD interpVal;
            interpVal.SetFromSlerp( interpPercent, quaternions.first, quaternions.second );
            return interpVal.GetEulerAngles() * float(RAD_TO_DEG);
        }

      #if GLS_DEBUG // For testing
        static Size                              GetCacheSize()   { return s_cacheSize; }
        const std::pair<Vector, GlsQuaternionD>* GetCache() const { return _cache;      }
      #endif

    private:
        // Types
        typedef std::pair<GlsQuaternionD, GlsQuaternionD> LowerUpperQuaternions;

        // Looks for the quaternions in the cache or computes them afresh. Updates the cache if needed.
        std::pair<GlsQuaternionD, GlsQuaternionD> GetQuaternionsFromCache( const Value& lowerValue, const Value& upperValue ) const
        {
            GlsQuaternionD lowerQuat;
            GlsQuaternionD upperQuat;

            // Initializing to the size represents the quat not being found yet
            Size lowerNdx = s_cacheSize;
            Size upperNdx = s_cacheSize;

            // Search the cache for previously used quaternions
            for( Size n = 0; n < s_cacheSize && (lowerNdx == s_cacheSize || upperNdx == s_cacheSize); ++n )
            {
                if( lowerNdx == s_cacheSize && lowerValue.CloseTo( _cache[n].first ) )
                {
                    lowerQuat = _cache[n].second;
                    lowerNdx  = n;
                }
                else if( upperNdx == s_cacheSize && upperValue.CloseTo( _cache[n].first ) )
                {
                    upperQuat = _cache[n].second;
                    upperNdx  = n;
                }
            }

            // Did we find them?
            if( lowerNdx == s_cacheSize )
            {
                const Vector anglesInRadians = lowerValue * float(DEG_TO_RAD);
                lowerQuat.SetFromEulerAngles( anglesInRadians.x, anglesInRadians.y, anglesInRadians.z );
                // Save return val so we don't cache upper on top of a newly cached lower
                lowerNdx = SaveInCache( lowerValue, lowerQuat, lowerNdx, upperNdx );
            }

            if( upperNdx == s_cacheSize )
            {
                const Vector anglesInRadians = upperValue * float(DEG_TO_RAD);
                upperQuat.SetFromEulerAngles( anglesInRadians.x, anglesInRadians.y, anglesInRadians.z );
                SaveInCache( upperValue, upperQuat, lowerNdx, upperNdx ); // Ignore return val
            }

            return std::make_pair( lowerQuat, upperQuat );
        }

        Size SaveInCache( const Value& value, const GlsQuaternionD& quat, const Size lowerNdx, const Size upperNdx ) const
        {
            for( Size n = 0; n < s_cacheSize; ++n )
            {
                if( n == lowerNdx || n == upperNdx )
                {
                    continue;
                }
                _cache[n] = std::make_pair( value, quat );
                return n;
            }
            DistiAssert( !"GlsAnimation: GlsSphericalLinearInterpolator<Vector> cache logic is broken." );
            return s_cacheSize;
        }

        // Data members
        static const Size                           s_cacheSize = 2;
        mutable std::pair< Vector, GlsQuaternionD > _cache[ s_cacheSize ];
    };


    template<class Value>
    struct GlsQuadraticEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * percent * percent + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuadraticEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (-(upperValue - lowerValue)) * percent * ( percent - 2 ) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuadraticEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2)); // t/(d/2)
            Value interpVal;
            if (percent < 1)
            {
                interpVal = ((upperValue - lowerValue)/2) * percent * percent + lowerValue;
            }
            else
            {
                --percent;
                interpVal = (-(upperValue - lowerValue) / 2) * (percent * (percent - 2) - 1) + lowerValue;
            }
            return interpVal;
        }
    };

    template<class Value>
    struct GlsCubicEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * percent * percent * percent + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsCubicEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey)) - 1;
            const Value interpVal = (upperValue - lowerValue) * (percent * percent * percent + 1) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsCubicEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2));
            Value interpVal;
            if (percent < 1)
            {
                interpVal = ((upperValue - lowerValue) / 2) * percent * percent * percent + lowerValue;
            }
            else
            {
                percent -= 2;
                interpVal = ((upperValue - lowerValue) / 2) * (percent * percent * percent + 2) + lowerValue;
            }
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuarticEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * percent * percent * percent * percent + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuarticEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey)) - 1;
            const Value interpVal = -(upperValue - lowerValue) * (percent * percent * percent * percent - 1) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuarticEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2));
            Value interpVal;
            if (percent < 1)
            {
                interpVal = ((upperValue - lowerValue) / 2) * percent * percent * percent * percent + lowerValue;
            }
            else
            {
                percent -= 2;
                interpVal = -((upperValue - lowerValue) / 2) * (percent * percent * percent * percent - 2) + lowerValue;
            }
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuinticEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * percent * percent * percent * percent * percent + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuinticEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey)) - 1;
            const Value interpVal = (upperValue - lowerValue) * (percent * percent * percent * percent * percent + 1) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsQuinticEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2));
            Value interpVal;
            if (percent < 1)
            {
                interpVal = ((upperValue - lowerValue) / 2) * percent * percent * percent * percent * percent + lowerValue;
            }
            else
            {
                percent -= 2;
                interpVal = ((upperValue - lowerValue) / 2) * (percent * percent * percent * percent * percent + 2) + lowerValue;
            }
            return interpVal;
        }
    };

    template<class Value>
    struct GlsSinusoidalEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = -(upperValue - lowerValue) * std::cos(percent * (Float(Detail::g_pi) / 2)) + (upperValue - lowerValue) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsSinusoidalEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * std::sin(percent *  (Float(Detail::g_pi) / 2)) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsSinusoidalEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = -((upperValue - lowerValue) / 2) * (std::cos(Float(Detail::g_pi)*percent) - 1) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsExponentialEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * ( std::pow( Float(2.0), 10 * ( percent - 1 ) ) ) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsExponentialEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * ( -std::pow( Float(2.0), -10 * percent ) + 1 ) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsExponentialEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2));
            Value interpVal;
            if (percent < 1)
            {
                interpVal = ((upperValue - lowerValue) / 2) * std::pow( Float(2.0), 10*(percent - 1) ) + lowerValue;
            }
            else
            {
                --percent;
                interpVal = ((upperValue - lowerValue) / 2) * (-std::pow(Float(2.0), -10 * percent) + 2) + lowerValue;
            }
            return interpVal;
        }
    };

    template<class Value>
    struct GlsCircularEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = -(upperValue - lowerValue) * (std::sqrt(1 - percent*percent) - 1) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsCircularEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey)) - 1;
            const Value interpVal = (upperValue - lowerValue) * std::sqrt(1 - percent*percent) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsCircularEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2));
            Value interpVal;
            if (percent < 1)
            {
                interpVal = -((upperValue - lowerValue) / 2) * (std::sqrt(1 - percent*percent) - 1) + lowerValue;
            }
            else
            {
                percent -= 2;
                interpVal = ((upperValue - lowerValue) / 2) * (std::sqrt(1 - percent*percent) + 1) + lowerValue;
            }
            return interpVal;
        }
    };
    
    template<class Value>
    struct GlsElasticEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey)) - 1;
            const Value interpVal = (-((upperValue - lowerValue) * std::pow(Float(2.0),10*percent) * std::sin( (percent-.075f)*(Float(2.0) * Float(Detail::g_pi))/0.3f)) + lowerValue );
            return interpVal;
        }
    };

    template<class Value>
    struct GlsElasticEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = ((upperValue - lowerValue) * std::pow(Float(2.0),-10*(percent)) * std::sin( (percent-.075f)*(Float(2.0) * Float(Detail::g_pi))/0.3f) + upperValue );
            return interpVal;
        }
    };

    template<class Value>
    struct GlsElasticEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2)) - 1;
            Value interpVal;
            if (percent < 0)
            {
                interpVal = ((upperValue - lowerValue) * std::pow(Float(2.0),  10*percent) * std::sin( (percent-.1125f)*(Float(2.0) * Float(Detail::g_pi))/.45f )) * -0.5f + lowerValue;
            }
            else
            {
                interpVal = (upperValue - lowerValue) * std::pow(Float(2.0),-10*(percent)) * std::sin( (percent-.1125f)*(Float(2.0) * Float(Detail::g_pi))/.45f )*.5f + upperValue;
            }
            return interpVal;
        }
    };
    
    template<class Value>
    struct GlsBounceEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>(((upperKey - lowerKey) - (key - lowerKey)) / (upperKey - lowerKey));
            Value interpVal;
            if( percent < (1/2.75) )
            {
                interpVal = (upperValue - lowerValue)*(  7.5625f*percent*percent) + lowerValue;
            }
            else if( percent <     (2/2.75) )
            {
                interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-1.500f/2.75f)*(percent-1.500f/2.75f) ) + .75f) + lowerValue) ;
            }
            else if( (percent <   (2.5/2.75)) )
            {
                interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.250f/2.75f)*(percent-2.250f/2.75f) ) + .9375f) + lowerValue);
            }
            else
            {
                interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.625f/2.75f)*(percent-2.625f/2.75f) ) + .984375f) + lowerValue);
            }
            return (upperValue - lowerValue) - interpVal + lowerValue;
        }
    };

    template<class Value>
    struct GlsBounceEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            Value interpVal;
            if( percent < (1/2.75) )
            {
                interpVal = (upperValue - lowerValue)*(  7.5625f*percent*percent) + lowerValue;
            }
            else if( percent <     (2/2.75) )
            {
                interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-1.500f/2.75f)*(percent-1.500f/2.75f) ) + .75f) + lowerValue) ;
            }
            else if( (percent <   (2.5/2.75)) )
            {
                interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.250f/2.75f)*(percent-2.250f/2.75f) ) + .9375f) + lowerValue);
            }
            else
            {
                interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.625f/2.75f)*(percent-2.625f/2.75f) ) + .984375f) + lowerValue);
            }
            return interpVal;
        }
    };

    template<class Value>
    struct GlsBounceEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            if(((key - lowerKey) < (upperKey - lowerKey) * 0.5))
            {
                const Float percent = static_cast<Float>(((upperKey - lowerKey) - (2 * (key - lowerKey))) / (upperKey - lowerKey));
                Value interpVal;
                if( percent < (1/2.75) )
                {
                    interpVal = (upperValue - lowerValue)*(  7.5625f*percent*percent) + lowerValue;
                }
                else if( percent <     (2/2.75) )
                {
                    interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-1.500f/2.75f)*(percent-1.500f/2.75f) ) + .75f) + lowerValue) ;
                }
                else if( (percent <   (2.5/2.75)) )
                {
                    interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.250f/2.75f)*(percent-2.250f/2.75f) ) + .9375f) + lowerValue);
                }
                else
                {
                    interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.625f/2.75f)*(percent-2.625f/2.75f) ) + .984375f) + lowerValue);
                }
                return ((upperValue - lowerValue) - interpVal + lowerValue)  * 0.5f + lowerValue;
            }
            else
            {
                const Float percent = static_cast<Float>((2 * (key - lowerKey) -(upperKey - lowerKey))/ (upperKey - lowerKey));
                Value interpVal;
                if( percent < (1/2.75) )
                {
                    interpVal = (upperValue - lowerValue)*(  7.5625f*percent*percent) + lowerValue;
                }
                else if( percent <     (2/2.75) )
                {
                    interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-1.500f/2.75f)*(percent-1.500f/2.75f) ) + .75f) + lowerValue) ;
                }
                else if( (percent <   (2.5/2.75)) )
                {
                    interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.250f/2.75f)*(percent-2.250f/2.75f) ) + .9375f) + lowerValue);
                }
                else
                {
                    interpVal = ( (upperValue - lowerValue)*( (7.5625f*(percent-2.625f/2.75f)*(percent-2.625f/2.75f) ) + .984375f) + lowerValue);
                }
                return (interpVal) * 0.5f + (upperValue - lowerValue) * 0.5f + lowerValue;
            }
        }
    };

    template<class Value>
    struct GlsBackEaseInInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey));
            const Value interpVal = (upperValue - lowerValue) * percent * percent*((1.70158f+1)*percent - 1.70158f) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsBackEaseOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            const Float percent = static_cast<Float>((key - lowerKey) / (upperKey - lowerKey)) - 1;
            const Value interpVal = (upperValue - lowerValue) *(percent*percent*((1.70158f+1)*percent + 1.70158f) + 1) + lowerValue;
            return interpVal;
        }
    };

    template<class Value>
    struct GlsBackEaseInOutInterpolator : GlsKeyframeInterpolator<Value>
    {
        // Define dependent names for GCC's two-phase lookup
        typedef typename GlsKeyframeInterpolator<Value>::Key   Key;   
        typedef typename GlsKeyframeInterpolator<Value>::Float Float; 

        Value operator()(
            const Key&   key,
            const Key&   lowerKey,   const Key&   upperKey,
            const Value& lowerValue, const Value& upperValue) const // override
        {
            Float percent = static_cast<Float>((key - lowerKey) / ((upperKey - lowerKey) /2));
            Value interpVal;
            if (percent < 1)
            {
                interpVal = (upperValue - lowerValue) / 2 * (percent*percent*(3.5949095f*percent - 2.5949095f)) + lowerValue;
            }
            else
            {
                percent -= 2;
                interpVal = (upperValue - lowerValue) / 2 * (percent * percent *(3.5949095f*percent + 2.5949095f) + 2) + lowerValue;
            }
            return interpVal;
        }
    };

    namespace Detail
    {
        template<class Value> struct DefaultInterpolator                 { typedef GlsLinearInterpolator<Value>                   Type;  };
        template<>            struct DefaultInterpolator<GlsQuaternionD> { typedef GlsSphericalLinearInterpolator<GlsQuaternionD> Type;  }; 
        template<>            struct DefaultInterpolator<std::string>    { typedef GlsGatedInterpolator<std::string>              Type;  }; 
        template<>            struct DefaultInterpolator<glsColor>       { typedef GlsColorInterpolationAdapter                   Type;  }; 

        const GlsKeyframeCurveBase::Key g_nan = std::numeric_limits<GlsKeyframeCurveBase::Key>::quiet_NaN();

        inline bool IsNaN( const double d )
        {
          #ifdef __FAST_MATH__ 
            // GCC's -ffast-math flag doesn't support d != d checking for NaN, so we have to compare bit patterns
            return 0 == std::memcmp( reinterpret_cast<const void*>( &d ), reinterpret_cast<const void*>( &g_nan ), sizeof( double ) );
          #else
            return d != d;
          #endif
        }
    } // namespace Detail

    template<class T>
    class GlsKeyframeCurve : public GlsKeyframeCurveBase
    {
    public:
        typedef stdortr1::shared_ptr<      GlsKeyframeCurve>       Ptr;                 
        typedef stdortr1::shared_ptr<const GlsKeyframeCurve>       PtrConst;            
        typedef T                                                  Value;               
        typedef typename Detail::DefaultInterpolator<Value>::Type  DefaultInterpolator; 

        explicit GlsKeyframeCurve( const GlsKeyframeInterpolator<Value>* const interpolator = new DefaultInterpolator() ) 
            : _interpolator( interpolator ? interpolator : new DefaultInterpolator()  )
            , _lowerInterpNdx( 0 )
        {}

        explicit GlsKeyframeCurve( typename GlsKeyframeInterpolator<Value>::PtrConst interpolator ) 
            : _interpolator( interpolator ? interpolator : typename GlsKeyframeInterpolator<Value>::PtrConst(new DefaultInterpolator()) )
            , _lowerInterpNdx( 0 )
        {}

        Size GetKeyframeCount() const // override
        {
            return _keyframes.size();
        }

        KeyPair GetMinMaxKeys() const // override
        {
            // Handle precondition
            if( 0 == GetKeyframeCount() )
            {
                return std::make_pair( Detail::g_nan, Detail::g_nan );
            }

            return std::make_pair( _keyframes.front().key, _keyframes.back().key );
        }

        void AddKeyframe( const Key& key, const Value& value, const Key& tolerance = Detail::g_glsAnimationFloatTolerance )
        {
            DistiAssert( !Detail::IsNaN( key ) );

            const Size count = GetKeyframeCount();
            DistiAssert( count != (std::numeric_limits<Size>::max)() ); // Are we out of room? (Extra parens avoid the NOMINMAX problems on Windows.)

            // Find the insertion point
            Size n = 0;
            while( n < count && _keyframes[ n ].key < key )
            {
                ++n;
            }

            // Put the value in the keyframe list
            if( n < count && Equal( _keyframes[ n ].key, key, static_cast<float>( tolerance ) ) )
            {
                // Replace the existing keyframe
                _keyframes[ n ].value = value;
            }
            else
            {
                // Add a new keyframe
                _keyframes.insert( _keyframes.begin() + n, KeyValue( key, value ) );
            }
        }

        Value Interpolate( const Key& key ) const
        {
            // Handle edge cases
            const Size count = GetKeyframeCount();
            if( 0 == count || Detail::IsNaN( key ) )
            {
                return Value();
            }
            else if( 1 == count                                               // Only one value, no interpolation possible
                || Detail::FloatLessThanOrEqualTo( key, _keyframes[0].key ) ) // Clamp to lowest value
            {
                _lowerInterpNdx = 0;
                return _keyframes[ 0 ].value;
            }
            else if( Detail::FloatGreaterThanOrEqualTo( key, _keyframes[ count - 1 ].key ) ) // Clamp to highest value
            {
                _lowerInterpNdx = count - 2; // Save one before the last keyframe as the lower index
                return _keyframes[ count - 1 ].value;
            }

            // Find the right pair of interpolation keyframes
            _lowerInterpNdx = ComputeInterpLowerNdx( key, count );

            // Interpolate between the two keyframes
            const KeyValue lower = _keyframes[ _lowerInterpNdx     ];
            const KeyValue upper = _keyframes[ _lowerInterpNdx + 1 ];
            const Value    value = (*_interpolator)( key, lower.key, upper.key, lower.value, upper.value );
            return value;
        }

      #ifdef GLS_DEBUG // For testing
        Size GetLowerInterpNdx() const { return _lowerInterpNdx; }
      #endif

    private:
        // Find the lower index of the right pair of interpolation keyframes
        Size ComputeInterpLowerNdx( const Key& key, const Size& count ) const
        {
            // Can we use our previous interp value? If not, perform a linear search up or down
            // from the last used key. This is likely to be faster than a binary search on the
            // same key set (lower half or upper half) when the keys are changing monotonically up
            // or down in relatively small increments, which will usually be the case, because it
            // will almost always find the next key range within one or two comparisons.
            if(  key >= _keyframes[ _lowerInterpNdx     ].key 
             &&  key <= _keyframes[ _lowerInterpNdx + 1 ].key )
            {
                return _lowerInterpNdx;
            }
            else if( key < _keyframes[ _lowerInterpNdx ].key ) 
            {
                DistiAssert( _lowerInterpNdx != 0 ); // Should be caught by previous conditions

                // Search down in the list from the last interpolation point (see comment at top of function)
                Size interpLowerNdx = _lowerInterpNdx - 1;
                while( interpLowerNdx != 0 && key < _keyframes[ interpLowerNdx ].key )
                {
                    --interpLowerNdx;
                }
                return interpLowerNdx;
            }
            else
            {
                DistiAssert( _lowerInterpNdx != (count - 2) ); // Should be caught by previous conditions

                // Search up in the list from the last interpolation point (see comment at top of function)
                Size interpLowerNdx = _lowerInterpNdx + 1;
                while( interpLowerNdx < count - 2 && _keyframes[ interpLowerNdx + 1 ].key < key )
                {
                    ++interpLowerNdx;
                }
                return interpLowerNdx;
            }
        }

        // Key-value pair struct (improves readibility over std::pair)
        struct KeyValue
        {
            Key   key;
            Value value;

            KeyValue() {}
            KeyValue( const Key& key_, const Value& value_ ) 
                : key( key_ ), value( value_ ) 
            {}
        };

        // Data members
        std::vector< KeyValue >                           _keyframes; // Need random access, so a map isn't a good fit.
        typename GlsKeyframeInterpolator<Value>::PtrConst _interpolator;
        mutable Size                                      _lowerInterpNdx; // cache value
    };
}

#endif