summaryrefslogtreecommitdiffstats
path: root/app/core/gimppickable-contiguous-region.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--app/core/gimppickable-contiguous-region.cc1123
1 files changed, 1123 insertions, 0 deletions
diff --git a/app/core/gimppickable-contiguous-region.cc b/app/core/gimppickable-contiguous-region.cc
new file mode 100644
index 0000000..ea30d0c
--- /dev/null
+++ b/app/core/gimppickable-contiguous-region.cc
@@ -0,0 +1,1123 @@
+/* GIMP - The GNU Image Manipulation Program
+ * Copyright (C) 1995 Spencer Kimball and Peter Mattis
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (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
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+
+#include <stdlib.h>
+
+#include <cairo.h>
+#include <gegl.h>
+#include <gdk-pixbuf/gdk-pixbuf.h>
+
+#include "libgimpcolor/gimpcolor.h"
+#include "libgimpmath/gimpmath.h"
+
+extern "C"
+{
+
+#include "core-types.h"
+
+#include "gegl/gimp-babl.h"
+
+#include "gimp-parallel.h"
+#include "gimp-utils.h" /* GIMP_TIMER */
+#include "gimpasync.h"
+#include "gimplineart.h"
+#include "gimppickable.h"
+#include "gimppickable-contiguous-region.h"
+
+
+#define EPSILON 1e-6
+
+#define PIXELS_PER_THREAD \
+ (/* each thread costs as much as */ 64.0 * 64.0 /* pixels */)
+
+
+typedef struct
+{
+ gint x;
+ gint y;
+ gint level;
+} BorderPixel;
+
+
+/* local function prototypes */
+
+static const Babl * choose_format (GeglBuffer *buffer,
+ GimpSelectCriterion select_criterion,
+ gint *n_components,
+ gboolean *has_alpha);
+static gfloat pixel_difference (const gfloat *col1,
+ const gfloat *col2,
+ gboolean antialias,
+ gfloat threshold,
+ gint n_components,
+ gboolean has_alpha,
+ gboolean select_transparent,
+ GimpSelectCriterion select_criterion);
+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);
+static gboolean find_contiguous_segment (const gfloat *col,
+ GeglBuffer *src_buffer,
+ GeglSampler *src_sampler,
+ const GeglRectangle *src_extent,
+ GeglBuffer *mask_buffer,
+ const Babl *src_format,
+ const Babl *mask_format,
+ gint n_components,
+ gboolean has_alpha,
+ gboolean select_transparent,
+ GimpSelectCriterion select_criterion,
+ gboolean antialias,
+ gfloat threshold,
+ gint initial_x,
+ gint initial_y,
+ gint *start,
+ gint *end,
+ gfloat *row);
+static void 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,
+ gboolean diagonal_neighbors,
+ gint x,
+ gint y,
+ const gfloat *col);
+
+static void line_art_queue_pixel (GQueue *queue,
+ gint x,
+ gint y,
+ gint level);
+
+
+/* public functions */
+
+GeglBuffer *
+gimp_pickable_contiguous_region_by_seed (GimpPickable *pickable,
+ gboolean antialias,
+ gfloat threshold,
+ gboolean select_transparent,
+ GimpSelectCriterion select_criterion,
+ gboolean diagonal_neighbors,
+ gint x,
+ gint y)
+{
+ GeglBuffer *src_buffer;
+ GeglBuffer *mask_buffer;
+ const Babl *format;
+ GeglRectangle extent;
+ gint n_components;
+ gboolean has_alpha;
+ gfloat start_col[MAX_CHANNELS];
+
+ g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);
+
+ gimp_pickable_flush (pickable);
+ src_buffer = gimp_pickable_get_buffer (pickable);
+
+ 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);
+
+ 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;
+ }
+
+ extent = *gegl_buffer_get_extent (src_buffer);
+
+ mask_buffer = gegl_buffer_new (&extent, babl_format ("Y float"));
+
+ 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,
+ antialias, threshold, diagonal_neighbors,
+ x, y, start_col);
+
+ GIMP_TIMER_END("foo");
+ }
+
+ return mask_buffer;
+}
+
+GeglBuffer *
+gimp_pickable_contiguous_region_by_color (GimpPickable *pickable,
+ gboolean antialias,
+ gfloat threshold,
+ gboolean select_transparent,
+ GimpSelectCriterion select_criterion,
+ const GimpRGB *color)
+{
+ /* Scan over the pickable's active layer, finding pixels within the
+ * specified threshold from the given R, G, & B values. If
+ * antialiasing is on, use the same antialiasing scheme as in
+ * fuzzy_select. Modify the pickable's mask to reflect the
+ * additional selection
+ */
+ GeglBuffer *src_buffer;
+ GeglBuffer *mask_buffer;
+ const Babl *format;
+ gint n_components;
+ gboolean has_alpha;
+ gfloat start_col[MAX_CHANNELS];
+
+ g_return_val_if_fail (GIMP_IS_PICKABLE (pickable), NULL);
+ g_return_val_if_fail (color != NULL, NULL);
+
+ /* increase the threshold by EPSILON, to allow for conversion errors,
+ * especially when threshold == 0 (see issue #1554.) we need to do this
+ * here, but not in the other functions, since the input color gets converted
+ * to the format in which we perform the comparison through a different path
+ * than the pickable's pixels, which can introduce error.
+ */
+ threshold += EPSILON;
+
+ gimp_pickable_flush (pickable);
+
+ src_buffer = gimp_pickable_get_buffer (pickable);
+
+ format = choose_format (src_buffer, select_criterion,
+ &n_components, &has_alpha);
+
+ gimp_rgba_get_pixel (color, format, start_col);
+
+ if (has_alpha)
+ {
+ if (select_transparent)
+ {
+ /* don't select transparency if "color" isn't fully transparent
+ */
+ if (start_col[n_components - 1] > 0.0)
+ select_transparent = FALSE;
+ }
+ }
+ else
+ {
+ select_transparent = FALSE;
+ }
+
+ mask_buffer = gegl_buffer_new (gegl_buffer_get_extent (src_buffer),
+ babl_format ("Y float"));
+
+ gegl_parallel_distribute_area (
+ gegl_buffer_get_extent (src_buffer), PIXELS_PER_THREAD,
+ [=] (const GeglRectangle *area)
+ {
+ GeglBufferIterator *iter;
+
+ iter = gegl_buffer_iterator_new (src_buffer,
+ area, 0, format,
+ GEGL_ACCESS_READ, GEGL_ABYSS_NONE, 2);
+
+ gegl_buffer_iterator_add (iter, mask_buffer,
+ area, 0, babl_format ("Y float"),
+ GEGL_ACCESS_WRITE, GEGL_ABYSS_NONE);
+
+ while (gegl_buffer_iterator_next (iter))
+ {
+ const gfloat *src = (const gfloat *) iter->items[0].data;
+ gfloat *dest = ( gfloat *) iter->items[1].data;
+ gint count = iter->length;
+
+ while (count--)
+ {
+ /* Find how closely the colors match */
+ *dest = pixel_difference (start_col, src,
+ antialias,
+ threshold,
+ n_components,
+ has_alpha,
+ select_transparent,
+ select_criterion);
+
+ src += n_components;
+ dest += 1;
+ }
+ }
+ });
+
+ return mask_buffer;
+}
+
+GeglBuffer *
+gimp_pickable_contiguous_region_by_line_art (GimpPickable *pickable,
+ GimpLineArt *line_art,
+ gint x,
+ gint y)
+{
+ GeglBuffer *src_buffer;
+ GeglBuffer *mask_buffer;
+ const Babl *format = babl_format ("Y float");
+ gfloat *distmap = NULL;
+ GeglRectangle extent;
+ gboolean free_line_art = FALSE;
+ gboolean filled = FALSE;
+ guchar start_col;
+
+ g_return_val_if_fail (GIMP_IS_PICKABLE (pickable) || GIMP_IS_LINE_ART (line_art), NULL);
+
+ if (! line_art)
+ {
+ /* 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).
+ */
+ line_art = gimp_line_art_new ();
+ gimp_line_art_set_input (line_art, pickable);
+ free_line_art = TRUE;
+ }
+
+ src_buffer = gimp_line_art_get (line_art, &distmap);
+ g_return_val_if_fail (src_buffer && distmap, NULL);
+
+ gegl_buffer_sample (src_buffer, x, y, NULL, &start_col, NULL,
+ GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);
+
+ extent = *gegl_buffer_get_extent (src_buffer);
+
+ mask_buffer = gegl_buffer_new (&extent, format);
+
+ if (start_col)
+ {
+ if (start_col == 1)
+ {
+ /* As a special exception, if you fill over a line art pixel, only
+ * fill the pixel and exit
+ */
+ gfloat col = 1.0;
+
+ gegl_buffer_set (mask_buffer, GEGL_RECTANGLE (x, y, 1, 1),
+ 0, format, &col, GEGL_AUTO_ROWSTRIDE);
+ }
+ else /* start_col == 2 */
+ {
+ /* If you fill over a closure pixel, let's fill on all sides
+ * of the start point. Otherwise we get a very weird result
+ * with only a single pixel filled in the middle of an empty
+ * region (since closure pixels are invisible by nature).
+ */
+ gfloat col = 0.0;
+
+ if (x - 1 >= extent.x && x - 1 < extent.x + extent.width &&
+ y - 1 >= extent.y && y - 1 < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x - 1, y - 1, &col);
+ if (x - 1 >= extent.x && x - 1 < extent.x + extent.width &&
+ y >= extent.y && y < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x - 1, y, &col);
+ if (x - 1 >= extent.x && x - 1 < extent.x + extent.width &&
+ y + 1 >= extent.y && y + 1 < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x - 1, y + 1, &col);
+ if (x >= extent.x && x < extent.x + extent.width &&
+ y - 1 >= extent.y && y - 1 < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x, y - 1, &col);
+ if (x >= extent.x && x < extent.x + extent.width &&
+ y + 1 >= extent.y && y + 1 < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x, y + 1, &col);
+ if (x + 1 >= extent.x && x + 1 < extent.x + extent.width &&
+ y - 1 >= extent.y && y - 1 < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x + 1, y - 1, &col);
+ if (x + 1 >= extent.x && x + 1 < extent.x + extent.width &&
+ y >= extent.y && y < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x + 1, y, &col);
+ if (x + 1 >= extent.x && x + 1 < extent.x + extent.width &&
+ y + 1 >= extent.y && y + 1 < (extent.y + extent.height))
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x + 1, y + 1, &col);
+ filled = TRUE;
+ }
+ }
+ else if (x >= extent.x && x < (extent.x + extent.width) &&
+ y >= extent.y && y < (extent.y + extent.height))
+ {
+ gfloat col = 0.0;
+
+ find_contiguous_region (src_buffer, mask_buffer,
+ format, 1, FALSE,
+ FALSE, GIMP_SELECT_CRITERION_COMPOSITE,
+ FALSE, 0.0, FALSE,
+ x, y, &col);
+ filled = TRUE;
+ }
+
+ if (filled)
+ {
+ GQueue *queue = g_queue_new ();
+ gfloat *mask;
+ gint width = gegl_buffer_get_width (src_buffer);
+ gint height = gegl_buffer_get_height (src_buffer);
+ gint line_art_max_grow;
+ gint nx, ny;
+
+ GIMP_TIMER_START();
+ /* 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.
+ * 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.
+ */
+ 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++)
+ {
+ if (distmap[x + y * width] == 1.0)
+ {
+ if (x > 0)
+ {
+ nx = x - 1;
+ if (y > 0)
+ {
+ ny = y - 1;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ }
+ ny = y;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ if (y < height - 1)
+ {
+ ny = y + 1;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ }
+ }
+ if (x < width - 1)
+ {
+ nx = x + 1;
+ if (y > 0)
+ {
+ ny = y - 1;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ }
+ ny = y;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ if (y < height - 1)
+ {
+ ny = y + 1;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ }
+ }
+ nx = x;
+ if (y > 0)
+ {
+ ny = y - 1;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ }
+ if (y < height - 1)
+ {
+ ny = y + 1;
+ if (mask[nx + ny * width] != 0.0)
+ {
+ line_art_queue_pixel (queue, x, y, 1);
+ continue;
+ }
+ }
+ }
+ }
+
+ g_object_get (line_art,
+ "max-grow", &line_art_max_grow,
+ NULL);
+ while (! g_queue_is_empty (queue))
+ {
+ BorderPixel *c = (BorderPixel *) g_queue_pop_head (queue);
+
+ if (mask[c->x + c->y * width] != 1.0)
+ {
+ mask[c->x + c->y * width] = 1.0;
+ if (c->level >= line_art_max_grow)
+ /* Do not overflood under line arts. */
+ continue;
+ if (c->x > 0)
+ {
+ nx = c->x - 1;
+ if (c->y > 0)
+ {
+ ny = c->y - 1;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ }
+ ny = c->y;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ if (c->y < height - 1)
+ {
+ ny = c->y + 1;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ }
+ }
+ if (c->x < width - 1)
+ {
+ nx = c->x + 1;
+ if (c->y > 0)
+ {
+ ny = c->y - 1;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ }
+ ny = c->y;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ if (c->y < height - 1)
+ {
+ ny = c->y + 1;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ }
+ }
+ nx = c->x;
+ if (c->y > 0)
+ {
+ ny = c->y - 1;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ }
+ if (c->y < height - 1)
+ {
+ ny = c->y + 1;
+ if (mask[nx + ny * width] == 0.0 &&
+ distmap[nx + ny * width] > distmap[c->x + c->y * width])
+ line_art_queue_pixel (queue, nx, ny, c->level + 1);
+ }
+ }
+ g_free (c);
+ }
+ g_queue_free (queue);
+ gegl_buffer_set (mask_buffer, gegl_buffer_get_extent (mask_buffer),
+ 0, NULL, mask, GEGL_AUTO_ROWSTRIDE);
+ g_free (mask);
+
+ GIMP_TIMER_END("watershed line art");
+ }
+ if (free_line_art)
+ g_clear_object (&line_art);
+
+ return mask_buffer;
+}
+
+/* private functions */
+
+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))
+ format = babl_format ("R'G'B'A float");
+ else
+ format = gimp_babl_format (gimp_babl_format_get_base_type (format),
+ GIMP_PRECISION_FLOAT_GAMMA,
+ *has_alpha);
+ break;
+
+ case GIMP_SELECT_CRITERION_R:
+ case GIMP_SELECT_CRITERION_G:
+ case GIMP_SELECT_CRITERION_B:
+ case GIMP_SELECT_CRITERION_A:
+ format = babl_format ("R'G'B'A float");
+ break;
+
+ case GIMP_SELECT_CRITERION_H:
+ case GIMP_SELECT_CRITERION_S:
+ case GIMP_SELECT_CRITERION_V:
+ format = babl_format ("HSVA float");
+ break;
+
+ case GIMP_SELECT_CRITERION_LCH_L:
+ format = babl_format ("CIE L alpha float");
+ break;
+
+ case GIMP_SELECT_CRITERION_LCH_C:
+ case GIMP_SELECT_CRITERION_LCH_H:
+ format = babl_format ("CIE LCH(ab) alpha float");
+ break;
+
+ default:
+ g_return_val_if_reached (NULL);
+ break;
+ }
+
+ *n_components = babl_format_get_n_components (format);
+
+ return format;
+}
+
+static gfloat
+pixel_difference (const gfloat *col1,
+ const gfloat *col2,
+ gboolean antialias,
+ gfloat threshold,
+ gint n_components,
+ gboolean has_alpha,
+ gboolean select_transparent,
+ GimpSelectCriterion select_criterion)
+{
+ gfloat max = 0.0;
+
+ /* if there is an alpha channel, never select transparent regions */
+ if (! select_transparent && has_alpha && col2[n_components - 1] == 0.0)
+ return 0.0;
+
+ if (select_transparent && has_alpha)
+ {
+ max = fabs (col1[n_components - 1] - col2[n_components - 1]);
+ }
+ else
+ {
+ gfloat diff;
+ gint b;
+
+ if (has_alpha)
+ n_components--;
+
+ switch (select_criterion)
+ {
+ case GIMP_SELECT_CRITERION_COMPOSITE:
+ for (b = 0; b < n_components; b++)
+ {
+ diff = fabs (col1[b] - col2[b]);
+ if (diff > max)
+ max = diff;
+ }
+ break;
+
+ case GIMP_SELECT_CRITERION_R:
+ max = fabs (col1[0] - col2[0]);
+ break;
+
+ case GIMP_SELECT_CRITERION_G:
+ max = fabs (col1[1] - col2[1]);
+ break;
+
+ case GIMP_SELECT_CRITERION_B:
+ max = fabs (col1[2] - col2[2]);
+ break;
+
+ case GIMP_SELECT_CRITERION_A:
+ max = fabs (col1[3] - col2[3]);
+ break;
+
+ case GIMP_SELECT_CRITERION_H:
+ if (col1[1] > EPSILON)
+ {
+ if (col2[1] > EPSILON)
+ {
+ max = fabs (col1[0] - col2[0]);
+ max = MIN (max, 1.0 - max);
+ }
+ else
+ {
+ /* "infinite" difference. anything >> 1 will do. */
+ max = 10.0;
+ }
+ }
+ else
+ {
+ if (col2[1] > EPSILON)
+ {
+ /* "infinite" difference. anything >> 1 will do. */
+ max = 10.0;
+ }
+ else
+ {
+ max = 0.0;
+ }
+ }
+ break;
+
+ case GIMP_SELECT_CRITERION_S:
+ max = fabs (col1[1] - col2[1]);
+ break;
+
+ case GIMP_SELECT_CRITERION_V:
+ max = fabs (col1[2] - col2[2]);
+ break;
+
+ 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:
+ if (col1[1] > 100.0 * EPSILON)
+ {
+ if (col2[1] > 100.0 * EPSILON)
+ {
+ max = fabs (col1[2] - col2[2]) / 360.0;
+ max = MIN (max, 1.0 - max);
+ }
+ else
+ {
+ /* "infinite" difference. anything >> 1 will do. */
+ max = 10.0;
+ }
+ }
+ else
+ {
+ if (col2[1] > 100.0 * EPSILON)
+ {
+ /* "infinite" difference. anything >> 1 will do. */
+ max = 10.0;
+ }
+ else
+ {
+ max = 0.0;
+ }
+ }
+ break;
+ }
+ }
+
+ if (antialias && threshold > 0.0)
+ {
+ gfloat aa = 1.5 - (max / threshold);
+
+ if (aa <= 0.0)
+ return 0.0;
+ else if (aa < 0.5)
+ return aa * 2.0;
+ else
+ return 1.0;
+ }
+ else
+ {
+ if (max > threshold)
+ return 0.0;
+ else
+ return 1.0;
+ }
+}
+
+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));
+}
+
+/* #define FETCH_ROW 1 */
+
+static gboolean
+find_contiguous_segment (const gfloat *col,
+ GeglBuffer *src_buffer,
+ GeglSampler *src_sampler,
+ const GeglRectangle *src_extent,
+ GeglBuffer *mask_buffer,
+ const Babl *src_format,
+ const Babl *mask_format,
+ gint n_components,
+ gboolean has_alpha,
+ gboolean select_transparent,
+ GimpSelectCriterion select_criterion,
+ gboolean antialias,
+ gfloat threshold,
+ gint initial_x,
+ gint initial_y,
+ gint *start,
+ gint *end,
+ gfloat *row)
+{
+ gfloat *s;
+ gfloat mask_row_buf[src_extent->width];
+ gfloat *mask_row = mask_row_buf - src_extent->x;
+ gfloat diff;
+
+#ifdef FETCH_ROW
+ gegl_buffer_get (src_buffer, GEGL_RECTANGLE (0, initial_y, width, 1), 1.0,
+ src_format,
+ row, GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);
+ s = row + initial_x * n_components;
+#else
+ s = (gfloat *) g_alloca (n_components * sizeof (gfloat));
+
+ gegl_sampler_get (src_sampler,
+ initial_x, initial_y, NULL, s, GEGL_ABYSS_NONE);
+#endif
+
+ diff = pixel_difference (col, s, antialias, threshold,
+ n_components, has_alpha, select_transparent,
+ select_criterion);
+
+ /* check the starting pixel */
+ if (! diff)
+ return FALSE;
+
+ mask_row[initial_x] = diff;
+
+ *start = initial_x - 1;
+#ifdef FETCH_ROW
+ s = row + *start * n_components;
+#endif
+
+ while (*start >= src_extent->x)
+ {
+#ifndef FETCH_ROW
+ gegl_sampler_get (src_sampler,
+ *start, initial_y, NULL, s, GEGL_ABYSS_NONE);
+#endif
+
+ diff = pixel_difference (col, s, antialias, threshold,
+ n_components, has_alpha, select_transparent,
+ select_criterion);
+ if (diff == 0.0)
+ break;
+
+ mask_row[*start] = diff;
+
+ (*start)--;
+#ifdef FETCH_ROW
+ s -= n_components;
+#endif
+ }
+
+ *end = initial_x + 1;
+#ifdef FETCH_ROW
+ s = row + *end * n_components;
+#endif
+
+ while (*end < src_extent->x + src_extent->width)
+ {
+#ifndef FETCH_ROW
+ gegl_sampler_get (src_sampler,
+ *end, initial_y, NULL, s, GEGL_ABYSS_NONE);
+#endif
+
+ diff = pixel_difference (col, s, antialias, threshold,
+ n_components, has_alpha, select_transparent,
+ select_criterion);
+ if (diff == 0.0)
+ break;
+
+ mask_row[*end] = diff;
+
+ (*end)++;
+#ifdef FETCH_ROW
+ s += n_components;
+#endif
+ }
+
+ gegl_buffer_set (mask_buffer, GEGL_RECTANGLE (*start + 1, initial_y,
+ *end - *start - 1, 1),
+ 0, mask_format, &mask_row[*start + 1],
+ GEGL_AUTO_ROWSTRIDE);
+
+ return TRUE;
+}
+
+static void
+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,
+ gboolean diagonal_neighbors,
+ gint x,
+ gint y,
+ const gfloat *col)
+{
+ const Babl *mask_format = babl_format ("Y float");
+ GeglSampler *src_sampler;
+ const GeglRectangle *src_extent;
+ gint old_y;
+ gint start, end;
+ gint new_start, new_end;
+ GQueue *segment_queue;
+ gfloat *row = NULL;
+
+ src_extent = gegl_buffer_get_extent (src_buffer);
+
+#ifdef FETCH_ROW
+ row = g_new (gfloat, src_extent->width * n_components);
+#endif
+
+ src_sampler = gegl_buffer_sampler_new (src_buffer,
+ format, GEGL_SAMPLER_NEAREST);
+
+ segment_queue = g_queue_new ();
+
+ push_segment (segment_queue,
+ y, /* dummy values: */ -1, 0, 0,
+ y, x - 1, x + 1);
+
+ do
+ {
+ pop_segment (segment_queue,
+ &y, &old_y, &start, &end);
+
+ for (x = start + 1; x < end; x++)
+ {
+ gfloat val;
+
+ gegl_buffer_get (mask_buffer, GEGL_RECTANGLE (x, y, 1, 1), 1.0,
+ mask_format, &val, GEGL_AUTO_ROWSTRIDE,
+ GEGL_ABYSS_NONE);
+
+ if (val != 0.0)
+ {
+ /* 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;
+ }
+
+ if (! find_contiguous_segment (col,
+ src_buffer, src_sampler, src_extent,
+ mask_buffer,
+ format, mask_format,
+ n_components,
+ has_alpha,
+ select_transparent, select_criterion,
+ antialias, threshold, x, y,
+ &new_start, &new_end,
+ row))
+ continue;
+
+ /* 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;
+
+ if (diagonal_neighbors)
+ {
+ if (new_start >= src_extent->x)
+ new_start--;
+
+ if (new_end < src_extent->x + src_extent->width)
+ new_end++;
+ }
+
+ if (y + 1 < src_extent->y + src_extent->height)
+ {
+ push_segment (segment_queue,
+ y, old_y, start, end,
+ y + 1, new_start, new_end);
+ }
+
+ if (y - 1 >= src_extent->y)
+ {
+ push_segment (segment_queue,
+ y, old_y, start, end,
+ y - 1, new_start, new_end);
+ }
+
+ }
+ }
+ while (! g_queue_is_empty (segment_queue));
+
+ g_queue_free (segment_queue);
+
+ g_object_unref (src_sampler);
+
+#ifdef FETCH_ROW
+ g_free (row);
+#endif
+}
+
+static void
+line_art_queue_pixel (GQueue *queue,
+ gint x,
+ gint y,
+ gint level)
+{
+ BorderPixel *p = g_new (BorderPixel, 1);
+
+ p->x = x;
+ p->y = y;
+ p->level = level;
+
+ g_queue_push_head (queue, p);
+}
+
+} /* extern "C" */