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 ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
975 right_seg->x[0], right_seg->y0,
976 right_seg->x[1], right_seg->y1);
979 #ifdef CHEAP_SANITYCHECK
980 if (right_seg->x[0] < left_seg->x[(left_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) {
981 /* notice: if we test *only* the line equation here, dd might be < 0, even though
982 right_seg was inserted to the right of left_seg correctly, due to numerical
984 double dd = right_seg->x[0] * left_seg->a + right_seg->y0 * left_seg->b + left_seg->c;
986 //art_warn ("segment %08x[%d] isn't to the left of %08x[%d]. d=%.16f\n",
987 // left_seg, left_seg->n_stack,
988 // right_seg, right_seg->n_stack,
994 if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
996 /* Top points of left and right segments coincide. This case
997 feels like a bit of duplication - we may want to merge it
998 with the cases below. However, this way, we're sure that this
999 logic makes only localized changes. */
1001 if (left_y1 < right_y1)
1003 /* Test left (x1, y1) against right segment */
1004 double left_x1 = left_seg->x[1];
1007 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1008 left_y1 == right_seg->y0)
1010 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1014 else if (d < EPSILON_A) /* should we use zero here? */
1017 art_dprint("break %08x because of common top point, left_y1 < right_y1\n", right_seg);
1019 /* I'm unsure about the break flags here. */
1020 double right_x1 = art_svp_intersect_break (ctx, right_seg,
1024 /* this is always true due to ART_BREAK_RIGHT right_x1>=left_x1 if
1025 _break uses x_ref clipping */
1026 if (left_x1 <= right_x1) {
1031 else if (left_y1 > right_y1)
1033 /* Test right (x1, y1) against left segment */
1034 double right_x1 = right_seg->x[1];
1036 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1037 right_y1 == left_seg->y0)
1040 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1043 else if (d > -EPSILON_A) /* should we use zero here? */
1046 art_dprint("break %08x because of common top point, left_y1 > right_y1\n", left_seg);
1048 /* See above regarding break flags. */
1049 double left_x1 = art_svp_intersect_break (ctx, left_seg,
1053 /* this is always true, due to ART_BREAK_LEFT left_x1<=right_x1, if
1054 _break uses x_ref clipping
1056 if (left_x1 <= right_x1) {
1061 else /* left_y1 == right_y1 */
1063 double left_x1 = left_seg->x[1];
1064 double right_x1 = right_seg->x[1];
1067 if (left_x1 <= right_x1)
1071 //int wind_left = left_seg->wind_left;
1072 //int wind_right = right_seg->wind_left;
1073 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1074 //left_seg->wind_left = wind_right;
1075 //right_seg->wind_left = wind_left;
1080 if (left_y1 < right_y1)
1082 /* Test left (x1, y1) against right segment */
1083 double left_x1 = left_seg->x[1];
1086 right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
1087 left_y1 == right_seg->y0)
1090 if(left_y1 < right_seg->y0) {
1091 art_warn("left_y1 < right_seg->y0\n");
1095 /* we might want to output a warning for left_y1 < right_seg->y0 */
1097 d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1100 else if (d < EPSILON_A)
1103 art_dprint("break %08x at %.16f because left_y1 < right_y1\n", right_seg, left_y1);
1104 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1105 right_seg->x[0], right_seg->y0,
1106 right_seg->x[1], right_seg->y1);
1108 double right_x1 = art_svp_intersect_break (ctx, right_seg,
1112 art_dprint("after break:\n", right_seg);
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 /* this is always true if _break uses x_ref clipping */
1118 if (left_x1 <= right_x1)
1122 else if (left_y1 > right_y1)
1124 /* Test right (x1, y1) against left segment */
1125 double right_x1 = right_seg->x[1];
1127 if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
1128 right_y1 == left_seg->y0)
1131 if(right_y1 < left_seg->y0) {
1132 art_warn("left_y1 < right_seg->y0\n");
1136 /* we might want to output a warning for right_y1 < left_seg->y0 */
1138 d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
1141 else if (d > -EPSILON_A)
1144 art_dprint("break %08x because left_y1 > right_y1\n", right_seg);
1146 double left_x1 = art_svp_intersect_break (ctx, left_seg,
1149 /* this is always true if _break uses x_ref clipping */
1150 if (left_x1 <= right_x1)
1154 else /* left_y1 == right_y1 */
1156 double left_x1 = left_seg->x[1];
1157 double right_x1 = right_seg->x[1];
1159 if (left_x1 <= right_x1)
1164 /* The segments cross. Find the intersection point. */
1166 in_seg = left_seg->in_seg;
1167 in_curs = left_seg->in_curs;
1168 left_x0 = in_seg->points[in_curs - 1].x;
1169 left_y0 = in_seg->points[in_curs - 1].y;
1170 left_x1 = in_seg->points[in_curs].x;
1171 left_y1 = in_seg->points[in_curs].y;
1174 /* check for endpoint = firstpoint cases */
1175 if(left_seg->y0 == right_seg->y1 && left_seg->x[0] == right_seg->x[1])
1177 if(left_seg->y1 == right_seg->y0 && left_seg->x[1] == right_seg->x[0])
1181 d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
1182 d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
1190 /* Is this division always safe? It could possibly overflow. */
1204 x = left_x0 + t * (left_x1 - left_x0);
1205 y = left_y0 + t * (left_y1 - left_y0);
1209 /* Make sure intersection point is within bounds of right seg. */
1210 if (y < right_seg->y0)
1212 x = right_seg->x[0];
1215 else if (y > right_seg->y1)
1217 x = right_seg->x[1];
1220 else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
1221 x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
1222 else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
1223 x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
1225 x = double_precision(x);
1226 y = double_precision(y);
1228 assert(ctx->y >= left_seg->y0);
1230 art_dprint ("intersect at %.16f %.16f\n", x, y);
1235 /* as we use the full segment length (not just the subsegment currently
1236 under evaluation), intersection points may be above the current scanline.
1237 As we're not able to process these anymore, we also don't need to add
1238 anything to the active list or pq */
1239 if(ctx->y - y > EPSILON_A) {
1240 art_warn("ignoring previously unhandled intersection point %.16f,%.16f between segments %08x and %08x, dy = %.16f\n",
1241 x, y, left_seg, right_seg,
1249 if(y > left_seg->y1) {
1250 /* not within the subsegment we're currently looking into- this is not an intersection */
1254 if (y == left_seg->y0)
1256 if (y != right_seg->y0)
1259 art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches former y0 of %08x, [%08x]\n",
1260 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1262 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1263 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1264 art_svp_intersect_add_point (ctx, x, y, right_seg->right,
1270 art_dprint ("art_svp_intersect_test_cross: intersection (%.16f, %.16f) at current scan line (y=ly0=ry0)\n",
1271 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1273 /* Intersection takes place at current scan line, with
1274 left->x0 <= x <= right->x0, left->x0 != right->x0.
1276 This happens if one of the lines is horizontal, or very near
1277 horizontal. (true horizontal lines are processed by _horiz())
1279 Process immediately rather than queueing intersection point into
1281 ArtActiveSeg *winner, *loser;
1283 /* Choose "most vertical" segement */
1284 if (left_seg->a > right_seg->a)
1295 art_dprint (" x = %.16f\n", x);
1296 art_dprint (" loser->x[0] = %.16f\n", loser->x[0]);
1297 art_dprint ("winner->x[0] = %.16f\n", winner->x[0]);
1299 loser->x[0] = winner->x[0];
1300 loser->horiz_x = loser->x[0];
1301 loser->horiz_delta_wind += loser->delta_wind;
1302 winner->horiz_delta_wind -= loser->delta_wind;
1304 art_svp_intersect_swap_active (ctx, left_seg, right_seg);
1308 else if (y == right_seg->y0)
1311 art_dprint ("*** art_svp_intersect_test_cross: intersection (%.16f, %.16f) matches latter y0 of [%08x], %08x\n",
1312 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1313 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", left_seg,
1314 left_seg->x[0], left_seg->y0,
1315 left_seg->x[1], left_seg->y1);
1316 art_dprint ("%08x = %.16f,%.16f -> %.16f %.16f\n", right_seg,
1317 right_seg->x[0], right_seg->y0,
1318 right_seg->x[1], right_seg->y1);
1321 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1322 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1323 art_svp_intersect_add_point (ctx, x, y, left_seg->left,
1329 art_dprint ("Inserting (%.16f, %.16f) into %08x, %08x\n",
1330 x, y, (unsigned long)left_seg, (unsigned long)right_seg);
1332 /* Insert the intersection point into both segments. */
1333 art_svp_intersect_push_pt (ctx, left_seg, x, y);
1334 art_svp_intersect_push_pt (ctx, right_seg, x, y);
1335 if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
1336 art_svp_intersect_add_point (ctx, x, y, left_seg->left, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1337 if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
1338 art_svp_intersect_add_point (ctx, x, y, right_seg->right, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1344 * art_svp_intersect_active_delete: Delete segment from active list.
1345 * @ctx: Intersection context.
1346 * @seg: Segment to delete.
1348 * Deletes @seg from the active list.
1350 static /* todo inline */ void
1351 art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1353 ArtActiveSeg *left = seg->left, *right = seg->right;
1356 left->right = right;
1358 ctx->active_head = right;
1364 * art_svp_intersect_active_free: Free an active segment.
1365 * @seg: Segment to delete.
1369 static /* todo inline */ void
1370 art_svp_intersect_active_free (ArtActiveSeg *seg)
1372 art_free (seg->stack);
1374 art_dprint ("Freeing %08x\n", (unsigned long) seg);
1382 * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
1384 * Tests @seg against its left and right neighbors for intersections.
1385 * Precondition: the line in @seg is not purely horizontal.
1388 art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
1391 ArtActiveSeg *left = seg, *right = seg;
1397 ArtActiveSeg *leftc;
1399 for (leftc = left->left; leftc != NULL; leftc = leftc->left)
1400 if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
1402 if (leftc != NULL &&
1403 art_svp_intersect_test_cross (ctx, leftc, left,
1406 if (left == right || right == NULL)
1407 right = left->right;
1414 else if (right != NULL && right->right != NULL)
1416 ArtActiveSeg *rightc;
1418 for (rightc = right->right; rightc != NULL; rightc = rightc->right)
1419 if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
1421 if (rightc != NULL &&
1422 art_svp_intersect_test_cross (ctx, right, rightc,
1425 if (left == right || left == NULL)
1439 * art_svp_intersect_horiz: Add horizontal line segment.
1440 * @ctx: Intersector context.
1441 * @seg: Segment on which to add horizontal line.
1442 * @x0: Old x position.
1443 * @x1: New x position.
1445 * Adds a horizontal line from @x0 to @x1, and updates the current
1446 * location of @seg to @x1.
1449 art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1450 double x0, double x1)
1458 art_dprint("horiz: seg=%08x x0=%f x1=%f segid=%08x flags=%s delta_wind=%d\n", seg, x0, x1, seg->seg_id,
1459 seg->flags & ART_ACTIVE_FLAGS_OUT?"out":"", seg->delta_wind);
1462 hs = art_new (ArtActiveSeg, 1);
1464 hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
1465 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1467 ArtSvpWriter *swr = ctx->out;
1469 swr->add_point (swr, seg->seg_id, x0, ctx->y);
1471 hs->seg_id = seg->seg_id;
1473 hs->horiz_delta_wind = seg->delta_wind;
1476 /* Ideally, the (a, b, c) values will never be read. However, there
1477 are probably some tests remaining that don't check for _DEL
1478 before evaluating the line equation. For those, these
1479 initializations will at least prevent a UMR of the values, which
1480 can crash on some platforms. */
1485 seg->horiz_delta_wind -= seg->delta_wind;
1487 art_svp_intersect_add_horiz (ctx, hs);
1492 art_boolean first = ART_TRUE;
1494 for (left = seg->left; left != NULL; left = seg->left)
1496 int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
1498 if (left->x[left_bneg] <= x1)
1500 if (left->x[left_bneg ^ 1] <= x1 &&
1501 x1 * left->a + ctx->y * left->b + left->c >= 0)
1503 if (left->y0 != ctx->y && left->y1 != ctx->y)
1505 art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
1508 art_dprint ("x0=%.16f > x1=%.16f, swapping %08x, %08x\n",
1509 x0, x1, (unsigned long)left, (unsigned long)seg);
1511 art_svp_intersect_swap_active (ctx, left, seg);
1512 if (first && left->right != NULL)
1514 art_svp_intersect_test_cross (ctx, left, left->right,
1522 ArtActiveSeg *right;
1523 art_boolean first = ART_TRUE;
1525 for (right = seg->right; right != NULL; right = seg->right)
1527 int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
1529 if (right->x[right_bneg ^ 1] >= x1)
1531 if (right->x[right_bneg] >= x1 &&
1532 x1 * right->a + ctx->y * right->b + right->c <= 0)
1534 if (right->y0 != ctx->y && right->y1 != ctx->y)
1536 art_svp_intersect_break (ctx, right, x1, ctx->y,
1540 art_dprint ("[right]x0=%.16f < x1=%.16f, swapping %08x, %08x\n",
1541 x0, x1, (unsigned long)seg, (unsigned long)right);
1543 art_svp_intersect_swap_active (ctx, seg, right);
1544 if (first && right->left != NULL)
1546 art_svp_intersect_test_cross (ctx, right->left, right,
1556 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1560 * art_svp_intersect_insert_line: Insert a line into the active list.
1561 * @ctx: Intersector context.
1562 * @seg: Segment containing line to insert.
1564 * Inserts the line into the intersector context, taking care of any
1565 * intersections, and adding the appropriate horizontal points to the
1569 art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
1571 if (seg->y1 == seg->y0)
1574 art_dprint ("art_svp_intersect_insert_line(%d): %08x is horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1576 art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
1581 art_dprint ("art_svp_intersect_insert_line(%d): %08x is non-horizontal\n", seg->flags&ART_ACTIVE_FLAGS_IN_ACTIVE, (unsigned long)seg);
1583 art_svp_intersect_insert_cross (ctx, seg);
1584 art_svp_intersect_add_horiz (ctx, seg);
1587 seg->flags |= ART_ACTIVE_FLAGS_IN_ACTIVE; //q
1591 art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
1594 int n_stack = --seg->n_stack;
1595 seg->x[1] = seg->stack[n_stack - 1].x;
1596 seg->y1 = seg->stack[n_stack - 1].y;
1597 seg->x[0] = seg->stack[n_stack].x;
1598 seg->y0 = seg->stack[n_stack].y;
1599 seg->horiz_x = seg->x[0];
1601 art_dprint("process intersection %08x (%.16f,%.16f-%.16f,%.16f)\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
1603 art_svp_intersect_insert_line (ctx, seg);
1607 art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
1608 ArtPriPoint *pri_pt)
1610 const ArtSVPSeg *in_seg = seg->in_seg;
1611 int in_curs = seg->in_curs;
1612 ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
1615 swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
1616 if (in_curs + 1 >= in_seg->n_points)
1618 ArtActiveSeg *left = seg->left, *right = seg->right;
1622 swr->close_segment (swr, seg->seg_id);
1623 seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
1625 seg->flags |= ART_ACTIVE_FLAGS_DEL;
1626 art_svp_intersect_add_horiz (ctx, seg);
1627 art_svp_intersect_active_delete (ctx, seg);
1628 if (left != NULL && right != NULL)
1629 art_svp_intersect_test_cross (ctx, left, right,
1630 ART_BREAK_LEFT | ART_BREAK_RIGHT);
1635 seg->horiz_x = seg->x[1];
1637 art_svp_intersect_setup_seg (seg, pri_pt);
1638 art_pri_insert (ctx->pq, pri_pt);
1639 art_svp_intersect_insert_line (ctx, seg);
1644 art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
1646 ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
1649 ArtActiveSeg *beg_range;
1650 ArtActiveSeg *last = NULL;
1651 ArtActiveSeg *left, *right;
1652 ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
1655 seg->in_seg = in_seg;
1658 seg->n_stack_max = 4;
1659 seg->stack = art_new (ArtPoint, seg->n_stack_max);
1661 seg->horiz_delta_wind = 0;
1665 pri_pt->user_data = seg;
1666 art_svp_intersect_setup_seg (seg, pri_pt);
1667 art_pri_insert (ctx->pq, pri_pt);
1669 /* Find insertion place for new segment */
1670 /* This is currently a left-to-right scan, but should be replaced
1671 with a binary search as soon as it's validated. */
1673 x0 = in_seg->points[0].x;
1674 y0 = in_seg->points[0].y;
1676 for (test = ctx->active_head; test != NULL; test = test->right)
1679 int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
1681 if (x0 < test->x[test_bneg])
1683 if (x0 < test->x[test_bneg ^ 1]) {
1685 art_dprint("inserting segment %08x before %08x (x0 < xmin)\n", seg, test);
1689 d = x0 * test->a + y0 * test->b + test->c;
1692 art_dprint("inserting segment %08x before %08x (d = %.16f)\n", seg, test, d);
1697 art_dprint("segment %08x is to the right of %08x d=%.16f\n", seg, test, d);
1701 d = x0 * test->a + y0 * test->b + test->c;
1702 art_dprint("segment %08x is to the right of %08x d=%.16f (not used)\n", seg, test, d);
1708 left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
1711 art_dprint("left=%08x x0=%.16f y=%.16f\n", left, x0, y0);
1717 right = ctx->active_head;
1718 ctx->active_head = seg;
1722 right = left->right;
1729 seg->delta_wind = in_seg->dir ? 1 : -1;
1732 art_svp_intersect_insert_line (ctx, seg);
1737 art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
1740 /* At this point, we seem to be getting false positives, so it's
1741 turned off for now. */
1744 int winding_number = 0;
1746 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1748 /* Check winding number consistency. */
1749 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1751 if (winding_number != seg->wind_left)
1752 art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %08x has wind_left of %d, expected %d\n",
1753 (unsigned long) seg, seg->wind_left, winding_number);
1754 winding_number = seg->wind_left + seg->delta_wind;
1757 if (winding_number != 0)
1758 art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
1765 * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
1766 * @ctx: Intersection context.
1768 * The main function of the horizontal commit is to output new
1769 * points to the output writer.
1771 * This "commit" pass is also where winding numbers are assigned,
1772 * because doing it here provides much greater tolerance for inputs
1773 * which are not in strict SVP order.
1775 * Each cluster in the horiz_list contains both segments that are in
1776 * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
1777 * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
1778 * need to deal with both.
1781 art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
1784 int winding_number = 0; /* initialization just to avoid warning */
1786 double last_x = 0; /* initialization just to avoid warning */
1789 art_dprint ("art_svp_intersect_horiz_commit: y=%.16f\n", ctx->y);
1790 for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
1791 art_dprint (" %08x: %.16f %+d segid=%d\n",
1792 (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind, seg->seg_id);
1795 /* Output points to svp writer. */
1796 for (seg = ctx->horiz_first; seg != NULL;)
1798 /* Find a cluster with common horiz_x, */
1800 double x = seg->horiz_x;
1802 /* Generate any horizontal segments. */
1803 if (horiz_wind != 0)
1805 ArtSvpWriter *swr = ctx->out;
1809 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);
1811 seg_id = swr->add_segment (swr, winding_number, horiz_wind,
1813 swr->add_point (swr, seg_id, x, ctx->y);
1814 swr->close_segment (swr, seg_id);
1817 /* Find first active segment in cluster. */
1819 for (curs = seg; curs != NULL && curs->horiz_x == x;
1820 curs = curs->horiz_right)
1821 if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
1824 if (curs != NULL && curs->horiz_x == x)
1826 /* There exists at least one active segment in this cluster. */
1828 /* Find beginning of cluster. */
1829 for (; curs->left != NULL; curs = curs->left)
1830 if (curs->left->horiz_x != x)
1833 if (curs->left != NULL)
1834 winding_number = curs->left->wind_left + curs->left->delta_wind;
1841 art_dprint (" curs %08x: winding_number = %d += %d\n", (unsigned long)curs, winding_number, curs->delta_wind);
1843 if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
1844 curs->wind_left != winding_number)
1846 ArtSvpWriter *swr = ctx->out;
1848 if (curs->flags & ART_ACTIVE_FLAGS_OUT)
1850 swr->add_point (swr, curs->seg_id,
1851 curs->horiz_x, ctx->y);
1852 swr->close_segment (swr, curs->seg_id);
1855 curs->seg_id = swr->add_segment (swr, winding_number,
1858 curs->flags |= ART_ACTIVE_FLAGS_OUT;
1860 curs->wind_left = winding_number;
1861 winding_number += curs->delta_wind;
1864 while (curs != NULL && curs->horiz_x == x);
1867 /* Skip past cluster. */
1870 ArtActiveSeg *next = seg->horiz_right;
1872 seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
1873 horiz_wind += seg->horiz_delta_wind;
1874 seg->horiz_delta_wind = 0;
1875 if (seg->flags & ART_ACTIVE_FLAGS_DEL)
1877 if (seg->flags & ART_ACTIVE_FLAGS_OUT)
1879 ArtSvpWriter *swr = ctx->out;
1880 swr->close_segment (swr, seg->seg_id);
1882 art_svp_intersect_active_free (seg);
1886 while (seg != NULL && seg->horiz_x == x);
1890 ctx->horiz_first = NULL;
1891 ctx->horiz_last = NULL;
1893 art_svp_intersect_sanitycheck_winding (ctx);
1899 art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx, double y)
1902 ArtActiveSeg *last = NULL;
1906 art_dprint ("Active list (y = %.16f (new: %.16f)):\n", ctx->y, y);
1909 for (seg = ctx->active_head; seg != NULL; seg = seg->right)
1912 char c1=' ',c2=' ',e1=' ';
1913 if(seg->y0 > ctx->y) c1='!';
1914 if(seg->y0 > y) c2='!';
1915 if(seg->y0 > seg->y1) e1='E';
1918 if (seg->left != last)
1920 art_warn ("*** art_svp_intersect_sanitycheck: last=%08x, seg->left=%08x\n",
1921 (unsigned long)last, (unsigned long)seg->left);
1925 /* pairwise compare with previous seg */
1927 /* First the top. */
1928 if (last->y0 < seg->y0)
1935 /* Then the bottom. */
1936 if (last->y1 < seg->y1)
1939 seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
1940 last->y1 == seg->y0))
1942 d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
1943 if (d >= EPSILON_A) {
1944 art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to right (d = %g)\n",
1945 last->x[1], last->y1, (unsigned long) last,
1946 (unsigned long) seg, d);
1950 art_dprint("is to the left (d=%.16f of previous x1,y1) of\n", d);
1955 art_dprint("is to the left (previous x1 < next x%d) of\n", (seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1);
1959 else if (last->y1 > seg->y1)
1963 last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
1964 seg->y1 == last->y0))
1966 d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
1967 if (d < -EPSILON_A) {
1968 art_warn ("*** bottom (%.16f, %.16f) of %08x is not clear of %08x to left (d = %.16f)\n",
1969 seg->x[1], seg->y1, (unsigned long) seg,
1970 (unsigned long) last, d);
1974 art_dprint("is to the left (d=%.16f of next x1,y1) of\n", d);
1979 art_dprint("is to the left (next x1 > previous x%d) of\n", last->flags & ART_ACTIVE_FLAGS_BNEG);
1985 if (last->x[1] - seg->x[1] > EPSILON_A) {
1986 art_warn ("*** bottoms (%.16f, %.16f) of %08x and (%.16f, %.16f) of %08x out of order\n",
1987 last->x[1], last->y1, (unsigned long)last,
1988 seg->x[1], seg->y1, (unsigned long)seg);
1992 art_dprint("is to the left (y1s equal, previous x1 < next x1)\n");
1999 art_dprint ("%c%08x: %c%c %02d (%.16f, %.16f)-(%.16f, %.16f) ",
2001 (unsigned long)seg, c1, c2, seg->flags,
2002 seg->x[0], seg->y0, seg->x[1], seg->y1);
2014 art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
2016 ArtIntersectCtx *ctx;
2018 ArtPriPoint *first_point;
2023 if (in->n_segs == 0)
2030 art_dprint("Segments: %d\n", in->n_segs);
2031 for(t=0;t<in->n_segs;t++) {
2032 const ArtSVPSeg* seg = &in->segs[t];
2033 art_dprint("Segment %08x(%d): %d points, %s, BBox: (%f,%f,%f,%f)\n",
2034 seg, t, seg->n_points, seg->dir==0?"UP ":"DOWN",
2035 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
2037 for(p=0;p<seg->n_points;p++) {
2038 ArtPoint* point = &seg->points[p];
2039 art_dprint(" (%.16f,%.16f)\n", point->x, point->y);
2045 ctx = art_new (ArtIntersectCtx, 1);
2048 pq = art_pri_new ();
2051 ctx->active_head = NULL;
2053 ctx->horiz_first = NULL;
2054 ctx->horiz_last = NULL;
2057 first_point = art_new (ArtPriPoint, 1);
2058 first_point->x = in->segs[0].points[0].x;
2059 first_point->y = in->segs[0].points[0].y;
2060 first_point->user_data = NULL;
2061 ctx->y = first_point->y;
2062 art_pri_insert (pq, first_point);
2064 double lasty = -HUGE_VAL;
2065 while (!art_pri_empty (pq))
2067 ArtPriPoint *pri_point = art_pri_choose (pq);
2068 ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
2071 art_dprint ("\nIntersector step %d (%d items in pq)\n", count++, pq->n_items);
2074 art_svp_intersect_sanitycheck(ctx, pri_point->y);
2077 art_dprint ("priq choose (%.16f, %.16f) %08x\n", pri_point->x, pri_point->y,
2078 (unsigned long)pri_point->user_data);
2080 art_dprint (" %08x = %.16f,%.16f -> %.16f %.16f\n", seg, seg->x[0], seg->y0, seg->x[1], seg->y1);
2083 //for(t=0;t<pq->n_items;t++) {
2084 // art_dprint("pq[%d] %.16f,%.16f %08x\n",
2088 // pq->items[t]->user_data);
2092 //art_dprint("y=%f %08x\n", pri_point->y, pri_point->user_data);
2093 if (ctx->y != pri_point->y)
2095 art_svp_intersect_horiz_commit (ctx);
2096 ctx->y = pri_point->y;
2099 if(ctx->y < lasty) {
2100 art_warn("y decreased\n");
2106 /* Insert new segment from input */
2107 const ArtSVPSeg *in_seg = 0;
2110 in_seg = &in->segs[ctx->in_curs++];
2111 if(in_seg->n_points > 1)
2113 if(ctx->in_curs == in->n_segs) {
2119 art_dprint("ignoring input segment %08x- it only contains %d point(s)\n",
2120 in_seg, in_seg->n_points);
2127 for(t=0;t<in_seg->n_points-1;t++) {
2128 if(!(in_seg->points[t].y <= in_seg->points[t+1].y)) {
2133 art_warn("bad input: contains a segment with descending y\n");
2134 for(t=0;t<in_seg->n_points;t++) {
2135 art_dprint("%d) %.16f %.16f\n", t, in_seg->points[t].x, in_seg->points[t].y);
2141 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);
2143 art_svp_intersect_add_seg (ctx, in_seg);
2144 if (ctx->in_curs < in->n_segs)
2146 const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
2147 pri_point->x = next_seg->points[0].x;
2148 pri_point->y = next_seg->points[0].y;
2149 /* user_data is already NULL */
2150 art_pri_insert (pq, pri_point);
2153 art_free(pri_point);pri_point =0;
2155 art_free(pri_point);pri_point = 0;
2160 int n_stack = seg->n_stack;
2164 art_svp_intersect_process_intersection (ctx, seg);
2165 art_free (pri_point);
2169 art_svp_intersect_advance_cursor (ctx, seg, pri_point);
2175 art_svp_intersect_horiz_commit (ctx);