gimppickable-contiguous-region.c 41.5 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 <https://www.gnu.org/licenses/>.
16 17 18 19
 */

#include "config.h"

20 21
#include <stdlib.h>

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

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

#include "core-types.h"

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

34
#include "gimp-parallel.h"
35
#include "gimp-utils.h" /* GIMP_TIMER */
36
#include "gimpasync.h"
37
#include "gimplineart.h"
38
#include "gimppickable.h"
39
#include "gimppickable-contiguous-region.h"
40 41


42 43 44 45 46
typedef struct
{
  GeglBuffer *buffer;
  gboolean    select_transparent;
  gfloat      stroke_threshold;
47 48
  gint        segment_max_length;
  gint        spline_max_length;
49 50
} LineArtData;

51 52 53 54
typedef struct
{
  gint   x;
  gint   y;
55
  gint   level;
56 57
} BorderPixel;

58

59 60
/*  local function prototypes  */

61 62 63 64
static const Babl * choose_format         (GeglBuffer          *buffer,
                                           GimpSelectCriterion  select_criterion,
                                           gint                *n_components,
                                           gboolean            *has_alpha);
65 66
static gfloat   pixel_difference          (const gfloat        *col1,
                                           const gfloat        *col2,
67
                                           gboolean             antialias,
68 69
                                           gfloat               threshold,
                                           gint                 n_components,
70 71 72
                                           gboolean             has_alpha,
                                           gboolean             select_transparent,
                                           GimpSelectCriterion  select_criterion);
73 74 75 76 77 78 79 80 81 82 83 84 85
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);
86
static gboolean find_contiguous_segment   (const gfloat        *col,
87
                                           GeglBuffer          *src_buffer,
88
                                           GeglSampler         *src_sampler,
89 90
                                           GeglBuffer          *mask_buffer,
                                           const Babl          *src_format,
91
                                           const Babl          *mask_format,
92
                                           gint                 n_components,
93
                                           gboolean             has_alpha,
94
                                           gint                 width,
95 96 97
                                           gboolean             select_transparent,
                                           GimpSelectCriterion  select_criterion,
                                           gboolean             antialias,
98
                                           gfloat               threshold,
99 100
                                           gint                 initial_x,
                                           gint                 initial_y,
101
                                           gint                *start,
102 103 104
                                           gint                *end,
                                           gfloat              *row);
static void     find_contiguous_region    (GeglBuffer          *src_buffer,
105 106
                                           GeglBuffer          *mask_buffer,
                                           const Babl          *format,
107 108
                                           gint                 n_components,
                                           gboolean             has_alpha,
109 110 111
                                           gboolean             select_transparent,
                                           GimpSelectCriterion  select_criterion,
                                           gboolean             antialias,
112
                                           gfloat               threshold,
113
                                           gboolean             diagonal_neighbors,
114 115
                                           gint                 x,
                                           gint                 y,
116
                                           const gfloat        *col);
117

118 119
static LineArtData   * line_art_data_new    (GeglBuffer          *buffer,
                                             gboolean             select_transparent,
120 121 122
                                             gfloat               stroke_threshold,
                                             gint                 segment_max_length,
                                             gint                 spline_max_length);
123 124 125
static void            line_art_data_free   (LineArtData         *data);
static GimpPickableLineArtAsyncResult *
                       line_art_result_new  (GeglBuffer          *line_art,
126
                                             gfloat              *distmap);
127 128 129 130 131
static void            line_art_result_free (GimpPickableLineArtAsyncResult
                                                                 *data);
static void            line_art_queue_pixel (GQueue              *queue,
                                             gint                 x,
                                             gint                 y,
132
                                             gint                 level);
133

134 135 136

/*  public functions  */

137 138 139
static void
gimp_pickable_contiguous_region_prepare_line_art_async_func (GimpAsync   *async,
                                                             LineArtData *data)
