synfig-core/trunk/src/synfig/valuenode_animated.cpp

   1 /* === S Y N F I G ========================================================= */
   2 /*!     \file valuenode_animated.cpp
   3 **      \brief Template File
   4 **
   5 **      $Id$
   6 **
   7 **      \legal
   8 **      Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
   9 **
  10 **      This package is free software; you can redistribute it and/or
  11 **      modify it under the terms of the GNU General Public License as
  12 **      published by the Free Software Foundation; either version 2 of
  13 **      the License, or (at your option) any later version.
  14 **
  15 **      This package is distributed in the hope that it will be useful,
  16 **      but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 **      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18 **      General Public License for more details.
  19 **      \endlegal
  20 */
  21 /* ========================================================================= */
  22
  23 /* === H E A D E R S ======================================================= */
  24
  25 #ifdef USING_PCH
  26 #       include "pch.h"
  27 #else
  28 #ifdef HAVE_CONFIG_H
  29 #       include <config.h>
  30 #endif
  31
  32 #include <vector>
  33 #include <list>
  34 #include <stdexcept>
  35
  36 #include <cmath>
  37
  38 #include <ETL/bezier>
  39 #include <ETL/hermite>
  40 #include <ETL/spline>
  41 #include <ETL/handle>
  42 #include <ETL/misc>
  43
  44 #include <algorithm>
  45 #include <typeinfo>
  46
  47 #include "canvas.h"
  48 #include "general.h"
  49 #include "valuenode_animated.h"
  50 #include "valuenode_const.h"
  51 #include "exception.h"
  52 #include "gradient.h"
  53
  54 #endif
  55
  56 /* === U S I N G =========================================================== */
  57
  58 using namespace std;
  59 using namespace etl;
  60 using namespace synfig;
  61
  62 /* === M A C R O S ========================================================= */
  63
  64 // Fast binary search implementation
  65 /*
  66 template<typename I, typename T> inline I
  67 binary_find(I begin, I end, const T& value)
  68 {
  69         I iter(begin+(end-begin)/2);
  70
  71         while(end-begin>1 && !(*iter==value))
  72         {
  73                 ((*iter<value)?begin:end) = iter;
  74
  75                 iter = begin+(end-begin)/2;
  76         }
  77         return iter;
  78 }
  79 */
  80
  81 /*
  82 template<typename T> String tangent_info(T a, T b, T v)
  83 {
  84         return "...";
  85 }
  86
  87 String tangent_info(Vector a, Vector b, Vector v)
  88 {
  89         if(a==b)
  90                 return strprintf("(should be zero) T=[%f,%f], Pp=[%f,%f], Pn=[%f,%f]",v[0],v[1],a[0],a[1],b[0],b[1]);
  91         else
  92                 return strprintf("(should NOT be zero) T=[%f,%f], Pp=[%f,%f], Pn=[%f,%f]",v[0],v[1],a[0],a[1],b[0],b[1]);
  93 }
  94 */
  95
  96 template <class T>
  97 struct subtractor : public std::binary_function<T, T, T>
  98 {
  99         T operator()(const T &a,const T &b)const
 100         {
 101                 return a-b;
 102         }
 103 };
 104
 105 template <>
 106 struct subtractor<Angle> : public std::binary_function<Angle, Angle, Angle>
 107 {
 108         Angle operator()(const Angle &a,const Angle &b)const
 109         {
 110                 return a.dist(b);
 111         }
 112 };
 113
 114 template <class T>
 115 struct magnitude : public std::unary_function<float, T>
 116 {
 117         float operator()(const T &a)const
 118         {
 119                 return abs(a);
 120         }
 121 };
 122
 123 template <>
 124 struct magnitude<Angle> : public std::unary_function<float, Angle>
 125 {
 126         float operator()(const Angle &a)const
 127         {
 128                 return abs(Angle::rad(a).get());
 129         }
 130 };
 131
 132 template <>
 133 struct magnitude<Vector> : public std::unary_function<float, Vector>
 134 {
 135         float operator()(const Vector &a)const
 136         {
 137                 return a.mag();
 138         }
 139 };
 140
 141 template <>
 142 struct magnitude<Color> : public std::unary_function<float, Color>
 143 {
 144         float operator()(const Color &a)const
 145         {
 146                 return abs(a.get_y());
 147         }
 148 };
 149
 150
 151
 152
 153
 154 template <class T>
 155 struct is_angle_type
 156 {
 157         bool operator()()const
 158         {
 159                 return false;
 160         }
 161 };
 162
 163 template <>
 164 struct is_angle_type<Angle>
 165 {
 166         bool operator()()const
 167         {
 168                 return true;
 169         }
 170 };
 171
 172 /* === G L O B A L S ======================================================= */
 173
 174 /* === C L A S S E S ======================================================= */
 175
 176 template<typename T>
 177 class _Hermite : public synfig::ValueNode_Animated
 178 {
 179 public:
 180         typedef T value_type;
 181         affine_combo<value_type,Time> affine_combo_func;
 182         subtractor<value_type>  subtract_func;
 183         magnitude<value_type>   magnitude_func;
 184         is_angle_type<value_type>       is_angle;
 185 private:
 186         struct PathSegment
 187         {
 188                 is_angle_type<value_type>       is_angle;
 189                 subtractor<value_type>  subtract_func;
 190
 191                 mutable hermite<Time,Time> first;
 192                 mutable hermite<value_type,Time> second;
 193                 WaypointList::iterator start;
 194                 WaypointList::iterator end;
 195
 196                 value_type resolve(const Time &t)const
 197                 {
 198                         bool start_static(start->is_static());
 199                         bool end_static(end->is_static());
 200
 201                         if(!start_static || !end_static)
 202                         {
 203                                 //if(!start_static)
 204                                         second.p1()=start->get_value(t).get(value_type());
 205                                 if(start->get_after()==INTERPOLATION_CONSTANT || end->get_before()==INTERPOLATION_CONSTANT)
 206                                         return second.p1();
 207                                 //if(!end_static)
 208                                         second.p2()=end->get_value(t).get(value_type());
 209
 210                                 // At the moment, the only type of non-constant interpolation
 211                                 // that we support is linear.
 212                                 second.t1()=
 213                                 second.t2()=subtract_func(second.p2(),second.p1());
 214
 215                                 second.sync();
 216                         }
 217
 218                         return second(first(t));
 219                 }
 220         };
 221         typedef vector <
 222                 PathSegment
 223                 /*
 224                 pair <
 225                         hermite<Time,Time>,
 226                         hermite<value_type,Time>
 227                 >
 228                 */
 229         > curve_list_type;
 230
 231         curve_list_type curve_list;
 232
 233         // Bounds of this curve
 234         Time r,s;
 235
 236 public:
 237         ValueNode* clone(const GUID& deriv_guid)const
 238         {
 239                 { ValueNode* x(find_value_node(get_guid()^deriv_guid).get()); if(x)return x; }
 240                 _Hermite<T>* ret(new _Hermite<T>());
 241                 ret->set_guid(get_guid()^deriv_guid);
 242                 for(WaypointList::const_iterator iter=waypoint_list().begin();iter!=waypoint_list().end();++iter)
 243                         ret->add(iter->clone(deriv_guid));
 244                 return ret;
 245         }
 246
 247         _Hermite()
 248         {
 249                 set_type(ValueBase(value_type()).get_type());
 250         }
 251
 252         virtual WaypointList::iterator new_waypoint(Time t, ValueBase value)
 253         {
 254                 // Make sure we are getting data of the correct type
 255                 //if(data.type!=type)
 256                 //      return waypoint_list_type::iterator();
 257
 258                 try { find(t); throw Exception::BadTime(_("A waypoint already exists at this point in time")); } catch(Exception::NotFound) { };
 259                 Waypoint waypoint(value,t);
 260                 waypoint.set_parent_value_node(this);
 261
 262                 waypoint_list_.push_back(waypoint);
 263                 WaypointList::iterator ret=waypoint_list_.end();
 264                 --ret;
 265
 266                 if(is_angle())
 267                 {
 268                         ret->set_before(INTERPOLATION_LINEAR);
 269                         ret->set_after(INTERPOLATION_LINEAR);
 270                 }
 271
 272                 changed();
 273
 274                 return ret;
 275         }
 276
 277         virtual WaypointList::iterator new_waypoint(Time t, ValueNode::Handle value_node)
 278         {
 279                 // Make sure we are getting data of the correct type
 280                 //if(data.type!=type)
 281                 //      return waypoint_list_type::iterator();
 282                 try { find(t); throw Exception::BadTime(_("A waypoint already exists at this point in time")); } catch(Exception::NotFound) { };
 283
 284                 Waypoint waypoint(value_node,t);
 285                 waypoint.set_parent_value_node(this);
 286
 287                 waypoint_list_.push_back(waypoint);
 288                 WaypointList::iterator ret=waypoint_list_.end();
 289                 --ret;
 290
 291                 if(is_angle())
 292                 {
 293                         ret->set_before(INTERPOLATION_LINEAR);
 294                         ret->set_after(INTERPOLATION_LINEAR);
 295                 }
 296
 297                 changed();
 298
 299                 return ret;
 300         }
 301
 302         virtual void on_changed()
 303         {
 304                 ValueNode_Animated::on_changed();
 305
 306                 if(waypoint_list_.size()<=1)
 307                         return;
 308                 std::sort(waypoint_list_.begin(),waypoint_list_.end());
 309                 //waypoint_list_.sort();
 310
 311                 r=waypoint_list_.front().get_time();
 312                 s=waypoint_list_.back().get_time();
 313
 314                 curve_list.clear();
 315
 316                 WaypointList::iterator prev,iter,next=waypoint_list_.begin();
 317                 int i=0;
 318
 319                 for(iter=next++;iter!=waypoint_list_.end() && next!=waypoint_list_.end();prev=iter,iter=next++,i++)
 320                 {
 321                         typename curve_list_type::value_type curve;
 322                         WaypointList::iterator after_next(next);
 323                         ++after_next;
 324
 325                         curve.start=iter;
 326                         curve.end=next;
 327
 328                         // Set up the positions
 329                         curve.first.set_rs(iter->get_time(), next->get_time());
 330                         curve.second.set_rs(iter->get_time(), next->get_time());
 331
 332                         Waypoint::Interpolation iter_get_after(iter->get_after());
 333                         Waypoint::Interpolation next_get_after(next->get_after());
 334                         Waypoint::Interpolation iter_get_before(iter->get_before());
 335                         Waypoint::Interpolation next_get_before(next->get_before());
 336
 337                         if(is_angle())
 338                         {
 339                                 if(iter_get_after==INTERPOLATION_TCB)
 340                                         iter_get_after=INTERPOLATION_LINEAR;
 341                                 if(next_get_after==INTERPOLATION_TCB)
 342                                         next_get_after=INTERPOLATION_LINEAR;
 343                                 if(iter_get_before==INTERPOLATION_TCB)
 344                                         iter_get_before=INTERPOLATION_LINEAR;
 345                                 if(next_get_before==INTERPOLATION_TCB)
 346                                         next_get_before=INTERPOLATION_LINEAR;
 347                         }
 348
 349                         if(iter->is_static() && next->is_static())
 350                         {
 351                                 curve.second.p1()=iter->get_value().get(T());
 352                                 curve.second.p2()=next->get_value().get(T());
 353                                 if(iter_get_after==INTERPOLATION_CONSTANT || next_get_before==INTERPOLATION_CONSTANT)
 354                                 {
 355                                         // Sections must be constant on both sides.
 356                                         // NOTE: this is commented out because of some
 357                                         // user interface issues. Namely, if a section is
 358                                         // constant and the user turns off the constant on
 359                                         // one waypoint, this will end up turning it back on.
 360                                         // Confusing.
 361                                         //iter->get_after()=next->get_before()=INTERPOLATION_CONSTANT;
 362                                         curve.second.p1()=
 363                                         curve.second.p2()=iter->get_value().get(T());
 364                                         curve.second.t1()=
 365                                         curve.second.t2()=subtract_func(curve.second.p1(),curve.second.p2());
 366                                 }
 367                                 else
 368                                 {
 369                                         if(iter_get_after==INTERPOLATION_TCB && iter!=waypoint_list_.begin() && !is_angle())
 370                                         {
 371                                                 if(iter->get_before()!=INTERPOLATION_TCB && !curve_list.empty())
 372                                                 {
 373                                                         curve.second.t1()=curve_list.back().second.t2();
 374                                                 }
 375                                                 else
 376                                                 {
 377
 378                                                 const Real& t(iter->get_tension());             // Tension
 379                                                 const Real& c(iter->get_continuity());  // Continuity
 380                                                 const Real& b(iter->get_bias());                        // Bias
 381
 382                                                 // The folloing line works where the previous line fails.
 383                                                 value_type Pp; Pp=curve_list.back().second.p1();        // P_{i-1}
 384
 385                                                 const value_type& Pc(curve.second.p1());        // P_i
 386                                                 const value_type& Pn(curve.second.p2());        // P_{i+1}
 387
 388                                                 // TCB
 389                                                 value_type vect(static_cast<value_type>(subtract_func(Pc,Pp)*(((1.0-t)*(1.0+c)*(1.0+b))/2.0)+(Pn-Pc)*(((1.0-t)*(1.0-c)*(1.0-b))/2.0)));
 390
 391                                                 // Tension Only
 392                                                 //value_type vect=(value_type)((Pn-Pp)*(1.0-t));
 393
 394                                                 // Linear
 395                                                 //value_type vect=(value_type)(Pn-Pc);
 396
 397                                                 // Debugging stuff
 398                                                 //synfig::info("%d:t1: %s",i,tangent_info(Pp,Pn,vect).c_str());
 399
 400                                                 // Adjust for time
 401                                                 //vect=value_type(vect*(curve.second.get_dt()*2.0)/(curve.second.get_dt()+curve_list.back().second.get_dt()));
 402                                                 //vect=value_type(vect*(curve.second.get_dt())/(curve_list.back().second.get_dt()));
 403
 404                                                 curve.second.t1()=vect;
 405                                                 }
 406                                         }
 407                                         else if(
 408                                                 iter_get_after==INTERPOLATION_LINEAR || iter_get_after==INTERPOLATION_HALT ||
 409                                                 (iter_get_after==INTERPOLATION_TCB && iter==waypoint_list_.begin()))
 410                                         {
 411                                                 curve.second.t1()=subtract_func(curve.second.p2(),curve.second.p1());
 412                                         }
 413
 414                                         if(iter_get_before==INTERPOLATION_TCB && iter->get_after()!=INTERPOLATION_TCB && !curve_list.empty())
 415                                         {
 416                                                 curve_list.back().second.t2()=curve.second.t1();
 417                                                 curve_list.back().second.sync();
 418                                         }
 419
 420
 421                                         if(next_get_before==INTERPOLATION_TCB && after_next!=waypoint_list_.end()  && !is_angle())
 422                                         {
 423                                                 const Real &t(next->get_tension());             // Tension
 424                                                 const Real &c(next->get_continuity());  // Continuity
 425                                                 const Real &b(next->get_bias());                        // Bias
 426                                                 const value_type &Pp(curve.second.p1());        // P_{i-1}
 427                                                 const value_type &Pc(curve.second.p2());        // P_i
 428                                                 value_type Pn; Pn=after_next->get_value().get(T());     // P_{i+1}
 429
 430                                                 // TCB
 431                                                 value_type vect(static_cast<value_type>(subtract_func(Pc,Pp) * (((1.0-t)*(1.0-c)*(1.0+b))/2.0) +
 432                                                                                                                                                          (Pn-Pc) * (((1.0-t)*(1.0+c)*(1.0-b))/2.0)));
 433
 434                                                 // Tension Only
 435                                                 //value_type vect((value_type)((Pn-Pp)*(1.0-t)));
 436
 437                                                 // Linear
 438                                                 //value_type vect=(value_type)(Pc-Pp);
 439
 440                                                 // Debugging stuff
 441                                                 //synfig::info("%d:t2: %s",i,tangent_info(Pp,Pn,vect).c_str());
 442
 443                                                 // Adjust for time
 444                                                 //vect=value_type(vect*(curve.second.get_dt()*2.0)/(curve.second.get_dt()+(after_next->get_time()-next->get_time())));
 445                                                 //vect=value_type(vect*(curve.second.get_dt()/((after_next->get_time()-next->get_time()))));
 446
 447                                                 curve.second.t2()=vect;
 448                                         }
 449                                         else if(
 450                                                 next_get_before==INTERPOLATION_LINEAR || next_get_before==INTERPOLATION_HALT ||
 451                                                 (next_get_before==INTERPOLATION_TCB && after_next==waypoint_list_.end()))
 452                                         {
 453                                                 curve.second.t2()=subtract_func(curve.second.p2(),curve.second.p1());
 454                                         }
 455
 456                                         // Adjust for time
 457                                         const float timeadjust(0.5);
 458
 459                                         if(iter_get_after==INTERPOLATION_HALT)
 460                                                 curve.second.t1()*=0;
 461                                         // if this isn't the first curve
 462                                         else if(iter_get_after != INTERPOLATION_LINEAR && !curve_list.empty())
 463                                                 // adjust it for the curve that came before it
 464                                                 curve.second.t1() *=
 465                                                         //                  (time span of this curve) * 1.5
 466                                                         // -----------------------------------------------------------------
 467                                                         // ((time span of this curve) * 0.5) + (time span of previous curve)
 468                                                         (curve.second.get_dt()*(timeadjust+1)) /
 469                                                         (curve.second.get_dt()*timeadjust + curve_list.back().second.get_dt());
 470
 471                                         if(next_get_before==INTERPOLATION_HALT)
 472                                                 curve.second.t2()*=0;
 473                                         // if this isn't the last curve
 474                                         else if(next_get_before != INTERPOLATION_LINEAR && after_next!=waypoint_list_.end())
 475                                                 // adjust it for the curve that came after it
 476                                                 curve.second.t2() *=
 477                                                         //                (time span of this curve) * 1.5
 478                                                         // -------------------------------------------------------------
 479                                                         // ((time span of this curve) * 0.5) + (time span of next curve)
 480                                                         (curve.second.get_dt()*(timeadjust+1)) /
 481                                                         (curve.second.get_dt()*timeadjust+(after_next->get_time()-next->get_time()));
 482                                 } // not CONSTANT
 483                         }
 484
 485                         // Set up the time to the default stuff
 486                         curve.first.set_rs(iter->get_time(), next->get_time());
 487                         curve.first.p1()=iter->get_time();
 488                         curve.first.p2()=next->get_time();
 489                         curve.first.t1()=(curve.first.p2()-curve.first.p1())*(1.0f-iter->get_time_tension());
 490                         curve.first.t2()=(curve.first.p2()-curve.first.p1())*(1.0f-next->get_time_tension());
 491
 492
 493                         curve.first.sync();
 494                         curve.second.sync();
 495
 496                         curve_list.push_back(curve);
 497                 }
 498         }
 499
 500         virtual ValueBase operator()(Time t)const
 501         {
 502                 if(waypoint_list_.empty())
 503                         return value_type();    //! \todo Perhaps we should throw something here?
 504                 if(waypoint_list_.size()==1)
 505                         return waypoint_list_.front().get_value(t);
 506                 if(t<=r)
 507                         return waypoint_list_.front().get_value(t);
 508                 if(t>=s)
 509                         return waypoint_list_.back().get_value(t);
 510
 511                 typename curve_list_type::const_iterator iter;
 512
 513                 // This next line will set iter to the
 514                 // correct iterator for the given time.
 515                 for(iter=curve_list.begin();iter<curve_list.end() && t>=iter->first.get_s();++iter)
 516                         continue;
 517                 if(iter==curve_list.end())
 518                         return waypoint_list_.back().get_value(t);
 519                 return iter->resolve(t);
 520         }
 521 };
 522
 523
 524 template<typename T>
 525 class _Constant : public synfig::ValueNode_Animated
 526 {
 527 public:
 528         typedef T value_type;
 529
 530 private:
 531
 532         // Bounds of this curve
 533         Time r,s;
 534
 535 public:
 536         ValueNode* clone(const GUID& deriv_guid)const
 537         {
 538                 { ValueNode* x(find_value_node(get_guid()^deriv_guid).get()); if(x)return x; }
 539                 _Constant<T>* ret(new _Constant<T>());
 540                 ret->set_guid(get_guid()^deriv_guid);
 541                 for(WaypointList::const_iterator iter=waypoint_list().begin();iter!=waypoint_list().end();++iter)
 542                         ret->add(iter->clone(deriv_guid));
 543                 return ret;
 544         }
 545
 546         _Constant()
 547         {
 548                 set_type(ValueBase(value_type()).get_type());
 549         }
 550
 551         virtual WaypointList::iterator new_waypoint(Time t, ValueBase value)
 552         {
 553                 // Make sure we are getting data of the correct type
 554                 //if(data.type!=type)
 555                 //      return waypoint_list_type::iterator();
 556                 try { find(t); throw Exception::BadTime(_("A waypoint already exists at this point in time")); } catch(Exception::NotFound) { };
 557
 558                 Waypoint waypoint(value,t);
 559                 waypoint.set_parent_value_node(this);
 560
 561                 waypoint_list_.push_back(waypoint);
 562                 WaypointList::iterator ret=waypoint_list_.end();
 563                 --ret;
 564                 changed();
 565
 566                 return ret;
 567         }
 568
 569         virtual WaypointList::iterator new_waypoint(Time t, ValueNode::Handle value_node)
 570         {
 571                 // Make sure we are getting data of the correct type
 572                 //if(data.type!=type)
 573                 //      return waypoint_list_type::iterator();
 574                 try { find(t); throw Exception::BadTime(_("A waypoint already exists at this point in time")); } catch(Exception::NotFound) { };
 575
 576                 Waypoint waypoint(value_node,t);
 577                 waypoint.set_parent_value_node(this);
 578
 579                 waypoint_list_.push_back(waypoint);
 580                 WaypointList::iterator ret=waypoint_list_.end();
 581                 --ret;
 582                 changed();
 583
 584                 return ret;
 585         }
 586
 587         virtual void on_changed()
 588         {
 589                 ValueNode_Animated::on_changed();
 590
 591                 if(waypoint_list_.size()<=1)
 592                         return;
 593                 std::sort(waypoint_list_.begin(),waypoint_list_.end());
 594                 //waypoint_list_.sort();
 595                 r=waypoint_list_.front().get_time();
 596                 s=waypoint_list_.back().get_time();
 597
 598         }
 599
 600         virtual ValueBase operator()(Time t)const
 601         {
 602                 if(waypoint_list_.size()==1)
 603                         return waypoint_list_.front().get_value(t);
 604                 if(waypoint_list_.empty())
 605                         return value_type();
 606                 if(t<=r)
 607                         return waypoint_list_.front().get_value(t);
 608                 if(t>=s)
 609                         return waypoint_list_.back().get_value(t);
 610
 611                 typename WaypointList::const_iterator iter;
 612                 typename WaypointList::const_iterator next;
 613
 614                 // This next line will set iter to the
 615                 // correct iterator for the given time.
 616                 for(next=waypoint_list_.begin(),iter=next++;next!=waypoint_list_.end() && t>=next->get_time();iter=next++)
 617                         continue;
 618
 619                 return iter->get_value(t);
 620         }
 621 };
 622
 623 class _AnimBool : public synfig::ValueNode_Animated
 624 {
 625 public:
 626         typedef bool value_type;
 627
 628 private:
 629
 630         // Bounds of this curve
 631         Time r,s;
 632
 633 public:
 634         ValueNode* clone(const GUID& deriv_guid)const
 635         {
 636                 { ValueNode* x(find_value_node(get_guid()^deriv_guid).get()); if(x)return x; }
 637                 _AnimBool* ret(new _AnimBool());
 638                 ret->set_guid(get_guid()^deriv_guid);
 639                 for(WaypointList::const_iterator iter=waypoint_list().begin();iter!=waypoint_list().end();++iter)
 640                         ret->add(iter->clone(deriv_guid));
 641                 return ret;
 642         }
 643
 644         _AnimBool()
 645         {
 646                 set_type(ValueBase(value_type()).get_type());
 647         }
 648
 649         virtual WaypointList::iterator new_waypoint(Time t, ValueBase value)
 650         {
 651                 // Make sure we are getting data of the correct type
 652                 //if(data.type!=type)
 653                 //      return waypoint_list_type::iterator();
 654                 try { find(t); throw Exception::BadTime(_("A waypoint already exists at this point in time")); } catch(Exception::NotFound) { };
 655
 656
 657                 Waypoint waypoint(value,t);
 658                 waypoint.set_parent_value_node(this);
 659
 660                 waypoint_list_.push_back(waypoint);
 661                 WaypointList::iterator ret=waypoint_list_.end();
 662                 --ret;
 663                 changed();
 664
 665                 return ret;
 666         }
 667
 668         virtual WaypointList::iterator new_waypoint(Time t, ValueNode::Handle value_node)
 669         {
 670                 // Make sure we are getting data of the correct type
 671                 //if(data.type!=type)
 672                 //      return waypoint_list_type::iterator();
 673                 try { find(t); throw Exception::BadTime(_("A waypoint already exists at this point in time")); } catch(Exception::NotFound) { };
 674
 675                 Waypoint waypoint(value_node,t);
 676                 waypoint.set_parent_value_node(this);
 677
 678                 waypoint_list_.push_back(waypoint);
 679                 WaypointList::iterator ret=waypoint_list_.end();
 680                 --ret;
 681                 changed();
 682
 683                 return ret;
 684         }
 685
 686         virtual void on_changed()
 687         {
 688                 ValueNode_Animated::on_changed();
 689
 690                 if(waypoint_list_.size()<=1)
 691                         return;
 692                 std::sort(waypoint_list_.begin(),waypoint_list_.end());
 693                 //waypoint_list_.sort();
 694                 r=waypoint_list_.front().get_time();
 695                 s=waypoint_list_.back().get_time();
 696
 697         }
 698
 699         virtual ValueBase operator()(Time t)const
 700         {
 701                 if(waypoint_list_.size()==1)
 702                         return waypoint_list_.front().get_value(t);
 703                 if(waypoint_list_.empty())
 704                         return false;
 705                 if(t<r)
 706                         return waypoint_list_.front().get_value(t);
 707                 if(t>s)
 708                         return waypoint_list_.back().get_value(t);
 709
 710                 WaypointList::const_iterator iter;
 711                 WaypointList::const_iterator next;
 712
 713                 // This next line will set iter to the
 714                 // correct iterator for the given time.
 715                 for(next=waypoint_list_.begin(),iter=next++;next!=waypoint_list_.end() && t>=next->get_time();iter=next++)
 716                         if(iter->get_time()==t)
 717                                 return iter->get_value(t);
 718
 719                 if(iter->get_time()==t)
 720                         return iter->get_value(t);
 721
 722                 if(next!=waypoint_list_.end())
 723                         return iter->get_value(t).get(bool()) || next->get_value(t).get(bool());
 724                 return iter->get_value(t);
 725         }
 726 };
 727
 728 /* === M E T H O D S ======================================================= */
 729
 730 ValueNode_Animated::ValueNode_Animated()
 731 {
 732         DCAST_HACK_ENABLE();
 733 }
 734
 735 int
 736 ValueNode_Animated::find(const Time& begin,const Time& end,std::vector<Waypoint*>& selected)
 737 {
 738         Time curr_time(begin);
 739         int ret(0);
 740
 741         // try to grab first waypoint
 742         try
 743         {
 744                 WaypointList::iterator iter;
 745                 iter=find(curr_time);
 746                 selected.push_back(&*iter);
 747                 ret++;
 748         }
 749         catch(...) { }
 750
 751         try
 752         {
 753                 WaypointList::iterator iter;
 754                 while(true)
 755                 {
 756                         iter=find_next(curr_time);
 757                         curr_time=iter->get_time();
 758                         if(curr_time>=end)
 759                                 break;
 760                         selected.push_back(&*iter);
 761                         ret++;
 762                 }
 763         }
 764         catch(...) { }
 765
 766         return ret;
 767 }
 768
 769 /*
 770 void
 771 ValueNode_Animated::manipulate_time(const Time& old_begin,const Time& old_end,const Time& new_begin,const Time& new_end)
 772 {
 773 #define old_2_new(x)    (((x)-old_begin)/(old_end-old_begin)*(new_end-new_begin)+new_begin)
 774         std::vector<Waypoint*> selected;
 775         std::vector<Waypoint*>::iterator iter;
 776
 777         if(find(old_begin,old_end,selected))
 778         {
 779                 // check to make sure this operation is OK
 780                 for(iter=selected.begin();iter!=selected.end();++iter)
 781                 {
 782                         try
 783                         {
 784                                 Time new_time(old_2_new((*iter)->get_time()));
 785                                 if(new_time>=old_begin && new_time<old_end)
 786                                         continue;
 787                                 find(new_time);
 788                                 // If we found a waypoint already at that time, then
 789                                 // we need to abort
 790                                 throw Exception::BadTime(_("Waypoint Conflict"));
 791                         }
 792                         catch(Exception::NotFound) { }
 793
 794                         selected.back()->set_time(old_2_new(selected.back()->get_time()));
 795                         selected.pop_back();
 796                 }
 797
 798
 799                 while(!selected.empty())
 800                 {
 801                         selected.back()->set_time(old_2_new(selected.back()->get_time()));
 802                         selected.pop_back();
 803                 }
 804
 805                 changed();
 806         }
 807 #undef old_2_new
 808 }
 809 */
 810
 811 Waypoint
 812 ValueNode_Animated::new_waypoint_at_time(const Time& time)const
 813 {
 814         Waypoint waypoint;
 815         try
 816         {
 817                 // Trivial case, we are sitting on a waypoint
 818                 waypoint=*find(time);
 819                 waypoint.make_unique();
 820         }
 821         catch(...)
 822         {
 823                 if(waypoint_list().empty())
 824                 {
 825                         waypoint.set_value((*this)(time));
 826                 }
 827                 else
 828                 {
 829                         WaypointList::const_iterator prev;
 830                         WaypointList::const_iterator next;
 831
 832                         bool has_prev(false), has_next(false);
 833
 834                         try { prev=find_prev(time); has_prev=true; } catch(...) { }
 835                         try { next=find_next(time); has_next=true; } catch(...) { }
 836
 837                         /*
 838                         WaypointList::const_iterator closest;
 839
 840                         if(has_prev&&!has_next)
 841                                 closest=prev;
 842                         else if(has_next&&!has_prev)
 843                                 closest=next;
 844                         else if(time-prev->get_time()<next->get_time()-time)
 845                                 closest=prev;
 846                         else
 847                                 closest=next;
 848
 849                         for(iter=waypoint_list().begin();iter!=waypoint_list().end();++iter)
 850                         {
 851                                 const Real dist(abs(iter->get_time()-time));
 852                                 if(dist<abs(closest->get_time()-time))
 853                                         closest=iter;
 854                         }
 855                         */
 856
 857                         if(has_prev && !prev->is_static())
 858                                 waypoint.set_value_node(prev->get_value_node());
 859                         if(has_next && !next->is_static())
 860                                 waypoint.set_value_node(next->get_value_node());
 861                         else
 862                                 waypoint.set_value((*this)(time));
 863
 864                         /*if(has_prev)
 865                                 waypoint.set_after(prev->get_before());
 866                         if(has_next)
 867                                 waypoint.set_before(next->get_after());
 868                         */
 869                 }
 870         }
 871         waypoint.set_time(time);
 872         waypoint.set_parent_value_node(const_cast<ValueNode_Animated*>(this));
 873 //      synfig::info("waypoint.get_after()=set to %d",waypoint.get_after());
 874 //      synfig::info("waypoint.get_before()=set to %d",waypoint.get_before());
 875
 876         return waypoint;
 877 }
 878
 879 ValueNode_Animated::WaypointList::iterator
 880 ValueNode_Animated::find(const UniqueID &x)
 881 {
 882         ValueNode_Animated::WaypointList::iterator iter;
 883         iter=std::find(waypoint_list().begin(),waypoint_list().end(),x);
 884         if(iter==waypoint_list().end() || iter->get_uid()!=x.get_uid())
 885                 throw Exception::NotFound(strprintf("ValueNode_Animated::find(): Can't find UniqueID %d",x.get_uid()));
 886         return iter;
 887 }
 888
 889 ValueNode_Animated::WaypointList::const_iterator
 890 ValueNode_Animated::find(const UniqueID &x)const
 891 {
 892         return const_cast<ValueNode_Animated*>(this)->find(x);
 893         /*
 894         ValueNode_Animated::WaypointList::const_iterator iter;
 895         iter=std::find(waypoint_list().begin(),waypoint_list().end(),x);
 896         if(iter!=waypoint_list().end() && iter->get_uid()!=x.get_uid())
 897                 throw Exception::NotFound(strprintf("ValueNode_Animated::find()const: Can't find UniqueID %d",x.get_uid()));
 898         return iter;
 899         */
 900 }
 901
 902 ValueNode_Animated::WaypointList::iterator
 903 ValueNode_Animated::find(const Time &x)
 904 {
 905         WaypointList::iterator iter(binary_find(waypoint_list().begin(),waypoint_list().end(),x));
 906
 907         if(iter!=waypoint_list().end() && x.is_equal(iter->get_time()))
 908                 return iter;
 909
 910         throw Exception::NotFound(strprintf("ValueNode_Animated::find(): Can't find Waypoint at %s",x.get_string().c_str()));
 911 }
 912
 913 ValueNode_Animated::WaypointList::const_iterator
 914 ValueNode_Animated::find(const Time &x)const
 915 {
 916         return const_cast<ValueNode_Animated*>(this)->find(x);
 917         /*
 918         WaypointList::const_iterator iter(binary_find(waypoint_list().begin(),waypoint_list().end(),x));
 919
 920         if(iter!=waypoint_list().end() && x.is_equal(iter->get_time()))
 921                 return iter;
 922
 923         throw Exception::NotFound(strprintf("ValueNode_Animated::find(): Can't find Waypoint at %s",x.get_string().c_str()));
 924         */
 925 }
 926
 927 ValueNode_Animated::WaypointList::iterator
 928 ValueNode_Animated::find_next(const Time &x)
 929 {
 930         WaypointList::iterator iter(binary_find(waypoint_list().begin(),waypoint_list().end(),x));
 931
 932         if(iter!=waypoint_list().end())
 933         {
 934                 if(iter->get_time().is_more_than(x))
 935                         return iter;
 936                 ++iter;
 937                 if(iter!=waypoint_list().end() && iter->get_time().is_more_than(x))
 938                         return iter;
 939         }
 940
 941         throw Exception::NotFound(strprintf("ValueNode_Animated::find_next(): Can't find Waypoint after %s",x.get_string().c_str()));
 942 }
 943
 944 ValueNode_Animated::WaypointList::const_iterator
 945 ValueNode_Animated::find_next(const Time &x)const
 946 {
 947         return const_cast<ValueNode_Animated*>(this)->find_next(x);
 948         /*
 949         WaypointList::const_iterator iter(binary_find(waypoint_list().begin(),waypoint_list().end(),x));
 950
 951         if(iter!=waypoint_list().end())
 952         {
 953                 if(iter->get_time()-Time::epsilon()>x)
 954                         return iter;
 955                 ++iter;
 956                 if(iter!=waypoint_list().end() && iter->get_time()-Time::epsilon()>x)
 957                         return iter;
 958         }
 959
 960         throw Exception::NotFound(strprintf("ValueNode_Animated::find_next(): Can't find Waypoint after %s",x.get_string().c_str()));
 961 */
 962 }
 963
 964 ValueNode_Animated::WaypointList::iterator
 965 ValueNode_Animated::find_prev(const Time &x)
 966 {
 967         WaypointList::iterator iter(binary_find(waypoint_list().begin(),waypoint_list().end(),x));
 968
 969         if(iter!=waypoint_list().end())
 970         {
 971                 if(iter->get_time().is_less_than(x))
 972                         return iter;
 973                 if(iter!=waypoint_list().begin() && (--iter)->get_time().is_less_than(x))
 974                         return iter;
 975         }
 976
 977         throw Exception::NotFound(strprintf("ValueNode_Animated::find_prev(): Can't find Waypoint after %s",x.get_string().c_str()));
 978 }
 979
 980 ValueNode_Animated::WaypointList::const_iterator
 981 ValueNode_Animated::find_prev(const Time &x)const
 982 {
 983         return const_cast<ValueNode_Animated*>(this)->find_prev(x);
 984         /*
 985         WaypointList::const_iterator iter(binary_find(waypoint_list().begin(),waypoint_list().end(),x));
 986
 987         if(iter!=waypoint_list().end())
 988         {
 989                 if(iter->get_time()+Time::epsilon()<x)
 990                         return iter;
 991                 if(iter!=waypoint_list().begin() && (--iter)->get_time()+Time::epsilon()<x)
 992                         return iter;
 993         }
 994         throw Exception::NotFound(strprintf("ValueNode_Animated::find_prev(): Can't find Waypoint after %s",x.get_string().c_str()));
 995         */
 996 }
 997
 998 void
 999 ValueNode_Animated::erase(const UniqueID &x)
