summaryrefslogtreecommitdiffstats
path: root/art_svp_vpath.c
diff options
context:
space:
mode:
Diffstat (limited to 'art_svp_vpath.c')
-rw-r--r--art_svp_vpath.c215
1 files changed, 215 insertions, 0 deletions
diff --git a/art_svp_vpath.c b/art_svp_vpath.c
new file mode 100644
index 0000000..196711a
--- /dev/null
+++ b/art_svp_vpath.c
@@ -0,0 +1,215 @@
+/* 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.
+ */
+
+/* Sort vector paths into sorted vector paths */
+
+#include "config.h"
+#include "art_svp_vpath.h"
+
+#include <stdlib.h>
+#include <math.h>
+
+#include "art_misc.h"
+
+#include "art_vpath.h"
+#include "art_svp.h"
+
+
+/* reverse a list of points in place */
+static void
+reverse_points (ArtPoint *points, int n_points)
+{
+ int i;
+ ArtPoint tmp_p;
+
+ for (i = 0; i < (n_points >> 1); i++)
+ {
+ tmp_p = points[i];
+ points[i] = points[n_points - (i + 1)];
+ points[n_points - (i + 1)] = tmp_p;
+ }
+}
+
+/**
+ * art_svp_from_vpath: Convert a vpath to a sorted vector path.
+ * @vpath: #ArtVPath to convert.
+ *
+ * Converts a vector path into sorted vector path form. The svp form is
+ * more efficient for rendering and other vector operations.
+ *
+ * Basically, the implementation is to traverse the vector path,
+ * generating a new segment for each "run" of points in the vector
+ * path with monotonically increasing Y values. All the resulting
+ * values are then sorted.
+ *
+ * Note: I'm not sure that the sorting rule is correct with respect
+ * to numerical stability issues.
+ *
+ * Return value: Resulting sorted vector path.
+ **/
+ArtSVP *
+art_svp_from_vpath (ArtVpath *vpath)
+{
+ int n_segs, n_segs_max;
+ ArtSVP *svp;
+ int dir;
+ int new_dir;
+ int i;
+ ArtPoint *points;
+ int n_points, n_points_max;
+ double x, y;
+ double x_min, x_max;
+
+ n_segs = 0;
+ n_segs_max = 16;
+ svp = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
+ (n_segs_max - 1) * sizeof(ArtSVPSeg));
+
+ dir = 0;
+ n_points = 0;
+ n_points_max = 0;
+ points = NULL;
+ i = 0;
+
+ x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant,
+ but it makes gcc -Wall -ansi -pedantic happier */
+ x_min = x_max = 0; /* same */
+
+ while (vpath[i].code != ART_END) {
+ if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN)
+ {
+ if (points != NULL && n_points >= 2)
+ {
+ if (n_segs == n_segs_max)
+ {
+ n_segs_max <<= 1;
+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
+ (n_segs_max - 1) *
+ sizeof(ArtSVPSeg));
+ }
+ svp->segs[n_segs].n_points = n_points;
+ svp->segs[n_segs].dir = (dir > 0);
+ if (dir < 0)
+ reverse_points (points, n_points);
+ svp->segs[n_segs].points = points;
+ svp->segs[n_segs].bbox.x0 = x_min;
+ svp->segs[n_segs].bbox.x1 = x_max;
+ svp->segs[n_segs].bbox.y0 = points[0].y;
+ svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
+ n_segs++;
+ points = NULL;
+ }
+
+ if (points == NULL)
+ {
+ n_points_max = 4;
+ points = art_new (ArtPoint, n_points_max);
+ }
+
+ n_points = 1;
+ points[0].x = x = vpath[i].x;
+ points[0].y = y = vpath[i].y;
+ x_min = x;
+ x_max = x;
+ dir = 0;
+ }
+ else /* must be LINETO */
+ {
+ new_dir = (vpath[i].y > y ||
+ (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1;
+ if (dir && dir != new_dir)
+ {
+ /* new segment */
+ x = points[n_points - 1].x;
+ y = points[n_points - 1].y;
+ if (n_segs == n_segs_max)
+ {
+ n_segs_max <<= 1;
+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
+ (n_segs_max - 1) *
+ sizeof(ArtSVPSeg));
+ }
+ svp->segs[n_segs].n_points = n_points;
+ svp->segs[n_segs].dir = (dir > 0);
+ if (dir < 0)
+ reverse_points (points, n_points);
+ svp->segs[n_segs].points = points;
+ svp->segs[n_segs].bbox.x0 = x_min;
+ svp->segs[n_segs].bbox.x1 = x_max;
+ svp->segs[n_segs].bbox.y0 = points[0].y;
+ svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
+ n_segs++;
+
+ n_points = 1;
+ n_points_max = 4;
+ points = art_new (ArtPoint, n_points_max);
+ points[0].x = x;
+ points[0].y = y;
+ x_min = x;
+ x_max = x;
+ }
+
+ if (points != NULL)
+ {
+ if (n_points == n_points_max)
+ art_expand (points, ArtPoint, n_points_max);
+ points[n_points].x = x = vpath[i].x;
+ points[n_points].y = y = vpath[i].y;
+ if (x < x_min) x_min = x;
+ else if (x > x_max) x_max = x;
+ n_points++;
+ }
+ dir = new_dir;
+ }
+ i++;
+ }
+
+ if (points != NULL)
+ {
+ if (n_points >= 2)
+ {
+ if (n_segs == n_segs_max)
+ {
+ n_segs_max <<= 1;
+ svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
+ (n_segs_max - 1) *
+ sizeof(ArtSVPSeg));
+ }
+ svp->segs[n_segs].n_points = n_points;
+ svp->segs[n_segs].dir = (dir > 0);
+ if (dir < 0)
+ reverse_points (points, n_points);
+ svp->segs[n_segs].points = points;
+ svp->segs[n_segs].bbox.x0 = x_min;
+ svp->segs[n_segs].bbox.x1 = x_max;
+ svp->segs[n_segs].bbox.y0 = points[0].y;
+ svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
+ n_segs++;
+ }
+ else
+ art_free (points);
+ }
+
+ svp->n_segs = n_segs;
+
+ qsort (&svp->segs, n_segs, sizeof (ArtSVPSeg), art_svp_seg_compare);
+
+ return svp;
+}
+
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-15 00:32:15 +0000