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 #ifdef ROBIN_DEBUG
290 dump_svp("art_svp_intersect svp1", svp1);
291 dump_svp("art_svp_intersect svp2", svp2);
292 #endif
293
294 svp3 = art_svp_merge (svp1, svp2);
295 swr = art_svp_writer_rewind_new (ART_WIND_RULE_INTERSECT);
296 art_svp_intersector (svp3, swr);
297 svp_new = art_svp_writer_rewind_reap (swr);
298 art_free (svp3); /* shallow free because svp3 contains shared segments */
299 #ifdef ROBIN_DEBUG
300 dump_svp("art_svp_intersect svp_new", svp_new);
301 #endif
302
303 return svp_new;
304 #else
305 ArtSVP *svp3, *svp4, *svp_new;
306
307 svp3 = art_svp_merge_perturbed (svp1, svp2);
308 svp4 = art_svp_uncross (svp3);
309 art_svp_free (svp3);
310
311 svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_INTERSECT);
312 art_svp_free (svp4);
313 return svp_new;
314 #endif
315 }
316
317 /* Compute the symmetric difference of two vector paths.
318
319 Status of this routine:
320
321 Basic correctness: Seems to work.
322
323 Numerical stability: We cheat (adding random perturbation). Thus,
324 it seems very likely that no numerical stability problems will be
325 seen in practice.
326
327 Speed: We could do a lot better by scanning through the svp
328 representations and culling out any segments that are exactly
329 identical. It would also be better if we didn't go to unsorted
330 vector path and back to add the perturbation.
331
332 Precision: Awful. In the case of inputs which are similar (the
333 common case for canvas display), the entire outline is "hairy." In
334 addition, the perturbation fuzzes the coordinates slightly. It can
335 be used as a conservative approximation.
336
337 */
338
339 /**
340 * art_svp_diff: Compute the symmetric difference of two sorted vector paths.
341 * @svp1: One sorted vector path.
342 * @svp2: The other sorted vector path.
343 *
344 * Computes the symmetric of the two argument svp's. Given two svp's
345 * with winding numbers of 0 and 1 everywhere, the resulting winding
346 * number will be 1 where either, but not both, of the argument svp's
347 * has a winding number 1, 0 otherwise. The result is newly allocated.
348 *
349 * Currently, this routine has accuracy problems pending the
350 * implementation of the new intersector.
351 *
352 * Return value: The symmetric difference of @svp1 and @svp2.
353 **/
354 ArtSVP *
art_svp_diff(const ArtSVP * svp1,const ArtSVP * svp2)355 art_svp_diff (const ArtSVP *svp1, const ArtSVP *svp2)
356 {
357 #ifdef ART_USE_NEW_INTERSECTOR
358 ArtSVP *svp3, *svp_new;
359 ArtSvpWriter *swr;
360
361 svp3 = art_svp_merge (svp1, svp2);
362 swr = art_svp_writer_rewind_new (ART_WIND_RULE_ODDEVEN);
363 art_svp_intersector (svp3, swr);
364 svp_new = art_svp_writer_rewind_reap (swr);
365 art_free (svp3); /* shallow free because svp3 contains shared segments */
366
367 return svp_new;
368 #else
369 ArtSVP *svp3, *svp4, *svp_new;
370
371 svp3 = art_svp_merge_perturbed (svp1, svp2);
372 svp4 = art_svp_uncross (svp3);
373 art_svp_free (svp3);
374
375 svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_ODDEVEN);
376 art_svp_free (svp4);
377 return svp_new;
378 #endif
379 }
380
381 #ifdef ART_USE_NEW_INTERSECTOR
382 ArtSVP *
art_svp_minus(const ArtSVP * svp1,const ArtSVP * svp2)383 art_svp_minus (const ArtSVP *svp1, const ArtSVP *svp2)
384 {
385 ArtSVP *svp2_mod;
386 ArtSVP *svp3, *svp_new;
387 ArtSvpWriter *swr;
388 int i;
389
390 svp2_mod = (ArtSVP *) svp2; /* get rid of the const for a while */
391
392 /* First invert svp2 to "turn it inside out" */
393 for (i = 0; i < svp2_mod->n_segs; i++)
394 svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir;
395
396 svp3 = art_svp_merge (svp1, svp2_mod);
397 swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
398 art_svp_intersector (svp3, swr);
399 svp_new = art_svp_writer_rewind_reap (swr);
400 art_free (svp3); /* shallow free because svp3 contains shared segments */
401
402 /* Flip svp2 back to its original state */
403 for (i = 0; i < svp2_mod->n_segs; i++)
404 svp2_mod->segs[i].dir = !svp2_mod->segs[i].dir;
405
406 return svp_new;
407 }
408 #endif /* ART_USE_NEW_INTERSECTOR */
409