[Gimp-developer] iscissors tool

[Martin Waitz]

hi :)

some time ago i said i would like to work on the iscissors tool.
well, i started rewriting it, as i didn't really liked the
current code.
my implementation is far from being ready, but i don't have
that much time to work on it for the next weeks, and
i don't want my code to just rod on my discs.

i haven't really had the time to learn all of the gimp stuff
i would need to build a good tool, so my code is not really
integrated into the gimp, i just added enough function calls
to be able to do quick tests.
my code is not useable in its current form!
but i think it's a good basis for a future iscissors tool

well, have a look at it...

my implementation goes to gimpiscissorstool-livewire.[ch],
i changed gimpiscissorstool.[ch] just enough to disable the
old code and to enable some features using my code

-- 
CU,               / Friedrich-Alexander University Erlangen, Germany
Martin Waitz    //  [Tali on IRCnet]  [tali.home.pages.de] _________
______________/// - - - - - - - - - - - - - - - - - - - - ///
dies ist eine manuell generierte mail, sie beinhaltet    //
tippfehler und ist auch ohne grossbuchstaben gueltig.   /
                            -
Wer bereit ist, grundlegende Freiheiten aufzugeben, um sich 
kurzfristige Sicherheit zu verschaffen, der hat weder Freiheit 
noch Sicherheit verdient.
                        Benjamin Franklin  (1706 - 1790)

/* The GIMP -- an 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 2 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, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*
 * This code was written by Martin Waitz <[EMAIL PROTECTED]>,
 * based on a paper by Mortensen and Barrett:
 * http://www.cs.orst.edu/~enm/publications/GMIP_98/seg_scissors.html
 * it really needs some work, especially integration into the GIMP.
 */




#include "config.h"

#include <string.h>
#include <unistd.h>

#include <gtk/gtk.h>
#include <gdk/gdkkeysyms.h>

#include "tools-types.h"

#include "core/gimpimage.h"
#include "core/gimpimage-projection.h"

#include "base/tile.h"
#include "base/tile-manager.h"

#include "gimpiscissorstool-livewire.h"

/***************************************************************************/

/* XXX static const gint MAX_COST = (255);*/
#define MAX_COST (255)


/***************************************************************************/

/* DEBUG stuff */
/*#define DEBUG*/

#ifdef DEBUG

struct my_debug_header {
	guint32 magic;
	guint32 size;
	gchar* filename;
	gchar* function;
	guint32 linenum;
	guint8 data[0];
};
#define MY_DEBUG_MAGIC_HEAD (0xdeadbeaf)
#define MY_DEBUG_MAGIC_TAIL (0xfacefeed)

static gpointer
my_malloc0(gulong n_bytes, gchar* filename, gchar* function, guint linenum)
{
	struct my_debug_header *p;

	g_assert( n_bytes > 0 );
	p = (struct my_debug_header*) g_malloc0( n_bytes + sizeof(struct my_debug_header)+4 );

	/* insert info before data */
	p->magic = MY_DEBUG_MAGIC_HEAD;
	p->size = n_bytes;
	p->filename = filename;
	p->function = function;
	p->linenum = linenum;
	/* insert info after data */
	* (guint32*) (p->data+n_bytes) = MY_DEBUG_MAGIC_TAIL;

	/*g_printerr( "my_malloc: %p (%d)\n", p->data, n_bytes );*/

	return p->data;
}

static void
my_check_pointer(gpointer mem)
{
	struct my_debug_header *p;

	g_assert( mem );

	p = (struct my_debug_header*) ( ((guint8*) mem) - sizeof(struct my_debug_header) );
	g_assert( (gpointer) p > (gpointer) 0x8000000);
	/* g_assert( (gpointer) p < sbrk(0) ); */
	g_assert( p->data == mem );
	g_assert( p->magic == MY_DEBUG_MAGIC_HEAD );
	g_assert( p->size > 0 );
	g_assert( p->filename );
	g_assert( p->function );
	g_assert( p->linenum>0 );
	g_assert( * (guint32*) (p->data+p->size) == MY_DEBUG_MAGIC_TAIL );
}

static void
my_free(gpointer mem)
{
	struct my_debug_header *p;

	if( mem==NULL ) return;

	/*g_printerr( "my_free: %p\n", mem );*/
	my_check_pointer( mem );

	p = (struct my_debug_header*) ( ((guint8*) mem) - sizeof(struct my_debug_header) );
	memset( p, 0, p->size + sizeof(struct my_debug_header)+4 );
	g_free( p );
}

#undef g_new
#undef g_new0
#undef g_renew
#define g_new(struct_type, n_structs)		\
    ((struct_type *) my_malloc0 (((gsize) sizeof (struct_type)) * ((gsize) (n_structs)), \
     __FILE__, __PRETTY_FUNCTION__, __LINE__))
#define g_new0(struct_type, n_structs)		\
    ((struct_type *) my_malloc0 (((gsize) sizeof (struct_type)) * ((gsize) (n_structs)), \
     __FILE__, __PRETTY_FUNCTION__, __LINE__))
#define g_renew(struct_type, mem, n_structs)	\
    ((struct_type *) my_realloc ((mem), ((gsize) sizeof (struct_type)) * ((gsize) (n_structs)), \
     __FILE__, __PRETTY_FUNCTION__, __LINE__))
#define g_free(p) my_free(p)

#define check_pointer(p) my_check_pointer(p)

#else

#define check_pointer g_assert

#endif


/***************************************************************************/
/* Curve */

/* curve from free point to seedpoint */
/* okay, that seems like the wrong direction, but it's easier that way */

/* the curve is stored as an array of directions between the pixels.
 * there are two types of curves: with and without aging information:
 * curves are built without aging information.
 * aging information is the information about the similarity of several
 * curves. it is generated by curve_replace, which merges the aging
 * info from one curve with the shape of a new curve */


/* store the aging information for one link of the live wire */
struct _AgeEntry {
	gint paths;
	GTimeVal time;
};


/* construct a new curve */
Curve *
curve_new()
{
	Curve *curve;
	curve = g_new0(Curve, 1);
	curve->curve = g_byte_array_new();

	return( curve );
}

/* destruct a curve */
void
curve_free(Curve *curve)
{
	g_assert( curve );

	g_byte_array_free( curve->curve, TRUE );
	if( curve_has_age(curve) ) {
		g_array_free( curve->age, TRUE );
	}
	g_free( curve );
}

/* modify a coordianate according to a given direction */
inline void
curve_proceed(guint8 dir, gint *x, gint *y)
{
	static const gint move_x[] = { +1, +1,  0, -1, -1, -1,  0, +1 };
	static const gint move_y[] = {  0, +1, +1, +1,  0, -1, -1, -1 };

	g_assert( dir < sizeof(move_x)/sizeof(move_x[0]) );

	*x += move_x[dir];
	*y += move_y[dir];
}

/* return the reverse of the given direction */
inline guint8
curve_reverse(guint8 dir)
{
	return (dir+4) % 8;
}

/* set the free point of an new curve */
/* only works on a freshly created curve */
void
curve_set_free(Curve *curve, gint x, gint y)
{
	check_pointer( curve );
	g_assert( curve->curve->len == 0 );

	curve->free_x = curve->seed_x = x;
	curve->free_y = curve->seed_y = y;

	curve->bounds_x1 = curve->bounds_x2 = x;
	curve->bounds_y1 = curve->bounds_y2 = y;
}

/* add point to curve (moving seedpoint) */
void
curve_move_seed(Curve *curve, guint8 dir)
{
	check_pointer( curve );
	g_assert( !curve_has_age(curve) );

	/* add coord */
	g_byte_array_append( curve->curve, &dir, 1 );
	curve_proceed( dir, &curve->seed_x, &curve->seed_y );
	/* update bounding box */
	if( curve->seed_x<curve->bounds_x1 ) curve->bounds_x1 = curve->seed_x;
	if( curve->seed_x>curve->bounds_x2 ) curve->bounds_x2 = curve->seed_x;
	if( curve->seed_y<curve->bounds_y1 ) curve->bounds_y1 = curve->seed_y;
	if( curve->seed_y>curve->bounds_y2 ) curve->bounds_y2 = curve->seed_y;
}


/* traverse the curve */
/* last point traversed is the one just before the seed point */
/* stops if the callback returns FALSE */
void
curve_traverse(Curve *curve, CurveTraversalCallback callback, gpointer data)
{
	CurveLink link;
	gint i;

	check_pointer( curve );
	g_assert( callback );

	link.x = curve->free_x;
	link.y = curve->free_y;
	for(i=0; i<curve->curve->len; i++) {
		link.dir = curve->curve->data[i];
		if( !callback( curve, &link, data ) ) break;
		curve_proceed( link.dir, &link.x, &link.y );
	}
}


/* is aging information available for this path? */
gboolean
curve_has_age(Curve *curve)
{
	return curve->age!=NULL;
}

/* add aging information for this path */
/* only for empty path */
void
curve_add_age(Curve *curve)
{
	check_pointer( curve );
	g_assert( curve->curve->len == 0 );
	g_assert( curve->age==NULL );

	curve->age = g_array_new( FALSE, FALSE, sizeof(AgeEntry) );
}

/* free aging information of this curve */
void
curve_drop_age(Curve *curve)
{
	check_pointer( curve );

	if( curve_has_age( curve ) ) {
		g_array_free( curve->age, TRUE );
		curve->age = NULL;
	}
}

/* update the counters in the target curve, freeing source */
/* something like { target.copyFrom(source); free(source); } */
/* points that haven't moved between both curves are aged */
void
curve_replace(Curve *target, Curve *source)
{
	check_pointer( source );
	check_pointer( target );

	if( curve_has_age( target ) ) {
		guint8 *s, *t;
		gint slen, tlen;
		gint overlap, i;
		GTimeVal current_time;

		/* although curve is saved from free to seedpoint, it actually
		 * is rooted at the seedpoint, start there for comparision
		 */
		slen = source->curve->len;
		tlen = target->curve->len;
		if( target->seed_x==source->seed_x && target->seed_y==source->seed_y ) {
			s = &source->curve->data[slen-1];
			t = &target->curve->data[tlen-1];
			for( overlap=0; overlap<MIN(slen,tlen) && *s==*t; overlap++, s--, t-- ) {
				/* increase number of paths for that point */
				g_array_index(target->age, AgeEntry, tlen-overlap-1).paths++;
			}
			/* now we have:
			 *  o=free points      | overlapping part->age it |  x=seed points
			 * source:  o----------\ (length overlap, from (slen-overlap) to (slen-1)
			 *			==========================x
			 *			==========================x
			 * target:      o------/ (length overlap, from (tlen-overlap) to (tlen-1)
			 */
			/* move that part of the ageing info to the new position in the curve */
			if( slen > tlen ) {
				target->age = g_array_set_size(target->age, slen);
				memmove( &g_array_index(target->age, AgeEntry, (slen-overlap)),
					 &g_array_index(target->age, AgeEntry, (tlen-overlap)),
					 overlap * sizeof(AgeEntry) );
			} else if( slen < tlen ) {
				memmove( &g_array_index(target->age, AgeEntry, (slen-overlap)),
					 &g_array_index(target->age, AgeEntry, (tlen-overlap)),
					 overlap * sizeof(AgeEntry) );
				target->age = g_array_set_size(target->age, slen);
			}
		} else {
			overlap = 0;
			target->age = g_array_set_size(target->age, slen);
		}
		g_get_current_time( &current_time );
		for( i=0; i<slen-overlap; i++ ) {
			g_array_index( target->age, AgeEntry, i ).paths = 0;
			g_array_index( target->age, AgeEntry, i ).time = current_time;
		}
	}
	/* move over curve */
	target->seed_x = source->seed_x;
	target->seed_y = source->seed_y;
	target->free_x = source->free_x;
	target->free_y = source->free_y;
	g_byte_array_free( target->curve, TRUE );
	target->curve = source->curve;
	target->bounds_x1 = source->bounds_x1;
	target->bounds_x2 = source->bounds_x2;
	target->bounds_y1 = source->bounds_y1;
	target->bounds_y2 = source->bounds_y2;
	curve_drop_age( source );
	g_free( source );
}

