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, "%% begin\n");
179 edge_t* s = poly->edges;
181 fprintf(fi, "%g setgray\n", s->b.y < s->a.y ? 0.7 : 0);
182 fprintf(fi, "%d %d moveto\n", s->a.x, s->a.y);
183 fprintf(fi, "%d %d lineto\n", s->b.x, s->b.y);
184 fprintf(fi, "stroke\n");
187 fprintf(fi, "showpage\n");
191 inline static event_t event_new()
194 memset(&e, 0, sizeof(e));
198 void event_dump(event_t*e)
200 if(e->type == EVENT_HORIZONTAL) {
201 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);
202 } else if(e->type == EVENT_START) {
203 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
204 } else if(e->type == EVENT_END) {
205 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
206 } else if(e->type == EVENT_CROSS) {
207 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
213 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
214 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
216 void segment_dump(segment_t*s)
218 fprintf(stderr, "(%d,%d)->(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y);
219 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
220 (double)s->delta.x / s->delta.y);
223 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
228 int x = x1;x1=x2;x2=x;
229 int y = y1;y1=y2;y2=y;
232 /* up/down for horizontal segments is handled by "rotating"
233 them 90° anticlockwise in screen coordinates (tilt your head to
238 int x = x1;x1=x2;x2=x;
239 int y = y1;y1=y2;y2=y;
246 s->k = (double)x1*y2-(double)x2*y1;
247 s->left = s->right = 0;
250 s->minx = min32(x1,x2);
251 s->maxx = max32(x1,x2);
254 s->polygon_nr = polygon_nr;
257 static int segment_count=0;
258 s->nr = segment_count++;
261 assert(LINE_EQ(s->a, s) == 0);
262 assert(LINE_EQ(s->b, s) == 0);
264 /* check that all signs are in order:
272 p.x = min32(s->a.x, s->b.x);
273 assert(LINE_EQ(p, s) <= 0);
274 p.x = max32(s->a.x, s->b.x);
275 assert(LINE_EQ(p, s) >= 0);
277 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
280 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
282 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
283 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
286 void segment_destroy(segment_t*s)
288 dict_clear(&s->scheduled_crossings);
292 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
295 for(l=list;l;l=l->next) {
296 if(l->a.x == l->b.x &&
298 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
301 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
305 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
306 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
307 s->dir==DIR_UP?"up":"down");
309 event_t e = event_new();
310 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
318 void schedule_endpoint(status_t*status, segment_t*s)
320 // schedule end point of segment
321 assert(s->b.y > status->y);
327 heap_put(status->queue, &e);
330 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
332 /* the code that's required (and the checks you can perform) before
333 it can be said with 100% certainty that we indeed have a valid crossing
334 amazes me every time. -mk */
338 assert(s1->right == s2);
339 assert(s2->left == s1);
340 int32_t miny1 = min32(s1->a.y,s1->b.y);
341 int32_t maxy1 = max32(s1->a.y,s1->b.y);
342 int32_t miny2 = min32(s2->a.y,s2->b.y);
343 int32_t maxy2 = max32(s2->a.y,s2->b.y);
344 int32_t minx1 = min32(s1->a.x,s1->b.x);
345 int32_t minx2 = min32(s2->a.x,s2->b.x);
346 int32_t maxx1 = max32(s1->a.x,s1->b.x);
347 int32_t maxx2 = max32(s2->a.x,s2->b.x);
348 /* check that precomputation is sane */
349 assert(minx1 == s1->minx && minx2 == s2->minx);
350 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
351 /* both segments are active, so this can't happen */
352 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
353 /* we know that right now, s2 is to the right of s1, so there's
354 no way the complete bounding box of s1 is to the right of s1 */
355 assert(!(s1->minx > s2->maxx));
356 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
359 if(s1->maxx <= s2->minx) {
360 /* bounding boxes don't intersect */
364 if(dict_contains(&s1->scheduled_crossings, s2)) {
365 /* FIXME: this whole segment hashing thing is really slow */
366 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
367 return; // we already know about this one
370 double adx = s1->delta.x;
371 double ady = s1->delta.y;
372 double bdx = s2->delta.x;
373 double bdy = s2->delta.y;
374 double det = adx*bdy - ady*bdx;
377 // lines are exactly on top of each other (ignored)
379 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
383 /* lines are parallel */
387 double asign2 = LINE_EQ(s1->a, s2);
388 double bsign2 = LINE_EQ(s1->b, s2);
389 if(asign2<0 && bsign2<0) {
390 // segment1 is completely to the left of segment2
393 if(asign2>0 && bsign2>0) {
394 // segment2 is completely to the left of segment1
398 // segment1 touches segment2 in a single point (ignored)
400 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
405 // segment1 touches segment2 in a single point (ignored)
407 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
411 double asign1 = LINE_EQ(s2->a, s1);
412 double bsign1 = LINE_EQ(s2->b, s1);
413 if(asign1<0 && bsign1<0) {
414 // segment1 is completely to the left of segment2
417 if(asign1>0 && bsign1>0) {
418 // segment2 is completely to the left of segment1
422 // segment2 touches segment1 in a single point (ignored)
424 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
429 // segment2 touches segment1 in a single point (ignored)
431 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
436 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
437 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
440 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
441 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
443 assert(p.y >= status->y);
445 assert(p.x >= s1->minx && p.x <= s1->maxx);
446 assert(p.x >= s2->minx && p.x <= s2->maxx);
451 assert(!dict_contains(status->seen_crossings, &pair));
452 dict_put(status->seen_crossings, &pair, 0);
455 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
458 /* we insert into each other's intersection history because these segments might switch
459 places and we still want to look them up quickly after they did */
460 dict_put(&s1->scheduled_crossings, s2, 0);
461 dict_put(&s2->scheduled_crossings, s1, 0);
463 event_t e = event_new();
464 e.type = EVENT_CROSS;
468 heap_put(status->queue, &e);
472 void exchange_two(status_t*status, event_t*e)
474 //exchange two segments in list
475 segment_t*s1 = e->s1;
476 segment_t*s2 = e->s2;
478 if(!dict_contains(status->intersecting_segs, s1))
479 dict_put(status->intersecting_segs, s1, 0);
480 if(!dict_contains(status->intersecting_segs, s2))
481 dict_put(status->intersecting_segs, s2, 0);
483 segment_t*left = actlist_left(status->actlist, s2);
484 segment_t*right = actlist_right(status->actlist, s1);
487 actlist_swap(status->actlist, s1, s2);
488 assert(actlist_right(status->actlist, s2) == s1);
489 assert(actlist_left(status->actlist, s1) == s2);
490 left = actlist_left(status->actlist, s2);
491 right = actlist_right(status->actlist, s1);
493 schedule_crossing(status, left, s2);
495 schedule_crossing(status, s1, right);
498 typedef struct _box {
499 point_t left1, left2, right1, right2;
501 static inline box_t box_new(int x, int y)
504 box.right1.x = box.right2.x = x;
505 box.left1.x = box.left2.x = x-1;
506 box.left1.y = box.right1.y = y-1;
507 box.left2.y = box.right2.y = y;
512 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
514 assert(s->pos.x != p.x || s->pos.y != p.y);
517 if(!dict_contains(status->segs_with_point, s))
518 dict_put(status->segs_with_point, s, 0);
519 assert(s->fs_out_ok);
524 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
525 s->pos.x, s->pos.y, p.x, p.y);
527 // omit horizontal lines
528 if(s->pos.y != p.y) {
529 edge_t*e = rfx_calloc(sizeof(edge_t));
533 assert(e->a.y != e->b.y);
534 e->next = status->output;
539 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
545 /* by restricting the recalculation of line segments to a range between the lowest
546 and the highest modified segment, we only do about a 33% overprocessing of fill
547 styles. (update: that statistic might be outdated now that xmin/xmax are double) */
548 typedef struct _segrange {
555 static inline char xpos_eq(segment_t*s1, segment_t*s2, int y)
557 if(XPOS_EQ(s1, s2, y)) {
563 void segrange_adjust_endpoints(segrange_t*range, int y)
566 /* this would mean that the segment left/right of the minimum/maximum
567 intersects the current segment exactly at the scanline, but somehow
568 wasn't found to be passing through the same snapping box */
569 assert(!min || !min->left || !XPOS_EQ(min, min->left, y));
570 assert(!max || !max->right || !XPOS_EQ(max, max->right, y));
573 segment_t*min = range->segmin;
574 segment_t*max = range->segmax;
575 if(min) while(min->left && xpos_eq(min, min->left, y)) {
578 if(max) while(max->right && xpos_eq(max, max->right, y)) {
584 void segrange_test_segment_min(segrange_t*range, segment_t*seg, int y)
587 /* we need to calculate the xpos anew (and can't use start coordinate or
588 intersection coordinate), because we need the xpos exactly at the end of
590 TODO: might be faster to use XPOS_COMPARE here (see also _max)
592 double x = XPOS(seg, y);
593 if(!range->segmin || x<range->xmin) {
598 void segrange_test_segment_max(segrange_t*range, segment_t*seg, int y)
601 double x = XPOS(seg, y);
602 if(!range->segmax || x>range->xmax) {
617 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
619 segment_t*first=0, *last = 0;
621 for(t=0;t<status->xrow->num;t++) {
622 box_t box = box_new(status->xrow->x[t], y);
623 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
625 seg = actlist_right(status->actlist, seg);
629 // this segment started in this scanline, ignore it
630 seg->changed = 1;last = seg;if(!first) {first=seg;}
631 } else if(seg->delta.x <= 0) {
632 // ignore segment w/ negative slope
634 last = seg;if(!first) {first=seg;}
635 double d1 = LINE_EQ(box.right1, seg);
636 double d2 = LINE_EQ(box.right2, seg);
639 insert_point_into_segment(status, seg, box.right2);
641 /* we unfortunately can't break here- the active list is sorted according
642 to the *bottom* of the scanline. hence pretty much everything that's still
643 coming might reach into our box */
647 seg = actlist_right(status->actlist, seg);
650 segrange_test_segment_min(range, first, y);
651 segrange_test_segment_max(range, last, y);
661 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
663 segment_t*first=0, *last = 0;
665 for(t=status->xrow->num-1;t>=0;t--) {
666 box_t box = box_new(status->xrow->x[t], y);
667 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
671 // this segment started in this scanline, ignore it
672 seg->changed = 1;last = seg;if(!first) {first=seg;}
673 } else if(seg->delta.x > 0) {
674 // ignore segment w/ positive slope
676 last = seg;if(!first) {first=seg;}
677 double d1 = LINE_EQ(box.left1, seg);
678 double d2 = LINE_EQ(box.left2, seg);
681 insert_point_into_segment(status, seg, box.right2);
686 seg = actlist_left(status->actlist, seg);
689 segrange_test_segment_min(range, last, y);
690 segrange_test_segment_max(range, first, y);
693 /* segments ending in the current scanline need xrow treatment like everything else.
694 (consider an intersection taking place just above a nearly horizontal segment
695 ending on the current scanline- the intersection would snap down *below* the
696 ending segment if we don't add the intersection point to the latter right away)
697 we need to treat ending segments seperately, however. we have to delete them from
698 the active list right away to make room for intersect operations (which might
699 still be in the current scanline- consider two 45° polygons and a vertical polygon
700 intersecting on an integer coordinate). but once they're no longer in the active list,
701 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
702 them to the active list just for point snapping would be overkill.
703 (One other option to consider, however, would be to create a new active list only
706 void add_points_to_ending_segments(status_t*status, int32_t y)
708 segment_t*seg = status->ending_segments;
710 segment_t*next = seg->right;seg->right=0;
712 assert(seg->b.y == status->y);
714 if(status->xrow->num == 1) {
716 point_t p = {status->xrow->x[0], y};
717 insert_point_into_segment(status, seg, p);
720 int start=0,end=status->xrow->num,dir=1;
721 if(seg->delta.x < 0) {
722 start = status->xrow->num-1;
725 for(t=start;t!=end;t+=dir) {
726 box_t box = box_new(status->xrow->x[t], y);
727 double d0 = LINE_EQ(box.left1, seg);
728 double d1 = LINE_EQ(box.left2, seg);
729 double d2 = LINE_EQ(box.right1, seg);
730 double d3 = LINE_EQ(box.right2, seg);
731 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
732 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
733 insert_point_into_segment(status, seg, box.right2);
739 /* we *need* to find a point to insert. the segment's own end point
740 is in that list, for Pete's sake. */
744 // now that this is done, too, we can also finally free this segment
745 segment_destroy(seg);
748 status->ending_segments = 0;
751 static void recalculate_windings(status_t*status, segrange_t*range)
753 segrange_adjust_endpoints(range, status->y);
755 segment_t*s = range->segmin;
756 segment_t*end = range->segmax;
760 s = actlist_leftmost(status->actlist);
762 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
763 s == range->segmin?"S":(
764 s == range->segmax?"E":""));
767 fprintf(stderr, "\n");
771 /* test sanity: check that we don't have changed segments
772 outside of the given range */
773 s = actlist_leftmost(status->actlist);
774 while(s && s!=range->segmin) {
776 s = actlist_right(status->actlist, s);
778 s = actlist_rightmost(status->actlist);
779 while(s && s!=range->segmax) {
781 s = actlist_left(status->actlist, s);
783 /* in check mode, go through the whole interval so we can test
784 that all polygons where the fillstyle changed also have seg->changed=1 */
785 s = actlist_leftmost(status->actlist);
790 end = actlist_right(status->actlist, end);
796 segment_t* left = actlist_left(status->actlist, s);
797 windstate_t wind = left?left->wind:status->windrule->start(status->num_polygons);
798 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
799 fillstyle_t*fs_old = s->fs_out;
800 s->fs_out = status->windrule->diff(&wind, &s->wind);
802 assert(!(!s->changed && fs_old!=s->fs_out));
807 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");
810 s = actlist_right(status->actlist, s);
813 fprintf(stderr, "\n");
817 /* we need to handle horizontal lines in order to add points to segments
818 we otherwise would miss during the windrule re-evaluation */
819 void intersect_with_horizontal(status_t*status, segment_t*h)
821 segment_t* left = actlist_find(status->actlist, h->a, h->a);
822 segment_t* right = actlist_find(status->actlist, h->b, h->b);
824 /* not strictly necessary, also done by the event */
825 xrow_add(status->xrow, h->a.x);
828 left = actlist_right(status->actlist, left);
829 right = actlist_right(status->actlist, right);
834 int x = XPOS_INT(s, status->y);
836 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
844 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
845 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
846 xrow_add(status->xrow, x);
848 s = actlist_right(status->actlist, s);
852 void event_apply(status_t*status, event_t*e)
855 case EVENT_HORIZONTAL: {
859 intersect_with_horizontal(status, e->s1);
860 segment_destroy(e->s1);e->s1=0;
864 //delete segment from list
870 dict_del(status->intersecting_segs, s);
871 dict_del(status->segs_with_point, s);
872 assert(!dict_contains(status->intersecting_segs, s));
873 assert(!dict_contains(status->segs_with_point, s));
875 segment_t*left = actlist_left(status->actlist, s);
876 segment_t*right = actlist_right(status->actlist, s);
877 actlist_delete(status->actlist, s);
879 schedule_crossing(status, left, right);
881 s->left = 0; s->right = status->ending_segments;
882 status->ending_segments = s;
886 //insert segment into list
891 actlist_insert(status->actlist, e->p, 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 actlist_insert(actlist, e->p, s);
1000 left = actlist_left(actlist, s);
1002 before = left?left->wind:windrule->start(1);
1003 after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
1007 left = actlist_left(actlist, s);
1008 actlist_delete(actlist, s);
1011 after = left?left->wind:windrule->start(1);
1018 fill ^= 1;//(before.is_filled != after.is_filled);
1020 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
1021 y, e->type==EVENT_START?"start":"end",
1025 before.is_filled, after.is_filled);
1028 if(e->type == EVENT_END)
1032 e = heap_chopmax(queue);
1033 } while(e && y == e->p.y);
1035 assert(!fill); // check that polygon is not bleeding
1037 actlist_destroy(actlist);
1038 heap_destroy(queue);
1041 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
1043 current_polygon = poly;
1044 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1046 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
1049 memset(&status, 0, sizeof(status_t));
1050 status.num_polygons = 1;
1051 status.queue = queue;
1052 status.windrule = windrule;
1053 status.actlist = actlist_new();
1055 status.seen_crossings = dict_new2(&point_type);
1058 status.xrow = xrow_new();
1060 event_t*e = heap_chopmax(queue);
1064 status.intersecting_segs = dict_new2(&ptr_type);
1065 status.segs_with_point = dict_new2(&ptr_type);
1069 fprintf(stderr, "----------------------------------- %d\n", status.y);
1070 actlist_dump(status.actlist, status.y-1);
1073 actlist_verify(status.actlist, status.y-1);
1075 xrow_reset(status.xrow);
1077 xrow_add(status.xrow, e->p.x);
1078 event_apply(&status, e);
1080 e = heap_chopmax(queue);
1081 } while(e && status.y == e->p.y);
1083 xrow_sort(status.xrow);
1085 memset(&range, 0, sizeof(range));
1087 actlist_dump(status.actlist, status.y);
1089 add_points_to_positively_sloped_segments(&status, status.y, &range);
1090 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1091 add_points_to_ending_segments(&status, status.y);
1093 recalculate_windings(&status, &range);
1095 check_status(&status);
1096 dict_destroy(status.intersecting_segs);
1097 dict_destroy(status.segs_with_point);
1101 dict_destroy(status.seen_crossings);
1103 actlist_destroy(status.actlist);
1104 heap_destroy(queue);
1105 xrow_destroy(status.xrow);
1107 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1108 p->edges = status.output;
1110 add_horizontals(p, &windrule_evenodd); // output is always even/odd