1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 2001 Raph Levien
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.
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.
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.
20 /* This file contains a testbed implementation of the new intersection
25 #include "art_svp_intersect.h"
27 #include <math.h> /* for sqrt */
29 /* Sanitychecking verifies the main invariant on every priority queue
30 point. Do not use in production, as it slows things down way too
34 /* This can be used in production, to prevent hangs. Eventually, it
35 should not be necessary. */
36 #define CHEAP_SANITYCHECK
42 /* A priority queue - perhaps move to a separate file if it becomes
43 needed somewhere else */
45 #define ART_PRIQ_USE_HEAP
47 typedef struct _ArtPriQ ArtPriQ;
48 typedef struct _ArtPriPoint ArtPriPoint;
65 ArtPriQ *result = art_new (ArtPriQ, 1);
68 result->n_items_max = 16;
69 result->items = art_new (ArtPriPoint *, result->n_items_max);
74 art_pri_free (ArtPriQ *pq)
81 art_pri_empty (ArtPriQ *pq)
83 return pq->n_items == 0;
86 #ifdef ART_PRIQ_USE_HEAP
88 /* This heap implementation is based on Vasek Chvatal's course notes:
89 http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
92 art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing)
94 ArtPriPoint **items = pq->items;
97 parent = (vacant - 1) >> 1;
98 while (vacant > 0 && (missing->y < items[parent]->y ||
99 (missing->y == items[parent]->y &&
100 missing->x < items[parent]->x)))
102 items[vacant] = items[parent];
104 parent = (vacant - 1) >> 1;
107 items[vacant] = missing;
111 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
113 if (pq->n_items == pq->n_items_max)
114 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
116 art_pri_bubble_up (pq, pq->n_items++, point);
120 art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
122 ArtPriPoint **items = pq->items;
123 int vacant = 0, child = 2;
128 if (items[child - 1]->y < items[child]->y ||
129 (items[child - 1]->y == items[child]->y &&
130 items[child - 1]->x < items[child]->x))
132 items[vacant] = items[child];
134 child = (vacant + 1) << 1;
138 items[vacant] = items[n - 1];
142 art_pri_bubble_up (pq, vacant, missing);
146 art_pri_choose (ArtPriQ *pq)
148 ArtPriPoint *result = pq->items[0];
150 art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
156 /* Choose least point in queue */
158 art_pri_choose (ArtPriQ *pq)
162 double best_x, best_y;
166 if (pq->n_items == 0)
169 best_x = pq->items[best]->x;
170 best_y = pq->items[best]->y;
172 for (i = 1; i < pq->n_items; i++)
175 if (y < best_y || (y == best_y && pq->items[i]->x < best_x))
178 best_x = pq->items[best]->x;
182 result = pq->items[best];
183 pq->items[best] = pq->items[--pq->n_items];
188 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
190 if (pq->n_items == pq->n_items_max)
191 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
193 pq->items[pq->n_items++] = point;
200 #include <stdlib.h> /* for rand() */
204 double_rand (double lo, double hi, int quant)
206 int tmp = rand () / (RAND_MAX * (1.0 / quant)) + 0.5;
207 return lo + tmp * ((hi - lo) / quant);
211 * This custom allocator for priority queue points is here so I can
212 * test speed. It doesn't look like it will be that significant, but
213 * if I want a small improvement later, it's something.
216 typedef ArtPriPoint *ArtPriPtPool;
218 static ArtPriPtPool *
219 art_pri_pt_pool_new (void)
221 ArtPriPtPool *result = art_new (ArtPriPtPool, 1);
227 art_pri_pt_alloc (ArtPriPtPool *pool)
229 ArtPriPoint *result = *pool;
231 return art_new (ArtPriPoint, 1);
234 *pool = result->user_data;
240 art_pri_pt_free (ArtPriPtPool *pool, ArtPriPoint *pt)
242 pt->user_data = *pool;
247 art_pri_pt_pool_free (ArtPriPtPool *pool)
249 ArtPriPoint *pt = *pool;
252 ArtPriPoint *next = pt->user_data;
260 main (int argc, char **argv)
262 ArtPriPtPool *pool = art_pri_pt_pool_new ();
265 const int n_iter = 1;
266 const int pq_size = 100;
268 for (j = 0; j < n_iter; j++)
272 for (i = 0; i < pq_size; i++)
274 ArtPriPoint *pt = art_pri_pt_alloc (pool);
275 pt->x = double_rand (0, 1, 100);
276 pt->y = double_rand (0, 1, 100);
277 pt->user_data = (void *)i;
278 art_pri_insert (pq, pt);
281 while (!art_pri_empty (pq))
283 ArtPriPoint *pt = art_pri_choose (pq);
285 printf ("(%g, %g), %d\n", pt->x, pt->y, (int)pt->user_data);
286 art_pri_pt_free (pool, pt);
291 art_pri_pt_pool_free (pool);
295 #else /* TEST_PRIQ */
297 /* A virtual class for an "svp writer". A client of this object creates an
298 SVP by repeatedly calling "add segment" and "add point" methods on it.
301 typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
303 /* An implementation of the svp writer virtual class that applies the
306 struct _ArtSvpWriterRewind {
315 art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left,
316 int delta_wind, double x, double y)
318 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
321 art_boolean left_filled, right_filled;
322 int wind_right = wind_left + delta_wind;
324 const int init_n_points_max = 4;
328 case ART_WIND_RULE_NONZERO:
329 left_filled = (wind_left != 0);
330 right_filled = (wind_right != 0);
332 case ART_WIND_RULE_INTERSECT:
333 left_filled = (wind_left > 1);
334 right_filled = (wind_right > 1);
336 case ART_WIND_RULE_ODDEVEN:
337 left_filled = (wind_left & 1);
338 right_filled = (wind_right & 1);
340 case ART_WIND_RULE_POSITIVE:
341 left_filled = (wind_left > 0);
342 right_filled = (wind_right > 0);
345 art_die ("Unknown wind rule %d\n", swr->rule);
347 if (left_filled == right_filled)
349 /* discard segment now */
351 art_dprint ("swr add_segment: %d += %d (%g, %g) --> -1\n",
352 wind_left, delta_wind, x, y);
358 seg_num = svp->n_segs++;
359 if (swr->n_segs_max == seg_num)
361 swr->n_segs_max <<= 1;
362 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
363 (swr->n_segs_max - 1) *
366 swr->n_points_max = art_renew (swr->n_points_max, int,
369 seg = &svp->segs[seg_num];
371 seg->dir = right_filled;
372 swr->n_points_max[seg_num] = init_n_points_max;
377 seg->points = art_new (ArtPoint, init_n_points_max);
378 seg->points[0].x = x;
379 seg->points[0].y = y;
381 art_dprint ("swr add_segment: %d += %d (%g, %g) --> %d(%s)\n",
382 wind_left, delta_wind, x, y, seg_num,
383 seg->dir ? "v" : "^");
389 art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id,
392 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
397 art_dprint ("swr add_point: %d (%g, %g)\n", seg_id, x, y);
400 /* omitted segment */
403 seg = &swr->svp->segs[seg_id];
404 n_points = seg->n_points++;
405 if (swr->n_points_max[seg_id] == n_points)
406 art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
407 seg->points[n_points].x = x;
408 seg->points[n_points].y = y;
409 if (x < seg->bbox.x0)
411 if (x > seg->bbox.x1)
417 art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id)
419 /* Not needed for this simple implementation. A potential future
420 optimization is to merge segments that can be merged safely. */
422 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
427 seg = &swr->svp->segs[seg_id];
428 if (seg->n_points < 2)
429 art_warn ("*** closing segment %d with only %d point%s\n",
430 seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
435 art_dprint ("swr close_segment: %d\n", seg_id);
440 art_svp_writer_rewind_reap (ArtSvpWriter *self)
442 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
443 ArtSVP *result = swr->svp;
445 art_free (swr->n_points_max);
451 art_svp_writer_rewind_new (ArtWindRule rule)
453 ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
455 result->super.add_segment = art_svp_writer_rewind_add_segment;
456 result->super.add_point = art_svp_writer_rewind_add_point;
457 result->super.close_segment = art_svp_writer_rewind_close_segment;
460 result->n_segs_max = 16;
461 result->svp = (ArtSVP*)art_alloc (sizeof(ArtSVP) +
462 (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
463 result->svp->n_segs = 0;
464 result->n_points_max = (int*)art_new (int, result->n_segs_max);
466 return &result->super;
469 /* Now, data structures for the active list */
471 typedef struct _ArtActiveSeg ArtActiveSeg;
473 /* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
474 x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
475 #define ART_ACTIVE_FLAGS_BNEG 1
477 /* This flag is set if the segment has been inserted into the active
479 #define ART_ACTIVE_FLAGS_IN_ACTIVE 2
481 /* This flag is set when the segment is to be deleted in the
482 horiz commit process. */
483 #define ART_ACTIVE_FLAGS_DEL 4
485 /* This flag is set if the seg_id is a valid output segment. */
486 #define ART_ACTIVE_FLAGS_OUT 8
488 /* This flag is set if the segment is in the horiz list. */
489 #define ART_ACTIVE_FLAGS_IN_HORIZ 16
491 struct _ArtActiveSeg {
493 int wind_left, delta_wind;
494 ArtActiveSeg *left, *right; /* doubly linked list structure */
496 const ArtSVPSeg *in_seg;
501 double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
504 /* bottom point and intersection point stack */
509 /* horiz commit list */
510 ArtActiveSeg *horiz_left, *horiz_right;
512 int horiz_delta_wind;
516 typedef struct _ArtIntersectCtx ArtIntersectCtx;
518 struct _ArtIntersectCtx {
524 ArtActiveSeg *active_head;
527 ArtActiveSeg *horiz_first;
528 ArtActiveSeg *horiz_last;
530 /* segment index of next input segment to be added to pri q */
534 #define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
537 * art_svp_intersect_setup_seg: Set up an active segment from input segment.
538 * @seg: Active segment.
539 * @pri_pt: Priority queue point to initialize.
541 * Sets the x[], a, b, c, flags, and stack fields according to the
542 * line from the current cursor value. Sets the priority queue point
543 * to the bottom point of this line. Also advances the input segment
547 art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
549 const ArtSVPSeg *in_seg = seg->in_seg;
550 int in_curs = seg->in_curs++;
551 double x0, y0, x1, y1;
555 x0 = in_seg->points[in_curs].x;
556 y0 = in_seg->points[in_curs].y;
557 x1 = in_seg->points[in_curs + 1].x;
558 y1 = in_seg->points[in_curs + 1].y;
563 r2 = dx * dx + dy * dy;
564 s = r2 == 0 ? 1 : 1 / sqrt (r2);
566 seg->b = b = -dx * s;
567 seg->c = -(a * x0 + b * y0);
568 seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
574 seg->stack[0].x = x1;
575 seg->stack[0].y = y1;
579 * art_svp_intersect_add_horiz: Add point to horizontal list.
580 * @ctx: Intersector context.
581 * @seg: Segment with point to insert into horizontal list.
583 * Inserts @seg into horizontal list, keeping it in ascending horiz_x
586 * Note: the horiz_commit routine processes "clusters" of segs in the
587 * horiz list, all sharing the same horiz_x value. The cluster is
588 * processed in active list order, rather than horiz list order. Thus,
589 * the order of segs in the horiz list sharing the same horiz_x
590 * _should_ be irrelevant. Even so, we use b as a secondary sorting key,
591 * as a "belt and suspenders" defensive coding tactic.
594 art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
596 ArtActiveSeg **pp = &ctx->horiz_last;
598 ArtActiveSeg *place_right = NULL;
601 #ifdef CHEAP_SANITYCHECK
602 if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
604 //art_warn ("*** attempt to put segment in horiz list twice\n");
607 seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
611 art_dprint ("add_horiz %lx, x = %g\n", (unsigned long) seg, seg->horiz_x);
613 for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
614 (place->horiz_x == seg->horiz_x &&
619 pp = &place->horiz_left;
622 seg->horiz_left = place;
623 seg->horiz_right = place_right;
625 ctx->horiz_first = seg;
627 place->horiz_right = seg;
631 art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
635 int n_stack = seg->n_stack;
637 if (n_stack == seg->n_stack_max)
638 art_expand (seg->stack, ArtPoint, seg->n_stack_max);
639 seg->stack[n_stack].x = x;
640 seg->stack[n_stack].y = y;
646 pri_pt = art_new (ArtPriPoint, 1);
649 pri_pt->user_data = seg;
650 art_pri_insert (ctx->pq, pri_pt);
653 #define ART_BREAK_LEFT 1
654 #define ART_BREAK_RIGHT 2
657 * art_svp_intersect_break: Break an active segment.
659 * Note: y must be greater than the top point's y, and less than
662 * Return value: x coordinate of break point.
665 art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
666 double x_ref, double y, int break_flags)
668 double x0, y0, x1, y1;
669 const ArtSVPSeg *in_seg = seg->in_seg;
670 int in_curs = seg->in_curs;
673 x0 = in_seg->points[in_curs - 1].x;
674 y0 = in_seg->points[in_curs - 1].y;
675 x1 = in_seg->points[in_curs].x;
676 y1 = in_seg->points[in_curs].y;
677 x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
678 if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
679 (break_flags == ART_BREAK_RIGHT && x < x_ref))
682 art_dprint ("art_svp_intersect_break: limiting x to %f, was %f, %s\n",
683 x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right");
688 /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
689 arithmetic, but it might be worthwhile to check just in case. */
692 art_svp_intersect_push_pt (ctx, seg, x, y);
698 art_svp_intersect_add_horiz (ctx, seg);
705 * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
706 * @ctx: Intersector context.
707 * @x: X coordinate of point to add.
708 * @y: Y coordinate of point to add.
709 * @seg: "nearby" segment, or NULL if leftmost.
711 * Return value: Segment immediately to the left of the new point, or
712 * NULL if the new point is leftmost.
714 static ArtActiveSeg *
715 art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
716 ArtActiveSeg *seg, int break_flags)
718 ArtActiveSeg *left, *right;
719 double x_min = x, x_max = x;
720 art_boolean left_live, right_live;
723 ArtActiveSeg *test, *result = NULL;
728 right = ctx->active_head;
731 left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
732 right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
733 while (left_live || right_live)
737 if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
738 /* It may be that one of these conjuncts turns out to be always
739 true. We test both anyway, to be defensive. */
740 y != left->y0 && y < left->y1)
742 d = x_min * left->a + y * left->b + left->c;
745 new_x = art_svp_intersect_break (ctx, left, x_min, y,
750 right_live = (right != NULL);
752 else if (new_x < x_min)
755 left_live = (left != NULL);
758 left_live = ART_FALSE;
761 left_live = ART_FALSE;
765 if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
766 /* It may be that one of these conjuncts turns out to be always
767 true. We test both anyway, to be defensive. */
768 y != right->y0 && y < right->y1)
770 d = x_max * right->a + y * right->b + right->c;
773 new_x = art_svp_intersect_break (ctx, right, x_max, y,
778 left_live = (left != NULL);
780 else if (new_x >= x_max)
782 right = right->right;
783 right_live = (right != NULL);
786 right_live = ART_FALSE;
789 right_live = ART_FALSE;
793 /* Ascending order is guaranteed by break_flags. Thus, we don't need
794 to actually fix up non-ascending pairs. */
796 /* Now, (left, right) defines an interval of segments broken. Sort
797 into ascending x order. */
798 test = left == NULL ? ctx->active_head : left->right;
800 if (test != NULL && test != right)
804 else /* assert y == test->y1, I think */
816 art_warn ("art_svp_intersect_add_point: non-ascending x\n");
825 art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
826 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
828 right_seg->left = left_seg->left;
829 if (right_seg->left != NULL)
830 right_seg->left->right = right_seg;
832 ctx->active_head = right_seg;
833 left_seg->right = right_seg->right;
834 if (left_seg->right != NULL)
835 left_seg->right->left = left_seg;
836 left_seg->left = right_seg;
837 right_seg->right = left_seg;
841 * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
842 * @ctx: Intersector context.
843 * @left_seg: Left segment of the pair.
844 * @right_seg: Right segment of the pair.
845 * @break_flags: Flags indicating whether to break neighbors.
847 * Tests crossing of @left_seg and @right_seg. If there is a crossing,
848 * inserts the intersection point into both segments.
850 * Return value: True if the intersection took place at the current
851 * scan line, indicating further iteration is needed.
854 art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
855 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
858 double left_x0, left_y0, left_x1;
859 double left_y1 = left_seg->y1;
860 double right_y1 = right_seg->y1;
863 const ArtSVPSeg *in_seg;
866 double x, y; /* intersection point */
869 static int count = 0;
871 art_dprint ("art_svp_intersect_test_cross %lx <-> %lx: count=%d\n",
872 (unsigned long)left_seg, (unsigned long)right_seg, count++);
875 if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
877 /* Top points of left and right segments coincide. This case
878 feels like a bit of duplication - we may want to merge it
879 with the cases below. However, this way, we're sure that this
880 logic makes only localized changes. */
882 if (left_y1 < right_y1)
884 /* Test left (x1, y1) against right segment */
885 double left_x1 = left_seg->x[1];
888 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
889 left_y1 == right_seg->y0)
891 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
894 else if (d < EPSILON_A)
896 /* I'm unsure about the break flags here. */
897 double right_x1 = art_svp_intersect_break (ctx, right_seg,
900 if (left_x1 <= right_x1)
904 else if (left_y1 > right_y1)
906 /* Test right (x1, y1) against left segment */
907 double right_x1 = right_seg->x[1];
909 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
910 right_y1 == left_seg->y0)
912 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
915 else if (d > -EPSILON_A)
917 /* See above regarding break flags. */
918 double left_x1 = art_svp_intersect_break (ctx, left_seg,
921 if (left_x1 <= right_x1)
925 else /* left_y1 == right_y1 */
927 double left_x1 = left_seg->x[1];
928 double right_x1 = right_seg->x[1];
930 if (left_x1 <= right_x1)
933 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
937 if (left_y1 < right_y1)
939 /* Test left (x1, y1) against right segment */
940 double left_x1 = left_seg->x[1];
943 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
944 left_y1 == right_seg->y0)
946 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
949 else if (d < EPSILON_A)
951 double right_x1 = art_svp_intersect_break (ctx, right_seg,
954 if (left_x1 <= right_x1)
958 else if (left_y1 > right_y1)
960 /* Test right (x1, y1) against left segment */
961 double right_x1 = right_seg->x[1];
963 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
964 right_y1 == left_seg->y0)
966 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
969 else if (d > -EPSILON_A)
971 double left_x1 = art_svp_intersect_break (ctx, left_seg,
974 if (left_x1 <= right_x1)
978 else /* left_y1 == right_y1 */
980 double left_x1 = left_seg->x[1];
981 double right_x1 = right_seg->x[1];
983 if (left_x1 <= right_x1)
987 /* The segments cross. Find the intersection point. */
989 in_seg = left_seg->in_seg;
990 in_curs = left_seg->in_curs;
991 left_x0 = in_seg->points[in_curs - 1].x;
992 left_y0 = in_seg->points[in_curs - 1].y;
993 left_x1 = in_seg->points[in_curs].x;
994 left_y1 = in_seg->points[in_curs].y;
995 d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
996 d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1004 /* Is this division always safe? It could possibly overflow. */
1018 x = left_x0 + t * (left_x1 - left_x0);
1019 y = left_y0 + t * (left_y1 - left_y0);
1023 /* Make sure intersection point is within bounds of right seg. */
1024 if (y < right_seg->y0)
1026 x = right_seg->x[0];
1029 else if (y > right_seg->y1)
1031 x = right_seg->x[1];
1034 else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1035 x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1036 else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1037 x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1039 if (y == left_seg->y0)
1041 if (y != right_seg->y0)
1044 art_dprint ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n",
1045 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1047 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1048 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1049 art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1054 /* Intersection takes place at current scan line; process
1055 immediately rather than queueing intersection point into
1057 ArtActiveSeg *winner, *loser;
1059 /* Choose "most vertical" segement */
1060 if (left_seg->a > right_seg->a)
1071 loser->x[0] = winner->x[0];
1072 loser->horiz_x = loser->x[0];
1073 loser->horiz_delta_wind += loser->delta_wind;
1074 winner->horiz_delta_wind -= loser->delta_wind;
1076 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1080 else if (y == right_seg->y0)
1083 art_dprint ("*** art_svp_intersect_test_cross: intersection (%g, %g) matches latter y0 of %lx, %lx\n",
1084 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1086 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1087 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1088 art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1094 art_dprint ("Inserting (%g, %g) into %lx, %lx\n",
1095 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1097 /* Insert the intersection point into both segments. */
1098 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1099 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1100 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1101 art_svp_intersect_add_point (ctx, x, y, left_seg->left, break_flags);
1102 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1103 art_svp_intersect_add_point (ctx, x, y, right_seg->right, break_flags);
1109 * art_svp_intersect_active_delete: Delete segment from active list.
1110 * @ctx: Intersection context.
1111 * @seg: Segment to delete.
1113 * Deletes @seg from the active list.
1115 static /* todo inline */ void
1116 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1118 ArtActiveSeg *left = seg->left, *right = seg->right;
1121 left->right = right;
1123 ctx->active_head = right;
1129 * art_svp_intersect_active_free: Free an active segment.
1130 * @seg: Segment to delete.
1134 static /* todo inline */ void
1135 art_svp_intersect_active_free (ArtActiveSeg *seg)
1137 art_free (seg->stack);
1139 art_dprint ("Freeing %lx\n", (unsigned long) seg);
1145 * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1147 * Tests @seg against its left and right neighbors for intersections.
1148 * Precondition: the line in @seg is not purely horizontal.
1151 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1154 ArtActiveSeg *left = seg, *right = seg;
1160 ArtActiveSeg *leftc;
1162 for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1163 if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1165 if (leftc != NULL &&
1166 art_svp_intersect_test_cross (ctx, leftc, left,
1169 if (left == right || right == NULL)
1170 right = left->right;
1177 else if (right != NULL && right->right != NULL)
1179 ArtActiveSeg *rightc;
1181 for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1182 if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1184 if (rightc != NULL &&
1185 art_svp_intersect_test_cross (ctx, right, rightc,
1188 if (left == right || left == NULL)
1202 * art_svp_intersect_horiz: Add horizontal line segment.
1203 * @ctx: Intersector context.
1204 * @seg: Segment on which to add horizontal line.
1205 * @x0: Old x position.
1206 * @x1: New x position.
1208 * Adds a horizontal line from @x0 to @x1, and updates the current
1209 * location of @seg to @x1.
1212 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1213 double x0, double x1)
1220 hs = art_new (ArtActiveSeg, 1);
1222 hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1223 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1225 ArtSvpWriter *swr = ctx->out;
1227 swr->add_point (swr, seg->seg_id, x0, ctx->y);
1229 hs->seg_id = seg->seg_id;
1231 hs->horiz_delta_wind = seg->delta_wind;
1234 /* Ideally, the (a, b, c) values will never be read. However, there
1235 are probably some tests remaining that don't check for _DEL
1236 before evaluating the line equation. For those, these
1237 initializations will at least prevent a UMR of the values, which
1238 can crash on some platforms. */
1243 seg->horiz_delta_wind -= seg->delta_wind;
1245 art_svp_intersect_add_horiz (ctx, hs);
1250 art_boolean first = ART_TRUE;
1252 for (left = seg->left; left != NULL; left = seg->left)
1254 int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1256 if (left->x[left_bneg] <= x1)
1258 if (left->x[left_bneg ^ 1] <= x1 &&
1259 x1 * left->a + ctx->y * left->b + left->c >= 0)
1261 if (left->y0 != ctx->y && left->y1 != ctx->y)
1263 art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1266 art_dprint ("x0=%g > x1=%g, swapping %lx, %lx\n",
1267 x0, x1, (unsigned long)left, (unsigned long)seg);
1269 art_svp_intersect_swap_active (ctx, left, seg);
1270 if (first && left->right != NULL)
1272 art_svp_intersect_test_cross (ctx, left, left->right,
1280 ArtActiveSeg *right;
1281 art_boolean first = ART_TRUE;
1283 for (right = seg->right; right != NULL; right = seg->right)
1285 int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1287 if (right->x[right_bneg ^ 1] >= x1)
1289 if (right->x[right_bneg] >= x1 &&
1290 x1 * right->a + ctx->y * right->b + right->c <= 0)
1292 if (right->y0 != ctx->y && right->y1 != ctx->y)
1294 art_svp_intersect_break (ctx, right, x1, ctx->y,
1298 art_dprint ("[right]x0=%g < x1=%g, swapping %lx, %lx\n",
1299 x0, x1, (unsigned long)seg, (unsigned long)right);
1301 art_svp_intersect_swap_active (ctx, seg, right);
1302 if (first && right->left != NULL)
1304 art_svp_intersect_test_cross (ctx, right->left, right,
1314 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1318 * art_svp_intersect_insert_line: Insert a line into the active list.
1319 * @ctx: Intersector context.
1320 * @seg: Segment containing line to insert.
1322 * Inserts the line into the intersector context, taking care of any
1323 * intersections, and adding the appropriate horizontal points to the
1327 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1329 if (seg->y1 == seg->y0)
1332 art_dprint ("art_svp_intersect_insert_line: %lx is horizontal\n",
1333 (unsigned long)seg);
1335 art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1339 art_svp_intersect_insert_cross (ctx, seg);
1340 art_svp_intersect_add_horiz (ctx, seg);
1345 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1348 int n_stack = --seg->n_stack;
1349 seg->x[1] = seg->stack[n_stack - 1].x;
1350 seg->y1 = seg->stack[n_stack - 1].y;
1351 seg->x[0] = seg->stack[n_stack].x;
1352 seg->y0 = seg->stack[n_stack].y;
1353 seg->horiz_x = seg->x[0];
1354 art_svp_intersect_insert_line (ctx, seg);
1358 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1359 ArtPriPoint *pri_pt)
1361 const ArtSVPSeg *in_seg = seg->in_seg;
1362 int in_curs = seg->in_curs;
1363 ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1366 swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1367 if (in_curs + 1 == in_seg->n_points)
1369 ArtActiveSeg *left = seg->left, *right = seg->right;
1373 swr->close_segment (swr, seg->seg_id);
1374 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1376 seg->flags |= ART_ACTIVE_FLAGS_DEL;
1377 art_svp_intersect_add_horiz (ctx, seg);
1378 art_svp_intersect_active_delete (ctx, seg);
1379 if (left != NULL && right != NULL)
1380 art_svp_intersect_test_cross (ctx, left, right,
1381 ART_BREAK_LEFT | ART_BREAK_RIGHT);
1386 seg->horiz_x = seg->x[1];
1388 art_svp_intersect_setup_seg (seg, pri_pt);
1389 art_pri_insert (ctx->pq, pri_pt);
1390 art_svp_intersect_insert_line (ctx, seg);
1395 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1397 ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1400 ArtActiveSeg *beg_range;
1401 ArtActiveSeg *last = NULL;
1402 ArtActiveSeg *left, *right;
1403 ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1406 seg->in_seg = in_seg;
1409 seg->n_stack_max = 4;
1410 seg->stack = art_new (ArtPoint, seg->n_stack_max);
1412 seg->horiz_delta_wind = 0;
1416 pri_pt->user_data = seg;
1417 art_svp_intersect_setup_seg (seg, pri_pt);
1418 art_pri_insert (ctx->pq, pri_pt);
1420 /* Find insertion place for new segment */
1421 /* This is currently a left-to-right scan, but should be replaced
1422 with a binary search as soon as it's validated. */
1424 x0 = in_seg->points[0].x;
1425 y0 = in_seg->points[0].y;
1427 for (test = ctx->active_head; test != NULL; test = test->right)
1430 int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1432 if (x0 < test->x[test_bneg])
1434 if (x0 < test->x[test_bneg ^ 1])
1436 d = x0 * test->a + y0 * test->b + test->c;
1443 left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1447 right = ctx->active_head;
1448 ctx->active_head = seg;
1452 right = left->right;
1459 seg->delta_wind = in_seg->dir ? 1 : -1;
1462 art_svp_intersect_insert_line (ctx, seg);
1467 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1470 /* At this point, we seem to be getting false positives, so it's
1471 turned off for now. */
1474 int winding_number = 0;
1476 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1478 /* Check winding number consistency. */
1479 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1481 if (winding_number != seg->wind_left)
1482 art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %lx has wind_left of %d, expected %d\n",
1483 (unsigned long) seg, seg->wind_left, winding_number);
1484 winding_number = seg->wind_left + seg->delta_wind;
1487 if (winding_number != 0)
1488 art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1495 * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1496 * @ctx: Intersection context.
1498 * The main function of the horizontal commit is to output new
1499 * points to the output writer.
1501 * This "commit" pass is also where winding numbers are assigned,
1502 * because doing it here provides much greater tolerance for inputs
1503 * which are not in strict SVP order.
1505 * Each cluster in the horiz_list contains both segments that are in
1506 * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1507 * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1508 * need to deal with both.
1511 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1514 int winding_number = 0; /* initialization just to avoid warning */
1516 double last_x = 0; /* initialization just to avoid warning */
1519 art_dprint ("art_svp_intersect_horiz_commit: y=%g\n", ctx->y);
1520 for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1521 art_dprint (" %lx: %g %+d\n",
1522 (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind);
1525 /* Output points to svp writer. */
1526 for (seg = ctx->horiz_first; seg != NULL;)
1528 /* Find a cluster with common horiz_x, */
1530 double x = seg->horiz_x;
1532 /* Generate any horizontal segments. */
1533 if (horiz_wind != 0)
1535 ArtSvpWriter *swr = ctx->out;
1538 seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1540 swr->add_point (swr, seg_id, x, ctx->y);
1541 swr->close_segment (swr, seg_id);
1544 /* Find first active segment in cluster. */
1546 for (curs = seg; curs != NULL && curs->horiz_x == x;
1547 curs = curs->horiz_right)
1548 if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1551 if (curs != NULL && curs->horiz_x == x)
1553 /* There exists at least one active segment in this cluster. */
1555 /* Find beginning of cluster. */
1556 for (; curs->left != NULL; curs = curs->left)
1557 if (curs->left->horiz_x != x)
1560 if (curs->left != NULL)
1561 winding_number = curs->left->wind_left + curs->left->delta_wind;
1568 art_dprint (" curs %lx: winding_number = %d += %d\n",
1569 (unsigned long)curs, winding_number, curs->delta_wind);
1571 if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1572 curs->wind_left != winding_number)
1574 ArtSvpWriter *swr = ctx->out;
1576 if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1578 swr->add_point (swr, curs->seg_id,
1579 curs->horiz_x, ctx->y);
1580 swr->close_segment (swr, curs->seg_id);
1583 curs->seg_id = swr->add_segment (swr, winding_number,
1586 curs->flags |= ART_ACTIVE_FLAGS_OUT;
1588 curs->wind_left = winding_number;
1589 winding_number += curs->delta_wind;
1592 while (curs != NULL && curs->horiz_x == x);
1595 /* Skip past cluster. */
1598 ArtActiveSeg *next = seg->horiz_right;
1600 seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1601 horiz_wind += seg->horiz_delta_wind;
1602 seg->horiz_delta_wind = 0;
1603 if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1605 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1607 ArtSvpWriter *swr = ctx->out;
1608 swr->close_segment (swr, seg->seg_id);
1610 art_svp_intersect_active_free (seg);
1614 while (seg != NULL && seg->horiz_x == x);
1618 ctx->horiz_first = NULL;
1619 ctx->horiz_last = NULL;
1621 art_svp_intersect_sanitycheck_winding (ctx);
1627 art_svp_intersect_print_active (ArtIntersectCtx *ctx)
1631 art_dprint ("Active list (y = %g):\n", ctx->y);
1632 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1634 art_dprint (" %lx: (%g, %g)-(%g, %g), (a, b, c) = (%g, %g, %g)\n",
1636 seg->x[0], seg->y0, seg->x[1], seg->y1,
1637 seg->a, seg->b, seg->c);
1644 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx)
1647 ArtActiveSeg *last = NULL;
1650 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1652 if (seg->left != last)
1654 art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n",
1655 (unsigned long)last, (unsigned long)seg->left);
1659 /* pairwise compare with previous seg */
1661 /* First the top. */
1662 if (last->y0 < seg->y0)
1669 /* Then the bottom. */
1670 if (last->y1 < seg->y1)
1673 seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1674 last->y1 == seg->y0))
1676 d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1677 if (d >= -EPSILON_A)
1678 art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n",
1679 last->x[1], last->y1, (unsigned long) last,
1680 (unsigned long) seg, d);
1683 else if (last->y1 > seg->y1)
1687 last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1688 seg->y1 == last->y0))
1690 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1692 art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n",
1693 seg->x[1], seg->y1, (unsigned long) seg,
1694 (unsigned long) last, d);
1699 if (last->x[1] > seg->x[1])
1700 art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n",
1701 last->x[1], last->y1, (unsigned long)last,
1702 seg->x[1], seg->y1, (unsigned long)seg);
1711 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
1713 ArtIntersectCtx *ctx;
1715 ArtPriPoint *first_point;
1720 if (in->n_segs == 0)
1723 ctx = art_new (ArtIntersectCtx, 1);
1726 pq = art_pri_new ();
1729 ctx->active_head = NULL;
1731 ctx->horiz_first = NULL;
1732 ctx->horiz_last = NULL;
1735 first_point = art_new (ArtPriPoint, 1);
1736 first_point->x = in->segs[0].points[0].x;
1737 first_point->y = in->segs[0].points[0].y;
1738 first_point->user_data = NULL;
1739 ctx->y = first_point->y;
1740 art_pri_insert (pq, first_point);
1742 while (!art_pri_empty (pq))
1744 ArtPriPoint *pri_point = art_pri_choose (pq);
1745 ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
1748 art_dprint ("\nIntersector step %d\n", count++);
1749 art_svp_intersect_print_active (ctx);
1750 art_dprint ("priq choose (%g, %g) %lx\n", pri_point->x, pri_point->y,
1751 (unsigned long)pri_point->user_data);
1754 art_svp_intersect_sanitycheck(ctx);
1757 if (ctx->y != pri_point->y)
1759 art_svp_intersect_horiz_commit (ctx);
1760 ctx->y = pri_point->y;
1765 /* Insert new segment from input */
1766 const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++];
1767 art_svp_intersect_add_seg (ctx, in_seg);
1768 if (ctx->in_curs < in->n_segs)
1770 const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
1771 pri_point->x = next_seg->points[0].x;
1772 pri_point->y = next_seg->points[0].y;
1773 /* user_data is already NULL */
1774 art_pri_insert (pq, pri_point);
1777 art_free (pri_point);
1781 int n_stack = seg->n_stack;
1785 art_svp_intersect_process_intersection (ctx, seg);
1786 art_free (pri_point);
1790 art_svp_intersect_advance_cursor (ctx, seg, pri_point);
1795 art_svp_intersect_horiz_commit (ctx);
1801 #endif /* not TEST_PRIQ */