Cinder

  • Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

include/cinder/BSpline.h

Go to the documentation of this file.
00001 /*
00002  Copyright (c) 2010, The Barbarian Group
00003  All rights reserved.
00004 
00005  Redistribution and use in source and binary forms, with or without modification, are permitted provided that
00006  the following conditions are met:
00007 
00008     * Redistributions of source code must retain the above copyright notice, this list of conditions and
00009     the following disclaimer.
00010     * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and
00011     the following disclaimer in the documentation and/or other materials provided with the distribution.
00012 
00013  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
00014  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
00015  PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
00016  ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
00017  TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00018  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00019  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00020  POSSIBILITY OF SUCH DAMAGE.
00021 
00022  Significant Portions Copyright:
00023  Geometric Tools, LLC
00024  Copyright (c) 1998-2010
00025  Distributed under the Boost Software License, Version 1.0.
00026  http://www.boost.org/LICENSE_1_0.txt
00027  http://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
00028 */
00029 
00030 #pragma once
00031 
00032 #include <vector>
00033 #include "cinder/Vector.h"
00034 
00035 namespace cinder {
00036 
00037 class BSplineBasis
00038 {
00039  public:
00040     BSplineBasis();
00041 
00042     // Open uniform or periodic uniform.  The knot array is internally
00043     // generated with equally spaced elements.
00044     BSplineBasis( int aNumCtrlPoints, int iDegree, bool bOpen );
00045     void create( int aNumCtrlPoints, int iDegree, bool bOpen );
00046 
00047     // Open nonuniform.  The knot array must have n-d elements.  The elements
00048     // must be nondecreasing.  Each element must be in [0,1].  The caller is
00049     // responsible for deleting afKnot.  An internal copy is made, so to
00050     // dynamically change knots you must use the setKnot function.
00051     BSplineBasis( int aNumCtrlPoints, int iDegree, const float* afKnot );
00052     void create( int aNumCtrlPoints, int iDegree, const float* afKnot );
00053 
00054     BSplineBasis( const BSplineBasis &basis );
00055     BSplineBasis& operator=( const BSplineBasis &basis );
00056 
00057     ~BSplineBasis();
00058 
00059     int getNumControlPoints() const;
00060     int getDegree() const;
00061     bool isOpen() const;
00062     bool isUniform() const;
00063 
00064     // The knot values can be changed only if the basis function is nonuniform
00065     // and the input index is valid (0 <= i <= n-d-1).  If these conditions
00066     // are not satisfied, getKnot returns MAX_REAL.
00067     void setKnot( int i, float fKnot );
00068     float getKnot( int i ) const;
00069 
00070     // access basis functions and their derivatives
00071     float getD0( int i ) const;
00072     float getD1( int i ) const;
00073     float getD2( int i ) const;
00074     float getD3( int i ) const;
00075 
00076     // evaluate basis functions and their derivatives
00077     void compute( float fTime, unsigned int uiOrder, int &riMinIndex, int &riMaxIndex ) const;
00078 
00079  protected:
00080     int initialize( int iNumCtrlPoints, int iDegree, bool bOpen );
00081     float** allocate() const;
00082     void deallocate( float** aafArray );
00083 
00084     // Determine knot index i for which knot[i] <= rfTime < knot[i+1].
00085     int getKey( float& rfTime ) const;
00086 
00087     int mNumCtrlPoints;    // n+1
00088     int mDegree;           // d
00089     float *mKnots;          // knot[n+d+2]
00090     bool mOpen, mUniform;
00091 
00092     // Storage for the basis functions and their derivatives first three
00093     // derivatives.  The basis array is always allocated by the constructor
00094     // calls.  A derivative basis array is allocated on the first call to a
00095     // derivative member function.
00096     float **m_aafBD0;             // bd0[d+1][n+d+1]
00097     mutable float **m_aafBD1;     // bd1[d+1][n+d+1]
00098     mutable float **m_aafBD2;     // bd2[d+1][n+d+1]
00099     mutable float **m_aafBD3;     // bd3[d+1][n+d+1]
00100 };
00101 
00102 template<typename T>
00103 class BSpline
00104 {
00105   public:
00106     // Construction and destruction.  The caller is responsible for deleting
00107     // the input arrays if they were dynamically allocated.  Internal copies
00108     // of the arrays are made, so to dynamically change control points or
00109     // knots you must use the 'setControlPoint', 'getControlPoint', and
00110     // 'Knot' member functions.
00111 
00112     // Uniform spline.  The number of control points is n+1 >= 2.  The degree
00113     // of the B-spline is d and must satisfy 1 <= d <= n.  The knots are
00114     // implicitly calculated in [0,1].  If bOpen is 'true', the spline is
00115     // open and the knots are
00116     //   t[i] = 0,               0 <= i <= d
00117     //          (i-d)/(n+1-d),   d+1 <= i <= n
00118     //          1,               n+1 <= i <= n+d+1
00119     // If bOpen is 'false', the spline is periodic and the knots are
00120     //   t[i] = (i-d)/(n+1-d),   0 <= i <= n+d+1
00121     // If bLoop is 'true', extra control points are added to generate a closed
00122     // curve.  For an open spline, the control point array is reallocated and
00123     // one extra control point is added, set to the first control point
00124     // C[n+1] = C[0].  For a periodic spline, the control point array is
00125     // reallocated and the first d points are replicated.  In either case the
00126     // knot array is calculated accordingly.
00127     BSpline( const std::vector<T> &points, int degree, bool loop, bool open );
00128     
00129     // Open, nonuniform spline.  The knot array must have n-d elements.  The
00130     // elements must be nondecreasing.  Each element must be in [0,1].
00131     BSpline() : mCtrlPoints( 0 ), mNumCtrlPoints( -1 ) {}
00132     BSpline( int numControlPoints, const T *controlPoints, int degree, bool loop, const float *knots );
00133     BSpline( const BSpline &bspline );
00134     BSpline& operator=( const BSpline &bspline );
00135 
00136     ~BSpline();
00137 
00138     int getNumControlPoints() const { return mNumCtrlPoints; }
00139     int getDegree() const { return mBasis.getDegree(); }
00140     int getNumSpans() const { return mNumCtrlPoints - mBasis.getDegree(); }
00141     bool isOpen() const { return mBasis.isOpen(); }
00142     bool isUniform() const { return mBasis.isUniform(); }
00143     bool isLoop() const { return mLoop; }
00144 
00145     // Control points may be changed at any time.  The input index should be
00146     // valid (0 <= i <= n).  If it is invalid, getControlPoint returns a
00147     // vector whose components are all MAX_REAL.
00148     void setControlPoint( int i, const T &rkCtrl );
00149     T getControlPoint( int i ) const;
00150 
00151     // The knot values can be changed only if the basis function is nonuniform
00152     // and the input index is valid (0 <= i <= n-d-1).  If these conditions
00153     // are not satisfied, getKnot returns MAX_REAL.
00154     void setKnot( int i, float fKnot );
00155     float getKnot( int i ) const;
00156 
00157     // The spline is defined for 0 <= t <= 1.  If a t-value is outside [0,1],
00158     // an open spline clamps t to [0,1].  That is, if t > 1, t is set to 1;
00159     // if t < 0, t is set to 0.  A periodic spline wraps to to [0,1].  That
00160     // is, if t is outside [0,1], then t is set to t-floor(t).
00161     T getPosition( float t ) const;
00162     T getDerivative( float t ) const;
00163     T getSecondDerivative( float t ) const;
00164     T getThirdDerivative( float t ) const;
00165     typename T::TYPE getSpeed( float t ) const { return getDerivative( t ).length(); }
00166 
00167     float getLength( float fT0, float fT1 ) const;
00168 
00169     // If you need position and derivatives at the same time, it is more
00170     // efficient to call these functions.  Pass the addresses of those
00171     // quantities whose values you want.  You may pass 0 in any argument
00172     // whose value you do not want.
00173     void get( float t, T *position, T *firstDerivative = NULL, T *secondDerivative = NULL, T *thirdDerivative = NULL ) const;
00175     float getTime( float length ) const;
00176 
00177     // Access the basis function to compute it without control points.  This
00178     // is useful for least squares fitting of curves.
00179     BSplineBasis& getBasis();
00180 
00181  protected:
00182     // Replicate the necessary number of control points when the create
00183     // function has bLoop equal to true, in which case the spline curve must
00184     // be a closed curve.
00185     void createControl( const T *akCtrlPoint );
00186 
00187     int mNumCtrlPoints;
00188     T *mCtrlPoints;  // ctrl[n+1]
00189     bool mLoop;
00190     BSplineBasis mBasis;
00191     int mReplicate;  // the number of replicated control points
00192 };
00193 
00194 typedef BSpline<Vec2f> BSpline2f;
00195 typedef BSpline<Vec3f> BSpline3f;
00196 
00197 } // namespace cinder