140 141
{
  GeglBuffer *lineart;
142
  gfloat     *distmap;
143
  gboolean    has_alpha;
144
  gboolean    select_transparent = FALSE;
145

146
  has_alpha = babl_format_has_alpha (gegl_buffer_get_format (data->buffer));
147

148
  if (has_alpha)
149
    {
150
      if (data->select_transparent)
151 152 153 154 155 156
        {
          /*  don't select transparent regions if there are no fully
           *  transparent pixels.
           */
          GeglBufferIterator *gi;

157 158
          gi = gegl_buffer_iterator_new (data->buffer, NULL, 0,
                                         babl_format ("A u8"),
159 160 161 162 163 164
                                         GEGL_ACCESS_READ, GEGL_ABYSS_NONE, 3);
          while (gegl_buffer_iterator_next (gi))
            {
              guint8 *p = (guint8*) gi->items[0].data;
              gint    k;

165 166 167 168 169 170 171 172 173 174 175
              if (gimp_async_is_canceled (async))
                {
                  gegl_buffer_iterator_stop (gi);

                  gimp_async_abort (async);

                  line_art_data_free (data);

                  return;
                }

176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198
              for (k = 0; k < gi->length; k++)
                {
                  if (! *p)
                    {
                      select_transparent = TRUE;
                      break;
                    }
                  p++;
                }
              if (select_transparent)
                break;
            }
          if (select_transparent)
            gegl_buffer_iterator_stop (gi);
        }
    }

  /* For smart selection, we generate a binarized image with close
   * regions, then run a composite selection with no threshold on
   * this intermediate buffer.
   */
  GIMP_TIMER_START();

199
  lineart = gimp_lineart_close (data->buffer,
200
                                select_transparent,
201
                                data->stroke_threshold,
202 203 204 205 206 207
                                /*minimal_lineart_area,*/
                                5,
                                /*normal_estimate_mask_size,*/
                                5,
                                /*end_point_rate,*/
                                0.85,
208
                                data->spline_max_length,
209 210 211 212 213 214 215 216 217 218 219 220 221 222
                                /*spline_max_angle,*/
                                90.0,
                                /*end_point_connectivity,*/
                                2,
                                /*spline_roundness,*/
                                1.0,
                                /*allow_self_intersections,*/
                                TRUE,
                                /*created_regions_significant_area,*/
                                4,
                                /*created_regions_minimum_area,*/
                                100,
                                /*small_segments_from_spline_sources,*/
                                TRUE,
223
                                data->segment_max_length,
224
                                &distmap);
225 226 227

  GIMP_TIMER_END("close line-art");

228
  gimp_async_finish_full (async,
229
                          line_art_result_new (lineart, distmap),
230
                          (GDestroyNotify) line_art_result_free);
231 232 233 234 235

  line_art_data_free (data);
}

GeglBuffer *
236 237 238
gimp_pickable_contiguous_region_prepare_line_art (GimpPickable  *pickable,
                                                  gboolean       select_transparent,
                                                  gfloat         stroke_threshold,
239 240
                                                  gint           segment_max_length,
                                                  gint           spline_max_length,
241
                                                  gfloat       **distmap)
242
{
243 244 245 246
  GimpAsync                      *async;
  LineArtData                    *data;
  GimpPickableLineArtAsyncResult *result;
  GeglBuffer                     *lineart;
247 248 249 250 251 252 253

  g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);

  gimp_pickable_flush (pickable);

  async = gimp_async_new ();
  data  = line_art_data_new (gimp_pickable_get_buffer (pickable),
254 255
                             select_transparent, stroke_threshold,
                             segment_max_length, spline_max_length);
256 257 258

  gimp_pickable_contiguous_region_prepare_line_art_async_func (async, data);

259 260 261 262 263
  result = gimp_async_get_result (async);

  lineart   = g_object_ref (result->line_art);
  *distmap  = result->distmap;
  result->distmap  = NULL;
264 265 266

  g_object_unref (async);

267 268 269
  return lineart;
}

270 271 272 273
GimpAsync *
gimp_pickable_contiguous_region_prepare_line_art_async (GimpPickable *pickable,
                                                        gboolean      select_transparent,
                                                        gfloat        stroke_threshold,
274 275
                                                        gint          segment_max_length,
                                                        gint          spline_max_length,
276 277 278 279 280 281 282 283 284 285 286 287
                                                        gint          priority)
{
  GeglBuffer  *buffer;
  GimpAsync   *async;
  LineArtData *data;

  g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);

  gimp_pickable_flush (pickable);

  buffer = gegl_buffer_dup (gimp_pickable_get_buffer (pickable));

288 289
  data  = line_art_data_new (buffer, select_transparent, stroke_threshold,
                             segment_max_length, spline_max_length);
290 291 292 293 294 295 296 297 298 299 300 301 302

  g_object_unref (buffer);

  async = gimp_parallel_run_async_full (
    priority,
    (GimpParallelRunAsyncFunc)
      gimp_pickable_contiguous_region_prepare_line_art_async_func,
    data,
    (GDestroyNotify) line_art_data_free);

  return async;
}

