Fawkes API  Fawkes Development Version
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
bezier.cpp
1 
2 /***************************************************************************
3  * bezier.cpp - Bezier curve
4  *
5  * Created: Mon Oct 06 15:14:53 2008
6  * Copyright 2008 Daniel Beck
7  *
8  ****************************************************************************/
9 
10 /* This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version. A runtime exception applies to
14  * this software (see LICENSE.GPL_WRE file mentioned below for details).
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU Library General Public License for more details.
20  *
21  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
22  */
23 
24 #include <geometry/bezier.h>
25 #include <geometry/hom_point.h>
26 #include <geometry/hom_vector.h>
27 
28 using namespace std;
29 
30 namespace fawkes {
31 
32 /** @class fawkes::Bezier <geometry/bezier.h>
33  * A Bezier curve class.
34  * @author Daniel Beck
35  */
36 
37 /** Constructor. */
38 Bezier::Bezier()
39 {
40  m_de_casteljau_points = NULL;
41  m_last_t = -1.0;
42  m_num_subdivisions = 0;
43 
44  register_primitives();
45 }
46 
47 /** Constructor.
48  * @param control_points the control points for the Bezier curve
49  */
50 Bezier::Bezier(const vector<HomPoint>& control_points)
51  : m_control_points(control_points)
52 {
53  m_num_control_points = m_control_points.size();
54 
55  m_de_casteljau_points = NULL;
56  init_dclj_array();
57 
58  m_last_t = -1.0;
59  m_num_subdivisions = 0;
60 
62 }
63 
64 /** Copy constructor.
65  * @param b another Bezier curve
66  */
68  : m_control_points(b.m_control_points)
69 {
70  m_num_control_points = b.m_num_control_points;
71  m_de_casteljau_points = NULL;
72  init_dclj_array();
73 
74  m_last_t = -1.0;
75  m_num_subdivisions = 0;
76 
79 }
80 
81 /** Destructor. */
83 {
84  for (unsigned int i = 0; i < m_dclj_array_size; ++i)
85  { delete m_de_casteljau_points[i].first; }
86 
87  delete[] m_de_casteljau_points;
88 }
89 
90 /** Set the control points.
91  * @param control_points the new control points
92  */
93 void
94 Bezier::set_control_points(const vector<HomPoint>& control_points)
95 {
96  m_control_points.clear();
97  m_control_points = control_points;
98 
99  m_num_control_points = m_control_points.size();
100 
101  m_last_t = -1.0;
102 
103  init_dclj_array();
104 
107 }
108 
109 void
110 Bezier::init_dclj_array()
111 {
112  m_dclj_array_size = m_num_control_points * (m_num_control_points + 1) / 2;
113  m_dclj_array_size -= m_num_control_points;
114 
115  delete m_de_casteljau_points;
116  m_de_casteljau_points = new pair<HomPoint*, bool>[m_dclj_array_size];
117 
118  for (unsigned int i = 0; i < m_dclj_array_size; ++i)
119  {
120  m_de_casteljau_points[i].first = NULL;
121  m_de_casteljau_points[i].second = false;
122  }
123 }
124 
125 /** Replace a specific control point.
126  * @param index the index of the control point
127  * @param control_point the replacement control point
128  */
129 void
130 Bezier::set_control_point(unsigned int index, const HomPoint& control_point)
131 {
132  m_control_points[index] = control_point;
133  m_de_casteljau_points[index] = pair<HomPoint*, bool>( &(m_control_points[index]), true );
134 
135  m_last_t = -1.0;
136 
139 }
140 
141 /** Get the control points.
142  * @return a copy of the control points
143  */
144 std::vector<HomPoint>
146 {
147  return m_control_points;
148 }
149 
150 /** Get a specific control point.
151  * @param i the index of the control point
152  * @return control point
153  */
154 HomPoint
155 Bezier::get_control_point(unsigned int i) const
156 {
157  if (i < m_num_control_points)
158  { return m_control_points.at(i); }
159  else
160  { throw exception(); }
161 }
162 
163 /** Get the degree of the polynom.
164  * @return the degree of the polynom
165  */
166 unsigned int
168 {
169  return m_num_control_points - 1;
170 }
171 
172 /** Evalutate the polynom for a given t
173  * @param t a value between 0.0 and 1.0
174  * @return the corresponding point on the curve
175  */
176 HomPoint
177 Bezier::eval(float t)
178 {
179  if ( t < 0 || t > 1)
180  { throw exception(); }
181 
182  return de_casteljau(m_num_control_points - 1, 0, t);
183 }
184 
185 /** Compute the tangent vector at position t.
186  * @param t the curve parameter
187  * @return the tangent vector
188  */
189 HomVector
191 {
192  HomVector v;
193  HomPoint b0 = de_casteljau(m_num_control_points - 2, 0, t);
194  HomPoint b1 = de_casteljau(m_num_control_points - 2, 1, t);
195  v = b1 - b0;
196 
197  return v;
198 }
199 
200 /** Compute the tangent vector at the specified control point.
201  * @param index the index of the control point
202  * @return the tangent vector
203  */
204 HomVector
205 Bezier::tangent_at_point(unsigned int index)
206 {
207  float t;
208  if (index > m_num_control_points)
209  { t = 1.0; }
210  else
211  { t = index / (float) m_num_control_points; }
212 
213  return tangent_at_t(t);
214 }
215 
216 /** Subdivide the curve into two polynome of the same degree.
217  * @param t determines the point where the curve is divided
218  * @param c the Bezier for the part [0, t]
219  * @param d the Bezier for the part [t, 1]
220  */
221 void
223 {
224  if ( t < 0 || t > 1 )
225  { throw exception(); }
226 
227  vector<HomPoint> control_points;
228 
229  for (unsigned k = 0; k < m_num_control_points; ++k)
230  {
231  HomPoint p = de_casteljau(k, 0, t);
232  control_points.push_back(p);
233  }
234 
235  c.set_control_points(control_points);
236  control_points.clear();
237 
238  for (unsigned i = 0; i < m_num_control_points; ++i)
239  {
240  unsigned int k = m_num_control_points - i - 1;
241  HomPoint p = de_casteljau(k, i, t);
242  control_points.push_back(p);
243  }
244 
245  d.set_control_points(control_points);
246 }
247 
248 /** Approximate the curve with points.
249  * @param num_subdivisions the number of subdivisions that is performed
250  * @return the point approximating the curve
251  */
252 const vector<HomPoint>&
253 Bezier::approximate(unsigned int num_subdivisions)
254 {
255  if (m_num_subdivisions == num_subdivisions)
256  { return m_approximation; }
257 
258  vector<Bezier> b1;
259  vector<Bezier> b2;
260 
261  b1.push_back( *this );
262 
263  for (unsigned int i = 0; i < num_subdivisions; ++i)
264  {
265  b2.clear();
266 
267  for ( vector<Bezier>::iterator iter = b1.begin();
268  iter != b1.end();
269  ++iter )
270  {
271  Bezier c, d;
272  iter->subdivide(0.5, c, d);
273  b2.push_back(c);
274  b2.push_back(d);
275  }
276 
277  b1.clear();
278  b1 = b2;
279  }
280 
281  for ( vector<Bezier>::iterator bit = b2.begin();
282  bit != b2.end();
283  ++bit )
284  {
285  vector<HomPoint> points = bit->get_control_points();
286 
287  vector<HomPoint>::iterator pit = points.begin();
288 
289  if ( bit != b2.begin() )
290  // skip first control point for all Bezier curves except for
291  // the first one
292  { ++pit; }
293 
294  for ( vector<HomPoint>::iterator iter = pit;
295  iter != points.end();
296  ++iter )
297  { m_approximation.push_back( *iter); }
298  }
299 
300  m_num_subdivisions = num_subdivisions;
301 
302  return m_approximation;
303 }
304 
305 HomPoint
306 Bezier::de_casteljau(unsigned int k, unsigned int i, float t)
307 {
308  if (0 == k)
309  { return m_control_points.at(i); }
310 
311  if (m_last_t != t)
312  {
313  for ( unsigned int j = 0;
314  j < m_dclj_array_size;
315  ++j )
316  {
317  delete m_de_casteljau_points[j].first;
318 
319  m_de_casteljau_points[j].first = NULL;
320  m_de_casteljau_points[j].second = false;
321  }
322 
323  m_last_t = t;
324  }
325 
326  unsigned int index = get_dclj_array_index(k, i);
327 
328  if ( m_de_casteljau_points[index].second )
329  { return *( m_de_casteljau_points[index].first ); }
330  else
331  {
332  HomPoint* p = new HomPoint();
333  *p = de_casteljau(k-1, i, t) * (1.0 - t) + de_casteljau(k-1, i+1, t) * t;
334  m_de_casteljau_points[index] = pair<HomPoint*, bool>(p, true);
335  return *p;
336  }
337 }
338 
339 unsigned int
340 Bezier::get_dclj_array_index(unsigned int k, unsigned int i) const
341 {
342  unsigned int index = 0;
343 
344  for (unsigned int j = 0; j < k; ++j)
345  { index += m_num_control_points - j; }
346 
347  index += i;
348  index -= m_num_control_points;
349 
350  return index;
351 }
352 
353 void
355 {
356  vector<HomPoint>::iterator iter;
357  for ( iter = m_control_points.begin();
358  iter != m_control_points.end();
359  ++iter )
360  {
361  HomPoint& p = *iter;
362  add_primitive( &p );
363  }
364 }
365 
366 void
368 {
369  m_last_t = -1.0;
370 }
371 
372 } // end namespace fawkes