/* check aging information */
/* if age is reached, curve gets truncated and TRUE is returned */
gboolean
curve_check_age(Curve *curve, GradientInput *gi)
{
	AgeEntry *age;
	GTimeVal current_time;
	gint x, y;
	guint8 dir;
	gint i;
	glong msec;
	gint path_max, path_thresh;

	check_pointer( curve );

	if( !curve->age ) return FALSE;
	g_assert( curve->curve->len == curve->age->len );

	if( curve->age->len<20 ) return FALSE;

	g_get_current_time( &current_time );

	x = curve->free_x;
	y = curve->free_y;
	path_max = g_array_index( curve->age, AgeEntry, curve->age->len-1 ).paths;
	if( path_max < 10 ) return FALSE; /* is there a bug with path_max? */
	path_thresh = path_max / 5 + 10;
	/* only check the first half of the wire */
	for(i=0; i<curve_length(curve)/2; i++) {
		age = &g_array_index( curve->age, AgeEntry, i);
		msec = (current_time.tv_sec - age->time.tv_sec) * 1000 +
			(current_time.tv_usec - age->time.tv_usec) / 1000;
		g_assert( age->paths <= path_max );
		g_assert( msec < 1000000 );
		/*g_printerr( "curve_check_age: age=%p msec=%d paths=%d\n", age, msec, age->paths );*/
		/* check for age */
		if( (msec > 500+4*gradientinput_get_magnitude(gi, x, y)) &&
				(age->paths > path_thresh) ) {
			g_printerr( "curve_check_age: [aged] i=%d/%d msec=%ld paths=%d/%d\n",
					i, curve_length(curve), msec, age->paths, path_thresh );
			curve_truncate_at_free( curve, i, x, y );
			return TRUE;
		}

		/* get next coords */
		dir = curve->curve->data[i];
		curve_proceed( dir, &x, &y );
	}

	return FALSE;
}

/* truncate curve to only contain the part between the free point and the truncation point */
/* -> remove seed point */
void
curve_truncate_at_seed(Curve *curve, gint index, gint x, gint y)
{
	gint newlen;

	check_pointer( curve );
	g_assert( index>0 );

	newlen = curve->curve->len - index;
	g_assert( newlen>0 );
	g_byte_array_set_size( curve->curve, newlen );
	if( curve_has_age(curve) ) {
		g_array_set_size( curve->age, newlen );
	}
	curve->seed_x = x;
	curve->seed_y = y;
	/* TODO: fix bounding box? */
}

/* truncate curve to only contain the part between the seed point and the truncation point */
/* -> remove free point */
void
curve_truncate_at_free(Curve *curve, gint index, gint x, gint y)
{
	gint newlen;

	check_pointer( curve );
	g_assert( index>=0 );

	if( index==0 ) return;

	newlen = curve->curve->len - index;
	g_assert( newlen>0 );
	memmove( curve->curve->data, curve->curve->data+index, newlen );
	g_byte_array_set_size( curve->curve, newlen );
	if( curve_has_age(curve) ) {
		memmove( &g_array_index(curve->age, AgeEntry, 0),
			 &g_array_index(curve->age, AgeEntry, index),
			 newlen * sizeof(AgeEntry) );
		g_array_set_size( curve->age, newlen );
	}
	curve->free_x = x;
	curve->free_y = y;
	/* TODO: fix bounding box? */
}

/* not needed, remove? */
gboolean curve_contains_callback(Curve *curve, CurveLink *link, gpointer data);
gboolean
curve_contains(Curve *curve, GimpIscissorsTool *iscissors, gdouble x, gdouble y, gint tolerance)
{
	struct CurveContainsParam {
		GimpIscissorsTool *iscissors;
		gdouble x, y;
		gint tolerance;
		gboolean result;
	} param;
	gint px, py, cx, cy;

	check_pointer( curve );
	g_assert( iscissors );

	/* check bonding box */
	gdisplay_transform_coords(GIMP_TOOL(iscissors)->gdisp,
			x, y, &px, &py, FALSE);
	gdisplay_transform_coords(GIMP_TOOL(iscissors)->gdisp,
			curve->bounds_x1, curve->bounds_y1, &cx, &cy, FALSE);
	if( px <= cx-tolerance ) return FALSE;
	if( py <= cy-tolerance ) return FALSE;
	gdisplay_transform_coords(GIMP_TOOL(iscissors)->gdisp,
			curve->bounds_x1, curve->bounds_y1, &cx, &cy, FALSE);
	if( px >= cx+tolerance ) return FALSE;
	if( py >= cy+tolerance ) return FALSE;

	/* check curve */
	param.iscissors = iscissors;
	param.x = x;
	param.y = y;
	param.tolerance = tolerance;
	param.result = FALSE;
	curve_traverse( curve, curve_contains_callback, &param );

	return param.result;
}
gboolean
curve_contains_callback(Curve *curve, CurveLink *link, gpointer data)
{
	struct CurveContainsParam {
		GimpIscissorsTool *iscissors;
		gdouble x, y;
		gint tolerance;
		gboolean result;
	} *param;
	param = (struct CurveContainsParam*) data;

	if( gimp_draw_tool_in_radius( GIMP_DRAW_TOOL(param->iscissors),
				      GIMP_TOOL(param->iscissors)->gdisp,
				      link->x, link->y, param->x, param->y, param->tolerance ) )
		param->result = TRUE;

	return !param->result;
}


/* if both curves have a point in common, both curves will be truncated at that point */
/* (c1-seed and c2-free is moved to intersection) */
/* returns TRUE if curves are modified */
struct CurveFindIntersectCallbackParam {
	Curve *c1;
	gint index1, index2;
	gint x, y;
	gboolean found;
};
gboolean curve_find_intersect_callback1(Curve *c1, CurveLink *, gpointer data);
gboolean curve_find_intersect_callback2(Curve *c2, CurveLink *, gpointer data);
gboolean
curve_find_intersect(Curve *c1, Curve *c2)
{
	struct CurveFindIntersectCallbackParam param;

	g_assert( c1 );
	g_assert( c2 );

	/* first check bounding boxes */
	if( c1->bounds_x1 > c2->bounds_x2 ||
	    c1->bounds_x2 < c2->bounds_x1 ||
	    c1->bounds_y1 > c2->bounds_y2 ||
	    c1->bounds_y2 < c2->bounds_y1 ) return FALSE;

	/* start searching with the free point of c2 */
	param.c1 = c1;
	param.index2 = -1;
	param.found = FALSE;
	curve_traverse( c2, curve_find_intersect_callback2, &param );
	if( !param.found ) return FALSE;

	/* FIXME: have a look at corner cases */
	curve_truncate_at_seed( c1, param.index1, param.x, param.y );
	curve_truncate_at_free( c2, param.index2, param.x, param.y );

	return TRUE;
}
gboolean
curve_find_intersect_callback2(Curve *c2, CurveLink *link, gpointer data)
{
	/* outer loop */
	struct CurveFindIntersectCallbackParam *param =
		(struct CurveFindIntersectCallbackParam *) data;

	param->index2++;
	param->index1 = -1;

	if( link->x < param->c1->bounds_x1 ||
	    link->y < param->c1->bounds_y1 ||
	    link->x > param->c1->bounds_x2 ||
	    link->y > param->c1->bounds_y2 ) return TRUE;
	/* this point of c2 is within c1's bounding box */
	param->x = link->x;
	param->y = link->y;
	curve_traverse( param->c1, curve_find_intersect_callback1, param );

	return !param->found;
}
gboolean
curve_find_intersect_callback1(Curve *c1, CurveLink *link, gpointer data)
{
	/* inner loop */
	struct CurveFindIntersectCallbackParam *param =
		(struct CurveFindIntersectCallbackParam *) data;

	param->index1++;

	if( link->x==param->x && link->y==param->y )
		param->found = TRUE;

	return !param->found;
}


/* draw one curve segment to the screen */
static gboolean curve_draw_callback( Curve *curve, CurveLink *, gpointer data );
inline void
curve_draw(Curve *curve, GimpDrawTool *draw_tool)
{
	curve_traverse( curve, curve_draw_callback, draw_tool );
}
static gboolean
curve_draw_callback( Curve *curve, CurveLink *link, gpointer data )
{
	gint x2, y2;
	GimpDrawTool *draw_tool = (GimpDrawTool*) data;

	g_assert( draw_tool );

	x2 = link->x; y2 = link->y;
	curve_proceed( link->dir, &x2, &y2 );
	gimp_draw_tool_draw_line( draw_tool, link->x, link->y, x2, y2, FALSE);

	return TRUE;
}

/* get a list of all the points on that curve */
gboolean curve_get_points_callback(Curve *curve, CurveLink *link, gpointer data);
void
curve_get_points(Curve *curve, gint *len, GimpVector2 **points)
{
	GimpVector2 *p;

	check_pointer( curve );

	*len = curve->curve->len;
	p = g_new( GimpVector2, *len );
	*points = p;

	curve_traverse( curve, curve_get_points_callback, &p );
	p->x = curve->seed_x;
	p->y = curve->seed_y;
}
gboolean
curve_get_points_callback(Curve *curve, CurveLink *link, gpointer data)
{
	GimpVector2 **param = (GimpVector2**) data;

	(*param)->x = link->x;
	(*param)->y = link->y;
	(*param)++;

	return TRUE;
}

/***************************************************************************/

/* build up a 2 dimensional array */
gpointer*
array2d_new(gint w, gint h, gsize el_size)
{
	int i;
	guint8 *pp;
	gpointer *p;

	/* alloc one big matrix holding all the data */
	pp = g_new( guint8, w * h * el_size );
	check_pointer( pp );

	/* build a pointer array pointing into that matrix */
	p = g_new( gpointer, h );
	check_pointer( p );
	for( i=0; i<h; i++ )
		p[i] = pp + i * w*el_size;

	return p;
}

/* free such an array */
void
array2d_free(gpointer *p)
{
	g_free( *p );
	g_free( p );
}


/***************************************************************************/

/* GradientInput: store all the information needed for gradient based
 * 		  cost function
 */

GradientInput *
gradientinput_new()
{
	GradientInput *gi;

	gi = g_new0( GradientInput, 1 );
	gi->width = gi->height = -1;

	return gi;
}

void
gradientinput_free( GradientInput *gi )
{
	if( gi->magnitude ) array2d_free( (gpointer*) gi->magnitude );
	if( gi->direction ) array2d_free( (gpointer*) gi->direction );

	g_free( gi );
}

