decompose.c

Go to the documentation of this file.

/* decompose.c 146 2007-04-09 00:43:46Z selinger */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "potracelib.h"
#include "curve.h"
#include "lists.h"
#include "auxiliary.h"
#include "bitmap.h"
#include "decompose.h"
//#include "progress.h"

static void
bm_clearexcess (potrace_bitmap_t * bm)
{
  potrace_word mask;
  int y;

  if (bm->w % BM_WORDBITS != 0)
    {
      mask = BM_ALLBITS << (BM_WORDBITS - (bm->w % BM_WORDBITS));
      for (y = 0; y < bm->h; y++)
        {
          *bm_index (bm, bm->w, y) &= mask;
        }
    }
}

struct bbox_s
{
  int x0, x1, y0, y1;           /* bounding box */
};
typedef struct bbox_s bbox_t;

static void
clear_bm_with_bbox (potrace_bitmap_t * bm, bbox_t * bbox)
{
  int imin = (bbox->x0 / BM_WORDBITS);
  int imax = ((bbox->x1 + BM_WORDBITS - 1) / BM_WORDBITS);
  int i, y;

  for (y = bbox->y0; y < bbox->y1; y++)
    {
      for (i = imin; i < imax; i++)
        {
          bm_scanline (bm, y)[i] = 0;
        }
    }
}

/* ---------------------------------------------------------------------- */
/* auxiliary functions */

static inline int
detrand (int x, int y)
{
  unsigned int z;
  static const unsigned char t[256] = {
    /* non-linear sequence: constant term of inverse in GF(8), 
       mod x^8+x^4+x^3+x+1 */
    0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0,
    0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
    1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1,
    0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0,
    0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0,
    0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0,
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1,
    1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0,
    0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1,
    1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
  };

  /* 0x04b3e375 and 0x05a8ef93 are chosen to contain every possible
     5-bit sequence */
  z = ((0x04b3e375 * x) ^ y) * 0x05a8ef93;
  z =
    t[z & 0xff] ^ t[(z >> 8) & 0xff] ^ t[(z >> 16) & 0xff] ^ t[(z >> 24) &
                                                               0xff];
  return z & 1;
}

static int
majority (potrace_bitmap_t * bm, int x, int y)
{
  int i, a, ct;

  for (i = 2; i < 5; i++)
    {                           /* check at "radius" i */
      ct = 0;
      for (a = -i + 1; a <= i - 1; a++)
        {
          ct += BM_GET (bm, x + a, y + i - 1) ? 1 : -1;
          ct += BM_GET (bm, x + i - 1, y + a - 1) ? 1 : -1;
          ct += BM_GET (bm, x + a - 1, y - i) ? 1 : -1;
          ct += BM_GET (bm, x - i, y + a) ? 1 : -1;
        }
      if (ct > 0)
        {
          return 1;
        }
      else if (ct < 0)
        {
          return 0;
        }
    }
  return 0;
}

/* ---------------------------------------------------------------------- */
/* decompose image into paths */

static void
xor_to_ref (potrace_bitmap_t * bm, int x, int y, int xa)
{
  int xhi = x & -BM_WORDBITS;
  int xlo = x & (BM_WORDBITS - 1);      /* = x % BM_WORDBITS */
  int i;

  if (xhi < xa)
    {
      for (i = xhi; i < xa; i += BM_WORDBITS)
        {
          *bm_index (bm, i, y) ^= BM_ALLBITS;
        }
    }
  else
    {
      for (i = xa; i < xhi; i += BM_WORDBITS)
        {
          *bm_index (bm, i, y) ^= BM_ALLBITS;
        }
    }
  /* note: the following "if" is needed because x86 treats a<<b as
     a<<(b&31). I spent hours looking for this bug. */
  if (xlo)
    {
      *bm_index (bm, xhi, y) ^= (BM_ALLBITS << (BM_WORDBITS - xlo));
    }
}

static void
xor_path (potrace_bitmap_t * bm, path_t * p)
{
  int xa, x, y, k, y1;

  if (p->priv->len <= 0)
    {                           /* a path of length 0 is silly, but legal */
      return;
    }

  y1 = p->priv->pt[p->priv->len - 1].y;

  xa = p->priv->pt[0].x & -BM_WORDBITS;
  for (k = 0; k < p->priv->len; k++)
    {
      x = p->priv->pt[k].x;
      y = p->priv->pt[k].y;

      if (y != y1)
        {
          /* efficiently invert the rectangle [x,xa] x [y,y1] */
          xor_to_ref (bm, x, min (y, y1), xa);
          y1 = y;
        }
    }
}

