# 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