Fixed the name of the last parameter in the set_time() prototype to match that of...
[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: 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 }