Engine/source/util/catmullRom.h

   1 //-----------------------------------------------------------------------------
   2 // Copyright (c) 2012 GarageGames, LLC
   3 //
   4 // Permission is hereby granted, free of charge, to any person obtaining a copy
   5 // of this software and associated documentation files (the "Software"), to
   6 // deal in the Software without restriction, including without limitation the
   7 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   8 // sell copies of the Software, and to permit persons to whom the Software is
   9 // furnished to do so, subject to the following conditions:
  10 //
  11 // The above copyright notice and this permission notice shall be included in
  12 // all copies or substantial portions of the Software.
  13 //
  14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  19 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  20 // IN THE SOFTWARE.
  21 //-----------------------------------------------------------------------------
  22
  23 #ifndef _CATMULLROM_H_
  24 #define _CATMULLROM_H_
  25
  26
  27 /// The shared base class used by the catmull rom
  28 /// interpolation template class.
  29 /// @see CatmullRom
  30 class CatmullRomBase
  31 {
  32 protected:
  33
  34    CatmullRomBase();
  35    virtual ~CatmullRomBase() {}
  36
  37 public:
  38
  39    /// Clean out all the data.
  40    virtual void clear();
  41
  42    /// Find length of curve between parameters t1 and t2.
  43    F32 arcLength( F32 t1, F32 t2 );
  44
  45    /// Get the total length of the curve.
  46    inline F32 getLength() { return mTotalLength; }
  47
  48    /// Get the closest previous control point to time t.
  49    U32 getPrevNode( F32 t );
  50
  51    /// Returns the time at idx (rather than at a F32 time)
  52    F32 getTime( U32 idx );
  53
  54    /// Find length of curve segment between parameters u1 and u2.
  55    virtual F32 segmentArcLength( U32 i, F32 u1, F32 u2 ) = 0;
  56
  57 protected:
  58
  59    static const F32 smX[];
  60    static const F32 smC[];
  61
  62    void _initialize( U32 count, const F32 *times = NULL );
  63
  64    /// The time to arrive at each point.
  65    F32 *mTimes;
  66
  67    /// the length of each curve segment.
  68    F32* mLengths;
  69
  70    /// The total length of curve.
  71    F32 mTotalLength;
  72
  73    /// The number of points and times.
  74    U32 mCount;
  75 };
  76
  77
  78 /// The catmull-rom template class for performing interpolation
  79 /// over an arbitraty type.
  80 template<typename TYPE>
  81 class CatmullRom : public CatmullRomBase
  82 {
  83 public:
  84
  85    CatmullRom();
  86    virtual ~CatmullRom();
  87
  88    /// Initialization.
  89    void initialize( U32 count, const TYPE *positions, const F32 *times = NULL );
  90
  91    // evaluate position
  92    TYPE evaluate( F32 t );
  93
  94    /// Evaluate derivative at parameter t.
  95    TYPE velocity( F32 t );
  96
  97    // Evaluate second derivative at parameter t.
  98    TYPE acceleration( F32 t );
  99
 100    // Returns the position at idx (rather than at a F32 time)
 101    TYPE getPosition( U32 idx );
 102
 103    // CatmullRomBase
 104    void clear();
 105    F32 segmentArcLength( U32 i, F32 u1, F32 u2 );
 106
 107 protected:
 108
 109    /// The sample points.
 110    TYPE* mPositions;
 111
 112 private:
 113
 114    /// The copy constructors are disabled.
 115    CatmullRom( const CatmullRom &other );
 116    CatmullRom& operator=( const CatmullRom &other );
 117 };
 118
 119
 120 template<typename TYPE>
 121 inline CatmullRom<TYPE>::CatmullRom()
 122    :  CatmullRomBase(),
 123       mPositions( NULL )
 124 {
 125 }
 126
 127 template<typename TYPE>
 128 inline CatmullRom<TYPE>::~CatmullRom()
 129 {
 130    clear();
 131 }
 132
 133 template<typename TYPE>
 134 inline void CatmullRom<TYPE>::clear()
 135 {
 136    delete [] mPositions;
 137    mPositions = NULL;
 138
 139    CatmullRomBase::clear();
 140 }
 141
 142 template<typename TYPE>
 143 inline void CatmullRom<TYPE>::initialize( U32 count, const TYPE *positions, const F32 *times )
 144 {
 145    AssertFatal( positions, "CatmullRom::initialize - Got null position!" );
 146    AssertFatal( count > 1, "CatmullRom::initialize - Must have more than 2 points!" );
 147
 148    // Clean up any previous state.
 149    clear();
 150
 151    // copy the points.
 152    mPositions = new TYPE[count];
 153    for ( U32 i = 0; i < count; ++i )
 154       mPositions[i] = positions[i];
 155
 156    _initialize( count, times );
 157 }
 158
 159 template<typename TYPE>
 160 inline TYPE CatmullRom<TYPE>::evaluate( F32 t )
 161 {
 162    AssertFatal( mCount >= 2, "CatmullRom::evaluate - Not initialized!" );
 163
 164    // handle boundary conditions
 165    if ( t <= mTimes[0] )
 166       return mPositions[0];
 167    else if ( t >= mTimes[mCount-1] )
 168       return mPositions[mCount-1];
 169
 170    // find segment and parameter
 171    U32 i;  // segment #
 172    for ( i = 0; i < mCount-1; ++i )
 173    {
 174       if ( t <= mTimes[i+1] )
 175       {
 176          break;
 177       }
 178    }
 179
 180    AssertFatal( i >= 0 && i < mCount, "CatmullRom::evaluate - Got bad index!" );
 181
 182    F32 t0 = mTimes[i];
 183    F32 t1 = mTimes[i+1];
 184    F32 u = (t - t0)/(t1 - t0);
 185
 186    S32 idx0, idx1, idx2, idx3;
 187    idx0 = i - 1;
 188    idx1 = i;
 189    idx2 = i + 1;
 190    idx3 = i + 2;
 191
 192    if ( idx0 < 0 )
 193       idx0 = 0;
 194    if ( idx3 >= mCount )
 195       idx3 = mCount - 1;
 196
 197    TYPE A = 3.0f*mPositions[idx1]
 198             - mPositions[idx0]
 199             - 3.0f*mPositions[idx2]
 200             + mPositions[idx3];
 201
 202    TYPE B = 2.0f*mPositions[idx0]
 203             - 5.0f*mPositions[idx1]
 204             + 4.0f*mPositions[idx2]
 205             - mPositions[idx3];
 206
 207    TYPE C = mPositions[idx2] - mPositions[idx0];
 208
 209    return mPositions[i] + (0.5f*u)*(C + u*(B + u*A));
 210 }
 211
 212 template<typename TYPE>
 213 inline TYPE CatmullRom<TYPE>::velocity( F32 t )
 214 {
 215    AssertFatal( mCount >= 2, "CatmullRom::velocity - Not initialized!" );
 216
 217    // handle boundary conditions
 218    if ( t <= mTimes[0] )
 219       t = 0.0f;
 220    else if ( t > mTimes[mCount-1] )
 221       t = mTimes[mCount-1];
 222
 223    // find segment and parameter
 224    U32 i;
 225    for ( i = 0; i < mCount-1; ++i )
 226    {
 227       if ( t <= mTimes[i+1] )
 228       {
 229          break;
 230       }
 231    }
 232    F32 t0 = mTimes[i];
 233    F32 t1 = mTimes[i+1];
 234    F32 u = (t - t0)/(t1 - t0);
 235
 236    S32 idx0, idx1, idx2, idx3;
 237    idx0 = i - 1;
 238    idx1 = i;
 239    idx2 = i + 1;
 240    idx3 = i + 2;
 241
 242    if ( idx0 < 0 )
 243       idx0 = 0;
 244    if ( idx3 >= mCount )
 245       idx3 = mCount - 1;
 246
 247    TYPE A = 3.0f*mPositions[idx1]
 248             - mPositions[idx0]
 249             - 3.0f*mPositions[idx2]
 250             + mPositions[idx3];
 251
 252    TYPE B = 2.0f*mPositions[idx0]
 253             - 5.0f*mPositions[idx1]
 254             + 4.0f*mPositions[idx2]
 255             - mPositions[idx3];
 256
 257    TYPE C = mPositions[idx2] - mPositions[idx0];
 258
 259    return 0.5f*C + u*(B + 1.5f*u*A);
 260 }
 261
 262 template<typename TYPE>
 263 inline TYPE CatmullRom<TYPE>::acceleration( F32 t )
 264 {
 265    AssertFatal( mCount >= 2, "CatmullRom::acceleration - Not initialized!" );
 266
 267    // handle boundary conditions
 268    if ( t <= mTimes[0] )
 269       t = 0.0f;
 270    else if ( t > mTimes[mCount-1] )
 271       t = mTimes[mCount-1];
 272
 273    // find segment and parameter
 274    U32 i;
 275    for ( i = 0; i < mCount-1; ++i )
 276    {
 277       if ( t <= mTimes[i+1] )
 278       {
 279          break;
 280       }
 281    }
 282    F32 t0 = mTimes[i];
 283    F32 t1 = mTimes[i+1];
 284    F32 u = (t - t0)/(t1 - t0);
 285
 286    S32 idx0, idx1, idx2, idx3;
 287    idx0 = i - 1;
 288    idx1 = i;
 289    idx2 = i + 1;
 290    idx3 = i + 2;
 291
 292    if ( idx0 < 0 )
 293       idx0 = 0;
 294    if ( idx3 >= mCount )
 295       idx3 = mCount - 1;
 296
 297    TYPE A = 3.0f*mPositions[idx1]
 298             - mPositions[idx0]
 299             - 3.0f*mPositions[idx2]
 300             + mPositions[idx3];
 301
 302    TYPE B = 2.0f*mPositions[idx0]
 303             - 5.0f*mPositions[idx1]
 304             + 4.0f*mPositions[idx2]
 305             - mPositions[idx3];
 306
 307    TYPE C = mPositions[idx2] - mPositions[idx0];
 308
 309    return B + (3.0f*u)*A;
 310 }
 311
 312 template<typename TYPE>
 313 inline TYPE CatmullRom<TYPE>::getPosition( U32 idx )
 314 {
 315    AssertFatal( idx >= 0 && idx < mCount-1, "CatmullRom<>::getPosition - Got bad index!" );
 316    return mPositions[idx];
 317 }
 318
 319 template<typename TYPE>
 320 inline F32 CatmullRom<TYPE>::segmentArcLength( U32 i, F32 u1, F32 u2 )
 321 {
 322    AssertFatal( i >= 0 && i < mCount-1, "CatmullRom<>::getPosition - Got bad index!" );
 323
 324    if ( u2 <= u1 )
 325       return 0.0f;
 326
 327    if ( u1 < 0.0f )
 328       u1 = 0.0f;
 329
 330    if ( u2 > 1.0f )
 331       u2 = 1.0f;
 332
 333    S32 idx0, idx1, idx2, idx3;
 334    idx0 = i - 1;
 335    idx1 = i;
 336    idx2 = i + 1;
 337    idx3 = i + 2;
 338
 339    if ( idx0 < 0 )
 340       idx0 = 0;
 341    if ( idx3 >= mCount )
 342       idx3 = mCount - 1;
 343
 344    TYPE A = 3.0f*mPositions[idx1]
 345    - mPositions[idx0]
 346    - 3.0f*mPositions[idx2]
 347    + mPositions[idx3];
 348    TYPE B = 2.0f*mPositions[idx0]
 349    - 5.0f*mPositions[idx1]
 350    + 4.0f*mPositions[idx2]
 351    - mPositions[idx3];
 352    TYPE C = mPositions[idx2] - mPositions[idx0];
 353
 354    F32 sum = 0.0f;
 355
 356    for ( U32 j = 0; j < 5; ++j )
 357    {
 358       F32 u = 0.5f*((u2 - u1)*smX[j] + u2 + u1);
 359       TYPE derivative;
 360       if ( i == 0 || i >= mCount-2)
 361          derivative = 0.5f*B + u*A;
 362       else
 363          derivative = 0.5f*C + u*(B + 1.5f*u*A);
 364       sum += smC[j]*derivative.len();
 365    }
 366    sum *= 0.5f*(u2-u1);
 367
 368    return sum;
 369 }
 370
 371 #endif // _CATMULLROM_H_