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 Color
 144 synfig::Gradient::operator()(const Real &x,float supersample)const
 145 {
 146         if(empty())
 147                 return Color(0,0,0,0);
 148         if(supersample<0)
 149                 supersample=-supersample;
 150         if(supersample>2.0)
 151                 supersample=2.0f;
 152
 153         float begin_sample(x-supersample*0.5);
 154         float end_sample(x+supersample*0.5);
 155
 156         if(size()==1 || end_sample<=front().pos || isnan(x))
 157                 return front().color;
 158
 159         if(begin_sample>=back().pos)
 160                 return back().color;
 161
 162         /*
 163         if(end_sample>=back().pos)
 164                 end_sample=back().pos;
 165
 166         if(begin_sample<=front().pos)
 167                 begin_sample=front().pos;
 168         */
 169
 170         const_iterator iter,next;
 171
 172         /*
 173         //optimizize...
 174         Real    left = x-supersample/2, right = x+supersample/2;
 175
 176         if(left < front().pos) left = front().pos;
 177         if(right > back().pos) right = back().pos;
 178
 179         //find using binary search...
 180         const_iterator iterl,iterr;
 181
 182         //the binary search should give us the values BEFORE the point we're looking for...
 183         iterl = binary_find(begin(),end(),left);
 184         iterr = binary_find(iterl,end(),right);
 185
 186         //now integrate over the range of left to right...
 187
 188         if(iterl == iterr)
 189         {
 190                 iterr++; //let's look at the next one shall we :)
 191
 192                 //interpolate neighboring colors
 193                 const Real one = iterr->pos - iterl->pos;
 194                 const Real lambda = (x - iterl->pos)/one;
 195
 196                 //(1-l)iterl + (l)iterr
 197                 return iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
 198
 199                 //return Color::blend(iterr->color,iterl->color,lambda,Color::BLEND_STRAIGHT);
 200         }else
 201         {
 202                 //itegration madness
 203                 const_iterator i = iterl, ie = iterr+1;
 204                 Real wlast = left;
 205
 206                 ColorAccumulator clast,cwork;
 207                 {
 208                         const Real lambda = (x - iterl->pos)/(iterr->pos - iterl->pos);
 209
 210                         //premultiply because that's the form in which we can combine things...
 211                         clast = iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
 212                         //Color::blend((i+1)->color,i->color,(left - i->pos)/((i+1)->pos - i->pos),Color::BLEND_STRAIGHT);
 213                 }
 214
 215                 ColorAccumulator        accum = 0;
 216
 217                 //loop through all the trapezoids and integrate them as we go...
 218                 //      area of trap = (yi + yi1)*(xi1 - xi)
 219                 //      yi = clast, xi = wlast, yi1 = i->color, xi1 = i->pos
 220
 221                 for(;i<=iterr; wlast=i->pos,clast=i->color.premult_alpha(),++i)
 222                 {
 223                         const Real diff = i->pos - wlast;
 224                         if(diff > 0) //only accumulate if there will be area to add
 225                         {
 226                                 cwork = i->color.premult_alpha();
 227                                 accum += (cwork + clast)*diff;
 228                         }
 229                 }
 230
 231                 {
 232                         const_iterator ibef = i-1;
 233                         const Real diff = right - ibef->pos;
 234
 235                         if(diff > 0)
 236                         {
 237                                 const Real lambda = diff/(i->pos - ibef->pos);
 238                                 cwork = ibef->color.premult_alpha()*(1-lambda) + i->color.premult_alpha()*lambda;
 239
 240                                 accum += (cwork + clast)*diff; //can probably optimize this more... but it's not too bad
 241                         }
 242                 }
 243
 244                 accum /= supersample; //should be the total area it was sampled over...
 245                 return accum.demult_alpha();
 246         }*/
 247
 248         next=begin(),iter=next++;
 249
 250         //add for optimization
 251         next = binary_find(begin(),end(),(Real)begin_sample);
 252         iter = next++;
 253
 254         //! As a future optimization, this could be performed faster
 255         //! using a binary search.
 256         for(;iter<end();iter=next++)
 257         {
 258                 if(next==end() || x>=iter->pos &&  x<next->pos && iter->pos!=next->pos)
 259                 {
 260                         // If the supersample region falls square in between
 261                         // two CPoints, then we don't have to do anything special.
 262                         if(next!=end() && (!supersample || (iter->pos<=begin_sample && next->pos>=end_sample)))
 263                         {
 264                                 const Real dist(next->pos-iter->pos);
 265                                 const Real pos(x-iter->pos);
 266                                 const Real amount(pos/dist);
 267                                 return Color::blend(next->color,iter->color, amount, Color::BLEND_STRAIGHT);
 268                         }
 269                         // In this case our supersample region extends over one or more
 270                         // CPoints. So, we need to calculate our coverage amount.
 271                         ColorAccumulator pool(Color::alpha());
 272                         float divisor(0.0),weight(0);
 273
 274                         const_iterator iter2,next2;
 275                         iter2=iter;
 276                         if(iter==begin() && iter->pos>x)
 277                         {
 278                                 weight=x-iter->pos;
 279                                 //weight*=iter->color.get_a();
 280                                 pool+=ColorAccumulator(iter->color).premult_alpha()*weight;
 281                                 divisor+=weight;
 282                         }
 283                         else
 284                         {
 285                                 while(iter2->pos>=begin_sample)
 286                                 {
 287                                         if(iter2==begin())
 288                                         {
 289                                                 weight=iter2->pos-(begin_sample);
 290                                                 //weight*=iter2->color.get_a();
 291                                                 pool+=ColorAccumulator(iter2->color).premult_alpha()*weight;
 292                                                 divisor+=weight;
 293                                                 break;
 294                                         }
 295                                         next2=iter2--;
 296                                         pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
 297                                         divisor+=weight;
 298                                 }
 299                         }
 300
 301                         next2=iter;
 302                         iter2=next2++;
 303                         while(iter2->pos<=end_sample)
 304                         {
 305                                 if(next2==end())
 306                                 {
 307                                         weight=(end_sample)-iter2->pos;
 308                                         pool+=ColorAccumulator(iter2->color).premult_alpha()*weight;
 309                                         divisor+=weight;
 310                                         break;
 311                                 }
 312                                 pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
 313                                 divisor+=weight;
 314                                 iter2=next2++;
 315                         }
 316
 317                         if(divisor && pool.get_a() && pool.is_valid())
 318                         {
 319 /*
 320                                 pool.set_r(pool.get_r()/pool.get_a());
 321                                 pool.set_g(pool.get_g()/pool.get_a());
 322                                 pool.set_b(pool.get_b()/pool.get_a());
 323                                 pool.set_a(pool.get_a()/divisor);
 324 */
 325                                 pool/=divisor;
 326                                 pool.set_r(pool.get_r()/pool.get_a());
 327                                 pool.set_g(pool.get_g()/pool.get_a());
 328                                 pool.set_b(pool.get_b()/pool.get_a());
 329                                 if(pool.is_valid())
 330                                         return pool;
 331                                 else
 332                                         return Color::alpha();
 333                         }
 334                         else
 335                                 return Color::alpha();
 336                 }
 337         }
 338
 339         // We should never get to this point.
 340
 341         synfig::error("synfig::Gradient::operator()(): Logic Error (x=%f)",x);
 342         assert(0);
 343         throw std::logic_error(strprintf("synfig::Gradient::operator()(): Logic Error (x=%f)",x));
 344 }
 345
 346 synfig::Gradient::iterator
 347 synfig::Gradient::proximity(const Real &x)
 348 {
 349         iterator iter;
 350         float dist(100000000);
 351         float prev_pos(-0230);
 352         // This algorithm requires a sorted list.
 353         for(iter=begin();iter<end();iter++)
 354         {
 355                 float new_dist;
 356
 357                 if(prev_pos==iter->pos)
 358                         new_dist=(abs(x-iter->pos-0.00001));
 359                 else
 360                         new_dist=(abs(x-iter->pos));
 361
 362                 if(new_dist>dist)
 363                 {
 364                         iter--;
 365                         return iter;
 366                 }
 367                 dist=new_dist;
 368                 prev_pos=iter->pos;
 369         }
 370         iter--;
 371         return iter;
 372 }
 373
 374 synfig::Gradient::const_iterator
 375 synfig::Gradient::proximity(const Real &x)const
 376 {
 377         return const_cast<Gradient*>(this)->proximity(x);
 378         /*
 379         const_iterator iter;
 380         float dist(100000000);
 381
 382         // This algorithm requires a sorted list.
 383         for(iter=begin();iter<end();iter++)
 384         {
 385                 const float new_dist(abs(x-iter->pos));
 386                 if(new_dist>dist)
 387                 {
 388                         iter--;
 389                         return iter;
 390                 }
 391                 dist=new_dist;
 392         }
 393         iter--;
 394         return iter;
 395         */
 396 }
 397
 398 synfig::Gradient::iterator
 399 synfig::Gradient::find(const UniqueID &id)
 400 {
 401         iterator iter;
 402
 403         for(iter=begin();iter<end();iter++)
 404         {
 405                 if(id==*iter)
 406                         return iter;
 407         }
 408
 409         throw Exception::NotFound("synfig::Gradient::find(): Unable to find UniqueID in gradient");
 410 }
 411
 412 synfig::Gradient::const_iterator
 413 synfig::Gradient::find(const UniqueID &id)const
 414 {
 415         const_iterator iter;
 416
 417         for(iter=begin();iter<end();iter++)
 418         {
 419                 if(id==*iter)
 420                         return iter;
 421         }
 422
 423         throw Exception::NotFound("synfig::Gradient::find()const: Unable to find UniqueID in gradient");
 424 }