path: root/converter/other/pamtosvg/pxl-outline.c

/* pxl-outline.c: find the outlines of a bitmap image; each outline is
   made up of one or more pixels; and each pixel participates via one
   or more edges.
*/

#include <assert.h>

#include "mallocvar.h"

#include "message.h"
#include "bitmap.h"
#include "bitmap.h"
#include "logreport.h"
#include "pxl-outline.h"

/* We consider each pixel to consist of four edges, and we travel along
   edges, instead of through pixel centers.  This is necessary for those
   unfortunate times when a single pixel is on both an inside and an
   outside outline.

   The numbers chosen here are not arbitrary; the code that figures out
   which edge to move to depends on particular values.  See the
   `TRY_PIXEL' macro in `edge.c'.  To emphasize this, I've written in the
   numbers we need for each edge value.  */

typedef enum
  {
    TOP = 1, LEFT = 2, BOTTOM = 3, RIGHT = 0, NO_EDGE = 4
  } edge_type;

/* This choice is also not arbitrary: starting at the top edge makes the
   code find outside outlines before inside ones, which is certainly
   what we want.  */
#define START_EDGE  top

typedef enum
  {
    NORTH = 0, NORTHWEST = 1, WEST = 2, SOUTHWEST = 3, SOUTH = 4,
    SOUTHEAST = 5, EAST = 6, NORTHEAST = 7
  } direction_type;

#define NUM_EDGES NO_EDGE

#define COMPUTE_DELTA(axis, dir)                        \
  ((dir) % 2 != 0                                       \
    ? COMPUTE_##axis##_DELTA ((dir) - 1)                \
      + COMPUTE_##axis##_DELTA (((dir) + 1) % 8)        \
    : COMPUTE_##axis##_DELTA (dir)                      \
  )

#define COMPUTE_ROW_DELTA(dir)                          \
  ((dir) == NORTH ? -1 : (dir) == SOUTH ? +1 : 0)

#define COMPUTE_COL_DELTA(dir)                  \
  ((dir) == WEST ? -1 : (dir) == EAST ? +1 : 0)

static void append_pixel_outline (pixel_outline_list_type *,
                                  pixel_outline_type);
static pixel_outline_type new_pixel_outline (void);
static void free_pixel_outline (pixel_outline_type *);
static void concat_pixel_outline (pixel_outline_type *,
                                  const pixel_outline_type*);
static bool is_marked_edge (edge_type, unsigned short, unsigned short, bitmap_type);

static void
mark_edge (edge_type e, unsigned short, unsigned short, bitmap_type *);

static bool is_marked_dir(unsigned short, unsigned short, direction_type, bitmap_type);
static bool is_other_dir_marked(unsigned short, unsigned short, direction_type, bitmap_type);
static void mark_dir(unsigned short, unsigned short, direction_type, bitmap_type *);

static unsigned
num_neighbors(unsigned short, unsigned short, bitmap_type);

#define CHECK_FATAL() if (at_exception_got_fatal(exp)) goto cleanup;
#define RETURN_IF_FATAL() if (at_exception_got_fatal(exp)) return;




static pixel
getBitmapColor(bitmap_type  const bitmap,
               unsigned int const row,
               unsigned int const col) {

    unsigned char * const p = BITMAP_PIXEL(bitmap, row, col);

    pixel pix;
  
    if (bitmap.np >= 3)
        PPM_ASSIGN(pix, p[0], p[1], p[2]);
    else
        PPM_ASSIGN(pix, p[0], p[0], p[0]);

    return pix;
}




static void
append_outline_pixel(pixel_outline_type * const pixelOutlineP,
                     pm_pixelcoord        const coord) {
/*----------------------------------------------------------------------------
  Add a point to the pixel list.
-----------------------------------------------------------------------------*/

    O_LENGTH(*pixelOutlineP)++;
    REALLOCARRAY_NOFAIL(pixelOutlineP->data, O_LENGTH(*pixelOutlineP));

    O_COORDINATE(*pixelOutlineP, O_LENGTH(*pixelOutlineP) - 1) = coord;
}



/* We check to see if the edge of the pixel at position ROW and COL
   is an outline edge */

static bool
is_outline_edge (edge_type edge, bitmap_type bitmap,
                 unsigned short row, unsigned short col, pixel color,
                 at_exception_type * exp)
{
  /* If this pixel isn't of the same color, it's not part of the outline. */
  if (!PPM_EQUAL (getBitmapColor (bitmap, row, col), color))
    return false;

  switch (edge)
    {
    case LEFT:
      return (bool)
          (col == 0 ||
           !PPM_EQUAL (getBitmapColor (bitmap, row, col - 1), color));

    case TOP:
      return (bool)
          (row == 0 ||
           !PPM_EQUAL (getBitmapColor (bitmap, row - 1, col), color));

    case RIGHT:
        return (bool)
            (col == bitmap.width - 1
             || !PPM_EQUAL(getBitmapColor(bitmap, row, col + 1), color));

    case BOTTOM:
        return (bool)
            (row == bitmap.height - 1
             || !PPM_EQUAL(getBitmapColor (bitmap, row + 1, col), color));

    case NO_EDGE:
    default:
      LOG1 ("is_outline_edge: Bad edge value(%d)", edge);
      at_exception_fatal(exp, "is_outline_edge: Bad edge value");
    }

  return false; /* NOT REACHED */
}