typedef struct _TmpGradient TmpGradient;
struct _TmpGradient {
	GimpImage *image;
	GimpImageType type;
	gint **smooth_x, **smooth_y;
	gint **gradient_x, **gradient_y;
	gint width, height;
};

static /*inline*/ void /* performance critical */
_convolve_smooth_tile(TmpGradient *tg, Tile *tile, gint tile_x, gint tile_y)
{
	gint x, y;
	gint x0, y0;
	gint *smooth_x;
	gint *smooth_y1, *smooth_y2, *smooth_y3;
	guchar col[3];
	gpointer src;

	/* leave out one pixel at the border */
	x0 = tile_x? 0 : 1;
	y0 = tile_y? 0 : 1;

	for( y=y0; y<tile_eheight(tile)-1; y++ ) {
		smooth_x = &tg->smooth_x[tile_y+y][(tile_x+x0-1)*3];
		smooth_y1 = &tg->smooth_y[tile_y+y-1][(tile_x+x0)*3];
		smooth_y2 = &tg->smooth_y[tile_y+y+0][(tile_x+x0)*3];
		smooth_y3 = &tg->smooth_y[tile_y+y+1][(tile_x+x0)*3];
		for( x=x0; x<tile_ewidth(tile)-1; x++ ) {
			/* push one pixel into the convolved image */
			src = tile_data_pointer( tile, x, y );
			gimp_image_get_color( tg->image, tg->type, col, src );
			/* smooth convolution filter: {+1, +2, +1} */
			*smooth_x++ += col[0]; /* (tile_x+x-1, tile_y+y) */
			*smooth_x++ += col[1];
			*smooth_x++ += col[2];
			*smooth_x++ += col[0]<<1; /* (tile_x+x, tile_y+y) */
			*smooth_x++ += col[1]<<1;
			*smooth_x++ += col[2]<<1;
			*smooth_x++ += col[0]; /* (tile_x+x+1, tile_y+y) */
			*smooth_x++ += col[1];
			*smooth_x++ += col[2];
			smooth_x -= 6; /* go to the pixel to the left of the next one */
			*smooth_y1++ += col[0]; /* (tile_x+x, tile_y+y-1) */
			*smooth_y1++ += col[1];
			*smooth_y1++ += col[2];
			*smooth_y2++ += col[0]<<1; /* (tile_x+x, tile_y+y) */
			*smooth_y2++ += col[1]<<1;
			*smooth_y2++ += col[2]<<1;
			*smooth_y3++ += col[0]; /* (tile_x+x, tile_y+y+1) */
			*smooth_y3++ += col[1];
			*smooth_y3++ += col[2];
		}
	}
}

static /*inline*/ void /* performance critical */
_convolve_smooth_tile_fast(TmpGradient *tg, Tile *tile, gint tile_x, gint tile_y)
{
	gint x, y;
	gint *smooth_x;
	gint *smooth_y1, *smooth_y2, *smooth_y3;
	guchar col[3];
	gpointer src;

	for( y=0; y<TILE_HEIGHT; y++ ) {
		smooth_x = &tg->smooth_x[tile_y+y][(tile_x-1)*3];
		smooth_y1 = &tg->smooth_y[tile_y+y-1][tile_x*3];
		smooth_y2 = &tg->smooth_y[tile_y+y+0][tile_x*3];
		smooth_y3 = &tg->smooth_y[tile_y+y+1][tile_x*3];
		for( x=0; x<TILE_WIDTH; x++ ) {
			/* push one pixel into the convolved image */
			src = tile_data_pointer( tile, x, y );
			gimp_image_get_color( tg->image, tg->type, col, src );
			/* smooth convolution filter: {+1, +2, +1} */
			*smooth_x++ += col[0];
			*smooth_x++ += col[1];
			*smooth_x++ += col[2];
			*smooth_x++ += col[0]<<1;
			*smooth_x++ += col[1]<<1;
			*smooth_x++ += col[2]<<1;
			*smooth_x++ += col[0];
			*smooth_x++ += col[1];
			*smooth_x++ += col[2];
			smooth_x -= 6; /* go to the pixel to the left of the next one */
			*smooth_y1++ += col[0];
			*smooth_y1++ += col[1];
			*smooth_y1++ += col[2];
			*smooth_y2++ += col[0]<<1;
			*smooth_y2++ += col[1]<<1;
			*smooth_y2++ += col[2]<<1;
			*smooth_y3++ += col[0];
			*smooth_y3++ += col[1];
			*smooth_y3++ += col[2];
		}
	}

}

static /*inline*/ void /* performance critical */
_convolve_gradient(TmpGradient *tg)
{
	gint i;
	gint *gradient;
	gint *src_1, *src_2;

	/* calculate gradient in x-direction */
	gradient = &tg->gradient_x[1][1*3];
	src_1 = &tg->smooth_y[1][0*3];
	src_2 = &tg->smooth_y[1][2*3];
	for( i=(tg->height-2)*tg->width -2; i; i-- ) {
		/* gradient convolution filter: {+1, 0, -1} */
		*gradient++ = *src_1++ - *src_2++;
		*gradient++ = *src_1++ - *src_2++;
		*gradient++ = *src_1++ - *src_2++;
		/* (3 color channels) */
	}

	/* calculate gradient in y-direction */
	gradient = &tg->gradient_y[1][1*3];
	src_1 = &tg->smooth_x[0][1*3];
	src_2 = &tg->smooth_x[2][1*3];
	for( i=(tg->height-2)*tg->width -2; i; i-- ) {
		/* gradient convolution filter: {+1, 0, -1} */
		*gradient++ = *src_1++ - *src_2++;
		*gradient++ = *src_1++ - *src_2++;
		*gradient++ = *src_1++ - *src_2++;
		/* (3 color channels) */
	}

	/* the borders contain crap now */
}

/* fast integer square root */
#define integer_sqrt_iter(N) \
	try = root + (1 << (N)); \
	if (n >= try << (N)) { \
		n -= try << (N); \
		root |= 2 << (N); \
	}
guint32 /* performance critical */
integer_sqrt(guint32 n)
{
	guint32 root = 0, try;

	integer_sqrt_iter(15); integer_sqrt_iter(14); integer_sqrt_iter(13); integer_sqrt_iter(12);
	integer_sqrt_iter(11); integer_sqrt_iter(10); integer_sqrt_iter( 9); integer_sqrt_iter( 8);
	integer_sqrt_iter( 7); integer_sqrt_iter( 6); integer_sqrt_iter( 5); integer_sqrt_iter( 4);
	integer_sqrt_iter( 3); integer_sqrt_iter( 2); integer_sqrt_iter( 1); integer_sqrt_iter( 0);

	return root >> 1;
}



/* update all the gradients with data from the image */
void
gradientinput_set_image(GradientInput *gi, GimpImage *image)
{
	TmpGradient tg;
	Tile *tile;
	gint x, y;
	gint margin = 1; /* XXX */

	check_pointer( gi );
	g_assert( image );

	gi->image = image;

	if( gi->width!=gimp_image_get_width(image) || gi->height!=gimp_image_get_height(image) ) {
		/* realloc memory for cache */
		if( gi->magnitude ) array2d_free( (gpointer*) gi->magnitude );
		if( gi->direction ) array2d_free( (gpointer*) gi->direction );

		gi->width = gimp_image_get_width(image);
		gi->height = gimp_image_get_height(image);
		g_assert( gi->width >= 4 );
		g_assert( gi->height >= 4 );

		gi->magnitude = (gint**) array2d_new( gi->width, gi->height, sizeof(**gi->magnitude) );
		gi->direction = (gint**) array2d_new( gi->width, gi->height, sizeof(**gi->direction) );
	}

	/* temp. memory for storage of gradients */
	tg.image = gi->image;
	tg.type = gimp_image_projection_type(gi->image);
	tg.width = gi->width;
	tg.height = gi->height;
	tg.smooth_x = (gint**) array2d_new( tg.width, tg.height, sizeof(gint)*3 );
	tg.smooth_y = (gint**) array2d_new( tg.width, tg.height, sizeof(gint)*3 );
	tg.gradient_x = (gint**) array2d_new( tg.width, tg.height, sizeof(gint)*3 );
	tg.gradient_y = (gint**) array2d_new( tg.width, tg.height, sizeof(gint)*3 );

	/* calculate horizontal and vertical gradients */
	for( y=0; y<gi->height; y+=TILE_HEIGHT ) {
		for( x=0; x<gi->width; x+=TILE_WIDTH ) {
			/* walk all tiles and add to convolution */
			tile = tile_manager_get_tile(
					gimp_image_projection(image),
					x, y, TRUE, FALSE);
			if( x==0 || y==0 ||
					x+TILE_WIDTH+margin>=gi->width ||
					y+TILE_HEIGHT+margin>=gi->height ) {
				/* on the borders, we use the checking version */
				_convolve_smooth_tile(&tg, tile, x, y );
			} else {
				/* in the middle, we use the fast one */
				_convolve_smooth_tile_fast(&tg, tile, x, y );
			}
		}
	}

	_convolve_gradient(&tg);

	gi->max_magnitude = 0;
	/* get image data */
	for( y=1; y<gi->height-1; y++ ) 
		for( x=1; x<gi->width-1; x++ ) {
			gint mag, dir, c, g_x, g_y;

			mag = g_x = g_y = 0;
			/* search for the color channel with the strongest magnitude */
			for( c=0; c<3; c++ ) {
				gint g_cx, g_cy, cmag;
				g_cx = tg.gradient_x[y][3*x+c];
				g_cy = tg.gradient_y[y][3*x+c];
				/* calculate gradient magnitude */
				cmag = integer_sqrt( g_cx*g_cx + g_cy*g_cy );
				if( cmag > mag ) {
					g_x = g_cx;
					g_y = g_cy;
					mag = cmag;
				}
			}
			gi->magnitude[y][x] = mag;
			if( mag > gi->max_magnitude )
				gi->max_magnitude = mag;
			/* calculate gradient direction */
			/* FIXME: test it! integer version?! */
			dir = (MAX_COST/G_PI/2.0) * atan2( g_y, g_x );
			if( dir<0 ) dir+= MAX_COST;
			gi->direction[y][x] = dir;
		}
	g_printerr( "gradientinput_set_image: max_magnitude=%d\n", gi->max_magnitude );

	/* normalize gradient magnitude */
	for( y=0; y<gi->height; y++ ) 
		for( x=0; x<gi->width; x++ ) {
			gi->magnitude[y][x] = gi->magnitude[y][x] * MAX_COST / gi->max_magnitude;
		}

	array2d_free( (gpointer*) tg.smooth_x );
	array2d_free( (gpointer*) tg.smooth_y );
	array2d_free( (gpointer*) tg.gradient_x );
	array2d_free( (gpointer*) tg.gradient_y );
}

inline gint /* performance critical */
gradientinput_get_magnitude(GradientInput *gi, gint x, gint y)
{
	return( gi->magnitude[y][x] );
}

inline gint /* performance critical */
gradientinput_get_direction(GradientInput *gi, gint x, gint y)
{
	return( gi->direction[y][x] );
}



/***************************************************************************/

/* abstract class for cost functions (one component of the local link costs) */


