gimppickable-contiguous-region.c 23.3 KB
Newer Older
1
/* GIMP - The GNU Image Manipulation Program
2 3
 * Copyright (C) 1995 Spencer Kimball and Peter Mattis
 *
4
 * This program is free software: you can redistribute it and/or modify
5
 * it under the terms of the GNU General Public License as published by
6
 * the Free Software Foundation; either version 3 of the License, or
7 8 9 10 11 12 13 14
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
15
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
16 17 18 19
 */

#include "config.h"

20 21
#include <stdlib.h>

22
#include <cairo.h>
23
#include <gegl.h>
24
#include <gdk-pixbuf/gdk-pixbuf.h>
25 26

#include "libgimpcolor/gimpcolor.h"
27
#include "libgimpmath/gimpmath.h"
28 29 30

#include "core-types.h"

31 32
#include "gegl/gimp-babl.h"

33
#include "gimp-utils.h" /* GIMP_TIMER */
34
#include "gimppickable.h"
35
#include "gimppickable-contiguous-region.h"
36 37 38 39


/*  local function prototypes  */

40 41 42 43
static const Babl * choose_format         (GeglBuffer          *buffer,
                                           GimpSelectCriterion  select_criterion,
                                           gint                *n_components,
                                           gboolean            *has_alpha);
44 45
static gfloat   pixel_difference          (const gfloat        *col1,
                                           const gfloat        *col2,
46
                                           gboolean             antialias,
47 48
                                           gfloat               threshold,
                                           gint                 n_components,
49 50 51
                                           gboolean             has_alpha,
                                           gboolean             select_transparent,
                                           GimpSelectCriterion  select_criterion);
52 53 54 55 56 57 58 59 60 61 62 63 64
static void     push_segment              (GQueue              *segment_queue,
                                           gint                 y,
                                           gint                 old_y,
                                           gint                 start,
                                           gint                 end,
                                           gint                 new_y,
                                           gint                 new_start,
                                           gint                 new_end);
static void     pop_segment               (GQueue              *segment_queue,
                                           gint                *y,
                                           gint                *old_y,
                                           gint                *start,
                                           gint                *end);
65
static gboolean find_contiguous_segment   (const gfloat        *col,
66
                                           GeglBuffer          *src_buffer,
67
                                           GeglSampler         *src_sampler,
68 69
                                           GeglBuffer          *mask_buffer,
                                           const Babl          *src_format,
70
                                           const Babl          *mask_format,
71
                                           gint                 n_components,
72
                                           gboolean             has_alpha,
73
                                           gint                 width,
74 75 76
                                           gboolean             select_transparent,
                                           GimpSelectCriterion  select_criterion,
                                           gboolean             antialias,
77
                                           gfloat               threshold,
78 79
                                           gint                 initial_x,
                                           gint                 initial_y,
80
                                           gint                *start,
81 82 83
                                           gint                *end,
                                           gfloat              *row);
static void     find_contiguous_region    (GeglBuffer          *src_buffer,
84 85
                                           GeglBuffer          *mask_buffer,
                                           const Babl          *format,
86 87
                                           gint                 n_components,
                                           gboolean             has_alpha,
88 89 90
                                           gboolean             select_transparent,
                                           GimpSelectCriterion  select_criterion,
                                           gboolean             antialias,
91
                                           gfloat               threshold,
92
                                           gboolean             diagonal_neighbors,
93 94
                                           gint                 x,
                                           gint                 y,
95
                                           const gfloat        *col);
96 97 98 99


/*  public functions  */

100
GeglBuffer *
101 102 103 104 105
gimp_pickable_contiguous_region_by_seed (GimpPickable        *pickable,
                                         gboolean             antialias,
                                         gfloat               threshold,
                                         gboolean             select_transparent,
                                         GimpSelectCriterion  select_criterion,
106
                                         gboolean             diagonal_neighbors,
107 108
                                         gint                 x,
                                         gint                 y)