/* Is this really an edge and is it still unmarked? */

static bool
is_unmarked_outline_edge(unsigned short row,
                         unsigned short col,
                         edge_type edge,
                         bitmap_type bitmap,
                         bitmap_type marked,
                         pixel color,
                         at_exception_type * exp)
{
  return
    (bool)(!is_marked_edge (edge, row, col, marked)
              && is_outline_edge (edge, bitmap, row, col, color, exp));
}


static bool
is_valid_dir(unsigned int   const row,
             unsigned int   const col,
             direction_type const dir,
             bitmap_type    const bitmap,
             bitmap_type    const marked) {
  
    return(!is_marked_dir(row, col, dir, marked)
           && COMPUTE_DELTA(ROW, dir)+row > 0
           && COMPUTE_DELTA(COL, dir)+col > 0
           && BITMAP_VALID_PIXEL(bitmap,
                                 COMPUTE_DELTA(ROW, dir) + row,
                                 COMPUTE_DELTA(COL, dir) + col)
           && PPM_EQUAL(getBitmapColor(bitmap,
                                       COMPUTE_DELTA(ROW, dir) + row,
                                       COMPUTE_DELTA(COL, dir) + col),
                        getBitmapColor(bitmap, row, col)));
}



static bool
next_unmarked_pixel(unsigned int *   const row,
                    unsigned int *   const col,
                    direction_type * const dir,
                    bitmap_type      const bitmap,
                    bitmap_type *    const marked) {

    unsigned int   const orig_row = *row;
    unsigned int   const orig_col = *col;
    direction_type const orig_dir = *dir;

    direction_type test_dir;
    pixel color;

    test_dir = *dir;  /* initial value */
    color = getBitmapColor(bitmap, *row, *col);

    do {
        if (is_valid_dir(orig_row, orig_col, test_dir, bitmap, *marked)) {
            *row = orig_row + COMPUTE_DELTA(ROW, test_dir);
            *col = orig_col + COMPUTE_DELTA(COL, test_dir);
            *dir = test_dir;
            break;
        }

        if (orig_dir == test_dir)
            test_dir = (orig_dir + 2) % 8;
        else if ((orig_dir + 2) % 8 == test_dir)
            test_dir = (orig_dir + 6) % 8;
        else if ((orig_dir + 6) % 8 == test_dir)
            test_dir = (orig_dir + 1) % 8;
        else if ((orig_dir + 1) % 8 == test_dir)
            test_dir = (orig_dir + 7) % 8;
        else if ((orig_dir + 7) % 8 == test_dir)
            test_dir = (orig_dir + 3) % 8;
        else if ((orig_dir + 3) % 8 == test_dir)
            test_dir = (orig_dir + 5) % 8;
        else if ((orig_dir + 5) % 8 == test_dir)
            break;
    } while (1);

    if ((*row != orig_row || *col != orig_col) && 
        (!(is_other_dir_marked(orig_row, orig_col, test_dir, *marked) &&
           is_other_dir_marked(orig_row + COMPUTE_DELTA(ROW, test_dir),
                               orig_col + COMPUTE_DELTA(COL, test_dir),
                               test_dir,*marked))))
        return true;
    else
        return false;
}



static pixel_outline_type
findOneCenterline(bitmap_type    const bitmap,
                  direction_type const originalDir,
                  unsigned int   const originalRow,
                  unsigned int   const originalCol,
                  bitmap_type *  const marked) {

    direction_type searchDir;
    unsigned int row, col;
    pixel_outline_type outline;

    outline = new_pixel_outline();
    outline.open  = false;
    outline.color = getBitmapColor(bitmap, originalRow, originalCol);

    /* Add the starting pixel to the output list, changing from bitmap
       to Cartesian coordinates and specifying the left edge so that
       the coordinates won't be adjusted.
    */
    {
        pm_pixelcoord pos;
        pos.col = col; pos.row = bitmap.height - row - 1;
        LOG2(" (%d,%d)", pos.col, pos.row);
        append_outline_pixel(&outline, pos);
    }
    searchDir = originalDir;  /* initial value */
    row = originalRow;         /* initial value */
    col = originalCol;         /* initial values */

    for ( ; ; ) {
        unsigned int const prevRow = row;
        unsigned int const prevCol = col;

        /* If there is no adjacent, unmarked pixel, we can't proceed
           any further, so return an open outline.
        */
        if (!next_unmarked_pixel(&row, &col, &searchDir, bitmap, marked)) {
            outline.open = true;
            break;
        }

        /* If we've moved to a new pixel, mark all edges of the previous
           pixel so that it won't be revisited.
        */
        if (!(prevRow == originalRow && prevCol == originalCol))
            mark_dir(prevRow, prevCol, searchDir, marked);
        mark_dir(row, col, (searchDir + 4) % 8, marked);

        /* If we've returned to the starting pixel, we're done. */
        if (row == originalRow && col == originalCol)
            break;

        
        {
            /* Add the new pixel to the output list. */
            pm_pixelcoord pos;
            pos.col = col; pos.row = bitmap.height - row - 1;
            LOG2(" (%d,%d)", pos.col, pos.row);
            append_outline_pixel(&outline, pos);
        }
    }
    mark_dir(originalRow, originalCol, originalDir, marked);

    return outline;
}



