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