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