path: root/libart_lgpl/art_uta_vpath.c

/* Libart_LGPL - library of basic graphic primitives
 * Copyright (C) 1998-2000 Raph Levien
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include "config.h"
#include "art_uta_vpath.h"

#include <math.h>

#include "art_misc.h"
#include "art_vpath.h"
#include "art_uta.h"

#ifndef MAX
#define MAX(a, b)  (((a) > (b)) ? (a) : (b))
#endif /* MAX */

#ifndef MIN
#define MIN(a, b)  (((a) < (b)) ? (a) : (b))
#endif /* MIN */

/**
 * art_uta_add_line: Add a line to the uta.
 * @uta: The uta to modify.
 * @x0: X coordinate of line start point.
 * @y0: Y coordinate of line start point.
 * @x1: X coordinate of line end point.
 * @y1: Y coordinate of line end point.
 * @rbuf: Buffer containing first difference of winding number.
 * @rbuf_rowstride: Rowstride of @rbuf.
 *
 * Add the line (@x0, @y0) - (@x1, @y1) to @uta, and also update the
 * winding number buffer used for rendering the interior. @rbuf
 * contains the first partial difference (in the X direction) of the
 * winding number, measured in grid cells. Thus, each time that a line
 * crosses a horizontal uta grid line, an entry of @rbuf is
 * incremented if @y1 > @y0, decremented otherwise.
 *
 * Note that edge handling is fairly delicate. Please rtfs for
 * details.
 **/