void
costfunction_free(CostFunction *map)
{
	check_pointer( map );

	/* leave input, has to be deleted explicitly */
	g_free( map->data );
	g_free( map );
}

/* if cost function is dependent on the last selected curve, update it */
inline void
costfunction_new_livewire(CostFunction *map, Curve *last)
{
	if( map->new_livewire )
		map->new_livewire(map, last);
}

inline gint /* performance critical */
costfunction_get_cost(CostFunction *map, CurveLink *link)
{
	/* has to be always defined, no check (no branch->fast) */
	return( map->get_cost(map, link) );
}


/***************************************************************************/

gint gradientmag_get_cost(CostFunction *cost, CurveLink *link);
gint gradientdir_get_cost(CostFunction *cost, CurveLink *link);


/* GradientMag: derived from CostFunction */
/* strong gradients have low costs */

CostFunction *
gradientmag_new(GradientInput *gi)
{
	CostFunction *cost;

	cost = g_new0( CostFunction, 1 );
	cost->get_cost = gradientmag_get_cost;
	cost->input = gi;

	return cost;
}

gint /* performance critical */
gradientmag_get_cost(CostFunction *cost, CurveLink *link)
{
	GradientInput *gi = (GradientInput*) cost->input;

	return MAX_COST - gradientinput_get_magnitude( gi, link->x, link->y );
}

/* GradientDir: derived from CostFunction */
/* gradients orthogonal to link directions have low costs */
/* TODO: implement! */

CostFunction *
gradientdir_new(GradientInput *gi)
{
	CostFunction *cost;

	cost = g_new0( CostFunction, 1 );
	cost->get_cost = gradientdir_get_cost;
	cost->input = gi;

	return cost;
}


gint /* performance critical */
gradientdir_get_cost(CostFunction *cost, CurveLink *link)
{
	gint x1, y1, x2, y2;
	guint8 dir;
	guint8 alpha1, alpha2;
	GradientInput *gi = (GradientInput*) cost->input;

	dir = link->dir;
	x1 = x2 = link->x; y1 = y2 = link->y;
	curve_proceed( dir, &x2, &y2 );

	g_assert( x2>=0 && y2>=0 && x2<gi->width && y2<gi->height );

	dir += 2; dir %= 8;	/* orthogonal */
	dir *= 32;		/* scale to 0..255 */

	/* calculate angle between directions */
	if( gradientinput_get_magnitude( gi, x1, y1 ) < MAX_COST/8 )
		alpha1 = 63;
	else
		alpha1 = gradientinput_get_direction( gi, x1, y1 ) - dir;
	if( gradientinput_get_magnitude( gi, x2, y2 ) < MAX_COST/8 )
		alpha2 = 127;
	else
		alpha2 = gradientinput_get_direction( gi, x2, y2 ) - dir;

#ifdef SLOW
	if( alpha1<0 ) alpha1 += 256;
	if( alpha1 >= 128 ) alpha1 = 255-alpha1;
	if( alpha1 >= 64 ) {
		/* angle too big, flip dir */
		alpha1 -= 128;
		alpha2 -= 128;
	}

	if( alpha1<0 ) alpha1 += 256;
	while(alpha2<0) alpha2 += 256;
	if( alpha2 >= 128 ) alpha2 = 255-alpha2;

	/* maximum alpha1 is 63, max. alpha2 is 128 */
	return (alpha1 + alpha2) * 4 / 3;
#else /* same as above  */
	if( alpha1 & 128 ) alpha1 ^= 255;
	if( alpha1 & 192 ) {
		alpha1 ^= 128;
		alpha2 ^= 128;
	}
	if( alpha2 & 128 ) alpha2 ^= 255;

	return alpha1 + alpha2;
#endif
}

/***************************************************************************/

/* DynamicMap derived from CostFunction: */
/* gets trained to previous values, which get low costs */

/* one really needs to be able to disable this function on the fly,
 * as it has problems with various images
 */

gint dynamicmap_get_cost_none(CostFunction *map, CurveLink *link);
gint dynamicmap_get_cost(CostFunction *map, CurveLink *link);
void dynamicmap_new_livewire(CostFunction *map, Curve *last);
gint dynamicmap_build_histogram(CostFunction *map, Curve *curve);


CostFunction *
dynamicmap_new(CostFunction *input)
{
	CostFunction *cost;

	cost = g_new0( CostFunction, 1 );
	/* at first, don't return any costs unless we got trained */
	cost->get_cost = dynamicmap_get_cost_none;
	cost->new_livewire = dynamicmap_new_livewire;
	cost->input = input;

	return cost;
}

/* this function gets called whenever we don't have trained costs available */
gint /* performance critical */
dynamicmap_get_cost_none(CostFunction *cost, CurveLink *link)
{
	return costfunction_get_cost( (CostFunction*)cost->input, link );
}

/* calculate trained costs */
gint /* performance critical */
dynamicmap_get_cost(CostFunction *cost, CurveLink *link)
{
	guint *map;

	map = (guint*) cost->data;

	return map[ costfunction_get_cost( (CostFunction*)cost->input, link ) ];
}

/* train based on the last curve selected */
void
dynamicmap_new_livewire(CostFunction *cost, Curve *last)
{
	gint histmax, i;
	guint *map;

	check_pointer( cost );
	g_assert( cost->input );

	g_free( cost->data );
	cost->data = NULL;

	if( !last ) {
		/* reset training */
		cost->get_cost = dynamicmap_get_cost_none;
		return;
	}
	/* train the cost mapping */
	cost->data = map = g_new0( guint, MAX_COST+1 );
	histmax = dynamicmap_build_histogram(cost, last);
	/* normize and invert histogram */
	for( i=0; i<MAX_COST; i++ ) {
		map[i] = MAX_COST - MAX_COST*map[i]/histmax;
		g_printerr( "%d ", map[i] );
	}
	g_printerr( "\n" );

	/* activate trained costs */
	cost->get_cost = dynamicmap_get_cost;
}

/* build histogram of the function along the curve in map, return maximal count */
struct _DynamicMapBuildHistogramParam {
	CostFunction *cost;
	gint weight;
	gint max;
};
gboolean dynamicmap_build_histogram_callback(Curve *curve, CurveLink *link, gpointer data);
gint
dynamicmap_build_histogram(CostFunction *cost, Curve *curve)
{
	struct _DynamicMapBuildHistogramParam param;

	check_pointer( cost );
	check_pointer( curve );

	param.cost = cost;
	param.weight = 32; /* use the last 32 pixels */
	param.max = 0;

	curve_traverse( curve, dynamicmap_build_histogram_callback, &param );

	return param.max;
}
gboolean
dynamicmap_build_histogram_callback(Curve *curve, CurveLink *link, gpointer data)
{
	static const gint smooth[] = { 1, 2, 5, 7, 9, 10, 9, 7, 5, 2, 1 };
	static const gint smooth_size = (sizeof(smooth) / sizeof(smooth[0]));
	int value;
	struct _DynamicMapBuildHistogramParam *param = (struct _DynamicMapBuildHistogramParam*) data;
	guint *map;
	gint i, v;

	value = costfunction_get_cost( (CostFunction*) param->cost->input, link );
	g_assert( value>=0 && value<=MAX_COST );

	/* add the current weight to the histogram */
	map = (guint*) param->cost->data;
	for( v=value-smooth_size/2, i=0; v<=value+smooth_size/2; v++, i++ ) {
		if( v<0 || v>MAX_COST ) continue;
		map[v] += smooth[i] * param->weight;
		if( map[v]>param->max ) param->max=map[v];
	}

	/* adjust weight */
	param->weight--;

	return param->weight>0;
}


/***************************************************************************/


/* NULL is considered an empty list */
inline CostList *
costlist_new()
{
	return NULL;
}

void
costlist_free(CostList *costs)
{
	CostList *next;

	while( costs ) {
		next = costs->next;
		costfunction_free( costs->cost );
		g_free( costs );
		costs = next;
	}
}

/* add a new weighted cost component */
CostList *
costlist_add(CostList *costs, CostFunction *cf, gint weight)
{
	CostList *c;

	c = g_new(CostList, 1);
	c->cost = cf;
	c->weight = weight;
	c->next = costs;

	return c;
}


/* update all cost components with data from the last curve */
void
costlist_new_livewire(CostList *costs, Curve *last)
{
	while( costs ) {
		costfunction_new_livewire( costs->cost, last );
		costs = costs->next;
	}
}


/* diagonal links are sqrt(2) more expensive */
static const gint scale_diag[2] ={ 1414, 1000 };

/* get the overall weighted costs */
gint
costlist_get(CostList *costs, CurveLink *link)
{
	gint cost;
	gint sum, sum_weight;

	sum = sum_weight = 0;
	while( costs!=NULL ) {
		cost = costfunction_get_cost( costs->cost, link );
		if( cost>=0 ) {
			sum += cost * costs->weight;
			sum_weight += costs->weight;
		}
		costs = costs->next;
	}

	return sum * 1000 / scale_diag[link->dir%2] / sum_weight;
}

/***************************************************************************/

static const gint BUCKET_SORT_SIZE = (MAX_COST + 1);

/* a sorted list of coordinates
 * they are sorted according to their cumulative costs to the current seedpoint.
 * as elements with lowest costs are removed, and new elements have a cost difference
 * of less than MAX_COST, they can be sorted in O(1) via MAX_COST buckets,
 * each holding all coordinates with the exact same cost
 */

typedef struct _CoordStack CoordStack;
struct _CoordStack {
	gint x, y;
	CoordStack *next;
};
struct _BucketSort {
	GPtrArray *buckets;
	gint pos, size;
};



/* create new buckets for sorting */
BucketSort *
bucketsort_new()
{
	BucketSort *bsort = g_new( BucketSort, 1 );
	bsort->buckets = g_ptr_array_sized_new( BUCKET_SORT_SIZE );
	g_ptr_array_set_size( bsort->buckets, BUCKET_SORT_SIZE );
	bsort->pos = 0;
	bsort->size = 0;

	return bsort;
}

void
bucketsort_free(BucketSort *bsort)
{
	check_pointer( bsort );

	bucketsort_remove_all( bsort );
	g_ptr_array_free( bsort->buckets, TRUE );
	g_free( bsort );
}

/* flush the entire list */
void
bucketsort_remove_all(BucketSort *bsort)
{
	int i;
	CoordStack *stack, *next;

	check_pointer( bsort );
	g_assert( bsort->buckets );

	for( i=0; i<BUCKET_SORT_SIZE; i++ ) {
		stack = (CoordStack*) g_ptr_array_index( bsort->buckets, i );
		g_ptr_array_index( bsort->buckets, i ) = NULL;
		while( stack!=NULL ) {
			next = stack->next;
			g_free( stack );
			stack = next;
		}
	}
	bsort->pos = 0;
	bsort->size = 0;
}

/* test if there are elements in the list */
gboolean
bucketsort_is_empty(BucketSort *bsort)
{
	check_pointer( bsort );

	return( bsort->size==0 );
}

/* add a new element, value MUST NOT be greater than
 * the lowest value in the list plus MAX_COST
 */
void
bucketsort_push(BucketSort *bsort, gint x, gint y, gint value)
{
	CoordStack *coord;
	CoordStack **stack;

	check_pointer( bsort );

	stack = (CoordStack**) &g_ptr_array_index( bsort->buckets, value % BUCKET_SORT_SIZE );

	coord = g_new( CoordStack, 1 );
	coord->x = x;
	coord->y = y;
	coord->next = *stack;
	*stack = coord;

	bsort->size++;
}

