23 char point_equals(const void*o1, const void*o2)
25 const point_t*p1 = o1;
26 const point_t*p2 = o2;
27 return p1->x == p2->x && p1->y == p2->y;
29 unsigned int point_hash(const void*o)
34 void* point_dup(const void*o)
37 point_t*n = malloc(sizeof(point_t));
42 void point_free(void*o)
56 typedef struct _status {
65 dict_t*seen_crossings; //list of crossing we saw so far
66 dict_t*intersecting_segs; //list of segments intersecting in this scanline
67 dict_t*segs_with_point; //lists of segments that received a point in this scanline
71 int compare_events_simple(const void*_a,const void*_b)
73 event_t* a = (event_t*)_a;
74 event_t* b = (event_t*)_b;
77 } else if(a->p.y > b->p.y) {
79 } else if(a->p.x < b->p.x) {
81 } else if(a->p.x > b->p.x) {
87 int compare_events(const void*_a,const void*_b)
89 event_t* a = (event_t*)_a;
90 event_t* b = (event_t*)_b;
91 int d = b->p.y - a->p.y;
93 /* we need to schedule end before intersect (so that a segment about
94 to end has a chance to tear up a few other segs first) and start
95 events after intersect (so that start segments don't position themselves
96 between two segments about to intersect (not a problem as such, but makes
97 things slower)). Horizontal lines come last, because the only purpose
98 they have is to create snapping coordinates for the segments (still)
99 existing in this scanline */
100 d = b->type - a->type;
106 gfxpoly_t* gfxpoly_new(double gridsize)
108 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
109 p->gridsize = gridsize;
112 void gfxpoly_destroy(gfxpoly_t*poly)
114 edge_t* s = poly->edges;
116 edge_t*next = s->next;
122 int gfxpoly_size(gfxpoly_t*poly)
124 edge_t* s = poly->edges;
131 char gfxpoly_check(gfxpoly_t*poly)
133 edge_t* s = poly->edges;
134 dict_t*d = dict_new2(&point_type);
136 if(!dict_contains(d, &s->a)) {
137 dict_put(d, &s->a, (void*)(ptroff_t)1);
139 int count = (ptroff_t)dict_lookup(d, &s->a);
142 dict_put(d, &s->a, (void*)(ptroff_t)count);
144 if(!dict_contains(d, &s->b)) {
145 dict_put(d, &s->b, (void*)(ptroff_t)1);
147 int count = (ptroff_t)dict_lookup(d, &s->b);
150 dict_put(d, &s->b, (void*)(ptroff_t)count);
154 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
155 int count = (ptroff_t)c;
157 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
164 void gfxpoly_dump(gfxpoly_t*poly)
166 edge_t* s = poly->edges;
167 double g = poly->gridsize;
169 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
174 inline static event_t event_new()
177 memset(&e, 0, sizeof(e));
181 void event_dump(event_t*e)
183 if(e->type == EVENT_HORIZONTAL) {
184 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);
185 } else if(e->type == EVENT_START) {
186 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
187 } else if(e->type == EVENT_END) {
188 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
189 } else if(e->type == EVENT_CROSS) {
190 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
196 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
197 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
199 void segment_dump(segment_t*s)
201 fprintf(stderr, "(%d,%d)->(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y);
202 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
203 (double)s->delta.x / s->delta.y);
206 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
211 int x = x1;x1=x2;x2=x;
212 int y = y1;y1=y2;y2=y;
215 /* up/down for horizontal segments is handled by "rotating"
216 them 90° anticlockwise in screen coordinates (tilt your head to
221 int x = x1;x1=x2;x2=x;
222 int y = y1;y1=y2;y2=y;
229 s->k = (double)x1*y2-(double)x2*y1;
230 s->left = s->right = 0;
233 s->minx = min32(x1,x2);
234 s->maxx = max32(x1,x2);
237 s->polygon_nr = polygon_nr;
240 static int segment_count=0;
241 s->nr = segment_count++;
244 assert(LINE_EQ(s->a, s) == 0);
245 assert(LINE_EQ(s->b, s) == 0);
247 /* check that all signs are in order:
255 p.x = min32(s->a.x, s->b.x);
256 assert(LINE_EQ(p, s) <= 0);
257 p.x = max32(s->a.x, s->b.x);
258 assert(LINE_EQ(p, s) >= 0);
260 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
263 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
265 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
266 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
269 void segment_destroy(segment_t*s)
271 dict_clear(&s->scheduled_crossings);
275 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
278 for(l=list;l;l=l->next) {
279 if(l->a.x == l->b.x &&
281 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
284 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
288 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
289 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
290 s->dir==DIR_UP?"up":"down");
292 event_t e = event_new();
293 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
301 void schedule_endpoint(status_t*status, segment_t*s)
303 // schedule end point of segment
304 assert(s->b.y > status->y);
310 heap_put(status->queue, &e);
313 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
315 /* the code that's required (and the checks you can perform) before
316 it can be said with 100% certainty that we indeed have a valid crossing
317 amazes me every time. -mk */
321 assert(s1->right == s2);
322 assert(s2->left == s1);
323 int32_t miny1 = min32(s1->a.y,s1->b.y);
324 int32_t maxy1 = max32(s1->a.y,s1->b.y);
325 int32_t miny2 = min32(s2->a.y,s2->b.y);
326 int32_t maxy2 = max32(s2->a.y,s2->b.y);
327 int32_t minx1 = min32(s1->a.x,s1->b.x);
328 int32_t minx2 = min32(s2->a.x,s2->b.x);
329 int32_t maxx1 = max32(s1->a.x,s1->b.x);
330 int32_t maxx2 = max32(s2->a.x,s2->b.x);
331 /* check that precomputation is sane */
332 assert(minx1 == s1->minx && minx2 == s2->minx);
333 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
334 /* both segments are active, so this can't happen */
335 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
336 /* we know that right now, s2 is to the right of s1, so there's
337 no way the complete bounding box of s1 is to the right of s1 */
338 assert(!(s1->minx > s2->maxx));
339 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
342 if(s1->maxx <= s2->minx) {
343 /* bounding boxes don't intersect */
347 if(dict_contains(&s1->scheduled_crossings, s2)) {
348 /* FIXME: this whole segment hashing thing is really slow */
349 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
350 return; // we already know about this one
353 double adx = s1->delta.x;
354 double ady = s1->delta.y;
355 double bdx = s2->delta.x;
356 double bdy = s2->delta.y;
357 double det = adx*bdy - ady*bdx;
360 // lines are exactly on top of each other (ignored)
362 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
366 /* lines are parallel */
370 double asign2 = LINE_EQ(s1->a, s2);
371 double bsign2 = LINE_EQ(s1->b, s2);
372 if(asign2<0 && bsign2<0) {
373 // segment1 is completely to the left of segment2
376 if(asign2>0 && bsign2>0) {
377 // segment2 is completely to the left of segment1
381 // segment1 touches segment2 in a single point (ignored)
383 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
388 // segment1 touches segment2 in a single point (ignored)
390 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
394 double asign1 = LINE_EQ(s2->a, s1);
395 double bsign1 = LINE_EQ(s2->b, s1);
396 if(asign1<0 && bsign1<0) {
397 // segment1 is completely to the left of segment2
400 if(asign1>0 && bsign1>0) {
401 // segment2 is completely to the left of segment1
405 // segment2 touches segment1 in a single point (ignored)
407 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
412 // segment2 touches segment1 in a single point (ignored)
414 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
419 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
420 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
423 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
424 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
426 assert(p.y >= status->y);
428 assert(p.x >= s1->minx && p.x <= s1->maxx);
429 assert(p.x >= s2->minx && p.x <= s2->maxx);
434 assert(!dict_contains(status->seen_crossings, &pair));
435 dict_put(status->seen_crossings, &pair, 0);
438 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
441 /* we insert into each other's intersection history because these segments might switch
442 places and we still want to look them up quickly after they did */
443 dict_put(&s1->scheduled_crossings, s2, 0);
444 dict_put(&s2->scheduled_crossings, s1, 0);
446 event_t e = event_new();
447 e.type = EVENT_CROSS;
451 heap_put(status->queue, &e);
455 void exchange_two(status_t*status, event_t*e)
457 //exchange two segments in list
458 segment_t*s1 = e->s1;
459 segment_t*s2 = e->s2;
461 if(!dict_contains(status->intersecting_segs, s1))
462 dict_put(status->intersecting_segs, s1, 0);
463 if(!dict_contains(status->intersecting_segs, s2))
464 dict_put(status->intersecting_segs, s2, 0);
466 segment_t*left = actlist_left(status->actlist, s2);
467 segment_t*right = actlist_right(status->actlist, s1);
470 actlist_swap(status->actlist, s1, s2);
471 assert(actlist_right(status->actlist, s2) == s1);
472 assert(actlist_left(status->actlist, s1) == s2);
473 left = actlist_left(status->actlist, s2);
474 right = actlist_right(status->actlist, s1);
476 schedule_crossing(status, left, s2);
478 schedule_crossing(status, s1, right);
481 typedef struct _box {
482 point_t left1, left2, right1, right2;
484 static inline box_t box_new(int x, int y)
487 box.right1.x = box.right2.x = x;
488 box.left1.x = box.left2.x = x-1;
489 box.left1.y = box.right1.y = y-1;
490 box.left2.y = box.right2.y = y;
495 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
497 assert(s->pos.x != p.x || s->pos.y != p.y);
500 if(!dict_contains(status->segs_with_point, s))
501 dict_put(status->segs_with_point, s, 0);
502 assert(s->fs_out_ok);
507 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
508 s->pos.x, s->pos.y, p.x, p.y);
510 // omit horizontal lines
511 if(s->pos.y != p.y) {
512 edge_t*e = rfx_calloc(sizeof(edge_t));
516 assert(e->a.y != e->b.y);
517 e->next = status->output;
522 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
528 /* by restricting the recalculation of line segments to a range between the lowest
529 and the highest modified segment, we only do about a 33% overprocessing of fill
530 styles. (update: that statistic might be outdated now that xmin/xmax are double) */
531 typedef struct _segrange {
538 static inline char xpos_eq(segment_t*s1, segment_t*s2, int y)
540 if(XPOS_EQ(s1, s2, y)) {
546 void segrange_adjust_endpoints(segrange_t*range, int y)
549 /* this would mean that the segment left/right of the minimum/maximum
550 intersects the current segment exactly at the scanline, but somehow
551 wasn't found to be passing through the same snapping box */
552 assert(!min || !min->left || !XPOS_EQ(min, min->left, y));
553 assert(!max || !max->right || !XPOS_EQ(max, max->right, y));
556 segment_t*min = range->segmin;
557 segment_t*max = range->segmax;
558 if(min) while(min->left && xpos_eq(min, min->left, y)) {
561 if(max) while(max->right && xpos_eq(max, max->right, y)) {
567 void segrange_test_segment_min(segrange_t*range, segment_t*seg, int y)
570 /* we need to calculate the xpos anew (and can't use start coordinate or
571 intersection coordinate), because we need the xpos exactly at the end of
573 TODO: might be faster to use XPOS_COMPARE here (see also _max)
575 double x = XPOS(seg, y);
576 if(!range->segmin || x<range->xmin) {
581 void segrange_test_segment_max(segrange_t*range, segment_t*seg, int y)
584 double x = XPOS(seg, y);
585 if(!range->segmax || x>range->xmax) {
600 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
602 segment_t*first=0, *last = 0;
604 for(t=0;t<status->xrow->num;t++) {
605 box_t box = box_new(status->xrow->x[t], y);
606 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
607 seg = actlist_right(status->actlist, seg);
611 // this segment started in this scanline, ignore it
612 seg->changed = 1;last = seg;if(!first) {first=seg;}
613 } else if(seg->delta.x < 0) {
614 // ignore segment w/ negative slope
616 double d1 = LINE_EQ(box.right1, seg);
617 double d2 = LINE_EQ(box.right2, seg);
619 seg->changed = 1;last = seg;if(!first) {first=seg;}
620 insert_point_into_segment(status, seg, box.right2);
625 seg = actlist_right(status->actlist, seg);
628 segrange_test_segment_min(range, first, y);
629 segrange_test_segment_max(range, last, y);
639 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
641 segment_t*first=0, *last = 0;
644 for(t=status->xrow->num-1;t>=0;t--) {
645 box_t box = box_new(status->xrow->x[t], y);
646 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
650 // this segment started in this scanline, ignore it
651 seg->changed = 1;last = seg;if(!first) {first=seg;}
652 if(!first) {first=seg; firstx = seg->a.x;}
653 } else if(seg->delta.x >= 0) {
654 // ignore segment w/ positive slope
656 double d1 = LINE_EQ(box.left1, seg);
657 double d2 = LINE_EQ(box.left2, seg);
659 seg->changed = 1;last = seg;if(!first) {first=seg;}
660 insert_point_into_segment(status, seg, box.right2);
665 seg = actlist_left(status->actlist, seg);
668 segrange_test_segment_min(range, last, y);
669 segrange_test_segment_max(range, first, y);
672 static void recalculate_windings(status_t*status, segrange_t*range)
674 segrange_adjust_endpoints(range, status->y);
676 segment_t*s = range->segmin;
677 segment_t*end = range->segmax;
681 /* test sanity: check that we don't have changed segments
682 outside of the given range */
683 s = actlist_leftmost(status->actlist);
684 while(s && s!=range->segmin) {
686 s = actlist_right(status->actlist, s);
688 s = actlist_rightmost(status->actlist);
689 while(s && s!=range->segmax) {
691 s = actlist_left(status->actlist, s);
693 /* in check mode, go through the whole interval so we can test
694 that all polygons where the fillstyle changed also have seg->changed=1 */
695 s = actlist_leftmost(status->actlist);
700 end = actlist_right(status->actlist, end);
706 segment_t* left = actlist_left(status->actlist, s);
707 windstate_t wind = left?left->wind:status->windrule->start(status->num_polygons);
708 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
709 fillstyle_t*fs_old = s->fs_out;
710 s->fs_out = status->windrule->diff(&wind, &s->wind);
712 assert(!(!s->changed && fs_old!=s->fs_out));
717 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");
720 s = actlist_right(status->actlist, s);
723 fprintf(stderr, "\n");
727 /* we need to handle horizontal lines in order to add points to segments
728 we otherwise would miss during the windrule re-evaluation */
729 void intersect_with_horizontal(status_t*status, segment_t*h)
731 segment_t* left = actlist_find(status->actlist, h->a, h->a);
732 segment_t* right = actlist_find(status->actlist, h->b, h->b);
734 /* not strictly necessary, also done by the event */
735 xrow_add(status->xrow, h->a.x);
738 left = actlist_right(status->actlist, left);
739 right = actlist_right(status->actlist, right);
744 int x = XPOS_INT(s, status->y);
746 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
754 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
755 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
756 xrow_add(status->xrow, x);
758 s = actlist_right(status->actlist, s);
762 void event_apply(status_t*status, event_t*e)
765 case EVENT_HORIZONTAL: {
769 intersect_with_horizontal(status, e->s1);
770 segment_destroy(e->s1);e->s1=0;
774 //delete segment from list
780 dict_del(status->intersecting_segs, s);
781 dict_del(status->segs_with_point, s);
782 assert(!dict_contains(status->intersecting_segs, s));
783 assert(!dict_contains(status->segs_with_point, s));
785 insert_point_into_segment(status, s, s->b);
786 segment_t*left = actlist_left(status->actlist, s);
787 segment_t*right = actlist_right(status->actlist, s);
788 actlist_delete(status->actlist, s);
790 schedule_crossing(status, left, right);
791 segment_destroy(s);e->s1=0;
795 //insert segment into list
800 actlist_insert(status->actlist, e->p, s);
801 segment_t*left = actlist_left(status->actlist, s);
802 segment_t*right = actlist_right(status->actlist, s);
804 schedule_crossing(status, left, s);
806 schedule_crossing(status, s, right);
807 schedule_endpoint(status, e->s1);
811 // exchange two segments
815 if(actlist_right(status->actlist, e->s1) == e->s2 &&
816 actlist_left(status->actlist, e->s2) == e->s1) {
817 exchange_two(status, e);
819 /* ignore this crossing for now (there are some line segments in between).
820 it'll get rescheduled as soon as the "obstacles" are gone */
821 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
822 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
823 assert(del1 && del2);
828 assert(dict_contains(status->seen_crossings, &pair));
829 dict_del(status->seen_crossings, &pair);
837 void check_status(status_t*status)
839 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
840 if((s->pos.x != s->b.x ||
841 s->pos.y != s->b.y) &&
842 !dict_contains(status->segs_with_point, s)) {
843 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
845 s->delta.x<0?"-":"+",
853 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
856 |..| |...........| | |
857 |..| |...........| | |
858 |..+ + +..| +--+ +--+
859 |...........| |..| | |
860 |...........| |..| | |
864 fprintf(stderr, "========================================================================\n");
866 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
867 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
869 actlist_t* actlist = actlist_new();
871 event_t*e = heap_chopmax(queue);
877 fprintf(stderr, "----------------------------------- %d\n", y);
878 actlist_dump(actlist, y-1);
881 /* FIXME: this actually fails sometimes */
882 actlist_verify(actlist, y-1);
885 if(fill && x != e->p.x) {
887 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
889 edge_t*l= malloc(sizeof(edge_t));
893 l->next = poly->edges;
899 windstate_t before,after;
902 actlist_insert(actlist, e->p, s);
909 left = actlist_left(actlist, s);
911 before = left?left->wind:windrule->start(1);
912 after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
916 left = actlist_left(actlist, s);
917 actlist_delete(actlist, s);
920 after = left?left->wind:windrule->start(1);
927 fill ^= 1;//(before.is_filled != after.is_filled);
929 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
930 y, e->type==EVENT_START?"start":"end",
934 before.is_filled, after.is_filled);
937 if(e->type == EVENT_END)
941 e = heap_chopmax(queue);
942 } while(e && y == e->p.y);
944 assert(!fill); // check that polygon is not bleeding
946 actlist_destroy(actlist);
950 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
952 heap_t* queue = heap_new(sizeof(event_t), compare_events);
954 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
957 memset(&status, 0, sizeof(status_t));
958 status.num_polygons = 1;
959 status.queue = queue;
960 status.windrule = windrule;
961 status.actlist = actlist_new();
963 status.seen_crossings = dict_new2(&point_type);
966 status.xrow = xrow_new();
968 event_t*e = heap_chopmax(queue);
972 status.intersecting_segs = dict_new2(&ptr_type);
973 status.segs_with_point = dict_new2(&ptr_type);
977 fprintf(stderr, "----------------------------------- %d\n", status.y);
978 actlist_dump(status.actlist, status.y-1);
981 actlist_verify(status.actlist, status.y-1);
983 xrow_reset(status.xrow);
985 xrow_add(status.xrow, e->p.x);
986 event_apply(&status, e);
988 e = heap_chopmax(queue);
989 } while(e && status.y == e->p.y);
991 xrow_sort(status.xrow);
993 memset(&range, 0, sizeof(range));
994 add_points_to_positively_sloped_segments(&status, status.y, &range);
995 add_points_to_negatively_sloped_segments(&status, status.y, &range);
996 recalculate_windings(&status, &range);
998 check_status(&status);
999 dict_destroy(status.intersecting_segs);
1000 dict_destroy(status.segs_with_point);
1004 dict_destroy(status.seen_crossings);
1006 actlist_destroy(status.actlist);
1007 heap_destroy(queue);
1008 xrow_destroy(status.xrow);
1010 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1011 p->edges = status.output;
1013 add_horizontals(p, &windrule_evenodd); // output is always even/odd