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
27 #include "art_svp_intersect.h"
29 #include <math.h> /* for sqrt */
31 /* Sanitychecking verifies the main invariant on every priority queue
32 point. Do not use in production, as it slows things down way too
36 /* This can be used in production, to prevent hangs. Eventually, it
37 should not be necessary. */
38 #define CHEAP_SANITYCHECK
42 #define ABORT_ON_ERROR
46 /* A priority queue - perhaps move to a separate file if it becomes
47 needed somewhere else */
49 #define ART_PRIQ_USE_HEAP
51 typedef struct _ArtPriQ ArtPriQ;
52 typedef struct _ArtPriPoint ArtPriPoint;
69 ArtPriQ *result = art_new (ArtPriQ, 1);
72 result->n_items_max = 16;
73 result->items = art_new (ArtPriPoint *, result->n_items_max);
78 art_pri_free (ArtPriQ *pq)
85 art_pri_empty (ArtPriQ *pq)
87 return pq->n_items == 0;
90 /* This heap implementation is based on Vasek Chvatal's course notes:
91 http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
94 art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing)
96 ArtPriPoint **items = pq->items;
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)))
104 items[vacant] = items[parent];
106 parent = (vacant - 1) >> 1;
109 items[vacant] = missing;
113 art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
116 art_dprint("insert into pq %08x: %.16f,%.16f %08x\n", pq, point->x, point->y, point->user_data);
118 if (pq->n_items == pq->n_items_max)
119 art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
121 art_pri_bubble_up (pq, pq->n_items++, point);
125 art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
127 ArtPriPoint **items = pq->items;
128 int vacant = 0, child = 2;
133 if (items[child - 1]->y < items[child]->y ||
134 (items[child - 1]->y == items[child]->y &&
135 items[child - 1]->x < items[child]->x))
137 items[vacant] = items[child];
139 child = (vacant + 1) << 1;
143 items[vacant] = items[n - 1];
147 art_pri_bubble_up (pq, vacant, missing);
151 art_pri_choose (ArtPriQ *pq)
153 ArtPriPoint *result = pq->items[0];
155 art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
159 static const ArtSVP* current_svp = 0;
163 #ifdef ABORT_ON_ERROR
165 fprintf(stderr, "internal error: no current polygon\n");
168 const ArtSVP*svp = current_svp;
169 FILE*fi = fopen("svp.ps", "wb");
171 fprintf(fi, "%% begin\n");
172 for (i = 0; i < svp->n_segs; i++)
174 fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
175 for (j = 0; j < svp->segs[i].n_points; j++)
177 fprintf(fi, "%.32f %.32f %s\n",
178 svp->segs[i].points[j].x,
179 svp->segs[i].points[j].y,
180 j ? "lineto" : "moveto");
182 fprintf(fi, "stroke\n");
184 fprintf(fi, "showpage\n");
187 fprintf(stderr, "There was an error during polygon processing.\n");
188 fprintf(stderr, "I saved a debug file, called svp.ps, to the current directory.\n");
189 fprintf(stderr, "Please help making this tool more stable by mailing\n");
190 fprintf(stderr, "this file to debug@swftools.org. Thank you!\n");
195 /* A virtual class for an "svp writer". A client of this object creates an
196 SVP by repeatedly calling "add segment" and "add point" methods on it.
199 typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
201 /* An implementation of the svp writer virtual class that applies the
204 struct _ArtSvpWriterRewind {
213 art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left,
214 int delta_wind, double x, double y)
216 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
219 art_boolean left_filled, right_filled;
220 int wind_right = wind_left + delta_wind;
222 const int init_n_points_max = 4;
226 case ART_WIND_RULE_NONZERO:
227 left_filled = (wind_left != 0);
228 right_filled = (wind_right != 0);
230 case ART_WIND_RULE_INTERSECT:
231 left_filled = (wind_left > 1);
232 right_filled = (wind_right > 1);
234 case ART_WIND_RULE_ODDEVEN:
235 left_filled = (wind_left & 1);
236 right_filled = (wind_right & 1);
238 case ART_WIND_RULE_POSITIVE:
239 left_filled = (wind_left > 0);
240 right_filled = (wind_right > 0);
243 art_die ("Unknown wind rule %d\n", swr->rule);
247 art_dprint("New svp segment %d: %.32f %.32f left_filled=%d, right_filled=%d\n", swr->svp->n_segs, x, y, left_filled, right_filled);
250 if (left_filled == right_filled)
252 /* discard segment now */
254 art_dprint (" discarding segment: %d += %d (%.16f, %.16f)\n",
255 wind_left, delta_wind, x, y);
261 seg_num = svp->n_segs++;
262 if (swr->n_segs_max == seg_num)
264 swr->n_segs_max += 10;
265 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
266 (swr->n_segs_max - 1) *
269 swr->n_points_max = art_renew (swr->n_points_max, int,
272 seg = &svp->segs[seg_num];
274 seg->dir = right_filled;
275 swr->n_points_max[seg_num] = init_n_points_max;
280 seg->points = art_new (ArtPoint, init_n_points_max);
281 seg->points[0].x = x;
282 seg->points[0].y = y;
284 art_dprint ("swr add_segment: %d += %d (%.16f, %.16f) --> %d (%s)\n",
285 wind_left, delta_wind, x, y, seg_num,
286 seg->dir ? "filled" : "non-filled");
292 art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id,
296 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
301 art_dprint ("swr add_point: %d (%.16f, %.16f)\n", seg_id, x, y);
304 /* omitted segment */
307 seg = &swr->svp->segs[seg_id];
310 seg->points[seg->n_points-1].x == x &&
311 seg->points[seg->n_points-1].y == y) {
312 //art_warn("duplicate point %.16f,%.16f in segment %08x\n",
317 n_points = seg->n_points++;
318 if (swr->n_points_max[seg_id] == n_points)
319 art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
321 if(0 && n_points>=2) {
322 double dx1 = seg->points[n_points-1].x - seg->points[n_points-2].x;
323 double dy1 = seg->points[n_points-1].y - seg->points[n_points-2].y;
324 double dx2 = x - seg->points[n_points-2].x;
325 double dy2 = y - seg->points[n_points-2].y;
326 if(fabs(dx1*dy2 - dx2*dy1) < 1e-10) {
328 n_points--; // remove previous point pointing in the same direction
330 //art_warn("redundant point %.16f,%.16f in segment %08x\n",
331 // seg->points[n_points-1].x, seg->points[n_points-1].y,
336 if(n_points && seg->points[n_points-1].y > y) {
337 art_warn("non-increasing segment (%.16f -> %.16f)\n", seg->points[n_points-1].y, y);
341 seg->points[n_points].x = x;
342 seg->points[n_points].y = y;
343 if (x < seg->bbox.x0)
345 if (x > seg->bbox.x1)
351 art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id)
353 /* Not needed for this simple implementation. A potential future
354 optimization is to merge segments that can be merged safely. */
355 #ifdef CHEAP_SANITYCHECK
356 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
361 seg = &swr->svp->segs[seg_id];
362 if (seg->n_points < 2)
363 art_warn ("*** closing segment %d with only %d point%s\n",
364 seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
369 art_dprint ("swr close_segment: %d\n", seg_id);
374 art_svp_writer_rewind_reap (ArtSvpWriter *self)
376 ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
377 ArtSVP *result = swr->svp;
379 art_free (swr->n_points_max);
385 art_svp_writer_rewind_new (ArtWindRule rule)
387 ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
389 result->super.add_segment = art_svp_writer_rewind_add_segment;
390 result->super.add_point = art_svp_writer_rewind_add_point;
391 result->super.close_segment = art_svp_writer_rewind_close_segment;
394 result->n_segs_max = 16;
395 result->svp = (ArtSVP*)art_alloc (sizeof(ArtSVP) +
396 (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
397 result->svp->n_segs = 0;
398 result->n_points_max = (int*)art_new (int, result->n_segs_max);
400 return &result->super;
403 /* Now, data structures for the active list.
412 -------------+--------------------
420 typedef struct _ArtActiveSeg ArtActiveSeg;
422 /* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
423 x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
424 #define ART_ACTIVE_FLAGS_BNEG 1
426 /* This flag is set if the segment has been inserted into the active
428 #define ART_ACTIVE_FLAGS_IN_ACTIVE 2
430 /* This flag is set when the segment is to be deleted in the
431 horiz commit process. */
432 #define ART_ACTIVE_FLAGS_DEL 4
434 /* This flag is set if the seg_id is a valid output segment. */
435 #define ART_ACTIVE_FLAGS_OUT 8
437 /* This flag is set if the segment is in the horiz list. */
438 #define ART_ACTIVE_FLAGS_IN_HORIZ 16
440 struct _ArtActiveSeg {
442 int wind_left, delta_wind;
443 ArtActiveSeg *left, *right; /* doubly linked list structure */
445 const ArtSVPSeg *in_seg;
450 double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
453 /* bottom point and intersection point stack */
458 /* horiz commit list */
459 ArtActiveSeg *horiz_left, *horiz_right;
461 int horiz_delta_wind;
465 typedef struct _ArtIntersectCtx ArtIntersectCtx;
467 struct _ArtIntersectCtx {
473 ArtActiveSeg *active_head;
476 ArtActiveSeg *horiz_first;
477 ArtActiveSeg *horiz_last;
479 /* segment index of next input segment to be added to pri q */
483 #define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
486 * art_svp_intersect_setup_seg: Set up an active segment from input segment.
487 * @seg: Active segment.
488 * @pri_pt: Priority queue point to initialize.
490 * Sets the x[], a, b, c, flags, and stack fields according to the
491 * line from the current cursor value. Sets the priority queue point
492 * to the bottom point of this line. Also advances the input segment
496 art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
498 const ArtSVPSeg *in_seg = seg->in_seg;
500 double x0, y0, x1, y1;
505 in_curs = seg->in_curs++;
506 //} while(in_seg->points[in_curs].x == in_seg->points[in_curs + 1].x &&
507 // in_seg->points[in_curs].y == in_seg->points[in_curs + 1].y &&
508 // in_curs < in_seg->n_points-1
511 x0 = in_seg->points[in_curs].x;
512 y0 = in_seg->points[in_curs].y;
513 x1 = in_seg->points[in_curs + 1].x;
514 y1 = in_seg->points[in_curs + 1].y;
519 r2 = dx * dx + dy * dy;
521 //art_warn("segment %08x has zero length\n", seg);
523 s = r2 == 0 ? 1 : 1 / sqrt (r2);
525 seg->b = b = -dx * s;
526 seg->c = -(a * x0 + b * y0);
527 seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
533 seg->stack[0].x = x1;
534 seg->stack[0].y = y1;
537 art_warn("art_svp_intersect.c: bad input polygon %08x, contains decreasing y values\n", seg->in_seg);
541 art_dprint("segment %08x (top: %.16f,%.16f) starts with endpoint at %.16f,%.16f\n", seg,
548 * art_svp_intersect_add_horiz: Add point to horizontal list.
549 * @ctx: Intersector context.
550 * @seg: Segment with point to insert into horizontal list.
552 * Inserts @seg into horizontal list, keeping it in ascending horiz_x
555 * Note: the horiz_commit routine processes "clusters" of segs in the
556 * horiz list, all sharing the same horiz_x value. The cluster is
557 * processed in active list order, rather than horiz list order. Thus,
558 * the order of segs in the horiz list sharing the same horiz_x
559 * _should_ be irrelevant. Even so, we use b as a secondary sorting key,
560 * as a "belt and suspenders" defensive coding tactic.
563 art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
565 ArtActiveSeg **pp = &ctx->horiz_last;
567 ArtActiveSeg *place_right = NULL;
569 #ifdef CHEAP_SANITYCHECK
570 if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
572 double dx = seg->x[1] - seg->x[0];
573 double dy = seg->y1 - seg->y0;
574 double len = sqrt(dx*dx+dy*dy);
575 art_warn("attempt to put segment %08x %.16f,%.16f (len:%.16f) in horiz list twice\n", seg, seg->x[0], seg->y0, len);
578 seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
582 art_dprint ("add_horiz %08x, x = %.16f\n", (unsigned long) seg, seg->horiz_x);
584 for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
585 (place->horiz_x == seg->horiz_x &&
590 pp = &place->horiz_left;
593 seg->horiz_left = place;
594 seg->horiz_right = place_right;
597 ctx->horiz_first = seg;
599 place->horiz_right = seg;
602 art_dprint("horiz_list:\n");
603 ArtActiveSeg*s = ctx->horiz_first;
605 art_dprint(" %08x x=%.16f wind_left=%d delta_wind=%d horiz_delta_wind=%d\n", s, s->horiz_x,
606 s->wind_left, s->delta_wind, s->horiz_delta_wind);
613 art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
617 int n_stack = seg->n_stack;
619 if (n_stack == seg->n_stack_max)
620 art_expand (seg->stack, ArtPoint, seg->n_stack_max);
623 seg->stack[n_stack].x = x;
624 seg->stack[n_stack].y = y;
629 art_dprint("art_svp_intersect_push_pt %08x |top %.16f,%.16f\n", seg, seg->x[0], seg->y0);
630 for(t=seg->n_stack-1;t>=0;t--) {
631 if(t!=seg->n_stack-1)
632 art_dprint("art_svp_intersect_push_pt %08x |pt %.16f,%.16f\n", seg, seg->stack[t].x, seg->stack[t].y);
634 art_dprint("art_svp_intersect_push_pt %08x |new %.16f,%.16f\n", seg, seg->stack[t].x, seg->stack[t].y);
638 art_dprint("(shortening segment %08x to %.16f,%.16f)\n", seg, x, y);
641 if(seg->stack[seg->n_stack-1].y == seg->y0) {
642 art_warn("duplicate y coordinate (=y0) in point stack\n");
646 if(seg->stack[seg->n_stack-2].y < seg->stack[seg->n_stack-1].y) {
647 art_warn("bad shortening- segment got *longer*\n");
656 pri_pt = art_new (ArtPriPoint, 1);
659 pri_pt->user_data = seg;
660 art_pri_insert (ctx->pq, pri_pt);
663 #define ART_BREAK_LEFT 1
664 #define ART_BREAK_RIGHT 2
667 * art_svp_intersect_break: Break an active segment.
669 * Note: y must be greater than the top point's y, and less than
672 * Return value: x coordinate of break point.
675 art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
676 double x_ref, double y, int break_flags)
678 double x0, y0, x1, y1;
679 const ArtSVPSeg *in_seg = seg->in_seg;
680 int in_curs = seg->in_curs;
683 x0 = in_seg->points[in_curs - 1].x;
684 y0 = in_seg->points[in_curs - 1].y;
685 x1 = in_seg->points[in_curs].x;
686 y1 = in_seg->points[in_curs].y;
688 x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
690 //printf("%d %.16f %.16f %d\n", break_flags&ART_BREAK_LEFT, x, x_ref, x > x_ref);
691 //printf("%d %.16f %.16f %d\n", break_flags&ART_BREAK_RIGHT, x, x_ref, x < x_ref);
693 if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
694 (break_flags == ART_BREAK_RIGHT && x < x_ref))
697 art_dprint ("art_svp_intersect_break %08x: limiting x to %.16f, was %.16f, %s\n", seg,
698 x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right");
700 //x = x_ref; //used to be *within* the VERBOSE comment
703 if(y < y0 || y > y1) {
704 art_warn("!! bad break %.16f of %.16f-%.16f\n", y, y0, y1);
708 /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
709 arithmetic, but it might be worthwhile to check just in case. */
711 /* TODO: should we check seg instead of in_seg ? */
714 art_warn("bad x value %.16f in intersect_break: not between %.16f and %.16f\n", x, x0, x1);
718 art_warn("bad x value %.16f in intersect_break: not between %.16f and %.16f\n", x, x1, x0);
724 art_svp_intersect_push_pt (ctx, seg, x, y);
728 art_warn("intersect_break at a y above the current scanline (%.16f < %.16f)", y, ctx->y);
733 art_svp_intersect_add_horiz (ctx, seg);
740 * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
741 * @ctx: Intersector context.
742 * @x: X coordinate of point to add.
743 * @y: Y coordinate of point to add.
744 * @seg: "nearby" segment, or NULL if leftmost.
746 * Return value: Segment immediately to the left of the new point, or
747 * NULL if the new point is leftmost.
749 static ArtActiveSeg *
750 art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
751 ArtActiveSeg *seg, int break_flags)
753 ArtActiveSeg *left, *right;
754 double x_min = x, x_max = x;
755 art_boolean left_live, right_live;
758 ArtActiveSeg *test, *result = NULL;
763 right = ctx->active_head;
766 left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
767 right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
772 dd = seg->a*x + seg->b*y + seg->c;
773 art_dprint("add_point seg=%08x %f,%f%s%s (left=%08x, right=%08x) d=%f\n", seg, x, y,
774 break_flags&ART_BREAK_LEFT?" BREAK_LEFT":"",
775 break_flags&ART_BREAK_LEFT?" BREAK_RIGHT":"",
776 seg?seg->left:0, seg?seg->right:0, dd);
778 /* add_point relies on the fact that the active list is ascending-
779 no checks are done for lines which are not in strict order.
781 a point position (x,y) is tested against left (if break_flags&ART_BREAK_LEFT)
782 and right (if break_flags&ART_BREAK_RIGHT) neighboring segments which are
783 within EPSILON_A distance of the point. If they are, they are split at y.
784 For ART_BREAK_LEFT, the "intersection point" on the line (which is to the left
785 of (x,y) will never be to the right of "our" (x,y)- new_x will be shifted
786 by _break to make sure of that. (Which should only happen for horizontal
787 line segments) Likewise for ART_BREAK_RIGHT.
789 The horizontal area around (x,y) (x_min, x_max) will be extended into the
790 break direction for every cut we make.
793 //new_x = art_svp_intersect_break (ctx, left, x_min, y, ART_BREAK_LEFT);
795 while (left_live || right_live)
798 art_dprint(" left: %08x (%d) right: %08x (%d)\n", left, left_live, right, right_live);
802 if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
803 /* It may be that one of these conjuncts turns out to be always
804 true. We test both anyway, to be defensive. */
805 y != left->y0 && y < left->y1)
807 d = x_min * left->a + y * left->b + left->c;
810 new_x = art_svp_intersect_break (ctx, left, x_min, y,
813 art_dprint("break %08x at x<=%.16f,y=%.16f, new_x=%f\n", left, x_min, y, new_x);
818 right_live = (right != NULL);
820 else if (new_x < x_min)
823 left_live = (left != NULL);
826 left_live = ART_FALSE;
829 left_live = ART_FALSE;
833 if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
834 /* It may be that one of these conjuncts turns out to be always
835 true. We test both anyway, to be defensive. */
836 y != right->y0 && y < right->y1)
838 d = x_max * right->a + y * right->b + right->c;
841 new_x = art_svp_intersect_break (ctx, right, x_max, y,
844 art_dprint("break %08x at x>=%.16f,y=%.16f, new_x=%f\n", right, x_max, y, new_x);
849 left_live = (left != NULL);
851 else if (new_x >= x_max)
853 right = right->right;
854 right_live = (right != NULL);
857 right_live = ART_FALSE;
860 right_live = ART_FALSE;
864 /* Ascending order is guaranteed by break_flags. Thus, we don't need
865 to actually fix up non-ascending pairs. */
867 /* Now, (left, right) defines an interval of segments broken. Sort
868 into ascending x order. (find segment to the left of the new point) */
869 test = left == NULL ? ctx->active_head : left->right;
871 if (test != NULL && test != right)
875 else if(y == test->y1)
878 art_warn ("internal error in add_point: y=%.16f is between %.16f and %.16f\n", y, test->y0, test->y1);
891 /* FIXME the following code doesn't do anything (?) */
895 art_warn ("art_svp_intersect_add_point: non-ascending x\n");
904 art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
905 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
907 if((left_seg && left_seg->right != right_seg) ||
908 (right_seg && right_seg->left != left_seg)) {
909 art_warn("error: active list in disarray\n");
913 right_seg->left = left_seg->left;
914 if (right_seg->left != NULL)
915 right_seg->left->right = right_seg;
917 ctx->active_head = right_seg;
918 left_seg->right = right_seg->right;
919 if (left_seg->right != NULL)
920 left_seg->right->left = left_seg;
921 left_seg->left = right_seg;
922 right_seg->right = left_seg;
925 volatile char add0 = 0;
926 static double double_precision(double x)
928 /* make sure x has exactly 11 bits exponent and 52 bit mantissa-
929 there is probably a more elegant (or faster) way to trick the compiler
930 into doing this, but this works for now. */
933 xx[0]+=add0; xx[1]+=add0; xx[2]+=add0; xx[3]+=add0;
934 xx[4]+=add0; xx[5]+=add0; xx[6]+=add0; xx[7]+=add0;
939 * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
940 * @ctx: Intersector context.
941 * @left_seg: Left segment of the pair.
942 * @right_seg: Right segment of the pair.
943 * @break_flags: Flags indicating whether to break neighbors.
945 * Tests crossing of @left_seg and @right_seg. If there is a crossing,
946 * inserts the intersection point into both segments.
948 * Return value: True if the intersection took place at the current
949 * scan line, indicating further iteration is needed.
952 art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
953 ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
956 double left_x0, left_y0, left_x1;
957 double left_y1 = left_seg->y1;
958 double right_y1 = right_seg->y1;
961 const ArtSVPSeg *in_seg;
964 double x, y; /* intersection point */
967 static int count = 0;
969 art_dprint ("art_svp_intersect_test_cross %08x <-> %08x: count=%d\n",
970 (unsigned long)left_seg, (unsigned long)right_seg, count++);
971 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", left_seg,
972 left_seg->x[0], left_seg->y0,
973 left_seg->x[1], left_seg->y1);
974 art_dprint ("(full: %.16f,%.16f -> %.16f %.16f)\n",
975 left_seg->in_seg->points[left_seg->in_curs - 1].x, left_seg->in_seg->points[left_seg->in_curs - 1].y,
976 left_seg->in_seg->points[left_seg->in_curs].x, left_seg->in_seg->points[left_seg->in_curs].y
979 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
980 right_seg->x[0], right_seg->y0,
981 right_seg->x[1], right_seg->y1);
982 art_dprint ("(full: %.16f,%.16f -> %.16f %.16f)\n",
983 right_seg->in_seg->points[right_seg->in_curs - 1].x, right_seg->in_seg->points[right_seg->in_curs - 1].y,
984 right_seg->in_seg->points[right_seg->in_curs].x, right_seg->in_seg->points[right_seg->in_curs].y
988 #ifdef CHEAP_SANITYCHECK
989 if (right_seg->x[0] < left_seg->x[(left_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) {
990 /* notice: if we test *only* the line equation here, dd might be < 0, even though
991 right_seg was inserted to the right of left_seg correctly, due to numerical
993 double dd = right_seg->x[0] * left_seg->a + right_seg->y0 * left_seg->b + left_seg->c;
995 //art_warn ("segment %08x[%d] isn't to the left of %08x[%d]. d=%.16f\n",
996 // left_seg, left_seg->n_stack,
997 // right_seg, right_seg->n_stack,
1003 if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
1005 /* Top points of left and right segments coincide. This case
1006 feels like a bit of duplication - we may want to merge it
1007 with the cases below. However, this way, we're sure that this
1008 logic makes only localized changes. */
1010 if (left_y1 < right_y1)
1012 /* Test left (x1, y1) against right segment */
1013 double left_x1 = left_seg->x[1];
1016 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1017 left_y1 == right_seg->y0)
1019 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1023 else if (d < EPSILON_A) /* should we use zero here? */
1026 art_dprint("break %08x because of common top point, left_y1 < right_y1\n", right_seg);
1028 /* I'm unsure about the break flags here. */
1029 double right_x1 = art_svp_intersect_break (ctx, right_seg,
1033 /* this is always true due to ART_BREAK_RIGHT right_x1>=left_x1 if
1034 _break uses x_ref clipping */
1035 if (left_x1 <= right_x1) {
1040 else if (left_y1 > right_y1)
1042 /* Test right (x1, y1) against left segment */
1043 double right_x1 = right_seg->x[1];
1045 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1046 right_y1 == left_seg->y0)
1049 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1052 else if (d > -EPSILON_A) /* should we use zero here? */
1055 art_dprint("break %08x because of common top point, left_y1 > right_y1\n", left_seg);
1057 /* See above regarding break flags. */
1058 double left_x1 = art_svp_intersect_break (ctx, left_seg,
1062 /* this is always true, due to ART_BREAK_LEFT left_x1<=right_x1, if
1063 _break uses x_ref clipping
1065 if (left_x1 <= right_x1) {
1070 else /* left_y1 == right_y1 */
1072 double left_x1 = left_seg->x[1];
1073 double right_x1 = right_seg->x[1];
1076 if (left_x1 <= right_x1)
1080 //int wind_left = left_seg->wind_left;
1081 //int wind_right = right_seg->wind_left;
1082 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1083 //left_seg->wind_left = wind_right;
1084 //right_seg->wind_left = wind_left;
1089 if (left_y1 < right_y1)
1091 /* Test left (x1, y1) against right segment */
1092 double left_x1 = left_seg->x[1];
1095 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1096 left_y1 == right_seg->y0)
1099 if(left_y1 < right_seg->y0) {
1100 art_warn("left_y1 < right_seg->y0\n");
1104 /* we might want to output a warning for left_y1 < right_seg->y0 */
1106 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1109 else if (d < EPSILON_A)
1112 art_dprint("break %08x at %.16f because left_y1 < right_y1\n", right_seg, left_y1);
1113 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1114 right_seg->x[0], right_seg->y0,
1115 right_seg->x[1], right_seg->y1);
1117 double right_x1 = art_svp_intersect_break (ctx, right_seg,
1121 art_dprint("after break:\n", right_seg);
1122 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1123 right_seg->x[0], right_seg->y0,
1124 right_seg->x[1], right_seg->y1);
1126 /* this is always true if _break uses x_ref clipping */
1127 if (left_x1 <= right_x1)
1131 else if (left_y1 > right_y1)
1133 /* Test right (x1, y1) against left segment */
1134 double right_x1 = right_seg->x[1];
1136 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1137 right_y1 == left_seg->y0)
1140 if(right_y1 < left_seg->y0) {
1141 art_warn("left_y1 < right_seg->y0\n");
1145 /* we might want to output a warning for right_y1 < left_seg->y0 */
1147 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1150 else if (d > -EPSILON_A)
1153 art_dprint("break %08x because left_y1 > right_y1\n", right_seg);
1155 double left_x1 = art_svp_intersect_break (ctx, left_seg,
1158 /* this is always true if _break uses x_ref clipping */
1159 if (left_x1 <= right_x1)
1163 else /* left_y1 == right_y1 */
1165 double left_x1 = left_seg->x[1];
1166 double right_x1 = right_seg->x[1];
1168 if (left_x1 <= right_x1)
1173 /* The segments cross. Find the intersection point. */
1175 in_seg = left_seg->in_seg;
1176 in_curs = left_seg->in_curs;
1177 left_x0 = in_seg->points[in_curs - 1].x;
1178 left_y0 = in_seg->points[in_curs - 1].y;
1179 left_x1 = in_seg->points[in_curs].x;
1180 left_y1 = in_seg->points[in_curs].y;
1183 /* check for endpoint = firstpoint cases */
1184 if(left_seg->y0 == right_seg->y1 && left_seg->x[0] == right_seg->x[1])
1186 if(left_seg->y1 == right_seg->y0 && left_seg->x[1] == right_seg->x[0])
1190 d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
1191 d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1199 /* Is this division always safe? It could possibly overflow. */
1213 x = left_x0 + t * (left_x1 - left_x0);
1214 y = left_y0 + t * (left_y1 - left_y0);
1218 /* Make sure intersection point is within bounds of right seg. */
1219 if (y < right_seg->y0)
1221 x = right_seg->x[0];
1224 else if (y > right_seg->y1)
1226 x = right_seg->x[1];
1229 else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1230 x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1231 else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1232 x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1234 x = double_precision(x);
1235 y = double_precision(y);
1237 assert(ctx->y >= left_seg->y0);
1239 art_dprint ("intersect at %.16f %.16f\n", x, y);
1244 /* as we use the full segment length (not just the subsegment currently
1245 under evaluation), intersection points may be above the current scanline.
1246 As we're not able to process these anymore, we also don't need to add
1247 anything to the active list or pq.
1249 Intersection points above the current scanline happen if an
1250 intersection is handled twice- once when the line is inserted, and
1251 once when e.g. some other intersection point triggers insert_cross.
1256 if(y > left_seg->y1) {
1257 /* not within the subsegment we're currently looking into- this is not an intersection */
1261 if (y == left_seg->y0)
1263 if (y != right_seg->y0)
1266 art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches former y0 of %08x, [%08x]\n",
1267 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1269 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1270 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1271 art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1277 art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) at current scan line (y=ly0=ry0)\n",
1278 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1280 /* Intersection takes place at current scan line, with
1281 left->x0 <= x <= right->x0, left->x0 != right->x0.
1283 This happens if one of the lines is horizontal, or very near
1284 horizontal. (true horizontal lines are processed by _horiz())
1286 Process immediately rather than queueing intersection point into
1288 ArtActiveSeg *winner, *loser;
1290 /* Choose "most vertical" segement */
1291 if (left_seg->a > right_seg->a)
1302 art_dprint (" x = %.16f\n", x);
1303 art_dprint (" loser->x[0] = %.16f\n", loser->x[0]);
1304 art_dprint ("winner->x[0] = %.16f\n", winner->x[0]);
1306 loser->x[0] = winner->x[0];
1307 loser->horiz_x = loser->x[0];
1308 loser->horiz_delta_wind += loser->delta_wind;
1309 winner->horiz_delta_wind -= loser->delta_wind;
1311 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1315 else if (y == right_seg->y0)
1318 art_dprint ("*** art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches latter y0 of [%08x], %08x\n",
1319 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1320 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", left_seg,
1321 left_seg->x[0], left_seg->y0,
1322 left_seg->x[1], left_seg->y1);
1323 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1324 right_seg->x[0], right_seg->y0,
1325 right_seg->x[1], right_seg->y1);
1328 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1329 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1330 art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1336 art_dprint ("Inserting (%.16f, %.16f) into %08x, %08x\n",
1337 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1339 /* Insert the intersection point into both segments. */
1340 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1341 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1342 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1343 art_svp_intersect_add_point (ctx, x, y, left_seg->left, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1344 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1345 art_svp_intersect_add_point (ctx, x, y, right_seg->right, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1351 * art_svp_intersect_active_delete: Delete segment from active list.
1352 * @ctx: Intersection context.
1353 * @seg: Segment to delete.
1355 * Deletes @seg from the active list.
1357 static /* todo inline */ void
1358 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1360 ArtActiveSeg *left = seg->left, *right = seg->right;
1363 left->right = right;
1365 ctx->active_head = right;
1371 * art_svp_intersect_active_free: Free an active segment.
1372 * @seg: Segment to delete.
1376 static /* todo inline */ void
1377 art_svp_intersect_active_free (ArtActiveSeg *seg)
1379 art_free (seg->stack);
1381 art_dprint ("Freeing %08x\n", (unsigned long) seg);
1389 * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1391 * Tests @seg against its left and right neighbors for intersections.
1392 * Precondition: the line in @seg is not purely horizontal.
1395 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1398 ArtActiveSeg *left = seg, *right = seg;
1404 ArtActiveSeg *leftc;
1406 for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1407 if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1409 if (leftc != NULL &&
1410 art_svp_intersect_test_cross (ctx, leftc, left,
1413 if (left == right || right == NULL)
1414 right = left->right;
1421 else if (right != NULL && right->right != NULL)
1423 ArtActiveSeg *rightc;
1425 for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1426 if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1428 if (rightc != NULL &&
1429 art_svp_intersect_test_cross (ctx, right, rightc,
1432 if (left == right || left == NULL)
1446 * art_svp_intersect_horiz: Add horizontal line segment.
1447 * @ctx: Intersector context.
1448 * @seg: Segment on which to add horizontal line.
1449 * @x0: Old x position.
1450 * @x1: New x position.
1452 * Adds a horizontal line from @x0 to @x1, and updates the current
1453 * location of @seg to @x1.
1456 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1457 double x0, double x1)
1465 art_dprint("horiz: seg=%08x x0=%f x1=%f segid=%08x flags=%s delta_wind=%d\n", seg, x0, x1, seg->seg_id,
1466 seg->flags & ART_ACTIVE_FLAGS_OUT?"out":"", seg->delta_wind);
1469 hs = art_new (ArtActiveSeg, 1);
1471 hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1472 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1474 ArtSvpWriter *swr = ctx->out;
1476 swr->add_point (swr, seg->seg_id, x0, ctx->y);
1478 hs->seg_id = seg->seg_id;
1480 hs->horiz_delta_wind = seg->delta_wind;
1483 /* Ideally, the (a, b, c) values will never be read. However, there
1484 are probably some tests remaining that don't check for _DEL
1485 before evaluating the line equation. For those, these
1486 initializations will at least prevent a UMR of the values, which
1487 can crash on some platforms. */
1492 seg->horiz_delta_wind -= seg->delta_wind;
1494 art_svp_intersect_add_horiz (ctx, hs);
1499 art_boolean first = ART_TRUE;
1501 for (left = seg->left; left != NULL; left = seg->left)
1503 int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1505 if (left->x[left_bneg] <= x1)
1507 if (left->x[left_bneg ^ 1] <= x1 &&
1508 x1 * left->a + ctx->y * left->b + left->c >= 0)
1510 if (left->y0 != ctx->y && left->y1 != ctx->y)
1512 art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1515 art_dprint ("x0=%.16f > x1=%.16f, swapping %08x, %08x\n",
1516 x0, x1, (unsigned long)left, (unsigned long)seg);
1518 art_svp_intersect_swap_active (ctx, left, seg);
1519 if (first && left->right != NULL)
1521 art_svp_intersect_test_cross (ctx, left, left->right,
1529 ArtActiveSeg *right;
1530 art_boolean first = ART_TRUE;
1532 for (right = seg->right; right != NULL; right = seg->right)
1534 int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1536 if (right->x[right_bneg ^ 1] >= x1)
1538 if (right->x[right_bneg] >= x1 &&
1539 x1 * right->a + ctx->y * right->b + right->c <= 0)
1541 if (right->y0 != ctx->y && right->y1 != ctx->y)
1543 art_svp_intersect_break (ctx, right, x1, ctx->y,
1547 art_dprint ("[right]x0=%.16f < x1=%.16f, swapping %08x, %08x\n",
1548 x0, x1, (unsigned long)seg, (unsigned long)right);
1550 art_svp_intersect_swap_active (ctx, seg, right);
1551 if (first && right->left != NULL)
1553 art_svp_intersect_test_cross (ctx, right->left, right,
1563 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1567 * art_svp_intersect_insert_line: Insert a line into the active list.
1568 * @ctx: Intersector context.
1569 * @seg: Segment containing line to insert.
1571 * Inserts the line into the intersector context, taking care of any
1572 * intersections, and adding the appropriate horizontal points to the
1576 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1578 if (seg->y1 == seg->y0)
1581 art_dprint ("art_svp_intersect_insert_line(%d): %08x is horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1583 art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1588 art_dprint ("art_svp_intersect_insert_line(%d): %08x is non-horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1590 art_svp_intersect_insert_cross (ctx, seg);
1591 art_svp_intersect_add_horiz (ctx, seg);
1594 seg->flags |= ART_ACTIVE_FLAGS_IN_ACTIVE; //q
1598 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1601 int n_stack = --seg->n_stack;
1602 seg->x[1] = seg->stack[n_stack - 1].x;
1603 seg->y1 = seg->stack[n_stack - 1].y;
1604 seg->x[0] = seg->stack[n_stack].x;
1605 seg->y0 = seg->stack[n_stack].y;
1606 seg->horiz_x = seg->x[0];
1608 art_dprint("process intersection %08x (%.16f,%.16f-%.16f,%.16f)\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
1610 art_svp_intersect_insert_line (ctx, seg);
1614 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1615 ArtPriPoint *pri_pt)
1617 const ArtSVPSeg *in_seg = seg->in_seg;
1618 int in_curs = seg->in_curs;
1619 ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1622 swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1623 if (in_curs + 1 >= in_seg->n_points)
1625 ArtActiveSeg *left = seg->left, *right = seg->right;
1629 swr->close_segment (swr, seg->seg_id);
1630 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1632 seg->flags |= ART_ACTIVE_FLAGS_DEL;
1633 art_svp_intersect_add_horiz (ctx, seg);
1634 art_svp_intersect_active_delete (ctx, seg);
1635 if (left != NULL && right != NULL)
1636 art_svp_intersect_test_cross (ctx, left, right,
1637 ART_BREAK_LEFT | ART_BREAK_RIGHT);
1642 seg->horiz_x = seg->x[1];
1644 art_svp_intersect_setup_seg (seg, pri_pt);
1645 art_pri_insert (ctx->pq, pri_pt);
1646 art_svp_intersect_insert_line (ctx, seg);
1651 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1653 ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1656 ArtActiveSeg *beg_range;
1657 ArtActiveSeg *last = NULL;
1658 ArtActiveSeg *left, *right;
1659 ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1662 seg->in_seg = in_seg;
1665 seg->n_stack_max = 4;
1666 seg->stack = art_new (ArtPoint, seg->n_stack_max);
1668 seg->horiz_delta_wind = 0;
1672 pri_pt->user_data = seg;
1673 art_svp_intersect_setup_seg (seg, pri_pt);
1674 art_pri_insert (ctx->pq, pri_pt);
1676 /* Find insertion place for new segment */
1677 /* This is currently a left-to-right scan, but should be replaced
1678 with a binary search as soon as it's validated. */
1680 x0 = in_seg->points[0].x;
1681 y0 = in_seg->points[0].y;
1683 for (test = ctx->active_head; test != NULL; test = test->right)
1686 int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1688 if (x0 < test->x[test_bneg])
1690 if (x0 < test->x[test_bneg ^ 1]) {
1692 art_dprint("inserting segment %08x before %08x (x0 < xmin)\n", seg, test);
1696 d = x0 * test->a + y0 * test->b + test->c;
1699 art_dprint("inserting segment %08x before %08x (d = %.16f)\n", seg, test, d);
1704 art_dprint("segment %08x is to the right of %08x d=%.16f\n", seg, test, d);
1708 d = x0 * test->a + y0 * test->b + test->c;
1709 art_dprint("segment %08x is to the right of %08x d=%.16f (not used)\n", seg, test, d);
1715 left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1718 art_dprint("left=%08x x0=%.16f y=%.16f\n", left, x0, y0);
1724 right = ctx->active_head;
1725 ctx->active_head = seg;
1729 right = left->right;
1736 seg->delta_wind = in_seg->dir ? 1 : -1;
1739 art_svp_intersect_insert_line (ctx, seg);
1744 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1747 /* At this point, we seem to be getting false positives, so it's
1748 turned off for now. */
1751 int winding_number = 0;
1753 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1755 /* Check winding number consistency. */
1756 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1758 if (winding_number != seg->wind_left)
1759 art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %08x has wind_left of %d, expected %d\n",
1760 (unsigned long) seg, seg->wind_left, winding_number);
1761 winding_number = seg->wind_left + seg->delta_wind;
1764 if (winding_number != 0)
1765 art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1772 * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1773 * @ctx: Intersection context.
1775 * The main function of the horizontal commit is to output new
1776 * points to the output writer.
1778 * This "commit" pass is also where winding numbers are assigned,
1779 * because doing it here provides much greater tolerance for inputs
1780 * which are not in strict SVP order.
1782 * Each cluster in the horiz_list contains both segments that are in
1783 * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1784 * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1785 * need to deal with both.
1788 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1791 int winding_number = 0; /* initialization just to avoid warning */
1793 double last_x = 0; /* initialization just to avoid warning */
1796 art_dprint ("art_svp_intersect_horiz_commit: y=%.16f\n", ctx->y);
1797 for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1798 art_dprint (" %08x: %.16f %+d segid=%d\n",
1799 (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind, seg->seg_id);
1802 /* Output points to svp writer. */
1803 for (seg = ctx->horiz_first; seg != NULL;)
1805 /* Find a cluster with common horiz_x, */
1807 double x = seg->horiz_x;
1809 /* Generate any horizontal segments. */
1810 if (horiz_wind != 0)
1812 ArtSvpWriter *swr = ctx->out;
1816 art_dprint ("generate horizontal segment: y=%.16f x=%.16f-%.16f wind=%d horiz_wind=%d\n", ctx->y, last_x, x, winding_number, horiz_wind);
1818 seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1820 swr->add_point (swr, seg_id, x, ctx->y);
1821 swr->close_segment (swr, seg_id);
1824 /* Find first active segment in cluster. */
1826 for (curs = seg; curs != NULL && curs->horiz_x == x;
1827 curs = curs->horiz_right)
1828 if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1831 if (curs != NULL && curs->horiz_x == x)
1833 /* There exists at least one active segment in this cluster. */
1835 /* Find beginning of cluster. */
1836 for (; curs->left != NULL; curs = curs->left)
1837 if (curs->left->horiz_x != x)
1840 if (curs->left != NULL)
1841 winding_number = curs->left->wind_left + curs->left->delta_wind;
1848 art_dprint (" curs %08x: winding_number = %d += %d\n", (unsigned long)curs, winding_number, curs->delta_wind);
1850 if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1851 curs->wind_left != winding_number)
1853 ArtSvpWriter *swr = ctx->out;
1855 if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1857 swr->add_point (swr, curs->seg_id,
1858 curs->horiz_x, ctx->y);
1859 swr->close_segment (swr, curs->seg_id);
1862 curs->seg_id = swr->add_segment (swr, winding_number,
1865 curs->flags |= ART_ACTIVE_FLAGS_OUT;
1867 curs->wind_left = winding_number;
1868 winding_number += curs->delta_wind;
1871 while (curs != NULL && curs->horiz_x == x);
1874 /* Skip past cluster. */
1877 ArtActiveSeg *next = seg->horiz_right;
1879 seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1880 horiz_wind += seg->horiz_delta_wind;
1881 seg->horiz_delta_wind = 0;
1882 if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1884 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1886 ArtSvpWriter *swr = ctx->out;
1887 swr->close_segment (swr, seg->seg_id);
1889 art_svp_intersect_active_free (seg);
1893 while (seg != NULL && seg->horiz_x == x);
1897 ctx->horiz_first = NULL;
1898 ctx->horiz_last = NULL;
1900 art_svp_intersect_sanitycheck_winding (ctx);
1906 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx, double y)
1909 ArtActiveSeg *last = NULL;
1913 art_dprint ("Active list (y = %.16f (new: %.16f)):\n", ctx->y, y);
1916 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1919 char c1=' ',c2=' ',e1=' ';
1920 if(seg->y0 > ctx->y) c1='!';
1921 if(seg->y0 > y) c2='!';
1922 if(seg->y0 > seg->y1) e1='E';
1925 if (seg->left != last)
1927 art_warn ("*** art_svp_intersect_sanitycheck: last=%08x, seg->left=%08x\n",
1928 (unsigned long)last, (unsigned long)seg->left);
1932 /* pairwise compare with previous seg */
1934 /* First the top. */
1935 if (last->y0 < seg->y0)
1942 /* Then the bottom. */
1943 if (last->y1 < seg->y1)
1946 seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1947 last->y1 == seg->y0))
1949 d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1950 if (d >= EPSILON_A) {
1951 art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to right (d = %g)\n",
1952 last->x[1], last->y1, (unsigned long) last,
1953 (unsigned long) seg, d);
1957 art_dprint("is to the left (d=%.16f of previous x1,y1) of\n", d);
1962 art_dprint("is to the left (previous x1 < next x%d) of\n", (seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1);
1966 else if (last->y1 > seg->y1)
1970 last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1971 seg->y1 == last->y0))
1973 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1974 if (d < -EPSILON_A) {
1975 art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to left (d = %.16f)\n",
1976 seg->x[1], seg->y1, (unsigned long) seg,
1977 (unsigned long) last, d);
1981 art_dprint("is to the left (d=%.16f of next x1,y1) of\n", d);
1986 art_dprint("is to the left (next x1 > previous x%d) of\n", last->flags & ART_ACTIVE_FLAGS_BNEG);
1992 if (last->x[1] - seg->x[1] > EPSILON_A) {
1993 art_warn ("*** bottoms (%.16f, %.16f) of %08x and (%.16f, %.16f) of %08x out of order\n",
1994 last->x[1], last->y1, (unsigned long)last,
1995 seg->x[1], seg->y1, (unsigned long)seg);
1999 art_dprint("is to the left (y1s equal, previous x1 < next x1)\n");
2006 art_dprint ("%c%08x: %c%c %02d (%.16f, %.16f)-(%.16f, %.16f) ",
2008 (unsigned long)seg, c1, c2, seg->flags,
2009 seg->x[0], seg->y0, seg->x[1], seg->y1);
2021 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
2023 ArtIntersectCtx *ctx;
2025 ArtPriPoint *first_point;
2030 if (in->n_segs == 0)
2037 art_dprint("Segments: %d\n", in->n_segs);
2038 for(t=0;t<in->n_segs;t++) {
2039 const ArtSVPSeg* seg = &in->segs[t];
2040 art_dprint("Segment %08x(%d): %d points, %s, BBox: (%f,%f,%f,%f)\n",
2041 seg, t, seg->n_points, seg->dir==0?"UP ":"DOWN",
2042 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
2044 for(p=0;p<seg->n_points;p++) {
2045 ArtPoint* point = &seg->points[p];
2046 art_dprint(" (%.16f,%.16f)\n", point->x, point->y);
2052 ctx = art_new (ArtIntersectCtx, 1);
2055 pq = art_pri_new ();
2058 ctx->active_head = NULL;
2060 ctx->horiz_first = NULL;
2061 ctx->horiz_last = NULL;
2064 first_point = art_new (ArtPriPoint, 1);
2065 first_point->x = in->segs[0].points[0].x;
2066 first_point->y = in->segs[0].points[0].y;
2067 first_point->user_data = NULL;
2068 ctx->y = first_point->y;
2069 art_pri_insert (pq, first_point);
2071 double lasty = -HUGE_VAL;
2072 while (!art_pri_empty (pq))
2074 ArtPriPoint *pri_point = art_pri_choose (pq);
2075 ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
2078 art_dprint ("\nIntersector step %d (%d items in pq)\n", count++, pq->n_items);
2081 art_svp_intersect_sanitycheck(ctx, pri_point->y);
2084 art_dprint ("priq choose (%.16f, %.16f) %08x\n", pri_point->x, pri_point->y,
2085 (unsigned long)pri_point->user_data);
2087 art_dprint (" %08x = %.16f,%.16f -> %.16f %.16f\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
2090 //for(t=0;t<pq->n_items;t++) {
2091 // art_dprint("pq[%d] %.16f,%.16f %08x\n",
2095 // pq->items[t]->user_data);
2099 //art_dprint("y=%f %08x\n", pri_point->y, pri_point->user_data);
2100 if (ctx->y != pri_point->y)
2102 art_svp_intersect_horiz_commit (ctx);
2103 ctx->y = pri_point->y;
2106 if(ctx->y < lasty) {
2107 art_warn("y decreased\n");
2113 /* Insert new segment from input */
2114 const ArtSVPSeg *in_seg = 0;
2117 in_seg = &in->segs[ctx->in_curs++];
2118 if(in_seg->n_points > 1)
2120 if(ctx->in_curs == in->n_segs) {
2126 art_dprint("ignoring input segment %08x- it only contains %d point(s)\n",
2127 in_seg, in_seg->n_points);
2134 for(t=0;t<in_seg->n_points-1;t++) {
2135 if(!(in_seg->points[t].y <= in_seg->points[t+1].y)) {
2140 art_warn("bad input: contains a segment with descending y\n");
2141 for(t=0;t<in_seg->n_points;t++) {
2142 art_dprint("%d) %.16f %.16f\n", t, in_seg->points[t].x, in_seg->points[t].y);
2148 art_dprint("insert new segment from input (%.16f,%.16f) dir=%d\n", in_seg->points[0].x, in_seg->points[0].y, in_seg->dir);
2150 art_svp_intersect_add_seg (ctx, in_seg);
2151 if (ctx->in_curs < in->n_segs)
2153 const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
2154 pri_point->x = next_seg->points[0].x;
2155 pri_point->y = next_seg->points[0].y;
2156 /* user_data is already NULL */
2157 art_pri_insert (pq, pri_point);
2160 art_free(pri_point);pri_point =0;
2162 art_free(pri_point);pri_point = 0;
2167 int n_stack = seg->n_stack;
2171 art_svp_intersect_process_intersection (ctx, seg);
2172 art_free (pri_point);
2176 art_svp_intersect_advance_cursor (ctx, seg, pri_point);
2182 art_svp_intersect_horiz_commit (ctx);