/* get the coordinate with the lowest costs and removes it from list */
void
bucketsort_pop(BucketSort *bsort, gint *x, gint *y)
{
	CoordStack *coord;
	CoordStack **stack;

	check_pointer( bsort );
	g_assert( bsort->size > 0 );

	stack = (CoordStack**) &g_ptr_array_index( bsort->buckets, bsort->pos );
	while( *stack==NULL ) {
		bsort->pos = (bsort->pos+1) % BUCKET_SORT_SIZE;
		stack = (CoordStack**) &g_ptr_array_index( bsort->buckets, bsort->pos );
	}
	
	coord = *stack;
	*stack = coord->next;

	*x = coord->x;
	*y = coord->y;

	g_free( coord );
	bsort->size--;
}



/***************************************************************************/

/* PathSearch: calculate spanning tree and curves */


static gboolean pathsearch_dowork(gpointer data);
static void pathsearch_startwork(PathSearch *psearch);
static void pathsearch_stopwork(PathSearch *psearch);

/* allocate new PathSearch */
PathSearch*
pathsearch_new(CostList *costlist)
{
	PathSearch *psearch;

	psearch = g_new0( PathSearch, 1 );
	psearch->costs = costlist;

	return( psearch );
}

/* start with background work */
inline static void
pathsearch_startwork(PathSearch *psearch)
{
	check_pointer( psearch );
	check_pointer( psearch->tree_cum_cost );
	check_pointer( psearch->tree_dir );
	check_pointer( psearch->active );
	g_assert( !bucketsort_is_empty(psearch->active) );

	if( psearch->working ) return;
	psearch->work_tag = g_idle_add( pathsearch_dowork, psearch );
	psearch->working = TRUE;
}

/* stop background work */
inline static void
pathsearch_stopwork(PathSearch *psearch)
{
	check_pointer( psearch );

	if( !psearch->working ) return;
	psearch->working = FALSE;
	g_source_remove( psearch->work_tag );
}


void
pathsearch_free(PathSearch *psearch)
{
	g_assert( psearch );

	pathsearch_stop( psearch );
	costlist_free( psearch->costs );

	bucketsort_free( psearch->active );

	g_free( psearch );
}

/* stop with path generation and abandon all cached data */
void
pathsearch_stop(PathSearch *psearch)
{
	check_pointer( psearch );

	pathsearch_stopwork( psearch );

	if( psearch->tree_cum_cost ) array2d_free( (gpointer*) psearch->tree_cum_cost );
	if( psearch->tree_dir ) array2d_free( (gpointer*) psearch->tree_dir );
	if( psearch->active ) bucketsort_free( psearch->active );
	psearch->tree_cum_cost = NULL;
	psearch->tree_dir = NULL;
	psearch->active = NULL;
	costlist_new_livewire( psearch->costs, NULL );
}

/* use new image for path calculation */
/* must be called before trying to use the path generator */
void
pathsearch_set_image(PathSearch *psearch, GimpImage *image)
{
	check_pointer( psearch );

	pathsearch_stop( psearch );

	psearch->width = gimp_image_get_width(image);
	psearch->height = gimp_image_get_height(image);
}

/* set the seed point of all generated paths */
/* must be called before pathsearch_generate and after pathsearch_set_image */
void
pathsearch_set_seed(PathSearch *psearch, gint x, gint y, Curve *last)
{
	check_pointer( psearch );
	g_assert( x>=0 && x<psearch->width );
	g_assert( y>=0 && y<psearch->height );

	pathsearch_stopwork( psearch );

	psearch->seed_x = x;
	psearch->seed_y = y;

	costlist_new_livewire( psearch->costs, last );

	/* create new structures for the spanning tree */
	if( !psearch->tree_cum_cost ) psearch->tree_cum_cost =
		(gint**) array2d_new( psearch->width+1, psearch->height+1, sizeof(gint) );
	if( !psearch->tree_dir ) psearch->tree_dir =
		(guint8**) array2d_new( psearch->width+1, psearch->height+1, sizeof(guint8) );
	for( y=0; y<psearch->height; y++ )
		for( x=0; x<psearch->width; x++ ) {
			psearch->tree_cum_cost[y][x] = G_MAXINT;
			psearch->tree_dir[y][x] = DIR_NONE;
		}
	psearch->tree_cum_cost[psearch->seed_y][psearch->seed_x] = 0;

	/* mark new seed point as the only active one */
	if( psearch->active )
		bucketsort_remove_all( psearch->active );
	else
		psearch->active = bucketsort_new();
	bucketsort_push( psearch->active, psearch->seed_x, psearch->seed_y, 0 );

	pathsearch_startwork( psearch );
}

/* calculate a path to the seed point */
Curve *
pathsearch_generate(PathSearch *psearch, gint x, gint y)
{
	Curve *curve;
	guint8 dir;

	check_pointer( psearch );
	check_pointer( psearch->tree_dir );
	g_assert( x>=0 && x<psearch->width );
	g_assert( y>=0 && y<psearch->height );

	curve = curve_new();
	curve_set_free( curve, x, y );
	if( x==psearch->seed_x && y==psearch->seed_y ) return curve;
	dir = psearch->tree_dir[y][x];
	if( dir == DIR_NONE ) return NULL;
	while( x!=psearch->seed_x || y!=psearch->seed_y ) {
		curve_move_seed( curve, dir );
		curve_proceed( dir, &x, &y );
		dir = psearch->tree_dir[y][x];
	}
#ifdef DEBUG
	if( psearch->tree_cum_cost ) {
		CurveLink link;
		link.x = curve->free_x;
		link.y = curve->free_y;
		link.dir = 1;
		g_printerr("pathsearch_generate: x=%d y=%d len=%d lcost=%d cost=%d\n",
				curve->free_x, curve->free_y, curve_length(curve),
				costlist_get(psearch->costs, &link),
				psearch->tree_cum_cost[curve->free_y][curve->free_x] );
	} else {
		CurveLink link;
		link.x = curve->free_x;
		link.y = curve->free_y;
		link.dir = 1;
		g_printerr("pathsearch_generate: x=%d y=%d len=%d lcost=%d\n",
				curve->free_x, curve->free_y, curve_length(curve),
				costlist_get(psearch->costs, &link) );
	}
#endif

	return curve;
}

/* work on the spanning tree
 * every time this function is called, a bit of the tree
 * is generated
 */
static gboolean
pathsearch_dowork(gpointer data)
{
	CurveLink link;
	gint count;
	gint x, y, cumcost;
	PathSearch *psearch = (PathSearch*) data;

	check_pointer( psearch );
	check_pointer( psearch->tree_cum_cost );
	check_pointer( psearch->tree_dir );
	g_assert( psearch->working );

	count = 0;
	while( !bucketsort_is_empty(psearch->active) ) {
		/* get a newly evaluated pixel */
		bucketsort_pop( psearch->active, &x, &y );
		cumcost = psearch->tree_cum_cost[y][x];

		/* and work with it's neighbors */
		for( link.dir=0; link.dir<8; link.dir++ ) {
			gint nc, cost;

			link.x = x; link.y = y;
			curve_proceed( curve_reverse( link.dir ), &link.x, &link.y );
			if( link.x<0 || link.y<0 || link.x>=psearch->width || link.y>=psearch->height )
				continue;
			nc = psearch->tree_cum_cost[link.y][link.x];
			cost = cumcost + costlist_get(psearch->costs, &link);
			if( cost >= nc )
				continue;
			/* we found a better path */
			psearch->tree_cum_cost[link.y][link.x] = cost;
			psearch->tree_dir[link.y][link.x] = link.dir;
			/* mark that pixel for future work */
			bucketsort_push( psearch->active, link.x, link.y, cost );
		}

		/* only do some iterations here, come back after processing other events */
		if( ++count > 1000 ) return TRUE;
	}

	/* done, free the now obsolete data */
	costlist_new_livewire( psearch->costs, NULL ); /* XXX: needed? */
	array2d_free( (gpointer*) psearch->tree_cum_cost );
	bucketsort_free( psearch->active );
	psearch->tree_cum_cost = NULL;
	psearch->active = NULL;

	/* don't call this function again */
	psearch->working = FALSE;
	return FALSE;
}


/***************************************************************************/

/* LiveWire: high level stuff: maintain a list of curves */

LiveWire *
livewire_new()
{
	LiveWire *lw;
	CostList *costs;
	CostFunction *cost;

	lw = g_new0( LiveWire, 1 );

	costs = costlist_new();

	/* initialize cost functions */
	lw->grad_input = gradientinput_new();
	cost = gradientmag_new( lw->grad_input );
	costs = costlist_add( costs, cost, 2 );
	cost = dynamicmap_new( cost );
	costs = costlist_add( costs, cost, 1 );

	cost = gradientdir_new( lw->grad_input );
	costs = costlist_add( costs, cost, 2 );

	lw->psearch = pathsearch_new(costs);

	return lw;
}

void
livewire_free(LiveWire *lw)
{
	g_assert( lw );

	livewire_reset( lw );

	g_free( lw );
}

/* use this image for live wire */
void
livewire_set_image(LiveWire *lw, GimpImage *image)
{
	check_pointer( lw );

	pathsearch_set_image( lw->psearch, image );

	gradientinput_set_image( lw->grad_input, image );
}

/* start selecting an object */
void
livewire_start(LiveWire *lw, gint x, gint y)
{
	check_pointer( lw );
	g_assert( lw->wire==NULL );

	livewire_reset( lw );

	pathsearch_set_seed( lw->psearch, x, y, NULL );

	/* lw->wire will always hold the current wire, with aging info */
	lw->wire = curve_new();
	curve_add_age( lw->wire );
}

/* move the end of the live wire */
void
livewire_move(LiveWire *lw, gint x, gint y)
{
	Curve *curve;

	check_pointer( lw );
	check_pointer( lw->wire );

	if( x==lw->wire->free_x && y==lw->wire->free_y )
		return;

	curve = pathsearch_generate( lw->psearch, x, y );
	if( curve == NULL ) return;

	curve_replace( lw->wire, curve );

	/* path cooling: auto-generate new seed points? */
	if( curve_check_age( lw->wire, lw->grad_input ) ) {
		/* curve already got truncated */
		livewire_confirm( lw );
	}
}

/* the current live wire is ok, freeze it and start a new one from here */
void
livewire_confirm(LiveWire *lw)
{
	Curve *first;

	check_pointer( lw );
	check_pointer( lw->wire );

	if( curve_length(lw->wire) == 0 ) return;

	g_printerr( "livewire_confirm()\n" );
	curve_drop_age( lw->wire );
	pathsearch_set_seed( lw->psearch, lw->wire->free_x, lw->wire->free_y, lw->wire );
	/* lw->curves is in oposite order */
	lw->curves = g_list_prepend( lw->curves, lw->wire );

	first = (Curve*) g_list_last(lw->curves)->data;
	if( lw->wire!=first && curve_find_intersect( lw->wire, first ) ) {
		lw->wire = NULL;
		livewire_done( lw );
	} else {
		/* new live wire, with new age information */
		lw->wire = curve_new();
		curve_add_age( lw->wire );
	}
}

