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 *
art_svp_merge(const ArtSVP * svp1,const ArtSVP * svp2)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
print_ps_vpath(ArtVpath * vpath)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
print_ps_svp(ArtSVP * vpath)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 *
art_svp_merge_perturbed(const ArtSVP * svp1,const ArtSVP * svp2)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 *
art_svp_union(const ArtSVP * svp1,const ArtSVP * svp2)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 *
art_svp_intersect(const ArtSVP * svp1,const ArtSVP * svp2)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 *
art_svp_diff(const ArtSVP * svp1,const ArtSVP * svp2)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 *
art_svp_minus(const ArtSVP * svp1,const ArtSVP * svp2)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 */
402