void
art_uta_add_line (ArtUta *uta, gdouble x0, gdouble y0, gdouble x1, gdouble y1,
          gint *rbuf, gint rbuf_rowstride)
{
  gint xmin, ymin;
  gdouble xmax, ymax;
  gint xmaxf, ymaxf;
  gint xmaxc, ymaxc;
  gint xt0, yt0;
  gint xt1, yt1;
  gint xf0, yf0;
  gint xf1, yf1;
  gint ix, ix1;
  ArtUtaBbox bb;

  xmin = floor (MIN(x0, x1));
  xmax = MAX(x0, x1);
  xmaxf = floor (xmax);
  xmaxc = ceil (xmax);
  ymin = floor (MIN(y0, y1));
  ymax = MAX(y0, y1);
  ymaxf = floor (ymax);
  ymaxc = ceil (ymax);
  xt0 = (xmin >> ART_UTILE_SHIFT) - uta->x0;
  yt0 = (ymin >> ART_UTILE_SHIFT) - uta->y0;
  xt1 = (xmaxf >> ART_UTILE_SHIFT) - uta->x0;
  yt1 = (ymaxf >> ART_UTILE_SHIFT) - uta->y0;
  if (xt0 == xt1 && yt0 == yt1)
    {
      /* entirely inside a microtile, this is easy! */
      xf0 = xmin & (ART_UTILE_SIZE - 1);
      yf0 = ymin & (ART_UTILE_SIZE - 1);
      xf1 = (xmaxf & (ART_UTILE_SIZE - 1)) + xmaxc - xmaxf;
      yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;

      ix = yt0 * uta->width + xt0;
      bb = uta->utiles[ix];
      if (bb == 0)
    bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
      else
    bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
               MIN(ART_UTA_BBOX_Y0(bb), yf0),
               MAX(ART_UTA_BBOX_X1(bb), xf1),
               MAX(ART_UTA_BBOX_Y1(bb), yf1));
      uta->utiles[ix] = bb;
    }
  else
    {
      gdouble dx, dy;
      gint sx, sy;

      dx = x1 - x0;
      dy = y1 - y0;
      sx = dx > 0 ? 1 : dx < 0 ? -1 : 0;
      sy = dy > 0 ? 1 : dy < 0 ? -1 : 0;
      if (ymin == ymaxf)
    {
      /* special case horizontal (dx/dy slope would be infinite) */
      xf0 = xmin & (ART_UTILE_SIZE - 1);
      yf0 = ymin & (ART_UTILE_SIZE - 1);
      xf1 = (xmaxf & (ART_UTILE_SIZE - 1)) + xmaxc - xmaxf;
      yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;

      ix = yt0 * uta->width + xt0;
      ix1 = yt0 * uta->width + xt1;
      while (ix != ix1)
        {
          bb = uta->utiles[ix];
          if (bb == 0)
        bb = ART_UTA_BBOX_CONS(xf0, yf0, ART_UTILE_SIZE, yf1);
          else
        bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
                   MIN(ART_UTA_BBOX_Y0(bb), yf0),
                   ART_UTILE_SIZE,
                   MAX(ART_UTA_BBOX_Y1(bb), yf1));
          uta->utiles[ix] = bb;
          xf0 = 0;
          ix++;
        }
      bb = uta->utiles[ix];
      if (bb == 0)
        bb = ART_UTA_BBOX_CONS(0, yf0, xf1, yf1);
      else
        bb = ART_UTA_BBOX_CONS(0,
                   MIN(ART_UTA_BBOX_Y0(bb), yf0),
                   MAX(ART_UTA_BBOX_X1(bb), xf1),
                   MAX(ART_UTA_BBOX_Y1(bb), yf1));
      uta->utiles[ix] = bb;
    }
      else
    {
      /* Do a Bresenham-style traversal of the line */
      gdouble dx_dy;
      gdouble x, y;
      gdouble xn, yn;

      /* normalize coordinates to uta origin */
      x0 -= uta->x0 << ART_UTILE_SHIFT;
      y0 -= uta->y0 << ART_UTILE_SHIFT;
      x1 -= uta->x0 << ART_UTILE_SHIFT;
      y1 -= uta->y0 << ART_UTILE_SHIFT;
      if (dy < 0)
        {
          gdouble tmp;

          tmp = x0;
          x0 = x1;
          x1 = tmp;

          tmp = y0;
          y0 = y1;
          y1 = tmp;

          dx = -dx;
          sx = -sx;
          dy = -dy;
          /* we leave sy alone, because it would always be 1,
         and we need it for the rbuf stuff. */
        }
      xt0 = ((gint)floor (x0) >> ART_UTILE_SHIFT);
      xt1 = ((gint)floor (x1) >> ART_UTILE_SHIFT);
      /* now [xy]0 is above [xy]1 */

      ix = yt0 * uta->width + xt0;
      ix1 = yt1 * uta->width + xt1;

      dx_dy = dx / dy;
      x = x0;
      y = y0;
      while (ix != ix1)
        {
          gint dix;

          /* figure out whether next crossing is horizontal or vertical */
          yn = (yt0 + 1) << ART_UTILE_SHIFT;

          /* xn is the intercept with bottom edge of this tile. The
         following expression is careful to result in exactly
         x1 when yn = y1. */
          xn = x1 + dx_dy * (yn - y1);

          if (xt0 != (gint)floor (xn) >> ART_UTILE_SHIFT)
        {
          /* horizontal crossing */
          xt0 += sx;
          dix = sx;
          if (dx > 0)
            {
              xn = xt0 << ART_UTILE_SHIFT;
              yn = y0 + (xn - x0) / dx_dy;

              xf0 = (gint)floor (x) & (ART_UTILE_SIZE - 1);
              xf1 = ART_UTILE_SIZE;
            }
          else
            {
              xn = (xt0 + 1) << ART_UTILE_SHIFT;
              yn = y0 + (xn - x0) / dx_dy;

              xf0 = 0;
              xmaxc = (gint)ceil (x);
              xf1 = xmaxc - ((xt0 + 1) << ART_UTILE_SHIFT);
            }
          ymaxf = (gint)floor (yn);
          ymaxc = (gint)ceil (yn);
          yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
        }
          else
        {
          /* vertical crossing */
          dix = uta->width;
          xf0 = (gint)floor (MIN(x, xn)) & (ART_UTILE_SIZE - 1);
          xmax = MAX(x, xn);
          xmaxc = (gint)ceil (xmax);
          xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
          yf1 = ART_UTILE_SIZE;

          if (rbuf != NULL)
            rbuf[yt0 * rbuf_rowstride + xt0] += sy;

          yt0++;
        }
          yf0 = (gint)floor (y) & (ART_UTILE_SIZE - 1);
          bb = uta->utiles[ix];
          if (bb == 0)
        bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
          else
        bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
                       MIN(ART_UTA_BBOX_Y0(bb), yf0),
                       MAX(ART_UTA_BBOX_X1(bb), xf1),
                       MAX(ART_UTA_BBOX_Y1(bb), yf1));
          uta->utiles[ix] = bb;

          x = xn;
          y = yn;
          ix += dix;
        }
      xmax = MAX(x, x1);
      xmaxc = ceil (xmax);
      ymaxc = ceil (y1);
      xf0 = (gint)floor (MIN(x1, x)) & (ART_UTILE_SIZE - 1);
      yf0 = (gint)floor (y) & (ART_UTILE_SIZE - 1);
      xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
      yf1 = ymaxc - (yt0 << ART_UTILE_SHIFT);
      bb = uta->utiles[ix];
      if (bb == 0)
        bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
      else
        bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
                   MIN(ART_UTA_BBOX_Y0(bb), yf0),
                   MAX(ART_UTA_BBOX_X1(bb), xf1),
                   MAX(ART_UTA_BBOX_Y1(bb), yf1));
      uta->utiles[ix] = bb;
    }
    }
}