109
{
110 111 112 113 114 115 116
  GeglBuffer    *src_buffer;
  GeglBuffer    *mask_buffer;
  const Babl    *format;
  GeglRectangle  extent;
  gint           n_components;
  gboolean       has_alpha;
  gfloat         start_col[MAX_CHANNELS];
117 118

  g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);
119

120 121
  gimp_pickable_flush (pickable);

122
  src_buffer = gimp_pickable_get_buffer (pickable);
123

124 125
  format = choose_format (src_buffer, select_criterion,
                          &n_components, &has_alpha);
126

127
  gegl_buffer_sample (src_buffer, x, y, NULL, start_col, format,
128 129
                      GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);

130
  if (has_alpha)
131 132
    {
      if (select_transparent)
133
        {
134 135 136
          /*  don't select transparent regions if the start pixel isn't
           *  fully transparent
           */
137
          if (start_col[n_components - 1] > 0)
138
            select_transparent = FALSE;
139
        }
140
    }
141 142 143 144 145
  else
    {
      select_transparent = FALSE;
    }

146
  extent = *gegl_buffer_get_extent (src_buffer);
147

148
  mask_buffer = gegl_buffer_new (&extent, babl_format ("Y float"));
149

150 151 152 153 154 155 156 157
  if (x >= extent.x && x < (extent.x + extent.width) &&
      y >= extent.y && y < (extent.y + extent.height))
    {
      GIMP_TIMER_START();

      find_contiguous_region (src_buffer, mask_buffer,
                              format, n_components, has_alpha,
                              select_transparent, select_criterion,
158
                              antialias, threshold, diagonal_neighbors,
159
                              x, y, start_col);
160

161 162
      GIMP_TIMER_END("foo");
    }
163

164
  return mask_buffer;
165 166
}

167
GeglBuffer *
168 169 170 171 172 173
gimp_pickable_contiguous_region_by_color (GimpPickable        *pickable,
                                          gboolean             antialias,
                                          gfloat               threshold,
                                          gboolean             select_transparent,
                                          GimpSelectCriterion  select_criterion,
                                          const GimpRGB       *color)
174
{
175
  /*  Scan over the pickable's active layer, finding pixels within the
Sven Neumann's avatar
Sven Neumann committed
176 177
   *  specified threshold from the given R, G, & B values.  If
   *  antialiasing is on, use the same antialiasing scheme as in
178
   *  fuzzy_select.  Modify the pickable's mask to reflect the
Sven Neumann's avatar
Sven Neumann committed
179
   *  additional selection
180
   */
181 182 183
  GeglBufferIterator *iter;
  GeglBuffer         *src_buffer;
  GeglBuffer         *mask_buffer;
184 185
  const Babl         *format;
  gint                n_components;
186
  gboolean            has_alpha;
187
  gfloat              start_col[MAX_CHANNELS];
188

189
  g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);
190 191
  g_return_val_if_fail (color != NULL, NULL);

192 193
  gimp_pickable_flush (pickable);

194
  src_buffer = gimp_pickable_get_buffer (pickable);
195

196 197 198 199
  format = choose_format (src_buffer, select_criterion,
                          &n_components, &has_alpha);

  gimp_rgba_get_pixel (color, format, start_col);
200

201
  if (has_alpha)
202 203 204
    {
      if (select_transparent)
        {
205
          /*  don't select transparency if "color" isn't fully transparent
206
           */
207
          if (start_col[n_components - 1] > 0.0)
208 209 210 211 212 213 214 215
            select_transparent = FALSE;
        }
    }
  else
    {
      select_transparent = FALSE;
    }

216 217
  mask_buffer = gegl_buffer_new (gegl_buffer_get_extent (src_buffer),
                                 babl_format ("Y float"));
218

219 220
  iter = gegl_buffer_iterator_new (src_buffer,
                                   NULL, 0, format,
221
                                   GEGL_ACCESS_READ, GEGL_ABYSS_NONE);