303
GeglBuffer *
304
gimp_pickable_contiguous_region_by_seed (GimpPickable        *pickable,
305
                                         GeglBuffer          *line_art,
306
                                         gfloat              *distmap,
307 308 309 310
                                         gboolean             antialias,
                                         gfloat               threshold,
                                         gboolean             select_transparent,
                                         GimpSelectCriterion  select_criterion,
311
                                         gboolean             diagonal_neighbors,
312
                                         gfloat               stroke_threshold,
313
                                         gint                 flooding_max,
314 315
                                         gint                 segment_max_length,
                                         gint                 spline_max_length,
316 317
                                         gint                 x,
                                         gint                 y)
318
{
319 320 321 322 323 324 325
  GeglBuffer    *src_buffer;
  GeglBuffer    *mask_buffer;
  const Babl    *format;
  GeglRectangle  extent;
  gint           n_components;
  gboolean       has_alpha;
  gfloat         start_col[MAX_CHANNELS];
326
  gboolean       smart_line_art = FALSE;
327
  gboolean       free_line_art  = FALSE;
328 329

  g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);
330

331
  if (select_criterion == GIMP_SELECT_CRITERION_LINE_ART)
332
    {
333 334
      g_return_val_if_fail ((line_art && distmap) ||
                            (! line_art && ! distmap),
335
                            NULL);
336
      if (line_art == NULL)
337
        {
338 339 340
          /* It is much better experience to pre-compute the line art,
           * but it may not be always possible (for instance when
           * selecting/filling through a PDB call).
341
           */
342
          line_art      = gimp_pickable_contiguous_region_prepare_line_art (pickable, select_transparent,
343
                                                                            stroke_threshold,
344 345
                                                                            segment_max_length,
                                                                            spline_max_length,
346
                                                                            &distmap);
347
          free_line_art = TRUE;
348
        }
349

350 351
      src_buffer = line_art;

352
      smart_line_art     = TRUE;
353 354 355 356 357
      antialias          = FALSE;
      threshold          = 0.0;
      select_transparent = FALSE;
      select_criterion   = GIMP_SELECT_CRITERION_COMPOSITE;
      diagonal_neighbors = FALSE;
358 359 360 361 362

      format = choose_format (src_buffer, select_criterion,
                              &n_components, &has_alpha);
      gegl_buffer_sample (src_buffer, x, y, NULL, start_col, format,
                          GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);
363 364 365 366 367
    }
  else
    {
      gimp_pickable_flush (pickable);
      src_buffer = gimp_pickable_get_buffer (pickable);
368

369 370 371 372 373
      format = choose_format (src_buffer, select_criterion,
                              &n_components, &has_alpha);
      gegl_buffer_sample (src_buffer, x, y, NULL, start_col, format,
                          GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);

374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
      if (has_alpha)
        {
          if (select_transparent)
            {
              /*  don't select transparent regions if the start pixel isn't
               *  fully transparent
               */
              if (start_col[n_components - 1] > 0)
                select_transparent = FALSE;
            }
        }
      else
        {
          select_transparent = FALSE;
        }
389 390
    }

391
  extent = *gegl_buffer_get_extent (src_buffer);
392

393
  mask_buffer = gegl_buffer_new (&extent, babl_format ("Y float"));
394

395 396 397 398 399 400 401 402 403 404 405 406
  if (smart_line_art && start_col[0])
    {
      /* As a special exception, if you fill over a line art pixel, only
       * fill the pixel and exit
       */
      start_col[0] = 1.0;
      gegl_buffer_set (mask_buffer, GEGL_RECTANGLE (x, y, 1, 1),
                       0, babl_format ("Y float"), start_col,
                       GEGL_AUTO_ROWSTRIDE);
      smart_line_art = FALSE;
    }
  else if (x >= extent.x && x < (extent.x + extent.width) &&
407 408 409 410 411 412 413
      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,
414
                              antialias, threshold, diagonal_neighbors,
415
                              x, y, start_col);
416

417 418
      GIMP_TIMER_END("foo");
    }
