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: gradient.cpp,v 1.2 2005/01/21 19:29:10 darco Exp $
   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
  37 #include <ETL/misc>
  38 #endif
  39
  40 /* === U S I N G =========================================================== */
  41
  42 using namespace std;
  43 using namespace etl;
  44 using namespace synfig;
  45
  46 /* === M A C R O S ========================================================= */
  47
  48 /* === G L O B A L S ======================================================= */
  49
  50 /* === P R O C E D U R E S ================================================= */
  51
  52 /* === M E T H O D S ======================================================= */
  53
  54 synfig::Gradient::Gradient(const Color &c1, const Color &c2)
  55 {
  56         push_back(CPoint(0.0,c1));
  57         push_back(CPoint(1.0,c2));
  58 }
  59
  60 synfig::Gradient::Gradient(const Color &c1, const Color &c2, const Color &c3)
  61 {
  62         push_back(CPoint(0.0,c1));
  63         push_back(CPoint(0.5,c2));
  64         push_back(CPoint(1.0,c3));
  65 }
  66
  67 // This sort algorithm MUST be stable
  68 // ie: it must not change the order of items with the same value.
  69 // I am using a bubble sort.
  70 // This algorithm will sort a nearly-sorted list at ~O(N), and
  71 // it will sort an inverse sorted list at ~O(N*N).
  72 void
  73 synfig::Gradient::sort()
  74 {
  75         stable_sort(begin(),end());
  76         /*
  77         iterator iter;
  78         iterator iter2,next;
  79
  80         for(iter=begin();iter!=end();iter++)
  81         {
  82                 for(next=iter, iter2=next--;iter2!=begin();iter2=next--)
  83                 {
  84                         if(*iter<*next)
  85                         {
  86                                 //insert(next,*iter);
  87                                 //erase(iter);
  88                                 iter_swap(next,iter);
  89
  90                                 continue;
  91                         }
  92                         else
  93                                 break;
  94                 }
  95         }
  96         */
  97 }
  98
  99 static synfig::ColorAccumulator
 100 supersample_helper(const synfig::Gradient::CPoint &color1, const synfig::Gradient::CPoint &color2, float begin, float end, float &weight)
 101 {
 102         if(color1.pos==color2.pos || color1.pos>=end || color2.pos<=begin)
 103         {
 104                 weight=0;
 105                 return Color::alpha();
 106         }
 107         if(color1.pos>=begin && color2.pos<end)
 108         {
 109                 weight=color2.pos-color1.pos;
 110                 ColorAccumulator ret=Color::blend(color2.color,color1.color, 0.5, Color::BLEND_STRAIGHT);
 111                 ret.set_r(ret.get_r()*ret.get_a());
 112                 ret.set_g(ret.get_g()*ret.get_a());
 113                 ret.set_b(ret.get_b()*ret.get_a());
 114                 return ret*weight;
 115         }
 116         if(color1.pos>=begin && color2.pos>=end)
 117         {
 118                 weight=end-color1.pos;
 119                 float pos((end+color1.pos)*0.5);
 120                 float amount((pos-color1.pos)/(color2.pos-color1.pos));
 121                 //if(abs(amount)>1)amount=(amount>0)?1:-1;
 122                 ColorAccumulator ret(Color::blend(color2.color,color1.color, amount, Color::BLEND_STRAIGHT));
 123                 ret.set_r(ret.get_r()*ret.get_a());
 124                 ret.set_g(ret.get_g()*ret.get_a());
 125                 ret.set_b(ret.get_b()*ret.get_a());
 126                 return ret*weight;
 127         }
 128         if(color1.pos<begin && color2.pos<end)
 129         {
 130                 weight=color2.pos-begin;
 131                 float pos((begin+color2.pos)*0.5);
 132                 float amount((pos-color1.pos)/(color2.pos-color1.pos));
 133                 //if(abs(amount)>1)amount=(amount>0)?1:-1;
 134                 ColorAccumulator ret(Color::blend(color2.color,color1.color, amount, Color::BLEND_STRAIGHT));
 135                 ret.set_r(ret.get_r()*ret.get_a());
 136                 ret.set_g(ret.get_g()*ret.get_a());
 137                 ret.set_b(ret.get_b()*ret.get_a());
 138                 return ret*weight;
 139         }
 140         synfig::error("color1.pos=%f",color1.pos);
 141         synfig::error("color2.pos=%f",color2.pos);
 142         synfig::error("begin=%f",begin);
 143         synfig::error("end=%f",end);
 144
 145         weight=0;
 146         return Color::alpha();
 147
 148 //      assert(0);
 149 }
 150
 151 Color
 152 synfig::Gradient::operator()(const Real &x,float supersample)const
 153 {
 154         if(empty())
 155                 return Color(0,0,0,0);
 156         if(supersample<0)
 157                 supersample=-supersample;
 158         if(supersample>2.0)
 159                 supersample=2.0f;
 160
 161         float begin_sample(x-supersample*0.5);
 162         float end_sample(x+supersample*0.5);
 163
 164         if(size()==1 || end_sample<=front().pos || isnan(x))
 165                 return front().color;
 166
 167         if(begin_sample>=back().pos)
 168                 return back().color;
 169
 170         /*
 171         if(end_sample>=back().pos)
 172                 end_sample=back().pos;
 173
 174         if(begin_sample<=front().pos)
 175                 begin_sample=front().pos;
 176         */
 177
 178         const_iterator iter,next;
 179
 180         /*
 181         //optimizize...
 182         Real    left = x-supersample/2, right = x+supersample/2;
 183
 184         if(left < front().pos) left = front().pos;
 185         if(right > back().pos) right = back().pos;
 186
 187         //find using binary search...
 188         const_iterator iterl,iterr;
 189
 190         //the binary search should give us the values BEFORE the point we're looking for...
 191         iterl = binary_find(begin(),end(),left);
 192         iterr = binary_find(iterl,end(),right);
 193
 194         //now integrate over the range of left to right...
 195
 196         if(iterl == iterr)
 197         {
 198                 iterr++; //let's look at the next one shall we :)
 199
 200                 //interpolate neighboring colors
 201                 const Real one = iterr->pos - iterl->pos;
 202                 const Real lambda = (x - iterl->pos)/one;
 203
 204                 //(1-l)iterl + (l)iterr
 205                 return iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
 206
 207                 //return Color::blend(iterr->color,iterl->color,lambda,Color::BLEND_STRAIGHT);
 208         }else
 209         {
 210                 //itegration madness
 211                 const_iterator i = iterl, ie = iterr+1;
 212                 Real wlast = left;
 213
 214                 ColorAccumulator clast,cwork;
 215                 {
 216                         const Real lambda = (x - iterl->pos)/(iterr->pos - iterl->pos);
 217
 218                         //premultiply because that's the form in which we can combine things...
 219                         clast = iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
 220                         //Color::blend((i+1)->color,i->color,(left - i->pos)/((i+1)->pos - i->pos),Color::BLEND_STRAIGHT);
 221                 }
 222
 223                 ColorAccumulator        accum = 0;
 224
 225                 //loop through all the trapezoids and integrate them as we go...
 226                 //      area of trap = (yi + yi1)*(xi1 - xi)
 227                 //      yi = clast, xi = wlast, yi1 = i->color, xi1 = i->pos
 228
 229                 for(;i<=iterr; wlast=i->pos,clast=i->color.premult_alpha(),++i)
 230                 {
 231                         const Real diff = i->pos - wlast;
 232                         if(diff > 0) //only accumulate if there will be area to add
 233                         {
 234                                 cwork = i->color.premult_alpha();
 235                                 accum += (cwork + clast)*diff;
 236                         }
 237                 }
 238
 239                 {
 240                         const_iterator ibef = i-1;
 241                         const Real diff = right - ibef->pos;
 242
 243                         if(diff > 0)
 244                         {
 245                                 const Real lambda = diff/(i->pos - ibef->pos);
 246                                 cwork = ibef->color.premult_alpha()*(1-lambda) + i->color.premult_alpha()*lambda;
 247
 248                                 accum += (cwork + clast)*diff; //can probably optimize this more... but it's not too bad
 249                         }
 250                 }
 251
 252                 accum /= supersample; //should be the total area it was sampled over...
 253                 return accum.demult_alpha();
 254         }*/
 255
 256         next=begin(),iter=next++;
 257
 258         //add for optimization
 259         next = binary_find(begin(),end(),(Real)begin_sample);
 260         iter = next++;
 261
 262         //! As a future optimization, this could be performed faster
 263         //! using a binary search.
 264         for(;iter<end();iter=next++)
 265         {
 266                 if(next==end() || x>=iter->pos &&  x<next->pos && iter->pos!=next->pos)
 267                 {
 268                         // If the supersample region falls square in between
 269                         // two CPoints, then we don't have to do anything special.
 270                         if(next!=end() && (!supersample || (iter->pos<=begin_sample && next->pos>=end_sample)))
 271                         {
 272                                 const Real dist(next->pos-iter->pos);
 273                                 const Real pos(x-iter->pos);
 274                                 const Real amount(pos/dist);
 275                                 return Color::blend(next->color,iter->color, amount, Color::BLEND_STRAIGHT);
 276                         }
 277                         // In this case our supersample region extends over one or more
 278                         // CPoints. So, we need to calculate our coverage amount.
 279                         ColorAccumulator pool(Color::alpha());
 280                         float divisor(0.0),weight(0);
 281
 282                         const_iterator iter2,next2;
 283                         iter2=iter;
 284                         if(iter==begin() && iter->pos>x)
 285                         {
 286                                 weight=x-iter->pos;
 287                                 //weight*=iter->color.get_a();
 288                                 pool+=ColorAccumulator(iter->color)*(float)iter->color.get_a()*weight;
 289                                 divisor+=weight;
 290                         }
 291                         else
 292                         {
 293                                 while(iter2->pos>=begin_sample)
 294                                 {
 295                                         if(iter2==begin())
 296                                         {
 297                                                 weight=iter2->pos-(begin_sample);
 298                                                 //weight*=iter2->color.get_a();
 299                                                 pool+=ColorAccumulator(iter2->color)*(float)iter2->color.get_a()*weight;
 300                                                 divisor+=weight;
 301                                                 break;
 302                                         }
 303                                         next2=iter2--;
 304                                         pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
 305                                         divisor+=weight;
 306                                 }
 307                         }
 308
 309                         next2=iter;
 310                         iter2=next2++;
 311                         while(iter2->pos<=end_sample)
 312                         {
 313                                 if(next2==end())
 314                                 {
 315                                         weight=(end_sample)-iter2->pos;
 316                                         pool+=ColorAccumulator(iter2->color)*(float)iter2->color.get_a()*weight;
 317                                         divisor+=weight;
 318                                         break;
 319                                 }
 320                                 pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
 321                                 divisor+=weight;
 322                                 iter2=next2++;
 323                         }
 324
 325                         if(divisor && pool.get_a() && pool.is_valid())
 326                         {
 327 /*
 328                                 pool.set_r(pool.get_r()/pool.get_a());
 329                                 pool.set_g(pool.get_g()/pool.get_a());
 330                                 pool.set_b(pool.get_b()/pool.get_a());
 331                                 pool.set_a(pool.get_a()/divisor);
 332 */
 333                                 pool/=divisor;
 334                                 pool.set_r(pool.get_r()/pool.get_a());
 335                                 pool.set_g(pool.get_g()/pool.get_a());
 336                                 pool.set_b(pool.get_b()/pool.get_a());
 337                                 if(pool.is_valid())
 338                                         return pool;
 339                                 else
 340                                         return Color::alpha();
 341                         }
 342                         else
 343                                 return Color::alpha();
 344                 }
 345         }
 346
 347         // We should never get to this point.
 348
 349         synfig::error("synfig::Gradient::operator()(): Logic Error (x=%f)",x);
 350         assert(0);
 351         throw std::logic_error(strprintf("synfig::Gradient::operator()(): Logic Error (x=%f)",x));
 352 }
 353
 354 synfig::Gradient::iterator
 355 synfig::Gradient::proximity(const Real &x)
 356 {
 357         iterator iter;
 358         float dist(100000000);
 359         float prev_pos(-0230);
 360         // This algorithm requires a sorted list.
 361         for(iter=begin();iter<end();iter++)
 362         {
 363                 float new_dist;
 364
 365                 if(prev_pos==iter->pos)
 366                         new_dist=(abs(x-iter->pos-0.00001));
 367                 else
 368                         new_dist=(abs(x-iter->pos));
 369
 370                 if(new_dist>dist)
 371                 {
 372                         iter--;
 373                         return iter;
 374                 }
 375                 dist=new_dist;
 376                 prev_pos=iter->pos;
 377         }
 378         iter--;
 379         return iter;
 380 }
 381
 382 synfig::Gradient::const_iterator
 383 synfig::Gradient::proximity(const Real &x)const
 384 {
 385         return const_cast<Gradient*>(this)->proximity(x);
 386         /*
 387         const_iterator iter;
 388         float dist(100000000);
 389
 390         // This algorithm requires a sorted list.
 391         for(iter=begin();iter<end();iter++)
 392         {
 393                 const float new_dist(abs(x-iter->pos));
 394                 if(new_dist>dist)
 395                 {
 396                         iter--;
 397                         return iter;
 398                 }
 399                 dist=new_dist;
 400         }
 401         iter--;
 402         return iter;
 403         */
 404 }
 405
 406 synfig::Gradient::iterator
 407 synfig::Gradient::find(const UniqueID &id)
 408 {
 409         iterator iter;
 410
 411         for(iter=begin();iter<end();iter++)
 412         {
 413                 if(id==*iter)
 414                         return iter;
 415         }
 416
 417         throw Exception::NotFound("synfig::Gradient::find(): Unable to find UniqueID in gradient");
 418 }
 419
 420 synfig::Gradient::const_iterator
 421 synfig::Gradient::find(const UniqueID &id)const
 422 {
 423         const_iterator iter;
 424
 425         for(iter=begin();iter<end();iter++)
 426         {
 427                 if(id==*iter)
 428                         return iter;
 429         }
 430
 431         throw Exception::NotFound("synfig::Gradient::find()const: Unable to find UniqueID in gradient");
 432 }