catmullRom.h

Engine/source/util/catmullRom.h

More...

Classes:

Detailed Description

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