419 420 421 422 423 424

  if (smart_line_art)
    {
      /* The last step of the line art algorithm is to make sure that
       * selections does not leave "holes" between its borders and the
       * line arts, while not stepping over as well.
425 426 427
       * I used to run the "gegl:watershed-transform" operation to flood
       * the stroke pixels, but for such simple need, this simple code
       * is so much faster while producing better results.
428
       */
429 430 431 432 433
      gfloat *mask;
      GQueue *queue  = g_queue_new ();
      gint    width  = gegl_buffer_get_width (line_art);
      gint    height = gegl_buffer_get_height (line_art);
      gint    nx, ny;
434 435 436

      GIMP_TIMER_START();

437 438 439 440 441 442 443
      mask = g_new (gfloat, width * height);
      gegl_buffer_get (mask_buffer, NULL, 1.0, NULL,
                       mask, GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);

      for (y = 0; y < height; y++)
        for (x = 0; x < width; x++)
          {
444
            if (distmap[x + y * width] == 1.0)
445 446 447 448 449 450 451 452 453
              {
                if (x > 0)
                  {
                    nx = x - 1;
                    if (y > 0)
                      {
                        ny = y - 1;
                        if (mask[nx + ny * width] != 0.0)
                          {
454
                            line_art_queue_pixel (queue, x, y, 1);
455 456 457 458 459 460
                            continue;
                          }
                      }
                    ny = y;
                    if (mask[nx + ny * width] != 0.0)
                      {
461
                        line_art_queue_pixel (queue, x, y, 1);
462 463 464 465 466 467 468
                        continue;
                      }
                    if (y < height - 1)
                      {
                        ny = y + 1;
                        if (mask[nx + ny * width] != 0.0)
                          {
469
                            line_art_queue_pixel (queue, x, y, 1);
470 471 472 473 474 475 476 477 478 479 480 481
                            continue;
                          }
                      }
                  }
                if (x < width - 1)
                  {
                    nx = x + 1;
                    if (y > 0)
                      {
                        ny = y - 1;
                        if (mask[nx + ny * width] != 0.0)
                          {
482
                            line_art_queue_pixel (queue, x, y, 1);
483 484 485 486 487 488
                            continue;
                          }
                      }
                    ny = y;
                    if (mask[nx + ny * width] != 0.0)
                      {
489
                        line_art_queue_pixel (queue, x, y, 1);
490 491 492 493 494 495 496
                        continue;
                      }
                    if (y < height - 1)
                      {
                        ny = y + 1;
                        if (mask[nx + ny * width] != 0.0)
                          {
497
                            line_art_queue_pixel (queue, x, y, 1);
498 499 500 501 502 503 504 505 506 507
                            continue;
                          }
                      }
                  }
                nx = x;
                if (y > 0)
                  {
                    ny = y - 1;
                    if (mask[nx + ny * width] != 0.0)
                      {
508
                        line_art_queue_pixel (queue, x, y, 1);
509 510 511 512 513 514 515 516
                        continue;
                      }
                  }
                if (y < height - 1)
                  {
                    ny = y + 1;
                    if (mask[nx + ny * width] != 0.0)
                      {
517
                        line_art_queue_pixel (queue, x, y, 1);
518 519 520 521 522 523 524
                        continue;
                      }
                  }
              }
          }

      while (! g_queue_is_empty (queue))
525
        {
526
          BorderPixel *c = g_queue_pop_head (queue);
527

528
          if (mask[c->x + c->y * width] != 1.0)
529
            {
530
              mask[c->x + c->y * width] = 1.0;
531 532 533
              if (c->level >= flooding_max)
                /* Do not overflood under line arts. */
                continue;
534 535 536 537 538 539 540
              if (c->x > 0)
                {
                  nx = c->x - 1;
                  if (c->y > 0)
                    {
                      ny = c->y - 1;
                      if (mask[nx + ny * width] == 0.0 &&
541 542
                          distmap[nx + ny * width] > distmap[c->x + c->y * width])
                        line_art_queue_pixel (queue, nx, ny, c->level + 1);
543 544 545
                    }
                  ny = c->y;
                  if (mask[nx + ny * width] == 0.0 &&
546 547
                      distmap[nx + ny * width] > distmap[c->x + c->y * width])
                    line_art_queue_pixel (queue, nx, ny, c->level + 1);
548 549 550 551
                  if (c->y < height - 1)
                    {
                      ny = c->y - 1;
                      if (mask[nx + ny * width] == 0.0 &&
552 553
                          distmap[nx + ny * width] > distmap[c->x + c->y * width])
                        line_art_queue_pixel (queue, nx, ny, c->level + 1);
554 555 556 557 558 559 560 561 562
                    }
                }
              if (c->x < width - 1)
                {
                  nx = c->x + 1;
                  if (c->y > 0)
                    {
                      ny = c->y - 1;
                      if (mask[nx + ny * width] == 0.0 &&
563 564
                          distmap[nx + ny * width] > distmap[c->x + c->y * width])
                        line_art_queue_pixel (queue, nx, ny, c->level + 1);
565 566 567
                    }
                  ny = c->y;
                  if (mask[nx + ny * width] == 0.0 &&
568 569
                      distmap[nx + ny * width] > distmap[c->x + c->y * width])
                    line_art_queue_pixel (queue, nx, ny, c->level + 1);
570 571 572 573
                  if (c->y < height - 1)
                    {
                      ny = c->y - 1;
                      if (mask[nx + ny * width] == 0.0 &&
574 575
                          distmap[nx + ny * width] > distmap[c->x + c->y * width])
                        line_art_queue_pixel (queue, nx, ny, c->level + 1);
576 577 578 579 580 581 582
                    }
                }
              nx = c->x;
              if (c->y > 0)
                {
                  ny = c->y - 1;
                  if (mask[nx + ny * width] == 0.0 &&
583 584
                      distmap[nx + ny * width] > distmap[c->x + c->y * width])
                    line_art_queue_pixel (queue, nx, ny, c->level + 1);
585 586 587 588 589
                }
              if (c->y < height - 1)
                {
                  ny = c->y + 1;
                  if (mask[nx + ny * width] == 0.0 &&
590 591
                      distmap[nx + ny * width] > distmap[c->x + c->y * width])
                    line_art_queue_pixel (queue, nx, ny, c->level + 1);
592
                }
593
            }
594
          g_free (c);
595
        }
596 597 598 599
      g_queue_free (queue);
      gegl_buffer_set (mask_buffer, gegl_buffer_get_extent (mask_buffer),
                       0, NULL, mask, GEGL_AUTO_ROWSTRIDE);
      g_free (mask);
600 601

      GIMP_TIMER_END("watershed line art");
602 603 604 605 606 607

      if (free_line_art)
        {
          g_object_unref (src_buffer);
          g_free (distmap);
        }
608
    }