static bool
wrongDirection(unsigned int   const row,
               unsigned int   const col,
               direction_type const dir,
               bitmap_type    const bitmap,
               bitmap_type    const marked) {

    return (!is_valid_dir(row, col, dir, bitmap, marked)
            || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row,
                              COMPUTE_DELTA(COL, dir) + col,
                              dir, bitmap, marked)
                && num_neighbors(row, col, bitmap) > 2)
            || num_neighbors(row, col, bitmap) > 4
            || num_neighbors(COMPUTE_DELTA(ROW, dir) + row,
                             COMPUTE_DELTA(COL, dir) + col, bitmap) > 4
            || (is_other_dir_marked(row, col, dir, marked)
                && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir),
                                       col + COMPUTE_DELTA(COL, dir),
                                       dir, marked)));
}



pixel_outline_list_type
find_centerline_pixels(bitmap_type         const bitmap,
                       pixel               const bg_color, 
                       at_progress_func          notify_progress,
                       void *              const progress_data,
                       at_testcancel_func        test_cancel,
                       void *              const testcancel_data,
                       at_exception_type * const exp) {

  pixel_outline_list_type outline_list;
  signed short row;
  bitmap_type marked = new_bitmap(bitmap.width, bitmap.height);
  unsigned int const max_progress = bitmap.height * bitmap.width;
    
  O_LIST_LENGTH(outline_list) = 0;
  outline_list.data = NULL;

  for (row = 0; row < bitmap.height; ++row) {
      signed short col;
      for (col = 0; col < bitmap.width; ) {
          bool           const clockwise = false;

          direction_type dir;
          pixel_outline_type outline;

          if (notify_progress)
              notify_progress((float)(row * bitmap.width + col) /
                              ((float) max_progress * (float)3.0),
                              progress_data);

		  if (PPM_EQUAL(getBitmapColor(bitmap, row, col), bg_color)) {
	          ++col;
			  continue;
          }

          dir = EAST;

          if (wrongDirection(row, col, dir, bitmap, marked)) {
              dir = SOUTHEAST;
              if (wrongDirection(row, col, dir, bitmap, marked)) {
                  dir = SOUTH;
                  if (wrongDirection(row, col, dir, bitmap, marked)) {
                      dir = SOUTHWEST;
                      if (wrongDirection(row, col, dir, bitmap, marked)) {
						  ++col;
						  continue;
                      }
                  }
              }
          }

          LOG2("#%u: (%sclockwise) ", O_LIST_LENGTH(outline_list),
               clockwise ? "" : "counter");

          outline = findOneCenterline(bitmap, dir, row, col, &marked);

          /* If the outline is open (i.e., we didn't return to the
             starting pixel), search from the starting pixel in the
             opposite direction and concatenate the two outlines.
          */

          if (outline.open) {
              pixel_outline_type partial_outline;
              bool okay = false;

              if (dir == EAST) {
                  dir = SOUTH;
                  okay = is_valid_dir(row, col, dir, bitmap, marked);
                  if (!okay) {
                      dir = SOUTHWEST;
                      okay = is_valid_dir(row, col, dir, bitmap, marked);
                      if (!okay) {
                          dir = SOUTHEAST;
                          okay = is_valid_dir(row, col, dir, bitmap, marked);
                      }
                  }
              } else if (dir == SOUTHEAST) {
                  dir = SOUTHWEST;
                  okay = is_valid_dir(row, col, dir, bitmap, marked);
                  if (!okay) {
                      dir = EAST;
                      okay=is_valid_dir(row, col, dir, bitmap, marked);
                      if (!okay) {
                          dir = SOUTH;
                          okay = is_valid_dir(row, col, dir, bitmap, marked);
                      }
                  }
              } else if (dir == SOUTH) {
                  dir = EAST;
                  okay = is_valid_dir(row, col, dir, bitmap, marked);
                  if (!okay) {
                      dir = SOUTHEAST;
                      okay = is_valid_dir(row, col, dir, bitmap, marked);
                      if (!okay) {
                          dir = SOUTHWEST;
                          okay = is_valid_dir(row, col, dir, bitmap, marked);
                      }
                  }
              } else if (dir == SOUTHWEST) {
                  dir = SOUTHEAST;
                  okay = is_valid_dir(row, col, dir, bitmap, marked);
                  if (!okay) {
                      dir = EAST;
                      okay = is_valid_dir(row, col, dir, bitmap, marked);
                      if (!okay) {
                          dir = SOUTH;
                          okay = is_valid_dir(row, col, dir, bitmap, marked);
                      }
                  }
              }
              if (okay) {
                  partial_outline =
                      findOneCenterline(bitmap, dir, row, col, &marked);
                  concat_pixel_outline(&outline, &partial_outline);
                  if (partial_outline.data)
                      free(partial_outline.data);
              } else
                  ++col;
          }        
            
          /* Outside outlines will start at a top edge, and move
             counterclockwise, and inside outlines will start at a
             bottom edge, and move clockwise.  This happens because of
             the order in which we look at the edges.
          */
          O_CLOCKWISE(outline) = clockwise;
          if (O_LENGTH(outline) > 1)
              append_pixel_outline(&outline_list, outline);
          LOG1("(%s)", (outline.open ? " open" : " closed"));
          LOG1(" [%u].\n", O_LENGTH(outline));
          if (O_LENGTH(outline) == 1)
              free_pixel_outline(&outline);
        }
  }
  if (test_cancel && test_cancel(testcancel_data)) {
      if (O_LIST_LENGTH (outline_list) != 0)
          free_pixel_outline_list (&outline_list);
  }
  free_bitmap(&marked);
  flush_log_output();
  return outline_list;
}



