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