static void
setbbox_path (bbox_t * bbox, path_t * p)
{
  int x, y;
  int k;

  bbox->y0 = INT_MAX;
  bbox->y1 = 0;
  bbox->x0 = INT_MAX;
  bbox->x1 = 0;

  for (k = 0; k < p->priv->len; k++)
    {
      x = p->priv->pt[k].x;
      y = p->priv->pt[k].y;

      if (x < bbox->x0)
        {
          bbox->x0 = x;
        }
      if (x > bbox->x1)
        {
          bbox->x1 = x;
        }
      if (y < bbox->y0)
        {
          bbox->y0 = y;
        }
      if (y > bbox->y1)
        {
          bbox->y1 = y;
        }
    }
}

static path_t *
findpath (potrace_bitmap_t * bm, int x0, int y0, int sign, int turnpolicy)
{
  int x, y, dirx, diry, len, size, area;
  int c, d, tmp;
  point_t *pt, *pt1;
  path_t *p = NULL;

  x = x0;
  y = y0;
  dirx = 0;
  diry = -1;

  len = size = 0;
  pt = NULL;
  area = 0;

  while (1)
    {
      /* add point to path */
      if (len >= size)
        {
          size += 100;
          size = (int) (1.3 * size);
          pt1 = (point_t *) realloc (pt, size * sizeof (point_t));
          if (!pt1)
            {
              goto error;
            }
          pt = pt1;
        }
      pt[len].x = x;
      pt[len].y = y;
      len++;

      /* move to next point */
      x += dirx;
      y += diry;
      area += x * diry;

      /* path complete? */
      if (x == x0 && y == y0)
        {
          break;
        }

      /* determine next direction */
      c = BM_GET (bm, x + (dirx + diry - 1) / 2, y + (diry - dirx - 1) / 2);
      d = BM_GET (bm, x + (dirx - diry - 1) / 2, y + (diry + dirx - 1) / 2);

      if (c && !d)
        {                       /* ambiguous turn */
          if (turnpolicy == POTRACE_TURNPOLICY_RIGHT
              || (turnpolicy == POTRACE_TURNPOLICY_BLACK && sign == '+')
              || (turnpolicy == POTRACE_TURNPOLICY_WHITE && sign == '-')
              || (turnpolicy == POTRACE_TURNPOLICY_RANDOM && detrand (x, y))
              || (turnpolicy == POTRACE_TURNPOLICY_MAJORITY
                  && majority (bm, x, y))
              || (turnpolicy == POTRACE_TURNPOLICY_MINORITY
                  && !majority (bm, x, y)))
            {
              tmp = dirx;       /* right turn */
              dirx = diry;
              diry = -tmp;
            }
          else
            {
              tmp = dirx;       /* left turn */
              dirx = -diry;
              diry = tmp;
            }
        }
      else if (c)
        {                       /* right turn */
          tmp = dirx;
          dirx = diry;
          diry = -tmp;
        }
      else if (!d)
        {                       /* left turn */
          tmp = dirx;
          dirx = -diry;
          diry = tmp;
        }
    }                           /* while this path */

  /* allocate new path object */
  p = path_new ();
  if (!p)
    {
      goto error;
    }

  p->priv->pt = pt;
  p->priv->len = len;
  p->area = area;
  p->sign = sign;

  return p;

error:
  free (pt);
  return NULL;
}

