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 /* Primitive intersection and winding number operations on sorted
21 vector paths.
22
23 These routines are internal to libart, used to construct operations
24 like intersection, union, and difference. */
25
26 #include "config.h"
27 #include "art_svp_wind.h"
28
29 #include <stdio.h> /* for fprintf of debugging info */
30 #include <string.h> /* for memcpy */
31 #include <math.h>
32 #include "art_misc.h"
33
34 #include "art_rect.h"
35 #include "art_svp.h"
36 #ifdef NOSTDERR
37 # define STDERR stdout
38 #else
39 # define STDERR stderr
40 #endif
41
42 #define noVERBOSE
43
44 #define PT_EQ(p1,p2) ((p1).x == (p2).x && (p1).y == (p2).y)
45
46 #define PT_CLOSE(p1,p2) (fabs ((p1).x - (p2).x) < 1e-6 && fabs ((p1).y - (p2).y) < 1e-6)
47
48 /* return nonzero and set *p to the intersection point if the lines
49 z0-z1 and z2-z3 intersect each other. */
50 static int
intersect_lines(ArtPoint z0,ArtPoint z1,ArtPoint z2,ArtPoint z3,ArtPoint * p)51 intersect_lines (ArtPoint z0, ArtPoint z1, ArtPoint z2, ArtPoint z3,
52 ArtPoint *p)
53 {
54 double a01, b01, c01;
55 double a23, b23, c23;
56 double d0, d1, d2, d3;
57 double det;
58
59 /* if the vectors share an endpoint, they don't intersect */
60 if (PT_EQ (z0, z2) || PT_EQ (z0, z3) || PT_EQ (z1, z2) || PT_EQ (z1, z3))
61 return 0;
62
63 #if 0
64 if (PT_CLOSE (z0, z2) || PT_CLOSE (z0, z3) || PT_CLOSE (z1, z2) || PT_CLOSE (z1, z3))
65 return 0;
66 #endif
67
68 /* find line equations ax + by + c = 0 */
69 a01 = z0.y - z1.y;
70 b01 = z1.x - z0.x;
71 c01 = -(z0.x * a01 + z0.y * b01);
72 /* = -((z0.y - z1.y) * z0.x + (z1.x - z0.x) * z0.y)
73 = (z1.x * z0.y - z1.y * z0.x) */
74
75 d2 = a01 * z2.x + b01 * z2.y + c01;
76 d3 = a01 * z3.x + b01 * z3.y + c01;
77 if ((d2 > 0) == (d3 > 0))
78 return 0;
79
80 a23 = z2.y - z3.y;
81 b23 = z3.x - z2.x;
82 c23 = -(z2.x * a23 + z2.y * b23);
83
84 d0 = a23 * z0.x + b23 * z0.y + c23;
85 d1 = a23 * z1.x + b23 * z1.y + c23;
86 if ((d0 > 0) == (d1 > 0))
87 return 0;
88
89 /* now we definitely know that the lines intersect */
90 /* solve the two linear equations ax + by + c = 0 */
91 det = 1.0 / (a01 * b23 - a23 * b01);
92 p->x = det * (c23 * b01 - c01 * b23);
93 p->y = det * (c01 * a23 - c23 * a01);
94
95 return 1;
96 }
97
98 #define EPSILON 1e-6
99
100 static double
trap_epsilon(double v)101 trap_epsilon (double v)
102 {
103 const double epsilon = EPSILON;
104
105 if (v < epsilon && v > -epsilon) return 0;
106 else return v;
107 }
108
109 /* Determine the order of line segments z0-z1 and z2-z3.
110 Return +1 if z2-z3 lies entirely to the right of z0-z1,
111 -1 if entirely to the left,
112 or 0 if overlap.
113
114 The case analysis in this function is quite ugly. The fact that it's
115 almost 200 lines long is ridiculous.
116
117 Ok, so here's the plan to cut it down:
118
119 First, do a bounding line comparison on the x coordinates. This is pretty
120 much the common case, and should go quickly. It also takes care of the
121 case where both lines are horizontal.
122
123 Then, do d0 and d1 computation, but only if a23 is nonzero.
124
125 Finally, do d2 and d3 computation, but only if a01 is nonzero.
126
127 Fall through to returning 0 (this will happen when both lines are
128 horizontal and they overlap).
129 */
130 static int
x_order(ArtPoint z0,ArtPoint z1,ArtPoint z2,ArtPoint z3)131 x_order (ArtPoint z0, ArtPoint z1, ArtPoint z2, ArtPoint z3)
132 {
133 double a01, b01, c01;
134 double a23, b23, c23;
135 double d0, d1, d2, d3;
136
137 if (z0.y == z1.y)
138 {
139 if (z2.y == z3.y)
140 {
141 double x01min, x01max;
142 double x23min, x23max;
143
144 if (z0.x > z1.x)
145 {
146 x01min = z1.x;
147 x01max = z0.x;
148 }
149 else
150 {
151 x01min = z0.x;
152 x01max = z1.x;
153 }
154
155 if (z2.x > z3.x)
156 {
157 x23min = z3.x;
158 x23max = z2.x;
159 }
160 else
161 {
162 x23min = z2.x;
163 x23max = z3.x;
164 }
165
166 if (x23min >= x01max) return 1;
167 else if (x01min >= x23max) return -1;
168 else return 0;
169 }
170 else
171 {
172 /* z0-z1 is horizontal, z2-z3 isn't */
173 a23 = z2.y - z3.y;
174 b23 = z3.x - z2.x;
175 c23 = -(z2.x * a23 + z2.y * b23);
176
177 if (z3.y < z2.y)
178 {
179 a23 = -a23;
180 b23 = -b23;
181 c23 = -c23;
182 }
183
184 d0 = trap_epsilon (a23 * z0.x + b23 * z0.y + c23);
185 d1 = trap_epsilon (a23 * z1.x + b23 * z1.y + c23);
186
187 if (d0 > 0)
188 {
189 if (d1 >= 0) return 1;
190 else return 0;
191 }
192 else if (d0 == 0)
193 {
194 if (d1 > 0) return 1;
195 else if (d1 < 0) return -1;
196 else fprintf (STDERR,"case 1 degenerate\n");
197 return 0;
198 }
199 else /* d0 < 0 */
200 {
201 if (d1 <= 0) return -1;
202 else return 0;
203 }
204 }
205 }
206 else if (z2.y == z3.y)
207 {
208 /* z2-z3 is horizontal, z0-z1 isn't */
209 a01 = z0.y - z1.y;
210 b01 = z1.x - z0.x;
211 c01 = -(z0.x * a01 + z0.y * b01);
212 /* = -((z0.y - z1.y) * z0.x + (z1.x - z0.x) * z0.y)
213 = (z1.x * z0.y - z1.y * z0.x) */
214
215 if (z1.y < z0.y)
216 {
217 a01 = -a01;
218 b01 = -b01;
219 c01 = -c01;
220 }
221
222 d2 = trap_epsilon (a01 * z2.x + b01 * z2.y + c01);
223 d3 = trap_epsilon (a01 * z3.x + b01 * z3.y + c01);
224
225 if (d2 > 0)
226 {
227 if (d3 >= 0) return -1;
228 else return 0;
229 }
230 else if (d2 == 0)
231 {
232 if (d3 > 0) return -1;
233 else if (d3 < 0) return 1;
234 else fprintf (STDERR,"case 2 degenerate\n");
235 return 0;
236 }
237 else /* d2 < 0 */
238 {
239 if (d3 <= 0) return 1;
240 else return 0;
241 }
242 }
243
244 /* find line equations ax + by + c = 0 */
245 a01 = z0.y - z1.y;
246 b01 = z1.x - z0.x;
247 c01 = -(z0.x * a01 + z0.y * b01);
248 /* = -((z0.y - z1.y) * z0.x + (z1.x - z0.x) * z0.y)
249 = -(z1.x * z0.y - z1.y * z0.x) */
250
251 if (a01 > 0)
252 {
253 a01 = -a01;
254 b01 = -b01;
255 c01 = -c01;
256 }
257 /* so now, (a01, b01) points to the left, thus a01 * x + b01 * y + c01
258 is negative if the point lies to the right of the line */
259
260 d2 = trap_epsilon (a01 * z2.x + b01 * z2.y + c01);
261 d3 = trap_epsilon (a01 * z3.x + b01 * z3.y + c01);
262 if (d2 > 0)
263 {
264 if (d3 >= 0) return -1;
265 }
266 else if (d2 == 0)
267 {
268 if (d3 > 0) return -1;
269 else if (d3 < 0) return 1;
270 else
271 fprintf (STDERR, "colinear!\n");
272 }
273 else /* d2 < 0 */
274 {
275 if (d3 <= 0) return 1;
276 }
277
278 a23 = z2.y - z3.y;
279 b23 = z3.x - z2.x;
280 c23 = -(z2.x * a23 + z2.y * b23);
281
282 if (a23 > 0)
283 {
284 a23 = -a23;
285 b23 = -b23;
286 c23 = -c23;
287 }
288 d0 = trap_epsilon (a23 * z0.x + b23 * z0.y + c23);
289 d1 = trap_epsilon (a23 * z1.x + b23 * z1.y + c23);
290 if (d0 > 0)
291 {
292 if (d1 >= 0) return 1;
293 }
294 else if (d0 == 0)
295 {
296 if (d1 > 0) return 1;
297 else if (d1 < 0) return -1;
298 else
299 fprintf (STDERR, "colinear!\n");
300 }
301 else /* d0 < 0 */
302 {
303 if (d1 <= 0) return -1;
304 }
305
306 return 0;
307 }
308
309 /* similar to x_order, but to determine whether point z0 + epsilon lies to
310 the left of the line z2-z3 or to the right */
311 static int
x_order_2(ArtPoint z0,ArtPoint z1,ArtPoint z2,ArtPoint z3)312 x_order_2 (ArtPoint z0, ArtPoint z1, ArtPoint z2, ArtPoint z3)
313 {
314 double a23, b23, c23;
315 double d0, d1;
316
317 a23 = z2.y - z3.y;
318 b23 = z3.x - z2.x;
319 c23 = -(z2.x * a23 + z2.y * b23);
320
321 if (a23 > 0)
322 {
323 a23 = -a23;
324 b23 = -b23;
325 c23 = -c23;
326 }
327
328 d0 = a23 * z0.x + b23 * z0.y + c23;
329
330 if (d0 > EPSILON)
331 return -1;
332 else if (d0 < -EPSILON)
333 return 1;
334
335 d1 = a23 * z1.x + b23 * z1.y + c23;
336 if (d1 > EPSILON)
337 return -1;
338 else if (d1 < -EPSILON)
339 return 1;
340
341 if (z0.x == z1.x && z1.x == z2.x && z2.x == z3.x)
342 {
343 fprintf (STDERR, "x_order_2: colinear and horizontally aligned!\n");
344 return 0;
345 }
346
347 if (z0.x <= z2.x && z1.x <= z2.x && z0.x <= z3.x && z1.x <= z3.x)
348 return -1;
349 if (z0.x >= z2.x && z1.x >= z2.x && z0.x >= z3.x && z1.x >= z3.x)
350 return 1;
351
352 fprintf (STDERR, "x_order_2: colinear!\n");
353 return 0;
354 }
355
356 #ifdef DEAD_CODE
357 /* Traverse the vector path, keeping it in x-sorted order.
358
359 This routine doesn't actually do anything - it's just here for
360 explanatory purposes. */
361 void
traverse(ArtSVP * vp)362 traverse (ArtSVP *vp)
363 {
364 int *active_segs;
365 int n_active_segs;
366 int *cursor;
367 int seg_idx;
368 double y;
369 int tmp1, tmp2;
370 int asi;
371 int i, j;
372
373 active_segs = art_new (int, vp->n_segs);
374 cursor = art_new (int, vp->n_segs);
375
376 n_active_segs = 0;
377 seg_idx = 0;
378 y = vp->segs[0].points[0].y;
379 while (seg_idx < vp->n_segs || n_active_segs > 0)
380 {
381 fprintf (STDERR,"y = %g\n", y);
382 /* delete segments ending at y from active list */
383 for (i = 0; i < n_active_segs; i++)
384 {
385 asi = active_segs[i];
386 if (vp->segs[asi].n_points - 1 == cursor[asi] &&
387 vp->segs[asi].points[cursor[asi]].y == y)
388 {
389 fprintf (STDERR,"deleting %d\n", asi);
390 n_active_segs--;
391 for (j = i; j < n_active_segs; j++)
392 active_segs[j] = active_segs[j + 1];
393 i--;
394 }
395 }
396
397 /* insert new segments into the active list */
398 while (seg_idx < vp->n_segs && y == vp->segs[seg_idx].points[0].y)
399 {
400 cursor[seg_idx] = 0;
401 fprintf (STDERR,"inserting %d\n", seg_idx);
402 for (i = 0; i < n_active_segs; i++)
403 {
404 asi = active_segs[i];
405 if (x_order (vp->segs[asi].points[cursor[asi]],
406 vp->segs[asi].points[cursor[asi] + 1],
407 vp->segs[seg_idx].points[0],
408 vp->segs[seg_idx].points[1]) == -1)
409 break;
410 }
411 tmp1 = seg_idx;
412 for (j = i; j < n_active_segs; j++)
413 {
414 tmp2 = active_segs[j];
415 active_segs[j] = tmp1;
416 tmp1 = tmp2;
417 }
418 active_segs[n_active_segs] = tmp1;
419 n_active_segs++;
420 seg_idx++;
421 }
422
423 /* all active segs cross the y scanline (considering segs to be
424 closed on top and open on bottom) */
425 for (i = 0; i < n_active_segs; i++)
426 {
427 asi = active_segs[i];
428 fprintf (STDERR,"%d (%g, %g) - (%g, %g) %s\n", asi,
429 vp->segs[asi].points[cursor[asi]].x,
430 vp->segs[asi].points[cursor[asi]].y,
431 vp->segs[asi].points[cursor[asi] + 1].x,
432 vp->segs[asi].points[cursor[asi] + 1].y,
433 vp->segs[asi].dir ? "v" : "^");
434 }
435
436 /* advance y to the next event */
437 if (n_active_segs == 0)
438 {
439 if (seg_idx < vp->n_segs)
440 y = vp->segs[seg_idx].points[0].y;
441 /* else we're done */
442 }
443 else
444 {
445 asi = active_segs[0];
446 y = vp->segs[asi].points[cursor[asi] + 1].y;
447 for (i = 1; i < n_active_segs; i++)
448 {
449 asi = active_segs[i];
450 if (y > vp->segs[asi].points[cursor[asi] + 1].y)
451 y = vp->segs[asi].points[cursor[asi] + 1].y;
452 }
453 if (seg_idx < vp->n_segs && y > vp->segs[seg_idx].points[0].y)
454 y = vp->segs[seg_idx].points[0].y;
455 }
456
457 /* advance cursors to reach new y */
458 for (i = 0; i < n_active_segs; i++)
459 {
460 asi = active_segs[i];
461 while (cursor[asi] < vp->segs[asi].n_points - 1 &&
462 y >= vp->segs[asi].points[cursor[asi] + 1].y)
463 cursor[asi]++;
464 }
465 fprintf (STDERR,"\n");
466 }
467 art_free (cursor);
468 art_free (active_segs);
469 }
470 #endif
471
472 /* I believe that the loop will always break with i=1.
473
474 I think I'll want to change this from a simple sorted list to a
475 modified stack. ips[*][0] will get its own data structure, and
476 ips[*] will in general only be allocated if there is an intersection.
477 Finally, the segment can be traced through the initial point
478 (formerly ips[*][0]), backwards through the stack, and finally
479 to cursor + 1.
480
481 This change should cut down on allocation bandwidth, and also
482 eliminate the iteration through n_ipl below.
483
484 */
485 static void
insert_ip(int seg_i,int * n_ips,int * n_ips_max,ArtPoint ** ips,ArtPoint ip)486 insert_ip (int seg_i, int *n_ips, int *n_ips_max, ArtPoint **ips, ArtPoint ip)
487 {
488 int i;
489 ArtPoint tmp1, tmp2;
490 int n_ipl;
491 ArtPoint *ipl;
492
493 n_ipl = n_ips[seg_i]++;
494 if (n_ipl == n_ips_max[seg_i])
495 art_expand (ips[seg_i], ArtPoint, n_ips_max[seg_i]);
496 ipl = ips[seg_i];
497 for (i = 1; i < n_ipl; i++)
498 if (ipl[i].y > ip.y)
499 break;
500 tmp1 = ip;
501 for (; i <= n_ipl; i++)
502 {
503 tmp2 = ipl[i];
504 ipl[i] = tmp1;
505 tmp1 = tmp2;
506 }
507 }
508
509 /* test active segment (i - 1) against i for intersection, if
510 so, add intersection point to both ips lists. */
511 static void
intersect_neighbors(int i,int * active_segs,int * n_ips,int * n_ips_max,ArtPoint ** ips,int * cursor,ArtSVP * vp)512 intersect_neighbors (int i, int *active_segs,
513 int *n_ips, int *n_ips_max, ArtPoint **ips,
514 int *cursor, ArtSVP *vp)
515 {
516 ArtPoint z0, z1, z2, z3;
517 int asi01, asi23;
518 ArtPoint ip;
519
520 asi01 = active_segs[i - 1];
521
522 z0 = ips[asi01][0];
523 if (n_ips[asi01] == 1)
524 z1 = vp->segs[asi01].points[cursor[asi01] + 1];
525 else
526 z1 = ips[asi01][1];
527
528 asi23 = active_segs[i];
529
530 z2 = ips[asi23][0];
531 if (n_ips[asi23] == 1)
532 z3 = vp->segs[asi23].points[cursor[asi23] + 1];
533 else
534 z3 = ips[asi23][1];
535
536 if (intersect_lines (z0, z1, z2, z3, &ip))
537 {
538 #ifdef VERBOSE
539 fprintf (STDERR,"new intersection point: (%g, %g)\n", ip.x, ip.y);
540 #endif
541 insert_ip (asi01, n_ips, n_ips_max, ips, ip);
542 insert_ip (asi23, n_ips, n_ips_max, ips, ip);
543 }
544 }
545
546 /* Add a new point to a segment in the svp.
547
548 Here, we also check to make sure that the segments satisfy nocross.
549 However, this is only valuable for debugging, and could possibly be
550 removed.
551 */
552 static void
svp_add_point(ArtSVP * svp,int * n_points_max,ArtPoint p,int * seg_map,int * active_segs,int n_active_segs,int i)553 svp_add_point (ArtSVP *svp, int *n_points_max,
554 ArtPoint p, int *seg_map, int *active_segs, int n_active_segs,
555 int i)
556 {
557 int asi, asi_left, asi_right;
558 int n_points, n_points_left, n_points_right;
559 ArtSVPSeg *seg;
560
561 asi = seg_map[active_segs[i]];
562 seg = &svp->segs[asi];
563 n_points = seg->n_points;
564 /* find out whether neighboring segments share a point */
565 if (i > 0)
566 {
567 asi_left = seg_map[active_segs[i - 1]];
568 n_points_left = svp->segs[asi_left].n_points;
569 if (n_points_left > 1 &&
570 PT_EQ (svp->segs[asi_left].points[n_points_left - 2],
571 svp->segs[asi].points[n_points - 1]))
572 {
573 /* ok, new vector shares a top point with segment to the left -
574 now, check that it satisfies ordering invariant */
575 if (x_order (svp->segs[asi_left].points[n_points_left - 2],
576 svp->segs[asi_left].points[n_points_left - 1],
577 svp->segs[asi].points[n_points - 1],
578 p) < 1)
579
580 {
581 #ifdef VERBOSE
582 fprintf (STDERR,"svp_add_point: cross on left!\n");
583 #endif
584 }
585 }
586 }
587
588 if (i + 1 < n_active_segs)
589 {
590 asi_right = seg_map[active_segs[i + 1]];
591 n_points_right = svp->segs[asi_right].n_points;
592 if (n_points_right > 1 &&
593 PT_EQ (svp->segs[asi_right].points[n_points_right - 2],
594 svp->segs[asi].points[n_points - 1]))
595 {
596 /* ok, new vector shares a top point with segment to the right -
597 now, check that it satisfies ordering invariant */
598 if (x_order (svp->segs[asi_right].points[n_points_right - 2],
599 svp->segs[asi_right].points[n_points_right - 1],
600 svp->segs[asi].points[n_points - 1],
601 p) > -1)
602 {
603 #ifdef VERBOSE
604 fprintf (STDERR,"svp_add_point: cross on right!\n");
605 #endif
606 }
607 }
608 }
609 if (n_points_max[asi] == n_points)
610 art_expand (seg->points, ArtPoint, n_points_max[asi]);
611 seg->points[n_points] = p;
612 if (p.x < seg->bbox.x0)
613 seg->bbox.x0 = p.x;
614 else if (p.x > seg->bbox.x1)
615 seg->bbox.x1 = p.x;
616 seg->bbox.y1 = p.y;
617 seg->n_points++;
618 }
619
620 #if 0
621 /* find where the segment (currently at i) is supposed to go, and return
622 the target index - if equal to i, then there is no crossing problem.
623
624 "Where it is supposed to go" is defined as following:
625
626 Delete element i, re-insert at position target (bumping everything
627 target and greater to the right).
628 */
629 static int
630 find_crossing (int i, int *active_segs, int n_active_segs,
631 int *cursor, ArtPoint **ips, int *n_ips, ArtSVP *vp)
632 {
633 int asi, asi_left, asi_right;
634 ArtPoint p0, p1;
635 ArtPoint p0l, p1l;
636 ArtPoint p0r, p1r;
637 int target;
638
639 asi = active_segs[i];
640 p0 = ips[asi][0];
641 if (n_ips[asi] == 1)
642 p1 = vp->segs[asi].points[cursor[asi] + 1];
643 else
644 p1 = ips[asi][1];
645
646 for (target = i; target > 0; target--)
647 {
648 asi_left = active_segs[target - 1];
649 p0l = ips[asi_left][0];
650 if (n_ips[asi_left] == 1)
651 p1l = vp->segs[asi_left].points[cursor[asi_left] + 1];
652 else
653 p1l = ips[asi_left][1];
654 if (!PT_EQ (p0, p0l))
655 break;
656
657 #ifdef VERBOSE
658 fprintf (STDERR,"point matches on left (%g, %g) - (%g, %g) x (%g, %g) - (%g, %g)!\n",
659 p0l.x, p0l.y, p1l.x, p1l.y, p0.x, p0.y, p1.x, p1.y);
660 #endif
661 if (x_order (p0l, p1l, p0, p1) == 1)
662 break;
663
664 #ifdef VERBOSE
665 fprintf (STDERR,"scanning to the left (i=%d, target=%d)\n", i, target);
666 #endif
667 }
668
669 if (target < i) return target;
670
671 for (; target < n_active_segs - 1; target++)
672 {
673 asi_right = active_segs[target + 1];
674 p0r = ips[asi_right][0];
675 if (n_ips[asi_right] == 1)
676 p1r = vp->segs[asi_right].points[cursor[asi_right] + 1];
677 else
678 p1r = ips[asi_right][1];
679 if (!PT_EQ (p0, p0r))
680 break;
681
682 #ifdef VERBOSE
683 fprintf (STDERR,"point matches on left (%g, %g) - (%g, %g) x (%g, %g) - (%g, %g)!\n",
684 p0.x, p0.y, p1.x, p1.y, p0r.x, p0r.y, p1r.x, p1r.y);
685 #endif
686 if (x_order (p0r, p1r, p0, p1) == 1)
687 break;
688
689 #ifdef VERBOSE
690 fprintf (STDERR,"scanning to the right (i=%d, target=%d)\n", i, target);
691 #endif
692 }
693
694 return target;
695 }
696 #endif
697
698 /* This routine handles the case where the segment changes its position
699 in the active segment list. Generally, this will happen when the
700 segment (defined by i and cursor) shares a top point with a neighbor,
701 but breaks the ordering invariant.
702
703 Essentially, this routine sorts the lines [start..end), all of which
704 share a top point. This is implemented as your basic insertion sort.
705
706 This routine takes care of intersecting the appropriate neighbors,
707 as well.
708
709 A first argument of -1 immediately returns, which helps reduce special
710 casing in the main unwind routine.
711 */
712 static void
fix_crossing(int start,int end,int * active_segs,int n_active_segs,int * cursor,ArtPoint ** ips,int * n_ips,int * n_ips_max,ArtSVP * vp,int * seg_map,ArtSVP ** p_new_vp,int * pn_segs_max,int ** pn_points_max)713 fix_crossing (int start, int end, int *active_segs, int n_active_segs,
714 int *cursor, ArtPoint **ips, int *n_ips, int *n_ips_max,
715 ArtSVP *vp, int *seg_map,
716 ArtSVP **p_new_vp, int *pn_segs_max,
717 int **pn_points_max)
718 {
719 int i, j;
720 int target;
721 int asi, asj;
722 ArtPoint p0i, p1i;
723 ArtPoint p0j, p1j;
724 int swap = 0;
725 #ifdef VERBOSE
726 int k;
727 #endif
728 ArtPoint *pts;
729
730 #ifdef VERBOSE
731 fprintf (STDERR,"fix_crossing: [%d..%d)", start, end);
732 for (k = 0; k < n_active_segs; k++)
733 fprintf (STDERR," %d", active_segs[k]);
734 fprintf (STDERR,"\n");
735 #endif
736
737 if (start == -1)
738 return;
739
740 for (i = start + 1; i < end; i++)
741 {
742
743 asi = active_segs[i];
744 if (cursor[asi] < vp->segs[asi].n_points - 1) {
745 p0i = ips[asi][0];
746 if (n_ips[asi] == 1)
747 p1i = vp->segs[asi].points[cursor[asi] + 1];
748 else
749 p1i = ips[asi][1];
750
751 for (j = i - 1; j >= start; j--)
752 {
753 asj = active_segs[j];
754 if (cursor[asj] < vp->segs[asj].n_points - 1)
755 {
756 p0j = ips[asj][0];
757 if (n_ips[asj] == 1)
758 p1j = vp->segs[asj].points[cursor[asj] + 1];
759 else
760 p1j = ips[asj][1];
761
762 /* we _hope_ p0i = p0j */
763 if (x_order_2 (p0j, p1j, p0i, p1i) == -1)
764 break;
765 }
766 }
767
768 target = j + 1;
769 /* target is where active_seg[i] _should_ be in active_segs */
770
771 if (target != i)
772 {
773 swap = 1;
774
775 #ifdef VERBOSE
776 fprintf (STDERR,"fix_crossing: at %i should be %i\n", i, target);
777 #endif
778
779 /* let's close off all relevant segments */
780 for (j = i; j >= target; j--)
781 {
782 asi = active_segs[j];
783 /* First conjunct: this isn't the last point in the original
784 segment.
785
786 Second conjunct: this isn't the first point in the new
787 segment (i.e. already broken).
788 */
789 if (cursor[asi] < vp->segs[asi].n_points - 1 &&
790 (*p_new_vp)->segs[seg_map[asi]].n_points != 1)
791 {
792 int seg_num;
793 /* so break here */
794 #ifdef VERBOSE
795 fprintf (STDERR,"closing off %d\n", j);
796 #endif
797
798 pts = art_new (ArtPoint, 16);
799 pts[0] = ips[asi][0];
800 seg_num = art_svp_add_segment (p_new_vp, pn_segs_max,
801 pn_points_max,
802 1, vp->segs[asi].dir,
803 pts,
804 NULL);
805 (*pn_points_max)[seg_num] = 16;
806 seg_map[asi] = seg_num;
807 }
808 }
809
810 /* now fix the ordering in active_segs */
811 asi = active_segs[i];
812 for (j = i; j > target; j--)
813 active_segs[j] = active_segs[j - 1];
814 active_segs[j] = asi;
815 }
816 }
817 }
818 if (swap && start > 0)
819 {
820 int as_start;
821
822 as_start = active_segs[start];
823 if (cursor[as_start] < vp->segs[as_start].n_points)
824 {
825 #ifdef VERBOSE
826 fprintf (STDERR,"checking intersection of %d, %d\n", start - 1, start);
827 #endif
828 intersect_neighbors (start, active_segs,
829 n_ips, n_ips_max, ips,
830 cursor, vp);
831 }
832 }
833
834 if (swap && end < n_active_segs)
835 {
836 int as_end;
837
838 as_end = active_segs[end - 1];
839 if (cursor[as_end] < vp->segs[as_end].n_points)
840 {
841 #ifdef VERBOSE
842 fprintf (STDERR,"checking intersection of %d, %d\n", end - 1, end);
843 #endif
844 intersect_neighbors (end, active_segs,
845 n_ips, n_ips_max, ips,
846 cursor, vp);
847 }
848 }
849 if (swap)
850 {
851 #ifdef VERBOSE
852 fprintf (STDERR,"fix_crossing return: [%d..%d)", start, end);
853 for (k = 0; k < n_active_segs; k++)
854 fprintf (STDERR," %d", active_segs[k]);
855 fprintf (STDERR,"\n");
856 #endif
857 }
858 }
859
860 /* Return a new sorted vector that covers the same area as the
861 argument, but which satisfies the nocross invariant.
862
863 Basically, this routine works by finding the intersection points,
864 and cutting the segments at those points.
865
866 Status of this routine:
867
868 Basic correctness: Seems ok.
869
870 Numerical stability: known problems in the case of points falling
871 on lines, and colinear lines. For actual use, randomly perturbing
872 the vertices is currently recommended.
873
874 Speed: pretty good, although a more efficient priority queue, as
875 well as bbox culling of potential intersections, are two
876 optimizations that could help.
877
878 Precision: pretty good, although the numerical stability problems
879 make this routine unsuitable for precise calculations of
880 differences.
881
882 */
883
884 /* Here is a more detailed description of the algorithm. It follows
885 roughly the structure of traverse (above), but is obviously quite
886 a bit more complex.
887
888 Here are a few important data structures:
889
890 A new sorted vector path (new_svp).
891
892 For each (active) segment in the original, a list of intersection
893 points.
894
895 Of course, the original being traversed.
896
897 The following invariants hold (in addition to the invariants
898 of the traverse procedure).
899
900 The new sorted vector path lies entirely above the y scan line.
901
902 The new sorted vector path keeps the nocross invariant.
903
904 For each active segment, the y scan line crosses the line from the
905 first to the second of the intersection points (where the second
906 point is cursor + 1 if there is only one intersection point).
907
908 The list of intersection points + the (cursor + 1) point is kept
909 in nondecreasing y order.
910
911 Of the active segments, none of the lines from first to second
912 intersection point cross the 1st ip..2nd ip line of the left or
913 right neighbor. (However, such a line may cross further
914 intersection points of the neighbors, or segments past the
915 immediate neighbors).
916
917 Of the active segments, all lines from 1st ip..2nd ip are in
918 strictly increasing x_order (this is very similar to the invariant
919 of the traverse procedure, but is explicitly stated here in terms
920 of ips). (this basically says that nocross holds on the active
921 segments)
922
923 The combination of the new sorted vector path, the path through all
924 the intersection points to cursor + 1, and [cursor + 1, n_points)
925 covers the same area as the argument.
926
927 Another important data structure is mapping from original segment
928 number to new segment number.
929
930 The algorithm is perhaps best understood as advancing the cursors
931 while maintaining these invariants. Here's roughly how it's done.
932
933 When deleting segments from the active list, those segments are added
934 to the new sorted vector path. In addition, the neighbors may intersect
935 each other, so they are intersection tested (see below).
936
937 When inserting new segments, they are intersection tested against
938 their neighbors. The top point of the segment becomes the first
939 intersection point.
940
941 Advancing the cursor is just a bit different from the traverse
942 routine, as the cursor may advance through the intersection points
943 as well. Only when there is a single intersection point in the list
944 does the cursor advance in the original segment. In either case,
945 the new vector is intersection tested against both neighbors. It
946 also causes the vector over which the cursor is advancing to be
947 added to the new svp.
948
949 Two steps need further clarification:
950
951 Intersection testing: the 1st ip..2nd ip lines of the neighbors
952 are tested to see if they cross (using intersect_lines). If so,
953 then the intersection point is added to the ip list of both
954 segments, maintaining the invariant that the list of intersection
955 points is nondecreasing in y).
956
957 Adding vector to new svp: if the new vector shares a top x
958 coordinate with another vector, then it is checked to see whether
959 it is in order. If not, then both segments are "broken," and then
960 restarted. Note: in the case when both segments are in the same
961 order, they may simply be swapped without breaking.
962
963 For the time being, I'm going to put some of these operations into
964 subroutines. If it turns out to be a performance problem, I could
965 try to reorganize the traverse procedure so that each is only
966 called once, and inline them. But if it's not a performance
967 problem, I'll just keep it this way, because it will probably help
968 to make the code clearer, and I believe this code could use all the
969 clarity it can get. */
970 /**
971 * art_svp_uncross: Resolve self-intersections of an svp.
972 * @vp: The original svp.
973 *
974 * Finds all the intersections within @vp, and constructs a new svp
975 * with new points added at these intersections.
976 *
977 * This routine needs to be redone from scratch with numerical robustness
978 * in mind. I'm working on it.
979 *
980 * Return value: The new svp.
981 **/
982 ArtSVP *
art_svp_uncross(ArtSVP * vp)983 art_svp_uncross (ArtSVP *vp)
984 {
985 int *active_segs;
986 int n_active_segs;
987 int *cursor;
988 int seg_idx;
989 double y;
990 int tmp1, tmp2;
991 int asi;
992 int i, j;
993 /* new data structures */
994 /* intersection points; invariant: *ips[i] is only allocated if
995 i is active */
996 int *n_ips, *n_ips_max;
997 ArtPoint **ips;
998 /* new sorted vector path */
999 int n_segs_max, seg_num;
1000 ArtSVP *new_vp;
1001 int *n_points_max;
1002 /* mapping from argument to new segment numbers - again, only valid
1003 if active */
1004 int *seg_map;
1005 double y_curs;
1006 ArtPoint p_curs;
1007 int first_share;
1008 double share_x;
1009 ArtPoint *pts;
1010
1011 n_segs_max = 16;
1012 new_vp = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
1013 (n_segs_max - 1) * sizeof(ArtSVPSeg));
1014 new_vp->n_segs = 0;
1015
1016 if (vp->n_segs == 0)
1017 return new_vp;
1018
1019 active_segs = art_new (int, vp->n_segs);
1020 cursor = art_new (int, vp->n_segs);
1021
1022 seg_map = art_new (int, vp->n_segs);
1023 n_ips = art_new (int, vp->n_segs);
1024 n_ips_max = art_new (int, vp->n_segs);
1025 ips = art_new (ArtPoint *, vp->n_segs);
1026
1027 n_points_max = art_new (int, n_segs_max);
1028
1029 n_active_segs = 0;
1030 seg_idx = 0;
1031 y = vp->segs[0].points[0].y;
1032 while (seg_idx < vp->n_segs || n_active_segs > 0)
1033 {
1034 #ifdef VERBOSE
1035 fprintf (STDERR,"y = %g\n", y);
1036 #endif
1037
1038 /* maybe move deletions to end of loop (to avoid so much special
1039 casing on the end of a segment)? */
1040
1041 /* delete segments ending at y from active list */
1042 for (i = 0; i < n_active_segs; i++)
1043 {
1044 asi = active_segs[i];
1045 if (vp->segs[asi].n_points - 1 == cursor[asi] &&
1046 vp->segs[asi].points[cursor[asi]].y == y)
1047 {
1048 do
1049 {
1050 #ifdef VERBOSE
1051 fprintf (STDERR,"deleting %d\n", asi);
1052 #endif
1053 art_free (ips[asi]);
1054 n_active_segs--;
1055 for (j = i; j < n_active_segs; j++)
1056 active_segs[j] = active_segs[j + 1];
1057 if (i < n_active_segs)
1058 asi = active_segs[i];
1059 else
1060 break;
1061 }
1062 while (vp->segs[asi].n_points - 1 == cursor[asi] &&
1063 vp->segs[asi].points[cursor[asi]].y == y);
1064
1065 /* test intersection of neighbors */
1066 if (i > 0 && i < n_active_segs)
1067 intersect_neighbors (i, active_segs,
1068 n_ips, n_ips_max, ips,
1069 cursor, vp);
1070
1071 i--;
1072 }
1073 }
1074
1075 /* insert new segments into the active list */
1076 while (seg_idx < vp->n_segs && y == vp->segs[seg_idx].points[0].y)
1077 {
1078 #ifdef VERBOSE
1079 fprintf (STDERR,"inserting %d\n", seg_idx);
1080 #endif
1081 cursor[seg_idx] = 0;
1082 for (i = 0; i < n_active_segs; i++)
1083 {
1084 asi = active_segs[i];
1085 if (x_order_2 (vp->segs[seg_idx].points[0],
1086 vp->segs[seg_idx].points[1],
1087 vp->segs[asi].points[cursor[asi]],
1088 vp->segs[asi].points[cursor[asi] + 1]) == -1)
1089 break;
1090 }
1091
1092 /* Create and initialize the intersection points data structure */
1093 n_ips[seg_idx] = 1;
1094 n_ips_max[seg_idx] = 2;
1095 ips[seg_idx] = art_new (ArtPoint, n_ips_max[seg_idx]);
1096 ips[seg_idx][0] = vp->segs[seg_idx].points[0];
1097
1098 /* Start a new segment in the new vector path */
1099 pts = art_new (ArtPoint, 16);
1100 pts[0] = vp->segs[seg_idx].points[0];
1101 seg_num = art_svp_add_segment (&new_vp, &n_segs_max,
1102 &n_points_max,
1103 1, vp->segs[seg_idx].dir,
1104 pts,
1105 NULL);
1106 n_points_max[seg_num] = 16;
1107 seg_map[seg_idx] = seg_num;
1108
1109 tmp1 = seg_idx;
1110 for (j = i; j < n_active_segs; j++)
1111 {
1112 tmp2 = active_segs[j];
1113 active_segs[j] = tmp1;
1114 tmp1 = tmp2;
1115 }
1116 active_segs[n_active_segs] = tmp1;
1117 n_active_segs++;
1118
1119 if (i > 0)
1120 intersect_neighbors (i, active_segs,
1121 n_ips, n_ips_max, ips,
1122 cursor, vp);
1123
1124 if (i + 1 < n_active_segs)
1125 intersect_neighbors (i + 1, active_segs,
1126 n_ips, n_ips_max, ips,
1127 cursor, vp);
1128
1129 seg_idx++;
1130 }
1131
1132 /* all active segs cross the y scanline (considering segs to be
1133 closed on top and open on bottom) */
1134 #ifdef VERBOSE
1135 for (i = 0; i < n_active_segs; i++)
1136 {
1137 asi = active_segs[i];
1138 fprintf (STDERR,"%d ", asi);
1139 for (j = 0; j < n_ips[asi]; j++)
1140 fprintf (STDERR,"(%g, %g) - ",
1141 ips[asi][j].x,
1142 ips[asi][j].y);
1143 fprintf (STDERR,"(%g, %g) %s\n",
1144 vp->segs[asi].points[cursor[asi] + 1].x,
1145 vp->segs[asi].points[cursor[asi] + 1].y,
1146 vp->segs[asi].dir ? "v" : "^");
1147 }
1148 #endif
1149
1150 /* advance y to the next event
1151 Note: this is quadratic. We'd probably get decent constant
1152 factor speed improvement by caching the y_curs values. */
1153 if (n_active_segs == 0)
1154 {
1155 if (seg_idx < vp->n_segs)
1156 y = vp->segs[seg_idx].points[0].y;
1157 /* else we're done */
1158 }
1159 else
1160 {
1161 asi = active_segs[0];
1162 if (n_ips[asi] == 1)
1163 y = vp->segs[asi].points[cursor[asi] + 1].y;
1164 else
1165 y = ips[asi][1].y;
1166 for (i = 1; i < n_active_segs; i++)
1167 {
1168 asi = active_segs[i];
1169 if (n_ips[asi] == 1)
1170 y_curs = vp->segs[asi].points[cursor[asi] + 1].y;
1171 else
1172 y_curs = ips[asi][1].y;
1173 if (y > y_curs)
1174 y = y_curs;
1175 }
1176 if (seg_idx < vp->n_segs && y > vp->segs[seg_idx].points[0].y)
1177 y = vp->segs[seg_idx].points[0].y;
1178 }
1179
1180 first_share = -1;
1181 share_x = 0; /* to avoid gcc warning, although share_x is never
1182 used when first_share is -1 */
1183 /* advance cursors to reach new y */
1184 for (i = 0; i < n_active_segs; i++)
1185 {
1186 asi = active_segs[i];
1187 if (n_ips[asi] == 1)
1188 p_curs = vp->segs[asi].points[cursor[asi] + 1];
1189 else
1190 p_curs = ips[asi][1];
1191 if (p_curs.y == y)
1192 {
1193 svp_add_point (new_vp, n_points_max,
1194 p_curs, seg_map, active_segs, n_active_segs, i);
1195
1196 n_ips[asi]--;
1197 for (j = 0; j < n_ips[asi]; j++)
1198 ips[asi][j] = ips[asi][j + 1];
1199
1200 if (n_ips[asi] == 0)
1201 {
1202 ips[asi][0] = p_curs;
1203 n_ips[asi] = 1;
1204 cursor[asi]++;
1205 }
1206
1207 if (first_share < 0 || p_curs.x != share_x)
1208 {
1209 /* this is where crossings are detected, and if
1210 found, the active segments switched around. */
1211
1212 fix_crossing (first_share, i,
1213 active_segs, n_active_segs,
1214 cursor, ips, n_ips, n_ips_max, vp, seg_map,
1215 &new_vp,
1216 &n_segs_max, &n_points_max);
1217
1218 first_share = i;
1219 share_x = p_curs.x;
1220 }
1221
1222 if (cursor[asi] < vp->segs[asi].n_points - 1)
1223 {
1224
1225 if (i > 0)
1226 intersect_neighbors (i, active_segs,
1227 n_ips, n_ips_max, ips,
1228 cursor, vp);
1229
1230 if (i + 1 < n_active_segs)
1231 intersect_neighbors (i + 1, active_segs,
1232 n_ips, n_ips_max, ips,
1233 cursor, vp);
1234 }
1235 }
1236 else
1237 {
1238 /* not on a cursor point */
1239 fix_crossing (first_share, i,
1240 active_segs, n_active_segs,
1241 cursor, ips, n_ips, n_ips_max, vp, seg_map,
1242 &new_vp,
1243 &n_segs_max, &n_points_max);
1244 first_share = -1;
1245 }
1246 }
1247
1248 /* fix crossing on last shared group */
1249 fix_crossing (first_share, i,
1250 active_segs, n_active_segs,
1251 cursor, ips, n_ips, n_ips_max, vp, seg_map,
1252 &new_vp,
1253 &n_segs_max, &n_points_max);
1254
1255 #ifdef VERBOSE
1256 fprintf (STDERR,"\n");
1257 #endif
1258 }
1259
1260 /* not necessary to sort, new segments only get added at y, which
1261 increases monotonically */
1262 #if 0
1263 qsort (&new_vp->segs, new_vp->n_segs, sizeof (svp_seg), svp_seg_compare);
1264 {
1265 int k;
1266 for (k = 0; k < new_vp->n_segs - 1; k++)
1267 {
1268 fprintf (STDERR,"(%g, %g) - (%g, %g) %s (%g, %g) - (%g, %g)\n",
1269 new_vp->segs[k].points[0].x,
1270 new_vp->segs[k].points[0].y,
1271 new_vp->segs[k].points[1].x,
1272 new_vp->segs[k].points[1].y,
1273 svp_seg_compare (&new_vp->segs[k], &new_vp->segs[k + 1]) > 1 ? ">": "<",
1274 new_vp->segs[k + 1].points[0].x,
1275 new_vp->segs[k + 1].points[0].y,
1276 new_vp->segs[k + 1].points[1].x,
1277 new_vp->segs[k + 1].points[1].y);
1278 }
1279 }
1280 #endif
1281
1282 art_free (n_points_max);
1283 art_free (seg_map);
1284 art_free (n_ips_max);
1285 art_free (n_ips);
1286 art_free (ips);
1287 art_free (cursor);
1288 art_free (active_segs);
1289
1290 return new_vp;
1291 }
1292
1293 #define noVERBOSE
1294
1295 /* Rewind a svp satisfying the nocross invariant.
1296
1297 The winding number of a segment is defined as the winding number of
1298 the points to the left while travelling in the direction of the
1299 segment. Therefore it preincrements and postdecrements as a scan
1300 line is traversed from left to right.
1301
1302 Status of this routine:
1303
1304 Basic correctness: Was ok in gfonted. However, this code does not
1305 yet compute bboxes for the resulting svp segs.
1306
1307 Numerical stability: known problems in the case of horizontal
1308 segments in polygons with any complexity. For actual use, randomly
1309 perturbing the vertices is recommended.
1310
1311 Speed: good.
1312
1313 Precision: good, except that no attempt is made to remove "hair".
1314 Doing random perturbation just makes matters worse.
1315
1316 */
1317 /**
1318 * art_svp_rewind_uncrossed: Rewind an svp satisfying the nocross invariant.
1319 * @vp: The original svp.
1320 * @rule: The winding rule.
1321 *
1322 * Creates a new svp with winding number of 0 or 1 everywhere. The @rule
1323 * argument specifies a rule for how winding numbers in the original
1324 * @vp map to the winding numbers in the result.
1325 *
1326 * With @rule == ART_WIND_RULE_NONZERO, the resulting svp has a
1327 * winding number of 1 where @vp has a nonzero winding number.
1328 *
1329 * With @rule == ART_WIND_RULE_INTERSECT, the resulting svp has a
1330 * winding number of 1 where @vp has a winding number greater than
1331 * 1. It is useful for computing intersections.
1332 *
1333 * With @rule == ART_WIND_RULE_ODDEVEN, the resulting svp has a
1334 * winding number of 1 where @vp has an odd winding number. It is
1335 * useful for implementing the even-odd winding rule of the
1336 * PostScript imaging model.
1337 *
1338 * With @rule == ART_WIND_RULE_POSITIVE, the resulting svp has a
1339 * winding number of 1 where @vp has a positive winding number. It is
1340 * useful for implementing asymmetric difference.
1341 *
1342 * This routine needs to be redone from scratch with numerical robustness
1343 * in mind. I'm working on it.
1344 *
1345 * Return value: The new svp.
1346 **/
1347 ArtSVP *
art_svp_rewind_uncrossed(ArtSVP * vp,ArtWindRule rule)1348 art_svp_rewind_uncrossed (ArtSVP *vp, ArtWindRule rule)
1349 {
1350 int *active_segs;
1351 int n_active_segs;
1352 int *cursor;
1353 int seg_idx;
1354 double y;
1355 int tmp1, tmp2;
1356 int asi;
1357 int i, j;
1358
1359 ArtSVP *new_vp;
1360 int n_segs_max;
1361 int *winding;
1362 int left_wind;
1363 int wind;
1364 int keep, invert;
1365
1366 #ifdef VERBOSE
1367 print_svp (vp);
1368 #endif
1369 n_segs_max = 16;
1370 new_vp = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
1371 (n_segs_max - 1) * sizeof(ArtSVPSeg));
1372 new_vp->n_segs = 0;
1373
1374 if (vp->n_segs == 0)
1375 return new_vp;
1376
1377 winding = art_new (int, vp->n_segs);
1378
1379 active_segs = art_new (int, vp->n_segs);
1380 cursor = art_new (int, vp->n_segs);
1381
1382 n_active_segs = 0;
1383 seg_idx = 0;
1384 y = vp->segs[0].points[0].y;
1385 while (seg_idx < vp->n_segs || n_active_segs > 0)
1386 {
1387 #ifdef VERBOSE
1388 fprintf (STDERR,"y = %g\n", y);
1389 #endif
1390 /* delete segments ending at y from active list */
1391 for (i = 0; i < n_active_segs; i++)
1392 {
1393 asi = active_segs[i];
1394 if (vp->segs[asi].n_points - 1 == cursor[asi] &&
1395 vp->segs[asi].points[cursor[asi]].y == y)
1396 {
1397 #ifdef VERBOSE
1398 fprintf (STDERR,"deleting %d\n", asi);
1399 #endif
1400 n_active_segs--;
1401 for (j = i; j < n_active_segs; j++)
1402 active_segs[j] = active_segs[j + 1];
1403 i--;
1404 }
1405 }
1406
1407 /* insert new segments into the active list */
1408 while (seg_idx < vp->n_segs && y == vp->segs[seg_idx].points[0].y)
1409 {
1410 #ifdef VERBOSE
1411 fprintf (STDERR,"inserting %d\n", seg_idx);
1412 #endif
1413 cursor[seg_idx] = 0;
1414 for (i = 0; i < n_active_segs; i++)
1415 {
1416 asi = active_segs[i];
1417 if (x_order_2 (vp->segs[seg_idx].points[0],
1418 vp->segs[seg_idx].points[1],
1419 vp->segs[asi].points[cursor[asi]],
1420 vp->segs[asi].points[cursor[asi] + 1]) == -1)
1421 break;
1422 }
1423
1424 /* Determine winding number for this segment */
1425 if (i == 0)
1426 left_wind = 0;
1427 else if (vp->segs[active_segs[i - 1]].dir)
1428 left_wind = winding[active_segs[i - 1]];
1429 else
1430 left_wind = winding[active_segs[i - 1]] - 1;
1431
1432 if (vp->segs[seg_idx].dir)
1433 wind = left_wind + 1;
1434 else
1435 wind = left_wind;
1436
1437 winding[seg_idx] = wind;
1438
1439 switch (rule)
1440 {
1441 case ART_WIND_RULE_NONZERO:
1442 keep = (wind == 1 || wind == 0);
1443 invert = (wind == 0);
1444 break;
1445 case ART_WIND_RULE_INTERSECT:
1446 keep = (wind == 2);
1447 invert = 0;
1448 break;
1449 case ART_WIND_RULE_ODDEVEN:
1450 keep = 1;
1451 invert = !(wind & 1);
1452 break;
1453 case ART_WIND_RULE_POSITIVE:
1454 keep = (wind == 1);
1455 invert = 0;
1456 break;
1457 default:
1458 keep = 0;
1459 invert = 0;
1460 break;
1461 }
1462
1463 if (keep)
1464 {
1465 ArtPoint *points, *new_points;
1466 int n_points;
1467 int new_dir;
1468
1469 #ifdef VERBOSE
1470 fprintf (STDERR,"keeping segment %d\n", seg_idx);
1471 #endif
1472 n_points = vp->segs[seg_idx].n_points;
1473 points = vp->segs[seg_idx].points;
1474 new_points = art_new (ArtPoint, n_points);
1475 memcpy (new_points, points, n_points * sizeof (ArtPoint));
1476 new_dir = vp->segs[seg_idx].dir ^ invert;
1477 art_svp_add_segment (&new_vp, &n_segs_max,
1478 NULL,
1479 n_points, new_dir, new_points,
1480 &vp->segs[seg_idx].bbox);
1481 }
1482
1483 tmp1 = seg_idx;
1484 for (j = i; j < n_active_segs; j++)
1485 {
1486 tmp2 = active_segs[j];
1487 active_segs[j] = tmp1;
1488 tmp1 = tmp2;
1489 }
1490 active_segs[n_active_segs] = tmp1;
1491 n_active_segs++;
1492 seg_idx++;
1493 }
1494
1495 #ifdef VERBOSE
1496 /* all active segs cross the y scanline (considering segs to be
1497 closed on top and open on bottom) */
1498 for (i = 0; i < n_active_segs; i++)
1499 {
1500 asi = active_segs[i];
1501 fprintf (STDERR,"%d:%d (%g, %g) - (%g, %g) %s %d\n", asi,
1502 cursor[asi],
1503 vp->segs[asi].points[cursor[asi]].x,
1504 vp->segs[asi].points[cursor[asi]].y,
1505 vp->segs[asi].points[cursor[asi] + 1].x,
1506 vp->segs[asi].points[cursor[asi] + 1].y,
1507 vp->segs[asi].dir ? "v" : "^",
1508 winding[asi]);
1509 }
1510 #endif
1511
1512 /* advance y to the next event */
1513 if (n_active_segs == 0)
1514 {
1515 if (seg_idx < vp->n_segs)
1516 y = vp->segs[seg_idx].points[0].y;
1517 /* else we're done */
1518 }
1519 else
1520 {
1521 asi = active_segs[0];
1522 y = vp->segs[asi].points[cursor[asi] + 1].y;
1523 for (i = 1; i < n_active_segs; i++)
1524 {
1525 asi = active_segs[i];
1526 if (y > vp->segs[asi].points[cursor[asi] + 1].y)
1527 y = vp->segs[asi].points[cursor[asi] + 1].y;
1528 }
1529 if (seg_idx < vp->n_segs && y > vp->segs[seg_idx].points[0].y)
1530 y = vp->segs[seg_idx].points[0].y;
1531 }
1532
1533 /* advance cursors to reach new y */
1534 for (i = 0; i < n_active_segs; i++)
1535 {
1536 asi = active_segs[i];
1537 while (cursor[asi] < vp->segs[asi].n_points - 1 &&
1538 y >= vp->segs[asi].points[cursor[asi] + 1].y)
1539 cursor[asi]++;
1540 }
1541 #ifdef VERBOSE
1542 fprintf (STDERR,"\n");
1543 #endif
1544 }
1545 art_free (cursor);
1546 art_free (active_segs);
1547 art_free (winding);
1548
1549 return new_vp;
1550 }
1551