Initial Stable Commit
[synfig.git] / 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 }