/**
 * art_uta_from_vpath: Generate uta covering a vpath.
 * @vec: The source vpath.
 *
 * Generates a uta covering @vec. The resulting uta is of course
 * approximate, ie it may cover more pixels than covered by @vec.
 *
 * Return value: the new uta.
 **/
ArtUta *
art_uta_from_vpath (const ArtVpath *vec)
{
  ArtUta *uta;
  ArtIRect bbox;
  gint *rbuf;
  gint i;
  gdouble x, y;
  gint sum;
  gint xt, yt;
  ArtUtaBbox *utiles;
  ArtUtaBbox bb;
  gint width;
  gint height;
  gint ix;

  art_vpath_bbox_irect (vec, &bbox);

  uta = art_uta_new_coords (bbox.x0, bbox.y0, bbox.x1, bbox.y1);

  width = uta->width;
  height = uta->height;
  utiles = uta->utiles;

  rbuf = art_new (int, width * height);
  for (i = 0; i < width * height; i++)
    rbuf[i] = 0;

  x = 0;
  y = 0;
  for (i = 0; vec[i].code != ART_END; i++)
    {
      switch (vec[i].code)
    {
    case ART_MOVETO:
      x = vec[i].x;
      y = vec[i].y;
      break;
    case ART_LINETO:
      art_uta_add_line (uta, vec[i].x, vec[i].y, x, y, rbuf, width);
      x = vec[i].x;
      y = vec[i].y;
      break;
    default:
      /* this shouldn't happen */
          art_free (rbuf);
          art_free (uta);
          return NULL;
    }
    }

  /* now add in the filling from rbuf */
  ix = 0;
  for (yt = 0; yt < height; yt++)
    {
      sum = 0;
      for (xt = 0; xt < width; xt++)
    {
      sum += rbuf[ix];
      /* Nonzero winding rule - others are possible, but hardly
         worth it. */
      if (sum != 0)
        {
          bb = utiles[ix];
          bb &= 0xffff0000;
          bb |= (ART_UTILE_SIZE << 8) | ART_UTILE_SIZE;
          utiles[ix] = bb;
          if (xt != width - 1)
        {
          bb = utiles[ix + 1];
          bb &= 0xffff00;
          bb |= ART_UTILE_SIZE;
          utiles[ix + 1] = bb;
        }
          if (yt != height - 1)
        {
          bb = utiles[ix + width];
          bb &= 0xff0000ff;
          bb |= ART_UTILE_SIZE << 8;
          utiles[ix + width] = bb;
          if (xt != width - 1)
            {
              utiles[ix + width + 1] &= 0xffff;
            }
        }
        }
      ix++;
    }
    }

  art_free (rbuf);

  return uta;
}