222

223
  gegl_buffer_iterator_add (iter, mask_buffer,
224
                            NULL, 0, babl_format ("Y float"),
225
                            GEGL_ACCESS_WRITE, GEGL_ABYSS_NONE);
Sven Neumann's avatar
Sven Neumann committed
226

227
  while (gegl_buffer_iterator_next (iter))
Sven Neumann's avatar
Sven Neumann committed
228
    {
229 230 231
      const gfloat *src   = iter->data[0];
      gfloat       *dest  = iter->data[1];
      gint          count = iter->length;
Sven Neumann's avatar
Sven Neumann committed
232

233
      while (count--)
Sven Neumann's avatar
Sven Neumann committed
234 235
        {
          /*  Find how closely the colors match  */
236
          *dest = pixel_difference (start_col, src,
237 238
                                    antialias,
                                    threshold,
239
                                    n_components,
240 241 242 243
                                    has_alpha,
                                    select_transparent,
                                    select_criterion);

244
          src  += n_components;
245
          dest += 1;
Sven Neumann's avatar
Sven Neumann committed
246 247
        }
    }
248

249
  return mask_buffer;
Sven Neumann's avatar
Sven Neumann committed
250 251
}

252 253 254

/*  private functions  */

255 256 257 258 259 260 261 262 263 264 265 266 267 268
static const Babl *
choose_format (GeglBuffer          *buffer,
               GimpSelectCriterion  select_criterion,
               gint                *n_components,
               gboolean            *has_alpha)
{
  const Babl *format = gegl_buffer_get_format (buffer);

  *has_alpha = babl_format_has_alpha (format);

  switch (select_criterion)
    {
    case GIMP_SELECT_CRITERION_COMPOSITE:
      if (babl_format_is_palette (format))
269
        format = babl_format ("R'G'B'A float");
270 271
      else
        format = gimp_babl_format (gimp_babl_format_get_base_type (format),
272
                                   GIMP_PRECISION_FLOAT_GAMMA,
273 274 275 276 277 278
                                   *has_alpha);
      break;

    case GIMP_SELECT_CRITERION_R:
    case GIMP_SELECT_CRITERION_G:
    case GIMP_SELECT_CRITERION_B:
279
    case GIMP_SELECT_CRITERION_A:
280
      format = babl_format ("R'G'B'A float");
281 282 283 284 285 286 287 288
      break;

    case GIMP_SELECT_CRITERION_H:
    case GIMP_SELECT_CRITERION_S:
    case GIMP_SELECT_CRITERION_V:
      format = babl_format ("HSVA float");
      break;

289
    case GIMP_SELECT_CRITERION_LCH_L:
290 291 292
      format = babl_format ("CIE L alpha float");
      break;

293 294 295 296 297
    case GIMP_SELECT_CRITERION_LCH_C:
    case GIMP_SELECT_CRITERION_LCH_H:
      format = babl_format ("CIE LCH(ab) alpha float");
      break;

298 299 300 301 302 303 304 305 306 307
    default:
      g_return_val_if_reached (NULL);
      break;
    }

  *n_components = babl_format_get_n_components (format);

  return format;
}

308 309 310
static gfloat
pixel_difference (const gfloat        *col1,
                  const gfloat        *col2,
311
                  gboolean             antialias,
312 313
                  gfloat               threshold,
                  gint                 n_components,
314 315 316
                  gboolean             has_alpha,
                  gboolean             select_transparent,
                  GimpSelectCriterion  select_criterion)
