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

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