Merge branch 'blender2.7'
[blender.git] / source / blender / blenkernel / intern / colorband.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 /** \file blender/blenkernel/intern/colorband.c
21  *  \ingroup bke
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_math.h"
27 #include "BLI_utildefines.h"
28 #include "BLI_math_color.h"
29 #include "BLI_heap.h"
30
31 #include "DNA_key_types.h"
32 #include "DNA_texture_types.h"
33
34 #include "BKE_colorband.h"
35 #include "BKE_material.h"
36 #include "BKE_key.h"
37
38 void BKE_colorband_init(ColorBand *coba, bool rangetype)
39 {
40         int a;
41
42         coba->data[0].pos = 0.0;
43         coba->data[1].pos = 1.0;
44
45         if (rangetype == 0) {
46                 coba->data[0].r = 0.0;
47                 coba->data[0].g = 0.0;
48                 coba->data[0].b = 0.0;
49                 coba->data[0].a = 0.0;
50
51                 coba->data[1].r = 1.0;
52                 coba->data[1].g = 1.0;
53                 coba->data[1].b = 1.0;
54                 coba->data[1].a = 1.0;
55         }
56         else {
57                 coba->data[0].r = 0.0;
58                 coba->data[0].g = 0.0;
59                 coba->data[0].b = 0.0;
60                 coba->data[0].a = 1.0;
61
62                 coba->data[1].r = 1.0;
63                 coba->data[1].g = 1.0;
64                 coba->data[1].b = 1.0;
65                 coba->data[1].a = 1.0;
66         }
67
68         for (a = 2; a < MAXCOLORBAND; a++) {
69                 coba->data[a].r = 0.5;
70                 coba->data[a].g = 0.5;
71                 coba->data[a].b = 0.5;
72                 coba->data[a].a = 1.0;
73                 coba->data[a].pos = 0.5;
74         }
75
76         coba->tot = 2;
77         coba->cur = 0;
78         coba->color_mode = COLBAND_BLEND_RGB;
79         coba->ipotype = COLBAND_INTERP_LINEAR;
80 }
81
82 static void colorband_init_from_table_rgba_simple(
83         ColorBand *coba,
84         const float (*array)[4], const int array_len)
85 {
86         /* No Re-sample, just de-duplicate. */
87         const float eps = (1.0f / 255.0f) + 1e-6f;
88         BLI_assert(array_len < MAXCOLORBAND);
89         int stops = min_ii(MAXCOLORBAND, array_len);
90         if (stops) {
91                 const float step_size = 1.0f / (float)max_ii(stops - 1, 1);
92                 int i_curr = -1;
93                 for (int i_step = 0; i_step < stops; i_step++) {
94                         if ((i_curr != -1) && compare_v4v4(&coba->data[i_curr].r, array[i_step], eps)) {
95                                 continue;
96                         }
97                         i_curr += 1;
98                         copy_v4_v4(&coba->data[i_curr].r, array[i_step]);
99                         coba->data[i_curr].pos = i_step * step_size;
100                         coba->data[i_curr].cur = i_curr;
101                 }
102                 coba->tot = i_curr + 1;
103                 coba->cur = 0;
104         }
105         else {
106                 /* coba is empty, set 1 black stop */
107                 zero_v3(&coba->data[0].r);
108                 coba->data[0].a = 1.0f;
109                 coba->cur = 0;
110                 coba->tot = 1;
111         }
112 }
113
114
115 /* -------------------------------------------------------------------- */
116 /** \name Color Ramp Re-Sample
117  *
118  * Local functions for #BKE_colorband_init_from_table_rgba
119  * \{ */
120
121 /**
122  * Used for calculating which samples of a color-band to remove (when simplifying).
123  */
124 struct ColorResampleElem {
125         struct ColorResampleElem *next, *prev;
126         HeapNode *node;
127         float rgba[4];
128         float pos;
129 };
130
131 /**
132  * Measure the 'area' of each channel and combine to use as a cost for this samples removal.
133  */
134 static float color_sample_remove_cost(const struct ColorResampleElem *c)
135 {
136         if (c->next == NULL || c->prev == NULL) {
137                 return -1.0f;
138         }
139         float area = 0.0f;
140 #if 0
141         float xy_prev[2], xy_curr[2], xy_next[2];
142         xy_prev[0] = c->prev->pos;
143         xy_curr[0] = c->pos;
144         xy_next[0] = c->next->pos;
145         for (int i = 0; i < 4; i++) {
146                 xy_prev[1] = c->prev->rgba[i];
147                 xy_curr[1] = c->rgba[i];
148                 xy_next[1] = c->next->rgba[i];
149                 area += fabsf(cross_tri_v2(xy_prev, xy_curr, xy_next));
150         }
151 #else
152         /* Above logic, optimized (p: previous, c: current, n: next). */
153         const float xpc = c->prev->pos - c->pos;
154         const float xnc = c->next->pos - c->pos;
155         for (int i = 0; i < 4; i++) {
156                 const float ycn = c->rgba[i] - c->next->rgba[i];
157                 const float ypc = c->prev->rgba[i] - c->rgba[i];
158                 area += fabsf((xpc * ycn) + (ypc * xnc));
159         }
160 #endif
161         return area;
162 }
163
164 /* TODO(campbell): create BLI_math_filter? */
165 static float filter_gauss(float x)
166 {
167         const float gaussfac = 1.6f;
168         const float two_gaussfac2 = 2.0f * gaussfac * gaussfac;
169         x *= 3.0f * gaussfac;
170         return 1.0f / sqrtf((float)M_PI * two_gaussfac2) * expf(-x * x / two_gaussfac2);
171 }
172
173 static void colorband_init_from_table_rgba_resample(
174         ColorBand *coba,
175         const float (*array)[4], const int array_len,
176         bool filter_samples)
177 {
178         BLI_assert(array_len >= 2);
179         const float eps_2x = ((1.0f / 255.0f) + 1e-6f);
180         struct ColorResampleElem *c, *carr = MEM_mallocN(sizeof(*carr) * array_len, __func__);
181         int carr_len = array_len;
182         c = carr;
183         {
184                 const float step_size = 1.0f / (float)(array_len - 1);
185                 for (int i = 0; i < array_len; i++, c++) {
186                         copy_v4_v4(carr[i].rgba, array[i]);
187                         c->next = c + 1;
188                         c->prev = c - 1;
189                         c->pos = i * step_size;
190                 }
191         }
192         carr[0].prev = NULL;
193         carr[array_len - 1].next = NULL;
194
195         /* -2 to remove endpoints. */
196         Heap *heap = BLI_heap_new_ex(array_len - 2);
197         c = carr;
198         for (int i = 0; i < array_len; i++, c++) {
199                 float cost = color_sample_remove_cost(c);
200                 if (cost != -1.0f) {
201                         c->node = BLI_heap_insert(heap, cost, c);
202                 }
203                 else {
204                         c->node = NULL;
205                 }
206         }
207
208         while ((carr_len > 1 && !BLI_heap_is_empty(heap)) &&
209                ((carr_len >= MAXCOLORBAND) || (BLI_heap_top_value(heap) <= eps_2x)))
210         {
211                 c = BLI_heap_pop_min(heap);
212                 struct ColorResampleElem *c_next = c->next, *c_prev = c->prev;
213                 c_prev->next = c_next;
214                 c_next->prev = c_prev;
215                 /* Clear data (not essential, avoid confusion). */
216                 c->prev = c->next = NULL;
217                 c->node = NULL;
218
219                 /* Update adjacent */
220                 for (int i = 0; i < 2; i++) {
221                         struct ColorResampleElem *c_other = i ? c_next : c_prev;
222                         if (c_other->node != NULL) {
223                                 const float cost = color_sample_remove_cost(c_other);
224                                 if (cost != -1.0) {
225                                         BLI_heap_node_value_update(heap, c_other->node, cost);
226                                 }
227                                 else {
228                                         BLI_heap_remove(heap, c_other->node);
229                                         c_other->node = NULL;
230                                 }
231                         }
232                 }
233                 carr_len -= 1;
234         }
235         BLI_heap_free(heap, NULL);
236
237         /* First member is never removed. */
238         int i = 0;
239         BLI_assert(carr_len < MAXCOLORBAND);
240         if (filter_samples == false) {
241                 for (c = carr; c != NULL; c = c->next, i++) {
242                         copy_v4_v4(&coba->data[i].r, c->rgba);
243                         coba->data[i].pos = c->pos;
244                         coba->data[i].cur = i;
245                 }
246         }
247         else {
248                 for (c = carr; c != NULL; c = c->next, i++) {
249                         const int steps_prev = c->prev ? (c - c->prev) - 1 : 0;
250                         const int steps_next = c->next ? (c->next - c) - 1 : 0;
251                         if (steps_prev == 0 && steps_next == 0) {
252                                 copy_v4_v4(&coba->data[i].r, c->rgba);
253                         }
254                         else {
255                                 float rgba[4];
256                                 float rgba_accum = 1;
257                                 copy_v4_v4(rgba, c->rgba);
258
259                                 if (steps_prev) {
260                                         const float step_size = 1.0 / (float)(steps_prev + 1);
261                                         int j = steps_prev;
262                                         for (struct ColorResampleElem *c_other = c - 1; c_other != c->prev; c_other--, j--) {
263                                                 const float step_pos = (float)j * step_size;
264                                                 BLI_assert(step_pos > 0.0f && step_pos < 1.0f);
265                                                 const float f = filter_gauss(step_pos);
266                                                 madd_v4_v4fl(rgba, c_other->rgba, f);
267                                                 rgba_accum += f;
268                                         }
269                                 }
270                                 if (steps_next) {
271                                         const float step_size = 1.0 / (float)(steps_next + 1);
272                                         int j = steps_next;
273                                         for (struct ColorResampleElem *c_other = c + 1; c_other != c->next; c_other++, j--) {
274                                                 const float step_pos = (float)j * step_size;
275                                                 BLI_assert(step_pos > 0.0f && step_pos < 1.0f);
276                                                 const float f = filter_gauss(step_pos);
277                                                 madd_v4_v4fl(rgba, c_other->rgba, f);
278                                                 rgba_accum += f;
279                                         }
280                                 }
281
282                                 mul_v4_v4fl(&coba->data[i].r, rgba, 1.0f / rgba_accum);
283                         }
284                         coba->data[i].pos = c->pos;
285                         coba->data[i].cur = i;
286                 }
287         }
288         BLI_assert(i == carr_len);
289         coba->tot = i;
290         coba->cur = 0;
291
292         MEM_freeN(carr);
293 }
294
295 void BKE_colorband_init_from_table_rgba(
296         ColorBand *coba,
297         const float (*array)[4], const int array_len,
298         bool filter_samples)
299 {
300         /* Note, we could use MAXCOLORBAND here, but results of re-sampling are nicer,
301          * avoid different behavior when limit is hit. */
302         if (array_len < 2) {
303                 /* No Re-sample, just de-duplicate. */
304                 colorband_init_from_table_rgba_simple(coba, array, array_len);
305         }
306         else {
307                 /* Re-sample */
308                 colorband_init_from_table_rgba_resample(coba, array, array_len, filter_samples);
309         }
310 }
311
312 /** \} */
313
314 ColorBand *BKE_colorband_add(bool rangetype)
315 {
316         ColorBand *coba;
317
318         coba = MEM_callocN(sizeof(ColorBand), "colorband");
319         BKE_colorband_init(coba, rangetype);
320
321         return coba;
322 }
323
324 /* ------------------------------------------------------------------------- */
325
326 static float colorband_hue_interp(
327         const int ipotype_hue,
328         const float mfac, const float fac,
329         float h1, float h2)
330 {
331         float h_interp;
332         int mode = 0;
333
334 #define HUE_INTERP(h_a, h_b) ((mfac * (h_a)) + (fac * (h_b)))
335 #define HUE_MOD(h) (((h) < 1.0f) ? (h) : (h) - 1.0f)
336
337         h1 = HUE_MOD(h1);
338         h2 = HUE_MOD(h2);
339
340         BLI_assert(h1 >= 0.0f && h1 < 1.0f);
341         BLI_assert(h2 >= 0.0f && h2 < 1.0f);
342
343         switch (ipotype_hue) {
344                 case COLBAND_HUE_NEAR:
345                 {
346                         if      ((h1 < h2) && (h2 - h1) > +0.5f) mode = 1;
347                         else if ((h1 > h2) && (h2 - h1) < -0.5f) mode = 2;
348                         else                                     mode = 0;
349                         break;
350                 }
351                 case COLBAND_HUE_FAR:
352                 {
353                         if      ((h1 < h2) && (h2 - h1) < +0.5f) mode = 1;
354                         else if ((h1 > h2) && (h2 - h1) > -0.5f) mode = 2;
355                         else                                     mode = 0;
356                         break;
357                 }
358                 case COLBAND_HUE_CCW:
359                 {
360                         if (h1 > h2) mode = 2;
361                         else         mode = 0;
362                         break;
363                 }
364                 case COLBAND_HUE_CW:
365                 {
366                         if (h1 < h2) mode = 1;
367                         else         mode = 0;
368                         break;
369                 }
370         }
371
372         switch (mode) {
373                 case 0:
374                         h_interp = HUE_INTERP(h1, h2);
375                         break;
376                 case 1:
377                         h_interp = HUE_INTERP(h1 + 1.0f, h2);
378                         h_interp = HUE_MOD(h_interp);
379                         break;
380                 case 2:
381                         h_interp = HUE_INTERP(h1, h2 + 1.0f);
382                         h_interp = HUE_MOD(h_interp);
383                         break;
384         }
385
386         BLI_assert(h_interp >= 0.0f && h_interp < 1.0f);
387
388 #undef HUE_INTERP
389 #undef HUE_MOD
390
391         return h_interp;
392 }
393
394 bool BKE_colorband_evaluate(const ColorBand *coba, float in, float out[4])
395 {
396         const CBData *cbd1, *cbd2, *cbd0, *cbd3;
397         float fac;
398         int ipotype;
399         int a;
400
401         if (coba == NULL || coba->tot == 0) return false;
402
403         cbd1 = coba->data;
404
405         ipotype = (coba->color_mode == COLBAND_BLEND_RGB) ? coba->ipotype : COLBAND_INTERP_LINEAR;
406
407         if (coba->tot == 1) {
408                 out[0] = cbd1->r;
409                 out[1] = cbd1->g;
410                 out[2] = cbd1->b;
411                 out[3] = cbd1->a;
412         }
413         else if ((in <= cbd1->pos) && ELEM(ipotype, COLBAND_INTERP_LINEAR, COLBAND_INTERP_EASE)) {
414                 out[0] = cbd1->r;
415                 out[1] = cbd1->g;
416                 out[2] = cbd1->b;
417                 out[3] = cbd1->a;
418         }
419         else {
420                 CBData left, right;
421
422                 /* we're looking for first pos > in */
423                 for (a = 0; a < coba->tot; a++, cbd1++) {
424                         if (cbd1->pos > in) {
425                                 break;
426                         }
427                 }
428
429                 if (a == coba->tot) {
430                         cbd2 = cbd1 - 1;
431                         right = *cbd2;
432                         right.pos = 1.0f;
433                         cbd1 = &right;
434                 }
435                 else if (a == 0) {
436                         left = *cbd1;
437                         left.pos = 0.0f;
438                         cbd2 = &left;
439                 }
440                 else {
441                         cbd2 = cbd1 - 1;
442                 }
443
444                 if ((in >= cbd1->pos) && ELEM(ipotype, COLBAND_INTERP_LINEAR, COLBAND_INTERP_EASE)) {
445                         out[0] = cbd1->r;
446                         out[1] = cbd1->g;
447                         out[2] = cbd1->b;
448                         out[3] = cbd1->a;
449                 }
450                 else {
451
452                         if (cbd2->pos != cbd1->pos) {
453                                 fac = (in - cbd1->pos) / (cbd2->pos - cbd1->pos);
454                         }
455                         else {
456                                 /* was setting to 0.0 in 2.56 & previous, but this
457                                  * is incorrect for the last element, see [#26732] */
458                                 fac = (a != coba->tot) ? 0.0f : 1.0f;
459                         }
460
461                         if (ipotype == COLBAND_INTERP_CONSTANT) {
462                                 /* constant */
463                                 out[0] = cbd2->r;
464                                 out[1] = cbd2->g;
465                                 out[2] = cbd2->b;
466                                 out[3] = cbd2->a;
467                         }
468                         else if (ipotype >= COLBAND_INTERP_B_SPLINE) {
469                                 /* ipo from right to left: 3 2 1 0 */
470                                 float t[4];
471
472                                 if (a >= coba->tot - 1) cbd0 = cbd1;
473                                 else cbd0 = cbd1 + 1;
474                                 if (a < 2) cbd3 = cbd2;
475                                 else cbd3 = cbd2 - 1;
476
477                                 CLAMP(fac, 0.0f, 1.0f);
478
479                                 if (ipotype == COLBAND_INTERP_CARDINAL) {
480                                         key_curve_position_weights(fac, t, KEY_CARDINAL);
481                                 }
482                                 else {
483                                         key_curve_position_weights(fac, t, KEY_BSPLINE);
484                                 }
485
486                                 out[0] = t[3] * cbd3->r + t[2] * cbd2->r + t[1] * cbd1->r + t[0] * cbd0->r;
487                                 out[1] = t[3] * cbd3->g + t[2] * cbd2->g + t[1] * cbd1->g + t[0] * cbd0->g;
488                                 out[2] = t[3] * cbd3->b + t[2] * cbd2->b + t[1] * cbd1->b + t[0] * cbd0->b;
489                                 out[3] = t[3] * cbd3->a + t[2] * cbd2->a + t[1] * cbd1->a + t[0] * cbd0->a;
490                                 CLAMP(out[0], 0.0f, 1.0f);
491                                 CLAMP(out[1], 0.0f, 1.0f);
492                                 CLAMP(out[2], 0.0f, 1.0f);
493                                 CLAMP(out[3], 0.0f, 1.0f);
494                         }
495                         else {
496                                 float mfac;
497
498                                 if (ipotype == COLBAND_INTERP_EASE) {
499                                         mfac = fac * fac;
500                                         fac = 3.0f * mfac - 2.0f * mfac * fac;
501                                 }
502
503                                 mfac = 1.0f - fac;
504
505                                 if (UNLIKELY(coba->color_mode == COLBAND_BLEND_HSV)) {
506                                         float col1[3], col2[3];
507
508                                         rgb_to_hsv_v(&cbd1->r, col1);
509                                         rgb_to_hsv_v(&cbd2->r, col2);
510
511                                         out[0] = colorband_hue_interp(coba->ipotype_hue, mfac, fac, col1[0], col2[0]);
512                                         out[1] = mfac * col1[1] + fac * col2[1];
513                                         out[2] = mfac * col1[2] + fac * col2[2];
514                                         out[3] = mfac * cbd1->a + fac * cbd2->a;
515
516                                         hsv_to_rgb_v(out, out);
517                                 }
518                                 else if (UNLIKELY(coba->color_mode == COLBAND_BLEND_HSL)) {
519                                         float col1[3], col2[3];
520
521                                         rgb_to_hsl_v(&cbd1->r, col1);
522                                         rgb_to_hsl_v(&cbd2->r, col2);
523
524                                         out[0] = colorband_hue_interp(coba->ipotype_hue, mfac, fac, col1[0], col2[0]);
525                                         out[1] = mfac * col1[1] + fac * col2[1];
526                                         out[2] = mfac * col1[2] + fac * col2[2];
527                                         out[3] = mfac * cbd1->a + fac * cbd2->a;
528
529                                         hsl_to_rgb_v(out, out);
530                                 }
531                                 else {
532                                         /* COLBAND_BLEND_RGB */
533                                         out[0] = mfac * cbd1->r + fac * cbd2->r;
534                                         out[1] = mfac * cbd1->g + fac * cbd2->g;
535                                         out[2] = mfac * cbd1->b + fac * cbd2->b;
536                                         out[3] = mfac * cbd1->a + fac * cbd2->a;
537                                 }
538                         }
539                 }
540         }
541         return true;   /* OK */
542 }
543
544 void BKE_colorband_evaluate_table_rgba(const ColorBand *coba, float **array, int *size)
545 {
546         int a;
547
548         *size = CM_TABLE + 1;
549         *array = MEM_callocN(sizeof(float) * (*size) * 4, "ColorBand");
550
551         for (a = 0; a < *size; a++)
552                 BKE_colorband_evaluate(coba, (float)a / (float)CM_TABLE, &(*array)[a * 4]);
553 }
554
555 static int vergcband(const void *a1, const void *a2)
556 {
557         const CBData *x1 = a1, *x2 = a2;
558
559         if (x1->pos > x2->pos) return 1;
560         else if (x1->pos < x2->pos) return -1;
561         return 0;
562 }
563
564 void BKE_colorband_update_sort(ColorBand *coba)
565 {
566         int a;
567
568         if (coba->tot < 2)
569                 return;
570
571         for (a = 0; a < coba->tot; a++)
572                 coba->data[a].cur = a;
573
574         qsort(coba->data, coba->tot, sizeof(CBData), vergcband);
575
576         for (a = 0; a < coba->tot; a++) {
577                 if (coba->data[a].cur == coba->cur) {
578                         coba->cur = a;
579                         break;
580                 }
581         }
582 }
583
584 CBData *BKE_colorband_element_add(struct ColorBand *coba, float position)
585 {
586         if (coba->tot == MAXCOLORBAND) {
587                 return NULL;
588         }
589         else {
590                 CBData *xnew;
591
592                 xnew = &coba->data[coba->tot];
593                 xnew->pos = position;
594
595                 if (coba->tot != 0) {
596                         BKE_colorband_evaluate(coba, position, &xnew->r);
597                 }
598                 else {
599                         zero_v4(&xnew->r);
600                 }
601         }
602
603         coba->tot++;
604         coba->cur = coba->tot - 1;
605
606         BKE_colorband_update_sort(coba);
607
608         return coba->data + coba->cur;
609 }
610
611 int BKE_colorband_element_remove(struct ColorBand *coba, int index)
612 {
613         int a;
614
615         if (coba->tot < 2)
616                 return 0;
617
618         if (index < 0 || index >= coba->tot)
619                 return 0;
620
621         coba->tot--;
622         for (a = index; a < coba->tot; a++) {
623                 coba->data[a] = coba->data[a + 1];
624         }
625         if (coba->cur) coba->cur--;
626         return 1;
627 }