home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / math / Curve.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  69KB  |  2,573 lines
  1.  
  2. #ifndef __MATH_CURVE_H__
  3. #define __MATH_CURVE_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     Curve base template.
  9.  
  10. ===============================================================================
  11. */
  12.  
  13. template< class type >
  14. class idCurve {
  15. public:
  16.                         idCurve( void );
  17.     virtual                ~idCurve( void );
  18.  
  19.     virtual int            AddValue( const float time, const type &value );
  20.     virtual void        RemoveIndex( const int index ) { values.RemoveIndex(index); times.RemoveIndex(index); changed = true; }
  21.     virtual void        Clear( void ) { values.Clear(); times.Clear(); currentIndex = -1; changed = true; }
  22.  
  23.     virtual type        GetCurrentValue( const float time ) const;
  24.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  25.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  26.  
  27.     virtual bool        IsDone( const float time ) const;
  28.  
  29. // RAVEN BEGIN
  30. // jscott: added
  31.     void                SetGranularity( int gran ) { times.SetGranularity( gran ); values.SetGranularity( gran ); }
  32. // RAVEN END
  33.  
  34.     int                    GetNumValues( void ) const { return values.Num(); }
  35.     void                SetValue( const int index, const type &value ) { values[index] = value; changed = true; }
  36.     type                GetValue( const int index ) const { return values[index]; }
  37.     type *                GetValueAddress( const int index ) { return &values[index]; }
  38.     float                GetTime( const int index ) const { return times[index]; }
  39.  
  40.     float                GetLengthForTime( const float time ) const;
  41.     float                GetTimeForLength( const float length, const float epsilon = 0.1f ) const;
  42.     float                GetLengthBetweenKnots( const int i0, const int i1 ) const;
  43.  
  44.     void                MakeUniform( const float totalTime );
  45.     void                SetConstantSpeed( const float totalTime );
  46.     void                ShiftTime( const float deltaTime );
  47.     void                Translate( const type &translation );
  48.  
  49. // RAVEN BEGIN
  50. // ddynerman: spline joining
  51.     virtual bool        Weld( idCurve<type>* c ) const;
  52. // RAVEN END
  53.  
  54. protected:
  55.     idList<float>        times;            // knots
  56.     idList<type>        values;            // knot values
  57.     mutable int            currentIndex;    // cached index for fast lookup
  58.     mutable bool        changed;        // set whenever the curve changes
  59.  
  60.     int                    IndexForTime( const float time ) const;
  61.     float                TimeForIndex( const int index ) const;
  62.     type                ValueForIndex( const int index ) const;
  63.  
  64.     float                GetSpeed( const float time ) const;
  65.     float                RombergIntegral( const float t0, const float t1, const int order ) const;
  66. };
  67.  
  68. /*
  69. ====================
  70. idCurve::idCurve
  71. ====================
  72. */
  73. template< class type >
  74. ID_INLINE idCurve<type>::idCurve( void ) {
  75.     currentIndex = -1;
  76.     changed = false;
  77. }
  78.  
  79. /*
  80. ====================
  81. idCurve::~idCurve
  82. ====================
  83. */
  84. template< class type >
  85. ID_INLINE idCurve<type>::~idCurve( void ) {
  86. }
  87.  
  88. /*
  89. ====================
  90. idCurve::AddValue
  91.  
  92.   add a timed/value pair to the spline
  93.   returns the index to the inserted pair
  94. ====================
  95. */
  96. template< class type >
  97. ID_INLINE int idCurve<type>::AddValue( const float time, const type &value ) {
  98.     int i;
  99.  
  100.     i = IndexForTime( time );
  101.     times.Insert( time, i );
  102.     values.Insert( value, i );
  103.     changed = true;
  104.     return i;
  105. }
  106.  
  107. /*
  108. ====================
  109. idCurve::GetCurrentValue
  110.  
  111.   get the value for the given time
  112. ====================
  113. */
  114. template< class type >
  115. ID_INLINE type idCurve<type>::GetCurrentValue( const float time ) const {
  116.     int i;
  117.  
  118.     i = IndexForTime( time );
  119.     if ( i >= values.Num() ) {
  120.         return values[values.Num() - 1];
  121.     } else {
  122.         return values[i];
  123.     }
  124. }
  125.  
  126. /*
  127. ====================
  128. idCurve::GetCurrentFirstDerivative
  129.  
  130.   get the first derivative for the given time
  131. ====================
  132. */
  133. template< class type >
  134. ID_INLINE type idCurve<type>::GetCurrentFirstDerivative( const float time ) const {
  135.     return ( values[0] - values[0] );
  136. }
  137.  
  138. /*
  139. ====================
  140. idCurve::GetCurrentSecondDerivative
  141.  
  142.   get the second derivative for the given time
  143. ====================
  144. */
  145. template< class type >
  146. ID_INLINE type idCurve<type>::GetCurrentSecondDerivative( const float time ) const {
  147.     return ( values[0] - values[0] );
  148. }
  149.  
  150. /*
  151. ====================
  152. idCurve::IsDone
  153. ====================
  154. */
  155. template< class type >
  156. ID_INLINE bool idCurve<type>::IsDone( const float time ) const {
  157.     return ( time >= times[ times.Num() - 1 ] );
  158. }
  159.  
  160. /*
  161. ====================
  162. idCurve::GetSpeed
  163. ====================
  164. */
  165. template< class type >
  166. ID_INLINE float idCurve<type>::GetSpeed( const float time ) const {
  167.     int i;
  168.     float speed;
  169.     type value;
  170.  
  171.     value = GetCurrentFirstDerivative( time );
  172.     for ( speed = 0.0f, i = 0; i < value.GetDimension(); i++ ) {
  173.         speed += value[i] * value[i];
  174.     }
  175.     return idMath::Sqrt( speed );
  176. }
  177.  
  178. /*
  179. ====================
  180. idCurve::RombergIntegral
  181. ====================
  182. */
  183. template< class type >
  184. ID_INLINE float idCurve<type>::RombergIntegral( const float t0, const float t1, const int order ) const {
  185.     int i, j, k, m, n;
  186.     float sum, delta;
  187.     float *temp[2];
  188.  
  189.     temp[0] = (float *) _alloca16( order * sizeof( float ) );
  190.     temp[1] = (float *) _alloca16( order * sizeof( float ) );
  191.  
  192.     delta = t1 - t0;
  193.     temp[0][0] = 0.5f * delta * ( GetSpeed( t0 ) + GetSpeed( t1 ) );
  194.  
  195.     for ( i = 2, m = 1; i <= order; i++, m *= 2, delta *= 0.5f ) {
  196.  
  197.         // approximate using the trapezoid rule
  198.         sum = 0.0f;
  199.         for ( j = 1; j <= m; j++ ) {
  200.             sum += GetSpeed( t0 + delta * ( j - 0.5f ) );
  201.         }
  202.  
  203.         // Richardson extrapolation
  204.         temp[1][0] = 0.5f * ( temp[0][0] + delta * sum );
  205.         for ( k = 1, n = 4; k < i; k++, n *= 4 ) {
  206.             temp[1][k] = ( n * temp[1][k-1] - temp[0][k-1] ) / ( n - 1 );
  207.         }
  208.  
  209.         for ( j = 0; j < i; j++ ) {
  210.             temp[0][j] = temp[1][j];
  211.         }
  212.     }
  213.     return temp[0][order-1];
  214. }
  215.  
  216. /*
  217. ====================
  218. idCurve::GetLengthBetweenKnots
  219. ====================
  220. */
  221. template< class type >
  222. ID_INLINE float idCurve<type>::GetLengthBetweenKnots( const int i0, const int i1 ) const {
  223.     float length = 0.0f;
  224.     for ( int i = i0; i < i1; i++ ) {
  225.         length += RombergIntegral( times[i], times[i+1], 5 );
  226.     }
  227.     return length;
  228. }
  229.  
  230. /*
  231. ====================
  232. idCurve::GetLengthForTime
  233. ====================
  234. */
  235. template< class type >
  236. ID_INLINE float idCurve<type>::GetLengthForTime( const float time ) const {
  237.     float length = 0.0f;
  238.     int index = IndexForTime( time );
  239.     for ( int i = 0; i < index; i++ ) {
  240.         length += RombergIntegral( times[i], times[i+1], 5 );
  241.     }
  242.     length += RombergIntegral( times[index], time, 5 );
  243.     return length;
  244. }
  245.  
  246. /*
  247. ====================
  248. idCurve::GetTimeForLength
  249. ====================
  250. */
  251. template< class type >
  252. ID_INLINE float idCurve<type>::GetTimeForLength( const float length, const float epsilon ) const {
  253.     int i, index;
  254.     float *accumLength, totalLength, len0, len1, t, diff;
  255.  
  256.     if ( length <= 0.0f ) {
  257.         return times[0];
  258.     }
  259.  
  260.     accumLength = (float *) _alloca16( values.Num() * sizeof( float ) );
  261.     totalLength = 0.0f;
  262.     for ( index = 0; index < values.Num() - 1; index++ ) {
  263.         totalLength += GetLengthBetweenKnots( index, index + 1 );
  264.         accumLength[index] = totalLength;
  265.         if ( length < accumLength[index] ) {
  266.             break;
  267.         }
  268.     }
  269.  
  270.     if ( index >= values.Num() - 1 ) {
  271.         return times[times.Num() - 1];
  272.     }
  273.  
  274.     if ( index == 0 ) {
  275.         len0 = length;
  276.         len1 = accumLength[0];
  277.     } else {
  278.         len0 = length - accumLength[index-1];
  279.         len1 = accumLength[index] - accumLength[index-1];
  280.     }
  281.  
  282.     // invert the arc length integral using Newton's method
  283.     t = ( times[index+1] - times[index] ) * len0 / len1;
  284.     for ( i = 0; i < 32; i++ ) {
  285.         diff = RombergIntegral( times[index], times[index] + t, 5 ) - len0;
  286.         if ( idMath::Fabs( diff ) <= epsilon ) {
  287.             return times[index] + t;
  288.         }
  289.         t -= diff / GetSpeed( times[index] + t );
  290.     }
  291.     return times[index] + t;
  292. }
  293.  
  294. /*
  295. ====================
  296. idCurve::MakeUniform
  297. ====================
  298. */
  299. template< class type >
  300. ID_INLINE void idCurve<type>::MakeUniform( const float totalTime ) {
  301.     int i, n;
  302.  
  303.     n = times.Num() - 1;
  304.     for ( i = 0; i <= n; i++ ) {
  305.         times[i] = i * totalTime / n;
  306.     }
  307.     changed = true;
  308. }
  309.  
  310. /*
  311. ====================
  312. idCurve::SetConstantSpeed
  313. ====================
  314. */
  315. template< class type >
  316. ID_INLINE void idCurve<type>::SetConstantSpeed( const float totalTime ) {
  317. // RAVEN BEGIN
  318. // bdube: fixed warning
  319.     int i;
  320. // RAVEN END
  321.     float *length, totalLength, scale, t;
  322.  
  323.     length = (float *) _alloca16( values.Num() * sizeof( float ) );
  324.     totalLength = 0.0f;
  325.     for ( i = 0; i < values.Num() - 1; i++ ) {
  326.         length[i] = GetLengthBetweenKnots( i, i + 1 );
  327.         totalLength += length[i];
  328.     }
  329.     scale = totalTime / totalLength;
  330.     for ( t = 0.0f, i = 0; i < times.Num() - 1; i++ ) {
  331.         times[i] = t;
  332.         t += scale * length[i];
  333.     }
  334.     times[times.Num() - 1] = totalTime;
  335.     changed = true;
  336. }
  337.  
  338. /*
  339. ====================
  340. idCurve::ShiftTime
  341. ====================
  342. */
  343. template< class type >
  344. ID_INLINE void idCurve<type>::ShiftTime( const float deltaTime ) {
  345.     for ( int i = 0; i < times.Num(); i++ ) {
  346.         times[i] += deltaTime;
  347.     }
  348.     changed = true;
  349. }
  350.  
  351. /*
  352. ====================
  353. idCurve::Translate
  354. ====================
  355. */
  356. template< class type >
  357. ID_INLINE void idCurve<type>::Translate( const type &translation ) {
  358.     for ( int i = 0; i < values.Num(); i++ ) {
  359.         values[i] += translation;
  360.     }
  361.     changed = true;
  362. }
  363.  
  364. /*
  365. ====================
  366. idCurve::IndexForTime
  367.  
  368.   find the index for the first time greater than or equal to the given time
  369. ====================
  370. */
  371. template< class type >
  372. ID_INLINE int idCurve<type>::IndexForTime( const float time ) const {
  373.     int len, mid, offset, res;
  374.  
  375.     if ( currentIndex >= 0 && currentIndex <= times.Num() ) {
  376.         // use the cached index if it is still valid
  377.         if ( currentIndex == 0 ) {
  378.             if ( time <= times[currentIndex] ) {
  379.                 return currentIndex;
  380.             }
  381.         } else if ( currentIndex == times.Num() ) {
  382.             if ( time > times[currentIndex-1] ) {
  383.                 return currentIndex;
  384.             }
  385.         } else if ( time > times[currentIndex-1] && time <= times[currentIndex] ) {
  386.             return currentIndex;
  387.         } else if ( time > times[currentIndex] && ( currentIndex+1 == times.Num() || time <= times[currentIndex+1] ) ) {
  388.             // use the next index
  389.             currentIndex++;
  390.             return currentIndex;
  391.         }
  392.     }
  393.  
  394.     // use binary search to find the index for the given time
  395.     len = times.Num();
  396.     mid = len;
  397.     offset = 0;
  398.     res = 0;
  399.     while( mid > 0 ) {
  400.         mid = len >> 1;
  401.         if ( time == times[offset+mid] ) {
  402.             return offset+mid;
  403.         } else if ( time > times[offset+mid] ) {
  404.             offset += mid;
  405.             len -= mid;
  406.             res = 1;
  407.         } else {
  408.             len -= mid;
  409.             res = 0;
  410.         }
  411.     }
  412.     currentIndex = offset+res;
  413.     return currentIndex;
  414. }
  415.  
  416. /*
  417. ====================
  418. idCurve::ValueForIndex
  419.  
  420.   get the value for the given time
  421. ====================
  422. */
  423. template< class type >
  424. ID_INLINE type idCurve<type>::ValueForIndex( const int index ) const {
  425.     int n = values.Num()-1;
  426.  
  427.     if ( index < 0 ) {
  428.         return values[0] + index * ( values[1] - values[0] );
  429.     } else if ( index > n ) {
  430.         return values[n] + ( index - n ) * ( values[n] - values[n-1] );
  431.     }
  432.     return values[index];
  433. }
  434.  
  435. /*
  436. ====================
  437. idCurve::TimeForIndex
  438.  
  439.   get the value for the given time
  440. ====================
  441. */
  442. template< class type >
  443. ID_INLINE float idCurve<type>::TimeForIndex( const int index ) const {
  444.     int n = times.Num()-1;
  445.  
  446.     if ( index < 0 ) {
  447.         return times[0] + index * ( times[1] - times[0] );
  448.     } else if ( index > n ) {
  449.         return times[n] + ( index - n ) * ( times[n] - times[n-1] );
  450.     }
  451.     return times[index];
  452. }
  453.  
  454. // RAVEN BEGIN
  455. // ddynerman: spline welding
  456. /*
  457. ====================
  458. idCurve::Weld
  459.  
  460.   Weld splines, implementation specific - parent version does nothing
  461. ====================
  462. */
  463. template< class type >
  464. ID_INLINE bool idCurve<type>::Weld( idCurve<type>* c ) const {
  465.     return false;
  466. }
  467. // RAVEN END
  468.  
  469.  
  470. /*
  471. ===============================================================================
  472.  
  473.     Bezier Curve template.
  474.     The degree of the polynomial equals the number of knots minus one.
  475.  
  476. ===============================================================================
  477. */
  478.  
  479. template< class type >
  480. class idCurve_Bezier : public idCurve<type> {
  481. public:
  482.                         idCurve_Bezier( void );
  483.  
  484.     virtual type        GetCurrentValue( const float time ) const;
  485.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  486.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  487.  
  488. protected:
  489.     void                Basis( const int order, const float t, float *bvals ) const;
  490.     void                BasisFirstDerivative( const int order, const float t, float *bvals ) const;
  491.     void                BasisSecondDerivative( const int order, const float t, float *bvals ) const;
  492. };
  493.  
  494. /*
  495. ====================
  496. idCurve_Bezier::idCurve_Bezier
  497. ====================
  498. */
  499. template< class type >
  500. ID_INLINE idCurve_Bezier<type>::idCurve_Bezier( void ) {
  501. }
  502.  
  503. /*
  504. ====================
  505. idCurve_Bezier::GetCurrentValue
  506.  
  507.   get the value for the given time
  508. ====================
  509. */
  510. template< class type >
  511. ID_INLINE type idCurve_Bezier<type>::GetCurrentValue( const float time ) const {
  512.     int i;
  513.     float *bvals;
  514.     type v;
  515.  
  516.     bvals = (float *) _alloca16( values.Num() * sizeof( float ) );
  517.  
  518.     Basis( values.Num(), time, bvals );
  519.     v = bvals[0] * values[0];
  520.     for ( i = 1; i < values.Num(); i++ ) {
  521.         v += bvals[i] * values[i];
  522.     }
  523.     return v;
  524. }
  525.  
  526. /*
  527. ====================
  528. idCurve_Bezier::GetCurrentFirstDerivative
  529.  
  530.   get the first derivative for the given time
  531. ====================
  532. */
  533. template< class type >
  534. ID_INLINE type idCurve_Bezier<type>::GetCurrentFirstDerivative( const float time ) const {
  535.     int i;
  536.     float *bvals, d;
  537.     type v;
  538.  
  539.     bvals = (float *) _alloca16( values.Num() * sizeof( float ) );
  540.  
  541.     BasisFirstDerivative( values.Num(), time, bvals );
  542.     v = bvals[0] * values[0];
  543.     for ( i = 1; i < values.Num(); i++ ) {
  544.         v += bvals[i] * values[i];
  545.     }
  546.     d = ( times[times.Num()-1] - times[0] );
  547.     return ( (float) (values.Num()-1) / d ) * v;
  548. }
  549.  
  550. /*
  551. ====================
  552. idCurve_Bezier::GetCurrentSecondDerivative
  553.  
  554.   get the second derivative for the given time
  555. ====================
  556. */
  557. template< class type >
  558. ID_INLINE type idCurve_Bezier<type>::GetCurrentSecondDerivative( const float time ) const {
  559.     int i;
  560.     float *bvals, d;
  561.     type v;
  562.  
  563.     bvals = (float *) _alloca16( values.Num() * sizeof( float ) );
  564.  
  565.     BasisSecondDerivative( values.Num(), time, bvals );
  566.     v = bvals[0] * values[0];
  567.     for ( i = 1; i < values.Num(); i++ ) {
  568.         v += bvals[i] * values[i];
  569.     }
  570.     d = ( times[times.Num()-1] - times[0] );
  571.     return ( (float) (values.Num()-2) * (values.Num()-1) / ( d * d ) ) * v;
  572. }
  573.  
  574. /*
  575. ====================
  576. idCurve_Bezier::Basis
  577.  
  578.   bezier basis functions
  579. ====================
  580. */
  581. template< class type >
  582. ID_INLINE void idCurve_Bezier<type>::Basis( const int order, const float t, float *bvals ) const {
  583.     int i, j, d;
  584.     float *c, c1, c2, s, o, ps, po;
  585.  
  586.     bvals[0] = 1.0f;
  587.     d = order - 1;
  588.     if ( d <= 0 ) {
  589.         return;
  590.     }
  591.  
  592.     c = (float *) _alloca16( (d+1) * sizeof( float ) );
  593.     s = (float) ( t - times[0] ) / ( times[times.Num()-1] - times[0] );
  594.     o = 1.0f - s;
  595.     ps = s;
  596.     po = o;
  597.  
  598.     for ( i = 1; i < d; i++ ) {
  599.         c[i] = 1.0f;
  600.     }
  601.     for ( i = 1; i < d; i++ ) {
  602.         c[i-1] = 0.0f;
  603.         c1 = c[i];
  604.         c[i] = 1.0f;
  605.         for ( j = i+1; j <= d; j++ ) {
  606.             c2 = c[j];
  607.             c[j] = c1 + c[j-1];
  608.             c1 = c2;
  609.         }
  610.         bvals[i] = c[d] * ps;
  611.         ps *= s;
  612.     }
  613.     for ( i = d-1; i >= 0; i-- ) {
  614.         bvals[i] *= po;
  615.         po *= o;
  616.     }
  617.     bvals[d] = ps;
  618. }
  619.  
  620. /*
  621. ====================
  622. idCurve_Bezier::BasisFirstDerivative
  623.  
  624.   first derivative of bezier basis functions
  625. ====================
  626. */
  627. template< class type >
  628. ID_INLINE void idCurve_Bezier<type>::BasisFirstDerivative( const int order, const float t, float *bvals ) const {
  629.     int i;
  630.  
  631.     Basis( order-1, t, bvals+1 );
  632.     bvals[0] = 0.0f;
  633.     for ( i = 0; i < order-1; i++ ) {
  634.         bvals[i] -= bvals[i+1];
  635.     }
  636. }
  637.  
  638. /*
  639. ====================
  640. idCurve_Bezier::BasisSecondDerivative
  641.  
  642.   second derivative of bezier basis functions
  643. ====================
  644. */
  645. template< class type >
  646. ID_INLINE void idCurve_Bezier<type>::BasisSecondDerivative( const int order, const float t, float *bvals ) const {
  647.     int i;
  648.  
  649.     BasisFirstDerivative( order-1, t, bvals+1 );
  650.     bvals[0] = 0.0f;
  651.     for ( i = 0; i < order-1; i++ ) {
  652.         bvals[i] -= bvals[i+1];
  653.     }
  654. }
  655.  
  656.  
  657. /*
  658. ===============================================================================
  659.  
  660.     Quadratic Bezier Curve template.
  661.     Should always have exactly three knots.
  662.  
  663. ===============================================================================
  664. */
  665.  
  666. template< class type >
  667. class idCurve_QuadraticBezier : public idCurve<type> {
  668. public:
  669.                         idCurve_QuadraticBezier( void );
  670.  
  671.     virtual type        GetCurrentValue( const float time ) const;
  672.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  673.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  674.  
  675. protected:
  676.     void                Basis( const float t, float *bvals ) const;
  677.     void                BasisFirstDerivative( const float t, float *bvals ) const;
  678.     void                BasisSecondDerivative( const float t, float *bvals ) const;
  679. };
  680.  
  681. /*
  682. ====================
  683. idCurve_QuadraticBezier::idCurve_QuadraticBezier
  684. ====================
  685. */
  686. template< class type >
  687. ID_INLINE idCurve_QuadraticBezier<type>::idCurve_QuadraticBezier( void ) {
  688. }
  689.  
  690.  
  691. /*
  692. ====================
  693. idCurve_QuadraticBezier::GetCurrentValue
  694.  
  695.   get the value for the given time
  696. ====================
  697. */
  698. template< class type >
  699. ID_INLINE type idCurve_QuadraticBezier<type>::GetCurrentValue( const float time ) const {
  700.     float bvals[3];
  701.     assert( values.Num() == 3 );
  702.     Basis( time, bvals );
  703.     return ( bvals[0] * values[0] + bvals[1] * values[1] + bvals[2] * values[2] );
  704. }
  705.  
  706. /*
  707. ====================
  708. idCurve_QuadraticBezier::GetCurrentFirstDerivative
  709.  
  710.   get the first derivative for the given time
  711. ====================
  712. */
  713. template< class type >
  714. ID_INLINE type idCurve_QuadraticBezier<type>::GetCurrentFirstDerivative( const float time ) const {
  715.     float bvals[3], d;
  716.     assert( values.Num() == 3 );
  717.     BasisFirstDerivative( time, bvals );
  718.     d = ( times[2] - times[0] );
  719.     return ( bvals[0] * values[0] + bvals[1] * values[1] + bvals[2] * values[2] ) / d;
  720. }
  721.  
  722. /*
  723. ====================
  724. idCurve_QuadraticBezier::GetCurrentSecondDerivative
  725.  
  726.   get the second derivative for the given time
  727. ====================
  728. */
  729. template< class type >
  730. ID_INLINE type idCurve_QuadraticBezier<type>::GetCurrentSecondDerivative( const float time ) const {
  731.     float bvals[3], d;
  732.     assert( values.Num() == 3 );
  733.     BasisSecondDerivative( time, bvals );
  734.     d = ( times[2] - times[0] );
  735.     return ( bvals[0] * values[0] + bvals[1] * values[1] + bvals[2] * values[2] ) / ( d * d );
  736. }
  737.  
  738. /*
  739. ====================
  740. idCurve_QuadraticBezier::Basis
  741.  
  742.   quadratic bezier basis functions
  743. ====================
  744. */
  745. template< class type >
  746. ID_INLINE void idCurve_QuadraticBezier<type>::Basis( const float t, float *bvals ) const {
  747.     float s1 = (float) ( t - times[0] ) / ( times[2] - times[0] );
  748.     float s2 = s1 * s1;
  749.     bvals[0] = s2 - 2.0f * s1 + 1.0f;
  750.     bvals[1] = -2.0f * s2 + 2.0f * s1;
  751.     bvals[2] = s2;
  752. }
  753.  
  754. /*
  755. ====================
  756. idCurve_QuadraticBezier::BasisFirstDerivative
  757.  
  758.   first derivative of quadratic bezier basis functions
  759. ====================
  760. */
  761. template< class type >
  762. ID_INLINE void idCurve_QuadraticBezier<type>::BasisFirstDerivative( const float t, float *bvals ) const {
  763.     float s1 = (float) ( t - times[0] ) / ( times[2] - times[0] );
  764.     bvals[0] = 2.0f * s1 - 2.0f;
  765.     bvals[1] = -4.0f * s1 + 2.0f;
  766.     bvals[2] = 2.0f * s1;
  767. }
  768.  
  769. /*
  770. ====================
  771. idCurve_QuadraticBezier::BasisSecondDerivative
  772.  
  773.   second derivative of quadratic bezier basis functions
  774. ====================
  775. */
  776. template< class type >
  777. ID_INLINE void idCurve_QuadraticBezier<type>::BasisSecondDerivative( const float t, float *bvals ) const {
  778.     float s1 = (float) ( t - times[0] ) / ( times[2] - times[0] );
  779.     bvals[0] = 2.0f;
  780.     bvals[1] = -4.0f;
  781.     bvals[2] = 2.0f;
  782. }
  783.  
  784.  
  785. /*
  786. ===============================================================================
  787.  
  788.     Cubic Bezier Curve template.
  789.     Should always have exactly four knots.
  790.  
  791. ===============================================================================
  792. */
  793.  
  794. template< class type >
  795. class idCurve_CubicBezier : public idCurve<type> {
  796. public:
  797.                         idCurve_CubicBezier( void );
  798.  
  799.     virtual type        GetCurrentValue( const float time ) const;
  800.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  801.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  802.  
  803. protected:
  804.     void                Basis( const float t, float *bvals ) const;
  805.     void                BasisFirstDerivative( const float t, float *bvals ) const;
  806.     void                BasisSecondDerivative( const float t, float *bvals ) const;
  807. };
  808.  
  809. /*
  810. ====================
  811. idCurve_CubicBezier::idCurve_CubicBezier
  812. ====================
  813. */
  814. template< class type >
  815. ID_INLINE idCurve_CubicBezier<type>::idCurve_CubicBezier( void ) {
  816. }
  817.  
  818.  
  819. /*
  820. ====================
  821. idCurve_CubicBezier::GetCurrentValue
  822.  
  823.   get the value for the given time
  824. ====================
  825. */
  826. template< class type >
  827. ID_INLINE type idCurve_CubicBezier<type>::GetCurrentValue( const float time ) const {
  828.     float bvals[4];
  829.     assert( values.Num() == 4 );
  830.     Basis( time, bvals );
  831.     return ( bvals[0] * values[0] + bvals[1] * values[1] + bvals[2] * values[2] + bvals[3] * values[3] );
  832. }
  833.  
  834. /*
  835. ====================
  836. idCurve_CubicBezier::GetCurrentFirstDerivative
  837.  
  838.   get the first derivative for the given time
  839. ====================
  840. */
  841. template< class type >
  842. ID_INLINE type idCurve_CubicBezier<type>::GetCurrentFirstDerivative( const float time ) const {
  843.     float bvals[4], d;
  844.     assert( values.Num() == 4 );
  845.     BasisFirstDerivative( time, bvals );
  846.     d = ( times[3] - times[0] );
  847.     return ( bvals[0] * values[0] + bvals[1] * values[1] + bvals[2] * values[2] + bvals[3] * values[3] ) / d;
  848. }
  849.  
  850. /*
  851. ====================
  852. idCurve_CubicBezier::GetCurrentSecondDerivative
  853.  
  854.   get the second derivative for the given time
  855. ====================
  856. */
  857. template< class type >
  858. ID_INLINE type idCurve_CubicBezier<type>::GetCurrentSecondDerivative( const float time ) const {
  859.     float bvals[4], d;
  860.     assert( values.Num() == 4 );
  861.     BasisSecondDerivative( time, bvals );
  862.     d = ( times[3] - times[0] );
  863.     return ( bvals[0] * values[0] + bvals[1] * values[1] + bvals[2] * values[2] + bvals[3] * values[3] ) / ( d * d );
  864. }
  865.  
  866. /*
  867. ====================
  868. idCurve_CubicBezier::Basis
  869.  
  870.   cubic bezier basis functions
  871. ====================
  872. */
  873. template< class type >
  874. ID_INLINE void idCurve_CubicBezier<type>::Basis( const float t, float *bvals ) const {
  875.     float s1 = (float) ( t - times[0] ) / ( times[3] - times[0] );
  876.     float s2 = s1 * s1;
  877.     float s3 = s2 * s1;
  878.     bvals[0] = -s3 + 3.0f * s2 - 3.0f * s1 + 1.0f;
  879.     bvals[1] = 3.0f * s3 - 6.0f * s2 + 3.0f * s1;
  880.     bvals[2] = -3.0f * s3 + 3.0f * s2;
  881.     bvals[3] = s3;
  882. }
  883.  
  884. /*
  885. ====================
  886. idCurve_CubicBezier::BasisFirstDerivative
  887.  
  888.   first derivative of cubic bezier basis functions
  889. ====================
  890. */
  891. template< class type >
  892. ID_INLINE void idCurve_CubicBezier<type>::BasisFirstDerivative( const float t, float *bvals ) const {
  893.     float s1 = (float) ( t - times[0] ) / ( times[3] - times[0] );
  894.     float s2 = s1 * s1;
  895.     bvals[0] = -3.0f * s2 + 6.0f * s1 - 3.0f;
  896.     bvals[1] = 9.0f * s2 - 12.0f * s1 + 3.0f;
  897.     bvals[2] = -9.0f * s2 + 6.0f * s1;
  898.     bvals[3] = 3.0f * s2;
  899. }
  900.  
  901. /*
  902. ====================
  903. idCurve_CubicBezier::BasisSecondDerivative
  904.  
  905.   second derivative of cubic bezier basis functions
  906. ====================
  907. */
  908. template< class type >
  909. ID_INLINE void idCurve_CubicBezier<type>::BasisSecondDerivative( const float t, float *bvals ) const {
  910.     float s1 = (float) ( t - times[0] ) / ( times[3] - times[0] );
  911.     bvals[0] = -6.0f * s1 + 6.0f;
  912.     bvals[1] = 18.0f * s1 - 12.0f;
  913.     bvals[2] = -18.0f * s1 + 6.0f;
  914.     bvals[3] = 6.0f * s1;
  915. }
  916.  
  917.  
  918. /*
  919. ===============================================================================
  920.  
  921.     Spline base template.
  922.  
  923. ===============================================================================
  924. */
  925.  
  926. template< class type >
  927. class idCurve_Spline : public idCurve<type> {
  928. public:
  929.     enum                boundary_t { BT_FREE, BT_CLAMPED, BT_CLOSED };
  930.  
  931.                         idCurve_Spline( void );
  932.  
  933.     virtual bool        IsDone( const float time ) const;
  934.  
  935.     virtual void        SetBoundaryType( const boundary_t bt ) { boundaryType = bt; changed = true; }
  936.     virtual boundary_t    GetBoundaryType( void ) const { return boundaryType; }
  937.  
  938.     virtual void        SetCloseTime( const float t ) { closeTime = t; changed = true; }
  939. // RAVEN BEGIN
  940. // jsinger: changed to be const so that we can call it during binary serialization
  941.     virtual float        GetCloseTime( void ) const { return boundaryType == BT_CLOSED ? closeTime : 0.0f; }
  942. // RAVEN END
  943.  
  944. protected:
  945.     boundary_t            boundaryType;
  946.     float                closeTime;
  947.  
  948.     type                ValueForIndex( const int index ) const;
  949.     float                TimeForIndex( const int index ) const;
  950.     float                ClampedTime( const float t ) const;
  951. };
  952.  
  953. /*
  954. ====================
  955. idCurve_Spline::idCurve_Spline
  956. ====================
  957. */
  958. template< class type >
  959. ID_INLINE idCurve_Spline<type>::idCurve_Spline( void ) {
  960.     boundaryType = BT_FREE;
  961.     closeTime = 0.0f;
  962. }
  963.  
  964. /*
  965. ====================
  966. idCurve_Spline::ValueForIndex
  967.  
  968.   get the value for the given time
  969. ====================
  970. */
  971. template< class type >
  972. ID_INLINE type idCurve_Spline<type>::ValueForIndex( const int index ) const {
  973.     int n = values.Num()-1;
  974.  
  975.     if ( index < 0 ) {
  976.         if ( boundaryType == BT_CLOSED ) {
  977.             return values[ values.Num() + index % values.Num() ];
  978.         }
  979.         else {
  980.             return values[0] + (float)index * ( values[1] - values[0] );
  981.         }
  982.     }
  983.     else if ( index > n ) {
  984.         if ( boundaryType == BT_CLOSED ) {
  985.             return values[ index % values.Num() ];
  986.         }
  987.         else {
  988.             return values[n] + (float)( index - n ) * ( values[n] - values[n-1] );
  989.         }
  990.     }
  991.     return values[index];
  992. }
  993.  
  994. /*
  995. ====================
  996. idCurve_Spline::TimeForIndex
  997.  
  998.   get the value for the given time
  999. ====================
  1000. */
  1001. template< class type >
  1002. ID_INLINE float idCurve_Spline<type>::TimeForIndex( const int index ) const {
  1003.     int n = times.Num()-1;
  1004.  
  1005.     if ( index < 0 ) {
  1006.         if ( boundaryType == BT_CLOSED ) {
  1007.             return ( index / times.Num() ) * ( times[n] + closeTime ) - ( times[n] + closeTime - times[times.Num() + index % times.Num()] );
  1008.         }
  1009.         else {
  1010.             return times[0] + index * ( times[1] - times[0] );
  1011.         }
  1012.     }
  1013.     else if ( index > n ) {
  1014.         if ( boundaryType == BT_CLOSED ) {
  1015.             return ( index / times.Num() ) * ( times[n] + closeTime ) + times[index % times.Num()];
  1016.         }
  1017.         else {
  1018.             return times[n] + ( index - n ) * ( times[n] - times[n-1] );
  1019.         }
  1020.     }
  1021.     return times[index];
  1022. }
  1023.  
  1024. /*
  1025. ====================
  1026. idCurve_Spline::ClampedTime
  1027.  
  1028.   return the clamped time based on the boundary type
  1029. ====================
  1030. */
  1031. template< class type >
  1032. ID_INLINE float idCurve_Spline<type>::ClampedTime( const float t ) const {
  1033.     if ( boundaryType == BT_CLAMPED ) {
  1034.         if ( t < times[0] ) {
  1035.             return times[0];
  1036.         }
  1037.         else if ( t >= times[times.Num()-1] ) {
  1038.             return times[times.Num()-1];
  1039.         }
  1040.     }
  1041.     return t;
  1042. }
  1043.  
  1044. /*
  1045. ====================
  1046. idCurve_Spline::IsDone
  1047. ====================
  1048. */
  1049. template< class type >
  1050. ID_INLINE bool idCurve_Spline<type>::IsDone( const float time ) const {
  1051.     return ( boundaryType != BT_CLOSED && time >= times[ times.Num() - 1 ] );
  1052. }
  1053.  
  1054.  
  1055. /*
  1056. ===============================================================================
  1057.  
  1058.     Cubic Interpolating Spline template.
  1059.     The curve goes through all the knots.
  1060.  
  1061. ===============================================================================
  1062. */
  1063.  
  1064. template< class type >
  1065. class idCurve_NaturalCubicSpline : public idCurve_Spline<type> {
  1066. public:
  1067.                         idCurve_NaturalCubicSpline( void );
  1068.  
  1069.     virtual void        Clear( void ) { idCurve_Spline<type>::Clear(); values.Clear(); b.Clear(); c.Clear(); d.Clear(); }
  1070.  
  1071.     virtual type        GetCurrentValue( const float time ) const;
  1072.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  1073.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  1074.  
  1075. protected:
  1076.     mutable idList<type>b;
  1077.     mutable idList<type>c;
  1078.     mutable idList<type>d;
  1079.  
  1080.     void                Setup( void ) const;
  1081.     void                SetupFree( void ) const;
  1082.     void                SetupClamped( void ) const;
  1083.     void                SetupClosed( void ) const;
  1084. };
  1085.  
  1086. /*
  1087. ====================
  1088. idCurve_NaturalCubicSpline::idCurve_NaturalCubicSpline
  1089. ====================
  1090. */
  1091. template< class type >
  1092. ID_INLINE idCurve_NaturalCubicSpline<type>::idCurve_NaturalCubicSpline( void ) {
  1093. }
  1094.  
  1095. /*
  1096. ====================
  1097. idCurve_NaturalCubicSpline::GetCurrentValue
  1098.  
  1099.   get the value for the given time
  1100. ====================
  1101. */
  1102. template< class type >
  1103. ID_INLINE type idCurve_NaturalCubicSpline<type>::GetCurrentValue( const float time ) const {
  1104.     float clampedTime = ClampedTime( time );
  1105.     int i = IndexForTime( clampedTime );
  1106.     float s = time - TimeForIndex( i );
  1107.     Setup();
  1108.     return ( values[i] + s * ( b[i] + s * ( c[i] + s * d[i] ) ) );
  1109. }
  1110.  
  1111. /*
  1112. ====================
  1113. idCurve_NaturalCubicSpline::GetCurrentFirstDerivative
  1114.  
  1115.   get the first derivative for the given time
  1116. ====================
  1117. */
  1118. template< class type >
  1119. ID_INLINE type idCurve_NaturalCubicSpline<type>::GetCurrentFirstDerivative( const float time ) const {
  1120.     float clampedTime = ClampedTime( time );
  1121.     int i = IndexForTime( clampedTime );
  1122.     float s = time - TimeForIndex( i );
  1123.     Setup();
  1124.     return ( b[i] + s * ( 2.0f * c[i] + 3.0f * s * d[i] ) );
  1125. }
  1126.  
  1127. /*
  1128. ====================
  1129. idCurve_NaturalCubicSpline::GetCurrentSecondDerivative
  1130.  
  1131.   get the second derivative for the given time
  1132. ====================
  1133. */
  1134. template< class type >
  1135. ID_INLINE type idCurve_NaturalCubicSpline<type>::GetCurrentSecondDerivative( const float time ) const {
  1136.     float clampedTime = ClampedTime( time );
  1137.     int i = IndexForTime( clampedTime );
  1138.     float s = time - TimeForIndex( i );
  1139.     Setup();
  1140.     return ( 2.0f * c[i] + 6.0f * s * d[i] );
  1141. }
  1142.  
  1143. /*
  1144. ====================
  1145. idCurve_NaturalCubicSpline::Setup
  1146. ====================
  1147. */
  1148. template< class type >
  1149. ID_INLINE void idCurve_NaturalCubicSpline<type>::Setup( void ) const {
  1150.     if ( changed ) {
  1151.         switch( boundaryType ) {
  1152.             case BT_FREE:        SetupFree(); break;
  1153.             case BT_CLAMPED:    SetupClamped(); break;
  1154.             case BT_CLOSED:        SetupClosed(); break;
  1155.         }
  1156.         changed = false;
  1157.     }
  1158. }
  1159.  
  1160. /*
  1161. ====================
  1162. idCurve_NaturalCubicSpline::SetupFree
  1163. ====================
  1164. */
  1165. template< class type >
  1166. ID_INLINE void idCurve_NaturalCubicSpline<type>::SetupFree( void ) const {
  1167.     int i;
  1168.     float inv;
  1169.     float *d0, *d1, *beta, *gamma;
  1170.     type *alpha, *delta;
  1171.  
  1172.     d0 = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1173.     d1 = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1174.     alpha = (type *) _alloca16( ( values.Num() - 1 ) * sizeof( type ) );
  1175.     beta = (float *) _alloca16( values.Num() * sizeof( float ) );
  1176.     gamma = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1177.     delta = (type *) _alloca16( values.Num() * sizeof( type ) );
  1178.  
  1179.     for ( i = 0; i < values.Num() - 1; i++ ) {
  1180.         d0[i] = times[i+1] - times[i];
  1181.     }
  1182.  
  1183.     for ( i = 1; i < values.Num() - 1; i++ ) {
  1184.         d1[i] = times[i+1] - times[i-1];
  1185.     }
  1186.  
  1187.     for ( i = 1; i < values.Num() - 1; i++ ) {
  1188.         type sum = 3.0f * ( d0[i-1] * values[i+1] - d1[i] * values[i] + d0[i] * values[i-1] );
  1189.         inv = 1.0f / ( d0[i-1] * d0[i] );
  1190.         alpha[i] = inv * sum;
  1191.     }
  1192.  
  1193.     beta[0] = 1.0f;
  1194.     gamma[0] = 0.0f;
  1195.     delta[0] = values[0] - values[0];
  1196.  
  1197.     for ( i = 1; i < values.Num() - 1; i++ ) {
  1198.         beta[i] = 2.0f * d1[i] - d0[i-1] * gamma[i-1];
  1199.         inv = 1.0f / beta[i];
  1200.         gamma[i] = inv * d0[i];
  1201.         delta[i] = inv * ( alpha[i] - d0[i-1] * delta[i-1] );
  1202.     }
  1203.     beta[values.Num() - 1] = 1.0f;
  1204.     delta[values.Num() - 1] = values[0] - values[0];
  1205.  
  1206.     b.AssureSize( values.Num() );
  1207.     c.AssureSize( values.Num() );
  1208.     d.AssureSize( values.Num() );
  1209.  
  1210.     c[values.Num() - 1] = values[0] - values[0];
  1211.  
  1212.     for ( i = values.Num() - 2; i >= 0; i-- ) {
  1213.         c[i] = delta[i] - gamma[i] * c[i+1];
  1214.         inv = 1.0f / d0[i];
  1215.         b[i] = inv * ( values[i+1] - values[i] ) - ( 1.0f / 3.0f ) * d0[i] * ( c[i+1] + 2.0f * c[i] );
  1216.         d[i] = ( 1.0f / 3.0f ) * inv * ( c[i+1] - c[i] );
  1217.     }
  1218. }
  1219.  
  1220. /*
  1221. ====================
  1222. idCurve_NaturalCubicSpline::SetupClamped
  1223. ====================
  1224. */
  1225. template< class type >
  1226. ID_INLINE void idCurve_NaturalCubicSpline<type>::SetupClamped( void ) const {
  1227.     int i;
  1228.     float inv;
  1229.     float *d0, *d1, *beta, *gamma;
  1230.     type *alpha, *delta;
  1231.  
  1232.     d0 = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1233.     d1 = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1234.     alpha = (type *) _alloca16( ( values.Num() - 1 ) * sizeof( type ) );
  1235.     beta = (float *) _alloca16( values.Num() * sizeof( float ) );
  1236.     gamma = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1237.     delta = (type *) _alloca16( values.Num() * sizeof( type ) );
  1238.  
  1239.     for ( i = 0; i < values.Num() - 1; i++ ) {
  1240.         d0[i] = times[i+1] - times[i];
  1241.     }
  1242.  
  1243.     for ( i = 1; i < values.Num() - 1; i++ ) {
  1244.         d1[i] = times[i+1] - times[i-1];
  1245.     }
  1246.  
  1247.     inv = 1.0f / d0[0];
  1248.     alpha[0] = 3.0f * ( inv - 1.0f ) * ( values[1] - values[0] );
  1249.     inv = 1.0f / d0[values.Num() - 2];
  1250.     alpha[values.Num() - 1] = 3.0f * ( 1.0f - inv ) * ( values[values.Num() - 1] - values[values.Num() - 2] );
  1251.  
  1252.     for ( i = 1; i < values.Num() - 1; i++ ) {
  1253.         type sum = 3.0f * ( d0[i-1] * values[i+1] - d1[i] * values[i] + d0[i] * values[i-1] );
  1254.         inv = 1.0f / ( d0[i-1] * d0[i] );
  1255.         alpha[i] = inv * sum;
  1256.     }
  1257.  
  1258.     beta[0] = 2.0f * d0[0];
  1259.     gamma[0] = 0.5f;
  1260.     inv = 1.0f / beta[0];
  1261.     delta[0] = inv * alpha[0];
  1262.  
  1263.     for ( i = 1; i < values.Num() - 1; i++ ) {
  1264.         beta[i] = 2.0f * d1[i] - d0[i-1] * gamma[i-1];
  1265.         inv = 1.0f / beta[i];
  1266.         gamma[i] = inv * d0[i];
  1267.         delta[i] = inv * ( alpha[i] - d0[i-1] * delta[i-1] );
  1268.     }
  1269.  
  1270.     beta[values.Num() - 1] = d0[values.Num() - 2] * ( 2.0f - gamma[values.Num() - 2] );
  1271.     inv = 1.0f / beta[values.Num() - 1];
  1272.     delta[values.Num() - 1] = inv * ( alpha[values.Num() - 1] - d0[values.Num() - 2] * delta[values.Num() - 2] );
  1273.  
  1274.     b.AssureSize( values.Num() );
  1275.     c.AssureSize( values.Num() );
  1276.     d.AssureSize( values.Num() );
  1277.  
  1278.     c[values.Num() - 1] = delta[values.Num() - 1];
  1279.  
  1280.     for ( i = values.Num() - 2; i >= 0; i-- ) {
  1281.         c[i] = delta[i] - gamma[i] * c[i+1];
  1282.         inv = 1.0f / d0[i];
  1283.         b[i] = inv * ( values[i+1] - values[i] ) - ( 1.0f / 3.0f ) * d0[i]* ( c[i+1] + 2.0f * c[i] );
  1284.         d[i] = ( 1.0f / 3.0f ) * inv * ( c[i+1] - c[i] );
  1285.     }
  1286. }
  1287.  
  1288. /*
  1289. ====================
  1290. idCurve_NaturalCubicSpline::SetupClosed
  1291. ====================
  1292. */
  1293. template< class type >
  1294. ID_INLINE void idCurve_NaturalCubicSpline<type>::SetupClosed( void ) const {
  1295.     int i, j;
  1296.     float c0, c1;
  1297.     float *d0;
  1298.     idMatX mat;
  1299.     idVecX x;
  1300.  
  1301.     d0 = (float *) _alloca16( ( values.Num() - 1 ) * sizeof( float ) );
  1302.     x.SetData( values.Num(), VECX_ALLOCA( values.Num() ) );
  1303.     mat.SetData( values.Num(), values.Num(), MATX_ALLOCA( values.Num() * values.Num() ) );
  1304.  
  1305.     b.AssureSize( values.Num() );
  1306.     c.AssureSize( values.Num() );
  1307.     d.AssureSize( values.Num() );
  1308.  
  1309.     for ( i = 0; i < values.Num() - 1; i++ ) {
  1310.         d0[i] = times[i+1] - times[i];
  1311.     }
  1312.  
  1313.     // matrix of system
  1314.     mat[0][0] = 1.0f;
  1315.     mat[0][values.Num() - 1] = -1.0f;
  1316.     for ( i = 1; i <= values.Num() - 2; i++ ) {
  1317.         mat[i][i-1] = d0[i-1];
  1318.         mat[i][i  ] = 2.0f * ( d0[i-1] + d0[i] );
  1319.         mat[i][i+1] = d0[i];
  1320.     }
  1321.     mat[values.Num() - 1][values.Num() - 2] = d0[values.Num() - 2];
  1322.     mat[values.Num() - 1][0] = 2.0f * ( d0[values.Num() - 2] + d0[0] );
  1323.     mat[values.Num() - 1][1] = d0[0];
  1324.  
  1325.     // right-hand side
  1326.     c[0].Zero();
  1327.     for ( i = 1; i <= values.Num() - 2; i++ ) {
  1328.         c0 = 1.0f / d0[i];
  1329.         c1 = 1.0f / d0[i-1];
  1330.         c[i] = 3.0f * ( c0 * ( values[i + 1] - values[i] ) - c1 * ( values[i] - values[i - 1] ) );
  1331.     }
  1332.     c0 = 1.0f / d0[0];
  1333.     c1 = 1.0f / d0[values.Num() - 2];
  1334.     c[values.Num() - 1] = 3.0f * ( c0 * ( values[1] - values[0] ) - c1 * ( values[0] - values[values.Num() - 2] ) );
  1335.  
  1336.     // solve system for each dimension
  1337.     mat.LU_Factor( NULL );
  1338.     for ( i = 0; i < values[0].GetDimension(); i++ ) {
  1339.         for ( j = 0; j < values.Num(); j++ ) {
  1340.             x[j] = c[j][i];
  1341.         }
  1342.         mat.LU_Solve( x, x, NULL );
  1343.         for ( j = 0; j < values.Num(); j++ ) {
  1344.             c[j][i] = x[j];
  1345.         }
  1346.     }
  1347.  
  1348.     for ( i = 0; i < values.Num() - 1; i++ ) {
  1349.         c0 = 1.0f / d0[i];
  1350.         b[i] = c0 * ( values[i + 1] - values[i] ) - ( 1.0f / 3.0f ) * ( c[i+1] + 2.0f * c[i] ) * d0[i];
  1351.         d[i] = ( 1.0f / 3.0f ) * c0 * ( c[i + 1] - c[i] );
  1352.     }
  1353. }
  1354.  
  1355.  
  1356. /*
  1357. ===============================================================================
  1358.  
  1359.     Uniform Cubic Interpolating Spline template.
  1360.     The curve goes through all the knots.
  1361.  
  1362. ===============================================================================
  1363. */
  1364.  
  1365. template< class type >
  1366. class idCurve_CatmullRomSpline : public idCurve_Spline<type> {
  1367. public:
  1368.                         idCurve_CatmullRomSpline( void );
  1369.  
  1370.     virtual type        GetCurrentValue( const float time ) const;
  1371.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  1372.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  1373.  
  1374. protected:
  1375.     void                Basis( const int index, const float t, float *bvals ) const;
  1376.     void                BasisFirstDerivative( const int index, const float t, float *bvals ) const;
  1377.     void                BasisSecondDerivative( const int index, const float t, float *bvals ) const;
  1378. };
  1379.  
  1380. /*
  1381. ====================
  1382. idCurve_CatmullRomSpline::idCurve_CatmullRomSpline
  1383. ====================
  1384. */
  1385. template< class type >
  1386. ID_INLINE idCurve_CatmullRomSpline<type>::idCurve_CatmullRomSpline( void ) {
  1387. }
  1388.  
  1389. /*
  1390. ====================
  1391. idCurve_CatmullRomSpline::GetCurrentValue
  1392.  
  1393.   get the value for the given time
  1394. ====================
  1395. */
  1396. template< class type >
  1397. ID_INLINE type idCurve_CatmullRomSpline<type>::GetCurrentValue( const float time ) const {
  1398.     int i, j, k;
  1399.     float bvals[4], clampedTime;
  1400.     type v;
  1401.  
  1402.     if ( times.Num() == 1 ) {
  1403.         return values[0];
  1404.     }
  1405.  
  1406.     clampedTime = ClampedTime( time );
  1407.     i = IndexForTime( clampedTime );
  1408.     Basis( i-1, clampedTime, bvals );
  1409.     v = values[0] - values[0];
  1410.     for ( j = 0; j < 4; j++ ) {
  1411.         k = i + j - 2;
  1412.         v += bvals[j] * ValueForIndex( k );
  1413.     }
  1414.     return v;
  1415. }
  1416.  
  1417. /*
  1418. ====================
  1419. idCurve_CatmullRomSpline::GetCurrentFirstDerivative
  1420.  
  1421.   get the first derivative for the given time
  1422. ====================
  1423. */
  1424. template< class type >
  1425. ID_INLINE type idCurve_CatmullRomSpline<type>::GetCurrentFirstDerivative( const float time ) const {
  1426.     int i, j, k;
  1427.     float bvals[4], d, clampedTime;
  1428.     type v;
  1429.  
  1430.     if ( times.Num() == 1 ) {
  1431.         return ( values[0] - values[0] );
  1432.     }
  1433.  
  1434.     clampedTime = ClampedTime( time );
  1435.     i = IndexForTime( clampedTime );
  1436.     BasisFirstDerivative( i-1, clampedTime, bvals );
  1437.     v = values[0] - values[0];
  1438.     for ( j = 0; j < 4; j++ ) {
  1439.         k = i + j - 2;
  1440.         v += bvals[j] * ValueForIndex( k );
  1441.     }
  1442.     d = ( TimeForIndex( i ) - TimeForIndex( i-1 ) );
  1443.     return v / d;
  1444. }
  1445.  
  1446. /*
  1447. ====================
  1448. idCurve_CatmullRomSpline::GetCurrentSecondDerivative
  1449.  
  1450.   get the second derivative for the given time
  1451. ====================
  1452. */
  1453. template< class type >
  1454. ID_INLINE type idCurve_CatmullRomSpline<type>::GetCurrentSecondDerivative( const float time ) const {
  1455.     int i, j, k;
  1456.     float bvals[4], d, clampedTime;
  1457.     type v;
  1458.  
  1459.     if ( times.Num() == 1 ) {
  1460.         return ( values[0] - values[0] );
  1461.     }
  1462.  
  1463.     clampedTime = ClampedTime( time );
  1464.     i = IndexForTime( clampedTime );
  1465.     BasisSecondDerivative( i-1, clampedTime, bvals );
  1466.     v = values[0] - values[0];
  1467.     for ( j = 0; j < 4; j++ ) {
  1468.         k = i + j - 2;
  1469.         v += bvals[j] * ValueForIndex( k );
  1470.     }
  1471.     d = ( TimeForIndex( i ) - TimeForIndex( i-1 ) );
  1472.     return v / ( d * d );
  1473. }
  1474.  
  1475. /*
  1476. ====================
  1477. idCurve_CatmullRomSpline::Basis
  1478.  
  1479.   spline basis functions
  1480. ====================
  1481. */
  1482. template< class type >
  1483. ID_INLINE void idCurve_CatmullRomSpline<type>::Basis( const int index, const float t, float *bvals ) const {
  1484.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  1485.     bvals[0] = ( ( -s + 2.0f ) * s - 1.0f ) * s * 0.5f;                // -0.5f s * s * s + s * s - 0.5f * s
  1486.     bvals[1] = ( ( ( 3.0f * s - 5.0f ) * s ) * s + 2.0f ) * 0.5f;    // 1.5f * s * s * s - 2.5f * s * s + 1.0f
  1487.     bvals[2] = ( ( -3.0f * s + 4.0f ) * s + 1.0f ) * s * 0.5f;        // -1.5f * s * s * s - 2.0f * s * s + 0.5f s
  1488.     bvals[3] = ( ( s - 1.0f ) * s * s ) * 0.5f;                        // 0.5f * s * s * s - 0.5f * s * s
  1489. }
  1490.  
  1491. /*
  1492. ====================
  1493. idCurve_CatmullRomSpline::BasisFirstDerivative
  1494.  
  1495.   first derivative of spline basis functions
  1496. ====================
  1497. */
  1498. template< class type >
  1499. ID_INLINE void idCurve_CatmullRomSpline<type>::BasisFirstDerivative( const int index, const float t, float *bvals ) const {
  1500.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  1501.     bvals[0] = ( -1.5f * s + 2.0f ) * s - 0.5f;                        // -1.5f * s * s + 2.0f * s - 0.5f
  1502.     bvals[1] = ( 4.5f * s - 5.0f ) * s;                                // 4.5f * s * s - 5.0f * s
  1503.     bvals[2] = ( -4.5 * s + 4.0f ) * s + 0.5f;                        // -4.5 * s * s + 4.0f * s + 0.5f
  1504.     bvals[3] = 1.5f * s * s - s;                                    // 1.5f * s * s - s
  1505. }
  1506.  
  1507. /*
  1508. ====================
  1509. idCurve_CatmullRomSpline::BasisSecondDerivative
  1510.  
  1511.   second derivative of spline basis functions
  1512. ====================
  1513. */
  1514. template< class type >
  1515. ID_INLINE void idCurve_CatmullRomSpline<type>::BasisSecondDerivative( const int index, const float t, float *bvals ) const {
  1516.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  1517.     bvals[0] = -3.0f * s + 2.0f;
  1518.     bvals[1] = 9.0f * s - 5.0f;
  1519.     bvals[2] = -9.0f * s + 4.0f;
  1520.     bvals[3] = 3.0f * s - 1.0f;
  1521. }
  1522.  
  1523.  
  1524. /*
  1525. ===============================================================================
  1526.  
  1527.     Cubic Interpolating Spline template.
  1528.     The curve goes through all the knots.
  1529.     The curve becomes the Catmull-Rom spline if the tension,
  1530.     continuity and bias are all set to zero.
  1531.  
  1532. ===============================================================================
  1533. */
  1534.  
  1535. template< class type >
  1536. class idCurve_KochanekBartelsSpline : public idCurve_Spline<type> {
  1537. public:
  1538.                         idCurve_KochanekBartelsSpline( void );
  1539.  
  1540.     virtual int            AddValue( const float time, const type &value );
  1541.     virtual int            AddValue( const float time, const type &value, const float tension, const float continuity, const float bias );
  1542.     virtual void        RemoveIndex( const int index ) { values.RemoveIndex(index); times.RemoveIndex(index); tension.RemoveIndex(index); continuity.RemoveIndex(index); bias.RemoveIndex(index); }
  1543.     virtual void        Clear( void ) { values.Clear(); times.Clear(); tension.Clear(); continuity.Clear(); bias.Clear(); currentIndex = -1; }
  1544.  
  1545.     virtual type        GetCurrentValue( const float time ) const;
  1546.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  1547.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  1548.  
  1549. protected:
  1550.     idList<float>        tension;
  1551.     idList<float>        continuity;
  1552.     idList<float>        bias;
  1553.  
  1554.     void                TangentsForIndex( const int index, type &t0, type &t1 ) const;
  1555.  
  1556.     void                Basis( const int index, const float t, float *bvals ) const;
  1557.     void                BasisFirstDerivative( const int index, const float t, float *bvals ) const;
  1558.     void                BasisSecondDerivative( const int index, const float t, float *bvals ) const;
  1559. };
  1560.  
  1561. /*
  1562. ====================
  1563. idCurve_KochanekBartelsSpline::idCurve_KochanekBartelsSpline
  1564. ====================
  1565. */
  1566. template< class type >
  1567. ID_INLINE idCurve_KochanekBartelsSpline<type>::idCurve_KochanekBartelsSpline( void ) {
  1568. }
  1569.  
  1570. /*
  1571. ====================
  1572. idCurve_KochanekBartelsSpline::AddValue
  1573.  
  1574.   add a timed/value pair to the spline
  1575.   returns the index to the inserted pair
  1576. ====================
  1577. */
  1578. template< class type >
  1579. ID_INLINE int idCurve_KochanekBartelsSpline<type>::AddValue( const float time, const type &value ) {
  1580.     int i;
  1581.  
  1582.     i = IndexForTime( time );
  1583.     times.Insert( time, i );
  1584.     values.Insert( value, i );
  1585.     tension.Insert( 0.0f, i );
  1586.     continuity.Insert( 0.0f, i );
  1587.     bias.Insert( 0.0f, i );
  1588.     return i;
  1589. }
  1590.  
  1591. /*
  1592. ====================
  1593. idCurve_KochanekBartelsSpline::AddValue
  1594.  
  1595.   add a timed/value pair to the spline
  1596.   returns the index to the inserted pair
  1597. ====================
  1598. */
  1599. template< class type >
  1600. ID_INLINE int idCurve_KochanekBartelsSpline<type>::AddValue( const float time, const type &value, const float tension, const float continuity, const float bias ) {
  1601.     int i;
  1602.  
  1603.     i = IndexForTime( time );
  1604.     this->times.Insert( time, i );
  1605.     this->values.Insert( value, i );
  1606.     this->tension.Insert( tension, i );
  1607.     this->continuity.Insert( continuity, i );
  1608.     this->bias.Insert( bias, i );
  1609.     return i;
  1610. }
  1611.  
  1612. /*
  1613. ====================
  1614. idCurve_KochanekBartelsSpline::GetCurrentValue
  1615.  
  1616.   get the value for the given time
  1617. ====================
  1618. */
  1619. template< class type >
  1620. ID_INLINE type idCurve_KochanekBartelsSpline<type>::GetCurrentValue( const float time ) const {
  1621.     int i;
  1622.     float bvals[4], clampedTime;
  1623.     type v, t0, t1;
  1624.  
  1625.     if ( times.Num() == 1 ) {
  1626.         return values[0];
  1627.     }
  1628.  
  1629.     clampedTime = ClampedTime( time );
  1630.     i = IndexForTime( clampedTime );
  1631.     TangentsForIndex( i - 1, t0, t1 );
  1632.     Basis( i - 1, clampedTime, bvals );
  1633.     v = bvals[0] * ValueForIndex( i - 1 );
  1634.     v += bvals[1] * ValueForIndex( i );
  1635.     v += bvals[2] * t0;
  1636.     v += bvals[3] * t1;
  1637.     return v;
  1638. }
  1639.  
  1640. /*
  1641. ====================
  1642. idCurve_KochanekBartelsSpline::GetCurrentFirstDerivative
  1643.  
  1644.   get the first derivative for the given time
  1645. ====================
  1646. */
  1647. template< class type >
  1648. ID_INLINE type idCurve_KochanekBartelsSpline<type>::GetCurrentFirstDerivative( const float time ) const {
  1649.     int i;
  1650.     float bvals[4], d, clampedTime;
  1651.     type v, t0, t1;
  1652.  
  1653.     if ( times.Num() == 1 ) {
  1654.         return ( values[0] - values[0] );
  1655.     }
  1656.  
  1657.     clampedTime = ClampedTime( time );
  1658.     i = IndexForTime( clampedTime );
  1659.     TangentsForIndex( i - 1, t0, t1 );
  1660.     BasisFirstDerivative( i - 1, clampedTime, bvals );
  1661.     v = bvals[0] * ValueForIndex( i - 1 );
  1662.     v += bvals[1] * ValueForIndex( i );
  1663.     v += bvals[2] * t0;
  1664.     v += bvals[3] * t1;
  1665.     d = ( TimeForIndex( i ) - TimeForIndex( i-1 ) );
  1666.     return v / d;
  1667. }
  1668.  
  1669. /*
  1670. ====================
  1671. idCurve_KochanekBartelsSpline::GetCurrentSecondDerivative
  1672.  
  1673.   get the second derivative for the given time
  1674. ====================
  1675. */
  1676. template< class type >
  1677. ID_INLINE type idCurve_KochanekBartelsSpline<type>::GetCurrentSecondDerivative( const float time ) const {
  1678.     int i;
  1679.     float bvals[4], d, clampedTime;
  1680.     type v, t0, t1;
  1681.  
  1682.     if ( times.Num() == 1 ) {
  1683.         return ( values[0] - values[0] );
  1684.     }
  1685.  
  1686.     clampedTime = ClampedTime( time );
  1687.     i = IndexForTime( clampedTime );
  1688.     TangentsForIndex( i - 1, t0, t1 );
  1689.     BasisSecondDerivative( i - 1, clampedTime, bvals );
  1690.     v = bvals[0] * ValueForIndex( i - 1 );
  1691.     v += bvals[1] * ValueForIndex( i );
  1692.     v += bvals[2] * t0;
  1693.     v += bvals[3] * t1;
  1694.     d = ( TimeForIndex( i ) - TimeForIndex( i-1 ) );
  1695.     return v / ( d * d );
  1696. }
  1697.  
  1698. /*
  1699. ====================
  1700. idCurve_KochanekBartelsSpline::TangentsForIndex
  1701. ====================
  1702. */
  1703. template< class type >
  1704. ID_INLINE void idCurve_KochanekBartelsSpline<type>::TangentsForIndex( const int index, type &t0, type &t1 ) const {
  1705.     float dt, omt, omc, opc, omb, opb, adj, s0, s1;
  1706.     type delta;
  1707.  
  1708.     delta = ValueForIndex( index + 1 ) - ValueForIndex( index );
  1709.     dt = TimeForIndex( index + 1 ) - TimeForIndex( index );
  1710.  
  1711.     omt = 1.0f - tension[index];
  1712.     omc = 1.0f - continuity[index];
  1713.     opc = 1.0f + continuity[index];
  1714.     omb = 1.0f - bias[index];
  1715.     opb = 1.0f + bias[index];
  1716.     adj = 2.0f * dt / ( TimeForIndex( index + 1 ) - TimeForIndex( index - 1 ) );
  1717.     s0 = 0.5f * adj * omt * opc * opb;
  1718.     s1 = 0.5f * adj * omt * omc * omb;
  1719.  
  1720.     // outgoing tangent at first point
  1721.     t0 = s1 * delta + s0 * ( ValueForIndex( index ) - ValueForIndex( index - 1 ) );
  1722.  
  1723.     omt = 1.0f - tension[index + 1];
  1724.     omc = 1.0f - continuity[index + 1];
  1725.     opc = 1.0f + continuity[index + 1];
  1726.     omb = 1.0f - bias[index + 1];
  1727.     opb = 1.0f + bias[index + 1];
  1728.     adj = 2.0f * dt / ( TimeForIndex( index + 2 ) - TimeForIndex( index ) );
  1729.     s0 = 0.5f * adj * omt * omc * opb;
  1730.     s1 = 0.5f * adj * omt * opc * omb;
  1731.  
  1732.     // incoming tangent at second point
  1733.     t1 = s1 * ( ValueForIndex( index + 2 ) - ValueForIndex( index + 1 ) ) + s0 * delta;
  1734. }
  1735.  
  1736. /*
  1737. ====================
  1738. idCurve_KochanekBartelsSpline::Basis
  1739.  
  1740.   spline basis functions
  1741. ====================
  1742. */
  1743. template< class type >
  1744. ID_INLINE void idCurve_KochanekBartelsSpline<type>::Basis( const int index, const float t, float *bvals ) const {
  1745.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  1746.     bvals[0] = ( ( 2.0f * s - 3.0f ) * s ) * s + 1.0f;                // 2.0f * s * s * s - 3.0f * s * s + 1.0f
  1747.     bvals[1] = ( ( -2.0f * s + 3.0f ) * s ) * s;                    // -2.0f * s * s * s + 3.0f * s * s
  1748.     bvals[2] = ( ( s - 2.0f ) * s ) * s + s;                        // s * s * s - 2.0f * s * s + s
  1749.     bvals[3] = ( ( s - 1.0f ) * s ) * s;                            // s * s * s - s * s
  1750. }
  1751.  
  1752. /*
  1753. ====================
  1754. idCurve_KochanekBartelsSpline::BasisFirstDerivative
  1755.  
  1756.   first derivative of spline basis functions
  1757. ====================
  1758. */
  1759. template< class type >
  1760. ID_INLINE void idCurve_KochanekBartelsSpline<type>::BasisFirstDerivative( const int index, const float t, float *bvals ) const {
  1761.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  1762.     bvals[0] = ( 6.0f * s - 6.0f ) * s;                                // 6.0f * s * s - 6.0f * s
  1763.     bvals[1] = ( -6.0f * s + 6.0f ) * s;                            // -6.0f * s * s + 6.0f * s
  1764.     bvals[2] = ( 3.0f * s - 4.0f ) * s + 1.0f;                        // 3.0f * s * s - 4.0f * s + 1.0f
  1765.     bvals[3] = ( 3.0f * s - 2.0f ) * s;                                // 3.0f * s * s - 2.0f * s
  1766. }
  1767.  
  1768. /*
  1769. ====================
  1770. idCurve_KochanekBartelsSpline::BasisSecondDerivative
  1771.  
  1772.   second derivative of spline basis functions
  1773. ====================
  1774. */
  1775. template< class type >
  1776. ID_INLINE void idCurve_KochanekBartelsSpline<type>::BasisSecondDerivative( const int index, const float t, float *bvals ) const {
  1777.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  1778.     bvals[0] = 12.0f * s - 6.0f;
  1779.     bvals[1] = -12.0f * s + 6.0f;
  1780.     bvals[2] = 6.0f * s - 4.0f;
  1781.     bvals[3] = 6.0f * s - 2.0f;
  1782. }
  1783.  
  1784.  
  1785. /*
  1786. ===============================================================================
  1787.  
  1788.     B-Spline base template. Uses recursive definition and is slow.
  1789.     Use idCurve_UniformCubicBSpline or idCurve_NonUniformBSpline instead.
  1790.  
  1791. ===============================================================================
  1792. */
  1793.  
  1794. template< class type >
  1795. class idCurve_BSpline : public idCurve_Spline<type> {
  1796. public:
  1797.                         idCurve_BSpline( void );
  1798.  
  1799.     virtual int            GetOrder( void ) const { return order; }
  1800.     virtual void        SetOrder( const int i ) { assert( i > 0 && i < 10 ); order = i; }
  1801.  
  1802.     virtual type        GetCurrentValue( const float time ) const;
  1803.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  1804.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  1805.  
  1806. protected:
  1807.     int                    order;
  1808.  
  1809.     float                Basis( const int index, const int order, const float t ) const;
  1810.     float                BasisFirstDerivative( const int index, const int order, const float t ) const;
  1811.     float                BasisSecondDerivative( const int index, const int order, const float t ) const;
  1812. };
  1813.  
  1814. /*
  1815. ====================
  1816. idCurve_BSpline::idCurve_NaturalCubicSpline
  1817. ====================
  1818. */
  1819. template< class type >
  1820. ID_INLINE idCurve_BSpline<type>::idCurve_BSpline( void ) {
  1821.     order = 4;    // default to cubic
  1822. }
  1823.  
  1824. /*
  1825. ====================
  1826. idCurve_BSpline::GetCurrentValue
  1827.  
  1828.   get the value for the given time
  1829. ====================
  1830. */
  1831. template< class type >
  1832. ID_INLINE type idCurve_BSpline<type>::GetCurrentValue( const float time ) const {
  1833.     int i, j, k;
  1834.     float clampedTime;
  1835.     type v;
  1836.  
  1837.     if ( times.Num() == 1 ) {
  1838.         return values[0];
  1839.     }
  1840.  
  1841.     clampedTime = ClampedTime( time );
  1842.     i = IndexForTime( clampedTime );
  1843.     v = values[0] - values[0];
  1844.     for ( j = 0; j < order; j++ ) {
  1845.         k = i + j - ( order >> 1 );
  1846.         v += Basis( k-2, order, clampedTime ) * ValueForIndex( k );
  1847.     }
  1848.     return v;
  1849. }
  1850.  
  1851. /*
  1852. ====================
  1853. idCurve_BSpline::GetCurrentFirstDerivative
  1854.  
  1855.   get the first derivative for the given time
  1856. ====================
  1857. */
  1858. template< class type >
  1859. ID_INLINE type idCurve_BSpline<type>::GetCurrentFirstDerivative( const float time ) const {
  1860.     int i, j, k;
  1861.     float clampedTime;
  1862.     type v;
  1863.  
  1864.     if ( times.Num() == 1 ) {
  1865.         return values[0];
  1866.     }
  1867.  
  1868.     clampedTime = ClampedTime( time );
  1869.     i = IndexForTime( clampedTime );
  1870.     v = values[0] - values[0];
  1871.     for ( j = 0; j < order; j++ ) {
  1872.         k = i + j - ( order >> 1 );
  1873.         v += BasisFirstDerivative( k-2, order, clampedTime ) * ValueForIndex( k );
  1874.     }
  1875.     return v;
  1876. }
  1877.  
  1878. /*
  1879. ====================
  1880. idCurve_BSpline::GetCurrentSecondDerivative
  1881.  
  1882.   get the second derivative for the given time
  1883. ====================
  1884. */
  1885. template< class type >
  1886. ID_INLINE type idCurve_BSpline<type>::GetCurrentSecondDerivative( const float time ) const {
  1887.     int i, j, k;
  1888.     float clampedTime;
  1889.     type v;
  1890.  
  1891.     if ( times.Num() == 1 ) {
  1892.         return values[0];
  1893.     }
  1894.  
  1895.     clampedTime = ClampedTime( time );
  1896.     i = IndexForTime( clampedTime );
  1897.     v = values[0] - values[0];
  1898.     for ( j = 0; j < order; j++ ) {
  1899.         k = i + j - ( order >> 1 );
  1900.         v += BasisSecondDerivative( k-2, order, clampedTime ) * ValueForIndex( k );
  1901.     }
  1902.     return v;
  1903. }
  1904.  
  1905. /*
  1906. ====================
  1907. idCurve_BSpline::Basis
  1908.  
  1909.   spline basis function
  1910. ====================
  1911. */
  1912. template< class type >
  1913. ID_INLINE float idCurve_BSpline<type>::Basis( const int index, const int order, const float t ) const {
  1914.     if ( order <= 1 ) {
  1915.         if ( TimeForIndex( index ) < t && t <= TimeForIndex( index + 1 ) ) {
  1916.             return 1.0f;
  1917.         } else {
  1918.             return 0.0f;
  1919.         }
  1920.     } else {
  1921.         float sum = 0.0f;
  1922.         float d1 = TimeForIndex( index+order-1 ) - TimeForIndex( index );
  1923.         if ( d1 != 0.0f ) {
  1924.             sum += (float) ( t - TimeForIndex( index ) ) * Basis( index, order-1, t ) / d1;
  1925.         }
  1926.  
  1927.         float d2 = TimeForIndex( index+order ) - TimeForIndex( index+1 );
  1928.         if ( d2 != 0.0f ) {
  1929.             sum += (float) ( TimeForIndex( index+order ) - t ) * Basis( index+1, order-1, t ) / d2;
  1930.         }
  1931.         return sum;
  1932.     }
  1933. }
  1934.  
  1935. /*
  1936. ====================
  1937. idCurve_BSpline::BasisFirstDerivative
  1938.  
  1939.   first derivative of spline basis function
  1940. ====================
  1941. */
  1942. template< class type >
  1943. ID_INLINE float idCurve_BSpline<type>::BasisFirstDerivative( const int index, const int order, const float t ) const {
  1944.     return ( Basis( index, order-1, t ) - Basis( index+1, order-1, t ) ) *
  1945.             (float) ( order - 1 ) / ( TimeForIndex( index + ( order - 1 ) - 2 ) - TimeForIndex( index - 2 ) );
  1946. }
  1947.  
  1948. /*
  1949. ====================
  1950. idCurve_BSpline::BasisSecondDerivative
  1951.  
  1952.   second derivative of spline basis function
  1953. ====================
  1954. */
  1955. template< class type >
  1956. ID_INLINE float idCurve_BSpline<type>::BasisSecondDerivative( const int index, const int order, const float t ) const {
  1957.     return ( BasisFirstDerivative( index, order-1, t ) - BasisFirstDerivative( index+1, order-1, t ) ) *
  1958.             (float) ( order - 1 ) / ( TimeForIndex( index + ( order - 1 ) - 2 ) - TimeForIndex( index - 2 ) );
  1959. }
  1960.  
  1961.  
  1962. /*
  1963. ===============================================================================
  1964.  
  1965.     Uniform Non-Rational Cubic B-Spline template.
  1966.  
  1967. ===============================================================================
  1968. */
  1969.  
  1970. template< class type >
  1971. class idCurve_UniformCubicBSpline : public idCurve_BSpline<type> {
  1972. public:
  1973.                         idCurve_UniformCubicBSpline( void );
  1974.  
  1975.     virtual type        GetCurrentValue( const float time ) const;
  1976.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  1977.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  1978.  
  1979. protected:
  1980.     void                Basis( const int index, const float t, float *bvals ) const;
  1981.     void                BasisFirstDerivative( const int index, const float t, float *bvals ) const;
  1982.     void                BasisSecondDerivative( const int index, const float t, float *bvals ) const;
  1983. };
  1984.  
  1985. /*
  1986. ====================
  1987. idCurve_UniformCubicBSpline::idCurve_UniformCubicBSpline
  1988. ====================
  1989. */
  1990. template< class type >
  1991. ID_INLINE idCurve_UniformCubicBSpline<type>::idCurve_UniformCubicBSpline( void ) {
  1992.     order = 4;    // always cubic
  1993. }
  1994.  
  1995. /*
  1996. ====================
  1997. idCurve_UniformCubicBSpline::GetCurrentValue
  1998.  
  1999.   get the value for the given time
  2000. ====================
  2001. */
  2002. template< class type >
  2003. ID_INLINE type idCurve_UniformCubicBSpline<type>::GetCurrentValue( const float time ) const {
  2004.     int i, j, k;
  2005.     float bvals[4], clampedTime;
  2006.     type v;
  2007.  
  2008.     if ( times.Num() == 1 ) {
  2009.         return values[0];
  2010.     }
  2011.  
  2012.     clampedTime = ClampedTime( time );
  2013.     i = IndexForTime( clampedTime );
  2014.     Basis( i-1, clampedTime, bvals );
  2015.     v = values[0] - values[0];
  2016.     for ( j = 0; j < 4; j++ ) {
  2017.         k = i + j - 2;
  2018.         v += bvals[j] * ValueForIndex( k );
  2019.     }
  2020.     return v;
  2021. }
  2022.  
  2023. /*
  2024. ====================
  2025. idCurve_UniformCubicBSpline::GetCurrentFirstDerivative
  2026.  
  2027.   get the first derivative for the given time
  2028. ====================
  2029. */
  2030. template< class type >
  2031. ID_INLINE type idCurve_UniformCubicBSpline<type>::GetCurrentFirstDerivative( const float time ) const {
  2032.     int i, j, k;
  2033.     float bvals[4], d, clampedTime;
  2034.     type v;
  2035.  
  2036.     if ( times.Num() == 1 ) {
  2037.         return ( values[0] - values[0] );
  2038.     }
  2039.  
  2040.     clampedTime = ClampedTime( time );
  2041.     i = IndexForTime( clampedTime );
  2042.     BasisFirstDerivative( i-1, clampedTime, bvals );
  2043.     v = values[0] - values[0];
  2044.     for ( j = 0; j < 4; j++ ) {
  2045.         k = i + j - 2;
  2046.         v += bvals[j] * ValueForIndex( k );
  2047.     }
  2048.     d = ( TimeForIndex( i ) - TimeForIndex( i-1 ) );
  2049.     return v / d;
  2050. }
  2051.  
  2052. /*
  2053. ====================
  2054. idCurve_UniformCubicBSpline::GetCurrentSecondDerivative
  2055.  
  2056.   get the second derivative for the given time
  2057. ====================
  2058. */
  2059. template< class type >
  2060. ID_INLINE type idCurve_UniformCubicBSpline<type>::GetCurrentSecondDerivative( const float time ) const {
  2061.     int i, j, k;
  2062.     float bvals[4], d, clampedTime;
  2063.     type v;
  2064.  
  2065.     if ( times.Num() == 1 ) {
  2066.         return ( values[0] - values[0] );
  2067.     }
  2068.  
  2069.     clampedTime = ClampedTime( time );
  2070.     i = IndexForTime( clampedTime );
  2071.     BasisSecondDerivative( i-1, clampedTime, bvals );
  2072.     v = values[0] - values[0];
  2073.     for ( j = 0; j < 4; j++ ) {
  2074.         k = i + j - 2;
  2075.         v += bvals[j] * ValueForIndex( k );
  2076.     }
  2077.     d = ( TimeForIndex( i ) - TimeForIndex( i-1 ) );
  2078.     return v / ( d * d );
  2079. }
  2080.  
  2081. /*
  2082. ====================
  2083. idCurve_UniformCubicBSpline::Basis
  2084.  
  2085.   spline basis functions
  2086. ====================
  2087. */
  2088. template< class type >
  2089. ID_INLINE void idCurve_UniformCubicBSpline<type>::Basis( const int index, const float t, float *bvals ) const {
  2090.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  2091.     bvals[0] = ( ( ( -s + 3.0f ) * s - 3.0f ) * s + 1.0f ) * ( 1.0f / 6.0f );
  2092.     bvals[1] = ( ( ( 3.0f * s - 6.0f ) * s ) * s + 4.0f ) * ( 1.0f / 6.0f );
  2093.     bvals[2] = ( ( ( -3.0f * s + 3.0f ) * s + 3.0f ) * s + 1.0f ) * ( 1.0f / 6.0f );
  2094.     bvals[3] = ( s * s * s ) * ( 1.0f / 6.0f );
  2095. }
  2096.  
  2097. /*
  2098. ====================
  2099. idCurve_UniformCubicBSpline::BasisFirstDerivative
  2100.  
  2101.   first derivative of spline basis functions
  2102. ====================
  2103. */
  2104. template< class type >
  2105. ID_INLINE void idCurve_UniformCubicBSpline<type>::BasisFirstDerivative( const int index, const float t, float *bvals ) const {
  2106.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  2107.     bvals[0] = -0.5f * s * s + s - 0.5f;
  2108.     bvals[1] = 1.5f * s * s - 2.0f * s;
  2109.     bvals[2] = -1.5f * s * s + s + 0.5f;
  2110.     bvals[3] = 0.5f * s * s;
  2111. }
  2112.  
  2113. /*
  2114. ====================
  2115. idCurve_UniformCubicBSpline::BasisSecondDerivative
  2116.  
  2117.   second derivative of spline basis functions
  2118. ====================
  2119. */
  2120. template< class type >
  2121. ID_INLINE void idCurve_UniformCubicBSpline<type>::BasisSecondDerivative( const int index, const float t, float *bvals ) const {
  2122.     float s = (float) ( t - TimeForIndex( index ) ) / ( TimeForIndex( index+1 ) - TimeForIndex( index ) );
  2123.     bvals[0] = -s + 1.0f;
  2124.     bvals[1] = 3.0f * s - 2.0f;
  2125.     bvals[2] = -3.0f * s + 1.0f;
  2126.     bvals[3] = s;
  2127. }
  2128.  
  2129.  
  2130. /*
  2131. ===============================================================================
  2132.  
  2133.     Non-Uniform Non-Rational B-Spline (NUBS) template.
  2134.  
  2135. ===============================================================================
  2136. */
  2137.  
  2138. template< class type >
  2139. class idCurve_NonUniformBSpline : public idCurve_BSpline<type> {
  2140. public:
  2141.                         idCurve_NonUniformBSpline( void );
  2142.  
  2143.     virtual type        GetCurrentValue( const float time ) const;
  2144.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  2145.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  2146. // RAVEN BEGIN
  2147. // ddynerman: spline welding
  2148.     virtual bool        Weld( idCurve<type>* c ) const;
  2149. // RAVEN END
  2150.  
  2151. protected:
  2152.     void                Basis( const int index, const int order, const float t, float *bvals ) const;
  2153.     void                BasisFirstDerivative( const int index, const int order, const float t, float *bvals ) const;
  2154.     void                BasisSecondDerivative( const int index, const int order, const float t, float *bvals ) const;
  2155. };
  2156.  
  2157. /*
  2158. ====================
  2159. idCurve_NonUniformBSpline::idCurve_NonUniformBSpline
  2160. ====================
  2161. */
  2162. template< class type >
  2163. ID_INLINE idCurve_NonUniformBSpline<type>::idCurve_NonUniformBSpline( void ) {
  2164. }
  2165.  
  2166. /*
  2167. ====================
  2168. idCurve_NonUniformBSpline::GetCurrentValue
  2169.  
  2170.   get the value for the given time
  2171. ====================
  2172. */
  2173. template< class type >
  2174. ID_INLINE type idCurve_NonUniformBSpline<type>::GetCurrentValue( const float time ) const {
  2175.     int i, j, k;
  2176.     float clampedTime;
  2177.     type v;
  2178.     float *bvals = (float *) _alloca16( order * sizeof(float) );
  2179.  
  2180.     if ( times.Num() == 1 ) {
  2181.         return values[0];
  2182.     }
  2183.  
  2184.     clampedTime = ClampedTime( time );
  2185.     i = IndexForTime( clampedTime );
  2186.     Basis( i-1, order, clampedTime, bvals );
  2187.     v = values[0] - values[0];
  2188.     for ( j = 0; j < order; j++ ) {
  2189.         k = i + j - ( order >> 1 );
  2190.         v += bvals[j] * ValueForIndex( k );
  2191.     }
  2192.     return v;
  2193. }
  2194.  
  2195. /*
  2196. ====================
  2197. idCurve_NonUniformBSpline::GetCurrentFirstDerivative
  2198.  
  2199.   get the first derivative for the given time
  2200. ====================
  2201. */
  2202. template< class type >
  2203. ID_INLINE type idCurve_NonUniformBSpline<type>::GetCurrentFirstDerivative( const float time ) const {
  2204.     int i, j, k;
  2205.     float clampedTime;
  2206.     type v;
  2207.     float *bvals = (float *) _alloca16( order * sizeof(float) );
  2208.  
  2209.     if ( times.Num() == 1 ) {
  2210.         return ( values[0] - values[0] );
  2211.     }
  2212.  
  2213.     clampedTime = ClampedTime( time );
  2214.     i = IndexForTime( clampedTime );
  2215.     BasisFirstDerivative( i-1, order, clampedTime, bvals );
  2216.     v = values[0] - values[0];
  2217.     for ( j = 0; j < order; j++ ) {
  2218.         k = i + j - ( order >> 1 );
  2219.         v += bvals[j] * ValueForIndex( k );
  2220.     }
  2221.     return v;
  2222. }
  2223.  
  2224. /*
  2225. ====================
  2226. idCurve_NonUniformBSpline::GetCurrentSecondDerivative
  2227.  
  2228.   get the second derivative for the given time
  2229. ====================
  2230. */
  2231. template< class type >
  2232. ID_INLINE type idCurve_NonUniformBSpline<type>::GetCurrentSecondDerivative( const float time ) const {
  2233.     int i, j, k;
  2234.     float clampedTime;
  2235.     type v;
  2236.     float *bvals = (float *) _alloca16( order * sizeof(float) );
  2237.  
  2238.     if ( times.Num() == 1 ) {
  2239.         return ( values[0] - values[0] );
  2240.     }
  2241.  
  2242.     clampedTime = ClampedTime( time );
  2243.     i = IndexForTime( clampedTime );
  2244.     BasisSecondDerivative( i-1, order, clampedTime, bvals );
  2245.     v = values[0] - values[0];
  2246.     for ( j = 0; j < order; j++ ) {
  2247.         k = i + j - ( order >> 1 );
  2248.         v += bvals[j] * ValueForIndex( k );
  2249.     }
  2250.     return v;
  2251. }
  2252.  
  2253. /*
  2254. ====================
  2255. idCurve_NonUniformBSpline::Basis
  2256.  
  2257.   spline basis functions
  2258. ====================
  2259. */
  2260. template< class type >
  2261. ID_INLINE void idCurve_NonUniformBSpline<type>::Basis( const int index, const int order, const float t, float *bvals ) const {
  2262.     int r, s, i;
  2263.     float omega;
  2264.  
  2265.     bvals[order-1] = 1.0f;
  2266.     for ( r = 2; r <= order; r++ ) {
  2267.         i = index - r + 1;
  2268.         bvals[order - r] = 0.0f;
  2269.         for ( s = order - r + 1; s < order; s++ ) {
  2270.             i++;
  2271.             omega = (float) ( t - TimeForIndex( i ) ) / ( TimeForIndex( i + r - 1 ) - TimeForIndex( i ) );
  2272.             bvals[s - 1] += ( 1.0f - omega ) * bvals[s];
  2273.             bvals[s] *= omega;
  2274.         }
  2275.     }
  2276. }
  2277.  
  2278. /*
  2279. ====================
  2280. idCurve_NonUniformBSpline::BasisFirstDerivative
  2281.  
  2282.   first derivative of spline basis functions
  2283. ====================
  2284. */
  2285. template< class type >
  2286. ID_INLINE void idCurve_NonUniformBSpline<type>::BasisFirstDerivative( const int index, const int order, const float t, float *bvals ) const {
  2287.     int i;
  2288.  
  2289.     Basis( index, order-1, t, bvals+1 );
  2290.     bvals[0] = 0.0f;
  2291.     for ( i = 0; i < order-1; i++ ) {
  2292.         bvals[i] -= bvals[i+1];
  2293.         bvals[i] *= (float) ( order - 1) / ( TimeForIndex( index + i + (order-1) - 2 ) - TimeForIndex( index + i - 2 ) );
  2294.     }
  2295.     bvals[i] *= (float) ( order - 1) / ( TimeForIndex( index + i + (order-1) - 2 ) - TimeForIndex( index + i - 2 ) );
  2296. }
  2297.  
  2298. /*
  2299. ====================
  2300. idCurve_NonUniformBSpline::BasisSecondDerivative
  2301.  
  2302.   second derivative of spline basis functions
  2303. ====================
  2304. */
  2305. template< class type >
  2306. ID_INLINE void idCurve_NonUniformBSpline<type>::BasisSecondDerivative( const int index, const int order, const float t, float *bvals ) const {
  2307.     int i;
  2308.  
  2309.     BasisFirstDerivative( index, order-1, t, bvals+1 );
  2310.     bvals[0] = 0.0f;
  2311.     for ( i = 0; i < order-1; i++ ) {
  2312.         bvals[i] -= bvals[i+1];
  2313.         bvals[i] *= (float) ( order - 1) / ( TimeForIndex( index + i + (order-1) - 2 ) - TimeForIndex( index + i - 2 ) );
  2314.     }
  2315.     bvals[i] *= (float) ( order - 1) / ( TimeForIndex( index + i + (order-1) - 2 ) - TimeForIndex( index + i - 2 ) );
  2316. }
  2317.  
  2318. // RAVEN BEGIN
  2319. // ddynerman: spline welding
  2320. /*
  2321. ====================
  2322. idCurve_NonUniformBSpline::Weld
  2323.  
  2324.   Attach two B-Splines together
  2325. ====================
  2326. */
  2327. template< class type >
  2328. ID_INLINE bool idCurve_NonUniformBSpline<type>::Weld( idCurve<type>* c ) const {
  2329.     idCurve_NonUniformBSpline<type>* spline = dynamic_cast<idCurve_NonUniformBSpline<type>*>(c);
  2330.     
  2331.     if( spline == NULL ) {
  2332.         return false;
  2333.     }
  2334.  
  2335.     type refLine = values[ values.Num() - 1 ] - values[ values.Num() - 2 ];
  2336.     float length = (spline->values[ 0 ] - spline->values[ 1 ]).Length();
  2337.  
  2338.     bool valuesChanged = spline->values[ 0 ] != values[ values.Num() - 1 ];
  2339.     spline->values[ 0 ] = values[ values.Num() - 1 ];
  2340.  
  2341.     type deltaPos = ~refLine * length;
  2342.     type newValue = spline->values[ 0 ] + deltaPos;
  2343.     
  2344.     valuesChanged = (spline->values[ 1 ] != newValue) || valuesChanged;
  2345.  
  2346.     spline->values[ 1 ] = newValue;
  2347.  
  2348.     return valuesChanged;
  2349. }
  2350. // RAVEN END
  2351.  
  2352. /*
  2353. ===============================================================================
  2354.  
  2355.     Non-Uniform Rational B-Spline (NURBS) template.
  2356.  
  2357. ===============================================================================
  2358. */
  2359.  
  2360. template< class type >
  2361. class idCurve_NURBS : public idCurve_NonUniformBSpline<type> {
  2362. public:
  2363.                         idCurve_NURBS( void );
  2364.  
  2365.     virtual int            AddValue( const float time, const type &value );
  2366.     virtual int            AddValue( const float time, const type &value, const float weight );
  2367.     virtual void        RemoveIndex( const int index ) { values.RemoveIndex(index); times.RemoveIndex(index); weights.RemoveIndex(index); }
  2368.     virtual void        Clear( void ) { values.Clear(); times.Clear(); weights.Clear(); currentIndex = -1; }
  2369.  
  2370.     virtual type        GetCurrentValue( const float time ) const;
  2371.     virtual type        GetCurrentFirstDerivative( const float time ) const;
  2372.     virtual type        GetCurrentSecondDerivative( const float time ) const;
  2373.  
  2374. protected:
  2375.     idList<float>        weights;
  2376.  
  2377.     float                WeightForIndex( const int index ) const;
  2378. };
  2379.  
  2380. /*
  2381. ====================
  2382. idCurve_NURBS::idCurve_NURBS
  2383. ====================
  2384. */
  2385. template< class type >
  2386. ID_INLINE idCurve_NURBS<type>::idCurve_NURBS( void ) {
  2387. }
  2388.  
  2389. /*
  2390. ====================
  2391. idCurve_NURBS::AddValue
  2392.  
  2393.   add a timed/value pair to the spline
  2394.   returns the index to the inserted pair
  2395. ====================
  2396. */
  2397. template< class type >
  2398. ID_INLINE int idCurve_NURBS<type>::AddValue( const float time, const type &value ) {
  2399.     int i;
  2400.  
  2401.     i = IndexForTime( time );
  2402.     times.Insert( time, i );
  2403.     values.Insert( value, i );
  2404.     weights.Insert( 1.0f, i );
  2405.     return i;
  2406. }
  2407.  
  2408. /*
  2409. ====================
  2410. idCurve_NURBS::AddValue
  2411.  
  2412.   add a timed/value pair to the spline
  2413.   returns the index to the inserted pair
  2414. ====================
  2415. */
  2416. template< class type >
  2417. ID_INLINE int idCurve_NURBS<type>::AddValue( const float time, const type &value, const float weight ) {
  2418.     int i;
  2419.  
  2420.     i = IndexForTime( time );
  2421.     times.Insert( time, i );
  2422.     values.Insert( value, i );
  2423.     weights.Insert( weight, i );
  2424.     return i;
  2425. }
  2426.  
  2427. /*
  2428. ====================
  2429. idCurve_NURBS::GetCurrentValue
  2430.  
  2431.   get the value for the given time
  2432. ====================
  2433. */
  2434. template< class type >
  2435. ID_INLINE type idCurve_NURBS<type>::GetCurrentValue( const float time ) const {
  2436.     int i, j, k;
  2437.     float w, b, *bvals, clampedTime;
  2438.     type v;
  2439.  
  2440.     if ( times.Num() == 1 ) {
  2441.         return values[0];
  2442.     }
  2443.  
  2444.     bvals = (float *) _alloca16( order * sizeof(float) );
  2445.  
  2446.     clampedTime = ClampedTime( time );
  2447.     i = IndexForTime( clampedTime );
  2448.     Basis( i-1, order, clampedTime, bvals );
  2449.     v = values[0] - values[0];
  2450.     w = 0.0f;
  2451.     for ( j = 0; j < order; j++ ) {
  2452.         k = i + j - ( order >> 1 );
  2453.         b = bvals[j] * WeightForIndex( k );
  2454.         w += b;
  2455.         v += b * ValueForIndex( k );
  2456.     }
  2457.     return v / w;
  2458. }
  2459.  
  2460. /*
  2461. ====================
  2462. idCurve_NURBS::GetCurrentFirstDerivative
  2463.  
  2464.   get the first derivative for the given time
  2465. ====================
  2466. */
  2467. template< class type >
  2468. ID_INLINE type idCurve_NURBS<type>::GetCurrentFirstDerivative( const float time ) const {
  2469.     int i, j, k;
  2470.     float w, wb, wd1, b, d1, *bvals, *d1vals, clampedTime;
  2471.     type v, vb, vd1;
  2472.  
  2473.     if ( times.Num() == 1 ) {
  2474.         return values[0];
  2475.     }
  2476.  
  2477.     bvals = (float *) _alloca16( order * sizeof(float) );
  2478.     d1vals = (float *) _alloca16( order * sizeof(float) );
  2479.  
  2480.     clampedTime = ClampedTime( time );
  2481.     i = IndexForTime( clampedTime );
  2482.     Basis( i-1, order, clampedTime, bvals );
  2483.     BasisFirstDerivative( i-1, order, clampedTime, d1vals );
  2484.     vb = vd1 = values[0] - values[0];
  2485.     wb = wd1 = 0.0f;
  2486.     for ( j = 0; j < order; j++ ) {
  2487.         k = i + j - ( order >> 1 );
  2488.         w = WeightForIndex( k );
  2489.         b = bvals[j] * w;
  2490.         d1 = d1vals[j] * w;
  2491.         wb += b;
  2492.         wd1 += d1;
  2493.         v = ValueForIndex( k );
  2494.         vb += b * v;
  2495.         vd1 += d1 * v;
  2496.     }
  2497.     return ( wb * vd1 - vb * wd1 ) / ( wb * wb );
  2498. }
  2499.  
  2500. /*
  2501. ====================
  2502. idCurve_NURBS::GetCurrentSecondDerivative
  2503.  
  2504.   get the second derivative for the given time
  2505. ====================
  2506. */
  2507. template< class type >
  2508. ID_INLINE type idCurve_NURBS<type>::GetCurrentSecondDerivative( const float time ) const {
  2509.     int i, j, k;
  2510.     float w, wb, wd1, wd2, b, d1, d2, *bvals, *d1vals, *d2vals, clampedTime;
  2511.     type v, vb, vd1, vd2;
  2512.  
  2513.     if ( times.Num() == 1 ) {
  2514.         return values[0];
  2515.     }
  2516.  
  2517.     bvals = (float *) _alloca16( order * sizeof(float) );
  2518.     d1vals = (float *) _alloca16( order * sizeof(float) );
  2519.     d2vals = (float *) _alloca16( order * sizeof(float) );
  2520.  
  2521.     clampedTime = ClampedTime( time );
  2522.     i = IndexForTime( clampedTime );
  2523.     Basis( i-1, order, clampedTime, bvals );
  2524.     BasisFirstDerivative( i-1, order, clampedTime, d1vals );
  2525.     BasisSecondDerivative( i-1, order, clampedTime, d2vals );
  2526.     vb = vd1 = vd2 = values[0] - values[0];
  2527.     wb = wd1 = wd2 = 0.0f;
  2528.     for ( j = 0; j < order; j++ ) {
  2529.         k = i + j - ( order >> 1 );
  2530.         w = WeightForIndex( k );
  2531.         b = bvals[j] * w;
  2532.         d1 = d1vals[j] * w;
  2533.         d2 = d2vals[j] * w;
  2534.         wb += b;
  2535.         wd1 += d1;
  2536.         wd2 += d2;
  2537.         v = ValueForIndex( k );
  2538.         vb += b * v;
  2539.         vd1 += d1 * v;
  2540.         vd2 += d2 * v;
  2541.     }
  2542.     return ( ( wb * wb ) * ( wb * vd2 - vb * wd2 ) - ( wb * vd1 - vb * wd1 ) * 2.0f * wb * wd1 ) / ( wb * wb * wb * wb );
  2543. }
  2544.  
  2545. /*
  2546. ====================
  2547. idCurve_NURBS::WeightForIndex
  2548.  
  2549.   get the weight for the given index
  2550. ====================
  2551. */
  2552. template< class type >
  2553. ID_INLINE float idCurve_NURBS<type>::WeightForIndex( const int index ) const {
  2554.     int n = weights.Num()-1;
  2555.  
  2556.     if ( index < 0 ) {
  2557.         if ( boundaryType == BT_CLOSED ) {
  2558.             return weights[ weights.Num() + index % weights.Num() ];
  2559.         } else {
  2560.             return weights[0] + index * ( weights[1] - weights[0] );
  2561.         }
  2562.     } else if ( index > n ) {
  2563.         if ( boundaryType == BT_CLOSED ) {
  2564.             return weights[ index % weights.Num() ];
  2565.         } else {
  2566.             return weights[n] + ( index - n ) * ( weights[n] - weights[n-1] );
  2567.         }
  2568.     }
  2569.     return weights[index];
  2570. }
  2571.  
  2572. #endif /* !__MATH_CURVE_H__ */
  2573.