/* last confirm was wrong, undo it */
void
livewire_undo(LiveWire *lw)
{
	check_pointer( lw );
	g_assert( lw->curves );

	g_printerr( "livewire_undo()\n" );
	curve_free( lw->wire );
	lw->wire = (Curve*) lw->curves->data;
	lw->curves = g_list_remove( lw->curves, lw->wire );

	pathsearch_set_seed( lw->psearch, lw->wire->seed_x, lw->wire->seed_y, lw->curves->data );
}

/* curve segments are closed now */
void
livewire_done(LiveWire *lw)
{
	check_pointer( lw );

	g_printerr( "livewire_done()\n" );
	lw->closed = TRUE;
	pathsearch_stop( lw->psearch );
}

/* restart */
void
livewire_reset(LiveWire *lw)
{
	check_pointer( lw );

	pathsearch_stop( lw->psearch );

	g_free( lw->wire );
	lw->wire = NULL;

	while( lw->curves ) {
		curve_free( (Curve*) lw->curves->data );
		lw->curves = g_list_delete_link( lw->curves, lw->curves );
	}
	lw->curves = NULL;
}

/* return TRUE if it is already closed */
gboolean
livewire_closed(LiveWire *lw)
{
	check_pointer( lw );

	return lw->closed;
}



/* The GIMP -- an 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 2 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, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#ifndef __GIMP_ISISSORSTOOL_LIVEWIRE_H__
#define __GIMP_ISISSORSTOOL_LIVEWIRE_H__

#include <glib.h>
#include <glib-object.h>
#include <gtk/gtk.h>

#include "core/core-types.h"
#include "tools-types.h"
#include "core/gimpimage.h"
#include "display/gimpdisplay.h"

#include "gimpiscissorstool.h"

/* definition of classes */
typedef struct _Curve Curve;
typedef struct _CurveLink CurveLink;
typedef struct _AgeEntry AgeEntry;
typedef struct _GradientInput GradientInput;
typedef struct _CostFunction CostFunction;
typedef struct _CostList CostList;
typedef struct _BucketSort BucketSort;
typedef struct _PathSearch PathSearch;
/*typedef struct _LiveWire LiveWire;*/



/***************************************************************************/
/* CurveLink: position and direction of a link between two pixels */

struct _CurveLink {
	gint x, y;
	guint8 dir;
};

/***************************************************************************/
/* Curves: store one path segment between two seed points */

struct _Curve {
	/* start and end point */
	gint free_x, free_y;
	gint seed_x, seed_y;
	/* the actual data */
	GByteArray *curve;
	GArray *age; /* optional */
	/* bounding box of the curve */
	gint bounds_x1, bounds_x2;
	gint bounds_y1, bounds_y2;
};

static const guint8 DIR_NONE = 8;
typedef gboolean (*CurveTraversalCallback)(Curve*, CurveLink *, gpointer);

Curve* curve_new();
void curve_free(Curve *curve);
void curve_set_free(Curve *curve, gint x, gint y);
void curve_move_seed(Curve *curve, guint8 dir);
static inline gint curve_length(Curve *curve) {return curve->curve->len;}
void curve_traverse(Curve *curve, CurveTraversalCallback callback, gpointer data);
gboolean curve_has_age(Curve *curve);
void curve_add_age(Curve *curve);
void curve_drop_age(Curve *curve);
void curve_replace(Curve *target, Curve *source);
gboolean curve_check_age(Curve *curve, GradientInput *gi);
void curve_truncate_at_seed(Curve *curve, gint index, gint x, gint y);
void curve_truncate_at_free(Curve *curve, gint index, gint x, gint y);
gboolean curve_contains(Curve *curve, GimpIscissorsTool *iscissors, gdouble x, gdouble y, gint tolerance);
gboolean curve_find_intersect(Curve *c1, Curve *c2);
void curve_get_points(Curve *curve, gint *len, GimpVector2 **points);
void curve_draw(Curve *curve, GimpDrawTool *draw_tool);

void curve_proceed(guint8 dir, gint *x, gint *y);


/***************************************************************************/

struct _GradientInput {
	GimpImage *image;
	gint width, height;
	gint max_magnitude;
	gint **magnitude;
	gint **direction;
};

GradientInput * gradientinput_new();
void gradientinput_set_image(GradientInput *gi, GimpImage *image);
inline gint gradientinput_get_magnitude(GradientInput *gi, gint x, gint y);
inline gint gradientinput_get_direction(GradientInput *gi, gint x, gint y);


/***************************************************************************/
/* CostFunction: abstract class to calculate local costs */

struct _CostFunction {
	/* overrideable functions: */
	gint (*get_cost)(CostFunction *map, CurveLink *link);
	void (*new_livewire)(CostFunction *map, Curve *last);
	/* pointer to our input object */
	gpointer input;
	gpointer data;
};

void costfunction_free(CostFunction *cfunc);
void costfunction_new_livewire(CostFunction *map, Curve *last);
gint costfunction_get_cost(CostFunction *cfunc, CurveLink *link);



/***************************************************************************/
/* CostList: weighted costs */

struct _CostList {
	CostFunction *cost;
	gint weight;
	CostList *next;
};

CostList * costlist_new();
void costlist_free(CostList *costs);
CostList * costlist_add(CostList *costs, CostFunction *map, gint weight);
void costlist_set_image(CostList *costs, GimpImage *image);
void costlist_new_livewire(CostList *costs, Curve *last);
gint costlist_get(CostList *costs, CurveLink *link);


/***************************************************************************/
/* BucketSort: sorted list of active points */

BucketSort * bucketsort_new();
void bucketsort_free(BucketSort *bsort);
void bucketsort_remove_all(BucketSort *bsort);
gboolean bucketsort_is_empty(BucketSort *bsort);
void bucketsort_push(BucketSort *bsort, gint x, gint y, gint value);
void bucketsort_pop(BucketSort *bsort, gint *x, gint *y);


/***************************************************************************/
/* PathSearch: maintain a spanning tree of optimal paths */

struct _PathSearch {
	CostList *costs;	/* list of costs */
	gint seed_x, seed_y;	/* seed point for new curves */
	Curve *last_curve;	/* last curve ending at that seed point, if any */
	gint width, height;
	/* the spanning tree */
	gint **tree_cum_cost;
	guint8 **tree_dir;
	/* for background work: */
	BucketSort *active;
	gboolean working;
	guint work_tag;
};

PathSearch* pathsearch_new();
void pathsearch_free(PathSearch *psearch);
void pathsearch_stop(PathSearch *psearch);
void pathsearch_set_image(PathSearch *psearch, GimpImage *image);
void pathsearch_set_seed(PathSearch *psearch, gint x, gint y, Curve *last);
Curve * pathsearch_generate(PathSearch *psearch, gint x, gint y);


/***************************************************************************/

struct _LiveWire {
	PathSearch *psearch;
	GradientInput *grad_input;
	CostList *costs;	/* list of costs */
	GList *curves;
	Curve *wire;
	gboolean closed;
};

LiveWire * livewire_new();
void livewire_free(LiveWire *lw);
void livewire_set_image(LiveWire *lw, GimpImage *image);
void livewire_start(LiveWire *lw, gint x, gint y);
void livewire_move(LiveWire *lw, gint x, gint y);
void livewire_confirm(LiveWire *lw);
void livewire_undo(LiveWire *lw);
void livewire_done(LiveWire *lw);
void livewire_reset(LiveWire *lw);
gboolean livewire_closed(LiveWire *lw);


#endif


? .gimpiscissorstool.c.swp
? gimpiscissorstool-livewire.c
? gimpiscissorstool-livewire.h
Index: Makefile.am
===================================================================
RCS file: /cvs/gnome/gimp/app/tools/Makefile.am,v
retrieving revision 1.52
diff -u -p -r1.52 Makefile.am
--- Makefile.am 2002/02/08 07:51:16     1.52
+++ Makefile.am 2002/02/21 23:10:06
@@ -60,6 +60,8 @@ libapptools_a_SOURCES = @STRIP_BEGIN@ \
        gimpinktool-blob.h              \
        gimpiscissorstool.c             \
        gimpiscissorstool.h             \
+       gimpiscissorstool-livewire.c    \
+       gimpiscissorstool-livewire.h    \
        gimplevelstool.c                \
        gimplevelstool.h                \
        gimpmagnifytool.c               \
Index: gimpiscissorstool.c
===================================================================
RCS file: /cvs/gnome/gimp/app/tools/gimpiscissorstool.c,v
retrieving revision 1.108
diff -u -p -r1.108 gimpiscissorstool.c
--- gimpiscissorstool.c 2002/02/05 11:35:02     1.108
+++ gimpiscissorstool.c 2002/02/21 23:10:08
@@ -29,11 +29,14 @@
  * bore little resemblance to the one described in the paper above.
  * The 0.54 version of the algorithm was then forwards ported to 1.1.4
  * by Austin Donnelly.
+ * first Livewire boundary implementation done by Laramie Leavitt.
+ *
+ * The code was completely redesigned by Martin Waitz for 1.3,
+ * based on another paper by Mortensen and Barrett:
+ * http://www.cs.orst.edu/~enm/publications/GMIP_98/seg_scissors.html
  */
 
-/* Livewire boundary implementation done by Laramie Leavitt */
 
-
 #include "config.h"
 
 #include <stdlib.h>
@@ -65,9 +68,10 @@
 #include "display/gimpdisplay-foreach.h"
 
 #include "gimpbezierselecttool.h"
-#include "gimpiscissorstool.h"
 #include "gimpeditselectiontool.h"
 #include "selection_options.h"
+#include "gimpiscissorstool.h"
+#include "gimpiscissorstool-livewire.h"
 
 #include "libgimp/gimpintl.h"
 
@@ -83,8 +87,6 @@
 #define  FIXED             5   /* additional fixed size to expand cost map */
 #define  MIN_GRADIENT      63  /* gradients < this are directionless */
 
-#define  MAX_POINTS        2048
-
 #define  COST_WIDTH         2  /* number of bytes for each pixel in cost map  */
 #define  BLOCK_WIDTH       64
 #define  BLOCK_HEIGHT      64
@@ -102,14 +104,9 @@
 #define  PIXEL_COST(x)     (x >> 8)
 #define  PIXEL_DIR(x)      (x & 0x000000ff)
 
-
-struct _ICurve
-{
-  gint       x1, y1;
-  gint       x2, y2;
-  GPtrArray *points;
-};
 
+/***************************************************************************/
+/* OLD */
 
 /*  local function prototypes  */
 
@@ -166,9 +163,7 @@ static void          find_max_gradient  
                                                gint              *x,
                                                gint              *y);
 static void          calculate_curve           (GimpTool          *tool,
-                                               ICurve            *curve);
-static void          iscissors_draw_curve      (GimpDrawTool      *draw_tool,
-                                               ICurve            *curve);
+                                               Curve            *curve);
 static void          iscissors_free_icurves    (GSList            *list);
 static void          iscissors_free_buffers    (GimpIscissorsTool *iscissors);
 
@@ -194,7 +189,8 @@ static GPtrArray   * plot_pixels        
 
 /*  static variables  */
 
-/*  where to move on a given link direction  */
+/* where to move on a given link direction  */
+#if 0
 static gint move[8][2] =
 {
   {  1,  0 },
@@ -206,6 +202,7 @@ static gint move[8][2] =
   {  1, -1 },
   { -1, -1 },
 };
