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  */
00153 HomPoint
00154 Bezier::get_control_point(unsigned int i) const
00155 {
00156   if (i < m_num_control_points)
00157     { return m_control_points.at(i); }
00158   else
00159     { throw exception(); }
00160 }
00161 
00162 /** Get the degree of the polynom.
00163  * @return the degree of the polynom
00164  */
00165 unsigned int
00166 Bezier::degree() const
00167 {
00168   return m_num_control_points - 1;
00169 }
00170 
00171 /** Evalutate the polynom for a given t
00172  * @param t a value between 0.0 and 1.0
00173  * @return the corresponding point on the curve
00174  */
00175 HomPoint
00176 Bezier::eval(float t)
00177 {
00178   if ( t < 0 || t > 1)
00179     { throw exception(); }
00180
00181   return de_casteljau(m_num_control_points - 1, 0, t);
00182 }
00183 
00184 /** Compute the tangent vector at position t.
00185  * @param t the curve parameter
00186  * @return the tangent vector
00187  */
00188 HomVector
00189 Bezier::tangent_at_t(float t)
00190 {
00191   HomVector v;
00192   HomPoint b0 = de_casteljau(m_num_control_points - 2, 0, t);
00193   HomPoint b1 = de_casteljau(m_num_control_points - 2, 1, t);
00194   v = b1 - b0;
00195
00196   return v;
00197 }
00198 
00199 /** Compute the tangent vector at the specified control point.
00200  * @param index the index of the control point
00201  * @return the tangent vector
00202  */
00203 HomVector
00204 Bezier::tangent_at_point(unsigned int index)
00205 {
00206   float t;
00207   if (index > m_num_control_points)
00208     { t = 1.0; }
00209   else
00210     { t = index / (float) m_num_control_points; }
00211
00212   return tangent_at_t(t);
00213 }
00214 
00215 /** Subdivide the curve into two polynome of the same degree.
00216  * @param t determines the point where the curve is divided
00217  * @param c the Bezier for the part [0, t]
00218  * @param d the Bezier for the part [t, 1]
00219  */
00220 void
00221 Bezier::subdivide(float t, Bezier& c, Bezier& d)
00222 {
00223   if ( t < 0 || t > 1 )
00224     { throw exception(); }
00225
00226   vector<HomPoint> control_points;
00227
00228   for (unsigned k = 0; k < m_num_control_points; ++k)
00229     {
00230       HomPoint p = de_casteljau(k, 0, t);
00231       control_points.push_back(p);
00232     }
00233
00234   c.set_control_points(control_points);
00235   control_points.clear();
00236
00237   for (unsigned i = 0; i < m_num_control_points; ++i)
00238     {
00239       unsigned int k = m_num_control_points - i - 1;
00240       HomPoint p = de_casteljau(k, i, t);
00241       control_points.push_back(p);
00242     }
00243
00244   d.set_control_points(control_points);
00245 }
00246 
00247 /** Approximate the curve with points.
00248  * @param num_subdivisions the number of subdivisions that is performed
00249  * @return the point approximating the curve
00250  */
00251 const vector<HomPoint>&
00252 Bezier::approximate(unsigned int num_subdivisions)
00253 {
00254   if (m_num_subdivisions == num_subdivisions)
00255     { return m_approximation; }
00256
00257   vector<Bezier> b1;
00258   vector<Bezier> b2;
00259
00260   b1.push_back( *this );
00261
00262   for (unsigned int i = 0; i < num_subdivisions; ++i)
00263     {
00264       b2.clear();
00265
00266       for ( vector<Bezier>::iterator iter = b1.begin();
00267             iter != b1.end();
00268             ++iter )
00269         {
00270           Bezier c, d;
00271           iter->subdivide(0.5, c, d);
00272           b2.push_back(c);
00273           b2.push_back(d);
00274         }
00275
00276       b1.clear();
00277       b1 = b2;
00278     }
00279
00280   for ( vector<Bezier>::iterator bit = b2.begin();
00281         bit != b2.end();
00282         ++bit )
00283     {
00284       vector<HomPoint> points = bit->get_control_points();
00285
00286       vector<HomPoint>::iterator pit = points.begin();
00287
00288       if ( bit != b2.begin() )
00289         // skip first control point for all Bezier curves except for
00290         // the first one
00291         { ++pit; }
00292
00293       for ( vector<HomPoint>::iterator iter = pit;
00294             iter != points.end();
00295             ++iter )
00296         { m_approximation.push_back( *iter); }
00297     }
00298
00299   m_num_subdivisions = num_subdivisions;
00300
00301   return m_approximation;
00302 }
00303
00304 HomPoint
00305 Bezier::de_casteljau(unsigned int k, unsigned int i, float t)
00306 {
00307   if (0 == k)
00308     { return m_control_points.at(i); }
00309
00310   if (m_last_t != t)
00311     {
00312       for ( unsigned int j = 0;
00313             j < m_dclj_array_size;
00314             ++j )
00315         {
00316           delete m_de_casteljau_points[j].first;
00317
00318           m_de_casteljau_points[j].first  = NULL;
00319           m_de_casteljau_points[j].second = false;
00320         }
00321
00322       m_last_t = t;
00323     }
00324
00325   unsigned int index = get_dclj_array_index(k, i);
00326
00327   if ( m_de_casteljau_points[index].second )
00328     { return *( m_de_casteljau_points[index].first ); }
00329   else
00330     {
00331       HomPoint* p = new HomPoint();
00332       *p = de_casteljau(k-1, i, t) * (1.0 - t) + de_casteljau(k-1, i+1, t) * t;
00333       m_de_casteljau_points[index] = pair<HomPoint*, bool>(p, true);
00334       return *p;
00335     }
00336 }
00337
00338 unsigned int
00339 Bezier::get_dclj_array_index(unsigned int k, unsigned int i) const
00340 {
00341   unsigned int index = 0;
00342
00343   for (unsigned int j = 0; j < k; ++j)
00344     { index += m_num_control_points - j; }
00345
00346   index += i;
00347   index -= m_num_control_points;
00348
00349   return index;
00350 }
00351
00352 void
00353 Bezier::register_primitives()
00354 {
00355   vector<HomPoint>::iterator iter;
00356   for ( iter  = m_control_points.begin();
00357         iter != m_control_points.end();
00358         ++iter )
00359     {
00360       HomPoint& p = *iter;
00361       add_primitive( &p );
00362     }
00363 }
00364
00365 void
00366 Bezier::post_transform()
00367 {
00368   m_last_t = -1.0;
00369 }
00370
00371 } // end namespace fawkes