317
{
318
  gfloat max = 0.0;
319 320

  /*  if there is an alpha channel, never select transparent regions  */
321 322
  if (! select_transparent && has_alpha && col2[n_components - 1] == 0.0)
    return 0.0;
323

324
  if (select_transparent && has_alpha)
325
    {
326
      max = fabs (col1[n_components - 1] - col2[n_components - 1]);
327 328 329
    }
  else
    {
330 331
      gfloat diff;
      gint   b;
332 333

      if (has_alpha)
334
        n_components--;
335

336
      switch (select_criterion)
337
        {
338
        case GIMP_SELECT_CRITERION_COMPOSITE:
339
          for (b = 0; b < n_components; b++)
340
            {
341
              diff = fabs (col1[b] - col2[b]);
342 343 344 345 346 347
              if (diff > max)
                max = diff;
            }
          break;

        case GIMP_SELECT_CRITERION_R:
348
          max = fabs (col1[0] - col2[0]);
349 350 351
          break;

        case GIMP_SELECT_CRITERION_G:
352
          max = fabs (col1[1] - col2[1]);
353 354 355
          break;

        case GIMP_SELECT_CRITERION_B:
356
          max = fabs (col1[2] - col2[2]);
357 358
          break;

359 360 361 362
        case GIMP_SELECT_CRITERION_A:
          max = fabs (col1[3] - col2[3]);
          break;

363
        case GIMP_SELECT_CRITERION_H:
364 365
          max = fabs (col1[0] - col2[0]);
          max = MIN (max, 1.0 - max);
366 367 368
          break;

        case GIMP_SELECT_CRITERION_S:
369
          max = fabs (col1[1] - col2[1]);
370 371 372
          break;

        case GIMP_SELECT_CRITERION_V:
373
          max = fabs (col1[2] - col2[2]);
374
          break;
375 376 377 378 379 380 381 382 383 384 385 386 387

        case GIMP_SELECT_CRITERION_LCH_L:
          max = fabs (col1[0] - col2[0]) / 100.0;
          break;

        case GIMP_SELECT_CRITERION_LCH_C:
          max = fabs (col1[1] - col2[1]) / 100.0;
          break;

        case GIMP_SELECT_CRITERION_LCH_H:
          max = fabs (col1[2] - col2[2]) / 360.0;
          max = MIN (max, 1.0 - max);
          break;
388
        }
389 390
    }

391
  if (antialias && threshold > 0.0)
392
    {
393
      gfloat aa = 1.5 - (max / threshold);
394

395
      if (aa <= 0.0)
396
        return 0.0;
397
      else if (aa < 0.5)
398
        return aa * 2.0;
399
      else
400
        return 1.0;
401 402 403 404
    }
  else
    {
      if (max > threshold)
405
        return 0.0;
406
      else
407
        return 1.0;
408 409 410
    }
}

411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
static void
push_segment (GQueue *segment_queue,
              gint    y,
              gint    old_y,
              gint    start,
              gint    end,
              gint    new_y,
              gint    new_start,
              gint    new_end)
{
  /* To avoid excessive memory allocation (y, old_y, start, end) tuples are
   * stored in interleaved format:
   *
   * [y1] [old_y1] [start1] [end1] [y2] [old_y2] [start2] [end2]
   */

  if (new_y != old_y)
    {
      /* If the new segment's y-coordinate is different than the old (source)
       * segment's y-coordinate, push the entire segment.
       */
      g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_y));
      g_queue_push_tail (segment_queue, GINT_TO_POINTER (y));
      g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_start));
      g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_end));
    }
  else
    {
      /* Otherwise, only push the set-difference between the new segment and
       * the source segment (since we've already scanned the source segment.)
       * Note that the `+ 1` and `- 1` terms of the end/start coordinates below
       * are only necessary when `diagonal_neighbors` is on (and otherwise make
       * the segments slightly larger than necessary), but, meh...
       */
      if (new_start < start)
        {
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_y));
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (y));
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_start));
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (start + 1));
        }

      if (new_end > end)
        {
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_y));
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (y));
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (end - 1));
          g_queue_push_tail (segment_queue, GINT_TO_POINTER (new_end));
        }
    }
}

