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

   1 /* === S Y N F I G ========================================================= */
   2 /*!     \file gradient.cpp
   3 **      \brief Color Gradient Class Member Definitions
   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 "gradient.h"
  33 #include "general.h"
  34 #include <stdexcept>
  35 #include "exception.h"
  36 #include <algorithm>
  37
  38 #include <ETL/misc>
  39 #endif
  40
  41 /* === U S I N G =========================================================== */
  42
  43 using namespace std;
  44 using namespace etl;
  45 using namespace synfig;
  46
  47 /* === M A C R O S ========================================================= */
  48
  49 /* === G L O B A L S ======================================================= */
  50
  51 /* === P R O C E D U R E S ================================================= */
  52
  53 /* === M E T H O D S ======================================================= */
  54
  55 synfig::Gradient::Gradient(const Color &c1, const Color &c2)
  56 {
  57         push_back(CPoint(0.0,c1));
  58         push_back(CPoint(1.0,c2));
  59 }
  60
  61 synfig::Gradient::Gradient(const Color &c1, const Color &c2, const Color &c3)
  62 {
  63         push_back(CPoint(0.0,c1));
  64         push_back(CPoint(0.5,c2));
  65         push_back(CPoint(1.0,c3));
  66 }
  67
  68 // This sort algorithm MUST be stable
  69 // ie: it must not change the order of items with the same value.
  70 // I am using a bubble sort.
  71 // This algorithm will sort a nearly-sorted list at ~O(N), and
  72 // it will sort an inverse sorted list at ~O(N*N).
  73 void
  74 synfig::Gradient::sort()
  75 {
  76         stable_sort(begin(),end());
  77         /*
  78         iterator iter;
  79         iterator iter2,next;
  80
  81         for(iter=begin();iter!=end();iter++)
  82         {
  83                 for(next=iter, iter2=next--;iter2!=begin();iter2=next--)
  84                 {
  85                         if(*iter<*next)
  86                         {
  87                                 //insert(next,*iter);
  88                                 //erase(iter);
  89                                 iter_swap(next,iter);
  90
  91                                 continue;
  92                         }
  93                         else
  94                                 break;
  95                 }
  96         }
  97         */
  98 }
  99
 100 static synfig::ColorAccumulator
 101 supersample_helper(const synfig::Gradient::CPoint &color1, const synfig::Gradient::CPoint &color2, float begin, float end, float &weight)
 102 {
 103         if(color1.pos==color2.pos || color1.pos>=end || color2.pos<=begin)
 104         {
 105                 weight=0;
 106                 return Color::alpha();
 107         }
 108         if(color1.pos>=begin && color2.pos<end)
 109         {
 110                 weight=color2.pos-color1.pos;
 111                 ColorAccumulator ret=Color::blend(color2.color,color1.color, 0.5, Color::BLEND_STRAIGHT).premult_alpha()*weight;
 112                 return ret;
 113         }
 114         if(color1.pos>=begin && color2.pos>=end)
 115         {
 116                 weight=end-color1.pos;
 117                 float pos((end+color1.pos)*0.5);
 118                 float amount((pos-color1.pos)/(color2.pos-color1.pos));
 119                 //if(abs(amount)>1)amount=(amount>0)?1:-1;
 120                 ColorAccumulator ret(Color::blend(color2.color,color1.color, amount, Color::BLEND_STRAIGHT).premult_alpha()*weight);
 121                 return ret;
 122         }
 123         if(color1.pos<begin && color2.pos<end)
 124         {
 125                 weight=color2.pos-begin;
 126                 float pos((begin+color2.pos)*0.5);
 127                 float amount((pos-color1.pos)/(color2.pos-color1.pos));
 128                 //if(abs(amount)>1)amount=(amount>0)?1:-1;
 129                 ColorAccumulator ret(Color::blend(color2.color,color1.color, amount, Color::BLEND_STRAIGHT).premult_alpha()*weight);
 130                 return ret;
 131         }
 132         synfig::error("color1.pos=%f",color1.pos);
 133         synfig::error("color2.pos=%f",color2.pos);
 134         synfig::error("begin=%f",begin);
 135         synfig::error("end=%f",end);
 136
 137         weight=0;
 138         return Color::alpha();
 139
 140 //      assert(0);
 141 }
 142
 143 static void show_gradient(const Gradient::CPointList x) {
 144         int i = 0;
 145         for (Gradient::const_iterator iter = x.begin(); iter != x.end(); iter++) {
 146                 printf("%3d : %.3f %s\n", i++, (*iter).pos, (*iter).color.get_string().c_str());
 147         }
 148 }
 149
 150 Gradient &
 151 synfig::Gradient::operator+=(const Gradient &rhs)
 152 {
 153         bool print=false;                       // for debugging
 154         if (print) { printf("\nadding lhs:\n"); show_gradient(this->cpoints); printf("\n"); }
 155         if (print) { printf("adding rhs:\n"); show_gradient(rhs.cpoints); printf("\n"); }
 156         CPointList ret;
 157         const_iterator iter1 = begin(), iter2 = rhs.begin(), left_same, right_same;
 158         CPoint left, right;
 159         if (iter1 != end()) left = *iter1;
 160         if (iter2 != rhs.end()) right = *iter2;
 161         int pos1 = 0, pos2 = 0;
 162         CPoint old1, old2;
 163
 164         // if there are cpoints in both gradients run through both until one runs out
 165         if (iter1 != end() && iter2 != rhs.end())
 166                 while(true)
 167                 {
 168                         // if the left one has the first cpoint
 169                         if (left.pos < right.pos)
 170                         {
 171                                 // add on the right gradient's value at this point
 172                                 if (print) printf("using pos %.2f from left %d in loop\n", left.pos, pos1++);
 173                                 ret.push_back(CPoint(left.pos, left.color + rhs(left.pos)));
 174                                 if(++iter1 == end()) break;
 175                                 left=*iter1;
 176                         }
 177                         // if the right one has the first cpoint
 178                         else if (left.pos > right.pos)
 179                         {
 180                                 // add on the left gradient's value at this point
 181                                 if (print) printf("using pos %.2f from right %d in loop\n", right.pos, pos2++);
 182                                 ret.push_back(CPoint(right.pos, right.color + (*this)(right.pos)));
 183                                 if(++iter2 == rhs.end()) break;
 184                                 right=*iter2;
 185                         }
 186                         // they both have a cpoint at the same time
 187                         else
 188                         {
 189                                 int tpos1 = pos1, tpos2 = pos2;
 190                                 // skip past all cpoints at the same position
 191                                 for(left_same = ++iter1; iter1 != end() && (*iter1).pos == left.pos; iter1++, pos1++)
 192                                 {
 193                                         if (print) printf("skipping past pos %d in left\n", pos1);
 194                                 }
 195                                 for(right_same = ++iter2; iter2 != rhs.end() && (*iter2).pos == right.pos; iter2++, pos2++)
 196                                 {
 197                                         if (print) printf("skipping past pos %d in right\n", pos2);
 198                                 }
 199
 200                                 // if the is only one cpoint at this position in each gradient,
 201                                 // there's only one corresponding cpoint in the sum
 202                                 if (iter1 == left_same && iter2 == right_same) {
 203                                         if (print) printf("two singles at left %d and right %d\n", pos1++, pos2++);
 204                                         ret.push_back(CPoint(left.pos, left.color + right.color));
 205                                 }
 206                                 // otherwise we sum the first in each, and the last in each
 207                                 else
 208                                 {
 209                                         if (print) printf("[copying %d from left %d and %d from right %d at %.2f]\n", iter1-left_same+1, tpos1, iter2-right_same+1, tpos2, left.pos);
 210                                         // merge the front two cpoints
 211                                         if (print) printf("  copy front from left %d right %d\n", tpos1++, tpos2++);
 212                                         ret.push_back(CPoint(left.pos, left.color + right.color));
 213
 214                                         // merge the middle pairs points - each middle point merges with its counterpart
 215                                         while(left_same < iter1-1 && right_same < iter2-1)
 216                                         {
 217                                                 old1 = *(left_same++);
 218                                                 old2 = *(right_same++);
 219                                                 if (print) printf("  copy middle from left %d and right %d\n", tpos1++, tpos2++);
 220                                                 ret.push_back(CPoint(old1.pos, old1.color+old2.color));
 221                                         }
 222                                         // if one gradient has more middle points than the other, merge the rest with the last point in the other gradient
 223                                         for(old2 = (*(iter2-1)); left_same < iter1-1; left_same++)
 224                                         {
 225                                                 old1 = *left_same;
 226                                                 if (print) printf("  copy middle from left %d plus end of right\n", tpos1++);
 227                                                 ret.push_back(CPoint(old1.pos, old1.color + old2.color));
 228                                         }
 229                                         for(old1 = (*(iter1-1)); right_same < iter2-1; right_same++)
 230                                         {
 231                                                 old2 = *right_same;
 232                                                 if (print) printf("  copy middle from right %d plus end of left\n", tpos2++);
 233                                                 ret.push_back(CPoint(old2.pos, old1.color + old2.color));
 234                                         }
 235                                         // merge the back two cpoints
 236                                         if (print) printf("  copy end from left %d right %d\n", pos1++, pos2++);
 237                                         ret.push_back(CPoint(left.pos, (*(iter1-1)).color + (*(iter2-1)).color));
 238                                 }
 239                                 // make sure we update 'left' and 'right'
 240                                 if (iter1 != end()) left=*iter1;
 241                                 if (iter2 == rhs.end()) break;
 242                                 right = *iter2;
 243                                 if (iter1 == end()) break;
 244                         }
 245                 }
 246
 247         // one of the gradients has run out of points
 248         // does the left one have points left?
 249         if (iter1 != end())
 250                 while(true)
 251                 {
 252                         if (print) printf("finish end from left %d\n", pos1++);
 253                         ret.push_back(CPoint(left.pos, left.color + rhs(left.pos)));
 254                         if(++iter1 == end()) break;
 255                         left = *iter1;
 256                 }
 257         // the left one was empty, so maybe the right one has points left
 258         else if (iter2 != rhs.end())
 259                 while(true)
 260                 {
 261                         if (print) printf("finish end from right %d\n", pos2++);
 262                         ret.push_back(CPoint(right.pos, right.color + (*this)(right.pos)));
 263                         if(++iter2 == rhs.end()) break;
 264                         right = *iter2;
 265                 }
 266
 267         if (print) { printf("\nsummed ret:\n"); show_gradient(ret); printf("\n"); }
 268         cpoints = ret;
 269         return *this;
 270 }
 271
 272 Gradient &
 273 synfig::Gradient::operator-=(const Gradient &rhs)
 274 {
 275         return (*this)+=(rhs*-1);
 276 }
 277
 278 Gradient &
 279 synfig::Gradient::operator*=(const float    &rhs)
 280 {
 281         if (rhs == 0)
 282                 cpoints.clear();
 283         else
 284                 for (iterator iter = cpoints.begin(); iter!=cpoints.end(); iter++)
 285                         (*iter).color *= rhs;
 286         return *this;
 287 }
 288
 289 Gradient &
 290 synfig::Gradient::operator/=(const float    &rhs)
 291 {
 292         for (iterator iter = cpoints.begin(); iter!=cpoints.end(); iter++)
 293                 (*iter).color /= rhs;
 294         return *this;
 295 }
 296
 297 Color
 298 synfig::Gradient::operator()(const Real &x,float supersample)const
 299 {
 300         if(cpoints.empty())
 301                 return Color(0,0,0,0);
 302         if(supersample<0)
 303                 supersample=-supersample;
 304         if(supersample>2.0)
 305                 supersample=2.0f;
 306
 307         float begin_sample(x-supersample*0.5);
 308         float end_sample(x+supersample*0.5);
 309
 310         if(cpoints.size()==1 || end_sample<=cpoints.front().pos || isnan(x))
 311                 return cpoints.front().color;
 312
 313         if(begin_sample>=cpoints.back().pos)
 314                 return cpoints.back().color;
 315
 316         /*
 317         if(end_sample>=back().pos)
 318                 end_sample=back().pos;
 319
 320         if(begin_sample<=front().pos)
 321                 begin_sample=front().pos;
 322         */
 323
 324         const_iterator iter,next;
 325
 326         /*
 327         //optimizize...
 328         Real    left = x-supersample/2, right = x+supersample/2;
 329
 330         if(left < front().pos) left = front().pos;
 331         if(right > back().pos) right = back().pos;
 332
 333         //find using binary search...
 334         const_iterator iterl,iterr;
 335
 336         //the binary search should give us the values BEFORE the point we're looking for...
 337         iterl = binary_find(begin(),end(),left);
 338         iterr = binary_find(iterl,end(),right);
 339
 340         //now integrate over the range of left to right...
 341
 342         if(iterl == iterr)
 343         {
 344                 iterr++; //let's look at the next one shall we :)
 345
 346                 //interpolate neighboring colors
 347                 const Real one = iterr->pos - iterl->pos;
 348                 const Real lambda = (x - iterl->pos)/one;
 349
 350                 //(1-l)iterl + (l)iterr
 351                 return iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
 352
 353                 //return Color::blend(iterr->color,iterl->color,lambda,Color::BLEND_STRAIGHT);
 354         }else
 355         {
 356                 //itegration madness
 357                 const_iterator i = iterl, ie = iterr+1;
 358                 Real wlast = left;
 359
 360                 ColorAccumulator clast,cwork;
 361                 {
 362                         const Real lambda = (x - iterl->pos)/(iterr->pos - iterl->pos);
 363
 364                         //premultiply because that's the form in which we can combine things...
 365                         clast = iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
 366                         //Color::blend((i+1)->color,i->color,(left - i->pos)/((i+1)->pos - i->pos),Color::BLEND_STRAIGHT);
 367                 }
 368
 369                 ColorAccumulator        accum = 0;
 370
 371                 //loop through all the trapezoids and integrate them as we go...
 372                 //      area of trap = (yi + yi1)*(xi1 - xi)
 373                 //      yi = clast, xi = wlast, yi1 = i->color, xi1 = i->pos
 374
 375                 for(;i<=iterr; wlast=i->pos,clast=i->color.premult_alpha(),++i)
 376                 {
 377                         const Real diff = i->pos - wlast;
 378                         if(diff > 0) //only accumulate if there will be area to add
 379                         {
 380                                 cwork = i->color.premult_alpha();
 381                                 accum += (cwork + clast)*diff;
 382                         }
 383                 }
 384
 385                 {
 386                         const_iterator ibef = i-1;
 387                         const Real diff = right - ibef->pos;
 388
 389                         if(diff > 0)
 390                         {
 391                                 const Real lambda = diff/(i->pos - ibef->pos);
 392                                 cwork = ibef->color.premult_alpha()*(1-lambda) + i->color.premult_alpha()*lambda;
 393
 394                                 accum += (cwork + clast)*diff; //can probably optimize this more... but it's not too bad
 395                         }
 396                 }
 397
 398                 accum /= supersample; //should be the total area it was sampled over...
 399                 return accum.demult_alpha();
 400         }*/
 401
 402         next=begin(),iter=next++;
 403
 404         //add for optimization
 405         next = binary_find(begin(),end(),(Real)begin_sample);
 406         iter = next++;
 407
 408         //! As a future optimization, this could be performed faster
 409         //! using a binary search.
 410         for(;iter<end();iter=next++)
 411         {
 412                 if(next==end() || x>=iter->pos &&  x<next->pos && iter->pos!=next->pos)
 413                 {
 414                         // If the supersample region falls square in between
 415                         // two CPoints, then we don't have to do anything special.
 416                         if(next!=end() && (!supersample || (iter->pos<=begin_sample && next->pos>=end_sample)))
 417                         {
 418                                 const Real dist(next->pos-iter->pos);
 419                                 const Real pos(x-iter->pos);
 420                                 const Real amount(pos/dist);
 421                                 return Color::blend(next->color,iter->color, amount, Color::BLEND_STRAIGHT);
 422                         }
 423                         // In this case our supersample region extends over one or more
 424                         // CPoints. So, we need to calculate our coverage amount.
 425                         ColorAccumulator pool(Color::alpha());
 426                         float divisor(0.0),weight(0);
 427
 428                         const_iterator iter2,next2;
 429                         iter2=iter;
 430                         if(iter==begin() && iter->pos>x)
 431                         {
 432                                 weight=x-iter->pos;
 433                                 //weight*=iter->color.get_a();
 434                                 pool+=ColorAccumulator(iter->color).premult_alpha()*weight;
 435                                 divisor+=weight;
 436                         }
 437                         else
 438                         {
 439                                 while(iter2->pos>=begin_sample)
 440                                 {
 441                                         if(iter2==begin())
 442                                         {
 443                                                 weight=iter2->pos-(begin_sample);
 444                                                 //weight*=iter2->color.get_a();
 445                                                 pool+=ColorAccumulator(iter2->color).premult_alpha()*weight;
 446                                                 divisor+=weight;
 447                                                 break;
 448                                         }
 449                                         next2=iter2--;
 450                                         pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
 451                                         divisor+=weight;
 452                                 }
 453                         }
 454
 455                         next2=iter;
 456                         iter2=next2++;
 457                         while(iter2->pos<=end_sample)
 458                         {
 459                                 if(next2==end())
 460                                 {
 461                                         weight=(end_sample)-iter2->pos;
 462                                         pool+=ColorAccumulator(iter2->color).premult_alpha()*weight;
 463                                         divisor+=weight;
 464                                         break;
 465                                 }
 466                                 pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
 467                                 divisor+=weight;
 468                                 iter2=next2++;
 469                         }
 470
 471                         if(divisor && pool.get_a() && pool.is_valid())
 472                         {
 473 /*
 474                                 pool.set_r(pool.get_r()/pool.get_a());
 475                                 pool.set_g(pool.get_g()/pool.get_a());
 476                                 pool.set_b(pool.get_b()/pool.get_a());
 477                                 pool.set_a(pool.get_a()/divisor);
 478 */
 479                                 pool/=divisor;
 480                                 pool.set_r(pool.get_r()/pool.get_a());
 481                                 pool.set_g(pool.get_g()/pool.get_a());
 482                                 pool.set_b(pool.get_b()/pool.get_a());
 483                                 if(pool.is_valid())
 484                                         return pool;
 485                                 else
 486                                         return Color::alpha();
 487                         }
 488                         else
 489                                 return Color::alpha();
 490                 }
 491         }
 492
 493         // We should never get to this point.
 494
 495         synfig::error("synfig::Gradient::operator()(): Logic Error (x=%f)",x);
 496         assert(0);
 497         throw std::logic_error(strprintf("synfig::Gradient::operator()(): Logic Error (x=%f)",x));
 498 }
 499
 500 synfig::Gradient::iterator
 501 synfig::Gradient::proximity(const Real &x)
 502 {
 503         iterator iter;
 504         float dist(100000000);
 505         float prev_pos(-0230);
 506         // This algorithm requires a sorted list.
 507         for(iter=begin();iter<end();iter++)
 508         {
 509                 float new_dist;
 510
 511                 if(prev_pos==iter->pos)
 512                         new_dist=(abs(x-iter->pos-0.00001));
 513                 else
 514                         new_dist=(abs(x-iter->pos));
 515
 516                 if(new_dist>dist)
 517                 {
 518                         iter--;
 519                         return iter;
 520                 }
 521                 dist=new_dist;
 522                 prev_pos=iter->pos;
 523         }
 524         iter--;
 525         return iter;
 526 }
 527
 528 synfig::Gradient::const_iterator
 529 synfig::Gradient::proximity(const Real &x)const
 530 {
 531         return const_cast<Gradient*>(this)->proximity(x);
 532         /*
 533         const_iterator iter;
 534         float dist(100000000);
 535
 536         // This algorithm requires a sorted list.
 537         for(iter=begin();iter<end();iter++)
 538         {
 539                 const float new_dist(abs(x-iter->pos));
 540                 if(new_dist>dist)
 541                 {
 542                         iter--;
 543                         return iter;
 544                 }
 545                 dist=new_dist;
 546         }
 547         iter--;
 548         return iter;
 549         */
 550 }
 551
 552 synfig::Gradient::iterator
 553 synfig::Gradient::find(const UniqueID &id)
 554 {
 555         iterator iter;
 556
 557         for(iter=begin();iter<end();iter++)
 558         {
 559                 if(id==*iter)
 560                         return iter;
 561         }
 562
 563         throw Exception::NotFound("synfig::Gradient::find(): Unable to find UniqueID in gradient");
 564 }
 565
 566 synfig::Gradient::const_iterator
 567 synfig::Gradient::find(const UniqueID &id)const
 568 {
 569         const_iterator iter;
 570
 571         for(iter=begin();iter<end();iter++)
 572         {
 573                 if(id==*iter)
 574                         return iter;
 575         }
 576
 577         throw Exception::NotFound("synfig::Gradient::find()const: Unable to find UniqueID in gradient");
 578 }