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 /* compare_events_simple differs from compare_events in that it schedules
71 events from left to right regardless of type. It's only used in horizontal
72 processing, in order to get an x-wise sorting of the current scanline */
73 static int compare_events_simple(const void*_a,const void*_b)
75 event_t* a = (event_t*)_a;
76 event_t* b = (event_t*)_b;
79 } else if(a->p.y > b->p.y) {
81 } else if(a->p.x < b->p.x) {
83 } else if(a->p.x > b->p.x) {
89 static int compare_events(const void*_a,const void*_b)
91 event_t* a = (event_t*)_a;
92 event_t* b = (event_t*)_b;
93 int d = b->p.y - a->p.y;
95 /* we need to schedule end before intersect (so that a segment about
96 to end has a chance to tear up a few other segs first) and start
97 events after intersect (so that start segments don't position themselves
98 between two segments about to intersect (not a problem as such, but makes
99 things slower)). Horizontal lines come last, because the only purpose
100 they have is to create snapping coordinates for the segments (still)
101 existing in this scanline */
102 d = b->type - a->type;
108 gfxpoly_t* gfxpoly_new(double gridsize)
110 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
111 p->gridsize = gridsize;
114 void gfxpoly_destroy(gfxpoly_t*poly)
116 edge_t* s = poly->edges;
118 edge_t*next = s->next;
124 int gfxpoly_size(gfxpoly_t*poly)
126 edge_t* s = poly->edges;
133 char gfxpoly_check(gfxpoly_t*poly)
135 edge_t* s = poly->edges;
136 dict_t*d = dict_new2(&point_type);
138 if(!dict_contains(d, &s->a)) {
139 dict_put(d, &s->a, (void*)(ptroff_t)1);
141 int count = (ptroff_t)dict_lookup(d, &s->a);
144 dict_put(d, &s->a, (void*)(ptroff_t)count);
146 if(!dict_contains(d, &s->b)) {
147 dict_put(d, &s->b, (void*)(ptroff_t)1);
149 int count = (ptroff_t)dict_lookup(d, &s->b);
152 dict_put(d, &s->b, (void*)(ptroff_t)count);
156 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
157 int count = (ptroff_t)c;
159 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
168 void gfxpoly_dump(gfxpoly_t*poly)
170 edge_t* s = poly->edges;
171 double g = poly->gridsize;
173 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
178 gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename)
180 FILE*fi = fopen(filename, "wb");
181 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
182 fprintf(fi, "%% begin\n");
183 edge_t* s = poly->edges;
185 fprintf(fi, "%g setgray\n", s->b.y < s->a.y ? 0.7 : 0);
186 fprintf(fi, "%d %d moveto\n", s->a.x, s->a.y);
187 fprintf(fi, "%d %d lineto\n", s->b.x, s->b.y);
188 fprintf(fi, "stroke\n");
191 fprintf(fi, "showpage\n");
195 inline static event_t event_new()
198 memset(&e, 0, sizeof(e));
202 void event_dump(event_t*e)
204 if(e->type == EVENT_HORIZONTAL) {
205 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);
206 } else if(e->type == EVENT_START) {
207 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
208 } else if(e->type == EVENT_END) {
209 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
210 } else if(e->type == EVENT_CROSS) {
211 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
217 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
218 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
220 void segment_dump(segment_t*s)
222 fprintf(stderr, "(%d,%d)->(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y);
223 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
224 (double)s->delta.x / s->delta.y);
227 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
232 int x = x1;x1=x2;x2=x;
233 int y = y1;y1=y2;y2=y;
236 /* up/down for horizontal segments is handled by "rotating"
237 them 90° anticlockwise in screen coordinates (tilt your head to
242 int x = x1;x1=x2;x2=x;
243 int y = y1;y1=y2;y2=y;
250 s->k = (double)x1*y2-(double)x2*y1;
251 s->left = s->right = 0;
254 s->minx = min32(x1,x2);
255 s->maxx = max32(x1,x2);
258 s->polygon_nr = polygon_nr;
261 static int segment_count=0;
262 s->nr = segment_count++;
265 assert(LINE_EQ(s->a, s) == 0);
266 assert(LINE_EQ(s->b, s) == 0);
268 /* check that all signs are in order:
276 p.x = min32(s->a.x, s->b.x);
277 assert(LINE_EQ(p, s) <= 0);
278 p.x = max32(s->a.x, s->b.x);
279 assert(LINE_EQ(p, s) >= 0);
281 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
284 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
286 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
287 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
290 void segment_destroy(segment_t*s)
292 dict_clear(&s->scheduled_crossings);
296 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
299 for(l=list;l;l=l->next) {
300 if(l->a.x == l->b.x &&
302 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
305 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
309 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
310 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
311 s->dir==DIR_UP?"up":"down");
313 event_t e = event_new();
314 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
322 void schedule_endpoint(status_t*status, segment_t*s)
324 // schedule end point of segment
325 assert(s->b.y > status->y);
331 heap_put(status->queue, &e);
334 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
336 /* the code that's required (and the checks you can perform) before
337 it can be said with 100% certainty that we indeed have a valid crossing
338 amazes me every time. -mk */
342 assert(s1->right == s2);
343 assert(s2->left == s1);
344 int32_t miny1 = min32(s1->a.y,s1->b.y);
345 int32_t maxy1 = max32(s1->a.y,s1->b.y);
346 int32_t miny2 = min32(s2->a.y,s2->b.y);
347 int32_t maxy2 = max32(s2->a.y,s2->b.y);
348 int32_t minx1 = min32(s1->a.x,s1->b.x);
349 int32_t minx2 = min32(s2->a.x,s2->b.x);
350 int32_t maxx1 = max32(s1->a.x,s1->b.x);
351 int32_t maxx2 = max32(s2->a.x,s2->b.x);
352 /* check that precomputation is sane */
353 assert(minx1 == s1->minx && minx2 == s2->minx);
354 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
355 /* both segments are active, so this can't happen */
356 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
357 /* we know that right now, s2 is to the right of s1, so there's
358 no way the complete bounding box of s1 is to the right of s1 */
359 assert(!(s1->minx > s2->maxx));
360 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
363 if(s1->maxx <= s2->minx) {
364 /* bounding boxes don't intersect */
368 if(dict_contains(&s1->scheduled_crossings, s2)) {
369 /* FIXME: this whole segment hashing thing is really slow */
370 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
371 return; // we already know about this one
374 double adx = s1->delta.x;
375 double ady = s1->delta.y;
376 double bdx = s2->delta.x;
377 double bdy = s2->delta.y;
378 double det = adx*bdy - ady*bdx;
381 // lines are exactly on top of each other (ignored)
383 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
387 /* lines are parallel */
391 double asign2 = LINE_EQ(s1->a, s2);
392 double bsign2 = LINE_EQ(s1->b, s2);
393 if(asign2<0 && bsign2<0) {
394 // segment1 is completely to the left of segment2
397 if(asign2>0 && bsign2>0) {
398 // segment2 is completely to the left of segment1
402 // segment1 touches segment2 in a single point (ignored)
404 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
409 // segment1 touches segment2 in a single point (ignored)
411 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
415 double asign1 = LINE_EQ(s2->a, s1);
416 double bsign1 = LINE_EQ(s2->b, s1);
417 if(asign1<0 && bsign1<0) {
418 // segment1 is completely to the left of segment2
421 if(asign1>0 && bsign1>0) {
422 // segment2 is completely to the left of segment1
426 // segment2 touches segment1 in a single point (ignored)
428 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
433 // segment2 touches segment1 in a single point (ignored)
435 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
440 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
441 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
444 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
445 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
447 assert(p.y >= status->y);
449 assert(p.x >= s1->minx && p.x <= s1->maxx);
450 assert(p.x >= s2->minx && p.x <= s2->maxx);
455 assert(!dict_contains(status->seen_crossings, &pair));
456 dict_put(status->seen_crossings, &pair, 0);
459 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
462 /* we insert into each other's intersection history because these segments might switch
463 places and we still want to look them up quickly after they did */
464 dict_put(&s1->scheduled_crossings, s2, 0);
465 dict_put(&s2->scheduled_crossings, s1, 0);
467 event_t e = event_new();
468 e.type = EVENT_CROSS;
472 heap_put(status->queue, &e);
476 void exchange_two(status_t*status, event_t*e)
478 //exchange two segments in list
479 segment_t*s1 = e->s1;
480 segment_t*s2 = e->s2;
482 if(!dict_contains(status->intersecting_segs, s1))
483 dict_put(status->intersecting_segs, s1, 0);
484 if(!dict_contains(status->intersecting_segs, s2))
485 dict_put(status->intersecting_segs, s2, 0);
487 segment_t*left = actlist_left(status->actlist, s2);
488 segment_t*right = actlist_right(status->actlist, s1);
491 actlist_swap(status->actlist, s1, s2);
492 assert(actlist_right(status->actlist, s2) == s1);
493 assert(actlist_left(status->actlist, s1) == s2);
494 left = actlist_left(status->actlist, s2);
495 right = actlist_right(status->actlist, s1);
497 schedule_crossing(status, left, s2);
499 schedule_crossing(status, s1, right);
502 typedef struct _box {
503 point_t left1, left2, right1, right2;
505 static inline box_t box_new(int x, int y)
508 box.right1.x = box.right2.x = x;
509 box.left1.x = box.left2.x = x-1;
510 box.left1.y = box.right1.y = y-1;
511 box.left2.y = box.right2.y = y;
516 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
518 assert(s->pos.x != p.x || s->pos.y != p.y);
521 if(!dict_contains(status->segs_with_point, s))
522 dict_put(status->segs_with_point, s, 0);
523 assert(s->fs_out_ok);
528 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
529 s->pos.x, s->pos.y, p.x, p.y);
531 // omit horizontal lines
532 if(s->pos.y != p.y) {
533 edge_t*e = rfx_calloc(sizeof(edge_t));
539 assert(e->a.y != e->b.y);
540 e->next = status->output;
545 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
551 typedef struct _segrange {
558 void segrange_adjust_endpoints(segrange_t*range, int y)
560 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
562 /* this would mean that the segment left/right of the minimum/maximum
563 intersects the current segment exactly at the scanline, but somehow
564 wasn't found to be passing through the same snapping box */
565 assert(!min || !min->left || !XPOS_EQ(min, min->left, y));
566 assert(!max || !max->right || !XPOS_EQ(max, max->right, y));
569 /* this doesn't actually ever happen anymore (see checks above) */
570 segment_t*min = range->segmin;
571 segment_t*max = range->segmax;
572 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
575 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
581 void segrange_test_segment_min(segrange_t*range, segment_t*seg, int y)
584 /* we need to calculate the xpos anew (and can't use start coordinate or
585 intersection coordinate), because we need the xpos exactly at the end of
587 TODO: might be faster to use XPOS_COMPARE here (see also _max)
589 double x = XPOS(seg, y);
590 if(!range->segmin || x<range->xmin) {
595 void segrange_test_segment_max(segrange_t*range, segment_t*seg, int y)
598 double x = XPOS(seg, y);
599 if(!range->segmax || x>range->xmax) {
614 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
616 segment_t*first=0, *last = 0;
618 for(t=0;t<status->xrow->num;t++) {
619 box_t box = box_new(status->xrow->x[t], y);
620 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
622 seg = actlist_right(status->actlist, seg);
625 // this segment started in this scanline, ignore it
626 seg->changed = 1;last = seg;if(!first) {first=seg;}
627 } else if(seg->delta.x <= 0) {
628 // ignore segment w/ negative slope
630 last = seg;if(!first) {first=seg;}
631 double d1 = LINE_EQ(box.right1, seg);
632 double d2 = LINE_EQ(box.right2, seg);
635 insert_point_into_segment(status, seg, box.right2);
637 /* we unfortunately can't break here- the active list is sorted according
638 to the *bottom* of the scanline. hence pretty much everything that's still
639 coming might reach into our box */
643 seg = actlist_right(status->actlist, seg);
646 segrange_test_segment_min(range, first, y);
647 segrange_test_segment_max(range, last, y);
657 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
659 segment_t*first=0, *last = 0;
661 for(t=status->xrow->num-1;t>=0;t--) {
662 box_t box = box_new(status->xrow->x[t], y);
663 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
667 // this segment started in this scanline, ignore it
668 seg->changed = 1;last = seg;if(!first) {first=seg;}
669 } else if(seg->delta.x > 0) {
670 // ignore segment w/ positive slope
672 last = seg;if(!first) {first=seg;}
673 double d1 = LINE_EQ(box.left1, seg);
674 double d2 = LINE_EQ(box.left2, seg);
677 insert_point_into_segment(status, seg, box.right2);
682 seg = actlist_left(status->actlist, seg);
685 segrange_test_segment_min(range, last, y);
686 segrange_test_segment_max(range, first, y);
689 /* segments ending in the current scanline need xrow treatment like everything else.
690 (consider an intersection taking place just above a nearly horizontal segment
691 ending on the current scanline- the intersection would snap down *below* the
692 ending segment if we don't add the intersection point to the latter right away)
693 we need to treat ending segments seperately, however. we have to delete them from
694 the active list right away to make room for intersect operations (which might
695 still be in the current scanline- consider two 45° polygons and a vertical polygon
696 intersecting on an integer coordinate). but once they're no longer in the active list,
697 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
698 them to the active list just for point snapping would be overkill.
699 (One other option to consider, however, would be to create a new active list only
702 void add_points_to_ending_segments(status_t*status, int32_t y)
704 segment_t*seg = status->ending_segments;
706 segment_t*next = seg->right;seg->right=0;
708 assert(seg->b.y == status->y);
710 if(status->xrow->num == 1) {
712 point_t p = {status->xrow->x[0], y};
713 insert_point_into_segment(status, seg, p);
716 int start=0,end=status->xrow->num,dir=1;
717 if(seg->delta.x < 0) {
718 start = status->xrow->num-1;
721 for(t=start;t!=end;t+=dir) {
722 box_t box = box_new(status->xrow->x[t], y);
723 double d0 = LINE_EQ(box.left1, seg);
724 double d1 = LINE_EQ(box.left2, seg);
725 double d2 = LINE_EQ(box.right1, seg);
726 double d3 = LINE_EQ(box.right2, seg);
727 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
728 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
729 insert_point_into_segment(status, seg, box.right2);
735 /* we *need* to find a point to insert. the segment's own end point
736 is in that list, for Pete's sake. */
740 // now that this is done, too, we can also finally free this segment
741 segment_destroy(seg);
744 status->ending_segments = 0;
747 static void recalculate_windings(status_t*status, segrange_t*range)
749 segrange_adjust_endpoints(range, status->y);
751 segment_t*s = range->segmin;
752 segment_t*end = range->segmax;
756 s = actlist_leftmost(status->actlist);
758 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
759 s == range->segmin?"S":(
760 s == range->segmax?"E":""));
763 fprintf(stderr, "\n");
767 /* test sanity: check that we don't have changed segments
768 outside of the given range */
769 s = actlist_leftmost(status->actlist);
770 while(s && s!=range->segmin) {
774 s = actlist_rightmost(status->actlist);
775 while(s && s!=range->segmax) {
779 /* in check mode, go through the whole interval so we can test
780 that all polygons where the fillstyle changed also have seg->changed=1 */
781 s = actlist_leftmost(status->actlist);
786 end = actlist_right(status->actlist, end);
792 segment_t* left = actlist_left(status->actlist, s);
793 windstate_t wind = left?left->wind:status->windrule->start(status->num_polygons);
794 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
795 fillstyle_t*fs_old = s->fs_out;
796 s->fs_out = status->windrule->diff(&wind, &s->wind);
798 assert(!(!s->changed && fs_old!=s->fs_out));
803 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");
809 fprintf(stderr, "\n");
813 /* we need to handle horizontal lines in order to add points to segments
814 we otherwise would miss during the windrule re-evaluation */
815 void intersect_with_horizontal(status_t*status, segment_t*h)
817 segment_t* left = actlist_find(status->actlist, h->a, h->a);
818 segment_t* right = actlist_find(status->actlist, h->b, h->b);
820 /* not strictly necessary, also done by the event */
821 xrow_add(status->xrow, h->a.x);
829 left = actlist_right(status->actlist, left); //first seg to the right of h->a
830 right = right->right; //first seg to the right of h->b
835 int x = XPOS_INT(s, status->y);
837 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
845 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
846 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
847 xrow_add(status->xrow, x);
853 void event_apply(status_t*status, event_t*e)
856 case EVENT_HORIZONTAL: {
860 intersect_with_horizontal(status, e->s1);
861 segment_destroy(e->s1);e->s1=0;
865 //delete segment from list
871 dict_del(status->intersecting_segs, s);
872 dict_del(status->segs_with_point, s);
873 assert(!dict_contains(status->intersecting_segs, s));
874 assert(!dict_contains(status->segs_with_point, s));
876 segment_t*left = actlist_left(status->actlist, s);
877 segment_t*right = actlist_right(status->actlist, s);
878 actlist_delete(status->actlist, s);
880 schedule_crossing(status, left, right);
882 s->left = 0; s->right = status->ending_segments;
883 status->ending_segments = s;
887 //insert segment into list
892 assert(e->p.x == s->a.x && e->p.y == s->a.y);
893 actlist_insert(status->actlist, s->a, s->b, s);
894 segment_t*left = actlist_left(status->actlist, s);
895 segment_t*right = actlist_right(status->actlist, s);
897 schedule_crossing(status, left, s);
899 schedule_crossing(status, s, right);
900 schedule_endpoint(status, e->s1);
904 // exchange two segments
908 if(actlist_right(status->actlist, e->s1) == e->s2 &&
909 actlist_left(status->actlist, e->s2) == e->s1) {
910 exchange_two(status, e);
912 /* ignore this crossing for now (there are some line segments in between).
913 it'll get rescheduled as soon as the "obstacles" are gone */
914 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
915 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
916 assert(del1 && del2);
921 assert(dict_contains(status->seen_crossings, &pair));
922 dict_del(status->seen_crossings, &pair);
930 void check_status(status_t*status)
932 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
933 if((s->pos.x != s->b.x ||
934 s->pos.y != s->b.y) &&
935 !dict_contains(status->segs_with_point, s)) {
936 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
938 s->delta.x<0?"-":"+",
946 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
949 |..| |...........| | |
950 |..| |...........| | |
951 |..+ + +..| +--+ +--+
952 |...........| |..| | |
953 |...........| |..| | |
957 fprintf(stderr, "========================================================================\n");
959 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
960 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
962 actlist_t* actlist = actlist_new();
964 event_t*e = heap_chopmax(queue);
970 fprintf(stderr, "----------------------------------- %d\n", y);
971 actlist_dump(actlist, y-1);
974 actlist_verify(actlist, y-1);
977 if(fill && x != e->p.x) {
979 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
981 edge_t*l= malloc(sizeof(edge_t));
985 l->next = poly->edges;
991 windstate_t before,after;
994 assert(e->p.x == s->a.x && e->p.y == s->a.y);
995 actlist_insert(actlist, s->a, s->b, s);
1001 heap_put(queue, &e);
1002 left = actlist_left(actlist, s);
1004 before = left?left->wind:windrule->start(1);
1005 after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
1009 left = actlist_left(actlist, s);
1010 actlist_delete(actlist, s);
1013 after = left?left->wind:windrule->start(1);
1020 fill ^= 1;//(before.is_filled != after.is_filled);
1022 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
1023 y, e->type==EVENT_START?"start":"end",
1027 before.is_filled, after.is_filled);
1030 if(e->type == EVENT_END)
1034 e = heap_chopmax(queue);
1035 } while(e && y == e->p.y);
1037 assert(!fill); // check that polygon is not bleeding
1039 actlist_destroy(actlist);
1040 heap_destroy(queue);
1043 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
1045 current_polygon = poly;
1046 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1048 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
1051 memset(&status, 0, sizeof(status_t));
1052 status.num_polygons = 1;
1053 status.queue = queue;
1054 status.windrule = windrule;
1055 status.actlist = actlist_new();
1057 status.seen_crossings = dict_new2(&point_type);
1060 status.xrow = xrow_new();
1062 event_t*e = heap_chopmax(queue);
1066 status.intersecting_segs = dict_new2(&ptr_type);
1067 status.segs_with_point = dict_new2(&ptr_type);
1071 fprintf(stderr, "----------------------------------- %d\n", status.y);
1072 actlist_dump(status.actlist, status.y-1);
1075 actlist_verify(status.actlist, status.y-1);
1077 xrow_reset(status.xrow);
1079 xrow_add(status.xrow, e->p.x);
1080 event_apply(&status, e);
1082 e = heap_chopmax(queue);
1083 } while(e && status.y == e->p.y);
1085 xrow_sort(status.xrow);
1087 memset(&range, 0, sizeof(range));
1089 actlist_dump(status.actlist, status.y);
1091 add_points_to_positively_sloped_segments(&status, status.y, &range);
1092 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1093 add_points_to_ending_segments(&status, status.y);
1095 recalculate_windings(&status, &range);
1097 check_status(&status);
1098 dict_destroy(status.intersecting_segs);
1099 dict_destroy(status.segs_with_point);
1103 dict_destroy(status.seen_crossings);
1105 actlist_destroy(status.actlist);
1106 heap_destroy(queue);
1107 xrow_destroy(status.xrow);
1109 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1110 p->edges = status.output;
1112 add_horizontals(p, &windrule_evenodd); // output is always even/odd