Does anyone find iscissors useful? Does it do what you would
like or expect? If not, then you may want to test this patch for me.
Since ISCISSORS is currently a bug, help fix it.
This patch adds the livewire path to iscissors. Now you can
see where the actual line is going to end up. There are still a few
bugs and some memory leaks that should be worked out soon, but I am
interested in a complete rewrite.
There are a few issues with a rewrite of iscissors. In order
to be effective I need to know how to do the following:
1. Allocate a buffer the same size as the (x,y) of the visible portion
of the image. This buffer will be destroyed when the tool is closed
or the image changes.
2. Allocate a task to compute values in the background so that the
mouse can still be moved while the computation takes place.
#2 is the hard part. I can do #1 with the current tile system.
Are there any capabilities in the gimp to allow #2? If not, then
iscissors probably won't get much better than this patch.
(ok, a little, but it can't keep up when running on a i586 233 MMX over a
10 MBit network connection to the xserver--my test setup ).
Anyway, try it out, tell me if you like it. I may become motivated to
finish it then...
Laramie
--- iscissors.old Fri Sep 15 18:51:04 2000
+++ iscissors.c Fri Sep 15 19:59:43 2000
@@ -30,6 +30,10 @@
* The 0.54 version of the algorithm was then forwards ported to 1.1.4
* by Austin Donnelly. */
+/* Modifications to implement the livewire boundary were done in version
+ * gimp 1.1.25 by Laramie Leavitt */
+
+
#include "config.h"
#include <stdlib.h>
@@ -89,8 +93,10 @@
DRAW_NOTHING = 0x0,
DRAW_CURRENT_SEED = 0x1,
DRAW_CURVE = 0x2,
- DRAW_ACTIVE_CURVE = 0x4
+ DRAW_ACTIVE_CURVE = 0x4,
+ DRAW_LIVEWIRE = 0x8
} Iscissors_draw;
+
#define DRAW_ALL (DRAW_CURRENT_SEED | DRAW_CURVE)
typedef struct _iscissors Iscissors;
@@ -107,6 +113,8 @@
TempBuf *dp_buf; /* dynamic programming buffer */
+ ICurve *livewire;
+
ICurve *curve1; /* 1st curve connected to current point */
ICurve *curve2; /* 2nd curve connected to current point */
@@ -121,6 +129,8 @@
/* XXX might be useful */
Channel *mask; /* selection mask */
TileManager *gradient_map; /* lazily filled gradient map */
+ TileManager *cost_map; /* lazily filled in cost map */
+
};
typedef struct _IScissorsOptions IScissorsOptions;
@@ -136,22 +146,35 @@
/* Other defines... */
#define MAX_GRADIENT 179.606 /* == sqrt(127^2 + 127^2) */
+
#define GRADIENT_SEARCH 32 /* how far to look when snapping to an edge */
+#define GRADIENT_RADIUS (GRADIENT_SEARCH >> 1)
+
#define TARGET_HEIGHT 25
#define TARGET_WIDTH 25
+
#define POINT_WIDTH 8 /* size (in pixels) of seed handles */
#define POINT_HALFWIDTH (POINT_WIDTH / 2)
+
#define EXTEND_BY 0.2 /* proportion to expand cost map by */
#define FIXED 5 /* additional fixed size to expand cost map */
#define MIN_GRADIENT 63 /* gradients < this are directionless */
#define MAX_POINTS 2048
+#define POS_GRADIENT 0
+#define POS_COST 1
+#define POS_DIR 2
+#define POS_LAPLACE 3
+
#ifdef USE_LAPLACIAN
-# define COST_WIDTH 3 /* number of bytes for each pixel in cost map */
+# define TOTAL_COST_WIDTH 4
#else
-# define COST_WIDTH 2 /* number of bytes for each pixel in cost map */
+# define TOTAL_COST_WIDTH 3
#endif
+
+#define TILE_LAYER( tile, layer ) ((tile_ewidth(tile)*tile_eheight(tile))*layer)
+
#define BLOCK_WIDTH 64
#define BLOCK_HEIGHT 64
#define CONV_WIDTH (BLOCK_WIDTH + 2)
@@ -174,7 +197,6 @@
#define PIXEL_COST(x) (x >> 8)
#define PIXEL_DIR(x) (x & 0x000000ff)
-
/* static variables */
/* where to move on a given link direction */
@@ -212,7 +234,15 @@
D(static guint sent2 = 0xd2d2d2d2);
static guchar maxgrad_conv2 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
D(static guint sent3 = 0xd3d3d3d3);
+static guchar costgrad_conv0 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
+D(static guint sent1 = 0xd4d4d4d4);
+static guchar costgrad_conv1 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
+D(static guint sent2 = 0xd5d5d5d5);
+#ifdef USE_LAPLACIAN
+static guchar costgrad_conv2 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
+D(static guint sent2 = 0xd6d6d6d6);
+#endif
static gint horz_deriv [9] =
{
@@ -228,6 +258,12 @@
-1, -2, -1,
};
+static gint blur_32 [9] =
+{
+ 1, 1, 1,
+ 1, 24, 1,
+ 1, 1, 1,
+};
#ifdef USE_LAPLACIAN
static gint laplacian [9] =
@@ -238,13 +274,7 @@
};
#endif
-static gint blur_32 [9] =
-{
- 1, 1, 1,
- 1, 24, 1,
- 1, 1, 1,
-};
-
+static gboolean first_gradient = TRUE;
static gfloat distance_weights [GRADIENT_SEARCH * GRADIENT_SEARCH];
static gint diagonal_weight [256];
@@ -354,6 +384,7 @@
private->core = draw_core_new (iscissors_draw);
private->op = -1;
private->curves = NULL;
+ private->livewire = NULL;
private->dp_buf = NULL;
private->state = NO_ACTION;
private->mask = NULL;
@@ -470,7 +501,7 @@
iscissors->nx = iscissors->x;
iscissors->ny = iscissors->y;
iscissors->state = SEED_ADJUSTMENT;
- iscissors->draw = DRAW_ACTIVE_CURVE;
+ iscissors->draw = DRAW_ACTIVE_CURVE | DRAW_LIVEWIRE;
draw_core_resume (iscissors->core, tool);
grab_pointer = TRUE;
}
@@ -506,7 +537,7 @@
else if (!iscissors->connected)
{
iscissors->state = SEED_PLACEMENT;
- iscissors->draw = DRAW_CURRENT_SEED;
+ iscissors->draw = DRAW_CURRENT_SEED | DRAW_LIVEWIRE;
grab_pointer = TRUE;
draw_core_resume (iscissors->core, tool);
@@ -631,6 +662,7 @@
}
}
+ /* TODO: Use the livewire segment instead of recomputing */
/* Create the new curve segment */
if (iscissors->ix != iscissors->x ||
iscissors->iy != iscissors->y)
@@ -703,7 +735,7 @@
return;
if (iscissors->state == SEED_PLACEMENT)
- iscissors->draw = DRAW_CURRENT_SEED;
+ iscissors->draw = DRAW_CURRENT_SEED | DRAW_LIVEWIRE;
else if (iscissors->state == SEED_ADJUSTMENT)
iscissors->draw = DRAW_ACTIVE_CURVE;
@@ -778,13 +810,58 @@
gdk_draw_line (iscissors->core->win, iscissors->core->gc,
tx2 - (TARGET_WIDTH >> 1), ty2,
tx2 + (TARGET_WIDTH >> 1), ty2);
+
gdk_draw_line (iscissors->core->win, iscissors->core->gc,
tx2, ty2 - (TARGET_HEIGHT >> 1),
tx2, ty2 + (TARGET_HEIGHT >> 1));
+ }
- if (!iscissors->first_point)
+// Calculate livewire.
+ if ((iscissors->draw & DRAW_LIVEWIRE) && !iscissors->first_point )
+ {
+ if( !iscissors->livewire ||
+ (iscissors->livewire
+ && ( iscissors->ix != iscissors->livewire->x1
+ || iscissors->x != iscissors->livewire->x2
+ || iscissors->iy != iscissors->livewire->y1
+ || iscissors->y != iscissors->livewire->y2 )
+ )
+ )
+ {
+
+ curve = g_new (ICurve, 1);
+
+ curve->x1 = iscissors->ix;
+ curve->y1 = iscissors->iy;
+ curve->x2 = iscissors->x;
+ curve->y2 = iscissors->y;
+ curve->points = NULL;
+ TRC (("create new livewire segment\n"));
+ if ( iscissors->livewire )
+ {
+ if (iscissors->livewire->points)
+ {
+ TRC (("g_ptr_array_free (iscissors->livewire->points);\n"));
+ g_ptr_array_free (iscissors->livewire->points, TRUE);
+ }
+ TRC (("g_free (iscissors->livewire);\n"));
+ g_free (iscissors->livewire);
+
+ iscissors->livewire = NULL;
+ }
+
+ iscissors->livewire = curve;
+ TRC (("calculate curve\n"));
+ calculate_curve (tool, curve);
+ curve = NULL;
+ }
+
+ /* plot the curve */
+ iscissors_draw_curve (gdisp, iscissors, iscissors->livewire );
+#if 0
gdk_draw_line (iscissors->core->win, iscissors->core->gc,
tx1, ty1, tx2, ty2);
+#endif
}
if ((iscissors->draw & DRAW_CURVE) && !iscissors->first_point)
@@ -1127,9 +1204,6 @@
channel_delete (iscissors->mask);
iscissors->mask = NULL;
- /* free the gradient map */
- if (iscissors->gradient_map)
- {
/* release any tile we were using */
if (cur_tile)
{
@@ -1138,13 +1212,53 @@
}
cur_tile = NULL;
+ /* free the gradient map */
+ if (iscissors->gradient_map)
+ {
+
TRC (("tile_manager_destroy (iscissors->gradient_map);\n"));
tile_manager_destroy (iscissors->gradient_map);
iscissors->gradient_map = NULL;
}
+ /* free the cost map */
+ if( iscissors->cost_map )
+ {
+ TRC (("tile_manager_destroy (iscissors->cost_map);\n"));
+ tile_manager_destroy (iscissors->cost_map);
+ iscissors->cost_map = NULL;
+ }
+
+ if ( iscissors->livewire )
+ {
+ if (iscissors->livewire->points)
+ {
+ TRC (("g_ptr_array_free (iscissors->livewire->points);\n"));
+ g_ptr_array_free (iscissors->livewire->points, TRUE);
+ }
+ TRC (("g_free (iscissors->livewire);\n"));
+ g_free (iscissors->livewire);
+
+ iscissors->livewire = NULL;
+ }
+
+ if ( iscissors->livewire )
+ {
+ if (iscissors->livewire->points)
+ {
+ TRC (("g_ptr_array_free (iscissors->livewire->points);\n"));
+ g_ptr_array_free (iscissors->livewire->points, TRUE);
+ }
+ TRC (("g_free (iscissors->livewire);\n"));
+ g_free (iscissors->livewire);
+
+ iscissors->livewire = NULL;
+ }
+
iscissors->curve1 = NULL;
iscissors->curve2 = NULL;
+
+
iscissors->first_point = TRUE;
iscissors->connected = FALSE;
iscissors->state = NO_ACTION;
@@ -1518,9 +1632,12 @@
gradient_map_value (TileManager *map,
gint x,
gint y,
- guint8 *grad,
- guint8 *dir)
+ guint8 *cost,
+ guint8 *dir,
+ guint8 *lap
+ )
{
+
static int cur_tilex;
static int cur_tiley;
guint8 *p;
@@ -1539,8 +1656,22 @@
}
p = tile_data_pointer (cur_tile, x % TILE_WIDTH, y % TILE_HEIGHT);
- *grad = p[0];
- *dir = p[1];
+
+/* For the old behavior, prior to this patch, use the following instead
+ of POS_COST. The main difference is that POS_COST is somoothed before
+ the edge detection algorithm, and POS_GRADIENT is not. Mostly. There
+ is also a little math difference in the rounding and subtractions.
+*/
+
+/* *cost = p[ POS_GRADIENT ]; */
+
+ *cost = p[ POS_COST ];
+ *dir = p[ POS_DIR ];
+#ifdef USE_LAPLACIAN
+ *lap = p[ POS_LAPLACE ];
+#else
+ *lap = 0;
+#endif
return TRUE;
}
@@ -1553,9 +1684,9 @@
gint link)
{
gint value = 0;
- guint8 grad1, dir1, grad2, dir2;
+ guint8 grad1, dir1, lap1, grad2, dir2, lap2;
- if (!gradient_map_value (gradient_map, x, y, &grad1, &dir1))
+ if (!gradient_map_value (gradient_map, x, y, &grad1, &dir1, &lap1))
{
grad1 = 0;
dir1 = 255;
@@ -1565,16 +1696,19 @@
* so have low cost. */
grad1 = 255 - grad1;
+
+
/* calculate the contribution of the gradient magnitude */
if (link > 1)
value += diagonal_weight [grad1] * OMEGA_G;
else
value += grad1 * OMEGA_G;
+
/* calculate the contribution of the gradient direction */
x += (gint8)(pixel & 0xff);
y += (gint8)((pixel & 0xff00) >> 8);
- if (!gradient_map_value (gradient_map, x, y, &grad2, &dir2))
+ if (!gradient_map_value (gradient_map, x, y, &grad2, &dir2, &lap2))
{
grad2 = 0;
dir2 = 255;
@@ -1582,6 +1716,9 @@
value += (direction_value [dir1][link] + direction_value [dir2][link]) *
OMEGA_D;
+
+ /* calculate the contribution of the laplacian */
+
return value;
}
@@ -1637,6 +1774,7 @@
((gint8)(((pixel) & 0xff00) >> 8)) * dp_buf->width)
+
static void
find_optimal_path (TileManager *gradient_map,
TempBuf *dp_buf,
@@ -1782,22 +1920,41 @@
}
+/*
+// find_max_gradient.
+//
+// This method searches the local area around the (x,y)
+// Point to find the point with the maximum gradient.
+//
+*/
+
/* Called to fill in a newly referenced tile in the gradient map */
static void
gradmap_tile_validate (TileManager *tm,
Tile *tile)
{
- static gboolean first_gradient = TRUE;
gint x, y;
gint dw, dh;
gint sw, sh;
gint i, j;
gint b;
- gfloat gradient;
- guint8 *gradmap;
+
guint8 *tiledata;
- guint8 *datah, *datav;
- gint8 hmax, vmax;
+
+#ifdef USE_LAPLACIAN
+ guint8 *laplv;
+ guint8 lmax;
+#endif
+ guint8 chmax, cvmax;
+ guint8 ghmax, gvmax;
+
+ gfloat gradient, cost;
+
+ guint8 *gradmap;
+ guint8 *gradh, *gradv;
+
+ guint8 *costh, *costv;
+
Tile *srctile;
PixelRegion srcPR, destPR;
GImage *gimage;
@@ -1843,8 +2000,26 @@
/* XXX tile edges? */
- /* Blur the source to get rid of noise */
+
+ /* First, calculate the cost map. The cost map is DIFFERENT from the gradient map. */
+ /* Get the horizontal derivative */
+ /* This requires doing the convolve operations twice-- once with a blurred input, and once without. */
+
destPR.rowstride = TILE_WIDTH * 4;
+ destPR.data = costgrad_conv0;
+ convolve_region (&srcPR, &destPR, horz_deriv, 3, 1, NEGATIVE_CONVOL);
+
+ /* Get the vertical derivative */
+ destPR.data = costgrad_conv1;
+ convolve_region (&srcPR, &destPR, vert_deriv, 3, 1, NEGATIVE_CONVOL);
+
+#ifdef USE_LAPLACIAN
+ /* Get the laplacian */
+ destPR.data = costgrad_conv2;
+ convolve_region (&srcPR, &destPR, laplacian, 3, 1, NEGATIVE_CONVOL);
+#endif
+
+ /* Blur the source to get rid of noise */
destPR.data = maxgrad_conv0;
convolve_region (&srcPR, &destPR, blur_32, 3, 32, NORMAL_CONVOL);
@@ -1862,61 +2037,87 @@
/* calculate overall gradient */
tiledata = tile_data_pointer (tile, 0, 0);
+
+ /* fill in the cost map */
+
for (i = 0; i < srcPR.h; i++)
{
- datah = maxgrad_conv1 + srcPR.rowstride*i;
- datav = maxgrad_conv2 + srcPR.rowstride*i;
- gradmap = tiledata + tile_ewidth (tile) * COST_WIDTH * i;
+ gradh = maxgrad_conv1 + (srcPR.rowstride * i);
+ gradv = maxgrad_conv2 + (srcPR.rowstride * i);
+ costh = costgrad_conv0 + (srcPR.rowstride * i);
+ costv = costgrad_conv1 + (srcPR.rowstride * i);
+
+#ifdef USE_LAPLACIAN
+ laplv = costgrad_conv2 + (srcPR.rowstride * i);
+#endif
+
+ // The gradient is always the first one.
+ gradmap = tiledata + ( tile_ewidth ( tile ) * i * TOTAL_COST_WIDTH );
+ /* find the maximums */
for (j = 0; j < srcPR.w; j++)
{
- hmax = datah[0] - 128;
- vmax = datav[0] - 128;
+ chmax = costh[0] - 128;
+ cvmax = costv[0] - 128;
+#ifdef USE_LAPLACIAN
+ lmax = laplv[0] - 128;
+#endif
+ ghmax = gradh[0];
+ gvmax = gradv[0];
+
for (b = 1; b < srcPR.bytes; b++)
{
- if (abs (datah[b] - 128) > abs (hmax)) hmax = datah[b] - 128;
- if (abs (datav[b] - 128) > abs (vmax)) vmax = datav[b] - 128;
+#ifdef USE_LAPLACIAN
+ if (abs (laplv[b] - 128) > abs (lmax)) lmax = laplv[b] - 128;
+#endif
+ if (abs (costh[b] - 128) > abs (chmax)) chmax = costh[b] - 128;
+ if (abs (costv[b] - 128) > abs (cvmax)) cvmax = costv[b] - 128;
+ if (gradh[b] > ghmax) ghmax = gradh[b];
+ if (gradv[b] > gvmax) gvmax = gradv[b];
}
+ gradient = sqrt (ghmax * ghmax + gvmax * gvmax);
+ cost = sqrt (chmax * chmax + cvmax * cvmax );
+
+ gradmap[ POS_COST ] = (guint8 ) CLAMP( (gint) cost, 0, 255 );
+ gradmap[ POS_GRADIENT ] = gradient * 255 / MAX_GRADIENT;
+ gradmap[ POS_DIR ] = 255;
+#ifdef USE_LAPLACIAN
+ gradmap[ POS_LAPLACE ] = lmax;
+#endif
+ /* 1 byte absolute magitude first */
+
if (i == 0 || j == 0 || i == srcPR.h-1 || j == srcPR.w-1)
{
- gradmap[j*COST_WIDTH] = 0;
- gradmap[j*COST_WIDTH + 1] = 255;
+ gradmap[ POS_GRADIENT ] = 0;
+ /* Do I need to set POS_COST to 0 here as well? */
goto contin;
}
- /* 1 byte absolute magitude first */
- gradient = sqrt(SQR(hmax) + SQR(vmax));
- gradmap[j*COST_WIDTH] = gradient * 255 / MAX_GRADIENT;
-
/* then 1 byte direction */
- if (gradient > MIN_GRADIENT)
+ if (cost > MIN_GRADIENT)
{
gfloat direction;
- if (!hmax)
- direction = (vmax > 0) ? G_PI_2 : -G_PI_2;
+ if (!chmax)
+ direction = (cvmax > 0) ? G_PI_2 : -G_PI_2;
else
- direction = atan ((double) vmax / (double) hmax);
+ direction = atan ((double) cvmax / (double) chmax);
/* Scale the direction from between 0 and 254,
* corresponding to -PI/2, PI/2 255 is reserved for
* directionless pixels */
- gradmap[j*COST_WIDTH + 1] =
- (guint8) (254 * (direction + G_PI_2) / G_PI);
+ gradmap[ POS_DIR ] = (guint8) (254 * (direction + G_PI_2) / G_PI);
}
- else
- gradmap[j*COST_WIDTH + 1] = 255; /* reserved for weak gradient */
+contin:
- contin:
- {
-#ifdef DEBUG
- int g = gradmap[j*COST_WIDTH];
- int d = gradmap[j*COST_WIDTH + 1];
- TRC (("%c%c", 'a' + (g * 25 / 255), '0' + (d / 25)));
-#endif /* DEBUG */
- }
+ costh += srcPR.bytes;
+ costv += srcPR.bytes;
+#ifdef USE_LAPLACIAN
+ laplv += srcPR.bytes;
+#endif
+ gradh += srcPR.bytes;
+ gradv += srcPR.bytes;
- datah += srcPR.bytes;
- datav += srcPR.bytes;
+ gradmap += TOTAL_COST_WIDTH;
}
TRC (("\n"));
}
@@ -1925,19 +2126,21 @@
tile_release (srctile, FALSE);
}
+
static TileManager *
gradient_map_new (GImage *gimage)
{
TileManager *tm;
tm = tile_manager_new (gimage->width, gimage->height,
- sizeof (guint8) * COST_WIDTH);
+ sizeof (guint8) * TOTAL_COST_WIDTH );
tile_manager_set_user_data (tm, gimage);
tile_manager_set_validate_proc (tm, gradmap_tile_validate);
return tm;
}
+
static void
find_max_gradient (Iscissors *iscissors,
GImage *gimage,
@@ -1945,7 +2148,6 @@
gint *y)
{
PixelRegion srcPR;
- gint radius;
gint i, j;
gint endx, endy;
gint sx, sy, cx, cy;
@@ -1961,17 +2163,16 @@
if (!iscissors->gradient_map)
iscissors->gradient_map = gradient_map_new (gimage);
- radius = GRADIENT_SEARCH >> 1;
-
/* calculate the extent of the search */
cx = CLAMP (*x, 0, gimage->width);
cy = CLAMP (*y, 0, gimage->height);
- sx = cx - radius;
- sy = cy - radius;
- x1 = CLAMP (cx - radius, 0, gimage->width);
- y1 = CLAMP (cy - radius, 0, gimage->height);
- x2 = CLAMP (cx + radius, 0, gimage->width);
- y2 = CLAMP (cy + radius, 0, gimage->height);
+ sx = cx - GRADIENT_RADIUS;
+ sy = cy - GRADIENT_RADIUS;
+
+ x1 = CLAMP (cx - GRADIENT_RADIUS, 0, gimage->width);
+ y1 = CLAMP (cy - GRADIENT_RADIUS, 0, gimage->height);
+ x2 = CLAMP (cx + GRADIENT_RADIUS, 0, gimage->width);
+ y2 = CLAMP (cy + GRADIENT_RADIUS, 0, gimage->height);
/* calculate the factor to multiply the distance from the cursor by */
max_gradient = 0;
@@ -1994,8 +2195,8 @@
gradient = srcPR.data + srcPR.rowstride * (i - srcPR.y);
for (j = srcPR.x; j < endx; j++)
{
- g = *gradient;
- gradient += COST_WIDTH;
+ g = gradient[ POS_GRADIENT ] ;
+ gradient += TOTAL_COST_WIDTH;
g *= distance_weights [(i-y1) * GRADIENT_SEARCH + (j-x1)];
if (g > max_gradient)
{
@@ -2011,3 +2212,4 @@
}
/* End of iscissors.c */
+
