1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 2001 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 */
20 /* This file contains a testbed implementation of the new intersection
21 code.
22 */
24 #include <math.h> /* for sqrt */
26 /* Sanitychecking verifies the main invariant on every priority queue
27 point. Do not use in production, as it slows things down way too
28 much. */
29 #define noSANITYCHECK
31 /* This can be used in production, to prevent hangs. Eventually, it
32 should not be necessary. */
33 #define CHEAP_SANITYCHECK
35 #define noVERBOSE
36 #ifdef VERBOSE
37 #include <stdio.h>
38 #endif
40 #include "art_misc.h"
41 #include "art_svp.h"
42 #include "art_svp_intersect.h"
44 /* A priority queue - perhaps move to a separate file if it becomes
45 needed somewhere else */
47 #define ART_PRIQ_USE_HEAP
49 typedef struct _ArtPriQ ArtPriQ;
50 typedef struct _ArtPriPoint ArtPriPoint;
52 struct _ArtPriQ {
53 int n_items;
54 int n_items_max;
55 ArtPriPoint **items;
56 };
58 struct _ArtPriPoint {
59 double x;
60 double y;
61 void *user_data;
62 };
64 static ArtPriQ *
65 art_pri_new (void)
66 {
67 ArtPriQ *result = art_new (ArtPriQ, 1);
69 result->n_items = 0;
70 result->n_items_max = 16;
71 result->items = art_new (ArtPriPoint *, result->n_items_max);
72 return result;
73 }
75 static void
76 art_pri_free (ArtPriQ *pq)
77 {
78 art_free (pq->items);
79 art_free (pq);
80 }
82 static art_boolean
83 art_pri_empty (ArtPriQ *pq)
84 {
85 return pq->n_items == 0;
86 }
88 #ifdef ART_PRIQ_USE_HEAP
90 /* This heap implementation is based on Vasek Chvatal's course notes:
91 http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
93 static void
94 art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing)
95 {
96 ArtPriPoint **items = pq->items;
97 int parent;
99 parent = (vacant - 1) >> 1;
100 while (vacant > 0 && (missing->y < items[parent]->y ||
101 (missing->y == items[parent]->y &&
102 missing->x < items[parent]->x)))
103 {
104 items[vacant] = items[parent];
105 vacant = parent;
106 parent = (vacant - 1) >> 1;
107 }
109 items[vacant] = missing;
110 }
112 static void
113 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
114 {
115 if (pq->n_items == pq->n_items_max)
116 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
118 art_pri_bubble_up (pq, pq->n_items++, point);
119 }
121 static void
122 art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
123 {
124 ArtPriPoint **items = pq->items;
125 int vacant = 0, child = 2;
126 int n = pq->n_items;
128 while (child < n)
129 {
130 if (items[child - 1]->y < items[child]->y ||
131 (items[child - 1]->y == items[child]->y &&
132 items[child - 1]->x < items[child]->x))
133 child--;
134 items[vacant] = items[child];
135 vacant = child;
136 child = (vacant + 1) << 1;
137 }
138 if (child == n)
139 {
140 items[vacant] = items[n - 1];
141 vacant = n - 1;
142 }
144 art_pri_bubble_up (pq, vacant, missing);
145 }
147 static ArtPriPoint *
148 art_pri_choose (ArtPriQ *pq)
149 {
150 ArtPriPoint *result = pq->items[0];
152 art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
153 return result;
154 }
156 #else
158 /* Choose least point in queue */
159 static ArtPriPoint *
160 art_pri_choose (ArtPriQ *pq)
161 {
162 int i;
163 int best = 0;
164 double best_x, best_y;
165 double y;
166 ArtPriPoint *result;
168 if (pq->n_items == 0)
169 return NULL;
171 best_x = pq->items[best]->x;
172 best_y = pq->items[best]->y;
174 for (i = 1; i < pq->n_items; i++)
175 {
176 y = pq->items[i]->y;
177 if (y < best_y || (y == best_y && pq->items[i]->x < best_x))
178 {
179 best = i;
180 best_x = pq->items[best]->x;
181 best_y = y;
182 }
183 }
184 result = pq->items[best];
185 pq->items[best] = pq->items[--pq->n_items];
186 return result;
187 }
189 static void
190 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
191 {
192 if (pq->n_items == pq->n_items_max)
193 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
195 pq->items[pq->n_items++] = point;
196 }
198 #endif
200 #ifdef TEST_PRIQ
202 #include <stdlib.h> /* for rand() */
203 #include <stdio.h>
205 static double
206 double_rand (double lo, double hi, int quant)
207 {
208 int tmp = rand () / (RAND_MAX * (1.0 / quant)) + 0.5;
209 return lo + tmp * ((hi - lo) / quant);
210 }
212 /*
213 * This custom allocator for priority queue points is here so I can
214 * test speed. It doesn't look like it will be that significant, but
215 * if I want a small improvement later, it's something.
216 */
218 typedef ArtPriPoint *ArtPriPtPool;
220 static ArtPriPtPool *
221 art_pri_pt_pool_new (void)
222 {
223 ArtPriPtPool *result = art_new (ArtPriPtPool, 1);
224 *result = NULL;
225 return result;
226 }
228 static ArtPriPoint *
229 art_pri_pt_alloc (ArtPriPtPool *pool)
230 {
231 ArtPriPoint *result = *pool;
232 if (result == NULL)
233 return art_new (ArtPriPoint, 1);
234 else
235 {
236 *pool = result->user_data;
237 return result;
238 }
239 }
241 static void
242 art_pri_pt_free (ArtPriPtPool *pool, ArtPriPoint *pt)
243 {
244 pt->user_data = *pool;
245 *pool = pt;
246 }
248 static void
249 art_pri_pt_pool_free (ArtPriPtPool *pool)
250 {
251 ArtPriPoint *pt = *pool;
252 while (pt != NULL)
253 {
254 ArtPriPoint *next = pt->user_data;
255 art_free (pt);
256 pt = next;
257 }
258 art_free (pool);
259 }
261 int
262 main (int argc, char **argv)
263 {
264 ArtPriPtPool *pool = art_pri_pt_pool_new ();
265 ArtPriQ *pq;
266 int i, j;
267 const int n_iter = 1;
268 const int pq_size = 100;
270 for (j = 0; j < n_iter; j++)
271 {
272 pq = art_pri_new ();
274 for (i = 0; i < pq_size; i++)
275 {
276 ArtPriPoint *pt = art_pri_pt_alloc (pool);
277 pt->x = double_rand (0, 1, 100);
278 pt->y = double_rand (0, 1, 100);
279 pt->user_data = (void *)i;
280 art_pri_insert (pq, pt);
281 }
283 while (!art_pri_empty (pq))
284 {
285 ArtPriPoint *pt = art_pri_choose (pq);
286 if (n_iter == 1)
287 printf ("(%g, %g), %d\n", pt->x, pt->y, (int)pt->user_data);
288 art_pri_pt_free (pool, pt);
289 }
291 art_pri_free (pq);
292 }
293 art_pri_pt_pool_free (pool);
294 return 0;
295 }
297 #else /* TEST_PRIQ */
299 /* A virtual class for an "svp writer". A client of this object creates an
300 SVP by repeatedly calling "add segment" and "add point" methods on it.
301 */
303 typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
305 /* An implementation of the svp writer virtual class that applies the
306 winding rule. */
308 struct _ArtSvpWriterRewind {
309 ArtSvpWriter super;
310 ArtWindRule rule;
311 ArtSVP *svp;
312 int n_segs_max;
313 int *n_points_max;
314 };
316 static int
317 art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left,
318 int delta_wind, double x, double y)
319 {
320 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
321 ArtSVP *svp;
322 ArtSVPSeg *seg;
323 art_boolean left_filled, right_filled;
324 int wind_right = wind_left + delta_wind;
325 int seg_num;
326 const int init_n_points_max = 4;
328 switch (swr->rule)
329 {
330 case ART_WIND_RULE_NONZERO:
331 left_filled = (wind_left != 0);
332 right_filled = (wind_right != 0);
333 break;
334 case ART_WIND_RULE_INTERSECT:
335 left_filled = (wind_left > 1);
336 right_filled = (wind_right > 1);
337 break;
338 case ART_WIND_RULE_ODDEVEN:
339 left_filled = (wind_left & 1);
340 right_filled = (wind_right & 1);
341 break;
342 case ART_WIND_RULE_POSITIVE:
343 left_filled = (wind_left > 0);
344 right_filled = (wind_right > 0);
345 break;
346 default:
347 art_die ("Unknown wind rule %d\n", swr->rule);
348 }
349 if (left_filled == right_filled)
350 {
351 /* discard segment now */
352 #ifdef VERBOSE
353 printf ("swr add_segment: %d += %d (%g, %g) --> -1\n",
354 wind_left, delta_wind, x, y);
355 #endif
356 return -1;
357 }
359 svp = swr->svp;
360 seg_num = svp->n_segs++;
361 if (swr->n_segs_max == seg_num)
362 {
363 swr->n_segs_max <<= 1;
364 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
365 (swr->n_segs_max - 1) *
366 sizeof(ArtSVPSeg));
367 swr->svp = svp;
368 swr->n_points_max = art_renew (swr->n_points_max, int,
369 swr->n_segs_max);
370 }
371 seg = &svp->segs[seg_num];
372 seg->n_points = 1;
373 seg->dir = right_filled;
374 swr->n_points_max[seg_num] = init_n_points_max;
375 seg->bbox.x0 = x;
376 seg->bbox.y0 = y;
377 seg->bbox.x1 = x;
378 seg->bbox.y1 = y;
379 seg->points = art_new (ArtPoint, init_n_points_max);
380 seg->points[0].x = x;
381 seg->points[0].y = y;
382 #ifdef VERBOSE
383 printf ("swr add_segment: %d += %d (%g, %g) --> %d(%s)\n",
384 wind_left, delta_wind, x, y, seg_num,
385 seg->dir ? "v" : "^");
386 #endif
387 return seg_num;
388 }
390 static void
391 art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id,
392 double x, double y)
393 {
394 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
395 ArtSVPSeg *seg;
396 int n_points;
398 #ifdef VERBOSE
399 printf ("swr add_point: %d (%g, %g)\n", seg_id, x, y);
400 #endif
401 if (seg_id < 0)
402 /* omitted segment */
403 return;
405 seg = &swr->svp->segs[seg_id];
406 n_points = seg->n_points++;
407 if (swr->n_points_max[seg_id] == n_points)
408 art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
409 seg->points[n_points].x = x;
410 seg->points[n_points].y = y;
411 if (x < seg->bbox.x0)
412 seg->bbox.x0 = x;
413 if (x > seg->bbox.x1)
414 seg->bbox.x1 = x;
415 seg->bbox.y1 = y;
416 }
418 static void
419 art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id)
420 {
421 /* Not needed for this simple implementation. A potential future
422 optimization is to merge segments that can be merged safely. */
423 #ifdef SANITYCHECK
424 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
425 ArtSVPSeg *seg;
427 if (seg_id >= 0)
428 {
429 seg = &swr->svp->segs[seg_id];
430 if (seg->n_points < 2)
431 art_warn ("*** closing segment %d with only %d point%s\n",
432 seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
433 }
434 #endif
436 #ifdef VERBOSE
437 printf ("swr close_segment: %d\n", seg_id);
438 #endif
439 }
441 ArtSVP *
442 art_svp_writer_rewind_reap (ArtSvpWriter *self)
443 {
444 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
445 ArtSVP *result = swr->svp;
447 art_free (swr->n_points_max);
448 art_free (swr);
449 return result;
450 }
452 ArtSvpWriter *
453 art_svp_writer_rewind_new (ArtWindRule rule)
454 {
455 ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
457 result->super.add_segment = art_svp_writer_rewind_add_segment;
458 result->super.add_point = art_svp_writer_rewind_add_point;
459 result->super.close_segment = art_svp_writer_rewind_close_segment;
461 result->rule = rule;
462 result->n_segs_max = 16;
463 result->svp = art_alloc (sizeof(ArtSVP) +
464 (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
465 result->svp->n_segs = 0;
466 result->n_points_max = art_new (int, result->n_segs_max);
468 return &result->super;
469 }
471 /* Now, data structures for the active list */
473 typedef struct _ArtActiveSeg ArtActiveSeg;
475 /* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
476 x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
477 #define ART_ACTIVE_FLAGS_BNEG 1
479 /* This flag is set if the segment has been inserted into the active
480 list. */
481 #define ART_ACTIVE_FLAGS_IN_ACTIVE 2
483 /* This flag is set when the segment is to be deleted in the
484 horiz commit process. */
485 #define ART_ACTIVE_FLAGS_DEL 4
487 /* This flag is set if the seg_id is a valid output segment. */
488 #define ART_ACTIVE_FLAGS_OUT 8
490 /* This flag is set if the segment is in the horiz list. */
491 #define ART_ACTIVE_FLAGS_IN_HORIZ 16
493 struct _ArtActiveSeg {
494 int flags;
495 int wind_left, delta_wind;
496 ArtActiveSeg *left, *right; /* doubly linked list structure */
498 const ArtSVPSeg *in_seg;
499 int in_curs;
501 double x[2];
502 double y0, y1;
503 double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
504 and a>0 */
506 /* bottom point and intersection point stack */
507 int n_stack;
508 int n_stack_max;
509 ArtPoint *stack;
511 /* horiz commit list */
512 ArtActiveSeg *horiz_left, *horiz_right;
513 double horiz_x;
514 int horiz_delta_wind;
515 int seg_id;
516 };
518 typedef struct _ArtIntersectCtx ArtIntersectCtx;
520 struct _ArtIntersectCtx {
521 const ArtSVP *in;
522 ArtSvpWriter *out;
524 ArtPriQ *pq;
526 ArtActiveSeg *active_head;
528 double y;
529 ArtActiveSeg *horiz_first;
530 ArtActiveSeg *horiz_last;
532 /* segment index of next input segment to be added to pri q */
533 int in_curs;
534 };
536 #define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
538 /**
539 * art_svp_intersect_setup_seg: Set up an active segment from input segment.
540 * @seg: Active segment.
541 * @pri_pt: Priority queue point to initialize.
542 *
543 * Sets the x[], a, b, c, flags, and stack fields according to the
544 * line from the current cursor value. Sets the priority queue point
545 * to the bottom point of this line. Also advances the input segment
546 * cursor.
547 **/
548 static void
549 art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
550 {
551 const ArtSVPSeg *in_seg = seg->in_seg;
552 int in_curs = seg->in_curs++;
553 double x0, y0, x1, y1;
554 double dx, dy, s;
555 double a, b, r2;
557 x0 = in_seg->points[in_curs].x;
558 y0 = in_seg->points[in_curs].y;
559 x1 = in_seg->points[in_curs + 1].x;
560 y1 = in_seg->points[in_curs + 1].y;
561 pri_pt->x = x1;
562 pri_pt->y = y1;
563 dx = x1 - x0;
564 dy = y1 - y0;
565 r2 = dx * dx + dy * dy;
566 s = r2 == 0 ? 1 : 1 / sqrt (r2);
567 seg->a = a = dy * s;
568 seg->b = b = -dx * s;
569 seg->c = -(a * x0 + b * y0);
570 seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
571 seg->x[0] = x0;
572 seg->x[1] = x1;
573 seg->y0 = y0;
574 seg->y1 = y1;
575 seg->n_stack = 1;
576 seg->stack[0].x = x1;
577 seg->stack[0].y = y1;
578 }
580 /**
581 * art_svp_intersect_add_horiz: Add point to horizontal list.
582 * @ctx: Intersector context.
583 * @seg: Segment with point to insert into horizontal list.
584 *
585 * Inserts @seg into horizontal list, keeping it in ascending horiz_x
586 * order.
587 *
588 * Note: the horiz_commit routine processes "clusters" of segs in the
589 * horiz list, all sharing the same horiz_x value. The cluster is
590 * processed in active list order, rather than horiz list order. Thus,
591 * the order of segs in the horiz list sharing the same horiz_x
592 * _should_ be irrelevant. Even so, we use b as a secondary sorting key,
593 * as a "belt and suspenders" defensive coding tactic.
594 **/
595 static void
596 art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
597 {
598 ArtActiveSeg **pp = &ctx->horiz_last;
599 ArtActiveSeg *place;
600 ArtActiveSeg *place_right = NULL;
603 #ifdef CHEAP_SANITYCHECK
604 if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
605 {
606 art_warn ("*** attempt to put segment in horiz list twice\n");
607 return;
608 }
609 seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
610 #endif
612 #ifdef VERBOSE
613 printf ("add_horiz %lx, x = %g\n", (unsigned long) seg, seg->horiz_x);
614 #endif
615 for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
616 (place->horiz_x == seg->horiz_x &&
617 place->b < seg->b));
618 place = *pp)
619 {
620 place_right = place;
621 pp = &place->horiz_left;
622 }
623 *pp = seg;
624 seg->horiz_left = place;
625 seg->horiz_right = place_right;
626 if (place == NULL)
627 ctx->horiz_first = seg;
628 else
629 place->horiz_right = seg;
630 }
632 static void
633 art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
634 double x, double y)
635 {
636 ArtPriPoint *pri_pt;
637 int n_stack = seg->n_stack;
639 if (n_stack == seg->n_stack_max)
640 art_expand (seg->stack, ArtPoint, seg->n_stack_max);
641 seg->stack[n_stack].x = x;
642 seg->stack[n_stack].y = y;
643 seg->n_stack++;
645 seg->x[1] = x;
646 seg->y1 = y;
648 pri_pt = art_new (ArtPriPoint, 1);
649 pri_pt->x = x;
650 pri_pt->y = y;
651 pri_pt->user_data = seg;
652 art_pri_insert (ctx->pq, pri_pt);
653 }
655 /**
656 * art_svp_intersect_break: Break an active segment.
657 *
658 * Note: y must be greater than the top point's y, and less than
659 * the bottom's.
660 *
661 * Return value: x coordinate of break point.
662 */
663 static double
664 art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
665 double y)
666 {
667 double x0, y0, x1, y1;
668 const ArtSVPSeg *in_seg = seg->in_seg;
669 int in_curs = seg->in_curs;
670 double x;
672 x0 = in_seg->points[in_curs - 1].x;
673 y0 = in_seg->points[in_curs - 1].y;
674 x1 = in_seg->points[in_curs].x;
675 y1 = in_seg->points[in_curs].y;
676 x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
678 /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
679 arithmetic, but it might be worthwhile to check just in case. */
681 if (y > ctx->y)
682 art_svp_intersect_push_pt (ctx, seg, x, y);
683 else
684 {
685 seg->x[0] = x;
686 seg->y0 = y;
687 seg->horiz_x = x;
688 art_svp_intersect_add_horiz (ctx, seg);
689 }
691 return x;
692 }
694 /**
695 * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
696 * @ctx: Intersector context.
697 * @x: X coordinate of point to add.
698 * @y: Y coordinate of point to add.
699 * @seg: "nearby" segment, or NULL if leftmost.
700 *
701 * Return value: Segment immediately to the left of the new point, or
702 * NULL if the new point is leftmost.
703 **/
704 static ArtActiveSeg *
705 art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
706 ArtActiveSeg *seg)
707 {
708 ArtActiveSeg *left, *right;
709 double x_min = x, x_max = x;
710 art_boolean left_live, right_live;
711 double d;
712 double new_x;
713 ArtActiveSeg *test, *result = NULL;
714 double x_test;
716 left = seg;
717 if (left == NULL)
718 right = ctx->active_head;
719 else
720 right = left->right;
721 left_live = (left != NULL);
722 right_live = (right != NULL);
723 while (left_live || right_live)
724 {
725 if (left_live)
726 {
727 if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
728 /* It may be that one of these conjuncts turns out to be always
729 true. We test both anyway, to be defensive. */
730 y != left->y0 && y < left->y1)
731 {
732 d = x_min * left->a + y * left->b + left->c;
733 if (d < EPSILON_A)
734 {
735 new_x = art_svp_intersect_break (ctx, left, y);
736 if (new_x > x_max)
737 {
738 x_max = new_x;
739 right_live = (right != NULL);
740 }
741 else if (new_x < x_min)
742 x_min = new_x;
743 left = left->left;
744 left_live = (left != NULL);
745 }
746 else
747 left_live = ART_FALSE;
748 }
749 else
750 left_live = ART_FALSE;
751 }
752 else if (right_live)
753 {
754 if (x <= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
755 /* It may be that one of these conjuncts turns out to be always
756 true. We test both anyway, to be defensive. */
757 y != right->y0 && y < right->y1)
758 {
759 d = x_max * right->a + y * right->b + right->c;
760 if (d > -EPSILON_A)
761 {
762 new_x = art_svp_intersect_break (ctx, right, y);
763 if (new_x < x_min)
764 {
765 x_min = new_x;
766 left_live = (left != NULL);
767 }
768 else if (new_x >= x_max)
769 x_max = new_x;
770 right = right->right;
771 right_live = (right != NULL);
772 }
773 else
774 right_live = ART_FALSE;
775 }
776 else
777 right_live = ART_FALSE;
778 }
779 }
781 /* Now, (left, right) defines an interval of segments broken. Sort
782 into ascending x order. */
783 test = left == NULL ? ctx->active_head : left->right;
784 result = left;
785 if (test != NULL && test != right)
786 {
787 x_test = test->x[1];
788 for (;;)
789 {
790 if (x_test <= x)
791 result = test;
792 test = test->right;
793 if (test == right)
794 break;
795 new_x = test->x[1];
796 if (new_x < x_test)
797 {
798 art_warn ("art_svp_intersect_add_point: non-ascending x\n");
799 }
800 x_test = new_x;
801 }
802 }
803 return result;
804 }
806 static void
807 art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
808 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
809 {
810 right_seg->left = left_seg->left;
811 if (right_seg->left != NULL)
812 right_seg->left->right = right_seg;
813 else
814 ctx->active_head = right_seg;
815 left_seg->right = right_seg->right;
816 if (left_seg->right != NULL)
817 left_seg->right->left = left_seg;
818 left_seg->left = right_seg;
819 right_seg->right = left_seg;
820 }
822 typedef enum {
823 ART_BREAK_LEFT = 1,
824 ART_BREAK_RIGHT = 2
825 } ArtBreakFlags;
827 /**
828 * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
829 * @ctx: Intersector context.
830 * @left_seg: Left segment of the pair.
831 * @right_seg: Right segment of the pair.
832 * @break_flags: Flags indicating whether to break neighbors.
833 *
834 * Tests crossing of @left_seg and @right_seg. If there is a crossing,
835 * inserts the intersection point into both segments.
836 *
837 * Return value: True if the intersection took place at the current
838 * scan line, indicating further iteration is needed.
839 **/
840 static art_boolean
841 art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
842 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
843 ArtBreakFlags break_flags)
844 {
845 double left_x0, left_y0, left_x1;
846 double left_y1 = left_seg->y1;
847 double right_y1 = right_seg->y1;
848 double d;
850 const ArtSVPSeg *in_seg;
851 int in_curs;
852 double d0, d1, t;
853 double x, y; /* intersection point */
855 #ifdef VERBOSE
856 static int count = 0;
858 printf ("art_svp_intersect_test_cross %lx <-> %lx: count=%d\n",
859 (unsigned long)left_seg, (unsigned long)right_seg, count++);
860 #endif
862 if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
863 {
864 if (left_seg->b < right_seg->b)
865 {
866 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
867 return ART_TRUE;
868 }
869 else
870 return ART_FALSE;
871 }
873 if (left_y1 < right_y1)
874 {
875 /* Test left (x1, y1) against right segment */
876 double left_x1 = left_seg->x[1];
878 if (left_x1 <
879 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
880 left_y1 == right_seg->y0)
881 return ART_FALSE;
882 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
883 if (d < -EPSILON_A)
884 return ART_FALSE;
885 else if (d < EPSILON_A)
886 {
887 double right_x1 = art_svp_intersect_break (ctx, right_seg, left_y1);
888 if (left_x1 <= right_x1)
889 return ART_FALSE;
890 }
891 }
892 else if (left_y1 > right_y1)
893 {
894 /* Test right (x1, y1) against left segment */
895 double right_x1 = right_seg->x[1];
897 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
898 right_y1 == left_seg->y0)
899 return ART_FALSE;
900 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
901 if (d > EPSILON_A)
902 return ART_FALSE;
903 else if (d > -EPSILON_A)
904 {
905 double left_x1 = art_svp_intersect_break (ctx, left_seg, right_y1);
906 if (left_x1 <= right_x1)
907 return ART_FALSE;
908 }
909 }
910 else /* left_y1 == right_y1 */
911 {
912 double left_x1 = left_seg->x[1];
913 double right_x1 = right_seg->x[1];
915 if (left_x1 <= right_x1)
916 return ART_FALSE;
917 }
919 /* The segments cross. Find the intersection point. */
921 in_seg = left_seg->in_seg;
922 in_curs = left_seg->in_curs;
923 left_x0 = in_seg->points[in_curs - 1].x;
924 left_y0 = in_seg->points[in_curs - 1].y;
925 left_x1 = in_seg->points[in_curs].x;
926 left_y1 = in_seg->points[in_curs].y;
927 d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
928 d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
929 if (d0 == d1)
930 {
931 x = left_x0;
932 y = left_y0;
933 }
934 else
935 {
936 /* Is this division always safe? It could possibly overflow. */
937 t = d0 / (d0 - d1);
938 if (t <= 0)
939 {
940 x = left_x0;
941 y = left_y0;
942 }
943 else if (t >= 1)
944 {
945 x = left_x1;
946 y = left_y1;
947 }
948 else
949 {
950 x = left_x0 + t * (left_x1 - left_x0);
951 y = left_y0 + t * (left_y1 - left_y0);
952 }
953 }
955 /* Make sure intersection point is within bounds of right seg. */
956 if (y < right_seg->y0)
957 {
958 x = right_seg->x[0];
959 y = right_seg->y0;
960 }
961 else if (y > right_seg->y1)
962 {
963 x = right_seg->x[1];
964 y = right_seg->y1;
965 }
966 else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
967 x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
968 else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
969 x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
971 if (y == left_seg->y0)
972 {
973 if (y != right_seg->y0)
974 {
975 #ifdef VERBOSE
976 printf ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n",
977 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
978 #endif
979 art_svp_intersect_push_pt (ctx, right_seg, x, y);
980 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
981 art_svp_intersect_add_point (ctx, x, y, right_seg->right);
982 }
983 else
984 {
985 /* Intersection takes place at current scan line; process
986 immediately rather than queueing intersection point into
987 priq. */
989 /* Choose "most vertical" segement */
990 if (left_seg->a > right_seg->a)
991 x = left_seg->x[0];
992 else
993 x = right_seg->x[0];
994 /* todo: fudge x */
996 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
997 return ART_TRUE;
998 }
999 }
1000 else if (y == right_seg->y0)
1001 {
1002 #ifdef VERBOSE
1003 printf ("*** art_svp_intersect_test_cross: intersection (%g, %g) matches latter y0 of %lx, %lx\n",
1004 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1005 #endif
1006 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1007 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1008 art_svp_intersect_add_point (ctx, x, y, left_seg->left);
1009 }
1010 else
1011 {
1012 #ifdef VERBOSE
1013 printf ("Inserting (%g, %g) into %lx, %lx\n",
1014 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1015 #endif
1016 /* Insert the intersection point into both segments. */
1017 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1018 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1019 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1020 art_svp_intersect_add_point (ctx, x, y, left_seg->left);
1021 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1022 art_svp_intersect_add_point (ctx, x, y, right_seg->right);
1023 }
1024 return ART_FALSE;
1025 }
1027 /**
1028 * art_svp_intersect_active_delete: Delete segment from active list.
1029 * @ctx: Intersection context.
1030 * @seg: Segment to delete.
1031 *
1032 * Deletes @seg from the active list.
1033 **/
1034 static /* todo inline */ void
1035 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1036 {
1037 ArtActiveSeg *left = seg->left, *right = seg->right;
1039 if (left != NULL)
1040 left->right = right;
1041 else
1042 ctx->active_head = right;
1043 if (right != NULL)
1044 right->left = left;
1045 }
1047 /**
1048 * art_svp_intersect_active_free: Free an active segment.
1049 * @seg: Segment to delete.
1050 *
1051 * Frees @seg.
1052 **/
1053 static /* todo inline */ void
1054 art_svp_intersect_active_free (ArtActiveSeg *seg)
1055 {
1056 art_free (seg->stack);
1057 #ifdef VERBOSE
1058 printf ("Freeing %lx\n", (unsigned long) seg);
1059 #endif
1060 art_free (seg);
1061 }
1063 /**
1064 * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1065 *
1066 * Tests @seg against its left and right neighbors for intersections.
1067 * Precondition: the line in @seg is not purely horizontal.
1068 **/
1069 static void
1070 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1071 ArtActiveSeg *seg)
1072 {
1073 ArtActiveSeg *left = seg, *right = seg;
1075 for (;;)
1076 {
1077 if (left != NULL && left->left != NULL)
1078 {
1079 if (art_svp_intersect_test_cross (ctx, left->left, left,
1080 ART_BREAK_LEFT))
1081 {
1082 if (left == right || right == NULL)
1083 right = left->right;
1084 }
1085 else
1086 {
1087 left = NULL;
1088 }
1089 }
1090 else if (right != NULL && right->right != NULL)
1091 {
1092 if (art_svp_intersect_test_cross (ctx, right, right->right,
1093 ART_BREAK_RIGHT))
1094 {
1095 if (left == right || left == NULL)
1096 left = right->left;
1097 }
1098 else
1099 {
1100 right = NULL;
1101 }
1102 }
1103 else
1104 break;
1105 }
1106 }
1108 /**
1109 * art_svp_intersect_horiz: Add horizontal line segment.
1110 * @ctx: Intersector context.
1111 * @seg: Segment on which to add horizontal line.
1112 * @x0: Old x position.
1113 * @x1: New x position.
1114 *
1115 * Adds a horizontal line from @x0 to @x1, and updates the current
1116 * location of @seg to @x1.
1117 **/
1118 static void
1119 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1120 double x0, double x1)
1121 {
1122 ArtActiveSeg *hs;
1124 if (x0 == x1)
1125 return;
1127 hs = art_new (ArtActiveSeg, 1);
1129 hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1130 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1131 {
1132 ArtSvpWriter *swr = ctx->out;
1134 swr->add_point (swr, seg->seg_id, x0, ctx->y);
1135 }
1136 hs->seg_id = seg->seg_id;
1137 hs->horiz_x = x0;
1138 hs->horiz_delta_wind += seg->delta_wind;
1139 hs->stack = NULL;
1140 hs->horiz_delta_wind = 0;
1141 seg->horiz_delta_wind -= seg->delta_wind;
1143 art_svp_intersect_add_horiz (ctx, hs);
1145 if (x0 > x1)
1146 {
1147 ArtActiveSeg *left;
1149 for (left = seg->left; left != NULL; left = seg->left)
1150 {
1151 int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1153 if (left->x[left_bneg] <= x1)
1154 break;
1155 if (left->x[left_bneg ^ 1] <= x1 &&
1156 x1 * left->a + ctx->y * left->b + left->c >= 0)
1157 break;
1158 if (left->y0 != ctx->y && left->y1 != ctx->y)
1159 {
1160 art_svp_intersect_break (ctx, left, ctx->y);
1161 }
1162 #ifdef VERBOSE
1163 printf ("x0=%g > x1=%g, swapping %lx, %lx\n",
1164 x0, x1, (unsigned long)left, (unsigned long)seg);
1165 #endif
1166 art_svp_intersect_swap_active (ctx, left, seg);
1167 }
1168 }
1169 else
1170 {
1171 ArtActiveSeg *right;
1173 for (right = seg->right; right != NULL; right = seg->right)
1174 {
1175 int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1177 if (right->x[right_bneg ^ 1] >= x1)
1178 break;
1179 if (right->x[right_bneg] >= x1 &&
1180 x1 * right->a + ctx->y * right->b + right->c <= 0)
1181 break;
1182 if (right->y0 != ctx->y && right->y1 != ctx->y)
1183 {
1184 art_svp_intersect_break (ctx, right, ctx->y);
1185 }
1186 #ifdef VERBOSE
1187 printf ("x0=%g < x1=%g, swapping %lx, %lx\n",
1188 x0, x1, (unsigned long)seg, (unsigned long)right);
1189 #endif
1190 art_svp_intersect_swap_active (ctx, seg, right);
1191 }
1192 }
1194 seg->x[0] = x1;
1195 seg->x[1] = x1;
1196 seg->horiz_x = x1;
1197 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1198 }
1200 /**
1201 * art_svp_intersect_insert_line: Insert a line into the active list.
1202 * @ctx: Intersector context.
1203 * @seg: Segment containing line to insert.
1204 *
1205 * Inserts the line into the intersector context, taking care of any
1206 * intersections, and adding the appropriate horizontal points to the
1207 * active list.
1208 **/
1209 static void
1210 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1211 {
1212 if (seg->y1 == seg->y0)
1213 {
1214 #ifdef VERBOSE
1215 printf ("art_svp_intersect_insert_line: %lx is horizontal\n",
1216 (unsigned long)seg);
1217 #endif
1218 art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1219 }
1220 else
1221 {
1222 art_svp_intersect_insert_cross (ctx, seg);
1223 art_svp_intersect_add_horiz (ctx, seg);
1224 }
1225 }
1227 static void
1228 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1229 ArtActiveSeg *seg)
1230 {
1231 int n_stack = --seg->n_stack;
1232 seg->x[1] = seg->stack[n_stack - 1].x;
1233 seg->y1 = seg->stack[n_stack - 1].y;
1234 seg->x[0] = seg->stack[n_stack].x;
1235 seg->y0 = seg->stack[n_stack].y;
1236 seg->horiz_x = seg->x[0];
1237 art_svp_intersect_insert_line (ctx, seg);
1238 }
1240 static void
1241 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1242 ArtPriPoint *pri_pt)
1243 {
1244 const ArtSVPSeg *in_seg = seg->in_seg;
1245 int in_curs = seg->in_curs;
1246 ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1248 if (swr != NULL)
1249 swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1250 if (in_curs + 1 == in_seg->n_points)
1251 {
1252 ArtActiveSeg *left = seg->left, *right = seg->right;
1254 #if 0
1255 if (swr != NULL)
1256 swr->close_segment (swr, seg->seg_id);
1257 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1258 #endif
1259 seg->flags |= ART_ACTIVE_FLAGS_DEL;
1260 art_svp_intersect_add_horiz (ctx, seg);
1261 art_svp_intersect_active_delete (ctx, seg);
1262 if (left != NULL && right != NULL)
1263 art_svp_intersect_test_cross (ctx, left, right,
1264 ART_BREAK_LEFT | ART_BREAK_RIGHT);
1265 art_free (pri_pt);
1266 }
1267 else
1268 {
1269 seg->horiz_x = seg->x[1];
1271 art_svp_intersect_setup_seg (seg, pri_pt);
1272 art_pri_insert (ctx->pq, pri_pt);
1273 art_svp_intersect_insert_line (ctx, seg);
1274 }
1275 }
1277 static void
1278 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1279 {
1280 ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1281 ArtActiveSeg *test;
1282 double x0, y0;
1283 ArtActiveSeg *beg_range;
1284 ArtActiveSeg *last = NULL;
1285 ArtActiveSeg *left, *right;
1286 ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1288 seg->flags = 0;
1289 seg->in_seg = in_seg;
1290 seg->in_curs = 0;
1292 seg->n_stack_max = 4;
1293 seg->stack = art_new (ArtPoint, seg->n_stack_max);
1295 seg->horiz_delta_wind = 0;
1297 pri_pt->user_data = seg;
1298 art_svp_intersect_setup_seg (seg, pri_pt);
1299 art_pri_insert (ctx->pq, pri_pt);
1301 /* Find insertion place for new segment */
1302 /* This is currently a left-to-right scan, but should be replaced
1303 with a binary search as soon as it's validated. */
1305 x0 = in_seg->points[0].x;
1306 y0 = in_seg->points[0].y;
1307 beg_range = NULL;
1308 for (test = ctx->active_head; test != NULL; test = test->right)
1309 {
1310 double d;
1311 int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1313 if (x0 < test->x[test_bneg])
1314 {
1315 if (x0 < test->x[test_bneg ^ 1])
1316 break;
1317 d = x0 * test->a + y0 * test->b + test->c;
1318 if (d < 0)
1319 break;
1320 }
1321 last = test;
1322 }
1324 left = art_svp_intersect_add_point (ctx, x0, y0, last);
1325 seg->left = left;
1326 if (left == NULL)
1327 {
1328 right = ctx->active_head;
1329 ctx->active_head = seg;
1330 }
1331 else
1332 {
1333 right = left->right;
1334 left->right = seg;
1335 }
1336 seg->right = right;
1337 if (right != NULL)
1338 right->left = seg;
1340 seg->delta_wind = in_seg->dir ? 1 : -1;
1341 seg->horiz_x = x0;
1343 art_svp_intersect_insert_line (ctx, seg);
1344 }
1346 #ifdef SANITYCHECK
1347 static void
1348 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1349 {
1350 #if 0
1351 /* At this point, we seem to be getting false positives, so it's
1352 turned off for now. */
1354 ArtActiveSeg *seg;
1355 int winding_number = 0;
1357 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1358 {
1359 /* Check winding number consistency. */
1360 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1361 {
1362 if (winding_number != seg->wind_left)
1363 art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %lx has wind_left of %d, expected %d\n",
1364 (unsigned long) seg, seg->wind_left, winding_number);
1365 winding_number = seg->wind_left + seg->delta_wind;
1366 }
1367 }
1368 if (winding_number != 0)
1369 art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1370 winding_number);
1371 #endif
1372 }
1373 #endif
1375 /**
1376 * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1377 * @ctx: Intersection context.
1378 *
1379 * The main function of the horizontal commit is to output new
1380 * points to the output writer.
1381 *
1382 * This "commit" pass is also where winding numbers are assigned,
1383 * because doing it here provides much greater tolerance for inputs
1384 * which are not in strict SVP order.
1385 *
1386 * Each cluster in the horiz_list contains both segments that are in
1387 * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1388 * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1389 * need to deal with both.
1390 **/
1391 static void
1392 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1393 {
1394 ArtActiveSeg *seg;
1395 int winding_number = 0; /* initialization just to avoid warning */
1396 int horiz_wind = 0;
1397 double last_x = 0; /* initialization just to avoid warning */
1399 #ifdef VERBOSE
1400 printf ("art_svp_intersect_horiz_commit: y=%g\n", ctx->y);
1401 for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1402 printf (" %lx: %g %+d\n",
1403 (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind);
1404 #endif
1406 /* Output points to svp writer. */
1407 for (seg = ctx->horiz_first; seg != NULL;)
1408 {
1409 /* Find a cluster with common horiz_x, */
1410 ArtActiveSeg *curs;
1411 double x = seg->horiz_x;
1413 /* Generate any horizontal segments. */
1414 if (horiz_wind != 0)
1415 {
1416 ArtSvpWriter *swr = ctx->out;
1417 int seg_id;
1419 seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1420 last_x, ctx->y);
1421 swr->add_point (swr, seg_id, x, ctx->y);
1422 swr->close_segment (swr, seg_id);
1423 }
1425 /* Find first active segment in cluster. */
1427 for (curs = seg; curs != NULL && curs->horiz_x == x;
1428 curs = curs->horiz_right)
1429 if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1430 break;
1432 if (curs != NULL && curs->horiz_x == x)
1433 {
1434 /* There exists at least one active segment in this cluster. */
1436 /* Find beginning of cluster. */
1437 for (; curs->left != NULL; curs = curs->left)
1438 if (curs->left->horiz_x != x)
1439 break;
1441 if (curs->left != NULL)
1442 winding_number = curs->left->wind_left + curs->left->delta_wind;
1443 else
1444 winding_number = 0;
1446 do
1447 {
1448 #ifdef VERBOSE
1449 printf (" winding_number = %d += %d\n",
1450 winding_number, curs->delta_wind);
1451 #endif
1452 if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1453 curs->wind_left != winding_number)
1454 {
1455 ArtSvpWriter *swr = ctx->out;
1457 if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1458 {
1459 swr->add_point (swr, curs->seg_id,
1460 curs->horiz_x, ctx->y);
1461 swr->close_segment (swr, curs->seg_id);
1462 }
1464 curs->seg_id = swr->add_segment (swr, winding_number,
1465 curs->delta_wind,
1466 x, ctx->y);
1467 curs->flags |= ART_ACTIVE_FLAGS_OUT;
1468 }
1469 curs->wind_left = winding_number;
1470 winding_number += curs->delta_wind;
1471 curs = curs->right;
1472 }
1473 while (curs != NULL && curs->horiz_x == x);
1474 }
1476 /* Skip past cluster. */
1477 do
1478 {
1479 ArtActiveSeg *next = seg->horiz_right;
1481 seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1482 horiz_wind += seg->horiz_delta_wind;
1483 seg->horiz_delta_wind = 0;
1484 if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1485 {
1486 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1487 {
1488 ArtSvpWriter *swr = ctx->out;
1489 swr->close_segment (swr, seg->seg_id);
1490 }
1491 art_svp_intersect_active_free (seg);
1492 }
1493 seg = next;
1494 }
1495 while (seg != NULL && seg->horiz_x == x);
1497 last_x = x;
1498 }
1499 ctx->horiz_first = NULL;
1500 ctx->horiz_last = NULL;
1501 #ifdef SANITYCHECK
1502 art_svp_intersect_sanitycheck_winding (ctx);
1503 #endif
1504 }
1506 #ifdef VERBOSE
1507 static void
1508 art_svp_intersect_print_active (ArtIntersectCtx *ctx)
1509 {
1510 ArtActiveSeg *seg;
1512 printf ("Active list (y = %g):\n", ctx->y);
1513 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1514 {
1515 printf (" %lx: (%g, %g)-(%g, %g), (a, b, c) = (%g, %g, %g)\n",
1516 (unsigned long)seg,
1517 seg->x[0], seg->y0, seg->x[1], seg->y1,
1518 seg->a, seg->b, seg->c);
1519 }
1520 }
1521 #endif
1523 #ifdef SANITYCHECK
1524 static void
1525 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx)
1526 {
1527 ArtActiveSeg *seg;
1528 ArtActiveSeg *last = NULL;
1529 double d;
1531 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1532 {
1533 if (seg->left != last)
1534 {
1535 art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n",
1536 (unsigned long)last, (unsigned long)seg->left);
1537 }
1538 if (last != NULL)
1539 {
1540 /* pairwise compare with previous seg */
1542 /* First the top. */
1543 if (last->y0 < seg->y0)
1544 {
1545 }
1546 else
1547 {
1548 }
1550 /* Then the bottom. */
1551 if (last->y1 < seg->y1)
1552 {
1553 if (!((last->x[1] <
1554 seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1555 last->y1 == seg->y0))
1556 {
1557 d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1558 if (d >= -EPSILON_A)
1559 art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n",
1560 last->x[1], last->y1, (unsigned long) last,
1561 (unsigned long) seg, d);
1562 }
1563 }
1564 else if (last->y1 > seg->y1)
1566 {
1567 if (!((seg->x[1] >
1568 last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1569 seg->y1 == last->y0))
1570 {
1571 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1572 if (d <= EPSILON_A)
1573 art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n",
1574 seg->x[1], seg->y1, (unsigned long) seg,
1575 (unsigned long) last, d);
1576 }
1577 }
1578 else
1579 {
1580 if (last->x[1] > seg->x[1])
1581 art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n",
1582 last->x[1], last->y1, (unsigned long)last,
1583 seg->x[1], seg->y1, (unsigned long)seg);
1584 }
1585 }
1586 last = seg;
1587 }
1588 }
1589 #endif
1591 void
1592 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
1593 {
1594 ArtIntersectCtx *ctx;
1595 ArtPriQ *pq;
1596 ArtPriPoint *first_point;
1597 #ifdef VERBOSE
1598 int count = 0;
1599 #endif
1601 if (in->n_segs == 0)
1602 return;
1604 ctx = art_new (ArtIntersectCtx, 1);
1605 ctx->in = in;
1606 ctx->out = out;
1607 pq = art_pri_new ();
1608 ctx->pq = pq;
1610 ctx->active_head = NULL;
1612 ctx->horiz_first = NULL;
1613 ctx->horiz_last = NULL;
1615 ctx->in_curs = 0;
1616 first_point = art_new (ArtPriPoint, 1);
1617 first_point->x = in->segs[0].points[0].x;
1618 first_point->y = in->segs[0].points[0].y;
1619 first_point->user_data = NULL;
1620 ctx->y = first_point->y;
1621 art_pri_insert (pq, first_point);
1623 while (!art_pri_empty (pq))
1624 {
1625 ArtPriPoint *pri_point = art_pri_choose (pq);
1626 ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
1628 #ifdef VERBOSE
1629 printf ("\nIntersector step %d\n", count++);
1630 art_svp_intersect_print_active (ctx);
1631 printf ("priq choose (%g, %g) %lx\n", pri_point->x, pri_point->y,
1632 (unsigned long)pri_point->user_data);
1633 #endif
1634 #ifdef SANITYCHECK
1635 art_svp_intersect_sanitycheck(ctx);
1636 #endif
1638 if (ctx->y != pri_point->y)
1639 {
1640 art_svp_intersect_horiz_commit (ctx);
1641 ctx->y = pri_point->y;
1642 }
1644 if (seg == NULL)
1645 {
1646 /* Insert new segment from input */
1647 const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++];
1648 art_svp_intersect_add_seg (ctx, in_seg);
1649 if (ctx->in_curs < in->n_segs)
1650 {
1651 const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
1652 pri_point->x = next_seg->points[0].x;
1653 pri_point->y = next_seg->points[0].y;
1654 /* user_data is already NULL */
1655 art_pri_insert (pq, pri_point);
1656 }
1657 else
1658 art_free (pri_point);
1659 }
1660 else
1661 {
1662 int n_stack = seg->n_stack;
1664 if (n_stack > 1)
1665 {
1666 art_svp_intersect_process_intersection (ctx, seg);
1667 art_free (pri_point);
1668 }
1669 else
1670 {
1671 art_svp_intersect_advance_cursor (ctx, seg, pri_point);
1672 }
1673 }
1674 }
1676 art_svp_intersect_horiz_commit (ctx);
1678 art_pri_free (pq);
1679 art_free (ctx);
1680 }
1682 #endif /* not TEST_PRIQ */