1000 {
1001         waypoint_list().erase(find(x));
1002 }
1003
1004 ValueNode_Animated::WaypointList::iterator
1005 ValueNode_Animated::add(const Waypoint &x)
1006 {
1007         Waypoint waypoint(x);
1008         waypoint.set_parent_value_node(this);
1009         waypoint_list_.push_back(waypoint);
1010         //assert(waypoint_list_.back().get_parent_value_node()==this);
1011         WaypointList::iterator ret=waypoint_list_.end();
1012         --ret;
1013         changed();
1014         return ret;
1015 }
1016
1017 void
1018 ValueNode_Animated::set_type(ValueBase::Type t)
1019 {
1020         ValueNode::set_type(t);
1021 }
1022
1023 ValueNode_Animated::Handle
1024 synfig::ValueNode_Animated::create(ValueBase::Type type)
1025 {
1026         switch(type)
1027         {
1028                 case ValueBase::TYPE_TIME:
1029                         return ValueNode_Animated::Handle(new _Hermite<Time>);
1030                 case ValueBase::TYPE_REAL:
1031                         return ValueNode_Animated::Handle(new _Hermite<Vector::value_type>);
1032                 case ValueBase::TYPE_INTEGER:
1033                         return ValueNode_Animated::Handle(new _Hermite<int>);
1034                 case ValueBase::TYPE_ANGLE:
1035                         return ValueNode_Animated::Handle(new _Hermite<Angle>);
1036                 case ValueBase::TYPE_VECTOR:
1037                         return ValueNode_Animated::Handle(new _Hermite<Vector>);
1038                 case ValueBase::TYPE_COLOR:
1039                         return ValueNode_Animated::Handle(new _Hermite<Color>);
1040
1041                 case ValueBase::TYPE_STRING:
1042                         return ValueNode_Animated::Handle(new _Constant<String>);
1043                 case ValueBase::TYPE_GRADIENT:
1044                         return ValueNode_Animated::Handle(new _Hermite<Gradient>);
1045                 case ValueBase::TYPE_BOOL:
1046                         return ValueNode_Animated::Handle(new _AnimBool);
1047                 case ValueBase::TYPE_CANVAS:
1048                         return ValueNode_Animated::Handle(new _Constant<Canvas::LooseHandle>);
1049                 default:
1050                         throw
1051                                 Exception::BadType(strprintf(_("%s: You cannot use a %s in an animated ValueNode"),"synfig::ValueNode_Animated::create()",
1052                                         ValueBase::type_name(type).c_str())
1053                                 );
1054                         break;
1055         }
1056         return ValueNode_Animated::Handle();
1057 }
1058
1059 ValueNode_Animated::Handle
1060 ValueNode_Animated::create(const ValueBase& value, const Time& time)
1061 {
1062         return create(ValueNode::Handle(ValueNode_Const::create(value)),time);
1063 }
1064
1065 ValueNode_Animated::Handle
1066 ValueNode_Animated::create(ValueNode::Handle value_node, const Time& time)
1067 {
1068         ValueNode_Animated::Handle ret(create(value_node->get_type()));
1069         ret->new_waypoint(time,value_node);
1070         return ret;
1071 }
1072
1073 ValueNode_Animated::~ValueNode_Animated()
1074 {
1075 }
1076
1077 String
1078 ValueNode_Animated::get_name()const
1079 {
1080         return "animated";
1081 }
1082
1083 String
1084 ValueNode_Animated::get_local_name()const
1085 {
1086         return _("Animated");
1087 }
1088
1089 void ValueNode_Animated::get_times_vfunc(Node::time_set &set) const
1090 {
1091         //add all the way point times to the value node...
1092
1093         WaypointList::const_iterator    i = waypoint_list().begin(),
1094                                                                         end = waypoint_list().end();
1095
1096         for(; i != end; ++i)
1097         {
1098                 TimePoint t;
1099                 t.set_time(i->get_time());
1100                 t.set_before(i->get_before());
1101                 t.set_after(i->get_after());
1102                 t.set_guid(i->get_guid());
1103                 set.insert(t);
1104         }
1105 }
1106 struct timecmp
1107  {
1108         Time t;
1109
1110         timecmp(const Time &c) :t(c) {}
1111
1112         bool operator()(const Waypoint &rhs) const
1113         {
1114                 return t.is_equal(rhs.get_time());
1115         }
1116  };
1117
1118  ValueNode_Animated::findresult
1119  ValueNode_Animated::find_uid(const UniqueID &x)
1120  {
1121         findresult      f;
1122         f.second = false;
1123
1124         //search for it... and set the bool part of the return value to true if we found it!
1125         f.first = std::find(waypoint_list_.begin(), waypoint_list_.end(), x);
1126         if(f.first != waypoint_list_.end())
1127                 f.second = true;
1128
1129         return f;
1130  }
1131
1132  ValueNode_Animated::const_findresult
1133  ValueNode_Animated::find_uid(const UniqueID &x)const
1134  {
1135         const_findresult        f;
1136         f.second = false;
1137
1138         //search for it... and set the bool part of the return value to true if we found it!
1139         f.first = std::find(waypoint_list_.begin(), waypoint_list_.end(), x);
1140         if(f.first != waypoint_list_.end())
1141                 f.second = true;
1142
1143         return f;
1144  }
1145
1146  ValueNode_Animated::findresult
1147  ValueNode_Animated::find_time(const Time &x)
1148  {
1149         findresult      f;
1150         f.second = false;
1151
1152         //search for it... and set the bool part of the return value to true if we found it!
1153         f.first = std::find_if(waypoint_list_.begin(), waypoint_list_.end(), timecmp(x));
1154         if(f.first != waypoint_list_.end())
1155                 f.second = true;
1156
1157         return f;
1158  }
1159
1160 ValueNode_Animated::const_findresult
1161 ValueNode_Animated::find_time(const Time &x)const
1162 {
1163         const_findresult        f;
1164         f.second = false;
1165
1166         //search for it... and set the bool part of the return value to true if we found it!
1167         f.first = std::find_if(waypoint_list_.begin(), waypoint_list_.end(), timecmp(x));
1168         if(f.first != waypoint_list_.end())
1169                 f.second = true;
1170
1171         return f;
1172 }
1173
1174 void
1175 ValueNode_Animated::insert_time(const Time& location, const Time& delta)
1176 {
1177         if(!delta)
1178                 return;
1179         try
1180         {
1181                 WaypointList::iterator iter(find_next(location));
1182                 for(;iter!=waypoint_list().end();++iter)
1183                 {
1184                         iter->set_time(iter->get_time()+delta);
1185                 }
1186                 changed();
1187         }
1188         catch(Exception::NotFound) { }
1189 }