[gegl/soc-2011-seamless-clone: 31/49] Rewrite the outline finding algorithm for seamless clone operation
- From: Barak Itkin <barakitkin src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gegl/soc-2011-seamless-clone: 31/49] Rewrite the outline finding algorithm for seamless clone operation
- Date: Sat, 29 Sep 2012 20:29:28 +0000 (UTC)
commit 786646145644cf1e6d38a86eff637d62dc7a016d
Author: Barak Itkin <lightningismyname gmail com>
Date: Sat Jul 14 22:28:38 2012 +0300
Rewrite the outline finding algorithm for seamless clone operation
This commit should solve two bugs:
1. Do not get stuck in infinite loops on certain shapes
2. Offset the entire outline by 0.25px outside along the normal to avoid
duplicate points in 1px wide areas (duplicate points can not be accepted
by the meshing algorithm)
operations/common/seamless-clone/find-outline.c | 280 ++++++++++----------
operations/common/seamless-clone/find-outline.h | 75 +++++-
operations/common/seamless-clone/make-mesh.c | 40 ++--
.../common/seamless-clone/seamless-clone-common.c | 4 +-
4 files changed, 233 insertions(+), 166 deletions(-)
---
diff --git a/operations/common/seamless-clone/find-outline.c b/operations/common/seamless-clone/find-outline.c
index cb329da..892e43d 100644
--- a/operations/common/seamless-clone/find-outline.c
+++ b/operations/common/seamless-clone/find-outline.c
@@ -28,200 +28,192 @@
*/
#include <gegl.h>
-#include <stdio.h> /* TODO: get rid of this debugging way! */
+
#include "seamless-clone.h"
#include <poly2tri-c/p2t/poly2tri.h>
#include <poly2tri-c/refine/refine.h>
-/* Define the directions
- *
- * 0
- *
- * 7 N 1
- * ^
- * |
- * |
- * 6 W<----+---->E 2
- * | =====>X
- * | ||
- * v ||
- * 5 S 3 ||
- * vv
- * 4 Y
- */
-typedef enum {
- D_N = 0, /* 000 */
- D_NE = 1, /* 001 */
- D_E = 2, /* 010 */
- D_SE = 3, /* 011 */
- D_S = 4, /* 100 */
- D_SW = 5, /* 101 */
- D_W = 6, /* 110 */
- D_NW = 7 /* 111 */
-} OUTLINE_DIRECTION;
-
-#define cwdirection(t) (((t)+1)%8)
-#define ccwdirection(t) (((t)+7)%8)
-#define oppositedirection(t) (((t)+4)%8)
-
-#define isSouth(s) (((s) == D_S) || ((s) == D_SE) || ((s) == D_SW))
-#define isNorth(s) (((s) == D_N) || ((s) == D_NE) || ((s) == D_NW))
-
-#define isEast(s) (((s) == D_NE) || ((s) == D_E) || ((s) == D_SE))
-#define isWest(s) (((s) == D_NW) || ((s) == D_W) || ((s) == D_SW))
-
-/**
- * Add a COPY of the given point into the array pts. The original point CAN
- * be freed later!
- */
static inline void
-add_point (GPtrArray* pts, ScPoint *pt)
+sc_point_copy_to (const ScPoint *src,
+ ScPoint *dst)
{
- ScPoint *cpy = g_slice_new (ScPoint);
- cpy->x = pt->x;
- cpy->y = pt->y;
+ dst->x = src->x;
+ dst->y = src->y;
+ dst->outside_normal = src->outside_normal;
+}
- g_ptr_array_add (pts, cpy);
+static inline ScPoint*
+sc_point_copy (const ScPoint *src)
+{
+ ScPoint *self = g_slice_new (ScPoint);
+ sc_point_copy_to (src, self);
+ return self;
}
-static inline void
-spoint_move (ScPoint *pt, OUTLINE_DIRECTION t, ScPoint *dest)
+static inline ScPoint*
+sc_point_move (const ScPoint *src,
+ ScDirection t,
+ ScPoint *dst)
{
- dest->x = pt->x + (isEast(t) ? 1 : (isWest(t) ? -1 : 0));
- dest->y = pt->y + (isSouth(t) ? 1 : (isNorth(t) ? -1 : 0));
+ dst->x = src->x + SC_DIRECTION_XOFFSET (t, 1);
+ dst->y = src->y + SC_DIRECTION_YOFFSET (t, 1);
+ return dst;
}
static inline gboolean
-in_range(gint val,gint min,gint max)
+sc_point_eq (const ScPoint *pt1,
+ const ScPoint *pt2)
{
- return (((min) <= (val)) && ((val) <= (max)));
+ return pt1->x == pt2->x && pt1->y == pt2->y;
}
-static inline gfloat
-sc_sample_alpha (GeglBuffer *buf, gint x, gint y, const Babl *format)
+static gint
+sc_point_cmp (const ScPoint *pt1,
+ const ScPoint *pt2)
{
- gfloat col[4] = {0, 0, 0, 0};
- gegl_buffer_sample (buf, x, y, NULL, col, format, GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);
- return col[3];
+ if (pt1->y < pt2->y)
+ return -1;
+ else if (pt1->y > pt2->y)
+ return +1;
+ else
+ {
+ if (pt1->x < pt2->x)
+ return -1;
+ else if (pt1->x > pt2->x)
+ return +1;
+ else
+ return 0;
+ }
}
static inline gboolean
-is_opaque (const GeglRectangle *rect,
- GeglBuffer *pixels,
+in_range (gint val,
+ gint min,
+ gint max)
+{
+ return (min <= val) && (val <= max);
+}
+
+static inline gboolean
+in_rectangle (const GeglRectangle *rect,
+ const ScPoint *pt)
+{
+ return in_range (pt->x, rect->x, rect->x + rect->width - 1)
+ && in_range (pt->y, rect->y, rect->y + rect->height - 1);
+}
+
+static inline gboolean
+is_opaque (const GeglRectangle *search_area,
+ GeglBuffer *buffer,
const Babl *format,
const ScPoint *pt)
{
- g_assert (pt != NULL);
- g_assert (rect != NULL);
+ gfloat col[4] = {0, 0, 0, 0};
+
+ if (! in_rectangle (search_area, pt))
+ return FALSE;
+
+ gegl_buffer_sample (buffer, pt->x, pt->y, NULL, col, format,
+ GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);
+
+ return col[3] >= 0.5f;
+}
+
+/* This function assumes the pixel is white! */
+static inline gboolean
+is_opaque_island (const GeglRectangle *search_area,
+ GeglBuffer *buffer,
+ const Babl *format,
+ const ScPoint *pt)
+{
+ gint i;
+ ScPoint temp;
+
+ for (i = 0; i < 8; ++i)
+ if (is_opaque (search_area, buffer, format, sc_point_move (pt, i, &temp)))
+ return FALSE;
- return in_range(pt->x, rect->x, rect->x + rect->width - 1)
- && in_range(pt->y, rect->y, rect->y + rect->height - 1)
- && (sc_sample_alpha (pixels, pt->x, pt->y, format) >= 0.5f);
+ return TRUE;
}
-/* This function receives a white pixel (pt) and the direction of the movement
- * that lead to it (prevdirection). It will return the direction leading to the
- * next white pixel (while following the edges in CW order), and the pixel
- * itself would be stored in dest.
- *
- * The logic is simple:
- * 1. Try to continue in the same direction that lead us to the current pixel
- * 2. Dprev = oppposite(prevdirection)
- * 3. Dnow = cw(Dprev)
- * 4. While moving to Dnow is white:
- * 4.1. Dprev = Dnow
- * 4.2. Dnow = cw(D)
- * 5. Return the result - moving by Dprev
- */
-static inline OUTLINE_DIRECTION
-outline_walk_cw (const GeglRectangle *rect,
- GeglBuffer *pixels,
- const Babl *format,
- OUTLINE_DIRECTION prevdirection,
- ScPoint *pt,
- ScPoint *dest)
+static inline ScDirection
+walk_cw (const GeglRectangle *search_area,
+ GeglBuffer *buffer,
+ const Babl *format,
+ const ScPoint *cur_pt,
+ ScDirection dir_from_prev,
+ ScPoint *next_pt)
{
- OUTLINE_DIRECTION Dprev = oppositedirection(prevdirection);
- OUTLINE_DIRECTION Dnow = cwdirection (Dprev);
-
- ScPoint ptN, ptP;
+ ScDirection dir_to_prev = SC_DIRECTION_OPPOSITE (dir_from_prev);
+ ScDirection dir_to_next = SC_DIRECTION_CW (dir_to_prev);
- spoint_move (pt, Dprev, &ptP);
- spoint_move (pt, Dnow, &ptN);
+ sc_point_move (cur_pt, dir_to_next, next_pt);
- while (is_opaque (rect, pixels, format, &ptN))
+ while (! is_opaque (search_area, buffer, format, next_pt))
{
- Dprev = Dnow;
- ptP.x = ptN.x;
- ptP.y = ptN.y;
- Dnow = cwdirection (Dprev);
- spoint_move (pt, Dnow, &ptN);
+ dir_to_next = SC_DIRECTION_CW (dir_to_next);
+ sc_point_move (cur_pt, dir_to_next, next_pt);
}
- dest->x = ptP.x;
- dest->y = ptP.y;
- return Dprev;
+ return dir_to_next;
}
-#define pteq(pt1,pt2) (((pt1)->x == (pt2)->x) && ((pt1)->y == (pt2)->y))
-
-GPtrArray*
-sc_outline_find_ccw (const GeglRectangle *rect,
- GeglBuffer *pixels)
+ScOutline*
+sc_outline_find (const GeglRectangle *search_area,
+ GeglBuffer *buffer)
{
const Babl *format = babl_format("RGBA float");
- GPtrArray *points = g_ptr_array_new ();
-
- gint x = rect->x, y;
+ ScOutline *result = g_ptr_array_new ();
gboolean found = FALSE;
- ScPoint START, pt, ptN;
- OUTLINE_DIRECTION DIR, DIRN;
+ ScPoint current, next, *first;
+ ScDirection to_next;
+
+ gint row_max = search_area->x + search_area->width;
+ gint col_max = search_area->y + search_area->height;
- /* First of all try to find a white pixel */
- for (y = rect->y; y < rect->y + rect->height; y++)
+ for (current.y = search_area->y; current.y < row_max; ++current.y)
{
- for (x = rect->x; x < rect->x + rect->width; x++)
- {
- if (sc_sample_alpha (pixels, x, y, format) >= 0.5f)
- {
- found = TRUE;
- break;
- }
- }
- if (found) break;
+ for (current.x = search_area->x; current.x < col_max; ++current.x)
+ if (is_opaque (search_area, buffer, format, ¤t)
+ && ! is_opaque_island (search_area, buffer, format, ¤t))
+ {
+ found = TRUE;
+ break;
+ }
+
+ if (found)
+ break;
}
- if (!found)
- return points;
-
- pt.x = START.x = x;
- pt.y = START.y = y;
- DIR = D_NW;
-
- add_point (points, &START);
+ if (found)
+ {
+ current.outside_normal = SC_DIRECTION_N;
+ g_ptr_array_add (result, first = sc_point_copy (¤t));
- DIRN = outline_walk_cw (rect, pixels, format, DIR,&pt,&ptN);
+ to_next = walk_cw (search_area, buffer, format, ¤t,
+ SC_DIRECTION_E, &next);
- while (! pteq(&ptN,&START))
- {
- add_point (points, &ptN);
- pt.x = ptN.x;
- pt.y = ptN.y;
- DIR = DIRN;
- DIRN = outline_walk_cw (rect, pixels, format, DIR,&pt,&ptN);
+ while (! sc_point_eq (&next, first))
+ {
+ next.outside_normal = SC_DIRECTION_CW(SC_DIRECTION_CW(to_next));
+ g_ptr_array_add (result, sc_point_copy (&next));
+ sc_point_copy_to (&next, ¤t);
+ to_next = walk_cw (search_area, buffer, format, ¤t,
+ to_next, &next);
+ }
}
- return points;
+ return result;
}
void
sc_outline_free (ScOutline *self)
{
- GPtrArray *real = (GPtrArray*) self;
- gint i;
- for (i = 0; i < real->len; i++)
- g_slice_free (ScPoint, g_ptr_array_index (self, i));
- g_ptr_array_free (real, TRUE);
+ GPtrArray *real = (GPtrArray*) self;
+ gint i;
+ for (i = 0; i < real->len; i++)
+ g_slice_free (ScPoint, g_ptr_array_index (self, i));
+ g_ptr_array_free (real, TRUE);
}
diff --git a/operations/common/seamless-clone/find-outline.h b/operations/common/seamless-clone/find-outline.h
index f3762c2..01e1fc1 100644
--- a/operations/common/seamless-clone/find-outline.h
+++ b/operations/common/seamless-clone/find-outline.h
@@ -22,8 +22,81 @@
#include <gegl.h>
+/**
+ * An enumeration for representing progress directions in 2 dimensions
+ * <pre>
+ * 0
+ *
+ * 7 N 1
+ * ^
+ * |
+ * 6 W<--+-->E 2
+ * | =====>X
+ * v ||
+ * 5 S 3 ||
+ * vv
+ * 4 Y
+ * </pre>
+ */
+typedef enum {
+ SC_DIRECTION_N = 0,
+ SC_DIRECTION_NE = 1,
+ SC_DIRECTION_E = 2,
+ SC_DIRECTION_SE = 3,
+ SC_DIRECTION_S = 4,
+ SC_DIRECTION_SW = 5,
+ SC_DIRECTION_W = 6,
+ SC_DIRECTION_NW = 7
+} ScDirection;
+
+#define SC_DIRECTION_CW(d) (((d)+1)%8)
+#define SC_DIRECTION_CCW(d) (((d)+7)%8)
+#define SC_DIRECTION_OPPOSITE(d) (((d)+4)%8)
+
+#define SC_DIRECTION_IS_NORTH(d) ( \
+ ((d) == SC_DIRECTION_N) || \
+ ((d) == SC_DIRECTION_NE) || \
+ ((d) == SC_DIRECTION_NW) \
+)
+
+#define SC_DIRECTION_IS_SOUTH(d) ( \
+ ((d) == SC_DIRECTION_S) || \
+ ((d) == SC_DIRECTION_SE) || \
+ ((d) == SC_DIRECTION_SW) \
+)
+
+#define SC_DIRECTION_IS_EAST(d) ( \
+ ((d) == SC_DIRECTION_E) || \
+ ((d) == SC_DIRECTION_NE) || \
+ ((d) == SC_DIRECTION_SE) \
+)
+
+#define SC_DIRECTION_IS_WEST(d) ( \
+ ((d) == SC_DIRECTION_W) || \
+ ((d) == SC_DIRECTION_NW) || \
+ ((d) == SC_DIRECTION_SW) \
+)
+
+#define SC_DIRECTION_XOFFSET(d,s) ( \
+ (SC_DIRECTION_IS_EAST(d)) ? (s) : \
+ ((SC_DIRECTION_IS_WEST(d)) ? -(s) : \
+ 0) \
+)
+
+#define SC_DIRECTION_YOFFSET(d,s) ( \
+ (SC_DIRECTION_IS_SOUTH(d)) ? (s) : \
+ ((SC_DIRECTION_IS_NORTH(d)) ? -(s) : \
+ 0) \
+)
+
+/**
+ * A struct for representing a point which belongs to an outline,
+ * together with the direction which is the normal pointing outside
+ * of the interior area defined by the outline
+ */
typedef struct {
gint x, y;
+ ScDirection outside_normal;
} ScPoint;
/* Define a type for the outline to distinguish it from all the other
@@ -33,7 +106,7 @@ typedef struct {
*/
typedef GPtrArray ScOutline;
-ScOutline* sc_outline_find_ccw (const GeglRectangle *rect, GeglBuffer *pixels);
+ScOutline* sc_outline_find (const GeglRectangle *rect, GeglBuffer *pixels);
void sc_outline_free (ScOutline *self);
diff --git a/operations/common/seamless-clone/make-mesh.c b/operations/common/seamless-clone/make-mesh.c
index 55e7bbe..176ecb1 100644
--- a/operations/common/seamless-clone/make-mesh.c
+++ b/operations/common/seamless-clone/make-mesh.c
@@ -1,6 +1,6 @@
/* This file is an image processing operation for GEGL
*
- * seamless-clone.c
+ * make-mesh.c
* Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
*
* This program is free software: you can redistribute it and/or modify
@@ -70,16 +70,16 @@ sc_compute_sample_list_part (ScOutline *outline,
if (!needsMore || d <= 1)
{
- g_ptr_array_add (sl->points, pt1);
- return;
- }
+ g_ptr_array_add (sl->points, pt1);
+ return;
+ }
else
{
- gint index12 = (index1 + index2) / 2;
- sc_compute_sample_list_part (outline, index1, index12, Px, Py, sl, k + 1);
- sc_compute_sample_list_part (outline, index12, index2, Px, Py, sl, k + 1);
- return;
- }
+ gint index12 = (index1 + index2) / 2;
+ sc_compute_sample_list_part (outline, index1, index12, Px, Py, sl, k + 1);
+ sc_compute_sample_list_part (outline, index12, index2, Px, Py, sl, k + 1);
+ return;
+ }
}
static void
@@ -113,7 +113,7 @@ sc_compute_sample_list_weights (gdouble Px,
/* Did the point match one of the outline points? */
if (norm1 == 0)
{
- gdouble temp = 1;
+ gdouble temp = 1;
g_ptr_array_remove_range (sl->points, 0, N);
/* No weights yet so nothing to remove */
@@ -127,13 +127,13 @@ sc_compute_sample_list_weights (gdouble Px,
if (temp <= 1 && temp >= -1)
{
- /* Result is in the range of 0 to PI */
+ /* Result is in the range of 0 to PI */
ang = acos (temp);
}
else
{
- ang = 0;
- }
+ ang = 0;
+ }
tan_as_half[i] = tan (ang / 2);
tan_as_half[i] = ABS (tan_as_half[i]);
@@ -147,7 +147,7 @@ sc_compute_sample_list_weights (gdouble Px,
weightTemp = (tan_as_half[i - 1] + tan_as_half[i % N]) / pow (norms[i % N], 2);
sl->total_weight += weightTemp;
g_array_append_val (sl->weights, weightTemp);
- }
+ }
}
ScSampleList*
@@ -247,15 +247,17 @@ sc_make_fine_mesh (ScOutline *outline,
for (i = 0; i < N; i++)
{
ScPoint *pt = (ScPoint*) g_ptr_array_index (realOutline, i);
+ gdouble realX = pt->x + SC_DIRECTION_XOFFSET (pt->outside_normal, 0.25);
+ gdouble realY = pt->y + SC_DIRECTION_YOFFSET (pt->outside_normal, 0.25);
- min_x = MIN (pt->x, min_x);
- min_y = MIN (pt->y, min_y);
- max_x = MAX (pt->x, max_x);
- max_y = MAX (pt->y, max_y);
+ min_x = MIN (realX, min_x);
+ min_y = MIN (realY, min_y);
+ max_x = MAX (realX, max_x);
+ max_y = MAX (realY, max_y);
/* No one should care if the points are given in reverse order,
* and prepending to the GList is more efficient */
- g_ptr_array_add (mesh_points, p2t_point_new_dd (pt->x, pt->y));
+ g_ptr_array_add (mesh_points, p2t_point_new_dd (realX, realY));
}
mesh_bounds->x = min_x;
diff --git a/operations/common/seamless-clone/seamless-clone-common.c b/operations/common/seamless-clone/seamless-clone-common.c
index 4fbadc3..555923e 100644
--- a/operations/common/seamless-clone/seamless-clone-common.c
+++ b/operations/common/seamless-clone/seamless-clone-common.c
@@ -111,7 +111,7 @@ sc_point_to_color_func (P2trPoint *point,
dest_c[1] += weight * (input_c[1] - aux_c[1]);
dest_c[2] += weight * (input_c[2] - aux_c[2]);
weightT += weight;
- }
+ }
col_cpy[0] = dest[0] = dest_c[0] / weightT;
col_cpy[1] = dest[1] = dest_c[1] / weightT;
@@ -256,7 +256,7 @@ sc_generate_cache (GeglBuffer *fg,
ScCache *result = g_new0 (ScCache, 1);
/* Find an outline around the area of the paste */
- outline = sc_outline_find_ccw (extents, fg);
+ outline = sc_outline_find (extents, fg);
/* Create a fine mesh from the polygon defined by that outline */
result->mesh = sc_make_fine_mesh (outline, &result->mesh_bounds,
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
