home *** CD-ROM | disk | FTP | other *** search
/ PC Pro 2002 April / pcpro0402.iso / essentials / graphics / Gimp / gimp-src-20001226.exe / src / gimp / app / iscissors.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-12-17  |  52.7 KB  |  2,017 lines
  1. /* The GIMP -- an image manipulation program
  2.  * Copyright (C) 1995 Spencer Kimball and Peter Mattis
  3.  *
  4.  * This program is free software; you can redistribute it and/or modify
  5.  * it under the terms of the GNU General Public License as published by
  6.  * the Free Software Foundation; either version 2 of the License, or
  7.  * (at your option) any later version.
  8.  *
  9.  * This program is distributed in the hope that it will be useful,
  10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  * GNU General Public License for more details.
  13.  *
  14.  * You should have received a copy of the GNU General Public License
  15.  * along with this program; if not, write to the Free Software
  16.  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17.  */
  18.  
  19. /* This tool is based on a paper from SIGGRAPH '95:
  20.  *  "Intelligent Scissors for Image Composition", Eric N. Mortensen and
  21.  *   William A. Barrett, Brigham Young University.
  22.  *
  23.  * thanks to Professor D. Forsyth for prompting us to implement this tool. */
  24.  
  25. /* The history of this implementation is lonog and varied.  It was
  26.  * orignally done by Spencer and Peter, and worked fine in the 0.54
  27.  * (motif only) release of the gimp.  Later revisions (0.99.something
  28.  * until about 1.1.4) completely changed the algorithm used, until it
  29.  * bore little resemblance to the one described in the paper above.
  30.  * The 0.54 version of the algorithm was then forwards ported to 1.1.4
  31.  * by Austin Donnelly.  */
  32.  
  33. #include "config.h"
  34.  
  35. #include <stdlib.h>
  36.  
  37. #include <gtk/gtk.h>
  38. #include <gdk/gdkkeysyms.h>
  39.  
  40. #include "apptypes.h"
  41.  
  42. #include "appenv.h"
  43. #include "draw_core.h"
  44. #include "channel_pvt.h"
  45. #include "cursorutil.h"
  46. #include "drawable.h"
  47. #include "gdisplay.h"
  48. #include "gimage_mask.h"
  49. #include "iscissors.h"
  50. #include "edit_selection.h"
  51. #include "paint_funcs.h"
  52. #include "selection_options.h"
  53. #include "temp_buf.h"
  54. #include "tools.h"
  55. #include "bezier_selectP.h"
  56. #include "scan_convert.h"
  57.  
  58. #include "libgimp/gimpmath.h"
  59.  
  60. #ifdef DEBUG
  61. #define TRC(x) g_print x
  62. #define D(x) x
  63. #else
  64. #define TRC(x)
  65. #define D(x)
  66. #endif
  67.  
  68.  
  69. /*  local structures  */
  70.  
  71. typedef struct _ICurve ICurve;
  72.  
  73. struct _ICurve
  74. {
  75.   int x1, y1;
  76.   int x2, y2;
  77.   GPtrArray *points;
  78. };
  79.  
  80. /*  The possible states...  */
  81. typedef enum
  82. {
  83.   NO_ACTION,
  84.   SEED_PLACEMENT,
  85.   SEED_ADJUSTMENT,
  86.   WAITING
  87. } Iscissors_state;
  88.  
  89. /*  The possible drawing states...  */
  90. typedef enum
  91. {
  92.   DRAW_NOTHING      = 0x0,
  93.   DRAW_CURRENT_SEED = 0x1,
  94.   DRAW_CURVE        = 0x2,
  95.   DRAW_ACTIVE_CURVE = 0x4
  96. } Iscissors_draw;
  97. #define  DRAW_ALL          (DRAW_CURRENT_SEED | DRAW_CURVE)
  98.  
  99. typedef struct _iscissors Iscissors;
  100.  
  101. struct _iscissors
  102. {
  103.   DrawCore       *core;         /*  Core select object               */
  104.  
  105.   SelectOps       op;
  106.  
  107.   gint            x, y;         /*  upper left hand coordinate       */
  108.   gint            ix, iy;       /*  initial coordinates              */
  109.   gint            nx, ny;       /*  new coordinates                  */
  110.  
  111.   TempBuf        *dp_buf;       /*  dynamic programming buffer              */
  112.  
  113.   ICurve         *curve1;       /*  1st curve connected to current point    */
  114.   ICurve         *curve2;       /*  2nd curve connected to current point    */
  115.  
  116.   GSList         *curves;       /*  the list of curves                      */
  117.  
  118.   gboolean        first_point;  /*  is this the first point?                */
  119.   gboolean        connected;    /*  is the region closed?                   */
  120.  
  121.   Iscissors_state state;        /*  state of iscissors               */
  122.   Iscissors_draw  draw;         /*  items to draw on a draw request         */
  123.  
  124.   /* XXX might be useful */
  125.   Channel        *mask;         /*  selection mask                   */
  126.   TileManager    *gradient_map; /*  lazily filled gradient map */
  127. };
  128.  
  129. typedef struct _IScissorsOptions IScissorsOptions;
  130. struct _IScissorsOptions
  131. {
  132.   SelectionOptions  selection_options;
  133. };
  134.  
  135.  
  136. /**********************************************/
  137. /*  Intelligent scissors selection apparatus  */
  138.  
  139.  
  140. /*  Other defines...  */
  141. #define  MAX_GRADIENT      179.606  /* == sqrt(127^2 + 127^2) */
  142. #define  GRADIENT_SEARCH   32  /* how far to look when snapping to an edge */
  143. #define  TARGET_HEIGHT     25
  144. #define  TARGET_WIDTH      25
  145. #define  POINT_WIDTH       8   /* size (in pixels) of seed handles */
  146. #define  POINT_HALFWIDTH   (POINT_WIDTH / 2)
  147. #define  EXTEND_BY         0.2 /* proportion to expand cost map by */
  148. #define  FIXED             5   /* additional fixed size to expand cost map */
  149. #define  MIN_GRADIENT      63  /* gradients < this are directionless */
  150.  
  151. #define  MAX_POINTS        2048
  152.  
  153. #ifdef USE_LAPLACIAN
  154. # define COST_WIDTH        3  /* number of bytes for each pixel in cost map  */
  155. #else
  156. # define COST_WIDTH        2  /* number of bytes for each pixel in cost map  */
  157. #endif
  158. #define  BLOCK_WIDTH       64
  159. #define  BLOCK_HEIGHT      64
  160. #define  CONV_WIDTH        (BLOCK_WIDTH + 2)
  161. #define  CONV_HEIGHT       (BLOCK_HEIGHT + 2)
  162.  
  163. /* weight to give between laplacian (_Z), gradient (_G) and direction (_D) */
  164. #ifdef USE_LAPLACIAN
  165. #  define  OMEGA_Z           0.16
  166. #  define  OMEGA_D           0.42
  167. #  define  OMEGA_G           0.42
  168. #else
  169. #  define  OMEGA_D           0.2
  170. #  define  OMEGA_G           0.8
  171. #endif
  172.  
  173. /* sentinel to mark seed point in ?cost? map */
  174. #define  SEED_POINT        9
  175.  
  176. /*  Functional defines  */
  177. #define  PIXEL_COST(x)     (x >> 8)
  178. #define  PIXEL_DIR(x)      (x & 0x000000ff)
  179.  
  180.  
  181. /*  static variables  */
  182.  
  183. /*  where to move on a given link direction  */
  184. static int move [8][2] =
  185. {
  186.   { 1, 0 },
  187.   { 0, 1 },
  188.   { -1, 1 },
  189.   { 1, 1 },
  190.   { -1, 0 },
  191.   { 0, -1 },
  192.   { 1, -1 },
  193.   { -1, -1 },
  194. };
  195.  
  196. /* IE:
  197.  * '---+---+---`
  198.  * | 7 | 5 | 6 |
  199.  * +---+---+---+
  200.  * | 4 |   | 0 |
  201.  * +---+---+---+
  202.  * | 2 | 1 | 3 |
  203.  * `---+---+---'
  204.  */
  205.  
  206. /*  points for drawing curves  */
  207. static GdkPoint    curve_points [MAX_POINTS];
  208.  
  209.  
  210. /*  temporary convolution buffers --  */
  211. D(static guint sent0 = 0xd0d0d0d0);
  212. static guchar  maxgrad_conv0 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
  213. D(static guint sent1 = 0xd1d1d1d1);
  214. static guchar  maxgrad_conv1 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
  215. D(static guint sent2 = 0xd2d2d2d2);
  216. static guchar  maxgrad_conv2 [TILE_WIDTH * TILE_HEIGHT * 4] = "";
  217. D(static guint sent3 = 0xd3d3d3d3);
  218.  
  219.  
  220. static gint horz_deriv [9] =
  221. {
  222.   1, 0, -1,
  223.   2, 0, -2,
  224.   1, 0, -1,
  225. };
  226.  
  227. static gint vert_deriv [9] =
  228. {
  229.   1, 2, 1,
  230.   0, 0, 0,
  231.   -1, -2, -1,
  232. };
  233.  
  234.  
  235. #ifdef USE_LAPLACIAN
  236. static gint  laplacian [9] = 
  237. {
  238.   -1, -1, -1,
  239.   -1, 8, -1,
  240.   -1, -1, -1,
  241. };
  242. #endif
  243.  
  244. static gint blur_32 [9] = 
  245. {
  246.   1, 1, 1,
  247.   1, 24, 1,
  248.   1, 1, 1,
  249. };
  250.  
  251. static gfloat    distance_weights [GRADIENT_SEARCH * GRADIENT_SEARCH];
  252.  
  253. static gint      diagonal_weight [256];
  254. static gint      direction_value [256][4];
  255. static gboolean  initialized = FALSE;
  256. static Tile     *cur_tile = NULL;
  257.  
  258.  
  259. /***********************************************************************/
  260. /* static variables */
  261.  
  262. static IScissorsOptions *iscissors_options = NULL;
  263.  
  264.  
  265. /***********************************************************************/
  266. /*  Local function prototypes  */
  267.  
  268. static void   iscissors_button_press    (Tool *, GdkEventButton *, gpointer);
  269. static void   iscissors_button_release  (Tool *, GdkEventButton *, gpointer);
  270. static void   iscissors_motion          (Tool *, GdkEventMotion *, gpointer);
  271. static void   iscissors_oper_update     (Tool *, GdkEventMotion *, gpointer);
  272. static void   iscissors_modifier_update (Tool *, GdkEventKey *,    gpointer);
  273. static void   iscissors_cursor_update   (Tool *, GdkEventMotion *, gpointer);
  274. static void   iscissors_control         (Tool *, ToolAction, gpointer);
  275.  
  276. static void   iscissors_reset           (Iscissors *iscissors);
  277. static void   iscissors_draw            (Tool      *tool);
  278.  
  279. static TileManager * gradient_map_new          (GImage      *gimage);
  280.  
  281. static void          find_optimal_path         (TileManager *gradient_map,
  282.                         TempBuf     *dp_buf,
  283.                         gint         x1,
  284.                         gint         y1,
  285.                         gint         x2,
  286.                         gint         y2,
  287.                         gint         xs,
  288.                         gint         ys);
  289. static void          find_max_gradient         (Iscissors   *iscissors,
  290.                         GImage      *gimage,
  291.                         gint        *x,
  292.                         gint        *y);
  293. static void          calculate_curve           (Tool        *tool,
  294.                         ICurve      *curve);
  295. static void          iscissors_draw_curve      (GDisplay    *gdisp,
  296.                         Iscissors   *iscissors,
  297.                         ICurve      *curve);
  298. static void          iscissors_free_icurves    (GSList      *list);
  299. static void          iscissors_free_buffers    (Iscissors   *iscissors);
  300.  
  301. static gint          mouse_over_vertex         (Iscissors   *iscissors,
  302.                         gint         x,
  303.                         gint         y);
  304. static gboolean      clicked_on_vertex         (Tool        *tool);
  305. static GSList      * mouse_over_curve          (Iscissors   *iscissors,
  306.                         gint         x,
  307.                         gint         y);
  308. static gboolean      clicked_on_curve          (Tool        *tool);
  309.  
  310. static void          precalculate_arrays       (void);
  311. static GPtrArray   * plot_pixels               (Iscissors   *iscissors,
  312.                         TempBuf     *dp_buf,
  313.                         gint         x1,
  314.                         gint         y1,
  315.                         gint         xs,
  316.                         gint         ys,
  317.                         gint         xe,
  318.                         gint         ye);
  319.  
  320. static void
  321. iscissors_options_reset (void)
  322. {
  323.   IScissorsOptions *options = iscissors_options;
  324.  
  325.   selection_options_reset ((SelectionOptions *) options);
  326. }
  327.  
  328. static IScissorsOptions *
  329. iscissors_options_new (void)
  330. {
  331.   IScissorsOptions *options;
  332.  
  333.   /*  the new intelligent scissors tool options structure  */
  334.   options = g_new (IScissorsOptions, 1);
  335.   selection_options_init ((SelectionOptions *) options,
  336.               ISCISSORS,
  337.               iscissors_options_reset);
  338.  
  339.   return options;
  340. }
  341.  
  342. Tool *
  343. tools_new_iscissors (void)
  344. {
  345.   Tool * tool;
  346.   Iscissors * private;
  347.  
  348.   if (!iscissors_options)
  349.     {
  350.       iscissors_options = iscissors_options_new ();
  351.       tools_register (ISCISSORS, (ToolOptions *) iscissors_options);
  352.     }
  353.  
  354.   tool = tools_new_tool (ISCISSORS);
  355.   private = g_new0 (Iscissors, 1);
  356.  
  357.   private->core = draw_core_new (iscissors_draw);
  358.   private->op           = -1;
  359.   private->curves       = NULL;
  360.   private->dp_buf       = NULL;
  361.   private->state        = NO_ACTION;
  362.   private->mask         = NULL;
  363.   private->gradient_map = NULL;
  364.  
  365.   tool->auto_snap_to = FALSE;   /*  Don't snap to guides   */
  366.  
  367.   tool->private = (void *) private;
  368.   
  369.   tool->button_press_func    = iscissors_button_press;
  370.   tool->button_release_func  = iscissors_button_release;
  371.   tool->motion_func          = iscissors_motion;
  372.   tool->oper_update_func     = iscissors_oper_update;
  373.   tool->modifier_key_func    = iscissors_modifier_update;
  374.   tool->cursor_update_func   = iscissors_cursor_update;
  375.   tool->control_func         = iscissors_control;
  376.  
  377.   iscissors_reset (private);
  378.  
  379.   return tool;
  380. }
  381.  
  382. void
  383. tools_free_iscissors (Tool *tool)
  384. {
  385.   Iscissors * iscissors;
  386.  
  387.   iscissors = (Iscissors *) tool->private;
  388.  
  389.   TRC (("tools_free_iscissors\n"));
  390.  
  391.   /*  XXX? Undraw curve  */
  392.   /*iscissors->draw = DRAW_CURVE;*/
  393.  
  394.   if (tool->state == ACTIVE)
  395.     draw_core_stop (iscissors->core, tool);
  396.   draw_core_free (iscissors->core);
  397.  
  398.   iscissors_reset (iscissors);
  399.  
  400.   g_free (iscissors);
  401. }
  402.  
  403.  
  404. /*  Local functions  */
  405.  
  406. static void
  407. iscissors_button_press (Tool           *tool,
  408.             GdkEventButton *bevent,
  409.             gpointer        gdisp_ptr)
  410. {
  411.   GDisplay     *gdisp;
  412.   GimpDrawable *drawable;
  413.   Iscissors    *iscissors;
  414.   gboolean      grab_pointer = FALSE;
  415.  
  416.   gdisp = (GDisplay *) gdisp_ptr;
  417.   iscissors = (Iscissors *) tool->private;
  418.   drawable = gimage_active_drawable (gdisp->gimage);
  419.  
  420.   gdisplay_untransform_coords (gdisp, bevent->x, bevent->y,
  421.                    &iscissors->x, &iscissors->y, FALSE, FALSE);
  422.  
  423.   /*  If the tool was being used in another image...reset it  */
  424.  
  425.   if (tool->state == ACTIVE && gdisp_ptr != tool->gdisp_ptr)
  426.     {
  427.       /*iscissors->draw = DRAW_CURVE; XXX? */
  428.       draw_core_stop (iscissors->core, tool);
  429.       iscissors_reset (iscissors);
  430.     }
  431.  
  432.   tool->state = ACTIVE;
  433.   tool->gdisp_ptr = gdisp_ptr;
  434.  
  435.   switch (iscissors->state)
  436.     {
  437.     case NO_ACTION:
  438. #if 0
  439.       /* XXX what's this supposed to do? */
  440.       if (!(bevent->state & GDK_SHIFT_MASK) &&
  441.       !(bevent->state & GDK_CONTROL_MASK))
  442.     if (selection_point_inside (gdisp->select, gdisp_ptr,
  443.                     bevent->x, bevent->y))
  444.       {
  445.         init_edit_selection (tool, gdisp->select, gdisp_ptr,
  446.                  bevent->x, bevent->y);
  447.         return;
  448.       }
  449. #endif
  450.  
  451.       iscissors->state = SEED_PLACEMENT;
  452.       iscissors->draw = DRAW_CURRENT_SEED;
  453.       grab_pointer = TRUE;
  454.  
  455.       if (! (bevent->state & GDK_SHIFT_MASK))
  456.     find_max_gradient (iscissors, gdisp->gimage,
  457.                &iscissors->x, &iscissors->y);
  458.  
  459.       iscissors->x = CLAMP (iscissors->x, 0, gdisp->gimage->width - 1);
  460.       iscissors->y = CLAMP (iscissors->y, 0, gdisp->gimage->height - 1);
  461.  
  462.       iscissors->ix = iscissors->x;
  463.       iscissors->iy = iscissors->y;
  464.  
  465.       /*  Initialize the selection core only on starting the tool  */
  466.       draw_core_start (iscissors->core, gdisp->canvas->window, tool);
  467.       break;
  468.  
  469.     default:
  470.       /*  Check if the mouse click occured on a vertex or the curve itself  */
  471.       if (clicked_on_vertex (tool))
  472.     {
  473.       iscissors->nx = iscissors->x;
  474.       iscissors->ny = iscissors->y;
  475.       iscissors->state = SEED_ADJUSTMENT;
  476.       iscissors->draw = DRAW_ACTIVE_CURVE;
  477.       draw_core_resume (iscissors->core, tool);
  478.       grab_pointer = TRUE;
  479.     }
  480.       /*  If the iscissors is connected, check if the click was inside  */
  481.       else if (iscissors->connected && iscissors->mask &&
  482.            channel_value (iscissors->mask, iscissors->x, iscissors->y))
  483.     {
  484.       /*  Undraw the curve  */
  485.       tool->state = INACTIVE;
  486.       iscissors->draw = DRAW_CURVE;
  487.       draw_core_stop (iscissors->core, tool);
  488.  
  489.       if (iscissors->op == SELECTION_REPLACE)
  490.         gimage_mask_clear (gdisp->gimage);
  491.       else
  492.         gimage_mask_undo (gdisp->gimage);
  493.  
  494.       if (((SelectionOptions *) iscissors_options)->feather)
  495.         channel_feather (iscissors->mask,
  496.                  gimage_get_mask (gdisp->gimage),
  497.                  ((SelectionOptions *) iscissors_options)->feather_radius,
  498.                  ((SelectionOptions *) iscissors_options)->feather_radius,
  499.                  iscissors->op, 0, 0);
  500.       else
  501.         channel_combine_mask (gimage_get_mask (gdisp->gimage),
  502.                   iscissors->mask, iscissors->op, 0, 0);
  503.  
  504.       iscissors_reset (iscissors);
  505.  
  506.       gdisplays_flush ();
  507.     }
  508.       /*  if we're not connected, we're adding a new point  */
  509.       else if (!iscissors->connected)
  510.     {
  511.       iscissors->state = SEED_PLACEMENT;
  512.       iscissors->draw = DRAW_CURRENT_SEED;
  513.       grab_pointer = TRUE;
  514.       
  515.       draw_core_resume (iscissors->core, tool);
  516.     }
  517.       break;
  518.     }
  519.  
  520.   if (grab_pointer)
  521.     gdk_pointer_grab (gdisp->canvas->window, FALSE,
  522.               GDK_POINTER_MOTION_HINT_MASK |
  523.               GDK_BUTTON1_MOTION_MASK |
  524.               GDK_BUTTON_RELEASE_MASK,
  525.               NULL, NULL, bevent->time);  
  526. }
  527.  
  528.  
  529. static void
  530. iscissors_convert (Iscissors *iscissors,
  531.            gpointer   gdisp_ptr)
  532. {
  533.   GDisplay *gdisp = (GDisplay *) gdisp_ptr;
  534.   ScanConverter    *sc;
  535.   ScanConvertPoint *pts;
  536.   guint   npts;
  537.   GSList *list;
  538.   ICurve *icurve;
  539.   guint   packed;
  540.   gint    i;
  541.   gint    index;
  542.  
  543.   sc = scan_converter_new (gdisp->gimage->width, gdisp->gimage->height, 1);
  544.  
  545.   /* go over the curves in reverse order, adding the points we have */
  546.   list = iscissors->curves;
  547.   index = g_slist_length (list);
  548.   while (index)
  549.     {
  550.       index--;
  551.  
  552.       icurve = (ICurve *) g_slist_nth_data (list, index);
  553.  
  554.       npts = icurve->points->len;
  555.       pts = g_new (ScanConvertPoint, npts);
  556.  
  557.       for (i = 0; i < npts; i ++)
  558.     {
  559.       packed = GPOINTER_TO_INT (g_ptr_array_index (icurve->points, i));
  560.       pts[i].x = packed & 0x0000ffff;
  561.       pts[i].y = packed >> 16;
  562.     }
  563.  
  564.       scan_converter_add_points (sc, npts, pts);
  565.       g_free (pts);
  566.     }
  567.  
  568.   if (iscissors->mask)
  569.     channel_delete (iscissors->mask);
  570.   iscissors->mask = scan_converter_to_channel (sc, gdisp->gimage);
  571.   scan_converter_free (sc);
  572.  
  573.   channel_invalidate_bounds (iscissors->mask);    
  574. }
  575.  
  576.  
  577. static void
  578. iscissors_button_release (Tool           *tool,
  579.               GdkEventButton *bevent,
  580.               gpointer        gdisp_ptr)
  581. {
  582.   Iscissors *iscissors;
  583.   GDisplay  *gdisp;
  584.   ICurve    *curve;
  585.  
  586.   gdisp = (GDisplay *) gdisp_ptr;
  587.   iscissors = (Iscissors *) tool->private;
  588.  
  589.   TRC (("iscissors_button_release\n"));
  590.  
  591.   /* Make sure X didn't skip the button release event -- as it's known
  592.    * to do */
  593.   if (iscissors->state == WAITING)
  594.     return;
  595.  
  596.   gdk_pointer_ungrab (bevent->time);
  597.   gdk_flush ();  /* XXX why the flush? */
  598.  
  599.   /*  Undraw everything  */
  600.   switch (iscissors->state)
  601.     {
  602.     case SEED_PLACEMENT:
  603.       iscissors->draw = DRAW_CURVE | DRAW_CURRENT_SEED;
  604.       break;
  605.     case SEED_ADJUSTMENT:
  606.       iscissors->draw = DRAW_CURVE | DRAW_ACTIVE_CURVE;
  607.       break;
  608.     default:
  609.       break;
  610.     }
  611.  
  612.   draw_core_stop (iscissors->core, tool);
  613.  
  614.   /*  First take care of the case where the user "cancels" the action  */
  615.   if (! (bevent->state & GDK_BUTTON3_MASK))
  616.     {
  617.       /*  Progress to the next stage of intelligent selection  */
  618.       switch (iscissors->state)
  619.     {
  620.     case SEED_PLACEMENT:
  621.       /*  Add a new icurve  */
  622.       if (!iscissors->first_point)
  623.         {
  624.           /*  Determine if we're connecting to the first point  */
  625.           if (iscissors->curves)
  626.         {
  627.           curve = (ICurve *) iscissors->curves->data;
  628.           if (abs (iscissors->x - curve->x1) < POINT_HALFWIDTH &&
  629.               abs (iscissors->y - curve->y1) < POINT_HALFWIDTH)
  630.             {
  631.               iscissors->x = curve->x1;
  632.               iscissors->y = curve->y1;
  633.               iscissors->connected = TRUE;
  634.             }
  635.         }
  636.  
  637.           /*  Create the new curve segment  */
  638.           if (iscissors->ix != iscissors->x ||
  639.           iscissors->iy != iscissors->y)
  640.         {
  641.           curve = g_new (ICurve, 1);
  642.  
  643.           curve->x1 = iscissors->ix;
  644.           curve->y1 = iscissors->iy;
  645.           iscissors->ix = curve->x2 = iscissors->x;
  646.           iscissors->iy = curve->y2 = iscissors->y;
  647.           curve->points = NULL;
  648.           TRC (("create new curve segment\n"));
  649.           iscissors->curves = g_slist_append (iscissors->curves,
  650.                               (void *) curve);
  651.           TRC (("calculate curve\n"));
  652.           calculate_curve (tool, curve);
  653.         }
  654.         }
  655.       else /* this was our first point */
  656.         {
  657.           iscissors->first_point = FALSE;
  658.         }
  659.       break;
  660.  
  661.     case SEED_ADJUSTMENT:
  662.       /*  recalculate both curves  */
  663.       if (iscissors->curve1)
  664.         {
  665.           iscissors->curve1->x1 = iscissors->nx;
  666.           iscissors->curve1->y1 = iscissors->ny;
  667.           calculate_curve (tool, iscissors->curve1);
  668.         }
  669.       if (iscissors->curve2)
  670.         {
  671.           iscissors->curve2->x2 = iscissors->nx;
  672.           iscissors->curve2->y2 = iscissors->ny;
  673.           calculate_curve (tool, iscissors->curve2);
  674.         }
  675.       break;
  676.  
  677.     default:
  678.       break;
  679.     }
  680.     }
  681.  
  682.   TRC (("button_release: draw core resume\n"));
  683.  
  684.   /*  Draw only the boundary  */
  685.   iscissors->state = WAITING;
  686.   iscissors->draw = DRAW_CURVE;
  687.   draw_core_resume (iscissors->core, tool);
  688.  
  689.   /*  convert the curves into a region  */
  690.   if (iscissors->connected)
  691.     iscissors_convert (iscissors, gdisp_ptr);
  692. }
  693.  
  694. static void
  695. iscissors_motion (Tool           *tool,
  696.           GdkEventMotion *mevent,
  697.           gpointer        gdisp_ptr)
  698. {
  699.   Iscissors *iscissors;
  700.   GDisplay *gdisp;
  701.   
  702.   gdisp = (GDisplay *) gdisp_ptr;
  703.   iscissors = (Iscissors *) tool->private;
  704.  
  705.   if (tool->state != ACTIVE || iscissors->state == NO_ACTION)
  706.     return;
  707.  
  708.   if (iscissors->state == SEED_PLACEMENT)
  709.     iscissors->draw = DRAW_CURRENT_SEED;
  710.   else if (iscissors->state == SEED_ADJUSTMENT)
  711.     iscissors->draw = DRAW_ACTIVE_CURVE;
  712.  
  713.   draw_core_pause (iscissors->core, tool);
  714.  
  715.   gdisplay_untransform_coords (gdisp, mevent->x, mevent->y, 
  716.                    &iscissors->x, &iscissors->y, FALSE, FALSE);
  717.   
  718.   switch (iscissors->state)
  719.     {
  720.     case SEED_PLACEMENT:
  721.       /*  Hold the shift key down to disable the auto-edge snap feature  */
  722.       if (! (mevent->state & GDK_SHIFT_MASK))
  723.     find_max_gradient (iscissors, gdisp->gimage,
  724.                &iscissors->x, &iscissors->y);
  725.  
  726.       iscissors->x = CLAMP (iscissors->x, 0, gdisp->gimage->width - 1);
  727.       iscissors->y = CLAMP (iscissors->y, 0, gdisp->gimage->height - 1);
  728.  
  729.       if (iscissors->first_point)
  730.     {
  731.       iscissors->ix = iscissors->x;
  732.       iscissors->iy = iscissors->y;
  733.     }
  734.       break;
  735.  
  736.     case SEED_ADJUSTMENT:
  737.       /*  Move the current seed to the location of the cursor  */
  738.       if (! (mevent->state & GDK_SHIFT_MASK))
  739.     find_max_gradient (iscissors, gdisp->gimage,
  740.                &iscissors->x, &iscissors->y);
  741.  
  742.       iscissors->x = CLAMP (iscissors->x, 0, gdisp->gimage->width - 1);
  743.       iscissors->y = CLAMP (iscissors->y, 0, gdisp->gimage->height - 1);
  744.  
  745.       iscissors->nx = iscissors->x;
  746.       iscissors->ny = iscissors->y;
  747.       break;
  748.  
  749.     default:
  750.       break;
  751.     }
  752.  
  753.   draw_core_resume (iscissors->core, tool);
  754. }
  755.  
  756.  
  757. static void
  758. iscissors_draw (Tool *tool)
  759. {
  760.   GDisplay *gdisp;
  761.   Iscissors *iscissors;
  762.   ICurve *curve;
  763.   GSList *list;
  764.   int tx1, ty1, tx2, ty2;
  765.   int txn, tyn;
  766.  
  767.   TRC (("iscissors_draw\n"));
  768.  
  769.   gdisp = (GDisplay *) tool->gdisp_ptr;
  770.   iscissors = (Iscissors *) tool->private;
  771.  
  772.   gdisplay_transform_coords (gdisp, iscissors->ix, iscissors->iy, &tx1, &ty1,
  773.                  FALSE);
  774.  
  775.   /*  Draw the crosshairs target if we're placing a seed  */
  776.   if (iscissors->draw & DRAW_CURRENT_SEED)
  777.     {
  778.       gdisplay_transform_coords (gdisp, iscissors->x, iscissors->y, &tx2, &ty2,
  779.                  FALSE);
  780.  
  781.       gdk_draw_line (iscissors->core->win, iscissors->core->gc, 
  782.              tx2 - (TARGET_WIDTH >> 1), ty2,
  783.              tx2 + (TARGET_WIDTH >> 1), ty2);
  784.       gdk_draw_line (iscissors->core->win, iscissors->core->gc, 
  785.              tx2, ty2 - (TARGET_HEIGHT >> 1),
  786.              tx2, ty2 + (TARGET_HEIGHT >> 1));
  787.  
  788.       if (!iscissors->first_point)
  789.     gdk_draw_line (iscissors->core->win, iscissors->core->gc, 
  790.                tx1, ty1, tx2, ty2);
  791.     }
  792.  
  793.   if ((iscissors->draw & DRAW_CURVE) && !iscissors->first_point)
  794.     {
  795.       /*  Draw a point at the init point coordinates  */
  796.       if (!iscissors->connected)
  797.     gdk_draw_arc (iscissors->core->win, iscissors->core->gc, 1,
  798.               tx1 - POINT_HALFWIDTH, ty1 - POINT_HALFWIDTH, 
  799.               POINT_WIDTH, POINT_WIDTH, 0, 23040);
  800.  
  801.       /*  Go through the list of icurves, and render each one...  */
  802.       list = iscissors->curves;
  803.       while (list)
  804.     {
  805.       curve = (ICurve *) list->data;
  806.  
  807.       /*  plot the curve  */
  808.       iscissors_draw_curve (gdisp, iscissors, curve);
  809.  
  810.       gdisplay_transform_coords (gdisp, curve->x1, curve->y1, &tx1, &ty1,
  811.                      FALSE);
  812.  
  813.       gdk_draw_arc (iscissors->core->win, iscissors->core->gc, 1,
  814.             tx1 - POINT_HALFWIDTH, ty1 - POINT_HALFWIDTH, 
  815.             POINT_WIDTH, POINT_WIDTH, 0, 23040);
  816.  
  817.       list = g_slist_next (list);
  818.     }
  819.     }
  820.  
  821.   if (iscissors->draw & DRAW_ACTIVE_CURVE)
  822.     {
  823.       gdisplay_transform_coords (gdisp, iscissors->nx, iscissors->ny,
  824.                  &txn, &tyn, FALSE);
  825.  
  826.       /*  plot both curves, and the control point between them  */
  827.       if (iscissors->curve1)
  828.     {
  829.       gdisplay_transform_coords (gdisp, iscissors->curve1->x2, 
  830.                      iscissors->curve1->y2, &tx1, &ty1, FALSE);
  831.  
  832.       gdk_draw_line (iscissors->core->win, iscissors->core->gc, 
  833.              tx1, ty1, txn, tyn);
  834.     }
  835.       if (iscissors->curve2)
  836.     {
  837.       gdisplay_transform_coords (gdisp, iscissors->curve2->x1, 
  838.                      iscissors->curve2->y1, &tx2, &ty2, FALSE);
  839.  
  840.       gdk_draw_line (iscissors->core->win, iscissors->core->gc, 
  841.              tx2, ty2, txn, tyn);
  842.     }
  843.  
  844.       gdk_draw_arc (iscissors->core->win, iscissors->core->gc, 1,
  845.             txn - POINT_HALFWIDTH, tyn - POINT_HALFWIDTH, 
  846.             POINT_WIDTH, POINT_WIDTH, 0, 23040);
  847.     }
  848. }
  849.  
  850.  
  851. static void
  852. iscissors_draw_curve (GDisplay  *gdisp,
  853.               Iscissors *iscissors,
  854.               ICurve    *curve)
  855. {
  856.   gpointer *point;
  857.   guint     len;
  858.   gint      tx, ty;
  859.   gint      npts;
  860.   guint32   coords;
  861.  
  862.   /* Uh, this shouldn't happen, but it does.  So we ignore it.
  863.    * Quality code, baby. */
  864.   if (!curve->points)
  865.       return;
  866.  
  867.   npts = 0;
  868.   point = curve->points->pdata;
  869.   len = curve->points->len;
  870.   while (len--)
  871.     {
  872.       coords = GPOINTER_TO_INT (*point);
  873.       point++;
  874.       gdisplay_transform_coords (gdisp, (coords & 0x0000ffff), 
  875.                  (coords >> 16), &tx, &ty, FALSE);
  876.       if (npts < MAX_POINTS)
  877.     {
  878.       curve_points [npts].x = tx;
  879.       curve_points [npts].y = ty;
  880.       npts ++;
  881.     }
  882.       else
  883.     {
  884.       g_warning ("too many points in ICurve segment!");
  885.       return;
  886.     }
  887.     }
  888.  
  889.   /*  draw the curve */
  890.   gdk_draw_lines (iscissors->core->win, iscissors->core->gc,
  891.           curve_points, npts);
  892. }
  893.  
  894. static void
  895. iscissors_oper_update (Tool           *tool,
  896.                GdkEventMotion *mevent,
  897.                gpointer        gdisp_ptr)
  898. {
  899.   Iscissors *iscissors;
  900.   GDisplay  *gdisp;
  901.   gint       x, y;
  902.  
  903.   iscissors = (Iscissors *) tool->private;
  904.   gdisp = (GDisplay *) gdisp_ptr;
  905.  
  906.   gdisplay_untransform_coords (gdisp, mevent->x, mevent->y,
  907.                    &x, &y, FALSE, FALSE);
  908.  
  909.   if (mouse_over_vertex (iscissors, x, y))
  910.     {
  911.       iscissors->op = SELECTION_MOVE_MASK; /* abused */
  912.     }
  913.   else if (mouse_over_curve (iscissors, x, y))
  914.     {
  915.       iscissors->op = SELECTION_MOVE; /* abused */
  916.     }
  917.   else if (iscissors->connected && iscissors->mask &&
  918.        channel_value (iscissors->mask, x, y))
  919.     {
  920.       if (mevent->state & GDK_SHIFT_MASK &&
  921.       mevent->state & GDK_CONTROL_MASK)
  922.     {
  923.       iscissors->op = SELECTION_INTERSECT;
  924.     }
  925.       else if (mevent->state & GDK_SHIFT_MASK)
  926.     {
  927.       iscissors->op = SELECTION_ADD;
  928.     }
  929.       else if (mevent->state & GDK_CONTROL_MASK)
  930.     {
  931.       iscissors->op = SELECTION_SUB;
  932.     }
  933.       else
  934.     {
  935.       iscissors->op = SELECTION_REPLACE;
  936.     }
  937.     }
  938.   else if (iscissors->connected && iscissors->mask)
  939.     {
  940.       iscissors->op = -1;
  941.     }
  942.   else
  943.     {
  944.       iscissors->op = -2;
  945.     }
  946. }
  947.  
  948. static void
  949. iscissors_modifier_update (Tool        *tool,
  950.                GdkEventKey *kevent,
  951.                gpointer     gdisp_ptr)
  952. {
  953.   Iscissors *iscissors;
  954.   SelectOps  op;
  955.  
  956.   iscissors = (Iscissors *) tool->private;
  957.  
  958.   op = iscissors->op;
  959.  
  960.   if (op == -2)
  961.     return;
  962.  
  963.   switch (kevent->keyval)
  964.     {
  965.     case GDK_Shift_L: case GDK_Shift_R:
  966.       if (op == SELECTION_REPLACE)
  967.     op = SELECTION_ADD;
  968.       else if (op == SELECTION_ADD)
  969.     op = SELECTION_REPLACE;
  970.       else if (op == SELECTION_SUB)
  971.     op = SELECTION_INTERSECT;
  972.       else if (op == SELECTION_INTERSECT)
  973.     op = SELECTION_SUB;
  974.       break;
  975.  
  976.     case GDK_Control_L: case GDK_Control_R:
  977.       if (op == SELECTION_REPLACE)
  978.     op = SELECTION_SUB;
  979.       else if (op == SELECTION_ADD)
  980.     op = SELECTION_INTERSECT;
  981.       else if (op == SELECTION_SUB)
  982.     op = SELECTION_REPLACE;
  983.       else if (op == SELECTION_INTERSECT)
  984.     op = SELECTION_ADD;
  985.       break;
  986.     }
  987.  
  988.   iscissors->op = op;
  989. }
  990.  
  991. static void
  992. iscissors_cursor_update (Tool           *tool,
  993.              GdkEventMotion *mevent,
  994.              gpointer        gdisp_ptr)
  995. {
  996.   Iscissors *iscissors;
  997.   GDisplay *gdisp;
  998.  
  999.   iscissors = (Iscissors *) tool->private;
  1000.   gdisp = (GDisplay *) gdisp_ptr;
  1001.  
  1002.   switch (iscissors->op)
  1003.     {
  1004.     case SELECTION_REPLACE:
  1005.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1006.                     RECT_SELECT,
  1007.                     CURSOR_MODIFIER_NONE,
  1008.                     FALSE);
  1009.       break;
  1010.     case SELECTION_ADD:
  1011.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1012.                     RECT_SELECT,
  1013.                     CURSOR_MODIFIER_PLUS,
  1014.                     FALSE);
  1015.       break;
  1016.     case SELECTION_SUB:
  1017.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1018.                     RECT_SELECT,
  1019.                     CURSOR_MODIFIER_MINUS,
  1020.                     FALSE);
  1021.       break;
  1022.     case SELECTION_INTERSECT:
  1023.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1024.                     RECT_SELECT,
  1025.                     CURSOR_MODIFIER_INTERSECT,
  1026.                     FALSE);
  1027.       break;
  1028.     case SELECTION_MOVE_MASK: /* abused */
  1029.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1030.                     ISCISSORS,
  1031.                     CURSOR_MODIFIER_MOVE,
  1032.                     FALSE);
  1033.       break;
  1034.     case SELECTION_MOVE: /* abused */
  1035.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1036.                     ISCISSORS,
  1037.                     CURSOR_MODIFIER_PLUS,
  1038.                     FALSE);
  1039.       break;
  1040.     case -1:
  1041.       gdisplay_install_tool_cursor (gdisp, GIMP_BAD_CURSOR,
  1042.                     ISCISSORS,
  1043.                     CURSOR_MODIFIER_NONE,
  1044.                     FALSE);
  1045.       break;
  1046.     default:
  1047.       switch (iscissors->state)
  1048.     {
  1049.     case WAITING:
  1050.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1051.                     ISCISSORS,
  1052.                     CURSOR_MODIFIER_PLUS,
  1053.                     FALSE);
  1054.       break;
  1055.     case SEED_PLACEMENT:
  1056.     case SEED_ADJUSTMENT:
  1057.     default:
  1058.       gdisplay_install_tool_cursor (gdisp, GIMP_MOUSE_CURSOR,
  1059.                     ISCISSORS,
  1060.                     CURSOR_MODIFIER_NONE,
  1061.                     FALSE);
  1062.       break;
  1063.     }
  1064.     }
  1065. }
  1066.  
  1067. static void
  1068. iscissors_control (Tool       *tool,
  1069.            ToolAction  action,
  1070.            gpointer    gdisp_ptr)
  1071. {
  1072.   Iscissors * iscissors;
  1073.   Iscissors_draw draw;
  1074.  
  1075.   iscissors = (Iscissors *) tool->private;
  1076.  
  1077.   switch (iscissors->state)
  1078.     {
  1079.     case SEED_PLACEMENT:
  1080.       draw = DRAW_CURVE | DRAW_CURRENT_SEED;
  1081.       break;
  1082.  
  1083.     case SEED_ADJUSTMENT:
  1084.       draw = DRAW_CURVE | DRAW_ACTIVE_CURVE;
  1085.       break;
  1086.  
  1087.     default:
  1088.       draw = DRAW_CURVE;
  1089.       break;
  1090.     }
  1091.  
  1092.   iscissors->draw = draw;
  1093.   switch (action)
  1094.     {
  1095.     case PAUSE: 
  1096.       draw_core_pause (iscissors->core, tool);
  1097.       break;
  1098.  
  1099.     case RESUME:
  1100.       draw_core_resume (iscissors->core, tool);
  1101.       break;
  1102.  
  1103.     case HALT:
  1104.       draw_core_stop (iscissors->core, tool);
  1105.       iscissors_reset (iscissors);
  1106.       break;
  1107.  
  1108.     default:
  1109.       break;
  1110.     }
  1111. }
  1112.  
  1113.  
  1114. static void
  1115. iscissors_reset (Iscissors *iscissors)
  1116. {
  1117.   TRC( ("iscissors_reset\n"));
  1118.  
  1119.   /*  Free and reset the curve list  */
  1120.   if (iscissors->curves)
  1121.     {
  1122.       iscissors_free_icurves (iscissors->curves);
  1123.       TRC (("g_slist_free (iscissors->curves);\n"));
  1124.       g_slist_free (iscissors->curves);
  1125.       iscissors->curves = NULL;
  1126.     }
  1127.  
  1128.   /*  free mask  */
  1129.   if (iscissors->mask)
  1130.     channel_delete (iscissors->mask);
  1131.   iscissors->mask = NULL;
  1132.  
  1133.   /* free the gradient map */
  1134.   if (iscissors->gradient_map)
  1135.     {
  1136.       /* release any tile we were using */
  1137.       if (cur_tile)
  1138.       {
  1139.     TRC (("tile_release\n"));
  1140.     tile_release (cur_tile, FALSE);
  1141.       }
  1142.       cur_tile = NULL;
  1143.  
  1144.       TRC (("tile_manager_destroy (iscissors->gradient_map);\n"));
  1145.       tile_manager_destroy (iscissors->gradient_map);
  1146.       iscissors->gradient_map = NULL;
  1147.     }
  1148.  
  1149.   iscissors->curve1 = NULL;
  1150.   iscissors->curve2 = NULL;
  1151.   iscissors->first_point = TRUE;
  1152.   iscissors->connected = FALSE;
  1153.   iscissors->state = NO_ACTION;
  1154.  
  1155.   /*  Reset the dp buffers  */
  1156.   iscissors_free_buffers (iscissors);
  1157.  
  1158.   /*  If they haven't already been initialized, precalculate the diagonal
  1159.    *  weight and direction value arrays
  1160.    */
  1161.   if (!initialized)
  1162.     {
  1163.       precalculate_arrays ();
  1164.       initialized = TRUE;
  1165.     }
  1166. }
  1167.  
  1168.  
  1169. static void
  1170. iscissors_free_icurves (GSList *list)
  1171. {
  1172.   ICurve * curve;
  1173.  
  1174.   TRC (("iscissors_free_icurves\n"));
  1175.  
  1176.   while (list)
  1177.     {
  1178.       curve = (ICurve *) list->data;
  1179.       if (curve->points)
  1180.     {
  1181.       TRC (("g_ptr_array_free (curve->points);\n"));
  1182.       g_ptr_array_free (curve->points, TRUE);
  1183.     }
  1184.       TRC (("g_free (curve);\n"));
  1185.       g_free (curve);
  1186.       list = g_slist_next (list);
  1187.     }
  1188. }
  1189.  
  1190.  
  1191. static void
  1192. iscissors_free_buffers (Iscissors *iscissors)
  1193. {
  1194.   if (iscissors->dp_buf)
  1195.     temp_buf_free (iscissors->dp_buf);
  1196.  
  1197.   iscissors->dp_buf = NULL;
  1198. }
  1199.  
  1200.  
  1201. /* XXX need some scan-conversion routines from somewhere.  maybe. ? */
  1202.  
  1203. static gint
  1204. mouse_over_vertex (Iscissors *iscissors,
  1205.            gint       x,
  1206.            gint       y)
  1207. {
  1208.   GSList *list;
  1209.   ICurve *curve;
  1210.   gint curves_found = 0;
  1211.  
  1212.   /*  traverse through the list, returning non-zero if the current cursor
  1213.    *  position is on an existing curve vertex.  Set the curve1 and curve2
  1214.    *  variables to the two curves containing the vertex in question
  1215.    */
  1216.  
  1217.   iscissors->curve1 = iscissors->curve2 = NULL;
  1218.  
  1219.   list = iscissors->curves;
  1220.  
  1221.   while (list && curves_found < 2)
  1222.     {
  1223.       curve = (ICurve *) list->data;
  1224.  
  1225.       if (abs (curve->x1 - x) < POINT_HALFWIDTH &&
  1226.       abs (curve->y1 - y) < POINT_HALFWIDTH)
  1227.     {
  1228.       iscissors->curve1 = curve;
  1229.       if (curves_found++)
  1230.         return curves_found;
  1231.     }
  1232.       else if (abs (curve->x2 - x) < POINT_HALFWIDTH &&
  1233.            abs (curve->y2 - y) < POINT_HALFWIDTH)
  1234.     {
  1235.       iscissors->curve2 = curve;
  1236.       if (curves_found++)
  1237.         return curves_found;
  1238.     }
  1239.  
  1240.       list = g_slist_next (list);
  1241.     }
  1242.  
  1243.   return curves_found;
  1244. }
  1245.  
  1246. static gboolean
  1247. clicked_on_vertex (Tool *tool)
  1248. {
  1249.   Iscissors *iscissors;
  1250.   gint curves_found = 0;
  1251.  
  1252.   iscissors = (Iscissors *) tool->private;
  1253.  
  1254.   curves_found = mouse_over_vertex (iscissors, iscissors->x, iscissors->y);
  1255.  
  1256.   if (curves_found > 1)
  1257.     return TRUE;
  1258.  
  1259.   /*  if only one curve was found, the curves are unconnected, and
  1260.    *  the user only wants to move either the first or last point
  1261.    *  disallow this for now.
  1262.    */
  1263.   if (curves_found == 1)
  1264.     return FALSE;
  1265.  
  1266.   /*  no vertices were found at the cursor click point.  Now check whether
  1267.    *  the click occured on a curve.  If so, create a new vertex there and
  1268.    *  two curve segments to replace what used to be just one...
  1269.    */
  1270.   return clicked_on_curve (tool);
  1271. }
  1272.  
  1273.  
  1274. static GSList *
  1275. mouse_over_curve (Iscissors *iscissors,
  1276.           gint       x,
  1277.           gint       y)
  1278. {
  1279.   GSList   *list;
  1280.   gpointer *pt;
  1281.   gint      len;
  1282.   ICurve   *curve;
  1283.   guint32   coords;
  1284.   gint      tx, ty;
  1285.  
  1286.   /*  traverse through the list, returning the curve segment's list element
  1287.    *  if the current cursor position is on a curve... 
  1288.    */
  1289.  
  1290.   for (list = iscissors->curves; list; list = g_slist_next (list))
  1291.     {
  1292.       curve = (ICurve *) list->data;
  1293.  
  1294.       pt = curve->points->pdata;
  1295.       len = curve->points->len;
  1296.       while (len--)
  1297.     {
  1298.       coords = GPOINTER_TO_INT (*pt);
  1299.       pt++;
  1300.       tx = coords & 0x0000ffff;
  1301.       ty = coords >> 16;
  1302.  
  1303.       /*  Is the specified point close enough to the curve?  */
  1304.       if (abs (tx - x) < POINT_HALFWIDTH &&
  1305.           abs (ty - y) < POINT_HALFWIDTH)
  1306.         {
  1307.           return list;
  1308.         }
  1309.     }
  1310.     }
  1311.  
  1312.   return NULL;
  1313. }
  1314.  
  1315. static gboolean
  1316. clicked_on_curve (Tool *tool)
  1317. {
  1318.   Iscissors *iscissors;
  1319.   GSList    *list, *new_link;
  1320.   ICurve    *curve, *new_curve;
  1321.  
  1322.   iscissors = (Iscissors *) tool->private;
  1323.  
  1324.   /*  traverse through the list, getting back the curve segment's list
  1325.    *  element if the current cursor position is on a curve...
  1326.    *  If this occurs, replace the curve with two new curves,
  1327.    *  separated by a new vertex.
  1328.    */
  1329.   list = mouse_over_curve (iscissors, iscissors->x, iscissors->y);
  1330.  
  1331.   if (list)
  1332.     {
  1333.       curve = (ICurve *) list->data;
  1334.  
  1335.       /*  Since we're modifying the curve, undraw the existing one  */
  1336.       iscissors->draw = DRAW_CURVE;
  1337.       draw_core_pause (iscissors->core, tool);
  1338.  
  1339.       /*  Create the new curve  */
  1340.       new_curve = g_new (ICurve, 1);
  1341.  
  1342.       new_curve->x2 = curve->x2;
  1343.       new_curve->y2 = curve->y2;
  1344.       new_curve->x1 = curve->x2 = iscissors->x;
  1345.       new_curve->y1 = curve->y2 = iscissors->y;
  1346.       new_curve->points = NULL;
  1347.  
  1348.       /*  Create the new link and supply the new curve as data  */
  1349.       new_link = g_slist_alloc ();
  1350.       new_link->data = (void *) new_curve;
  1351.  
  1352.       /*  Insert the new link in the list  */
  1353.       new_link->next = list->next;
  1354.       list->next = new_link;
  1355.  
  1356.       iscissors->curve1 = new_curve;
  1357.       iscissors->curve2 = curve;
  1358.  
  1359.       /*  Redraw the curve  */
  1360.       draw_core_resume (iscissors->core, tool);
  1361.  
  1362.       return TRUE;
  1363.     }
  1364.  
  1365.   return FALSE;
  1366. }
  1367.  
  1368.  
  1369. static void
  1370. precalculate_arrays (void)
  1371. {
  1372.   gint i;
  1373.  
  1374.   for (i = 0; i < 256; i++)
  1375.     {
  1376.       /*  The diagonal weight array  */
  1377.       diagonal_weight [i] = (int) (i * G_SQRT2);
  1378.  
  1379.       /*  The direction value array  */
  1380.       direction_value [i][0] = (127 - abs (127 - i)) * 2;
  1381.       direction_value [i][1] = abs (127 - i) * 2;
  1382.       direction_value [i][2] = abs (191 - i) * 2;
  1383.       direction_value [i][3] = abs (63 - i) * 2;
  1384.  
  1385.       TRC (("i: %d, v0: %d, v1: %d, v2: %d, v3: %d\n", i,
  1386.         direction_value [i][0],
  1387.         direction_value [i][1],
  1388.         direction_value [i][2],
  1389.         direction_value [i][3]));
  1390.     }
  1391.  
  1392.   /*  set the 256th index of the direction_values to the hightest cost  */
  1393.   direction_value [255][0] = 255;
  1394.   direction_value [255][1] = 255;
  1395.   direction_value [255][2] = 255;
  1396.   direction_value [255][3] = 255;
  1397. }
  1398.  
  1399.  
  1400. static void
  1401. calculate_curve (Tool   *tool,
  1402.          ICurve *curve)
  1403. {
  1404.   GDisplay  *gdisp;
  1405.   Iscissors *iscissors;
  1406.   gint x, y, dir;
  1407.   gint xs, ys, xe, ye;
  1408.   gint x1, y1, x2, y2;
  1409.   gint width, height;
  1410.   gint ewidth, eheight;
  1411.  
  1412.   TRC (("calculate_curve(%p, %p)\n", tool, curve));
  1413.  
  1414.   /*  Calculate the lowest cost path from one vertex to the next as specified
  1415.    *  by the parameter "curve".
  1416.    *    Here are the steps:
  1417.    *      1)  Calculate the appropriate working area for this operation
  1418.    *      2)  Allocate a temp buf for the dynamic programming array
  1419.    *      3)  Run the dynamic programming algorithm to find the optimal path
  1420.    *      4)  Translate the optimal path into pixels in the icurve data
  1421.    *            structure.
  1422.    */
  1423.  
  1424.   gdisp = (GDisplay *) tool->gdisp_ptr;
  1425.   iscissors = (Iscissors *) tool->private;
  1426.  
  1427.   /*  Get the bounding box  */
  1428.   xs = CLAMP (curve->x1, 0, gdisp->gimage->width - 1);
  1429.   ys = CLAMP (curve->y1, 0, gdisp->gimage->height - 1);
  1430.   xe = CLAMP (curve->x2, 0, gdisp->gimage->width - 1);
  1431.   ye = CLAMP (curve->y2, 0, gdisp->gimage->height - 1);
  1432.   x1 = MIN (xs, xe);
  1433.   y1 = MIN (ys, ye);
  1434.   x2 = MAX (xs, xe) + 1;  /*  +1 because if xe = 199 & xs = 0, x2 - x1, width = 200  */
  1435.   y2 = MAX (ys, ye) + 1;
  1436.  
  1437.   /*  expand the boundaries past the ending points by 
  1438.    *  some percentage of width and height.  This serves the following purpose:
  1439.    *  It gives the algorithm more area to search so better solutions
  1440.    *  are found.  This is particularly helpful in finding "bumps" which
  1441.    *  fall outside the bounding box represented by the start and end
  1442.    *  coordinates of the "curve".
  1443.    */
  1444.   ewidth = (x2 - x1) * EXTEND_BY + FIXED;
  1445.   eheight = (y2 - y1) * EXTEND_BY + FIXED;
  1446.  
  1447.   if (xe >= xs)
  1448.     x2 += CLAMP (ewidth, 0, gdisp->gimage->width - x2);
  1449.   else
  1450.     x1 -= CLAMP (ewidth, 0, x1);
  1451.   if (ye >= ys)
  1452.     y2 += CLAMP (eheight, 0, gdisp->gimage->height - y2);
  1453.   else
  1454.     y1 -= CLAMP (eheight, 0, y1);
  1455.  
  1456.   /* blow away any previous points list we might have */
  1457.   if (curve->points)
  1458.     {
  1459.       TRC (("1229: g_ptr_array_free (curve->points);\n"));
  1460.       g_ptr_array_free (curve->points, TRUE);
  1461.       curve->points = NULL;
  1462.     }
  1463.  
  1464.   /*  If the bounding box has width and height...  */
  1465.   if ((x2 - x1) && (y2 - y1))
  1466.     {
  1467.       width = (x2 - x1);
  1468.       height = (y2 - y1);
  1469.  
  1470.       /* Initialise the gradient map tile manager for this image if we
  1471.        * don't already have one. */
  1472.       if (!iscissors->gradient_map)
  1473.       iscissors->gradient_map = gradient_map_new (gdisp->gimage);
  1474.  
  1475.       TRC (("dp buf resize\n"));
  1476.       /*  allocate the dynamic programming array  */
  1477.       iscissors->dp_buf = 
  1478.     temp_buf_resize (iscissors->dp_buf, 4, x1, y1, width, height);
  1479.  
  1480.       TRC (("find_optimal_path\n"));
  1481.       /*  find the optimal path of pixels from (x1, y1) to (x2, y2)  */
  1482.       find_optimal_path (iscissors->gradient_map, iscissors->dp_buf,
  1483.              x1, y1, x2, y2, xs, ys);
  1484.       
  1485.       /*  get a list of the pixels in the optimal path  */
  1486.       TRC (("plot_pixels\n"));
  1487.       curve->points = plot_pixels (iscissors, iscissors->dp_buf,
  1488.                    x1, y1, xs, ys, xe, ye);
  1489.     }
  1490.   /*  If the bounding box has no width  */
  1491.   else if ((x2 - x1) == 0)
  1492.     {
  1493.       /*  plot a vertical line  */
  1494.       y = ys;  
  1495.       dir = (ys > ye) ? -1 : 1;
  1496.       curve->points = g_ptr_array_new ();
  1497.       while (y != ye)
  1498.     {
  1499.       g_ptr_array_add (curve->points, GINT_TO_POINTER ((y << 16) + xs));
  1500.       y += dir;
  1501.     }
  1502.     }
  1503.   /*  If the bounding box has no height  */
  1504.   else if ((y2 - y1) == 0)
  1505.     {
  1506.       /*  plot a horizontal line  */
  1507.       x = xs;
  1508.       dir = (xs > xe) ? -1 : 1;
  1509.       curve->points = g_ptr_array_new ();
  1510.       while (x != xe)
  1511.     {
  1512.       g_ptr_array_add (curve->points, GINT_TO_POINTER ((ys << 16) + x));
  1513.       x += dir;
  1514.     }
  1515.     }
  1516. }
  1517.  
  1518.  
  1519. /* badly need to get a replacement - this is _way_ too expensive */
  1520. static gboolean
  1521. gradient_map_value (TileManager *map,
  1522.             gint         x,
  1523.             gint         y,
  1524.             guint8      *grad,
  1525.             guint8      *dir)
  1526. {
  1527.   static int cur_tilex;
  1528.   static int cur_tiley;
  1529.   guint8 *p;
  1530.  
  1531.   if (!cur_tile ||
  1532.       x / TILE_WIDTH != cur_tilex ||
  1533.       y / TILE_HEIGHT != cur_tiley)
  1534.     {
  1535.       if (cur_tile)
  1536.     tile_release (cur_tile, FALSE);
  1537.       cur_tile = tile_manager_get_tile (map, x, y, TRUE, FALSE);
  1538.       if (!cur_tile)
  1539.     return FALSE;
  1540.       cur_tilex = x / TILE_WIDTH;
  1541.       cur_tiley = y / TILE_HEIGHT;    
  1542.     }
  1543.  
  1544.   p = tile_data_pointer (cur_tile, x % TILE_WIDTH, y % TILE_HEIGHT);
  1545.   *grad = p[0];
  1546.   *dir  = p[1];
  1547.  
  1548.   return TRUE;
  1549. }
  1550.  
  1551. static gint
  1552. calculate_link (TileManager *gradient_map,
  1553.         gint         x,
  1554.         gint         y,
  1555.         guint32      pixel,
  1556.         gint         link)
  1557. {
  1558.   gint value = 0;
  1559.   guint8 grad1, dir1, grad2, dir2;
  1560.  
  1561.   if (!gradient_map_value (gradient_map, x, y, &grad1, &dir1))
  1562.     {
  1563.       grad1 = 0;
  1564.       dir1 = 255;
  1565.     }
  1566.  
  1567.   /* Convert the gradient into a cost: large gradients are good, and
  1568.    * so have low cost. */
  1569.   grad1 = 255 - grad1;
  1570.  
  1571.   /*  calculate the contribution of the gradient magnitude  */
  1572.   if (link > 1)
  1573.     value += diagonal_weight [grad1] * OMEGA_G;
  1574.   else
  1575.     value += grad1 * OMEGA_G;
  1576.  
  1577.   /*  calculate the contribution of the gradient direction  */
  1578.   x += (gint8)(pixel & 0xff);
  1579.   y += (gint8)((pixel & 0xff00) >> 8);
  1580.   if (!gradient_map_value (gradient_map, x, y, &grad2, &dir2))
  1581.     {
  1582.       grad2 = 0;
  1583.       dir2 = 255;
  1584.     }  
  1585.   value += (direction_value [dir1][link] + direction_value [dir2][link]) *
  1586.     OMEGA_D;
  1587.  
  1588.   return value;
  1589. }
  1590.  
  1591.  
  1592. static GPtrArray *
  1593. plot_pixels (Iscissors *iscissors,
  1594.          TempBuf   *dp_buf,
  1595.          gint       x1,
  1596.          gint       y1,
  1597.          gint       xs,
  1598.          gint       ys,
  1599.          gint       xe,
  1600.          gint       ye)
  1601. {
  1602.   gint       x, y;
  1603.   guint32    coords;
  1604.   gint       link;
  1605.   gint       width;
  1606.   guint     *data;
  1607.   GPtrArray *list;
  1608.  
  1609.   width = dp_buf->width;
  1610.  
  1611.   /*  Start the data pointer at the correct location  */
  1612.   data = (guint *) temp_buf_data (dp_buf) + (ye - y1) * width + (xe - x1);
  1613.  
  1614.   x = xe;
  1615.   y = ye;
  1616.  
  1617.   list = g_ptr_array_new ();
  1618.  
  1619.   while (1)
  1620.     {
  1621.       coords = (y << 16) + x;
  1622.       g_ptr_array_add (list, GINT_TO_POINTER (coords));
  1623.  
  1624.       link = PIXEL_DIR (*data);
  1625.       if (link == SEED_POINT)
  1626.     return list;
  1627.  
  1628.       x += move [link][0];
  1629.       y += move [link][1];
  1630.       data += move [link][1] * width + move [link][0];
  1631.     }
  1632.  
  1633.   /*  won't get here  */
  1634.   return NULL;
  1635. }
  1636.  
  1637.  
  1638. #define PACK(x, y) ((((y) & 0xff) << 8) | ((x) & 0xff))
  1639. #define OFFSET(pixel) ((gint8)((pixel) & 0xff) + \
  1640.   ((gint8)(((pixel) & 0xff00) >> 8)) * dp_buf->width)
  1641.  
  1642.  
  1643. static void
  1644. find_optimal_path (TileManager *gradient_map,
  1645.            TempBuf     *dp_buf,
  1646.            gint         x1,
  1647.            gint         y1,
  1648.            gint         x2,
  1649.            gint         y2,
  1650.            gint         xs,
  1651.            gint         ys)
  1652. {
  1653.   gint i, j, k;
  1654.   gint x, y;
  1655.   gint link;
  1656.   gint linkdir;
  1657.   gint dirx, diry;
  1658.   gint min_cost;
  1659.   gint new_cost;
  1660.   gint offset;
  1661.   gint cum_cost [8];
  1662.   gint link_cost [8];
  1663.   gint pixel_cost [8];
  1664.   guint32 pixel [8];
  1665.   guint32 * data, *d;
  1666.  
  1667.   TRC (("find_optimal_path (%p, %p, [%d,%d-%d,%d] %d, %d)\n",
  1668.     gradient_map, dp_buf, x1, y1, x2, y2, xs, ys));
  1669.  
  1670.   /*  initialize the dynamic programming buffer  */
  1671.   data = (guint32 *) temp_buf_data (dp_buf);
  1672.   for (i = 0; i < dp_buf->height; i++)
  1673.     for (j = 0; j < dp_buf->width; j++)
  1674.       *data++ = 0;  /*  0 cumulative cost, 0 direction  */
  1675.  
  1676.   /*  what directions are we filling the array in according to?  */
  1677.   dirx = (xs - x1 == 0) ? 1 : -1;
  1678.   diry = (ys - y1 == 0) ? 1 : -1;
  1679.   linkdir = (dirx * diry);
  1680.  
  1681.   y = ys;
  1682.  
  1683.   /*  Start the data pointer at the correct location  */
  1684.   data = (guint32 *) temp_buf_data (dp_buf);
  1685.  
  1686.   TRC (("find_optimal_path: mainloop\n"));
  1687.  
  1688.   for (i = 0; i < dp_buf->height; i++)
  1689.     {
  1690.       x = xs;
  1691.  
  1692.       d = data + (y-y1) * dp_buf->width + (x-x1);
  1693.  
  1694.       for (j = 0; j < dp_buf->width; j++)
  1695.     {
  1696.       min_cost = G_MAXINT;
  1697.  
  1698.       /* pixel[] array encodes how to get to a neigbour, if possible.
  1699.        * 0 means no connection (eg edge).
  1700.        * Rest packed as bottom two bytes: y offset then x offset.
  1701.        * Initially, we assume we can't get anywhere. */
  1702.       for (k = 0; k < 8; k++)
  1703.         pixel [k] = 0;
  1704.  
  1705.       /*  Find the valid neighboring pixels  */
  1706.       /*  the previous pixel  */
  1707.       if (j)
  1708.         pixel [((dirx == 1) ? 4 : 0)] = PACK (-dirx, 0);
  1709.  
  1710.       /*  the previous row of pixels  */
  1711.       if (i)
  1712.         {
  1713.           pixel [((diry == 1) ? 5 : 1)] = PACK (0, -diry);
  1714.  
  1715.           link = (linkdir == 1) ? 3 : 2;
  1716.           if (j)
  1717.         pixel [((diry == 1) ? (link + 4) : link)] = PACK(-dirx, -diry);
  1718.  
  1719.           link = (linkdir == 1) ? 2 : 3;
  1720.           if (j != dp_buf->width - 1)
  1721.         pixel [((diry == 1) ? (link + 4) : link)] = PACK (dirx, -diry);
  1722.         }
  1723.  
  1724.       /*  find the minimum cost of going through each neighbor to reach the
  1725.        *  seed point...
  1726.        */
  1727.       link = -1;
  1728.       for (k = 0; k < 8; k ++)
  1729.         if (pixel [k])
  1730.           {
  1731.         link_cost [k] = calculate_link (gradient_map,
  1732.                         xs + j*dirx, ys + i*diry,
  1733.                         pixel [k],
  1734.                         ((k > 3) ? k - 4 : k));
  1735.         offset = OFFSET (pixel [k]);
  1736.         pixel_cost [k] = PIXEL_COST (d [offset]);
  1737.         cum_cost [k] = pixel_cost [k] + link_cost [k];
  1738.         if (cum_cost [k] < min_cost)
  1739.           {
  1740.             min_cost = cum_cost [k];
  1741.             link = k;
  1742.           }
  1743.           }
  1744.  
  1745.       /*  If anything can be done...  */
  1746.       if (link >= 0)
  1747.         {
  1748.           /*  set the cumulative cost of this pixel and the new direction  */
  1749.           *d = (cum_cost [link] << 8) + link;
  1750.  
  1751.           /*  possibly change the links from the other pixels to this pixel...
  1752.            *  these changes occur if a neighboring pixel will receive a lower
  1753.            *  cumulative cost by going through this pixel.  
  1754.            */
  1755.           for (k = 0; k < 8; k ++)
  1756.         if (pixel [k] && k != link)
  1757.           {
  1758.             /*  if the cumulative cost at the neighbor is greater than
  1759.              *  the cost through the link to the current pixel, change the
  1760.              *  neighbor's link to point to the current pixel.
  1761.              */
  1762.             new_cost = link_cost [k] + cum_cost [link];
  1763.             if (pixel_cost [k] > new_cost)
  1764.             {
  1765.               /*  reverse the link direction   /-----------------------\ */
  1766.               offset = OFFSET (pixel [k]);
  1767.               d [offset] = (new_cost << 8) + ((k > 3) ? k - 4 : k + 4);
  1768.             }
  1769.           }
  1770.         } 
  1771.       /*  Set the seed point  */
  1772.       else if (!i && !j)
  1773.         *d = SEED_POINT;
  1774.  
  1775.       /*  increment the data pointer and the x counter  */
  1776.       d += dirx;
  1777.       x += dirx;
  1778.     }
  1779.  
  1780.       /*  increment the y counter  */
  1781.       y += diry;
  1782.     }
  1783.  
  1784.   TRC (("done: find_optimal_path\n"));
  1785. }
  1786.  
  1787.  
  1788. /* Called to fill in a newly referenced tile in the gradient map */
  1789. static void
  1790. gradmap_tile_validate (TileManager *tm,
  1791.                Tile        *tile)
  1792. {
  1793.   static gboolean first_gradient = TRUE;
  1794.   gint    x, y;
  1795.   gint    dw, dh;
  1796.   gint    sw, sh;
  1797.   gint    i, j;
  1798.   gint    b;
  1799.   gfloat  gradient;
  1800.   guint8 *gradmap;
  1801.   guint8 *tiledata;
  1802.   guint8 *datah, *datav;
  1803.   gint8   hmax, vmax;
  1804.   Tile   *srctile;
  1805.   PixelRegion srcPR, destPR;
  1806.   GImage *gimage;
  1807.  
  1808.   gimage = (GImage *) tile_manager_get_user_data (tm);
  1809.  
  1810.   if (first_gradient)
  1811.     {
  1812.       gint radius = GRADIENT_SEARCH >> 1;
  1813.       /*  compute the distance weights  */
  1814.       for (i = 0; i < GRADIENT_SEARCH; i++)
  1815.     for (j = 0; j < GRADIENT_SEARCH; j++)
  1816.       distance_weights [i * GRADIENT_SEARCH + j] =
  1817.         1.0 / (1 + sqrt (SQR(i - radius) + SQR(j - radius)));
  1818.       first_gradient = FALSE;
  1819.     }
  1820.  
  1821.   tile_manager_get_tile_coordinates (tm, tile, &x, &y);
  1822.   dw = tile_ewidth (tile);
  1823.   dh = tile_eheight (tile);
  1824.  
  1825.   TRC (("fill req for tile %p @ (%d, %d)\n", tile, x, y));
  1826.  
  1827.   /* get corresponding tile in the gimage */
  1828.   srctile = tile_manager_get_tile (gimp_image_composite (gimage),
  1829.                    x, y, TRUE, FALSE);
  1830.   if (!srctile)
  1831.     {
  1832.       g_warning ("bad tile coords?");
  1833.       return;
  1834.     }
  1835.   sw = tile_ewidth (srctile);
  1836.   sh = tile_eheight (srctile);
  1837.  
  1838.   if (dw != sw || dh != sh)
  1839.     g_warning ("dw:%d sw:%d  dh:%d sh:%d\n", dw, sw, dh, sh);
  1840.  
  1841.   srcPR.w = MIN (dw, sw);
  1842.   srcPR.h = MIN (dh, sh);
  1843.   srcPR.bytes = gimp_image_composite_bytes (gimage);
  1844.   srcPR.data = tile_data_pointer (srctile, 0, 0);
  1845.   srcPR.rowstride = srcPR.w * srcPR.bytes;
  1846.  
  1847.   /* XXX tile edges? */
  1848.  
  1849.   /*  Blur the source to get rid of noise  */
  1850.   destPR.rowstride = TILE_WIDTH * 4;
  1851.   destPR.data = maxgrad_conv0;
  1852.   convolve_region (&srcPR, &destPR, blur_32, 3, 32, NORMAL_CONVOL);
  1853.  
  1854.   /*  Set the "src" temp buf up as the new source Pixel Region  */
  1855.   srcPR.rowstride = destPR.rowstride;
  1856.   srcPR.data = destPR.data;
  1857.  
  1858.   /*  Get the horizontal derivative  */
  1859.   destPR.data = maxgrad_conv1;
  1860.   convolve_region (&srcPR, &destPR, horz_deriv, 3, 1, NEGATIVE_CONVOL);
  1861.  
  1862.   /*  Get the vertical derivative  */
  1863.   destPR.data = maxgrad_conv2;
  1864.   convolve_region (&srcPR, &destPR, vert_deriv, 3, 1, NEGATIVE_CONVOL);
  1865.  
  1866.   /* calculate overall gradient */
  1867.   tiledata = tile_data_pointer (tile, 0, 0);
  1868.   for (i = 0; i < srcPR.h; i++)
  1869.     {
  1870.       datah = maxgrad_conv1 + srcPR.rowstride*i;
  1871.       datav = maxgrad_conv2 + srcPR.rowstride*i;
  1872.       gradmap = tiledata + tile_ewidth (tile) * COST_WIDTH * i;
  1873.  
  1874.       for (j = 0; j < srcPR.w; j++)
  1875.     {
  1876.       hmax = datah[0] - 128;
  1877.       vmax = datav[0] - 128;
  1878.       for (b = 1; b < srcPR.bytes; b++)
  1879.         {
  1880.           if (abs (datah[b] - 128) > abs (hmax)) hmax = datah[b] - 128;
  1881.           if (abs (datav[b] - 128) > abs (vmax)) vmax = datav[b] - 128;
  1882.         }
  1883.  
  1884.       if (i == 0 || j == 0 || i == srcPR.h-1 || j == srcPR.w-1)
  1885.       {
  1886.           gradmap[j*COST_WIDTH] = 0;
  1887.           gradmap[j*COST_WIDTH + 1] = 255;
  1888.           goto contin;
  1889.       }
  1890.  
  1891.       /* 1 byte absolute magitude first */
  1892.       gradient = sqrt(SQR(hmax) + SQR(vmax));
  1893.       gradmap[j*COST_WIDTH] = gradient * 255 / MAX_GRADIENT;
  1894.  
  1895.       /* then 1 byte direction */
  1896.       if (gradient > MIN_GRADIENT)
  1897.         {
  1898.           gfloat direction;
  1899.           if (!hmax)
  1900.         direction = (vmax > 0) ? G_PI_2 : -G_PI_2;
  1901.           else
  1902.         direction = atan ((double) vmax / (double) hmax);
  1903.           /* Scale the direction from between 0 and 254,
  1904.            *  corresponding to -PI/2, PI/2 255 is reserved for
  1905.            *  directionless pixels */
  1906.           gradmap[j*COST_WIDTH + 1] =
  1907.         (guint8) (254 * (direction + G_PI_2) / G_PI);
  1908.         }
  1909.       else
  1910.         gradmap[j*COST_WIDTH + 1] = 255; /* reserved for weak gradient */
  1911.  
  1912.     contin:
  1913.       {
  1914. #ifdef DEBUG
  1915.         int g = gradmap[j*COST_WIDTH];
  1916.         int d = gradmap[j*COST_WIDTH + 1];
  1917.         TRC (("%c%c", 'a' + (g * 25 / 255), '0' + (d / 25)));
  1918. #endif /* DEBUG */
  1919.       }
  1920.  
  1921.       datah += srcPR.bytes;
  1922.       datav += srcPR.bytes;
  1923.     }
  1924.       TRC (("\n"));
  1925.     }
  1926.   TRC (("\n"));
  1927.  
  1928.   tile_release (srctile, FALSE);
  1929. }
  1930.  
  1931. static TileManager *
  1932. gradient_map_new (GImage *gimage)
  1933. {
  1934.   TileManager *tm;
  1935.  
  1936.   tm = tile_manager_new (gimage->width, gimage->height,
  1937.              sizeof (guint8) * COST_WIDTH);
  1938.   tile_manager_set_user_data (tm, gimage);
  1939.   tile_manager_set_validate_proc (tm, gradmap_tile_validate);
  1940.  
  1941.   return tm;
  1942. }
  1943.  
  1944. static void
  1945. find_max_gradient (Iscissors *iscissors,
  1946.            GImage    *gimage,
  1947.            gint      *x,
  1948.            gint      *y)
  1949. {
  1950.   PixelRegion srcPR;
  1951.   gint    radius;
  1952.   gint    i, j;
  1953.   gint    endx, endy;
  1954.   gint    sx, sy, cx, cy;
  1955.   gint    x1, y1, x2, y2;
  1956.   void   *pr;
  1957.   guint8 *gradient;
  1958.   gfloat  g, max_gradient;
  1959.  
  1960.   TRC (("find_max_gradient(%d, %d)\n", *x, *y));
  1961.  
  1962.   /* Initialise the gradient map tile manager for this image if we
  1963.    * don't already have one. */
  1964.   if (!iscissors->gradient_map)
  1965.     iscissors->gradient_map = gradient_map_new (gimage);
  1966.  
  1967.   radius = GRADIENT_SEARCH >> 1;
  1968.  
  1969.   /*  calculate the extent of the search  */
  1970.   cx = CLAMP (*x, 0, gimage->width);
  1971.   cy = CLAMP (*y, 0, gimage->height);
  1972.   sx = cx - radius;
  1973.   sy = cy - radius;
  1974.   x1 = CLAMP (cx - radius, 0, gimage->width);
  1975.   y1 = CLAMP (cy - radius, 0, gimage->height);
  1976.   x2 = CLAMP (cx + radius, 0, gimage->width);
  1977.   y2 = CLAMP (cy + radius, 0, gimage->height);
  1978.   /*  calculate the factor to multiply the distance from the cursor by  */
  1979.  
  1980.   max_gradient = 0;
  1981.   *x = cx;
  1982.   *y = cy;
  1983.  
  1984.   /*  Find the point of max gradient  */
  1985.   pixel_region_init (&srcPR, iscissors->gradient_map,
  1986.              x1, y1, x2 - x1, y2 - y1, FALSE);
  1987.  
  1988.   /* this iterates over 1, 2 or 4 tiles only */
  1989.   for (pr = pixel_regions_register (1, &srcPR);
  1990.        pr != NULL;
  1991.        pr = pixel_regions_process (pr))
  1992.     {
  1993.       endx = srcPR.x + srcPR.w;
  1994.       endy = srcPR.y + srcPR.h;
  1995.       for (i = srcPR.y; i < endy; i++)
  1996.     {
  1997.       gradient = srcPR.data + srcPR.rowstride * (i - srcPR.y);
  1998.       for (j = srcPR.x; j < endx; j++)
  1999.         {
  2000.           g = *gradient;
  2001.           gradient += COST_WIDTH;
  2002.           g *= distance_weights [(i-y1) * GRADIENT_SEARCH + (j-x1)];
  2003.           if (g > max_gradient)
  2004.         {
  2005.           max_gradient = g;
  2006.           *x = j;
  2007.           *y = i;
  2008.         }
  2009.         }
  2010.     }
  2011.     }
  2012.  
  2013.   TRC (("done: find_max_gradient(%d, %d)\n", *x, *y));
  2014. }
  2015.  
  2016. /* End of iscissors.c */
  2017.