X-Git-Url: http://git.asbjorn.biz/?a=blobdiff_plain;f=lib%2Fart%2Fart_svp_ops.c;fp=lib%2Fart%2Fart_svp_ops.c;h=5bb837c5ac9f1d596837bead3a9b2a1cfe4f28d0;hb=418ef05b5d0b74e6f19200ffa40bcc3afccb5029;hp=0000000000000000000000000000000000000000;hpb=c1f4a906117e98e2f4ba59abc1ce153e8129bc19;p=swftools.git

diff --git a/lib/art/art_svp_ops.c b/lib/art/art_svp_ops.c
new file mode 100644
index 0000000..5bb837c
--- /dev/null
+++ b/lib/art/art_svp_ops.c
@@ -0,0 +1,401 @@
+/* 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.
+ */
+
+#define noVERBOSE
+
+/* Vector path set operations, over sorted vpaths. */
+
+#include "config.h"
+#include "art_svp_ops.h"
+
+#include "art_misc.h"
+
+#include "art_svp.h"
+#include "art_vpath.h"
+#include "art_svp_vpath.h"
+#include "art_svp.h"
+#ifdef ART_USE_NEW_INTERSECTOR
+#include "art_svp_intersect.h"
+#else
+#include "art_svp_wind.h"
+#endif
+#include "art_vpath_svp.h"
+
+/* Merge the segments of the two svp's. The resulting svp will share
+   segments with args passed in, so be super-careful with the
+   allocation.  */
+/**
+ * art_svp_merge: Merge the segments of two svp's.
+ * @svp1: One svp to merge.
+ * @svp2: The other svp to merge.
+ *
+ * Merges the segments of two SVP's into a new one. The resulting
+ * #ArtSVP data structure will share the segments of the argument
+ * svp's, so it is probably a good idea to free it shallowly,
+ * especially if the arguments will be freed with art_svp_free().
+ *
+ * Return value: The merged #ArtSVP.
+ **/
+static ArtSVP *
+art_svp_merge (const ArtSVP *svp1, const ArtSVP *svp2)
+{
+  ArtSVP *svp_new;
+  int ix;
+  int ix1, ix2;
+
+  svp_new = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
+				 (svp1->n_segs + svp2->n_segs - 1) *
+				 sizeof(ArtSVPSeg));
+  ix1 = 0;
+  ix2 = 0;
+  for (ix = 0; ix < svp1->n_segs + svp2->n_segs; ix++)
+    {
+      if (ix1 < svp1->n_segs &&
+	  (ix2 == svp2->n_segs ||
+	   art_svp_seg_compare (&svp1->segs[ix1], &svp2->segs[ix2]) < 1))
+	svp_new->segs[ix] = svp1->segs[ix1++];
+      else
+	svp_new->segs[ix] = svp2->segs[ix2++];
+    }
+
+  svp_new->n_segs = ix;
+  return svp_new;
+}
+
+#ifdef VERBOSE
+
+#define XOFF 50
+#define YOFF 700
+
+static void
+print_ps_vpath (ArtVpath *vpath)
+{
+  int i;
+
+  printf ("gsave %d %d translate 1 -1 scale\n", XOFF, YOFF);
+  for (i = 0; vpath[i].code != ART_END; i++)
+    {
+      switch (vpath[i].code)
+	{
+	case ART_MOVETO:
+	  printf ("%g %g moveto\n", vpath[i].x, vpath[i].y);
+	  break;
+	case ART_LINETO:
+	  printf ("%g %g lineto\n", vpath[i].x, vpath[i].y);
+	  break;
+	default:
+	  break;
+	}
+    }
+  printf ("stroke grestore showpage\n");
+}
+
+#define DELT 4
+
+static void
+print_ps_svp (ArtSVP *vpath)
+{
+  int i, j;
+
+  printf ("%% begin\n");
+  for (i = 0; i < vpath->n_segs; i++)
+    {
+      printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0);
+      for (j = 0; j < vpath->segs[i].n_points; j++)
+	{
+	  printf ("%g %g %s\n",
+		  XOFF + vpath->segs[i].points[j].x,
+		  YOFF - vpath->segs[i].points[j].y,
+		  j ? "lineto" : "moveto");
+	}
+      printf ("%g %g moveto %g %g lineto %g %g lineto %g %g lineto stroke\n",
+	      XOFF + vpath->segs[i].points[0].x - DELT,
+	      YOFF - DELT - vpath->segs[i].points[0].y,
+	      XOFF + vpath->segs[i].points[0].x - DELT,
+	      YOFF - vpath->segs[i].points[0].y,
+	      XOFF + vpath->segs[i].points[0].x + DELT,
+	      YOFF - vpath->segs[i].points[0].y,
+	      XOFF + vpath->segs[i].points[0].x + DELT,
+	      YOFF - DELT - vpath->segs[i].points[0].y);
+      printf ("%g %g moveto %g %g lineto %g %g lineto %g %g lineto stroke\n",
+	      XOFF + vpath->segs[i].points[j - 1].x - DELT,
+	      YOFF + DELT - vpath->segs[i].points[j - 1].y,
+	      XOFF + vpath->segs[i].points[j - 1].x - DELT,
+	      YOFF - vpath->segs[i].points[j - 1].y,
+	      XOFF + vpath->segs[i].points[j - 1].x + DELT,
+	      YOFF - vpath->segs[i].points[j - 1].y,
+	      XOFF + vpath->segs[i].points[j - 1].x + DELT,
+	      YOFF + DELT - vpath->segs[i].points[j - 1].y);
+      printf ("stroke\n");
+    }
+
+  printf ("showpage\n");
+}
+#endif
+
+#ifndef ART_USE_NEW_INTERSECTOR
+static ArtSVP *
+art_svp_merge_perturbed (const ArtSVP *svp1, const ArtSVP *svp2)
+{
+  ArtVpath *vpath1, *vpath2;
+  ArtVpath *vpath1_p, *vpath2_p;
+  ArtSVP *svp1_p, *svp2_p;
+  ArtSVP *svp_new;
+
+  vpath1 = art_vpath_from_svp (svp1);
+  vpath1_p = art_vpath_perturb (vpath1);
+  art_free (vpath1);
+  svp1_p = art_svp_from_vpath (vpath1_p);
+  art_free (vpath1_p);
+
+  vpath2 = art_vpath_from_svp (svp2);
+  vpath2_p = art_vpath_perturb (vpath2);
+  art_free (vpath2);
+  svp2_p = art_svp_from_vpath (vpath2_p);
+  art_free (vpath2_p);
+
+  svp_new = art_svp_merge (svp1_p, svp2_p);
+#ifdef VERBOSE
+  print_ps_svp (svp1_p);
+  print_ps_svp (svp2_p);
+  print_ps_svp (svp_new);
+#endif
+  art_free (svp1_p);
+  art_free (svp2_p);
+
+  return svp_new;
+}
+#endif
+
+/* Compute the union of two vector paths.
+
+   Status of this routine:
+
+   Basic correctness: Seems to work.
+
+   Numerical stability: We cheat (adding random perturbation). Thus,
+   it seems very likely that no numerical stability problems will be
+   seen in practice.
+
+   Speed: Would be better if we didn't go to unsorted vector path
+   and back to add the perturbation.
+
+   Precision: The perturbation fuzzes the coordinates slightly. In
+   cases of butting segments, razor thin long holes may appear.
+
+*/
+/**
+ * art_svp_union: Compute the union of two sorted vector paths.
+ * @svp1: One sorted vector path.
+ * @svp2: The other sorted vector path.
+ *
+ * Computes the union of the two argument svp's. Given two svp's with
+ * winding numbers of 0 and 1 everywhere, the resulting winding number
+ * will be 1 where either (or both) of the argument svp's has a
+ * winding number 1, 0 otherwise. The result is newly allocated.
+ *
+ * Currently, this routine has accuracy problems pending the
+ * implementation of the new intersector.
+ *
+ * Return value: The union of @svp1 and @svp2.
+ **/
+ArtSVP *
+art_svp_union (const ArtSVP *svp1, const ArtSVP *svp2)
+{
+#ifdef ART_USE_NEW_INTERSECTOR 
+  ArtSVP *svp3, *svp_new;
+  ArtSvpWriter *swr;
+
+  svp3 = art_svp_merge (svp1, svp2);
+  swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
+  art_svp_intersector (svp3, swr);
+  svp_new = art_svp_writer_rewind_reap (swr);
+  art_free (svp3); /* shallow free because svp3 contains shared segments */
+
+  return svp_new;
+#else
+  ArtSVP *svp3, *svp4, *svp_new;
+
+  svp3 = art_svp_merge_perturbed (svp1, svp2);
+  svp4 = art_svp_uncross (svp3);
+  art_svp_free (svp3);
+
+  svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_POSITIVE);
+#ifdef VERBOSE
+  print_ps_svp (svp4);
+  print_ps_svp (svp_new);
+#endif
+  art_svp_free (svp4);
+  return svp_new;
+#endif
+}
+
+/* Compute the intersection of two vector paths.
+
+   Status of this routine:
+
+   Basic correctness: Seems to work.
+
+   Numerical stability: We cheat (adding random perturbation). Thus,
+   it seems very likely that no numerical stability problems will be
+   seen in practice.
+
+   Speed: Would be better if we didn't go to unsorted vector path
+   and back to add the perturbation.
+
+   Precision: The perturbation fuzzes the coordinates slightly. In
+   cases of butting segments, razor thin long isolated segments may
+   appear.
+
+*/
+
+/**
+ * art_svp_intersect: Compute the intersection of two sorted vector paths.
+ * @svp1: One sorted vector path.
+ * @svp2: The other sorted vector path.
+ *
+ * Computes the intersection of the two argument svp's. Given two
+ * svp's with winding numbers of 0 and 1 everywhere, the resulting
+ * winding number will be 1 where both of the argument svp's has a
+ * winding number 1, 0 otherwise. The result is newly allocated.
+ *
+ * Currently, this routine has accuracy problems pending the
+ * implementation of the new intersector.
+ *
+ * Return value: The intersection of @svp1 and @svp2.
+ **/
+ArtSVP *
+art_svp_intersect (const ArtSVP *svp1, const ArtSVP *svp2)
+{
+#ifdef ART_USE_NEW_INTERSECTOR 
+  ArtSVP *svp3, *svp_new;
+  ArtSvpWriter *swr;
+
+  svp3 = art_svp_merge (svp1, svp2);
+  swr = art_svp_writer_rewind_new (ART_WIND_RULE_INTERSECT);
+  art_svp_intersector (svp3, swr);
+  svp_new = art_svp_writer_rewind_reap (swr);
+  art_free (svp3); /* shallow free because svp3 contains shared segments */
+
+  return svp_new;
+#else
+  ArtSVP *svp3, *svp4, *svp_new;
+
+  svp3 = art_svp_merge_perturbed (svp1, svp2);
+  svp4 = art_svp_uncross (svp3);
+  art_svp_free (svp3);
+
+  svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_INTERSECT);
+  art_svp_free (svp4);
+  return svp_new;
+#endif
+}
+
+/* Compute the symmetric difference of two vector paths.
+
+   Status of this routine:
+
+   Basic correctness: Seems to work.
+
+   Numerical stability: We cheat (adding random perturbation). Thus,
+   it seems very likely that no numerical stability problems will be
+   seen in practice.
+
+   Speed: We could do a lot better by scanning through the svp
+   representations and culling out any segments that are exactly
+   identical. It would also be better if we didn't go to unsorted
+   vector path and back to add the perturbation.
+
+   Precision: Awful. In the case of inputs which are similar (the
+   common case for canvas display), the entire outline is "hairy." In
+   addition, the perturbation fuzzes the coordinates slightly. It can
+   be used as a conservative approximation.
+
+*/
+
+/**
+ * art_svp_diff: Compute the symmetric difference of two sorted vector paths.
+ * @svp1: One sorted vector path.
+ * @svp2: The other sorted vector path.
+ *
+ * Computes the symmetric of the two argument svp's. Given two svp's
+ * with winding numbers of 0 and 1 everywhere, the resulting winding
+ * number will be 1 where either, but not both, of the argument svp's
+ * has a winding number 1, 0 otherwise. The result is newly allocated.
+ *
+ * Currently, this routine has accuracy problems pending the
+ * implementation of the new intersector.
+ *
+ * Return value: The symmetric difference of @svp1 and @svp2.
+ **/
+ArtSVP *
+art_svp_diff (const ArtSVP *svp1, const ArtSVP *svp2)
+{
+#ifdef ART_USE_NEW_INTERSECTOR 
+  ArtSVP *svp3, *svp_new;
+  ArtSvpWriter *swr;
+
+  svp3 = art_svp_merge (svp1, svp2);
+  swr = art_svp_writer_rewind_new (ART_WIND_RULE_ODDEVEN);
+  art_svp_intersector (svp3, swr);
+  svp_new = art_svp_writer_rewind_reap (swr);
+  art_free (svp3); /* shallow free because svp3 contains shared segments */
+
+  return svp_new;
+#else
+  ArtSVP *svp3, *svp4, *svp_new;
+
+  svp3 = art_svp_merge_perturbed (svp1, svp2);
+  svp4 = art_svp_uncross (svp3);
+  art_svp_free (svp3);
+
+  svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_ODDEVEN);
+  art_svp_free (svp4);
+  return svp_new;
+#endif
+}
+
+#ifdef ART_USE_NEW_INTERSECTOR 
+ArtSVP *
+art_svp_minus (const ArtSVP *svp1, const ArtSVP *svp2)
+{
+  ArtSVP *svp2_mod;
+  ArtSVP *svp3, *svp_new;
+  ArtSvpWriter *swr;
+  int i;
+
+  svp2_mod = (ArtSVP *) svp2; /* get rid of the const for a while */
+
+  /* First invert svp2 to "turn it inside out" */
+  for (i = 0; i < svp2_mod->n_segs; i++)
+    svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir;
+
+  svp3 = art_svp_merge (svp1, svp2_mod);
+  swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
+  art_svp_intersector (svp3, swr);
+  svp_new = art_svp_writer_rewind_reap (swr);
+  art_free (svp3); /* shallow free because svp3 contains shared segments */
+
+  /* Flip svp2 back to its original state */
+  for (i = 0; i < svp2_mod->n_segs; i++)
+    svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir;
+
+  return svp_new;
+}
+#endif /* ART_USE_NEW_INTERSECTOR */