/* Add an outline to an outline list. */

static void
append_pixel_outline (pixel_outline_list_type *outline_list,
                      pixel_outline_type outline)
{
  O_LIST_LENGTH (*outline_list)++;
  REALLOCARRAY_NOFAIL(outline_list->data, outline_list->length);
  O_LIST_OUTLINE (*outline_list, O_LIST_LENGTH (*outline_list) - 1) = outline;
}


/* Free the list of outline lists. */

void
free_pixel_outline_list (pixel_outline_list_type *outline_list)
{
  unsigned this_outline;

  for (this_outline = 0; this_outline < outline_list->length; this_outline++)
    {
      pixel_outline_type o = outline_list->data[this_outline];
      free_pixel_outline (&o);
    }
  outline_list->length = 0;

  if (outline_list->data != NULL)
    {
      free (outline_list->data);
      outline_list->data = NULL;
    }

  flush_log_output ();
}


/* Return an empty list of pixels.  */


static pixel_outline_type
new_pixel_outline (void)
{
  pixel_outline_type pixel_outline;

  O_LENGTH (pixel_outline) = 0;
  pixel_outline.data = NULL;
  pixel_outline.open = false;

  return pixel_outline;
}

static void
free_pixel_outline (pixel_outline_type * outline)
{
  if (outline->data)
    {
      free (outline->data) ;
      outline->data   = NULL;
      outline->length = 0;
    }
}

/* Concatenate two pixel lists. The two lists are assumed to have the
   same starting pixel and to proceed in opposite directions therefrom. */

static void
concat_pixel_outline(pixel_outline_type *o1, const pixel_outline_type *o2)
{
  int src, dst;
  unsigned o1_length, o2_length;
  if (!o1 || !o2 || O_LENGTH(*o2) <= 1) return;

  o1_length = O_LENGTH(*o1);
  o2_length = O_LENGTH(*o2);
  O_LENGTH(*o1) += o2_length - 1;
  /* Resize o1 to the sum of the lengths of o1 and o2 minus one (because
     the two lists are assumed to share the same starting pixel). */
  REALLOCARRAY_NOFAIL(o1->data, O_LENGTH(*o1));
  /* Shift the contents of o1 to the end of the new array to make room
     to prepend o2. */
  for (src = o1_length - 1, dst = O_LENGTH(*o1) - 1; src >= 0; src--, dst--)
    O_COORDINATE(*o1, dst) = O_COORDINATE(*o1, src);
  /* Prepend the contents of o2 (in reverse order) to o1. */
  for (src = o2_length - 1, dst = 0; src > 0; src--, dst++)
    O_COORDINATE(*o1, dst) = O_COORDINATE(*o2, src);
}


/* If EDGE is not already marked, we mark it; otherwise, it's a fatal error.
   The position ROW and COL should be inside the bitmap MARKED. EDGE can be
   NO_EDGE. */

static void
mark_edge (edge_type edge, unsigned short row,
           unsigned short col, bitmap_type *marked)
{
  *BITMAP_PIXEL (*marked, row, col) |= 1 << edge;
}


/* Mark the direction of the pixel ROW/COL in MARKED. */

static void
mark_dir(unsigned short row, unsigned short col, direction_type dir, bitmap_type *marked)
{
  *BITMAP_PIXEL(*marked, row, col) |= 1 << dir;
}


/* Test if the direction of pixel at ROW/COL in MARKED is marked. */

static bool
is_marked_dir(unsigned short row, unsigned short col, direction_type dir, bitmap_type marked)
{
  return (bool)((*BITMAP_PIXEL(marked, row, col) & 1 << dir) != 0);
}


static bool
is_other_dir_marked(unsigned short row, unsigned short col, direction_type dir, bitmap_type marked)
{
  return (bool)((*BITMAP_PIXEL(marked, row, col) & (255 - (1 << dir) - (1 << ((dir + 4) % 8))) ) != 0);
}


/* Return the number of pixels adjacent to pixel ROW/COL that are black. */

