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