drop parameters into output device as well as input device
[swftools.git] / 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 */