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