static void
pop_segment (GQueue *segment_queue,
             gint   *y,
             gint   *old_y,
             gint   *start,
             gint   *end)
{
  *y     = GPOINTER_TO_INT (g_queue_pop_head (segment_queue));
  *old_y = GPOINTER_TO_INT (g_queue_pop_head (segment_queue));
  *start = GPOINTER_TO_INT (g_queue_pop_head (segment_queue));
  *end   = GPOINTER_TO_INT (g_queue_pop_head (segment_queue));
}

476
/* #define FETCH_ROW 1 */
477

478
static gboolean
479
find_contiguous_segment (const gfloat        *col,
480
                         GeglBuffer          *src_buffer,
481
                         GeglSampler         *src_sampler,
482
                         GeglBuffer          *mask_buffer,
483 484
                         const Babl          *src_format,
                         const Babl          *mask_format,
485
                         gint                 n_components,
486
                         gboolean             has_alpha,
487
                         gint                 width,
488 489 490
                         gboolean             select_transparent,
                         GimpSelectCriterion  select_criterion,
                         gboolean             antialias,
491
                         gfloat               threshold,
492 493
                         gint                 initial_x,
                         gint                 initial_y,
494
                         gint                *start,
495 496
                         gint                *end,
                         gfloat              *row)
497
{
498 499 500 501 502 503
  gfloat *s;
  gfloat  mask_row[width];
  gfloat  diff;

#ifdef FETCH_ROW
  gegl_buffer_get (src_buffer, GEGL_RECTANGLE (0, initial_y, width, 1), 1.0,
504
                   src_format,
505 506 507 508
                   row, GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);
  s = row + initial_x * n_components;
#else
  s = g_alloca (n_components * sizeof (gfloat));
509

510 511
  gegl_sampler_get (src_sampler,
                    initial_x, initial_y, NULL, s, GEGL_ABYSS_NONE);
512
#endif
513

514
  diff = pixel_difference (col, s, antialias, threshold,
515
                           n_components, has_alpha, select_transparent,
516
                           select_criterion);
517

518
  /* check the starting pixel */
519
  if (! diff)
520 521 522
    return FALSE;

  mask_row[initial_x] = diff;
523

524
  *start = initial_x - 1;
525 526 527
#ifdef FETCH_ROW
  s = row + *start * n_components;
#endif
528

529
  while (*start >= 0)
530
    {
531
#ifndef FETCH_ROW
532 533
      gegl_sampler_get (src_sampler,
                        *start, initial_y, NULL, s, GEGL_ABYSS_NONE);
534
#endif
535

536
      diff = pixel_difference (col, s, antialias, threshold,
537
                               n_components, has_alpha, select_transparent,
538
                               select_criterion);
539 540
      if (diff == 0.0)
        break;
541

542
      mask_row[*start] = diff;
543

544
      (*start)--;
545
#ifdef FETCH_ROW
546
      s -= n_components;
547
#endif
548 549
    }

550
  *end = initial_x + 1;
551 552 553
#ifdef FETCH_ROW
  s = row + *end * n_components;
#endif
554

555
  while (*end < width)
556
    {
557
#ifndef FETCH_ROW
558 559
      gegl_sampler_get (src_sampler,
                        *end, initial_y, NULL, s, GEGL_ABYSS_NONE);
560
#endif
561

562
      diff = pixel_difference (col, s, antialias, threshold,
563
                               n_components, has_alpha, select_transparent,
564
                               select_criterion);
565 566
      if (diff == 0.0)
        break;
567

568
      mask_row[*end] = diff;
569

570
      (*end)++;
571
#ifdef FETCH_ROW
572
      s += n_components;
573
#endif
574 575
    }

576 577 578
  gegl_buffer_set (mask_buffer, GEGL_RECTANGLE (*start + 1, initial_y,
                                                *end - *start - 1, 1),
                   0, mask_format, &mask_row[*start + 1],
579 580
                   GEGL_AUTO_ROWSTRIDE);

581 582 583 584
  return TRUE;
}