609

610
  return mask_buffer;
611 612
}

613
GeglBuffer *
614 615 616 617 618 619
gimp_pickable_contiguous_region_by_color (GimpPickable        *pickable,
                                          gboolean             antialias,
                                          gfloat               threshold,
                                          gboolean             select_transparent,
                                          GimpSelectCriterion  select_criterion,
                                          const GimpRGB       *color)
620
{
621
  /*  Scan over the pickable's active layer, finding pixels within the
Sven Neumann's avatar
Sven Neumann committed
622 623
   *  specified threshold from the given R, G, & B values.  If
   *  antialiasing is on, use the same antialiasing scheme as in
624
   *  fuzzy_select.  Modify the pickable's mask to reflect the
Sven Neumann's avatar
Sven Neumann committed
625
   *  additional selection
626
   */
627 628 629
  GeglBufferIterator *iter;
  GeglBuffer         *src_buffer;
  GeglBuffer         *mask_buffer;
630 631
  const Babl         *format;
  gint                n_components;
632
  gboolean            has_alpha;
633
  gfloat              start_col[MAX_CHANNELS];
634

635
  g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);
636 637
  g_return_val_if_fail (color != NULL, NULL);

638 639
  gimp_pickable_flush (pickable);

640
  src_buffer = gimp_pickable_get_buffer (pickable);
641

642 643 644 645
  format = choose_format (src_buffer, select_criterion,
                          &n_components, &has_alpha);

  gimp_rgba_get_pixel (color, format, start_col);
646

647
  if (has_alpha)
648 649 650
    {
      if (select_transparent)
        {
651
          /*  don't select transparency if "color" isn't fully transparent
652
           */
653
          if (start_col[n_components - 1] > 0.0)
654 655 656 657 658 659 660 661
            select_transparent = FALSE;
        }
    }
  else
    {
      select_transparent = FALSE;
    }

662 663
  mask_buffer = gegl_buffer_new (gegl_buffer_get_extent (src_buffer),
                                 babl_format ("Y float"));
664

665 666
  iter = gegl_buffer_iterator_new (src_buffer,
                                   NULL, 0, format,
667
                                   GEGL_ACCESS_READ, GEGL_ABYSS_NONE, 2);
668