static unsigned
num_neighbors(unsigned short row, unsigned short col, bitmap_type bitmap)
{
    unsigned dir, count = 0;
    pixel color = getBitmapColor(bitmap, row, col);
    for (dir = NORTH; dir <= NORTHEAST; dir++)
    {
	int delta_r = COMPUTE_DELTA(ROW, dir);
	int delta_c = COMPUTE_DELTA(COL, dir);
	unsigned int test_row = row + delta_r;
	unsigned int test_col = col + delta_c;
	if (BITMAP_VALID_PIXEL(bitmap, test_row, test_col)
	    && PPM_EQUAL(getBitmapColor(bitmap, test_row, test_col), color))
	    ++count;
    }
    return count;
}


/* Test if the edge EDGE at ROW/COL in MARKED is marked.  */

static bool
is_marked_edge (edge_type edge, unsigned short row, unsigned short col, bitmap_type marked)
{
  return
    (bool)(edge == NO_EDGE ? false : (*BITMAP_PIXEL (marked, row, col) & (1 << edge)) != 0);
}



static void
nextClockwisePointTop(bitmap_type         const bitmap,
                      edge_type *         const edge,
                      unsigned int *      const row,
                      unsigned int *      const col,
                      pixel               const color,
                      bitmap_type         const marked,
                      at_exception_type * const exp,
                      pm_pixelcoord *     const posP) {

    if ((*col >= 1 && !is_marked_edge(TOP, *row, *col-1, marked) &&
             is_outline_edge(TOP, bitmap, *row, *col-1, color, exp))) {

        /* WEST */

        *edge = TOP;
        --*col;
        posP->col = *col;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col >= 1 && *row >= 1 &&
         !is_marked_edge(RIGHT, *row-1, *col-1, marked) &&
         is_outline_edge(RIGHT, bitmap, *row-1, *col-1,
                         color, exp)) &&
        !(is_marked_edge(LEFT, *row-1, *col, marked) &&
          is_marked_edge(TOP, *row,*col-1, marked)) &&
        !(is_marked_edge(BOTTOM, *row-1, *col, marked) &&
          is_marked_edge(RIGHT, *row, *col-1, marked))) {

        /* NORTHWEST */

        *edge = RIGHT;
        --*col;
        --*row;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row;
        return;
    } 

    RETURN_IF_FATAL();

    if ((!is_marked_edge(LEFT, *row, *col, marked)
         && is_outline_edge(LEFT, bitmap, *row, *col, color, exp))) {

        *edge = LEFT;
        posP->col = *col;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}



