Fawkes API
Fawkes Development Version
|
00001 00002 /*************************************************************************** 00003 * bezier.cpp - Bezier curve 00004 * 00005 * Created: Mon Oct 06 15:14:53 2008 00006 * Copyright 2008 Daniel Beck 00007 * 00008 ****************************************************************************/ 00009 00010 /* This program is free software; you can redistribute it and/or modify 00011 * it under the terms of the GNU General Public License as published by 00012 * the Free Software Foundation; either version 2 of the License, or 00013 * (at your option) any later version. A runtime exception applies to 00014 * this software (see LICENSE.GPL_WRE file mentioned below for details). 00015 * 00016 * This program is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 * GNU Library General Public License for more details. 00020 * 00021 * Read the full text in the LICENSE.GPL_WRE file in the doc directory. 00022 */ 00023 00024 #include <geometry/bezier.h> 00025 #include <geometry/hom_point.h> 00026 #include <geometry/hom_vector.h> 00027 00028 using namespace std; 00029 00030 namespace fawkes { 00031 00032 /** @class fawkes::Bezier <geometry/bezier.h> 00033 * A Bezier curve class. 00034 * @author Daniel Beck 00035 */ 00036 00037 /** Constructor. */ 00038 Bezier::Bezier() 00039 { 00040 m_de_casteljau_points = NULL; 00041 m_last_t = -1.0; 00042 m_num_subdivisions = 0; 00043 00044 register_primitives(); 00045 } 00046 00047 /** Constructor. 00048 * @param control_points the control points for the Bezier curve 00049 */ 00050 Bezier::Bezier(const vector<HomPoint>& control_points) 00051 : m_control_points(control_points) 00052 { 00053 m_num_control_points = m_control_points.size(); 00054 00055 m_de_casteljau_points = NULL; 00056 init_dclj_array(); 00057 00058 m_last_t = -1.0; 00059 m_num_subdivisions = 0; 00060 00061 register_primitives(); 00062 } 00063 00064 /** Copy constructor. 00065 * @param b another Bezier curve 00066 */ 00067 Bezier::Bezier(const Bezier& b) 00068 : m_control_points(b.m_control_points) 00069 { 00070 m_num_control_points = b.m_num_control_points; 00071 m_de_casteljau_points = NULL; 00072 init_dclj_array(); 00073 00074 m_last_t = -1.0; 00075 m_num_subdivisions = 0; 00076 00077 clear_primitives(); 00078 register_primitives(); 00079 } 00080 00081 /** Destructor. */ 00082 Bezier::~Bezier() 00083 { 00084 for (unsigned int i = 0; i < m_dclj_array_size; ++i) 00085 { delete m_de_casteljau_points[i].first; } 00086 00087 delete[] m_de_casteljau_points; 00088 } 00089 00090 /** Set the control points. 00091 * @param control_points the new control points 00092 */ 00093 void 00094 Bezier::set_control_points(const vector<HomPoint>& control_points) 00095 { 00096 m_control_points.clear(); 00097 m_control_points = control_points; 00098 00099 m_num_control_points = m_control_points.size(); 00100 00101 m_last_t = -1.0; 00102 00103 init_dclj_array(); 00104 00105 clear_primitives(); 00106 register_primitives(); 00107 } 00108 00109 void 00110 Bezier::init_dclj_array() 00111 { 00112 m_dclj_array_size = m_num_control_points * (m_num_control_points + 1) / 2; 00113 m_dclj_array_size -= m_num_control_points; 00114 00115 delete m_de_casteljau_points; 00116 m_de_casteljau_points = new pair<HomPoint*, bool>[m_dclj_array_size]; 00117 00118 for (unsigned int i = 0; i < m_dclj_array_size; ++i) 00119 { 00120 m_de_casteljau_points[i].first = NULL; 00121 m_de_casteljau_points[i].second = false; 00122 } 00123 } 00124 00125 /** Replace a specific control point. 00126 * @param index the index of the control point 00127 * @param control_point the replacement control point 00128 */ 00129 void 00130 Bezier::set_control_point(unsigned int index, const HomPoint& control_point) 00131 { 00132 m_control_points[index] = control_point; 00133 m_de_casteljau_points[index] = pair<HomPoint*, bool>( &(m_control_points[index]), true ); 00134 00135 m_last_t = -1.0; 00136 00137 clear_primitives(); 00138 register_primitives(); 00139 } 00140 00141 /** Get the control points. 00142 * @return a copy of the control points 00143 */ 00144 std::vector<HomPoint> 00145 Bezier::get_control_points() const 00146 { 00147 return m_control_points; 00148 } 00149 00150 /** Get a specific control point. 00151 * @param i the index of the control point 00152 * @return control point 00153 */ 00154 HomPoint 00155 Bezier::get_control_point(unsigned int i) const 00156 { 00157 if (i < m_num_control_points) 00158 { return m_control_points.at(i); } 00159 else 00160 { throw exception(); } 00161 } 00162 00163 /** Get the degree of the polynom. 00164 * @return the degree of the polynom 00165 */ 00166 unsigned int 00167 Bezier::degree() const 00168 { 00169 return m_num_control_points - 1; 00170 } 00171 00172 /** Evalutate the polynom for a given t 00173 * @param t a value between 0.0 and 1.0 00174 * @return the corresponding point on the curve 00175 */ 00176 HomPoint 00177 Bezier::eval(float t) 00178 { 00179 if ( t < 0 || t > 1) 00180 { throw exception(); } 00181 00182 return de_casteljau(m_num_control_points - 1, 0, t); 00183 } 00184 00185 /** Compute the tangent vector at position t. 00186 * @param t the curve parameter 00187 * @return the tangent vector 00188 */ 00189 HomVector 00190 Bezier::tangent_at_t(float t) 00191 { 00192 HomVector v; 00193 HomPoint b0 = de_casteljau(m_num_control_points - 2, 0, t); 00194 HomPoint b1 = de_casteljau(m_num_control_points - 2, 1, t); 00195 v = b1 - b0; 00196 00197 return v; 00198 } 00199 00200 /** Compute the tangent vector at the specified control point. 00201 * @param index the index of the control point 00202 * @return the tangent vector 00203 */ 00204 HomVector 00205 Bezier::tangent_at_point(unsigned int index) 00206 { 00207 float t; 00208 if (index > m_num_control_points) 00209 { t = 1.0; } 00210 else 00211 { t = index / (float) m_num_control_points; } 00212 00213 return tangent_at_t(t); 00214 } 00215 00216 /** Subdivide the curve into two polynome of the same degree. 00217 * @param t determines the point where the curve is divided 00218 * @param c the Bezier for the part [0, t] 00219 * @param d the Bezier for the part [t, 1] 00220 */ 00221 void 00222 Bezier::subdivide(float t, Bezier& c, Bezier& d) 00223 { 00224 if ( t < 0 || t > 1 ) 00225 { throw exception(); } 00226 00227 vector<HomPoint> control_points; 00228 00229 for (unsigned k = 0; k < m_num_control_points; ++k) 00230 { 00231 HomPoint p = de_casteljau(k, 0, t); 00232 control_points.push_back(p); 00233 } 00234 00235 c.set_control_points(control_points); 00236 control_points.clear(); 00237 00238 for (unsigned i = 0; i < m_num_control_points; ++i) 00239 { 00240 unsigned int k = m_num_control_points - i - 1; 00241 HomPoint p = de_casteljau(k, i, t); 00242 control_points.push_back(p); 00243 } 00244 00245 d.set_control_points(control_points); 00246 } 00247 00248 /** Approximate the curve with points. 00249 * @param num_subdivisions the number of subdivisions that is performed 00250 * @return the point approximating the curve 00251 */ 00252 const vector<HomPoint>& 00253 Bezier::approximate(unsigned int num_subdivisions) 00254 { 00255 if (m_num_subdivisions == num_subdivisions) 00256 { return m_approximation; } 00257 00258 vector<Bezier> b1; 00259 vector<Bezier> b2; 00260 00261 b1.push_back( *this ); 00262 00263 for (unsigned int i = 0; i < num_subdivisions; ++i) 00264 { 00265 b2.clear(); 00266 00267 for ( vector<Bezier>::iterator iter = b1.begin(); 00268 iter != b1.end(); 00269 ++iter ) 00270 { 00271 Bezier c, d; 00272 iter->subdivide(0.5, c, d); 00273 b2.push_back(c); 00274 b2.push_back(d); 00275 } 00276 00277 b1.clear(); 00278 b1 = b2; 00279 } 00280 00281 for ( vector<Bezier>::iterator bit = b2.begin(); 00282 bit != b2.end(); 00283 ++bit ) 00284 { 00285 vector<HomPoint> points = bit->get_control_points(); 00286 00287 vector<HomPoint>::iterator pit = points.begin(); 00288 00289 if ( bit != b2.begin() ) 00290 // skip first control point for all Bezier curves except for 00291 // the first one 00292 { ++pit; } 00293 00294 for ( vector<HomPoint>::iterator iter = pit; 00295 iter != points.end(); 00296 ++iter ) 00297 { m_approximation.push_back( *iter); } 00298 } 00299 00300 m_num_subdivisions = num_subdivisions; 00301 00302 return m_approximation; 00303 } 00304 00305 HomPoint 00306 Bezier::de_casteljau(unsigned int k, unsigned int i, float t) 00307 { 00308 if (0 == k) 00309 { return m_control_points.at(i); } 00310 00311 if (m_last_t != t) 00312 { 00313 for ( unsigned int j = 0; 00314 j < m_dclj_array_size; 00315 ++j ) 00316 { 00317 delete m_de_casteljau_points[j].first; 00318 00319 m_de_casteljau_points[j].first = NULL; 00320 m_de_casteljau_points[j].second = false; 00321 } 00322 00323 m_last_t = t; 00324 } 00325 00326 unsigned int index = get_dclj_array_index(k, i); 00327 00328 if ( m_de_casteljau_points[index].second ) 00329 { return *( m_de_casteljau_points[index].first ); } 00330 else 00331 { 00332 HomPoint* p = new HomPoint(); 00333 *p = de_casteljau(k-1, i, t) * (1.0 - t) + de_casteljau(k-1, i+1, t) * t; 00334 m_de_casteljau_points[index] = pair<HomPoint*, bool>(p, true); 00335 return *p; 00336 } 00337 } 00338 00339 unsigned int 00340 Bezier::get_dclj_array_index(unsigned int k, unsigned int i) const 00341 { 00342 unsigned int index = 0; 00343 00344 for (unsigned int j = 0; j < k; ++j) 00345 { index += m_num_control_points - j; } 00346 00347 index += i; 00348 index -= m_num_control_points; 00349 00350 return index; 00351 } 00352 00353 void 00354 Bezier::register_primitives() 00355 { 00356 vector<HomPoint>::iterator iter; 00357 for ( iter = m_control_points.begin(); 00358 iter != m_control_points.end(); 00359 ++iter ) 00360 { 00361 HomPoint& p = *iter; 00362 add_primitive( &p ); 00363 } 00364 } 00365 00366 void 00367 Bezier::post_transform() 00368 { 00369 m_last_t = -1.0; 00370 } 00371 00372 } // end namespace fawkes