+#endif
 
 /* IE:
  * '---+---+---`
@@ -333,12 +330,16 @@ gimp_iscissors_tool_init (GimpIscissorsT
   tool = GIMP_TOOL (iscissors);
 
   iscissors->op           = -1;
+#if 0
   iscissors->curves       = NULL;
   iscissors->dp_buf       = NULL;
-  iscissors->state        = NO_ACTION;
-  iscissors->mask         = NULL;
   iscissors->gradient_map = NULL;
   iscissors->livewire     = NULL;
+#else
+       iscissors->livewire = livewire_new();
+#endif
+  iscissors->state        = NO_ACTION;
+  iscissors->mask         = NULL;
 
   tool->tool_cursor  = GIMP_SCISSORS_TOOL_CURSOR;
 
@@ -355,6 +356,7 @@ gimp_iscissors_tool_finalize (GObject *o
   iscissors = GIMP_ISCISSORS_TOOL (object);
 
   gimp_iscissors_tool_reset (iscissors);
+  livewire_free( iscissors->livewire );
 
   G_OBJECT_CLASS (parent_class)->finalize (object);
 }
@@ -427,11 +429,13 @@ gimp_iscissors_tool_button_press (GimpTo
 
   /*  If the tool was being used in another image...reset it  */
 
-  if (tool->state == ACTIVE && gdisp != tool->gdisp)
-    {
-      gimp_draw_tool_stop (GIMP_DRAW_TOOL (tool));
-      gimp_iscissors_tool_reset (iscissors);
-    }
+       if (gdisp != tool->gdisp) {
+               if ( tool->state == ACTIVE ) {
+                       gimp_draw_tool_stop (GIMP_DRAW_TOOL (tool));
+                       gimp_iscissors_tool_reset (iscissors);
+               }
+               livewire_set_image( iscissors->livewire, gdisp->gimage );
+       }
 
   tool->state = ACTIVE;
   tool->gdisp = gdisp;