669
  gegl_buffer_iterator_add (iter, mask_buffer,
670
                            NULL, 0, babl_format ("Y float"),
671
                            GEGL_ACCESS_WRITE, GEGL_ABYSS_NONE);
Sven Neumann's avatar
Sven Neumann committed
672

673
  while (gegl_buffer_iterator_next (iter))
Sven Neumann's avatar
Sven Neumann committed
674
    {
675 676
      const gfloat *src   = iter->items[0].data;
      gfloat       *dest  = iter->items[1].data;
677
      gint          count = iter->length;
Sven Neumann's avatar
Sven Neumann committed
678

679
      while (count--)
Sven Neumann's avatar
Sven Neumann committed
680 681
        {
          /*  Find how closely the colors match  */
682
          *dest = pixel_difference (start_col, src,
683 684
                                    antialias,
                                    threshold,
685
                                    n_components,
686 687 688 689
                                    has_alpha,
                                    select_transparent,
                                    select_criterion);

690
          src  += n_components;
691
          dest += 1;
Sven Neumann's avatar
Sven Neumann committed
692 693
        }
    }
694

695
  return mask_buffer;
Sven Neumann's avatar
Sven Neumann committed
696 697
}

698 699 700

/*  private functions  */

701 702 703 704 705 706 707 708 709 710 711 712 713 714
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))
715
        format = babl_format ("R'G'B'A float");
716 717
      else
        format = gimp_babl_format (gimp_babl_format_get_base_type (format),
718 719 720
                                   GIMP_PRECISION_FLOAT_NON_LINEAR,
                                   *has_alpha,
                                   NULL);
721 722 723 724 725
      break;

    case GIMP_SELECT_CRITERION_R:
    case GIMP_SELECT_CRITERION_G:
    case GIMP_SELECT_CRITERION_B:
726
    case GIMP_SELECT_CRITERION_A:
727
      format = babl_format ("R'G'B'A float");
728 729 730 731 732 733 734 735
      break;

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

736
    case GIMP_SELECT_CRITERION_LCH_L:
737 738 739
      format = babl_format ("CIE L alpha float");
      break;

740 741 742 743 744
    case GIMP_SELECT_CRITERION_LCH_C:
    case GIMP_SELECT_CRITERION_LCH_H:
      format = babl_format ("CIE LCH(ab) alpha float");
      break;

745
    case GIMP_SELECT_CRITERION_LINE_ART:
746
      format = babl_format ("Y'A float");
747 748
      break;

749 750 751 752 753 754 755 756 757 758
    default:
      g_return_val_if_reached (NULL);
      break;
    }

  *n_components = babl_format_get_n_components (format);

  return format;
}

759 760 761
static gfloat
pixel_difference (const gfloat        *col1,
                  const gfloat        *col2,
762
                  gboolean             antialias,
763 764
                  gfloat               threshold,
                  gint                 n_components,
765 766 767
                  gboolean             has_alpha,
                  gboolean             select_transparent,
                  GimpSelectCriterion  select_criterion)
768
{
769
  gfloat max = 0.0;
770 771

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

775
  if (select_transparent && has_alpha)
776
    {
777
      max = fabs (col1[n_components - 1] - col2[n_components - 1]);
778 779 780
    }
  else
    {
781 782
      gfloat diff;
      gint   b;
783 784

      if (has_alpha)
785
        n_components--;
786

787
      switch (select_criterion)
788
        {
789
        case GIMP_SELECT_CRITERION_COMPOSITE:
790
          for (b = 0; b < n_components; b++)
791
            {
792
              diff = fabs (col1[b] - col2[b]);
793 794 795 796 797 798
              if (diff > max)
                max = diff;
            }
          break;

        case GIMP_SELECT_CRITERION_R:
799
          max = fabs (col1[0] - col2[0]);
800 801 802
          break;

        case GIMP_SELECT_CRITERION_G:
803
          max = fabs (col1[1] - col2[1]);
804 805 806
          break;

        case GIMP_SELECT_CRITERION_B:
807
          max = fabs (col1[2] - col2[2]);
808 809
          break;

810 811 812 813
        case GIMP_SELECT_CRITERION_A:
          max = fabs (col1[3] - col2[3]);
          break;

814
        case GIMP_SELECT_CRITERION_H:
815 816
          max = fabs (col1[0] - col2[0]);
          max = MIN (max, 1.0 - max);
817 818 819
          break;

        case GIMP_SELECT_CRITERION_S:
820
          max = fabs (col1[1] - col2[1]);
821 822 823
          break;

        case GIMP_SELECT_CRITERION_V:
824
          max = fabs (col1[2] - col2[2]);
825
          break;
826 827 828 829 830 831 832 833 834 835 836 837 838

        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;
839 840 841 842

        case GIMP_SELECT_CRITERION_LINE_ART:
          /* Smart selection is handled before. */
          g_return_val_if_reached (0.0);
843
        }
844 845
    }

846
  if (antialias && threshold > 0.0)
847
    {
848
      gfloat aa = 1.5 - (max / threshold);
849

850
      if (aa <= 0.0)
851
        return 0.0;
852
      else if (aa < 0.5)
853
        return aa * 2.0;
854
      else
855
        return 1.0;
856 857 858 859
    }
  else
    {
      if (max > threshold)
860
        return 0.0;
861
      else
862
        return 1.0;
863 864 865
    }
}

