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