--- /dev/null
+/* 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, double x0, double y0, double x1, double y1,
+ int *rbuf, int rbuf_rowstride)
+{
+ int xmin, ymin;
+ double xmax, ymax;
+ int xmaxf, ymaxf;
+ int xmaxc, ymaxc;
+ int xt0, yt0;
+ int xt1, yt1;
+ int xf0, yf0;
+ int xf1, yf1;
+ int 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
+ {
+ double dx, dy;
+ int 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 */
+ double dx_dy;
+ double x, y;
+ double 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)
+ {
+ double 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 = ((int)floor (x0) >> ART_UTILE_SHIFT);
+ xt1 = ((int)floor (x1) >> ART_UTILE_SHIFT);
+ /* now [xy]0 is above [xy]1 */
+
+ ix = yt0 * uta->width + xt0;
+ ix1 = yt1 * uta->width + xt1;
+#ifdef VERBOSE
+ printf ("%% ix = %d,%d; ix1 = %d,%d\n", xt0, yt0, xt1, yt1);
+#endif
+
+ dx_dy = dx / dy;
+ x = x0;
+ y = y0;
+ while (ix != ix1)
+ {
+ int dix;
+
+ /* figure out whether next crossing is horizontal or vertical */
+#ifdef VERBOSE
+ printf ("%% %d,%d\n", xt0, yt0);
+#endif
+ 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 != (int)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 = (int)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 = (int)ceil (x);
+ xf1 = xmaxc - ((xt0 + 1) << ART_UTILE_SHIFT);
+ }
+ ymaxf = (int)floor (yn);
+ ymaxc = (int)ceil (yn);
+ yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
+ }
+ else
+ {
+ /* vertical crossing */
+ dix = uta->width;
+ xf0 = (int)floor (MIN(x, xn)) & (ART_UTILE_SIZE - 1);
+ xmax = MAX(x, xn);
+ xmaxc = (int)ceil (xmax);
+ xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
+ yf1 = ART_UTILE_SIZE;
+
+ if (rbuf != NULL)
+ rbuf[yt0 * rbuf_rowstride + xt0] += sy;
+
+ yt0++;
+ }
+ yf0 = (int)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 = (int)floor (MIN(x1, x)) & (ART_UTILE_SIZE - 1);
+ yf0 = (int)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;
+ int *rbuf;
+ int i;
+ double x, y;
+ int sum;
+ int xt, yt;
+ ArtUtaBbox *utiles;
+ ArtUtaBbox bb;
+ int width;
+ int height;
+ int 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;
+}
git.asbjorn.biz / swftools.git / blobdiff