12 static gfxpoly_t*current_polygon = 0;
13 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
15 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
16 fprintf(stderr, "I'm saving a debug file \"poly.ps\" to the current directory.\n");
17 gfxpoly_save(current_polygon, "poly.ps");
21 char point_equals(const void*o1, const void*o2)
23 const point_t*p1 = o1;
24 const point_t*p2 = o2;
25 return p1->x == p2->x && p1->y == p2->y;
27 unsigned int point_hash(const void*o)
32 void* point_dup(const void*o)
35 point_t*n = malloc(sizeof(point_t));
40 void point_free(void*o)
54 typedef struct _status {
62 segment_t*ending_segments;
64 dict_t*seen_crossings; //list of crossing we saw so far
65 dict_t*intersecting_segs; //list of segments intersecting in this scanline
66 dict_t*segs_with_point; //lists of segments that received a point in this scanline
70 int compare_events_simple(const void*_a,const void*_b)
72 event_t* a = (event_t*)_a;
73 event_t* b = (event_t*)_b;
76 } else if(a->p.y > b->p.y) {
78 } else if(a->p.x < b->p.x) {
80 } else if(a->p.x > b->p.x) {
86 int compare_events(const void*_a,const void*_b)
88 event_t* a = (event_t*)_a;
89 event_t* b = (event_t*)_b;
90 int d = b->p.y - a->p.y;
92 /* we need to schedule end before intersect (so that a segment about
93 to end has a chance to tear up a few other segs first) and start
94 events after intersect (so that start segments don't position themselves
95 between two segments about to intersect (not a problem as such, but makes
96 things slower)). Horizontal lines come last, because the only purpose
97 they have is to create snapping coordinates for the segments (still)
98 existing in this scanline */
99 d = b->type - a->type;
105 gfxpoly_t* gfxpoly_new(double gridsize)
107 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
108 p->gridsize = gridsize;
111 void gfxpoly_destroy(gfxpoly_t*poly)
113 edge_t* s = poly->edges;
115 edge_t*next = s->next;
121 int gfxpoly_size(gfxpoly_t*poly)
123 edge_t* s = poly->edges;
130 char gfxpoly_check(gfxpoly_t*poly)
132 edge_t* s = poly->edges;
133 dict_t*d = dict_new2(&point_type);
135 if(!dict_contains(d, &s->a)) {
136 dict_put(d, &s->a, (void*)(ptroff_t)1);
138 int count = (ptroff_t)dict_lookup(d, &s->a);
141 dict_put(d, &s->a, (void*)(ptroff_t)count);
143 if(!dict_contains(d, &s->b)) {
144 dict_put(d, &s->b, (void*)(ptroff_t)1);
146 int count = (ptroff_t)dict_lookup(d, &s->b);
149 dict_put(d, &s->b, (void*)(ptroff_t)count);
153 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
154 int count = (ptroff_t)c;
156 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
165 void gfxpoly_dump(gfxpoly_t*poly)
167 edge_t* s = poly->edges;
168 double g = poly->gridsize;
170 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
175 gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename)
177 FILE*fi = fopen(filename, "wb");
178 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
179 fprintf(fi, "%% begin\n");
180 edge_t* s = poly->edges;
182 fprintf(fi, "%g setgray\n", s->b.y < s->a.y ? 0.7 : 0);
183 fprintf(fi, "%d %d moveto\n", s->a.x, s->a.y);
184 fprintf(fi, "%d %d lineto\n", s->b.x, s->b.y);
185 fprintf(fi, "stroke\n");
188 fprintf(fi, "showpage\n");
192 inline static event_t event_new()
195 memset(&e, 0, sizeof(e));
199 void event_dump(event_t*e)
201 if(e->type == EVENT_HORIZONTAL) {
202 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);
203 } else if(e->type == EVENT_START) {
204 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
205 } else if(e->type == EVENT_END) {
206 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
207 } else if(e->type == EVENT_CROSS) {
208 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
214 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
215 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
217 void segment_dump(segment_t*s)
219 fprintf(stderr, "(%d,%d)->(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y);
220 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
221 (double)s->delta.x / s->delta.y);
224 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
229 int x = x1;x1=x2;x2=x;
230 int y = y1;y1=y2;y2=y;
233 /* up/down for horizontal segments is handled by "rotating"
234 them 90° anticlockwise in screen coordinates (tilt your head to
239 int x = x1;x1=x2;x2=x;
240 int y = y1;y1=y2;y2=y;
247 s->k = (double)x1*y2-(double)x2*y1;
248 s->left = s->right = 0;
251 s->minx = min32(x1,x2);
252 s->maxx = max32(x1,x2);
255 s->polygon_nr = polygon_nr;
258 static int segment_count=0;
259 s->nr = segment_count++;
262 assert(LINE_EQ(s->a, s) == 0);
263 assert(LINE_EQ(s->b, s) == 0);
265 /* check that all signs are in order:
273 p.x = min32(s->a.x, s->b.x);
274 assert(LINE_EQ(p, s) <= 0);
275 p.x = max32(s->a.x, s->b.x);
276 assert(LINE_EQ(p, s) >= 0);
278 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
281 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
283 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
284 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
287 void segment_destroy(segment_t*s)
289 dict_clear(&s->scheduled_crossings);
293 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
296 for(l=list;l;l=l->next) {
297 if(l->a.x == l->b.x &&
299 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
302 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
306 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
307 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
308 s->dir==DIR_UP?"up":"down");
310 event_t e = event_new();
311 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
319 void schedule_endpoint(status_t*status, segment_t*s)
321 // schedule end point of segment
322 assert(s->b.y > status->y);
328 heap_put(status->queue, &e);
331 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
333 /* the code that's required (and the checks you can perform) before
334 it can be said with 100% certainty that we indeed have a valid crossing
335 amazes me every time. -mk */
339 assert(s1->right == s2);
340 assert(s2->left == s1);
341 int32_t miny1 = min32(s1->a.y,s1->b.y);
342 int32_t maxy1 = max32(s1->a.y,s1->b.y);
343 int32_t miny2 = min32(s2->a.y,s2->b.y);
344 int32_t maxy2 = max32(s2->a.y,s2->b.y);
345 int32_t minx1 = min32(s1->a.x,s1->b.x);
346 int32_t minx2 = min32(s2->a.x,s2->b.x);
347 int32_t maxx1 = max32(s1->a.x,s1->b.x);
348 int32_t maxx2 = max32(s2->a.x,s2->b.x);
349 /* check that precomputation is sane */
350 assert(minx1 == s1->minx && minx2 == s2->minx);
351 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
352 /* both segments are active, so this can't happen */
353 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
354 /* we know that right now, s2 is to the right of s1, so there's
355 no way the complete bounding box of s1 is to the right of s1 */
356 assert(!(s1->minx > s2->maxx));
357 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
360 if(s1->maxx <= s2->minx) {
361 /* bounding boxes don't intersect */
365 if(dict_contains(&s1->scheduled_crossings, s2)) {
366 /* FIXME: this whole segment hashing thing is really slow */
367 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
368 return; // we already know about this one
371 double adx = s1->delta.x;
372 double ady = s1->delta.y;
373 double bdx = s2->delta.x;
374 double bdy = s2->delta.y;
375 double det = adx*bdy - ady*bdx;
378 // lines are exactly on top of each other (ignored)
380 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
384 /* lines are parallel */
388 double asign2 = LINE_EQ(s1->a, s2);
389 double bsign2 = LINE_EQ(s1->b, s2);
390 if(asign2<0 && bsign2<0) {
391 // segment1 is completely to the left of segment2
394 if(asign2>0 && bsign2>0) {
395 // segment2 is completely to the left of segment1
399 // segment1 touches segment2 in a single point (ignored)
401 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
406 // segment1 touches segment2 in a single point (ignored)
408 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
412 double asign1 = LINE_EQ(s2->a, s1);
413 double bsign1 = LINE_EQ(s2->b, s1);
414 if(asign1<0 && bsign1<0) {
415 // segment1 is completely to the left of segment2
418 if(asign1>0 && bsign1>0) {
419 // segment2 is completely to the left of segment1
423 // segment2 touches segment1 in a single point (ignored)
425 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
430 // segment2 touches segment1 in a single point (ignored)
432 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
437 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
438 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
441 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
442 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
444 assert(p.y >= status->y);
446 assert(p.x >= s1->minx && p.x <= s1->maxx);
447 assert(p.x >= s2->minx && p.x <= s2->maxx);
452 assert(!dict_contains(status->seen_crossings, &pair));
453 dict_put(status->seen_crossings, &pair, 0);
456 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
459 /* we insert into each other's intersection history because these segments might switch
460 places and we still want to look them up quickly after they did */
461 dict_put(&s1->scheduled_crossings, s2, 0);
462 dict_put(&s2->scheduled_crossings, s1, 0);
464 event_t e = event_new();
465 e.type = EVENT_CROSS;
469 heap_put(status->queue, &e);
473 void exchange_two(status_t*status, event_t*e)
475 //exchange two segments in list
476 segment_t*s1 = e->s1;
477 segment_t*s2 = e->s2;
479 if(!dict_contains(status->intersecting_segs, s1))
480 dict_put(status->intersecting_segs, s1, 0);
481 if(!dict_contains(status->intersecting_segs, s2))
482 dict_put(status->intersecting_segs, s2, 0);
484 segment_t*left = actlist_left(status->actlist, s2);
485 segment_t*right = actlist_right(status->actlist, s1);
488 actlist_swap(status->actlist, s1, s2);
489 assert(actlist_right(status->actlist, s2) == s1);
490 assert(actlist_left(status->actlist, s1) == s2);
491 left = actlist_left(status->actlist, s2);
492 right = actlist_right(status->actlist, s1);
494 schedule_crossing(status, left, s2);
496 schedule_crossing(status, s1, right);
499 typedef struct _box {
500 point_t left1, left2, right1, right2;
502 static inline box_t box_new(int x, int y)
505 box.right1.x = box.right2.x = x;
506 box.left1.x = box.left2.x = x-1;
507 box.left1.y = box.right1.y = y-1;
508 box.left2.y = box.right2.y = y;
513 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
515 assert(s->pos.x != p.x || s->pos.y != p.y);
518 if(!dict_contains(status->segs_with_point, s))
519 dict_put(status->segs_with_point, s, 0);
520 assert(s->fs_out_ok);
525 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
526 s->pos.x, s->pos.y, p.x, p.y);
528 // omit horizontal lines
529 if(s->pos.y != p.y) {
530 edge_t*e = rfx_calloc(sizeof(edge_t));
534 assert(e->a.y != e->b.y);
535 e->next = status->output;
540 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
546 /* by restricting the recalculation of line segments to a range between the lowest
547 and the highest modified segment, we only do about a 33% overprocessing of fill
548 styles. (update: that statistic might be outdated now that xmin/xmax are double) */
549 typedef struct _segrange {
556 void segrange_adjust_endpoints(segrange_t*range, int y)
558 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
560 /* this would mean that the segment left/right of the minimum/maximum
561 intersects the current segment exactly at the scanline, but somehow
562 wasn't found to be passing through the same snapping box */
563 assert(!min || !min->left || !XPOS_EQ(min, min->left, y));
564 assert(!max || !max->right || !XPOS_EQ(max, max->right, y));
567 /* this doesn't actually ever happen anymore (see checks above) */
568 segment_t*min = range->segmin;
569 segment_t*max = range->segmax;
570 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
573 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
579 void segrange_test_segment_min(segrange_t*range, segment_t*seg, int y)
582 /* we need to calculate the xpos anew (and can't use start coordinate or
583 intersection coordinate), because we need the xpos exactly at the end of
585 TODO: might be faster to use XPOS_COMPARE here (see also _max)
587 double x = XPOS(seg, y);
588 if(!range->segmin || x<range->xmin) {
593 void segrange_test_segment_max(segrange_t*range, segment_t*seg, int y)
596 double x = XPOS(seg, y);
597 if(!range->segmax || x>range->xmax) {
612 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
614 segment_t*first=0, *last = 0;
616 for(t=0;t<status->xrow->num;t++) {
617 box_t box = box_new(status->xrow->x[t], y);
618 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
620 seg = actlist_right(status->actlist, seg);
623 // this segment started in this scanline, ignore it
624 seg->changed = 1;last = seg;if(!first) {first=seg;}
625 } else if(seg->delta.x <= 0) {
626 // ignore segment w/ negative slope
628 last = seg;if(!first) {first=seg;}
629 double d1 = LINE_EQ(box.right1, seg);
630 double d2 = LINE_EQ(box.right2, seg);
633 insert_point_into_segment(status, seg, box.right2);
635 /* we unfortunately can't break here- the active list is sorted according
636 to the *bottom* of the scanline. hence pretty much everything that's still
637 coming might reach into our box */
641 seg = actlist_right(status->actlist, seg);
644 segrange_test_segment_min(range, first, y);
645 segrange_test_segment_max(range, last, y);
655 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
657 segment_t*first=0, *last = 0;
659 for(t=status->xrow->num-1;t>=0;t--) {
660 box_t box = box_new(status->xrow->x[t], y);
661 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
665 // this segment started in this scanline, ignore it
666 seg->changed = 1;last = seg;if(!first) {first=seg;}
667 } else if(seg->delta.x > 0) {
668 // ignore segment w/ positive slope
670 last = seg;if(!first) {first=seg;}
671 double d1 = LINE_EQ(box.left1, seg);
672 double d2 = LINE_EQ(box.left2, seg);
675 insert_point_into_segment(status, seg, box.right2);
680 seg = actlist_left(status->actlist, seg);
683 segrange_test_segment_min(range, last, y);
684 segrange_test_segment_max(range, first, y);
687 /* segments ending in the current scanline need xrow treatment like everything else.
688 (consider an intersection taking place just above a nearly horizontal segment
689 ending on the current scanline- the intersection would snap down *below* the
690 ending segment if we don't add the intersection point to the latter right away)
691 we need to treat ending segments seperately, however. we have to delete them from
692 the active list right away to make room for intersect operations (which might
693 still be in the current scanline- consider two 45° polygons and a vertical polygon
694 intersecting on an integer coordinate). but once they're no longer in the active list,
695 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
696 them to the active list just for point snapping would be overkill.
697 (One other option to consider, however, would be to create a new active list only
700 void add_points_to_ending_segments(status_t*status, int32_t y)
702 segment_t*seg = status->ending_segments;
704 segment_t*next = seg->right;seg->right=0;
706 assert(seg->b.y == status->y);
708 if(status->xrow->num == 1) {
710 point_t p = {status->xrow->x[0], y};
711 insert_point_into_segment(status, seg, p);
714 int start=0,end=status->xrow->num,dir=1;
715 if(seg->delta.x < 0) {
716 start = status->xrow->num-1;
719 for(t=start;t!=end;t+=dir) {
720 box_t box = box_new(status->xrow->x[t], y);
721 double d0 = LINE_EQ(box.left1, seg);
722 double d1 = LINE_EQ(box.left2, seg);
723 double d2 = LINE_EQ(box.right1, seg);
724 double d3 = LINE_EQ(box.right2, seg);
725 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
726 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
727 insert_point_into_segment(status, seg, box.right2);
733 /* we *need* to find a point to insert. the segment's own end point
734 is in that list, for Pete's sake. */
738 // now that this is done, too, we can also finally free this segment
739 segment_destroy(seg);
742 status->ending_segments = 0;
745 static void recalculate_windings(status_t*status, segrange_t*range)
747 segrange_adjust_endpoints(range, status->y);
749 segment_t*s = range->segmin;
750 segment_t*end = range->segmax;
754 s = actlist_leftmost(status->actlist);
756 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
757 s == range->segmin?"S":(
758 s == range->segmax?"E":""));
761 fprintf(stderr, "\n");
765 /* test sanity: check that we don't have changed segments
766 outside of the given range */
767 s = actlist_leftmost(status->actlist);
768 while(s && s!=range->segmin) {
772 s = actlist_rightmost(status->actlist);
773 while(s && s!=range->segmax) {
777 /* in check mode, go through the whole interval so we can test
778 that all polygons where the fillstyle changed also have seg->changed=1 */
779 s = actlist_leftmost(status->actlist);
784 end = actlist_right(status->actlist, end);
790 segment_t* left = actlist_left(status->actlist, s);
791 windstate_t wind = left?left->wind:status->windrule->start(status->num_polygons);
792 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
793 fillstyle_t*fs_old = s->fs_out;
794 s->fs_out = status->windrule->diff(&wind, &s->wind);
796 assert(!(!s->changed && fs_old!=s->fs_out));
801 fprintf(stderr, "[%d] %s/%d/%s/%s ", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit");
807 fprintf(stderr, "\n");
811 /* we need to handle horizontal lines in order to add points to segments
812 we otherwise would miss during the windrule re-evaluation */
813 void intersect_with_horizontal(status_t*status, segment_t*h)
815 segment_t* left = actlist_find(status->actlist, h->a, h->a);
816 segment_t* right = actlist_find(status->actlist, h->b, h->b);
818 /* not strictly necessary, also done by the event */
819 xrow_add(status->xrow, h->a.x);
827 left = actlist_right(status->actlist, left); //first seg to the right of h->a
828 right = right->right; //first seg to the right of h->b
833 int x = XPOS_INT(s, status->y);
835 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
843 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
844 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
845 xrow_add(status->xrow, x);
851 void event_apply(status_t*status, event_t*e)
854 case EVENT_HORIZONTAL: {
858 intersect_with_horizontal(status, e->s1);
859 segment_destroy(e->s1);e->s1=0;
863 //delete segment from list
869 dict_del(status->intersecting_segs, s);
870 dict_del(status->segs_with_point, s);
871 assert(!dict_contains(status->intersecting_segs, s));
872 assert(!dict_contains(status->segs_with_point, s));
874 segment_t*left = actlist_left(status->actlist, s);
875 segment_t*right = actlist_right(status->actlist, s);
876 actlist_delete(status->actlist, s);
878 schedule_crossing(status, left, right);
880 s->left = 0; s->right = status->ending_segments;
881 status->ending_segments = s;
885 //insert segment into list
890 assert(e->p.x == s->a.x && e->p.y == s->a.y);
891 actlist_insert(status->actlist, s->a, s->b, s);
892 segment_t*left = actlist_left(status->actlist, s);
893 segment_t*right = actlist_right(status->actlist, s);
895 schedule_crossing(status, left, s);
897 schedule_crossing(status, s, right);
898 schedule_endpoint(status, e->s1);
902 // exchange two segments
906 if(actlist_right(status->actlist, e->s1) == e->s2 &&
907 actlist_left(status->actlist, e->s2) == e->s1) {
908 exchange_two(status, e);
910 /* ignore this crossing for now (there are some line segments in between).
911 it'll get rescheduled as soon as the "obstacles" are gone */
912 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
913 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
914 assert(del1 && del2);
919 assert(dict_contains(status->seen_crossings, &pair));
920 dict_del(status->seen_crossings, &pair);
928 void check_status(status_t*status)
930 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
931 if((s->pos.x != s->b.x ||
932 s->pos.y != s->b.y) &&
933 !dict_contains(status->segs_with_point, s)) {
934 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
936 s->delta.x<0?"-":"+",
944 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
947 |..| |...........| | |
948 |..| |...........| | |
949 |..+ + +..| +--+ +--+
950 |...........| |..| | |
951 |...........| |..| | |
955 fprintf(stderr, "========================================================================\n");
957 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
958 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
960 actlist_t* actlist = actlist_new();
962 event_t*e = heap_chopmax(queue);
968 fprintf(stderr, "----------------------------------- %d\n", y);
969 actlist_dump(actlist, y-1);
972 /* FIXME: this actually fails sometimes */
973 actlist_verify(actlist, y-1);
976 if(fill && x != e->p.x) {
978 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
980 edge_t*l= malloc(sizeof(edge_t));
984 l->next = poly->edges;
990 windstate_t before,after;
993 assert(e->p.x == s->a.x && e->p.y == s->a.y);
994 actlist_insert(actlist, s->a, s->b, s);
1000 heap_put(queue, &e);
1001 left = actlist_left(actlist, s);
1003 before = left?left->wind:windrule->start(1);
1004 after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
1008 left = actlist_left(actlist, s);
1009 actlist_delete(actlist, s);
1012 after = left?left->wind:windrule->start(1);
1019 fill ^= 1;//(before.is_filled != after.is_filled);
1021 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
1022 y, e->type==EVENT_START?"start":"end",
1026 before.is_filled, after.is_filled);
1029 if(e->type == EVENT_END)
1033 e = heap_chopmax(queue);
1034 } while(e && y == e->p.y);
1036 assert(!fill); // check that polygon is not bleeding
1038 actlist_destroy(actlist);
1039 heap_destroy(queue);
1042 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
1044 current_polygon = poly;
1045 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1047 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
1050 memset(&status, 0, sizeof(status_t));
1051 status.num_polygons = 1;
1052 status.queue = queue;
1053 status.windrule = windrule;
1054 status.actlist = actlist_new();
1056 status.seen_crossings = dict_new2(&point_type);
1059 status.xrow = xrow_new();
1061 event_t*e = heap_chopmax(queue);
1065 status.intersecting_segs = dict_new2(&ptr_type);
1066 status.segs_with_point = dict_new2(&ptr_type);
1070 fprintf(stderr, "----------------------------------- %d\n", status.y);
1071 actlist_dump(status.actlist, status.y-1);
1074 actlist_verify(status.actlist, status.y-1);
1076 xrow_reset(status.xrow);
1078 xrow_add(status.xrow, e->p.x);
1079 event_apply(&status, e);
1081 e = heap_chopmax(queue);
1082 } while(e && status.y == e->p.y);
1084 xrow_sort(status.xrow);
1086 memset(&range, 0, sizeof(range));
1088 actlist_dump(status.actlist, status.y);
1090 add_points_to_positively_sloped_segments(&status, status.y, &range);
1091 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1092 add_points_to_ending_segments(&status, status.y);
1094 recalculate_windings(&status, &range);
1096 check_status(&status);
1097 dict_destroy(status.intersecting_segs);
1098 dict_destroy(status.segs_with_point);
1102 dict_destroy(status.seen_crossings);
1104 actlist_destroy(status.actlist);
1105 heap_destroy(queue);
1106 xrow_destroy(status.xrow);
1108 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1109 p->edges = status.output;
1111 add_horizontals(p, &windrule_evenodd); // output is always even/odd