bezier.cpp

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

Generated on Tue Feb 22 13:32:26 2011 for Fawkes API by  doxygen 1.4.7