Use filename_extension() and filename_sans_extension().
[synfig.git] / ETL / trunk / ETL / _bspline.h
1 /*! ========================================================================
2 ** Extended Template and Library
3 ** B-Spline Class Implementation
4 ** $Id$
5 **
6 ** Copyright (c) 2002 Robert B. Quattlebaum Jr.
7 **
8 ** This package is free software; you can redistribute it and/or
9 ** modify it under the terms of the GNU General Public License as
10 ** published by the Free Software Foundation; either version 2 of
11 ** the License, or (at your option) any later version.
12 **
13 ** This package is distributed in the hope that it will be useful,
14 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
15 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16 ** General Public License for more details.
17 **
18 ** === N O T E S ===========================================================
19 **
20 ** This is an internal header file, included by other ETL headers.
21 ** You should not attempt to use it directly.
22 **
23 ** ========================================================================= */
24
25 /* === S T A R T =========================================================== */
26
27 #ifndef __ETL__BSPLINE_H
28 #define __ETL__BSPLINE_H
29
30 /* === H E A D E R S ======================================================= */
31
32 #include <vector>
33 #include <functional>
34 #include "_curve_func.h"
35
36 /* === M A C R O S ========================================================= */
37
38 /* === T Y P E D E F S ===================================================== */
39
40 /* === C L A S S E S & S T R U C T S ======================================= */
41
42 _ETL_BEGIN_NAMESPACE
43
44 template <class T, class K=float, class C=affine_combo<T,K>, class D=distance_func<T> >
45 class bspline : public std::unary_function<K,T>
46 {
47 public:
48         typedef T value_type;
49         typedef K knot_type;
50         typedef std::vector<knot_type>  knot_container;
51         typedef std::vector<value_type> cpoint_container;
52         typedef typename knot_container::iterator knot_iterator;
53         typedef typename cpoint_container::iterator cpoint_iterator;
54
55         typedef C affine_func_type;
56         typedef D distance_func_type;
57
58 protected:
59         affine_func_type affine_func;
60         distance_func_type distance_func;
61
62 private:
63         int m;
64         knot_container _knots;
65         cpoint_container _cpoints;
66         bool _loop;
67
68 public:
69         bspline():m(2),_loop(false) {  }
70
71         int get_m()const { return m-1; };
72         int set_m(int new_m) { m=new_m+1; return m-1; };
73
74         bool set_loop(bool x) { _loop=x; reset_knots(); return _loop; }
75
76         knot_container & knots() { return _knots; };
77         cpoint_container & cpoints() { return _cpoints; };
78
79         const knot_container & knots()const { return _knots; };
80         const cpoint_container & cpoints()const { return _cpoints; };
81
82         void reset_knots()
83         {
84                 int i;
85
86                 if(!_loop)
87                 {
88                         _knots.clear();
89                         if(!_cpoints.size())
90                                 return;
91                         while(m>(signed)_cpoints.size())
92                                 m--;
93                         for(i=0;i<m;i++)
94                                 *_knots.insert(_knots.end())=0;
95                         for(i=1;i<(signed)_cpoints.size()-m+1;i++)
96                                 *_knots.insert(_knots.end())=i;
97                         for(i=0;i<m;i++)
98                                 *_knots.insert(_knots.end())=_cpoints.size()-m+1;
99                 }
100                 else
101                 {
102                         _knots.clear();
103                         if(!_cpoints.size())
104                                 return;
105                         while(m>(signed)_cpoints.size())
106                                 m--;
107                         for(i=0;i<=(signed)_cpoints.size()-m+1;i++)
108                                 *_knots.insert(_knots.end())=i;
109                 }
110         }
111
112         int calc_curve_segment(knot_type t)const
113         {
114                 int k;
115                 if(t<0)
116                         t=0;
117                 if(t>=_knots.back())
118                         t=_knots.back()-0.0001;
119                 for(k=0;_knots[k]>t || _knots[k+1]<=t;k++);
120
121                 return k;
122         }
123
124         knot_container get_segment_knots(int i)const
125         {
126                 if(i+1<m)
127                 {
128                         knot_container ret(_knots.begin(),_knots.begin()+i+m+1);
129
130                         return ret;
131                 }
132                 if(i+1>=(signed)_knots.size())
133                 {
134                         knot_container ret(_knots.begin()+i-m+1,_knots.end());
135                         return ret;
136                 }
137                 return knot_container(_knots.begin()+i-m+1,     _knots.begin()+i+m);
138         }
139
140         cpoint_container get_segment_cpoints(int i)const
141         {
142                 if(i+1<m)
143                 {
144                         return cpoint_container();
145                 }
146                 if(i+1>=(signed)_knots.size())
147                 {
148                         return cpoint_container();
149                 }
150                 return cpoint_container(_cpoints.begin()+i-m+1, _cpoints.begin()+i+1);
151         }
152
153         cpoint_container calc_shell(knot_type t, int level)const
154         {
155                 int
156                         i=calc_curve_segment(t),
157                         j,k;
158
159                 knot_container u=get_segment_knots(i);
160
161                 cpoint_container d=get_segment_cpoints(i);
162
163                 if(!d.size())
164                         return cpoint_container();
165
166                 for(j=0;d.size()>1 && j<level;d.pop_back(),j++)
167                 {
168                         for(k=0;k<d.size()-1;k++)
169                         {
170                                 d[k]=affine_func(d[k],d[k+1],((t-u[j+k+1])/(u[m+k]-u[j+k+1])));
171                         }
172                 }
173                 return d;
174         }
175
176         value_type operator()(knot_type t)const
177         {
178                 return get_curve_val(calc_curve_segment(t),t);
179         }
180
181         value_type get_curve_val(int i,knot_type t)const
182         {
183                 int
184                         j,k;
185
186                 knot_container u=get_segment_knots(i);
187
188                 cpoint_container d=get_segment_cpoints(i);
189
190                 if(!d.size())
191                         return value_type();
192
193                 for(j=0;d.size()>1;d.pop_back(),j++)
194                 {
195                         for(k=0;k<(signed)d.size()-1;k++)
196                         {
197                                 d[k]=affine_func(d[k],d[k+1],((t-u[j+k+1])/(u[m+k]-u[j+k+1])));
198                         }
199                 }
200                 return d.front();
201         }
202
203         cpoint_iterator find_closest_cpoint(const value_type &point, typename distance_func_type::result_type max)
204         {
205                 cpoint_iterator i=_cpoints.begin();
206                 cpoint_iterator ret=i;
207                 typename distance_func_type::result_type dist=distance_func(point,_cpoints[0]);
208
209                 // The distance function returns "cooked" (ie: squared)
210                 // distances, so we need to cook our max distance for
211                 // the comparison to work correctly.
212                 max=distance_func.cook(max);
213
214                 for(++i;i<_cpoints.end();i++)
215                 {
216                         typename distance_func_type::result_type thisdist=distance_func(point,*i);
217
218                         if(thisdist<dist)
219                         {
220                                 dist=thisdist;
221                                 ret=i;
222                         }
223                 }
224                 if(dist<max)
225                         return ret;
226                 return _cpoints.end();
227         }
228 };
229
230 _ETL_END_NAMESPACE
231
232 /* -- F U N C T I O N S ----------------------------------------------------- */
233
234 /* -- E N D ----------------------------------------------------------------- */
235
236 #endif