static void
nextClockwisePointRight(bitmap_type         const bitmap,
                        edge_type *         const edge,
                        unsigned int *      const row,
                        unsigned int *      const col,
                        pixel               const color,
                        bitmap_type         const marked,
                        at_exception_type * const exp,
                        pm_pixelcoord *     const posP) {

    if ((*row >= 1 &&
         !is_marked_edge(RIGHT, *row-1, *col, marked) &&
         is_outline_edge(RIGHT, bitmap, *row-1, *col, color, exp))) {

         /* NORTH */
        
        *edge = RIGHT;
        --*row;
        posP->col = *col+1;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();
    
    if ((*col+1 < marked.width && *row >= 1 &&
         !is_marked_edge(BOTTOM, *row-1, *col+1, marked) &&
         is_outline_edge(BOTTOM, bitmap, *row-1, *col+1,
                         color, exp)) &&
        !(is_marked_edge(LEFT, *row, *col+1, marked) &&
          is_marked_edge(BOTTOM, *row-1, *col, marked)) &&
        !(is_marked_edge(TOP, *row, *col+1, marked) &&
          is_marked_edge(RIGHT, *row-1, *col, marked))) {

        /* NORTHEAST */
        *edge = BOTTOM;
        ++*col;
        --*row;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row - 1;
        return;
    } 

    RETURN_IF_FATAL();

    if ((!is_marked_edge(TOP, *row, *col, marked) &&
         is_outline_edge(TOP, bitmap, *row, *col, color, exp))) {

        *edge = TOP;
        posP->col = *col;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}



static void
nextClockwisePointBottom(bitmap_type         const bitmap,
                         edge_type *         const edge,
                         unsigned int *      const row,
                         unsigned int *      const col,
                         pixel               const color,
                         bitmap_type         const marked,
                         at_exception_type * const exp,
                         pm_pixelcoord *     const posP) {
    
    if ((*col+1 < marked.width &&
         !is_marked_edge(BOTTOM, *row, *col+1, marked) &&
         is_outline_edge(BOTTOM, bitmap, *row, *col+1, color, exp))) {

        /* EAST */

        *edge = BOTTOM;
        ++*col;
        posP->col = *col+1;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col + 1 < marked.width && *row+1 < marked.height &&
         !is_marked_edge(LEFT, *row+1,*col+1, marked) &&
         is_outline_edge(LEFT, bitmap, *row+1, *col+1, color, exp)) &&
        !(is_marked_edge(TOP, *row+1, *col, marked) &&
          is_marked_edge(LEFT, *row, *col+1, marked)) &&
        !(is_marked_edge(RIGHT, *row+1, *col, marked) &&
          is_marked_edge(BOTTOM, *row, *col+1, marked))) {

        /* SOUTHEAST */

        *edge = LEFT;
        ++*col;
        ++*row;
        posP->col = *col;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    if ((!is_marked_edge(RIGHT, *row, *col, marked) &&
         is_outline_edge(RIGHT, bitmap, *row, *col, color, exp))) {

        *edge = RIGHT;
        posP->col = *col+1;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}



static void
nextClockwisePointLeft(bitmap_type         const bitmap,
                       edge_type *         const edge,
                       unsigned int *      const row,
                       unsigned int *      const col,
                       pixel               const color,
                       bitmap_type         const marked,
                       at_exception_type * const exp,
                       pm_pixelcoord *     const posP) {

    if ((*row+1 < marked.height &&
         !is_marked_edge(LEFT, *row+1, *col, marked) &&
         is_outline_edge(LEFT, bitmap, *row+1, *col, color, exp))) {

        /* SOUTH */

        *edge = LEFT;
        ++*row;
        posP->col = *col;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col >= 1 && *row+1 < marked.height &&
         !is_marked_edge(TOP, *row+1, *col-1, marked) &&
         is_outline_edge(TOP, bitmap, *row+1, *col-1, color, exp)) &&
        !(is_marked_edge(RIGHT, *row, *col-1, marked) &&
          is_marked_edge(TOP, *row+1, *col, marked)) &&
        !(is_marked_edge(BOTTOM, *row, *col-1, marked) &&
          is_marked_edge(LEFT, *row+1, *col, marked))) {
        
        /* SOUTHWEST */
        
        *edge = TOP;
        --*col;
        ++*row;
        posP->col = *col;
        posP->row = bitmap.height - *row;
        return;
    } 

    RETURN_IF_FATAL();

    if ((!is_marked_edge(BOTTOM, *row, *col, marked) &&
         is_outline_edge(BOTTOM, bitmap, *row, *col, color, exp))) {
        *edge = BOTTOM;
        posP->col = *col+1;
        posP->row = bitmap.height - *row - 1;
        return;
    }
    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}



static void
nextClockwisePoint(bitmap_type         const bitmap,
                   edge_type *         const edge,
                   unsigned int *      const row,
                   unsigned int *      const col,
                   pixel               const color,
                   bitmap_type         const marked,
                   at_exception_type * const exp,
                   pm_pixelcoord *     const posP) {
    
    switch (*edge) {
    case TOP:
        nextClockwisePointTop(  bitmap, edge, row, col, color,
                                marked, exp, posP);
        break;
    case RIGHT: 
        nextClockwisePointRight(bitmap, edge, row, col, color,
                                marked, exp, posP);
        break;
    case BOTTOM: 
        nextClockwisePointBottom(bitmap, edge, row, col, color,
                                 marked, exp, posP);
        break;
    case LEFT: 
        nextClockwisePointLeft(  bitmap, edge, row, col, color,
                                 marked, exp, posP);
        break;
    case NO_EDGE:
        break;
    default:
        *edge = NO_EDGE;
        break;
    }
}



static void
nextCcwPointTop(bitmap_type         const bitmap,
                edge_type *         const edge,
                unsigned int *      const row,
                unsigned int *      const col,
                pixel               const color,
                bitmap_type         const marked,
                at_exception_type * const exp,
                pm_pixelcoord *     const posP) {

    if ((!is_marked_edge(LEFT, *row, *col, marked) &&
         is_outline_edge(LEFT,bitmap,*row,*col, color, exp))) {

        *edge = LEFT;
        posP->col = *col;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col >= 1 &&
         !is_marked_edge(TOP, *row, *col-1, marked) &&
         is_outline_edge(TOP, bitmap, *row, *col-1, color, exp))) {

        /* WEST */

        *edge = TOP;
        --*col;
        posP->col = *col;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();
    
    if ((*col >= 1 && *row >= 1 &&
         !is_marked_edge(RIGHT, *row-1, *col-1, marked) &&
         is_outline_edge(RIGHT, bitmap, *row-1, *col-1, color, exp))) {

        /* NORTHWEST */

        *edge = RIGHT;
        --*col;
        --*row;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row;
        return;
    } 

    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}



static void
nextCcwPointRight(bitmap_type         const bitmap,
                  edge_type *         const edge,
                  unsigned int *      const row,
                  unsigned int *      const col,
                  pixel               const color,
                  bitmap_type         const marked,
                  at_exception_type * const exp,
                  pm_pixelcoord *     const posP) {

    if ((!is_marked_edge(TOP, *row, *col, marked) &&
         is_outline_edge(TOP, bitmap, *row, *col, color, exp))) {

        *edge = TOP;
        posP->col = *col;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    if ((*row >= 1 &&
         !is_marked_edge(RIGHT, *row-1, *col, marked) &&
         is_outline_edge(RIGHT, bitmap, *row-1, *col, color, exp))) {

        /* NORTH */
        
        *edge = RIGHT;
        --*row;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col + 1 < marked.width && *row >= 1 &&
         !is_marked_edge(BOTTOM, *row-1, *col+1, marked) &&
         is_outline_edge(BOTTOM, bitmap, *row-1, *col+1, color, exp))) {

        /* NORTHEAST */

        *edge = BOTTOM;
        ++*col;
        ++*row;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}



static void
nextCcwPointBottom(bitmap_type         const bitmap,
                   edge_type *         const edge,
                   unsigned int *      const row,
                   unsigned int *      const col,
                   pixel               const color,
                   bitmap_type         const marked,
                   at_exception_type * const exp,
                   pm_pixelcoord *     const posP) {

    if ((!is_marked_edge(RIGHT, *row, *col, marked) &&
         is_outline_edge(RIGHT, bitmap, *row, *col, color, exp))) {

        *edge = RIGHT;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col + 1 < marked.width &&
         !is_marked_edge(BOTTOM, *row, *col+1, marked) &&
         is_outline_edge(BOTTOM, bitmap, *row, *col+1, color, exp))) {

        /* EAST */

        *edge = BOTTOM;
        ++*col;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    if ((*col + 1 < marked.width && *row + 1 < marked.height &&
         !is_marked_edge(LEFT, *row+1, *col+1, marked) &&
         is_outline_edge(LEFT, bitmap, *row+1, *col+1, color, exp))) {

        /* SOUTHEAST */

        *edge = LEFT;
        ++*col;
        ++*row;
        posP->col = *col;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();
    
    *edge = NO_EDGE;
}



static void
nextCcwPointLeft(bitmap_type         const bitmap,
                 edge_type *         const edge,
                 unsigned int *      const row,
                 unsigned int *      const col,
                 pixel               const color,
                 bitmap_type         const marked,
                 at_exception_type * const exp,
                 pm_pixelcoord *     const posP) {


    if ((!is_marked_edge(BOTTOM, *row, *col, marked) &&
         is_outline_edge(BOTTOM, bitmap, *row, *col, color, exp))) {

        *edge = BOTTOM;
        posP->col = *col + 1;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();

    if ((*row + 1 < marked.height &&
         !is_marked_edge(LEFT, *row+1, *col, marked) &&
         is_outline_edge(LEFT, bitmap, *row+1, *col, color, exp))) {

        /* SOUTH */

        *edge = LEFT;
        ++*row;
        posP->col = *col;
        posP->row = bitmap.height - *row - 1;
        return;
    }

    RETURN_IF_FATAL();
    
    if ((*col >= 1 && *row + 1 < marked.height &&
         !is_marked_edge(TOP, *row+1, *col-1, marked) &&
         is_outline_edge(TOP, bitmap, *row+1, *col-1, color, exp))) {

        /* SOUTHWEST */

        *edge = TOP;
        --*col;
        ++*row;
        posP->col = *col;
        posP->row = bitmap.height - *row;
        return;
    }

    RETURN_IF_FATAL();

    *edge = NO_EDGE;
}

static void
nextCounterClockwisePoint(bitmap_type         const bitmap,
                          edge_type *         const edge,
                          unsigned int *      const row,
                          unsigned int *      const col,
                          pixel               const color,
                          bitmap_type         const marked,
                          at_exception_type * const exp,
                          pm_pixelcoord *     const posP) {

    switch (*edge) {
    case TOP:
        nextCcwPointTop(   bitmap, edge, row, col, color, marked, exp, posP);
        break;
    case RIGHT: 
        nextCcwPointRight( bitmap, edge, row, col, color, marked, exp, posP);
        break;
    case BOTTOM: 
        nextCcwPointBottom(bitmap, edge, row, col, color, marked, exp, posP);
        break;
    case LEFT: 
        nextCcwPointLeft(  bitmap, edge, row, col, color, marked, exp, posP);
        break;
    case NO_EDGE:
        break;
    default: 
        *edge = NO_EDGE;
        break;
    }
}



static void
nextPoint(bitmap_type         const bitmap,
          edge_type *         const edge,
          unsigned int *      const row,
          unsigned int *      const col,
          pm_pixelcoord *     const nextPointP,
          pixel               const color,
          bool                const clockwise,
          bitmap_type         const marked,
          at_exception_type * const exp) {

    if (!clockwise)
        nextClockwisePoint(       bitmap, edge, row, col, color,
                                  marked, exp, nextPointP);
    else
        nextCounterClockwisePoint(bitmap, edge, row, col, color,
                                  marked, exp, nextPointP);
}



static pixel_outline_type
find_one_outline(bitmap_type         const bitmap,
                 edge_type           const originalEdge,
                 unsigned int        const originalRow,
                 unsigned int        const originalCol,
                 bitmap_type *       const marked,
                 bool                const clockwise,
                 bool                const ignore,
                 at_exception_type * const exp) {
/*----------------------------------------------------------------------------
  Calculate one single outline.  We pass the position of the
  starting pixel and the starting edge.  We mark all edges we track along
  and append the outline pixels to the coordinate list.
-----------------------------------------------------------------------------*/
    unsigned int row;
    unsigned int col;
    edge_type    edge;

    pixel_outline_type outline;
    pm_pixelcoord pos;
    
    outline = new_pixel_outline();
    outline.color = getBitmapColor(bitmap, originalRow, originalCol);

    row  = originalRow;   /* initial value */
    col  = originalCol;   /* initial value */
    edge = originalEdge;  /* initial value */

    /* Set initial position */
    pos.col = col + ((edge == RIGHT) || (edge == BOTTOM) ? 1 : 0);
    pos.row = bitmap.height - row - 1 + 
        (edge == TOP || edge == RIGHT ? 1 : 0);

    do {
        /* Put this edge into the output list */
        if (!ignore) {
            LOG2(" (%d,%d)", pos.col, pos.row);
            append_outline_pixel(&outline, pos);
        }
        
        mark_edge(edge, row, col, marked);
        nextPoint(bitmap, &edge, &row, &col, &pos, outline.color, clockwise,
                  *marked, exp);
            /* edge, row, and col are both input and output in the above */
    } while (edge != NO_EDGE && !at_exception_got_fatal(exp));

    if (ignore || at_exception_got_fatal(exp))
        free_pixel_outline(&outline);

    return outline;
}



pixel_outline_list_type
find_outline_pixels(bitmap_type         const bitmap,
                    bool                const bg_spec,
                    pixel               const bg_color, 
                    at_progress_func          notify_progress,
                    void *              const progress_data,
                    at_testcancel_func        test_cancel,
                    void *              const testcancel_data,
                    at_exception_type * const exp) {
/*----------------------------------------------------------------------------
   Return a list of outlines in the image whose raster is 'bitmap'.

   The background color of the image is 'bg_color' if 'bg_spec' is true;
   otherwise, there is no background color.
-----------------------------------------------------------------------------*/
    /* We go through a bitmap TOP to BOTTOM, LEFT to RIGHT, looking for
       each pixel with an unmarked edge that we consider a starting point
       of an outline.  When we find one, we trace the outline and add it
       to the list, marking the edges in it as we go.
    */
    unsigned int const max_progress = bitmap.height * bitmap.width;
    
    pixel_outline_list_type outline_list;
    unsigned int row;
    bitmap_type marked;
    
    marked = new_bitmap (bitmap.width, bitmap.height);
    
    O_LIST_LENGTH(outline_list) = 0;
    outline_list.data = NULL;
    
    for (row = 0; row < bitmap.height; ++row) {
        unsigned int col;
        for (col = 0; col < bitmap.width; ++col) {
            pixel const color = getBitmapColor(bitmap, row, col);
            bool const is_background =
                bg_spec && PPM_EQUAL(color, bg_color);

            if (notify_progress)
                notify_progress((float)(row * bitmap.width + col) /
                                ((float) max_progress * (float)3.0),
                                progress_data);

            /* A valid edge can be TOP for an outside outline.
               Outside outlines are traced counterclockwise.
            */

            if (!is_background &&
                is_unmarked_outline_edge(row, col, TOP,
                                         bitmap, marked, color, exp)) {
                pixel_outline_type outline;
                
                CHECK_FATAL();   /* FREE(DONE) outline_list */
                
                LOG1("#%u: (counterclockwise)", O_LIST_LENGTH(outline_list));
                
                outline = find_one_outline(bitmap, TOP, row, col, &marked,
                                           false, false, exp);
                CHECK_FATAL();    /* FREE(DONE) outline_list */
                
                O_CLOCKWISE(outline) = false;
                append_pixel_outline(&outline_list, outline);
                
                LOG1(" [%u].\n", O_LENGTH (outline));
            } else
                CHECK_FATAL ();	/* FREE(DONE) outline_list */

            /* A valid edge can be BOTTOM for an inside outline.
               Inside outlines are traced clockwise.
            */
            if (row > 0) {
                pixel const colorAbove = getBitmapColor(bitmap, row-1, col);
                if (!(bg_spec && PPM_EQUAL(colorAbove, bg_color)) &&
                    is_unmarked_outline_edge(row-1, col, BOTTOM,
                                             bitmap, marked, colorAbove,exp)) {
                    CHECK_FATAL(); /* FREE(DONE) outline_list */
                    
                    /* This lines are for debugging only:*/
                    if (is_background) {
                        pixel_outline_type outline;
                    
                        LOG1("#%u: (clockwise)", O_LIST_LENGTH(outline_list));
                        
                        outline = find_one_outline(bitmap, BOTTOM, row-1, col,
                                                   &marked, true, false, exp);
                        CHECK_FATAL(); /* FREE(DONE) outline_list */
                        
                        O_CLOCKWISE(outline) = true;
                        append_pixel_outline(&outline_list, outline);
                        
                        LOG1(" [%u].\n", O_LENGTH(outline));
                    } else {
                        find_one_outline(bitmap, BOTTOM, row-1, col,
                                         &marked, true, true, exp);
                        CHECK_FATAL(); /* FREE(DONE) outline_list */
                    }
                } else
                    CHECK_FATAL();	/* FREE(DONE) outline_list */
            }
            if (test_cancel && test_cancel(testcancel_data)) {
                free_pixel_outline_list(&outline_list);
                goto cleanup;
            }
        }
    }
 cleanup:
    free_bitmap(&marked);
    flush_log_output();
    if (at_exception_got_fatal(exp))
        free_pixel_outline_list(&outline_list);

    return outline_list;
}