17 char point_equals(const void*o1, const void*o2)
19 const point_t*p1 = o1;
20 const point_t*p2 = o2;
21 return p1->x == p2->x && p1->y == p2->y;
23 unsigned int point_hash(const void*o)
28 void* point_dup(const void*o)
31 point_t*n = malloc(sizeof(point_t));
36 void point_free(void*o)
50 typedef struct _status {
59 dict_t*seen_crossings; //list of crossing we saw so far
60 dict_t*intersecting_segs; //list of segments intersecting in this scanline
61 dict_t*segs_with_point; //lists of segments that received a point in this scanline
65 int compare_events_simple(const void*_a,const void*_b)
67 event_t* a = (event_t*)_a;
68 event_t* b = (event_t*)_b;
71 } else if(a->p.y > b->p.y) {
73 } else if(a->p.x < b->p.x) {
75 } else if(a->p.x > b->p.x) {
81 int compare_events(const void*_a,const void*_b)
83 event_t* a = (event_t*)_a;
84 event_t* b = (event_t*)_b;
85 int d = b->p.y - a->p.y;
87 /* we should schedule start events after end/intersect.
88 The order of end/intersect doesn't actually matter, however,
89 so this might be doing too much */
90 d = b->type - a->type;
96 gfxpoly_t* gfxpoly_new(double gridsize)
98 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
99 p->gridsize = gridsize;
102 void gfxpoly_destroy(gfxpoly_t*poly)
104 edge_t* s = poly->edges;
106 edge_t*next = s->next;
112 char gfxpoly_check(gfxpoly_t*poly)
114 edge_t* s = poly->edges;
115 dict_t*d = dict_new2(&point_type);
117 if(!dict_contains(d, &s->a)) {
118 dict_put(d, &s->a, (void*)(ptroff_t)1);
120 int count = (ptroff_t)dict_lookup(d, &s->a);
123 dict_put(d, &s->a, (void*)(ptroff_t)count);
125 if(!dict_contains(d, &s->b)) {
126 dict_put(d, &s->b, (void*)(ptroff_t)1);
128 int count = (ptroff_t)dict_lookup(d, &s->b);
131 dict_put(d, &s->b, (void*)(ptroff_t)count);
135 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
136 int count = (ptroff_t)c;
138 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
145 void gfxpoly_dump(gfxpoly_t*poly)
147 edge_t* s = poly->edges;
148 double g = poly->gridsize;
150 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
155 inline static event_t event_new()
158 memset(&e, 0, sizeof(e));
162 void event_dump(event_t*e)
164 if(e->type == EVENT_HORIZONTAL) {
165 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);
166 } else if(e->type == EVENT_START) {
167 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
168 } else if(e->type == EVENT_END) {
169 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
170 } else if(e->type == EVENT_CROSS) {
171 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
177 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
178 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
180 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
185 int x = x1;x1=x2;x2=x;
186 int y = y1;y1=y2;y2=y;
189 /* up/down for horizontal segments is handled by "rotating"
190 them 90° anticlockwise in screen coordinates (tilt your head to
195 int x = x1;x1=x2;x2=x;
196 int y = y1;y1=y2;y2=y;
203 s->k = (double)x1*y2-(double)x2*y1;
204 s->left = s->right = 0;
208 s->polygon_nr = polygon_nr;
211 static int segment_count=0;
212 s->nr = segment_count++;
215 assert(LINE_EQ(s->a, s) == 0);
216 assert(LINE_EQ(s->b, s) == 0);
218 /* check that all signs are in order:
226 p.x = min32(s->a.x, s->b.x);
227 assert(LINE_EQ(p, s) <= 0);
228 p.x = max32(s->a.x, s->b.x);
229 assert(LINE_EQ(p, s) >= 0);
231 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
234 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
236 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
237 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
240 void segment_destroy(segment_t*s)
242 dict_clear(&s->scheduled_crossings);
246 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
249 for(l=list;l;l=l->next) {
250 if(l->a.x == l->b.x &&
252 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
255 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
257 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
258 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
259 s->dir==DIR_UP?"up":"down");
261 event_t e = event_new();
262 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
270 void schedule_endpoint(status_t*status, segment_t*s)
272 // schedule end point of segment
273 assert(s->b.y > status->y);
279 heap_put(status->queue, &e);
282 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
284 /* the code that's required (and the checks you can perform) before
285 it can be said with 100% certainty that we indeed have a valid crossing
286 amazes me every time. -mk */
289 /* we probably could precompute these */
290 int32_t minx1 = min32(s1->a.x,s1->b.x);
291 int32_t miny1 = min32(s1->a.y,s1->b.y);
292 int32_t maxx1 = max32(s1->a.x,s1->b.x);
293 int32_t maxy1 = max32(s1->a.y,s1->b.y);
294 int32_t minx2 = min32(s2->a.x,s2->b.x);
295 int32_t miny2 = min32(s2->a.y,s2->b.y);
296 int32_t maxx2 = max32(s2->a.x,s2->b.x);
297 int32_t maxy2 = max32(s2->a.y,s2->b.y);
299 /* both segments are active, so this can't happen */
300 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
302 /* TODO: optimize this. remove y, precompute the two x values */
303 if(maxx1 <= minx2 || maxx2 <= minx1 ||
304 maxy1 <= miny2 || maxy2 <= miny1) {
305 /* bounding boxes don't intersect */
309 if(dict_contains(&s1->scheduled_crossings, s2)) {
310 /* FIXME: this whole segment hashing thing is really slow */
311 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
313 // we already know about this one
317 double adx = s1->delta.x;
318 double ady = s1->delta.y;
319 double bdx = s2->delta.x;
320 double bdy = s2->delta.y;
321 double det = adx*bdy - ady*bdx;
324 // lines are exactly on top of each other (ignored)
326 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
330 /* lines are parallel */
334 double asign2 = LINE_EQ(s1->a, s2);
335 double bsign2 = LINE_EQ(s1->b, s2);
336 if(asign2<0 && bsign2<0) {
337 // segment1 is completely to the left of segment2
340 if(asign2>0 && bsign2>0) {
341 // segment2 is completely to the left of segment1
345 // segment1 touches segment2 in a single point (ignored)
347 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
352 // segment1 touches segment2 in a single point (ignored)
354 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
358 double asign1 = LINE_EQ(s2->a, s1);
359 double bsign1 = LINE_EQ(s2->b, s1);
360 if(asign1<0 && bsign1<0) {
361 // segment1 is completely to the left of segment2
364 if(asign1>0 && bsign1>0) {
365 // segment2 is completely to the left of segment1
369 // segment2 touches segment1 in a single point (ignored)
371 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
376 // segment2 touches segment1 in a single point (ignored)
378 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
383 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
384 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
387 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
388 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
390 assert(p.y >= status->y);
395 assert(!dict_contains(status->seen_crossings, &pair));
396 dict_put(status->seen_crossings, &pair, 0);
397 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
400 /* we insert into each other's intersection history because these segments might switch
401 places and we still want to look them up quickly after they did */
402 dict_put(&s1->scheduled_crossings, s2, 0);
403 dict_put(&s2->scheduled_crossings, s1, 0);
405 event_t e = event_new();
406 e.type = EVENT_CROSS;
410 heap_put(status->queue, &e);
414 void exchange_two(status_t*status, event_t*e)
416 //exchange two segments in list
417 segment_t*s1 = e->s1;
418 segment_t*s2 = e->s2;
420 if(!dict_contains(status->intersecting_segs, s1))
421 dict_put(status->intersecting_segs, s1, 0);
422 if(!dict_contains(status->intersecting_segs, s2))
423 dict_put(status->intersecting_segs, s2, 0);
425 segment_t*left = actlist_left(status->actlist, s2);
426 segment_t*right = actlist_right(status->actlist, s1);
429 actlist_swap(status->actlist, s1, s2);
430 assert(actlist_right(status->actlist, s2) == s1);
431 assert(actlist_left(status->actlist, s1) == s2);
432 left = actlist_left(status->actlist, s2);
433 right = actlist_right(status->actlist, s1);
435 schedule_crossing(status, left, s2);
437 schedule_crossing(status, s1, right);
440 typedef struct _box {
441 point_t left1, left2, right1, right2;
443 static inline box_t box_new(int x, int y)
446 box.right1.x = box.right2.x = x;
447 box.left1.x = box.left2.x = x-1;
448 box.left1.y = box.right1.y = y-1;
449 box.left2.y = box.right2.y = y;
454 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
456 assert(s->pos.x != p.x || s->pos.y != p.y);
459 if(!dict_contains(status->segs_with_point, s))
460 dict_put(status->segs_with_point, s, 0);
463 assert(s->fs_out_ok);
466 fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y);
468 // omit horizontal lines
469 if(s->pos.y != p.y) {
470 edge_t*e = malloc(sizeof(edge_t));
473 assert(e->a.y != e->b.y);
474 e->next = status->output;
479 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
485 /* possible optimizations:
486 1.) keep two different active lists around, one for negative and one for
488 2.) delay starting events until after this function (tricky, because we *do*
489 need the start coordinates)
500 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y)
503 for(t=0;t<status->xrow->num;t++) {
504 box_t box = box_new(status->xrow->x[t], y);
505 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
506 seg = actlist_right(status->actlist, seg);
509 // this segment just started, ignore it
510 } else if(seg->delta.x < 0) {
511 // ignore segment w/ negative slope
513 double d1 = LINE_EQ(box.right1, seg);
514 double d2 = LINE_EQ(box.right2, seg);
516 insert_point_into_segment(status, seg, box.right2);
521 seg = actlist_right(status->actlist, seg);
533 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y)
536 for(t=status->xrow->num-1;t>=0;t--) {
537 box_t box = box_new(status->xrow->x[t], y);
538 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
541 // this segment just started, ignore it
542 } else if(seg->delta.x >= 0) {
543 // ignore segment w/ positive slope
545 double d1 = LINE_EQ(box.left1, seg);
546 double d2 = LINE_EQ(box.left2, seg);
548 insert_point_into_segment(status, seg, box.right2);
553 seg = actlist_left(status->actlist, seg);
558 static void recalculate_windings(status_t*status)
560 /* TODO: we could use some clever second linked list structure so that we
561 only need to process points we know we marked */
563 segment_t*s = actlist_leftmost(status->actlist);
566 windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons);
567 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
568 s->fs_out = status->windrule->diff(&wind, &s->wind);
571 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");
574 s = actlist_right(status->actlist, s);
577 fprintf(stderr, "\n");
582 /* we need to handle horizontal lines in order to add points to segments
583 we otherwise would miss during the windrule re-evaluation */
584 void intersect_with_horizontal(status_t*status, segment_t*h)
586 segment_t* left = actlist_find(status->actlist, h->a, h->a);
587 segment_t* right = actlist_find(status->actlist, h->b, h->b);
589 /* not strictly necessary, also done by the event */
590 xrow_add(status->xrow, h->a.x);
593 left = actlist_right(status->actlist, left);
594 right = actlist_right(status->actlist, right);
600 x1 + ((x2-x1)*(y-y1)) / dy =
601 (x1*(y2-y) + x2*(y-y1)) / dy
607 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
613 assert(p.x >= h->a.x);
614 assert(p.x <= h->b.x);
615 assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
616 assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
617 xrow_add(status->xrow, p.x);
619 s = actlist_right(status->actlist, s);
623 void event_apply(status_t*status, event_t*e)
626 case EVENT_HORIZONTAL: {
630 intersect_with_horizontal(status, e->s1);
634 //delete segment from list
638 dict_del(status->intersecting_segs, s);
639 dict_del(status->segs_with_point, s);
640 assert(!dict_contains(status->intersecting_segs, s));
641 assert(!dict_contains(status->segs_with_point, s));
643 insert_point_into_segment(status, s, s->b);
644 segment_t*left = actlist_left(status->actlist, s);
645 segment_t*right = actlist_right(status->actlist, s);
646 actlist_delete(status->actlist, s);
648 schedule_crossing(status, left, right);
649 segment_destroy(s);e->s1=0;
653 //insert segment into list
658 actlist_insert(status->actlist, e->p, s);
659 segment_t*left = actlist_left(status->actlist, s);
660 segment_t*right = actlist_right(status->actlist, s);
662 schedule_crossing(status, left, s);
664 schedule_crossing(status, s, right);
665 schedule_endpoint(status, e->s1);
669 // exchange two segments
673 if(actlist_right(status->actlist, e->s1) == e->s2 &&
674 actlist_left(status->actlist, e->s2) == e->s1) {
675 exchange_two(status, e);
677 /* ignore this crossing for now (there are some line segments in between).
678 it'll get rescheduled as soon as the "obstacles" are gone */
679 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
680 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
681 assert(del1 && del2);
686 assert(dict_contains(status->seen_crossings, &pair));
687 dict_del(status->seen_crossings, &pair);
695 void check_status(status_t*status)
697 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
698 if((s->pos.x != s->b.x ||
699 s->pos.y != s->b.y) &&
700 !dict_contains(status->segs_with_point, s)) {
701 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
703 s->delta.x<0?"-":"+",
711 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
714 |..| |...........| | |
715 |..| |...........| | |
716 |..+ + +..| +--+ +--+
717 |...........| |..| | |
718 |...........| |..| | |
722 fprintf(stderr, "========================================================================\n");
724 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
725 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
727 actlist_t* actlist = actlist_new();
729 event_t*e = heap_chopmax(queue);
735 actlist_verify_and_dump(actlist, y-1);
738 if(fill && x != e->p.x) {
740 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
742 edge_t*l= malloc(sizeof(edge_t));
746 l->next = poly->edges;
752 windstate_t before,after;
755 actlist_insert(actlist, e->p, s);
762 left = actlist_left(actlist, s);
764 before = left?left->wind:windrule->start(1);
765 after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
769 left = actlist_left(actlist, s);
770 actlist_delete(actlist, s);
773 after = left?left->wind:windrule->start(1);
780 fill ^= 1;//(before.is_filled != after.is_filled);
782 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
783 y, e->type==EVENT_START?"start":"end",
787 before.is_filled, after.is_filled);
790 if(e->type == EVENT_END)
793 e = heap_chopmax(queue);
794 } while(e && y == e->p.y);
797 fprintf(stderr, "Error: polygon is bleeding\n");
803 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
805 heap_t* queue = heap_new(sizeof(event_t), compare_events);
807 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
810 memset(&status, 0, sizeof(status_t));
811 status.num_polygons = 1;
812 status.queue = queue;
813 status.windrule = windrule;
814 status.actlist = actlist_new();
816 status.seen_crossings = dict_new2(&point_type);
819 status.xrow = xrow_new();
821 event_t*e = heap_chopmax(queue);
825 status.intersecting_segs = dict_new2(&ptr_type);
826 status.segs_with_point = dict_new2(&ptr_type);
827 fprintf(stderr, "----------------------------------- %d\n", status.y);
828 actlist_verify_and_dump(status.actlist, status.y-1);
830 xrow_reset(status.xrow);
832 xrow_add(status.xrow, e->p.x);
833 event_apply(&status, e);
835 e = heap_chopmax(queue);
836 } while(e && status.y == e->p.y);
838 xrow_sort(status.xrow);
839 add_points_to_positively_sloped_segments(&status, status.y);
840 add_points_to_negatively_sloped_segments(&status, status.y);
841 recalculate_windings(&status);
843 check_status(&status);
844 dict_destroy(status.intersecting_segs);
845 dict_destroy(status.segs_with_point);
849 dict_destroy(status.seen_crossings);
851 actlist_destroy(status.actlist);
853 xrow_destroy(status.xrow);
855 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
856 p->edges = status.output;
858 add_horizontals(p, &windrule_evenodd); // output is always even/odd