866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930
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));
}

931
/* #define FETCH_ROW 1 */
932

933
static gboolean
934
find_contiguous_segment (const gfloat        *col,
935
                         GeglBuffer          *src_buffer,
936
                         GeglSampler         *src_sampler,
937
                         GeglBuffer          *mask_buffer,
938 939
                         const Babl          *src_format,
                         const Babl          *mask_format,
940
                         gint                 n_components,
941
                         gboolean             has_alpha,
942
                         gint                 width,
943 944 945
                         gboolean             select_transparent,
                         GimpSelectCriterion  select_criterion,
                         gboolean             antialias,
946
                         gfloat               threshold,
947 948
                         gint                 initial_x,
                         gint                 initial_y,
949
                         gint                *start,
950 951
                         gint                *end,
                         gfloat              *row)
952
{
953 954 955 956 957 958
  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,
959
                   src_format,
960 961 962 963
                   row, GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);
  s = row + initial_x * n_components;
#else
  s = g_alloca (n_components * sizeof (gfloat));
964

965 966
  gegl_sampler_get (src_sampler,
                    initial_x, initial_y, NULL, s, GEGL_ABYSS_NONE);
967
#endif
968

969
  diff = pixel_difference (col, s, antialias, threshold,
970
                           n_components, has_alpha, select_transparent,
971
                           select_criterion);
972

973
  /* check the starting pixel */
974
  if (! diff)
975 976 977
    return FALSE;

  mask_row[initial_x] = diff;
978

979
  *start = initial_x - 1;
980 981 982
#ifdef FETCH_ROW
  s = row + *start * n_components;
#endif
983

984
  while (*start >= 0)
985
    {
986
#ifndef FETCH_ROW
987 988
      gegl_sampler_get (src_sampler,
                        *start, initial_y, NULL, s, GEGL_ABYSS_NONE);
989
#endif
990

991
      diff = pixel_difference (col, s, antialias, threshold,
992
                               n_components, has_alpha, select_transparent,
993
                               select_criterion);
994 995
      if (diff == 0.0)
        break;
996

997
      mask_row[*start] = diff;
998

999
      (*start)--;
1000
#ifdef FETCH_ROW
1001
      s -= n_components;
1002
#endif
1003 1004
    }

1005
  *end = initial_x + 1;
1006 1007 1008
#ifdef FETCH_ROW
  s = row + *end * n_components;
#endif
1009

1010
  while (*end < width)
1011
    {
1012
#ifndef FETCH_ROW
1013 1014
      gegl_sampler_get (src_sampler,
                        *end, initial_y, NULL, s, GEGL_ABYSS_NONE);
1015
#endif
1016

1017
      diff = pixel_difference (col, s, antialias, threshold,
1018
                               n_components, has_alpha, select_transparent,
1019
                               select_criterion);
1020 1021
      if (diff == 0.0)
        break;
1022

1023
      mask_row[*end] = diff;
1024

1025
      (*end)++;
1026
#ifdef FETCH_ROW
1027
      s += n_components;
1028
#endif
1029 1030
    }

1031 1032 1033
  gegl_buffer_set (mask_buffer, GEGL_RECTANGLE (*start + 1, initial_y,
                                                *end - *start - 1, 1),
                   0, mask_format, &mask_row[*start + 1],
1034 1035
                   GEGL_AUTO_ROWSTRIDE);

1036 1037 1038 1039
  return TRUE;
}

static void
1040 1041 1042 1043 1044 1045 1046 1047 1048
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,
1049
                        gboolean             diagonal_neighbors,