static void
pathlist_to_tree (path_t * plist, potrace_bitmap_t * bm)
{
  path_t *p, *p1;
  path_t *heap, *heap1;
  path_t *cur;
  path_t *head;
  path_t **hook, **hook_in, **hook_out; /* for fast appending to linked list */
  bbox_t bbox;

  bm_clear (bm, 0);

  /* save original "next" pointers */
  list_forall (p, plist)
  {
    p->sibling = p->next;
    p->childlist = NULL;
  }

  heap = plist;

  /* the heap holds a list of lists of paths. Use "childlist" field
     for outer list, "next" field for inner list. Each of the sublists
     is to be turned into a tree. This code is messy, but it is
     actually fast. Each path is rendered exactly once. We use the
     heap to get a tail recursive algorithm: the heap holds a list of
     pathlists which still need to be transformed. */

  while (heap)
    {
      /* unlink first sublist */
      cur = heap;
      heap = heap->childlist;
      cur->childlist = NULL;

      /* unlink first path */
      head = cur;
      cur = cur->next;
      head->next = NULL;

      /* render path */
      xor_path (bm, head);
      setbbox_path (&bbox, head);

      /* now do insideness test for each element of cur; append it to
         head->childlist if it's inside head, else append it to
         head->next. */
      hook_in = &head->childlist;
      hook_out = &head->next;
      list_forall_unlink (p, cur)
      {
        if (p->priv->pt[0].y <= bbox.y0)
          {
            list_insert_beforehook (p, hook_out);
            /* append the remainder of the list to hook_out */
            *hook_out = cur;
            break;
          }
        if (BM_GET (bm, p->priv->pt[0].x, p->priv->pt[0].y - 1))
          {
            list_insert_beforehook (p, hook_in);
          }
        else
          {
            list_insert_beforehook (p, hook_out);
          }
      }

      /* clear bm */
      clear_bm_with_bbox (bm, &bbox);

      /* now schedule head->childlist and head->next for further
         processing */
      if (head->next)
        {
          head->next->childlist = heap;
          heap = head->next;
        }
      if (head->childlist)
        {
          head->childlist->childlist = heap;
          heap = head->childlist;
        }
    }

  /* copy sibling structure from "next" to "sibling" component */
  p = plist;
  while (p)
    {
      p1 = p->sibling;
      p->sibling = p->next;
      p = p1;
    }

  /* reconstruct a new linked list ("next") structure from tree
     ("childlist", "sibling") structure. This code is slightly messy,
     because we use a heap to make it tail recursive: the heap
     contains a list of childlists which still need to be
     processed. */
  heap = plist;
  if (heap)
    {
      heap->next = NULL;        /* heap is a linked list of childlists */
    }
  plist = NULL;
  hook = &plist;
  while (heap)
    {
      heap1 = heap->next;
      for (p = heap; p; p = p->sibling)
        {
          /* p is a positive path */
          /* append to linked list */
          list_insert_beforehook (p, hook);

          /* go through its children */
          for (p1 = p->childlist; p1; p1 = p1->sibling)
            {
              /* append to linked list */
              list_insert_beforehook (p1, hook);
              /* append its childlist to heap, if non-empty */
              if (p1->childlist)
                {
                  list_append (path_t, heap1, p1->childlist);
                }
            }
        }
      heap = heap1;
    }

  return;
}

static int
findnext (potrace_bitmap_t * bm, int *xp, int *yp)
{
  int x;
  int y;

  for (y = *yp; y >= 0; y--)
    {
      for (x = 0; x < bm->w; x += BM_WORDBITS)
        {
          if (*bm_index (bm, x, y))
            {
              while (!BM_GET (bm, x, y))
                {
                  x++;
                }
              /* found */
              *xp = x;
              *yp = y;
              return 0;
            }
        }
    }
  /* not found */
  return 1;
}

int
bm_to_pathlist (const potrace_bitmap_t * bm, path_t ** plistp,
                const potrace_param_t * param)
{
  int x;
  int y;
  path_t *p;
  path_t *plist = NULL;         /* linked list of path objects */
  path_t **hook = &plist;       /* used to speed up appending to linked list */
  potrace_bitmap_t *bm1 = NULL;
  int sign;

  bm1 = bm_dup (bm);
  if (!bm1)
    {
      goto error;
    }

  /* be sure the byte padding on the right is set to 0, as the fast
     pixel search below relies on it */
  bm_clearexcess (bm1);

  /* iterate through components */
  y = bm1->h - 1;
  while (findnext (bm1, &x, &y) == 0)
    {
      /* calculate the sign by looking at the original */
      sign = BM_GET (bm, x, y) ? '+' : '-';

      /* calculate the path */
      p = findpath (bm1, x, y + 1, sign, param->turnpolicy);
      if (p == NULL)
        {
          goto error;
        }

      /* update buffered image */
      xor_path (bm1, p);

      /* if it's a turd, eliminate it, else append it to the list */
      if (p->area <= param->turdsize)
        {
          path_free (p);
        }
      else
        {
          list_insert_beforehook (p, hook);
        }

      if (bm1->h > 0)
        {                       /* to be sure */
          //progress_update(1-y/(double)bm1->h, progress);
        }
    }

  pathlist_to_tree (plist, bm1);
  bm_free (bm1);
  *plistp = plist;

//  progress_update(1.0, progress);

  return 0;

error:
  bm_free (bm1);
  list_forall_unlink (p, plist)
  {
    path_free (p);
  }
  return -1;
}