Fix assert in some cases when using DataTransfer modifier for custom normals.
[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
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(ColorBand *coba,
83                                                   const float (*array)[4],
84                                                   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 /** \name Color Ramp Re-Sample
116  *
117  * Local functions for #BKE_colorband_init_from_table_rgba
118  * \{ */
119
120 /**
121  * Used for calculating which samples of a color-band to remove (when simplifying).
122  */
123 struct ColorResampleElem {
124   struct ColorResampleElem *next, *prev;
125   HeapNode *node;
126   float rgba[4];
127   float pos;
128 };
129
130 /**
131  * Measure the 'area' of each channel and combine to use as a cost for this samples removal.
132  */
133 static float color_sample_remove_cost(const struct ColorResampleElem *c)
134 {
135   if (c->next == NULL || c->prev == NULL) {
136     return -1.0f;
137   }
138   float area = 0.0f;
139 #if 0
140   float xy_prev[2], xy_curr[2], xy_next[2];
141   xy_prev[0] = c->prev->pos;
142   xy_curr[0] = c->pos;
143   xy_next[0] = c->next->pos;
144   for (int i = 0; i < 4; i++) {
145     xy_prev[1] = c->prev->rgba[i];
146     xy_curr[1] = c->rgba[i];
147     xy_next[1] = c->next->rgba[i];
148     area += fabsf(cross_tri_v2(xy_prev, xy_curr, xy_next));
149   }
150 #else
151   /* Above logic, optimized (p: previous, c: current, n: next). */
152   const float xpc = c->prev->pos - c->pos;
153   const float xnc = c->next->pos - c->pos;
154   for (int i = 0; i < 4; i++) {
155     const float ycn = c->rgba[i] - c->next->rgba[i];
156     const float ypc = c->prev->rgba[i] - c->rgba[i];
157     area += fabsf((xpc * ycn) + (ypc * xnc));
158   }
159 #endif
160   return area;
161 }
162
163 /* TODO(campbell): create BLI_math_filter? */
164 static float filter_gauss(float x)
165 {
166   const float gaussfac = 1.6f;
167   const float two_gaussfac2 = 2.0f * gaussfac * gaussfac;
168   x *= 3.0f * gaussfac;
169   return 1.0f / sqrtf((float)M_PI * two_gaussfac2) * expf(-x * x / two_gaussfac2);
170 }
171
172 static void colorband_init_from_table_rgba_resample(ColorBand *coba,
173                                                     const float (*array)[4],
174                                                     const int array_len,
175                                                     bool filter_samples)
176 {
177   BLI_assert(array_len >= 2);
178   const float eps_2x = ((1.0f / 255.0f) + 1e-6f);
179   struct ColorResampleElem *c, *carr = MEM_mallocN(sizeof(*carr) * array_len, __func__);
180   int carr_len = array_len;
181   c = carr;
182   {
183     const float step_size = 1.0f / (float)(array_len - 1);
184     for (int i = 0; i < array_len; i++, c++) {
185       copy_v4_v4(carr[i].rgba, array[i]);
186       c->next = c + 1;
187       c->prev = c - 1;
188       c->pos = i * step_size;
189     }
190   }
191   carr[0].prev = NULL;
192   carr[array_len - 1].next = NULL;
193
194   /* -2 to remove endpoints. */
195   Heap *heap = BLI_heap_new_ex(array_len - 2);
196   c = carr;
197   for (int i = 0; i < array_len; i++, c++) {
198     float cost = color_sample_remove_cost(c);
199     if (cost != -1.0f) {
200       c->node = BLI_heap_insert(heap, cost, c);
201     }
202     else {
203       c->node = NULL;
204     }
205   }
206
207   while ((carr_len > 1 && !BLI_heap_is_empty(heap)) &&
208          ((carr_len >= MAXCOLORBAND) || (BLI_heap_top_value(heap) <= eps_2x))) {
209     c = BLI_heap_pop_min(heap);
210     struct ColorResampleElem *c_next = c->next, *c_prev = c->prev;
211     c_prev->next = c_next;
212     c_next->prev = c_prev;
213     /* Clear data (not essential, avoid confusion). */
214     c->prev = c->next = NULL;
215     c->node = NULL;
216
217     /* Update adjacent */
218     for (int i = 0; i < 2; i++) {
219       struct ColorResampleElem *c_other = i ? c_next : c_prev;
220       if (c_other->node != NULL) {
221         const float cost = color_sample_remove_cost(c_other);
222         if (cost != -1.0) {
223           BLI_heap_node_value_update(heap, c_other->node, cost);
224         }
225         else {
226           BLI_heap_remove(heap, c_other->node);
227           c_other->node = NULL;
228         }
229       }
230     }
231     carr_len -= 1;
232   }
233   BLI_heap_free(heap, NULL);
234
235   /* First member is never removed. */
236   int i = 0;
237   BLI_assert(carr_len < MAXCOLORBAND);
238   if (filter_samples == false) {
239     for (c = carr; c != NULL; c = c->next, i++) {
240       copy_v4_v4(&coba->data[i].r, c->rgba);
241       coba->data[i].pos = c->pos;
242       coba->data[i].cur = i;
243     }
244   }
245   else {
246     for (c = carr; c != NULL; c = c->next, i++) {
247       const int steps_prev = c->prev ? (c - c->prev) - 1 : 0;
248       const int steps_next = c->next ? (c->next - c) - 1 : 0;
249       if (steps_prev == 0 && steps_next == 0) {
250         copy_v4_v4(&coba->data[i].r, c->rgba);
251       }
252       else {
253         float rgba[4];
254         float rgba_accum = 1;
255         copy_v4_v4(rgba, c->rgba);
256
257         if (steps_prev) {
258           const float step_size = 1.0 / (float)(steps_prev + 1);
259           int j = steps_prev;
260           for (struct ColorResampleElem *c_other = c - 1; c_other != c->prev; c_other--, j--) {
261             const float step_pos = (float)j * step_size;
262             BLI_assert(step_pos > 0.0f && step_pos < 1.0f);
263             const float f = filter_gauss(step_pos);
264             madd_v4_v4fl(rgba, c_other->rgba, f);
265             rgba_accum += f;
266           }
267         }
268         if (steps_next) {
269           const float step_size = 1.0 / (float)(steps_next + 1);
270           int j = steps_next;
271           for (struct ColorResampleElem *c_other = c + 1; c_other != c->next; c_other++, j--) {
272             const float step_pos = (float)j * step_size;
273             BLI_assert(step_pos > 0.0f && step_pos < 1.0f);
274             const float f = filter_gauss(step_pos);
275             madd_v4_v4fl(rgba, c_other->rgba, f);
276             rgba_accum += f;
277           }
278         }
279
280         mul_v4_v4fl(&coba->data[i].r, rgba, 1.0f / rgba_accum);
281       }
282       coba->data[i].pos = c->pos;
283       coba->data[i].cur = i;
284     }
285   }
286   BLI_assert(i == carr_len);
287   coba->tot = i;
288   coba->cur = 0;
289
290   MEM_freeN(carr);
291 }
292
293 void BKE_colorband_init_from_table_rgba(ColorBand *coba,
294                                         const float (*array)[4],
295                                         const int array_len,
296                                         bool filter_samples)
297 {
298   /* Note, we could use MAXCOLORBAND here, but results of re-sampling are nicer,
299    * avoid different behavior when limit is hit. */
300   if (array_len < 2) {
301     /* No Re-sample, just de-duplicate. */
302     colorband_init_from_table_rgba_simple(coba, array, array_len);
303   }
304   else {
305     /* Re-sample */
306     colorband_init_from_table_rgba_resample(coba, array, array_len, filter_samples);
307   }
308 }
309
310 /** \} */
311
312 ColorBand *BKE_colorband_add(bool rangetype)
313 {
314   ColorBand *coba;
315
316   coba = MEM_callocN(sizeof(ColorBand), "colorband");
317   BKE_colorband_init(coba, rangetype);
318
319   return coba;
320 }
321
322 /* ------------------------------------------------------------------------- */
323
324 static float colorband_hue_interp(
325     const int ipotype_hue, const float mfac, const float fac, float h1, float h2)
326 {
327   float h_interp;
328   int mode = 0;
329
330 #define HUE_INTERP(h_a, h_b) ((mfac * (h_a)) + (fac * (h_b)))
331 #define HUE_MOD(h) (((h) < 1.0f) ? (h) : (h)-1.0f)
332
333   h1 = HUE_MOD(h1);
334   h2 = HUE_MOD(h2);
335
336   BLI_assert(h1 >= 0.0f && h1 < 1.0f);
337   BLI_assert(h2 >= 0.0f && h2 < 1.0f);
338
339   switch (ipotype_hue) {
340     case COLBAND_HUE_NEAR: {
341       if ((h1 < h2) && (h2 - h1) > +0.5f) {
342         mode = 1;
343       }
344       else if ((h1 > h2) && (h2 - h1) < -0.5f) {
345         mode = 2;
346       }
347       else {
348         mode = 0;
349       }
350       break;
351     }
352     case COLBAND_HUE_FAR: {
353       /* Do full loop in Hue space in case both stops are the same... */
354       if (h1 == h2) {
355         mode = 1;
356       }
357       else if ((h1 < h2) && (h2 - h1) < +0.5f) {
358         mode = 1;
359       }
360       else if ((h1 > h2) && (h2 - h1) > -0.5f) {
361         mode = 2;
362       }
363       else {
364         mode = 0;
365       }
366       break;
367     }
368     case COLBAND_HUE_CCW: {
369       if (h1 > h2) {
370         mode = 2;
371       }
372       else {
373         mode = 0;
374       }
375       break;
376     }
377     case COLBAND_HUE_CW: {
378       if (h1 < h2) {
379         mode = 1;
380       }
381       else {
382         mode = 0;
383       }
384       break;
385     }
386   }
387
388   switch (mode) {
389     case 0:
390       h_interp = HUE_INTERP(h1, h2);
391       break;
392     case 1:
393       h_interp = HUE_INTERP(h1 + 1.0f, h2);
394       h_interp = HUE_MOD(h_interp);
395       break;
396     case 2:
397       h_interp = HUE_INTERP(h1, h2 + 1.0f);
398       h_interp = HUE_MOD(h_interp);
399       break;
400   }
401
402   BLI_assert(h_interp >= 0.0f && h_interp < 1.0f);
403
404 #undef HUE_INTERP
405 #undef HUE_MOD
406
407   return h_interp;
408 }
409
410 bool BKE_colorband_evaluate(const ColorBand *coba, float in, float out[4])
411 {
412   const CBData *cbd1, *cbd2, *cbd0, *cbd3;
413   float fac;
414   int ipotype;
415   int a;
416
417   if (coba == NULL || coba->tot == 0) {
418     return false;
419   }
420
421   cbd1 = coba->data;
422
423   /* Note: when ipotype >= COLBAND_INTERP_B_SPLINE,
424    * we cannot do early-out with a constant color before first color stop and after last one,
425    * because interpolation starts before and ends after those... */
426   ipotype = (coba->color_mode == COLBAND_BLEND_RGB) ? coba->ipotype : COLBAND_INTERP_LINEAR;
427
428   if (coba->tot == 1) {
429     out[0] = cbd1->r;
430     out[1] = cbd1->g;
431     out[2] = cbd1->b;
432     out[3] = cbd1->a;
433   }
434   else if ((in <= cbd1->pos) &&
435            ELEM(ipotype, COLBAND_INTERP_LINEAR, COLBAND_INTERP_EASE, COLBAND_INTERP_CONSTANT)) {
436     /* We are before first color stop. */
437     out[0] = cbd1->r;
438     out[1] = cbd1->g;
439     out[2] = cbd1->b;
440     out[3] = cbd1->a;
441   }
442   else {
443     CBData left, right;
444
445     /* we're looking for first pos > in */
446     for (a = 0; a < coba->tot; a++, cbd1++) {
447       if (cbd1->pos > in) {
448         break;
449       }
450     }
451
452     if (a == coba->tot) {
453       cbd2 = cbd1 - 1;
454       right = *cbd2;
455       right.pos = 1.0f;
456       cbd1 = &right;
457     }
458     else if (a == 0) {
459       left = *cbd1;
460       left.pos = 0.0f;
461       cbd2 = &left;
462     }
463     else {
464       cbd2 = cbd1 - 1;
465     }
466
467     if ((a == coba->tot) &&
468         ELEM(ipotype, COLBAND_INTERP_LINEAR, COLBAND_INTERP_EASE, COLBAND_INTERP_CONSTANT)) {
469       /* We are after last color stop. */
470       out[0] = cbd2->r;
471       out[1] = cbd2->g;
472       out[2] = cbd2->b;
473       out[3] = cbd2->a;
474     }
475     else if (ipotype == COLBAND_INTERP_CONSTANT) {
476       /* constant */
477       out[0] = cbd2->r;
478       out[1] = cbd2->g;
479       out[2] = cbd2->b;
480       out[3] = cbd2->a;
481     }
482     else {
483       if (cbd2->pos != cbd1->pos) {
484         fac = (in - cbd1->pos) / (cbd2->pos - cbd1->pos);
485       }
486       else {
487         /* was setting to 0.0 in 2.56 & previous, but this
488          * is incorrect for the last element, see [#26732] */
489         fac = (a != coba->tot) ? 0.0f : 1.0f;
490       }
491
492       if (ELEM(ipotype, COLBAND_INTERP_B_SPLINE, COLBAND_INTERP_CARDINAL)) {
493         /* ipo from right to left: 3 2 1 0 */
494         float t[4];
495
496         if (a >= coba->tot - 1) {
497           cbd0 = cbd1;
498         }
499         else {
500           cbd0 = cbd1 + 1;
501         }
502         if (a < 2) {
503           cbd3 = cbd2;
504         }
505         else {
506           cbd3 = cbd2 - 1;
507         }
508
509         CLAMP(fac, 0.0f, 1.0f);
510
511         if (ipotype == COLBAND_INTERP_CARDINAL) {
512           key_curve_position_weights(fac, t, KEY_CARDINAL);
513         }
514         else {
515           key_curve_position_weights(fac, t, KEY_BSPLINE);
516         }
517
518         out[0] = t[3] * cbd3->r + t[2] * cbd2->r + t[1] * cbd1->r + t[0] * cbd0->r;
519         out[1] = t[3] * cbd3->g + t[2] * cbd2->g + t[1] * cbd1->g + t[0] * cbd0->g;
520         out[2] = t[3] * cbd3->b + t[2] * cbd2->b + t[1] * cbd1->b + t[0] * cbd0->b;
521         out[3] = t[3] * cbd3->a + t[2] * cbd2->a + t[1] * cbd1->a + t[0] * cbd0->a;
522         CLAMP(out[0], 0.0f, 1.0f);
523         CLAMP(out[1], 0.0f, 1.0f);
524         CLAMP(out[2], 0.0f, 1.0f);
525         CLAMP(out[3], 0.0f, 1.0f);
526       }
527       else {
528         if (ipotype == COLBAND_INTERP_EASE) {
529           const float fac2 = fac * fac;
530           fac = 3.0f * fac2 - 2.0f * fac2 * fac;
531         }
532         const float mfac = 1.0f - fac;
533
534         if (UNLIKELY(coba->color_mode == COLBAND_BLEND_HSV)) {
535           float col1[3], col2[3];
536
537           rgb_to_hsv_v(&cbd1->r, col1);
538           rgb_to_hsv_v(&cbd2->r, col2);
539
540           out[0] = colorband_hue_interp(coba->ipotype_hue, mfac, fac, col1[0], col2[0]);
541           out[1] = mfac * col1[1] + fac * col2[1];
542           out[2] = mfac * col1[2] + fac * col2[2];
543           out[3] = mfac * cbd1->a + fac * cbd2->a;
544
545           hsv_to_rgb_v(out, out);
546         }
547         else if (UNLIKELY(coba->color_mode == COLBAND_BLEND_HSL)) {
548           float col1[3], col2[3];
549
550           rgb_to_hsl_v(&cbd1->r, col1);
551           rgb_to_hsl_v(&cbd2->r, col2);
552
553           out[0] = colorband_hue_interp(coba->ipotype_hue, mfac, fac, col1[0], col2[0]);
554           out[1] = mfac * col1[1] + fac * col2[1];
555           out[2] = mfac * col1[2] + fac * col2[2];
556           out[3] = mfac * cbd1->a + fac * cbd2->a;
557
558           hsl_to_rgb_v(out, out);
559         }
560         else {
561           /* COLBAND_BLEND_RGB */
562           out[0] = mfac * cbd1->r + fac * cbd2->r;
563           out[1] = mfac * cbd1->g + fac * cbd2->g;
564           out[2] = mfac * cbd1->b + fac * cbd2->b;
565           out[3] = mfac * cbd1->a + fac * cbd2->a;
566         }
567       }
568     }
569   }
570
571   return true; /* OK */
572 }
573
574 void BKE_colorband_evaluate_table_rgba(const ColorBand *coba, float **array, int *size)
575 {
576   int a;
577
578   *size = CM_TABLE + 1;
579   *array = MEM_callocN(sizeof(float) * (*size) * 4, "ColorBand");
580
581   for (a = 0; a < *size; a++) {
582     BKE_colorband_evaluate(coba, (float)a / (float)CM_TABLE, &(*array)[a * 4]);
583   }
584 }
585
586 static int vergcband(const void *a1, const void *a2)
587 {
588   const CBData *x1 = a1, *x2 = a2;
589
590   if (x1->pos > x2->pos) {
591     return 1;
592   }
593   else if (x1->pos < x2->pos) {
594     return -1;
595   }
596   return 0;
597 }
598
599 void BKE_colorband_update_sort(ColorBand *coba)
600 {
601   int a;
602
603   if (coba->tot < 2) {
604     return;
605   }
606
607   for (a = 0; a < coba->tot; a++) {
608     coba->data[a].cur = a;
609   }
610
611   qsort(coba->data, coba->tot, sizeof(CBData), vergcband);
612
613   for (a = 0; a < coba->tot; a++) {
614     if (coba->data[a].cur == coba->cur) {
615       coba->cur = a;
616       break;
617     }
618   }
619 }
620
621 CBData *BKE_colorband_element_add(struct ColorBand *coba, float position)
622 {
623   if (coba->tot == MAXCOLORBAND) {
624     return NULL;
625   }
626   else {
627     CBData *xnew;
628
629     xnew = &coba->data[coba->tot];
630     xnew->pos = position;
631
632     if (coba->tot != 0) {
633       BKE_colorband_evaluate(coba, position, &xnew->r);
634     }
635     else {
636       zero_v4(&xnew->r);
637     }
638   }
639
640   coba->tot++;
641   coba->cur = coba->tot - 1;
642
643   BKE_colorband_update_sort(coba);
644
645   return coba->data + coba->cur;
646 }
647
648 int BKE_colorband_element_remove(struct ColorBand *coba, int index)
649 {
650   int a;
651
652   if (coba->tot < 2) {
653     return 0;
654   }
655
656   if (index < 0 || index >= coba->tot) {
657     return 0;
658   }
659
660   coba->tot--;
661   for (a = index; a < coba->tot; a++) {
662     coba->data[a] = coba->data[a + 1];
663   }
664   if (coba->cur) {
665     coba->cur--;
666   }
667   return 1;
668 }