@@ -451,14 +455,19 @@ gimp_iscissors_tool_button_press (GimpTo
       iscissors->x = CLAMP (iscissors->x, 0, gdisp->gimage->width - 1);
       iscissors->y = CLAMP (iscissors->y, 0, gdisp->gimage->height - 1);
 
+#if 0
       iscissors->ix = iscissors->x;
       iscissors->iy = iscissors->y;
+#endif
+
+      livewire_start( iscissors->livewire, iscissors->x, iscissors->y );
 
       /*  Initialize the selection core only on starting the tool  */
       gimp_draw_tool_start (GIMP_DRAW_TOOL (tool), gdisp);
       break;
 
     default:
+#if 0
       /*  Check if the mouse click occured on a vertex or the curve itself  */
       if (clicked_on_vertex (tool))
        {
@@ -498,6 +507,7 @@ gimp_iscissors_tool_button_press (GimpTo
        }
       /*  if we're not connected, we're adding a new point  */
       else if (! iscissors->connected)
+#endif
        {
          iscissors->state = SEED_PLACEMENT;
          iscissors->draw  = DRAW_CURRENT_SEED;
@@ -512,50 +522,33 @@ gimp_iscissors_tool_button_press (GimpTo
 }
 
 
+// create a new channel mask using our curves
 static void
 iscissors_convert (GimpIscissorsTool *iscissors,
                   GimpDisplay       *gdisp)
 {
-  GimpScanConvert *sc;
-  GimpVector2     *points;
-  guint            n_points;
-  GSList          *list;
-  ICurve          *icurve;
-  guint            packed;
-  gint             i;
-  gint             index;
-
-  sc = gimp_scan_convert_new (gdisp->gimage->width, gdisp->gimage->height, 1);
+       GList *list;
+       GimpScanConvert *sc;
+       GimpVector2 *points;
+       guint n_points;
 
-  /* go over the curves in reverse order, adding the points we have */
-  list = iscissors->curves;
-  index = g_slist_length (list);
-  while (index)
-    {
-      index--;
-      icurve = (ICurve *) g_slist_nth_data (list, index);
-
-      n_points = icurve->points->len;
-      points   = g_new (GimpVector2, n_points);
+       sc = gimp_scan_convert_new (gdisp->gimage->width, gdisp->gimage->height, 1);
 
-      for (i = 0; i < n_points; i ++)
-       {
-         packed = GPOINTER_TO_INT (g_ptr_array_index (icurve->points, i));
-         points[i].x = packed & 0x0000ffff;
-         points[i].y = packed >> 16;
+       /* FIXME: move to livewire_ */
+       list = iscissors->livewire->curves;
+       while( list ) {
+               curve_get_points( (Curve*) list->data, &n_points, &points );
+               gimp_scan_convert_add_points( sc, n_points, points );
+               g_free( points );
        }
-
-      gimp_scan_convert_add_points (sc, n_points, points);
-      g_free (points);
-    }
 
-  if (iscissors->mask)
-    g_object_unref (G_OBJECT (iscissors->mask));
+       if (iscissors->mask)
+               g_object_unref (G_OBJECT (iscissors->mask));
 
-  iscissors->mask = gimp_scan_convert_to_channel (sc, gdisp->gimage);
-  gimp_scan_convert_free (sc);
+       iscissors->mask = gimp_scan_convert_to_channel (sc, gdisp->gimage);
+       gimp_scan_convert_free (sc);
 
-  gimp_channel_invalidate_bounds (iscissors->mask);    
+       gimp_channel_invalidate_bounds (iscissors->mask);    
 }
 
 static void
@@ -567,12 +560,12 @@ gimp_iscissors_tool_button_release (Gimp
 {
   GimpIscissorsTool *iscissors;
   SelectionOptions  *sel_options;
-  ICurve            *curve;
 
   iscissors = GIMP_ISCISSORS_TOOL (tool);
 
   sel_options = (SelectionOptions *) tool->tool_info->tool_options;
 
+  g_printerr( "gimp_iscissors_tool_button_release: state=%d\n", iscissors->state);
   /* Make sure X didn't skip the button release event -- as it's known
    * to do
    */
@@ -596,7 +589,7 @@ gimp_iscissors_tool_button_release (Gimp
       break;
     }
 
-  gimp_draw_tool_stop (GIMP_DRAW_TOOL (tool));
+  //gimp_draw_tool_stop (GIMP_DRAW_TOOL (tool));
 
   /*  First take care of the case where the user "cancels" the action  */
   if (! (state & GDK_BUTTON3_MASK))
@@ -605,6 +598,7 @@ gimp_iscissors_tool_button_release (Gimp
       switch (iscissors->state)
        {
        case SEED_PLACEMENT:
+#if 0
          /*  Add a new icurve  */
          if (!iscissors->first_point)
            {
@@ -640,8 +634,11 @@ gimp_iscissors_tool_button_release (Gimp
            {
              iscissors->first_point = FALSE;
            }
+#else
+         livewire_confirm( iscissors->livewire );
+#endif
          break;
-
+#if 0
        case SEED_ADJUSTMENT:
          /*  recalculate both curves  */
          if (iscissors->curve1)
@@ -657,7 +654,7 @@ gimp_iscissors_tool_button_release (Gimp
              calculate_curve (tool, iscissors->curve2);
            }
          break;
-
+#endif
        default:
          break;
        }
@@ -667,11 +664,13 @@ gimp_iscissors_tool_button_release (Gimp
   iscissors->state = WAITING;
   iscissors->draw  = DRAW_CURVE;
 
-  gimp_draw_tool_resume (GIMP_DRAW_TOOL (tool));
+  gimp_draw_tool_pause (GIMP_DRAW_TOOL (tool));
 
-  /*  convert the curves into a region  */
-  if (iscissors->connected)
-    iscissors_convert (iscissors, gdisp);
+       /*  convert the curves into a region  */
+       if( livewire_closed( iscissors->livewire ) ) {
+               iscissors_convert( iscissors, gdisp );
+               iscissors->state = NO_ACTION;
+       }
 }
 
 static void
@@ -708,6 +707,7 @@ gimp_iscissors_tool_motion (GimpTool    
   iscissors->x = coords->x;
   iscissors->y = coords->y;
   
+#if 0
   switch (iscissors->state)
     {
     case SEED_PLACEMENT:
@@ -742,6 +742,7 @@ gimp_iscissors_tool_motion (GimpTool    
     default:
       break;
     }
+#endif
 
   gimp_draw_tool_resume (GIMP_DRAW_TOOL (tool));
 }
@@ -752,8 +753,8 @@ gimp_iscissors_tool_draw (GimpDrawTool *
   GimpTool          *tool;
   GimpIscissorsTool *iscissors;
   GimpDisplay       *gdisp;
-  ICurve            *curve;
-  GSList            *list;
+  Curve            *curve;
+  GList            *list;
 
   tool      = GIMP_TOOL (draw_tool);
   iscissors = GIMP_ISCISSORS_TOOL (draw_tool);
@@ -773,6 +774,7 @@ gimp_iscissors_tool_draw (GimpDrawTool *
                                   FALSE);
 
       /* Draw a line boundary */
+#if 0
       if (! iscissors->first_point && ! (iscissors->draw & DRAW_LIVEWIRE))
        {
           gimp_draw_tool_draw_line (draw_tool,
@@ -780,8 +782,12 @@ gimp_iscissors_tool_draw (GimpDrawTool *
                                     iscissors->x, iscissors->y,
                                     FALSE);
        }
+#endif
     }
 
+       livewire_move( iscissors->livewire, iscissors->x, iscissors->y );
+
+#if 0
   /* Draw the livewire boundary */
   if ((iscissors->draw & DRAW_LIVEWIRE) && ! iscissors->first_point)
     {
@@ -793,6 +799,7 @@ gimp_iscissors_tool_draw (GimpDrawTool *
            iscissors->iy != iscissors->livewire->y1 ||
            iscissors->y  != iscissors->livewire->y2)))
         {
+
           curve = g_new (ICurve, 1);
 
           curve->x1 = iscissors->ix;
@@ -815,12 +822,17 @@ gimp_iscissors_tool_draw (GimpDrawTool *
           calculate_curve (tool, curve);
           curve = NULL;
         }
-
-      /*  plot the curve  */
-      iscissors_draw_curve (draw_tool, iscissors->livewire);
-    }
-
-  if ((iscissors->draw & DRAW_CURVE) && ! iscissors->first_point)
+#endif
+       /*  plot the curve  */
+       if( iscissors->livewire->wire )
+               curve_draw( iscissors->livewire->wire, draw_tool );
+#if 0
+    }
+#endif
+
+  if( iscissors->livewire->curves ) {
+#if 0
+  if ((iscissors->draw & DRAW_CURVE) && iscissors->livewire->curves )
     {
       /*  Draw a point at the init point coordinates  */
       if (! iscissors->connected)
@@ -834,26 +846,27 @@ gimp_iscissors_tool_draw (GimpDrawTool *
                                       GTK_ANCHOR_CENTER,
                                       FALSE);
         }
+#endif
 
       /*  Go through the list of icurves, and render each one...  */
-      for (list = iscissors->curves; list; list = g_slist_next (list))
+      for (list = iscissors->livewire->curves; list; list = g_list_next (list))
        {
-         curve = (ICurve *) list->data;
+         curve = (Curve *) list->data;
 
-         /*  plot the curve  */
-         iscissors_draw_curve (draw_tool, curve);
+         /*  plot the curve_  */
+         curve_draw( curve, draw_tool );
 
           gimp_draw_tool_draw_handle (draw_tool,
                                       GIMP_HANDLE_FILLED_CIRCLE,
-                                      curve->x1,
-                                      curve->y1,
+                                      curve->seed_x,
+                                      curve->seed_y,
                                       POINT_WIDTH,
                                       POINT_WIDTH,
                                       GTK_ANCHOR_CENTER,
                                       FALSE);
        }
     }
-
+#if 0
   if (iscissors->draw & DRAW_ACTIVE_CURVE)
     {
       /*  plot both curves, and the control point between them  */
@@ -885,23 +898,26 @@ gimp_iscissors_tool_draw (GimpDrawTool *
                                   GTK_ANCHOR_CENTER,
                                   FALSE);
     }
+#endif
 }
 
 
+#if 0
+// draw one curve segment to the screen
 static void
 iscissors_draw_curve (GimpDrawTool *draw_tool,
                      ICurve       *curve)
 {
   gpointer *point;
   guint     len;
-  gint      npts = 0;
+  gint      n_pts = 0;
   guint32   coords;
   guint32   coords_2;
 
   /* Uh, this shouldn't happen, but it does.  So we ignore it.
    * Quality code, baby.
    */
-  if (! curve->points)
+  if (! curve->coords )
     return;
 
   point = curve->points->pdata + 1;
@@ -930,6 +946,7 @@ iscissors_draw_curve (GimpDrawTool *draw
        }
     }
 }
+#endif
 
 static void
 gimp_iscissors_tool_oper_update (GimpTool        *tool,
@@ -949,7 +966,7 @@ gimp_iscissors_tool_oper_update (GimpToo
     {
       iscissors->op = SELECTION_MOVE; /* abused */
     }
-  else if (iscissors->connected && iscissors->mask &&
+  else if (livewire_closed(iscissors->livewire) && iscissors->mask &&
           gimp_channel_value (iscissors->mask, coords->x, coords->y))
     {
       if ((state & GDK_SHIFT_MASK) && (state & GDK_CONTROL_MASK))
@@ -969,7 +986,7 @@ gimp_iscissors_tool_oper_update (GimpToo
          iscissors->op = SELECTION_REPLACE;
        }
     }
-  else if (iscissors->connected && iscissors->mask)
+  else if (livewire_closed(iscissors->livewire) && iscissors->mask)
     {
       iscissors->op = -1;
     }
@@ -1039,9 +1056,12 @@ gimp_iscissors_tool_cursor_update (GimpT
 }
 
 
+/***************************************************************************/
+
 static void
 gimp_iscissors_tool_reset (GimpIscissorsTool *iscissors)
 {
+#if 0
   /*  Free and reset the curve list  */
   if (iscissors->curves)
     {
@@ -1049,6 +1069,9 @@ gimp_iscissors_tool_reset (GimpIscissors
       g_slist_free (iscissors->curves);
       iscissors->curves = NULL;
     }
+#endif
+
+       livewire_reset( iscissors->livewire );
 
   /*  free mask  */
   if (iscissors->mask)
@@ -1056,7 +1079,7 @@ gimp_iscissors_tool_reset (GimpIscissors
       g_object_unref (G_OBJECT (iscissors->mask));
       iscissors->mask = NULL;
     }
-
+#if 0
   /* free the gradient map */
   if (iscissors->gradient_map)
     {
@@ -1075,10 +1098,12 @@ gimp_iscissors_tool_reset (GimpIscissors
   iscissors->curve2      = NULL;
   iscissors->first_point = TRUE;
   iscissors->connected   = FALSE;
+#endif
   iscissors->state       = NO_ACTION;
-
+#if 0
   /*  Reset the dp buffers  */
   iscissors_free_buffers (iscissors);
+#endif
 
   /*  If they haven't already been initialized, precalculate the diagonal
    *  weight and direction value arrays
@@ -1094,15 +1119,12 @@ gimp_iscissors_tool_reset (GimpIscissors
 static void
 iscissors_free_icurves (GSList *list)
 {
-  ICurve * curve;
+  Curve * curve;
 
   while (list)
     {
-      curve = (ICurve *) list->data;
-      if (curve->points)
-       g_ptr_array_free (curve->points, TRUE);
-
-      g_free (curve);
+      curve = (Curve *) list->data;
+      curve_free( curve );
       list = g_slist_next (list);
     }
 }
@@ -1111,10 +1133,12 @@ iscissors_free_icurves (GSList *list)
 static void
 iscissors_free_buffers (GimpIscissorsTool *iscissors)
 {
+#if 0
   if (iscissors->dp_buf)
     temp_buf_free (iscissors->dp_buf);
 
   iscissors->dp_buf = NULL;
+#endif
 }
 
 
@@ -1125,6 +1149,7 @@ mouse_over_vertex (GimpIscissorsTool *is
                   gdouble            x,
                   gdouble            y)
 {
+#if 0
   GSList *list;
   ICurve *curve;
   gint    curves_found = 0;
@@ -1133,7 +1158,6 @@ mouse_over_vertex (GimpIscissorsTool *is
    *  position is on an existing curve vertex.  Set the curve1 and curve2
    *  variables to the two curves containing the vertex in question
    */
-
   iscissors->curve1 = iscissors->curve2 = NULL;
 
   list = iscissors->curves;
@@ -1160,7 +1184,7 @@ mouse_over_vertex (GimpIscissorsTool *is
                                          GIMP_TOOL (iscissors)->gdisp,
                                          x, y,
                                          GIMP_HANDLE_CIRCLE,
-                                         curve->x2, curve->y2,
+                                         curve->x1, curve->y1,
                                          POINT_WIDTH, POINT_WIDTH,
                                          GTK_ANCHOR_CENTER,
                                          FALSE))
@@ -1173,8 +1197,9 @@ mouse_over_vertex (GimpIscissorsTool *is
 
       list = g_slist_next (list);
     }
-
   return curves_found;
+#endif
+  return 0;
 }
 
 static gboolean
@@ -1210,6 +1235,7 @@ mouse_over_curve (GimpIscissorsTool *isc
                  gdouble            x,
                  gdouble            y)
 {
+#if 0
   GSList   *list;
   gpointer *pt;
   gint      len;
@@ -1220,7 +1246,6 @@ mouse_over_curve (GimpIscissorsTool *isc
   /*  traverse through the list, returning the curve segment's list element
    *  if the current cursor position is on a curve... 
    */
-
   for (list = iscissors->curves; list; list = g_slist_next (list))
     {
       curve = (ICurve *) list->data;
@@ -1245,7 +1270,7 @@ mouse_over_curve (GimpIscissorsTool *isc
            }
        }
     }
-
+#endif
   return NULL;
 }
 
@@ -1254,7 +1279,7 @@ clicked_on_curve (GimpTool *tool)
 {
   GimpIscissorsTool *iscissors;
   GSList            *list, *new_link;
-  ICurve            *curve, *new_curve;
+  Curve            *curve, *new_curve;
 
   iscissors = GIMP_ISCISSORS_TOOL (tool);
 
@@ -1267,6 +1292,7 @@ clicked_on_curve (GimpTool *tool)
 
   if (list)
     {
+#if 0 /* temporarily disabled for live wire redesign */
       curve = (ICurve *) list->data;
 
       /*  Since we're modifying the curve, undraw the existing one  */
@@ -1297,6 +1323,7 @@ clicked_on_curve (GimpTool *tool)
       gimp_draw_tool_resume (GIMP_DRAW_TOOL (tool));
 
       return TRUE;
+#endif
     }
 
   return FALSE;
@@ -1326,8 +1353,8 @@ precalculate_arrays (void)
   direction_value[255][2] = 255;
   direction_value[255][3] = 255;
 }
-
 
+#if 0
 static void
 calculate_curve (GimpTool *tool,
                 ICurve   *curve)
@@ -1440,7 +1467,7 @@ calculate_curve (GimpTool *tool,
        }
     }
 }
-
+#endif
 
 /* badly need to get a replacement - this is _way_ too expensive */
 static gboolean
@@ -1515,6 +1542,7 @@ calculate_link (TileManager *gradient_ma
 }
 
 
+#if 0
 static GPtrArray *
 plot_pixels (GimpIscissorsTool *iscissors,
             TempBuf           *dp_buf,
@@ -1559,6 +1587,7 @@ plot_pixels (GimpIscissorsTool *iscissor
   /*  won't get here  */
   return NULL;
 }
+#endif
 
 
 #define PACK(x, y) ((((y) & 0xff) << 8) | ((x) & 0xff))
Index: gimpiscissorstool.h
===================================================================
RCS file: /cvs/gnome/gimp/app/tools/gimpiscissorstool.h,v
retrieving revision 1.12
diff -u -p -r1.12 gimpiscissorstool.h
--- gimpiscissorstool.h 2001/12/03 13:44:56     1.12
+++ gimpiscissorstool.h 2002/02/21 23:10:08
@@ -44,9 +44,7 @@ typedef enum
   DRAW_ALL          = (DRAW_CURRENT_SEED | DRAW_CURVE)
 } Iscissors_draw;
 
-typedef struct _ICurve ICurve;
 
-
 #define GIMP_TYPE_ISCISSORS_TOOL            (gimp_iscissors_tool_get_type ())
 #define GIMP_ISCISSORS_TOOL(obj)            (G_TYPE_CHECK_INSTANCE_CAST ((obj), 
GIMP_TYPE_ISCISSORS_TOOL, GimpIscissorsTool))
 #define GIMP_ISCISSORS_TOOL_CLASS(klass)    (G_TYPE_CHECK_CLASS_CAST ((klass), 
GIMP_TYPE_ISCISSORS_TOOL, GimpIscissorsToolClass))
@@ -55,6 +53,7 @@ typedef struct _ICurve ICurve;
 #define GIMP_ISCISSORS_TOOL_GET_CLASS(obj)  (G_TYPE_INSTANCE_GET_CLASS ((obj), 
GIMP_TYPE_ISCISSORS_TOOL, GimpIscissorsToolClass))
 
 
+typedef struct _LiveWire LiveWire;
 typedef struct _GimpIscissorsTool      GimpIscissorsTool;
 typedef struct _GimpIscissorsToolClass GimpIscissorsToolClass;
 
@@ -63,7 +62,7 @@ struct _GimpIscissorsTool
   GimpDrawTool    parent_instance;
 
   SelectOps       op;
-
+#if 0
   gint            x, y;         /*  upper left hand coordinate            */
   gint            ix, iy;       /*  initial coordinates                   */
   gint            nx, ny;       /*  new coordinates                       */
@@ -79,7 +78,10 @@ struct _GimpIscissorsTool
 
   gboolean        first_point;  /*  is this the first point?              */
   gboolean        connected;    /*  is the region closed?                 */
-
+#else
+  gint x, y;                   /* mouse position: move the wire there on next redraw 
+*/
+  LiveWire *livewire;
+#endif
   Iscissors_state state;        /*  state of iscissors                    */
   Iscissors_draw  draw;         /*  items to draw on a draw request       */
 

msg01998/pgp00000.pgp
Description: PGP signature