13 static gfxpoly_t*current_polygon = 0;
14 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
16 if(!current_polygon) {fprintf(stderr, "error outside polygon\n");exit(1);}
18 void*md5 = init_md5();
20 edge_t* s = current_polygon->edges;
22 update_md5(md5, (unsigned char*)&s->a.x, sizeof(s->a.x));
23 update_md5(md5, (unsigned char*)&s->a.y, sizeof(s->a.y));
24 update_md5(md5, (unsigned char*)&s->b.x, sizeof(s->b.x));
25 update_md5(md5, (unsigned char*)&s->b.y, sizeof(s->b.y));
29 char filename[32+4+1];
31 sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
32 h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
34 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
35 fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
37 gfxpoly_save(current_polygon, filename);
41 static char point_equals(const void*o1, const void*o2)
43 const point_t*p1 = o1;
44 const point_t*p2 = o2;
45 return p1->x == p2->x && p1->y == p2->y;
47 static unsigned int point_hash(const void*o)
52 static void* point_dup(const void*o)
55 point_t*n = malloc(sizeof(point_t));
60 static void point_free(void*o)
67 static type_t point_type = {
74 typedef struct _status {
81 windcontext_t*context;
82 segment_t*ending_segments;
84 dict_t*seen_crossings; //list of crossing we saw so far
85 dict_t*intersecting_segs; //list of segments intersecting in this scanline
86 dict_t*segs_with_point; //lists of segments that received a point in this scanline
90 /* compare_events_simple differs from compare_events in that it schedules
91 events from left to right regardless of type. It's only used in horizontal
92 processing, in order to get an x-wise sorting of the current scanline */
93 static int compare_events_simple(const void*_a,const void*_b)
95 event_t* a = (event_t*)_a;
96 event_t* b = (event_t*)_b;
97 int d = b->p.y - a->p.y;
104 static int compare_events(const void*_a,const void*_b)
106 event_t* a = (event_t*)_a;
107 event_t* b = (event_t*)_b;
108 int d = b->p.y - a->p.y;
110 /* we need to schedule end after intersect (so that a segment about
111 to end has a chance to tear up a few other segs first) and start
112 events after end (in order not to confuse the intersection check, which
113 assumes there's an actual y overlap between active segments)).
114 Horizontal lines come last, because the only purpose
115 they have is to create snapping coordinates for the segments (still)
116 existing in this scanline.
118 d = b->type - a->type;
124 gfxpoly_t* gfxpoly_new(double gridsize)
126 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
127 p->gridsize = gridsize;
130 void gfxpoly_destroy(gfxpoly_t*poly)
132 edge_t* s = poly->edges;
134 edge_t*next = s->next;
140 int gfxpoly_size(gfxpoly_t*poly)
142 edge_t* s = poly->edges;
150 char gfxpoly_check(gfxpoly_t*poly)
152 edge_t* s = poly->edges;
153 dict_t*d = dict_new2(&point_type);
155 if(!dict_contains(d, &s->a)) {
156 dict_put(d, &s->a, (void*)(ptroff_t)1);
158 int count = (ptroff_t)dict_lookup(d, &s->a);
161 dict_put(d, &s->a, (void*)(ptroff_t)count);
163 if(!dict_contains(d, &s->b)) {
164 dict_put(d, &s->b, (void*)(ptroff_t)1);
166 int count = (ptroff_t)dict_lookup(d, &s->b);
169 dict_put(d, &s->b, (void*)(ptroff_t)count);
173 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
174 int count = (ptroff_t)c;
176 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
185 void gfxpoly_dump(gfxpoly_t*poly)
187 edge_t* s = poly->edges;
188 double g = poly->gridsize;
190 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
195 gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename)
197 FILE*fi = fopen(filename, "wb");
198 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
199 fprintf(fi, "%% begin\n");
200 edge_t* s = poly->edges;
202 fprintf(fi, "%g setgray\n", s->b.y < s->a.y ? 0.7 : 0);
203 fprintf(fi, "%d %d moveto\n", s->a.x, s->a.y);
204 fprintf(fi, "%d %d lineto\n", s->b.x, s->b.y);
205 fprintf(fi, "stroke\n");
208 fprintf(fi, "showpage\n");
212 inline static event_t event_new()
215 memset(&e, 0, sizeof(e));
219 static void event_dump(event_t*e)
221 if(e->type == EVENT_HORIZONTAL) {
222 fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
223 } else if(e->type == EVENT_START) {
224 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
225 } else if(e->type == EVENT_END) {
226 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
227 } else if(e->type == EVENT_CROSS) {
228 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
229 } else if(e->type == EVENT_CORNER) {
230 fprintf(stderr, "event: segment [%d] ends, segment [%d] starts, at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
236 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
237 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
239 static void segment_dump(segment_t*s)
241 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
242 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
243 (double)s->delta.x / s->delta.y);
246 static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr)
251 int32_t x = x1;x1=x2;x2=x;
252 int32_t y = y1;y1=y2;y2=y;
255 /* up/down for horizontal segments is handled by "rotating"
256 them 90° anticlockwise in screen coordinates (tilt your head to
261 int32_t x = x1;x1=x2;x2=x;
262 int32_t y = y1;y1=y2;y2=y;
269 s->k = (double)x1*y2-(double)x2*y1;
270 s->left = s->right = 0;
273 s->minx = min32(x1,x2);
274 s->maxx = max32(x1,x2);
277 s->polygon_nr = polygon_nr;
280 static int segment_count=0;
281 s->nr = segment_count++;
285 assert(LINE_EQ(s->a, s) == 0);
286 assert(LINE_EQ(s->b, s) == 0);
288 /* check that all signs are in order:
296 p.x = min32(s->a.x, s->b.x);
297 assert(LINE_EQ(p, s) <= 0);
298 p.x = max32(s->a.x, s->b.x);
299 assert(LINE_EQ(p, s) >= 0);
302 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
305 static segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr)
307 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
308 segment_init(s, x1, y1, x2, y2, polygon_nr);
312 static void segment_destroy(segment_t*s)
314 dict_clear(&s->scheduled_crossings);
318 static void gfxpoly_enqueue(edge_t*list, heap_t*queue, int polygon_nr)
321 for(l=list;l;l=l->next) {
322 if(l->a.x == l->b.x &&
324 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
327 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, polygon_nr);
331 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
332 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
333 s->dir==DIR_UP?"up":"down");
335 event_t e = event_new();
336 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
344 static void schedule_endpoint(status_t*status, segment_t*s)
346 // schedule end point of segment
347 assert(s->b.y > status->y);
353 heap_put(status->queue, &e);
356 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
358 /* the code that's required (and the checks you can perform) before
359 it can be said with 100% certainty that we indeed have a valid crossing
360 amazes me every time. -mk */
364 assert(s1->right == s2);
365 assert(s2->left == s1);
366 int32_t miny1 = min32(s1->a.y,s1->b.y);
367 int32_t maxy1 = max32(s1->a.y,s1->b.y);
368 int32_t miny2 = min32(s2->a.y,s2->b.y);
369 int32_t maxy2 = max32(s2->a.y,s2->b.y);
370 int32_t minx1 = min32(s1->a.x,s1->b.x);
371 int32_t minx2 = min32(s2->a.x,s2->b.x);
372 int32_t maxx1 = max32(s1->a.x,s1->b.x);
373 int32_t maxx2 = max32(s2->a.x,s2->b.x);
374 /* check that precomputation is sane */
375 assert(minx1 == s1->minx && minx2 == s2->minx);
376 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
377 /* both segments are active, so this can't happen */
378 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
379 /* we know that right now, s2 is to the right of s1, so there's
380 no way the complete bounding box of s1 is to the right of s1 */
381 assert(!(s1->minx > s2->maxx));
382 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
385 if(s1->maxx <= s2->minx) {
386 /* bounding boxes don't intersect */
390 if(dict_contains(&s1->scheduled_crossings, s2)) {
391 /* FIXME: this whole segment hashing thing is really slow */
392 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
393 return; // we already know about this one
396 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
399 // lines are exactly on top of each other (ignored)
401 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
405 /* lines are parallel */
409 double asign2 = LINE_EQ(s1->a, s2);
410 double bsign2 = LINE_EQ(s1->b, s2);
411 if(asign2<0 && bsign2<0) {
412 // segment1 is completely to the left of segment2
415 if(asign2>0 && bsign2>0) {
416 // segment2 is completely to the left of segment1
420 // segment1 touches segment2 in a single point (ignored)
422 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
427 // segment1 touches segment2 in a single point (ignored)
429 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
433 double asign1 = LINE_EQ(s2->a, s1);
434 double bsign1 = LINE_EQ(s2->b, s1);
435 if(asign1<0 && bsign1<0) {
436 // segment1 is completely to the left of segment2
439 if(asign1>0 && bsign1>0) {
440 // segment2 is completely to the left of segment1
444 // segment2 touches segment1 in a single point (ignored)
446 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
451 // segment2 touches segment1 in a single point (ignored)
453 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
458 /* TODO: should we precompute these? */
459 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
460 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
463 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
464 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
466 assert(p.y >= status->y);
468 assert(p.x >= s1->minx && p.x <= s1->maxx);
469 assert(p.x >= s2->minx && p.x <= s2->maxx);
474 assert(!dict_contains(status->seen_crossings, &pair));
475 dict_put(status->seen_crossings, &pair, 0);
478 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
481 /* we insert into each other's intersection history because these segments might switch
482 places and we still want to look them up quickly after they did */
483 dict_put(&s1->scheduled_crossings, s2, 0);
484 dict_put(&s2->scheduled_crossings, s1, 0);
486 event_t e = event_new();
487 e.type = EVENT_CROSS;
491 heap_put(status->queue, &e);
495 static void exchange_two(status_t*status, event_t*e)
497 //exchange two segments in list
498 segment_t*s1 = e->s1;
499 segment_t*s2 = e->s2;
501 if(!dict_contains(status->intersecting_segs, s1))
502 dict_put(status->intersecting_segs, s1, 0);
503 if(!dict_contains(status->intersecting_segs, s2))
504 dict_put(status->intersecting_segs, s2, 0);
506 assert(s2->left == s1);
507 assert(s1->right == s2);
508 actlist_swap(status->actlist, s1, s2);
509 assert(s2->right == s1);
510 assert(s1->left == s2);
511 segment_t*left = s2->left;
512 segment_t*right = s1->right;
514 schedule_crossing(status, left, s2);
516 schedule_crossing(status, s1, right);
519 typedef struct _box {
520 point_t left1, left2, right1, right2;
522 static inline box_t box_new(int32_t x, int32_t y)
525 box.right1.x = box.right2.x = x;
526 box.left1.x = box.left2.x = x-1;
527 box.left1.y = box.right1.y = y-1;
528 box.left2.y = box.right2.y = y;
533 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
535 assert(s->pos.x != p.x || s->pos.y != p.y);
538 if(!dict_contains(status->segs_with_point, s))
539 dict_put(status->segs_with_point, s, 0);
540 assert(s->fs_out_ok);
545 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
546 s->pos.x, s->pos.y, p.x, p.y);
548 // omit horizontal lines
549 if(s->pos.y != p.y) {
550 edge_t*e = rfx_calloc(sizeof(edge_t));
556 assert(e->a.y != e->b.y);
557 e->next = status->output;
562 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
568 typedef struct _segrange {
575 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
577 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
578 segment_t*min = range->segmin;
579 segment_t*max = range->segmax;
581 /* we need this because if two segments intersect exactly on
582 the scanline, segrange_test_segment_{min,max} can't tell which
583 one is smaller/larger */
584 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
587 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
593 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
596 /* we need to calculate the xpos anew (and can't use start coordinate or
597 intersection coordinate), because we need the xpos exactly at the end of
599 TODO: might be faster to use XPOS_COMPARE here (see also _max)
601 double x = XPOS(seg, y);
602 if(!range->segmin || x<range->xmin) {
607 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
610 double x = XPOS(seg, y);
611 if(!range->segmax || x>range->xmax) {
626 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
628 segment_t*first=0, *last = 0;
630 for(t=0;t<status->xrow->num;t++) {
631 box_t box = box_new(status->xrow->x[t], y);
632 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
634 seg = actlist_right(status->actlist, seg);
637 // this segment started in this scanline, ignore it
638 seg->changed = 1;last = seg;if(!first) {first=seg;}
639 } else if(seg->delta.x <= 0) {
640 // ignore segment w/ negative slope
642 last = seg;if(!first) {first=seg;}
643 double d1 = LINE_EQ(box.right1, seg);
644 double d2 = LINE_EQ(box.right2, seg);
647 insert_point_into_segment(status, seg, box.right2);
649 /* we unfortunately can't break here- the active list is sorted according
650 to the *bottom* of the scanline. hence pretty much everything that's still
651 coming might reach into our box */
655 seg = actlist_right(status->actlist, seg);
658 segrange_test_segment_min(range, first, y);
659 segrange_test_segment_max(range, last, y);
669 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
671 segment_t*first=0, *last = 0;
673 for(t=status->xrow->num-1;t>=0;t--) {
674 box_t box = box_new(status->xrow->x[t], y);
675 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
679 // this segment started in this scanline, ignore it
680 seg->changed = 1;last = seg;if(!first) {first=seg;}
681 } else if(seg->delta.x > 0) {
682 // ignore segment w/ positive slope
684 last = seg;if(!first) {first=seg;}
685 double d1 = LINE_EQ(box.left1, seg);
686 double d2 = LINE_EQ(box.left2, seg);
689 insert_point_into_segment(status, seg, box.right2);
694 seg = actlist_left(status->actlist, seg);
697 segrange_test_segment_min(range, last, y);
698 segrange_test_segment_max(range, first, y);
701 /* segments ending in the current scanline need xrow treatment like everything else.
702 (consider an intersection taking place just above a nearly horizontal segment
703 ending on the current scanline- the intersection would snap down *below* the
704 ending segment if we don't add the intersection point to the latter right away)
705 we need to treat ending segments seperately, however. we have to delete them from
706 the active list right away to make room for intersect operations (which might
707 still be in the current scanline- consider two 45° polygons and a vertical polygon
708 intersecting on an integer coordinate). but once they're no longer in the active list,
709 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
710 them to the active list just for point snapping would be overkill.
711 (One other option to consider, however, would be to create a new active list only
714 static void add_points_to_ending_segments(status_t*status, int32_t y)
716 segment_t*seg = status->ending_segments;
718 segment_t*next = seg->right;seg->right=0;
720 assert(seg->b.y == status->y);
722 if(status->xrow->num == 1) {
724 point_t p = {status->xrow->x[0], y};
725 insert_point_into_segment(status, seg, p);
728 int start=0,end=status->xrow->num,dir=1;
729 if(seg->delta.x < 0) {
730 start = status->xrow->num-1;
733 for(t=start;t!=end;t+=dir) {
734 box_t box = box_new(status->xrow->x[t], y);
735 double d0 = LINE_EQ(box.left1, seg);
736 double d1 = LINE_EQ(box.left2, seg);
737 double d2 = LINE_EQ(box.right1, seg);
738 double d3 = LINE_EQ(box.right2, seg);
739 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
740 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
741 insert_point_into_segment(status, seg, box.right2);
747 /* we *need* to find a point to insert. the segment's own end point
748 is in that list, for Pete's sake. */
752 // now that this is done, too, we can also finally free this segment
753 segment_destroy(seg);
756 status->ending_segments = 0;
759 static void recalculate_windings(status_t*status, segrange_t*range)
762 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
764 segrange_adjust_endpoints(range, status->y);
766 segment_t*s = range->segmin;
767 segment_t*end = range->segmax;
771 s = actlist_leftmost(status->actlist);
773 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
774 s == range->segmin?"S":(
775 s == range->segmax?"E":""));
778 fprintf(stderr, "\n");
782 /* test sanity: check that we don't have changed segments
783 outside of the given range */
784 s = actlist_leftmost(status->actlist);
785 while(s && s!=range->segmin) {
789 s = actlist_rightmost(status->actlist);
790 while(s && s!=range->segmax) {
794 /* in check mode, go through the whole interval so we can test
795 that all polygons where the fillstyle changed also have seg->changed=1 */
796 s = actlist_leftmost(status->actlist);
801 end = actlist_right(status->actlist, end);
807 segment_t* left = actlist_left(status->actlist, s);
808 windstate_t wind = left?left->wind:status->windrule->start(status->context);
809 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
810 fillstyle_t*fs_old = s->fs_out;
811 s->fs_out = status->windrule->diff(&wind, &s->wind);
813 assert(!(!s->changed && fs_old!=s->fs_out));
820 fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit",
821 fs_old!=s->fs_out?"CHANGED":"");
828 /* we need to handle horizontal lines in order to add points to segments
829 we otherwise would miss during the windrule re-evaluation */
830 static void intersect_with_horizontal(status_t*status, segment_t*h)
832 segment_t* left = actlist_find(status->actlist, h->a, h->a);
833 segment_t* right = actlist_find(status->actlist, h->b, h->b);
835 /* not strictly necessary, also done by the event */
836 xrow_add(status->xrow, h->a.x);
844 left = actlist_right(status->actlist, left); //first seg to the right of h->a
845 right = right->right; //first seg to the right of h->b
850 int32_t x = XPOS_INT(s, status->y);
852 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
860 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
861 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
862 xrow_add(status->xrow, x);
868 static void event_apply(status_t*status, event_t*e)
871 case EVENT_HORIZONTAL: {
875 intersect_with_horizontal(status, e->s1);
876 segment_destroy(e->s1);e->s1=0;
880 //delete segment from list
886 dict_del(status->intersecting_segs, s);
887 dict_del(status->segs_with_point, s);
888 assert(!dict_contains(status->intersecting_segs, s));
889 assert(!dict_contains(status->segs_with_point, s));
891 segment_t*left = actlist_left(status->actlist, s);
892 segment_t*right = actlist_right(status->actlist, s);
893 actlist_delete(status->actlist, s);
895 schedule_crossing(status, left, right);
897 s->left = 0; s->right = status->ending_segments;
898 status->ending_segments = s;
902 //insert segment into list
907 assert(e->p.x == s->a.x && e->p.y == s->a.y);
908 actlist_insert(status->actlist, s->a, s->b, s);
909 segment_t*left = actlist_left(status->actlist, s);
910 segment_t*right = actlist_right(status->actlist, s);
912 schedule_crossing(status, left, s);
914 schedule_crossing(status, s, right);
915 schedule_endpoint(status, e->s1);
919 // exchange two segments
923 if(actlist_right(status->actlist, e->s1) == e->s2 &&
924 actlist_left(status->actlist, e->s2) == e->s1) {
925 exchange_two(status, e);
928 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
930 /* ignore this crossing for now (there are some line segments in between).
931 it'll get rescheduled as soon as the "obstacles" are gone */
932 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
933 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
934 assert(del1 && del2);
939 assert(dict_contains(status->seen_crossings, &pair));
940 dict_del(status->seen_crossings, &pair);
948 static void check_status(status_t*status)
950 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
951 if((s->pos.x != s->b.x ||
952 s->pos.y != s->b.y) &&
953 !dict_contains(status->segs_with_point, s)) {
954 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
956 s->delta.x<0?"-":"+",
964 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
967 |..| |...........| | |
968 |..| |...........| | |
969 |..+ + +..| +--+ +--+
970 |...........| |..| | |
971 |...........| |..| | |
975 fprintf(stderr, "========================================================================\n");
977 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
978 gfxpoly_enqueue(poly->edges, queue, 0);
980 actlist_t* actlist = actlist_new();
982 event_t*e = heap_chopmax(queue);
988 fprintf(stderr, "----------------------------------- %d\n", y);
989 actlist_dump(actlist, y-1);
992 actlist_verify(actlist, y-1);
995 if(fill && x != e->p.x) {
997 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1000 edge_t*l= malloc(sizeof(edge_t));
1001 l->a.y = l->b.y = y;
1002 /* TODO: strictly speaking we need to draw from low x to high x so that left/right fillstyles add up
1003 (because the horizontal line's fill style controls the area *below* the line)
1007 l->next = poly->edges;
1010 /* the output should always be intersection free polygons, so check this horizontal
1011 line isn't hacking through any segments in the active list */
1012 segment_t* start = actlist_find(actlist, l->a, l->a);
1013 segment_t* s = actlist_find(actlist, l->b, l->b);
1015 assert(s->a.y == y || s->b.y == y);
1021 segment_t*s = e->s1;
1023 windstate_t before,after;
1026 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1027 actlist_insert(actlist, s->a, s->b, s);
1033 heap_put(queue, &e);
1034 left = actlist_left(actlist, s);
1036 before = left?left->wind:windrule->start(context);
1037 after = s->wind = windrule->add(context, before, s->fs, s->dir, s->polygon_nr);
1041 left = actlist_left(actlist, s);
1042 actlist_delete(actlist, s);
1045 after = left?left->wind:windrule->start(context);
1052 fill ^= 1;//(before.is_filled != after.is_filled);
1054 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
1055 y, e->type==EVENT_START?"start":"end",
1059 before.is_filled, after.is_filled);
1062 if(e->type == EVENT_END)
1066 e = heap_chopmax(queue);
1067 } while(e && y == e->p.y);
1069 assert(!fill); // check that polygon is not bleeding
1071 actlist_destroy(actlist);
1072 heap_destroy(queue);
1075 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1077 current_polygon = poly;
1078 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1080 gfxpoly_enqueue(poly->edges, queue, /*polygon nr*/0);
1083 memset(&status, 0, sizeof(status_t));
1084 status.queue = queue;
1085 status.windrule = windrule;
1086 status.context = context;
1087 status.actlist = actlist_new();
1089 status.seen_crossings = dict_new2(&point_type);
1092 status.xrow = xrow_new();
1094 event_t*e = heap_chopmax(queue);
1098 status.intersecting_segs = dict_new2(&ptr_type);
1099 status.segs_with_point = dict_new2(&ptr_type);
1103 fprintf(stderr, "----------------------------------- %d\n", status.y);
1104 actlist_dump(status.actlist, status.y-1);
1107 actlist_verify(status.actlist, status.y-1);
1109 xrow_reset(status.xrow);
1111 xrow_add(status.xrow, e->p.x);
1112 event_apply(&status, e);
1114 e = heap_chopmax(queue);
1115 } while(e && status.y == e->p.y);
1117 xrow_sort(status.xrow);
1119 memset(&range, 0, sizeof(range));
1121 actlist_dump(status.actlist, status.y);
1123 add_points_to_positively_sloped_segments(&status, status.y, &range);
1124 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1125 add_points_to_ending_segments(&status, status.y);
1127 recalculate_windings(&status, &range);
1129 check_status(&status);
1130 dict_destroy(status.intersecting_segs);
1131 dict_destroy(status.segs_with_point);
1135 dict_destroy(status.seen_crossings);
1137 actlist_destroy(status.actlist);
1138 heap_destroy(queue);
1139 xrow_destroy(status.xrow);
1141 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1142 p->edges = status.output;
1144 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd