Partially fix 1702760: stop compiler warning about trgt_png.cpp.
[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 **
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 }