1 /* === S Y N F I G ========================================================= */
3 ** \brief Color Gradient Class Member Definitions
8 ** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
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.
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.
21 /* ========================================================================= */
23 /* === H E A D E R S ======================================================= */
35 #include "exception.h"
41 /* === U S I N G =========================================================== */
45 using namespace synfig;
47 /* === M A C R O S ========================================================= */
49 /* === G L O B A L S ======================================================= */
51 /* === P R O C E D U R E S ================================================= */
53 /* === M E T H O D S ======================================================= */
55 synfig::Gradient::Gradient(const Color &c1, const Color &c2)
57 push_back(CPoint(0.0,c1));
58 push_back(CPoint(1.0,c2));
61 synfig::Gradient::Gradient(const Color &c1, const Color &c2, const Color &c3)
63 push_back(CPoint(0.0,c1));
64 push_back(CPoint(0.5,c2));
65 push_back(CPoint(1.0,c3));
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).
74 synfig::Gradient::sort()
76 stable_sort(begin(),end());
81 for(iter=begin();iter!=end();iter++)
83 for(next=iter, iter2=next--;iter2!=begin();iter2=next--)
100 static synfig::ColorAccumulator
101 supersample_helper(const synfig::Gradient::CPoint &color1, const synfig::Gradient::CPoint &color2, float begin, float end, float &weight)
103 if(color1.pos==color2.pos || color1.pos>=end || color2.pos<=begin)
106 return Color::alpha();
108 if(color1.pos>=begin && color2.pos<end)
110 weight=color2.pos-color1.pos;
111 ColorAccumulator ret=Color::blend(color2.color,color1.color, 0.5, Color::BLEND_STRAIGHT).premult_alpha()*weight;
114 if(color1.pos>=begin && color2.pos>=end)
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);
123 if(color1.pos<begin && color2.pos<end)
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);
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);
138 return Color::alpha();
143 static void show_gradient(const Gradient::CPointList x) {
145 for (Gradient::const_iterator iter = x.begin(); iter != x.end(); iter++) {
146 printf("%3d : %.3f %s\n", i++, (*iter).pos, (*iter).color.get_string().c_str());
151 synfig::Gradient::operator+=(const Gradient &rhs)
153 bool print=false; // for debugging
154 if (print) { printf("\nadding lhs:\n"); show_gradient(this->cpoints); printf("\n"); }
155 if (print) { printf("adding rhs:\n"); show_gradient(rhs.cpoints); printf("\n"); }
157 const_iterator iter1 = begin(), iter2 = rhs.begin(), left_same, right_same;
159 if (iter1 != end()) left = *iter1;
160 if (iter2 != rhs.end()) right = *iter2;
161 int pos1 = 0, pos2 = 0;
164 // if there are cpoints in both gradients run through both until one runs out
165 if (iter1 != end() && iter2 != rhs.end())
168 // if the left one has the first cpoint
169 if (left.pos < right.pos)
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;
177 // if the right one has the first cpoint
178 else if (left.pos > right.pos)
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;
186 // they both have a cpoint at the same time
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++)
193 if (print) printf("skipping past pos %d in left\n", pos1);
195 for(right_same = ++iter2; iter2 != rhs.end() && (*iter2).pos == right.pos; iter2++, pos2++)
197 if (print) printf("skipping past pos %d in right\n", pos2);
200 // if the is only one cpoint at this position in each gradient,
201 // there's only one corresponding cpoint in the sum
202 if (iter1 == left_same && iter2 == right_same) {
203 if (print) printf("two singles at left %d and right %d\n", pos1++, pos2++);
204 ret.push_back(CPoint(left.pos, left.color + right.color));
206 // otherwise we sum the first in each, and the last in each
209 if (print) printf("[copying %d from left %d and %d from right %d at %.2f]\n", iter1-left_same+1, tpos1, iter2-right_same+1, tpos2, left.pos);
210 // merge the front two cpoints
211 if (print) printf(" copy front from left %d right %d\n", tpos1++, tpos2++);
212 ret.push_back(CPoint(left.pos, left.color + right.color));
214 // merge the middle pairs points - each middle point merges with its counterpart
215 while(left_same < iter1-1 && right_same < iter2-1)
217 old1 = *(left_same++);
218 old2 = *(right_same++);
219 if (print) printf(" copy middle from left %d and right %d\n", tpos1++, tpos2++);
220 ret.push_back(CPoint(old1.pos, old1.color+old2.color));
222 // if one gradient has more middle points than the other, merge the rest with the last point in the other gradient
223 for(old2 = (*(iter2-1)); left_same < iter1-1; left_same++)
226 if (print) printf(" copy middle from left %d plus end of right\n", tpos1++);
227 ret.push_back(CPoint(old1.pos, old1.color + old2.color));
229 for(old1 = (*(iter1-1)); right_same < iter2-1; right_same++)
232 if (print) printf(" copy middle from right %d plus end of left\n", tpos2++);
233 ret.push_back(CPoint(old2.pos, old1.color + old2.color));
235 // merge the back two cpoints
236 if (print) printf(" copy end from left %d right %d\n", pos1++, pos2++);
237 ret.push_back(CPoint(left.pos, (*(iter1-1)).color + (*(iter2-1)).color));
239 // make sure we update 'left' and 'right'
240 if (iter1 != end()) left=*iter1;
241 if (iter2 == rhs.end()) break;
243 if (iter1 == end()) break;
247 // one of the gradients has run out of points
248 // does the left one have points left?
252 if (print) printf("finish end from left %d\n", pos1++);
253 ret.push_back(CPoint(left.pos, left.color + rhs(left.pos)));
254 if(++iter1 == end()) break;
257 // the left one was empty, so maybe the right one has points left
258 else if (iter2 != rhs.end())
261 if (print) printf("finish end from right %d\n", pos2++);
262 ret.push_back(CPoint(right.pos, right.color + (*this)(right.pos)));
263 if(++iter2 == rhs.end()) break;
267 if (print) { printf("\nsummed ret:\n"); show_gradient(ret); printf("\n"); }
273 synfig::Gradient::operator-=(const Gradient &rhs)
275 return (*this)+=(rhs*-1);
279 synfig::Gradient::operator*=(const float &rhs)
284 for (iterator iter = cpoints.begin(); iter!=cpoints.end(); iter++)
285 (*iter).color *= rhs;
290 synfig::Gradient::operator/=(const float &rhs)
292 for (iterator iter = cpoints.begin(); iter!=cpoints.end(); iter++)
293 (*iter).color /= rhs;
298 synfig::Gradient::operator()(const Real &x,float supersample)const
301 return Color(0,0,0,0);
303 supersample=-supersample;
307 float begin_sample(x-supersample*0.5);
308 float end_sample(x+supersample*0.5);
310 if(cpoints.size()==1 || end_sample<=cpoints.front().pos || isnan(x))
311 return cpoints.front().color;
313 if(begin_sample>=cpoints.back().pos)
314 return cpoints.back().color;
317 if(end_sample>=back().pos)
318 end_sample=back().pos;
320 if(begin_sample<=front().pos)
321 begin_sample=front().pos;
324 const_iterator iter,next;
328 Real left = x-supersample/2, right = x+supersample/2;
330 if(left < front().pos) left = front().pos;
331 if(right > back().pos) right = back().pos;
333 //find using binary search...
334 const_iterator iterl,iterr;
336 //the binary search should give us the values BEFORE the point we're looking for...
337 iterl = binary_find(begin(),end(),left);
338 iterr = binary_find(iterl,end(),right);
340 //now integrate over the range of left to right...
344 iterr++; //let's look at the next one shall we :)
346 //interpolate neighboring colors
347 const Real one = iterr->pos - iterl->pos;
348 const Real lambda = (x - iterl->pos)/one;
350 //(1-l)iterl + (l)iterr
351 return iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
353 //return Color::blend(iterr->color,iterl->color,lambda,Color::BLEND_STRAIGHT);
357 const_iterator i = iterl, ie = iterr+1;
360 ColorAccumulator clast,cwork;
362 const Real lambda = (x - iterl->pos)/(iterr->pos - iterl->pos);
364 //premultiply because that's the form in which we can combine things...
365 clast = iterl->color.premult_alpha()*(1-lambda) + iterr->color.premult_alpha()*lambda;
366 //Color::blend((i+1)->color,i->color,(left - i->pos)/((i+1)->pos - i->pos),Color::BLEND_STRAIGHT);
369 ColorAccumulator accum = 0;
371 //loop through all the trapezoids and integrate them as we go...
372 // area of trap = (yi + yi1)*(xi1 - xi)
373 // yi = clast, xi = wlast, yi1 = i->color, xi1 = i->pos
375 for(;i<=iterr; wlast=i->pos,clast=i->color.premult_alpha(),++i)
377 const Real diff = i->pos - wlast;
378 if(diff > 0) //only accumulate if there will be area to add
380 cwork = i->color.premult_alpha();
381 accum += (cwork + clast)*diff;
386 const_iterator ibef = i-1;
387 const Real diff = right - ibef->pos;
391 const Real lambda = diff/(i->pos - ibef->pos);
392 cwork = ibef->color.premult_alpha()*(1-lambda) + i->color.premult_alpha()*lambda;
394 accum += (cwork + clast)*diff; //can probably optimize this more... but it's not too bad
398 accum /= supersample; //should be the total area it was sampled over...
399 return accum.demult_alpha();
402 next=begin(),iter=next++;
404 //add for optimization
405 next = binary_find(begin(),end(),(Real)begin_sample);
408 //! As a future optimization, this could be performed faster
409 //! using a binary search.
410 for(;iter<end();iter=next++)
412 if(next==end() || x>=iter->pos && x<next->pos && iter->pos!=next->pos)
414 // If the supersample region falls square in between
415 // two CPoints, then we don't have to do anything special.
416 if(next!=end() && (!supersample || (iter->pos<=begin_sample && next->pos>=end_sample)))
418 const Real dist(next->pos-iter->pos);
419 const Real pos(x-iter->pos);
420 const Real amount(pos/dist);
421 return Color::blend(next->color,iter->color, amount, Color::BLEND_STRAIGHT);
423 // In this case our supersample region extends over one or more
424 // CPoints. So, we need to calculate our coverage amount.
425 ColorAccumulator pool(Color::alpha());
426 float divisor(0.0),weight(0);
428 const_iterator iter2,next2;
430 if(iter==begin() && iter->pos>x)
433 //weight*=iter->color.get_a();
434 pool+=ColorAccumulator(iter->color).premult_alpha()*weight;
439 while(iter2->pos>=begin_sample)
443 weight=iter2->pos-(begin_sample);
444 //weight*=iter2->color.get_a();
445 pool+=ColorAccumulator(iter2->color).premult_alpha()*weight;
450 pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
457 while(iter2->pos<=end_sample)
461 weight=(end_sample)-iter2->pos;
462 pool+=ColorAccumulator(iter2->color).premult_alpha()*weight;
466 pool+=supersample_helper(*iter2, *next2, begin_sample, end_sample, weight);
471 if(divisor && pool.get_a() && pool.is_valid())
474 pool.set_r(pool.get_r()/pool.get_a());
475 pool.set_g(pool.get_g()/pool.get_a());
476 pool.set_b(pool.get_b()/pool.get_a());
477 pool.set_a(pool.get_a()/divisor);
480 pool.set_r(pool.get_r()/pool.get_a());
481 pool.set_g(pool.get_g()/pool.get_a());
482 pool.set_b(pool.get_b()/pool.get_a());
486 return Color::alpha();
489 return Color::alpha();
493 // We should never get to this point.
495 synfig::error("synfig::Gradient::operator()(): Logic Error (x=%f)",x);
497 throw std::logic_error(strprintf("synfig::Gradient::operator()(): Logic Error (x=%f)",x));
500 synfig::Gradient::iterator
501 synfig::Gradient::proximity(const Real &x)
504 float dist(100000000);
505 float prev_pos(-0230);
506 // This algorithm requires a sorted list.
507 for(iter=begin();iter<end();iter++)
511 if(prev_pos==iter->pos)
512 new_dist=(abs(x-iter->pos-0.00001));
514 new_dist=(abs(x-iter->pos));
528 synfig::Gradient::const_iterator
529 synfig::Gradient::proximity(const Real &x)const
531 return const_cast<Gradient*>(this)->proximity(x);
534 float dist(100000000);
536 // This algorithm requires a sorted list.
537 for(iter=begin();iter<end();iter++)
539 const float new_dist(abs(x-iter->pos));
552 synfig::Gradient::iterator
553 synfig::Gradient::find(const UniqueID &id)
557 for(iter=begin();iter<end();iter++)
563 throw Exception::NotFound("synfig::Gradient::find(): Unable to find UniqueID in gradient");
566 synfig::Gradient::const_iterator
567 synfig::Gradient::find(const UniqueID &id)const
571 for(iter=begin();iter<end();iter++)
577 throw Exception::NotFound("synfig::Gradient::find()const: Unable to find UniqueID in gradient");