lib/art/art_svp_ops.c

   1 /* Libart_LGPL - library of basic graphic primitives
   2  * Copyright (C) 1998-2000 Raph Levien
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #define noVERBOSE
  21
  22 /* Vector path set operations, over sorted vpaths. */
  23
  24 #include "config.h"
  25 #include "art_svp_ops.h"
  26
  27 #include "art_misc.h"
  28
  29 #include "art_svp.h"
  30 #include "art_vpath.h"
  31 #include "art_svp_vpath.h"
  32 #include "art_svp.h"
  33 #ifdef ART_USE_NEW_INTERSECTOR
  34 #include "art_svp_intersect.h"
  35 #else
  36 #include "art_svp_wind.h"
  37 #endif
  38 #include "art_vpath_svp.h"
  39
  40 /* Merge the segments of the two svp's. The resulting svp will share
  41    segments with args passed in, so be super-careful with the
  42    allocation.  */
  43 /**
  44  * art_svp_merge: Merge the segments of two svp's.
  45  * @svp1: One svp to merge.
  46  * @svp2: The other svp to merge.
  47  *
  48  * Merges the segments of two SVP's into a new one. The resulting
  49  * #ArtSVP data structure will share the segments of the argument
  50  * svp's, so it is probably a good idea to free it shallowly,
  51  * especially if the arguments will be freed with art_svp_free().
  52  *
  53  * Return value: The merged #ArtSVP.
  54  **/
  55 static ArtSVP *
  56 art_svp_merge (const ArtSVP *svp1, const ArtSVP *svp2)
  57 {
  58   ArtSVP *svp_new;
  59   int ix;
  60   int ix1, ix2;
  61
  62   svp_new = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
  63                                  (svp1->n_segs + svp2->n_segs - 1) *
  64                                  sizeof(ArtSVPSeg));
  65   ix1 = 0;
  66   ix2 = 0;
  67   for (ix = 0; ix < svp1->n_segs + svp2->n_segs; ix++)
  68     {
  69       if (ix1 < svp1->n_segs &&
  70           (ix2 == svp2->n_segs ||
  71            art_svp_seg_compare (&svp1->segs[ix1], &svp2->segs[ix2]) < 1))
  72         svp_new->segs[ix] = svp1->segs[ix1++];
  73       else
  74         svp_new->segs[ix] = svp2->segs[ix2++];
  75     }
  76
  77   svp_new->n_segs = ix;
  78   return svp_new;
  79 }
  80
  81 #ifdef VERBOSE
  82
  83 #define XOFF 50
  84 #define YOFF 700
  85
  86 static void
  87 print_ps_vpath (ArtVpath *vpath)
  88 {
  89   int i;
  90
  91   printf ("gsave %d %d translate 1 -1 scale\n", XOFF, YOFF);
  92   for (i = 0; vpath[i].code != ART_END; i++)
  93     {
  94       switch (vpath[i].code)
  95         {
  96         case ART_MOVETO:
  97           printf ("%g %g moveto\n", vpath[i].x, vpath[i].y);
  98           break;
  99         case ART_LINETO:
 100           printf ("%g %g lineto\n", vpath[i].x, vpath[i].y);
 101           break;
 102         default:
 103           break;
 104         }
 105     }
 106   printf ("stroke grestore showpage\n");
 107 }
 108
 109 #define DELT 4
 110
 111 static void
 112 print_ps_svp (ArtSVP *vpath)
 113 {
 114   int i, j;
 115
 116   printf ("%% begin\n");
 117   for (i = 0; i < vpath->n_segs; i++)
 118     {
 119       printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0);
 120       for (j = 0; j < vpath->segs[i].n_points; j++)
 121         {
 122           printf ("%g %g %s\n",
 123                   XOFF + vpath->segs[i].points[j].x,
 124                   YOFF - vpath->segs[i].points[j].y,
 125                   j ? "lineto" : "moveto");
 126         }
 127       printf ("%g %g moveto %g %g lineto %g %g lineto %g %g lineto stroke\n",
 128               XOFF + vpath->segs[i].points[0].x - DELT,
 129               YOFF - DELT - vpath->segs[i].points[0].y,
 130               XOFF + vpath->segs[i].points[0].x - DELT,
 131               YOFF - vpath->segs[i].points[0].y,
 132               XOFF + vpath->segs[i].points[0].x + DELT,
 133               YOFF - vpath->segs[i].points[0].y,
 134               XOFF + vpath->segs[i].points[0].x + DELT,
 135               YOFF - DELT - vpath->segs[i].points[0].y);
 136       printf ("%g %g moveto %g %g lineto %g %g lineto %g %g lineto stroke\n",
 137               XOFF + vpath->segs[i].points[j - 1].x - DELT,
 138               YOFF + DELT - vpath->segs[i].points[j - 1].y,
 139               XOFF + vpath->segs[i].points[j - 1].x - DELT,
 140               YOFF - vpath->segs[i].points[j - 1].y,
 141               XOFF + vpath->segs[i].points[j - 1].x + DELT,
 142               YOFF - vpath->segs[i].points[j - 1].y,
 143               XOFF + vpath->segs[i].points[j - 1].x + DELT,
 144               YOFF + DELT - vpath->segs[i].points[j - 1].y);
 145       printf ("stroke\n");
 146     }
 147
 148   printf ("showpage\n");
 149 }
 150 #endif
 151
 152 #ifndef ART_USE_NEW_INTERSECTOR
 153 static ArtSVP *
 154 art_svp_merge_perturbed (const ArtSVP *svp1, const ArtSVP *svp2)
 155 {
 156   ArtVpath *vpath1, *vpath2;
 157   ArtVpath *vpath1_p, *vpath2_p;
 158   ArtSVP *svp1_p, *svp2_p;
 159   ArtSVP *svp_new;
 160
 161   vpath1 = art_vpath_from_svp (svp1);
 162   vpath1_p = art_vpath_perturb (vpath1);
 163   art_free (vpath1);
 164   svp1_p = art_svp_from_vpath (vpath1_p);
 165   art_free (vpath1_p);
 166
 167   vpath2 = art_vpath_from_svp (svp2);
 168   vpath2_p = art_vpath_perturb (vpath2);
 169   art_free (vpath2);
 170   svp2_p = art_svp_from_vpath (vpath2_p);
 171   art_free (vpath2_p);
 172
 173   svp_new = art_svp_merge (svp1_p, svp2_p);
 174 #ifdef VERBOSE
 175   print_ps_svp (svp1_p);
 176   print_ps_svp (svp2_p);
 177   print_ps_svp (svp_new);
 178 #endif
 179   art_free (svp1_p);
 180   art_free (svp2_p);
 181
 182   return svp_new;
 183 }
 184 #endif
 185
 186 /* Compute the union of two vector paths.
 187
 188    Status of this routine:
 189
 190    Basic correctness: Seems to work.
 191
 192    Numerical stability: We cheat (adding random perturbation). Thus,
 193    it seems very likely that no numerical stability problems will be
 194    seen in practice.
 195
 196    Speed: Would be better if we didn't go to unsorted vector path
 197    and back to add the perturbation.
 198
 199    Precision: The perturbation fuzzes the coordinates slightly. In
 200    cases of butting segments, razor thin long holes may appear.
 201
 202 */
 203 /**
 204  * art_svp_union: Compute the union of two sorted vector paths.
 205  * @svp1: One sorted vector path.
 206  * @svp2: The other sorted vector path.
 207  *
 208  * Computes the union of the two argument svp's. Given two svp's with
 209  * winding numbers of 0 and 1 everywhere, the resulting winding number
 210  * will be 1 where either (or both) of the argument svp's has a
 211  * winding number 1, 0 otherwise. The result is newly allocated.
 212  *
 213  * Currently, this routine has accuracy problems pending the
 214  * implementation of the new intersector.
 215  *
 216  * Return value: The union of @svp1 and @svp2.
 217  **/
 218 ArtSVP *
 219 art_svp_union (const ArtSVP *svp1, const ArtSVP *svp2)
 220 {
 221 #ifdef ART_USE_NEW_INTERSECTOR
 222   ArtSVP *svp3, *svp_new;
 223   ArtSvpWriter *swr;
 224
 225   svp3 = art_svp_merge (svp1, svp2);
 226   swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
 227   art_svp_intersector (svp3, swr);
 228   svp_new = art_svp_writer_rewind_reap (swr);
 229   art_free (svp3); /* shallow free because svp3 contains shared segments */
 230
 231   return svp_new;
 232 #else
 233   ArtSVP *svp3, *svp4, *svp_new;
 234
 235   svp3 = art_svp_merge_perturbed (svp1, svp2);
 236   svp4 = art_svp_uncross (svp3);
 237   art_svp_free (svp3);
 238
 239   svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_POSITIVE);
 240 #ifdef VERBOSE
 241   print_ps_svp (svp4);
 242   print_ps_svp (svp_new);
 243 #endif
 244   art_svp_free (svp4);
 245   return svp_new;
 246 #endif
 247 }
 248
 249 /* Compute the intersection of two vector paths.
 250
 251    Status of this routine:
 252
 253    Basic correctness: Seems to work.
 254
 255    Numerical stability: We cheat (adding random perturbation). Thus,
 256    it seems very likely that no numerical stability problems will be
 257    seen in practice.
 258
 259    Speed: Would be better if we didn't go to unsorted vector path
 260    and back to add the perturbation.
 261
 262    Precision: The perturbation fuzzes the coordinates slightly. In
 263    cases of butting segments, razor thin long isolated segments may
 264    appear.
 265
 266 */
 267
 268 /**
 269  * art_svp_intersect: Compute the intersection of two sorted vector paths.
 270  * @svp1: One sorted vector path.
 271  * @svp2: The other sorted vector path.
 272  *
 273  * Computes the intersection of the two argument svp's. Given two
 274  * svp's with winding numbers of 0 and 1 everywhere, the resulting
 275  * winding number will be 1 where both of the argument svp's has a
 276  * winding number 1, 0 otherwise. The result is newly allocated.
 277  *
 278  * Currently, this routine has accuracy problems pending the
 279  * implementation of the new intersector.
 280  *
 281  * Return value: The intersection of @svp1 and @svp2.
 282  **/
 283 ArtSVP *
 284 art_svp_intersect (const ArtSVP *svp1, const ArtSVP *svp2)
 285 {
 286 #ifdef ART_USE_NEW_INTERSECTOR
 287   ArtSVP *svp3, *svp_new;
 288   ArtSvpWriter *swr;
 289
 290   svp3 = art_svp_merge (svp1, svp2);
 291   swr = art_svp_writer_rewind_new (ART_WIND_RULE_INTERSECT);
 292   art_svp_intersector (svp3, swr);
 293   svp_new = art_svp_writer_rewind_reap (swr);
 294   art_free (svp3); /* shallow free because svp3 contains shared segments */
 295
 296   return svp_new;
 297 #else
 298   ArtSVP *svp3, *svp4, *svp_new;
 299
 300   svp3 = art_svp_merge_perturbed (svp1, svp2);
 301   svp4 = art_svp_uncross (svp3);
 302   art_svp_free (svp3);
 303
 304   svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_INTERSECT);
 305   art_svp_free (svp4);
 306   return svp_new;
 307 #endif
 308 }
 309
 310 /* Compute the symmetric difference of two vector paths.
 311
 312    Status of this routine:
 313
 314    Basic correctness: Seems to work.
 315
 316    Numerical stability: We cheat (adding random perturbation). Thus,
 317    it seems very likely that no numerical stability problems will be
 318    seen in practice.
 319
 320    Speed: We could do a lot better by scanning through the svp
 321    representations and culling out any segments that are exactly
 322    identical. It would also be better if we didn't go to unsorted
 323    vector path and back to add the perturbation.
 324
 325    Precision: Awful. In the case of inputs which are similar (the
 326    common case for canvas display), the entire outline is "hairy." In
 327    addition, the perturbation fuzzes the coordinates slightly. It can
 328    be used as a conservative approximation.
 329
 330 */
 331
 332 /**
 333  * art_svp_diff: Compute the symmetric difference of two sorted vector paths.
 334  * @svp1: One sorted vector path.
 335  * @svp2: The other sorted vector path.
 336  *
 337  * Computes the symmetric of the two argument svp's. Given two svp's
 338  * with winding numbers of 0 and 1 everywhere, the resulting winding
 339  * number will be 1 where either, but not both, of the argument svp's
 340  * has a winding number 1, 0 otherwise. The result is newly allocated.
 341  *
 342  * Currently, this routine has accuracy problems pending the
 343  * implementation of the new intersector.
 344  *
 345  * Return value: The symmetric difference of @svp1 and @svp2.
 346  **/
 347 ArtSVP *
 348 art_svp_diff (const ArtSVP *svp1, const ArtSVP *svp2)
 349 {
 350 #ifdef ART_USE_NEW_INTERSECTOR
 351   ArtSVP *svp3, *svp_new;
 352   ArtSvpWriter *swr;
 353
 354   svp3 = art_svp_merge (svp1, svp2);
 355   swr = art_svp_writer_rewind_new (ART_WIND_RULE_ODDEVEN);
 356   art_svp_intersector (svp3, swr);
 357   svp_new = art_svp_writer_rewind_reap (swr);
 358   art_free (svp3); /* shallow free because svp3 contains shared segments */
 359
 360   return svp_new;
 361 #else
 362   ArtSVP *svp3, *svp4, *svp_new;
 363
 364   svp3 = art_svp_merge_perturbed (svp1, svp2);
 365   svp4 = art_svp_uncross (svp3);
 366   art_svp_free (svp3);
 367
 368   svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_ODDEVEN);
 369   art_svp_free (svp4);
 370   return svp_new;
 371 #endif
 372 }
 373
 374 #ifdef ART_USE_NEW_INTERSECTOR
 375 ArtSVP *
 376 art_svp_minus (const ArtSVP *svp1, const ArtSVP *svp2)
 377 {
 378   ArtSVP *svp2_mod;
 379   ArtSVP *svp3, *svp_new;
 380   ArtSvpWriter *swr;
 381   int i;
 382
 383   svp2_mod = (ArtSVP *) svp2; /* get rid of the const for a while */
 384
 385   /* First invert svp2 to "turn it inside out" */
 386   for (i = 0; i < svp2_mod->n_segs; i++)
 387     svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir;
 388
 389   svp3 = art_svp_merge (svp1, svp2_mod);
 390   swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
 391   art_svp_intersector (svp3, swr);
 392   svp_new = art_svp_writer_rewind_reap (swr);
 393   art_free (svp3); /* shallow free because svp3 contains shared segments */
 394
 395   /* Flip svp2 back to its original state */
 396   for (i = 0; i < svp2_mod->n_segs; i++)
 397     svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir;
 398
 399   return svp_new;
 400 }
 401 #endif /* ART_USE_NEW_INTERSECTOR */