1050 1051 1052
                        gint                 x,
                        gint                 y,
                        const gfloat        *col)
1053
{
1054 1055 1056 1057 1058 1059 1060
  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;
1061 1062 1063 1064

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

1066
  src_sampler = gegl_buffer_sampler_new (src_buffer,
1067 1068
                                          format, GEGL_SAMPLER_NEAREST);

1069
  segment_queue = g_queue_new ();
1070

1071 1072 1073
  push_segment (segment_queue,
                y, /* dummy values: */ -1, 0, 0,
                y, x - 1, x + 1);
1074

1075 1076
  do
    {
1077 1078
      pop_segment (segment_queue,
                   &y, &old_y, &start, &end);
1079

1080 1081
      for (x = start + 1; x < end; x++)
        {
1082 1083
          gfloat val;

1084 1085 1086
          gegl_buffer_get (mask_buffer, GEGL_RECTANGLE (x, y, 1, 1), 1.0,
                           mask_format, &val, GEGL_AUTO_ROWSTRIDE,
                           GEGL_ABYSS_NONE);
1087

1088
          if (val != 0.0)
1089 1090 1091 1092 1093 1094 1095 1096
            {
              /* 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;
            }
1097

1098 1099
          if (! find_contiguous_segment (col,
                                         src_buffer, src_sampler, mask_buffer,
1100
                                         format, mask_format,
1101 1102
                                         n_components,
                                         has_alpha,
1103
                                         gegl_buffer_get_width (src_buffer),
1104
                                         select_transparent, select_criterion,
1105
                                         antialias, threshold, x, y,
1106 1107
                                         &new_start, &new_end,
                                         row))
1108
            continue;
1109

1110 1111 1112 1113 1114 1115 1116 1117
          /* 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;

1118 1119 1120 1121 1122 1123 1124 1125 1126
          if (diagonal_neighbors)
            {
              if (new_start >= 0)
                new_start--;

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

1127
          if (y + 1 < gegl_buffer_get_height (src_buffer))
1128
            {
1129 1130 1131
              push_segment (segment_queue,
                            y, old_y, start, end,
                            y + 1, new_start, new_end);
1132
            }
1133

1134
          if (y - 1 >= 0)
1135
            {
1136 1137 1138
              push_segment (segment_queue,
                            y, old_y, start, end,
                            y - 1, new_start, new_end);
1139
            }
1140

1141
        }
1142
    }
1143
  while (! g_queue_is_empty (segment_queue));
1144

1145
  g_queue_free (segment_queue);
1146

1147 1148
  g_object_unref (src_sampler);

1149 1150 1151
#ifdef FETCH_ROW
  g_free (row);
#endif
1152
}
1153 1154 1155 1156

static LineArtData *
line_art_data_new (GeglBuffer *buffer,
                   gboolean    select_transparent,
1157 1158 1159
                   gfloat      stroke_threshold,
                   gint        segment_max_length,
                   gint        spline_max_length)
1160 1161 1162 1163 1164 1165
{
  LineArtData *data = g_slice_new (LineArtData);

  data->buffer             = g_object_ref (buffer);
  data->select_transparent = select_transparent;
  data->stroke_threshold   = stroke_threshold;
1166 1167
  data->segment_max_length = segment_max_length;
  data->spline_max_length  = spline_max_length;
1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178

  return data;
}

static void
line_art_data_free (LineArtData *data)
{
  g_object_unref (data->buffer);

  g_slice_free (LineArtData, data);
}
1179 1180 1181

static GimpPickableLineArtAsyncResult *
line_art_result_new (GeglBuffer *line_art,
1182
                     gfloat     *distmap)
1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205
{
  GimpPickableLineArtAsyncResult *data;

  data = g_slice_new (GimpPickableLineArtAsyncResult);
  data->line_art = line_art;
  data->distmap  = distmap;

  return data;
}

static void
line_art_result_free (GimpPickableLineArtAsyncResult *data)
{
  g_object_unref (data->line_art);
  g_clear_pointer (&data->distmap, g_free);

  g_slice_free (GimpPickableLineArtAsyncResult, data);
}

static void
line_art_queue_pixel (GQueue *queue,
                      gint    x,
                      gint    y,
1206
                      gint    level)
1207 1208 1209
{
  BorderPixel *p = g_new (BorderPixel, 1);

1210 1211 1212
  p->x      = x;
  p->y      = y;
  p->level  = level;
1213 1214 1215

  g_queue_push_head (queue, p);
}