static void
585 586 587 588 589 590 591 592 593
find_contiguous_region (GeglBuffer          *src_buffer,
                        GeglBuffer          *mask_buffer,
                        const Babl          *format,
                        gint                 n_components,
                        gboolean             has_alpha,
                        gboolean             select_transparent,
                        GimpSelectCriterion  select_criterion,
                        gboolean             antialias,
                        gfloat               threshold,
594
                        gboolean             diagonal_neighbors,
595 596 597
                        gint                 x,
                        gint                 y,
                        const gfloat        *col)
598
{
599 600 601 602 603 604 605
  const Babl  *mask_format = babl_format ("Y float");
  GeglSampler *src_sampler;
  gint         old_y;
  gint         start, end;
  gint         new_start, new_end;
  GQueue      *segment_queue;
  gfloat      *row = NULL;
606 607 608 609

#ifdef FETCH_ROW
  row = g_new (gfloat, gegl_buffer_get_width (src_buffer) * n_components);
#endif
610

611 612 613
  src_sampler  = gegl_buffer_sampler_new (src_buffer,
                                          format, GEGL_SAMPLER_NEAREST);

614
  segment_queue = g_queue_new ();
615

616 617 618
  push_segment (segment_queue,
                y, /* dummy values: */ -1, 0, 0,
                y, x - 1, x + 1);
619

620 621
  do
    {
622 623
      pop_segment (segment_queue,
                   &y, &old_y, &start, &end);
624

625 626
      for (x = start + 1; x < end; x++)
        {
627 628
          gfloat val;

629 630 631
          gegl_buffer_get (mask_buffer, GEGL_RECTANGLE (x, y, 1, 1), 1.0,
                           mask_format, &val, GEGL_AUTO_ROWSTRIDE,
                           GEGL_ABYSS_NONE);
632

633
          if (val != 0.0)
634 635 636 637 638 639 640 641
            {
              /* If the current pixel is selected, then we've already visited
               * the next pixel.  (Note that we assume that the maximal image
               * width is sufficiently low that `x` won't overflow.)
               */
              x++;
              continue;
            }
642

643 644
          if (! find_contiguous_segment (col,
                                         src_buffer, src_sampler, mask_buffer,
645
                                         format, mask_format,
646 647
                                         n_components,
                                         has_alpha,
648
                                         gegl_buffer_get_width (src_buffer),
649
                                         select_transparent, select_criterion,
650
                                         antialias, threshold, x, y,
651 652
                                         &new_start, &new_end,
                                         row))
653
            continue;
654

655 656 657 658 659 660 661 662
          /* We can skip directly to `new_end + 1` on the next iteration, since
           * we've just selected all pixels in the range `[x, new_end)`, and
           * the pixel at `new_end` is above threshold.  (Note that we assume
           * that the maximal image width is sufficiently low that `x` won't
           * overflow.)
           */
          x = new_end;

663 664 665 666 667 668 669 670 671
          if (diagonal_neighbors)
            {
              if (new_start >= 0)
                new_start--;

              if (new_end < gegl_buffer_get_width (src_buffer))
                new_end++;
            }

672
          if (y + 1 < gegl_buffer_get_height (src_buffer))
673
            {
674 675 676
              push_segment (segment_queue,
                            y, old_y, start, end,
                            y + 1, new_start, new_end);
677
            }
678

679
          if (y - 1 >= 0)
680
            {
681 682 683
              push_segment (segment_queue,
                            y, old_y, start, end,
                            y - 1, new_start, new_end);
684
            }
685

686
        }
687
    }
688
  while (! g_queue_is_empty (segment_queue));
689

690
  g_queue_free (segment_queue);
691

692 693
  g_object_unref (src_sampler);

694 695 696
#ifdef FETCH_ROW
  g_free (row);
#endif
697
}